-
Bug
-
Resolution: Fixed
-
P4
-
17, 18, 19
-
b13
-
generic
-
generic
-
Verified
A DESCRIPTION OF THE PROBLEM :
Class: ./java.base/share/classes/jdk/internal/util/random/RandomSupport.java
Method: public static long[] convertSeedBytesToLongs(byte[] seed, int n, int z)
The method attempts to create an array of longs by consuming the input bytes most significant bit first. New bytes are appended to the existing long using the OR operator on the signed byte. Due to sign extension this will overwrite all the existing bits from 63 to 8 if the next byte is negative.
STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
The bug will not readily manifest as a poorly seeded RNG with many of the bits in the generated long[] set to 1 quickly recovers and outputs a random sequence. Reproducing cannot be done without access to the internal class RandomSupport.
I have extracted the part of the class with the bug into a driver program:
public class RandomSupport {
private static final char[] HEX_DIGITS =
{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
public static long[] convertSeedBytesToLongs(byte[] seed, int n, int z) {
final long[] result = new long[n];
final int m = Math.min(seed.length, n << 3);
// Distribute seed bytes into the words to be formed.
for (int j = 0; j < m; j++) {
// Sign extension bug
result[j >> 3] = (result[j >> 3] << 8) | seed[j];
}
// Filling the rest of the long[] has been removed for brevity.
// It only matters if the bytes are shorter than the desired length of long[].
return result;
}
public static long[] convertSeedBytesToLongsFixed(byte[] seed, int n, int z) {
final long[] result = new long[n];
final int m = Math.min(seed.length, n << 3);
// Distribute seed bytes into the words to be formed.
for (int j = 0; j < m; j++) {
result[j >> 3] = (result[j >> 3] << 8) | (seed[j] & 0xff);
}
return result;
}
public static void main(String[] args) {
RandomGenerator rng = RandomGeneratorFactory.of("L64X128MixRandom").create(42);
for (int i = 1; i < 8; i++) {
byte[] seed = new byte[i];
for (int j = 0; j < 10; j++) {
rng.nextBytes(seed);
for (byte b : seed) {
System.out.printf("%c%c", HEX_DIGITS[(b & 0xf0) >> 4], HEX_DIGITS[b & 0xf]);
}
System.out.printf(" %-16s %-16s%n",
Long.toHexString(convertSeedBytesToLongs(seed, 1, 1)[0]),
Long.toHexString(convertSeedBytesToLongsFixed(seed, 1, 1)[0]));
}
}
}
}
EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
Compile and run the driver program:
> javac RandomSupport.java
> java RandomSupport
Column: Description
1: Hex representation of the input byte[], most significant bits first
2: Current long output (hex representation)
3: Corrected long output (hex representation)
12 12 12
10 10 10
38 38 38
ec ffffffffffffffec ec
8a ffffffffffffff8a 8a
7e 7e 7e
cf ffffffffffffffcf cf
12 12 12
11 11 11
d4 ffffffffffffffd4 d4
7ae2 ffffffffffffffe2 7ae2
47c8 ffffffffffffffc8 47c8
3cc0 ffffffffffffffc0 3cc0
2475 2475 2475
fdce ffffffffffffffce fdce
7c04 7c04 7c04
16a4 ffffffffffffffa4 16a4
0bf1 fffffffffffffff1 bf1
cb22 ffffffffffffcb22 cb22
63eb ffffffffffffffeb 63eb
6d72b7 ffffffffffffffb7 6d72b7
ddd3a6 ffffffffffffffa6 ddd3a6
6194a2 ffffffffffffffa2 6194a2
d54bc0 ffffffffffffffc0 d54bc0
3142f5 fffffffffffffff5 3142f5
643056 643056 643056
ff94ba ffffffffffffffba ff94ba
86923e ffffffffffff923e 86923e
faf8f0 fffffffffffffff0 faf8f0
b69017 ffffffffffff9017 b69017
f4b40258 ffffffffffb40258 f4b40258
c099cae2 ffffffffffffffe2 c099cae2
9273a475 ffffffffffffa475 9273a475
99359c54 ffffffffffff9c54 99359c54
c4bc9ec4 ffffffffffffffc4 c4bc9ec4
b6fe22ae ffffffffffffffae b6fe22ae
45da4c38 ffffffffffda4c38 45da4c38
c88f5faf ffffffffffffffaf c88f5faf
7e45efe8 ffffffffffffffe8 7e45efe8
94c41ade ffffffffffffffde 94c41ade
b4e3c54f86 ffffffffffffff86 b4e3c54f86
b60419a301 ffffffffffffa301 b60419a301
59c748bb7e ffffffffffffbb7e 59c748bb7e
649d200092 ffffffffffffff92 649d200092
1b92cd6d7d ffffffffffcd6d7d 1b92cd6d7d
a53b475f48 ffffffa53b475f48 a53b475f48
08437a5639 8437a5639 8437a5639
7957b2be40 ffffffffffffbe40 7957b2be40
2c725e4ba9 ffffffffffffffa9 2c725e4ba9
f8e20015f8 fffffffffffffff8 f8e20015f8
61647952a3cf ffffffffffffffcf 61647952a3cf
c1a63d44671c ffffffa63d44671c c1a63d44671c
08f4f39fa3cd ffffffffffffffcd 8f4f39fa3cd
627a1e5efe40 fffffffffffffe40 627a1e5efe40
60971cf0fa75 fffffffffffffa75 60971cf0fa75
d4b76b20627c ffffffb76b20627c d4b76b20627c
ad3590466c4a ffffffff90466c4a ad3590466c4a
3d31e711953c ffffffffffff953c 3d31e711953c
71b26c7c8c98 ffffffffffffff98 71b26c7c8c98
cbadc78bf991 ffffffffffffff91 cbadc78bf991
b7aba9f5d8b006 ffffffffffffb006 b7aba9f5d8b006
e3da732bbdcc12 ffffffffffffcc12 e3da732bbdcc12
7c3919405eb1ac ffffffffffffffac 7c3919405eb1ac
5677bf994db54d ffffffffffffb54d 5677bf994db54d
e06cb024107afd fffffffffffffffd e06cb024107afd
65ff73250a89f7 fffffffffffffff7 65ff73250a89f7
abb44e062013d2 ffffffffffffffd2 abb44e062013d2
9f938d8a2c2239 ffffffff8a2c2239 9f938d8a2c2239
375e554d2506c8 ffffffffffffffc8 375e554d2506c8
90976dbbcf1cb2 ffffffffffffffb2 90976dbbcf1cb2
ACTUAL -
See expected result. The long created by the current code has many bits of the original input bytes overwritten with 1s (the output hex representation contains a lot of leading f characters). This results in loss of information in byte[] seeds.
---------- BEGIN SOURCE ----------
See 'Steps to reproduce'
---------- END SOURCE ----------
CUSTOMER SUBMITTED WORKAROUND :
None. Currently any generator created using a random byte[] will not be seeded with the full randomness of the bytes. The only other method to create generators with a RandomGeneratorFactory uses a single long seed. Thus generators can only be created with 64-bits of randomness. Using a random byte[] will generate a long[] array for seeding where only the least significant 8-bits of each long are ensured to be random. The more significant bits have an increasing chance of being set to 1s. This is 1 - 1/(2^7) = 0.9921875 for the highest 8-bits in the long if 8 bytes were used to create it (as it has 7 chances to overwrite the bits as they are shifted up).
Class: ./java.base/share/classes/jdk/internal/util/random/RandomSupport.java
Method: public static long[] convertSeedBytesToLongs(byte[] seed, int n, int z)
The method attempts to create an array of longs by consuming the input bytes most significant bit first. New bytes are appended to the existing long using the OR operator on the signed byte. Due to sign extension this will overwrite all the existing bits from 63 to 8 if the next byte is negative.
STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
The bug will not readily manifest as a poorly seeded RNG with many of the bits in the generated long[] set to 1 quickly recovers and outputs a random sequence. Reproducing cannot be done without access to the internal class RandomSupport.
I have extracted the part of the class with the bug into a driver program:
public class RandomSupport {
private static final char[] HEX_DIGITS =
{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
public static long[] convertSeedBytesToLongs(byte[] seed, int n, int z) {
final long[] result = new long[n];
final int m = Math.min(seed.length, n << 3);
// Distribute seed bytes into the words to be formed.
for (int j = 0; j < m; j++) {
// Sign extension bug
result[j >> 3] = (result[j >> 3] << 8) | seed[j];
}
// Filling the rest of the long[] has been removed for brevity.
// It only matters if the bytes are shorter than the desired length of long[].
return result;
}
public static long[] convertSeedBytesToLongsFixed(byte[] seed, int n, int z) {
final long[] result = new long[n];
final int m = Math.min(seed.length, n << 3);
// Distribute seed bytes into the words to be formed.
for (int j = 0; j < m; j++) {
result[j >> 3] = (result[j >> 3] << 8) | (seed[j] & 0xff);
}
return result;
}
public static void main(String[] args) {
RandomGenerator rng = RandomGeneratorFactory.of("L64X128MixRandom").create(42);
for (int i = 1; i < 8; i++) {
byte[] seed = new byte[i];
for (int j = 0; j < 10; j++) {
rng.nextBytes(seed);
for (byte b : seed) {
System.out.printf("%c%c", HEX_DIGITS[(b & 0xf0) >> 4], HEX_DIGITS[b & 0xf]);
}
System.out.printf(" %-16s %-16s%n",
Long.toHexString(convertSeedBytesToLongs(seed, 1, 1)[0]),
Long.toHexString(convertSeedBytesToLongsFixed(seed, 1, 1)[0]));
}
}
}
}
EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
Compile and run the driver program:
> javac RandomSupport.java
> java RandomSupport
Column: Description
1: Hex representation of the input byte[], most significant bits first
2: Current long output (hex representation)
3: Corrected long output (hex representation)
12 12 12
10 10 10
38 38 38
ec ffffffffffffffec ec
8a ffffffffffffff8a 8a
7e 7e 7e
cf ffffffffffffffcf cf
12 12 12
11 11 11
d4 ffffffffffffffd4 d4
7ae2 ffffffffffffffe2 7ae2
47c8 ffffffffffffffc8 47c8
3cc0 ffffffffffffffc0 3cc0
2475 2475 2475
fdce ffffffffffffffce fdce
7c04 7c04 7c04
16a4 ffffffffffffffa4 16a4
0bf1 fffffffffffffff1 bf1
cb22 ffffffffffffcb22 cb22
63eb ffffffffffffffeb 63eb
6d72b7 ffffffffffffffb7 6d72b7
ddd3a6 ffffffffffffffa6 ddd3a6
6194a2 ffffffffffffffa2 6194a2
d54bc0 ffffffffffffffc0 d54bc0
3142f5 fffffffffffffff5 3142f5
643056 643056 643056
ff94ba ffffffffffffffba ff94ba
86923e ffffffffffff923e 86923e
faf8f0 fffffffffffffff0 faf8f0
b69017 ffffffffffff9017 b69017
f4b40258 ffffffffffb40258 f4b40258
c099cae2 ffffffffffffffe2 c099cae2
9273a475 ffffffffffffa475 9273a475
99359c54 ffffffffffff9c54 99359c54
c4bc9ec4 ffffffffffffffc4 c4bc9ec4
b6fe22ae ffffffffffffffae b6fe22ae
45da4c38 ffffffffffda4c38 45da4c38
c88f5faf ffffffffffffffaf c88f5faf
7e45efe8 ffffffffffffffe8 7e45efe8
94c41ade ffffffffffffffde 94c41ade
b4e3c54f86 ffffffffffffff86 b4e3c54f86
b60419a301 ffffffffffffa301 b60419a301
59c748bb7e ffffffffffffbb7e 59c748bb7e
649d200092 ffffffffffffff92 649d200092
1b92cd6d7d ffffffffffcd6d7d 1b92cd6d7d
a53b475f48 ffffffa53b475f48 a53b475f48
08437a5639 8437a5639 8437a5639
7957b2be40 ffffffffffffbe40 7957b2be40
2c725e4ba9 ffffffffffffffa9 2c725e4ba9
f8e20015f8 fffffffffffffff8 f8e20015f8
61647952a3cf ffffffffffffffcf 61647952a3cf
c1a63d44671c ffffffa63d44671c c1a63d44671c
08f4f39fa3cd ffffffffffffffcd 8f4f39fa3cd
627a1e5efe40 fffffffffffffe40 627a1e5efe40
60971cf0fa75 fffffffffffffa75 60971cf0fa75
d4b76b20627c ffffffb76b20627c d4b76b20627c
ad3590466c4a ffffffff90466c4a ad3590466c4a
3d31e711953c ffffffffffff953c 3d31e711953c
71b26c7c8c98 ffffffffffffff98 71b26c7c8c98
cbadc78bf991 ffffffffffffff91 cbadc78bf991
b7aba9f5d8b006 ffffffffffffb006 b7aba9f5d8b006
e3da732bbdcc12 ffffffffffffcc12 e3da732bbdcc12
7c3919405eb1ac ffffffffffffffac 7c3919405eb1ac
5677bf994db54d ffffffffffffb54d 5677bf994db54d
e06cb024107afd fffffffffffffffd e06cb024107afd
65ff73250a89f7 fffffffffffffff7 65ff73250a89f7
abb44e062013d2 ffffffffffffffd2 abb44e062013d2
9f938d8a2c2239 ffffffff8a2c2239 9f938d8a2c2239
375e554d2506c8 ffffffffffffffc8 375e554d2506c8
90976dbbcf1cb2 ffffffffffffffb2 90976dbbcf1cb2
ACTUAL -
See expected result. The long created by the current code has many bits of the original input bytes overwritten with 1s (the output hex representation contains a lot of leading f characters). This results in loss of information in byte[] seeds.
---------- BEGIN SOURCE ----------
See 'Steps to reproduce'
---------- END SOURCE ----------
CUSTOMER SUBMITTED WORKAROUND :
None. Currently any generator created using a random byte[] will not be seeded with the full randomness of the bytes. The only other method to create generators with a RandomGeneratorFactory uses a single long seed. Thus generators can only be created with 64-bits of randomness. Using a random byte[] will generate a long[] array for seeding where only the least significant 8-bits of each long are ensured to be random. The more significant bits have an increasing chance of being set to 1s. This is 1 - 1/(2^7) = 0.9921875 for the highest 8-bits in the long if 8 bytes were used to create it (as it has 7 chances to overwrite the bits as they are shifted up).
- relates to
-
JDK-8294509 The sign extension bug applies to 'public static int[] convertSeedBytesToInts(byte[] seed, int n, int z)' in RandomSupport
- Closed