Software Testing and Analysis Process Principles and Techniques

–

BusAc

CP > CT2

–

T T

Constraints at-most-one(EduAc, BusAc)

at-most-one(YP YT2)

YP > YT2 ↠ YP > YT1

at-most-one(CP CT2)

CP > CT2 ↠ CP > CT1

at-most-one(SP T2)

SP > T2 ↠ SP > T1 Abbreviations EduAc

Educational account

Edu

Educational price

BusAc

Business account

No discount

CP > CT1

Current purchase greater than threshold 1

Tier 1

Tier 2

Special Price

YP > YT1 CP > CT2

Year cumulative purchase greater than threshold 1 Current purchase greater than threshold 2

YP > YT2

Year cumulative purchase greater than threshold 2

SP > Sc

Special Price better than scheduled price

SP > T1

Special Price better than tier 1

SP > T2 Special Price better than tier 2 Open table as spreadsheet Figure 14.4: A decision table for the functional specification of feature Pricing of the Chipmunk Web site of Figure 14.3. The informal specification of Figure 14.3 identifies three customer profiles: educational, business, and individual. Figure 14.4 has only rows Educational account (EduAc) and Business account (BusAc). The choice individual corresponds to the combination False, False for choices EduAc and BusAc, and is thus redundant. The informal specification of Figure 14.3 indicates different discount policies depending on the relation between the current purchase and two progressive thresholds for the current purchase and the yearly cumulative purchase. These cases correspond to rows 3 through 6 of Figure 14.4. Conditions on thresholds that do not correspond to individual rows in the table can be defined by suitable combinations of values for these rows. Finally, the informal specification of Figure 14.3 distinguishes the cases in which special offer prices do not exceed either the scheduled or the tier 1 or tier 2 prices. Rows 7 through 9 of the table, suitably combined, capture all possible cases of special prices without redundancy. Constraints formalize the compatibility relations among different basic conditions listed in the table. For example, a cumulative purchase exceeding threshold tier 2 also exceeds threshold tier 1. The basic condition adequacy criterion requires generation of a test case specification for each column in the table. Don’t care entries of the table can be filled out arbitrarily, as long as constraints are not violated. The compound condition adequacy criterion requires a test case specification for each combination of truth values of basic conditions. The compound condition adequacy criterion generates a number of cases exponential in the number of basic conditions (2n combinations for n conditions) and can thus be applied only to small sets of basic conditions. For the modified condition/decision adequacy criterion (MC/DC), each column in the table represents a test case specification. In addition, for each of the original columns, MC/DC generates new columns by modifying each of the cells containing True or False. If modifying a truth value in one column results in a test case specifi∆ modified condition/decision coverage cation consistent with an existing column (agreeing in all places where neither is don’t care), the two test cases are represented by one merged column, provided they can be merged without violating constraints.

The MC/DC criterion formalizes the intuitive idea that a thorough test suite would not only test positive combinations of values – combinations that lead to specified outputs – but also negative combinations of values – combinations that differ from the specified ones – thus, they should produce different outputs, in some cases among the specified ones, in some other cases leading to error conditions. Applying MC/DC to column 1 of Figure 14.4 generates two additional columns: one for Educational Account = False and Special Price better than scheduled price = False, and the other for Educational Account = True and Special Price better than scheduled price = True. Both columns are already in the table (columns 3 and 2, respectively) and thus need not be added. Similarly, from column 2, we generate two additional columns corresponding to Educational Account = False and Special Price better than scheduled price = True, and Educational Account = True and Special Price better than scheduled price = False, also already in the table. Generation of a new column for each possible variation of the Boolean values in the columns, varying exactly one value for each new column, produces 78 new columns, 21 of which can be merged with columns already in the table. Figure 14.5 shows a table obtained by suitably joining the generated columns with the existing ones. Many don’t care cells from the original table are assigned either True or False values, to allow merging of different columns or to obey constraints. The few don’t-care entries left can be set randomly to obtain a complete test case. EduAc

BusAc

CP > CT1

YP > YT1

–

CP > CT2

YP > YT2

–

SP > Sc

–

SP > T1

–

SP >

T2 Out Edu SP ND Open table as spreadsheet

EduAc

–

BusAc

CP > CT1

–

YP > YT1

–

CP > CT2

YP > YT2

–

SP > Sc

–

SP > T1

–

SP > T2

–

Edu

Out SP T2 SP Open table as spreadsheet

Abbreviations EduAc

Educational account

Edu

Educational price

BusAc

Business account

No discount

CP > CT1

Current purchase greater than threshold 1

Tier 1

Tier 2

Special Price

YP > YT1 CP > CT2 YP > YT2

Year cumulative purchase greater than threshold 1 Current purchase greater than threshold 2 Year cumulative purchase greater than threshold

SP > Sc

Special Price better than scheduled price

SP > T1

Special Price better than tier 1

SP > T2 Special Price better than tier 2 Open table as spreadsheet Figure 14.5: The set of test cases generated for feature Pricing of the Chipmunk Web site applying the modified adequacy criterion. There are many ways of merging columns that generate different tables. The table in Figure 14.5 may not be the optimal one – the one with the fewest columns. The objective in test design is not to find an optimal test suite, but rather to produce a cost effective test suite with an acceptable trade-off between the cost of generating and executing test cases and the effectiveness of the tests. The table in Figure 14.5 fixes the entries as required by the constraints, while the initial table in Figure 14.4 does not. Keeping constraints separate from the table corresponding to the initial specification increases the number of don’t care entries in the original table, which in turn increases the opportunity for merging columns when generating new cases with the MC/DC criterion. For example, if business account (BusAc) = False, the constraint at-mostone(EduAc, BusAc) can be satisfied by assigning either True or False to entry educational account. Fixing either choice prematurely may later make merging with a newly generated column impossible. [2]The set of columns sharing a label is therefore equivalent to a logical

expression in sum-of-productsform.

14.4 Deriving Test Cases from Control and Data Flow Graphs Functional specifications are seldom given as control or data flow graphs, but sometimes they describe a set of mutually dependent steps to be executed in a given (partial) order, and can thus be modeled with flow graphs. The specification in Figure 14.6 describes the Chipmunk functionality that prepares orders for shipping. The specification indicates a set of steps to check the validity of fields in the order form. Type and validity of some of the values depend on other fields in the form. For example, shipping methods are different for domestic and international customers, and payment methods depend on customer type. Process shipping order The Process shipping order function checks the validity of orders and prepares the receipt. A valid order contains the following data: cost of goods If the cost of goods is less than the minimum processable order (MinOrder), then the order is invalid. shipping address The address includes name, address, city, postal code, and country. preferred shipping method If the address is domestic, the shipping method must be either land freight,or expedited land freight,or overnight air.If the address is international, the shipping method must be either air freight or expedited air freight; a shipping cost is computed based on address and shipping method. type of customer A customer can be individual, business,or educational. preferred method of payment Individual customers can use only credit cards, while business and educational customers can choose between credit card and invoice. card information If the method of payment is credit card, fields credit card number, name on card, expiration date, and billing address, if different from shipping address, must be provided. If credit card information is not valid, the user can either provide new data or abort the order. The outputs of Process shipping order are validity Validity is a Boolean output that indicates whether the order can be processed. total charge The total charge is the sum of the value of goods and the computed

shipping costs (only if validity = true). payment status If all data are processed correctly and the credit card information is valid or the payment method is by invoice, payment status is set to valid, the order is entered, and a receipt is prepared; otherwise validity = false. Figure 14.6: Functional specification of the feature Process shipping order of the Chipmunk Web site. The informal specification in Figure 14.6 can be modeled with a control flow graph, where the nodes represent computations and branches represent control flow consistent with the dependencies among computations, as illustrated in Figure 14.7. Given a control or a data flow graph model, we can generate test case specifications using the criteria originally devised for structural testing and described in Chapters 12 and 13.

Figure 14.7: A control flow graph model corresponding to functionality Process shipping order of Figure 14.6. Control flow testing criteria require test cases that exercise all elements of a particular kind in a graph model. The node adequacy criterion requires each node to be exercised at least once, and corresponds to statement testing. It is easy to verify that ∆ node adequacy criterion test suite T-node in Figure 14.8, consisting of test case specifications TC-1 and TC-2, causes all nodes of the control flow graph of Figure 14.7 to be traversed, and thus Tnode satisfies the node adequacy criterion. T-node Open table as spreadsheet Case

Too

Ship

Cust

Pay

Same

small

where

method

type

method

addr

valid

TC-1

Int

Air

Bus

TC-2

Dom

Air

Ind

–

Yes No (abort)

Abbreviations: Too small

CostOfGoods

Ship where

Shipping address, Int = international, Dom = domestic

Ship how

Air = air freight, Land = land freight

Cust type

Bus = business, Edu = educational, Ind = individual

Pay method

CC = credit card, Inv = invoice

Same addr

Billing address = shipping address ?

CC Valid

Credit card information passes validity check?

Figure 14.8: Test suite T-node, comprising test case specifications TC-1 and TC-2, exercises each of the nodes in a control flow graph model of the specification in Figure 14.6. The branch adequacy criterion requires each branch to be exercised at least once: each edge of the graph must be traversed by at least one test case. Test suite T-branch (Figure 14.9) covers all branches of the control flow graph of Figure 14.7 and thus satisfies the branch adequacy criterion. T-branch Open table as spreadsheet Case

Too

Ship

Cust

Pay

Same

small

where

method

type

method

addr

valid

TC-1

Int

Air

Bus

Yes

TC-2

Dom

Land

–

TC-3

Yes

–

TC-4

Dom

Air

–

Edu

Inv

–

Yes

–

No (abort)

–

No (no abort)

TC-5

Int

TC-6

–

TC-7

TC-8 TC-9

Land

Abbreviations: Too small Ship where

CostOfGoods

Ship how

Air = air freight, Land = land freight

Cust type

Bus = business, Edu = educational, Ind = individual

Pay method

CC = credit card, Inv = invoice

Same addr

Billing address = shipping address ?

CC Valid

Credit card information passes validity check?

Figure 14.9: Test suite T-branch exercises each of the decision outcomes in a control flow graph model of the specification in Figure 14.6. In principle, other test adequacy criteria described in Chapters 12 and 13 can be applied to more complex control structures derived from specifications, such as loops. A good functional specification should rarely result in a complex control structure, but data flow testing may be useful at a much coarser structure (e.g., to test interaction of transactions through a database).

14.5 Deriving Test Cases from Grammars Functional specifications for complex documents or domain-specific notations, as well as for conventional compilers and interpreters, are often structured as an annotated grammar or set of regular expressions. Test suites can be systematically derived from these grammatical structures. The informal specification of the Chipmunk Web site advanced search, shown in Figure 14.10, defines the syntax of a search pattern. Not surprisingly, this specification can easily be expressed as a grammar. Figure 14.11 expresses the specification as a grammar in Backus Naur Form (BNF). Advanced search The Advanced search function allows for searching elements in the Web site database. The key for searching can be: a simple string, i.e., a simple sequence of characters a compound string, i.e., a string terminated with character *, used as wild character, or a string composed of substrings included in braces and separated with commas, used to indicate alternatives a combination of strings, i.e., a set of strings combined with the Boolean operators NOT, AND, OR, and grouped within parentheses to change the priority of operators. Examples: laptop The routine searches for string “laptop” {DVD*,CD*} The routine searches for strings that start with substring “DVD” or “CD” followed by any number of characters. NOT (C2021*) AND C20* The routine searches for strings that start with substring “C20” followed by any number of characters, except substring “21.” Figure 14.10: Functional specification of the feature Advanced search of the Chipmunk Web site.

Figure 14.11: BNF description of functionality Advanced search A second example is given in Figure 14.12, which specifies a product configuration of the Chipmunk Web site. In this case, the syntactic structure of product configuration is described by an XML schema, which defines an element Model of type ProductConfigurationType. XML schemata are essentially a variant of BNF, so it is not difficult to render the schema in the same BNF notation, as shown in Figure 14.11. 2 3 4 5 6 Chipmunk Computers – Product Configuration Schema 7 Copyright 2001 D. Seville, Chipmunk Computers Inc. 8 9 10 11 12 13 14 16 18 19 20 21 22 23 25 26 27 28 1

Figure 14.12: An XML schema description of a Product configuration on the Chipmuk Web site. Items are enclosed in matching tags (〈tag〉 text 〈/tag〉) or incorporated in

a self-terminating tag (〈tag attribute=”value” /〉). The schema describes type ProductConfigurationType as a tuple composed of a required field modelNumber of type string; a set (possibly empty) of Components, each of which is composed of two stringvalued fields ComponentType and ComponentValue; and a possibly empty set of OptionalComponents, each of which is composed of a single string-valued ComponentType. Grammars are well suited to represent inputs of varying and unbounded size, with recursive structures and boundary conditions. These characteristics are not easily addressed with the fixed lists of parameters required by conventional combinatoric techniques described in Chapter 11, or by other model-based techniques presented in this chapter. Generating test cases from grammar specifications is straightforward and can easily be automated. Each test case is a string generated from the grammar. To produce a string, we start from a non terminal symbol and progressively apply productions to substitute substrings for non terminals occurring in the current string, until we obtain a string composed only of terminal symbols. In general, we must choose among several applicable production rules at each step. A simple criterion requires each production to be exercised at least once in producing a set of test cases. The number and complexity of the generated test cases depend on the order of application of the productions. If we first apply productions with non terminals on the right-hand side, we generate a smaller set of large test cases. First applying productions with only terminals on the right-hand side generates larger sets of smaller test cases. An algorithm that favors non terminals applied to the BNF for advanced search of Figure 14.10, exercises all the productions to generate the single test case not Char {*, Char} and (Char or Char) The derivation tree for this test case is given in Figure 14.14. It shows that each production of the BNF is exercised at least once.

Figure 14.14: The derivation tree of a test case for functionality Advanced Search derived from the BNF specification of Figure 14.11. The simple production coverage criterion is subsumed by a richer criterion that applies boundary conditions on the number of times each recursive production is applied successively. To generate test cases for boundary conditions we need to choose a minimum and maximum number of applications of each recursive production and then generate a test case for the minimum, maximum, one greater than minimum and one smaller than maximum. The approach is essentially similar to boundary interior path testing of program loops (see Section 12.5 of Chapter 12, page 222), where the “loop” in this case is in repeated applications of a production. To apply the boundary condition criterion, we need to annotate recursive productions with limits. Names and limits are shown in Figure 14.15, which extends the grammar of Figure 14.13. Alternatives within compound productions are broken out into individual productions. Production names are added for reference, and limits are added to recursive productions. In the example of Figure 14.15, the limit of productions compSeq1 and optCompSeq1 is set to 16; we assume that each model can have at most 16 required and 16 optional components.

Figure 14.13: BNF description of Product configuration.

Figure 14.15: The BNF description of Product Configuration extended with production names and limits. The boundary condition grammar-based criterion would extend the minimal set by adding test cases that cover the following choices: zero required components (compSeq1 applied 0 times) one required component (compSeq1 applied 1 time) fifteen required components (compSeq1 applied n – 1 times) sixteen required components (compSeq1 applied n times) zero optional components (optCompSeq1 applied 0 times) one optional component (optCompSeq1 applied 1 time) fifteen optional components (optCompSeq1 applied n – 1 times) sixteen optional components (optCompSeq1 applied n times) Probabilistic grammar-based criteria assign probabilities to productions, indicating which production to select at each step to generate test cases. Unlike names and limits, probabilities are attached to grammar productions as a separate set of annotations. We can generate several sets of test cases from the same grammar with different sets of probabilities, called “seeds.” Figure 14.16 shows a sample seed for the grammar that specifies the product configuration functionality of the Chipmunk Web site presented in Figure 14.15. weight

Model

weight

compSeq1

weight

compSeq2

weight

optCompSeq1

weight

optCompSeq2

weight

Comp

weight

OptComp

weight

modNum

weight

CompTyp

weight

CompVal

Figure 14.16: Sample seed probabilities for BNF productions of Product configuration. Probabilities are interpreted as weights that determine how frequently each production is used to generate a test case. The equal weight for compSeq1 and optCompSeq1 in Figure 14.16 indicates that test cases are generated by balancing use of these two productions; they contain approximately the same number of required and optional components. Weight 0 disables the productions, which are then applied only when application of competing productions reaches the limit indicated in the grammar.

Open Research Issues As long as there have been models of software, there has been model-based testing. A recent and ongoing ferment of activity in model-based testing is partly the result of wider use of models throughout software development. Ongoing research will certainly include test design based on software architecture, domain-specific models, and models of emerging classes of systems such as service-oriented architectures and adaptive systems, as well as additional classes of systems and models that we cannot yet anticipate. As well as following the general trend toward greater use of models in development, though, research in model-based testing reflects greater understanding of the special role that models of software can play in test design and in combining conventional testing with analysis. A model is often the best way – perhaps the only way – to divide one property to be verified into two, one part that is best verified with static analysis and another part that is best verified with testing. Conformance testing of all kinds exploits models in this way, focusing analysis techniques where they are most necessary (e.g., nondeterministic scheduling decisions in concurrent software) and using testing to cost-effectively verify consistency between model and program. Models are also used to specify and describe system structure at levels of organization beyond those that are directly accommodated in conventional programming languages (e.g., components and subsystems). Analysis, and to a lesser extent testing, have been explicit concerns in development of architecture description languages. Still there remains a divide between models developed primarily for people to communicate and record design decisions (e.g., UML) and models developed primarily for verification (e.g., various FSM notations). Today we see a good deal of research re-purposing design models for test design, which involves adding or disambiguating the semantics of notations intended for human communication. A challenge for future design notations is to provide a better foundation for analysis and testing without sacrificing the characteristics that make them useful for communicating and recording design decisions. An important issue in modeling, and by extension in model-based testing, is how to use

multiple model “views” to together form a comprehensive model of a program. More work is needed on test design that uses more than one modeling view, or on the potential interplay between test specifications derived from different model views of the same program. As with many other areas of software testing and analysis, more empirical research is also needed to characterize the cost and effectiveness of model-based testing approaches. Perhaps even more than in other areas of testing research, this is not only a matter of carrying out experiments and case studies, but is at least as much a matter of understanding how to pose questions that can be effectively answered by experiments and whose answers generalize in useful ways.

Further Reading Myers’ classic text [Mye79] describes a number of techniques for testing decision structures. Richardson, O’Malley, and Tittle [ROT89] and Stocks and Carrington [SC96] among others attempt to generate test cases based on the structure of (formal) specifications. Beizer’s Black Box Testing [Bei95] is a popular presentation of techniques for testing based on control and data flow structure of (informal) specifications. Test design based on finite state machines has long been important in the domain of communication protocol development and conformance testing; Fujiwara, von Bochmann, Amalou, and Ghedamsi [FvBK+91] is a good introduction. Gargantini and Heitmeyer [GH99] describe a related approach applicable to software systems in which the finite state machine is not explicit but can be derived from a requirements specification. Generating test suites from context-free grammars is described by Celentano et al. [CCD+80] and apparently goes back at least to Hanford’s test generator for an IBM PL/I compiler [Han70]. The probabilistic approach to grammar-based testing is described by Sirer and Bershad [SB99], who use annotated grammars to systematically generate tests for Java virtual machine implementations. Heimdahl et al. [HDW04] provide a cautionary note regarding how naive model-based testing can go wrong, while a case study by Pretschner et al. [PPW+05] suggests that model based testing is particularly effective in revealing errors in informal specifications.

Related Topics Readers interested in testing based on finite state machines may proceed to Chapter 15, in which finite state models are applied to testing object-oriented programs.

Exercises Derive sets of test cases for functionality Maintenance from the FSM specification in Figure 14.2. 1. Derive a test suite that satisfies the Transition Coverage criterion.

2. Derive a test suite that satisfies the Single State Path Coverage criterion.

14.1

3. Indicate at least one element of the program that must be covered by a test suite satisfying the Single Transition Path Coverage, but need not be covered by a test suite that satisfies the Single State Path Coverage criterion. Derive a test case that covers that element. 4. Describe at least one element that must be covered by a test suite that satisfies both the Single Transition Path Coverage and Boundary Interior Loop Coverage criteria, but need not be covered by a test suite that satisfies the Transition Coverage and Single State Path Coverage criteria. Derive testsuite casederived that covers that element. Discuss how the atest for functionality Maintenance applying Transition

14.2

14.3

Coverage to the FSM specification of Figure 14.2 (Exercise 14.1) must be modified under the following assumptions. 1. How must it be modified if the implicit transitions ar error conditions? 2. How must it be modified if the implicit transitions are self-transitions? Finite state machine specifications are often augumented with variables that may be tested and changed by state transitions. The same system can often be described by a machine with more or fewer states, depending on how much information is represented by the states themselves and how much is represented by extra variables. For example, in Figure 5.9 (page 69), the state of the buffer (empty or not) is represented directly by the states, but we could also represent that information with a variable empty and merge states Empty buffer and Within line of the finite state machine into a single Gathering state to obtain a more compact finite state machine, as in this diagram:

For the following questions, consider only scalar variables with a limited set of possible values, like the Boolean variable empty in the example. 1. How can we systematically transform a test case for one version of the specification into a test suite for the other? Under what conditions is this transformation possible? Consider transformation in both directions, merging states by adding variables and splitting states to omit variables.

2. If a test suite satisfies the transition coverage criterion for the version with more states, will a corresponding test suite (converting each test case as you described in part (a)) necessarily satisfy the transition coverage criterion for the version with a suite that satisfies the transition coverage criterion for the version with fewer states? 3. Conversely, if a test suite satisfies the transition coverage criterion for the version of the specification with fewer states, will a corresponding test suite (converted as you described in part (a)) necessarily satisfy the transition coverage criterion for the version with more states? 4. How might you combine transition coverage with decision structure testing methods to select test suites independently from the information coded explicitly in the states or implicitly in the state variable?

Chapter 15: Testing Object-Oriented Software Systematic testing of object-oriented software is fundamentally similar to systematic testing approaches for procedural software: We begin with functional tests based on specification of intended behavior, add selected structural test cases based on the software structure, and work from unit testing and small-scale integration testing toward larger integration and then system testing. Nonetheless, the differences between procedural software and objectoriented software are sufficient to make specialized techniques appropriate.

Required Background Chapters 11, 12, 13, and 14 This chapter builds on basic functional, structural, and model-based testing techniques, including data flow testing techniques. Some basic techniques, described more thoroughly in earlier chapters, are recapped very briefly here to provide flexibility in reading order. Chapter 5 Many of the techniques described here employ finite state machines for modeling object state.

15.1 Overview Object-oriented software differs sufficiently from procedural software to justify reconsidering and adapting approaches to software test and analysis. For example, methods in objectoriented software are typically shorter than procedures in other software, so faults in complex intraprocedural logic and control flow occur less often and merit less attention in testing. On the other hand, short methods together with encapsulation of object state suggest greater attention to interactions among method calls, while polymorphism, dynamic binding, generics, and increased use of exception handling introduce new classes of fault that require attention. Some traditional test and analysis techniques are easily adapted to object-oriented software. For example, code inspection can be applied to object-oriented software much as it is to procedural software, albeit with different checklists. In this chapter we will be concerned mostly with techniques that require more substantial revision (like conventional structural testing techniques) and with the introduction of new techniques for coping with problems associated with object-oriented software.

15.2 Issues in Testing Object-Oriented Software The characteristics of object-oriented software that impact test design are summarized in the sidebar on page 273 and discussed in more detail below. The behavior of object-oriented programs is inherently stateful: The behavior of statedependent behavior a method depends not only on the parameters passed explicitly to the method, but also on the state of the object. For example, method CheckConfiguration() of class Model, shown in Figure 15.1, returns True or False depending on whether all components are bound to compatible slots in the current object state.

public class Model extends Orders.CompositeItem { 2 public String modelID; // Database key for slots 3 private int baseWeight; // Weight excluding optional compon 4 private int heightCm, widthCm, depthCm; // Dimensions if bo 5 private Slot[] slots; // Component slots 6 7 private boolean legalConfig = false; // memoized result of 8 private static final String NoModel = “NO MODEL SELECTED”; 12 … 13 /** Constructor, which should be followed by selectModel */ 14 public Model(Orders.Order order) { 15 super( order); 16 modelID = NoModel; 17 } 99 … 100 /** Is the current binding of components to slots a legal 101 configuration? Memoize the result for repeated calls / 102 public boolean isLegalConfiguration() { 103 if (! legalConfig) { 104 checkConfiguration(); 105 } 106 return legalConfig; 107 } 108 109 /** Are all required slots filled with compatible component 110 * It is impossible to assign an incompatible component, 111 * so just to check that every required slot is filled. */ 112 private void checkConfiguration() { 113 legalConfig = true; 114 for (int i=0; i

118 119 120 241 242

} } } … }

Figure 15.1: Part of a Java implementation of class Model. In object-oriented programs, public and private parts of a class (fields and methods) are distinguished. Private state and methods are inaccessible to external entities, which can only change or inspect private state by invoking public methods.[1] For example, the instance variable modelID of class Model in Figure 15.1 is accessible by external entities, but slots and legalConfig are accessible only within methods of the same class. The constructor Model() and the method checkConfiguration() can be used by external entities to create new objects and to check the validity of the current configuration, while method openDB() can be invoked only by methods of this class. Encapsulated information creates new problems in designing oracles and test cases. Oracles must identify incorrect (hidden) state, and test cases must exercise objects in different (hidden) states. Object-oriented programs include classes that are defined by extending or specializing other classes through inheritance. For example, class Model in Figure 15.1 extends class CompositeItem, as indicated in the class declaration. A child class can inherit variables and methods from its ancestors, overwrite others, and add yet others. For example, the class diagram of Figure 15.3 shows that class Model inherits the instance variables sku, units and parts, and methods validItem(), getUnitPrice() and getExtendedPrice(). It overwrites methods getHeightCm(), getWidthCm(), getDepthCm() and getWeightGm(). It adds the instance variables baseWeight, modelID, heightCm, widthCm, DepthCm, slots and legalConfig, and the methods selectModel(), deselect-Model(), addComponent(), removeComponent() and isLegalConfiguration().

Figure 15.3: An excerpt from the class diagram of the Chipmunk Web presence that shows the hierarchy rooted in class LineItem. Summary: Relevant Characteristics of Object-Oriented Software State Dependent Behavior Testing techniques must consider the state in which methods are invoked. Testing techniques that are oblivious to state (e.g., traditional coverage of control structure) are not effective in revealing state-dependent faults. Encapsulation The effects of executing object-oriented code may include outputs, modification of object state, or both. Test oracles may require access to private (encapsulated) information to distinguish between correct and incorrect behavior. Inheritance Test design must consider the effects of new and overridden methods on the behavior of inherited methods, and distinguish between methods that require new test cases, ancestor methods that can be tested by reexecuting existing test cases, and methods that do not need to be retested. Polymorphism and Dynamic Binding A single method call may be dynamically bound to different methods depending on the state of the computation. Tests must exercise different bindings to reveal failures that depend on a particular binding or on interactions between bindings for different calls. Abstract Classes Abstract classes cannot be directly instantiated and tested, yet they may be important interface elements in libraries and components. It is necessary to test

them without full knowledge of how they may be instantiated. Exception Handling Exception handling is extensively used in modern object-oriented programming. The textual distance between the point where an exception is thrown and the point where it is handled, and the dynamic determination of the binding, makes it important to explicitly test exceptional as well as normal control flow. Concurrency Modern object-oriented languages and toolkits encourage and sometimes even require multiple threads of control (e.g., the Java user interface construction toolkits AWT and Swing). Concurrency introduces new kinds of possible failures, such as deadlock and race conditions, and makes the behavior of a system dependent on scheduler decisions that are not under the tester’s control.

Inheritance brings in optimization issues. Child classes may share several methods with their ancestors. Sometimes an inherited method must be retested in the child class, despite not having been directly changed, because of interaction with other parts of the class that have changed. Many times, though, one can establish conclusively that the behavior of an inherited method is really unchanged and need not be retested. In other cases, it may be necessary to rerun tests designed for the inherited method, but not necessary to design new tests. Most object-oriented languages allow variables to dynamically change their type, as long as they remain within a hierarchy rooted at the declared type of the variable. For example, variable subsidiary of method getYTDPurchased() in Figure 15.4 can be dynamically bound to different classes of the Account hierarchy, and thus the invocation of method subsidiary.getYTDPurchased() can be bound dynamically to different methods.

1 public abstract class Account { 151 … 152 /** 153 * The YTD Purchased amount for an account is the YTD 154 * total of YTD purchases of all customers using this accoun 155 * plus the YTD purchases of all subsidiaries of this accoun 156 * currency is currency of this account. 157 */ 158 public int getYTDPurchased() { 159 160 if (ytdPurchasedValid) { return ytdPurchased; } 161 162 int totalPurchased = 0; 163 for (Enumeration e = subsidiaries.elements() ; e.hasMoreE 164 { 165 Account subsidiary = (Account) e.nextElement(); 166 totalPurchased += subsidiary.getYTDPurchased();

167 168 169 170 171 172 173 174 175 176 332 333

} for (Enumeration e = customers.elements(); e.hasMoreEleme { Customer aCust = (Customer) e.nextElement(); totalPurchased += aCust.getYearlyPurchase(); } ytdPurchased = totalPurchased; ytdPurchasedValid = true; return totalPurchased; } … }

Figure 15.4: Part of a Java implementation of Class Account. The abstract class is specialized by the regional markets served by Chipmunk into USAccount, UKAccount, JPAccount, EUAccount and OtherAccount, which differ with regard to shipping methods, taxes, and currency. A corporate account may be associated with several individual customers, and large companies may have different subsidiaries with accounts in different markets. Method getYTDPurchased() sums the year-to-date purchases of all customers using the main account and the accounts of all subsidiaries. Dynamic binding to different methods may affect the whole computation. Testing a call by considering only one possible binding may not be enough. Test designers need testing techniques that select subsets of possible bindings that cover a sufficient range of situations to reveal faults in possible combinations of bindings. Some classes in an object-oriented program are intentionally left incomplete and cannot be directly instantiated. These abstract classes[2] must be extended through subclasses; only subclasses that fill in the missing details (e.g., method bodies) can be instantiated. For example, both classes LineItem of Figure 15.3 and Account of Figure 15.4 are abstract. If abstract classes are part of a larger system, such as the Chipmunk Web presence, and if they are not part of the public interface to that system, then they can be tested by testing all their child classes: classes Model, Component, CompositeItem, and SimpleItem for class LineItem and classes USAccount, UKAccount, JPAccount, EUAccount and OtherAccount for class Account. However, we may need to test an abstract class either prior to implementing all child classes, for example if not all child classes will be implemented by the same engineers in the same time frame, or without knowing all its implementations, for example if the class is included in a library whose reuse cannot be fully foreseen at development time. In these cases, test designers need techniques for selecting a representative set of instances for testing the abstract class. Exceptions were originally introduced in programming languages independently of objectoriented features, but they play a central role in modern object-oriented programming languages and in object-oriented design methods. Their prominent role in object-oriented

programs, and the complexity of propagation and handling of exceptions during program execution, call for careful attention and specialized techniques in testing. The absence of a main execution thread in object-oriented programs makes them well suited for concurrent and distributed implementations. Although many object-oriented programs are designed for and executed in sequential environments, the design of object-oriented applications for concurrent and distributed environments is becoming very frequent. Object-oriented design and programming greatly impact analysis and testing. However, test designers should not make the mistake of ignoring traditional technology and methodologies. A specific design approach mainly affects detailed design and code, but there are many aspects of software development and quality assurance that are largely independent of the use of a specific design approach. In particular, aspects related to planning, requirements analysis, architectural design, deployment and maintenance can be addressed independently of the design approach. Figure 15.5 indicates the scope of the impact of object-oriented design on analysis and testing.

Figure 15.5: The impact of object-oriented design and coding on analysis and testing. [1]Object-oriented

languages differ with respect to the categories of accessibility they provide. For example, nothing in Java corresponds exactly to the “friend” functions in C++ that are permitted to access the private state of other objects. But while details vary, encapsulation of state is fundamental to the object-oriented programming paradigm, and all major object-oriented languages have a construct comparable to Java’s private field declarations. [2]Here

we include the Java interface construct as a kind of abstract class.

15.3 An Orthogonal Approach to Test Testing all aspects of object-oriented programs simultaneously would be difficult and expensive; fortunately it is also unnecessary. It is more cost-effective to address different features individually, using appropriate techniques for each, and to explicitly address significant interactions (e.g., between inheritance and state-dependent behavior) rather than blindly exploring all different feature combinations. The proper blend of techniques depends on many factors: application under test, development approach, team organization, application criticality, development environment and the implementation languages, use of design and language features, and project timing and resource constraints. Nonetheless, we can outline a general approach that works in stages, from single classes to class and system interactions. A single “stage” is actually a set of interrelated test design and test execution activities. The approach is summarized in the sidebar on page 281 and described in more detail in this section in the order that tests related to a particular class would be executed, although test design and execution activities are actually interleaved and distributed through development. The smallest coherent unit for unit testing of object-oriented testing is the class. Test designers can address inheritance, state-dependent behavior and exceptions with intraclass testing. For example, when testing class Model of Figure 15.3, test designers may first use testing histories (see Section 15.10) to infer that method getExtendedPrice need not be retested, since it has already been tested in class LineItem. On the other hand, test designers must derive new test cases for the new methods and for those affected by the modifications introduced in class Model. After considering individual methods, test designers can proceed to design functional test cases from the statechart specification of class Model (see Section 15.5) and structural test cases from data flow information (see Section 15.7). To execute test cases, test designers may decide to use equivalent scenarios as oracles (see Section 15.8). Test designers will then create test cases for exceptions thrown or handled by the class under test (see Section 15.12). Class Model does not make polymorphic calls, so no additional test cases need be designed to check behavior with variable bindings to different classes. Integration (interclass) tests must be added to complete the testing for hierarchy, polymorphism, and exception-related problems. For example, when testing integration of class Model within the Chipmunk Web presence, test designers will identify class Slot as a predecessor in the integration order and will test it first, before testing its integration with class Model (see Sections 15.5 and 15.7). They will also derive test cases for completing the test of exceptions (see Section 15.12) and polymorphism (see Section 15.9). System and acceptance testing check overall system behavior against user and system requirements. Since these requirements are (at least in principle) independent of the design approach, system and acceptance testing can be addressed with traditional techniques. For example, to test the business logic subsystem of the Chipmunk Web presence, test designers may decide to derive test cases from functional specifications using category-

partition and catalog based methods (see Chapter 11). Steps in Object-Oriented Software Testing Object-oriented testing can be broken into three phases, progressing from individual classes toward consideration of integration and interactions. Intraclass Testing classes in isolation (unit testing) 1. If the class-under-test is abstract, derive a set of instantiations to cover significant cases. Instantiations may be taken from the application (if available) and/or created just for the purpose of testing. 2. Design test cases to check correct invocation of inherited and overridden methods, including constructors. If the class-under-test extends classes that have previously been tested, determine which inherited methods need to be retested and which test cases from ancestor classes can be reused. 3. Design a set of intraclass test cases based on a state machine model of specified class behavior. 4. Augment the state machine model with structural relations derived from class source code and generate additional test cases to cover structural features. 5. Design an initial set of test cases for exception handling, systematically exercising exceptions that should be thrown by methods in the class under test and exceptions that should be caught and handled by them. 6. Design an initial set of test cases for polymorphic calls (calls to superclass or interface methods that can be bound to different subclass methods depending on instance values). Interclass Testing class integration (integration testing) 1. Identify a hierarchy of clusters of classes to be tested incrementally. 2. Design a set of functional interclass test cases for the cluster-under-test. 3. Add test cases to cover data flow between method calls. 4. Integrate the intraclass exception-handling test sets with interclass exceptionhandling test cases for exceptions propagated across classes. 5. Integrate the polymorphism test sets with tests that check for interclass interactions of polymorphic calls and dynamic bindings. System and Acceptance Apply standard functional and acceptance testing techniques to larger components and the whole system.

15.4 Intraclass Testing Unit and integration testing aim to expose faults in individual program units and in their interactions, respectively. The meaning of “unit” is the smallest development work assignment for a single programmer that can reasonably be planned and tracked. In procedural programs, individual program units might be single functions or small sets of strongly related functions and procedures, often included in a single file of source code. In object-oriented programs, small sets of strongly related functions or procedures are naturally identified with classes, which are generally the smallest work units that can be systematically tested. Treating an individual method as a unit is usually not practical because methods in a single class interact by modifying object state and because the effect of an individual method is often visible only through its effect on other methods. For example, method check configuration of class computer, shown in Figure 15.1, can be executed only if the object is in a given state, and its result depends on the current configuration. The method may execute correctly in a given state (i.e., for a given configuration), but may not execute correctly in a different state (e.g., accepting malformed configurations or rejecting acceptable configurations). Moreover, method check configuration might produce an apparently correct output (return value) but leave the object in an incorrect state.

15.5 Testing with State Machine Models Since the state of an object is implicitly part of the input and output of methods, we need a way to systematically explore object states and transitions. This can be guided by a state machine model, which can be derived from module specifications. A state machine model can be extracted from an informal, natural language specification of intended behavior, even when the specification does not explicitly describe states and transitions. States can be inferred from descriptions of methods that act differently or return different results, depending on the state of the object; this includes any description of when it is allowable to call a method. Of course, one wants to derive only a reasonable number of abstract states as representatives of a much larger number of concrete states, and some judgment is required to choose the grouping. For example, if an object kept an integer count, we might choose “zero” and “nonzero” as representative states, rather than creating a different state for every possible value. The principle to observe is that we are producing a model of how one method affects another, so the states should be refined just enough to capture interactions. Extracting a state machine from an informal specification, and then creating test cases (sequences of method calls) to cover transitions in that model, are illustrated in the sidebar on page 283. Sometimes an explicit state machine model is already available as part of a specification or design. If so, it is likely to be in the form of a statechart (also known as a state diagram in the UML family of notations). Statecharts include standard state transition diagrams, but also provide hierarchical structuring constructs. The structuring facilities of statecharts can be used to organize and hide complexity, but this complexity must be exposed to be tested. From Informal Specs to Transition Coverage An Informal Specification of Class Slot Slot represents a configuration choice in all instances of a particular model of computer. It may or may not be implemented as a physical slot on a bus. A given model may have zero or more slots, each of which is marked as required or optional. If a slot is marked as “required,” it must be bound to a suitable component in all legal configurations. Class Slot offers the following services: Incorporate: Make a slot part of a model, and mark it as either required or optional. All instances of a model incorporate the same slots. Example: We can incorporate a required primary battery slot and an optional secondary battery slot on the Chipmunk C20 laptop that includes two battery slots. The C20 laptop may then be sold with one battery or two batteries, but it is not sold without at least the primary battery. Bind: Associate a compatible component with a slot. Example: We can bind slot

primary battery to a Blt4, Blt6, or Blt8 lithium battery or to a Bcdm4 nickel cadmium battery. We cannot bind a disk drive to the battery slot. Unbind: The unbind operation breaks the binding of a component to a slot, reversing the effect of a previous bind operation. IsBound: Returns true if a component is currently bound to a slot, or false if the slot is currently empty. The Corresponding Finite State Machine A simple analysis of the informal specification of class Slot allows one to identify states and transitions. Often an analysis of natural language specifications will reveal ambiguities that must be resolved one way or the other in the model; these may suggest additional test cases to check the interpretation, or lead to refinement of the specification, or both. For class slot, we infer that the bind operation makes sense only after the slot has been incorporated in a model, and that it is initially empty.

The Generated Test Case Specifications A single test case will be given as a sequence of method calls. For class Slot, the following test cases suffice to execute each transition in the state machine model: TC-1 incorporate, isBound, bind, isBound TC-2 incorporate, unBind, bind, unBind, isBound

The most common structuring mechanism in statecharts is grouping of states in superstates (also called OR-states). A transition from a superstate is equivalent to a transition from every state contained within it. A transition to a superstate is equivalent to a transition to the initial state within the superstate. We can obtain an ordinary state machine by “flattening” the statechart hierarchy, replacing transitions to and from superstates to transitions among elementary states. Figure 15.6 shows a statechart specification for class Model of the business logic of the Chipmunk Web presence. Class Model provides methods for selecting a computer model and a set of components to fill logical and physical slots. The state modelSelected is decomposed into its two component states, with entries to modelSelected directed to the default initial state workingConfiguration.

Figure 15.6: Statechart specification of class Model. Table 15.1 shows a set of test cases that cover all transitions of the finite state machine of Figure 15.7, a flattened version of the statechart of Figure 15.6. Notice that transition selectModel of the statechart corresponds to a single transition in the FSM, since entry to the superstate is directed to the default initial state, while transition deselectModel of the statechart corresponds to two transitions in the FSM, one for each of the two children states, since the superstate can be exited while in either component state.

Figure 15.7: Finite state machine corresponding to the statechart of Figure 15.6. Table 15.1: A set of test cases that satisfies the transition coverage criterion for the statechart of Figure 15.6. Open table as spreadsheet

Test Case TCA selectModel(M1) addComponent(S1,C1) addComponent(S2,C2) isLegalConfiguration()

Test Case TCB selectModel(M1) deselectModel() selectModel(M2) addComponent(S1,C1) addComponent(S2,C2) removeComponent(S1) isLegalConfiguration()

Test Case TCD selectModel(M1) addComponent(S1,C1)

Test Case TCE selectModel(M1)

Test Case TCC selectModel(M1) addComponent(S1,C1) removeComponent(S1) addComponent(S1,C2) isLegalConfiguration()

addComponent(S2,C2) addComponent(S3,C3) deselectModel() selectModel(M1) addComponent(S1,C1) isLegalConfiguration()

addComponent(S1,C1) addComponent(S2,C2) addComponent(S3,C3) removeComponent(S2) addComponent(S2,C4) isLegalConfiguration()

In covering the state machine model, we have chosen sets of transition sequences that together exercise each individual transition at least once. This is the transition adequacy criterion introduced in Chapter 14. The stronger history-sensitive criteria described in that chapter are also applicable in principle, but are seldom used because of their cost. Even transition coverage may be impractical for complex statecharts. The number of states and transitions can explode in “flattening” a statechart that represents multiple threads of control. Unlike flattening of ordinary superstates, which leaves the number of elementary states unchanged while replicating some transitions, flattening of concurrent state machines (so-called AND-states) produces new states that are combinations of elementary states. Figure 15.8 shows the statechart specification of class Order of the business logic of the Chipmunk Web presence. Figure 15.9 shows the corresponding “flattened” state machine. Flattening the AND-state results in a number of states equal to the Cartesian product of the elementary states (3 × 3 = 9 states) and a corresponding number of transitions. For instance, transition add item that exits state not scheduled of the statechart corresponds to three transitions exiting the states not schedXcanc no fee, not schedXcanc fee, and not schedXnot canc, respectively. Covering all transitions at least once may result in a number of test cases that exceeds the budget for testing the class. In this case, we may forgo flattening and use simpler criteria that take advantage of the hierarchical structure of the statechart.

Figure 15.8: Statechart specification of class Order. This is a conceptual model in which both methods of class Order and method calls by class Order are represented as transitions with names that differ from method names in the implementation (e.g., 5DaysBeforeShipping is not a legal method or field name).

Figure 15.9: Finite state machine corresponding to the statechart of Figure 15.8. Table 15.2 shows a test suite that satisfies the simple transition coverage adequacy criterion, which requires the execution of all transitions that appear in the statechart. The criterion requires that each statechart transition is exercised at least once, but does not

guarantee that transitions are exercised in all possible states. For example, transition add item, which leaves the initial state, is exercised from at least one substate, but not from all possible substates as required by the transition coverage adequacy criterion. Table 15.2: A test suite that satisfies the simple transition coverage adequacy criterion for the statechart of Figure 15.8. Transitions are indicated without parameters for simplicity. Open table as spreadsheet

Test Case TCA add_item() add_item() package() get_shipping_cost() get_discount() purchase() place_order() 24_hours() 5_days() schedule() ship() deliver()

Test Case TCD add_item() add_item() package() get_shipping_cost() get_discount() purchase() place_order() remove_item() add_item() package() get_shipping_cost() get_discount() purchase() place_order() 24_hours()

Test Case TCB add_item() add_item() remove_item() add_item() package() get_shipping_cost() get_discount() purchase() place_order() 24_hours() 5_days() schedule() ship() deliver()

Test Case TCE add_item() add_item() package() get_shipping_cost() get_discount() purchase() place_order() schedule() suspend() 5_days() schedule() ship()

Test Case TCC add_item() add_item() package() get_shipping_cost() get_discount() purchase() place_order() add_item() package() get_shipping_cost() get_discount() purchase() place_order() 24_hours() 5_days() schedule() ship() deliver()

Test Case TCF add_item() add_item() package() get_shipping_cost() get_discount() purchase() place_order() schedule() cancel()

5_days() schedule() ship() deliver()

deliver()

Test Case TCG add_item() add_item() package() get_shipping_cost() get_discount() purchase() place_order() schedule() ship() address_unknown()

Test Case TCH add_item() add_item() package() get_shipping_cost() get_discount() purchase() place_order() schedule() 5_days() address_unknown()

Test Case TCI add_item() add_item() package() get_shipping_cost() get_discount() purchase() place_order() schedule() 24_hours() cancel()

15.6 Interclass Testing Interclass testing is the first level of integration testing for object-oriented software. While intraclass testing focuses on single classes, interclass testing checks interactions among objects of different classes. As in integration testing of imperative programs, test designers proceed incrementally, starting from small clusters of classes. Since the point of interclass testing is to verify interactions, it is useful to model potential interactions through a use/include relation. Classes A and B are related by the use/include relation if objects of class A make method calls on objects of class B, or if objects of class A contain references to objects of class B. Inheritance is ignored (we do not consider a subclass to use or include its ancestors), and abstract classes, which cannot directly participate in interactions, are omitted. Derivation of the use/include relation from a conventional UML class diagram is illustrated in Figures 15.10 and 15.11.

Figure 15.10: Part of a class diagram of the Chipmunk Web presence. Classes Account, LineItem, and CSVdb are abstract.

Figure 15.11: Use/include relation for the class diagram in Figure 15.10. Abstract classes are not included. Two classes are related if one uses or includes the other. Classes that are higher in the diagram include or use classes that are lower in the diagram. Interclass testing strategies usually proceed bottom-up, starting from classes that depend on no others. The implementation-level use/include relation among classes typically parallels the more abstract, logical depends relation among modules (see sidebar on page 292), so a bottom-up strategy works well with cluster-based testing. For example, we can start integrating class SlotDB with class Slot, and class Component with class ComponentDB, and then proceed incrementally integrating classes ModelDB and Model, up to class Order. Dependence The hierarchy of clusters for interclass testing is based on a conceptual relation of dependence, and not directly on concrete relations among implementation classes (or implementation-level design documentation). Module A depends on module B if the functionality of B must be present for the functionality of A to be provided. If A and B are implemented as classes or clusters of closely related classes, it is likely that the logical depends relation will be reflected in concrete relations among the classes. Typically, the class or classes in A will either call methods in the class or classes in B, or classes in A will have references to classes in B forming a contains relation among their respective objects. Concrete relations among classes do not always indicate dependence. It is common for contained objects to have part-of relations with their ancestors in the containment hierarchy, but the dependence is normally from container to contained object and not vice versa. It is also common to find calls from framework libraries to methods that use those libraries. For example, the SAX API for parsing XML is an event-driven parsing

framework, which means the parsing library makes calls (through interfaces) on methods provided by the application. This style of event handling is most familiar to Java programmers through the standard Java graphical user interface libraries. It is clear that the application depends on the library and not vice versa. The depends relation is as crucial to other software development processes as it is to testing. It is essential to building a system as a set of incremental releases, and to scheduling and managing the construction of each release. The depends relation may be documented in UML package diagrams, and even if not documented explicitly it is surely manifest in the development build order. Test designers may (and probably should) be involved in defining the build order, but should not find themselves in the position of discovering or re-creating it after the fact.

Well-designed systems normally have nearly acyclic dependence relations, with dependence loops limited to closely related clusters. When there are larger loops in the relation, or when a use/include relation among classes runs contrary to the depends relation (e.g., an “up-call” to an ancestor in the depends relation), the loop can be broken by substituting a stub for the ancestor class. Thus, we always work with an acyclic graph of clusters. In principle, while climbing the dependence relation, a thorough interclass testing should consider all combinations of possible interactions. If, for example, a test case for class Order includes a call to a method of class Model, and the called method calls a method of class Slot, each call should be exercised for all relevant states of the different classes, as identified during intraclass testing. However, this suffers from the same kind of combinatorial explosion that makes flattening concurrent state diagrams impractical. We need to select a subset of interactions among the possible combinations of method calls and class states. An arbitrary or random selection of interactions may be an acceptable solution, but in addition one should explicitly test any significant interaction scenarios that have been previously identified in design and analysis. Interaction scenarios may have been recorded in the form of UML interaction diagrams, expressed as sequence or collaboration diagrams. These diagrams describe interactions among objects and can be considered essentially as test scenarios created during the course of design. In addition to testing the scenarios spelled out in sequence or collaboration diagrams, the test designer can vary those scenarios to consider illegal or unexpected interaction sequences. For example, replacing a single interaction in a sequence diagram with another interaction that should not be permitted at that point yields a test case that checks error handling. Figure 15.12 shows a possible pattern of interactions among objects, when a customer assembling an order O first selects the computer model C20, then adds a hard disk HD60 that is not compatible with the slots of the selected model, and then adds “legal” hard disk HD20. The sequence diagram indicates the sequence of interactions among objects and

suggests possible testing scenarios. For example, it suggests adding a component after having selected a model. In other words, it indicates interesting states of objects of type ModelDB and Slots when testing class Model.

Figure 15.12: A (partial) sequence diagram that specifies the interactions among objects of type Order, Model, ModelDB, Component, ComponentDB, Slots, and SlotDB, to select a computer, add an illegal component, and then add a legal one. Unlike statecharts, which should describe all possible sequences of transitions that an object can undergo, interaction diagrams illustrate selected interactions that the designers considered significant because they were typical, or perhaps because they were difficult to understand. Deriving test cases from interaction diagrams is useful as a way of choosing some significant cases among the enormous variety of possible interaction sequences, but it is insufficient as a way of ensuring thorough testing. Integration tests should at the very least repeat coverage of individual object states and transitions in the context of other parts of the cluster under test.

15.7 Structural Testing of Classes In testing procedural code, we take specifications as the primary source of information for test design (functional testing), and then we analyze implementation structure and add test cases as needed to cover additional variation (structural testing). The same approach applies to object-oriented programs and for the same reasons. The techniques described in previous sections are all based on specification of intended behavior. They should be augmented (but never replaced) by structural techniques. If we compare the implementation of class Model shown in Figures 15.1 and 15.2 with its specification in Figures 15.3 and 15.6, we notice that the code uses an instance variable legalConfig and an internal (private) method checkConfiguration to optimize the implementation of method isLegalConfiguration. The functional test cases shown in Table 15.1 do not include method checkConfiguration, though some of them will call it indirectly through isLegalConfiguration. An alert test designer will note that every modification of the object state that could possibly invalidate a configuration should reset the hidden legalConfig variable to False, and will derive structural test cases to cover behaviors not sufficiently exercised by functional test cases. public 61 … 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

class Model extends Orders.CompositeItem {

/** Bind a component to a slot. * @param slotIndex Which slot (integer index)? * @param sku Key to component database. * Choices should be constrained by web interface, so we do * need to be graceful in handling bogus parameters. */ public void addComponent(int slotIndex, String sku) { Slot slot =slots[slotIndex]; if (componentDB.contains(sku)) { Component comp = new Component(order, sku); if (comp.isCompatible(slot.slotID)) { slot.bind(comp); // Note this cannot have made the // configuration illegal. } else { slot.unbind(); legalConfig = false; } } else { slot.unbind(); legalConfig = false; } }

86 87 88 89 90 91 92 93 215 216

/** Unbind a component from a slot. */ public void removeComponent(int slotIndex) { // assert slotIndex in 0..slots.length if (slots[slotIndex].isBound()) { slots[slotIndex].unbind(); } legalConfig = false; 94 } … }

Figure 15.2: More of the Java implementation of class Model. Because of the way method isLegalConfig is implemented (see Figure 15.1), all methods that modify slots must reset the private variable legalConfig. The chief difference between functional testing techniques for object-oriented software and their counterparts for procedural software (Chapters 10, 11, and 14) is the central role of object state and of sequences of method invocations to modify and observe object state. Similarly, structural test design must be extended beyond consideration of control and data flow in a single method to take into account how sequences of method invocations interact. For example, tests of isLegalConfiguration would not be sufficient without considering the prior state of private variable legalConfig. Since the state of an object is comprised of the values of its instance variables, the number of possible object states can be enormous. We might choose to consider only the instance variables that do not appear in the specification, and add only those to the state machine representation of the object state. In the class Model example, we will have to add only the state of the Boolean variable legalConfig, which can at most double the number of states (and at worst quadruple the number of transitions). While we can model the concrete values of a single Boolean variable like legalConfig, this approach would not work if we had a dozen such variables, or even a single integer variable introduced in the implementation. To reduce the enormous number of states obtained by considering the combinations of all values of the instance variables, we could select a few representative values. Another way to reduce the number of test cases based on interaction through instance variable values while remaining sensitive enough to catch many common oversights is to model not the values of the variables, but the points at which the variables receive those values. This is the same intuition behind data flow testing described in Chapter 13, although it requires some extension to cover sequences in which one method defines (sets) a variable and another uses that variable. Definition-use pairs for the instance variables of an object are computed on an intraclass control flow graph that joins all the methods of a single class, and thus allows pairing of definitions and uses that occur in different methods. Figure 15.13 shows a partial intraclass control flow graph of class Model. Each method is modeled with a standard control flow graph (CFG), just as if it were an independent

procedure, except that these are joined to allow paths that invoke different methods in sequence. To allow sequences of method calls, the class itself is modeled with a node class Model connected to the CFG of each method. Method Model includes two extra statements that correspond to the declarations of variables legalConfig and modelDB that are initialized when the constructor is invoked.[3]

Figure 15.13: A partial intraclass control flow graph for the implementation of class Model in Figures 15.1 and 15.2. Sometimes definitions and uses are made through invocation of methods of other classes. For example, method addComponent calls method contains of class componentDB. Moreover, some variables are structured; for example, the state variable slot is a complex object. For the moment, we simply “unfold” the calls to external methods, and we treat arrays and objects as if they were simple variables. A test case to exercise a definition-use pair (henceforth DU pair) is a sequence of method invocations that starts with a constructor, and includes the definition followed by the use without any intervening definition (a definition-clear path). A suite of test cases can be designed to satisfy a data flow coverage criterion by covering all such pairs. In that case we say the test suite satisfies the all DU pairs adequacy criterion. Consider again the private variable legalConfig in class Model, Figures 15.1 and 15.2. There are two uses of legalConfig, both in method isLegalConfiguration, one in the if and one in the return statement; and there are several definitions in methods addComponent, removeComponent, checkConfiguration and in the constructor, which initializes legalConfig to False. The all DU pairs adequacy criterion requires a test case to exercise each definition followed by each use of legalConfig with no intervening definitions. Specifications do not refer to the variable legalConfig and thus do not directly consider method interactions through legalConfig or contribute to defining test cases to exercise such

interactions. This is the case, for example, in the invocation of method checkConfiguration in isLegalConfiguration: The specification suggests that a single invocation of method isLegalConfiguration can be sufficient to test the interactions involving this method, while calls to method checkConfiguration in isLegalConfiguration indicate possible failures that may be exposed only after two calls of method isLegalConfiguration. In fact, a first invocation of isLegalConfiguration with value True for legalConfig implies a call to checkConfiguration and consequent new definitions of legalConfig. Only a second call to isLegalConfiguration would exercise the use of the new value in the if statement, thus revealing failures that may derive from bad updates of legalConfig in checkConfiguration. The all DU pairs adequacy criterion ensures that every assignment to a variable is tested at each of the uses of that variable, but like other structural coverage criteria it is not particularly good at detecting missing code. For example, if the programmer omitted an assignment to legalConfig, there would be no DU pair connecting the missing assignment to the use. However, assignments to legalConfig are correlated with updates to slots, and all DU pairs coverage with respect to slots is likely to reveal a missing assignment to the Boolean variable. Correlation among assignments to related fields is a common characteristic of the structure of object-oriented software. Method calls and complex state variables complicate data flow analysis of object-oriented software, as procedure calls and structured variables do in procedural code. As discussed in Chapters 6 and 13, there is no universal recipe to deal with interclass calls. Test designers must find a suitable balance between costs and benefits. A possible approach to deal with interclass calls consists in proceeding incrementally following the dependence relation, as we did for functional interclass testing. The dependence relation that can be derived from code may differ from the dependence relation derived from specifications. However, we can still safely assume that well-designed systems present at most a small number of easily breakable cycles. The dependencies of the implementation and specification of class Model are the same and are shown in Figure 15.11. Leaf classes of the dependence hierarchy can be analyzed in isolation by identifying definitions and uses of instance variables, as just shown. The data flow information collected on leaf classes can be summarized by marking methods that access but do not modify the state as Inspectors; methods that modify, but do not otherwise access the state, as Modifiers; and methods that both access and modify the state as Inspector/Modifiers. When identifying inspectors, modifiers and inspector/modifiers, we consider the whole object state. Thus, we mark a method as inspector/modifier even if it uses just one instance variable and modifies a different one. This simplification is crucial to scalability, since distinguishing uses and definitions of each individual variable would quickly lead to an unmanageable amount of information while climbing the dependence hierarchy. If methods contain more than one execution path, we could summarize the whole method as an inspector, modifier, or inspector/modifier, or we could select a subset of paths to be

considered independently. A single method might include Inspector, Modifier, and Inspector/Modifier paths. Once the data flow information of leaf classes has been summarized, we can proceed with classes that only use or contain leaf classes. Invocations of modifier methods and inspector/modifiers of leaf classes are considered as definitions. Invocations of inspectors and inspector/modifiers are treated as uses. When approximating inspector/modifiers as uses, we assume that the method uses the values of the instance variables for computing the new state. This is a common way of designing methods, but some methods may fall outside this pattern. Again, we trade precision for scalability and reduced cost. We can then proceed incrementally analyzing classes that depend only on classes already analyzed, until we reach the top of the hierarchy. In this way, each class is always considered in isolation, and the summary of information at each step prevents exponential growth of information, thus allowing large classes to be analyzed, albeit at a cost in precision. Figure 15.14 shows the summary information for classes Slot, ModelDB, and Model. The summary information for classes Slot and ModelDB can be used for computing structural coverage of class Model without unfolding the method calls. The summary information for class Model can be used to compute structural coverage for class Order without knowing the structure of the classes used by class Order. Method checkConfiguration is not included in the summary information because it is private. The three paths in checkConfiguration are included in the summary information of the calling method isLegalConfiguration. Class Slot Slot() bind()

modifier modifier

unbind()

modifier

isBound()

inspector

Class ModelDB ModelDB()

modifier

getModel()

inspector

findModel()

inspector

Class Model

Model()

modifier

selectModel()

modifier

deselectModel()

modifier

addComponent() [1,2,8,9,10]

inspector/modifier

addComponent() [1,2,3,4,5,6,10]

inspector/modifier

addComponent() [1,2,3,4,7,10]

inspector/modifier

removeComponent() [1,2,3,4,5]

inspector/modifier

removeComponent() [1,2,4,5]

inspector/modifier

isLegalConfiguration() [1,2,3,[1,2,3,4,9],4]

inspector/modifier

isLegalConfiguration() [1,2,3,[1,2,3,4,5,6,7,4,9],4]

inspector/modifier

isLegalConfiguration() [1,2,3,[1,2,3,4,5,6,7,8,4,9],4]

inspector/modifier

isLegalConfiguration() [1,2,4]

modifier

Figure 15.14: Summary information for structural interclass testing for classes Slot, ModelDB, and Model. Lists of CFG nodes in square brackets indicate different paths, when methods include more than one part. While summary information is usually derived from child classes, sometimes it is useful to provide the same information without actually performing the analysis, as we have done when analyzing class Model. This is useful when we cannot perform data flow analysis on the child classes, as when child classes are delivered as a closed component without source code, or are not available yet because the development is still in progress. [3]We

have simplified Figure 15.13 by omitting methods getHeightCm, getWidthCm, getDepthCm, and getWeightGm, since they depend only on the constructor and do not affect other methods. Exception handlers are excluded since they will be treated separately, as described in Section 15.12.

15.8 Oracles for Classes Unit (intraclass) and integration (interclass) testing require suitable scaffolding to exercise the classes under test (drivers and stubs) and to inspect the test results (oracles). Constructing stubs and drivers for object-oriented software is essentially similar to the same task for procedural programs, and as in procedural programs, stubs can be avoided to the extent that the order of test execution is aligned with the build order of the software system. Oracles, however, can be more difficult to construct, owing to encapsulation of object state. The effect of executing a method or a whole sequence of methods in a test case is not only the outputs produced, but also the state of the objects after execution. For example, if method deselectModel of class Model does not clear the array slots, it is erroneous, even if it produces the expected visible outputs. Thus, oracles need to check the validity of both output and state. Unfortunately for the oracle builder, though, the state of objects may not be directly accessible. For example, variable slots is private and thus cannot be directly accessed by an oracle outside the class under test. One approach to building oracles is to break the encapsulation, for example, by modifying the source code to allow inspection of private variables. If we violate encapsulation by modifying code just for the purpose of testing, rather than leaving the modifications in the actual delivered code, then we risk differences in behavior between what is tested and what is used. We may mask faults, or we may inadvertently insert faults not present in the original code, particularly if we make modifications by hand. Even a small difference in performance can be important in a real-time system or in a multi-threaded system sensitive to scheduler decisions. Modifications that remain in the code, or (better) design rules that require programmers to provide observability interfaces, avoid discrepancies between the production code and the tested code. This is a particularly attractive option if the interface for observing object state can be separated from the main class, as one can for example do with a C++ friend class.[4] An observability interface can be a collection of observer methods, or a single method to produce a representation of the full object state. Often an interface that produces a readable, canonical representation of an object value will be useful in debugging as well as in testing. A second alternative is not to reveal the internal state of an object per se, but to provide a way of determining whether two objects are equivalent. Here “equivalent” does not mean that the internal states of two objects are identical, but that they represent the same abstract value. For example, we might consider the Java Vector class as representing a sequence. If so, then not only might two vectors with different capacities be considered equivalent, but we might even consider a vector object and a linked list object to be equivalent if they contain the same elements in the same order. An (abstract) check for equivalence can be used in a test oracle if test cases exercise two sequences of method calls that should (or should not) produce the same object state. Comparing objects using this equivalent scenarios approach is particularly suitable when the

classes being tested are an instance of a fairly simple abstract data type, such as a dictionary structure (which includes hash tables, search trees, etc.), or a sequence or collection. Table 15.3 shows two sequences of method invocations, one equivalent and one nonequivalent to test case TCE for class Model. The equivalent sequence is obtained by removing “redundant” method invocations – invocations that brings the system to a previous state. In the example, method deselectModel cancels the effect of previous invocations of method selectModel and addComponent. The nonequivalent sequence is obtained by selecting a legal subset of method invocations that bring the object to a different state. Table 15.3: Equivalent and nonequivalent scenarios (invocation sequences) for test case TCE from Table 15.1 for class Model. Test Case TCE selectModel(M1) addComponent(S1,C1) addComponent(S2,C2) isLegalCon.guration() deselectModel() selectModel(M2) addComponent(S1,C1) isLegalCon.guration()

Scenario TCE1 selectModel(M2) addComponent(S1,C1) isLegalCon.guration() EQUIVALENT

Scenario TCE2 selectModel(M2) addComponent(S1,C1) addComponent(S2,C2) isLegalConfiguration() NONEQUIVALENT

Producing equivalent sequences is often quite simple. While finding nonequivalent sequences is even easier, choosing a few good ones is difficult. One approach is to hypothesize a fault in the method that “generated” the test case, and create a sequence that could be equivalent if the method contained that fault. For example, test case TCE was designed to test method deselectModel. The nonequivalent sequence of Table 15.3 leads to a state that could be produced if method deselectModel did not clear all slots, leaving component C2 bound to slot S2 in the final configuration. One sequence of method invocations is equivalent to another if the two sequences lead to the same object state. This does not necessarily mean that their concrete representation is bit-for-bit equal. For example, method addComponent binds a component to a slot by creating a new Slot object (Figure 15.2). Starting from two identical Model objects, and calling addComponent on both with exactly the same parameters, would result in two objects that represent the same information but that nonetheless would contain references to distinct Slot objects. The default equals method inherited from class Object, which makes a bit-for-bit comparison, would not consider them equivalent. A good practice is to add a suitable observer method to a class (e.g., by overriding the default equals method in Java). [4]A

“friend” class in C++ is permitted direct access to private variables in another class. There is no direct equivalent in Java or SmallTalk, although in Java one could obtain a somewhat similar effect by using package visibility for variables and placing oracles in the

same package.

15.9 Polymorphism and Dynamic Binding Limited use of polymorphism and dynamic binding is easily addressed by unfolding polymorphic calls, considering each method that can be dynamically bound to each polymorphic call. Complete unfolding is impractical when many references may each be bound to instances of several subclasses. Consider, for example, the code fragment in Figure 15.15. Object Account may by an instance of any of the classes USAccount, UKAccount, EUAccount, JPAccount, or OtherAccount. Method validateCredit can be dynamically bound to methods validateCredit of any of the classes EduCredit, BizCredit, or IndividualCredit, each implementing different credit policies. Parameter creditCard may be dynamically bound to VISACard, AmExpCard, or ChipmunkCard, each with different characteristics. Even in this simple example, replacing the calls with all possible instances results in 45 different cases (5 possible types of account × 3 possible types of credit × 3 possible credit cards).

1 abstract class Credit { 15 … 16 abstract boolean validateCredit( Account a, int amt, CreditC 60 … 61 } Figure 15.15: A method call in which the method itself and two of its parameters can be dynamically bound to different classes. The explosion in possible combinations is essentially the same combinatorial explosion encountered if we try to cover all combinations of attributes in functional testing, and the same solutions are applicable. The combinatorial testing approach presented in Chapter 11 can be used to choose a set of combinations that covers each pair of possible bindings (e.g., Business account in Japan, Education customer using Chipmunk Card), rather than all possible combinations (Japanese business customer using Chipmunk card). Table 15.4 shows 15 cases that cover all pairwise combinations of calls for the example of Figure 15.15. Table 15.4: A set of test case specifications that cover all pairwise combinations of the possible polymorphic bindings of Account, Credit, and creditCard. Open table as spreadsheet Account

Credit

creditCard

USAccount

EduCredit

VISACard

USAccount

BizCredit

AmExpCard

USAccount

individualCredit

ChipmunkCard

UKAccount

EduCredit

AmExpCard

UKAccount

BizCredit

VISACard

UKAccount

individualCredit

ChipmunkCard

EUAccount

EduCredit

ChipmunkCard

EUAccount

BizCredit

AmExpCard

EUAccount

individualCredit

VISACard

JPAccount

EduCredit

VISACard

JPAccount

BizCredit

ChipmunkCard

JPAccount

individualCredit

AmExpCard

OtherAccount

EduCredit

ChipmunkCard

OtherAccount

BizCredit

VISACard

OtherAccount

individualCredit

AmExpCard

The combinations in Table 15.4 were of dynamic bindings in a single call. Bindings in a sequence of calls can also interact. Consider, for example, method getYTDPurchased of class Account shown in Figure 15.4 on page 278, which computes the total yearly purchase associated with one account to determine the applicable discount. Chipmunk offers tiered discounts to customers whose total yearly purchase reaches a threshold, considering all subsidiary accounts. The total yearly purchase for an account is computed by method getYTDPurchased, which sums purchases by all customers using the account and all subsidiaries. Amounts are always recorded in the local currency of the account, but getYTDPurchased sums the purchases of subsidiaries even when they use different currencies (e.g., when some are bound to subclass USAccount and others to EUAccount). The intra-and interclass testing techniques presented in the previous section may fail to reveal this type of fault. The problem can be addressed by selecting test cases that cover combinations of polymorphic calls and bindings. To identify sequential combinations of bindings, we must first identify individual polymorphic calls and binding sets, and then select possible sequences. Let us consider for simplicity only the method getYTDPurchased. This method is called once for each customer and once for each subsidiary of the account and in both cases can be dynamically bound to methods belonging to any of the subclasses of Account (UKAccount, EUAccount, and so on). At each of these calls, variable totalPurchased is used and changed, and at the end of the method it is used twice more (to set an instance variable and to return a value from the method). Data flow analysis may be used to identify potential interactions between possible bindings at a point where a variable is modified and points where the same value is used. Any of the

standard data flow testing criteria could be extended to consider each possible method binding at the point of definition and the point of use. For instance, a single definition-use pair becomes n × m pairs if the point of definition can be bound in n ways and the point of use can be bound in m ways. If this is impractical, a weaker but still useful alternative is to vary both bindings independently, which results in m or n pairs (whichever is greater) rather than their product. Note that this weaker criterion would be very likely to reveal the fault in getYTDPurchased, provided the choices of binding at each point are really independent rather than going through the same set of choices in lockstep. In many cases, binding sets are not mutually independent, so the selection of combinations is limited.

15.10 Inheritance Inheritance does not introduce new classes of faults except insofar as it is associated with polymorphism and dynamic binding, which we have already discussed, and exception handling, which is discussed in Section 15.12. It does provide an opportunity for optimization by reusing test cases and even test executions. Subclasses share methods with ancestors. Identifying which methods do not need to be retested and which test cases can be reused may significantly reduce testing effort. Methods of a subclass can be categorized as New if they are newly defined in the subclass – that is, they do not occur in the ancestor. New methods include those with the same name but different parameters than methods in ancestor classes. Recursive if they are inherited from the ancestor without change – that is, they occur only in the ancestor. Redefined if they are overridden in the subclass, that is, both occur in the subclass. Abstract new if they are newly defined and abstract in the subclass. Abstract recursive if they are inherited from the ancestor, where they are abstract. Abstract redefined if they are redefined in the subclass, and they are abstract in the ancestor. When testing a base class, one that does not specialize a previously tested class, we can summarize the testing information in a simple table that indicates the sets of generated and executed test cases. Such a table is called a testing history. In general we will have four sets of test cases for a method: intraclass functional, intraclass structural, interclass functional, and interclass structural. For methods that do not call methods in other classes, we will have only intraclass test cases, since no integration test focuses on such methods. For abstract methods, we will only have functional test cases, since we do not have the code of the method. Each set of test cases is marked with a flag that indicates whether the test set can be executed. Table 15.5 shows a testing history for class LineItem, whose code is shown in Figure 15.16. Methods validItem, getWeightGm, getHeightCm, getWidthCm, and getDepthCm are abstract and do not interact with external classes; thus we only have intraclass functional test cases that cannot be directly executed. Method getUnitPrice is abstract, but from the specifications (not shown here) we can infer that it interacts with other classes; thus we have both intra-and interclass functional test cases. Both the constructor and method getExtendedPrice are implemented and interact with other classes (Order and AccountType, respectively), and thus we have all four sets of test cases. Table 15.5: Testing history for class LineItem

Table 15.5: Testing history for class LineItem Open table as spreadsheet Method

Intra funct

Intra struct

Inter funct

Inter struct

LineItem

〈TSLI1,Y 〉

〈TSLI2,Y 〉

〈TSLI3,Y 〉

〈TSLI4,Y 〉

validItem

〈TSvI1,N〉

〈–,–〉

getUnitPrice

〈TSgUP1,N〉

〈–,–〉

〈TSgUP3,N〉

〈–,–〉

getExtendedPrice

〈TSgXP1,Y 〉

〈TSgXP2,Y 〉

〈TSgXP3,Y 〉

〈TSgXP4,Y 〉

getWeightGm

〈TSgWG1,N〉

〈–,–〉

getHeightCm

〈TSgHC1,N〉

〈–,–〉

getWidthCm

〈TSgWC1,N〉

〈–,–〉

getDepthCm

〈TSgDC1,N〉

〈–,–〉

Legend: 〈TSI,B〉 refers to test set I, to be executed if B = Y. 〈–,–〉 means no applicable tests. 1

/** One line item of a customer order (abstract). */ 2 public abstract class LineItem { 3 4 /** The order this LineItem belongs to. */ 5 protected Order order; 6 7 /** Constructor links item to owning order. Must call in sub 8 public LineItem(Order order) { order = order; } 9 10 /** Stock-keeping unit (sku) is unique key to all product da 11 public String sku; 12 13 /** Number of identical units to be purchased. */ 14 public int units=1; 15 16 /** Has this line item passed all validation tests? */ 17 public abstract boolean validItem(); 18 19 /** Price of a single item. */ 20 public abstract int getUnitPrice(AccountType accountType); 21 22 /** Extended price for number of units */ 23 public int getExtendedPrice(AccountType accountType)

24 25 26 27 28 29 30 31 32 33 34 35

{

return units * this.getUnitPrice(accountType); }

// Dimensions for packing and shipping (required of all top/** Weight in grams */ public abstract int getWeightGm(); /** Height in centimeters */ public abstract int getHeightCm(); /** Width in Centimeters. */ public abstract int getWidthCm(); /** Depth in Centimeters */ public abstract int getDepthCm(); }

Figure 15.16: Part of a Java implementation of the abstract class LineItem. New and abstract new methods need to be tested from scratch, thus we need to derive the needed test cases and execute them. We report the testing activity in the testing history of the new class by adding a new row and new test cases. Recursive and abstract recursive methods do not need to be retested. Thus the old test sets are copied into the new table and marked as not-to-be-executed. Redefined and abstract redefined methods must be retested, so we add new test cases and mark them to be executed. Table 15.6 shows the testing history for class CompositeItem that specializes class LineItem. The code of class CompositeItem is shown in Figure 15.17. Class CompositeItem adds a constructor, and thus we add a line to the testing history that indicates the four sets of test cases to be added and executed. It redefines method getUnitPrice, which was virtual in class LineItem: the functional test cases derived for class LineItem are thus executed, and new structural test cases are added. All other classes are inherited, and thus the testing history reports all test cases and marks them as not-to-be-executed. Table 15.6: Testing history for class CompositeItem. New test sets are marked with a prime. Open table as spreadsheet Method

Intra funct

Intra struct

Inter funct

Inter struct

LineItem

〈TSLI1,N〉

〈TSLI2,N〉

〈TSLI3,N〉

〈TSLI4,N〉

validItem

〈TSvI1,N〉

〈–,–〉

getUnitPrice

〈TSgUP1,Y 〉

〈TS′gUP2,Y 〉

〈TSgUP3,Y 〉

〈TS′gUP4,Y 〉

getExtendedPrice

〈TSgXP1,N〉

〈TSgXP2,N〉

〈TSgXP3,N〉

〈TSgXP4,N〉

getWeightGm

〈TSgWG1,N〉

〈–,–〉

getHeightCm

〈TSgHC1,N〉

〈–,–〉

getWidthCm

〈TSgWC1,N〉

〈–,–〉

getDepthCm

〈TSgDC1,N〉

〈–,–〉

CompositeItem

〈TS′CM1,Y 〉

〈TS′CM2,Y 〉

〈TS′CM3,Y 〉

〈TS′CM4,Y 〉

package Orders; 2 import Accounts.AccountType; 3 import Prices.Pricelist; 4 import java.util.*; 5 6 /** 7 * A composite line item includes a “wrapper” item for the whole 8 * bundle and a set of zero or more component items. 9 */ 10 public abstract class CompositeItem extends LineItem { 11 12 /** 13 * A composite item has some unifying name and base price 14 * (which might be zero) and has zero or more additional pa 15 * which are themselves line items. 16 */ 17 private Vector parts = new Vector(); 18 19 /** 20 * Constructor from LineItem, links to an encompassing Orde 21 */ 22 public CompositeItem(Order order) { 23 super( order); 24 } 25 26 public int getUnitPrice(AccountType accountType) { 27 Pricelist prices = new Pricelist(); 28 int price = prices.getPrice(sku, accountType); 29 for (Enumeration e = parts.elements(); e.hasMoreElements 30 { 31 LineItem i = (LineItem) e.nextElement(); 32 price += i.getUnitPrice(accountType); 33 } 34 return price; 35 } 36 } 1

37 Figure 15.17: Part of a Java implementation of class CompositeItem. The testing history approach reduces the number of tests to be executed, but requires extra effort of keeping track of testing activities. Effort is repaid mainly when it is possible to avoid designing new test cases, but when the cost of executing test cases is high (e.g., because the test requires interaction with an external device or a human) the savings in test execution cost can also be significant. If the cost of executing test cases is negligible, it may be cheaper to simply retest all classes regardless of the tests executed on the ancestors.

15.11 Genericity Generics, also known as parameterized types or (in C++) as templates, are an important tool for building reusable components and libraries. A generic class (say, linked lists) is designed to be instantiated with many different parameter types (e.g., LinkedList and LinkedList). We can test only instantiations, not the generic class itself, and we may not know in advance all the different ways a generic class might be instantiated. A generic class is typically designed to behave consistently over some set of permitted parameter types. Therefore the testing (and analysis) job can be broken into two parts: showing that some instantiation is correct and showing that all permitted instantiations behave identically. Testing a single instantiation raises no particular problems, provided we have source code for both the generic class and the parameter class. Roughly speaking, we can design test cases as if the parameter were copied textually into the body of the generic class. Consider first the case of a generic class that does not make method calls on, nor access fields of, its parameters. Ascertaining this property is best done by inspecting the source code, not by testing it. If we can nonetheless conjecture some ways in which the generic and its parameter might interact (e.g., if the generic makes use of some service that a parameter type might also make use of, directly or indirectly), then we should design test cases aimed specifically at detecting such interaction. Gaining confidence in an unknowable set of potential instantiations becomes more difficult when the generic class does interact with the parameter class. For example, Java (since version 1.5) has permitted a declaration like this: class PriorityQueue { … } The generic PriorityQueue class will be able to make calls on the methods of interface Comparable. Now the behavior of PriorityQueue is not independent of E, but it should be dependent only in certain very circumscribed ways, and in particular it should behave correctly whenever E obeys the requirements of the contract implied by Comparable. The contract imposed on permitted parameters is a kind of specification, and specificationbased (functional) test selection techniques are an appropriate way to select representative instantiations of the generic class. For example, if we read the interface specification for java.lang.Comparable, we learn that most but not all classes that implement Comparable also satisfy the rule (x.compareTo(y) == 0) == (x.equals(y)) Explicit mention of this condition strongly suggests that test cases should include instantiations with classes that do obey this rule (class String, for example) and others that do not (e.g., class BigDecimal with two BigDecimal values 4.0 and 4.00).

15.12 Exceptions Programs in modern object-oriented languages use exceptions to separate handling of error cases from the primary program logic, thereby simplifying normal control flow. Exceptions also greatly reduce a common class of faults in languages without exception-handling constructs. One of the most common faults in C programs, for example, is neglecting to check for the error indications returned by a C function. In a language like Java, an exception is certain to interrupt normal control flow. The price of separating exception handling from the primary control flow logic is introduction of implicit control flows. The point at which an exception is caught and handled may be far from the point at which it is thrown. Moreover, the association of exceptions with handlers is dynamic. In most object-oriented languages and procedural languages that provide exception handling, an exception propagates up the stack of calling methods until it reaches a matching handler. Since exceptions introduce a kind of control flow, one might expect that it could be treated like other control flow in constructing program models and deriving test cases. However, treating every possible exception this way would create an unwieldy control flow graph accounting for potential exceptions at every array subscript reference, every memory allocation, every cast, and so on, and these would be multiplied by matching them to every handler that could appear immediately above them on the call stack. Worse, many of these potential exceptions are actually impossible, so the burden would not be just in designing test cases for each of them but in deciding which can actually occur. It is more practical to consider exceptions separately from normal control flow in test design. We can dismiss from consideration exceptions triggered by program errors signaled by the underlying system (subscript errors, bad casts, etc.), since exercising these exceptions adds nothing to other efforts to prevent or find the errors themselves. If a method A throws an exception that indicates a programming error, we can take almost the same approach. However, if there are exception handlers for these program error exceptions, such as we may find in fault-tolerant programs or in libraries that attempt to maintain data consistency despite errors in client code, then it is necessary to test the error recovery code (usually by executing it together with a stub class with the programming error). This is different and much less involved than testing the error recovery code coupled with every potential point at which the error might be present in actual code. Exceptions that indicate abnormal cases but not necessarily program errors (e.g., exhaustion of memory or premature end-of-file) require special treatment. If the handler for these is local (e.g., a Java try block with an exception handler around a group of file operations), then the exception handler itself requires testing. Whether to test each individual point where exceptions bound to the same handler might be raised (e.g., each individual file operation within the same try block) is a matter of judgment. The remaining exceptions are those that are allowed to propagate beyond the local context in which they are thrown. For example, suppose method A makes a call to method B, within

a Java try block with an exception handler for exceptions of class E. Suppose B has no exception handler for E and makes a call to method C, which throws E. Now the exception will propagate up the chain of method calls until it reaches the handler in A. There could be many such chains, which depend in part on overriding inherited methods, and it is difficult (sometimes even impossible) to determine all and only the possible pairings of points where an exception is thrown with handlers in other methods. Since testing all chains through which exceptions can propagate is impractical, it is best to make it unnecessary. A reasonable design rule to enforce is that, if a method propagates an exception without catching it, the method call should have no other effect. If it is not possible to ensure that method execution interrupted by an exception has no effect, then an exception handler should be present (even if it propagates the same exception by throwing it again). Then, it should suffice to design test cases to exercise each point at which an exception is explicitly thrown by application code, and each handler in application code, but not necessarily all their combinations.

Open Research Issues Many problems involved in test and analysis of object-oriented systems are still open. Most results about functional testing refer to a subset of UML and to algebraic specifications. Additional work is needed to complete the available methods to cope with all aspects of object-oriented systems and different specification approaches. The few techniques for structural testing disclose a wide set of problems that need additional investigation. We need additional experimental data about the effectiveness of the available techniques and better ways to cope with interclass testing. Test and analysis problems of many features that characterize object-oriented systems, such as exceptions, polymorphism, dynamic binding, and inheritance, have been investigated only partially and need additional work. Despite a good deal of experience with objectoriented design, we still have little information about common faults, and we lack fault taxonomies.

Further Reading Many recent books on software testing and software engineering address object-oriented software to at least some degree. The most complete book-length account of current methods is Binder’s Testing Object Oriented Systems [Bin00]. Structural state-based testing is discussed in detail by Buy, Orso, and Pezz` e [BOP00]. The data flow approach to testing software with polymorphism and dynamic binding was initially proposed by Orso [Ors98]. Harrold, McGregor, and Fitzpatrick [HMF92] provide a detailed discussion of the use of testing histories for selecting test cases for subclasses. Th´ evenod-Fosse and Waeselynck describe statistical testing using statechart specifications [TFW93]. An excellent paper by Doong and Frankl [DF94] introduces

equivalent scenarios. Although Doong and Frankl discuss their application with algebraic specifications (which are not much used in practice), the value of the approach does not hinge on that detail.

Related Topics Basic functional and structural testing strategies are treated briefly here, and readers who have not already read Chapters 10, 11, and 12 will find there a more thorough presentation of the rationale and basic techniques for those approaches. Chapters 13 and 14 likewise present the basic data flow and model-based testing approaches in more detail. As integration testing progresses beyond small clusters of classes to major subsystems and components, the interclass testing techniques described in this chapter will become less relevant, and component testing techniques presented in Chapter 21 more important. The system and acceptance testing techniques described in Chapter 22 are as appropriate to object-oriented software as they are to mixed and purely procedural software systems.

Exercises The set of test cases given in Table 15.1 is not the smallest test suite that satisfies the transition coverage criterion for the finite state machine (FSM) of Figure 15.7. 1. Derive a smaller set of test cases that satisfy the transition coverage criterion for the FSM. 15.1 2. Compare the two sets of test cases. What are the advantages of each?

15.2

15.3

15.4

3. Derive a suite of test cases that satisfies the simple transition coverage criterion but does not satisfy the transition coverage criterion. The test cases given in Table 15.1 assume that transitions not given explicitly are “don’t care,” and thus we do not exercise them. Modify the test suite, first assuming that omitted transitions are “error” transitions. Next, modify the same test suite, but instead assuming that the omitted transitions are “self” transitions. Are the two modified test suites different? Why or why not? Generate at least one equivalent and one nonequivalent scenario for at least one of the test cases TCA,…,TCE of Table 15.1. A canonical representation is a unique representation of a set of equivalent objects. For example, {a,a,c,b}, {c,b,a}, and {a,b,c} are all representations of the same mathematical set object. If we choose a lexicographically sorted representation without duplicates as a canonical representation, then we will use {a,b,c} as the unique way of writing that set. Imagine we are using the equivalent scenarios approach to test a hash table class. Why might we want a toString method that returns a canonical representation of the table? Give an example of a test case in which you might use it.

Chapter 16: Fault-Based Testing A model of potential program faults is a valuable source of information for evaluating and designing test suites. Some fault knowledge is commonly used in functional and structural testing, for example when identifying singleton and error values for parameter characteristics in category-partition testing or when populating catalogs with erroneous values, but a fault model can also be used more directly. Fault-based testing uses a fault model directly to hypothesize potential faults in a program under test, as well as to create or evaluate test suites based on its efficacy in detecting those hypothetical faults.

Required Background Chapter 9 The introduction to test case selection and adequacy sets the context for this chapter. Though not strictly required, it is helpful in understanding how the techniques described in this chapter should be applied. Chapter 12 Some basic knowledge of structural testing criteria is required to understand the comparison of fault-based with structural testing criteria.

16.1 Overview Engineers study failures to understand how to prevent similar failures in the future. For example, failure of the Tacoma Narrows Bridge in 1940 led to new understanding of oscillation in high wind and to the introduction of analyses to predict and prevent such destructive oscillation in subsequent bridge design. The causes of an airline crash are likewise extensively studied, and when traced to a structural failure they frequently result in a directive to apply diagnostic tests to all aircraft considered potentially vulnerable to similar failures. Experience with common software faults sometimes leads to improvements in design methods and programming languages. For example, the main purpose of automatic memory management in Java is not to spare the programmer the trouble of releasing unused memory, but to prevent the programmer from making the kind of memory management errors (dangling pointers, redundant deallocations, and memory leaks) that frequently occur in C and C++ programs. Automatic array bounds checking cannot prevent a programmer from using an index expression outside array bounds, but can make it much less likely that the fault escapes detection in testing, as well as limiting the damage incurred if it does lead to operational failure (eliminating, in particular, the buffer overflow attack as a means of subverting privileged programs). Type checking reliably detects many other faults during program translation. Of course, not all programmer errors fall into classes that can be prevented or statically detected using better programming languages. Some faults must be detected through testing, and there too we can use knowledge about common faults to be more effective. The basic concept of fault-based testing is to select test cases that would distinguish the program under test from alternative programs that contain hypothetical faults. This is usually approached by modifying the program under test to actually produce the hypothetical faulty programs. Fault seeding can be used to evaluate the thoroughness of a test suite (that is, as an element of a test adequacy criterion), or for selecting test cases to augment a test suite, or to estimate the number of faults in a program.

16.2 Assumptions in Fault-Based Testing The effectiveness of fault-based testing depends on the quality of the fault model and on some basic assumptions about the relation of the seeded faults to faults that might actually be present. In practice, the seeded faults are small syntactic changes, like replacing one variable reference by another in an expression, or changing a comparison from 0) { emit(buf, pos); } }

Figure 16.1: Program transduce converts line endings among Unix, DOS, and Macintosh conventions. The main procedure, which selects the output line end convention, and the output procedure emit are not shown. Since mutants must be valid, mutation operators are syntactic patterns defined relative to particular programming languages. Figure 16.2 shows some mutation operators for the C language. Constraints are associated with mutation operators to guide selection of test cases likely to distinguish mutants from the original program. For example, the mutation operator svr (scalar variable replacement) can be applied only to variables of compatible type (to be valid), and a test case that distinguishes the mutant from the original program must execute the modified statement in a state in which the original variable and its substitute have different values. Open table as spreadsheet ID

Operator

Description

Constraint

Operand Modifications constant for constant replacement

replace constant C1 with constant C2 C1 ≠ C2

scr

scalar for constant replacement

replace constant C with scalar variable C≠X X

acr

array for constant replacement

replace constant C with array reference A[I]

crp

scr

struct for constant replacement

C ≠ A[I]

replace constant C with struct field S

C≠S

svr

scalar variable replacement

replace scalar variable X with a scalar variable Y

X≠Y

csr

constant for scalar variable replacement

replace scalar variable X with a constant C

X≠C

asr

array for scalar variable replacement

replace scalar variable X with an array reference A[I]

X ≠ A[I]

struct for scalar replacement

replace scalar variable X with struct field S

X≠S

ssr

vie

car

scalar variable initialization elimination constant for array replacement

sar

scalar for array replacement

cnr

comparable array replacement

sar

struct for array reference replacement

remove initialization of a scalar variable

replace array reference A[I] with constant C replace array reference A[I] with scalar variable X

A[I]≠C

replace array reference with a comparable array reference replace array reference A[I] with a struct field S

A[I]≠S

Expression Modifications abs

absolute value insertion

replace e by abs(e)

e= BUFLEN–2) (pos == BUFLEN–2)

1U 1D

2M End Long Mixed

–

ror

(pos > 0) (pos >= 0)

–

sdl

atCR = 0 nothing

–

atCR = 0 pos = 0

–

ssr

Open table as spreadsheet Test case

1U 1D

Description

Test case

One line, Unix lineend

One line, DOS lineend

End

Description

Two lines, Mac line-end Last line not terminated with line-end sequence

2U Two lines, Unix line-end Long 2D

Two lines, DOS line-end

Mixed

Very long line (greater than buffer length) Mix of DOS and Unix line ends in the same file

Figure 16.3: A sample set of mutants for program Transduce generated with mutation operators from Figure 16.2. x indicates the mutant is killed by the test case in the column head. kills Mj, which can be distinguished from the original program by test cases 1D,2U, 2D, and 2M. Mutants Mi, Mk, and Ml are not distinguished from the original program by any test in TS. We say that mutants not killed by a test suite are live. A mutant can remain live for two reasons: The mutant can be distinguished from the original program, but the test suite T does not contain a test case that distinguishes them (i.e., the test suite is not adequate with respect to the mutant). The mutant cannot be distinguished from the original program by any test case (i.e., the mutant is equivalent to the original program). Given a set of mutants SM and a test suite T, the fraction of nonequivalent mutants killed by T measures the adequacy of T with respect to SM. Unfortunately, the problem of identifying equivalent mutants is undecidable in general, and we could err either by claiming that a mutant is equivalent to the program under test when it is not or by counting some equivalent mutants among the remaining live mutants. The adequacy of the test suite TS evaluated with respect to the four mutants of Figure 16.3 is 25%. However, we can easily observe that mutant Mi is equivalent to the original program (i.e., no input would distinguish it). Conversely, mutants Mk and Ml seem to be nonequivalent to the original program: There should be at least one test case that distinguishes each of them from the original program. Thus the adequacy of TS, measured after eliminating the equivalent mutant Mi, is 33%. Mutant Ml is killed by test case Mixed, which represents the unusual case of an input file containing both DOS-and Unix-terminated lines. We would expect that Mixed would also kill Mk, but this does not actually happen: Both Mk and the original program produce the same result for Mixed. This happens because both the mutant and the original program fail in the same way.[1] The use of a simple oracle for checking the correctness of the outputs (e.g., checking each output against an expected output) would reveal the fault. The test suite TS2 obtained by adding test case Mixed to TS would be 100% adequate (relative to this set of mutants) after removing the fault.

Mutation Analysis vs. Structural Testing For typical sets of syntactic mutants, a mutation-adequate test suite will also be adequate with respect to simple structural criteria such as statement or branch coverage. Mutation adequacy can simulate and subsume a structural coverage criterion if the set of mutants can be killed only by satisfying the corresponding test coverage obligations. Statement coverage can be simulated by applying the mutation operator sdl (statement deletion) to each statement of a program. To kill a mutant whose only difference from the program under test is the absence of statement S requires executing the mutant and the program under test with a test case that executes S in the original program. Thus to kill all mutants generated by applying the operator sdl to statements of the program under test, we need a test suite that causes the execution of each statement in the original program. Branch coverage can be simulated by applying the operator cpr (constant for predicate replacement) to all predicates of the program under test with constants True and False. To kill a mutant that differs from the program under test for a predicate P set to the constant value False, we need to execute the mutant and the program under test with a test case that causes the execution of the True branch of P. To kill a mutant that differs from the program under test for a predicate P set to the constant value True,we need to execute the mutant and the program under test with a test case that causes the execution of the False branch of P. A test suite that satisfies a structural test adequacy criterion may or may not kill all the corresponding mutants. For example, a test suite that satisfies the statement coverage adequacy criterion might not kill an sdl mutant if the value computed at the statement does not affect the behavior of the program on some possible executions.

[1]The

program was in regular use by one of the authors and was believed to be correct. Discovery of the fault came as a surprise while using it as an example for this chapter.

16.5 Variations on Mutation Analysis The mutation analysis process described in the preceding sections, which kills mutants based on the outputs produced by execution of test cases, is known as strong mutation. It can generate a number of mutants quadratic in the size of the program. Each mutant must be compiled and executed with each test case until it is killed. The time and space required for compiling all mutants and for executing all test cases for each mutant may be impractical. The computational effort required for mutation analysis can be reduced by decreasing the number of mutants generated and the number of test cases to be executed. Weak mutation analysis decreases the number of tests to be executed by killing mutants when they produce a different intermediate state, rather than waiting for a difference in the final result or observable program behavior. weak mutation analysis With weak mutation, a single program can be seeded with many faults. A “metamutant” program is divided into segments containing original and mutated source code, with a mechanism to select which segments to execute. Two copies of the metamutant are executed in tandem, one with only original program code selected and the other with a set of live mutants selected. Execution is paused after each segment to compare the program state of the two versions. If the state is equivalent, execution resumes with the next segment of original and mutated code. If the state differs, the mutant is marked as dead, and execution of original and mutated code is restarted with a new selection of live mutants. Weak mutation testing does not decrease the number of program mutants that must be considered, but it does decrease the number of test executions and compilations. This performance benefit has a cost in accuracy: Weak mutation analysis may “kill” a mutant even if the changed intermediate state would not have an effect on the final output or observable behavior of the program. Like structural test adequacy criteria, mutation analysis can be used either to judge the thoroughness of a test suite or to guide selection of additional test cases. If one is designing test cases to kill particular mutants, then it may be important to have a complete set of mutants generated by a set of mutation operators. If, on the other hand, the goal is a statistical estimate of the extent to which a test suite distinguishes programs with seeded faults from the original program, then only a much smaller statistical sample of mutants is required. Aside from its limitation to assessment rather than creation statistical mutation analysis of test suites, the main limitation of statistical mutation analysis is that partial coverage is meaningful only to the extent that the generated mutants are a valid statistical model of occurrence frequencies of actual faults. To avoid reliance on this implausible assumption, the target coverage should be 100% of the sample; statistical sampling may keep the sample small enough to permit careful examination of equivalent mutants. Estimating Population Sizes

Counting fish Lake Winnemunchie is inhabited by two kinds of fish, a native trout and an introduced species of chub. The Fish and Wildlife Service wishes to estimate the populations to evaluate their efforts to eradicate the chub without harming the population of native trout. The population of chub can be estimated statistically as follows. 1000 chub are netted, their dorsal fins are marked by attaching a tag, then they are released back into the lake. Over the next weeks, fishermen are asked to report the number of tagged and untagged chub caught. If 50 tagged chub and 300 untagged chub are caught, we can calculate

and thus there are about 6000 untagged chub remaining in the lake. It may be tempting to also ask fishermen to report the number of trout caught and to perform a similar calculation to estimate the ratio between chub and trout. However, this is valid only if trout and chub are equally easy to catch, or if one can adjust the ratio using a known model of trout and chub vulnerability to fishing. Counting residual faults A similar procedure can be used to estimate the number of faults in a program: Seed a given number S of faults in the program. Test the program with some test suite and count the number of revealed faults. Measure the number of seeded faults detected, DS, and also the number of natural faults DN detected. Estimate the total number of faults remaining in the program, assuming the test suite is as effective at finding natural faults as it is at finding seeded faults, using the formula

If we estimate the number of faults remaining in a program by determining the proportion of seeded faults detected, we must be wary of the pitfall of estimating trout population by counting chub. The seeded faults are chub, the real faults are trout, and we must either have good reason for believing the seeded faults are no easier to detect than real remaining faults, or else make adequate allowances for uncertainty. The difference is that we cannot avoid the problem by repeating the process with trout – once a fault has been detected, our knowledge of its presence cannot be erased. We depend, therefore, on a very good fault model, so that the chub are as representative as possible of trout. Of course, if we use special bait for chub, or design test cases to detect particular seeded faults, then statistical estimation of the total population of fish or errors cannot be justified.

Hardware Fault-based Testing Fault-based testing is widely used for semiconductor and hardware system validation and evaluation both for evaluating the quality of test suites and for evaluating fault tolerance.

Semiconductor testing has conventionally been aimed at detecting random errors in fabrication, rather than design faults. Relatively simple fault models have been developed for testing semiconductor memory devices, the prototypical faults being “stuck-at-0” and “stuckat-1” (a gate, cell, or pin that produces the same logical value regardless of inputs). A number of more complex fault models have been developed for particular kinds of semiconductor devices (e.g., failures of simultaneous access in dualport memories). A test vector (analogous to a test suite for software) can be judged by the number of hypothetical faults it can detect, as a fraction of all possible faults under the model. Fabrication of a semiconductor device, or assembly of a hardware system, is more analogous to copying disk images than to programming. The closest analog of software is not the hardware device itself, but its design – in fact, a high-level design of a semiconductor device is essentially a program in a language that is compiled into silicon. Test and analysis of logic device designs faces the same problems as test and analysis of software, including the challenge of devising fault models. Hardware design verification also faces the added problem that it is much more expensive to replace faulty devices that have been delivered to customers than to deliver software patches. In evaluation of fault tolerance in hardware, the usual approach is to modify the state or behavior rather than the system under test. Due to a difference in terminology between hardware and software testing, the corruption of state or modification of behavior is called a “fault,” and artificially introducing it is called “fault injection.” Pin-level fault injection consists of forcing a stuck-at-0, a stuck-at-1, or an intermediate voltage level (a level that is neither a logical 0 nor a logical 1) on a pin of a semiconductor device. Heavy ion radiation is also used to inject random faults in a running system. A third approach, growing in importance as hardware complexity increases, uses software to modify the state of a running system or to simulate faults in a running simulation of hardware logic design.

Fault seeding can be used statistically in another way: To estimate the number of faults remaining in a program. Usually we know only the number of faults that have been detected, and not the number that remains. However, again to the extent that the fault model is a valid statistical model of actual fault occurrence, we can estimate that the ratio of actual faults found to those still remaining should be similar to the ratio of seeded faults found to those still remaining. Once again, the necessary assumptions are troubling, and one would be unwise to place too much confidence in an estimate of remaining faults. Nonetheless, a prediction with known weaknesses is better than a seat-of-the-pants guess, and a set of estimates derived in different ways is probably the best one can hope for. While the focus of this chapter is on fault-based testing of software, related techniques can be applied to whole systems (hardware and software together) to evaluate fault tolerance. Some aspects of fault-based testing of hardware are discussed in the sidebar on page 323.

Open Research Issues Fault-based testing has yet to be widely applied in software development, although it is an important research tool for evaluating other test selection techniques. Its limited impact on software practice so far can be blamed perhaps partly on computational expense and partly on the lack of adequate support by industrial strength tools. One promising direction in fault-based testing is development of fault models for particular classes of faults. These could result in more sharply focused fault-based techniques, and also partly address concerns about the extent to which the fault models conventionally used in mutation testing are representative of real faults. Two areas in which researchers have attempted to develop focused models, expressed as sets of mutation operators, are component interfaces and concurrency constructs. Particularly important is development of fault models based on actual, observed faults in software. These are almost certainly dependent on application domain and perhaps to some extent also vary across software development organizations, but too little empirical evidence is available on the degree of variability.

Further Reading Software testing using fault seeding was developed by Hamlet [Ham77] and independently by DeMillo, Lipton, and Sayward [DLS78]. Underlying theories for fault-based testing, and in particular on the conditions under which a test case can distinguish faulty and correct versions of a program, were developed by Morell [Mor90] and extended by Thompson, Richardson, and Clarke [TRC93]. Statistical mutation using a Bayesian approach to grow the sample until sufficient evidence has been collected has been described by Sahinoglu and Spafford [SS90]. Weak mutation was proposed by Howden [How82]. The sample mutation operators used in this chapter are adapted from the Mothra software testing environment [DGK+88].

Exercises

Consider the C function in Figure 16.4, used to determine whether a misspelled word a dictionary word by at most one character, which may be a deletion, an insertion, or (e.g., “text” is edit distance 1 from “test” by a substitution, and edit distance 1 from “t deletion of “s”).

1 2 3 4 5

/* edit1( s1, s2 ) returns TRUE iff s1 can be transformed * by inserting, deleting, or substituting a single charact * by a no-op (i.e., if they are already equal). */ 6 int edit1( char *s1, char *s2) {

16.1

7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

if (*s1 == 0) { if (*s2 == 0) return TRUE; /* Try inserting a character in s1 or deleting in s2 * if (*(s2+1)==0) return TRUE; return FALSE; } if (*s2 == 0) { /* Only match is by deleting last char f if (*(s1 + 1) == 0) return TRUE; return FALSE; } /* Now we know that neither string is empty */ if (*s1 == *s2) { return edit1(s1 +1, s2 +1); }

/* Mismatch; only dist 1 possibilities are identical str * inserting, deleting, or substituting character */

/* Substitution: We “look past” the mismatched character if (strcmp(s1+1, s2+1) == 0) return TRUE; /* Deletion: look past character in s1 */ if (strcmp(s1+1, s2) == 0) return TRUE; /* Insertion: look past character in s2 */ if (strcmp(s1, s2+1) == 0) return TRUE; return FALSE; }

Figure 16.4: C function to determine whether one string is with distance 1 of another.

Suppose we seed a fault in line 27, replacing s1 +1 by s1 + 0. Is there a test case th mutant using weak mutation, but not using strong mutation? Display such a test case one, or explain why there is none.

16.2

16.3

We have described weak mutation as continuing execution up to the point that a muta then restarting execution of the original and mutated program from the beginning. Wh execution just continue after killing a mutant? What would be necessary to make cont execution possible?

Motivate the need for the competent programmer and the coupling effect hypotheses mutation analysis still make sense if these hypotheses did not hold? Why?

16.4

Generate some invalid, valid-but-not-useful, useful, equivalent and nonequivalent muta program in Figure 16.1 using mutant operators from Figure

Chapter 17: Test Execution Whereas test design, even when supported by tools, requires insight and ingenuity in similar measure to other facets of software design, test execution must be sufficiently automated for frequent reexecution without little human involvement. This chapter describes approaches for creating the run-time support for generating and managing test data, creating scaffolding for test execution, and automatically distinguishing between correct and incorrect test case executions.

Required Background Chapter 7 Reasoning about program correctness is closely related to test oracles that recognize incorrect behavior at run-time. Chapters 9 and 10 Basic concepts introduced in these chapters are essential background for understanding the distinction between designing a test case specification and executing a test case. Chapters 11 through 16 These chapters provide more context and concrete examples for understanding the material presented here.

17.1 Overview Designing tests is creative; executing them should be as mechanical as compiling the latest version of the product, and indeed a product build is not complete until it has passed a suite of test cases. In many organizations, a complete build-and-test cycle occurs nightly, with a report of success or problems ready each morning. The purpose of run-time support for testing is to enable frequent hands-free reexecution of a test suite. A large suite of test data may be generated automatically from a more compact and abstract set of test case specifications. For unit and integration testing, and sometimes for system testing as well, the software under test may be combined with additional “scaffolding” code to provide a suitable test environment, which might, for example, include simulations of other software and hardware resources. Executing a large number of test cases is of little use unless the observed behaviors are classified as passing or failing. The human eye is a slow, expensive, and unreliable instrument for judging test outcomes, so test scaffolding typically includes automated test oracles. The test environment often includes additional support for selecting test cases (e.g., rotating nightly through portions of a large test suite over the course of a week) and for summarizing and reporting results.

17.2 From Test Case Specifications to Test Cases If the test case specifications produced in test design already include concrete input values and expected results, as for example in the category-partition method, then producing a complete test case may be as simple as filling a template with those values. A more general test case specification (e.g., one that calls for “a sorted sequence, length greater than 2, with items in ascending order with no duplicates”) may designate many possible concrete test cases, and it may be desirable to generate just one instance or many. There is no clear, sharp line between test case design and test case generation. A rule of thumb is that, while test case design involves judgment and creativity, test case generation should be a mechanical step. Automatic generation of concrete test cases from more abstract test case specifications reduces the impact of small interface changes in the course of development. Corresponding changes to the test suite are still required with each program change, but changes to test case specifications are likely to be smaller and more localized than changes to the concrete test cases. Instantiating test cases that satisfy several constraints may be simple if the constraints are independent (e.g., a constraint on each of several input parameter values), but becomes more difficult to automate when multiple constraints apply to the same item. Some wellformed sets of constraints have no solution at all (“an even, positive integer that is not the sum of two primes”). Constraints that appear to be independent may not be. For example, a test case specification that constrains both program input and output imposes a conjunction of two constraints on output (it conforms to the given output constraint and it is produced by the given input). General test case specifications that may require considerable computation to produce test data often arise in model-based testing. For example, if a test case calls for program execution corresponding to a certain traversal of transitions in a finite state machine model, the test data must trigger that traversal, which may be quite complex if the model includes computations and semantic constraints (e.g., a protocol model in Promela; see Chapter 8). Fortunately, model-based testing is closely tied to model analysis techniques that can be adapted as test data generation methods. For example, finite state verification techniques typically have facilities for generating counter-examples to asserted properties. If one can express the negation of a test case specification, then treating it as a property to be verified will result in a counter-example from which a concrete test case can be generated.

17.3 Scaffolding During much of development, only a portion of the full system is available for testing. In modern development methodologies, the partially developed system is likely to consist of one or more runnable programs and may even be considered a version or prototype of the final system from very early in construction, so it is possible at least to execute each new portion of the software as it is constructed, but the external interfaces of the evolving system may not be ideal for testing; often additional code must be added. For example, even if the actual subsystem for placing an order with a supplier is available and fully operational, it is probably not desirable to place a thousand supply orders each night as part of an automatic test run. More likely a portion of the order placement software will be “stubbed out” for most test executions. Code developed to facilitate testing is called scaffolding, by analogy to the temporary structures erected around a building during construction or maintenance. Scaffolding may include test drivers (substituting for a main or calling program), test harnesses (substituting for parts of the deployment environment), and stubs (substituting for functionality called or used by the software under test), in addition to program instrumentation and support for recording and managing test execution. A common estimate is that half of the code developed in a software project is scaffolding of some kind, but the amount of scaffolding that must be constructed with a software project can vary widely, and depends both on the application domain and the architectural design and build plan, which can reduce cost by exposing appropriate interfaces and providing necessary functionality in a rational order. The purposes of scaffolding are to provide controllability to execute test cases and observability to judge the outcome of test execution. Sometimes scaffolding is required to simply make a module executable, but even in incremental development with immediate integration of each module, scaffolding for controllability and observability may be required because the external interfaces of the system may not provide sufficient control to drive the module under test through test cases, or sufficient observability of the effect. It may be desirable to substitute a separate test “driver” program for the full system, in order to provide more direct control of an interface or to remove dependence on other subsystems. Consider, for example, an interactive program that is normally driven through a graphical user interface. Assume that each night the program goes through a fully automated and unattended cycle of integration, compilation, and test execution. It is necessary to perform some testing through the interactive interface, but it is neither necessary nor efficient to execute all test cases that way. Small driver programs, independent of the graphical user interface, can drive each module through large test suites in a short time. When testability is considered in software architectural design, it often happens that interfaces exposed for use in scaffolding have other uses. For example, the interfaces needed to drive an interactive program without its graphical user interface are likely to serve also as the interface for a scripting facility. A similar phenomenon appears at a finer grain. For example, introducing a Java interface to isolate the public functionality of a class and hide methods introduced for testing the implementation has a cost, but also potential side

benefits such as making it easier to support multiple implementations of the interface.

17.4 Generic versus Specific Scaffolding The simplest form of scaffolding is a driver program that runs a single, specific test case. If, for example, a test case specification calls for executing method calls in a particular sequence, this is easy to accomplish by writing the code to make the method calls in that sequence. Writing hundreds or thousands of such test-specific drivers, on the other hand, may be cumbersome and a disincentive to thorough testing. At the very least one will want to factor out some of the common driver code into reusable modules. Sometimes it is worthwhile to write more generic test drivers that essentially interpret test case specifications. At least some level of generic scaffolding support can be used across a fairly wide class of applications. Such support typically includes, in addition to a standard interface for executing a set of test cases, basic support for logging test execution and results. Figure 17.1 illustrates use of generic test scaffolding in the JFlex lexical analyzer generator. public final class IntCharSet { 75 … 76 public void add(Interval intervall) { 186 … 187 } 1

1 2 3 4 5 11 12 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

package JFlex.tests; import JFlex.IntCharSet; import JFlex.Interval; import junit.framework.TestCase; … public class CharClassesTest extends TestCase { … public void testAdd1() { IntCharSet set = new IntCharSet(new Interval(‘a’,’h’)); set.add(new Interval(‘o’,’z’)); set.add(new Interval(‘A’,’Z’)); set.add(new Interval(‘h’,’o’)); assertEquals(“{ [‘A’-‘Z’][‘a’-‘z’] }”, set.toString()); } public void testAdd2() { IntCharSet set = new IntCharSet(new Interval(‘a’,’h’)); set.add(new Interval(‘o’,’z’)); set.add(new Interval(‘A’,’Z’)); set.add(new Interval(‘i’,’n’)); assertEquals(“{ [‘A’-‘Z’][‘a’-‘z’] }”, set.toString()); }

99 100

… }

Figure 17.1: Excerpt of JFlex 1.4.1 source code (a widely used open-source scanner generator) and accompanying JUnit test cases. JUnit is typical of basic test scaffolding libraries, providing support for test execution, logging, and simple result checking (assertEquals in the example). The illustrated version of JUnit uses Java reflection to find and execute test case methods; later versions of JUnit use Java annotation (metadata) facilities, and other tools use source code preprocessors or generators. Fully generic scaffolding may suffice for small numbers of hand-written test cases. For larger test suites, and particularly for those that are generated systematically (e.g., using the combinatorial techniques described in Chapter 11 or deriving test case specifications from a model as described in Chapter 14), writing each test case by hand is impractical. Note, however, that the Java code expressing each test case in Figure 17.1 follows a simple pattern, and it would not be difficult to write a small program to convert a large collection of input, output pairs into procedures following the same pattern. A large suite of automatically generated test cases and a smaller set of hand-written test cases can share the same underlying generic test scaffolding. Scaffolding to replace portions of the system is somewhat more demanding, and again both generic and application-specific approaches are possible. The simplest kind of stub, sometimes called a mock, can be generated automatically by analysis of the source code. A mock is limited to checking expected invocations and producing precomputed results that are part of the test case specification or were recorded in a prior execution. Depending on system build order and the relation of unit testing to integration in a particular process, isolating the module under test is sometimes considered an advantage of creating mocks, as compared to depending on other parts of the system that have already been constructed. The balance of quality, scope, and cost for a substantial piece of scaffolding software – say, a network traffic generator for a distributed system or a test harness for a compiler – is essentially similar to the development of any other substantial piece of software, including similar considerations regarding specialization to a single project or investing more effort to construct a component that can be used in several projects. The balance is altered in favor of simplicity and quick construction for the many small pieces of scaffolding that are typically produced during development to support unit and small-scale integration testing. For example, a database query may be replaced by a stub that provides only a fixed set of responses to particular query strings.

17.5 Test Oracles It is little use to execute a test suite automatically if execution results must be manually inspected to apply a pass/fail criterion. Relying on human intervention to judge test outcomes is not merely expensive, but also unreliable. Even the most conscientious and hard-working person cannot maintain the level of attention required to identify one failure in a hundred program executions, little more one or ten thousand. That is a job for a computer. Software that applies a pass/fail criterion to a program execution is called a test oracle, often shortened to oracle. In addition to rapidly classifying a large number of test case executions, automated test oracles make it possible to classify behaviors that exceed human capacity in other ways, such as checking real-time response against latency requirements or dealing with voluminous output data in a machine-readable rather than human-readable form. Ideally, a test oracle would classify every execution of a correct program as passing and would detect every program failure. In practice, the pass/fail criterion is usually imperfect. A test oracle may apply a pass/fail criterion that reflects only part of the actual program specification, or is an approximation, and therefore passes some program executions it ought to fail. Several partial test oracles (perhaps applied with different parts of the test suite) may be more cost-effective than one that is more comprehensive. A test oracle may also give false alarms, failing an execution that it ought to pass. False alarms in test execution are highly undesirable, not only because of the direct expense of manually checking them, but because they make it likely that real failures will be overlooked. Nevertheless sometimes the best we can obtain is an oracle that detects deviations from expectation that may or may not be actual failures. One approach to judging correctness – but not the only one – compares the actual output or behavior of a program with predicted output or behavior. A test case with a comparisonbased oracle relies on predicted output that is either precomputed as part of the test case specification or can be derived in some way independent of the program under test. Precomputing expected test results is reasonable for a small number of relatively simple test cases, and is still preferable to manual inspection of program results because the expense of producing (and debugging) predicted results is incurred once and amortized over many executions of the test case. Support for comparison-based test oracles is often included in a test harness program or testing framework. A harness typically takes two inputs: (1) the input to the program under test (or can be mechanically transformed to a well-formed input), and (2) the predicted output. Frameworks for writing test cases as program code likewise provide support for comparison-based oracles. The assertEquals method of JUnit, illustrated in Figure 17.1, is a simple example of comparison-based oracle support. Comparison-based oracles are useful mainly for small, simple test cases, but sometimes expected outputs can also be produced for complex test cases and large test suites. Capture-replay testing, a special case of this in which the predicted output or behavior is

preserved from an earlier execution, is discussed in this chapter. A related approach is to capture the output of a trusted alternate version of the program under test. For example, one may produce output from a trusted implementation that is for some reason unsuited for production use; it may too slow or may depend on a component that is not available in the production environment. It is not even necessary that the alternative implementation be more reliable than the program under test, as long as it is sufficiently different that the failures of the real and alternate version are likely to be independent, and both are sufficiently reliable that not too much time is wasted determining which one has failed a particular test case on which they disagree.

Figure 17.2: A test harness with a comparison-based test oracle processes test cases consisting of (program input, predicted output) pairs. A third approach to producing complex (input, output) pairs is sometimes possible: It may be easier to produce program input corresponding to a given output than vice versa. For example, it is simpler to scramble a sorted array than to sort a scrambled array. A common misperception is that a test oracle always requires predicted program output to compare to the output produced in a test execution. In fact, it is often possible to judge output or behavior without predicting it. For example, if a program is required to find a bus route from station A to station B, a test oracle need not independently compute the route to ascertain that it is in fact a valid route that starts at A and ends at B. Oracles that check results without reference to a predicted output are often partial, in the sense that they can detect some violations of the actual specification but not others. They check necessary but not sufficient conditions for correctness. For example, if the specification calls for finding the optimum bus route according to some metric, partial oracle a validity check is only a partial oracle because it does not check optimality. Similarly, checking that a sort routine produces sorted output is simple and cheap, but it is only a partial oracle because the output is also required to be a permutation of the input. A cheap partial oracle that can be used for a large number of test cases is often combined with a more expensive comparison-based oracle that can be used with a smaller set of test cases for which predicted output has been obtained. Ideally, a single expression of a specification would serve both as a work assignment and as a source from which useful test oracles were automatically derived. Specifications are often incomplete, and their informality typically makes automatic derivation of test oracles impossible. The idea is nonetheless a powerful one, and wherever formal or semiformal specifications (including design models) are available, it is worth-while to consider whether test oracles can be derived from them. Some of the effort of formalization will be incurred either early, in writing specifications, or later when oracles are derived from them, and

earlier is usually preferable. Model-based testing, in which test cases and test oracles are both derived from design models are discussed in Chapter 14.

17.6 Self-Checks as Oracles A program or module specification describes all correct program behaviors, so an oracle based on a specification need not be paired with a particular test case. Instead, the oracle can be incorporated into the program under test, so that it checks its own work (see Figure 17.3). Typically these self-checks are in the form of assertions, similar to assertions used in symbolic execution and program verification (see Chapter 7), but designed to be checked during execution.

Figure 17.3: When self-checks are embedded in the program, test cases need not include predicted outputs. Self-check assertions may be left in the production version of a system, where they provide much better diagnostic information than the uncontrolled application crash the customer may otherwise report. If this is not acceptable – for instance, if the cost of a runtime assertion check is too high – most tools for assertion processing also provide controls for activating and deactivating assertions. It is generally considered good design practice to make assertions and self-checks be free of side-effects on program state. Side-effect free assertions are essential when assertions may be deactivated, because otherwise suppressing assertion checking can introduce program failures that appear only when one is not testing. Self-checks in the form of assertions embedded in program code are useful primarily for checking module and subsystem-level specifications, rather than overall program behavior. Devising program assertions that correspond in a natural way to specifications (formal or informal) poses two main challenges: bridging the gap between concrete execution values and abstractions used in specification, and dealing in a reasonable way with quantification over collections of values. Test execution necessarily deals with concrete values, while abstract models are indispensable in both formal and informal specifications. Chapter 7 (page 110) describes the role of abstraction functions and structural invariants in specifying concrete operational behavior based on an abstract model of the internal state of a module. The intended effect of an operation is described in terms of a precondition (state before the operation) and postcondition (state after the operation), relating the concrete state to the abstract model. Consider again a specification of the get method of java.util.Map from Chapter 7, with preand postconditions expressed as the Hoare triple

φ is an abstraction function that constructs the abstract model type (sets of key, value pairs) from the concrete data structure. φ is a logical association that need not be implemented when reasoning about program correctness. To create a test oracle, it is useful to have an actual implementation of φ. For this example, we might implement a special observer method that creates a simple textual representation of the set of (key, value) pairs. Assertions used as test oracles can then correspond directly to the specification. Besides simplifying implementation of oracles by implementing this mapping once and using it in several assertions, structuring test oracles to mirror a correctness argument is rewarded when a later change to the program invalidates some part of that argument (e.g., by changing the treatment of duplicates or using a different data structure in the implementation). In addition to an abstraction function, reasoning about the correctness of internal structures usually involves structural invariants, that is, properties of the data structure that are preserved by all operations. Structural invariants are good candidates for self checks implemented as assertions. They pertain directly to the concrete data structure implementation, and can be implemented within the module that encapsulates that data structure. For example, if a dictionary structure is implemented as a red-black tree or an AVL tree, the balance property is an invariant of the structure that can be checked by an assertion within the module. Figure 17.4 illustrates an invariant check found in the source code of the Eclipse programming invariant. 1

package org.eclipse.jdt.internal.ui.text; 2 import java.text.CharacterIterator; 3 import org.eclipse.jface.text.Assert; 4 /** 5 *A CharSequence based implementation of 6 * CharacterIterator. 7 * @since 3.0 8 */ 9 public class SequenceCharacterIterator implements CharacterIter 13 … 14 private void invariant() { 15 Assert.isTrue(fIndex >= fFirst); 16 Assert.isTrue(fIndex last) throw new IllegalArgumentException(); if (last > sequence.length()) throw new IllegalArgumentException(); fSequence= sequence; fFirst= first; fLast= last; fIndex= first; invariant(); } …

public char setIndex(int position) { if (position >= getBeginIndex() && position ctx; 4 SSL_free(inctx->ssl); 5 sslconn->ssl = NULL; 6 inctx->ssl = NULL; 7 inctx->filter_ctx->pssl = NULL; 8 } This memory leak illustrates several properties typical of integration faults. In principle, it stems from incomplete knowledge of the protocol required to interact with some other portion of the code, either because the specification is (inevitably) incomplete or because it is not humanly possible to remember everything. The problem is due at least in part to a weakness of the programming language – it would not have occurred in a language with automatic garbage collection, such as Java. Finally, although the fault would be very difficult to detect with conventional unit testing techniques, there do exist both static and dynamic analysis techniques that could have made early detection much more likely, as discussed in Chapter 18.

Among strategies for incrementally testing partially assembled systems, we can distinguish two main classes: structural and feature oriented. In a structural approach, modules are constructed, assembled, and tested together in an order based on hierarchical structure in the design. Structural approaches include bottom-up, top-down, and a combination sometimes referred to as sandwich or backbone strategy. Feature-oriented strategies derive the order of integration from characteristics of the application, and include threads and critical modules strategies. Top-down and bottom-up strategies are classic alternatives in system construction and

incremental integration testing as modules accumulate. They consist in sorting modules according to the use/include relation (see Chapter 15, page 286), and in starting testing from the top or from the bottom of the hierarchy, respectively. A top-down integration strategy begins at the top of the uses hierarchy, including the interfaces exposed through a user interface or top-level application program interface (API). The need for drivers is reduced or eliminated while descending the hierarchy, since at each stage the already tested modules can be used as drivers while testing the next layer. For example, referring to the excerpt of the Chipmunk Web presence shown in Figure 21.1, we can start by integrating CustomerCare with Customer, while stubbing Account and Order. We could then add either Account or Order and Package, stubbing Model and Component in the last case. We would finally add Model, Slot, and Component in this order, without needing any driver.

Figure 21.1: An excerpt of the class diagram of the Chipmunk Web presence. Modules are sorted from the top to the bottom according to the use/include relation. The topmost modules are not used or included in any other module, while the bottom-most modules do not include or use other modules. Bottom-up integration similarly reduces the need to develop stubs, except for breaking circular relations. Referring again to the example in Figure 21.1, we can start bottom-up by integrating Slot with Component, using drivers for Model and Order.We can then incrementally add Model and Order. We can finally add either Package or Account and Customer, before integrating CustomerCare, without constructing stubs.

Top-down and bottom-up approaches to integration testing can be applied early in the development if paired with similar design strategies: If modules are delivered following the hierarchy, either top-down or bottom-up, they can be integrated and tested as soon as they are delivered, thus providing early feedback to the developers. Both approaches increase controllability and diagnosability, since failures are likely caused by interactions with the newly integrated modules. In practice, software systems are rarely developed strictly top-down or bottom-up. Design and integration strategies are driven by other factors, like reuse of existing modules or commercial off-the-shelf (COTS) components, or the need to develop early prototypes for user feedback. Integration may combine elements of the two approaches, starting from both ends of the hierarchy and proceeding toward the middle. An early top-down approach may result from developing prototypes for early user feedback, while existing modules may be integrated bottom-up. This is known as the sandwich or backbone strategy. For example, referring once more to the small system of Figure 21.1, let us imagine reusing existing modules for Model, Slot, and Component, and developing CustomerCare and Customer as part of an early prototype. We can start integrating CustomerCare and Customer top down, while stubbing Account and Order. Meanwhile, we can integrate bottom-up Model, Slot, and Component with Order, using drivers for Customer and Package. We can then integrate Account with Customer, and Package with Order, before finally integrating the whole prototype system. The price of flexibility and adaptability in the sandwich strategy is complex planning and monitoring. While top-down and bottom-up are straightforward to plan and monitor, a sandwich approach requires extra coordination between development and test. In contrast to structural integration testing strategies, feature-driven strategies select an order of integration that depends on the dynamic collaboration patterns among modules regardless of the static structure of the system. The thread integration testing strategy integrates modules according to system features. Test designers identify threads of execution that correspond to system features, and they incrementally test each thread. The thread integration strategy emphasizes module interplay for specific functionality. Referring to the Chipmunk Web presence, we can identify feature threads for assembling models, finalizing orders, completing payments, packaging and shipping, and so on. Feature thread integration fits well with software processes that emphasize incremental delivery of user-visible functionality. Even when threads do not correspond to usable end-user features, ordering integration by functional threads is a useful tactic to make flaws in integration externally visible. Incremental delivery of usable features is not the only possible consideration in choosing the order in which functional threads are integrated and tested. Risk reduction is also a driving force in many software processes. Critical module integration testing focuses on modules that pose the greatest risk to the project. Modules are sorted and incrementally integrated according to the associated risk factor that characterizes the criticality of each module. Both external risks (such as safety) and project risks (such as schedule) can be considered.

A risk-based approach is particularly appropriate when the development team does not have extensive experience with some aspect of the system under development. Consider once more the Chipmunk Web presence. If Chipmunk has not previously constructed software that interacts directly with shipping services, those interface modules will be critical because of the inherent risks of interacting with externally provided subsystems, which may be inadequately documented or misunderstood and which may also change. Feature-driven test strategies usually require more complex planning and management than structural strategies. Thus, we adopt them only when their advantages exceed the extra management costs. For small systems a structural strategy is usually sufficient, but for large systems feature-driven strategies are usually preferred. Often large projects require combinations of development strategies that do not fit any single test integration strategies. In these cases, quality managers would combine different strategies: top-down, bottom-up, and sandwich strategies for small subsystems, and a blend of threads and critical module strategies at a higher level.

21.3 Testing Components and Assemblies Many software products are constructed, partly or wholly, from assemblies of prebuilt software components.[1] A key characteristic of software components is that the organization that develops a component is distinct from the (several) groups of developers who use it to construct systems. The component developers cannot completely anticipate the uses to which a component will be put, and the system developers have limited knowledge of the component. Testing components (by the component developers) and assemblies (by system developers) therefore brings some challenges and constraints that differ from testing other kinds of module. Reusable components are often more dependable than software developed for a single application. More effort can be invested in improving the quality of a component when the cost is amortized across many applications. Moreover, when reusing a component that has been in use in other applications for some time, one obtains the benefit not only of test and analysis by component developers, but also of actual operational use. The advantages of component reuse for quality are not automatic. They do not apply to code that was developed for a single application and then scavenged for use in another. The benefit of operational experience as a kind of in vivo testing, moreover, is obtained only to the extent that previous uses of the component are quite similar to the new use. These advantages are balanced against two considerable disadvantages. First, a component designed for wide reuse will usually be much more complex than a module designed for a single use; a rule of thumb is that the development effort (including analysis and test) for a widely usable component is at least twice that for a module that provides equivalent functionality for a single application. In addition, a reusable component is by definition developed without full knowledge of the environment in which it will be used, and it is exceptionally difficult to fully and clearly describe all the assumptions, dependencies, and limitations that might impinge upon its use in a particular application. In general, a software component is characterized by a contract or application program interface (API) distinct from its implementation. Where a mature market has developed for components addressing a particular need, a single interface specification (e.g., SQL for database access or document object model (DOM) for access and traversal of XML data) can have several distinct implementations. The contract describes the component by specifying access points of the component, such as procedures (methods) and their parameters, possible exceptions, global variables, and input and output network connections. Even when the interface specification is bound to a single implementation, the logical distinction between interface and implementation is crucial to effective use and testing. Terminology for Components and Frameworks Component A software component is a reusable unit of deployment and composition that is deployed and integrated multiple times and usually by different teams. Components are characterized by a contract or interface and may or may not have state.

Components are often confused with objects, and a component can be encapsulated by an object or a set of objects, but they typically differ in many respects: Components typically use persistent storage, while objects usually have only local state. Components may be accessed by an extensive set of communication mechanisms, while objects are activated through method calls. Components are usually larger grain subsystems than objects. Component contract or interface The component contract describes the access points and parameters of the component, and specifies functional and nonfunctional behavior and any conditions required for using the component. Framework A framework is a micro-architecture or a skeleton of an application, with hooks for attaching application-specific functionality or configuration-specific components. A framework can be seen as a circuit board with empty slots for components. Frameworks and design patterns Patterns are logical design fragments, while frameworks are concrete elements of the application. Frameworks often implement patterns. Component-based system A component-based system is a system built primarily by assembling software components (and perhaps a small amount of application-specific code) connected through a framework or ad hoc “glue code.” COTS The term commercial off-the-shelf, or COTS, indicates components developed for the sale to other organizations.

The interface specification of a component should provide all the information required for reusing the component, including so-called nonfunctional properties such as performance or capacity limits, in addition to functional behavior. All dependence of the component on the environment in which it executes should also be specified. In practice, few component specifications are complete in every detail, and even details that are specified precisely can easily be overlooked or misunderstood when embedded in a complex specification document. The main problem facing test designers in the organization that produces a component is lack of information about the ways in which the component will be used. A component may be reused in many different contexts, including applications for which its functionality is an imperfect fit. A general component will typically provide many more features and options than are used by any particular application. A good deal of functional and structural testing of a component, focused on finding and removing as many program faults as possible, can be oblivious to the context of actual use.

As with system and acceptance testing of complete applications, it is then necessary to move to test suites that are more reflective of actual use. Testing with usage scenarios places a higher priority on finding faults most likely to be encountered in use and is needed to gain confidence that the component will be perceived by its users (that is, by developers who employ it as part of larger systems) as sufficiently dependable. Test designers cannot anticipate all possible uses of a component under test, but they can design test suites for classes of use in the form of scenarios. Test scenarios are closely related to scenarios or use cases in requirements analysis and design. Sometimes different classes of use are clearly evident in the component specification. For example, the W3 Document Object Model (DOM) specification has parts that deal exclusively with HTML markup and parts that deal with XML; these correspond to different uses to which a component implementing the DOM may be put. The DOM specification further provides two “views” of the component interface. In the flat view, all traversal and inspection operations are provided on node objects, without regard to subclass. In the structured view, each subclass of node offers traversal and inspection operations specific to that variety of node. For example, an Element node has methods to get and set attributes, but a Text node (which represents simple textual data within XML or HTML) does not.

Open Research Issues Ensuring quality of components and of component-based systems remains a challenging problem and a topic of current research. One research thread considers how dynamic analysis of components and component-based systems in one environment can produce useful information for assessing likely suitability for using some of the same components in another environment (by characterizing the contexts in which a component has been used successfully). A related approach of characterizing a set of behaviors and recognizing changes or differences (whether or not those differences are failures) may be applicable in the increasingly important context of dynamically configurable and field-upgradable systems, which pose all the problems of component-based systems with the additional complication of performing integration in deployed systems rather than in the development environment. For these and other systems, self-monitoring and postdeployment testing in the field are likely to play an increasingly important role in the future. Software design for testability is an important factor in the cost and effectiveness of test and analysis, particularly for module and component integration. To some extent modelbased testing (Chapter 14) is progress toward producing modules and components with well-specified and testable interfaces, but much remains to be done in characterizing and supporting testability. Design for testability should be an important factor in the evolution of architectural design approaches and notations, including architecture design languages.

Further Reading The buffer overflow problem in libpng, which caused security vulnerabilities in major Windows, Linux, and Mac OS X Web browsers and e-mail clients, was discovered in 2004

and documented by the United States Computer Emergency Readiness Team (CERT) in Vulnerability Note VU#388984 [Uni04]. The full report on the famous Ariane 5 failure [Lio96] is available from several sources on the Web. The NASA report on loss of the Mars Climate Orbiter [Ste99] is also available on the Web. Leveson [Lev04] describes the role of software in the Ariane failure, loss of the Mars Climate Orbiter, and other spacecraft losses. Weyuker [Wey98] describes challenges of testing component-based systems.

Exercises

21.1

21.2

21.3 [1]The

When developing a graphical editor, we used a COTS component for saving and reading files in XML format. During integration testing, the program failed when reading an empty file and when reading a file containing a syntax error. Try to classify the corresponding faults according to the taxonomy described in Table 21.1. The Chipmunk quality team decided to use both thread and critical module integration testing strategies for the Chipmunk Web presence. Envisage at least one situation in which thread integration should be preferred over critical module and one in which critical module testing should be preferred over thread, and motivate the choice. Can a backbone testing strategy yield savings in the cost of producing test scaffolding, relative to other structural integration testing strategies? If so, how and under what conditions? If not, why not?

term component is used loosely and often inconsistently in different contexts. Our working definition and related terms are explained in the sidebar on page 414.

Chapter 22: System, Acceptance, and Regression Testing System testing can be considered a final step in integration testing, but encompassing systemwide properties against a system specification. Acceptance testing abandons specifications in favor of users, and measures how the final system meets users’ expectations. Regression testing checks for faults introduced during evolution.

Required Background Chapter 4 The concepts of dependability, reliability, availability and mean time to failure are important for understanding the difference between system and acceptance testing. Chapter 17 Generating reusable scaffolding and test cases is a foundation for regression testing. Some knowledge about the scaffolding and test case generation problem, though not strictly required, may be useful for understanding regression testing problems.

22.1 Overview System, acceptance, and regression testing are all concerned with the behavior of a software system as a whole, but they differ in purpose. System testing is a check of consistency between the software system and its specification (it is a verification activity). Like unit and integration testing, system testing is primarily aimed at uncovering faults, but unlike testing activities at finer granularity levels, system testing focuses on system-level properties. System testing together with acceptance testing also serves an important role in assessing whether a product can be released to customers, which is distinct from its role in exposing faults to be removed to improve the product. System, Acceptance, and Regression Testing Open table as spreadsheet System test

Acceptance test

Regression test

Checks against requirements specifications

Checks suitability for user needs

Rechecks test cases passed by previous production versions

Performed by development test group

Performed by test group with user involvement

Performed by development test group

Validates usefulness and satisfaction with the product

Verifies correctness and completion of the product

Guards against unintended changes

Flaws in specifications and in development, as well as changes in users’ expectations, may result in products that do not fully meet users’ needs despite passing system tests. Acceptance testing, as its name implies, is a validation activity aimed primarily at the acceptability of the product, and it includes judgments of actual usefulness and usability rather than conformance to a requirements specification. Regression testing is specialized to the problem of efficiently checking for unintended effects of software changes. New functionality and modification of existing code may introduce unexpected interactions and lead latent faults to produce failures not experienced in previous releases.

22.2 System Testing The essential characteristics of system testing are that it is comprehensive, based on a specification of observable behavior, and independent of design and implementation decisions. System testing can be considered the culmination of integration testing, and passing all system tests is tantamount to being complete and free of known bugs. The system test suite may share some test cases with test suites used in integration and even unit testing, particularly when a thread-based or spiral model of development has been taken and subsystem correctness has been tested primarily through externally visible features and behavior. However, the essential characteristic of independence implies that test cases developed in close coordination with design and implementation may be unsuitable. The overlap, if any, should result from using system test cases early, rather than reusing unit and integration test cases in the system test suite. Independence in system testing avoids repeating software design errors in test design. This danger exists to some extent at all stages of development, but always in trade for some advantage in designing effective test cases based on familiarity with the software design and its potential pitfalls. The balance between these considerations shifts at different levels of granularity, and it is essential that independence take priority at some level to obtain a credible assessment of quality. In some organizations, responsibility for test design and execution shifts at a discrete point from the development team to an independent verification and validation team that is organizationally isolated from developers. More often the shift in emphasis is gradual, without a corresponding shift in responsible personnel. Particularly when system test designers are developers or attached to the development team, the most effective way to ensure that the system test suite is not unduly influenced by design decisions is to design most system test cases as early as possible. Even in agile development processes, in which requirements engineering is tightly interwoven with development, it is considered good practice to design test cases for a new feature before implementing the feature. When the time between specifying a feature and implementing it is longer, early design of system tests facilitates risk-driven strategies that expose critical behaviors to system test cases as early as possible, avoiding unpleasant surprises as deployment nears. For example, in the (imaginary) Chipmunk development of Web-based purchasing, some questions were raised during requirements specification regarding the point at which a price change becomes effective. For example, if an item’s catalog price is raised or lowered between the time it is added to the shopping cart and the time of actual purchase, which price is the customer charged? The requirement was clarified and documented with a set of use cases in which outcomes of various interleavings of customer actions and price changes were specified, and each of these scenarios became a system test case specification. Moreover, since this was recognized as a critical property with many opportunities for failure, the system architecture and build-plan for the Chipmunk Web presence was structured with interfaces that could be artificially driven through various scenarios early in

development, and with several of the system test scenarios simulated in earlier integration tests. The appropriate notions of thoroughness in system testing are with respect to the system specification and potential usage scenarios, rather than code or design. Each feature or specified behavior of the system should be accounted for in one or several test cases. In addition to facilitating design for test, designing system test cases together with the system requirements specification document helps expose ambiguity and refine specifications. The set of feature tests passed by the current partial implementation is often used as a gauge of progress. Interpreting a count of failing feature-based system tests is discussed in Chapter 20, Section 20.6. Additional test cases can be devised during development to check for observable symptoms of failures that were not anticipated in the initial system specification. They may also be based on failures observed and reported by actual users, either in acceptance testing or from previous versions of a system. These are in addition to a thorough specification-based test suite, so they do not compromise independence of the quality assessment. Some system properties, including performance properties like latency between an event and system response and reliability properties like mean time between failures, are inherently global. While one certainly should aim to provide estimates of these properties as early as practical, they are vulnerable to unplanned interactions among parts of a complex system and its environment. The importance of such global properties is therefore magnified in system testing. Global properties like performance, security, and safety are difficult to specify precisely and operationally, and they depend not only on many parts of the system under test, but also on its environment and use. For example, U.S. HIPAA regulations governing privacy of medical records require appropriate administrative, technical, and physical safeguards to protect the privacy of health information, further specified as follows: Implementation specification: safeguards. A covered entity must reasonably safeguard protected health information from any intentional or unintentional use or disclosure that is in violation of the standards, implementation specifications or other requirements of this subpart. [Uni00, sec. 164.530(c)(2)] It is unlikely that any precise operational specification can fully capture the HIPAA requirement as it applies to an automated medical records system. One must consider the whole context of use, including, for example, which personnel have access to the system and how unauthorized personnel are prevented from gaining access. Some global properties may be defined operationally, but parameterized by use. For example, a hard-real-time system must meet deadlines, but cannot do so in a completely arbitrary environment; its performance specification is parameterized by event frequency and minimum inter-arrival times. An e-commerce system may be expected to provide a certain level of responsiveness up to a certain number of transactions per second and to

degrade gracefully up to a second rate. A key step is identifying the “operational envelope” of the system, and testing both near the edges of that envelope (to assess compliance with specified goals) and well beyond it (to ensure the system degrades or fails gracefully). Defining borderline and extreme cases is logically part of requirements engineering, but as with precise specification of features, test design often reveals gaps and ambiguities. Not all global properties will be amenable to dynamic testing at all, at least in the conventional sense. One may specify a number of properties that a secure computer system should have, and some of these may be amenable to testing. Others can be addressed only through inspection and analysis techniques, and ultimately one does not trust the security of a system at least until an adversarial team has tried and failed to subvert it. Similarly, there is no set of test cases that can establish software safety, in part because safety is a property of a larger system and environment of which the software is only part. Rather, one must consider the safety of the overall system, and assess aspects of the software that are critical to that overall assessment. Some but not all of those claims may be amenable to testing. Testing global system properties may require extensive simulation of the execution environment. Creating accurate models of the operational environment requires substantial human resources, and executing them can require substantial time and machine resources. Usually this implies that “stress” testing is a separate activity from frequent repetition of feature tests. For example, a large suite of system test cases might well run each night or several times a week, but a substantial stress test to measure robust performance under heavy load might take hours to set up and days or weeks to run. A test case that can be run automatically with few human or machine resources should generally focus on one purpose: to make diagnosis of failed test executions as clear and simple as possible. Stress testing alters this: If a test case takes an hour to set up and a day to run, then one had best glean as much information as possible from its results. This includes monitoring for faults that should, in principle, have been found and eliminated in unit and integration testing, but which become easier to recognize in a stress test (and which, for the same reason, are likely to become visible to users). For example, several embedded system products ranging from laser printers to tablet computers have been shipped with slow memory leaks that became noticeable only after hours or days of continuous use. In the case of the tablet PC whose character recognition module gradually consumed all system memory, one must wonder about the extent of stress testing the software was subjected to. Unit, Integration, and System Testing Open table as spreadsheet Unit Test Test cases derived

module specifications

Integration Test architecture and design specifications

System Test

requirements specification

from Visibility required

all the details of the code

some details of the code, mainly interfaces

Scaffolding required

Potentially complex, to simulate the activation environment (drivers), the modules called by the module under test (stubs) and test oracles

Depends on architecture and integration order. Modules and subsystems can be incrementally integrated to reduce need for drivers and stubs.

Focus on

behavior of individual modules

module integration and interaction

no details of the code

Mostly limited to test oracles, since the whole system should not require additional drivers or stubs to be executed. Sometimes includes a simulated execution environment (e.g., for embedded systems).

system functionality

22.3 Acceptance Testing The purpose of acceptance testing is to guide a decision as to whether the product in its current state should be released. The decision can be based on measures of the product or process. Measures of the product are typically some inference of dependability based on statistical testing. Measures of the process are ultimately based on comparison to experience with previous products. Although system and acceptance testing are closely tied in many organizations, fundamental differences exist between searching for faults and measuring quality. Even when the two activities overlap to some extent, it is essential to be clear about the distinction, in order to avoid drawing unjustified conclusions. Quantitative goals for dependability, including reliability, availability, and mean time between failures, were introduced in Chapter 4. These are essentially statistical measures and depend on a statistically valid approach to drawing a representative sample of test executions from a population of program behaviors. Systematic testing, which includes all of the testing techniques presented heretofore in this book, does not draw statistically representative samples. Their purpose is not to fail at a “typical” rate, but to exhibit as many failures as possible. They are thus unsuitable for statistical testing. The first requirement for valid statistical testing is a precise definition of what is being measured and for what population. If system operation involves transactions, each of which consists of several operations, a failure rate of one operation in a thousand is quite different from a failure rate of one transaction in a thousand. In addition, the failure rate may vary depending on the mix of transaction types, or the failure rate may be higher when one million transactions occur in an hour than when the same transactions are spread across a day. Statistical modeling therefore necessarily involves construction of a model of usage, and the results are relative to that model. Suppose, for example, that a typical session using the Chipmunk Web sales facility consists of 50 interactions, the last of which is a single operation in which the credit card is charged and the order recorded. Suppose the Chipmunk software always operates flawlessly up to the point that a credit card is to be charged, but on half the attempts it charges the wrong amount. What is the reliability of the system? If we count the fraction of individual interactions that are correctly carried out, we conclude that only one operation in 100 fails, so the system is 99% reliable. If we instead count entire sessions, then it is only 50% reliable, since half the sessions result in an improper credit card charge. Statistical models of usage, or operational profiles, may be available from measurement of actual use of prior, similar systems. For example, use of a current telephone handset may be a reasonably good model of how a new handset will be used. Good models may also be obtained in embedded systems whose environment is primarily made up of predictable devices rather than unpredictable humans. In other cases one cannot justify high confidence in a model, but one can limit the uncertainty to a small number of parameters. One can perform sensitivity testing to determine which parameters are critical. Sensitivity testing

consists of repeating statistical tests while systematically varying parameters to note the effect of each parameter on the output. A particular parameter may have little effect on outcomes over the entire range of plausible values, or there may be an effect that varies smoothly over the range. If the effect of a given parameter is either large or varies discontinuously (e.g., performance falls precipitously when system load crosses some threshold), then one may need to make distinct predictions for different value ranges. A second problem faced by statistical testing, particularly for reliability, is that it may take a very great deal of testing to obtain evidence of a sufficient level of reliability. Consider that a system that executes once per second, with a failure rate of one execution in a million, or 99.9999% reliability, fails about 31 times each year; this may require a great testing effort and still not be adequate if each failure could result in death or a lawsuit. For critical systems, one may insist on software failure rates that are an insignificant fraction of total failures. For many other systems, statistical measures of reliability may simply not be worth the trouble. A less formal, but frequently used approach to acceptance testing is testing with users. An early version of the product is delivered to a sample of users who provide feedback on failures and usability. Such tests are often called alpha and beta tests. The two terms distinguish between testing phases. Often the early or alpha phases are performed within the developing organization, while the later or beta phases are performed at users’ sites. In alpha and beta testing, the user sample determines the operational profile. A good sample of users should include representatives of each distinct category of users, grouped by operational profile and significance. Suppose, for example, Chipmunk plans to provide Web-based sales facilities to dealers, industrial customers, and individuals. A good sample should include both users from each of those three categories and a range of usage in each category. In the industrial user category, large customers who frequently issue complex orders as well as small companies who typically order a small number of units should be represented, as the difference in their usage may lead to different failure rates. We may weigh differently the frequency of failure reports from dealers and from direct customers, to reflect either the expected mix of usage in the full population or the difference in consequence of failure.

22.4 Usability A usable product is quickly learned, allows users to work efficiently, and is pleasant to use. Usability involves objective criteria such as the time and number of operations required to perform tasks and the frequency of user error, in addition to the overall, subjective satisfaction of users. For test and analysis, it is useful to distinguish attributes that are uniquely associated with usability from other aspects of software quality (dependability, performance, security, etc.). Other software qualities may be necessary for usability; for example, a program that often fails to satisfy its functional requirements or that presents security holes is likely to suffer poor usability as a consequence. Distinguishing primary usability properties from other software qualities allows responsibility for each class of properties to be allocated to the most appropriate personnel, at the most cost-effective points in the project schedule. Even if usability is largely based on user perception and thus is validated based on user feedback, it can be verified early in the design and through the whole software life cycle. The process of verifying and validating usability includes the following main steps: Inspecting specifications with usability checklists. Inspection provides early feedback on usability. Testing early prototypes with end users to explore their mental model (exploratory test), evaluate alternatives (comparison test), and validate software usability. A prototype for early assessment of usability may not include any functioning software; a cardboard prototype may be as simple as a sequence of static images presented to users by the usability tester. Testing incremental releases with both usability experts and end users to monitor progress and anticipate usability problems. System and acceptance testing that includes expert-based inspection and testing, userbased testing, comparison testing against competitors, and analysis and checks often done automatically, such as a check of link connectivity and verification of browser compatibility. Userbased testing (i.e., testing with representatives of the actual end-user population) is particularly important for validating software usability. It can be applied at different stages, from early prototyping through incremental releases of the final system, and can be used with different goals: exploring the mental model of the user, evaluating design alternatives, and validating against established usability requirements and standards. The purpose of exploratory testing is to investigate the mental model of end users. It consists of asking users about their approach to interactions with the system. For example, during an exploratory test for the Chipmunk Web presence, we may provide users with a generic interface for choosing the model they would like to buy, in order to understand how users will interact with the system. A generic interface could present information about all

laptop computer characteristics uniformly to see which are examined first by the sample users, and thereby to determine the set of characteristics that should belong to the summary in the menu list of laptops. Exploratory test is usually performed early in design, especially when designing a system for a new target population. The purpose of comparison testing is evaluating options. It consists of observing user reactions to alternative interaction patterns. During comparison test we can, for example, provide users with different facilities to assemble the desired Chipmunk laptop configuration, and to identify patterns that facilitate users’ interactions. Comparison test is usually applied when the general interaction patterns are clear and need to be refined. It can substitute for exploratory testing if initial knowledge about target users is sufficient to construct a range of alternatives, or otherwise follows exploratory testing. The purpose of validation testing is assessing overall usability. It includes identifying difficulties and obstacles that users encounter while interacting with the system, as well as measuring characteristics such as error rate and time to perform a task. A well-executed design and organization of usability testing can produce results that are objective and accurately predict usability in the target user population. The usability test design includes selecting suitable representatives of the target users and organizing sessions that guide the test toward interpretable results. A common approach is divided into preparation, execution, and analysis phases. During the preparation phase, test designers define the objectives of the session, identify the items to be tested, select a representative population of end users, and plan the required actions. During execution, users are monitored as they execute the planned actions in a controlled environment. During analysis, results are evaluated, and changes to the software interfaces or new testing sessions are planned, if required. Each phase must be carefully executed to ensure success of the testing session. User time is a valuable and limited resource. Well-focused test objectives should not be too narrow, to avoid useless waste of resources, nor too wide, to avoid scattering resources without obtaining useful data. Focusing on specific interactions is usually more effective than attempting to assess the usability of a whole program at once. For example, the Chipmunk usability test team independently assesses interactions for catalog browsing, order definition and purchase, and repair service. The larger the population sample, the more precise the results, but the cost of very large samples is prohibitive; selecting a small but representative sample is therefore critical. A good practice is to identify homogeneous classes of users and select a set of representatives from each class. Classes of users depend on the kind of application to be tested and may be categorized by role, social characteristics, age, and so on. A typical compromise between cost and accuracy for a well-designed test session is five users from a unique class of homogeneous users, four users from each of two classes, or three users for each of three or more classes. Questionnaires should be prepared for the selected users to verify their membership in their respective classes. Some approaches also assign a weight to each class, according to their importance to the business. For example, Chipmunk

can identify three main classes of users: individual, business, and education customers. Each of the main classes is further divided. Individual customers are distinguished by education level; business customers by role; and academic customers by size of the institution. Altogether, six putatively homogeneous classes are obtained: Individual customers with and without at least a bachelor degree, managers and staff of commercial customers, and customers at small and large education institutions. Users are asked to execute a planned set of actions that are identified as typical uses of the tested feature. For example, the Chipmunk usability assessment team may ask users to configure a product, modify the configuration to take advantage of some special offers, and place an order with overnight delivery. Users should perform tasks independently, without help or influence from the testing staff. User actions are recorded, and comments and impressions are collected with a post-activity questionnaire. Activity monitoring can be very simple, such as recording sequences of mouse clicks to perform each action. More sophisticated monitoring can include recording mouse or eye movements. Timing should also be recorded and may sometimes be used for driving the sessions (e.g., fixing a maximum time for the session or for each set of actions). An important aspect of usability is accessibility to all users, including those with disabilities. Accessibility testing is legally required in some application domains. For example, some governments impose specific accessibility rules for Web applications of public institutions. The set of Web Content Accessibility Guidelines (WCAG) defined by the World Wide Web Consortium are becoming an important standard reference. The WCAG guidelines are summarized in the sidebar on page 426. Web Content Accessibility Guidelines (WCAG)[a] 1. Provide equivalent alternatives to auditory and visual content that convey essentially the same function or purpose. 2. Ensure that text and graphics are understandable when viewed without color. 3. Mark up documents with the proper structural elements, controlling presentation with style sheets rather than presentation elements and attributes. 4. Use markup that facilitates pronunciation or interpretation of abbreviated or foreign text. 5. Ensure that tables have necessary markup to be transformed by accessible browsers and other user agents. 6. Ensure that pages are accessible even when newer technologies are not supported or are turned off. 7. Ensure that moving, blinking, scrolling, or auto-updating objects or pages may be paused or stopped.

8. Ensure that the user interface, including embedded user interface elements, follows principles of accessible design: device-independent access to functionality, keyboard operability, self-voicing, and so on. 9. Use features that enable activation of page elements via a variety of input devices. 10. Use interim accessibility so that assisting technologies and older browsers will operate correctly. 11. Where technologies outside of W3C specifications is used (e.g, Flash), provide alternative versions to ensure accessibility to standard user agents and assistive technologies (e.g., screen readers). 12. Provide context and orientation information to help users understand complex pages or elements. 13. Provide clear and consistent navigation mechanisms to increase the likelihood that a person will find what they are looking for at a site. 14. Ensure that documents are clear and simple, so they may be more easily understood.

[a]Excerpted

and adapted from Web Content Accessibility Guidelines 1.0, W3C Recommendation 5-May 1999; used by permission. The current version is distributed by W3C at http://www.w3.org/TR/WAI-WEBCONTENT.

22.5 Regression Testing When building a new version of a system (e.g., by removing faults, changing or adding functionality, porting the system to a new platform, or extending interoperability), we may also change existing functionality in unintended ways. Sometimes even small changes can produce unforeseen effects that lead to new failures. For example, a guard added to an array to fix an overflow problem may cause a failure when the array is used in other contexts, or porting the software to a new platform may expose a latent fault in creating and modifying temporary files. When a new version of software no longer correctly provides functionality that should be preserved, we say that the new version regresses with respect to former versions. The nonregression of new versions (i.e., preservation of functionality), is a basic quality requirement. Disciplined design and development techniques, including precise specification and modularity that encapsulates independent design decisions, improves the likelihood of achieving nonregression. Testing activities that focus on regression problems are called (non) regression testing. Usually “non” is omitted and we commonly say regression testing. A simple approach to regression testing consists of reexecuting all test cases designed for previous versions. Even this simple retest all approach may present nontrivial problems and costs. Former test cases may not be reexecutable on the new version without modification, and rerunning all test cases may be too expensive and unnecessary. A good quality test suite must be maintained across system versions. Changes in the new software version may impact the format of inputs and outputs, and test cases may not be executable without corresponding changes. Even simple modifications of the data structures, such as the addition of a field or small change of data types, may invalidate former test cases, or outputs comparable with the new ones. Moreover, some test cases may be obsolete, since they test features of the software that have been modified, substituted, or removed from the new version. Scaffolding that interprets test case specifications, rather than fully concrete test data, can reduce the impact of input and output format changes on regression testing, as discussed in Chapter 17. Test case specifications and oracles that capture essential correctness properties, abstracting from arbitrary details of behavior, likewise reduce the likelihood that a large portion of a regression test suite will be invalidated by a minor change. High-quality test suites can be maintained across versions by identifying and removing obsolete test cases, and by revealing and suitably marking redundant test cases. Redundant cases differ from obsolete, being executable but not important with respect to the considered testing criteria. For example, test cases that cover the same path are mutually redundant with respect to structural criteria, while test cases that match the same partition are mutually redundant with respect to functional criteria. Redundant test cases may be introduced in the test suites due to concurrent work of different test designers or to changes in the code. Redundant test cases do not reduce the overall effectiveness of tests, but impact on the cost-benefits trade-off: They are unlikely to reveal faults, but they augment

the costs of test execution and maintenance. Obsolete test cases are removed because they are no longer useful, while redundant test cases are kept because they may become helpful in successive versions of the software. Good test documentation is particularly important. As we will see in Chapter 24, test specifications define the features to be tested, the corresponding test cases, the inputs and expected outputs, as well as the execution conditions for all cases, while reporting documents indicate the results of the test executions, the open faults, and their relation to the test cases. This information is essential for tracking faults and for identifying test cases to be reexecuted after fault removal.

22.6 Regression Test Selection Techniques Even when we can identify and eliminate obsolete test cases, the number of tests to be reexecuted may be large, especially for legacy software. Executing all test cases for large software products may require many hours or days of execution and may depend on scarce resources such as an expensive hardware test harness. For example, some mass market software systems must be tested for compatibility with hundreds of different hardware configurations and thousands of drivers. Many test cases may have been designed to exercise parts of the software that cannot be affected by the changes in the version under test. Test cases designed to check the behavior of the file management system of an operating system is unlikely to provide useful information when reexecuted after changes of the window manager. The cost of reexecuting a test suite can be reduced by selecting a subset of test cases to be reexecuted, omitting irrelevant test cases or prioritizing execution of subsets of the test suite by their relation to changes. Test case prioritization orders frequency of test case execution, executing all of them eventually but reducing the frequency of those deemed least likely to reveal faults by some criterion. Alternate execution is a variant on prioritization for environments with frequent releases and small incremental changes; it selects a subset of regression test cases for each software version. Prioritization can be based on the specification and code-based regression test selection techniques described later in this chapter. In addition, test histories and fault-proneness models can be incorporated in prioritization schemes. For example, a test case that has previously revealed a fault in a module that has recently undergone change would receive a very high priority, while a test case that has never failed (yet) would receive a lower priority, particularly if it primarily concerns a feature that was not the focus of recent changes. Regression test selection techniques are based on either code or specifications. Codebased selection techniques select a test case for execution if it exercises a portion of the code that has been modified. Specification-based criteria select a test case for execution if it is relevant to a portion of the specification that has been changed. Code-based regression test techniques can be supported by relatively simple tools. They work even when specifications are not properly maintained. However, like code-based test techniques in general, they do not scale well from unit testing to integration and system testing. In contrast, specification-based criteria scale well and are easier to apply to changes that cut across several modules. However, they are more challenging to automate and require carefully structured and well-maintained specifications. Among code-based test selection techniques, control-based techniques rely on a record of program elements executed by each test case, which may be gathered from an instrumented version of the program. The structure of the new and old versions of the program are compared, and test cases that exercise added, modified, or deleted elements are selected for reexecution. Different criteria are obtained depending on the program model on which the version comparison is based (e.g., control flow or data flow graph models).

Control flow graph (CFG) regression techniques are based on the differences between the CFGs of the new and old versions of the software. Let us consider, for example, the C function cgi_decode from Chapter 12. Figure 22.1 shows the original function as presented in Chapter 12, while Figure 22.2 shows a revison of the program. We refer to these two versions as 1.0 and 2.0, respectively. Version 2.0 adds code to fix a fault in interpreting hexadecimal sequences ‘%xy’. The fault was revealed by testing version 1.0 with input terminated by an erroneous subsequence ‘%x’, causing version 1.0 to read past the end of the input buffer and possibly overflow the output buffer. Version 2.0 contains a new branch to map the unterminated sequence to a question mark.

1 #include “hex_values.h” 2 /** Translate a string from the CGI encoding to plain ascii text. 3 * ‘+’ becomes space, %xx becomes byte with hex value xx, 4 * other alphanumeric characters map to themselves. 5 * Returns 0 for success, positive for erroneous input 6 * 1 = bad hexadecimal digit 7 */ 8 int cgi_decode(char *encoded, char *decoded) { 9 char *eptr = encoded; 10 char *dptr = decoded; 11 int ok=0; 12 while (*eptr) { 13 char c; 14 c = *eptr; 15 if (c == ‘+’) { /* Case 1: ‘+’ maps to blank */ 16 *dptr = ”; 17 } else if (c == ‘%’) { /* Case 2: ‘%xx’ is hex for character x 18 int digit_high = Hex_Values[*(++eptr)]; /* note illegal => 19 int digit_low = Hex_Values[*(++eptr)]; 20 if ( digit_high == -1 || digit low==-1) { 21 /* dptr=’?’; / 22 ok=1; /* Bad return code */ 23 } else { 24 *dptr = 16* digit_high + digit_low; 25 } 26 } else { /* Case 3: Other characters map to themselves */ 27 *dptr = eptr; 28 } 29 ++dptr; 30 ++eptr; 31 } 32 dptr = ‘’; /* Null terminator for string * 33 return ok; 34 }

Figure 22.1: C function cgi_decode version 1.0. The C function cgi_decode translates a cgi-encoded string to a plain ASCII string, reversing the encoding applied by the common gateway interface of most Web servers. Repeated from Figure 12.1 in Chapter 12.

1 #include “hex values.h” 2 /** Translate a string from the CGI encoding to plain ascii text. 3 * ‘+’ becomes space, %xx becomes byte with hex value xx, 4 * other alphanumeric characters map to themselves, illegal to ‘?’. 5 * Returns 0 for success, positive for erroneous input 6 * 1 = bad hex digit, non-ascii char, or premature end. 7 */ 8 int cgi_decode(char *encoded, char *decoded) { 9 char *eptr = encoded; 10 char *dptr = decoded; 11 int ok=0; 12 while (*eptr) { 13 char c; 14 c = *eptr; 15 if (c == ‘+’) { /* Case 1: ‘+’ maps to blank */ 16 *dptr = ”; 17 } else if (c == ‘%’) { /* Case 2: ‘%xx’ is hex for character x 18 if (! ( *(eptr + 1) && *(eptr + 2) )) { /* %xx must precede 19 ok=1; return; 20 } 21 /* OK, we know the xx are there, now decode them */ 22 int digit high = Hex Values[*(++eptr)]; /* note illegal => 23 int digit low = Hex Values[*(++eptr)]; 24 if ( digit high == -1 || digit low==-1) { 25 /* dptr=’?’; / 26 ok=1; /* Bad return code */ 27 } else { 28 *dptr = 16* digit high + digit low; 29 } 30 } else { /* Case 3: Other characters map to themselves */ 31 *dptr = *eptr; 32 } 33 if (! isascii(*dptr)) { /* Produce only legal ascii */ 34 *dptr = ‘?’; 35 ok=1; 36 } 37 ++dptr; 38 ++eptr;

39 } 40 *dptr = ‘’; /* Null terminator for string */ 41 return ok; 42 } Figure 22.2: Version 2.0 of the C function cgi_decode adds a control on hexadecimal escape sequences to reveal incorrect escape sequences at the end of the input string and a new branch to deal with non-ASCII characters. Let us consider all structural test cases derived for cgi_decode in Chapter 12, and assume we have recorded the paths exercised by the different test cases as shown in Figure 22.3. Recording paths executed by test cases can be done automatically with modest space and time overhead, since what must be captured is only the set of program elements exercised rather than the full history. Open table as spreadsheet Id

Test case

Path

TC1

“”

ABM

TC2

“test+case%1Dadequacy”

A B C D F L…B M

TC3

“adequate+test%0Dexecution%7U”

ABCDFL…BM

TC4

“%3D”

ABCDG HLBM

TC5

“%A”

ABCDGILBM

TC6

“a+b”

ABCDFLBCELBCDFLBM

TC7

“test”

ABCDFLBCDFLBCDFLB CDFLBM

TC8

“+%0D+%4J”

A B C E L B C D G I L…B M

TC9

“first+test%9Ktest%K9”

A B C D F L…B M

Figure 22.3: Paths covered by the structural test cases derived for version 1.0 of function cgi_decode. Paths are given referring to the nodes of the control flow graph of Figure 22.4. CFG regression testing techniques compare the annotated control flow graphs of the two program versions to identify a subset of test cases that traverse modified parts of the graphs. The graph nodes are annotated with corresponding program statements, so that comparison of the annotated CFGs detects not only new or missing nodes and arcs, but also nodes whose changed annotations correspond to small, but possibly relevant, changes in statements. The CFG for version 2.0 of cgi_decode is given in Figure 22.4. Differences between version

2.0 and 1.0 are indicated in gray. In the example, we have new nodes, arcs and paths. In general, some nodes or arcs may be missing (e.g., when part of the program is removed in the new version), and some other nodes may differ only in the annotations (e.g., when we modify a condition in the new version). CFG criteria select all test cases that exercise paths through changed portions of the CFG, including CFG structure changes and node annotations. In the example, we would select all test cases that pass through node D and proceed toward node G and all test cases that reach node L, that is, all test cases except TC1. In this example, the criterion is not very effective in reducing the size of the test suite because modified statements affect almost all paths.

Figure 22.4: The control flow graph of function cgi_decode version 2.0. Gray background indicates the changes from the former version. If we consider only the corrective modification (nodes X and Y ), the criterion is more effective. The modification affects only the paths that traverse the edge between D and G, so the CFG regression testing criterion would select only test cases traversing those nodes (i.e., TC2, TC3, TC4, TC5, TC8 and TC9). In this case the size of the test suite to be reexecuted includes two-thirds of the test cases of the original test suite. In general, the CFG regression testing criterion is effective only when the changes affect a relatively small subset of the paths of the original program, as in the latter case. It becomes almost useless when the changes affect most paths, as in version 2.0. Data flow (DF) regression testing techniques select test cases for new and modified pairs of definitions with uses (DU pairs, cf. Sections 6.1, page 77 and 13.2, page 236). DF regression selection techniques reexecute test cases that, when executed on the original program, exercise DU pairs that were deleted or modified in the revised program. Test

cases that executed a conditional statement whose predicate was altered are also selected, since the changed predicate could alter some old definition-use associations. Figure 22.5 shows the new definitions and uses introduced by modifications to cgi_decode.[1] These new definitions and uses introduce new DU pairs and remove others. Open table as spreadsheet Variable

Definitions

Uses

*eptr

eptr

dptr

dptr ok

W ZW

Figure 22.5: Definitions and uses introduced by changes in cgi_decode. Labels refer to the nodes in the control flow graph of Figure 22.4. In contrast to code-based techniques, specification-based test selection techniques do not require recording the control flow paths executed by tests. Regression test cases can be identified from correspondence between test cases and specification items. For example, when using category partition, test cases correspond to sets of choices, while in finite state machine model-based approaches, test cases cover states and transitions. Where test case specifications and test data are generated automatically from a specification or model, generation can simply be repeated each time the specification or model changes. Code-based regression test selection criteria can be adapted for model-based regression test selection. Consider, for example, the control flow graph derived from the process shipping order specification in Chapter 14. We add the following item to that specification: Restricted countries A set of restricted destination countries is maintained, based on current trade restrictions. If the shipping address contains a restricted destination country, only credit card payments are accepted for that order, and shipping proceeds only after approval by a designated company officer responsible for checking that the goods ordered may be legally exported to that country. The new requirement can be added to the flow graph model of the specification as illustrated in Figure 22.6.

Figure 22.6: A flow graph model of the specification of the shipping order functionality presented in Chapter 14, augmented with the “restricted country” requirement. The changes in the flow graph are indicated in black. We can identify regression test cases with the CFG criterion that selects all cases that correspond to international shipping addresses (i.e., test cases TC-1 and TC-5 from the following table). The table corresponds to the functional test cases derived using to the method described in Chapter 14 on page 259. Open table as spreadsheet Case

Too small

Ship where

Ship method

Cust type

Pay method

Same addr

CC valid

TC-1

Int

Air

Bus

Yes

TC-2

Dom

Land

–

TC-3

Yes

–

TC-4

Dom

Air

–

TC-5

Int

Land

–

TC-6

–

Edu

Inv

–

TC-7

–

Yes

–

TC-8

–

No (abort)

TC-9

–

No (no abort)

Models derived for testing can be used not only for selecting regression test cases, but also for generating test cases for the new code. In the preceding example, we can use the model not only to identify the test cases that should be reused, but also to generate new test cases for the new functionality, following the combinatorial approaches described in Chapter 11. [1]When

dealing with arrays, we follow the criteria discussed in Chapter 13: A change of an array value is a definition of the array and a use of the index. A use of an array value is a use of both the array and the index.

22.7 Test Case Prioritization and Selective Execution Regression testing criteria may select a large portion of a test suite. When a regression test suite is too large, we must further reduce the set of test cases to be executed. Random sampling is a simple way to reduce the size of the regression test suite. Better approaches prioritize test cases to reflect their predicted usefulness. In a continuous cycle of retesting as the product evolves, high-priority test cases are selected more often than low-priority test cases. With a good selection strategy, all test cases are executed sooner or later, but the varying periods result in an efficient rotation in which the cases most likely to reveal faults are executed most frequently. Priorities can be assigned in many ways. A simple priority scheme assigns priority according to the execution history: Recently executed test cases are given low priority, while test cases that have not been recently executed are given high priority. In the extreme, heavily weighting execution history approximates round robin selection. Other history-based priority schemes predict fault detection effectiveness. Test cases that have revealed faults in recent versions are given high priority. Faults are not evenly distributed, but tend to accumulate in particular parts of the code or around particular functionality. Test cases that exercised faulty parts of the program in the past often exercise faulty portions of subsequent revisions. Structural coverage leads to a set of priority schemes based on the elements covered by a test case. We can give high priority to test cases that exercise elements that have not recently been exercised. Both the number of elements covered and the “age” of each element (time since that element was covered by a test case) can contribute to the prioritization. Structural priority schemes produce several criteria depending on which elements we consider: statements, conditions, decisions, functions, files, and so on. The choice of the element of interest is usually driven by the testing level. Fine-grain elements such as statements and conditions are typically used in unit testing, while in integration or system testing one can consider coarser grain elements such as methods, features, and files.

Open Research Issues System requirements include many nonfunctional behavioral properties. While there is an active research community in reliability testing, in general, assessment of nonfunctional properties is not as well-studied as testing for correctness. Moreover, as trends in software develop, new problems for test and analysis are following the emphasis on particular nonfunctional properties. A prominent example of this over the last several years, and with much left to do, is test and analysis to assess and improve security. Selective regression test selection based on analysis of source code is now well-studied. There remains need and opportunity for improvement in techniques that give up the safety

guarantee (selecting all test cases that might be affected by a software change) to obtain more significant test suite reductions. Specification-based regression test selection is a promising avenue of research, particularly as more systems incorporate components without full source code. Increasingly ubiquitous network access is blurring the once-clear lines between alpha and beta testing and opening possibilities for gathering much more information from execution of deployed software. We expect to see advances in approaches to gathering information (both from failures and from normal execution) as well as exploiting potentially large amounts of gathered information. Privacy and confidentiality are an important research challenge in postdeployment monitoring.

Further Reading Musa [Mus04] is a guide to reliability engineering from a pioneer in the field; ongoing research appears in the International Symposium on Software Reliability Engineering (ISSRE) conference series. Graves et al. [GHK+98] and Rothermel and Harrold [RH97] provide useful overviews of selective regression testing. Kim and Porter [KP02] describe history-based test prioritization. Barnum [Bar01] is a well-regarded text on usability testing; Nielsen [Nie00] is a broader popular introduction to usability engineering, with a chapter on usability testing.

Exercises

22.4

Consider the Chipmunk Computer Web presence. Define at least one test case that may serve both during final integration and early system testing, at least one that serves only as an integration test case, and at least one that is more suitable as a system test case than as a final integration test case. Explain your choices. When and why should testing responsibilities shift from the development team to an independent quality team? In what circumstances might using an independent quality team be impractical? Identify some kinds of properties that cannot be efficiently verified with system testing, and indicate how you would verify them. Provide two or more examples of resource limitations that may impact system test more than module and integration test. Explain the difference in impact.

22.5

Consider the following required property of the Chipmunk Computer Web presence:

22.1

22.2 22.3

Customers should perceive that purchasing a computer using the Chipmunk Web presence is at least as convenient, fast, and intuitive as purchasing a computer in an off-line retail store. Would you check it as part of system or acceptance testing? Reformulate the property to allow test designers to check it in a different testing phase (system testing, if you consider the property checkable as part of acceptance testing, or vice versa).

Chapter 23: Automating Analysis and Test Automation can improve the efficiency of some quality activities and is a necessity for implementing others. While a greater degree of automation can never substitute for a rational, well-organized quality process, considerations of what can and should be automated play an important part in devising and incrementally improving a process that makes the best use of human resources. This chapter discusses some of the ways that automation can be employed, as well as its costs and limitations, and the maturity of the required technology. The focus is not on choosing one particular set of “best” tools for all times and situations, but on a continuing rational process of identifying and deploying automation to best effect as the organization, process, and available technology evolve.

Required Background Chapter 20 Some knowledge about planning and monitoring, though not strictly required, can be useful to understand the need for automated management support. Chapter 17 Some knowledge about execution and scaffolding is useful to appreciate the impact of tools for scaffolding generation and test execution. Chapter 19 Some knowledge about program analysis is useful to understand the need to automate analysis techniques.

23.1 Overview A rational approach to automating test and analysis proceeds incrementally, prioritizing the next steps based on variations in potential impact, variations in the maturity, cost, and scope of the applicable technology, and fit and impact on the organization and process. The potential role of automation in test and analysis activities can be considered along three nonorthogonal dimensions: the value of the activity and its current cost, the extent to which the activity requires or is made less expensive by automation, and the cost of obtaining or constructing tool support. Some test and analysis tasks depend so heavily on automation that a decision to employ a technique is tantamount to a decision to use tools. For example, employing structural coverage criteria in program testing necessarily means using coverage measurement tools. In other cases, an activity may be carried out manually, but automation reduces cost or improves effectiveness. For example, tools for capturing and replaying executions reduce the costs of reexecuting test suites and enable testing strategies that would be otherwise impractical. Even tasks that appear to be inherently manual may be enhanced with automation. For example, although software inspection is a manual activity at its core, a variety of tools have been developed to organize and present information and manage communication for software inspection, improving the efficiency of inspectors. The difficulty and cost of automating test and analysis vary enormously, ranging from tools that are so simple to develop that they are justifiable even if their benefits are modest to tools that would be enormously valuable but are simply impossible. For example, if we have specification models structured as finite state machines, automatic generation of test case specifications from the finite state model is a sufficiently simple and well-understood technique that obtaining or building suitable tools should not be an obstacle. At the other extreme, as we have seen in Chapter 2, many important problems regarding programs are undecidable. For example, no matter how much value we might derive from a tool that infallibly distinguishes executable from nonexecutable program paths, no such tool can exist. We must therefore weigh the difficulty or expense of automation together with potential benefits, including costs of training and integration. Difficulty and cost are typically entangled with scope and accuracy. Sometimes a generalpurpose tool (e.g., capture and replay for Windows applications) is only marginally more difficult to produce than a tool specialized for one project (e.g., capture and replay for a specific Windows application). Investment in the general-purpose tool, whether to build it or to buy it, can be amortized across projects. In other cases, it may be much more costeffective to create simple, project-specific tools that sidestep the complexity of more generic tools. However industrious and well-intentioned, humans are slow and error-prone when dealing with repetitive tasks. Conversely, simple repetitive tasks are often straightforward to automate, while judgment and creative problem solving remain outside the domain of automation. Human beings are very good at identifying the relevant execution scenarios that correspond to test case specifications (for example, by specifying the execution space of

the program under test with a finite state machine), but are very inefficient in generating large volumes of test cases (for example, by clicking combinations of menus in graphic interfaces), or identifying erroneous results within a large set of outputs produced when executing regression tests. Automating the repetitive portions of the task not only reduces costs, but improves accuracy as well.

23.2 Automation and Planning One important role of a test strategy is to prescribe tools for key elements of the quality process used in the organization. Analysis and test strategies can include very detailed process and tool prescriptions, particularly in critical application domains where quality assurance procedures are imposed by certification agencies, as in avionics software. In general, however, a single detailed process and its supporting tools will not be a uniformly good fit for a diverse set of software projects. Rather, an analysis and testing strategy can recommend different tools contingent on aspects of a project including application domain, development languages, and size. Overall quality strategies often indicate tools for organizing test design and execution and for generating quality documents, for collecting metrics, and for managing regression test suites. They less often indicate tools for generating test cases from requirement and design specifications, or for dynamic analysis. The quality plan for a particular project indicates tools inherited from the strategy as well as additional tools selected for that project. The quality manager should also evaluate needs and opportunities for acquiring or customizing existing tools or developing ad hoc solutions. For both organization-standard and project-specific tool choices, the plan must include related costs such as training, implied activities, and potential risks. The quality strategy and plan must position tools within a development process and an analysis and test methodology. Tools are worthless and even harmful if not properly contextualized. For example, while tools for measuring code coverage are simple and inexpensive, if not preceded by careful consideration of the role of coverage metrics in the test process, they are at best an annoyance, producing data that are not put to productive use, and at worst a distorting influence that steers the process in unplanned ways.

23.3 Process Management Managing a quality process involves planning a set of activities with appropriate cost and quality trade-offs, monitoring progress to identify risks as early as possible and to avoid delays, and adjusting the plan as needed. These tasks require human creativity and insight for which no tool can substitute. Nonetheless, tools can support process management, improving decision making by organizing and monitoring activities and results, facilitating group interaction, managing quality documents, and tracking costs. Classic planning tools facilitate task scheduling, resource allocation, and cost estimation by arranging tasks according to resource and time constraints. They can be specialized to analysis and test management with features for automatically deriving relations among tasks, launching tasks, and monitoring completion of activities. For example, quality planning tools can schedule test generation and execution activities consistent with dependence among quality activities and between quality and development activities. They can recognize delivery of a given artifact, automatically schedule execution of a corresponding test suite, notify the test designer of test results, record the actual execution time of the activity, and signal schedule deviations to the quality manager. Quality planning tools are most useful when integrated in the analysis and test environment to react automatically to events with activation of other tools and procedures. Analysis and testing involve complex relations among a large number of artifacts. A failure of a particular test case may be specific to a particular version of a module in some configurations of a system and to portions of a design specification that is in turn tied back to product requirements. An inspection may detect a fault indicated by a particular checklist item, which is applied by inspectors when they recognize a particular software design pattern, and that fault is also related to elements of the program, design, and version and configuration information. In most development projects, managing those relations, deriving useful information from them, and taking appropriate action are major tasks themselves. Fortunately, managing the Web of relations among artifacts can be automated and managed by version control tools. Version and configuration control tools relate versions of software artifacts and are often used to trigger consistency checks and other activities. They can support analysis and testing activities in much the same manner as they control assembly and compilation of related modules, for example, triggering execution of the appropriate test suites for each software modification, associating version status with test reports, and tracking completion of follow-up activities for detected failures. In other words, artifacts and tasks related to quality are simply part of the product and development process, with the same requirements and opportunities for automated support. Also like other aspects of a development environment, integrated quality tracking improves efficiency in a well-structured process, but does not by itself bring order out of chaos. Process management includes monitoring progress in terms of both schedule (comparing actual effort and completion times to a plan) and level of quality. Quality of the final product cannot be directly measured before its completion, but useful indications can be derived, for example, using the orthogonal defect classification discussed in Chapter 20. For both

schedule and quality, the essential function of tracking is to recognize deviations from expectation, so that an alert manager can direct attention to understanding and dealing with problems before they are insurmountable. Essential tasks that require human ingenuity include selecting or designing proxy measures that can be computed early, and interpreting those measures in a way that avoids misleading conclusions or distorted incentives. For example, counting lines of code is sometimes useful as a simple proxy for productivity, but must be carefully interpreted to avoid creating an incentive for verbosity or a disincentive for effective reuse of components. Similarly, the number of faults detected is a useful proxy measure if the goal is simply to detect deviations from the norm, but one should be as concerned about the causes of abnormally low numbers as high. Collection, summary, and presentation of data can be automated; design and interpretation cannot. Effective management also involves coordinating people, who may work in different groups or even different companies, possibly distributed across time zones and continents. Several studies have indicated that a large proportion of a software engineer’s time is devoted to communication. It is therefore important both to facilitate effective communication and to limit disruptions and distractions of unmanaged communication. Where simple general-purpose tools like e-mail, chats, and forums are employed, a key factor in their efficiency is appropriately matching synchronous communication or asynchronous communication to tasks. When excessive interruptions slow progress, replacing synchronous communication by asynchronous or scheduled communication may be indicated. Conversely, asynchronous communication may be replaced or augmented with synchronous communication (e.g., messaging or chat) to improve the efficiency of discussions that have been splintered into many small exchanges punctuated by waits for reply. Communication is most effective when all parties have immediate access to relevant information. In this regard, task-specific tools can improve on general-purpose communication support. For example, tools for distributed software inspections extend the familiar interfaces for chat (for synchronous inspection) or forum (for asynchronous inspection), adding managed presentation of the artifact to be inspected and appropriate portions of checklists and automated analysis results.

23.4 Static Metrics Static metrics measure software properties, often to estimate other properties. Among the most basic properties of software is size, which is strongly correlated to schedule and cost, including the cost of testing. Even something as straightforward as counting lines of code turns out to have several possible variations, depending on whether and how one filters out variations in white space, comments, and programming style. Common metrics of code size include: Size

Size of the source file, measured in bytes

Lines

All-inclusive count of lines in source code file

LOC

Lines of code, excluding comment and blank lines

eLOC

Effective lines of code, excluding comments, blank lines, and stand-alone braces or parenthesis

Logical lines of code, that is, statements as identified by logical separators such as semicolons Open table as spreadsheet

lLOC

Every programmer knows that there are variations in complexity between different pieces of code and that this complexity may be as important as sheer size. A number of attempts have been made to quantify aspects of complexity and readability: CDENS Blocks

Comment density (i.e., comment lines/eLOC) Number of basic blocks (i.e., sequences of statements with one entry point, one exit point, and no internal branches)

AveBlockL

Average number of lines per basic block

NEST

Control structure nesting level (minimum, maximum, and average)

Loops

Number of loops

LCSAJ

Number of linear code sequences; see Chapter 5

BRANCH Number of branches in the control flow graph Open table as spreadsheet Size and complexity may also be estimated on a coarser scale, considering only interfaces between units:

Cyclomatic Complexity Cyclomatic complexity is measured as e − n + 2, where e is the number of edges of the control flow graph and n is the number of nodes in the graph. Cyclomatic complexity does not depend on the size of the code but on branching in the control structure. For example, graphs CFG1 and CFG2, as follow, have the same cyclomatic

complexity, despite their different sizes, while the cyclomatic complexity of CFG3 is higher than that of CFG2 despite having the same number of nodes.

Low to moderate cyclomatic complexity (below 20) is interpreted as indicating a simple program; high cyclomatic complexity (above 20) indicates complex programs; very high cyclomatic complexity (above 50) characterizes programs that may be very difficult or impossible to thoroughly test. Cyclomatic complexity is certainly a sign of complex control flow structure, but it does not capture other aspects of logical complexity that can lead to difficulty in testing. There is little evidence that cyclomatic complexity is a more reliable predictor of testing effort or quality than lines of code.

Functions

Number of defined functions (or methods, procedures, etc.)

FPar

Number of formal parameters of functions

FRet

Number of return points of functions

IComplex

Interface complexity (i.e., FPar + FRet)

All these metrics are proxies for size and complexity. Despite several attempts beginning in the 1970s, no proposed metric has succeeded in capturing intrinsic complexity in a manner that robustly correlates with effort or quality. Lines of code, despite its obvious shortcomings, is not much worse than other measures of size. Among attempts to measure complexity, only cyclomatic complexity (V (g)) is still commonly collected by many tools (see sidebar). Cyclomatic complexity is defined as the number of independent paths through the control flow graph. Additional metrics have been introduced to capture complexity in structures unique to objectoriented programming: WMC DIT

Weighted methods per class, the sum of the complexities of methods in all classes, divided by the number of classes. This metric is parametric with respect to a measure of complexity in methods Depth of the inheritance tree of a class

NOC

Number of children (subclasses) of a class

RFC

Response for a class, the number of methods that may be executed in response to a method call to an object of the class. The size of the transitive closure of the calling relation rooted at a class

CBO

Coupling between object classes, the number of classes with which the class is coupled through any relation (e.g., containment, method calls, subclassing)

LCOM

Lack of cohesion in methods, the number of methods with pairwise disjoint sets of instance variables referenced within their respective method bodies

All metrics discussed so far focus on code structure and can be measured only when the code is available, often late in the development process. A subset of the object-oriented metrics can be derived from detailed design, which still may be too late for many purposes. Many standards define metrics. The well-known ISO/IEC 9126 standard (sidebar on page 446) suggests a hierarchy of properties to measure the quality of software. The six main high-level quality dimensions identified by the ISO/IEC 9126 standard describe quality properties as perceived by users.

23.5 Test Case Generation and Execution Test case generation and execution can be a large fraction of overall cost for test and analysis, and if done poorly can become a scheduling bottleneck near product delivery deadlines. Although designing a test suite involves human creativity in the same degree as other kinds of design, instantiating and executing test cases is a repetitive and tedious task that can be largely automated, reducing overall cost and accelerating the test cycle. Technical aspects of test case generation and execution are discussed in Chapter 17 and are not repeated here. Strategic aspects of automating test case generation and execution are much as for other quality activities: Essentially mechanical tasks should be factored out and automated, and essentially intellectual and creative tasks should be supported through cognitive aids, bookkeeping support, and communication support.

23.6 Static Analysis and Proof Analysis of specifications and proof of properties span activities from simple checks to full proof of program correctness. Although analysis and proof are often related to formal methods, we can also analyze several aspects of semiformal and informal specifications, if they are precisely defined. For example, we can automatically check important syntactic properties of informal textual and diagrammatic notations. ISO/IEC 9126 Properties The ISO/IEC 9126 standard requires estimation of user-perceived quality on several dimensions. The standard defines only qualitative and subjective measures, but an organization can obtain more useful values by mapping them to objectively measurable criteria. Functionality

Ability to meet explicit and implicit functional requirements

Suitability

Ability to provide functionality required to satisfy user goals

Accuracy

Ability to provide correct results

Interoperability

Ability to interact with other products

Security

Ability to protect access to private data and guarantee a level of service, preventing denial of service

Reliability

Ability to provide the required level of service when the software is used under appropriate conditions

Maturity Fault Tolerance

Ability to avoid failures that result from software faults Ability to maintain a suitable level of functionality even in the presence of external failures

Recoverability

Ability to recover data and resume function after a failure

Usability

Ease of understanding, teaching and using the software

Understandability

Ease of understanding the product

Learnability

Ease of training users

Operability

Ease of working with the product

Attractiveness

Degree of appreciation by users

Efficiency

Ability to guarantee required performance under given conditions

Time Behavior

Ability to satisfy average and maximum response time requirements

Resource

Amount of resources needed for executing the software

Utilization Maintainability

Ability to be updated, corrected, and modified

Analyzability

Ease of analyzing the software to reveal faults

Changeability

Ease of changing the software to remove faults and change existing and add new functionality

Stability

Ability to minimize the effects of changes on normal behavior

Testability

Ease of testing the software

Portability

Ability to be executed in different environments and interoperate with other software

Adaptability

Ability to be adapted to new operating environments

Installability

Ease of installing the software in different environments

Co-existence

Ability to share resources with other products

Replaceability Ability to be replaced by other products Open table as spreadsheet

Automated analysis is effective both for quickly and cheaply checking simple properties, and for more expensive checks that are necessary for critical properties that resist cheaper forms of verification. For example, simple data flow analyses can almost instantaneously identify anomalous patterns (e.g., computing a value that is never used) that are often symptoms of other problems (perhaps using the wrong value at a different point in a program). At the other extreme, using a finite state verification tool to find subtle synchronization faults in interface protocols requires a considerable investment in constructing a model and formalizing the properties to be verified, but this effort is justified by the cost of failure and the inadequacy of conventional testing to find timing-dependent faults. It may be practical to verify some critical properties only if the program to be checked conforms to certain design rules. The problem of verifying critical properties is then decomposed into a design step and a proof step. In the design step, software engineers select and enforce design rules to accommodate analysis, encapsulating critical parts of the code and selecting a well-understood design idiom for which suitable analysis techniques are known. Test designers can then focus on the encapsulated or simplified property. For example, it is common practice to encapsulate safety-critical properties into a safety kernel. In this way, the hard problem of proving the safety-critical properties of a complex system is decomposed into two simpler problems: Prove safety properties of the (small) kernel, and check that all safety-related actions are mediated by the kernel. Tools for verifying a wide class of properties, like program verifiers based on theorem

proving, require extensive human interaction and guidance. Other tools with a more restricted focus, including finite state verification tools, typically execute completely automatically but almost always require several rounds of revision to properly formalize a model and property to be checked. The least burdensome of tools are restricted to checking a fixed set of simple properties, which (being fixed) do not require any additional effort for specification. These featherweight analysis tools include type checkers, data flow analyzers, and checkers of domain specific properties, such as Web site link checkers. Type-checking techniques are typically applied to properties that are syntactic in the sense that they enforce a simple well-formedness rule. Violations are easy to diagnose and repair even if the rules are stricter than one would like. Data flow analyzers, which are more sensitive to program control and data flow, are often used to identify anomalies rather than simple, unambiguous faults. For example, assigning a value to a variable that is not subsequently used suggests that either the wrong variable was set or an intended subsequent use is missing, but the program must be inspected to determine whether the anomaly corresponds to a real fault. Approximation in data flow analysis, resulting from summarization of execution on different control flow paths, can also necessitate interpretation of results. Tools for more sophisticated analysis of programs are, like data flow analyses, ultimately limited by the undecidability of program properties. Some report false alarms in addition to real violations of the properties they check; others avoid false alarms but may also fail to detect all violations. Such “bug finders,” though imperfect, may nonetheless be very costeffective compared to alternatives that require more interaction. Tools that provide strong assurance of important general properties, including model checkers and theorem provers, are much more “heavyweight” with respect to requirement for skilled human interaction and guidance. Finite state verification systems (often called model checkers) can verify conformance between a model of a system and a specified property, but require construction of the model and careful statement of the property. Although the verification tool may execute completely automatically, in practice it is run over and over again between manual revisions of the model and property specification or, in the case of model checkers for programs, revision of the property specification and guidance on program abstraction. Direct verification of software has proved effective, despite this cost, for some critical properties of relatively small programs such as device drivers. Otherwise, finite state verification technology is best applied to specification and design models. The most general (but also the most expensive) static analysis tools execute with interactive guidance. The symbolic execution techniques described in Chapter 7, together with sophisticated constraint solvers, can be used to construct formal proofs that a program satisfies a wide class of formally specified properties. Interactive theorem proving requires specialists with a strong mathematical background to formulate the problem and the property and interactively select proof strategies. The cost of semiautomated formal verification can be justified for a high level algorithm that will be used in many applications, or at a more detailed level to prove a few crucial properties of safety-critical applications.

23.7 Cognitive Aids Quality activities often require examining and understanding complex artifacts, from requirements statements to program code to test execution logs. Information clutter and nonlocality increase the cognitive burden of these tasks, decreasing effectiveness and efficiency. Even inherently manual tasks that depend on human judgment and creativity can be made more effective by cognitive aids that reduce cognitive burden by gathering and presenting relevant information in a task-appropriate manner, with a minimum of irrelevant and distracting details. Information that requires a shift of attention (e.g., following a reference in one file or page to a definition on another) is said to be nonlocal. Nonlocality creates opportunities for human error, which lead to software faults, such as inconsistent uses of data values in a program, or inconsistent use of technical terms in a specification document. Not surprisingly, then, quality tasks often involve gathering and analyzing nonlocal information. Human analysis capability is amplified by bringing relevant information together. For example, where a human may be required to make a judgment about consistent use of technical terms, tools can support that judgment by gathering uses of terms together. Often tools synthesize a global view from scattered local information, as, for example, displaying a call graph extracted from many source code files. Information required for a quality task is often obscured by a mass of distracting irrelevant detail. Tool support for focus and abstraction, delivering and drawing attention to relevant information while suppressing irrelevant detail, improve human effectiveness by reducing clutter and distraction. For example, an inspection tool that displays just the checklist items relevant to a particular inspection task and location in the artifact under inspection increases the efficiency and thoroughness of the human inspector. Similarly, an effective summary report of automated test executions quickly focuses attention on deviations from expected test behavior. Cognitive aids for browsing and visualization are sometimes available as separate tools, but more often their features are embedded in other tools and customized to support particular tasks. Pretty-printing and program slicing,[1] for example, improve code readability and make it easier to identify elements of interest. Diagrammatic representations condense presentation of code properties, providing a summary view of nonlocal information. Diagrammatic and graphical representations are often used to present the results of program analysis, such as data and control flow relations, structural test coverage, distribution of faults and corrections in a program, and source code metrics. Figure 23.1 shows a sample screen shot that visualizes some characteristics of a program. Nodes represent classes and edges inheritance between classes. Node size and background summarize various metrics of the corresponding class. In the diagram of Figure 23.1, width indicates the number of attributes of the class, height indicates the number of methods, and color indicates lines of code, where white represents the smallest classes, black represents the largest, and intermediate sizes are represented by shades of gray. The graphic provides no more information than a table of values, but it facilitates a quicker and fuller grasp of how

those values are distributed.

Figure 23.1: Visualization tools can summarize nonlocal information to facilitate understanding and navigation. The CodeCrawler tool, shown here, uses color, width, and height to represent three static measures of size (number of attributes, number of methods, and lines of code) with connections representing inheritance relations. [1]Program

slicing is an application of static or dynamic dependence analysis (see Chapter 6) to identify portions of a program relevant to the current focus.

23.8 Version Control The quality process can exploit many general development tools not specifically designed for quality activities. Most fundamental among these are version control systems, which record versions and releases of each part of an evolving software system. In addition to maintaining test artifacts (plans, test cases, logs, etc.), the historical information kept in version control systems is useful for tracing faults across versions and collecting data for improving the process. Test cases, scaffolding, and oracles are bound to the code: Changes in the code may result in incompatibilities with scaffolding and oracles, and test cases may not exercise new relevant behaviors. Thus, test suites must evolve with code. Test designers use version control systems to coordinate evolution of test artifacts with associated program artifacts. In addition to test and program artifacts, the status and history of faults is essential to project management, and many version control systems include functionality for supporting fault tracking.

23.9 Debugging Detecting the presence of software faults is logically distinct from the subsequent tasks of locating, diagnosing, and repairing faults. Testing is concerned with fault detection, while locating and diagnosing faults fall under the rubric of debugging. Responsibility for testing and debugging typically fall to different individuals. Nonetheless, since the beginning point for debugging is often a set of test cases, their relation is important, and good test automation derives as much value as possible for debugging. A small, simple test case that invariably fails is far more valuable in debugging than a complex scenario, particularly one that may fail or succeed depending on unspecified conditions. This is one reason test case generators usually produce larger suites of singlepurpose test cases rather than a smaller number of more comprehensive test cases. Typical run-time debugging tools allow inspection of program state and controls to pause execution at selected points (breakpoints), or when certain conditions occur (watchpoints), or after a fixed number of execution steps. Modern debugging tools almost always provide display and control at the level of program source code, although compiler transformations of object code cannot always be hidden (e.g., order of execution may differ from the order of source code). Specialized debugging support may include visualization (e.g., of thread and process interactions) and animation of data structures; some environments permit a running program to be paused, modified, and continued. When failures are encountered in stress testing or operational use, the “test case” is likely to be an unwieldy scenario with many irrelevant details, and possibly without enough information to reliably trigger failure. Sometimes the scenario can be automatically reduced to a smaller test case. A test data reduction tool executes many variations on a test case, omitting portions of the input for each trial, in order to discover which parts contain the core information that triggers failure. The technique is not universally applicable, and meaningful subdivisions of input data may be application-specific, but it is an invaluable aid to dealing with large data sets. While the purpose of test data reduction is to aid debugging, it may also produce a useful regression test case to guard against reintroduction of the same program fault. Not only the test case or cases that trigger failure but also those that execute correctly are valuable. Differential debugging compares a set of failing executions to other executions that do not fail, focusing attention on parts of the program that are always or often executed on failures and less often executed when the program completes successfully. Variations on this approach include varying portions of a program (to determine which of several recent changes is at fault), varying thread schedules (to isolate which context switch triggers a fatal race condition), and even modifying program data state during execution.

23.10 Choosing and Integrating Tools Automation is a key lever for reducing cost and improving the effectiveness of test and analysis, but only if tools and approaches are a good fit with the development organization, process, application domain, and suitable test and analysis techniques. A large software development organization in which a single software project is spread across several teams and functional areas has foremost a requirement for coordination and communication. We would typically expect to see process management and version and configuration control in a central role, with automation of other activities from programming to inspection to system testing arranged to fit smoothly into it. A large organization can typically afford to establish and maintain such a system, as well as to orient new employees to it. A smaller organization, or one divided into autonomous groups along project rather than functional lines, still benefits from integration of test and analysis tools with process management, but can afford to place a higher priority on other aspects of test and analysis automation. A simple and obvious rule for automating test and analysis activities is to select tools that improve the efficiency of tasks that are significant costs (in money or schedule) for the organization and projects in question. For example, automated module testing is of little use for an organization using the Cleanroom process, but is likely to be important to an organization using XP. An organization building safety-critical software can justify investment (including training) in sophisticated tools for verifying the properties of specifications and design, but an organization that builds rapidly evolving mass market applications is more likely to benefit from good support for automated regression testing. While automating what one is already doing manually is easiest to justify, one should not fail to consider activities that are simply impossible without automation. For example, if static source code analysis can efficiently detect a class of software faults that requires considerable testing effort, then acquiring or constructing tools to perform that analysis may be more cost-effective than automation to make the testing effort more efficient. Investments in automation must be evaluated in a scope that extends beyond a single project and beyond the quality team. The advantage of reusing common tools across projects is savings not only in the cost of acquiring and installing tools, but also in the cost of learning to use them effectively and the consequent impact on project schedule. A continuing benefit for a one-time or declining investment becomes more attractive when tool use is considered over the longer term. Often a quality tool will have costs and benefits for other parts of the software organization (e.g., in the quality of diagnostic information produced), and the most successful tool adoptions are those that produce visible benefits for all parties. Consider, for example, adoption of tools for recording and tracking faults. Tracking reported failures from the field and from system testing is easy to justify in most organizations, as it has immediate visible benefits for everyone who must deal with failure reports. Collecting additional information to enable fault classification and process improvement has at least equal benefits in the long term, but is more challenging because the payoff is not immediate.

Open Research Issues Tools and automation are likely to remain an important part of research in all subareas of software analysis and test, particularly but not only for techniques that are essentially impossible to carry out manually. Where manual effort is central, as, for example, in software inspection or project planning, automation is equally important but depends more critically on fitting into the overall process and project context and human factors. For example, with version and configuration control systems playing a central role in team coordination and communication, we can expect to see innovations in the way test and analysis tasks exploit and are integrated with versioning repositories. Nearly universal network connectivity has enabled a related trend, expanding the iterative cycle of software development and evolution beyond deployment. Regularly scheduled software field updates and automated transmission of crash logs and bug reports to developers is already commonplace for so-called desktop computers and seems inevitable for the growing tide of embedded systems. Research in software test and analysis is just beginning to address the kinds of automation this expansion enables and, in some cases, necessitates, such as rapid classification of error and crash logs. A natural extension into more sophisticated self-monitoring, diagnosis, and automatic adaptation in deployed software is sometimes included under the rubric of self-managed computing. The current generation of integrated development environments is an architectural improvement of over its predecessors, particularly in provision of plug-in frameworks for tools. Nevertheless the distance from devising a useful technique to fielding a useful and well-integrated tool, particularly one with rich visualization capabilities, remains large. There is still a good deal of room for progress in approaches and techniques for quickly generating and integrating tools.

Further Reading Surveys of currently available tools are available commercially, and reviews of many tools can be found in trade magazines and books. Since tools are constantly evolving, the research literature and other archival publications are less useful for determining what is immediately available. The research literature is more useful for understanding basic problems and approaches in automation to guide the development and use of tools. Zeller [Zel05] is a good modern reference on program debugging, with an emphasis on recent advances in automated debugging. A series of books by Tufte [Tuf01, Tuf97, Tuf90, Tuf06] are useful reading for anyone designing informationdense displays, and Nielsen [Nie00] is an introduction to usability that, though specialized to Web applications, describes more generally useful principles. Norman [Nor90] is an excellent and entertaining introduction to fundamental principles of usability that apply to software tools as well as many other designed artifacts. The example in Figure 23.1 is taken from Lanza and Ducasse [LD03], who describe a simple and adaptable approach to depicting program attributes using multiple graphical dimensions.

Related Topics Chapter 19 describes program analysis tools in more detail.

Exercises Appropriate choice of tools may vary between projects depending, among other factors, on application domain, development language(s), and project size. Describe possible differences in A&T tool choices for the following: Program analysis tools for a project with Java as the only development language, and for another project with major components in Java, SQL, and Python, and a variety of other scripting and special-purpose languages in other roles. 23.1

23.2

23.3

Planning and monitoring tools for a three-month, three-person project in which all but acceptance testing is designed and carried out by developers, and for a two-year project carried out by a seven-person team including two full-time testers. A testing framework for an information system that archives international weather data, and for a weather forecasting system based on computer simulation. Consider the following design rule: All user text (prompts, error messages, et al.) are made indirectly through tables, so that a table of messages in another language can be substituted at run-time. How would you go about partly or wholly automating a check of this property? Suppose two kinds of fault are equally common and equally costly, but one is local (entirely within a module) and the other is inherently nonlocal (e.g., it could involve incompatibility between modules). If your project budget is enough to automate detection of either the local or the nonlocal property, but not both, which will you automate? Why?

Chapter 24: Documenting Analysis and Test Mature software processes include documentation standards for all the activities of the software process, including test and analysis activities. Documentation can be inspected to verify progress against schedule and quality goals and to identify problems, supporting process visibility, monitoring, and replicability.

Required Background Chapter 20 This chapter describes test and analysis strategy and plans, which are intertwined with documentation. Plans and strategy documents are part of quality documentation, and quality documents are used in process monitoring.

24.1 Overview Documentation is an important element of the software development process, including the quality process. Complete and well-structured documents increase the reusability of test suites within and across projects. Documents are essential for maintaining a body of knowledge that can be reused across projects. Consistent documents provide a basis for monitoring and assessing the process, both internally and for external authorities where certification is desired. Finally, documentation includes summarizing and presenting data that forms the basis for process improvement. Test and analysis documentation includes summary documents designed primarily for human comprehension and details accessible to the human reviewer but designed primarily for automated analysis. Documents are divided into three main categories: planning, specification, and reporting. Planning documents describe the organization of the quality process and include strategies and plans for the division or the company, and plans for individual projects. Specification documents describe test suites and test cases. A complete set of analysis and test specification documents include test design specifications, test case specification, checklists, and analysis procedure specifications. Reporting documents include details and summary of analysis and test results.

24.2 Organizing Documents In a small project with a sufficiently small set of documents, the arrangement of other project artifacts (e.g., requirements and design documents) together with standard content (e.g., mapping of subsystem test suites to the build schedule) provides sufficient organization to navigate through the collection of test and analysis documentation. In larger projects, it is common practice to produce and regularly update a global guide for navigating among individual documents. Mature processes require all documents to contain metadata that facilitate their management. Documents must include some basic information about its context in order to make the document self-contained, approval indicating the persons responsible for the document and document history, as illustrated in the template on page 457. Naming conventions help in quickly identifying documents. A typical standard for document names would include keywords indicating the general scope of the document, its nature, the specific document, and its version, as in Figure 24.1.

Figure 24.1: Sample document naming conventions, compliant with IEEE standards. Chipmunk Document Template Document Title Approvals issued by

name

signature

date

approved by

name

signature

date

distribution status

(internal use only, restricted, …)

(people to whom the document must be sent) Open table as spreadsheet

distribution list

History version

description

Open table as spreadsheet Table of Contents List of sections. Summary Summarize the contents of the document. The summary should clearly explain the relevance of the document to its possible uses. Goals of the document Describe the purpose of this document: Who should read it, and why? Required documents and references Provide a reference to other documents and artifacts needed for understanding and exploiting this document. Provide a rationale for the provided references. Glossary Provide a glossary of terms required to understand this document. Section 1 … Section N …

24.3 Test Strategy Document Analysis and test strategies (Chapter 20) describe quality guidelines for sets of projects, usually for an entire company or organization. Strategies, and therefore strategy documents, vary widely among organizations, but we can identify a few key elements that should be included in almost any well-designed strategy document. These are illustrated in the document excerpt on page 459. Strategy documents indicate common quality requirements across products. Requirements may depend on business conditions. For example, a company that produces safety-critical software may need to satisfy minimum dependability requirements defined by a certification authority, while a department that designs software embedded in hardware products may need to ensure portability across product lines. Some requirements on dependability and usability may be necessary to maintain brand image and market position. For example, a company might decide to require conformance to W3C-WAI accessibility standards (see Chapter 22) uniformly across the product line. The strategy document sets out requirements on other quality documents, typically including an analysis and test plan, test design specifications, test case specifications, test logs, and test summary reports. Basic document requirements, such as naming and versioning, follow standards for other project documentation, but quality documents may have additional, specialized requirements. For example, testing logs for avionics software may be required to contain references to the version of the simulator used for executing the test before installing the software on board the aircraft.

24.4 Analysis and Test Plan While the format of an analysis and test strategy vary from company to company, the structure of an analysis and test plan is more standardized. A typical structure of a test and analysis plan includes information about items to be verified, features to be tested, the testing approach, pass and fail criteria, test deliverables, tasks, responsibilities and resources, and environment constraints. Basic elements are described in the sidebar on page 461. The overall quality plan usually comprises several individual plans of limited scope. Each test and analysis plan should indicate the items to be verified through analysis or testing. They may include specifications or documents to be inspected, code to be analyzed or tested, and interface specifications to undergo consistency analysis. They may refer to the whole system or part of it – like a subsystem or a set of units. Where the project plan includes planned development increments, the analysis and test plan indicates the applicable versions of items to be verified. For each item, the plan should indicate any special hardware or external software required for testing. For example, the plan might indicate that one suite of subsystem tests for a security package can be executed with a software simulation of a smart card reader, while another suite requires access to the physical device. Finally, for each item, the plan should reference related documentation, such as requirements and design specifications, and user, installation, and operations guides. An Excerpt of the Chipmunk Analysis and Test Strategy Document CP05-14.03: Analysis and Test Strategy … Applicable Standards and Procedures Artifact

Applicable Standards and Guidelines

Web application

Accessibility: W3C-WAI …

Reusable component (internally developed)

Inspection procedure: [WB12-03.12] Qualification procedure: [WB1222.04]

External component Open table as spreadsheet …

Documentation Standards Project documents must be archived according to the standard Chipmunk archive procedure [WB02-01.02]. Standard required documents include Document

Content & Organization Standard

Quality plan

[WB06-01.03]

Test design specifications

[WB07-01.01] (per test suite)

Test case specifications

[WB08-01.07] (per test suite)

Test logs

[WB10-02.13]

Test summary reports

[WB11-01.11]

Inspection reports Open table as spreadsheet

[WB12-09.01]

… Analysis and Test Activities … Tools The following tools are approved and should be used in all development projects. Exceptions require configuration committee approval and must be documented in the project plan. Fault logging

Chipmunk BgT [WB10-23.01]

… Open table as spreadsheet … Staff and Roles A development work unit consists of unit source code, including unit test cases, stubs, and harnesses, and unit test documentation. A unit may be committed to the project baseline when the source code, test cases, and test results have passed peer review. … References [WB02-01.02] Archive Procedure [WB07-01.01] Test Design Specifications Guidelines [WB11-01.11] Summary Reports Template [WB11-09.01] Inspection Report Template [WB12-22.04] Quality Procedures for Software Developed by Third Parties

[WB06-01.03] Quality Plan Guidelines [WB08-01.07] Test Case Specifications Guidelines [WB10-02.13] Test Log Template [WB12-03.12] Standard Inspection Procedures [WB12-23.01] BgT Installation Manual and User Guide

Open table as spreadsheet … A test and analysis plan may not address all aspects of software quality and testing activities. It should indicate the features to be verified and those that are excluded from consideration (usually because responsibility for them is placed elsewhere). For example, if the item to be verified includes a graphical user interface, the test and analysis plan might state that it deals only with functional properties and not with usability, which is to be verified separately by a usability and human interface design team. Explicit indication of features not to be tested, as well as those included in an analysis and test plan, is important for assessing completeness of the overall set of analysis and test activities. Assumption that a feature not considered in the current plan is covered at another point is a major cause of missing verification in large projects. The quality plan must clearly indicate criteria for deciding the success or failure of each planned activity, as well as the conditions for suspending and resuming analysis and test. Plans define items and documents that must be produced during verification. Test deliverables are particularly important for regression testing, certification, and process improvement. We will see the details of analysis and test documentation in the next section. The core of an analysis and test plan is a detailed schedule of tasks. The schedule is usually illustrated with GANTT and PERT diagrams showing the relation among tasks as well as their relation to other project milestones.[1] The schedule includes the allocation of limited resources (particularly staff) and indicates responsibility for reresources and responsibilities sults. A quality plan document should also include an explicit risk plan with contingencies. As far as possible, contingencies should include unambiguous triggers (e.g., a date on which a contingency is activated if a particular task has not be completed) as well as recovery procedures. Finally, the test and analysis plan should indicate scaffolding, oracles, and any other software or hardware support required for test and analysis activities. [1]Project scheduling is discussed in more detail in Chapter 20.

24.5 Test Design Specification Documents Design documentation for test suites and test cases serve essentially the same purpose as other software design documentation, guiding further development and preparing for maintenance. Test suite design must include all the information needed for initial selection of test cases and maintenance of the test suite over time, including rationale and anticipated evolution. Specification of individual test cases includes purpose, usage, and anticipated changes. A Standard Organization of an Analysis and Test Plan Analysis and test items: The items to be tested or analyzed. The description of each item indicates version and installation procedures that may be required. Features to be tested: The features considered in the plan. Features not to be tested: Features not considered in the current plan. Approach: The overall analysis and test approach, sufficiently detailed to permit identification of the major test and analysis tasks and estimation of time and resources. Pass/Fail criteria: Rules that determine the status of an artifact subjected to analysis and test. Suspension and resumption criteria: Conditions to trigger suspension of test and analysis activities (e.g., an excessive failure rate) and conditions for restarting or resuming an activity. Risks and contingencies: Risks foreseen when designing the plan and a contingency plan for each of the identified risks. Deliverables: A list all A&T artifacts and documents that must be produced. Task and schedule: A complete description of analysis and test tasks, relations among them, and relations between A&T and development tasks, with resource allocation and constraints. A task schedule usually includes GANTT and PERT diagrams.

Staff and responsibilities: Staff required for performing analysis and test activities, the required skills, and the allocation of responsibilities among groups and individuals. Allocation of resources to tasks is described in the schedule. Environmental needs: Hardware and software required to perform analysis or testing activities.

Test design specification documents describe complete test suites (i.e., sets of test cases that focus on particular aspects, elements, or phases of a software project). They may be divided into unit, integration, system, and acceptance test suites, if we organize them by the granularity of the tests, or functional, structural, and performance test suites, if the primary organization is based on test objectives. A large project may include many test design specifications for test suites of different kinds and granularity, and for different versions or configurations of the system and its components. Each specification should be uniquely identified and related to corresponding project documents, as illustrated in the sidebar on page 463. Test design specifications identify the features they are intended to verify and the approach used to select test cases. Features to be tested should be cross-referenced to relevant parts of a software specification or design document. The test case selection approach will typically be one of the test selection techniques described in Chapters 10 through 16 with documentation on how the technique has been applied. A test design specification also includes description of the testing procedure and pass/fail criteria. The procedure indicates steps required to set up the testing environment and perform the tests, and includes references to scaffolding and oracles. Pass/fail criteria distinguish success from failure of a test suite as a whole. In the simplest case a test suite execution may be determined to have failed if any individual test case execution fails, but in system and acceptance testing it is common to set a tolerance level that may depend on the number and severity of failures. A test design specification logically includes a list of test cases. Test case specifications may be physically included in the test design specification document, or the logical inclusion may be implemented by some form of automated navigation. For example, a navigational index can be constructed from references in test case specifications. Individual test case specifications elaborate the test design for each individual test case, defining test inputs, required environmental conditions and procedures for test execution, as well as expected outputs or behavior. The environmental conditions may include hardware and software as well as any other requirements. For example, while most tests should be executed automatically without human interaction, intervention of personnel with certain special skills (e.g., a device operator) may be an environmental requirement for some.

A test case specification indicates the item to be tested, such as a particular module or product feature. It includes a reference to the corresponding test design document and describes any dependence on execution of other test cases. Like any standard document, a test case specification is labeled with a unique identifier. A sample test case specification is provided on page 464.

24.6 Test and Analysis Reports Reports of test and analysis results serve both developers and test designers. They identify open faults for developers and aid in scheduling fixes and revisions. They help test designers assess and refine their approach, for example, noting when some class of faults is escaping early test and analysis and showing up only in subsystem and system testing (see Section 20.6, page 389). Functional Test Design Specification of check configuration Test Suite Identifier WB07-15.01 Features to Be Tested Functional test for check configuration, module specification WB02-15.32.[a] Approach Combinatorial functional test of feature parameters, enumerated by category-partition method over parameter table on page 3 of this document.[b] Procedure Designed for conditional inclusion in nightly test run. Build target T02 15 32 11 includes JUnit harness and oracles, with test reports directed to standard test log. Test environment includes table MDB 15 32 03 for loading initial test database state. Test cases[c] WB0715.01.C01

malformed model number

WB0715.01.C02

model number not in DB

…

WB0715.01.C09[d]

valid model number with all legal required slots and some legal optional slots

…

WB0715.01.C19

empty model DB

WB0715.01.C23

model DB with a single element

WB0715.01.C24

empty component DB

WB0715.01.C29 [d]See

component DB with a single element

sample test case specification, page 464.

Open table as spreadsheet Pass/Fail Criterion Successful completion requires correct execution of all test cases with no violations in test log.

Test Case Specification for check configuration Test Case Identifier WB07-15.01.C09[a] Test items Module check configuration of the Chipmunk Web presence system, business logic subsystem. Input specification Test Case Specification: Model No.

valid

No. of required slots for selected model (#SMRS)

many

No. of optional slots for selected model (#SMOS)

many

Correspondence of selection with model slots

complete

No. of required components with selection ≠ empty

= No. of required slots

No. of optional components with select ≠ empty

Required component selection

all valid

Optional component selection

all valid

No. of models in DB

many

No. of components in Open table as spreadsheet

DB many

Test case: Model number

Chipmunk C20

#SMRS

Screen

13″

Processor

Chipmunk II plus

Hard disk

30 GB

RAM

512 MB

RodentOS 3.2 Personal Edition

#SMOS

External storage DVD player device Open table as spreadsheet Output Specification return value valid Environment Needs Execute with ChipmunkDBM v3.4 database initialized from table MDB 15 32 03. Special Procedural Requirements none Intercase Dependencies none

A prioritized list of open faults is the core of an effective fault handling and repair procedure. Failure reports must be consolidated and categorized so that repair effort can be managed systematically, rather than jumping erratically from problem to problem and wasting time on duplicate reports. They must be prioritized so that effort is not squandered on faults of relatively minor importance while critical faults are neglected or even forgotten. Other reports should be crafted to suit the particular needs of an organization and project, including process improvement as described in Chapter 23. Summary reports serve primarily to track progress and status. They may be as simple as confirmation that the nightly build-and-test cycle ran successfully with no new failures, or they may provide somewhat more information to guide attention to potential trouble spots. Detailed test logs are designed for selective reading, and include summary tables that typically include the test suites executed, the number of failures, and a breakdown of failures into those repeated from prior test execution, new failures, and test cases that previously failed but now execute correctly. In some domains, such as medicine or avionics, the content and form of test logs may be prescribed by a certifying authority. For example, some certifications require test execution logs signed by both the person who performed the test and a quality inspector, who ascertains conformance of the test execution with test specifications.

Open Research Issues Many available tools generate documentation from test execution records and the tables used to generate test specifications, minimizing the extra effort of producing documents in a useful form. Test design derived automatically or semiautomatically from design models is growing in importance, as is close linking of program documentation with source code, ranging from simple comment extraction and indexing like Javadoc to sophisticated hypermedia systems. In the future we should see these trends converge, and expect to see test documentation fit in an overall framework for managing and navigating information on a software product and project.

Further Reading The guidelines in this chapter are based partly on IEEE Standard 829-1998 [Ins98]. Summary reports must convey information efficiently, managing both overview and access to details. Tufte’s books on information design are useful sources of principles and examples. The second [Tuf90] and fourth [Tuf06] volumes in the series are particularly relevant. Experimental hypermedia software documentation systems [ATWJ00] hint at possible future systems that incorporate test documentation with other views of an evolving software product.

Exercises

24.1

24.2

Agile software development methods (XP, Scrum, etc.) typically minimize documentation written during software development. Referring to the sidebar on page 381, identify standard analysis and test documents that could be generated automatically or semiautomatically or replaced with functionally equivalent, automatically generated documentation during an XP project. Test documents may become very large and unwieldy. Sometimes a more compact specification of several test cases together is more useful than individual specifications of each test case. Referring to the test case specification on page 464, design a tabular form to compactly document a suite of similar test case specifications.

24.3

Design a checklist for inspecting test design specification documents.

24.4

The Chipmunk Web presence project is starting up, and it has been decided that all project artifacts, including requirements documents, documentation in English, Italian, French, and German, source code, test plans, and test suites, will be managed in one or more CVS repositories.[2] The project team is divided between Milan, Italy, and Eugene, Oregon. What are the main design choices and issues you will consider in designing the organization of the version control repositories?

[a]An

excerpt of specification WB02-15.32 is presented in Figure 11.1, page 182.

[b]Reproduced

in Table 11.1, page 187.

[c]The

detailed list of test cases is produced automatically from the test case file, which in turn is generated from the specification of categories and partitions. The test suite is implicitly referenced by individual test case numbers (e.g., WB07-15.01.C09 is a test case in test suite WB07-15.01). [a]The

prefix WB07-15.01 implicitly references a test suite to which this test case directly belongs. That test suite may itself be a component of higher level test suites, so logically the test case also belongs to any of those test suites. Furthermore, some additional test suites may be composed of selections from other test suites. [2]If

you are more familiar with another version control system, such as Subversion or Perforce, you may substitute it for CVS.

Bibliography [ABC82] Richards W. Adrion, Martha A. Branstad, and John C. Cherniavsky. Validation, verification, and testing of computer software. ACM Computing Surveys, 14(2):159–192, June 1982. [ASU86] Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley Longman, Boston, 1986. [ATWJ00] Kenneth M. Anderson, Richard N. Taylor, and E. James Whitehead Jr. Chimera: Hypermedia for heterogeneous software development environments. ACM Transactions on Information Systems, 18(3):211–245, July 2000. [Bar01] Carol M. Barnum. Usability Testing and Research. Allyn & Bacon, Needham Heights, MA, 2001. [Bei95] Boris Beizer. Black-Box Testing: Techniques for Functional Testing of Software and Systems. John Wiley and Sons, New York, 1995. [BGM91] Gilles Bernot, Marie Claude Gaudel, and Bruno Marre. Software testing based on formal specifications: A theory and a tool. Software Engineering Journal, 6(6):387–405, November 1991. [BHC+94] Inderpal Bhandari, Michael J. Halliday, Jarir Chaar, Kevin Jones, Janette S. Atkinson, Clotilde Lepori-Costello, Pamela Y. Jasper, Eric D. Tarver, Cecilia Carranza Lewis, and Masato Yonezawa. In-process improvement through defect data interpretation. IBM Systems Journal, 33(1):182–214, 1994. [BHG87] Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman. Concurrency Control and Recovery in Database Systems. Addison-Wesley, Boston, 1987. [Bin00] Robert V. Binder. Testing Object-Oriented Systems, Models, Patterns, and Tools. Addison-Wesley, Boston, 2000. [Bis02] Matt Bishop. Computer Security: Art and Science. Addison-Wesley Professional, Boston, 2002. [Boe81] Barry W. Boehm. Software Engineering Economics. Prentice Hall, Englewood Cliffs, NJ, 1981. [BOP00] Ugo Buy, Alessandro Orso, and Mauro Pezzé. Automated testing of classes. In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA), pages 39–48, Portland, OR, 2000. [BPS00] William R. Bush, Jonathan D. Pincus, and David J. Sielaff. A static analyzer for finding dynamic programming errors. Software: Practice & Experience, 30:775– 802, 2000.

[BR01a] Thomas Ball and Sriram K. Rajamani. Automatically validating temporal safety properties of interfaces. In SPIN ’01: Proceedings of the 8th International SPIN Workshop on Model Checking of Software, pages 103–122, Toronto, Ontario, Canada, 2001. Springer-Verlag. [BR01b] Thomas Ball, and Sriram K. Rajamani. Bebop: a path-sensitive interprocedural dataflow engine. In PASTE ’01: Proceedings of the 2001 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, pages 97–103, Snowbird, UT, 2001. [Bry86] Randal E. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers, 35(8):677–691, 1986. [Bry92] Randal E. Bryant. Symbolic boolean manipulation with ordered binarydecision diagrams. ACM Computing Surveys, 24(3):293–318, 1992. [BSW69] K. A. Bartlett, R. A. Scantlebury, and P. T. Wilkinson. A note on reliable fullduplex transmission over half-duplex lines. Communications of the ACM, 12(5):260– 261, May 1969. [CBC+92] Ram Chillarege, Inderpal S. Bhandari, Jarir K. Chaar, Michael J. Halliday, Diane S. Moebus, Bonnie K. Ray, and Man-Yuen Wong. Orthogonal defect classification-A concept for in-process measurements. IEEE Transactions on Software Engineering, 18(11):943–956, 1992. [CC77] Patrick Cousot and Radhia Cousot. Abstract interpretation: A unified lattice model for static analysis of programs by construction of approximation of fixpoints. In ACM Symposium on Principles of Programming Languages, pages 238–252, Los Angeles, CA, January 1977. [CCD+80] Augusto Celentano, Stefano Crespi Reghizzi, Pier Luigi Della Vigna, Carlo Ghezzi, G. Granata, and F. Savoretti. Compiler testing using a sentence generator. Software – Practice & Experience, 10:897–918, 1980. [CDFP97] David M. Cohen, Siddhartha R. Dalal, Michael L. Fredman, and Gardner C. Patton. The AETG system: An approach to testing based on combinatiorial design. IEEE Transactions on Software Engineering, 23(7):437–444, July 1997. [CHBC93] Jarir Chaar, Michael J. Halliday, Inderpal S. Bhandari, and Ram Chillarege. In-process evaluation for software inspection and test. IEEE Transactions on Software Engineering, 19(11):1055–1070, November 1993. [Cla76] Lori A. Clarke. A system to generate test data and symbolically execute programs. IEEE Transactions on Software Engineering, SE-2(3):215–222, September 1976. [CPDGP01] Alberto Coen—Porisini, Giovanni Denaro, Carlo Ghezzi, and Mauro

Pezzèe. Using symbolic execution for verifying safety-critical systems. In Proceedings of the 8th European Software Engineering Conference held jointly with the 9th ACM SIGSOFT International Symposium on Foundations of Software Engineering (ESEC/FSE-9), pages 142–151, Vienna, Austria, 2001. [CPRZ89] Lori Clarke, Andy Podgurski, Debra Richardson, and Steven J. Zeil. A formal evaluation of data flow path selection criteria. IEEE Transactions on Software Engineering, 15(11):1318–1332, 1989. [DCCN04] Matthew B. Dwyer, Lori A. Clarke, Jamieson M. Cobleigh, and Gleb Naumovich. Flow analysis for verifying properties of concurrent software systems. ACM Transactions on Software Engineering and Methodologies, 13(4):359–430, 2004. [DF94] Roong-Ko Doong and Phyllis G. Frankl. The ASTOOT approach to testing object-oriented programs. ACM Transactions on Software Engineering and Methodology, 3(2):101–130, April 1994. [DGK+88] Richard A. DeMillo, D.S. Guindi, Kim King, Mike M. McCracken, and A. Jefferson Offut. An extended overview of the Mothra software testing environment. In Proceedings of the 2nd Workshop on Software Testing, Verification, and Analysis (TAV), Banff, Alberta, 1988. [Dij72] Edsgar W. Dijkstra. Notes on structured programming. In O. J. Dahl, E. W. Dijkstra, and C. A. R. Hoare, editors, Structured Programming. Academic Press, London, 1972. [DL99] Tom DeMarco and Timothy Lister. Peopleware (2nd ed.): Productive Projects and Teams. Dorset House, New York, 1999. [DLS78] Richard A. DeMillo, Richard J. Lipton, and Frederick G. Sayward. Hints on test data selection: Help for the practicing programmer. IEEE Computer, 11(4):34– 41, 1978. [DN81] Joe W. Duran and Simeon Ntafos. A report on random testing. In ICSE ’81: Proceedings of the 5th International Conference on Software Engineering, pages 179–183, San Diego, CA, 1981. [DP02] Giovanni Denaro, and Mauro Pezzè;. An empirical evaluation of faultproneness models. In Proceedings of the 24th International Conference on Software Engineering (ICSE), pages 241–251, Orlando, Florida, 2002. [DRW03] Alastair Dunsmore, Marc Roper, and Murray Wood. The development and evaluation of three diverse techniques for object-oriented code inspection. IEEE Transactions on Software Engineering, 29(8):677–686, 2003. [ECGN01] Michael D. Ernst, Jake Cockrell, William G. Griswold, and David Notkin.

Dynamically discovering likely program invariants to support program evolution. IEEE Transactions on Software Engineering, 27(2):99–123, February 2001. [Fag86] Michal E. Fagan. Advances in software inspections. IEEE Transactions on Software Engineering, 12(7):744–751, 1986. [FHLS98] Phyllis Frankl, Richard Hamlet, Bev Littlewood, and Lorenzo Strigini. Evaluating Testing methods by Delivered Reliability. IEEE Transactions on Software Engineering, 24(8):586–601, 1998. [FI98] Phyllis G. Frankl and Oleg Iakounenko. Further empirical studies of test effectiveness. In Proceedings of the ACM SIGSOFT 6th International Symposium on the Foundations of Software Engineering (FSE), volume 23, 6 of Software Engineering Notes, pages 153–162, New York, November 3–5 1998. ACM Press. [Flo67] Robert W. Floyd. Assigning meanings to programs. In Proceedings of the Symposium on Applied Mathematics, volume 19, pages 19–32, Providence, RI, 1967. American Mathematical Society. [FO76] Lloyd D. Fosdick, and Leon J. Osterweil. Data flow analysis in software reliability. ACM Computing Surveys, 8(3):305–330, 1976. [FvBK+91] Susumu Fujiwara, Gregor von Bochmann, Ferhat Khendek, Mokhtar Amalou, and Abderrazak Ghedamsi. Test selection based on finite state models. IEEE Transactions on Software Engineering, 17(6):591–603, June 1991. [FW93] Phyllis G. Frankl, and Elaine G. Weyuker. Provable improvements on branch testing. IEEE Transactions on Software Engineering, 19(10):962–975, October 1993. [GG75] John B. Goodenough, and Susan L. Gerhart. Toward a theory of test data selection. IEEE Transactions on Software Engineering, 1(2):156–173, 1975. [GG93] Tom Gilb, and Dorothy Graham. Software Inspection. Addison-Wesley Longman, Boston, 1993. [GH99] Angelo Gargantini and Connie Heitmeyer. Using model checking to generate tests from requirements specifications. In Proceedings of the 7th European Software Engineering Conference held jointly with the 7th ACM SIGSOFT Symposium on Foundations of Software Engineering (ESEC/FSE), pages 146–162, Toulouse, France, September 6–10 1999. [GHK+98] Todd Graves, Mary Jean Harrold, Jung-Min Kim, Adam Porter, and Gregg Rothermel. An empirical study of regression test selection techniques. In Proceedings of the 20th International Conference on Software Engineering (ICSE), pages 188–197. IEEE Computer Society Press, April 1998. [GJM02] Carlo Gezzi, Mehdi Jazayeri, and Dino Mandrioli. Fundamentals of Software

Engineering. Prentice Hall PTR, Upper Saddle River, NJ, 2nd edition, 2002. [GMH81] John Gannon, Paul McMullin, and Richard Hamlet. Data abstraction, implementation, specification, and testing. ACM Transactions on Programming Languages and Systems, 3(3):211–223, 1981. [Gou83] John S. Gourlay. A mathematical framework for the investigation of testing. IEEE Transactions on Software Engineering, 6(11):086–709, November 1983. [GS94] Robert B. Grady and Tom Van Slack. Key lessons in achieving widespread inspection use. IEEE Software, 11(4):46–57, 1994. [Gut77] John Guttag. Abstract data types and the development of data structures. Communications of the ACM, 20(6):396–404, 1977. [HA05] Hanna Hulkko and Pekka Abrahamsson. A multiple case study on the impact of pair programming on product quality. In Proceedings of the 27th International Conference on Software Engineering (ICSE), pages 495–504, St. Louis, MO, 2005. [Ham77] Richard G. Hamlet. Testing programs with the aid of a compiler. IEEE Transactions on Software Engineering, 3(4):279–290, July 1977. [Han70] Kenneth V. Hanford. Automatic generation of test cases. IBM Systems Journal, 4:242–257, 1970. [HDW04] Mats P.E. Heimdahl, George Devaraj, and Robert J. Weber. Specification test coverage adequacy criteria = specification test generation inadequacy criteria? In Proceedings of the Eighth IEEE International Symposium on High Assurance Systems Engineering (HASE), pages 178–186, Tampa, Florida, March 2004. [Her76] P. Herman. A data flow analysis approach to program testing. The Australian Computer Journal, November 1976. [Hin01] Michael Hind. Pointer analysis: haven’t we solved this problem yet? In Proceedings of the ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, pages 54–61, Snowbird, UT, 2001. [HJ92] Reed Hastings and Bob Joyce. Purify: Fast detection of memory leaks and access errors. In Proceedings of the Winter USENIX Conference, pages 125–136. USENIX Association, January 1992. [HJMS03] Thomas A. Henzinger, Ranjit Jhala, Rupak Majumdar, and Gregoire Sutre. Software verification with blast. In Proceedings of the Tenth International Workshop on Model Checking of Software (SPIN), volume 2648 of Lecture Notes in Computer Science, pages 235–239. Springer-Verlag, 2003. [HK76] Sidney L. Hantler and James C. King. An introduction to proving the

correctness of programs. ACM Computing Surveys, 8(3):331–353, 1976. [HM03] Ted Husted and Vincent Massol. JUnit in Action. Manning Publications, Greenwich, CT, 2003. [HMF92] Mary Jean Harrold, John D. McGregor, and Kevin J. Fitzpatrick. Incremental Testing of Object-Oriented Class Structures. In Proceedings of the 14th International Conference on Software Engineering, pages 68–80, Melbourne, Australia, May 1992. [Hoa69] C. A. R. Hoare. An axiomatic basis for computer programming. Communications of the ACM, 12(10):576–580, 1969. [Hol97] Gerard J. Holzmann. The model checker SPIN. IEEE Transactions on Software Engineering, 23(5):279–295, 1997. [Hol03] Gerard J. Holzmann. The SPIN Model Checker: Primer and Reference Manual. Addison-Wesley Professional, Boston, 2003. [How75] William E. Howden. Methodology for the generation of program test data. IEEE Transactions on Computers, 24(5):554–560, May 1975. [How76] William E. Howden. Reliability of the path analysis testing strategy. IEEE Transactions on Software Engineering, 2(3):208–215, 1976. [How77] William E. Howden. Symbolic testing and the DISSECT symbolic evaluation system. IEEE Transactions on Software Engineering, SE–3(4):266–278, July 1977. [How78] William E. Howden. An evaluation of the effectiveness of symbolic testing. Software: Practice & Experience, 8:381–397, 1978. [How82] William E. Howden. Weak mutation testing and completeness of test sets. IEEE Transactions on Software Engineering, 8(4):371–379, July 1982. [HR00] Michael R. A. Huth and Mark D. Ryan. Logic in Computer Science: Modelling and Reasoning about Systems. Cambridge University Press, 2000. [HT90] Richard Hamlet, and Ross Taylor. Partition testing does not inspire confidence. IEEE Transactions on Software Engineering, 16(12):206–215, December 1990. [HW01] Daniel M. Hoffman, and David M. Weiss, editors. Software Fundamentals: Collected Papers by David L. Parnas. Addison-Wesley Longman, Boston, 2001. [Ins98] Institute of Electrical and Electronics Engineers. Software test documentation IEEE Std 829-1998. Technical report, IEEE, New York, 1998. [Ins02] Institute of Electrical and Electronics Engineers. IEEE standard for software

quality assurance plans – IEEE Std 730-2002. Technical report, IEEE, New York, 2002. [Jaa03] Ari Jaaksi. Assessing software projects: Tools for business owners. In Proceedings of the 9th European Software Engineering Conference held jointly with 10th ACM SIGSOFT International Symposium on Foundations of Software Engineering (ESEC/FSE), pages 15–18, Helsinki, Finland, September 2003. [Jac02] Daniel Jackson. Alloy: a lightweight object modelling notation. ACM Transactions on Software Engineering and Methodology, 11(2):256–290, 2002. [JN95] Neil D. Jones and Flemming Nielson. Abstract interpretation: A semanticsbased tool for program analysis. In S. Abramsky, Dov M. Gabbay, and T.S.E. Maibaum, editors, Handbook of Logic in Computer Science, volume 4, Semantic Modelling, pages 527–636. Clarendon Press, Oxford, UK, 1995. [KE85] Richard A. Kemmerer and Steven T. Eckman. UNISEX: A UNIX-based symbolic EXecutor for Pascal. Software: Practice & Experience, 15(5):439–458, 1985. [KM93] John C. Knight and E. Ann Myers. An improved inspection technique. Commununications of the ACM, 36(11):51–61, 1993. [KP02] Jung-Min Kim and Adam Porter. A history-based test prioritization technique for regression testing in resource constrained environments. In Proceedings of the 24th International Conference on Software Engineering, pages 119–129, Orlando, FL, 2002. [Lam89] Leslie Lamport. A simple approach to specifying concurrent systems. Commununications of the ACM, 32(1):32–45, 1989. [LD03] Michele Lanza and Stephane Ducasse. Polymetric views – a lightweight visual approach to reverse engineering. IEEE Transactions on Software Engineering, 29(9):782–795, September 2003. [Lev95] Nancy G. Leveson. Safeware: System Safety and Computers. AddisonWesley, Boston, 1995. [Lev04] Nancy G. Leveson. Role of software in spacecraft accidents. Journal of Spacecraft and Rockets, 41(4), July-August 2004. [Lio96] Jacques-Louis Lions. ARIANE 5 flight 501 failure: Report of the inquiry board. European Space Agency press release. Originally appeared at http://www.esrin.esa.it/htdocs/tidc/Press/Press96/ariane5rep.html. Reproduced at http://www.cs.berkeley.edu/∼demmel/ma221/ariane5rep.html, July 1996. [LK83] Janusz Laski and Bogdan Korel. A data flow oriented program testing strategy.

IEEE Transactions on Software Engineering, 9(5):33–43, 1983. [LPS02] Marek Leszak, Dewayne E. Perry, and Dieter Stoll. Classification and evaluation of defects in a project retrospective. The Journal of Systems and Software, 61(3):173–187, April 2002. [Mar97] Brian Marick. The Craft of Software Testing: Subsystems Testing Including Object-Based and Object-Oriented Testing. Prentice-Hall, Englewood Cliffs, NJ, 1997. [McC83] Thomas McCabe. Structured Testing. IEEE Computer Society Press, 1983. [Mea55] George H. Mealy. A method for synthesizing sequential circuits. Bell System Technical Journal, 34:1045–1079, 1955. [MF96] Delia I. S. Marx and Phyllis G. Frankl. The path-wise approach to data flow testing with pointer variables. In Proceedings of the 1996 International Symposium on Software Testing and analysis, pages 135–146, New York, January 8–10 1996. ACM Press. [Moo56] Edward F. Moore. Gedanken experiments on sequential machines. In Automata Studies, pages 129–153. Princeton University Press, Princeton, NJ, 1956. [Mor90] Larry J. Morell. A theory of fault-based testing. IEEE Transactions on Software Engineering, 16(8):844–857, August 1990. [MP43] Warren Sturgis McCulloch and Walter Harry Pitts. A logical calculus of the ideas immanent in nervous activity. Bulletin of Mathematical Biophysics, 5(115), 1943. Reprinted in Neurocomputing: Foundations of Research, 1988, MIT Press, Cambridge MA. [MS03] Atif M. Memon and Mary Lou Soffa. Regression testing of GUIs. In Proceedings of the 9th European Software Engineering Conference held jointly with 11th ACM SIGSOFT International Symposium on Foundations of Software Engineering (ESEC/FSE), pages 118–127, Helsinki, Finland, 2003. [Mus04] John D. Musa. Software Reliability Engineering: More Reliable Software Faster And Cheaper. Authorhouse, second edition, 2004. [Mye79] Glenford Myers. The Art of Software Testing. John Wiley and Sons, New York, 1979. [Nie00] Jakob Nielsen. Designing Web Usability: The Practice of Simplicity. New Riders Publishing, Indianapolis, IN, 2000. [Nor90] Donald A. Norman. The Design of Everyday Things. Doubleday/Currency ed., 1990.

[OAFG98] Thomas Ostrand, Aaron Anodide, Herbert Foster, and Tarak Goradia. A visual test development environment for GUI systems. In Proceedings of the ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA), volume 23,2 of ACM Software Engineering Notes, pages 82–92, New York, March 2– 5 1998. ACM Press. [OB88] Thomas J. Ostrand and Marc J. Balcer. The category-partition method for specifying and generating functional tests. Communications of the ACM, 31(6):676– 686, June 1988. [OO90] Kurt M. Olender and Leon J. Osterweil. Cecil: A sequencing constraint language for automatic static analysis generation. IEEE Transactions on Software Engineering, 16(3):268–280, 1990. [OO92] Kurt M. Olender and Leon J. Osterweil. Interprocedural static analysis of sequencing constraints. ACM Transactions on Software Engineering and Methodologies, 1(1):21–52, 1992. [Ors98] Alessandro Orso. Integration Testing of Object-Oriented Software. PhD thesis, Politecnico di Milano, 1998. [PJ97] Adam A. Porter and Philip M. Johnson. Assessing software review meetings: Results of a comparative analysis of two experimental studies. IEEE Transactions on Software Engineering, 23(3):129–145, March 1997. [PP98] Dennis K. Peters and David L. Parnas. Using Test Oracles Generated from Program Documentation. IEEE Transactions on Software Engineering, 24(3):161– 173, 1998. [PPP+97] James M. Perpich, Dewayne E. Perry, Adam A. Porter, Lawrence G. Votta, and Michael W. Wade. Anywhere, anytime code inspections: Using the web to remove inspection bottlenecks in large-scale software development. In Proceedings of the International Conference on Software Engineering (ICSE), Boston, Massachusetts, 1997. [PPW+05] Alexander Pretschner, Wolfgang Prenninger, Stefan Wagner, Christian Kühnel, M. Baumgartner, B. Sostawa, R. Zölch, and T. Stauner. One evaluation of model-based testing and its automation. In Proceedings of the 27th international Conference on Software Engineering (ICSE), pages 392–401, St. Louis, MO, 2005. [PTY95] Mauro Pezzè, Richard Taylor, and Michal Young. Graph models for reachability analysis of concurrent programs. ACM Transactions on Software Engineering and Methodologies, 4(2):171–213, April 1995. [PW85] David L. Parnas and David M. Weiss. Active design reviews: principles and practices. In Proceedings of the 8th International Conference on Software Engineering (ICSE), pages 132–136, London, England, 1985.

[PY99] Christina Pavlopoulou and Michal Young. Residual test coverage monitoring. In Proceedings of the International Conference on Software Engineering (ICSE), pages 277–284, 1999. [RAO92] Debra J. Richardson, Stephanie Leif Aha, and T. Owen O’Malley. Specification-based test oracles for reactive systems. In Proceedings of the 14th International Conference on Software Engineering (ICSE), pages 105–118, Melbourne, Australia, 1992. [RH97] Gregg Rothermel and Mary Jean Harrold. A safe, efficient regression test selection technique. ACM Transactions on Software Engineering and Methodology, 6(2):173–210, April 1997. [Ros95] David S. Rosenblum. A practical approach to programming with assertions. IEEE Transactions on Software Engineering, 21(1):19–31, 1995. [ROT89] Debra J. Richardson, Owen O’Malley, and Cynthia Tittle. Approaches to specification-based testing. In Proceedings of the ACM SIGSOFT Symposium on Software Testing, Analysis, and Verification (ISSTA 89), 1989. [RRL99] Atanas Rountev, Barbara G. Ryder, and William Landi. Dataflow analysis of program fragments. In Proceedings of the 7th European Software Engineering Conference held jointly with the 7th ACM International Symposium on Foundations of Software Engineering(ESEC/FSE), pages 235–252, Toulouse, France, 1999. Springer-Verlag. [Rus91] Glen W. Russell. Experience with inspection in ultralarge-scale development. IEEE Software, 8(1):25–31, 1991. [RW85] Sandra Rapps and Elaine Weyuker. Selecting software test data using data flow information. IEEE Transactions on Software Engineering, 11(4):367–375, April 1985. [SB99] Emin Gün Sirer and Brian N. Bershad. Using production grammars in software testing. In Proceedings of the 2nd Conference on Domain-Specific Languages (DSL ’99), pages 1–14, Austin, Texas, October 1999. USENIX, ACM Press. [SBN+97] Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, and Thomas Anderson. Eraser: A dynamic data race detector for multithreaded programs. ACM Transactions on Computer Systems, 15(4):391–411, 1997. [SC96] Phil Stocks and David Carrington. A framework for specification-based testing. IEEE Transactions on Software Engineering, 22(11):777–793, 1996. [SE04] David Saff and Michael D. Ernst. Mock object creation for test factoring. In Proceedings of the Workshop on Program Analysis for Software Tools and Engineering (PASTE ’04), pages 49–51, Washington, DC, 2004.

[SJLY00] Chris Sauer, D. Ross Jeffery, Lesley Land, and Philip Yetton. The effectiveness of software development technical reviews: A behaviorally motivated program of research. IEEE Transactions on Software Engineering, 26(1):1–14, 2000. [SS90] Mehmet Sahinoglu and Eugene Spafford. Sequential statistical procedure in mutation-based testing. In Proceedings of the 28th Annual Spring Reliability Seminar, pages 127–148, Boston, April 1990. Central New England Council of IEEE. [Ste96] Bjarne Steensgaard. Points-to analysis in almost linear time. In Proceedings of the Symposium on Principles of Programming Languages, pages 32–41, 1996. [Ste99] Arthur G. Stephenson. Mars climate orbiter: Mishap investigation board report. Technical report, NASA, November 1999. [TFW93] Pascale Théevenod—Fosse and Héléne Waeselynck. Statemate applied to statistical software testing. In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA), pages 99–109, Cambridge, MA, 1993. [TRC93] Margaret C. Thompson, Debra J. Richardson, and Lori A. Clarke. An information flow model of fault detection. In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA), pages 182–192, 1993. [Tuf90] Edward R. Tufte. Envisioning Information. Graphic Press, Cheshire CT, 1990. [Tuf97] Edward R. Tufte. Visual Explanations: Images and Quantities, Evidence and Narrative. Graphic Press, Cheshire CT, 1997. [Tuf01] Edward R. Tufte. The Visual Display of Quantitative Information. Graphic Press, Cheshire CT, 2nd edition, 2001. [Tuf06] Edward R. Tufte. Beautiful Evidence. Graphic Press, Cheshire CT, 2006. [Uni00] United State Department of Health and Human Services. Standards for privacy of individually identifiable health information (regulations pertaining to entities by the Health Insurance Portability and Accountability Act of 1996 (HIPAA). Text and commentary available at http://www.hhs.gov/ocr/hipaa/finalreg.html, Dec 2000. [Uni04] United States Computer Emergency Response Team (CERT). libpng fails to properly check length of transparency chunk (tRNS) data. Vulnerability Note VU#388984, available at http://www.kb.cert.org/vuls/id/388984, November 2004. [vBDZ89] Gregor von Bochman, Rachida Dssouli, and J. R. Zhao. Trace analysis for conformance and arbitration testing. IEEE Transactions on Software Engineering, 15(11):1347–1356, November 1989. [vBP94] Gregor von Bochmann and Alexandre Petrenko. Protocol Testing: Review of Methods and Relevance for Software Testing. Technical Report IRO-923,

Department d’Informatique et de Recherche Opérationnelle, Université de Montréal, 1994. [Wei07] Mark Allen Weiss. Data Structures and Algorithm Analysis in Java. AddisonWesley, Boston, 2nd edition, 2007. [Wey98] Elaine J. Weyuker. Testing component-based software: A cautionary tale. IEEE Software, 15(5):54–59, September/October 1998. [WHH80] Martin R. Woodward, David Hedley, and Michael A. Hennell. Experience with path analysis and testing of programs. IEEE Transactions on Software Engineering, 6(3):278–286, May 1980. [WO80] Elaine J. Weyuker and Thomas J. Ostrand. Theories of program testing and the the application of revealing subdomains. IEEE Transactions on Software Engineering, 6(3):236–246, May 1980. [YT89] Michal Young and Richard N. Taylor. Rethinking the taxonomy of fault detection techniques. In Proceedings of the International Conference on Software Engineering (ICSE), pages 53–62, Pittsburgh, May 1989. [Zel05] Andreas Zeller. Why Programs Fail: A Guide to Systematic Debugging. Morgan Kaufmann, San Francisco, 2005.

Index A A&T plan, 458 abstract classes, 277 testing, 281 abstraction function, 58, 110 abstraction in finite state models, 138 acceptance testing, 421-423 accessibility W3C Web content accessibility guidelines, 426 adaptive systems, 452 adequacy fault-based, 319 of test suites, 151 algebraic laws for data model verification, 144 alias, 94-96 in data flow testing, 241 interprocedural analysis, 97 all definitions adequacy criterion, 240 all definitions coverage, 241 all DU pairs adequacy criterion, 239, 295 all DU pairs coverage, 239 all DU paths adequacy criterion, 240 all DU paths coverage, 240 all-paths analysis, 85 Alloy finite state verification tool, 144 alpha and beta test, 10, 423 alpha test, 10 alternate expression, alternate program in fault-based testing, 315 analysis of dynamic memory use, 360-363 analysis plan, 382-386 AND-states in statecharts, 286

any-path analysis, 85 API (application program interface), 413 architectural design, 6 impact on static analysis and test, 40 argument in data flow analysis, 94 Ariane 5 incident, 406 array in data flow analysis, 94, 236 in data flow testing, 241 assembly testing, 413-415 assertion in symbolic execution, 105 assumed precondition, 194, 199 atomic blocks in Promela, 122 atomic operation, 132 atomic transaction serializability, 34 automating analysis and test, 439 availability, 10, 44 available expressions data flow analysis, 85

Index B Büuchi automaton, 125 backbone strategy, 410 Backus Naur Form (BNF), 257 backward data flow analysis, 87 basic block, 60 coverage, 216 basic condition, 219, 251 coverage, 253 basic condition adequacy criterion, 219 basic condition coverage, 219 basis set of a graph, 228 BDD, see ordered binary decision diagram (OBDD) behavior models extracting from execution, 365-369 beta test, 10, 423 bias in test case selection, 164 big bang testing, 408 binary decision diagram, see ordered binary decision diagram (OBDD) black-box testing, 154, 161, 162 BNF, see Backus Naur Form Boolean connective, 251 Boolean expression, 251 bottom-up integration testing, 410 boundary condition grammar-based criterion, 262 boundary interior criterion, 223 boundary interior loop coverage, 250 boundary value testing, 185, 194 boundary values, 172 branch adequacy criterion, 217, 257 branch and condition adequacy, 220

branch coverage, 217, 227 simulated with mutation, 320 brute force test case generation, 167 buffer overflow, 30, 50 build plan, 6, 408 build-and-test cycle, 327

Index C call coverage, 229 call graph, 63-65 analysis of Java throws clause, 65 Capability Maturity Model (CMM), 341 capture and replay, 337 catalog-based testing, 194-204 category-partition testing, 180-188 category, 180, 181 error constraints, 186 property constraints, 186 regression test selection, 432 cause-effect graphs, 253 certification testing in SRET, 380 CFG, see control flow graph characteristic function, 135 checklist, 37, 344-348 for Java source code, 346, 347 choice in category partition, 180 class reasoning about, 109 classes of values, 180, 185, 194 Cleanroom process, 378, 399 CMM, see Capability Maturity Model code generation from finite state models, 130 cognitive burden and aids, 448-449 collaboration diagram, 293 collective code ownership, 351 combinatorial testing, 179 for polymorphism, 302 combining techniques, 7

commercial off-the-shelf components (COTS), 414 in integration testing, 410 communication protocol, 246, 249 comparing testing criteria, 230 comparison-based oracle, 332 competent programmer hypothesis, 314 compiler grammar-based testing, 257 complete state transition relation, 70 complete analysis, 21 completeness structuring quality process for, 40 complex condition, 251 complex document structure grammar-based testing, 257 component, 414 component and assembly testing, 413-415 component-based system, 414 component-based testing, 405 compositional reasoning, 108 compound condition adequacy, 220 compound condition coverage, 253 conclusion of inference rule, 109 concurrency, 277 concurrency fault, 356 specifying properties, 24 concurrency control protocol, 35 condition testing, 219-222 conformance testing, 116, 130 conservative analysis, 20, 21, 91 consistency checks internal and external, 377 consistent self-consistency, 17 constraint in decision tables, 253

context independence in interprocedural analysis, 97 context-sensitive analysis, 65, 96 contract, 413, 415 as precondition, postcondition pair, 105 interface of component, 414 monitoring satisfactory completion, 400 of procedure as Hoare triple, 109 control dependence graph, 80 control flow graph, 59-63 control flow testing, 212 model-based, 257 regression testing, 429 controllability, 329 correctness, 43 and operating conditions, 45 correctness conjectures, 377 cost depends on time between error and fault detection, 29, 376 estimating and controlling, 382 of faults, 49 verification vs. development cost, 4 cost-effectiveness structuring quality process for, 40 COTS, see commercial off-the-shelf components counting residual faults, 322 coupling effect hypothesis, 314 critical dependence, 384 critical module, 412 critical paths, 383 critical systems, 44 cross-quality requirements, 6 CSP basis of Spin guarded commands, 122 cyclomatic complexity, 444 cyclomatic testing, 228

Index D dangling pointer, 357 data collection, 49 data dependence graph, 80 data flow (DF) regression test, 432 data flow adequacy criterion, 239 data flow analysis, 447 with arrays and pointers, 94, 236 data flow analysis algorithm, 82-84 data flow equation, 83 data flow graph deriving test cases from, 257 data flow model, 77 data flow testing for object-oriented programs, 295 data model verification, 140-146 data race, 356 data structure in data flow testing, 241 reasoning about, 109 database problem tracking, 11 deadlock, 32, 356 debugging, 449-451 decision structure, 251-255 decision table, 253 defect repair cost predictor, 40 defensive programming, 33 leads to unreachable code, 230 definition in a data flow model, 77 in catalog-based testing, 194, 199 definition-clear path, 78

definition-use association, see definition-use pair definition-use pair (DU pair), 77, 82, 236, 238 definition-use path (DU path), 238 delocalization inspection techniques to deal with, 344 dependability, 10, 15, 43, 421 measures of, 10 vs. time-to-market, 40 dependable, 16 dependence, 77 design activities paired with verification, 3 architectural, 6 feasibility study, 5 test design vs. test execution, 5 design for test, 35, 330, 375, 376, 389 risk-driven strategy, 419 system architecture and build plan, 408 design pattern vs. framework, 414 design rule to simplify verification, 447 design secret and modular reasoning, 109 desperate tester strategy, 410 deterministic, 24 state transition relation, 70 development risk, 391 development testing in SRET, 380 diagnosability, 408 digraph, see directed graph direct data dependence, 78 directed graph, 57 distraction cognitive burden, 448 distributed specifying properties, 24 distributed systems

finite state verification applicable to, 121 divide and conquer, 35 document object model (DOM), 415 as a component interface contract, 415 documentation, 455 documentation quality, 458 DOM, see document object model domain-specific language grammar-based testing, 257 dominator, 80 double-checked locking idiom, 117, 130 driver, 408 DU pair, see definition-use pair DU path, see definition-use path dual of a directed graph, 68 dynamic analysis, 355 dynamic binding, 277, 301-303 dynamic memory allocation faults, 357 dynamic memory analysis, 360-363 dynamic method dispatch representation in call graph, 63

Index E egoless programming, 351 elementary condition, 219 elementary items identifying, 194 embedded control system, 246 encapsulation, 272 and test oracles, 300 modular reasoning, 109 entry and exit testing (procedure call testing), 229 environment, 328 environmental needs, 460 equivalent mutant, 319 equivalent scenarios, 300 erroneous condition testing, 185, 194 error off-by-one, 185 error propagation, 236 error values, 172 estimating population sizes, 322 exception, 277, 308-309 analysis in Java, 97 as implicit control flow, 60, 309 test cases for, 281 executing test cases, 327 execution history priority schema, 436 execution risk, 391 exhaustive testing, 20 explicit model checking vs. symbolic model checking, 138 explicit requirement vs. implicit requirement, 43 exploratory testing, 424 extensional representation, 134

external and internal qualities, 42 extreme programming (XP), 351, 381, 401

Index F fail-fast, 30 failure critical vs. noncritical, 44 fairness properties, 125 false alarms, 129 fault analysis, 12 categorization, 49 distribution, 391 injection, 323 localization, 408 model, 314-316 propagation to failure, 212 revealing priority schema, 436 seeding, 154, 314, 315 fault-based testing, 154, 313 adequacy criterion, 156, 319 of hardware, 323 vs. functional testing, 163 feasibility study, 5, 46, 382 feature-oriented integration strategy, 412 features to be analyzed or tested, 460 feedback, 36-37, 399, 408 in the Cleanroom process, 378 feedback loop, 49 finite models of software, 55 finite state machine (FSM), 65-73, 359 conformance testing, 130 correctness relations, 70 deriving test cases from, 246-250 don’t care transition, 250 error transition, 250 model derived from class specification, 282 self transition, 250

finite state verification, 113, 360, 447 FLAVERS finite state verification tool, 139 flow analysis, 359 vs. finite state verification, 113 flow-insensitive, 97 formal specification for symbolic execution, 356 forward, any-path analysis static taint analysis, 92 forward data flow analysis, 85, 90 fossil code, 230 framework, 414 FSM, see finite state machine function (mathematics vs. programs), 170 functional specification, 162 functional testing, 154, 161, 166

Index G garbage detector, 363 gen set in data flow analysis, 85 varying, 92 generating test cases, 327 generating test case specifications, 172 generating test data, 328-329 generics, 306-308 glass-box testing, see structural testing global property, 420 graceful degradation, 45 grammars deriving tests from, 257-265 graphical user interface specifying properties, 24 guarded commands in Promela, 122

Index H halting problem, 18 hazards, 44 hierarchical (compositional) reasoning, 108 hierarchical interprocedural analysis, 97 HIPAA safeguards, 420 Hoare triple, 108 in test oracle, 335 HTML DOM model, 415 HTTP, see Hypertext Transport Protocol Hypertext Transport Protocol (HTTP), 35, 36

Index I immediate dominator, 80 implementation, 17 implicit control flow, 60, 309 implicit requirement, 43 incident Apache 2 buffer overflow, 407 Apache 2.0.48 memory leak, 409 Ariane 5 failure, 406 libPNG buffer overflow, 406 loss of Mars Climate Orbiter, 407 incremental development and scaffolding, 329 independent verification and validation (IV&V), 400, 419 independently testable feature (ITF), 170 indivisible action, 132 inevitability flow analysis, 90 infeasibility identifying infeasible paths with symbolic execution, 102 infeasible path, 105 problem in test coverage, 230-232, 243 unsatisfiable test obligations, 156 inference rule, 109 information clutter cognitive burden, 448 information hiding and modular reasoning, 109 inheritance, 272 in object-oriented testing, 303-306 representation in call graph, 63 testing inherited and overridden methods, 281 inspection, 37, 341 benefits and bottlenecks, 46 inspection process, 344 inspector, 297

inspector/modifiers, 297 instruction reordering, 132 integration faults taxonomy, 407 integration strategies feature-oriented, 412 integration testing, 405 for object-oriented programs, 286-293 strategies, 408-412 intensional model, 134-138 interclass structural testing, 297 interclass testing, 286-293 interface contract of component, 414 interface specification, 413, 415 internal and external qualities, 42 interpreter grammar-based testing, 257 interprocedural control flow (call graph), 63 interprocedural data flow analysis, 96 intraclass structural testing, 295 intraclass testing, 281-286 intraprocedural control flow graph, 59 invariant, 358 assertion, 105 preserved in a loop, 106 structural, 335 ISO/IEC 9126 standard quality metrics, 445 items to be verified, 458 ITF, see independently testable feature IV&V, see independent verification and validation

Index J Java inspection checklist, 346, 347 JUnit, 330, 331

Index K kill, 78 in data flow analysis, 82 mutation analysis, 319 kill set in data flow analysis, 85 varying, 92

Index L lattice, 93 LCSAJ, see linear code sequence and jump libPNG buffer overflow incident, 406 linear code sequence and jump (LCSAJ), 60, 227 lines of code static metric, 443 live mutants, 319 live variables data flow analysis, 85 liveness properties, 125 LOC source lines of code, 443 lock, 356 lockset analysis, 363-365 loop boundary adequacy criterion, 227 loop invariant, 105 lost update problem, 132

Index M may immediately precede (MIP) relation, 139 MC/DC, see modified condition/decision coverage Mealy machine, 65 mean time between failures (MTBF), 10, 44, 378 memory analysis, 360-363 fault, 357, 360 leak, 357, 360, 409 metrics, 389 MIP, see may immediately precede relation missing code fault, 163 missing path faults, 215 misspelled variable, 90 mock, 330 model, 55 correspondence, 129-134 extraction, 129 granularity, 131-134 important attributes of, 55 intensional, 134 refinement, 138-140 model checking, see finite state verification, 447 model-based testing, 154, 171, 245 regression test selection, 432 modified condition/decision coverage (MC/DC), 221, 255 required by RTCA/DO-178B standard, 222, 379 modifier, 297 modular specifications and reasoning, 109 module and unit testing, 405 monitoring and planning, 41 monitoring the quality process, 389-394 MTBF, see mean time between failures multiple condition coverage, 220

mutant, 315 mutation analysis, 315-324 vs. structural testing, 320 mutation operator, 315, 316, 318

Index N necessary condition, 22 nightly build-and-test cycle, 327, 420 node adequacy criterion, 257 nondeterministic, 24 nonfunctional properties in component interface contract, 415 nonlinearity, 4 nonlocality cognitive burden, 448 normal conditions selected in catalog-based testing, 194

Index O OBDD, see ordered binary decision diagram object reference in data flow analysis, 94 object-oriented method dispatch representation in call graph, 63 object-oriented software issues in testing, 272 orthogonal approach to testing, 280 testing, 271 observability, 36, 329, 408 OCL assertions about data models, 140 ODC, see orthogonal defect classification operation in catalog-based testing, 194 operational profile, 422 in SRET, 380 optimistic inaccuracy, 20, 21 OR-state in statechart, 284 oracle, 8, 328, 332-338 for object-oriented programs, 298-301 from finite state machine, 249 ordered binary decision diagram (OBDD), 135 orthogonal defect classification (ODC), 392 outsourcing, 401 overall quality, 458

Index P pair programming, 351, 381, 401 pairwise combination testing, 188-194 parameter characteristic, 180, 181 parameterized type, 306-308 partial functionality, 45 partial oracle, 333 partial order reduction, 134, 138 partition, 35-36 categories into choices, 180, 185 partition testing, 162-167 patch level, 11 patch level release, 11 path adequacy criterion, 222 path coverage, 222 path testing, 222-228 and data interactions, 236 peer review, 401 performance, 419 Perl taint mode, 91 personnel risk, 386, 390 pessimistic inaccuracy, 20, 21 plan, 41 analysis and test plan, 8 analysis and test plan document, 458-460 monitoring, 8 relation to strategy, 379 selecting analysis and test tools, 441 test and analysis, 382 planning and monitoring, 41 sandwich integration strategy, 412 planning tools, 441-443 point release, 11

pointer in data flow analysis, 94, 236 in data flow testing, 241 pointer arithmetic in data flow analysis, 94 polymorphism, 277, 301-303 post-dominator, 81 postcondition, 105, 358 in catalog-based testing, 194, 199 in test oracle, 335 of state transition, 249 powerset lattice, 93 pre-dominator, 81 precondition, 105, 358 in catalog-based testing, 194, 197 in test oracle, 335 of state transition, 249 predicate, 251 premise of inference rule, 109 preserving an invariant, 106 principles of test and analysis, 29 prioritization of regression test cases, 434-436 probabilistic grammar-based criteria, 265 problem tracking database, 11 procedure call testing, 229-230 procedure entry and exit testing, 229 process improvement, 12, 49, 394-399 management, 441 monitoring, 389-394 visibility, 36, 41, 383, 389 process qualities vs. product qualities, 42 production coverage criterion, 262 program generation, 130 generic term for artifact under test, 161

verifier, 447 program analysis, 355 program dependence graph representation of, 80 program location in fault-based testing, 315 Promela (Spin input language), 121, 122, 129 test case generation, 329 propagation from fault to failure, 212 protocol, 246, 249 proxy measure, 41 test coverage, 156

Index Q quality cross-quality requirements, 6 goal, 42 manager, 382 plan, 8, 376, 458 process, 39, 376-377 team, 399-402 quantifier in assertions, 337

Index R race condition, 32, 117, 132 random testing, 162 RCA, see root cause analysis reaching definition, 82 data flow equation, 83 reading techniques in inspection, 344 redundancy, 32-33 reference in data flow analysis, 94 refining finite state models, 138-140 region in control flow analysis, 59 regression test, 11, 418, 427-436 prioritization, 434-436 selection, 428-434 regular expressions deriving tests from, 257-265 relational algebra, 144 for data model verification, 140 release point release vs. patch, 11 reliability, 10, 44, 45, 419 report, 462-465 representative value classes, 171 representative values, 180, 185 requirement engineering, 420 implicit vs. explicit, 43 risk, 391 specification, 16, 162 residual faults statistical estimation, 322 resources and responsibilities, 460

responsibilities allocating, 50 restriction, 33-35 retest all, 427 reuse unreachable code in, 230 review phase in inspection, 344 risk generic to process management, 390 planning, 386-389 specific to quality management, 391 robustness, 45 root cause analysis (RCA), 37, 49, 394 RTCA/DO-178B standard, 379 run-time support for testing, 327

Index S safe analysis, 21 safety, 44, 45, 420 properties, 125 property of system and environment, 420 specification, 45 sandwich or backbone, 410 scaffolding, 8, 328-332, 408 generic vs. specific, 330 scalability of finite state verification techniques, 114 scenarios, 415 schedule risk, 386, 390 schedule visibility, 36 scripting rule grammar-based testing, 257 SDL, 246 security, 420 finite state verification applicable to, 121 security hazard preventing with Perl taint mode, 91 seeded faults, 154, 314, 315 selection of test cases, 151 selective regression test execution, 434-436 self-monitoring and adaptive systems, 452 semantic constraints in category-partition method, 180, 186 sensitivity, 29-32 sensitivity testing, 422 sequence diagram, 293 sequencing properties, 125 serializability, 34

severity levels in fault classification, 392, 397 short-circuit evaluation, 221 Simple Mail Transport Protocol (SMTP), 36 simple transition coverage, 286 single state path coverage, 250 single transition path coverage, 250 singularity in input space, 164 SMTP, see Simple Mail Transport Protocol software reliability engineered testing (SRET), 380, 399 sound analysis, 21 special value testing, 164 specification, 17 as precondition and postcondition assertions, 105 correctness relative to, 44 decomposing for category-partition testing, 180, 181 requirement, 16 specification-based testing, 154, 161, 166 regression test selection, 432 Spin finite state verification tool, 121 spiral process in SRET approach, 380 spiral process model, 376 spurious reports in finite state verification, 138 SQL as a component interface contract, 415 SRET, see software reliability engineered testing state transition table representation of finite state machine, 70 state diagram, see statechart state space, 58 state space exploration, 116-134 state space explosion problem, 126 state transition diagram representation of finite state machine, 70

state transition table representation of finite state machine, 69 state-based intraclass testing, 281 state-based testing object state, 282 state-dependent behavior, 272 statechart, 246, 282 of object behavior, 284 stateless component interfaces, 35 statement adequacy criterion, 215 statement coverage, 156, 215, 227 simulated with mutation, 320 static analysis, 48, 341, 355 automation, 445-448 static metrics, 443-445 statistical approximation, 45 statistical estimation of population sizes, 322 statistical mutation analysis, 321 statistical testing, 378, 421 vs. systematic testing, 422 strategy, 41, 377-381 document, 458 relation to plan, 379 stress testing, 420 strong mutation, 321 structural integration test strategy, 410 structural invariant, 110, 335 structural priority schema, 436 structural testing, 154, 211 of classes, 293-298 vs. functional testing, 161, 163 vs. mutation analysis, 320 stub, 329, 408 subsumes, 157 sufficient condition, 22, 23 summary information in symbolic execution, 104 superstate

in statechart, 284 suspend and resume criteria, 460 symbolic execution, 101, 356-359 vs. finite state verification, 113 symbolic model checking, 134, 135, 138 symbolic testing, 358-359 symbolic values for variables in symbolic execution, 106 synchronized block (in Java), 356 syntax grammar-based testing, 257 system integration, 408 system testing, 418-421 systematic test case generation, 167

Index T taint mode in Perl, 91 tasks and schedule, 460 technology risk, 386, 390 template, 306-308 temporal logic, 125 TERk coverage, 227 test adequacy criterion, 153 deliverable, 460 driver, 329 execution, 48, 153 harness, 329 input, 152 obligation, 153, 154 oracle, 332-338 pass/fail criterion, 152 plan, 382-386 scenarios, 415 specification, 153 strategy document, 458 test case, 153 maintenance, 427 test case specification, 172 document, 462 generating, 180, 186 test coverage as proxy measure for thoroughness, 156 test design early, 48 specification document, 460-462 test first in XP, 381, 401 testability design for, 330, 375, 376, 389 testing history, 304 testing team, 400

theorem prover, 447, 448 in symbolic execution, 107 thread, 116 dynamic analysis of locks, 363-365 testing, 412 throws clause check, 65, 97 time-to-market vs. dependability, 40 timeliness structuring quality process for, 40 top-down and bottom-up testing, 410 trade-offs among goals, 42 transition coverage, 249 transition table representation of finite state machine, 69 type checking, 33, 447

Index U UML data models, 140 sequence and collaboration diagrams, 293 statechart, 284 undecidability, 18, 113 undecidability and unsatisfiable test obligations, 156 unit work assignment, 170 unit and integration test suites unsuitable for system testing, 418 unit testing for object-oriented programs, 282-286 unreachable code, 230 usability, 423-425 specifying and verifying properties, 24 usability testing, 6 assigned to separate team, 460 usage profile, 44, 378 use in a data flow model, 77 use/include relation, 286 useful distinct from dependable, 16 useful mutant, 316 usefulness, 43, 418 useless definition, 90 user stories, 381

Index V V model, 17, 376, 405 V&V, see verification and validation valid mutant, 316 validated precondition, 194, 197, 199 validation, 15, 17 acceptance testing as, 418 vs. verification, 7 variable in catalog-based testing, 194 initialization analysis, 87 verification, 16 of self-consistency and well-formedness, 17 purpose of functional testing, 162 system testing as, 418 vs. validation, 7 verification and validation (V&V), 6 version control, 449 visibility, 36, 41, 383, 389

Index W W3C Web content accessibility guidelines, 426 waterfall process model, 376 WCAG W3C Web content accessibility guidelines, 426 weak mutation analysis, 321 weakening a predicate, 104 well-formedness and self-consistency, 17 white-box testing, see structural testing

Index X-Z XML as a component interface contract, 415 DOM model, 415 XML schema grammar-based testing, 262 XP, see extreme programming

List of Figures

Preface Figure 1: Selecting core material by need

Chapter 1: Software Test and Analysis in a Nutshell Figure 1.1: Main analysis and testing activities through the software life cycle.

Chapter 2: A Framework for Test and Analysis Figure 2.1: Validation activities check work products against actual user requirements, while verification activities check consistency of work products. Figure 2.2: Verification trade-off dimensions

Chapter 3: Basic Principles Figure 3.1: Standard C functions strcpy and strncpy may or may not fail when the source string is too long. The procedure stringCopy is sensitive: It is guaranteed to fail in an observable way if the source string is too long. Figure 3.2: Can the variable k ever be uninitialized the first time i is added to it? The property is undecidable, so Java enforces a simpler, stricter property.

Chapter 4: Test and Analysis Activities Within a Software Process Figure 4.1: Relation among dependability properties

Chapter 5: Finite Models Figure 5.1: Abstraction elides details of execution states and in so doing may cause an abstract model execution state to represent more than one concrete program execution state. In the illustration, program state is represented by three attributes, each with two possible values, drawn as light or dark circles. Abstract model states retain the first two attributes and elide the third. The relation between (1a) and (1b) illustrates coarsening of the execution model, since the first and third program execution steps modify only the omitted attribute. The relation between (2a) and (2b) illustrates introduction of nondeterminism, because program execution states with different successor states have been merged. Figure 5.2: Building blocks for constructing intraprocedural control flow graphs. Other control constructs are represented analogously. For example, the for construct of C, C++, and Java is represented as if the initialization part appeared before a while loop, with the increment part at the end of the while loop body. Figure 5.3: A Java method to collapse adjacent newline characters, from the StringUtilities class of the Velocity project of the open source Apache project. (c) 2001 Apache Software Foundation, used with permission. Figure 5.4: A control flow graph corresponding to the Java method in Figure 5.3. The for statement and the predicate of the if statement have internal control flow branches, so those statements are broken across basic blocks. Figure 5.5: Linear code sequences and jumps (LCSAJs) corresponding to the Java method in Figure 5.3 and the control flow graph in Figure 5.4. Note that proceeding to the next sequential basic block is not considered a “jump” for purposes of identifying LCSAJs. Figure 5.6: Overapproximation in a call graph. Although the method A.check() can never actually call C.foo(), a typical call graph construction will include it as a possible call. Figure 5.7: The Java code above can be represented by the context-insensitive call graph at left. However, to capture the fact that method depends never attempts to store into a nonexistent array element, it is necessary to represent parameter values that differ depending on the context in which depends is called, as in the context-sensitive call graph on the right. Figure 5.8: The number of paths in a call graph – and therefore the number of calling contexts in a context-sensitive analysis – can be exponentially larger than the number of procedures, even without recursion. Figure 5.9: Finite state machine (Mealy machine) description of line-end conversion procedure, depicted as a state transition diagram (top) and as a state transition table (bottom). An omission is obvious in the tabular representation, but easy to overlook in the state transition diagram.

Figure 5.10: Correctness relations for a finite state machine model. Consistency and completeness are internal properties, independent of the program or a higher-level specification. If, in addition to these internal properties, a model accurately represents a program and satisfies a higher-level specification, then by definition the program itself satisfies the higher-level specification. Figure 5.11: Procedure to convert among Dos, Unix, and Macintosh line ends. Figure 5.12: Completed finite state machine (Mealy machine) description of line-end conversion procedure, depicted as a state-transition table (bottom). The omitted transition in Figure 5.9 has been added.

Chapter 6: Dependence and Data Flow Models Figure 6.1: Java implementation of Euclid’s algorithm for calculating the greatest common denominator of two positive integers. The labels A–F are provided to relate statements in the source code to graph nodes in subsequent figures. Figure 6.2: Control flow graph of GCD method in Figure 6.1. Figure 6.3: Data dependence graph of GCD method in Figure 6.1, with nodes for statements corresponding to the control flow graph in Figure 6.2. Each directed edge represents a direct data dependence, and the edge label indicates the variable that transmits a value from the definition at the head of the edge to the use at the tail of the edge. Figure 6.4: Calculating control dependence for node E in the control flow graph of the GCD method. Nodes C, D, and E in the gray region are post-dominated by E; that is, execution of E is inevitable in that region. Node B has successors both within and outside the gray region, so it controls whether E is executed; thus E is controldependent on B. Figure 6.5: Control dependence tree of the GCD method. The loop test and the return statement are reached on every possible execution path, so they are controldependent only on the entry point. The statements within the loop are controldependent on the loop test. Figure 6.6: An iterative work-list algorithm to compute reaching definitions by applying each flow equation until the solution stabilizes. Figure 6.7: An iterative work-list algorithm for computing available expressions. Figure 6.8: Function questionable (repeated from Chapter 3) has a potentially uninitialized variable, which the Java compiler can detect using data flow analysis. Figure 6.9: Control flow graph of the source code in Figure 6.8, annotated with variable definitions and uses. Figure 6.10: Control flow graph of the source code in Figure 6.8, annotated with gen and kill sets for checking variable initialization using a forward, all-paths Avail analysis. (Empty gen and kill sets are omitted.) The Avail set flowing from node G to node C will be {i,k}, but the Avail set flowing from node B to node C is {i}. The all-paths analysis intersects these values, so the resulting Avail (C) is {i}. This value propagates through nodes C and D to node F, which has a use of k as well as a definition. Since k ∉ Avail(F), a possible use of an uninitialized variable is detected. Figure 6.11: Part of a CGI program (Web form processing) in Python. The misspelled variable name in the data validation method will be implicitly declared and will not be rejected by the Python compiler or interpreter, which could allow invalid data to be treated as valid. The classic live variables data flow analysis can show that the

assignment to valid is a useless definition, suggesting that the programmer probably intended to assign the value to a different variable. Figure 6.12: The powerset lattice of set {a,b,c}. The powerset contains all subsets of the set and is ordered by set inclusion. Figure 6.13: Spurious execution paths result when procedure calls and returns are treated as normal edges in the control flow graph. The path (A,X,Y,D) appears in the combined graph, but it does not correspond to an actual execution order.

Chapter 7: Symbolic Execution and Proof of Properties Figure 7.1: Binary search procedure. Figure 7.2: Hand-tracing an execution step with concrete values (left) and symbolic values (right).

Chapter 8: Finite State Verification Figure 8.1: The finite state verification framework. Figure 8.2: Double-check pattern, misapplied to reinitialization. Figure 8.3: Finite state models of individual threads executing the lookup and reInit methods from Figure 8.2. Each state machine may be replicated to represent concurrent threads executing the same method. Figure 8.5: Excerpts of Spin verification tool transcript. Spin has performed a depth-first search of possible executions of the model, exploring 10 states and 51 state transitions in 0.16 seconds before finding a sequence of 17 transitions from the initial state of the model to a state in which one of the assertions in the model evaluates to False. Figure 8.4: Promela finite state model of faulty double-check implementation. Figure 8.6: A Spin guided simulation trace describes each of the 17 steps from the initial model state to the state in which the assertion !(modifying) is violated. For example, in step 8, one of the two processes (threads) simulating execution of the Lookup method sets the global variable modifying to True, represented as the integer value 1. A graphical representation of this trace is presented in Figure 8.7. Figure 8.7: A graphical interpretation of Spin guided simulation output (Figure 8.6) in terms of Java source code (Figure 8.2) and state machines (Figure 8.3). Figure 8.8: The classic dining philosophers problem in Promela. The number of unique states explored before finding the potential deadlock (with default settings) grows from 145 with 5 philosophers, to 18,313 with 10 philosophers, to 148,897 with 15 philosophers. Figure 8.9: A simple data race in Java. The possible ending values of i depend on how the statement i = i+1 in one thread is interleaved with the same sequence in the other thread. Figure 8.10: Coarse and fine-grain models of the same program from Figure 8.9. In the coarse-grain model, i will be increased by 2, but other outcomes are possible in the finer grain model in which the shared variable i is loaded into temporary variable or register, updated locally, and then stored. Figure 8.11: The lost update problem, in which only one of the two increments affects the final value of i. The illustrated sequence of operations from the program of Figure 8.9 can be found using the finer grain model of Figure 8.10, but is not revealed by the coarser grain model. Figure 8.12: Ordered binary decision diagram (OBDD) encoding of the Boolean proposition a ↠ b ∧ c, which is equivalent to ¬a ∨ (b ∧ c). The formula and OBDD structure can be thought of as a function from the Boolean values of a, b, and c to a

single Boolean value True or False. Figure 8.13: Ordered binary decision diagram (OBDD) representation of a transition relation, in three steps. In part (A), each state and symbol in the state machine is assigned a Boolean label. For example, state s0 is labeled 00. In part (B), transitions are encoded as tuples 〈sym,from,to〉 indicating a transition from state from to state to on input symbol sym. In part (C), the transition tuples correspond to paths leading to the True leaf of the OBDD, while all other paths lead to False. The OBDD represents a characteristic function that takes valuations of x0 …x4 and returns True only if it corresponds to a state transition. Figure 8.14: The data model of a simple Web site. Figure 8.15: Alloy model of a Web site with different kinds of pages, users, and access rights (data model part). Continued in Figure 8.16. Figure 8.16: Alloy model of a Web site with different kinds of pages, users, and access rights, continued from Figure 8.15. Figure 8.17: A Web site that violates the “browsability” property, because public page Page_2 is not reachable from the home page using only unrestricted links. This diagram was generated by the Alloy tool.

Chapter 9: Test Case Selection and Adequacy Figure 9.1: A Java method for collapsing sequences of blanks, excerpted from the StringUtils class of Velocity version 1.3.1, an Apache Jakarta project. © Apache Group, used by permission.

Chapter 10: Functional Testing Figure 10.1: The Java class roots, which finds roots of a quadratic equation. The case analysis in the implementation is incomplete: It does not properly handle the case in which b2 − 4ac = 0 and a = 0. We cannot anticipate all such faults, but experience teaches that boundary values identifiable in a specification are disproportionately valuable. Uniform random generation of even large numbers of test cases is ineffective at finding the fault in this program, but selection of a few “special values” based on the specification quickly uncovers it. Figure 10.2: A quasi-partition of a program’s input space. Black circles represent inputs that lead to failures. All elements of the input domain belong to at least one class, but classes are not disjoint. Figure 10.3: The main steps of a systematic approach to functional program testing.

Chapter 11: Combinatorial Testing Figure 11.1: Functional specification of the feature Check configuration of the Web site of a computer manufacturer. Figure 11.2: An informal (and imperfect) specification of C function cgi decode Figure 11.3: Elementary items of specification cgi decode Figure 11.4: Test case specifications for cgi decode generated after step 2

Chapter 12: Structural Testing Figure 12.1: The C function cgi decode, which translates a cgi-encoded string to a plain ASCII string (reversing the encoding applied by the common gateway interface of most Web servers). Figure 12.2: Control flow graph of function cgi decode from Figure 12.1 Figure 12.3: The control flow graph of C function cgi decode which is obtained from the program of Figure 12.1 after removing node F. Figure 12.4: Deriving a tree from a control flow graph to derive subpaths for boundary/interior testing. Part (i) is the control flow graph of the C function cgi decode, identical to Figure 12.1 but showing only node identifiers without source code. Part (ii) is a tree derived from part (i) by following each path in the control flow graph up to the first repeated node. The set of paths from the root of the tree to each leaf is the required set of subpaths for boundary/interior coverage. Figure 12.5: A C function for searching and dynamically rearranging a linked list, excerpted from a symbol table package. Initialization of the back pointer is missing, causing a failure only if the search key is found in the second position in the list. Figure 12.6: The control flow graph of C function search with move-to-front feature. Figure 12.7: The boundary/interior subpaths for C function search. Figure 12.8: The subsumption relation among structural test adequacy criteria described in this chapter.

Chapter 13: Data Flow Testing Figure 13.1: The C function cgi_decode, which translates a cgi-encoded string to a plain ASCII string (reversing the encoding applied by the common gateway interface of most Web servers). This program is also used in Chapter 12 and also presented in Figure 12.1 of Chapter 12. Figure 13.2: A C procedure with a large number of DU paths. The number of DU paths for variable ch is exponential in the number of if statements, because the use in each increment and in the final print statement can be paired with any of the preceding definitions. The number of DU paths for variable count is the same as the number of DU pairs. For variable ch, there is only one DU pair, matching the procedure header with the final print statement, but there are 256 definition-clear paths between those statements exponential in the number of intervening if statements. Figure 13.3: Pointers to objects in the program stack can create essentially arbitrary definition-use associations, particularly when combined with pointer arithmetic as in this example.

Chapter 14: Model-Based Testing Figure 14.1: Functional specification of feature Maintenance of the Chipmunk Web site. Figure 14.2: A finite state machine corresponding to functionality Maintenance specified in Figure 14.1 Figure 14.3: The functional specification of feature Pricing of the Chipmunk Web site. Figure 14.4: A decision table for the functional specification of feature Pricing of the Chipmunk Web site of Figure 14.3. Figure 14.5: The set of test cases generated for feature Pricing of the Chipmunk Web site applying the modified adequacy criterion. Figure 14.6: Functional specification of the feature Process shipping order of the Chipmunk Web site. Figure 14.7: A control flow graph model corresponding to functionality Process shipping order of Figure 14.6. Figure 14.8: Test suite T-node, comprising test case specifications TC-1 and TC-2, exercises each of the nodes in a control flow graph model of the specification in Figure 14.6. Figure 14.9: Test suite T-branch exercises each of the decision outcomes in a control flow graph model of the specification in Figure 14.6. Figure 14.10: Functional specification of the feature Advanced search of the Chipmunk Web site. Figure 14.11: BNF description of functionality Advanced search Figure 14.12: An XML schema description of a Product configuration on the Chipmuk Web site. Items are enclosed in matching tags (〈tag〉 text 〈/tag〉) or incorporated in a self-terminating tag (〈tag attribute=”value” /〉). The schema describes type ProductConfigurationType as a tuple composed of a required field modelNumber of type string; a set (possibly empty) of Components, each of which is composed of two stringvalued fields ComponentType and ComponentValue; and a possibly empty set of OptionalComponents, each of which is composed of a single string-valued ComponentType. Figure 14.14: The derivation tree of a test case for functionality Advanced Search derived from the BNF specification of Figure 14.11. Figure 14.13: BNF description of Product configuration. Figure 14.15: The BNF description of Product Configuration extended with production

names and limits. Figure 14.16: Sample seed probabilities for BNF productions of Product configuration.

Chapter 15: Testing Object-Oriented Software Figure 15.1: Part of a Java implementation of class Model. Figure 15.3: An excerpt from the class diagram of the Chipmunk Web presence that shows the hierarchy rooted in class LineItem. Figure 15.4: Part of a Java implementation of Class Account. The abstract class is specialized by the regional markets served by Chipmunk into USAccount, UKAccount, JPAccount, EUAccount and OtherAccount, which differ with regard to shipping methods, taxes, and currency. A corporate account may be associated with several individual customers, and large companies may have different subsidiaries with accounts in different markets. Method getYTDPurchased() sums the year-to-date purchases of all customers using the main account and the accounts of all subsidiaries. Figure 15.5: The impact of object-oriented design and coding on analysis and testing. Figure 15.6: Statechart specification of class Model. Figure 15.7: Finite state machine corresponding to the statechart of Figure 15.6. Figure 15.8: Statechart specification of class Order. This is a conceptual model in which both methods of class Order and method calls by class Order are represented as transitions with names that differ from method names in the implementation (e.g., 5DaysBeforeShipping is not a legal method or field name). Figure 15.9: Finite state machine corresponding to the statechart of Figure 15.8. Figure 15.10: Part of a class diagram of the Chipmunk Web presence. Classes Account, LineItem, and CSVdb are abstract. Figure 15.11: Use/include relation for the class diagram in Figure 15.10. Abstract classes are not included. Two classes are related if one uses or includes the other. Classes that are higher in the diagram include or use classes that are lower in the diagram. Figure 15.12: A (partial) sequence diagram that specifies the interactions among objects of type Order, Model, ModelDB, Component, ComponentDB, Slots, and SlotDB, to select a computer, add an illegal component, and then add a legal one. Figure 15.2: More of the Java implementation of class Model. Because of the way method isLegalConfig is implemented (see Figure 15.1), all methods that modify slots must reset the private variable legalConfig. Figure 15.13: A partial intraclass control flow graph for the implementation of class Model in Figures 15.1 and 15.2. Figure 15.14: Summary information for structural interclass testing for classes Slot, ModelDB, and Model. Lists of CFG nodes in square brackets indicate different paths,

when methods include more than one part. Figure 15.15: A method call in which the method itself and two of its parameters can be dynamically bound to different classes. Figure 15.16: Part of a Java implementation of the abstract class LineItem. Figure 15.17: Part of a Java implementation of class CompositeItem.

Chapter 16: Fault-Based Testing Figure 16.1: Program transduce converts line endings among Unix, DOS, and Macintosh conventions. The main procedure, which selects the output line end convention, and the output procedure emit are not shown. Figure 16.2: A sample set of mutation operators for the C language, with associated constraints to select test cases that distinguish generated mutants from the original program. Figure 16.3: A sample set of mutants for program Transduce generated with mutation operators from Figure 16.2. x indicates the mutant is killed by the test case in the column head. Figure 16.4: C function to determine whether one string is within edit distance 1 of another.

Chapter 17: Test Execution Figure 17.1: Excerpt of JFlex 1.4.1 source code (a widely used open-source scanner generator) and accompanying JUnit test cases. JUnit is typical of basic test scaffolding libraries, providing support for test execution, logging, and simple result checking (assertEquals in the example). The illustrated version of JUnit uses Java reflection to find and execute test case methods; later versions of JUnit use Java annotation (metadata) facilities, and other tools use source code preprocessors or generators. Figure 17.2: A test harness with a comparison-based test oracle processes test cases consisting of (program input, predicted output) pairs. Figure 17.3: When self-checks are embedded in the program, test cases need not include predicted outputs. Figure 17.4: A structural invariant checked by run-time assertions. Excerpted from the Eclipse programming environment, version 3. © 2000, 2005 IBM Corporation; used under terms of the Eclipse Public License v1.0.

Chapter 18: Inspection Figure 18.1: Detailed description referenced by a checklist item.

Chapter 19: Program Analysis Figure 19.1: A C program that invokes the C function cgi_decode of Figure 12.1 with memory for outbuf allocated from the heap. Figure 19.2: Excerpts of Purify verification tool transcript. Purify has monitored memory allocation during execution and has detected buffer array out of bounds errors. Figure 19.3: States of a memory location for dynamic memory analysis (adapted from Hastings and Joyce [HJ92]). Figure 19.4: Threads accessing the same shared variable with different locks. (Adapted from Savage et al. [SBN+97]) Figure 19.5: The state transition diagram for lockset analysis with multiple read accesses. Figure 19.6: A Java method for inserting a node into an AVL tree [Wei07]. Figure 19.7: A sample set of predicate patterns implemented by the Daikon behavior analysis tool. Figure 19.8: Two test cases for method insert of Figure 19.6. testCaseSingleValues inserts 5, 2, and 7 in this order; testCaseRandom inserts 300 randomly generated integer values. Figure 19.9: The behavioral models for method insert of Figure 19.6. The model was obtained using Daikon with test cases testCaseSingleValues and testCaseRandom shown in Figure 19.8.

Chapter 20: Planning and Monitoring the Process Figure 20.1: Three possible simple schedules with different risks and resource allocation. The bars indicate the duration of the tasks. Diamonds indicate milestones, and arrows between bars indicate precedence between tasks. Figure 20.2: Initial schedule for quality activities in development of the business logic subsystem of the Chipmunk Web presence, presented as a GANTT diagram. Figure 20.3: A typical distribution of faults for system builds through time.

Chapter 21: Integration and Component-based Software Testing Figure 21.1: An excerpt of the class diagram of the Chipmunk Web presence. Modules are sorted from the top to the bottom according to the use/include relation. The topmost modules are not used or included in any other module, while the bottom-most modules do not include or use other modules.

Chapter 22: System, Acceptance, and Regression Testing Figure 22.1: C function cgi_decode version 1.0. The C function cgi_decode translates a cgi-encoded string to a plain ASCII string, reversing the encoding applied by the common gateway interface of most Web servers. Repeated from Figure 12.1 in Chapter 12. Figure 22.2: Version 2.0 of the C function cgi_decode adds a control on hexadecimal escape sequences to reveal incorrect escape sequences at the end of the input string and a new branch to deal with non-ASCII characters. Figure 22.3: Paths covered by the structural test cases derived for version 1.0 of function cgi_decode. Paths are given referring to the nodes of the control flow graph of Figure 22.4. Figure 22.4: The control flow graph of function cgi_decode version 2.0. Gray background indicates the changes from the former version. Figure 22.5: Definitions and uses introduced by changes in cgi_decode. Labels refer to the nodes in the control flow graph of Figure 22.4. Figure 22.6: A flow graph model of the specification of the shipping order functionality presented in Chapter 14, augmented with the “restricted country” requirement. The changes in the flow graph are indicated in black.

Chapter 23: Automating Analysis and Test Figure 23.1: Visualization tools can summarize non-local information to facilitate understanding and navigation. The CodeCrawler tool, shown here, uses color, width, and height to represent three static measures of size (number of attributes, number of methods, and lines of code) with connections representing inheritance relations.

Chapter 24: Documenting Analysis and Test Figure 24.1: Sample document naming conventions, compliant with IEEE standards.

List of Tables

Chapter 11: Combinatorial Testing Table 11.1: Categories and value classes derived with the category-partition method from the specification of Figure 11.1 Table 11.2: An excerpt of test case specifications derived from the value classes given in Table 11.1 Table 11.3: Parameters and values controlling Chipmunk Web site display Table 11.4: Covering all pairs of value classes for three parameters by extending the cross-product of two parameters Table 11.5: Covering all pairs of value classes for the five parameters Table 11.6: Pairs of tables that indicate valid value classes for the Chipmunk Web site display Table 11.7: Part of a simple test catalog. Table 11.8: Summary table: Test case specifications for cgi decode generated with a catalog.

Chapter 12: Structural Testing Table 12.1: Sample test suites for C function cgi decode from Figure 12.1

Chapter 13: Data Flow Testing Table 13.1: Definitions and uses for C function cgi decode. eptr and dptr indicate the strings, while eptr and dptr indicate the indexes. Table 13.2: DU pairs for C function cgi_decode. Variable Hex_Values does not appear because it is not defined (modified) within the procedure.

Chapter 14: Model-Based Testing Table 14.1: A test suite satisfying the transition coverage criterion with respect to the finite state machine of Figure 14.2

Chapter 15: Testing Object-Oriented Software Table 15.1: A set of test cases that satisfies the transition coverage criterion for the statechart of Figure 15.6. Table 15.2: A test suite that satisfies the simple transition coverage adequacy criterion for the statechart of Figure 15.8. Transitions are indicated without parameters for simplicity. Table 15.3: Equivalent and nonequivalent scenarios (invocation sequences) for test case TCE from Table 15.1 for class Model. Table 15.4: A set of test case specifications that cover all pairwise combinations of the possible polymorphic bindings of Account, Credit, and creditCard. Table 15.5: Testing history for class LineItem Table 15.6: Testing history for class CompositeItem. New test sets are marked with a prime.

Chapter 20: Planning and Monitoring the Process Table 20.1: Standard severity levels for root cause analysis (RCA).

Chapter 21: Integration and Component-based Software Testing Table 21.1: Integration faults.

List of Sidebars

Chapter 1: Software Test and Analysis in a Nutshell Why Combine Techniques?

Chapter 2: A Framework for Test and Analysis A Note on Terminology

Chapter 4: Test and Analysis Activities Within a Software Process Excerpt of Web Presence Feasibility Study

Chapter 5: Finite Models Graph Representations Duals

Chapter 8: Finite State Verification The Promela Modeling Language Safety and Liveness Properties An Illustration of State Space Explosion

Chapter 9: Test Case Selection and Adequacy Testing Terms

Chapter 10: Functional Testing Functional vs. Structural Testing Units and Features

Chapter 11: Combinatorial Testing Identifying and Bounding Variation

Chapter 14: Model-Based Testing Terminology: Predicates and Conditions

Chapter 15: Testing Object-Oriented Software Summary: Relevant Characteristics of Object-Oriented Software Steps in Object-Oriented Software Testing From Informal Specs to Transition Coverage Dependence

Chapter 16: Fault-Based Testing Fault-Based Testing: Terminology Mutation Analysis: Terminology Mutation Analysis vs. Structural Testing Estimating Population Sizes Hardware Fault-based Testing

Chapter 18: Inspection Social and Educational Benefits of Inspection Java Checklist: Level 1 inspection (single-pass read-through, context independent) Java Checklist: Level 2 inspection (comprehensive review in context) TEST PLAN CHECKLIST: Comprehensive review in context

Chapter 19: Program Analysis Concurrency Faults Memory Faults

Chapter 20: Planning and Monitoring the Process Cleanroom SRET Extreme Programming (XP) Risk Management in the Quality Plan: Risks Generic to Process Management Risk Management in the Quality Plan: Risks Specific to Quality Management ODC Classification of Triggers Listed by Activity ODC Classification of Customer Impact ODC Classification of Defect Types for Targets Design and Code The 80/20 or Pareto Rule

Chapter 21: Integration and Component-based Software Testing Memory Leaks Terminology for Components and Frameworks

Chapter 22: System, Acceptance, and Regression Testing System, Acceptance, and Regression Testing Unit, Integration, and System Testing Web Content Accessibility Guidelines (WCAG)

Chapter 23: Automating Analysis and Test Cyclomatic Complexity ISO/IEC 9126 Properties

Chapter 24: Documenting Analysis and Test Chipmunk Document Template Document Title An Excerpt of the Chipmunk Analysis and Test Strategy A Standard Organization of an Analysis and Test Plan Functional Test Design Specification of check configuration Test Case Specification for check configuration

References

^{^} [email protected] (kupdf.net)

Source URL: Read More
The public content above was dynamically discovered – by graded relevancy to this site’s keyword domain name. Such discovery was by systematic attempts to filter for “Creative Commons“ re-use licensing and/or by Press Release distributions. “Source URL” states the content’s owner and/or publisher. When possible, this site references the content above to generate its value-add, the dynamic sentimental analysis below, which allows us to research global sentiments across a multitude of topics related to this site’s specific keyword domain name. Additionally, when possible, this site references the content above to provide on-demand (multilingual) translations and/or to power its “Read Article to Me” feature, which reads the content aloud to visitors. Where applicable, this site also auto-generates a “References” section, which appends the content above by listing all mentioned links. Views expressed in the content above are solely those of the author(s). We do not endorse, offer to sell, promote, recommend, or, otherwise, make any statement about the content above. We reference the content above for your “reading” entertainment purposes only. Review “DMCA & Terms”, at the bottom of this site, for terms of your access and use as well as for applicable DMCA take-down request.

Acquire this Domain
You can acquire this site’s domain name! We have nurtured its online marketing value by systematically curating this site by the domain’s relevant keywords. Explore our content network – you can advertise on each or rent vs. buy the domain. Buy@TLDtraders.com | Skype: TLDtraders | +1 (475) BUY-NAME (289 – 6263). Thousands search by this site’s exact keyword domain name! Most are sent here because search engines often love the keyword. This domain can be your 24/7 lead generator! If you own it, you could capture a large amount of online traffic for your niche. Stop wasting money on ads. Instead, buy this domain to gain a long-term marketing asset. If you can’t afford to buy then you can rent the domain.

About Us
We are Internet Investors, Developers, and Franchisers – operating a content network of several thousand sites while federating 100+ eCommerce and SaaS startups. With our proprietary “inverted incubation” model, we leverage a portfolio of $100M in valued domains to impact online trends, traffic, and transactions. We use robotic process automation, machine learning, and other proprietary approaches to power our content network. Contact us to learn how we can help you with your online marketing and/or site maintenance.

1 2

Categories:Pairing Companies

Pairing.us

Software Testing and Analysis Process Principles and Techniques

References

400 Bad Request

Sentiment Analysis

400 Bad Request

Emotions Detected

References

400 Bad Request

Sentiment Analysis

400 Bad Request

Emotions Detected

Share