Why software fail: segmentation fault (incorrect memory usage), deadlocks, wrong
implementation, memory leaks, regression to past bugs
Avoiding Software Failures: Test the software (in-house, externally), Code review, Better
design (“write better code!”), Include fewer features
Better Programming Languages & IDEs Defensive programming
Coping with An Imperfect World: Disclaim liability, Release patches, Backup user data,
Fault: (or Bug) A static defect in the software (incorrect lines of code)
Error: An incorrect internal state (unobserved)(dynamic concept-while running)
Failure: External, incorrect behavior with respect to the expected behavior (observed)
(something doesn’t meet the requirement)
Software contains faults
- Fault avoidance: better design, programming language
- Fault detection: testing, debugging
- Fault Tolerance: redundancy, isolation
Testing: Evaluating software by observing its execution
Test Failure: Execution that results in a failure
Debugging: The process of finding a fault given a failure
Types of testing:
Static Testing (at compile time)
o Static Analysis
Code inspection (formal)
Dynamic Testing (at run time) – focus of the course
o Black-box testing. Deriving tests from external descriptions of software: specifications,
requirements, designs; anything but the code.
o White-box testing. Deriving tests from the source code, e.g. branches, conditions,
Note: impossible to completely test a nontrivial system ( potential inputs are infinite ) –
practical limitations ( prohibitive time and cost ) – Theoretical limitations (halt problem )
Three conditions must be present for a failure to be observed:
o Reachability: the location or locations in the program that contain the fault must be
o Infection: After executing the location, the state of the program must be incorrect.
o Propagation: The infected state must propagate to cause some output of the
program to be incorrect. Test Case
o Test Case: What you feed to software; What the software should output in response.
o Test Case Values: The input values necessary to complete some execution of the
software under test. (Traditionally called Test Case )
o Test Set: A set of test cases
o Expected Results: The result that will be produced when executing the test if and
only if the program satisfies its intended behavior.
Key Idea: Coverage -> Find a reduced space and cover that space.( tells us when we can plausibly
Test Requirement: A test requirement is a specific element of a software artifact that a test
case must satisfy or cover. (TR: a set of test requirements)
Coverage Criterion is a rule or collection of rules that impose test requirements on a test
set. Coverage criterion is a recipe for generating TR in a systematic way.
Coverage: Given a set of test requirements TR for a coverage criterion C, a test set T satisfies
C iff for every test requirement tr ∈TR, at least one t ∈ T satisfies tr.
Coverage Level: Given a set of test requirements TR and a test set T, the coverage level is
the ratio of the number of test requirements satisfied by T to the size of TR. help us
evaluate the goodness of a test set, especially in the presence of infeasible test requirements.
Criteria Subsumption: A test criterion C1 subsumes C2 if and only if every set of test cases
that satisfies criterion C1 also satisfies C2
Let G ′be a subgraph of G; then the nodes of G ′must be a subset N subof N. Then the initial nodes of G ′
are N 0∩ N suband its final nodes are N f∩ N sub. The edges of G ′are E ∩ (N sub × Nsub).
Path: is a sequence of nodes from a graph G whose adjacent pairs all belong to the set of
edges E of G.
Subpath: is a subsequence of a path.
Test Path: is a path p (possibly of length 0) that starts at some node in N0 and ends at some
node in Nf.
A node n is syntactically reachable from ni if there exists a path from ni to n. ( focus of the
course, can be computed using BFS, DFS )
A node n is semantically reachable if one of the paths from ni to n can be reached on some
input. ( is undecidable )
Reachability: We define reachG() as the portion of the graph that is syntactically reachable
from. When talking about nodes or edges in a graph G in a coverage criterion. ( Unreadable nodes : uninteresting, frustrate coverage criteria ) – include the same node of reachable
because it is of path length 0
SESE graphs (single-entry, single-exit): All test paths start at a single node and end at
another node ( if 0 and N fhave exactly one element each. N fmust be reachable from every node in
N , and no node in N \ N fmay be reachable from N , unless N 0= N f.)
pathG(t): is the set of test paths corresponding to test case t. (Connect test cases and test
paths with a mapping pathG from test cases to test paths)
Note: Each test case gives at least one test path. If the software is deterministic, then each
test case gives exactly one test path; otherwise, multiple test cases may arise from one test
Node Coverage(NC): For each node n ∈ reachG(N0), TR contains a requirement to visit node
n.( Node Coverage (NC): TR contains each reachable node in G.)
- Test set T satisfies node coverage on graph G if and only if for every syntactically
reachable node n ∈ N , there is some path p in path(T ) such that p visits n.
Edge Coverage (EC): TR contains each reachable path of length up to 1, inclusive, in G.
Edge-Pair Coverage (EPC): TR contains each reachable path of length up to 2, inclusive, in
Note: NC and EC are only different when there is an edge and another subpath between a
pair of nodes (as in an “if-else” statement)
Simple Path: if no node appears more than once in the path, except that the first and last
nodes may be the same.
o no internal loops
o can bound their length
o can create any path by composing simple paths
o many simple paths exist (too many!)
Prime Path: if it is simple and does not appear as a proper subpath of any other simple path.
Prime Path Coverage (PPC): TR contains each prime path in G.
Note: There is a problem with using PPC as a coverage criterion: a prime path may be
infeasible but contain feasible simple paths.
Round Trip Path: is a prime path of nonzero length that starts and ends at the same node. Simple Round Trip Coverage (SRTC): TR contains at least one round-trip path for each
reachable node in G that begins and ends a round-trip path.
Complete Round Trip Coverage (CRTC): TR contains all round-trip paths for each
reachable node in G.
Complete Path Coverage (CPC): TR contains all paths in G.
Specified Path Coverage (SPC): TR contains a specified set S of paths.
Tour: Test path p tours subpath q iff q is a subpath of p.
Tour with sidetrips: Test path p tours subpath q with sidetrips iff every edge in q is also in
p, in the same order. ( if not included many TRs are infeasible )
Tour with detours: Test path p tours subpath q with detours iff every node in q is also in p,
in the same order. ( less practical )
TRtour: the subset of test requirements that can be toured
TRsidetrip: the subset of test requirements that can be toured with sidetrips.
Best Effort Touring: A set T of test paths achieves best effort touring if for every path p in
TRtour, some path in T tours p (directly) and for every path p in TRsidetrip, some path in T
tours p either directly or with a sidetrip.
o CFG nodes: zero or more statements
o CFG edges: an edge (s1,s2) indicates that s1 may be followed by s2 in an execution.
o A basic block: has one entry point and one exit point. (grouping together statements
which always execute together (in sequential programs)) might have multiple
successors, however, cannot jump to the middle of a basic block