A Novel Algorithm for Automata Learning via Databases

Abstract

Automata learning is a powerful technique for obtaining system models from observed behavior and is often used in software testing, verification, and reverse engineering. However, most algorithms used today either require interaction with that system or suffer from poor scaling due to memory limitations. A relatively new approach in automata learning algorithms has been to store the dataset in a database and interact with it through custom database queries. This thesis uses this approach to develop a novel algorithm based on regular expression queries and custom data structures. Upon evaluation on generated datasets of binary sequences and the Abbadingo benchmarks, this approach was found to scale linearly to much larger dataset sizes than EDSM and to use orders of magnitude fewer queries than L*. It is also accompanied by a formal proof of correctness. Ultimately, this work provides a highly scalable algorithm and a self-contained, comprehensive theoretical framework.