UTF32ToUTF8 still accepts overlong UTF-8 for ranges that span into 3- and 4-byte code points

UTF32ToUTF8 converts a code-point automaton into the byte automaton that RegexpQuery, WildcardQuery, AutomatonQuery and ByteRunAutomaton run against indexed terms, and promises an "equivalent UTF-8 representation". For a code-point range that starts below U+0800 and ends at or above U+1000, the byte automaton also accepts the 2,048 overlong 3-byte sequences E0 80..9F xx; for a range that starts below U+10000 and ends at or above U+40000, also the 65,536 overlong 4-byte sequences F0 80..8F xx xx. makeAnyChar(), the regexp ., the wildcard ? and negated classes such as [^/] are such ranges. Valid UTF-8 terms are not affected, but binary terms that are not UTF-8 are matched by Unicode queries that should reject them: next to the term a, the binary term E0 80 80 makes RegexpQuery("."), WildcardQuery("?") and an AutomatonQuery for [U+0001, U+10FFFF] each count 2 documents instead of 1. #12458 reported this bug class in 2023 and its fix #12472 (9.8.0) handled only ranges whose last code point has lead byte exactly E0 or F0; the rest has been there since the class was written in 2010 (LUCENE-2265, first released in 4.0.0-ALPHA).

• UTF-8 lengths: U+0000..U+007F take 1 byte, U+0080..U+07FF 2, U+0800..U+FFFF 3 (lead byte E0..EF), U+10000..U+10FFFF 4 (lead byte F0..F4). Each further byte is a continuation byte 80..BF.
• Overlong sequence: a longer spelling of a code point that has a shorter one. UTF-8 forbids them, so each Unicode scalar value (every code point except the surrogates U+D800..U+DFFF) has exactly one encoding. That is why the byte after E0 must be A0..BF (E0 80 80 would be U+0000; the first real 3-byte code point U+0800 is E0 A0 80) and the byte after F0 must be 90..BF (U+10000 is F0 90 80 80). For 2 bytes the same rule makes C0 and C1 illegal lead bytes.
• UTF32ToUTF8: converts each code-point range of an automaton into byte transitions. CompiledAutomaton (:237) and ByteRunAutomaton (:45) use it, so RegexpQuery, WildcardQuery and AutomatonQuery (default isBinary = false) run its output against the term dictionary.

1. When the two ends of a range have different UTF-8 lengths, build() takes its last branch (195-212): start() for the lower end, a middle loop for each whole length class in between (200-208), and end() for the upper end (211).
2. all() (268-282) emits "a lead byte in a range, then left continuation bytes 80..BF" (lines 276, 280). It never narrows the byte after E0 or F0.
3. The middle loop calls all(E0, EF, 2) for the whole 3-byte class (when lo < U+0800 and hi >= U+10000), which includes E0 80..9F xx. The 2-byte class starts at C2 (startCodes, line 34), so C0/C1 stay out.
4. end() at upto == 0 covers the lead bytes below the upper end's lead byte from startCode = lead & ~mask (257), which is E0 or F0, through all(...) (259-261). This runs when the upper end's lead byte is E1..EF (hi >= U+1000) or F1..F4 (hi >= U+40000).
5. The two special cases #12472 added (248-255) apply only at upto == 1 and only when the upper end's lead byte is exactly E0 (second byte from A0) or F0 (from 90). The 2-byte case beside them (243-247) asserts upto == 0 and starts the lead byte at C2; it is the 2010 special case, rewritten by #12472 with the same effect.

For [U+007F, U+1000] (7F to E1 80 80): start gives 7F; the middle loop gives C2..DF 80..BF; end computes startCode = E1 & ~0F = E0 and emits all(E0, E0, 2) = E0 80..BF 80..BF, of which only E0 A0..BF 80..BF is real UTF-8, so 32 x 64 = 2,048 overlong strings get in; then E1 80 80. For [U+007F, U+0FFF] the upper end is E0 BF BF, step 4 emits nothing and the E0 special case applies: exact.

makeAnyChar() = [U+0000, U+10FFFF] hits both sources (the middle loop's E0 box and end()'s all(F0, F3, 3)), and so do the regexp . (RegExp.java:1447), the wildcard ? (WildcardQuery.java:83) and negated classes, which are makeAnyChar() minus the excluded characters (RegExp.java:1302): [^/]* accepts 61 E0 80 AF 62, which Lucene's lenient decoder turns into a/b.

For one range [lo, hi], the byte language is exactly the shortest-form encodings of lo..hi, plus the box E0 80..9F 80..BF iff lo < U+0800 and hi >= U+1000, plus the box F0 80..8F 80..BF 80..BF iff lo < U+10000 and hi >= U+40000, and nothing else. (Under Lucene's convention, shared by the study's oracle, a surrogate code point in the range counts with its mechanical encoding ED A0..BF xx; RFC 3629 does not allow those either, but they are not overlong.) Checked by the study verifier on 828 ranges (all 259.8M canonical encodings plus an exact count of accepted strings); re-run here with the study's exact checker on all 9,472,128 ranges with ends below U+1100 (524,288 bad = 2,048 x 256) and on 262,177 enumerated whole automata (176,200 differ from a reference encoder). JBMC on a verbatim extraction (the extracted code, checked equal to the real class on 8,000,000 pairs; accepted strings of up to 4 bytes): complete for all ranges, proved sound for same-length ranges and 1->2 bytes, and a counterexample in each of the length classes (1,3), (1,4), (2,3), (2,4) and (3,4). Not every range in those classes is unsound: a 2->3-byte range with hi < U+1000 is exact, as the conditions above say.

Valid UTF-8 is safe: a valid term never has 80..9F after E0 or 80..8F after F0, and the automaton is built one code point per edge, so a valid term only goes through shortest-form pieces (reasoning, backed by the single-range checks). The surrogate block ED A0..BF xx is also accepted for makeAnyChar(), but those are the encodings of U+D800..U+DFFF, which are in the range: not part of this report.

• Who is exposed. Applications that index non-UTF-8 terms through a binary route, such as StringField(String, BytesRef, Store) (StringField.java:69-79; the route that was run), KeywordField(String, BytesRef, Store) (KeywordField.java:78), a token stream with a BytesTermAttribute (TermToBytesRefAttribute.java:46-48), a custom IndexableField, or segments holding such terms copied in with addIndexes, and query the same field with RegexpQuery, WildcardQuery, AutomatonQuery with the default isBinary = false, or anything else that compiles a code-point automaton (CompiledAutomaton.java:236-237, ByteRunAutomaton.java:27-29). Lucene expects such terms: "it can be provided with a binary (not necessarily UTF8!) term" (CompiledAutomaton.java:231-233).
• Not exposed. Terms indexed from Java strings: Lucene's encoder always writes valid UTF-8 and replaces unpaired surrogates with EF BF BD (UnicodeUtil.java:172-176, :233). TermQuery, which builds no automaton and seeks the exact term bytes (TermQuery.java:141, 212-213). PrefixQuery and TermRangeQuery, which use binary automata (PrefixQuery.java:40, TermRangeQuery.java:88-92).
• Reachable in the source, not run end to end: FuzzyQuery (FuzzyAutomatonBuilder.java:63, 73 use the 3-argument CompiledAutomaton constructor, which passes isBinary = false, CompiledAutomaton.java:142-143), Intervals.wildcard and Intervals.regexp (Intervals.java:206, 239), SpanMultiTermQueryWrapper (rewrites through the wrapped query, SpanMultiTermQueryWrapper.java:120-121), and the doc-values rewrite, which runs the query's compiled automaton on doc-values terms (DocValuesRewriteMethod.java:98-99). Whether each can match an overlong term depends on the automaton it builds.
• Direct convert() callers get an automaton with too many strings (6,018 for the 3,970 code points of [U+007F, U+1000]). FuzzySuggester and FuzzyCompletionQuery call it directly but intersect it with suggestions built by the analyzer, so no wrong suggestion is expected when those terms are valid UTF-8 (reasoning; their tests pass with and without the fix). An analyzer that emits binary terms was not analysed.
• No setting needed, and silent. Once the prerequisite exists (non-UTF-8 terms in a field that also gets Unicode queries, itself uncommon), no setting is involved, a one-character pattern triggers it, and nothing fails: the query just matches extra terms. In exclusion patterns the extra term is the one the filter meant to exclude ([^/]* accepts the overlong / in 61 E0 80 AF 62).
• How likely. Low. A Unicode pattern can reach the overlong bytes only if the rest of the term is valid UTF-8, and random binary keys almost never are. Java's modified UTF-8 (C0 80 for U+0000) and CESU-8 (ED .. surrogate pairs) do not produce these bytes. The #12472 CHANGES entry calls the scenario "extremely rare" (lucene/CHANGES.txt:3425-3427). "Low" is a judgement; prevalence was not measured.
• Inconsistent. Ranges one code point apart differ ([U+007F, U+0FFF] is exact, [U+007F, U+1000] is not), and 2-byte overlongs (C0 80) are rejected while 3- and 4-byte ones are accepted.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected [U+0000, U+1000] to reject E0 80 80, but it accepted
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.assertTrue(Assert.java:42)
       org.junit.Assert.assertFalse(Assert.java:65)
       org.apache.lucene.util.automaton.TestUTF32ToUTF8Overlong.testRangeFromOneToThreeBytesRejectsOverlong(TestUTF32ToUTF8Overlong.java:27)

• Contract. UTF32ToUTF8.java:27: "Converts UTF-32 automata to the equivalent UTF-8 representation." :287: "Converts an incoming utf32 automaton to an equivalent utf8 one." Automata.java:104: makeAnyChar() "accepts any single codepoint"; :137-138: makeCharRange "accepts a single codepoint whose value is in the given interval (including both end points)".
• #12458 (gsmiller, 2023-07-24, type:bug): "This happens when a transition in the input automaton contains a code-point range that spans different UTF8 byte counts"; its example was U+FFFF/U+10000 accepting F0 80..8F xx xx. mikemccand replied: "This likely also occurs for the other UTF-8 byte transitions (1->2, 2->3, 3->4, 1->3, etc.)", and quoted the build() middle loop that still emits one of the boxes.
• #12472 (tang-hi; ec1367862d0, 9.x 20748b7a505, first released in 9.8.0) is under "Bug Fixes" (lucene/CHANGES.txt:3409, 3425-3427). Its regression test TestUnicodeUtil#testUTF8SpanMultipleBytes (:195-220) asserts the exact string count (6) for the adjacent pairs [U+007F, U+0080], [U+07FF, U+0800], [U+FFFF, U+10000] only.
• Tests cannot see it today. TestUTF32ToUTF8.testRandomRanges does test ranges that span lengths (both ends from all four length buckets, TestUTF32ToUTF8.java:121-163), but it only feeds shortest-form encodings (matches(), :41-46), so it cannot see extra accepted strings; no test feeds such a range overlong bytes or counts its strings, except the #12472 test for the three adjacent pairs.
• Stated intent elsewhere. In review of the open PR #13072 its author wrote that after UTF32ToUTF8 "transitions intentionally have gaps for illegal UTF-8 byte sequences".

The strongest case for "not a bug": (1) ByteRunAutomaton is "Automaton representation for matching UTF-8 byte[]" (ByteRunAutomaton.java:19) and BytesRef.utf8ToString() "May throw ... if the data is not well-formed UTF-8" (BytesRef.java:134-135), so overlong input is outside the documented domain. (2) The 2010 code knowingly allowed the extra edges: "special case -- avoid created unused edges (utf8 doesn't accept certain byte sequences) -- there are other cases we could optimize too", and the Python prototype in the tree lists extra paths under "could be more minimal" (UTF32ToUTF8.py:23-26). (3) In the #12472 review mikemccand wrote: "Net/net I don't think this will impact any users ... users who index binary content would search it with binary terms (not via conversion from Unicode, where this bug lurks) unless they had a truly exotic use case." (4) The fix makes automata bigger, and terms that are valid UTF-8 are never mis-matched today. (5) For total automata such as .*, CompiledAutomaton already matches every term, UTF-8 or not (type ALL, CompiledAutomaton.java:179-199, 352-353). (6) UTF32ToUTF8 is @lucene.internal; AutomatonQuery and CompiledAutomaton are @lucene.experimental. (7) #12458 was closed after #12472, which could be read as upstream accepting what was left.

Why it fails: the conversion's own output is not equivalent to its input (6,018 strings for 3,970 code points), found by enumerating its output, without indexing or matching any invalid input, which is what #12472's regression test checks. Upstream filed and fixed the same symptom as a bug, and a committer expected the other transitions to be affected. In the #12472 review mikemccand asked whether "there are other cases we could optimize too" was "still true" and asked for "the three-to-four and one-to-two cases" in the test; the comment was then deleted and no leftover case was named. The discussion contains no explicit decision about the leftover cases; #12458 closed as completed when #12472 merged, after the reviewer called the fix "fundamentally correct", which more likely means it was believed complete (point 7). Point 3 is about impact, not intent: the same comment proposed the CHANGES wording that names this exact scenario. Point 5 is the separate shortcut for total automata; apart from the two boxes, non-total ones such as . or [^/]* reject the other invalid forms (C0/C1, sequences above U+10FFFF, lone continuation bytes); they accept the encoded surrogates ED A0..BF xx, because U+D800..U+DFFF are in the code-point range (not part of this report). Point 6 limits who may call the class, not what "equivalent" means. Verdict: a real, long-standing defect with low practical impact; because the fix has a size cost, upstream may prefer to fix or to document (option C). Terms that are valid UTF-8 are never mis-matched. The cross-model refute review rated the "intended" argument weak; the later cross-model fact check rated it moderate, while still finding the evidence against intent stronger.

Both fixes change only all(), the one place that emits the boxes: it is called with lead byte E0 and 2 continuation bytes, or F0 and 3, only from the two buggy paths (start() and the same-length middle pass a lead byte + 1 or continuation bytes; lines 184-191, 227-229). Both were validated in a scratch worktree at ea57360912ed with gradle and JDK 25; the worktree was removed afterwards. Automaton sizes (run automaton / minimal DFA states):

The minimal sizes are the same for both fixes because their languages are the same; no correct fix can avoid that growth. No query-speed benchmark was run.

+12 lines at the top of all(): when the lead-byte range starts at E0 with 2 continuation bytes left (or F0 with 3), emit that lead byte on its own, followed by A0..BF (or 90..BF) and the remaining 80..BF bytes, then continue the range from E1 (or F1). It is the study verifier's patch with a new comment, and the same logic as the study's JBMC-checked version.

private void all(int start, int end, int startCode, int endCode, int left) {
  // The shortest 3-byte sequence is E0 A0 80 (U+0800) and the shortest 4-byte one is F0 90 80 80
  // (U+10000): after a lead byte E0 or F0, a second byte below A0 or 90 would be an overlong
  // (invalid) encoding, so that lead byte gets its own, narrower second-byte range.
  if ((left == 2 && startCode == 0xE0) || (left == 3 && startCode == 0xF0)) {
    int n = utf8.createState();
    utf8.addTransition(start, n, startCode);
    all(n, end, startCode == 0xE0 ? 0xA0 : 0x90, 0xBF, left - 1);
    if (startCode == endCode) {
      return;
    }
    startCode++;
  }
  ... (unchanged: emit [startCode, endCode] followed by `left` bytes 80..BF)
}

Trade-offs

• Run automata grow: regexp . 14 -> 19 states, *foo* 104 -> 144 (+38%), 528 boundary ranges +11% (table above).
• Smallest diff of the two, and the logic is covered by the study's JBMC proof.

What the checks validated

• Repro: 9 of 9 pass with -ea and -da; the plain program exits 0.
• gradle, seed DEADBEEF: :lucene:core:test over org.apache.lucene.util.automaton.* (with the repro and the 2 regression tests), TestUnicodeUtil, TestRegexp*, TestWildcard*, TestAutomatonQuery*, TestPrefix*, TestFuzzy*, TestTermRangeQuery, TestTermsEnum*, and :lucene:suggest:test TestFuzzySuggester, TestFuzzyCompletionQuery: 357 tests, 0 failures, 3 skipped (stock: 10 failures, all in the new tests); checkGoogleJavaFormat passes.
• gradle with -Ptests.asserts=false -Ptests.seed=1234ABCD on TestUTF32ToUTF8*: 17 of 17 pass.
• The study's exact checker: 0 bad among all 9,472,128 ranges with ends below U+1100, 994,755 structural and 300,000 random ranges; 0 of 262,177 whole automata differ from a reference encoder. The verifier's 828-range characterization: no overlong and no other extra string.
• Study: JBMC proves the same logic (in the extracted code, accepted strings of up to 4 bytes) sound and complete for all 0 <= lo <= hi <= U+10FFFF.

+35/-9 lines: all() is restructured so that E0 (or F0) gets its own state, which joins the shared chain of continuation states after its narrow second byte, instead of a copy of the whole chain.

Trade-offs

• About 60% fewer extra run-automaton states than option A (regexp .: 16 instead of 19; *foo*: 120 instead of 144; 528 ranges +4.7% instead of +11%); the same minimal DFAs.
• A larger diff to review, and not covered by a model-checking proof.

What the checks validated

• The same runs as option A, all passing: repro 9 of 9 (-ea, -da), plain program, gradle 357 tests with 0 failures and checkGoogleJavaFormat, the assertions-off gradle run, the exact checker (0 bad ranges, 0 of 262,177 automata) and the 828-range characterization.

State in the UTF32ToUTF8, ByteRunAutomaton and AutomatonQuery javadocs that the byte automaton is equivalent only on valid UTF-8, and that Unicode queries can match some non-UTF-8 binary terms.

Trade-offs

No size cost, but it leaves the #12458 class half fixed, contradicts "equivalent", and keeps ranges one code point apart behaving differently. Not recommended.

Method: bounded-exhaustive translation validation plus bounded model checking (the study's "semi-formal" tier). Study run 3, experiment "automaton-verification", finding F3 (2026-10-22, main 7cecf79523).

• An AI tool wrote an exact reference semantics for UTF-8 ranges and compared the real UTF32ToUTF8 + ByteRunAutomaton with it on every range with ends below U+1100 (9.47M ranges), 994,755 structural ranges, 300,000 random ranges and 262,177 enumerated whole automata.
• It then ran JBMC 6.11 on a verbatim extraction of UTF32ToUTF8.java:33-283 (checked equal to the real class on 8,000,000 range and byte-string pairs), split by the UTF-8 lengths of the two ends. Main: complete for all ranges, with a counterexample in each of the length classes (1,3), (1,4), (2,3), (2,4), (3,4); every counterexample was replayed on the real jar. The fixed version: sound and complete for all ranges (for the extracted code and accepted strings of up to 4 bytes).
• The AI tool reports that it saw #12458 and #12472 only after the harness had found the problem (README section 10).
• A second, independent AI tool re-checked it with its own RFC 3629 oracle, test and patch, and the public-list rerun reproduced it on b83101cdd2. On 2026-10-26 the hunt reduced it to the 9-test JUnit and re-ran it on main and old releases.