如何精准捕获代码缺陷：基于 Rust 正则引擎的高效模糊测试实战

Finding Bugs

文章背景与核心概要

在复杂系统与底层基础库的开发中，传统的单元测试往往只能覆盖开发者预想到的常规路径，极易漏掉隐蔽的边界状态与特征交互缺陷。本文源自知名技术讨论社区 Lobste.rs 上关于“测试有效性”的探讨，作者以 Rust 生态核心的 regex 正则引擎历史真实 Bug 为例，展示了如何脱离臃肿庞杂的外部测试框架，仅凭一个轻量级的伪随机数生成器 (PRNG) 与群集测试 (Swarm Testing) 策略，高效生成极短却极具杀伤力的边缘用例。通过将待测引擎与标准实现 (Oracle) 交叉比对，这种轻巧敏捷的方法不仅执行速度极快，还能在极短时间内精准揪出传统测试难以触及的深层逻辑漏洞。这种实战经验表明，高质效的测试并不依赖海量算力与庞大测试数据，而是取决于精巧的测试架构设计与特征组合策略。

发布日期： 2026 年 9 月 19 日
原文出处： Lobste.rs 讨论区

Published on: Sep 19, 2026

Source: Lobste.rs Discussion

📌 核心概述

📌 Summary

本文通过为 Rust 语言的核心正则库 regex 量身打造一个轻量级模糊测试器 (Fuzzer) ，深入探讨了生成式随机测试 (Generative Testing) 相比于传统单元测试的强大优势。作者并未依赖笨重庞大的测试框架，而是展示了如何仅凭一个极简的伪随机数生成器 (PRNG) ，搭配权威比对基准 (Oracle) ——直接将 regex 与轻量版 regex_lite 的运行结果进行交叉比对——就能精准揪出那些隐藏极深的代码缺陷。

This article explores the effectiveness of generative (randomized) testing compared to traditional unit tests by building a custom fuzzer for the Rust regex crate. Rather than relying on complex frameworks, the author demonstrates how a lightweight, pseudo-random number generator (PRNG) coupled with an oracle (comparing regex against regex_lite) can successfully uncover hidden bugs.

文中所阐述的核心原则包括：采用 群集测试 (Swarm Testing) 策略 (随机分配特性分布与字符集) 、专注于挖掘 短小而刁钻的边界极端用例 而非盲目堆砌海量数据负载，以及将漏掉的 Bug 视作测试框架本身的设计不足并不断反哺完善。

Key principles covered include swarm testing (randomizing feature distributions and alphabets), targeting small and tricky edge cases rather than massive payloads, and treating missed bugs as failures in the testing harness itself.

缺陷溯源：一个真实的正则表达式 Bug

The Bug

对于正则表达式 ".abb|b" 和输入字符串 "zabb"，旧版本的 regex crate 出现了一个离奇的错误：它返回的第一个匹配项居然是 "b"，而不是理应匹配的完整字符串 "zabb"：

For the ".abb|b" regex and "zabb" input, an older version of the regex crate incorrectly returned b as the first match instead of the entire zabb string:

use regex;

fn main() {
    let r = regex::Regex::new(".abb|b").unwrap();

    let m = r.find("zabb").unwrap();

    // Fails with regex-automata=0.4.15:
    assert_eq!(m.as_str(), "zabb")
}

我们该如何主动发现这类诡异的缺陷呢？正则表达式引擎属于纯粹的算法实现，这使它们成为了应用生成式测试的绝佳温床。而在算法测试领域，最强大、最直接的手段莫过于将待测系统的输出与已知正确的权威答案 (即测试预言机 Oracle) 进行比对。虽然原始评论中提到其测试工具当时缺乏可用的 Oracle，但在构建稳健系统时，我们在架构设计之初就应当把 Oracle 纳入考量。幸运的是，在针对 regex 库的案例中，我们完全可以直接拉来 regex_lite 库作为权威参考，将两者的输出进行全自动交叉验证。

How do we find bugs like this? Regular expression engines are pure algorithms, making them prime candidates for generative testing. The most powerful technique for testing algorithms is to compare them against a known correct answer (an oracle). While the original comment noted their fuzzer lacked an oracle, robust systems should be designed with oracles in mind. Fortunately, for our regex case study, we can simply cross-check outputs against the regex_lite crate.

生成测试字符串

Generating a String

我们可以借助一个极简的伪随机数生成器 (PRNG) ，搭建一个纯粹的随机字符串生成工具：

We can build a simple random string generator using a pseudo-random number generator:

use fastrand::Rng;

在进行随机化测试时，人们往往有一种下意识的直觉：疯狂生成海量的数据载荷 (例如动辄 5 GiB 的超大输入) 。然而在现实中，软件缺陷通常孕育自各种特性之间微妙而精细的小规模交互，而非单纯因为数据量巨大。

When performing randomized testing, the instinct is often to generate massive payloads (e.g., 5 GiBs of input). However, bugs usually stem from small, intricate interactions between features.

我们的生成策略遵循两步走方案：

Our strategy follows a two-step approach:

确立基准字符集：从现有的单元测试中提取并固定基础字符表；
动态子集抽样：在每一次迭代中，随机挑选该字符表的一个子集 (即群集测试 Swarm Testing 的精髓) ，随后仅使用这些被挑中的字符生成随机长度的测试字符串。

Fix a base alphabet derived from unit tests.

For each iteration, pick a random subset of that alphabet (swarm testing), then generate a string of random length using only those characters.

为了把运行性能压榨到极致，我们在各轮迭代之间通过预分配策略循环复用内存缓冲区，彻底避免频繁的动态内存申请：

To maximize performance, we reuse memory across iterations via static allocation:

use fastrand::Rng;

fn main() {
    let mut rng = Rng::new();

    // Re-use the same memory for all tests.
    let mut text_alphabet: Vec<u8> = vec![];
    let mut text: Vec<u8> = vec![];

    for _ in 0..1_000_000 {
        // It's unlikely that a counter example with
        // 7 different letters exists, while there
        // isn't one with just 6.
        alphabet_swarm(&mut rng, b"abcdef", &mut text_alphabet);
        let text =
            gen_string(&mut rng, &text_alphabet, &mut text);
    }
}

fn alphabet_swarm<'a>(
    rng: &mut Rng,
    all: &[u8],
    pick: &'a mut Vec<u8>,
) {
    pick.clear();
    pick.extend(all);
    rng.shuffle(pick);
    let count = rng.usize(1..=pick.len());
    pick.truncate(count);
}

fn gen_string<'a>(
    rng: &mut Rng,
    alphabet: &[u8],
    result: &'a mut Vec<u8>,
) -> &'a str {
    result.clear();
    // Again, this is a short string.
    // Longer failures are not likely.
    let count = rng.usize(0..8);
    for _ in 0..count {
        result.push(alphabet[rng.usize(0..alphabet.len())]);
    }
    str::from_utf8(result).unwrap()
}

设定正则语法特性的分布权重

Generating a Regex Distribution

在生成正则表达式时，我们同样贯彻这种群集测试思路：

We apply the same swarm-testing strategy to generate regular expressions:

随机激活正则语法语义特性的某一个子集；
随机决定生成表达式的长度规模；
全程复用内存缓冲区。

Pick a subset of active regex features.

Pick sizes at random.

Re-use memory buffers.

首先，我们为不同的正则表达式语法特性定义离散权重，而不是非开即关的布尔开关：

First, we define weights for different regex features rather than using binary toggles:

#[derive(Default, Debug)]
struct ReOptions {
    alt: u16, // |
    rep: u16, // *
    any: u16, // .
    lit: u16, // 'a'
    sum: u16,
    alphabet: Vec<u8>,
}

接下来，我们实现群集抽样逻辑，在运行期间动态随机配置各项语法特性的权重与字符集：

Next, we implement the swarm logic to dynamically configure weights and alphabets:

impl ReOptions {
    fn swarm(&mut self, rng: &mut Rng, alphabet_full: &[u8]) {
        // We _still_ want to enable a few features at a time.
        self.alt = if rng.bool() { 0 } else { rng.u16(0..100) };
        self.rep = if rng.bool() { 0 } else { rng.u16(0..100) };
        self.any = if rng.bool() { 0 } else { rng.u16(0..100) };
        self.lit = rng.u16(1..100);
        self.sum = self.alt + self.rep + self.any + self.lit;
        assert!(self.sum > 0);
        alphabet_swarm(rng, alphabet_full, &mut self.alphabet);
    }
}

递归生成正则表达式

Generating a Regex

我们采用递归方式构造复杂的正则表达式语法树，通过向下传递输出缓冲区以及一个控制表达式规模的 size 参数来精确约束生成深度：

We construct regular expressions recursively, passing down output buffers and a size parameter to control expression length:

fn gen_re(
    rng: &mut Rng,
    options: &ReOptions,
    result: &mut Vec<u8>,
) {
    result.clear();
    let size = rng.u8(0..8);
    gen_re_rec(rng, options, result, size);
}

fn gen_re_rec(
    rng: &mut Rng,
    options: &ReOptions,
    result: &mut Vec<u8>,
    size: u8,
) {
    if size == 0 {
        return; // Base case, empty regex.
    }

    // Pick one of the features, according to weights.
    let mut p = rng.u16(0..options.sum);
    if p < options.alt {
        // Alternation distributes the size
        // among the two children.
        let size_left = rng.u8(0..=size - 1);
        let size_right = size - size_left - 1;
        assert!(size == size_left + 1 + size_right);

        result.push(b'(');
        gen_re_rec(rng, options, result, size_left);
        result.extend(b")|(");
        gen_re_rec(rng, options, result, size_right);
        result.push(b')');
        return;
    }
    p -= options.alt;

    if p < options.rep {
        result.push(b'(');
        gen_re_rec(rng, options, result, size - 1);
        result.extend(b")*");
        return;
    }
    p -= options.rep;

    if p < options.any {
        gen_re_rec(rng, options, result, size - 1);
        result.push(b'.');
        return;
    }
    p -= options.any;

    if p < options.lit {
        gen_re_rec(rng, options, result, size - 1);
        let index = rng.usize(0..options.alphabet.len());
        let lit = options.alphabet[index];
        result.push(lit);
        return;
    }
    unreachable!();
}

缺陷搜索主循环

Search Loop

考虑到编译正则表达式本身涉及状态机构建，属于计算密集型操作，我们可以将每次编译出的一对正则对象保留下来，复用于数千个随机输入字符串的匹配验证：

Because compiling regular expressions is computationally expensive, we can test multiple input strings against a single compiled regex pair:

fn main() {
    let mut rng = Rng::new();

    let mut options = ReOptions::default();
    let mut text_alphabet: Vec<u8> = vec![];
    let mut text: Vec<u8> = vec![];
    let mut re: Vec<u8> = vec![];

    let mut test_count: u32 = 0;
    for _ in 0..1_000_000 {
        options.swarm(&mut rng, b"abcdef");
        alphabet_swarm(&mut rng, b"abcdefx", &mut text_alphabet);

        gen_re(&mut rng, &options, &mut re);

        let re = str::from_utf8(&re).unwrap();
        let r1 = regex::Regex::new(re).unwrap();
        let r2 = regex_lite::Regex::new(re).unwrap();

        for _ in 0..1000 {
            test_count += 1;
            let text =
                gen_string(&mut rng, &text_alphabet, &mut text);

            let m1 = r1.find(text)
                .map_or("not found", |it| it.as_str());
            let m2 = r2.find(text)
                .map_or("not found", |it| it.as_str());

            if m1 != m2 {
                eprintln!("err re={re} text={text} m1={m1} m2={m2}");
                return;
            }

            if test_count % 500_000 == 0 {
                eprintln!("ok  re={re} text={text}");
            }
        }
    }
}

完整实现代码

Complete Implementation

想要获取完整且统一的测试脚本，可以直接查阅下方链接中的开源仓库，或者直接将上文各章节的代码片段拼装整合：

For the complete, unified script, see the repository linked below or use the implementation assembled from the sections above:

GitHub 仓库：regex-fuzz

GitHub Repository: regex-fuzz

核心启示与工程反思

Key Takeaways

比对基准 (Oracle) 威力无穷：将测试结果与已知正确的标准实现进行模糊比对极为高效——因此在系统设计之初就融入 Oracle 机制是绝对物超所值的。
用例贵在短小精悍：将测试重心聚焦于简短但交互复杂的刁钻边缘用例，远比生成庞大而均匀的冗长输入更能击中要害。
极简主义大巧不工：尽管高级模糊测试工具功能惊艳，但只要策略得当，即便是最朴素的伪随机数生成器 (PRNG) 也能发挥出令人震撼的测试威力。
系统与测试协同演进：将测试脚手架 (乃至比对基准 Oracle) 直接融入系统架构设计中，能为软件质量带来巨大的工程杠杆效应。
平民化的高质效工程：运用这些测试方法论并不需要高深莫测的学术背景或高昂的算力门槛，普通工程师同样能轻松落地并从中受益匪浅。

Oracles are powerful: Fuzzing against a known-good oracle is exceptionally effective—making it worth the effort to build oracles into your systems.

Keep examples small: Target small, tricky edge cases rather than large, uniform inputs.

Simplicity works: While advanced fuzzers are fantastic, even a humble PRNG can be brutally effective when applied correctly.

Co-design systems and tests: Building testing harnesses (and oracles) directly into your system design yields massive leverage.

Accessible engineering: You don't need an advanced academic background to implement and benefit from these testing methodologies.