Dynamic Taint Tracking
Dynamic Analysis & Debugging for VR · VR Analysis & Discovery track
8 min read
In this module
Tracking Data Through Execution
In Source Code Auditing, taint analysis was a static technique — following untrusted data through source code. Dynamic taint tracking does the same thing at runtime, watching actual execution and recording exactly which input bytes influence which memory locations and registers at every point. It answers the question you actually care about: "which bytes of my input control this crash?"
How Dynamic Taint Tracking Works
A dynamic taint tracker instruments every instruction the program executes. For each instruction, it:
- Checks the taint status of all input operands (registers and memory locations)
- Applies propagation rules to determine the taint status of outputs
- Updates the taint map - a shadow data structure that mirrors the program's memory and registers but stores taint labels instead of values
For example, when the program executes MOV RAX, [RBP-0x10]:
- The tracker looks up the taint label of the 8 bytes at
[RBP-0x10] - It copies that taint label to RAX's entry in the taint map
- If those bytes originated from input byte 42-49, RAX is now labelled "tainted by input bytes 42-49"
When the program executes ADD RAX, RCX:
- RAX's taint is the union of RAX's and RCX's prior taint labels
- If RAX was tainted by bytes 42-49 and RCX was tainted by byte 100, the result is tainted by bytes 42-49 and 100
Follow the shadow state down a short, illustrative snippet that reads a packet's length field. Watch three rules at work: mov copies a label, add unions labels (a constant contributes none), and xor ecx, ecx clears one, because the result is zero whatever ECX held. Before you reach the last box, decide which input bytes end up controlling the memcpy length.
These rules only follow explicit data flow, where a tainted value is copied or computed into another. They miss implicit flows through control dependencies: if (input[4] == 'A') x = 1; else x = 0; leaves x clean even though the input decided its value. Trackers that try to follow control dependencies swing the other way and taint far too much. That trade-off between under-tainting (missing real influence) and over-tainting (labelling almost everything) is the main practical limit of the technique, and pointer arithmetic, table lookups and hash functions make it worse.
Intel PIN for Custom Taint Tracking
Intel PIN is a dynamic binary instrumentation (DBI) framework that lets you insert analysis code at any point in a program's execution. It works by JIT-compiling the target program with your instrumentation code interleaved:
// Simplified PIN taint tracking tool#include "pin.H"#include <map>#include <set>
// Shadow memory: maps each memory byte to its taint labelsstd::map<ADDRINT, std::set<int>> mem_taint;
// Shadow registers: maps each register to its taint labelsstd::map<REG, std::set<int>> reg_taint;
// Instrument memory reads: propagate taint from memory to registerVOID RecordMemRead(ADDRINT addr, UINT32 size, REG dst) { std::set<int> combined; for (UINT32 i = 0; i < size; i++) { auto it = mem_taint.find(addr + i); if (it != mem_taint.end()) { combined.insert(it->second.begin(), it->second.end()); } } if (!combined.empty()) { reg_taint[dst] = combined; } else { reg_taint.erase(dst); }}
// Taint the input buffer when recv() returnsVOID AfterRecv(ADDRINT buf, ADDRINT ret_val) { if ((int)ret_val > 0) { for (int i = 0; i < (int)ret_val; i++) { mem_taint[buf + i] = {i}; // Label each byte with its index } }}This is highly simplified - a real implementation must handle every instruction type, track taint through arithmetic, and deal with flags registers. But it illustrates the core concept: shadow the program's state with taint labels and update them at every instruction.
Valgrind for Memory Error Detection
Valgrind (specifically its Memcheck tool) is not a traditional taint tracker, but it tracks the "definedness" of every bit in memory - essentially tracking whether data has been initialised. This catches:
- Reads of uninitialised memory - data that was never written to
- Use of uninitialised values in branches - control flow depending on undefined data
- Heap buffer overflows and underflows - via red zones around allocations
- Use after free - accessing freed memory
# Run a program under Valgrindvalgrind --tool=memcheck --track-origins=yes ./target_program input_file
# Typical Valgrind output for an uninitialized read:# ==12345== Conditional jump or move depends on uninitialized value(s)# ==12345== at 0x401234: process_data (parser.c:87)# ==12345== by 0x401567: main (main.c:42)# ==12345== Uninitialized value was created by a heap allocation# ==12345== at 0x4C2BBAF: malloc (vg_replace_malloc.c:299)# ==12345== by 0x401200: read_packet (parser.c:60)The --track-origins=yes flag is critical for VR: it tells you where the uninitialised data was allocated, making it possible to trace the root cause.
Valgrind and AddressSanitizer (ASan) catch overlapping but different bugs. Valgrind detects uninitialised reads that ASan misses. ASan detects some out-of-bounds accesses that Valgrind misses (particularly stack buffer overflows). ASan is much faster (2x slowdown vs. Valgrind's 10-50x). For thorough VR, use both: ASan during fuzzing (where speed matters) and Valgrind for targeted analysis of specific test cases.
DynamoRIO for Cross-Platform Instrumentation
DynamoRIO is another DBI framework, similar to Intel PIN but with different architecture support and licensing. Its Dr. Memory tool provides Valgrind-like memory checking on Windows (where Valgrind does not run):
# Run with DynamoRIO's Dr. Memorydrmemory -- ./target_program input_file
# Custom DynamoRIO client for taint trackingdrrun -c my_taint_tracker.dll -- ./target_program input_fileDynamoRIO's API allows building custom instrumentation tools that track memory accesses, function calls, and data flow across the entire program execution.
Identifying Which Input Bytes Reach Which Code
The practical payoff of dynamic taint tracking is answering: "if I change byte N of my input, what parts of the program are affected?" This is directly useful for exploit development:
# Conceptual taint query output:# Input byte 0-3: influences the message type field (controls dispatch)# Input byte 4-7: influences the length field (controls allocation size)# Input byte 8-11: influences the checksum comparison# Input byte 12+: payload data, reaches memcpy at 0x401234With this information, you can:
- Construct inputs that pass validation (taint shows which bytes control checks)
- Identify which bytes to mutate to trigger different code paths
- Build exploit payloads where each byte serves a specific purpose
Taint-Guided Fuzzing
Dynamic taint tracking can supercharge fuzzing by telling the fuzzer which input bytes matter for each code path. Traditional coverage-guided fuzzers mutate bytes randomly and hope to discover new paths. Taint-guided fuzzers use taint information to mutate only the bytes that influence the next branch decision:
# Traditional fuzzer: mutates random bytes# Iteration 1: mutate byte 47 -> no new coverage# Iteration 2: mutate byte 3 -> no new coverage# ...# Iteration 99: mutate byte 4 -> new coverage! (byte 4 is the length field)
# Taint-guided fuzzer: knows byte 4 controls the branch# Iteration 1: mutate byte 4 -> new coverage immediatelyAngora runs real byte-level taint tracking to learn which input bytes reach each branch. REDQUEEN, which AFL++ implements as CmpLog, gets a similar answer far more cheaply without tracking taint at all: it logs the operands of each comparison and looks for those values in the input, an idea its authors call input-to-state correspondence. Both make a big difference on programs with complex input validation.
Practical Taint Tracking Workflow
- Identify the input source - determine which function reads the input (recv, read, fread) and which buffer it lands in
- Mark input bytes - configure the taint tracker to label each input byte with its offset
- Run the program - let it process the input while the tracker records taint propagation
- Query at crash/sink points - when the program crashes or reaches a dangerous function, query the taint map to see which input bytes are present
- Build a byte map - document which input bytes control which program behaviour
This byte map replaces trial-and-error with systematic construction — every position in your input has a known role, and you can build payloads deliberately rather than by guesswork.