We present an efficient incremental learning algorithm for Deterministic Finite Automaton (DFA) with the help of inverse query (IQ) and membership query (MQ). This algorithm is an extension of the Identification of Regular Languages (ID) algorithm from a complete to an incremental learning setup. The learning algorithm learns by making use of a set of labeled examples and by posing queries to a knowledgeable teacher, which is equipped to answer IQs along with MQs and equivalence query. Based on the examples (elements of the live complete set) and responses against IQs from the minimally adequate teacher (MAT), the learning algorithm constructs the hypothesis automaton, consistent with all observed examples. The Incremental DFA Learning algorithm through Inverse Queries (IDLIQ) takes time complexity in the presence of a MAT and ensures convergence to a minimal representation of the target DFA with finite number of labeled examples. Existing incremental learning algorithms; the Incremental ID, the Incremental Distinguishing Strings have polynomial (cubic) time complexity in the presence of a MAT. Therefore, sometimes, these algorithms even fail to learn large complex software systems. In this research work, we have reduced the complexity (from cubic to square form) of the DFA learning in an incremental setup. Finally, we prove the correctness and termination of the IDLIQ algorithm.
Get full access to this article
View all access options for this article.
References
1.
BiermannAW, FeldmanJA. On the synthesis of finite-state machines from samples of their behavior. IEEE Trans Comput, 1972; 100:592–597.
2.
LangKJ.Random DFA's can be approximately learned from sparse uniform examples. In: Proceedings of the Fifth Annual Workshop on Computational Learning Theory. ACM: Pittsburgh, PA, USA;, 1992; pp. 45–52; doi: 10.1145/130385.130390
3.
ParekhR, NichitiuC, HonavarV. A polynomial time incremental algorithm for regular grammar inference. In: Proc. Fourth Int. Colloq. on Grammatical Inference (ICGI 98). Springer; 1998.
4.
PetrenkoA, AvellanedaF, GrozR, OriatC. FSM inference and checking sequence construction are two sides of the same coin. Softw Q J, 2019; 27:651–674.
5.
SeijasPL, ThompsonS, FranciscoMÁ. Model extraction and test generation from JUnit test suites. Softw Q J, 2018; 26:1519–1552.
6.
AngluinD.Learning regular sets from queries and counterexamples. Inform Comput, 1987; 75:87–106.
7.
AngluinD.A note on the number of queries needed to identify regular languages. Inform Control, 1981; 51:76–87.
8.
GoldEM.Language identification in the limit. Inform Control, 1967; 10:447–474.
9.
OncinaJ, GarciaP. Identifying regular languages in polynomial. In: Advances in Structural and Syntactic Pattern Recognition, Volume 5 of Series in Machine Perception and Artificial Intelligence. Singapore: World Scientific; 1992; pp.99–108.
10.
MeinkeK, SindhuMA. Correctness and Performance of an Incremental Learning Algorithm for Kripke Structures Technical Report. School of Computer Science and Communication, Royal Institute of Technology: Stockholm; 2010.
11.
MeinkeK, SindhuMA. Incremental Learning-Based Testing for Reactive Systems in Tests and Proofs (Gogolla M, Wolff B. eds.) 6706. Springer: Heidelberg; 2011; pp.134–151.
12.
MazharR, SindhuMA. DKL: An efficient algorithm for learning deterministic Kripke Structures. Acta Informatica, 2021; 58:611–651.
13.
KearnsMJ, VaziraniUV, VaziraniU.An Introduction to Computational Learning Theory. MIT Press: Cambridge, MA, USA; 1994.
14.
IsbernerM, HowarF, SteffenB. The TTT algorithm: A redundancy-free approach to active automata learning. In: International Conference on Runtime Verification. 2014; pp.307–322.
15.
DupontP. Incremental regular inference. In: Proceedings of the Third ICGI-96. Springer; 1996.
16.
MeinkeK. CGE: A sequential learning algorithm for mealy automata. In: Proc. Tenth Int. Colloq. on Grammatical Inference (ICGI 2010). Springer; 2010; pp.148–162.
17.
BalcázarJL, DíazJ, GavaldaR, WatanabeO. An optimal parallel algorithm for learning DFA. In: Proceedings of the Seventh Annual Conference on Computational Learning Theory. Springer; 1994; pp.208–217.
18.
ShahbazM, GrozR. Analysis and testing of black-box component-based systems by inferring partial models. Softw Test Verificat Reliabil, 2014; 24:253–288.
19.
AichernigBK, TapplerM. Learning from faults: Mutation testing in active automata learning. In: NASA Formal Methods Symposium. Springer; 2017.
20.
AichernigBK, TapplerM. Efficient active automata learning via mutation testing. J Autom Reason, 2019; 63:1103–1134.
21.
ShuG, LeeD. Testing security properties of protocol implementations—A machine learning based approach. In: 27th International Conference on Distributed Computing Systems. 2007.
22.
ChoCY, ShinECR, SongD, et al. Inference and analysis of formal models of botnet command and control protocols. In: 17th ACM Conference on Computer and Communications Security. 2010; pp.426–439.
23.
HungarH, NieseO, SteffenB. Domain specific optimization in automata learning. In: International Conference on Computer Aided Verification. 2003; pp.315–327.
24.
AartsF, KuppensH, TretmansJ, et al.Improving active mealy machine learning for protocol conformance testing. Mach Learn, 2014; 96(1–2):189–224.
25.
SmeenkW, MoermanJ, VaandragerF, JansenDN. Applying automata learning to embedded control software. In: International Conference on Formal Engineering Methods. 2015; pp.67–83.
26.
HesselA, LarsenKG, MikucionisM, et al. Testing real-time systems using UPPAAL. In: Formal Methods and Testing: An Outcome of the FORTEST Network, Revised Selected Papers. Springer: Berlin, Heidelberg; 2008; pp.77–117.
27.
HagererA, HungarH, NieseO, SteffenB. Model generation by moderated regular extrapolation. In: International Conference on Fundamental Approaches to Software Engineering. 2002; pp.80–95.
28.
WindmüllerS, NeubauerJ, SteffenB, et al. Active continuous quality control. In: Proceedings of the 16th International ACM Sigsoft Symposium on Component-Based Software Engineering. 2013; pp.111–120.
29.
FengL, LundmarkS, MeinkeK, et al. Case studies in learning-based testing. In: ICTSS’13 LNGS 8254. Springer; 2013; pp.164–179.
KrichenM. Improving formal verification and testing techniques for internet of things and smart cities. Mobile Netw Appl, 2019 [Epub ahead of print]; doi: 10.1007/s11036-019-01369-6.
32.
KumarN, MisraS, RodriguesJJPC, ObaidatM. Coalition games for spatiotemporal big data in internet of vehicles environment: A comparitive analysis. IEEE Internet Things J, 2015; 2(4):310–320.
33.
BergT, JonssonB, LeuckerM, SaksenaM. Insights to angluins learning. Electron Notes Theoret Comput Sci, 2015; 118:3–18.
34.
AngluinD.Negative results for equivalence queries. Mach Learn, 1990; 5:121–150.
AngulinD.Queries and concept learning. Mach Learn, 1988; 2:319–342.
37.
BalcázarJL, DìazJ, GavaldàR, WatanabeO. The query complexity of learning DFA. New Gener Comput, 1994; 12:337–358.
38.
De la HigueraC. Learning grammars and automata with queries. In: Topics in Grammatical Inference. Springer: Berlin, Heidelberg; 2016; pp.47–71.
39.
Becerra-BonacheL, DediuAH, TîrnăucăC. Learning DFA from correction and equivalence queries. In: International Colloquium on Grammatical Inference. Springer: Berlin, Heidelberg; 2006; pp.281–292.
40.
BergadanoF, VarricchioS. Learning behaviors of automata from multiplicity and equivalence queries. SIAM J Comput, 1996; 25(6):12681280.
41.
KinberE.On learning regular expressions and patterns via membership and correction queries. International Colloquium on Grammatical Inference. Springer: Berlin, Heidelberg; 2008; pp.125–138.
42.
ChandleeJ, FuJ, KarydisK, et al.Integrating grammatical inference into robotic planning. Int Confer Grammat Infer, 2012; 21:6983.
43.
MeinkeK. Learning based testing for Cyber Physical Systems of systems: A Platooning Study. In: Computer Performance Engineering. EPEW 2017. Lecture Notes in Computer Science, vol 10497. Springer: Cham; 2017.
44.
KhosrowjerdiH, MeinkeK. Learning-based testing for autonomous systems using spatial and temporal requirements. In: Proceedings of the 1st International Workshop on Machine Learning and Software Engineering in Symbiosis. 2018; pp.6–15.
45.
KhaliliA, NarizzanoM, NataleL, TacchellaA. Learning middleware models for verification of distributed control programs. Robot Autonom Syst, 2017; 92:139–151.
46.
AngluinD, ChenD. Learning a random DFA from uniform strings and state information. In: International Conference on Algorithmic Learning Theory. Springer: Cham; 2015.
47.
CasselS, HowarF, JonssonB, SteffenB. Active learning for extended finite state machines. Formal Aspects Comput, 2016; 28:233–263.
48.
VolpatoM, TretmansJ. Active learning of nondeterministic systems from an IOCO perspective. In: International Symposium on Leveraging Applications of Formal Methods, Verification and Validation. Springer: Berlin, Heidelberg; 2014; pp.220–235.
49.
LiY, ChenY-F, ZhangL, LiuD. A Novel Learning Algorithm for Büchi Automata Based on Family of DFAs and Classification Trees. In: International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Springer: Berlin, Heidelberg; 2017; pp.208–226.
50.
YangN, AslamK, SchiffelersR, et al. Improving model inference in industry by combining active and passive learning. In: 2019 IEEE 26th International Conference on Software Analysis, Evolution and Reengineering (SANER). 2019; pp.253–263.
51.
HopcroftJ. An n log n algorithm for minimizing states in a finite automaton. In: Theory of Machines and Computations. Elsevier; 1971; pp.189–196.
