You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "gsmiller (via GitHub)" <gi...@apache.org> on 2023/07/24 19:41:08 UTC
[GitHub] [lucene] gsmiller opened a new issue, #12458: UTF32toUTF8 can produce automata that produce invalid unicode
gsmiller opened a new issue, #12458:
URL: https://github.com/apache/lucene/issues/12458
### Description
When converting a unicode (UTF32) automaton down to a UTF8 representation, UTF32toUTF8 can create an automaton that produces/accepts invalid UTF8. This happens when a transition in the input automaton contains a code-point range that spans different UTF8 byte counts.
As an example/repro, create an automaton that accepts the two single-character terms: `U+65535` and `U+65536` (sample code for this in the repro test case below). Before compiling, the UTF32 representation is:
This range correctly covers `65535 - 65536` (`0xffff - 0x10000`). Note that the min value (65535) is the largest value that can be represented in three UTF8 bytes (it's representation is `11101111 10111111 10111111` in UTF8), and the max value (65536) is the smallest valid UTF8 representation that uses four bytes (`11110000 10010000 10000000 10000000`).
After converting with `UTF32toUTF8#convert`, the resulting automaton looks like this:
This automaton incorrectly accepts/produces everything in the range `0xf0 0x80 0x80 0x80` - `0xf0 0x8f 0xbf 0xbf`. These are four byte UTF8 sequences encoding all code points from `0x00 - 0xffff` (`0 - 65535`). So this automaton now incorrectly accepts/produces everything between `0 - 65534` (`65535` is valid of course). Because it's representing these values as four UTF8 bytes, I believe these are actually invalid UTF8 since my understanding is that code points should be represented with the minimal number of bytes, but I might be mistaken.
The bug lies in the `UTF32toUTF8#end` logic.
Here is a full test case that demonstrates the bug:
```
public void testFoo() throws Exception {
Automaton.Builder b = new Automaton.Builder();
// start state:
int s1 = b.createState();
// single end accept state:
int s2 = b.createState();
b.setAccept(s2, true);
// add two single-code-point terms: U+65535 and U+65536
b.addTransition(s1, s2, 65535);
b.addTransition(s1, s2, 65536);
Automaton a = b.finish();
CompiledAutomaton c = new CompiledAutomaton(a);
FiniteStringsIterator it = new FiniteStringsIterator(c.automaton);
int termCount = 0;
for (IntsRef r = it.next(); r != null; r = it.next()) {
termCount++;
}
assertEquals(2, termCount);
}
```
The assertion fails as:
```
expected:<2> but was:<65538>
```
### Version and environment details
_No response_
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] mikemccand commented on issue #12458: UTF32toUTF8 can create automata that produce/accept invalid unicode
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on issue #12458:
URL: https://github.com/apache/lucene/issues/12458#issuecomment-1653658734
The code does in fact seem to try to handle this case, when the start/end UTF-8 have different numbers of bytes, in the final `else` clause in the confusing `build` method:
```
} else {
// start
start(start, end, startUTF8, upto, true);
// possibly middle, spanning multiple num bytes
int byteCount = 1 + startUTF8.len - upto;
final int limit = endUTF8.len - upto;
while (byteCount < limit) {
// wasteful: we only need first byte, and, we should
// statically encode this first byte:
tmpUTF8a.set(startCodes[byteCount - 1]);
tmpUTF8b.set(endCodes[byteCount - 1]);
all(start, end, tmpUTF8a.byteAt(0), tmpUTF8b.byteAt(0), tmpUTF8a.len - 1);
byteCount++;
}
```
Here the bug must lurk!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] gsmiller commented on issue #12458: UTF32toUTF8 can create automata that produce/accept invalid unicode
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on issue #12458:
URL: https://github.com/apache/lucene/issues/12458#issuecomment-1681354136
Fixed by @tang-hi in GH#12472. Thanks!!!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] mikemccand commented on issue #12458: UTF32toUTF8 can create automata that produce/accept invalid unicode
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on issue #12458:
URL: https://github.com/apache/lucene/issues/12458#issuecomment-1653651762
And ... 2 -> 3 bytes DOES fail, fun :)
```
public void testUTF8TwoToThreeBytes() throws Exception {
Automaton.Builder b = new Automaton.Builder();
// start state:
int s1 = b.createState();
// single end accept state:
int s2 = b.createState();
b.setAccept(s2, true);
// add two single-code-point terms
b.addTransition(s1, s2, 0x7FF);
b.addTransition(s1, s2, 0x800);
Automaton a = b.finish();
CompiledAutomaton c = new CompiledAutomaton(a);
FiniteStringsIterator it = new FiniteStringsIterator(c.automaton);
int termCount = 0;
for (IntsRef r = it.next(); r != null; r = it.next()) {
termCount++;
}
assertEquals(2, termCount);
}
```
```
> java.lang.AssertionError: expected:<2> but was:<2050>
> at __randomizedtesting.SeedInfo.seed([E20E213BD5F7763C:1E8F5BB354E27C83]:0)
> at org.junit.Assert.fail(Assert.java:89)
> at org.junit.Assert.failNotEquals(Assert.java:835)
> at org.junit.Assert.assertEquals(Assert.java:647)
> at org.junit.Assert.assertEquals(Assert.java:633)
> at org.apache.lucene.util.automaton.TestUTF32ToUTF8.testUTF8TwoToThreeBytes(TestUTF32ToUTF8.java:335)
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] mikemccand commented on issue #12458: UTF32toUTF8 can create automata that produce/accept invalid unicode
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on issue #12458:
URL: https://github.com/apache/lucene/issues/12458#issuecomment-1657101258
Whoa, great find! T hanks @tang-hi -- I'll try to review the PR soon.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] gsmiller closed issue #12458: UTF32toUTF8 can create automata that produce/accept invalid unicode
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller closed issue #12458: UTF32toUTF8 can create automata that produce/accept invalid unicode
URL: https://github.com/apache/lucene/issues/12458
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] tang-hi commented on issue #12458: UTF32toUTF8 can create automata that produce/accept invalid unicode
Posted by "tang-hi (via GitHub)" <gi...@apache.org>.
tang-hi commented on issue #12458:
URL: https://github.com/apache/lucene/issues/12458#issuecomment-1656725544
I have discovered the bug.
```Java
if (endUTF8.numBits(upto) == 5) {
// special case -- avoid created unused edges (endUTF8
// doesn't accept certain byte sequences) -- there
// are other cases we could optimize too:
startCode = 194;
} else {
startCode = endUTF8.byteAt(upto) & (~MASKS[endUTF8.numBits(upto) - 1]);
}
```
In the provided Java code snippet, there is an assumption that the codepoint will start at 0x80 when the number of bits is 6. However, this assumption is incorrect. In reality, when the length of the codepoint is 3 and the first byte is 0xE0, it will start from 0xA0. Similarly, when the length of the codepoint is 4 and the first byte is 0xF0, it will start from 0x90. You can verify this information on the following website: https://www.utf8-chartable.de/unicode-utf8-table.pl
Here is the PR to fix that #12472
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] mikemccand commented on issue #12458: UTF32toUTF8 can create automata that produce/accept invalid unicode
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on issue #12458:
URL: https://github.com/apache/lucene/issues/12458#issuecomment-1653642809
Hmm curiously the 1 -> 2 byte test case passes:
```
public void testUTF8OneToTwoBytes() throws Exception {
Automaton.Builder b = new Automaton.Builder();
// start state:
int s1 = b.createState();
// single end accept state:
int s2 = b.createState();
b.setAccept(s2, true);
// add two single-code-point terms: U+65535 and U+65536
b.addTransition(s1, s2, 127);
b.addTransition(s1, s2, 128);
Automaton a = b.finish();
CompiledAutomaton c = new CompiledAutomaton(a);
FiniteStringsIterator it = new FiniteStringsIterator(c.automaton);
int termCount = 0;
for (IntsRef r = it.next(); r != null; r = it.next()) {
termCount++;
}
assertEquals(2, termCount);
}
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] mikemccand commented on issue #12458: UTF32toUTF8 can create automata that produce/accept invalid unicode
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on issue #12458:
URL: https://github.com/apache/lucene/issues/12458#issuecomment-1653547413
Thanks @gsmiller! What a scary/crazy failure, and it has been lurking for soooo long, I suspect since `UTF32toUTF8` was created. And thank you randomized testing for finally uncovering this corner case bug.
This likely also occurs for the other UTF-8 byte transitions (1->2, 2->3, 3->4, 1->3, etc.), when they appear in a single UTF-32 transition, hrmph.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org