| 摘要: |
| 模型学习是一种获取黑盒软件系统行为模型的有效方法，可分为主动学习和被动学习.主动学习是基于字母表构造测试用例，通过与黑盒系统主动交互，可在多项式时间内得到目标系统的最小完备自动机，其中等价查询仍是开发和应用主动自动机学习工具的障碍之一.通过探讨反例对于学习算法的影响，定义假设的比较规则，提出测试用例构造的两个原则，同时依据原则对Wp-method等价查询算法改进，产生更优的假设，有效降低查询的数量，并基于LearnLib开源工具，分别以3类自动机为实验对象验证原则和改进算法的有效性. |
| 关键词: 模型学习 自动机 成员查询 等价查询 |
| DOI：10.13328/j.cnki.jos.006532 |
| 分类号: |
| 基金项目:国家重点研发计划（2019QY1300） |
|
| Optimization of Equivalence Query Algorithm in Active Automata Learning |
|
PAN 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) can be divided into active and passive learning. Based on given input and output alphabets, the minimum complete state machine of the target system can be obtained in polynomial time through active interaction with the black box system. And the algorithm of equivalence query is still a big obstacle to the development and application of active automata learning tools. This study discusses the influence of counterexamples on the learning algorithms with the discrimination tree, and defines the comparison rules of hypotheses, and proposes two principles of constructing test cases. According to the principle, the Wp-method equivalence query algorithm is improved to produce better hypotheses and effectively reduce the number of queries and symbols. Based on the LearnLib, three kinds of automata are used as experimental objects to verify the effectiveness of the principle and the improved algorithm. |
| Key words: model learning automata membership query equivalence query |
