Learning Abstracted Non-deterministic Finite State Machines

Andrea Pferscher; Bernhard Aichernig

doi:10.1007/978-3-030-64881-7_4

Learning Abstracted Non-deterministic Finite State Machines

Andrea Pferscher^*
, Bernhard Aichernig

^*Corresponding author for this work

Institute of Software Engineering and Artificial Intelligence (7160)

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Abstract

Active automata learning gains increasing interest since it gives an insight into the behavior of a black-box system. A crucial drawback of the frequently used learning algorithms based on Angluin’s L ^∗ is that they become impractical if systems with a large input/output alphabet are learned. Previous work suggested to circumvent this problem by abstracting the input alphabet and the observed outputs. However, abstraction could introduce non-deterministic behavior. Already existing active automata learning algorithms for observable non-deterministic systems learn larger models if outputs are only observable after certain input/output sequences. In this paper, we introduce an abstraction scheme that merges akin states. Hence, we learn a more generic behavioral model of a black-box system. Furthermore, we evaluate our algorithm in a practical case study. In this case study, we learn the behavior of five different Message Queuing Telemetry Transport (mqtt) brokers interacting with multiple clients.

Original language	English
Title of host publication	Testing Software and Systems - 32nd IFIP WG 6.1 International Conference, ICTSS 2020, Proceedings
Subtitle of host publication	32nd IFIP WG 6.1 International Conference, ICTSS 2020, Naples, Italy, December 9-11, 2020, Proceedings
Editors	Valentina Casola, Alessandra De Benedictis, Massimiliano Rak
Publisher	Springer
Pages	52-69
Number of pages	18
Volume	12543
ISBN (Print)	978-3-030-64880-0
DOIs	https://doi.org/10.1007/978-3-030-64881-7_4
Publication status	Published - Dec 2020
Event	32nd IFIP International Conference on Testing Software and Systems: ICTSS 2020 - Virtuell, Italy Duration: 9 Dec 2020 → 11 Dec 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12543 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	32nd IFIP International Conference on Testing Software and Systems
Abbreviated title	IFIP-ICTSS 2020
Country/Territory	Italy
City	Virtuell
Period	9/12/20 → 11/12/20

Keywords

Active automata learning
Model inference
Non-deterministic finite state machines
MQTT

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Fields of Expertise

Information, Communication & Computing

Access to Document

10.1007/978-3-030-64881-7_4

Cite this

Pferscher, A., & Aichernig, B. (2020). Learning Abstracted Non-deterministic Finite State Machines. In V. Casola, A. De Benedictis, & M. Rak (Eds.), Testing Software and Systems - 32nd IFIP WG 6.1 International Conference, ICTSS 2020, Proceedings: 32nd IFIP WG 6.1 International Conference, ICTSS 2020, Naples, Italy, December 9-11, 2020, Proceedings (Vol. 12543, pp. 52-69). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12543 LNCS). Springer. https://doi.org/10.1007/978-3-030-64881-7_4

Learning Abstracted Non-deterministic Finite State Machines. / Pferscher, Andrea; Aichernig, Bernhard.
Testing Software and Systems - 32nd IFIP WG 6.1 International Conference, ICTSS 2020, Proceedings: 32nd IFIP WG 6.1 International Conference, ICTSS 2020, Naples, Italy, December 9-11, 2020, Proceedings. ed. / Valentina Casola; Alessandra De Benedictis; Massimiliano Rak. Vol. 12543 Springer, 2020. p. 52-69 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12543 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Pferscher, A & Aichernig, B 2020, Learning Abstracted Non-deterministic Finite State Machines. in V Casola, A De Benedictis & M Rak (eds), Testing Software and Systems - 32nd IFIP WG 6.1 International Conference, ICTSS 2020, Proceedings: 32nd IFIP WG 6.1 International Conference, ICTSS 2020, Naples, Italy, December 9-11, 2020, Proceedings. vol. 12543, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12543 LNCS, Springer, pp. 52-69, 32nd IFIP International Conference on Testing Software and Systems, Virtuell, Italy, 9/12/20. https://doi.org/10.1007/978-3-030-64881-7_4

Pferscher A, Aichernig B. Learning Abstracted Non-deterministic Finite State Machines. In Casola V, De Benedictis A, Rak M, editors, Testing Software and Systems - 32nd IFIP WG 6.1 International Conference, ICTSS 2020, Proceedings: 32nd IFIP WG 6.1 International Conference, ICTSS 2020, Naples, Italy, December 9-11, 2020, Proceedings. Vol. 12543. Springer. 2020. p. 52-69. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-64881-7_4

Pferscher, Andrea ; Aichernig, Bernhard. / Learning Abstracted Non-deterministic Finite State Machines. Testing Software and Systems - 32nd IFIP WG 6.1 International Conference, ICTSS 2020, Proceedings: 32nd IFIP WG 6.1 International Conference, ICTSS 2020, Naples, Italy, December 9-11, 2020, Proceedings. editor / Valentina Casola ; Alessandra De Benedictis ; Massimiliano Rak. Vol. 12543 Springer, 2020. pp. 52-69 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b585262359a640f2a047b99a13c41fc6,

title = "Learning Abstracted Non-deterministic Finite State Machines",

abstract = "Active automata learning gains increasing interest since it gives an insight into the behavior of a black-box system. A crucial drawback of the frequently used learning algorithms based on Angluin{\textquoteright}s L ∗ is that they become impractical if systems with a large input/output alphabet are learned. Previous work suggested to circumvent this problem by abstracting the input alphabet and the observed outputs. However, abstraction could introduce non-deterministic behavior. Already existing active automata learning algorithms for observable non-deterministic systems learn larger models if outputs are only observable after certain input/output sequences. In this paper, we introduce an abstraction scheme that merges akin states. Hence, we learn a more generic behavioral model of a black-box system. Furthermore, we evaluate our algorithm in a practical case study. In this case study, we learn the behavior of five different Message Queuing Telemetry Transport (mqtt) brokers interacting with multiple clients. ",

keywords = "Active automata learning, Model inference, Non-deterministic finite state machines, MQTT",

author = "Andrea Pferscher and Bernhard Aichernig",

year = "2020",

month = dec,

doi = "10.1007/978-3-030-64881-7\_4",

language = "English",

isbn = "978-3-030-64880-0",

volume = "12543",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "52--69",

editor = "Valentina Casola and \{De Benedictis\}, Alessandra and Massimiliano Rak",

booktitle = "Testing Software and Systems - 32nd IFIP WG 6.1 International Conference, ICTSS 2020, Proceedings",

address = "United States",

note = "32nd IFIP International Conference on Testing Software and Systems : ICTSS 2020, IFIP-ICTSS 2020 ; Conference date: 09-12-2020 Through 11-12-2020",

}

TY - GEN

T1 - Learning Abstracted Non-deterministic Finite State Machines

AU - Pferscher, Andrea

AU - Aichernig, Bernhard

PY - 2020/12

Y1 - 2020/12

N2 - Active automata learning gains increasing interest since it gives an insight into the behavior of a black-box system. A crucial drawback of the frequently used learning algorithms based on Angluin’s L ∗ is that they become impractical if systems with a large input/output alphabet are learned. Previous work suggested to circumvent this problem by abstracting the input alphabet and the observed outputs. However, abstraction could introduce non-deterministic behavior. Already existing active automata learning algorithms for observable non-deterministic systems learn larger models if outputs are only observable after certain input/output sequences. In this paper, we introduce an abstraction scheme that merges akin states. Hence, we learn a more generic behavioral model of a black-box system. Furthermore, we evaluate our algorithm in a practical case study. In this case study, we learn the behavior of five different Message Queuing Telemetry Transport (mqtt) brokers interacting with multiple clients.

AB - Active automata learning gains increasing interest since it gives an insight into the behavior of a black-box system. A crucial drawback of the frequently used learning algorithms based on Angluin’s L ∗ is that they become impractical if systems with a large input/output alphabet are learned. Previous work suggested to circumvent this problem by abstracting the input alphabet and the observed outputs. However, abstraction could introduce non-deterministic behavior. Already existing active automata learning algorithms for observable non-deterministic systems learn larger models if outputs are only observable after certain input/output sequences. In this paper, we introduce an abstraction scheme that merges akin states. Hence, we learn a more generic behavioral model of a black-box system. Furthermore, we evaluate our algorithm in a practical case study. In this case study, we learn the behavior of five different Message Queuing Telemetry Transport (mqtt) brokers interacting with multiple clients.

KW - Active automata learning

KW - Model inference

KW - Non-deterministic finite state machines

KW - MQTT

UR - https://www.scopus.com/pages/publications/85097833821

U2 - 10.1007/978-3-030-64881-7_4

DO - 10.1007/978-3-030-64881-7_4

M3 - Conference paper

SN - 978-3-030-64880-0

VL - 12543

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 52

EP - 69

BT - Testing Software and Systems - 32nd IFIP WG 6.1 International Conference, ICTSS 2020, Proceedings

A2 - Casola, Valentina

A2 - De Benedictis, Alessandra

A2 - Rak, Massimiliano

PB - Springer

T2 - 32nd IFIP International Conference on Testing Software and Systems

Y2 - 9 December 2020 through 11 December 2020

ER -

Learning Abstracted Non-deterministic Finite State Machines

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Fields of Expertise

Access to Document

Other files and links

Dependable Internet of Things

Cite this

Learning Abstracted Non-deterministic Finite State Machines

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Fields of Expertise

Access to Document

Other files and links

Projects

Dependable Internet of Things

Cite this