Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension


Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
1 change: 1 addition & 0 deletions CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -52,6 +52,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
- **Model-based storage test (#385).** `tests/model_based_test.rs` runs random sequences of `transact` (multi-valued batches, transaction- and fact-level valid-time windows, a triple repeated with another window), `retract`, write transactions (committed or rolled back, retracting their own assertions), checkpoints, reopens (default, a 4-page cache, auto-checkpoint every 2 writes) and simulated crashes (a copy of the `.graph` file and WAL taken while the handle is open, so the WAL is replayed) against a file in a temp dir. After every step, `current_tx_count`, `verify`, full rows with windows and tx counts, and entity-, entity+attribute-, attribute-, attribute+value-, value-bound and full-scan queries, under `:as-of N` and `:valid-at T`, must match a plain reference model (one valid-time window per triple, #435; API-011 for two windows of one triple in one statement and API-019 for an empty or inverted window, from `execute` and `tx.execute`, #436; the last statement that writes a triple decides it at commit, #477). Reads inside a write transaction are checked against what its commit will hold. Normal CI runs 24 cases; the nightly property-test workflow runs 30,000.
- **SIGKILL crash test checks committed data (#384).** `tests/crash_kill_test.rs` used to check only that the file reopened and one attribute query ran, so it missed #370 and could not reach #371. The child now runs a seeded workload (multi-valued batches, batched retracts, re-assertions) and logs each transaction after `execute` returns; it checkpoints after every transaction, every third, never (WAL replay), automatically every 2 writes, or every third with `SyncMode::Normal`. After a `SIGKILL` at a random point, the reopened file must hold exactly the model after the last logged transaction or the one in flight, through a full scan, attribute (AEVT), attribute+value (AVET) and entity-bound (EAVT) queries and `:as-of`, with `verify` clean. The checks run again after a second reopen and after a checkpoint plus reopen. Per-PR CI runs 5 rounds (one per mode); the nightly crash-kill workflow runs 100 per OS. `MINIGRAF_CRASH_KILL_SEED` replays a failure.
- **Fuzzing reaches the v8 decoders, and the corpus is kept between runs (#387, #375).** On `v3`, the `btree_page` and `fact_page` targets still wrote the pre-release single-header layout and stopped at `STG-032` on every input, and `file_header` rarely got past the meta CRC. The page targets now start from a real v8 file built through the public API (rewritten with `LogWriter` at fixed tx times so its bytes are the same in every process). They overwrite one page with the input and recompute that page's checksum. `btree_page` fuzzes any leaf or internal node of the five trees, `file_header` fuzzes either meta slot (with or without a matching CRC, with or without the other slot), and `fact_page` fuzzes the fact page of a v7 golden file through migration and the read-only load. Each run executes one input-chosen probe query or `verify()`. The nightly fuzz workflow now runs every target in its own parallel job, on `main` and `v3` on alternating crons, and keeps each target's corpus in the Actions cache. A new weekly workflow (`fuzz-corpus.yml`) minimizes the cached corpus with `cargo fuzz cmin`, keeps every committed `seed_*` file, and proposes the result as a pull request.
- **Two fuzz targets check results, not just crashes (#387).** `ops_sequence` decodes the input into up to 32 storage operations (transact, retract, a write transaction that commits or rolls back, checkpoint, reopen, and a crash that opens a copy of the file and WAL) and, after each one, compares the full rows now and at an input-chosen `:as-of`, plus one input-chosen query shape, with the reference model of the model-based test. It uses that test's driver and checks, now in `tests/reference_model`, so the proptest test and the fuzzer share one oracle. `corrupt_file` damages a file written over three checkpoints with up to 16 byte flips and an optional truncation, without fixing any checksum, and requires every query to fail or to return exactly the answers of the last checkpoint or the one before it, all from the same one. Its first run found that a file cut to under one page opens as a new, empty database (#506); the target skips those lengths until that is fixed.

### Known issues

Expand Down
2 changes: 1 addition & 1 deletion ROADMAP.md
Original file line number Diff line number Diff line change
Expand Up @@ -91,7 +91,7 @@ Scope — release-gate testing and documentation:
- SIGKILL crash test that checks committed data through EAVT, AEVT and full scan (#384; done on `v3`: `tests/crash_kill_test.rs`, 100 rounds per OS nightly)
- Model-based test of transact/retract/checkpoint/reopen (#385; done on `v3`: `tests/model_based_test.rs`, 30,000 cases nightly)
- Wider property tests: file-backed, batched, retracts, temporal, joins (#386)
- Persistent fuzz corpus and an operation-sequence target (#387; corpus caching, weekly `cmin` and the v8 page targets done on `v3`; `ops_sequence` and `corrupt_file` targets next)
- Persistent fuzz corpus and an operation-sequence target (#387; done on `v3`: corpus caching, weekly `cmin`, the v8 page targets, and the `ops_sequence` and `corrupt_file` targets)
- Fault injection across save/WAL/recovery (#390)
- Long-running soak test at scale (#392)
- Benchmarks at 100K–10M facts and a published performance envelope (#394)
Expand Down
15 changes: 15 additions & 0 deletions fuzz/Cargo.toml
Original file line number Diff line number Diff line change
Expand Up @@ -14,6 +14,9 @@ libfuzzer-sys = "0.4"
minigraf = { path = ".." }
tempfile = "3"
crc32fast = "1"
# ops_sequence includes tests/reference_model, shared with the model-based test.
proptest = "1"
uuid = { version = "1.0", features = ["v5"] }

[[bin]]
name = "wal_entry"
Expand Down Expand Up @@ -50,3 +53,15 @@ name = "datalog_eval"
path = "fuzz_targets/datalog_eval.rs"
test = false
doc = false

[[bin]]
name = "ops_sequence"
path = "fuzz_targets/ops_sequence.rs"
test = false
doc = false

[[bin]]
name = "corrupt_file"
path = "fuzz_targets/corrupt_file.rs"
test = false
doc = false
Binary file added fuzz/corpus/corrupt_file/seed_flip_free_list.bin
Binary file not shown.
Binary file added fuzz/corpus/corrupt_file/seed_flip_internal.bin
Binary file not shown.
Binary file added fuzz/corpus/corrupt_file/seed_flip_leaf.bin
Binary file not shown.
Binary file added fuzz/corpus/corrupt_file/seed_flip_meta_a.bin
Binary file not shown.
Binary file added fuzz/corpus/corrupt_file/seed_flip_meta_b.bin
Binary file not shown.
Binary file not shown.
Binary file added fuzz/corpus/corrupt_file/seed_flip_value.bin
Binary file not shown.
Binary file added fuzz/corpus/corrupt_file/seed_no_edits.bin
Binary file not shown.
Binary file not shown.
Binary file not shown.
Original file line number Diff line number Diff line change
@@ -0,0 +1 @@
AAAAAAAA?vAAAAêA2AãAAAÃë=$Å
Binary file not shown.
Original file line number Diff line number Diff line change
@@ -0,0 +1 @@
ÝÝÝ?ÿZñ·È°£PWžBÀ[0ŒÉNéNq
Original file line number Diff line number Diff line change
@@ -0,0 +1 @@
<<<?<<<<<<<<<<|<<<?<<<<
202 changes: 202 additions & 0 deletions fuzz/fuzz_targets/corrupt_file.rs
Original file line number Diff line number Diff line change
@@ -0,0 +1,202 @@
//! Opening a damaged file must return an error or correct data, never wrong
//! data.
//!
//! The template is built once per process from fixed statements over three
//! checkpoints, with no WAL left; after each checkpoint the answers of a fixed
//! set of queries are recorded. The input damages a copy of it:
//!
//! - byte 0: bit 0 opens read-only; bits 1–2 pick a truncation: 1 = to a page
//! multiple, 2 = to any length, else none
//! - bytes 1..5: the truncation length (u32 LE, modulo the file length)
//! - then up to 16 edits of 5 bytes: offset (u32 LE, modulo the file length)
//! and a byte to xor in (0 becomes 1)
//!
//! Checksums are **not** recomputed: the CRCs are the contract under test.
//! Each query must fail or return exactly the answer of the last generation or
//! of the one before it (the meta fallback when the active meta page is
//! damaged), and every query that answers must agree on one generation. A
//! mismatch panics. `verify()` runs too and may fail, but must not panic.
#![no_main]
use libfuzzer_sys::fuzz_target;
use minigraf::{Minigraf, OpenOptions, QueryResult};
use std::sync::OnceLock;

const PAGE_SIZE: usize = 4096;
const MAX_EDITS: usize = 16;

/// Queries that between them read every index (EAVT, AEVT, AVET, VAET), the
/// DICT (idents and long values) and the time-travel paths.
const QUERIES: [&str; 8] = [
"(query [:find ?e ?a ?v :any-valid-time :where [?e ?a ?v]])",
"(query [:find ?a ?v :where [:e1 ?a ?v]])",
"(query [:find ?e ?v :where [?e :a/num ?v]])",
"(query [:find ?e :where [?e :a/num 7]])",
"(query [:find ?e :where [?e :a/next :e5]])",
"(query [:find ?v :valid-at \"2002-01-01\" :where [:e0 :a/long ?v]])",
"(query [:find ?e ?v :as-of 1 :where [?e :a/name ?v]])",
"(query [:find ?e ?v :where [?e :a/note ?v]])",
];

/// One generation's answers: the tx count, then one sorted row list per query.
/// Rows are compared, never printed (a `Ref` renders its `Uuid`).
#[derive(PartialEq)]
struct Answers {
tx_count: u64,
rows: Vec<Vec<String>>,
}

struct Template {
bytes: Vec<u8>,
/// Answers after each of the three checkpoints, oldest first.
generations: Vec<Answers>,
}

fn rows(db: &Minigraf, query: &str) -> Option<Vec<String>> {
match db.execute(query).ok()? {
QueryResult::QueryResults { results, .. } => {
let mut out: Vec<String> = results.iter().map(|r| format!("{r:?}")).collect();
out.sort();
Some(out)
}
_ => None,
}
}

fn answers(db: &Minigraf) -> Answers {
Answers {
tx_count: db.current_tx_count(),
rows: QUERIES
.iter()
.map(|q| rows(db, q).expect("template query"))
.collect(),
}
}

fn template() -> &'static Template {
static T: OnceLock<Template> = OnceLock::new();
T.get_or_init(build_template)
}

fn build_template() -> Template {
let dir = tempfile::tempdir().expect("tempdir");
let path = dir.path().join("template.graph");
let long = |c: &str| c.repeat(300);
let mut generations = Vec::new();
{
let db = Minigraf::open(&path).expect("open");
// Checkpoint 1: enough entities for internal nodes in every index.
let mut facts = String::new();
for i in 0..90 {
facts.push_str(&format!(
"[:e{i} :a/num {i}] [:e{i} :a/name \"name{i}\"] [:e{i} :a/next :e{}] ",
i + 1
));
}
db.execute(&format!("(transact [{facts}])"))
.expect("transact");
db.checkpoint().expect("checkpoint");
generations.push(answers(&db));

// Checkpoint 2: long values (value pages), a valid-time window, a
// retraction, and new values for existing triples.
db.execute(&format!(
"(transact {{:valid-from \"2001-01-01\" :valid-to \"2005-01-01\"}} \
[[:e0 :a/long \"{}\"] [:e1 :a/flag true] [:e2 :a/kw :k/x]])",
long("L")
))
.expect("transact");
db.execute("(retract [[:e3 :a/num 3] [:e7 :a/num 7]])")
.expect("retract");
db.execute(&format!(
"(transact [[:e1 :a/note \"{}\"] [:e7 :a/num 70] [:e9 :a/next :e5]])",
long("N")
))
.expect("transact");
db.checkpoint().expect("checkpoint");
generations.push(answers(&db));

// Checkpoint 3: copy-on-write over the same leaves, freeing pages.
db.execute(&format!(
"(transact [[:e40 :a/note \"{}\"] [:e7 :a/num 7] [:e1 :a/name \"renamed\"]])",
long("M")
))
.expect("transact");
db.execute("(retract [[:e4 :a/next :e5] [:e1 :a/flag true]])")
.expect("retract");
db.checkpoint().expect("checkpoint");
generations.push(answers(&db));
}
let mut wal = path.as_os_str().to_owned();
wal.push(".wal");
assert!(
!std::path::Path::new(&wal).exists(),
"template must have no WAL"
);
let bytes = std::fs::read(&path).expect("read template");
assert!(
generations[1] != generations[2],
"the last two generations must differ"
);
Template { bytes, generations }
}

fn u32_at(data: &[u8], at: usize) -> Option<usize> {
let b = data.get(at..at + 4)?;
Some(u32::from_le_bytes([b[0], b[1], b[2], b[3]]) as usize)
}

fuzz_target!(|data: &[u8]| {
let Some(&flags) = data.first() else {
return;
};
let t = template();
let len = t.bytes.len();
let mut bytes = t.bytes.clone();
for edit in data.get(5..).unwrap_or(&[]).chunks_exact(5).take(MAX_EDITS) {
let off = u32_at(edit, 0).unwrap_or(0) % len;
bytes[off] ^= edit[4].max(1);
}
let trunc = u32_at(data, 1).unwrap_or(0) % len;
match (flags >> 1) & 0x03 {
1 => bytes.truncate(trunc / PAGE_SIZE * PAGE_SIZE),
2 => bytes.truncate(trunc),
_ => {}
}
// An empty file opens as a new, empty database. A file shorter than one
// page does too today (#506); skipped until that is fixed.
if bytes.len() < PAGE_SIZE {
return;
}

let Ok(dir) = tempfile::tempdir() else {
return;
};
let path = dir.path().join("fuzz.graph");
if std::fs::write(&path, &bytes).is_err() {
return;
}
let opts = OpenOptions::new().read_only(flags & 0x01 != 0);
let Ok(db) = Minigraf::open_with_options(&path, opts) else {
return;
};

// The last generation, or the one before it; narrowed by every answer.
let mut candidates: Vec<&Answers> = t.generations[1..].iter().collect();
candidates.retain(|g| g.tx_count == db.current_tx_count());
assert!(
!candidates.is_empty(),
"opened with a tx count of no recent generation"
);
for (i, q) in QUERIES.iter().enumerate() {
let Some(got) = rows(&db, q) else {
continue;
};
candidates.retain(|g| g.rows[i] == got);
assert!(
!candidates.is_empty(),
"query {i} answered with data of no recent generation, or of a \
different generation than the queries before it"
);
}
let _ = db.verify();
});
Loading
Loading