Logic-based testing, logic-based coverage criteria

Logic Coverage

Types of logic coverage:

• With equivalence partitioning, we make certain we adequately cover the domain of input/output values
• With Whitebox coverages (statement- & branch-coverages) we make sure we reach all different parts and branches of the code
• With logic coverage, we focus on the combinations of truth assignments of the logical expressions in loops and conditionals

Terminology:

• Predicate: an expression that evaluates to either true or false. Predicates contain Boolean variables, relational operators (e.g., <,>, !=, ==, etc.), Boolean function calls, logical operators (e.g., logical AND, logical OR etc.) or Boolean values (i.e., true and false)
• Clause: a predicate with no logical operators
• Logical Operators
  • $\neg$ the negation operator
  • $\land$ the and operator
  • $\lor$ the or operator
  • $\rightarrow$ – the implication operator
  • $\oplus$ the exclusive or operator
  • $\leftrightarrow$ the equivalence operator

Logic Expressions

Logic Expressions may be derived from variety of artifacts:

• source code (e.g., if ((x>10 && y < -22)))
• specifications (e.g,. "to be able to push a new item onto stack, the stack should not be full and stack object not null")
• fsm: "state = card_inserted and action = PIN_ok $\rightarrow$ state = show_accounts"
• SQL queries: "SELECT AVG(Salary), Emp_Age FROM Employee WHERE Salary > 100,000 and Emp_Age < 35"
• etc.

They look like (a < b) $\lor$ f(z) $\land$ D $\land$ TRUE

• (a < b) is relational Boolean expression
• f(z) is boolean function call (f is a function and returns true or false)
• D is a boolean variable
• TRUE is a boolean value

The predicate is “(a < b) $\lor$ f(z) $\land$ D $\land$ TRUE” The four clauses are "(a < b)", "f(z)", "D", "TRUE".

Human language can be vaue sometimes. For example, saying "I am interested in 633 and 683" it means course can be 663 OR 682.

• this is important to note when applying logic coverage on informal specifications, user manulas, API docs, etc.

Criteria

Assume P is the set of all predicates and C is the set of all clauses in p.

• predicate coverage (PC): for each $p \in P$, $TR$ contains two requirements: $p$ evalues to true, and $p$ evalues to false.
• clause coverage (CC): for each $c \in C$, $TR$ contains two requirements: $c$ evalues to true, and $c$ evaluates to false.

Example: (x>y) $\lor$ f(z) $\land$ w

• (x>y) is C1, f(z) is C2, w is C3
• predicate coverage:
  • x=10, y=9, f(z)=true, w=true (this predicate evaluates to true)
  • x=5, y=5, f(z)=false, w=true (this predicate evaluates to false)
• clause coverage:
  • x=10, y=9, f(z)=true, w=true (C1=true, C2=true, C3=true)
  • x=5, y=5, f(z)=false, w=false (C1=false, C2=false, C3=false)

PC does nto full exercise all the clauses, especially in the presence of a short circuit evaluation.

• short circuit: not all clauses may be evaluated because when the earlier expressions are true, the rest are ignored

CC does not subsume PC, i.e., we may satisfy CC without causing hte predicate to be both true and false

The most comprehensive solution is to try all possible combinations of the clauses.

Assume P is the set of all predicates and C is the set of all clauses in P: Combinatorial Coverage (CoC) : For each p $\in$ P, TR has test requirements for the clauses in $C_p$ to evaluate to each possible combination of truth values.

• for a predicate with $n$ clauses, there are $2^n$ possible truth sassignments.
• Not scalable, maybe even impractical if the number of clauses is very large.

We need a way to capture the effect of each and every clause while not exhausting all combinations. This can be done through active clause.

• In (a $\lor$ b) $\land$ c, a is "active" if b is false and c is true, and c is active if (a $\lor$ b is true)
• Determination: a clause $C_i$ in predicate p, called the major clause, determines p if and only if the values of the remaining minor clauses $C_j$, (j!= i) are such that changing $C_i$ changes the value of p.
• Our goal is to find for each clause when the clause determines the value of the predicate.
• An important note about determination: the definition does not require $c_i = p$ ($c-i$ can be negation of p). E.g., $a \leftrightarrow b$: a is active is b is false. a= false, b=false $\rightarrow P$=true.

Active clause coverage (ACC): For each $p \in P$ and each major clause $c_i$ in $C_p$ , choose minor clauses $c_j,j$ != $i$, so that $C_i$ determines p. TR has two requirements for each $c_i$ : $c_i$ evaluates to true and $ci$ evaluates to false.

• this identifies and reduces duplicates.

General Active Clause Coverage (GACC) : For each p in P and each major clause $c_i$ in $C_p$, choose minor clauses $c_j,j$ != $i$, so that $c_i$ determines p. TR has two requirements for each $c_i$ : $c_i$ evaluates to true and $c_i$ evaluates to false. The values chosen for the minor clauses $c_j$ do not need to be the same when $c_i$ is true as when $c_i$ is false.

• It is possible to satisfy GACC without satisfying predicate coverage
• GACC does not subsume predicate coverage (PC)
• We really want to cause predicates to be both true and false!

Correlated Active Clause Coverage (CACC) : For each p in P and each major clause $c_i$ in $C_p$, choose minor clauses $c_j,j$ != $i$, so that $c_i$ determines p. TR has two requirements for each $c_i$ : $c_i$ evaluates to true and $c_i$ evaluates to false. The values chosen for the minor clauses $c_j$ must cause $p(c_i = true) != p(c_i = false)$

Logic criteria subsumption. COC subsumes CAC which subsumes GACC and PC, and GACC subsumes CC.