Composing Software Components (eBook)

The Griffin 6
Acknowledgements 7
Contents 8
Chapter 1 15
1.1 A ‘Clear Drop’ 16
1.1.1 Testing Components and Recording Approximations 16
1.1.2 Synthesizing a System 19
1.1.3 Discussion of the Example 20
1.2 Roadmap of this Monograph 22
1.2.1 Theory vs. Practice 23
1.2.2 Formal Theory of Software Testing 24
1.2.3 Exploratory Tools 25
1.2.4 Insights into Component Composition 25
1.2.5 Implications for Testing in General 26
Part I Components and Component-based Development 28
Chapter 2 29
2.1 Standardized Components Make Engineering Possible 29
2.2 Mechanical Engineering of a Vacuum System 31
2.3 Electrical/Computer Engineering of a Laptop 33
2.4 Can It Be Done with Software? 35
Chapter 3 41
3.1 The Parts: Components 42
3.1.1 Common Environment for Software 42
3.1.2 Reuse 43
3.1.3 Information Hiding 44
3.1.4 Object-oriented Design 44
3.1.5 Szyperski’s Definition 45
3.2 The Systems: Component-based Software Development (CBSD) 46
3.2.1 Product Families 48
3.2.2 Component Development and Cataloging 48
3.2.3 System Design using Components 50
3.3 The Viewpoint: Testing Simple Components and Systems 50
3.3.1 Simple Components 50
3.3.2 Simple Systems 51
3.3.3 Critique of the Model 51
Chapter 4 53
4.1 Components and Connectors 53
4.2 System Architecture 55
4.3 Component Models 56
4.3.1 Middleware and Container Services 56
4.4 Immutable Components 57
4.5 Broader Theory of CBSD 58
4.5.1 General Component-based System Design Theory 58
4.5.2 Component-based Verification 60
4.5.3 Testing vs. Proving 61
4.6 Summary of CBSD Issues 62
Chapter 5 65
5.1 ‘Lifecycle’ Models of Development 66
5.1.1 Development Phases 66
5.1.2 Waterfall Models 67
5.1.3 Agile Models 68
5.1.4 Which Model is Best? 69
5.2 Functional/Requirements Testing 70
5.2.1 Unit Testing vs. System Testing 70
5.3 Preventing Bugs 71
5.3.1 Software Inspection 71
5.3.2 Formal Methods 72
5.3.3 Creating Perfection vs. Finding Failure 73
5.4 Testing in CBSD 73
Part II Software Testing: Practice and Theory 64
Chapter 6 75
6.1 Floyd-Hoare-Mills Semantics 75
6.2 Functional Testing Theory 77
6.2.1 Functional Testing Theory without State 77
6.2.2 Extending Functional Theory to Include State 79
6.2.3 Testing Concurrent Software 82
6.3 Summary of Testing Theory 85
Chapter 7 86
7.1 Divide and Conquer (or Multiply and Founder?) 87
7.2 History of ‘Coverage’ Testing 88
7.2.1 Functional Coverage 89
7.2.2 Structural Coverage 90
7.2.3 Combining Functional and Structural Coverage 94
7.3 Usage Profiles 95
7.4 Subdomain Testing in the Presence of State 97
7.5 Concurrency 100
7.6 Comparing Subdomain Techniques 101
7.6.1 The ‘Subsumes’ Partial Ordering 101
7.6.2 Random Testing 102
7.6.3 Comparing Randomand Subdomain-testing 103
Part III Composition of Components 104
Chapter 8 105
8.1 Software Testing is ‘Non-compositional’ 105
8.2 Approximating and Measuring Component Properties 107
8.3 Calculating Properties of Stateless Systems 109
8.3.1 Series System 110
8.3.2 Conditional System Control Structure 113
8.3.3 Iterative System Control Structure 114
8.4 Combining Different Component Approximations 115
8.5 Synthesizing a Component-based System 116
8.5.1 Combining Testing and Proving 116
8.6 Summary of the Subdomain Testing Theory 118
Chapter 9 119
9.1 Getting Started 120
9.2 A Simple Complete Example 121
9.3 Approximation and Prediction Errors 132
9.4 Better Component Approximations 136
9.4.1 Splitting and Adjusting Subdomains 138
9.4.2 Piecewise-linear Component Approximation 138
9.4.3 How Well Can a Component Developer Do? 141
9.5 Internal Profiles 142
9.6 Incremental Processing 145
9.7 Tutorial Summary 146
Chapter 10 147
10.1 Extended Subdomain Theory of Composition 147
10.1.1 Algorithms for Synthesizing Systems from Components with State 148
10.1.2 Verifying the Algorithms 152
10.2 Testing Measurements 153
10.2.1 3-D Graphs and Approximation Errors 153
10.2.2 Equi-spaced vs. Sequence Sampling 154
10.3 System Predictions 155
10.3.1 Synthesis of Systems with State 156
10.4 A Tutorial Example with State 158
10.4.1 Tutorial: Modes (Preferences) 159
Chapter 11 174
11.1 Adding Concurrency to Composition Theory 174
11.1.1 Algorithm for Synthesizing Components in Parallel 175
11.2 Testing Measurements, Behavior Graphs, and System Predictions 176
11.3 A Tutorial Example with Concurrency 177
11.3.1 Tutorial: Multiversion Software 178
Chapter 12 186
12.1 Reliability in Other Engineering Disciplines 186
12.2 Software Reliability Theory 188
12.2.1 Software ‘Time’ Parameter 189
12.2.2 The Minefield Analogy 189
12.2.3 A Speculative Software Failure Rate 191
12.2.4 Measuring Software Failure Rate 195
12.2.5 Failure Rate in Subdomains 198
12.3 Component Independence 199
12.4 Reliability Synthesis 200
12.4.1 Difficulties in Component Measurements 201
12.4.2 Synthesis Rules 201
Part IV Supporting Tools 205
Chapter 13 206
13.1 Component Developers and System Designers 206
13.2 Ideal Tools for I-CBSD 207
13.2.1 Ideal Component-level Testing/Measurement Tools 207
13.2.2 Ideal System-level Synthesis (CAD) Tools 208
13.2.3 SYN Tools: An Existence Proof 208
Chapter 14 209
14.1 Component Conventions 211
14.1.1 Artificial Components 212
14.2 Underlying Algorithms 213
14.3 Execution by Table-lookup 214
14.3.1 Validating Tools 215
14.3.2 A Nasty Mistake 217
14.4 Tool Performance 220
Chapter 15 223
15.1 Debugging Components 223
15.1.1 Checking Tests Against Requirements 224
15.1.2 Executing Code Outside the Tools 225
15.1.3 Finding Good Subdomains 225
15.1.4 Graphical Aids 226
15.2 Debugging Component-based Systems 226
15.2.1 Component Mismatch 229
15.2.2 Interface Profiles 231
15.3 Debugging of Support Tools 232
15.3.1 Problem Decomposition 232
15.3.2 Iterative Enhancement 233
15.3.3 Components and Debugging of Tools 234
Chapter 16 237
16.1 Unstable Algorithms and Code 237
16.2 Improving the SYN Tools 238
16.3 Who’s Next? 240
Part V Case Studies 241
Chapter 17 242
17.1 Better Component Approximation, Better System Prediction 242
17.1.1 Tuning Subdomains with Tool Support 247
17.2 Predicting Prediction Accuracy 250
17.2.1 Prediction Error is Linear in Measurement Error 250
17.2.2 Theory of Error Propagation 251
17.2.3 Prediction Error is an Emergent System Property 254
17.2.4 Approximating System Prediction Errors 255
17.3 Approximation Accuracy as a Component Test-quality Metric 256
17.4 The Right Subdomains for Component Testing 257
Chapter 18 259
18.1 Fundamental Questions about Subdomain Testing 259
18.1.1 How to Sample Subdomains? 260
18.1.2 Is Series Synthesis Associative? 263
18.2 Moving Control Structures between Components and Systems 264
18.2.1 Series Composition within a Component 265
18.2.2 Conditionals in Code and Conditional Components 266
18.2.3 Raising the Level of Programming 268
18.3 Persistent State 268
18.3.1 Infeasible States 268
18.3.2 Modes and Storage in State 272
18.3.3 A Controlled ‘Editor’ System 279
18.4 Iteration at System Level 286
18.5 Component and System Reliability 290
18.6 Substituting one Component for Another 294
18.6.1 Meeting a Non-functional System Requirement Bound 295
Part VI Implications for Software Testing 298
Chapter 19 299
19.1 Components Make Ideal Software ‘Units’ 300
19.1.1 Solving Unit-testing Problems 301
19.1.2 Choosing Unit-test Subdomains 303
19.2 Unit Testing Is More Than it Seems 305
19.2.1 Saving and Using Unit-test Results 305
19.2.2 Unit Tests the Only Tests 305
19.3 Trusting Unit Tests 307
19.3.1 Trustworthy Component Testing 307
19.3.2 Matching Interface Profiles 307
19.4 Comparing System Predictions to Requirements 308
Chapter 20 310
20.1 Non-functional Depends on Functional 310
20.2 Non-functional ‘Compositional’ Properties 311
20.2.1 Run Time 312
20.2.2 Reliability 312
20.2.3 Safety Factors and Prediction Accuracy 313
20.3 Predicting Emergent Properties 314
20.3.1 Memory Leaks 314
20.3.2 Security 315
20.3.3 ‘Emergent’ Prediction Error 316
Chapter 21 318
21.1 Software Components are Unlike Mechanical Components 318
21.2 Software Functions Are Inherently Discontinuous 319
21.2.1 Simple Component Behaviors Lead to Complicated System Behaviors 321
21.3 Testing Theory is Unlike Other Formal Methods 322
21.3.1 Conservative Reductions 322
21.3.2 Special Role of Persistent State 323
21.4 The Several Meanings of ‘Compositional’ 324
21.4.1 Compositional Properties 325
21.4.2 Testing Can Be Made Compositional 325
21.5 Simple Tools are Remarkably Powerful 326
Chapter 22 329
22.1 Subdomain Testing in Non-numeric Domains 329
22.2 Completing a Testing Theory including State 330
22.2.1 Reliability in the Presence of State 330
22.2.2 BetterTools for State 331
22.3 Limited Input Domain 331
Appendix A 341
A.1 Documentation 342
A.2 SYN Documentation Tricks 343
A.2.1 Stand-alone Script Execution 344
A.2.2 Error Messages 344
A.2.3 ‘Message-discovery’ Documentation 346
A.2.4 ‘#debug’ Statements 347
A.2.5 The Script Header Comments 347
A.3 Details of the Tool Scripts 347
A.3.1 File Formats 348
A.3.2 Testing and Approximating Components:and friends 351
A.3.3 Synthesizing and Predicting Systems:and 352
A.3.4 Auxiliary Scripts 359
Index 361