Time to Learn - Learning Timed Automata from Tests

Martin Tappler, Bernhard K. Aichernig, Kim Guldstrand Larsen, Florian Lorber

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

Abstract

Model learning has gained increasing interest in recent years. It derives behavioural models from test data of black-box systems. The main advantage offered by such techniques is that they enable model-based analysis without access to the internals of a system. Applications range from fully automated testing over model checking to system understanding. Current work focuses on learning variations of finite state machines. However, most techniques consider discrete time. In this paper, we present a novel method for learning timed automata, finite state machines extended with real-valued clocks. The learning method generates a model consistent with a set of timed traces collected via testing. This generation is based on genetic programming, a search-based technique for automatic program creation. We evaluate our approach on 44 timed systems, comprised of four systems from the literature (two industrial and two academic) and 40 randomly generated examples.
Original languageEnglish
Title of host publicationFormal Modeling and Analysis of Timed Systems - 17th International Conference, FORMATS 2019, Proceedings
EditorsÉtienne André, Mariëlle Stoelinga, Mariëlle Stoelinga
Number of pages20
Place of PublicationHeidelberg
PublisherSpringer
Publication dateAug 2019
Pages216-235
ISBN (Print)978-3-030-29661-2
ISBN (Electronic)978-3-030-29662-9
DOIs
Publication statusPublished - Aug 2019
Event17th FORMATS 2019: Amsterdam, The Netherlands - Amsterdam, Netherlands
Duration: 26 Aug 201931 Aug 2019

Conference

Conference17th FORMATS 2019: Amsterdam, The Netherlands
CountryNetherlands
CityAmsterdam
Period26/08/201931/08/2019
SeriesLecture Notes in Computer Science
Volume11750
ISSN0302-9743

Fingerprint

Finite automata
Genetic programming
Model checking
Testing
Clocks

Cite this

Tappler, M., Aichernig, B. K., Larsen, K. G., & Lorber, F. (2019). Time to Learn - Learning Timed Automata from Tests. In É. André, M. Stoelinga, & M. Stoelinga (Eds.), Formal Modeling and Analysis of Timed Systems - 17th International Conference, FORMATS 2019, Proceedings (pp. 216-235). Heidelberg: Springer. Lecture Notes in Computer Science, Vol.. 11750 https://doi.org/10.1007/978-3-030-29662-9_13
Tappler, Martin ; Aichernig, Bernhard K. ; Larsen, Kim Guldstrand ; Lorber, Florian. / Time to Learn - Learning Timed Automata from Tests. Formal Modeling and Analysis of Timed Systems - 17th International Conference, FORMATS 2019, Proceedings. editor / Étienne André ; Mariëlle Stoelinga ; Mariëlle Stoelinga. Heidelberg : Springer, 2019. pp. 216-235 (Lecture Notes in Computer Science, Vol. 11750).
@inproceedings{b7b7cbbd7b384e41ad45d47b1db0230f,
title = "Time to Learn - Learning Timed Automata from Tests",
abstract = "Model learning has gained increasing interest in recent years. It derives behavioural models from test data of black-box systems. The main advantage offered by such techniques is that they enable model-based analysis without access to the internals of a system. Applications range from fully automated testing over model checking to system understanding. Current work focuses on learning variations of finite state machines. However, most techniques consider discrete time. In this paper, we present a novel method for learning timed automata, finite state machines extended with real-valued clocks. The learning method generates a model consistent with a set of timed traces collected via testing. This generation is based on genetic programming, a search-based technique for automatic program creation. We evaluate our approach on 44 timed systems, comprised of four systems from the literature (two industrial and two academic) and 40 randomly generated examples.",
author = "Martin Tappler and Aichernig, {Bernhard K.} and Larsen, {Kim Guldstrand} and Florian Lorber",
year = "2019",
month = "8",
doi = "10.1007/978-3-030-29662-9_13",
language = "English",
isbn = "978-3-030-29661-2",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "216--235",
editor = "{\'E}tienne Andr{\'e} and Mari{\"e}lle Stoelinga and Mari{\"e}lle Stoelinga",
booktitle = "Formal Modeling and Analysis of Timed Systems - 17th International Conference, FORMATS 2019, Proceedings",
address = "Germany",

}

Tappler, M, Aichernig, BK, Larsen, KG & Lorber, F 2019, Time to Learn - Learning Timed Automata from Tests. in É André, M Stoelinga & M Stoelinga (eds), Formal Modeling and Analysis of Timed Systems - 17th International Conference, FORMATS 2019, Proceedings. Springer, Heidelberg, Lecture Notes in Computer Science, vol. 11750, pp. 216-235, 17th FORMATS 2019: Amsterdam, The Netherlands, Amsterdam, Netherlands, 26/08/2019. https://doi.org/10.1007/978-3-030-29662-9_13

Time to Learn - Learning Timed Automata from Tests. / Tappler, Martin; Aichernig, Bernhard K.; Larsen, Kim Guldstrand; Lorber, Florian.

Formal Modeling and Analysis of Timed Systems - 17th International Conference, FORMATS 2019, Proceedings. ed. / Étienne André; Mariëlle Stoelinga; Mariëlle Stoelinga. Heidelberg : Springer, 2019. p. 216-235 (Lecture Notes in Computer Science, Vol. 11750).

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

TY - GEN

T1 - Time to Learn - Learning Timed Automata from Tests

AU - Tappler, Martin

AU - Aichernig, Bernhard K.

AU - Larsen, Kim Guldstrand

AU - Lorber, Florian

PY - 2019/8

Y1 - 2019/8

N2 - Model learning has gained increasing interest in recent years. It derives behavioural models from test data of black-box systems. The main advantage offered by such techniques is that they enable model-based analysis without access to the internals of a system. Applications range from fully automated testing over model checking to system understanding. Current work focuses on learning variations of finite state machines. However, most techniques consider discrete time. In this paper, we present a novel method for learning timed automata, finite state machines extended with real-valued clocks. The learning method generates a model consistent with a set of timed traces collected via testing. This generation is based on genetic programming, a search-based technique for automatic program creation. We evaluate our approach on 44 timed systems, comprised of four systems from the literature (two industrial and two academic) and 40 randomly generated examples.

AB - Model learning has gained increasing interest in recent years. It derives behavioural models from test data of black-box systems. The main advantage offered by such techniques is that they enable model-based analysis without access to the internals of a system. Applications range from fully automated testing over model checking to system understanding. Current work focuses on learning variations of finite state machines. However, most techniques consider discrete time. In this paper, we present a novel method for learning timed automata, finite state machines extended with real-valued clocks. The learning method generates a model consistent with a set of timed traces collected via testing. This generation is based on genetic programming, a search-based technique for automatic program creation. We evaluate our approach on 44 timed systems, comprised of four systems from the literature (two industrial and two academic) and 40 randomly generated examples.

U2 - 10.1007/978-3-030-29662-9_13

DO - 10.1007/978-3-030-29662-9_13

M3 - Article in proceeding

SN - 978-3-030-29661-2

T3 - Lecture Notes in Computer Science

SP - 216

EP - 235

BT - Formal Modeling and Analysis of Timed Systems - 17th International Conference, FORMATS 2019, Proceedings

A2 - André, Étienne

A2 - Stoelinga, Mariëlle

A2 - Stoelinga, Mariëlle

PB - Springer

CY - Heidelberg

ER -

Tappler M, Aichernig BK, Larsen KG, Lorber F. Time to Learn - Learning Timed Automata from Tests. In André É, Stoelinga M, Stoelinga M, editors, Formal Modeling and Analysis of Timed Systems - 17th International Conference, FORMATS 2019, Proceedings. Heidelberg: Springer. 2019. p. 216-235. (Lecture Notes in Computer Science, Vol. 11750). https://doi.org/10.1007/978-3-030-29662-9_13