Why does LeetCode give the ERROR : AddressSanitizer: heap-buffer-overflow?

Question

I am practicing a simple quick sort algorithm on LeetCode in C++. The code is supposed to read an unsorted input array and display a sorted version of it. The quicksort algorithm uses a random pivot to ensure symmetry in the array. The code by itself does not seem to have any issues when I run on my local machine (MinGW Compiler). However, when I run the same code on LeetCode I get a comprehensive error message.

Code shown below :

 class Solution {
   public:
    vector<int>& sortArray(vector<int>& nums) {
        size_t l = 0;
        size_t r = nums.size();
        quick_sort(nums, l, r);
        return nums;
    }

    void quick_sort(vector<int>& nums, size_t l, size_t r) {
        if (l >= r)
            return;
        size_t pivot = l + rand() % (r - l + 1);
        swap(nums[l], nums[pivot]);
        size_t m = partition(nums, l, r);
        quick_sort(nums, l, m - 1);
        quick_sort(nums, m + 1, r);        
    }

    size_t partition(vector<int>& nums, size_t l, size_t r) {
        size_t j = l;
        int x = nums[l];
        for (size_t i = l + 1; i <= r; i++) {
            if (nums[i] <= x) {
                j++;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[l], nums[j]);
        return j;
    }
 };

 int main() {
    int n;
    std::cin >> n;
    vector<int> a(n);
    for (auto &item : a) {
        std::cin >> item;
    }
    Solution sorter;
    sorter.sortArray(a);
    for (auto &item : a) {
        std::cout << item << ' ';
    }
}

Error message shown below :

==29==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000060 at pc 0x00000040f1a0 bp 0x7ffe8b2e2470 sp 0x7ffe8b2e2468
READ of size 4 at 0x602000000060 thread T0
    #1 0x7f7f30fcf2e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)

0x602000000060 is located 0 bytes to the right of 16-byte region [0x602000000050,0x602000000060)
allocated by thread T0 here:
#0 0x7f7f329f4ce0 in operator new(unsigned long) (/usr/local/lib64/libasan.so.5+0xe9ce0)
#4 0x7f7f30fcf2e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)

Shadow bytes around the buggy address:
  0x0c047fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  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 00 00[fa]fa fa fa
  0x0c047fff8010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8050: 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
==29==ABORTING

With pivot = l + rand() % (r - l + 1);, pivot may end up being equal to r. But r is not a valid index into nums, it's one past the end. Then nums[pivot] would exhibit undefined behavior. — Igor Tandetnik
– Igor Tandetnik, Commented Jul 17, 2019 at 4:03
partition also runs the loop up to and including r. That has the same problem. — Igor Tandetnik
– Igor Tandetnik, Commented Jul 17, 2019 at 4:04

ymonad · Accepted Answer · 2019-07-17 04:04:03Z

2

Addition to @igor-tandenik's comment

In sortArray(vector<int>& nums):

size_t r = nums.size();
quick_sort(nums, l, r);

In quick_sort(vector<int>& nums, size_t l, size_t r):

size_t m = partition(nums, l, r);

In partition(vector<int>& nums, size_t l, size_t r):

for (size_t i = l + 1; i <= r; i++) {
    if (nums[i] <= x) {
        j++;
        swap(nums[i], nums[j]);
    }
}

Since loop condition is i <= r, i would be nums.size() so swap(nums[i], nums[j]) is invalid.

answered Jul 17, 2019 at 4:04

ymonad

12.1k1 gold badge41 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Why does LeetCode give the ERROR : AddressSanitizer: heap-buffer-overflow?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related