Dataflow Testing

Dataflow Testing

• Testing All-Nodes and All-Edges in a control flow graph may miss significant test cases
• Testing All-Paths in a control flow graph is often too time-consuming
• Can we select a subset of these paths that will reveal the most faults?
• Dataflow Testing focuses on the points at which variables receive values and the points at which these values are used
  • Goal: try to ensure that values are computed and used correctly

Dataflow Analysis

• Dataflow analysis can reveal interesting bugs
  • A variable that is defined but never used
  • A variable that is used but never defined
  • A variable that is defined twice before it is used
  • Sending a modifier message to an object more than once between accesses
  • De-allocating a variable before it is used - Container problem
  • De-allocating container loses references to items in the container, memory leak

Definitions

• A node n in the program graph is a defining node for variable v, written as DEF(v, n), if the value of v is defined at the statement fragment in that node
  • Input, assignment, procedure calls
• A node in the program graph is a usage node for variable v, written as USE(v, n), if the value of v is used at the statement fragment in that node
  • Output, assignment, conditionals
• A usage node is a predicate use, P-use, if variable v appears in a predicate expression - Always in nodes with outdegree ≥ 2
• A usage node is a computation use, C-use, if variable v appears in a computation
  • Always in nodes with outdegree ≤ 1
• A node in the program is a kill node for a variable v, written as KILL(v, n), if the variable is deallocated at the statement fragment in that node

Example 2 - Billing program

public int calculateBill (int usage) { 
  double bill = 0;
  if (usage > 0) { 
    bill = 40; 
  } 
  if (usage > 100) {
    if (usage <= 200) { 
      bill = bill + (usage     - 100) *0.5; 
    } else { 
      bill = bill + 50 + (usage     - 200) * 0.1; 
    }
    if (bill >= 100) { 
      bill = bill * 0.9; 
    } 
  }
  return bill; 
}
Kill node for bill

Definition-Use path

• What is a du-path (definition-use path)?
  • A definition-use path, du-path, with respect to a variable v is a path whose first node is a defining node for v, and its last node is a usage node for v
• What is a dc-path (definition-clear path)?
  • A du-path with no other defining node for v is a definition-clear path

Dataflow Coverage Metrics

• Based on these definitions we can define a set of coverage metrics for a set of test cases
• We have already seen - All-Nodes
  • All-Edges - All-Paths
• Dataflow has additional test metrics for a set T of paths in a program graph
  • All assume that all paths in T are feasible

All-Defs Criterion

• The set T satisfies the All-Def criterion iff
  • For every variable v in V, T contains a dc-path from every defining node for v to at least one usage node for v
    • Notallusenodesneedtobereached
    • T is the set of paths in the program graph
    • V is the set of variables

All-Uses Criterion

• The set T satisfies the All-Uses criterion iff
  • For every variable v in V, T contains dc-paths that start at every defining node for v, and terminate at every usage node for v
    • T is the set of paths in the program graph
    • V is the set of variables
• We cannot take the cross product of DEF and USE to define du-paths:
  • DEF(v, n)  USE(v, n)
  • Because it can result in infeasible paths

All-P-uses / Some-C-uses Criterion

• The set T satisfies the All-P-uses/Some-C-uses criterion iff
  • For every variable v in V for the program P, T contains a dc-path from every defining node of v to every P-use node for v
  • If a definition of v has no P-uses, a dc-path leads to at least one C-use node for v
    • T is the set of paths in the program graph
    • V is the set of variables

All-C-uses / Some-P-uses

• The test set T satisfies the All-C- uses/Some-P-uses criterion iff
  • For every variable v in V for the program P, T contains a dc-path from every defining node of v to every C-use of v
  • If a definition of v has no C-uses, a dc-path leads to at least one P-use
    • T is the set of paths in the program graph
    • V is the set of variables

Data flow guidelines

• When is dataflow analysis good to use?
  • Data flow testing is good for computationally/control intensive programs
    • If P-use of variables are computed, then P-use data flow testing is good
  • Define/use testing provides a rigorous, systematic way to examine points at which faults may occur.
• Aliasing of variables causes serious problems!
• Working things out by hand for anything but small methods is hopeless
• Compiler-based tools help in determining coverage values