我正在编写一个更简单版本的 Boyer Moore 算法，我需要使用循环缓冲区，因为可能会有很大的输入。程序应写入已与模式进行比较的符号的所有位置。但是当我将程序提交到 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;
}
input: example\nthis is simple exampleoutput: 7, 14, 13, 12, 11, 10, 20, 22, 21, 20, 19, 18, 17, 16the 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
int pat_len = read_str(MAX_PATTERN_LEN, pat, &is_patread, NULL)被推迟时，
ind_EOFind_EOF