21/10/2022, 18:42 Software Testing

Software Testing
Motivation
Popular Errors
Ariane 5: rocket exploded due to conversion of 64 bit fp to 16 bit
int for altitude data
Therac 25: machine that gives radiation therapy to cancer
patients. Race condition occured and 6 died
Intel pentium bug: defective pentium chip so lost $475m cause of
FP division error
Inadequate software testing costs US 22-59 billion per year
Amazon had an online discount sale and gave double the discount
Types of software:
Agile: developer must also test
Embedded safety critical: must meet regulatory standards ex:
in cars
Enterprise software: very complex and large. Critical server
requirement ex:citibank, railways
Web apps: Available to many users, Social networking
Free software: also expected to be correct
Cost of testing:Cost of fixing at later stages is very expensive. Errors
more often start at unit testing stage. followed by design and then
requirements. More often detected during system testing or
integration
Testing cannot prove a software to be correct, only shows errors
Testing cannot be replaced by software reviews
Cannot be fully automated
There are 5 process maturity levels:
Level 0: No diff between testing and debugging. Doesn't help
https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 1/66
21/10/2022, 18:42 Software Testing

develop good software

Level 1: Purpose is to show written code is correct.
Level 2: Purpose is to show failures.This is a negative activity.
Many companies are at this level.
Level 3: Testing can show presence of failure. Testers and
developers work together to reduce risk
Level 4: Testing is a mental discipline that increases quality.
Measure and improve software quality
Terminologies
Validation: evaluation at the end of development
Verification: during software development
Testing mainly deals with verification
Formal methods: model checking, theorem proving, program abalysis
Accreditation: safety critical software
Fault: defect that occurs in software, not when software is executing
Failure: The incorrect behavior when software is executing which is
due to a fault in the code
Error: incorrect state that a software enters because of a fault
bug and fault was used by edison
error was used by ada lovelace
Test case: involves inputs to software and expects outputs
If actual output matches expected output, then test cases passed.
Otherwise failed
Failed test case indicates error
test case has id, and traceability details that tell what functionality is
being tested by the test case
Traceability data is stored in a traceability matrix
Various levels of testing:
UNit testing: by developer during coding
Integration: Various components put together and tested (HW or
SW component)
System testing: Full system implementation and platform where

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 2/66
21/10/2022, 18:42 Software Testing

system will run (ex: with db, clients, server). It is an end to end
testing
Acceptance testing: Done by end customer to make sure it meets
requirements
Beta testing is done in beta version of software (not fully tested
yet)
Functional testing: checks if software meets specified
functionality
Stress testing: peak conditions tested (10000 users)
Performance testing: speed and response
Usability testing: UI testing
Regression Testing: Done after modifying one component and
checks if others are not damaged
2 broad methods of testing:
Black box testing: Test without looking at internal code
White box testing: Tests internal structure and code (unit,
integration, system)
Activities in testing:
1. Define and design test case
2. Test automation is making is execution ready
3. Test execution
4. Evaluation analysis: check if passed and if not where there is an
error
Adjacent activities are test management, maintenance and
documentation
Test design is the most critical job. Effective test cases must be
designed. Inputs and expected outputs are defined. Domain
knowledge is needed so it cannot be automated.
jUnit is used to convert test cases to executable scripts
Testing Based on Models and Criteria
Testability: is the software testable( can inputs be give, executed,
and outputs be observed)
Observability: How easy is it to observe the behaviour of a program in
terms of its outputs, other internal factors

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 3/66
21/10/2022, 18:42 Software Testing

Controllability: how easy is it to provide a program with the needed

inputs (giving inputs to a function deep in the software)
Testability consists of observability and controllability
RIPR Model: conditions necessary for failure to be observed:
Reachability: fault location should be reached
Infection: state should be incorrect
Propogation: Incorrect output must be produced
Reveal: Tester must observe incorrect position of the program
Model Based Testing
Working with the model of the software and deriving test cases
from model
Model can be based on mathematical notation, or modelling
language like UML, ..
Models can be made for the requirements or design stage
Start with software artifact and come up with a model. Refine test
requirements and have inputs ready. Test script prepared by
automation. Inputs can the be passed and execution is done.
Models represent a software artifact or its abstraction. There are
no models for code.
Graphs can be extracted from code or from design elements such
as fsm
Logical predicates are present at every decision statement
models are considered for defining coverage criteria
Models:
Graphs for control flow or data flow
Logical Expressions
Sets (input domain for black box)
Grammars: syntax of language represented using grammar
Predicate coverage: making the predicate both true and false
Test requirement is to achieve predicate coverage
Test requirement: A requirement given for a test case. ex: cover a
while loop 3 iterations
Criteria: Rule or set of rules that impose requirements on test
https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 4/66
21/10/2022, 18:42 Software Testing

cases. Given a set of test requirements TR for a coverage criteria,

a set of test cases T satisfies C iff for evert tr in TR, there is one
test t in T such that t satisfies tr.
A coverage criteria that is not satisfiable is infeasible. (ex a
predicate that is a tautology so can never be false)
Coverage criteria used in 2 ways:
Generator: Generate test cases to satisfy coverage criteria
Recognizer: Generate externally and check if the cases meet
coverage criteria
Criteria Subsumption
Coverage criteria C1 subsumes C2 iff every test case that satisfies
C1 satisfies C2
Subsumption only applies to feasible criteria
Test Automation using JUnit
Ensuring RIPR are done in the step of automation
Prefix are given towards reachability and postfix to ensure
propogation
Test automation controls execution of tests and compares actual and
expected output. Preconditions are set up
Prefix values are inputs needed to put software into the correct state
where it can receive actual test cases.
Postfix values: values needed so that output of tests can reach the
output of software.
Verificatioin values are needed to see the results of test case
values
Exit values are needed to terminate the program or go to a stable
state
Test case has test case values, prefix, postfix, expected outputs
Executable test script is now needed and it contains the above values
JUnit is open source and is used for test automation
Results can also be evaluated using junit
JUnit features
Assertions always return true or false

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 5/66
21/10/2022, 18:42 Software Testing

Common test data can be shared between people

GUI and textual interface
Test suites for organizing and running test cases
JUnit mainly for testing java programs
JUnit used for unit and integration testing but not for system
Can test an entire object or part of an object or interaction between
objects
Each test is embedded into a test method
Test class contains 1 or more test methods
Methods to set up state before and update after each test are
included in test class
junit.framework.assert class must be used.
test runner method uses result of assert.
assertTrue(boolean) if boolean predicate is true then true
assertFalse(boolean) if boolean predicate is true then return false
assertTrue(string,boolean) if boolean predicate is false print string
fail(string) output string to user on failure
Test fixture is a state of the test which includes objects and variables
used by many tests, prefix and postfix values
Objects in test fixtures declared as instance variables
Prefix values initialized using @Before and postfix using @After (reset
values)
if you allocate external resources in a @Before method, you need to
release them after the test runs using an @After method
Basics of graphs
Graph is a tuple (V,E)
Graphs can be finite or infinite but we consider finite
Degree of vertex is number of edges on a vertex
Indegree is number of edges coming in and outdegree is number of
edges going out
Special vertices can be designated that are initial and final
Final vertices are denoted using 2 circles

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 6/66
21/10/2022, 18:42 Software Testing

Initial vertex has a line coming in that is not connected to any other
vertex
Usually only 1 initial vertex and many final
Initial and final vertex could be the same
Graphs can represent contorl flow, data flow, call graph, use case,
activity
Graphs can have labels with edges or vertices
Tests must cover the graph
If statement can have a vertex with each outgoing edge representing
if condition being true and false. Statements can then be written as a
label for the vertices with condition for if as label for edge
Path is a sequence of vertices such that there exists an edge
between every vertex in the path
Length of path is number of edges
Subpath: subsequence of vertices in a path
A vertex is reachable if there is a path from the initial vertex to that
vertex
An edge (u,v) is reachable if there is a path from the initial vertex to
the vertex u in the edge.
A subgraph is subset of vertices and edges of the graph. The
subgraph is reachable if any vertex of the subgraph is reachable from
the initial node of the graph.
Reachability
DFS
BFS
Test path begins with initial and ends in final vertex
If test path can be executed by text cases then its feasible.
otherwise infeasible
Test path p visits vertex v if v occurs in the path P. Test path p
visits edge e if e occurs in path p.
Test path p tours a path q if q is a sub path of p
Each vertex and edge itself is a subpath so test path tours those
edges and vertices
Many different test cases can execute the same path
https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 7/66
21/10/2022, 18:42 Software Testing

Reachability is now in the presence of the conditions in the labels

Path(T) is set of tets paths executed by a set of test cases T
A vertex or edge or subgraph is reachable if there is a test case
whose path can be executed to reach the vertex or edge or
subgraph
infeasible test paths lead to unreachable components
Test Requirement: properties of test paths
Test criteria: rules that define test requirements(example cover all
2 branches of a switch case)
Satisfaction: Given TR for a critera C, set of tests T satisfies C iff
for every test requirement, there is a test path that meets the test
requirement
Structural coverage criteria: defined in terms of vertices and
edges
Data flow coverage criteria: Graph must be annotated and
requirements are based on annotations
Structural coverage criteria
Node/vertex coverage: test cases should visit every reachable node
once
Edge coverage: Visit every reachable path of length up to 1 (length 0
means just a vertex. edge coverage subsumes node coverage)
Edge pair coverage: Visit every reachable path of length up to 2
(subsumes edge coverage). Could be useful for branches
Path Coverage
Complete path coverage :TR contails all paths in G (infeasible) so
we consider specified path coverage where TR contains a set S
of paths which the user specifies. If the graph has a loop, then
complete path coverage is infeasible.
Test cases must cover the loop: execute the loop at its bounfary
confition (skip loop) and execute it once for normal iterations
Simple path: no node appears more than once except for the first
and last node (every loop is a simple path)
Prime path: Simple path that is not a subpath of any other simple
path

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 8/66
21/10/2022, 18:42 Software Testing

Prime path coverage (loops): Must cover all prime paths in a

graph. It skips a loop and also executes it. It also subsumes node
and edge, but does not subsume edge pair coverage if the graph
has a self loop
Some codes may have a do while loop which enters the loop
atleast once therefore causing a node to repeat twice in the path.
Tour with side trip: Test path p tours sub path q with side trip iff
every edge in q is also in p in the same order (can include sidetrip
but must come back and execute in same order)
Tour with detours: Test path p tours sub path q with detour iff
every node in q is also in p in the same order. Detour from node n
can be included as long as it comes back to the prime path at
successor of n.
If side trips are not allowed, then may have infeasible test
requirements. But cannot always allow
Best effort touring: Satisfy as many test requirements as possible
without sidetrips and use sidetrips to satisfy remaining
Round trip:starts and ends at same node. length cannot be zero
and it is a prime path.
Complete round trip coverage: TR contains all round trip paths for
each reachable node in the graph that begins and ends in a round
trip path
Simple round trip coverage: Contains atleast 1 round trip path for
each reachable node in the graph that begins and ends in a round
trip path
Round trip coverage does not subsume edge, node or edge pair
coverage
Elementary Graph Algorithms
Adjacency list is useful for sparse (not many edges but many
vertices) and Adjacency matrix is good for dense graphs (Many
edges)
Adjacency list: |V| lists where each list has all the vertices conected
to that vertex
Space for adjacency list is O(|V|+|E|)
Adjacency matrix is |V|x|V|

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 9/66
21/10/2022, 18:42 Software Testing

BFSExplores adjacency list of start vertex, adds to queue, and takes

one from the list at a time and explores each
Computes the distance from start vertex to reachable verties
Path from start to vertex in bfs tree is shortest path
Uses 3 colors : white, gray, black
Initially a vertex is white. It is not discovered
When discovered but not explored, becomes gray and added to
the queue
When fully explored and removed from the queue it is made black
BFS running time is O(V+E)
Distance in the bfs tree is number of edges from start vertex to
that vertex
BFS discovers every reachable vertex and also the shortest
distance. Also, for a vertex v, the shortest path from the root is
the shortest path from the root to the parent of vertex v plus the
edge from the parent to v.
v.pi is parent of v
Predecessor subgraph is a bfs tree
The shortest path distance increases as we explore the graph
The distance value for each vertex is greater than or equal to to
the shortest path distance from the start to that vertex
DFS
predecessor subgraph forms a depth first forest.
2 timestamps used, v.d when first discovered(colored gray) and
v.f (v is colored black).
v.d < v.f for every vertex
v.d and v.f are both between 1 and 2|V|
initialize a time variable to 0 initially.
for each vertex u the graph, if it is white, visit it
DFS VISIT
increment time
u.d=time

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 10/66
21/10/2022, 18:42 Software Testing

it is made gray
for each vertex adjacent to u, if it is not yet discovered (white),
make u the parent and visit that vertex
make u black since it is explored
increment time
u.f=time
DFS visit is called once for every vertex
Running time is O(V+E)
in DFS of a graph G, every edge of G is a tree edge or a back edge
tree edge: edges in the depth first forest
back edges: edge connecting descendant to ancestor, also self
loop
forward edges: edge connecting a vertex to its descendant
cross edges: all other edges
Paranthesis Theorem: for any 2 vertices u and v,
if [u.d,u.f] and [v.d,v.f] are disjoint, u is not a descendant of v
and vice versa also
if [u.d,u.f] is contained in [v.u,v.f] then u is a descendant of v
v is a proper descendant of u if u.d<v.d<u.f<v.f
Strongly connected component is a cycle in a directed graph. All
vertices are reachable from each other. self loops are also
included
Transpose of a graph would be the graph with every edge
direction reversed
Graph and its transpose have the same strongly connected
components
Finding strongly connected components:
Call DFS
Find transpose of the graph
Run DFS on the reversed graph but consider vertices in
decreasing order of finish times
Output vertices in each tree in the DFS forest as a SCC

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 11/66
21/10/2022, 18:42 Software Testing

Correctness
Take all theof strongly
DFS (component
connectedgraph)
component, collapse each one to
create a meta vertex.
There is an edge in the component graph if the graph has a
directed edge from one strongly connected component to another
component graph is acyclic
Discovery and finish time for a component is the least of all and
highest of all vertices
If there are 2 SCC C and C', then if there is an edge from C to C',
finish time of C is greater than finish time of C'
The opposite of the above statement is true for the transpose
Algorithms: Structural graph coverage criteria
Undecidable to see if a criteria is feasible or not
TR for node coverage: all vertices in the graph
TR for edge coverage: all edges in the graph
BFS can be modified to get test paths for node and edge coverage
Edge Pair coverage: explore adjacency list of one node, and
adjacency list of the successors for all vertices
Complete path coverage not feasible if there are loops
Prime path coverage: compute list of prime paths which is the TR
First enumerate simple paths in increasing order of length
Choose some of the simple paths as prime paths
if the final node is included,include ! in the path. If it is a loop and
cannot be further extended use *
Repeat this till you get paths of length |V|
Test path for prime path coverage: Start with longest prime path
and extend it to the left to see if it can be extended to the start
node
Data Flow Graph
Data is represented as variables
A variable is created and then used. A variable that is not declared
cannot be used
We need to track a variable from where its defined to where it's used

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 12/66
21/10/2022, 18:42 Software Testing

Definition of a variable is where the value of a variable is stored in

memory
Input, assignment, parameter passing are all examples of def
Use is where the value of a variable is accessed
du-pairs are pairs of definition and use - (li,lj) defined at li and used at
lj
Several du pairs coiuld be there for a variable
def(n) is applciable for a graph and for a node n, def(n) is the
variables that are declared at that node
def(e) is applicable for a graph and for an edge e, def(e) is the
variables that are defined at that edge
Same applies for use(n) and use(e)
Sequence of assignment statements is collapsed into 1 node
Parameters passed to a method are considered as def
iPat++ , then both def and use
If a variable is used in a computation or an output statement, then
computation use or c use (dcu): dcu(li,lj,v)
If v is used in a conditional statement, then it is a predicate use (p-
use)(dpu). The conditional statament has 2 dpu, one for true branch
and one for false. dpu(li,(lj,lt),v) and dpu(li,(lj,lf),v)
du(li,lj,v) variable v is defined at li and used at lj
A definition may not reach a use
A path is def-clear if variable v is not given another value anywhere in
the path and the def reaches the use
du path is a def clear path from the def of v to the use of v
du(ni,nj,v) are set of du paths from ni to nj for a variable v
du(ni,v) are the set of du paths that start at ni for a variable v
du path can be from def to another use, where the variable is again
defined at the point where it is used
Algorithms: Data flow coverage criteria
Data flow coverage criteria is a set of du-paths
Grouping of du paths can be done in 2 ways:
As per definitions - def-path set: Consider all du-paths wrt a
https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 13/66
21/10/2022, 18:42 Software Testing

variable defined in a node ex:(du(ni,v) is set of all du-paths wrt to

var v that start at ni). du(ni,v)
As per def and use - def-pair set: Set of du-paths with respect to
a variable that start and end at node i and node j. It is from a given
definition to a given use, du(ni,nj,v)
A test path p is said to du tour a sub path d with respect to v if p
tours d and the portion pf p to which d corresponds is def-clear
wrt v
def-clear side trips are also allowed
DU paths are simple
Data flow criteria
Each def reaches atleast 1 use
Each def reaches all possible uses
Each def reaches all possible uses through all du paths
ALL-defs coverage: For each def path set S, the TR contains
atleast one path d in S (each def reaches atleast 1 use)
All-uses coverage: For each def pair set S, TR contains atleast
one path d in S ( atleast 1 path for every def use pair)
All-du-paths coverage: For each def-pair set S, TR contains every
path d in S
Every use is preceded by a def
For every node with many outgoing edges, atleast one variable is
used on each out edge and the same variables are used on all out
edges
If all uses is satisfied, then all defs also satisfied
If all du-paths is satisfied, then all uses satisfied so all defs too
All uses coverage subsumes edge coverage
Prime path coverage subsumes all du-path
For an input program, data flow analysis is done
Then def-use pairs are identified and for each du-pair test data is
generated
If du-pair is covered then test case generated. Otherwise another
du-pair is taken

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 14/66
21/10/2022, 18:42 Software Testing

Graph Coverage Criteria: Applied to Test Code

Function calls are represented using a call graph
Control flow graph: nodes are statement or basic block, edges are
transfers of control
Basic block is a sequence of statements such that there are no
branches. If first is executed then all are
CFGs are also annotated with branch predicates
Extra nodes are added to the CFG for loops
Testing Source Code: Classical Coverage Criteria
Data flow graph augments control flow graph with data
Code coverage: Statement coverage, branch coverage decision
coverage, path coverage
Node coverage is the same as statement coverage
Edge coverage is the same as branch coverage
Prime path coverage is the same as loop coverage
Cyclomatic complexity: Basis path testing, structural testing
It is a software metric used to indiciate how complex a program is
It represents the number of linearly independent paths in the cfg
of a program
A linearly independent path is any path through the program that
introduces atleast one new edge that is not included in any other
linearly independent paths.
Basis path testing deals with testing each independent path in teh
CFG
Linearly independent path is a path that is not a sub path of any
other path
Cyclomatic complexity M=E-N+2P
E:# of edges
N:# of nodes
P: # of connected components
https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 15/66
21/10/2022, 18:42 Software Testing

Cyclomatic complexity should usually be between 1 and 10

1 decision point has 1 node with 2 edges going out so
cyclomatic complexity can give the number of decision points
plus 1
If an edge is added from the final to initial vertex, it becomes a
strongly connected compnonent
Cyclomatic complexity aka cyclomatic number
Basis path testing: Used to test a code with respect to cyclomatic
complexity
TR for basis path testing is the set of linearly independent paths
Basis path testing subsumes branch coverage and complete path
coverage subsumes basis path testing
Decision to decision path: DD Path
Path of execution between 2 decisions
Chain in a graph is a path which has different start and end
vertices, and all interior vertices have indegree and outdegree as 1
Maximal chain is a chain that is not a part of any other
DD-Path is a set of vertices that satisfies one of the following
Single vertex with in degree 0 (initial)
Single vertex with outdegree 0 (final)
Single verted with indegree >=2 or outdegree>=2 (decision
vertex)
Single vertex with indrgee and outdegree 1
Chain of length >=1
Graph criteria: subsumption

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 16/66
21/10/2022, 18:42 Software Testing

Data Flow Graph Coverage Criteria : Applied to Test Code

3 data flow coverage criterias: all defs,all uses, all du paths
No defs and uses at the dummy node used for the loop
Node which is reached on completion of the loop still has previous
loop counter under def because of last increment
Defs only appear at nodes
Uses can appear at nodes or edges. They appear at edges for
checking of conditions
List all nodes and the defs and uses at each node
Then list all the edges and the uses at edges

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 17/66
21/10/2022, 18:42 Software Testing

( 1,1) not listed as it starts and ends at the same node and is not a du
path. (8,8) should also not have been listed
1 DU path for every DU pair
Find unique DU paths
Categorize paths into skip the loop, 1 iteration of the loop, and more
than 1 iteration of the loop
Test paths must cover all DU paths
More bugs detected using data flow coverage criteria than branch
coverage criteria
Software Design and Integration Testing
C reating graphs for design instead of code is in integration testing
Software design tells how a large software is split into modules
Modules interact wuth each other using interfaces
Interfaces define how control and data flow between modules
Modules are self contained(standalone)
Integration testing involves testing if the put together modules meet
functionalities and if interfaces are correct
Integration is after unit testing
Types of interfaces:
Procedure call interface: procedure or method in one module calls
procedure/method in another module
Shared memory interface: Block of memory shared between 2
modules
Message passing interface: Modules prepare messages and
transmit it through the interface
25% of total errors are interface errors
Types of errors:
Module functionality related: One module could call another
module and assumes the other module offers some functionalities
but that module may not offer those
Interface related: Wrong parameter order when calling procedure
in another module
Inadequate error handling
https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 18/66
21/10/2022, 18:42 Software Testing

Initialization and other value errors

Timing and performance: may have timed out early
Integration does not have to wait for all modules to be ready
Testing as and when module is ready: Not all components may be
ready so extra components are neeeded. this is Scaffolding
Types of scaffolding:
Test stub: Create a dummy module that substitutes actual module
Test driver: replaces a component that takes care of the calling of
the modules. For example, parent may call 3 modules, but if parent
is not ready then use test driver
5 approaches to integration testing
Incremental: As and when modules are ready, test cycle by cycle
Top-down: Works with hierarchical design. Top level is
decomposed, and those are further decomponsed into other
modules. Terminal modules are not decomposed. Start with top
model and test top model independently with 1 lower level
module, then keep adding one at a time from the lower level. (ppt
diagram) Stubs are used
Bottom up: Start from modules in the lowest levels and move up
and use test drivers
Sandwich: Mix of top down and bottom down. Uses both of them
Big bang: All undividually tested modules are put together and
tested
Graphs for integration testing
Nodes are modules, test stubs, test drivers
Edges are interfaces
Design Integration Testing and Graph Coverage
Call graphs are used
Structural coverage criteria deals with calls over interfaces
Data flow coverage criteria deals with data exchange between
interfaces
Structural
Nodes are modules so node coverage will be to call every module

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 19/66
21/10/2022, 18:42 Software Testing

atleast once
Edges are calls so edge coverage is to execute every call once
Path coverage is to test a sequence of calls (for big bang)
No loops in call graphs so no prime paths
Class inheritance testing
Arrow from class B to class A means B extends A
Arrow from class A to object a1 means a1 is an object of class A
Class call graphs dont make sense as there wont be many calls
within a classs so graphs represent inheritance and polymorphism
Consider objects for each of the classes since classes are not
execuatble)
OO call coverage criteria (1 obj per class): TR contains each
reachable node in the call graph of an object instantiated for each
class
OO Object call coverage (many objs in a class): TR contains each
reachable node in the call graph of every object instantiated for
each class
Data flow
Caller: module that calls another
Callee: module that is called
Call site: node where the call occurs
Actual parameter: variable in the caller
Formal parameter: variable in the callee
Coupling variables: defined in one unit and used in another
Parameter coupling: x could be passed in caller and y used in
callee
Shared data coupling: Shared variables
External device coupling: access data from a file
Last def (before calls and returns so caller to callee or callee to
caller): set of nodes that define a variable x and has a def clear
path from the node to the call site
First use: Set of nodes that have uses for a variable y and a def
clear and use clear path from call site to the node

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 20/66
21/10/2022, 18:42 Software Testing

Coupling data flow coverage criteria:

Coupling DU path is from last def to first use
All coupling def coverage: Path from every last def to atleast one
first use
All coupling use coverage: Path from every last def to every first
use
all coupling du paths coverage: Every simple path from last def to
first use executed
Side trips are allowed
If a calls b ad b calls c and c uses a var in a then transitive du pairs
(not needed)
For arrays, ref to one element in the array refers to ref to entire
array
D0-178C used by aviation authority mentions coupling testing
Specification Testing and Graph Coverage
Types of design specifications:
Sequencing constraint
State behavior
precondition is something which must be true before an action can
occur
postcondition is something which must be true after an action occurs
Sequencing constraints are rules that impose constraints on the order
in which methods may be called
These are written along with design so that design can meet
requirements
Designer should always write sequencing constraints
Consider CFG and see if sequencing constraints are violated
They can violate statically (dont run the code) or dynamically
In dynamic testing, sometimes a loop cannot be skipped completely
so might have to enter a loop atleast once
One test criteria for each sequencing constraint
For state related sequencing constraing FSM is used
Graph Coverage and Finite state Machines
https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 21/66
21/10/2022, 18:42 Software Testing

UML supports FSMs

FSM good for control intensive application but not for data intensive
FSM annotated with entry actions, exit actions, actions on transitions
Preconditions are conditions true for a transition to be take
Trigger is the event that causes a transition to take place
Node coverage: execute every state
Edge coverage: every transition
Edge pair coverage: execute every pair of transitions
Data flow coverage: No defs or uses in nodes. So data flow coverage
not used. Logic used instead
FSM not used to model, only english statements are written by
designers in the specification. Testers use FSM.
Control flow graph is not an FSM
Call graphs are not FSMs
Values of variables need to be considered in FSMs and transitions tell
how values change
UML is unified modelling language
Many UML diagrams are graphs: FSM, state charts, use case
Graph coverage criteria can be applied
Nodes and edges will have defs and uses but different from CFG
Logic: Basics Needed for Software Testing
P redicate evaluates to true or false. ex: x>=y where x and y are
integers, f(x) where f is a function that returns a boolean value
Clause is a predicate that does not contain any logical operator . it is
a boolean atomic entity
Logic Coverage Criteria
P : set of predicates, C: set of Clauses in P
Predicate coverage: For each p in P, TR has 2 requirements, p
evaluates to True and False
For predicates associated with branches, predicate coverage and
edge coverage are the same thing

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 22/66
21/10/2022, 18:42 Software Testing

Clause coverage: for each clause c in C, TR has 2 requirements, c

evaulates to true and c is false
Clause coverage does not subsume predicate coverage
Combinatorial coverage (multiple condition coverage): For each p in
P, All possible truth value combinations must be included for the
clauses in P (Cp)
Combinatorial coverage is not feasible
Clause determining a predicate: the value of the clause is the same
as the value of the predicate. The values of the other clauses do not
matter.
Clause which is the focus is the major clause and the other clauses
are minor clauses
Each clause is treated as a major clause
Active clause coverage: Major clause must be made true once and
false once
For a predicate with n clauses, active vlause coverage has n+1 TRs
Modified condition decision coverage (MCDC): Same as active clause
coverage
MCDC is manditory for safety critical software
In ACC, we dont consider values of minor clauses.
Types of ACC:
General ACC: Same as active clause coverage, and the value of
the minor clauses dont have to be the same for when major clause
is true and false. GACC does not subsume predicate coverage.
Correlated ACC: Minor clauses correlate with each other. The
values chosen for minor clause must make the predicate to
evaluate to True for one value of the major clause and false for the
other value of the major clause. CACC subsumes predicate
coverage
Restricted ACC: The value of the minor clauses have to be the
same for when the major clause is true and false
Coverage Criteria continued
Inactive clause coverage: major clause should not affect the
predicate

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 23/66
21/10/2022, 18:42 Software Testing

There ci isaretrue4 TRs,

with pthetruemajor clause is ci and predicate is p
ci is false with p true
ci is true with p false
ci is false with p false
Inactive clause coverage subsumes predicate coverage as according
to the TR p is both true and false
Correlated ICC does not make sense since major clause does not
determine predicate
General Incactive clause coverage: The valuse of the minor clauses
may vary
Restricted inactive clause coverage: The values of the minor clauses
must be the same for when the predicate is true and the same for
when predicate is false
Many TRs are infeasible so ignore the coverage criteria and look at
others
RACC and RICC are infeasible often, so use CICC or CACC instead
Logic coverage criteria test cases
As long as a predicate is not valid or is not a contradiction, then
predicate and clause coverage can be done
RIPR must be solved when writing test cases
Test cases for ACC and ICC: Make the major clause true and xor it
with the major clause made false. Pc= (Pc=true) xor (Pc=false)
If the major clause always determines the predicate, then ICC is
infeasible. If a major clause can never determine a predicate, then
ACC is infeasible
If the expression for making a clause major clause evaluates to false,
then it is impossible for that clause to determine the predicate and
that clause is also redundant so can be removed from the expression
Find expression Px for every clause x. Evaluate the expression and
include in truth table to find out GACC,RACC etc
https://cs.gmu.edu/~offutt/softwaretest/edition1/exer-student.pdf
pg 51
Logic clause coverage subsumption

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 24/66
21/10/2022, 18:42 Software Testing

Logic coverage criteria applied to test code

predicates are found in decision statements
Variables in the prediciate that are not inputs to the program are
called internal variables
Issues:
ACC can be expensive so rewrite program to elminate many
clauses in predicates
To find cyclomatic complexity, we work with simple predicates
(predicate with 1 clause)
Breaking down program to change complex predicates to simple

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 25/66
21/10/2022, 18:42 Software Testing

may not always work

Predicate transformation deals with re writing predicates so that
they have 1 clause only
Some code segments may get repeated so not a good
programming practice to split predicates into simple predicates
On splitting predicates to simple predicates and applying
predicate coverage, CACC may not be satisfied
Logic and specifications
specifications can be written in english or formal language
logic expressions can be included in the specifications
if the specifications are informal then specifications must be derived
Pre conditions and post conditions contain predicates
invariants might specify mutual exclusion property and include
predicates
assertions also include predicates and are used for debugging
Code usually includes preconditions
ACC is very easy if it is in CNF form or DNF
If in CNF, Make all minor clauses true. Make the major clause true
once and false once
If i DNF, Make all minor clauses false and make the major clause true
once and false once
Some clauses are dependent on each other so sometimes 2 cannot
be true or false at the same time for clause coverage
Functional Testing
Functional testing is in the domain of black box testing
Black box testing deals only with inputs and outputs applied to code,
design, requirements
Black box testing is also referred to as functional testing
A program P is viewed as a function that transforms inputs xi to
outputs yi such that yi=P(xi) where yi and xi are vectors of inputs and
outputs
Domain of input and outputs must be understood first
Select values from the domain of inputs and select corresponding

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 26/66
21/10/2022, 18:42 Software Testing

output
Combinations of test cases from different domains are considered
Input values chosen must produce special values
Soemtimes to do functional testing, the context in which a function is
invoked may be needed. For example, if x>20 call a function g
Types of functional testing:
Equivalence class partitioning: Assumes input domain is large, so
partition inputs such that finite number of partitions and each
partition is sub domain and is an equivalence class. All inputs from
one sub domain have the same effect (output is same)
Boundary Value Analysis: Test inputs near the boundary of the
data domain are chosen. If the partition has an ordered set of
elements, then consider the first and last element. If the partition
specifies a number of values, test for minimum and max value of
the number, and also a value smaller than minimum and greater
than the maximum.
Pair-wise testing: orthogonal arrays
Decision tables: Equivalence class partitioning considers inputs
individually. Decision tables can consider a combination of
equivalence classes.
Decision table has conditions, value for the conditions (Yes - y,
No - n, - is dont care), and rules that specifiy if for each rule a
condition is needed. All possibile combinations are considered
(3 conditions so 2^3 combinations hence 8 rules and each
column has all possible combinations of Y and N)
There are also effects and numbers associated with each
effect and rule. These numbers are the effect sequence
number which specified the order in which the effect should be
carried out if the corresponding conditions are satisfied
There is a checksum row at the end for verification of the
combinations (should be 2^3)
Example in PPT
Random Testing: pick a random input and test. Monkey runners is
a tool which produces random inputs. It can check if exceptions
and error conditions are handled.
Input Space Partitioning

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 27/66
21/10/2022, 18:42 Software Testing

It is the same as equivalence class partioning

Given a set S, a partition of S is a subset of sets such that the
subsets are disjoint and the union of all subsets is the set S
The set that is split into partitions is the input domain
Each partition is based on some characteristic. The characteristic
allows the user to partition. for example, characteristic order of file
and partitions are ascending, descending. But this overlaps if file size
is 1 since file belongs to ascending and descending partition. So
characteristics must be chosen accordingly
Partition must be complete and cover the whole domain and also be
disjoint.
Input domain modelling
Identify testable functions: Identify which functions are to be
tested
Identify the parameters than can affect a given testable functions
and the parameters together give the input domain
Identify the characteristics and partition for each characteristic
Get the tets inputs which is a tuple of values with a value for each
parameter
2 approaches for input domain modelling are:
Interface based approach: Considers each parameter in
isolation, and it is easy to identify characteristics.
Disadvantage is that not all info available to tester is reflected
in the interface domain model and is incomplete. And
sometimes combinations of interface parameters may need to
be considered. Inputs are obtained from specifications so it is
black box testing.
Functionality based approach: Characteristics are based on
functionality of the system and not using the interface. It is
based on requirements and is better than interface based.
Since it is based on functionality, identifying characteristics is

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 28/66
21/10/2022, 18:42 Software Testing

difficult. Preconditions,post conditions are used to identify

characteristics. Domain knowledge is needed.
More combinations makes it more likely to find faults
On choosing characteristics, the domain of characteristics needs to
be divided into sets called blocks
M ore blocks results in more tests
Identifying values: valid values, boundary, invalid, a range of valid
values can be further partitioned to sub partitions and might be
cheap to add more partitions to characteristics that have less
partitions, there should be no missing partitions and union of all
should be complete input space, they should be disjoint and no
overlap
Input space partitioning coverage criteria
All combinations Coverage AcoC: All combinations of blocks from all
characteristics must be used. ex: [A,B],[1,2,3],[x,y] where the values
inside the partitions are blocks so 12 (product of number of blocks in
each characteristic). It generates all possible combinations so might
not always be necessary
Each choice coverage: One value from each block for each
characteristic must be used in at least one test case.for example,
[A,B], [1,2,3] then (A,1), (B,2) and 3 must also be included so it can go
along with A or B. Total number of test cases is max number of blocks
in any characteristic. It is a weak coverage criteria and might leave
out important combinations
Pair wise coverage: A value from each block for each characteristic
must be combined with a value from every block for each other
characteristic. example, 3 partitions with 2,3,2 blocks, then
2*3+2*2+3*2 pairs in total. The chosen test cases can each then
cover as many number of pairs.The test suite has atleast max size
block to the power 2 values.
T wise coverage: A value from each block for each group of t
characteristics must be combined.If the value for T is chosen to be
the number of partitions, then TWC is equivalent to all combinations.
The test suite has atleast max size block to the power t values.
The above criterias consider combinations blindly. the next 2 do not

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 29/66
21/10/2022, 18:42 Software Testing

consider it blindly. There will be an important block for each partition

and this is the base choice
Base Choice Coverage: A base choice is chosen for each
characteristic and a base test is formed using the base choice. Each
time except for 1 characteristic, base choice is chosen for all others
and the other one alone is varied for all combinations. The base test
has base choice for all characteristics. Totally, 1 + (Bi-1) for each i
from 1 to n where n is number of characteristics
Multiple Base Choice Coverage: Sometimes, multiple base choices
may be chosen. Base tests are formed using each base choice for
each characteristic. If there are mi base choices for each character
and M base tests, then M+(M*(Bi-mi)) for i=1 to n
All combinations subsumes all others. T wise subsumes pair wise.
Multiple base choice subsumes base choice. Pair wise and base
choice both subsume each choice
infeasible combinations of partitions are also possible. Constraints
are relations between partitions from different characteristics
the 2 kinds of constraints are:
A block from one characteristic cannot be combined with another
block from another characteristic
A block from one characteristic must be combined with another
block from another characteristic
For ACoC , PWC and TWC, must drop infeasible combinations
For BCC and MBCC, base case can be altered to handle constraints
Choice clause coverage subsumption

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 30/66
21/10/2022, 18:42 Software Testing

Syntax Based Testing

S yntax can be used to generate artifacts that are valid and invalid.
These artifacts are sometimes test cases, but are mostly used to
generate test cases
Syntax comes in 3 levels
Words: the lexical level, specified using regular expressions.
defines how characters form tokens
Phrases: Grammar level, determines how tokens form phrases.
Specified usimg CFG in Backus Naur Form BNF
Context: Types of variables, what the refer to. Specified using

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 31/66
21/10/2022, 18:42 Software Testing

context associate
Semantics sensitive grammar
a language with regex
L(r+r')=L(r)UL(r')
L(r*)=L(r)*
L(r.r')=L(r).L(r')
CFG is of the form G=(N,A,S,P) where N-non terminals, A-terminals, S
belongs to N and is start non-terminal, P is productions)
Lexical analyzer parses a regular expression
Sentential Form of Grammar G: any alpha belonging to (N U A)* such
that S derives alpha in any number of steps (Intermediate RHS of
derivations)
A Language is a context free language if there is a context free
grammar which has the same language
Coverage Criteria over grammars:
Terminal Symbol Coverage (TSC):TR contains each terminal
symbol in the grammar
Production Coverage (PC): TR contains each production
Derivation Coverage (DC): TR contains every possible string that
can be derived from the grammar. Can be infeasible if language is
infinite
PC subsumes TSC
DC is infeasible
Mutation Testing
Mutation involves making syntactically valid changes and then testing
Grammars generate valid strings. Derivations in grammar also used to
generate invalid strings
Testng based on the valid and invalid strings is mutation testing
Can be applied to code, design, inputs, requirements
Ground String: A string in the grammar
Mutation Operator: Rule that specifies syntactic variations of strings
generated from a grammar
Mutant: Result of 1 application of a mutation operator
Ground string could be a program specified using a grammar (ex java)

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 32/66
21/10/2022, 18:42 Software Testing

Mutation operator can be applied to grammar or dynamically derived

during derivation
Sometimes when we mutate inputs, program stays the same and only
program outputs are checked so after applying mutation operator we
still get ground string
Ideally use only 1 mutation operator and after analyzing it use another
so that it is easier to track
If the program is small, then every possible application of a mutation
operator to a ground string should be consudered. Not for large
Mutation operators have been designed for several programming
languages, modelling languages, data definition languages etx
Mutation operators for programming languages can be applied at unit
testing and integration testing levels
Let M be the set of mutants. Each mutant m in M leads to a different
test requirement
Testing goal is to kill mutant by causing mutant to produce different
output
Given a mutant m in M for a derivation D and a test t, t kills m iff the
output of t on D is different from output of t on m
Coverage Criteria
Mutation Coverage: For each mutatnt m in M, TR contains exactly
one requirement to kill m
amount of coverage is written as percent of killed mutants and
is mutation score
high mutation score does not mean better testing
When grammar is mutated to produce invalid strings, run mutants
and check if correct behavior
Mutation Operator Coverage: For each mutation operator, TR
contains one requirement to create a mutated string m that is
derived using the mutation operator
Mutation Production Coverage: For each mutation operator, and
each production the operator can be applied to, TR contains one
requirement to create a mutated string from that production
Mutation testing is very difficult to apply by hand
Mutation Testing for programs
https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 33/66
21/10/2022, 18:42 Software Testing

program based mutation: begin with program which is ground string,

apply 1 or more mutation operators to get mutant. mutant must
compile. mutant is not a test, must write test which can kill mutant
delta 1 means 1 mutation applied
Variable reference mutant: replaces one variable with another
Mutant can change a relational operator
Bomb() is a special mutation operator that causes run time failure as
soon as it is reached. Useful for random crash testing
failOnZero() is a special mutation operator that causes a failure if the
parameter is 0 and does nothing if it is not 0
Exhaustive muation operators available. Must be selected carefully to
strengthen quality of testing.
Test case is effective if different behavior form original program
Mutation operators mimic programmer mistakes
Variants of mutants
Stillborn Mutant: Mutant of program result in invalid programs
that cant be compiled
Trivial mutant: Mutant can be killed by almost any test case. not
useful
Equivalent mutant: Functionally equal to given program, cannot
be killed
Dead Mutant: Valid and can be killed by a test case. Useful for
mutation testing
Killing a mutant: May not be necessary to see change through output
only, reachability and infection enough, propogation not needed
Strongly Killing mutant: output of test case on program is different
from output of test case on mutant
Strong Mutation Coverage: TR contains one requirement to strongly
kill every mutant m in M
Weakly Killing mutant: test case weakly kills a mutant m if the state
https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 34/66
21/10/2022, 18:42 Software Testing

of execution of P on t is different from state of execution of m

immediately after l where l is the location that the mutant modified
Weak Mutation Coverage: TR contains one requirement to weakly kill
every mutant m in M
mutation testing process
Take the input test program
Create mutants using available mutation operators
If mutant equals original so waste, use equivalence heuristic to
check
Generate test cases
Run T on P and m
Eliminate ineffective test cases and check if threshold reached
If threshold not reached generate more test cases
otherwise If program is not correct fix it
Mutation Operators
Operators mimic programmer mistakes so change relational operators
or variable references
FailOnZero() is a common testing heuristic so every programmer must
check this
Effective mutation operators: If tests are created that kill mutants
created by a set of mutation operators O={o1,o2,..} also kill mutants
created by all remaining operators with high probability then O is a
set of effective mutation operators
Difficult to find effective mutation operators
Mutation operators that insert unary and modify unary and binary
operators are effective
List of mutation operators
Absolute Value Insertion: Each arithmetic expression is modified
by function abs, negabs, failonzero
Arithmetic Operator Replacement: Each occurence of +,-,*,/,**,%
is replaced by each other. leftOp returns the left operand and
ignored the right. rightop returns right and ignores left.

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 35/66
21/10/2022, 18:42 Software Testing

Relational Operator Replacement: <,>,<=,>=,=,!= is replaced by

each of the others and by falseOp and trueOp where falseOp
always returns
Conditional false andReplacement
Operator trueOp always
: Eachreturns true of logical
occurrence
operator &&,||,& - and without conditional, | - or without condition,
not - ^ is replaced by each pf the others. Additionally falseOp,
trueOp, leftOp, rightOp are also present
Shift Operator Replacement: Each occurrence of ← , , > is
replaced by another, and also leftOp which returns left operand
unshifted
Logical Operator Replacement: Bitwise logical operators are
replaced by each other: &, |, ^(xor) and also by leftOp,rightOp,
true,false
Assignment Operator Replacement: +=,-=,/=,*=,%=, ← =, =
replaced by each other
Unary Operator Insertion: Unary operators are
+,-,conditional,logical ~ is inserted before each expression
Unary Operator Deletion: Unary operators are
+,-,conditional,logical ~ are deleted from expressions
Scalar Variable Replacement: Replace each variable reference
with another variable of the same type and within the scope
Bomb statement replacement: replace each statement with bomb
which signals failure
Mutation testing vs graph and logic based testing
Mutation is the strongest test criteria so subsumes a good amount of
other criteria
Mutation operators can be picked such that it subsumes particular
coverage criterias
Mutation operators that ensure coverage of a criteria are said to yield
the criteria
Typical coverage criteria impose a local requirement, every branch is
to be executed. doesnt talk about inputs
Mutation tetsing imposes a global requirement, incorrect output must
be produced
Mutation testing has stronger requiremenets that other coverage
criteria

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 36/66
21/10/2022, 18:42 Software Testing

Weak mutation: mutations not equal at infection but equal at

propogation stage
Mutation testing subsumes node coverage. Draw cfg of the program
and to target a particular node, add a bomb there and test case visits
the bomb statement
Mutation testing subsumes edge coverage because mutation
operator to be applied to subsume edge coverage is to replace
logical predicate with true and false
Test case must take false branch to kill true mutant and take true
branch to kill false mutant
Mutation testing does not subsume prime path coverage etc
Mutation coverage subsumes predicate coverage since it is the same
as edge coverage
Mutation testing also subsumes clause coverage and not
combinatorial coverage
Clause coverage:each clause must be tested to be true and flase.
Relational, conditional and logical operator replacement will make
each clause in each predicate true and false
To kill true mutant test case must cause clause and predicate to be
false and to kill a false mutant, test case must cause clause and
predicate to be true
For example if a mutant for a^b is a^true, then in the test case b is
false to kill the mutant
Mutation testing subsumes GACC, but not CACC and RACC
Only 1 mutation operator at a time so no CACC and RACC
Mutation testing subsumes all-defs
Mutation applied is to delete all variable definitons
Grammar coverage and mutation coverage

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 37/66
21/10/2022, 18:42 Software Testing

Mutation Testing
Mutation testing at integration level: Integration mutation and is also
known as interface mutation and creates mutants on connections
between components
Integration mutation operators
Change calling method by modifying parameters sent to called
method
Change calling method by modifying call
Change called method by modifying values that enter and leave
the method

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 38/66
21/10/2022, 18:42 Software Testing

Change called method by modifying statements that return from

the method (only return statements)
There are 5 interface mutation operators
Integration parameter variable replacement (IVPR): Each parameter in
method call is replaced by each other variable with compatible type
and in the scope. In OO, replace primitive type vars and objects
Integration unary operation insertion (IUOI): Each expression in
method call modified by inserting all possible unary operators in front
and behind the variable in parameter
Integration parameter exchange (IPEX): Each parameter in method
call is exchanged with each parameter of compatible type in that
method call ex add(a,b) becomes add(b,a)
Integration method call deletion(IMCD): Each method call is deleted.
If the method returns a value and is used in an expression then
constant value replaces it. If method returns obbject, method call
replaced by new() so new empty object created
Inegration return expression modification (IREM): Each expression in
each return statement in a method is modified using unary operator
insertion and arithmetic operator replacement
Object oriented conecpts for integration testing
Encapsulation: abstraction mechanism to enforce information
hiding. Objects can restrict access to member variables and
methods by other objects. Java has 4 access levels, private,
protected, public and default(package)
Inheritance: subclass inherits from parent class and can inherit
variables and method and can also inherit from ancestors. Every
class can have only one parent in java. super. can access parent
variables and methods.
Method overriding: Allows method in subclass to have same name
and args as parent, and it allows methods to be redefined
Variable hiding: defining a variable in a child class that has same
name and type as inherited variable so inherited variable hidden in
child class
Constructor is a method to create an object and takes arguments.
super keyword used to explicitly call it and this clal must be first
statement in derived class constructor with the correct
parameters
https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 39/66
21/10/2022, 18:42 Software Testing

Polymorphism: attributes and methods. They use dynamic

binding. Object has a declared type and an actual type. actual
type can be declared type or any descendent
Polymorphic attribute is an object reference that can take various
types
Polymorphic method can accept parameters of different types by
having parameter of object type
Overloading:Same name for constructor or method but different
signature (arguments). It occurs for methods within a class
Instance and class variables are associated with a class. Instance
variables belong to an object and every instance has own copy of
variables and changes reflect only in that instance. Class variables
are static and there is only 1 copy which is shared amonst all
instances. Class variables are declared with static. local variables
declared within methods
Mutation testing for integration
Mutation operators for OO features
Access modifier change(AMC): Access level for each instance
variable and method changed to other access levels. Ensures
accessibility is correct. AMC mutant killed only if new access level
denires access to another class or allows access that casues
name conflict
Hiding variable deletion(HVD): Declaration of overriding or hiding
variable is deleted. References to that variable then access parent
definition
Hiding variable insertion(HVI): Declaration is added to hide
declaration of variable in ancestor. Mutant can be killed only by
test cases that can show that reference to overriding variable is
incorrect
Overriding method deletion (OMD): Each entire declaration of the
overriding method is deleted so parent method is used
Overriding method moving(OMM): Each call to an overriden
method is moved to the first and last statements of the method,
and uo and down one method. Overriding methods in child call
mathod in parent so call may be at the wrong time so by moving
around the call checks if call is at wrong time

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 40/66
21/10/2022, 18:42 Software Testing

Overriding method rename(OMR): Renames parents verisons of

the methods that are overridden in a sub class so that overriding
doesnt affect parents method.
Super keyword deletion(SKD): delets each occurrence of super so
reference will be to local and not to ancestor
Parent Constructor deletion(PCD): Each call to super constructor
is deleted. Therefore, default constructor is used. to kill these
mutants test case where default constructor causes incorrect
initial state should be found
Actual Type Change (ATC): Actual type of a new object is changed
in the new() statement. Causes object reference to reer to an
object of a type that is different from the original actual type. New
actual type must be in same tyoe family of original actual type
Declared/Parameter type chande (DTC/PTC): The declared type of
each new object/each parameter object changed in the
declaration. New declared type muct be ancestor of original type.
To kill such mutants, test case must cause object behavior to be
wrong with new declared type
Reference Type Change (RTC): Right side objects of assignment
statements changed to refer to objects of compatible type. FOr
ecample if Integer os assigned to refer to Object, replace to String
since both are from Object
Overloading Method Change (OMC): For each pair of methods
that have same name, bodies are interchanged. Tests errors
relating to overloading methods invoked wrongly
Overloading method deletion(OMD): Each overloaded method
declaration is deleted one at a time. Ensures coverage of
overloaded methods, all must be invoked atleast once. If mutant
works correctly even after deleting, then error. Otherwise,
incorrect method would be invoked or incorrect parameter tyoe
conversion
Argument order change (AOC): Order of arguments in method
invocatino us changed to be the same as that of another
overloading method so different method is called
Argument number change (ANC): Number of arguments in method
invocations changed so that same as another overloading method.
Therefore can ensure programmer did not invoke wrong method

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 41/66
21/10/2022, 18:42 Software Testing

this Keyword Deletion (tkd): Each occurrence of this is deleted.

Checks if memer variables are used correctly
Static modifier change(SMC): Each instance of static modifier is
removed and is added to instance variables so checks if instance
and class variables are correct
Variable initialization deletion (VID): remove initialization of each
member variable. Member variables are initialized to the default
values.
Default constructor deletion(DCD): Delete each declaration of
default constructor(constructor with no parameters). ensures that
user defined constructors are implemented properly
Mutation testing grammars and inputs
BNF grammars used to define syntax for input of a program or
method
Regular expression may not be enough to express large set so use
BNF
Tests are input strings derived from the grammar
Strings are derived by applying production rules to replace non
terminals with other strings, stop when string of terminals obtained
If grammar not available, derive grammar from informal description
XML is an input format extensible markup language
Describes structured inputs and is used with web apps
built in syntax to describe inputs are called schemas
XML tages are in ↔ Back of card
XML messages must have a single document element with proper
tages and proper nesting
ex:
<title> hello ― title>
Tester should also give malformed or invalid inputs to see if it is
rejected
Input grammars can be mutated to generate invalid inputs
When mutating grammars, mutants are the test cases themselves so
no ground string, or killing of mutants
Mutating grammars

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 42/66
21/10/2022, 18:42 Software Testing

Non terminal replacement: every non terminal in production is

replaced with another non terminal
Terminal replacement: every terminal symbol in a production is
replaced by other terminals
Terminal and non terminal deletion: Every terminal and non
terminal in a production is deleted
Terminal and non terminal duplication; every terminal and non
terminal is duplicated one at a time
Above operators can also be used in XML
Mutations when applied to program result in programs which can be
killed by test inputs, mutation applied to inputs directly produces test
inputs
Encapsulation: Access levels in Java

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 43/66
21/10/2022, 18:42 Software Testing

Testing of web applications

Web application is deployed (available worldwide) on the web
Requests accepted used HTTP
Like client server application, client runs on browser
Web service is a web deployed program that accepts XML messages
wrapped in SOAP
no UI
service must be published so that other applications can use it
Message passing interface used for loosely coupled components to
communicate
Webapp is distributed
Each component can be developed using a completely different
technology
WAYS OF DEPLOYING A WEB APP
bundled(pre install on computer) ex:OS
shrink-wrap(buy and install) ex: antivirus
contract(access to software depends on contract period)
embedded(on hardware device, communicates with sensors
actuators)
web software, deployed through HTTP
ARCHITECURE OF WEB APPLICATION
presentation layer: UI
data content: data access happens
data representation: data stored and retrieved form memory
Data storage: permanent data storage
Each layer must be tested seperately and system level testing must
also be done
ISSUES WITH WEB APPLICATION
must be fast(not slow, no bugs)

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 44/66
21/10/2022, 18:42 Software Testing

must be of high quality

HTTP is a stateless protocol, each request is independent
state managed using cookies
html forms created dynamically so UI can change
flow of control can be controlled by user by back buttons etc
servers dk where the request comes form
new components can be added during execution
webapp extremely loosely coupled because coupled through
internet, coupled through diverse hardware, diverse programmin
glanguages
OUR TECHNIQUES VS TESTING WEB APPS
graphs dont apply for system level testing of web app, can use for
one component alone since program is distributed across internet
state behavior is hard to model since there is server state, client
state
HTML UI has low controllability
hard to get access to server side
not clear what logic predicates can be used
no model for mutation operators
CATEGORIES OF WEB applications
static
dynamic
web services
HTML can be stored as static HTML file or generated by JSP,ASP
dynamically
Web site is collection of web pages
TEST CASE FOR WEB APP
sequence of interactions between components on clients and
servers

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 45/66
21/10/2022, 18:42 Software Testing

depicted by a path of transitions (but challenging for dynamic)

TESTING STATIC WEB APP
not program testing but testing HTML connections
check if links are valid
main ussue is ensure there are no dead link(hyperlink to non valid
URL)
non-functional parameters
must do load testing(everyone logs in)
performance evaluation
access control (authentication)
GRAPH MODEL OF STATIC WEB site
nodes are web pages
edges are HTML links
BFS used to build graph, by starting with intro pages and
recursively do BFS for all links on intro pages
graph then tested for edge coverage (traverse each edge)
Testing of web applications and web services contd (client side)
Testing dynamic web apps
web server is where all software resides, and web page is
dynamically generated based on client interaction
testing can be done on client or server side
Client side testing (black box)
Tester has no access to data on the server
Client and server are completely seperate
Client provides inputs (html form elements)
Inputs can be chosen or generated
Generated from previous user sessions (very effective)
Supplied by tester
Generated randomly (not very effective)
Bypass testing: values that violate constraints on inputs

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 46/66
21/10/2022, 18:42 Software Testing

Problem is not all screens are accessible

Test value selection
Values within domain are needed. Not efficient to generate all
possible inputs
Generating random values is not effective
Very hard to automatically generate values
User data might be innefective from testing point of view
Tester supplied inputs might be expensive
Study the application and construct a set of values
Bypass testing
Webapps impose constraints on inputs through HTML forms
Client side validation using script (check input data before
sending to server)
Use explicit attributes with html form tags
Bypass testing creates inputs that violate validation rules and are
directly sent to server thereby bypassing client side validation
let tester save and modify the HTML
Remove any client side validation scripts or attributes added to
tags to restrict inputs
Can see how the server reacts to these invalid inputs
Bypass testing can also be done at the server side
safer to do it at the client side since server data might get
corrupted
Validation types
HTML
length
value (preset values)
Transfer mode (get or post)
field elements (preset field)
target url
Scripting Constraints
data type conversion
https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 47/66
21/10/2022, 18:42 Software Testing

data format validation (ex: only pdf files, only zip files)
data value (btwm 1 and 10)
Inter-value,Inter-Field (match credit card and expiry date)
Invalid characters
Inter request data fields (cookies, hidden)
Security violation
empty string
commas
tag symbols
dir paths
special characters
Testing of web applications and web services contd (server side)
Server responses
E rrors at server could cause permanent database damage if not
recognized (Exposure)
Valid responses
Ignores invalid input
Provides error message which is generic or specific
Faults and failures: invalid input cause abnormal server error
Server side testing (white box)
use normal graph models if server code is available
control flow graph only used with static models
Presentation layer of web app is used for testing
2 graph models for software in presentation layer
Component interaction model
application transition graph
Atomic sections
We look at server side code present in the presentation layer
sections are dynamically generated and sent from server to the
client
Atomic section has the property that if one part of the section is
https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 48/66
21/10/2022, 18:42 Software Testing

sent to the client, the entire section is.

Atomic section can include javascriot
atomic section can be empty
Content variable is when data is generated dynamically. it
provides data to an atomic section
Graph models
Component interaction model (CIM)
models individual components
combines atomic sections
intra-component: interactions within a component
nodes are atomic sections
transitions tell how to move from one section to another
Application transition graph(ATG)
Each node is a CIM
edges are transitions among CIM
inter component
Component expressions
Atomic sections are combined to model dynamically generated
web pages
4 ways to combine and generate component expressions:
Sequence P1.P2 (P1 then P2)
Selection P1|P2 (p1 or p2)
Iteration P1* (P1 0 or more times)
aggregation P1 {P2} (p2 is included in p1)
algos can automatically generate these expressions
Transitions in Component interaction model
Simple link transition (HTML Link)
Form link (Form submission)
Component expression transition (Execution of a component
causes a component expression to be sent to client)
Operational Transition (sudden unplanned input; ex: back, forward,

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 49/66
21/10/2022, 18:42 Software Testing

refresh, user edits url, broswer reloads from cache)

Redirect transition (server side transition not visible to user)
Video for CIM example and ATG example 20 minutes
ATG cannot be generated automatically
There is no data-flow based testing for web apps
Testing of OO Applications
Abstraction
Classes used to represent abstraction
inheritance, polymorphism, dynamic binding also support
abstraction
new types created by abstraction are descendants of existing
types
2 new types
extension: class extends parent if new method name
introduced and doesn't override any method in ancestor
class refines parent if new behavior provided which is not in
overriden method, and doesnt call overriden method
inheritance
sub type inheritance (aka substitution principle): If class B uses
sub-type inheritance from class A, it is possible to freely
substitute any instance of B for A and still satisfy a client of A. B
has a is-a relationship with A
sub-class inheritance: Descendant can reuse methods and
variables from ancestor without having to ensure descendant
instances meet ancestor specifications
polyphormic methods
If class B inherits from class A, and A and B defne a method m, m
is polymorphic
if an object x is declared to be of type A, then during execution x
can be of type A or B and the version executed depends on the
current actual type of the object
Collection of methods that can be executed are called
polymorphic call set: ex: {A:m(),B:m()}
4 levels of class testing

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 50/66
21/10/2022, 18:42 Software Testing

intra-method: testing a particular method

inter-method: interaction between methods are tested
intra-class: testing within a class
inter-class: interaction between classes is tested
Visualizing OO interactions
Assume a class encapsulates all state info required as a collection
of state variables
Class is static entity
Interactions between clsases and methods are difficult to visualize
If a class V extends W and there is a method m which is overriden
in V, and if a new object o is created and o=new V() and o=new
W() are executed conditionally based on the value of another
variable b, whether m in V or m in W is executed deponds on the
value of b so we cannot visualize which method is executed
Data flow anomoly: a variable needed by one method might not be
available because it may have been defined in the parent class
method which was not executed and instead an overriden child
class method was only executed
Yo-Yo Graph
Understanding which version of a method will be executed is
difficult adn executions can bounce up and down between
inheritance levels
Yo-Yo graph has a root and descendants. Nodes are methods,
edges are method calls
Methods include new, inherited and overrden methods
directed edge is from caller to callee
Each class in graph is given a level in the graph and it shows the
actual calls made if an object has the actual type of that level.
these are in bold arrows
Dashed arrows are calls that cannot be made due to overriding
example in ppt
Faults in OO programs
Less static determinism as when one method calls another,
overriden can happen so it is not static and is dynamic

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 51/66
21/10/2022, 18:42 Software Testing

Inheritance and polymorphism yield vertical and dynamic

integration
Assume that Instances of descendant can be substituted for
instances of tha ancestor
9 kinds of faults/anomolies
ITU: inconsistent type use - descendent class does not
override any inherited method. if class C extends T and C adds
new methods, object can be used as both T and C and
methods in T might make object go to state that is inconsistent
for C
SDA: State definition anomaly - state interactions of
descendant not consistent with ancestor. Class X extends W
and X overrides methods in W, but variables that are defined by
a overriden method may never be defined because the
overriding method is executed instead and other functions may
use the variable that must have been defined by the overriden
method
SDIH: State definition inconsistency - Local variable introduced
in class definition and name is same as another inherited
variable. Local variable is only referred to unless super.v used
(hidden variable). Anomoly if method defines local variable and
sends to another method in a different class which is expecting
inherited variable from ancestor
SDI: State defined incorrectly - overriding method defines
same variable that overriden method defines.
SVA: State visibility anomaly: X extends W and Y extends X. W
may have a private variable which is not visible by descendant
but needs to be used by descendant overriding method
IISD: indirect inconsistent state definition - descendent adds
extension method that defines inherited state variable
ACB1: Anomalous construction behavior 1
ACB2: Anomalous construction behavior 2
IC: Incomplete construction
Symbolic Testing
Program proving: Any input is given and programs execute correctly.
Involve formal methods

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 52/66
21/10/2022, 18:42 Software Testing

Program testing: only a set of testcases are used

Program can never be proved to be correct as we cannot
exhuastively test usng all possible inputs. w can only claim program
works right for the inputs we have tested. no claims about test cases
we have not used.

Formal methods are mathematical techniques based on deriving

formal models from program. Formal models include model checking,
theorem proving, program analysis
Program is not even executed in program proving and program is just
proved to meet specification
Not all proofs can be automated
Symbolic execution is in between proving and testing. It executes a
program symbolically for a set of inputs
Each symbolic execution is equal to a large number of normal test
cases
Symbolic values ex: alpha1 is a placeholder for a concrete value (can
be thought of as a variable)
PC - path constraint : conditions that collect predicates related to
RIPR (marked as true if it is reachable)
Symbolic execution tree: Has conditional statements and test case
which make the condition true and false
Variables are in terms of symbolic values as symbolic expressions
Symbolic state (sigma): symbolic expressions for each variable at a
point of time
Symbolic path constraint: predicate formula to reach a statement
Symbolic execution generates test input for each execution path of a
program
Execution path is a sequence of true and false where true/false at the
ith position in the sequence denotes that the ith conditional
statement in the path took the then(for true) and else (for false)
symbolic state (sigma) is initially empty
At a read statement (for example parameter passing to the function)
symbolic values are assigned to each variable and the mapping is

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 53/66
21/10/2022, 18:42 Software Testing

added to sigma
At an assignment statement v=e, symbolic expressions are assigned.
Sigma is updated by mapping variable v to sigma(e), which is
obtained by evaluating e in the current symbolic state
PC is initialized to true at the beginning of symbolic execution
At a conditional statement if(E) then .. else .., PC is PC ^ sigma(e) for
then branch and PC ^ !sigma(e) for the else branch
Each path constraint (predicate formula) is solved to find a suitable
assignment of concrete to symbolic values and if it is satisfiable then
symbolic exec continues. Otherwise, it terminates. It can also
terminate if an exit statement is reached or error occurs.

A t the end of symbolic execution, PC is solved using constraint

solver. If concrete values are obtained then those are test inputs
When the concrete obtained are used to test, all execution paths are
tested
Symbolic testing with loops
Path constraint for a loop is a sequence of trues followed by a false
which is for when it terminates
Symbolic execution may result in an infitinite number of paths so have
a timeout for time or number of iterations
If the PC generated contains formulas that cannot be solved by a
constraint solver, symbolic execution cannot generate inputs and this
is a disadvantage
Some functions may be used for which code is not available so this is
another disadvantage
Real life programs have many paths so many path constraints and
exploring all paths may not be feasible
DART overcomes disadvantages of symbolic testing
DART - Directed automated random testing or concolic testing
It performs symbolic testing dynamically
It is a combination of concrete and symbolic
Concolic testing generates a random input for the program and
collects symbolic PC along the execution

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 54/66
21/10/2022, 18:42 Software Testing

CUTE,PEX,SAGE are popular constraint solver tools

DART part1
DART is a concolic testing tool
It applies to unit testing phase
DART does symbolic and concrete execution
DART can explore all paths when feasible
DART can automate unit testing
DART automatically extracts the interface of a program using static
source code parsing
DART generates a test driver which can give random inputs to the
program
As the program executes, DART collects some information and
generates new inputs through dynamic analysis
DART elmiinated the need to write a test driver as it does it
automatically
DART can detect standard errors
Sometimes through random testing it is unlikely to satisfy the
conditions for an error to be produced
Dart can do inter procedural dynamic tracing: ex: if f(x)==5
where function f returns 2*x, DART will replace f(x)
by 2*x

DART does directed search by starting with the random input, checks
the PC, and if some predicate was made true, it will now be made
false and values are generated by the constraint solver so that other
paths can be explored
DART stops on identifying an error
Execution model of DART helps execute normally and
symbolically(collects path constraints)
Symbolic representation of a variable is its memory address
Memory M is a mapping from address locations m to words which are
the actual contents
M'=M + [ m |-> v] Memory M is updated and only value of
address m changes to v

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 55/66
21/10/2022, 18:42 Software Testing

Symbolic variables are identified by addresses

m can denote the memory address or the variable identified by
address m
symbolic expression is a logical expression with symbolic variables
and constants
examples: *(e,e') is multiplication, <=(e,e'),
negation, *e' is pointer dereference, etc

Semantics of programs must be defined at memory level

Statements are machine instructions at the level of memory
Statement labels are denoted by instruction addresses
special statements used in programs are abort: program error and
halt: normal program termination
a special function at(l,M) gives address of next instruction
evaluate-concrete(e,M) evaluates expression e using values in
memory M and gives a value for e
Inputs to dart are memory locations corresponding to symbolic
variables
input vector assigns an input value to each parameter and defines the
initial value of memory M
A - assignment statements, C - Conditional statements
program execution w is the following regex Execs=(AUC)*
(abort|halt)

DART part2
Execs can be a tree with assignments having one successor and
conditions with 1 or 2, and leaves are abort or halt
symbolic memory S maps memory addresses to expressions
Whenever a path constraint is not linear, algo uses concrete values
and not symbolic
Symbolic evaluation of expressions
just a variable, then directly return symbolic expression which is
S(m) if m is in S and M(m) otherwise
*(e',e") where * can be any arithmetic
operation :operands e' and e" so each should seperately be
evaluated first. if either of the 2 evaluated expressions is not a

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 56/66
21/10/2022, 18:42 Software Testing

constant then non linear expression is obtained so ust do concrete

evaluation. If both are constants then do concrete evaluation.
Otherwise if 1 is a constant, evaluate that expression and return
case *e' : pointer so first evaluate e', and then see if a constant
is obtained. if it is a constant and is in the domain S, then S*C ,
otherwise M( *c ). if it is not a constant then evaluate concrete
all_locs_definite variable in symbolic eval algo: it is set to 0 if the
value of a variable is not known. for example when a program
dereferences a pointer whose value depends on some input
parameter
substituting concrete values overcomes unsolvability of pc by
constraint solver sometimes
DART test driver algo explanation (look at algo in ppt, not sure if
needed)
Repeat loop while all linear and all locations are defined
DART keeps a stack , input vector and boolean var directed which
is for directed search
instrument program is a function called in the test driver with
stack and input vector
DART can run forever
instrument program initializes inputs with random values in input
vector if not initialized
it initializes memory and sets up symbolic memory, sets initial
program counter
if a new assignment statement is encountered, it is symbolically
and concretely evaluated and memory location is updated
for conditional statement, concrete evaluation done and checks if
it should take then or else branch and updates path constraint and
stack accordingly
stack keeps track of path constraint that was last added
If halt is encountered, must solve path constraint, calls a
constraint solver
stack has info related to each conditional statement.
if DART prints bug found, then input that causes abort. If
terminates without printing then no input that causes abort.

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 57/66
21/10/2022, 18:42 Software Testing

otherwise it runs forever

Given a C program to test, parts of DART that need to be understood
are interface extraction, random test driver, implementation of
directed search
DART part3
DART for C inteface extraction
DART for C random test driver
main function of test driver initializes all external variables and
args of the top level function with random values
number of times that the top level function needs to be called
iteratively in a single run is specified by the tester
driver also has code simulating external functions such that
whenever an external funcion is called, random valye of the
functions return type is returned by the simulated function
once the test driver has been generated, it can be combined with
the C program being tested to form a self executabl program
DART for C implementation of directed search
Symbolic calc is performed using CIL, a OCAML appl for parsing
and analyzing C code
DART uses constraint solver IP_Solve to solve linear constraint
using real and integer programming techniques
OO call coverage criteria specific to integration testing
Coupling variables in OO: pair of method calls within body of method
under test, made through common instance context, wrt set of state
variables commonly referenced by both methods, consists of atleast
one path between method calls wrt state variable
Must identify points of integration
OO Defs and uses can be indirect. We dont know which version is
exec in which method so must consider all methods that can execute
Polymorphic call set: set of methods that can potentially execute as a
result of a method call through a particular instance context
testing goals: how a method can interact with instance bound to an
object. When an object o is bound to an instnce of w, it is different
from when o is bound to z. Need to consider set of interactions
possible, need to test all couplings with all type bindings
https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 58/66
21/10/2022, 18:42 Software Testing

COverage criteria
All coupling Sequences (ACS) - includes all coupling variables: For
every coupling sequence Sj in f(), there is atleast one test case t
such that there is a coupling path induced by S(j,k) that is a sub
path of the execution trace of f(t). Atleast one coupling path must
be executed. Does not consider inheritance and polymorphism
All poly classes(APC) - includes one test case for every possible
type subs and for every type the object can bind to: For every
coupling sequence S(j,k) in a method f(), and for every class in the
family of types defined by the context of S(j,k) there is atleast one
test case t such that when f() exec using t, there is a path p in the
set of coupling paths S(j,k) that is a sub path of the execution
trace of f(t). There is atleast 1 test case for every type the object
can bind to. Subsumes ACS.
All coupling defs and uses (ACDU): For every coupling variable v in
each coupling S(j,k) of t, there is a coupling path p induced by
S(j,k) such that p is a sub-path of the execution trace of f (t) for at
least one test case t. Does not consider inheritance and
polymorphism . Every last def reaches every first use so they must
be tested .
All-Poly-Coupling-Defs-Uses (APCDU): Every last to every first
use with inheritance and poly
All-Poly-Coupling-Defs-Uses subsumes All poly classes(APC) and All
coupling defs and uses and both of these subsume All coupling
Sequences
Testing Mobile Applications
Mobile application testing is testing of software meant to run only on
handheld devices
Usability very important and it should be consistent accross all
platforms
Can be automated or manual
Apps are either pre installed or installed using distribution platforms
Testing of wearable applications is also related (watch apps)
Challenges:
Wide range of OS and platforms - Device fragmentation

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 59/66
21/10/2022, 18:42 Software Testing

Multiple devices must also be used to test

Different screen sizes and hardware devices, cannot buy each
phone
Large number of network providers (above 400) and some use
common standards such as GSM but some use less common
standards and different infrastruture
Executing a test script across devices is challenging since devices
differ in input methods, and single script ccannot work in all
devices
Mobile apps need to be tested for downloadability from a
particular store
Compatibility across devices and platforms is important
mobile vs desktop
Desktop, application tested on cpu but for mobile tested on
mobile handset
Mobile screen size and memory less than desktop
Mobiles use cellular or wifi but desktop uses only broadband or
dial up
test script can be used for desktop but not for mobiles
Types of mobile app testing
Functional testing: ensures app meets requirements and are
conducted using UI and call flow
Usability testing: checks if good UI experience and easy to use.
Tests accross devices and sizing
Performance testing: checks performance under certain
conditions. ex low memory low battery bad network. it is done on
client and server side
Compatibility testing: Testing on different browsers, diff devices,
diff OS, resolution
Memory related testing: ensures that appl manages memory and
doesnt slow down device. Memory constraing should be there and
temp files should be deleted
Installation testing: Some are pre installed and some have to be
downloaded. this testing covers updating and installation
Interrupt testing: Application might face interrupts such as
https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 60/66
21/10/2022, 18:42 Software Testing

incoming call, sms, removed battery, charge phone, so check if

goes to correct state and then resumes
Security testing: apps used for bank transactions so check for
vulnerabilities related to hacking, access control. There are
standards that need to be met
Location testing: connectivity changes with location so must
check app functionality after these changes but difficult to mimic
different locations
Emulators used to test system level features
Emulator is a software that runs a software from one environment
fom another without changing software. duplicates features of real
system
3 emulators
Device emulator provided by device manufacturer
Browser emulator: simulates mobile browser
OS emulator: provided by OS firm
Non functional system testing
Non functional begins only at system tetsing phase
Non functional system tests
Interoperability: whether system can interoperate with 3rd party
products. includes compatibilty.
2 types of compatability
Forward: older version doc should be compatible with
newer version
Backward: newer version doc should atleast be opened
using old version
Security: Checks if system protects data and maintains seciruty
related functionality. CIA ensured (confidentiality, integrity,
availability) and also deals with autentiation (validation of
credentials) and authorization (permission).
types of security testing
Verify only authorized access permitted
Verify correctness of enc and dec algos

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 61/66
21/10/2022, 18:42 Software Testing

illegal file reading

virus checker mustnotprevent
allowedvirus
(unathorized)
identify back doors through which access to system can be
gained
Verify authentication protocols, client server communication
Reliability: ability to keep operating over long periods of time.
includes hardware and software reliability
Scalability: verify that system can scale up to its engineering
limits. max magnitude of users that can be used while
performance requirements are still met. limitations to scale up are
because of memory, cpu speed, bandwidth. `
Documentation: verify technical accuracy and readability of the
documentations, online help, tutorials
performed at 3 levels
Read test: check clarity, organization, flow, accuracy
Hands on test: seek online help and see how useful it is
Functional test: instructions in doc are followed to see if
system works as expected
Tests performed
grammar test
graphics usage
glossary
proper index
online and printed doc versions should be consistent
very installation procedure by executing step by step
verify troubleshooting using actual error scenarios
Regulatory: Each country has regulatory bodies based on the
country. Qualiy standards must be met. Ex: FCC,CE,CSA
Performance: Sees how responsiveness and stability is at different
loads, Measures attributes such as scalability, reliability
Types
Load testing: Understand behavior at a specific load
Stress testing: to find upper limit capacity and checks what

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 62/66
21/10/2022, 18:42 Software Testing

happens if load
Soak testing akagoes above the
endurance maximum
testing: continuous expected load
is used and checks for memory leaks
Spike testing: Suddenly increase number of users. It is a type
of stress testing
Goals
Must show system meets performance criteria
compare 2 systems and check which is better
identify which parts of the system caused bad performance
Performance testing always includes
Number of users
response time
Throughput
tools to create and run performance scripts
HP load runner
NeoLoad - good for web and mobile
Apache jmeter: good for web apps, open source
Rational performance tetser
Gatling: good for web apps, open source
System running scripts needs to be monitored using special
scripts or external devices
Regression Testing
Regression testing is validating modified software to detect if new
errors have been introduced into code that was previously tested
It is a black box technique and is expensive
After release, software maintained by developers and during
maintenance, modifications done to code
Let P be a program and P' is the modified program. T is test suite for
P. steps of regression test
1. Select T' which is a subset of T for P'
2. Test P' with T'
3. If needed create new test cases T'' for P'

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 63/66
21/10/2022, 18:42 Software Testing

4. Test P' with T"

5. P' is the new version and P is not kept so keep new test suite from
T,T',T" for P'
Step 1 deals with regression test selection
Step 3 deals with coverage identification problem
Step 2 and 4 address test suite execution problem (problem of
efficiently executing test cases and checking results)
Step 5: test suite maintenance
Regression test selection is applicable when specifications have
changed and when they have not changed
If specifications have changed, then find out which test cases are
obselete for P'. These can be removed and regression testing done
on remaining test cases
Obselete for p' if the test case specifies an input to p' that is invalid
for p'
Test selection requires domain specific knowledge, selected based
on area of frequent faults, include area where many changes made,
based on criticality
Test selection techniques
Minimization test selection techniques: T' is as minimal as
possible. it is undecidable.
Data flow coverage based regression test selection: select cases
that test interactions that have been modified. every def use pair
in P' that is new or deleted from P or modified is tested.
technique is not safe if it fails to select a tes t case that would
have revealed a fault
If safety conditions explicitly mentioned can be satisfied, then
safe regression test selection guarantees that T' contains all
test cases in T that reveal faults in P'
Random test selection: randomly select test cases and is often
useless
Retest all uses all T to test P', but some new test cases may be
needed.
Different test selection techniques create trade offs between costs of
selecting and executing and detecting faults

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 64/66
21/10/2022, 18:42 Software Testing

Choice if test selection technique affects how cost effective

regression testing is
Heavily automated, regression tools are record and playback type.
test case recorded by navigating through the program under test and
verified by checking results

OO Subsumption

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 65/66
21/10/2022, 18:42 Software Testing

https://www.remnote.com/w/635287b773d6cd59ed18f547/Software-Testing-OPik7onwKsHeo76aL 66/66