c - 为什么我在这段代码中出现缓冲区溢出?
问题描述
typedef struct
{
int top;
char *arr;
}adjacent;
char *removeDuplicates(char * S)
{
int count = 0;
adjacent *ptr = malloc(sizeof(adjacent));
ptr->top = 0;
ptr->arr = malloc(sizeof(char) * strlen(S));
ptr->arr[0] = S[0];
for(int i = 1; i < strlen(S); i++)
{
if(ptr->arr[ptr->top] == S[i])
{
count--;
ptr->top = (ptr->top) - 1;
}
else
{
count++;
ptr->top = (ptr->top) + 1;
ptr->arr[ptr->top] = S[i];
}
}
ptr->arr[count + 1] = '\0';
return ptr->arr;
}
我收到的错误出现在网站 leetcode.com 上。问题是从字符串中删除所有相邻的重复项。给定一个由小写字母组成的字符串 S,重复删除包括选择两个相邻且相等的字母并将它们删除。
我们反复对 S 进行重复删除,直到我们不再可以为止。
在完成所有此类重复删除后返回最终字符串。保证答案是独一无二的。
错误:
Runtime Error
=================================================================
==29==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000004f at pc 0x0000004018ae bp 0x7ffed3a16300 sp 0x7ffed3a162f8
READ of size 1 at 0x60200000004f thread T0
#2 0x7f9d2765f2e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
0x60200000004f is located 1 bytes to the left of 6-byte region [0x602000000050,0x602000000056)
allocated by thread T0 here:
#0 0x7f9d28ae92b0 in malloc (/usr/local/lib64/libasan.so.5+0xe82b0)
#3 0x7f9d2765f2e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
Shadow bytes around the buggy address:
0x0c047fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
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 07 fa fa fa 00 00 fa[fa]06 fa fa fa fa fa
0x0c047fff8010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 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
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
==29==ABORTING
解决方案
除了逐一分配、内存泄漏和不必要的重复之外,count
还有arr->top
一个更严重的问题。
假设第二个字符与第一个字符相同。指数降为-1
。然后当你检查下一个字符时,它不再检查前一个字符,而是索引超出范围。
整个技术是错误的。与其玩索引,不如增加它。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char *removeDuplicates(char * S)
{
char *arr = malloc(strlen(S) + 1); // fix the off-by-one
if (arr == NULL) {
exit(1);
}
int count = 0;
int index = 0;
while(S[index] != '\0') {
int duplic = 0;
while(S[index + duplic + 1] == S[index]) {
duplic++;
}
if(duplic == 0) {
arr[count++] = S[index];
}
index += duplic + 1;
}
arr[count] = '\0';
return arr;
}
int main()
{
char s[100] = "";
while(strcmp(s, "q") != 0) {
scanf(" %99[^\n]", s);
char *result = removeDuplicates(s);
printf("[%s]\n", result);
free(result);
}
}
测试运行:
aaab [乙] 阿布 [一个] 阿爸 [啊] 阿巴 [] q [问]
推荐阅读
- java - Android Studio中Java的Clojure单元测试?
- jquery - jQuery - 使用 :after 从 CSS 获取图像
- reactjs - 如何在组件之间传递状态变量
- python - 在 python 中将 int 转换为 str 会产生 TypeError
- forms - Flutter 如何在显示对话框中使用文本表单获取用户输入?
- python - 将新行添加到 Google 表格时触发 Python
- javascript - 单击多次执行的模态按钮代码时(JQuery-JavaScript)
- keras - CNN 识别能否回答“不是这些类中的任何一个”
- sql - 我可以准确查询结果吗
- java - 对整数输入进行排序时如何在输出中显示“主题”