CHAPTER – 4
CONTROL FLOW TESTING
2
OUTLINE OF THE CHAPTER
Basic Idea
Outline of Control Flow
Testing
Control Flow Graph
Paths in a Control Flow Graph
Path Selection Criteria
Generating Test Input
Containing Infeasible Paths
Summary
3
Two kinds of basic program
statements:
Assignment statements (Ex. x = 2*y; )
Conditional statements (Ex. if(), for(),
while(), …)
Control flow
Successive execution of program
statements is viewed as flow of control.
Conditional statements alter the default
flow.
Program path
A program path is a sequence of
statements from entry to exit.
There can be a large number of paths in a
program.
There is an (input, expected output) pair
for each path.
Executing a path requires invoking the
program unit with the right test input.
BASIC IDEA
Paths are chosen by using the concepts of
path selection criteria.
Tools: Automatically generate test
inputs from program paths.
OUTLINE OF CONTROL FLOW
TESTING
Figure 1: The process of generating test input data for control flow testing. 4
5
Inputs to the test generation
OUTLINE OF CONTROL FLOW
process
Source code
Path selection criteria: statement, branch,
…
Generation of control flow graph
(CFG)
A CFG is a graphical representation of a
program unit.
Compilers are modified to produce CFGs.
(You can draw one by hand.)
Selection of paths
Enough entry/exit paths are selected to
satisfy path selection criteria.
Generation of test input data
Two kinds of paths
Executable path: There exists input so that the path is
executed.
Infeasible path: There is no input to execute the path.
Solve the path conditions to produce test
input for each path.
TESTING
6
CONTROL FLOW GRAPH
Figure 2: Symbols in a
control flow graph
CONTROL FLOW GRAPH
7
8
CONTROL FLOW GRAPH
Figure 3: A high-level CFG
representation of openfiles().
9
CONTROL FLOW GRAPH
Figure 4: A detailed CFG
representation of openfiles().
CONTROL FLOW GRAPH
10
11
Figure 5: A CFG representation of
ReturnAverage().
FLOW GRAPH
CONTROL
12
A path is represented as a
sequence of computation and
PATHS IN A CONTROL FLOW
decision nodes from the entry
node to the exit node.
A few paths in Figure 5
Path 1: 1-2-3(F)-10(T)-12-13
Path 2: 1-2-3(F)-10(F)-11-13
Path 3: 1-2-3(T)-4(T)-5-6(T)-7(T)-8-9-
3(F)-10(T)-12-13
Path 4: 1-2-3(T)-4(T)-5-6-7(T)-8-9-
3(T)-4(T)-5-6(T)-7(T)-8-9-3(F)-10(T)-
12-13
GRAPH
13
Program paths are selectively
executed.
Question: What paths do I select
PATH SELECTION CRITERIA
for testing?
The concept of path selection
criteria is used to answer the
question.
Advantages of selecting paths
based on defined criteria:
Ensure that all program constructs are
executed at least once.
Repeated selection of the same path is
avoided.
One can easily identify what features
have been tested and what not.
Path selection criteria
Select all paths.
Select paths to achieve complete
statement coverage.
Select paths to achieve complete branch
coverage.
Select paths to achieve predicate
coverage.
PATH SELECTION CRITERIA
consideration.
under
the program unit
all the paths in
criterion: Select
coverage
All-path
paths.
all the program
inputs will exercise
unit has 25+ paths.
Selecting all the
The openfiles()
Existence of Existence of Existence of
“file1” “file2” “file3”
No No No
No No Yes
No Yes No
No Yes Yes
Yes No No
Yes No Yes
Yes Yes No
Yes Yes Yes
Table 1: Input Domain of openfiles()
14
Table 2: Inputs and paths in openfiles()
PATH SELECTION CRITERIA
Input Path
<No, No, No> 1-2-3(F)-8-9(F)-14-15(F)-19-21
<Yes, No, No> 1-2-3(T)-4(F)-6-8-9(F)-14-15(F)-19-21
<Yes, Yes, Yes> 1-2-3(T)-4(F)-6-8-9(T)-10(T)-11-13(F)-14- 15(T) -
16(T)-18-20-21
15
16
PATH SELECTION CRITERIA
Statement coverage criterion
Statement here means node.
Statement coverage means executing
individual program statements and observing
the output.
1-2-3(T)-4(T)-5-6(T)-7(T)-8-9-3(F)-10(T)-12-13
100% statement coverage means all the
statements have been executed at least once.
Cover all assignment statements.
Cover all conditional statements.
Less than 100% statement coverage is
unacceptable.
1-2-3(F)-10(F)-11-13
Table 3: Paths for statement
coverage of the CFG of Figure 5.
SCPath1
SCPath2
17
Branch coverage criterion
A branch is an outgoing
edge from a node in a
PATH SELECTION CRITERIA
CFG.
A condition node has
two outgoing branches
– corresponding to the
True and False values of
the condition.
Covering a branch
means executing a path
that contains the branch.
Complete branch
coverage means
selecting a number
of paths such that
every branch is
included in at least
one path.
PATH COVERAGE
Ensures all independent paths in the CFG are executed at least
once.
Basis Path Testing (Cyclomatic Complexity-based)
•A white-box testing technique based on executing a set of linearly
independent paths.
•Uses Cyclomatic Complexity to determine the minimum
number of test paths needed.
PATH SELECTION CRITERIA
Figure 6: The dotted arrows represent the branches not
covered
by the statement covering in Table 3. 19
PATH SELECTION CRITERIA
Table 4: Paths for branch coverage of
BCPath 1 1-2-3(F)-10(F)-11-13
BCPath 2 1-2-3(T)-4(T)-5-6(T)-7(T)-8-9-3(F)-10(T)-12-13
the flow graph of Figure 5
BCPath 3 1-2-3(T)-4(F)-10(F)-11-13
BCPath 4 1-2-3(T)-4(T)-5-6(F)-9-3(F)-10(F)-11-13
BCPath 5 1-2-3(T)-4(T)-5-6(T)-7(F)-9-3(F)-10(F)-11-13
20
Figure 7: Partial control flow graph with (a)
OR operation and (b) AND operation.
21
PATH SELECTION CRITERIA
Predicate coverage/condition
coverage criterion Table 5: Two test cases providing complete
statement coverage and branch coverage
If all possible combinations of truth
values of the conditions affecting a path
have been explored under some tests,
then we say that predicate coverage has
been achieved.
Figure 7: Partial control flow graph with (a) OR operation and
22
PATH SELECTION CRITERIA
(b) AND operation.
The False branch of node 5 is
executed under exactly one
condition, namely, when OB1 =
False, OB2 = False, and OB3 =
False, whereas the true branch
executes under seven conditions.
If all possible combinations
of truth values of the
conditions affecting a
selected path have been
explored under some tests,
then we say that predicate
coverage has been achieved.
Therefore, the path taking the
true branch of node 5 in Figure 7
must be executed for all seven
possible combinations of truth
values of OB1, OB2, and OB3,
which results in OB = True.
Control flow testing scenarios for a web application:
Login and Authentication Flow Testing:
•Verify the login functionality with correct credentials.
•Test login with incorrect credentials and check for error handling.
•Test password reset functionality.
•Check if session management works correctly after successful login.
•Verify the behavior when the user is already logged in and tries to access
the login page.
User Registration Flow Testing:
•Test user registration with valid and unique information.
•Verify the handling of duplicate or invalid registration details.
•Check if a verification email is sent and account activation works as
expected.
•Ensure that password validation and complexity requirements are
enforced during registration.
Form Validation Testing:
•Test each field in a form with valid and invalid inputs (e.g., text fields,
checkboxes, radio buttons, dropdowns).
•Check if required fields are properly validated and errors are displayed
when they are empty.
•Verify the handling of maximum and minimum length for text fields.
•Test special characters, numbers, and edge cases for various input
fields.
Control flow testing scenarios for a web application:
Navigation Testing:
•Verify that all navigation links and buttons lead to the correct pages
•Check for proper redirects after form submissions or actions
(e.g., after submitting a contact form).
•Test the behavior of the "Back" button in different scenarios.
•Ensure that navigation menus and dropdowns work as intended.
Error Handling and Validation Messages:
[Link] error messages for various scenarios (e.g., 404 page not fou
server errors).
[Link] if validation error messages are displayed correctly for inv
user inputs.
3. Verify that error messages are clear and user-friendly.
User Permissions and Access Control Testing:
[Link] different user roles and ensure they have appropriate
access to various sections of the application.
[Link] that unauthorized users are restricted from
accessing sensitive areas.
[Link] Management and Security Testing:
[Link] session expiration and handling of expired sessions.
[Link] for proper logout functionality.
[Link] the application's security measures, such as
preventing Cross-Site Scripting (XSS) and
[Link]-Site Request Forgery (CSRF) attacks.
[Link] for Mobile Responsiveness:
[Link] the web application on different devices and screen
sizes to ensure proper responsiveness and layout.
31
Having identified a path, a
key question is how to make
the path execute, if possible.
Generate input data that satisfy all
the conditions on the path.
GENERATING TEST INPUT
Key concepts in generating
test input data
Input vector
Predicate
Path predicate
Predicate interpretation
Path predicate expression
Generating test input from path
predicate expression
32
Input vector
An input vector is a collection of all
data entities read by the routine whose
values must be fixed prior to entering
the routine.
GENERATING TEST INPUT
Members of an input vector can be as
follows.
Input arguments to the routine
Global variables and constants
Files
Contents of registers (in Assembly
language programming)
Network connections
Timers
Example: An input vector for
openfiles() consists of individual
presence or absence of the files
“files1,” “file2,” and “file3.”
Example: The input vector of
ReturnAverege() shown in Figure 5 is
<value[], AS, MIN, MAX>.
33
Predicate
A predicate is a logical function evaluated at
a decision point.
Example: ti < AS is a predicate in node 3 of
Figure 5.
GENERATING TEST INPUT
Example: The construct OB is a predicate in
node 5 in Figure 7.
Path predicate
A path predicate is the set of predicates
associated with a path.
An example path from Figure 5.
1-2-3(T)-4(T)-5-6(T)-7(T)-8-9-3(F)-10(T)-12-
13.
The path predicate for the path shown above.
ti < AS ≡ True
value[i] != -999 ≡ True
value[i] >= MIN ≡ True
value[i] <= MAX ≡ True
ti < AS ≡ False
tv > 0 ≡ True
34
Predicate interpretation
A path predicate may contain local
variables.
Example: It is composed of
elements of the input vector
GENERATING TEST INPUT
<value[], AS, MIN, MAX>, a
vector of local variables <i, ti, tv>,
and the constant −999.
The local variables are not visible
outside a function but are used to
hold intermediate results, pointer to
array elements, and control loop
iterations.
Local variables play no role in
selecting inputs that force a path
to execute.
Local variables can be
eliminated by a process called
symbolic execution.
The input vector for the
method in example is given
by<x1, x2>.
35
The method defines a local
variable y and uses the
constants 7 and 0.
The predicate x1 + y >= 0
SYMBOLIC SUBSTITUTION
can be rewritten as x1 + x2 + 7
>= 0 by symbolically
substituting y with x2 +7.
The rewritten predicate x1 +
x2 + 7 >= 0 has been
expressed solely in terms of
the input vector<x1,x2>and
the constant vector<0,7>.
Predicate interpretation is
defined as the process of
symbolically substituting
operations along a path in order to
express the predicate solely in
terms of the input vector and a
constant vector.
A predicate may have
different interpretations
depending on how control
reaches the predicate.
This means the decision in
the program (whether to go to
the if-block or the else-block)
now depends only on the
inputs x1, x2, and constants
like 7
36
Path predicate expression
An interpreted path predicate is called a path
predicate expression.
A path predicate expression has the following
attributes.
GENERATING TEST INPUT
It is void of local variables.
It is a set of constraints in terms of the input
vector, and, maybe, constants.
Path forcing inputs can be generated by
solving the constraints.
If a path predicate expression has no solution,
the path is infeasible.
Path predicate expression for the path 1-2-
3(T)-4(T)-5-6(T)-7(T)-8-9-3(F)-10(T)-12-13
[Figure 5].
0 < AS ≡ True ……
(1)
value[0] != -999 ≡ True ……
(2)
value[0] >= MIN ≡ True ……
(3)
value[0] <= MAX ≡ True ……
(4)
1 < AS ≡ False ……
(5)
1>0 ≡ True ……
(6)
GENERATING TEST INPUT Interpretation of Path Predicate of Path in
Figure 5
Path
1-2-3(T)-4(T)-5-6(T)-7(T)-8-
9-3(F)-10(T)-12-13
The rows here have been obtained
from Side 24 [from path predicate]
by combining each interpreted
predicate in column 3 with its
intended evaluation in column 1.
37
38
Path predicate expression
An example of infeasible
path
GENERATING TEST INPUT
Another example of path
from Figure 5.
1-2-3(T)-4(F)-10(T)-12-13
Path predicate expression
for the path
shown above.
0 < AS ≡ True ……
(1)
value[0] != -999 ≡ True ……
(2)
0>0 ≡ True ……
(3)
39
Generating input data from a
path predicate expression
Consider the path predicate expression
(reproduced below.)
0 < AS ≡ True
GENERATING TEST INPUT
…… (1)
value[0] != -999 ≡ True
…… (2)
value[0] >= MIN ≡ True
…… (3)
value[0] <= MAX ≡ True
…… (4)
1 < AS ≡ False
…… (5)
1>0 ≡ True
…… (6)
One can solve the above equations to
obtain the following test input data
AS =1
MIN = 25
MAX = 35
Value[0] = 30
Note: The above set is not unique.
40
A program unit may
contain a large number of
paths.
Path selection becomes a
CONTAINING INFEASIBLE
problem. Some selected paths
may be infeasible.
Apply a path selection
strategy:
Select as many short paths as
possible.
Choose longer paths.
There are efforts to write
code with fewer/no infeasible
paths.
PATHS
41
Control flow is a fundamental
concept in program execution.
A program path is an instance of
execution of a program unit.
Select a set of paths by considering
path selection criteria.
Statement coverage
Branch coverage
Predicate coverage
All paths
From source code, derive a CFG
(compilers are modified for this.)
Select paths from a CFG based on
path selection criteria.
Extract path predicates from each
path.
Solve the path predicate expression
SUMMARY
to generate test input data.
There are two kinds of paths.
feasible
infeasible
int binsearch(int X, int V[], int n) {
int low, high, mid;
low = 0;
high = n - 1;
while (low <= high) {
mid = (low + high) / 2;
if (X < V[mid])
high = mid - 1;
else if (X > V[mid])
low = mid + 1;
else
return mid;
}
return -1;
}
THANK YOU!!