You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "jcwinters (via GitHub)" <gi...@apache.org> on 2025/05/08 01:58:57 UTC
[PR] LANG-1772 restrict size of cache to prevent overflow errors [commons-lang]
jcwinters opened a new pull request, #1379:
URL: https://github.com/apache/commons-lang/pull/1379
Added a length restriction to `RandomStringutils`, limiting the cache to 60M entries. Because of rejections the bitIndex in the underling cache can overflow when right shifting. Also added a test to verify the fix.
This test takes quite a while to run, so if necessary I can create a profile for slow tests to exclude the test from the normal build.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "jcwinters (via GitHub)" <gi...@apache.org>.
jcwinters commented on PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#issuecomment-2896502012
I believe I've now incorporated most of the suggestions (I didn't use constants for the divide by 3 for instance) - sorry for the length of time this has taken
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "ppkarwasz (via GitHub)" <gi...@apache.org>.
ppkarwasz commented on code in PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#discussion_r2103834348
##########
src/main/java/org/apache/commons/lang3/RandomStringUtils.java:
##########
@@ -329,7 +333,16 @@ public static String random(int count, int start, int end, final boolean letters
// Ideally the cache size depends on multiple factor, including the cost of generating x bytes
// of randomness as well as the probability of rejection. It is however not easy to know
// those values programmatically for the general case.
- final CachedRandomBits arb = new CachedRandomBits((count * gapBits + 3) / 5 + 10, random);
+ // Calculate cache size:
+ // 1. Multiply count by bits needed per character (gapBits)
+ // 2. Add padding bits (3) to handle partial bytes
+ // 3. Divide by 5 to convert to bytes (normally this would be by 8, dividing by 5 allows for about 60% extra space)
+ // 4. Add base padding (10) to handle small counts efficiently
+ // 5. Ensure we don't exceed Integer.MAX_VALUE / 5 + 10 to provide a good balance between overflow prevention and
+ // making the cache extremely large
+ final long desiredCacheSize = ((long) count * gapBits + CACHE_PADDING_BITS) / BITS_TO_BYTES_DIVISOR + BASE_CACHE_SIZE_PADDING;
+ final int cacheSize = Math.min((int) desiredCacheSize, Integer.MAX_VALUE / BITS_TO_BYTES_DIVISOR + BASE_CACHE_SIZE_PADDING);
Review Comment:
Should the cast to `int` be outside of `Math.min`? By casting a positive `long` to `int`, you can obtain both positive and negative values. I would suggest to cast after we are sure the value is in the range of `int`:
```suggestion
final int cacheSize = (int) Math.min(desiredCacheSize, Integer.MAX_VALUE / BITS_TO_BYTES_DIVISOR + BASE_CACHE_SIZE_PADDING);
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "ppkarwasz (via GitHub)" <gi...@apache.org>.
ppkarwasz commented on code in PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#discussion_r2086199080
##########
src/main/java/org/apache/commons/lang3/RandomStringUtils.java:
##########
@@ -97,6 +97,7 @@ public class RandomStringUtils {
private static final int ASCII_9 = '9';
private static final int ASCII_A = 'A';
private static final int ASCII_z = 'z';
+ private static final int MAX_CACHE_SIZE = 60_000_000;
Review Comment:
Rejections are not a problem. Theoretically `CachedRandomBits#nextBits` should be able to produce an unlimited sequence of integers without `bitIndex` ever overflowing. The `bitIndex` counter is reset to `0` when it reaches `8 * cache.length`:
https://github.com/apache/commons-lang/blob/a41a57e58e73242c1fc5dd1f8e53bc883558331d/src/main/java/org/apache/commons/lang3/CachedRandomBits.java#L84-L90
The problem you are experiencing only occurs if `cache.length = (count * gapBits + 3) / 5 + 10` is `268_435_456` or higher. For `gapBits = 21` (i.e. no constraints on the Unicode characters to use), an overflow should happen if `count` is at least `63_913_202`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "ppkarwasz (via GitHub)" <gi...@apache.org>.
ppkarwasz commented on PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#issuecomment-2873964590
> You've proposed an alternative solution. Would you shows in a PR?
I'll submit a PR by the end of the week.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "ppkarwasz (via GitHub)" <gi...@apache.org>.
ppkarwasz commented on PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#issuecomment-2887585781
> Where are we on this one? @ppkarwasz do you still plan on providing an alternative solution?
This pull request appears to be nearly ready. It includes the following changes:
- Sets the maximum size of the internal `CachedRandomBits` class to `Integer.MAX_VALUE / 8`.
- Limits the maximum requested size for `CachedRandomBits` to approximately `Integer.MAX_VALUE / 5`.
I could switch the `bitIndex` field to `long`, which would allow increasing the maximum size of `CachedRandomBits` up to `Integer.MAX_VALUE`. However, it's unclear whether this would provide any practical benefit. A benchmark would likely show that caching such a large number of random bits offers no significant performance advantage.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory commented on PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#issuecomment-2862752705
The test as is blows up GitHub builds so let's use something like `@EnabledIfSystemProperty(named = "test.large.heap", matches = "true")`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory commented on PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#issuecomment-2897927983
Hi @jcwinters
I still don't understand what the magic numbers mean, so constants with comments or a better code comment is needed IMO.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "jcwinters (via GitHub)" <gi...@apache.org>.
jcwinters commented on PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#issuecomment-2863478821
> A simpler solution would be to:
>
> * Change the type of `bitIndex` to `long`, so it can count up to `8 * Integer.MAX_VALUE`
> * Refactor the expression that computes the `cacheSize` argument in a way that it does not overflow:
>
I considered that, changing `bitindex` to long adds some casting complexity I didn't want to deal with as arrays are int indexed. And I didn't particularly want to change the randomization algorithm, as to get rid of overflow possibilities I'd have to change to something that doesn't have rejections, and it made my head hurt.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory commented on PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#issuecomment-2897919250
Hi @jcwinters,
No need to apologize, we're all busy 😃
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory merged PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory commented on PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#issuecomment-2876712217
@jcwinters
Please 'mvn' by itself before you push to catch all build errors.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] LANG-1772 restrict size of cache to prevent overflow errors [commons-lang]
Posted by "ppkarwasz (via GitHub)" <gi...@apache.org>.
ppkarwasz commented on PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#issuecomment-2862166291
> Added a length restriction to `RandomStringutils`, limiting the cache to 60M entries. Because of rejections the bitIndex in the underling cache can overflow when right shifting. Also added a test to verify the fix.
The problem is caused by an integer overflow of `bitIndex` in:
https://github.com/apache/commons-lang/blob/a511a163b579fdaafa81fb6ca908034d32291871/src/main/java/org/apache/commons/lang3/CachedRandomBits.java#L95
A simpler solution would be to:
- Change the type of `bitIndex` to `long`, so it can count up to `8 * Integer.MAX_VALUE`
- Refactor the expression that computes the `cacheSize` argument in a way that it does not overflow:
https://github.com/apache/commons-lang/blob/a511a163b579fdaafa81fb6ca908034d32291871/src/main/java/org/apache/commons/lang3/RandomStringUtils.java#L332
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "ppkarwasz (via GitHub)" <gi...@apache.org>.
ppkarwasz commented on code in PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#discussion_r2086790446
##########
src/main/java/org/apache/commons/lang3/CachedRandomBits.java:
##########
@@ -52,6 +52,16 @@ final class CachedRandomBits {
*/
private int bitIndex;
+ /**
+ * The maximum size of the cache.
+ *
+ * <p>
+ * This is dictated by the {@code if (bitIndex >> 3 >= cache.length)} in the {@link #nextBits(int)} method.
+ * Essentially {@code 63_913_202 << 3 } will overflow so this line will never evaluate to true.
+ * At some point the {@code bitIndex += generatedBitsInIteration} will overflow and cause an exception.
+ */
+ private static final int MAX_CACHE_SIZE = 63_913_200;
Review Comment:
The value here should rather be `0x1FFF_FFFF` (i.e. `268_435_455`, but in hex it is easier to understand).
`63_913_201` is the highest `x` such that `(21x + 3) / 5 + 10 ≤ 268 435 455`.
##########
src/main/java/org/apache/commons/lang3/RandomStringUtils.java:
##########
@@ -330,8 +329,8 @@ public static String random(int count, int start, int end, final boolean letters
// Ideally the cache size depends on multiple factor, including the cost of generating x bytes
// of randomness as well as the probability of rejection. It is however not easy to know
// those values programmatically for the general case.
- // To prevent overflow restrict the cache size to 60M entries (
- final int cacheSize = Math.min ((count * gapBits + 3) / 5 + 10, MAX_CACHE_SIZE);
+ // For huge strings the padding required can cause an overflow
+ final int cacheSize = (count * gapBits + 3) / 5 + 10 > 0 ? (count * gapBits + 3) / 5 + 10 : Integer.MAX_VALUE;
Review Comment:
```suggestion
final int cacheSize = count * gapBits + 3 > 0 ? (count * gapBits + 3) / 5 + 10 : Integer.MAX_VALUE;
```
Adding `10` can transform a negative number into a small positive one.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "ppkarwasz (via GitHub)" <gi...@apache.org>.
ppkarwasz commented on code in PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#discussion_r2085485496
##########
src/main/java/org/apache/commons/lang3/RandomStringUtils.java:
##########
@@ -97,6 +97,7 @@ public class RandomStringUtils {
private static final int ASCII_9 = '9';
private static final int ASCII_A = 'A';
private static final int ASCII_z = 'z';
+ private static final int MAX_CACHE_SIZE = 60_000_000;
Review Comment:
This value is also much lower than the value that makes `bitIndex` overflow. The first forbidden value is `2^28 = 268_435_456`, so values up to `0x1fff ffff` should be allowed.
**Note**: The expression `(count * gapBits + 3) / 5 + 10` overflows if `count` exceeds `(2^31 - 1 - 3) / 21 = 102_261_125`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory commented on code in PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#discussion_r2085058140
##########
src/main/java/org/apache/commons/lang3/RandomStringUtils.java:
##########
@@ -97,6 +97,7 @@ public class RandomStringUtils {
private static final int ASCII_9 = '9';
private static final int ASCII_A = 'A';
private static final int ASCII_z = 'z';
+ private static final int MAX_CACHE_SIZE = 60_000_000;
Review Comment:
This value seems arbitrary. The constant should have a Javadoc even if it only says this is a completely arbitrary choice or serves some defined use case.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "ppkarwasz (via GitHub)" <gi...@apache.org>.
ppkarwasz commented on code in PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#discussion_r2100949198
##########
src/main/java/org/apache/commons/lang3/RandomStringUtils.java:
##########
@@ -329,7 +329,10 @@ public static String random(int count, int start, int end, final boolean letters
// Ideally the cache size depends on multiple factor, including the cost of generating x bytes
// of randomness as well as the probability of rejection. It is however not easy to know
// those values programmatically for the general case.
- final CachedRandomBits arb = new CachedRandomBits((count * gapBits + 3) / 5 + 10, random);
+ // For huge strings the padding required can cause an overflow
+ // 63_913_201 is the highest x such that (21x + 3) / 5 + 10 < 0x0FFF_FFFF.
+ final long cacheSize = Math.min((count * gapBits + 3) / 5 + 10, Integer.MAX_VALUE / 5);
Review Comment:
```suggestion
final long cacheSize = Math.min((long) count * gapBits + 3, Integer.MAX_VALUE) / 5 + 10;
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "jcwinters (via GitHub)" <gi...@apache.org>.
jcwinters commented on code in PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#discussion_r2086810278
##########
src/main/java/org/apache/commons/lang3/RandomStringUtils.java:
##########
@@ -97,6 +97,7 @@ public class RandomStringUtils {
private static final int ASCII_9 = '9';
private static final int ASCII_A = 'A';
private static final int ASCII_z = 'z';
+ private static final int MAX_CACHE_SIZE = 60_000_000;
Review Comment:
Yep I agree with that number :-) And as you say if we get rid of overflow this wouldn't be an issue. It would be easy enough to swap the bit shift for a /, but I suspect the efficiency loss makes it not viable. Anyway I've updated the PR, and I look forward to seeing yours
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory commented on PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#issuecomment-2887557770
Hi all,
Where are we on this one? @ppkarwasz do you still plan on providing an alternative solution?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "jcwinters (via GitHub)" <gi...@apache.org>.
jcwinters commented on code in PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#discussion_r2086153654
##########
src/main/java/org/apache/commons/lang3/RandomStringUtils.java:
##########
@@ -97,6 +97,7 @@ public class RandomStringUtils {
private static final int ASCII_9 = '9';
private static final int ASCII_A = 'A';
private static final int ASCII_z = 'z';
+ private static final int MAX_CACHE_SIZE = 60_000_000;
Review Comment:
Yes but that ignores rejections, `next()` is called every time we evaluate a candidate bit pattern, some of them are rejected. In my testing (10000 runs) that rejection happens between 62 and 62.4M times. To be honest there is probably a very small chance of overflow even at 60M if the rejection rate is statistically high.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "jcwinters (via GitHub)" <gi...@apache.org>.
jcwinters commented on PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#issuecomment-2900276181
I think I'm there now
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [LANG-1772] Restrict size of cache to prevent overflow errors [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory commented on PR #1379:
URL: https://github.com/apache/commons-lang/pull/1379#issuecomment-2873250469
Hi @ppkarwasz
You've proposed an alternative solution. Would you shows in a PR?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org