主动自动机学习中的等价查询算法优化*潘 雁, 祝跃飞(数学工程与先进计算国家重点实验室(信息工程大学), 河南 郑州 450001)通信作者: 祝跃飞, E-mail: yfzhu17@sina.com摘　要: 模型学习是一种获取黑盒软件系统行为模型的有效方法, 可分为主动学习和被动学习. 主动学习是基于字母表构造测试用例, 通过与黑盒系统主动交互, 可在多项式时间内得到目标系统的最小完备自动机, 其中等价查询仍是开发和应用主动自动机学习工具的障碍之一. 通过探讨反例对于学习算法的影响, 定义假设的比较规则, 提出测试用例构造的两个原则, 同时依据原则对Wp-method 等价查询算法改进, 产生更优的假设, 有效降低查询的数量, 并基于LearnLib 开源工具, 分别以3 类自动机为实验对象验证原则和改进算法的有效性.关键词: 模型学习; 自动机; 成员查询; 等价查询中图法分类号: TP18中文引用格式: 潘雁, 祝跃飞. 主动自动机学习中的等价查询算法优化. 软件学报. http://www.jos.org.cn/1000-9825/6532.htm英文引用格式: Pan Y, Zhu YF. Optimization of Equivalence Query Algorithm in Active Automata Learning. Ruan Jian XueBao/Journal of Software (in Chinese). http://www.jos.org.cn/1000-9825/6532.htmOptimization of Equivalence Query Algorithm in Active Automata LearningPAN Yan, ZHU Yue-Fei(State Key Laboratory of Mathematical Engineering and Advanced Computing (Information Engineering University), Zhengzhou 450001, China)Abstract: As an effective technique for black-box state machine models of software systems, model learning (a.k.a. automata learning) canbe divided into active and passive learning. Based on given input and output alphabets, the minimum complete state machine of the targetsystem can be obtained in polynomial time through active interaction with the black box system. And the algorithm of equivalence queryis still a big obstacle to the development and application of active automata learning tools. This study discusses the influence ofcounterexamples on the learning algorithms with the discrimination tree, and defines the comparison rules of hypotheses, and proposes twoprinciples of constructing test cases. According to the principle, the Wp-method equivalence query algorithm is improved to produce betterhypotheses and effectively reduce the number of queries and symbols. Based on the LearnLib, three kinds of automata are used asexperimental objects to verify the effectiveness of the principle and the improved algorithm.Key words: model learning; automata; membership query; equivalence query计算机技术的发展使得软件系统在日常生活中无处不在, 软件实现的正确性是极其重要的, 而获取未知软件系统的行为模型是极具挑战性的, 其中模型学习[1]是一种获取未知软件系统的行为模型的常用方法, 其对象是黑盒系统, 一般为具有明确输入输出的软件, 如智能卡片[2]、协议实现[3]、遗留软件[4]等. 根据学习的策略, 模型学习一般分为两种: 一是基于软件系统已记录的输入输出数据进行分析, 称为被动学习, 其可以抽象为基于正反例数据进行正则语言的推断, 该问题被证明是NP 难问题[5], 以协议实现为例, 对于某个协议实现, 已有丰富且覆盖面较广的数据包, 被动学习即是通过已有的数据包推断协议自动机, 但已有的数据包都是问题描述中的正例数据, 没有反例数据, 这也是实际应用中广泛存在的问题; 二是基于已知字母表构造测试用例, 通过与黑盒系统主动交互来推断自动机, 称为主动自动机学习(亦称为主动学习), 能在一定程度上克服被动学习仅具有正样本的缺点, 同时被证明* 基金项目: 国家重点研发计划(2019QY1300)收稿时间: 2021-07-26; 修改时间: 2021-09-27, 2021-11-01; 采用时间: 2021-11-09;软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cnJournal of Software [doi: 10.13328/j.cnki.jos.006532] http://www.jos.org.cn©中国科学院软件研究所版权所有. Tel: +86-10-62562563网络首发时间：2022-11-15 09:35:41网络首发地址：https://kns.cnki.net/kcms/detail/11.2560.TP.20221113.1436.044.html可以在多项式时间内得到目标系统的最小完备自动机.主动学习广泛使用的框架是Angluin 提出的MAT (minimal adequete teacher) 框架[6], 主要分为两个步骤: 成员查询和等价查询, 成员查询是构造输入并获得程序的输出, 得到结果后观察是否符合一定条件, 若不符合条件, 则需继续进行查询直至满足一定的条件, 而后依据此结果构建一个假设. 由于只能获取部分输入的响应, 超出此范围的输入并不能保证其假设的正确性, 因此得到假设后需要通过等价查询判断假设的自动机是否正确, 如果不正确,等价查询将返回一个使假设不成功的反例. 而后算法需要依据反例对原始的分类策略和成员查询的空间进行更新, 同样需要使其符合一定条件, 循环上述过程直至构建的假设与实际系统的自动机相同, 该方法的前提条件是目标自动机的状态数已知.但是在实际系统中, 具有无穷知识的预言机并不存在, 使得理想的等价查询难以实现. 而是通常基于一致性检测的方法, 通过精心构造的成员查询对等价查询进行模拟, 常用算法包括W-method[7]和Wp-method (partial Wmethod)算法[8], 以及基于两种算法的随机化算法random W-method 和random Wp-method, 但是随机化方法的效果存在不确定性, 因此实际过程中仍以W-method 和Wp-method 算法为主[9–12], 其中Wp-method 算法所需的测试例理论上更少. 由于等价查询的复杂度相较于成员查询更高, 且随着目标状态数呈指数增长, Aarts 等人认为等价查询的测试选择和覆盖仍然是开发和应用主动学习工具的主要问题, 因此, 需要更多的研究以期提高等价查询的测试效率[13].由于Wp-method 算法的初衷是全覆盖的一致性测试, 构造的集合是固定的, 不关心测试顺序, 而在模型学习的等价查询阶段执行顺序是重要的, 如random Wp-method 本质上是随机选取Wp-method 集合中的测试用例进行查询, 直至找到反例或验证假设, 这些改进算法探讨的更多是在一次等价查询过程中如何更早地找到反例. 而本文尝试探讨不同反例对于所构造的假设的影响, 从而能在后续的学习过程中减少测试用例, 并通过分析优化Wpmethod构造的测试用例所执行的测试顺序使第一个反例尽可能地好. 本文的主要贡献在于:(1) 探讨反例对于学习算法的影响, 定义了反例和假设的对比方法.(2) 基于测试用例构造的两个原则优化Wp-method 算法的测试顺序, 提高等价查询算法的效率, 并通过实验验证优化效果.(3) 基于LearnLib 框架修改的代码开源 (https://gitee.com/z11panyan/learnlib.git, 文中设计的算法为 RefineWpmethod).本文第1 节介绍相关工作, 第2 节介绍主动自动机学习的基础理论, 第3 节阐述本文提出的优化方法, 第4 节展示相关的实验结果, 第5 节总结全文.1 相关工作基于MAT 框架的主动学习的通用流程如图1 所示, 框架中包含一个学习器与一个预言机, 学习器通过向预言机提出查询来学习未知的模型, 预言机了解SUL (system under learning) 的所有内容, 但学习者仅知道SUL 的输入/输出字母表. 为了学习未知自动机, 学习器提出查询, 即发送一个序列至SUL, 若SUL 接受则返回“是”, 否则返回“否”; 然后通过接收到的查询响应尝试构造一个行为与目标自动机相匹配的未知自动机, 并提交至预言机, 由预言机进行判断自动机是否正确并给出反例.LM为了将模型学习技术应用到具有大量输入和输出的实际系统中, Aarts 等人[14]在MAT 框架上增加了组件: 映射器(Mapper), 以便生成具有大消息字母表的组件, 其位于学习器和SUL 之间, 起着抽象与具象的作用, 学习器向映射器发送抽象消息, 映射器基于输入字母表将其转换为具体的消息并将其转发给SUL, 同时, 映射器将SUL 的具体响应转换回抽象消息并发送给学习器. Shahbaz 等人[15]以Mealy 自动机为目标提出了 , 其关注的响应是由输出字母表构成的输出序列. 基于观测表的方法将反例的后缀添加至观测表的列中, 会导致较大的冗余, Kearns 等人[16]构造了一种判别树的数据结构, 替代观测表, 判别树中的叶节点代表状态, 内部节点是两个状态的区分后缀,保证了由判别树生成的辨别串是无冗余的, 有效降低了测试序列的规模.等价查询算法方面, 最早采用的是1978 年Chow[7]提出的W-method 算法, 通过构建n-switch 树, 生成测试序列集合, 并从理论上证明了方法所构建的测试序列集合能有效验证自动机假设与实际自动机的等效性. Fujiwara2 软件学报 ****年第**卷第*期等人[8]提出了Wp-method 算法, 从理论上将全局的特征集合缩小为局部的某个状态的特征集合, 减少了测试序列的数量. 文献[17] 中的UIO (unique input/output) 方法是一种更特殊的情形下采用的, 其UIO 序列是一个可以区分某个状态与其他所有状态的输入序列, 但是这个序列不是每一个状态都存在的. 崔玲等人[18]提出一种基于集合覆盖的测试集约简方法, 通过分析Wp-method 方法的特点, 找出测试序列之间包含关系的规律, 删除冗余的测试用例. Yang 等人[19]提出主被动结合的等价查询算法, 增加基于日志的被动学习环节与查询缓存, 减少与SUL 的交互次数.学习器预言机成员查询等价查询① 开始/改进④ 响应⑤ 假设⑧ 反例⑧ 正确目标系统② 成员查询③ 响应⑥ 等价查询⑦ 响应图 1　基于MAT 框架的通用流程反例分析算法方面, L*算法是将反例的所有后缀加入观测表的行中, 导致观测表的规模较大, 而Rivest 等人[ 2 0 ]提出一种二叉搜索的方法, 有效提升了从反例中提取区分后缀的效率. 文献[21,22] 基于判别树提出Observation Pack 算法, 通过不断的Sift 与Split 操作构建判别树, 其中叶节点使用状态接受序列进行标记, 内部节点使用区分其叶节点代表的状态的后缀序列. 文献[23,24] 在此基础上, 针对状态图中存在的自循环和状态循环产生的长反例, 提出TTT 算法, 有效地消除了在分析反例时的过长前缀, 该算法也被各类开源工具采纳并实现.在自动机类型方面, 由于Mealy 自动机的表达能力有限, 文献[25,26] 将主动自动机学习推广到寄存器自动机, 一种能够表达数据对控制流影响的自动机模型, 其值可以分配给寄存器并对下一次输入进行比较, 可直接推断出一部分数据值对控制流的影响, 其表达能力相较于Mealy 自动机有一定的提升. Argyros 等人[27]采用的符号自动机是寄存器自动机的另一种形式, 其基于符号有限自动机的学习设计了一种黑盒差分测试框架SFADiff.实际应用中, Raffelt 等人于2006 年构建了基于Java 的开源框架LearnLib[28], 是被最为广泛使用的框架, 其主要学习的模型为Moore 与Mealy 自动机. 其所在团队在LearnLib 的基础上实现了RALib[29], 其基于SL*算法对寄存器自动机进行学习. Aarts 等人于2012 年在LearnLib 的基础上实现了TOMTE, 其关注点在映射器的实现, 其在文献[30] 与其博士论文中对映射器的抽象与具象行为进行了形式化描述, 并在TOMTE 中予以实现, 其学习模型主要为寄存器自动机, 上述框架都在持续更新中. 在网络协议领域, Cho 等人[31]基于L*算法提出了一种预测算法,采用观测表中的查询结果对新的输入序列的观测结果进行预测, 降低了成员查询的数量级, 并将其应用于僵尸网络命令与控制协议的分析. Ruiter 所在团队分别对TLS、OpenVPN[9]、QUIC 协议[32]的相关实现进行了分析;Fiterău-Broştean 团队分别针对TCP[33]、SSH[34]、DTLS 协议[11]进行研究, 并发现了相应的漏洞; 申莹珠等人基于LearnLib 平台对OpenVPN[35,36]、IPSec 协议进行了相关的研究; 王辰等人[37]结合协议特点提出了一种基于域知识的协议自动机主动学习算法. 除此之外, 很多研究者将模型学习与模型检测[38]、白盒测试[39]、模糊测试[40]结合以解决新的问题.2 基础知识主动学习可以抽象为主动构造一系列可观测的输入输出序列, 并基于此构建与软件实现逻辑相同的最小自动机, 下面对文献[24] 中的定义和算法进行一定的简化, 表1 是过程中常使用到的相关符号.潘雁 等: 主动自动机学习中的等价查询算法优化3表 1 符号描述表符号 a;b u; v;w u
v U
V s B [w] ⌊s⌋意义 字母 串 串的连接 集合的连接 状态 f0;1g 等价类 访问字符串2.1 基础定义  = fa;b; : : : ; zg w w1
w2 jwj "n = fw 2 jjwj = ng n [n] = fw 2 jjwj ⩽ ng 8U;V  ;U
V =fu
vju 2 U; v 2 Vg定义 1. 字母表. 单个字母的有穷非空集合, 记为 , 如 ; 由字母构成的有穷序列, 称为串, 记为 ,其构成的集合记为 , 串的连接记为 , 串的长度记为 . 特别地, 为空串, 长度为0. 长度为n 的串构成的集合为 , 长度不大于 的串构成 . 同时定义集合的连接,.w;u 2  u w 9v 2  w = u
v u⊑prefw juj < jwju⊊prefw w;u 2  v w 9u 2  w = u
v v⊑suffw juj < jwjv⊊suffw U   8w 2 U;8u⊑prefw u 2 U U给定 , 为 的前缀, 当且仅当 , 使得 , 记为 , 当 , 称严格前缀, 记为; 同理, 给定 , 为 的后缀, 当且仅当 , 使得 , 记为 , 当 , 称严格后缀,记为 . 给定 , 若 , 满足 , 则称 满足前缀闭合性.定义 2. 字母表  上的确定性有限自动机使用四元组 A = ⟨S; s0;