Transcript Dynamic Symbolic Data Structure Repair

PhD Research Proposal
Automatic test case generation for programs
that are coded against interfaces and
annotations or use native code
Mainul Islam
Supervisor: Dr. Christoph Csallner
The University of Texas at Arlington
December 12th, 2012
Outline
•
•
•
•
•
•
•
•
Problem Description
Motivation
Limitation of Current Approaches (with example)
Thesis Statement
Background
Solution Approach
Experimental Results
Plan of Action
2
Problem Description
• Current state of the art tools are not very good at
generating test cases when the code under test:
– requires additional pieces of code that are not yet part of
the program.
– uses multiple interfaces, annotations or reflection.
– imposes complex (type) constraints.
– uses native code.
3
Motivation
• Automatic test case generation is important
• At the initial stage of any development the
implementation of some code may not be
available
• Existing techniques (such as Pex and Moles*) are
not very good at generating test cases when the
code under test uses interfaces/annotations,
multiple inheritance and native code.
• Significant number of Java programs use native
code
* http://research.microsoft.com/en-us/projects/pex/
4
Limitation of Current Techniques:
Motivating Example 1
public @interface A { /* … */ }
public interface I { public int m1(); /* … */ }
public interface J { public int m2(); /* … */ }
public class C {
public static void foo(I i) {
int x = i.m1();
if ( i instanceof J ) {
J j = (J) i;
int y = j.m2();
}
}
}
To reach this block of
code ‘i’ must be an
instance of I, as well
as an instance of J
if ( i.getClass().isAnnotationPresent(A.class) ) {
// ..
To reach this block of
}
code ‘i’ must be an
instance of I, as well
as annotated with A
5
Motivating Example 2
(Dependency on Native Code)
Java code
C++ code
public class C {
public native boolean
isDivisible(int x, int y);
public static void NativeTest(int a, int b) {
boolean divisible =
new C().isDivisible(a, b);
if (divisible) {
// …
}
}
}
bool isDivisible(int x, int y) {
if ( y*(x/y) == x )
return true;
return false;
}
To reach this
block of code ‘a’
must be divisible
by ‘b’
6
Motivation: Patterns in Real World Program
7
Pattern 1
R m(…, T t, …) {
// …
if ( … (t instanceof X) )
// …
}
•
•
•
•
•
‘T’ an ‘X’ are non-compatible
‘m’ is user-defined
At least one of {T, X} is an interface
None of {T, X} is final
At least one of {T, X} is a user-type
8
Thesis Statement
• We can generate automatic test inputs and
systematically increase code coverage compared to
existing techniques specially when the code under
test:
– requires additional pieces of code that are not yet part of
the program.
– uses multiple interfaces, annotations or reflection.
– imposes complex (type) constraints.
– uses native code.
9
Background: Symbolic Execution
• Systematically explore all feasible
execution paths
• Initialize the input with symbolic
values and execute the program
over symbolic values
• At conditional statements check
if either of the branches can be
taken
• For each path get an
accumulated path condition
If (S) then … else …
C
S
true
C` = C ⋀ S
false
C` = C ⋀ ⌝S
10
Dynamic Symbolic Execution by Example
taken with permission from Nikolai Tillmann (Microsoft Research)
public static void TestMe(int a[]) {
if (a == null) return;
if (a.length > 0)
if (a[0] == 123)
throw new
Exception(“Error”);
}
Choose Next Path
Solve
Constraints to Solve
Execute
Input
(a)
null
a == null
F
T
a.length > 0
F
a != null &&
a.length > 0
T
a[0] == 123
F
a != null
T
a != null &&
a.length > 0&&
a[0] == 123
Done: No Path Left
Observed Constraints
a == null
{}
a != null &&
!(a.length > 0)
{0}
a != null &&
a.length > 0 &&
a[0] != 123
{123}
a != null &&
a.length > 0 &&
a[0] == 123
11
Sub-/Supertype relation in Java
• Java defines a binary sub-type relation
• If type B implements/extends type A then,
– A is a direct super-type of B
– B is a direct sub-type of A
Reflexive: A is also a subtype of itself
Transitive: if B is a subtype of A and C is a
subtype of B then C is also a subtype of A
12
Sub-/Supertype relation in Java
• A class has one direct class super type and
arbitrarily many interface super types.
• Exceptions:
type object – has no direct super type
type null – has no direct sub type
13
Our Solution Approach
• Introduce Dynamic Symbolic Mock Classes
Technique implemented on:
 Dsc1 – Dynamic Symbolic Execution Engine for
Java
 Z32 – SMT solver (from Microsoft Research)
1 - http://ranger.uta.edu/~csallner/dsc/index.html
2 - http://z3.codeplex.com/
14
Solution Workflow
Default Input
values (0, null, …)
Invoke DSE on given input values and
collect path constraints
New Test Cases
(and corresponding
mock classes )
More
Paths
?
No
Stop
Yes
Add mock classes and map each
of them to a constraint literal
Invert one of the collected path
constraints
(Map each reference type to a constraint
literal and encode their properties to build
a constraint system)
Constraint
System
Satisfiable
?
Yes
Map the constraint solver model to new
test cases (and mock classes)
Encode properties (e.g.,
subtype relation) of mock
classes in the constraint system
No
Constraint
System
Satisfiable
?
Yes
No
15
Subtype Constraints
Object
public @interface A { /* … */ }
public interface I { public int m1(); /* … */ }
public interface J { public int m2(); /* … */ }
Annotation
I
J
C
A
M
public class C {
public static void foo(I i) {
int x = i.m1();
if ( i instanceof J ) {
J j = (J) i;
int y = j.m2();
}
// ..
}
}
null
A desired
solution
with
Type: M,
Initial
Types in
thenew
system
to reach the code block
Constraints:
type(i) subtypeof I
type(i) != null type
type(i) subtypeof J
16
Subtype Constraints
Object
public @interface A { /* … */ }
public interface I { public int m1(); /* … */ }
public interface J { public int m2(); /* … */ }
Annotation
I
J
C
A
M1
public class C {
public static void foo(I i) {
int x = i.m1();
// ..
if ( i.getClass().
isAnnotationPresent(A.class) ) {
// ..
}
}
null
A desired
solution
Type: M1,
Initial
Types with
in thenew
system
to reach the code block
Constraints:
type(i) subtypeof I
type(i) != null type
type(i) subtypeof A
17
Subtype Relation Matrix
Solution:
mI = true
mJ = true
mC = false
mA = mAn = false
public @interface A { /* … */ }
public interface I { public int m1(); /* … */ }
public interface J { public int m2(); /* … */ }
public class C {
public static void foo(I i) {
int x = i.m1();
if ( i instanceof J ) {
J j = (J) i;
int y = j.m2();
}
// ..
}
}
null Object An
I
J
C
A
M
x
x
x
x
x
x
0
null
x
x
1
Object
x
2
An
x
3
I
x
4
J
x
5
C
x
6
A
x
x
7
M
x
mAn mI mJ mC mA x
x
x
x
x
x
18
Experimental Results (1)
• Experiments are done on simplified version of
real world code
• C# codes are translated manually
19
Experimental Results (2)
• Experiments are done on original code
• Randoop has several side effects
20
Workflow: to handle Native Code
Default Input
values (0, null, …)
Invoke DSE on given input values and
collect path constraints
New Test
Cases
Stop
No
More
Paths
?
No
Yes
Yes
Invert one of the collected path
constraints and build constraint system
Constraint
System
Satisfiable
?
Native
Code
Invoked?
No
Collect the constraints from the
native code for current input
values
Convert the native code
constraints to Java constraints
Yes
Map the constraint solver model to new
test cases
21
Technique to handle Native Code
In each iteration of the dynamic symbolic execution
of a Java program:
• Check if a native code call is invoked. If yes, start
executing the native code on current input values
• Use any existing tool (such as Klee* for C++ code)
to collect the path constraints of the native code
• Convert the constraints collected from the native
code and merge them with the constraints
previously collected from the Java program
• Solve the whole constraint system using a
Constraint solver and generate test case.
• http://klee.llvm.org/
22
Initial Experiments
In JDK 1.6:
• Total # types: 23799
• Total # of types (have at least one native
method): 381
• Total # of native methods: 2019
• http://klee.llvm.org/
23
Plan of Actions
Time
Action
Plan (to do)
Spring 2013
Implement and evaluate the
technique to handle native
code.
Submit a short paper
Summer 2013
Internship (currently
interviewing)
Join back to UTA in Fall
2013
Fall 2013
Detail experiments of the
technique to handle native
code against the existing
techniques.
Submit the experiment
results to a journal
paper
Spring 2014
Write up and submit
dissertation.
Ph.D. defense
24
List of publications
1. Mainul Islam and Christoph Csallner. Generating
Test Cases for Programs that are Coded Against
Interfaces and Annotations (submitted)
2. Mainul Islam and Christoph Csallner. Dsc+Mock:
A test case + mock class generator in support of
coding against interfaces (In Proc. 8th International
Workshop on Dynamic Analysis (WODA), co-located with
International Symposium on Software Testing and Analysis
(ISSTA), 2010)
25
Thank You!
26
Backup Slides
27
Pattern 2
class P {T t, …}
class Q {
M m(…, P p, …) {
// …
if ( … (p.t instanceof X) )
// …
}
28
Pattern 3
M m(…) {
// …
if ( … (..).foo() instanceof X )
// …
}
29
Related work
Mock classes inferred from Programmer-Written
specification:
•
•
•
•
EasyMock, jMock, Mockito
NMock
Google Mock
SynthiaMock
30
Related work: example with EasyMock
public interface K extends I, J { /* … */ }
public class Test {
public void testFooIsInstanceOfJ() {
K mock = createMock(K.class);
expect(mock.m1()).andReturn(0);
expect(mock.m2()).andReturn(0);
replay(mock);
C.foo(mock);
verify(mock);
}
}
31
u1
u3
0.4
0.5
Visual similarity
0.6
0.2
0.9
0.5
0.3
0.3
0.5
0.8
0.9
u5
u2
0.2
0.4
0.2
0.4
u4
Geo similarity
32