WorksComputer Science
DeCompCert: A Verified Decompiler for CompCert-Generated AArch64
Abstract
DeCompCert is a Rocq-verified decompiler for AArch64 assembly generated by CompCert. It reconstructs CompCert C through nine reverse passes, combining deductively verified transformations with translation validation. Untrusted OCaml and Datalog analyses propose candidate reconstructions, while verified validators accept only candidates that satisfy the required semantic correspondence. The composed correctness theorem guarantees that every defined, safe behavior of an accepted C reconstruction is matched by the input CompCert assembly; under a safety assumption, the two programs are observationally equivalent. We evaluate DeCompCert on approximately 2.16 million lines of C. With exact function and call signatures, it reconstructs and recompiles all 3,173 eligible contexts under both unoptimized and optimized CompCert pipelines. Without retained signatures, its cumulative inference portfolio validates 2,606 of 3,164 contexts (82.4%), while the platform-plus-IDA configuration validates 2,407 contexts (76.1%). Native execution and output-quality experiments further evaluate the generated C and characterize the remaining limitations in signature recovery and source resemblance.
Introduction
Decompilation is the process of inferring source code from low-level (typically object- or assembly-level) code. It plays a key role in reverse engineering, binary analysis, and instrumentation [11, 51]. In this work, we study a precisely scoped, useful instance of this problem: recovering C from AArch64 artifacts produced by the verified CompCert compiler. Such recovery supports auditing deployed CompCert-built software, inspecting certified artifacts whose source is no longer available, and reusing source-level analyses or instrumentation. Reasoning directly about assembly is challenging because compilation removes much of the structure and semantic information originally present in the source program. For example, function prototypes are stripped; the calling convention identifies possible argument and result registers, but does not tell us whether their values are integers, pointers, or parts of higher-level aggregates. Some constructs, such as variable names, simply cannot be recovered; thus, any decompilation is essentially a representative of some equivalence
Authors’ Contact Information: Swarn Priya, Washington State University, USA; Basesh Ammanaghatta Shivakumar, Washington State University, USA; Thomas Gilray, Washington State University, USA; Kristopher Micinski, Syracuse University, USA. class of source-level terms. For the CompCert-generated inputs considered here, decompilation is sound when every defined observable behavior of the synthesized source term is exhibited by the supplied typed CompCert Asm program. Production decompilers such as IDA Pro [19] and Ghidra [28] do not provide end-to-end soundness guarantees, and empirical studies have identified semantically incorrect outputs [25, 57]. The synthesized high-level code often requires cleanup via an iterative process of manual fixups (to types, variable names, etc.). While this may suffice for reading the code, it precludes scenarios where the decompiled program is used as the basis for subsequent analysis, instrumentation, or hardening.
In this paper, we present, to our knowledge, the first end-to-end sound decompilation of CompCert-generated AArch64 to C via translation validation [29, 32]. The essence of our approach (§ 3) is to separate generation and checking. DeCompCert uses CompCert’s intermediate representations [23] to give semantics to progressively higher-level reconstructions. Starting with Asm, we reconstruct the inputs of CompCert’s passes using untrusted lifters with certified validators or directly verified Rocq reconstruction [47]. Other transformations require search, for which unsound Datalog-based analyses [10] propose candidates that validators proved sound in Rocq subsequently accept. DeCompCert then works by composing each of the certified passes together: as we lift to progressively higher-level IRs, each validated higher-level artifact becomes the input of the next pass, ultimately yielding a Csyntax program which has been proven to simulate its assembly-level equivalent. DeCompCert requires a typed, unexpanded CompCert Asm program; its correctness theorem does not require source-derived function prototypes. The theorem unconditionally provides a forward simulation from reconstructed Cstrategy semantics to the input Asm artifact; when the program is safe, we also show exact observational equivalence.
Our evaluation deliberately separates two questions. Given correct function and call signatures, DeCompCert reconstructs, certifies, and recompiles all 3,173 eligible contexts across sixteen application groups and both CompCert pipelines. This 100% result measures reverse-pipeline completeness. Starting instead from CompCert-emitted assembly without retained signatures, DeCompCert inference alone accepts 1,874 of 3,164 contexts (59.2%). This lower rate measures the additional challenge of recovering interfaces absent from assembly text, not a failure of the verified reverse passes. Checked platform proposals raise coverage to 2,218 (70.1%); configurations adding checked Ghidra or IDA proposals reach 2,325 (73.5%) or 2,407 (76.1%), respectively. The cumulative portfolio reaches 2,606 (82.4%) with additional reconstruction improvements and longer runs. All configurations use the same validator boundary. On the shared fourteen-application scope, DeCompCert’s first inferred signature matches 40.9% of held-out CompCert signatures, compared with 28.6% for Ghidra. These measurements distinguish first-choice signature agreement from complete chains accepted by the proved validators. A failed or exhausted search produces no unchecked result.
Contributions. This paper makes the following contributions:
Verified and compositional decompilation. DeCompCert reverses nine CompCert transformations using directly verified reconstruction and translation validation. We prove the correctness of both the individual passes and their complete composition. Whenever the whole decompiler accepts, a machine-checked theorem guarantees that every defined observable behavior of the reconstructed C program is matched by the supplied Asm program.
Inference-guided reconstruction. Application-wide Datalog (Ascent [34, 35]) analyses recover stack and register relationships, types, layouts, and function-signature candidates. DeCompCert can begin from assembly text without retained source signatures: complete typed-Asm assignments are proposed from register and stack accesses interpreted under the ABI, checked target-platform declarations, and independently bound Ghidra or IDA signatures, then passed
through the unchanged proved validators. The same whole-decompiler theorem applies to every accepted reconstruction relative to its inferred typed Asm input.
Implementation and evaluation. From CompCert-emitted assembly without retained signatures, DeCompCert alone accepts 59.2% of configured contexts; platform proposals raise coverage to 70.1%, configurations adding Ghidra or IDA reach 73.5% or 76.1%, and the cumulative portfolio reaches 82.4%. A separate exact-signature oracle baseline accepts all 3,173 eligible contexts at
-O0,-O1, and-O2(the latter two use the same CompCert optimized pipeline); this isolates reconstruction coverage and is not the operational input model.Evaluation of reconstructed-code quality. We measure source similarity across 45,660 matched function instances, compare a fixed subset with Ghidra, and evaluate how Ascent-guided type and layout recovery changes the reconstructed code.
Formal Guarantees for Sound Decompilation
We explain our approach by way of example. Figure 1 shows a small C function containing a call, a conditional, and two return paths. Although the source is simple, compilation removes most of its explicit structure. The argument , initially passed in register x0, is moved to the callee-saved register x19 so that it remains available after the call to compute; the returned value then occupies x0. These registers no longer carry the names or roles of the corresponding source variables. The source condition is represented by the inverted branch cbnz w19, L1; furthermore, return finish(y) is translated as b _finish, which must be recognized as a tail call. The expression survives only as an addition over physical registers. The complete assembly also contains stack-frame allocation and callee-save operations with no direct source-level counterparts [2, 3].

Figure 1. Abridged AArch64 compilation of process. Stack-pointer adjustments, the initial save of X19, return-address preservation, and CFI directives are omitted to emphasize the data and control flow.
Traditional decompilation is analysis-directed: heuristics reconstruct higher-level code informed by the results of a static analysis. As an example, consider the recovery of function prototypes from low-level code. In the assembly, function prototypes are absent, but propagating known information can help infer them: the use of w19 in cbnz suggests a 32-bit argument to process; the subsequent addition uses the value returned in w0 by compute, suggesting an integer result; and the tail branch to finish connects the outgoing register state with another function interface. Based on the result of these analyses, DeCompCert infers a candidate decompilation consistent with the observed analysis facts. But crucially, DeCompCert does not require analyses or transformations to be sound: instead, DeCompCert uses certified validators to establish a simulation between the low- and high-level IRs [45]. For each pass, DeCompCert’s validator either accepts or rejects the lifting from lower- to higher-level code. Using CompCert’s semantics [23], we prove that, if the validator accepts, then the high-level fragment simulates its low-level equivalent.
No Search Required: One-to-One Liftings
Even when reversing, some compiler passes are functional in flavor; when low-level constructs correspond one-to-one with higher-level constructs, we proceed precisely as CompCert does: by writing functions in Rocq [47], with correctness established by proving a simulation between the source and reconstructed programs. Let be a reconstruction pass that transforms a lower-level program into a higher-level program . We prove that reconstruction establishes a simulation:
The proof defines a relation between execution states of the reconstructed and lower-level programs. We establish three main properties:
Initial-state correspondence. Every initial state of is related to an initial state of .
Step simulation. For every pair of related states, an execution step of can be matched by an execution sequence of with the same observable trace, preserving . Unmatched silent steps decrease a well-founded measure.
Final-state correspondence. If a state of is final, its related state is final with the same result.
Together, these lemmas establish a forward simulation. Writing for observable behavior, for a non-wrong behavior, and for CompCert’s behavior-improvement relation [44]:
Unlike translation validation [29, 32], correctness is established directly for the reconstruction algorithm rather than by checking each candidate against an existing compilation theorem.
Translation Validation in Reverse
Decompilation inexorably confronts the case where there are numerous plausible higher-level programs potentially consistent with a lower-level program (e.g., multiple looping constructs), potentially infinitely many (e.g., in the case of variable name identification). Traditional decompilers often employ tactics such as ranking candidates via heuristics and choosing the best supposed match. Instead, we employ translation validation to validate each proposed candidate. Translation validation is a well-known approach to constructing certified compilers by chaining together a set of validators which establish that properties in the high-level fragment carry over to the low-level fragment [29, 48]. For example, CompCert’s register allocator is implemented via translation validation: the register allocator need not be verified, but a certified validator checks the transformation from virtual registers to physical registers and stack locations [33]. Let be a CompCert compilation pass from a higher-level language to a lower-level language . Given a supplied lower-level program and a reconstructed candidate , the validator checks . Each validator establishes a pass-specific certified correspondence . We then prove that this correspondence implies a simulation: .
Once the typed Asm input is fixed, reconstruction and checking can be separated. For a compiler pass , an exact round-trip validator establishes
Exact equality is one certification mechanism. Register allocation instead uses CompCert’s allocation relation: a proved validator checks an unverified allocator’s transformation from pseudo-registers to physical registers and stack locations, including spills and reloads [33]. Source validators compare modulo specific proved normalizations. Directly verified passes construct a state relation and prove initial-state, step, and final-state correspondence. Silent administrative steps require a decreasing measure to rule out unmatched infinite stuttering. These mechanisms have different local proofs but must supply a continuous simulation path for the actual connected output.
Decompiling CompCert
DeCompCert’s high-level architecture is sketched in Figure 2. Our implementation begins with a trusted front end that parses CompCert-emitted assembly text, reverses instruction expansion, and constructs CompCert’s typed, unexpanded Asm representation. Precisely identifying reachable instructions in arbitrary binaries is undecidable in general [15]; we treat certified binary lifting [49, 50] as orthogonal. Function and call signatures are inferred and ranked by an application-wide analysis of the assembly and target ABI. Checked platform and linked-binary proposals can augment this ranking without entering the trusted core. In every configuration, the resulting Asm program enters the same nine semantic reverse transformations shown in Figure 2; the reconstruction algorithms, validators, and semantic theorems after that boundary are unchanged.

Figure 2. DeCompCert’s high-level architecture and trusted computing base.
Whenever the composed reconstruction function returns a Csyntax program, DeCompCert establishes an unconditional guarantee that each reconstructed-C behavior is matched by a behavior of the supplied lower-level program that is at least as defined. If the reconstructed Csyntax program is safe, Section 4 strengthens this guarantee to observational equivalence. Reconstruction does not attempt to recover the exact intermediate program that originally produced the input. For example, freshly generated RTL pseudo-registers during decompilation from LTL to RTL need not coincide with those of the original RTL program.
Asm to Mach
Asm is CompCert’s representation of target assembly, AArch64 in our case. Our input is its unexpanded form, which still includes pseudo-instructions for actions such as allocating and releasing a stack frame. Mach is the intermediate language immediately before assembly generation [23]. Each function is a linear sequence of instructions over machine registers, with explicit labels, branches, and concrete stack offsets. Mach retains a more abstract view of operations, calls, and returns: a single Mach instruction can correspond to several Asm instructions.
Our Asm-to-Mach decompiler reconstructs candidates by recognizing the instruction sequences emitted by Asmgen. For example, one Mach conditional branch can become an Asm comparison that sets condition flags, followed by a branch that tests those flags. Because an assembly pattern may admit several Mach reconstructions, we propose multiple candidates for subsequent validation. Our Asm-to-Mach validator reruns CompCert’s Asmgen pass on the reconstructed Mach program . The validator accepts only if the result is exactly the supplied unexpanded Asm program :
Validator soundness follows by unfolding the executable check and using decidable equality of complete Asm programs. We then apply CompCert’s existing Asmgen correctness theorem, which gives a forward simulation from the semantics of to the semantics of . Appendix A gives the local semantic-preservation statements and proofs.
Reconstructing Stack Frames: Mach to Linear
The Mach-to-Linear pass reverses CompCert’s stack layout pass, which transforms Linear into Mach by assigning concrete stack-frame offsets to abstract stack locations and inserting instructions to save and restore callee-saved registers. It also adjusts stack-relative operations and determines the final stack-frame size. In Linear, stack locations are represented abstractly as , where identifies the stack region, is the offset, and is the value type. In the process example (Figure 1), Stacking saves the caller’s value of x19 at stack offset 16 and restores it before both exits: the tail call to finish and the return. These three stack operations are introduced by Stacking and have no counterparts in the Linear program.
Callee-save facts and rules. To help us infer the stack layout, we use a logic program written in Datalog [34]; our Datalog program implements the rules in Figure 3. The rules make use of facts supplied by an OCaml-based extractor, which traverses the Mach instruction and transforms them into facts that record stack stores (setStack) and loads (getStack), returns, tail calls, instruction positions, and callee-saved registers. In the rules, is an instruction position, a machine register, a stack offset, and a memory type. The instruction order is encoded via next, and returns and tail calls are treated uniformly as exits. The rules run to a fixed point to compute the contiguous save prefix for each function entry and the restore suffix before each exit; the analysis pairs a save and restore only when their register, offset, and memory type agree. The resulting matches guide reconstruction of the Linear program, whose correctness is independently verified in Rocq.

Figure 3. Relational rules for identifying candidate save–restore pairs.
Concrete-to-abstract stack offsets. If the local region begins at byte offset 88, for example, Mgetstack 96 Tint X1 reconstructs the Linear local slot . An access in the fixed-frame area is rejected because it has no Linear stack-location counterpart. DeCompCert obtains these boundaries from a Linear skeleton that temporarily omits unresolved stack accesses, then makes a second pass to reconstruct them. Operations and addressing modes can also refer to Linear’s addressable stack data. If that region begins at fe_stack_data, the corresponding Linear-relative offset is . The implementation then applies CompCert’s existing stack-shift functions to operations and addressing modes with the negated displacement.
Recovering frame sizes. Recovering the Linear stack-data size requires a separate search. Linear records only the size of its addressable stack-data area, whereas Mach records the size of the complete activation record. Stacking also aligns the complete frame, so several nearby Linear sizes can produce the same Mach frame size. For a supplied Mach function , DeCompCert tries candidate sizes in decreasing order. For each size , it constructs a Linear function with fn_stacksize = s, recomputes the frame layout, reverses the corresponding stack-offset adjustments, and invokes the Stacking validator. The first candidate for which is accepted. Before returning a reconstructed program, we perform the same validation at the program level. For an input Mach program and reconstructed Linear program , we prove that the executable validator exactly reflects this condition: . This check covers not only reconstructed function bodies but also global variables, external declarations, public symbols, their ordering, and the main symbol. CompCert’s correctness theorem for Stacking then provides a forward simulation from the semantics of to the semantics of .
Reconstructing Control Flow: Linear to LTL
The Linear-to-LTL decompiler reverses CompCert’s linearization pass, which transforms an LTL control-flow graph into a sequential list of Linear instructions. In LTL, each node contains a basic block with explicit successors, whereas Linear uses labels, jumps, and implicit fall-through.
Our decompiler reconstructs the LTL control-flow graph in two passes. First, it assigns a fresh LTL node to each Linear instruction and constructs a mapping from labels to their corresponding nodes. Since a Linear label is a pseudo-instruction, a label maps to the node immediately following it, rather than to the node assigned to the label itself.
In the second pass, the decompiler reconstructs each Linear instruction as an LTL basic block with explicit successors. Ordinary instructions receive the next node as their successor. Conditional branches receive two successors: the target obtained from the label mapping and the fall-through node. Unconditional jumps become LTL branches to the corresponding target nodes. Jump tables are reconstructed by replacing their target labels with graph nodes, while returns and tail calls terminate execution without successors. Label pseudo-instructions become branch-only blocks leading to the following node. The algorithm also introduces a final sentinel node representing the position immediately after the Linear instruction sequence. Missing or duplicate labels cause reconstruction to fail, ensuring that each reconstructed branch has a uniquely determined target.
Unlike the translation-validated passes, the Linear-to-LTL reconstruction algorithm and its correctness proof are implemented entirely in Rocq. The proof relates each reconstructed LTL node to the suffix of the original Linear instruction list beginning at the corresponding position. Corresponding call and return states have the same register values and memory.
The main step proof proceeds by induction over the LTL transition. When the transition executes an actual instruction, the correspondence between LTL nodes and Linear code positions identifies the matching Linear instruction. Executing that instruction produces the same trace and re-establishes the state relation. Some LTL transitions, such as entering a reconstructed block or traversing an inserted branch-only block, do not advance the Linear program. We assign these states a natural-number rank and prove in Rocq that every such silent step strictly decreases the rank. Initial states are related, and related final states return the same result. CompCert’s forward_simulation_star theorem [45] combines these properties into a forward simulation.
Theorem 3.1 (Linear-to-LTL semantic preservation). Let be a Linear program and let
Reconstructing Register Allocation: LTL to RTL
Register allocation replaces RTL pseudo-registers with physical registers and stack slots, introducing additional moves, spills, and reloads. Reversing this transformation is challenging because the original pseudo-registers are lost, and the same physical location may hold different values across control-flow paths. We follow a translation-validation approach: an untrusted OCaml decompiler generates RTL candidates, which are checked using CompCert’s formally verified register-allocation validator [33]. Successful validation guarantees a forward simulation from the reconstructed RTL to the original LTL.
For each basic block, reconstruction carries an immutable environment that maps LTL locations to RTL pseudo-registers. A move introduced by allocation does not become an RTL computation: it returns a new environment in which the source and destination locations name the same pseudo-register. A real operation reads its operands through the current environment and binds its result location to a fresh pseudo-register. Locations first observed at a block entry receive placeholder registers for live-in values. After the control-flow graph has been explored, the output environments of predecessors are reconciled at joins and loop headers; pairs introduced for Twolong values are tracked together during this reconciliation. Finally, RTL typing and Allocation.check_function check the complete candidate against the supplied LTL function.
Reconstructing High-Level Program Structure
The remaining stages of DeCompCert reconstruct higher-level program abstractions from RTL through Csyntax. These passes recover expression trees, generic operations, addressable local variables, types, and source-level control-flow patterns when they are present in the supplied intermediate representation. RTL-to-CminorSel and CminorSel-to-Cminor use deductive verification.
Control-flow expressions. RTL represents a function as a control-flow graph in which each node contains one operation, load, store, call, branch, builtin, jump table, or return. CminorSel instead combines expressions into statements. The verified RTL-to-CminorSel pass reconstructs an expression or statement for each RTL node and uses labels and gotos to preserve joins, back edges, and explicit successors. Loads and stores retain their memory chunks and addressing modes; calls retain direct or indirect targets and argument order; jump tables become CminorSel switch statements with the same indexed successors.
An RTL transition can correspond to several CminorSel transitions. For example, the RTL node r3 = r1 + r2 is reconstructed as an assignment whose operands are Evar r1 and Evar r2, followed by a goto to the successor label. The assignment performs the RTL operation, while sequencing, label lookup, and the goto introduce silent administrative steps. The direct simulation matches one RTL transition with one or more CminorSel transitions. Whole-pipeline correctness also requires a simulation from the reconstructed CminorSel program to RTL. We establish this using a phase-indexed state relation. Each reconstructed operation is matched by its corresponding RTL instruction, while intermediate execution steps may stutter only when a well-founded index decreases. A register-environment invariant ensures that used RTL registers agree with their corresponding CminorSel locals. Evaluation-correspondence lemmas cover operations, addresses, conditions, calls, memory effects, builtins, returns, and jump-table destinations. The simulations in both directions are presented in Appendix § 11.
Instruction selection. This pass reconstructs Cminor from CminorSel. CminorSel uses target-specific operations and addressing modes, whereas Cminor represents computations using generic operators and explicit address expressions. The decompiler recursively translates CminorSel expressions and statements into Cminor. Composite selected operations may require multiple Cminor operations. A key challenge arises from expression-level constructs such as let bindings, conditional expressions, and calls, which cannot always be represented by a single Cminor expression. The decompiler introduces fresh temporary variables and statements to preserve their evaluation order. For example, the CminorSel expression let in is reconstructed as: tmp = x + 3; result = tmp * tmp;. The temporary ensures that the bound expression is evaluated only once. Fresh identifiers are chosen above all identifiers occurring in the input function to avoid conflicts with existing variables.
The reconstruction algorithm and its correctness proof are implemented in Rocq. The proof relates the original CminorSel environment to the reconstructed Cminor environment, allowing additional temporary variables while preserving the values of existing variables. It also relates expression-level let bindings to their corresponding generated temporaries. These relations are used to prove that reconstructed expressions and statements preserve evaluation order, computations, memory operations, and observable events. The proof establishes a forward simulation from the supplied CminorSel program to the reconstructed Cminor program, under explicit premises requiring defined unsigned comparisons, defined selections, and unique labels. These premises belong to this pass-local simulation direction. The complementary Cminor-to-CminorSel simulation used for the connected theorem derives the required facts from each successful Cminor step and has no global definedness premise.
Recovering addressable variables. The Cminor-to-Csharpminor decompiler reconstructs each function’s nonempty stack block as a single addressable variable. CompCert’s Cminorgen pass allocates Csharpminor addressable locals, each with an identifier and size, at offsets within a single Cminor stack block. This erases the original variable boundaries, which therefore cannot be uniquely recovered. The reconstructed variable therefore has the size of the Cminor stack block and a fresh identifier chosen above all global, parameter, and local-variable identifiers to avoid conflicts. Functions without stack space require no additional addressable variable. For a nonempty stack block, offset zero becomes the variable’s address, and each interior address becomes a constant byte displacement from that base.
The validator checks this reconstruction by recompiling the untrusted generator’s Csharpminor candidate with Cminorgen. It requires at most one nonnegative-size addressable object per function and accepts when the generated Cminor program equals the supplied program , either directly or after normalizing constant stack-address displacements with :
We prove simulations in both directions for and compose them with Cminorgen correctness; Appendix § 11 gives the validator and proof. Successful validation therefore establishes a forward simulation from the reconstructed Csharpminor program to the supplied Cminor program.
The single-object check is a conservative output-quality and safety guard. The current forward-simulation proof does not use it: Cminorgen correctness and the proved simulations suffice. We retain the check to avoid extra object boundaries that can introduce additional source-level undefined behavior and make the safety premise for observational equivalence harder to establish.
Recovering types and structured statements. The Csharpminor-to-Clight decompiler reverses Cshmgen. It must recover types erased by lowering and recognize the blocks, loops, and numbered exits used to encode structured control flow. An OCaml extractor records type facts from signatures, operations, memory accesses, and assignments; Ascent propagates these facts across related variables. The inferred facts guide candidate declarations and expressions. Addressable objects retain their byte size but not their source element type. Access widths and scaled addresses therefore guide array candidates, with a byte array used when the access patterns do not suggest a more precise layout. Recognized block/loop/exit patterns can become Clight conditionals, loops, breaks, and switches. However, the connected RTL-to-CminorSel lifter emits one labeled statement per CFG node and connects nodes with gotos. It therefore does not supply these structured patterns to the later recognizer. The evaluated end-to-end pipeline retains label/goto control flow and recovers no structured loops or source-level switches; the recognizer applies only when such patterns are present in a separately supplied candidate.
The difficult part is that exact round-trip equality is too restrictive. Discarded call destinations and the representation of narrow ABI values can make the generated Csharpminor program differ syntactically from the supplied one, . The validator therefore recompiles the candidate with Cshmgen and accepts only when the complete result belongs to a finite family obtained using proved discarded-result, narrow-value, and parameter-entry transformations. Each transformation has a reverse simulation, so accepting these additional forms does not weaken soundness. A separate arity check is necessary because Cshmgen retains actual variadic arguments but can erase whether a prototype declared the correct fixed prefix.
The OCaml and Ascent analyses remain untrusted. Successful validation implies
Thus, wrong inferred types or structures can cause rejection but cannot make an accepted reconstruction unsound. Appendix A defines the accepted normalizations and gives the proof.
Recovering recompilable C. The accepted Clight reconstruction guides the final recovery of a Csyntax program , including source-level expression grouping, loop initializers, short-circuit expressions, and comma expressions. The generator is untrusted, so the final validator recompiles the candidate through SimplExpr and SimplLocals. It accepts when these verified passes reproduce the complete accepted Clight program exactly, or when a fixed family of proved normalizations makes the generated program equal to it. These remove administrative skip prefixes and guarded call-result copies, and fold value-preserving assignment casts under precise constant/range checks. Their simulations are proved separately. Writing for this local check:
On the preferred source path, the Csharpminor-to-Clight validator uses the same , so this theorem closes the final adjacent boundary. If the local comparison rejects, a proved fallback instead replays the Csyntax candidate through SimplExpr and SimplLocals, applies only proved cleanup combinations, and validates the result against the reconstructed Csharpminor input. The complete composition accepts either source-side proof premise.
Recovering Function Signatures from Assembly
CompCert’s typed Asm requires signatures for functions and calls, even when the input assembly carries no type information. DeCompCert recovers these interfaces by reasoning from about functions their callers. Assembly does not determine a unique signature: a 64-bit value may be an integer or a pointer, and unused results leave the return type unconstrained. The analysis therefore ranks alternatives for reconstruction to try to validate. We first use the target calling convention to identify potential arguments and results. Reading an argument register before its first write suggests a parameter, and using a call’s result register before overwriting it suggests a returned value. A Datalog-based analysis propagates these analysis facts across direct calls throughout the application, connecting each callee’s interface to observations at its call sites. When a function forwards a call’s result, the analysis also connects their return types. These rules iterate until no new analysis information is found.
Where choices remain, platform declarations for imported functions [1, 3] and signatures proposed by Ghidra [28] or IDA/Hex-Rays [19] guide ranking. DeCompCert restricts platform declarations to actual imports and checks decompiler proposals against independently decoded function entries and direct calls. Each search candidate assigns signatures to functions and call sites together, producing a complete typed Asm program. The search starts from a default assignment, then tries individual changes and combinations in rank order, up to a fixed candidate budget. When validation rejects a function, the search prioritizes changes to related signature choices while leaving unrelated choices fixed. A successful assignment supports reconstruction through the same nine reverse passes. Acceptance establishes the typed-Asm-to-C guarantee, but does not establish that the original signatures have been recovered. An incorrect interface can still be internally consistent enough to pass validation. The theorem therefore relates reconstructed C to the selected typed assembly candidate; ensuring that this candidate faithfully represents the input assembly remains an obligation of the trusted front end (§ 4).
Establishing End-to-End Soundness
The mechanized theorem begins with a typed, unexpanded CompCert Asm program and ends with reconstructed Csyntax. Parsing textual assembly, reversing CompCert’s instruction expansion, assigning function and call signatures, decoding binaries, linking, and relocation precede this boundary. Within it, eight fixed lower/Clight checks establish simulations between adjacent CompCert semantics. At the recompilable-C boundary, the proof uses either the adjacent local Clight2 check or a verified replay from Csyntax directly to the retained Csharpminor program.
The word typed describes the Asm value consumed by the semantics; it does not require those types to be retained from compilation. This gives two layers. The trusted front end parses textual assembly and constructs the typed Asm program, including its calling interfaces. The certified core then relates that typed Asm program to the reconstructed C program. DeCompCert mechanizes the second layer; proving the parser is outside the scope of this work. In the signature-free mode of § 3.6, candidate interfaces are inferred by application-wide assembly analysis, optionally augmented with checked platform and linked-binary proposals, before this formal boundary. They are then examined through validation and native experiments.
The theorem below is universally quantified over , so the same typed-Asm-to-C proof applies whether its signatures were retained or inferred. This quantification must not be read as a proof of the first front-end layer. An inferred candidate can be internally consistent and still misrepresent an interface that is unobservable in the text. In that case the theorem remains about the candidate typed Asm semantics, rather than the external executable semantics.
Composing Local Guarantees
Let follow the first eight reconstruction stages, and let
denote their certified interfaces. For a translation-validated pass, OK includes acceptance by the proved validator. The connected driver retains both the reconstructed Csharpminor and Clight programs for the source-boundary procedure. That procedure returns Csyntax only when either the preferred local Clight2 validator accepts or the verified Csyntax-to-Csharpminor replay accepts. We write for the resulting error-propagating composition. Thus states that all eight fixed checks accepted, one proved source-boundary mode accepted, and every stage consumed the actual output retained from its predecessor.
Composition requires a continuous semantic path from Csyntax to Asm. DeCompCert establishes both relevant simulation directions at the RTL, CminorSel, and Cminor boundaries. The decompilation-oriented theorems express the local relationship between the input and reconstruction. The complementary compiler-oriented simulations connect Cminor through CminorSel to RTL and therefore align with the surrounding CompCert results.
The complementary Cminor-to-CminorSel simulation is the most technically demanding new proof in DeCompCert. It cannot be obtained by instantiating CompCert’s instruction-selection theorem: the supplied CminorSel program is not required to be the exact result of applying instruction selection to the reconstructed Cminor program. Reconstruction can introduce different temporary assignments, sequencing, labels, and administrative control flow. We therefore relate their executions directly. A phase-indexed relation records whether execution is evaluating setup assignments, performing the corresponding action, or following an administrative label or goto. Action phases match the RTL instruction from which the code was reconstructed; administrative phases take silent steps and decrease a well-founded measure. RTL provenance rules out effectful expression forms that the pass never produces. The same proof structure covers calls, memory operations, conditions, builtins, and jump tables without adding a global definedness premise. Appendix § 11.§ 1 gives the detailed construction.
This modular proof does not require C output to recompile into assembly that is syntactically identical to the input. Such a comparison would reject differences in temporary names, labels, register choices, and stack layout even when the programs have the required semantic relation. Instead, each boundary checks the information available at that representation and reuses a CompCert theorem. Some new complementary simulations bridge the remaining boundaries. For SQLite, the reconstructed C program compiles successfully, but the local validator rejects it because the generated Clight2 program differs from the expected one in seven narrow assignments. These differences are handled by a proved normalization at the Csharpminor level, allowing the alternative validator to accept the reconstruction.
Theorem 4.1 (Composed decompiler simulation). For every supplied unexpanded Asm program and reconstructed Csyntax program ,
Consequently, if , then the supplied Asm program has a behavior such that under CompCert’s behavior-improvement relation.
Here and throughout the end-to-end statements, denotes Cstrategy semantics , CompCert’s strategy semantics for C. It does not denote the nondeterministic Csem semantics. Atomic strategy semantics is used internally when deriving the converse simulation under the safety premise below.
The proof composes the semantic results for the actual intermediate programs returned by ; candidate-generation algorithms do not occur in its conclusion. It also does not rely on testing, equality with the unavailable original source, or recompilation into a second assembly program. In particular, the conclusion has no premise requiring a retained source signature. A candidate rejected by any checker receives no guarantee. An accepted inferred candidate receives the guarantee relative to its typed Asm semantics; establishing that this semantics is the faithful interpretation of the supplied text is a responsibility of the trusted front end.
Observational Equivalence
The composed simulation gives an unconditional compiler-style guarantee for every accepted reconstruction. For exact equivalence, CompCert’s generic results convert the simulation through atomic Cstrategy semantics because Cstrategy semantics is receptive and Asm semantics is determinate [45]. As in verified compilation, the C program must be safe: after source-level undefined behavior, its semantics does not constrain the lower-level execution [44].
Why safety is required for exact equivalence. The composed simulation theorem does not require the reconstructed C program to be safe. For every accepted reconstruction, it guarantees that every defined observable behavior of the C program is preserved by the supplied assembly. Safety is needed only for the converse direction, which establishes exact observational equivalence.
Exact round-trip validation alone does not establish safety. For example, AArch64 hardware integer division returns zero when the divisor is zero [2 SDIV, UDIV], whereas division by zero is undefined in C [20]. A reconstructed expression may therefore recompile exactly to the supplied division instruction, even though their behaviors differ when . The round-trip check establishes that the reconstruction compiles to the supplied assembly, but CompCert’s correctness theorem does not constrain the target behavior once the source encounters undefined behavior.
This limitation is inherited from CompCert itself. Proving the reconstructed C program safe rules out such undefined executions, allowing us to establish exact observational equivalence. Here, means that every behavior of is non-wrong.
Theorem 4.2 (Whole-decompiler observational equivalence). If the composed decompiler returns and the reconstructed program is safe, then it has exactly the observable behaviors of the supplied Asm program:
Safety is required only for the exact-equivalence corollary. Without this assumption, Theorem 4.1 still guarantees that every defined observable behavior of the reconstructed C program is preserved by the supplied typed Asm program. However, it does not establish the converse inclusion, and hence cannot transfer arbitrary universal behavioral properties from C to Asm. We demonstrate the stronger result on a closed recovered checksum program. Rocq verifies its complete finite C execution graph, including allocations, loads, and stores for five addressable locals, establishing safety and the result 222. The exact-equivalence corollary then establishes the same observable result for the supplied Asm program.
Connecting the extracted checker to the theorem. The preceding results compose the local pass theorems, but an executable decompiler must additionally ensure that one reported success supplies the premises from one continuous candidate chain. In particular, the OCaml search must not accidentally combine an accepted Mach candidate from one attempt, a Linear candidate from another, and readable C from a third. We therefore define and extract a single Rocq function . It receives the supplied Asm program, the proposed Mach, Linear, Clight, and Csyntax programs, and a tag selecting one of the two proved source-boundary modes. It reruns the Asm-to-Mach and Mach-to-Linear validators, recomputes every intermediate program from LTL through Csharpminor, and reruns the selected readable-source check. The mode Clight2 selects validation of the reconstructed Clight-to-Csyntax boundary, while CsharpminorReplay selects direct replay of the proposed Csyntax program to Csharpminor. The checker returns the proposed Csyntax program only when the selected connected check succeeds.
Only the programs proposed at validation boundaries appear as arguments to . The LTL, RTL, CminorSel, Cminor, and Csharpminor programs do not appear as separate arguments because checker recomputes them in sequence. Thus, the smaller argument list still checks one continuous execution of all nine reverse passes.
Theorem 4.3 (Extracted connected-checker soundness). For supplied programs , , , , and , source mode , and program returned by the connected checker,
The proof unfolds the extracted checker and considers each validation result. A successful evaluation yields the two target-validation premises, the actual outputs of all five recomputed intermediate transformations, and either the local Clight2 validation premises or the Csyntax-to-Csharpminor replay premise. These are exactly the premises of Theorem 4.1. Because every successful branch of the connected checker returns , the success equation also gives .
The OCaml driver uses this extracted function as its sole final acceptance boundary and emits the returned program rather than independently interpreting the individual validation results. It establishes that the concrete C program emitted by the executable decompiler is exactly the program covered by the composed semantic guarantee.
Trusted computing base. The trusted base of the certified core contains the Rocq kernel, the CompCert semantics, and the assumptions inherited from CompCert. OCaml and Ascent reconstruction procedures inside this boundary are untrusted because their outputs are validated. For a claim beginning at an external .s file, the textual assembly parser and the selected interface assignment are part of the trusted front end. The printer, assembler, linker, and native compilers also lie outside the theorem. Appendix § 11 gives the local statements and state relations; the supplement provides proof accounting, and the artifact contains the assumption audit.
Implementation
We implement the decompiler as an extension of CompCert 3.17, reusing its intermediate-language definitions, operational semantics, calling conventions, forward transformations, and program printers. Each reverse pass consumes a CompCert program and either returns a reconstructed higher-level program or reports that reconstruction failed. The passes can be executed independently or composed into an assembly-to-Csyntax/recompilable C pipeline.
Verified reconstruction passes are implemented and proved correct in Rocq. For translation-validated passes, OCaml performs syntax-directed reconstruction, while Ascent supports relational searches such as recovering stack layouts, calls, and signatures. These components generate candidates but are not trusted for correctness: a validator proved sound in Rocq checks every accepted result. The reverse passes are integrated into CompCert’s command-line driver through separate decompilation flags. Intermediate printers expose the reconstructed Mach, Linear, LTL, RTL, CminorSel, Cminor, Csharpminor, Clight, and Csyntax/recompilable C programs. The current implementation parses an AArch64 assembly and uses the target ABI when recovering machine-level information. When signatures are unavailable, the driver parses components independently, namespaces private symbols, constructs an application graph, and combines register-use, stack-access, and call-site facts through an Ascent fixed point. It ranks complete signature assignments and tries them under a cumulative candidate budget. Versioned Apple and GNU/Linux profiles are filtered against checked image imports, and independently decoded AArch64 entries and direct calls bind Ghidra and IDA proposals to the linked program. These sources only add untrusted candidate preferences. Each assignment produces a typed CompCert Asm candidate; no source-derived signature is consulted during this search. Parsing and candidate generation precede the mechanized semantic boundary. The complete-pipeline proof starts from each candidate Asm value and covers the nine reverse transformations through Csyntax, so the same proof applies to every accepted signature-free result.
The implementation adds approximately 52,100 lines of Rocq code beyond CompCert 3.17, excluding tests. Of these, about 33,200 lines are dedicated to proofs, validators, and reverse simulations. For the type/layout refinement evaluated in § 6.4, an analysis-only Csharpminor control-flow graph (CFG) assigns separate identities to parameter entries and assignment, call, and builtin results. It records a reaching identity only when all reachable predecessors agree. Ascent propagates field-access and stride facts through justified value copies, projecting it to declarations with one syntactic definition; resource-budget skips retain the earlier proposals. Composite declarations are shared only within flow-related families whose selected layouts, including nested pointer targets, are compatible. Identical physical fields alone do not establish a shared family or an original nominal type. Candidate ranking first compares aggregate function costs lexicographically (casts, expression nodes, and locals); only ties prefer fewer composite declarations and members. All proposals still require acceptance by the unchanged Cshmgen and final Csyntax validators.
Evaluation
We evaluate DeCompCert through four research questions, RQ1–RQ4:
RQ1 How often does DeCompCert reconstruct a complete chain from assembly without retained signatures?
RQ2 How much do checked platform and decompiler proposals improve coverage?
RQ3 Does the reverse pipeline succeed when exact signatures are supplied?
RQ4 How does the pipeline generalize to unseen inputs, and how does its C output behave and compare with the source?
RQ1: Assembly-Only Signature Inference
We start from CompCert-emitted AArch64 assembly at -O0 and the target ABI, with no source ASTs, types, or source-derived signatures. We measure how often reconstruction yields an accepted Asm-to-Csyntax chain. Most of the 3,164 contexts are translation units. Coreutils uses 132 source-bound contexts from 57 linked images; SQLite uses one whole-program amalgamation. Each configuration records its search bounds and receipts. The 3,173-context oracle in RQ3 includes nine additional OpenSSL der_*_gen.c data units. They emit no functions or calls, so the frozen signature campaign has no interface to infer and excludes them. Table 1(a) reports exact first-proposal matches (counts and percentages) out of held-out CompCert signatures; (b) reports accepted complete chains out of configured contexts. Only denotes DeCompCert alone, and Total denotes the cumulative engineering portfolio described in RQ2. Held-out CompCert signatures are used only to score proposals after inference, never to generate them. DeCompCert alone accepts 1,874/3,164 contexts (59.2%). On the shared 14-application scope (36,929 signatures), its first proposal matches 40.9% of held-out signatures, compared with 28.6% for Ghidra. This measures exact CompCert interface agreement, not the general usefulness of Ghidra’s output.
| Application | DeCompCert | Ghidra | Only | + Plat. | + Ghidra | + IDA | Total | ||
| zlib 1.3.1 | 151 | 99 (65.6%) | 81 (53.6%) | 15 | 15 | 15 | 15 | 15 | 15 |
| Lua 5.4.7 | 1,079 | 600 (55.6%) | 89 (8.2%) | 34 | 26 | 26 | 26 | 28 | 28 |
| libuv 1.48.0 | 613 | 335 (54.6%) | 116 (18.9%) | 37 | 26 | 27 | 31 | 28 | 31 |
| libpng 1.6.43 | 530 | 237 (44.7%) | 18 (3.4%) | 16 | 16 | 16 | 16 | 16 | 16 |
| Binutils libiberty | 622 | 197 (31.7%) | 165 (26.5%) | 122 | 115 | 116 | 116 | 115 | 115 |
| BearSSL 0.6 | 605 | 252 (41.7%) | 53 (8.8%) | 277 | 263 | 264 | 264 | 264 | 264 |
| OpenSSL 3.5.9 (libssl) | 3,165 | 1,501 (47.4%) | 392 (12.4%) | 94 | 73 | 73 | 76 | 73 | 76 |
| OpenSSL 3.5.9 (libcrypto) | 14,674 | 5,440 (37.1%) | 4,255 (29.0%) | 980 | 525 | 579 | 630 | 637 | 777 |
| wolfSSL 5.9.4 | 1,322 | 679 (51.4%) | 161 (12.2%) | 42 | 33 | 33 | 34 | 33 | 34 |
| Mbed TLS 3.6.4 | 2,174 | 1,103 (50.7%) | 196 (9.0%) | 108 | 85 | 87 | 87 | 87 | 87 |
| nginx 1.30.5 | 1,407 | 601 (42.7%) | 118 (8.4%) | 120 | 67 | 82 | 85 | 97 | 97 |
| LibreSSL 4.3.3 | 6,716 | 2,718 (40.5%) | 2,781 (41.4%) | 480 | 313 | 337 | 374 | 387 | 389 |
| Coreutils 9.5 | 5,819 | 2,798 (48.1%) | — | 132 | 75 | 86 | 86 | 86 | 94 |
| curl 8.8.0 | 1,740 | 691 (39.7%) | 129 (7.4%) | 213 | 165 | 173 | 174 | 178 | 178 |
| BusyBox 1.36.1 | 2,131 | 647 (30.4%) | 2,003 (94.0%) | 493 | 77 | 304 | 311 | 363 | 405 |
| SQLite 3.46.0 | 2,521 | — | 412 (16.3%) | 1 | 0 | 0 | 0 | 0 | 0 |
| All 16 applications | 3,164 | 1,874 (59.2%) | 2,218 (70.1%) | 2,325 (73.5%) | 2,407 (76.1%) | 2,606 (82.4%) |
Table 1. Signature recovery and complete-chain coverage at -O0.
RQ2: Checked Platform and Decompiler Proposals
Platform- and decompiler-generated metadata can improve complete-chain coverage by helping DeCompCert choose which signature assignments to try. We restrict platform declarations to checked imports, excluding symbols defined by the image, and check untrusted Ghidra and IDA/Hex-Rays signatures against independently decoded AArch64 function entries and calls. Every accepted chain must pass the same proved validators. Platform proposals add 344 net acceptances, raising coverage to 70.1%; the alternative configurations that also use Ghidra or IDA reach 73.5% and 76.1%, respectively. We report the platform-plus-IDA configuration as our primary assisted result: it accepts 2,407/3,164 contexts and uses no Ghidra input.
The cumulative portfolio builds on the IDA result to reach 2,606 accepted contexts (82.4%). Ranking candidates by agreement between Ghidra and IDA adds 52 contexts to the initial 2,407 acceptances. The remaining gains come from improved assembly-only reconstruction and further searches for OpenSSL and Coreutils, including searches guided by dependency profiles. Public-header proposals include only symbols referenced but not defined by each input, and some reruns use longer per-stage time bounds; the artifact records these changes and limits. Because this total combines runs with different procedures and budgets, we report it as a secondary coverage result, not a uniform ablation or a per-application maximum over the other configurations.
An accepted chain need not recover the original interfaces, since the validators check reconstruction relative to the inferred typed Asm. In the frozen 15-context zlib evaluation, 104/152 internal-function signatures and 373/449 call-site signatures match exactly, but only 3/15 accepted contexts match throughout. Among the 1,198 cumulative acceptances with comparable archived receipts, 6,809/13,373 internal-function signatures and 44,074/64,802 call-site signatures match exactly, with complete agreement in 112/1,198 contexts. We do not extrapolate from this non-random subset to the other 1,408 acceptances, which lack comparable receipts; Appendix § 11.10 describes the comparison protocol. Proposals can reduce the search needed for reconstruction, but time and candidate limits still constrain coverage. In a libuv rerun with the same implementation, candidate bound, and timeout, assembly-only inference accepts 26/37 contexts; enabling all hint sources accepts 31/37, reduces checked candidates from 1,878 to 1,365, and lowers total time from 673.5 to 590.2 seconds. This reduction comes with higher 95th-percentile latency (71.3 to 91.0 seconds); Appendix § 11.11 reports medians and counts of functions in accepted translation units. Across the evaluation, candidates fail validation because of incompatible call shapes, result types, stack layouts, or complete program interfaces, while some searches exhaust the candidate bound before finding an accepted assignment. SQLite’s 3.9 MB amalgamation does not finish even its first whole-program candidate within the time bound. Larger bounds may improve coverage by allowing more search, but every accepted chain must still satisfy the same validators.
RQ3: Controlled Exact-Signature Oracle
We compile the source with CompCert and retain its exact signatures at the assembly boundary. This oracle isolates reverse-pipeline coverage with ideal interface information. Table 2 summarizes the results; the supplement gives the per-application breakdown.
| Driver flag | Internal pipeline | Accepted | Eligible |
| -O0 | unoptimized | 3,173 | 3,173 |
| -O1 | optimized (-O) | 3,173 | 3,173 |
| -O2 | optimized (same -O) | 3,173 | 3,173 |
Table 2. Exact-signature oracle coverage.
All 3,173 eligible contexts complete the connected Asm-to-Csyntax chain and recompile with CompCert, covering approximately 2.16 million physical lines of C. CompCert 3.17 maps literal -O1 and -O2 to the same optimized pipeline, so the oracle tests two CompCert pipelines in total; receipts record each driver invocation. Native Clang [46] -O2 tests use Clang’s own optimization level. The same 83 configured inputs are rejected by the CompCert frontend under all flags, before decompilation. The smaller -O0 separate-pass experiment accepts all 2,696 eligible files at each of nine reverse boundaries (24,264 local invocations). These results show that the reverse pipeline handles CompCert’s optimized assembly with supplied interfaces. They do not establish application-scale signature-free coverage after optimization.
RQ4: Execution, Generalization, and Output Fidelity
Validator acceptance establishes a semantic relation to the supplied typed Asm. We also test the C printer, native ABI interoperability, generalization to unseen inputs, and resemblance to source. Table 3 summarizes execution and generalization; Chain/eligible reports complete connected reconstructions over eligible contexts (program/driver-flag cells for generated programs). The large wolfSSL/OpenSSL native studies, the held-out-version study, and the generated-program study start from retained typed Asm and test the reverse pipeline, not assembly-only signature inference. The fixed-fixture and mixed-zip studies below separately exercise inferred interfaces.
| Cohort | Chain/eligible | Native result |
| wolfSSL −O2 | 42/42 | 36/36 executions pass |
| OpenSSL libcrypto −O2 | 989/989 | 836/836 executions pass |
| Unseen Lua/zlib −O0 | 49/49 | 24/24 executions pass |
| Unseen Lua/zlib optimized | 7/49 | Partial outputs not linked |
| Generated programs | 236/267 | 234 match; 2 inconclusive |
| Fixed ABI fixtures, inferred | 27/30 | 23/30 native comparisons pass |
| Fixed ABI fixtures, exact | 30/30 | 29/30 native comparisons pass |
| Mixed current zlib | 10/15 | 3/3 hybrid workloads pass |
Table 3. Native execution and generalization results.
Native execution. For wolfSSL and OpenSSL libcrypto at -O2, using retained exact signatures, we compile original and reconstructed C with both CompCert and Clang, using the profile in Appendix § 11.13. All 42 wolfSSL and 989 OpenSSL contexts complete the chain. The executables pass 36/36 selected wolfSSL executions and 836/836 OpenSSL executions. The OpenSSL total comprises 824 upstream-test executions, four independent-oracle executions, and eight focused whole-pipeline executions. The upstream tests record 19,900 passing TAP assertions and no failures.
Signature-free execution audit. On 30 fixed executable test fixtures, inferred interfaces yield accepted chains for 27/30, and 23/30 outputs pass the native comparison. Exact interfaces yield 30/30 accepted chains and 29/30 native passes. Three accepted inferred outputs are not reparsable by CompCert; one further native run needs a Clang adapter. On the 23 inferred outputs that pass natively, CompCert’s interpreter reports 2 expected terminations, 15 internal stuck/undefined-behavior outcomes, 5 unsupported externals, and 1 inline-assembly stop; exact interfaces give the same split. A current zlib replay accepts 10/15 units; a hybrid retaining the five original objects passes 3/3 workloads, but is not a full reconstruction. Appendix A.12 gives the complete audit.
Frozen generalization. The producer, profiles, and budgets were frozen before acquiring Lua 5.4.9 and zlib 1.3.2. All 49 −O0 contexts complete the chain and recompile with CompCert and Clang; original and reconstructed libraries pass 24/24 native executions. Only 7/49 contexts complete under each optimized flag, so we do not count the partial libraries as application successes. Of 288 generated program/flag cells, 267 pass the frontend, 236 complete reconstruction, and 234 produce matching native records. The remaining two reconstructed cells are inconclusive: the reference and all comparison executables time out. No completed comparison produces a mismatch. All 64 bounded programs pass under each of the three flags (192 successful cells).
Output fidelity and type/layout recovery. We compare original and reconstructed functions after the same CompCert frontend elaboration. Across 3,173 accepted contexts and 45,660 matched function instances, reconstructed C contains 4.11 times as many tokens and 16.96 times as many local declarations as the original. Median binding-normalized token distance [52] is 0.846; median normalized pq-gram distance [5] is 0.972 (lower is closer). The output retains label/goto control flow and recovers no structured loops or switches. On a fixed 100-function zlib sample, median raw token distance is 0.845 for DeCompCert and 0.691 for default Ghidra. The paired Ascent experiment (Table 4) uses the same 3,173 inputs and validators. Source types are held out from candidate generation and ranking. Changes use unrounded counts: relative percentages for counts and bytes, and percentage points (pp) for agreement and recall. Definition-sensitive value flow and compatible layout sharing remove 74,901 casts, 81,320 composite definitions, and 10.35% of whole-C bytes. Access-selected physical-field recall rises by 2.41 percentage points, while exact signature-slot agreement falls by 0.16 points. The analysis often replaces generic pointers with validated physical record views that differ from the original nominal types.
| Measurement | Previous | Current | Change |
| Function casts | 1,072,844 | 997,943 | −6.98% |
| Composite definitions | 192,125 | 110,805 | −42.33% |
| Whole-C bytes | 325,611,708 | 291,905,715 | −10.35% |
| Exact signature-slot agreement | 37.46% | 37.29% | −0.16 pp |
| Access-selected physical-field recall | 19.59% | 21.99% | +2.41 pp |
Table 4. Paired type/layout refinement.
Related Work
Verified compilation and translation validation. CompCert proves semantic preservation for an optimizing compiler by assigning operational semantics to its intermediate languages and proving simulations between them [23]. DeCompCert uses this infrastructure, but its theorem does not follow merely by reversing CompCert’s theorem: we prove complementary simulations and compose them with the remaining pass results. Related CompCert extensions establish separate or open-component compilation and mixed C/assembly linking [21, 41, 42]; these techniques are complementary to DeCompCert’s connected reverse-pipeline theorem. Translation validation checks each transformation result instead of the producer [32]. Prior applications include an optimizing compiler [29], CompCert instruction scheduling [48], and LLVM optimization validation in Alive2 [26]. DeCompCert applies the same separation to reverse transformations: OCaml or Ascent proposes a program and a proved Rocq checker certifies each accepted result. Other passes are implemented and proved directly in Rocq, and both forms are composed into one decompiler theorem.
Recompilation-guided recovery. Compile-and-compare techniques use a compiler as feedback for search or evaluation. Evolving Exact Decompilation searches for source programs whose recompilation matches a target [37]. Coda uses recompilation feedback during iterative recovery [17], while LLM4Decompile evaluates reconstructed code by recompilation and re-execution [43]. These systems establish useful syntactic or testing-based checks, but do not provide a composed, machine-checked semantic theorem for the recovered source. DeCompCert uses exact forward replay where the CompCert pass boundary supports it and proves complementary simulations where syntactic round trips are inappropriate, notably across optimized RTL. Uroboros, Ramblr, and Ddisasm instead target reassemblable or relocatable assembly [16, 53, 54]; they preserve a lower-level representation rather than certified decompilation.
Recovery of source abstractions. Decompilers reconstruct expressions, variables, types, and structured control flow erased by compilation. Production systems such as Ghidra and RetDec combine many heuristic analyses to produce usable C-like output [6, 28]. Cifuentes systematized early reverse-compilation analyses [11]; Debin uses learned scores and approximate inference to recover names and types from stripped binaries [18]; TIE recovers source types with constraints [22]; and Retyped extends machine-code type inference with recursive types, polymorphism, and subtyping [31]. TRex instead targets accurate behavior-capturing types rather than an often unrecoverable original nominal type [8], a distinction that also motivates DeCompCert’s physical-layout measurements. Phoenix, DREAM, and SAILR recover structured control flow using structural and compiler-aware methods [7, 38, 56]. Recent hybrid systems use learned semantic proposals together with symbolic reasoning. ReSym fine-tunes separate models for variables and structures, then uses Prolog to aggregate and cross-check their per-function predictions [55]. HyRES combines Datalog-based static analysis, an LLM, and heuristic aggregation to recover structure layouts and semantics from stripped binaries [39]. These systems optimize recovery of source-like names and abstractions; their predictions are not semantic certificates for the emitted program. DeCompCert’s usage of analysis is inspired by these tools, but leverages translation validation to achieve soundness of the result.
Lifting and verified decompilation. BAP and angr lift instructions into analysis representations [9, 40]. Formally checked lifters validate x86-64 instructions or reconstruct sound control-flow overapproximations [12, 49]. TrABin uses proof-producing ARMv8 and Cortex-M0 transpilers to generate HOL4 certificates for lifting into a binary intermediate language [24]. Myreen et al. produce logical functions with machine-code theorems [27], while BIRD proves a register-to-variable pass over a generic Coq representation [14]. FoxDec is the closest effort to sound recovery at the binary boundary: FoxDec 1.0 recovers restricted, recompilable C from x86-64 binaries using verified control-flow recovery and proved symbolic rewrites; its subset requires signatures and headers, excludes indirect branches, and can require intervention during reference recovery [51]. FoxDec 3.0 instead lifts position-independent x86-64 ELF binaries to symbolized, recompilable NASM [50]. It recompiles that assembly, independently lifts both binaries to Ghidra low P-code, and generates Isabelle/HOL [30] certificates establishing isomorphic control-flow graphs and equal corresponding basic-block effects modulo an address transposition. DeCompCert instead consumes textual assembly and reconstructs recompilable C through a sequence of CompCert intermediate languages, composing verified passes and proved validators for untrusted candidate generation into one machine-checked semantic theorem for the complete reconstruction. Its parser, instruction decoder, and interface reconstruction are trusted; the theorem begins with the CompCert Asm program that the frontend constructs. Connecting that boundary to hardware is complementary work: Sail provides authoritative Armv8-A ISA semantics, while Islaris verifies machine code against full-scale ISA semantics [4, 36].
Testing and output fidelity. Recompilable output alone does not establish correctness. Empirical studies find recompilation and semantic failures in C decompilers [25], while D-Helix compares symbolic models of lifted and recompiled programs and reports 4,515 incorrect functions across 93,000 Ghidra and angr outputs [57]. Conventional tools and DeCompCert therefore do not expose directly comparable success measures: producing decompiled text is different from producing a complete reconstruction accepted by a proved validator. DeCompCert uses testing to measure coverage, not to justify correctness. It also separates semantics from resemblance to the unavailable source: names, types, expressions, and structure can be lost [13]. DeCompCert certifies one reconstruction without claiming to recover the original or enumerate every equivalent program.
AI Usage Statement
OpenAI’s Codex was used as an implementation assistant for our certified Rocq development; under our supervision, we used Codex for code development, proof repair suggestions, experiment and artifact automation, consistency checks, and data analysis. The authors wrote the paper manually, but used AI tools for copyediting and critique. The authors take full responsibility for all work.
Data-Availability Statement
An anonymized artifact contains DeCompCert’s source code, mechanized proofs, untrusted reconstruction analyses, experiment outputs, paper tables, and scripts that check the correspondence between them. It provides a pinned container and separate quick and full validation tracks. The quick track checks the reported aggregates, focused inference tests, proof hygiene, and one connected reconstruction; the full track additionally rebuilds and checks the mechanized proof closure. Third-party application sources that cannot be redistributed are identified by version with acquisition and preparation instructions; experiment outputs include hashes where available. Platform-specific native replays are documented separately from portable proof and table checks. We intend to submit this artifact for Artifact Evaluation.
References
Detailed Reconstruction and Proofs
§ 3 and § 4 present the central reconstruction problems and the main correctness argument. This section provides additional technical details on the individual decompilation passes, including their reconstruction process, formal specifications, and soundness guarantees. We also present supporting lemmas and proofs underlying the results presented in the main paper.
Decompiler Passes and Their Soundness Proofs
This section presents the mechanized correctness argument for each semantic reverse pass. The textual assembly parser and instruction decoder belong to the trusted front end; the proofs begin with CompCert’s unexpanded Asm representation. The proof statements quantify over the unexpanded Asm program and do not require its function signatures to have been retained from source compilation. The signature-free front end may therefore propose the typed Asm input without changing any pass theorem. Its inference remains untrusted, and only candidates accepted by the validators receive the composed guarantee.
The proof modules for Asm, Mach, and Linear establish the lower reconstruction results. The RTL-to-CminorSel and CminorSel-to-Cminor reverse-proof modules establish the middle simulations. The C-front-end validator modules check the Cminor, Csharpminor, Clight, and Csyntax boundaries, and DecompPipelineproof composes the accepted programs returned by the driver. The development reuses CompCert’s Asmgen, Stacking, Allocation, Cminorgen, Cshmgen, SimplExpr, and SimplLocals correctness results. Its logical assumption audit includes CompCert’s selected target configuration and external-semantics interfaces, standard extensionality and proof-irrelevance principles used by CompCert, and classical logic used by the reverse proofs. There are no admitted proof obligations or correctness axioms for the candidate generators. Parsing, printing, signature inference, assembling, linking, and native execution remain outside the mechanized theorem.
One computational constant also appears in the audit and should not be mistaken for a generator-correctness assumption. DecompLTL_Validation.decompile_ltl_function is declared as a Rocq Parameter of computational type because the development does not execute the untrusted OCaml generator during proof checking. Extraction replaces this constant with the implementation in DecompLTL. No proposition about the result of that function is assumed: the theorem is conditional only on the verified allocation validator accepting the proposed RTL function. Consequently, an arbitrary or faulty replacement can reduce coverage or fail validation, but cannot establish a false accepted result.
Asm to Mach
The Asm-to-Mach decompiler is implemented in OCaml as a syntax-directed inverse of CompCert’s Asmgen pass. It recognizes the target instruction sequences generated for Mach operations, calls, branches, returns, builtins, and stack-frame operations, and reconstructs the corresponding Mach instructions while preserving labels and control flow. Because some assembly patterns admit several possible reconstructions, the decompiler may generate multiple candidates. Each candidate is checked by rerunning Asmgen, and only a candidate that reproduces the complete supplied unexpanded Asm program is accepted.
The textual-assembly parser and the recovery of symbols and function signatures precede this proved boundary. Signatures can either be retained by CompCert or inferred from assembly and the target ABI. In both cases, the semantic theorem is quantified over the resulting typed Asm program. The validator certifies the Mach reconstruction relative to this typed Asm candidate; fidelity of inferred signatures to external assembly remains a trusted front-end obligation.
The Asm-to-Mach validator reruns CompCert’s Asmgen pass on the reconstructed Mach program. It accepts only if the result is exactly the supplied unexpanded Asm program:
We first define decidable equality for Asm instructions and operands, including registers, addressing modes, labels, builtins, frame operations, and branch targets. We extend this equality to functions and complete programs, then apply Asmgenproof.transf_program_correct. The proof reuses CompCert’s target-specific return-address relation.
Theorem A.1 (Asm-to-Mach semantic preservation). Let be an unexpanded Asm program and an accepted Mach reconstruction. Then
Proof sketch. The validator reruns CompCert’s Asmgen transformation on the reconstructed Mach program and accepts only when . Validator soundness follows by unfolding the executable check and using decidable equality of complete Asm programs. We then apply CompCert’s existing Asmgen correctness theorem, which gives a forward simulation from the semantics of to the semantics of . CompCert’s generic simulation theorem converts this simulation into the behavior-improvement result . Finally, when is safe, behavior improvement cannot replace it with an undefined behavior; therefore .
Corollary A.2 (Preservation of defined Mach behaviors).
Proof sketch. The corollary follows directly from the theorem. Since excludes undefined behavior, implies . Hence the supplied Asm program exhibits the same behavior .
LTL to RTL
CompCert’s register allocation transforms RTL into LTL by replacing pseudo-registers with physical registers and stack slots, introducing moves, spills, and reloads when necessary. Our LTL-to-RTL decompiler reverses this transformation by reconstructing pseudo-registers and eliminating instructions introduced by register allocation. We follow a translation-validation approach: an untrusted OCaml decompiler generates an RTL candidate, whose correctness is checked using CompCert’s register-allocation validator.
Figure 4 illustrates the relationship between RTL and LTL using a simple function, add, which returns the sum of two integers. For simplicity, we illustrate register spilling and reloading using this small example, although register allocation for such a function would typically not require these operations. In the LTL representation, X0 and X1 initially hold the arguments x and y, respectively, while X0 is also used to return the result. In block 3, the value of x is moved to register X19, and the value of y is spilled into an abstract stack slot. In block 2, y is reloaded into register X20, and the addition is performed, storing the result in X0.

Figure 4. Compilation of add to RTL and LTL.
The corresponding RTL representation is simpler. It uses pseudo-registers r1 and r2 for the arguments and r3 for the result, without explicitly managing physical registers or stack slots. Reconstructing RTL from LTL therefore requires identifying and eliminating instructions introduced by register allocation, such as moves, spills, and reloads, while recovering suitable pseudo-registers and instructions. For example, the sequence of instructions in LTL blocks 3 and 2 can be reconstructed as a single RTL addition instruction.
Overview of decompilation. The decompiler maintains an environment , where a location represents a physical register or stack slot, and a register represents a reconstructed RTL pseudo-register. Multiple locations may map to the same pseudo-register because register allocation can move or copy a value between locations. The function signature and target calling convention determine the initial locations of function parameters.
Consider the example in Figure 4. Initially, the environment maps X0 to r1 and X1 to r2. The instruction X19 := X0 updates the environment with . Similarly, spilling X1 into stack[0] adds . When X20 := stack[0] reloads the value, the environment is updated with . The reconstruction algorithm first processes the moves preceding an LTL computation and updates the environment. It then reconstructs the corresponding RTL instruction, introducing a fresh pseudo-register for the computed result. Finally, it processes any trailing moves and identifies the successor node. Thus, by traversing the LTL control-flow graph and tracking how values move between physical locations, the decompiler recovers the pseudo-registers and reconstructs the RTL instructions while eliminating moves introduced by register allocation.
Translation validation. The reconstruction algorithm is implemented in OCaml and is not part of the trusted proof. Each generated RTL candidate is checked against the original LTL program using two existing CompCert components. First, RTLtyping.type function checks that the reconstructed RTL function is well typed. Second, Allocation.check function validates that the LTL function corresponds to a valid register allocation of the reconstructed RTL function. This includes checking the correspondence of operations, register locations, spills, reloads, control-flow edges, calls, and returns. For the example in Figure 4, validation establishes that pseudo-register r1 corresponds to X0 and subsequently X19, while r2 corresponds to X1, stack[0], and X20. It also checks that the LTL addition implements the reconstructed RTL addition and that the result is returned through X0. Candidates that fail either check are rejected. The correctness of LTL-to-RTL decompilation follows the translation-validation approach described in § 3. Successful RTL type checking and register-allocation validation establish CompCert’s allocation specification for the reconstructed RTL program and the supplied LTL program . We therefore reuse CompCert’s existing correctness theorem for validated register allocation, which establishes a forward simulation from to . Consequently, every defined observable behavior of the reconstructed is also a behavior of the supplied .
The central validator lemma is
Its proof unfolds the validator and applies two existing results. CompCert’s RTL type-checking theorem proves the inferred register typing. Its allocation checker soundness theorem converts successful checking into the semantic register-allocation relation.
This function relation is lifted to entire programs. Internal functions satisfy the checked allocation relation; external functions, globals, public symbols, and the main symbol are preserved. The final theorem is obtained by instantiating Allocproof.validated_program_correct.
Theorem A.3 (LTL-to-RTL semantic preservation). Let be an LTL program and let . Then .
Corollary A.4 (Preservation of defined RTL behaviors).
The state relation used by CompCert’s register allocation validator allows an RTL register to hold a value less defined than that of its corresponding LTL location. Consequently, the correctness theorem establishes a forward simulation from the reconstructed RTL program to the original LTL program, ensuring that the reconstruction introduces no new defined observable behaviors. However, this guarantee is directional and does not establish the converse simulation for full behavioral equivalence.
RTL to CminorSel
RTL-to-CminorSel reconstruction is implemented and verified directly in Rocq. The proof is organized at the expression, instruction, function, and program levels. First, a register-environment relation states that every RTL register used by the function has the same value as the corresponding CminorSel local variable. The relation is restricted to the finite set of registers occurring in the function. RTL register maps assign Vundef to uninitialized registers, whereas the CminorSel environment contains only declared parameters and locals. The relation permits corresponding values to be Vundef; it does not assume that every register contains a defined value. We prove the following properties:
a reconstructed register expression evaluates to the corresponding RTL register value;
reconstructed operation operands preserve their order and values;
reconstructed addressing expressions compute the same memory address;
call targets and argument lists denote the same functions and values.
The proof considers each RTL instruction. Assignments preserve the correspondence between registers and local variables, while loads and stores use addressing lemmas to establish the same memory effects. Conditional branches select the same successor. The remaining cases handle calls, tail calls, builtins, jump tables, and returns. The state relation connects an RTL state at program counter with a CminorSel state executing goto pc. Label lookup identifies the corresponding reconstructed statement. The relation also connects RTL call stacks with CminorSel continuations and ensures that their register and local environments agree. The state relation also includes an RTL value-analysis invariant that justifies simplifying reconstructed expressions and conditions. We prove that this invariant holds initially and is preserved by every RTL step, without requiring all registers to contain defined values. Initial states are related through preservation of global symbols, and related final states return the same integer value.
The step theorem shows that each RTL transition is matched by one or more CminorSel transitions with the same observable trace. Multiple target steps are needed because one RTL instruction can reconstruct to a sequence of CminorSel assignments, statements, labels, and gotos. The complete simulation is therefore proved using CompCert’s forward_simulation_plus construction.
Theorem A.5 (RTL-to-CminorSel semantic preservation). Let be an RTL program and let . Then .
Proof sketch. Successful reconstruction establishes correspondence between the global environments, functions, RTL nodes, and reconstructed CminorSel statements. The expression lemmas show that corresponding operands, operations, addresses, conditions, and call arguments evaluate to the same values. Using these lemmas, the instruction proof shows that every RTL transition is reproduced by one or more CminorSel transitions with the same trace, memory effects, and updated environment. Initial-state and final-state correspondence are combined with this step result using forward_simulation_plus. CompCert’s generic behavior theorem then produces a CminorSel behavior satisfying .
Corollary A.6 (Preservation of defined RTL behaviors).
Proof sketch. For the corollary, Safe() excludes undefined RTL behavior. Therefore implies , and the reconstructed CminorSel program exhibits the same behavior .
Complementary simulation for composition. The preceding simulation follows an RTL execution through the reconstructed CminorSel program. To obtain a continuous semantic path from reconstructed C to the supplied assembly, we also prove the complementary simulation from the reconstructed CminorSel program to the supplied RTL program. The main difficulty is that one RTL node is reconstructed as a CminorSel statement containing assignments, sequences, labels, blocks, and gotos. Some CminorSel transitions therefore perform only administrative work and have no corresponding RTL transition. The complementary proof uses a phase-indexed state relation. A related state contains a CminorSel state, its corresponding RTL state, and a natural-number index representing the remaining administrative phases. A CminorSel transition that performs the action reconstructed from an RTL instruction is matched by that RTL instruction with the same observable trace. A transition that only traverses a sequence, label, block, or goto may leave the RTL state unchanged, but it must strictly decrease the phase index. Because the index is a natural number, these silent transitions cannot continue indefinitely.
Inverse-evaluation lemmas show that evaluating a reconstructed CminorSel expression recovers the corresponding RTL register values, operation operands, memory addresses, conditions, call targets, and jump-table destinations. Successful reconstruction also supplies the required correspondence between entry nodes, successor nodes, symbols, functions, and calling conventions. As in the preceding direction, the relation includes the proved RTL value-analysis invariant needed to justify reconstructed normalizations.
Theorem A.7 (Complementary CminorSel-to-RTL simulation). Let be an RTL program and let . Then .
Consequently, .
Proof sketch. The proof relates each CminorSel execution phase to the RTL instruction from which it was reconstructed. For every CminorSel transition, the RTL program either executes the corresponding instruction with the same trace or remains unchanged while the phase index strictly decreases. Initial states are related using preservation of memory, symbols, the main function, and its signature; related final states return the same integer value. We use the well-founded order on natural numbers and determinacy of CminorSel semantics to assemble these results with CompCert’s forward_simulation_determ construction.
This theorem requires no additional semantic assumption. Together with the RTL-to-CminorSel theorem above, it establishes both simulation directions for every successfully reconstructed pair at this boundary.
CminorSel to Cminor
CminorSel expressions can contain target-specific operations and value-level selections that are absent from Cminor. Reconstruction may therefore produce a sequence of setup statements followed by a simpler Cminor expression.
The expression proof is organized around a relation , where computes any required temporary values and denotes the final result. The central expression lemma shows that evaluating in a CminorSel environment is reproduced by executing and then evaluating in the resulting Cminor environment. Supporting lemmas cover constants, variables, operations, addressing modes, loads, conditions, argument lists, and call targets. Freshness lemmas ensure that setup statements modify only newly introduced temporaries.
The proof then proceeds by induction over CminorSel statements. Sequencing is handled by composing the corresponding Cminor executions. Conditions and selections use the expression theorem before entering the reconstructed branch. Loops, blocks, and exits preserve their continuation structure. Further cases cover calls, tail calls, builtins, switches, labels, gotos, and returns.
Three side conditions are required by the current proof:
every reached unsigned-long comparison produces a defined Boolean result;
every reached selection has a defined condition; and
every reached function contains unique labels.
The first two conditions account for a semantic difference: CminorSel may propagate Vundef through a value-level operation, while reconstructed Cminor control flow can become stuck when asked to branch on an undefined condition. The third condition is used because expanding a nested selection can duplicate a labeled branch; uniqueness ensures that a reconstructed goto still has an unambiguous corresponding target.
The state relation combines expression-environment agreement with corresponding call stacks, functions, statements, and memories. A strengthened invariant carries label uniqueness across execution. Every CminorSel step is matched by one or more Cminor steps, after which the resulting states again satisfy the invariant.
Theorem A.8 (CminorSel-to-Cminor semantic preservation). Let be a CminorSel program and let . If reached unsigned-long comparisons and selections are defined and reached functions have unique labels, then .
Corollary A.9 (Preservation of defined CminorSel behaviors). Under the same side conditions, .
These three conditions belong to the original pass-local simulation from CminorSel to Cminor. They are not premises of the complete decompiler theorem, which uses the complementary simulation below at this boundary.
Complementary simulation for composition. For end-to-end composition we also require a simulation from the reconstructed Cminor program to its CminorSel input. This direction is proved for the CminorSel programs generated by the preceding RTL-to-CminorSel pass. This restriction is significant: arbitrary CminorSel permits effectful operations inside expressions, whereas RTL-generated CminorSel uses an effect-free expression subset whose effects occur at statement boundaries. The successful RTL reconstruction provides a provenance witness showing the exact RTL instruction and execution phase represented by every reached CminorSel state.
Reconstruction of one CminorSel expression can introduce several silent Cminor assignments before its observable action and additional silent bookkeeping afterward. The state relation therefore has three phases: before, while setup precedes the matching action; after, while only trailing administration remains; and stuck, for a finite silent suffix whose reconstructed computation is undefined. Each phase carries a natural-number rank. At exact instruction boundaries the relation combines the ordinary CminorSel-to-Cminor match relation with generated-syntax and RTL provenance invariants. Constructor-specific lemmas cover operations, loads, stores, calls, builtins, conditions, jump tables, gotos, and returns.
The syntax-specific step proof is first established for safe Cminor states, where progress permits inverse evaluation of every generated setup expression. This local use of safety does not become a theorem premise. If a related Cminor state is unsafe, negating CompCert’s definition of safety exposes a finite silent path to a non-final state with no transition; the stuck phase simulates that path by stuttering with a decreasing rank. Observable external and builtin transitions are replayed in CminorSel with the same trace, using receptiveness where the external result is chosen by the environment. Recursive progress lemmas handle structured builtin arguments. For an unsigned-long comparison or value-level selection, the successful Cminor transition being simulated supplies the defined Boolean result needed by the corresponding CminorSel operation. If the condition is undefined, Cminor has no transition, so there is no source step to match. Setup statements generated from RTL operands contain only variable reads and are covered by separate total lemmas. Consequently, these partial operations require no global definedness hypothesis in the complementary direction.
Theorem A.10 (Complementary Cminor-to-CminorSel simulation). Let , , and be RTL, CminorSel, and Cminor programs such that
Then . Consequently,
Proof sketch. Successful RTL-to-CminorSel and CminorSel-to-Cminor reconstruction establishes the generated-syntax, label-uniqueness, register-environment, and RTL provenance invariants at each instruction boundary. The proof relates Cminor and CminorSel states using the before, after, and stuck phases, ordered by a well-founded natural-number rank.
For a safe Cminor state, inversion of the Cminor transition and the constructor-specific evaluation lemmas identify the corresponding CminorSel action. Silent setup and cleanup steps are handled by decreasing the phase rank, while observable calls and builtins are replayed with the same trace. For an unsafe Cminor state, CompCert’s definition of safety yields a finite silent execution to a non-final state with no successor. The stuck phase represents this execution while decreasing the rank. Initial states are related using preservation of global environments and function entry, and related final states return the same value. These results are combined with the well-founded phase order to construct the forward simulation. Because safe and unsafe states are both handled inside the proof, the final theorem requires no global safety or definedness assumption.
Cminor to Csharpminor
The Cminor-to-Csharpminor generator represents each nonempty stack frame as one addressable object and reconstructs interior byte displacements from its base. Let require every function in to contain at most one addressable object and require the size of that object to be nonnegative. Let denote the normalization that folds constant Cminor stack-address displacements. Validator soundness establishes
The comparison includes complete Cminor programs: function bodies, external declarations, global variables, public symbols, their order, and the program entry point. The frame-shape check is required even when the unnormalized programs match. Without it, a candidate could divide one Cminor stack block into several Csharpminor objects. Cminorgen could assign those objects contiguous offsets and reproduce the same Cminor syntax, although the reconstructed program would have different object boundaries and could interpret interior accesses differently. In the normalized case, CminorStackAddr provides a simulation from to and a simulation from back to . Composing these simulations with Cminorgenproof.transl_program_correct gives the same semantic guarantee as exact round-trip validation.
Theorem A.11 (Cminor-to-Csharpminor semantic preservation). Let be a Cminor program and an accepted Csharpminor reconstruction. Then
Proof sketch. Unfolding the validator yields the frame-shape property, a generated Cminor program , and either exact equality or normalized equality . In the exact case, CompCert’s Cminorgen correctness theorem directly gives a forward simulation from to . In the normalized case, we first apply Cminorgen correctness to obtain a simulation from to . We then compose it with the proved simulation from to . Normalized equality identifies this program with , and the reverse normalization theorem supplies the final simulation from to . CompCert’s generic behavior theorem therefore produces a Cminor behavior satisfying .
Corollary A.12 (Preservation of defined Csharpminor behaviors).
Safe() excludes undefined Csharpminor behavior. Therefore implies , and the supplied Cminor program has the same behavior .
Csharpminor to Clight
The OCaml extractor records direct type facts from function signatures, operations, memory accesses, calls, builtins, and assignments. Ascent then propagates these facts across copy-related variables. The central relations are
, , , .
Copy edges generate symmetric same-type edges; their transitive closure then propagates inferred types:
For example, in t = x; result = Odivu(t,y), unsigned division suggests unsigned-integer types for t, y, and result; the copy relation assigns the same candidate type to x. The analysis retains conflicting type candidates as alternatives.
Addressable variables retain their size in bytes but not their element type. A 40-byte object accessed with 32-bit loads can therefore be proposed as int buffer[10]. When the access patterns do not suggest an element type, the decompiler proposes a byte array. Scaled address such as &buffer + index × 4 can become buffer[index] when the inferred element size is four bytes. The scale must be removed during reconstruction because Clight reintroduces it when compiling the array access.
Csharpminor conditionals are already structured, while combinations of Sblock, Sloop, and numbered Sexit encode loops, break, and continue. The generator recognizes these forms blocked switch structures, but interprets a numbered exit as a structured statement only when the surrounding nesting justifies it. Control flow that does not match these patterns remains explicit. These facts guide candidate generation but are not trusted by the correctness proof. An incorrect type, layout, or structure inference may cause rejection, but it cannot establish the theorem for an incorrect candidate.
Let denote the supplied Csharpminor program and let denote its reconstructed Clight program. The validator first checks that every variadic prototype in contains exactly the fixed parameter prefix recorded by its calling convention. It then recompiles using CompCert’s Cshmgen pass and compares the complete generated Csharpminor program with and a finite set of permitted normalizations of .
We write for this set. It contains itself and the programs obtained by composing the following proved transformations: discarded-result cleanup, guarded narrow-result restoration, canonical-result restoration, narrow-assignment restoration, and parameter-entry restoration. More precisely, let , , , , and denote these transformations, respectively. Then
Validator soundness establishes
The equality comparison covers complete Csharpminor programs, including all function bodies, global definitions, public symbols, and the program entry point. The validator therefore cannot accept a candidate merely because an individual reconstructed function or expression happens to match.
Theorem A.13 (Csharpminor-to-Clight semantic preservation). Let be a Csharpminor program and an accepted Clight reconstruction. Then
Proof sketch. Validator soundness produces a Csharpminor program such that Cshmgen translates to and . CompCert’s Cshmgenproof.transl_program_correct gives a forward simulation from the semantics of to the semantics of . If , this simulation directly establishes the result. Otherwise, is one of the permitted normalized programs. Each cleanup and restoration transformation has a proved reverse simulation relating its output to its input. We compose the simulations required by the applicable normalization case to obtain a simulation from to . Finally, composition with the Cshmgen simulation yields a simulation from the accepted Clight reconstruction to the supplied Csharpminor program . CompCert’s generic behavior-preservation theorem then gives the stated behavior-improvement result.
Corollary A.14 (Preservation of defined Clight behaviors).
The batched discarded-result cleanup has its own semantic-correctness proof, avoiding repeated whole-program cleanup passes. Consequently, neither Ascent nor the OCaml candidate generator belongs to the trusted base; an incorrect type, layout, or declaration inference can make validation fail, but every candidate accepted by the validator satisfies the theorem above.
Clight to Csyntax/Readable C
The final reconstruction recovers a Csyntax program that can be printed as recompilable C. It reconstructs source-level expression grouping, loop initializers, short-circuit expressions, comma expressions, and structured conditionals. The supplied input is the second Clight form in CompCert’s pipeline: SimplExpr lowers C expressions to Clight, after which SimplLocals converts eligible local variables to temporaries.
The generator is untrusted. The validator runs these two verified passes on the candidate and compares the complete generated Clight program with . Exact equality is too restrictive because the forward passes can introduce administrative skip prefixes and temporary result copies. Let remove only the proved skip and guarded-assignment patterns, and let fold only proved call/builtin result-copy patterns into direct result assignments. The validator uses the following bounded family:
The repeated forms are needed because one cleanup can expose an administrative pattern recognized by the other. The search remains finite, and every application of or has its own proved Clight simulation.
Writing for the validator, soundness establishes
The equality compares complete Clight programs, including function bodies, global definitions, public symbols, the main identifier, and composite-type definitions.
Theorem A.15 (Clight-to-Csyntax semantic preservation). Let be a Clight program and an accepted Csyntax reconstruction. Then
Proof sketch. Validator soundness produces , , and . CompCert’s correctness theorem for SimplExpr gives a simulation from to , and the theorem for SimplLocals gives a simulation from to . If , checked equality identifies with . Otherwise, we compose the simulation from with the cleanup simulations in . The checked equality then identifies the result with the supplied Clight program. Composition therefore gives a simulation from the accepted Csyntax program to . CompCert’s generic behavior theorem produces a Clight behavior satisfying .
Corollary A.16 (Preservation of defined C behaviors).
Safe excludes undefined behavior of the reconstructed C program. Therefore implies , and the supplied Clight program has the same behavior .
This theorem closes the source boundary when the preceding Csharpminor-to-Clight validator supplies the same . The complete pipeline also has a verified replay path for candidates rejected by this local comparison: it runs SimplExpr and SimplLocals, applies the same finite cleanup family, and validates the resulting Clight program directly against the reconstructed Csharpminor input. The subsequent pretty-printer serializes the accepted Csyntax program and is outside the semantic transformation.
Composing these pass-local results with the complementary middle-level simulations yields the whole-decompiler theorem stated in § 4.
Discharging the C-Safety Assumption
For a closed checksum recovered without manual cleanup, Rocq checks an untrusted finite execution graph containing 97 states and 130 edges. The check covers progress, memory operations, and every C expression-evaluation order, proving that all executions terminate with an empty trace and result 222. The composed theorem transfers this result to the supplied Asm. This example shows that the final C-safety premise can be proved, but does not claim safety for all reconstructed applications. The artifact records the full search protocols, certificate, assumption audit, and machine-readable results.
Accepted-Chain Signature Fidelity
Validator acceptance establishes consistency with the inferred typed Asm; it does not establish recovery of CompCert’s held-out interface. We therefore compare the complete accepted assignment with the held-out assignment after validation. On the frozen 15-context zlib campaign, 104/152 (68.4%) internal-function signatures and 373/449 (83.1%) call-site signatures match exactly; only 3/15 contexts have a fully exact signature set.
We also audit every cumulative-portfolio acceptance for which both the archived receipt and held-out assignment remain available: 1,198/2,606 contexts. In this receipt-backed subset, 6,809/13,373 (50.9%) internal-function signatures and 44,074/64,802 (68.0%) call-site signatures match exactly, and 112/1,198 (9.3%) contexts are exact throughout. The other 1,408 acceptances lack comparable archived receipts; we neither classify them nor extrapolate from the non-random subset.
Uniform Cost Ablation
We replay libuv with one producer, candidate bound, and timeout. Assembly-only inference accepts 26/37 contexts after 1,878 candidates in 673.468 seconds (median 7.193, p95 71.327). Adding checked platform, Ghidra, and IDA proposals accepts 31/37 after 1,365 candidates in 590.192 seconds (median 5.218, p95 90.966). The accepted units contain 258/706 versus 430/706 functions; these are functions contained in accepted translation units, not independently certified functions.
Signature-Free Execution Audit
On 30 fixed executable fixtures, inferred interfaces yield 27/30 accepted chains and 23/30 native passes. Exact interfaces yield 30/30 and 29/30. Of the four accepted inferred outputs not run natively, three printed C files are not reparsable by CompCert and one reaches a documented Clang adapter limitation; the latter also accounts for the exact-interface native failure.
CompCert’s interpreter reports 2 expected terminations, 15 external stuck/undefined-behavior outcomes, 5 unsupported external calls, and 1 inline-assembly stop on the 23 inferred outputs that pass natively. Exact interfaces give the same aggregate split, implicating reconstructed body and layout safety rather than signature inference alone. In a separate current zlib replay, inference accepts 10/15 translation units. Replacing those ten objects while retaining five originals passes 3/3 workloads; this hybrid is not a full signature-free application reconstruction.
Native Clang Profile
The CompCert-compatible Clang profile for recovered C contains four flags:
-ffreestanding-ffp-contract=off-fwrapv-fno-strict-aliasing
The first permits the recovered entry prototype, the second prevents contraction absent from the CompCert run, and the last two align signed-overflow and aliasing assumptions with CompCert C. Ordinary original/native caller code uses -ffp-contract=off; the receipts preserve the complete command lines and any fixture-specific adapter.
References
- [1]Apple Inc. n.d. Writing ARM64 Code for Apple Platforms. https://developer.apple.com/documentation/xcode/writing-arm64-code-for-apple-platforms Accessed November 12, 2026.
- [2]Arm Limited. 2024. Arm A-profile A64 Instruction Set Architecture. https://support.arm.com/documentation/ddi0602/2024-12 DDI0602, version 2024-12. Base instruction descriptions.
- [3]Arm Limited. 2026. Procedure Call Standard for the Arm 64-bit Architecture (AArch64). https://github.com/ARM-software/abi-aa/blob/2025Q4/aapcs64/aapcs64.rst Release 2025Q4, January 23, 2026.
- [4]Alasdair Armstrong, Thomas Bauereiss, Brian Campbell, Alastair Reid, Kathryn E. Gray, Robert M. Norton, Prashanth Mundkur, Mark Wassell, Jon French, Christopher Pulte, Shaked Flur, Ian Stark, Neel Krishnaswami, and Peter Sewell. 2019. ISA Semantics for ARMv8-A, RISC-V, and CHERI-MIPS. Proceedings of the ACM on Programming Languages 3, POPL, Article 71 (2019), 31 pages. doi:10.1145/3290384DOI
- [5]Nikolaus Augsten, Michael H. Böhlen, and Johann Gamper. 2010. The pq-Gram Distance between Ordered Labeled Trees. ACM Transactions on Database Systems 35, 1, Article 4 (2010), 36 pages. doi:10.1145/1670243.1670247
- [6]Avast Software. 2017. RetDec: A Retargetable Machine-Code Decompiler. https://retdec.com/.
- [7]Zion Leonahane Basque, Ati Priya Bajaj, Wil Gibbs, Jude O’Kain, Derron Miao, Tiffany Bao, Adam Doupé, Yan Shoshitaishvili, and Rouyu Wang. 2024. Ahoy SAIL! There Is No Need to DREAM of C: A Compiler-Aware Structuring Algorithm for Binary Decompilation. In 33rd USENIX Security Symposium. USENIX Association, Philadelphia, PA, USA, 361–378. https://www.usenix.org/conference/usenixsecurity24/presentation/basque
- [8]Jay Bosamiya, Maverick Woo, and Bryan Parno. 2025. TRex: Practical Type Reconstruction for Binary Code. In 34th USENIX Security Symposium. USENIX Association, Seattle, WA, USA, 6897–6915. https://www.usenix.org/conference/usenixsecurity25/presentation/bosamiyaDOI
- [9]David Brumley, Ivan Jager, Thanassis Avgerinos, and Edward J. Schwartz. 2011. BAP: A Binary Analysis Platform. In Computer Aided Verification (Lecture Notes in Computer Science, Vol. 6806). Springer, Berlin, Heidelberg, 463–469. doi:10.1007/978-3-642-22110-1_37DOI
- [10]Stefano Ceri, Georg Gottlob, and Letizia Tanca. 1989. What You Always Wanted to Know About Datalog (And Never Dared to Ask). IEEE Transactions on Knowledge and Data Engineering 1, 1 (March 1989), 146–166. https://www2.cs.sfu.ca/CourseCentral/721/jim/DatalogPaper.pdfDOI
- [11]Cristina Cifuentes. 1994. Reverse Compilation Techniques. Ph. D. Dissertation. Queensland University of Technology. https://www.phatcode.net/res/228/files/decompilation_thesis.pdf
- [12]Sandeep Dasgupta, Sushant Dinesh, Deepan Venkatesh, Vikram S. Adve, and Christopher W. Fletcher. 2020. Scalable Validation of Binary Lifters. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York, NY, USA, 655–671. doi:10.1145/3385412.3385964DOI
- [13]Luke Dramko, Jeremy Lacomis, Edward J. Schwartz, Bogdan Vasilescu, and Claire Le Goues. 2024. A Taxonomy of C Decompiler Fidelity Issues. In 33rd USENIX Security Symposium. USENIX Association, Philadelphia, PA, USA, 379–396. https://www.usenix.org/conference/usenixsecurity24/presentation/dramkoDOI
- [14]Daniel Engel, Freek Verbeek, and Binoy Ravindran. 2023. BIRD: A Binary Intermediate Representation for Formally Verified Decompilation of x86-64 Binaries. In Tests and Proofs (Lecture Notes in Computer Science, Vol. 14066). Springer, Cham, Switzerland, 3–20. doi:10.1007/978-3-031-38828-6_1
- [15]Daniel Engel, Freek Verbeek, and Binoy Ravindran. 2024. On the Decidability of Disassembling Binaries. In Theoretical Aspects of Software Engineering (Lecture Notes in Computer Science, Vol. 14777), Wei-Ngan Chin and Zhiwu Xu (Eds.). Springer, Cham, Switzerland, 127–145. doi:10.1007/978-3-031-64626-8_3
- [16]Antonio Flores-Montoya and Eric Schulte. 2020. Datalog Disassembly. In 29th USENIX Security Symposium (USENIX Security 20). USENIX Association, 1075–1092. https://www.usenix.org/conference/usenixsecurity20/presentation/flores-montoyaarxiv.org/abs/1906.03969
- [17]Cheng Fu, Huili Chen, Haolan Liu, Xinyun Chen, Yuandong Tian, Farinaz Koushanfar, and Jishen Zhao. 2019. Coda: An End-to-End Neural Program Decompiler. In Advances in Neural Information Processing Systems, Vol. 32. Curran Associates, Inc. https://proceedings.neurips.cc/paper/2019/hash/093b60fd0557804c8ba0cbf1453da22f-Abstract.html
- [18]Jingxuan He, Pesho Ivanov, Petar Tsankov, Veselin Raychev, and Martin Vechev. 2018. Debin: Predicting Debug Information in Stripped Binaries. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. ACM, New York, NY, USA, 14 pages. doi:10.1145/3243734.3243866DOI
- [19]Hex-Rays SA. 2026. IDA Pro. https://hex-rays.com/ida-pro.
- [20]ISO/IEC JTC 1/SC 22/WG 14. 2011. Programming Languages—C. Technical Report N1570. ISO/IEC. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf Committee draft, April 12, 2011. Section 6.5.5, paragraph 5.
- [21]Jérémie Koenig and Zhong Shao. 2021. CompCertO: Compiling Certified Open C Components. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. ACM, New York, NY, USA, 1095–1109. doi:10.1145/3453483.3454097DOI
- [22]JongHyup Lee, Thanassis Avgerinos, and David Brumley. 2011. TIE: Principled Reverse Engineering of Types in Binary Programs. In Proceedings of the Network and Distributed System Security Symposium. The Internet Society, Reston, VA, USA, 18 pages. https://www.ndss-symposium.org/ndss2011/tie-principled-reverse-engineering-of-types-in-binary-programs/
- [23]Xavier Leroy. 2009. Formal verification of a realistic compiler. Commun. ACM 52, 7 (July 2009), 107–115. doi:10.1145/1538788.1538814DOI
- [24]Andreas Lindner, Roberto Guanciale, and Roberto Metere. 2019. TrABin: Trustworthy Analyses of Binaries. Science of Computer Programming 174 (2019), 72–89. doi:10.1016/j.scico.2019.01.001DOI
- [25]Zhibo Liu and Shuai Wang. 2020. How Far We Have Come: Testing Decompilation Correctness of C Decompilers. In Proceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis. ACM, New York, NY, USA, 475–487. doi:10.1145/3395363.3397370DOI
- [26]Nuno P. Lopes, Juneyoung Lee, Chung-Kil Hur, Zhengyang Liu, and John Regehr. 2021. Alive2: Bounded Translation Validation for LLVM. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. ACM, New York, NY, USA, 65–79. doi:10.1145/3453483.3454030DOI
- [27]Magnus O. Myreen, Michael J. C. Gordon, and Konrad Slind. 2012. Decompilation into Logic—Improved. In 2012 Formal Methods in Computer-Aided Design. IEEE, Piscataway, NJ, USA, 78–81. https://www.cl.cam.ac.uk/~mom22/decompilation/fmcad12.pdf
- [28]National Security Agency. 2019. Ghidra. https://github.com/NationalSecurityAgency/ghidra.
- [29]George C. Necula. 2000. Translation Validation for an Optimizing Compiler. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation. ACM, New York, NY, USA, 83–94. doi:10.1145/349299.349314DOI
- [30]Tobias Nipkow, Lawrence C. Paulson, and Markus Wenzel. 2002. Isabelle/HOL: A Proof Assistant for Higher-Order Logic. Lecture Notes in Computer Science, Vol. 2283. Springer, Berlin, Heidelberg. doi:10.1007/3-540-45949-9DOI
- [31]Matthew Noonan, Alexey Loginov, and David R. Kofl. 2016. Polymorphic Type Inference for Machine Code. In Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York, NY, USA, 27–41. doi:10.1145/2908080.2908119DOI
- [32]Amir Pnueli, Michael Siegel, and Eli Singerman. 1998. Translation Validation. In Tools and Algorithms for the Construction and Analysis of Systems (Lecture Notes in Computer Science, Vol. 1384), Bernhard Steffen (Ed.). Springer, Berlin, Heidelberg, 151–166. doi:10.1007/BFb0054170
- [33]Silvain Rideau and Xavier Leroy. 2010. Validating Register Allocation and Spilling. In Compiler Construction (Lecture Notes in Computer Science, Vol. 6011), Rajiv Gupta (Ed.). Springer, Berlin, Heidelberg, 224–243. doi:10.1007/978-3-642-11970-5_13DOI
- [34]Arash Sahebolamri, Langston Barrett, Scott Moore, and Kristopher Micinski. 2023. Bring Your Own Data Structures to Datalog. Proc. ACM Program. Lang. 7, OOPSLA2, Article 264 (Oct. 2023), 26 pages. doi:10.1145/3622840DOI
- [35]Arash Sahebolamri, Thomas Gilray, and Kristopher Micinski. 2022. Seamless Deductive Inference via Macros. In Proceedings of the 31st ACM SIGPLAN International Conference on Compiler Construction. ACM, New York, NY, USA, 12 pages. doi:10.1145/3497776.3517779DOI
- [36]Michael Sammler, Angus Hammond, Rodolphe Lepigre, Brian Campbell, Jean Pichon-Pharabod, Derek Dreyer, Deepak Garg, and Peter Sewell. 2022. Islaris: Verification of Machine Code Against Authoritative ISA Semantics. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation. ACM, New York, NY, USA, 825–840. doi:10.1145/3519939.3523434DOI
- [37]Eric Schulte, Jason Rouchi, Matt Noonan, and David Ciarletta, and Alexey Loginov. 2018. Evolving Exact Decompilation. In Proceedings of the 2018 Workshop on Binary Analysis Research. Internet Society, San Diego, CA, USA. doi:10.14722/bar.2018.23008DOI
- [38]Edward J. Schwartz, JongHyup Lee, Maverick Woo, and David Brumley. 2013. Native x86 Decompilation Using Semantics-Preserving Structural Analysis and Iterative Control-Flow Structuring. In 22nd USENIX Security Symposium. USENIX Association, Berkeley, CA, USA, 353–368. https://www.usenix.org/conference/usenixsecurity13/technical-sessions/presentation/schwartz
- [39]Zihan Sha, Hui Shu, Hao Wang, Zeyu Gao, Yang Lan, and Chao Zhang. 2026. HyRES: Recovering Data Structures in Binaries via Semantic Enhanced Hybrid Reasoning. ACM Transactions on Software Engineering and Methodology 35, 3, Article 69 (2026), 28 pages. doi:10.1145/3736719DOI
- [40]Yan Shoshitaishvili, Ruoyu Wang, Christopher Salls, Nick Stephens, Mario Polino, Andrew Dutcher, John Grosen, Siji Feng, Christine Hauser, Christopher Kruegel, and Giovanni Vigna. 2016. SoK: (State of) The Art of War: Offensive Techniques in Binary Analysis. In 2016 IEEE Symposium on Security and Privacy (SP). IEEE, IEEE, Los Alamitos, CA, USA, 138–157. doi:10.1109/SP.2016.17DOI
- [41]Youngju Song, Minki Cho, Dongjoo Kim, Yonghyun Kim, Jeehoon Kang, and Chung-Kil Hur. 2020. CompCertM: CompCert with C-Assembly Linking and Lightweight Modular Verification. Proceedings of the ACM on Programming Languages 4, POPL, Article 23 (2020), 31 pages. doi:10.1145/3371091DOI
- [42]Gordon Stewart, Lennart Zannier, Santiago Cuellar, and Andrew W. Appel. 2015. Compositional CompCert. In Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM, New York, NY, USA, 275–287. doi:10.1145/2676726.2676985DOI
- [43]Hanzhuo Tan, Qi Luo, Jing Li, and Yuqun Zhang. 2024. LLM4Decompile: Decompiling Binary Code with Large Language Models. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, Miami, Florida, USA, 3473–3487. doi:10.18653/v1/2024.emnlp-main.203DOI
- [44]The CompCert Project. n.d.. CompCert: Module Behaviors. https://compcert.org/doc/html/compcert.common.Behaviors.html Behavior improvement and preservation of safe behaviors. Accessed November 12, 2026.
- [45]The CompCert Project. n.d.. CompCert: Module Smallstep. https://compcert.org/doc/html/compcert.common.Smallstep.html Generic simulations and the forward-to-backward simulation theorem. Accessed November 12, 2026.
- [46]The LLVM Project. n.d.. Clang: A C Language Family Frontend for LLVM. https://clang.llvm.org/ Accessed November 12, 2026.
- [47]The Rocq Development Team. n.d.. The Rocq Prover Reference Manual. https://rocq-prover.org/doc/master/refman/index.html Accessed November 12, 2026.
- [48]Jean-Baptiste Tristan and Xavier Leroy. 2008. Formal Verification of Translation Validators: A Case Study on Instruction Scheduling Optimizations. In Proceedings of the 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM, New York, NY, USA, 17–27. doi:10.1145/1328438.1328444DOI
- [49]Freek Verbeek, Joshua A. Boekenek, Zhouli Fu, and Binoy Ravindran. 2022. Formally Verified Lifting of C-Compiled x86-64 Binaries. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation. ACM, New York, NY, USA, 934–949. doi:10.1145/3519939.3523702DOI
- [50]Freek Verbeek, Nico Naus, and Binoy Ravindran. 2024. Verifiably Correct Lifting of Position-Independent x86-64 Binaries to Symbolized Assembly. In Proceedings of the 2024 ACM SIGSAC Conference on Computer and Communications Security. ACM, New York, NY, USA, 2786–2798. doi:10.1145/3658644.3690244DOI
- [51]Freek Verbeek, Pierre Olivier, and Binoy Ravindran. 2020. Sound C Code Decompilation for a Subset of x86-64 Binaries. In Software Engineering and Formal Methods (Lecture Notes in Computer Science, Vol. 12310), Frank de Boer and Antonio Cerone (Eds.). Springer International Publishing, Cham, 247–264. doi:10.1007/978-3-030-58768-0_14DOI
- [52]Robert A. Wagner and Michael J. Fischer. 1974. The String-to-String Correction Problem. J. ACM 21, 1 (Jan. 1974), 168–173. doi:10.1145/321796.321811DOI
- [53]Ruoyu Wang, Yan Shoshitaishvili, Antonio Bianchi, Aravind Machiry, John Grosen, Paul Grosen, Christopher Kruegel, and Giovanni Vigna. 2017. Ramblr: Making Reassembly Great Again. In 24th Annual Network and Distributed System Security Symposium. Internet Society, San Diego, CA, USA. doi:10.14722/ndss.2017.23225DOI
- [54]Shuai Wang, Pei Wang, and Dinghao Wu. 2015. Reassembly Without Symbols. In 24th USENIX Security Symposium (USENIX Security 15). USENIX Association, Washington, D.C., 627–642. https://www.usenix.org/conference/usenixsecurity15/technical-sessions/presentation/wang-shuai
- [55]Danning Xie, Zhuo Zhang, Nan Jiang, Xianghe Xu, Lin Tan, and Xiangyu Zhang. 2024. ReSym: Harnessing LLMs to Recover Variable and Data Structure Symbols from Stripped Binaries. In Proceedings of the 2024 ACM SIGSAC Conference on Computer and Communications Security. ACM, New York, NY, USA, 4554–4568. doi:10.1145/3658644.3670340DOI
- [56]Khaled Yakdan, Sebastian Eschweiler, Elmar Gerhards-Padilla, and Matthew Smith. 2015. NoMore Gadgets: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantics-Preserving Transformations. In Proceedings of the Network and Distributed System Security Symposium. The Internet Society, Reston, VA, USA, 15 pages. doi:10.14722/ndss.2015.23185
- [57]Muqi Zou, Arslan Khan, Ruoyu Wu, Han Gao, Antonio Bianchi, and Dave (Jing) Tian. 2024. D-Helix: A Generic Decompiler Testing Framework Using Symbolic Differentiation. In 33rd USENIX Security Symposium (USENIX Security 24). USENIX Association, Philadelphia, PA, 397–414. https://www.usenix.org/conference/usenixsecurity24/presentation/zou