PolyTracker

PolyTracker is a tool originally created for the Automated Lexical Annotation and Navigation of Parsers, a backronym devised solely for the purpose of referring to it as The ALAN Parsers Project. However, it has evolved into a general purpose tool for efficiently performing data-flow and control-flow analysis of programs. PolyTracker is an LLVM pass that instruments programs to track which bytes of an input file are operated on by which functions. It outputs a database containing the data-flow information, as well as a runtime trace. PolyTracker also provides a Python library for interacting with and analyzing its output, as well as an interactive Python REPL.

PolyTracker can be used in conjunction with PolyFile to automatically determine the semantic purpose of the functions in a parser. It also has an experimental feature capable of generating a context free grammar representing the language accepted by a parser.

Unlike dynamic instrumentation alternatives like Taintgrind, PolyTracker imposes negligible performance overhead for almost all inputs, and is capable of tracking every byte of input at once. PolyTracker started as a fork of the LLVM DataFlowSanitizer and takes much inspiration from the Angora Fuzzer. However, unlike the Angora system, PolyTracker is able to track the entire provenance of a taint. In February of 2021, the LLVM DataFlowSanitizer added a new feature for tracking taint provenance called origin tracking. However, it is only able to track at most 16 taints at once, while PolyTracker can track up to 2³¹-1.

This README serves as the general usage guide for installing PolyTracker and compiling/instrumenting binaries. For programmatically interacting with or extending PolyTracker through its Python API, as well as for interacting with runtime traces produced from instrumented code, consult the Python documentation.

Quickstart

PolyTracker is controlled via a Python script called polytracker. You can install it by running

pip3 install polytracker

PolyTracker requires a very particular system environment to run, so almost all users are likely to run it in a containerized environment. Luckily, polytracker makes this easy. All you need to do is have docker installed, then run:

polytracker docker pull

and

polytracker docker run

The latter command will mount the current working directory into the PolyTracker Docker container, and allow you to build and run instrumented programs.

The polytracker control script—which you can run from either your host system or from inside the Docker container—has a variety of commands, both for instrumenting programs as well as analyzing the resulting artifacts. For example, you can explore the dataflows in the execution, reconstruct the instrumented program's control flow graph, and even extract a context free grammar matching the inputs accepted by the program. You can explore these commands by running

polytracker --help

The polytracker script is also a REPL, if run with no command line arguments:

$ polytracker
PolyTracker (4.0.0)
https://github.com/trailofbits/polytracker
Type "help" or "commands"
>>> commands

Instrumenting a simple C/C++ program

PolyTracker also comes with a build command. This command allows the user to run any build command in a Blight instrumented environment. This will produce a blight_journal.jsonl file that records all commands run during the build. If you have a C/C++ target, you can instrument it by invoking polytracker build and passing your build command:

polytracker build gcc -g -o my_binary my_source.c

To instrument a build target, use the instrument-targets command. By default the command will use the a blight_journal.jsonl in your current working directory to build an instrumented version of your build target. The instrumented build target will be built using the same flags as the original build target.

polytracker instrument-targets my_binary

build also supports more complex programs that use a build system like autotiools or CMake:

polytracker build cmake .. -DCMAKE_BUILD_TYPE=Release
polytracker build ninja
# or
polytracker build ./configure
polytracker build make

Then run instrument-targets on any targets of the build:

polytracker instrument-targets a.bin b.so

Then a.instrumented.bin and b.instrumented.so will be the instrumented versions. See the Dockerfiles in the examples directory for examples of how real-world programs can be instrumented.

Running and Analyzing an Instrumented Program

The instrumented software will write its output to the path specified in POLYDB, or polytracker.tdag if omitted. This is a binary file that can be operated on by running:

from polytracker import PolyTrackerTrace, taint_dag

trace = PolyTrackerTrace.load("polytracker.tdag")
tdfile = trace.tdfile

first_node = list(tdfile.nodes)[0]
print(f"First node affects control flow: {first_node.affects_control_flow}")

# Operate on all Range nodes
for index, node in enumerate(tdfile.nodes):
  if isinstance(node, taint_dag.TDRangeNode):
    print(f"Node {index}: first {node.first}, last {node.last}")

# Access taint forest
tdforest = trace.taint_forest
n1 = tdforest.get_node(1)
print(
  f"Forest node {n1.label}. Parent labels: {n1.parent_labels}, "
  f"source: {n1.source.path if n1.source is not None else None}, "
  f"affects control flow: {n1.affected_control_flow}"
)

You can also run an instrumented binary directly from the REPL:

$ polytracker
PolyTracker (4.0.0)
https://github.com/trailofbits/polytracker
Type "help" or "commands"
>>> trace = run_trace("path_to_binary", "path_to_input_file")

This will automatically run the instrumented binary in a Docker container, if necessary.

⚠️ If running PolyTracker inside Docker or a VM: PolyTracker can be very slow if running in a virtualized environment and either the input file or, especially, the output database are located in a directory mapped or mounted from the host OS. This is particularly true when running PolyTracker in Docker from a macOS host. The solution is to write the database to a path inside of the container/VM and then copy it out to the host system at the very end.

The Python API documentation is available here.

Runtime Parameters and Instrumentation Tuning

At runtime, PolyTracker instrumentation looks for a number of configuration parameters specified through environment variables. This allows one to modify instrumentation parameters without needing to recompile the binary.

Environment Variables

PolyTracker accepts configuration parameters in the form of environment variables to avoid recompiling target programs. The current set of environment variables that PolyTracker supports is: