Getting buffer overflow even though I have included the condition that avoids buffer flow (Question 74. Search a 2D Matrix) from leetcode

Question

I was solving Q 74. Search a 2D Matrix from leetcode and I am getting heap buffer overflow error for my solution even though I have included the statements which should avoid buffer overflow which are:

row = (t1 + (t2 - t1) / 2)
col = (t1 + (t2 - t1) / 2)

Here is my code:

bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row, col, t1, t2, rows = matrix.size(), cols = matrix[0].size();
        t1 = 0, t2 = rows - 1;
        while (t1 <= t2) {
            row = (t1 + (t2 - t1) / 2);
            if (target > matrix[row][cols - 1])
                t1 = row + 1;
            else if (target < matrix[row][cols - 1])
                t2 = row - 1;
            else
                break;
        }
        t1 = 0, t2 = matrix[0].size();
        while (t1 <= t2) {
            col = (t1 + (t2 - t1) / 2);
            if (target > matrix[row][col])
                t1 = col + 1;
            else if (target < matrix[row][col])
                t2 = col - 1;
            else if (target == matrix[row][col])
                return true;
        }
        return false;
    }

Test Case it showed error for

Last executed input
[[1,3,5,7],[10,11,16,20],[23,30,34,60]]
13

Runtime Error Details:

=================================================================
==33==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000200 at pc 0x000000345c27 bp 0x7fff3ffa6370 sp 0x7fff3ffa6368
READ of size 4 at 0x602000000200 thread T0
    #2 0x7ffbc11d20b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x602000000200 is located 0 bytes to the right of 16-byte region [0x6020000001f0,0x602000000200)
allocated by thread T0 here:
    #7 0x7ffbc11d20b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Shadow bytes around the buggy address:
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff8000: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
  0x0c047fff8010: fa fa fd fd fa fa fd fa fa fa fd fa fa fa fd fd
  0x0c047fff8020: fa fa fd fa fa fa fd fa fa fa fd fd fa fa fd fa
  0x0c047fff8030: fa fa fd fa fa fa fd fa fa fa fd fa fa fa 00 00
=>0x0c047fff8040:[fa]fa fd fa fa fa fd fa fa fa 00 00 fa fa fd fa
  0x0c047fff8050: fa fa fd fa fa fa 00 00 fa fa fa fa fa fa fa fa
  0x0c047fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8090: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==33==ABORTING

What am I missing?

I see no code to initialize `row` in `searchMatrix`. Crank up your compiler's warnings until it complains, then fix them all. — Stephen Newell, Jul 03 '22 at 02:52
*What am I missing?* -- [Please debug your code](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). — PaulMcKenzie, Jul 03 '22 at 05:45
The code fails for a 0x0 matrix and a 3'000'000'000x4 matrix. You should use `std::midpoint` for `row` / `col`. — Goswin von Brederlow, Jul 03 '22 at 10:58

score 0 · Accepted Answer · answered Jul 03 '22 at 10:55

0

t2 = matrix[0].size(); is out-of-bounds.

Did you mean

t2 = cols - 1;

answered Jul 03 '22 at 10:55

Goswin von Brederlow

11,875
2
24
42

Yep! fixed that, Thanks. Also in the first while loop there is a but the correct else if statement would be ```else if (target < matrix[row][0]) t2 = row - 1; ``` – Saurish Sharma Jul 04 '22 at 02:50

Getting buffer overflow even though I have included the condition that avoids buffer flow (Question 74. Search a 2D Matrix) from leetcode

1 Answers1