This is an automated email from the ASF dual-hosted git repository.
tballison pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/tika.git
The following commit(s) were added to refs/heads/main by this push:
new e40df7fe40 TIKA-5052: PatchedCharset decode was quadratic on
malformed-heavy input (#3601)
e40df7fe40 is described below
commit e40df7fe401db6e0394383326239997e424efae1
Author: Tim Allison <[email protected]>
AuthorDate: Thu Nov 12 16:52:28 2026 -0500
TIKA-5052: PatchedCharset decode was quadratic on malformed-heavy input
(#3601)
---
.../org/apache/tika/detect/PatchedCharset.java | 57 +++++++++++++-
.../org/apache/tika/detect/PatchedCharsetTest.java | 67 ++++++++++++++++
.../apache/tika/detect/x-test-mismatch-WHATWG.tsv | 6 ++
.../tika/fuzzing/PatchedCharsetFuzzTest.java | 91 ++++++++++++++++++++++
.../decode/big5-patched-pairs.seed | 1 +
.../decode/malformed-every-other-byte.seed | 1 +
6 files changed, 220 insertions(+), 3 deletions(-)
diff --git a/tika-core/src/main/java/org/apache/tika/detect/PatchedCharset.java
b/tika-core/src/main/java/org/apache/tika/detect/PatchedCharset.java
index 35248924ac..1fdffc297a 100644
--- a/tika-core/src/main/java/org/apache/tika/detect/PatchedCharset.java
+++ b/tika-core/src/main/java/org/apache/tika/detect/PatchedCharset.java
@@ -225,41 +225,92 @@ final class PatchedCharset extends Charset {
this.base = cs.base.newDecoder();
}
+ /**
+ * Bound on the unit walk per base run. The framework re-enters
decodeLoop after every
+ * malformed sequence the base reports, and an unbounded walk to the
next patched unit
+ * made malformed-heavy input quadratic (a 2.6 MB non-EUC-JP page took
30 minutes).
+ */
+ private static final int SCAN_CHUNK = 256;
+
@Override
protected CoderResult decodeLoop(ByteBuffer in, CharBuffer out) {
+ // State for a base that stops inside a sequence the unit table
ended early (its lead
+ // bytes differ from the table): the next run must reach further.
Each retry strictly
+ // extends the run or returns, so the loop terminates.
+ int chunk = SCAN_CHUNK;
+ int skip = -1; // walk past the patched unit the base
straddles
+ boolean toEnd = false; // the rest is shorter than a table unit:
give the base all of it
while (true) {
int start = in.position();
int limit = in.limit();
+ int scanEnd = toEnd ? limit : (int) Math.min(limit, start +
(long) chunk);
// Walk the base's units so a patched sequence is only matched
at a unit boundary.
int i = start;
int unit = 0;
String value = null;
+ boolean incomplete = false;
while (i < limit) {
+ if (toEnd) {
+ i = limit;
+ break;
+ }
int b = in.get(i) & 0xFF;
int n = cs.unitLength[b];
if (n == 1) {
value = cs.single[b];
} else if (i + n > limit) {
+ incomplete = true;
break;
} else if (n == 2) {
value = cs.patch(b, in.get(i + 1));
}
if (value != null) {
- unit = n;
- break;
+ if (i != skip) {
+ unit = n;
+ break;
+ }
+ value = null;
}
i += n;
+ if (i >= scanEnd) {
+ break;
+ }
}
if (i > start) {
ByteBuffer run = in.duplicate();
run.limit(i);
CoderResult cr = base.decode(run, out, false);
in.position(run.position());
- if (cr.isError() || cr.isOverflow() || run.hasRemaining())
{
+ if (cr.isError() || cr.isOverflow()) {
return cr;
}
+ if (run.hasRemaining()) {
+ if (run.position() == start) {
+ if (i >= limit) {
+ return CoderResult.UNDERFLOW;
+ }
+ if (value != null) {
+ skip = i;
+ } else if (incomplete) {
+ toEnd = true;
+ } else {
+ chunk = Math.min(chunk * 2, Integer.MAX_VALUE
/ 2);
+ }
+ continue;
+ }
+ chunk = SCAN_CHUNK;
+ skip = -1;
+ toEnd = false;
+ continue;
+ }
}
+ chunk = SCAN_CHUNK;
+ skip = -1;
+ toEnd = false;
if (value == null) {
+ if (i < limit && !incomplete) {
+ continue;
+ }
return CoderResult.UNDERFLOW;
}
if (out.remaining() < value.length()) {
diff --git
a/tika-core/src/test/java/org/apache/tika/detect/PatchedCharsetTest.java
b/tika-core/src/test/java/org/apache/tika/detect/PatchedCharsetTest.java
index fcff3fa1fb..84fe927a03 100644
--- a/tika-core/src/test/java/org/apache/tika/detect/PatchedCharsetTest.java
+++ b/tika-core/src/test/java/org/apache/tika/detect/PatchedCharsetTest.java
@@ -21,6 +21,7 @@ import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertNotNull;
import static org.junit.jupiter.api.Assertions.assertNull;
+import static org.junit.jupiter.api.Assertions.assertTimeoutPreemptively;
import static org.junit.jupiter.api.Assertions.assertTrue;
import java.io.ByteArrayInputStream;
@@ -30,6 +31,7 @@ import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.Reader;
import java.nio.charset.Charset;
+import java.time.Duration;
import java.util.Arrays;
import java.util.Collections;
import java.util.HexFormat;
@@ -209,6 +211,71 @@ public class PatchedCharsetTest {
}
}
+ /**
+ * Bytes that are not the charset make the base report a malformed
sequence every few bytes;
+ * each one re-enters decodeLoop. The walk to the next patched unit was
unbounded, so this
+ * was quadratic: 131 KB of a non-EUC-JP page took 5 s and a 2.6 MB page
half an hour.
+ */
+ @Test
+ public void malformedHeavyInputDecodesInLinearTime() {
+ // 0x80 is a lead byte in every patch table and a malformed single
byte for every base
+ byte[] junk = new byte[1 << 20];
+ for (int i = 0; i < junk.length; i++) {
+ junk[i] = (byte) (i % 2 == 0 ? 0x80 : 'A');
+ }
+ for (Charset c : CharsetSupersets.patched()) {
+ PatchedCharset cs = (PatchedCharset) c;
+ String decoded = assertTimeoutPreemptively(Duration.ofSeconds(20),
+ () -> new String(junk, cs), cs.name());
+ assertEquals(unitwise(cs, junk, true), decoded, cs.name());
+ }
+ }
+
+ /**
+ * A unit table whose lead bytes disagree with the base's: the base then
stops inside a
+ * sequence the walk ended early. Its view wins, decoding continues past
the point, and the
+ * loop ends. The shipped tables agree with their bases, so this needs a
test table.
+ */
+ @Test
+ public void baseSequenceLongerThanTableUnit() throws IOException {
+ PatchedCharset mismatch =
PatchedCharset.load("/org/apache/tika/detect/x-test-mismatch-WHATWG.tsv");
+ Charset base = mismatch.base();
+ // a wrong exit condition here loops forever; fail instead of hanging
the build
+ Charset cs = assertTimeoutPreemptively(Duration.ofSeconds(30), () -> {
+ new String(new byte[] {(byte) 0xA1, (byte) 0xC1}, mismatch);
+ new String(new byte[] {(byte) 0x8F, (byte) 0xB0, (byte) 0xA2,
(byte) 0xCC}, mismatch);
+ new String(new byte[] {'a', (byte) 0x8F, (byte) 0xB0}, mismatch);
+ return mismatch;
+ });
+ assertEquals(1, mismatch.unitLength(0xA1));
+ assertEquals(2, mismatch.unitLength(0x8F));
+ String waveDash = dec(base, 0xA1, 0xC1);
+ assertFalse(waveDash.contains("�"));
+ // A1 is a single byte to the table; the base needs the trail
+ assertEquals(waveDash, dec(cs, 0xA1, 0xC1));
+ // ... followed by a patched pair, and inside a longer text
+ assertEquals(waveDash + "¬", dec(cs, 0xA1, 0xC1, 0xA2, 0xCC));
+ assertEquals("ab" + waveDash + "¬c" + waveDash, dec(cs, 'a', 'b',
0xA1, 0xC1, 0xA2, 0xCC, 'c', 0xA1, 0xC1));
+ // 8F is 2 bytes to the table and 3 to the base, so it straddles the
patched pair that follows
+ String jisX0212 = dec(base, 0x8F, 0xB0, 0xA2);
+ assertEquals(1, jisX0212.length());
+ assertEquals(jisX0212 + "�", dec(cs, 0x8F, 0xB0, 0xA2, 0xCC));
+ // truly incomplete at the end
+ assertEquals("a�", dec(cs, 'a', 0xA1));
+ assertEquals("a�", dec(cs, 'a', 0x8F, 0xB0));
+ // whole and streamed decodes agree
+ byte[] b = new byte[2000];
+ Random r = new Random(5052L);
+ int[] pieces = {0xA1, 0xC1, 0xA2, 0xCC, 0x8F, 0xB0, 0xA2, 'x', 0x80};
+ for (int i = 0; i < b.length; i++) {
+ b[i] = (byte) pieces[r.nextInt(pieces.length)];
+ }
+ String whole = new String(b, cs);
+ for (int chunk = 1; chunk <= 5; chunk++) {
+ assertEquals(whole, read(new FixedChunkStream(b, chunk), cs,
chunk), "chunk " + chunk);
+ }
+ }
+
@Test
public void encodesAsTheBase() {
String s = "中文 abc";
diff --git
a/tika-core/src/test/resources/org/apache/tika/detect/x-test-mismatch-WHATWG.tsv
b/tika-core/src/test/resources/org/apache/tika/detect/x-test-mismatch-WHATWG.tsv
new file mode 100644
index 0000000000..6857bd84dd
--- /dev/null
+++
b/tika-core/src/test/resources/org/apache/tika/detect/x-test-mismatch-WHATWG.tsv
@@ -0,0 +1,6 @@
+# Test table whose unit lengths disagree with the base (PatchedCharsetTest):
A1 is a single byte
+# here but a 2-byte lead to x-eucJP-Open; 8F is 2 bytes here but 3 to the base.
+name x-test-mismatch
+base x-eucJP-Open
+lead 80-8E,8F-8F,90-A0,A2-FF
+A2CC U+00AC
diff --git
a/tika-fuzzing/src/test/java/org/apache/tika/fuzzing/PatchedCharsetFuzzTest.java
b/tika-fuzzing/src/test/java/org/apache/tika/fuzzing/PatchedCharsetFuzzTest.java
new file mode 100644
index 0000000000..c365b9cd0b
--- /dev/null
+++
b/tika-fuzzing/src/test/java/org/apache/tika/fuzzing/PatchedCharsetFuzzTest.java
@@ -0,0 +1,91 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.tika.fuzzing;
+
+import java.io.ByteArrayInputStream;
+import java.io.IOException;
+import java.io.InputStreamReader;
+import java.io.Reader;
+import java.nio.charset.Charset;
+import java.util.List;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
+import java.util.concurrent.Future;
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.TimeoutException;
+
+import com.code_intelligence.jazzer.junit.FuzzTest;
+
+import org.apache.tika.detect.CharsetSupersets;
+
+/**
+ * The WHATWG-patched decoders ({@code CharsetSupersets.decodeAs}) on
arbitrary bytes: a decode
+ * must finish within the budget (a malformed-heavy page once took half an
hour), and decoding
+ * the whole array must equal decoding it through a reader in small chunks.
+ */
+class PatchedCharsetFuzzTest {
+
+ private static final long TIMEOUT_SECONDS =
Long.getLong("tika.fuzz.timeout", 10);
+
+ private static final List<Charset> PATCHED = List.of(
+ CharsetSupersets.decodeAs(Charset.forName("Big5")),
+ CharsetSupersets.decodeAs(Charset.forName("Big5-HKSCS")),
+ CharsetSupersets.decodeAs(Charset.forName("EUC-JP")));
+
+ private static final ExecutorService WORKER =
Executors.newSingleThreadExecutor(r -> {
+ Thread t = new Thread(r, "tika-fuzz-decode");
+ t.setDaemon(true);
+ return t;
+ });
+
+ @FuzzTest
+ void decode(byte[] data) throws Exception {
+ for (Charset cs : PATCHED) {
+ Future<String> whole = WORKER.submit(() -> new String(data, cs));
+ String decoded;
+ try {
+ decoded = whole.get(TIMEOUT_SECONDS, TimeUnit.SECONDS);
+ } catch (TimeoutException e) {
+ whole.cancel(true);
+ throw new IllegalStateException(cs.name() + ": decode of " +
data.length
+ + " bytes exceeded " + TIMEOUT_SECONDS + "s", e);
+ } catch (ExecutionException e) {
+ throw new IllegalStateException(cs.name(), e.getCause());
+ }
+ for (int chunk : new int[] {5, 64}) {
+ String streamed = streamed(data, cs, chunk);
+ if (!decoded.equals(streamed)) {
+ throw new IllegalStateException(cs.name() + ": whole
decode differs from a "
+ + chunk + "-char streamed decode of " +
data.length + " bytes");
+ }
+ }
+ }
+ }
+
+ private static String streamed(byte[] data, Charset cs, int chunk) throws
IOException {
+ StringBuilder sb = new StringBuilder();
+ char[] buf = new char[chunk];
+ try (Reader r = new InputStreamReader(new ByteArrayInputStream(data),
cs)) {
+ int n;
+ while ((n = r.read(buf)) != -1) {
+ sb.append(buf, 0, n);
+ }
+ }
+ return sb.toString();
+ }
+}
diff --git
a/tika-fuzzing/src/test/resources/org/apache/tika/fuzzing/PatchedCharsetFuzzTestInputs/decode/big5-patched-pairs.seed
b/tika-fuzzing/src/test/resources/org/apache/tika/fuzzing/PatchedCharsetFuzzTestInputs/decode/big5-patched-pairs.seed
new file mode 100644
index 0000000000..cca74670d2
--- /dev/null
+++
b/tika-fuzzing/src/test/resources/org/apache/tika/fuzzing/PatchedCharsetFuzzTestInputs/decode/big5-patched-pairs.seed
@@ -0,0 +1 @@
+xxxxxxx�အE�b�
\ No newline at end of file
diff --git
a/tika-fuzzing/src/test/resources/org/apache/tika/fuzzing/PatchedCharsetFuzzTestInputs/decode/malformed-every-other-byte.seed
b/tika-fuzzing/src/test/resources/org/apache/tika/fuzzing/PatchedCharsetFuzzTestInputs/decode/malformed-every-other-byte.seed
new file mode 100644
index 0000000000..6c139efd9b
--- /dev/null
+++
b/tika-fuzzing/src/test/resources/org/apache/tika/fuzzing/PatchedCharsetFuzzTestInputs/decode/malformed-every-other-byte.seed
@@ -0,0 +1 @@
+�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A�A
[...]
\ No newline at end of file