Study Guides
(238,096)

Canada
(114,916)

University of Waterloo
(5,555)

Computer Science
(327)

CS 447
(6)

Lin Tan
(6)

Final

# Final Cheat Sheet This includes all the material in the course summarized

Unlock Document

University of Waterloo

Computer Science

CS 447

Lin Tan

Winter

Description

Fault, Error, Failure
Definitions
Debugging: The process of finding a fault given a failure.
Error: An incorrect internal state (unobserved).
Failure: External, incorrect behaviour with respect to the expected behaviour
(observed).
Fault: A static defect in the software (incorrect lines of code).
Test Failure: Execution that results in a failure.
Testing: Evaluating software by observing its execution.
Graphs
Types of Coverage
NC, Node Coverage
o TR contains each reachable node in G.
EC, Edge Coverage
o TR contains each reachable path of length up to 1, inclusive, in G.
o Includes single nodes due to “up to” part.
EPC, Edge Pair Coverage
o TR contains each reachable path of length up to 2, inclusive, in G.
CPC, Complete Path Coverage
o TR contain all paths in G.
o Impossible if graph has a loop
SPC, Specified Path Coverage
o TR contains a set S of test paths, where S is supplied as a parameter.
PPC, Prime Path Coverage
o TR contains each prime path in G.
o PPC does not subsume EPC
If a node n has a path to itself EPC requires [n, n, m] which is
not prime.
SRTC, Simple Round Trip Coverage
o TR contains at least one round-trip path for each reachable node in G
that begins and ends a round-trip path.
CRTC, Complete Round Trip Coverage
o TR contains all round-trip paths for each reachable node in G.
ADC, All-Defs Coverage
o For each set of du-paths S=du(n,v), TR contains at least one path d in
S.
o Every def reaches a use
AUC, All-Uses Coverage
o For each set of du-paths to uses S=du(ni,nj,v), TR contains at least
one path d in S.
o Every def reaches all possible uses.
ADUPC, All-Du-Paths Coverage
o For each set S=du(ni, nj, v), TR contains every path d in S.
o All the paths between defs and uses. Definitions
Actual parameter: Variable in the caller.
Formal parameter: Variable in the callee.
Basic Block: A block which has one entry point and one exit point.
Best Effort Touring: Satisfy as many test requirements as possible without
sidetrips. Allow side trips to satisfy unsatisfied test requirements.
Caller: A unit that invokes another unit.
Callee: The unit that is called.
Callsite: Statement or node where the call appears.
Definition (def): A location where a value for a variable is stored into
memory.
def(n) or def(e): The set of variables that are defined by bode n or edge e.
Def-clear: A path from li to lj is def-clear with respect to variable v if v is not
given another value on any of the nodes or edges in the path.
du-path: A simple subpath that is def-clear with respect to v from a def of v to
a use of v.
DU pair: A pair of locations (li, lj) such that a variable v is defined at li and
used at lj.\
First-use: The set of nodes that have uses of a variable u and for which there
is a def-clear and use-clear path from the call site to the nodes.
Last-def: The set of nodes that define a variable x and has a def-clear path
from the node through a callsite to a use in another unit.
Prime Path: A simple path that does not appear as a proper subpath of any
other simple path.
Reach: If there is a def-clear path from li to lj with respect to v, the def of v at
li reaches the use at lj.
Round Trip Path: A prime path that starts and ends at the same node.
Simple Path: A path from node ni to nj is simple if no node appears more
than once, except possibly the first and last nodes are the same
Tour: A test path p tours subpath q if q is a subpath of p.
Tour With Sidetrips: A test path p tours subpath p with sidetrips iff every
edge in q is also in p in the same order.
Tour With Detours: A test path p tours subpath p with detours iff every node
in q is also in p in the same order.
Use: A location where a variable’s value is accessed.
use(n) or use(e): The set of variables that are used by node n or edge e.
Logical Expressions
Types of Coverage
PC, Predicate Coverage
o For all p in P, p evaluates to true, and p evaluates to false
CC, Clause Coverage
o For each c in C, c evaluates to true, and c evaluates to false
CoC, Combinatorial Coverage o For each p in P, TR has test requirements for the clauses in Cp to
evaluate to each possible combination of truth values
ACC, Active Clause Coverage
o For each p in P and making each clause ci in Cp major, choose
assignments for minor clauses cj, j != i such that ci determines p. TR
has two requirements for each ci: ci evalues to true and ci evaluates
to false.
o Leaves ambiguity as to whether minor clauses can change value.
GACC, General Active Clause Coverage
o For each p in P and each major clause ci in Cp, choose minor clauses
cj, j != i, so that ci determines p. TR has two requirements for each ci:
ci evalues to true and ci evalues to false. The values chosen for minor
clauses cj do not need to be the same when ci is true and when ci is
false, that is, cj(ci = true) = cj(ci = false) for all cj OR cj(ci = true) !=
cj(ci = false) for all cj.
o Note that the cjs may be different when ci evaluates to true and ci
evaluates to false. There are no restrictions on the cj.
o Does not subsume PC
RACC, Restricted Active Clause Coverage
o For each p in P and each major clause ci in Cp, choose minor clauses
cj, j != i, so that ci determines p. TR has two requirements for each ci:
ci evalues to true and ci evalues to false. The values chosen for the
minor clauses cj must be the same when ci is true and when ci is
false, that is, it is required that cj(ci = true) = cj(ci = false) for all cj.
o The values for each cj must be the same when ci is true and when ci
is false.

More
Less
Related notes for CS 447