模型学习算法的开发正是对寄存器自动机进行的特定扩展。11 这些自动机具有有限的一组状态，但都用一组可用于存储数据值的寄存器进行扩展了。输入和输出动作被参数化为具体的数据值，可以在转换保护中进行相等测试并存储在寄存器中。图 10 给出了寄存器自动机的简单示例，即容量为 2 的 FIFO 集。一个 FIFO 集对应于一个只能存储不同值的队列。它有一个 Push（d）输入符，用来尝试在队列中插入值 d 的符号，还有一个 Pop 输入符，用来尝试从队列中取回一个值。如果输入值可以成功添加，则 Push 的对应输出为 OK，如果输入值已经在队列中或者队列为满，则 Push 的对应输出为 KO。如果以队列中最旧的值作为参数，则 Pop 的对应输出是 Out，如果队列是空的，则 Pop 的对应输出是 KO。

图.10

抽象是将模型学习方法扩展至现实应用的关键

在寄存器自动机中，所有数据值是完全对称的，j2直播，且这种对称性是可以在学习过程中被利用的。在本文中已经探索了两种不同的方法。第一种方法，以 Cassel 等人为代表，12 已在软件工具 LearnLib26 和 RALib 中得到实施。10 模型学习算法通常依赖于 Nerode 关系（Nerode relation）来识别已学过的自动机的状态和转换：如果两个词的残差语言（residual languages）吻合，这两个词则导致相同的状态。现在的基本思想是为寄存器自动机设计出一个类似 Nerode 的同余关系，而这决定了已推断的自动机的寄存器的状态、转换、和内容。这种实施方法的技术基础是所谓的符号决策树（symbolic decision trees），它可以用来总结许多用简明符号表达的测试结果。

学习寄存器自动机的第二种方法，以 Aarts 等人为代表，已在软件工具 Tomte 中得到实施。这种方法使用反例引导的抽象提炼来自动构建适当的映射器。这种想法源于一个彻底抽象，即完全忽略在输入和输出动作中出现的数据值。当这种抽象过于粗糙时，learner 将观察到非确定性行为。比如在图 10 的示例中，输入序列 Push Push Pop Pop 大部分情况触发的输出为 OK OK Out KO，但有时为 OK OK Out Out。出现这种行为就需要对抽象进行提炼。在我们的示例中，比如就第二个 Push，我们至少需要两个抽象版本，因为这显然关乎该输入的数据值是否等于第一个 Push 的数据值。RALib 和 Tomte 在性能上都优于 LearnLib。Tomte 和 RALib 的性能大致相当。RALib 在一些基准测试中胜过 Tomte，但是 Tomte 能够学习一些 RALib 无法处理的寄存器自动机，例如容量为 40 的 FIFO 集。

研究挑战

即使模型学习已经在许多地方得到成功应用，但该研究领域仍处于起步阶段。模型学习的应用具有巨大的潜力，尤其是在传统控制软件领域，但是还需要对算法和工具进行更多的研究，以将模型学习从目前的学术原型水平转变为可实际使用的技术水平，从而方便应用于大量不同类型的系统。在这里，我将讨论一些主要的研究挑战。

谓词与数据操作。最近对寄存器自动机模型学习算法所做的扩展是一个突破，这可能使模型学习适用于更大范围的系统。由于不允许对数据进行操作的限制，可以被描述为寄存器自动机的系统类型很少，并且主要由一些学术样例构成，例如有界重传协议和一些简单数据结构等等。然而，如 Cassel 等人所指，12 使用 SMT 解决寄存器自动机的新学习算法可以被扩展为 EFSM 的形式，其中模型防护（guard）可能包含谓词，如 successor 和小于关系（less than relation）。目前已经有 RALib 的原型实现，而且我们正在接近可以自动学习真实世界协议模型的目标，这样的协议可以像 TCP、SIP、SSH 和 TLS 等等，而这些都不需要手动定义抽象。然而，我们对使用不同谓词和操作学习 EFSM 的算法的理解仍然有限，而且还有许多悬而未决的问题。

即使模型学习已经在许多地方得到成功应用，但该研究领域仍处于起步阶段。

Isberner24开发了一种用于可视下推自动机（VPA）的模型学习算法，该算法是 Alur 和 Madhusudan 提出的一种限制类型的下推自动机。5 这个结果在某种意义上与学习寄存器自动机上的结果正交：使用寄存器自动机学习，可以学习具有存储来自无限域的、带有有限容量存储值的堆栈，而使用 VPA 学习可以学习具有无限容量的堆栈，其存储来自有限域的数据值。从实践角度来看，开发一种通用于寄存器自动机和 VPA 这一类模型的学习算法将是有用的。许多协议中的消息可以缓冲，因此我们需要能够学习具有无限容量的队列的算法。