From the documentation:
Beautiful Soup provides a special argument called attrs which you can use in these situations. attrs is a dictionary that acts just like the keyword arguments:
soup.findAll(id=re.compile("para$"))
# [<p id="firstpara" align="center">This is paragraph <b>one</b>.</p>,
# <p id="secondpara" align="blah">This is paragraph <b>two</b>.</p>]
soup.findAll(attrs={'id' : re.compile("para$")})
# [<p id="firstpara" align="center">This is paragraph <b>one</b>.</p>,
# <p id="secondpara" align="blah">This is paragraph <b>two</b>.</p>]
You can use attrs if you need to put restrictions on attributes whose names are Python reserved words, like class, for, or import; or attributes whose names are non-keyword arguments to the Beautiful Soup search methods: name, recursive, limit, text, or attrs itself.
from BeautifulSoup import BeautifulStoneSoup
xml = '<person name="Bob"><parent rel="mother" name="Alice">'
xmlSoup = BeautifulStoneSoup(xml)
xmlSoup.findAll(name="Alice")
# []
xmlSoup.findAll(attrs={"name" : "Alice"})
# [parent rel="mother" name="Alice"></parent>]
So for your given example:
soup.findAll(attrs={ "foo" : re.compile(".*") })
# or
soup.findAll(attrs={ re.compile("foo:.*") : re.compile(".*") })