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

^*Korrespondierende/r Autor/-in für diese Arbeit

Institute of Software Engineering and Artificial Intelligence (7160)

Publikation: Beitrag in Buch/Bericht/Konferenzband › Beitrag in einem Konferenzband › Begutachtung

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.

Originalsprache	englisch
Titel	Testing Software and Systems - 32nd IFIP WG 6.1 International Conference, ICTSS 2020, Proceedings
Untertitel	32nd IFIP WG 6.1 International Conference, ICTSS 2020, Naples, Italy, December 9-11, 2020, Proceedings
Redakteure/-innen	Valentina Casola, Alessandra De Benedictis, Massimiliano Rak
Herausgeber (Verlag)	Springer
Seiten	52-69
Seitenumfang	18
Band	12543
ISBN (Print)	978-3-030-64880-0
DOIs	https://doi.org/10.1007/978-3-030-64881-7_4
Publikationsstatus	Veröffentlicht - Dez. 2020
Veranstaltung	32nd IFIP International Conference on Testing Software and Systems: ICTSS 2020 - Virtuell, Italien Dauer: 9 Dez. 2020 → 11 Dez. 2020

Publikationsreihe

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

Konferenz

Konferenz	32nd IFIP International Conference on Testing Software and Systems
Kurztitel	IFIP-ICTSS 2020
Land/Gebiet	Italien
Ort	Virtuell
Zeitraum	9/12/20 → 11/12/20

ASJC Scopus subject areas

Theoretische Informatik
Allgemeine Computerwissenschaft

Fields of Expertise

Information, Communication & Computing

Zugriff auf Dokument

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

Andere Dateien und Links

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

1 Abgeschlossen

Verlaesslichkeit im Internet der Dinge
Pernkopf, F. (Kontaktperson), Zakany, N. (Kontaktperson), Eichlseder, M. (Kontaktperson), Saukh, O. (Kontaktperson), Mangard, S. (Kontaktperson), Steinbauer-Wagner, G. (Kontaktperson), Knoll, C. (Teilnehmer / Mitarbeiter), Tranninger, M. (Teilnehmer / Mitarbeiter), Römer, K. U. (Konsortialführer/in bzw. Koordinator/in von mehreren TU Graz Instituten), Rath, M. (Teilnehmer / Mitarbeiter), Kubin, G. (Kontaktperson), Horn, M. (Kontaktperson), Tappler, M. (Teilnehmer / Mitarbeiter), Bloem, R. (Konsortialführer/in bzw. Koordinator/in von mehreren TU Graz Instituten), Weiser, S. (Teilnehmer / Mitarbeiter), Leitinger, E. (Kontaktperson), Ebrahimi, M. (Teilnehmer / Mitarbeiter), Aichernig, B. (Kontaktperson), Malenko, M. (Teilnehmer / Mitarbeiter), Steinberger, M. (Kontaktperson), Großwindhager, B. (Teilnehmer / Mitarbeiter), Baunach, M. C. (Kontaktperson), Witrisal, K. (Kontaktperson), Teschl, R. (Kontaktperson), Boano, C. A. (Kontaktperson), Alothman Alterkawi, A. B. (Teilnehmer / Mitarbeiter), Bösch, W. (Kontaktperson) & Grosinger, J. (Kontaktperson)
1/01/16 → 31/03/22
Projekt: Forschungsprojekt

Dieses zitieren

Pferscher, A., & Aichernig, B. (2020). Learning Abstracted Non-deterministic Finite State Machines. in V. Casola, A. De Benedictis, & M. Rak (Hrsg.), 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 (Band 12543, S. 52-69). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 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. Hrsg. / Valentina Casola; Alessandra De Benedictis; Massimiliano Rak. Band 12543 Springer, 2020. S. 52-69 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 12543 LNCS).

Publikation: Beitrag in Buch/Bericht/Konferenzband › Beitrag in einem Konferenzband › Begutachtung

Pferscher, A & Aichernig, B 2020, Learning Abstracted Non-deterministic Finite State Machines. in V Casola, A De Benedictis & M Rak (Hrsg.), 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. Bd. 12543, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bd. 12543 LNCS, Springer, S. 52-69, 32nd IFIP International Conference on Testing Software and Systems, Virtuell, Italien, 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, Hrsg., 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. Band 12543. Springer. 2020. S. 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. Hrsg. / Valentina Casola ; Alessandra De Benedictis ; Massimiliano Rak. Band 12543 Springer, 2020. S. 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

Publikationsreihe

Konferenz

ASJC Scopus subject areas

Fields of Expertise

Zugriff auf Dokument

Andere Dateien und Links

Projekte

Verlaesslichkeit im Internet der Dinge

Dieses zitieren