1
Q
What is a control-flow graph?
A
Flow chart
- Directed graph
- Nodes are blocks of sequential statements
- Edges are transfers of control & may be labelled with predicate repping condition of control transfer
- Several conventions for these models with slight diffs e.g. hierarchical & concurrent)
- Blocks include if-then-else, while loops & switches
- UML activity diagrams can also be used to model CFGs
2
Q
What is the subsumption hierarchy?
A
All-Coupling-Paths → All-Coupling-Uses → All-Coupling-Defs → Call Coupling
3
Q
What is Integration test coverage criteria?
A
- Call-coupling - requires execution of all call sites in caller
- All-coupling-defs - requires that for each coupling def (last-def), min 1 coupling path to min 1 reachable coupling
use (first-use) executed - all-coupling-use - requires that for each coupling def (last-def), min 1 coupling path to each reachable coupling use executed
- all-coupling-paths - requires all loop-free coupling paths executed
4
Q
What is a coupling du-path?
A
Path from last-def to first-use across 2 units (caller & callee)
5
Q
What is the mutation coverage/score?
A
- Complete coverage kills all non-equiv mutants
- Each mutation is test req
- Num mutants depend on def on mutation operators & syntax/structure of software
- Num muntants tend to be large so may need random sampling
6
Q
What are the types of mutant?
A
Stillborn, trivial and equivalent
Only mutants which behave differently to og program with no test cases to ID them are interesting
7
Q
Stillborn mutant
A
Syntactically incorrect, killed by compiler
8
Q
Trivial mutant
A
Killed by almost any test case
9
Q
Equivalent mutant
A
Always acts in same behaviour as og program
10
Q
What are the types of control-flow coverage?
A
Statement, decision, condition and path
11
Q
Statement control-flow coverage
A
Same as =Node =Line
- Hypothesis/motivation for coverage criterion: Faults can’t be discovered if parts containing them not executed
- Statement coverage criterion: Equiv to covering all nodes in CFG
- Executing statement (code line) is weak guarantee of correctness but easy to achieve
- Several statements can execute same statements
- Can help with detecting certain types of detects but may lead to incompleteness
12
Q
Decision control-flow coverage
A
- (=Edge =Branch)
- Based on program structure (CFG)
- Edge coverage criterion: Select test T such that by executing program under test P for each case t in T, each edge of P’s CFG traversed min 1x
- Must exercise all decisions that traverse Control flow of program with true/false values
13
Q
Condition control-flow coverage
A
- Further strengthens edge coverage
- Condition coverage criterion:Derive/design test set T such that by executing program under test P for each element in T, each edge of P’s CFG traversed & all poss values of constituents of compound conditions as exercise min 1x
- Compound (composite) conditions: c1 & c2 or c3 where Ci’s relational expressions/boolean vars (atomic conditions)
14
Q
Modified condition-decision coverage
A
- Only combos of values such that every atomic condition (consituent) Ci drives overall condition truth values x2 (true & false)
- To get test suite, take pair for each constituent & 2 min sets to satisfy them.
15
Q
Path control-flow coverage
A
- Path coverage criterion: Select test set T such that by executing P for each test case t in T, all paths leading from initial to final node of P’s CFG traversed
- Num paths too large, if not infinite, some paths being infeasible and sometimes important to determine critical paths leading to more system load etc
- To tackle this, look for conditions executing loops 0 times, a max num times or an average num times
16
Q
What are the 3 types of coupling between units?
A
Parameter, shared data (non-local vars) and external resource device) couple (refs of several modules to same external resource)
17
Q
Call sites
A
statements in caller (A) where callee (B) invoked
18
Q
Last defs
A
Set of nodes (in CFGs) that define x (var) for
which there’s def-clear path from node through call site or return to use in caller
19
Q
First uses
A
Set of nodes (in CFGs) that “use” x & for which
there exists def-clear path between call site (if use is in caller) or callee entry point (if use in callee)
20
Q
Coupling-Based Criteria
A
- Integration testing of units/modules assures they have consistent assumptions & comm correctly.
- Coupling between 2 units measures dependency
relations between them by reflecting interconnections between units; faults in 1 unit may affect coupled unit - Each module to be integrated should have passed isolated/unit test
- Must be performed at higher abstraction level - looking at program as atomic building blocks & focusing on interconnections
- Goal is to guide testers during integration testing, help define criterion to determine when to stop
integration testing (when given coupling coverage reached)
21
Q
Definitions in coupling-based criteria
A
- Interface between 2 units is mapping of actual to formal
parameters - Formal param is identifier used in method to stand for value that’s passed into method by caller.
- Actual param is actual value passed into method by caller
- When method called, formal param temporarily bound to actual param
- Data-flow conns between units often complex so rich source of faults
- During integration testing, look at defs &
uses across diff units - To increase confidence in interfaces, ensure vars defined in caller units appropriately used in
callee (called) units - Look at var defs before calls & return to other units, & uses of vars just after calls & after returns from called unit
- Vars defined in 1 unit & used in other as coupling vars
22
Q
Comparison criteria
A
- Num stubs & drivers needed
- Time to working/demonstrable system
- Integration start time (early as poss)
- Ability to test paths (ensure path coverage of components)
- Ability to plan & control
23
Q
Sandwich
A
- Choose target layer
- Top-down approach used in top layers & bottom in lower layers or vice versa
- Allows testing of general purpose utilities correctness at start
- No need for stubs for utilities (challenging)
- Allows integration testing of top components to start early - tests control, GUI & key units early
- Test drivers at top layer unnecessary
- May not test thoroughly indiv units of target layer, must be done separately
- Early integration start, early time to working system, drivers & stubs required, medium difficulty to test paths & hard to plan & control.
24
Q
Top-down
A
- Reverse of bottom-up
- When units not yet tested are needed, must use stubs simulating activity of missing units
- Provides early working prototype
- Dev of lower level units deferred
- Reusable test cases as integration goes on so better regression testing
- Driver programs unnecessary, but stubs time consuming & error prone
- Writing stubs may be complex & correctness affects test validity
- Inadequate if low level unit specs unstable
- Early integration start, early time to working system, no drivers, stubs require, hard to test paths & hard to plan & control.
25
Bottom-up
- Design based on fundamental decomposition
- Each component at lowest of hierarchy tested 1st
- Can help fault localisation
- Helps us isolate/localise faults more easily, esp interface faults
- Convenient when many general purpose utility routines invoked by units at low levels
- Top-level units may be more important but tested last
- Faults in top level sometimes reflect faults in design/architecture and must be corrected early
- Early integration start, late time to working system, drivers required, no stubs, easy to test paths & easy to plan & control.
26
What are the 3 approaches to incremental integration testing?
Bottom-up, top-down and sandwich
27
What are the 2 approaches to integration testing?
Big-bang/all at once and incremental
28
Big bang approach to integration testing
- All components brought together at once into system & tested as entire system
- Difficult to find root cause of failure
- Must wait for all components to be ready so not usually recommended
- Late integration start, late time to working system, no drivers or stubs, hard to test paths & easy to plan & control.
29
Integration testing
Background:When components (modules/units) tested to satisfactory level, integrate/combine them into working systems
- When system integrated, can still observe fault originating from components integration/interfaces with each other
-Systematic Testing Principle: Integration testing should be systematic & planned so when failure occurs, we have an idea of its cause
- Reality: Development not usually sequential but activities overlapping, some components may be in coding, unit & integration testing
- Impacts: Integration strategy affects order of coding, unit testing & cost & thoroughness of testing
- Dependency/call graphs used to find procedures never called (dead calls) & act as doc to understand programs & base further analysis
30
What are the assumptions made in mutant testing?
Competent programmer (program nearly correct) and coupling effect whereby test cases that distinguish programs differing from correct by simple errors are so sensitive they'd distinguish complex errors
31
Mutation operators
Predefined program modification rules for automated generation of mutants
- Variable replacements
- Relational operator replacement
- Off-by-1 Mutation
- Replacement by 0
- Arithmetic Operator Replacement
- Constant replacement
- Scalar variable replacement
- Scalar variable for constant
replacement
- Constant for scalar variable
replacement
- Array reference for constant
replacement
- Array reference for scalar variable
replacement
- Constant for array reference
replacement
- Scalar variable for array reference
replacement
- Array reference for array
reference replacement
- Source constant replacement
- Data statement alteration
- Comparable array name
replacement
- Arithmetic operator replacement
- Relational operator replacement
- Logical connector replacement
- Absolute value insertion
- Unary operator insertion
- Statement deletion
- Return statement replacement
32
Mutation testing
-Fault-Based Testing: Directed towards typical faults that could occur in program
- Syntactic variations applied in systematic way to program to create faulty versions exhibiting diff behaviour (each version called mutant)
- Mutation testing helps user create effective test data in interactive manner
- Goal is to have strong/effective test suite to catch typical future faults, seeding bugs to find bugs
- Measures quality of test cases & provides tester with clear target (mutants to kill)
- Forces programmer to inspect code & consider test data that will expose certain kinds of faults
- Computationally intensive & can be used in diff testing levels in addition to unit testing
33
Process of mutation testing
- Take program & test suite generated for program using other test techniques
- Create num of mutant programs, each differing slightly e.g. x=a+b → x=a-b
- OG test suite run on mutants
- If any test case fails on given mutant, mutant is dead/killed
- If all mutants killed, test suite considered adequate
- Mutant remains live if test set inadequate to kill it or because it’s equiv to OG program
- If test suite inadequate, test data must be augmented by adding extra test cases
34
Analysis of coverage data
- Coverage criteria performs better than random test selection
- Signif improvements occur as coverage increases (esp 90-100%)
- 100% coverage isn’t a reliable indicator of test set effectiveness, especially for edge coverage
- Wide variation in test effectiveness for given criteria
35
Control-flow
- Result of if/while statements
- Dominant q is how focus of controls moves through program execution
- Refers to paths execution of program takes
36
Data flow
- How vars transfer values among each other
- Impacted by control flow
- Dominant q is how data moves through serious of atomic computational (in each line of code) along execution paths
- As data moves, control & computation activated
- Reasoning is about data transformation & their flow
- Abstracts over explicit control flow by placing emphasis on routing & transformation of data
37
all-DU-Paths criterion
Test set T satisfies all-DUPaths criterion for program P iff for every var v e V, T contains all def-clear paths from every defining node of v to every reachable use of v & that these paths are
either single loops traversals, or cycle free.
38
all-C-Uses/Some-P-Uses criterion
Test set T satisfies all-C-Uses/Some P-Uses criterion for program P iff for every var v e V, T contains min 1 def-clear path from every defining node of v to every computation use of v, & if def of v has 0 C-Uses, there’s def-clear path to min 1 pred use.
39
all-P-Uses/Some-C-Uses criterion
Test set T satisfies all-P-Uses/Some C-Uses criterion for program P iff for every var v e V, T contains at min 1 def-clear path from every defining node of v to every pred use of v & if def of v has 0 P-Uses, there’s def-clear path to at min 1 computation use.
40
all-Uses criterion
Test set T satisfies all-Uses
criterion for program P iff (if & only if) for every var v e V, T contains min 1 def-clear path from
every defining node of v to every reachable use of v.
41
all-Definitions criterion
Test set T satisfies all-
Definitions criterion for program P iff (if & only if) for every var v e V, T contains def-clear paths from every defining node of v to at least a use of v.
42
Definition/Defining Node
Node n e CFG(P) is defining node of var v e V written as DEF(v,n), iff (if & if only) value of var v defined in statement corres to node n
43
Usage/Use Node
Node n e CFG(P) is usage node of var v e V written as USE(v,n), iff value of var v used in statement corres to node n
44
Predicate and Computation Use
Usage node USE(v,n) is predicate use (denoted as P-Use) iff statement n is pred statement, otherwise USE(v,n) is computation use (denoted as C-use)
45
Definition-Use (def-use/du-path)
With respect to var v (denoted du-path) is path in PATHS(P) such that for some v e V, there are define & usage nodes DEF(v,m) & USE(v,n) such that m & n are initial & final path nodes
46
PATHS(P)
Set of all CFGs in program P
47
Definition-Clear (DC)-Path
With respect to var v is definition-use path in PATH(P) with initial & final nodes DEF(v,m) & USE(v,n) such that no other node in path is defining node of v
48
Definition Occurrence
Value written/bound to var e.g. a=5
49
Use Occurrence
Value of var read/used
50
Computational
Compute value for defining other vars/output values e.g. b=a+7
51
Predicate Use
Var used to decide whether predicate is true/false e.g. if (a<11)
52
Data-Flow Coverage
- Focus on paths CFG takes that are signif for data flow in program
- Focus on assignment of values to vars & uses
- Want to analyse occurrences of values
- Generate test data according to way data manipulated in program
- Can help us definite intermediary coverage criteria between all-lines testing (poss too weak) & all-paths testing (often imposs)
Software Testing
flashcards
Decks in class (3)
# Cards
