Learning finite state machine specifications from test cases [Elektronische Ressource] / vorgelegt von Edith Benedicta Maria Werner

Edith Werner

Sujets

• Informatik

Informations

• Publié par: georg-august-universitat_gottingen
• Publié le: 01 janvier 2010
• Nombre de lectures: 24
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Learning
FiniteStateMachineSpeciVcations
fromTestCases
Dissertation
zur Erlangung des Doktorgrades
der Mathematisch-Naturwissenschaftlichen Fakultäten
der Georg-August-Universität zu Göttingen
vorgelegt von
Edith Benedicta Maria Werner
aus Nürnberg
Göttingen
im Mai 2010Referent: Prof. Dr. Jens Grabowski,
Universität Göttingen.
Korreferent: Prof. Dr. Stephan Waack,
Universität Göttingen.
Tag der mündlichen Prüfung: 1. Juni 2010Abstract
Up-to-datesoftwaresystemsareoftenmodularandneedtobechangeable. Whilemodu-
larityisbelievedtoreducesoftwareproductioncosts,italsoleadstoincreaseddiXculty
intesting,asthefutureusesofamodulearegettingmorevariedandthereforeharderto
guess. Also, reused modules are often represented as black boxes, whose interior struc-
tureishiddenfromthesystem. Inconsequence,onreusingamodule,thetestingfocuses
on integration testing and monitoring the interfaces of the module.
Inordertomonitorasystem,amodelofthesystemisneededtocomparetheobserved
traces to. However, with the advent of agile development methods and decreasing time
to market, formal models of a system are seldom available. While formal modeling
has not been widely adopted in industry, the importance of testing has increased, in
part thanks to the same agile development methods that obsolete explicit modeling. An
exampleisthetestVrstparadigmofeXtremeProgramming,whichrequiresthatthetests
for any software have to be written before the software itself. Therefore, test cases are
available even for systems without a formal model.
Inconsequence,weproposetogenerateasystemmodelsuitableformonitoringfrom
atestsuiteforthesystem. Theapproachisbasedonautomatalearning. Angluin’slearn-
ing algorithm is used to generate an appropriate model, while state-merging methods
are applied to represent the test cases in a format that can be processed by the learning
algorithm.
BothAngluin’salgorithmandstate-mergingaretailoredtothecharacteristicsoftest-
ing. For algorithm, this comprises a mapping of the query mechanisms onto
a test suite. The state-merging is used to construct a generic representation of arbitrary
testsuitesbyexploitingthepropertiesofagiventestspeciVcationlanguageforabetter
coverage. The approach is implemented in a prototypical tool and validated by a case
study.iiZusammenfassung
Moderne Software-Systeme sind häuVg 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 wer-
den 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äuVg 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).
UmdasSystem-VerhaltenanderbeobachtetenSchnittstellebewertenzukönnen,wird
einformalesModelldesSystemsbenötigt,umdiebeobachtetenEreignisfolgendamitzu
vergleichen. LeidersindformaleModellenurseltenverfügbar,dadurchdieAnwendung
agiler Entwicklungsmethoden und die immer kürzer werdenden Entwicklungszeiten
häuVgkeineformalenModelleerstelltwerden. GleichzeitighatsichdasTestenvonSoft-
ware immer mehr durchgesetzt, so dass für die meisten Software-Systeme eine Samm-
lung 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
basiertaufAnsätzenzummaschinellenLernenvonendlichenAutomaten. EinLernalgo-
rithmus,derzuerstvonDanaAngluinvorgeschlagenwurde,erzeugtdasformaleModell,
währendMethodenzurZustands-VereinigungdieTestfälleineinefürdenLernalgorith-
mus geeignete Datenstruktur umwandeln.
Sowohl der Lernalgorithmus als auch die Methoden zur Zustands-Vereinigung wer-
den 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. DieZustands-VereinigungwirdbenutztumeinegenerischeRepräsentationbe-
liebiger Testfälle zu errechnen, wobei die semantischen Eigenschaften der Testsprache
ausgenutztwerdenumeinebessereÜberdeckungdesZielmodellszuerhalten. Derkom-
binierte Ansatz wird in einem prototypischen Werkzeug implementiert und durch eine
Fallstudie belegt.ivAcknowledgments
Like Alice in Wonderland, the research for this thesis has taken me to various unknown
shoresandtopics. Manyfriendsandcolleagueshaveaccompaniedmealongthepathof
my scientiVc journey, and to all of them I oUer my thanks for their company.
First and foremost, I want to give my thanks to my supervisor, Prof. Dr. Jens
Grabowski. Without his patience and persistence, this thesis would never have been
completed.
I am also very grateful to all colleagues who oUered their advice on this thesis. Franz
Schenk was theVrst one to read my initial eUorts, and his comments on structure have
greatlyeasedmytask. SteUenHerboldprovedtobethepersonwiththemostinsighton
themathematicalfoundationsofmyresearchtopic;thereforehewastheonetospotany
theoreticalinconsistencies. PhilipMakedonskihashelpedtopolishmyEnglishphrasing.
SpecialthanksareduetoProf.Dr.WolfgangMayforhisvaluablecommentsoncorrectly
formulating mathematical deVnitions.
Many grateful thoughts also go to all my friends and family, whose constant support
and never ending inquiries as to the progress of my thesis helped meVnishing it.viContents
1 Introduction 1
1.1 Contribution of this Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Impact . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 StateoftheArt 5
2.1 Synthesis - State Merging Approaches . . . . . . . . . . . . . . . . . . . . 6
2.2 Process Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Induction - State Splitting Approaches . . . . . . . . . . . . . . . . . . . . 8
2.4 Machine Learning Approaches in Testing . . . . . . . . . . . . . . . . . . 9
2.5 ClassiVcation of the Contribution of this Thesis . . . . . . . . . . . . . . 10
3 Foundations 11
3.1 Preliminary DeVnitions and Nomenclature . . . . . . . . . . . . . . . . . 11
3.1.1 Words and Languages . . . . . . . . . . . . . . . . . . . . . . . . 12
3.1.2 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.1.3 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.1.4 Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Automata in System Modeling . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2.1 Communication Protocols . . . . . . . . . . . . . . . . . . . . . . 15
3.2.2 State-based Systems . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2.3 State Machines in UML . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3 Traces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3.1 Automata View . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3.2 System View . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3.3 Reconciliation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4.1 Test Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4.2 Structure-based Testing . . . . . . . . . . . . . . . . . . . . . . . 20
3.4.3 SpeciVcation-based Testing . . . . . . . . . . . . . . . . . . . . . 22
3.4.4 Protocol Conformance Testing . . . . . . . . . . . . . . . . . . . . 24
3.4.5 Monitoring and Passive Testing . . . . . . . . . . . . . . . . . . . 24
3.5 Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
viiContents
3.6 Automata Synthesis with State-Merging . . . . . . . . . . . . . . . . . . . 27
3.7 Learning Finite Automata Using Queries . . . . . . . . . . . . . . . . . . 28
3.7.1 Main Flow of the Learning Algorithm . . . . . . . . . . . . . . . . 28
3.7.2 Minimally Adequate Teacher . . . . . . . . . . . . . . . . . . . . 29
3.7.3 The Learner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4 AdaptationofAngluin’sAlgorithmtoLearningfromTestCases 35
4.1 Analysis of the Learning Algorithm . . . . . . . . . . . . . . . . . . . . . 36
4.1.1 Output of the Algorithm: A Deterministic Finite Automaton . . . 36
4.1.2 Input of the Algorithm: Positive and Negative Examples of the
Target Automaton . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2 Learning from Finite Traces . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2.1 Adaptation of the Teacher . . . . . . . . . . . . . . . . . . . . . . 41
4.2.2 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.2.3 Query Complexity in Relation to the Size of the Test Suite . . . . 47
4.3 Learning from InVnite Tr