false

Study Guides
(248,005)

Canada
(121,222)

University of Waterloo
(5,717)

Computer Science
(334)

CS 447
(6)

Lin Tan
(6)

Midterm

Unlock Document

Computer Science

CS 447

Lin Tan

Winter

Description

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,
Failure Recovery
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
o Review
Walk-through (informal)
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,
statements.
Note: impossible to completely test a nontrivial system ( potential inputs are infinite ) –
practical limitations ( prohibitive time and cost ) – Theoretical limitations (halt problem )
RIP Model:
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
reached.
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
stop testing.)
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
Subgraph
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.
Note:
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
path.
NON-deterministic
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
G.
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.
Control-Flow Graph
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

More
Less
Related notes for CS 447

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.