[
https://issues.apache.org/jira/browse/SPARK-58708?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
sepuri sai krishna updated SPARK-58708:
---------------------------------------
Description:
{{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.
was:
{{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. Two independent problems fall out of
that. Both 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 any non-positive length. 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. Proposed fix
Both are localized to {{ByteArray}}:
* {{subStringSQL}}: compute the end offset in {{long}}, clamp it to
{{bytes.length}}, and clamp {{start}} to 0 before it is used in any comparison.
With that change the 3125-case differential test above reports *0 mismatches*
against the {{UTF8String}} oracle.
* {{lpad}} / {{rpad}} / {{padWithEmptyPattern}}: treat any non-positive length
as empty, i.e. {{len <= 0}} instead of {{len == 0}}, matching {{UTF8String}}.
In both cases the intended behaviour is simply to match the existing,
already-correct STRING semantics, so no new user-visible behaviour is being
invented.
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 an
unclassified JVM exception in the second.
> BINARY 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
>
> {{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]
