open-standards/wai/wai-wasmq/tests/fuzz.rs

//! A sweep for what a review found by reading (extensions/quantum-wasmq.md §3, §4): input
//! that panics a reader, and a module two engines run differently. Valid modules, envelopes
//! and programs are changed a byte at a time, tens of thousands of times from fixed seeds:
//! every reader must refuse or accept without a panic, what the profile accepts must
//! prepare, and every engine must give each export of an accepted module the same result,
//! the same fuel and the same fault.

use wai_wasmq::engine::{Engine, Interpreter, Trap};
use wai_wasmq::interp::Metering;
use wai_wasmq::{meter, profile};

struct Rng(u64);
impl Rng {
    fn next(&mut self) -> u64 {
        self.0 = self.0.wrapping_add(0x9e37_79b9_7f4a_7c15);
        let mut z = self.0;
        z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
        z ^ (z >> 31)
    }
    fn below(&mut self, n: usize) -> usize {
        (self.next() % n.max(1) as u64) as usize
    }
}

/// `bytes` with one change: a bit flipped, a byte set, inserted or removed, a stretch
/// copied from elsewhere in it, or its end cut off.
fn change(bytes: &[u8], rng: &mut Rng) -> Vec<u8> {
    let mut b = bytes.to_vec();
    if b.is_empty() {
        return b;
    }
    let at = rng.below(b.len());
    match rng.below(12) {
        0..=4 => b[at] ^= 1 << rng.below(8),
        5 | 6 => b[at] = rng.next() as u8,
        7 => b.insert(at, rng.next() as u8),
        8 => {
            b.remove(at);
        }
        9 | 10 => {
            let from = rng.below(b.len());
            let n = rng.below(8) + 1;
            for k in 0..n {
                if at + k < b.len() && from + k < b.len() {
                    b[at + k] = b[from + k];
                }
            }
        }
        _ => b.truncate(at),
    }
    b
}

const CONTROL: &str = r#"(module (memory (export "memory") 1 4)
  (table 3 funcref) (elem (i32.const 0) $sq $neg $sq)
  (type $u (func (param i32) (result i32)))
  (global $g (mut i64) (i64.const 7))
  (data (i32.const 8) "\01\02\03\04\05\06\07\08")
  (func $sq (type $u) local.get 0 local.get 0 i32.mul)
  (func $neg (type $u) i32.const 0 local.get 0 i32.sub)
  (func (export "loop") (param i64) (result i64) (local i32 i32)
    local.get 0 i32.wrap_i64 i32.const 63 i32.and local.set 1
    block loop
      local.get 1 i32.eqz br_if 1
      local.get 2 local.get 1 local.get 1 i32.const 3 i32.rem_u call_indirect (type $u) i32.add local.set 2
      local.get 1 i32.const 1 i32.sub local.set 1
      br 0
    end end
    local.get 2 i64.extend_i32_u global.get $g i64.add)
  (func (export "table") (param i64) (result i64)
    block block block
      local.get 0 i32.wrap_i64 br_table 0 1 2
    end i64.const 10 return
    end i64.const 20 global.set $g i64.const 21 return
    end i64.const 30)
  (func $fib (param i32) (result i32)
    local.get 0 i32.const 2 i32.lt_u if (result i32) local.get 0 else
      local.get 0 i32.const 1 i32.sub call $fib local.get 0 i32.const 2 i32.sub call $fib i32.add end)
  (func (export "fib") (param i64) (result i64) local.get 0 i32.wrap_i64 i32.const 15 i32.and call $fib i64.extend_i32_u)
  (func (export "mem") (param i64 i32) (result i64)
    i32.const 16 i32.const 7 local.get 1 i32.const 255 i32.and memory.fill
    i32.const 4096 i32.const 8 local.get 1 i32.const 255 i32.and memory.copy
    local.get 0 i32.wrap_i64 i32.const 7 i32.and memory.grow drop
    memory.size i64.extend_i32_u
    local.get 1 i64.load8_u offset=4096 i64.add
    local.get 1 i32.const 3 i32.shl local.get 0 i64.store
    local.get 1 i64.load16_s i64.add)
  (func (export "multi") (param i64 i64) (result i64)
    local.get 0 local.get 1 block (param i64 i64) (result i64) i64.add end
    i64.const 3 loop (param i64 i64) (result i64) i64.mul end
    local.get 0 local.get 0 local.get 1 i64.lt_s select)
  (func (export "echo") (param i32 f32 i64) (result f32 i32 i64) local.get 1 local.get 0 local.get 2)
  (func (export "div") (param i64 i64 i32 i32) (result i64)
    local.get 0 local.get 1 i64.div_s local.get 0 local.get 1 i64.rem_u i64.xor
    local.get 2 local.get 3 i32.div_u local.get 2 local.get 3 i32.rem_s i32.rotl i64.extend_i32_s i64.add))"#;

const FLOATS: &str = r#"(module (memory 1 1)
  (func (export "mix") (param f64 f64 f32) (result i64)
    local.get 0 local.get 1 f64.div local.get 0 local.get 1 f64.min f64.sub f64.sqrt
    local.get 2 f64.promote_f32 f64.max f64.nearest i64.reinterpret_f64
    local.get 2 local.get 2 f32.mul f32.ceil local.get 0 f32.demote_f64 f32.copysign i32.reinterpret_f32 i64.extend_i32_u i64.xor)
  (func (export "trunc") (param f64 f32) (result i64)
    local.get 0 i64.trunc_f64_s local.get 1 i32.trunc_f32_u i64.extend_i32_u i64.add
    local.get 0 i32.trunc_sat_f64_s i64.extend_i32_s i64.add)
  (func (export "store") (param f64 i32) (result i64)
    local.get 1 i32.const 1023 i32.and local.get 0 f64.store
    local.get 1 i32.const 1023 i32.and f32.load f32.neg f32.floor i32.trunc_sat_f32_s i64.extend_i32_s
    local.get 0 f64.abs f64.trunc i64.trunc_sat_f64_u i64.add))"#;

fn outcome(e: &dyn Engine, name: &str, args: &[u64]) -> (Result<Vec<u64>, Trap>, i64) {
    let mut i = match e.instantiate() {
        Ok(i) => i,
        Err(why) => return (Err(Trap::Host(why)), 0),
    };
    i.set_fuel(50_000);
    i.set_stack(0);
    let r = i.call(name, args);
    (r, i.fuel())
}

/// Changes `seed` `rounds` times, each from the original or from the last accepted
/// change; how many changed modules the profile accepted, and how many calls every
/// engine agreed on.
fn sweep(seed: &[u8], rounds: usize, rng: &mut Rng) -> (usize, usize) {
    let (mut accepted, mut calls) = (0, 0);
    let mut base = seed.to_vec();
    for round in 0..rounds {
        if round % 16 == 0 {
            base = seed.to_vec();
        }
        let m = change(&base, rng);
        let checked = std::panic::catch_unwind(|| profile::check(&m));
        let Ok(checked) = checked else { panic!("profile::check panicked on {m:02x?}") };
        let Ok(facts) = checked else { continue };
        accepted += 1;
        // What the profile accepts, prepares; and every engine takes it.
        let prepared = match std::panic::catch_unwind(|| meter::prepare(&m)) {
            Ok(Ok(p)) => p,
            Ok(Err(e)) => panic!("the profile accepts a module that does not prepare ({e}): {m:02x?}"),
            Err(_) => panic!("meter::prepare panicked on {m:02x?}"),
        };
        if facts.memory.is_some_and(|(min, _)| min > 64) {
            continue; // a module of a large memory at once: nothing more to learn, and slow
        }
        let own = Interpreter::new(&m, Metering::Own).unwrap_or_else(|e| panic!("the interpreter refuses a module the profile accepts ({e}): {m:02x?}"));
        let via = Interpreter::new(&prepared, Metering::Module).unwrap_or_else(|e| panic!("the interpreter refuses a prepared module ({e}): {m:02x?}"));
        #[cfg(all(feature = "wasmtime", not(target_arch = "wasm32")))]
        let native = wai_wasmq::engine::Native::new(&prepared).unwrap_or_else(|e| panic!("the native engine refuses a prepared module ({e}): {m:02x?}"));
        for (name, (params, _)) in &facts.functions {
            if params.len() > 6 {
                continue;
            }
            let args: Vec<u64> = params
                .iter()
                .map(|_| match rng.below(4) {
                    0 => rng.below(40) as u64,
                    1 => rng.next(),
                    2 => 0x7ff8_0000_0000_0001 ^ (rng.next() & 0xffff),
                    _ => (rng.next() as u32 as u64) | (rng.next() << 40),
                })
                .collect();
            let a = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| outcome(&own, name, &args))).unwrap_or_else(|_| panic!("the interpreter panicked running {name}{args:x?} of {m:02x?}"));
            assert!(!matches!(a.0, Err(Trap::Host(_))), "the interpreter could not run {name}{args:x?}: {:?} in {m:02x?}", a.0);
            let b = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| outcome(&via, name, &args))).unwrap_or_else(|_| panic!("the interpreter panicked running the prepared {name}{args:x?} of {m:02x?}"));
            assert_eq!(a, b, "{name}{args:x?}: the interpreter on the module and on its prepared form differ, in {m:02x?}");
            #[cfg(all(feature = "wasmtime", not(target_arch = "wasm32")))]
            assert_eq!(a, outcome(&native, name, &args), "{name}{args:x?}: the interpreter and the native engine differ, in {m:02x?}");
            calls += 1;
        }
        // An accepted change is built on, so that changes meet.
        if rng.below(3) == 0 {
            base = m;
        }
    }
    (accepted, calls)
}

#[test]
fn a_changed_module_is_refused_or_runs_the_same_on_every_engine() {
    let mut rng = Rng(0x0077_6173_6d51);
    let (mut accepted, mut calls) = (0, 0);
    for (seed, rounds) in [(wat::parse_str(CONTROL).unwrap(), 14_000), (wat::parse_str(FLOATS).unwrap(), 8_000)] {
        // The seeds themselves are in the profile, and the engines agree on them.
        if let Err(e) = profile::check(&seed) {
            panic!("a seed is outside the profile: {e}");
        }
        let (a, c) = sweep(&seed, rounds, &mut rng);
        accepted += a;
        calls += c;
    }
    // The sweep reached what it is for: thousands of changed modules inside the profile,
    // and their exports run on every engine.
    assert!(accepted > 2_000 && calls > 8_000, "{accepted} changed modules accepted, {calls} calls compared");
}

#[test]
fn a_changed_reference_module_is_refused_or_runs_the_same_on_every_engine() {
    let mut rng = Rng(0x0072_6566);
    let mut accepted = 0;
    for file in ["qldpc_decoder.wasm", "atom_planner.wasm"] {
        let seed = std::fs::read(std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("../quantum-conformance/wasmq/modules").join(file)).unwrap();
        accepted += sweep(&seed, 300, &mut rng).0;
    }
    assert!(accepted > 20, "{accepted} changed modules accepted");
}

#[test]
fn a_changed_envelope_or_program_is_refused_without_a_panic() {
    let dir = std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("../quantum-conformance/wasmq/envelopes");
    let mut rng = Rng(0x0065_6e76);
    let (mut opened, mut refused) = (0, 0);
    for file in ["surface3-decode64.wai", "list-echo.wai", "fault-fuel.wai"] {
        let env = std::fs::read(dir.join(file)).unwrap();
        assert!(wai_wasmq::open(&env).is_ok());
        for _ in 0..4_000 {
            let e = change(&env, &mut rng);
            match std::panic::catch_unwind(|| wai_wasmq::open(&e)) {
                Ok(Ok(o)) => {
                    // One envelope for one bundle (§2.4): what opens is the envelope of the
                    // bundle it opens as, byte for byte. (A change to a name or a budget
                    // makes another bundle, with an envelope of its own.)
                    assert!(wai_wasmq::pack(&o.bundle).is_ok_and(|again| again == e), "bytes that open as a bundle are not that bundle's envelope");
                    opened += 1;
                }
                Ok(Err(_)) => refused += 1,
                Err(_) => panic!("open panicked on a change of {file}"),
            }
        }
    }
    assert!(refused > 11_000, "{refused} refused, {opened} opened");
    // The program, as the reader with callouts takes it.
    let program = std::fs::read(dir.join("surface3-decode64.qasm")).unwrap();
    let (mut read, mut not) = (0, 0);
    for _ in 0..6_000 {
        let p = change(&program, &mut rng);
        let Ok(text) = String::from_utf8(p) else { continue };
        match std::panic::catch_unwind(|| wai_wasmq::envelope::read(&text, &Default::default())) {
            Ok(Ok(_)) => read += 1,
            Ok(Err(_)) => not += 1,
            Err(_) => panic!("the reader panicked on {text:?}"),
        }
    }
    assert!(read > 100 && not > 1_000, "{read} programs read, {not} refused");
}

/// A random place in a job, changed: replaced by a value of some other kind, or removed.
fn change_json(v: &mut serde_json::Value, rng: &mut Rng) {
    use serde_json::{Value, json};
    let mut at = v;
    loop {
        let n = match &*at {
            Value::Object(o) => o.len(),
            Value::Array(a) => a.len(),
            _ => 0,
        };
        if n == 0 || rng.below(5) == 0 {
            *at = match rng.below(12) {
                0 => Value::Null,
                1 => json!(true),
                2 => json!(0),
                3 => json!(-1),
                4 => json!(1u64 << 53),
                5 => json!(u64::MAX),
                6 => json!(1.5),
                7 => json!(""),
                8 => json!("x"),
                9 => json!([]),
                10 => json!({}),
                _ => json!("0".repeat(64)),
            };
            return;
        }
        let k = rng.below(n);
        if rng.below(6) == 0
            && let Value::Object(o) = at
        {
            let name = o.keys().nth(k).unwrap().clone();
            o.remove(&name);
            return;
        }
        at = match at {
            Value::Object(o) => o.values_mut().nth(k).unwrap(),
            Value::Array(a) => &mut a[k],
            _ => unreachable!(),
        };
    }
}

fn sealed_again(job: &serde_json::Value) -> serde_json::Value {
    let mut result = job["result"].clone();
    if let Some(o) = result.as_object_mut() {
        o.remove("receipt");
    }
    let key = wai_quantum::ed25519_dalek::SigningKey::from_bytes(&[9; 32]);
    let receipt = wai_quantum::engine::receipt::seal(&key, &job["request"], &result);
    if result.is_object() {
        result["receipt"] = receipt;
    }
    let status = if result["status"] == "ok" { "done" } else { "fault" };
    serde_json::json!({ "status": status, "method": result["method"], "request": job["request"], "result": result })
}

#[test]
fn a_changed_job_does_not_hold_with_its_envelope_and_no_job_or_record_panics() {
    use std::panic::{AssertUnwindSafe, catch_unwind};
    use wai_wasmq::run::{EngineKind, replay, run, verify};
    let dir = std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("../quantum-conformance/wasmq/envelopes");
    let key = wai_quantum::ed25519_dalek::SigningKey::from_bytes(&[7; 32]);
    let k = EngineKind::Interpreter;
    let mut rng = Rng(0x6a6f_6272_6563);
    let (mut as_edited, mut sealed) = (0, 0);
    for file in ["list-echo.wai", "fault-fuel.wai", "fault-trap.wai", "reset-draws.wai"] {
        let o = wai_wasmq::open(&std::fs::read(dir.join(file)).unwrap()).unwrap();
        let (job, log) = run(&o, k, &key, true).unwrap();
        assert!(verify(&job, Some(&o), k).unwrap().ok(), "{file}: the positive control");
        let same = sealed_again(&job);
        assert!(verify(&same, Some(&o), k).unwrap().ok(), "{file}: sealed again unchanged, under another key");
        for _ in 0..500 {
            let mut e = job.clone();
            change_json(&mut e, &mut rng);
            if e == job {
                continue;
            }
            // As edited: no signature, no form and no run lets a change of what is sealed
            // through; a change of the host's unsealed words is noted, and decides nothing.
            let v = catch_unwind(AssertUnwindSafe(|| verify(&e, Some(&o), k))).unwrap_or_else(|_| panic!("verify panicked on {e}"));
            if e["request"] == job["request"] && e["result"] == job["result"] {
                let v = v.unwrap();
                assert!(v.ok() && !v.notes.is_empty(), "{file}: an unsealed change is judged by what is sealed, and noted: {e}");
            } else {
                assert!(!v.as_ref().is_ok_and(|v| v.ok()), "{file}: a changed job holds with its envelope: {e}");
            }
            as_edited += 1;
            let _ = catch_unwind(AssertUnwindSafe(|| verify(&e, None, k))).unwrap_or_else(|_| panic!("verify panicked on {e}"));
            // Sealed again, under any key, it holds only if nothing signed changed.
            let again = sealed_again(&e);
            if again != same {
                let v = catch_unwind(AssertUnwindSafe(|| verify(&again, Some(&o), k))).unwrap_or_else(|_| panic!("verify panicked on {again}"));
                assert!(!v.as_ref().is_ok_and(|v| v.ok()), "{file}: a changed result, sealed again, holds with its envelope: {again}");
                let _ = catch_unwind(AssertUnwindSafe(|| verify(&again, None, k))).unwrap_or_else(|_| panic!("verify panicked on {again}"));
                sealed += 1;
            }
        }
        // A record, changed: refused or replayed, never a panic.
        let log = log.unwrap();
        for _ in 0..500 {
            let mut l = log.clone();
            if l.is_empty() {
                break;
            }
            let at = rng.below(l.len());
            match rng.below(8) {
                0 => l[at].shot = rng.next(),
                1 => l[at].callout = "nobody".into(),
                2 => l[at].input = (0..rng.below(64)).map(|_| rng.next() as u8).collect(),
                3 => l[at].output = (0..rng.below(64)).map(|_| rng.next() as u8).collect(),
                4 => l[at].fuel = rng.next(),
                5 => {
                    l.remove(at);
                }
                6 => {
                    let c = l[at].clone();
                    l.insert(at, c);
                }
                _ => {
                    let other = rng.below(l.len());
                    l.swap(at, other);
                }
            }
            let _ = catch_unwind(AssertUnwindSafe(|| replay(&o, &l, k))).unwrap_or_else(|_| panic!("replay panicked on a changed record of {file}"));
        }
    }
    assert!(as_edited > 1_500 && sealed > 500, "{as_edited} changes as edited, {sealed} sealed again");
}