Help page for Minimal-MUMCUT Coverage web app

Help Page for the Minimal MUMCUT Coverage Web Application

This tool produces test set specifications to satisfy DNF coverage logic criteria. Predicates must be in minimal DNF form. Users enter a predicate and choose a criterion, and the tool generates non-equivalent mutants that can only be killed by a test set that satisfies that criterion.

A minimal-DNF predicate consists of literals connected by AND and terms separated by OR, where all terms are prime implicants. A prime implicant of a function is an implicant that cannot be covered by a more general (more reduced—meaning with fewer literals) implicant. A test set that satisfies the Minimal-MUMCUT criterion is guaranteed to detect the following nine single faults:

1.	Expression Negation Fault	(ENF)	Implementing ab + cd as !(ab + cd)
2.	Term Negation Fault	(TNF)	Implementing ab + cd as !(ab) + cd
3.	Term Omission Fault	(TOF)	Implementing ab + cd as cd
4.	Literal Reference Fault	(LRF)	Implementing ab + cd as cb + cd
5.	Literal Insertion Fault	(LIF)	Implementing ab + cd as abc + cd
6.	Literal Omission Fault	(LOF)	Implementing ab + cd as b + cd
7.	Literal Negation Fault	(LNF)	Implementing ab + cd as !(a)b + cd
8.	Operator Reference Fault +	(ORF+)	Implementing ab + cd as abcd
9.	Operator Reference Fault .	(ORF.)	Implementing ab + cd as a + b + cd

A test set that detects all LIFs (LIF faults), LRFs, and LOFs is guaranteed to detect the other six faults. The Minimal-MUMCUT criterion guarantees detection of all LIFs, LRFs, and LOFs by selecting specific Unique True Points (UTP) and Near False Points (NFP) according to complex rules (as defined in the papers referenced below.) A UTP for a term is a point that makes only that term true. For ab + cd, 1100 is a UTP for ab. An NFP for a literal is a point that makes the predicate false but if that single literal is negated, the predicate is true. For ab + cd, an NFP for a is 0100. For readers familiar with the MUMCUT strategy, Minimal-MUMCUT uses the feasiblity of the MUTP and CUTPNFP criteria to reduce MUMCUT test set size without sacrificing fault detection.

Minimal-MUMCUT is composed of three component criteria:

MUTP - Guarantees detection of faults ENF, ORF+, LNF, TNF, TOF, LIF, and when feasible, LRF.
CUTPNFP - When feasible, guarantees detection of all faults MUTP detects except LIF.
MNFP - Guarantees detection of faults ENF, TNF, ORF. LNF, LOF, and when feasible, LRF.

There is some debate as to which tests to generate when CUTPNFP is infeasible, because no UTP-NFP pair exists for some literals in a term. The approach taken by this tool is that when a corresponding pair does not exist, a non-corresponding NFP will be selected rather than not selecting any NFPs at all.

When selecting a criterion, the tool shows the truth assignments needed to satisfy the criterion and also shows a set of mutations whose corresponding mutants can only be killed by tests that satisfy the criterion. The tests and mutants are listed in order such that the first test can kill the first mutant, the second test can kill the second mutant, and so on.

The mutants generated by the tool correspond to one of seven fault types:

(false)
(true)
TOF
LIF-LIF
Term Replacement Fault - Literal Insertion Faults (TRF-LIF)
Term Insertion Fault - Literal Reference Faults (TIF-LRF)
Term Insertion Fault - Literal Omission Fault (TIF-LOF)

A (false) mutant means that the predicate has been replaced by the keyword false. A (true) mutant means that the predicate has been replaced by the keyword true. A TOF is as described above and can be produced when a term in the predicate contains all unique literals. A LIF-LIF is a double fault where a LIF occurs in two different terms and is only generated as a mutant when selecting the Minimal-MUMCUT/SMOTP option.

A TRF-LIF involves replacing a term by one or more terms so that if the fault is detected, the tests are guaranteed to detect one or more LIFs. For ab + cd, a TRF-LIF would be abc + ab!d + cd.

A TIF-LRF involves inserting a term such that if the fault is detected, the test is guaranteed to detect one or more LRFs. For ab + bc, a TIF-LRF would be ab + bc + a!b!c.

A TIF-LOF involves inserting a term such that if the fault is detected, the test is guaranteed to detect one or more LOFs. For ab + cd, a TIF-LOF would be ab + cd + a!bc!d.

The tool abbreviates each TRF-LIF as a TRF and collectively abbreviates TIF-LRFs and TIF-LOFs as TIFS. A TRF mutant can only be killed by an UTP and a TIF mutant can only be killed by a NFP.

The tool also detects equivalent LIF and LRF mutants so that all mutants generated are non-equivalent. For example, given ab + bc, an equivalent LIF would be ab!c + bc.

The test data generated for Minimal-MUMCUT will also detect most double faults (killing second order mutants). Of the 81 (9x9) double fault types, all but six are guaranteed to be detected by a test set that satisfies the Minimal-MUMCUT criterion. The six double fault types that are not guaranteed to be detected are TOF-LRF, ORF.-LRF, LOF-LRF, LIF-LRF, LRF-LRF, and LIF-LIF.

In practice it has been found to be likely that a Minimal-MUMCUT test set will detect all but the LIF-LIF faults. Incorporating a criterion known as SMOTP for pairs of MUTP infeasible terms will guarantee detection of all occurrences of double LIFs. To guarantee this, when selecting Minimal-MUMCUT/SMOTP, Overlapping True Points (OTPs) may be included in the tests. An OTP is a point that makes two terms true in the predicate. For a!bc + a!dc + e, an OTP for the first two terms is 10100. This is the only point that can detect the double LIF: a!bcd + a!dcb + e. TRF mutants, where a TRF occurs in two terms, are generated and such mutants can only be killed by an OTP that detects the LIF-LIF.

For users who are familiar with the MUTP strategy, a Minimal-MUMCUT test set guarantees detection of all double faults if and only if MUTP is feasible. For users familiar with the CUTPNFP strategy, a Minimal-MUMCUT test set guarantees detection of all but the LIF-LIF if and only if CUTPNFP is feasible. Thus, the data generated from the Minimal-MUMCUT/SMOTP option is guranteed to detect all but five double fault types, but when the CUTPNFP stragegy is feasible, the data generated from the tool will detect all double fault types. In practice it has been found that the CUTPNFP strategy is usually feasible.

Restrictions:

Predicates are limited to 26 unique literals
Predicates must be in Minimal DNF.
Each literal must be a single lower case letter.
No letters of the alphabet may be skipped. For example, a & b is valid but a & c is not since the letter b is skipped.
The infeasible literal combinations must allow at least a single UTP for each term and a single NFP for each literal.

The various minimization options produce a combinatorial optimization model to minimize the number of tests needed to satisfy (as much as possible) the chosen criterion. While a MUTP, CUTPNFP, or MNFP test set produced by the tool is guaranteed to be minimal in the sense that if even one test is removed, the criterion will not be satisfied, it is not necessarily minimum in that it may be possible to form a test set with fewer tests and still satisfy the criterion. The optimization problem can be run in an LP solver such as MPL or CPLEX to obtain a minimum test set. To run the model in a solver you may need to remove the ";" characters in the model (some solvers require a ";" to separate constraints whereas for others using it causes a warning that can lead to incorrect results).

The Fault Detection Maximization option takes as input the desired test set size and produces a combinatorial optimization model to solve the problem of finding a test set of that size that maximizes the number of minimal DNF single logic faults detected.

Technical details on these criteria are in the the following papers:

Reconciling perspectives of software logic testing, Garrett Kaminski, Gregory Williams, and Paul Ammann, Software Testing, Verification, and Reliability, 18(3):149-188, September 2008.
Using a Fault Hierarchy to Improve the Efficiency of DNF Logic Mutation Testing, Garrett Kaminski and Paul Ammann, 2nd IEEE International Conference on Software Testing, Verification and Validation (ICST 2009), pages 386-395, Denver CO, April 2009, IEEE Computer Society
Using Logic Criterion Feasibility to Reduce Test Set Size While Guaranteeing Fault Detection, Garrett Kaminski and Paul Ammann, 2nd IEEE International Conference on Software Testing, Verification and Validation (ICST 2009), 356-365, Denver CO, April 2009, IEEE Computer Society
Using Logic Criterion Feasibility to Reduce Test Set Size While Guaranteeing Double Fault Detection, Garrett Kaminski and Paul Ammann, Mutation 2009 Workshop, pages 167-176, Denver CO, April 2009, IEEE Computer Society

In the fault detection maximization model, faults involving a term are modeled as variables whose names consist of the fault type, followed by an underscore, followed by the term the fault occurs in. For example, a TOF for the 2nd term would correspond to the variable TOF_2 in the optimization model. Faults involving a literal are modeled as variables whose names consist of the fault type, followed by an underscore, followed by the term the fault occurs in, followed by an underscore, followed by the literal in the term the fault occurs in. For example, a LOF for the 3rd literal in the 2nd term would be represented by the variable LOF_2_3 in the optimization model. For LIFs and LRFs, the corresponding variable names in the optimization model include an additional underscore indicating the name of the literal that is being inserted or referenced, where uppercase indicates negation. For example, LRF_3_2_C corresponds to a fault where the 2nd literal in the 3rd term is repl aced with the literal !c. For users familiar with optimization modeling, the variables that begin with a captial "M" are used for constratins that model implications. These constratints ensure that a given fault is detected if and only if one of the test points that detects the fault is chosen.