FOUNDATIONS OF SOFTWARE TESTING: for vtu;for vtu

Cover......Page 1
Contents......Page 8
Preface......Page 14
Acknowledgments......Page 20
Part I: Preliminaries......Page 22
 Chapter 1: Basics of Software Testing......Page 24
  1.1.Humans, Errors, and Testing......Page 25
   1.1.1. Errors, faults, and failures......Page 26
   1.1.3. Developer and tester as two roles......Page 28
   1.2.1. Quality attributes......Page 29
   1.2.2. Reliability......Page 31
  1.3 Requirements, Behavior, and Correctness......Page 32
   1.3.1. Input domain and program correctness......Page 33
   1.3.2. Valid and invalid inputs......Page 34
   1.4.1. Correctness......Page 36
   1.4.3. Program use and the operational profile......Page 37
   1.5.1. Preparing a test plan......Page 38
   1.5.2. Constructing test data......Page 39
   1.5.3. Executing the program......Page 41
   1.5.4. Specifying program behavior......Page 42
   1.5.5. Assessing the correctness of program behavior......Page 45
   1.5.6. Construction of oracles......Page 47
  1.6 Test Metrics......Page 48
   1.6.1. Organizational metrics......Page 49
   1.6.4. Product metrics: Generic......Page 50
   1.6.5. Product metrics: OO software......Page 52
   1.6.7. Static and dynamic metrics......Page 53
   1.6.8. Testability......Page 54
  1.7 Software and Hardware Testing......Page 55
  1.8 Testing and Verification......Page 57
  1.9 Defect Management......Page 58
  1.10 Execution History......Page 59
  1.11 Test-Generation Strategies......Page 60
  1.12 Static Testing......Page 62
   1.12.2. Inspections......Page 63
   1.12.3. Use of static code analysis tools in static testing......Page 64
   1.12.4. Software complexity and static testing......Page 65
  1.13 Model-Based Testing and Model Checking......Page 66
   1.14.1. Basic block......Page 67
   1.14.2. Flow graph: Definition and pictorial representation......Page 69
   1.14.3. Path......Page 71
  1.15 Dominators and Postdominators......Page 75
   1.16.1. Data dependence......Page 77
   1.16.2. Control dependence......Page 78
  1.17 Strings, Languages, and Regular Expressions......Page 80
  1.18 Types of Testing......Page 81
   1.18.1. Classifier C1: Source of testgeneration......Page 82
   1.18.2. Classifier C2: Life cycle phase......Page 85
   1.18.3. Classifier C3: Goal-directed testing......Page 86
   1.18.4. Classifier C4: Artifact under test......Page 89
   1.18.5. Classifier C5: Test process models......Page 91
  1.19 The Saturation Effect......Page 95
   1.19.1. Confidence and true reliability......Page 96
   1.19.3. False sense of confidence......Page 97
   1.19.4. Reducing Δ......Page 98
   1.19.5. Impact on test process......Page 99
  Summary......Page 100
  Bibliographic Notes......Page 101
  Exercises......Page 106
Part II: Test Generation......Page 110
 Chapter 2: Test Generation from Requirements......Page 112
  2.1 Introduction......Page 113
  2.2 The Test-Selection Problem......Page 114
  2.3 Equivalence Partitioning......Page 116
   2.3.1. Faults targeted......Page 117
   2.3.2. Relations and equivalence partitioning......Page 118
   2.3.3. Equivalence classes for variables......Page 123
   2.3.4. Unidimensional versus multidimensional partitioning......Page 127
   2.3.5. A systematic procedure forequivalence partitioning......Page 129
   2.3.6. Test selection based on equivalence classes......Page 135
   2.3.7. GUI design and equivalence classes......Page 138
  2.4 Boundary-Value Analysis......Page 140
   2.5.1 Steps in the category-partition method......Page 146
  2.6 Cause–Effect Graphing......Page 153
   2.6.1. Notation used in cause–effect graphing......Page 154
   2.6.2. Creating cause–effect graphs......Page 157
   2.6.3. Decision table from cause–effect graph......Page 161
   2.6.4. Heuristics to avoid combinatorial explosion......Page 166
   2.6.5. Test generation from a decision table......Page 169
  2.7 Test Generation from Predicates......Page 170
   2.7.1. Predicates and boolean expressions......Page 171
   2.7.2. Fault model for predicate testing......Page 173
   2.7.3. Predicate constraints......Page 175
   2.7.4. Predicate-testing criteria......Page 177
   2.7.5. Generating BOR-, BRO-, and BRE-adequate tests......Page 179
    2.7.5 Generating the BOR-constraint set......Page 181
    Generating the BRO-constraint set......Page 183
    2.7.5.3 Generating the BRE-constraint set......Page 186
    2.7.5.4 Generating BOR Constraints for Nonsingular Expressions......Page 189
   2.7.6 Cause–effect Graphs and Predicate Testing......Page 194
   2.7.7 Fault Propagation......Page 195
    2.7.8.1 Specification-based Predicate Test Generation......Page 197
    2.7.8.2 Program-based Predicate Test Generation......Page 199
  Summary......Page 201
  Bibliographic Notes......Page 202
  Exercises......Page 205
 Chapter 3: Test Generation from Finite-State Models......Page 214
  3.1 Software Design and Testing......Page 215
  3.2 Finite-state Machines......Page 217
   3.2.1. Excitation using an input sequence......Page 221
   3.2.2. Tabular representation......Page 222
   3.2.3. Properties of FSM......Page 223
  3.3 Conformance Testing......Page 224
   3.3.1. Reset inputs......Page 226
   3.3.2. The testing problem......Page 228
  3.4 A Fault Model......Page 229
   3.4.1. Mutants of FSMs......Page 232
   3.4.2. Fault coverage......Page 234
  3.5 Characterization Set......Page 235
   3.5.1. Construction of the k-equivalence partitions......Page 236
   3.5.2. Deriving the characterization set......Page 239
  3.6 The W-method......Page 242
   3.6.2. Maximum number of states......Page 243
   3.6.3. Computation of the transition cover set......Page 244
   3.6.4. Constructing Z......Page 245
   3.6.5. Deriving a test set......Page 246
   3.6.6. Testing using the W-method......Page 247
   3.6.7. The error-detection process......Page 249
  3.7 The Partial W-method......Page 250
   3.7.1. Testing using the Wp-methodfor m = n......Page 252
   3.7.2. Testing using the Wp-methodfor m > n......Page 255
  3.8 The UIO-sequence Method......Page 257
   3.8.2. UIO sequences......Page 258
   3.8.3. Core and noncore behavior......Page 260
   3.8.4. Generation of UIO sequences......Page 262
    3.8.4.1 Explanation of gen-UIO......Page 265
   3.8.5. Distinguishing signatures......Page 274
   3.8.6. Test generation......Page 277
   3.8.7. Test optimization......Page 279
   3.8.8. Fault detection......Page 280
  3.9 Automata Theoretic Versuscontrol-flow-based Techniques......Page 283
   3.9.1. n-switch-cover......Page 286
   3.9.2. Comparing automata-theoreticmethods......Page 288
  Summary......Page 290
  Bibliographic Notes......Page 291
  Exercises......Page 294
 Chapter 4: Test Generation from Combinatorial Designs......Page 300
  4.1 Combinatorial Designs......Page 301
   4.1.2. Modeling the input and configuration spaces......Page 302
  4.2 A Combinatorial Test-Design Process......Page 308
  4.3 Fault Model......Page 310
   4.3.1. Fault vectors......Page 312
  4.4 Latin Squares......Page 313
  4.5 Mutually Orthogonal Latin Squares......Page 315
  4.6 Pairwise Design: Binary Factors......Page 317
  4.7 Pairwise Design: Multivalued Factors......Page 322
  4.8 Orthogonal Arrays......Page 330
   4.8.1. Mixed-level orthogonal arrays......Page 332
   4.9.2. Mixed-level covering arrays......Page 335
  4.10 Arrays Of Strength >2......Page 336
  4.11 Generating Covering Arrays......Page 337
  Summary......Page 347
  Bibliographic Notes......Page 348
  Exercises......Page 351
 Chapter 5: Test Selection, Minimization, and Prioritization for Regression Testing......Page 356
  5.1 What is Regression Testing?......Page 357
  5.2 Regression-Test Process......Page 358
   5.2.1. Test revalidation, selection, minimization, and prioritization......Page 359
   5.2.2. Test setup......Page 360
   5.2.3. Test sequencing......Page 361
   5.2.4. Test execution......Page 363
  5.3 RTS: The Problem......Page 364
  5.4 Selecting Regression Tests......Page 365
   5.4.3. Selecting modification-traversing tests......Page 366
   5.4.4. Test minimization......Page 367
  5.5 Test Selection Using Execution Trace......Page 368
   5.5.1. Obtaining the execution trace......Page 369
   5.5.2. Selecting regression tests......Page 371
   5.5.4. Handling changes in declarations......Page 376
  5.6 Test Selection Using Dynamic Slicing......Page 379
   5.6.2. Computation of dynamic slices......Page 381
   5.6.3. Selecting tests......Page 383
   5.6.4. Potential dependence......Page 384
   5.6.6. Addition and deletion of statements......Page 388
   5.6.8. Reduced dynamic-dependence graph......Page 390
  5.7 Scalability of Test-Selection Algorithms......Page 392
  5.8 Test Minimization......Page 394
   5.8.1. The set-cover problem......Page 395
   5.8.2. A procedure for test minimization......Page 396
  5.9 Test Prioritization......Page 398
  5.10 Tools For Regression Testing......Page 402
  Summary......Page 405
  Bibliographic Notes......Page 406
  Exercises......Page 412
Part III: Test Adequacy Assessment and Enhancement......Page 420
 Chapter 6: Test-Adequacy Assessment Using Control Flow and Data Flow......Page 422
   6.1.1. What is test adequacy?......Page 423
   6.1.2. Measurement of test adequacy......Page 424
   6.1.3. Test enhancement using measurements of adequacy......Page 426
   6.1.4. Infeasibility and test adequacy......Page 430
   6.1.5. Error detection and test enhancement......Page 432
   6.1.6. Single and multiple executions......Page 435
   6.2.1. Statement and block coverage......Page 436
   6.2.2. Conditions and decisions......Page 439
   6.2.3. Decision coverage......Page 441
   6.2.4. Condition coverage......Page 443
   6.2.5. Condition/decision coverage......Page 445
   6.2.6. Multiple condition coverage......Page 447
   6.2.7. Linear code sequence and jump (LCSAJ) coverage......Page 450
   6.2.8. Modified condition/decision coverage......Page 454
   6.2.9. MC/DC-adequate tests for compound conditions......Page 455
   6.2.10. Definition of MC/DC coverage......Page 461
   6.2.12. Error detection and MC/DC adequacy......Page 469
   6.2.13. Short-circuit evaluation andinfeasibility......Page 471
   6.2.14. Tracing test cases to requirements......Page 473
  6.3 Data-Flow Concepts......Page 475
   6.3.1. Definitions and uses......Page 476
   6.3.2. c-use and p-use......Page 477
   6.3.3. Global and local definitions and uses......Page 478
   6.3.4. Data-flow graph......Page 479
   6.3.5. Def–clear paths......Page 481
   6.3.6. Def–use pairs......Page 482
   6.3.7. Def–use chains......Page 483
   6.3.8. A little optimization......Page 484
   6.3.9. Data contexts and ordered data contexts......Page 485
  6.4 Adequacy Criteria Based on Data Flow......Page 488
   6.4.1. c-use coverage......Page 489
   6.4.2. p-use coverage......Page 490
   6.4.4. k–dr chain coverage......Page 492
   6.4.5. Using the k–dr chain coverage......Page 494
   6.4.6. Infeasible c-uses and p-uses......Page 495
   6.4.7. Context coverage......Page 496
  6.5 Control Flow Versus Data Flow......Page 499
  6.6 The Subsumes Relation......Page 501
  6.7 Structural and Functional Testing......Page 503
  6.8 Scalability of Coverage Measurement......Page 504
  Summary......Page 507
  Bibliographic Notes......Page 508
  Exercises......Page 515
 Chapter 7: Test-Adequacy Assessment Using Program Mutation......Page 523
  7.1 Introduction......Page 524
  7.2 Mutation and Mutants......Page 525
   7.2.1. First-order and higher-order mutants......Page 526
   7.2.2. Syntax and semantics of mutants......Page 527
   7.2.3. Strong and weak mutations......Page 530
   7.2.4. Why mutate?......Page 532
   7.3.1. A procedure for test-adequacyassessment......Page 533
   7.3.2. Alternate procedures for test-adequacy assessment......Page 541
   7.3.3. Distinguished versus killed mutants......Page 542
   7.3.4. Conditions for distinguishing a mutant......Page 543
  7.4 Mutation Operators......Page 545
   7.4.1. Operator types......Page 546
   7.4.2. Language dependence ofmutation operators......Page 548
   7.5.1. Goodness criteria for mutationoperators......Page 550
   7.5.2. Guidelines......Page 551
   7.6.1. The competent programmerhypothesis......Page 552
  7.7 Equivalent Mutants......Page 553
  7.8 Fault Detection Using Mutation......Page 554
  7.9 Types of Mutants......Page 557
   7.10.1. What is not mutated?......Page 558
   7.10.2. Linearization......Page 559
   7.10.3. Execution sequence......Page 561
   7.10.4. Effect of an execution sequence......Page 564
   7.10.6. Global and local reference sets......Page 565
   7.10.7. Mutating program constants......Page 568
    7.10.7.1 Required Constant Replacement......Page 569
    7.10.8.1 Binary Operator Mutations......Page 570
    7.10.8.2 Unary Operator Mutations......Page 571
   7.10.9. Mutating statements......Page 576
    7.10.9.1 Trap on Statement Execution......Page 577
    7.10.9.2 Trap on if Condition......Page 578
    7.10.9.3 Statement Deletion......Page 579
    7.10.9.4 return Statement Replacement......Page 580
    7.10.9.7 break Replacement by continue......Page 582
    7.10.9.9 Continue Out to nth Enclosing Level......Page 583
    7.10.9.11 Multiple Trip Continue......Page 585
    7.10.9.12 Sequence Operator Mutation......Page 586
    7.10.9.13 Move Brace Up or Down......Page 587
    7.10.9.14 Switch Statement Mutation......Page 589
    7.10.10.1 Scalar Variable Reference Replacement......Page 591
    7.10.10.5 Structure Component Replacement......Page 593
    7.10.10.6 Array Reference Subscript Mutation......Page 594
    7.10.10.7 Domain Traps......Page 595
  7.11 Mutation Operators for Java......Page 596
   7.11.1. Traditional mutation operators......Page 598
   7.11.2. Inheritence......Page 599
   7.11.3. Polymorphism and dynamic binding......Page 602
   7.11.4. Method overloading......Page 603
   7.11.5. Java-specific mutation operators......Page 605
  7.12 Mutation Operators for Fortran 77, C, and Java: A Comparison......Page 606
  7.13 Tools for Mutation Testing......Page 609
   7.14.1. Prioritizing functions to be mutated......Page 611
   7.14.2. Selecting a subset of mutationoperators......Page 612
Summary......Page 614
Bibliographic Notes......Page 615
Exercises......Page 627
References......Page 636
Subject Index......Page 674
Name Index......Page 706