Learning Finite State Machine Specifications from Test Cases

Abstract

Moderne Software-Systeme sind häufig modular aufgebaut, müssen dabei aber Ansprüchen an Wartbarkeit und Änderbarkeit genügen. Während man einerseits annimmt, dass modulare Software mit geringerem Kostenaufwand hergestellt werden kann, wird andererseits die Komplexität des Testens erhöht, da die zukünftigen Anwendungen eines Moduls sich nur schwer vorhersagen lassen. Dazu kommt, dass Module häufig als abgeschlossene Bausteine wiederverwendet werden, so dass die innere Struktur der Module dem System verborgen bleibt. Daher konzentriert sich der Test eines wiederverwendeten Moduls oft auf den Integrationstest und das Beobachten der Schnittstellen des Moduls (Monitoring).Um das System-Verhalten an der beobachteten Schnittstelle bewerten zu können, wird ein formales Modell des Systems benötigt, um die beobachteten Ereignisfolgen damit zu vergleichen. Leider sind formale Modelle nur selten verfügbar, da durch die Anwendung agiler Entwicklungsmethoden und die immer kürzer werdenden Entwicklungszeiten häufig keine formalen Modelle erstellt werden. Gleichzeitig hat sich das Testen von Software immer mehr durchgesetzt, so dass für die meisten Software-Systeme eine Sammlung von Testfällen vorliegt.Die vorliegende Arbeit schlägt eine Methode vor, mit deren Hilfe aus den Testfällen eines Software-Systems ein formales Modell errechnet werden kann. Die Methode basiert auf Ansätzen zum maschinellen Lernen von endlichen Automaten. Ein Lernalgorithmus, der zuerst von Dana Angluin vorgeschlagen wurde, erzeugt das formale Modell, während Methoden zur Zustands-Vereinigung die Testfälle in eine für den Lernalgorithmus geeignete Datenstruktur umwandeln.Sowohl der Lernalgorithmus als auch die Methoden zur Zustands-Vereinigung werden an die Eigenschaften des Testens angepasst. Für den Lernalgorithmus von Dana Angluin bedeutet das, dass die Fragemechanismen auf die Testfälle abgebildet werden müssen. Die Zustands-Vereinigung wird benutzt um eine generische Repräsentation beliebiger Testfälle zu errechnen, wobei die semantischen Eigenschaften der Testsprache ausgenutzt werden um eine bessere Überdeckung des Zielmodells zu erhalten. Der kombinierte Ansatz wird in einem prototypischen Werkzeug implementiert und durch eine Fallstudie belegt.