Report

Logical Coverage (ch. 3) Course Software Testing & Verification 2013/14 Wishnu Prasetya How to test this? m(p) { if (!member(p) || (p.age>17 && !admin(p)) S0 ; else S1 ; } m(p) { if (!member(p)) goto L0 if (!p.age17) goto L1 if (!admin(p)) goto L1 L0: S0 ; L1: S1 ; } The code to the left is often transformed to the “short-circuiting” version above by a compiler. • Edge coverage or even full path coverage on the original code may feel inadequate. • The short circuit version do have more paths (4), but requires us to know what the compiled code is. 2 The obvious ones Member(p) (p.age>17 admin(p)) a (b c) • (C3.12) Predicate coverage • (C3.13) Clause coverage; Note that AO call “Member(p)” a clause instead of e.g. proposition. |TR| = ... ? – feels too weak – strangely does not subsume predicate coverage, nor the other way around. • (C3.14) All combinations explodes if the formula is large 3 Using active clauses a (b c) a b c 0 0 0 1 0 0 1 0 0 1 1 0 1 1 0 duplicates 1 1 1 • Major and minor clause. • (Def 3.42) a major clause c of p determines p if it is possible to make it active : to assign values to the minor clauses so that changing the value of c changes the value of p. • (Def3.43, Active Clause Covrg, ACC) For each major clause c which determines p, TR includes the cases c=1 and c=0. Minor clauses must be given values that would make p active. • |T| 2*n, but duplicates can be removed, ending up with |T| n+1, if n is number of clauses. Sounds good, but.... 4 You need to fix the def. of ACC! a b a b ab 0 0 1 1 1 1 • Active Clause Covrg (ACC): for each major clause c which determines p, TR includes the cases c=1 and c=0; etc need refinement! – does not specify if you should use the same values of minor clauses or not. – does not require p to actually change when you change c – does not subsume predicate covrg. See example above. 5 Correlated and Restricted ACC a b a b ab 0 0 1 1 0 0 0 0 1 0 1 0 • (C3.15) General ACC: for each major clause c which determines p, TR includes the cases c=1 and c=0. Minor clauses must be given values that would make p active. The values of the minors in both cases do not have to be the same. actually this is just the same as ACC. • (C3.16) Correlated ACC: as above, but for those two cases of c, one must cause p to be 1 and the other 0. • (C3.17) Restricted ACC: as in ACC but the values of the minors 6 chosen in both cases of c must be the same. Correlated vs Restricted ACC a (b c) a: b: c: • • • • isStudent(p) ( isMasterStudent(p) c ) a b c whole a b c whole 0 0 1 0 0 1 0 0 1 1 0 1 1 1 0 1 1 0 0 0 1 0 0 0 1 1 0 1 1 1 0 1 1 0 0 0 1 0 0 0 1 0 1 1 1 0 1 1 a: b: c: Left shows tests that cover CACC; after removing duplicates we get |T| = 4. Right covers RACC; after removing duplicates |T| = 4. RACC subsumes CACC 7 Keep in mind some combinations may actually be impossible Inactive-clause approach • ACC-variants makes sure that each situation where a clause affects the whole predicate is tested. Inactive clause is the opposite. • A major clause c is in inactive if it is possible to assign values to minor clauses so that changing the value of c won’t change the value of p. • (Def3.44, Inactive Clause Coverage, ICC) For each major clause c, if it is possible to make it inactive, TR includes: (1) a test where c=0 and p=1, (2) a test where c=1 and p=1, (3) a test where c=0 and p=0, (4) a test where c=1 and p=0. Minor clauses must be given values that make c inactive. • (C3.18, GICC) if the values of minor clauses in 1,2,3,4 do not have to be the same. • (C3.19, RICC) if the values of minors in 1/2 and 3/4 have to be 8 te same. Overview Combinatorial Clause Coverage COC Restricted Active Clause Coverage RACC Restricted Inactive Clause Coverage RICC Correlated Active Clause Coverage CACC General Inactive Clause Coverage GICC General Active Clause Coverage GACC Clause Coverage CC Predicate Coverage PC 9 Finding values to set a clause active/inactive • In ACC-variants we need to figure out how to assign values to minor clauses to make a major clause c determines p. Is there an algorithm for this!? yes; simple, namely by solving (finding values of the variables that make the formula true) : pc=0 pc=1 • Equivalently, solve: pc=0 xor pc=1 = 1 • How to solve such a formula? You can imagine how; but if p is large, use e.g. a SAT solver. 10 Constructing the TR • We’ll take CACC as an example. Given a p, and a constraint B over the clauses (e.g. isMasterStd(p) isStd(p)). • For each clause c, solve these: (1) Bc=1 (pc=1 = 1) ( pc=0 xor pc=1) (2) Bc=0 (pc=0 = 0) ( pc=0 xor pc=1) Add the solutions to TR. • Remove duplicates from TR. 11 Going back to program p.pt+1 < 1000 awardPt(p) { p.pt ++ ; if (birthday(p) && p.pt <1000 ) notify(p) ; } • Apply a logic-coverage at each decision point. This produces a TR for each. But : – we still have to calculate the corresponding program’s inputs calculate it by hand? – Can we automate the calculation? what to do with loops/recursions? 12 Disjunctive Normal Form (DNF) ((a c) b) (a c) (a c) (b c) • Rather than investigating each clause of p, we can opt to investigate different “logical scenarios” that affect p. • Every proposition logic formula f can be rewritten to an equivalent DNF. A DNF consists of implicants, connected by . Each implicant consists of literals connected by . A literal is a clause, or a negation of a clause. 13 Implicants of p and p p = ab bc p = (ab bc) = b ac • We’ll write p to abbreviate p • Implicants of p scenarios leading to p becomes true • Implicants of p scenarios leading to p become false. • Idea: cover all those scenarios. 14 Implicant Coverage p = ab bc p = (ab bc) = b ac implicant a b c ab 1 1 0 bc 1 1 0 b 0 0 1 ac 0 0 1 • (C3.20, IC) Let p be a DNF, and p be a DNF of p; for each implicant i in p and p TR includes the case that i = 1. • IC subsumes pred. cov (PC); but not necessarily 15 subsumes any ACC variant. Unique true point p = abc abc bc p = ab ac bc • (p140) a unique true point of a DNF p wrt implicant i is values assignment that makes i = 1 and other implicants (of p) = 0. • (C3.21, Unique True Point Covrg, UTPC) Given minimal DNF p and its negation p; for every implicant i in p and p the TR includes a unique true point for i. • (p140) Prime implicant, e.g. abc in red; abc is not. • (p140) Redundant implicant, e.g ab in blue. • A DNF is minimal if every implicant is prime and not redundant. In such a DNF, there exists a test satisfying an 16 implicant that does not satisfy the others. IC vs UTPC p = ab bc p = b ac implicant a b c ab 1 1 0 bc 1 1 0 b 0 0 1 ac 0 0 1 implicant a b c ab 1 1 1 bc 0 1 0 b 0 0 0 ac 0 1 1 |T| = 2 |T| = 4 17 Converting to DNF ab a b 0 1 0 1 1 1 1 0 c 00 01 11 10 0 0 1 1 1 1 1 0 1 1 • Rewriting, using Boolean algebra • For small number of clauses we can also use Karnaugh map (p144 -145). Important property: the combinations that belong to two adjacent cells, differ only in one bit. (“adjancent” in donut sense.) This allows simplication over those cells. • Karnaugh gives you minimal DNF. if you make sure that every group has at least one non-shared cell. 18 Near False Point • Not suprisingly, UTPC does not subsume GACC it just disregard clauses. • Let p be a DNF with implicant i. Let c be a clause in i. A nearfalse point is a values assignment that makes p=0, but if we flip the value of c, it will make i=1 (thus also p). p = ab bc Near-false points for a in ab : 011 Flipping the value of a : 111 makes ab true (and p too) • NFP gives us a concept of how a clause influences an implicant. • Hey, this 111 is actually also a UTP of ab ! 19 Near False Point p = ab bc Near-false points for a in ab : 011 Flipping the value of a : 111 makes ab true (and p too) is actually also a UTP of ab • (C3.22, Corresponding Unique True Point and Near False Point Pair Covrg) Given a minimalDNF p, for every clause c and implicant i, TR contains a unique true point for i and a near-false point wrt c and i, such that these points only differ in the value of c. • Does not subsume UTPC (simply because you dont have the DNF for p) , but it subsumes RACC. 20 UTPC vs CUTPNFP • How strong are they compared to each other? • Well, we just said they are unrelated. • Still... let’s define a new metric: their ability to reveal certain types of faults let’s take hypothetical faults you can make when you manually write down a DNF 21 Some mistakes when coding down a DNF • • • • • • • • • ENF: Expression Negation Fault TNF: Term/Implicant Neg. Fault TOF: Term Omission Fault LNF: Literal Negation Fault LRF: Literal Reference Fault LOF: Literal Omission Fault LIF: Literal Insertion Fault ORF+: Operator Reference Fault ORF*: Operator Reference Fault f = ab+c f = ab+c f = ab+c f = ab+c f = ab + bcd f = ab + c f = ab + c f = ab + c f = ab + c f’ = ab+c f’ = ab+c f’ = ab f’ = ab+c f’ = ad + bcd f’ = a + c f’ = ab + bc f’ = abc f’ = a + b + c Key idea: fault classes are related to testing. A test case “reveals” a fault if it results f’ is different than the expected result on f. A test-case that reveals certain faults may reveal additional faults. 22 Literal Insertion Fault LIF Term Omission Fault TOF Operator Reference Fault ORF+ Literal Reference Fault LRF Literal Negation Fault LNF Literal Omission Fault LOF Operator Reference Fault ORF* Term Negation Fault TNF Expression Negation Fault ENF UTPC can detect TOF. CUTPNFP detects TOF as well, and detects LOF too. 23