JDK-8311905 : BitSet.valueOf(...) allows bitsets to be created that behave incorrectly.
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util
  • Affected Version: 8,11,17,20,21
  • Priority: P4
  • Status: New
  • Resolution: Unresolved
  • OS: generic
  • CPU: generic
  • Submitted: 2023-07-11
  • Updated: 2023-07-12
Description
A DESCRIPTION OF THE PROBLEM :
All 4 overloaded BitSet.valueOf(...) methods allow the user to load in objects that are too big, leading to the class' wordsInUse field to become too big. This in turn causes the length() method to overflow. 
The largest value that wordsInUse normally can get to is Integer.MAX_VALUE/64 + 1 (we refer to this as MAX_WIU). If wordsInUse is set to a value higher than MAX_WIU, then length() will overflow when doing BITS_PER_WORD * (wordsInUse - 1) + ...
Alongside the overflow in length(), it also means that a number of optimisations no longer properly work, as these assume wordsInUse only refers to bits accessible to the bitset.

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
This description applies to the valueOf(long[]) method, but similar steps apply for the other methods:
1) Create an array with a length greater than Integer.MAX_VALUE/64 + 1 (MAX_WIU).
2) Set at least one bit in this array to 1, in an element at index >= MAX_WIU. (For avoidance of doubt, this is: arr[i] with i >= MAX_WIU.)
3) Use the BitSet.valueOf(long[]) method.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
Call length() on the newly created bitset. Provided this method returns a value > 0*, call bitset.get( bitset.length()-1 ). The expected result is that this call will return True, as per length() specification.

*: It is possible for the length() to overflow to a negative number or to 0. In this case, the .get( .length()-1 ) call is not possible. The "Furthermore" part however does still apply.
ACTUAL -
The actual result is that this call will return False.

Furthermore, while bits were set in the original array, no bits are set to true in the new bitset.

---------- BEGIN SOURCE ----------
int MAX_WIU = Integer.MAX_VALUE/64 + 1;

// Expected
long[] okArr = new long[MAX_WIU];
okArr[ okArr.length-1 ] = 1;
BitSet okBS = BitSet.valueOf(okArr);
System.out.println(okBS.length()); // 2147483585
System.out.println(okBS.get( okBS.length()-1 )); // TRUE

// Actual
long[] arr = new long[2*MAX_WIU+1];
arr[ arr.length-1 ] = 1;
BitSet bitSet = BitSet.valueOf(arr);
System.out.println(bitSet.length()); // 1
System.out.println(bitSet.get( bitSet.length()-1 )); // FALSE

LongBuffer lb = LongBuffer.wrap(arr);
BitSet bitSet2 = BitSet.valueOf(lb);
System.out.println(bitSet2.length()); // 1
System.out.println(bitSet2.get( bitSet2.length()-1 )); // FALSE

ByteBuffer bb = ByteBuffer.allocate(arr.length * Long.BYTES);
bb.asLongBuffer().put(arr);
BitSet bitSet3 = BitSet.valueOf(bb);
System.out.println(bitSet3.length()); // 57
System.out.println(bitSet3.get( bitSet3.length()-1 )); // FALSE

byte[] barr = new byte[bb.remaining()];
bb.get(barr);
BitSet bitSet4 = BitSet.valueOf(barr);
System.out.println(bitSet4.length()); // 57
System.out.println(bitSet4.get( bitSet4.length()-1 )); // FALSE
---------- END SOURCE ----------

FREQUENCY : always



Comments
The observations on Windows 10: JDK 8: Failed, false values returned. JDK 11: Failed. JDK 17: Failed. JDK 20: Failed. JDK 21ea+20: Failed.
12-07-2023