Software Verification and Validation

Lecture No. 11
 Module 69:
Confidence based testing techniques
Confidence based testing techniques

 Structural (coverage-
based) techniques:
 Goodness was determined by
the coverage of the product
by the test set so far: e.g., %
of statements or
requirements tested
 Often based on control-flow
graph of the program
 Three techniques:
– control-flow coverage
– data-flow coverage
– coverage-based testing of
requirements
Confidence based techniques
 Confidence based
methods:
 In coverage-based testing,
we take the structure of
the artifact to be tested
into account
 In fault-based testing, we
do not directly consider
this artifact
 We look for a test set with
high ability to detect faults
 Two techniques:
 Fault seeding
 Mutation testing
Confidence based techniques
 Fault seeding and mutation
testing are fault-oriented
techniques, applicable to all
levels of testing.
 In Fault Seeding Technique,
a predefined number of
artificially generated errors
is "sown" in the program
code.
Confidence based techniques
 Whereas, in mutation
testing, we sow one fault at
a time leading to original
program and mutant version
of that program
 Test runs are used to detect
these faults
 We examine ratio between
actual and artificial errors
based on the total number
of detected errors.
 The testers do not know the
artificially generated errors.
 Module 70:
Mutation Testing
Mutation Testing

 Mutation Testing is a
testing technique that
focuses on measuring the
adequacy of test cases.
 Mutation Testing is NOT a
testing strategy like path or
data-flow testing. It does
not outline test data
selection criteria.
 Mutation Testing should
be used in conjunction with
traditional testing
techniques, not instead of
them.
Mutation Testing

procedure insert(a, b, n, x);

begin bool found:= false;
for i:= 1 to n do
if a[i] = x n-1
then found:= true; goto
leave endif
enddo;
leave:
if found 2
then b[i]:= b[i] + 1
else n:= n+1; a[n]:= x; b[n]:= 1
endif
end insert;
-
 Mutation Testing

 Let P be the original, and P’ the mutant

 Suppose we have two tests:
 T1 is a test, which inserts an element that equals a[k] with
k<n
 T2 is another test, which inserts an element that does not
equal an element a[k] with k<n
 Now P and P’ will behave the same on T1, while they differ for
T2
 In some sense, T2 is a “better” test, since it in a way tests
this upper bound of the for-loop, which T1 does not
Mutation Testing
 How to use mutants in
testing:
 If a test produces different
results for one of the
mutants, that mutant is said
to be dead
 If a test set leaves us with
many live mutants, that test
set is of low quality
 If we have M mutants, and a
test set results in D dead
mutants, then the mutation
adequacy score is D/M
 larger mutation adequacy
score means better test set
Mutation Testing

 Strong vs weak mutation

testing:
 Suppose we have a
program P with a
component T
 We have a mutant T’ of T
 Since T is part of P, we
then also have a mutant P’
of P
Mutation Testing

 In weak mutation testing,

we require that T and T’
produce different results,
but P and P’ may still
produce the same results
 In strong mutation testing,
we require that P and P’
produce different results
Mutation Testing

 Assumptions underlying
mutation testing:
 Competent Programmer
Hypothesis: competent
programmers write
programs that are
approximately correct

 Coupling Effect Hypothesis:

tests that reveal simple
fault can also reveal
complex faults
Mutation Testing
 Mutation Testing:
 Faults are introduced into
the program by creating
many versions of the
program called mutants.
 Each mutant contains a
single fault.
 Test cases are applied to
the original program and to
the mutant program.
 The goal is to cause mutant
program to fail, thus
demonstrating effectiveness
of the test case.
 Module 71:
Test and Mutation Adequacy
Test and Mutation Adequacy
 Test adequacy:
 A test case is adequate if it
is useful in detecting faults
in a program.
 A test case can be shown to
be adequate by finding at
least one mutant program
that generates a different
output than does the
original program for that
test case.
 If original and all mutants
generate same output, test
case is inadequate.
Test and Mutation Adequacy

 Mutant programs:
 Mutation testing involves
the creation of a set of
mutant programs of the
program being tested.
 Each mutant differs from
the original program by one
mutation.
 A mutation is a single
syntactic change that is
made to a program
statement.
 Test and Mutation Adequacy

 Mutation adequacy:
 Mutation adequacy uses a similar concept to fault seeding to
evaluate the effectiveness of a test suite.
 Assume we have a test suite TS with confidence C with total
test cases c(j).
 Assume that the program under test P passes all the test
cases c(j) for 1 <= j <= C.
 Can we stop testing? That is, have we tested P adequately?
 The mutation adequacy criterion provides one answer that we
might use.
 The mutation adequacy approach differs from fault seeding in
that it is applied at a particular point in the testing process
and also in that faults are not directly inserted into P.
 Test and Mutation Adequacy

 Mutation adequacy:
 Instead, a series of mutants m(i) are created.
 Each mutant m(i) differs from P by the injection of exactly one
fault.
 Let M be the total number of mutants m(i).
 The test suite TS is applied to each mutant m(i).
 If a particular mutant m(i) fails any test in c(j), then it is said
to be killed.
 All mutants that are not killed are said to remain live at this
point.
 The ratio of killed to total mutants (K/M) can be considered a
measure of adequacy of TS.
Test and Mutation Adequacy
 Mutation score:mutation
score for a set of test cases
is the percentage of non-
equivalent mutants killed by
the test data.
 Mutation Score = 100 * D
/ (N - E)
 D = Dead mutants
 N = Number of mutants
 E = Number of
equivalent mutants
 A set of test cases is
mutation adequate if its
mutation score is 100%.
 Test and Mutation Adequacy

 Mutation operator – Example:

 Manually creating mutants is time-consuming.
 A collection of mutants m(i) created from P at some point in time
will no longer be representative of P after it has undergone many
changes.
 Mutation can be automated by through the concept of mutation
operators.
 Mutation operators are simple changes that can be made at
various program locations.
 Test and Mutation Adequacy

 Mutation operator example:

 The following table shows a program P to perform integer
division. Given inputs x and y, P computes the integer division
of x divided by y producing quotient q and remainder r. Three
mutants m(1), m(2), and m(3) are shown resulting from
application of the mutation operators in the previous table
Test and Mutation Adequacy

 Mutation testing –
evaluation:
 Theoretical and
experimental results have
shown that mutation testing
is an effective approach to
measuring the adequacy of
test cases.
 The major drawback of
mutation testing is the cost
of generating the mutants
and executing each test
case against them.
 Module 72:
Fault Seeding
Fault Seeding

 Fault Seeding, is used to

estimate the “number of
errors” remaining in a
program.
 In Fault Seeding Technique,
a predefined number of
artificially generated errors
is "sown" in the program
code.
 Fault Seeding

1. Before testing, “seed” the program with a number of “typical

errors” keeping careful track of the changes made.

2. After a period of testing, compare the number of seeded and

non-seeded errors detected.

3. Before testing, “seed” the program with a number of “typical

errors,” keeping careful track of the changes made.

4. After a period of testing, compare the number of seeded and

non-seeded errors detected.
Fault Seeding

3. If S is the total number of

faults seeded, n is the
number of seeded faults
detected, and N is the
number of non-seeded
errors detected, the
number of remaining (non-
seeded) faults in program
is:
N(S/n – 1)
 Fault seeding as a
technique introduced by
Mills (1972)
 Fault Seeding

 This helps in calculating confidence C

 C = 1 if n > N and C = S/(S - N + 1) if n < N
 where
 S is the number of seeded faults,
 N is the total number of non-seeded (indigenous) faults which
can be found
 We calculate N by
 N = S*n / s
 where n is actual number of non-seeded faults and s is the
number of seeded faults detected during testing.
 Fault seeding provides an alternative to structural testing
techniques providing us with a measure of sufficiency of testing or
effectiveness of our test suite.
 Fault Seeding

 One or more faults are deliberately introduced into a code base,

without informing the testers.
 The discovery of seeded faults during testing can be used to
calibrate the effectiveness of the test process.
 Let S is the total number of seeded faults, and s(t) is the number
of seeded faults that have been discovered at time t.
 s(t)/S is the seed-discovery effectiveness of testing to time t.
 If seeded faults are assumed are to be representative of actual
faults, then seed-discovery effectiveness can be assumed to be
representative of overall testing effectiveness
 Fault Seeding

 Question:
 Seed 100 faults into a project at time 0.
 Testing continues to time 30, at which point 73 of the seeded
faults have been detected.
 If 219 actual faults were discovered, what is the expected
number of total faults prior to seeding?
 How many latent faults are expected to remain in the software
at time 30?
 Answers:
 The discovered original faults are three times the numbered of
discovered seeded faults, so 300 original faults are expected.
 The latent faults are those remaining and not removed: (300 -
219) original faults plus (100 - 73) seeded faults, that is 81 +
27 = 108 latent faults.
Fault Seeding

 Fault types:
 Domain faults
 Computational faults
…
 Fault Seeding
Fault Seeding Mutation Testing

v
Fault Seeding

 Mutation Testing
 Best suitable for smaller
systems
 Critical systems
 Fault localization is easy
 Fault Seeding
 Economical yet fault
localization is difficult
 Module 73:
Mutation Testing Example
Mutation Testing Example

 Example Code:
 We do two mutations
 One by one
 Therefore there are three
versions, two mutants and one
original code

int myCompute(int a, int b) {

IF (a > b) (a < b)
return a + b;
ELSE
return a – b; (a / b)
}
Mutation Testing Example

 Three versions:

int myCompute(int a, int b) {

IF (a > b) return a + b;
ELSE return a – b; }

int myCompute(int a, int b) {

IF (a < b) return a + b;
ELSE return a – b; }

int myCompute(int a, int b) {

IF (a > b) return a + b;
ELSE return a / b; }
 Mutation Testing Example
 Test Output
(ORIGINAL CODE)
S # Test Cases Expected Actual
int myCompute(int a, int b) {
1 T1 = [{(2, 1), 3}] 3 3
IF (a > b) return a + b;
ELSE return a – b; } 2 T2 = [{1, 2), -1}] -1 -1

(MUTATION 1 (M1) S # Test Cases Expected Actual

int myCompute(int a, int b) {
1 T1 = [{(2, 1), 3}] 3 1
IF (a < b) return a + b;
ELSE return a – b; } 2 T2 = [{1, 2), -1}] -1 3

(MUTATION 2 (M2) S # Test Cases Expected Actual

int myCompute(int a, int b) {
IF (a > b) return a + b; 1 T1 = [{(2, 1), 3}] 3 3
ELSE return a / b; } 2 T2 = [{1, 2), -1}] -1 0.5
Mutation Testing Example

 Mutation Score = 100 * D /

(N - E)
 D = Dead mutants
 N = Number of mutants
 E = Number of equivalent
mutants
 Total dead mutants = 2
 Number of mutants = 2
 Equivalent mutants = 0
 Mutation score = 100 * 2/2
 Mutation score = 100%
 Word about equivalent mutants
…
 Module 74:
Fault Seeding Example
Fault Seeding Example
 Example Code:
 We do fault seeding
 N number of faults seeded in one go
 Therefore there are two versions,
one fault seeded and one original
code

int myCompute(int a, int b) {

IF (a > b) (a < b)
return a + b;
ELSE
return a – b; (a / b)
}
Mutation Testing Example

 Two versions:

int myCompute(int a, int b) {

IF (a > b) return a + b;
ELSE return a – b; }

int myCompute(int a, int b) {

IF (a < b) return a + b;
ELSE return a / b; }
 Mutation Testing Example
 Test Output
(ORIGINAL CODE)
S # Test Cases Expected Actual
int myCompute(int a, int b) { 1 T1 = [{(2, 1), 3}] 3 3
IF (a > b) return a + b; 2 T2 = [{1, 2), -1}] -1 -1
ELSE return a – b; }

Fault seeded code

S # Test Cases Expected Actual
int myCompute(int a, int b) {
1 T1 = [{(2, 1), 3}] 3 2
IF (a < b) return a + b;
2 T2 = [{1, 2), -1}] -1 3
ELSE return a / b; }
 Fault Seeding Example
This helps in calculating confidence C
C = 1 if n > N and C = S/(S - N + 1) if n < N
where
S is the number of seeded faults,
N is the total number of non-seeded (indigenous) faults which
can be found
We calculate N by
N = S*n / s
where n is actual number of faults detected during testing and s
is the number of seeded faults detected during testing.

C = 1 since N=0, n=2 => n > N

Fault Seeding Example

 The difference is in the

manner we execute
 Mutation testing
 Fault seeding
 Confidence calculation
…