Definition-use graph example

Example 1

DUG - Example 1.svg


Example 2

In order to exemplify the data flow testing criteria, consider the definition-use graph of the source code below:

<source lang="java" line> public boolean validateIdentifier(String s) { char achar; /∗ 1 ∗/ boolean valid_id = false; /∗ 1 ∗/ if (s.length() > 0) { /∗ 2 ∗/ achar = s.charAt(0); /∗ 2 ∗/ validId = validS(achar); /∗ 2 ∗/ if (s.length() > 1) { /∗ 3 ∗/ achar = s.charAt(1); /∗ 3 ∗/ int i = 1; /∗ 4 ∗/ while (i < s.length() − 1) { /∗ 5 ∗/ achar = s.charAt(i); /∗ 5 ∗/ if (! validF(achar)) /∗ 6 ∗/ valid_id = false ; /∗ 7 ∗/ i++; } } } /∗ 8, 9, 10 ∗/ if (valid_id && (s.length() >= 1) && (s.length() < 6)) /∗ 11 ∗/ return true; else /∗ 12 ∗/ return false ; } </source>

There are three different kinds of information annotated on the definition-use graph:

Observe that at node 1 there are three variable definitions related to the variables s and valid_id, since at lines 4 and 6 respectively there are statements causing such definitions. At nodes 2 and 5 there are variable computational uses of the variables achar (line 9), s, and i (line 14). Finally, we have variable predicative uses of variables assigned to the outgoing edges of decision nodes. For instance, node 4 is a decision node and has the variable predicative use of variables i and s, which means that such variables decide which edge is going to be taken – (4, 5) or (4, 8) – due to the conditional statement at line 13.

As an example of a data flow association for a computational variable use, consider the variable s defined at node 1. There is computational variable use of such a variable at node 3 represented by the association [s, 1, 3]. Similarly, [valid_id, 1, (8, 9,)] and [valid_id, 1, (8, 12,)] correspond to the data flow association for a predicative variable use of the variable valid_id defined at node 1 and its predicative variable uses on edges (8, 9) and (8, 12). The path (1,8,12) is a definition clear path with respect to valid_id defined at node 1 which covers the data flow association [valid_id, 1, (8, 12,)].

On the other hand, the path (1,2,8,12) is not a definition clear path with respect to valid_id defined at node 1 since there is a redefinition of valid_id at node 2, and, in this way, when reaching the variable predicative use of valid_id at edge (8, 12), such a use does not correspond to the value of valid_id defined at node 1 but to the one defined at node 2. In order to cover the data flow association with respect to the definition of valid_id at node 1, we have to find a test case that follows any complete path not passing through node 2.

In order to exercise the definition of variable valid_id defined at node 6, according to the All-Defs criterion, the following paths can be executed: (6,7,4,8,12) or (6,7,4,8,9). However, one must have in mind that the path (6,7,4,8,91) is infeasible, as are all complete paths which include it. Therefore, considering this example, there is only one possible executable path to satisfy the testing requirement passing through (6,7,4,8,12), and the test case (1#@, Invalid), for instance, follows such a path. In order to satisfy the All-Defs criterion, this analysis has to be done for each variable definition in the product under testing.

As regards the All-Uses criterion, with respect to the same definition, the following associations are required: [valid_id, 6, (8, 9)] and [valid_id, 6, (8, 12)]. As previously discussed, the association [valid_id, 6, (8, 9)] is infeasible and can be dropped off, while the other can be covered by the same test case. This analysis has to be carried out for all other variable definitions and their corresponding def-use associations in order to satisfy the All-Uses criterion.

DefinitionUseGraph-Identifier-validateIdentifier.png