An incorrect internal state that is the manifestation of some fault.
Failure:
External, incorrect behavior with respect to the requirements or other description of the expected behavior.
PIE
Execution/Reachability:
The location or locations in the program that contain the fault must be reached.
Infection:
The state of the program must be incorrect.
Propagation:
The infected state must propagate to cause some output of the program to be incorrect.
White-Box Testing
Graphs in Testing
Software testing is just convert the software into a graph, and then cover it.
Test Path:
A path that starts at an initial vertex and ends at a final vertex.
Represent execution of test cases.
Some test paths can be executed by many tests, and some test paths cannot be executed by any tests.
Graph Coverage Criteria
Reach:
Syntactic reach: A path exists in the graph.
Semantic reach: A test exists that can execute that path.
Cover:
A test path p covers a vertex v if v is in p.
A test path p covers an edge e if e is in p.
A test path p covers a sub path p' if p' is in p.
We use graphs in testing as follows:
Developing a model of the software as a graph.
Requiring test to cover specific sets of vertexes, edges or sub_paths.
Types of common graph coverage method:
Structural Coverage:
Defined on a graph just in terms of vertexes and edges.
Data Flow Coverage:
Requires a graph to be annotated with references to variables.
Testing Criteria:
Test Requirements(TR):
Describe properties of test paths
Test Criterion:
Rules that define TR.
Satisfaction:
Given a set TR of test requirements for a criterion C, a set of tests T satisfies C on a graph if and only if for every test requirement in TR, there is a test path in path(T) that meets the test requirement tr.
Structural Coverage
Vertex Courage(VC)
Test set T satisfies vertex coverage on graph G if and only if for every syntactically reachable vertex v in V, there is a path p in path(T) such that p covers v.
TR contains each reachable vertex in G.
Edge Courage(EC)
Test set T satisfies edge coverage on graph G if and only if for every syntactically reachable edge e in E, there is a path p in path(T) such that p covers e.
TR contains each reachable edge in G.
Connection between VC and EC
If EC is satisfied, then VC is.
But VC does not indicate EC.
Covering Multiple Edges
Edge-pair coverage(EPC): TR contains each reachable path of length to up 2, inclusive, in G.
Complete Path Coverage(CPC): TR contains all paths in G.
n Path Coverage(nPC): TR contains each reachable path of length up to n, inclusive, in G.
Thus VC(n = 0), EC(n = 1), EPC(n = 2), CPC(n = infinite) are all nPCs.
Subsume:
C1 subsumes C2, denoted by C1 >= C2: For any T, if T satisfies C1 implies T satisfies C2.
Thus n1PC >= n2PC, if n1 >= n2.
C1 >= C2 does not imply that T1 satisfying C1 can detect any fault detected by T2 which satisfies C2.
Control Flow Graph
A control flow graph(CFG) is a representation, using graph notation, of all paths that might be traversed through a program during its execution.
Vertex:
Statement
Block
Function
Module
Edge:
Flow
Jump
Call
Data Flow Coverage
Data Flow
Beyond structure
Goal: Try to ensure that values are computed and used correctly
Definition(def): A location where a value for a variable is stored into memory.
Use: A location where a variable's value is accessed.
Sets of Def and Use
def(n) or def(e): The set of variables that are defined by node n or edge e.
use(n) or use(e): The set of variables that used by node n or edge e.
DU Pair
A pair of locations(li, lj) such that a variable v is defined at li and used at lj
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
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
du-path: A simple sub_path that is def-clear with respect to v from a def of v to a use of v
du(ni, nj, v): the set of du-paths from ni to nj
du(ni, v): the set of du-paths that start at ni
Data Flow Coverage Criteria
All-defs coverage(ADC): For each set of du-paths S = du(n, v), TR contains at least one path d in S.
All-uses coverage(AUC): For each set of du-paths to uses S = du(ni, nj, v), TR contains at least one path d in S.
All-du-paths coverage(ADUPC): For each set S = du(ni, nj, v), TR contains every path d in S.
Black-Box Testing
Random Testing
Test cases are generated purely at random
Input domain must be known
Pick random points within input domain
Automation
Problems in Random Testing(RT)
Define input domain
Generate random sequence
Pseudo random sequence algorithm
Seed of pseudo random sequence algorithm
Randomness and Integrity Service(random.org)
Ruzz testing
Usually used in security
A special form of random testing, aims to breaking the software
Providing invalid, unexpected, or random data to the inputs of a program
Adaptive RT(ART)
Impact of the compactness of failure regions on the performance of rt may be the shape of block, strip, or points.
A passed test may be near with tests that passed. A failed test may be surrounded with tests that failed.
So select test cases far away from others
FSCS-ART algorithm
randomly generate an input t, run t, and t to T
while (stop criteria not reached)
randomly generate k candidate input c1, ... ck
for each candidate ci, compute min distance di to T
select on candidate t with max distance
run t, and t to T
Anti-Random Testing
To test the program when the input domain is discrete
Process:
Select one test case randomly
Select a test case with the maximum sum of hamming distance to existed test cases
Repeat...
Equivalence Partition
Equivalence partition
Can be equally applied at several levels of testing:
Unit
Integration
System
Relatively easy to apply with no automation
Easy to adjust the procedure to get more or fewer tests
Partitioning Domains
Domain D
Partition scheme p of D
The partition p defines a set of blocks b1, b2, ...bn
The partition must satisfy two properties:
blocks must be pairwise disjoint (no overlap)
together the blocks cover the domain D (complete)
Two Approaches:
Interface-based approach
Develops characteristics directly from individual input parameters
Simplest application
Can be partially automated in some situations
Functionality-based approach
Develops characteristics from a behavioral view of the program under test
Hard to develop--requires more design effort
May result in better tests, or fewer tests that are effective
Interface-based approach
Mechanically consider each parameter in isolation
This is an easy modeling technique and relies mostly on syntax
Ignores relationships among parameters
Functionality-based approach
Identify characteristics that correspond to the intended functionality
Requires more design effort from tester
Can incorporate domain and semantic knowledge
Can use relationships among parameters
Modeling can be based on requirements, not implementation
The same parameter may appear in multiple characteristics, so it's harder to translate values to test cases
Combinatorial Testing
Fixed strength combinatorial testing
Pair-wise testing
T-way combinatorial testing
Variable strength combinatorial testing
Key issue
Sampling in all combinations
Do not consider special information of inputs
Functional Testing
Brief
Functional testing is a quality assurance (QA) process and a type of black-box testing that bases its test cases on the specifications of the software component under test.
Functions are tested by feeding them input and examining the output, and internal program structure is rarely considered (unlike white-box testing).
Functional testing usually describes what the system does.
General steps:
Segment function points according to requirements
Deriving test requirements based on function points
Design functional test cases based on test requirements
Executing functional test case one by one to validation products