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

Reply via email to