Transcript notes_6

CEN 5076 Class 6 – 10/10
Testing Theory cont.
•
•
•
•
•
Testing Theory cont.
Introduction
Categories of Metrics
Review of several OO metrics
Format of Presentation
Introduction to Testing Theory
Weyuker and Ostrand (W&O) 1980:
The primary goals of a theory of testing are to
provide a basis for practical program testing
methodologies, and to establish ways of
determining the effectiveness of tests in
detecting errors.
•
We first look at the approach by Goodenough
and Gerhart (G&G) (1975).
•
Then the approach by Weyuker and Ostrand
(1980).
CEN 5076 Class 6 - 10/10
2
Introduction to Testing Theory
The following concepts and theorem are taken
from “Towards a Theory of Test Data
Selection” by Goodenough and Gerhart 1975.
•
The purpose of testing is to determine whether
a program contains any errors.
•
An ideal test therefore succeeds only when a
program contains no errors.
•
What are the characteristics of an ideal test?
CEN 5076 Class 6 - 10/10
3
Introduction to Testing Theory cont
Basic defns:
An ideal test for a program F consists of a set
of test data T = { ti } s.t. there is an input d in
F’s domain for which an incorrect output is
produced iff there is some ti  T on which F is
incorrect.
F is a program, D is the domain and R the
output for F.
On input d  D, F (if it terminates) produces
output F(d)  R.
CEN 5076 Class 6 - 10/10
4
Introduction to Testing Theory cont
Basic defns cont:
F is correct on input d (abbreviated OK(d) ) if
F(d) exists and OUT(d, F(d)), i.e., OUT(d, F(d))
is true iff F(d) is an acceptable result.
A test T for program F is simply a finite subset
of D.
A test selection criterion, C, specifies
conditions which must be fulfilled by a test.
T constitutes and ideal test if OK(t) for all t
implies OK(d) for all d  D.
CEN 5076 Class 6 - 10/10

T
5
Introduction to Testing Theory cont
Basic defns cont:
If T = D then we have exhaustive testing and
the above holds. It is usually impractical to
perform exhaustive testing
A test is successful iff (  t T) OK(t))
C is reliable iff either every test selected by C
is successful, or no test selected is successful.
C is valid iff whenever program F is incorrect,
C selects at least one test set T which is not
successful for F.
CEN 5076 Class 6 - 10/10

6
Introduction to Testing Theory cont
Basic defns cont:
A thorough test, T, satisfies COMPLETE(T, C),
where COMPLETE is a predicate that defines
how some data selection criterion C is used in
selecting a particular set of test data T.
The data selection criterion C must be defined
so tests satisfying COMPLETE(T, C), produce
consistent and meaningful results, i.e., C is
reliable and valid.
CEN 5076 Class 6 - 10/10
7
Introduction to Testing Theory cont
•
If C is a reliable and valid criterion, then
any test selected by C is an ideal test.
OR
•
If the data selection criterion is reliable
as well as valid then every complete test
is capable of detecting every error in the
program.
CEN 5076 Class 6 - 10/10
8
Introduction to Testing Theory cont
Given a program F, with domain D, output requirement OK(d) = OUT(d, F(d))
and test data selection criterion C:
(1) SUCCESSFUL(T )  ( t T ) OK (t )
(2) RELIABLE (C )  (T 1, T 2  D)(COMPLETE (T 1, C )  COMPLETE (T 2, C )
 ( SUCCESSFUL(T 1)  SUCCESSFUL(T 2)))
(3) VALID(C )  (d  D) OK (d )  (T  D)(COMPLETE (T , C ) 
( SUCCESSFUL(T ))
Fundamenta l Theorem
(T  D)( C )(COMPLETE (T , C )  RELIABLE (C )  VALID(C ) 
SUCCESSFUL(T ))  (d  D) OK (d )
CEN 5076 Class 6 - 10/10
9
Introduction to Testing Theory cont
•
The theorem states that test satisfying
COMPLETE(T, C) where C satisfies RELIABLE
and VALID are “thorough” in the appropriate
sense.
•
Note, proving a data selection criterion to be
reliable and valid, and then finding and
successfully executing a complete test
satisfying this criterion is just a way of proving
the correctness of the program.
CEN 5076 Class 6 - 10/10
10
Introduction to Testing Theory cont
Example (to be done in class):
F computes d * d, for d an integer, while the
output spec is F(d) = d + d
Show when C1 selects {0, 2}, C1 is a reliable
but not a valid test.
Show when C2 selects subsets of {0, 1, 2, 3, 4},
C2 is a valid but not a reliable test.
If F computes d + 5 is C2 reliable and/or valid?
CEN 5076 Class 6 - 10/10
11
Introduction to Testing Theory cont
Weyuker and Ostrand (W&O) point out several
difficulties with applying the Goodenough and
Gerhart (G&G), theory:
1. Concepts of reliability and validity are defined
w.r.t. the entire input domain of a program, i.e.
in general one does not know what errors are
actually present in a program.
2. All the defns are relative to a single program. A
criterion which is reliable or valid for F is not
necessarily so for a slightly different program
F’.
CEN 5076 Class 6 - 10/10
12
Introduction to Testing Theory cont
A measure of a test’s goodness should be
independent of whether or not the program is
correct, and if incorrect, should not depend on
which errors actually appear in the program.
3. Neither validity nor reliability is preserved
throughout the debugging process.
4. Lack of independence of the properties of
validity and reliability.
5. If not familiar with the program it is practically
impossible to find test selection criteria which
are both reliable and valid.
CEN 5076 Class 6 - 10/10
13
Introduction to Testing Theory cont
•
W&O state that reliability and validity represent
ideal abstract goals for test set selection.
•
W&O state that a test criterion C is revealing
for a subset S of the input domain if whenever
S contains an input which is processed
incorrectly then every test set which satisfies C
is unsuccessful.
REVEALING (C , S ) iff
(d  S ) (OK ( d ))  (T  S ) (COMPLETE (T , C )
 SUCCESS(T ))
CEN 5076 Class 6 - 10/10
14
Introduction to Testing Theory cont
•
If S is a revealing subdomain, running
successful tests from S only assures that
correctness of the program on S. Even this
cannot in general be guaranteed.
•
Showing that S is revealing requires a proof
that no error, no matter how unlikely, can occur
for the elements of S, i.e., requires the
equivalent to a proof of correctness for the
subdomain.
CEN 5076 Class 6 - 10/10
15
Introduction to Testing Theory cont
•
Weyuker has shown that there can be no
algorithm which can decide whether or not a
given statement, branch, or path of a program
may ever be exercised, nor whether or not
every such unit may be exercised.
•
This a testing methodology which requires the
generation of data to do one or more of the
above cannot be guaranteed to terminate.
CEN 5076 Class 6 - 10/10
16
Introduction to Testing Theory cont
Types of errors:
•
Goodenough states that in general software
errors fall into two categories:
1. Performance errors – failure to produce results
within specified or desired time and space
limitations), and
2. Logic errors – production of incorrect results
independent of the time and space required.
CEN 5076 Class 6 - 10/10
17
Introduction to Testing Theory cont
Types of errors - Logic errors:
•
Construction – failure to satisfy a specification
through error in an implementation.
•
Specification – failure to write a specification
that correctly represents a design.
•
Design – failure to satisfy an understood
requirement.
•
Requirements – failure to satisfy the real
requirement.
CEN 5076 Class 6 - 10/10
18