自定义长算术函数触发AddressSanitizer堆缓冲区溢出问题求助

问题描述 #

实现了一套自定义长算术函数，运行时触发AddressSanitizer堆缓冲区溢出错误，错误发生在inf_sum函数第72行，调用链路为inf_sum→inf_add→inf_product→inf_multi→inf_pow→main。仅通过__inf_domain_expansion函数管理__INTINF变量内存（接近溢出时扩容2倍），尝试调整扩容触发条件至使用率超80%仍未解决，确认是digits数组内存不足导致。

错误日志 #

==11157==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60e0004b72c0 at pc 0x55bf1bedcc01 bp 0x7ffc5d6d6c00 sp 0x7ffc5d6d6bf0
READ of size 8 at 0x60e0004b72c0 thread T0
    #0 0x55bf1bedcc00 in inf_sum /home/user/C/longArithmetic/intinf.c:72
    #1 0x55bf1bedcedc in inf_add /home/user/C/longArithmetic/intinf.c:91
    #2 0x55bf1bedd037 in inf_product /home/user/C/longArithmetic/intinf.c:106
    #3 0x55bf1bedd19e in inf_multi /home/user/C/longArithmetic/intinf.c:115
    #4 0x55bf1bedd2c5 in inf_pow /home/user/C/longArithmetic/intinf.c:127
    #5 0x55bf1bedc448 in main /home/user/C/longArithmetic/test.c:14
    #6 0x7f8425afed8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #7 0x7f8425afee3f in __libc_start_main_impl ../csu/libc-start.c:392
    #8 0x55bf1bedc264 in _start (/home/user/C/longArithmetic/test.out+0x1264)

0x60e0004b72c0 is located 0 bytes to the right of 160-byte region [0x60e0004b7220,0x60e0004b72c0)
allocated by thread T0 here:
    #0 0x7f8425e99887 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:145
    #1 0x55bf1bedc574 in inf /home/user/C/longArithmetic/intinf.c:16
    #2 0x55bf1bedd132 in inf_multi /home/user/C/longArithmetic/intinf.c:113
    #3 0x55bf1bedd2c5 in inf_pow /home/user/C/longArithmetic/intinf.c:127
    #4 0x55bf1bedc448 in main /home/user/C/longArithmetic/test.c:14
    #5 0x7f8425afed8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58

SUMMARY: AddressSanitizer: heap-buffer-overflow /home/user/C/longArithmetic/intinf.c:72 in inf_sum
Shadow bytes around the buggy address:
  0x0c1c8008ee00: fd fd fd fd fa fa fa fa fa fa fa fa fd fd fd fd
  0x0c1c8008ee10: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0c1c8008ee20: fa fa fa fa fa fa fa fa fd fd fd fd fd fd fd fd
  0x0c1c8008ee30: fd fd fd fd fd fd fd fd fd fd fd fd fa fa fa fa
  0x0c1c8008ee40: fa fa fa fa 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c1c8008ee50: 00 00 00 00 00 00 00 00[fa]fa fa fa fa fa fa fa
  0x0c1c8008ee60: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0c1c8008ee70: fd fd fd fd fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c1c8008ee80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c1c8008ee90: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c1c8008eea0: 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
  Shadow gap:              cc
==11157==ABORTING

关键定义 #

#define MODULO      (1000000000000000000ULL)
#define START_SIZE  (20)

typedef long long          int64;
typedef unsigned long long u64;
typedef unsigned char      u8;

原始函数源码 #

void inf_sum(__INTINF *dst, __INTINF *num1, __INTINF *num2)
{
    __inf_clear(dst);

    __INTINF *max_num = NULL;
    int64     max_count = 0;
    u8        carry_flag = 0;
    if (num1->count > num2->count) {
        max_num = num1;
        memset(num2->digits + num2->count, 0, num1->count - num2->count);
    }
    else if (num2->count > num1->count) {
        max_num = num2;
        memset(num1->digits + num1->count, 0, num2->count - num1->count);
    } else {
        max_num = num1;
    }
    max_count = max_num->count;

    for (int i = 0; i < max_count; ++i) {
        dst->count++;
        __inf_domain_expansion(dst);
        dst->digits[i] = num1->digits[i] + num2->digits[i] + carry_flag;
        carry_flag = 0;
        if (dst->digits[i] > MODULO - 1) {
            dst->digits[i] -= MODULO;
            carry_flag = 1;
        }
    }
    
    if (carry_flag) {
        dst->count++;
        __inf_domain_expansion(dst);
        dst->digits[dst->count] = carry_flag;
    }
}

void inf_add(__INTINF **num1, __INTINF *num2)
{
    __INTINF *new_num1 = inf();

    inf_sum(new_num1, *num1, num2);

    inf_free(*num1);

    *num1 = new_num1;
}

void inf_product(__INTINF **dst, __INTINF *num1, __INTINF *num2)
{
    __inf_clear(*dst);

    int64 times = 0;
    for (int i = 0; i < num2->count; ++i) {
        times = (num2->digits[i]) * (int64)pow(MODULO, i);;
        for (int j = 0; j < times; ++j) {
            inf_add(dst, num1);
        }
    }
}

void inf_multi(__INTINF **num1, __INTINF *num2)
{
    __INTINF *new_num1 = inf();

    inf_product(&new_num1, *num1, num2);

    inf_free(*num1);

    *num1 = new_num1;
}

void inf_pow(__INTINF **dst, __INTINF *num, u64 exp)
{
    __inf_copy(dst, num);

    for (int i = 0; i < exp - 1; ++i) {
        inf_multi(dst, num);
    }
}

static void __inf_domain_expansion(__INTINF *num)
{
    if (num->count >= num->size) {
        num->size *= 2;
        num->digits = (u64*)realloc(num->digits, num->size * sizeof(u64));
        memset(num->digits + num->count, 0, num->size);
    }
}

主程序代码 #

__INTINF *n1 = inf(); /* Allocate memmory to var n1 */
__INTINF *n2 = inf(); /* Allocate memmory to var n1 */

inf_put(n1, 127ULL); /* Initializes n1 data */

inf_pow(&n2, n1, 6512); /* Raises n1 to power of 6512 */

问题分析与修复方案 #

1. 核心错误点 #

(1) inf_sum中越界访问短数组的digits

当num1和num2长度不同时，直接用memset填充短数组的digits到长数组长度，但短数组的digits内存空间可能不足以容纳额外元素，导致越界读写。正确做法是不修改原数组，而是在求和时判断索引是否超出短数组的count，超出则取0。

(2) __inf_domain_expansion中memset长度错误

memset(num->digits + num->count, 0, num->size)的长度参数是字节数，但实际需要填充的是num->size - num->count个u64元素，正确长度应为(num->size - num->count) * sizeof(u64)，否则会越界写内存。

(3) inf_sum进位处理时索引越界

dst->digits[dst->count] = carry_flag中，dst->count已经是加1后的元素个数，数组索引应从0开始，正确索引为dst->count - 1，否则会访问超出数组范围的内存。

(4) inf_product实现逻辑完全错误

用循环加法模拟乘法完全不可行（比如MODULO=1e18时，循环次数会达到天文数字），必须改用长乘法的逐位累加逻辑，否则程序无法正常运行且会导致内存异常。

2. 修复后的代码 #

void inf_sum(__INTINF *dst, __INTINF *num1, __INTINF *num2)
{
    __inf_clear(dst);

    int64 max_count = num1->count > num2->count ? num1->count : num2->count;
    u8    carry_flag = 0;

    for (int i = 0; i < max_count; ++i) {
        dst->count++;
        __inf_domain_expansion(dst);
        // 索引超出数组count时取0，避免越界访问
        u64 val1 = (i < num1->count) ? num1->digits[i] : 0;
        u64 val2 = (i < num2->count) ? num2->digits[i] : 0;
        dst->digits[i] = val1 + val2 + carry_flag;
        carry_flag = 0;
        if (dst->digits[i] >= MODULO) {
            dst->digits[i] -= MODULO;
            carry_flag = 1;
        }
    }
    
    if (carry_flag) {
        dst->count++;
        __inf_domain_expansion(dst);
        dst->digits[dst->count - 1] = carry_flag; // 修正索引
    }
}

void inf_add(__INTINF **num1, __INTINF *num2)
{
    __INTINF *new_num1 = inf();

    inf_sum(new_num1, *num1, num2);

    inf_free(*num1);

    *num1 = new_num1;
}

// 修复长乘法实现
void inf_product(__INTINF **dst, __INTINF *num1, __INTINF *num2)
{
    __inf_clear(*dst);
    // 乘法结果最多有num1->count + num2->count位
    int64 result_max_count = num1->count + num2->count;
    // 先扩容到足够大小
    while ((*dst)->size < result_max_count) {
        __inf_domain_expansion(*dst);
    }

    for (int i = 0; i < num1->count; ++i) {
        u8 carry = 0;
        for (int j = 0; j < num2->count; ++j) {
            int64 pos = i + j;
            // 计算当前位的累加值
            unsigned __int128 sum = (unsigned __int128)(*dst)->digits[pos] 
                                  + (unsigned __int128)num1->digits[i] * num2->digits[j]
                                  + carry;
            (*dst)->digits[pos] = (u64)(sum % MODULO);
            carry = (u8)(sum / MODULO);
        }
        // 处理当前i的进位
        int64 pos = i + num2->count;
        while (carry && pos < result_max_count) {
            unsigned __int128 sum = (unsigned __int128)(*dst)->digits[pos] + carry;
            (*dst)->digits[pos] = (u64)(sum % MODULO);
            carry = (u8)(sum / MODULO);
            pos++;
        }
    }

    // 更新实际有效位数
    (*dst)->count = result_max_count;
    while ((*dst)->count > 0 && (*dst)->digits[(*dst)->count - 1] == 0) {
        (*dst)->count--;
    }
    if ((*dst)->count == 0) {
        (*dst)->count = 1; // 至少保留一位0
    }
}

void inf_multi(__INTINF **num1, __INTINF *num2)
{
    __INTINF *new_num1 = inf();

    inf_product(&new_num1, *num1, num2);

    inf_free(*num1);

    *num1 = new_num1;
}

void inf_pow(__INTINF **dst, __INTINF *num, u64 exp)
{
    __inf_clear(*dst);
    // 初始化结果为1
    inf_put(*dst, 1ULL);

    __INTINF *base = inf();
    __inf_copy(&base, num);

    // 快速幂优化，避免重复乘法
    while (exp > 0) {
        if (exp % 2 == 1) {
            inf_multi(dst, base);
        }
        inf_multi(&base, base);
        exp /= 2;
    }
    inf_free(base);
}

static void __inf_domain_expansion(__INTINF *num)
{
    if (num->count >= num->size) {
        num->size *= 2;
        num->digits = (u64*)realloc(num->digits, num->size * sizeof(u64));
        // 修正memset长度：填充新增的元素，每个元素是u64
        memset(num->digits + num->count, 0, (num->size - num->count) * sizeof(u64));
    }
}

3. 额外优化 #

• inf_pow改用快速幂算法，将时间复杂度从O(exp)降至O(log exp)，避免6512