You are on page 1of 722

Foundations of Software Testing 2E

Part I

Chapter 1 Chapter 2

Part II

Chapter 3 Chapter 4 Chapter 5 Chapter 6

Part III

Chapter 7 Chapter 8

Part IV

Chapter 9 Chapter 10 Chapter 11

Updated: July 21, 2013
Foundations of Software Testing 2E

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

ADITYA P. MATHUR

Contents
Author: Aditya P. Mathur

1

Chapter 1:

Updated: July 17, 2013

Foundations of Software Testing 2E

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Preliminaries: Software Testing

Contents
Author: Aditya P. Mathur

2

Learning Objectives
Errors, Testing, debugging, test process, CFG, correctness, reliability,

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

n 

oracles.

n 

Finite state machines

n 

Testing techniques

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

3

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

1.1 Humans, errors and testing

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

4

Errors
Errors are a part of our daily life.

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Humans make errors in their thoughts, actions, and in the products that
might result from their

actions.

Errors occur wherever humans are involved in taking actions and making
decisions.

These fundamental facts of human existence
make testing an essential activity.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

5

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Errors: Examples

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

6

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Error, faults, failures

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

7

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

1.2 Software Quality

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

8

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Software quality

Static quality attributes: structured, maintainable, testable code as well as
the availability of correct and complete documentation.

Dynamic quality attributes: software reliability, correctness,
completeness, consistency, usability, and performance

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

9

Software quality (contd.)

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Completeness refers to the availability of all features listed in the requirements,
or in the user manual. An incomplete software is one that does not fully
implement all features required.

Consistency refers to adherence to a common set of conventions and
assumptions. For example, all buttons in the user interface might follow a
common color coding convention. An example of inconsistency would be when
a database application displays the date of birth of a person in the database.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

10

Software quality (contd.)
Usability refers to the ease with which an application can be used. This is an
Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

area in itself and there exist techniques for usability testing. Psychology plays
an important role in the design of techniques for usability testing.

Performance refers to the time the application takes to perform a requested
task. It is considered as a non-functional requirement. It is specified in terms
such as ``This task must be performed at the rate of X units of activity in one
second on a machine running at speed Y, having Z gigabytes of memory."

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

11

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

12

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

1.3 Requirements, behavior, and correctness

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Requirements, behavior, correctness

Requirements leading to two different programs:

Requirement 1: It is required to write a

program that inputs two integers and outputs the maximum of these.

Requirement 2: It is required to write a

program that inputs a sequence of integers and outputs the sorted version of
this sequence.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

13

Requirements: Incompleteness

of max when the input integers are 13 and 19 can be easily determined to be 19.

Suppose now that the tester wants to know if the two integers are to be input to the
program on one line followed by a carriage return, or on two separate lines with a
carriage return typed in after each number. The requirement as stated above fails to
provide an answer to this question.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

14

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Suppose that program max is developed to satisfy Requirement 1. The expected output

written to satisfy this requirement. Ltd Requirements: Ambiguity . The behavior of sort program. Mathur 15 Copyright © 2013 Dorling Kindersley (India) Pvt. It is not clear whether the input sequence is to sorted in ascending or in descending order. Contents Foundations of Software Testing 2E Author: Aditya P.Requirement 2 is ambiguous. will depend on the decision taken by the programmer while writing sort.

768 till 32. Mathur 16 Copyright © 2013 Dorling Kindersley (India) Pvt.The set of all possible inputs to a program P is known as the input domain or input space. Ltd Input domain (Input space) . Using Requirement 1 above we find the input domain of max to be the set of all pairs of integers where each element in the pair integers is in the range -32. Contents Foundations of Software Testing 2E Author: Aditya P. Using Requirement 2 it is not possible to find the input domain for the sort program.767. of P.

Mathur 17 . Contents Foundations of Software Testing 2E Author: Aditya P. The order of the output sequence is determined by an input request character which should be ``A'' when an ascending sequence is desired. Ltd It is required to write a program that inputs a sequence of integers and outputs the integers in this sequence sorted in either ascending or descending order. and ``D'' otherwise. While providing input to the program. the sequence is terminated with a period. the request character is input first followed by the sequence of integers to be sorted.Input domain (Continued) Modified Requirement 2: Copyright © 2013 Dorling Kindersley (India) Pvt.

Ltd Input domain (Continued) . Mathur 18 Copyright © 2013 Dorling Kindersley (India) Pvt. The first element of the pair is a character.Based on the above modified requirement. Contents Foundations of Software Testing 2E Author: Aditya P. the input domain for sort is a set of pairs. The second element of the pair is a sequence of zero or more integers ending with a period.

Any character other than ``A'’ and ``D'' is considered as invalid input to sort. Mathur 19 . Ltd request characters can be ``A'' and ``D''.Valid/Invalid Inputs The modified requirement for sort mentions that the Copyright © 2013 Dorling Kindersley (India) Pvt. but fails to answer the question ``What if the user types a different character ?’’ When using sort it is certainly possible for the user to type a character other than ``A'' and ``D''. The requirement for sort does not specify what action it should take when an invalid input is encountered. Contents Foundations of Software Testing 2E Author: Aditya P.

Ltd 1.4 Correctness versus reliability Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 20 .

it is almost . Ltd Though correctness of a program is desirable. Mathur 21 Copyright © 2013 Dorling Kindersley (India) Pvt. Thus. Contents Foundations of Software Testing 2E Author: Aditya P.Correctness never the objective of testing. correctness is established via mathematical proofs of programs. To establish correctness via testing would imply testing a program on all elements in the input domain. In most cases that are encountered in practice. this is impossible to accomplish.

testing attempts to find if there are any errors in it. and the error removal processes together increase our confidence in the correct functioning of the program under test. Mathur 22 . Ltd While correctness attempts to establish that the program is error free.Correctness and Testing Copyright © 2013 Dorling Kindersley (India) Pvt. Thus. Contents Foundations of Software Testing 2E Author: Aditya P. completeness of testing does not necessarily demonstrate that a program is error free. debugging. Testing.

Software reliability is the probability of failure free operation of software in its intended environment. Ltd Software reliability: two definitions Software reliability [ANSI/IEEE Std 729-1983]: is the probability of failure free operation of software over a given time interval and under given conditions.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 23 . Contents Foundations of Software Testing 2E Author: Aditya P.

allows any one of two types of input sequences. Contents Foundations of Software Testing 2E Author: Aditya P.Operational profile Copyright © 2013 Dorling Kindersley (India) Pvt. on any given execution. Ltd An operational profile is a numerical description of how a program is used. Mathur 24 . Consider a sort program which. Sample operational profiles for sort follow.

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Operational profile Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 25 .

Mathur 26 . Ltd Operational profile Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.

Ltd 1. Mathur 27 .5 Testing and debugging Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.

When testing reveals an error. is known as debugging.Testing is the process of determining if a program has any errors. Mathur 28 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Testing and debugging . the process used to determine the cause of this error and to remove it. Contents Foundations of Software Testing 2E Author: Aditya P.

Mathur 29 . Ltd A test/debug cycle Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 30 Copyright © 2013 Dorling Kindersley (India) Pvt. . Specifically.Test plan Example: The sort program is to be tested to meet the requirements given earlier. the following needs to be done. Ltd A test cycle is often guided by a test plan. •  Execute sort on at least two input sequences. one with ``A'' and the other with ``D'' as request characters. Contents Foundations of Software Testing 2E Author: Aditya P.

•  All failures of the test program should be recorded in a suitable file using the Company Failure Report Form. •  Test the program for robustness against erroneous inputs such as ``R'' Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Test plan (contd.•  Execute the program on an empty input sequence.) typed in as the request character. Mathur 31 . Contents Foundations of Software Testing 2E Author: Aditya P.

one for each input variable. A test set is a collection of zero or more test cases. Mathur 32 . Sample test case for sort: Test data: <''A'’ 12 -29 32 > Expected output: -29 12 32 Contents Foundations of Software Testing 2E Author: Aditya P.Test case/data A test case is a pair consisting of test data to be input to the program and the Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd expected output. The test data is a set of values.

formal mathematical specification. Mathur 33 . Contents Foundations of Software Testing 2E Author: Aditya P. A state diagram specifies program states and how the program changes its state on an input sequence.Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Program behavior Can be specified in several ways: plain natural language. etc. a state diagram. inputs.

Mathur 34 . Ltd Consider a menu driven application.Program behavior: Example Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P.

) Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Program behavior: Example (contd. Mathur 35 .

Mathur 36 .Behavior: observation and analysis Copyright © 2013 Dorling Kindersley (India) Pvt. In the second step one analyzes the observed behavior to check if it is correct or not. Ltd In the first step one observes the behavior. Contents Foundations of Software Testing 2E Author: Aditya P. The entity that performs the task of checking the correctness of the observed behavior is known as an oracle. Both these steps could be quite complex for large commercial programs.

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Oracle: Example Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 37 .

one might use a matrix multiplication program to check if a matrix inversion program has produced the correct output. the matrix inversion program inverts a given matrix A and generates B as the output matrix. In this case. Ltd Oracles can also be programs designed to check the behavior of other programs.Oracle: Programs Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. For example. Mathur 38 .

Contents Foundations of Software Testing 2E Author: Aditya P. such as the one to check a matrix multiplication program or a sort program. Ltd Oracle: Construction Construction of automated oracles.Copyright © 2013 Dorling Kindersley (India) Pvt. the construction of automated oracles is a complex undertaking. In general. Mathur 39 . requires the determination of inputoutput relationship.

Ltd Oracle construction: Example Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 40 .

Program verification and testing are best considered as complementary techniques.Program verification aims at proving the correctness of programs by showing that it contains no errors. Ltd Testing and verification . program verification is often avoided. Contents Foundations of Software Testing 2E Author: Aditya P. This is very different from testing that aims at uncovering errors in a program. and the focus is on testing. Mathur 41 Copyright © 2013 Dorling Kindersley (India) Pvt. In practice.

the person/tool who verified a program might have made a mistake in the verification process. Mathur 42 Copyright © 2013 Dorling Kindersley (India) Pvt.) despite the success of a set of tests. and so on. Verified and published programs have been shown to be incorrect. incorrect assumptions might be made regarding the components that interface with the program. Ltd Testing is not a perfect technique in that a program might contain errors .Testing and verification (contd. Contents Foundations of Software Testing 2E Author: Aditya P. Verification promises to verify that a program is free from errors. there might be an incorrect assumption on the input conditions. However.

Ltd 1.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 43 . Test generation strategies Contents Foundations of Software Testing 2E Author: Aditya P.10.

Contents Foundations of Software Testing 2E Author: Aditya P. In more advanced test processes. requirements serve as a source for the development of formal models. Ltd Any form of test generation uses a source document. the process is a bit more formal. The tests are generated using a mix of formal and informal methods either directly from the requirements document serving as the source. Mathur 44 .Test generation Copyright © 2013 Dorling Kindersley (India) Pvt. the source document resides in the mind of the tester who generates tests based on a knowledge of the requirements. In the most informal of test methods. In several commercial environments.

Specification based: require that a subset of the requirements be modeled using a formal mathematical notation. Mathur 45 . Timed automata. etc. Ltd Model based: require that a subset of the requirements be modeled using a formal notation (usually graphical). Examples: B. Petri net. and Larch.Test generation strategies Copyright © 2013 Dorling Kindersley (India) Pvt. Models: Finite State Machines. Contents Foundations of Software Testing 2E Author: Aditya P. Code based: generate tests directly from the code. Z.

Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 46 . Ltd Test generation strategies (Summary) Contents Foundations of Software Testing 2E Author: Aditya P.

13 Types of software testing Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd 1. Mathur 47 .

Mathur 48 . Ltd One possible classification is based on the following four classifiers: C1: Source of test generation. C2: Lifecycle phase in which testing takes place C3: Goal of a specific testing activity C4: Characteristics of the artifact under test Contents Foundations of Software Testing 2E Author: Aditya P.Types of testing Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 49 . Ltd C1: Source of test generation Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.

Ltd C2: Lifecycle phase Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 50 .

Mathur 51 .Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd C3: Goal of specific testing activity Contents Foundations of Software Testing 2E Author: Aditya P.

Ltd C4: Artifact under test Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 52 .Copyright © 2013 Dorling Kindersley (India) Pvt.

Ltd Summary We have dealt with some of the most basic concepts in software testing. Exercises at the end of Chapter 1 are to help you sharpen your understanding. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 53 .Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 54 . 2013 Foundations of Software Testing 2E Contents Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Chapter 2: Preliminaries: Mathematical Updated: July 12.

1 Predicates and Boolean expressions Contents Foundations of Software Testing 2E Author: Aditya P. Ltd 2.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 55 .

1997. “Specification based testing using cause-effect graphs. Tai. Here is an example from Paradkar. Mathur 56 . and Vouk. Ltd Where do predicates arise? Predicates arise from requirements in a variety of applications. A boiler needs to be to be shut down when the following conditions hold: Contents Foundations of Software Testing 2E Author: Aditya P.” V 4. Annals of Software Engineering.Copyright © 2013 Dorling Kindersley (India) Pvt. pp 133-157.

  The water level in the boiler is above Y lbs.  The water level in the boiler is below X lbs.Boiler shutdown conditions 2. Mathur 57 Copyright © 2013 Dorling Kindersley (India) Pvt. (c) 4.  A water pump has failed. 5. (d) Boiler in degraded mode when either is true. (e) The boiler is to be shut down when a or b is true or the boiler is in degraded mode and the steam meter fails. We combine these five conditions to form a compound condition (predicate) for boiler shutdown.  Steam meter has failed. (a) . (b) 3. Ltd 1.  A pump monitor has failed. Contents Foundations of Software Testing 2E Author: Aditya P.

we obtain the following Boolean expression E that when true must force a boiler shutdown: E=a+b+(c+d)e where the + sign indicates “OR” and a multiplication indicates “AND. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 58 . Ltd Denoting the five conditions above as a through e.” The goal of predicate-based test generation is to generate tests from a predicate p that guarantee the detection of any error that belongs to a class of errors in the coding of p.Boiler shutdown conditions Copyright © 2013 Dorling Kindersley (India) Pvt.

The following predicate represents the condition part of the statement. also known as a Boolean expression. Ltd A condition is represented formally as a predicate. Mathur 59 Copyright © 2013 Dorling Kindersley (India) Pvt. .Another example For example. consider the requirement ``if the printer is ON and has paper then send document to printer.” This statement consists of a condition part and an action part. pr: (printer_status=ON) ∧ (printer_tray!= empty) Contents Foundations of Software Testing 2E Author: Aditya P.

Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Test generation from predicates . Mathur 60 Copyright © 2013 Dorling Kindersley (India) Pvt. Conditions guard actions.We will now examine two techniques. The conditions from which tests are generated might arise from requirements or might be embedded in the program to be tested. For example. if condition then action is a typical format of many functional requirements. named BOR and BRO for generating tests that are guaranteed to detect certain faults in the coding of conditions.

≤. ≠. (gender==“female”∧age>65) Contents Foundations of Software Testing 2E Author: Aditya P. a+b<c) e1 and e2 are expressions whose values can be compared using relop. OR. >. Relational expression: e1 relop e2. Boolean operators (bop): {!. (x<0) Compound predicate: Join one or more simple predicates using bop.Predicates Relational operators (relop): {<. Simple predicate: A Boolean variable or a relational expression. Ltd = and == are equivalent. xor} also known as {not. AND. Mathur 61 . (e.g.∨. =.∧.} Copyright © 2013 Dorling Kindersley (India) Pvt. ≥. XOR}.

e. in (a∧b∨!c) Contents Foundations of Software Testing 2E Author: Aditya P. Singular Boolean expression: When each literal appears only once. Ltd Boolean expressions . b. Mathur 62 Copyright © 2013 Dorling Kindersley (India) Pvt. Negation is also denoted by placing a bar over a Boolean expression such as in (a ∧ b) We also write ab for a∧b and a+b for a∨b when there is no confusion. and c are also known as literals.Boolean expression: one or more Boolean variables joined by bop. (a∧b∨!c) a.g..

Mathur 63 .g. (p q) +(rs) + (a c). Ltd Disjunctive normal form (DNF): Sum of product terms: e.g. e.. CNF: (p+!r)(p+s)(q+!r)(q+s) is equivalent to DNF: (pq+!rs) Contents Foundations of Software Testing 2E Author: Aditya P.: (p+q)(r+s)(a+c) Any Boolean expression in DNF can be converted to an equivalent CNF and vice versa.Boolean expressions (contd. Conjunctive normal form (CNF): Product of sums: e.g.) Copyright © 2013 Dorling Kindersley (India) Pvt.

then ei is considered singular only if it is non-singular and mutually singular with the remaining elements of E.Mutually singular: Boolean expressions e1 and e2 are mutually singular when they do not share any literal. If expression E contains components e1... Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 64 Copyright © 2013 Dorling Kindersley (India) Pvt. e2.) . Ltd Boolean expressions (contd.

< (a+b) ! c p Leaf nodes Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Boolean expressions: Syntax tree representation Root node (AND-node) Notice that internal nodes are labeled by ∧ Boolean and relational operators Root node: OR-node is labeled as ∨. Mathur 65 . Copyright © 2013 Dorling Kindersley (India) Pvt.Abstract syntax tree (AST) for: (a+b)<c ∧!p.

Mathur 66 .2 Program representation: Control flow graphs Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd 2.

Ltd Program representation: Basic blocks . The entry and exit points of a basic block coincide when the block contains only one statement. Control always enters a basic block at its entry point and exits from its exit point. Contents Foundations of Software Testing 2E Author: Aditya P.A basic block in program P is a sequence of consecutive statements with a single entry and a single exit point. Mathur 67 Copyright © 2013 Dorling Kindersley (India) Pvt. There is no possibility of exit or a halt at any point inside the basic block except at its exit point. Thus. a block has unique entry and exit points.

Ltd Example: Computing x raised to y Contents Foundations of Software Testing 2E Author: Aditya P.Basic blocks: Example Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 68 .

) Copyright © 2013 Dorling Kindersley (India) Pvt.Basic blocks: Example (contd. Mathur 69 . Ltd Basic blocks Contents Foundations of Software Testing 2E Author: Aditya P.

A control flow graph (or flow graph) G is defined as a finite set N of nodes and a finite set E of edges. We often write G= (N. j) in E connects two nodes ni and nj in N. An edge (i. Ltd Control Flow Graph (CFG) . Contents Foundations of Software Testing 2E Author: Aditya P. E) to denote a flow graph G with nodes given by N and edges by E. Mathur 70 Copyright © 2013 Dorling Kindersley (India) Pvt.

that has no outgoing edge. Contents Foundations of Software Testing 2E Author: Aditya P. also in N. j) connecting basic blocks bi and bj implies that control can go from block bi to block bj. Ltd In a flow graph of a program. and another node labeled End. Blocks and nodes are labeled such that block bi corresponds to node ni. Mathur 71 Copyright © 2013 Dorling Kindersley (India) Pvt. each basic block becomes a node and edges are used to . We also assume that there is a node labeled Start in N that has no incoming edge. An edge (i.Control Flow Graph (CFG) indicate the flow of control between blocks.

4). Mathur 72 . (2. Ltd CFG Example N={Start. 2. 7. (3. 5). (4. (1. 9). (1. 6. 6). (7. (7.4). 5). 3. 7). 4. End)} Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. (6. End} E={(Start.1). (5. 2). 5. 8. 9. 1. (5. (9. 3). 8).

9. (1. 7. 4).CFG Example Copyright © 2013 Dorling Kindersley (India) Pvt. 1. 7). 5). (9. Mathur 73 . 3). N={Start. 5). (2. (5. (6.1). 9). 8). 8. (1. 6). 3. 2).4). (4. 4. (7. 2. (3. 6. (5. 5. (7. Ltd Same CFG with statements removed. End} E={(Start. End)} Contents Foundations of Software Testing 2E Author: Aditya P.

nr. k>0. E). Ltd Consider a flow graph G= (N. … e_k) .Paths Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 74 . denotes a path of length k through the flow graph if the following sequence condition holds. } Contents Foundations of Software Testing 2E Author: Aditya P. (e_1. nq) and ei+1 = (nr. and 0< i<k. A sequence of k edges. e_2. Given that np. ns) then nq = nr. and ns are nodes belonging to N. if ei = (np. nq.

(1. 5. 7. End)) Bold edges: complete path. End) p2= (Start. (6. 1). (2. (7. Mathur 75 . 9). (5. 1.Paths: sample paths through the exponentiation flow graph Copyright © 2013 Dorling Kindersley (India) Pvt. (4. 4. (5. 9. End) Specified unambiguously using edges: p1= ( (Start. 2). 4). 2. (9. 5. 5). 5. 5. 7. 3. 7). Dashed edges: subpath. 4. 6). Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Two feasible and complete paths: p1= ( Start. 1. 6. 5). 9. 6.

5.Paths: infeasible Copyright © 2013 Dorling Kindersley (India) Pvt. End) p2= (Start. 9. Ltd A path p through a flow graph for program P is considered feasible if there exists at least one test case which when input to P causes p to be traversed. 2. 6. Mathur 76 . 1. 1. 7. 5. 4. End) Contents Foundations of Software Testing 2E Author: Aditya P. p1= ( Start. 3. 7. 1. 5. . 4. 8. 9.

Each additional condition in the program can increases the number of distinct paths by at least one. conditions can have a multiplicative effect on the number of paths. Ltd There can be many distinct paths through a program. A program with no . Depending on their location.Number of paths condition contains exactly one path that begins at node Start and terminates at node End. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 77 Copyright © 2013 Dorling Kindersley (India) Pvt.

languages. and regular expressions Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 78 .6 Strings. Ltd 2.

AaBc.Strings play an important role in testing. Examples: 1011. a set of all strings consisting of zeros and ones is the language of binary numbers. In this section we provide a brief introduction to strings and languages. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Strings . A collection of strings also forms a language. A string serves as a test input. “Hello world”. For example. Mathur 79 Copyright © 2013 Dorling Kindersley (India) Pvt.

Though alphabets can be infinite. 1} is an alphabet consisting of two symbols 0 and 1. Ltd A collection of symbols is known as an alphabet. Another alphabet is Y={dog.Alphabet Copyright © 2013 Dorling Kindersley (India) Pvt. X={0. Mathur 80 . horse. and ``lion". Contents Foundations of Software Testing 2E Author: Aditya P. lion}that consists of four symbols ``dog". We use an upper case letter such as X and Y to denote alphabets. ``horse". we are concerned only with finite alphabets. ``cat". For example. cat.

lion}. Mathur 81 . horse. Also. Ltd A string over an alphabet X is any sequence of zero or more symbols that belong to X. A string of length 0. |1011|=4 and |dog cat dog|=3.Strings over an Alphabet Copyright © 2013 Dorling Kindersley (India) Pvt. is denoted by ε. Foundations of Software Testing 2E Contents Author: Aditya P. Given a string s. 1}. For example. 0110 is a string over the alphabet {0. cat. we denote its length by |s|. r to denote strings. Thus. We will use lower case letters such as p. Note that ε denotes an empty string and also stands for “element of” when used with sets. also known as an empty string. dog cat dog dog lion is a string over the alphabet {dog. q. The length of a string is the number of symbols in that string.

For example.s2 to denote the concatenation of strings s1 and s2. Ltd String concatenation . for any string s.Let s1 and s2 be two strings over alphabet X. and two strings 011 and 101 over X. 1}. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 82 Copyright © 2013 Dorling Kindersley (India) Pvt.s=s. We write s1. given the alphabet X={0.101=011101. It is easy to see that |s1. ε =s and ε. Also. we have s.s2|=|s1|+|s2|. we obtain 011.

A language can be finite or infinite. Ltd A set L of strings over an alphabet X is known as a language. 0101}: A language containing three strings Contents Foundations of Software Testing 2E Author: Aditya P. 11. The following sets are finite languages over the binary alphabet {0. Mathur 83 .Languages Copyright © 2013 Dorling Kindersley (India) Pvt. 1}: ∅: The empty set {ε}: A language consisting only of one string of length zero {00.

Let r1 and r2 be two regular expressions over the alphabet X that denote. Then r1.r2 is a regular expression that denotes the set L1. the following are regular expressions over X: If a belongs to X. Contents Foundations of Software Testing 2E Author: Aditya P.Given a finite alphabet X. Ltd Regular expressions . respectively.L2. Mathur 84 Copyright © 2013 Dorling Kindersley (India) Pvt. sets L1 and L2. then a is a regular expression that denotes the set {a}.

Mathur 85 Copyright © 2013 Dorling Kindersley (India) Pvt. If r1 and r2 are regular expressions that denote. then r1r2 is also a regular expression that denotes the set L1 ∪ L2. Contents Foundations of Software Testing 2E Author: Aditya P. sets L1 and L2. If r denotes the set L then r* denotes the set {ε}∪ L+.) . respectively. is a regular expression.If r is a regular expression that denotes the set L then r+ is a regular expression that denotes the set obtained by concatenating L with itself one or more times also written as L+ Also. r* known as the Kleene closure of r. Ltd Regular expressions (contd.

Exercises at the end of Chapter 2 will help you sharpen your understanding. Mathur 86 . Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Summary We have introduced mathematical preliminaries an understanding of which will be useful while you go through the remaining parts of this book.

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Chapter 3 Domain Partitioning Updated: July 12. 2013 Foundations of Software Testing 2E Contents Author: Aditya P. Mathur 87 .

Cause effect graphing has been omitted from these slides. Mathur 88 . Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Learning Objectives Essential black-box techniques for generating tests for functional testing.§  Equivalence class partitioning §  Boundary value analysis Copyright © 2013 Dorling Kindersley (India) Pvt.

These techniques are useful during functional testing where the objective is to test whether or not an application. system. Mathur 89 . Ltd Test generation techniques described in this chapter belong to the black-box testing category. correctly implements the functionality as per the given requirements Contents Foundations of Software Testing 2E Author: Aditya P.Applications of test generation techniques Copyright © 2013 Dorling Kindersley (India) Pvt. or subsystem. unit.

Mathur 90 Copyright © 2013 Dorling Kindersley (India) Pvt. A Practitioners Guide to software Test Design Test Design Test Case Spec. Ltd Functional Testing: Test Documents (IEEE829 Standard) . Test Procedure Test incident Test log Test item transmittal report report Test summary Test generation techniques report Contents Foundations of Software Testing 2E Author: Aditya P. Spec.Requirements Test Plan Model Reference: Lee Copland.

Foundations of Software Testing 2E Contents Author: Aditya P. items to be Copyright © 2013 Dorling Kindersley (India) Pvt.Functional Testing: Documents Test Plan: Describe scope. Ltd tested. resources. Test design spec: Identifies a subset of features to be tested and identifies the test cases to test the features in this subset. Dependencies with other test cases are specified here. Test case spec: Lists inputs. Each test case has a unique ID for reference in other documents. setting of environment variables and test procedures. approvals needed. approach. Could be used at the system test level or at lower levels. expected outputs. responsibilities. deliverables. Mathur 91 . test schedule. features to be tested by this test case.g. and any other special requirements e.

Test log: A log observations during the execution of a test.g. a database. Ltd Test procedure spec: Describe the procedure for executing a test case. Test summary: Summarize the results of testing activities and provide an evaluation.Functional Testing: Documents (contd) Copyright © 2013 Dorling Kindersley (India) Pvt. Test incident report: Document any special event that is recommended for further investigation. Test transmittal report: Identifies the test items being provided for testing. e. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 92 .

and category partitioning. boundary value analysis. Each of these test generation techniques is black-box and useful for generating test cases during functional testing. Mathur 93 . Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Test generation techniques in this chapter Three techniques are considered: equivalence partitioning.

Ltd 3. Mathur 94 .2 The test selection problem Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 95 . sequence diagrams. Ltd Requirements serve as the starting point for the generation of tests. are then specified rigorously using modeling elements such as use cases. S. more aptly ideas.Requirements and test generation Copyright © 2013 Dorling Kindersley (India) Pvt. and RSML. requirements may exist only in the minds of one or more people. Rigorously specified requirements are often transformed into formal requirements using requirements specification languages such as Z. During the initial phases of development. Contents Foundations of Software Testing 2E Author: Aditya P. These requirements. and statecharts in UML.

Mathur 96 .Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Test generation techniques Contents Foundations of Software Testing 2E Author: Aditya P.

Copyright © 2013 Dorling Kindersley (India) Pvt. However. Mathur 97 . The test selection problem is to select a subset T of tests such that execution of P against each element of T will reveal all errors in P. there are heuristics and model based methods that can be used to generate tests that will reveal certain type of faults. In general there does not exist any algorithm to construct such a test set. Ltd Test selection problem Let D denote the input domain of a program P. Contents Foundations of Software Testing 2E Author: Aditya P.

Copyright © 2013 Dorling Kindersley (India) Pvt. The problem of test selection is difficult due primarily to the size and complexity of the input domain of P. Contents Foundations of Software Testing 2E Author: Aditya P.) The challenge is to construct a test set T⊆D that will reveal as many errors in P as possible. Mathur 98 . Ltd Test selection problem (contd.

Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Exhaustive testing The large size of the input domain prevents a tester from exhaustively testing the program under test against all possible inputs.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 99 . The complexity makes it harder to select individual tests. By ``exhaustive" testing we mean testing the given program against every element in its input domain.

Consider program P that is required to sort a sequence of integers into ascending order. Ltd Large input domain . If there is no limit on the size of the sequence that can be input. Calculate the size of the input domain. Foundations of Software Testing 2E Author: Aditya P. then the input domain of P is infinitely large and P can never be tested exhaustively. Mathur 100 Contents Copyright © 2013 Dorling Kindersley (India) Pvt. then the size of the input domain depends on the value of N. 32767]. Assuming that P will be executed on a machine in which integers range from -32768 to 32767. say Nmax>1. the input domain of P consists of all possible sequences of integers in the range [-32768. If the size of the input sequence is limited to.

assume that the employee record consists of the following items with their respective types and constraints: Calculate the size of the input domain. Ltd Consider a procedure P in a payroll processing system that takes an employee record as input and computes the weekly salary. Foundations of Software Testing 2E Author: Aditya P.Complex input domain Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 101 Contents . For simplicity.

Mathur 102 .Copyright © 2013 Dorling Kindersley (India) Pvt.3 Equivalence partitioning Contents Foundations of Software Testing 2E Author: Aditya P. Ltd 3.

Contents Foundations of Software Testing 2E Author: Aditya P. the sub-domains by definition are disjoint. say N>1. Each subset is known as an equivalence class. In strict mathematical terms. as shown (next slide (a)). Ltd Equivalence partitioning Test selection using equivalence partitioning allows a tester to subdivide the input domain into a relatively small number of sub-domains. Mathur 103 . The four subsets shown in (a) constitute a partition of the input domain while the subsets in (b) are not.Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 104 . Ltd Subdomains Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.

Ltd Program behavior and equivalence classes The equivalence classes are created assuming that the program under test exhibits the same behavior on all elements.e. Mathur 105 . This assumption allow the tester to select exactly one test from each equivalence class resulting in a test suite of exactly N tests. within a class. Contents Foundations of Software Testing 2E Author: Aditya P. i. tests.Copyright © 2013 Dorling Kindersley (India) Pvt.

E3. inputs (U). Contents Foundations of Software Testing 2E Author: Aditya P. and U1. can be further subdivided into subsets on which the application is required to behave differently (e. Each of the two subsets. U2). E1. or legal.The entire set of inputs to any application can be divided into at least two subsets: one containing all the expected. Mathur 106 Copyright © 2013 Dorling Kindersley (India) Pvt.g. or illegal. Ltd Faults targeted . E2. inputs (E) and the other containing all unexpected.

) . Mathur 107 Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P.Equivalence class partitioning selects tests that target any faults in the application that cause it to behave incorrectly when the input is in either of the two classes or their subsets. Ltd Faults targeted (contd.

The set of input values is now divided into a set E containing all integers in the range [1..Example 1 the only legal values of age are in the range [1. Ltd Consider an application A that takes an integer denoted by age as input..120] Contents Foundations of Software Testing 2E Author: Aditya P.120]. Mathur 108 Copyright © 2013 Dorling Kindersley (India) Pvt.. Let us suppose that .120] and a set U containing the remaining integers. All integers Other integers [1.

Thus. Similarly...) . Contents Foundations of Software Testing 2E Author: Aditya P. E is further subdivided into two regions depending on the expected behavior. Mathur 109 Copyright © 2013 Dorling Kindersley (India) Pvt. This leads to a subdivision of U into two categories.61] in accordance with requirement R1 and those in the range [62. Ltd Example 1 (contd. it is expected that all invalid inputs less than or equal to 1 are to be treated in one way while all greater than 120 are to be treated differently. assume that the application is required to process all values in the range [1.Further.120] according to requirement R2.

Mathur 110 .) >120 [1..61] Contents Foundations of Software Testing 2E Author: Aditya P.All integers <1 [62-120] Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Example 1 (contd.

two regions containing expected inputs and two regions containing the unexpected inputs.. Ltd Example 1 (contd. Mathur 111 Copyright © 2013 Dorling Kindersley (India) Pvt.120] will reveal any fault with respect to R2. Similarly. Contents Foundations of Software Testing 2E Author: Aditya P. i. A similar expectation applies to the two regions containing the unexpected inputs.Tests selected using the equivalence partitioning technique aim at targeting faults in the application under test with respect to inputs in any of the four regions.) . It is expected that any single test selected from the range [1.. any test selected from the region [62.e.61] will reveal any fault with respect to R1..

Contents Foundations of Software Testing 2E Author: Aditya P. As is the case with any test selection technique in software testing.The effectiveness of tests generated using equivalence partitioning for testing application A. The effectiveness can be improved through an unambiguous and complete specification of the requirements and carefully selected tests using the equivalence partitioning technique described in the following sections. Mathur 112 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Effectiveness . is judged by the ratio of the number of faults these tests are able to expose to the total faults lurking in A. the effectiveness of tests selected using equivalence partitioning is less than 1 for most practical applications.

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Example 2 This example shows a few ways to define equivalence classes based on the knowledge of requirements and the program text. An exception is raised if there is no file with name f. Mathur 113 . Contents Foundations of Software Testing 2E Author: Aditya P. Consider that wordCount method takes a word w and a filename f as input and returns the number of occurrences of w in the text contained in the file named f.

f)). f if (not exists(f) {raise exception.) String w.Example 2 (contd. examples above. f Input w.} if(length(w)==0)return(0). Ltd begin . Using the partitioning method described in the return(getCount(w. if(empty(f))return(0). return(0). Mathur 114 Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. we obtain the equivalence end classes (next slide).

Ltd Equivalence class Contents Foundations of Software Testing 2E Author: Aditya P. empty Copyright © 2013 Dorling Kindersley (India) Pvt.Example 2 (contd. Mathur 115 . not empty E2 non-null does not exist E3 non-null exists. not empty E5 null does not exist E6 null exists. empty E4 null exists.) w f E1 non-null exists.

Ltd Note that the number of equivalence classes without any knowledge of the program code is 2.) Copyright © 2013 Dorling Kindersley (India) Pvt. and perhaps more. even before the code is available Contents Foundations of Software Testing 2E Author: Aditya P. an experienced tester will likely derive the six equivalence classes given above. Mathur 116 . whereas the number of equivalence classes derived with the knowledge of partial code is 6. Of course.Example 2 (contd.

suppose that a program outputs an integer.Copyright © 2013 Dorling Kindersley (India) Pvt. It is worth asking: ``Does the program ever generate a 0? What are the maximum and minimum possible values of the output?" These two questions lead to two the following equivalence classes based on outputs: Contents Foundations of Software Testing 2E Author: Aditya P. For example. Ltd Equivalence classes based on program output In some cases the equivalence classes are based on the output generated by the program. Mathur 117 .

Ltd Equivalence classes based on program output (contd. E4: All other output values. E2: Output value v is the maximum possible.) E1: Output value v is 0.Copyright © 2013 Dorling Kindersley (India) Pvt. each of the four classes given above might lead to one equivalence class consisting of inputs. Mathur 118 . Thus. Based on the output equivalence classes one may now derive equivalence classes for the inputs. E3: Output value v is the minimum possible. Contents Foundations of Software Testing 2E Author: Aditya P.

{132}} letter:bool {{J}.0 {{-1.Equivalence classes for variables: range Example Constraints Classes Copyright © 2013 Dorling Kindersley (India) Pvt.52}} age: int {{-1}. Ltd Eq.. {3}} Contents Foundations of Software Testing 2E Author: Aditya P. inside the range and {92} two with values outside the range. Mathur 119 . {15.90] {50}.0}. {75}. area: float area≥0. {56}. Classes One class with values speed ∈[60.

Contents Foundations of Software Testing 2E Author: Aditya P. {Sue}. Ltd Equivalence classes for variables: strings Example Constraints Classes firstname: string {{ε}. Mathur 120 . {Loooong Name}} illegal strings based on any constraints.Equivalence Classes At least one containing all legal strings and one all Copyright © 2013 Dorling Kindersley (India) Pvt.

{green}} up:boolean {{true}.} {blue}.Equivalence Classes Constraints Each value in a separate class Copyright © 2013 Dorling Kindersley (India) Pvt. {false}} Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Equivalence classes for variables: enumeration Example Classes autocolor:{red. blue. green} {{red. Mathur 121 .

and one containing a larger than expected array. {[-10. 12. 0. one Copyright © 2013 Dorling Kindersley (India) Pvt. {[-9. Contents Foundations of Software Testing 2E Author: Aditya P.Equivalence Classes Constraints One class containing all legal arrays. 20]}. 15]} containing the empty array. Mathur 122 . Ltd Equivalence classes for variables: arrays Example Classes int [ ] aName: new int[3]. {[ ]}.

Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. or structures. one must consider legal and illegal values for each component of the structure. Mathur 123 . While generating equivalence classes for such inputs. are compound types. The next example illustrates the derivation of equivalence classes for an input variable that has a compound type. in C++. Ltd Equivalence classes for variables: compound data type Arrays in Java and records. Such input types may arise while testing components of an application such as a function or an object.

string lName. // Letter grades corresponding to course titles.Equivalence classes for variables: compound data type: Example Copyright © 2013 Dorling Kindersley (India) Pvt. // Course titles. Mathur 124 . } In-class exercise: Derive equivalence classes for each component of R and combine them! Contents Foundations of Software Testing 2E Author: Aditya P. // Last name. char grades [200]. string cTitle [200]. // First name. Ltd struct transcript { string fName.

One way to partition the input domain is to consider one input variable at a time. Ltd uni-dimensional partitioning . each input variable leads to a partition of the input domain. This type of partitioning is used commonly. Mathur 125 Copyright © 2013 Dorling Kindersley (India) Pvt. Thus. Contents Foundations of Software Testing 2E Author: Aditya P. We refer to this style of partitioning as uni-dimensional equivalence partitioning or simply uni-dimensional partitioning.

Contents Foundations of Software Testing 2E Author: Aditya P. Nevertheless. Many classes so created might be infeasible. equivalence classes so created offer an increased variety of tests as is illustrated in the next section. Ltd Another way is to consider the input domain I as the set product of the input . Multidimensional partitioning leads to a large number of equivalence classes that are difficult to manage manually. Mathur 126 Copyright © 2013 Dorling Kindersley (India) Pvt. We refer to this method as multidimensional equivalence partitioning or simply multidimensional partitioning. This procedure creates one partition consisting of several equivalence classes.Multidimensional partitioning variables and define a relation on I.

This leads to the following six equivalence classes. For uni-dimensional partitioning we apply the partitioning guidelines to x and y individually. Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 127 . Each of these inputs is expected to lie in the following ranges: 3≤ x≤7 and 5≤y≤9. Ltd Partitioning Example Consider an application that requires two integer inputs x and y.

) y ignored. For multidimensional partitioning we consider the input domain to be the set product X x Y. Mathur 128 . Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Partitioning Example (contd.E1: x<3 E2: 3≤x≤7 E3: x>7 E4: y<5 E5: 5≤y≤9 E6: y>9 Copyright © 2013 Dorling Kindersley (India) Pvt. x ignored. This leads to 9 equivalence classes.

Ltd Partitioning Example (contd. y>9 E7: >7. 5≤y≤9 E9: x>7. y>9 Copyright © 2013 Dorling Kindersley (India) Pvt.) Contents Foundations of Software Testing 2E Author: Aditya P.E1: x<3. Mathur 129 . y>9 E4: 3≤x≤7. y<5 E5: 3≤x≤7. 5≤y≤9 E3: x<3. y<5 E2: x<3. y<5 E8: x>7. 5≤y≤9 E6: 3≤x≤7.

y<5 E8: x>7. y>9 9 equivalence classes: Contents Foundations of Software Testing 2E Author: Aditya P. Ltd 6 equivalence classes: E1: x<3. y>9 E7: >7. y<5 E5: 3≤x≤7. 5≤y≤9 E6: 3≤x≤7.) Copyright © 2013 Dorling Kindersley (India) Pvt. y<5 E3: x<3. y>9 E2: x<3.Partitioning Example (contd. 5≤y≤9 E4: 3≤x≤7. Mathur 130 . 5≤y≤9 E9: x>7.

Identify the input domain: Read the requirements carefully and identify all input and output variables. and any conditions associated with their use. and other operating systems. an approximation to the input domain is the product of these sets. Given the set of values each variable can assume. Windows. Mathur 131 Copyright © 2013 Dorling Kindersley (India) Pvt. their types. also serve as input variables. Contents Foundations of Software Testing 2E Author: Aditya P. Environment variables.1. such as class variables used in the method under test and environment variables in Unix. Ltd Systematic procedure for equivalence partitioning .

the equivalence classes based on an input variable partition the input domain. Values for which the program is expected to behave in the ``same way" are grouped together. Contents Foundations of Software Testing 2E Author: Aditya P. is done based on the the expected behavior of the program. Ltd Systematic procedure for equivalence partitioning (contd. Mathur 132 Copyright © 2013 Dorling Kindersley (India) Pvt. partitioning the input domain using values of one variable.2. Together. Each subset is an equivalence class. Equivalence classing: Partition the set of values of each variable into disjoint subsets. Note that ``same way" needs to be defined by the tester.) .

by not combining the equivalence classes. Contents Foundations of Software Testing 2E Author: Aditya P. The equivalence classes are combined using the multidimensional partitioning approach described earlier. However. Combine equivalence classes: This step is usually omitted and the equivalence classes defined for each variable are directly used to select test cases. Mathur 133 Copyright © 2013 Dorling Kindersley (India) Pvt. one misses the opportunity to generate useful tests.3.) . Ltd Systematic procedure for equivalence partitioning (contd.

Copyright © 2013 Dorling Kindersley (India) Pvt. There might also be constraints in the requirements that render certain equivalence infeasible. suppose that an application is tested via its GUI. The GUI might disallow invalid inputs by offering a palette of valid inputs only. Ltd Systematic procedure for equivalence partitioning (contd. Contents Foundations of Software Testing 2E Author: Aditya P. For example. Such an equivalence class might arise due to several reasons. Identify infeasible equivalence classes: An infeasible equivalence class is one that contains a combination of input data that cannot be generated during test. data is input using commands available in the GUI.e.) 4. i. Mathur 134 .

Values of tempch are in the range -10. C (for control). is used by a human operator to give one of four commands (cmd): change the boiler temperature (temp).10 in increments of 5 degrees Fahrenheit. Ltd The control software of BCS. Command temp causes CS to ask the operator to enter the amount by which the temperature is to be changed (tempch).. Foundations of Software Testing 2E Author: Aditya P. One . An temperature change of 0 is not an option. is required to offer several options. Mathur Contents 135 Copyright © 2013 Dorling Kindersley (India) Pvt.Boiler control example (BCS) of the options. and cancel the request (cancel). shut down the boiler (shut). abbreviated as CS.

if V is set to file. Ltd BCS: example (contd. the operator is asked to enter one of the three commands via a GUI. The command file may contain any one of the three commands. However.) . The file name is obtained from variable F. together with the value of the temperature to be changed if the command is temp. BCS obtains the command from a command file. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 136 Copyright © 2013 Dorling Kindersley (India) Pvt.Selection of option C forces the BCS to examine variable V. If V is set to GUI.

cancel) tempch GUI cmd Control Software (CS) tempch: desired temperature change (-10. shut. file} F: file name if V is set to “file. F: Environment variables (temp. Mathur 137 .” Contents Foundations of Software Testing 2E Author: Aditya P.) V..V F cmd: command Copyright © 2013 Dorling Kindersley (India) Pvt.10) datafile V ∈{GUI. Ltd BCS: example (contd.

Ltd BCS: example (contd.) . Mathur 138 Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. In response to temp and shut commands. the control software is required to generate appropriate signals to be sent to the boiler heating system.Values of V and F can be altered by a different module in BCS.

) . The tester takes on the role of an operator and interacts with the CS via a GUI. We refer to these four values of tempch as tvalid while all other values as tinvalid. and 10. -5. 5. the only options available for the value of tempch are -10. For example. The GUI forces the tester to select from a limited set of values as specified in the requirements. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd BCS: example (contd.We assume that the control software is to be tested in a simulated environment. Mathur 139 Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 140 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd BCS: 1. identify input variables.The first step in generating equivalence partitions is to identify the (approximate) input domain. Identify input domain . First we examine the requirements. and values. their types. These are listed in the following table. Contents Foundations of Software Testing 2E Author: Aditya P. Recall that the domain identified in this step will likely be a superset of the complete input domain of the control software.

values Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 141 . 5. cancel. 10} Copyright © 2013 Dorling Kindersley (India) Pvt. GUI F Environment String A file name cmd Input via GUI/File Enumerated {temp. shut} tempch Input via GUI/File Enumerated {-10. -5. types. Ltd BCS: Variables.Variable Kind Type Value(s) V Environment Enumerated File.

shut.Copyright © 2013 Dorling Kindersley (India) Pvt. 0) Does this belong to the input domain? Contents Foundations of Software Testing 2E Author: Aditya P. temp. cmdfile. shut. Mathur 142 . --. --). Ltd BCS: Input domain Input domain⊆S=V×F×cmd×tempch Sample values in the input domain (--: don’t care): (GUI. --) (file. (file. cmdfile.

{file}. Mathur 143 .Variable Partition V {{GUI}. {undefined}} F {{fvalid}. {shut}. {cancel}. Ltd BCS: 2. {finvalid}} cmd {{temp}. Equivalence classing Contents Foundations of Software Testing 2E Author: Aditya P. {cinvalid}} tempch {{tvalid}. {tinvalid}} Copyright © 2013 Dorling Kindersley (India) Pvt.

Sample equivalence class: {(GUI. Mathur 144 . fvalid. For example. There are a total of 3×4×2×5=120 equivalence classes.Note that tinvalid. and fvalid denote sets of values. temp.) for the control software. tvalid. {(GUI}}. temp. Combine equivalence classes (contd. fvalid. -10)} Note that each of the classes listed above represents an infinite number of input values Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd BCS: 3. Contents Foundations of Software Testing 2E Author: Aditya P. finvalid. -10)} denotes an infinite set of values obtained by replacing fvalid by a string that corresponds to the name of an existing file. “undefined” denotes one value. Each value is a potential input to the BCS.

F.BCS: 4. tvalid∪ tinvalid)} This parent-child relationship between cmd and tempch renders infeasible a total of 3×2×3×5=90 equivalence classes. Mathur 145 . {cancel. Thus. Discard infeasible equivalence classes Copyright © 2013 Dorling Kindersley (India) Pvt. shut. Ltd Note that the GUI requests for the amount by which the boiler temperature is to be changed only when the operator selects temp for cmd. {(V. Exercise: How many additional equivalence classes are infeasible? Contents Foundations of Software Testing 2E Author: Aditya P. all equivalence classes that match the following template are infeasible. cinvalid}.

After having discarded all infeasible equivalence classes. Contents Foundations of Software Testing 2E Author: Aditya P.) . Mathur 146 Copyright © 2013 Dorling Kindersley (India) Pvt. we are left with a total of 18 testable (or feasible) equivalence classes. Discard infeasible equivalence classes (contd. Ltd BCS: 4.

In the most general case. it is relatively straightforward to select tests. complications could arise in the presence of infeasible data and don't care values. However.Selecting test data Copyright © 2013 Dorling Kindersley (India) Pvt. Exercise: Generate sample tests for BCS from the remaining feasible equivalence classes. a tester simply selects one test that serves as a representative of each equivalence class. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Given a set of equivalence classes that form a partition of the input domain. Mathur 147 .

4.While designing equivalence classes for programs that obtain input exclusively from a keyboard. testing must account for the possibility that a user may inadvertently enter a value for X that is out of range. However. the requirement for an application. For example. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 148 Copyright © 2013 Dorling Kindersley (India) Pvt. The application places a constraint on an input variable X such that it can assume integral values in the range 0. one must account for the possibility of errors in data entry.. Ltd GUI design and equivalence classes .

) . Ltd GUI design and equivalence classes (contd. Suppose also that the GUI offers exactly five correct choices to the user for X. Mathur 149 Copyright © 2013 Dorling Kindersley (India) Pvt. In such a situation it is impossible to test the application with a value of X that is out of range. Hence only the correct values of X will be input. Contents Foundations of Software Testing 2E Author: Aditya P.Suppose that all data entry to the application is via a GUI front end. See figure on the next slide.

Ltd GUI design and equivalence classes (contd. Mathur 150 .) Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.

Ltd 3. Mathur 151 .4 Boundary value analysis Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.

though not necessarily. suppose that method M is required to compute a function f1 when x≤ 0 is true and function f2 otherwise. Ltd Experience indicates that programmers make mistakes in processing values at and near the . {-4. Mathur 152 Copyright © 2013 Dorling Kindersley (India) Pvt. for example. 7} derived using equivalence partitioning. the value x=0. M has an error due to which it computes f1 for x<0 and f2 otherwise. lies at the boundary of the equivalence classes x≤0 and x>0. Foundations of Software Testing 2E Contents Author: Aditya P.Errors at the boundaries boundaries of equivalence classes. when M is tested against x=0 but not if the input test set is. For example. In this example. Obviously. However. this fault is revealed.

Certainly. boundary value analysis focuses on tests at and near the boundaries of equivalence classes. Contents Foundations of Software Testing 2E Author: Aditya P.Boundary value analysis is a test selection technique that targets faults in applications at the boundaries of equivalence classes. tests derived using either of the two techniques may overlap. Mathur 153 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Boundary value analysis (BVA) . While equivalence partitioning selects tests from within equivalence classes.

Mathur 154 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd 1  . This leads to as many partitions as there are input variables. Alternately. a single partition of an input domain can be created using multidimensional partitioning. We will generate several sub-domains in this step. 3  Select test data such that each boundary value occurs in at least one test input.BVA: Procedure Partition the input domain using uni-dimensional partitioning. Boundaries may also be identified using special relationships amongst the inputs. Contents Foundations of Software Testing 2E Author: Aditya P. 2  Identify the boundaries for each partition.

. Ltd Assuming that an item code must be in the range 99. Equivalence classes for qty: E4: Values less than 1. E3: Values greater than 999. Contents Foundations of Software Testing 2E Author: Aditya P.100. Equivalence classes for code: E1: Values less than 99. Mathur 155 .999 and quantity in the range 1. E2: Values in the range. E6: Values greater than 100. E5: Values in the range.. Create equivalence classes Copyright © 2013 Dorling Kindersley (India) Pvt.BVA: Example: 1.

BVA: Example: 2. Boundaries are indicated with an x. Foundations of Software Testing 2E Author: Aditya P. Ltd 98 101 x * 100 E6 Equivalence classes and boundaries for findPrice. Mathur Contents 156 . Points near the boundary are marked *. Identify boundaries * x 99 E1 100 998 * * E2 0 * E4 x 1 2 99 * * E5 1000 x * 999 E3 Copyright © 2013 Dorling Kindersley (India) Pvt.

qty=0). Consider the . qty=2). qty=99). t4: (code=998. qty=101) } Contents Foundations of Software Testing 2E Author: Aditya P. t2: (code=99.BVA: Example: 3. Mathur 157 Copyright © 2013 Dorling Kindersley (India) Pvt. for each variable. Ltd must include. qty=100). values at and around the boundary. qty=1). Illegal values of code and t3: (code=100. t6: (code=1000. t5: (code=999. Construct test set Test selection based on the boundary value analysis technique requires that tests following test set: T={ t1: (code=98. qty included.

Highly recommended: Go through Example 3. Contents Foundations of Software Testing 2E Author: Aditya P.12.11.BVA: In-class exercise ability to detect missing code for checking the validity of age. Is there an advantage of separating the invalid values of code and age into different test cases? Answer: Refer to Example 3. Mathur 158 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Is T the best possible test set for findPrice? Answer this question based on T’s .

This examination may lead to boundaries that are not evident from equivalence classes obtained from the input and output variables. Mathur 159 . Additional tests may be obtained when using a partition of the input domain obtained by taking the product of equivalence classes created using individual variables. Contents Foundations of Software Testing 2E Author: Aditya P.BVA: Recommendations Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Relationships amongst the input variables must be examined carefully while identifying boundaries along the input domain.

Tests using predicate syntax Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 160 . Ltd 4.4.Copyright © 2013 Dorling Kindersley (India) Pvt.

Ltd Where do predicates arise? Predicates arise from requirements in a variety of applications. Mathur 161 .” Annals of Software Engineering. pp 133-157. 1997. “Specification based testing using cause-effect graphs. and Vouk. Tai.Copyright © 2013 Dorling Kindersley (India) Pvt.” V 4. Here is an example from Paradkar. A boiler needs to be shut down when the following conditions hold: Contents Foundations of Software Testing 2E Author: Aditya P.

  A pump monitor has failed.  The water level in the boiler is below X lbs.  Steam meter has failed. We combine these five conditions to form a compound condition (predicate) for boiler shutdown. Contents Foundations of Software Testing 2E Author: Aditya P. (a) 2. Ltd 1.  A water pump has failed. (b) 3.Boiler shutdown conditions Copyright © 2013 Dorling Kindersley (India) Pvt. (c) 4. 5. (d) Boiler in degraded mode when either is true. (e) The boiler is to be shut down when a or b is true or the boiler is in degraded mode and the steam meter fails. Mathur 162 .  The water level in the boiler is above Y lbs.

Contents Foundations of Software Testing 2E Author: Aditya P. we obtain the following Boolean expression E that when true must force a boiler shutdown: E=a+b+(c+d)e where the + sign indicates “OR” and a multiplication indicates “AND.” The goal of predicate-based test generation is to generate tests from a predicate p that guarantee the detection of any error that belongs to a class of errors in the coding of p. Mathur 163 . Ltd Denoting the five conditions above as a through e.Boiler shutdown conditions Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 164 Copyright © 2013 Dorling Kindersley (India) Pvt. also known as a Boolean expression.Another example For example. . The following predicate represents the condition part of the statement. consider the requirement ``if the printer is ON and has paper then send document to printer. pr: (printer_status=ON) ∧ (printer_tray!= empty) Contents Foundations of Software Testing 2E Author: Aditya P.” This statement consists of a condition part and an action part. Ltd A condition is represented formally as a predicate.

Given a function f to be tested in an application. one can apply these techniques to generate tests for f. Mathur 165 .Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Summary Equivalence partitioning and boundary value analysis are the most commonly used methods for test generation while doing functional testing. Contents Foundations of Software Testing 2E Author: Aditya P.

Mathur 166 . 2013 Foundations of Software Testing 2E Contents Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Chapter 4 Predicate Analysis Updated: July 12.

Mathur 167 . Ltd Learning Objectives Contents Foundations of Software Testing 2E Author: Aditya P.§  Domain testing §  Cause-effect graphing §  Test generation from predicates Copyright © 2013 Dorling Kindersley (India) Pvt.

Copyright © 2013 Dorling Kindersley (India) Pvt.4 Tests using predicate syntax 4.1: A fault model Contents Foundations of Software Testing 2E Author: Aditya P.4. Ltd 4. Mathur 168 .

Fault model for predicate testing Copyright © 2013 Dorling Kindersley (India) Pvt. c. b. Contents Foundations of Software Testing 2E Author: Aditya P. and d are integer variables and e is a Boolean variable. Ltd What faults are we targeting when testing for the correct implementation of predicates? Boolean operator fault: Suppose that the specification of a software module requires that an action be performed when the condition (a<b) ∨ (c>d) ∧e is true. Here a. Mathur 169 .

Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Boolean operator faults Correct predicate: (a<b) ∨ (c>d) ∧e (a<b) ∧ (c>d) ∧e Incorrect Boolean operator (a<b) ∨ ! (c>d) ∧e Incorrect negation operator (a<b) ∧(c>d) ∨ e Incorrect Boolean operators (a<b) ∨ (e>d) ∧c Incorrect Boolean variable. Mathur 170 .

Mathur 171 . Ltd Relational operator faults Correct predicate: (a<b) ∨ (c>d) ∧e (a==b) ∨ (c>d) ∧e Incorrect relational operator (a==b) ∨ (c≤d) ∧e Two relational operator faults (a==b) ∨ (c>d) ∨ e Incorrect Boolean operators Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.

Incorrect predicate: Ei: : e3 relop2 e4.Arithmetic expression faults Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 172 . Ltd Correct predicate: Ec: e1 relop1 e2. Ei has an off-by-ε fault if |e3-e4|= ε for any test case for which e1=e2. Contents Foundations of Software Testing 2E Author: Aditya P. Ei has an off-by-ε* fault if |e3-e4|≥ ε for any test case for which e1=e2. Assume that Ec and Ei use the same set of variables. Ei has an off-by-ε+ fault if |e3-e4|> ε for any test case for which e1=e2.

c=2> Ei: a<b-1. <a=3.g. Ei: a<b. b=1. b=2. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 173 Copyright © 2013 Dorling Kindersley (India) Pvt. Ei: a<b+1. Given c=1. <a=4. Given c>0. c=1>. Ei has an off-by-1* fault as |a-(b+1)|≥ 1 for any test case for which a=b+c. Given c=2. Assume ε=1. b=2.Correct predicate: Ec: a<(b+c). c=1>. <a=2. e. Ei has an off-by-1 fault as |a-b|= 1 for a test case for which a=b+c. Ltd Arithmetic expression faults: Examples . Ei has an off-by-1+ fault as |a-(b-1)|>1 for any test case for which a=b+c.

Find an incorrect version of Ec that has off-by-1* fault. Assume ε=1. Find an incorrect version of Ec that has off-by-1 fault. Ltd Arithmetic expression faults: In class exercise Given the correct predicate: Ec: 2*X+Y>2. Find an incorrect version of Ec that has off-by-1+ fault. Mathur 174 . Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.

Given a correct predicate pc. Contents Foundations of Software Testing 2E Author: Aditya P. Such a test set is said to guarantee the detection of any fault of the kind in the fault model introduced above. the goal of predicate testing is to generate a test set T such that there is at least one test case t∈ T for which pc and its faulty version pi. evaluate to different truth values. Ltd Goal of predicate testing . Mathur 175 Copyright © 2013 Dorling Kindersley (India) Pvt.

As an example. b=0. c=0> and t2: <a=0. b=1.) . c=1>. suppose that pc: a<b+c and pi: a>b+c. t2} where t1: <a=0. Contents Foundations of Software Testing 2E Author: Aditya P. the fault is revealed by t2 as pc evaluates to true and pi to false when evaluated against t2. Ltd Goal of predicate testing (contd. However. Consider a test set T={t1. The fault in pi is not revealed by t1 as both pc and pi evaluate to false when evaluated against t1. Mathur 176 Copyright © 2013 Dorling Kindersley (India) Pvt.

Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 177 . Ltd Missing or extra Boolean variable faults Correct predicate: a ∨ b Missing Boolean variable fault: a Extra Boolean variable fault: a ∨ b∧c Contents Foundations of Software Testing 2E Author: Aditya P.

1: Predicate constraints Contents Foundations of Software Testing 2E Author: Aditya P. Ltd 4. Mathur 178 .4.Copyright © 2013 Dorling Kindersley (India) Pvt.4 Tests using predicate syntax 4.

<. =. f. A test case that satisfies this constraint for E must cause E to evaluate to false. +ε. consider the predicate E: a<b and the constraint “>” . Contents Foundations of Software Testing 2E Author: Aditya P. >. -ε} A BR symbol is a constraint on a Boolean variable or a relational expression. Mathur 179 .Predicate constraints: BR symbols Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Consider the following Boolean-Relational set of BR-symbols: BR={t. For example.

Contents Foundations of Software Testing 2E Author: Aditya P.A constraint C is considered infeasible for predicate pr if there exists no input values for the variables in pr that satisfy c. Ltd Infeasible constraints . Mathur 180 Copyright © 2013 Dorling Kindersley (India) Pvt. For example. the constraint t is infeasible for the predicate a>b∧ b>d if it is known that d>a.

Test case t satisfies C for predicate pr. n>0.Predicate constraints Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Let pr denote a predicate with n.. Mathur 181 . Constraint C for predicate pr guides the development of a test for pr.e. one for each Boolean variable or relational expression in pr. it offers hints on what the values of the variables should be for pr to satisfy C. Contents Foundations of Software Testing 2E Author: Aditya P. ∨ and ∧ operators. When clear from context. A predicate constraint C for predicate pr is a sequence of (n+1) BR symbols. if each component of pr satisfies the corresponding constraint in C when evaluated against t. i. we refer to ``predicate constraint" as simply constraint.

C is referred to as a true constraint when pr(C) is true and a false constraint otherwise. pr(C) =false. Mathur 182 . Contents Foundations of Software Testing 2E Author: Aditya P.True and false constraints Copyright © 2013 Dorling Kindersley (India) Pvt. respectively. A set of constraints S is partitioned into subsets St and Sf. S= St ∪ Sf. such that for each C in St. and for any C in Sf. Ltd pr(C) denotes the value of predicate pr evaluated using a test case that satisfies C. pr(C) =true.

Ltd Predicate constraints: Example Consider the predicate pr: b∧ (r<s) ∨ (u≥v) and a constraint C: (t. >). <b=true.Copyright © 2013 Dorling Kindersley (India) Pvt. =. v=0> The following test case does not satisfy C for pr. u=1. r=1. Mathur 183 . v=2> Contents Foundations of Software Testing 2E Author: Aditya P. s=1. The following test case satisfies C for pr. u=1. <b=true. s=2. r=1.

4 Tests using predicate syntax 4.3: Predicate testing criteria Contents Foundations of Software Testing 2E Author: Aditya P.4. Ltd 4.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 184 .

Contents Foundations of Software Testing 2E Author: Aditya P. and BRE. Ltd Predicate testing: criteria . BRO. We will discuss three such criteria named BOR. faults correspond to the fault model we discussed earlier.Given a predicate pr. we want to generate a test set T such that •  T is minimal and •  T guarantees the detection of any fault in the implementation of pr. Mathur 185 Copyright © 2013 Dorling Kindersley (India) Pvt.

T is referred to as a BOR-adequate test set and sometimes written as TBOR. guarantees the detection of single or multiple Boolean operator faults in the implementation of pr. Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 186 . Ltd Predicate testing: BOR testing criterion A test set T that satisfies the BOR testing criterion for a compound predicate pr.

A test set T that satisfies the BRO testing criterion for a compound predicate pr. Ltd Predicate testing: BRO testing criterion . Mathur 187 Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. guarantees the detection of single Boolean operator and relational operator faults in the implementation of pr. T is referred to as a BRO-adequate test set and sometimes written as TBRO.

T is referred to as a BRE-adequate test set and sometimes written as TBRE. relational expression. Ltd Predicate testing: BRE testing criterion A test set T that satisfies the BRE testing criterion for a compound predicate pr. guarantees the detection of single Boolean operator.Copyright © 2013 Dorling Kindersley (India) Pvt. and arithmetic expression faults in the implementation of pr. Mathur 188 . Contents Foundations of Software Testing 2E Author: Aditya P.

Contents Foundations of Software Testing 2E Author: Aditya P. be a test set derived from predicate pr. Let pf be another predicate obtained from pr by injecting single or multiple faults of one of three kinds: Boolean operator fault. and arithmetic expression fault.BRE}. BRO. p(t)≠ pf(t). Tx is said to guarantee the detection of faults in pf if for some t∈Tx. Ltd Predicate testing: guaranteeing fault detection . relational operator fault. Mathur 189 Copyright © 2013 Dorling Kindersley (India) Pvt.Let Tx. x∈{BOR.

Mathur 190 . d=2 >. t). t) Contents Foundations of Software Testing 2E Author: Aditya P. d=0 >. i.Guaranteeing fault detection: example Copyright © 2013 Dorling Kindersley (India) Pvt. t)} Let TBOR={t1. t2. a<b is true and c<d is also true. t). c=1. c=1.f). t1: <a=1. f) t3: <a=1. Satisfies (t. b=2. c=1. t3} is a BOR adequate test set that satisfies S. (f. Satisfies (t.e. b=2. d=0 >. (t. t2: <a=1. b=0. Satisfies (f. Ltd Let pr=a<b ∧ c>d Constraint set S={(t.

Mathur 191 . Ltd Guaranteeing fault detection: In class exercise Generate single Boolean operator faults in pr: a<b ∧ c>d and show that T guarantees the detection of each fault. Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.

1: BOR. Mathur 192 . Ltd 4.4 Tests using predicate syntax 4.4. and BRE adequate tests Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. BRO.

v)|u∈A. Contents Foundations of Software Testing 2E Author: Aditya P. BRO. Ltd Algorithms for generating BOR.Copyright © 2013 Dorling Kindersley (India) Pvt.b)|a∈A and b∈B} The onto product of two sets A and B is defined as: A⊗B={(u. Mathur 193 .} Note that A⊗B is a minimal set. v∈B. and BRE adequate tests Define the cross product of two sets A and B as: A×B={(a. such that each element of A appears at least once as u and each element of B appears once as v.

f). =. <). <} A×B={(t. >} and B={f. (=. (t. <). f).Copyright © 2013 Dorling Kindersley (India) Pvt. f). (>. (>. Mathur 194 . (=.<). (=.<)} A⊗B ={(t. Ltd Set products: Example Let A={t. (>. f).<)} Any other possibilities for A⊗B? Contents Foundations of Software Testing 2E Author: Aditya P.

An illustration follows. We want to generate TBOR for pr: a<b ∧ c>d First. generate syntax tree of pr.Generation of BOR constraint set Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 195 . ∧ a<b c>d Contents Foundations of Software Testing 2E Author: Aditya P. Ltd See page 184 for a formal algorithm.

where SNt is the true constraint set. and SNf is the false constraint. Ltd Generation of the BOR constraint set Given node N in the syntax tree for predicate pr. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 196 . we use the following notation: SN= SNt ∪ SNf is the constraint set.Copyright © 2013 Dorling Kindersley (India) Pvt.

label each leaf node with the constraint set {(t). and so on for convenience. Ltd Second.) Copyright © 2013 Dorling Kindersley (India) Pvt.Generation of the BOR constraint set (contd. Contents Foundations of Software Testing 2E Author: Aditya P. N2. We label the nodes as N1. (f)} SN2= N2 {(t). N3 N1 SN1= ∧ c>d a<b {(t). (f)} Notice that N1 and N2 are direct descendants of N3 which is an AND-node. (f)}. Mathur 197 .

t)} ∧ N2 N1 SN3f = (SN1f ×{t2})∪({t1}× SN2f c>d {(t). (f)} = {(f. For an AND node.t).{(t. (f. Ltd Third.Generation of the BOR constraint set (contd. t). SN3={(t. f)} Contents Foundations of Software Testing 2E Author: Aditya P.) case N3. t)}∪{(t. in this . (f)} a<b = ({(f)} ×{(t)})∪({(t)}× {(f)}) = {(f. Mathur 198 Copyright © 2013 Dorling Kindersley (India) Pvt. t). f)} SN3t = SN1t ⊗ SN2t ={(t)} ⊗ {(t)}={(t. compute the constraint set for the next higher node in the syntax tree. (t. f)} N3 {(t). the formulae used are the following.

c=6.t). SN3={(t. we have computed the BOR constraint set for the root node of . t) t2=<a=1. d=5> (f. t2. f) Contents Foundations of Software Testing 2E Author: Aditya P. (f)} t1=<a=1. b=0. TBOR ={t1. f)} SN3 contains a sequence of three constraints and N3 hence we get a minimal test set consisting of three test cases. (f)} a<b {(t). d=2> (t. We can now generate a test set using the BOR constraint set associated with the root node. Mathur 199 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd As per our objective. t).Generation of TBOR the AST(pr). t) t3=<a=1. d=5> (t. c=1. (t. c=6. b=2. Here is one possible test set. t3} ∧ N2 N1 c>d {(t). b=2. (f.

See pages 187-188 for a formal algorithm. Contents Foundations of Software Testing 2E Author: Aditya P. An illustration follows. Recall that a test set adequate with respect to a BRO constraint set for predicate pr. Ltd Generation of BRO constraint set . Mathur 200 Copyright © 2013 Dorling Kindersley (India) Pvt. guarantees the detection of all combinations of single or multiple Boolean operator and relational operator faults.

(=)} Sf={(>)} Note: tN denotes an element of StN and fN denotes an element of SfN Foundations of Software Testing 2E Author: Aditya P. (=)} Sf={(=). (>)} relop: < St={(<)} Sf={(=). (<)} Separation of S into its true (St) and false (Sf)components: relop: > St={(>)} relop: ≥ St={(>). (=). (<)} Sf={(<)} relop: = St={(=)} Sf={(<). Mathur 201 Contents .BRO constraint set The BRO constraint set S for relational expression e1 relop e2: Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd S={(>). (>)} relop: ≤ St={(<).

Mathur 202 . ∨ N4 ∧ r>s N1 a+b<c N6 ! p N5 N3 N2 Contents Foundations of Software Testing 2E Author: Aditya P.BRO constraint set: Example Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd pr: (a+b<c)∧!p ∨ (r>s) Step 1: Construct the AST for the given predicate.

Ltd Step 2: Label each leaf node with its constraint set S. (=). (<)} N2 {(t). (=). (f)} Contents Foundations of Software Testing 2E Author: Aditya P. (<)} N3 ! p Copyright © 2013 Dorling Kindersley (India) Pvt. N5 {(>).BRO constraint set: Example (contd. Mathur 203 .) ∨ N4 N6 ∧ r>s N1 a+b<c {(>).

(<. t)} Contents Foundations of Software Testing 2E Author: Aditya P. f)} ∪ {(<.=)} ×{(f)}) ∪ {(<)} ×{(t)}) ={(>. SfN3=SN2t= {(t)} StN4=SN1t ⊗ SN3t={(<)} ⊗{(f)}={(<. (=. f)} SfN4= (SfN1 × {(tN3)}) ∪ ({(tN1)} × SfN3) =({(>. f). t)} ={(>. f). Mathur 204 .) StN3=SN2f={(f)} Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Step 2: Traverse the tree and compute constraint set for each internal node.BRO constraint set: Example (contd. f). (=.

(f)} Contents Foundations of Software Testing 2E Author: Aditya P. t)} N4 ∧ r>s N1 a+b<c {(>). (<)} N3 {(f). (>. {t)} N2 {(t). f). Mathur 205 Copyright © 2013 Dorling Kindersley (India) Pvt. (=). f).) . (<. (<)} N6 ! p N5 {(>). (=. f). Ltd BRO constraint set: Example (contd. (=).∨ {(<.

=)} ∪ {(>.f)} ×{(>)}) ={(<.f).f. SfN6=SfN4 ⊗ SfN5 ={(>. (=.f)} ×{(=)}) ∪ {(>. f)} ={(>.(=.) Copyright © 2013 Dorling Kindersley (India) Pvt.=).=)} StN6= (StN4 × {(fN5)})∪ ({(fN4)} × StN5) =({(<.(<)}={(<.=).<).f. Mathur 206 .>)} Contents Foundations of Software Testing 2E Author: Aditya P.f.f.(<. Ltd Next compute the constraint set for the rot node (this is an OR-node).BRO constraint set: Example (contd.f.(>.>)} ={(<.f).t.(<.f.t)} ⊗{(=).

(f)} Foundations of Software Testing 2E N5 Author: Aditya P.=). t)} ∨ N6 N4 ∧ N1 a+b<c {(>). (=. {t)} ! p N2 {(t). (=).=).f.f.Constraint set for Copyright © 2013 Dorling Kindersley (India) Pvt. (>. Mathur Contents 207 .<). f).t.f. Ltd BRO constraint set: Example (contd. (=).) pr: (a+b<c)∧!p ∨ (r>s) {(>.>)} {(<. f). f).(>.f. (=. (<)} r>s {(>). (<. (<)} N3 {(f).=). (<.(<.

=).Copyright © 2013 Dorling Kindersley (India) Pvt.f. Ltd BRO constraint set: In-class exercise Given the constraint set for pr: (a+b<c)∧!p ∨ (r>s). Mathur 208 .<).>)} Contents Foundations of Software Testing 2E Author: Aditya P. {(>.=).(<.f.=). construct TBRO .f. (<.f.(>.t. (=.

Mathur 209 . Ltd 4.4 Tests using predicate syntax 4.4.5: BOR constraints for non-singular expressions Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.

let us look at some non-singular expressions. We will now learn how to generate BOR constraints for non-singular predicates. Recall that a singular predicate contains only one occurrence of each variable. their respective disjunctive normal forms (DNF). and their mutually singular components. Ltd BOR constraints for non-singular expressions .Test generation procedures described so far are for singular predicates. Mathur 210 Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. First.

bc+!b. !b+!c+ cde a(bc+!b+de) abc+a!b+ade a.Predicate (pr) DNF Mutually singular components in pr ab(b+c) abb+abc a. (bc+bd) a(!b+!c)+cde a!ba +a!c+cde a. de Copyright © 2013 Dorling Kindersley (India) Pvt. b(b+c) a(bc+ bd) abc+abd a. Ltd Non-singular expressions and DNF: Examples Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 211 .

First we examine the Meaning Impact (MI) procedure for generating a minimal set of constraints from a possibly non-singular predicate. Mathur 212 . Contents Foundations of Software Testing 2E Author: Aditya P. Next. Ltd Generating BOR constraints for non-singular expressions We proceed in two steps.Copyright © 2013 Dorling Kindersley (India) Pvt. we examine the procedure to generate BOR constraint set for a non-singular predicate.

Ltd Meaning Impact (MI) procedure Given Boolean expression E in DNF. The MI procedure is on page 193 and is illustrated next. the MI procedure produces a set of constraints SE that guarantees the detection of missing or extra NOT (!) operator faults in the implementation of E. Mathur 213 . Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.

b. For example. For example bc is the same as b∧c. Ltd Consider the non-singular predicate: a(bc+!bd). Contents Foundations of Software Testing 2E Author: Aditya P. and as per common convention we have omitted the Boolean AND operator.MI procedure: An Example Copyright © 2013 Dorling Kindersley (India) Pvt. ! is the Boolean NOT operator. Recall that + is the Boolean OR operator. and d are Boolean variables and also referred to as literals. Its DNF equivalent is: E=abc+a!bd. Mathur 214 . Note that a. c. Each literal represents a condition. a could represent r<s.

are to be interpreted similarly.) Copyright © 2013 Dorling Kindersley (India) Pvt. The second element.t)} Note that the four t’s in the first element of Te1 denote the values of the Boolean variables a. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 215 .f.t). (t.t.t). and others. Similarly construct Te2 for e2 that makes e2 true. Te1 ={(t.t. Step 1: Construct a constraint set Te1 for e1 that makes e1 true.t. we can write E=e1+e2.f)} Te2 ={(t. b.c. respectively. Ltd Step 0: Express E in DNF notation.f.t. and d.MI procedure: Example (contd. Clearly. where e1=abc and e2=a!bd. (t.t.f.

remove the constraints that are in any other Tej.t).t).t)} Contents Foundations of Software Testing 2E Author: Aditya P. (t.f.t.) Copyright © 2013 Dorling Kindersley (India) Pvt. Hence we get: TSe1 ={(t.MI procedure: Example (contd.f. Note that this step will lead TSei ∩TSej =∅. (t.f.t.t. This gives us TSei and TSej. There are no common constraints between Te1 and Te2 in our example.t. Ltd Step 2: From each Tei .t. Mathur 216 .f)} TSe2 ={(t.

MI procedure: Example (contd.) Copyright © 2013 Dorling Kindersley (India) Pvt.t.t). (t. Mathur 217 .f.t.f)} Note that for each constraint x in StE we get E(x)=true. Ltd Step 3: Construct StE by selecting one element from each Te. Also. StE ={(t. StE is minimal.f. Check it out! Contents Foundations of Software Testing 2E Author: Aditya P.

one at a time.Copyright © 2013 Dorling Kindersley (India) Pvt. derive constraints Fe that make e true. e11= !abc e21= a!bc e31= ab!c e12= !a!bd e22= abd e32= a!b!d From each term e above. Contents Foundations of Software Testing 2E Author: Aditya P.) Step 4: For each term in E. obtain terms by complementing each literal. Mathur 218 . Ltd MI procedure: Example (contd. We get the following six sets.

t)} Fe22= {(t.f. (t.t)} Fe32= {(t.t).f)} Fe31= {(t.t.t.t).t.t.t.f)} Fe12= {(f.f.t).t.f.f.f)} Fe21= {(t.f). (t.f. (f.t).f.t. (t.t.f.t.f.) Fe11= {(f.t.f. Mathur 219 .f.f)} Contents Foundations of Software Testing 2E Author: Aditya P. (t.t).f.t.t. (f.t. Ltd MI procedure: Example (contd.Copyright © 2013 Dorling Kindersley (India) Pvt.

t. FSe12= FSe12 FSe22= {(t.f)} FSe31= FSe13 Constraints common to Te1 and Te2 are removed. Mathur 220 Copyright © 2013 Dorling Kindersley (India) Pvt.t)} FSe32= FSe13 Contents Foundations of Software Testing 2E Author: Aditya P.f.f. Ltd MI procedure: Example (contd.t.) .Step 5: Now construct FSe by removing from Fe any constraint that appeared in any of the two sets Te constructed earlier. FSe11= FSe11 FSe21= {(t.

t.f).f.t. Contents Foundations of Software Testing 2E Author: Aditya P.f). (t.t.t. (f.f.t). Mathur 221 Copyright © 2013 Dorling Kindersley (India) Pvt.t.) SfE ={(f. Ltd Step 6: Now construct SfE by selecting one constraint from each Fe .t.t)} Note: Each constraint in StE makes E true and each constraint in SfE makes E false.f.t. (f.t).t. (t.t.t).f.MI procedure: Example (contd.t.f).f. (t. (t.f). Check it out! We are now done with the MI procedure.f.f. (t. (f.f).t.t)} Step 7: Now construct SE= StE ∪SfE SE={{(t.t.f.

The BOR-MI-CSET procedure takes a non-singular expression E as input and generates a constraint set that guarantees the detection of Boolean operator faults in the implementation of E. Ltd BOR-MI-CSET procedure . Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 222 Copyright © 2013 Dorling Kindersley (India) Pvt. The BOR-MI-CSET procedure using the MI procedure described earlier. The entire procedure is described on page 195. We illustrate it with an example.

BOR-MI-CSET: Example Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 223 . Ltd Consider a non-singular Boolean expression: E= a(bc+!bd) Mutually non-singular components of E: e1=a e2=bc+!bd We use the BOR-CSET procedure to generate the constraint set for e1 (singular component) and MI-CSET procedure for e2 (non-singular component).

) For component e1 we get: Ste1={t}. Ltd BOR-MI-CSET: Example (contd. Contents Foundations of Software Testing 2E Author: Aditya P. Sfe1={f} Recall that Ste1 is true constraint set for e1 and Sfe1 is false constraint set for e1. Mathur 224 .Copyright © 2013 Dorling Kindersley (India) Pvt.

t).f. As per Step 1 of the MI-CSET procedure we obtain: Tu={(t. Let us now apply the MI-CSET procedure to obtain the BOR constraint set for e2.BOR-MI-CSET: Example (contd.f)} Tv={(f.t. (f. (t. Ltd Component e2 is a DNF expression.t. We can write e2=u+v where u=bc and v=! bd.t.t). Mathur 225 .) Copyright © 2013 Dorling Kindersley (India) Pvt.t)} Contents Foundations of Software Testing 2E Author: Aditya P.

t.f).t. t)} Next we apply Step 4 to u and v. We obtain the following complemented expressions from u and v: One possible alternative. Can you think of other alternatives? u1=!bc u2=b!c v1=bd v2=!b!d Contents Foundations of Software Testing 2E Author: Aditya P.BOR-MI-CSET: Example (contd. (f. Mathur 226 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Applying Steps 2 and 3 to Tu and Tv we obtain: .) TSu=Tu TSv=Tv Ste2={(t.

t).f)} FSu2=(t.f.f).t).t.f.t).t)} FSv2={(f. (f. (t.t). Mathur 227 .f)} FSv1={(t.f).f.t. (f. (t.f)} Fu2=(t.t.t.t. (t.f.t)} Fv2={(f. (f.f.f.f.f)} Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Continuing with Step 4 we obtain: Next we apply Step 5 to the F constraint sets to obtain: FSu1={(f.f.f)} Fv1={(t.) Fu1={(f.BOR-MI-CSET: Example (contd.t.f)} Contents Foundations of Software Testing 2E Author: Aditya P.

Ltd Applying Step 6 to the FS sets leads to the following Sfe2={(f.t. (t.f).) Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. t).f).f.t)}.f). Combing the true and false constraint sets for e2 we get: Se2={(t. (f. Mathur 228 .t. t.f.t. {(f. (t.t)}.BOR-MI-CSET: Example (contd.

t. t.f). Contents Foundations of Software Testing 2E Author: Aditya P. (f.t)} from MI-CSET procedure. (t. We now apply Step 2 of the BOR-CSET procedure to obtain the constraint set for the entire expression E.t.BOR-MI-CSET: Example (contd.f). Ltd Summary: from BOR-CSET procedure. Mathur 229 .) Ste1={(t)} Sfe1={(f)} Ste2={(t. t)} Copyright © 2013 Dorling Kindersley (India) Pvt.f. Sfe2={(f.

(t.f). Ltd Obtained by applying Step 2 of BOR-CSET to an .f.f). (f.t.f).BOR-MI-CSET: Example (contd.t. t.t.t)} N2 ∨ {(t.f).t. Mathur Contents 230 Copyright © 2013 Dorling Kindersley (India) Pvt. (f.t)} N1 a ∧ {(t).(f)} b ∧ c !b d Apply MI-CSET Foundations of Software Testing 2E Author: Aditya P.t.) StN3=StN1 ⊗ StN22 AND node. t). SfN3=(SfN1 × {t2})∪({t1} × SfN2) N3 ∧ {(t. (f. (t.t).t.t.t. (t.f.(t.f.f.f).t.

Most requirements contain conditions under which functions are to be executed. Ltd Summary . Predicate testing procedures covered are excellent means to generate tests to ensure that each condition is tested adequately. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 231 Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 232 . and predicate testing procedures to generate tests for a requirement of the following type: if condition then action 1. action 2. …action n. and predicate testing if there are nested conditions.) Copyright © 2013 Dorling Kindersley (India) Pvt. boundary value analysis.Summary (contd. Ltd Usually one would combine equivalence partitioning. Contents Foundations of Software Testing 2E Author: Aditya P. BVA. Apply predicate testing Apply eq. partitioning.

Ltd Chapter 5 Test Generation from Finite State Models Updated: July 16. Mathur 233 .Copyright © 2013 Dorling Kindersley (India) Pvt. 2013 Foundations of Software Testing 2E Contents Author: Aditya P.

Mathur 234 . Ltd Learning Objectives UIO method is not covered in these slides.8). It is left for the students to read on their own (Section 5.§  What are Finite State Models? §  The W method for test generation §  The Wp method for test generation §  Automata theoretic versus control-flow based test generation Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P.

Ltd §  elevator designs.g. steam boiler control. transmission. automobile components (locks. etc.Where are these methods used? Conformance testing of communications protocols--this is where it all started. Generation of tests from FSM specifications assists in testing the conformance of implementations to the corresponding FSM model. nuclear plant protection systems. Alert: It will be a mistake to assume that the test generation methods described here are applicable only to protocol testing! Foundations of Software Testing 2E Author: Aditya P. e.) §  Finite state machines are widely used in modeling of all kinds of systems. stepper motors. Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur Contents 235 . etc). §  Testing of any system/subsystem modeled as a finite state machine.

Mathur 236 .2 Finite State Machines Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd 5.

Contents Foundations of Software Testing 2E Author: Aditya P.A finite state machine. For example. a network protocol could be modeled using an FSM. Ltd What is a Finite State Machine? . Mathur 237 Copyright © 2013 Dorling Kindersley (India) Pvt. An FSM is derived from application requirements. abbreviated as FSM. is an abstract representation of behavior exhibited by some systems.

performance requirements.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 238 . Real time requirements. Ltd What is a Finite State Machine? Not all aspects of an application’s requirements are specified by an FSM. Contents Foundations of Software Testing 2E Author: Aditya P. and several types of computational requirements cannot be specified by an FSM.

The role assigned to an FSM depends on whether it is a part of the requirements specification or of the design specification. Ltd An FSM could serve any of two roles: as a specification of the required behavior and/ or as a design artifact according to which an application is to be implemented. Contents Foundations of Software Testing 2E Author: Aditya P. Note that FSMs are a part of UML 2. Mathur 239 .Requirements or design specification? Copyright © 2013 Dorling Kindersley (India) Pvt.0 design notation.

pacemakers. and many more. While the FSM’s considered in examples are abstract machines. Mathur 240 Copyright © 2013 Dorling Kindersley (India) Pvt. safety software modeling in nuclear plants. network protocols. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Where are FSMs used? .Modeling GUIs. WEB applications. Teller machines. they are abstractions of many real-life machines.

Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 241 Copyright © 2013 Dorling Kindersley (India) Pvt. While FSMs can be modeled using statecharts. Ltd FSM and statcharts . The term “state diagram” is often used to denote a graphical representation of an FSM or a statechart. the reverse is not true. Techniques for generating tests from FSMs are different from those for generating tests from statecharts.Note that FSMs are different from statecharts.

O). q0 in Q is the initial state. and O: Q x X→ Y is an output function Contents Foundations of Software Testing 2E Author: Aditya P. Y is a finite set of output symbols also known as the output alphabet. X is a finite set of input symbols also known as the input alphabet. Ltd An FSM (Mealy) is a 6-tuple: (X. δ. Y. q0. Mathur 242 . Q is a finite set states. where:. δ: Q x X→ Q is a next-state or state transition function. Q.FSM (Mealy machine): Formal definition Copyright © 2013 Dorling Kindersley (India) Pvt.

X .Copyright © 2013 Dorling Kindersley (India) Pvt. q0. Mathur 243 . Q. Y. F). q0. Contents Foundations of Software Testing 2E Author: Aditya P. where:. Y. Ltd FSM (Moore machine): Formal definition An FSM (Moore) is a 7-tuple: (X. Q. δ. O. and δ are the same as in FSM (Mealy) O: Q → Y is an output function F∈Q is the set of final or accepting or terminating states.

F. Mathur 244 . Moore (1956 publication) Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.) Mealy machines are due to G. H. Ltd FSM: Formal definition (contd. Mealy (1955 publication) Moore machines are due to E.

Ltd Requirements FSM based Test inputs Application Observed behavior Contents Foundations of Software Testing 2E Author: Aditya P.Test generation from FSMs Our focus FSM Test generation algorithm Test generation for application Application Test inputs Blue: Generated Test driver data Pass/fail Test inputs Oracle Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 245 .

In any case. Mathur 246 Copyright © 2013 Dorling Kindersley (India) Pvt. For example. Ltd Many real-life devices have computers embedded in them. An embedded system can be as simple as a child's musical keyboard or as complex as the flight controller in an aircraft. an . engine control being one example.Embedded systems automobile has several embedded computers to perform various tasks. Another example is a computer inside a toy for processing inputs and generating audible and visual responses. Such devices are also known as embedded systems. an embedded system contains one or more computers for processing inputs. Contents Foundations of Software Testing 2E Author: Aditya P.

Contents Foundations of Software Testing 2E Author: Aditya P.An embedded computer often receives inputs from its environment and responds with appropriate actions. While doing so. Ltd Specifying embedded systems . It is this behavior of an embedded system in response to inputs that is often modeled by a finite state machine (FSM). Mathur 247 Copyright © 2013 Dorling Kindersley (India) Pvt. it moves from one state to another. The response of an embedded system to its inputs depends on its current state.

Ltd Simple three state lamp behavior: (a) Lamp switch can be turned clockwise. Mathur 248 . Contents Foundations of Software Testing 2E Author: Aditya P. (b) Lamp switch can be turned clockwise and counterclockwise.FSM: lamp example Copyright © 2013 Dorling Kindersley (India) Pvt.

and OUT actions. ADD. OUT: Output num.FSM: Actions with state transitions Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Machine to convert a sequence of decimal digits to an integer: (a) Notice the ADD. Mathur 249 . ADD: Add to num. INIT. (b) INIT: Initialize num. Contents Foundations of Software Testing 2E Author: Aditya P.

Mathur 250 . Ltd FSM: Formal definition An FSM is a quintuple: (X. q0. Contents Foundations of Software Testing 2E Author: Aditya P. Y is a finite set of output symbols also known as the output alphabet. Y. where: X is a finite set of input symbols also known as the input alphabet. O).Copyright © 2013 Dorling Kindersley (India) Pvt. Q. Q is a finite set states. δ.

FSM: Formal definition (contd. sometimes it is convenient to add F⊆ Q as a set of final or accepting states while specifying an FSM. δ: Q x X→ Q is a next-state or state transition function. In some variants of FSM more than one state could be specified as an initial state. and O: Q x X→ Y is an output function. Also. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd q0 in Q is the initial state.) Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 251 .

i is also known as the input portion of the edge and o its output portion.A state diagram is a directed graph that contains nodes representing states and edges representing state transitions and output functions. Each directed edge in a state diagram connects two states. Ltd State diagram representation of FSM . Mathur 252 Copyright © 2013 Dorling Kindersley (India) Pvt. Each edge is labeled i/o where i denotes an input symbol that belongs to the input alphabet X and o denotes an output symbol that belongs to the output alphabet O. Contents Foundations of Software Testing 2E Author: Aditya P. Each node is labeled with the state it represents.

2 Tabular representation Contents Foundations of Software Testing 2E Author: Aditya P. Ltd 5.2.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 253 .

Contents Foundations of Software Testing 2E Author: Aditya P. The rightmost sub-table is the next state sub-table. The table consists of two sub-tables that consist of one or more columns each. The leftmost sub table is the output or the action sub-table. Ltd Tabular representation of FSM .A table is often used as an alternative to the state diagram to represent the state transition function δ and the output function O. Mathur 254 Copyright © 2013 Dorling Kindersley (India) Pvt. The rows are labeled by the states of the FSM.

Tabular representation of FSM: Example Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 255 . Ltd The table given below shows how to represent functions δ and O for the DIGDEC machine.

Ltd 5. Mathur 256 .3 Properties of FSM Contents Foundations of Software Testing 2E Author: Aditya P.2.Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 257 Copyright © 2013 Dorling Kindersley (India) Pvt. qj) there exists an input sequence that takes M from state qi to state qj. Ltd Properties of FSM .Completely specified: An FSM M is said to be completely specified if from each state in M there exists a transition for each input symbol. Contents Foundations of Software Testing 2E Author: Aditya P. Strongly connected: An FSM M is considered strongly connected if for each pair of states (qi .

Q1. be the states of machines M1 and M2. Contents Foundations of Software Testing 2E Author: Aditya P. Q2. T1. Y. Let qi and qj. V⊆ X+. m20. qi and qj are considered V-equivalent if O1(qi. O1) and M2=(X. s)=O2(qj. Y. Mathur 258 Copyright © 2013 Dorling Kindersley (India) Pvt. m10. s) for all s in V. respectively.e. Let V denote a set of non-empty strings over the input alphabet X i.V-equivalence: Let M1=(X. i≠ j. T2. Ltd Properties of FSM: Equivalence . O2) be two FSMs.

Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Properties of FSM: Distinguishable . yield identical output sequences. respectively. This definition of equivalence also applies to states within a machine. r)=O2(qj. Mathur 259 Copyright © 2013 Dorling Kindersley (India) Pvt.Stated differently. If qi and qj are not equivalent then they are said to be distinguishable. when excited in states qi and qj. Thus. machines M1 and M2 could be the same machine. states qi and qj are considered V-equivalent if M1 and M2 . r) for any set V. States qi and qj are said to be equivalent if O1(qi.

Contents Foundations of Software Testing 2E Author: Aditya P. Machines that are not equivalent are considered distinguishable. Minimal machine: An FSM M is considered minimal if the number of states in M is less than or equal to any other FSM equivalent to M. Mathur 260 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Machine equivalence: Machines M1 and M2 are said to be equivalent if (a) for each .Properties of FSM: Machine Equivalence state σ in M1 there exists a state σ ' in M2 such that σ and σ ' are equivalent and (b) for each state σ in M2 there exists a state σ ' in M1 such that σ and σ ' are equivalent.

O2) be two FSMs. Mathur 261 Copyright © 2013 Dorling Kindersley (India) Pvt. Q1. m10. T1. Q2. States qiε Q1 and qjε Q2 are considered k-equivalent if. Ltd Properties of FSM: k-equivalence . m20. when excited by any input of length k. Y. T2. yield identical output sequences.k-equivalence: Let M1=(X. Y. O1) and M2=(X. Contents Foundations of Software Testing 2E Author: Aditya P.

It is also easy to see that if two states are k-distinguishable for any k>0 then they are also distinguishable for any n≥ k. M1 and M2 may be the same machines implying that kdistinguishability applies to any pair of states of an FSM. If M1 and M2 are not kdistinguishable then they are said to be k-equivalent. Mathur 262 .Properties of FSM: k-equivalence (contd. Ltd States that are not k-equivalent are considered k-distinguishable. Once again. Contents Foundations of Software Testing 2E Author: Aditya P.) Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 263 . Ltd Example: Completely specified machine Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.

4 A fault model Contents Foundations of Software Testing 2E Author: Aditya P. Ltd 5.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 264 .

Ltd Faults in implementation .An FSM serves to specify the correct requirement or design of an application. Mathur 265 Copyright © 2013 Dorling Kindersley (India) Pvt. Hence tests generated from an FSM target faults related to the FSM itself. What faults are targeted by the tests generated using an FSM? Contents Foundations of Software Testing 2E Author: Aditya P.

Fault model a/0 q0 q0 a/1 b/1 q0 a/1 b/1 a/1 b/1 q1 q1 q1 b/0 b/0 b/0 Correct design Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 266 . Ltd a/1 Operation error a/1 Transfer error Contents Foundations of Software Testing 2E Author: Aditya P.

a/1 b/1 a/0 q0 q0 a/1 q2 a/1 b/0 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Fault model (contd. Mathur 267 .) q1 b/0 Extra state error Missing state error Contents Foundations of Software Testing 2E Author: Aditya P.

6 The W-method Contents Foundations of Software Testing 2E Author: Aditya P. Ltd 5. Mathur 268 .5 Characterization set 5.Copyright © 2013 Dorling Kindersley (India) Pvt.

Minimality: An FSM M is considered minimal if the number of states in M is less than or equal to any other FSM equivalent to M. Contents Foundations of Software Testing 2E Author: Aditya P. Completely specified: An FSM M is said to be completely specified if from each state in M there exists a transition for each input symbol. Ltd Assumptions for test generation . Mathur 269 Copyright © 2013 Dorling Kindersley (India) Pvt.

Step 1: Estimate the maximum number of states (m) in the correct implementation of the given FSM M. Step 2: Construct the characterization set W for M. Step 3: (a) Construct the testing tree for M and (b) generate the transition cover set P from the testing tree. Mathur 270 Copyright © 2013 Dorling Kindersley (India) Pvt. Step 4: Construct set Z from W and m. Step 5: Desired test set=P.Z Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Chow’s (W) method .

let m=|Q|. Ltd Step 1: Estimation of m This is based on a knowledge of the implementation. Mathur 271 . Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. In the absence of any such knowledge.

Step 2: Construction of the W-set Copyright © 2013 Dorling Kindersley (India) Pvt. δ. W is a finite set of input sequences that distinguish the behavior of any pair of states in M. Mathur 272 . s) Contents Foundations of Software Testing 2E Author: Aditya P. Q. s)≠O(qj. Ltd Let M=(X. Each input sequence in W is of finite length. O) be a minimal and complete FSM. Y. Given states qi and qj in Q. W contains a string s such that: O(qi. q1.

Ltd Example of a W-set W={baaa.q1)=1101 O(baaa.Copyright © 2013 Dorling Kindersley (India) Pvt.q1) ≠ O(baaa.q2)=1100 Thus. Mathur 273 .q2) Contents Foundations of Software Testing 2E Author: Aditya P. baaa distinguishes state q1 from q2 as O(baaa.aa.aaa} O(baaa.

Mathur 274 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Steps in the construction of W-set . m>0. Contents Foundations of Software Testing 2E Author: Aditya P.Step 1: Construct a sequence of k-equivalence partitions of Q denoted as P1. …Pm. Step 2: Traverse the k-equivalence partitions in reverse order to obtain distinguishing sequence for each pair of states. P2.

Ltd What is a k-equivalence partition of Q? . Σk2 … Σkn such that ∪ni=1 Σki =Q States in Σki are k-equivalent. If state u is in Σki and v in Σkj for i≠j. then u and v are k-distinguishable. Contents Foundations of Software Testing 2E Author: Aditya P. denoted as Pk. Mathur 275 Copyright © 2013 Dorling Kindersley (India) Pvt.A k-equivalence partition of Q. is a collection of n finite sets Σk1.

construct a 1-equivalence partition. Mathur 276 . Ltd Given an FSM M. Current state Output Next state a b a b q1 0 1 q1 q4 q2 0 1 q1 q5 q3 0 1 q5 q1 q4 1 1 q3 q4 q5 1 1 q2 q5 Contents Foundations of Software Testing 2E Author: Aditya P. start with a tabular representation of M.How to construct a k-equivalence partition? Copyright © 2013 Dorling Kindersley (India) Pvt.

This gives us 1-partition P1 consisting Σ 1 2 Current state Output Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 277 .Construct 1-equivalence partition Group states identical in their Output entries. Ltd of Σ1={q1. q2. q5}. Next state a b a b q1 0 1 q1 q4 q2 0 1 q1 q5 q3 0 1 q5 q1 q4 1 1 q3 q4 q5 1 1 q2 q5 Contents Foundations of Software Testing 2E Author: Aditya P. q3} and Σ2 ={q4.

Remove the output columns.Construct 2-equivalence partition: Rewrite P1 table is the group number in which lies state qi. Σ 1 2 Current state Next state a b q1 q11 q42 q2 q11 q52 q3 q52 q11 q4 q31 q42 q5 q21 q52 P1 Table Group number Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 278 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Rewrite P1 table. Replace a state entry qi by qij where j .

Mathur 279 Copyright © 2013 Dorling Kindersley (India) Pvt. This . Note the change in second subscripts. Ltd Group all entries with identical second subscripts under the next state column. Σ Current state Next state a b q1 q11 q43 q2 q11 q53 2 q3 q53 q11 3 q4 q32 q43 q5 q21 q53 1 P2 Table Contents Foundations of Software Testing 2E Author: Aditya P.Construct 2-equivalence partition: Construct P2 table gives us the P2 table.

Note the change in second subscripts. Mathur 280 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Group all entries with identical second subscripts under the next state column. This . Σ Current state Next state a b q1 q11 q43 q2 q11 q54 2 q3 q54 q11 3 q4 q32 q43 4 q5 q21 q54 1 P3 Table Contents Foundations of Software Testing 2E Author: Aditya P.Construct 3-equivalence partition: Construct P3 table gives us the P3 table.

Construct 4-equivalence partition: Construct P4 table Σ Current state P4 Table Next state a b 1 q1 q11 q44 2 q2 q11 q55 3 q3 q55 q11 4 q4 q33 q44 5 q5 q22 q55 Contents Foundations of Software Testing 2E Author: Aditya P. we finally arrive at P4 table. Mathur 281 Copyright © 2013 Dorling Kindersley (India) Pvt. . Ltd Continuing with regrouping and relabeling.

When the process converges.Copyright © 2013 Dorling Kindersley (India) Pvt. and the machine is minimal. each state will be in a separate group. The next step is to obtain the distinguishing strings for each state. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 282 . Ltd k-equivalence partition: Convergence The process is guaranteed to converge.

Hence z now becomes b. Initialize z=ε. Find tables Pi and Pi+1 such that (q1. We get P3 and P4. Mathur 283 . This symbol is b.Copyright © 2013 Dorling Kindersley (India) Pvt. q2) are in the same group in Pi and different groups in Pi+1. Ltd Finding distinguishing sequences: Example Let us find a distinguishing sequence for states q1 and q2. We update z to z. Find the input symbol that distinguishes q1 and q2 in table P3. Contents Foundations of Software Testing 2E Author: Aditya P.b.

We move to the P2 table and find the input symbol that distinguishes q4 and q5. Let us select a. Let us select a as the distinguishing symbol. Mathur 284 Copyright © 2013 Dorling Kindersley (India) Pvt.The next states for q1 and q2 on b are. respectively. respectively. q3 and q2. Contents Foundations of Software Testing 2E Author: Aditya P.) . We update z to baa. Ltd Finding the distinguishing sequences: Example (contd. These two states are distinguished in P1 by a and b. Update z which now becomes ba. q4 and q5. The next states for states q4 and q5 on symbol a are.

Ltd Finding the distinguishing sequences: Example (contd.baaa).baaa)≠o(q2. Mathur 285 Copyright © 2013 Dorling Kindersley (India) Pvt. respectively. Check that o(q1. This is the farthest we can go backwards through the various tables. Contents Foundations of Software Testing 2E Author: Aditya P. baaa is the desired distinguishing sequence for states q1 and q2. Moving to the original state transition table we obtain a as the distinguishing symbol for q1 and q5 We update z to baaa. q1 and q5.) .The next states for q3 and q2 on a are.

aaa. This leads us to the following characterization set for our FSM. W={a.) Using the procedure analogous to the one used for q1 and q2. baaa} Contents Foundations of Software Testing 2E Author: Aditya P. aa.Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Finding the distinguishing sequences: Example (contd. we can find the distinguishing sequence for each pair of states. Mathur 286 .

Step 3: (a) Construct the testing tree for M and (b) generate the transition cover set P Next (a) from the testing tree. Step 4: Construct set Z from W and m. Mathur 287 Copyright © 2013 Dorling Kindersley (India) Pvt. Step 5: Desired test set=P.Z Contents Foundations of Software Testing 2E Author: Aditya P. Step 2: Construct the characterization set W for M. Ltd Chow’s method: where are we? .Step 1: Estimate the maximum number of states (m) in the correct implementation Done of the given FSM M.

the initial state. Suppose that the testing tree has been constructed until level k . If n is not a leaf node then we expand it by adding a branch from node n to a new node m if δ(n. Ltd A testing tree of an FSM is a tree rooted at the initial state. State q0. x)=m for x∈ X . Here is how we construct the testing tree. It contains at least one . This branch is labeled as x. The (k+1)th level is built as follows. Mathur 288 Copyright © 2013 Dorling Kindersley (India) Pvt.Step 3: (a) Construct the testing tree for M path from the initial state to the remaining states in the FSM. is the root of the testing tree. Select a node n at level k. This step is repeated for all nodes at level k. Contents Foundations of Software Testing 2E Author: Aditya P. If n appears at any level from 1 through k . then n is a leaf node and is not expanded any further.

Example: Construct the testing tree for M q1 becomes leaf. No further expansion possible . . q4 can be expanded. Ltd Start here. M . Mathur 289 Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. initial state is the root. .

Step 1: Estimate the maximum number of states (m) in the correct implementation Done of the given FSM M. Mathur 290 Copyright © 2013 Dorling Kindersley (India) Pvt.Z Contents Foundations of Software Testing 2E Author: Aditya P. Step 3: (a) Construct the testing tree for M and (b) generate the transition cover set P Next. (b) from the testing tree. Step 5: Desired test set=P. Step 2: Construct the characterization set W for M. Step 4: Construct set Z from W and m. Ltd Chow’s method: where are we? .

baab. The empty string (ε) also belongs to P. ba. Concatenation of the labels along the edges of a sub-path is a string that belongs to P. bb. P={ε. starting at the . Ltd A transition cover set P is a set of all strings representing sub-paths. baaa. in the testing tree. b. bab. baaab.Step 3: (b) Find the transition cover set from the testing tree root. a. Mathur 291 Copyright © 2013 Dorling Kindersley (India) Pvt. baa. baaaa} Contents Foundations of Software Testing 2E Author: Aditya P.

Step 4: Construct set Z from W and m. Next Step 5: Desired test set=P. Mathur 292 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Chow’s method: where are we? . Step 3: (a) Construct the testing tree for M and (b) generate the transition cover set P Done from the testing tree.Step 1: Estimate the maximum number of states (m) in the correct implementation Done of the given FSM M. Step 2: Construct the characterization set W for M.Z Contents Foundations of Software Testing 2E Author: Aditya P.

aaaa.. m=6 Z = W ∪ X1. Mathur 293 . aa. aa. baaa} ∪ {a.Step 4: Construct set Z from W and m Copyright © 2013 Dorling Kindersley (India) Pvt. ba. W={a. baaaa. aaa.W ={a.W For m=n. Ltd Given that X is the input alphabet and W the characterization set. baaa}. bbaaa} Contents Foundations of Software Testing 2E Author: Aditya P. b}. baaa} ={a. b}. Xm-1-n. we have: Z = X0.W ∪ …. aaa.W ∪ X1.W=W For X={a. aa. baa. aaa. aa. we get Z = X0. baaa. baaa.{a. aaa. aa.W ∪ Xm-n. aaa.

Step 4: Construct set Z from W and m. Step 2: Construct the characterization set W for M. Mathur 294 Copyright © 2013 Dorling Kindersley (India) Pvt.Z Done Next Contents Foundations of Software Testing 2E Author: Aditya P. Step 3: (a) Construct the testing tree for M and (b) generate the transition cover set P Done from the testing tree.Step 1: Estimate the maximum number of states (m) in the correct implementation Done of the given FSM M. Step 5: Desired test set=P. Ltd Chow’s method: where are we? .

3. Reset the application to the initial state after each test.Z Do the following to test the implementation: 1. 2.Step 5: Desired test set=P.Z Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd The test inputs based on the given FSM M can now be derived as: T=P.  Execute the application and check if the response matches. Foundations of Software Testing 2E Author: Aditya P.  Generate test cases for the application. there might be variables to be set before it can be exercised with elements of T.  Find the expected response to each element of T. Note that even though the application is modeled by M. Mathur Contents 295 .

Ltd Correct design t1=baaaaaa t2=baaba M1(t1)=1101001 M2(t2)=11001 M1 Foundations of Software Testing 2E Contents M2 Author: Aditya P.Example 1: Testing an erroneous application Error revealing M(t1)=1101001 M M(t2)=11011 test cases Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 296 .

Ltd Example 2: Extra state. m=6. Mathur Contents 297 . Author: Aditya P.M1 M2 t1=baaba M(t1)=11011 M1(t1)=11001 t2=baaa M(t2)=1101 M2(t2)=1100 Foundations of Software Testing 2E Copyright © 2013 Dorling Kindersley (India) Pvt. N=5.

Ltd moves the application from initial state q0 to state qj. Mathur 298 . each test case t is of the form r. Contents Foundations of Software Testing 2E Author: Aditya P.Error detection process: in-class discussion Given m=n. Then. r Copyright © 2013 Dorling Kindersley (India) Pvt. s=as’ takes it from qi to state qj or qj’.s where r is in P and s in W.

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd 5. Mathur 299 .7 The Partial W method Contents Foundations of Software Testing 2E Author: Aditya P.

Phase 2: Generate additional tests using a subset of the transition cover set and state identification sets.Tests are generated from minimal. Test generation process is divided into two phases: Phase 1: Generate a test set using the state cover set (S) and the characterization set (W). Ltd The partial W (Wp) method . Mathur 300 Copyright © 2013 Dorling Kindersley (India) Pvt. What is a state cover set? A state identification set? Contents Foundations of Software Testing 2E Author: Aditya P. and connected FSM. complete. Size of tests generated is generally smaller than that generated using the W-method.

S={ε. b. there is a string in S that takes M from its initial state to qi. Ltd Given FSM M with input alphabet X. baa. Also. Contents Foundations of Software Testing 2E Author: Aditya P. a state cover set S is a finite non-empty set of . Mathur 301 Copyright © 2013 Dorling Kindersley (India) Pvt. ba.State cover set strings over X* such that for each state qi in Q. S is not necessarily unique. baaa} S is always a subset of the transition cover set P.

there is a string in Wi that distinguishes qi from qj. s)≠ O(qj. Ltd State identification set . s) . [Wi is minimal. j≠ i .Given an FSM M with Q as the set of states.] (b) O(qi.] (c) No subset of Wi satisfies property (b). for 1≤j≤ n . Mathur 302 Copyright © 2013 Dorling Kindersley (India) Pvt.] Contents Foundations of Software Testing 2E Author: Aditya P. an identification set for state qi∈Q is denoted by Wi and has the following properties: (a) Wi⊆ W . 1≤ i≤n [Identification set is a subset of W. s∈ Wi [For each state other than qi.

aa. Ltd State identification set: Example . Mathur 303 Copyright © 2013 Dorling Kindersley (India) Pvt. a} W3={a aa} W4=W5={a.x) o(Sj.Last element of the output string Si Sj X o(Si. aaa} Foundations of Software Testing 2E 4 Contents Author: Aditya P.x) 1 2 baaa 1 0 3 aa 0 1 4 a 0 1 5 a 0 1 3 aa 0 1 4 a 0 1 5 a 0 1 4 a 0 1 5 a 0 1 5 aaa 1 0 2 3 W1=W2={baaa.

Ltd Wp method: Example: Step 1: Compute S. Wi. W3. aaa. P. b. aaa} W={a. bb. baa.W S={ε. W4. b. W. baaaa} W1=W2={baaa. a. aa. baab. ba.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 304 . baaa} W={W1. bab. baaa} P={ε. aa. a} W3={a aa} W4=W5={a. baaab. W5} Contents Foundations of Software Testing 2E Author: Aditya P. baa. W2. ba. baaa.

baaa}. ba. baa.{a. W={ε. baaa} Elements of T1 ensure that the each state of the FSM is covered and distinguished from the remaining states.Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Wp method: Example: Step 2: Compute T1 [m=n] T1=S. aaa. b. Contents Foundations of Software Testing 2E Author: Aditya P. aa. Mathur 305 .

Ltd Wp method: Example: Step 3: Compute R and δ [m=n] ba. b. bab. a.R=P-S={ε. baaa} ={a. baaaa} Let each element of R be denoted as ri1. b. Copyright © 2013 Dorling Kindersley (India) Pvt. baa. baa. ri2. m)=qij . δ(rik.…rik. baab. baaab. baaab. baaa. baaaa}-{ε. ba. bb. bb. bab. where m∈X (the alphabet) Contents Foundations of Software Testing 2E Author: Aditya P. baab. Mathur 306 .

a)=q1 δ(q1. baabaaa} ∪ {baaaba. baaaaaa. baab)=q5 δ(q1.W4 ) ∪ ({bab}. bb)=q4 δ(q1. baaaaa} Contents Foundations of Software Testing 2E Author: Aditya P.W5 ) ∪ ({baaaa}.W5 ) ∪ ({baab}. aaa. W1 ) ={abaaa. babaaa} ∪ {baaba.W5 ) ∪ {baaab}.Wp method: Example: Step 4: Compute T2 [m=n] δ(q1. baaab)=q5 δ(q1. bab)=q5 T2=({a}. Wij . baaabaaa} ∪ {baaaabaaa. W1 )∪ ({bb}. where Wij is the identification set for state qij. Mathur 307 . Ltd T2=R⊗W=∪k(j=1) (rij}. δ(q1. baaaa)=q1 Copyright © 2013 Dorling Kindersley (India) Pvt. bbaaa} ∪ {baba. aa} ∪ {bba.

Ltd Wp method: Example: Savings Test set size using the W method= 44 Test set size using the Wp method= 34 (20 from T1+14 from T2) Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 308 .Copyright © 2013 Dorling Kindersley (India) Pvt.

Ltd Testing proceeds in two phases. Contents Foundations of Software Testing 2E Author: Aditya P. Tests from T2 are applied in phase 2. Tests from T1 are applied in phase 1. even when tests from phase cover all transitions. they do not ensure all transition coverage. Mathur 309 . they do not apply the state identification sets and hence not all transfer errors are guaranteed to be revealed by these tests.Testing using the Wp method Copyright © 2013 Dorling Kindersley (India) Pvt. Also. While tests from phase 1 ensure state coverage.

X[m-n]. Ltd Wp method: Both sets T1 and T2 are computed a bit differently.Copyright © 2013 Dorling Kindersley (India) Pvt. where X[m-n] is the set union of Xi . 1≤i≤ (m-n) T2= T2=R. Mathur 310 . X[m-n] ⊗W Contents Foundations of Software Testing 2E Author: Aditya P. as follows: T1=S.

Mathur 311 . Ltd 5.Copyright © 2013 Dorling Kindersley (India) Pvt.8 The UIO sequence method [See the text] Contents Foundations of Software Testing 2E Author: Aditya P.

Mathur 312 .Copyright © 2013 Dorling Kindersley (India) Pvt.9 Automata theoretic versus control flow based techniques Contents Foundations of Software Testing 2E Author: Aditya P. Ltd 5.

Let us understand the difference between the two types of techniques and their fault detection abilities. Control theoretic techniques . Ltd Automata-theoretic vs. In contrast.The W and the Wp methods are considered automata-theoretic methods for test generation. many books on software testing mention control-theoretic techniques for test generation. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 313 Copyright © 2013 Dorling Kindersley (India) Pvt.

Ltd State cover: A test set T is considered adequate with respect to the state cover criterion for an FSM M if the execution of M against each element of T causes each state in M to be visited at least once. Mathur 314 . Transition cover: A test set T is considered adequate with respect to the branch/ transition cover criterion for an FSM M if the execution of M against each element of T causes each transition in M to be taken at least once Contents Foundations of Software Testing 2E Author: Aditya P.Control theoretic techniques Copyright © 2013 Dorling Kindersley (India) Pvt.

b) and qi. tr2) in M to be taken at least once.Copyright © 2013 Dorling Kindersley (India) Pvt. qj.) Switch cover: A test set T is considered adequate with respect to the 1-switch cover criterion for an FSM M if the execution of M against each element of T causes each pair of transitions (tr1. Mathur 315 . where for some input substring ab tr1: qi=δ(qj. Contents Foundations of Software Testing 2E Author: Aditya P. a) and tr_2: qk= δ(qi. Ltd Control theoretic techniques (contd. qk are states in M.

Ltd Control theoretic techniques (contd.) . Exiting the loop upon arrival covers the ``boundary" condition and entering it and traversing the loop at least once covers the ``interior" condition. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 316 Copyright © 2013 Dorling Kindersley (India) Pvt.Boundary interior cover: A test set T is considered adequate with respect to the boundary-interior cover criterion for an FSM M if the execution of M against each element of T causes each loop (a self-transition) across states to be traversed zero times and at least once.

a correct one (M1) and one with a transfer error . Mathur 317 Copyright © 2013 Dorling Kindersley (India) Pvt. t=abba covers all states but does not not reveal the error. Both machines generate the same output which is 0111. Will the tests generated by the W method reveal this error? Check it out! Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Consider the following machines.Control theoretic technique: Example 1 (M1’).

aaba. such as (tr1. abbaab}.Control theoretic technique: Example 2 (M2’). Mathur 318 Copyright © 2013 Dorling Kindersley (India) Pvt. Consider the test set: {bb. Ltd Consider the following machines. Does it cover all branches? Does it reveal the error? Are the states in M2 1-distinguishable? Contents Foundations of Software Testing 2E Author: Aditya P. tr6. aabb. tr2). There are 12 branch pairs. a correct one (M2) and one with a transfer error . tr3). (tr1. tr5). baab.

Ltd Consider the following machines.Control theoretic technique: Example 3 (M3’). a correct one (M3) and one with a transfer error not traversed. T1 causes each state to be entered but loop Copyright © 2013 Dorling Kindersley (India) Pvt. T2 causes each loop to be traversed once. Mathur 319 . t2: abaab}. Consider T={t1: aab. Is the error revealed by T? Contents Foundations of Software Testing 2E Author: Aditya P.

and minimal. What happens if it is not? Contents Foundations of Software Testing 2E Author: Aditya P. connected. transfer errors. Tests so generated are guaranteed to detect all operation errors. GUIs can also be modeled using FSMs The W and the Wp methods are automata theoretic methods to generate tests from a given FSM model. Ltd Behavior of a large variety of applications can be modeled using finite state . Mathur 320 Copyright © 2013 Dorling Kindersley (India) Pvt. and missing/extra state errors in the implementation given that the FSM representing the implementation is complete.Summary machines (FSM).

that are often described in books on software testing. Mathur 321 .Summary (contd. state cover.) Copyright © 2013 Dorling Kindersley (India) Pvt. and n-switch cover. Ltd Automata theoretic techniques generate tests superior in their fault detection ability than their control-theoretic counterparts. Contents Foundations of Software Testing 2E Author: Aditya P. include branch cover. boundary-interior. The size of tests sets generated by the W method is larger than generated by the Wp method while their fault detection effectiveness are the same. Control-theoretic techniques.

2013 Foundations of Software Testing 2E Contents Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 322 . Ltd Chapter 6 Test Generation: Combinatorial Designs Updated: July 16.

§  What are test configurations? How do they differ from test sets? §  Why combinatorial design? §  What are Latin squares and mutually orthogonal Latin squares (MOLS)? §  How does one generate test configurations from MOLS? §  What are orthogonal arrays. Ltd Learning Objectives Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 323 . covering arrays and mixed-level covering arrays? §  How to generate mixed-level covering arrays and test configurations from them? Copyright © 2013 Dorling Kindersley (India) Pvt.

1. Test configuration and test set Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd 6.1. Mathur 324 .

known as a test configuration.§  Software applications are often designed to work in a variety of environments. Contents Foundations of Software Testing 2E Author: Aditya P. §  Each environment corresponds to a given set of values for each factor. Ltd Test configuration . §  An environment is characterized by combination of hardware and software. lead to a variety of environments. network connection. and hardware platform. Mathur 325 Copyright © 2013 Dorling Kindersley (India) Pvt. Combinations of factors such as the operating system.

The number of such test configurations could be exorbitantly large making it impossible to test the application exhaustively. can be combined to create several test configurations for a printer. or environments. the application must be tested under as many test configurations. Dial-up connection. §  Different versions of operating systems and printer drivers. and a PC with 512MB of main memory. as possible. Ltd Test configuration: Example . §  To ensure high reliability across the intended environments.§  Windows XP. Mathur 326 Copyright © 2013 Dorling Kindersley (India) Pvt. is one possible configuration. Contents Foundations of Software Testing 2E Author: Aditya P.

Contents Foundations of Software Testing 2E Author: Aditya P. §  Techniques we shall learn are useful in deriving test configurations as well as test sets. Ltd Test configuration and test set . a test set is a collection of test cases. Each test case consists of input values and expected output. Mathur 327 Copyright © 2013 Dorling Kindersley (India) Pvt.§  While a test configuration is a combination of factors corresponding to hardware and software within which an application is to operate.

Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 328 Copyright © 2013 Dorling Kindersley (India) Pvt. §  For example. each test run of a program often requires at least one value for each variable.§  While testing a program with one or more input variables. a program to find the greatest common divisor of two integers x and y requires two values. Ltd Motivation . one corresponding to x and the other to y.

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Motivation [2] While equivalence partitioning discussed earlier offers a set of guidelines to design test cases. (b) It lacks guidelines on how to select inputs from various sub-domains in the partition. Mathur 329 . Contents Foundations of Software Testing 2E Author: Aditya P. it suffers from two shortcomings: (a) It raises the possibility of a large number of sub-domains in the partition.

The number of sub-domains in a partition of the input domain increases in direct proportion to the number and type of input variables. does not account for the possibility of faults in the program under test that arise due to specific interactions amongst values of different input variables. and especially so when multidimensional partitioning is used. Once a partition is determined. Contents Foundations of Software Testing 2E Author: Aditya P. especially when using uni-dimensional equivalence partitioning. Mathur 330 Copyright © 2013 Dorling Kindersley (India) Pvt. Such a selection procedure. one selects at random a value from each of the subdomains. Ltd Motivation [3] .

Contents Foundations of Software Testing 2E Author: Aditya P. is large and complex. Mathur 331 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Motivation [4] . other interactions in the input domain might remain untested. We will learn several techniques for generating test configurations or test sets that are small even when the set of possible configurations or the input domain and the number of sub-domains in its partition.While boundary values analysis leads to the selection of test cases that test a program at the boundaries of the input domain.

Modeling the input and configuration spaces Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 332 .2. Ltd 6.1.Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 333 Copyright © 2013 Dorling Kindersley (India) Pvt. The configuration space of P consists of all possible settings of the environment variables under which P could be used. Contents Foundations of Software Testing 2E Author: Aditya P. Consider program P that takes two integers x>0 and y>0 as inputs. Ltd Modeling: Input and configuration space [1] . The input space of P is the set of all pairs of positive non-zero integers.The input space of a program P consists of k-tuples of values that could be input to P during execution.

and must be able to print to a local or a networked printer. Contents Foundations of Software Testing 2E Author: Aditya P. and Z a local or a networked printer. Y a browser. The configuration space of P consists of triples (X. through the Netscape or Safari browsers.Now suppose that this program is intended to be executed under the Windows and the MacOS operating system. Ltd Modeling: Input and configuration space [2] . Y. Mathur 334 Copyright © 2013 Dorling Kindersley (India) Pvt. Z) where X represents an operating system.

Contents Foundations of Software Testing 2E Author: Aditya P. X2.. The inputs are also referred to as test parameters or as values. . We refer to the inputs as factors.Xn. Let us assume that each factor may be set at any one from a total of ci.Consider a program P that takes n inputs corresponding to variables X1. Each value assignable to a factor is known as a level. |F| refers to the number of levels for factor F. 1≤ i ≤ n values. Ltd Factors and levels . Mathur 335 Copyright © 2013 Dorling Kindersley (India) Pvt.

f). (c. respectively. e). is known as a factor combination. Let us say that during an execution of P. Thus. Contents Foundations of Software Testing 2E Author: Aditya P.A set of values. f). (a. one for each factor. we have 2 factors and 3 levels for each factor. (b. c} and {d. This leads to a total of 32=9 factor combinations. Mathur 336 Copyright © 2013 Dorling Kindersley (India) Pvt. b. d). (c. (b. X and Y may each assume a value from the set {a. and (c. d). (a. For example. e). e. namely (a. f}. f). (b. d). Ltd Factor combinations . e). suppose that program P has two input variables X and Y.

Mathur 337 Copyright © 2013 Dorling Kindersley (India) Pvt. the total number of factor combinations is nk. Suppose now that each factor combination yields one test case. Contents Foundations of Software Testing 2E Author: Aditya P. if a program has 15 factors with 4 levels each. For many programs. For example. Ltd Factor combinations: Too large? .In general. the number of tests generated for exhaustive testing could be exorbitantly large. for k factors with each factor assuming a value from a set of n values. Executing a billion tests might be impractical for many software applications. the total number of tests is 415 ~109.

Let us denote these four factors by S. and P. Contents Foundations of Software Testing 2E Author: Aditya P. A. Mathur 338 Copyright © 2013 Dorling Kindersley (India) Pvt. and schedules Pizza for delivery. Delivery address and a home phone number. Toppings list.A PDS takes orders online. T. A customer is required to specify the following four items as part of the online order: Pizza size. Ltd Example: Pizza Delivery Service (PDS) [1] . respectively. checks for their validity.

and the zip code. The phone number is a numeric string possibly containing the dash (``--") separator. the customer can customize the toppings. Mathur 339 Copyright © 2013 Dorling Kindersley (India) Pvt. and Small. Ltd Pizza Delivery Service (PDS): Specs . In addition. Medium. The delivery address consists of customer name. city. one line of address. There is a list of 6 toppings from which to select. Contents Foundations of Software Testing 2E Author: Aditya P.Suppose now that there are three varieties for size: Large.

The total number of factor combinations is 24+23=24. Suppose we consider 6+1=7 levels for Toppings. Mathur 340 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd PDS: Input space model . Different types of values for Address and Phone number will further increase the combinations Contents Foundations of Software Testing 2E Author: Aditya P. Number of combinations= 24+5x23+23+5x22=84.

and Format. we have a total 43=64 factor combinations. Ltd The Graphical User Interface of application T consists of three menus labeled File. Thus. Contents Foundations of Software Testing 2E Author: Aditya P. We have three factors in T.Example: Testing a GUI Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 341 . Edit. Each of these three factors can be set to any of four levels.

.. The levels listed in Table 11. Mathur 342 .Example: The UNIX sort utility Copyright © 2013 Dorling Kindersley (India) Pvt. sort [-cmu] [-ooutput] [-Tdirectory] [-y [ kmem]] [-zrecsz] [-dfiMnr] [-b] [ tchar] [kkeydef] [+pos1[-pos2]] [file.1 of the book lead to a total of approximately 1.9x109 combinations. Ltd The sort utility has several options and makes an interesting example for the identification of factors and levels.] We have identified a total of 20 factors for the sort command. The command line for sort is given below. Contents Foundations of Software Testing 2E Author: Aditya P.

OS. Ltd There is often a need to test a web application on different platforms to ensure that any claim such as ``Application X can be used under Windows and Mac OS X” are valid. Mathur 343 . operating system. and browser combinations. it is easy to obtain three factors. Here we consider a combination of hardware. Contents Foundations of Software Testing 2E Author: Aditya P. i.Example: Compatibility testing Copyright © 2013 Dorling Kindersley (India) Pvt. Let X denote a Web application to be tested for compatibility. Given that we want X to work on a variety of hardware.e. and a browser as a platform. hardware. and browser. OS.

Ltd Compatibility testing: Factor levels Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 344 .Copyright © 2013 Dorling Kindersley (India) Pvt.

Similarly. we assume that this is not the case for testing application X. some of these combinations are infeasible.2 is an OS for the Apple computers and not for the Dell Dimension series PCs. Contents Foundations of Software Testing 2E Author: Aditya P.Compatibility testing: Combinations For example. However. Mac OS10. . Ltd There are 75 factor combinations. the Safari browser is used on Apple computers and not on the PC in the Dell Series. While various editions of the Windows OS can be used on an Apple computer using an OS bridge such as the Virtual PC. Mathur 345 Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 346 Copyright © 2013 Dorling Kindersley (India) Pvt. Note that there is a large number of hardware configurations under the Dell Dimension Series. Contents Foundations of Software Testing 2E Author: Aditya P. Pentium versus Athelon. Thus. e. in all we are left with 35 platforms on which to test X.g.The discussion above leads to a total of 40 infeasible factor combinations corresponding to the hardware-OS combination and the hardware-browser combination. These configurations are obtained by selecting from a variety of processor types. and several others. memory sizes. processor speeds. Ltd Compatibility testing: Reduced combinations .

Contents Foundations of Software Testing 2E Author: Aditya P. and hence the time to test.While testing against all configurations will lead to more thorough testing of application X. Ltd Compatibility testing: Reduced combinations-2 . it will also increase the number of factor combinations. Mathur 347 Copyright © 2013 Dorling Kindersley (India) Pvt.

Combinatorial test design process Contents Foundations of Software Testing 2E Author: Aditya P.2. Ltd 6. Mathur 348 .Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 349 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Combinatorial test design process .Modeling of input space or the environment is not exclusive and one might apply either one or both depending on the application under test. Contents Foundations of Software Testing 2E Author: Aditya P.

Ltd Step 1: Model the input space and/or the configuration space. Contents Foundations of Software Testing 2E Author: Aditya P. The model is expressed in . Steps 2 and 3 can be automated. Step 3: The combinatorial object generated is used to design a test set or a test configuration as the requirement might be.Combinatorial test design process: steps terms of factors and their respective levels. Mathur 350 Copyright © 2013 Dorling Kindersley (India) Pvt. Step 2: The model is input to a combinatorial design procedure to generate a combinatorial object which is simply an array of factors and levels. Such an object is also known as a factor covering design.

Mathur 351 Contents Copyright © 2013 Dorling Kindersley (India) Pvt. consider the combination in which all factors are set to ``Unused" except the -o option which is set to ``Valid File" and the file option that is set to ``Exists.” Two sample test cases are: t1: sort -o afile bfile t2: sort -o cfile dfile Is one of the above tests sufficient? Foundations of Software Testing 2E Author: Aditya P.Combinatorial test design process: test inputs many test inputs. For example. Ltd Each combination obtained from the levels listed in Table 6.1 can be used to generate .

Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 352 Copyright © 2013 Dorling Kindersley (India) Pvt. the factor combinations do not indicate in any way the sequence in which the generated tests are to be applied to the program under test. Further. The sequencing of tests generated by most test generation techniques must be determined by the tester and is not a unique characteristic of test generated in combinatorial testing.Combinatorial test design process: summary case. Ltd Combination of factor levels is used to generate one or more test cases. For each test . This sequence too must be determined by the tester. the sequence in which inputs are to be applied to the program under test must be determined by the tester.

3. Mathur 353 . Ltd 6. Fault model Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.

Contents Foundations of Software Testing 2E Author: Aditya P. We say that an interaction fault is triggered when a certain combination of t≥1 input values causes the program containing the fault to enter an invalid state. Of course. this invalid state must propagate to a point in the program execution where it is observable and hence is said to reveal the fault. Mathur 354 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Fault model .Faults aimed at by the combinatorial design techniques are known as interaction faults.

for any arbitrary value of t. Mathur 355 Copyright © 2013 Dorling Kindersley (India) Pvt. In general. Contents Foundations of Software Testing 2E Author: Aditya P. i. Ltd t-way interaction faults . are known as simple faults. t=1. regardless of the values of other input variables. the faults are known as t--way interaction faults.Faults triggered by some value of an input variable. For t=2. the faults are known as pairwise interaction faults.e.

y) when X=x1 and Y=y1. z)-g(x. Ltd Pairwise interaction fault: Example . This is a pairwise interaction fault due to the interaction between factors X and Y. Mathur 356 Copyright © 2013 Dorling Kindersley (India) Pvt. Foundations of Software Testing 2E Contents Author: Aditya P. y.Correct output: f(x.

z=1 and x=-1. y=1. Ltd 3-way interaction fault: Example . However. z=1.This fault is triggered by all inputs such that x+y≠x-y and z ≠ 0. Mathur 357 Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. the fault is revealed only by the following two of the eight possible input combinations: x=-1. y=-1.

V is considered as a t-fault vector if any t ≤ k elements in V are needed to trigger a fault in P.. 1≤ i ≤ k levels. l2. each at qi.. a vector V of factor levels is (l1..Given a set of k factors f1. Mathur 358 Copyright © 2013 Dorling Kindersley (India) Pvt.. 1 ≤ i ≤ k is a specific level for the corresponding factor. Note that a t-way fault vector for P triggers a t-way fault in P. f2. where li. lk). A run V is a fault vector for program P if the execution of P against a test case derived from V triggers a fault in P. fk... V is also known as a run. Ltd Fault vectors . Contents Foundations of Software Testing 2E Author: Aditya P.

1. *) is a 2-way fault vector given that the values x1 and y1 trigger the twoway fault. Foundations of Software Testing 2E Contents Author: Aditya P. Mathur 359 Copyright © 2013 Dorling Kindersley (India) Pvt. (x1.1. 1) are three fault vectors that trigger the 3-way fault.The input domain consists of three factors x. Of these eight runs. (-1. y. 1) and (-1. and z each having two levels. (1. 1) and (-1. y1. For example. 0) are two runs. -1. There is a total of eight runs. -1. Ltd Fault vectors: Example .

Ltd Goal reviewed The goal of the test generation techniques described in this chapter is to generate a sufficient number of runs such that tests generated from these runs reveal all t-way faults in the program under test.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 360 . Contents Foundations of Software Testing 2E Author: Aditya P.

Mathur 361 Copyright © 2013 Dorling Kindersley (India) Pvt.The number of such runs increases with the value of t.. t +k-1. and k-way runs also. while generating t-way runs. Contents Foundations of Software Testing 2E Author: Aditya P. Hence. Ltd Goal reviewed . . In many situations. t+2. there is always a chance that runs generated with t=2 reveal some higher level interaction faults. one automatically generates some t+1. Of course.. t is set to 2 and hence the tests generated are expected to reveal pairwise interaction faults.

Mathur 362 .4.Copyright © 2013 Dorling Kindersley (India) Pvt. Latin squares Contents Foundations of Software Testing 2E Author: Aditya P. Ltd 6.

2. A Latin square of order n is an n x n matrix such . in a square arrangement. 3}. etc. Mathur 363 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Let S be a finite set of n symbols.Latin Squares that no symbol appears more than once in a row and column. Contents Foundations of Software Testing 2E Author: Aditya P. B. Latin squares of order 3. S={A. C. S={1. B}. The term ``Latin square" arises from the fact that the early versions used letters from the Latin alphabet A. Latin squares of order 2.

Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 364 . Ltd Larger Latin Squares Larger Latin squares of order n can be constructed by creating a row of n distinct symbols. For example. Additional rows can be created by permuting the first row. here is a Latin square M of order 4 constructed by cyclically rotating the first row and placing successive rotations in subsequent rows.Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 365 Copyright © 2013 Dorling Kindersley (India) Pvt. 1≤ (i. For example. Ltd Modulo arithmetic and Latin Squares . A Latin square based on integers 0. 1… n is said to be in standard form if the elements in the top row 0 and the leftmost column are arranged in order. Contents Foundations of Software Testing 2E Author: Aditya P. j) ≤ 4. the Latin square M of order 4 given below is constructed such that M(i.A Latin square of order n>2 can also be constructed easily by doing modulo arithmetic. j)=i+j (mod 4).

Mutually orthogonal Latin squares Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 366 .5. Ltd 6.

i. the elements in the ith row and jth column of M1 and M2. i. each of order n. we simply juxtapose the corresponding elements of M1 and M2.e. We now create an n x n matrix M from M1 and M2 such that the L(i. then M1 and M2 are said to be mutually orthogonal Latin squares of order n. If each element of M is unique. respectively. Ltd Let M1 and M2 be two Latin squares. j) and M2(i. j)M2(i. Mathur 367 Copyright © 2013 Dorling Kindersley (India) Pvt. Let M1(i. j) .e. j). it appears exactly once in M.Mutually Orthogonal Latin Squares (MOLS) denote. Contents Foundations of Software Testing 2E Author: Aditya P. j) is M1(i.

MOLS of order 3 follow. Mathur 368 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd There are no MOLS of order 2. . Contents Foundations of Software Testing 2E Author: Aditya P. Its elements are unique and hence M1 and M2 are MOLS.MOLS: Example Juxtaposing the corresponding elements gives us L.

or a power of prime. When n is prime. The number of MOLS of order n is denoted by N(n). N(n)=n-1. Numbers 2 and 6 are known as Eulerian numbers after the famous mathematician Leonhard Euler (1707-1783). Contents Foundations of Software Testing 2E Author: Aditya P. Such a set of MOLS is a complete set. Mathur 369 Copyright © 2013 Dorling Kindersley (India) Pvt. When n is prime or a power of prime. MOLS do not exist for n=2 and n=6 but they do exist for all other values of n>2. MOLS(n) contains n-1 mutually orthogonal Latin squares.MOLS(n) is the set of MOLS of order n. Ltd MOLS: How many of a given order? .

4. Mathur 370 . 3. 2. Ltd MOLS: Construction [1] Example: We begin by constructing a Latin square of order 5 given the symbol set S={1. Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. 5}.

Contents Foundations of Software Testing 2E Author: Aditya P.Next. Mathur 371 Copyright © 2013 Dorling Kindersley (India) Pvt. we obtain M2 by rotating rows 2 through 5 of M1 by two positions to the left. Ltd MOLS: Construction [2] .

M2. respectively. It is easy to check that indeed the elements of MOLS(5) are mutually orthogonal by superimposing them pairwise. Thus. M4}. we get MOLS(5)={M1. M3. Mathur 372 Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P.MOLS: Construction [3] positions. Ltd M3 and M4 are obtained similarly but by rotating the first row of M1 by 3 and 4 .

Mathur 373 Copyright © 2013 Dorling Kindersley (India) Pvt. limitation . The CRC Handbook of Combinatorial Designs gives a large table of MOLS.The method illustrated in the previous example is guaranteed to work only when constructing MOLS(n) for n that is prime or a power of prime. the maximum size of MOLS(n) is n-1. For other values of n. There is no general method available to construct the largest possible MOLS(n) for n that is not a prime or a power of prime. Ltd MOLS: Construction. Contents Foundations of Software Testing 2E Author: Aditya P.

Pairwise designs: Binary factors Contents Foundations of Software Testing 2E Author: Aditya P. Ltd 6.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 374 .6.

We will now look at a simple technique to generate a subset of factor combinations from the complete set. Only 2-valued. factors are considered. This assumption will be relaxed later. Mathur 375 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Pairwise designs . Each combination selected generates at least one test input or test configuration for the program under test. Contents Foundations of Software Testing 2E Author: Aditya P. or binary. Each factor can be at one of two levels.

Pairwise designs: Example variable. All possible combinations of these three factors follow. Considering each input variable as a factor. {Y1. and Z denote the three input variables and {X1. one corresponding to each input . Let X. Contents Foundations of Software Testing 2E Author: Aditya P. {Z1. Ltd Suppose that a program to be tested requires 3 inputs. Y. Each variable can take only one of two distinct values. Z2} their respective sets of values. X2}. Y2}. the total number of factor combinations is 23. Mathur 376 Copyright © 2013 Dorling Kindersley (India) Pvt.

(X2. Z1). Contents Foundations of Software Testing 2E Author: Aditya P. (Y1.Pairwise designs: Reducing the combinations There are 12 such pairs: (X1. Z1). (X2. Y1). and (Y2. Z2). (Y1. Z2). Z1). Z2). (X1. It is a balanced design because each value occurs exactly the same number of times. . Z1). Mathur 377 Copyright © 2013 Dorling Kindersley (India) Pvt. (Y2. (X2. Y2). There are several sets of four combinations that cover all 12 pairs. (X1. (X1. Y1). The following four combinations cover all pairs: The above design is also known as a pairwise design. Z2). Y2). Ltd Now suppose we want to generate tests such that each pair appears in at least one test. (X2.

Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Example: ChemFun applet . We refer to the inputs as factors. For simplicity we assume that each input has exactly two possible values. Mathur 378 Copyright © 2013 Dorling Kindersley (India) Pvt. The applet has 5 inputs listed after the next slide with their possible values.A Java applet ChemFun allows its user to create an in-memory database of chemical elements and search for an element.

Ltd Example: ChemFun applet Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 379 .Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 380 .Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Example: ChemFun applet: Factor identification Contents Foundations of Software Testing 2E Author: Aditya P.

Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 381 . Ltd ChemFun applet: Input/Output Input: n=5 factors Output: A set of factor combinations such that all pairs of input values are covered.

Mathur 382 . k>0. S2k-1= For k=3 we have S5= 10 and for k=2. S3= 3. Hence the desired integer k=3. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Compute the smallest integer k such that n≤ |S2k-1| S2k-1: Set of all binary strings of length 2k-1.ChemFun applet: Step 1 Copyright © 2013 Dorling Kindersley (India) Pvt.

Ltd ChemFun applet: Step 2 . Contents Foundations of Software Testing 2E Author: Aditya P.Select any subset of n strings from S2k-1. We have. We select first five of the 10 strings in S5. k=3 and we have the following strings in the set S5. Mathur 383 Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 384 . Ltd ChemFun applet: Step 3 Append 0's to the end of each selected string. Contents Foundations of Software Testing 2E Author: Aditya P. This will increase the size of each string from 2k-1 to 2k.Copyright © 2013 Dorling Kindersley (India) Pvt.

X2. where the value of each variable is selected depending on whether the bit in column i. Contents Foundations of Software Testing 2E Author: Aditya P. Xn). Mathur 385 Copyright © 2013 Dorling Kindersley (India) Pvt.…. Ltd ChemFun applet: Step 4 . 1≤ i ≤ n. is a 0 or a 1.Each combination is of the kind (X1.

Mathur 386 .) Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd The following factor combinations by replacing the 0s and 1s in each column by the corresponding values of each factor. Contents Foundations of Software Testing 2E Author: Aditya P.ChemFun applet: Step 4 (contd.

Mathur 387 .Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd ChemFun applet: tests Contents Foundations of Software Testing 2E Author: Aditya P.

Recall that the total number of combinations is 32. Mathur 388 Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd ChemFun applet: All tests . Requiring only pairwise coverage reduces the tests to 6.

7.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 389 . Ltd 6. Pairwise designs: Multi-valued factors Contents Foundations of Software Testing 2E Author: Aditya P.

Mathur 390 . Ltd Next we will learn how to use MOLS to construct test configurations when: Contents Foundations of Software Testing 2E Author: Aditya P. •  The number of levels for each factor is more than two.Pairwise designs: Multi-valued factors •  The number of factors is two or more. Copyright © 2013 Dorling Kindersley (India) Pvt. •  All factors have the same number of levels.

Contents Foundations of Software Testing 2E Author: Aditya P. The submission of the sample itself is done using a software application available from AGTC. Several genomics facilities are available that allow a DNA sample to be submitted for sequencing. One such facility is offered by The Applied Genomics Technology Center (AGTC) at the School of Medicine in Wayne State University. Mathur 391 . We refer to this software as AGTCS.Multi-valued factors: Sample problem Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd DNA sequencing is a common activity amongst biologists and other researchers.

Sample problem (contd. the user of AGTCS. Ltd AGTCS is supposed to work on a variety of platforms that differ in their hardware . the hardware platform and the operating system are two factors to be considered while developing a test plan for AGTCS. In addition. Thus. For simplicity we consider a total of four factors with their respective levels given next. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 392 Copyright © 2013 Dorling Kindersley (India) Pvt. must either have a profile already created with AGTCS or create a new one prior to submitting a sample.) and software configurations. AGTCS supports only a limited set of browsers. referred to as PI.

We want to test under enough configurations so that all possible pairs of factor levels are covered. Ltd DNA sequencing: factors and levels . Contents Foundations of Software Testing 2E Author: Aditya P.There are 64 combinations of the factors listed. As PCs and Macs run their dedicated operating systems. Mathur 393 Copyright © 2013 Dorling Kindersley (India) Pvt. the number of combinations reduces to 32.

Ltd DNA sequencing: Approach to test design .We can now proceed to design test configurations in at least two ways. Exercise 6. Contents Foundations of Software Testing 2E Author: Aditya P. The approach used in this example is to arrive at a common set of test configurations that obey the constraint related to the operating systems. One way is to treat the testing on PC and Mac as two distinct problems and design the test configurations independently.12 asks you to take this approach and explore its advantages over the second approach used in this example. Mathur 394 Copyright © 2013 Dorling Kindersley (India) Pvt.

|F2’|=4. hardware. respectively. F3’. |F3’|=4. and PI. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 395 Copyright © 2013 Dorling Kindersley (India) Pvt. browser. where F1’. and F4’ denote. |F1’|=2. Output: A set of factor combinations such that all pairwise combinations are covered. Ltd DNA sequencing: Test design algorithm . OS. |F4’|=2. F2’.Input: n=4 factors.

Doing so gives us F1=F2'. b=k=4. F2. Note that a different assignment is also possible because |F1|=|F4|and |F2|=|F3|. F2=F3'.Test design algorithm: Step 1 Copyright © 2013 Dorling Kindersley (India) Pvt. F4=F4'. F3. Let b=|F1|=4 and k=|F2|=4 Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Reliable the factors as F1. F3=F1'. F4 such that |F1|≥|F2| ≥ |F3| ≥ |F4|. Mathur 396 .

Ltd Test design algorithm: Step 2 Prepare a table containing 4 columns and b x k=16 rows divided into 4 blocks. F2. Label the columns as F1. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 397 . … Fn. Each block contains k rows.Copyright © 2013 Dorling Kindersley (India) Pvt.

Fill Block 1 of column F2 with the sequence 1... 2's in Block 2. Mathur 398 .Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Test design algorithm: Step 3 (contd. k in rows 1 through k (k=4)..) Fill column F1 with 1's in Block 1. 2. and so on.

Test design algorithm: Step 4 Copyright © 2013 Dorling Kindersley (India) Pvt. We choose the following set of MOLS of order 4. we can use the procedure described earlier. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 399 . Ltd Find MOLS of order 4. As 4 is a power of prime.

Test design algorithm: Step 5 From M2 Copyright © 2013 Dorling Kindersley (India) Pvt. An entry marked with an asterisk (*) indicates an invalid level. Ltd From M1 Fill the remaining two columns of the table constructed earlier using columns of M1 for F3 and M2 for F4. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 400 . A boxed entry in each row indicates a pair that does not satisfy the operating system constraint.

Contents Foundations of Software Testing 2E Author: Aditya P.. we need to resolve two problems before we get to the design of test configurations. Ltd Test design algorithm: Step 6 [1] . These infeasible values are marked with an asterisk. However. Problem 1: Factors F3 and F4 can only assume values 1 and 2 whereas the table above contains other infeasible values for these two factors. we can obtain 16 distinct test configurations for AGTCS.Using the 16 entries in the table above. Solution: One simple way to get rid of the infeasible values is to replace them by an arbitrarily selected feasible value for the corresponding factor. Mathur 401 Copyright © 2013 Dorling Kindersley (India) Pvt.

Foundations of Software Testing 2E Author: Aditya P. Four such configurations are highlighted in the design by enclosing the corresponding numbers in rectangles. Here we are assume that one is not using Virtual PC on the Mac. Here is an example: F1: Operating system=1(Win 2000) F3: Hardware=2 (Mac) is infeasible. Mathur Contents 402 Copyright © 2013 Dorling Kindersley (India) Pvt.Problem 2: Some configurations do not satisfy the operating system constraint. Ltd Test design algorithm: Step 6 [2] .

Mathur 403 Copyright © 2013 Dorling Kindersley (India) Pvt. (F1=3. Consider block 3. Removing Row~3 will leave the following five pairs uncovered: (F1=3. F4=2). Contents Foundations of Software Testing 2E Author: Aditya P.Delete rows with conflicts?: Obviously we cannot delete these rows as that would leave some pairs uncovered. F2=3). and (F3=1. F3=1). Ltd Test design algorithm: Step 6 [3] . (F2=3. (F2=3. F4=2). F4=2).

Mathur 404 . Step 2: Add new configurations that cover the pairs that are left uncovered when we replace the highlighted rows. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Proposed solution: We follow a two step procedure to remove the highlighted configurations and retain complete pairwise coverage.Test design algorithm: Step 6 [4] Copyright © 2013 Dorling Kindersley (India) Pvt. Step 1: Modify the four highlighted rows so they do not violate the constraint.

Mathur 405 .Test design algorithm: Step 6 [5] F2: Browser F4: PI F3: Hardware Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd F1: OS Contents Foundations of Software Testing 2E Author: Aditya P.

Can we remove some rows from the design without affecting pairwise coverage? Contents Foundations of Software Testing 2E Author: Aditya P.Test design algorithm: Design configurations Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 406 . Ltd We can easily construct 20 test configurations from the design obtained. This is in contrast to 32 configurations obtained using a brute force method.

While the MOLS approach assists with the generation of a balanced design in that all interaction pairs are covered an equal number of times.Shortcomings of using MOLS Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd A sufficient number of MOLS might not exist for the problem at hand. Mathur 407 . the number of test configurations is often larger than what can be achieved using other methods.

Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 408 .8. Orthogonal Arrays Contents Foundations of Software Testing 2E Author: Aditya P. Ltd 6.

k.Orthogonal arrays An orthogonal array. Mathur 409 Copyright © 2013 Dorling Kindersley (India) Pvt. s. is an N x k matrix in which the entries are from a finite set S of s symbols such that any N x t sub array contains each t-tuple exactly the same number of times. Foundations of Software Testing 2E Contents Author: Aditya P. Ltd Examine this matrix and extract as many properties as you can: . such as the one above. Such an orthogonal array is denoted by OA(N. t).

and F3 to indicate the three factors. Note that the value of parameter k is 3 and hence we have labeled the columns as F1. 3. 2). 2}. Contents Foundations of Software Testing 2E Author: Aditya P. This array is denoted as OA(4. Ltd Orthogonal arrays: Example . Mathur 410 Copyright © 2013 Dorling Kindersley (India) Pvt. 2. It uses symbols from the set {1.The following orthogonal array has 4 runs and has a strength of 2. F2.

2). Mathur 411 Copyright © 2013 Dorling Kindersley (India) Pvt. It is easy to verify that each of the four pairs appears exactly once in each 4 x 2 sub array. 2). N is referred to . 1). Contents Foundations of Software Testing 2E Author: Aditya P. and (2.Orthogonal arrays: Index as the number of runs and t as the strength of the orthogonal array. (2. (1. Ltd The index of an orthogonal array is denoted by λ and is equal to N/st. 1). λ =4/22=1 implying that each pair (t=2) appears exactly once (λ =1) in any 4 x 2 sub array. There is a total of st=22=4 pairs given as (1.

3. 2) and has an index of 1. Ltd Orthogonal arrays: Another example . Each of the four factors can be at any one of 3 levels.What kind of an OA is this? It has 9 runs and a strength of 2. Mathur 412 Copyright © 2013 Dorling Kindersley (India) Pvt. This array is denoted as OA(9. 4. Contents Foundations of Software Testing 2E Author: Aditya P.

s are determined from the context. Arrays shown earlier are LN denotes an orthogonal array of 9 runs. Contents Foundations of Software Testing 2E Author: Aditya P. k. Mathur 413 .e. t. by examining the array itself.Orthogonal arrays: Alternate notations Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Orthogonal array of N runs where k factors take on any value from a set of s symbols. i.

Mixed-level Orthogonal Arrays Contents Foundations of Software Testing 2E Author: Aditya P.9.Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd 6. Mathur 414 .

one encounters more than one factor.Mixed level Orthogonal arrays Copyright © 2013 Dorling Kindersley (India) Pvt. each taking on a different set of values. Ltd So far we have seen fixed level orthogonal arrays. Mixed orthogonal arrays are useful in designing test configurations for such applications. In many practical applications. This is because the design of such arrays assumes that all factors assume values from the same set of s values. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 415 .

Runs=N.Copyright © 2013 Dorling Kindersley (India) Pvt. Total factors: Contents Foundations of Software Testing 2E Author: Aditya P. and so on. Mathur 416 . k2 at s2 levels. k1 factors at s1 levels. Ltd Mixed level Orthogonal arrays: Notation Strength=t.

Mathur 417 .Mixed level Orthogonal arrays: Index and balance Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd The formula used for computing the index λ of an orthogonal array does not apply to the mixed level orthogonal array as the count of values for each factor is a variable. The balance property of orthogonal arrays remains intact for mixed level orthogonal arrays in that any N x t sub array contains each t-tuple corresponding to the t columns. exactly the same number of times. which is λ.

Mathur 418 Copyright © 2013 Dorling Kindersley (India) Pvt.This array can be used to design test configurations for an application that contains 4 factors each at 2 levels and 1 factor at 4 levels. each pair occurs exactly once. Contents Foundations of Software Testing 2E Author: Aditya P. In the two leftmost columns. In columns 1 and 5. each pair also occurs exactly twice. each pair occurs exactly twice. each possible pair occurs exactly the same number of times. In columns 1 and 3. Can you identify some properties? Balance: In any sub array of size 8 x 2. Ltd Mixed level Orthogonal arrays: Example .

labeled F7 through F9. Ltd Mixed level Orthogonal arrays: Example This array can be used to generate test configurations when there are six binary factors. labeled F1 through F6 and three factors each with four possible levels. Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 419 .

Mathur 420 .Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Mixed level Orthogonal arrays: Test generation: Pizza delivery We have 3 binary factors and one factor at 3 levels. Hence we can use the following array to generate test configurations: Contents Foundations of Software Testing 2E Author: Aditya P.

Mathur 421 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Test generation: Pizza delivery: Array . What kind of errors will likely be revealed when testing using these 12 configurations? Contents Foundations of Software Testing 2E Author: Aditya P.Check that all possible pairs of factor combinations are covered in the design above.

Ltd Test generation: Pizza delivery: test configurations Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 422 .

Ltd 6.Copyright © 2013 Dorling Kindersley (India) Pvt. Covering and mixed-level covering arrays Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 423 .9.

we can relax the balance requirement and use covering arrays. Foundations of Software Testing 2E Contents Author: Aditya P. For deterministic applications. Ltd essential in statistical experiments. 1998]: The balance requirement is often Copyright © 2013 Dorling Kindersley (India) Pvt.The “Balance” requirement Observation [Dalal and Mallows. For example. it is not always so in software testing. or mixed level covering arrays for combinatorial designs. Mathur 424 . if a software application has been tested once for a given pair of factor levels. unless the application is known to behave non-deterministically. there is generally no need for testing it again for the same pair. and when repeatability is not the focus.

k the number factors.A covering array CA(N. N denotes the number of runs. and λ the index While generating test cases or test configurations for a software application. Ltd Covering array . Mathur 425 Copyright © 2013 Dorling Kindersley (India) Pvt. t) is an N x k matrix in which entries are from a finite set S of s symbols such that each N x t sub-array contains each possible t-tuple at least λ times. k. s. the number of levels for each factor. t the strength. s. Contents Foundations of Software Testing 2E Author: Aditya P. we use λ=1.

Contents Foundations of Software Testing 2E Author: Aditya P. s.While an orthogonal array OA(N. Ltd Covering array and orthogonal array . We are interested in minimal covering arrays. k. Mathur 426 Copyright © 2013 Dorling Kindersley (India) Pvt. This difference leads to combinatorial designs that are often smaller in size than orthogonal arrays. t) covers each possible t-tuple at least λ times in any N x t sub array. a covering array CA(N. k. Covering arrays are also referred to as unbalanced designs. t) covers each possible t-tuple λ times in any N x t sub array. Thus. covering arrays do not meet the balance requirement that is met by orthogonal arrays. s.

Contents Foundations of Software Testing 2E Author: Aditya P. 2. However. Ltd A balanced design of strength 2 for 5 binary factors. a covering design with the same parameters requires only 6 runs.Covering array: Example OA(8. 2). Mathur 427 Copyright © 2013 Dorling Kindersley (India) Pvt. 5. requires 8 runs and is denoted by .

Q= ∑k i and each N x t sub- i=1 array contains at least one occurrence of each t-tuple corresponding to the t columns. Mathur 428 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Mixed level covering arrays . s1.. € Mixed-level covering arrays are generally smaller than mixed-level orthogonal arrays and more appropriate for use in software testing. Contents Foundations of Software Testing 2E Author: Aditya P. s2.A mixed-level covering array is denoted as p and refers to an N x Q matrix of entries such that.… denote the number of levels of each the corresponding factor.

Mathur 429 . Ltd Mixed level covering array: Example we notice a reduction of 6 configurations. Is the above array balanced? Contents Foundations of Software Testing 2E Author: Aditya P.Comparing this with Copyright © 2013 Dorling Kindersley (India) Pvt.

10. Arrays of strength >2 Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 430 . Ltd 6.Copyright © 2013 Dorling Kindersley (India) Pvt.

Ltd Designs with strengths higher than 2 are sometimes needed to achieve higher confidence in the correctness of software. Consider the following factors in a pacemaker. Mathur 431 . Contents Foundations of Software Testing 2E Author: Aditya P.Arrays of strength >2 Copyright © 2013 Dorling Kindersley (India) Pvt.

Ltd Due to the high reliability requirement of the pacemaker. Thus.Pacemaker example ensure that there are no pairwise or 3-way interaction errors. 3. Mathur Contents 432 Copyright © 2013 Dorling Kindersley (India) Pvt. we need a suitable combinatorial object with strength 3. Thus. we would like to test it to . a total of 54 tests will be required to test for all 3-way interactions of the 5 pacemaker parameters Could a design of strength 2 cover some triples and higher order tuples? Foundations of Software Testing 2E Author: Aditya P. 5. 3) that has 54 runs for 5 factors each at 3 levels and is of strength 3. We could use an orthogonal array OA(54.

The procedure is known as In-parameter Order (IPO) procedure. Inputs: (a) n ≥2: Number of parameters (factors). Ltd We will now study a procedure due to Lei and Tai for the generation of mixed level covering arrays. Mathur 433 . Output: MCA Contents Foundations of Software Testing 2E Author: Aditya P.Generating mixed level covering arrays Copyright © 2013 Dorling Kindersley (India) Pvt. (b) Number of values (levels) for each parameter.

Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 434 . Generating covering arrays Contents Foundations of Software Testing 2E Author: Aditya P.11. Ltd 6.

IPO procedure Copyright © 2013 Dorling Kindersley (India) Pvt. Step 2: Horizontal growth. Mathur 435 . Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Consists of three steps: Step 1: Main procedure. Step 3: Vertical growth.

and C. B. a2. B from the set {b1. A assumes values from the set {a1. Mathur 436 . Ltd Consider a program with three factors A. We begin by applying the Main procedure which is the first step in the generation of an MCA using the IPO procedure.IPO procedure: Example Copyright © 2013 Dorling Kindersley (India) Pvt. We want to generate a mixed level covering array for these three factors. b2}. a3}. Contents Foundations of Software Testing 2E Author: Aditya P. c2.. c3}. and C from the set {c1.

Mathur 437 . Ltd Main: Step 1: Construct all runs that consist of pairs of values of the first two parameters.IPO procedure: main procedure Copyright © 2013 Dorling Kindersley (India) Pvt. We obtain the following set. t2. Let us denote the elements of as t1.…t6. Contents Foundations of Software Testing 2E Author: Aditya P. The entire IPO procedure would terminate at this point if the number of parameters n=2. In our case n=3 hence we continue with horizontal growth.

and parameters B and C. Contents Foundations of Software Testing 2E Author: Aditya P. Let T’ denote the set of runs obtained by extending the runs in T. HG: Step 2: AP is the set of pairs yet to be covered. This leads us to the following set of fifteen pairs.IPO procedure: Horizontal growth Copyright © 2013 Dorling Kindersley (India) Pvt. At this point T’ is empty as we have not extended any run in T. Mathur 438 . Ltd HG: Step 1: Compute the set of all pairs AP between parameters A and C.

This gives us: t1’=(a1. c3). and t3’=(a2. (a3. c1). c2). t2. (b2. c1). 4: Expand t1. b2. c1). c1). b1. c2). c1). Mathur 439 . b1. c2). c3) Update T’ which now becomes {a1. b2. b1. b1. c3. Ltd HG: Steps 3. (b1. c3). c3)} Update pairs remaining to be covered AP={(a1. (a2. b1. (a2. c2). t2’=(a1. (b2. b1. (a2. c2. (a1. b2. (a2. c1).Horizontal growth: Extend Copyright © 2013 Dorling Kindersley (India) Pvt. c2). c2). c3)} Contents Foundations of Software Testing 2E Author: Aditya P. c3)} Update T’ which becomes {(a1. t3 by appending c1. (a3. (a1. (a3.

namely. c1). Step 5: We have not extended t4. HG: Step 6: Expand t4. If we extend it by c2 then we cover one pair from AP. t6 as C does not have enough elements. Thus. c1) and (b2. t5. b2) by c1 then we cover two of the uncovered pairs from AP. If we extend it by c3 then we cover one pairs in AP. Mathur 440 . Ltd HG. t5. (a2. t6 by suitably selected values of C. we choose to extend t4 by c1. Contents Foundations of Software Testing 2E Author: Aditya P.Horizontal growth: Optimal extension Copyright © 2013 Dorling Kindersley (India) Pvt. We find the best way to extend these in the next step. If we extend t4=(a2.

b1. c2). c3). (a3. (a3. (a2. (b1. (a3. c3). (a2. b2. (a1. b1. (a3. c3)} HG: Step 6: Similarly we extend t5 and t6 by the best possible values of parameter C. Mathur 441 . c2). (a2. c2). b2. b1. c3). b1. c2). (b2. c2). c1). Ltd T’={(a1. c1) T’={(a1. c3). b1. b2. b2. (a1. b1. c1). c1)} AP= {(a1. c3)} Contents Foundations of Software Testing 2E Author: Aditya P. (b1. (a3. b2. c1)} AP= {(a1. (a2.Horizontal growth: Update and extend remaining Copyright © 2013 Dorling Kindersley (India) Pvt. (a2. c1). b2. (a3. c2). This leads to: t5’=(a3. c3). (a2. c1). c2). c3) and t6’=(a3. c3). (b2. c2).

c2). c2). we have generated six complete runs namely: T’={(a1. b2. (a2. (a3. Contents Foundations of Software Testing 2E Author: Aditya P. (a3. b2. (b1. c3)} Also. c3). b1. c2). c1)} We now move to the vertical growth step of the main IPO procedure to cover the remaining pairs.Horizontal growth: Done Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd We have completed the horizontal growth step. (b2. However. c2). (a3. (a2. c1). b1. b2. These are: AP= {(a1. b1. c3). we have five pairs remaining to be covered. c1). Mathur 442 . c3). (a1. (a2.

*. This is covered by the run (a2. Note that the value of parameter Y does not matter and hence is indicated as a * which denotes a don’t care value. c3) covers pair p. *. we will add a new run to T’ such that p is covered. consider p=(a3. c3). Let us begin with the pair p= (a1. This is covered by the run (a3. The run t= (a1. Mathur 443 . Ltd For each missing pair p from AP.Vertical growth Copyright © 2013 Dorling Kindersley (India) Pvt. consider p=(a2. Next . *. c2) Next . c2) Contents Foundations of Software Testing 2E Author: Aditya P. c2). c2).

b1. b2. (a3. b1. Thus. consider p=(b2. b1. b1. (a1. c1). b2. c2). (a3. (a1. c3). Thus. consider p=(b1. We already have (a3. Finally. c1). c2). We replace the don’t care entries by an arbitrary value of the corresponding factor and get: T={(a1. *. c2). (a2. c1). Ltd Next . c3).Vertical growth (contd. b1. c3) and hence we can modify it . (a3. b2. (a2. *. b1. p is covered without any new run added. We already have (a1.) to get the run (a1. Mathur 444 Copyright © 2013 Dorling Kindersley (India) Pvt. b2. c2)} Contents Foundations of Software Testing 2E Author: Aditya P. c3). b2. c2) and hence we can modify it to get the run (a3. c3). (a2. c2). c3). p is covered without any new run added.

MCA(9. Ltd Final covering array Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 445 . 21 32. 2) Run F1(X) F2(Y) F3(Z) 1 1 1 1 2 1 2 2 3 1 2 3 4 2 1 2 5 2 1 3 6 2 2 1 7 3 1 2 8 3 1 3 9 3 2 1 Copyright © 2013 Dorling Kindersley (India) Pvt.

Lei and Tai found that the IPO algorithm performs almost as well as AETG in the size of the generated arrays. Mathur 446 Copyright © 2013 Dorling Kindersley (India) Pvt.That completes our presentation of an algorithm to generate covering arrays. A detailed analysis of the algorithm has been given by Lei and Tai. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Practicalities . Lei and Tai offer several other algorithms for horizontal and vertical growth that are faster than the algorithm mentioned here.

Ltd AETG from Telcordia is a commercial tool to generate covering arrays. Contents Foundations of Software Testing 2E Author: Aditya P. AETG is covered by US patent 5.Tools Copyright © 2013 Dorling Kindersley (India) Pvt. It allows users to specify constraints across parameters. For example. parameter A might not assume a value a2 when parameter B assumes value b3. Mathur 447 . Publicly available tool: ACTS from Jeff Lie’s group a UT Arlington.043.542.

For software testing. Contents Foundations of Software Testing 2E Author: Aditya P.” combinatorial designs offer a significant reduction in the number of test configurations/test cases. By requiring only pair-wise coverage and relaxing the “balance requirement. We introduced one algorithm for generating covering arrays. MOLS. Orthogonal arrays. Ltd test cases.Summary Combinatorial design techniques assist with the design of test configurations and Copyright © 2013 Dorling Kindersley (India) Pvt. This continues to be a research topic of considerable interest. Handbooks offer a number covering and mixed level covering arrays. Mathur 448 . covering arrays. and mixed-level covering arrays are used as combinatorial objects to generate test configurations/test cases. most useful amongst these are mixed level covering arrays.

Test Adequacy Measurement and Enhancement: Control and Data flow Updated: July 16. 2013 Foundations of Software Testing 2E Contents Author: Aditya P. Ltd Chapter 7 . Mathur 449 Copyright © 2013 Dorling Kindersley (India) Pvt.

LCSAJ.Learning Objectives What is test adequacy? What is test enhancement? When to measure test Copyright © 2013 Dorling Kindersley (India) Pvt. and MC/DC coverage §  Data flow coverage §  Strengths and limitations of code coverage based measurement of test adequacy §  The “subsumes” relation amongst coverage criteria §  Tools for the measurement of code coverage Contents Foundations of Software Testing 2E Author: Aditya P. statement. multiple condition. Ltd §  adequacy and how to use it to enhance tests? §  Control flow based test adequacy. decision. Mathur 450 . condition.

1 Test adequacy: basics Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd 7. Mathur 451 .

R2. Ltd §  . Also.What is adequacy? Consider a program P written to meet a set R of functional requirements. R). or as: Is T adequate? Contents Foundations of Software Testing 2E Author: Aditya P.…. Rn . We notate such a P and R as ( P. Mathur 452 Copyright © 2013 Dorling Kindersley (India) Pvt. Let R contain n requirements labeled R1. §  We now ask: Is T good enough? This question can be stated differently as: Has P been tested thoroughly?. §  Suppose now that a set T containing k tests has been constructed to test P to determine whether or not it meets all the requirements in R . P has been executed against each test in T and has produced correct behavior.

have the same meaning. Mathur 453 Copyright © 2013 Dorling Kindersley (India) Pvt. §  This measurement is done against a given criterion C . The determination of whether or not a test set T for program P satisfies criterion C depends on the criterion itself and is explained later. Contents Foundations of Software Testing 2E Author: Aditya P." ``good enough. Ltd §  ." used in the questions above.Measurement of adequacy In the context of software testing." and ``adequate. the terms ``thorough. A test set is considered adequate with respect to criterion C when it satisfies C. §  Adequacy is measured for a given test set designed to test P to determine whether or not P meets its requirements.

say x and y . Copyright © 2013 Dorling Kindersley (India) Pvt. from the standard input device. R2.1 Find and print to the standard output device the sum of x and y if x<y . Ltd Program sumProduct must meet the following requirements: Contents Foundations of Software Testing 2E Author: Aditya P. R2. Mathur 454 .2 Find and print to the standard output device the product of x and y if x≥ y.Example R1 Input two integers.

The lone test case t in T tests R1 and R2. T={t: <x=2. Obviously. Mathur 455 Copyright © 2013 Dorling Kindersley (India) Pvt.2. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Suppose now that the test adequacy criterion C is specified as: . but not R2.Example (contd. y=3> is inadequate with respect to C for program sumProduct. R ) is considered adequate if for each requirement r in R there is at least one test case in T that tests the correctness of P with respect to r .1.) C : A test T for program ( P.

Ltd Black-box and white-box criteria . Contents Foundations of Software Testing 2E Author: Aditya P. A criterion C is a black-box test adequacy criterion if the corresponding coverage domain Ce depends solely on requirements R for the program P under test. Mathur 456 Copyright © 2013 Dorling Kindersley (India) Pvt. we derive a finite set known as the coverage domain and denoted as Ce . A criterion C is a white-box test adequacy criterion if the corresponding coverage domain Ce depends solely on program P under test.For each adequacy criterion C .

Given that Ce has n≥ 0 elements. and R. Ltd that T covers Ce if for each element e' in Ce there is at least one test case in T that tests e'. Contents Foundations of Software Testing 2E Author: Aditya P. T is considered inadequate with respect to C if it covers k elements of Ce where k<n . T is considered adequate with respect to C if it covers all elements in the coverage domain.Coverage We want to measure the adequacy of T. The notion of “tests” is explained later through examples. The fraction k/n is a measure of the extent to which T is adequate with respect to C . we say Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 457 . P . This fraction is also known as the coverage of T with respect to C .

Ltd Example . The coverage of T with respect to C.1 but not R2. R2. R2. T covers R1 and R2.2}. Contents Foundations of Software Testing 2E Author: Aditya P.66. R ) is considered adequate if for each requirement r in R there is at least one test case in T that tests the correctness of P with respect to r. Mathur 458 Copyright © 2013 Dorling Kindersley (India) Pvt.2 .” In this case the finite set of elements Ce={R1. and R is 0.Let us again consider the following criterion: “A test T for program ( P.1. Hence T is not adequate with respect to C . P.

respectively. Mathur 459 Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. For the given adequacy criterion C we obtain the coverage domain Ce to be the set { p1.Consider the following criterion: “A test T for program ( P. one corresponding to condition x<y and the other to x≥ y. R ) is considered adequate if each path in P is traversed at least once. Ltd Another Example .” Assume that P has exactly two paths. p2}. We refer to these as p1 and p2.

As T contains only one test for which x<y . We can also say that p1 is tested and p2 is not tested.5 and hence T is not adequate with respect to C. Contents Foundations of Software Testing 2E Author: Aditya P. only the path p1 is executed. Ltd Another Example (contd. we execute P against each test case in T . Mathur 460 Copyright © 2013 Dorling Kindersley (India) Pvt. P .) . and R is 0.To measure the adequacy of T of sumProduct against C . the coverage of T with respect to C. Thus.

Code-based coverage domain Copyright © 2013 Dorling Kindersley (India) Pvt. when the coverage domain must contain elements from the code. Errors in the program and incomplete or incorrect requirements might cause the program. This assumption is based on a knowledge of the requirements. Contents Foundations of Software Testing 2E Author: Aditya P. these elements must be derived by analyzing the code and not only by an examination of its requirements. to be different from the expected. However. and hence the coverage domain. Ltd In the previous example we assumed that P contains exactly two paths. Mathur 461 .

This path traverses all the statements.t. C but does not reveal the error. There is only one path denoted as p1. Contents Foundations of Software Testing 2E Author: Aditya P. Using the path-based coverage criterion C.Example This program is obviously incorrect as per the requirements of sumProduct. T={t: <x=2. Mathur 462 Copyright © 2013 Dorling Kindersley (India) Pvt.r. we get coverage domain Ce={ p1}. y=3> }is adequate w. Ltd sumProduct1 .

p2}. T={t: <x=2. Ltd sumProduct2 This program is correct as per the requirements of sumProduct.) Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 463 .r. Contents Foundations of Software Testing 2E Author: Aditya P.t. It has two paths denoted by p1 and p2. y=3>} is inadequate w.Example (contd. the path-based coverage criterion C. Ce={ p1.

Mathur 464 .Copyright © 2013 Dorling Kindersley (India) Pvt. This does not diminish in any way the need for the measurement of test adequacy as increasing coverage might reveal an error!. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Lesson An adequate test set might not reveal even the most obvious error in a program.

Mathur 465 . Ltd 7.3 Test enhancement Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.1.

Enhancement in turn is also likely to test the program in ways it has not been tested before such as testing untested portion. or testing the features in a sequence different from the one used previously. Testing the program differently than before raises the possibility of discovering any uncovered errors. Mathur 466 Copyright © 2013 Dorling Kindersley (India) Pvt. Identification of this deficiency helps in the enhancement of the inadequate test set. an inadequate test set is a cause for worry. Ltd While a test set adequate with respect to some criterion does not guarantee an error- . Contents Foundations of Software Testing 2E Author: Aditya P.Test Enhancement free program. Inadequacy with respect to any criterion often implies test deficiency.

T' is adequate with respect to the path coverage criterion. Thus. Mathur 467 . One test that does so is {<x=3>. Contents Foundations of Software Testing 2E Author: Aditya P. t2: <x=3. y=1>} Executing sum-product-2 against the two tests in T’ causes paths p1 and p2 are traversed. y=4>. Adding this test to T and denoting the expanded test set by T' we get: T'={t1: <x=3. Ltd For sumProduct2.Test Enhancement: Example Copyright © 2013 Dorling Kindersley (India) Pvt. y=1>}. to make T adequate with respect to the path coverage criterion we need to add a test that covers p2.

Ltd Test Enhancement: Procedure Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 468 .Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 469 .Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Test Enhancement: Example Consider a program intended to compute xy given integers x and y. For y<0 the program skips the computation and outputs a suitable error message.

) Suppose that test T is considered adequate if it tests the exponentiation Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 470 . x≠0. y≠ 0. y=1>. y=0}. One such test set is T={t1: <x=0. y=0>}.Test Enhancement: Example (contd. Again. t2: <x=1. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd program for at least one zero and one non-zero value of each of the two inputs x and y. one can derive an adequate test set for the program by an examination of Ce. The coverage domain for C can be determined using C alone and without any inspection of the program For C we get Ce={x=0.

Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Test Enhancement: Example: Path coverage . The number of paths depends on the value of y and hence that of count. Mathur 471 Copyright © 2013 Dorling Kindersley (India) Pvt. An examination of the exponentiation program reveals that it has an indeterminate number of paths due to the while loop.Criterion C of the previous example is a black-box coverage criterion as it does not require an examination of the program under test for the measurement of adequacy Let us now consider the path coverage criterion defined in in an earlier example.

) . This simple analysis of paths in exponentiation reveals that for the path coverage criterion we cannot determine the coverage domain. Mathur 472 Copyright © 2013 Dorling Kindersley (India) Pvt. The usual approach in such cases is to simplify C and reformulate it as follows: A test T is considered adequate if it tests all paths.Given that y is any non-negative integer. the number of paths can be arbitrarily large. Ltd Example: Path coverage (contd. Contents Foundations of Software Testing 2E Author: Aditya P. In case the program contains a loop. then it is adequate to traverse the loop body zero times and once.

p3}. p2.) . Mathur 473 Copyright © 2013 Dorling Kindersley (India) Pvt.The modified path coverage criterion leads to C‘e={p1. Ltd Example: Path coverage (contd. The elements of Ce’ are enumerated below with respect to flow graph for the exponentiation program. Contents Foundations of Software Testing 2E Author: Aditya P.

) .66.We measure the adequacy of T with respect to C'. Thus. As T does not contain any test with y<0. the coverage of T with respect to C' is 2/3=0. Mathur 474 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Example: Path coverage (contd. Contents Foundations of Software Testing 2E Author: Aditya P. p3 remains uncovered.

Ltd Any test case with y<0 will cause p3 to be traversed. y=0>. Let . y=-1>} Contents Foundations of Software Testing 2E Author: Aditya P. We add t to T. y=1>. The loop in the enhancement terminates as we have covered all feasible elements of Ce’. The enhanced test set is: T={<x=0. Test t covers path p3 and P behaves correctly. Mathur 475 Copyright © 2013 Dorling Kindersley (India) Pvt. <x=1.) us use t:<x=5. <x=5. y=-1>.Example: Path coverage (contd.

4 Infeasibility and test adequacy Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd 7. Mathur 476 .1.

Contents Foundations of Software Testing 2E Author: Aditya P. There does not exist an algorithm that would analyze a given program and determine if a given element in the coverage domain is infeasible or not. Thus. it is usually the tester who determines whether or not an element of the coverage domain is infeasible. Ltd An element of the coverage domain is infeasible if it cannot be covered by any test in the input domain of the program under test. Mathur 477 .Infeasibility Copyright © 2013 Dorling Kindersley (India) Pvt.

Thus.Demonstrating feasibility Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 478 . Ltd Feasibility can be demonstrated by executing the program under test against a test case and showing that indeed the element under consideration is covered. an attempt to enhance a test set by executing a test aimed at covering element e of program P. Infeasibility cannot be demonstrated by program execution against a finite number of test cases. For complex programs the problem of determining infeasibility could be difficult. In some cases simple arguments can be constructed to show that a given element is infeasible. might fail. Contents Foundations of Software Testing 2E Author: Aditya P.

Infeasible path: Example

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

This program inputs two integers x and y, and
computes z. Ce={p1, p2, p3}.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

479

p1 is infeasible and cannot be traversed by any test case.
This is because when control reaches node 5, condition
y≥0 is false and hence control can never reach node 6.

Thus, any test adequate with respect to the path
coverage criterion for the exponentiation program will
only cover p2 and p3
Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

480

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Example: Flow graph and paths

Adequacy and infeasibility

considered adequate when all feasible elements in the domain have been covered.

While programmers might not be concerned with infeasible elements, testers
attempting to obtain code coverage are. Prior to test enhancement, a tester usually does
not know which elements of a coverage domain are infeasible. Unfortunately, it is only
during an attempt to construct a test case to cover an element that one might realize
the infeasibility of an element.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

481

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

In the presence of one or more infeasible elements in the coverage domain, a test is

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

7.1.5 Error detection and test enhancement

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

482

The purpose of test enhancement is to determine test cases that test the untested
parts of a program or exercise the program using uncovered portions of the input
domain. Even the most carefully designed tests based exclusively on requirements
can be enhanced.
The more complex the set of requirements, the more likely it is that a test set designed
using requirements is inadequate with respect to even the simplest of various test
adequacy criteria.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

483

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Test enhancement

Example

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

A program to meet the following requirements is to be developed.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

484

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Example (contd.)

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

485

Example (contd.)

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Consider the following program written to meet the requirements stated earlier.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

486

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Example (contd.)

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

487

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Example (contd.)

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

488

Example (contd.)

whether or not our program meets its requirements.
T={<request=1, x=2, y=3>, <request=2, x=4>, <request=3>}

For the first two of the three requests the program correctly outputs 8 and 24,
respectively. The program exits when executed against the last request. This program
behavior is correct and hence one might conclude that the program is correct. It will
not be difficult for you to believe that this conclusion is incorrect.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

489

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Suppose now that the following set containing three tests has been developed to test

Let us now evaluate T against the path coverage criterion.
In class exercise: Go back to the example
program and extract the paths not covered by T.

The coverage domain consists of all paths that traverse each of the three loops zero
and once in the same or different executions of the program. This is left as an exercise
and we continue with one sample, and “tricky,” uncovered path.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

490

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Example (contd.)

Example (contd.)

line 10, then the first if at line 12, followed by the statements that compute the
factorial starting at line 20, and then the code to compute the exponential starting at
line 13.

p is traversed when the program is launched and the first input request is to compute
the factorial of a number, followed by a request to compute the exponential. It is easy
to verify that the sequence of requests in T does not exercise p. Therefore T is
inadequate with respect to the path coverage criterion.
Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

491

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Consider the path p that begins execution at line 1, reaches the outermost while at

Example (contd.)

T’={<request=2, x=4>, <request=1, x=2, y=3>, <request=3>}

When the values in T' are input to our example program in the sequence given, the
program correctly outputs 24 as the factorial of 4 but incorrectly outputs 192 as the value
of 23 .
This happens because T' traverses our “tricky” path which makes the computation of the
exponentiation begin without initializing product. In fact the code at line 14 begins with
the value of product set to 24.
Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

492

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

To cover p we construct the following test:

) . Execution of the program under test on T' did cover a path that was not covered earlier and revealed an error in the program.In our effort to increase the path coverage we constructed T' . Mathur 493 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Example (contd. Contents Foundations of Software Testing 2E Author: Aditya P. This example has illustrated a benefit of test enhancement based on code coverage.

Mathur 494 .Copyright © 2013 Dorling Kindersley (India) Pvt.1.6 Single and multiple executions Contents Foundations of Software Testing 2E Author: Aditya P. Ltd 7.

Ltd In the previous example we constructed two test sets T and T' . Notice that both T . x=4>. Hence we consider T as a test set containing one test case and write it as follows: Contents Foundations of Software Testing 2E Author: Aditya P. x=2. Should T (or T’) be considered a single test or a sequence of three tests? T’={<request=2. Mathur 495 Copyright © 2013 Dorling Kindersley (India) Pvt. <request=3>} we assumed that all three tests. y=3>. are input in a sequence during a single execution of the test program. one for each value of request. <request=1.Multiple executions and T' contain three tests one for each value of variable request.

) We assumed that all three tests. it as follows: T”=T∪T’ Contents Foundations of Software Testing 2E Author: Aditya P. one for each value of request. are input in a sequence Copyright © 2013 Dorling Kindersley (India) Pvt. Hence we consider T as a test set containing one test case and write it. Mathur 496 .Multiple executions (contd. Ltd during a single execution of the test program.

Mathur 497 .2.Copyright © 2013 Dorling Kindersley (India) Pvt.1 Statement and block coverage Contents Foundations of Software Testing 2E Author: Aditya P. Ltd 7.

and while statements in C and Java. . Notation: (P. if. adequacy with respect to the statement coverage and block coverage criteria are defined next. Mathur 498 Copyright © 2013 Dorling Kindersley (India) Pvt. such as the #define and int statements in C. Ltd Any program written in a procedural language consists of a sequence of statements. For any procedural language. while others are executable. Recall that a basic block is a sequence of consecutive statements that has exactly one entry point and one exit point. R) denotes program P subject to requirement R. Contents Foundations of Software Testing 2E Author: Aditya P.Declarations and basic blocks Some of these statements are declarative. such as the assignment.

where . Mathur 499 Copyright © 2013 Dorling Kindersley (India) Pvt. R ) is computed as Sc/(Se-Si) . Contents Foundations of Software Testing 2E Author: Aditya P.Statement coverage Sc is the number of statements covered. R) is 1. Si is the number of unreachable statements. i. the size of the coverage domain. Ltd The statement coverage of T with respect to ( P. T is considered adequate with respect to the statement coverage criterion if the statement coverage of T with respect to (P.e. and Se is the total number of statements in the program.

Mathur 500 Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Block coverage . the size of the block coverage domain.e. T is considered adequate with respect to the block coverage criterion if the statement coverage of T with respect to (P. and Be is the total number of blocks in the program. where Bc is the number of blocks covered. i. Bi is the number of unreachable blocks. R) is 1. R) is computed as Bc/(Be -Bi) .The block coverage of T with respect to (P.

Example: statement coverage Coverage domain: Se={2. Se=7. R ) with respect to the statement coverage criterion. 5. Ltd Let T1={t1:<x=-1. 4. 4. Contents Foundations of Software Testing 2E Author: Aditya P. 9. Note: 7b is unreachable. y=1>} . 7. 7. 6. 6. 3. 4. (b) Sc=6. 3. Hence we conclude that T1 is adequate for (P. and 10. 10} Statements covered: t1: 2. Si=1. 7b. 3. y=-1>. The statement coverage for T is 6/(7-1)=1 . Mathur 501 Copyright © 2013 Dorling Kindersley (India) Pvt. 9. 5. and 10 t2: 2.t 2:<x=1.

5 t2. Bc=3. 2. 3.75. Mathur 502 Copyright © 2013 Dorling Kindersley (India) Pvt. t3: same coverage as of t1. 4. Hence T2 is not adequate for (P. 5 . Bi=1.Example: block coverage Blocks covered: t1: Blocks 1. Be=5 . Ltd Coverage domain: Be={1. 2. Block coverage for T2= 3/(5-1)=0. Contents Foundations of Software Testing 2E Author: Aditya P. R) with respect to the block coverage criterion.

r. block coverage criterion. In . we obtain a test set adequate with respect to the block coverage criterion for the program under consideration.t.Example: block coverage (contd.) class exercise: Verify this statement! Also. Mathur 503 Copyright © 2013 Dorling Kindersley (India) Pvt. if test t2 in T1 is added to T2. Ltd T1 is adequate w. In class exercise: Verify this statement! Contents Foundations of Software Testing 2E Author: Aditya P.

yield a coverage value between 0 and 1. For example. Ltd The formulae given for computing various types of code coverage. while specifying a coverage value. Mathur 504 .65 is the same as 65% statement coverage. Contents Foundations of Software Testing 2E Author: Aditya P. one might instead use percentages. However. a statement coverage of 0.Coverage values Copyright © 2013 Dorling Kindersley (India) Pvt.

2 Conditions and decisions Contents Foundations of Software Testing 2E Author: Aditya P. Ltd 7.2.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 505 .

A OR B . and x and y are integers. x and x+y are valid conditions.Conditions Copyright © 2013 Dorling Kindersley (India) Pvt. and the constants 1 and 0 correspond to. and B are Boolean variables. Note that in programming language C. A . Such an expression is also known as a predicate. Given that A . x > y . Mathur 506 . A AND (x<y). Ltd Any expression that evaluates to true or false constitutes a condition. Contents Foundations of Software Testing 2E Author: Aditya P. respectively. (A AND B). are all sample conditions. true and false.

Mathur 507 . Simple conditions are also referred to as atomic or elementary conditions because they cannot be parsed any further into two or more conditions. Contents Foundations of Software Testing 2E Author: Aditya P.Simple and compound conditions Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd A simple condition does not use any Boolean operators except for the not operator. ≤ >. ==. A compound condition is made up of two or more simple conditions joined by one or more Boolean operators. ≠ }. ≥. It is made up of variables and at most one relational operator from the set {<.

most .Conditions as decisions high level languages provide if. while. Mathur 508 Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Any condition can serve as a decision in an appropriate context within a program. and switch statements to serve as contexts for decisions.

and undefined. When the . In some cases the evaluation of a condition might fail in which case the corresponding decision's outcome is undefined. false. Ltd A decision can have three possible outcomes. Mathur 509 Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P.Outcomes of a decision condition corresponding to a decision to take one or the other path is taken. true.

The condition inside the if statement at line 6 will remain undefined because the loop at lines 2-4 will never terminate. Ltd Undefined condition . Contents Foundations of Software Testing 2E Author: Aditya P. the decision at line 6 evaluates to undefined. Thus. Mathur 510 Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 511 Copyright © 2013 Dorling Kindersley (India) Pvt. B . and C. Contents Foundations of Software Testing 2E Author: Aditya P. The answer is four when one is interested in the number of occurrences of simple conditions in a compound condition.How many simple conditions are there in the compound condition: Cond=(A AND B) OR (C AND A)? The first occurrence of A is said to be coupled to its second occurrence. Indeed. Does Cond contain three or four simple conditions? Both answers are correct depending on one's point of view. Ltd Coupled conditions . there are three distinct conditions A .

2. Mathur 512 .3 Decision coverage Contents Foundations of Software Testing 2E Author: Aditya P. Ltd 7.Copyright © 2013 Dorling Kindersley (India) Pvt.

x<y does not constitute a decision and neither does A*B. a condition becomes a decision only when it is used in the Copyright © 2013 Dorling Kindersley (India) Pvt.Conditions within assignments Strictly speaking. At line 4. Mathur 513 . Ltd appropriate context such as within an if statement. Contents Foundations of Software Testing 2E Author: Aditya P.

e. This implies that.Decision coverage possible destinations that correspond to this decision. the expression in the if or a while statement has evaluated to true in some execution of the program under test and to false in the same or another execution. i. for example. all outcomes of the decision have been taken. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd A decision is considered covered if the flow of control has been diverted to all . Mathur 514 Copyright © 2013 Dorling Kindersley (India) Pvt.

Decision coverage: switch statement

more executions of the program under test the flow of control has been diverted to all
possible destinations.

Covering a decision within a program might reveal an error that is not revealed by
covering all statements and all blocks.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

515

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

A decision implied by the switch statement is considered covered if during one or

This program inputs an integer x, and if necessary,
transforms it into a positive value before invoking
foo-1 to compute the output z. The program has an
error. As per its requirements, the program is
supposed to compute z using foo-2 when x≥0.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

516

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Decision coverage: Example

Consider the test set T={t1:<x=-5>}. It is adequate
with respect to statement and block coverage
criteria, but does not reveal the error.

Another test set T'={t1:<x=-5> t2:<x=3>} does
reveal the error. It covers the decision whereas T
does not. Check!

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

517

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Decision coverage: Example (contd.)

Decision coverage: Computation

revealing an error that is not revealed by a test set adequate with respect to statement
and block coverage.
The decision coverage of T with respect to ( P, R ) is computed as Dc/(De -Di) , where
Dc is the number of decisions covered, Di is the number of infeasible decisions, and
De is the total number of decisions in the program, i.e. the size of the decision coverage
domain.
T is considered adequate with respect to the decisions coverage criterion if the decision
coverage of T with respect to ( P, R ) is 1.
Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

518

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

The previous example illustrates how and why decision coverage might help in

The domain of decision coverage consists of all decisions in the program under test.

Note that each if and each while contribute to one decision whereas a switch
contribute to more than one.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

519

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Decision coverage: domain

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

7.2.4 Condition coverage

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

520

Condition coverage

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

A decision can be composed of a simple condition such as x<0 , or of a more
complex condition, such as (( x<0 AND y<0 ) OR ( p≥q )).
AND, OR, XOR are the logical operators that connect two or more simple
conditions to form a compound condition.
A simple condition is considered covered if it evaluates to true and false in one or
more executions of the program in which it occurs. A compound condition is
considered covered if each simple condition it is comprised of is also covered.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

521

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

7.2.5 Condition/decision coverage

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

522

Decision coverage is concerned with the coverage of decisions regardless of whether
or not a decision corresponds to a simple or a compound condition. Thus, in the
statement

there is only one decision that leads control to line 2 if the compound condition
inside the if evaluates to true. However, a compound condition might evaluate to true
or false in one of several ways.
Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

523

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Decision and condition coverage

The condition at line 1 evaluates to false when x≥0 regardless of the value of y.
Another condition, such as x<0 OR y<0, evaluates to true regardless of the value of
y, when x<0.
With this evaluation characteristic in view, compilers often generate code that uses
short circuit evaluation of compound conditions.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

524

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Decision and condition coverage (contd)

Decision and condition coverage (contd)

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Here is a possible translation:

We now see two decisions, one corresponding to each simple condition in the if
statement.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

525

The condition coverage of T with respect to ( P, R ) is computed as Cc/(Ce -Ci) ,
where Cc is the number of simple conditions covered, Ci is the number of infeasible
simple conditions, and |Ce is the total number of simple conditions in the program, i.e.
the size of the condition coverage domain.
T is considered adequate with respect to the condition coverage criterion if the
condition coverage of T with respect to ( P, R ) is 1.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

526

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Condition coverage

An alternate formula where each simple condition contributes 2, 1, or 0 to Cc
depending on whether it is covered, partially covered, or not covered, respectively. is:

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

527

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Condition coverage: alternate formula

Condition coverage: Example

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Partial specifications for computing z:

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

528

Condition coverage: Example (contd.)

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Consider the test set:

Check that T is adequate with respect to the
statement, block, and decision coverage criteria
and the program behaves correctly against t1 and
t2.
Cc=1, Ce=2, Ci=0. Hence condition coverage for
T=0.5.
Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

529

Condition coverage: Example (contd.)

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Add the following test case to T:
t3: <x=3, y=4>
Check that the enhanced test set T is adequate
with respect to the condition coverage criterion
and possibly reveals an error in the program.
Under what conditions will a possible error at
line 7 be revealed by t3?

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

530

Condition/decision coverage

imply that each simple condition within a compound condition has taken both
values true and false.
Condition coverage ensures that each component simple condition within a
condition has taken both values true and false.
However, as illustrated next, condition coverage does not require each decision to
have taken both outcomes. Condition/decision coverage is also known as branch
condition coverage.
Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

531

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

When a decision is composed of a compound condition, decision coverage does not

Condition/decision coverage: Example

In class exercise: Confirm that T1 is adequate with respect to
to decision coverage but not condition coverage.
In class exercise: Confirm that T2 is adequate with respect to
condition coverage but not decision coverage.
Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

532

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Consider the following program and two test sets.

Condition/decision coverage: Definition

+Dc)/((Ce -Ci) +(De-Di)) , where Cc is the number of simple conditions covered,
Dc is the number of decisions covered, Ce and De are the number of simple
conditions and decisions respectively, and Ci and Di are the number of infeasible
simple conditions and decisions, respectively.

T is considered adequate with respect to the multiple condition coverage criterion if
the condition coverage of T with respect to ( P, R ) is 1.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

533

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

The condition/decision coverage of T with respect to (P, R) is computed as (Cc

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Condition/decision coverage: Example

In class exercise: Check that the following test set is
adequate with respect to the condition/decision
coverage criterion.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

534

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

7.2.6 Multiple Condition coverage

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

535

Consider a compound condition with two or more simple conditions. Using condition
coverage on some compound condition C implies that each simple condition within C
has been evaluated to true and false.

However, does it imply that all combinations of the values of the individual simple
conditions in C have been exercised?

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

536

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Multiple condition coverage

Multiple condition coverage: Example Copyright © 2013 Dorling Kindersley (India) Pvt. The four possible combinations of the outcomes of these two simple conditions are enumerated in the table. Consider T: Check: Does T cover all four combinations? Check: Does T’ cover all four combinations? Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Consider D=(A<B) OR (A>C) composed of two simple conditions A< B and A> C . Mathur 537 .

k2. the total number of combinations to be covered is n ∑2 ki i=1 € Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 538 . Each decision has several combinations of values of its constituent simple conditions. Thus. For example. Assume also that each decision contains k1. Ltd Suppose that the program under test contains a total of n decisions. …. kn simple conditions.Multiple condition coverage: Definition Copyright © 2013 Dorling Kindersley (India) Pvt. decision i will have a total of 2ki combinations.

Mathur 539 Copyright © 2013 Dorling Kindersley (India) Pvt. R ) is 1. T is considered adequate with respect to the multiple condition coverage criterion if the condition coverage of T with respect to ( P. Contents Foundations of Software Testing 2E Author: Aditya P. R ) is computed as Cc/(Ce Ci) . Ci is the number of infeasible simple combinations.) .The multiple condition coverage of T with respect to ( P. and Ce is the total number of combinations in the program. where Cc is the number of combinations covered. Ltd Multiple condition coverage: Definition (contd.

computation of S for one of the four combinations. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 540 Copyright © 2013 Dorling Kindersley (India) Pvt. .Multiple condition coverage: Example There is an obvious error in the program. line 3 in the table. Ltd Consider the following program with specifications in the table. has been left out.

Ltd Is T adequate with respect to decision coverage? Multiple condition coverage? Does it reveal the error? Contents Foundations of Software Testing 2E Author: Aditya P.) Copyright © 2013 Dorling Kindersley (India) Pvt.Multiple condition coverage: Example (contd. Mathur 541 .

Multiple condition coverage: Example (contd. Mathur 542 . Does T’ reveal the error? Contents Foundations of Software Testing 2E Author: Aditya P. Ltd To improve decision coverage we add t3 to T and obtain T’.) Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 543 Copyright © 2013 Dorling Kindersley (India) Pvt. Does your test reveal the error? If yes. Ltd Multiple condition coverage: Example (contd. Do you notice that some combinations of simple conditions remain uncovered? Now add a test to T’ to cover the uncovered combinations.In class exercise: Construct a table showing the simple conditions covered by T’.) . then under what conditions? Contents Foundations of Software Testing 2E Author: Aditya P.

2. Mathur 544 .Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd 7.7 LCSAJ coverage Contents Foundations of Software Testing 2E Author: Aditya P.

Contents Foundations of Software Testing 2E Author: Aditya P. executed one after the other. and terminated by a jump to the next such pair. Y. A Linear Code Sequence and Jump is a program unit comprised of a textual code sequence that terminates in a jump to the beginning of another code sequence and jump. Ltd Execution of sequential programs that contain at least one condition. An LCSAJ is represented as a triple (X. Z) where X and Y are. locations of the first and the last statements and Z is the location to which the statement at Y jumps. Mathur 545 Copyright © 2013 Dorling Kindersley (India) Pvt. respectively. proceeds in pairs .Linear Code Sequence and Jump (LCSAJ) where the first element of the pair is a sequence of statements.

we say that the LCSAJ (X. Z) is a jump and Z may be program exit. Y.Consider this program. Contents Foundations of Software Testing 2E Author: Aditya P. Y. and then jumps to statement Z. Mathur 546 Copyright © 2013 Dorling Kindersley (India) Pvt. When control arrives at statement X. follows through to statement Y. Z) is traversed or covered or exercised. Ltd Linear Code Sequence and Jump (LCSAJ) . The last statement in an LCSAJ (X.

t2 covers (1. T covers all three LCSAJs. Mathur 547 Copyright © 2013 Dorling Kindersley (India) Pvt. exit) is executed. 6. 8. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd LCSAJ coverage: Example 1 . exit).t1 covers (1.7) and (7.4.

Mathur 548 . Ltd LCSAJ coverage: Example 2 In class exercise: Find all LCSAJs Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.

) Verify: This set covers all LCSAJs. Ltd LCSAJ coverage: Example 2 (contd. Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 549 .

Ltd The LCSAJ coverage of a test set T with respect to (P. R) is .LCSAJ coverage: Definition Copyright © 2013 Dorling Kindersley (India) Pvt. R) is computed as T is considered adequate with respect to the LCSAJ coverage criterion if the LCSAJ coverage of T with respect to (P. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 550 .

Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 551 .2. Ltd 7.8 Modified condition/decision coverage Contents Foundations of Software Testing 2E Author: Aditya P.

the maximum number of tests required to cover C is 2n . Mathur 552 . Contents Foundations of Software Testing 2E Author: Aditya P. Ltd embedded simple conditions. When a compound condition C contains n simple conditions.Modified Condition/Decision (MC/DC) Coverage Obtaining multiple condition coverage might become expensive when there are many Copyright © 2013 Dorling Kindersley (India) Pvt.

Ltd MC/DC coverage requires that every compound condition in a program must be tested by demonstrating that each simple condition within the compound condition has an independent effect on its outcome. Mathur 553 . Thus. Contents Foundations of Software Testing 2E Author: Aditya P. MC/DC coverage is a weaker criterion than the multiple condition coverage criterion.Compound conditions and MC/DC Copyright © 2013 Dorling Kindersley (India) Pvt.

Mathur 554 .Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd MC/DC coverage: Simple conditions Contents Foundations of Software Testing 2E Author: Aditya P.

9 MC/DC adequate tests for compound conditions Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 555 . Ltd 7.Copyright © 2013 Dorling Kindersley (India) Pvt.2.

Contents Foundations of Software Testing 2E Author: Aditya P. Create a table with five columns and four rows. C1. Ltd Let C=C1 and C2 and C3. An optional column labeled “Comments” may be added. from left to right. Label the . C3 and C. The remaining entries are empty. C2 . The column labeled Test contains rows labeled by test case numbers t1 through t4 .Generating tests for compound conditions columns as Test. Mathur 556 Copyright © 2013 Dorling Kindersley (India) Pvt.

Generating tests for compound conditions (contd. Mathur 557 . and C of the empty table. C3. and C from the table for simple conditions into columns C2. Ltd Copy all entries in columns C1 .) Copyright © 2013 Dorling Kindersley (India) Pvt. C2 . Contents Foundations of Software Testing 2E Author: Aditya P.

) Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 558 . Ltd Fill the first three rows in the column marked C1 with true and the last row with false.Generating tests for compound conditions (contd.

Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 559 Copyright © 2013 Dorling Kindersley (India) Pvt. respectively.Fill the last row under columns labeled C2 .) . true. C3 . We now have a table containing MC/DC adequate tests for C=(C1 AND C2 AND C3) derived from tests for C=(C1 AND C2) . and false. Ltd MC/DC coverage: Generating tests for compound conditions (contd. and C with true.

15 and 7.16). Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 560 .) The procedure illustrated above can be extended to derive tests for any compound condition using tests for a simpler compound condition (solve Exercises 7.Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd MC/DC coverage: Generating tests for compound conditions (contd.

Ltd 7. Mathur 561 .Copyright © 2013 Dorling Kindersley (India) Pvt.10 Definition of MC/DC coverage Contents Foundations of Software Testing 2E Author: Aditya P.2.

•  Each simple condition within a compound condition C in P has been shown to independently effect the outcome of C. is considered adequate . This is the MC part of the coverage we discussed. •  Each block in P has been covered. Contents Foundations of Software Testing 2E Author: Aditya P. •  Each simple condition in P has taken both true and false values. •  Each decision in P has taken all possible outcomes. Ltd A test set T for program P written to meet requirements R. Mathur 562 Copyright © 2013 Dorling Kindersley (India) Pvt. the following requirements are met.MC/DC coverage: Definition with respect to the MC/DC coverage criterion if upon the execution of P on each test in T.

Contents Foundations of Software Testing 2E Author: Aditya P. With regard to the second requirement. respectively. Ltd The first three requirements above correspond to block. it is to be noted that conditions that are not part of a decision.Analysis coverage. condition. The fourth requirement corresponds to ``MC" coverage. such as the one in the following statement A= (p<q) OR (x>y) are also included in the set of conditions to be covered. Thus. Mathur 563 Copyright © 2013 Dorling Kindersley (India) Pvt. the MC/DC coverage criterion is a mix of four coverage criteria based on the flow of control. and decision .

) poses a problem. Mathur 564 Copyright © 2013 Dorling Kindersley (India) Pvt. a condition such as (A AND B) OR (C AND A) .Analysis (contd. It is not possible to keep the first occurrence of A fixed while varying the value of its second occurrence. In such cases an adequate test set need only demonstrate the independent effect of any one occurrence of the coupled condition Contents Foundations of Software Testing 2E Author: Aditya P. Ltd With regard to the fourth requirement. Here the first occurrence of A is said to be coupled to its second occurrence.

. denoted by MCc. Mathur 565 . ni denote the number of simple conditions Copyright © 2013 Dorling Kindersley (India) Pvt. is computed as follows. The MC coverage of T for program P subject to requirements R. Ltd in Ci . Contents Foundations of Software Testing 2E Author: Aditya P. and fi the number of infeasible simple conditions in Ci . ei the number of simple conditions shown to have independent affect on the outcome of Ci.. Test set T is considered adequate with respect to the MC coverage if MCc=1 of T is 1.Adequacy Let C1. C2.. CN be the conditions in P.

R1. R2: The invocation described above must continue until an input Boolean variable becomes true. Ltd Consider the following requirements: R1. R1. Contents Foundations of Software Testing 2E Author: Aditya P.2: Invoke fire-2 when (x<y) AND (z * z ≤ y) OR (current=``South").Example Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 566 .1: Invoke fire-1 when (x<y) AND (z * z > y) AND (prev=``East").3: Invoke fire-3 when none of the two conditions above is true.

Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 567 .) Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Example (contd.

Mathur 568 . Ltd Example (contd.) Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.

is adequate with respect to statement. and decision coverage criteria but not with respect to the condition coverage criterion.Example (contd. block. Ltd Verify that the following set T1 of four tests. Mathur 569 . executed in the given order.) Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P.

Ltd to the condition coverage but not with respect to the multiple condition coverage criterion. obtained by adding t5 to T1. Mathur 570 .Example (contd.) Verify that the following set T2. is adequate with respect Copyright © 2013 Dorling Kindersley (India) Pvt. Note that sequencing of tests is important in this case! Contents Foundations of Software Testing 2E Author: Aditya P.

Mathur 571 . obtained by adding t6. and t9 to T2 is adequate Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd with respect to MC/DC coverage criterion. Note again that sequencing of tests is important in this case (especially for t1 and t7)! Contents Foundations of Software Testing 2E Author: Aditya P.Example (contd.) Verify that the following set T3. t8. t7.

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd 7. Mathur 572 .2.12 Error detection and MC/DC adequacy Contents Foundations of Software Testing 2E Author: Aditya P.

For example. Mathur 573 Copyright © 2013 Dorling Kindersley (India) Pvt. the correct condition is (x<y AND done) which has been coded as (x<y OR done). the correct condition should be (x<y AND z*x ≥ y AND d=``South") has been coded as (x<y OR z*x ≥ y).MC/DC adequacy and error detection Missing condition: One or more simple conditions is missing from a compound condition. For example. . the correct condition should be (x<y AND done) but the condition coded is (done). Ltd We consider the following three types of errors. For example. Incorrect Boolean operator: One or more Boolean operators is incorrect. Contents Foundations of Software Testing 2E Author: Aditya P. Mixed: One or more simple conditions is missing and one or more Boolean operators is incorrect.

Verify that the following set of four tests is MC/DC adequate but does not reveal the error. Contents Foundations of Software Testing 2E Author: Aditya P.Example Suppose that condition C=C1 AND C2 AND C3 has been coded as C'=C1 AND C2. Mathur 574 . Four Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd tests that form an MC/DC adequate set are in the following table.

Mathur 575 Copyright © 2013 Dorling Kindersley (India) Pvt. the examples do favor MC/DC over condition coverage. Ltd MC/DC and condition coverage . (Note the emphasis on “likely. However.Several examples in the book show that satisfying the MC/DC adequacy criteria does not necessarily imply that errors made while coding conditions will be revealed. The examples also show that an MC/DC adequate test will likely reveal more errors than a decision or condition-coverage adequate test.”) Contents Foundations of Software Testing 2E Author: Aditya P.

or the combination C1=false and C2=false may be infeasible if the programming language allows. or requires as in C. Thus. the combination C1=false and C2=true. Mathur 576 Copyright © 2013 Dorling Kindersley (India) Pvt. condition C2 is not evaluated if C1 evaluates to false. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd MC/DC and short circuit evaluation .Consider C=C1 AND C2. The outcome of the above condition does not depend on C2 when C1 is false. When using short-circuit evaluation. short circuit evaluation.

Mathur 577 . Consider. Ltd Dependence of one decision on another might also lead to an infeasible combination. for example.MC/DC and decision dependence Copyright © 2013 Dorling Kindersley (India) Pvt. Infeasible condition A<5 Contents Foundations of Software Testing 2E Author: Aditya P. the following sequence of statements.

however. It may. In the sequence above. Mathur 578 Copyright © 2013 Dorling Kindersley (India) Pvt. Consider the following sequence. both decisions are reachable but the second decision is not feasible. A decision might be reachable but .Infeasibility and reachability not feasible and vice versa. Contents Foundations of Software Testing 2E Author: Aditya P. be feasible. In this case the second decision is not reachable due an error at line 3. Ltd Note that infeasibility is different from reachability.

2. Ltd 7.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 579 .15 Tracing test cases to requirements Contents Foundations of Software Testing 2E Author: Aditya P.

Advantages of trace back: Assists us in determining whether or not the new test case is redundant. It has the likelihood of revealing errors and ambiguities in the requirements. Ltd When enhancing a test set to satisfy a given coverage criterion. Contents Foundations of Software Testing 2E Author: Aditya P.27. See example 7. Mathur 580 Copyright © 2013 Dorling Kindersley (India) Pvt. It assists with the process of documenting tests against requirements.Test trace back following question: What portions of the requirements are tested when the program under test is executed against the newly added test case? The task of relating the new test case to the requirements is known as test trace-back. it is desirable to ask the .

Mathur 581 .3 Concepts from data flow 7. Ltd 7.1 Definitions and uses Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.3.

This is in contrast to criteria based on “flow of control” that we have examined so far. Test adequacy criteria based on the flow of data are useful in improving tests that are adequate with respect to control-flow based criteria. Let us look at an example. Ltd We will now examine some test adequacy criteria based on the flow of “data” in a program.Basic concepts Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 582 .

Contents Foundations of Software Testing 2E Author: Aditya P.Example: Test enhancement using data flow Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 583 . Ltd Here is an MC/DC adequate test set that does not reveal the error.

An MC/DC adequate test does not force the execution of this path and hence the divide by zero error is not revealed. Foundations of Software Testing 2E Author: Aditya P. at line 9. To do so one requires a test that causes conditions at lines 5 and 8 to be true.Example (contd. Mathur Contents 584 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Neither of the two tests force the use of z defined on .) line 6.

Ltd error.) Verify that the following test set covers all def-use pairs of z and reveals the Copyright © 2013 Dorling Kindersley (India) Pvt.Example (contd. Mathur 585 . Would an LCSAJ adequate test also reveal the error? Contents Foundations of Software Testing 2E Author: Aditya P.

Definitions and uses Copyright © 2013 Dorling Kindersley (India) Pvt. x+y) uses variables x and y. &x. Contents Foundations of Software Testing 2E Author: Aditya P. A[10]. y. Statement printf(``Output: %d \n". Statement x=y+z defines variable x and uses variables y and z. &y) defines variables x and y. defines three variables. such as C and Java. Mathur 586 . Variables are defined by assigning values to them and are used in expressions. Statement scanf(``%d %d". contains variables. Ltd A program written in a procedural language. Declaration int x.

or a reference to. x.) A parameter x passed as call-by-value to a function. is considered as a use of.Copyright © 2013 Dorling Kindersley (India) Pvt. serves as a definition and use of x Contents Foundations of Software Testing 2E Author: Aditya P. A parameter x passed as call-by-reference. Ltd Definitions and uses (contd. Mathur 587 .

Definitions and uses: Pointers Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 588 . Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Consider the following sequence of statements that use pointers. The first of the above statements defines a pointer variable z the second defines y and uses z the third defines x through the pointer variable z and the last defines y and uses x accessed through the pointer variable z.

Ltd Arrays are also tricky. and y. The choice of whether to consider the entire array A as defined or the specific element depends upon how stringent is the requirement for coverage analysis.Definitions and uses: Arrays The first statement defines variable A. Consider the following declaration and two statements in C: . The second statement defines A and uses i . Mathur 589 Copyright © 2013 Dorling Kindersley (India) Pvt. Alternate: second statement defines A[i] and not the entire array A. x. Contents Foundations of Software Testing 2E Author: Aditya P.

2 C-use and p-use Contents Foundations of Software Testing 2E Author: Aditya P.3.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 590 . Ltd 7.

in an output statement. Mathur 591 . as a parameter within a function call. and in subscript expressions. How many c-uses of x can you find in the following statements? Answer: 5 Contents Foundations of Software Testing 2E Author: Aditya P. are classified as c-use. where the ``c" in c-use stands for computational. Ltd Uses of a variable that occur within an expression as part of an assignment statement.c-use Copyright © 2013 Dorling Kindersley (India) Pvt.

The ``p" in p-use stands for predicate. is considered as a p-use.p-use The occurrence of a variable in an expression used as a condition in a branch Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 592 . Ltd statement such as an if and a while. How many p-uses of z and x can you find in the following statements? Answer: 3 (2 of z and 1 of x) Contents Foundations of Software Testing 2E Author: Aditya P.

Is the use of x in the subscript.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 593 . a c-use or a p-use? Discuss. Ltd p-use: possible confusion Consider the statement: The use of A is clearly a p-use. Contents Foundations of Software Testing 2E Author: Aditya P.

The first definition of p is considered local to the block while the second definition is global. and uses. We are concerned with global definitions. their definitions flow into this block from some other block. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 594 .C-uses within a basic block Copyright © 2013 Dorling Kindersley (India) Pvt. only the second definition will propagate to the next block. Ltd Consider the basic block While there are two definitions of p in this block. Note that y and z are global uses.

Mathur 595 .Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd 7.3.4 Data flow graph Contents Foundations of Software Testing 2E Author: Aditya P.

Data flow graph Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. It is similar to a control flow graph of a program in that the nodes. and all paths thorough the control flow graph are preserved in the data flow graph. Mathur 596 . An example follows. edges. also known as def-use graph. Ltd A data-flow graph of a program. captures the flow of definitions (also known as defs) across basic blocks in a program.

Ltd Given a program.Example block. Similarly. find its basic blocks. c-use and p-use to each node in the graph. Attach defs. Contents Foundations of Software Testing 2E Author: Aditya P. ui(x) refers to the use of variable x at node i. c-uses and p-uses in each . We use di(x) to refer to the definition of variable x at node i. Each block becomes a node in the def-use graph (this is similar to the control flow graph). Mathur 597 Copyright © 2013 Dorling Kindersley (India) Pvt. compute defs. Label each edge with the condition which when true causes the edge to be taken.

) Unreachable node Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Example (contd. Mathur 598 .Copyright © 2013 Dorling Kindersley (India) Pvt.

3. Mathur 599 .5 Def-clear paths Contents Foundations of Software Testing 2E Author: Aditya P. Ltd 7.Copyright © 2013 Dorling Kindersley (India) Pvt.

without redefining x anywhere else along the path. is a def-clear path for x. Mathur 600 . Contents Foundations of Software Testing 2E Author: Aditya P. Thus. Path 2-5 is def-clear for variable z defined at node 2 and used at node 5. Ltd defined and ending at a node at which x is used. definition of z at node 2 is live at node 5 while that at node 1 is not live at node 5. Path 1-2-5 is NOT def-clear for variable z defined at node 1 and used at node 5.Def-clear path Any path starting from a node at which variable x is Copyright © 2013 Dorling Kindersley (India) Pvt.

16 Find def-clear paths for defs and uses of x and z. Mathur 601 Contents . Ltd P7. Which definitions are live at node 4? Foundations of Software Testing 2E Author: Aditya P.Def-clear path (another example) Copyright © 2013 Dorling Kindersley (India) Pvt.

Copyright © 2013 Dorling Kindersley (India) Pvt.6 def-use pairs Contents Foundations of Software Testing 2E Author: Aditya P.3. Ltd 7. Mathur 602 .

l) and x is used at node k. Contents Foundations of Software Testing 2E Author: Aditya P. dpu (di(x)) denotes the set of all edges (k. If uj(x)) is a p-use then all edges of the kind (j. dcu (di(x)) denotes the set of all nodes where di(x)) is live and used. k) must also be taken during some executions. We say that a def-use pair (di(x). l) such that there is a def-clear path from node i to edge (k. Ltd Def of a variable at line l1 and its use at line l2 constitute a def-use pair. l1 and l2 . uj(x)) is covered when a def-clear path that includes nodes i to node j is executed.Def-use pairs can be the same. Mathur 603 Copyright © 2013 Dorling Kindersley (India) Pvt.

Ltd Def-use pairs (example) Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 604 .

Contents Foundations of Software Testing 2E Author: Aditya P. Analysis of the data flow graph can reveal a minimal set of def-use pairs whose coverage implies coverage of all def-use pairs. Exercise: Analyze the def-use graph shown in the previous slide and determine a minimal set of def-uses to be covered. in some cases.Def-use pairs: Minimal set of a def-use pair implies coverage of another def-use pair. Mathur 605 Copyright © 2013 Dorling Kindersley (India) Pvt. However. coverage . Ltd Def-use pairs are items to be covered during testing.

PU: total number of p-uses.Data flow based adequacy Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. v2…vn each defined at di nodes. Mathur 606 . Given a total of n variables v1. Ltd CU: total number of c-uses in a program.

Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 607 .1. Ltd 7. c-use coverage Contents Foundations of Software Testing 2E Author: Aditya P.4.4 Adequacy criteria based on data flow 7.

Mathur 608 . Ltd C-use coverage Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt.

.. count=1> Contents Foundations of Software Testing 2E Author: Aditya P. q.. Mathur 609 Copyright © 2013 Dorling Kindersley (India) Pvt. End) covers the c-use at node z of x defined at node q given that (k …. z) is def clear with respect to x Exercise: Find the c-use coverage when program c-use of x P7.16 is executed against the following test: t1: <x=5.Path (Start.. k. Ltd C-use coverage: path traversed .. y=-1. . z. .

2 p-use coverage Contents Foundations of Software Testing 2E Author: Aditya P.4.4 Adequacy criteria based on data flow 7. Ltd 7. Mathur 610 .Copyright © 2013 Dorling Kindersley (India) Pvt.

Ltd p-use coverage Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 611 .

count=3> Contents Foundations of Software Testing 2E Author: Aditya P.16 is executed against the following test: t2: <x=-2. Ltd p-use coverage: paths traversed . Mathur 612 Copyright © 2013 Dorling Kindersley (India) Pvt. y=-1.Exercise: Find the p-use coverage when program P7.

Mathur 613 .4 Adequacy criteria based on data flow 7. all-uses coverage Contents Foundations of Software Testing 2E Author: Aditya P.4.3. Ltd 7.Copyright © 2013 Dorling Kindersley (India) Pvt.

Copyright © 2013 Dorling Kindersley (India) Pvt.16? Contents Foundations of Software Testing 2E Author: Aditya P.r. Ltd All-uses coverage Exercise: Is T={t1. Mathur 614 . to all-uses coverage for P7.t. t2} adequate w.

However. Mathur 615 . Contents Foundations of Software Testing 2E Author: Aditya P.and c-uses Coverage of a c. Ltd Infeasible p. then some c.Copyright © 2013 Dorling Kindersley (India) Pvt. if this path is infeasible.and p-uses that require this path to be traversed might also be infeasible. Infeasible uses are often difficult to determine without some hint from a test tool.or a p-use requires a path to be traversed through the program.

Mathur 616 Copyright © 2013 Dorling Kindersley (India) Pvt. Show that this c-use is infeasible. Ltd Infeasible c-use: Example . Contents Foundations of Software Testing 2E Author: Aditya P.Consider the c-use at node 4 of z defined at node 5.

Ltd 7.4 k-dr chain coverage Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 617 .Copyright © 2013 Dorling Kindersley (India) Pvt.4.

Contents Foundations of Software Testing 2E Author: Aditya P.Other data-flow based criteria Copyright © 2013 Dorling Kindersley (India) Pvt. These are alternating sequences of def-use for one or more variables. p-. Ltd There exist several other adequacy criteria based on data flows. Examples: (a) def-use chain or k-dr chain coverage. Some of these are more powerful in their error-detection effectiveness than the c-. Mathur 618 . (b) Data context and ordered data context coverage. and all-uses criteria.

Copyright © 2013 Dorling Kindersley (India) Pvt.6 The “subsumes” relation Contents Foundations of Software Testing 2E Author: Aditya P. Ltd 7. Mathur 619 .

Mathur 620 Copyright © 2013 Dorling Kindersley (India) Pvt. what can we conclude about the adequacy of T with respect to another criterion C2? Effectiveness: Given a test set T that is adequate with respect to criterion C. Ltd Subsumes relation . what can we expect regarding its effectiveness in revealing errors? Contents Foundations of Software Testing 2E Author: Aditya P.Subsumes: Given a test set T that is adequate with respect to criterion C1.

Mathur 621 .Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Subsumes relationship Contents Foundations of Software Testing 2E Author: Aditya P.

Many more exist. Data flow based: c-use. p-uses. Ltd We have introduced the notion of test adequacy and enhancement. elementary data context. all-uses. Contents Foundations of Software Testing 2E Author: Aditya P. Control flow based: statement. and LCSAJ coverage.Summary Copyright © 2013 Dorling Kindersley (India) Pvt. MC/DC. Mathur 622 . Many more exist. condition. multiple condition. data context. Two types of adequacy criteria considered: one based on control flow and the other on data flow. decision. k-dr chain.

Ltd Use of any of the criteria discussed here requires a test tool that measures coverage .) during testing and displays it in a user-friendly manner. and Bullseye. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 623 Copyright © 2013 Dorling Kindersley (India) Pvt. Incremental assessment of code coverage and enhancement of tests can allow the application of coverage-based testing to large programs. This is a myth and needs to be shattered. xSUDS is one such set of tools. Several other commercial tools. are available. Several test organizations believe that code coverage is useful at unit-level.Summary (contd. such as PaRTe. Cobertura.

Tests derived using black-box approaches can almost always be enhanced using one or more of the assessment criteria discussed. Ltd Summary (contd. Contents Foundations of Software Testing 2E Author: Aditya P.) . Mathur 624 Copyright © 2013 Dorling Kindersley (India) Pvt. it is the perhaps the most effective way to assess the amount of code that has been tested and what remains untested.Even though coverage is not guaranteed to reveal all program errors.

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Chapter 8 Test Adequacy Measurement and Enhancement Using Mutation Updated: July 18. Mathur 625 . 2013 Foundations of Software Testing 2E Contents Author: Aditya P.

Ltd §  adequacy and how to use it to enhance tests? §  What is program mutation? §  Competent programmer hypothesis and the coupling effect.Learning Objectives What is test adequacy? What is test enhancement? When to measure test Copyright © 2013 Dorling Kindersley (India) Pvt. §  Mutation operators §  Tools for mutation testing Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 626 . §  Strengths and limitations of test adequacy based on program mutation.

§  We now ask: Is T good enough? This question can be stated differently as: Has P been tested thoroughly?.…. §  Suppose now that a set T containing k tests has been constructed to test P to determine whether or not it meets all the requirements in R . Mathur 627 Copyright © 2013 Dorling Kindersley (India) Pvt. Also.What is adequacy? Consider a program P written to meet a set R of functional requirements. Let R contain n requirements labeled R1. We notate such a P and R as ( P. Rn . R2. Ltd §  . R). P has been executed against each test in T and has produced correct behavior. or as: Is T adequate? Contents Foundations of Software Testing 2E Author: Aditya P.

Now suppose we do the following: Changed to P P’ What behavior do you expect from P’ against tests in T? Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 628 Copyright © 2013 Dorling Kindersley (India) Pvt.§  Suppose that program P has been tested against a test set T and P has not failed on any test case in T. Ltd What is program mutation? .

§  There might be a test t in T such that P(t)≠P’(t). In this case we say that T is unable to distinguish P and P’. Or. that t has killed P’. Ltd What is program mutation? [2] . §  There might be not be any test t in T such that P(t)≠P’(t). In this case we say that t distinguishes P’ from P.§  P’ is known as a mutant of P. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 629 Copyright © 2013 Dorling Kindersley (India) Pvt. Hence P’ is considered live in the test process.

Ltd What is program mutation? [3] . §  If P’ is not equivalent to P but no test in T is able to distinguish it from P then T is considered inadequate. We will refer to program mutation as mutation. Contents Foundations of Software Testing 2E Author: Aditya P. §  A non-equivalent and live mutant offers the tester an opportunity to generate a new test case and hence enhance T. Mathur 630 Copyright © 2013 Dorling Kindersley (India) Pvt.§  If there does not exist any test case t in the input domain of P that distinguishes P from P’ then P’ is said to be equivalent to P.

§ 

Given a test set T for program P that must meet requirements R, a test adequacy
assessment procedure proceeds as follows.

§ 

Step 1: Create a set M of mutants of P. Let M={M0, M1…Mk}. Note that we have
k mutants.

§ 

Step 2: For each mutant Mi find if there exists a t in T such that Mi(t) ≠P(t). If
such a t exists then Mi is considered killed and removed from further
consideration.
Contents

Foundations of Software Testing 2E

Author: Aditya P. Mathur

631

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Test adequacy using mutation [1]

§ 

Step 3: At the end of Step 2 suppose that k1 ≤ k mutants have been killed and (kk1) mutants are live.
Case 1: (k-k1)=0: T is adequate with respect to mutation.
Case 2: (k-k1)>0 then we compute the mutation score (MS) as follows:
MS=k1/(k-e)
where e is the number of equivalent mutants. Note: e ≤ (k-k1).
Contents

Foundations of Software Testing 2E

Author: Aditya P. Mathur

632

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Test adequacy using mutation [2]

§ 

One has the opportunity to enhance a test set T after having assessed its
adequacy.

§ 

Step 1: If the mutation score (MS) is 1, then some other technique, or a different
set of mutants, needs to be used to help enhance T.

§ 

Step 2: If the mutation score (MS) is less than 1, then there exist live mutants that
are not equivalent to P. Each live mutant needs to be distinguished from P.
Contents

Foundations of Software Testing 2E

Author: Aditya P. Mathur

633

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Test enhancement using mutation

§ 

Step 3: Hence a new test t is designed with the objective of distinguishing at least
one of the live mutants; let us say this mutant is m.

§ 

Step 4: If t does not distinguish m then another test t’ needs to be designed to
distinguish m. Suppose that t does distinguish m.

§ 

Step 5: It is possible that t also distinguishes other live mutants.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

634

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Test enhancement using mutation [2]

§ 

Step 6: Add t to T and re-compute the mutation score (MS).

§ 

Repeat the enhancement process from Step 1.

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Test enhancement using mutation [3]

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

635

§ 

As with any test enhancement technique, there is no guarantee that tests derived
to distinguish live mutants will reveal a yet undiscovered error in P. Nevertheless,
empirical studies have found to be the most powerful of all formal test
enhancement techniques.

§ 

The next simple example illustrates how test enhancement using mutation detects
errors.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

636

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Error detection using mutation

§ 

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Error detection using mutation [2]

Consider the following function foo that is required to return the sum of two
integers x and y. Clearly foo is incorrect.
int foo(int x, y){
return (x-y);

This should be return (x+y)

}

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

637

§ 

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Error detection using mutation [3]

Now suppose that foo has been tested using a test set T that contains two tests:
T={ t1: <x=1, y=0>, t2: <x=-1, y=0>}

§ 

First note that foo behaves perfectly fine on each test in, i.e. foo returns the
expected value for each test case in T. Also, T is adequate with respect to all
control and data flow based test adequacy criteria.
Contents

Foundations of Software Testing 2E

Author: Aditya P. Mathur

638

Error detection using mutation [4]

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Let us evaluate the adequacy of T using mutation. Suppose that the following
three mutants are generated from foo.
M1: int foo(int x, y){

§ 

M2: int foo(int x, y){

M3: int foo(int x, y){

return (x+y);

return (x-0);

return (0+y);

}

}

}

Note that M1 is obtained by replacing the - operator by a + operator, M2 by
replacing y by 0, and M3 by replacing x by 0.
Contents

Foundations of Software Testing 2E

Author: Aditya P. Mathur

639

Error detection using mutation [4]
Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Next we execute each mutant against tests in T until the mutant is distinguished
or we have exhausted all tests. Here is what we get.
T={ t1: <x=1, y=0>, t2: <x=-1, y=0>}
Test (t)

foo(t)

M1(t)

M2(t)

M3(t)

t1

1

1

1

0

t2

-1

-1

-1

0

Live

Live

Killed
Contents

Foundations of Software Testing 2E

Author: Aditya P. Mathur

640

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Error detection using mutation [5]
After executing all three mutants we find that two are live and one is
distinguished. Computation of mutation score requires us to determine of any of
the live mutants is equivalent.

In class exercise: Determine whether or not the two live mutants are equivalent
to foo and compute the mutation score of T.

Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

641

Error detection using mutation [6]

M1: int foo(int x, y){

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Let us examine the following two live mutants.
M2: int foo(int x, y){

return (x+y);

return (x-0);

}

}

Let us focus on M1. A test that distinguishes M1 from foo must
satisfy the following condition:
x-y≠x+y implies y ≠0.
Hence we get t3: <x=1, y=1>
Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

642

Error detection using mutation [7]

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Executing foo on t3 gives us foo(t3)=0. However, according to the requirements
we must get foo(t3)=2. Thus, t3 distinguishes M1 from foo and also reveals
the error.
M1: int foo(int x, y){

M2: int foo(int x, y){

return (x+y);

return (x-0);

}

}

In class exercise: (a) Will any test that distinguishes also reveal the error? (b)
Will any test that distinguishes M2 reveal the error?
Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

643

Guaranteed error detection

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd

Sometimes there exists a mutant P’ of program P such that any test t that
distinguishes P’ from P also causes P to fail. More formally:
Let P’ be a mutant of P and t a test in the input domain of P. We say
that P’ is an error revealing mutant if the following condition holds
for any t.
P’(t) ≠P(t) and P(t) ≠R(t), where R(t) is the expected response of P
based on its requirements.
Is M1 in the previous example an error revealing mutant? What about
M2?
Contents
Foundations of Software Testing 2E

Author: Aditya P. Mathur

644

Ltd A test case t that distinguishes a mutant m from its parent program P program must satisfy the following three conditions: Condition 1: Reachability: t must cause m to follow a path that arrives at the mutated statement in m.Distinguishing a mutant Copyright © 2013 Dorling Kindersley (India) Pvt. Condition 2: Infection: If Sin is the state of the mutant upon arrival at the mutant statement and Sout the state soon after the execution of the mutated statement. Contents Foundations of Software Testing 2E Author: Aditya P. then Sin≠ Sout. Mathur 645 .

Ltd Distinguishing a mutant [2] Condition 3: Propagation: If difference between Sin and Sout must propagate to the output of m such that the output of m is different from that of P.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 646 . Exercise: Show that in the previous example both t1 and t2 satisfy the above three conditions for M3. Contents Foundations of Software Testing 2E Author: Aditya P.

empirical studies have shown that one can expect about 5% of the generated mutants to the equivalent to the parent program. Mathur 647 . Hence there is no way to fully automate the detection of equivalent mutants. •  Identifying equivalent mutants is generally a manual and often time consuming--as well as frustrating--process. •  The number of equivalent mutants can vary from one program to another. However. Contents Foundations of Software Testing 2E Author: Aditya P.Equivalent mutants The problem of deciding whether or not a mutant is equivalent to its Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd •  parent program is undecidable.

int p=0.A misconception There is a widespread misconception amongst testing educators. including mutation. y){ Correct program int foo(int x. Mathur Contents 648 . will not be Program under test int foo(int x. and practitioners that any “coverage” based technique. p=p+1. if(x<y) p=p+1. Consider the following programs. y){ int p=0. if(x<y) Missing else Copyright © 2013 Dorling Kindersley (India) Pvt. return(x+p*y) else } p=p-1. return(x+p*y) } Foundations of Software Testing 2E Author: Aditya P. Ltd able to detect errors due to missing path. researchers.

A misconception [2] Copyright © 2013 Dorling Kindersley (India) Pvt. Is T guaranteed to reveal the error? (c) Suppose T is def-use adequate for foo. (b) Suppose T is decision adequate for foo. in other words M is an error revealing mutant. Mathur 649 . Is T guaranteed to reveal the error? Contents Foundations of Software Testing 2E Author: Aditya P. Ltd (a)  Suggest at least one mutant M of foo that is guaranteed to reveal the error.

M1 O(P) M2 …. Ltd Mutant operators A mutant operator O is a function that maps the program under test to a set of k (zero or more) mutants of P.•  Copyright © 2013 Dorling Kindersley (India) Pvt. Mk Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 650 .

Ltd Mutant operators [2] A mutant operator creates mutants by making simple changes in the program under test. the “variable replacement” mutant operator replaces a variable name by another variable declared in the program. Contents Foundations of Software Testing 2E Author: Aditya P.•  Copyright © 2013 Dorling Kindersley (India) Pvt. An “relational operator replacement” mutant operator replaces relational operator wirh another relational operator. Mathur 651 . •  For example.

Mathur 652 . z=x*(y+1)+1. Ltd Mutant operator Contents Foundations of Software Testing 2E Author: Aditya P. x=x*y+1. Replacement by 0 z=x*y+1. z=(x+1)*y+1. z=0. Copyright © 2013 Dorling Kindersley (India) Pvt.Mutant operators: Examples In P In mutant Variable replacement z=x*y+1. z=x+y-1. z=x*x+1. z=0*y+1. Relational operator replacement if (x<y) if(x>y) if(x<=y) Off-by-1 z=x*y+1. z=x*y-1. Arithmetic operator replacement z=x*y+1.

•  In practice only first order mutants are generated for two reasons: (a) to lower the cost of testing and (b) most higher order mutants are killed by tests adequate with respect to first order mutants. where the variable replacement operator has been applied twice. [See coupling effect later. Ltd order. Similarly higher order mutants can be defined. is x=z+y. a second order mutant of z=x+y.Mutants: First order and higher order •  A mutant obtained by making exactly “one change” is considered first •  Copyright © 2013 Dorling Kindersley (India) Pvt.] Contents Foundations of Software Testing 2E Author: Aditya P. For example. A mutant obtained by making two changes is a second order mutant. Mathur 653 .

instead of using x<y+1 one might use x<y. For example.Mutant operators: basis A mutant operator models a simple mistake that could be made by a Copyright © 2013 Dorling Kindersley (India) Pvt. As we shall see later. •  While programmers make “complex mistakes” too. Mathur 654 . mutant operators model simple mistakes. Ltd •  programmer •  Several error studies have revealed that programmers--novice and experts--make simple mistakes. the “coupling effect” explains why only simple mistakes are modeled. Contents Foundations of Software Testing 2E Author: Aditya P.

It Copyright © 2013 Dorling Kindersley (India) Pvt. Based on the effectiveness criteria. we say that S1 is superior to S2 if mutants generated using S1 guarantee a larger number of errors detected over a set of erroneous programs. Contents Foundations of Software Testing 2E Author: Aditya P. evident that two groups might arrive at a different set of mutation operators for the same programming language. Mathur 655 .Mutant operators: Goodness •  The design of mutation operators is based on guidelines and experience. How should we judge whether or not that a set of mutation operators is “good enough?” •  Informal definition: •  Let S1 and S2 denote two sets of mutation operators for language L. Ltd is Thus.

We say that one is using “constrained” or “selective” mutation when one uses this small set of mutation operators. Ltd •  rather than the complete set of operators. •  Experiments have revealed relatively small sets of mutation operators for C and Fortran. Contents Foundations of Software Testing 2E Author: Aditya P.Mutant operators: Goodness [2] Generally one uses a small set of highly effective mutation operators Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 656 .

and Java. C. •  Languages differ in their syntax thereby offering opportunities for making Copyright © 2013 Dorling Kindersley (India) Pvt. Ada. •  Mutant operators have been developed for languages such as Fortran. Ltd Mutant operators: Language dependence mistakes that duffer between two languages. Lisp.•  For each programming language one develops a set of mutant operators. This leads to differences in the set of mutant operators for two languages. [See the text for a comparison of mutant operators across several languages.] Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 657 .

while such a situation is unlikely to arise. a programmer is unlikely to write a program that deposits money into an account. given an account number. a programmer writes a program P that is in the general neighborhood of the set of correct programs. Ltd Competent programmer hypothesis (CPH) CPH states that given a problem statement. •  An extreme interpretation of CPH is that when asked to write a program to find the account balance. Of course.•  Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. a devious programmer might certainly write such a program. Mathur 658 .

Ltd •  to satisfy a set of requirements will be a few mutants away from a correct program. and makes use of. a competent programs knows of. Mathur 659 . at least one sorting algorithm. •  It is Thus. Contents Foundations of Software Testing 2E Author: Aditya P. and if not. Mistakes will lead to a program that can be corrected by applying one or more first order mutations. will find one prior to writing the program. •  The CPH assumes that the programmer knows of an algorithm to solve the problem at hand. safe to assume that when asked to write a program to sort a list of numbers.Competent programmer hypothesis (CPH) [2] A more reasonable interpretation of the CPH is that the program written Copyright © 2013 Dorling Kindersley (India) Pvt.

Ltd •  Sayward as follows: “Test data that distinguishes all programs differing from a correct one by only simple errors is so sensitive that it also implicitly distinguishes more complex errors” •  Stated alternately." Contents Foundations of Software Testing 2E Author: Aditya P. again in the words of DeMillo. Lipton. Mathur 660 ..seemingly simple tests can be quite sensitive via the coupling effect.Coupling effect The coupling effect has been paraphrased by DeMillo. Lipton and Sayward ``. and Copyright © 2013 Dorling Kindersley (India) Pvt.

This perturbation takes place at the point of mutation and has the potential of infecting the entire state of the program. Contents Foundations of Software Testing 2E Author: Aditya P. •  It is during an analysis of the behavior of the mutant in relation to that of its parent that one discovers complex faults.Coupling effect [2] For some input. Mathur 661 . Ltd •  the state space of the program under test. a non-equivalent mutant forces a slight perturbation in Copyright © 2013 Dorling Kindersley (India) Pvt.

We are not aware of any commercially available tool for mutation testing.Tools for mutation testing As with any other type of test adequacy assessment. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd •  assessment must be done with the help of a tool. Two such tools are Proteum for C from Professor Josè Maldonado and muJava for Java from Professor Jeff Offutt. See the textbook for a more complete listing of mutation tools. mutation based Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 662 . •  There are few mutation testing tools available freely.

§  Execution of the program under test against T and saving the output for Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd •  comparison against that of mutants. Contents Foundations of Software Testing 2E Author: Aditya P. §  A selectable palette of mutation operators. §  Management of test set T. §  Generation of mutants.Tools for mutation testing: Features A typical tool for mutation testing offers the following features. Mathur 663 .

§  Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. an advanced mutation tool for Fortran also provided automatic test generation using DeMillo and Offutt’s method. Mathur 664 .e. Ltd Tools for mutation testing: Features [2] Mutant execution and computation of mutation score using user identified equivalent mutants. §  Mothra. allows the application of a subset of mutation operators to a portion of the program under test. §  Incremental mutation testing: i.

Ltd §  relatively small units. a class in Java or a small collection of functions in C.Mutation and system testing Adequacy assessment using mutation is often recommended only for Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 665 . §  The following procedure is recommended to assess the adequacy of system tests. e. given a good tool. one can use mutation to assess adequacy of system tests. §  However. Contents Foundations of Software Testing 2E Author: Aditya P.g.

Ltd §  secure functioning of the application. Mathur 666 . §  Step 2: Select a small set of mutation operators. Repeat the following steps for each unit in U. This selection is best guided by the operators defined by Eric Wong or Jeff Offutt.Mutation and system testing [2] Step 1: Identify a set U of application units that are critical to the safe and Copyright © 2013 Dorling Kindersley (India) Pvt.] §  Step 3: Apply the operators to the selected unit. Contents Foundations of Software Testing 2E Author: Aditya P. [See the text for details.

.§  Step 4: Assess the adequacy of T using the mutants so generated. Note the use of incremental testing and constrained mutation (i. §  Step 5: Repeat Steps 3 and 4 for the next unit until all units have been considered. and perhaps enhanced it.e. If necessary. enhance T. Contents Foundations of Software Testing 2E Author: Aditya P. use of a limited set of highly effective mutation operators). §  We have now assessed T. Mathur 667 Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Mutation and system testing [3] .

Mathur 668 . Ltd Mutation and system testing [4] Application of mutation.§  Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. security. is recommended for applications that must meet stringent availability. safety requirements. and other advanced test assessment and enhancement techniques.

§  Identification of equivalent mutants is an undecidable problem--similar the identification of infeasible paths in control or data flow based test assessment.Summary Mutation testing is the most powerful technique for the assessment and Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. as with any other test assessment technique. §  Mutation. must be applied incrementally and with assistance from good tools. Ltd §  enhancement of tests. Mathur 669 .

it can be used for the assessment of system and other types of tests applied to an entire application. secure. Mathur 670 .Summary [2] While mutation testing is often recommended for unit testing. when done Copyright © 2013 Dorling Kindersley (India) Pvt. and safe systems. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd §  carefully and incrementally. §  Mutation is a highly recommended technique for use in the assurance of quality of highly available.

Test Selection. and Prioritization for Regression Testing Updated: July 17. Ltd Chapter 9 . Mathur 671 Copyright © 2013 Dorling Kindersley (India) Pvt. 2013 Foundations of Software Testing 2E Contents Author: Aditya P. Minimization.

Mathur 672 .Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Learning Objectives What is regression testing? How to select a subset of tests for regression testing? How to select or minimize a set of tests for regression testing? How to prioritize a set of tests for regression testing? Contents Foundations of Software Testing 2E Author: Aditya P.

Mathur 673 .Copyright © 2013 Dorling Kindersley (India) Pvt.1. Ltd 9. What is regression testing? Contents Foundations of Software Testing 2E Author: Aditya P.

Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 674 . Ltd Regression testing Contents Foundations of Software Testing 2E Author: Aditya P.

Copyright © 2013 Dorling Kindersley (India) Pvt. [This is the TEST-ALL approach. Ltd What tests to use? Idea 1: All valid tests from the previous version and new tests created to test any added functionality. Mathur 675 .] What are the strengths and shortcomings of this approach? Contents Foundations of Software Testing 2E Author: Aditya P.

But what if you have limited resources to run tests and have to meet a deadline? What if running all tests as well as meeting the deadline is simply not possible? Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd The test-all approach The test-all approach is best when you want to be certain that the the new version works on all tests developed for the previous version and any new tests. Mathur 676 .

We will discuss two of these known as test minimization and test prioritization. Ltd Idea 2: Select a subset Tr of the original test set T such that successful execution of the modified code P’ against Tr implies that all the functionality carried over from the original code P to P‘is intact. Finding Tr can be done using several methods. Mathur 677 . Contents Foundations of Software Testing 2E Author: Aditya P.Test selection Copyright © 2013 Dorling Kindersley (India) Pvt.

Ltd 9.Copyright © 2013 Dorling Kindersley (India) Pvt.3. Regression test selection: The problem Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 678 .

our goal is to determine Tr such that successful execution of P’ against Tr implies that modified or newly added code in P’ has not broken the code carried over from P. Contents Foundations of Software Testing 2E Author: Aditya P.Given test set T. Ltd Regression Test Selection problem . Mathur 679 Copyright © 2013 Dorling Kindersley (India) Pvt. Such tests are not included in the regression subset Tr. The task of identifying such obsolete tests is known as test revalidation. Note that some tests might become obsolete when P is modified to P’.

Mathur 680 . Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Now that we know what the regression test selection problem is. let us look at an overall regression test process.Regression Test Process Test selection Test setup Copyright © 2013 Dorling Kindersley (India) Pvt. Test sequencing Test execution Error correction Output analysis In this chapter we will learn how to select tests for regression testing.

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd 9.5. Test selection using execution trace Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 681 .

Step 2: Extract test vectors from the execution traces for each node in the CFG of P Step 3: Construct syntax trees for each node in the CFGs of P and P’.Overview of a test selection method Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. find the execution trace of P for each test in T. Ltd Step 1: Given P and test set T. Mathur 682 . Step 4: Traverse the CFGs and determine the a subset of T appropriate for regression testing of P’. This step can be executed while constructing the CFGs of P and P’.

Let Tno be the set of all valid tests for P’. Contents Foundations of Software Testing 2E Author: Aditya P. Suppose that nodes in N are numbered 1. Ltd Let G=(N. and so on and that Start and End are two special nodes as discussed in Chapter 1. Tno contains only tests valid for P’. Thus.Execution Trace [1] Copyright © 2013 Dorling Kindersley (India) Pvt. E) denote the CFG of program P. It is obtained by discarding all tests that have become obsolete for some reason. 2. N is a finite set of nodes and E a finite set of edges connecting the nodes. Mathur 683 .

consider the following program.Execution Trace [2] G traversed when P is executed against t. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd An execution trace of program P for some test t in Tno is the sequence of nodes in . As an example. Mathur 684 Copyright © 2013 Dorling Kindersley (India) Pvt.

Execution Trace [3] Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 685 . Ltd Here is a CFG for our example program.

Mathur 686 . Ltd Now consider the following set of three tests and the corresponding trace.Execution Trace [4] Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P.

Ltd A test vector for node n. For program P we obtain the following test vectors. denoted by test(n).Test vector Copyright © 2013 Dorling Kindersley (India) Pvt. is the set of tests that traverse node n in the CFG. Mathur 687 . Contents Foundations of Software Testing 2E Author: Aditya P.

Ltd each node represents a basic block.Syntax trees A syntax tree is constructed for each node of CFG(P) and CFG(P’). Mathur 688 . Recall that Copyright © 2013 Dorling Kindersley (India) Pvt. Here sample syntax trees for the example program. Contents Foundations of Software Testing 2E Author: Aditya P.

Mathur 689 . Ltd Given the execution traces and the CFGs for P and P’. the following three steps are executed to obtain a subset T’ of T for regression testing of P’.Test selection [1] Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P.

Contents Foundations of Software Testing 2E Author: Aditya P. If two two nodes N in CFG(P) and N’ in CFG( P’) are found to be syntactically different.Test selection [2] Copyright © 2013 Dorling Kindersley (India) Pvt. The descent proceeds in parallel and the corresponding nodes are compared. Mathur 690 . all tests in test (N) are added to T’. Ltd The basic idea underlying the SelectTests procedure is to traverse the two CFGs from their respective START nodes using a recursive descent procedure.

Ltd Suppose that function g1 in P is modified as follows. Try the SelectTests algorithm and check if you get T’={t1. t3}. Contents Foundations of Software Testing 2E Author: Aditya P.Test selection example Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 691 .

Ltd Issues with SelectTests Think: What tests will be selected when only. one declaration is modified? Can you think of a way to select only tests that correspond to variables in the modified declaration? Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 692 .Copyright © 2013 Dorling Kindersley (India) Pvt. say.

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd 9.6. Test selection using dynamic slicing Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 693 .

is the set of statements in P that (a) lie in trace(t) and (b) effected the value of v at L. v. Question: What is the dynamic slice of P with respect to v and t if L is not in trace(t)? Contents Foundations of Software Testing 2E Author: Aditya P. The dynamic slice of P with respect to t and v. denoted as DS(t. L).Let L be a location in program P and v a variable used at L. Ltd Dynamic slice . Let trace(t) be the execution trace of P when executed against test t. Mathur 694 Copyright © 2013 Dorling Kindersley (India) Pvt.

] Contents Foundations of Software Testing 2E Author: Aditya P.Dynamic dependence graph (DDG) Copyright © 2013 Dorling Kindersley (India) Pvt. There are no edges among these nodes. Step 1: Initialize G with a node for each declaration. Control and data dependence edges are added from n to the existing nodes in G. Here is how a DDG G is constructed. Step 2: Add to G the first node in trace(t). [Recall from Chapter 2 the definitions of control and data dependence edges. Mathur 695 . Ltd The DDG is needed to obtain a dynamic slice. Step 3: For each successive statement in trace(t) a new node n is added to G.

3. 8} Ignore declarations for simplicity. Add a node to G corresponding to statement 1. 1 Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 696 Copyright © 2013 Dorling Kindersley (India) Pvt. 3. 2. and 3 respectively. trace(t)={1. 2. 6. Ltd Construction of a DDG: Example [1] . 0 and 5. 7.Let t: <x=2. y=4> Assume successive values of x to be 2. and for these values f1(x) is 0. 6. 2. 7. 2. 4. 5.

6. 7. 5. 2. Also add a data dependence edge from node 3 to node 1 as statement 3 is data dependent on statement 1 and a control edge from node 3 to 2. 2. Also add a data dependence edge from 2 to 1 as statement 2 is data dependent on statement 1. Mathur 697 Copyright © 2013 Dorling Kindersley (India) Pvt. 7.Construction of a DDG: Example [2] Add another node corresponding to statement 2 in trace(t). 3. 1 2 3 Contents Foundations of Software Testing 2E Author: Aditya P. 1 should be… 3 if(f1(x)==0) 2 Add yet another node corresponding to statement 3 in trace(t). Ltd trace(t)={1. 6. 3. 8} . 2. 4.

2. 7. 2.Construction of a DDG: Example [3] Copyright © 2013 Dorling Kindersley (India) Pvt. 3. 6. 4. Mathur 698 . 6. 8} Continuing this way we obtain the following DDG for program P and trace(t). should be… 3 if(f1(x)==0) Contents Foundations of Software Testing 2E Author: Aditya P. Ltd trace(t)={1. 5. 3. 7. 2.

n) of all nodes reachable from n. DS(t. v. Step 4: Find in G the set DS(t. n) is the dynamic slice of P with respect to v at location L and test t. v. If no such node exists then the dynamic slice is empty. Step 3: Identify in G node n labeled L that contains the last assignment to v. Ltd Step 1: Execute P against test t and obtain trace(t). including n. Mathur 699 . Step 2: Construct the dynamic dependence graph G from P and trace(t).Obtaining dynamic slice (DS) Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P. other wise execute Step 4.

We already have the DDG of P for t. Traverse the DDG backwards from node 7 and collect all nodes reachable from 7. Ltd Suppose we want to compute the dynamic slice of P with respect to variable w at line 8 and test t shown earlier. Mathur 700 . This gives us the following dynamic slice: {1. This occurs at line 7 as marked. 2. 7. Contents Foundations of Software Testing 2E Author: Aditya P. 5. 8}. 6.Obtaining dynamic slice: Example Copyright © 2013 Dorling Kindersley (India) Pvt. First identify the last definition of w in the DDG. 3.

. Ltd Let T be the test set used to test P. Which tests from T should be used to obtain a regression test T’ for P’? Find DS(t) for P. P’ is the modified program. If any of the modified nodes is in DS(t) then add t to T’. Contents Foundations of Software Testing 2E Author: Aditya P.nk be the nodes in the CFG of P modified to obtain P’.Test selection using dynamic slice Copyright © 2013 Dorling Kindersley (India) Pvt. Let n1. . n2. Mathur 701 .

Ltd In class exercise Suppose line 4 in the example program P shown earlier is modified to obtain P’.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 702 . (a)  Should t be included in T’? (b)  Will t be included in T’ if we were to use the execution slice instead of the dynamic slice to make our decision? Contents Foundations of Software Testing 2E Author: Aditya P.

Mathur 703 . the variable of interest. especially for large programs.Teasers [1] Copyright © 2013 Dorling Kindersley (India) Pvt. How can such statements be identified? [Hint: Read about potential dependence. Ltd You may have noticed that a DDG could be huge.] Contents Foundations of Software Testing 2E Author: Aditya P. How can one reduce the size of the DDG and still obtain the correct DS? The DS contains all statements in trace(t) that had an effect on w. However there could be a statement s in trace(t) that did not have an effect but could affect w if changed.

how would you select the variable for which to obtain the dynamic slice? Contents Foundations of Software Testing 2E Author: Aditya P. While selecting regression tests. Mathur 704 . Ltd Suppose statement s in P is deleted to obtain P’? How would you find the tests that should be included in the regression test suite? Suppose statement s is added to P to obtain P’? How would you find the tests that should be included in the regression test suite? In our example we used variable w to compute the dynamic slice.Teasers [2] Copyright © 2013 Dorling Kindersley (India) Pvt.

Ltd 9.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 705 .8 Test selection using test minimization Contents Foundations of Software Testing 2E Author: Aditya P.

Mathur 706 . Ltd Test minimization [1] Test minimization is yet another method for selecting tests for regression testing. To illustrate test minimization. main and f. Contents Foundations of Software Testing 2E Author: Aditya P.Copyright © 2013 Dorling Kindersley (India) Pvt. Now suppose that P is tested using test cases t1 and t2. suppose that P contains two functions. During testing it was observed that t1 causes the execution of main but not of f and t2 does cause the execution of both main and f.

Which of the two test cases should be included in the regression test suite? Obviously there is no need to execute P’ against t1 as it does not cause the execution of f. Mathur 707 . t2} to a obtain the regression test suite {t2}. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Now suppose that P’ is obtained from P by making some modification to f. the regression test suite consists of only t2. Thus.Test minimization [2] Copyright © 2013 Dorling Kindersley (India) Pvt. In this example we have used function coverage to minimize a test suite {t1.

def-use chains. One uses the following procedure to minimize a test set based on a selected testable entity. and mutants.Copyright © 2013 Dorling Kindersley (India) Pvt. program statements. Mathur 708 . for example. Ltd Test minimization [3] Test minimization is based on the coverage of testable entities in P. Testable entities include. Contents Foundations of Software Testing 2E Author: Aditya P. decisions.

Let e1. . Step 2: Execute P against all elements of test set T and for each test t in T determine which of the k testable entities is covered.A procedure for test minimization Copyright © 2013 Dorling Kindersley (India) Pvt. Step 3: Find a minimal subset T’of T such that each testable entity is covered by at least one test in T’.ek be the k testable entities of type TE present in P. e2. Contents Foundations of Software Testing 2E Author: Aditya P. Ltd Step 1: Identify the type of testable entity to be used for test minimization. In our previous example TE is function.. Mathur 709 .

3 Step3: A minimal test set for regression testing is {t1. 2. 3. 3 t2: main: 1. 3. Mathur 710 .Test minimization: Example Step 1: Let the basic block be the testable entity of interest. Ltd blocks for a sample program are shown here for both main and function f1. The basic Copyright © 2013 Dorling Kindersley (India) Pvt. t3}. f1: 1. Contents Foundations of Software Testing 2E Author: Aditya P. f1: 1. 3 t1: main: 1. f1: 1. Step 2: Suppose the coverage of the basic blocks when executed against three tests is as follows: t1: main: 1. 2. 3.

Ltd Test minimization: Teasers . Is the minimal test set unique? Why or why not? Is test minimization NP hard? How is the traditional set cover problem in mathematics related to the test minimization problem? What criteria should be used to decide the kind of testable entity to be used for minimization? Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 711 Copyright © 2013 Dorling Kindersley (India) Pvt.

Ltd 9.9 Test selection using test prioritization Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 712 .Copyright © 2013 Dorling Kindersley (India) Pvt.

There is a small chance that if P’ were executed against a discarded test case it would reveal an error in the modification made. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 713 . the one with the next highest coverage m the next higher priority and so on. it might not be wise to discard test cases as in test minimization. Ltd Note that test minimization will likely discard test cases. In such cases one uses test prioritization. When very high quality software is desired. Tests are prioritized based on some criteria. tests that cover the maximum number of a selected testable entity could be given the highest priority. For example.Test prioritization Copyright © 2013 Dorling Kindersley (India) Pvt.

Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 714 .. Test with the maximum coverage gets the highest priority and so on. For each t in T compute the number of distinct testable entities covered. . Let e1. Ltd A procedure for test prioritization Step 1: Identify the type of testable entity to be used for test minimization.Copyright © 2013 Dorling Kindersley (India) Pvt. Step 2: Execute P against all elements of test set T and for each test t in T.ek be the k testable entities of type TE present in P. Step 3: Arrange the tests in T in the order of their respective coverage. In our previous example TE is function. e2.

The choice is guided by several factors such as the resources available for regression testing and the desired product quality. Ltd Using test prioritization Once the tests are prioritized one has the option of using all tests for regression testing or a subset. In any case test are discarded only after careful consideration that does not depend only on the coverage criteria used.Copyright © 2013 Dorling Kindersley (India) Pvt. Mathur 715 . Contents Foundations of Software Testing 2E Author: Aditya P.

Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd 9. Tools Contents Foundations of Software Testing 2E Author: Aditya P.10. Mathur 716 .

Instead they rely on the tester for test selection. xSuds from Telcordia Technologies can be used for C programs to minimize and prioritize tests. Ltd Methods for test selection described here require the use of an automated tool for all but trivial programs. they do not use any of the algorithms described here for test selection.Tools for regression testing Copyright © 2013 Dorling Kindersley (India) Pvt. Such tool are especially useful when all tests are to be rerun. Many commercial tools for regression testing simply run the tests automatically. Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 717 .

In a situation where test resources are limited and deadlines are to be met. execution of all tests might not be feasible. In such situations one can make use of sophisticated technique for selecting a subset of all tests and hence reduce the time for regression testing. Mathur 718 . Ltd Summary [1] Regression testing is an essential phase of software product development.Copyright © 2013 Dorling Kindersley (India) Pvt. Contents Foundations of Software Testing 2E Author: Aditya P.

Select tests using execution slices [based on execution traces].Summary [2] Copyright © 2013 Dorling Kindersley (India) Pvt. Select tests using dynamic slices [based on execution traces and dynamic slices]. Select tests using code coverage [based on the coverage of testable entities]. Mathur 719 . Ltd Test selection for regression testing can be done using any of the following methods: Select only the modification traversing tests [based on CFGs]. Contents Foundations of Software Testing 2E Author: Aditya P.

Mathur 720 .Copyright © 2013 Dorling Kindersley (India) Pvt. Most commercially available tools are best in situations where test selection is done manually and do not use the techniques described in this chapter. Ltd Summary [3] Select tests using a combination of code coverage and human judgment [based on amount of the coverage of testable entities]. Contents Foundations of Software Testing 2E Author: Aditya P. Use of any of the techniques mentioned here requires access to sophisticated tools.

Mathur 721 .Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd Chapter 10 Unit Testing [Under Construction] Contents Foundations of Software Testing 2E Author: Aditya P.

Ltd Chapter 11 Integration Testing [Under Construction] Contents Foundations of Software Testing 2E Author: Aditya P. Mathur 722 .Copyright © 2013 Dorling Kindersley (India) Pvt.