AddressSanitizer heap-buffer-overflow error in Leetcode groupAnagram problem

Question

This is my program:

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;
}

Can anyone tell me why I get this error?

=================================================================
==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

I thought maybe i was trying to access an undeclared address but i don't see any, so i don't know what to do.

Answer 1

The buffers you allocate in isAnagram don't make room for the NULL terminator:

10,11c10,11
<     str1 = malloc(len * sizeof(char));
<     str2 = malloc(len * sizeof(char));
---
>     str1 = malloc(len * sizeof(char) + 1);
>     str2 = malloc(len * sizeof(char) + 1);

Furthermore, the five instances where you copy strings over don't write a NULL terminator (CTRL+F group[count) at the end of the buffer. In addition to that, you only allocate 100 char per string, which, looking at the LeetCode description, matches the maximum length of 100, but doesn't leave room for the NULL terminator.

You can mask, but not solve, this issue, by sanitizing the word buffer(s) you allocate as well as adding another char for the NULL terminator:

28c28
<             group[i][j] = (char *)malloc(100*sizeof(char));
---
>             group[i][j] = (char *)calloc(101, sizeof(char));

These two edits will let this solution pass most cases, but we eventually hit MLE (Memory Limit Exceeded) because you allocate an unnecessary amount of memory for each run.