FSTCompiler writes a corrupt FST when a node would expand to 2^31 bytes or more

FSTCompiler computes the padded size of a node with fixed-length arcs as a Java int. When one node has many arcs and one large output, the size reaches 2^31 and wraps; with assertions off the compiler skips the padding but still writes the header that claims it. compile() returns normally, lookups through that node throw, and enumeration can return a key that was never added. Silent in most releases since 4.2.0 (2013). This is about FSTs that applications build; the default index format on main does not use util.fst.

• An FST (finite state transducer) is Lucene's compact map from keys to values. A key is a sequence of integer labels (bytes BYTE1, 16-bit chars BYTE2, or ints BYTE4); the values are outputs. The FST is a graph of nodes, and each arc leaving a node carries one label. FSTCompiler builds it from sorted keys; Util.get, FSTEnum and the arc readers in FST read it.
• FSTCompiler writes each node in two passes. Pass 1 writes the arcs back to back, each only as long as it needs (flags, label, output, target): a list node that a reader scans from the start. Pass 2 runs for nodes that qualify for fixed-length arcs (depth at most 3 with at least 5 arcs, or at least 10 arcs at any depth; on by default): it pads every arc to the size of the largest one, maxBytesPerArc, so a reader can jump to arc i and binary search the labels. A small header in front says "binary-search node, numArcs arcs, maxBytesPerArc bytes each".

The padded size is computed as an int: numArcs * maxBytesPerArc (main FSTCompiler.java:665, int destPos = headerLen + nodeIn.numArcs * maxBytesPerArc;). If one arc is big and the node has many arcs, the product reaches 2^31 and wraps. In the binary-search writer the end position destPos then comes out too small, the guard if (destPos > srcPos) (:667) is false, so the arcs are not padded, and the header is written anyway (:695) over the first 6 bytes of arc 0.

The line before the guard, assert destPos >= srcPos (:666), catches it only with assertions on (-ea), while the FST is built. Java runs with assertions off unless told otherwise. Under -da, compile() returns normally and the FST holds the unpadded list plus a header that claims padding:

• every Util.get under that node throws (IndexOutOfBoundsException or ArrayIndexOutOfBoundsException on heap, IllegalArgumentException: read negative position through MMapDirectory);
• enumeration (IntsRefFSTEnum.next()) can return a key that was never added, because it decodes the big output's own bytes as an arc (it depends on those bytes and the shape);
• FST.save() writes the bad bytes as they are, so the corruption survives a save and reload.

BYTE2, ByteSequenceOutputs, 2,048 sparse root arcs (labels 0, 32, ..., 65,504), arc 0 with a 1,048,570-byte output: arc 0 is 1 + 2 + 3 + 1,048,570 = 2^20 bytes, so 2048 * 1048576 = 2^31, which is -2,147,483,648 as an int. destPos = 6 + (-2,147,483,648) = -2,147,483,642, below srcPos = 1,058,811, so no expansion happens. Util.get(key 32) then probes arc 1,023 about 1 GB before the start of a 1 MB FST, which on heap is block -32,704: Index -32704 out of bounds for length 33.

With allowFixedLengthArcs(false) the same keys build and read back correctly. With a 1,048,569-byte output (product 2,147,481,600) the compiler builds a correct 2,147,481,607-byte FST and all 2,048 lookups are right; one byte more gives a 1,058,812-byte FST on which every lookup throws. The failure is a cliff, not a limit.

• Who could hit it. Applications that build their own FST<BytesRef> or FST<CharsRef> maps with a wide node and one large output; #9132 (LUCENE-8084) describes that data shape ("one of the outputs is very long, all the others are small", "root level fanout is huge") but reports only wasted space. One in-tree public API is silent at build time: StemmerOverrideFilter.Builder with 2,048 one-code-point words and one 1,048,570-char stem builds, then every lookup throws. There is no field report.
• Not the default index format. On main and branch_10_6 no core codec imports util.fst (the default codec is Lucene104). Releases before 10.3 built the default terms index with FSTCompiler, as BYTE1 FSTs with small outputs; no way to reach this bug through them is known.
• Silent where it matters. Production runs with assertions off, so compile() succeeds and the damage shows only on read. In a deep node other keys keep working and the corruption stays hidden until a key under that node is read (301 of 301 other keys correct, 4,096 of 4,096 under the bad node throw, in one repro).
• Shape. It needs the binary-search layout, which the compiler picks for sparse labels: for BYTE2, at most 4,096 sparse arcs and one arc of at least 512 KiB; for BYTE1, at most about 33 arcs and one arc of 62-64 MiB or more; for BYTE4, for example 1,048,576 arcs at stride 1024 and one arc of 2 KiB. Contiguous label sets get other layouts and fail loudly (out of memory or ArrayIndexOutOfBoundsException, tried at -Xmx2g and -Xmx8g, not with larger heaps).
• Reach is very low (registry: data corruption, opt-in shape, extreme scale). Workaround: allowFixedLengthArcs(false).

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError
       org.apache.lucene.util.fst.FSTCompiler.writeNodeForBinarySearch(FSTCompiler.java:666)
       org.apache.lucene.util.fst.FSTCompiler.addNode(FSTCompiler.java:553)
       org.apache.lucene.util.fst.FSTSuffixNodeCache.add(FSTSuffixNodeCache.java:154)
       org.apache.lucene.util.fst.FSTCompiler.compileNode(FSTCompiler.java:388)
       org.apache.lucene.util.fst.FSTCompiler.compile(FSTCompiler.java:1014)
       org.apache.lucene.util.fst.TestFSTNodeExpandedSizeOverflow.testRootNodeOf2048ArcsWithOneMiBArc(TestFSTNodeExpandedSizeOverflow.java:33)

• The writer's own assertion states the invariant that breaks: assert destPos >= srcPos.
• No size limit is documented, and the FSTCompiler class javadoc advertises "FSTs larger than 2.1GB are now possible (as of Lucene 4.2)".
• Fixed-length arcs are documented as an optimization: "Pass false to disable the fixed length arc optimization ... smaller but slower to traverse". An optimization that changes the result is a bug by the API's own description, and with the optimization off the same input is correct.
• It is a cliff: one byte less builds a correct 2 GB FST.
• Precedent: FST size overflows were fixed as bugs before, for example #5804 / LUCENE-4739 (type:bug, "FSTs more than ~1.1GB" could not be saved and loaded) and #5146 / LUCENE-4074 (type:bug, an int overflow in the FST sorter).

The intended-behaviour checker argued every point for "not a bug": the classes are @lucene.experimental (but that means the API may change, not that output may be corrupt); #12624's review assumed single nodes are small (those comments are about shrinking a scratch buffer, and 105 review comments, 20 conversation comments and 61 reviews never mention overflow, destPos or a (long) cast); an assert guards it (FSTCompiler checks caller contracts with asserts, but this one is an internal invariant that legal input breaks, and about 25% of main's test seeds run with assertions off); it is a pathological shape and a known space limitation (#5747, #9132 are about wasted space only); the format cannot hold a 2 GiB fixed-length node (true, but the input does not need one: the list encoding is 1 MB); and nobody has hit it in about 13 years (that speaks to reach, not intent).

Verdict: not intended. Not documented, not an unsupported configuration, and no documented limit is exceeded; a real correctness bug with very low practical reach. Not a security issue: SECURITY.md says reports that feed arbitrary data into low-level APIs are generally not vulnerabilities but "are still valid bug reports", so a public issue is right.

The checks validated keeping oversized nodes as lists; the alternatives come from the brief and the fix README.

Local branch fix-fst-expanded-size-overflow, commit 13e3e5e3f5 on main b4383f066b (3 files, +37/-2). A node whose fixed-length arc area would be larger than 1 GiB keeps the variable-length list that pass 1 already wrote, which is a valid encoding. It uses the hook the commented-out LUCENE-4682 heuristic already reserves, one guard before all three fixed-length writers (continuous, direct addressing, binary search), with no reader or format change. The cap also keeps the other size products and the reader's bytesPerArc * mid in int range.

private static final int FIXED_LENGTH_ARC_MAX_NODE_BYTES = 1 << 30;
...
// if the expanded node would be too large, keep the variable length arcs written above
if (doFixedLengthArcs
    && (long) nodeIn.numArcs * maxBytesPerArc <= FIXED_LENGTH_ARC_MAX_NODE_BYTES) {

Trade-offs

• A node whose arc area is between 1 GiB and 2 GiB used to be expanded correctly; now it stays a list, so lookups there are a linear scan (slower, but it saves at least 1 GiB of build heap).
• Nodes over the cap keep pass-1 arcs without BIT_TARGET_NEXT: valid, slightly larger than a pure list. Output is byte-identical whenever the arc area is at most 2^30.
• The CHANGES entry sits under 10.7.0 with GITHUB#TBD placeholders, which is probably stale (10.6 is expected to be the last 10.x); let the committer choose. The commit was written by an AI tool.

What the checks validated

• The fix hunk applies cleanly to main and to branch_10_6; the test passes 5/5 with -ea and 5/5 with -da on both.
• org.apache.lucene.util.fst.*: 38 tests, 0 failures; :lucene:core:check -x test and error-prone pass on main.
• All probes and repros are correct on the fixed jars, including shapes that used to fail loudly. Boundary: at exactly 2^30 the node still expands (1,073,741,831 bytes, 2048/2048 correct); one byte more per arc keeps a 534,525-byte list (2048/2048 correct).

Compute the product as a long again, as 9.4.2 did.

Trade-offs

Not enough on its own: the scratch buffer is a byte[], so the bug only turns into another exception; 9.4.2-9.8.0 also show that a 2 GB node hit a second truncation.

Fail loudly in the compiler.

Trade-offs

Loud, but it rejects input that has a valid encoding (the list).

Use the largest size the scratch array can hold as the cap.

Trade-offs

More code and little headroom.

Decide fixed-length arcs by wasted space, as those issues propose.

Trade-offs

A format-affecting design change, out of scope for this bug.

Method: SMT (Z3) on the transcribed size arithmetic of FSTCompiler, then a concrete witness on the real jar (the study's "formal" tier). Run 3, experiment "fst-verification" (2026-10-22, main 7cecf79523).

• The task targeted util/fst, named FSTCompiler, the binary-search, direct and continuous arc encodings, fixed-length arcs and their thresholds, and asked for Alloy/Dafny models and bounded-exhaustive checks; the shared preamble named SMT (Z3/cvc5, bit-vector and floating-point theories) as a general technique. It said nothing about size arithmetic.
• while modelling a different finding, the AI tool transcribed the encoding-decision arithmetic into a Z3 bit-vector and floating-point model that contains int sizeForBinarySearch.
• 06:10: a Java probe for "expanded size exceeds 2^31" gave only loud failures. 06:11: the AI tool wrote smt/expand_overflow.py, whose query Q6 encodes the silent path: binary search chosen, destPos <= srcPos, expansion skipped, header still written.
• 06:36: after bounding srcPos correctly, Z3 reported Q6d satisfiable (default factor, credit 0) for 5, 10 and 64 arcs; the final log (06:47) has it unsatisfiable for 200 and 255 arcs within a 512 MB first-pass bound, where direct addressing is chosen instead.
• 06:37: a concrete re-execution of the same arithmetic picked a witness (64 arcs, one 33,554,427-byte output). On the real jar under -da it compiled and the lookups threw: the first observation of the silent corruption. 06:38: a JUnit repro.
• The experiment's bounded-exhaustive harness (7.0M FSTs, no discrepancy) cannot reach nodes of 2^31 bytes. A separate AI verifier wrote its own tests and ran 9.3.0, 9.4.2 and 9.9.2.

So the AI tool formed the mechanism while reading and modelling the code, Z3 showed the silent branch is reachable with default settings, and a concrete scan picked the sizes. Not "blind".