We defined the terms White Box and Black Box testing in Lecture #3. We will now discuss techniques for these testing strategies. We start with a widely known White Box technique known as Basis Path testing.

On page 178 of Chapter 9, the authors introduce the term Cyclomatic Complexity (or Cyclomatic Number). The Basis Path testing technique is based on this notion. The technique therefore requires that the module/program being tested must first be expressed as a directed graph. These directed graphs are often referred to as Program Graphs. The Cyclomatic Complexity/Number may then be determined and indicates the number of independent pathways through the program. These pathways may then be used to derive the minimum set of test cases to ensure statement coverage (but only weak decision coverage).

Following is some basic terminology followed by an outline of the technique.

Terminology:

1. Program Graph: A directed graph that depicts the flow of control in a program. Nodes represent program segments and edges are connectors from given segments to other program segments.
2. Node: A node represents a sequence of statements or a decision. A decision will have multiple emanating edges for each possible change in flow of control due to the decision. Each program graph begins with an entry node and ends with an exit node.
3. Edge: An edge depicts a transfer of control from one node to another.
4. Path: A path is a route through a graph that traverses edges from node to node beginning with the entry node and ending with the exit node.
5. Region: A region is an area within a graph that is completely bounded by nodes and edges.

• Looping constructs are depicted by a node with an emanating edge that returns to the node. These are constructs that are controlled by decisions, hence the representation.
• Predicates of selection structures should be basic clauses. That is, predicates containing conjuncts should be reexpressed as nested selection structures.

Cyclomatic Complexity/Number:

On page 179 the authors present three different expressions that may be used to compute Cyclomatic Number. We will use the following:

where E represents the number of edges of the program graph and N represents the number of nodes.

Basis Path Testing:

Recall, that the idea of the technique, is to determine a minimum set of test cases that will ensure statement coverage and possibly also decision coverage. Remember that weak decision coverage may be obtained if selection structures are restructured as basic clauses. That is, predicates consisting of conjunctions (i.e. AND) may be restructured as nested selection structures.

For a given program, the technique may be described thus:

1. Derive the program graph for the program.
2. Compute the Cyclomatic Number.
3. Identify the independent paths. The number of independent paths is equal to the Cyclomatic Number.
   1. Identify all nodes and assign unique numbers to each node.
      Note: We usually assign numbers sequentially starting with 1.
   2. Starting with the entry node, traverse the graph to the exit node listing nodes crossed and checking off traversed edges.
   3. Repeat the previous step until no unchecked edge remains.
4. Identify the miniumum test set.
   1. For each independent path, create a test case that will execute the path.
   2. The resulting set of test cases is the minimum test set.

Example:

Consider the following pseudocode that iterates through a list identifying numeric and non-numeric characters and then prints a count of the items in the list:
Note: Numbers at the left correspond to nodes in the program graph.

1    count=0
1    get first item in list.
2    do while not end of list
3       count=count + 1
4       if item numeric
5           print 'NUMERIC', item
        else
6           print 'NON-NUMERIC', item
7       endif
8       get next item in list.
9    enddo
10   print count

1. Nodes: 1, 2, 9, 10
2. Nodes: 1, 2, 3, 4, 5, 7, 8, 2, 9, 10
3. Nodes: 1, 2, 3, 4, 6, 7, 8, 2, 9, 10

Therefore, the corresponding minimum test set should ensure that the following three situations are addressed:

1. Empty list
2. Non-Empty list, a numeric items
3. Non-Empty list, a non numeric items

In Class Exercise:

Consider the following pseudocode that determines the total price for an item purchased from an electronic retailer.
Note: Numbers at the left correspond to nodes in the program graph.

1    rushCharge = 0 
1    if nextday = 'Y' 
2       rushCharge = 14.50
3    endif
3    tax = amount * 0.08 
3    if amount >= 1000 
4       shipcharge = amount * .06 + rushCharge 
5    else if amount >= 200 
6       shipcharge = amount * .08 + rushCharge
7    else if amount >= 100 
8       shipcharge = 10 + rushCharge 
9    else if amount >= 50 
10      shipcharge = 9 + rushCharge 
11   else if amount >= 25 
12      shipcharge = 7 + rushCharge 
     else 
13      shipcharge = 5 + rushCharge 
14   endif
14   total = amount + tax + shipcharge

Since the program graph contains 14 nodes and 19 edges then the cyclomatic number for the graph is:

1. Nodes: 1, 2, 3, 5, 7, 9, 11, 13, 14
2. Nodes: 1, 3, 4, 14
3. Nodes: 1, 3, 5, 6, 14
4. Nodes: 1, 3, 5, 7, 8, 14
5. Nodes: 1, 3, 5, 7, 9, 10, 14
6. Nodes: 1, 3, 5, 7, 9, 11, 12, 14
7. Nodes: 1, 3, 5, 7, 9, 11, 13, 14

Therefore, the corresponding minimum test set should ensure that the following seven situations are addressed:

1. Nextday='Y', Amount<25
2. Nextday='N', Amount>=1000
3. Nextday='N', 1000>Amount>=200
4. Nextday='N', 200>Amount>=100
5. Nextday='N', 100>Amount>=50
6. Nextday='N', 50>Amount>=25
7. Nextday='N', Amount<25