==284==ERROR：AddressSanitizer：stack-buffer-underflow

我正在编写一个更简单的Boyer摩尔算法版本，我需要使用循环缓冲区，因为可能会有一个非常大的输入。程序应该写入所有与模式比较的符号位置。但是当我将程序提交到gitlab服务器时，我的程序失败了。这些测试检查程序中未定义的行为，所以失败的原因很明显。然而，我不能发现UB。唯一的提示是一个错误消息，但我不明白如何使用这些字节地址来解决我的问题。还有，如果“pat”只是一个基本字符串，它如何下溢？

#include <stdio.h>

#define MAX_PATTERN_LEN 16
#define BUF_SIZE 16
#define ALPH_SIZE 256

void calculate_shifts(const unsigned char *str, int len_str, int *shifts) {
    for (int i = 0; i < ALPH_SIZE; i++) 
        shifts[i] = len_str;
    for (int i = 0; i < len_str - 1; i++) 
        shifts[str[i]] = len_str - 1 - i;
}

int read_str(int max_len, unsigned char *str_place, int *is_patread, int *ind_EOF) {
    int count_read = 0;
    int ch = EOF;
    for (int i = 0; i < max_len; i++) {
        ch = getchar();
        if (ch == EOF) {
            if (!(*ind_EOF)) 
                *ind_EOF = 1; 
            break;

        }
        if ((ch == '\n') && (*is_patread == 0)) {
            *is_patread = 1;
            break;
        }
        str_place[i] = (char) ch;
        count_read++;
    }
    return count_read;
}

typedef struct {
    unsigned char *buf;
    int idxIn;
    int idxOut;
    int size;
} Ring_buf;

void Ring_put(Ring_buf *ring, unsigned char symbol) {
    ring->buf[ring->idxIn++] = symbol;
    if (ring->idxIn >= ring->size) 
        ring->idxIn = 0;
}

void Ring_push_idxOut(Ring_buf *ring, int jump) {
    int new_indxOut = ring->idxOut + jump;
    if (new_indxOut >= ring->size) new_indxOut -= ring->size;
    ring->idxOut = new_indxOut;
}

void Ring_init(Ring_buf *ring, unsigned char *buf, int size) {
    ring->size = size;
    ring->buf = buf;
    ring->idxIn = 0;
    ring->idxOut = 0;
}

unsigned char Ring_showch(const Ring_buf *ring, int idx) {
    int actual_idx = ring->idxOut + idx;
    if (actual_idx >= ring->size) 
        actual_idx -= ring->size;
    return ring->buf[actual_idx];
}

int Ring_put_nchars(Ring_buf *ring, int num, int ind_EOF) {
    if (ind_EOF) return 0;
    int count_read = 0;
    int ch = EOF;
    for (int i = 0; i < num; i++) {
        ch = getchar();
        if (ch == EOF)
            break;
        Ring_put(ring, ch);
        count_read++;
    }
    return (count_read == num);
}

void search_substr(Ring_buf *ring, const unsigned char *pat, int pat_len, int ind_EOF) {
    int shift = 0, local_shift = 0, shift_addition = 0, shifts[ALPH_SIZE];
    calculate_shifts(pat, pat_len, shifts);
    for (;;) {
        while (local_shift <= (ring->size - pat_len)) {
            int j = pat_len - 1;
            for (; (Ring_showch(ring, local_shift + j) == pat[j]) && (j >= 0) ; j--) 
                printf("%d ", shift + local_shift + j + 1);
            if (j < 0) {
                shift_addition = shifts[pat[pat_len - 1]];
                local_shift += shift_addition;
            } else {
                printf("%d ", shift + local_shift + j + 1);
                shift_addition = shifts[Ring_showch(ring, local_shift + j)];
                if (j == 0) 
                    shift_addition = pat_len;
                if ((shift_addition == pat_len) && (j < pat_len - 1) && (pat[pat_len - 1] == pat[0])) 
                    shift_addition--;
                local_shift += shift_addition;
            }
        }
        int req_addplace = pat_len - 1 - (ring->size - 1 - local_shift);
        shift += req_addplace;
        if (!Ring_put_nchars(ring, req_addplace, ind_EOF))
            break;
        Ring_push_idxOut(ring, req_addplace);
        local_shift -= req_addplace;
    }
}

int main(void) {
    unsigned char pat[MAX_PATTERN_LEN + 1] = {'\0'};
    unsigned char str[BUF_SIZE] = {'\0'};
    int is_patread = 0, ind_EOF = 0;
    int pat_len = read_str(MAX_PATTERN_LEN + 1, pat, &is_patread, NULL);
    int str_len = read_str(BUF_SIZE, str, &is_patread, &ind_EOF);
    if (!str_len || !pat_len)
        return 0;
    Ring_buf ring;
    Ring_init(&ring, str, str_len);
    search_substr(&ring, pat, pat_len, ind_EOF);
    return 0;
}

字符串
第一个月
output: 7, 14, 13, 12, 11, 10, 20, 22, 21, 20, 19, 18, 17, 16个

the error message:
==284==ERROR: AddressSanitizer: stack-buffer-underflow on address 0x7ffd3cdb915f at pc 0x00000040166d bp 0x7ffd3cdb8b90 sp 0x7ffd3cdb8b80
READ of size 1 at 0x7ffd3cdb915f thread T0
    #0 0x40166c in search_substr /builds/J6i_AJma/0/c_programming_autumn/23203/i.bogachenkov/template/lab1-0/src/main.c:87
    #1 0x40187b in main /builds/J6i_AJma/0/c_programming_autumn/23203/i.bogachenkov/template/lab1-0/src/main.c:121
    #2 0x7f068531ab96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
    #3 0x400b69 in _start (/builds/J6i_AJma/0/c_programming_autumn/23203/i.bogachenkov/template/build_lab1-0/lab1-0+0x400b69)
Address 0x7ffd3cdb915f is located in stack of thread T0 at offset 31 in frame
    #0 0x4016af in main /builds/J6i_AJma/0/c_programming_autumn/23203/i.bogachenkov/template/lab1-0/src/main.c:111
  This frame has 5 object(s):
    [32, 49) 'pat:112' <== Memory access at offset 31 underflows this variable
    [96, 112) 'str:113'
    [128, 132) 'is_patread:114'
    [144, 148) 'ind_EOF:114'
    [160, 184) 'ring:119'
HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-underflow /builds/J6i_AJma/0/c_programming_autumn/23203/i.bogachenkov/template/lab1-0/src/main.c:87 in search_substr
Shadow bytes around the buggy address:
  0x1000279af1d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000279af1e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000279af1f0: 00 00 00 00 00 00 00 00 f3 f3 f3 f3 f3 f3 f3 f3
  0x1000279af200: f3 f3 f3 f3 f3 f3 f3 f3 00 00 00 00 00 00 00 00
  0x1000279af210: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x1000279af220: 00 00 00 00 00 00 00 00 f1 f1 f1[f1]00 00 01 f2
  0x1000279af230: f2 f2 f2 f2 00 00 f2 f2 04 f2 04 f2 00 00 00 f3
  0x1000279af240: f3 f3 f3 f3 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000279af250: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000279af260: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000279af270: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
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
==284==ABORTING

型

main()/read_str()：当ind_EOF被解引用时，int pat_len = read_str(MAX_PATTERN_LEN, pat, &is_patread, NULL)是未定义的行为（segfault）。将其视为错误，或者如果不是NULL，则仅解引用ind_EOF：

if(ind_EOF)
            *ind_EOF = 1;

字符串

read_str()：更倾向于初始化out参数而不是依赖于caller（在循环之前）：

if(ind_EOF)
   *ind_EOF = 0;

型

read_str()：out参数str_place应该是一个字符串，即'\0'终止，如果成功的话。最小的修复是传入max_len，比数组大小小一，因为你已经零初始化了输入字符串：

unsigned char pat[MAX_PATTERN_LEN + 1] = {0};
unsigned char str[BUF_SIZE + 1] = {0};
int is_patread = 0, ind_EOF = 0;
int pat_len = read_str(MAX_PATTERN_LEN, pat, &is_patread, NULL);
int str_len = read_str(BUF_SIZE, str, &is_patread, &ind_EOF);

型

read_str()：考虑使用fgets()并消除is_patread和ind_EOF参数，因为只有第二个调用者使用ind_EOF。

size_t read_str(size_t n, char *s) {
    return fgets(s, n, stdin) ? strlen(s) : 0;
}

型
..

int main(void) {
    char pat[MAX_PATTERN_LEN];
    size_t pat_len = read_str(MAX_PATTERN_LEN, pat);
    if(!pat_len) return 0;

    char str[BUF_SIZE];
    size_t str_len = read_str(BUF_SIZE, str);
    if(!str_len) return 0;
    int ind_EOF = feof(stdin);
    // ...

型

search_substr()：在使用它之前检查j是否在预期范围内（即交换控制表达式的两个表达式的顺序）：

for (; ((j >= 0) && Ring_showch(ring, local_shift + j) == pat[j]); j--)

型

Ring_put_nchars()：在示例输入中，调用ch = getchar()中的块。我不知道这是否是预期的行为，但读取一个旨在写入的函数很奇怪。
read_str()：str_place[i] = (char) ch;你不使用(unsigned char)有点奇怪。

==284==ERROR：AddressSanitizer：stack-buffer-underflow

1条答案

相关问题

热门标签

最新问答