[Question] How to map input bytes to the functions that accessed them in v4.0.0?

[rayansiddique9]

I'm analyzing parser behavior and need to determine which functions in an instrumented program accessed specific input bytes. This would help understand:

• Which parsing functions process which byte ranges
• How input bytes flow through the call stack
• Which code paths are triggered by specific input patterns

Environment

• PolyTracker version: 4.0.0 (Docker: trailofbits/polytracker:latest)
• Platform: macOS ARM64 (using --platform linux/amd64)
• Python version (in container): 3.10

What I've Successfully Extracted

I've made significant progress exploring the v4.0.0 API and can extract:

1. Function Names

from polytracker.taint_dag import TDFunctionsSection, TDStringSection

# Extract function ID → name mapping
for func_id, fn_header in enumerate(functions_section):
    func_name = string_section.read_string(fn_header.name_offset)

Results: Successfully extracted all function names: main, parse_expr, program, statement, expr, test, sum, term, etc.

2. Function Call Trace

from polytracker.taint_dag import TDEventsSection

# Iterate through execution trace
for event in events_section:
    function_id = event.fnidx      # Function being called
    event_type = event.kind        # ENTRY (0) or EXIT (1)

Results: Complete function call trace with proper nesting:

ENTER program
  ENTER statement
    ENTER expr
      ENTER term

3. Input Byte Offsets

# Extract byte offsets from taint forest
for node in trace.taint_forest.nodes():
    if node.source is not None:
        offset = trace.file_offset(node).offset  # Byte offset in input
        affected_cf = node.affected_control_flow # Whether byte influenced branching

Results: All input bytes tracked with control flow information.

What's Missing: The Correlation

I cannot find a way to correlate these pieces together to answer:
"Which function accessed byte X?"

For example, given:

• Input file: {i=1;}\n
• Byte 2 (= character) at offset 2

I need to determine: "The expr function accessed byte 2"

What I've Tried

Approach 1: TDEvent attributes

for event in events_section:
    # event has: fnidx, kind
    # event does NOT have: label, taints, bytes_accessed

Result: Events know which function, but not which bytes it accessed.

Approach 2: Taint nodes

for node in forest.nodes():
    # node has: label, source, affected_control_flow
    # node does NOT have: function, event, accessed_by

Result: Nodes know which byte, but not which function accessed it.

Approach 3: Documented methods

# These raise NotImplementedError:
trace.access_sequence()  # NotImplementedError
trace.function_trace()   # NotImplementedError
for event in trace:      # NotImplementedError (via __iter__)

Result: Documented API methods are not implemented in v4.0.0.

Approach 4: Control Flow Log

from polytracker.taint_dag import TDControlFlowLogSection

# CF log has function_id_mapping but unclear how to correlate with taints

Result: Found function_id_mapping attribute but it's a method, and calling it returns empty results.

Questions

1. Is there an API I'm missing?
   Is there a method/property that links taint labels to the events/functions that accessed them?

2. Should I use a different trace format?
   Issue Emitting and loading a DBProgramTrace instead of a TDProgramTrace #6534 mentioned DBProgramTrace vs TDProgramTrace. Can I generate .db files where access_sequence() actually works?

3. Is this data available internally but not exposed?
   If the correlation exists internally but isn't exposed via Python API, would you accept a PR to add it?

4. Alternative approach?
   Is there a recommended way to achieve this byte-to-function mapping with the current v4.0.0 API?

Minimal Reproduction

# Instrument a C program
docker run --rm --platform linux/amd64 \
    -v $(pwd):/workdir -w /workdir \
    trailofbits/polytracker bash -c \
    "polytracker build clang program.c -o program && \
     polytracker instrument-targets --taint --ftrace program"

# Execute with stdin tracking
docker run --rm --platform linux/amd64 \
    -v $(pwd):/workdir -w /workdir \
    -e POLYDB=polytracker.tdag \
    -e POLYTRACKER_STDIN_SOURCE=1 \
    trailofbits/polytracker \
    bash -c "./program.instrumented < input.txt"

# Analyze the trace
docker run --rm --platform linux/amd64 \
    -v $(pwd):/workdir -w /workdir \
    trailofbits/polytracker python3 -c "
from polytracker import PolyTrackerTrace
from polytracker.taint_dag import TDFunctionsSection, TDEventsSection, TDStringSection

trace = PolyTrackerTrace.load('polytracker.tdag')

# Can extract functions and events separately,
# but cannot correlate which functions accessed which bytes

Use Case

This mapping would enable:

• Parser debugging: Identify which function mishandled a specific byte
• Security analysis: Find which code paths process attacker-controlled bytes
• Execution visualization: Create diagrams showing byte flow through functions
• Performance analysis: Identify hot paths for specific input patterns

---

Related Issues:

• Emitting and loading a DBProgramTrace instead of a TDProgramTrace #6534 - "Emitting and loading a DBProgramTrace instead of a TDProgramTrace" (similar access_sequence question)

[hbrodin]

This is achievable for the subset of input bytes that influence control flow (branches, switches), using PolyTracker's ControlFlowLog feature. PolyTracker does not record a general "function X read label Y" log. It records which taint labels
affected control flow decisions in which function. For parser analysis, this is often exactly what matters, since parsers branch on input bytes to dispatch parsing logic.

What to change in your instrumentation

Three things need to change.

1. Add --cflog during instrumentation

  polytracker instrument-targets --taint --ftrace --cflog program

The --cflog flag enables the TaintedControlFlowPass LLVM pass, which instruments branches and switches to log which taint labels affect them. Without it, the ControlFlowLog section in the TDAG is empty.

2. Set POLYTRACKER_LOG_CONTROL_FLOW=1 at runtime

  docker run --rm --platform linux/amd64 \
      -v $(pwd):/workdir -w /workdir \
      -e POLYDB=polytracker.tdag \
      -e POLYTRACKER_STDIN_SOURCE=1 \
      -e POLYTRACKER_LOG_CONTROL_FLOW=1 \
      trailofbits/polytracker \
      bash -c "./program.instrumented < input.txt"

The LLVM pass inserts the instrumentation, but the runtime needs this env var to write control flow events to the TDAG.

3. Load functionid.json

The --cflog pass writes a functionid.json file next to the instrumented binary at compile time. This file maps numeric function IDs (used in the ControlFlowLog) to function names. Load it and pass it to cflog.function_id_mapping(...) before
iterating over events.

Working example: map input bytes to functions

  import json
  import cxxfilt
  from polytracker import PolyTrackerTrace
  from polytracker.taint_dag import (
      TDControlFlowLogSection,
      TDTaintedControlFlowEvent,
      TDSourceNode,
      TDUnionNode,
      TDRangeNode,
  )

  # Load the trace
  trace = PolyTrackerTrace.load("polytracker.tdag")
  tdfile = trace.tdfile

  # Get the control flow log section
  cflog = tdfile._get_section(TDControlFlowLogSection)

  # Load the function ID mapping produced at compile time
  # (sits next to your instrumented binary)
  with open("functionid.json") as f:
      funcnames = list(map(cxxfilt.demangle, json.load(f)))
  cflog.function_id_mapping(funcnames)


  def resolve_label_to_input_offsets(label, tdfile):
      """Walk the taint DAG from a label back to source
      nodes, returning the set of input byte offsets."""
      offsets = set()
      seen = set()
      stack = [label]
      while stack:
          lbl = stack.pop()
          if lbl in seen:
              continue
          seen.add(lbl)
          node = tdfile.decode_node(lbl)
          if isinstance(node, TDSourceNode):
              offsets.add(node.offset)
          elif isinstance(node, TDUnionNode):
              stack.append(node.left)
              stack.append(node.right)
          elif isinstance(node, TDRangeNode):
              stack.extend(range(node.first, node.last + 1))
      return offsets


  # Iterate control flow events
  for event in cflog:
      if isinstance(event, TDTaintedControlFlowEvent):
          input_offsets = resolve_label_to_input_offsets(
              event.label, tdfile
          )
          function_name = event.callstack[-1]
          print(
              f"Function '{function_name}' branched on "
              f"input bytes: {sorted(input_offsets)}"
          )
          print(
              f"  Full callstack: "
              f"{' -> '.join(event.callstack)}"
          )

This is the same pattern used in tests/test_cf_log.py and examples/analysis/ubet/eval_nitro.py (see the compare_cflog and input_offsets functions around line 266).

Limitations

The ControlFlowLog records when tainted data influences a branch, switch, select, or GEP index. It does not record:

• A function reading tainted data without branching on it (e.g., copying bytes through)
• Tainted data flowing through arithmetic or string operations without affecting control flow
• Which function passed tainted data to a sink

The answer to "which function accessed byte X" is only answerable as "which function branched on byte X," a strict subset. For parser analysis, this is usually sufficient because parsers branch on input to dispatch logic.

Full "function touched byte X" tracking would require a new TDAG event type that logs every taint label read per function. This would produce very large traces. The control-flow subset is a practical tradeoff.

About access_sequence(), __iter__(), and related methods

Those methods were part of an older database-backed trace format (DBProgramTrace) and are not implemented for the current TDAG backend (TDProgramTrace). The ControlFlowLog approach above is the way to get function-to-byte correlation in v4.0.0.