cb059d7a0b
A jeff register's size reached Vec::with_capacity before the qubit cap, so one of 2^32 - 1 qubits asked for 34 GB: under wasm32-wasip2 the test written first trapped in qureg_op. It is now refused (Q111) before anything is made. The audit of every allocation and loop sized by the input: - the wire reader bounds every pointer, segment and list in 64 bits (a segment count of u32::MAX overflowed a 32-bit usize), and counts each list element against the words it may visit; - the jeff reader counts every register slot, array element (an array copied by setIndex included), call frame and condition term against one budget, caps arrays, values per function, operations run and gates written, shares conditions between copies, and no longer truncates a 64-bit size, index, selector or shift to fit; - the QIR reader no longer copies a block's lines on each visit, bounds the nesting of branches, the instructions run over every path and the state each path copies, and dedups a condition's reads; - a condition is at most 1 024 terms and 32 deep once written, a run of one operator written flat; - a conversion's check is not run past 262 144 gates applied or 4e9 amplitudes, and says so; both readers take modules of up to 16 MiB. tests/formats_mutation.rs mutates every QIR and jeff file of the conformance set from a fixed seed (45 153 inputs: bits flipped, files cut short and spliced, every length, count, offset and 32-bit field inflated) and holds each to converting or a refusal with a code of the table, within 20 s and 1 GiB measured by a counting allocator. wai-quantum-formats.yml runs it natively and under wasm32-wasip2 (a release build with overflow checks), the count pinned. Co-Authored-By: Claude Opus 5.5 <[email protected]>
388 lines
17 KiB
Rust
388 lines
17 KiB
Rust
//! Hostile inputs for the readers of other formats: every QIR and jeff file
|
|
//! of the conformance set (`wai/quantum-conformance/formats/`), mutated by a
|
|
//! seeded generator, converted to OpenQASM with its check. Every input must
|
|
//! convert or be refused with a code of the reader's table, never panic or
|
|
//! abort, finish within [`MAX_SECONDS`], and allocate at most [`MAX_PEAK`]
|
|
//! bytes beyond what the test held before it.
|
|
//!
|
|
//! The mutations: bits flipped; a file cut short; the start of one file
|
|
//! spliced to the end of another; and every length, count and offset the
|
|
//! readers parse set to its largest and to values just past their bounds:
|
|
//! in a jeff module the segment table, each pointer's offset, struct sizes
|
|
//! and list counts, and each 16-, 32- and 64-bit field (register sizes,
|
|
//! loop bounds, array lengths, indices, angles); in a QIR module each number
|
|
//! (indices, counts, versions, angles), lines repeated and branches turned
|
|
//! back on themselves.
|
|
//!
|
|
//! The same cases run natively and under wasm32-wasip2, where an allocation
|
|
//! larger than the address space panics rather than failing lazily: the
|
|
//! seed and the count are fixed, so both builds see the same inputs. Under
|
|
//! `WAI_FORMATS_MUTATION_REPORT=1` it prints the slowest inputs.
|
|
|
|
#![cfg(feature = "quantum_engine")]
|
|
|
|
use serde_json::Value;
|
|
use std::alloc::{GlobalAlloc, Layout, System};
|
|
use std::sync::atomic::{AtomicUsize, Ordering};
|
|
use wai_quantum::engine::formats::{self, Format};
|
|
|
|
/// The allocator, counting what is live and the most it has been.
|
|
struct Counting;
|
|
|
|
static LIVE: AtomicUsize = AtomicUsize::new(0);
|
|
static PEAK: AtomicUsize = AtomicUsize::new(0);
|
|
|
|
unsafe impl GlobalAlloc for Counting {
|
|
unsafe fn alloc(&self, l: Layout) -> *mut u8 {
|
|
let p = unsafe { System.alloc(l) };
|
|
if !p.is_null() {
|
|
let now = LIVE.fetch_add(l.size(), Ordering::Relaxed) + l.size();
|
|
PEAK.fetch_max(now, Ordering::Relaxed);
|
|
}
|
|
p
|
|
}
|
|
unsafe fn dealloc(&self, p: *mut u8, l: Layout) {
|
|
unsafe { System.dealloc(p, l) };
|
|
LIVE.fetch_sub(l.size(), Ordering::Relaxed);
|
|
}
|
|
unsafe fn alloc_zeroed(&self, l: Layout) -> *mut u8 {
|
|
let p = unsafe { System.alloc_zeroed(l) };
|
|
if !p.is_null() {
|
|
let now = LIVE.fetch_add(l.size(), Ordering::Relaxed) + l.size();
|
|
PEAK.fetch_max(now, Ordering::Relaxed);
|
|
}
|
|
p
|
|
}
|
|
unsafe fn realloc(&self, p: *mut u8, l: Layout, size: usize) -> *mut u8 {
|
|
let q = unsafe { System.realloc(p, l, size) };
|
|
if !q.is_null() {
|
|
if size >= l.size() {
|
|
let now = LIVE.fetch_add(size - l.size(), Ordering::Relaxed) + (size - l.size());
|
|
PEAK.fetch_max(now, Ordering::Relaxed);
|
|
} else {
|
|
LIVE.fetch_sub(l.size() - size, Ordering::Relaxed);
|
|
}
|
|
}
|
|
q
|
|
}
|
|
}
|
|
|
|
#[global_allocator]
|
|
static ALLOCATOR: Counting = Counting;
|
|
|
|
const BUNDLE: &str = include_str!("../../quantum-conformance/formats/bundle.json");
|
|
|
|
/// The generator's seed.
|
|
const SEED: u64 = 0x5eed_1e55_f0f0_0018;
|
|
/// Mutated inputs made from each file.
|
|
const PER_FILE: usize = 24;
|
|
/// The jeff modules whose every 32-bit field is inflated in turn: those of
|
|
/// at most this many bytes.
|
|
const SWEEP_BYTES: usize = 12_288;
|
|
/// The longest one input may take, in seconds (a release build; the wasm32
|
|
/// leg of CI is a release build with overflow checks on).
|
|
const MAX_SECONDS: f64 = 20.0;
|
|
/// The most one input may allocate beyond what was live before it.
|
|
const MAX_PEAK: usize = 1 << 30;
|
|
|
|
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 {
|
|
if n == 0 { 0 } else { (self.next() % n as u64) as usize }
|
|
}
|
|
}
|
|
|
|
/// The values a length, count, size, index or bound is set to: the largest
|
|
/// it holds, and just past each bound the readers keep.
|
|
const BIG32: [u32; 9] = [u32::MAX, 0x7fff_ffff, 0x8000_0000, 1 << 16, (1 << 16) + 1, 1 << 20, (1 << 22) + 1, 1 << 24, 65_535];
|
|
const BIG64: [u64; 6] = [u64::MAX, i64::MAX as u64, 1 << 32, (1 << 32) + 1, 0x7ff0_0000_0000_0000, 0x7ff8_0000_0000_0001];
|
|
|
|
/// A jeff module's words: each 8-byte word after the segment table.
|
|
fn jeff_mutation(rng: &mut Rng, b: &[u8], other: &[u8]) -> (String, Vec<u8>) {
|
|
let mut v = b.to_vec();
|
|
let words = v.len() / 8;
|
|
match rng.below(9) {
|
|
0 => {
|
|
let flips = 1 + rng.below(8);
|
|
for _ in 0..flips {
|
|
let i = rng.below(v.len().max(1));
|
|
if let Some(x) = v.get_mut(i) {
|
|
*x ^= 1 << rng.below(8);
|
|
}
|
|
}
|
|
(format!("{flips} bits flipped"), v)
|
|
}
|
|
1 => {
|
|
let n = rng.below(v.len());
|
|
v.truncate(n);
|
|
(format!("cut to {n} bytes"), v)
|
|
}
|
|
2 => {
|
|
let (i, j) = (rng.below(v.len()), rng.below(other.len()));
|
|
let mut s = v[..i].to_vec();
|
|
s.extend_from_slice(&other[j..]);
|
|
(format!("the first {i} bytes and another file's from {j}"), s)
|
|
}
|
|
3 => {
|
|
// The segment table: the count, or a segment's size.
|
|
let i = 4 * rng.below(3);
|
|
let x = BIG32[rng.below(BIG32.len())];
|
|
if i + 4 <= v.len() {
|
|
v[i..i + 4].copy_from_slice(&x.to_le_bytes());
|
|
}
|
|
(format!("segment-table word {} set to {x}", i / 4), v)
|
|
}
|
|
4 | 5 => {
|
|
// A pointer: its offset, its struct's sizes, or its list's count.
|
|
let w = 1 + rng.below(words.saturating_sub(1).max(1));
|
|
let at = 8 * w;
|
|
if at + 8 > v.len() {
|
|
return ("nothing".into(), v);
|
|
}
|
|
let mut p = u64::from_le_bytes(v[at..at + 8].try_into().unwrap());
|
|
let what = match (p & 3, rng.below(3)) {
|
|
(0, 0) => {
|
|
p |= 0xffff_u64 << 32;
|
|
"a struct's data size at its largest"
|
|
}
|
|
(0, 1) => {
|
|
p |= 0xffff_u64 << 48;
|
|
"a struct's pointer count at its largest"
|
|
}
|
|
(1, 0) | (1, 1) => {
|
|
p = (p & 0x7_ffff_ffff) | (u64::from(BIG32[rng.below(BIG32.len())] >> 3) << 35);
|
|
"a list's count past its bounds"
|
|
}
|
|
_ => {
|
|
p = (p & !0xffff_fffc) | (u64::from(BIG32[rng.below(BIG32.len())]) & 0xffff_fffc);
|
|
"a pointer's offset past its bounds"
|
|
}
|
|
};
|
|
v[at..at + 8].copy_from_slice(&p.to_le_bytes());
|
|
(format!("word {w}: {what}"), v)
|
|
}
|
|
6 | 7 => {
|
|
// A 32-bit field: a register's size, a loop's bound, an index, a length.
|
|
let i = 8 + 4 * rng.below(v.len().saturating_sub(8) / 4);
|
|
let x = BIG32[rng.below(BIG32.len())];
|
|
if i + 4 <= v.len() {
|
|
v[i..i + 4].copy_from_slice(&x.to_le_bytes());
|
|
}
|
|
(format!("the 32 bits at {i} set to {x}"), v)
|
|
}
|
|
_ => {
|
|
// A 64-bit field: a 64-bit constant, or an angle.
|
|
let i = 8 + 8 * rng.below(words.saturating_sub(1));
|
|
let x = BIG64[rng.below(BIG64.len())];
|
|
if i + 8 <= v.len() {
|
|
v[i..i + 8].copy_from_slice(&x.to_le_bytes());
|
|
}
|
|
(format!("the 64 bits at {i} set to {x:#x}"), v)
|
|
}
|
|
}
|
|
}
|
|
|
|
const QIR_NUMBERS: [&str; 10] = ["4294967295", "18446744073709551615", "65536", "65537", "99999999999999999999999", "-1", "1e308", "nan", "0x7FF8000000000001", "2147483648"];
|
|
|
|
/// A QIR module's text: its numbers, its lines and its branches.
|
|
fn qir_mutation(rng: &mut Rng, t: &str, other: &str) -> (String, Vec<u8>) {
|
|
let lines: Vec<&str> = t.lines().collect();
|
|
match rng.below(7) {
|
|
0 | 1 => {
|
|
// A number: an index, a count, a version, an angle.
|
|
let spans: Vec<(usize, usize)> = {
|
|
let b = t.as_bytes();
|
|
let mut out = Vec::new();
|
|
let mut i = 0;
|
|
while i < b.len() {
|
|
if b[i].is_ascii_digit() {
|
|
let s = i;
|
|
while i < b.len() && (b[i].is_ascii_alphanumeric() || b[i] == b'.') {
|
|
i += 1;
|
|
}
|
|
out.push((s, i));
|
|
} else {
|
|
i += 1;
|
|
}
|
|
}
|
|
out
|
|
};
|
|
if spans.is_empty() {
|
|
return ("nothing".into(), t.as_bytes().to_vec());
|
|
}
|
|
let (s, e) = spans[rng.below(spans.len())];
|
|
let x = QIR_NUMBERS[rng.below(QIR_NUMBERS.len())];
|
|
(format!("the number at {s} set to {x}"), format!("{}{x}{}", &t[..s], &t[e..]).into_bytes())
|
|
}
|
|
2 => {
|
|
// A line repeated many times.
|
|
let i = rng.below(lines.len());
|
|
let k = [2usize, 64, 4096, 70_000][rng.below(4)];
|
|
let mut out: Vec<&str> = lines[..i].to_vec();
|
|
for _ in 0..k {
|
|
out.push(lines[i]);
|
|
}
|
|
out.extend_from_slice(&lines[i..]);
|
|
(format!("line {} repeated {k} times", i + 1), out.join("\n").into_bytes())
|
|
}
|
|
3 => {
|
|
// A branch turned back to the first block, or to itself.
|
|
let labels: Vec<&str> = lines.iter().filter_map(|l| l.trim().strip_suffix(':').filter(|x| !x.contains(' '))).collect();
|
|
let to = labels.get(rng.below(labels.len().max(1))).copied().unwrap_or("entry");
|
|
let i = rng.below(lines.len());
|
|
let mut out: Vec<String> = lines.iter().map(|l| l.to_string()).collect();
|
|
out.insert(i, format!(" br i1 true, label %{to}, label %{to}"));
|
|
(format!("a branch to %{to} at line {}", i + 1), out.join("\n").into_bytes())
|
|
}
|
|
4 => {
|
|
let n = rng.below(t.len());
|
|
let n = (0..=n).rev().find(|&k| t.is_char_boundary(k)).unwrap_or(0);
|
|
(format!("cut to {n} bytes"), t[..n].as_bytes().to_vec())
|
|
}
|
|
5 => {
|
|
let (i, j) = (rng.below(lines.len()), rng.below(other.lines().count().max(1)));
|
|
let mut out: Vec<&str> = lines[..i].to_vec();
|
|
out.extend(other.lines().skip(j));
|
|
(format!("the first {i} lines and another file's from line {}", j + 1), out.join("\n").into_bytes())
|
|
}
|
|
_ => {
|
|
let mut b = t.as_bytes().to_vec();
|
|
let flips = 1 + rng.below(4);
|
|
for _ in 0..flips {
|
|
let i = rng.below(b.len());
|
|
b[i] ^= 1 << rng.below(7);
|
|
}
|
|
(format!("{flips} bits flipped"), b)
|
|
}
|
|
}
|
|
}
|
|
|
|
thread_local! {
|
|
static CURRENT: std::cell::RefCell<String> = const { std::cell::RefCell::new(String::new()) };
|
|
}
|
|
|
|
#[test]
|
|
fn every_mutated_module_converts_or_is_refused_with_a_code() {
|
|
let bundle: Value = serde_json::from_str(BUNDLE).expect("bundle.json reads");
|
|
let mut files: Vec<(String, Format, Vec<u8>)> = Vec::new();
|
|
for c in bundle["cases"].as_array().expect("cases") {
|
|
let name = c["file"].as_str().unwrap().to_string();
|
|
match c["format"].as_str() {
|
|
Some("jeff") => files.push((name, Format::Jeff, formats::decode_base64(c["base64"].as_str().unwrap()).unwrap())),
|
|
Some("qir") => files.push((name, Format::Qir, c["text"].as_str().unwrap().as_bytes().to_vec())),
|
|
_ => {}
|
|
}
|
|
}
|
|
assert!(files.len() >= 40, "{} files", files.len());
|
|
// A panic says which input it was, even where a panic aborts.
|
|
let hook = std::panic::take_hook();
|
|
std::panic::set_hook(Box::new(move |info| {
|
|
CURRENT.with(|c| eprintln!("the input that panicked: {}", c.borrow()));
|
|
hook(info);
|
|
}));
|
|
let mut rng = Rng(SEED);
|
|
let (mut converted, mut refused, mut inputs) = (0usize, 0usize, 0usize);
|
|
let mut slowest: Vec<(f64, usize, String)> = Vec::new();
|
|
let mut worst_peak = (0usize, String::new());
|
|
let mut failures = Vec::new();
|
|
for (k, (name, format, bytes)) in files.iter().enumerate() {
|
|
// Each file unchanged, then its mutations.
|
|
for m in 0..=PER_FILE {
|
|
let (what, input) = if m == 0 {
|
|
("unchanged".to_string(), bytes.clone())
|
|
} else {
|
|
let others: Vec<&(String, Format, Vec<u8>)> = files.iter().filter(|f| f.1 == *format).collect();
|
|
let other = &others[rng.below(others.len())].2;
|
|
match format {
|
|
Format::Jeff => jeff_mutation(&mut rng, bytes, other),
|
|
_ => qir_mutation(&mut rng, std::str::from_utf8(bytes).unwrap(), std::str::from_utf8(other).unwrap()),
|
|
}
|
|
};
|
|
let label = format!("{name} #{m}: {what}");
|
|
CURRENT.with(|c| *c.borrow_mut() = label.clone());
|
|
let before = LIVE.load(Ordering::Relaxed);
|
|
PEAK.store(before, Ordering::Relaxed);
|
|
let start = std::time::Instant::now();
|
|
let out = formats::convert(*format, Format::Qasm, &input, None, true);
|
|
let secs = start.elapsed().as_secs_f64();
|
|
let peak = PEAK.load(Ordering::Relaxed).saturating_sub(before);
|
|
inputs += 1;
|
|
match out {
|
|
Ok(_) => converted += 1,
|
|
Err(d) if wai_quantum::qasm::diag::lookup(d.code).is_some() => refused += 1,
|
|
Err(d) => failures.push(format!("{label}: refused without a code of the table: {d}")),
|
|
}
|
|
if secs > MAX_SECONDS {
|
|
failures.push(format!("{label}: took {secs:.2} s, more than {MAX_SECONDS} s"));
|
|
}
|
|
if peak > MAX_PEAK {
|
|
failures.push(format!("{label}: allocated {peak} bytes at its peak, more than {MAX_PEAK}"));
|
|
}
|
|
if peak > worst_peak.0 {
|
|
worst_peak = (peak, label.clone());
|
|
}
|
|
slowest.push((secs, k, label));
|
|
}
|
|
}
|
|
// Every 32-bit field of each small jeff module set to its largest and to
|
|
// one past the register's cap, so that each loop bound, register size,
|
|
// array length and index the module holds is inflated in turn.
|
|
let mut swept = 0usize;
|
|
for (k, (name, format, bytes)) in files.iter().enumerate() {
|
|
if *format != Format::Jeff || bytes.len() > SWEEP_BYTES {
|
|
continue;
|
|
}
|
|
for i in (8..bytes.len().saturating_sub(3)).step_by(4) {
|
|
for x in [u32::MAX, (1 << 16) + 1] {
|
|
let mut input = bytes.clone();
|
|
input[i..i + 4].copy_from_slice(&x.to_le_bytes());
|
|
let label = format!("{name}: the 32 bits at {i} set to {x}");
|
|
CURRENT.with(|c| *c.borrow_mut() = label.clone());
|
|
let before = LIVE.load(Ordering::Relaxed);
|
|
PEAK.store(before, Ordering::Relaxed);
|
|
let start = std::time::Instant::now();
|
|
let out = formats::convert(*format, Format::Qasm, &input, None, true);
|
|
let secs = start.elapsed().as_secs_f64();
|
|
let peak = PEAK.load(Ordering::Relaxed).saturating_sub(before);
|
|
inputs += 1;
|
|
swept += 1;
|
|
match out {
|
|
Ok(_) => converted += 1,
|
|
Err(d) if wai_quantum::qasm::diag::lookup(d.code).is_some() => refused += 1,
|
|
Err(d) => failures.push(format!("{label}: refused without a code of the table: {d}")),
|
|
}
|
|
if secs > MAX_SECONDS {
|
|
failures.push(format!("{label}: took {secs:.2} s, more than {MAX_SECONDS} s"));
|
|
}
|
|
if peak > MAX_PEAK {
|
|
failures.push(format!("{label}: allocated {peak} bytes at its peak, more than {MAX_PEAK}"));
|
|
}
|
|
if peak > worst_peak.0 {
|
|
worst_peak = (peak, label.clone());
|
|
}
|
|
slowest.push((secs, k, label));
|
|
}
|
|
}
|
|
}
|
|
slowest.sort_by(|a, b| b.0.total_cmp(&a.0));
|
|
eprintln!(
|
|
"{inputs} inputs: {converted} converted, {refused} refused with a code; slowest {:.3} s ({}); largest peak {} bytes ({})",
|
|
slowest[0].0, slowest[0].2, worst_peak.0, worst_peak.1
|
|
);
|
|
if std::env::var_os("WAI_FORMATS_MUTATION_REPORT").is_some() {
|
|
for (s, _, l) in slowest.iter().take(15) {
|
|
eprintln!(" {s:.3} s {l}");
|
|
}
|
|
}
|
|
assert_eq!(inputs - swept, files.len() * (PER_FILE + 1), "the count of inputs is pinned by the files and PER_FILE");
|
|
eprintln!("{swept} of them every 32-bit field of the jeff modules of at most {SWEEP_BYTES} bytes, inflated");
|
|
assert!(failures.is_empty(), "{} of {inputs} inputs:\n{}", failures.len(), failures.join("\n"));
|
|
}
|