Skip to main content

An active automata learning library

Project description

AALpy

An Active Automata Learning Library

Python application CodeQL PyPI - Downloads

GitHub issues GitHub pull requests Python 3.6 PyPI - Wheel Binder Maintenance License: MIT


AALpy is a light-weight active automata learning library written in pure Python. You can start learning automata in just a few lines of code.

Whether you work with regular languages or you would like to learn models of (black-box) reactive systems, AALpy supports a wide range of modeling formalisms, including deterministic, non-deterministic, and stochastic automata.

Automata Type Supported Formalisms Features
Deterministic Deterministic Finite Automata
Mealy Machines
Moore Machines
Counterexample Processing
Seamless Caching
11 Equivalence Oracles
Passive learning of all formalisms
Non-Deterministic Observable Non-Deterministic FSM
Abstracted Non-Deterministic FSM
Dynamic Observation Table Updates
Size Reduction Trough Abstraction
Stochastic Markov Decision Processes
Stochastic Mealy Machines
Markov Chains
Counterexample Processing
Row/Cell Compatability Metrics
Model Checking with PRISM
Alergia Passive Learning

AALpy enables efficient learning by providing a large set of equivalence oracles, implementing various conformance testing strategies. Learning is mostly based on Angluin's L* algorithm, for which AALpy supports a selection of optimizations, including efficient counterexample processing and caching.

AALpy also includes passive automata learning algorithms. Unlike active algorithms which learn by interaction with the system, passive learning algorithms construct a model based on provided data. AALpy includes an implementation of RPNI, a passive deterministic automata learning algorithm that constructs a model that conforms to the provided data. AALpy also has an efficient implementation of the ALERGIA algorithm, suited for passive learning of Markov Chains, Markov Decision processes, and Stochastic Mealy Machines. For more efficient ALERGIA execution, AALpy offers bindings to jAlergia, a Java twin of AALpy's ALERGIA code.

Installation

Use the package manager pip to install AALpy.

pip install aalpy

The minimum required version of Python is 3.6.
Ensure that you have Graphviz installed and added to your path if you want to visualize models.

For manual installation, clone the master and install the following dependency.

pip install pydot
# and to install the library
python setup.py install

Documentation and Wiki

If you are interested in automata learning or would like to understand the automata learning process in more detail, please check out our Wiki. On Wiki, you will find more detailed examples on how to use AALpy.

For the official documentation of all classes and methods, check out:

Interactive examples can be found in the notebooks folder. If you would like to interact/change those examples in the browser, click here. (Navigate to the notebooks folder and select one notebook)

Examples.py contains many examples and it is a great starting point.

Usage

All automata learning procedures follow this high-level approach:

For more detailed examples, check out:

Examples.py contains examples covering almost the whole AALpy's functionality, and it is a great starting point/reference. Wiki has a step-by-step guide to using AALpy and can help you understand AALpy and automata learning in general.

The following snippet demonstrates a short example in which an automaton is either loaded or randomly generated and then learned.

from aalpy.utils import load_automaton_from_file, save_automaton_to_file, visualize_automaton, generate_random_dfa, dfa_from_state_setup
from aalpy.SULs import DfaSUL
from aalpy.oracles import RandomWalkEqOracle
from aalpy.learning_algs import run_Lstar

# load an automaton
# automaton = load_automaton_from_file('path_to_the_file.dot', automaton_type='dfa')

# or construct it from state setup
dfa_state_setup = {
    'q0': (True, {'a': 'q1', 'b': 'q2'}),
    'q1': (False, {'a': 'q0', 'b': 'q3'}),
    'q2': (False, {'a': 'q3', 'b': 'q0'}),
    'q3': (False, {'a': 'q2', 'b': 'q1'})
}

small_dfa = dfa_from_state_setup(dfa_state_setup)

# or randomly generate one
random_dfa = generate_random_dfa(alphabet=[1,2,3,4,5],num_states=20, num_accepting_states=8)
big_random_dfa = generate_random_dfa(alphabet=[1,2,3,4,5],num_states=2000, num_accepting_states=500)

# get input alphabet of the automaton
alphabet = random_dfa.get_input_alphabet()

# loaded or randomly generated automata are considered as BLACK-BOX that is queried
# learning algorithm has no knowledge about its structure
# create a SUL instance for the automaton/system under learning
sul = DfaSUL(random_dfa)

# define the equivalence oracle
eq_oracle = RandomWalkEqOracle(alphabet, sul, num_steps=5000, reset_prob=0.09)

# start learning
learned_dfa = run_Lstar(alphabet, sul, eq_oracle, automaton_type='dfa')

# save automaton to file and visualize it
# save_automaton_to_file(learned_dfa, path='Learned_Automaton', file_type='dot')
# or
learned_dfa.save()

# visualize automaton
# visualize_automaton(learned_dfa)
learned_dfa.visualize()
# or just print its DOT representation
print(learned_dfa)

To make experiments reproducible, define a random seed at the beginning of your program.

from random import seed
seed(2) # all experiments will be reproducible

Selected Applications

AALpy has been used to:

Cite AALpy and Research Contact

If you use AALpy in your research, please cite:

@inproceedings{aalpy,
	title = {{AALpy}: An Active Automata Learning Library},
	author = {Edi Mu\v{s}kardin and Bernhard K. Aichernig and Ingo Pill and Andrea Pferscher and Martin Tappler},
	booktitle = {Automated Technology for Verification and Analysis - 19th International
	Symposium, {ATVA} 2021, Gold Coast, Australia, October 18-22, 2021, Proceedings},
	series    = {Lecture Notes in Computer Science},  
	publisher = {Springer},
	year      = {2021},
}

If you have research suggestions or you need specific help concerning your research, feel free to start a discussion or contact edi.muskardin@silicon-austria.com. We are happy to help you and consult you in applying automata learning in various domains.

Contributing

Pull requests are welcome. For significant changes, please open an issue first to discuss what you would like to change. In case of any questions or possible bugs, please open issues.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distributions

No source distribution files available for this release.See tutorial on generating distribution archives.

Built Distribution

aalpy-1.2.7-py3-none-any.whl (97.1 kB view hashes)

Uploaded Python 3

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page