1 Molecular Biology 3M03 Fundamental Concepts of Development ...

Statistical Procedures for Certification of
Software SystemsTHOMASSTIELTJESINSTITUTE
FORMATHEMATICS
c Corro Ramos, Isaac (2009)
A catalogue record is available from the Eindhoven University of Technology Library
ISBN: 978-90-386-2098-5
NUR: 916
Subject headings: Bayesian statistics, reliability growth models, sequential testing,
software release, software reliability, software testing, stopping time, transition sys-
tems
Mathematics Subject Classification: 62L10, 62L15, 68M15
Printed by Printservice TU/e
Cover design by Paul Verspaget
This research was supported by the Netherlands Organisation for Scientific Research
(NWO) under project number 617.023.047.Statistical Procedures for Certification of
Software Systems
proefschrift
ter verkrijging van de graad van doctor aan de
Technische Universiteit Eindhoven, op gezag van de
Rector Magnificus, prof.dr.ir. C.J. van Duijn, voor een
commissie aangewezen door het College voor
Promoties in het openbaar te verdedigen
op dinsdag 15 december 2009 om 16.00 uur
door
Isaac Corro Ramos
geboren te Sevilla, SpanjeDit proefschrift is goedgekeurd door de promotoren:
prof.dr. K.M. van Hee
en
prof.dr. R.W. van der Hofstad
Copromotor:
dr. A. Di BucchianicoContents
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 The importance of software testing . . . . . . . . . . . . . . . 1
1.1.2 Software failure vs. fault . . . . . . . . . . . . . . . . . . . . . 2
1.1.3 Black-box vs. model-based testing . . . . . . . . . . . . . . . 3
1.1.4 When to stop testing . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Goal and outline of the thesis . . . . . . . . . . . . . . . . . . . . . . 4
2 Probability Models in Software Reliability and Testing 9
2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Stochastic processes . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 Counting processes . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.2 Basic properties . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.3 Property implications . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Software testing framework . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Common notation . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.2 Reliability growth models . . . . . . . . . . . . . . . . . . . . 19
2.3.3 Stochastic ordering and reliability growth . . . . . . . . . . . 21
2.4 Classification of software reliability growth models . . . . . . . . . . 23
2.4.1 Previous work on model classification . . . . . . . . . . . . . 23
2.4.2 Classification based on properties of stochastic processes . . . 26
2.5 General order statistics models . . . . . . . . . . . . . . . . . . . . . 27
2.5.1 Jelinski-Moranda model . . . . . . . . . . . . . . . . . . . . . 30
2.5.2 Geometric order statistics model . . . . . . . . . . . . . . . . 32
2.6 Non-homogenous Poisson process models . . . . . . . . . . . . . . . . 33
2.6.1 Goel-Okumoto model . . . . . . . . . . . . . . . . . . . . . . 35
2.6.2 Yamada S-shaped model . . . . . . . . . . . . . . . . . . . . . 36
2.6.3 Duane (power-law) model . . . . . . . . . . . . . . . . . . . . 37
2.7 Linking GOS and NHPP models . . . . . . . . . . . . . . . . . . . . 38
2.7.1 A note on NHPP-infinite models . . . . . . . . . . . . . . . . 40
2.8 Bayesian approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.9 Some other models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.9.1 Schick-Wolverton model . . . . . . . . . . . . . . . . . . . . . 42
3 Statistical Inference for Software Reliability Growth Models 45
3.1 Data description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 Trend analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3 Model type selection . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4 Model estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.4.1 ML estimation for GOS models . . . . . . . . . . . . . . . . . 56
Jelinski-Moranda model . . . . . . . . . . . . . . . . . . . . . 57
vvi Contents
3.4.2 ML estimation for NHPP models . . . . . . . . . . . . . . . . 58
Goel-Okumoto model . . . . . . . . . . . . . . . . . . . . . . 58
Duane (power-law) model . . . . . . . . . . . . . . . . . . . . 59
3.5 Model validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.6 Model interpretation . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4 A New Statistical Software Reliability Tool 65
4.1 General remarks about the implementation . . . . . . . . . . . . . . 65
4.2 Main functionalities . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.2.1 Data menu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2.2 Graphics menu . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2.3 Analysis menu . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.2.4 Help menu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.3 Two examples of applying reliability growth models in software de-
velopment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.3.1 Administrative software at an insurance company . . . . . . . 78
4.3.2 A closable dam operating system . . . . . . . . . . . . . . . . 83
5 Statistical Approach to Software Reliability Certification 89
5.1 Previous work on software reliability certification . . . . . . . . . . . 90
5.1.1 Certification procedure based on expected time to next failure 90
5.1.2 pro based on fault-free system . . . . . . 92
5.2 Bayesian approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.3 Bayesianreleaseprocedureforsoftwarereliabilitygrowthmodelswith
independent times between failures . . . . . . . . . . . . . . . . . . . 97
5.3.1 Jelinski-Moranda and Goel-Okumoto models . . . . . . . . . 99
Case 1: N and deterministic . . . . . . . . . . . . . . . . . 99
Case 2: N known and fixed, Gamma distributed . . . . . . 100
Case 3: N Poisson distributed, known and fixed (Goel-
Okumoto model) . . . . . . . . . . . . . . . . . . . . 102
Case 4: N Poisson and Gamma distributed (full Bayesian
approach) . . . . . . . . . . . . . . . . . . . . . . . . 103
5.3.2 Run model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Case 1: N and deterministic . . . . . . . . . . . . . . . . . 107
Case 2: N Poisson distributed, known and fixed . . . . . . 107
Case 3: N known and fixed, Beta distributed . . . . . . . . 109
Case 4: N Poisson and Beta (full Bayesian ap-
proach) . . . . . . . . . . . . . . . . . . . . . . . . . 110
6 Performance of the Certification Procedure 111
6.1 Jelinski-Moranda model . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.1.1 Case 1: N and deterministic . . . . . . . . . . . . . . . . . 111
6.1.2 Case 2: N known and fixed, Gamma distributed . . . . . . 112
6.1.3 Case 3: N Poisson distributed, known and fixed (Goel-
Okumoto model) . . . . . . . . . . . . . . . . . . . . . . . . . 117Contents vii
6.1.4 Case 4: N Poisson and Gamma distributed (full Bayesian
approach) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
6.2 Run model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
6.2.1 Case 1: N and deterministic . . . . . . . . . . . . . . . . . 124
6.2.2 Case 2: N Poisson distributed, known and fixed . . . . . . 124
6.2.3 Case 3: N known and fixed, Beta distributed . . . . . . . . 126
6.2.4 Case 4: N Poisson and Beta (full Bayesian ap-
proach) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
7 Model-Based Testing Framework 131
7.1 Labelled transition systems and a diagram technique for representation132
7.2 Example of modelling software as a labelled transition system . . . . 134
7.3 Error distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
7.3.1 Binomial distribution of error-marked transitions . . . . . . . 137
7.3.2 Poisson distribution ofed . . . . . . . . 139
7.4 Testing process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
7.5 Walking Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
7.5.1 Walking function update for labelled transition systems . . . 146
7.5.2 W update for acyclic workflow transition systems148
7.6 Common notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
8 Statistical Certification Procedures 155
8.1 Certificationprocedurebasedonthenumberofremainingerror-marked
transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
8.2 procedure based on the survival probability . . . . . . . 157
8.3 Practical application . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
8.3.1 General setup . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
8.3.2 Performance of the stopping rules . . . . . . . . . . . . . . . 162
9 Testing the Test Procedure 167
9.1 Generating random models . . . . . . . . . . . . . . . . . . . . . . . 167
9.2 Quality of the procedure . . . . . . . . . . . . . . . . . . . . . . . . . 170
9.3 Stresser: a tool for model-based testing certification . . . . . . . . . 173
9.3.1 Creating labelled transition systems . . . . . . . . . . . . . . 173
9.3.2 Error distribution . . . . . . . . . . . . . . . . . . . . . . . . 173
9.3.3 Parameters of testing: walk