betaFeedback

WorksComputer Science

C-to-Rust Translation Validation at the LLVM IR Level via AI-Assisted Refinement Proof

Abstract

Migrating C codebases to Rust is a promising approach to securing legacy software, but existing translators do not guarantee that a translated Rust program preserves the behavior of the C program. Neither rule-based nor large language model (LLM)-based translators have been formally verified, and existing approaches to checking translation correctness are limited to testing and bounded checks, which cannot reason about all possible executions. In this work, we present R2C2, which validates C-to-Rust translation by proving in Rocq that the Rust program refines the C program, i.e., every behavior on the Rust side is also a behavior on the C side. Since no formal semantics defines the behaviors of C and Rust programs in the same terms, we prove refinement between the two programs compiled to the LLVM intermediate representation (LLVM IR). In addition, to resolve the discrepancies between the data representations of C and Rust, we introduce a common abstraction that relates two corresponding representations through an abstract value, and specify the behavior of each library function over abstract values. We construct the refinement proof as a chain of refinement relations, where only one relation is program-specific and proved at validation time, while the others are proved for all programs in advance. Proof construction is automated by AI agents, and since Rocq checks the proofs, the agents need not be trusted. We evaluate R2C2 on LLM translations of 519 C programs drawn from a benchmark suite used in prior work on C-to-Rust translation validation. R2C2 proves the translations of 486 programs correct without bounding their executions and discovers three incorrect translations, providing valid counterexamples that existing translation validation tools cannot find. We also conduct a case study on a small real-world image compression library and demonstrate how R2C2 can handle file operations.

Introduction

Migrating C codebases to memory-safe Rust is a promising approach to securing legacy C software. C often suffers from memory bugs because it lacks language-level protections, whereas Rust provides memory safety guarantees at compile time [24]. As a result, C-to-Rust translation has emerged as an active research area with a variety of approaches, ranging from rule-based translators [7, 9, 10, 12, 16, 17, 18, 19, 20, 22, 28, 50, 60] to large language model (LLM)-based methods [1, 6, 21, 44, 52, 53, 57, 61, 62].

Unfortunately, existing translators do not guarantee the correctness of the translation, i.e., that a translated Rust program preserves the behavior of the C program. In theory, the correctness of rule-based translators could be proved, but no existing translators have been formally verified. LLM-based translators do not rely on algorithmic procedures that can be formally verified.

When translators are not verified in advance, an alternative approach to ensuring correctness is translation validation [41], which instead verifies each individual translation. While most prior studies adopt only testing, RustAssure [1] conducts symbolic testing to expand the covered input space, and VERT [53] leverages bounded model checking [8, 49] to compare behavior up to a fixed unrolling bound and recursion depth. These approaches can discover incorrect translations but cannot reason about all possible executions, leaving a significant gap in ensuring correctness.

To guarantee the correctness of translation for every possible execution, a line of research on translation validation has proposed techniques to generate refinement proofs, typically for compiler optimizations [2, 39, 41]. A translated program, the target, refines its source if every behavior of the target is also a behavior of the source. To close the gap in ensuring the correctness of C-to-Rust translation, adopting the approach of proving refinement is a promising direction.

Authors’ Contact Information: Eunsu Kim, KAIST, Daejeon, Republic of Korea, [email protected]; Sukyoung Ryu, KAIST, Daejeon, Republic of Korea, [email protected]; Jaemin Hong, UNIST, Ulsan, Republic of Korea, [email protected].

In this work, we present an approach to C-to-Rust translation validation based on foundational refinement proofs. Specifically, we tackle two challenges: (1) defining refinement, as no formal semantics defines the behaviors of C and Rust programs in the same terms; (2) proving refinement, as C and Rust represent the same data differently, and the proof must relate the two representations.

Challenge #1. A foundational refinement proof requires formal semantics that define the behaviors of the source and target programs. Refinement is an inclusion between the sets of behaviors, which is well-defined only if both formal semantics define program behaviors in the same terms, such as traces of the same kind of events. However, existing formal semantics for C [34, 38] and Rust [13, 24, 32] do not define behaviors in the same terms. The formal semantics for C and Rust were developed independently and differ in how they model values, operations, and memory.

We address this challenge by validating the translation at the LLVM intermediate representation (LLVM IR) level. LLVM IR is an intermediate language used by compilers for many programming languages, including C and Rust. Its formal semantics has been developed to verify compiler optimizations through refinement [36, 58]. We compile the source C program and its Rust translation into LLVM IR and prove that the compiled Rust program refines the compiled C program.

Challenge #2. C and Rust often represent the same data differently, which makes refinement proofs challenging. For example, a variable-length array (VLA) in C is translated into a Vec in Rust, which is a struct containing a pointer to a heap-allocated array; they differ in memory layout and supported operations. These differences remain even after compilation to LLVM IR, where a C VLA is represented as a pointer to its first element and a Rust Vec is represented as a struct.

Therefore, a refinement proof should establish a relation between data in two different representations. Following the usual simulation approach, a proof starts the two programs with related input states, follows their executions, and compares their output states, where each step involves re-establishing the relation between the data. This is challenging, as the data is typically modified through library functions, whose calling conventions and internal logic differ between C and Rust.

We address this challenge by introducing a common abstraction for each pair of C and Rust representations that frequently correspond in translation, relating two representations of the same data. A common abstraction specifies the type of an abstract value shared by the two representations. For example, a C VLA and a Rust Vec have a common abstraction: a list.

We formalize the concept of a common abstraction by defining a predicate over ghost resources [25, 26] that expresses how a value is laid out in memory in each representation, so that a proof can reason about memory updates at the level of abstract values. With a common abstraction, simulation starts with the same abstract value in two representations and, at the end, compares the outputs as abstract values. We also describe the behavior of each library function with a specification over abstract values, reducing the effort required to re-establish the relation after each library call.

AI-assisted proof automation. Existing translation validation techniques [2, 39, 41] construct refinement proofs using deterministic procedures, often by exploiting known structural correspondences or transformation patterns in their domains. However, our translation validation also targets translations produced by LLM-based translators, which may restructure the code in arbitrary ways to produce idiomatic Rust code. For this reason, we instead leverage AI agents to automate proof construction, taking advantage of recent advances in AI’s ability to generate formal proofs [37, 54]. Since a proof assistant checks the generated proofs, the agents need not be trusted.

For efficient proof generation, we construct a refinement proof as a chain of multiple refinement relations, where only one relation is program-specific while the others are common to all translations. The common parts are proved in advance, and only the program-specific part is proved by an agent at validation time through simulation. Furthermore, we provide simulation rules that capture common reasoning patterns required in proofs.

Implementation and evaluation. We implement our approach as a tool named R2C2 based on the Rocq proof assistant. Our semantics of LLVM IR is a variant of Vellvm [58], a formal semantics of LLVM IR mechanized in Rocq. The refinement relations and theorems for proving them are taken from CRIS [29], a Rocq framework for refinement proofs. On top of these, we build our program models, common abstractions, and specifications of library functions.

We evaluate R2C2 on LLM translations of the 519 C programs in the benchmark suite of VERT [53]. R2C2 proves the translations of 486 programs correct without bounding their executions, and discovers three incorrect translations, providing valid counterexamples that neither VERT nor RustAssure finds. It validates a translation in 23.3 minutes at a cost of $2.91 on average using gpt-6.1-sol, and more capable LLMs prove complex programs faster at a higher cost. We also conduct a case study on QOI [5], a small real-world image compression library, demonstrating how R2C2 handles complex features such as file operations.

Contributions. To summarize, the contributions of this paper are as follows:

  • We formulate C-to-Rust translation validation as a refinement proof between the compiled programs at the LLVM IR level (§ 3).

  • We introduce common abstractions to relate different data representations of C and Rust through abstract values and specify the behavior of library functions over those values (§ 4).

  • We construct a refinement proof as a chain of refinement relations and show how the program-specific part can be proved by simulation (§ 5).

  • We implement the proposed approach in Rocq on top of Vellvm and CRIS, automating the construction of refinement proofs with AI agents (§ 6).

  • We evaluate R2C2 on 519 C programs, proving 486 translations correct and finding three incorrect translations, and also conduct a case study on an image compression library (§ 7).

Background

This section introduces LLVM IR and its semantics (§ 2.1) and explains how CRIS defines refinement (§ 2.2). This and subsequent sections use has_duplicate in Figure 1 as a running example, so we first explain the example here. The top left shows a C function that takes a pointer a to an integer array of length n, copies the data from a to a VLA s, sorts s, and checks for a duplicate within a loop. Note that lib.h provides void sort(int *first, int *last), which sorts the elements from first to last. The top right shows its Rust translation, which takes a slice a, represented as a fat pointer accompanied by its length, copies the data from a to a Vec s, sorts s, and checks for a duplicate using methods provided by Rust iterators.

C and Rust implementations of has_duplicate with their generated LLVM IR

Figure 1. A C function has_duplicate (left) and its Rust translation (right), each above the LLVM IR that Clang or rustc generates from it at O1. We omit attributes, flags, alignment, and metadata, and rename registers.

LLVM IR

LLVM IR is a typed language in static single assignment (SSA) form, used by Clang and rustc. Each SSA register, whose name starts with %, is assigned exactly once. A program consists of functions and global variables, whose names start with @. The body of a function consists of basic blocks, each of which is a sequence of instructions ending with a terminator.

Figure 1 shows LLVM IR programs compiled from has_duplicate: the bottom left is compiled from C, and the bottom right is compiled from Rust. Both the C VLA s and the Rust Vec s become stack memory allocated by alloca: for the VLA, an array is allocated and pointed to by %vla; for the Vec, a struct that later holds a pointer to a heap buffer is allocated and pointed to by %s. During compilation, library function calls are handled in three ways: (1) compiled to an LLVM intrinsic call, e.g., memcpy becomes @llvm.memcpy; (2) compiled to an external function call, e.g., sort and to_vec; or (3) inlined, e.g., windows and any are inlined, so the basic blocks form a loop.

LLVM IR has two mechanisms for introducing undefined behavior (UB) [33]: some operations, such as division by zero, immediately cause UB; others, such as overflow of an addition marked as non-wrapping, defer UB by returning a special value, namely poison, which propagates through most operations and causes actual UB only when its concrete value is required, e.g., in a branch condition. Another special value for deferred UB is undef, which represents nondeterminism. The LLVM community is working to remove undef from LLVM IR entirely [35], so our semantics only includes poison and excludes undef; since current compilers may still produce IR with undef, we eliminate undef from compiled IR [6].

The denotational semantics of LLVM IR is defined using interaction trees (ITrees) [51], which represent computations that interact with their environment through events. ITrees can express executions of any length, including nonterminating ones, because they are coinductively defined:

itree⁡ E R≜∣ Ret⁡ (r:R)∣ Tau⁡ (T:itree⁡ E R)∣ Vis⁡ {X} (ev:E X) (k:X→itree⁡ E R)\begin{aligned} \operatorname{itree}\ E\ R \triangleq{}& \mid\ \operatorname{Ret}\ (r:R)\\ &\mid\ \operatorname{Tau}\ (T:\operatorname{itree}\ E\ R)\\ &\mid\ \operatorname{Vis}\ \{X\}\ (ev:E\ X)\ (k:X\to\operatorname{itree}\ E\ R) \end{aligned}
x←T1; T2≜bind⁡ T1 (λx. T2)x\leftarrow T_1;\ T_2 \triangleq\operatorname{bind}\ T_1\ (\lambda x.\ T_2)

// run T1T_1: itree, then T2T_2: itree with xx = return of T1T_1

trigger⁡ ev≜Vis⁡ ev (λx.Ret⁡ x)\operatorname{trigger}\ ev \triangleq\operatorname{Vis}\ ev\ (\lambda x.\operatorname{Ret}\ x)

// trigger the event evev and return the response

An ITree either returns a value (Ret), takes a silent step (Tau), or triggers an event and continues with the response (Vis). For events, we follow the definition in CRIS:

E::= Call⁡(f,v)∣IO⁡(f,v)∣Choose⁡ X∣UB⁡∣NB⁡∣Take⁡ X∣Assume⁡ Q∣Guarantee⁡ Q// imaginary operations\begin{aligned} E \mathrel{::=}&\ \operatorname{Call}(f,v)\mid\operatorname{IO}(f,v)\mid\operatorname{Choose}\ X\mid\operatorname{UB}\mid\operatorname{NB}\\ &\mid\operatorname{Take}\ X\mid\operatorname{Assume}\ Q\mid\operatorname{Guarantee}\ Q\quad//\ \text{imaginary operations} \end{aligned}

An event is either a function call (Call), an interaction with the environment (IO) with a name ff and an argument vv, a nondeterministic choice (Choose), UB (UB), no behavior (NB), or an imaginary operation of CRIS (Take, Assume, or Guarantee, where QQ is an assertion on ghost resources). Imaginary operations are not used in the LLVM IR semantics but are used in our specifications of library functions (§ 5.1).

Our semantics, given in detail in §A, is a variant of Vellvm [58], with two changes: it uses CRIS’s events, and it passes memory directly instead of modeling memory operations as events. The denotation of an instruction ii, ⟦i⟧(ρ,m):itree⁡ E (Val⁡×Mem⁡)\llbracket i\rrbracket(\rho,m):\operatorname{itree}\ E\ (\operatorname{Val}\times\operatorname{Mem}), takes a local environment ρ\rho, which maps registers to values, and a memory mm, which is a collection of allocated blocks of bytes, and returns an ITree that produces a value and a new memory. Similarly, ⟦e⟧(ρ,m):itree⁡ E Val⁡\llbracket e\rrbracket(\rho,m):\operatorname{itree}\ E\ \operatorname{Val} evaluates an expression ee to a value, and ⟦es⟧\llbracket es\rrbracket evaluates a list eses of expressions from left to right. For example, the semantics of load and call instructions is as follows:

⟦load⁡(τ,e)⟧(ρ,m)=p←⟦e⟧(ρ,m); match⁡ load⁡(τ,p,m) with⁡ Success⁡ v⇒Ret⁡(v,m)∣Failure⁡⇒trigger⁡ UB⁡\llbracket\operatorname{load}(\tau,e)\rrbracket(\rho,m)=p\leftarrow\llbracket e\rrbracket(\rho,m);\ \operatorname{match}\ \operatorname{load}(\tau,p,m)\ \operatorname{with}\ \operatorname{Success}\ v\Rightarrow\operatorname{Ret}(v,m)\mid\operatorname{Failure}\Rightarrow\operatorname{trigger}\ \operatorname{UB}
⟦call⁡(τ,e,es)⟧(ρ,m)=args⁡←⟦es⟧(ρ,m); p←⟦e⟧(ρ,m); if⁡ p=poison⁡ then⁡trigger⁡ UB⁡ else⁡trigger⁡ Call⁡(fn(p),(τ,args⁡,m))\llbracket\operatorname{call}(\tau,e,es)\rrbracket(\rho,m)=\operatorname{args}\leftarrow\llbracket es\rrbracket(\rho,m);\ p\leftarrow\llbracket e\rrbracket(\rho,m);\ \operatorname{if}\ p=\operatorname{poison}\ \operatorname{then}\operatorname{trigger}\ \operatorname{UB}\ \operatorname{else}\operatorname{trigger}\ \operatorname{Call}(f_n(p),(\tau,\operatorname{args},m))

load⁡(τ,e)\operatorname{load}(\tau,e) evaluates an expression ee to obtain a pointer and reads a value of type τ\tau from the pointed-to memory location using a pure function load⁡\operatorname{load}, shown in blue, which does not trigger any events. load⁡\operatorname{load} returns Success vv with the read value vv, or Failure for an invalid access, on which the denotation triggers UB. call⁡(τ,e,es)\operatorname{call}(\tau,e,es) evaluates eses and ee to obtain arguments and a function pointer, and triggers a Call event (or UB if the pointer is poison), passing the function pointer, the arguments, and the current memory, and receiving the result of type τ\tau and the new memory. The denotation of an LLVM IR function FF, ⟦F⟧(args⁡,m):itree⁡ E (Val⁡×Mem⁡)\llbracket F\rrbracket(\operatorname{args},m):\operatorname{itree}\ E\ (\operatorname{Val}\times\operatorname{Mem}), takes the arguments and the initial memory and returns an ITree that produces the return value and the final memory. It executes the basic blocks starting from the entry block.

Refinement in CRIS

In CRIS, a module is a mapping from function names to function bodies, where a function body takes a Rocq value and returns an ITree producing a Rocq value: Mod⁡≜FName⁡→(Any⁡→itree⁡ E Any⁡)\operatorname{Mod}\triangleq\operatorname{FName}\to(\operatorname{Any}\to\operatorname{itree}\ E\ \operatorname{Any}).

A Call event to a function within the same module is handled by the function’s body, while calling a function not in the module causes UB. To call a function in another module, modules M1M_1 and M2M_2 can be linked to form a module M1⋆M2M_1\star M_2, which contains functions from both modules: M1⋆M2=M1∪M2M_1\star M_2=M_1\cup M_2.

A program is a module that designates one of its functions that does not use its input as the entry. The denotation of a program MM is ⟦M⟧:itree⁡ E′ Any⁡\llbracket M\rrbracket:\operatorname{itree}\ E'\ \operatorname{Any}, obtained from the ITree returned by the entry function by replacing every Call event with the body of the callee, where E′E' consists of events other than Call.

Figure 2 defines the behavior of a program MM as a set of traces, Beh⁡(⟦M⟧)\operatorname{Beh}(\llbracket M\rrbracket). A trace records the IO interactions of an execution (Interact), each with its name ff, argument aa, and response rr, and ends with Done vv, where vv is the value returned by the entry function. Beh⁡(T)\operatorname{Beh}(T) collects the traces of a tree TT by cases: a returned value vv gives a trace Done vv, a silent step Tau is skipped, IO gives traces for all responses, Choose gives traces for all choices, UB gives every trace, and NB gives none. For the imaginary operations, Take gives the traces common to all choices, and Assume QQ and Guarantee QQ continue if QQ holds and otherwise behave as UB and NB, respectively. A program MM refines M′M', written M⊑behM′M \sqsubseteq_{\mathrm{beh}} M', if every trace of ⟦M⟧\llbracket M\rrbracket is a trace of ⟦M′⟧\llbracket M'\rrbracket.1

Definitions of trace, behavior, and refinement

Figure 2. Definitions of trace, behavior, and refinement.

Defining Translation Correctness as Refinement

In this section, we define the correctness of C-to-Rust translation as refinement in CRIS at the LLVM IR level. We represent a C program and its translated Rust program as CRIS programs and define translation correctness as refinement between these two CRIS programs. We restrict our scope to programs with a single public function; in general, when a program has multiple public functions, translation validation could be performed for each pair of corresponding public functions. We first construct a CRIS function from an LLVM IR function (§ 3.1), then build a CRIS program from the CRIS function by linking it with library modules (§ 3.2), and finally define correctness as refinement between CRIS programs (§ 3.3).

Constructing CRIS Functions

We construct a CRIS function, a driver, for each LLVM IR function. When building a CRIS program later, each driver serves as the entry of the program. The goal of drivers is to resolve the discrepancies between C and Rust, enabling refinement proofs. Refinement is defined as a subset relation between trace sets, and traces carry values. Therefore, input and output values should be represented identically for both LLVM IR functions compiled from C and Rust. Drivers achieve this goal by taking abstract values as input, converting the input to the representation of each language, running the LLVM IR function with the correct representation, and converting the results back to abstract values. For an LLVM IR function FXF_X from each language X∈{C,Rust}X \in\{\mathrm{C}, \mathrm{Rust}\}, its driver driver⁡(FX)\operatorname{driver}(F_X) is as follows:

driver⁡(FX)≜λ .v←trigger⁡ IO⁡("input",());if ¬valid_input⁡FX(v) then Ret Noneelse (p,m)←register⁡FX(v,m0);(r,m′)←[FX](r,m);o←observe⁡(r); o′←observe⁡(read⁡FX(p,m′));Ret⁡(Some⁡(o,o′))\begin{aligned} \operatorname{driver}(F_X) &\triangleq\lambda\ _.\\ v &\leftarrow\operatorname{trigger}\ \operatorname{IO}(\text{"input"}, ());\\ &\text{if }\neg\operatorname{valid\_input}_{F_X}(v)\text{ then Ret None}\\ &\text{else }(p,m)\leftarrow\operatorname{register}_{F_X}(v,m_0);\\ &(r,m')\leftarrow[F_X](r,m);\\ &o\leftarrow\operatorname{observe}(r); \ o'\leftarrow\operatorname{observe}(\operatorname{read}_{F_X}(p,m'));\\ &\operatorname{Ret}(\operatorname{Some}(o,o')) \end{aligned}
valid_input⁡FX:list⁡ Any⁡→Prop⁡register⁡FX:list⁡ Any⁡×Mem⁡→list⁡ Obj⁡×Mem⁡args⁡FX:list⁡ Any⁡→list⁡ Obj⁡→list⁡ Val⁡read⁡FX:list⁡ Obj⁡×Mem⁡→list⁡ Any⁡observe⁡:A→itree⁡ E A\begin{aligned} \operatorname{valid\_input}_{F_X}&:\operatorname{list}\ \operatorname{Any}\to\operatorname{Prop}\\ \operatorname{register}_{F_X}&:\operatorname{list}\ \operatorname{Any}\times\operatorname{Mem}\to\operatorname{list}\ \operatorname{Obj}\times\operatorname{Mem}\\ \operatorname{args}_{F_X}&:\operatorname{list}\ \operatorname{Any}\to\operatorname{list}\ \operatorname{Obj}\to\operatorname{list}\ \operatorname{Val}\\ \operatorname{read}_{F_X}&:\operatorname{list}\ \operatorname{Obj}\times\operatorname{Mem}\to\operatorname{list}\ \operatorname{Any}\\ \operatorname{observe}&:A\to\operatorname{itree}\ E\ A \end{aligned}

As the driver is the entry of a CRIS program, it does not use its argument (line 1) and instead receives the input vv by triggering an IO event (line 2). By taking the input through an event, the driver records it in the trace. The input is a list of abstract values, whose types are determined by the common abstractions of the arguments of the C and Rust functions. For example, the drivers for has_duplicate take a single abstract value, a list of 32-bit signed integers.

Then, the driver determines whether vv is an intended input to the function FF using valid_inputF_F; if not, it immediately returns None (line 3). We allow the user to specify the intended input space (§ 6). For has_duplicate, it checks whether the length of the list is within the size bound of the architecture.

If the input is valid, the driver converts the input to the appropriate representation for the language (line 4) and runs the LLVM IR function using its denotation ⟦FX⟧\llbracket F_X \rrbracket (line 5): registerF,X_{F,X} allocates vv in the initial memory m0m_0 using the representation of language XX, returning a list of objects, each of which is an LLVM IR value or a tuple of such values, that hold information about the registered input, and the updated memory mm; argsF,X_{F,X} constructs the arguments required by the LLVM IR function. For has_duplicate, the list is allocated as an array, and pp contains the pointer to the array and its length; the arguments are these two values, passed as parameters %a and %n for C and as %a.0 and %a.1 for Rust.

After the call, the driver collects the output (line 6). It takes the return value rr of the function and, to also capture observable memory effects, reads the data referred to by the pointer arguments as abstract values using readF,X_{F,X}. For has_duplicate, it returns the list represented by the array pointed to by pp.

The driver observes each output value to properly handle poison: when an LLVM IR function compiled from C produces poison, a function compiled from Rust should be considered to refine it regardless of the value it produces. For this purpose, we introduce value refinement: vv refines v′v', written v⊑v′v \sqsubseteq v', if v=v′v = v', or if v′v' is poison and vv has the same type; aggregate values, including abstract values such as lists, are compared element-wise. observe(v)(v) provides any non-poison value that refines vv:

observe⁡(v)≜trigger⁡ Choose⁡ {x∣x⊑v∧x≠poison⁡}\operatorname{observe}(v) \triangleq\operatorname{trigger}\ \operatorname{Choose}\ \{x \mid x \sqsubseteq v \land x \ne\operatorname{poison}\}

The driver finishes by returning the observed values, recording the output in a trace (line 7).

Building CRIS Programs

To build a CRIS program, we need library modules that model the behavior of library functions, as the translated program may call library functions. We introduce three modules: libLLVMlib_{LLVM}, libClib_C, and Wfun(libRust)W_{\mathrm{fun}}(lib_{Rust}), which consist of CRIS functions that express the behavior of LLVM intrinsics, C library functions, and Rust library functions, respectively. For example, sort in libClib_C takes two pointers along with the current memory and returns an ITree that produces the new memory in which the array between the two pointers is sorted. Note that Wfun(libRust)W_{\mathrm{fun}}(lib_{Rust}) is a wrapper module generated by CRIS from the underlying module libRustlib_{Rust} by inserting pre- and postconditions into ITrees, as explained further in § 5.1. Currently, these modules only include functions used by the benchmark suite in § 7, but we can model more functions to support additional programs.

With these library modules, we build a CRIS program from a driver. We first introduce a main module main(FX)main(F_X) that consists only of the driver function driver(FX)driver(F_X). We then link the main module with the necessary library modules—libLLVMlib_{LLVM} and the library module for the relevant language LL—to obtain a CRIS program whose entry is the driver in the main module:

program(FX,L)≜main(FX)⋆L⋆libLLVMprogram(F_X,L) \triangleq main(F_X) \star L \star lib_{LLVM}

The programs from C and Rust are program(FC,libC)program(F_C,lib_C) and program(FRust,Wfun(libRust))program(F_{Rust},W_{\mathrm{fun}}(lib_{Rust})), respectively.

Translation Correctness

We define the correctness of translation as follows:

Definition 1 (Translation Correctness). FRustF_{Rust} is a correct translation of FCF_C if

program(FRust,Wfun(libRust))⊨behprogram(FC,libC).program(F_{Rust},W_{\mathrm{fun}}(lib_{Rust})) \models_{\mathrm{beh}} program(F_C,lib_C).

Our validation aims to prove this refinement, implying that the translation is correct with respect to our library modules, and thus relies on the assumptions that these models faithfully represent the actual libraries. We formally express these assumptions using the notion of contextual refinement: a module MM contextually refines a module M′M', written M⊑ctxM′M \sqsubseteq_{\mathrm{ctx}} M', if replacing M′M' with MM in any program adds no behavior [45]:

M⊑ctxM′≜∀C. M⋆C⊑behM′⋆C(1)M \sqsubseteq_{\mathrm{ctx}} M' \triangleq\forall C.\ M \star C \sqsubseteq_{\mathrm{beh}} M' \star C \tag*{(1)}

Let libLLVM,stdlib_{LLVM,std}, libC,stdlib_{C,std}, and libRust,stdlib_{Rust,std} be conceptual standard library modules that precisely describe all possible behaviors of the respective libraries. We assume the following:

libLLVM⊑ctxlibLLVM,stdlibLLVM,std⊑ctxlibLLVMlibC⊑ctxlibC,stdlibRust,std⊑ctxWfun(libRust)lib_{LLVM} \sqsubseteq_{\mathrm{ctx}} lib_{LLVM,std} \qquad lib_{LLVM,std} \sqsubseteq_{\mathrm{ctx}} lib_{LLVM} \qquad lib_C \sqsubseteq_{\mathrm{ctx}} lib_{C,std} \qquad lib_{Rust,std} \sqsubseteq_{\mathrm{ctx}} W_{\mathrm{fun}}(lib_{Rust})

Under these assumptions, Definition 1 implies correctness with respect to the actual libraries:

main(FRust)⋆libRust,std⋆libLLVM,stdmain(F_{Rust}) \star lib_{Rust,std} \star lib_{LLVM,std}
⊑beh main(FRust)⋆Wfun(libRust)⋆libLLVM=program(FRust,Wfun(libRust))\sqsubseteq_{\mathrm{beh}}\ main(F_{Rust}) \star W_{\mathrm{fun}}(lib_{Rust}) \star lib_{LLVM} = program(F_{Rust}, W_{\mathrm{fun}}(lib_{Rust}))
⊑beh main(FC)⋆libC⋆libLLVM=program(FC,libC)\sqsubseteq_{\mathrm{beh}}\ main(F_C) \star lib_C \star lib_{LLVM} = program(F_C, lib_C)
⊑beh main(FC)⋆libC,std⋆libLLVM,std\sqsubseteq_{\mathrm{beh}}\ main(F_C) \star lib_{C,std} \star lib_{LLVM,std}

Furthermore, while our validation is performed at the LLVM IR level, the refinement extends to the binary and source levels if we assume that the compilers are correct. If an LLVM compiler is correct, a compiled binary refines its source LLVM IR; if a C compiler is correct, the compiled LLVM IR refines its C source. With such compilers, the binary compiled from the translated Rust code refines the C source:

Binary from Rust⊑behLLVM IR from Rust⊑behLLVM IR from C⊑behC source\text{Binary from Rust} \sqsubseteq_{\mathrm{beh}} \text{LLVM IR from Rust} \sqsubseteq_{\mathrm{beh}} \text{LLVM IR from C} \sqsubseteq_{\mathrm{beh}} \text{C source}

However, validation at the LLVM IR level is incomplete: even when the translated Rust code refines the C source, the LLVM IR from Rust may not refine the LLVM IR from C, as the LLVM IR does not necessarily preserve all possible behaviors of the source. For example, a compiler may turn UB in the C source into defined behavior in the LLVM IR, which is legitimate since the LLVM IR only needs to refine the source. We discuss cases where validation fails for this reason in § 7.3.

Reasoning with Common Abstractions

We now introduce common abstractions, which we use to reason about different representations of the same abstract value in C and Rust in refinement proofs. Proving refinement requires establishing a simulation between the two programs, and we represent common abstractions with ghost resources [25, 26] that relate the memories of the two programs. During simulation, resources expressing a common abstraction are obtained when the input is allocated, and they are maintained throughout execution, even across library function calls, until the results are read back. We introduce representation predicates, which describe an abstract value in a specific representation (§ 4.1), and common abstractions, which connect representation predicates of C and Rust (§ 4.2), and provide specifications of library functions in terms of common abstractions (§ 4.3).

Representation Predicates

We reason about memory using ghost resources, which do not affect execution, with ownership of cells as the most basic resource. We write p↦qup \mapsto_q u for the ownership of the cells at pp that hold an LLVM IR value uu, with right qq; the full right q=1q = 1 allows writing, and a smaller right allows only reading. The separating conjunction [40] P∗QP * Q holds when the resources can be split into two disjoint parts, one satisfying PP and the other satisfying QQ.

To describe the actual memory, we also introduce a memory authority Auth⁡(m)\operatorname{Auth}(m), which tracks the entire memory mm. Every ownership resource must agree with it: Auth⁡(m)∗p↦qu\operatorname{Auth}(m) * p \mapsto_q u ensures that pp points to live cells in mm that hold uu. When the memory changes, Auth⁡(m)\operatorname{Auth}(m) is updated to reflect the new memory. The C and Rust programs run on separate memories, each with its own authority.

Since C and Rust may lay out the same abstract value differently, we describe each layout with a representation predicate defined using ownership resources. A representation predicate own⁡qa◃R▹v\operatorname{own}_q a \triangleleft R \mathbin{\triangleright} v is a resource stating that an LLVM IR value aa represents an abstract value vv in a representation RR, with right qq; aa can be a tuple of values, such as a pointer and a length. We define the predicate for each abstract value and each representation. For example, in has_duplicate, a list stored in the local variable ss has two different representations, Array in C and Vec in Rust, whose predicates are defined as follows:

own⁡q(p,n)◃(Array⁡ τ)▹vs≜⌈n=∣vs∣⌉∗∗0≤i<n(p+i⋅∣τ∣↦qvs[i])\operatorname{own}_q(p,n) \triangleleft(\operatorname{Array}\ \tau) \mathbin{\triangleright} vs \triangleq\lceil n = |vs| \rceil* \mathop{*}_{0 \le i < n}(p+i\cdot|\tau| \mapsto_q vs[i])
own⁡qh◃(Vec⁡ τ)▹vs≜∃c d. h↦q(c,d,∣vs∣)∗own⁡q(d,∣vs∣)◃(Array⁡ τ)▹vs\operatorname{own}_q h \triangleleft(\operatorname{Vec}\ \tau) \mathbin{\triangleright} vs \triangleq\exists c\,d.\ h \mapsto_q(c,d,|vs|) * \operatorname{own}_q(d,|vs|) \triangleleft(\operatorname{Array}\ \tau) \mathbin{\triangleright} vs

For Array, ⌈n=∣vs∣⌉\lceil n = |vs| \rceil states the pure fact that nn equals the length of the list, and the ii-th element is stored at offset i⋅∣τ∣i \cdot|\tau| from pp, where ∣τ∣|\tau| is the size of the element type τ\tau. For Vec, the header struct hh holds the capacity $c, the address dd of the buffer, and the length ∣vs∣|vs|, and own⁡q(d,∣vs∣)◃(Array⁡ τ) vs\operatorname{own}_{q}(d, |vs|) \triangleleft(\operatorname{Array}\ \tau)\ vs states that the first ∣vs∣|vs| cells of the buffer hold vsvs. Thus, a list vsvs in has_duplicate is described by own⁡1(%vla,%n)◃(Array⁡ i32) vs\operatorname{own}_{1}(\%vla, \%n) \triangleleft(\operatorname{Array}\ \mathrm{i32})\ vs in C and by own⁡1 %s◃(Vec⁡ i32) vs\operatorname{own}_{1}\ \%s \triangleleft(\operatorname{Vec}\ \mathrm{i32})\ vs in Rust.

Common Abstractions

When a C object and a Rust object represent the same abstract value up to refinement, we say that they have a common abstraction. For example, a C VLA and a Rust Vec, described by Array and Vec, have the common abstraction List when they represent the same list. Table 1 enumerates the common abstractions we support. We identified them from the benchmark suite in § 7, and this list can be extended to support more abstractions.

Common abstraction (abstract value)C representationRust representation
List (list of elements)T* with a length, T[n], VLA&[T], &mut [T], [T; n], Vec<T>
String (list of ASCII bytes)NUL-terminated char*&str, Vec<char>
Struct (record of fields)struct (non-recursive)struct (non-recursive)
Table (list of lists)two-dimensional VLAVec<Vec<T>>
File (file state)FILE*File

Table 1. Supported common abstractions.

A representation pair, or a pair for short, is a resource stating that a C object and a Rust object have a common abstraction. A pair pair⁡q(ac,Rc∣ar,Rr)(vc)\operatorname{pair}_{q}(a_{c}, R_{c}\mid a_{r}, R_{r})(v_{c}) states that the C object aca_{c} represents vcv_{c} in representation RcR_{c}, and the Rust object ara_{r} represents vrv_{r} that refines vcv_{c} in representation RrR_{r}:

pair⁡q(ac,Rc∣ar,Rr)(vc)≔∃vr. own⁡q ac◃Rc vc∗own⁡q ar◃Rr vr∗⌈vr⊑vc⌉\operatorname{pair}_{q}(a_{c}, R_{c}\mid a_{r}, R_{r})(v_{c}) \coloneqq\exists v_{r}.\ \operatorname{own}_{q}\ a_{c} \triangleleft R_{c}\ v_{c} * \operatorname{own}_{q}\ a_{r} \triangleleft R_{r}\ v_{r} * \lceil v_{r} \sqsubseteq v_{c}\rceil

During simulation, a representation pair is typically obtained when the input is allocated. For a function FF whose input is a single abstract value (we write a singleton list [x][x] as xx), its drivers driver⁡(FC)\operatorname{driver}(F_{C}) and driver⁡(FRust)\operatorname{driver}(F_{\mathrm{Rust}}) register the same input in their respective memories using register⁡F,X\operatorname{register}_{F,X}, and we reason about how registration updates the memories at the level of abstract values using a representation pair with the following lemma:

Lemma 2 (Registration). For every abstract value vv of a common abstraction and memories mcm_{c} and mrm_{r}, if register⁡F,C(v,mc)=(ac,mc′)\operatorname{register}_{F,C}(v,m_{c}) = (a_{c},m'_{c}) and register⁡F,Rust(v,mr)=(ar,mr′)\operatorname{register}_{F,\mathrm{Rust}}(v,m_{r}) = (a_{r},m'_{r}), then

Auth⁡(mc)∗Auth⁡(mr)⇒Auth⁡(mc′)∗Auth⁡(mr′)∗pair⁡1(ac,Rc∣ar,Rr)(v)\operatorname{Auth}(m_{c}) * \operatorname{Auth}(m_{r}) \Rightarrow\operatorname{Auth}(m'_{c}) * \operatorname{Auth}(m'_{r}) * \operatorname{pair}_{1}(a_{c}, R_{c}\mid a_{r}, R_{r})(v)

where register⁡F,C\operatorname{register}_{F,C} allocates vv in representation RcR_{c}, and register⁡F,Rust\operatorname{register}_{F,\mathrm{Rust}} allocates vv in representation RrR_{r}. Here, P⇒QP \Rightarrow Q means that PP can be updated to QQ by changing only ghost resources.

For example, in has_duplicate, the input list vsvs is allocated as an array in both the C and Rust drivers, and the registration lemma provides pair⁡1((%a,%n),Array⁡ i32∣(%a.0,%a.1),Array⁡ i32)(vs)\operatorname{pair}_{1}((\%a,\%n), \operatorname{Array}\ \mathrm{i32}\mid(\%a.0,\%a.1), \operatorname{Array}\ \mathrm{i32})(vs).

If the obtained representation pair is maintained until this point, we can reason about the final memories and conclude that the value read by the Rust driver using read⁡F,X\operatorname{read}_{F,X} refines that read by the C driver:

Lemma 3 (Read). For every abstract value vv of a common abstraction and memories mcm_{c} and mrm_{r},

Auth⁡(mc)∗Auth⁡(mr)∗pair⁡q(ac,Rc∣ar,Rr)(v)⇒⌈read⁡F,Rust(ar,mr)⊑read⁡F,C(ac,mc)⌉\operatorname{Auth}(m_{c}) * \operatorname{Auth}(m_{r}) * \operatorname{pair}_{q}(a_{c}, R_{c}\mid a_{r}, R_{r})(v) \Rightarrow\lceil\operatorname{read}_{F,\mathrm{Rust}}(a_{r},m_{r}) \sqsubseteq\operatorname{read}_{F,C}(a_{c},m_{c}) \rceil

where read⁡F,C\operatorname{read}_{F,C} reads aca_{c} in representation RcR_{c}, and read⁡F,Rust\operatorname{read}_{F,\mathrm{Rust}} reads ara_{r} in representation RrR_{r}.

For an input of multiple abstract values, the two lemmas apply to each abstract value allocated in memory, yielding a representation pair for each.

Library Specifications

We provide the specification of each library function, consisting of its pre- and postconditions, at the level of abstract values using representation predicates, to express that corresponding C and Rust functions perform the same operation. Although the two functions take different arguments and may represent their objects differently, their specifications describe the same update to the same abstract value. A specification is a Hoare triple ∀x. {P} f(a) {Q}\forall x.\ \{P\}\ f(a)\ \{Q\} with precondition PP and postcondition QQ: for every xx, a call to ff with arguments aa requires the resources PP and, when it returns, provides the resources QQ.

The specifications of sort in Figure 3 describe the same operation on the same abstract value, although the C and Rust functions take different arguments. The C function takes pointers to the first element and one past the last element, whereas the Rust function takes a pointer and a length; both preconditions describe the array specified by these arguments as a list vsvs in the representation Array i32. Both postconditions state that the same array then represents a sorted permutation wsws of vsvs.

The specifications of sort in C and Rust

Figure 3. The specifications of sort in C and Rust.

For C library functions, we prove that the specifications are sound with respect to their bodies, so these specifications do not need to be trusted. In contrast, for Rust library functions, our assumption libRust,std⊑ctxWfun(libRust)lib_{\mathrm{Rust},\mathrm{std}} \sqsubseteq_{\mathrm{ctx}} W_{\mathrm{fun}}(lib_{\mathrm{Rust}}) states that the specifications are trusted, as they are integrated into Wfun(libRust)W_{\mathrm{fun}}(lib_{\mathrm{Rust}}) and determine its behavior. We do not provide specifications for LLVM intrinsics.

To facilitate reasoning about common abstractions across library calls, we introduce Rule Pair-Update, which captures that when two corresponding calls that return without triggering IO events update the objects of a representation pair in the same way, the pair still holds after the calls, with the updated value:

∀v. {own1 ac◃Rc v} callc {own1 ac◃Rc (fc v)}∀v. {own1 ar◃Rr v} callr {own1 ar◃Rr (fr v)}callc,callr return without triggering IO events∀vc vr. vr⊑vc⇒fr vr⊑fc vc{pair1(ac,Rc∣ar,Rr)(vc)} callr≲callc {pair1(ac,Rc∣ar,Rr)(fc vc)}\begin{aligned} &\forall v.\ \{own_1\ a_c \mathbin{\triangleleft} R_c\ v\}\ call_c\ \{own_1\ a_c \mathbin{\triangleleft} R_c\ (f_c\ v)\}\qquad\forall v.\ \{own_1\ a_r \mathbin{\triangleleft} R_r\ v\}\ call_r\ \{own_1\ a_r \mathbin{\triangleleft} R_r\ (f_r\ v)\}\\ &call_c,call_r\ \text{return without triggering IO events}\qquad\forall v_c\ v_r.\ v_r \sqsubseteq v_c \mathrel{\Rightarrow} f_r\ v_r \sqsubseteq f_c\ v_c\\ &\{pair_1(a_c,R_c\mid a_r,R_r)(v_c)\}\ call_r\mathrel{\lesssim}call_c\ \{pair_1(a_c,R_c\mid a_r,R_r)(f_c\ v_c)\} \end{aligned}

Pair-Update

The upper premises of the rule are the specifications of the two calls: the C call updates the value of aca_c from vv to fc vf_c\ v, and the Rust call updates the value of ara_r from vv to fr vf_r\ v. The last premise requires the two updates to preserve refinement: if vrv_r refines vcv_c, then fr vrf_r\ v_r refines fc vcf_c\ v_c. The conclusion is expressed as a relational triple [55] {P} t≲s {Q}\{P\}\ t\mathrel{\lesssim}s\ \{Q\}, which means that, starting from PP, tt refines ss, and QQ holds when both terminate. It states that the value of the pair changes from vcv_c to fc vcf_c\ v_c. The rule is proved by unfolding the representation pair, applying each specification to its representation predicate, and folding the results using the last premise.

For example, we can reason about the corresponding sort calls in has duplicate using Rule Pair-Update. Before these calls, we have pair1((%v\a,%n), Array i32∣%s, Vec i32)(vs)pair_1((\%v\mathbin{\backslash}a,\%n),\ Array\ i32\mid\%s,\ Vec\ i32)(vs). The Rust sort borrows the buffer of the Vec, described by Array, so the rule applies to the C array and this buffer. By their specifications, both calls update vsvs to a sorted permutation, so both fcf_c and frf_r are sort—a function that returns the sorted list; the values of this pair are lists of defined integers, for which refinement is equality, so the last premise holds. After the calls, we thus have the same pair with value sort vssort\ vs.

Proving Refinement

We now show how to prove the refinement stated in Definition 1 using the resources and library specifications introduced in § 4. We split this refinement into a chain of refinement relations, where only one relation is program-specific, while the others can be proved once in advance and applied to every translation (§ 5.1), and prove the program-specific part through simulation (§ 5.2).

Chain of Refinements

To explain our refinement chain, we first introduce imaginary operations and wrappers in CRIS. To establish simulation, we need to reason about memory using resources, and CRIS enables this with imaginary operations that interact with resources through events during execution. Two imaginary operations are important in our discussion: Guarantee⁡(P)\operatorname{Guarantee}(P) provides resources satisfying PP, and Assume⁡(P)\operatorname{Assume}(P) receives them; if Assume⁡\operatorname{Assume} cannot receive the required resources, it triggers UB, and if Guarantee⁡\operatorname{Guarantee} cannot provide them, it triggers NB.

CRIS streamlines the introduction of appropriate imaginary operations into functions using wrappers [29, 45]: WfunW_{\mathrm{fun}} and WcallW_{\mathrm{call}} insert these operations according to the specification of each function. Wfun(M)W_{\mathrm{fun}}(M) inserts Take⁡\operatorname{Take} and Assume⁡\operatorname{Assume} for the precondition at the start of each function in MM and Choose⁡\operatorname{Choose} and Guarantee⁡\operatorname{Guarantee} for the postcondition at its end. Wcall(M)W_{\mathrm{call}}(M) inserts, around each function call in MM, Choose⁡\operatorname{Choose} and Guarantee⁡\operatorname{Guarantee} for the callee’s precondition before the call and Take⁡\operatorname{Take} and Assume⁡\operatorname{Assume} for the postcondition after it. For example, Wfun(libC)W_{\mathrm{fun}}(lib_C) defines sort as follows:

Wfun(libC)(sort)=λv.  vs←trigger⁡(Take⁡(list Z));  trigger⁡(Assume⁡ Psort(vs));W_{\mathrm{fun}}(lib_C)(sort) = \lambda v.\; vs \leftarrow\operatorname{trigger}\left(\operatorname{Take}(list\ Z)\right);\; \operatorname{trigger}\left(\operatorname{Assume}\ P_{sort}(vs)\right);
r←libC(sort)(v);r \leftarrow lib_C(sort)(v);
r′←trigger⁡(Choose⁡ Val);  trigger⁡(Guarantee⁡ Qsort(vs,r,r′));  Ret⁡ r′r' \leftarrow\operatorname{trigger}(\operatorname{Choose}\ Val);\; \operatorname{trigger}\left(\operatorname{Guarantee}\ Q_{sort}(vs,r,r')\right);\; \operatorname{Ret}\ r'

where PsortP_{sort} and QsortQ_{sort} are the pre- and postconditions of sort in Figure 3. If a function has no specification, WfunW_{\mathrm{fun}} and WcallW_{\mathrm{call}} insert no imaginary operations into the function’s body or around calls to it, respectively.

Now, the refinement stated in Definition 1 can be proved using the following chain of refinements:

program⁡(FRust,Wfun(libRust))=main⁡(FRust)⋆Wfun(libRust)⋆libLLVM\begin{aligned} \operatorname{program}(F_{Rust},W_{\mathrm{fun}}(lib_{Rust})) \\ &= \operatorname{main}(F_{Rust}) \star W_{\mathrm{fun}}(lib_{Rust}) \star lib_{LLVM} \end{aligned}
⊑ctxinline⁡(main⁡(FRust),Wfun(libRust)⋆libLLVM)(1) inlining(2)\sqsubseteq_{\mathrm{ctx}}\operatorname{inline}(\operatorname{main}(F_{Rust}),W_{\mathrm{fun}}(lib_{Rust}) \star lib_{LLVM}) \qquad(1)\ \text{inlining} \tag*{(2)}
⊑ctxinline⁡(Wfun(Wcall(main⁡(FC))),Wfun(libC)⋆libLLVM)(2) simulation (xref‘§5.2‘)(3)\sqsubseteq_{\mathrm{ctx}}\operatorname{inline}(W_{\mathrm{fun}}(W_{\mathrm{call}}(\operatorname{main}(F_C))),W_{\mathrm{fun}}(lib_C) \star lib_{LLVM}) \qquad(2)\ \text{simulation }({xref}`\S5.2`) \tag*{(3)}
⊑behWfun(Wcall(main⁡(FC)))⋆Wfun(libC)⋆libLLVM(3) uninlining(4)\sqsubseteq_{\mathrm{beh}} W_{\mathrm{fun}}(W_{\mathrm{call}}(\operatorname{main}(F_C))) \star W_{\mathrm{fun}}(lib_C) \star lib_{LLVM} \qquad(3)\ \text{uninlining} \tag*{(4)}
⊑behmain⁡(FC)⋆libC⋆libLLVM(4) cancellation=program⁡(FC,libC)(5)\begin{aligned} \sqsubseteq_{\mathrm{beh}} \operatorname{main}(F_C) \star lib_C \star lib_{LLVM} \qquad(4)\ \text{cancellation} \\ &= \operatorname{program}(F_C,lib_C) \tag*{(5)} \end{aligned}

Step 2 is the core of the chain: it shows that the Rust program refines the C program through simulation, as detailed in § 5.2. Since wrappers are applied to modules in this step, we can interact with resources through the inserted imaginary operations during simulation. Here, main⁡(FC)\operatorname{main}(F_C) is wrapped, but main⁡(FRust)\operatorname{main}(F_{Rust}) is not, because simulation in CRIS provides initial resources to the source (the C side) but not to the target (the Rust side) of the refinement. In addition, library function calls are inlined in these modules: for modules MM and LL, the module inline⁡(M,L)\operatorname{inline}(M,L) keeps only functions from MM, replacing any Call event to a function from LL with the body of that function. Inlining is required because C and Rust library functions may differ in their signatures, preventing corresponding Call events from being matched in simulation.

Steps 1 and 3 perform inlining and uninlining, and we prove these refinement relations in the lemma below:

Lemma 4 (Inlining and Uninlining). For modules MM and LL, the following hold:

(i) (Inlining) M⋆L⊑ctxinline⁡(M,L)M \star L \sqsubseteq_{\mathrm{ctx}} \operatorname{inline}(M,L).

(ii) (Uninlining) If MM defines an entry and LL does not,2{}^{2} then inline⁡(M,L)⊑behM⋆L\operatorname{inline}(M,L) \sqsubseteq_{\mathrm{beh}} M \star L.

Proof sketch. (i) Calls to MM’s functions behave the same in both modules; if a context calls a function in LL, the call triggers UB in inline⁡(M,L)\operatorname{inline}(M,L), which allows every behavior. (ii) Execution starts from the entry of MM, so LL’s functions are called only from within those of MM. inline⁡(M,L)\operatorname{inline}(M,L) runs them in place, as [M⋆L][M \star L] does at each call, so every behavior of inline⁡(M,L)\operatorname{inline}(M,L) is a behavior of M⋆LM \star L. □\square

Finally, step 4 removes wrappers using the cancellation theorem of CRIS, which states that Wfun(Wcall(M))⊑behMW_{\mathrm{fun}}(W_{\mathrm{call}}(M)) \sqsubseteq_{\mathrm{beh}} M if MM defines an entry and the precondition of the entry holds at the start. This holds because Guarantee⁡\operatorname{Guarantee} of a caller, inserted by WcallW_{\mathrm{call}}, matches Assume⁡\operatorname{Assume} of the callee, inserted by WfunW_{\mathrm{fun}}, and vice versa. In step 4, the precondition of the entry requires the authorities of the two initial memories, which can be established at the start of the program, so we can apply the cancellation theorem. Note that Wfun(Wcall(main⁡(FC))⋆Wfun(libC)⋆libLLVMW_{\mathrm{fun}}(W_{\mathrm{call}}(\operatorname{main}(F_C)) \star W_{\mathrm{fun}}(lib_C) \star lib_{LLVM} is the same as Wfun(Wcall(main⁡(FC)⋆libC⋆libLLVM))W_{\mathrm{fun}}(W_{\mathrm{call}}(\operatorname{main}(F_C) \star lib_C \star lib_{LLVM})): libClib_C has no function calls, so WcallW_{\mathrm{call}} does not introduce any imaginary operations; we provide no specifications for libLLVMlib_{LLVM}, so wrappers insert no imaginary operations; and wrappers distribute over linking.

Establishing Simulation

We now show how to prove step 2 through simulation. The adequacy theorem of CRIS states that for functions with the same name in two modules, if the execution of the target function can be matched by that of the source function with the same IO events, then the target contextually refines the source.

The beginning and end of the simulation are handled by the lemmas stated in §4.2. Lemma 2 provides a representation pair for the input before the LLVM IR functions are called, and, by Lemma 3, if the two functions maintain the representation pair, we obtain refinement between the outputs.

The remaining task is to prove that the ITrees denoted by the two LLVM IR functions FCF_C and FRustF_{Rust} maintain the representation pair and relate their return values, as described by the following relational triple:

{Auth⁡(mc)∗Auth⁡(mr)∗pair⁡1(ac,Rc∣ar,Rr)(v)}⟦FRust⟧(args⁡Rust(v,ar),mr)≲⟦FC⟧(args⁡C(v,ac),mc){λ(rr,mr′)(rc,mc′).Auth⁡(mc′)∗Auth⁡(mr′)∗∃v′.pair⁡q(ac,Rc∣ar,Rr)(v′)∗⌜rr⊑rc⌝}\begin{aligned} &\{ \operatorname{Auth}(m_c) * \operatorname{Auth}(m_r) * \operatorname{pair}_1(a_c, R_c \mid a_r, R_r)(v) \}\\ &\qquad\llbracket F_{Rust}\rrbracket(\operatorname{args}_{Rust}(v,a_r),m_r) \lesssim\llbracket F_C\rrbracket(\operatorname{args}_C(v,a_c),m_c)\\ &\{ \lambda(r_r,m'_r)(r_c,m'_c). \operatorname{Auth}(m'_c) * \operatorname{Auth}(m'_r) * \exists v'.\operatorname{pair}_q(a_c,R_c \mid a_r,R_r)(v') * \ulcorner r_r \sqsubseteq r_c\urcorner\} \end{aligned}

The precondition consists of the memory authorities and the resources from Lemma 2; the postcondition consists of the authorities of the final memories, the resources required by Lemma 3, and refinement between the return values. We call this triple the obligation, as it is the only part proved separately for each translation.

To prove the obligation, we use the simulation rules provided by CRIS, as well as a few convenience rules we derived from CRIS’s rules, with representative ones shown in Figure 4. Rules Reduce-C and Reduce-Rust execute code that triggers no events on one side; reduces⁡(s,s′)\operatorname{reduces}(s,s') states that ss can be reduced to s′s' by executing a part of ss that triggers no events. Computations on registers and memory that do not cause UB trigger no events, so these rules can be applied to them. In contrast, calls to functions with specifications cannot be reduced, because the wrappers introduce imaginary operations around them, and we introduce separate rules for handling these calls: Rules Call-C and Call-Rust execute a library call using the specification of the callee. The rules provide the precondition PP and continue, for every return value rr, with the postcondition Q(r)Q(r), preserving the other resources RR. Both rules also require the library function to return without triggering IO events. Note that these rules are usable even though we inline functions because ITrees are coinductively defined and their unfolding is lazy; a function is inlined only when a term with a Call event is unfolded, and we can apply these rules before the unfolding. Since these two rules execute a program on one side, the two programs need not make corresponding calls. When two calls that return without IO events correspond, Rule Pair-Update stated in §4.3 can be used. It is derived from the above two rules: it unfolds the pair, applies Call-C and Call-Rust, and folds the results back.

Representative simulation rules derived from the rules of CRIS

Figure 4. Representative simulation rules derived from the rules of CRIS.

Now, we demonstrate simulation using these rules with a proof of has_duplicate, whose outline is shown in Figure 5. The proof involves two representation pairs: paira^{a} denotes the input, pair1((%a,%n),Array⁡ i32∣(%a.0,%a.1),Array⁡ i32),andpair_1((\%a,\%n),\operatorname{Array}\ i32 \mid(\%a.0,\%a.1),\operatorname{Array}\ i32), and pair^{r}$ denotes the local copies, pair1((% ⁣vla,%n),Array⁡ i32∣%s,Vec⁡ i32)_1((\%\!vla,\%n),\operatorname{Array}\ i32 \mid\%s,\operatorname{Vec}\ i32). We split the proof into six parts, (a)–(f), where Lemma 2 handles (a) and Lemma 3 handles (f).

Proof outline of has_duplicate

Figure 5. Proof outline of has_duplicate. The left and right columns show corresponding code of the two drivers and of the two IRs in Figure 1, where comments summarize the instructions that only compute register values; the middle column shows the resources after each row, omitting the memory authorities and the ownership of local allocations, or the trace element that both sides produce.

In (b), Rules Reduce-C and Reduce-Rust execute alloca, which provides ownership of the local copies; Reduce-C also executes memcpy, which is an LLVM intrinsic with no specification, and Call-Rust applies the specification of to_vec. The two copies then represent vsvs, so their predicates fold into pair⁡s(vs)\operatorname{pair}^{s}(vs). If the VLA exceeds the stack allocation limit, the C alloca triggers UB and the simulation ends there, so the proof need not exclude such inputs.

In (c), the two sort calls update pair⁡s(vs)\operatorname{pair}^{s}(vs) to pair⁡s(ws)\operatorname{pair}^{s}(ws), where wsws is the sorted permutation of vsvs. Since the Rust sort is called on the buffer of the Vec, which Reduce-Rust loads, the proof applies Pair-Update to the C array and this buffer, unfolding and folding the predicates as follows:

\begin{aligned} &\{\operatorname{pair}^{s}(vs)\}\\ &\{\operatorname{own}_{1}(\%vla,\%n)\mathbin{\triangleleft}(\operatorname{Array}\ i32)\ vs * \operatorname{own}_{1}\ \%s\mathbin{\triangleleft}(\operatorname{Vec}\ i32)\ vs\}\\ &\{\operatorname{own}_{1}(\%vla,\%n)\mathbin{\triangleleft}(\operatorname{Array}\ i32)\ vs * \%s \mapsto_{1}(c,\%buf,\%len)\\ &\qquad*\operatorname{own}_{1}(\%buf,\%len)\mathbin{\triangleleft}(\operatorname{Array}\ i32)\ vs\}\\ &\{\%s \mapsto_{1}(c,\%buf,\%len) * \operatorname{own}_{1}(\%vla,\%n),\operatorname{Array}\ i32\mid(\%buf,\%len),\operatorname{Array}\ i32)(vs)\}\\ &\qquad@\operatorname{sort}(\%buf,\%len)\preccurlyeq@\operatorname{sort}(\%vla,\%add.ptr)\\ &\{\%s \mapsto_{1}(c,\%buf,\%len) * \operatorname{pair}_{1}(\%vla,\%n),\operatorname{Array}\ i32\mid(\%buf,\%len),\operatorname{Array}\ i32)(ws)\}\\ &\{\operatorname{own}_{1}(\%vla,\%n)\mathbin{\triangleleft}(\operatorname{Array}\ i32)\ ws * \operatorname{own}_{1}\ \%s\mathbin{\triangleleft}(\operatorname{Vec}\ i32)\ ws\}\\ &\{\operatorname{pair}^{s}(ws)\} \end{aligned}

In (d), the two loops are related using the coinduction principle [23, 59] provided by CRIS. The proof chooses an invariant that holds at the start of every iteration of both loops. It then executes one iteration of each loop under the invariant: either both loops exit, or both start the next iteration with the invariant holding again. In the latter case, since both loops have made progress, the invariant allows the proof to assume that the two loops are related. Here, the invariant is pair⁡a(vs)∗pair⁡s(ws)∗Iloop\operatorname{pair}^{a}(vs) * \operatorname{pair}^{s}(ws) * I_{\mathrm{loop}}, where IloopI_{\mathrm{loop}} states that the C index is ii and the Rust window starts at i−1i-1 for some 1≤i<n1 \leq i < n. In each iteration, both loops compare ws[i−1]ws[i-1] and ws[i]ws[i]; if they are equal or i+1=ni+1=n, both loops exit with the same result, and otherwise both start the next iteration with i+1i+1, where the invariant holds again.

In (e), Call-Rust applies the specification of drop_in_place, which frees the buffer of the Vec, and the two functions release their stack allocations upon return, including the local copies. Both return the same value, and the resources at return, pair⁡a(vs)∗⌜r=%more⌝\operatorname{pair}^{a}(vs) * \ulcorner r = \%more \urcorner, satisfy the postcondition of the obligation.

Automating Translation Validation with AI Agents

We fully automate the translation validation process using AI agents in the workflow depicted in Figure 6. It involves two agentic steps: argument matching and obligation proof. All other steps are implemented as algorithmic procedures without involving agents. In this section, we discuss each step of the workflow.

Figure 6. The translation validation workflow. Dashed boxes are agentic steps; solid boxes are algorithmic steps; labels show what each step passes on.

Input. The input includes a C source, its Rust translation, the name of the public entry function to be validated, and a restriction on the function’s input space. The current implementation provides a list of predefined restrictions, and the user may select one of them for each argument: an integer is nonzero/nonnegative/positive; a list is nonempty; a list contains only nonnegative/positive elements; a string contains only binary-digit/decimal-digit/lowercase characters. Extending the implementation to support an arbitrary Rocq predicate would not be challenging.

Argument matching. Agent 1 determines the correspondence between the arguments of the two functions and assigns a common abstraction to each pair. For example, for has_duplicate, the agent matches the C arguments (a, n) with the Rust argument a and assigns List as their common abstraction. A function may have multiple argument pairs with common abstractions, e.g., when taking two lists as input.

Compilation. We use the same compiler settings for every input (see §B for the exact settings). We disable optimizations that may cause the two LLVM IRs to differ unnecessarily in structure; for example, we disable loop unrolling since the two compilers may unroll a loop by different factors. We also prevent inlining of each library function call if the callee is defined in our library modules, and let the compilers inline the other library calls; in has_duplicate, windows and any are inlined to form a loop as in C, whereas the sort functions in both C and Rust are not inlined and can be reasoned about using their specifications.

After compilation, since our LLVM IR semantics does not support undef, we replace undef in the C-side LLVM IR with poison and undef in the Rust-side LLVM IR with zero or null, depending on the value’s type. This conversion may add behaviors to the C program and remove behaviors from the Rust program, making the refinement easier to establish. However, the validation remains sound in most cases, assuming that the translation uses only safe Rust. In the C-side IR, undef is either never read or represents the value of an uninitialized variable, whose read is already UB in the C source. In the Rust-side IR, undef is never read if the compiler is correct, since safe Rust never reads a value before initializing it.

Template generation. We generate a template for the refinement proof, consisting of the two drivers and the refinement chain, where the obligation of the simulation proof is the only part left to be proved by an agent in a subsequent step. Generating drivers requires defining valid_input_F, register_F,X, args_F,X, and read_F,X. Their exact behavior depends on the argument types and the argument matching. For each function, we prepare a building block for each supported argument type and common abstraction listed in Table 1 and compose them to complete the drivers even when multiple argument pairs are found. In addition, valid_input_F combines the given restriction with the condition that the input fits within the size bounds of the architecture.

Obligation proof. Agent 2 proves the given obligation using the provided simulation rules. The proof ideas described in § 5.2 are provided as skills to guide the agent. The agent can only modify its proof files and is not allowed to weaken the final theorem stating the refinement.

Proof check. Once the agent completes the proof, the Rocq kernel checks it, and we also ensure that no additional axioms or admits have been introduced. A failed proof is returned to the agent for revision.

Counterexample check. When the agent determines that the refinement is unprovable, it proposes a counterexample, which is an input on which the two LLVM IR programs behave differently. To validate the counterexample, we run the two programs on the suggested input. If the C-side program incurs UB, the counterexample is invalid even when the outputs differ between C and Rust. For this reason, we extract the ITree of the C-side driver into OCaml [51, 58] and execute it, detecting any UB event and obtaining results that may contain poison. We then run the Rust program natively and compare its results with those of C up to value refinement. An invalid counterexample is returned to the agent.

Output. The workflow ends with one of three outcomes: proved, counterexample, or fail, where fail covers every outcome other than proved or counterexample. A counterexample does not necessarily mean that the translation is incorrect because validation is performed at the LLVM IR level. In particular, if the C source has UB but it becomes defined behavior in the LLVM IR, we may obtain a false counterexample. Therefore, the user should review the counterexample to determine whether it is genuine.

Evaluation

In this section, we describe our implementation of R2C2 (§ 7.1), evaluate it on 519 C programs (§ 7.2), and conduct a case study on a larger C program (§ 7.5). Our experiments were conducted on an Ubuntu machine with an AMD Ryzen 9 9950X 16-core processor (16 cores, 32 threads, 4.3 GHz) and 128 GB of DRAM.

Implementation

R2C2 is implemented in Rocq 9.0 on top of the CRIS [29] and ITrees [51] libraries. Our development adds no axioms: the eight axioms it relies on are all assumed by the libraries it uses. We use Codex CLI and Claude Code to run agents. To improve proof construction, we set the context window of Agent 2 to 872k tokens in Codex CLI. Our library modules include 29 LLVM intrinsics, 25 C library functions, and 49 Rust library functions. These include C functions for memory allocation, strings, math, characters, and I/O, and Rust functions for Vec, slices, str, memory allocation, I/O, and panics. For Rust Vec and slices, the supported element types are i32, u32, i64, u64, u8, bool, and char, as well as nested Vec for two-dimensional arrays. Our trusted computing base comprises the Rocq kernel, the definitions of ITrees and CRIS modules, from which behaviors and refinement are defined, the Vellvm parser that turns LLVM IR files into Rocq definitions, our Vellvm-based LLVM IR semantics, including its memory model, and our library modules.

Evaluation on the VERT Benchmarks

We evaluate R2C2 on the benchmark suite of VERT [53], which includes 519 C programs.3 Of these, 504 programs are from the TransCoder-IR dataset [46], implementing algorithms involving loops and recursion over integers, floating-point numbers, arrays, strings, and two-dimensional arrays. The other 15 programs are parts of projects collected from prior work on C-to-Rust translation [10, 60], and they use structs with pointers. Each program has 13.3 LOC on average, with a maximum of 154 LOC. We translated each C program into Rust using gpt-6-luna via Codex CLI, with a prompt requesting a safe, idiomatic translation. We manually determined the input restrictions for each program.

We evaluate R2C2 with the following three research questions (RQs):

RQ1. Effectiveness: For how many translations does R2C2 prove correctness or find a counterexample, and how do the results compare with existing C-to-Rust translation validation tools? (§ 7.3)

RQ2. Efficiency: How much time and cost does translation validation require? (§7.2.2)

RQ3. Impact of model choice: How do effectiveness and efficiency vary with the agent model? (§ 7.4.1)

For RQ1 and RQ2, we used gpt-6-luna as Agent 1 and gpt-6.1-sol as Agent 2, both via Codex CLI.

RQ1: Effectiveness

Of the 519 translations, R2C2 proves the correctness of 486, finds a counterexample for 26, and fails on 7, demonstrating the effectiveness of our approach. The seven failures are due to unsupported features: four involve recursive structs, one involves an Option<String> return value, one involves the mustprogress LLVM IR attribute, which our LLVM IR semantics does not model, and one involves closures.

We manually investigated the 26 counterexamples and found that 3 are genuine counterexamples, while the other 23 are false positives. We now discuss representative cases in detail.

Figure 7(a) shows one incorrect translation, which fails to preserve the behavior on large inputs. The C program stores the length of a given string in int n, truncating the 64-bit result of strlen. For example, if a string has length 232+32^{32}+3, nn is 3, and C copies only the first 3 characters into arr of length 4. The Rust program also truncates the length, but it iterates over the entire string and panics due to an out-of-bounds index for arr. This example demonstrates the effectiveness of R2C2 in finding subtle translation errors.

C code (left) and Rust code (right) of translations for which a counterexample is found

Figure 7. C code (left) and Rust code (right) of translations for which a counterexample is found: (a)–(b) incorrect translations, (c) a translation whose counterexample causes UB, and (d) the LLVM IRs compiled from (c).

The other two incorrect translations share the same cause, and we show one case in Figure 7(b). The C program calls calloc, which returns NULL when allocation fails, but the Rust program uses vec!, which panics on allocation failure. Strictly speaking, this does not preserve the behavior of C, but one may want to consider such a translation correct, as vec! is an idiomatic way of allocating memory in Rust, and allocation failure is rare in practice. For this purpose, we could modify the models of the allocation functions to never fail.

The 23 false positives occur when the C program exhibits UB that is compiled into defined behavior in LLVM IR. Of these, 20 arise from signed integer overflow and 3 from accesses beyond a row of a two-dimensional array. Figure 7(c) shows one case: when sum equals INT_MAX, sum + 1 overflows, which is UB in C. However, the C-side LLVM IR in Figure 7(d) does not result in UB: sum + 1 is not marked as non-wrapping, so it wraps around into INT_MIN; zext zero-extends it to 2312^{31}, and a contract of this size is allocated. In contrast, the Rust-side LLVM IR sign-extends INT_MIN to a huge size with sext, and from_elem panics due to a capacity overflow.

We also manually reviewed the compiled LLVM IR programs to confirm that our removal of undef does not affect these outcomes. In these programs, all occurrences of undef are either operands of phi or select: in 9 C programs and 62 Rust programs, undef appears but is never read; in 5 C programs, it represents the value of an uninitialized variable, and reading it is already UB in C.

Comparison with existing tools

We compare the effectiveness of R2C2 with that of two existing C-to-Rust translation validation tools, VERT [53] and RustAssure [1], using the same translations.

VERT compares each translation with a Rust program obtained by compiling the C program to WebAssembly and then translating it to Rust using rWasm [4]. It first runs property-based testing and then performs bounded model checking, each for 120 seconds, unrolling each loop up to 14 iterations. We classify its outcome as validated if both testing and bounded model checking pass, counterexample if either check finds a difference, or fail if it produces no result, e.g., due to a timeout or a compilation or runtime error.

RustAssure symbolically executes the LLVM IR of the two programs and compares graphs representing their symbolic return values using edit distance. It limits symbolic execution to 180 minutes per function with input arrays of 100 elements. We classify its outcome as validated if it finds no difference, difference if it reports a difference, or fail if it produces no result. A reported difference only indicates a potential difference in the output and does not provide an input that can serve as a counterexample.

Note that a validated outcome from either tool does not provide a correctness guarantee as strong as that of R2C2. Their validation covers only a subset of possible inputs and handles loops only up to a bound, failing to cover all possible executions. In contrast, R2C2 considers all valid inputs with respect to user-provided input restrictions and executions of arbitrary length, including nonterminating ones, using coinduction.

The experimental results, summarized in Table 2, show that R2C2 is more effective than the existing tools. Of the 519 translations, VERT validates 158, finds a counterexample for 132, and fails on 229; RustAssure validates 147, reports a difference for 74, and fails on 298. We now discuss the differences in the results.

R2C2VERT ValidatedVERT CounterexampleVERT FailRustAssure ValidatedRustAssure DifferenceRustAssure FailTotal
Proved15212021414268276486
Counterexample5129561526
Fail1060077
Total15813222914774298519

Table 2. Results of R2C2, VERT, and RustAssure on the 519 translations.

VERT reports a counterexample for 120 translations that R2C2 verifies, but none of them is a genuine counterexample: 65 are due to providing invalid inputs to functions, e.g., passing an array pointer and a symbolic integer independent of the array length, when the function expects the correct length, resulting in out-of-bounds access; 32 are due to checking strict equality of outputs rather than refinement, e.g., rejecting a case where the C program has UB and the Rust program panics; 23 are due to incorrect preprocessing that changes the behavior before the checks, e.g., replacing f64f64 with f32f32.

RustAssure reports a difference for 68 translations that R2C2 verifies; it only provides different graphs, not a counterexample. We investigated how different graphs arise from symbolic execution and identified two notable causes: it sometimes fails to match C and Rust arguments, providing different symbolic inputs to the two programs; when symbolic execution times out, it compares incomplete graphs.

For the three incorrect translations discovered by R2C2, neither tool provides a valid counterexample. For Figure 7(a), VERT provides a counterexample consisting of an invalid input, rather than a genuine one involving an extremely long string; RustAssure only reports a difference. Both tools fail on the two cases involving structs with heap buffers. For the 23 false positive cases from R2C2, VERT and RustAssure each validate 5 cases. However, these results are only because they cover a limited set of inputs, not because they appropriately handle UB in C at the source level. VERT samples inputs randomly and checks only small values during bounded model checking, while RustAssure explores only some paths within its time limit and fixes some inputs to constants. Neither tool exercises extreme input values such as INT_MAX.

Efficiency

7.2.2 RQ2: Efficiency. We assess the efficiency of R2C2 by measuring the time and cost of validation. We measured the end-to-end runtime of the entire workflow and counted the tokens used, calculating the cost based on the public API pricing of each model. On average, across the 512 translations excluding the 7 failures, R2C2 took 23.3 minutes and cost $2.91, with Agent 2 accounting for almost all of the time (98.1%) and cost (99.9%). For the 486 proved cases, it took 24.2 minutes and cost $3.05; for the 26 cases with counterexamples, it took 6.6 minutes and cost $0.31. Most cases took much less than the average, with medians of 13.0 minutes and $1.09. The distributions are skewed toward a few translations, with 90th percentiles of 46.6 minutes and $6.84. The most expensive case took 338.4 minutes and cost $44.31 and contains a triple-nested loop.

To better understand how program characteristics affect time and cost, we investigate how they correlate with the number of lines and the number of calls in the LLVM IRs from C and Rust, and the number of loops in the C source, showing the results in Figure 8. These features correspond to the work involved in our proofs: lines represent instructions that the proof simulates, calls are where it applies library specifications and matches the calls of the two programs, and loops are where it requires coinduction and invariants. We measure the correlations using Spearman’s rank correlation coefficient ρ\rho, which measures how consistently one value increases with the other: it is 1 when their rankings coincide and 0 when there is no rank correlation. For time and cost, ρ\rho is 0.76 and 0.73 for lines, 0.67 and 0.69 for calls, and 0.63 and 0.59 for loops (all p<0.001p < 0.001), so the correlations are strongest for lines, followed by calls and loops.

Figure 8. Time (top) and cost (bottom) of validating the 512 translations by the lines and the calls of the C and Rust IRs and the loops of the C source; in the scatter plots, dots are proved translations and crosses are counterexamples, and the whiskers of the box plots extend to 1.5 times the interquartile range.

RQ3: Impact of model choice

To see how the model affects the effectiveness and efficiency of R2C2, we measured the time and cost of running Agent 2 with four models on 21 programs. We selected seven programs from each of three difficulty levels defined by the time gpt-6.1-sol spent on them in RQ2: at most 10 minutes (easy), 30 to 60 minutes (medium), and at least 140 minutes (hard). We compare three OpenAI models, gpt-6.1-terra, gpt-6.1-sol, and gpt-6-astra, in increasing order of general performance and API price, using Codex CLI, and Anthropic’s frontier model, claude-opus-5-5, using Claude Code.

The experimental results, summarized in Table 3, show that our approach generalizes to other models. Only gpt-6.1-terra failed to finish one hard program within the six-hour time limit; all other models completed all programs. Therefore, we believe that R2C2 can use most of today’s frontier models for running agents, while less capable models may not be suitable for validating difficult translations.

ModelProvedEasy (7) TimeEasy (7) CostMedium (7) TimeMedium (7) CostHard (7) TimeHard (7) Cost
gpt-6.1-terra2010.80.6585.312.67200.940.77
gpt-6.1-sol217.70.5741.55.73193.427.29
gpt-6-astra218.83.8646.427.80150.4155.65
claude-opus-5-5216.82.8752.927.64136.660.78

Table 3. Proved translations, average time (minutes), and average cost (USD) of Agent 2 with four models on the 21 programs, seven at each level of difficulty.

In addition, the time and cost vary across models, so the choice of model can affect the efficiency of our approach. In terms of time, gpt-6-astra and claude-opus-5-5 do not show meaningful improvements over gpt-6.1-sol for easy and medium programs, and their advantages are clear only for hard programs. In terms of cost, gpt-6.1-sol finished at the lowest cost across all levels, although gpt-6.1-terra has the lowest per-token price. This shows that a cheaper model does not necessarily lead to a lower validation cost, and one needs to find a balance between the model’s capability and its price to reduce the validation cost.

Case Study: QOI

Beyond the VERT benchmarks, we conduct a case study on a larger program to demonstrate how R2C2 handles more complex features. We use QOI,4 a lossless image compression format [5], whose reference implementation in C consists of 312 lines and four functions: qoi_decode takes a buffer containing compressed data and allocates and returns a new buffer containing decompressed pixels; qoi_read reads a file, decodes the data with qoi_decode, and returns the pixel buffer; qoi_encode and qoi_write perform the inverse operations. We treat qoi_read and qoi_write as public functions and validate the translation of each. R2C2 successfully validated qoi_read and qoi_write, with Agent 2 using gpt-6.1-sol taking 12.6 and 7.0 hours, respectively. We now discuss the validation of qoi_read in more detail.

One important aspect of qoi_read is that it returns a pointer to an array. Its signatures are as follows:

void *qoi_read(const char *filename, qoi_desc *desc, int channels); // C
fn qoi_read(filename: &str, desc: &mut QoiDesc, channels: u8) -> Option<Vec<u8>>; // Rust

To compare the return values appropriately as abstract values, Agent 1 also determines the common abstraction for return values during argument matching, assigning List in this case. Furthermore, when this Rust function is compiled into LLVM IR, the return type becomes void, and the result is produced by writing it to the memory pointed to by the first argument %_0:

define void @qoi_read(ptr sret([24 x i8]) %_0, ptr %filename.0, i64 %filename.1, ptr %desc, i8 %channels)

Template generation recognizes this pattern by examining the return type and the number of parameters and generates the following driver so that the return value can be observed correctly:

driver⁡(qoi_read⁡Rust)≜λ_.v←trigger IO⁡("input",());if ¬valid_input⁡qoi_read⁡(v) then Ret Noneelse (p,q,m)←register⁡qoi_read⁡,Rust(v,m0);(_,m′)←⟦qoi_read⁡Rust⟧(args⁡qoi_read⁡,Rust(v,p,q),m);o←observe⁡(read⁡qoi_read⁡,Rust(q,m′));o′←observe⁡(read⁡qoi_read⁡,Rust(p,m′));Ret⁡(Some⁡(o,o′))\begin{aligned} \operatorname{driver}(\operatorname{qoi\_read}_{\mathrm{Rust}}) &\triangleq\lambda\_.\\ v &\leftarrow\operatorname{trigger\ IO}(\text{"input"}, ());\\ \text{if } \neg\operatorname{valid\_input}_{\operatorname{qoi\_read}}(v) &\text{ then Ret None}\\ \text{else } (p,q,m) &\leftarrow\operatorname{register}_{\operatorname{qoi\_read},\mathrm{Rust}}(v,m_0);\\ (\_,m') &\leftarrow\llbracket\operatorname{qoi\_read}_{\mathrm{Rust}}\rrbracket(\operatorname{args}_{\operatorname{qoi\_read},\mathrm{Rust}}(v,p,q),m);\\ o &\leftarrow\operatorname{observe}(\operatorname{read}_{\operatorname{qoi\_read},\mathrm{Rust}}(q,m'));\\ o' &\leftarrow\operatorname{observe}(\operatorname{read}_{\operatorname{qoi\_read},\mathrm{Rust}}(p,m'));\\ &\operatorname{Ret}(\operatorname{Some}(o,o')) \end{aligned}

Its register additionally allocates q, a memory location where the return value will be written, and args constructs the first argument using q. After the function call, the nominal return value of type void is ignored, and the actual return value is read from memory as a list using read with q.

Another important aspect is that qoi_read performs file operations. In C, it opens a file with fopen to obtain a FILE * handle, reads through it using fread, and closes it using fclose; in Rust, it uses File::open to obtain a File object, reads from it using read_exact, and drops it to close the file. We introduce representation predicates for C FILE and Rust File as follows:

own⁡q p◃FILE s≜∃meta⁡. p↦q (s,meta⁡)\operatorname{own}_{q}\ p \triangleleft\mathrm{FILE}\ s \triangleq\exists\operatorname{meta}.\ p \mapsto q\ (s,\operatorname{meta})
own⁡q p◃File s≜p↦q s\operatorname{own}_{q}\ p \triangleleft\mathrm{File}\ s \triangleq p \mapsto q\ s

where ss is a 32-bit integer that serves as a file descriptor. C FILE consists of a file descriptor and metadata, such as error and end-of-file indicators and the current position; Rust File just wraps the file descriptor. The common abstraction File relates them with the following representation pair:

pair⁡q(pc,FILE∣pr,File)(s)≜own⁡q pc◃FILE s∗own⁡q pr◃File s\operatorname{pair}_{q}(p_{c}, \mathrm{FILE} \mid p_{r}, \mathrm{File})(s) \triangleq\operatorname{own}_{q}\ p_{c} \mathrel{\triangleleft} \mathrm{FILE}\ s * \operatorname{own}_{q}\ p_{r} \mathrel{\triangleleft} \mathrm{File}\ s

The library modules describe I/O functions by triggering distinct IO events for each kind of operation, consistently on both the C and Rust sides: fopen and File::open trigger an event named file.open; fread and read_exact trigger file.read; fclose and dropping a File trigger file.close. This allows the same events to be matched during simulation.

Note that we do not claim to fully support I/O operations in this work; the purpose of this case study is to demonstrate that R2C2 can reason about I/O by modeling library functions with events in ITrees. The current implementation includes only a few functions and excludes several features, such as the buffering behavior of C FILE. Furthermore, events alone would not be sufficient: for example, a translation may read a file through a single call, while the source reads the same data through multiple calls, resulting in a different number of events and causing simulation to fail. Validating translations that heavily involve I/O would be an interesting direction for future work.

Related Work

C-to-Rust translation. C2Rust [15] syntactically translates C into unsafe Rust, and other rule-based translators aim to produce safer Rust, either by improving the output of C2Rust or by translating C directly: some replace raw pointers with references or other smart pointers by analyzing ownership and aliasing [7, 9, 10, 12, 60], others replace C types and APIs with their Rust counterparts, such as tagged unions, generics, algebraic data types, locks, and I/O [16, 18, 19, 20, 22, 28, 50], and techniques for different features can be combined [17]. LLM-based translators combine LLMs with program analysis or iterative repair [6, 21, 44, 52, 57, 61, 62]. Most of these studies evaluate the correctness of their translations through testing.

Translation validation. Pnueli et al. [41] proposed translation validation, which checks each translation instead of the translator. It has been applied to optimizing compilers [2, 39], and its validators have themselves been verified in the verified compiler CompCert [34, 47, 48]. LLVM IR has since become a major target of translation validation: Alive2 [36] validates LLVM optimizations with SMT queries over bounded executions, and Crellvm [27] lets the optimizations generate proofs that a verified checker validates. These validators relate programs in the same language, whereas we relate IR programs compiled from two different languages. Translation validation has also been applied to C-to-binary compilation [42], optimized x86 binaries [43], and V8’s JIT compiler [31].

Refinement theory. Our proofs build on CRIS [29], a Rocq framework for contextual refinement that generalizes Conditional Contextual Refinement [45], which unifies refinement and separation logic. They follow a line of work on proving contextual refinement using relational separation logics [14, 55]; their resources follow separation logic [40] as formalized in Iris [25, 26, 30], and their proofs of loops use parameterized coinduction [23, 59]. Programs in CRIS are ITrees [51], which represent effectful programs as coinductive trees of events, so semantics defined using ITrees are both executable and composable by interpretation [56].

LLM-based proof generation. Proofs generated by LLMs still provide formal guarantees once they are checked by a proof assistant, such as Rocq or Lean, or a verifier. This idea has increasingly been applied to proving existing theorems in a proof assistant [11], verifying programs against their specifications [54], and proving equivalence between a program and its LLM translation [3]. Recently, an LLM proved the memory safety of binaries of real-world libraries against mechanically generated specifications [37]. We follow this idea and apply it to C-to-Rust translation validation.

Formal foundations. Formal semantics of C and Rust have been developed for their own purposes: for C, to verify a compiler [34] or to clarify its standards [38], and for Rust, to prove the soundness of its type system [24] or to verify programs against their specifications [13, 32]. However, none of them defines the behaviors of C and Rust programs in the same terms, as required for C-to-Rust translation validation. We therefore turned to LLVM IR and chose Vellvm [58], a semantics of LLVM IR defined using ITrees. Another option is to define semantics for C and Rust separately but in the same terms: translation validation requires semantics for both languages but not a single semantics for both, just as CompCert [34] gives each of its languages its own semantics and relates them through their behaviors. We leave this option, which would validate translations at the source level, for future work.

Conclusion

We present R2C2, a tool that validates C-to-Rust translation by proving in Rocq that the Rust program refines the C program at the LLVM IR level. The use of LLVM IR allows us to describe the behavior of programs in the two languages in the same terms. We relate the different data representations of C and Rust through common abstractions and reason about library function calls using their specifications over abstract values. Refinement is established through a chain of refinement relations, where the program-specific part is proved by AI agents. We evaluate R2C2 on 519 C programs from VERT. It effectively validates translations, proving the translations of 486 programs correct without bounding their executions and finding three incorrect translations with valid counterexamples. On average, it validated each translation in 23.3 minutes at a cost of $2.91 using gpt-6.1-sol. We also conduct a case study on QOI, demonstrating how R2C2 can handle file operations.

References

Semantics of LLVM IR

This appendix describes the semantics of LLVM IR. A subset of the syntax of LLVM IR is shown in Figure 9. Metavariables σ\sigma, α\alpha, \@g, \@f, and ℓ\ell range over the names of registers, global variables, functions, and basic blocks, respectively. Each instruction in a basic block is paired with a register that receives its result, if it has one. Figure 10 shows the denotations of expressions, instructions, and terminators. The pure functions gep, alloca, load, and store return a value of the following type:

A subset of the syntax of LLVM IR

Figure 9. A subset of the syntax of LLVM IR.

The semantics of expressions, instructions, and terminators

Figure 10. The semantics of expressions, instructions, and terminators. On right-hand sides, ⟦e⟧\llbracket e\rrbracket stands for ⟦e⟧(ρ,m)\llbracket e\rrbracket(\rho,m). Functions in blue are pure functions.

MemoryResult A::=Success A∣Failure\mathit{MemoryResult}\ A ::= \mathit{Success}\ A \mid\mathit{Failure}

They return Failure when the operation is undefined, such as an access outside an allocated block, and the denotation then triggers UB. op returns its result in the same form, returning Failure on a division by zero or an overflow of signed division.

For a block BB entered from the block ℓ′\ell', [ ⁣[B.phis] ⁣](ρ,ℓ′)[\![B.\mathit{phis}]\!](\rho,\ell') evaluates every phi node of BB in ρ\rho for ℓ′\ell' and assigns their registers at once. The code of BB, denoted by [ ⁣[B.code] ⁣](ρ,m)[\![B.\mathit{code}]\!](\rho,m), runs the instructions of BB in order, writing each result to the assigned register; an instruction with no result, such as store, leaves ρ\rho unchanged.

run(ρ,m,ℓ′,ℓ)=ρ0←[ ⁣[Bℓ.phis] ⁣](ρ,ℓ′);  (ρ1,m1)←[ ⁣[Bℓ.code] ⁣](ρ0,m);  o←[ ⁣[Bℓ.term] ⁣](ρ1,m1);match o with inl ℓ′′⇒Tau(run(ρ1,m1,ℓ,ℓ′′))∣inr v⇒Ret(v,m1)\begin{aligned} \mathit{run}(\rho,m,\ell',\ell) &= \rho_0 \mathrel{\leftarrow} [\![B_\ell.\mathit{phis}]\!](\rho,\ell');\;(\rho_1,m_1) \mathrel{\leftarrow} [\![B_\ell.\mathit{code}]\!](\rho_0,m);\; o \mathrel{\leftarrow} [\![B_\ell.\mathit{term}]\!](\rho_1,m_1);\\ &\quad\mathit{match}\ o\ \mathit{with}\ \mathit{inl}\ \ell'' \Rightarrow\mathit{Tau}\left(\mathit{run}(\rho_1,m_1,\ell,\ell'')\right)\mid\mathit{inr}\ v \Rightarrow\mathit{Ret}(v,m_1) \end{aligned}
[ ⁣[F] ⁣](args,m)=run({F.args:=args},m,F.entry,F.entry)[\![F]\!](\mathit{args},m)=\mathit{run}(\{F.\mathit{args}:=\mathit{args}\},m,F.\mathit{entry},F.\mathit{entry})

Here BℓB_\ell is the basic block of FF labeled ℓ\ell, and run executes BℓB_\ell entered from the block ℓ′\ell'. When the terminator jumps to a block ℓ′′\ell'', run continues with Bℓ′′B_{\ell''} after a silent step; as in the iteration combinator of the ITrees library, this step guards the recursive call and makes run well-defined without changing behaviors. When the

\begin{aligned} \tau&::= i^{N} \mid\mathrm{float} \mid\mathrm{double} \mid\mathrm{ptr} \mid\mathrm{void} \mid[k \times\tau] \qquad N \in\{1,8,16,32,64\}\quad k \in\mathbb{N}\quad n \in\mathbb{Z}\cup\mathbb{R}\\ e &::= \%x \mid@g \mid n \mid\operatorname{binop}(op,e,e) \mid\operatorname{icmp}(c,e,e) \mid\operatorname{select}(e,e,e) \mid\operatorname{getelementptr}(\tau,e,\operatorname{list}\ e)\\ i &::= e \mid\operatorname{call}(\tau,e,\operatorname{list}\ e) \mid\operatorname{alloca}(\tau,e) \mid\operatorname{load}(\tau,e) \mid\operatorname{store}(e,e)\\ t &::= \operatorname{ret}(e) \mid\operatorname{br}(e,\ell,\ell) \mid\operatorname{br}(\ell) \mid\operatorname{unreachable}\\ \phi&::= \operatorname{phi}(\operatorname{list}\ (\ell,e))\\ B &::= \{\operatorname{label}:\ell;\ \operatorname{phis}:\operatorname{list}\ (\%x,\phi);\ \operatorname{code}:\operatorname{list}\ (\operatorname{option}\ \%x,i);\ \operatorname{term}:t\}\\ F &::= \{\operatorname{name}:@f;\ \operatorname{type}:\tau(\operatorname{list}\ \tau);\ \operatorname{args}:\operatorname{list}\ \%x;\ \operatorname{entry}:\ell;\ \operatorname{blocks}:\operatorname{list}\ B\}\\ P &::= \{\operatorname{globals}:\operatorname{list}\ (@g,e);\ \operatorname{functions}:\operatorname{list}\ F\} \end{aligned}
⟦e⟧:Env⁡×Mem⁡→itree⁡ E Val⁡\llbracket e\rrbracket:\operatorname{Env}\times\operatorname{Mem}\to\operatorname{itree}\ E\ \operatorname{Val}
⟦binop⁡(op,e1,e2)⟧(ρ,m)=v1←⟦e1⟧; v2←⟦e2⟧; match⁡ op(v1,v2) with⁡∣Success⁡ v⇒Ret⁡ v∣Failure⁡⇒trigger⁡ UB⁡⟦icmp⁡(c,e1,e2)⟧(ρ,m)=v1←⟦e1⟧; v2←⟦e2⟧;Ret⁡(c(v1,v2))\begin{aligned} \llbracket\operatorname{binop}(op,e_1,e_2)\rrbracket(\rho,m)&=v_1\leftarrow\llbracket e_1\rrbracket;\ v_2\leftarrow\llbracket e_2\rrbracket;\ \operatorname{match}\ op(v_1,v_2)\ \operatorname{with}\\ &\mid\operatorname{Success}\ v\Rightarrow\operatorname{Ret}\ v\\ &\mid\operatorname{Failure}\Rightarrow\operatorname{trigger}\ \operatorname{UB}\\ \llbracket\operatorname{icmp}(c,e_1,e_2)\rrbracket(\rho,m)&=v_1\leftarrow\llbracket e_1\rrbracket;\ v_2\leftarrow\llbracket e_2\rrbracket;\operatorname{Ret}(c(v_1,v_2)) \end{aligned}
⟦select⁡(e1,e2,e3)⟧(ρ,m)=b←⟦e1⟧; v2←⟦e2⟧; v3←⟦e3⟧;if⁡ b=poison⁡ then⁡Ret⁡poison⁡else⁡Ret⁡(if⁡ b then⁡ v2 else⁡ v3)⟦getelementptr⁡(τ,e,es)⟧(ρ,m)=p←⟦e⟧; vs←⟦es⟧; match⁡gep⁡(τ,p,vs,m) with⁡∣Success⁡ v⇒Ret⁡ v∣Failure⁡⇒trigger⁡ UB⁡\begin{aligned} \llbracket\operatorname{select}(e_1,e_2,e_3)\rrbracket(\rho,m)&=b\leftarrow\llbracket e_1\rrbracket;\ v_2\leftarrow\llbracket e_2\rrbracket;\ v_3\leftarrow\llbracket e_3\rrbracket;\\ &\operatorname{if}\ b=\operatorname{poison}\ \operatorname{then}\operatorname{Ret}\operatorname{poison}\\ &\operatorname{else}\operatorname{Ret}(\operatorname{if}\ b\ \operatorname{then}\ v_2\ \operatorname{else}\ v_3)\\ \llbracket\operatorname{getelementptr}(\tau,e,es)\rrbracket(\rho,m)&=p\leftarrow\llbracket e\rrbracket;\ vs\leftarrow\llbracket es\rrbracket;\ \operatorname{match}\operatorname{gep}(\tau,p,vs,m)\ \operatorname{with}\\ &\mid\operatorname{Success}\ v\Rightarrow\operatorname{Ret}\ v\\ &\mid\operatorname{Failure}\Rightarrow\operatorname{trigger}\ \operatorname{UB} \end{aligned}
⟦i⟧:Env⁡×Mem⁡→itree⁡ E (Val⁡×Mem⁡)\llbracket i\rrbracket:\operatorname{Env}\times\operatorname{Mem}\to\operatorname{itree}\ E\ (\operatorname{Val}\times\operatorname{Mem})
⟦alloca⁡(τ,e)⟧(ρ,m)=n←⟦e⟧; if⁡ n=poison⁡ then⁡trigger⁡ UB⁡else⁡match⁡alloca⁡(τ,n,m) with⁡∣Success⁡(m′,a)⇒Ret⁡(a,m′)∣Failure⁡⇒trigger⁡ UB⁡⟦load⁡(τ,e)⟧(ρ,m)=p←⟦e⟧; match⁡load⁡(τ,p,m) with⁡∣Success⁡ v⇒Ret⁡(v,m)∣Failure⁡⇒trigger⁡ UB⁡⟦e⟧(ρ,m)=v←⟦e⟧;Ret⁡(v,m)\begin{aligned} \llbracket\operatorname{alloca}(\tau,e)\rrbracket(\rho,m)&=n\leftarrow\llbracket e\rrbracket;\ \operatorname{if}\ n=\operatorname{poison}\ \operatorname{then}\operatorname{trigger}\ \operatorname{UB}\\ &\operatorname{else}\operatorname{match}\operatorname{alloca}(\tau,n,m)\ \operatorname{with}\\ &\mid\operatorname{Success}(m',a)\Rightarrow\operatorname{Ret}(a,m')\\ &\mid\operatorname{Failure}\Rightarrow\operatorname{trigger}\ \operatorname{UB}\\ \llbracket\operatorname{load}(\tau,e)\rrbracket(\rho,m)&=p\leftarrow\llbracket e\rrbracket;\ \operatorname{match}\operatorname{load}(\tau,p,m)\ \operatorname{with}\\ &\mid\operatorname{Success}\ v\Rightarrow\operatorname{Ret}(v,m)\\ &\mid\operatorname{Failure}\Rightarrow\operatorname{trigger}\ \operatorname{UB}\\ \llbracket e\rrbracket(\rho,m)&=v\leftarrow\llbracket e\rrbracket;\operatorname{Ret}(v,m) \end{aligned}
⟦store⁡(e1,e2)⟧(ρ,m)=w←⟦e1⟧; p←⟦e2⟧;if⁡ p=poison⁡ then⁡trigger⁡ UB⁡else⁡match⁡store⁡(p,w,m) with⁡∣Success⁡ m′⇒Ret⁡((),m′)∣Failure⁡⇒trigger⁡ UB⁡⟦call⁡(τ,e,es)⟧(ρ,m)=args⁡←⟦es⟧; p←⟦e⟧;if⁡ p=poison⁡ then⁡trigger⁡ UB⁡else⁡trigger⁡(Call⁡(fn⁡(p),(τ,args⁡,m)))\begin{aligned} \llbracket\operatorname{store}(e_1,e_2)\rrbracket(\rho,m)&=w\leftarrow\llbracket e_1\rrbracket;\ p\leftarrow\llbracket e_2\rrbracket;\\ &\operatorname{if}\ p=\operatorname{poison}\ \operatorname{then}\operatorname{trigger}\ \operatorname{UB}\\ &\operatorname{else}\operatorname{match}\operatorname{store}(p,w,m)\ \operatorname{with}\\ &\mid\operatorname{Success}\ m'\Rightarrow\operatorname{Ret}((),m')\\ &\mid\operatorname{Failure}\Rightarrow\operatorname{trigger}\ \operatorname{UB}\\ \llbracket\operatorname{call}(\tau,e,es)\rrbracket(\rho,m)&=\operatorname{args}\leftarrow\llbracket es\rrbracket;\ p\leftarrow\llbracket e\rrbracket;\\ &\operatorname{if}\ p=\operatorname{poison}\ \operatorname{then}\operatorname{trigger}\ \operatorname{UB}\\ &\operatorname{else}\operatorname{trigger}(\operatorname{Call}(\operatorname{fn}(p),(\tau,\operatorname{args},m))) \end{aligned}
⟦t⟧:Env⁡×Mem⁡→itree⁡ E (Label⁡+Val⁡)\llbracket t\rrbracket:\operatorname{Env}\times\operatorname{Mem}\to\operatorname{itree}\ E\ (\operatorname{Label}+\operatorname{Val})
⟦ret⁡(e)⟧(ρ,m)=v←⟦e⟧;Ret⁡(inr⁡ v)⟦unreachable⁡⟧(ρ,m)=trigger⁡ UB⁡⟦br⁡(e,ℓ1,ℓ2)⟧(ρ,m)=b←⟦e⟧; if⁡ b=poison⁡ then⁡trigger⁡ UB⁡else⁡Ret⁡(inl⁡(if⁡ b then⁡ℓ1 else⁡ℓ2))⟦br⁡(ℓ)⟧(ρ,m)=Ret⁡(inl⁡ ℓ)\begin{aligned} \llbracket\operatorname{ret}(e)\rrbracket(\rho,m)&=v\leftarrow\llbracket e\rrbracket;\operatorname{Ret}(\operatorname{inr}\ v)\\ \llbracket\operatorname{unreachable}\rrbracket(\rho,m)&=\operatorname{trigger}\ \operatorname{UB}\\ \llbracket\operatorname{br}(e,\ell_1,\ell_2)\rrbracket(\rho,m)&=b\leftarrow\llbracket e\rrbracket;\ \operatorname{if}\ b=\operatorname{poison}\ \operatorname{then}\operatorname{trigger}\ \operatorname{UB}\\ &\operatorname{else}\operatorname{Ret}(\operatorname{inl}(\operatorname{if}\ b\ \operatorname{then}\ell_1\ \operatorname{else}\ell_2))\\ \llbracket\operatorname{br}(\ell)\rrbracket(\rho,m)&=\operatorname{Ret}(\operatorname{inl}\ \ell) \end{aligned}

terminator returns a value vv, run ends with vv and the current memory. ⟦F⟧(args⁡,m)\llbracket F\rrbracket(\operatorname{args},m) assigns the arguments to F.args⁡F.\operatorname{args} and runs FF from the entry block with the memory mm.

Compilation Settings

We compile C programs with Clang 21.1.8 and Rust programs with rustc 1.93.1, both of which are based on LLVM 21, to LLVM IR for x86-64 Linux at the optimization level O1 (-O1 and -Copt-level=1). We use the GNU11 dialect of C (-std=gnu11) and the 2021 edition of Rust (--edition=2021). For both languages, we use the following settings.

  • Loop unrolling. We disable loop unrolling, since the two compilers may unroll a loop by different factors: -fno-unroll-loops for Clang, and for rustc, the LLVM options that set the unrolling thresholds and counts to zero and disable runtime unrolling, partial unrolling, peeling, and unroll-and-jam (-Cllvm-args=--unroll-threshold=0 and others).

  • Vectorization. Since our semantics does not support vector types, we disable loop and SLP vectorization (-fno-vectorize, -fno-slp-vectorize, -Cno-vectorize-loops, and -Cno-vectorize-slp), the vectorization of loop idioms (-disable-loop-idiom-vectorize-all), and vector combining (-disable-vector-combine), and we reject an LLVM IR that still contains vector types or instructions.

  • Inlining. Using the LLVM option -force-attribute, we add the noinline attribute to each library function with a specification and leave the other library functions to the optimizer. For Rust, we also disable inlining at the MIR level (-Zinline-mir=no), which would otherwise inline library functions before LLVM sees this attribute.

For C, we also disable floating-point contraction (-ffp-contract=off), which may fuse a multiplication and an addition into one operation, and keep calls to C library functions, such as isupper and printf, as calls to those functions (-D__NO_CTYPE and, if needed, -fno-builtin-f). For Rust, we make panics abort (-Cpanic=abort), so that the LLVM IR has no unwinding code.

References

  1. [1]Yubo Bai and Tapti Palit. 2025. RustAssure: Differential Symbolic Testing for LLM-Transpiled C-to-Rust Code. In 2025 40th IEEE/ACM International Conference on Automated Software Engineering (ASE). 534–546. doi:10.1109/ASE63991.2025.00051DOI
  2. [2]Clark Barrett, Yi Fang, Benjamin Goldberg, Ying Hu, Amir Pnueli, and Lenore Zuck. 2005. TVOC: A Translation Validator for Optimizing Compilers. In Proceedings of the 17th International Conference on Computer Aided Verification (Edinburgh, Scotland, UK) (CAV’05). Springer-Verlag, Berlin, Heidelberg, 291–295. doi:10.1007/11513988_29DOI
  3. [3]Sahil Bhatia, Jie Qiu, Niranjan Hasnabis, Sanjit Seshia, and Alvin Cheung. 2024. Verified Code Transpilation with LLMs. In Advances in Neural Information Processing Systems, A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang (Eds.), Vol. 37. Curran Associates, Inc., 41394–41424. doi:10.52202/079017-1310
  4. [4]Jay Bosamiya, Wen Shih Lim, and Bryan Parno. 2022. Provably-Safe Multilingual Software Sandboxing using WebAssembly. In 31st USENIX Security Symposium (USENIX Security 22). USENIX Association, Boston, MA, 1975–1992. https://www.usenix.org/conference/usenixsecurity22/presentation/bosamiya
  5. [5]Mario Bucev and Viktor Kunčák. 2022. Formally Verified Quite OK Image Format. In 2022 Formal Methods in Computer-Aided Design (FMCAD). 343–348. doi:10.34727/2022/isbn.978-3-85448-053-2_41DOI
  6. [6]Xuemeng Cai, Jiankun Liu, Xiping Huang, Yijun Yu, Haitao Wu, Chunmiao Li, Bo Wang, Imam Nur Bani Yusuf, and Lingxiao Jiang. 2025. RustMap: Towards Project-Scale C-to-Rust Migration via Program Analysis and LLM. In Engineering of Complex Computer Systems: 29th International Conference, ICECCS 2025, Hangzhou, China, July 2–4, 2025, Proceedings. Springer-Verlag, Berlin, Heidelberg, 283–302. doi:10.1007/978-3-032-00828-2_16DOI
  7. [7]Victor Chen, Ayden Coughlin, and Michael D. Bond. 2026. &in&ator: Correct, Precise C-to-Rust Interface Translation. Proc. ACM Program. Lang. 10, PLDI (June 2026). doi:10.1145/3808270DOI
  8. [8]Edmund Clarke, Daniel Kroening, and Flavio Lerda. 2004. A Tool for Checking ANSI-C Programs. In Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2004). Springer Berlin Heidelberg, Berlin, Heidelberg, 168–176. doi:10.1007/978-3-540-24730-2_15DOI
  9. [9]Mehmet Emre, Peter Boyland, Aesha Parekh, Ryan Schroeder, Kyle Dewey, and Ben Hardekopf. 2023. Aliasing Limits on Translating C to Safe Rust. Proc. ACM Program. Lang. 7, OOPSLA1 (apr 2023). doi:10.1145/3586046DOI
  10. [10]Mehmet Emre, Ryan Schroeder, Kyle Dewey, and Ben Hardekopf. 2021. Translating C to Safe Rust. Proc. ACM Program. Lang. 5, OOPSLA (oct 2021). doi:10.1145/3485498DOI
  11. [11]Emily First, Markus N. Rabe, Talia Ringer, and Yuriy Brun. 2023. Baldur: Whole-Proof Generation and Repair with Large Language Models. In Proceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (San Francisco, CA, USA) (ESEC/FSE 2023). Association for Computing Machinery, New York, NY, USA, 1229–1241. doi:10.1145/3611643.3616423arxiv.org/abs/2303.04910
  12. [12]Aymerich Roznerx and Jonathan Protzanko. 2026. Scylla: Translating an Applicative Subset of C to Safe Rust. Proc. ACM Program. Lang. 10, OOPSLA1 (April 2026). doi:10.1145/3798229
  13. [13]Lennard Gäher, Michael Sammler, Ralf Jung, Robbert Krebbbers, and Derek Dreyer. 2024. RefinedRust: A Type System for High-Assurance Verification of Rust Programs. Proc. ACM Program. Lang. 8, PLDI, Article 192 (June 2024), 25 pages. doi:10.1145/3656422DOI
  14. [14]Lennard Gäher, Michael Sammler, Simon Spies, Ralf Jung, Hoang-Hai Dang, Robbert Krebbbers, Jeehoon Kang, and Derek Dreyer. 2022. Simuliris: a separation logic framework for verifying concurrent program optimizations. Proc. ACM Program. Lang. 6, POPL, Article 28 (Jan. 2022), 31 pages. doi:10.1145/3498689DOI
  15. [15]Galois, Inc. 2024. C2Rust. https://github.com/immunant/c2rust.
  16. [16]Jaemin Hong, Hyunhee Kang, and Sukyoung Ryu. 2026. Replacing Output Parameters with Algebraic Data Types in C-to-Rust Translation. ACM Trans. Softw. Eng. Methodol. (Oct. 2026). doi:10.1145/3860636 Just Accepted.DOI
  17. [17]Jaemin Hong, Kangkuk Lee, Hanliang Zhang, Hyunhee Kang, Eunsu Kim, Justin Restivo, Thanos Tzpodalos, Ramla Ijaz, Sukyoung Ryu, and Zhong Shao. 2026. PROCTOR: An Extensible C-to-Rust Translation Framework With Static-Analysis-Driven Plug-Ins. IEEE Security & Privacy 24, 5 (2026), 56–67. doi:10.1109/MSEC.2026.3709880DOI
  18. [18]Jaemin Hong and Sukyoung Ryu. 2023. Contract: An Automatic C-to-Rust Lack API Translator for Concurrent Programs. In Proceedings of the 45th International Conference on Software Engineering (ICSE ’23). IEEE Press, Melbourne, Victoria, Australia, 716–728. doi:10.1109/ICSE48619.2023.00069DOI
  19. [19]Jaemin Hong and Sukyoung Ryu. 2024. Don’t Write, but Return: Replacing Output Parameters with Algebraic Data Types in C-to-Rust Translation. Proc. ACM Program. Lang. 8, PLDI (jun 2024). doi:10.1145/3656406DOI
  20. [20]Jaemin Hong and Sukyoung Ryu. 2024. To Tag, or Not to Tag: Translating C’s Unions to Rust’s Tagged Unions. In Proceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering (Sacramento, CA, USA) (ASE ’24). Association for Computing Machinery, New York, NY, USA, 40–52. doi:10.1145/3691620.3694985DOI
  21. [21]Jaemin Hong and Sukyoung Ryu. 2024. Type-migrating C-to-Rust translation using a large language model. Empirical Software Engineering 30, 1 (Oct. 2024). doi:10.1007/s10664-024-10573-2DOI
  22. [22]Jaemin Hong and Sukyoung Ryu. 2025. Forcrat: Automatic I/O API Translation from C to Rust via Origin and Capability Analysis. In 2025 40th IEEE/ACM International Conference on Automated Software Engineering (ASE). 1541–1552. doi:10.1109/ASE63991.2025.00130DOI
  23. [23]Chung-Kil Hur, Georg Neis, Derek Dreyer, and Viktor Vafeiadis. 2013. The Power of Parameterization in Conductive Proof. SIGPLAN Not. 48, 1 (Jan. 2013), 193–206. doi:10.1145/2480359.2429093DOI
  24. [24]Ralf Jung, Jacques-Henri Jourdan, Robbert Krebbers, and Derek Dreyer. 2017. RustBelt: securing the foundations of the Rust programming language. Proc. ACM Program. Lang. 2, POPL, Article 66 (Dec. 2017), 34 pages. doi:10.1145/3158154DOI
  25. [25]Ralf Jung, Robbert Krebbers, Jacques-Henri Jourdan, Alix Bı́zjak, Lars Birkedal, and Derek Dreyer. 2018. Iris: From the ground up: A modular foundation for higher-order concurrent separation logic. Journal of Functional Programming 28 (2018), e20. doi:10.1017/S0956796818000151DOI
  26. [26]Ralf Jung, David Swasey, Filip Sieczkowski, Kasper Svendsen, Aaron Turon, Lars Birkedal, and Derek Dreyer. 2015. Iris: Monoids and Invariants as an Orthogonal Basis for Concurrent Reasoning. SIGPLAN Not. 50, 1 (Jan. 2015), 637–650. doi:10.1145/2775051.2676980DOI
  27. [27]Jeehoon Kang, Yoonseung Kim, Youngju Song, June young Lee, Sanghoon Park, Mark Dongyeon Shin, Yonghyun Kim, Sungkeun Cho, Joonwon Choi, Chung-Kil Hur, and Kwangkeun Yi. 2018. Crellvm: verified credible compilation for LLVM. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation (Philadelphia, PA, USA) (PLDI 2018). Association for Computing Machinery, New York, NY, USA, 631–645. doi:10.1145/3192366.3192377DOI
  28. [28]Eunsu Kim, Sukyoung Ryu, and Jaemin Hong. 2026. Securing Union-Based Type Punning in C-to-Rust Translation. IEEE Security & Privacy 24, 05 (Sept. 2026), 68–78. doi:10.1109/MSEC.2026.3710213DOI
  29. [29]Yonghee Kim, Taeyoung Yoon, Sanghyun Yi, Jaehyung Lee, Soonwon Moon, Yeji Han, Seonho Lee, Taeyoung Rhee, Yujin Im, Donghyun Nam, Jeung Kim, and Chung-Kil Hur. 2026. CRIS: The Power of Imagination in Hybrid Verification. Proc. ACM Program. Lang. 10, PLDI, Article 239 (June 2026), 24 pages. doi:10.1145/3808317DOI
  30. [30]Robbert Krebbers, Amin Timany, and Lars Birkedal. 2017. Interactive Proofs in Higher-Order Concurrent Separation Logic. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2017). Association for Computing Machinery, New York, NY, USA, 205–217. doi:10.1145/3009837.3009855DOI
  31. [31]Seungwan Kwon, Jaeseong Kwon, Wooseok Kang, Juneyoung Lee, and Kihong Heo. 2024. Translation Validation for JIT Compiler in the V8 JavaScript Engine. In Proceedings of the IEEE/ACM 46th International Conference on Software Engineering (Lisbon, Portugal) (ICSE ’24). Association for Computing Machinery, New York, NY, USA. doi:10.1145/3597533.3639189DOI
  32. [32]Andreaa Lautąches, Travis Hance, Chanhee Cho, Matthias Brun, Isitha Subasinghe, Yi Zhou, Jon Howell, Bryan Parno, and Chris Hawblitzel. 2023. Verus: Verifying Rust Programs using Linear Ghost Types. Proc. ACM Program. Lang. 7, OOPSLA1, Article 85 (April 2023), 30 pages. doi:10.1145/3586037
  33. [33]Juneyoung Lee, Yoonseung Kim, Youngju Song, Chung-Kil Hur, Sanjoy Das, David Majnemer, John Regehr, and Nuno P. Lopes. 2017. Taming Undefined Behavior in LLVM. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’17). Association for Computing Machinery, New York, NY, USA, 633–647. doi:10.1145/3062341.3062343DOI
  34. [34]Xavier Leroy. 2009. Formal Verification of a Realistic Compiler. Commun. ACM 52, 7 (2009), 107–115. doi:10.1145/1538788.1538814DOI
  35. [35]Pedro Lobo, John McIver, George Mitenkov, Juneyoung Lee, Khirsthan Sundararajah, and Nuno P. Lopes. 2026. Towards Removing Unifying Values from LLVM IR. Proc. ACM Program. Lang. 10, PLDI, Article 172 (June 2026), 24 pages. doi:10.1145/3808250DOI
  36. [36]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 (Virtual, Canada) (PLDI 2021). Association for Computing Machinery, New York, NY, USA, 65–79. doi:10.1145/3453483.3454030DOI
  37. [37]Keane Lucas, Aengus Lynch, Luna Tong, Luke Champine, Zygi Straznickas, Dino Distefano, Harshikaa Agrawal, Evyatar Ben Asher, Ava Howell, Sami Jawhar, Chris Rohlf, Nickolai Zeldovich, Nicholas Carlini, Rajashree Agrawal, and Jason Gross. 2026. LLMs are making formal software verification feasible at a much larger scale. Retrieved November 10, 2026 from https://www.anthropic.com/research/formal-verification
  38. [38]Kayvan Memarian, Justus Matthiesen, James Lingard, Kyndylan Nienhuis, David Chisnall, Robert N. M. Watson, and Peter Sewell. 2016. Into the Depths of C: Elaborating the De Facto Standards. In Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’16). Association for Computing Machinery, New York, NY, USA, 1–15. doi:10.1145/2908080.2908081DOI
  39. [39]George C. Necula. 2000. Traditional validation for an optimizing compiler. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (Vancouver, British Columbia, Canada) (PLDI ’00). Association for Computing Machinery, New York, NY, USA, 83–94. doi:10.1145/349299.349314
  40. [40]Peter W. O’Hearn, John C. Reynolds, and Hongseok Yang. 2001. Local Reasoning about Programs that Alter Data Structures. In Proceedings of the 15th International Workshop on Computer Science Logic (CSL ’01). Springer-Verlag, Berlin, Heidelberg, 1–19. doi:10.1007/3-540-44802-0_1DOI
  41. [41]A. Pnueli, M. Siegel, and E. Singerman. 1998. Translation validation. In Tools and Algorithms for the Construction and Analysis of Systems, Bernhard Steffen (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 151–166. doi:10.1007/BFb0054170DOI
  42. [42]Thomas Arthur Leck Sewell, Magnus O. Myreen, and Gerwin Klein. 2013. Translation validation for a verified OS kernel. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation (Seattle, Washington, USA) (PLDI ’13). Association for Computing Machinery, New York, NY, USA, 471–482. doi:10.1145/2491956.2462183DOI
  43. [43]Rahul Sharma, Eric Schkufza, Berkeley Churchill, and Alex Aiken. 2013. Data-driven equivalence checking. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages & Applications (Indianapolis, Indiana, USA) (OOPSLA ’13). Association for Computing Machinery, New York, NY, USA, 391–406. doi:10.1145/2509136.2509509DOI
  44. [44]Monokai Shiraishi, Yinzhi Cao, and Takahiro Shinagawa. 2026. SmartC2Rust: Iterative, Feedback-Driven C-to-Rust Translation via Large Language Models for Safety and Equivalence. In Proceedings of the 2026 IEEE/ACM 48th International Conference on Software Engineering (Rio de Janeiro, Brazil) (ICSE ’26). Association for Computing Machinery, New York, NY, USA, 980–991. doi:10.1145/3744916.3773259
  45. [45]Youngju Song, Minki Cho, Dongjae Lee, Chung-Kil Hur, Michael Sammler, and Derek Dreyer. 2023. Conditional Contextual Refinement. Proc. ACM Program. Lang. 7, POPL, Article 39 (Jan. 2023), 31 pages. doi:10.1145/3571232DOI
  46. [46]Marcz Szafraniec, Baptiste Roziere, Hugh James Leather, Patrick Labatut, Francois Chambon, and Gabriel Synnaeve. 2023. Code Translation with Compiler Representations. In International Conference on Learning Representations. https://openreview.net/forum?id=XomEU3enSeQarxiv.org/abs/2207.03578
  47. [47]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 (San Francisco, California, USA) (POPL ’08). Association for Computing Machinery, New York, NY, USA, 17–27. doi:10.1145/1328438.1328444DOI
  48. [48]Jean-Baptiste Tristan and Xavier Leroy. 2009. Verified validation of lazy code motion. In Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation (Dublin, Ireland) (PLDI ’09). Association for Computing Machinery, New York, NY, USA, 316–326. doi:10.1145/1542476.1542512DOI
  49. [49]Alexa VanHattum, Daniel Schwartz-Narbonne, Nathan Chong, and Adrian Sampson. 2022. Verifying Dynamic Trait Objects in Rust. In Proceedings of the 44th International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP ’22). Association for Computing Machinery, New York, NY, USA, 321–330. doi:10.1145/3510457.3513031DOI
  50. [50]Xiafa Wu and Brian Demsky. 2025. GenC2Rust: Towards Generating Generic Rust Code from C. In 2025 IEEE/ACM 47th International Conference on Software Engineering (ICSE). IEEE Computer Society, Los Alamitos, CA, USA, 90–102. doi:10.1109/ICSE55347.2025.00127
  51. [51]Li-Yao Xia, Yannick Zakowski, Paul He, Chung-Kil Hur, Gregory Malecha, Benjamin C. Pierce, and Steve Zdancewic. 2019. Interaction trees: representing recursive and impure programs in Coq. Proc. ACM Program. Lang. 4, POPL, Article 51 (Dec. 2019), 32 pages. doi:10.1145/3371119
  52. [52]Qingxiao Xu and Jeff Huang. 2025. Optimizing Type Migration for LLM-Based C-to-Rust Translation: A Data Flow Graph Approach. In Proceedings of the 14th ACM SIGPLAN International Workshop on the State Of the Art in Program Analysis (SooP, Republic of Korea) (SOAP ’25). Association for Computing Machinery, New York, NY, USA, 8–14. doi:10.1145/3735544.3735582DOI
  53. [53]Aidan Z.H. Yang, Yoshiki Takashima, Brandon Paulsen, Josiah Dodds, and Daniel Kroening. 2025. VERT: Polyglot Verified Equivalent Rust Transpilation with Large Language Models. In 2025 40th IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE Press, 1453–1463. doi:10.1109/ASE63991.2025.00123DOI
  54. [54]Chenyu an Yang, Xuheng Li, Md Rakib Hossain Misu, Jianan Yao, Weidong Cui, Yeyun Gong, Chris Hawblitzel, Shuyendu Lahiri, Jacob R. Lorch, Shuai Lu, Fan Yang, Ziqiao Zhou, and Shan Lu. 2025. AutoVerus: Automated Proof Generation for Rust Code. Proc. ACM Program. Lang. 9, OOPSLA2, Article 396 (Oct. 2025), 29 pages. doi:10.1145/3763174DOI
  55. [55]Hongseok Yang. 2007. Relational separation logic. Theor. Comput. Sci. 375, 1-3 (2007), 308–334. doi:10.1016/j.tcs.2006.12.036DOI
  56. [56]Irene Yoon, Yannick Zakowski, and Steve Zdancewic. 2022. Formal reasoning about layered monadic interpreters. Proc. ACM Program. Lang. 6, ICFP, Article 99 (Aug. 2022), 29 pages. doi:10.1145/3547630DOI
  57. [57]Zhiqiang Yuan, Wenjun Mao, Zhuo Chen, Xinyue Shang, Chong Wang, Yiling Lou, and Xin Peng. 2026. Project-Level C-to-Rust Translation via Pointer Knowledge Graphs. Proc. ACM Softw. Eng. 3, FSE (June 2026). doi:10.1145/3808169DOI
  58. [58]Yannick Zakowski, Calvin Beck, Irene Yoon, Ilia Zaichuk, Vadim Zaliva, and Steve Zdancewic. 2021. Modular, compositional, and executable formal semantics for LLVM IR. Proc. ACM Program. Lang. 5, ICFP, Article 67 (Aug. 2021), 30 pages. doi:10.1145/3473572DOI
  59. [59]Yannick Zakowski, Paul H. Chung-Kil Hur, and Steve Zdancewic. 2020. An Equational Theory for Weak Bisimulation via Generalized Parameterized Coinduction. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020). Association for Computing Machinery, New York, NY, USA, 71–84. doi:10.1145/3372885.3373813DOI
  60. [60]Hanliang Zhang, Christina David, Yijun Yu, and Meng Wang. 2023. Ownership Guided C to Rust Translation. In Computer Aided Verification: 35th International Conference, CAV 2023, Paris, France, July 17–22, 2023, Proceedings, Part III. Springer-Verlag, Berlin, Heidelberg, 459–482. doi:10.1007/978-3-031-37709-9_22DOI
  61. [61]Ruxin Zhang, Shanxin Zhang, and Linbo Xie. 2025. A systematic exploration of C-to-rust code translation based on large language models: prompt strategies and automated repair. Automated Software Engineering 33, 1 (Oct. 2025). doi:10.1007/s10515-025-00570-0DOI
  62. [62]Han Zhou, Yu Luo, Mengtao Zhang, and Dianxiang Xu. 2025. C2RustTV: An LLM-based Framework for C to Rust Translation and Validation. In 2025 IEEE 49th Annual Computers, Software, and Applications Conference (COMPSAC). 1254–1259. doi:10.1109/COMPSAC65507.2025.00158

Paper details

vlnc:W_f72hsjv5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents