DPTrace: Dual Purpose Trace for
Exploitability Analysis of Program
Crashes
Rohit Mothe (@rohitwas)
Senior Security Researcher
rohit.mothe *noSPAM* intel.com
Rodrigo Rubira Branco (@BSDaemon)
Principal Security Researcher
rodrigo.branco *noSPAM* intel.com

Disclaimeru

We don’t speak for our employer(duh!). All the opinions andinformation presented here is our responsibility (actually no
one has seen this talk before today)u IMPORTANT: No, we are *not* part of the Intel Security Group(McAfee)Agenda
•
•
•
•
•
•
•
•

Objectives
Current state of Affairs or Security Today
Taint Analysis Introduction
Our approach – Dual Tracing
Comparison with other ideas
Demos
Limitations
FutureObjectives•

Contribute towards improving the state of the art in crashanalysis•Automate laborious/repetitive parts, but still requiring skilled
exploit writer/analyst•

Discuss hybrid usage of techniques and the mixture ofautomation with manual analysis

Current State of Affairsu

Buggy programs deployed on critical serversu

Rapidly-evolving threats, attackers and tools (exploitation
frameworks)uLack of developers training, resources and people to fix
problems and create safe codeuThat’s why we are here today, right?

tl; drthnx Marcio !

Taint Analysis for Program
Crashesu

Through our work we try to answer two fundamental questions:u Are the input operands in the attacker’s control?
u And if so, is the forward execution providing a primitivethat is good for an attacker?

u

Taint Analysis is one specific kind of program flow analysis and
we use it to define the influence of external data (attacker’s
controlled data) over the analyzed applicationu

Since the information flows, or is copied to, or influences otherdata there is a need to follow this influence in order todetermine the control over specific areas (registers, memory
locations). This is a requirement in order to determine
exploitability

History and LoreBackward-Taint
u
u

u
u

u

Original Motivation: Complex client-side vulnerability
in a closed (at the time) file format
Extended Motivation: Trying to better analyse
hundreds of thousands of bugs in Microsoft Word(search for Ben Nagy, Coseinc)Initial version integrated with a fuzzer, only for Linux(showed in 2011 at Troopers)
Ported version for Solaris to analyze a vulnerability
released by Secunia in the same software RISE
Security released a vulnerability a month before(also circa 2011)
Thanks to Julio Auto’s parallel research in the same
field, a Windows version was created (extended inthis research)

History and LoreForward-Taint
u

u
u
u
u

Original Motivation: Triaging submissions in avulnerability purchase program is hard. Many
submissions lack a complete exploit but still might
have real value
Extended Motivation: Categorizing fuzzing crashes isa pain (NOT bang(!) exploitable categorizing)
Manual process includes lots of repetitive steps
Automation is key. Certain classes repeat
themselves (such as UAF)
‘Prototyping Exploitation’ in such cases is both cost
and time effective. Also a more reasonable andsimpler ‘automatable’ problem than automating
exploit writing for all classes of bugs. Prototype or
GTFO!

Existing Solutions - What we aren’t
u

u

u

!exploitableu

Tries to classify unique issues (crashes appearing through different code paths, machines
involved in testing, and in multiple test cases). Group the crashes for analysisu

Quickly prioritizes issues (since crashes appear in thousands, while analysis capabilities are
VERY limited)uClassic, timeless!

Spider PiguCreated by Piotr Baniau

Not available for testing, but from the paper: It is much more advanced them the provided
tool (but well, it is not available?)u

Virtual Code Integration (or Dynamic Binary Rewriting)u

Disputable Objects: Partially controlled data is analyzed using the parent data

Taint Bochsu

Used for tracking sensitive data lifecycle in memory

Existing Solutions - What we aren’t
..

contd
u

u

u

Taint Checku

Uses DynamicRIO or Valgrindu

Taint Seed: Defining the tainted values (data comming from the network for example)u

Taint Tracker: Tracks the propagation, Taint Assert: Alert about security violationsu

Used while testing software to detect overflow conditions, does nto really help in the exploit
creation

BitblazeuAn amazing platform for binary analysisu

Provides better classification of exploitability (Charlie Miller talk in BH)u

Can be used as base platform for the provided solution (VINE)

Moflow Frameworku

Cisco Talos. Tools built on CMU’s BAP framework.

u

sliceflow- post-crash graph back taint sliceru

Post-crash forward symbolic emulator looking for more exploitable conditionsuPretty neat and advanced!

State Transition for Memory
CorruptionuCase 1 (green):
Format Stringu

Case 2 and 3(red and blue):buffer overflowuCase 4 (purple):
unpredictable

Source:Automatic Diagnosis andResponse to Memory
Corruption Vulnerabilities

c: corrupting
instruction
t: takeover instruction
f: faulting instruction

Moving Backwardu

Legitimate assumption:u

To change the execution of a program illegitimately
we need to have a value being derived from theattacker’s input (which we call: controlled by theattacker)uString sizes and format strings should usually be
supplied by the code itself, not from external, untrusted inputsu

Any data originated from or arithmetically derived
from un-trusted source must be inspectedAnalyzing Taintu

Tainted data: Data from un-trusted sourceu

Keeps track of tainted data (from un-trusted
source)uMonitors program execution to track how tainted
attribute propagatesu

Detect when tainted data is used in sensitive way

Taint PropagationuWhen a tainted location is used in such a way that a value ofother data is derived from the tainted data (like inmathematical operations, move instructions and others) wemark the other location as tainted as welluThe transitive relation is:u

If information A is used to derive information B:u A->t(B) -> Direct flowu

If B is used to derive information C:u B->t(C) -> Direct flowu Thus: A->t(C) -> Indirect flowu

Due to the transitive nature, you can analyze individualtransitions or the whole block (A->t(C))

Locationu

A location is defined as:uMemory address and sizeu

Register name (we use the register entirely, not partially -> thus
%al and %eax are the same)u When setting a register, we set it higher (setting %al as tainted will also

taint %eax)u When clearing a register, we clear it loweru

To keep track over bit operations in a register it is important totaint the code-block level of a control flow graphuThis create extra complexity due to the existence of the flow
graph and data flow dependencies graphuThe dependencies graph represents the influence of a source
data in the operation been performed

FlowsuExplicit flow:uu

Implicit flow:uu

mov %eax, A

If (x == 1) y=0;

Conditional statements require a special analysis
approach:uIn our case, we are analyzing the trace of aprogram (not the program itself, but only what was
executed during the debugging section)u

We have two different analysis step: tracing andanalysis

Special ConsiderationsuPartial Tainting: When the untrusted source does
not completely control the tainted datau

Tainting Merge: When there are two different
untrusted sources being used to derive some data

u

Data
u

In Use: when it is referenced by an operationu

Defined: when the data is modified

Inheritance problems
Problem: state explosion for binary operations !
Application

Propagation
Tracking

Inheritance
Tracking

mov %eax ß A
mov B ß %eax

taint(%eax) = taint(A)taint(B)= taint(%eax)%eax inherits from A
B inherits from %eax

add %ebx ß D

taint(%ebx) |= taint(D)insert D into %ebx’s
inherit-from list

EventsRaree.g., malloc/free, system calls

Frequente.g., memory access,data movement

Tracking Instructionsu

Pure assignments: Easy to trackuu

If a tainted location is used to define another location, thisnew location will be tainted

Operations over strings are tainted when:u

They are used to calculate string sizes using a tained
locationu a = strlen(tainted(string));u Since the ‘string’ is tainted, we assume the attacker

controls ‘a’u

Search for some specific char using a tainted location,
defining a flag if found or not foundu pointer = strchr(tainted(string), some_char);u If (pointer) flag=1;u ‘flag’ is tainted if the attacker controls ‘string’ or‘some_char’Tracking Instructions

..

contd

u

Arithmetic instructions with at least one tainted
data usually define tainted resultsu

Those arithmetic instructions can be simplified tomap to boolean operations and then thefollowing rules applies

Eflags and Flow InformationuThe eflags register can also be tainted to monitor
flags conditions influencing in operations (and
flow)

u

In the presented approach, conditional branches
are taken care due to the trace generated by
the WinDBG plugin (single-stepping)

Backward Taint Analysisu

Divide the analysis process in two parts:u

A trace from a good state to the crash (incrementally
dumped to a file) -> Gather substantial information about
the target application when it receives the input data,
which is formally named 'analysis'u

Analysis of the trace file -> Formally defined as 'verification'
step, where the conclusive analysis is doneForward Taint Analysis

24ØTo see what kind of primitives (read/write/calls) are available we‘prototype’ input control and allocate a fake object structure inmemory such that the program can continue from the point of thecrash to other code paths.

Ø

The property of such fake memory structure should guarantee to areasonable extent that any memory references (like virtual function
tables or other object pointers) will be resolved including memory
address references that are additive or subtractive to the faulting
address(which is already assumed controllable).

ØIn essence one could imagine it as simulating the reallocation of a fakeobject ‘within’ the debugger in a use-after-free situation andcontinuing the exception. Or allocating an adjacent object in an out ofbounds access violation, etc.

Fake Memory Structure
SampleForward Logicu

In the debugger you see a seemingly non exploitable read AV(access violation).
u

Example: mov eax ,[ecx] ; ( ecx is supposed here to be a pointer toattacker controlled memory.)uYou allocate a chunk of memory within the process (preferably the sizeof the memory pointed to by ecx to mimic an accurate freed block
control using heap massaging,feng-shui)uThe permissions of all memory blocks in a linked list chain are
read-only. So any attempt to write/execute on any of thevalues within the memory blocks would cause an exception
later and that shows evidence of exploitabilityu

Now manually change the ecx value in the crash to point tothe address of the root of this linked list which is the root of thechain of memory blocks pointing to one anotheruContinue the program execution and it will continue from thepoint of crash with the modified value of ecx.

Need for Intermediate
Languagesu

Assembly instructions have explicit operands, which are easy
to deal with, and sometimes implicit operands:uInstruction: push eaxu

Explicit operand: eaxu

What it really does?
u ESP = ESP – 4 (a substraction)u SS:[ESP] = EAX (a move)u Here we have ESP and SS as implicit operandsu

Tks to Edgar Barbose for this great example!

Implementing the TraceruInstead of using an intermediate language, we play straightwith the debugger interfaces (WinDBG). Windbg or GTFO!

uThe tracer stores some useful information, like effective
addresses and data values and also simplifies the instructions
for easy parsing:u

CMPXCHG r/m32, r32 -> 'Compare EAX with r/m32. If
equal, ZF is set and r32 is loaded into r/m32. Else, clear ZF
and load r/m32 into AL'u Such an instruction creates the need for conditionaltaints, since by controlling %eax and r32 the attacker
controls r/m32 too.

Implementation Detailsu

Instead of using an intermediate language, we play straight with the
debugger interfaces (WinDBG). Windbg or GTFO!

u

Trace File Contains:u

Mnemonic of the instruction and operandsu

Dependences for the source operandu Eg:

Elements of an indirectly addressed memoryu This creates a tree of the dataflow, with a root in the crash

instructionu

The verification (GUI and cmdline program) step reads this file and:uu

Search this tree using a BFS algorithm

Forward step uses the debugger interfaces for the memory allocationand forward executionICE CREAM ICE
CREAM ICE CREAM
ICE CREAM ICE
CREAM ICE CREAM
ICE CREAM ICE
CREAM ICE CREAM
ICE CREAM ICE
CREAM ICE CREAM
ICE CREAM ICE
CREAM ICE CREAM
ICE CREAM ICE
CREAM ICE CREAM
ICE CREAM ICE
CREAM ICE CREAM

30

Program Execution Timeline

31

Program start
Trace! Check Taint! Forward Execution

Initial Crash, AV

Trace! Check Taint! Forward Execution
…
…
…
…
…
…
Trace! Check Taint! Forward Execution…
…
Trace! Check Taint!
…
…

Exception à Constraint 1

Exception à Constraint n
Exploitable Primitive?! Profit!
OR march on, down to hell L

Theoretical Exampleu1-) mov edi, 0x1234 ; dst=edi, src=0x1234u2-) mov eax, [0xABCD]
addr

u

3-) lea ebx, [eax+ecx*8] ; dst=ebx, src=eax, srcdep1=ecxu

4-) mov [edi], ebxu5-) mov esi, [edi]u6-) mov edx, [esi]; dst=eax, src=ptr 0xABCD ; Note 0xABCD is evil

; dst=ptr 0x1234, src=ebx; dst=esi, src=ptr 0x1234, srcdep1=edi; Crash!!!

Theoretical Example

contd..

u6-) Where does [esi] come from?

u5-) [edi] is moved to esi, where edi comes from and what does
exist in [edi]?

u4-) [edi] receives ebx and edi is defined in 1-) from a fixed
value

u

3-) ebx comes from a lea instruction that uses eax and ecxu2-) eax receives a value controlled by the attackeru... ecx is out of the scope here :)Assumptions & Challengesu

Since we only use the trace information, if the crash input data does notforce a flow, we can’t see the influence of the input over this specific flow
data

u

To solve that:u

If a jmp is dependent of a flag, the attacker controls branch decisionuControl over a branch means tainted EIPu

To define the value of EIP, consider:u The address if the jump is takenu The address of the next instruction (if the jump is not taken)u The value of the interesting flag register (0 or 1)u Then: %eip <- (address of the next instruction) + value of theregister flag * ( |address if jump is taken – address of the next
instruction| )Forward Analysisu

The method here was conceived originally to help
determine whether crashes for potential UAF (Use-AfterFree) bugs in browsers are exploitable or notu

UAFs in browsers or any significantly large programs forthat matter are often hard to analyze for exploitability
and typically involve following varied code paths in thecontrol flow to find a write access violation/potential
code redirection using indirect callsu

The idea is not just limited to UAFs thoughu

After input control(first part of the problem) has been
determined, the next logical step is to gauge what canbe done with it.

Command-line options

Analyzer

37

Forward

Forward

Sample Analysis on dead bugs

40

Sample Analysis 1

41

We did a bit of cheating to avoid huge traces (from that point on
til the crash, we would have traced more than 10 million instructions)- CVE-2010-0188 – Adobe Reader Libtiff TIFFFetchShortPair Stack-based Buffer
Overflow- TIFF file embedded in a PDF were the IFD Entry has Tag ID (0x0129, 0x0141,
0x0212 or 0x0150) and Tag Type 3 (short)- The field data count of the TIFF file will be used as size (dc*2) to copy to a
fixed buffer in stackContd…

At the crash point, we check the trace to see if the pointer isIndeed controlled

42

Contd…

Dataflow information can be visualized in the GUI

43

Contd…

We indeed control the values (coming from our input file)44

Sample Analysis 2

CVE-2014-0282 IE8/9/10/11 ‘Cinput’ Use-After-Free (MS14-035)

Contd…

Replace Freed object with the root of the fake object chain

Contd…

Continue from initial crash and trace each subsequent
breakpoint/access violation

Contd…

Add the range of the fake allocated objects, so when we look for the taintinformation on the instruction of interest, we can confirm it is mapped to ourcontrolled memory areas

Contd…

Program Control Immediately evident. We just need to make sure wecan point indeed it to our fake structure

Contd…

50

We see that the EIP value at time of crash comes from our fake object
allocated at the previous crashContd…

51

Visualize it in the tracer and trace the program control (or directly in thecommand line of the debugger, shown later)

Contd…

52

Taint source is confirmed also in the analyzer (visual here). Samething can be obtained in the command line by !dptrace_analyzer<analyzer_binary> <trace_file> <keep GUI open> <ranges> <index of
instruction to check the taint of>Contd…

53

Because the backward taint analysis demand tracing the process, so
we can later construct the BFS analysis, it is important to use
intelligently/diligently. In the case of this issue, we use to analyze apart of the execution, instead of the initial crash.

Contd…

54

Contd…

55

Contd…

56

Everything that was done using the GUI (setting the taint ranges, defining
the instruction of interest and analyzing its taint information) is possible to
do via the command-line of the debugger, as shown here

Sample Analysis 357

CVE-2015-6152 IE 11 CObjectElement Use-After-Free . Initial Crash on IE 11
without patches.

Contd…

58

Fake object chain of 4 objects of size 200. Precise size can be determined bymanual analysis to figure out the freed/alloc’d function and checking thesize of the root object.

Contd…

59‘Redefine’ the reference to freed reference (eax) with the first fake object .
Continue the execution with !dptrace_trace and monitor the forward trace .

Contd…

60

Add taint range and check to see if the source of an access violation canbe traced back to controlled input

Contd…

Following another path by meeting a new constraint

61

Contd…

More constraints

62

Contd…

Checking the taint source again. This particular execution run leads
us to uncertainty and we aren’t sure of an exploitable primitive yet.

63

Contd…

So we carry on another execution while trying to meet some otherconstraints and hit an alternate code path this time.

64

Contd…

65

We try another path this time by crafting some different values within the fakeobject, notably the value of 0x40000 in the dword @ fake_object+0x24. We
also modify references to the same fake object in edi (CTreeNode *) and on
the stack (esp+24). Hit a more interesting exception!

Contd…

66

Preliminary analysis shows us that the MSHTML!!report_securityfailure call
was triggered due to a failed VTguard_check (next figure)Contd…

67

Confirm taint control and we influence the pointer which is dereferenced to do thevtguard check. That there is code execution right after the vtguard_check can either
be looked into the debugger or within IDA for more clarity as shown aboveChallenges & Limitationsu

Determining the actual range of memory which needs
to be traced. Determining this is easier for some cases(like file format bugs) whereas for browser based bugs
this can be difficult (and sometimes unnecessary)u

Explosion and partial tainting (we assume full control
when merging taint)u

Because the tracer outputs instruction information, it
needs to understand the semantics of it (for example,
source and destination operands):u

It only supports the most basic x86 subset (no x87,
MMX, XMM, etc) (future versions , also, helping iscaring!)Challenges & Limitations
Ø

Another limitation of the approach is covering conditional
code paths that hit only on certain values expected to be in
the memory address (checking of reference counters, object
type tag or some other metadata that affects the control
flow of the program after the crash point)Ø Branch Explosion! Similar problems can arise withsymbolic execution approachØ

Manual analysis involves knowing where to break , where to
start tracing, etc. The closer to the exception the better
because of smaller traces and faster processing time by the
analyzerØ

Not a magic solution that works on its own without a skilled
analyst. Not a one size fits all solution either. Meant toaugment crash analysis.

69

Futureu

We aren’t soothsayers. More like sooth-slayers \,,/u

Please, read TODO.txt in the code trunk and send pull requests :pLatest version of thispresentation, paper, codeand demos available at:u

https://github.com/rrbranco/blackhat2016

Acknowledgmentsu

Julio Auto for his previous work alongside one of the authors of this work
(Rodrigo Branco) in implementing VDT (Vulnerability Data tracer) which
was the original implementation of the backward taint tracing pluginuDavid D. Rude(@bannedit) and Kiran Bandla(@kb) for ideas andfeedback regarding the initial prototype of the forward traceu

All of the other researchers who contributed to this field!

Thanks!
Rohit Mothe (@rohitwas)
Senior Security Researcher
rohit.mothe *noSPAM* intel.com
Rodrigo Rubira Branco (@BSDaemon)
Principal Security Researcher
rodrigo.branco *noSPAM* intel.com