BS7925-2 Annex B - Guidelines for Testing and Test Measurement

Guidelines for Testing Techniques and Test Measurement

B.7    Branch/Decision Testing

Branch and Decision Coverage are closely related.  For components with one entry point 100% Branch Coverage is equivalent to 100% Decision Coverage, although lower levels of coverage may not be the same.  Both levels of coverage will be illustrated with one example:

The component shall determine the position of a word in a table of words ordered alphabetically.  Apart from the word and table, the component shall also be passed the number of words in the table to be searched.  The component shall return the position of the word in the table (starting at zero) if it is found, otherwise it shall return "-1".

The corresponding code is drawn from [K&R].  The three decisions have been highlighted.

            int binsearch (char *word, struct key tab[], int n) {
                        int cond;
                        int low, high, mid;
                        low = 0;
                        high = n - 1;
                        while (low <= high) {
                                    mid = (low+high) / 2;
                                    if ((cond = strcmp(word, tab[mid].word)) < 0)
                                                high = mid - 1;
                                    else if (cond > 0)
                                                low = mid + 1;
                                    else
                                                return mid;
                        }
                        return -1;
            }

 

In this example each decision has two outcomes corresponding to the true and false values of the conditions.  It is generally possible for a decision to have more than two outcomes.

Branch coverage may be demonstrated through coverage of the control flow graph of the program.  The first step to constructing a control flow graph for a procedure is to divide it into basic blocks.  These are sequences of instructions with no branches into the block (except to the beginning) and no branches out of the block (except at the end).  The statements in a basic block are guaranteed to be executed together or not at all.  The program above has the following basic blocks.

            int binsearch (char *word, struct key tab[], int n) {
                        int cond;
                        int low, high, mid;

B1                    low = 0;
                        high = n - 1;      
B2                    while (low <= high) {                                                                                       
B3                                mid = (low+high) / 2                                                                           
                                    if ((cond = strcmp(word, tab[mid].word)) < 0)                                         
B4                                            high = mid - 1;                                                                       
B5                                else if (cond > 0)                                                                                
B6                                            low = mid + 1;                                                                       
B7                                else                                                                                                  
                                                return mid;                                                                             
B8                    }                                                                                                                   
B9                    return -1;          
            }

 

A control flow graph may be constructed by making each basic block a node and drawing an arc for each possible transfer of control from one basic block to another.  These are the possible transfers of control:

B1 -> B2 B2 -> B3 B2 -> B9

B3 -> B4 B3 -> B5 B4 -> B8

B5 -> B6 B5 -> B7

B6 -> B8 B8 -> B2

 

This results in the graph presented in figure B.7.  The graph has one entry point, B1, and two exit points, B7 and B9.

Figure B.7: Control flow graph for binsearch

Of course, the above control flow graph would not necessarily be constructed by hand, but a tool would normally be used to show which decisions/branches have been executed.

The decisions are given by the basic blocks having more than one exit arrow, namely B2, B3 and B5.  Since each of these three blocks have two exits, we have six decisions to consider.

The branches are given by the arrows in the control flow graph; 10 in total.

For both branches and decisions any individual test of the component will exercise a path and hence potentially many decisions and branches.

Consider a test case which executes the path B1 -> B2 -> B9.  This case arises when n=0, that is, when the table being searched has no entries.  This path executes one decision (B2 -> B9) and hence provides 1/6 = 16.7% coverage.  The path executes 2 out of the 10 branches, giving 20% coverage (which is not the same as the coverage for decisions).

Consider now a test case which executes the path:

B1->B2->B3->B4->B8->B2->B3->B5->B6->B8->B2->B3->B5->B7

This path arises when the search first observes that the entry is in the first half of the table, then the second half of that (i.e., 2nd quarter) and then finds the entry.  Note that the two test cases provide 100% decision and branch coverage.

These test cases are shown below:

test	inputs			decisions exercised	expected
case	word	tab	n	(underlined)	outcome
1	chas	'empty table'	0	B1  »  B2 »  B9	-1
2	chas	alf bert chas dick eddy fred geoff	7	B1  »  B2  »  B3  »  B4   »  B8  »  B2  »  B3  »  B5  »  B6  »  B8  »  B2  »  B3  »  B5  »  B7	2

 

Branch and decision coverage are both normally measured using a software tool.