Study Guides (238,096)
CS 447 (6)
Lin Tan (6)
Final

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

6 Pages
140 Views

School
University of Waterloo
Department
Computer Science
Course
CS 447
Professor
Lin Tan
Semester
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

OR

Don't have an account?

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.