Mutation testing, reinventing the wheel, and python bytecode

Sun, 18 Jun 2006 19:18:54 +0000
tech article python

So I recently stumbled across Jester, which is a mutation testing tool.Mutation testing is really a way of testing your tests. The basic idea is:

  1. Ensure your tests work on the code under test.
  2. Generate a set of mutant pieces of code, which are copies of the original code with some small changes, or mutations.
  3. For each mutant, run you test cases. If one of these tests doesn't fail then you are missing test case.

So in testing your code you should first aim for complete coverage, that is ensure that your test cases exercise each line of code. Once you get here, then mutation testing can help you find other holes in your test cases.

So the interesting thing here is what mutation operations (or mutagens), you should do on the original code. Jester provides only some very simple mutations, (at least according to this paper):

Unfortunately it seems that such an approach is, well, way too simplistic, at least according Jeff Offutt, who has published papers in the area. Basically, any rudimentary testing finds these changes, and doesn't really find the holes in your test suite.

A paper on Mothra, a mutation system for FORTRAN, describes a large number of different mutation operations. (As a coincident, my friend has a bug tracking system called Mothra.)

Anyway, so while Jester has a python port, I didn't quite like its approach (especially since I needed to install Java, which I didn't really feel like doing). So I decided to explore how this could be done in Python.

So the first set of mutation I wanted to play with is changing some constants to different values. E.g: change 3 to (1 or 2). So this turns out to be reasonably easy to do in python. I took functions as the unit of test I wanted to play with. So, Python makes it easy to introspect function. You can get a list of conants on a function like so: function.func_code.co_consts. Now, you can't actually modify this, but what you can do is make a new copy of the method with a different set of constants. This is conveniant because in mutation testing we want to create mutants. So:

def f_new_consts(f, newconsts):
    """Return a copy of function f, but change its constants to newconsts."""
    co = f.func_code
    codeobj = type(co)(co.co_argcount, co.co_nlocals, co.co_stacksize,
                       co.co_flags, co.co_code, tuple(newconsts), co.co_names,
                       co.co_varnames, co.co_filename, co.co_name,
                       co.co_firstlineno, co.co_lnotab, co.co_freevars,
    new_function =  type(f)(codeobj, f.func_globals, f.func_name, f.func_defaults,
    return new_function

So that is the basic mechanism I'm using for creating mutant function with different constants. The other mutants I wanted to make where those where I change comparison operators. E.g: changing < to <= or >. This is a bit trickier, it means getting down and dirty with the python byte code, or at least this is my preferred approach. I guess you could also do syntactic changes and recompile. Anyway, you can get a string representation of a function's bytecode like so: function.func_code.co_code. To do something useful with this you really want convert it to a list of integers, which is easy as so: [ord(x) for x in function.func_code.co_code].

So far, so good, what you need to be able to do next is iterate through the different bytecode, this is a little tricky as they can be either 1 or 3 bytes long. A loop like so:

    from opcode import opname, HAVE_ARGUMENT
    i = 0
    opcodes = [ord(x) for x in co.co_code]
    while i < len(opcodes):
	print opname[opcode]

        i += 1
        if opcode >= HAVE_ARGUMENT:
           i+= 2

will iterate through the opcodes and printing each one. Basically all bytecodes larger than the constant HAVE_ARGUMENT, are three bytes long.

From here it is possible to find all the COMPARE_OP byte codes. The first argument byte specifies the type of compare operations, these can be decoded using the opcode.cmp_op tuple.

So, at this point I have some basic proof-of-concept code for creating some very simple mutants. The next step is to try and integrate this with my unit testing and coverage testing framework, and then my code will never have bugs in it again!

On robust scripts

Thu, 08 Jun 2006 11:01:54 +0000
tech code python

When you write scripts that run as cron jobs, and send email to people, and have the potential to send a *lot* of email to people you really don't want to screw up.

Unfortunately I did screw up when writing one of these. It was a pretty simple 200 lines or so python script that would find any new revisions that had been commited since the last time it ran, and email commit messages to developers.

The idea was simple, a file kept a list of the last seen revisions, I would go through the archive find new revisions, mail them out, and then finally write out the file with the latest files.

Spot the bug, or at least the design error? When our server ran out of disk space, the stage of writing out the the file with the last seen revisions failed, and created an empty file. So next time the script ran it thought all the revisions were new, resulting in thousands of email about revisions committed years ago. I pity our poor sysadmin who not only had to deal with out of disk problems but now also with a mail queue with thousands of messages.

Solution to the problem of course is try and write out the new revision file before sending the email, and write it to a temporary file, instead of blasting the last known good out of existance by writing directly over the top of it.

I guess the moral is designing these little scripts actually requires more care than I usually give them.

Sun, 12 Mar 2006 09:50:24 +0000
tech maps python code

Today I release the first version of nswgeo. It is a simple python script that queries the NSW Department of Lands GeoSpatialPortal to find the location of addresses in NSW.

Functional code in python (or yet another abuse of python)

Thu, 09 Feb 2006 10:54:18 +0000
tech python article

So I was inspired (distracted) by the python functional programming module, and got to thinking couldn't things like partial application and function composition be a bit more natural in the syntax.

So it turns out that with decorators and a bit of evil introspection I came up with something that works (at least for functions that don't have keyword arguments). So you can do something like:

def add(a, b): return a + b

add3 = add.add

assert(add3(1)(2)(3) == add3(1, 2, 3) == add3(1, 2)(3) == add3(1)(2, 3) == 6)

So what is the magic (or evilness)? Well first we (ab)use decorators to decorate things as Functional, which is you probably know, is just a shortcut for function = Functional(function).

The evil is in the Functional class:

class Functional:
    def __init__(self, fn, nargs = None):
        self.fn = fn
        if not nargs:
            _args, _, _, _ = inspect.getargspec(self.fn)
            self.nargs = len(_args)
            self.nargs = nargs

    def __call__(self, *args, **kargs):
        if len(args) > self.nargs:
            res = self.fn(*args[:self.nargs], **kargs)
            if res.__class__ == Functional:
                return res(*args[self.nargs:])
            if type(res) != type((0,)):
                res = (res, )
            return res + args[self.nargs:]

        elif len(args) == self.nargs:
            return self.fn(*args, **kargs)
            def newfunc(*fargs, **fkeyw):
                return self.fn(*(args + fargs))
            newfunc.func = self.fn
            newfunc.args = args
            return Functional(newfunc, self.nargs - len(args))

    def __getattr__(self, name):
        if hasattr(self.fn, name):
            return getattr(self.fn, name)
        func_1 = self.fn
        func_2 = globals()[name]
        def composition(*args, **kwargs):
            res = func_2(*args, **kwargs)
            if type(res) != type((0,)):
                res = (res, )
            return self(*res)
        return Functional(composition, func_2.nargs)

I totally abuse the __getattr__ method so that dot becomes a composition operator. This returns a new function (which is also Functional), which when called will pass on the return value from the first function to the second function. If the first function returns multiple results each of these is passed as arguments to the second function.

The real magic comes in the overload __call__, which is where partial functions are hacked in. Basically if not enough arguments are passed to the function is returns a new function that accumulates the arguments already passed and once it gets enough calls the original function. Of course the function returned from partial application is itself. The real evil is in supporting the case add3(1, 2, 3) which means we detect if too many arguments are passed and then call with only the first arguments, then if the called function returns another functional we apply the remaining arguments to it.

Oh yeah, I wouldn't use this in any real python code, as it is likely to confuse everyone!

More code uploaded..

Thu, 09 Feb 2006 09:32:16 +0000
pexif tech python

Ok, pexif 0.4 is out (even after saying th other day that I wouldn't do any more releases for a while!), and I've updated the pyannodex 0.7.3 tarball to include a missing header file. (I didn't really think that deserved a version bump!).

pyannodex 0.7.3 release

Tue, 07 Feb 2006 22:22:32 +0000
tech annodex python pyannodex

I've released 0.7.3 of the pyannodex bindings. This fixes some bugs, importantly includes the script which is kind of essential for installing it. It also includes tool.

Another day.. another pexif release

Mon, 06 Feb 2006 22:50:18 +0000
tech python pexif

pexif hits 0.3. Ok, there is now an easy way to get and set GPS coordinates on a photo, which was really my aim in writing this library in the first place. There is also a and script to do it on the command line.

I don't plan on doing any more major stuff to this library in the near future unless someone other than me is actually using it, so more than likely this will be the final pexif release. Itch scratched.

pexif 0.2 released

Sun, 05 Feb 2006 22:06:35 +0000
tech pexif python
I just released pexif 0.2 which handles JFIF files as well as just EXIF and has a slightly saner interface as well as an actual test suite, and documentation. Still probably not useful for general audience, but if any one is keen take a look.

pexif 0.1 release

Fri, 27 Jan 2006 18:46:27 +0000
tech pexif python

Short version: I release some code. It edits EXIF data.

Long version: All I wanted to do was write some simple code to add a GPS location take to my photos. It should have been easy. A couple of hours of scripting at the most. But it wasn't.

Most JPEG images have some meta data at the front of them telling you stuff like, when it was taken, what camera took it, wether the flash was used, and so on, and so on. The latest version of the spec also has a bunch of fields for storing GPS information. Unfortunately my cheapo camera doesn't store that kind of information, so I want to add it in after the fact. I thought I could just grab an existing EXIF editing library and away I would go.

Unfortunately the two Python libraries out there pyexif and, only handle the parsing of EXIF data, not the updating of it. The also seemed to be a C library libexif that claimed to do editing, but it was basically undocumented, I couldn't work out how to use it, and besides I wanted to write in python not C. (And I didn't feel like writing a Python wrapper for a library I didn't uderstand.)

This led me to writing some of my own Python code to try and just do enough to insert the GPS tags and nothing else. Unfortunately the way EXIF works things aren't quite that easy. Inside the file format you end up with internal offset pointers, which means if you change the layout (by inserting some extra tags), you end up needing to change all these pointers to work with the new offsets.

I thought this wouldn't be too bad because I'd just append to the end of the section I was working with, (which was unfortuantely first), and then the other sections could move freely. Unfortuantely these pointers don't reference from the start of a section, they reference from the start of the file. This basically means that I need to parse everything into memory, and then know how to write it all back out again. Pain, pain, pain. (This was of course a bit of a simplication, so please don't email me saying that isn't exactly how EXIF is structured.)

Anyway, I now have a library, which can read all the EXIF data, including the thumbnail section, edit and insert values into it, and then spit out a valid file again. Now I can start writing the code to do the actual tagging, which should be more interesting than this stuff, but right now, time for the LCA dinner.