Skip to content

Limit postprocess heuristics fuzz input size#2644

Merged
Sebastian Thiel (Byron) merged 2 commits into
mainfrom
fix-postprocess-timeout
Jun 16, 2026
Merged

Limit postprocess heuristics fuzz input size#2644
Sebastian Thiel (Byron) merged 2 commits into
mainfrom
fix-postprocess-timeout

Conversation

@Byron

@Byron Sebastian Thiel (Byron) commented Jun 15, 2026

Copy link
Copy Markdown
Member

Tasks

  • refackiew

Created by Codex on behalf of Byron. Byron will review before this is ready to merge.

Summary

Limit the gix-imara-diff postprocess_heuristics fuzz target to inputs whose parsed before and after strings are at most 128 KiB in total. The guard is fuzz-target-local and contained in fuzz_targets/postprocess_heuristics.rs, so the public diff API still handles large inputs normally.

Reported issue

Plain-text report from the session:

There is a fuzzer timeout in the gix-imara-diff post-process heuristics. The reproducer is pretty hefty clusterfuzz-testcase-minimized-gix-imara-diff-postprocess_heuristics-4774375640072192, and it's 'too slow' measured in 100 runs over 60 seconds.

It seems best to fix it by limitting the input size, after all the input document that causes this is huge measured in what people typically diff, with the timing being not slow on the individual run.

Take a quick look at possible performance improvements, the algorithm seems to be very recursive as well.

Original Stacktrace on revision eac50e1207e2549b23302c9faf595a420b9919fc:
- libFuzzer timeout after 61 seconds while running the minimized postprocess_heuristics testcase 100 times.
- The stack is in Myers diff computation before post-processing, with repeated gix_imara_diff::myers::Myers::run frames at gix-imara-diff/src/myers.rs:94.
- The call path reaches the fuzz target through Diff::compute -> postprocess_heuristics::do_fuzz.

Notes

Local measurements:

  • Before the guard, the reproducer took about 13.8 seconds for a single release-mode fuzzer run locally.
  • After the guard, the reported 100-run fuzzer command completed the reproducer in 25 ms.

Validation

  • cargo +nightly fuzz run --fuzz-dir gix-imara-diff/fuzz postprocess_heuristics ../clusterfuzz-testcase-minimized-gix-imara-diff-postprocess_heuristics-4774375640072192 -- -runs=100
  • cargo test --manifest-path gix-imara-diff/fuzz/Cargo.toml
  • cargo test -p gix-imara-diff
  • codex review --commit e8170f92363380c16e9f028564709dfad1720a0b

A ClusterFuzz testcase for the postprocess_heuristics target spent about 13.8
seconds in a single release-mode fuzzer run locally. The timeout happens while
computing the diff for an unusually large input, before the post-processing
heuristics run.

Skip fuzz inputs whose parsed before/after strings exceed 128 KiB in total. This
keeps the guard fuzz-target-local so the public diff API continues to handle
large inputs without silently producing partial results, while preventing the
reported oversized testcase from consuming the target budget.

Co-authored-by: Sebastian Thiel <[email protected]>
@Byron
Sebastian Thiel (Byron) marked this pull request as ready for review June 16, 2026 02:12
Copilot AI review requested due to automatic review settings June 16, 2026 02:12
@Byron

Copy link
Copy Markdown
Member Author

And it's clear that this fuzzer input is stress for Myers, not for post-processing in general.


Yes, but my read is: the report is more a Myers stress case than a post-processing stress case.

Key signals:

  • The timeout stack is in myers::middle_snake and repeated Myers::run, not in postprocess.rs.
  • The fuzz target amplifies cost heavily: for each input it computes Histogram and Myers, and for each algorithm it recomputes the diff three times for three post-processing modes. That is six full diff computations per fuzz iteration.
  • Histogram can fall back to Myers, so bad inputs can effectively hit the Myers path more than the target name suggests.
  • Post-processing has bounded local heuristics: indent sliding checks at most 100 positions, and blank-line context scans cap at 20. That can still add overhead on many hunks, but it does not look like the source of the deep recursive stack or the main timeout.

There may be real optimization opportunities, but I would separate them:

  1. Myers performance/depth: the recursive divide-and-conquer can get very deep with unlucky split shapes. The current implementation recurses into the low half and iterates over the high half, so it avoids one side of recursion, but still has bad-depth cases if splits are repeatedly skewed.

  2. Post-processing overhead: IndentHeuristic recomputes indentation repeatedly through the callback. A practical improvement would be caching IndentLevel per token for a postprocess run, especially for large inputs or many movable hunks.

  3. Fuzz-target realism: the target is intentionally expensive because it recomputes rather than cloning/reusing one diff. That is okay for coverage, but it makes the 100-runs/60s timeout a poor proxy for real user-facing “postprocess is slow.”

So: I would not conclude that post-processing is broadly too slow from this reproducer. I would conclude that huge, adversarial, repetitive inputs can make the full diff pipeline expensive, and the fuzzer target multiplies that cost. If we wanted a follow-up performance patch, I’d look first at indent-level caching and maybe a Myers recursion-depth guard or explicit work stack.

Copilot AI left a comment

Copy link
Copy Markdown

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Pull request overview

Limits the gix-imara-diff postprocess_heuristics fuzz target to avoid pathological slow inputs by skipping cases where the combined before/after input size exceeds 128 KiB, improving fuzzer runtime stability without changing the library’s behavior for real consumers.

Changes:

  • Add a fuzz-target-local MAX_INPUT_BYTES guard that early-returns when before.len() + after.len() exceeds 128 KiB.
  • Minor formatting tweak to the IndentLevel::for_ascii_line(...) call site.

💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.

Comment thread gix-imara-diff/fuzz/fuzz_targets/postprocess_heuristics.rs Outdated
@Byron
Sebastian Thiel (Byron) merged commit 8f55e18 into main Jun 16, 2026
55 of 58 checks passed
@Byron
Sebastian Thiel (Byron) deleted the fix-postprocess-timeout branch June 16, 2026 03:08
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants