This is an automated email from the ASF dual-hosted git repository.
garydgregory pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-bcel.git
The following commit(s) were added to refs/heads/master by this push:
new 2970b4c9 JustIce Pass 2 LVT check amplifies each 10-byte entry into
~131k hashtable operations (f005).
2970b4c9 is described below
commit 2970b4c9ef2e6ea9265ab4d758c81961ae0fcbb4
Author: Gary Gregory <[email protected]>
AuthorDate: Fri Sep 4 15:45:30 2026 -0400
JustIce Pass 2 LVT check amplifies each 10-byte entry into ~131k
hashtable operations (f005).
---
src/changes/changes.xml | 1 +
.../bcel/verifier/statics/LocalVariableInfo.java | 102 +++++++++++++--------
.../verifier/statics/LocalVariableInfoTest.java | 91 ++++++++++++++++++
3 files changed, 158 insertions(+), 36 deletions(-)
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index 4bad4357..186cd931 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -92,6 +92,7 @@ The <action> type attribute can be add,update,fix,remove.
<action type="fix" dev="ggregory" due-to="Gary
Gregory">Nested annotation element values recurse unboundedly;
MAX_ARRAY_DIMENSIONS cap bypassed (f002).</action>
<action type="fix" dev="ggregory" due-to="Gary
Gregory">Opcodes tableswitch and lookupswitch add boundary checks
(f003).</action>
<action type="fix" dev="ggregory" due-to="Gary
Gregory">JustIce Pass 2 hangs on cyclic superclass chain of a referenced
exception class (f004).</action>
+ <action type="fix" dev="ggregory" due-to="Gary
Gregory">JustIce Pass 2 LVT check amplifies each 10-byte entry into ~131k
hashtable operations (f005).</action>
<!-- ADD -->
<action type="add" dev="ggregory" due-to="nbauma109,
Gary Gregory">Add support for permitted subclasses #493.</action>
<action type="add" dev="ggregory" due-to="nbauma109,
Gary Gregory">Add RecordComponentInfo.getAttribute(byte tag)#494.</action>
diff --git
a/src/main/java/org/apache/bcel/verifier/statics/LocalVariableInfo.java
b/src/main/java/org/apache/bcel/verifier/statics/LocalVariableInfo.java
index 2f9ccbc4..15cea256 100644
--- a/src/main/java/org/apache/bcel/verifier/statics/LocalVariableInfo.java
+++ b/src/main/java/org/apache/bcel/verifier/statics/LocalVariableInfo.java
@@ -18,7 +18,11 @@
*/
package org.apache.bcel.verifier.statics;
-import java.util.Hashtable;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+import java.util.NavigableMap;
+import java.util.TreeMap;
import org.apache.bcel.generic.Type;
import org.apache.bcel.verifier.exc.LocalVariableInfoInconsistentException;
@@ -29,34 +33,35 @@ import
org.apache.bcel.verifier.exc.LocalVariableInfoInconsistentException;
*/
public class LocalVariableInfo {
- /** The types database. KEY: String representing the offset integer. */
- private final Hashtable<String, Type> types = new Hashtable<>();
+ /**
+ * A contiguous, inclusive range of bytecode offsets sharing one variable
name and one type.
+ */
+ private static final class Range {
+ private final int start;
+ private final int end; // inclusive
+ private final String name;
+ private final Type type;
- /** The names database. KEY: String representing the offset integer. */
- private final Hashtable<String, String> names = new Hashtable<>();
+ Range(final int start, final int end, final String name, final Type
type) {
+ this.start = start;
+ this.end = end;
+ this.name = name;
+ this.type = type;
+ }
+ }
/**
- * Constructs a new LocalVariableInfo.
+ * The database of ranges, keyed by their start offset. Invariant: the
stored ranges never overlap each other; additions overlapping an existing range
+ * with consistent information are coalesced into it, inconsistent ones
are rejected. Storing ranges instead of one entry per offset keeps the work and
+ * memory proportional to the number of LocalVariableTable entries: the
startPc and length fields are attacker-controlled in a malicious class file and
+ * would otherwise amplify each 10-byte table entry into up to 65,536
hashtable operations (CWE-407).
*/
- public LocalVariableInfo() {
- }
+ private final NavigableMap<Integer, Range> ranges = new TreeMap<>();
/**
- * Adds information about name and type for a given offset.
- *
- * @throws LocalVariableInfoInconsistentException if the new information
conflicts with already gathered information.
+ * Constructs a new LocalVariableInfo.
*/
- private void add(final int offset, final String name, final Type t) throws
LocalVariableInfoInconsistentException {
- if (getName(offset) != null && !getName(offset).equals(name)) {
- throw new LocalVariableInfoInconsistentException(
- "At bytecode offset '" + offset + "' a local variable has two
different names: '" + getName(offset) + "' and '" + name + "'.");
- }
- if (getType(offset) != null && !getType(offset).equals(t)) {
- throw new LocalVariableInfoInconsistentException(
- "At bytecode offset '" + offset + "' a local variable has two
different types: '" + getType(offset) + "' and '" + t + "'.");
- }
- setName(offset, name);
- setType(offset, t);
+ public LocalVariableInfo() {
}
/**
@@ -69,9 +74,37 @@ public class LocalVariableInfo {
* @throws LocalVariableInfoInconsistentException if the new information
conflicts with already gathered information.
*/
public void add(final String name, final int startPc, final int length,
final Type type) throws LocalVariableInfoInconsistentException {
- for (int i = startPc; i <= startPc + length; i++) { //
incl/incl-notation!
- add(i, name, type);
+ final int endPc = startPc + length; // incl/incl-notation!
+ int mergedStart = startPc;
+ int mergedEnd = endPc;
+ // Only ranges starting at or before endPc can overlap [startPc,
endPc]; since stored ranges never overlap each other, the first candidate is the
+ // last range starting at or before startPc.
+ Integer from = ranges.floorKey(startPc);
+ if (from == null) {
+ from = Integer.valueOf(startPc);
+ }
+ final List<Integer> merged = new ArrayList<>();
+ for (final Map.Entry<Integer, Range> entry : ranges.subMap(from, true,
Integer.valueOf(endPc), true).entrySet()) {
+ final Range range = entry.getValue();
+ if (range.end < startPc) {
+ continue; // does not overlap.
+ }
+ final int offset = Math.max(startPc, range.start);
+ if (!range.name.equals(name)) {
+ throw new LocalVariableInfoInconsistentException(
+ "At bytecode offset '" + offset + "' a local variable has
two different names: '" + range.name + "' and '" + name + "'.");
+ }
+ if (!range.type.equals(type)) {
+ throw new LocalVariableInfoInconsistentException(
+ "At bytecode offset '" + offset + "' a local variable has
two different types: '" + range.type + "' and '" + type + "'.");
+ }
+ // Consistent overlap: coalesce, so the database stays
proportional to the number of disjoint ranges.
+ mergedStart = Math.min(mergedStart, range.start);
+ mergedEnd = Math.max(mergedEnd, range.end);
+ merged.add(entry.getKey());
}
+ merged.forEach(ranges::remove);
+ ranges.put(Integer.valueOf(mergedStart), new Range(mergedStart,
mergedEnd, name, type));
}
/**
@@ -83,7 +116,8 @@ public class LocalVariableInfo {
* @return The name of the local variable that uses this local variable
slot at the given bytecode offset.
*/
public String getName(final int offset) {
- return names.get(Integer.toString(offset));
+ final Range range = lookup(offset);
+ return range != null ? range.name : null;
}
/**
@@ -95,20 +129,16 @@ public class LocalVariableInfo {
* @return The type of the local variable that uses this local variable
slot at the given bytecode offset.
*/
public Type getType(final int offset) {
- return types.get(Integer.toString(offset));
- }
-
- /**
- * Adds a name of a local variable and a certain slot to our 'names'
(Hashtable) database.
- */
- private void setName(final int offset, final String name) {
- names.put(Integer.toString(offset), name);
+ final Range range = lookup(offset);
+ return range != null ? range.type : null;
}
/**
- * Adds a type of a local variable and a certain slot to our 'types'
(Hashtable) database.
+ * Returns the range covering the given bytecode offset, or {@code null}
if no range covers it. Since the stored ranges never overlap, only the range
+ * with the greatest start offset at or below the given offset can cover
it.
*/
- private void setType(final int offset, final Type t) {
- types.put(Integer.toString(offset), t);
+ private Range lookup(final int offset) {
+ final Map.Entry<Integer, Range> entry =
ranges.floorEntry(Integer.valueOf(offset));
+ return entry != null && entry.getValue().end >= offset ?
entry.getValue() : null;
}
}
diff --git
a/src/test/java/org/apache/bcel/verifier/statics/LocalVariableInfoTest.java
b/src/test/java/org/apache/bcel/verifier/statics/LocalVariableInfoTest.java
new file mode 100644
index 00000000..939f87a0
--- /dev/null
+++ b/src/test/java/org/apache/bcel/verifier/statics/LocalVariableInfoTest.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
+ *
+ * https://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.bcel.verifier.statics;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNull;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTimeoutPreemptively;
+
+import java.time.Duration;
+
+import org.apache.bcel.generic.Type;
+import org.apache.bcel.verifier.exc.LocalVariableInfoInconsistentException;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Tests {@link LocalVariableInfo}.
+ */
+class LocalVariableInfoTest {
+
+ @Test
+ void testConflictingNameRejected() {
+ final LocalVariableInfo info = new LocalVariableInfo();
+ info.add("a", 0, 10, Type.INT);
+ assertThrows(LocalVariableInfoInconsistentException.class, () ->
info.add("b", 5, 10, Type.INT));
+ }
+
+ @Test
+ void testConflictingTypeRejected() {
+ final LocalVariableInfo info = new LocalVariableInfo();
+ info.add("a", 0, 10, Type.INT);
+ assertThrows(LocalVariableInfoInconsistentException.class, () ->
info.add("a", 10, 5, Type.FLOAT));
+ }
+
+ @Test
+ void testConsistentOverlapAccepted() {
+ final LocalVariableInfo info = new LocalVariableInfo();
+ info.add("a", 0, 10, Type.INT);
+ info.add("a", 5, 10, Type.INT);
+ assertEquals("a", info.getName(15));
+ assertNull(info.getName(16));
+ }
+
+ @Test
+ void testLookups() {
+ final LocalVariableInfo info = new LocalVariableInfo();
+ info.add("a", 0, 10, Type.INT);
+ info.add("b", 20, 5, Type.FLOAT);
+ assertEquals("a", info.getName(0));
+ assertEquals("a", info.getName(10));
+ assertEquals(Type.INT, info.getType(5));
+ assertNull(info.getName(11));
+ assertNull(info.getType(19));
+ assertEquals("b", info.getName(20));
+ assertEquals(Type.FLOAT, info.getType(25));
+ assertNull(info.getName(26));
+ }
+
+ /**
+ * A malicious class file can declare 65,535 maximum-length
LocalVariableTable entries for the same slot; processing them must stay
proportional to the
+ * number of entries, not to entries times offsets.
+ */
+ @Test
+ void testManyMaximumLengthEntriesFinishQuickly() {
+ assertTimeoutPreemptively(Duration.ofSeconds(10), () -> {
+ final LocalVariableInfo info = new LocalVariableInfo();
+ for (int i = 0; i < 65_535; i++) {
+ info.add("dup", 0, 65_535, Type.INT);
+ }
+ assertEquals("dup", info.getName(65_535));
+ assertNull(info.getName(65_536));
+ });
+ }
+}
