Dynamic tainting
DECAF provides sound dynamic tainting at the finest precision that is the bit level. Technically, DECAF has two tainting components. The first component propagates the tainting status of different variables alongside the execution. The second component complements the first level tainting by reconstructing the labels and the execution trace. It aims to construct the whole system information flow offline. Thereby, it asynchronously logs the translation block and cpu states in a different process on the disk space. The second level is part of the instruction tracer plugin and we do not discuss it in detail here. The first level, however, is the focus of the discussion in this section.
The first level dynamic tainting happens during the execution time by propagating the taint status of a variable based on the execution time operations. To implement the dynamic tainting, we should have a shadow variable for each variable and track the taint status of each bit of the original variables in the shadow variable. DECAF propagates the taint status dynamically by adding additional instructions before each instruction. The instructions are added before the original instructions because some operations affect a source variable, and after the instruction execution, the value of a variable is lost. Figure 13 shows how additional instructions are added to a binary for dynamic taint analysis.
Note that the number of instructions inserted for tainting before an instruction is different. While some instructions such as load and store (MOV in x86) can be easily tracked by a single load and store instruction on the shadow memory, some instructions like AND need more efforts for sound1 and precise2 tainting. Henderson et al use SAT solvers to find the best instructions to achieve this level of taint propagation soundness and precision for DECAF2; this is why for an AND we may have 9 instructions per an instruction (see Figure 13).
Figure 13. Dynamic tainting
Taint status of the variables is kept in TCGv shadow_arg. Taint analysis happens for three types of variables:
- The CPU registers are tracked using global variables
- The global variables are tracked using global variables
- The temporary variables are tracked by on-the-fly allocation for these variables
These variables in TCG are allocated and stored in a global TCGContext structure called tcg_ctx. For every TCG opcode, kept in gen_opc_ptr, the operands (or the arguments) are retrieved through their indexes kept in a stack referred by the gen_opparam_ptr array. These indexes in fact point to the element in the static_temps array within tcg_ctx that contain the value of the operand. The same indexes used to access a variable is used to access its taint status in TCGv shadow_arg.
The taint status of variables changes while execution. To track such changes, we have to propagate the taint status by injecting taint tracking instructions to a binary (see Figure 13). We do this by rewriting a block. After creating a TCG block (translating a binary to the tcg intermediate code), we read the instructions one by one from the tcg block and add the taint propagation instructions before them.
Adding the taint propagation instructions happens in the gen_taintcheck_insn function. The trace to this function starts from the gen_intermediate_code_internal function that performs the TCG translation. In this function, there is a call to optimize_taint that leads to calling gen_taintcheck_insn that does the tainting. Figure 14 shows the trace.
Figure 14. Taint instruction insertion
gen_taintcheck_insn reads the instructions for the new block one by one and then inserts the required taint propagation instructions before them. The taint propagation instructions change the taint status of the variables kept in TCGv shadow_arg. For insertion, DECAF first pops the tcg instructions and after inserting the taint propagation instructions, it pushes them back again. The implementation for INDEX_op_mov_i32 TCG instruction is shown below.
case INDEX_op_mov_i32: // Always bit taint
arg0 = find_shadow_arg(gen_opparam_ptr[-2]);
arg1 = find_shadow_arg(gen_opparam_ptr[-1]);
if (arg0) {
/* Store opcode parms */
orig0 = gen_opparam_ptr[-2];
orig1 = gen_opparam_ptr[-1];
/* Rewind the instruction stream */
gen_opparam_ptr -= 2;
gen_opc_ptr--;
/* Insert taint propagation */
tcg_gen_mov_i32(arg0, arg1);
/* Reinsert original opcode */
tcg_gen_mov_i32(orig0, orig1);
}
break;
Later in code, an optimization to remove unnecessary instructions is done in the tcg_liveness_analysis function.
In the previous subsection, we assume that the taint status of the corresponding memory is correctly loaded in its associated taint status container; only then the taint propagation logic would work. In this subsection, we explain how correctly the taint status of a memory address is loaded in its taint status container.
In Qemu memory management and Page fault handling section we explained how QEMU maps the guest virtual addresses to the host address space before every instruction. DECAF patches the memory management functionality of QEMU and adds another procedure that also loads or stores the corresponding taint status of memory address to the temporary variable tempidx of the CPU environment (CPUState). Right after the address mapping, DECAF loads the taint status of the memory address to the taint status container of the corresponding memory. DECAF is implemented as such because in this way, it only needs to track the taint statuses of the physical addresses that is both accurate and more efficient (in terms of memory space).
The patching to add the required functionality by tainting happens in gen_taintcheck_insn function. In this function, DECAF patches both the INDEX_op_qemu_ld* and INDEX_op_qemu_st* instructions. By patching, DECAF replaces these instructions by INDEX_op_taint_qemu_ld* and INDEX_op_taint_qemu_st* instructions. The part of code from get_taintcheck_insn for patching is:
/* Patch qemu_ld* opcode into taint_qemu_ld* */
gen_opc_ptr[-1] += (INDEX_op_taint_qemu_ld8u - INDEX_op_qemu_ld8u); //sina: here
orig0 = gen_opparam_ptr[-3];
When INDEX_op_taint_* instructions are observed a call to taint_stw_cb will be inserted at the interpretation time in tcg_out_op, and at the runtime the following calls will be issued:
tcg_out_op
taint_stb_cb
__taint_stb_raw
__taint_stb_raw_paddr
/////////////////////////////////
tcg_out_op(…){
…
//in case of cache hit
switch (opc) {
case 0:
..
break;
case 1:
tcg_out_calli(s, (tcg_target_long)taint_stw_cb);
….
/////////////////////////////////
taint_stq_cb and __taint_stq_raw are just two wrappers. __taint_stb_raw_paddr searches for a physical address taint status and updates it with the value of tempidx. Note that tempidx is a CPUState variable and Qemu has access to it at all times. This variable is updated with the taint source value whenever there is a data flow from a taint source such as the keyboard (see the next section for more details). There is also a __taint_ldb_raw_paddr function that updates tempidx by the value of the memory taint status. __taint_stb_raw_paddr maintains a multi-level structure for the physical addresses. The structure is shown in Figure 15. Note that for each level, there is an array e.g. there is an array for the middle indexes of the addresses. The middle index is a number of bits starting from the most significant bits of the address. The corresponding array element for a middle index points to all the leaf indexes that have the same middle index (see Figure 14 for Leaf index bits of an address). Finally, an array element of the Leaf index points to an array containing all the physical addresses that share the same Middle and Leaf index (their initial bits are the same).
Figure 15. Taint status container structure
taint_st_general_i32, which is called from __taint_stb_raw_paddr, breaks down an address to its levels (explained in the previous paragraph). Then, it searches for the address taint status in the data structure. If the input taint status is not clear (at least one of its bit is 1), taint_st_general_i32 creates a record for the address and returns the pointer. This record allocation happens in fetch_leaf_node_from_pool. This function does not allocate memory after a request for allocation; it maintains a list of pre-allocated objects beforehand. Note that lest level object is indeed a bitmap.
In the previous subsections, we extensively discuss taint status propagation. In this section, we explain how we mark a variable as tainted initially i.e. how we monitor taint sources. A set taint status indicates that the data from a taint source e.g. keyboard is present in the current variable. By default, DECAF has support for keyboard, Disk and Network interface cards. A programmer can add support for a custom taint source. In this section, we explain how the keystrokes are monitored by DECAF.
Before explaining DECAF implementation for keyboard taint source, we explain how keystrokes are read by QEMU. Different IO handlers are registered in the QEMU initialization phase in the io_mem_init function; this function along with many other functions is called in cpu_exec_init_all. io_mem_init registers keystroke handler through the cpu_register_io_memory_fixed function. This function registers ps2_write_keyboard function for x86 and PS2 keyboards. Thereafter this registration, this function will be called for keyboard operations. QEMU modifies the keystroke read functionality of QEMU to track the taint status of the input data. Firstly, DECAF modifies the PS2Queue data structure that contains the input data:
typedef struct {
uint8_t data[PS2_QUEUE_SIZE];
#ifdef CONFIG_TCG_TAINT
uint8_t taint_data[PS2_QUEUE_SIZE];
#endif /* CONFIG_TCG_TAINT */
int rptr, wptr, count;
} PS2Queue
taint_data would contain the taint status of the input data. DECAF would fill this array through ps2_queue_taint function. Then, the status from this function is copied to the tempidx global variable via DECAF_keystroke_read function. The trace to the discussed functions is as follows:
ps2_write_keyboard
ps2_put_keycode
ps2_put_keycode_taint
DECAF_keystroke_place
ps2_queue_taint
ps2_read_data
DECAF_keystroke_read
Note that the keyboard source monitoring happens under two conditions. First, CONFIG_TCG_TAINT must be set which will be if DECAF is compiled with the tainting option. Second, the keystroke monitoring must be enabled by the running plugin. By default, either a list of taint registers, memory or keystroke taint can be selected.
static void ps2_put_keycode(void *opaque, int keycode)
{
#ifdef CONFIG_TCG_TAINT
DECAF_keystroke_place(keycode);
if(taint_keystroke_enabled)
{
ps2_put_keycode_taint(opaque,keycode);
return;
}
#endif /* CONFIG_TCG_TAINT */
...
}
To recap, the taint status after reading a key is kept in the tempidx global variable. Note that this is in fact the taint status of the ax register since int 21 that is keyboard read copies the read character to ax.