podft: On Accelerating Dynamic Taint Analysis with
Precise Path Optimization
Zhiyou Tian∗ , Cong Sun∗ , Dongrui Zeng†+ , and Gang Tan‡
∗ State Key Lab of ISN, School of Cyber Engineering, Xidian University, China

Email: 21151213645@stu.xidian.edu.cn, suncong@xidian.edu.cn† Palo Alto Networks, Inc., Santa Clara, CA, USA
Email: dzeng@paloaltonetworks.com‡ The Pennsylvania State University, University Park, PA, USA
Email: gtan@psu.edu
Abstract—Dynamic taint analysis (DTA) has been widelyused in security applications, including exploit detection, data
provenance, fuzzing improvement, and information flow control.
Meanwhile, the usability of DTA is argued on its high runtime
overhead, causing a slowdown of more than one magnitude onlarge binaries. Various approaches have used preliminary static
analysis and introduced parallelization or higher-granularity
abstractions to raise the scalability of DTA. In this paper, we
present a dynamic taint analysis framework podft that definesand enforces different fast paths to improve the efficiency of
DBI-based dynamic taint analysis. podft uses a value-set analysis(VSA) to differentiate the instructions that must not be tainted
from those potentially tainted. Combining the VSA-based analysis
results with proper library function abstractions, we develop
taint tracking policies for fast and slow paths and implement
the tracking policy enforcement as a Pin-based taint tracker. The
experimental results show that podft is more efficient than thestate-of-the-art fast path-based DTA approach and competitive
with the static binary rewriting approach. podft has a highpotential to integrate basic block-level deep neural networks tosimplify fast path enforcement and raise tracking efficiency.

I.

I NTRODUCTION

Dynamic taint analysis (DTA), also known as dynamic
data-flow tracking (DDFT) or dynamic information-flow tracking (DIFT), is a program analysis technique that tracks selected data at runtime and checks specific tainted data forreaching sinks. Dynamic taint analysis can track system-wide
or application-level taints. The system-wide DTA approaches
are general but heavy-weighted tainting solutions that usuallydepend on virtual machine monitors [23], whole-system or
hardware emulators [12], [20], [41], [49]–[51], or FPGA [19],[28], [52]. Compared with the complicated hardware extensions and the system-level monitors or emulators, applicationlevel DTA is more flexible and pervasively used to investigate
the vulnerabilities of an independent program. In this scenario,
the tracking code can be instrumented during compilation[10], [14], [33], [36], [45] when source code is available, or+ Corresponding author

Workshop on Binary Analysis Research (BAR) 2023
3 March 2023, San Diego, CA, USA
ISBN 1-891562-84-3
https://dx.doi.org/10.14722/bar.2023.23010
www.ndss-symposium.org

instrumented on bytecode [21] or binaries [16], [18], [27], [29],[40], [42], [54].
Dynamic binary instrumentation (DBI) is promising intracking the runtime taint propagation across a process’s
memory space. Such approaches hold the tainting status of
suspicious data within tagging memory and virtual registers
and check at particular program execution points to decide if
specific runtime policies are enforced or violated. TaintCheck[40] uses Valgrind [39], and TaintTrace [16] uses DynamoRIO[13] to rewrite binaries for detecting various attacks. LIFT
[42] instruments binary with StarDBT [11] on Windows. It
first proposes to reduce the runtime overhead by the fast
paths and merged checks to simplify the instrumented taintoperations. libdft [5], [29] and its descendant reimplementation[8] are popular DBI-based taint tracking tools with a moderate
slowdown to the native execution. On generalizing the DBIbased taint tracking, efforts are made to model the implicit
flows [18], [27], the flows among distributed processes [31],or the taint propagations for different target ISAs [17].
Performance overhead is the prominent obstacle in using
dynamic taint analysis. At the software level, the potential
improvements come from two mostly orthogonal aspects.
First, the parallelization-based overhead mitigation offloads thetaint-tracking operations from the original program execution,
introducing parallelization over different CPU cores [24],[37], [38], [44] or hosts [43]. Second, hybrid analyses may
use static analysis to abstract the inlined taint propagation
operations from per instruction to a higher granularity [10],[22], [25], [26], [42], [47], [53]. The function-level summaries[26], [53] can abstract the taint computations and reduce
the overhead of instruction-level taint tracking. The libraryfunction abstractions [26] can be derived automatically withreachability analysis on the LLVM-PDG [7], [34] of the target
library and integrated into libdft. Jee et al. [25] use perbasic-block analysis to express the tainting behavior withan algebra. The optimized operations are aggregated into
maximized instrumentation units to minimize interference withthe target program. Fast path [10], [22], [42], [47] generally
instruments check-and-switch mechanisms at specific program
locations to ensure a switch to an efficient sub-trace execution
whose live variables are untainted. The original fast paths[42] are the code segments whose live-in and live-out states
are determined safe at their entry point. Saxena et al. [47]analyze the untainted local variables and registers using aOffline phaseof SDFT

modular stack analysis. Their fast path requires no tainting
for registers and only a write to clear the memory taint for
memory stores. Only memory loads are checked for a potential
switch to the slow path when the tainted data are loaded. Iodine[10] profiles representative executions to develop an efficient
predicated static taint analysis for the frequently-executed fast
path, but it will introduce high recovery cost at invariant
failures. Compared with the static fast paths, Taint Rabbit [22]generates the fast paths just-in-time even when the taints arepresented at in- and out-states of basic blocks. The efficiencyof their approach assumes the executions of a basic block arefrequently over the same taint state.

Function-level
policies
Pin-based
Tracker

DTA results

BPA-based CFG
Construction

Value-set analysis (VSA) [9] is a general-purpose static
analysis that over-approximates the values for each variable
at different program locations. Saxena et al. [47] first mentioned using value-set analysis to optimize dynamic dataflow tracking. However, they use a modular stack analysis
on a simple abstract domain instead of the high-cost VSA
on global and heap memory. TaintPipe [38] only uses VSA
to resolve the memory access scope specified by the path
predicate of straight-line code. S ELECTIVE TAINT [15] uses
value-set analysis to ensure a must-not-tainted instruction set
and taints only the instructions outside this set with static
binary rewriting. Although S ELECTIVE TAINT is very effectivein eliding uninvolved instructions, their static binary rewriting
technique may bloat the attack surface of binaries and confront
more scalability issues than DBI.

ICFG

Tracking policy
construction

VSA-based
tainted inst.
identification

MNT/May-tainted
instructions

Fig. 1.

Naive/Complex
fast path policies
As slow path
policies

Framework of podft (dashed block = usage of existing tools)

The contributions of this paper are summarized as follows:
1) We propose an efficient dynamic taint analysis framework
podft. We design a novel approach using the instructionlevel VSA results to build basic block-level tracking
policies for our framework’s naive and complex fast paths.
2) By enforcing the function- and basic block-level tracking policies with a Pin-based taint tracker and a priorstatic data-dependency analysis, our implementation outperforms the state-of-the-art DTA approach based on
fast paths [22] and is competitive with the static binary
rewriting approach [15].

This paper presents podft, a dynamic taint analysis framework that combines the VSA-based must-not-tainted (MNT
for short) instructions identification with a flexible fast-pathguided dynamic binary instrumentation approach for efficienttaint tracking. The runtime fast paths of podft are either on
the basic block level or the function level. These fast paths
can be divided into three categories. The function fast pathsummarizes the tainting behavior of frequently-used libraryfunctions. The naive fast path is on the basic blocks holding
only MNT instructions. The complex fast path is directed bya runtime tag memory checking at the entry of the hot andpotentially-tainted basic blocks. In contrast to these fast paths,
the rest basic blocks are decided on slow paths by podft.

II.

D ESIGN OF PODFT

This section depicts the framework of podft, including
the interprocedural control-flow graph construction, the static
analyses for the tracking policy construction and fast-slow path
differentiation, and the dynamic Pin-based taint tracking.
A. System Overview
podft is a hybrid taint tracking framework, as presented inFig. 1. Its static analysis uses the results of several existing
analyses to build the tracking policies for the later runtime
taint tracking. With the tracking policies, the Pin-based tracker
takes fast paths on demand to track the taints’ propagation at
runtime efficiently.

For high efficiency, podft uses static analysis to build thetracking policies used by the fast paths. We first derive thefunction-level policy by modeling the taint computation oflibrary functions with taint rules [26]. Then, for the usercode basic blocks, we use the value-set analysis [15] to divide
the instructions into MNT- or potentially-tainted instructions.
We derive the policy for naive fast paths on the basic blocks
of only MNT instructions. Considering the potentially-tainted
basic block as the one containing some potentially-tainted
instructions, the policy of complex fast path is enforced on the
hot potentially-tainted basic block when the tainted memory at
the block’s entry has no intersection with the static analyzed
memory locations used by the basic block. Such memory
locations are obtained by a static analysis similar to the Merged
Check of [42]. The runtime of podft takes these policies
to instrument only a limited number of potentially-tainted
instructions to track taints. Even if a slow path instead of acomplex fast path is taken for a potentially-tainted basic block,the instruction-level VSA results can still ignore tracking
specific MNT instructions in that basic block for efficiency.

First, podft uses BPA [32] to derive the indirect call targets
for the binary-level interprocedural control-flow graph (ICFG).
The ICFG is delivered to a value-set analysis [15] to derive
the must-not-tainted instruction set Iu . In this procedure, theinstruction operands’ value set is compared with the mustnot-tainted (MNT) value set. If some of the operand’s value
is potentially tainted, the unknown value propagates, and thedestination operand’s value set is removed from the MNT value
set. If all the operands’ value sets are MNT value sets, theinstruction is labeled as must-not-tainted instructions, and theMNT value set gets enlarged if the destination is concrete.
Then, podft’s tracking policy construction module traverses
the basic blocks of the ICFG to build the tracking policies forthe runtime Pin-based taint tracker (Section II-B). We build thebasic block-level fast path policy for the naive and complex fast
paths and hold the instruction-level policy for the instructions
on slow paths. Besides, we use the offline phase of [26] togenerate the taint rules from the C standard library functions’2

TABLE I.

T RACKING P OLICIES AND R ELATED P REDICATES FOR I NSTRUMENTATION

Policy Type

Policy applicable onnaive fast path

Bn = {bbl | bbl ∈ B − Bl ∧ ∀ins ∈ bbl.ins ∈ Iu }complex fast path{bbl | (bbl ∈ Bc ∪ Blo ) ∧ (TaintedMem(entry(bbl)) ∩ MergedDep(bbl) = ∅)},
s.t. Bc = {bbl | bbl ∈ B − Bl ∧ (It ∩ bbl ̸= ∅) ∧ Hot(bbl)} and Blo = {bbl | bbl ∈ Bl − {libc.so}}

slow path

Is = {bbl | bbl ∈ B − Bl ∧ (It ∩ bbl ̸= ∅) ∧ ¬Hot(bbl)} − Iu ;or instructions in {bbl | (bbl ∈ Bc ∪ Blo ) ∧ (TaintedMem(entry(bbl)) ∩ MergedDep(bbl) ̸= ∅)} − Iuvoid toy test ( int fd , char *buf, int size ){int read len = read(fd , buf , size ); // taint source
if ( read len > 0){
printf ("read data: %s\n", buf);for ( int i = 0; i<2; i++){buf[ i ] = i ;write (fd , buf[ i ], 1); // taint sink}}}int main(int argc , char *argv []){
char buffer [64] = {0};int fd = open(argv [1], O RDWR);
toy test (fd , buffer , 64);
return 0;}
Fig. 2.

Motivating Example

program dependency graph (PDG). The taint rules serve as
the function-level policies that abstract the taint computationof popular library functions.
Third, the Pin-based tracker of podft conducts the DBIbased dynamic taint analysis. We develop podft’s dynamic
analysis by extending the DTA tool libdft [5], [29], a Pintool
developed on top of the Intel DBI framework Pin [35]. podft’s
tracker instruments the binary program with proper analysis
routines based on the tracking policies (Section II-C). The
function-level policy guides the tracker to flip to a functionlevel taint computation during the execution of library functions. The basic block-level policies are enabled on the tracesof user code to take the naive fast path on MNT basic blocks
and the complex fast path when the hot potentially-tainted
basic blocks are decided untainted by a check on the tag
memory state at the block entry. For the basic blocks decided
tainted at runtime or potentially tainted but not frequently used,
the addresses of taint-involved instructions are used to guidethe tag operations along the slow paths.

Fig. 3.

Binary ICFG of the program in Fig. 2

tracking policies of complex fast paths are on Bc ∪ Blo . Bc
stands for the user-code basic blocks hot in execution andhave some potentially-tainted instructions. To generate Bc , in
our implementation, we determine a basic block as being hot
if executed more than once and all its instructions are in It .
The library’s basic blocks in Blo fall in the complex fast path
policy because the VSA-based analysis [15] cannot work on
the libraries. We can only assume the instructions in theselibrary basic blocks are potentially tainted. The applicabilityof complex fast-path policy is also decided by a runtime
condition. Specifically, for a basic block bbl, we use static
analysis to identify the entry-state memory and registers of bbl
that are data-depended by the memory or registers of bbl, i.e.,
MergedDep(bbl). Such entry-state memory and registers should
not intersect with the runtime tainted memory and registers at
bbl’s entry state, i.e., TaintedMem(entry(bbl)). If this runtime
condition is satisfied, we also ignore instrumenting the tag
operations for this basic block. Otherwise, the basic blocks in
Bc ∪ Blo are enforced with the slow path tracking policy that
instruments the instructions not in Iu . Besides, the slow path
policy applies to the potentially-tainted instructions in basic
blocks of (B − Bl ∪ Bn ∪ Bc ), i.e., Is .

B. VSA-based Tracking Policy Construction
The strategy of policy construction is based on the VSAbased instruction-level identification of the must-not-tainted
and potentially-tainted instructions, i.e., Iu and It in [15],respectively. Let B be the basic blocks of the program’s loaded
code and Bl be the basic blocks of the library functions.
Because our function-level tracking policy only applies to theC standard library, we distinguish the basic blocks of libc.sofrom the basic blocks of other libraries (Blo ).
The basic block-level tracking policies for fast paths andinstruction-level tracking policies for slow paths are presented
in Table I. The tracking policies of naive fast paths are on
basic blocks Bn . If a basic block is identified as in Bn , weignore instrumenting tag operations on all its instructions. The
3

Input: loaded imanges
1: for all image∈ loaded images do
2:
if image is libc.so then3:libc scope ← record scope(image);
4:
for all f unc ∈image do
5:
Instrumentfunc (entry(f unc), exit(f unc));6:
end for7:
else if image is other library then8:libs scope←record scope(image);9:
end if
10: end for
11: f laglibc ← 0;
12: for all trace@runtime do
13:
f laglibc ← (trace ∈ libc scope)?1 : 0;
14:
for all bbl ∈trace do
15:
if f laglibc ∨ bbl ∈ Bn then16:
skipTagOps(bbl);
17:
else if bbl ∈libs scope ∨bbl ∈ Bc then18:
if TaintedMem(entry(bbl))∩ MergedDep(bbl)=∅ then19:
skipTagOps(bbl);
20:
else
21:
for all ins ∈ bbl − Iu do
22:
Instrumentlibdft (ins);
23:
end for24:
end if25:
else {∀ins ∈ Is }26:
for all ins ∈ bbl − Iu do
27:
Instrumentlibdft (ins);
28:
end for29:
end if
30:
end for
31: end forFig. 4.

DBI algorithm is presented in Fig. 4. For all the loaded imagesof the program, we record and differentiate the virtual address
scopes of libc.so, other libraries, and user code. For the glibc
functions, podft instruments tag memory operations at thefunction’s entry and exit points based on the taint rules of [26](Instrumentfunc in Line 5). If the current trace is in libc.soor the current basic block is in Bn , we skip instrumenting
all instructions of this basic block. Otherwise, if the current
basic block is in other libraries or Bc , we decide if the basic
block is on a complex fast path or a slow one. Suppose theregisters and memory locations used in the basic block do notdepend on the tainted memory and registers at the entry stateof this basic block. In that case, we confirm the complex fast
path and skip instrumenting all its instructions. Otherwise, we
instrument all the potentially-tainted instructions with libdft’s
instruction-level instrumentation (Instrumentlibdft in Lines 22
and 27).
For the example in Fig. 3, the C standard library function
printf is instrumented at the function level. The basic
blocks of printf need no instrumentation at the instruction level. open, read, and write are system calls modeled by the I/O interface of libdft. The memory involvedin the basic block 0x8048541, i.e., buf[0] and buf[1]pointed by *[ebp+0xc], are sanitized with the constant of iheld in [ebp-0x10]. Therefore MergedDep(bbl0x8048541 ) =∅ at the entry of basic block 0x8048541. We have
MergedDep(bbl0x8048541 ) ∩ TaintedMem(0x8048541) = ∅ atruntime when reaching 0x8048541. The memory locations
used in this basic block have no data dependence with thetainted memory buf at the entry state of this basic block.
Thus, the basic block 0x8048541 is decided to be a complex
fast path, and all its instructions are not instrumented.

Algorithm for Tracker’s Dynamic Binary InstrumentationIII.

I MPLEMENTATION AND E VALUATIONThis section presents several important issues in our implementation and evaluates podft’s efficiency and effectiveness.

Taking the program in Fig. 2 for example, read is ataint source that reads file fd’s input as taints to buf. The
function toy_test prints buf, modifies the tainted buf[0]and buf[1] with constants in the for-loop, and delivers theuntainted buf[0..1] to the taint sink write to modify
the file. Thus, the data delivered to the sink are irrelevant to
the tainted data from the source. This secure program helps
illustrate the complex fast path decision. The binary ICFG of
the program is presented in Fig. 3. The red code locationsin Fig. 3 stand for the potentially-tainted instructions, andthe rest are the MNT instructions identified by the VSAbased analysis. The PLT instructions (e.g., at 0x80483a0 for
printf) are not tainted. The basic blocks with no potentiallytainted instruction, e.g., the one at 0x804857f, are in Bn for
the naive fast paths. The basic block at 0x8048541 is executed
twice and is in Bc to indicate a tentative complex fast path.
Whether the basic block at 0x8048541 can take a complex
fast path or a slow one is decided by the runtime checking on
TaintedMem(0x8048541) ∩ MergedDep(bbl0x8048541 ). Besides,
the potentially-tainted instructions in the basic blocks like
0x80484fd are in Is to take the slow-path policy.

A. Implementation Issues

C. Pin-based Taint Tracking

Finding the hot potentially-tainted basic blocks is criticalto the decision of Bc and Is . In our implementation, a basic
block is hot when executed more than once under the standard
inputs, and all its instructions are potentially tainted. Therefore,
we use another DBI execution over the standard inputs to
identify the basic blocks executed more than once. Afterall, specifying a hot basic block is configurable and standalone prior to the DTA procedure. This instrumented execution
also helps us to profile the related inputs and outputs of the
hot basic blocks used in training the neural hot basic blockmodel, as depicted in Section IV. podft holds a hashmap tofacilitate efficient inclusion decisions in Fig. 4. The hashmap isgenerated using the results of VSA-based analysis identifying
MNT- and potentially-tainted instructions. Each key of thehashmap is the address of a potentially-tainted basic block.
Each value of the hashmap points to an instruction-address
array of potentially-tainted instructions in the basic block.
Queries on this structure can efficiently decide Bc , Is , and Bn
for tracking policy enforcement.

The Pin-based tracker of podft is developed by extending
libdft to skip instrumenting specific traces, basic blocks, or
instructions according to the tracking policies in Table I. The

Another issue is deciding the complex fast path using static
analysis to find the data dependencies between the memory/registers used by the basic block and the memory/register
4

TABLE II.
Dataset ID
S1
S2
S3

B ENCHMARK P ROGRAMS

S2, podft achieves slowdowns of 1.6x to 27.9x with an averageslowdown of 10.6x. In contrast, the state-of-the-art fast-pathbased tool, i.e., Taint Rabbit, has a 30x average slowdown for
its TR-ID policy configuration and a 120x average slowdown
for the TR-BV policy configuration. We can see that on eachbenchmark in Table III, podft outperforms other DTA tools.
According to the average slowdowns, podft is more efficientthan the other DTA tools. More specifically, TaintRabbit-BV
reaches a timeout when tracking 429.mcf. Dytan cannot finish
the instrumented execution of 458.sjeng properly. Triton isrelatively inefficient, reaching timeouts on dataset S1 and fourbenchmarks of S2.

Description
10 SPEC CPU 2k6 benchmarks
3 server programs, i.e., Nginx (1.22.0), Apache httpd (2.4.7),
and MySQL (5.5.62)
9 CVE programs, as presented in Table V

at the block’s entry. By reimplementing the Merged Checkof [42], we scan the traces of instructions and build the data
dependencies for each memory reference. We use a fix-depth
backward data-dependency graph traversal from the in-block
memory references to find all the data dependencies to thebasic block’s entry memory locations. Then at runtime, a basic
block entry check can decide if such entry memory locations
have been tainted in the tag memory of podft.

Then, because podft uses the VSA-based static analysis of
S ELECTIVE TAINT [15], we compare the efficiency of podft
with this static binary rewriting approach. To deploy thetools provided by S ELECTIVE TAINT, we deploy both theS TATIC TAINTA LL and the S ELECTIVE TAINT system. S TATIC TAINTA LL system instruments all the instructions with static
taint analysis. First, we confront difficulties using S ELEC TIVE TAINT’s static rewriting on the server binaries of dataset
S2. Therefore we only use the benchmarks in S1 for thisevaluation. On dataset S1, podft has an average slowdown of
12.5x, while S TATIC TAINTA LL and S ELECTIVE TAINT report
average slowdowns of 39.1x and 27.1x, respectively. S ELEC TIVE TAINT reduces the slowdowns of S TATIC TAINTA LL in all
the S1 benchmarks. Although podft is generally more efficientthan S ELECTIVE TAINT on S1, we observe that in several
cases, e.g., 400.perlbench and 429.mcf, S ELECTIVE TAINT canoutperform podft.

B. Dataset and Experimental Settings
Our experiments are conducted on a Desktop with a
2.8GHz×4 Intel Core(TM) i7-7700HQ CPU, 8GB RAM,and Linux 3.16.0 kernel (Ubuntu 14.04 32-bit). The DBI
framework is Pin v2.14, and libdft we used is [5]. Because
the VSA-based MNT instructions identification [15] can only
work on 32-bit binaries, we adapt the function-level taintrule generation [26], developed on libdft64 [8] for 64-bit
binaries, to the 32-bit libdft [5]. The main adaption work is
to reimplement the tag operations used by each taint rule.
The benchmarks we use to evaluate podft are presented
in Table II. We compile the binaries of these benchmarks ontheir default compiler optimization level. For the performance
evaluation, we use the standard working task in the DBI
execution of each benchmark program of dataset S1 and S2.
Specifically, for the SPEC2k6 benchmarks of dataset S1, we
use the standard SPEC2k6 workload test in the instrumented
execution. For httpd and Nginx in dataset S2, we use thebenchmarking tool ab [1] to randomly select and deliver
10,000 and 100,000 requests to the servers. For MySQL, we
use the load emulation tool mysqlslap [2] to connect the
MyISAM [4] and InnoDB [3] storage engines of MySQL,
automatically generate a complicated table, and issue 1,000
related SQL queries with 10 parallel clients. The dataset S3
is mostly collected from the related work [15]. We ensurethat the vulnerabilities of these CVEs are reproduced in our
experimental environment.

We also compare the basic block-level instrumentation
coverage of podft’s DBI and S ELECTIVE TAINT’s static binary rewriting on dataset S1 and the standard workload. We
observed that podft has an average instrumentation coverageof 40.38%, while S ELECTIVE TAINT’s average instrumentation
coverage is 53.73%. S ELECTIVE TAINT statically instruments
many basic blocks that are unreachable by the benchmark
executions. We cannot compare the runtime reachable basic
blocks of S ELECTIVE TAINT-rewritten binaries with the podftinstrumented basic blocks because the static rewriting has
introduced additional code structures into the binary.
D. Effectiveness of podft’s Dynamic Taint Analysis
We validate the effectiveness of podft by tracking the realworld vulnerabilities of CVEs triggered by public exploits. The
CVEs and the tracking time of podft are presented in Table V.
podft’s taint tracking can successfully detect the sensitiveflow-related exploits of all these CVEs. For each CVE, wedevelop a specific Pintool over podft to track the vulnerability.
To retrieve the taint sources, we identify the target binary’s
specific syscalls, functions, or program arguments. We also
treat the user input as taint sources in the cases where the taintsource is unspecified by the CVE. We identify the taint sinkby manually analyzing the assembly code and investigating thevulnerable functions reported by the CVEs. We analyze thesuspicious variables and the instructions that operate on thesevariables in these functions. Consequently, the instrumented
check decides if such a variable holds a taint tag at these instructions’ locations. We observed that the tracking procedureof podft tainted all the vulnerable sinks.

C. Efficiency of podft
We first compare podft’s efficiency with other dynamic
taint analysis approaches, including Taint Rabbit [22], Dytan[6], [18], Triton [46], and Taintgrind [30]. Taint Rabbit isdeveloped on DynamoRIO [13], and Taintgrind is on Valgrind[39]. Dytan and Triton use Pin as used by podft. For deploying
the related tools, we deploy Taint Rabbit with the taint policy
TaintRabbit-ID (TR-ID) and TaintRabbit-BV (TR-BV). For afair comparison, we set the same taint sources and sinks foreach tool.
The results are presented in Table III. Besides the execution
time of the instrumented benchmark programs tracked by different tools, the slowdown metric of each tool (SD in Table III)measures the magnification of each tool’s instrumentation costcompared with the original execution. For the dataset S1 and
5TABLE III.

Benchmark400.perlbench
401.bzip2
429.mcf
445.gobmk
456.hmmer
458.sjeng
462.libquantum
464.h264ref
471.omnetpp
473.astar
mysqlslap myisam
mysqlslap innodb
httpd req 10k
httpd req 100k
Nginx req 10k
Nginx req 100k
Avg. slowdown

TABLE IV.

Benchmark400.perlbench
401.bzip2
429.mcf
445.gobmk
456.hmmer
458.sjeng
462.libquantum
464.h264ref
471.omnetpp
473.astar
Avg. slowdown

P ERFORMANCE I MPROVEMENT OF PODFT C OMPARED WITH OTHER DTA A PPROACHES ON DATASET S1 AND S2. S LOWDOWNSD TOOL =TTOOL /TORIG , S . T. TOOL = PODFT , TAINT R ABBIT-ID, TAINT R ABBIT-BV, TAINTGRIND , DYTAN , T RITON
podft
Tpodft (s)SDpodft
120.1
27.9
46.4
8.6
5.2
2.1
128.2
8.4
55.6
25.3
28.3
6.2
3.6
7.2
191.8
15.2
9.1
22.8
14.5
1.6
4.5
7.5
4.9
7.0
5.3
8.8
27.4
5.6
5.5
11.0
20.1
4.8
–
10.6

Torig
(s)
4.3
5.4
2.5
15.3
2.2
4.6
0.5
12.6
0.4
9.1
0.6
0.7
0.6
4.9
0.5
4.2

TaintRabbit-ID
TID (s)
SDID
126.6
29.4
85.7
15.9
34.2
13.7
219.2
14.3
74.8
34.0
34.9
7.6
6.8
13.6
762.3
60.5
54.6
136.5
129.6
14.2
27.5
45.8
28.8
41.1
11.7
19.5
39.8
8.1
9.8
19.6
24.7
5.9
–
30.0

TaintRabbit-BV
TBV (s)
SDBV
204.9
47.7
91.3
16.9
Timeout
N/A
204.7
13.4
78.5
35.7
39.2
8.5
8.2
16.4
2,588.7
205.5
54.1
135.3
129.2
14.2
404.2
673.7
392.3
560.4
15.9
26.5
74.4
15.2
11.7
23.4
32.8
7.8
–
120.0

P ERFORMANCE C OMPARISON OF PODFT WITH
S ELECTIVE TAINT
podft
SDpodft
27.9
8.6
2.1
8.4
25.3
6.2
7.2
15.2
22.8
1.6
12.5

S TATIC TAINTA LL
TAll (s)
SDAll
26.8
6.2
263.1
48.7
39.1
15.6
543.4
35.5
161.4
73.4
126.8
27.6
6.3
12.6
1,255.9
99.7
16.4
41.0
277.4
30.5
–
39.1

IV.

Program
Zydis v3.2.0
SoX v14.4.2
dcraw v9.28
ngiflib v0.4
jhead v3.00
Gravity v0.3.5
MP3Gain v1.5.2
Nginx v1.4.0

S ELECTIVE TAINT
TSelect (s)SDSelect
24.2
5.6
174.1
32.2
3.8
1.5
538.5
35.2
129.2
58.7
94.8
20.6
4.5
9.0
801.2
63.6
14.9
37.3
61.7
6.8
–
27.1

Type
H-OF
H-OF
S-OF
S-OF
H-OF
S-OF
S-OF
S-OF

Dytan
TDytan (s)SDDytan
3,208.6
746.2
20,812.6
3,854.2
2,845.4
1,138.2
45,147.5
2,950.8
11,531.6
5,241.6
Failed
N/A
333.2
666.4
81,798.6
6,492.0
1,401.5
3,503.8
19,525.1
2,145.6
951.9
1,586.5
999.1
1,427.3
227.6
379.3
2,386.9
487.1
201.1
402.2
2,062.3
491.0–
2,100.8

TritonTTriton (s)SDTriton
Timeout
N/A
Timeout
N/A
Timeout
N/A
Timeout
N/A
Timeout
N/A
Timeout
N/A
Timeout
N/A
Timeout
N/A
Timeout
N/A
Timeout
N/A
Timeout
N/A
Timeout
N/A
40,509.2
67,515.3
Timeout
N/A
33,671.6
67,343.2
Timeout
N/A–
67,429.3

2) In several cases, the data-dependency analysis may need
to be more precise in identifying the block-used memoryreferences. In such cases, the hot basic blocks must be
overly approximated as slow paths.
The above limitations motivate us to develop a morescalable complex fast path policy enforcement approach. Our
solution is to use deep neural networks to track taints at thebasic-block level. Since we can identify the hot potentiallytainted basic blocks, these basic blocks are more frequently
executed and have more inputs and outputs. We can use thefuzzing technique to profile the runtime tag memory relations
between the inputs and outputs. Because these hot basic blocks
only use a limited number of memory and registers, such
relations can be properly abstracted and are not expected overcomplicated.

TABLE V.
E FFECT OF PODFT ON T RACKING V ULNERABILITIES OF
CVE S (S-OF=S TACK OVERFLOW, H-OF=H EAP OVERFLOW )ID
CVE-2021-41253
CVE-2019-8354
CVE-2018-19655
CVE-2018-11575
CVE-2018-6612
CVE-2017-1000437
CVE-2017-14411
CVE-2013-2028

Taintgrind
TTaintgrind (s)SDTaintgrind
346.7
80.6
1,634.9
302.8
193.6
77.4
6,039.4
394.7
998.6
453.9
1,355.8
294.7
22.9
45.8
5,057.7
401.4
259.6
649.0
1,467.4
161.3
77.5
129.2
73.8
105.4
26.7
44.5
219.3
44.8
23.9
47.8
196.4
46.8
–
205.0

Tpodft (s)
1.4
2.8
1.7
1.4
1.2
9.8
2.2
1.1

Taking the principle of Neutaint [48], we are trying to train
neural hot basic block embeddings using these tag memory
relations. Unlike Neutaint, which uses only dynamic program
embedding, our neural hot basic block embedding will also
consider several instruction-level static features to merge thetaint-tracking prediction of different hot basic blocks into one
deep model for each binary program. Integrating our design
into podft can avoid differentiating complex fast paths fromslow paths on hot basic blocks, thus avoiding the static datadependency analysis. Moreover, compared with Neutaint’s
program-level embeddings, our basic block-level embeddings
are more flexible to be used in traditional DTA infrastructures.
We also plan to develop more dynamic neural library-function
embeddings to optimize the tainting abstraction of [26] and thefunction-level policy enforcement of podft. Another subsistentissue we need to resolve is that several static code features areused in our neural basic block embeddings, making our deepmodel correlate more with the compiler options of the binary
than Nuetaint’s model.

W ORK -I N -P ROGRESS

podft is a dynamic taint analysis framework that enforces
multiple fast-path tracking policies for efficient taint tracking.
podft uses a VSA-based analysis and function-level tainting
abstraction to generate these tracking policies. We use a basic
block-level static data-dependency analysis to decide whether a
hot potentially-tainted basic block takes a complex fast path ora slow path. Such analyses benefit the taint tracking efficiency
but still have several limitations:1) The VSA-based analysis [15] cannot work on librarycode. The function-level summaries [26] work only
for popular library functions. Thus, we must overapproximate most library basic blocks as all-instructiontainted slow paths to enforce instruction-level slow-pathtracking policy.

ACKNOWLEDGMENT
Zhiyou Tian and Cong Sun were supported by the National
Natural Science Foundation of China (62272366) and the Key
Research and Development Program of Shaanxi (2023-YBGY371).
6

R EFERENCES
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]
[19]

[20]

[21]

[22]

[23]

[24]

[25]

“ab - Apache HTTP server benchmarking tool.” [Online]. Available:
https://httpd.apache.org/docs/2.4/programs/ab.html“mysqlslap — A Load Emulation Client.” [Online]. Available:
https://dev.mysql.com/doc/refman/8.0/en/mysqlslap.html“The InnoDB Storage Engine.” [Online]. Available: https://dev.mysql.
com/doc/refman/5.7/en/innodb-storage-engine.html“The MyISAM Storage Engine.” [Online]. Available: https://dev.mysql.
com/doc/refman/8.0/en/myisam-storage-engine.html“libdft,” 2012-2022. [Online]. Available: https://gitlab.com/brown-ssl/
libdft/“Dytan Taint Analysis Framework on Linux 64-bit,” 2014. [Online].
Available: https://github.com/behzad-a/Dytan“Program Dependence Graph in LLVM,” 2017. [Online]. Available:
https://bitbucket.org/psu soslab/program-dependence-graph-in-llvm“libdft64,” 2019. [Online]. Available: https://github.com/AngoraFuzzer/
libdft64
G. Balakrishnan and T. W. Reps, “Analyzing memory accesses in x86
executables,” in CC’04, ser. LNCS, vol. 2985. Springer, 2004, pp.
5–23.
S. Banerjee, D. Devecsery, P. M. Chen, and S. Narayanasamy, “Iodine:
Fast dynamic taint tracking using rollback-free optimistic hybrid analysis,” in SP’19. IEEE, 2019, pp. 490–504.
E. Borin, C. Wang, Y. Wu, and G. Araujo, “Software-based transparent
and comprehensive control-flow error detection,” in CGO’06. IEEE,
2006, pp. 333–345.
E. Bosman, A. Slowinska, and H. Bos, “Minemu: The world’s fastest
taint tracker,” in RAID’11, ser. LNCS, vol. 6961. Springer, 2011, pp.
1–20.
D. Bruening, “Efficient, transparent, and comprehensive runtime code
manipulation,” Ph.D. dissertation, Massachusetts Institute of Technology, 2004.
W. Chang, B. Streiff, and C. Lin, “Efficient and extensible security
enforcement using dynamic data flow analysis,” in CCS’08. ACM,
2008, pp. 39–50.
S. Chen, Z. Lin, and Y. Zhang, “SelectiveTaint: Efficient data flow tracking with static binary rewriting,” in 30th USENIX Security Symposium.
USENIX Association, 2021, pp. 1665–1682.
W. Cheng, Q. Zhao, B. Yu, and S. Hiroshige, “TaintTrace: Efficient
flow tracing with dynamic binary rewriting,” in ISCC’06. IEEE, 2006,
pp. 749–754.
Z. L. Chua, Y. Wang, T. Baluta, P. Saxena, Z. Liang, and P. Su,“One engine to serve ’em all: Inferring taint rules without architectural
semantics,” in NDSS’19. The Internet Society, 2019.
J. A. Clause, W. Li, and A. Orso, “Dytan: a generic dynamic taintanalysis framework,” in ISSTA’07. ACM, 2007, pp. 196–206.
M. Dalton, H. Kannan, and C. Kozyrakis, “Raksha: a flexible information flow architecture for software security,” in ISCA’07. ACM, 2007,
pp. 482–493.
A. Ermolinskiy, S. Katti, S. Shenker, L. Fowler, and M. McCauley,“Towards practical taint tracking,” UCB/EECS-2010-92, UC Berkeley,
Tech. Rep., 2010.
X. Fu and H. Cai, “FlowDist: Multi-staged refinement-based dynamic
information flow analysis for distributed software systems,” in 30th
USENIX Security Symposium. USENIX Association, 2021, pp. 2093–
2110.
J. Galea and D. Kroening, “The Taint Rabbit: Optimizing generic taintanalysis with dynamic fast path generation,” in ASIA CCS ’20. ACM,
2020, pp. 622–636.
A. Ho, M. A. Fetterman, C. Clark, A. Warfield, and S. Hand, “Practical
taint-based protection using demand emulation,” in EuroSys’06. ACM,
2006, pp. 29–41.
K. Jee, V. P. Kemerlis, A. D. Keromytis, and G. Portokalidis, “ShadowReplica: efficient parallelization of dynamic data flow tracking,” in
CCS’13. ACM, 2013, pp. 235–246.
K. Jee, G. Portokalidis, V. P. Kemerlis, S. Ghosh, D. I. August,and A. D. Keromytis, “A general approach for efficiently accelerating

[26]

[27]

[28]

[29]

[30]
[31]

[32]
[33]

[34]
[35]

[36]

[37]
[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

7

software-based dynamic data flow tracking on commodity hardware,”in NDSS’12. The Internet Society, 2012.
X. Kan, C. Sun, S. Liu, Y. Huang, G. Tan, S. Ma, and Y. Zhang, “Sdft:
A PDG-based summarization for efficient dynamic data flow tracking,”
in QRS’21. IEEE, 2021, pp. 702–713.
M. G. Kang, S. McCamant, P. Poosankam, and D. Song, “DTA++:
dynamic taint analysis with targeted control-flow propagation,” in
NDSS’11. The Internet Society, 2011.
H. Kannan, M. Dalton, and C. Kozyrakis, “Decoupling dynamic information flow tracking with a dedicated coprocessor,” in DSN’09. IEEE,
2009, pp. 105–114.
V. P. Kemerlis, G. Portokalidis, K. Jee, and A. D. Keromytis, “libdft:
practical dynamic data flow tracking for commodity systems,” inVEE’12. ACM, 2012, pp. 121–132.
W. M. Khoo, “Taintgrind: a Valgrind taint analysis tool,” 2012.
[Online]. Available: https://github.com/wmkhoo/taintgrind
H. C. Kim, A. D. Keromytis, M. Covington, and R. Sahita, “Capturing information flow with concatenated dynamic taint analysis,” in
ARES’09. IEEE, 2009, pp. 355–362.
S. H. Kim, C. Sun, D. Zeng, and G. Tan, “Refining indirect call targets
at the binary level,” in NDSS’21. The Internet Society, 2021.
L. Lam and T. Chiueh, “A general dynamic information flow tracking
framework for security applications,” in ACSAC’06. IEEE, 2006, pp.
463–472.
S. Liu, G. Tan, and T. Jaeger, “PtrSplit: Supporting general pointers in
automatic program partitioning,” in CCS’17, 2017, pp. 2359–2371.
C. Luk, R. S. Cohn, R. Muth, H. Patil, A. Klauser, P. G. Lowney, S. Wallace, V. J. Reddi, and K. M. Hazelwood, “Pin: building customized
program analysis tools with dynamic instrumentation,” in PLDI’05.
ACM, 2005, pp. 190–200.
S. Mallissery, Y. Wu, C. Hsieh, and C. Bau, “Identification of data
propagation paths for efficient dynamic information flow tracking,” inSAC’20. ACM, 2020, pp. 92–99.
J. Ming, D. Wu, J. Wang, G. Xiao, and P. Liu, “StraightTaint: decoupledoffline symbolic taint analysis,” in ASE’16. ACM, 2016, pp. 308–319.
J. Ming, D. Wu, G. Xiao, J. Wang, and P. Liu, “TaintPipe:pipelined symbolic taint analysis,” in 24th USENIX Security Symposium.
USENIX Association, 2015, pp. 65–80.
N. Nethercote and J. Seward, “Valgrind: A program supervision framework,” Electron. Notes Theor. Comput. Sci., vol. 89, no. 2, pp. 44–66,
2003.
J. Newsome and D. X. Song, “Dynamic taint analysis for automatic
detection, analysis, and signature generation of exploits on commodity
software,” in NDSS’05. The Internet Society, 2005.
G. Portokalidis, A. Slowinska, and H. Bos, “Argos: an emulator for
fingerprinting zero-day attacks for advertised honeypots with automatic
signature generation,” in EuroSys’06. ACM, 2006, pp. 15–27.
F. Qin, C. Wang, Z. Li, H. Kim, Y. Zhou, and Y. Wu, “LIFT: A
low-overhead practical information flow tracking system for detecting
security attacks,” in MICRO-39. IEEE, 2006, pp. 135–148.
A. Quinn, D. Devecsery, P. M. Chen, and J. Flinn, “JetStream:cluster-scale parallelization of information flow queries,” in OSDI’16.
USENIX Association, 2016, pp. 451–466.
O. Ruwase, P. B. Gibbons, T. C. Mowry, V. Ramachandran, S. Chen,
M. Kozuch, and M. P. Ryan, “Parallelizing dynamic information flow
tracking,” in SPAA’08. ACM, 2008, pp. 35–45.
G. Ryan, A. Shah, D. She, K. Bhat, and S. Jana, “Fine grained dataflow
tracking with proximal gradients,” in 30th USENIX Security Symposium.
USENIX Association, 2021, pp. 1611–1628.
F. Saudel and J. Salwan, “Triton: A dynamic symbolic execution framework,” in Symposium sur la sécurité des technologies de l’information
et des communications, ser. SSTIC, Rennes, France, Jun. 2015, pp. 31–
54.
P. Saxena, R. Sekar, and V. Puranik, “Efficient fine-grained binary
instrumentationwith applications to taint-tracking,” in CGO’08. ACM,
2008, pp. 74–83.
D. She, Y. Chen, A. Shah, B. Ray, and S. Jana, “Neutaint: Efficient
dynamic taint analysis with neural networks,” in SP’20. IEEE, 2020,
pp. 1527–1543.

[49]

[50]

[51]

[52]

[53]

[54]

G. E. Suh, J. W. Lee, D. Zhang, and S. Devadas, “Secure program
execution via dynamic information flow tracking,” in ASPLOS’04.
ACM, 2004, pp. 85–96.
N. Vachharajani, M. J. Bridges, J. Chang, R. Rangan, G. Ottoni, J. A.
Blome, G. A. Reis, M. Vachharajani, and D. I. August, “RIFLE: anarchitectural framework for user-centric information-flow security,” in
MICRO-37. IEEE, 2004, pp. 243–254.
H. Yin, D. X. Song, M. Egele, C. Kruegel, and E. Kirda, “Panorama:
capturing system-wide information flow for malware detection andanalysis,” in CCS’07. ACM, 2007, pp. 116–127.
N. Zeldovich, H. Kannan, M. Dalton, and C. Kozyrakis, “Hardware
enforcement of application security policies using tagged memory,” in
OSDI’08. USENIX Association, 2008, pp. 225–240.
D. Y. Zhu, J. Jung, D. Song, T. Kohno, and D. Wetherall, “TaintEraser:
protecting sensitive data leaks using application-level taint tracking,”
ACM SIGOPS Oper. Syst. Rev., vol. 45, no. 1, pp. 142–154, 2011.
E. Zhu, F. Liu, Z. Wang, A. Liang, Y. Zhang, X. Li, and X. Li,“Dytaint: The implementation of a novel lightweight 3-state dynamic
taint analysis framework for x86 binary programs,” Comput. Secur.,vol. 52, pp. 51–69, 2015.

8