Why do I get heap buffer overflow in leetcode?

Question

I was trying to solve a problem for returning the longest palindrome in a string. I first copy the string in reverse order, and then try to find the longest substring. Here is the code I wrote:

char *longestPalindrome(char *s) {
    int len = strlen(s);
    char c[len];
    for (int i = 0; i < len; i++) {
        c[i] = s[len - 1 - i];
    }
    int st = 0;
    int length = 0;
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            int l = 0;
            for (int k = 0; ((i + k) < len) && ((j + k) < len); k++) {
                if (s[i + k] == c[j + k])
                    l++;
                else
                    break;
            }
            if (l > length) {
                length = l;
                st = i;
            }
        }
    }
    char *ans = (char *)calloc(length, sizeof(char));
    for (int i = 0; (i < length) && (i + st < len); i++) {
        ans[i] = s[i + st];
    }
    return ans;  
}

I keep getting this error:

ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000033
  at pc 0x559567cee1ab bp 0x7ffdab22ea70 sp 0x7ffdab22ea60

Now, when I comment out the if-else conditions inside the third for loop, I do not get any error. Why does this happen? In spite of adding the conditions (i + k) < len and (j + k) < len?

I tried commenting out the if-else condition and the code gives no error.

Answer 1

There are multiple problems in the code:

• you must allocate one extra byte for the match and store a null terminator at the end of the block to make it a proper C string:

    char *ans = calloc(length + 1, sizeof(char));
    for (int i = 0; i < length; i++) {
        ans[i] = s[st + i];
    }
    ans[length] = '\0';
    return ans;  
  

  note that you could also use strndup() and replace the whole code block with

    return strndup(st + i, length);
  

  without a null terminator, the calling code will cause an out of bounds access as it tries to locate the end of the string, for example when printing it.

• The algorithm does not find embedded palindromes in the argument string, it finds substrings that happen to have a reversed version embedded somewhere in the argument string. For example for "a dog has no god" will return "dog ", which is not a palindrome.

Here is a modified version:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *longestPalindrome(const char *s) {
    size_t len = strlen(s);
    size_t st = 0;
    size_t length = 0;
    size_t i, n, k;
    for (i = 0; i + length < len; i++) {
        for (n = length + 1; i + n < len; n++) {
            for (k = 0; k < n; k++) {
                if (s[i + k] != s[i + n - 1 - k])
                    break;
            }
            if (k == n) {
                /* found a palindrome of length n */
                length = n;
                st = i;
            }
        }
    }
    return strndup(s + st, length);
}

int main(int argc, char *argv[]) {
    for (int i = 1; i < argc; i++) {
        char *p = longestPalindrome(argv[i]);
        printf("'%s' -> '%s'\n", argv[i], p);
        free(p);
    }
    return 0;
}

The strdup and strndup functions have been part of the POSIX Standard for a long time, and they have finally been incorporated into the upcoming C23 standard. If strndup() is not available on your system, it can be written this way:

#include <stdlib.h>
#include <string.h>

char *strndup(const char *s, size_t n) {
    char *p = malloc(n + 1);
    if (p != NULL) {
        memcpy(p, s, n);
        p[n] = '\0';
    }
    return p;
}