Null Disquisition

Everyone loves pickle, I mean, what’s not to love. Super fast object serialization (via cPickle). However, there are some legitimate concerns regarding the security of pickle – specifically the load/loads method. The basic problem is, if you try to unpickle untrusted data, you are liable to create some objects that can do nasty things (like make system calls). Python even gives us a nice warning right in the docs

Warning pickle module is not intended to be secure against erroneous or maliciously constructed data. Never unpickle data received from an untrusted or unauthenticated source.

Now there are plenty of things you can do to improve the security of the unpickling process. Python lets you subclass pickle.Unpickler to give the user finer grained control over what gets unpickled. This is a fine approach (a nice example here), and will work for most, but I will give my take on the issue.

For most of the applications I write that use pickle, I’m just looking for a way to store arbitrary Python data as a string. One example might be storing small data objects on S3, or perhaps implementing user sessions for a webapp. Either way, I should be able to trust my own data for unpickling, but it’s always best to be double-extra-sure when dealing with something where you can blindly execute arbitrary bits of code (think, the evil eval method).

So, for my case, I simply want to verify that the pickled data I stored is coming back to me unmodified. My solution: sign the pickled data. Using the same signing method as AWS, I present the following:

import hmac
import hashlib
import base64
from cPickle import dumps
 # The unsigned pickled data
string_to_sign = dumps({'foo':"bar",'spam':"eggs",'the answer':42})
 # The signature object
signature = hmac.HMAC(key="my application's super secret key",
    msg= string_to_sign, digestmod=hashlib.sha256)
 # The signed string: store this
signed_string = string_to_sign + base64.encodestring(signature.digest())

Now you have your pickled data as the first part of the string with the last 45 characters being the signature. The key for HMAC signing is specific to your application, so if someone gets access to your pickled data and tries to mess with it and resign it, it won’t work. Here’s the unpickling process:

import hmac
import hashlib
import base64
from cPickle import loads
 # Break up the signed string into message and signature
signature = signed_string[-45:]
message = signed_string[:-45]
 # Calculate the signature of the message
msg_sig = hmac.HMAC(key="my application's super secret key",
    msg= message, digestmod=hashlib.sha256)
 # See that it matches the given signature
assert base64.encodestring(msg_sig.digest()) == signature

-David

Recently, at work we have written a totally badass XML API for clients to interface with our data (sorry no public side yet). After some gentle reassuring (and some not-so-gentle arm twisting), I convinced my boss-man we could do this in Python with AWS on the back-end. We settled on the Turbogears 2.0 meta-framework using Amazon S3/SimpleDB. The whole experience was very educational for many reasons – one, we had never using something besides MySQL for a data store, two, we had never used a Python framework before, and three, we had never really developed an app with a proper set of tests. That final point, testing, is the subject of this entry.

Py.Test, from the vaingloriously-named “py” module, is my unit testing framework of choice (I have written about it before). It provides a convenient way to collect tests and to write generative tests (which are super useful) for unit testing. After getting a few sets of unit tests rolled out for our API, we recognized that we would need some higher level tests – so called functional, or acceptance tests.

Functional Tests

Functional tests describe high-level tests that rely on the interaction of many components of the system, whereas a unit test will only test smaller, lower level components. For example, one (very high-level) functional test for an XML API would be to see that the resulting XML is well-formed. The well-formedness of an XML response from an API request is dependent on several components of the system. It requires proper request parsing, validation, error handling, template rendering, et al. A more typical test might be to see that the number of items returned by the API does not exceed a user-provided maximum, i.e., if the user requests http://api.example.com/?[request params]&max_count=10, no more than 10 results are shown.

Now, how to go about running these tests. The number of functional testing frameworks is too great to mention (here’s a bunch), but one that is well known and widely used is Selenium. It is written in Java and can do some pretty fancy stuff. However, one big drawback of Selenium is it’s weight. It’s heavy – it is Java after all, and requires a client server (whether you sacrifice your own cycles or a remote server). For the simple functional tests we were writing, it was completely overkill. After searching around for a Python functional testing framework (or at least something lighter than Selenium), it occurred to me that I could just use the test-collecting abilities of Py.Test plus some additional libraries. And that’s what we did.

Bottom Line

Mix together PyXML, Urllib2, and Py.Test and you have a pretty powerful (and portable) testing suite in Python. PyXML extends the built-in ‘xml’ module with some really nice packages including an XPath parser which I love.

Exempli Gratia

Consider an API that has a “users” noun, and just one verb “show”. We will allow one optional parameter order_by and one required parameter max_count. An valid URL would look like http://api.example.com/users/show?max_count=10&order_by=date.

We’ll start by creating the class that will contain the tests, and writing a function to get an XML doc given some url parameters.

import urllib2
from collections import defaultdict
from xml.dom import minidom
from xml import xpath
class TestUserNoun:
    def get_xml_doc(self,url_params):
        url = "http://api.example.com/users/show?"
        url += "max_count=%(max_count)s&order_by=%(order_by)s"
        url_p = urllib2.urlopen( url % defaultdict(str,url_params) )
        doc = minidom.parseString( url_p.read() )
        url_p.close()
        return doc

N.B., you can create a specific User-Agent with urllib2 if so desired, and defaultdict is used so we don’t have to check if the incoming dict (url_params) has everything we need for the url string.

Now we can start writing some tests

class TestUserNoun:
    ...
    def test_user_count(self):
        # Test several values of max_count
        counts = (5,10,15,20)
        def count_users(n):
            # Test that the number of results returned is less than or equal to n
            doc = self.get_xml_doc({'max_count':n})
            user_count = len( xpath.Evaluate('/xpath/expr',doc.documentElement) )
            assert user_count <= n
        for c in counts:
            yield count_users,c
    def test_order_by_date(self):
        # See that each item is older than the previous one
        doc = self.get_xml_doc({'max_count':10,'order_by':"date"})
        items = xpath.Evaluate('/xpath/expr',doc.documentElement)
        # Get the date of the first item
        last_date = xpath.Evaluate('@date_attr',items[0])
        # Compare the date of each item to the previous one
        for item,i in zip(items[1:],range(len(items[1:]))):
            item_date = xpath.Evaluate('@date_attr',item)
            assert item_date <= last_date
            last_date = item_date

And you get the idea – one can write tests ad nauseum (although I’m not sure if there’s such a thing as too many tests). Of course neither of these tests will work since the XPath expressions are not valid – I didn’t really feel like spelling out a whole XML schema just for this example. There are plenty of good XPath tutorials out there. The basic idea here is you want to test all of your request parameters for the API to see a number of things:

• Does the controller handle the requests properly? What about missing/extra parameters?
• Are errors handled properly?
• Is the resulting XML valid? This is implicitly done by parsing the XML document
• Does the resulting data correspond to the request parameters? This one will require the most tests to be written – don’t forget about generative tests!

A powerful test suite means a robust application. When you have a nice set of tests, you can push your code with confidence – and believe me, that is a very rewarding and relieving feeling. Writing this API has been an extremely rewarding experience, and probably the most educational thing I’ve done programming-wise since I wrote a cross-browser javascript event library like 5 years ago.

So go forth, programmer – embrace testing and empower yourself.

-David

A friend and I have been bouncing around the idea of a caching system that ran on Amazon’s cloud for a while now. Basically something like memcached, but without the (very real) limitations of physical memory or the need of a whole server. Sure, it’s hard to beat the speed of memory-level read access, but I think the appeal of a distributed, limitless cache might outweigh the slowdown.

Idea

Provide an interface for storing/retrieving serialized data on S3

Pretty simple idea, pretty simple implementation. Thanks to the S3 interface provided by Boto, things were a lot easier. I’m going to keep this open source under the MIT license. You can check out the code on GitHub repository – please feel free to fork, improve, submit, etc.

Overview

A quick walkthrough of the code will reveal truly how simple this is. The Client class provides basic CRUD methods for interfacing with S3: put, get, update, delete. The put and update methods store a timestamp as the “expires” header for the file to keep track of cache expiration. Also these two methods write a “type” header to the meta-data so CloudCached knows how to de-serialize the file.

class Client:
"Here's the class schema"
    def get(self, key)
    def put(self, key, value, time_to_expire=3600, replace=False)
    def update(self, key, value, time_to_expire=3600)
    def delete(self, key)

There are 6 basic data types used in this code for serializing any bit of python data: basestring (for str and unicode), int (for int and long), complex, float, and other. The other data type represents anything that is not a base type in Python. These “other” types get pickled while everything else just gets str’d.

The put method checks the md5sum to make sure everything went through cleanly (maybe a bit costly, but worth it in my opinion). cPickle is used in favor of pickle for obvious reasons (it’s much faster).

Results

Some very early tests show that this might just be usable.

    CloudCached Benchmarks (10 runs)
    --------------------------------------------------------
    Test                 |  Average (s)     | Total (s)

    --------------------------------------------------------
    GET integer          |  0.0283360004425 | 0.283360004425
    GET string (32 byte) |  0.0315794944763 | 0.315794944763
    GET string (512KB)   |  0.1265994787220 | 1.265994787220
    PUT integer          |  0.0650457143784 | 0.650457143784
    PUT string (32 byte) |  0.0563205003738 | 0.563205003738
    PUT string (512KB)   |  0.1773290872570 | 1.773290872570
    --------------------------------------------------------

Advantages

• Highly distributed. S3 data is distributed across multiple availability zones and could therefor be utilized by an application running across multiple availability zones.
• No size limit. Unlike the physical limitations of a memcached machine (or cluster of memcached machines), S3 does not have limits on the number of files (caches) you can store. Also, with S3, you can write files from 1 byte to 5 GB (although I think a 5GB cache file would defeat the purpose).
• Parallel read access. If applicable to the application, cache reads can be largely parallelized which could potentially give linear speedup to the cache loading.
• No server necessary. Since the application is reading and writing directly to S3, there is no need to a “cache server”. This could lead to a great deal of savings for people running multiple memcached machines. Memcached servers typically have a large memory capacity which means a m1.xlarge or c1.xlarge EC2 instance (assuming it’s running in EC2).

Considerations

It’s going to be hard to beat the speed of memcached. As far as speed is concerned, I’m using built-in Python stuff including urllib, httplib, xml.sax, etc (all of which are used by Boto). It might be worthwhile to write a C implementation of the S3 communication methods (but maybe not). The most costly part of this code aside from network communication is probably the serialization, and since cPickle is used there is not really improvement to be made there.

It might be cool to couple the meta-data with SimpleDB.

I registered cloudcached.com in case this gains some momentum. I will post updates and benchmarks there as they arrive.

-David

Dis·qui·si·tion, n. – A formal discourse on a subject, often in writing.

Started seriously getting the ball rolling on my thesis this week, outlines and everything. I found a really great app for writing called Scrivener (non free, OS X only). Notice that I said writing, not publishing. For my purposes, it does rather poorly as a publishing platform, but I have that end of things worked out rather well ( represent!). 1000 words in the first day. Granted, they are the easy words (background and lit review), but hopefully I can keep up a moderate pace so I can defend this summer. Once I start finishing sections and moving my draft into LaTeX, I’ll start publishing them somewhere here. Probably not in this blog, but maybe a directory for a Latex2HTML dump.

In other news, we got a Nikon d80. All the recent pics in my Flickr stream are taken with it (minimal post-processing).

It’s nice to be writing again.

There’s a weird thing that happens after a long night of mind-blowing back-breaking coding. Well, hacking in this case. Every time I stay up late working really hard on something, I feel compelled to blog/tweet/emote about my experience so others might feel sympathy/compassion for me. Even though I’m dizzyingly tired, and have to get up in ~5 hours, I cannot deny this urge to massage my ego.

So tonight I bring to you the joy of unit testing in Python. I’ve been using py.test, and loving it. It extends the basic functionality of Python’s built-in module, unittest (which is really not that bad). The main improvements are in the simplicity of writing the tests. Py.test supports unit testing on methods, classes, even whole modules.

Here’s your first test

def test_iszero():
    assert 1==0

If you haven’t guessed, this test will fail (1 does not equal 0). A cool thing about py.test is that you just prefix the method name with “test_” and that becomes a test. If it’s in a class or module, you need setup and teardown methods, but beyond that just write methods starting with “test_”. There’s lots more fancy stuff you can do, I suggest checking out the docs (link above).

However, by my favorite thing py.test does is support generative testing. By using generators, a test can spawn “sub” tests with a yield statement. Let’s say I want to test if a bunch of numbers are even.

def isEven(x):
    assert x%2==0
def test_evenNumbers():
    n = [1,2,3,4,5,6]
    for x in n:
        yield isEven,x

This can be tremendously helpful when you need to do a repetitive test on many input parameters. Enjoy! -David

After getting yelled at for not grading my student’s homework, I decided to ignore the threatening emails and continue doing what I feel like. Undergrads, know this: TAs don’t really care about you – sorry. I was debugging some code built on top of my awesome HTMLParser, and kept having a really frustrating problem. Some of my class variables were not getting reset during the init call. So I poke around and after a while discover (buried in my libraries)

class Foo:
    a = True
    b = []
    c = []
    def init(self):
        ""

It seems the class members a, b, and c are not getting reset when I instanciate becasue, quite simply, I am not resetting them in init. I originally put them there for prettiness (self.a, self.b, self.c is so cumbersome), and moving them back into init fixed my problem.

A little more digging reveals what is going on here. If you define a variable outside of a class method, the variable is implicitly made static.

class Foo:
    a = "Hello"
print Foo.a
>> Hello

These static members are accessed just like regular members, with the “self” object. For things like str, int, float, the value will seem to be reset when you create a new instance of the class. But what’s really happening is when you alter the static variable, you are actually creating a new class variable (in memory) which overrides the static for the duration of that object. This is not true for lists and dicts. I assume this is because Python uses pointers for array-like structures and the static member is just a pointer here. So when you alter the static list (via getitem, append, remove, et al.) you are operating on the pointer, not a copy of the list.

class Foo:
    a = []
    def init(self):
        print self.a
        self.a.append(1)
f = Foo()
f = Foo()
f = Foo()
>> []
>> [1]
>> [1,1]

Depending on how you’re structuring your code (or how good at Python you are) you might want this functionality. For me though, this was not the case, so I put everything back in init. Another good thing to point out is Python has a very convienent syntax for making a copy of an array.

    a = [1,2,3,4]
    b = a
    c = a[:]
    b[0] = 5
    c[0] = 6
    print a
    print b
    print c
    >> [5,2,3,4]
    >> [5,2,3,4]
    >> [6,2,3,4]

Sometimes I miss pointers, but not really. -David

In recent efforts to create a general purpose HTML scraper for mein Geschäftsführer, I’ve been getting my hands dirty in some Py. After much research and experimentation, I’ve decided to go with the built-in HTMLParser instead of the XML expat parser or the SGMLParser. Also, I should clarify this is not the HTMLParser from htmllib, this is HTMLParser’s HTMLParser. For all it’s wonderment, Python really fails on consistant naming schemes. Oh well.

One of the things I like most about HTMLParser is that it is not a module per say, but it is a factory for creating a wrapper. There is no default HTMLParser which you can feed HTML to and get output – you only get the factories for parsing.

class MyParser(HTMLParser):
    def handle_starttag(self,tag,attrs):
        if tag == "a":
        print "Found link:",attrs
    def handle_startendtag(self,tag,attrs):
        if tag == "img":
        print "Found image:",attrs
parser = MyParser()
parser.feed(rawhtml)

Lovely, no? There are a few more methods which you overwrite in order to achieve desired functionality. The nice thing about parsing HTML like this is that it is a one-pass operation. Unlike a series of regexp to find desired content, this allows us find multiple targets in a streaming fashion.

There was one really annoying thing about this module however. The built-in getpos() returns a tuple of line number and column position. I can’t think of an instance when this would be useful for anything really (unless you’re making a HTML editor in python or something), so natrually I modified it to my liking. My first solution was to just remove all the newlines and then work based on the column offset alone. Unfortunately, HTMLParser chokes on some really long lines. My next idea (the one I’m currently using) was to strip out tabs and trailing whitespace and precalculate the length of each line before I feed the parser.

linepos = []
charpos = 0
for line in self.html.split("\n"):
    self.linepos.append(charpos)
    charpos += len(line)
parser = MyParser(linepos=linepos)

This produces an array like [0,10,20,30,...] (if each line were 10 characters long). The next modification is to create a new method for MyParser.

def getcharpos(self):
    return self.linepos[self.lineno-1] + self.offset

The two properties lineno and offset are inherited from HTMLParser (actually inherited from markupbase), and they represent exactly what you’d think.

Now that I have absolute position of tags in the HTML, I can all kinds of fun things like use K-means grouping to find clusters of images. Or maybe I want to see the average distance between occuraces of the word “the” in an article. It’s 276.21 for this one, btw.

-David

As promised, I bring pretty pictures. The past few days I’ve been working on a solution to the 1d diffusion equation with a drift term, better known as the Fokker-Planck equation.

Sexy, I know. Anyhow, I finally worked out the Python code to get it rolling (literally!). The test system I did has periodic boundary conditions and an initial condition of a sharply-peaked Gaussian (a = 20). I’ll spare the details and jump to the fun part.

Here’s the Python code that made it happen (scipy and matplotlib required).

-David

In lieu of my typical witty banter I’m just going to post some code. Way too tired to put any effort forth.

Tried for days to get Access to export my ADO Recordset as something, anything. I tired:

• Loading it into a table – nope
• Making a temporary table on the database server and linking to it – nope
• Tried using getRows and manually creating a CSV – nope
• Conjured up the ancient spirits of BASIC – nope

I mean really. And the internet was of course no help. Turns out there’s a few built-ins that do the trick – go figure.

Problem: Need to export the data… why oh, why can’t I export the data

XML Solution:

Dim ADOrs As ADODB.Recordset
Set ADOrs = Me.RecordsetClone
ADOrs.Save "export.xml", adPersistXML
ADOrs.Close

Shoot me in the face that was easy.

CSV Solution:

Dim ADOrs As ADODB.Recordset
Set ADOrs = Me.RecordsetClone
Dim csv As String
csv = ADOrs.GetString(, , """,""", """" _
    & vbCrLf & """", "")
csv = Left$(csv , Len(csv) - 1)
Dim h As String ' Header row
For X = 1 To ADOrs.fields.Count - 1
  h = h & """" & ADOrs.fields(X).Name & """"
  If X < ADOrs.fields.Count - 1 Then
    h = h & ","
  End If
Next X
Open "export.csv" For Output As #1
Print #1, h
Print #1, """", csv
Close 1

Edit: An interesting note about the ADO Recordset XML export. It uses a special namespace (actually a few). It’s readable enough, and just as easily parse-able as any other XML document. A nice feature about this XML spec is that you can load it back into Access as an ADO recordset – so in theory this could be used for long-term caching of large chunks of data.

Just a quick blurb. I had a problem with CodeIgniter regenerating the session id all willy-nilly.

Here’s a snip from the config.

$config['sess_cookie_name'] = 'ci_session';
$config['sess_expiration'] = 54000;
$config['sess_encrypt_cookie'] = TRUE;
$config['sess_use_database'] = TRUE;
$config['sess_table_name'] = 'sessions';
$config['sess_match_ip'] = TRUE;
$config['sess_match_useragent']  = TRUE;
$config['sess_time_to_update'] = 300;

Turns out, CodeIgniter will regenerate the session id every time it updates the session table in the database. So, by default the session id gets regenerated every 5 mins (300 seconds). Instead of changing the sess_time_to_update value, I dug around in the code for a bit.

Here’s the culprit. (In basedir/system/libraries/Session.php)

$old_sessid = $this->userdata['session_id'];
$new_sessid = "";
while (strlen($new_sessid) < 32)
    $new_sessid .= mt_rand(0,mt_getrandmax());
$new_sessid = md5(uniqid($new_sessid,True));

Talk about entropy…

Quick hack: comment out these lines and set $new_sessid = $this->userdata['session_id'];

-David