Leetcode中AddressSanitizer: heap-buffer-overflow错误排查求助

我在解决LeetCode的Majority Element II题目时，本地macOS的g和clang编译器运行代码正常，但LeetCode内置编译器触发了AddressSanitizer: heap-buffer-overflow错误。想了解代码非逻辑部分的问题及错误原因，相关代码与错误信息如下：

原代码 #

int* majorityElement(int* nums, int numsSize, int* returnSize){
    int *ans = (int *)malloc(2 * (sizeof(int)));
    int limit = numsSize / 3;
    int index=0;
    *returnSize = 0;

    if (limit == 0){
        for(int i = 0; i < numsSize; i++){
            ans[index++] = nums[i];
        }
        return ans;
    }
    else {
        for (int i = 0; i < numsSize; i++)
        {
            int count = 1;
            if (nums[i] != -1)
            {
                for (int j = i+1; j < numsSize; j++)
                {
                    if (nums[i] == nums[j])
                    {
                        nums[j] = -1;
                        count++;
                    }
                    if ((count > limit) && (ans[index-1] != nums[i]))
                    {
                        ans[index++] = nums[i]; 
                    }
                }
            }
        };
    }
    return ans;

}

错误信息 #

==22==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000002c at pc 0x556888e8ee4b bp 0x7ffdb82cf510 sp 0x7ffdb82cf500
READ of size 4 at 0x60200000002c thread T0
    #2 0x7fd2226ee082 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
0x60200000002c is located 4 bytes to the left of 8-byte region [0x602000000030,0x602000000038)
allocated by thread T0 here:
    #0 0x7fd2230fc887 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:145
    #3 0x7fd2226ee082 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:145
    #3 0x7fd2226ee082 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
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 00 04 fa[fa]00 fa fa fa fa fa 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
  Shadow gap:              cc
==22==ABORTING

错误原因分析 #

1. 未正确设置returnSize
   代码所有分支都未更新*returnSize的实际值，始终保持初始的0。LeetCode判题器依赖这个值读取返回数组内容，必然导致越界访问。

2. limit==0时的数组溢出
   当numsSize>2时（比如numsSize=3，3/3=0），limit等于0，此时代码会把所有nums元素塞进仅malloc了2个int空间的ans数组，直接触发堆缓冲区溢出。

3. 访问ans[index-1]的越界问题
   在else分支中，当index=0时，ans[index-1]等价于访问ans[-1]，这个地址属于堆内存的左侧红区（错误信息里的0x60200000002c），属于非法内存访问，直接触发AddressSanitizer报错。

修复后的代码 #

int* majorityElement(int* nums, int numsSize, int* returnSize){
    // 题目要求最多返回2个元素，初始化返回数组
    int *ans = (int *)malloc(2 * sizeof(int));
    int limit = numsSize / 3;
    int index = 0;
    *returnSize = 0;

    if (limit == 0) {
        // 当数组长度<=2时，所有元素都满足出现次数>0
        if (numsSize <= 2) {
            for (int i = 0; i < numsSize; i++) {
                ans[index++] = nums[i];
            }
            *returnSize = index;
        } else {
            // 数组长度>3时，先去重再统计次数
            int temp[200000] = {0};
            int uniqueCount = 0;
            // 去重
            for (int i = 0; i < numsSize; i++) {
                int exists = 0;
                for (int j = 0; j < uniqueCount; j++) {
                    if (temp[j] == nums[i]) {
                        exists = 1;
                        break;
                    }
                }
                if (!exists) {
                    temp[uniqueCount++] = nums[i];
                }
            }
            // 统计每个唯一元素的出现次数
            for (int i = 0; i < uniqueCount; i++) {
                int count = 0;
                for (int j = 0; j < numsSize; j++) {
                    if (nums[j] == temp[i]) {
                        count++;
                    }
                }
                if (count > limit) {
                    ans[index++] = temp[i];
                }
            }
            *returnSize = index;
        }
    } else {
        // 遍历统计每个元素的出现次数，标记已处理元素
        for (int i = 0; i < numsSize; i++) {
            int count = 1;
            if (nums[i] != -1) {
                for (int j = i + 1; j < numsSize; j++) {
                    if (nums[i] == nums[j]) {
                        nums[j] = -1;
                        count++;
                    }
                }
                // 检查是否已经在结果数组中，避免重复添加
                int exists = 0;
                for (int k = 0; k < index; k++) {
                    if (ans[k] == nums[i]) {
                        exists = 1;
                        break;
                    }
                }
                if (!exists && count > limit) {
                    ans[index++] = nums[i];
                }
            }
        }
        *returnSize = index;
    }

    // 优化内存：如果没有结果，释放内存并返回NULL；如果结果少于2个，重新分配合适大小的内存
    if (*returnSize == 0) {
        free(ans);
        ans = NULL;
    } else if (*returnSize < 2) {
        int *newAns = (int *)malloc(*returnSize * sizeof(int));
        for (int i = 0; i < *returnSize; i++) {
            newAns[i] = ans[i];
        }
        free(ans);
        ans = newAns;
    }

    return ans;
}

关键修复点 #

• 所有分支都正确设置*returnSize，让判题器明确返回数组的有效长度
• 修复limit==0时的数组溢出问题，根据数组长度处理不同情况
• 移除对ans[index-1]的越界访问，改用遍历结果数组判断元素是否已存在
• 优化内存使用，避免不必要的空间浪费

内容的提问来源于stack exchange，提问作者Mudit Tyagi