Source-linked AI summary
Syzygy: Dual Code-Test C to (safe) Rust Translation using LLMs and Dynamic Analysis
Manish Shetty, Naman Jain, Adwait Godbole, Sanjit A. Seshia, Koushik Sen
TL;DR
C-to-Rust translation is challenging because the languages differ in typing and memory-access rules, and manual migration can take multiple person-weeks. Syzygy combines LLMs with dynamic analysis to incrementally translate code and tests, and the authors report a test-validated translation of Zopfli, a 98-function library with over 3000 LoC.
Problem
C-to-Rust translation is challenging because safe Rust and C differ in typing and memory-access rules, while manual migration can take multiple person-weeks.
Source: §1 · p. 1Method
Syzygy incrementally translates code and tests, combining LLM generation with dynamic-analysis information and intermediate I/O examples mined from top-level tests.
Source: §1 · p. 2Results
Syzygy translated Zopfli, a 98-function library with over 3000 LoC, and validated it using one million randomly generated strings for compression.
Source: §1 · p. 3Takeaways & Limitations
The authors describe Syzygy as a scalable approach that naturally performs test-driven development while translating C programs to Rust.
Source: §8.3 · p. 23Evaluation covers Zopfli and UrlParser, which may cause prompt overfitting, and test-based equivalence can suffer from incomplete coverage.
Source: §8.2 · p. 23
Abstract
from arXiv · showhide
Despite extensive usage in high-performance, low-level systems programming applications, C is susceptible to vulnerabilities due to manual memory management and unsafe pointer operations. Rust, a modern systems programming language, offers a compelling alternative. Its unique ownership model and type system ensure memory safety without sacrificing performance. In this paper, we present Syzygy, an automated approach to translate C to safe Rust. Our technique uses a synergistic combination of LLM-driven code and test translation guided by dynamic-analysis-generated execution information. This paired translation runs incrementally in a loop over the program in dependency order of the code elements while maintaining per-step correctness. Our approach exposes novel insights on combining the strengths of LLMs and dynamic analysis in the context of scaling and combining code generation with testing. We apply our approach to successfully translate Zopfli, a high-performance compression library with ~3000 lines of code and 98 functions. We validate the translation by testing equivalence with the source C program on a set of inputs. To our knowledge, this is the largest automated and test-validated C to safe Rust code translation achieved so far.
1 INTRODUCTION
Syzygy combines LLM translation with dynamic analysis and translated tests to incrementally generate equivalent safe Rust. The authors demonstrate the approach on Zopfli, validating the translation with top-level equivalence tests.
1 INTRODUCTION
- C-to-Rust translation is difficult because C and safe Rust differ in typing and memory-access rules, while manual migration can take multiple person-weeks.Prior rule-based approaches often produce terse, uninterpretable code, while symbolic synthesis often does not scale to multi-function codebases.Source: §1 · p. 1
- Syzygy combines LLM generation with dynamic execution information and translates both code and tests to validate intermediate functions.Dynamic analysis mines intermediate I/O examples from top-level tests, which LLMs translate into Rust equivalence tests.Source: §1 · pp. 2–3
- The approach decomposes codebases into translation units, then incrementally generates and tests each unit, repairing failures before proceeding.This draws on test-driven development, using intermediate equivalence tests to maintain compatibility with previously generated Rust code.Source: §1 · pp. 2–3
- Over 95% line coverage and 83% branch coverage were achieved on source C tests for the Zopfli translation, the largest test-validated C-to-safe-Rust translation reported.The evaluation used one million randomly generated strings for compression on a library with 98 functions and over 3000 LoC.Source: §1 · p. 3
2 BACKGROUND
C’s dynamic memory management, pointer casts, and aliasing require non-local reasoning that complicates safe Rust translation. Rust’s ownership rules address memory-safety risks, while smart pointers support some shared and mutable structures with trade-offs.
2 BACKGROUND
- Dynamic allocation, pointer casts, and aliasing complicate translation because they require non-local reasoning about memory.Syzygy’s dynamic analyses target allocation sizes, types, and aliasing.Source: §2 · p. 3
- Rust’s ownership and borrowing rules prevent dangling references and restrict mutable and immutable access, supporting memory safety.The paper describes C as memory-unsafe because direct pointer manipulation leaves programmers responsible for avoiding runtime errors such as out-of-bounds accesses and use-after-free.Source: §2 · p. 4
- Rc<T> and RefCell<T> can represent shared, mutable structures such as doubly linked lists, but add runtime overhead and possible panics if misused.Rc<RefCell<T>> combines multiple ownership with interior mutability.Source: §2 · p. 4
3 PROBLEM FORMULATION
The task is to synthesize safe Rust that preserves a C program’s functional behavior, with equivalence judged on test inputs. The formulation forbids unsafe Rust and limits the current infrastructure to specified C-program cases.
3 PROBLEM FORMULATION
- The synthesis goal is a safe Rust implementation that preserves the C program’s functional behavior.Source: §3 · p. 4
- Observational equivalence means the generated Rust program produces outputs equivalent to C on a set of test inputs.Source: §3 · p. 4
- The generated Rust program may contain no unsafe blocks or behaviors, even when the C tests exercise unsafe behavior; such cases may allow undefined behavior or runtime panics.Source: §3 · pp. 4–5
- The current testing and analysis infrastructure is limited to acyclic data structures, no multithreading, and no type punning.These are described as soft restrictions on code generation, but infrastructure is currently limited to those cases.Source: §3 · p. 4
4 APPROACH
Syzygy incrementally translates C code units into aligned Rust while combining LLM generation with dynamic execution information. It also translates and tests inputs from C executions to check equivalence as translation proceeds.
4 APPROACH
- Syzygy pairs incremental code translation with translated equivalence tests, using execution filtering to validate each unit against C and maintain compatibility with previously generated Rust.The translation units align with C in signatures and behavior, the call graph, structs, and type definitions.Source: §4 · p. 5, §4.1.1 · p. 6, §4.1.4 · p. 7
4.1.1 Incremental Aligned Translation.
- Starting from dependency leaves, the approach translates granular units such as functions, structs, typedefs, and macros, letting the LLM focus on individual functions.This decomposition is intended to improve translation accuracy.Source: §4.1.1 · pp. 5–6
4.1.2 Semantic Type Alignment & Dynamic Analysis.
- C pointers obscure object structure and usage, so safe Rust translation must recover information about types, mutability, nullability, and aliases that Rust signatures must express.The approach uses dynamic analysis to collect properties such as aliasing, nullability, and allocation sizes for LLM code and test generation.Source: §4.1.2 · p. 6
4.1.3 Sampling for Reliable Code Translation.
- The CodeGenerator samples multiple Rust translations and leaves execution correctness to EqTester, which tests candidates to filter valid generations.The approach relies on tests for reliability, while noting that test soundness depends on test reliability.Source: §4.1.3 · p. 6
4.1.4 Reliable Testing by I/O Translation.
- Because generated tests can violate type or input constraints, Syzygy translates C test inputs into Rust and uses value-based equivalence tests to check behavior and compatibility.Failed tests trigger multi-round repair; passing units are committed to the Rust codebase.Source: §4.1.4 · pp. 6–7
4.2 Dynamic Specification Mining
- For each C function, dynamic analysis gathers argument properties and input-output examples, which guide code generation and equivalence-test generation.The approach mines properties such as types, bounds, nullability, and aliasing.Source: §4.2 · p. 7
4.2.1 Mining Specifications from C Executions.
- Instrumented executions collect argument types, bounds, nullability, and aliasing; the mined properties help guide translation where static inference may be complex or infeasible.The runtime tracks variables and their properties, while LLVM instrumentation interacts with it during execution.Source: §4.2.1 · p. 7
4.2.2 C I/O Specification.
- Fuzzing the top-level entry point supplies valid internal-function arguments, which are serialized with outputs and side effects to form C I/O examples for Rust test generation and equivalence checking.Pointer arguments are dereferenced during serialization to capture their internal objects.Source: §4.2.2 · p. 9
4.3 Rust Code Generation
Syzygy slices the C program into dependency-ordered units and translates them incrementally. Dynamic properties guide candidate signatures, while sampled translations are screened for compilation and tested for correctness.
4.3.1 High-level strategy: slicing and greedy translation.
- Translating dependency-ordered units individually focuses generation, but struct-field choices can affect function signatures higher in the call graph.The approach currently requires manual struct definitions because incompatibilities can surface later and require backtracking.Source: §4.3.1 · pp. 9–10
4.3.2 Per-unit translation.
- Dynamic-analysis specifications for types, nullability, and aliasing constrain Rust signatures, while sampled candidates are selected first for compilation and execution correctness is deferred to EqTester.Nullability information can guide use of Option; aliasing may call for Rc<RefCell<RT>> or argument collapsing.Source: §4.3.2 · pp. 10–11, Figure 5 · p. 10
4.4 Rust Test Generation
Syzygy tests generated Rust functions by translating C inputs and expected outputs into Rust objects, then comparing C and Rust behavior. LLM-generated argument mappings are supported by dynamic-analysis information about sizes and aliasing.
4.4 Rust Test Generation
- Tests first translate C arguments into Rust arguments, then invoke both functions on equivalent inputs and compare their outputs.The generated mappings also handle expected outputs, not only inputs.Source: §4.4 · p. 11, §4.4.3 · pp. 12–13
4.4.1 C to Rust I/O Translation.
- LLM-generated translateArgs functions adapt C inputs and expected outputs to Rust function signatures, which can vary even for identical C pointer types.A C pointer may represent a singleton integer, an integer array, or a string, requiring different Rust argument types.Source: §4.4.1 · p. 11
4.4.2 Argument Construction LLM Tool.
- The Argument Construction API uses dynamic-analysis size and alias information to create Rust objects that preserve C allocation sizes and sharing.For example, aliased C struct pointers become references to one shared Rust struct object.Source: §4.4.2 · p. 12, Table 2 · p. 12
4.4.3 Equivalence Testing.
- Equivalence tests check whether translating C outputs matches executing Rust on translated inputs, using value-based output assertions.The LLM generates the test logic for each C/Rust function pair.Source: §4.4.3 · pp. 12–13
4.5 Multi-round & Rejection Sampling
Syzygy samples candidate translations and filters them through compilation and execution, then uses equivalence-test failures to guide repair. This process supports incremental translation while retaining previously generated Rust code as an invariant.
Rejection Sampling
- At each LLM pipeline module, multiple candidate generations are filtered by compilation or execution before proceeding to the next module.Candidates include Rust translations, argument translators, and equivalence tests.Source: §4.5 · p. 13
Error Feedback
- Failing equivalence tests provide diffs and assertion messages that the LLM uses to regenerate incorrect functions.For large outputs, a diff isolates the discrepancy for feedback.Source: §4.5 · p. 13
- Diff-based error feedback helped the LLM correct an iterator-position bug, and the repaired code passed the entire test suite.The tests deserialize iterators with index information, exposing an unnecessary update to the iterator position.Source: §4.5 · p. 13
5 IMPLEMENTATION
The implementation combines dependency-ordered translation with dynamic specifications, sampled Rust generation, argument mapping, and equivalence testing. Candidate code is filtered through compiler and execution checks, with iterative repair when needed.
5.1 Slicer
- The Slicer builds a dependency graph of code elements and traverses it in topological order, adding dynamic-analysis edges between function types and matching functions.Each translation unit is paired with its dependency slice.Source: §5.1 · p. 14
5.2 SpecMiner
- SpecMiner uses allocation tracking and runtime serialization to collect function inputs, outputs, return values, allocation bounds, and types.The collected specifications support inference of properties such as nullability and aliasing.Source: §5.2 · p. 14
5.3 CodeGenerator
- CodeGenerator samples Rust translations in parallel, uses Rust compilation with unsafe code forbidden to filter candidates, and repairs failures using compiler feedback.It retains a capped number of minimum compiling translations.Source: §5.3 · pp. 14–15
5.4 ArgTranslator
- ArgTranslator asks an LLM to generate a program mapping C arguments to Rust arguments and filters candidates by successful execution of that mapping.Bindgen supplies Rust signatures from C signatures, and FFI provides access to C functions and arguments.Source: §5.4 · p. 15
5.5 EqTester
- EqTester generates value-based tests to compare C and Rust functions, filtering candidates by compilation and equivalence-test success before iterative repair.The implementation uses Rust PartialEq for equality checks.Source: §5.5 · p. 15
6 EXPERIMENTS
Syzygy translated UrlParser and the Zopfli compression library using incremental code generation and testing. Zopfli’s repaired Rust translation passed a million-input test suite, although function-level pass rates were skewed and performance and long-function challenges remained.
6.1 UrlParser Case Study: Motivating Dual Translations
- For UrlParser, adding execution tests to compiler feedback enabled a correct translation of the top-level url_parse function after none of the initial candidates passed its tests.The individual-function tests were semi-manually constructed from repository tests.Source: §6.1 · p. 16
6.2 Zopfli Translation
- The Zopfli evaluation used 26 inputs with 88% line and 70% branch coverage before assembling the larger test suite.The program contains over 3,000 lines, 98 functions, and 10 structs; non-function units were manually checked, revealing a macro corner case that was manually repaired.Source: §6.2.1 · p. 16, §6.2 · p. 16
6.2.2 Results.
- After a local repair to zopfli_block_split_lz77, the Rust translation passed all 1,000,000 tests in the equivalence suite.The tests covered compression inputs and achieved 95% line coverage and 83% branch coverage; the repair sliced the splitpoints Vec.Source: §6.2.2 · pp. 16–17, Figure 8 · p. 17
- Figure 9 shows mean compilation and execution pass rates above 75%, but a long tail of functions had pass rates below 20%.Execution pass rates use compiling solutions as the denominator.Source: §6.2.2 · p. 17, Figure 9 · p. 18
6.2.3 Analysis.
- LLMs sometimes changed C logic inconsistently, and struggled to produce correct or compiling translations for long functions.For-loop translations can fail when C modifies the iterator inside the loop body, because Rust translations need to handle increments at continue statements.Source: §6.2.3 · pp. 17–18
- Even with optimized compilation, the translated Rust was up to 3.67x slower than C; Vec allocations and bounds checks were identified as contributors.The authors note that more careful timing is needed to understand differences between optimized versions.Source: §6.2.3 · p. 18, Table 3 · p. 18
- GPT-4O produced a correct Zopfli translation for under $800 but it was slower and crashed on some long inputs; without testing, compiling code crashed even on trivial input.The no-testing ablation generated a compiling version for under $100, while the authors conclude O1 produced more reliable, higher-quality translations.Source: §6.2.3 · p. 19
7 RELATED WORK
The related work frames C-to-Rust migration as relevant to safety-sensitive systems while noting disagreement about which code should move. Syzygy distinguishes itself through dynamic-analysis-guided, incremental code-and-test translation, alongside discussion of related LLM and agentic approaches.
7.1 C-to-Rust Interest and Applications
- C-to-Rust migration is considered relevant for cryptographic and network libraries and kernel code, but some argue low-level utilities may be better left in C because migration can introduce subtle bugs.The authors chose Zopfli partly because compression libraries are a DARPA TRACTOR milestone and a manual Rust translation exists.Source: §7.1 · p. 19
7.2 Automated C-to-Rust Translation
- Unlike [44], Syzygy combines LLM translation with intermediate internal-function equivalence tests, which the authors associate with accuracy gains on moderate-to-large codebases.The related work also notes that VERT [54] and [13] do not perform intermediate tests; VERT evaluates on code under 200 LoC, while [13] reports limited success on small benchmarks.Source: §7.2 · pp. 19–20
7.3 LLM-driven Code Translation
- Syzygy uses dynamic analysis to expose execution properties such as allocation, pointer access, aliasing, and nullability to LLMs, addressing C-specific translation challenges.The authors contrast this with Java-to-Python and Go-to-Rust, where memory-management patterns translate more directly [16] [58].Source: §7.3 · p. 20
7.4 Agentic Code Generation
- Syzygy is a non-agentic pipeline for long-horizon code translation; the authors describe CodePlan as repository-level editing with dependency graphs and inference-cost optimization as orthogonal work [11] [45] [52] [60].They suggest that ideas from traditional code generation may also transfer to translation [9] [10] [23] [57].Source: §7.4 · pp. 20–21
8 DISCUSSION
The discussion identifies limits in Syzygy’s safety constraints, greedy translation order, test coverage, and repair process, as well as performance and external-validity concerns. The authors report translating Zopfli and UrlParser and argue that broader evaluation and improvements to analysis and inference could extend the approach.
8.1 Challenges and Future Work
- Requiring no unsafe Rust may be overly strict for benign C behavior, while identifying unexploitable unsafe behavior requires attacker modeling and program analysis.The authors suggest a possible alternative: leave annotated functions in C and integrate them through FFI.Source: §8.1 · p. 21
- Greedy dependency-ordered translation reduces combinatorial search but can produce suboptimal choices because structs need global usage context and early type decisions can conflict with later uses.The authors currently translate structs manually and identify global consistency as future work.Source: §8.1 · pp. 21–22
- Randomly sampled test-based equivalence can miss translation bugs because test specifications may have incomplete coverage.The authors report generating over 1,000,000 tests for Zopfli to achieve high coverage and suggest better sampling or fuzzing heuristics.Source: §8.1 · p. 22, §8.2 · p. 23
- Intermediate equivalence checks may be unnecessarily strict and constrain simpler or more interpretable translations, but deciding which checks to relax requires downstream context.The dependency-ordered greedy approach offers limited flexibility for such relaxations.Source: §8.1 · p. 22
- In zopfli_append_data, preserving C’s separately stored array size and doubling behavior makes the Rust Vec translation non-idiomatic and can confuse the LLM about the vector’s length.Rust Vec would otherwise perform the allocation-doubling logic internally.Source: §8.1 · p. 22
- Repairs to a function that fails top-level validation can cascade to dependent functions, so the experiments used manual strategies for minimal edits.The authors propose more systematic LLM-guided repair as future work.Source: §8.1 · p. 22
8.2 Threats to validity; 8.3 Conclusion
- Type punning and rampant void∗ usage can make compile-time dynamic analyses imprecise or incomplete, while the evaluation to date covers Zopfli and UrlParser.The conclusion reports a successful translation of Zopfli, over 3,000 LoC, and identifies stronger analysis and LLM inference schedules as routes toward more complex programs.Source: §8.1 · p. 22, §8.2 · p. 23, §8.3 · p. 23
8.1 Challenges and Future Work
- The current argument-translation API balances ease of use against expressiveness, and the translated Zopfli program is up to 3.67× slower than C.The authors identify profiling and efficiency-aware translation as future directions.Source: §8.1 · p. 23
A PROMPTS
The appendix introduces prompts for different modules of the approach.
A PROMPTS
- The appendix presents prompts for different modules of Syzygy.The prompts are shown on the following page.Source: A PROMPTS · p. 27
B EXAMPLE
The appendix walks through translating GetCostModelMinCost and shows generated code, argument translation, and equivalence testing artifacts.
B EXAMPLE
- GetCostModelMinCost is difficult to interpret statically because it uses indirect calls through a costmodel function pointer and a void∗ context that may correspond to several cost functions.Figure 13 presents the source function.Source: B EXAMPLE · p. 27, Figure 13 · p. 31
- The candidate Rust translation is paired with a generated translateArgs function that maps the C function pointer’s GetCostFixed and GetCostStat variants to Rust closures.The argument translator is aligned with the candidate translation.Source: Figure 14 · p. 32, Figure 15 · p. 33
- The generated equivalence test compares the C function with the Rust candidate and uses assertions tolerant of floating-point precision.The test uses the previously generated translateArgs function.Source: Figure 16 · p. 34