Turn Desktop View Off
by Dinesh Thakur

Structural testing on the other hand is concerned with testing the implementation of the program. The intent of structural testing is not to exercise all the different input or output conditions but to exercise the different programming structures and data structures used in the program.

To test the structure of a program, structural testing aims to achieve test cases that will force the desired coverage of different structures. Various criteria have been proposed for this. Unlike the criteria for functional testing, which are frequently imprecise, the criteria for structural testing are generally quite precise as they are based on program structure formal and precise.

Control Flow Based Criteria

Most common structure based criteria are based on the control flow of the program. In these criteria the control flow graph of a program is considered and coverage of various aspects of the graph are specified as criteria. Hence before we consider the criteria let us precisely define a control flow graph for a program.

Let the control flow graph (or simply flow graph) of a program P be G. A node in this graph represents a block of statements that is always executed together i.e., whenever the first statement is executed all other statements are also executed an edge 9.i.j (from node i to node j) represents a possible transfer of control after executing the last statement of the block represented by node i to the first statement of the block represented by node j.

A node corresponding to a block whose first statement is the start statement of P is called the start node of G and a node corresponding to a block whose last statement is an exit statement is called an exit node. A path is a finite sequence of nodes (n1,n2,.......kk) k>1, node nk) .A complete path is  a path whose first node is the start node and the last node is an exit node.

The simplest coverage criterion is statement coverage, which requires that each statement of the program be executed at least once during testing. In other words it requires that the paths executed during testing include all the nodes in the graph. This is also called the all nodes criterion. This coverage criterion is not very strong and can leave errors undetected.

For example, if there is an if statement in the program without having an else clause the statement coverage criterion for this statement will be satisfied by a test case that evaluates the condition to true. No test case is needed that ensures that the condition in the if statement evaluates to false. This is a serious shortcoming because decisions in programs are potential sources of errors. As an example consider the following function to compute the absolute value of a number.


int abs (x)

int x;


if (x>=0) x=0 -x;

return (x)



A little more general coverage criterion is branch coverage, which requires that each edge in the control flow graph be traversed at least once during testing. In other words branch coverage requires that each decision in the program be evaluated to true and false values at least once during testing. Testing based on branch coverage is often called branch testing.

The Trouble with branch coverage comes if a decision has many conditions in it .For example; consider the following function that checks the validity of a data item. The data item is valid if it lies between 0 and 100 as it is checking for x <200 instead of 100 (perhaps a typing error made by the programmer).

Data  Flow -Based Testing

The basic idea behind data flow based testing is to make sure that during testing the definitions of variables and their subsequent use is tested. Just like the all nodes and all edges criteria try to generate confidence in testing by making sure that at least all statements and all branches have been tested the data flow testing tries to ensure some coverage of the definitions of variables. 

For data flow based criteria a definition use graph (de flues graph for short) for the program is first constructed from the control flow graph representing a block of code has variable occurrences in it. A variable occurrence can be one of the following three types (RW 85)

Ø     Def represents the definition of a variable. The variable on the left hand side of an assignment is the one getting defined.

Ø    C-use represents computational use of a variable. Any statement (e.g. read write an assignment) that uses the value of variables for computation purposes is said to be making c- use of the variables. In an assignment statement all variables on the right hand side have a c- use occurrence. In a read and a write statement all variable occurrences are of this type.

Ø    P- use represents predicate use. These are all the occurrences of the variables in a predicate (i.e. variables whose values are used for computing the value of the predicate), which is used for transfer of control.

In control flow based and data flow based testing the focus was on which paths to execute during testing. Mutation testing does not take a path-based approach. Instead it takes the program and creates many mutants of it by making simple changes to the program. The goal of testing is to make sure that during the course of testing each mutant produces an output different from the output of the original program.

In other words the mutation testing criterion does not say that the set of test cases must be such that certain paths are executed instead it requires the set of test cases to be such that they can distinguish between the original program and its mutants.