Dynamic Taint Analysis

Some questions about a sample are not about what the code does but about where data goes. Does anything from the C2 response end up in the command passed to CreateProcessW? Which bytes of the decrypted configuration become the host name in the next connect? Of the 400 bytes the sample reads from a file, which ones decide whether it goes on to install itself? You can answer each of these by hand with cross-references and data-flow reasoning in a disassembler, but the moment the data passes through a decryption loop, a few buffers and a couple of helper functions, that turns into an afternoon.

Dynamic taint analysis (DTA, also called data-flow tracking) automates exactly this. You mark some data as tainted when it enters the program, let the program run, and have the analysis carry the mark along every copy and computation. When tainted data reaches a place you care about, you get an alert, often with a record of which input bytes it came from. This lesson covers the model, the design choices that make taint trackers precise or useless, the tools that exist, and a small tracker you will build and break yourself.

The question taint answers

Every taint analysis is a query of one shape: does data from this source reach that sink, and through which bytes? It has three parts.

Sources and sinks are usually placed with hooks on API calls, the same technique as in Dynamic Binary Instrumentation: when recv returns, mark its output buffer; when send is entered, inspect its input buffer. Propagation is the hard part, because it has to happen at every instruction the program executes. That is why practical taint trackers are built on a dynamic instrumentation engine, an emulator, or a whole-system emulator: something must see each instruction and update the taint state alongside it.

Propagation, instruction by instruction

For each instruction, the tracker asks which operands are read and which are written, then applies a rule. A typical policy for x86-64:

The zeroing idiom is the classic trap. Treating xor eax, eax as an ordinary xor leaves eax tainted forever, and every later use spreads it further.

Design choices: granularity, colours, shadow memory

Granularity

Granularity is the smallest unit that carries its own taint. Bit-level tracking is the most precise and the most expensive; word-level tracking is cheap and sloppy (one tainted byte in a 4-byte word taints all four). Most practical systems, libdft included, track bytes: they match x86's addressable unit and keep masks and partial-register writes reasonably precise. Registers are then tracked per byte as well, so that mov al, [x] taints only the low byte of rax.

Colours

A single taint bit per byte says only "tainted or not". That is enough for "does anything from the network reach CreateProcessW?" but not for "which network bytes?". Colours distinguish sources. With a bitmask of eight colours you can give each source its own bit (0x01, 0x02, 0x04...), and when two flows meet in an add the result is simply the bitwise OR of their colours, so mixed data still records every origin. Some tools go further and store a full set of labels per byte (PANDA's taint2 does this), which lets you give every input byte its own label at a substantial memory and speed cost.

Shadow memory

The taint state lives in shadow memory: a parallel structure with one taint entry per byte of the program's memory, plus a shadow register file (libdft calls it a virtual CPU). The layout follows from the two choices above:

Real implementations allocate shadow pages lazily, only for memory the program actually uses, and map untouched regions to a shared zero page. Even so, shadow memory and the per-instruction bookkeeping are why DTA commonly slows a program by an order of magnitude or more.

When taint lies: over- and under-tainting

A taint tracker is an approximation, and it fails in two directions.

Over-tainting marks data as tainted when it is not really influenced by the source. Causes: coarse granularity, missing zeroing idioms, whole-register tracking, and aggressive address taint (below). Over-tainting spreads: once the stack pointer or a frequently used global is tainted, nearly everything is, and the result is noise.

Under-tainting misses real influence. Causes: unmodelled instructions (SIMD, string instructions, system calls that copy data inside the kernel), data that leaves and re-enters the process (written to a file, then read back), and the two special cases that follow.

Address taint

When a tainted value is used as an index, as in `movzx eax, byte ptr [table

• rcx]withrcxtainted, is the loaded value tainted? The bytes oftable` are not, but which byte you get depends entirely on the input. Base64 decoders, case conversion tables, and cryptographic S-boxes all work this way. Ignore address taint and a Base64-decoded C2 command appears clean; propagate it and every array access with a tainted index spreads taint, often too far. Most tools make it a switch; know which way yours is set.

Implicit flows

Consider:

status = 0;
if (net[0] == 1)
    status = 1;

status ends up equal to a function of net[0], but no instruction ever copies or computes it from net[0]. The only connection is a conditional branch, a control dependency. Standard DTA tracks explicit data flow only, so status stays clean: an implicit flow is lost. Propagating taint through every branch to everything written under it fixes this in theory and floods the program with taint in practice, which is why almost no production tracker does it. What many tools do instead is report tainted branches: a conditional jump whose flags came from tainted data. That does not taint status, but it tells you exactly where input steers execution, which is often the question you had anyway. The lab shows both behaviours.

Malware does not need to know any of this to defeat a naive tracker; a lookup-table decoder or a byte-by-byte if/switch reconstruction of a string is enough. When a flow you expected to see disappears, suspect these two cases first.

Tools

The practical pattern with PANDA is worth stating: record the sample running in a guest once, at near-normal speed, then replay the recording as many times as you like with taint turned on. The slowdown no longer affects the sample's timing checks, because the sample is not running live any more. The lab below reuses the Unicorn setup from Shellcode Analysis, and the upcoming symbolic execution lesson picks up where taint stops.

Analyst use cases

• Which input bytes control a branch? Taint every byte of a file, network response or command line with its own colour and report tainted branches. For a sample that parses a C2 command, you get the offsets of the opcode byte, the length fields and any magic value it checks, without reading the parser.
• Where does a decrypted configuration go? Place the source on the output buffer of the decryption routine (after an XOR loop, for instance) and the sinks on networking, file and process APIs. The alerts tell you which field is the C2 host, which is the port, and which is the campaign ID, which is most of a config extractor's work (config extraction gets its own lesson in the encoding and crypto module).
• What is in an exfiltrated buffer? Taint the results of file reads, registry queries and credential APIs with different colours, and inspect the colours of each byte arriving at send. A buffer whose bytes carry the "browser profile file" colour answers the capability question directly.
• Does attacker input reach something dangerous? The same machinery, pointed at a vulnerable service instead of a sample, checks whether network data reaches an indirect call target or a command string.

Lab: build a byte-level taint tracker

You will write a short x86-64 routine that copies a "network buffer" into a "send buffer" with a transformation, a checksum and a status byte, then emulate it with Unicorn while a Python tracker keeps shadow state for every register and memory byte. Each network byte gets its own colour. The outputs below are real, from Unicorn 2.1.4, Capstone 5.0.9 and pyelftools 0.33 in a Python 3.14 virtual environment on macOS (Apple silicon). The routine only moves bytes between buffers inside the emulator; nothing is sent anywhere.

1. Create a working directory and a virtual environment:

   mkdir m11b && cd m11b
   python3 -m venv venv
   ./venv/bin/pip install unicorn capstone pyelftools

2. Save the routine as build_packet.s and assemble it. Clang's integrated assembler can target x86-64 Linux from any host, so no cross toolchain is needed; you only use the object file's .text bytes:

   # build_packet.s - copy a "network" buffer into a "send" buffer, transformed
   # System V: rdi = send buffer, rsi = network buffer, rdx = length
       .intel_syntax noprefix
       .text
       .globl build_packet
   build_packet:
       mov   byte ptr [rdi], 0x42        # header byte: a constant
       xor   ecx, ecx                    # i = 0
       xor   r8d, r8d                    # checksum = 0
   next:
       movzx eax, byte ptr [rsi + rcx]   # b = net[i]
       xor   al, 0x5a                    # b ^= 0x5a
       add   al, cl                      # b += i
       mov   byte ptr [rdi + rcx + 1], al  # send[1 + i] = b
       xor   r8b, al                     # checksum ^= b
       inc   rcx
       cmp   rcx, rdx
       jb    next
       mov   byte ptr [rdi + rdx + 1], r8b # send[1 + len] = checksum
       xor   eax, eax                    # status = 0
       cmp   byte ptr [rsi], 0x01        # if net[0] == 1 ...
       jne   done
       mov   al, 1                       #   status = 1
   done:
       mov   byte ptr [rdi + rdx + 2], al  # send[2 + len] = status
       ret

   clang -target x86_64-linux-gnu -c build_packet.s -o build_packet.o

   The routine contains one of each case from this lesson: a constant (the header), a copy with a transformation, a many-to-one mix (the checksum), a zeroing idiom, and an implicit flow (the status byte).

3. Save taint.py. The shadow state is two dictionaries of colour sets, one for registers and one for memory bytes. A code hook runs before every instruction, disassembles it with Capstone, computes effective addresses from the live register values, and applies the propagation table from earlier:

   # taint.py - a byte-level dynamic taint tracker for one emulated x86-64 routine
   import sys
   from elftools.elf.elffile import ELFFile
   from capstone import Cs, CS_ARCH_X86, CS_MODE_64
   from capstone.x86 import X86_OP_REG, X86_OP_MEM, X86_OP_IMM
   from unicorn import Uc, UC_ARCH_X86, UC_MODE_64, UC_HOOK_CODE
   from unicorn import x86_const
   
   CODE, NET, SEND, STACK = 0x10000, 0x20000, 0x30000, 0x40000
   net = bytes.fromhex(sys.argv[1]) if len(sys.argv) > 1 else b"\x01ping"
   code = ELFFile(open("build_packet.o", "rb")).get_section_by_name(".text").data()
   
   # --- shadow state: a set of colours per register and per memory byte -------
   # colour i means "derived from network byte i"
   FAMILY = {"a": "rax", "b": "rbx", "c": "rcx", "d": "rdx", "si": "rsi", "di": "rdi"}
   def canon(name):                                   # al/eax/rax -> rax, r8b -> r8
       if name.startswith("r") and name[1:2].isdigit():
           return "r" + "".join(ch for ch in name[1:] if ch.isdigit())
       core = name.lstrip("er").rstrip("xlhw") or name
       return FAMILY.get(core, name)
   
   reg_taint, mem_taint, flags_taint = {}, {}, set()
   for i in range(len(net)):
       mem_taint[NET + i] = {i}                       # SOURCE: every network byte
   
   md = Cs(CS_ARCH_X86, CS_MODE_64); md.detail = True
   mu = Uc(UC_ARCH_X86, UC_MODE_64)
   
   def reg_value(reg_id):
       return mu.reg_read(getattr(x86_const, "UC_X86_REG_" + md.reg_name(reg_id).upper()))
   
   def addr_of(op):
       m = op.mem
       a = m.disp
       if m.base:  a += reg_value(m.base)
       if m.index: a += reg_value(m.index) * m.scale
       return a
   
   def get(op):
       if op.type == X86_OP_REG: return set(reg_taint.get(canon(md.reg_name(op.reg)), set()))
       if op.type == X86_OP_MEM:
           a = addr_of(op)
           return set().union(*(mem_taint.get(a + k, set()) for k in range(op.size)))
       return set()                                   # immediates are never tainted
   
   def put(op, t):
       if op.type == X86_OP_REG: reg_taint[canon(md.reg_name(op.reg))] = t
       else:
           a = addr_of(op)
           for k in range(op.size): mem_taint[a + k] = t
   
   def where(op):
       if op.type != X86_OP_MEM: return md.reg_name(op.reg)
       a = addr_of(op)
       return f"send[{a - SEND}]" if a >= SEND else f"net[{a - NET}]"
   
   def show(t): return "{" + ",".join(f"net[{i}]" for i in sorted(t)) + "}" if t else "clean"
   
   def on_insn(uc, address, size, _):
       global flags_taint
       insn = next(md.disasm(code[address - CODE:address - CODE + size], address))
       ops, mn = insn.operands, insn.mnemonic
       text = f"{address:#x}  {mn} {insn.op_str}"
       if mn in ("mov", "movzx"):                                   # copy
           t = get(ops[1]); put(ops[0], t)
       elif mn in ("xor", "sub") and ops[0].type == ops[1].type == X86_OP_REG \
               and ops[0].reg == ops[1].reg:                        # zeroing idiom
           t = set(); put(ops[0], t)
       elif mn in ("add", "sub", "xor", "and", "or"):               # combine
           t = get(ops[0]) | get(ops[1]); put(ops[0], t)
       elif mn in ("cmp", "test"):                                  # flags only
           flags_taint = get(ops[0]) | get(ops[1])
           if flags_taint: print(f"{text:46} flags <- {show(flags_taint)}")
           return
       elif mn.startswith("j") and mn != "jmp":
           if flags_taint: print(f"{text:46} BRANCH decided by {show(flags_taint)}")
           return
       else:
           return                                                   # inc, ret ...
       print(f"{text:46} {where(ops[0])} <- {show(t)}")
   
   mu.mem_map(CODE, 0x1000); mu.mem_map(NET, 0x1000)
   mu.mem_map(SEND, 0x1000); mu.mem_map(STACK, 0x1000)
   mu.mem_write(CODE, code); mu.mem_write(NET, net)
   for reg, val in (("RDI", SEND), ("RSI", NET), ("RDX", len(net)), ("RSP", STACK + 0x800)):
       mu.reg_write(getattr(x86_const, "UC_X86_REG_" + reg), val)
   mu.hook_add(UC_HOOK_CODE, on_insn)
   mu.emu_start(CODE, CODE + len(code) - 1)                         # stop at `ret`
   
   print("\nSINK: send buffer as it would be passed to send()")
   out = mu.mem_read(SEND, len(net) + 3)
   for i, b in enumerate(out):
       print(f"  send[{i}] = {b:#04x}  {show(mem_taint.get(SEND + i, set()))}")

   Note the simplifications. Registers are tracked whole (al, eax and rax share one entry) rather than per byte, only the handful of mnemonics this routine uses are modelled, and address taint is off: get on a memory operand looks only at the bytes read, never at the taint of rsi or rcx used to address them.

4. Run it with the default network buffer, 01 70 69 6e 67 (a command byte of 1 followed by ping):

   ./venv/bin/python taint.py

   0x10000  mov byte ptr [rdi], 0x42              send[0] <- clean
   0x10003  xor ecx, ecx                          ecx <- clean
   0x10005  xor r8d, r8d                          r8d <- clean
   0x10008  movzx eax, byte ptr [rsi + rcx]       eax <- {net[0]}
   0x1000c  xor al, 0x5a                          al <- {net[0]}
   0x1000e  add al, cl                            al <- {net[0]}
   0x10010  mov byte ptr [rdi + rcx + 1], al      send[1] <- {net[0]}
   0x10014  xor r8b, al                           r8b <- {net[0]}
   0x10008  movzx eax, byte ptr [rsi + rcx]       eax <- {net[1]}
   ...
   0x10014  xor r8b, al                           r8b <- {net[0],net[1],net[2],net[3],net[4]}
   0x1001f  mov byte ptr [rdi + rdx + 1], r8b     send[6] <- {net[0],net[1],net[2],net[3],net[4]}
   0x10024  xor eax, eax                          eax <- clean
   0x10026  cmp byte ptr [rsi], 1                 flags <- {net[0]}
   0x10029  jne 0x1002d                           BRANCH decided by {net[0]}
   0x1002b  mov al, 1                             al <- clean
   0x1002d  mov byte ptr [rdi + rdx + 2], al      send[7] <- clean
   
   SINK: send buffer as it would be passed to send()
     send[0] = 0x42  clean
     send[1] = 0x5b  {net[0]}
     send[2] = 0x2b  {net[1]}
     send[3] = 0x35  {net[2]}
     send[4] = 0x37  {net[3]}
     send[5] = 0x41  {net[4]}
     send[6] = 0x33  {net[0],net[1],net[2],net[3],net[4]}
     send[7] = 0x01  clean

   Read it as an analyst. The header is clean, as a constant should be. Each of send[1] to send[5] carries exactly one colour, so each output byte is derived from one input byte despite the XOR and the index addition: the transformation changed the values, not the flow. send[6] carries all five colours, the signature of a checksum or hash. The zeroing xor eax, eax cleared eax as the policy says. And the tracker flagged the jne at 0x10029 as decided by net[0]: that is the "which input bytes control a branch" answer.

5. Now change only the command byte and run again:

   ./venv/bin/python taint.py 0270696e67

   0x10029  jne 0x1002d                           BRANCH decided by {net[0]}
   0x1002d  mov byte ptr [rdi + rdx + 2], al      send[7] <- clean
   
   SINK: send buffer as it would be passed to send()
     send[0] = 0x42  clean
     send[1] = 0x58  {net[0]}
     send[2] = 0x2b  {net[1]}
     send[3] = 0x35  {net[2]}
     send[4] = 0x37  {net[3]}
     send[5] = 0x41  {net[4]}
     send[6] = 0x30  {net[0],net[1],net[2],net[3],net[4]}
     send[7] = 0x00  clean

   send[7] flipped from 0x01 to 0x00 because net[0] changed, yet the tracker still reports it clean. This is the implicit flow from earlier, caught red-handed: the status byte depends on the input only through the branch, and pure data-flow tracking cannot see it. The tainted-branch report is the clue that something downstream is input-dependent.

Questions to answer: Why does send[6] carry every colour, and what would a real sample's buffer look like if a byte carried colours from two different sources, such as a file read and a registry query? Rewrite the status logic as sete al after the cmp: which propagation rule would you need so the tracker catches it, and why is that no longer an implicit flow? If you replaced movzx eax, byte ptr [rsi + rcx] with a lookup through a 256-byte table indexed by the network byte, what would this tracker report for send[1] to send[5], and what switch would change that? Because registers are tracked whole here, construct a sequence of two instructions that makes the tracker over-taint.

Key takeaways

• Taint analysis answers one question: does data from a source reach a sink, and through which bytes? Sources and sinks are usually API hooks; propagation runs at every instruction.
• Propagation rules copy taint on moves, union it on arithmetic and clear it on constants and zeroing idioms; getting the idioms wrong causes runaway over-tainting.
• Granularity (usually byte), colours (a bitmask or label set per byte) and shadow memory (bitmap to per-byte sets) trade precision against memory and speed; order-of-magnitude slowdowns are normal.
• Over-tainting comes from coarse tracking and aggressive address taint; under-tainting comes from unmodelled instructions, lookup tables and implicit flows through branches, which most trackers deliberately ignore but can report as tainted branches.
• libdft offers fast byte-level taint on Pin, Triton pairs taint with symbolic execution, and PANDA provides whole-system taint on record-and-replay.
• For malware, use taint to find which input bytes steer a parser, where a decrypted config flows, and what an exfiltrated buffer is made of.