为什么我在LeetCode中遇到堆缓冲区溢出问题?

huangapple go评论122阅读模式
英文:

Why do I get heap buffer overflow in leetcode?

问题

我尝试解决一个返回字符串中最长回文子串的问题。
首先,我将字符串按照相反的顺序复制,然后尝试找到最长的子字符串。
以下是我编写的代码:

  1. char *longestPalindrome(char *s) {
  2. int len = strlen(s);
  3. char c[len];
  4. for (int i = 0; i < len; i++) {
  5. c[i] = s[len - 1 - i];
  6. }
  7. int st = 0;
  8. int length = 0;
  9. for (int i = 0; i < len; i++) {
  10. for (int j = 0; j < len; j++) {
  11. int l = 0;
  12. for (int k = 0; ((i + k) < len) && ((j + k) < len); k++) {
  13. if (s[i + k] == c[j + k])
  14. l++;
  15. else
  16. break;
  17. }
  18. if (l > length) {
  19. length = l;
  20. st = i;
  21. }
  22. }
  23. }
  24. char *ans = (char *)calloc(length, sizeof(char));
  25. for (int i = 0; (i < length) && (i + st < len); i++) {
  26. ans[i] = s[i + st];
  27. }
  28. return ans;
  29. }

我一直收到这个错误:

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

现在,当我注释掉第三个for循环内的if-else条件时,我不再收到错误。为什么会发生这种情况?
尽管添加了条件(i + k) < len(j + k) < len

我尝试注释掉if-else条件后,代码不再报错。

英文:

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:

  1. char *longestPalindrome(char *s) {
  2. int len = strlen(s);
  3. char c[len];
  4. for (int i = 0; i &lt; len; i++) {
  5. c[i] = s[len - 1 - i];
  6. }
  7. int st = 0;
  8. int length = 0;
  9. for (int i = 0; i &lt; len; i++) {
  10. for (int j = 0; j &lt; len; j++) {
  11. int l = 0;
  12. for (int k = 0; ((i + k) &lt; len) &amp;&amp; ((j + k) &lt; len); k++) {
  13. if (s[i + k] == c[j + k])
  14. l++;
  15. else
  16. break;
  17. }
  18. if (l &gt; length) {
  19. length = l;
  20. st = i;
  21. }
  22. }
  23. }
  24. char *ans = (char *)calloc(length, sizeof(char));
  25. for (int i = 0; (i &lt; length) &amp;&amp; (i + st &lt; len); i++) {
  26. ans[i] = s[i + st];
  27. }
  28. return ans;
  29. }

I keep getting this error:

  1. ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000033
  2. 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) &lt; len and (j + k) &lt; len?

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

答案1

得分: 1

只需将calloc(length, ...更改为calloc(length + 1, ...,然后在打印之前终止结果字符串。

英文:

Looks like you just need to terminate your result string before printing it. Just change calloc(length, ... to calloc(length + 1, ....

答案2

得分: 1

已发布的代码不会导致问题中发布的错误。在已发布的代码中没有越界访问。

换句话说,错误是由一些未发布的代码引起的。也许/很可能是longestPalindrome的调用者在使用返回的指针ans时引发了发布的错误。

关键在于:

> ...返回字符串中的最长回文串。

您的代码没有返回C风格的字符串。分配的内存不包含字符串终止字符(NUL终止符)。
(注意:当前分配的内存中甚至没有足够的空间来放置终止符)

因此,如果caller像这样做:

  1. ...
  2. char* str = longestPalindrome(someString);
  3. if (str) puts(str);

puts调用将访问越界内存。

解决方案:确保ans指向包含终止字符的内存。

此外,代码没有处理输入为空字符串的情况。这也可能导致错误。

顺便说一句:要小心使用像char c[len];这样的VLA(可变长度数组)。如果输入字符串非常大,可能会导致栈溢出。

英文:

The posted code will not give the error posted in the question. There are no out-of-bounds access in the posted code.

In other words - the error comes from some code that isn't posted. Maybe/likely the caller of longestPalindrome uses the returned pointer ans in a way that causes the posted error.

The key is here:

> ...returning the longest palindrome in a string.

Your code doesn't return a C style string. The allocated memory doesn't contain a string termination character (NUL termination).
(note: currently there isn't even room for the termination in the allocated memory)

So if the caller do something like:

  1. ...
  2. char* str = longestPalindrome(someString);
  3. if (str) puts(str);

the puts call will access memory out-of-bounds.

Solution: Make sure ans points to memory that contains a termination character.

Also the code doesn't handle the case where the input is an empty string. This can also result in errors.

BTW: Be careful about using VLAs like char c[len];. If the input string is very big it may result in stack overflow.

答案3

得分: 1

以下是翻译好的部分:

  1. 在代码中存在多个问题:
  2. * 你必须为匹配分配一个额外的字节,并在块的末尾存储一个空终止符,使其成为一个合适的C字符串
  3. ```c
  4. char *ans = calloc(length + 1, sizeof(char));
  5. for (int i = 0; i < length; i++) {
  6. ans[i] = s[st + i];
  7. }
  8. ans[length] = '
    在代码中存在多个问题:
  9. * 你必须为匹配分配一个额外的字节,并在块的末尾存储一个空终止符,使其成为一个合适的C字符串
  10.   ```c
  11.     char *ans = calloc(length + 1, sizeof(char));
  12.     for (int i = 0; i < length; i++) {
  13.         ans[i] = s[st + i];
  14.     }
  15.     ans[length] = '\0';
  16.     return ans;  
  17. ';
  18. return ans;

请注意,你也可以使用 strndup(),并用以下代码替换整个代码块:

  1. return strndup(st + i, length);

没有空终止符,调用代码将导致越界访问,因为它试图定位字符串的末尾,例如在打印时。

  • 该算法无法在参数字符串中找到嵌套的回文,它会找到在参数字符串中某处嵌套有一个翻转版本的子字符串。例如对于 &quot;a dog has no god&quot;,将返回 &quot;dog &quot;,这不是一个回文。

这是一个修改过的版本:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. char *longestPalindrome(const char *s) {
  5. size_t len = strlen(s);
  6. size_t st = 0;
  7. size_t length = 0;
  8. size_t i, n, k;
  9. for (i = 0; i + length < len; i++) {
  10. for (n = length + 1; i + n < len; n++) {
  11. for (k = 0; k < n; k++) {
  12. if (s[i + k] != s[i + n - 1 - k])
  13. break;
  14. }
  15. if (k == n) {
  16. /* 找到长度为 n 的回文 */
  17. length = n;
  18. st = i;
  19. }
  20. }
  21. }
  22. return strndup(s + st, length);
  23. }
  24. int main(int argc, char *argv[]) {
  25. for (int i = 1; i < argc; i++) {
  26. char *p = longestPalindrome(argv[i]);
  27. printf("'%s' -> '%s'\n", argv[i], p);
  28. free(p);
  29. }
  30. return 0;
  31. }

strdupstrndup 函数长期以来一直是POSIX标准的一部分,它们最终已纳入即将推出的C23标准中。如果你的系统上不支持 strndup(),可以这样写:

  1. #include <stdlib.h>
  2. #include <string.h>
  3. char *strndup(const char *s, size_t n) {
  4. char *p = malloc(n + 1);
  5. if (p != NULL) {
  6. memcpy(p, s, n);
  7. p[n] = '
    #include <stdlib.h>
  8. #include <string.h>
  9. char *strndup(const char *s, size_t n) {
  10.     char *p = malloc(n + 1);
  11.     if (p != NULL) {
  12.         memcpy(p, s, n);
  13.         p[n] = '\0';
  14.     }
  15.     return p;
  16. }
  17. ';
  18. }
  19. return p;
  20. }
  1. <details>
  2. <summary>英文:</summary>
  3. There are multiple problems in the code:
  4. * 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:
  1. char *ans = calloc(length + 1, sizeof(char));
  2. for (int i = 0; i &lt; length; i++) {
  3. ans[i] = s[st + i];
  4. }
  5. ans[length] = &#39;
    char *ans = calloc(length + 1, sizeof(char));
  6. for (int i = 0; i &lt; length; i++) {
  7. ans[i] = s[st + i];
  8. }
  9. ans[length] = &#39;\0&#39;;
  10. return ans;  
  11. &#39;;
  12. return ans;
  1. note that you could also use `strndup()` and replace the whole code block with
  1. return strndup(st + i, length);
  1. 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.
  2. * 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 `&quot;a dog has no god&quot;` will return `&quot;dog &quot;`, which is not a palindrome.
  3. 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;
}

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

  1. </details>

huangapple
  • 本文由 发表于 2023年7月20日 14:04:23
  • 转载请务必保留本文链接:https://go.coder-hub.com/76727078.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定