FITIn Internally

As FITIn is written on top of Valgrind, the tool works exclusively on the internal representation of Valgrind, called VEX IR. VEX IR is a static single assignment language, allowing assignments to variables only once. The language completely abstracts the originating assembler code and prevents the developer from looking behind it. We now explain how FITIn treats VEX IR of incoming SBs. As example, we use the expression state &= OVERLOAD; We first show its transition from source code to AMD64-assembly and to VEX IR. Then, we discuss the instrumentation of FITIn for this line in the context of our first experiment.

Our first task is to locate the SB that holds the translated expression. We start by consulting Valgrind about the actual SB segmentation. Using --trace-flags=10000000, Valgrind outputs every new SB. For the first experiment, on our test platform, there is a total of 1480 SBs. Since we are interested in SBs of main, we scan the output for main and find the following SBs:

However, as SBs result from code branches, method and system calls, this output tells us only the IDs of the SBs that might be interesting for us. More effort is required to find specific code in any of the SBs.

A little research in the assembly generated by the compiler revealed that our expression state &= OVERLOAD; has been translated to AND EAX, -2 (AMD64). This instruction is unique in this scope and thus straightforward to find. Adding --trace-notbelow=1322 and --trace-notabove=1330 filters out further SBs; in the end, the expression of interest turns out to be located inside SB 1328. After the first cleanup by Valgrind, we arrive at the code in Fig. 2 where lines 1-30 (extracted from --trace-flags=01000000) list the complete representation of state &= OVERLOAD by the VEX IR.

When in doubt about the representation of a certain instruction, one can always consult the associated IMark statement, a VEX statement without counterpart in the code, which serves the purpose to display address and length of the original instruction.

The assigned t{n}-values are of type IRTemp. The lines 2-6 will load the value from the memory, t13 references the value of the stack-frame base pointer RBP. On AMD64, Valgrind does not always strip away neutralizing cast operations, as they can be seen in lines 11-18. Line 19 represents the bitwise operation of clearing the least significant bit. After more casts and reassignments, line 23 will put the result of this operation into the shadow register table of Valgrind, a distinct memory area to represent data transfers via CPU registers. On AMD64, PUT(16) means: Originally, the result was stored in register RAX. In lines 27-29, the result is read from the shadow register table and finally stored at its original memory address.

Starting from line 31 of Fig. 2, we list the result of the instrumentation process of FITIn (as seen by --trace-flags=00100000). The following modifications take place:

  1. In line 34, FITIn adds a call to preLoadHelper just before loading from the address in t12. It is a DIRTY helper function, since it calls a procedure outside of VEX IR, possibly causing side effects. preLoadHelper will, at runtime, look for monitoring requests for this address. The returned t64 is a pointer to load state information of t16, used later.
  2. In the unmodified VEX IR (Fig. 2, left), the first use-after-load of t16 in line 6 is the cast operation t48 = 8Uto32(t16) in line 11. This is relevant for FITIn: Before casting, FITIn inserts the lines 36 and 37. The cast in line 36 is necessary to satisfy the VEX IR specification for passing t16 (a char) as argument to the helper function fi_reg_flip_or_leave, which expects arguments of platform address size. The function itself, another DIRTY, forms the heart of FITIn: If t16 has previously, in line 34, been marked as relevant, FITIn will increase the access counter. If the counter hits the user’s specification, FITIn will perform the bit flip here and return the modified value, t66. Otherwise, no modification will be applied.
  3. In the lines 42, 52, and 57, FITIn inserts another DIRTY called incrInst, which increases the instruction counter and terminates the program prematurely if the user demands so.
  4. In line 47, the corresponding statement IR-NoOp from line 20 is omitted, leaving proper re-insertions of NOP-commands up to the compiler of Valgrind.