CiRCLE: Recovering Complex Data Structures in Binaries beyond Fragmentation

Zeyu Gao, Junlin Zhou, Songtao Yang, Chao Zhang�Tsinghua University · Sichuan University · Zhongguancun Laboratory�IEEE S&P 2026

Problem: Decompilation Loses Data Structures

• Decompilers (IDA Pro, Ghidra) recover control flow well, but user-defined data structures are lost in stripped binaries�Pseudocode degrades into raw offsets, casts, and generic pointers (e.g., *(a1 + 16))�Field and hierarchy semantics disappear, hiding the program's real data model

Examples of structure representation in decompiled pseudocode

Why Recovery Is Hard: Three Bottlenecks

1. Local fragmentation: evidence breaks once accesses go beyond simple one-hop forms. �🡺 *(*(base + off1) + off2) should be base🡪field1🡪field2���
2. Global fragmentation: program-wide aggregation collapses under polymorphism �🡺 forcing type equality creates conflicts or degrades to void*�����Residual cases: dynamic offsets and irreconcilable conflicts cannot be resolved by static rules alone�🡺 *(base + index)

memset(struct * A dest, …)

memset(struct * B dest, …)

dest🡪field0: int

dest🡪field0: char

Limitations of Prior Work

• HyRES / TypeForge: depend on canonical local access forms�🡺 evidence for computed, multi-hop accesses is lost�TRex: observes low-level operations but does not consistently aggregate them across procedures�ReSym: open-ended LLM generation is unstable and hard to validate �🡺 plausible but wrong layouts

Limitations of Prior Work

• HyRES / TypeForge: depend on canonical local access forms�🡺 evidence for computed, multi-hop accesses is lost�TRex: observes low-level operations but does not consistently aggregate them across procedures�ReSym: open-ended LLM generation is unstable and hard to validate �🡺 plausible but wrong layouts�Common root cause: structural evidence is fragmented before global reasoning even begins

How Does the Author Solve the Problem?

1. Local fragmentation: evidence breaks once accesses go beyond simple one-hop forms. �🡺 *(*(base + off1) + off2) should be base🡪field1🡪field2���
2. Global fragmentation: program-wide aggregation collapses under polymorphism �🡺 forcing type equality creates conflicts or degrades to void*�����
3. Residual cases: dynamic offsets and irreconcilable conflicts cannot be resolved by static rules alone�🡺 *(base + index)

Build MOSAIC graph to maintain the information

Bottom up aggregation + Top-down consolidation

Use LLM for more chances

CiRCLE: A Staged Recovery Framework

• One shared evidence substrate: every stage reads and writes the same MOSAIC graph�Deterministic static core resolves most cases; the LLM touches only the residue�Recovered structures are imported back into the decompiler (IDA Pro plugin)

Stage 1 in Depth (1/2): Building the MOSAIC Graph

The MOSAIC Graph?

• MOSAIC (Memory Operation SAtellite Interconnection Chart), one graph per function�Computed and intermediate pointer expressions become first-class nodes�OFFSET / DEREF / REF edges capture memory semantics; SHARE records compatibility with direction and context�Second-hop and transitive accesses stay attached to the same intermediate base

How *(a1+4) = 456 becomes graph facts:

a1

a1 + 4

*(a1 + 4)

#456

OFFSET(4)

DEREF

SHARE

The MOSAIC Graph?

• MOSAIC (Memory Operation SAtellite Interconnection Chart), one graph per function�Computed and intermediate pointer expressions become first-class nodes�OFFSET / DEREF / REF edges capture memory semantics; SHARE records compatibility with direction and context�Second-hop and transitive accesses stay attached to the same intermediate base

Stage 1 in Depth (2/2): Per-Base-Pointer Local Drafts

• Candidate nomination over-approximates: any pointer-like node qualifies �🡺 direct (*p), offset (*(p+10)), or transitive dereference via SHARE���������One local draft per base pointer; nested children are processed before their containers (local reverse topological order)�Slot-address rule: type the slot (*b or b+δ) first; �🡪 if *(base + 4) is int, then this base+4 is slot which contains int�🡪 if c = base + 8 and c is struct C type? 🡺 base + 8 is slot which contains struct C type�No cross-base merging inside a function; that decision is deferred to global aggregation

It can generate the draft of types; based on MOSAIC graph

Stage 1 in Depth (2/2): Per-Base-Pointer Local Drafts (Example)

Stage 2: Conflict-Aware Global Aggregation

• Local drafts flow along MOSAIC edges and are aggregated program-wide�Incompatible layouts are kept separate instead of collapsing into void*

Stage 2 in Depth (1/2): Bottom-Up Propagation

• Call graph → SCC condensation → reverse topological order: �callees are processed before callers; recursive cycles iterate to a fixed point�Constraints flow backward: v1 = v2 pushes v1's layout to v2; �callee parameter → caller argument; return value �Conflict detector: �equal offsets require equal sizes; partial range overlap is a definitive conflict; full containment is allowed

Stage 2 in Depth (2/2): Top-Down Consolidation & Pruning

• Builds the Equivalence Class Graph (ECG): �nodes = per-function type-sharing classes / edges = caller-to-callee argument flow�DSU (Disjoint Set Union)-based consolidation in topological order: �a class merges with its callers only if all layouts remain conflict-free�- Merge success = monomorphic chain unified into one shared structure�- Merge failure = polymorphic boundary is preserved (LLM confirms genuinely ambiguous cases)�Final pruning removes over-approximation artifacts, e.g., singleton structs created from **p accesses

Stage 3: Bounded LLM Refinement

• Triggered only for residual hard cases left unresolved by the static core�LLM sees a localized evidence package isolated on the MOSAIC graph — never the whole binary�On failure, CiRCLE keeps the deterministic static result — no hallucinated layouts

LLM proposes structure

Apply in decompiler

Validate pseudocode

Accept / Fallback

retry — up to 4 rounds

Stage 3 in Depth: Trigger Tasks and the Validation Loop

• Task 1�Dynamic offset refinement: for *(base+i*8) patterns, the LLM either rejects the candidate as a false positive or proposes a complete definition (e.g., base[i].field arrays)�Task 2 �Merge conflict resolution: decides between a legitimate common base and a true union, given layouts, a static conflict report, and before/after pseudocode�Static heuristics filter obvious cases first; only genuinely ambiguous ones reach the LLM�Loop: �propose → import into decompiler → validate typed pseudocode for anomalies; re-checked on previously processed functions using the same structure�Four-round budget exhausted → refinement discarded, deterministic static result kept

Evaluation

• Four datasets: OSPREY, SPEC 2006, SPEC 2017, and 570 real-world binaries (140,000 functions)�Outperforms specialized tools : HyRES, TypeForge, TRex, ReSym
• Frontier models : GPT-5.2, DeepSeek-V3.2
• Ablation study: the three stages play distinct, complementary roles
• Ground Truth: Max Recoverable Truth (MRT)�🡺 Only cover the variable which can be reached from a binary (/w data-flow analysis on an unstripped binary)

​

Metric

• Structure Identification (SI) : Precision / Recall of identification of structure (struct, union, array?)
• Layout Recovery (LR) : Each layout with <offset, size> � - Recall: How many slots are recovered?� - Precision: How many slots are identified?
• Relationship Recovery (RR) : Recover the relationship between structures (like a pointer?)� - Upper Bound: It can find the relationship?� - Lower Bound: It can recognize the target structures layout?

Metric Example

Results

Ablation Study

Conclusion

• Preserve evidence early: the expression-level MOSAIC graph prevents local fragmentation�Aggregate with conflicts in mind: compatibility, not forced equality, survives polymorphism�Use LLMs as a scalpel: bounded, validated, and always backed by a deterministic fallback�Open source: github.com/vul337/CiRCLE (IDA Pro plugin)