Mdr-C-Tutorial

21.7 差分测试与边界验证 ​

在单元测试编写中，开发者往往容易陷入一种虚假的安全感。以实现 mdr_strspn 为例：精心构造 12 组涵盖空串、空集合、全匹配、前缀匹配以及全不匹配的经典断言，测试全部顺利通过。然而一旦将同一个函数接入自动化对照流水线，让它与系统标准库在 255 个非零单字节输入上逐个核对，控制台上瞬间爆出 128 处不一致。

手写的测试用例本身逻辑成立，但其视野被局限在常见的 7 位 ASCII 字符区间内；而算法实现为了节省内存开销，将字符查找表武断地截断为 128 项，直接导致高位落在 0x80 至 0xFF 区间的扩展字节全部被判定为集合外：

c
#include <stdbool.h>
#include <stdio.h>
#include <string.h>

/* 被测试的 mdr_strspn。作者假设「项目里的文本都是英文」，
 * 因而把查找表缩到 128 项，高半区一律当作集合外。 */
size_t mdr_strspn(const char *s, const char *accept) {
    bool in_set[128] = {false};
    size_t n = 0;

    while (*accept != '\0') {
        if ((unsigned char)*accept < 128) {
            in_set[(unsigned char)*accept] = true;
        }
        accept++;
    }
    while (s[n] != '\0' && (unsigned char)s[n] < 128 &&
           in_set[(unsigned char)s[n]]) {
        n++;
    }
    return n;
}

针对上述实现的验证结果形成了鲜明反差：12 组手写断言无一报错，而全量字节扫查则将高位缺陷全数捕获：

zsh - story
text
$ ./story
hand-written: 12 checks, 0 failed
MISMATCH byte 0x80: got 0, want 1
MISMATCH byte 0x81: got 0, want 1
MISMATCH byte 0x82: got 0, want 1
differential: 255 single-byte inputs, 128 mismatches

无论在 Linux 还是 Windows 环境下，输出的失败条目均逐行一致。128 处分歧恰好精准覆盖了从 0x80 到 0xFF 的全部字节空间，无一遗漏。

本节我们将系统化构建这套跨平台质量保障体系：确立高置信度的基准参考实现，制定输出结果规范化（Normalization）协议，依托小规模穷举与代数边界值全方位覆盖输入空间，借助内存防护字节与动态插桩（Sanitizer）精准捕获越界访问，并利用测试用例自动缩小算法（Test Case Reduction）提炼最小可复现缺陷集。完成本节后，mdr_ 库中的每个函数都将拥有一套秒级执行、具备确定性复现能力的工业级验证网。

1. 差分测试原理与预言机机制 ​

差分测试（Differential Testing）的核心思路是将完全相同的输入流分别注入两个在功能语义上应当等价的独立实现，并自动比对两者的输出行为。这种测试范式不直接回答“给定输入的绝对正确解是什么”，而是专注于核验“两个实现给出的结果是否彼此一致”。

这一策略绕开了软件工程测试中最棘手的难题：测试预言机（Test Oracle）的构建。在面对复杂的系统状态或海量边界组合时，人工推导并硬编码每一组输入的期望输出极其繁琐且极易出错；相比之下，校验两个实现是否输出了相同的偏移、长度或状态，在工程自动化上要轻量且稳固得多。

1998 年，William M. McKeeman 首次系统化地将差分测试应用于 C 编译器的验证：将相同的随机 C 程序输入多个编译器，观察生成的可执行文件在运行时行为是否等价。随后 Csmith 工具将这一思想推向极致，通过自动生成海量符合标准规范的复杂 C 程序并向 GCC 与 LLVM 喂入，在各大主流编译器中挖掘出数百个潜藏多年的代码生成缺陷。这些实践充分印证了差分测试的适用场景：当存在一个相对可信的参照体系，而被测系统的分支复杂度远超人工枚举能力时，差分测试能够释放出巨大的缺陷捕获能量。

在基础库开发中，参照实现主要有三大历史源流，其置信度自上而下递减：

参照来源典型代表核心优势局限与盲区
宿主标准库strspn、memcmp、memmove历经数十年的工业级检验，其实际行为即是事实规格仅覆盖 ISO C 既定标准接口，非标扩展函数无原生参照
显然正确的慢版本逐位展开的 clz、暴力双循环匹配的 memmem适用范围广，控制流结构简单直白，正确性肉眼可见慢版本本身的逻辑疏漏会伪装成被测对象的缺陷
多重构建靶标21.6 中的内建加速与回退版本确保同一套代码库在不同编译器优化分支下语义等价若双轨均存在相同的认知偏差，差分无法察觉

第三类参照在 21.6 中已经付诸实践：由 CMake 分别编出 mdr 与 mdr_fallback 两个静态库，一条走硬件内建加速，一条走纯 C 算法。通过将两套产物的行为逐一比对，可以有效防范在编写回退分支时抄错数值掩码、移位方向倒置等人为手滑缺陷。虽然该手段无法查出双轨共享的架构逻辑通病，却能精准阻击特性适配层的退化。

差分测试依托相对一致性规避人工预言盲区

差分测试的核心契约在于“检验行为等价性”，而非直接证明“逻辑的绝对正确性”。若选取的基准参考实现自身存在缺陷，双轨很可能“高度一致地输出错误”，从而导致测试在虚假的平静中绿灯通过。因此在遴选参照源时，应优先采用宿主系统的成熟标准库；当针对非标扩展函数自行编写朴素参考实现时，必须保持其逻辑单调纯粹，并在源码中详尽阐明其算法直白性。

❌ 人工硬编码期望值
c
CHECK_EQ_SIZE(mdr_strspn("12345abc", "0123456789"), 5u);
CHECK_EQ_SIZE(mdr_strspn("aabb", "ab"), 4u);
/* 测试质量高度依附于作者个人的边界想象力 */
✅ 差分循环全域比对
c
for (int c = 1; c < 256; c++) {
    char text[2] = {(char)c, '\0'};

    if (mdr_strspn(text, text) != strspn(text, text)) {
        report(c);
    }
}
/* 输入由循环按字符全集自动派生，边界无处遁形 */

左栏的写法把软件的质量上限死死捆绑在开发者的主观经验上，极易漏过非 ASCII 码区；右栏的差分循环则将输入域交给代数全集，255 种非零字节无一漏网，高位缺陷自然无所遁形。

单选

差分测试全部通过，能说明被测实现一定正确吗？

参照实现本身有缺陷，两份实现一致地算错
被测实现有缺陷，与参照不一致
两份实现的返回值类型不同
比较时没有规范化，把允许的差异当成了缺陷

2. 输出结果规范化 ​

在差分测试工程中，两个实现输出的裸数据往往无法直接用 == 进行机械比对。标准库中诸多接口的规范契约仅约束了相对逻辑，而非固定整型数值。

以最基础的字符串比较接口 strcmp 为例：ISO C 规范仅规定其实参按字典序在前时返回负值、相等返回 0、在后返回正值。不同 C 运行时的具体落地策略大相径庭：glibc 倾向于直接返回首个不匹配字符的无符号差值（如 'p' - 'r' = -2），而 Windows UCRT 则习惯将其归一化为 -1 与 1。若直接比对原始返回值，这种符合标准规范的实现自由度就会被测试套件误判为软件缺陷：

c
#include <stdio.h>
#include <string.h>

static int sign(int value) {
    if (value < 0) {
        return -1;
    }
    if (value > 0) {
        return 1;
    }
    return 0;
}

int main(int argc, char *argv[]) {
    const char *lhs = argc > 1 ? argv[1] : "apple";
    const char *rhs = argc > 2 ? argv[2] : "apricot";

    printf("strcmp(\"%s\", \"%s\") = %d\n", lhs, rhs, strcmp(lhs, rhs));
    printf("sign                   = %d\n", sign(strcmp(lhs, rhs)));
    return 0;
}
zsh - norm2
text
$ gcc -std=c17 -Wall -Wextra -o norm2 norm2.c
$ ./norm2
strcmp("apple", "apricot") = -2
sign                   = -1
$ ./norm2 apricot apple
strcmp("apricot", "apple") = 2
sign                   = 1
PowerShell - norm2
text
PS> gcc -std=c17 -Wall -Wextra -o norm2.exe norm2.c
PS> .\norm2.exe
strcmp("apple", "apricot") = -1
sign                   = -1
PS> .\norm2.exe apricot apple
strcmp("apricot", "apple") = 1
sign                   = 1

在上述终端对比中，面对相同输入，Linux 下返回 -2，Windows 下返回 -1。但经过符号规范化函数 sign(...) 收敛后，两边的测试结论呈现出清晰的确定性。

这里还有一个至关重要的编译期细节：测试中的实参对象必须取自运行时（如从命令行实参 argv 读取），决不可直接传递硬编码的字符串字面量常量。若写成常量调用，现代优化编译器前端会在常量折叠（Constant Folding）阶段直接计算出比较结果，掩盖了不同目标机器的运行时差值分歧（正如在 21.1 中字面量 strlen 被直接替换为立即数）。差分测试的所有输入流都应来自于运行期动态装载，彻底杜绝优化器“替被测代码做主”的隐蔽干扰。

在更广泛的函数集合中，规范化需针对四类典型输出形态进行处理：

差异类别根因机制与处理策略
比较函数的具体数值统一提取符号。strcmp、strncmp、memcmp 契约仅约束正负零，需通过 sign() 映射至 -1, 0, 1
查找函数返回的绝对指针换算为相对基地址的字节偏移量，未命中时统一映射为 -1。适用于 mdr_strstr、mdr_strchr、mdr_memchr、mdr_memmem
复制函数的目标缓冲区镜像必须核验预分配缓冲区的全域镜像，切忌仅比对到首个空字符。strncpy 尾部填零是否足额、strlcpy 截断时是否违规越界写入，均暴露在终止符后方
未指定状态与副作用参数排除比对范围。成功调用后 errno 不受保障；strtok 内部游标绝对地址、qsort 针对键值重复元素的内部排序稳定性均不属必须一致的规范内容

为了让测试代码保持聚焦，我们将这套规范化工具集中收纳于 tests/diff_util.h 与配套的 tests/diff_util.c 中：

c
/* 把任意整数规范化成 -1、0 或 1，只保留符号。 */
int diff_sign(int value);

/* 把查找函数返回的指针换成相对 base 的偏移；NULL 返回 -1。 */
long diff_offset(const void *base, const void *found);

/* 报告一次不一致：打印说明、输入与期望/实际值，并计入失败数。 */
int diff_report(const char *what, const void *input, size_t input_len,
                long expected, long actual);

/* 打印「套件: 总数 comparisons, 失败数 failed」，有失败返回 1。 */
int diff_summary(const char *suite);

辅助函数 diff_offset 统一屏蔽了指针判空与基地址相减的重复操作，diff_report 则接管了格式化输出与错误计数。值得注意的是，diff_report 采用了节流策略：仅针对前 5 次失败打印完整的输入切片与 HexDump 细节，后续分歧则仅累加计数。在真实开发中，单一逻辑缺陷往往会引发成百上千次连续报错，全量倾倒日志只会淹没最初也是最有价值的那条首发线索。

3. 测试输入的生成策略 ​

人工硬编码测试用例最大的短板在于覆盖广度高度受制于开发者的主观想象。在工程化差分测试中，测试输入的构造主要依赖三条技术路径，各自兼具特定的性能开销与覆盖优势。

3.1 紧凑空间组合穷举 ​

针对字符串检索与内存搬运这类算法，只要严格约束字符集字母表的宽度与输入序列的最大长度，所有可能的状态组合便能完全收敛在可控规模内。例如将字符表限制在 {'a','b','c'} 三个元素，并将主串（Haystack）长度限制在 4 以内、子串（Needle）长度限制在 2 以内：

c
/* 在字母表上按字典序生成下一个等长字符串；全部回绕时返回 0。 */
static int next_string(char *buf, size_t len, const char *alphabet) {
    size_t alpha_len = strlen(alphabet);

    for (size_t i = len; i > 0; i--) {
        const char *pos = strchr(alphabet, buf[i - 1]);

        if ((size_t)(pos - alphabet) + 1 < alpha_len) {
            buf[i - 1] = pos[1];
            return 1;
        }
        buf[i - 1] = alphabet[0];
    }
    return 0;
}

按照该规则，候选主串共有 1+3+9+27+81=121 种形态，候选子串有 1+3+9=13 种形态，两者笛卡尔积配对产生 1573 组样本。针对每组样本并行交叉核对六个基础字符串检索函数，累计产生 9438 次断言比对。测试程序 diff_string 另外单独遍历了 256 种非零单字节作为主串，再追加 3072 次比对，总体覆盖规模达到 12510 次。这类统计指标均由测试框架在运行时动态汇总，无需人工静态记账。

内存重叠拷贝接口 mdr_memmove 同样可以在一块 16 字节的局部缓冲区上实施组合穷举：目标偏移 dest、源偏移 src 与传输字节数 count 各自遍历 0 至 15 的全区间，仅剔除内存越界的非法组合，最终保留 1751 组有效样本。测试用例在调用前将缓冲区预填充为递增序列（0x01, 0x02, ..., 0x10），分别执行标准 memmove 与自研版本，随后对整块 16 字节的内存镜像执行全量位比对：

c
for (size_t dest = 0; dest < 16; dest++) {
    for (size_t src = 0; src < 16; src++) {
        for (size_t count = 0; count < 16; count++) {
            unsigned char a[16];
            unsigned char b[16];

            if (dest + count > 16 || src + count > 16) {
                continue;
            }
            for (size_t i = 0; i < 16; i++) {
                a[i] = (unsigned char)(i + 1u);
                b[i] = a[i];
            }
            memmove(a + dest, a + src, count);
            mdr_memmove(b + dest, b + src, count);
            if (memcmp(a, b, 16) != 0) {
                diff_report("memmove", b, 16, (long)dest, (long)src);
            } else {
                diff_ok();
            }
        }
    }
}

这段三重循环将内存重叠拷贝中最容易翻车的搬运方向全面展开。mdr_memmove 在底层规定：当 dest < src 时采用正向升序搬运，否则必须切换为逆向降序搬运。1751 组样本彻底覆盖了自重叠、相邻重叠、完全分离以及零长度空转的所有微观分支。

3.2 整数域按位穷举 ​

纯算术与位操作函数虽然没有可变文本那样的长度维度，但在低位宽区间内的状态空间同样可以被全量铺开。针对 mdr_clz_u32、mdr_ctz_u32 以及 mdr_popcount_u32，我们直接使用从 0x0000 到 0xFFFF 的全部 16 位无符号整数进行遍历：

c
/* 参照：显然正确的慢版本，每一位单独看。 */
static unsigned slow_clz_u32(uint32_t x) {
    unsigned n = 0;

    if (x == 0) {
        return 32;
    }
    for (uint32_t bit = 0x80000000u; (x & bit) == 0; bit >>= 1) {
        n++;
    }
    return n;
}

针对 65536 个数值各自比对三种位操作，累计 196608 次高密度比对在现代 CPU 上仅耗费数十毫秒。此处坚决采用逐位轮询的慢版本而非编译器自带的 __builtin_clz，原因在于内建加速分支本身正是待检验的被测对象，若拿它当基准，抽象层自身的架构盲区便无法被察觉。慢版本逻辑清晰单调，正确性一目了然，完美契合了基准参照的设计准则。

3.3 伪随机状态空间抽样 ​

纯粹基于有限集合的穷举存在固有瓶颈：面对动辄数十 KB 的长文本流、极其严苛的重复模式或极端对齐位移，穷举计算量会迅速发生维度爆炸。此时必须引入由受控伪随机数生成的动态输入流作为有力补充。这部分机制将在第 6 节展开。

三种输入来源的工程权衡十分清晰：组合穷举提供确定性的全域覆盖，但受限于状态空间爆炸；代数边界值开销极低且直击极端转折点；而伪随机生成则能轻而易举探索超长数据跨度。

小范围穷举背后依托着一条经验观察：底层字符串与内存函数的逻辑缺陷（如差一错误、跳出条件判定失准等）绝大多数在长度 3 到 5 的短序列上就会直接暴露。而对于更高级的定位算法（例如仅在特定长模式末尾才触发的子串查找分支），则需要借助后续的覆盖率导向模糊测试予以最终补位。

4. 边界值分析与特异点阵列 ​

与均匀撒网式的概率采样不同，边界值分析（Boundary Value Analysis）采取了一种高度聚焦的进攻姿态：它不在广袤的常规输入域中消耗过多算力，而是专门捕杀参数空间中处于极值、阶跃点以及符号跳变的奇异临界区。

经验表明，程序中的缺陷有相当大的比例集中爆发在循环终结边界与代数比较运算符的右侧。典型的特异值构造矩阵包括：长度维度上的 0、1、n-1、n、n+1；数值域中的 0、1、各类 2k 与 2k±1、全 1 位掩码；字符串层面的空串、单字符串，以及终止空字符恰好贴紧容量边界等极端工况：

函数边界值
mdr_strncpy、mdr_strlcpycount 为 0、1；源串长度等于 count-1、count、count+1
mdr_strncat、mdr_strlcat目标已有内容恰好填满；剩余空间为 0、1、刚好装下源串
mdr_strspn、mdr_strcspn集合为空；首字符在集合内外；整个串都在集合内
mdr_strstr、mdr_memmemneedle 为空；needle 比 haystack 长；命中在开头、末尾、不命中
mdr_clz_u32、mdr_ctz_u320、1、最高位、最低位、UINT32_MAX
mdr_bit_ceil_u320、1、2 的幂、2 的幂加一、0x80000001
mdr_ckd_add_size0、1、SIZE_MAX、SIZE_MAX - 1、两数之和恰好等于 SIZE_MAX
mdr_align_up_size已对齐、差一字节、align 为 1、align 为最大值

组合穷举与边界值矩阵构成了相辅相成的双层滤网：前者保证常规短序列的拓扑结构全量覆盖，后者确保算术进位与极值断点固若金汤。在自动化测试体系中，两者的执行时间通常都在几毫秒内，在持续集成中应当全量常驻。

4.1 边界验证与精确内存分配 ​

要探查底层字符串与内存函数是否存在潜在的指针越界，仅关注逻辑数值是远远不够的，还必须审查其底层的物理内存布局。

若在测试用例中习惯性地在缓冲区末尾“多留几字节作为安全垫”，越界访问就会悄无声息地落入闲置内存中，既不会破坏有效数据，也不会触发段错误，从而使内存越界缺陷彻底遁形。唯有将测试对象按其逻辑长度严丝合缝地精确分配，并将目标数据紧贴容器边缘放置，越界的读写行为才能被宿主环境捕获：

c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
    char *p = malloc(5);

    memcpy(p, "hello", 5);
    printf("length = %zu\n", strlen(p));
    free(p);
    return 0;
}

malloc(5) 仅分配了 5 字节堆空间，填入的 5 个有效字符末尾不带任何 \0。在 Linux 环境下启用 ASan 编译执行：

zsh - gcc -fsanitize=address
text
$ gcc -std=c17 -g -fsanitize=address -o asan_read asan_read.c
$ ./asan_read
=================================================================
==1340540==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x502000000015 at pc 0x7f6c5c879026 bp 0x7ffc986fdca0 sp 0x7ffc986fd460
READ of size 6 at 0x502000000015 thread T0
    #0 0x7f6c5c879025 in strlen ../../../../src/libsanitizer/sanitizer_common/sanitizer_common_interceptors.inc:391
    #1 0x55a612cb31f5 in main /home/minsecrus/tutorial/work/p070/work/asan_read.c:10
    #2 0x7f6c5c635ca7  (/lib/x86_64-linux-gnu/libc.so.6+0x29ca7) (BuildId: c495b62edadd6c356265942ec1282d98058a7b41)
    #3 0x7f6c5c635d64 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x29d64) (BuildId: c495b62edadd6c356265942ec1282d98058a7b41)
    #4 0x55a612cb30f0 in _start (/home/minsecrus/tutorial/work/p070/work/asan_read+0x10f0) (BuildId: c93b057037337bd0d7f1e15f20051ccbf8fa9a56)

0x502000000015 is located 0 bytes after 5-byte region [0x502000000010,0x502000000015)

AddressSanitizer 的诊断精准指明了溢出发生点：strlen 试图读取 6 个字节，超出了动态分配的 5 字节堆区域。若在编写测试时不假思索地调用 malloc(6) 甚至分配 16 字节缓冲区，这多出的填充空间就会成为隐蔽缺陷的温床，使得本该被拦截的未定义读写逃过编译器的法眼。

在缺乏编译器高级插桩环境的裸机平台或老旧工具链上，我们可以将这种“数据紧贴边缘”的思想转化为纯 C 实现的防护字节机制。通过构建轻量级包装对象，在数据区的前后两端分别铺设受控的哨兵字节，并在函数返回后核验哨兵是否完好：

c
/* 防护字节的个数：数据区前后各这么多字节。 */
#define DIFF_GUARD 16

typedef struct {
    unsigned char *raw;
    unsigned char *data;
    size_t size;
} diff_guard;

/* 分配 size 字节的数据区，前后各带 DIFF_GUARD 个 0xA5。成功返回 0。 */
int diff_guard_init(diff_guard *guard, size_t size);
void diff_guard_free(diff_guard *guard);

/* 检查哨字节是否完好；被改写时打印位置与内容，返回 1。 */
int diff_guard_check(const diff_guard *guard, const char *what);
c
int diff_guard_init(diff_guard *guard, size_t size) {
    guard->raw = (unsigned char *)malloc(size + 2 * DIFF_GUARD);
    if (guard->raw == NULL) {
        return -1;
    }
    for (size_t i = 0; i < DIFF_GUARD; i++) {
        guard->raw[i] = 0xA5;
        guard->raw[DIFF_GUARD + size + i] = 0xA5;
    }
    guard->data = guard->raw + DIFF_GUARD;
    guard->size = size;
    return 0;
}

int diff_guard_check(const diff_guard *guard, const char *what) {
    const unsigned char *front = guard->raw;
    const unsigned char *back = guard->raw + DIFF_GUARD + guard->size;

    diff_total++;
    for (size_t i = 0; i < DIFF_GUARD; i++) {
        if (front[i] != 0xA5) {
            diff_failed++;
            printf("GUARD %s: front[%zu] is %02X, expected A5\n", what, i,
                   front[i]);
            return 1;
        }
    }
    for (size_t i = 0; i < DIFF_GUARD; i++) {
        if (back[i] != 0xA5) {
            diff_failed++;
            printf("GUARD %s: data[%zu] is %02X, expected A5\n", what,
                   guard->size + i, back[i]);
            return 1;
        }
    }
    return 0;
}

5. 防护字节与越界拦截 ​

虽然 AddressSanitizer 功能强大，但它重度依赖特定的编译器驱动与专用运行时动态库。在原生 Windows 环境中，许多精简的 MinGW-w64 GCC 发行版并未随附 libasan，链接阶段常常直接受阻于 cannot find -lasan；而在嵌入式交叉编译或老旧架构上，ASan 往往无法直接就位。相比之下，防护字节（Guard Bytes，亦称哨兵字节 Canary Bytes）具备纯标准 C 的通用性，不依赖任何第三方运行时即可全平台开箱即用。

防护机制的逻辑极其直白：在目标数据区的前后两端分别留出固定跨度的衬垫区域，并在初始化时全部刷入特异的魔数标记。当被测函数执行完毕后，测试框架顺序扫描前后衬垫区；只要有任何一个魔数字节遭到篡改，即可判定发生了指针越界写。

在本库的实现中，衬垫填充字节统一选用 0xA5（二进制 10100101）。该数值既不是字符串结尾符 0x00，也不是常见的 ASCII 可打印英文字符，无论被误写为空字符还是普通字符，在十六进制比对中都极为醒目。这一整套管理逻辑被完整封装于 diff_guard 结构体及其实例函数中。

在验证定长拷贝函数 mdr_strlcpy 时，测试用例将数据区严格按照 dsize 分配，使得末尾的防护字节与缓冲区允许写入的终点紧紧相贴。此时人为注入一个典型的“多写一个空字符”的边界缺陷：

c
/* 注入的缺陷：多写一个字节。正确版本见 src/mdr_ext.c。 */
static size_t buggy_strlcpy(char *dst, const char *src, size_t dsize) {
    size_t len = strlen(src);

    if (dsize > 0) {
        size_t copy = len < dsize - 1 ? len : dsize - 1;

        memcpy(dst, src, copy);
        dst[copy] = '\0';
        dst[copy + 1] = '\0';
    }
    return len;
}

针对五组不同目标长度与源字符串组合执行拷贝，并在调用后立即核验哨兵区域：

zsh - diff_ext
text
$ ./diff_ext
GUARD strlcpy: data[1] is 00, expected A5
GUARD strlcpy: data[2] is 00, expected A5
GUARD strlcpy: data[6] is 00, expected A5
GUARD strlcpy: data[6] is 00, expected A5
diff_ext: 10 comparisons, 4 failed

诊断报告中的 data[1] 指向紧随有效数据区后方的首个哨兵字节。对于第一组设置 dsize = 1 的用例而言，规范契约仅允许写入 data[0] 作为终止符；报错信息直观反映了缺陷所在：算法在 dst[copy + 1] 处违规多写入了一个零字节，正好落入 data[dsize] 处将原本的 0xA5 污染为 0x00。在修复该缺陷后，同一套测试顺利通过全部 14 项细粒度检查。无论在 Linux 还是 Windows 原生环境下，输出完全一致。

统计计数从 14 降至 10 的原因在于熔断逻辑：一旦哨兵校验宣告失败，测试便不再对被污染的内容进行逻辑校验，四组失败用例各跳过了一次结果比较。

防护字节与动态插桩工具的技术特性对比如下：

校验手段外部依赖要求核心捕获能力固有盲区与限制
防护字节（Canary）纯标准 C 语法，无任何环境依赖数据区前后相邻内存的越界写入无法拦截越界读；无法捕捉跳跃式远距离覆写
AddressSanitizer（ASan）依赖现代编译器前端插桩与专用运行时库任意地址的读越界、写越界、释放后使用（UAF）难以探查未越界但逻辑未初始化的隐蔽脏读

由于哨兵字节位于数据区边界之外，只有在发生物理写入覆写时其数值才会改变；越界读取并不会在内存中留下物理印记，防护字节对此无能为力。为了排查越界读取，必须依赖 ASan 的影子内存（Shadow Memory）状态机。在工程流水线中，两者的协同策略是：防护字节内嵌于全平台自动化回归集中，随时编译常驻；ASan 构建（build-asan/）则作为高级质量门禁在持续集成中统一验收。

多选

要用防护字节抓住 mdr_strlcpy 多写一个字节的缺陷，下列哪些做法是必要的？

目标区正好按 dsize 分配，末尾不放余量
调用前后各检查一次哨字节
只检查返回值
用 ASan 构建跑同一批检查

mdr_strlcpy 的验证全景还印证了“审视缓冲区全域镜像”的重要性。若在测试中仅核验返回值与空字符结尾的常规字符串，多写入的那一个越界字符将永远被遮蔽；因为常规字符串比对一旦踩到首个 \0 便立即判定终结，根本无法洞察终止符后方的内存惨状。

diff_ext 的完整测试函数
c
static void check_strlcpy(const char *dst0, const char *src) {
    size_t dsize = strlen(dst0) + 1;
    diff_guard guard;

    if (diff_guard_init(&guard, dsize) != 0) {
        return;
    }
    memcpy(guard.data, dst0, dsize);
    size_t n = mdr_strlcpy((char *)guard.data, src, dsize);

    if (diff_guard_check(&guard, "strlcpy") == 0) {
        size_t want = strlen(src) < dsize - 1 ? strlen(src) : dsize - 1;

        if (n == strlen(src) && memcmp(guard.data, src, want) == 0) {
            diff_ok();
        } else {
            diff_report("strlcpy result", guard.data, dsize, (long)strlen(src),
                        (long)n);
        }
    }
    diff_guard_free(&guard);
}

目标缓冲区的长度取 strlen(dst0) + 1，也就是恰好装下原来的内容。哨字节检查通过后，再比较返回值和复制的前 min(strlen(src), dsize - 1) 个字节。每次调用计两次比较，五组 strlcpy 加两组 strlcat 一共 14 次。哨字节检查失败的那一次只剩一次比较，所以注入缺陷后总数从 14 掉到 10。

6. 确定性伪随机测试与跨平台可重现 ​

小规模组合穷举能够筑牢紧凑边界，代数特异点阵列能死守关键转折，而广袤的中间参数域则需交由伪随机输入流进行大密度抽样探测。在工程落地中，随机差分测试必须同时破解两个核心挑战：如何获得跨平台完全一致的高质量伪随机序列，以及一旦捕获分歧时如何做到百分之百可靠复现。

标准库提供的 rand() / srand() 完全无法胜任此项任务。ISO C 仅规定其返回值范围为 [0, RAND_MAX]，对其底层采用何种伪随机数算法未作任何强制约束。在不同 C 运行时体系下，相同的种子所生成的随机数流截然不同。在相同机器上分别使用 MinGW 的 UCRT 与 Linux glibc 观察种子为 1 时的前 5 个生成值：

text
41
18467
6334
26500
19169
text
1804289383
846930886
1681692777
1714636915
1957747793

两套环境输出的数列毫无交集。若在本地 Windows 开发机上用某个种子捕捉到了一处隐蔽崩溃，将该种子输入持续集成的 Linux 运行器时，测试流水线很可能一路畅通无阻，使得偶发缺陷沦为无法排查的“幽灵故障”。

最稳健的解决方案是在测试支持库中自主内嵌轻量级伪随机数生成器。经典的 splitmix64 算法仅需十余行代码，其状态空间仅为一个 uint64_t 对象：

c
uint64_t diff_random(uint64_t *state) {
    uint64_t z = (*state += 0x9E3779B97F4A7C15ULL);

    z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ULL;
    z = (z ^ (z >> 27)) * 0x94D049BB133111EBULL;
    return z ^ (z >> 31);
}

该算法的所有算术操作均严格局限在无符号 64 位整数的回绕加法、乘法、位移与异或运算中。由于标准 C 对无符号整数的溢出与位移行为拥有毫无歧义的严格规范，在任何合规的硬件与编译器上，相同的初始种子必然产出字符级完全一致的随机序列。借助命令行驱动测试：

c
int main(int argc, char *argv[]) {
    uint64_t state = argc > 1 ? (uint64_t)strtoull(argv[1], NULL, 0) : 1u;
    int count = argc > 2 ? atoi(argv[2]) : 5;

    for (int i = 0; i < count; i++) {
        printf("%016llx\n", (unsigned long long)splitmix64(&state));
    }
    return 0;
}

在两套操作系统上分别执行该探针：

zsh - rand_gen 1 5
text
$ ./rand_gen 1 5
910a2dec89025cc1
beeb8da1658eec67
f893a2eefb32555e
71c18690ee42c90b
71bb54d8d101b5b9

跨平台终端输出完全一致。数学运算的确定性排除了任何平台实现的自由发挥空间。

基于该生成器，标准随机差分测试驱动遵循统一的架构模式：在程序启动时自命令行解析随机种子与迭代轮数，首先打印当前的测试上下文；每轮迭代基于种子派生随机长度与缓冲区内容，并在遭遇结果分歧时立即固化输出当前种子与输入镜像：

c
int main(int argc, char *argv[]) {
    uint64_t seed = 1;
    int rounds = 1000;
    uint64_t state;

    for (int i = 1; i < argc; i++) {
        if (strcmp(argv[i], "--seed") == 0 && i + 1 < argc) {
            seed = diff_parse_seed(argv[++i]);
        } else if (strcmp(argv[i], "--rounds") == 0 && i + 1 < argc) {
            rounds = atoi(argv[++i]);
        }
    }
    printf("seed = 0x%llX, rounds = %d\n", (unsigned long long)seed, rounds);

    state = seed;
    for (int round = 0; round < rounds; round++) {
        size_t len = (size_t)(diff_random(&state) % 65u);
        unsigned char lhs[64];
        unsigned char rhs[64];
        int want;
        int got;

        fill_random(lhs, len, &state);
        memcpy(rhs, lhs, len);
        if (len > 0 && diff_random(&state) % 3u == 0) {
            size_t pos = (size_t)(diff_random(&state) % len);

            rhs[pos] = (unsigned char)(rhs[pos] ^ 0x80u);
        }
        want = diff_sign(memcmp(lhs, rhs, len));
        got = diff_sign(mdr_memcmp(lhs, rhs, len));
        if (want != got) {
            diff_report("memcmp", lhs, len, want, got);
        } else {
            diff_ok();
        }
    }
    return diff_summary("diff_memory");
}

每轮测试首先随机确定比对长度（0 至 64 字节），填充数据后以三分之一的先验概率将随机位置的字节最高位反转以制造内容分歧。为了提升对符号缺陷的敏感度，数据填充例程 fill_random 在字节流中刻意嵌入了零字节 0x00 与高位字节 0x80，因为均匀分布的随机数很难以足够的密度连续击中这两类临界值。

在测试执行时，控制台首先输出种子；当被测函数行为正确时测试顺利放行：

zsh - diff_memory
text
$ ./diff_memory --seed 0x1234 --rounds 5
seed = 0x1234, rounds = 5
diff_memory: 5 comparisons, 0 failed

此时若在 mdr_memcmp 中引入经典的历史缺陷：将内部比较指针强转为有符号的 char * 而非 unsigned char *，并使用相同的种子与轮次重新运行：

zsh - diff_memory --seed 0x1234 --rounds 5
text
$ ./diff_memory --seed 0x1234 --rounds 5
seed = 0x1234, rounds = 5
MISMATCH memcmp: input "\xB5\x00\x80<>\x00\x80r3\x00\x80\x1F\x15\x00\x80\x18\x86\x00\x80/\xC0\x00\x80\x0B\x83\x00\x80#\xD3\x00\x80\x0B\\"
  hex      B5 00 80 3C 3E 00 80 72 33 00 80 1F 15 00 80 18 86 00 80 2F C0 00 80 0B 83 00 80 23 D3 00 80 0B ... (33 bytes)
  expected -1, got 1
diff_memory: 5 comparisons, 1 failed

诊断报告完整呈现了转义字符串表示、十六进制内存切片、期望符号与实际符号。在该用例的下标 25 处，原始字节 0x00 经过最高位翻转变更为 0x80，前 25 个字节完全等价。按照标准无符号序关系，0x00 < 0x80，结果应当为负（-1）；但在有符号 char 解释下，0x80 被解释为负数 -128，比较操作误判为 0 > -128，导致输出反转为正（1）。

在 CI 流水线中，测试轮次的设定以运行时间为基准。1000 轮 memcmp 差分比对在主流处理器上仅需数十毫秒，即使扩大至 10000 轮也仅耗时 0.04 秒左右。测试的鲁棒性源于确定性种子的广泛探索，而非盲目调大单次测试时长。

随机差分测试必须具备完全的跨平台可重现性

随机差分测试严禁直接依赖宿主系统的 rand() 接口，必须采用项目内自建的跨平台确定性伪随机数发生器。测试每次执行必须在首行输出当前所用的随机种子；一旦遭遇断言失败，报告需完整记录种子、执行轮次与导致分歧的原始字节流。开发者在本地通过命令行传入 --seed 即可原样回放并单步调试该故障场景。

7. 诊断报告规范与测试用例自动缩小 ​

高质量的测试失败诊断应当具备自包含性，使开发者在不借助交互式调试器的情况下即可直观推断出缺陷的发生机理。一份合格的差分报告至少应囊括四大核心要素：被测操作名、完整的原始输入字节流、预期输出以及实际输出。若输入包含文本序列，则应同时给出 ASCII 可读视图与十六进制转储（HexDump）；前者直观展现语法结构，后者则能无所遁形地暴露隐藏在 0x80 以上的高位字节。

diff_report 默认将详细展开限制在前 5 次失败，其设计目的正在于保护“首发案发现场”。由于底层的单一逻辑错误往往会导致成百上千个连续样本齐刷刷报红，漫无节制的刷屏只会彻底冲走最初、最具特征的第一条诊断记录。

此外，随机生成的触发样本往往携带了大量与缺陷无关的冗余噪声。一段长达 64 字节的随机复合流所触发的符号翻转，实际上往往仅需 1 个特定字节即可触发。测试用例自动缩小（Test Case Reduction / Shrinking）算法能够系统化地剔除干扰字节，将庞杂的失败现场浓缩为最简可复现片段，便于直接固化为单测回归用例。

缩小器算法的核心策略在于交替执行“贪婪删除”与“语义降级”两个阶段：只要删减或简化后的输入依然能触发相同的断言失败，修改便被保留：

c
size_t diff_shrink(unsigned char *data, size_t len, diff_fail_fn fails,
                   void *ctx) {
    size_t i = 0;

    while (i < len) {
        unsigned char saved = data[i];

        memmove(data + i, data + i + 1, len - i - 1);
        if (fails(data, len - 1, ctx) != 0) {
            len--;
            continue;
        }
        memmove(data + i + 1, data + i, len - i - 1);
        data[i] = 0x00;
        if (fails(data, len, ctx) != 0) {
            i++;
            continue;
        }
        data[i] = (unsigned char)'a';
        if (fails(data, len, ctx) != 0) {
            i++;
            continue;
        }
        data[i] = saved;
        i++;
    }
    return len;
}

回调函数 fails 由调用方注入，用于判断给定的数据切片是否仍能复现双轨不一致。当单字节删除成功时，数据总长度减 1，游标下标 i 保持不动，以便继续考察平移过来的新字符；当删除受阻时，算法退而求其次尝试将其降级为最简数值 0x00 或可打印字符 'a'。若所有简化尝试均无法复现缺陷，则恢复该位置的原值并前进至下一字节。

针对前文那个由于使用有符号 char 导致比较翻转的 memcmp 缺陷，我们向缩小器注入一段全长 64 字节、每个元素均置位最高位的复杂输入：

c
/* 判定：这份输入上两份实现是否仍不一致（只比符号）。 */
static int still_fails(const unsigned char *data, size_t len, void *ctx) {
    unsigned char rhs[256];
    size_t n = len < sizeof rhs ? len : sizeof rhs;

    (void)ctx;
    memcpy(rhs, data, n);
    if (n > 0) {
        rhs[n - 1] = (unsigned char)(rhs[n - 1] ^ 0x80u);
    }
    return diff_sign(memcmp(data, rhs, n)) != diff_sign(buggy_memcmp(data, rhs, n));
}
zsh - shrink_demo
text
$ ./shrink_demo
before: 64 bytes "\xB4\xF5\xB3\x8D\xF5\xCA\x90\xB1\xF3\xA7\xD9\x9A\xCC\xB9\x87\x92\xDD\xC0\x8B\xDC\xC4\x94\xE5\xA3\x9E\xB8\x87\xB0\xFE\xBA\xDC\xAC\xD2\xDD\x9E\xE2\x89\xBC\xD9\xCC\x98\xC9\xF1\xAD\xCE\x89\x8D\xC4\xBE\xEE\x9A\xF6\xFD\xCC\xA8\xAD\x87\xE5\x8A\xCB\xC5\xB3\xC8\xC8"
after:  1 bytes "\x00"

整整 64 字节的杂乱序列被利落地剪裁至仅剩单字节 0x00。归约过程条理清晰：由于每一个字节的最高位都被预先置 1，前面 63 个字节无论如何移除都不影响最终符号错位，长度一路收缩至 1；随后替换阶段将仅存的单字节成功降级为 0x00。在 0x00 与反转最高位后的 0x80 之间，无符号与有符号比对的符号完全对立，缺陷被极致纯化。在回归套件中，固化这样一对干净的两字节对照用例，其可读性与防退化价值远胜直接硬编码原始的 64 字节脏数据。

需要注意：缩小器依赖高频调用判定谓词 fails。在针对复杂数据结构实施归约时，必须确保判定逻辑与最初捕获失败的准则百分之百等价；若判定条件定义松散，缩小器很可能会“漂移”到另一个无关的边界分支上，生成一份与原始缺陷风马牛不相及的假样本。

8. 基于覆盖率导向的差分模糊测试 ​

组合穷举与伪随机抽样在生成输入时，依然依赖开发者预先设定的数据骨架。然而在诸如 mdr_memmem 这样的子序列定位算法中，某些极其隐蔽的逻辑缺陷可能只在“子串恰好对齐在主串终结边缘且前驱字节存在局部重复”的极狭窄条件下才会发作。在盲目随机生成下，触及该状态组合的先验概率极低。

在第 14 章中探讨的覆盖率导向模糊测试（Coverage-guided Fuzzing，以 libFuzzer 为代表），彻底颠覆了输入生成逻辑：引擎在插桩反馈的指引下，根据代码基本块的命中情况自主学习输入变异策略，专门朝能够探索新控制流分支的方向倾斜算力。

差分测试可以极为自然地接入模糊测试目标（Fuzz Target）。我们将模糊引擎生成的原始字节流切分为前后两段，分别作为主串与子串，向基准实现与被测实现同时发起调用并校验返回偏移：

c
int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
    size_t haylen;
    size_t neelen;
    const void *got;
    const void *want;
    long got_off;
    long want_off;

    if (size < 2) {
        return 0;
    }
    haylen = size / 2;
    neelen = size - haylen;
    got = mdr_memmem(data, haylen, data + haylen, neelen);
    want = ref_memmem(data, haylen, data + haylen, neelen);
    got_off = got == NULL ? -1 : (long)((const uint8_t *)got - data);
    want_off = want == NULL ? -1 : (long)((const uint8_t *)want - data);
    if (got_off != want_off) {
        fprintf(stderr, "memmem mismatch: hay %zu bytes, needle %zu bytes, "
                        "want offset %ld, got %ld\n",
                haylen, neelen, want_off, got_off);
        abort();
    }
    return 0;
}

参考实现 ref_memmem 采用最朴素的滑动窗口与 memcmp 逐位置核对，逻辑简洁纯粹。由于两个实现检索的指针均派生自同一个只读内存对象 data，两者的命中位置可以直接通过指针算术相减求得偏移，无需借助额外的转换层。

在 Windows 环境下，我们可以直接使用 Visual Studio 自带的 Clang 工具链（如 Clang 22，其随附完整的 libFuzzer 与 ASan 运行时）。将相关动态库路径纳入环境后执行编译：

zsh - clang
text
$ export PATH="/d/Software/VS/1/VC/Tools/Llvm/x64/lib/clang/22/lib/windows:$PATH"
$ clang -std=c17 -g -O1 -fsanitize=fuzzer,address -Iinclude -o fuzz_memmem.exe \
      fuzz/fuzz_memmem.c src/mdr_string.c src/mdr_memory.c src/mdr_ext.c src/mdr_bits.c

在 PowerShell 终端下，编译选项建议包裹为 "-fsanitize=fuzzer,address" 字符串形式，避免逗号被外层命令行环境误判为参数间隔。

首先对未改动的正确实现施加 10 秒的高频模糊轰炸：

PowerShell - fuzz_memmem
text
PS> .\fuzz_memmem.exe -max_total_time=10
INFO: Running with entropic power schedule (0xFF, 100).
INFO: Seed: 2089663712
INFO: Loaded 1 modules   (371 inline 8-bit counters): 371 [00007FF692156A88, 00007FF692156BFB),
INFO: -max_len is not provided; libFuzzer will not generate inputs larger than 4096 bytes
INFO: A corpus is not provided, starting from an empty corpus
#2      INITED cov: 2 ft: 2 corp: 1/1b exec/s: 0 rss: 35Mb
Done 5051015 runs in 11 second(s)

在 11 秒内平稳完成了 505 万次变异执行，双轨未出现任何分歧。紧接着我们向 mdr_memmem 中注入一个仅在子串紧贴主串尾部时才触发的特异缺陷：当 mdr_memcmp 匹配成功、子串长度不小于 3 且 remaining == needlelen 时，逻辑错误地跳过返回语句：

PowerShell - fuzz_memmem -seed=1
text
PS> .\fuzz_memmem.exe -seed=1 -max_total_time=30 -artifact_prefix=fz/
INFO: Running with entropic power schedule (0xFF, 100).
INFO: Seed: 1
...
#27     NEW    cov: 30 ft: 30 corp: 5/12b lim: 4 exec/s: 0 rss: 62Mb L: 3/4 MS: 2 InsertByte-CrossOver-
#45     NEW    cov: 34 ft: 34 corp: 6/16b lim: 4 exec/s: 0 rss: 62Mb L: 4/4 MS: 3 CopyPart-ChangeBit-InsertByte-
#270    NEW    cov: 34 ft: 35 corp: 7/22b lim: 6 exec/s: 0 rss: 62Mb L: 6/6 MS: 5 ChangeBinInt-CopyPart-CrossOver-CopyPart-InsertRepeatedBytes-
memmem mismatch: hay 3 bytes, needle 3 bytes, want offset 0, got -1
artifact_prefix='fz/'; Test unit written to fz/crash-d58e696f63c81a98962dbf6dc92d0cc5e838b7a2
Base64: Hx8fHx8f

测试仅迭代到第 270 次，分歧断言便被触发。该缺陷要求子串长度恰好与主串相等且内容精确匹配，若采用盲目随机输入很难精准达成这种边界约束；而在覆盖率变异驱动下，引擎迅速捕捉到该控制流转折点。崩溃文件落地为 6 字节的 1f 1f 1f 1f 1f 1f，前半段与后半段各 3 字节，正确实现返回偏移 0，而缺陷版本返回了 -1。

将该崩溃样本作为输入直接传给目标程序，即可实现秒级单步回放：

text
PS> .\fuzz_memmem.exe fz/crash-d58e696f63c81a98962dbf6dc92d0cc5e838b7a2
memmem mismatch: hay 3 bytes, needle 3 bytes, want offset 0, got -1

在工程协同中，将该崩溃样本直接收录进代码仓库的回归语料库，并在持续集成中配置重放目标（Replay Target，可参阅第 14 章），即可筑牢永久防线。指定固定种子 -seed=1 则保证了整个探索与复现链路在工程记录中的严谨自洽。

9. 构建系统集成与持续回归流水线 ​

五个专门的差分测试源文件通过 file(GLOB ...) 自动纳管至 CMake 构建体系中。为了实现细粒度测试调度，我们在构建脚本中为其标注专有的测试标签：

cmake
file(GLOB MDR_DIFF_TESTS CONFIGURE_DEPENDS "${CMAKE_CURRENT_SOURCE_DIR}/tests/diff_*.c")
set(MDR_DIFF_SUPPORT "${CMAKE_CURRENT_SOURCE_DIR}/tests/diff_util.c")
if(EXISTS "${MDR_DIFF_SUPPORT}")
    list(REMOVE_ITEM MDR_DIFF_TESTS "${MDR_DIFF_SUPPORT}")
    foreach(diff_src IN LISTS MDR_DIFF_TESTS)
        get_filename_component(diff_name "${diff_src}" NAME_WE)
        add_executable(${diff_name}
            "${diff_src}"
            "${CMAKE_CURRENT_SOURCE_DIR}/tests/check.c"
            "${MDR_DIFF_SUPPORT}"
        )
        target_include_directories(${diff_name} PRIVATE "${CMAKE_CURRENT_SOURCE_DIR}/tests")
        target_link_libraries(${diff_name} PRIVATE mdr)
        add_test(NAME ${diff_name} COMMAND ${diff_name})
        set_tests_properties(${diff_name} PROPERTIES LABELS diff)
    endforeach()
endif()

通过配置属性 LABELS diff，开发者可以使用 ctest -L diff 精确筛选差分测试套件执行（关于 CTest 标签过滤的高级用法可参阅第 11 章），从而将基础单元测试与高密度的差分测试剥离开来。在 Linux 环境下验证执行：

zsh - ctest -L diff
text
$ ctest --test-dir build -L diff
Test project /home/minsecrus/tutorial/work/p070/21_库接口实现练习/build
    Start  9: diff_bits
1/5 Test  #9: diff_bits ........................   Passed    0.02 sec
    Start 10: diff_ext
2/5 Test #10: diff_ext .........................   Passed    0.00 sec
    Start 11: diff_memmove
3/5 Test #11: diff_memmove .....................   Passed    0.00 sec
    Start 12: diff_memory
4/5 Test #12: diff_memory ......................   Passed    0.00 sec
    Start 13: diff_string
5/5 Test #13: diff_string ......................   Passed    0.00 sec

100% tests passed, 0 tests failed out of 5

Label Time Summary:
diff    =   0.02 sec*proc (5 tests)

五套差分套件合计仅耗时 0.02 秒。即使包含了近 20 万次位操作比对，总耗时依然处于轻量量级。这种极高的执行效率使得差分套件能够毫无阻碍地挂载在每一次本地常规编译的后置钩子中，无需推迟至提交前夜才做大体量排查。

除了默认编译，同一套差分验证体系还应在另外两套变体目标下轮番巡检：

  1. Sanitizer 插桩构建（-DMDR_SANITIZE=ON）：开启 ASan 与 UBSan 运行时防护。由于差分测试密集遍历了各类边界切片与偏移行程，动态插桩能够顺带排查整个比对过程中是否踩踏未定义行为或内存溢出；
  2. 纯 C 回退构建（-DMDR_NO_BUILTINS=ON）：主动关闭底层一切编译器硬件扩展，强制整个工程回退至纯标准 C 算法，验证回退路径与系统参考实现是否严格自洽。
text
$ cmake -S . -B build-asan -DMDR_SANITIZE=ON
$ cmake --build build-asan -j2
$ ctest --test-dir build-asan -L diff
...
100% tests passed, 0 tests failed out of 5

若宿主 MinGW 工具链未随附 ASan 运行库，相关动态插桩构建可移步至 WSL、Linux 容器或 macOS 环境下执行；而标准构建与纯 C 回退构建在 Windows 原生命令行下均能无缝通过。

将该双轨甚至多轨差分体系接入持续集成（CI）矩阵，是现代系统软件工程的一项核心实践（关于跨平台构建矩阵的流水线配置可参阅第 18 章）。在云端矩阵中，各操作系统节点天然配备了不同的基准实现：Ubuntu 节点由 GNU glibc 坐镇，Windows 节点以微软 UCRT 为准绳，而 macOS 节点则由 Apple Libc 提供参照。

将同一个确定性种子分发至三大操作系统，若某套底层标准库针对极端边界（如高位有符号扩展或零长切片）的裁决存在未预料的方言漂移，CI 矩阵的差分红灯就会在第一时间发出预警。这种跨生态的参照互验，正是差分测试带给大型 C 语言工程最坚实的质量护城河。

五套差分测试套件的职责分工全景
  • diff_string：在受控字母表内穷举主串与子串的所有紧凑组合，针对 strchr、strrchr、strspn、strcspn、strpbrk、strstr 与标准库逐一比对，并追加 256 种非零单字节扫描，累计执行 12510 次断言；
  • diff_memory：由跨平台伪随机发生器驱动变长数据流，针对 memcmp 在高位字节下的符号映射执行 1000 轮差分校验；
  • diff_memmove：在 16 字节缓冲区上穷举目标偏移、源偏移与传输长度的全部合法排列，全量镜像校验重叠拷贝算法，累计执行 1751 次断言；
  • diff_bits：针对 0x0000 至 0xFFFF 的全部 16 位整数，对照朴素慢版本核验 clz、ctz、popcount 的数学等价性，累计执行 196608 次断言；
  • diff_ext：针对 strlcpy 与 strlcat 的缓冲区越界写实施精准防护字节（Canary）拦截，在紧凑分配边界下执行 14 次严格核验。

10. 习题 ​

10.1 巩固 ​

#22171
⚡2⏳2

正文开头那个 mdr_strspn：手写 12 个检查全过，差分扫 255 个单字节输入出 128 处不一致。把这段故事完整复现一遍。

(1) 抄下那个只有 128 项查找表的 mdr_strspn，手写 12 个 expect 调用（空串、集合为空、全部命中、前缀命中、一个都不命中，ASCII 范围内的常见情形），确认 12 个全过。

(2) 写一个循环，c 从 1 到 255，构造两字节的 text，比较 mdr_strspn(text, text) 与 strspn(text, text)，打印前三个不一致的字节和总数。期望看到 0x80、0x81、0x82 与总数 128。

(3) 同一个缺陷版，把 accept 换成 "x" 再扫一遍，不一致个数是多少？换成 "abc" 呢？用这两个数字解释为什么 tests/diff_string.c 里那 12510 次比较一次也没抓到它。

#22172
⚡3⏳2

strcmp 的返回值只规定符号。下面的程序把「原始返回值相等」当成一致，会在两台机器上得到不同结论：

c
#include "mdr_string.h"
#include <stdio.h>
#include <string.h>

int main(void) {
    printf("sys=%d mdr=%d\n", strcmp("apple", "apricot"),
           mdr_strcmp("apple", "apricot"));
    printf("sys=%d mdr=%d\n", strcmp("A", "z"), mdr_strcmp("A", "z"));
    return 0;
}

(1) 在本机与任一 glibc 环境上各运行一次，记录两行。两台的 sys 值相同吗？mdr 值呢？

(2) 写一个 static int sign(int)，把两列都规范化成 -1、0、1 再比较。改成符号比较后，两台机器上的结论是否一致？

(3) 把 strcmp("apple", "apricot") 改成从 argv 取实参，在同样的两台机器上再跑一次。若两台机器上常量版与运行期版都各自一致，说明本机的 strcmp 本来就不返回字节差；换到 glibc 上，常量版为什么可能给出与运行期版不同的数？这和第 2 节「实参必须从 argv 来」说的是同一件事吗？

(4) 列出第 2 节表里四类需要规范化的差异，各给出本页或前几节里一个具体例子。

#22173
⚡3⏳2

mdr_bit_ceil_u32 的规格是「不小于 x 的最小 2 的幂，放不下时返回 0」。下面这一版把判断条件写错了：

c
static uint32_t buggy_bit_ceil_u32(uint32_t x) {
    if (x <= 1) {
        return 1;
    }
    if (x >= 0x80000000u) {
        return 0;                 /* 正确版本是 x > 0x80000000u */
    }
    return 1u << (32 - mdr_clz_u32(x - 1));
}

(1) 写一个从 1 往上乘 2 的慢版本作参照，对 0 到 0xFFFF 的每个输入比较，记录不一致个数。

(2) 单独测 0x80000000，缺陷版给出什么？正确版本给出什么？

(3) 这说明「穷举到 0xFFFF」的覆盖边界在哪里。把参照换成按位扫描的写法后，哪些输入必须单列在边界值表里？按第 4 节的表格式写出 mdr_bit_ceil_u32 那一行。

(4) 如果只跑穷举不跑边界值，这个缺陷会在什么情况下才被发现？给出一个具体的场景。

10.2 编程 ​

#22174
⚡4⏳3

用防护字节抓住「多写一个字节」。

(1) 按 4.1 节的 diff_guard 接口实现 diff_guard_init、diff_guard_check、diff_guard_free：数据区前后各 16 个 0xA5，diff_guard_check 报告第一个被改写的哨字节的位置与内容。

(2) 注入下面这个缺陷，对 dst0 取 ""、"h"、"hello"、"world"、"a longer string"、src 取 "hello" 各调用一次（dsize = strlen(dst0) + 1）：

c
static size_t buggy_strlcpy(char *dst, const char *src, size_t dsize) {
    size_t len = strlen(src);

    if (dsize > 0) {
        size_t copy = len < dsize - 1 ? len : dsize - 1;

        memcpy(dst, src, copy);
        dst[copy] = '\0';
        dst[copy + 1] = '\0';
    }
    return len;
}

期望看到四次 GUARD strlcpy: data[N] is 00, expected A5，N 分别是 1、2、6、6。

(3) 把 dst0 取 "h" 那一组的 dsize 从 2 改成 3（即多留一个字节余量），缺陷依旧存在，检查为什么通过了。

(4) 一句话说明为什么防护字节查不出越界读。

#22175
⚡4⏳3

strncpy 会在源串比 count 短时把剩余位置补零，这个「补零」是规格的一部分，只比较字符串内容看不出来。

(1) 写一个只写到终止空字符、不补零的 nopad_strncpy，对源串取 ""、"a"、"ab"、"abc"、"abcd"、"abcde"，count 取 0 到 8，共 54 组。数据区先整体填 0xAA，调用后比较整块 8 字节，记录失败组数。

(2) 对每一组失败，再用 strcmp 比一次。54 组里有 27 组整块不同，strcmp 能报出其中几组？一个都没报出的话，说明 strcmp 只看得到什么、看不到什么。

(3) 用第 2 节表里「复制函数的目标缓冲区」那一行解释：为什么差分测试必须比较整块缓冲区，而不是比较到终止空字符为止。

(4) 把 count 取 8、src 取 "ab" 的那一组，打印两边的 8 个字节，指出从第几个字节开始不同。

#22176
⚡4⏳3

正文第 9 节把五个差分测试接进了构建。

(1) 按正文的 CMake 片段加上 LABELS diff，构建后运行 ctest --test-dir build -L diff。记录测试个数与总耗时。

(2) 新增一个空的 tests/diff_foo.c（只 return 0;），不改 CMakeLists.txt，重新运行 cmake --build。新目标会被自动发现吗？靠的是哪一行配置？

(3) 把 diff_ext 从 LABELS diff 的集合里排除（例如临时改名成 diffx_ext.c），ctest -L diff 的个数变成多少？ctest --test-dir build 的总数又变成多少？

(4) 说明在 CI 里为什么要跑三种构建：默认、-DMDR_SANITIZE=ON、-DMDR_NO_BUILTINS=ON。每种各能抓到哪一类问题。

#22177
⚡4⏳3

diff_memmove 用 16 字节缓冲区穷举出 1751 组。把同样的思路缩到 8 字节缓冲区。

(1) 写出三重循环（目标偏移、源偏移、字节数各取 0 到 7，两个区域都必须落在缓冲区内），先算出有多少组合法组合，再让程序自己数一遍核对。

(2) 把 mdr_memmove 换成一个只会从低地址往高地址复制的版本，重新运行，记录失败组数，并打印第一组失败的 dest、src、count。

(3) 用这组最小的失败输入解释：为什么 dest < src 时从低往高复制是对的，而 dest = 1、src = 0 时就不对。

(4) 16 字节的版本得到 1751 组，8 字节的得到多少组？这个数字随缓冲区长度增长得多快？这说明了小范围穷举的代价与覆盖面的关系。

#22178
⚡5⏳3

正文第 6 节说 rand() 不能用于可复现的随机测试。用 splitmix64 替换它。

(1) 抄下 diff_random，写一个程序从命令行读种子与个数，逐行打印。验证种子 1 的前五个值是 910a2dec89025cc1、beeb8da1658eec67、f893a2eefb32555e、71c18690ee42c90b、71bb54d8d101b5b9，种子 0x1234 的前五个值是 5f642f87d5e23888、5a4d78533d034cb5、8a85ffdaea35a5a6、ad002edb4259d53a、807b1f5869c624bc。在第二台机器上重复，确认逐行相同。

(2) 用同一个种子跑 srand(1); rand() 的前五个值，在 Windows 与 Linux 上各记一行。两台机器的数列为什么毫无关联？

(3) 给 mdr_memcmp 的差分测试加上 --seed、--rounds 参数，种子每次都打印出来。把 mdr_memcmp 里的 unsigned char 换成 char，用 --seed 0x1234 --rounds 5 跑一遍，记录 MISMATCH 行里的 expected、got 和失败计数。

(4) 按分裂后的输入逐字节核对，指出第一处不同的下标、翻转前后的字节值，以及为什么按 char 比较会把大小关系弄反。

#22179
⚡5⏳4

正文第 7 节的缩小器把 64 字节的失败输入缩到 1 字节。

(1) 抄下 diff_shrink 与判定函数，对一段 64 字节、每个字节都带最高位的数据（例如 0x80 | i）跑一遍，记录缩小后的长度与内容。

(2) 用计数器统计 fails 被调用了几次，换算成平均每个字节做几次尝试。

(3) 把 mdr_memcmp 换回正确的 unsigned char 版本，判定函数不变，再对同一段 64 字节输入跑一次缩小器。输出是什么？从 fails 在长度 0 时的返回值说起，解释缩小器为什么一个字节也没改。

(4) 说明「fails 的判定必须与最初发现失败时完全一致」这条要求。若判定函数漏掉了输入长度这个维度，缩小器可能产出什么？

10.3 综合与挑战 ​

#22180
⚡6⏳5选做

给 mdr_memmem 写一套完整的差分测试，覆盖穷举、边界值、随机与防护，并证明这套测试能抓住「只在 needle 贴着 haystack 末尾时出错」的缺陷。

(1) 参照实现用逐位置 memcmp 的写法，短到可以逐条件核对。用一个 long 表示命中偏移（NULL 记 -1），与 mdr_memmem 的返回值比较。

(2) 穷举：字母表 {'a','b'}，haystack 长度 0 到 4，needle 长度 0 到 2，共 217 组；再扫 256 个单字节 haystack。记录比较次数，并确认在正确实现上全部通过。

(3) 注入缺陷：命中时若 needlelen >= 3 且 remaining == needlelen 则不返回。用 (2) 的穷举跑一遍，记录失败数；再补一条边界用例 haystack = "abc"、needle = "abc"，记录两个实现的偏移。

(4) 用随机输入补位：长度与内容由 splitmix64 决定，needle 为 haystack 的随机子串、随机扰动或随机字节各占三分之一，跑 --seed 1 --rounds 2000。这个缺陷能被随机输入碰到吗？给出你实测的失败率或说明为什么碰不到。

(5) 把这个目标做成 LLVMFuzzerTestOneInput，同一条输入切成两半当 haystack 与 needle。用 clang -fsanitize=fuzzer,address 跑 -seed=1 -max_total_time=30，记录崩溃出现的执行编号、崩溃文件的十六进制内容，以及把它当参数传给目标程序时的重放输出。

(6) 最后写一段总结：对这一个缺陷，五种手段（穷举、边界值、随机、模糊、缩小）分别是否有效，为什么。这正对应第 3 节末尾说的「穷举到 needle 长度为 2 还不够」。

没有 libFuzzer 环境时第 (5) 问可以跳过，但要在报告里注明；其余各问都能用 gcc 完成。

11. 参考资料 ​