1 Software Testing and Maintenance 1 Predicate Testing  Introduction  Basic Concepts  Predicate Coverage  Program-Based Predicate Testing  Summary Software Testing and Maintenance 2 Motivation  Predicates are expressions that can be evaluated to a boolean value, i.e., true or false.  Many decision points can be encoded as a predicate, i.e., which action should be taken under what condition?  Predicate-based testing is about ensuring those predicates are implemented correctly.2 Software Testing and Maintenance 3 Applications  Program-based: Predicates can be identified from the branching points of the source code  e.g.: if ((a > b) || c) { … } else { … }  Specification-based: Predicates can be identified from both formal and informal requirements as well as behavioral models such as FSM  “if the printer is ON and has paper then send the document for printing”  Predicate testing is required by US FAA for safety critical avionics software in commercial aircraft Software Testing and Maintenance 4 Predicate Testing  Introduction  Basic Concepts  Predicate Coverage  Program-Based Predicate Testing  Summary3 Software Testing and Maintenance 5 Predicate  A predicate is an expression that evaluates to a Boolean value  Predicates may contain:  Boolean variables  Non-boolean variables that are compared with the relational operators {>, <, =, ≥, ≤, ≠}  Boolean function calls  The internal structure is created by logical operators:  ¬, ∧, ∨, →, ⊕, ↔ Software Testing and Maintenance 6 Clause  A clause is a predicate that does not contain any of the logical operators  Example: (a = b) ∨ C ∧ p(x) has three clauses: a relational expression (a = b), a boolean variable C, and a boolean function call p(x)4 Software Testing and Maintenance 7 Predicate Faults  An incorrect boolean operator is used  An incorrect boolean variable is used  Missing or extra boolean variables  An incorrect relational operator is used  Parentheses are used incorrectly Software Testing and Maintenance 8 Example  Assume that (a < b) ∨ (c > d) ∧ e is a correct boolean expression:  (a < b) ∧ (c > d) ∧ e  (a < b) ∨ (c > d) ∧ f  (a < b) ∨ (c > d)  (a = b) ∨ (c > d) ∧ e  (a = b) ∨ (c ≤ d) ∧ e  (a < b ∨ c > d) ∧ e5 Software Testing and Maintenance 9 Predicate Testing  Introduction  Basic Concepts  Predicate Coverage  Program-Based Predicate Testing  Summary Software Testing and Maintenance 10 Predicate Coverage  For each predicate p, TR contains two requirements: p evaluates to true, and p evaluates to false.  Example: ((a > b) ∨ C) ∧ p(x)) a b C p(x) 1 5 4 true true 2 5 6 false false6 Software Testing and Maintenance 11 Clause Coverage  For each clause c, TR contains two requirements: c evaluates to true, and c evaluates to false.  Example: ((a > b) ∨ C) ∧ p(x)) a b C p(x) 1 5 4 true true 2 5 6 false false Software Testing and Maintenance 12 Predicate vs Clause Coverage  Does predicate coverage subsume clause coverage? Does clause coverage subsume predicate coverage?  Example: p = a ∨ b a b a ∨ b 1 T T T 2 T F T 3 F T T 4 F F F7 Software Testing and Maintenance 13 Combinatorial Coverage  For each predicate p, TR has test requirements for the clauses in p to evaluate to each possible combination of truth values  Example: (a ∨ b) ∧ c a b c (a ∨ b) ∧ c 1 T T T T 2 T T F F 3 T F T T 4 T F F F 5 F T T T 6 F T F F 7 F F T F 8 F F F F Software Testing and Maintenance 14 Active Clause  The major clause is the clause on which we are focusing; all of the other clauses are minor clauses.  Typically each clause is treated in turn as a major clause  Determination: Given a major clause c in predicate p, c determines p if the minor clauses have values so that changing the truth value of c changes the truth value of p.  Note that c and p do not have to have the same value.  Example: p = a ∨ b8 Software Testing and Maintenance 15 Active Clause Coverage (ACC)  For each predicate p and each major clause c of p, choose minor clauses so that c determines p. TR has two requirements for each c: c evaluates to true and c evaluates to false.  Example: p = a ∨ b a b T f F f f T f F c = a c = b Software Testing and Maintenance 16 General Active Clause Coverage (GACC)  The same as ACC, and it does not require the minor clauses have the same values when the major clause evaluates to true and false.  Does GACC subsume predicate coverage?9 Software Testing and Maintenance 17 Correlated Active Clause Coverage (CACC)  The same as ACC, but it requires the entire predicate to be true for one value of the major clause and false for the other.  Example: a ↔ b Software Testing and Maintenance 18 CACC (2) a b c a ∧ (b ∨ c) 1 T T T T 2 T T F T 3 T F T T 5 F T T F 6 F T F F 7 F F T F  Example: a ∧ (b ∨ c)10 Software Testing and Maintenance 19 Restricted Active Clause Coverage (RACC)  The same as ACC, but it requires the minor clauses have the same values when the major clause evaluates to true and false.  Example: a ∧ (b ∨ c) a b c a ∧ (b ∨ c) 1 T T T T 5 F T T F 2 T T F T 6 F T F F 3 T F T T 7 F F T F Software Testing and Maintenance 20 CACC vs RACC (1)  Consider a system with a valve that might be either open or closed, and several modes, two of which are “operational” and “standby”.  Assume the following two constraints: (1) The valve must be open in “operational” and closed in all other modes; (2) The mode cannot be both “operational” and “standby” at the same time.  Let a = “The valve is closed”, b = “The system status is operational”, and c = “The system status is standby”. Then, the two constraints can be formalized as (1) ¬ a ↔ b; (2) ¬ (b ∧ c)11 Software Testing and Maintenance 21 CACC vs RACC (2) a b c (a ∧ b) ∨ c Constraints violated 1 T T T T 1 & 2 2 T T F T 1 3 T F T T 4 T F F F 5 F T T F 2 6 F T F F 7 …