Foundations of Software Testing, 2nd Edition

Cover......Page 1
Contents......Page 6
Preface to the SecondEdition......Page 14
Preface to the FirstEdition......Page 20
Acknowledgements......Page 28
Part I:Preliminaries......Page 32
 Chapter 1: Preliminaries: Software Testing......Page 34
  1.1 Humans, Errors, and Testing......Page 35
   1.1.1 Errors, faults, and failures......Page 36
   1.1.3 Developer and tester as two roles......Page 38
   1.2.1 Quality attributes......Page 39
   1.2.2 Reliability......Page 41
  1.3 Requirements, Behavior, and Correctness......Page 42
   1.3.1 Input domain......Page 43
   1.3.2 Specifying program behavior......Page 44
   1.3.3 Valid and invalid inputs......Page 48
   1.4.1 Correctness......Page 49
   1.4.2 Reliability......Page 50
   1.4.3 Operational profiles......Page 51
   1.5.2 Constructing test data......Page 52
   1.5.3 Executing the program......Page 54
   1.5.4 Assessing program correctness......Page 56
   1.5.5 Constructing an oracle......Page 57
   1.6.1 Organizational metrics......Page 59
   1.6.2 Project metrics......Page 60
   1.6.4 Product metrics: generic......Page 61
   1.6.5 Product metrics: OO software......Page 63
   1.6.8 Testability......Page 64
  1.7 Software and Hardware Testing......Page 66
  1.8 Testing and Verification......Page 68
  1.9 Defect Management......Page 69
  1.10 Test Generation Strategies......Page 70
   1.11.1 Walkthroughs......Page 73
   1.11.3 Software complexity and static testing......Page 74
  1.12 Model-Based Testing and Model Checking......Page 75
  1.13 Types of Testing......Page 76
   1.13.1 Classifier: C1: Source of test generation......Page 78
   1.13.2 Classifier: C2: Life cycle phase......Page 79
   1.13.3 Classifier: C3: Goal-directed testing......Page 81
   1.13.4 Classifier: C4: Artifact under test......Page 84
   1.13.5 Classifier: C5: Test process models......Page 85
  1.14 The Saturation Effect......Page 90
   1.14.2 Saturation region......Page 91
   1.14.4 Reducing......Page 92
  1.15 Principles of Testing......Page 94
  1.16 Tools......Page 97
  Summary......Page 98
  Exercises......Page 99
 Chapter 2: Preliminaries:Mathematical......Page 102
  2.1 Predicates and Boolean Expressions......Page 103
   2.2.1 Basic blocks......Page 105
   2.2.2 Flow graphs......Page 107
   2.2.3 Paths......Page 108
   2.2.4 Basis paths......Page 114
   2.2.5 Path conditions and domains......Page 116
   2.2.6 Domain and computation errors......Page 121
   2.2.7 Static code analysis tools and static testing......Page 122
  2.3 Execution History......Page 123
  2.4 Dominators and Post-Dominators......Page 124
   2.5.1 Data dependence......Page 126
   2.5.2 Control dependence......Page 127
   2.5.3 Call graph......Page 128
  2.6 Strings, Languages, and Regular Expressions......Page 129
  2.7 Tools......Page 130
  Exercises......Page 132
Part II:Test Generation......Page 134
 Chapter 3: DomainPartitioning......Page 136
  3.1 Introduction......Page 137
  3.2 The Test Selection Problem......Page 138
  3.3 Equivalence Partitioning......Page 140
   3.3.1 Faults targeted......Page 141
   3.3.2 Relations......Page 142
   3.3.3 Equivalence classes for variables......Page 147
   3.3.4 Unidimensional partitioning versus multidimensional partitioning......Page 152
   3.3.5 A systematic procedure......Page 154
   3.3.6 Test selection......Page 159
   3.3.7 Impact of GUI design......Page 162
  3.4 Boundary Value Analysis......Page 164
   3.5.1 Steps in the category-partition method......Page 171
  Exercises......Page 178
 Chapter 4: Predicate Analysis......Page 183
   4.2.1 Domain errors......Page 184
   4.2.2 Border shifts......Page 185
   4.2.3 ON-OFF points......Page 186
   4.2.4 Undetected errors......Page 188
   4.2.6 Paths to be tested......Page 190
  4.3 Cause-Effect Graphing......Page 191
   4.3.1 Notation used in cause-effect graphing......Page 192
   4.3.2 Creating cause-effect graphs......Page 194
   4.3.3 Decision table from cause-effect graph......Page 198
   4.3.4 Heuristics to avoid combinatorial explosion......Page 203
   4.3.5 Test generation from a decision table......Page 206
   4.4.1 A fault model......Page 207
   4.4.2 Missing or extra Boolean variable faults......Page 209
   4.4.3 Predicate constraints......Page 210
   4.4.4 Predicate testing criteria......Page 211
   4.4.5 BOR, BRO, and BRE adequate tests......Page 213
   4.4.6 BOR constraints for non-singular expressions......Page 222
   4.4.7 Cause-effect graphs and predicate testing......Page 228
   4.4.8 Fault propagation......Page 229
   4.4.9 Predicate testing in practice......Page 231
  4.5 Tests Using Basis Paths......Page 235
  4.6 Scenarios and Tests......Page 236
  Exercises......Page 238
 Chapter 5: Test Generation from Finite State Models......Page 244
  5.1 Software Design and Testing......Page 245
  5.2 Finite State Machines......Page 247
   5.2.1 Excitation using an input sequence......Page 251
   5.2.2 Tabular representation......Page 252
   5.2.3 Properties of FSM......Page 253
  5.3 Conformance Testing......Page 255
   5.3.1 Reset inputs......Page 257
  5.4 A Fault Model......Page 259
   5.4.1 Mutants of FSMs......Page 262
   5.4.2 Fault coverage......Page 264
  5.5 Characterization Set......Page 265
   5.5.1 Construction of the k-equivalence partitions......Page 266
   5.5.2 Deriving the characterization set......Page 270
   5.5.3 Identification sets......Page 272
   5.6.1 Assumptions......Page 273
   5.6.3 Computation of the transition cover set......Page 274
   5.6.5 Deriving a test set......Page 276
   5.6.6 Testing using the W-method......Page 277
   5.6.7 The error detection process......Page 280
  5.7 The Partial W-method......Page 281
   5.7.1 Testing using the Wp-method for m - n......Page 283
   5.7.2 Testing using the Wp-method for m>n......Page 285
   5.8.2 UIO sequences......Page 288
   5.8.3 Core and non-core behavior......Page 290
   5.8.4 Generation of UIO sequences......Page 292
   5.8.5 Explanation of gen-uio......Page 295
   5.8.6 Distinguishing signatures......Page 304
   5.8.7 Test generation......Page 306
   5.8.8 Test optimization......Page 308
   5.8.9 Fault detection......Page 310
  5.9 Automata Theoretic Versus Control-Flow Based Techniques......Page 313
   5.9.1 n-switch-cover......Page 316
   5.9.2 Comparing automata theoretic methods......Page 317
  5.10 Tools......Page 318
  Summary......Page 319
  Exercises......Page 320
 Chapter 6: Test Generation from Combinatorial Designs......Page 326
  6.1 Combinatorial Designs......Page 327
   6.1.2 Modeling the input and configuration spaces......Page 328
  6.2 A Combinatorial Test Design Process......Page 334
  6.3 Fault Model......Page 336
   6.3.1 Fault vectors......Page 338
  6.4 Latin Squares......Page 339
  6.5 Mutually Orthogonal Latin Squares......Page 341
  6.6 Pairwise Design: Binary Factors......Page 343
  6.7 Pairwise Design: Multi-Valued Factors......Page 349
   6.7.1 Shortcomings of using MOLS for test design......Page 356
  6.8 Orthogonal Arrays......Page 357
   6.8.1 Mixed-level orthogonal arrays......Page 358
  6.9 Covering and Mixed-Level Covering Arrays......Page 361
   6.9.1 Mixed-level covering arrays......Page 362
  6.10 Arrays of Strength > 2......Page 363
  6.11 Generating Covering Arrays......Page 364
  Summary......Page 373
  Exercises......Page 374
Part III: Test Adequacy Assessment and Enhancement......Page 378
 Chapter 7: Test Adequacy Assessment Using Control Flow and Data Flow......Page 380
   7.1.1 What is test adequacy?......Page 381
   7.1.2 Measurement of test adequacy......Page 382
   7.1.3 Test enhancement using measurements of adequacy......Page 384
   7.1.4 Infeasibility and test adequacy......Page 389
   7.1.5 Error detection and test enhancement......Page 391
   7.1.6 Single and multiple executions......Page 394
   7.2.1 Statement and block coverage......Page 395
   7.2.2 Conditions and decisions......Page 398
   7.2.3 Decision coverage......Page 400
   7.2.4 Condition coverage......Page 402
   7.2.5 Condition/decision coverage......Page 404
   7.2.6 Multiple condition coverage......Page 406
   7.2.7 Linear code sequence and jump (LCSAJ) coverage......Page 409
   7.2.8 Modified condition/decision coverage......Page 413
   7.2.9 MC/DC adequate tests for compound conditions......Page 414
   7.2.10 Definition of MC/DC coverage......Page 418
   7.2.12 Error detection and MC/DC adequacy......Page 427
   7.2.13 Short-circuit evaluation and infeasibility......Page 429
   7.2.15 Tracing test cases to requirements......Page 431
  7.3 Concepts From Data Flow......Page 433
   7.3.1 Definitions and uses......Page 435
   7.3.3 Global and local definitions and uses......Page 436
   7.3.4 Data flow graph......Page 437
   7.3.5 Def-clear paths......Page 439
   7.3.6 Def-use pairs......Page 440
   7.3.7 Def-use chains......Page 441
   7.3.8 A little optimization......Page 442
   7.3.9 Data contexts and ordered data contexts......Page 443
  7.4 Adequacy Criteria Based on Data Flow......Page 446
   7.4.1 c-use coverage......Page 447
   7.4.2 p-use coverage......Page 448
   7.4.4 k-dr chain coverage......Page 450
   7.4.5 Using the k-dr chain coverage......Page 452
   7.4.6 Infeasible c- and p-uses......Page 453
   7.4.7 Context coverage......Page 454
  7.5 Control Flow Versus Data Flow......Page 456
  7.6 The “Subsumes” Relation......Page 458
  7.7 Structural and Functional Testing......Page 460
  7.8 Scalability of Coverage Measurement......Page 462
  7.9 Tools......Page 464
  Summary......Page 465
  Exercises......Page 466
 Chapter 8: Test Adequacy Assessment using Program Mutation......Page 473
  8.1 Introduction......Page 474
  8.2 Mutation and Mutants......Page 475
   8.2.1 First order and higher order mutants......Page 476
   8.2.2 Syntax and semantics of mutants......Page 477
   8.2.3 Strong and weak mutations......Page 480
   8.2.4 Why mutate ?......Page 481
   8.3.1 A procedure for test adequacy assessment......Page 483
   8.3.2 Alternate procedures for test adequacy assessment......Page 493
   8.3.4 Conditions for distinguishing a mutant......Page 494
  8.4 Mutation Operators......Page 496
   8.4.1 Operator types......Page 498
   8.4.2 Language dependence of mutation operators......Page 499
   8.5.1 Goodness criteria for mutation operators......Page 501
   8.5.2 Guidelines......Page 502
   8.6.1 The competent programmer hypothesis......Page 503
   8.6.2 The coupling effect......Page 504
  8.8 Fault Detection Using Mutation......Page 505
  8.9 Types of Mutants......Page 508
  8.10 Mutation Operators for C......Page 509
   8.10.1 What is not mutated ?......Page 510
   8.10.2 Linearization......Page 511
   8.10.3 Execution sequence......Page 512
   8.10.4 Effect of an execution sequence......Page 515
   8.10.5 Global and local identifier sets......Page 516
   8.10.6 Global and local reference sets......Page 517
   8.10.7 Mutating program constants......Page 520
   8.10.8 Mutating operators......Page 521
   8.10.9 Binary operator mutations......Page 522
   8.10.10 Mutating statements......Page 528
   8.10.11 Mutating program variables......Page 542
   8.10.12 Structure Reference Replacement......Page 544
  8.11 Mutation Operators for Java......Page 547
   8.11.1 Traditional mutation operators......Page 548
   8.11.2 Inheritence......Page 549
   8.11.3 Polymorphism and dynamic binding......Page 552
   8.11.4 Method overloading......Page 554
   8.11.5 Java specific mutation operators......Page 555
  8.12 Comparison of Mutation Operators......Page 557
  8.13 Mutation Testing within Budget......Page 559
   8.13.1 Prioritizing functions to be mutated......Page 560
   8.13.2 Selecting a subset of mutation operators......Page 561
  8.14 CASE and Program Testing......Page 562
  8.15 Tools......Page 564
  Summary......Page 566
  Exercises......Page 567
Part IV: Phases of Testing......Page 576
 Chapter 9: Test Selection, Minimization, and Prioritization for Regression Testing......Page 578
  9.1 What is Regression Testing?......Page 579
  9.2 Regression Test Process......Page 580
   9.2.1 Revalidation, selection, minimization,and prioritization......Page 581
   9.2.2 Test setup......Page 582
   9.2.3 Test sequencing......Page 583
   9.2.4 Test execution......Page 585
  9.3 Regression Test Selection: The Problem......Page 586
   9.4.3 Selecting modification traversing tests......Page 588
   9.4.4 Test minimization......Page 589
   9.4.5 Test prioritization......Page 590
   9.5.1 Obtaining the execution trace......Page 591
   9.5.2 Selecting regression tests......Page 593
   9.5.4 Handling changes in declarations......Page 598
  9.6 Test Selection Using Dynamic Slicing......Page 601
   9.6.2 Computation of dynamic slices......Page 603
   9.6.3 Selecting tests......Page 605
   9.6.4 Potential dependence......Page 606
   9.6.5 Computing the relevant slice......Page 610
   9.6.6 Addition and deletion of statements......Page 611
   9.6.7 Identifying variables for slicing......Page 612
   9.6.8 Reduced dynamic dependence graph......Page 613
  9.7 Scalability of Test Selection Algorithms......Page 614
  9.8 Test Minimization......Page 617
   9.8.2 A procedure for test minimization......Page 618
  9.9 Test Prioritization......Page 621
  9.10 Tools......Page 625
  Summary......Page 626
  Exercises......Page 627
 Chapter 10: Unit Testing......Page 632
  10.2 Context......Page 633
  10.3 Test Design......Page 634
  10.4 Using JUnit......Page 636
   10.5.1 Using mock objects......Page 640
  10.6 Tools......Page 647
  Exercises......Page 648
 Chapter 11: Integration Testing......Page 650
  11.1 Introduction......Page 651
  11.2 Integration Errors......Page 652
  11.3 Dependence......Page 653
   11.3.1 Class relationships: static......Page 656
   11.3.2 Class relationships: dynamic......Page 657
   11.3.3 Class firewalls......Page 658
   11.3.4 Precise and imprecise relationships......Page 659
  11.4 OO versus Non-OO Programs......Page 661
  11.5 Integration Hierarchy......Page 662
   11.5.1 Choosing an integration strategy......Page 664
   11.5.2 Comparing integration strategies......Page 665
   11.5.3 Specific stubs and retesting......Page 666
   11.6.1 The TD method......Page 668
   11.6.2 The TJJM method......Page 680
   11.6.3 The BLW method......Page 685
   11.6.4 Comparison of TD, TJJM, and the BLW methods......Page 689
   11.6.5 Which test order algorithm to select?......Page 692
   11.7.1 Data variety......Page 693
   11.7.2 Data constraints......Page 695
  11.8 Test Assessment......Page 696
  11.9 Tools......Page 698
  Summary......Page 699
  Exercises......Page 700
Index......Page 704