Definition-use graph

De Software testing
Ir para: navegação, pesquisa

Concepts


Facts

  • The definition-use graph is called of DUG. <bib>vincenzi-etal:slides:2007</bib>, <bib>vincenzi-maldonado:slides:2007</bib>
  • The definition-use graph can be static or dynamically analyzed: statically to examine the diagram (formally through inspections or informally through look-sees); dynamically to construct and execute test cases. <bib>vincenzi-maldonado:slides:2007</bib>


Procedures

  • Definition-use graph construction <bib>mathur:2008, 458</bib>
    1. Consider a control-flow graph G = (N, E) of a program P, where N is the set of nodes and E the set of edges. Each node in G corresponds to a code block in P: those blocks are denoted as <math>b_{1}, b_{2}, ..., b_{k}</math>, assuming that P contains k > 0 code blocks.
    2. Let <math>def_{i}</math> denote the set of variables defined in code block i.
    3. Let <math>c-use_{i}</math> denote the set of variables that have a computational use in code block i.
    4. Let <math>p-use_{i}</math> denote the set of variables that have a predicative use in code block i.
    5. Compute <math>def_{i}</math>, <math>c-use_{i}</math>, and <math>p-use_{i}</math> for each code block i in P.
    6. Associate each node i in N with <math>def_{i}</math>, <math>c-use_{i}</math>, and <math>p-use_{i}</math>.
    7. For each node i that as a nonempty predicative use sets and ends in condition C, associate edges (i, j) and (i, k) with C and !C, respectively, given that edge (i, j) is taken when the condition is true and (i, k) is taken when the condition is false.