javm_fuzz/
shrink.rs

1//! Delta-debugging minimizer: shrink a failing program to a minimal reproducer.
2//!
3//! Generic over a `fails` predicate (typically "the Spike oracle, interpreter,
4//! and recompiler don't all agree"), so this module stays portable — the engine
5//! plumbing lives in the caller (`live.rs`).
6
7use crate::Program;
8use crate::encode;
9use std::collections::BTreeMap;
10
11fn rebuild(body: &[u32], regs: &BTreeMap<u8, u64>) -> Program {
12    let mut code = body.to_vec();
13    code.extend(encode::signature_epilogue(crate::SIG_BASE));
14    Program {
15        code,
16        init_regs: regs.clone(),
17        init_mem: None,
18    }
19}
20
21/// Minimize `prog` while `fails` keeps returning `true`. The trailing signature
22/// epilogue (length `sig_len`) is treated as fixed and regenerated each trial;
23/// the body (everything before it) is shrunk by greedily removing instructions,
24/// then unneeded seed registers are dropped. `fails` re-runs the comparison and
25/// returns `true` iff the divergence still reproduces.
26pub fn shrink(prog: &Program, sig_len: usize, mut fails: impl FnMut(&Program) -> bool) -> Program {
27    let body_end = prog.code.len().saturating_sub(sig_len);
28    let mut body: Vec<u32> = prog.code[..body_end].to_vec();
29    let mut regs = prog.init_regs.clone();
30
31    // 1. Greedily drop body instructions (repeat to a fixpoint).
32    let mut changed = true;
33    while changed {
34        changed = false;
35        let mut i = 0;
36        while i < body.len() {
37            let mut trial = body.clone();
38            trial.remove(i);
39            if fails(&rebuild(&trial, &regs)) {
40                body = trial;
41                changed = true;
42            } else {
43                i += 1;
44            }
45        }
46    }
47
48    // 2. Drop seed registers that aren't needed to reproduce.
49    for slot in regs.keys().copied().collect::<Vec<_>>() {
50        let mut trial = regs.clone();
51        trial.remove(&slot);
52        if fails(&rebuild(&body, &trial)) {
53            regs = trial;
54        }
55    }
56
57    rebuild(&body, &regs)
58}
javm_fuzz/shrink.rs

javm_fuzz/
shrink.rs
