Transcript Intro

Automatic Test-Data
Generation: An Immunological
Approach
Kostas Liaskos
Marc Roper
{Konstantinos.Liaskos, Marc.Roper}@cis.strath.ac.uk
TAIC PART 2007
Problem
Automated data-flow coverage of OO
programs
Particularly challenging – Need to
generate program as well as test data
Example of test case format
CUT cut = new CUT(3);
A a = new A();
a.meth2(4, 6);
cut.meth(a, 9);
CIS, Software Systems Group
2
Initial study
6 classes from the standard Java library
were tested
Good levels of data-flow coverage, but
always lower than branch/statement
2 categories of problematic test targets
were identified
• Equivalent: d-u pairs that correspond to the
same code structure
• Subsequent: the satisfaction of a test target
is strongly related with another
CIS, Software Systems Group
3
Proposed solution
 Utilization of an Artificial Immune System
(AIS) algorithm:
•
•
learning and adaptation implemented by
affinity maturation  combination of global &
local search  may be beneficial to tackle
subsequent test targets
immunological memory using memory cells
 good solutions are stored for future use
 may be beneficial to tackle both types of
problematic test targets
CIS, Software Systems Group
4
Clonal selection algorithm
 Key features:
• Mutation rate inversely proportionate to affinity
• Cloning rate proportionate to affinity
• Memory cells
 AIS Algorithm vs. GA
• Similarities:
Population-based algorithms
Selection mechanism
Mutation
• Differences:
No crossover is used
CIS, Software Systems Group
5
Human immune system
activation
selection
proliferation
differentiation
high affinity
selected
cell death
low affinity
no selection
CIS, Software Systems Group
6
Main challenge
Built a generic framework
 How do we mathematically represent
immune cells and molecules?
 How do we quantify their interactions or
recognition?
 How do we form the procedures of the
variety of the observed functions in the
human immune system?
CIS, Software Systems Group
7
Proposed framework
Representation:
 B-cells & T-cells represented as the
encoded test-cases
 Receptors of the immune cells
represented as encoded executed paths
 Antigens represented as test targets
Affinity computation:
 Binary distance between a receptor and
an antigen
CIS, Software Systems Group
8
Preliminary experiment


Test object: triangle classification program
Aim: validate our framework & experiment with the
parameters:









N (size of the Ab repertoire) = 20
m (size of the memory set) = 18
r (remaining Ab repertoire) = 2
d (set of d lowest affinity Ab’s that will be replaced by new
individuals) = 1
Ngen (maximum number of generation) = 100
n (number of highest affinity individuals to be chosen) = 10
β (multiplying factor for the total number of clones) = 1
Full path coverage for these parameter values
The algorithm failed to cover the “equilateral” testtarget in all cases with different settings
CIS, Software Systems Group
9
Conclusions & Future Work
 Our paper introduces a framework for the
application of AIS algorithms to the problem of
automatic test-data generation
 A prototype has been implemented
 The next step is to run an extended
experiment using 6 Java classes
 Compare the results with GAs
 Our ultimate goal is to propose a hybrid
AIS&GA algorithm
CIS, Software Systems Group
10