US008321840B2

(12) Unlted States Patent

Nagarajan et a].
(54) SOFTWARE FLOW TRACKING USING MULTIPLE THREADS
.. . . .

(10) Patent N0.:

(45) Date of Patent:
7,512,826 B2 * 7,523,465 B2 *
7,757,282 B2*

US 8,321,840 B2
Nov. 27, 2012

3/2009 Armstrong et a1. ......... .. 713/375 4/2009 Aamodt et al. 719/320

7/2010 Pandit et al. ....... . . . .. 726/22

7,814,469 B2 *

10/2010

Wan

et al.

...... ..

717/161

(75) Inventors: Vljayanand NagaraJan, Rlverslde, CA

(Us); Ho-seop K1111, Austln, TX (Us);
Youfeng Wu, Palo Alto, CA (US); Rajiv

7,818,547 B2 * 100010 Amidt et a1

7,823,135 B2 * 10/2010 Horning et al.
7,870,610 B1 * l/20ll
7/2012 4/2002

712/220
717/126
. . . .. 726/23

Mitchell et al. . . . .
Pensak et al. .... .. Guthrie et al.

Gupta Tucson AZ (Us)

7,950,012 B2 *
8,225,290 B2 * 2002/0040470 A1*

5/2011 Tirumalai et a1. ..

718/102
717/126 717/126

(73)

Asslgnee. Intel Corporatlon, Santa Clara, CA (Us)

2003/0088854 A1,. 5/2003 wygodny et a1 2003/0208743 A1 * 11/2003 Chong et al.

2005/0066079 A1* 3/2005 Luick .... ..

7l7/l30 717/106
710/36

(*)

Notice:

Subject to any disclaimer, the term ofthis

patent is extended or adjusted under 35

2005/0071438 A1 *
2005/0081018 Al*

3/2005 Liao et al.

709/214

4/2005 Luick .......................... .. 712/218

U.S.C. 154(b) by 1360 days.

(21) Appl. No.: 11/965,271
(22)
(65)

(Continued)
OTHER PUBLICATIONS
Chabbi, Ef?cient Taint Analysis Using Multicore Machines, Jul.
2007, Published on the Website of University of Arizona. [retrieved

Filed:

Dec_ 27, 2007

Prior Publication Data Us 2009/0172644 A1 Jul 2 2009

on Sep. 12, 2011]; Retrieved from Internet <URL:https:/WWW.cs. ariZ0na.edu/s0lar/papers/milind.thesis.pdf>; pp. 1-60.*

(51)
(52)

Int. Cl.
G06F 9/44 (2006-01)
US. Cl. ....................... .. 717/126; 717/106; 717/130

(Continued)
Primary Examiner * Thuy Dao
Assistant Examiner * Xi D Chen

(58)

Field of Classi?cation Search ...................... .. None

(74) Azwrney, Agenz, or Firm i Trop, Pruner & Hu, PC.

See application ?le for complete search history.

(57)
(56) References Clted U S PATENT DOCUMENTS
'

ABSTRACT

Methods, systems and machine readable media are disclosed for performing dynamic information How tracking. One
method includes executing operations of a program With a

Q1 *

""""""""""" "
714/11

main thread, and tracking the main threads execution of the

operations of the program With a tracking thread. The method

7117389 B2 * 100006 Luick

731343124 B2 * 11/2006 ohsawa et a1, ,,

7,272,820 B2 * 9/2007 Klianev ......... ..

713/100
717/ 106

further includes updating, With the tracking thread, a taint

value associated With the value of the main thread to re?ect

7,293,251 B2 : 11/2007 z?lman et a1~

* 733863839 B1 *
7,398,521 B2*
7,496,901 B2 *

717/100
717/130
717/151

Whether the value is tainted, and determining, With the track

ing thread based upon the taint value, Whether use of the value by the main thread violates a speci?c security policy.
18 Claims, 3 Drawing Sheets

6/2008 Golender et
7/2008 Ho?ehner et al.

2/2009 Begg et al. .................. .. 717/130

SCAN INPUT PROGRAM AND cREATE ,510 THE MAIN AND TRACKING THREADs

DISPATCH THE THREADs TO DIFFERENT PROCESSOR CORES

COMPUTED VALUES NEED FOR INFORMATION FLOW TRACKING

,520

MAIN THREAD RUN THE ORIGINAL OPERATIONS AND SEND NEcEssARY

TRACKING THREAD RUN THE TRACKING OPERATIONS AND DETERMINE WHETHER

INFORMATION TO THE TRACKING THREAD

TNO-TTYTH-TT A SECURITY POLICY SECURITY ATTACK IS VIOLATED

H
550

IS DETECTED

\
540

US 8,321,840 B2
Page 2
U.S. PATENT DOCUMENTS
2005/0223199 A1*
2005/0235136 A1*

Chen, Shuo et al., Non-Control-Data Attacks Are Realistic Threats,

10/2005
10/2005

Grochowskiet al. ....... .. 712/235

Barsotti et al. ..... . . . .. 713/1

Department of Computer Science, North Carolina State University,

pp. 1-15.

2006/0101410 A1*

5/2006

Massarenti et a1. ......... .. 717/126

Crandall, Jedidiah R., et al., Minos: Control Data Attack Prevention

2007/0240141 A1
2009/0013329 A1* 2009/0276754 A1*
2009/0313600 A1* 2010/0088681 A1*

10/2007 Qin et a1.

1/2009 May et a1. 11/2009 Lind et a1. . 719/313 . 717/106
12/2009 Ayers et al. . . 717/106 4/2010 Wang et a1. ................. .. 717/126

Orthogonal to Memory Model, IEEE Computer Society. Proceed

ings of the 37th International Symposium on Microarchitecture

(MICRO-37 2004), pp. 221-232. Dalton, Michael et al., Deconstructing Hardware Architectures for

Security, Computer Systems Laboratory, Stanford University, pp.

1-8.

OTHER PUBLICATIONS

Dehnert, James C., et al., The Transmeta Code Morphing Software:

Haldar, et al., Dynamic Taint Propagation for Java, Prodeedings fo the 215 Annual Computer Security Applications Conference,
2005 ; [retrieved on Sep. 13, 2011]; Retrieved from Internet <URL:ht

Using Speculation, Recovery, and Adaptive Retranslation to Address Real-Life Challenges, Appeared in the Proceedings for the First
Annual IEEE/ACM International Symposium on Code Generation

and Optimization, Mar. 27-29, 2003, San Francisco, CA, (2003),pp.

1-10.

tps:/ieeexplore.ieee.org/stamp/stampj sp?tp:&arnumber:
1565257>; pp. 1-9.*

Kiriansky, Vladimir et al., Secure Execution Via Program Shepherd ing, Originally Published in the Proceedings of the 11th USENIX

Jung, et al., Helper Thread Prefetching for Loosely-Coupled Mul tiprocessor Systems, 2006; [retrieved on Sep. 14, 2011]; Retrieved from Internet <URL:https:/ieeexplore.ieeeorg/stamp/stampjsp?tp:
&arnumber:1639375>; pp. 1-10.* Chen, et al., From Speculation to Security: Practical and Efficient

Security Symposium (Security 02), San Francisco, CA, Aug. 2002,

pp. 1-16.

INformation Flow Tracking Using Speculative Hardware, 2008

IEEE; [retrieved on Jul. 20, 2012]; Retrieved from Internet <URL : http: //ieeexpl ore .ieee .org/ stamp/ stamp .j sp?tp:&arnumber:

Newsome, James et al., Dynamic Taint Analysis for Automatic Detection, Analysis, and Signature Generation of Exploits on Com modity Software, pp. 1-17. Qin, Feng et al., LIFT: A Low-Overhead Practical Information Flow

Tracking System for Detecting Security Attacks, pp. 1-12.

Shetty, Rithin et al., HeapMon: a Low Overhead, Automatic, and

4556743>;pp. 401-412.* Lam, Chiueh, A General Dynamic INformation Flow Tracking Framework for Security Applications, 2006, IEEE; [retrieved on Jul. 20, 2012]; Retrieved from Internet <URL:http://ieeexplore.ieee.org/ stamp/ stamp.j sp?tp:&arnumber:404 1 190>;pp. 1-10.*
OZsoy, et al., SIFT: A Low-Overhead Dynamic Information Flow Tracking Architecture for SMT Processors, 2011 ACM; [retrieved on Jul. 20, 2012]; Retrieved from Internet <URL:http://dl.acm.org/

Programmable Memory Bug Detector, Appears in the Proceedings

of the First IBM PAC2 Conference, pp. 1-10.

Shi, Weidong et al., An Intrusion-Tolerant and Self-Recoverable Network Service System Using a Security Enhanced Chip Multipro
cessor, pp. 263-173. Suh, G. Edward et al., Secure Program Execution via Dynamic Information Flow Tracking, pp. 1-14. Vachharajani, Neil et al., RIFLE: An Architectural Framework for

citation.cfm?id:2016604>;pp. 1-11.* Chen, et al., Log-Based Architectures: Using Multicore to Help Software Behave Correctly, 2001, SIGOPS Operating Systems
Revew; [retrieved on Jul. 20, 2012]; Retrieved from Internet

User-Centric Information-Flow Security, Depts of Computer Sci

ence and Electrical Engineering; Princeton University, pp. 243 -254.

Chen, Shuo et al., Defeating Memory Corruption Attacks via

Pointer Taintedness Detection, pp. 1-10.

<URL:http://dl.acm.org/citation.cfm?id:1945023>;pp. 84-91.*

* cited by examiner

US. Patent

Nov. 27, 2012

Sheet 2 of3

US 8,321,840 B2

ORIGINAL OPERATION
200 2 Read lIVIem]

INFORMATION FLOW TRACKING OPERATION

Taint-vaIuelII/Iem] = 1

202 _,~ Load Regl, [Mem]

Taint-valuelRegl] = Taint-valuelMem]

2042 Reg2 = Regl + 2 206 2 Imp Reg2

Taint-valuelReg2l =Tainl-valuelReg1] If Taint-valuelRegZ] == 1 exception( I;

F I G. 2

200
SOURCE CODE /

220
MAIN THREAD CODE / TRACKING THREAD CODE

440
mov eax,<mern+oll.>
// delainting _ 454

void fun) ) { 470 . call <get> in) bu?lolchoice; 471\_/\ a. call sysiread
450 _,_ Choice = get) );

480 \a call <get> 451 \/\ mov <meni+off.>,1

472 __/~ b. mov eax, <mem> // in sysiread

// bounds checking
462 _,_ i?choice > 3) exi?n);

ICmD 98), 03h

ige <ex|t>
// spill code

mOV {96x9
R 474

5
_ 4&5
- 486

(receive branch outcome)

(receive esp value)

push eax R
- - 475

mov <esp'+off>, eax-3

call <gei>
476

464w bur = gerl I; // vulnerability call <get _ 2

// un-soilling

<5
_ 487

(receive esp value)

Switchlchoice): Case 1; F10;

460 Case 2;

non eax <1

477

add eax,ebp
(receive and check status) 475 _,~ imp eax
...

mov eax, <er>'+<>ff><-S //tracking or eaxebp

//checking _ 455

F2(); Case 3:
Fgl );

cmp eax,01h lnZ iabe'

raise exception

T1: call<f1>
T2: call<f2>

label:
. . .

T3: call <f3>

FIG. 4

US. Patent

Nov. 27, 2012

Sheet 3 of3

US 8,321,840 B2

500

SCAN INPUT PROGRAM AND CREATE f 510 THE MAIN AND TRACKING THREADS

DISPATCH THE THREADS TO DIFFERENT PROCESSOR CORES

COMPUTED VALUES NEED FOR INFORMATION
FLOW TRACKING _

1-520

MAIN THREAD RUN THE ORIGINAL

OPERATIONS AND

TRACKING THREAD RUN THE TRACKING

OPERATIONS AND

SEND NECESSARY

DETERMINE WHETHER

INFORMATION To THE "TWO-THEE"- A SECURITY POLICY

Tmmmnmm ?wmymmm swmmm

H
550

Iwmmn

\
540

FIG. 5

US 8,321,840 B2
1
SOFTWARE FLOW TRACKING USING MULTIPLE THREADS BACKGROUND

2
mentations, types and interrelationships of system compo
nents, and logic partitioning/ integration choices are set forth in order to provide a more thorough understanding of the present disclosure. It Will be appreciated, hoWever, by one
skilled in the art that embodiments of the disclosure may be

As computer systems become more complex, security is

becoming a greater concern. Authorization and privacy are tWo concerns Within the security domain. Authorization
issues are related to unauthorized access to computer systems

practiced Without such speci?c details. In other instances,

control structures, gate level circuits and full softWare instruc
tion sequences have not been shoWn in detail in order not to

or privilege escalation Within a system via exploitation of

holes in softWare. Privacy issues are related to access to

obscure the invention. Those of ordinary skill in the art, With the included descriptions, Will be able to implement appro

sensitive data and leaking of such data via access control

priate functionality Without undue experimentation.

References in the speci?cation to one embodiment, an

security holes or propagation. In an effort to resolve security issues, dynamic information How tracking has been used to protect systems from authori zation violations and compromised privacy. Such ?oW track

embodiment, an example embodiment, etc., indicate that

the embodiment described may include a particular feature,
structure, or characteristic, but every embodiment may not

ing is typically implemented using a hardWare-based approach. These approaches typically include additional
hardWare support for performing tracking of secure data
throughout its lifetime in a system. As an example, data may be tagged With a sensitivity level, Which may be located in the
20

necessarily include the particular feature, structure, or char acteristic. Moreover, such phrases are not necessarily refer
ring to the same embodiment. Further, When a particular feature, structure, or characteristic is described in connection With an embodiment, it is submitted that it is Within the knoWledge of one skilled in the art to effect such feature, structure, or characteristic in connection With other embodi
ments Whether or not explicitly described.
25

dedicated hardWare support. During program execution, the system dynamically propagates the sensitivity level for the tagged data and detects violations of user-speci?ed rules.

HoWever, by implementing dynamic information How track ing using a hardWare-based approach, legacy systems lacking such specialized hardWare cannot perform dynamic informa
tion ?oW tracking. Furthermore, there is added expense and computation complexity in performing a hardWare-based

Embodiments of the invention may be implemented in hardWare, ?rmWare, softWare, or any combination thereof.
Embodiments of the invention may also be implemented as
instructions stored on a machine-readable medium, Which may be read and executed by one or more processors. A

dynamic information How tracking process.

BRIEF DESCRIPTION OF THE DRAWINGS

30

machine-readable medium may include any mechanism for storing or transmitting information in a form readable by a

The invention described herein is illustrated by Way of example and not by Way of limitation in the accompanying

35

machine (e.g., a computing device). For example, a machine readable medium may include read only memory (ROM); random access memory (RAM); magnetic disk storage

?gures. For simplicity and clarity of illustration, elements

illustrated in the ?gures are not necessarily draWn to scale. For example, the dimensions of some elements may be exag

media; optical storage media; ?ash memory devices; and

others. Referring noW to FIG. 1, one embodiment of a computing device 100 is shoWn. The computing device 100 may include

gerated relative to other elements for clarity. Further, Where considered appropriate, reference labels have been repeated among the ?gures to indicate corresponding or analogous
elements. FIG. 1 shoWs an illustrative computing device having a

40 one or more processors 102 and a memory 104 coupled to a

chipset106.A mass storage device 112, a non-volatile storage (NV S) device 105, a netWork interface (UP) 114, and an

compiler for generating information How tracking code.

FIG. 2 shoWs illustrative information How tracking code
45

Input/Output (I/O) device 118 may also be coupled to the chipset 106. Embodiments of computing device 100 include,
but are not limited to, a desktop computer, a notebook com

generated by the compiler of FIG. 1.

FIG. 3 shoWs an illustrative process of the compiler of FIG.

1 for generating information How tracking code using a main thread and tracking thread. FIG. 4 shoWs illustrative information How tracking code
using a main thread and a tracking thread.
DETAILED DESCRIPTION OF THE DRAWINGS

50

puter, a server, a personal digital assistant, a netWork Work station, or the like. In one embodiment, the processor 102 may execute instructions stored in memory 104. The processors 102 may include, but are not limited to, processors manufactured or marketed by Intel Corp., IBM Corp., and Sun Microsystems Inc. In one embodiment, com

While the concepts of the present disclosure are suscep

55

tible to various modi?cations and alternative forms, speci?c exemplary embodiments thereof have been shoWn by Way of example in the draWings and Will herein be described in detail. It should be understood, hoWever, that there is no intent to limit the concepts of the present disclosure to the particular
forms disclosed, but on the contrary, the intention is to cover

puting device 100 may include multiple processors 102. The processors 102 may also include multiple processing cores 103. Thus, the computing device 100 may include multiple processing cores 103 for executing binary code of the com puting device 100 as a result of having multiple single core
processors 102, a single multi-core processor, and/or a com

60

bination of single core and multi-core processors 102. Fur thermore, each processing core 103 may support simulta neous execution of multiple threads. The memory 104 may include, but is not limited to,

all modi?cations, equivalents, and alternatives falling Within

the spirit and scope of the invention as de?ned by the

Dynamic Random Access Memory (DRAM), Static Random

appended claims.
In the folloWing description, numerous speci?c details such as logic implementations, opcodes, means to specify
65

Access Memory (SRAM), Synchronized Dynamic Random Access Memory (SDRAM), Rambus Dynamic Random
Access Memory (RDRAM), or the like. In one embodiment,
the memory 104 may include one or more memory units that

operands, resource partitioning/sharing/duplication imple

do not have to be refreshed.

US 8,321,840 B2
3
The chipset 106 may include a memory controller, such as

4
code such as C source code ?les to obtain compiled binary code for later execution by the computing device 100 or

a Memory Controller Hub (MCH), an input/output controller,

such as an Input/Output Controller Hub (ICH), or the like. In an alternative embodiment, a memory controller for memory

another computing device.

Whether the compiler 130 is implemented as a Just-In

104 may reside in the same chip as processor 102. The chipset 106 may also include system clock support, poWer manage ment support, audio support, graphics support, or the like. In one embodiment, chipset 106 is coupled to a board that includes sockets for processor 102 and memory 104. The components of computing device 100 may be con nected by various interconnects. In one embodiment, an inter connect may be point-to-point betWeen tWo components, While in other embodiments, an interconnect may connect more than tWo components. Such interconnects may include a Peripheral Component Interconnect (PCI), such as PCI

Time compiler, static compiler, and/or dynamic binary trans lator, the compiler 130 may generate code that results in

dynamic information How tracking. Dynamic information

How tracking generally tracks the How of data through the execution of the binary code in an attempt to guard against
malicious softWare attacks. An attacker may breach protec

tions of the computing device 100 through input channels of the computing device 100. The compiler 130 may generate
code that associates a taint value to each register and memory byte. The taint value may be implemented as a Boolean value

in Which a high value denotes that the corresponding object

(memory byte or register) is tainted and vice versa. In one embodiment, the compiler 130 may generate code that con siders input channels spurious and values derived from such input channels as tainted. The How of information from these tainted values is tracked and those values that are data depen
dent on such inputs are in turn marked tainted. Potential attacks are detected based upon the suspicious use of such
25

Express, a System Management bus (SMBUS), a LoW Pin Count (LPC) bus, a Serial Peripheral Interface (SPI) bus, an Accelerated Graphics Port (AGP) interface, or the like. I/O
device 118 may include a keyboard, a mouse, a display, a printer, a scanner, or the like.
20

The computing device 100 may interface to external sys tems through netWork interface 114. The netWork interface 114 may include, but is not limited to, a modem, a NetWork Interface Card (NIC), or other interfaces for coupling a com puting device to other computing devices. A carrier Wave

tainted values. Referring noW to FIG. 2, original code is shoWn in the left column and illustrative code the compiler 130 may generate

signal 123 may be received/transmitted by netWork interface

114. In the embodiment illustrated in FIG. 1, carrier Wave signal 123 is used to interface computing device 100 With a netWork 124, such as a Local Area NetWork (LAN), a Wide Area NetWork (WAN), the Internet, or any combination

to track operation of the original code is shoWn in the right column. Inparticular, the original code begins at line 200 With
30

a read operations that results in data received from a spurious input channel being stored at a memory location Mem. The

thereof. In one embodiment, network 124 is further coupled to a computing device 125 such that computing device 100
and computing device 125 may communicate over netWork 124. The computing device 100 also includes non-volatile stor
age 105 on Which ?rmWare and/ or data may be stored. Non
35

compiler 130 may generate ?oW tracking code shoWn at line

200 that updates a taint value associated With the memory location Mem to re?ect that the data stored at the memory

volatile storage devices include, but are not limited to, Read

Memory (ROM), Flash memory, Erasable Programmable Read Only Memory (EPROM), Electroni cally Erasable Programmable Read Only Memory (EE PROM), Non-Volatile Random Access Memory (NVRAM),
or the like.

Only

location Mem is tainted. As mentioned above, the compiler 130 may consider data received via input channels as spurious and therefore tainted since such input channels may provide a point of entry for malicious attacks. The original code at line 202 further loads the value stored
at the memory location Mem into a register Reg1. In response

40

to the original codes loading of register Reg1, the compiler

130 may generate tracking code at line 202 that updates a taint value associated With the register Reg1 to indicate that the value stored in the register Reg1 is tainted since the value in the register Reg1 is derived from the tainted value stored at memory location Mem. At line 204, the original code adds 2 to the tainted value of register Reg1 and stores the result in the

The mass storage 112 may include, but is not limited to, a

magnetic disk drive, such as a hard disk drive, a magnetic tape drive, an optical disk drive, or the like. It is appreciated that instructions executable by processor 102 may reside in mass storage 112, memory 104, non-volatile storage 105, or may
be transmitted or received via netWork interface 114.

45

register Reg2. The compiler 130 may generate tracking code

at line 204 that updates the taint value associate With the
50

In one embodiment, the computing device 100 may execute an Operating System (OS). Embodiments of an OS

include Microsoft WindoWs, the Apple Macintosh operat ing system, the Linux operating system, the Unix operating
system, or the like.

register Reg2 to indicate that the value of register Reg2 is tainted since the value of register Reg2 is derived from the tainted value of register Reg1. Furthermore, the original code at line 206 may attempt to jump to the execution point speci ?ed by the value of register Reg2. HoWever, the How tracking
code at line 206 may generate an exception to prevent the

The computing device 100 may also execute a compiler 130. In one embodiment, the compiler 130 may dynamically translate and optimiZe source code at runtime. For example, the compiler 130 may be implemented as part of a Java Virtual
Machine environment in Which Java source code ?les are

55

jump since compiler 130 generates ?oW tracking code that results in the computing device 100 determining that the target (i.e. value of register Reg2) of the execution point is
60

dynamically compiled and executed by the computing device 100 using Just-In-Time (J IT) compiler techniques. The com
piler 130 may also be implemented as part of a dynamic

tainted. In this manner, the compiler 130 may generate track ing code that may detect a potential security hole and invoke a proper response to the potential security breach. Further details of information How tracking are depicted in
FIG. 3 and FIG. 4. FIG. 3 shoWs a process that may be

binary translator that may read statically compiled native

code or byte code ?les and dynamically translate the code to

implemented by the compiler 130 to generate a main thread to

65

add functionality, compatibility, and/or optimiZations to the

code. The compiler 130 may also be implemented as part of a

execute an original program 300 and a tracking thread to track the operations of the main thread. FIG. 4 shoWs an illustrative

static compiler that reads, compiles and optimiZes source

code snippet 400 of the original program 300 and correspond

US 8,321,840 B2
5
ing main thread code 420 and tracking thread code 440 cre

6
betWeen the memory locations of the main thread 420 and the

ated by the compiler 130 from the illustrative code snippet

300.

As shown in FIG. 3, the compiler 130 at block 310 may scan the original program 400 and create main thread 420 and

tracking thread 440. In particular, the compiler 300 may gen

erate the main thread 420 such that the main thread 420

tracking thread 440. Thus, the above results in the taint value for each byte of the original address space of the main thread 420 being mapped to a byte of the address space of the tracking thread 440. In another embodiment, the taint value for each byte of the original address space of the main thread
420 is mapped to a one bit of the address of the tracking thread

comprises the operations speci?ed by the original program.

The compiler 300 may also generate the tracking thread 440
to track operations of the main thread 420. As discussed in more detail beloW, compiler 130 may further generate code for the main thread 420 and the tracking thread 440 that establish a communications channel via Which the main thread 420 and the tracking thread 440 may exchange data. In one embodiment, the compiler 300 may insert enqueue and

440. Such a mapping may increase the complexity in locating the taint value for a speci?c byte of the main thread 420 and

therefore possible introduce additional processing overhead.

HoWever, such a mapping may also greatly reduce the amount
of memory used to store the taint values.

Moreover, the tracking thread 440 at block 340 may also

notify the main thread 420 if any of the operations performed

by or to be performed by the main thread 420 violate a

dequeue operations into the main thread 420 and the tracking
thread 440 to pass values therebetWeen.

At block 320, the main thread 420 and tracking thread 440 may be dispatched to different processing cores 103 of the computing device 100. In one embodiment, the main thread 420 and tracking thread 440 are dispatched to different pro cessing cores 103 of the same processor 102; hoWever, it should be appreciated that the threads 420, 440 may be dis patched to different processors 102 for execution. In yet another embodiment, the threads 420, 440 are dispatched to a

20

speci?ed security policy of the computing device 100. One security policy that the tracking thread 440 may enforce is that arguments of control-?ow altering instructions (eg. reg ister indirect jumps, return targets) should not be input depen dent. In FIG. 2, this security policy corresponds to the check
done for the instruction Jmp Reg2, Where an exception is raised if Reg2 is tainted. To better understand the information How tracking code generation of the compiler 130 reference is made to FIG. 4 Which shoWs original C code 400, main thread code 420 (shoWn in assembly) to be executed by a processing core 103 of the computing device 100, and tracking thread code 440 (also in assembly) to be executed by another processing core 103 of the computing device 100. At 450 of the original code
400, a choice from a user is received. As shoWn at 460, the received choice results in the call of one of three different

25

single processing core 103 that provides multi-threaded sup port thus enabling e?icient concurrent execution of the
threads 420, 440 With a single processing core 103. As shoWn, the main thread 420 at block 330 performs the

original operations of the program 300. Furthermore, the main thread 420 may provide the tracking thread 440 With information that enables the tracking thread 440 to track the execution of the main thread 420. For example, the main thread 420 may provide the tracking thread 440 With register values of processing core 103 executing the main thread 420 that determine execution point targets of indirect jumps and/
or indirect calls of the main thread 420. The main thread 420

30

functions. Although the received input is validated at 462, the

main thread 420 still contains a buffer over?oW vulnerability
at 464.
35

The original code 400 at 450 indicates the computing

device is to get an input value from a user and assign the input value to the variable choice. The compiler 130 based upon this get of the original code 400 may generate a call to a get routine at 470 Which in turn results in the compiler 130 further generating a call to a sys_read routine at 471. The sys_read routine as shoWn at 472 results in the input value received from the user being stored at memory location <mem> and moved to the register eax of the main thread processing core

may also provide the tracking thread 440 With branch out come values of conditional jumps (e.g. taken/not taken bits) so the tracking thread 440 may folloW branches taken by the main thread 420. Furthermore, the main thread 420 may

40

provide the tracking thread 440 With addresses of register

based memory operations to that the tracking thread 440 may track such memory operations. Conversely, the tracking thread 440 at block 340 tracks the operations performed by the main thread 420 With the aid of the information received from the main thread 420. In par ticular, the tracking thread 440 may update taint values asso ciated With registers of the processing core 103 executing the main thread 420. In particular, the compiler 130 may generate the tracking thread 440 such that each register of the process ing core 103 that executes the tracking thread 440 holds the
45

103. Based upon this get of the original code 400, the compiler 130 further generates code for the tracking thread 440 Which enables the tracking thread to track the get operations of the main thread 420 and update taint values associated With registers and memory locations effected by

the get operation accordingly. In particular, the compiler

50

130 may generate a call to a get routine at 480 to track the

taint value for the corresponding register of the processing

core 103 that executes the main thread 420. For example, the

compiler 130 may generate the code of the tracking thread 440 such that the eax register of the tracking thread 440 holds
the taint value of the eax register of the main thread 440. The tracking thread 440 at block 340 may also update taint values associated With memory locations of the main thread

55

information How in the get routine at 470 of the main thread 420. The compiler 130 may further generate code at 481 that moves the value of 1 to the memory location <mem+off> in order to mark the corresponding memory location <mem> of the main thread 420 as tainted since the main thread 420
stores the user input value at the memory location <mem> as a result of the sys_read. The offset off refers to a linear

420. The compiler 130 may generate the code of the tracking thread 440 such that the tracking thread 440 stores taint values
for memory locations of the main thread 420 in a linear translated memory space of the tracking thread 440. In par

60

translation betWeen the original memory location <mem> of the main thread 420 and its corresponding memory location <mem+off> of the tracking thread 440 used to track the taint value for the memory location <mem>. Since the main thread
420 further stores the tainted value at memory location <mem> in the main thread processing core register eax, the

ticular, the compiler 13 0 may generate the tracking thread 440

such that tracking thread 440 stores taint values for each memory location Mem at memory location Mem+offset of the tracking thread 440 Where offset is a linear address offset
65

compiler 130 further generates code for the tracking thread

440 shoWn at 482 that moves the taint value for memory location <mem> to the tracking thread processing core reg

US 8,321,840 B2
7
ister eax, thus resulting in the taint value for the main thread processing core register eax indicating that the register eax is tainted. At 462, the original code 400 de?nes a boundary check for the variable choice. As a result of this boundary check, the compiler 130 generates code at 474 that results in the main thread 420 validating the input value stored in main thread processing core register eax and exiting if the input value is greater than or equal to the boundary limit of 3. The compiler 130 also generates code at 484 that results in the tracking thread 440 detainting the main thread processing core register eax by moving the value 0 to the tracking thread processing core register eax. Thus, tracking thread 440 marks the value stored by the main thread processing core register eax as being not tainted since the main thread 420 validates the value of the main thread processing core register eax. Also, as shoWn in FIG. 4, the tracking thread 440 receives the branch outcome of the main threads conditional jump to <exit>. The
tracking thread 440 may use the received branch outcome to

8
instruction set alloWs memory addressing With the base and index registers. Several memory operations use the base pointer register ebp as the base register, due to the use of local variables in functions. Similarly, stack operations use the

stack pointer register esp as the base register for addressing,

albeit implicitly. For compiler generated code, dynamic infor mation ?oW tracking operations involving these registers ebp,
esp are not frequent. Thus, in one embodiment, the tracking thread 440 maintains the actual values of stack pointer esp

and the base pointer ebp. Maintaining the actual values of these registers, reducing communications betWeen the main
thread 420 and the tracking thread 440 since the main thread 420 no longer needs to transfer the actual value of the stack

pointer esp for stack operations and the base pointer (ebp) for memory operations involving local variables.
While the disclosure has been illustrated and described in

detail in the draWings and foregoing description, such an illustration and description is to be considered as exemplary and not restrictive in character, it being understood that only
20

conditionally jump to corresponding code of the tracking

thread 440 in order to continue tracking the operations of the main thread 420. It should be appreciated that the compiler 130 may generate code (not shoWn) for the main thread 420 and the tracking thread 440 that sends the branch outcome
from the main thread 420 to the tracking thread 440 via a communications channel established betWeen the tWo threads. NoW consider the spill code at 475 of the main thread 420 Which stores the input value for choice of the processor reg

25

illustrative embodiments have been shoWn and described and that all changes and modi?cations that come Within the spirit of the disclosure are desired to be protected. What is claimed is: 1. A method comprising: executing operations of a program With a main thread, tracking the main threads execution of the operations of the program With a tracking thread dynamically gener ated by a compiler or a binary translator, updating, With the tracking thread, a taint value associated
With a value of the main thread to re?ect Whether the

ister eax on the stack at a memory location <esp> Which is 30

de?ned by the stack pointer register esp of the main thread processing core. The tracking code at 485 similarly spills the taint value associated With the main thread processor register
eax to a memory location <esp'+off>. Note that the corre

value is tainted, including updating a ?rst register of a ?rst core that executes the tracking thread With the taint value, the ?rst register associated With a ?rst register of
a second core that executes the main thread, the ?rst
35

sponding stack pointer register esp of the tracking thread

processing core in one embodiment contains the taint value of

register of the second core storing the value, the ?rst and
second cores being distinct cores, and

stack pointer register esp of the main thread processing core. Accordingly, for the tracking code to obtain the appropriate memory location for the taint value, the compiler 130 may generate the main thread 420 and the tracking thread 440 such that the value of the stack register esp is sent from the main thread 420 to the tracking thread 440.
Note that there is a buffer over?oW vulnerability at 476 due to another call to the get routine. If the call to the get routine results in the buffer buf over?owing into the variable choice the tracking of the get routine at 486 Would result in the variable choice being marked as tainted. Thus, When the

40

determining, With the tracking thread based upon the taint value, Whether use of the value by the main thread vio lates a speci?c security policy, the method further including de?ning a memory offset that correlates
memory locations of the main thread to memory loca

tions of the tracking thread, storing the value at a memory location of the main thread, and storing the taint
45

value at a memory location of the tracking thread that corresponds to the memory offset from the memory location of the main thread used to store the value.

variable choice is again brought into the main thread register

eax at 477 and its courresponding taint value is brought into the tracking thread register eax at 487, the main thread regis
ter eax is marked as tainted by the tracking thread register eax
if there Was a buffer over?oW as a result of the call to the get routine at 476.
50

2. The method of claim 1 further comprising: receiving the value as input to the program via the main

thread, and
determining that the value is tainted in response to the

tracking thread determining that the main thread

received the value as input. 3. The method of claim 1 further comprising: receiving an input value to the program via the main thread, updating, With the tracking thread, a taint value associated With the input value to indicate that the input value is

As shoWn at 478, the main thread 420 may perform an indirect jump to a memory location de?ned by the main thread processing register eax. The tracking thread 440 at 488 may check Whether the main thread processing register eax is tainted and notify the main thread 420 accordingly. As shoWn, the main thread 420 may receive the status check from the

55

tainted,
60

tracking thread 420. The compiler 130 may place code in the
main thread 420 that results in the main thread 420 taking some sort of protective action in response to the tracking thread 440 determining that the main thread 420 is attempt to jump to an execution point derived from a tainted value. It should be appreciated that various techniques may be
used to reduce the amount data transferred betWeen the main

65

deriving the value of the main thread from the input value, and determining that the value is tainted in response to the tracking thread determining that the main thread derived the value from the tainted input value. 4. The method of claim 1 further comprising: receiving an input value to the program via the main thread, updating, With the tracking thread, a taint value associated With the input value to indicate that the input value is

thread 420 and tracking thread 440. For example, the x86

tainted,

US 8,321,840 B2
10
validating the input value With the main thread, updating, With the tracking thread, the taint value associ
ated With the input value to indicate that the input value is not tainted in response to determining that the main
1 1. The machine readable medium of claim 1 0, Wherein the

plurality of instructions further result in the computing device

determining that a value of the main thread is tainted in response to the tracking thread determining that the main
5

thread validated the input value, deriving the value of the main thread from the input value after the main thread validated the input value, and updating, With the tracking thread, the taint value associ
ated With the value of the main thread to re?ect that the value is not tainted in response to the tracking thread determining that the main thread derived the value from
no tainted values.

thread received the value as input. 12. The machine readable medium of claim 1 0, Wherein the

plurality of instructions further result in the computing

device: receiving an input value to the program via the main thread,

updating, With the tracking thread, a taint value associated With the input value to indicate that the input value is

tainted,
deriving a value of the main thread from the input value, and determining that the value of the main thread is tainted in response to the tracking thread determining that the main thread derived the value from the tainted input value. 13. The machine readable medium of claim 1 0, Wherein the plurality of instructions further result in the computing device: creating a communication channel betWeen the main thread and the tracking thread, and sending data from the main thread to the tracking thread that permits the tracking thread to track operations of the main thread.

5. The method of claim 1 further comprising: dispatching the main thread and the tracking thread to a multi-threaded processing core of a computing device. 6. The method of claim 1 further comprising: dispatching the main thread to the ?rst core, and dispatching the tracking thread to the second core. 7. The method of claim 1 further comprising: sending the tracking thread a register value of the main thread associated With an execution point target of the main thread, and tracking execution How of the main thread With the track ing thread based upon the received execution point tar

20

25

get.
8. The method of claim 1 further comprising: sending the tracking thread a branch outcome of the main thread associated With a conditional jump, and tracking execution How of the main thread With the track ing thread based upon the received branch outcome. 9. The method of claim 1 further comprising: sending the tracking thread a memory address of the main thread associated With a register based memory opera
30

14. A computing device, comprising:

a ?rst processing core, a second processing core distinct from the ?rst processing
core,

a memory to store taint values, and

a machine readable medium comprising a plurality of

35

instructions, that in response to being executed, results in the computing device:

creating a main thread and a tracking thread for a program

tion, and tracking the register based memory operation of the main
thread With the tracking thread based upon the received
memory address.
40

such that the tracking thread tracks operations per formed by the main thread, updates taint values associ ated With a value of the main thread, including updating
a ?rst register of the ?rst processing core that executes

10. A non-transitory machine readable storage medium comprising a plurality of instructions, that in response to being executed, results in a computing device:
creating a main thread and a tracking thread for a program

the tracking thread With the taint value, the ?rst register
associated With a ?rst register of the second processing core that executes the main thread, the ?rst register of the
45

dynamically such that the tracking thread tracks opera tions performed by the main thread, updates a taint value associated With a value of the main thread, including
updating a ?rst register of a ?rst core that executes the

second processing core storing the value, and determin

ing based upon the taint value Whether use of the value

by the main thread violates a speci?ed security policy,

50

tracking thread With the taint value, the ?rst register

associated With a ?rst register of a second core that

executes the main thread, the ?rst register of the second core storing the value, the ?rst and second cores being distinct cores and determining based upon the taint value
Whether use of the value by the main thread violates a

de?ning a memory offset that correlates memory locations of the main thread to memory locations of the tracking thread, storing the value at a memory location of the main thread, and storing the taint value at a memory

location of the tracking thread that corresponds to the

memory offset from the memory location of the main thread used to store the value, dispatching the main thread to the second processing core

speci?ed security policy, and de?ning a memory offset

that correlates memory locations of the main thread to

memory locations of the tracking thread, storing the

value at a memory location of the main thread, and storing the taint value at a memory location of the track

ing thread that corresponds to the memory offset from

the memory location of the main thread used to store the

60

for execution, and dispatching the tracking thread to the ?rst processing core for execution. 15. The computing device of claim 14 Wherein a single processor comprises the ?rst processing core and the second
processing core. 16. The computing device of claim 14 Wherein a ?rst pro cessor comprises the ?rst processing core and a second pro cessor comprises the second processing core.

value,
dispatching the main thread to the second core for execu

tion, and
dispatching the tracking thread to the ?rst core for execu tion.

65

17. The computing device of claim 14 Wherein the plurality of instructions further result in the computing device deter
mining that a value of the main thread is tainted in response to

US 8,321,840 B2
11
the tracking thread determining that the main thread received
the value as input. and

12
deriving a value of the main thread from the input value,
determining that the value of the main thread is tainted in response t0 the tracking thread determining that the main thread derived the value from the tainted input Value
* * * * *

18, The computing device efelaim 14, wherein plurality of instructions further result in the computing device: receiving an input value to the program via the main thread, 5 updating, With the tracking thread, a taint value associated With the input value to indicate that the input value is
tainted,