Backward Program Slicing for Binary Analysis with Ghidra

Program slicing is a static analysis technique used in software verification, debugging, and reverse engineering. This post details the practical implementation of backward program slicing on compiled binaries using Ghidra’s intermediate representation (IR).

At its core, backward slicing identifies the execution paths and data flows that influence a specific instruction or variable. The target is formalized as the slicing criterion — a pair $(s,v)$ where $s$ is a program statement and $v \subseteq \operatorname{Vars}(s)$ is the set of variables whose values are observed at $s$ .

In binary analysis, backward slicing helps automate the process of understanding how data reaches a critical sink. For example, during a security audit, you might identify a call to a function like memcpy. To evaluate its safety, you might ask yourself:

What variables or calculations control the size argument of this memcpy?
What execution paths and conditional branches govern whether this call is reached?

Answering these questions by manually tracing assembly can become tedious and error-prone. Slicing helps automate this inquiry by mapping the binary to structured dependency graphs.

This post walks through the theoretical graph foundations and the practical implementation details of building a backward slicer directly utilizing the Java classes exposed by Ghidra.

Representing Programs as Graphs

To perform program slicing, we first build representations of the program’s structure. Consider this simple C function:

char* check_number(int n) {
    if (n > 0) {
        return "Positive";
    } else if (n < 0) {
        return "Negative";
    } else {
        return "Zero";
    }
}

Static analysis tools construct and reason about four primary graph representations to analyze this code.

1. Control Flow Graph (CFG)

The CFG represents all possible execution paths. Nodes represent basic blocks (sequences of instructions with a single entry and exit), and directed edges represent control flow transfers.

graph TD
    Entry([Entry]) --> S1{S1: n > 0}
    S1 -- True --> S2[S2: return 'Positive']
    S1 -- False --> S3{S3: n < 0}
    S3 -- True --> S4[S4: return 'Negative']
    S3 -- False --> S5[S5: return 'Zero']
    S2 --> Exit([Exit])
    S4 --> Exit
    S5 --> Exit

While a CFG is useful for understanding the sequence of execution, it does not explicitly track how data is propagated. For that, we rely on data dependencies.

2. Data Dependence Graph (DDG)

The DDG represents the flow of data. An edge exists from node $A$ to node $B$ if node $A$ defines or modifies a value that node $B$ subsequently reads. In our example, the input parameter $n$ serves as a root data source defined at function entry, which flows into and is consumed by conditional checks S1 and S3.

graph TD
    Entry([Entry: parameter n]) -->|Data: n| S1[S1: n > 0]
    Entry -->|Data: n| S3[S3: n < 0]

3. Control Dependence Graph (CDG)

While the CFG captures the raw execution order of basic blocks, the Control Dependence Graph (CDG) captures decision causality. A node $B$ is control-dependent on node $A$ if the branch condition at $A$ directly dictates whether $B$ will be reached or bypassed. For instance, return "Positive" (S2) is only executed if the conditional check n > 0 (S1) evaluates to True.

graph TD
    Entry([Entry]) --> S1[S1: n > 0]
    S1 -.->|True| S2[S2: return 'Positive']
    S1 -.->|False| S3[S3: n < 0]
    S3 -.->|True| S4[S4: return 'Negative']
    S3 -.->|False| S5[S5: return 'Zero']

4. The Program Dependence Graph (PDG)

By combining both control and data dependencies, we construct the Program Dependence Graph (PDG). The PDG uses distinct edge types to represent control dependencies (dashed lines) and data dependencies (solid lines).

graph TD
    %% Control Dependencies
    Entry([Entry]) -.-> S1[S1: n > 0]
    S1 -.->|True| S2[S2: return 'Positive']
    S1 -.->|False| S3[S3: n < 0]
    S3 -.->|True| S4[S4: return 'Negative']
    S3 -.->|False| S5[S5: return 'Zero']

    %% Data Dependencies
    Entry ===>|n| S1
    Entry ===>|n| S3

    classDef cd stroke-dasharray: 5 5;
    classDef dd stroke-width:3px;

The Slicing Mechanism

In The Program Dependence Graph and Its Use in Optimization, Ferrante et al., define a slice as the set of statements that influence a variable’s value at a chosen observation point. They demonstrate that any correct slice must capture both data flow and the control predicates that govern execution. Because a computation affecting a target variable may only run when a specific predicate holds, the conditional structure surrounding it must be included in the slice.

Since the PDG encapsulates both forms of dependence, extracting a backward slice becomes a graph-reachability problem. Starting from your target node (the slicing criterion), you perform a backward traversal along the control and data edges in reverse. Every node visited during this walk is part of the slice, showing you exactly which instructions could have influenced your target.

Slicing Binaries: The Ghidra Approach

Building a slicer inside Ghidra offers several practical advantages:

Preserved Context: The Ghidra database already preserves manual analyst annotations, data type definitions, and function renames that would otherwise need to be reconstructed.
Built-in Decompiler Pipeline: Ghidra’s decompiler computes the CFG, dominance structures, and SSA form out of the box, saving you from having to construct them from raw machine instructions.
Extensible IR: High-level P-code normalizes architecture-specific instruction semantics into a manageable set of core operations.

The architecture of Ghidra’s decompiler pipeline is heavily influenced by Dr. Cristina Cifuentes’ 1994 PhD dissertation [2], "Reverse Compilation Techniques". Cifuentes laid out the classic four-stage decompiler pipeline:

Disassembly and Translation: Translating machine bytes into an intermediate representation (IR).
Data-Flow Analysis: Transforming the IR into Single Static Assignment (SSA) form which defines a representation such that every variable is assigned exactly once, enabling dead code elimination and copy propagation.
Control-Flow Analysis: Structuring the CFG into high-level control constructs (such as loops and conditionals) using graph reducibility.
Code Generation: Generating readable C-like pseudo-code from the structured representation.

Ghidra implements this architecture by translating machine bytes into intermediate representations before performing high-level analysis:

[Machine Bytes]
       ↓ (Disassembly & SLEIGH Translation) — Stage 1
[Raw P-code]
       ↓ (Decompiler SSA Transformation) — Stage 2 & 3
[High-Level P-code AST] (PcodeOpAST / VarnodeAST)

SLEIGH and P-code

Ghidra’s first phase is translating machine bytes into an Intermediate Representation (IR). This translation is handled by Ghidra’s SLEIGH translation engine. SLEIGH is a processor specification language that maps target machine instructions to P-code, a machine-independent register-transfer language.

For static analysis and program slicing, we do not operate on raw P-code. Instead, we use High P-code that is represented by PcodeOpAST and VarnodeAST and generated within a HighFunction context. This is the representation generated after the decompiler has transformed the raw instructions into Single Static Assignment (SSA) form, which links every variable use to its unique definition point.

Addressing the Memory-Aliasing Problem

In binary analysis, standard SSA-based data flow analysis is insufficient because binaries make heavy use of memory dereferences. If register values are written to or read from memory, a naive SSA-based data flow graph will lose the connection between a STORE and a subsequent LOAD.

Consider the following code pattern:

*dest_ptr = computed_size; // STORE: writes to memory
// intermediate code ...
size_t len = *src_ptr;      // LOAD: reads from memory
memcpy(buf, input, len);

In a purely register-level SSA representation, the STORE writes to an abstract memory state, and the subsequent LOAD reads from memory without an explicit def-use edge connecting computed_size to len. If dest_ptr and src_ptr point to the same address, a naive slicer will fail to recognize the fact that computed_size influences len.

To bridge this gap, a robust slicing engine requires an alias-aware memory dependence model that operates on physical byte offsets:

Pointer Base Recovery: Input parameters, stack frame pointers, and global references are established as base variables.
Field-Sensitive Offset Calculation: Ghidra’s pointer-construction operators are recursively parsed:
- PTRSUB (Pointer Structure Sub-component): Resolves structured displacements, where:
  offset = base_ptr + offset_val
- PTRADD (Pointer Array Addition): Resolves scaled array access indices, where:
  offset = base_ptr + (index * element_size)
Conservative May-Aliasing Fallback: If a pointer’s offset depends on a dynamic variable (such as a loop index), the pointer is flagged as non-constant, falling back to a conservative "may-alias" state.
Temporal Execution Paths: Potential memory alias edges are validated against CFG reachability. A LOAD is only linked to a STORE if a valid control flow path exists between them, preventing the slicer from tracing backward to a store that can only execute in the future.

Implementing the Slicing Pipeline

By utilizing Ghidra’s Java API, we can programmatically build the dependency graphs and perform the slice.

[PcodeBlockBasic CFG] (High-Level P-code blocks)
                   ↓
[JungDirectedGraph<PcodeBlockBasic, PcodeEdge>] (Reverse CFG for post-dominance)
                   ↓
[ChkDominanceAlgorithm] (Cooper, Harvey, Kennedy Algorithm)
                   ↓
[GDirectedGraph] (Post-Dominance Tree)
                   ↓
[CDGBuilder] (Ferrante-style CDG construction)
                   ↓
[Map<PcodeBlockBasic, Set<PcodeBlockBasic>>] (Control Dependence Graph)
                   ↓
 [BackwardSlicer] (Worklist traversal over PcodeOpAST and VarnodeAST)

1. Dominance and Control Dependence

To construct the CDG, we compute post-dominance on the CFG. Ghidra provides ChkDominanceAlgorithm, which implements the Cooper, Harvey, and Kennedy (CHK) dominance algorithm. Running this on the reversed CFG yields the post-dominance tree of the function—identifying, for each node, the nearest point guaranteed to follow it on every execution path to the exit. Note that Ghidra provides a practical implementation including sink and source unification via unifySinks and unifySources. Pragmatically compiled functions tend to have multiple return instructions or abnormal exit paths (such as calls to exit() or abort()). Standard post-dominance algorithms require a single exit point. Thankfully Ghidra’s static unifySinks method resolves this by programmatically binding multiple exits to a single virtual sink.

2. Building the CDG

With the post-dominance tree in hand, we perform a Ferrante-style walk over the CFG edges. For each edge $(A, B)$ , we climb the post-dominance tree from $B$ up to (but not including) the immediate post-dominator of $A$ , marking each visited node as control-dependent on $A$ . The result is a map from each basic block to the set of blocks whose branch decisions govern whether it executes.

3. Executing the Backward Slice

Once control and memory dependencies are established, the backward slice is a straightforward worklist traversal over the PDG. From the seed operation, we chase data predecessors through the DDG (both SSA def-use chains and injected memory alias edges) and pull in the terminating branch of every control-dependent block:

private class BackwardSlicer {
    Set<PcodeOp> slice(
            PcodeOp seed,
            Map<PcodeOp, Set<PcodeOp>> ddg,
            Map<PcodeBlockBasic, Set<PcodeBlockBasic>> cdg,
            HighFunction hf) {

        Map<PcodeOp, PcodeBlockBasic> opToBlock = new HashMap<>();
        for (PcodeBlockBasic block : hf.getBasicBlocks()) {
            Iterator<PcodeOp> ops = block.getIterator();
            while (ops.hasNext()) {
                opToBlock.put(ops.next(), block);
            }
        }

        Set<PcodeOp> slice = new HashSet<>();
        Queue<PcodeOp> work = new ArrayDeque<>();
        work.add(seed);

        while (!work.isEmpty()) {
            PcodeOp op = work.remove();
            if (!slice.add(op)) continue;

            // 1. Trace Data Dependencies (SSA and Memory Aliasing)
            Set<PcodeOp> dataPreds = ddg.getOrDefault(op, Collections.emptySet());
            for (PcodeOp pred : dataPreds) {
                if (!slice.contains(pred)) {
                    work.add(pred);
                }
            }

            // 2. Trace Control Dependencies
            PcodeBlockBasic block = opToBlock.get(op);
            if (block != null) {
                Set<PcodeBlockBasic> controllers = cdg.getOrDefault(block, Collections.emptySet());
                for (PcodeBlockBasic controller : controllers) {
                    PcodeOp branch = controller.getLastOp();
                    if (branch != null && !slice.contains(branch)) {
                        work.add(branch);
                    }
                }
            }
        }
        return slice;
    }
}

Real-World Binary Slicing Caveats

Implementing this pipeline highlights several discrepancies between textbook static analysis and the realities of compiled binaries. When building analysis tooling, several key edge cases must be accounted for:

Unimplemented Semantics (unimpl): CPU instruction set architectures are vast. Ghidra’s SLEIGH engine may map less common or complex instructions as unimpl, generating no P-code semantics. This creates a silent dataflow cut that can cause a slice to truncate prematurely with no visible error.
Unmodeled Side-Effects: Primitive operations like USERDEFINED or CPOOLREF represent actions the decompiler treats as black boxes. Output variables from these operations must be conservatively assumed to depend on all inputs to avoid missing critical data flow.
Transient Register Overlaps: Sub-register layouts (such as writing to AL or AH and subsequently reading from EAX) introduce aliasing. Ghidra’s AST normalizes most of these layouts into distinct HighVariable instances, but cases that fall through this normalization require awareness at the analysis layer.
Unique Space Isolation: Ghidra uses a temporary address space (unique) for local, compiler-generated variables inside instruction translations. Because these variables are transient, block-local, and cannot be targeted by pointers, they can be safely exempted from the memory-aliasing engine, improving performance.

Conclusion

By mapping binary code to intermediate representations like Ghidra’s P-code, we can augment manual assembly inspection with automated, algorithmic program analysis. A static backward slicer accelerates reverse engineering by isolating the minimal set of vulnerable data paths and branch decisions governing critical sinks.

The pipeline described above handles standard control flow and common pointer operations reasonably well. But it’s important to keep in mind that production binary analysis regularly surfaces interesting problems: indirect jumps with unresolved targets, calls across binary boundaries, multi-threaded shared state, and heap allocations with no statically recoverable base. These are the cases where off-the-shelf tooling tends to face challenges.

If you are working on custom program analysis or binary auditing challenges, feel free to get in touch.

References

Ferrante, J., Ottenstein, K. J., & Warren, J. D. (1987). The Program Dependence Graph and Its Use in Optimization. ACM Transactions on Programming Languages and Systems, 9(3), 319–349. PDF Link
Cifuentes, C. (1994). Reverse Compilation Techniques (PhD dissertation). Queensland University of Technology. PDF Link
Cooper, K. D., Harvey, T. J., & Kennedy, K. (2001). A Simple, Fast Dominance Algorithm. Software—Practice and Experience, 4(1), 1-10. PDF Link
Angr Binary Analysis Framework: Backward Slicer Implementation. GitHub Repository
National Security Agency. (2024). Ghidra SLEIGH Compiler Language Manual. Ghidra Docs
National Security Agency. (2024). Ghidra P-Code Reference Manual. Ghidra Docs
National Security Agency. (2024). Ghidra API Reference: HighFunction Class. Ghidra API Docs
National Security Agency. (2024). Ghidra API Reference: ChkDominanceAlgorithm Class. Ghidra API Docs