Boyer Moore算法实现遇AddressSanitizer栈缓冲区下溢问题求助

我正在实现一个简化版Boyer-Moore算法，因输入数据可能极大而采用环形缓冲区处理。程序需输出所有与模式串比较过的字符位置，但提交至GitLab服务器后测试失败，这些测试用于检测未定义行为（UB）。已知失败源于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;
}

输入输出示例 #

• 输入：example\nthis is simple example
• 输出：7, 14, 13, 12, 11, 10, 20, 22, 21, 20, 19, 18, 17, 16

错误信息 #

==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

问题分析与修复 #

错误根源 #

错误信息显示，在search_substr函数的第87行（对应代码中的for循环）发生了栈缓冲区下溢，访问了pat数组的负数索引位置。问题出在循环条件的求值顺序：

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

C语言中逻辑与&&是短路求值，但这里先判断字符相等，再检查j >= 0。当j递减到-1时，会先执行pat[j]（即pat[-1]），这会访问pat数组起始地址之前的栈内存，触发缓冲区下溢。

修复方案 #

调整循环条件的顺序，先检查j >= 0，确保不会访问负数索引的数组元素：

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

这样当j变为-1时，短路求值会直接终止循环，不会执行pat[j]的访问。

错误信息中地址的解读 #

ASan给出的访问地址0x7ffd3cdb915f位于main函数栈帧的偏移31处，而pat数组在栈中的存储范围是偏移32到49。偏移31在pat的起始位置之前，说明程序访问了pat[-1]，这就是缓冲区下溢的直接证据。

内容的提问来源于stack exchange，提问作者papacuma