Почему я получаю переполнение буфера в этом коде? - PullRequest
Новая
       82

Почему я получаю переполнение буфера в этом коде?

1 голос
/ 11 октября 2019 
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

1 Ответ

0 голосов
/ 11 октября 2019

Помимо выделения по одному, утечки памяти и ненужного дублирования 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
[b]
abbb
[a]
abba
[aa]
aabbaa
[]
q
[q]
...