Jul 13 2011

A large part of my current project involves tracing program execution through memory. While there are a few methods of obtaining this data, the most straightforward is with the Valgrind toolkit. Valgrind

1. loads an arbitrary executable
2. translates it into an internal IR called VEX
3. lets you manipulate the code in converted form
4. compiles that code back to x86
5. runs the result

If you do any kind of online program analysis, this kind of framework makes your life much easier. Given the large scope of Valgrind’s operation (live translation of running code is no easy task), I expected the source to reflect the complexity of the problem. Fortunately, Valgrind’s Lackey example tool provides an easy starting point and Valgrind overall seems to succeed at providing a simple but flexible interface.

The first place to start is VEX itself. Viewing libvex.h and libvex_ir.h in the valgrind/VEX/pub/ directory should give you a basic idea of how VEX is structured. Since Valgrind was originally built to support Memcheck, VEX is especially geared toward tracking memory operations; loads and stores have extra emphasis.

VEX code consists of “superblocks,” sections of code with single entry and multiple exits. This corresponds to a glued-together set of basic blocks a compiler might work with. Since my trace requires true basic blocks, I treat an entry-exit pair as a unique basic block.

A Valgrind tool receives each set of superblocks in IR format, behind the scenes Valgrind takes care of decompilation and compilation. All your tool sees is a stream of VEX IR. For speed, the Valgrind JIT compiler caches and inlines sets of superblocks as they are run; if you need thus functionality turned off you can enable --vex-guest-chase-thresh=0. This supposedly turns off the multiple-exit feature of superblocks and makes them true basic blocks, but I have yet to test this in actuality.

The fact that both instrumentation code and instrumented code run simultaneously opens up a host of online analyses previously untenable with compile-time transformations. The closest modern analog would be LLVM passes; I plan to look into these for more performant tests but the compile-time restriction certainly puts it behind in flexibility.