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 b0c3e6a1 Verifier pass 3a delayed checks are quadratic in attribute
and code size (f023).
b0c3e6a1 is described below
commit b0c3e6a11bc32be316eadcd16a24c3811259e78b
Author: Gary Gregory <[email protected]>
AuthorDate: Fri Sep 4 18:23:28 2026 -0400
Verifier pass 3a delayed checks are quadratic in attribute and code size
(f023).
---
src/changes/changes.xml | 1 +
.../org/apache/bcel/verifier/statics/IntList.java | 14 +++---
.../bcel/verifier/statics/Pass3aVerifier.java | 56 ++++++++++------------
3 files changed, 34 insertions(+), 37 deletions(-)
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index da811fd8..e6d89ec0 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -108,6 +108,7 @@ The <action> type attribute can be add,update,fix,remove.
<action type="fix" dev="ggregory" due-to="Gary
Gregory">Signature.matchGJIdent recurses unboundedly on nested generic
signatures (Signature.translate) (f020).</action>
<action type="fix" dev="ggregory" due-to="Gary
Gregory">Utility.decode fixed 3x buffer breaks the encode/decode round trip and
throws unchecked AIOOBE (f021).</action>
<action type="fix" dev="ggregory" due-to="Gary
Gregory">BCELifier interpolates attacker class/package names into generated
Java source unescaped (f022).</action>
+ <action type="fix" dev="ggregory" due-to="Gary
Gregory">Verifier pass 3a delayed checks are quadratic in attribute and code
size (f023).</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/IntList.java
b/src/main/java/org/apache/bcel/verifier/statics/IntList.java
index 9c7c6fb3..17c8f26e 100644
--- a/src/main/java/org/apache/bcel/verifier/statics/IntList.java
+++ b/src/main/java/org/apache/bcel/verifier/statics/IntList.java
@@ -18,29 +18,29 @@
*/
package org.apache.bcel.verifier.statics;
-import java.util.ArrayList;
-import java.util.List;
+import java.util.HashSet;
+import java.util.Set;
/**
* A small utility class representing a set of basic int values.
*/
public class IntList {
- /** The int are stored as Integer objects here. */
- private final List<Integer> list;
+ /** The ints are stored as Integer objects in a hash set so that {@link
#contains(int)} is O(1), not a linear scan. */
+ private final Set<Integer> set;
/** This constructor creates an empty list. */
IntList() {
- list = new ArrayList<>();
+ set = new HashSet<>();
}
/** Adds an element to the list. */
void add(final int i) {
- list.add(Integer.valueOf(i));
+ set.add(Integer.valueOf(i));
}
/** Tests if the specified int is already in the list. */
boolean contains(final int i) {
- return list.contains(i);
+ return set.contains(Integer.valueOf(i));
}
}
diff --git a/src/main/java/org/apache/bcel/verifier/statics/Pass3aVerifier.java
b/src/main/java/org/apache/bcel/verifier/statics/Pass3aVerifier.java
index 7a846bed..4d3853bd 100644
--- a/src/main/java/org/apache/bcel/verifier/statics/Pass3aVerifier.java
+++ b/src/main/java/org/apache/bcel/verifier/statics/Pass3aVerifier.java
@@ -19,6 +19,8 @@
package org.apache.bcel.verifier.statics;
import java.util.Arrays;
+import java.util.HashSet;
+import java.util.Set;
import org.apache.bcel.Const;
import org.apache.bcel.Repository;
@@ -865,16 +867,6 @@ public final class Pass3aVerifier extends PassVerifier {
}
}
- /** A small utility method returning if a given int i is in the given
int[] ints. */
- private static boolean contains(final int[] ints, final int i) {
- for (final int k : ints) {
- if (k == i) {
- return true;
- }
- }
- return false;
- }
-
/** The Verifier that created this. */
private final Verifier verifier;
@@ -919,6 +911,14 @@ public final class Pass3aVerifier extends PassVerifier {
final int[] instructionPositions =
instructionList.getInstructionPositions();
final int codeLength = code.getCode().length;
+ // The number of instructions and the number of LineNumberTable,
LocalVariableTable and exception_table entries
+ // are attacker-controlled u2 values, so each membership test below
must be O(1): the previous linear scans made
+ // this method quadratic in the size of a crafted Code attribute (CPU
exhaustion).
+ final Set<Integer> instructionPositionSet = new HashSet<>();
+ for (final int instructionPosition : instructionPositions) {
+ instructionPositionSet.add(Integer.valueOf(instructionPosition));
+ }
+
/////////////////////
// LineNumberTable //
/////////////////////
@@ -926,22 +926,18 @@ public final class Pass3aVerifier extends PassVerifier {
if (lnt != null) {
final LineNumber[] lineNumbers = lnt.getLineNumberTable();
final IntList offsets = new IntList();
- lineNumberLoop: for (final LineNumber lineNumber : lineNumbers) {
// may appear in any order.
- for (final int instructionPosition : instructionPositions) {
- // TODO: Make this a binary search! The
instructionPositions array is naturally ordered!
- final int offset = lineNumber.getStartPC();
- if (instructionPosition == offset) {
- if (offsets.contains(offset)) {
- addMessage("LineNumberTable attribute '" +
code.getLineNumberTable() + "' refers to the same code offset ('" + offset
- + "') more than once which is violating the
semantics [but is sometimes produced by IBM's 'jikes' compiler].");
- } else {
- offsets.add(offset);
- }
- continue lineNumberLoop;
- }
+ for (final LineNumber lineNumber : lineNumbers) { // may appear in
any order.
+ final int offset = lineNumber.getStartPC();
+ if (!instructionPositionSet.contains(Integer.valueOf(offset)))
{
+ throw new ClassConstraintException("Code attribute '" +
tostring(code) + "' has a LineNumberTable attribute '" +
code.getLineNumberTable()
+ + "' referring to a code offset ('" + offset + "')
that does not exist.");
+ }
+ if (offsets.contains(offset)) {
+ addMessage("LineNumberTable attribute '" +
code.getLineNumberTable() + "' refers to the same code offset ('" + offset
+ + "') more than once which is violating the semantics
[but is sometimes produced by IBM's 'jikes' compiler].");
+ } else {
+ offsets.add(offset);
}
- throw new ClassConstraintException("Code attribute '" +
tostring(code) + "' has a LineNumberTable attribute '" +
code.getLineNumberTable()
- + "' referring to a code offset ('" +
lineNumber.getStartPC() + "') that does not exist.");
}
}
@@ -958,11 +954,11 @@ public final class Pass3aVerifier extends PassVerifier {
final int startpc = localVariable.getStartPC();
final int length = localVariable.getLength();
- if (!contains(instructionPositions, startpc)) {
+ if
(!instructionPositionSet.contains(Integer.valueOf(startpc))) {
throw new ClassConstraintException("Code attribute '"
+ tostring(code) + "' has a LocalVariableTable attribute '"
+ code.getLocalVariableTable() + "' referring to a
code offset ('" + startpc + "') that does not exist.");
}
- if (!contains(instructionPositions, startpc + length) &&
startpc + length != codeLength) {
+ if
(!instructionPositionSet.contains(Integer.valueOf(startpc + length)) && startpc
+ length != codeLength) {
throw new ClassConstraintException(
"Code attribute '" + tostring(code) + "' has a
LocalVariableTable attribute '" + code.getLocalVariableTable()
+ "' referring to a code offset
start_pc+length ('" + (startpc + length) + "') that does not exist.");
@@ -986,16 +982,16 @@ public final class Pass3aVerifier extends PassVerifier {
throw new ClassConstraintException("Code attribute '" +
tostring(code) + "' has an exception_table entry '" + element
+ "' that has its start_pc ('" + startpc + "') not smaller
than its end_pc ('" + endpc + "').");
}
- if (!contains(instructionPositions, startpc)) {
+ if (!instructionPositionSet.contains(Integer.valueOf(startpc))) {
throw new ClassConstraintException("Code attribute '" +
tostring(code) + "' has an exception_table entry '" + element
+ "' that has a non-existant bytecode offset as its
start_pc ('" + startpc + "').");
}
- if (!contains(instructionPositions, endpc) && endpc != codeLength)
{
+ if (!instructionPositionSet.contains(Integer.valueOf(endpc)) &&
endpc != codeLength) {
throw new ClassConstraintException("Code attribute '" +
tostring(code) + "' has an exception_table entry '" + element
+ "' that has a non-existant bytecode offset as its end_pc
('" + startpc + "') [that is also not equal to code_length ('" + codeLength
+ "')].");
}
- if (!contains(instructionPositions, handlerpc)) {
+ if (!instructionPositionSet.contains(Integer.valueOf(handlerpc))) {
throw new ClassConstraintException("Code attribute '" +
tostring(code) + "' has an exception_table entry '" + element
+ "' that has a non-existant bytecode offset as its
handler_pc ('" + handlerpc + "').");
}
