SOFTWARE TESTING-ARVIND G

MIT First Grade College

Manandavadi Road, Mysore-08
Affiliated to University of Mysore

VISION OF THE INSTITUTE

Empower the individuals and society at large through educational excellence;
sensitize them for a life dedicated to the service of fellow human beings and
mother land.
MISSION OF THE INSTITUTE
To impact holistic education that enables the students to become socially
responsive and useful, with roots firm on traditional and cultural values; and
to hone their skills to accept challenges and respond to opportunities in a global
scenario.
Lecture Notes on
Elective: SOFTWARE TESTING (LTP::4:1:1)
Course Outcomes
CO’s DESCRIPTION OF THE OUTCOMES BT
LEVEL
CO1 Interpret the fundamentals of software testing. L2
CO2 Describe test categories, test design techniques and test types, analyze L2
requirements and develop and test the test cases for functional and structural
test types.
CO3 Evaluate various techniques of testing at different levels of SDLC. L4
CO4 Analyse and write test cases to test software applications. L4, L3
CO5 Describe with example interaction, object oriented and class testing. L2

Prepared by
Asst. Prof. ARVIND G
Department
COMPUTER SCIENCE - B.C.A.

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Syllabus

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

UNIT – 1
Table of Contents
[Link]. Topics Page
No.
1 Basic Definitions 3-4

2 Test Cases 5

3 Insights from a Venn Diagram 5-6

4 Identifying Test Cases 6-7

5 Errors and Fault Taxonomies 8

6 Levels of Testing 8-9

7 Examples 10-13

7.1 Generalized pseudo code

7.2 The Triangle Problem

7.3 The NEXT Date Function

7.4 The Commission Problem

7.5 The SATM Problem

8 Decision Table-Based Testing-Decision Tables 14-20

8.1 Test Cases for the Triangle Problem

8.2 Test Cases for the NEXT Date Function

8.3 Test Cases for the Commission Problem

8.4 Guidelines and Observations

9 Data Flow Testing 21-24

9.1 Use Testing

9.2 Slice-Based Testing

9.3 Guidelines and Observations

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Dept. of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

DATA FLOW TESTING

3.1 Data Flow Testing

➢ Data flow testing refers to forms of structural testing that focus on the points at which variables
receive values and the points at which these values are used (or referenced).
➢ We will look at two mainline forms of data flow testing: one provides a set of basic definitions
and a unifying structure of test coverage metrics, while the second is based on a concept called a
“program slice”. Both of these formalize intuitive behaviors (and analyses) of testers, and
although they both start with a program graph, both move back in the direction of functional
testing.
➢ Most programs deliver functionality in terms of data. Variables that represent data somehow
receive values, and these values are used to compute values for other variables. Since the early
1960s, programmers have analyzed source code in terms of the points (statements) at which
variables receive values and points at which these values are used. Many times, their analyses
were based on concordances that list statement numbers in which variable names occur.
➢ Early “data flow” analyses often centered on a set of faults that are now known as define/reference
anomalies:
• a variable that is defined but never used (referenced)
• a variable that is used but never defined
• a variable that is defined twice before it is used
➢ Each of these anomalies can be recognized from the concordance of a program. Since the
concordance information is compiler generated, these anomalies can be discovered by what is
known as “static analysis”: finding faults in source code without executing it.

3.6.1 Define/Use Testing

➢ The following definitions refer to a program P that has a program graph G(P), and a set of program
variables V. The program graph G(P) is with statement fragments as nodes, and edges that
represent node sequences.
➢ G(P) has a single entry node, and a single exit node. We also disallow edges from a node to itself.
Paths, sub paths, and cycles.

Dept of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Definition
✓ Node n € G(P) is a defining node of the variable v €V, written as DEF(v,n), if the value of the
variable v is defined at the statement fragment corresponding to node n.
➢ Input statements, assignment statements, loop control statements, and procedure calls are all
examples of statements that are defining nodes. When the code corresponding to such statements
executes, the contents of the memory location(s) associated with the variables are changed.

Definition
✓ Node n □ G(P) is a usage node of the variable v □ V, written as USE(v, n), if the value of
the variable v is used at the statement fragment corresponding to node n.
➢ Output statements, assignment statements, conditional statements, loop control statements, and
procedure calls are all examples of statements that are usage nodes. When the code corresponding
to such statements executes, the contents of the memory location(s) associated with the variables
remain unchanged.

Definition
✓ A usage node USE(v, n) is a predicate use (denoted as P-use) iff the statement n is a predicate
statement; otherwise USE(v, n) is a computation use , (denoted C-use).
➢ The nodes corresponding to predicate uses always have an outdegree ≥ 2, and nodes corresponding
to computation uses always have outdegree ≤ 1.

Definition
✓ A definition-use (sub)path with respect to a variable v (denoted du-path) is a
(sub)path in PATHS(P) such that, for some v □ V, there are define and usage nodes DEF(v,
m) and USE(v, n) such that m and n are the initial and final nodes of the (sub)path.

Definition
✓ A definition-clear (sub)path with respect to a variable v (denoted dc-path) is a definition-use
(sub)path in PATHS(P) with initial and final nodes DEF (v, m) and USE (v, n) such that no other
node in the (sub)path is a defining node of v.

Dept of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

➢ Testers should notice how these definitions capture the essence of computing with stored data
values. Du-paths and dc-paths describe the flow of data across source statements from points at
which the values are defined to points at which the values are used. Du-paths that are not
definition-clear are potential trouble spots.

3.6.2 Example
➢ We will use the Commission Problem and its program graph to illustrate these definitions. The
numbered source code is given next, followed by a program graph constructed according to
the procedures.
➢ This program computes the commission on the sales of four salespersons, hence the outer For-
loop that repeats four times. During each repetition, a salesperson’s name is read from the
input device, and the input from that person is read to compute the total numbers of locks, stocks,
and barrels sold by the person.
➢ The While-loop is a classical sentinel controlled loop in which a value of -1 for locks signifies
the end of that person’s data. The totals are accumulated as the data lines are read in the While-
loop.
➢ After printing this preliminary information, the sales value is computed, using the constant item
prices defined at the beginning of the program. The sales value is then used to compute the
commission in the conditional portion of the program.

1 Program Commission (Input, Output)

2 Dim locks, stocks and barrels As Integer
3 Dim lockprice, stocksprice and barrelprice As Real
4 Dim totallocks, totalstocks and totalbarrels As Integer
5 Dim locksales, stockssales and barrelsales As Real
6 Dim sales, commission As Real
7 lock_price = 45.0;
8 stock_price = 30.0;
9 barrel_price 25.0;
10 totallocks =0
11 totalstocks =0

Dept of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

12 totalbarrels =0
13 input (locks)
14 while NOT (locks= -1) ‘loop condition uses -1 to indicate end of data’
15 input(stocks, barrels)
16 totallocks = totallocks + locks
17 totalstocks = totalstocks + stocks
18 totalbarrels = totalbarrels + barrels
19 input (locks)
20 Endwhile
21 Output (“Locks sold: “, totallocks)
22 Output (“stocks sold: “, totalstocks)
23 Output (“Barrels sold: “, totalbarrels)
24 locksales = lockprice * totallocks
25 stocksales = stockprice * totalstocks
26 barrelsales = barrelprice * totalbarrels
27 sales = locksales+ stocksales + barrelsales
28 output (“total sales:”, sales)
29 If (sales > 1800.0)
30 Then
31 Commission = 0.10 * 1000.0
32 Commission = Commission + 0.15 * 800.0
33 Commission = Commission + 0.20 * (sales - 1800.0)
34 Else if (sales > 1000.0)
35 Then
36 Commission = 0.10 * 1000.0
37 Commission = Commission + 0.15 * (sales - 1000.0)
38 Else
39 Commission = 0.10 * 1000.0
40 Endif
41 Endif
42 Output (“commission is $”, commission)

Dept of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

43 End commission

➢ The DD-Paths in this program are given in Table 1, and the DD-Path graph is shown in Figure
10.2. Tables 2 and 3 list the define and usage nodes for five variables in the commission problem.
We use this information in conjunction with the program graph in Figure 10.1 to identify various
definition-use and definition-clear paths.
Table 1 DD-Paths in Figure 10.1
Nodes
A 7,8,9,10,11,12,13
B 14
C 15,16,17,18,19,20
D 21,22,23,24,25,26,27,28
E 29
F 30,31,32,33
G 34
H 35,36,37
I 38,39
J 40
K 41,42,43

➢ It’s a judgment call whether or not non-executable statements such as constant (CONST) and
variable (VAR) declaration statements should be considered as defining nodes. Technically, these
only define memory space (the CONST declaration creates a compiler-produced initial value).
Such nodes aren’t very interesting when we follow what happens along their du-paths, but if there
is something wrong, it’s usually helpful to include them. Take your pick. We will refer to the
various paths as sequences of node numbers.

3.1.2 du-paths for Stocks

➢ First, let’s look at the du-paths for the variable stocks. We have DEF(stocks, 15) and USE(stocks,
17), so the path <15, 17> is a du-path wrt (with respect to) stocks. Since there are no other
defining nodes for stocks, this path is also definition-clear.

Dept of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

7 8 9 10 11 12 13

14
15 16 17 18 19 20

21 22 23 24 25 26 27 28

29

34
30

38
31
35

32 36
39
37
33

40

23 42 43

Figure 3.1 Program Graph of the Commission Program

3.1.3 du-paths for Locks
➢ Two defining and two usage nodes make the locks variable more interesting: we have DEF(locks,
13), DEF(locks, 19), USE(locks, 14), and USE(locks, 16). These yield four du- paths:

Dept of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

p1 = <13, 14>
p2 = <13, 14,15,16>
p3 = <19, 20, 14>
p4 = <19,20, 14,15, 16>

➢ Du-paths p1 and p2 refer to the priming value of locks which is read at node 13: locks has
a predicate use in the While statement (node 14), and if the condition is true (as in path p2),
a computation use at statement 16. The other two du-paths start near the end of the While loop and
occur when the loop repeats.

F H I

J
K

Figure 3.2 DD-Path Graph of the Commission Program

3.1.4 du-paths for totallocks

➢ The du-paths for totallocks will lead us to typical test cases for computations. With two defining
nodes (DEF(totallocks, 10) and DEF(totallocks, 16)) and three usage nodes

Dept of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

(USE(totallocks, 16), USE(totallocks, 21), USE(totallocks, 24)), we might expect six du- paths.
➢ Path p5 = <10,11,12,13,14,15,16> is a du-path in which the initial value (0) has a computation
use. This path is definition-clear. The next path is problematic:
p6 = <10,11,12,13,14,15,16,17,18,19,20,14,21>
➢ We have ignored the possible repetition of the While-loop. We could highlight this by noting
that the subpath <16,17,18,19,20,14,15> might be traversed several times. Ignoring this for
now, we still have a du-path that fails to be definition-clear. If there is a problem with the value
of totallocks at node 21 (the WRITE statement), we should look at the intervening DEF(totallocks,
16) node.
➢ The next path contains p6; we can show this by using a path name in place of its corresponding
node sequence:
p7 = <10,11,12,13,14,15,16,17,18,19,20,14,21, 22, 23, 24>
p7 = < p6, 22, 23, 24>
Du-path p7 is not definition-clear because it includes node 16.
➢ Subpaths that begin with node 16 (an assignment statement) are interesting. The first, <16, 16>,
seems degenerate. If we “expanded” it into machine code, we would be able to separate the define
and usage portions. We will disallow these as du-paths.
➢ Technically, the usage on the right-hand side of the assignment refers to a value defined at node
10, (see path p5). The remaining two du-paths are both subpaths of p7:
p8 = <16,17,08,19,20,14,21>
p9 = <16,17,08,19,20,14,21,22,23,24>
Both of these are definition-clear, and both have the loop iteration problem we discussed before.

3.1.5 du-paths for sales

➢ Since there is only one defining node for sales, all the du-paths wrt sales must be definition- clear.
They are interesting because they illustrate predicate and computation uses. The first three du-
paths are easy:
p10 = <27,28>
p11 = <27,28,29>

Dept of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

p12 = <27,28,29,30,31,32,33>

➢ Notice that p12 is a definition-clear path with three usage nodes; it also contains paths p10 and
p11. If we were testing with p12, we know we would also have covered the other two paths.
➢ The IF, ELSE IF logic in statements 29 through 40 highlights an ambiguity in the original research.
There are two choices for du-paths that begin with path p11: the static choice is the path
<27,28,29,30,31,32,33>, the dynamic choice is the path <27,28,29,34>. Here we will use the
dynamic view, so the remaining du-paths for sales are
p13 = <27,28,29,34>
p14 = <27,28,29,34,35,36,37>
p15 = <27,28,29,34,38,39>

Note that the dynamic view is very compatible with the kind of thinking we used for DD- Paths.

10.1.6 du paths for Commission

➢ If you have followed this discussion carefully, you are probably dreading the stuff on du- paths
wrt commission. You’re right -- it’s time for a change of pace. In statements 29 through 41,
the calculation of commission is controlled by ranges of the variable sales.
➢ Statements 31 to 33 build up the value of commission by using the memory location to hold
intermediate values.
➢ This is a common programming practice, and it is desirable because it shows how the final
value is computed. (We could replace these lines with the statement “commission := 220 +
0.20* (sales -1800)”, where 220 is the value of 0.10*1000 + 0.15*800, but this would be
hard for a maintainer to understand.)
➢ The “built-up” version uses intermediate values, and these will appear as define and usage nodes
in the du-path analysis. Since we decided to disallow du-paths from assignment statements like
31 and 32, we’ll just consider du-paths that begin with the three “real” defining nodes:
DEF(commission, 33), DEF(commission, 37), and DEF(commission, 38). There is only one
usage node, USE(commission, 42).

Dept of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

3.6.3 Du-path Test Coverage Metrics

➢ The whole point of analyzing a program as in the previous section is to define a set of test coverage
metrics known as the Rapps-Weyuker data flow metrics [Rapps 85].
➢ The first three of these are equivalent to three of E. F. Miller’s metrics: All-Paths, All-Edges, and
All-Nodes. The others presume that define and usage nodes have been identified for all program
variables, and that du-paths have been identified with respect to each variable.
➢ In the following definitions, T is a set of (sub)paths in the program graph G(P) of a program P,
with the set V of variables.

Definition
The set T satisfies the All-Defs criterion for the program P iff for every variable v □ V, T contains
definition clear (sub)paths from every defining node of v to a use of v.

Definition
The set T satisfies the All-Uses criterion for the program P iff for every variable v □ V, T contains
definition-clear (sub)paths from every defining node of v to every use of v, and to the successor
node of each USE(v,n).

Definition
The set T satisfies the All-P-Uses /Some C-Uses criterion for the program P iff for every variable
v □ V, T contains definition-clear (sub)paths from every defining node of v to every predicate use
of v, and if a definition of v has no P-uses, there is a definition-clear path to at least one
computation use.

Definition
The set T satisfies the All-C-Uses /Some P-Uses criterion for the program P iff for every variable
v □ V, T contains definition-clear (sub)paths from every defining node of v to every computation
use of v, and if a definition of v has no C-uses, there is a definition-clear path to at least one
predicate use.

Dept of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Definition
The set T satisfies the All-DU-paths criterion for the program P iff for every variable v □ V,
T contains definition-clear (sub)paths from every defining node of v to every use of v, and to
the successor node of each USE(v,n), and that these paths are either single loop traversals, or they
are cycle free.

➢ These test coverage metrics have several set-theory based relationships, which are referred to
as “subsumption” in [Rapps 85]. When one test coverage metric subsumes another, a set of
test cases that attains coverage in terms of the first metric necessarily attains coverage with
respect to the subsumed metric. These relationships are shown in Figure 3.3.

All -Paths

All- DU-Paths

All- Uses

All- C-Uses/some-P-uses All- P-Uses/some-C-uses

All- P-uses
All-Defs

All- Edges

All- Nodes

Figure 3.3 Rapps/Weyuker Hierarchy of Data Flow Coverage Metrics

3.2 Slice-Based Testing

➢ Program slices have surfaced and submerged in software engineering literature since the early
1980s. They were originally proposed in [Weiser 85], used as an approach to software maintenance
in [Gallagher 91], and most recently used to quantify functional cohesion in [Bieman 94]. Part of

Dept of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

this versatility is due to the natural, intuitively clear intent of the program slice concept.

➢ Informally, a program slice is a set of program statements that contribute to, or affect a value for
a variable at some point in the program. This notion of slice corresponds to other disciplines as
well. We might study history in terms of slices: US history, European history, Russian history, Far
East history, Roman history, and so on. The way such historical slices interact turns out to be very
analogous to the way program slices interact.
➢ We’ll start by growing our working definition of a program slice. We continue with the notation
we used for define-use paths: a program P that has a program graph G(P), and a set of program
variables V. The first try refines the definition in [Gallagher 91] to allow nodes in P(G) to
refer to statement fragments.

Definition
Given a program P, and a set V of variables in P, a slice on the variable set V at statement
n, written S(V,n), is the set of all statements in P that contribute to the values of variables in V.
Listing elements of a slice S(V,n) will be cumbersome, because the elements are program
statement fragments. Since it is much simpler to list fragment numbers in P(G), we make the
following trivial change (it keeps the set theory purists happy):

Definition
Given a program P, and a program graph G(P) in which statements and statement fragments
are numbered, and a set V of variables in P, the slice on the variable set V at statement fragment
n, written S(V,n), is the set node numbers of all statement fragments in P prior to n that
contribute to the values of variables in V at statement fragment n.

➢ The idea of slices is to separate a program into components that have some useful meaning. First,
we need to explain two parts of the definition. Here we mean “prior to” in the dynamic sense, so a
slice captures the execution time behavior of a program with respect to the variable(s) in the slice.
➢ Eventually, we will develop a lattice (a directed, acyclic graph) of slices, in which nodes are slices,
and edges correspond to the subset relationship.

Dept of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

➢ The “contribute” part is more complex. In a sense, declarative statements (such as CONST
and TYPE) have an effect on the value of a variable. One resolution might be to simply exclude
all non-executable statements.
➢ The notion of contribution is partially clarified by the predicate (P-use) and computation (C-use)
usage distinction of [Rapps 85], but we need to refine these forms of variable usage. Specifically,
the USE relationship pertains to five forms of usage:

P-use used in a predicate (decision)

C-use used in computation
O-use used for output
L-use used for location (pointers, subscripts)
I-use iteration (internal counters, loop indices)

While we’re at it, we identify two forms of definition nodes:

I-def defined by input

A-def defined by assignment
➢ For now, presume that the slice S(V, n) is a slice on one variable, that is, the set V consists of
a single variable, v. If statement fragment n is a defining node for v, then n is included in the
slice.
➢ If statement fragment n is a usage node for v, then n is not included in the slice. P-uses and C- uses
of other variables (not the v in the slice set V) are included to the extent that their execution
affects the value of the variable v.
➢ As a guideline, if the value of v is the same whether a statement fragment is included or excluded,
exclude the statement fragment. L-use and I-use variables are typically invisible outside
their modules, but this hardly precludes the problems such variables often create.
➢ Another judgment call: here (with some peril) we choose to exclude these from the intent
of “contribute”. Thus O-use, L-use, and I-use nodes are excluded from slices..

Dept of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Example
➢ The commission problem is used in this book because it contains interesting data flow properties,
and these are not present in the Triangle problem (or in NextDate). Follow these examples while
looking at the source code for the commission problem that we used to analyze in terms of
define-use paths.
➢ Slices on the locks variable show why it is potentially fault-prone. It has a P-use at node 14 and a
C-use at node 16, and has two definitions, the I-defs at nodes 13 and 19.

S1: S(locks, 13) = {13}

S2: S(locks, 14) = {13,14,19,20}
S3: S(locks, 16) = {13,14,19,20}
S4: S(locks, 19) = {19}
➢ The slices for stocks and barrels are boring. Both are short, definition-clear paths contained entirely
within a loop, so they are not affected by iterations of the loop. (Think of the loop body as a
DD-Path.)

S5: S(stocks, 15) = {13,14,15,19,20}

S6: S(stocks, 17) = {13,14,15,19,20}
S7: S(barrels, 15) = {13,14,15,19,20}
S8: S(barrels, 18) = {13,14,15,19,20}
➢ The next four slices illustrate how repetition appears in slices. Node 10 is an A-def for totallocks,
and node 16 contains both an A-def and a C-use. The remaining nodes in S10 (13,14,19 and 20)
pertain to the While-loop controlled by locks. Slices S10, S11, and S11 are equal because nodes
21 and 24 are, respectively, an O-use and a C-use of totallocks.
S9: S(totallocks, 10) = {10}
S10: S(totallocks, 16) = {10,13,14,16,19,20}
S11: S(totallocks, 21) = {10,13,14,16,19,20}
➢ The slices on num_stocks and num_barrels are quite similar. They are initialized by A-defs at
nodes 11 and 12, and then are redefined by A-defs at nodes 17 and 18. Again, the remaining nodes
(13,14,19 and 20) pertain to the While-loop controlled by locks.

Dept of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

S12: S(num_stocks, 11) = {11}

S13: S(num_stocks, 17) = {11,13,14,15,17,19,20}
S14: S(num_stocks, 22) = {11,13,14,15,17,19,20}
S15: S(num_stocks, 12) = {12}
S26: S(num_barrels, 18) = {12,13,14,15,17,19,20}
S17: S(num_barrels, 23) = {12,13,14,15,17,19,20}

➢ The next three slices demonstrate our convention regarding compiler-defined values.
S18: S(lockprice, 24) = {7}
S19: S(stockprice, 25) = {8}
S20: S(barrelprice, 26) = {9}
S21: S(locksales, 24) = {7,10,13,14,16,19,20,24}
S22: S(stocksales, 25) = {8,11,13,14,15,17,19,20,25}
S23: S(barrelsales, 26) = {9,12,13,14,15,18,19,20,26}

➢ The slices on sales and commission are the interesting ones. There is only one defining node
for sales, the A-def at node 27. The remaining slices on sales show the P-uses, C-uses, and the
O-use in definition-clear paths.

S24: S(sales, 27) = {7,8,9,10,11,12,13,14,15,16,17,18,19, 20, 24, 25, 26, 27}

S25: S(sales, 28) = {7,8,9,10,11,12,13,14,15,16,17,18,19, 20, 24, 25, 26, 27}
S26: S(sales, 29) = {7,8,9,10,11,12,13,14,15,16,17,18,19, 20, 24, 25, 26, 27}
S27: S(sales, 33) = {7,8,9,10,11,12,13,14,15,16,17,18,19, 20, 24, 25, 26, 27}
S28: S(sales, 34) = {7,8,9,10,11,12,13,14,15,16,17,18,19, 20, 24, 25, 26, 27}
S29: S(sales, 37) = {7,8,9,10,11,12,13,14,15,16,17,18,19, 20, 24, 25, 26, 27}
S30: S(sales, 39) = {7,8,9,10,11,12,13,14,15,16,17,18,19, 20, 24, 25, 26, 27}

➢ Think about slice S24 in terms of its “components”, the slices on the C-use variables. We can
write S24 = S10 S13 S16 S21 S22 S23, where the values of the six C-use variables

Dept of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

at node 36 are defined by the six slices joined together by the union operation. Notice how
the formalism corresponds to our intuition: if the value of sales is wrong, we first look at how
it is computed, and if this is OK, we check how the components are computed.
➢ Everything comes together (literally) with the slices on commission. There are six A-def nodes
for commission (corresponding to the six du-paths we identified earlier). Three computations of
commission are controlled by P-uses of sales in the IF, ELSE IF logic. This yields three “paths”
of slices that compute commission. (See Figure 3.4.)
S31: S(commission, 31) = {31}
S32: S(commission, 32) = {31, 32}
S33: S(commission, 33) = {7,8,9,10,11,12,13,14,15,16,17,18,19, 20, 24, 25, 26,
27,29,30,31,32,33}
S34: S(commission, 36) = {36}
S35: S(commission, 37) = {7,8,9,10,11,12,13,14,15,16,17,18,19, 20, 24, 25, 26,
27,36,37}
S36: S(commission, 39) = {7,8,9,10,11,12,13,14,15,16,17,18,19, 20, 24, 25, 26,
27,29,34,38,39}
Whichever computation is taken, all come together in the last slice.
S37: S(commission, 41) = {7,8,9,10,11,12,13,14,15,16,17,18,19, 20, 24, 25, 26,
27,29,30,31,32,33,34,35,36,37,38,39}
➢ The slice information improves our insight. Look at the lattice in Figure 3.4; it is a directed acyclic
graph in which slices are nodes, and an edge represents the proper subset relationship.

S31

S34
S32

S33 S35 S36

S37

Figure 3.4 Lattice of Slices on Commission

Dept of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

S31 S10 S13 S16 S21 S22 S23

S32 S24 S34

S33 S36 S35

S37

Figure 3.5 Lattice on Sales and Commission

➢ This lattice is drawn so that the position of the slice nodes roughly corresponds with their position
in the source code. The definition-clear paths <33, 41>, <37, 41>, and <39,41> correspond to the
edges that show slices S33, S35, and S36 are subsets of slice S37. Figure
3.5 shows a lattice of slices for the entire program. Some slices (those that are identical to others)
have been deleted for clarity.

10.2.2 Style and Technique

➢ When we analyze a program in terms of “interesting” slices, we can focus on parts of interest while
disregarding unrelated parts. We couldn’t do this with du-paths — they are sequences that include
statements and variables that may not be of interest.
➢ Before discussing some analytic techniques, we’ll first look at “good style”. We could have built
these stylistic precepts into the definitions, but then the definitions become even more
cumbersome.
1. Never make a slice S(V, n) for which variables v of V do not appear in statement
fragment n. This possibility is permitted by the definition of a slice, but it is bad practice.
As an example, suppose we defined a slice on the locks variable at node 27. Defining such
slices necessitates tracking the values of all variables at all points in the program.

Dept of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

2. Make slices on one variable. The set V in slice S(V,n) can contain several variables, and
sometimes such slices are useful. The slice S(V, 26) where

V= { locksSales, stocksSales, barrelsSales }

contains all the elements of the slice S({sales}, 36) except the CONST declarations and
statement 36. Since these two slices are so similar, why define the one in terms of C- uses?

3. Make slices for all A-def nodes. When a variable is computed by an assignment
statement, a slice on the variable at that statement will include (portions of) all du-paths of
the variables used in the computation. Slice S({sales}, 36) is a good example of an A-def
slice.

4. Make slices for P-use nodes. When a variable is used in a predicate, the slice on that
variable at the decision statement shows how the predicate variable got its value. This is
very useful in decision-intensive programs like the Triangle program and NextDate.

5. Slices on non-P-use usage nodes aren’t very interesting. We discussed C-use slices in
point 2, where we saw they were very redundant with the A-def slice. Slices on O- use
variables can always be expressed as unions of slices on all the A-defs (and I-defs) of the
O-use variable. Slices on I-use and O-use variables are useful during debugging, but if they
are mandated for all testing, the test effort is dramatically increased.

6. Consider making slices compilable. Nothing in the definition of a slice requires that the
set of statements is compilable, but if we make this choice, it means that a set of compiler
directive and declarative statements is a subset of every slice. If we added this same set of
statements to all the slices we made for the commission program, our lattices remain
undisturbed, but each slice is separately compilable (and therefore executable).

Dept of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

Guidelines and Observations

➢ Dataflow testing is clearly indicated for programs that are computationally intensive. As a
corollary, in control intensive programs, if control variables are computed (P-uses), dataflow
testing is also indicated.
➢ The definitions we made for define/use paths and slices give us very precise ways to describe parts
of a program that we would like to test. There are academic tools that support these definitions,
but they haven’t migrated to the commercial marketplace.
➢ Some pieces are there; you can find programming language compilers that provide on-screen
highlighting of slices, and most debugging tools let you “watch” certain variables as you step
through a program execution.
➢ Here are some tidbits that may prove helpful to you, particularly when you have a difficult module
to test.
1. Slices don’t map nicely into test cases (because the other, non-related code is still in an
executable path). On the other hand, they are a handy way to eliminate interaction among
variables. Use the slice composition approach to re-develop difficult sections of code, and
these slices before you splice (compose) them with other slices.

2. Relative complements of slices yield a “diagnostic” capability. The relative

complement of a set B with respect to another set A is the set of all elements of A that are
not elements of B. It is denoted as A -B. Consider the relative complement set
S(commission, 41) - S(sales, 27):

S(commission,41) = {7,8,9,10,11,12,13,14,15,16,17,18,19, 20, 24, 25, 26,

27,29,30,31,32,33,34,35,36,37,38,39}
S(sales, 27) = {7,8,9,10,11,12,13,14,15,16,17,18,19, 20, 24, 25, 26, 27}
S(commission, 41) - S(sales, 27) = {29,30,31,32,33,34,35,36,37, 38, 39}

If there is a problem with commission at line 48, we can divide the program into two parts,
the computation of sales at line 34, and the computation of commission between lines 35
and 48. If sales is OK at line 34, the problem must lie in the relative complement; if not,
the problem may be in either portion.

Dept of CS, BCA, MIT FGC

 SOFTWARE TESTING-ARVIND G

3. There is a many-to-many relationship between slices and DD-Paths: statements in one

slice may be in several DD-Paths, and statements in one DD-Path may be in several slices.
Well-chosen relative complements of slices can be identical to DD-Paths. For example,
consider S(commission, 40) -S(commission, 37).

4. If you develop a lattice of slices, it’s convenient to postulate a slice on the very first
statement. This way, the lattice of slices always terminates in one root node. Show equal
slices with a two-way arrow.

5. Slices exhibit define/reference information. Consider the following slices on totallocks:

S9: S(totallocks, 10) = {10}
S(totallocks, 16) = {10,13,14,16,19, 20}
S(totallocks, 21) = {10,13,14,16,19, 20}
When slices are equal, the corresponding paths are definition-clear.

Dept of CS, BCA, MIT FGC