LeetCode groupAnagrams问题中AddressSanitizer堆缓冲区溢出错误排查

在实现LeetCode的groupAnagrams（字母异位词分组）函数时，触发了AddressSanitizer检测到的heap-buffer-overflow（堆缓冲区溢出）错误，以下是代码、错误日志及问题分析与修复方案：

原代码 #

int cmpfunc (const void * a, const void * b) {
   return ( *(char*)a - *(char*)b );
}

bool isAnagram(char * s, char * t){
    char *str1,*str2;
    if (strlen(s) != strlen(t)) return false;
    char chTemp;
    int len = strlen(s);
    str1 = malloc(len * sizeof(char));
    str2 = malloc(len * sizeof(char));
    strcpy(str1,s);
    strcpy(str2,t);
    qsort(str1,len,sizeof(char),cmpfunc);
    qsort(str2,len,sizeof(char),cmpfunc);
    for (int i = 0; i < len; i++) {
        if (str1[i] != str2[i]) return false;
    }
    return true;
}

char *** groupAnagrams(char ** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
    if (strsSize == 0) return NULL;
    char ***group = (char ***)malloc(strsSize*sizeof(char**));
    for (int i = 0; i < strsSize; i++) {
        group[i] = (char **)malloc(strsSize*sizeof(char*));
        for (int j = 0; j < strsSize; j++) {
            group[i][j] = (char *)malloc(100*sizeof(char));
        }
    } 
    int *used = malloc(strsSize * sizeof(int));
    for (int i = 0; i < strsSize; i++) 
        used[i] = 0;

    *returnColumnSizes = (int *)malloc(strsSize*sizeof(int));
    for (int i = 0; i < strsSize; i++) 
        (*returnColumnSizes)[i] = 0;
    int count = 0;
    if (strsSize == 1) {
          for (int l = 0; l < strlen(strs[0]); l++) {
            group[0][0][l] = strs[0][l];
          }
          count = 1;
          (*returnColumnSizes)[0] = 1;
    } else {
        
        for (int i = 0; i < strsSize-1; i++) {
            int check  = 0;
            int k = 0;
            if (!used[i]) {
                for (int j = i+1; j < strsSize; j++) {
                        if (isAnagram(strs[i],strs[j])) {
                            if (k == 0) {
                                for (int l = 0; l < strlen(strs[i]); l++) {
                                    group[count][0][l] = strs[i][l];
                                }
                                for (int l = 0; l < strlen(strs[j]); l++) {
                                    group[count][1][l] = strs[j][l];
                                }
                                used[i] = 1;
                                used[j] = 1;
                                (*returnColumnSizes)[count] = 2; 
                                count++;
                                k++;
                            } else {
                                (*returnColumnSizes)[count-1]++; 
                                for (int l = 0; l < strlen(strs[j]); l++) {
                                    group[count-1][k+1][l] = strs[j][l];
                                }
                                used[j] = 1;
                                k++;
                            }
                            check = 1;
                        }
                    }
                    if (!check) {
                        for (int l = 0; l < strlen(strs[i]); l++) {
                            group[count][0][l] = strs[i][l];
                        }
                        (*returnColumnSizes)[count] = 1;
                        count++;
                    }
            }
        }
        if (!used[strsSize-1]) {
            for (int l = 0; l < strlen(strs[strsSize-1]); l++) {
                    group[count][0][l] = strs[strsSize-1][l];
            }
            (*returnColumnSizes)[count] = 1;
            count++;
        }
    }
   *returnSize = count;
    free(used);
    return group;
}

错误日志 #

=================================================================
==43==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6020000000d3 at pc 0x7f3b6a2e357d bp 0x7ffc1ee141b0 sp 0x7ffc1ee13958
WRITE of size 4 at 0x6020000000d3 thread T0
    #0 0x7f3b6a2e357c  (/lib/x86_64-linux-gnu/libasan.so.5+0x9b57c)
    #4 0x7f3b697100b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x6020000000d3 is located 0 bytes to the right of 3-byte region [0x6020000000d0,0x6020000000d3)
allocated by thread T0 here:
    #0 0x7f3b6a355bc8 in malloc (/lib/x86_64-linux-gnu/libasan.so.5+0x10dbc8)
    #4 0x7f3b697100b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
SUMMARY: AddressSanitizer: heap-buffer-overflow (/lib/x86_64-linux-gnu/libasan.so.5+0x9b57c) 
Shadow bytes around the buggy address:
  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 04 fa fa fa 04 fa fa fa 04 fa fa fa 04 fa
=>0x0c047fff8010: fa fa 04 fa fa fa 04 fa fa fa[03]fa fa fa 03 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
  0x0c047fff8060: 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
==43==ABORTING

错误分析与修复 #

1. isAnagram函数的堆溢出根源 #

在isAnagram函数中，使用malloc(len * sizeof(char))分配内存，但C语言中字符串是以'\0'作为终止符的，原字符串s和t的长度为len，实际占用len+1个字节（包含终止符）。使用strcpy复制时，会把原字符串的'\0'也复制过去，导致写入到分配的内存之外，直接触发堆缓冲区溢出。同时函数未释放分配的内存，存在内存泄漏。

修复：
调整内存分配大小，并添加内存释放逻辑：

bool isAnagram(char * s, char * t){
    if (strlen(s) != strlen(t)) return false;
    int len = strlen(s);
    // 分配包含终止符的内存空间
    char *str1 = malloc((len + 1) * sizeof(char));
    char *str2 = malloc((len + 1) * sizeof(char));
    if (!str1 || !str2) { // 增加内存分配失败判断
        free(str1);
        free(str2);
        return false;
    }
    strcpy(str1,s);
    strcpy(str2,t);
    qsort(str1,len,sizeof(char),cmpfunc);
    qsort(str2,len,sizeof(char),cmpfunc);
    bool result = true;
    for (int i = 0; i < len; i++) {
        if (str1[i] != str2[i]) {
            result = false;
            break;
        }
    }
    // 释放内存避免泄漏
    free(str1);
    free(str2);
    return result;
}

2. groupAnagrams函数的字符串终止符缺失 #

在复制字符串到group数组时，只复制了字符部分，没有添加'\0'终止符，导致后续操作（如字符串长度计算、比较）可能越界访问内存。

修复：
每次复制完字符串后，在末尾添加'\0'。例如处理单个字符串时：

if (strsSize == 1) {
    int strLen = strlen(strs[0]);
    for (int l = 0; l < strLen; l++) {
        group[0][0][l] = strs[0][l];
    }
    group[0][0][strLen] = '\0'; // 添加字符串终止符
    count = 1;
    (*returnColumnSizes)[0] = 1;
}

其他所有复制字符的循环后都需要添加这一步。

3. group数组索引逻辑错误 #

在else分支的异位词处理中，当k>0时，使用group[count-1][k+1]作为索引存在逻辑问题：k初始为0，第一次处理后k=1，此时新元素应该放在索引1的位置（而不是k+1=2），否则会跳过索引1，导致内存空间浪费，同时可能在后续操作中越界。

修复：
调整索引逻辑，用k直接作为当前要添加元素的索引：

if (k == 0) {
    int lenI = strlen(strs[i]);
    for (int l = 0; l < lenI; l++) {
        group[count][k][l] = strs[i][l];
    }
    group[count][k][lenI] = '\0';
    k++;
    int lenJ = strlen(strs[j]);
    for (int l = 0; l < lenJ; l++) {
        group[count][k][l] = strs[j][l];
    }
    group[count][k][lenJ] = '\0';
    used[i] = 1;
    used[j] = 1;
    (*returnColumnSizes)[count] = 2; 
    count++;
    k++;
} else {
    (*returnColumnSizes)[count-1]++; 
    int lenJ = strlen(strs[j]);
    for (int l = 0; l < lenJ; l++) {
        group[count-1][k][l] = strs[j][l];
    }
    group[count-1][k][lenJ] = '\0';
    used[j] = 1;
    k++;
}

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