Skip to main content

Def-Use

Topic appears in the following WE1 Exams:

  • 2021 07 26 Q3 (3 points)
  • 2021 01 13 Q2.1Q2 (3 points) Mixed def-use and symbolic execution

Therefore it appears in 33% of the WE1 exams and it is worth 3 points on average.

Summary

Identify every time a variable is defined (modified) and used with that version, for example:

1 int i, k = 0;
2 i = k;
3 while (i<10)
4 i++;

The def-use pairs for k are <1, 2> while the ones for i are <2, 3>, <2, 4>, <4, 3>, <4, 4>.

A more complex example:

0  int foo() {
1    x = input();
2    while (x > 0) {
3        y = 2 * x;
4      if (x > 10)
5        y = x - 1;
6      else
7        x = x + 2;
8      x = x - 1;
9    }
10   x = x - 1;
11   return x;
12 }

A control flow graph could be useful:

The identified def-use pairs for x are:

  • <1, 2> <1, 3> <1, 4> <1, 5> <1, 7> <1, 8> <1, 10>
  • <7,8>
  • <8, 2> <8, 3> <8, 4> <8, 5> <8, 7> <8, 8> <8, 10>
  • <10, 11>

While we see for y:

  • <3,?> <5, ?>

So y is defined but never used.

Past exam exercise

2021 07 26 Q3 (3 points)

Identify the def-use pairs for program my_func and say whether they highlight anything unusual.

0  int my_func (int x, int y) {
1      int z, k, res;
2      if (x <= 0 || y <= 0)
3          return -1;
4      z = x;
5      k = y;
6      while (x != y) {
7          if (x > y)
8              x = x - y;
9          else y = y - x; }
10     if (z % x == 0) {
11         res = 1;
12         z = 1; }
13     else z = 0;
14 	   return res; }
Variable Def-Use pairs
x <0,2>, <0,4>, <0,6>, <0,7>, <0,8>, <0,9>, <0,10>
<8,6>, <8,7>,<8,8>, <8,9>, <8,10>
y <0,2>, <0,5>, <0,6>, <0,7>, <0,8>, <0,9>
<9,6>, <9,7>,<9,8>, <9,9>
z <4, 10>, <12,?>, <13,?>
k <5, ?>
res <?,14>, <11,14>

Variable z is set at lines 12 and 13, but it is then never used, which is not necessarily a problem, though it is not ideal. Similarly, variable k is set at line 5, but it is never used. Variable res is potentially used at line 14 without being initialized. However, an inspection of the paths that lead to line 14 show that line 13 is actually never executed (i.e., the condition at line 10 is always true), so variable res will actually be always initialized when it is used.

2021 01 13 Q2.1Q2 (3 points) Mixed def-use and symbolic execution

0  int func (int) {
1      int k, i, y;
2      int res = 0;
3      if (x < 1)
4          return res;
5      if (x % 2 != 0)
6          return res;
7      y = x;
8      i = 0;
9      while (i <= 10 && y % 4 != 0)
10         y = y*y;
11         i = i + 1;
12     }
13     if (i > 55)
14 	       res = k;
15     else
16         res = res + 1;
17     return res;

Point A: identify pairs and highlight unusual

Identify the def-use pairs for program func and say whether they highlight anything unusual.

VariableDef-Use pairs
x<0,3>, <0,5>, <0,7>
k<?,14>
i<8,9>, <8,11>, <8,13>
<11, 9>, <11, 11>, <11, 13>
y<7, 9>, <7, 10>
<10, 9>, <10,10>
res<2,4>, <2,6>, <2,16>, <14,17>, <16,17>

Variable k is used in line 14 but it is never initialized.

Point B: symbolic execution

Use symbolic execution to determine the feasibility (and, in case, the path condition) of the following path: 0, 1, 2, 3, 5, 7, 8, 9, 10, 11, 12, 9, 10, 11, 12, 9, 13, 15, 16, 17

StepDefinitionsPath Conditions
0x=X
1
2res=0
3
5X=2KX >= 1
7y=XX >= 1
8i=0
9
10X >= 1, X not divisible by 4 (not exists P s.t. 2K = 4P)
11y=X^2=4K^2
12i = 1
9
10X >= 1, X not divisible by 4, X^2 not divisible by 4 (not exists P s.t. 4*K*K = 4P)

The last condition is not feasible, since it is enough to consider K*K = P to violate the condition. The path is not feasible.

Point C: mix def-use and symbolic execution

For any possibly erroneous situation highlighted by the def-use analysis, use symbolic execution to argue whether or not the problem can indeed manifest itself.

We saw that variable k is used in line 14 but it is never initialized. This situation is impossible to occur since the loop can get executed at most 1 time and for this reason i<=5 so the path is not taken.

Back to top