Skip to content

GH-51222: [C++] Fix integer overflows in binary_slice - #52451

Open
Dricmoy wants to merge 4 commits into
apache:mainfrom
Dricmoy:gh-51222-binary-slice-overflow
Open

GH-51222: [C++] Fix integer overflows in binary_slice#52451
Dricmoy wants to merge 4 commits into
apache:mainfrom
Dricmoy:gh-51222-binary-slice-overflow

Conversation

@Dricmoy

@Dricmoy Dricmoy commented Oct 8, 2026 •
edited
Loading

Copy link
Copy Markdown
Contributor

Rationale for this change

binary_slice uses INT64_MAX as its default stop, and several internal calculations used start, stop and step directly. With large values they overflowed. That caused ArrowInvalid: Negative buffer resize for valid calls like binary_slice(values, 1), wrong output, and crashes in release builds (e.g. step=INT64_MIN).

Closes #51222.

What changes are included in this PR?

  • Size estimate: MaxSliceBytes clamps start/stop to [-len - 1, len], and NumSelectedBytes computes ceil(span / |step|) without overflow.
  • Backward range: SliceBackwardRange clamps before adding 1.
  • Copy loops: they stop before advancing the pointer past the end.
  • Fixed-size binary: FixedOutputSize uses NumSelectedBytes.

The slicing rules and public API are unchanged.

Are these changes tested?

Yes. Cases with INT64_MIN/INT64_MAX start, stop and step are added to the existing binary and fixed-size-binary slice tests. arrow-compute-scalar-type-test passes under ASan + UBSan.

Are there any user-facing changes?

binary_slice with extreme start/stop/step returns the correct slice instead of raising, returning wrong bytes, or crashing.

This PR contains a "Critical Fix". binary_slice could return incorrect data or crash for valid SliceOptions with extreme start/stop/step.

utf8_slice_codeunits has a similar overflow, tracked separately in #55509.

Was AI used for this PR?

In accordance to the AI generation guidelines, please disclose below whether and how AI was used in this PR.

Yes. OpenAI Codex helped with the initial fix. Claude helped find the remaining overflow paths and write the follow-up change and tests. I reviewed all of it and take responsibility for the contribution.

PR code and description written by:

  • Human
  • AI

Reviewed before submission by:

  • Human
  • AI
  • Not reviewed

@github-actions

github-actions Bot commented Oct 8, 2026

Copy link
Copy Markdown

⚠️ GitHub issue #51222 has no components, please add labels for components.

pitrou
pitrou requested changes Oct 13, 2026
View reviewed changes

@pitrou pitrou left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks for the PR @Dricmoy . Here are a couple comments.

Comment thread cpp/src/arrow/compute/kernels/scalar_string_ascii.cc Resolved
Comment thread cpp/src/arrow/compute/kernels/scalar_string_test.cc Resolved
@Dricmoy
Dricmoy requested a review from pitrou October 16, 2026 19:54
dmitry-chirkov-dremio
dmitry-chirkov-dremio reviewed Oct 17, 2026
View reviewed changes
Comment thread cpp/src/arrow/compute/kernels/scalar_string_ascii.cc Outdated
// SliceOptions uses INT64_MIN/MAX for open-ended bounds. Clamp stop before
// arithmetic so equivalent out-of-range indices cannot overflow the size estimate.
const int64_t stop = std::clamp(opt.stop, -input_bytes, input_bytes);
int64_t max_slice_bytes = (stop - opt.start + opt.step - 1) / opt.step;

@dmitry-chirkov-dremio dmitry-chirkov-dremio Oct 17, 2026

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This fixes the default stop case, but the calculation can still overflow with valid values.
Check start=INT64_MIN, stop=-1, and step=1 overflows at INT64_MAX + 1.

dmitry-chirkov-dremio
dmitry-chirkov-dremio suggested changes Oct 21, 2026
View reviewed changes
Comment thread cpp/src/arrow/compute/kernels/scalar_string_ascii.cc Outdated
// before arithmetic so equivalent out-of-range indices cannot overflow the size estimate.
const int64_t start = std::clamp(opt.start, -input_bytes, input_bytes);
const int64_t stop = std::clamp(opt.stop, -input_bytes, input_bytes);
int64_t max_slice_bytes = (stop - start + opt.step - 1) / opt.step;

@dmitry-chirkov-dremio dmitry-chirkov-dremio Oct 21, 2026

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Check: input "abc", start=1, the default stop, and step=INT64_MAX

The code around here is short, but the arithmetic is fragile. See if you can separate out boundary checks although this might as well be "one last boundary to enforce"...

@Dricmoy
Dricmoy force-pushed the gh-51222-binary-slice-overflow branch from 61c9a9c to 6c0d83f Compare November 11, 2026 22:18
@Dricmoy

Dricmoy commented Nov 11, 2026 •
edited
Loading

Copy link
Copy Markdown
Contributor Author

Thanks for the reviews. Updated and rebased onto main:

  • The size estimate is split into MaxSliceBytes (clamps start/stop) and NumSelectedBytes (ceil(span / |step|) without overflow). This fixes the "abc", start=1, step=INT64_MAX case.
  • The lower clamp is now -len - 1, not -len, since that's "before the first byte" when slicing backward.
  • The same overflow is also fixed in SliceBackwardRange, both copy loops and FixedOutputSize.
  • Tests are added to the existing per-sign tests.

Tested with ASan + UBSan. I also ran a local, uncommitted comparison against Python slice semantics over ~20k start/stop/step combinations.

AI disclosure: I used Claude to find the remaining overflow paths and to draft the change and tests. I've reviewed all of it.

utf8_slice_codeunits has the same + step - 1 overflow. I'll file a separate issue for it.

@Dricmoy Dricmoy mentioned this pull request Nov 11, 2026
Open
@Dricmoy Dricmoy changed the title GH-51222: [C++] Avoid overflow in binary_slice output sizing GH-51222: [C++] Fix integer overflows in binary_slice Nov 11, 2026
dmitry-chirkov-dremio
dmitry-chirkov-dremio approved these changes Nov 13, 2026
View reviewed changes

@dmitry-chirkov-dremio dmitry-chirkov-dremio left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Lgtm. My earlier feedback is addressed. @pitrou's too it seems?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@pitrou pitrou Awaiting requested review from pitrou
1 more reviewer
@dmitry-chirkov-dremio dmitry-chirkov-dremio dmitry-chirkov-dremio approved these changes
Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

Component: C++

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

[C++] binary_slice with its default stop raises "Negative buffer resize"

4 participants

@Dricmoy @pitrou @dmitry-chirkov-dremio @raulcd