Skip to content

Constraint-Guided Multi-Agent Decompilation for Executable Binary Recovery

🕒 Published (v1): 2026-04-27 01:28 UTC · Source: Arxiv · link

Why this paper was selected

Constraint-guided multi-agent decompilation improves binary recovery compilability

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

Agent4Decompile is a multi-agent framework that recovers re-executable C source from compiled binaries by routing decompiled code through a three-level constraint hierarchy (syntax → compilation → execution), with a specialized LLM repair agent at each level. On 1,641 ExeBench binaries it achieves 40–46% re-executability, improving baseline decompiler output by 18–28 percentage points. A key finding is that compilation success (99–100%) does not imply behavioral correctness (32–42%): execution-level validation is essential.

Problem

Existing decompilers (Ghidra, IDA Pro, RetDec) produce code with only 22–26% re-executability—syntactic errors, type mismatches, and semantic divergence prevent the output from being recompiled and run correctly. Prior LLM-based approaches operate single-pass without iterative feedback, and cannot jointly address the three distinct error classes (syntax, type, behavioral) because each requires different diagnostic signals.

Method

Agent4Decompile frames decompilation refinement as progressive search-space reduction through a constraint hierarchy \(\phi_1 \subset \phi_2 \subset \phi_3\):

  • L1 (Syntax): \(\phi_1(C) \triangleq \text{parse}(C) \neq \bot\) — GCC -fsyntax-only, errors truncated to 500 chars fed to a SyntaxAgent.
  • L2 (Compilation): \(\phi_2(C) \triangleq \phi_1(C) \wedge \text{compile}(\text{parse}(C)) \neq \bot\) — GCC with -Wall -Wextra -Werror, type and linkage diagnostics fed to a CompilationAgent.
  • L3 (Execution): \(\phi_3(C, T) \triangleq \phi_2(C) \wedge \forall (i,o) \in T: \text{exec}(\text{compile}(C), i) = o\) — behavioral oracle from original binary; up to two failing test cases with unified diffs and a diagnostic checklist fed to an ExecAgent.

The Validate function returns (level, errors); the main loop calls Agent_â„“(C, E) and iterates up to \(N=7\) times. Agents are stateless (no repair history), output only corrected C (no chain-of-thought), and use DeepSeek V3.2 at temperature 0.0. Multiple binaries are processed in parallel via ProcessPoolExecutor with caching of decompiler outputs and oracles.

Key Contributions

  • Identification that a 57–68 pp gap exists between compile rate (99%) and re-executability (32–42%), motivating multi-level validation.
  • Agent4Decompile system: a three-level constraint-guided multi-agent refinement loop over three heterogeneous decompiler backends (Ghidra, Angr, RetDec) via a unified decompiler wrapper interface.
  • Largest decompilation experiment to date: 1,641 ExeBench binaries across four optimization levels (O0–O3) and three decompiler architectures.
  • Ablation confirming L3 execution feedback is critical; compile-only approaches plateau well below behavioral correctness.

Results

  • 157-binary benchmark: re-executability 50.3% (Ghidra), 45.2% (Angr), 43.3% (RetDec) vs. baselines of 22.3%, 24.8%, 25.5% — improvements of +28.0, +20.4, +17.8 pp.
  • vs. state-of-the-art: Agent4Decompile 50.3% vs. single-pass LLM refinement 35.2% (+15.1 pp) vs. fine-tuned LLM4Decompile-Ref 12.1% (+38.2 pp).
  • Compile-only ablation (L1+L2): 99–100% compilation rate but only 32–42% re-executability, confirming L3 is essential.
  • 1,641-binary benchmark (scalability): 40–46% re-executability, averaging 1.5–2.3 iterations per binary; O0 average 45.5% vs. baseline 25.6%.
  • Most successful refinements converge within 2–3 iterations; cases failing at iteration 5 rarely succeed with more.

Limitations

  • Targets only stripped x86-64 ELF binaries compiled from C; obfuscated binaries and non-x86 architectures are excluded.
  • Assumes test inputs are available (from domain knowledge, fuzzing, or LLM generation); test generation quality is not systematically evaluated.
  • Behavioral equivalence on a finite test suite is a proxy for semantic equivalence, not a guarantee.
  • Stateless agents cannot learn from prior repair failures within a refinement trajectory, risking repeated mistakes.
  • Evaluation uses ExeBench functions (isolated functions with main()), not full programs with complex inter-procedural dependencies.

Relevance to Harnesses / Meta-Harnesses

Agent4Decompile is a textbook example of a validation-driven meta-harness: it wraps multiple decompiler backends behind a unified interface and orchestrates specialized sub-agents through a deterministic, multi-level feedback loop—exactly the pattern of a harness that pipelines tools and agents with structured error routing. The three-level constraint pipeline (\(\phi_1 \to \phi_2 \to \phi_3\)) demonstrates how a harness can compose heterogeneous validators (parser, compiler, execution sandbox) into a progressive refinement loop, each validator feeding structured signals to the appropriate repair agent. The caching, parallelism via ProcessPoolExecutor, retry-with-backoff on API failures, and extensible decompiler/LLM backend interfaces are all hallmark meta-harness engineering concerns. For harness researchers, this paper provides a concrete case study of how to assign agent specialization by constraint level rather than by task phase, and shows quantitatively that the harness's choice of validation signal (execution vs. compilation) dominates performance.