diff --git a/.github/workflows/fuzz-corpus.yml b/.github/workflows/fuzz-corpus.yml new file mode 100644 index 0000000000..98fe931365 --- /dev/null +++ b/.github/workflows/fuzz-corpus.yml @@ -0,0 +1,179 @@ +name: Fuzz corpus (weekly) + +# Minimizes each target's cached fuzz corpus (see fuzz.yml) with +# `cargo fuzz cmin`, saves the result back to the cache, and proposes it as a +# commit to the branch in a pull request from bot/fuzz-corpus- (#387). +# Committed seed_* files are always kept: they are regression seeds. +# +# Two branches, as in fuzz.yml: main on Monday 08:00 UTC, v3 on Monday 20:00 +# UTC. Keep the cron strings here and in CORPUS_REF/run-name identical, and +# keep this file the same on main and v3. +# +# Opening the pull request needs the repository setting "Allow GitHub Actions +# to create and approve pull requests". Without it, the branch is still +# pushed and the job summary links to it. Pull requests opened with +# GITHUB_TOKEN do not start CI; they change only fuzz/corpus/. +run-name: >- + Fuzz corpus (${{ github.event_name == 'workflow_dispatch' && inputs.ref + || (github.event.schedule == '0 20 * * 1' && 'v3' || 'main') }}) + +on: + schedule: + - cron: "0 8 * * 1" # main + - cron: "0 20 * * 1" # v3 + workflow_dispatch: + inputs: + ref: + description: Branch whose corpus to minimize + required: true + default: main + +permissions: + contents: read + +env: + CORPUS_REF: ${{ github.event_name == 'workflow_dispatch' && inputs.ref || (github.event.schedule == '0 20 * * 1' && 'v3' || 'main') }} + # Larger corpus files stay in the cache only. + MAX_COMMITTED_BYTES: "65536" + +jobs: + targets: + name: List fuzz targets + runs-on: ubuntu-latest + outputs: + targets: ${{ steps.list.outputs.targets }} + steps: + - uses: actions/checkout@v4 + with: + ref: ${{ env.CORPUS_REF }} + + - name: Read the [[bin]] names + id: list + shell: bash + run: | + targets="$(sed -n 's/^name = "\(.*\)"$/\1/p' fuzz/Cargo.toml | grep -vx minigraf-fuzz \ + | jq -R . | jq -sc .)" + echo "targets=$targets" >> "$GITHUB_OUTPUT" + + cmin: + name: Minimize ${{ matrix.target }} + needs: targets + runs-on: ubuntu-latest + timeout-minutes: 60 + strategy: + fail-fast: false + matrix: + target: ${{ fromJSON(needs.targets.outputs.targets) }} + + steps: + - uses: actions/checkout@v4 + with: + ref: ${{ env.CORPUS_REF }} + + - name: Install Rust nightly + uses: dtolnay/rust-toolchain@nightly + + - name: Cache cargo-fuzz binary + uses: actions/cache@v4 + with: + path: ~/.cargo/bin/cargo-fuzz + key: cargo-fuzz-${{ runner.os }}-${{ hashFiles('fuzz/Cargo.toml') }} + + - name: Install cargo-fuzz + run: which cargo-fuzz || cargo install cargo-fuzz + + - name: Restore corpus + uses: actions/cache/restore@v4 + with: + path: fuzz/corpus/${{ matrix.target }} + key: fuzz-corpus-${{ env.CORPUS_REF }}-${{ matrix.target }}-cmin-${{ github.run_id }}-${{ github.run_attempt }} + restore-keys: fuzz-corpus-${{ env.CORPUS_REF }}-${{ matrix.target }}- + + - name: Minimize + shell: bash + env: + TARGET: ${{ matrix.target }} + run: | + dir="fuzz/corpus/$TARGET" + echo "Before: $(find "$dir" -type f | wc -l) files" + cargo fuzz cmin -O "$TARGET" "$dir" + # Put back every committed seed cmin dropped. + git ls-files -z "$dir" | grep -z '/seed_' | xargs -0 -r git checkout -- + echo "After: $(find "$dir" -type f | wc -l) files" + + - name: Save corpus + uses: actions/cache/save@v4 + with: + path: fuzz/corpus/${{ matrix.target }} + key: fuzz-corpus-${{ env.CORPUS_REF }}-${{ matrix.target }}-cmin-${{ github.run_id }}-${{ github.run_attempt }} + + - name: Keep committable files + shell: bash + env: + TARGET: ${{ matrix.target }} + run: | + mkdir -p "committed/$TARGET" + find "fuzz/corpus/$TARGET" -maxdepth 1 -type f -size -"$((MAX_COMMITTED_BYTES + 1))"c \ + -exec cp {} "committed/$TARGET/" \; + + - uses: actions/upload-artifact@v4 + with: + name: corpus-${{ matrix.target }} + path: committed/ + retention-days: 7 + + propose: + name: Propose the minimized corpus + needs: cmin + runs-on: ubuntu-latest + permissions: + contents: write + pull-requests: write + steps: + - uses: actions/checkout@v4 + with: + ref: ${{ env.CORPUS_REF }} + + - uses: actions/download-artifact@v4 + with: + pattern: corpus-* + path: minimized + merge-multiple: true + + - name: Commit, push and open the pull request + shell: bash + env: + GH_TOKEN: ${{ github.token }} + run: | + branch="bot/fuzz-corpus-$CORPUS_REF" + for d in minimized/*/; do + target="$(basename "$d")" + rm -rf "fuzz/corpus/$target" + cp -r "$d" "fuzz/corpus/$target" + done + git add -A fuzz/corpus + if git diff --cached --quiet; then + echo "Corpus unchanged." | tee -a "$GITHUB_STEP_SUMMARY" + exit 0 + fi + git config user.name "github-actions[bot]" + git config user.email "41898282+github-actions[bot]@users.noreply.github.com" + git commit -q -m "fuzz: minimized corpus for $CORPUS_REF (weekly cmin)" \ + -m "Run: $GITHUB_SERVER_URL/$GITHUB_REPOSITORY/actions/runs/$GITHUB_RUN_ID" \ + -m "Refs #387" + git push -f origin "HEAD:refs/heads/$branch" + + body="Weekly \`cargo fuzz cmin\` of the cached corpus of every fuzz target on \`$CORPUS_REF\`, with all committed \`seed_*\` files kept. Files over $MAX_COMMITTED_BYTES bytes stay in the cache only. Generated by \`.github/workflows/fuzz-corpus.yml\` (#387). + + Run: $GITHUB_SERVER_URL/$GITHUB_REPOSITORY/actions/runs/$GITHUB_RUN_ID" + existing="$(gh pr list --head "$branch" --base "$CORPUS_REF" --state open --json number --jq '.[0].number')" + if [ -n "$existing" ]; then + echo "Updated pull request #$existing." | tee -a "$GITHUB_STEP_SUMMARY" + elif gh pr create --base "$CORPUS_REF" --head "$branch" \ + --title "fuzz: minimized corpus for $CORPUS_REF" --body "$body"; then + echo "Opened a pull request from $branch." | tee -a "$GITHUB_STEP_SUMMARY" + else + compare="$GITHUB_SERVER_URL/$GITHUB_REPOSITORY/compare/$CORPUS_REF...$branch?expand=1" + echo "Could not open the pull request (is \"Allow GitHub Actions to create and approve pull requests\" off?). Open it from $compare" \ + | tee -a "$GITHUB_STEP_SUMMARY" + fi diff --git a/.github/workflows/fuzz.yml b/.github/workflows/fuzz.yml index eef1af0410..50160be718 100644 --- a/.github/workflows/fuzz.yml +++ b/.github/workflows/fuzz.yml @@ -1,22 +1,75 @@ name: Fuzz (nightly) +# Two branches alternate every 12 hours: main at 04:00 UTC, v3 at 16:00 UTC. +# Scheduled runs always use this file from the default branch, so the branch +# under test is chosen from the cron string that fired (as in bench.yml). +# Keep the cron strings here and in FUZZ_REF/run-name identical, and keep this +# file the same on main and v3. +# +# Each target runs in its own job, in parallel. The corpus a run grows is saved +# in the Actions cache per branch and target, and the next run starts from it +# (#387). fuzz-corpus.yml minimizes it weekly and proposes it as a commit. +run-name: >- + Fuzz (${{ github.event_name == 'workflow_dispatch' && inputs.ref + || (github.event.schedule == '0 16 * * *' && 'v3' || 'main') }}) + on: schedule: - - cron: "0 4 * * *" + - cron: "0 4 * * *" # main + - cron: "0 16 * * *" # v3 workflow_dispatch: + inputs: + ref: + description: Branch to fuzz + required: true + default: main + seconds: + description: Seconds per target + required: true + default: "3300" permissions: contents: read - issues: write + +env: + FUZZ_REF: ${{ github.event_name == 'workflow_dispatch' && inputs.ref || (github.event.schedule == '0 16 * * *' && 'v3' || 'main') }} + FUZZ_SECONDS: ${{ github.event_name == 'workflow_dispatch' && inputs.seconds || '3300' }} jobs: + targets: + name: List fuzz targets + runs-on: ubuntu-latest + outputs: + targets: ${{ steps.list.outputs.targets }} + steps: + - uses: actions/checkout@v4 + with: + ref: ${{ env.FUZZ_REF }} + + # Each branch fuzzes the targets its own fuzz/Cargo.toml declares. + - name: Read the [[bin]] names + id: list + shell: bash + run: | + targets="$(sed -n 's/^name = "\(.*\)"$/\1/p' fuzz/Cargo.toml | grep -vx minigraf-fuzz \ + | jq -R . | jq -sc .)" + echo "targets=$targets" >> "$GITHUB_OUTPUT" + echo "Targets on $FUZZ_REF: $targets" + fuzz: - name: Fuzz targets + name: Fuzz ${{ matrix.target }} + needs: targets runs-on: ubuntu-latest - timeout-minutes: 360 + timeout-minutes: 90 + strategy: + fail-fast: false + matrix: + target: ${{ fromJSON(needs.targets.outputs.targets) }} steps: - uses: actions/checkout@v4 + with: + ref: ${{ env.FUZZ_REF }} - name: Install Rust nightly uses: dtolnay/rust-toolchain@nightly @@ -30,102 +83,77 @@ jobs: - name: Install cargo-fuzz run: which cargo-fuzz || cargo install cargo-fuzz - - name: Fuzz wal_entry (55m) - id: wal_entry - shell: bash - run: | - set -o pipefail - cargo fuzz run wal_entry -- -max_total_time=3300 2>&1 | tee fuzz-wal_entry.log - continue-on-error: true - - - name: Fuzz file_header (55m) - id: file_header - shell: bash - run: | - set -o pipefail - cargo fuzz run file_header -- -max_total_time=3300 2>&1 | tee fuzz-file_header.log - continue-on-error: true - - - name: Fuzz fact_page (55m) - id: fact_page - shell: bash - run: | - set -o pipefail - cargo fuzz run fact_page -- -max_total_time=3300 2>&1 | tee fuzz-fact_page.log - continue-on-error: true + - name: Restore corpus + uses: actions/cache/restore@v4 + with: + path: fuzz/corpus/${{ matrix.target }} + key: fuzz-corpus-${{ env.FUZZ_REF }}-${{ matrix.target }}-${{ github.run_id }}-${{ github.run_attempt }} + restore-keys: fuzz-corpus-${{ env.FUZZ_REF }}-${{ matrix.target }}- - - name: Fuzz btree_page (55m) - id: btree_page - shell: bash - run: | - set -o pipefail - cargo fuzz run btree_page -- -max_total_time=3300 2>&1 | tee fuzz-btree_page.log - continue-on-error: true + - name: Build + run: cargo fuzz build -O ${{ matrix.target }} - - name: Fuzz datalog_parser (55m) - id: datalog_parser + # -timeout: one input running this long is a hang (libFuzzer's default + # of 1200 s would spend a third of the budget on it). + - name: Fuzz ${{ matrix.target }} shell: bash run: | set -o pipefail - cargo fuzz run datalog_parser -- -max_total_time=3300 2>&1 | tee fuzz-datalog_parser.log - continue-on-error: true + cargo fuzz run -O ${{ matrix.target }} fuzz/corpus/${{ matrix.target }} -- \ + -max_total_time="$FUZZ_SECONDS" -timeout=60 2>&1 | tee fuzz-${{ matrix.target }}.log - - name: Fuzz datalog_eval (55m) - id: datalog_eval - shell: bash - run: | - set -o pipefail - cargo fuzz run datalog_eval -- -max_total_time=3300 2>&1 | tee fuzz-datalog_eval.log - continue-on-error: true + - name: Save corpus + if: ${{ always() }} + uses: actions/cache/save@v4 + with: + path: fuzz/corpus/${{ matrix.target }} + key: fuzz-corpus-${{ env.FUZZ_REF }}-${{ matrix.target }}-${{ github.run_id }}-${{ github.run_attempt }} - - name: Upload fuzz failures - if: ${{ always() && (steps.wal_entry.outcome == 'failure' || steps.file_header.outcome == 'failure' || steps.fact_page.outcome == 'failure' || steps.btree_page.outcome == 'failure' || steps.datalog_parser.outcome == 'failure' || steps.datalog_eval.outcome == 'failure') }} + - name: Upload failure + if: ${{ failure() }} uses: actions/upload-artifact@v4 with: - name: fuzz-failures-${{ github.run_id }} + name: fuzz-failure-${{ matrix.target }} path: | - fuzz/artifacts/ - fuzz-*.log + fuzz/artifacts/${{ matrix.target }}/ + fuzz-${{ matrix.target }}.log if-no-files-found: warn retention-days: 30 - - name: Record fuzz failures - if: ${{ always() && (steps.wal_entry.outcome == 'failure' || steps.file_header.outcome == 'failure' || steps.fact_page.outcome == 'failure' || steps.btree_page.outcome == 'failure' || steps.datalog_parser.outcome == 'failure' || steps.datalog_eval.outcome == 'failure') }} + report: + name: Record fuzz failures + needs: fuzz + if: ${{ failure() }} + runs-on: ubuntu-latest + permissions: + contents: read + issues: write + steps: + - uses: actions/download-artifact@v4 + with: + pattern: fuzz-failure-* + path: failures + + - name: Open or update the issue shell: bash env: GH_TOKEN: ${{ github.token }} - ISSUE_TITLE: "Nightly fuzz failure" - FAILED_TARGETS: >- - wal_entry=${{ steps.wal_entry.outcome }}, - file_header=${{ steps.file_header.outcome }}, - fact_page=${{ steps.fact_page.outcome }}, - btree_page=${{ steps.btree_page.outcome }}, - datalog_parser=${{ steps.datalog_parser.outcome }}, - datalog_eval=${{ steps.datalog_eval.outcome }} + ISSUE_TITLE: "Nightly fuzz failure (${{ env.FUZZ_REF }})" run: | report_file="fuzz-failure.md" - artifact_url="$GITHUB_SERVER_URL/$GITHUB_REPOSITORY/actions/runs/$GITHUB_RUN_ID" + run_url="$GITHUB_SERVER_URL/$GITHUB_REPOSITORY/actions/runs/$GITHUB_RUN_ID" { - echo "The nightly fuzz workflow found one or more failures." + echo "The nightly fuzz workflow found one or more failures on \`$FUZZ_REF\`." echo - echo "- Run and artifacts: $artifact_url" - echo "- Commit: $GITHUB_SHA" - echo "- Target outcomes: $FAILED_TARGETS" - echo "- Reproduce: \`cargo +nightly fuzz run fuzz/artifacts//\`" - echo "- Full logs: see the \`fuzz-failures-$GITHUB_RUN_ID\` artifact on the run above" + echo "- Run and artifacts: $run_url" + echo "- Reproduce: check out \`$FUZZ_REF\` at the run's commit, then" + echo " \`cargo +nightly fuzz run fuzz/artifacts//\`" echo echo "## Fuzz logs (failed targets only, last 100 lines each)" echo - - IFS=',' read -ra target_outcomes <<< "$FAILED_TARGETS" - for entry in "${target_outcomes[@]}"; do - entry="$(echo "$entry" | xargs)" - target="${entry%%=*}" - outcome="${entry#*=}" - [ "$outcome" = "failure" ] || continue - log="fuzz-${target}.log" - [ -e "$log" ] || continue - echo "### $log" + shopt -s nullglob + for log in failures/fuzz-failure-*/fuzz-*.log; do + echo "### $(basename "$log")" echo echo '```text' tail -n 100 "$log" @@ -134,7 +162,7 @@ jobs: done } > "$report_file" - # Defensive hard cap: GitHub issue/comment bodies max out at 65536 chars. + # GitHub issue and comment bodies max out at 65536 characters. max_bytes=60000 if [ "$(wc -c < "$report_file")" -gt "$max_bytes" ]; then head -c "$max_bytes" "$report_file" > "${report_file}.tmp" @@ -142,7 +170,7 @@ jobs: echo echo "..." echo - echo "_Report truncated to fit GitHub's body size limit. See the run and artifact linked above for full logs._" + echo "_Report truncated to fit GitHub's body size limit. See the run linked above for full logs._" } >> "${report_file}.tmp" mv "${report_file}.tmp" "$report_file" fi @@ -153,7 +181,7 @@ jobs: --search "$ISSUE_TITLE in:title" \ --json number,title \ --limit 100 \ - --jq '.[] | select(.title == "Nightly fuzz failure") | .number' \ + --jq ".[] | select(.title == \"$ISSUE_TITLE\") | .number" \ | head -n 1)" if [ -n "$existing_issue" ]; then @@ -161,7 +189,4 @@ jobs: else gh issue create --repo "$GITHUB_REPOSITORY" --title "$ISSUE_TITLE" --body-file "$report_file" fi - - - name: Fail workflow when fuzzing finds a failure - if: ${{ always() && (steps.wal_entry.outcome == 'failure' || steps.file_header.outcome == 'failure' || steps.fact_page.outcome == 'failure' || steps.btree_page.outcome == 'failure' || steps.datalog_parser.outcome == 'failure' || steps.datalog_eval.outcome == 'failure') }} - run: exit 1 + exit 1 diff --git a/CHANGELOG.md b/CHANGELOG.md index 96a6da3b0a..fc33fbc20e 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -50,6 +50,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **Golden-file compatibility corpus (#391).** `tests/golden/` holds v7 files written by minigraf 2.0.3, each with a JSON manifest of its CRC32, `tx_count` and expected query results. They cover one checkpoint, several checkpoints, indexes rebuilt on open, a WAL left by a crash, a WAL whose entries were already checkpointed, and same-transaction multi-values (#371). `tests/golden_corpus_test.rs` opens a copy of each file and checks its manifest after open, after a checkpoint and reopen, and after one more write. Golden files are never regenerated, only added; a new `golden-corpus` job in `policy.yml` fails a pull request that changes one. The generator is a standalone crate pinned to `minigraf = "=2.0.3"` (`tests/golden/gen/v7/`). On `v3`, each v7 file must also carry a v8 meta page after its first open, and seven v8 files are frozen alongside them, written by the `v3` branch at `23aa57c` (`tests/golden/gen/v8/`): one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values (a 4,068-byte string stored twice, the 64/65-byte inline boundary, a 1,000-byte attribute and keyword). All #371 queries now pass. - **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. ### Known issues diff --git a/ROADMAP.md b/ROADMAP.md index 5827736a86..4e353541f2 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -76,7 +76,7 @@ Scope — format and storage integrity: - One current valid-time window per `(e, a, v)`: a later assertion replaces the earlier window, and two windows of one fact in one `transact` are `API-011` (#435; done on `v3`) - Empty or inverted valid-time windows rejected with `API-019` on every write path (#436; done on `v3`) - In a `WriteTransaction`, the last statement that writes a fact decides it, so reads inside the transaction match the commit; `LogWriter` keeps the same rules, with `API-020` for an assertion and retraction of one fact in one transaction (#477; done on `v3`) -- `btree_page` fuzz target that reaches node decoding (#375) +- `btree_page` fuzz target that reaches node decoding (#375; done on `v3` with #387: page targets rebuilt on real v8 files) Scope — query API: @@ -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) +- 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) - 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) diff --git a/docs/superpowers/plans/2026-10-09-fuzz-corpus-and-page-targets.md b/docs/superpowers/plans/2026-10-09-fuzz-corpus-and-page-targets.md new file mode 100644 index 0000000000..53ca584e85 --- /dev/null +++ b/docs/superpowers/plans/2026-10-09-fuzz-corpus-and-page-targets.md @@ -0,0 +1,30 @@ +# Fuzz corpus and page targets (PR A) — Plan + +Spec: `docs/superpowers/specs/2026-10-09-fuzz-corpus-and-ops-target-design.md` §3–§4. +Branch `fuzz/387-corpus-and-page-targets` off `origin/v3`; PR to `v3`, "Refs #387, #375". +Then PR A′: the two workflow files only, to `main`. + +## Tasks + +1. **Shared template helper** — `fuzz/fuzz_targets/common/mod.rs` (included with + `#[path]`): build the v8 template once (`OnceLock`) through the public API, list its + pages by type from the page headers, `fix_page_crc`, `fix_meta_crc`, and run the + standard probe queries plus `verify()`. Add `crc32fast` to `fuzz/Cargo.toml`. +2. **`btree_page`** — rewrite per spec §4.1. +3. **`fact_page`** — rewrite on `tests/golden/v7_basic.graph` per §4.2. +4. **`file_header`** — rewrite per §4.3. +5. **Seeds** — a `fuzz/seedgen` example? No: a `#[test]`-free binary is overkill. + Generate seeds once with a throwaway program in the scratchpad that uses the + same helper, and commit the bytes. Note how they were made in + `fuzz/corpus/README.md`. +6. **Acceptance for #375** — temporary `eprintln!` in `node.rs` leaf/internal decode + (not committed): run `btree_page` on the leaf seed, internal seed and a + truncated seed; confirm decode reached and the leaf seed's query returns rows. + Run each target for 60 s locally; no crashes. +7. **Workflows** — `fuzz.yml` (two crons, `targets` → matrix `fuzz` → `report`, + corpus cache), `fuzz-corpus.yml` (weekly cmin, seeds kept, cache save, bot + branch + PR, compare link fallback). Lint with `actionlint` if available. + Trigger `workflow_dispatch` on the PR branch with `seconds=60` to smoke-test. +8. **Docs** — `docs/TEST_COVERAGE.md` fuzz section, CLAUDE.md only if counts change + (fuzz targets are not counted as tests). +9. **PR A** to `v3`; monitor CI. **PR A′** to `main` (workflows only). diff --git a/docs/superpowers/specs/2026-10-09-fuzz-corpus-and-ops-target-design.md b/docs/superpowers/specs/2026-10-09-fuzz-corpus-and-ops-target-design.md new file mode 100644 index 0000000000..c7ea7e1721 --- /dev/null +++ b/docs/superpowers/specs/2026-10-09-fuzz-corpus-and-ops-target-design.md @@ -0,0 +1,227 @@ +# Fuzz corpus, page targets and an operation-sequence target — Design + +**Issues:** #387 (with #375), tracker #383 +**Milestone:** v3.0.0, branch `v3`, plus a workflow-only PR to `main` + +## 1. Problems + +1. `.github/workflows/fuzz.yml` neither caches nor commits the corpus. Every night + each target starts again from the seeds in `fuzz/corpus/` and spends its 55 + minutes finding the same coverage again. +2. Scheduled workflows run from the default branch's workflow file, and that file + checks out `main`. The v3 code (format v8) has never been fuzzed at night. +3. On `v3`, three of the six targets no longer reach the code they are named for. + They still write the pre-release single-header layout, which has no `"META"` + magic: + - `btree_page` and `fact_page` stop at STG-032 on every input (#375 was filed + against an older layout; the problem is now worse). + - `file_header` fuzzes page 0, but almost every input fails the meta CRC, so + the meta field checks behind it are never reached. +4. Every target parses one input. No target fuzzes a sequence of storage + operations or checks that the database returns correct data. + +`wal_entry`, `datalog_parser` and `datalog_eval` are fine. + +## 2. Delivery + +| PR | Base | Contents | +|---|---|---| +| A | `v3` | §3 workflows, §4 page targets (#375), seeds | +| A′ | `main` | §3 workflows only, byte-identical to PR A's copies | +| B | `v3` | §5 `ops_sequence`, §6 `corrupt_file`, seeds | + +All say "Refs #387" (PR A also "Refs #375"). No closing keywords: the tracker +closes issues. The workflow files are the same on both branches, so future +`main` → `v3` merges do not conflict on them. + +No library code changes. The fuzz crate is outside the published package and +does not affect binary size. + +## 3. Workflows + +### 3.1 Nightly fuzz (`fuzz.yml`) + +Same branch selection as `bench.yml`: two crons, and the cron string that fired +picks the ref. + +```yaml +on: + schedule: + - cron: '0 4 * * *' # main + - cron: '0 16 * * *' # v3 + workflow_dispatch: + inputs: + ref: { default: v3 } + seconds: { default: '3300' } +env: + FUZZ_REF: +``` + +Jobs: + +1. **`targets`**: checks out `FUZZ_REF`, reads the `[[bin]]` names from + `fuzz/Cargo.toml`, and outputs them as a JSON matrix. Each branch fuzzes the + targets it has, so PR B's new targets join the v3 run without touching + `main`'s workflow. +2. **`fuzz`** (matrix over targets, `fail-fast: false`, in parallel): checks out + `FUZZ_REF`, restores the corpus cache, runs + `cargo fuzz run fuzz/corpus/ -- -max_total_time=$seconds`, saves the + cache (`if: always()`), and uploads `fuzz/artifacts/` plus the log as an + artifact if the run failed. Running in parallel cuts the wall time from ~5.5 h + to ~1 h; the repo is public, so the minutes are free. +3. **`report`** (`needs: fuzz`, `if: failure()`): downloads the failure + artifacts and comments on, or opens, the "Nightly fuzz failure" issue as + today, with the branch in the body. Then fails. + +**Corpus cache.** `actions/cache/restore` and `actions/cache/save`, key +`fuzz-corpus---`, restore key prefix +`fuzz-corpus---`. The newest run's corpus is restored and the run +saves a new entry. Committed seeds and the cached corpus share the directory; +libFuzzer reads both. GitHub evicts entries unused for 7 days and caps the repo at +10 GB. With nightly runs, older entries age out on their own. + +### 3.2 Weekly corpus minimization (`fuzz-corpus.yml`) + +Mondays, once per branch (same two-cron pattern, at 08:00 and 20:00), plus +`workflow_dispatch`. For each target in turn, in one job: + +1. Restore the newest corpus cache for `-`. +2. `cargo fuzz cmin fuzz/corpus/`. +3. Keep every `seed_*` file (regression seeds are never dropped), plus the + minimized files cmin kept. +4. Save the minimized corpus as a new cache entry, so the nightly run starts from + it. + +Then commit `fuzz/corpus/` to the branch `bot/fuzz-corpus-` (force-pushed) +and open a PR to `` with `gh pr create`, or update the open one. A corpus +file larger than 64 KiB is left out of the commit (stays in the cache only). + +Needs `contents: write` and `pull-requests: write`. **The repository setting +"Allow GitHub Actions to create and approve pull requests" is off today.** While +it is off, the job pushes the branch and prints a compare link in the job +summary instead of failing. PRs opened with `GITHUB_TOKEN` do not trigger CI. +That is fine for corpus-only changes, and a maintainer reviews and merges them. + +## 4. Page targets (PR A, #375) + +The fuzz crate sees only the public API. To reach a decoder behind a checksum, +a target builds a real file with the public API, overwrites one page with fuzzer +bytes, and recomputes that page's checksum itself (`crc32fast`; the layouts are +in `storage/page.rs` and `storage/meta.rs`, spec §4). The target never asserts +success: errors are expected, and only panics, hangs and OOMs count as findings. + +**Template.** Built once per process (`OnceLock`) in a temp dir: 90 entities +with a number, a name and a ref to the next entity, a long string (a value +page), a fact-level valid-time window, a keyword and a retraction. The draft is +then rewritten through `LogWriter` with fixed tx times (`10^12 + 1000 × +tx_count`). The bytes are then the same in every process, so seeds cut from them +are still valid when the target runs. `LogWriter` commits once (one batch): +every tree page is reachable from the meta page, and nothing is freed. 90 +entities give the four fact indexes two leaves and an internal root each, and +keep a full scan cheap. Generation 1 is in slot A and generation 2 in slot B. +Each run copies the template bytes to a fresh file. + +**One probe per run.** Under ASan, running all seven probe queries and +`verify()` on every input held the targets to ~8 executions/s. Instead, one +input byte picks one probe (`pick % 8`: seven queries that between them scan +EAVT, AEVT, AVET, VAET, the DICT, `:valid-at` and `:as-of`, or `verify()`). The +fuzzer varies that byte like any other. + +### 4.1 `btree_page` + +- Byte 0 picks the node: bit 7 picks an internal node (else a leaf), and bits + 0–6 pick which one. +- Byte 1: bit 0 flips the type byte between leaf and internal, bit 1 opens + read-only. Byte 2 picks the probe. +- The rest overwrites the node's `count` field (offset 2) and body (offset 24). + The page id and generation stay, and the page CRC is recomputed, so the page + passes the header check and reaches the node decoder. + +### 4.2 `fact_page` + +v7 fact pages are read only when a v7 file is opened. The target uses +`tests/golden/v7_basic.graph` as its template (`include_bytes!`), overwrites +fact page 1 with the input, and opens. Byte 0 bit 0 picks read-only (in-memory +load) or read-write (migration to v8). Then a full scan, a name query and +`verify()`. The v7 header checksum covers only the header. + +### 4.3 `file_header` + +Byte 0: bit 0 replaces slot B (else slot A); bit 1 writes the correct meta CRC +over the result, so the field checks (page count, roots, free list, feature +bits) are reached; bit 2 zeroes the other slot, so the fuzzed one is the only +candidate; bit 3 keeps the magic and version (bytes 0..16) and overwrites from +the generation field on; bit 4 opens read-only. Byte 1 picks the probe. The +rest overwrites the slot. + +### 4.4 Seeds + +Each target gets seeds that reach its decoder. `btree_page`: a valid leaf, the +same leaf opened read-only, two valid internal nodes, a leaf whose `count` +overruns its truncated slot directory, and a leaf with its type flipped to +internal. `fact_page`: the v7 fact page, read-only and read-write. +`file_header`: each slot's own meta page, slot B alone, and slot B's fields +only, read-only. A seed generator is not committed: seeds are cut from the +template with the input layout above. Stale seeds +built for the old layout (`seed_v7_3page.bin`, `seed_v5_large_page_count.bin`, +…) stay, since a seed costs little, and new ones are added next to them. + +**Acceptance (#375).** A run on the valid-leaf seed reaches leaf decoding and the +query returns the template's entries. A truncated-slot seed reaches the decoder +and gets an error. Both were checked once with a temporary trace in +`storage/node.rs` (not committed): the valid leaf and internal seeds return all +rows and `verify()` passes, while the truncated and type-flipped seeds decode +the fuzzed page and fail with INT-049. + +## 5. `ops_sequence` (PR B) + +A differential target: storage operations on a file-backed database, compared +with the reference model in `tests/reference_model/mod.rs` that #385 and #386 +use. + +- The fuzz crate includes the model with + `#[path = "../../tests/reference_model/mod.rs"] mod reference_model;` and adds + `proptest` and `uuid` as fuzz-crate dependencies. The check helpers of + `tests/model_based_test.rs` (`check_full_rows`, `check_shapes`, `check`) move + into the shared module so the target and the test use one copy. +- The input is decoded with `arbitrary::Unstructured` into at most 32 ops: + transact, retract, a write transaction (commit or rollback), checkpoint, + reopen (default, small cache, auto-checkpoint) and crash (open a copy of the + file and WAL). The pools and grid are the model's, so statements hit each + other often. +- After each op, it compares the full rows, now and at a fuzzer-chosen `:as-of`, + and one fuzzer-chosen query shape with the model. A statement the model + rejects must fail with the model's error code. A mismatch panics with the step + number and the query. The message carries pool indices, never a `Uuid`. +- Seeds: a few encoded op lists covering every op kind. + +The proptest test explores randomly; the fuzzer adds coverage guidance and a +persistent corpus. Both use the same oracle. + +## 6. `corrupt_file` (PR B) + +Opening a damaged file must return an error or correct data, never wrong data. + +- **Template** (once per process): a file built from fixed statements over + three checkpoints, with no WAL left. For each checkpoint generation, the + expected answers of a fixed set of queries are recorded. +- **Input:** up to 16 `(offset, xor)` edits (offset modulo file length, nonzero + xor) and an optional truncation to a page multiple or an arbitrary length. + Checksums are **not** recomputed: the CRCs are the contract under test. +- Open read-only or read-write (from one input byte), then run the fixed + queries. Each query must either 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). The whole open must match one generation, not a different + generation per query. A mismatch panics. +- `verify()` runs too. It may report problems or fail but must not panic. +- Seeds: no edits, a flip in each page type, and a truncation at the last page. + +Any finding gets a regression test in `tests/` and a seed, as for every fuzz +find. + +## 7. Out of scope + +- Fuzzing the browser or IndexedDB backend. +- Byte edits with recomputed CRCs. CRC32 does not protect against deliberate + forgery, and that is not part of the format's contract. +- WAL corruption beyond what `wal_entry` covers. diff --git a/fuzz/.gitignore b/fuzz/.gitignore index 89259bfe0a..0b0c39a826 100644 --- a/fuzz/.gitignore +++ b/fuzz/.gitignore @@ -1,2 +1,4 @@ +target/ artifacts/ coverage/ +Cargo.lock diff --git a/fuzz/Cargo.toml b/fuzz/Cargo.toml index 06c3320ab7..7eb259d8e6 100644 --- a/fuzz/Cargo.toml +++ b/fuzz/Cargo.toml @@ -13,6 +13,7 @@ cargo-fuzz = true libfuzzer-sys = "0.4" minigraf = { path = ".." } tempfile = "3" +crc32fast = "1" [[bin]] name = "wal_entry" diff --git a/fuzz/corpus/btree_page/seed_v8_internal.bin b/fuzz/corpus/btree_page/seed_v8_internal.bin new file mode 100644 index 0000000000..b51199c645 Binary files /dev/null and b/fuzz/corpus/btree_page/seed_v8_internal.bin differ diff --git a/fuzz/corpus/btree_page/seed_v8_internal_verify.bin b/fuzz/corpus/btree_page/seed_v8_internal_verify.bin new file mode 100644 index 0000000000..d86a282b8b Binary files /dev/null and b/fuzz/corpus/btree_page/seed_v8_internal_verify.bin differ diff --git a/fuzz/corpus/btree_page/seed_v8_leaf.bin b/fuzz/corpus/btree_page/seed_v8_leaf.bin new file mode 100644 index 0000000000..df8c9a19c4 Binary files /dev/null and b/fuzz/corpus/btree_page/seed_v8_leaf.bin differ diff --git a/fuzz/corpus/btree_page/seed_v8_leaf_as_internal.bin b/fuzz/corpus/btree_page/seed_v8_leaf_as_internal.bin new file mode 100644 index 0000000000..f183393232 Binary files /dev/null and b/fuzz/corpus/btree_page/seed_v8_leaf_as_internal.bin differ diff --git a/fuzz/corpus/btree_page/seed_v8_leaf_read_only.bin b/fuzz/corpus/btree_page/seed_v8_leaf_read_only.bin new file mode 100644 index 0000000000..614fc9eeba Binary files /dev/null and b/fuzz/corpus/btree_page/seed_v8_leaf_read_only.bin differ diff --git a/fuzz/corpus/btree_page/seed_v8_leaf_truncated.bin b/fuzz/corpus/btree_page/seed_v8_leaf_truncated.bin new file mode 100644 index 0000000000..4d7c663c29 Binary files /dev/null and b/fuzz/corpus/btree_page/seed_v8_leaf_truncated.bin differ diff --git a/fuzz/corpus/fact_page/seed_v7_basic_fact_page.bin b/fuzz/corpus/fact_page/seed_v7_basic_fact_page.bin new file mode 100644 index 0000000000..220714e32b Binary files /dev/null and b/fuzz/corpus/fact_page/seed_v7_basic_fact_page.bin differ diff --git a/fuzz/corpus/fact_page/seed_v7_basic_fact_page_read_only.bin b/fuzz/corpus/fact_page/seed_v7_basic_fact_page_read_only.bin new file mode 100644 index 0000000000..8a06e949e7 Binary files /dev/null and b/fuzz/corpus/fact_page/seed_v7_basic_fact_page_read_only.bin differ diff --git a/fuzz/corpus/file_header/seed_v8_meta_a.bin b/fuzz/corpus/file_header/seed_v8_meta_a.bin new file mode 100644 index 0000000000..c781a76168 Binary files /dev/null and b/fuzz/corpus/file_header/seed_v8_meta_a.bin differ diff --git a/fuzz/corpus/file_header/seed_v8_meta_b.bin b/fuzz/corpus/file_header/seed_v8_meta_b.bin new file mode 100644 index 0000000000..6f8f299df8 Binary files /dev/null and b/fuzz/corpus/file_header/seed_v8_meta_b.bin differ diff --git a/fuzz/corpus/file_header/seed_v8_meta_b_fields_read_only.bin b/fuzz/corpus/file_header/seed_v8_meta_b_fields_read_only.bin new file mode 100644 index 0000000000..8c93149ff8 Binary files /dev/null and b/fuzz/corpus/file_header/seed_v8_meta_b_fields_read_only.bin differ diff --git a/fuzz/corpus/file_header/seed_v8_meta_b_only.bin b/fuzz/corpus/file_header/seed_v8_meta_b_only.bin new file mode 100644 index 0000000000..c47752a12f Binary files /dev/null and b/fuzz/corpus/file_header/seed_v8_meta_b_only.bin differ diff --git a/fuzz/fuzz_targets/btree_page.rs b/fuzz/fuzz_targets/btree_page.rs index 5e9fe30279..eb68b13dfe 100644 --- a/fuzz/fuzz_targets/btree_page.rs +++ b/fuzz/fuzz_targets/btree_page.rs @@ -1,39 +1,49 @@ +//! Fuzz B+tree node decoding (leaf and internal, every tree) (#375). +//! +//! Input byte 0 picks the node: bit 7 an internal node (else a leaf), bits 0-6 +//! which one. Byte 1: bit 0 flips the type byte between leaf and internal, bit +//! 1 opens read-only. Byte 2 picks the probe (`common::probe`). The remaining +//! bytes overwrite the node's `count` field (offset 2) and body (offset 24). +//! The type, page id and generation stay, and the page CRC is recomputed, so +//! the page reaches the node decoder instead of failing the header check. #![no_main] use libfuzzer_sys::fuzz_target; +#[path = "common/mod.rs"] +mod common; +use common::*; + fuzz_target!(|data: &[u8]| { - let dir = match tempfile::tempdir() { - Ok(d) => d, - Err(_) => return, - }; - let path = dir.path().join("fuzz.graph"); - let mut content = vec![0u8; 4096 * 3]; - content[0..4].copy_from_slice(b"MGRF"); - // v8 header (v1-v6 are rejected; v7 would always force a full rebuild - // from fact pages and never touch the root page below, which is a - // different code path than the one this target means to fuzz). - content[4..8].copy_from_slice(&8u32.to_le_bytes()); - // page_count = 3 (header page 0, unused page 1, fuzzed root page 2). - content[8..16].copy_from_slice(&3u64.to_le_bytes()); - // eavt_root_page = 2: points `load()`'s index wiring, and the query - // below, at the fuzzed page as the EAVT B+tree root. fact_page_count is - // left at 0, so `load()` takes the "no facts, trust the root" branch - // and does not force a rebuild that would ignore this page. - content[32..40].copy_from_slice(&2u64.to_le_bytes()); - // header_checksum (bytes 80-83) and index_checksum (bytes 64-67) are left - // zero: zero is the "unset" sentinel that skips checksum verification. - let copy_len = data.len().min(4096); - content[4096 * 2..4096 * 2 + copy_len].copy_from_slice(&data[..copy_len]); - if std::fs::write(&path, &content).is_err() { + let [sel, flags, pick, rest @ ..] = data else { return; + }; + let t = template(); + let pages = if sel & 0x80 != 0 { + &t.internals + } else { + &t.leaves + }; + let id = pages[usize::from(sel & 0x7f) % pages.len()]; + + let mut bytes = t.bytes.clone(); + let page = page_mut(&mut bytes, id); + if flags & 0x01 != 0 { + page[0] = if page[0] == PAGE_TYPE_LEAF { + PAGE_TYPE_INTERNAL + } else { + PAGE_TYPE_LEAF + }; } - let Ok(db) = minigraf::db::Minigraf::open(&path) else { + let (count, body) = rest.split_at(rest.len().min(2)); + page[2..2 + count.len()].copy_from_slice(count); + let n = body.len().min(PAGE_SIZE - 24); + page[24..24 + n].copy_from_slice(&body[..n]); + fix_page_crc(page); + + let Ok(dir) = tempfile::tempdir() else { return; }; - // `open()` alone only wires up `OnDiskIndexReader` against the root page — - // it never reads it. Run an entity-bound query so the EAVT range scan - // actually decodes the fuzzed page as a v8 B+tree leaf/internal node. - let _ = db.execute( - r#"(query [:find ?a ?v :where [#uuid "00000000-0000-0000-0000-000000000000" ?a ?v]])"#, - ); + if let Some(db) = write_and_open(dir.path(), &bytes, flags & 0x02 != 0) { + probe(&db, *pick); + } }); diff --git a/fuzz/fuzz_targets/common/mod.rs b/fuzz/fuzz_targets/common/mod.rs new file mode 100644 index 0000000000..c2262603db --- /dev/null +++ b/fuzz/fuzz_targets/common/mod.rs @@ -0,0 +1,170 @@ +//! Shared by the page targets: a real format v8 file built through the public +//! API, page lookups by type, checksum fix-ups, and the probe queries. +//! +//! The fuzz crate only sees the public API, so a target that wants to reach a +//! decoder behind a checksum builds a valid file, overwrites one page with +//! fuzzer bytes, and recomputes that page's checksum itself. The layouts are in +//! `src/storage/page.rs` and `src/storage/meta.rs` (v8 spec §4). +#![allow(dead_code)] + +use minigraf::{FactFilter, LogWriter, Minigraf, OpenOptions}; +use std::path::Path; +use std::sync::OnceLock; + +pub const PAGE_SIZE: usize = 4096; + +pub const PAGE_TYPE_VALUE: u8 = 0x51; +pub const PAGE_TYPE_LEAF: u8 = 0x61; +pub const PAGE_TYPE_INTERNAL: u8 = 0x62; +pub const PAGE_TYPE_FREELIST: u8 = 0x81; + +/// CRC field of a non-meta page (common page header) and of a meta page. +const PAGE_CRC: std::ops::Range = 4..8; +const META_CRC: std::ops::Range = 12..16; + +/// A file written by one checkpoint, with no WAL left. Every tree page is +/// reachable from the meta page (one checkpoint frees nothing), and the trees +/// are big enough to have internal nodes. +pub struct Template { + pub bytes: Vec, + /// Page ids by type, from the page headers. + pub leaves: Vec, + pub internals: Vec, + pub values: Vec, +} + +pub fn template() -> &'static Template { + static T: OnceLock