Foundations of Software Testing

by Mathur, Aditya P.

• ISBN13: 9788131716601
• ISBN10: 8131716600
• Edition: 1st
• Format: Hardcover
• Copyright: 2008-04-07
• Publisher: Addison-Wesley Professional

Summary

This book presents sound engineering approaches for software test generation, selection, minimization, assessment, and enhancement. Using numerous examples, it offers a lucid description of a wide range of techniques for a variety of testing-related tasks.

Author Biography

Aditya P. Mathur is Professor and Head, Department of Computer Science, at Purdue University, Indiana

Table of Contents

Preface	p. xiii
Acknowledgments	p. xix
Preliminaries	p. 1
Basics of Software Testing	p. 3
Humans, errors, and testing	p. 4
Errors, faults, and failures	p. 5
Test automation	p. 7
Developer and tester as two roles	p. 7
Software quality	p. 8
Quality attributes	p. 8
Reliability	p. 10
Requirements, behavior, and correctiness	p. 11
Input domain and program correctness	p. 12
Valid and invalid inputs	p. 13
Correctness versus reliability	p. 15
Correctness	p. 15
Reliability	p. 16
Program use and the operational profile	p. 16
Testing and debugging	p. 17
Preparing a test plan	p. 17
Constructing test data	p. 18
Executing the program	p. 20
Specifying program behavior	p. 21
Assessing the correctness of program behavior	p. 24
Construction of oracles	p. 26
Test metrics	p. 27
Organizational metrics	p. 28
Project metrics	p. 29
Process metrics	p. 29
Product metrics: Generic	p. 29
Product metrics: OO software	p. 31
Progress monitoring and trends	p. 32
Static and dynamic metrics	p. 32
Testability	p. 33
Software and hardware testing	p. 34
Testing and verification	p. 36
Defect management	p. 37
Execution history	p. 38
Test-generation strategies	p. 39
Static testing	p. 41
Walkthroughs	p. 42
Inspections	p. 42
Use of static code analysis tools in static testing	p. 43
Software complexity and static testing	p. 44
Model-based testing and model checking	p. 45
Control-flow graph	p. 46
Basic block	p. 46
Flow graph: Definition and pictorial representation	p. 48
Path	p. 50
Dominators and postdominators	p. 54
Program-dependence graph	p. 56
Data dependence	p. 56
Control dependence	p. 57
Strings, languages, and regular expressions	p. 59
Types of testing	p. 60
Classifier C1: Source of test generation	p. 61
Classifier C2: Life cycle phase	p. 64
Classifier C3: Goal-directed testing	p. 65
Classifier C4: Artifact under test	p. 68
Classifier C5: Test process models	p. 70
The saturation effect	p. 74
Confidence and true reliability	p. 75
Saturation region	p. 76
False sense of confidence	p. 76
Reducing [Delta]	p. 77
Impact on test process	p. 78
Summary	p. 79
Bibliographic Notes	p. 80
Exercises	p. 85
Test Generation	p. 89
Test Generation from Requirements	p. 91
Introduction	p. 92
The test-selection problem	p. 93
Equivalence partitioning	p. 95
Faults targeted	p. 96
Relations and equivalence partitioning	p. 97
Equivalence classes for variables	p. 102
Unidimensional versus multidimensional partitioning	p. 106
A systematic procedure for equivalence partitioning	p. 108
Test selection based on equivalence classes	p. 114
GUI design and equivalence classes	p. 117
Boundary-value analysis	p. 119
Category-partition method	p. 125
Steps in the category-partition method	p. 125
Cause-effect graphing	p. 132
Notation used in cause-effect graphing	p. 133
Creating cause-effect graphs	p. 136
Decision table from cause-effect graph	p. 140
Heuristics to avoid combinatorial explosion	p. 145
Test generation from a decision table	p. 148
Test generation from predicates	p. 149
Predicates and boolean expressions	p. 150
Fault model for predicate testing	p. 152
Predicate constraints	p. 154
Predicate-testing criteria	p. 156
Generating BOR-, BRO-, and BRE-adequate tests	p. 158
Cause-effect graphs and predicate testing	p. 173
Fault propagation	p. 174
Predicate testing in practice	p. 176
Summary	p. 180
Bibliographic Notes	p. 181
Exercises	p. 184
Test Generation from Finite-State Models	p. 193
Software design and testing	p. 194
Finite-state machines	p. 196
Excitation using an input sequence	p. 200
Tabular representation	p. 201
Properties of FSM	p. 202
Conformance testing	p. 203
Reset inputs	p. 205
The testing problem	p. 207
A fault model	p. 208
Mutants of FSMs	p. 211
Fault coverage	p. 213
Characterization set	p. 214
Construction of the k-equivalence partitions	p. 215
Deriving the characterization set	p. 218
Identification sets	p. 221
The w-method	p. 221
Assumptions	p. 222
Maximum number of states	p. 222
Computation of the transition cover set	p. 223
Constructing Z	p. 224
Deriving a test set	p. 225
Testing using the W-method	p. 226
The error-detection process	p. 228
The partial w-method	p. 229
Testing using the Wp-method for m = n	p. 231
Testing using the Wp-method for m > n	p. 234
The UIO-sequence method	p. 236
Assumptions	p. 237
UIO sequences	p. 237
Core and noncore behavior	p. 239
Generation of UIO sequences	p. 241
Distinguishing signatures	p. 253
Test generation	p. 256
Test optimization	p. 258
Fault detection	p. 259
Automata theoretic versus control-flow-based techniques	p. 262
n-switch-cover	p. 265
Comparing automata-theoretic methods	p. 267
Summary	p. 269
Bibliographic Notes	p. 270
Exercises	p. 273
Test Generation from Combinatorial Designs	p. 279
Combinatorial designs	p. 280
Test configuration and test set	p. 281
Modeling the input and configuration spaces	p. 281
A combinatorial test-design process	p. 287
Fault model	p. 289
Fault vectors	p. 291
Latin squares	p. 292
Mutually orthogonal latin squares	p. 294
Pairwise design: binary factors	p. 296
Pairwise design: multivalued factors	p. 301
Shortcomings of using MOLS for test design	p. 309
Orthogonal arrays	p. 309
Mixed-level orthogonal arrays	p. 311
Covering and mixed-level covering arrays	p. 314
Covering arrays	p. 314
Mixed-level covering arrays	p. 314
Arrays of strength >2	p. 315
Generating covering arrays	p. 316
Summary	p. 326
Bibliographic Notes	p. 327
Exercises	p. 330
Test Selection, Minimizations, and Priaritization for Regression Testing	p. 335
What is regression testing?	p. 336
Regression-test process	p. 337
Test revalidation, selection, minimization, and prioritization	p. 338
Test setup	p. 339
Test sequencing	p. 340
Test execution	p. 342
Output comparison	p. 343
RTS: the problem	p. 343
Selecting regression tests	p. 344
Test all	p. 345
Random selection	p. 345
Selecting modification-traversing tests	p. 345
Test minimization	p. 346
Test prioritization	p. 347
Test selection using execution trace	p. 347
Obtaining the execution trace	p. 348
Selecting regression tests	p. 350
Handling function calls	p. 355
Handling changes in declarations	p. 355
Test selection using dynamic slicing	p. 358
Dynamic slicing	p. 360
Computation of dynamic slices	p. 360
Selecting tests	p. 362
Potential dependence	p. 363
Computing the relevant slice	p. 367
Addition and deletion of statements	p. 367
Identifying variables for slicing	p. 369
Reduced dynamic-dependence graph	p. 369
Scalability of test-selection algorithms	p. 371
Test minimization	p. 373
The set-cover problem	p. 374
A procedure for test minimization	p. 375
Test prioritization	p. 377
Tools for regression testing	p. 381
Summary	p. 384
Bibliographic Notes	p. 385
Exercises	p. 391
Test Adequacy Assessment and Enhancement	p. 399
Test Adequacy: Assessment using Control Flow and Data Flow	p. 401
Test adequacy: basics	p. 402
What is test adequacy?	p. 402
Measurement of test adequacy	p. 403
Test enhancement using measurements of adequacy	p. 405
Infeasibility and test adequacy	p. 409
Error detection and test enhancement	p. 411
Single and multiple executions	p. 414
Adequacy criteria based on control flow	p. 415
Statement and block coverage	p. 415
Conditions and decisions	p. 418
Decision coverage	p. 420
Condition coverage	p. 422
Condition/decision coverage	p. 424
Multiple condition coverage	p. 426
Linear code sequence and jump (LCSAJ) coverage	p. 429
Modified condition/decision coverage	p. 433
MC/DC-adequate tests for compound conditions	p. 434
Definition of MC/DC coverage	p. 440
Minimal MC/DC tests	p. 448
Error detection and MC/DC adequacy	p. 448
Short-circuit evaluation and infeasibility	p. 450
Tracing test cases to requirements	p. 452
Data-flow concepts	p. 454
Definitions and uses	p. 455
c-use and p-use	p. 456
Global and local definitions and uses	p. 457
Data-flow graph	p. 458
Def-clear paths	p. 460
Def-use pairs	p. 461
Def-use chains	p. 462
A little optimization	p. 463
Data contexts and ordered data contexts	p. 464
Adequacy criteria based on data flow	p. 467
c-use coverage	p. 468
p-use coverage	p. 469
all-uses coverage	p. 471
k-dr chain coverage	p. 471
Using the k-dr chain coverage	p. 473
Infeasible c-uses and p-uses	p. 474
Context coverage	p. 475
Control flow versus data flow	p. 478
The subsumes relation	p. 480
Structural and functional testing	p. 482
Scalability of coverage measurement	p. 483
Summary	p. 486
Bibliographic Notes	p. 487
Exercises	p. 494
Test-Adequacy Assessment Using Program Mutation	p. 502
Introduction	p. 503
Mutation and mutants	p. 504
First-order and higher-order mutants	p. 505
Syntax and semantics of mutants	p. 506
Strong and weak mutations	p. 509
Why mutate?	p. 511
Test assessment using mutation	p. 512
A procedure for test-adequacy assessment	p. 512
Alternate procedures for test-adequacy assessment	p. 520
Distinguished versus killed mutants	p. 521
Conditions for distinguishing a mutant	p. 522
Mutation operators	p. 524
Operator types	p. 525
Language dependence of mutation operators	p. 527
Design of mutation operators	p. 529
Goodness criteria for mutation operators	p. 529
Guidelines	p. 530
Founding principles of mutation testing	p. 531
The competent programmer hypothesis	p. 531
The coupling effect	p. 532
Equivalent mutants	p. 532
Fault detection using mutation	p. 533
Types of mutants	p. 536
Mutation operators for C	p. 537
What is not mutated?	p. 537
Linearization	p. 538
Execution sequence	p. 540
Effect of an execution sequence	p. 543
Global and local identifier sets	p. 544
Global and local reference sets	p. 544
Mutating program constants	p. 547
Mutating operators	p. 549
Mutating statements	p. 555
Mutating program variables	p. 570
Mutation operators for java	p. 575
Traditional mutation operators	p. 577
Inheritence	p. 578
Polymorphism and dynamic binding	p. 581
Method overloading	p. 582
Java-specific mutation operators	p. 584
Mutation operators for fortran 77, C, and java: a comparison	p. 585
Tools for mutation testing	p. 588
Mutation testing within budget	p. 590
Prioritizing functions to be mutated	p. 590
Selecting a subset of mutation operators	p. 591
Summary	p. 593
Bibliographic Notes	p. 594
Exercises	p. 606
References	p. 615
Subject Index	p. 653
Name Index	p. 685
Table of Contents provided by Ingram. All Rights Reserved.