All You Ever Wanted to Know About Dynamic Taint Analysis and Forward Symbolic Execution (but might have been afraid to ask)
1 Dynamic analysis—the ability to monitor code as it executes. They differs dynamic taint analysis (observes which computation are may be? affected by input) and forward symbolic execution (construct logical formula of path). 2 They use SimpIL. It is enough to express typical languages. What about some strange assembly operations? It is side-effect free. Context: statements, memory state, variable values, PC, current statement (Σ, µ, ∆, pc, ι). Context does not change between transitions, so SimpIL does not support dynamically generated code (they discuss modification). 3 and use a variant of SimpIL.
4 Dynamic taint analysis: track flow between sources and sinks. Determined by taint policy: (1) overtainting, (2) undertainting, (3) precise. Tuple ⟨v, τ⟩: value and taint status. Taint policy: how taint is introduced, how taint propagates, how taint is checked. 5 Investigate more about taint jump policy. 6 Memory operation has two arguments: value and memory address. Taint jump policy treats them separately. 7 So, there is also taint addresses policy: memory cell is tainted if either the memory cell value or the memory address is tainted.
Control-flow taint: statement s2 is control-dependent on statement s1 if s1 controls whether or not s2 will execute (in SimpIL only indirect and conditional jumps). To detecting control-dependent taint:
- use of static analysis over the entire program, or over a collection of dynamic analysis runs,
- use heuristics.
Sanitization problem: 8 b = a ⊕ a, hash functions.
Add notes from Mendeley.
Sergey Vartanov, 2007–2020