bolt-stackinit-scanner

(Accompanying blog post and full project report)

A BOLT pass that statically analyses x86-64 binaries to flag stack loads that cannot be proven initialised. It was developed in an effort to validate the compiler's -ftrivial-auto-var-init flag, and can also be used as a general detector of uninitialised stack reads.

The scanner first collects all stack loads and stores it detects. For each load, it then checks that every byte of the read was written by an earlier store on every control-flow path reaching it. This check runs first within the function, and then extends across function boundaries by looking into callees and callers. Loads it cannot prove initialised are emitted as diagnostic reports; constructs it cannot model precisely are emitted as limitation reports.

The scanner is a work in progress. Refer to the full project report for the theoretical basis, the design choices, and the known limitations (mostly inherent to static analysis).

Repository Structure

This repository "forks" llvm/llvm-project.

Modifications to upstream files were kept to a minimum. Changes can be listed with e.g.:

$ git diff master bolt-stackinit-scanner

Key Files

File	Purpose
bolt/include/bolt/Passes/StackInitScanner.h, bolt/lib/Passes/StackInitScanner.cpp	Main implementation
bolt/test/binary-analysis/stackinit/	Test suite

Build

Refer to LLVM's documentation for requirements and full instructions.

As a brief guide to get started, configure LLVM with BOLT support with e.g.:

$ mkdir build.RELEASE
$ cmake -G Ninja -B build.RELEASE/ \
    -DLLVM_ENABLE_PROJECTS="clang;lld;bolt" \
    -DLLVM_TARGETS_TO_BUILD="X86;AArch64" \
    -DBOLT_TARGETS_TO_BUILD="X86;AArch64" \
    -DCMAKE_BUILD_TYPE=Release \
    -DLLVM_OPTIMIZED_TABLEGEN=ON \
    -DLLVM_PARALLEL_LINK_JOBS=4 \
    -DLLVM_ENABLE_ASSERTIONS=ON \
    llvm/

or for a debug build:

$ mkdir build.DEBUG
$ cmake -G Ninja -B build.DEBUG/ \
    -DLLVM_ENABLE_PROJECTS="clang;lld;bolt" \
    -DLLVM_TARGETS_TO_BUILD="X86;AArch64" \
    -DBOLT_TARGETS_TO_BUILD="X86;AArch64" \
    -DCMAKE_BUILD_TYPE=Debug \
    -DLLVM_OPTIMIZED_TABLEGEN=ON \
    -DLLVM_PARALLEL_LINK_JOBS=4 \
    -DLLVM_ENABLE_ASSERTIONS=ON \
    -DLLVM_ENABLE_DUMP=ON \
    llvm/

Then, build it with:

$ ninja -C build.RELEASE/

Run

The scanner is typically invoked as follows:

$ build.RELEASE/bin/llvm-bolt-binary-analysis \
    -scanners=stackinit \
    -allow-stripped \
    -experimental-shrink-wrapping \
    -assume-abi \
    -log-loads-stores \
    /path/to/target/binary

For a debug run, also include -debug-only=bolt-stackinit-scanner -no-threads.

Test

The scanner's test suite can be run with:

$ build.RELEASE/bin/llvm-lit -vva bolt/test/binary-analysis/stackinit/

The following subsections try to group most tests by complexity to facilitate onboarding on the subject.

Basic Tests

Direct loads and stores, simple cross-BB patterns, block-initialisation patterns, and triage categories.

File	Description
alignment-pops.s	Alignment-pop triage category for exit-BB pops
basic.s	Single-BB store/load ordering, frame pointer vs RSP, XMM stores
byte-coverage.s	Every byte in the load range must be covered by stores
interproc-basic.s	Basic callee-side inter-procedural: callee initialisation, late call, diamond CFG with one path missing initialisation, store-size mismatch
lods-stos.s	lods loads and stos stores detection
memset.s	memset block-initialisation pattern detection
noreturn.s	Non-returning call propagation, wrapper detection, glibc error() recognition
possibly-unused-pop.s	Dead-register pop triage category for pops to dead call-clobbered registers
redundant-loads.s	Redundant-loads optimisation: same-BB, cross-BB, diamond CFG
rep-stos.s	rep stos block-initialisation pattern detection
stack-clash-probe.s	Stack Clash probe triage category
unsatisfied-dedup.s	Diagnostic-report deduplication: same-BB, cross-BB, different ranges

Medium Tests

Derived accesses, conditional paths, pointer-to-stack resolution, and inter-procedural edge cases.

File	Description
cmov.s	cmov derived loads: no-path/one-path/two-paths stack sources, loops, ignored cases, memory-source operands
cmov-interproc.s	Inter-procedural save/restore, agreeing cmov paths, non-stack cmov operand (limitation), disagreeing cmov displacements (limitation)
derived-arithm.s	MOV/ADD/SUB/INC/DEC in the middle of derived register chains
derived-basic.s	Simple derived loads: LEA/MOV propagation, offsets
derived-conditional.s	Conditional paths, multi-BB register chains, 2-hop path constraints
derived-dedup.s	Duplicate derived accesses, path-constraint deduplication
derived-indexed.s	Indexed loads and stores: known-constant index register, unsupported opaque indices
derived-pointer.s	Pointer-to-stack resolution
derived-stores.s	Derived stores: diamond CFG, offset tracking
interproc-arg-forwarding.s	Inter-procedural argument forwarding through register shuffles
interproc-callee-init.s	Callee initialisation correctness: argument register clobbering, partial initialisation (single-exit and multi-exit callees), all-paths initialisation
interproc-csr.s	Callee-saved register preservation (-assume-abi)
interproc-derived.s	Inter-procedural with derived registers (copy+offset, ADD, LEA)
interproc-multilevel.s	Inter-procedural call chains at varying depths
interproc-recursion.s	Inter-procedural self-recursive calls
interproc-tailcall.s	Inter-procedural call chains through tail calls
loops.s	Initialised and uninitialised loop counters, cross-BB direct loads
stackargs.s	Caller-frame loads (loads exceeding the function's stack frame)

Advanced Tests

Path-constraint mechanics, forbidden basic blocks, store killing, and miscellaneous edge cases.

File	Description
constraint-path.s	Stuck paths with unsatisfied path constraint, distinct visited state for the same block at different constraint progress
derived-edge-cases.s	Circular register definitions, unreachable predecessors interacting with path constraints, external call severing RBP's reaching-def chain
derived-loop-carried.s	Loop-carried register update: multiple accesses on the same path with different ranges
forbidden-bb.s	Forbidden basic blocks: single-hop and 2-hop register chain scenarios
path-conflict.s	Intra-BB and cross-BB killed stores in pointer-to-stack resolution