Extending AALpy with Passive Learning: A Generalized State-Merging Approach

Benjamin von Berg (🖂), Bernhard K. Aichernig · 2025

Read Extending AALpy with Passive Learning: A Generalized State-Merging Approach by Benjamin von Berg (🖂), Bernhard K. Aichernig (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-06333.txt.

Introduction

Benjamin von Berg and Bernhard Aichernig add passive learning to an open-source automata learning library in a 2025 study. Automata learning infers a machine model of a system's behavior. Active learning asks the system questions, while passive learning works from logs that already exist. The library, AALpy, was known mainly for active methods across many automaton types.

The new code implements state merging in the red-blue framework in a general way. One shared internal representation lets the same method serve different automaton types with rich configuration options. Passive learning matters when a system cannot be probed freely, such as legacy or safety-critical software.

Catalog record

CREATORBenjamin von Berg (🖂), Bernhard K. Aichernig
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-06333

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Extending AALpy with Passive Learning: A Generalized State-Merging Approach Benjamin von Berg (🖂), Bernhard K. Aichernig Abstract AALpy is a well-established open-source automata learning library written in Python with a focus on active learning of systems with IO behavior. It provides a wide range of state-of-the-art algorithms for different automaton types ranging from fully deterministic to probabilistic automata. In this work, we present the recent addition of a generalized implementation of an important method from the domain of passive automata learning: state-merging in the red-blue framework. Using a common internal representation for different automaton types allows for a general and highly configurable implementation of the red-blue framework. We describe how to define and execute state-merging algorithms using AALpy, which reduces the implementation effort for state-merging algorithms mainly to the definition of compatibility criteria and scoring. This aids the implementation of both existing and novel algorithms. In particular, defining some existing state-merging algorithms from the literature with AALpy only takes a few lines of code. red-blue framework 1 Introduction AALpy [ 18 ] is an active automata learning library written in Python with a focus on systems that show IO behavior, i.e. reactive systems. Automata learning algorithms extract a finite-state model from observations of a system-under-learning. They form the basis for black-box checking [ 21 , 2 ] . AALpy is open-source and published on github 1 1 1 https://github.com/DES-Lab/AALpy . It is well-established in the community and has been used in various domains. This includes reinforcement learning [ 26 , 27 ] , analysis of communication protocols [ 22 , 23 ] and neural networks [ 19 ] , black-box checking [ 25 , 14 ] , anomaly detection [ 17 ] , software testing [ 9 ] , process mining [ 5 , 13 ] and reuse in other learning algorithms [ 3 , 12 ] . Passive learning algorithms use existing training data, like system logs, while active learning queries the system during learning. So far, AALpy has been mainly concerned with active automata learning. In this paper, we extend AALpy with a passive automata learning library for state-merging algorithms based on the red-blue framework [ 15 ] . This encompasses (1) algorithms already implemented in AALpy, such as RPNI [ 20 ] and IOAlergia [ 16 ] , (2) existing algorithms that were not originally designed for the IO setting, such as the likelihood-ratio method by Verwer et al. [ 29 ] or EDSM [ 15 ] and (3) new approaches based on state-merging, be it completely novel methods or adaptations of existing methods in order to account for domain knowledge, such as additional constraints. The rest of the paper is structured as follows. Section 2 gives some background and discusses how we generalized state merging. Section 3 demonstrates the usage of the new library. Section 4 draws the conclusions, relates AALpy to other tools and gives an outlook of further possible extensions. Further examples are provided in the Appendix . 2 Principles of Operation 2.1 Universal Internal Formalism The tool presented in this work covers several types of finite-state automata with IO behavior. These automaton types share a small set of common assumptions: (1) There is a unique initial state from which execution starts. (2) Applying an input to an automaton triggers a state change and the emission of an output. (3) For each transition, the reached state is uniquely determined by the combination of current state, applied input and observed output. The following definition of automata covers Assumption 1 and 2 above and can be extended to more specific types of automata. Definition 1 An IO automaton is a tuple \mathcal{M}=\langle Q,q_{0},I,O,T\rangle , where Q is the set of states, q_{0}\in Q is the initial state, I and O are the sets of input and output symbols respectively and T\subseteq Q\times I\times O\times Q is a set of transitions. A transition \langle q,i,o,q^{\prime}\rangle\in T implies that applying input i in state q may cause \mathcal{M} to emit the output o and switch to state q^{\prime} . In other words, the automaton might behave nondeterministically. We discern between different forms of determinism. Definition 2 An automaton \mathcal{M}=\langle Q,q_{0},I,O,T\rangle is deterministic iff \forall\langle q_{1},i_{1},o_{1},q^{\prime}_{1}\rangle,\langle q_{2},i_{2},o_{2},q^{\prime}_{2}\rangle\in T:q_{1}=q_{2}\land i_{1}=i_{2}\Rightarrow o_{1}=o_{2}\land q^{\prime}_{1}=q_{2}^{\prime} It is observably nondeterministic iff \forall\langle q_{1},i_{1},o_{1},q^{\prime}_{1}\rangle,\langle q_{2},i_{2},o_{2},q^{\prime}_{2}\rangle\in T:q_{1}=q_{2}\land i_{1}=i_{2}\land o_{1}=o_{2}\Rightarrow q^{\prime}_{1}=q_{2}^{\prime} Note that observable nondeterminism is equivalent to Assumption 3 above. Deterministic and observably nondeterministic automata allow writing the set of transitions as a (partial) transition function \delta of the set of transitions with \delta:Q\times I\rightharpoonup O\times Q and \delta:Q\times I\times O\rightharpoonup Q respectively. The definition of IO automata follows the behavior of Mealy machines, where the output of a transition depends on the source state, the target state and the provided input symbol. This is in contrast to Moore behavior, where the output depends on the target state alone: Definition 3 An IO automaton \mathcal{M}=\langle Q,q_{0},I,O,T\rangle has Moore behavior iff \forall\langle q_{1},i_{1},o_{1},q^{\prime}_{1}\rangle,\langle q_{2},i_{2},o_{2},q^{\prime}_{2}\rangle\in T:q^{\prime}_{1}=q^{\prime}_{2}\Rightarrow o_{1}=o_{2} A Moore machine can thus be seen as a deterministic IO automaton \mathcal{M}=\langle Q,q_{0},I,O,T\rangle with Moore behavior that emits the output o_{0} associated with q_{0} prior to handling the first input. Informally, we treat the emission of the initial output as the result of a transition \langle\epsilon,\epsilon,o_{0},q_{0}\rangle\in T . When learning probabilistic automaton types, not only the possibility of a transition happening needs to be considered, but also its probability. This prompts the use of IO Frequency Automata (IOFA), which augment IOA with an observation count for transitions. Definition 4 An IO frequency automaton is a tuple \mathcal{M}=\langle Q,q_{0},I,O,\delta,\nu\rangle , where \langle Q,q_{0},I,O,\delta\rangle is an observably nondeterministic IO automaton and \nu:Q\times I\times O\rightarrow\mathbb{N} is the frequency function. The intuition behind \nu(q,i,o)=n is that the transition from q on input i emitting o has been observed n times. We use IOFA as the common internal representation from which all supported automaton types can be extracted. This allows us to use a single implementation which is shared across all supported automaton types. Additional restrictions are required during the merging process to enforce the structural form of those automaton types and are covered in Section 2.3 . 2.2 State Merging in the Red-Blue Framework This section, gives a brief overview over state merging algorithms and the red-blue framework. For a more detailed account consider [ 10 ] and [ 15 ] respectively. State-merging algorithms are one of the main categories of passive automata learning algorithms. The input is given as a collection of traces, where each trace is a sequence of input-output pairs. The basic structure of state-merging algorithms consists of the following steps. First, a simple automaton representation of the provided traces is created, commonly using a so-called Prefix Tree Automaton (PTA). The PTA contains a state for every prefix in the input data. Grouping the behavior of traces with shared prefixes is admissible because we assume observable nondeterminism and results in a tree-shaped IOFA that describes exactly the observed traces and no other behavior. In the main loop of the algorithm, the automaton is generalized by iteratively merging pairs of states until no more merges are possible. We use the term merge candidate to refer to a pair of states that is considered for merging. Merging two states q_{1} and q_{2} results

Read the complete text