Detecting Changes in Loop Behavior for Active Learning

Bram Verboom, Simon Dieck, Sicco Verwer
Proceedings of 16th edition of the International Conference on Grammatical Inference, PMLR 217:142-156, 2023.

Abstract

Active automaton learning is a popular approach for building models of software systems. The approach forms a hypothesis model from observations and then performs a heuristic equivalence query to check if the learned model is equal to the model under test. The current methods for equivalence queries, however often fail to find counterexamples when encountering loops, one of the most common control structures in software. We introduce two novel equivalence checkers that better handle loops. One extends the well-known W-Method, and the other uses symbolic execution. Both methods are tested on RERS challenge problems. We show that our approaches find more counterexamples on suitable problems and thus learn more accurate models. We further test our symbolic execution approach outside active learning and show that it finds more errors than the state-of-the-art method Klee on several problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v217-verboom23a, title = {Detecting Changes in Loop Behavior for Active Learning}, author = {Verboom, Bram and Dieck, Simon and Verwer, Sicco}, booktitle = {Proceedings of 16th edition of the International Conference on Grammatical Inference}, pages = {142--156}, year = {2023}, editor = {Coste, François and Ouardi, Faissal and Rabusseau, Guillaume}, volume = {217}, series = {Proceedings of Machine Learning Research}, month = {10--13 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v217/verboom23a/verboom23a.pdf}, url = {https://proceedings.mlr.press/v217/verboom23a.html}, abstract = {Active automaton learning is a popular approach for building models of software systems. The approach forms a hypothesis model from observations and then performs a heuristic equivalence query to check if the learned model is equal to the model under test. The current methods for equivalence queries, however often fail to find counterexamples when encountering loops, one of the most common control structures in software. We introduce two novel equivalence checkers that better handle loops. One extends the well-known W-Method, and the other uses symbolic execution. Both methods are tested on RERS challenge problems. We show that our approaches find more counterexamples on suitable problems and thus learn more accurate models. We further test our symbolic execution approach outside active learning and show that it finds more errors than the state-of-the-art method Klee on several problems.} }
Endnote
%0 Conference Paper %T Detecting Changes in Loop Behavior for Active Learning %A Bram Verboom %A Simon Dieck %A Sicco Verwer %B Proceedings of 16th edition of the International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2023 %E François Coste %E Faissal Ouardi %E Guillaume Rabusseau %F pmlr-v217-verboom23a %I PMLR %P 142--156 %U https://proceedings.mlr.press/v217/verboom23a.html %V 217 %X Active automaton learning is a popular approach for building models of software systems. The approach forms a hypothesis model from observations and then performs a heuristic equivalence query to check if the learned model is equal to the model under test. The current methods for equivalence queries, however often fail to find counterexamples when encountering loops, one of the most common control structures in software. We introduce two novel equivalence checkers that better handle loops. One extends the well-known W-Method, and the other uses symbolic execution. Both methods are tested on RERS challenge problems. We show that our approaches find more counterexamples on suitable problems and thus learn more accurate models. We further test our symbolic execution approach outside active learning and show that it finds more errors than the state-of-the-art method Klee on several problems.
APA
Verboom, B., Dieck, S. & Verwer, S.. (2023). Detecting Changes in Loop Behavior for Active Learning. Proceedings of 16th edition of the International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 217:142-156 Available from https://proceedings.mlr.press/v217/verboom23a.html.

Related Material