Skip to content

Reformulated some pointer arithmetic to avoid (unsigned) overflow#23567

Merged
asmorkalov merged 1 commit intoopencv:4.xfrom
seanm:UBSan-overflow
May 29, 2023
Merged

Reformulated some pointer arithmetic to avoid (unsigned) overflow#23567
asmorkalov merged 1 commit intoopencv:4.xfrom
seanm:UBSan-overflow

Conversation

@seanm
Copy link
Copy Markdown
Contributor

@seanm seanm commented May 1, 2023

Although unsigned overflow is well-defined by the C++ standard, it is often unintentional or confusing and so UBSan has an option to warn about it.

It warned here:

Addition of unsigned offset to 0x00017fd31b97 overflowed to 0x00017fd30c97

In my own use of OpenCV at least, this is the only case of unsigned overflow.

I reformunated the pointer arithmetic to either add or subtract based on the sign of y. It's easier to understand this way vs always adding and wrapping around to an address smaller than the base address.

@seanm seanm force-pushed the UBSan-overflow branch from 28f2cd5 to 2df3f47 Compare May 1, 2023 22:32
@asmorkalov asmorkalov requested a review from opencv-alalek May 2, 2023 05:19
@seanm seanm force-pushed the UBSan-overflow branch 2 times, most recently from 2c78087 to 27a7a52 Compare May 15, 2023 16:30
auto ptr = src.ptr();
if (y < 0)
{
auto delta = -y*src.step;
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.

We should avoid unnecessary if branching.

does src.ptr() + y * (ssize_t)src.step work with UBSan? (to avoid unsigned value)

If no then please put this code under UBSan macro guard.

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

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

does src.ptr() + y * (ssize_t)src.step work with UBSan? (to avoid unsigned value)

That would be worse actually. signed overflow is undefined. unsigned overflow (what we have now) is actually well-defined (see my commit message).

If no then please put this code under UBSan macro guard.

I will pursue such a solution then...

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

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

@opencv-alalek please see my new solution.

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.

signed overflow is undefined

We should not have signed overflow in address arithmetic.

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

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

Actually, I've just done more reading, and in fact all pointer overflows are undefined behaviour, both signed and unsigned:

https://wdtz.org/catching-pointer-overflow-bugs.html
https://blog.regehr.org/archives/1395

Unsigned overflow is only well-defined for integers, not pointers.

Here's a simple case:

#include <cstdint>
#include <new>
#include <iostream>
#include <cassert>

int main()
{
    int* ptrStart = new int (1024);
    std::cout << "ptr start  = " << (void*)ptrStart << "\n";
    
    int* ptrEnd = ptrStart + 1024 * sizeof(int);    
    std::cout << "ptr end    = " << (void*)ptrEnd << "\n";
    
    int* ptr = ptrStart + 512; // still inside
    std::cout << "ptr offset = " << (void*)ptr << "\n";
    
    assert(ptr >= ptrStart);
    assert(ptr < ptrEnd);
    
    ptr += UINT64_MAX; // undefined
    std::cout << "ptr wrap   = " << (void*)ptr << "\n";

    assert(ptr >= ptrStart);
    assert(ptr < ptrEnd);
    
    return 0;
}

when run:

% clang++ -fsanitize=pointer-overflow test.cxx; ./a.out
ptr start  = 0x600002d00040
ptr end    = 0x600002d04040
ptr offset = 0x600002d00840
test.cxx:20:9: runtime error: addition of unsigned offset to 0x600002d00840 overflowed to 0x600002d0083c
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior test.cxx:20:9 in
ptr wrap   = 0x600002d0083c

So in fact this should not be suppressed, it should be fixed.

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

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

So I've changed this PR back to my original change (with a branch added). I've also done performance measurements and this function does not appear to be in a performance critical path, at least with my usage of it. I'm measuring the time to do:

cv::filter2D(region, imageDerivativeX, CV_64F, kernelX);
cv::filter2D(region, imageDerivativeY, CV_64F, kernelY);

With OpenCV 4.6 built as release, it takes 118 µs on average (measured on about 2000 calls). With this PR (with the branch added) it takes 104 µs on average. That's within error bars I'd guess.

I also checked with a profiler and 99% of FilterEngine__apply runtime is spent in its call to FilterEngine__proceed.

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.

  1. Use ssize_t cast to make signed arithmetic.
  2. There is no ANY overflow anymore.
  3. Profit.
-ptr += UINT64_MAX; // undefined
+size_t step = 4;
+int y = -1;
+ptr += y * (ssize_t)step;

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

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

Ah! I see what you mean now. I thought you were trying to argue that signed overflow is well-defined. Sorry for the misunderstanding. See my new commit.

@seanm seanm force-pushed the UBSan-overflow branch from 27a7a52 to c1ca539 Compare May 17, 2023 14:59
@asmorkalov
Copy link
Copy Markdown
Contributor

@opencv-alalek could you take a look

@seanm seanm force-pushed the UBSan-overflow branch 2 times, most recently from bb452cf to 6f778fc Compare May 24, 2023 02:04
ptrdiff_t offset = y * (ptrdiff_t)src.step;
FilterEngine__proceed(this_,
src.ptr() + y*src.step,
src.ptr() + offset,
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.

we have tons of such code in OpenCV; are we going to refactor all of it?

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

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

Yes, we should. It's a bug. Pointer overflow is disallowed by C++.

I only use a few OpenCV classes, but I have not encountered any other such overflows in my own use. Are you sure there are so many really?

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.

Just src.ptr() + y * (ptrdiff_t)src.step should be enough.

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

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

Done

@seanm seanm force-pushed the UBSan-overflow branch from 6f778fc to 1bd27fa Compare May 26, 2023 11:59
Pointer arithmetic overflow is always undefined, whether signed or unsigned.

It warned here:

`Addition of unsigned offset to 0x00017fd31b97 overflowed to 0x00017fd30c97`

Convert the offset to a signed number, so that we can offset either forward or backwards.

In my own use of OpenCV at least, this is the only case of pointer arithmetic overflow.
@seanm seanm force-pushed the UBSan-overflow branch from 1bd27fa to 2083fdc Compare May 26, 2023 19:55
@asmorkalov asmorkalov added this to the 4.8.0 milestone May 29, 2023
@asmorkalov asmorkalov merged commit 02397ef into opencv:4.x May 29, 2023
@asmorkalov asmorkalov mentioned this pull request May 31, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

4 participants