Formal models and scripts: study-fst-verification

Tools: Alloy, Dafny, Python

These are the working models and scripts this part of the hunt used. Some encode the code as it is (a counterexample is the expected result), others a fixed or correct variant; read the header comment of each file. Paths inside them were replaced by placeholders such as $LUCENE (a Lucene checkout) and $WORK.

Findings

• FSTMetadata.save always writes the current version, so re-saving a pre-9.0 BYTE2 FST breaks its lookups (finding LFV-052; repro · finding page)
• FSTCompiler silently writes a corrupt FST when a fixed-length-arc node would expand to 2^31 bytes or more (finding LFV-007; repro · finding page)
• Util.shortestPaths with topN=0 throws NoSuchElementException (finding LFV-070; repro · finding page)
• FSTCompiler throws ArrayIndexOutOfBoundsException on BYTE4 nodes whose labels span 2^31-8 or more (finding LFV-067; repro · finding page)

Files

• alloy/fst_arcs.als
• bin/matrix_table.py
• dafny/BitTable.dfy
• dafny/mut/BitTable_mutant_prev.dfy
• smt/da_decision.py
• smt/expand_overflow.py
• smt/scan_expand.py

How to run

• Alloy 6: open the .als file and run its commands (a counterexample found for one of its assertions is the finding).
• Dafny: dafny verify <file>.dfy (a failed obligation marks where the code's contract breaks).
• Python: python3 <file>.py; scripts that import z3 need the z3-solver package.

Snapshot of 2026-11-04. AI-assisted; not yet triaged by a human Lucene committer. Feedback: open an issue in lucene-ai-bug-hunt.