floating point

I’ve found that 99% of the time, when somebody asks a detailed technical question, the right first answer is “What are you really trying to do?” It’s often frustrating for the person who hears it; they think they understand their problem very well and that they’ve reduced it to a single technical point, but in reality approaching the issue from a completely different direction is the way to go. I ran into this with myself this morning when working on my thesis project, amock.

amock starts with a dynamic analysis of a Java program; it is implemented (for simplicity) as an offline analysis. The program is run in a special instrumented mode which dumps out a trace of every method called to a file, which is later processed by the actual analysis algorithm. In the trace generated by my instrumentation, every non-primitive object is assigned a unique integer ID, so that the processor can tell which object is which. It does this by using a weak identity hash map: a chimera of the standard Java classes WeakHashMap and IdentityHashMap.

The problem is, this doesn’t work for creating trace entries about constructors. When you’re calling a constructor, the semi-initialized object is this weird weird thing that you basically can’t examine at all… trying to do basically anything to it other than call ‘dup’ or call a constructor on it makes the verifier cry. Thus my instrumentation has to go to extra efforts to substitute a dummy ConstructorReceiver object into the calls to my tracer implementation, because you can’t actually pass a semi-initialized object to methods. This means that my trace entries for entering-constructor all have no idea which object they’re constructing, and there’s no good way to tell from the trace if two different entering-constructor entries refer to the same object (calling superclass constructors on it, say) or not. (The exiting-constructor entries do have an identity for the object, though, because the object is initialized by then).

So this morning I spent about an hour poring over the JVM spec and trying to come up with complicated instrumentations that would extract some information from this annoying uninitialized object. I had several different plans; for example, I started trying to work out how to instrument every single constructor in the system to add an extra object-id argument. I went to one of my labmates and tried to get advice on how to instrument the Java bytecode in order to somehow get this to work.

“What are you really trying to do?” he asked.

So I started explaining from the beginning. And suddenly it hit me: I didn’t need a fancier instrumentation. All I needed to do was write a braindead two-pass algorithm that reads in a trace file, matches entering-constructor and exiting-constructor entries, and spits out a trace with the additional information in it. It took me ten minutes and worked the first time.

It’s horribly hacky. The newest file is full of TODO comments and special cases. (The rest of the infrastructure is slightly less so.)

But!

amock can run a system test and automatically generate a passing unit test from it!

(The key word here is a system test: the one it is tested on. But still!)

I wrote three papers at the end of last semester. The first was the proposal for my master’s thesis. My project is inspired by David Saff’s test factoring project. It can be relatively easy to write a few top-level system tests for an application, whereas it can be slow and tedious to write a complete suite of unit tests which exercise the entire program. The concept behind test factoring is that by dynamically observing the execution of a system test, we can automatically generate a large number of unit tests which drive individual objects in the same way that the entire test suite did.

The main focus of David Saff’s project was efficiency: a very slow system test can be run much quicker if the code in only a small number of classes is executed, and the rest of the world is replaced by “mocks”. His project executed the program in a specialized runtime environment which read from a transcript of the system test and simulated method calls which reached outside of the tested classes by just returning whatever they did during the system test.

That project is quite interesting. However, my focus in test generation is less on efficiency of running tests and more in ease of creating and modifying tests. Often, you may find yourself needing to change a test you wrote to be more lenient: to allow a return value to take on more values, or to allow two events to occur in a different order, for example. The ability to do this is even more important for automatically generated tests, which never had the benefit of a human writer and may be very brittle. So, my project (which I am calling @amock@) has the same general idea as test factoring, but its output is standard Java code. The generated tests must be legible and comprehensible by developers; developers much be able to relax and otherwise tweak the generated tests. In order to implement “mocking out the world”, I am using jMock, a Java mock-object library. (Yes, I do realize that the mock objects folks prefer to think of mock objects as a design aide and not a post facto testing tool; perhaps this will lead to the generated tests not being very good for most programs. We will see.)

My goal is to implement @amock@, write my thesis, take two classes, and TA another one this semester; I’ll move to San Francisco and start my new job after that. Since this is a pretty heavy load, there’s a reasonable chance it’ll take me the summer to finish up the thesis and I’ll have to wait on the job; let’s hope that doesn’t happen.

My other two papers were group projects for my classes last term. I’d describe them both as interesting projects which didn’t pan out as conclusively as we’d hoped; however, I’m still pretty happy with both of them. For my databases class, I looked into the best database structures for implementing oh-so-trendy-Web-2.0 tagging queries, working with Richard Tibbetts and Chris Laas. For advanced algorithms, Natan Cliffer and I explored what we called packing dual problems of machine scheduling problems: problems that generalize the NP-complete bin packing problem in the same way that machine scheduling problems are generalized. I think our classification is an interesting idea, but unfortunately we didn’t prove any non-trivial results about specific subproblems.