System Implementation

The implementation of the algorithms described in Chapter 3 consists of approximately 7000 lines of C++.
This code is logically divided into components that match the system diagram in Figure 3.1. In this Chapter
we will explain the details of our implementation, focusing on the instrumentation and analysis routines that
make up the core of the system and the corresponding data structures.
4.1 Binary Instrumentation
The implementation of stage 1 of our algorithm is essentially two components that work in tandem to
perform instrumentation and run-time analysis. Using the functionality provided by Pin we instrument a
variety of events, including thread creation, system calls, and instruction execution. The instrumentation
code analyses the events and registers callbacks to the correct run-time processing routines.
4.1.1 Hooking System Calls
All taint analysis algorithms require some method to seed an initial pool of tainted locations. One approach
is to hook system calls known to read data that may be potentially tainted by attacker input, e.g. read.
Another potential approach is to hook specific library calls, but as previously pointed out [14] this could
require one to hook large numbers of library calls instead of a single system call on which they all rely.
To mark memory locations as tainted we hook the relevant system calls and extract their destination
locations. Pin allows us to register functions to be called immediately before a system call is executed
(PIN AddSyscallEntryFunction) and after it returns (PIN AddSyscallExitFunction). We use
this functionality to hook read, recv and recvfrom. When a system call is detected we extract the
destination bu er of the function using PIN GetSyscallArgument and store the location. This provides
us with the start address for a sequence of tainted memory locations.
When a system call returns we extract its return value using Pin GetSyscallReturn. For the system
calls we hook a return value greater than 0 means the call succeeded and data was read in. When the return
value is greater than 0 it also indicates exactly how many contiguous bytes from the start address we should
consider to be tainted. On a successful system call we first store the data read in, the destination memory
location and the file or socket it came from in a DataSource object. The DataSource class is a class
we created to allow us to keep track of any input data so that it can be recreated later when building the
exploit. It also allows us to determine what input source must be used in order to deliver an exploit to the
target program. Once the DataSource object has been stored we mark the range of the destination bu er
as tainted.
Once a location has been marked as tainted the instruction level instrumentation code can propagate the
taint information through the programs memory and registers.
45
4.1.2 Hooking Thread Creation and Signals
As well as system calls we insert hooks on thread creation and on signals received from the OS. In multithreaded
applications it is necessary for us to determine when threads are created and destroyed and to
identify the currently active thread when calling our analysis routines. Threads do not share registers so
a register that is tainted by one thread should not be marked as tainted for any others. When a thread is
created we instantiate a new object in our taint analysis engine that represents the taint state of its registers.
This object is deleted when the thread is destroyed.
As mentioned in Chapter 3, one of the mechanisms one could potentially use to detect a possible vulnerability
is by analysing any signals sent to the program. Using the function PIN AddContextChangeFunction
we can register a routine to intercept such signals. If the signal is one of SIGKILL, SIGABRT or SIGSEGV
we pause the program and attempt to generate an exploit. We eventually decided not to use this mechanism
for vulnerability detection as it introduced complications when attempting to determine the exact cause of
the signal and hence the vulnerability.
4.1.3 Hooking Instructions for Taint Analysis
In Chapter 3 all of the binary instrumentation is performed by algorithm 3.1. In this section we will elaborate
on the methods by which this instrumentation takes place.
Our taint analysis engine provides a low level API through the TaintManager class. This class provides
methods for directly marking memory regions and registers as tainted or untainted. To reflect the
taint semantics of each x86 instruction at run-time we created another class titled x86Simulator. This
class interacts directly with the TaintManager class and provides a higher level API to the rest of our
analysis client. For each x86 instruction X the x86Simulator contains functions with names beginning
with simulateX e.g. simulateMOV corresponds to the mov instruction. Each of these functions takes
arguments specifying the operands of the x86 instruction and computes the set of tainted locations resulting
from the instruction and these operands.
For each instruction taint analysis is performed by inserting a callback into the instruction stream to the
correct simulate function and provide it with the instructions operands. As Pin does not utilise an IR this
requires us to do some extra processing on each instruction in order to determine the required simulation
function and extract the instructions operands.
The x86Simulator class provides a mechanism for taint analysis but to use it we must have a method of
analysing individual x86 instruction. Pin allows one to register a function to hook every executed instruction
via INS AddInstrumentFunction. We use this function to filter out those instructions we wish to process.
For every instruction executed we first determine exactly what instruction it is so we can model its taint
semantics. This process is made easier as Pin filters each instruction into one or more categories, e.g. the
movsb instruction belongs to the XED CATEGORY STRINGOP category. It also assigns each instruction a
unique type, e.g. XED ICLASS MOVSB for the movsb instruction. An example of the code that performs
this filtering is shown in Listing 4.1.
This code allows us to determine the type of instruction being executed. The code to process the actual
instruction and insert the required callback is encapsulated in the processX86.processX functions.
Inserting Taint Analysis Callbacks
When hooking an instruction the goal is to determine the correct x86Simulator function to register a
callback to so that at run-time we can model the taint semantics of the instruction correctly. The code in
Listing 4.1 allows us to determine the instruction being executed but each instruction can have di erent
taint semantics depending on the types of its operands. For example, the x86 mov instruction can occur
in a number of di erent forms with the destination and source operands potentially being one of several
combinations of memory locations, registers and constants. In order to model the taint semantics of the
instruction we must also know the type of each operand as well as the type of the instruction. Listing 4.2
demonstrates the use of the Pin API to extract the required operand information for the mov instruction.
The code shown is part of the processX86.processMOV function.
46
Listing 4.1: “Filtering x86 instructions”
1 UINT32 cat = INS_Category(ins);
2
3 switch (cat) {
4 case XED_CATEGORY_STRINGOP:
5 switch (INS_Opcode(ins)) {
6 case XED_ICLASS_MOVSB:
7 case XED_ICLASS_MOVSW:
8 case XED_ICLASS_MOVSD:
9 processX86.processREP_MOV(ins);
10 break;
11 case XED_ICLASS_STOSB:
12 case XED_ICLASS_STOSD:
13 case XED_ICLASS_STOSW:
14 processX86.processSTO(ins);
15 break;
16 default:
17 insHandled = false;
18 break;
19 }
20 break;
21
22 case XED_CATEGORY_DATAXFER:
23
24 ...
Listing 4.2: “Determining the operand types for a mov instruction”
1 if (INS_IsMemoryWrite(ins)) {
2 writesM = true;
3 } else {
4 writesR = true;
5 }
6
7 if (INS_IsMemoryRead(ins)) {
8 readsM = true;
9 } else if (INS_OperandIsImmediate(ins, 1)) {
10 sourceIsImmed = true;
11 } else {
12 readsR = true;
13 }
Listing 4.3: “Inserting the analysis routine callbacks for a mov instruction”
1 if (writesM) {
2 INS_InsertCall(ins, IPOINT_BEFORE, AFUNPTR(&x86Simulator::simMov_RM),
3 IARG_MEMORYWRITE_EA,
4 IARG_MEMORYWRITE_SIZE,
5 IARG_UINT32, INS_RegR(ins, INS_MaxNumRRegs(ins)-1),
6 IARG_INST_PTR,
7 IARG_END);
8 } else if (writesR) {
9 if (readsM)
10 INS_InsertCall(ins, IPOINT_BEFORE, AFUNPTR(&x86Simulator::simMov_MR), ..., IARG_END);
11 else
12 INS_InsertCall(ins, IPOINT_BEFORE, AFUNPTR(&x86Simulator::simMov_RR), ..., IARG_END);
13 }
47
Once the operand types have been extracted we can determine the correct function in x86Simulator
to register as a callback. The x86Simulator class contains a function for every x86 instruction we wish
to analyse and for each instruction it contains one or more variants depending on the possible variations in
its operand types. For example, a mov instruction takes two operands; ignoring constants it can move data
from memory to a register, from a register to a register or from a register to memory. This results in three
functions in x86Simulator to handle the mov instruction - simMov MR, simMov RR and simMov RM.
The code in Listing 4.3 is from the function processX86.processMOV. It uses function INS InsertCall
to insert a callback to the correct analysis routine depending on the types of the mov instructions operands.
Along with the callback function to register, INS InsertCall takes the parameters to pass to this function1.
This process is repeated for any x86 instructions we consider to propagate taint information.
Under-approximating the Set of Tainted Locations
Due to time constraints on our implementation we have not created taint simulation functions for all possible
x86 instructions. In order to avoid false positives it is therefore necessary to have a default action for all
non-simulated instructions. This default action is to untaint all destination operands of the instruction. Pin
provides API calls that allow us to access the destination operands of an instruction without considering its
exact semantics. By untainting these destinations we ensure that all locations that we consider to be tainted
are in fact tainted. We perform a similar process for instructions that modify the EFLAGS register but are
not instrumented.
4.1.4 Hooking Instructions to Detect Potential Vulnerabilities
We detect potential vulnerabilities by checking the arguments to certain instructions. For a direct exploit
we require the value pointed to by the ESP register at a ret instruction to be tainted or the memory location/
register used by a call instruction. We can extract the value of the ESP using the IARG REG VALUE
placeholder provided by Pin and the operands to call instructions can be extracted in the same way as for
the taint analysis callbacks.
For an indirect exploit we must check the destination address of the write instruction is tainted, rather
than the value at that address. As described in [19], an address to an x86 instruction can have a number of
constituent components with the e ective address computed as follows2:
Effective address = Displacement + BaseReg + IndexReg * Scale
In order to exploit a write vulnerability we must control one or more of these components. Pin provides
functions to extract each component of an e ective address. e.g. INS OperandMemoryDisplacement,
INS OperandMemoryIndexReg and so on. For each instruction that writes to memory we insert a callback
to run-time analysis routine that takes these address components as parameters and the value of the write
source.
4.1.5 Hooking Instructions to Gather Conditional Constraints
As described in Chapter 3, to gather constraints from conditional instructions we record the operands
of instructions that modify the EFLAGS register and then generate constraints on these operands when
a conditional jump is encountered. Detecting if an instruction writes to the EFLAGS register is done
by checking if the EFLAGS register is in the list of written registers for the current instruction, e.g. if
1At instrumentation-time it is sometimes not possible to determine the exact operand values an instruction will have at runtime.
To facilitate passing such information to run-time analysis routines Pin provides placeholder values. These placeholders
are replaced by Pin with the corresponding value at run-time. For example, there are placeholders for the address written
by the instruction (IARG MEMORYWRITE EA) and the amount of data written (IARG MEMORYWRITTEN EA). There are a number
of other placeholders defined for retrieving common variables such as the current thread ID, instruction pointer and register
values.
2From the Pin website, http://www.pintool.org
48
Listing 4.4: “Inserting a callback on EFLAGS modification”
1 if (op0Mem && op1Reg) {
2 INS_InsertCall(ins, IPOINT_BEFORE, AFUNPTR(&x86Simulator::updateEflagsInfo_RM),
3 IARG_MEMORYREAD_EA,
4 IARG_MEMORYREAD_SIZE,
5 IARG_UINT32, INS_RegR(ins, INS_MaxNumRRegs(ins)-1),
6 IARG_UINT32, eflagsMask,
7 IARG_CONTEXT,
8 IARG_THREAD_ID,
9 IARG_INST_PTR,
10 IARG_END);
11 }
Listing 4.5: “Inserting callbacks on a conditional jump”
1 VOID
2 processJCC(INS ins, JCCType jccType)
3 {
4 unsigned eflagsMask = extractEflagsMask(ins, true);
5 INS_InsertCall(ins, IPOINT_AFTER, AFUNPTR(&x86Simulator::addJccCondition),
6 IARG_UINT32, eflagsMask,
7 IARG_BOOL, true,
8 IARG_UINT32, jccType,
9 IARG_INST_PTR,
10 IARG_END);
11
12 INS_InsertCall(ins, IPOINT_TAKEN_BRANCH, AFUNPTR(&x86Simulator::addJccCondition),
13 IARG_UINT32, eflagsMask,
14 IARG_BOOL, false,
15 IARG_UINT32, jccType,
16 IARG_INST_PTR,
17 IARG_END);
18 }
INS RegWContain(ins, REG EFLAGS) is true. If an instruction does write to the EFLAGS register we
can extract from it a bitmask describing those flags written.
Using the same INS Is* functions as shown in Listing 4.2 we determine the types of each operand.
Once again this is necessary as we use a di erent simulation function for each combination of operand types,
where an operand type can be a memory location, register or constant. Once the operand types have been
discovered we register a callback to the correct run-time routine, passing it the instruction operands and a
bitmask describing the bits changed in the EFLAGS register. Listing 4.4 exemplifies how the callback is
registered for a two operand instruction where the first operand is a memory location and the second is a
register.
On lines 3 and 4 the Pin placeholders to extract the memory location used and its size are used. The
register ID is extracted on line 5 and passed as a 32-bit integer. Similarly the bitmask describing the EFLAGS
modified is passed as a 32-bit integer on line 6.
Inserting Callbacks to Record Conditions from Conditional Jumps
The above code is used to keep track of the operands on which conditional jumps depend on. To then
convert this information to a constraint we need to instrument conditional jumps. Algorithm 3.1 in Chapter
3 we described the process of instrumenting a conditional jump instruction. We insert two callbacks for each
conditional jump. One on the path resulting from a true condition and one on the path resulting from a
false condition.
49
Listing 4.6: “Simulating a mov instruction”
1 VOID
2 x86Simulator::simMov_MR(UINT32 regId, ADDRINT memR, ADDRINT memRSize, THREADID id, ADDRINT pc)
3 {
4 SourceInfo si;
5
6 // If the source location is not tainted then untaint the destination
7 if (!tmgr.isMemLocTainted(memR, memRSize)) {
8 tmgr.unTaintReg(regId, id);
9 return;
10 }
11
12 // Set the information on the source operand
13 si.type = MEMORY;
14 // The mov instruction reads from address memR
15 si.loc.addr = memR;
16
17 vector sources;
18 sources.push_back(si);
19
20 TaintInfoPtr tiPtr = tmgr.createNewTaintInfo(sources, (unsigned)memRSize,
21 DIR_COPY, X_ASSIGN, 0);
22 tmgr.updateTaintInfoR(regId, tiPtr, id);