Decompiler Construction: Chapter 16 Memory Inferencing Safely
This is the most unsafe pass and should be walked through with caution!
Now that control flow is structured and basic SSA types are resolved, we must tackle the most unsafe aspect of decompilation: memory.
Memory Methodology
At the machine level, memory is a flat, untyped array of bytes. Reconstructing meaningful variables, structures, and arrays requires mapping abstract memory operations back into discrete, typed objects.
Like control flow passes, memory inferencing operates iteratively. However, memory transformations are very unsafe. An incorrect assumption about memory layout or aliasing will silently corrupt data flow and invalidate all future analysis.
Therefore, memory transformations must be strictly conservative:
- If an access pattern is ambiguous, it must remain abstract.
- Transformations must only apply when disjointness (non-overlapping memory) is mathematically proven.
- Over-approximation of types is preferable to under-approximation.
Failure to enforce conservative operations during memory inferencing will result in invalid data flow reconstruction and incorrect output code.
Alias Analysis and Safety
Before any pointer-based memory access can be folded into a discrete variable or struct field, we must establish alias constraints. If two pointers can potentially point to the same memory location, they may-alias. If they definitely point to the same location, they must-alias.
If P1 and P2 may-alias, a store to P1 invalidates any cached SSA value read from P2.
Safest Strategy
The safest strategy is to cover every control flow path while fuzzing every single variable and memory input and building diagnostic based off its data. This trade-offs speed for correctness.
Algorithm
The standard approach for computing safe alias sets is Andersen’s Points-To Analysis, which builds a constraint graph of all pointer assignments. Because Andersen’s is flow-insensitive and inclusion-based, it provides a highly accurate but computationally heavy baseline.
For faster, albeit less precise bounds, Steensgaard’s algorithm (unification-based) can be used as a fallback.
Time complexity:
- N = number of statements in the IR
- α = inverse Ackermann function
With Steensgaard’s Unification: O(N α(N)) (Near-linear) With Andersen’s Inclusion: O(N³) (Cubic worst-case)
Pseudo-code for Constraint Generation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
INPUT:
IR in SSA form
List of memory regions
OUTPUT:
Points-To Graph (Nodes = Variables/Regions, Edges = "points-to" relations)
STEP 1: Initialize Constraints
{
for each statement S in IR:
if S is "A = &B": // Address-of
add B to points_to(A)
if S is "A = B": // Copy
add edge B -> A in constraint_graph
if S is "A = *B": // Load
for each V in points_to(B):
add edge V -> A in constraint_graph
if S is "*A = B": // Store
for each V in points_to(A):
add edge B -> V in constraint_graph
}
STEP 2: Propagate (Fixed-Point)
{
worklist = all nodes in constraint_graph
while worklist not empty:
node N = pop(worklist)
for each successor S of N in constraint_graph:
old_set = points_to(S)
points_to(S) = union(points_to(S), points_to(N))
if points_to(S) changed:
worklist.add(S)
}
Aggregate Type Reconstruction (Structs and Arrays)
Once alias constraints ensure safe bounds, we can infer structures. This is done by tracking offsets from a common base pointer.
To infer struct safely the base pointer needs to be regioned out by fuzzing every path in execution and result.
Offset Accumulation Example
Every SSA pointer value must track its algebraic derivation from a base pointer.
Example IR:
1
2
3
4
5
R1 = alloc(32)
R2 = R1 + 8
*R2 = 42
R3 = R1 + 12
*R3 = 0
We can safely model this in IR by:
1
2
3
R1 = lura_structs(alloc(32));
lura_struct<8, 4>(R1) = 42;
lura_struct<12, 4>(R1) = 10;
Where lura_struct = lura_struct<Offset, Size(added to offset)>
A C code emissions would result in:
1
2
3
4
5
6
7
8
9
struct some_struct {
uint8_t pad_0[8]; // Offsets 0x0 to 0x7 (8 bytes)
int32_t field_8; // Offsets 0x8 to 0xB (4 bytes)
int32_t field_C; // Offsets 0xC to 0xF (4 bytes)
uint8_t pad_10[16]; // Offsets 0x10 to 0x1F (16 bytes)
};
struct some_struct* R1 = (struct some_struct*)malloc(32); // R1 = lura_structs(alloc(32));
R1->field_8 = 42; // lura_struct<8, 4>(R1) = 42;
R1->field_C = 10; // lura_struct<12, 4>(R1) = 10;
Further external analysis is needed for meaningful member names.
Next Chapter: Chapter 17 - Lowering IR to Readable and Executable Code
Prev Chapter: Chapter 15 - Deobfuscation Mixed Boolean Arithmetic and Opaque Predicate Removal