[
https://issues.apache.org/jira/browse/SPARK-58708?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
sepuri sai krishna updated SPARK-58708:
---------------------------------------
Summary: substring/lpad/rpad mishandle out-of-range length arguments (was:
BINARY substring/lpad/rpad mishandle out-of-range length arguments)
> substring/lpad/rpad mishandle out-of-range length arguments
> -----------------------------------------------------------
>
> Key: SPARK-58708
> URL: https://issues.apache.org/jira/browse/SPARK-58708
> Project: Spark
> Issue Type: Bug
> Components: SQL
> Affects Versions: 4.2.0
> Reporter: sepuri sai krishna
> Priority: Major
> Labels: pull-request-available
>
> {{ByteArray}} backs the BINARY overloads of {{substring()}}, {{lpad()}} and
> {{rpad()}}, and it does not validate its length argument the way the STRING
> implementations in {{UTF8String}} do. Three problems fall out of that. All
> are reachable from plain SQL with default configuration, on both the
> interpreted and codegen paths.
> h3. 1. Integer overflow in {{ByteArray.subStringSQL}} can allocate a huge
> array
> {{Substring}} dispatches BINARY input to {{ByteArray.subStringSQL}}. The end
> offset is computed in {{int}} arithmetic:
> {code:java}
> if ((bytes.length - start) < len) { // overflows when len is large negative
> end = bytes.length;
> } else {
> end = start + len; // overflows when start + len >
> Integer.MAX_VALUE
> }
> start = Math.max(start, 0); // start clamped only AFTER it was used
> above
> if (start >= end) {
> return EMPTY_BYTE;
> }
> return Arrays.copyOfRange(bytes, start, end);
> {code}
> When {{start}} is still negative, {{bytes.length - start}} overflows to a
> negative value, so the {{end = bytes.length}} clamp is skipped and {{end}}
> keeps an out-of-range value. {{Arrays.copyOfRange}} accepts an end past the
> array length and zero-pads the remainder, so the call silently returns a
> large array of zero bytes rather than an error or an empty result.
> {code:sql}
> -- 9-byte binary input
> SELECT length(substring(CAST('Spark SQL' AS BINARY), -1207959552,
> -1207959552));
> -- actual: 1879048201 (a 1.75 GiB array of mostly zero bytes)
> -- expected: 0
> SELECT substring(CAST('Spark SQL' AS BINARY), -2147483648, 5);
> -- actual: the whole 9-byte input
> -- expected: empty
> {code}
> The equivalent STRING expressions return {{''}} for both. This is both a
> wrong-results bug and a memory-safety concern: the allocation size is driven
> by user-supplied arguments and is unrelated to the size of the input, so a
> modestly sized query can allocate gigabytes and OOM the executor.
> The STRING path was fixed for this class of overflow in SPARK-32115, but
> {{ByteArray.subStringSQL}}, added later by SPARK-28412, was never brought in
> line even though its comment says the offsets are computed "according to
> UTF8String#subStringSQL".
> A differential test of {{ByteArray.subStringSQL}} against
> {{UTF8String.substringSQL}} as an oracle over 3125 (input, pos, len)
> combinations reports *239 mismatches* on current master.
> h3. 2. {{ByteArray.lpad}} / {{ByteArray.rpad}} throw
> {{NegativeArraySizeException}} on negative length
> {{BinaryPad}} rewrites to {{StaticInvoke(classOf[ByteArray], "lpad" |
> "rpad")}}. Those methods guard only the exact value zero before allocating:
> {code:java}
> if (len == 0) return EMPTY_BYTE;
> ...
> final byte[] result = new byte[len]; // negative len ->
> NegativeArraySizeException
> {code}
> {{padWithEmptyPattern}} has the same problem via {{len =
> Math.min(bytes.length, len)}}, which preserves a negative {{len}}.
> {code:sql}
> SELECT lpad(CAST('hi' AS BINARY), -1, CAST('??' AS BINARY));
> -- actual: java.lang.NegativeArraySizeException: -1
> -- expected: empty binary
> {code}
> The STRING overloads return {{''}} for most non-positive lengths, but not all
> -- see section 3. Besides the STRING/BINARY inconsistency,
> {{NegativeArraySizeException}} is a raw JVM exception rather than a
> {{SparkThrowable}}, so it surfaces with no error class and no error message
> framework context.
> Reproducible with any negative length, and with both an empty and a non-empty
> pad. Introduced by SPARK-37047, which added the BINARY overloads.
> h3. 3. {{UTF8String.lpad}} / {{UTF8String.rpad}} fail for {{len ==
> Integer.MIN_VALUE}}
> While confirming the STRING/BINARY difference above, the same class of
> overflow turned up on the STRING side as well. Both methods start with:
> {code:java}
> int spaces = len - this.numChars();
> if (spaces <= 0 || pad.numBytes() == 0) {
> return substring(0, len); // the empty string for any non-positive len
> }
> {code}
> For {{len == Integer.MIN_VALUE}} the subtraction wraps to a large positive
> value, so the non-positive case is missed and the padding branch runs
> instead. It is caught downstream by {{Math.toIntExact}} when the result size
> is computed:
> {code:sql}
> SELECT lpad('hello', -2147483648, '??');
> -- actual: java.lang.ArithmeticException: integer overflow
> -- expected: empty string
> {code}
> Every other non-positive length returns {{''}} as documented. As in section
> 2, {{ArithmeticException}} is a raw JVM exception rather than a
> {{SparkThrowable}}.
> h3. Proposed fix
> * {{ByteArray.subStringSQL}}: compute the end offset in {{long}}, clamp it to
> {{bytes.length}}, and clamp {{start}} to 0 only after it has been used. With
> that change the 3125-case differential test above reports *0 mismatches*
> against the {{UTF8String}} oracle.
> * {{ByteArray.lpad}} / {{ByteArray.rpad}}: treat any non-positive length as
> empty, i.e. {{len <= 0}} instead of {{len == 0}}. This also makes
> {{padWithEmptyPattern}} unreachable with a non-positive length.
> * {{UTF8String.lpad}} / {{UTF8String.rpad}}: return the empty string up front
> for {{len <= 0}}, before the wrapping subtraction is evaluated.
> With all three in place, a non-positive length yields the empty value for
> STRING and BINARY alike, across the whole {{int}} range, and no argument
> combination can produce a result longer than the input.
> h3. Impact
> Default configuration, no flags involved. Affects the interpreted and codegen
> paths equally, and both SQL and the DataFrame API. Wrong results in the first
> case (with a potential executor OOM driven by user-supplied arguments), and
> unclassified JVM exceptions in the other two.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
