Optimization of Equivalence Query Algorithm in Active Automata Learning

被引：0
|
作者：
Pan Y. [1 ]
Zhu Y.-F. [1 ]
机构：
[1] State Key Laboratory of Mathematical Engineering and Advanced Computing, Information Engineering University, Zhengzhou
来源：
Ruan Jian Xue Bao/Journal of Software | 2023年 / 34卷 / 07期
关键词：
automata; equivalence query; membership query; model learning;
D O I：
10.13328/j.cnki.jos.006532
中图分类号：
学科分类号：
摘要：
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. © 2023 Chinese Academy of Sciences. All rights reserved.
引用
收藏
页码：3241 / 3255
页数：14
相关论文
共 43 条
  • [1] Ali S, Sun HL, Zhao YW., Model learning: A survey of foundations, tools and applications, Frontiers of Computer Science, 15, 5, (2021)
  • [2] Chalupar G, Peherstorfer S, Poll E, de Ruiter J, de Ruiter JEJ., Automated reverse engineering using LEGO, Proc. of the 8th USENIX Workship on Offensive Technologies, pp. 1-10, (2014)
  • [3] de Ruiter J, Poll E., Protocol state fuzzing of TLS implementations, Proc. of the 24th USENIX Conf. on Security Symp, pp. 193-206, (2015)
  • [4] Aslam K, Cleophas L, Schiffelers R, van den Brand M., Interface protocol inference to aid understanding legacy software components, Software and Systems Modeling, 19, 6, pp. 1519-1540, (2020)
  • [5] Gold EM., Complexity of automaton identification from given data, Information & Control, 37, 3, pp. 302-320, (1978)
  • [6] Angluin D., Learning regular sets from queries and counterexamples, Information & Computation, 75, 2, pp. 87-106, (1987)
  • [7] Chow TS., Testing software design modeled by finite-state machines, IEEE Trans. on Software Engineering, SE-4, 3, pp. 178-187, (1978)
  • [8] Fujiwara S, Bochmann GV, Khendek F, Amalou M, Ghedamsi A., Test selection based on finite state models, IEEE Trans. on Software Engineering, 17, 6, pp. 591-603, (1991)
  • [9] Daniel LA, Poll E, de Ruiter J., Inferring OpenVPN state machines using protocol state fuzzing, Proc. of the 2018 IEEE European Symp. on Security and Privacy Workshops (EuroS&PW), pp. 11-19, (2018)
  • [10] Guo JX, Gu CX, Chen X, Wei FS., Model learning and model checking of IPSec implementations for internet of things, IEEE Access, 7, pp. 171322-171332, (2019)
12345