CS447 Study Guide - Midterm Guide: Grand Admiral Thrawn, Basic Block, Segmentation Fault
89 views8 pages
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.
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 Nsub of N. Then the initial nodes of G′
are N0 ∩ Nsub and its final nodes are Nf ∩ Nsub. The edges of G′ are E ∩ (Nsub × 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 N0 and Nf have exactly one element each. Nf must be reachable from every node in
N , and no node in N \ Nf may be reachable from Nf , unless N0 = Nf .)
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.
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. 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) Test failure: execution that results in a failure. Debugging: the process of finding a fault given a failure. Static testing (at compile time: static analysis, review. Dynamic testing (at run time) focus of the course: black-box testing. Deriving tests from external descriptions of software: specifications, requirements, designs; anything but the code: white-box testing. Deriving tests from the source code, e. g. branches, conditions, statements.