PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Benjamin von Berg, Bernhard K. Aichernig

arXiv:2506.06333v2cs.LGcs.FL

TL;DR

Passive automata learning uses existing traces, but AALpy had mainly focused on active learning. This paper adds a generalized red-blue state-merging implementation using a shared representation across supported automaton types. It covers varied IO behaviors and is described as sufficiently fast for practical applications.

  • Problem

    AALpy had mainly focused on active learning, while passive learning uses existing training data such as system logs.

    Source: §1 · p. 2

  • Method

    The paper implements the red-blue framework over a shared IO automaton representation and configures algorithms through choices including compatibility evaluation and scoring.

    Source: §2.1 · p. 2, §2.2 · p. 4, §3.1 · p. 9

  • Results

    The implementation covers deterministic, observably nondeterministic, and probabilistic IO automata with Mealy- or Moore-style outputs, and is sufficiently fast for practical applications.

    Source: §4 · p. 10

  • Takeaways & Limitations

    Defining state-merging algorithms in AALpy can focus implementation effort on compatibility criteria and scoring, supporting both existing and novel approaches.

    Source: §1 · p. 2, §3.1 · p. 9

    The supported IO automata assume a unique initial state, input-triggered state changes and outputs, and a uniquely determined reached state given the current state, input, and observed output.

    Source: §2.1 · p. 2

Abstract

from arXiv · show

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.

1 Introduction

AALpy is an open-source Python library focused on active learning of reactive systems, and this work extends it with passive state-merging algorithms in the red-blue framework. The extension covers existing and new approaches, including adaptations for domain knowledge.

1 Introduction

  • AALpy is an open-source Python library for active automata learning focused on reactive systems with input-output behavior.Automata learning extracts finite-state models from observations and forms a basis for black-box checking.Source: §1 · p. 1
  • The library has been used across reinforcement learning, communication protocols, neural networks, black-box checking, anomaly detection, software testing, and process mining.The paper also notes reuse in other learning algorithms.Source: §1 · p. 1
  • AALpy’s passive extension supports existing algorithms, methods adapted from outside the IO setting, and new state-merging approaches incorporating domain knowledge.Examples named include RPNI, IOAlergia, the likelihood-ratio method, and EDSM.Source: §1 · p. 2
  • The paper describes the background and generalized state-merging approach, demonstrates library usage, and concludes with related tools and possible extensions.Further examples appear in the appendix.Source: §1 · p. 2

2 Principles of Operation

AALpy represents IO systems with a shared automaton formalism, then uses red-blue state merging to generalize trace data while enforcing the chosen automaton structure. Its framework restricts candidate merges and supports multiple output and transition behaviors.

2.1 Universal Internal Formalism

  • The common IO automaton formalism assumes a unique initial state and input-triggered state changes with outputs, while allowing transitions to exhibit nondeterminism.IO frequency automata add transition-observation counts and serve as the shared representation from which supported types can be extracted.Source: §2.1 · p. 2, It is observably nondeterministic iff · p. 3

It is observably nondeterministic iff

  • Observable nondeterminism means the same state, input, and output determine a unique successor, and it is equivalent to the framework’s third automaton assumption.The formalism distinguishes this from deterministic behavior, where state and input determine both output and successor.Source: It is observably nondeterministic iff · pp. 2–3, §2.1 · p. 2

2.2 State Merging in the Red-Blue Framework

  • State merging starts with a prefix-tree automaton built from input-output traces, then generalizes it through merges that can imply further merges among successor states.The criteria for candidate selection and compatibility depend on the algorithm; the red-blue framework limits checks to red-blue pairs.Source: §2.2 · pp. 3–4
  • The red-blue framework considers red-blue state pairs, promotes blue states incompatible with every red state, and otherwise merges the highest-scoring candidate until all states are red.A specified node order breaks ties; the final model is returned when no states remain outside the red set.Source: §2.2 · p. 4

2.3 Enforcing Automaton Structure

  • AALpy combines Mealy- or Moore-style output behavior with deterministic, nondeterministic, or probabilistic transition behavior, with DFAs and Markov chains subsumed by these types.The table organizes the combinations by output behavior in rows and transition behavior in columns.Source: §2.3 · pp. 5–6, Table 1 · p. 6
  • Moore behavior and deterministic transitions are enforced by rejecting merges that would violate their respective structural properties.Probabilistic transition behavior is obtained by normalizing transition frequencies.Source: §2.3 · p. 6

3 Usage

Section 3 explains how to configure and run generalized state-merging algorithms, then describes utilities for inspecting models and supplying different training-data formats.

3.1 Defining and Running State-Merging Algorithms

  • GeneralizedStateMerging is configured with output behavior, transition behavior, and a ScoreCalculation object for compatibility and scoring.The choices support Moore or Mealy outputs and deterministic, nondeterministic, or stochastic transitions.Source: §3.1 · pp. 7–8
  • run accepts traces of input-output pairs and selects the output automaton type from the configured behaviors; Moore traces include the initial output.Other training representations include labeled input sequences for DFA inference and observation-only sequences for probabilistic models.Source: §3.1 · p. 7, §3.2 · p. 9
  • local_compatibility checks states as they are added to a partition, and any incompatible tested pair rejects the merge candidate.score_function evaluates a mapping from pre-merge states to their resulting partition states; True or False triggers immediate acceptance or rejection.Source: §3.1 · p. 8
  • EDSM scores a merge candidate by counting the local compatibility checks it triggers, treating those checks as evidence for the merge.The example score is the number of merged states minus the number of partitions.Source: §3.1 · p. 8
  • Options tune preprocessing, postprocessing, compatibility evaluation on the PTA or common futures, candidate order, and depth-first versus breadth-first checking.The minimum-blue option further limits candidates to red states paired with the least blue node under the chosen order.Source: §3.1 · p. 9

3.2 Utilities

  • Utilities support returning the internal GsmNode representation and instrumenting red-blue events such as merges and promotions for analysis or debugging.These options are intended for experimenting with algorithms and understanding failure cases.Source: §3.2 · p. 9
  • GsmNode.visualize supports customizable GraphViz views that can highlight local determinism or incorrect merges during algorithm design.GraphViz is cited as.Source: §3.2 · pp. 9–10

4 Concluding Remarks

The extension supports varied IO automata while prioritizing generality and usability over speed. The authors also identify combining active and passive learning and injecting domain knowledge as future directions.

  • FlexFringe is closely related but lacks out-of-the-box IO support, while LearnLib and jajapy focus on narrower domains and offer more algorithms within them.FlexFringe offers more configuration options, including custom data attached to states.Source: §4 · p. 10
  • 7.24× slower than LearnLib on Abbadingo RPNI training data, and 6.3× slower on the more complex tasks, though the authors call the difference significant but not prohibitive.They attribute the gap mainly to Python’s lower performance than Java and overhead from supporting nondeterministic transitions.Source: §4 · p. 10
  • The framework covers deterministic, observably nondeterministic, or probabilistic IO automata with Mealy- or Moore-style outputs, and learned DFAs with over a thousand states in minutes.The reported DFA example used several hundred thousand traces, PyPy, and an ordinary laptop.Source: §4 · p. 10
  • Future work aims to combine active and passive algorithms and inject domain knowledge, including in low-data scenarios.The authors note that domain knowledge could help generate traces with interesting behavior, such as safety-critical behavior.Source: §4 · p. 11

Appendix

The appendix illustrates adapting state-merging algorithms, including probabilistic and noisy-data examples, and describes a low-data comparison setup.

  • The appendix gives examples illustrating how state-merging algorithms are defined and executed in the tool, then compares implemented algorithms in a low-data scenario; resulting automata appear in Figure 4.Source: Appendix · p. 11
  • IOAlergia learns probabilistic Moore-style automata by testing whether candidate states’ output distributions are sufficiently similar given available data.Its Hoeffding-bound-based compatibility test uses ϵ to control merge aggressiveness and evaluates common futures on the PTA using original transition counts.Source: Appendix · p. 11
  • A modified IOAlergia converts local compatibility into a global score and uses current counts instead of original counts for frequencies.The change invalidates the statistical test’s assumption that samples are independent.Source: Appendix · p. 12
  • Combining IOAlergia with EDSM can overestimate evidence because EDSM scores the resulting partition while IOAlergia checks common futures on the PTA.A stateful ScoreCalculation can track local compatibility evaluations to address the overcounting.Source: Appendix · p. 12
  • For a car alarm, domain knowledge can forbid merging states inferred to represent different physical states, alongside IOAlergia compatibility.The physical state is inferred from the parity of lock and door actions.Source: Appendix · p. 13
  • For deterministic systems with uniformly distributed mislabeled data, the proposed sketch scores partitions using a binomial mismatch probability and rejects scores below a threshold.A post-processing step removes non-dominant transitions to yield a deterministic automaton rather than enforcing determinism during merging.Source: Appendix · pp. 13–14

Comparison of Examples

In the limited-data comparison, the learned models varied in structural fidelity: combining IOAlergia with EDSM and partition evaluation left one mistake, while the noise-aware method recovered the correct car-alarm model.

Comparison of Examples

  • The noise-aware algorithm for deterministic models correctly learned the model of the correct car-alarm system.Source: Comparison of Examples · p. 15
  • Example 7 better approximated the true structure, but a self-transition at the initial state showed it missed the abstract locking-and-door state space.Source: Comparison of Examples · p. 15
  • IOAlergia was off by one state but merged too aggressively, and the algorithm from Example 6 did not improve its result.The passage identifies over-merging as a known low-data problem.Source: Comparison of Examples · p. 15
  • The comparison used 200 randomly generated samples of lengths 10–20, with default ϵ = 0.05 for Alergia-based algorithms.The other algorithm used an estimated 1% error frequency and a 5% significance threshold.Source: Comparison of Examples · p. 15
  • With enough data, the algorithms from Examples 5–8 can learn the faulty system’s correct structure and transition probabilities up to sampling error.Source: Comparison of Examples · p. 15
  • IOAlergia combined with EDSM and partition evaluation produced a model with one mistake, merging the faulty armed state with its correctly functioning counterpart.The domain-knowledge algorithm produced the same result.Source: Comparison of Examples · p. 15, Figure 4 · p. 16

Related papers

Loading 2506.06333v2…