英文:
Why do I get heap buffer overflow in leetcode?
问题
我尝试解决一个返回字符串中最长回文子串的问题。
首先，我将字符串按照相反的顺序复制，然后尝试找到最长的子字符串。
以下是我编写的代码：
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;
}
我一直收到这个错误：
ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000033
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:
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.
答案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像这样做：
...
char* str = longestPalindrome(someString);
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:
...
char* str = longestPalindrome(someString);
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
以下是翻译好的部分：
在代码中存在多个问题：
* 你必须为匹配分配一个额外的字节，并在块的末尾存储一个空终止符，使其成为一个合适的C字符串：
```c
char *ans = calloc(length + 1, sizeof(char));
for (int i = 0; i < length; i++) {
ans[i] = s[st + i];
}
ans[length] = '在代码中存在多个问题：
* 你必须为匹配分配一个额外的字节，并在块的末尾存储一个空终止符，使其成为一个合适的C字符串：
```c
char *ans = calloc(length + 1, sizeof(char));
for (int i = 0; i < length; i++) {
ans[i] = s[st + i];
}
ans[length] = '\0';
return ans;
';
return ans;
请注意，你也可以使用 strndup()，并用以下代码替换整个代码块：
return strndup(st + i, length);
没有空终止符，调用代码将导致越界访问，因为它试图定位字符串的末尾，例如在打印时。
- 该算法无法在参数字符串中找到嵌套的回文，它会找到在参数字符串中某处嵌套有一个翻转版本的子字符串。例如对于
"a dog has no god"，将返回"dog "，这不是一个回文。
这是一个修改过的版本：
#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) {
/* 找到长度为 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;
}
strdup 和 strndup 函数长期以来一直是POSIX标准的一部分，它们最终已纳入即将推出的C23标准中。如果你的系统上不支持 strndup()，可以这样写：
#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] = '#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;
}
';
}
return p;
}
<details>
<summary>英文:</summary>
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] = 'char *ans = calloc(length + 1, sizeof(char));
for (int i = 0; i < length; i++) {
ans[i] = s[st + i];
}
ans[length] = '\0';
return ans;
';
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;
}
</details>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论