[
https://issues.apache.org/jira/browse/LANG-1814?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Ivan Ponomarev updated LANG-1814:
---------------------------------
Description:
{{ArrayUtils.subarray(.., int startIndexInclusive, int endIndexExclusive)}}
(the full family of overloads for different array types) is documented to
return an empty array when {{{}endIndexExclusive < startIndexInclusive{}}}:
{quote}“Undervalue (< startIndex) produces empty array.”
{quote}
However, for certain extreme combinations of indices the method violates this
contract due to subtraction overflow in index arithmetic. After clamping:
* {{startIndexInclusive}} is promoted to {{>= 0}}
* {{endIndexExclusive}} is only clamped to {{{}<= array.length{}}}, but may
remain negative
The method then computes:
{{final int newSize = endIndexExclusive - startIndexInclusive;}}
This subtraction is performed in {{int}} and may overflow, turning a logically
negative size into a positive value. As a result, the method attempts to
allocate and/or copy an array instead of returning an empty result.
*Observed failure modes*
Depending on the overflowed value and available heap size, this leads to:
* {{ArrayIndexOutOfBoundsException}} (small positive overflow, allocation
succeeds, copy fails)
* {{OutOfMemoryError}} (large positive overflow, allocation attempt fails)
{{*Reproducer*}}
@ParameterizedTest
@CsvSource({
// Normal operation
"2, 1",
// Overflowed to newSize == 1 (AIOOBE)
"2147483647, -2147483648",
// Overflowed to a large positive newSize (OOME)
"2000000000, -2000000000"
})
void testNegativeEndAndHugeStartDoesNotOverflow(int startIndexInclusive,
int endIndexExclusive) {
int[] array = \{1, 2, 3};
int[] result = ArrayUtils.subarray(array, startIndexInclusive,
endIndexExclusive);
assertEquals(0, result.length);
}
{{ }}
{{(For all inputs where {{{}endIndexExclusive < startIndexInclusive{}}}, the
method should return an empty array as documented, however, the method may
throw {{ArrayIndexOutOfBoundsException}} or {{OutOfMemoryError}} instead of
returning an empty array.)}}
*Proposed Fix*
For all {{ArrayUtils.subarray(..)}} overloads, ensure {{endIndexExclusive}} is
clamped to the same lower bound as {{startIndexInclusive}} before subtraction:
{{endIndexExclusive = {*}max0{*}(Math.min(endIndexExclusive, array.length));}}
{{int newSize = endIndexExclusive - startIndexInclusive; }}
This guarantees:
* {{0 <= endIndexExclusive}} < {{array.length}}
* {{newSize}} cannot overflow
* {{newSize <= 0}} correctly triggers an empty array return
was:
{{ArrayUtils.subarray(.., int startIndexInclusive, int endIndexExclusive)}}
(the full family of overloads for different array types) is documented to
return an empty array when {{{}endIndexExclusive < startIndexInclusive{}}}:
{quote}“Undervalue (< startIndex) produces empty array.”
{quote}
However, for certain extreme combinations of indices the method violates this
contract due to subtraction overflow in index arithmetic. After clamping:
* {{startIndexInclusive}} is promoted to {{>= 0}}
* {{endIndexExclusive}} is only clamped to {{{}<= array.length{}}}, but may
remain negative
The method then computes:
{{final int newSize = endIndexExclusive - startIndexInclusive;}}
This subtraction is performed in {{int}} and may overflow, turning a logically
negative size into a positive value. As a result, the method attempts to
allocate and/or copy an array instead of returning an empty result.
*Observed failure modes*
Depending on the overflowed value and available heap size, this leads to:
* {{ArrayIndexOutOfBoundsException}} (small positive overflow, allocation
succeeds, copy fails)
* {{OutOfMemoryError}} (large positive overflow, allocation attempt fails)
*Reproducer*
{color:#9e880d}@ParameterizedTest
{color}{color:#9e880d}@CsvSource{color}({
{color:#8c8c8c}// Normal operation
{color}{color:#8c8c8c} {color}{color:#067d17}"2, 1"{color},
{color:#8c8c8c}// Overflowed to newSize == 1 (AIOOBE)
{color}{color:#8c8c8c} {color}{color:#067d17}"2147483647, -2147483648"{color},
{color:#8c8c8c}// Overflowed to a large positive newSize (OOME)
{color}{color:#8c8c8c} {color}{color:#067d17}"2000000000, -2000000000"
{color}})
{color:#0033b3}void
{color}{color:#00627a}testNegativeEndAndHugeStartDoesNotOverflow{color}({color:#0033b3}int
{color}{color:#000000}startIndexInclusive{color}, {color:#0033b3}int
{color}{color:#000000}endIndexExclusive{color}) {
{color:#0033b3}int{color}[] {color:#000000}array {color}=
{{color:#1750eb}1{color}, {color:#1750eb}2{color}, {color:#1750eb}3{color}};
{color:#0033b3}int{color}[] {color:#000000}result {color}=
{color:#000000}ArrayUtils{color}.subarray({color:#000000}array{color},
{color:#000000}startIndexInclusive{color},
{color:#000000}endIndexExclusive{color});
assertEquals({color:#1750eb}0{color},
{color:#000000}result{color}.{color:#871094}length{color});
}
(For all inputs where {{{}endIndexExclusive < startIndexInclusive{}}}, the
method should return an empty array as documented, however, the method may
throw {{ArrayIndexOutOfBoundsException}} or {{OutOfMemoryError}} instead of
returning an empty array.)
*Proposed Fix*
For all {{ArrayUtils.subarray(..)}} overloads, ensure {{endIndexExclusive}} is
clamped to the same lower bound as {{startIndexInclusive}} before subtraction:
{{endIndexExclusive = {*}max0{*}(Math.min(endIndexExclusive, array.length));}}
{{int newSize = endIndexExclusive - startIndexInclusive; }}
This guarantees:
* {{0 <= endIndexExclusive}} < {{array.length}}
* {{newSize}} cannot overflow
* {{newSize <= 0}} correctly triggers an empty array return
> ArrayUtils.subarray(..) may overflow index arithmetic and violate contract
> for extreme index values
> ---------------------------------------------------------------------------------------------------
>
> Key: LANG-1814
> URL: https://issues.apache.org/jira/browse/LANG-1814
> Project: Commons Lang
> Issue Type: Bug
> Components: lang.*
> Reporter: Ivan Ponomarev
> Priority: Trivial
>
> {{ArrayUtils.subarray(.., int startIndexInclusive, int endIndexExclusive)}}
> (the full family of overloads for different array types) is documented to
> return an empty array when {{{}endIndexExclusive < startIndexInclusive{}}}:
> {quote}“Undervalue (< startIndex) produces empty array.”
> {quote}
> However, for certain extreme combinations of indices the method violates this
> contract due to subtraction overflow in index arithmetic. After clamping:
> * {{startIndexInclusive}} is promoted to {{>= 0}}
> * {{endIndexExclusive}} is only clamped to {{{}<= array.length{}}}, but may
> remain negative
> The method then computes:
>
> {{final int newSize = endIndexExclusive - startIndexInclusive;}}
> This subtraction is performed in {{int}} and may overflow, turning a
> logically negative size into a positive value. As a result, the method
> attempts to allocate and/or copy an array instead of returning an empty
> result.
> *Observed failure modes*
> Depending on the overflowed value and available heap size, this leads to:
> * {{ArrayIndexOutOfBoundsException}} (small positive overflow, allocation
> succeeds, copy fails)
> * {{OutOfMemoryError}} (large positive overflow, allocation attempt fails)
> {{*Reproducer*}}
> @ParameterizedTest
> @CsvSource({
> // Normal operation
> "2, 1",
> // Overflowed to newSize == 1 (AIOOBE)
> "2147483647, -2147483648",
> // Overflowed to a large positive newSize (OOME)
> "2000000000, -2000000000"
> })
> void testNegativeEndAndHugeStartDoesNotOverflow(int startIndexInclusive,
> int endIndexExclusive) {
> int[] array = \{1, 2, 3};
> int[] result = ArrayUtils.subarray(array, startIndexInclusive,
> endIndexExclusive);
> assertEquals(0, result.length);
> }
> {{ }}
> {{(For all inputs where {{{}endIndexExclusive < startIndexInclusive{}}}, the
> method should return an empty array as documented, however, the method may
> throw {{ArrayIndexOutOfBoundsException}} or {{OutOfMemoryError}} instead of
> returning an empty array.)}}
> *Proposed Fix*
> For all {{ArrayUtils.subarray(..)}} overloads, ensure {{endIndexExclusive}}
> is clamped to the same lower bound as {{startIndexInclusive}} before
> subtraction:
>
> {{endIndexExclusive = {*}max0{*}(Math.min(endIndexExclusive, array.length));}}
> {{int newSize = endIndexExclusive - startIndexInclusive; }}
> This guarantees:
> * {{0 <= endIndexExclusive}} < {{array.length}}
> * {{newSize}} cannot overflow
> * {{newSize <= 0}} correctly triggers an empty array return
>
>
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
