使用TTT算法学习正则语言

# 使用TTT算法学习正则语言 来源：http://rahul.gopinath.org/post/2026/06/09/ttt-grammar-inference/ **TLDR；** 本教程完整实现了用于主动自动机学习的TTT算法（Python版）。TTT结合了Kearns和Vazirani的判别树与Rivest和Schapire的二分搜索反例分析，并加入了前缀变换和判别器终结化，以消除所有冗余的成员查询。Python解释器已嵌入，因此您可以逐步完成实现。 ## 为什么要学习输入语言？ 假设你拿到一个软件，例如网络协议实现、解析器或安全过滤器。你想了解它接受哪些输入。你无法访问源代码，只能运行它并观察它对给定输入接受还是拒绝。这是黑盒场景。 一个天真的做法是穷举测试。但即使简单文法接受的所有字符串集合也是无限的。更好的方法是推断一个有限模型，即DFA，精确捕获输入行为。这样的模型本身就很有用：你可以检查它、验证属性、从中生成测试，或与规范对比以发现差异。 主动自动机学习就是用尽可能少的查询高效构造这种模型的学科。 在我之前的文章（http://rahul.gopinath.org/post/2024/01/04/lstar-learning-regular-languages/）中，我实现了Angluin的L*算法，用于从黑盒预言机学习正则语言。L*使用扁平观察表来跟踪状态区分，这导致冗余的成员查询：当反例到达时，其所有后缀都被添加为列，尽管大多数并未区分任何新状态。 TTT是正则语言推断的最先进算法。使用该算法，你可以推断任何黑盒程序输入语言（直至其正则近似）。它比L*快得多，且其生成的成员查询数量（即需要测试黑盒的输入数）被证明是无冗余的。 TTT算法融合了多项独立贡献： - Rivest和Schapire[1]（http://rahul.gopinath.org/post/2026/06/09/ttt-grammar-inference/#fn:rivest1993）贡献了二分搜索反例分析，能在O(log k)次查询（而非k次）中找到反例中的单个相关后缀。 - Kearns和Vazirani[2]（http://rahul.gopinath.org/post/2026/06/09/ttt-grammar-inference/#fn:kearns1994）引入判别树替代观察表。 - Isberner、Howar和Steffen[3]（http://rahul.gopinath.org/post/2026/06/09/ttt-grammar-inference/#fn:isberner2014）在此基础上增加了两个改进：**前缀变换**（保持访问序列最短）和**判别器终结化**（保持判别树浅）。TTT被证明是无冗余的——它从不执行其答案能从先前查询推导出的成员查询。 语言推断也可应用于硬件。然而，此类场景有其他考虑因素，例如重启系统可能不可行甚至代价高昂。ADT[4]（http://rahul.gopinath.org/post/2026/06/09/ttt-grammar-inference/#fn:adt）是TTT的一个显著扩展，它使用自适应区分序列，能在硬件场景中减少重置。 ## 定义 - **字母表** \\(A\\)：DFA读取的输入符号集合。 - **成员查询**：传递给黑盒预言机的字符串。预言机回答“是”（接受）或“否”（拒绝）。 - **等价查询**：传递给教师的假设文法。教师回答“是”，或返回一个反例字符串（假设与目标不一致）。 - **PAC预言机**：等价预言机的概率近似。在随机测试N次未发现反例后，我们宣布假设“可能近似正确”。 - **判别树（DT）**：一棵二叉树，内部节点是判别器后缀，叶子是状态。将字符串\\(w\\)在树中筛选，每层使用一次成员查询将其分类到某个状态。 - **访问序列** \\(reach(q)\\)：已知到达目标中状态\\(q\\)的最短字符串。在TTT文献中称为\\(acc(q)\\)，但用\\(reach(q)\\)以避免与DFA中\\(accept\\)混淆。 - **生成树**：从每个已知状态到其访问序列的映射。本实现使用字典（称为状态表）而非树。 - **开放转移**：从状态\\(q\\)经符号\\(a\\)的转移，尚未被筛选以确定目标状态。 - **反例分解**：在反例中寻找分割点、提取新判别器并分裂DT中叶子的过程。 ## 目录 1. [定义](#定义) 2. [前置条件](#前置条件) 3. [从L*到TTT](#从l到ttt) 4. [DFA表示](#dfa表示) 5. [预言机](#预言机) 6. [判别树](#判别树) 7. [状态表](#状态表) 1. [筛选](#筛选) 8. [假设构造](#假设构造) 1. [增量假设更新](#增量假设更新) 9. [反例分解](#反例分解) 1. [分割点](#分割点) 2. [前缀变换](#前缀变换) 3. [分裂叶子](#分裂叶子) 4. [判别器终结化](#判别器终结化) 5. [寻找分割点](#寻找分割点) 6. [整合分解](#整合分解) 7. [`close_transitions`中的工作列表增长](#close_transitions中的工作列表增长) 10. [无冗余性](#无冗余性) 11. [关于等价预言机的说明](#关于等价预言机的说明) 12. [主循环](#主循环) 13. [示例](#示例) 14. [评估模型精度](#评估模型精度) 15. [与L*比较](#与l比较) 16. [参考文献](#参考文献) 17. [工件](#工件) **重要：** Pyodide（https://pyodide.readthedocs.io/en/latest/）需要时间初始化。初始化完成通过“Run all”按钮的红色边框指示。 ## 前置条件 我们使用L*文章中未经改动的`Teacher`和`Oracle`。算法的其余部分独立于L*。 ### 可用包 这些包引用我之前文章中的包或已编译的纯Python包，可在以下位置获得。照例，如果需要在机器上直接运行程序，请安装它们。安装只需下载wheel文件（`pkg.whl`）并用`pip install pkg.whl`安装。 1. simplefuzzer-0.0.1-py2.py3-none-any.whl（https://rahul.gopinath.org/py/simplefuzzer-0.0.1-py2.py3-none-any.whl）来自“世界上最简单的文法模糊器”（http://rahul.gopinath.org/post/2019/05/28/simplefuzzer-01/）。 2. rxfuzzer-0.0.1-py2.py3-none-any.whl（https://rahul.gopinath.org/py/rxfuzzer-0.0.1-py2.py3-none-any.whl）来自“使用正则表达式进行模糊测试”（http://rahul.gopinath.org/post/2021/10/22/fuzzing-with-regular-expressions/）。 3. earleyparser-0.0.1-py2.py3-none-any.whl（https://rahul.gopinath.org/py/earleyparser-0.0.1-py2.py3-none-any.whl）来自“Earley解析器”（http://rahul.gopinath.org/post/2021/02/06/earley-parsing/）。 4. cfgrandomsample-0.0.1-py2.py3-none-any.whl（https://rahul.gopinath.org/py/cfgrandomsample-0.0.1-py2.py3-none-any.whl）来自“从上下文无关文法均匀随机采样字符串”（http://rahul.gopinath.org/post/2021/07/27/random-sampling-from-context-free-grammar/）。 5. cfgremoveepsilon-0.0.1-py2.py3-none-any.whl（https://rahul.gopinath.org/py/cfgremoveepsilon-0.0.1-py2.py3-none-any.whl）来自“从上下文无关文法移除空（epsilon）规则”（http://rahul.gopinath.org/post/2021/09/29/remove-epsilons/）。 6. gatleastsinglefault-0.0.1-py2.py3-none-any.whl（https://rahul.gopinath.org/py/gatleastsinglefault-0.0.1-py2.py3-none-any.whl）来自“专门化上下文无关文法以诱发故障”（http://rahul.gopinath.org/post/2021/09/09/fault-inducing-grammar/）。 7. hdd-0.0.1-py2.py3-none-any.whl（https://rahul.gopinath.org/py/hdd-0.0.1-py2.py3-none-any.whl）来自“层次化Delta调试”（http://rahul.gopinath.org/post/2019/12/04/hdd/）。 8. ddset-0.0.1-py2.py3-none-any.whl（https://rahul.gopinath.org/py/ddset-0.0.1-py2.py3-none-any.whl）来自“简单DDSet”（http://rahul.gopinath.org/post/2020/08/03/simple-ddset/）。 9. lstar-0.0.1-py2.py3-none-any.whl（https://rahul.gopinath.org/py/lstar-0.0.1-py2.py3-none-any.whl）来自“L*算法”（http://rahul.gopinath.org/post/2024/01/04/lstar-learning-regular-languages/）。 由于此笔记本既可作为网页笔记本，也可作为命令行脚本运行，因此如果未定义canvas，我们重新定义它。`__canvas__`函数在用作网页笔记本时由外部定义。 ## 从L*到TTT 在L*中，当等价预言机返回长度为\\(k\\)的反例\\(ce\\)时，算法将\\(ce\\)的所有\\(k\\)个后缀添加为新列（即状态判别器）。每个新列都需要重新查询所有现有行。然而，这些新列中有许多是冗余的，因为它们并未区分任何新状态对。 区分TTT与L*的关键洞见是：**一个反例只识别出一对被错误合并的状态对**。因此，只需**一个**新判别器就足够了，而不是\\(k\\)个。 TTT融合了以下独立贡献： - **Kearns和Vazirani（1994）**[2]（http://rahul.gopinath.org/post/2026/06/09/ttt-grammar-inference/#fn:kearns1994）用**判别树**替代了观察表。一棵由判别器后缀组成的二叉树，每个叶子对应一个状态。沿着树筛选字符串只需O(深度)次查询，而非O(|后缀集|)。 - **Rivest和Schapire（1993）**[1]（http://rahul.gopinath.org/post/2026/06/09/ttt-grammar-inference/#fn:rivest1993）证明，在反例上进行二分搜索可在O(log k)次查询中找到唯一的那个相关分割点，而不是添加所有k个后缀。 - **Isberner、Howar和Steffen（2014）**[3]（http://rahul.gopinath.org/post/2026/06/09/ttt-grammar-inference/#fn:isberner2014）将这些与**前缀变换**（保持访问序列最短）和**判别器终结化**（保持DT浅）相结合，产生了TTT。 判别树与访问序列生成树的组合被称为**观察包**[5]（http://rahul.gopinath.org/post/2026/06/09/ttt-grammar-inference/#fn:howar2012）。本文不直接使用该抽象；我们将两个结构分开管理。 ## DFA表示 `DFA`类与RPNI文章（http://rahul.gopinath.org/post/2025/10/24/rpni-learning-regular-languages/）中的类似。我们还添加了`run()`（返回消费完字符串后到达的状态）和`accepts()`（检查该状态是否为接受状态）。DFA类现在可以建模确定性有限状态机。我们还添加了一个辅助函数，用于将任意DFA渲染为Graphviz点图。 让我们对它进行彻底测试。 ## 预言机 让我们定义一个简单的模拟预言机，用于隔离测试组件。从L*导入的`Teacher`是完整预言机，将在主循环中使用。 ## 判别树 判别树（DT）替代了L*的扁平观察表。可以将其视为一场20问游戏：每个内部节点询问：“如果我将后缀\\(d\\)附加到该字符串，目标是否接受它？”然后左转（否）或右转（是）。每个叶子对应一个已知状态。 不同节点处的判别器后缀是**独立的字符串**，彼此无关；它们扮演的角色与L*中的后缀列相同，但每个反例只添加一个，而不是一次性添加反例的所有\\(k\\)个后缀。 树结构不是trie；父节点的后缀不是子节点后缀的前缀，且兄弟后缀之间不必有任何共同点。这棵树纯粹是一个**决策结构**：每个节点的后缀是在该点可达的状态之间进行区分的问题，之所以选择它，只是因为它区分了某对原本会被合并的状态。不同深度的两个节点可能共享同一个后缀，也可能完全不相关；重要的是每一步的二元答案。 内部节点的两个孩子本身都可以是内部节点，树可以任意深。叶子代表一个已知状态，它没有判别器。在学习早期，树很浅；每个反例只添加一个内部节点，将一个现有叶子分裂成两个孩子。节点初始作为叶子，持有一个状态名。当等价预言机返回反例时，意味着黑盒与假设DFA在某个字符串上不一致：到达不同黑盒状态的两个字符串被路由到了同一个假设状态。`decompose`识别出哪个叶子负有责任并将其分裂。 分裂叶子意味着它变成一个内部节点：它忘记状态名，获得一个判别器后缀，并长出两个子叶子，分别对应两个现在不同的状态。哪个子节点向右、哪个向左，由查询预言机`reach(old_state) + discriminator`决定。右子节点表示该查询返回True，左子节点表示返回False。注意，向右并不意味“被接受”：稍后，当筛选任意字符串\\(w\\)时，同一节点询问\\(w + discriminator\\)是否被接受，并在True时向右路由，False时向左。方向编码与预言机的一致性，而非\\(w\\)本身是否被接受。 我们进行原地突变，因为树中其他节点已经持有对该对象的引用；用新对象替换将使这些引用失效。