From Passive to Active: Learning Timed Automata Efficiently

Bernhard Aichernig; Andrea Pferscher; Martin Tappler

doi:10.1007/978-3-030-55754-6_1

From Passive to Active: Learning Timed Automata Efficiently

Bernhard Aichernig, Andrea Pferscher^*, Martin Tappler

^*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

Model-based testing is a promising technique for quality assurance. In practice, however, a model is not always present. Hence, model learning techniques attain increasing interest. Still, many learning approaches can only learn relatively simple types of models and advanced properties like time are ignored in many cases. In this paper we present an active model learning technique for timed automata. For this, we build upon an existing passive learning technique for real-timed systems. Our goal is to efficiently learn a timed system while simultaneously minimizing the set of training data. For evaluation we compared our active to the passive learning technique based on 43 timed systems with up to 20 locations and multiple clock variables. The results of 18060 experiments show that we require only 100 timed traces to adequately learn a timed system. The new approach is up to 755 times faster.

Original language	English
Title of host publication	NASA Formal Methods - 12th International Symposium, NFM 2020, Proceedings
Subtitle of host publication	12th International Symposium, NFM 2020, Moffett Field, CA, USA, May 11-15, 2020, Proceedings
Editors	Ritchie Lee, Susmit Jha, Anastasia Mavridou
Publisher	Springer
Pages	1-19
Number of pages	19
Volume	12229
ISBN (Print)	978-3-030-55753-9
DOIs	https://doi.org/10.1007/978-3-030-55754-6_1
Publication status	Published - 10 Aug 2020
Event	12th NASA Formal Methods Symposium: NFM 2020 - NASA Ames Research Center, Moffett Field, United States Duration: 12 May 2020 → 14 May 2020 https://ti.arc.nasa.gov/events/nfm-2020/

Publication series

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

Conference

Conference	12th NASA Formal Methods Symposium
Abbreviated title	NFM 2020
Country/Territory	United States
City	Moffett Field
Period	12/05/20 → 14/05/20
Internet address	https://ti.arc.nasa.gov/events/nfm-2020/

Keywords

Active automata learning
Genetic programming
Timed automata
Model learning
Model inference

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Fields of Expertise

Information, Communication & Computing

Access to Document

10.1007/978-3-030-55754-6_1

Cite this

Aichernig, B., Pferscher, A., & Tappler, M. (2020). From Passive to Active: Learning Timed Automata Efficiently. In R. Lee, S. Jha, & A. Mavridou (Eds.), NASA Formal Methods - 12th International Symposium, NFM 2020, Proceedings: 12th International Symposium, NFM 2020, Moffett Field, CA, USA, May 11-15, 2020, Proceedings (Vol. 12229, pp. 1-19). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12229 LNCS). Springer. https://doi.org/10.1007/978-3-030-55754-6_1

From Passive to Active: Learning Timed Automata Efficiently. / Aichernig, Bernhard; Pferscher, Andrea; Tappler, Martin.
NASA Formal Methods - 12th International Symposium, NFM 2020, Proceedings: 12th International Symposium, NFM 2020, Moffett Field, CA, USA, May 11-15, 2020, Proceedings. ed. / Ritchie Lee; Susmit Jha; Anastasia Mavridou. Vol. 12229 Springer, 2020. p. 1-19 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12229 LNCS).

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

Aichernig, B, Pferscher, A & Tappler, M 2020, From Passive to Active: Learning Timed Automata Efficiently. in R Lee, S Jha & A Mavridou (eds), NASA Formal Methods - 12th International Symposium, NFM 2020, Proceedings: 12th International Symposium, NFM 2020, Moffett Field, CA, USA, May 11-15, 2020, Proceedings. vol. 12229, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12229 LNCS, Springer, pp. 1-19, 12th NASA Formal Methods Symposium, Moffett Field, California, United States, 12/05/20. https://doi.org/10.1007/978-3-030-55754-6_1

Aichernig B, Pferscher A, Tappler M. From Passive to Active: Learning Timed Automata Efficiently. In Lee R, Jha S, Mavridou A, editors, NASA Formal Methods - 12th International Symposium, NFM 2020, Proceedings: 12th International Symposium, NFM 2020, Moffett Field, CA, USA, May 11-15, 2020, Proceedings. Vol. 12229. Springer. 2020. p. 1-19. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-55754-6_1

Aichernig, Bernhard ; Pferscher, Andrea ; Tappler, Martin. / From Passive to Active: Learning Timed Automata Efficiently. NASA Formal Methods - 12th International Symposium, NFM 2020, Proceedings: 12th International Symposium, NFM 2020, Moffett Field, CA, USA, May 11-15, 2020, Proceedings. editor / Ritchie Lee ; Susmit Jha ; Anastasia Mavridou. Vol. 12229 Springer, 2020. pp. 1-19 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6ede2f9cf74147c79262d65897451e50,

title = "From Passive to Active: Learning Timed Automata Efficiently",

abstract = "Model-based testing is a promising technique for quality assurance. In practice, however, a model is not always present. Hence, model learning techniques attain increasing interest. Still, many learning approaches can only learn relatively simple types of models and advanced properties like time are ignored in many cases. In this paper we present an active model learning technique for timed automata. For this, we build upon an existing passive learning technique for real-timed systems. Our goal is to efficiently learn a timed system while simultaneously minimizing the set of training data. For evaluation we compared our active to the passive learning technique based on 43 timed systems with up to 20 locations and multiple clock variables. The results of 18060 experiments show that we require only 100 timed traces to adequately learn a timed system. The new approach is up to 755 times faster.",

keywords = "Active automata learning, Genetic programming, Timed automata, Model learning, Model inference",

author = "Bernhard Aichernig and Andrea Pferscher and Martin Tappler",

year = "2020",

month = aug,

day = "10",

doi = "10.1007/978-3-030-55754-6_1",

language = "English",

isbn = "978-3-030-55753-9",

volume = "12229",

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

publisher = "Springer",

pages = "1--19",

editor = "Ritchie Lee and Susmit Jha and Anastasia Mavridou",

booktitle = "NASA Formal Methods - 12th International Symposium, NFM 2020, Proceedings",

note = "12th NASA Formal Methods Symposium : NFM 2020, NFM 2020 ; Conference date: 12-05-2020 Through 14-05-2020",

url = "https://ti.arc.nasa.gov/events/nfm-2020/",

}

TY - GEN

T1 - From Passive to Active: Learning Timed Automata Efficiently

AU - Aichernig, Bernhard

AU - Pferscher, Andrea

AU - Tappler, Martin

PY - 2020/8/10

Y1 - 2020/8/10

N2 - Model-based testing is a promising technique for quality assurance. In practice, however, a model is not always present. Hence, model learning techniques attain increasing interest. Still, many learning approaches can only learn relatively simple types of models and advanced properties like time are ignored in many cases. In this paper we present an active model learning technique for timed automata. For this, we build upon an existing passive learning technique for real-timed systems. Our goal is to efficiently learn a timed system while simultaneously minimizing the set of training data. For evaluation we compared our active to the passive learning technique based on 43 timed systems with up to 20 locations and multiple clock variables. The results of 18060 experiments show that we require only 100 timed traces to adequately learn a timed system. The new approach is up to 755 times faster.

AB - Model-based testing is a promising technique for quality assurance. In practice, however, a model is not always present. Hence, model learning techniques attain increasing interest. Still, many learning approaches can only learn relatively simple types of models and advanced properties like time are ignored in many cases. In this paper we present an active model learning technique for timed automata. For this, we build upon an existing passive learning technique for real-timed systems. Our goal is to efficiently learn a timed system while simultaneously minimizing the set of training data. For evaluation we compared our active to the passive learning technique based on 43 timed systems with up to 20 locations and multiple clock variables. The results of 18060 experiments show that we require only 100 timed traces to adequately learn a timed system. The new approach is up to 755 times faster.

KW - Active automata learning

KW - Genetic programming

KW - Timed automata

KW - Model learning

KW - Model inference

UR - http://www.scopus.com/inward/record.url?scp=85089722566&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-55754-6_1

DO - 10.1007/978-3-030-55754-6_1

M3 - Conference paper

SN - 978-3-030-55753-9

VL - 12229

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

SP - 1

EP - 19

BT - NASA Formal Methods - 12th International Symposium, NFM 2020, Proceedings

A2 - Lee, Ritchie

A2 - Jha, Susmit

A2 - Mavridou, Anastasia

PB - Springer

T2 - 12th NASA Formal Methods Symposium

Y2 - 12 May 2020 through 14 May 2020

ER -

From Passive to Active: Learning Timed Automata Efficiently

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Fields of Expertise

Access to Document

Other files and links

Fingerprint

Dependable Internet of Things

Cite this

From Passive to Active: Learning Timed Automata Efficiently

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Fields of Expertise

Access to Document

Other files and links

Fingerprint

Projects

Dependable Internet of Things

Cite this