Ivan Ponomarev created LANG-1814:
------------------------------------
Summary: 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
{{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
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
