Backward Program Slicing – react0r blog
react0r blog
Sharing research, innovation, and technology
Skip to content
Search for:
react0r blog
Sharing research, innovation, and technology
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) {<br>if (n > 0) {<br>return "Positive";<br>} else if (n<br>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<br>Entry([Entry]) --> S1{S1: n > 0}<br>S1 -- True --> S2[S2: return 'Positive']<br>S1 -- False --> S3{S3: n S4[S4: return 'Negative']<br>S3 -- False --> S5[S5: return 'Zero']<br>S2 --> Exit([Exit])<br>S4 --> Exit<br>S5 --> Exit<br>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<br>Entry([Entry: parameter n]) -->|Data: n| S1[S1: n > 0]<br>Entry -->|Data: n| S3[S3: n<br>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<br>Entry([Entry]) --> S1[S1: n > 0]<br>S1 -.->|True| S2[S2: return 'Positive']<br>S1 -.->|False| S3[S3: n |True| S4[S4: return 'Negative']<br>S3 -.->|False| S5[S5: return 'Zero']<br>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<br>%% Control Dependencies<br>Entry([Entry]) -.-> S1[S1: n > 0]<br>S1 -.->|True| S2[S2: return 'Positive']<br>S1 -.->|False| S3[S3: n |True| S4[S4: return 'Negative']<br>S3 -.->|False| S5[S5: return 'Zero']
%% Data Dependencies<br>Entry ===>|n| S1<br>Entry ===>|n| S3
classDef cd stroke-dasharray: 5 5;<br>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...