introtest CUUS047-Ammann ISBN 9780521880381 December 6, 2007 2:42 Char Count= 0 This page intentionally left blank i introtest CUUS047-Ammann ISBN 9780521880381 December 6, 2007 2:42 Char Count= 0 Introduction to Software Testing Extensively class tested, this text takes an innovative approach to soft- ware testing: it defines testing as the process of applying a few well- defined, general-purpose test criteria to a structure or model of the soft- ware. The structure of the text directly reflects the pedagogical approach and incorporates the latest innovations in testing, including modern types of software such as OO, Web applications, and embedded software. The book contains numerous examples throughout. An instructor’s solution manual, PowerPoint slides, sample syllabi, additional examples and up- dates, testing tools for students, and example software programs in Java are available on an extensive Web site at www.
Paul Ammann, PhD, is an Associate Professor of software engineer- ing at George Mason University. He received an outstanding teaching award in 2007 from the Volgenau School of Information Technology and Engineering. Ammann earned an AB degree in computer science from Dartmouth College and MS and PhD degrees in computer science from the University of Virginia. Jeff Offutt, PhD, is a Professor of software engineering at George Mason University.
He is editor-in-chief of the Journal of Software Testing, Verification and Reliability; chair of the steering committee for the IEEE International Conference on Software Testing, Verification, and Valida- tion; and on the editorial boards for several journals. He recived the outstanding teacher award from the Volgenau School of Information Technology and Engineering in 2003. Offutt earned a BS degree in mathematics and data processing from Morehead State University and MS and PhD degrees in computer science from the Georgia Institute of Technology. i introtest CUUS047-Ammann ISBN 9780521880381 December 6, 2007 2:42 Char Count= 0 ii introtest CUUS047-Ammann ISBN 9780521880381 December 6, 2007 2:42 Char Count= 0 INTRODUCTION TO SOFTWARE TESTING Paul Ammann George Mason University Jeff Offutt George Mason University iii CAMBRIDGE UNIVERSITY PRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo Cambridge University Press The Edinburgh Building, Cambridge CB2 8RU, UK Published in the United States of America by Cambridge University Press, New York www.org Information on this title: www.org/9780521880381 © Paul Ammann and Jeff Offutt 2008 This publication is in copyright.
Subject to statutory exception and to the provision of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published in print format 2008 ISBN-13 978-0-511-39330-3 eBook (EBL) ISBN-13 978-0-521-88038-1 hardback Cambridge University Press has no responsibility for the persistence or accuracy of urls for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate. introtest CUUS047-Ammann ISBN 9780521880381 December 6, 2007 2:42 Char Count= 0 Contents List of Figures page ix List of Tables xiii Preface xv Part 1 Overview 1 1 Introduction 3 1.1 Activities of a Test Engineer 4 1.1 Testing Levels Based on Software Activity 5 1.2 Beizer’s Testing Levels Based on Test Process Maturity 8 1.3 Automation of Test Activities 10 1.2 Software Testing Limitations and Terminology 11 1.3 Coverage Criteria for Testing 16 1.1 Infeasibility and Subsumption 20 1.2 Characteristics of a Good Coverage Criterion 20 1.4 Older Software Testing Terminology 21 1.5 Bibliographic Notes 22 Part 2 Coverage Criteria 25 2 Graph Coverage 27 2.2 Graph Coverage Criteria 32 2.1 Structural Coverage Criteria 33 2.2 Data Flow Criteria 44 2.3 Subsumption Relationships among Graph Coverage Criteria 50 2.3 Graph Coverage for Source Code 52 v introtest CUUS047-Ammann ISBN 9780521880381 December 6, 2007 2:42 Char Count= 0 vi Contents 2.1 Structural Graph Coverage for Source Code 52 2.2 Data Flow Graph Coverage for Source Code 54 2.4 Graph Coverage for Design Elements 65 2.1 Structural Graph Coverage for Design Elements 65 2.2 Data Flow Graph Coverage for Design Elements 67 2.5 Graph Coverage for Specifications 75 2.1 Testing Sequencing Constraints 75 2.2 Testing State Behavior of Software 77 2.6 Graph Coverage for Use Cases 87 2.1 Use Case Scenarios 90 2.7 Representing Graphs Algebraically 91 2.1 Reducing Graphs to Path Expressions 94 2.2 Applications of Path Expressions 96 2.3 Deriving Test Inputs 96 2.4 Counting Paths in a Flow Graph and Determining Max Path Length 97 2.5 Minimum Number of Paths to Reach All Edges 98 2.6 Complementary Operations Analysis 98 2.8 Bibliographic Notes 100 3 Logic Coverage 104 3.1 Overview: Logic Predicates and Clauses 104 3.2 Logic Expression Coverage Criteria 106 3.1 Active Clause Coverage 107 3.2 Inactive Clause Coverage 111 3.3 Infeasibility and Subsumption 112 3.4 Making a Clause Determine a Predicate 113 3.5 Finding Satisfying Values 115 3.3 Structural Logic Coverage of Programs 120 3.1 Predicate Transformation Issues 127 3.4 Specification-Based Logic Coverage 131 3.5 Logic Coverage of Finite State Machines 134 3.6 Disjunctive Normal Form Criteria 138 3.7 Bibliographic Notes 147 4 Input Space Partitioning 150 4.1 Input Domain Modeling 152 4.1 Interface-Based Input Domain Modeling 153 4.2 Functionality-Based Input Domain Modeling 154 4.4 Choosing Blocks and Values 156 4.5 Using More than One Input Domain Model 158 4.6 Checking the Input Domain Model 158 4.2 Combination Strategies Criteria 160 4.3 Constraints among Partitions 165 4.4 Bibliographic Notes 166 introtest CUUS047-Ammann ISBN 9780521880381 December 6, 2007 2:42 Char Count= 0 Contents vii 5 Syntax-Based Testing 170 5.1 Syntax-Based Coverage Criteria 170 5.1 BNF Coverage Criteria 170 5.2 Program-Based Grammars 176 5.1 BNF Grammars for Languages 176 5.2 Program-Based Mutation 176 5.3 Integration and Object-Oriented Testing 191 5.1 BNF Integration Testing 192 5.4 Specification-Based Grammars 197 5.2 Specification-Based Mutation 198 5.5 Input Space Grammars 201 5.2 Mutation for Input Grammars 204 5.6 Bibliographic Notes 210 Part 3 Applying Criteria in Practice 213 6 Practical Considerations 215 6.2 Integration and Testing 217 6.1 Stubs and Drivers 218 6.2 Class Integration Test Order 218 6.1 Requirements Analysis and Specification 220 6.2 System and Software Design 221 6.8 Operation and Maintenance 224 6.5 Identifying Correct Outputs 230 6.1 Direct Verification of Outputs 230 6.6 Bibliographic Notes 233 7 Engineering Criteria for Technologies 235 7.1 Testing Object-Oriented Software 236 7.1 Unique Issues with Testing OO Software 237 introtest CUUS047-Ammann ISBN 9780521880381 December 6, 2007 2:42 Char Count= 0 viii Contents 7.2 Types of Object-Oriented Faults 237 7.2 Testing Web Applications and Web Services 256 7.1 Testing Static Hyper Text Web Sites 257 7.2 Testing Dynamic Web Applications 257 7.3 Testing Web Services 260 7.3 Testing Graphical User Interfaces 260 7.4 Real-Time Software and Embedded Software 262 7.5 Bibliographic Notes 265 8 Building Testing Tools 268 8.1 Instrumentation for Graph and Logical Expression Criteria 268 8.1 Node and Edge Coverage 268 8.2 Data Flow Coverage 271 8.2 Building Mutation Testing Tools 272 8.1 The Interpretation Approach 274 8.2 The Separate Compilation Approach 274 8.3 The Schema-Based Approach 275 8.4 Using Java Reflection 276 8.5 Implementing a Modern Mutation System 277 8.3 Bibliographic Notes 277 9 Challenges in Testing Software 280 9.1 Testing for Emergent Properties: Safety and Security 280 9.1 Classes of Test Cases for Emergent Properties 283 9.1 Testability for Common Technologies 285 9.3 Test Criteria and the Future of Software Testing 286 9.1 Going Forward with Testing Research 288 9.4 Bibliographic Notes 290 List of Criteria 293 Bibliography 295 Index 319 introtest CUUS047-Ammann ISBN 9780521880381 December 6, 2007 2:42 Char Count= 0 List of Figures 1.1 Activities of test engineers page 4 1.2 Software development activities and testing levels – the “V Model” 6 2.1 Graph (a) has a single initial node, graph (b) multiple initial nodes, and graph (c) (rejected) with no initial nodes 28 2.2 Example of paths 29 2.3 A single entry single exit graph 30 2.4 Test case mappings to test paths 31 2.5 A set of test cases and corresponding test paths 32 2.6 A graph showing node coverage and edge coverage 34 2.7 Two graphs showing prime path coverage 37 2.8 Graph with a loop 37 2.9 Tours, sidetrips, and detours in graph coverage 38 2.10 An example for prime test paths 40 2.11 A graph showing variables, def sets and use sets 44 2.12 A graph showing an example of du-paths 46 2.13 Graph showing explicit def and use sets 47 2.14 Example of the differences among the three data flow coverage criteria 49 2.15 Subsumption relations among graph coverage criteria 50 2.16 CFG fragment for the if-else structure 52 2.17 CFG fragment for the if structure without an else 53 2.18 CFG fragment for the while loop structure 53 2.19 CFG fragment for the for loop structure 54 2.20 CFG fragment for the case structure 54 2.21 TestPat for data flow example 56 2.22 A simple call graph 65 2.23 A simple inheritance hierarchy 66 2.24 An inheritance hierarchy with objects instantiated 67 2.25 An example of parameter coupling 68 2.26 Coupling du-pairs 69 2.27 Last-defs and first-uses 69 ix introtest CUUS047-Ammann ISBN 9780521880381 December 6, 2007 2:42 Char Count= 0 x List of Figures 2.28 Quadratic root program 71 2.29 Def-use pairs under intra-procedural and inter-procedural data flow 72 2.30 Def-use pairs in object-oriented software 72 2.31 Def-use pairs in web applications and other distributed software 73 2.32 Control flow graph using the File ADT 76 2.33 Elevator door open transition 79 2.36 A FSM representing Stutter, based on control flow graphs of the methods 82 2.37 A FSM representing Stutter, based on the structure of the software 83 2.38 A FSM representing Stutter, based on modeling state variables 84 2.39 A FSM representing Stutter, based on the specifications 85 2.40 Class Queue for exercises.41 ATM actor and use cases 88 2.42 Activity graph for ATM withdraw funds 90 2.43 Examples of path products 92 2.44 Null path that leads to additive identity φ 93 2.46 Example graph to show reduction to path expressions 94 2.47 After step 1 in path expression reduction 95 2.48 After step 2 in path expression reduction 95 2.49 After step 3 in path expression reduction 95 2.50 Removing arbitrary nodes 95 2.52 Removing sequential edges 95 2.53 Removing self-loop edges 96 2.54 Final graph with one path expression 96 2.55 Graph example for computing maximum number of paths 97 2.56 Graph example for complementary path analysis 99 3.1 Subsumption relations among logic coverage criteria 113 3.5 FSM for a memory car seat – Lexus 2003 ES300 135 3.6 Fault detection relationships 143 4.1 Partitioning of input domain D into three blocks 151 4.2 Subsumption relations among input space partitioning criteria 163 5.1 Method Min and six mutants 177 5.2 Mutation testing process 181 5.3 Partial truth table for (a ∧ b) 187 5.4 Finite state machine for SMV specification 199 5.5 Mutated finite state machine for SMV specification 200 5.6 Finite state machine for bank example 202 5.7 Finite state machine for bank example grammar 202 5.8 Simple XML message for books 204 5.9 XML schema for books 205 introtest CUUS047-Ammann ISBN 9780521880381 December 6, 2007 2:42 Char Count= 0 List of Figures xi 7.1 Example class hierarchy in UML 238 7.2 Data flow anomalies with polymorphism 238 7.3 Calls to d() when object has various actual types 239 7.4 ITU: Descendant with no overriding methods 241 7.5 SDA, SDIH: State definition anomalies 243 7.6 IISD: Example of indirect inconsistent state definition 244 7.7 ACB1: Example of anomalous construction behavior 245 7.8 SVA: State visibility anomaly 247 7.9 Sample class hierarchy (a) and associated type families (b) 248 7.10 Control flow graph fragment (a) and associated definitions and uses (b) 249 7.11 Def-use pairs in object-oriented software 250 7.12 Control flow schematic for prototypical coupling sequence 251 7.13 Sample class hierarchy and def-use table 252 7.14 Coupling sequence: o of type A (a) bound to instance of A (b), B (c) or C (d) 253 8.2 Node coverage instrumentation 269 8.3 Edge coverage instrumentation 270 8.4 All uses coverage instrumentation 271 8.