Study Guides (248,005)
Canada (121,222)
CS 447 (6)
Lin Tan (6)

Midterm Review This includes all definitions and important notes to study for the midterm

8 Pages
Unlock Document

Computer Science
CS 447
Lin Tan

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

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
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.

Add your courses

Get notes from the top students in your class.