All You Ever Wanted to Know about Dynamic Taint Analysis and Forward Symbolic Execution (but Might Have Been Afraid to Ask)

By Edward J. Schwartz, Thanassis Avgerinos, David Brumley. 2010

847 citations recorded by the source corpus.

Dynamic taint analysis and forward symbolic execution are quickly becoming staple techniques in security analyses. Example applications of dynamic taint analysis and forward symbolic execution include malware analysis, input filter generation, test case generation, and vulnerability discovery. Despite the widespread usage of these two techniques, there has been little effort to formally define the algorithms and summarize the critical issues that arise when these techniques are used in typical security contexts. The contributions of this paper are two-fold. First, we precisely describe the algorithms for dynamic taint analysis and forward symbolic execution as extensions to the run-time semantics of a general language. Second, we highlight important implementation choices, common pitfalls, and considerations when using these techniques in a security context.

Subfields: Artificial Intelligence, Information Systems, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Signal Processing

Citations in the corpus

Model-Reuse Attacks on Deep Learning Systems (2018, methodology): “For example, dynamic taint analysis [52], a tool that tracks the influence of computation on predefined taint sources (e.”
DTA++: Dynamic Taint Analysis with Targeted Control-Flow Propagation (2011, methodology): “We start by giving some background about under-tainting in general, then give an overview of our approach, and illustrate with examples.”
Dynamic Malware Analysis in the Modern Era—A State of the Art Survey (2019, methodology): “Dynamic forward symbolic execution [62] is used to evaluate the malware execution using different inputs or environments.”
Symbolic execution for software testing: three decades later (2013, methodology): “For a detailed overview of symbolic execution techniques, we refer the reader to previously published surveys in the area, such as [11, 19, 32, 34].”
Sereum: Protecting Existing Smart Contracts Against Re-Entrancy Attacks (2018, methodology): “However, symbolic execution techniques suffer from the well-known path explosion problem for larger programs which is still an ongoing research topic [11], [28], [37], [41].”
A Survey of Symbolic Execution Techniques (2016, background): “ortant design choice for a symbolic engine, as it can significantly affect the coverage achieved by the exploration and the scalability of constraint solving [22]. The symbolic memory address problem [89] arises when the address referenced in the operation is a symbolic expression. In the remainder ”
Detecting trigger-based behaviors in botnet malware (2015, background): “Dynamic symbolic execution, also known as Concolic testing, executes program with predefined symbols [1, 2, 8, 17].”
SOK: (State of) The Art of War: Offensive Techniques in Binary Analysis (2016, background): “Whenever a conditional branch is reached, execution forks and follows both paths, saving the branch condition as a constraint on the path in which the branch was taken and the inverse of the branch condition as a constraint on the path in which the branch was not taken [49].”
BAP: A Binary Analysis Platform (2011, neutral): “– Forward symbolic execution [14].”
FlowFence: Practical Data Protection for Emerging IoT Application Frameworks (2016, methodology): “Dynamic or static taint analysis has been suggested as a method to address the limitations of the above permission-based systems [60] [53].”
The Art, Science, and Engineering of Fuzzing: A Survey (2018, methodology): “A broader treatment of dynamic symbolic execution can be found in other sources [20], [192].”
Evaluating Analysis Tools for Android Apps: Status Quo and Robustness Against Obfuscation (2016, background): “Anti-tainting: Taint analysis is a powerful analysis technique where data that flows between sources and sinks is tainted with so called tags [43].”
Unleashing Mayhem on Binary Code (2012, background): “Figure 4 shows how the symbolic execution throughput (number of test cases generated per second) is slowed down as the memory use increases.”
AFL++ : Combining Incremental Steps of Fuzzing Research (2020, methodology): “Recently, R ED Q UEEN [5], based on KAFL [36], explored the possibility to bypass hard comparisons and checksum checks, like other previous works in literature [35] [12] [33] [44], but without the use of expensive techniques like taint tracking [46] or symbolic execution [6, 37].”
Code-pointer integrity (2014, background): “…[31] encrypts code pointers in memory and provides security guarantees close to CPS. Data-ﬂow based techniques like data-ﬂow integrity (DFI) [10] or dynamic taint analysis (DTA) [42] can enforce that the used code pointer was not set by an unrelated instruction or to untrusted data, respectively.”
AVATAR: A Framework to Support Dynamic Security Analysis of Embedded Systems' Firmwares (2014, neutral): “[51]).”