Psst.. new poll here.
Psst.. new forums here.
Microsoft is blocking us again (TY IP Reputation!) so just use oauth login instead. :)
Paste
Pasted as Plain Text by registered user ragav132 ( 11 years ago )
cyclomatic complexity
Theory:
Control flow graph:
Control flow graphs describe the logic structure of software modules. A module
corresponds to a single function or subroutine in typical languages, has a single entry
and exit point, and is able to be used as a design component via a call/return
mechanism. This document uses C as the language for examples, and in C a module
is a function. Each flow graph consists of nodes and edges. The nodes represent
computational statements or expressions, and the edges represent transfer of control
between nodes.
Each possible execution path of a software module has a corresponding path from the
entry to the exit node of the module’s control flow graph. This correspondence is the
foundation for the structured testing methodology.
Definition of cyclomatic complexity, v(G)
Cyclomatic complexity is defined for each module to be e - n + 2, where e and n are
the number of edges and nodes in the control flow graph, respectively. Cyclomatic
complexity is also known as v(G), where v refers to the cyclomatic number in graph
theory and G indicates that the complexity is a function of the graph. The word
“cyclomatic” comes from the number of fundamental (or basic) cycles in connected,
undirected graphs. More importantly, it also gives the number of independent paths
through strongly connected directed graphs. A strongly connected graph is one in
which each node can be reached from any other node by following directed edges in
the graph. The cyclomatic number in graph theory is defined as e - n + 1. Program
control flow graphs are not strongly connected, but they become strongly connected
when a “virtual edge” is added connecting the exit node to the entry node. The
cyclomatic complexity definition for program control flow graphs is derived from the
cyclomatic number formula by simply adding one to represent the contribution of the
virtual edge. This definition makes the cyclomatic complexity equal the number of
independent paths through the standard control flow graph model, and avoids explicit
mention of the virtual edge.
Characterization of v(G) using a basis set of control flow paths:
Cyclomatic complexity can be characterized as the number of elements of a basis set
of control flow paths through the module. Some familiarity with linear algebra is
required to follow the details, but the point is that cyclomatic complexity is precisely
the minimum number of paths that can, in (linear) combination, generate all possible
paths through the module. To see this, consider the following mathematical model,
which gives a vector space corresponding to each flow graph.
Each path has an associated row vector, with the elements corresponding to edges in
the flow graph. The value of each element is the number of times the edge is traversed
by the path.
Considering a set of several paths gives a matrix in which the columns correspond to
edges and the rows correspond to paths. From linear algebra, it is known that each
matrix has a unique rank (number of linearly independent rows) that is less than or
equal to the number of columns. This means that no matter how many of the
(potentially infinite) number of possible paths are added to the matrix, the rank can
never exceed the number of edges in the graph. In fact, the maximum value of this
rank is exactly the cyclomatic complexity of the graph. A minimal set of vectors (paths)
with maximum rank is known as a basis, and a basis can also be described as a
linearly independent set of vectors that generate all vectors in the space by linear
combination. This means that the cyclomatic complexity is the number of paths in any
independent set of paths that generate all possible paths by linear combination.
Given any set of paths, it is possible to determine the rank by doing Gaussian
Elimination on the associated matrix. The rank is the number of non-zero rows once
elimination is complete.
If no rows are driven to zero during elimination, the original paths are linearly
independent. If the rank equals the cyclomatic complexity, the original set of paths
generate all paths by linear combination. If both conditions hold, the original set of
paths are a basis for the flow graph. There are a few important points to note about
the linear algebra of control flow paths. First, although every path has a corresponding
vector, not every vector has a corresponding path.
This is obvious, for example, for a vector that has a zero value for all elements
corresponding to edges out of the module entry node but has a nonzero value for any
other element cannot correspond to any path. Slightly less obvious, but also true, is
that linear combinations of vectors that correspond to actual paths may be vectors that
do not correspond to actual paths.
This follows from the non-obvious fact (shown in section 6) that it is always possible
to construct a basis consisting of vectors that correspond to actual paths, so any vector
can be generated from vectors corresponding to actual paths. This means that one
can not just find a basis set of vectors by algebraic methods and expect them to
correspond to paths—one must use a path-oriented technique such as that of section
6 to get a basis set of paths. Finally, there are a potentially infinite number of basis
sets of paths for a given module. Each basis set has the same number of paths in it
(the cyclomatic complexity), but there is no limit to the number of different sets of basis
paths. For example, it is possible to start with any path and construct a basis that
contains it.
The details of the theory behind cyclomatic complexity are too mathematically
complicated to be used directly during software development. However, the good
news is that this mathematical insight yields an effective operational testing method in
which a concrete basis set of paths is tested: structured testing.
dataflow testing
Title: Data Flow Testing
For the above function, draw the following tables and write the test cases:
a. Occurrence of variables and their categories.
b. du pairs and their type
c. All c-uses
d. All p-uses
Theory:
Data flow testing is a structural testing technique that
• Aims to execute sub-paths from points where each variable is defined to
points where it is referenced
• These sub-paths are called definition-use pairs or du-pairs (du-paths, du-
chains)
• Data flow testing is centred on variables (data)
Most failures involve execution of an incorrect definition
– Incorrect assignment or input statement
– Incorrect path is taken, which leads to incorrect definition (predicate is faulty)
– Definition is missing (i.e. null definition)
Data flow testing follows the sequences of events related to a given data item with
the objective to detect incorrect sequences. It explores the effect of using the value
produced by each and every computation.
Terminology:
• Variable definition
Occurrences of a variable where a variable is given a new value (assignment,
input by the user, input from a file, etc.)
Variable DECLARATION is NOT its definition !!!
• Variable uses
Occurrences of a variable where a variable is not given a new value (variable
DECLARATION is NOT its use)
– p-uses (predicate uses)
Occur in the predicate portion of a decision statement such as if-then-else,
while-do etc.
– c-uses (computation uses)
All others, including variable occurrences in the right hand side of an
assignment statement, or an output statement
– du-path
A sub-path from a variable definition to its use
Data Flow testing
• Checks the correctness of the du-paths in a Control
– Flow Graph of a program
–
• Test case definitions based on four groups of coverage
– All definitions
– All c-uses
– All p-uses
– All du-paths
Data Flow testing: key steps
Given a code (program or pseudo-code)
1. Number the lines
2. List the variables
3. List occurrences & assign a category to each variable
4. Identify du-pairs and their use (p- or c- )
5. Define test cases, depending on the required coverage
Solution:
Step 1: Number the lines:
0 void quad_eqn (float A,B,C, Boolean Is_Complex)
1 { float Discrim = B*B-4*A*C
2 float R1,R2;
3 {
4 If Discrim<0.0
5 Is_Complex=true;
6 Else
7 Is_Complex=false
8 Endif;
9 If not Is_Complex
10 R1=(-B+Sqrt(Discrim))/(2.0*A);
11 R2=(-B-Sqrt(Discrim))/(2.0*A);
12 Endif;
13 End quad_eqn;}
14 }
Step 2: List the variables:
– A, B, C
– DISCRIM
– Is_Complex
– R1, R2
Step 3: List occurrences and assign a category to each variable
Line No Category
Definition c-use p-use
0 A,B,C
1 DISCRIM A,B,C
2
3
4 DISCRIM
5 Is_Complex
6
7 Is_Complex
8
9 Is_Complex
10 R1 A,B,DISCRIM
11 R2 A,B,DISCRIM
12
13
14
Step 4: Identify du-pairs and their use (p- or c- )
Definition – use pair Variables
Start line ? end line c-use p-use
0 ? 1 A,B,C
0 ? 10 A,B
0 ? 11 A,B
1 ? 4 DISCRIM
1 ? 10 DISCRIM
1 ? 11 DISCRIM
5 ? 9 Is_Complex
7 ? 9 Is_Complex
10 ? 14 R1
11 ? 14 R2
Step 5: Define Test Cases:
D c- Variables Subpaths Test Inputs Is_Co R1 R2
use Case mplex
pairs
A B C
0?1 A,B,C 0-1 1 1 1 1 T . .
0?10 A,B 0-1-2-3-4-6-7-8-9-10 2 1 2 1 F -1 -1
0-11 A,B 0-1-2-3-4-6-7-8-9- 3 1 2 1 F -1 -1
10-11
1-10 DISCRIM 1-2-3-4-6-7-8-9-10 4 1 2 1 F -1 -1
1-11 DISCRIM 1-2-3-4-6-7-8-9-10- 5 1 2 1 F -1 -1
11
5-14 Is_Complex 5-8-9-12-13-14 6 1 1 1 T . .
7-14 Is_Complex 7-8-9-10-11-12-13- 7 1 2 1 F -1 -1
14
10-14 R1 10-11-12-13-14 8 1 2 1 F -1 -1
11-14 R2 11-12-13-14 9 1 2 1 F -1 -1
d p-use Variable Subpaths Test Inputs Is_Co R1 R2
pairs s Case mplex
A B C
1-(4-5) Discrim 1-2-3-4-5 10 1 1 1 T . .
1-(4-6) Discrim 1-2-3-4-6 11 1 2 1 F -1 -1
5-(9-12) Is_Comp 5-8-9-12 12 1 1 1 T . .
lex
7-(9-10) Is_Comp 7-8-9-10 13 1 2 1 F -1 -1
lex
Conclusion:
13 test cases were designed for data flow testing.
Title: Branch – Decision – Condition Coverage
Problem Statement:
For the following liability procedure, design test cases using branch, condition,
decision and multiple decision coverage.
Procedure Liability(Age,Gender, Married,Premium)
Begin
Premium:=500;
If(Age<25) and (Gender=Male) and (not Married) Then
Premium=Premium+1500;
Else (if (Married or Gender=Female)) Then
Premium=Premium-200;
if (Age>45) and (Age<65) Then
Premium=Premium-100;
End;
Theory:
Statement Coverage:
Statement coverage is achieved when the condition becomes either true or false. The
objective of statement coverage is that all the statements in the program should be
executed at least once. The statement coverage is necessary but not sufficient.
Branch or decision coverage:
Statement coverage does not address all the outcome of the decisions. Branches like
if … else, while …, for, do … while are to be evaluated for both true and false.
Each branch direction must be traversed at least once.
Condition/Decision Coverage:
Branch coverage considers entire Boolean expression as one and tests for true and
false. It ignores branches within Boolean expressions occurring due to relational and
logical operators. All conditions should be executed at least once for true and false.
Conditions using relational and logical operators should be checked for all possible
outcomes. Condition coverage checks for true and false outcome of each Boolean sub
expressions.
Multiple condition coverage:
Multiple condition coverage checks whether every possible combination of Boolean
sub expression occurs at least once. Test cases required for full multiple condition
coverage can be arrived at by using truth table of conditions.
A large number of test cases may be required for full multiple conditio n coverage.
Solution:
Branch or decision coverage:
Decision Age Gender Married Test Case
Coverage
IF-1 <25 Male False (1) 23, M F
IF-1 <25 Female False (2) 23, F F
IF-2 * Female * (2)
IF-2 >=25 Male False (3) 50 M F
IF-3 <=45 Female * (2)
IF-3 >45, <65 * * (3)
14
----------------------- Page 15-----------------------
Software Testing
Condition Coverage:
Condition Age Gender Married Test Case
Coverage
IF-1 <25 Female False (1) 23, F F
IF-1 >=25 Male True (2) 30 M T
IF-2 * Male True (2)
IF-3 <=45 * * (1)
IF-3 >45 * * (3) 70 F F
IF-3 <65 * * (2)
IF-3 >=65 * * (3)
Decision/Condition Coverage
Decision/Condition Age Gender Married Test Case
Coverage
IF-1 (Decision) <25 Male False (1) 23 M F
IF-1 (Decision) <25 Female False (2) 23 F F
IF-1 (Condition) <25 Female False (2)
IF-1 (Condition) >=25 Male True (3) 70 M T
IF-2 (Decision) * Female * (2)
IF-2 (Decision) >=25 Male False (4) 50 M F
IF-2 (Condition) * Male True (3)
IF-2 (Condition) * Female False (2)
IF-3 (Decision) <=45 * * (2)
IF-3 (Decision) >45, <65 * * (4)
IF-3 (Condition) <=45 * * (2)
IF-3 (Condition) >45 * * (4)
IF-3 (Condition) <65 * * (4)
IF-3 (Condition) >=65 * * (3)
Multiple Condition Coverage:
Decision/Condition Age Gender Married Test Case
Coverage
IF-1 <25 Male True (1)
IF-1 <25 Male False (2)
IF-1 <25 Female True (3)
IF-1 <25 Female False (4)
IF-1 >=25 Male True (5)
IF-1 >=25 Male False (6)
IF-1 >=25 Female True (7)
IF-1 >=25 Female False (8)
IF-2 * Male True (5)
IF-2 * Male False (6)
IF-2 * Female True (7)
IF-2 * Female False (8)
IF-3 <=45, >=65 * * Impossible
IF-3 <=45, <65 * * (8)
IF-3 >45,>65 * * (6)
IF-3 >45,<65 * * (7)
Conclusion:
All the types of test cases are designed for testing.
• Equivalence partitioning:
Equivalence partitioning (EP) is a good all-round specification-based black-
box technique. It can be applied at any level of testing and is often a good
technique to use first. It is a common sense approach to testing, so much so
that most testers practise it informally even though they may not realize it.
The idea behind the technique is to divide (i.e. to partition) a set of test
conditions into groups or sets that can be considered the same (i.e. the system
should handle them equivalently), hence 'equivalence partitioning'.
Equivalence partitions are also known as equivalence classes - the two terms
mean exactly the same thing.
The equivalence-partitioning technique then requires that we need test only one
condition from each partition. This is because we are assuming that all the
conditions in one partition will be treated in the same way by the software. If
one condition in a partition works, we assume all of the conditions in that
partition will work, and so there is little point in testing any of these others.
Conversely, if one of the conditions in a partition does not work, then we
assume that none of the conditions in that partition will work so again there is
little point in testing any more in that partition. Of course these are simplifying
assumptions that may not always be right but if we write them down, at least it
gives other people the chance to challenge the assumptions we have made
and hopefully help to identify better partitions.
• Boundary value analysis;
Boundary value analysis (BVA) is based on testing at the boundaries
between partitions. If you have ever done 'range checking', you were probably
using the boundary value analysis technique, even if you weren't aware of it.
Note that we have both valid boundaries (in the valid partitions) and invalid
boundaries (in the invalid partitions).
• Decision tables;
• State transition testing.
Revise this Paste