Choosing Rust Translations by Sortition of Test Inputs

Large language models can now propose several candidate Rust translations of a legacy C module. Rust is attractive here because its compiler forbids use-after-free bugs: reading memory after it has been released. Someone still has to decide which candidate to accept. Today that decision rests on very little. It is either a fixed test suite, or a single adversarial "discriminator" agent that hunts for inputs on which the Rust code behaves differently from the original C program. We propose to treat acceptance as a collective decision with voters. Each test input is a voter, and its vote is whether a candidate agrees with the C program on it. The accepting panel is a small random sample of inputs, and the sample must satisfy two properties borrowed from the theory of citizens' assemblies. First, its size depends only on the number of candidates and the tolerated error, never on how large the input space is. Second, a specific selection rule keeps rare behaviors from going unrepresented.

The second, less obvious claim comes from blockchain governance research. The evidence that decides acceptance is usually concentrated in one or two test generators. This mirrors the way voting power in decentralized organizations collapses onto a handful of delegates. We predict that this concentration, which we can measure, forecasts which translations ship with hidden defects. We propose to measure verification centralization with the same statistic used for decentralized organizations. We will then test whether a population-independent, coverage-preserving panel drawn from several independent generators lets fewer defects through than the current practice, at equal cost.

Core Claim

Fix $m$ candidate translations of a C program. Let $\ell(x,j)\in\{0,1\}$ record whether candidate $j$ diverges from the C program on input $x$. Divergence means different output, a crash, or a sanitizer report. The true defect rate of candidate $j$ is the average of $\ell$ over the input distribution. Suppose we draw $k$ inputs uniformly and pick the candidate with the lowest observed defect rate. Hoeffding's inequality plus a union bound over candidates then shows that the chosen candidate is within $\epsilon$ of the best with probability at least $1-\delta$ once

$$k \;=\; O\!\left(\epsilon^{-2}\ln(m/\delta)\right),$$

This has the same form as the population-independent panel size in Can a Few Decide for Many? The Metric Distortion of Sortition. That paper shows a uniformly drawn panel of $O(\epsilon^{-2}\ln(m/\epsilon))$ people approximates a whole population's choice among $m$ alternatives. This part is standard, and we claim nothing new for it.

The new claim is that the same paper's warning also carries over. It observes that uniform panels are good on average but occasionally unrepresentative after the draw, which it calls "nightmare scenarios." For memory safety that failure is the typical one: an ownership mistake often lives on one rare error-handling path. The paper's Fair Greedy Capture rule gives every agent an equal chance of selection while guaranteeing that tight clusters of agents are represented. We adapt it to inputs placed in a metric space of execution traces. Because inclusion probabilities stay equal, the certificate above still holds. Because the rule captures clusters, any behavioral cluster of mass roughly $1/k$ gets at least one representative input. We further claim that pooling inputs from several independent generators, and reporting how concentrated the deciding evidence is, predicts and reduces escaped defects.

Where This Sits

The first body of work supplies the problem. The translation pipelines produce candidates and verify them narrowly. Ownership guided C to Rust translation (Crown) infers pointer ownership statically, removing a median 37.3% of raw pointer declarations. It also shows that literal transpilation keeps the original use-after-free bugs intact. LLM-Driven Multi-step Translation from C to Rust using Static Analysis (SACTOR) goes through an unidiomatic intermediate stage that may still contain unsafe code. CRUST-Bench finds single-shot pass rates of 19–22% on multi-file repositories, rising to 48% for o3 after three rounds of test repair. Adversarial Agent Collaboration for C to Rust Translation (ACToR) pairs the translator with one discriminator agent that fuzzes differences against the C binary. It reports over 90% test pass rate on 57 BSD utilities and up to 25.1% improvement over non-adversarial baselines.

All of these pass or fail a candidate on evidence from one source, and none states how much testing suffices. We keep their candidate generation and replace the acceptance step.

C2RUST-BENCH is the nearest two-direction precedent. It samples 2,905 representative functions out of 15,503 by binning complexity metrics. That is sampling for evaluating models, with no guarantee attached. We sample inputs for deciding about a single program, with a stated $(\epsilon,\delta)$ certificate.

The second body of work supplies the lens and constrains the design. The Hidden Shortcomings of (D)AOs introduces the Nakamoto coefficient as a measure of concentration. The coefficient is the smallest number of participants who together hold a majority of voting power. Delegates' Nakamoto coefficients in that study were as low as 1 or 2. Liquid Democracy: An Algorithmic Perspective proves that routing votes through a few delegates correlates errors, so a single delegate's mistake becomes a failure of the whole decision.

We carry both over directly. A test generator plays the role of a delegate, and a discriminator's blind spot becomes the whole pipeline's blind spot. Merit-Based Sortition in Decentralized Systems points the opposite way. It shows that weighting selection toward past performers improves quality, which here would mean favoring the generator that found the most bugs so far. We treat that as a competing design to test, not as a result to dismiss. Fair, Manipulation-Robust, and Transparent Sortition supplies the idea of capping maximum selection probability. Here a cap stops any one generator from dominating the panel.

Research Program

The pool of inputs for each C program is the union of inputs from several independent generators:

  • uniform random inputs under the program's input grammar;
  • a coverage-guided fuzzer;
  • an LLM discriminator in the style of ACToR;
  • tests mined from the existing suite.

For every input we record an execution trace of the C program. The trace covers the branch profile, the allocation and free sequence, and the output. We embed traces in a metric space, with edit distance on basic-block sequences as the default and a learned embedding as a variant. For every input and every candidate we compute the divergence indicator $\ell$. Divergence includes AddressSanitizer reports on the C side and undefined-behavior reports from Rust's interpreter for unsafe code on the Rust side. This matters because intermediate and partially lifted translations can still contain use-after-free bugs.

The acceptance procedure draws a panel of size $k$ with Fair Greedy Capture over the trace metric. It enforces equal inclusion probability across inputs and a per-generator cap on inclusion probability. It accepts the candidate with the fewest observed divergences and reports the certificate $(\epsilon,\delta)$. It also reports a verification Nakamoto coefficient: the smallest number of generators whose inputs account for a majority of the decisive divergences, meaning those that separate the accepted candidate from the rejected ones.

The analytical work has two parts. The first is to prove that capture with capped inclusion probabilities keeps the uniform-sampling certificate. The second is to derive a coverage bound. We expect the bound to say that any cluster of trace-metric radius $r$ and mass above $c/k$ gets a representative, with $c$ a constant to be determined, by analogy with how Fair Greedy Capture bounds ex-post distortion.

Baselines

The naive reference point is acceptance by the repository's provided tests alone. This is CRUST-Bench's own protocol, under which o3 reaches a 48% pass rate after three repair rounds (CRUST-Bench). We use the same candidate pool, so what differs is only which accepted candidates later turn out to be defective.

The strongest existing competitor is the ACToR discriminator. It is the only published acceptance procedure that searches for divergence against the C oracle, and it reports over 90% test pass rate on BSDCoreUtils (Adversarial Agent Collaboration for C to Rust Translation). We run it with the same number of test executions per decision as our panel and the same candidates. Its prompts are tuned with the same budget we use to tune the trace embedding. No reported result was found on Lacuna for escaped-defect rates under any of these procedures, so every number for our target metric will be new. Beating ACToR means a statistically significant lower escape rate at equal executions, or an equal escape rate with at least 2× fewer executions.

The remaining baselines are the obvious simpler procedures at the same execution budget:

  • a coverage-guided fuzzer alone;
  • uniform random panels drawn from the pooled inputs;
  • proportional stratified sampling over k-means clusters of the same trace embedding.

Stratified sampling is the most dangerous of these, discussed below. Two ablations isolate our ingredients. Capture over the metric without generator pooling isolates the effect of coverage. Pooling with a per-generator cap but uniform draws isolates the effect of decentralizing the evidence. A merit-weighted variant, which favors generators by an exponential moving average of past bug yield as in Merit-Based Sortition in Decentralized Systems, tests whether concentrating on the best generator is better after all.

Why not just…?

Why not just run many uniform random tests and attach a confidence interval? That delivers the certificate, and our uniform-panel baseline is exactly this. The limitation is that the certificate holds on average over the input distribution. Ownership bugs sit on rare paths, which the sortition paper's nightmare-scenario analysis (Can a Few Decide for Many?) predicts uniform draws will sometimes miss entirely. If uniform panels escape no more seeded ownership defects than capture panels at equal $k$, our coverage claim fails, and we will report that.

Why not just use a coverage-guided fuzzer or the ACToR discriminator with a bigger budget? ACToR's own comparison shows that inputs optimized for code coverage missed edge cases its discriminator found. That supports adversarial search, but it also shows that each generator has characteristic blind spots. The Kahng et al. correlation result predicts that relying on one generator makes those blind spots decisive. The leave-one-generator-out experiment below tests this directly. If a single generator with doubled budget matches the pooled panel, the decentralization claim is wrong.

Why not just stratify by clusters of traces? Proportional stratified sampling also gives equal inclusion probability, and it also covers clusters. It is a real threat. The difference is that capture adapts to the geometry without fixing a number of strata, and it enforces representation of small, tight clusters that proportional allocation rounds to zero. If stratified sampling matches capture across the benchmarks, the contribution narrows to the certificate, the pooling cap, and the centralization measurement. We would present it that way.

Why not just improve the translator, e.g., more repair rounds? Better candidates are welcome, but CRUST-Bench shows repair plateaus at 48%. More importantly, better candidates do not tell you which one to trust. Our procedure sits on top of any generator, including Crown's statically lifted output.

Proposed Experiments

The experiments use three suites:

  • CRUST-Bench's 100 multi-file repositories, where the C code is the oracle and $m=8$ candidates come from o3, Claude, and Crown-then-LLM pipelines;
  • ACToR's 57 BSD utilities;
  • a 500-function sample from C2Rust-Bench, to measure how the method scales across complexity bins.

Ground truth for each accepted candidate comes from a held-out differential campaign with 100× the decision budget, run with sanitizers and drawn from generators and seeds disjoint from the panel. To measure use-after-free sensitivity directly, we also insert seeded ownership mutants into otherwise-correct candidates: early drops, double releases, and dangling references in unsafe blocks. The mutants follow the lifetime-bug patterns catalogued by Yuga and the memory-management category that makes up 40% of the vulnerabilities in A Closer Look at the Security Risks in the Rust Ecosystem.

The primary metrics are:

  • the escaped-defect rate of accepted candidates;
  • regret, meaning the true defect rate of the accepted candidate minus that of the best candidate;
  • test executions per decision.

Secondary metrics are certificate calibration and the verification Nakamoto coefficient.

Three checks decide the outcome.

The first is population independence. As we grow the input pool from $10^3$ to $10^6$ inputs per program, the $k$ needed for fixed regret should stay flat for capture and uniform panels. It should grow for procedures without a certificate.

The second is calibration. Across decisions, the fraction where true regret is at most $\epsilon$ should be at least $1-\delta$, both for uniform and for capped capture panels. Otherwise the equal-probability argument is broken.

The third is centralization. Across programs, a lower verification Nakamoto coefficient under the ACToR baseline should predict a higher held-out escape rate. Removing the dominant generator should flip more acceptance decisions under single-generator procedures than under the pooled panel.

The proposal succeeds if all three checks hold and capture beats both ACToR and stratified sampling on seeded-mutant escapes at equal budget. If the checks hold but stratified sampling ties capture, the certificate and the centralization diagnostic remain the contribution.