Unformatted text preview:

• Software testing is expensive • Unit testing applied to individual software components – One possible goal is 100% code coverage • Can require test harness/driver code & takes time, so often not as effective as it might be • DART helps automate unit testing by eliminating/reducing the need for writing manually test driver and harness code and automatically generating test inputs1. Automated extraction of program interface from source code 2. Generation of test driver for random testing through the interface 3. Dynamic test generation to direct executions along alternative program paths • DART can detect program crashes and assertion violations • Pre- and post-conditions can be added to generated test-driver int double(int x) { return 2 * x; } void test_me(int x, int y) { int z = double(x); if (z==y) { if (y == x+10) abort(); /* error */ } } (1) Interface extraction: • parameters of toplevel function • external variables • return values of external functions main(){ int tmp1 = randomInt(); int tmp2 = randomInt(); test_me(tmp1,tmp2); } (2) Generation of test driver for random testing: Closed (self-executable) program that can be run Problem: probability of reaching abort() is extremely low!main(){ int t1 = randomInt(); int t2 = randomInt(); test_me(t1,t2); } int double(int x) {return 2 * x; } void test_me(int x, int y) { int z = double(x); if (z==y) { if (y == x+10) abort(); /* error */ } } Concrete Execution Symbolic Execution Path Constraint main(){ int t1 = randomInt(); int t2 = randomInt(); test_me(t1,t2); } int double(int x) {return 2 * x; } void test_me(int x, int y) { int z = double(x); if (z==y) { if (y == x+10) abort(); /* error */ } } Concrete Execution Symbolic Execution Path Constraintmain(){ int t1 = randomInt(); int t2 = randomInt(); test_me(t1,t2); } int double(int x) {return 2 * x; } void test_me(int x, int y) { int z = double(x); if (z==y) { if (y == x+10) abort(); /* error */ } } Concrete Execution Symbolic Execution Path Constraint main(){ int t1 = randomInt(); int t2 = randomInt(); test_me(t1,t2); } int double(int x) {return 2 * x; } void test_me(int x, int y) { int z = double(x); if (z==y) { if (y == x+10) abort(); /* error */ } } Concrete Execution Symbolic Execution Path Constraintmain(){ int t1 = randomInt(); int t2 = randomInt(); test_me(t1,t2); } int double(int x) {return 2 * x; } void test_me(int x, int y) { int z = double(x); if (z==y) { if (y == x+10) abort(); /* error */ } } Concrete Execution Symbolic Execution Path Constraint main(){ int t1 = randomInt(); int t2 = randomInt(); test_me(t1,t2); } int double(int x) {return 2 * x; } void test_me(int x, int y) { int z = double(x); if (z==y) { if (y == x+10) abort(); /* error */ } } Concrete Execution Symbolic Execution Path Constraintmain(){ int t1 = randomInt(); int t2 = randomInt(); test_me(t1,t2); } int double(int x) {return 2 * x; } void test_me(int x, int y) { int z = double(x); if (z==y) { if (y == x+10) abort(); /* error */ } } Concrete Execution Symbolic Execution Path Constraint main(){ int t1 = randomInt(); int t2 = randomInt(); test_me(t1,t2); } int double(int x) {return 2 * x; } void test_me(int x, int y) { int z = double(x); if (z==y) { if (y == x+10) abort(); /* error */ } } Concrete Execution Symbolic Execution Path Constraintmain(){ int t1 = randomInt(); int t2 = randomInt(); test_me(t1,t2); } int double(int x) {return 2 * x; } void test_me(int x, int y) { int z = double(x); if (z==y) { if (y == x+10) abort(); /* error */ } } Concrete Execution Symbolic Execution Path Constraint main(){ int t1 = randomInt(); int t2 = randomInt(); test_me(t1,t2); } int double(int x) {return 2 * x; } void test_me(int x, int y) { int z = double(x); if (z==y) { if (y != x+10) abort(); /* error */ } } Concrete Execution Symbolic Execution Path Constraintmain(){ int t1 = randomInt(); int t2 = randomInt(); test_me(t1,t2); } int double(int x) {return 2 * x; } void test_me(int x, int y) { int z = double(x); if (z==y) { if (y == x+10) abort(); /* error */ } } Concrete Execution Symbolic Execution Path Constraint main(){ int t1 = randomInt(); int t2 = randomInt(); test_me(t1,t2); } int double(int x) {return 2 * x; } void test_me(int x, int y) { int z = double(x); if (z==y) { if (y == x+10) abort(); /* error */ } } Concrete Execution Symbolic Execution Path Constraintmain(){ int t1 = randomInt(); int t2 = randomInt(); test_me(t1,t2); } int double(int x) {return 2 * x; } void test_me(int x, int y) { int z = double(x); if (z==y) { if (y == x+10) abort(); /* error */ } } Concrete Execution Symbolic Execution Path Constraint Program Error • Dynamic test generation to direct executions along alternative program paths – collect symbolic constraints at branch points (whenever possible) – negate one constraint at a branch point to take other branch (say b) – call constraint solver with new path constraint to generate new test inputs – next execution driven by these new test inputs to take alternative branch b – check with dynamic instrumentation that branch b is indeed taken • Repeat this process until all execution paths are covered – May never terminate! • Significantly improves code coverage vs. pure random testingvoid foo(int x,int y){ int z = x*x*x; /* could be z = h(x) */ if (z == y) { abort(); /* error */ } } • Assume we can reason about linear constraints only • Initially x = 3 and y = 7 (randomly generated) • Concrete z = 27, but symbolic z = x*x*x – Cannot handle symbolic value of z! – Stuck? void foo(int x,int y){ int z = x*x*x; /* could be z = h(x) */ if (z == y) { abort(); /* error */ } } • Assume we can reason about linear constraints only • Initially x = 3 and y = 7 (randomly generated) • Concrete z = 27, but symbolic z = x*x*x – Cannot handle symbolic value of z! – Stuck? – NO! Use concrete value z = 27 and proceed… • Take else branch with constraint 27 != y • Solve 27 = y to take then branch • Execute next run with x = 3 and y = 27 • DART finds the error! Replace symbolic expression by concrete value when symbolic expression becomes unmanageable (e.g. non-linear) NOTE: whenever symbolic execution is stuck, static analysis becomes


View Full Document
Download Directed Automated Random Testing
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Directed Automated Random Testing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Directed Automated Random Testing 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?