Create Presentation
Download Presentation

Download Presentation
## Dynamic Symbolic Execution

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**Dynamic Symbolic Execution**CS 8803 FPLOct 31, 2012 (Slides adapted from KoushikSen)**Today, QA is mostly testing**“50% of my company employees are testers, and the rest spends 50% of their time testing!” Bill Gates 1995**Software Reliability Importance**• Software is pervading every aspects of life • Software everywhere • Software failures were estimated to cost the US economy about $60 billion annually [NIST 2002] • Improvements in software testing infrastructure may save one-third of this cost • Testing accounts for an estimated 50%-80% of the cost of software development [Beizer 1990]**Big Picture**Safe Programming Languages and Type systems Testing Model Checking and Theorem Proving Runtime Monitoring Static Program Analysis Dynamic Program Analysis Model Based Software Development and Analysis**Big Picture**Safe Programming Languages and Type systems Testing Model Checking and Theorem Proving Runtime Monitoring Static Program Analysis Dynamic Program Analysis Model Based Software Development and Analysis**void quicksort (int[] a, int lo, int hi) {**int i=lo, j=hi, h; int x=a[(lo+hi)/2]; // partition do { while (a[i]<x) i++; while (a[j]>x) j--; if (i<=j) { h=a[i]; a[i]=a[j]; a[j]=h; i++; j--; } } while (i<=j); // recursion if (lo<j) quicksort(a, lo, j); if (i<hi) quicksort(a, i, hi); } A Familiar Program: QuickSort**void quicksort (int[] a, int lo, int hi) {**int i=lo, j=hi, h; int x=a[(lo+hi)/2]; // partition do { while (a[i]<x) i++; while (a[j]>x) j--; if (i<=j) { h=a[i]; a[i]=a[j]; a[j]=h; i++; j--; } } while (i<=j); // recursion if (lo<j) quicksort(a, lo, j); if (i<hi) quicksort(a, i, hi); } Test QuickSort Create an array Initialize the elements of the array Execute the program on this array How much confidence do I have in this testing method? Is my test suite *Complete*? Can someone generate a small and *Complete* test suite for me? A Familiar Program: QuickSort**Automated Test Generation**• Studied since 70’s • King 76, Myers 79 • 30 years have passed, and yet no effective solution • What Happened?**Automated Test Generation**• Studied since 70’s • King 76, Myers 79 • 30 years have passed, and yet no effective solution • What Happened? • Program-analysis techniques were expensive • Automated theorem proving and constraint solving techniques were not efficient**Automated Test Generation**• Studied since 70’s • King 76, Myers 79 • 30 years have passed, and yet no effective solution • What Happened? • Program-analysis techniques were expensive • Automated theorem proving and constraint solving techniques were not efficient • Recent years have seen remarkable strides in static analysis and constraint solving • SLAM, BLAST, ESP, Bandera, Saturn, MAGIC**Automated Test Generation**• Studied since 70’s • King 76, Myers 79 • 30 years have passed, and yet no effective solution • What Happened? • Program analysis techniques were expensive • Automated theorem proving and constraint solving techniques were not efficient • Recent years have seen remarkable strides in static analysis and constraint solving • SLAM, BLAST, ESP, Bandera, Saturn, MAGIC Question: Can we use similar techniques in Automated Testing?**Testing**Systematic Automated Testing Model-Checking and Formal Methods Static Analysis Constraint Solving Automated Theorem Proving**CUTE and DART**• Combine random testing (concrete execution) and symbolic testing (symbolic execution) [PLDI’05, FSE’05, FASE’06, CAV’06,ISSTA’07, ICSE’07] Concrete + Symbolic = Concolic**Goal**• Automated Unit Testing of real-world C and Java Programs • Generate test inputs • Execute unit under test on generated test inputs • so that all reachable statements are executed • Any assertion violation gets caught**Goal**• Automated Unit Testing of real-world C and Java Programs • Generate test inputs • Execute unit under test on generated test inputs • so that all reachable statements are executed • Any assertion violation gets caught • Our Approach: • Explore all execution paths of an Unit for all possible inputs • Exploring all execution paths ensure that all reachable statements are executed**1**0 1 0 1 0 0 1 1 1 0 1 Execution Paths of a Program • Can be seen as a binary tree with possibly infinite depth • Computation tree • Each node represents the execution of a “if then else” statement • Each edge represents the execution of a sequence of non-conditional statements • Each path in the tree represents an equivalence class of inputs**2*x==y**x!=y+10 Example of Computation Tree void test_me(int x, int y) { if(2*x==y){ if(x != y+10){ printf(“I am fine here”); } else { printf(“I should not reach here”); ERROR; } } } N Y N Y ERROR**Divide by 0 Error**x = 3 / i; Buffer Overflow a[i] = 4; Concolic Testing: Finding Security and Safety Bugs**Divide by 0 Error**if (i !=0) x = 3 / i; else ERROR; Buffer Overflow if (0<=i && i < a.length) a[i] = 4; else ERROR; Concolic Testing: Finding Security and Safety Bugs Key: Add Checks Automaticallyand Perform Concolic Testing**Random testing**generate random inputs execute the program on generated inputs Probability of reaching an error can be astronomically less test_me(int x){ if(x==94389){ ERROR; } } Probability of hitting ERROR = 1/232 Existing Approach I**Symbolic Execution**use symbolic values for input variables execute the program symbolically on symbolic input values collect symbolic path constraints use theorem prover to check if a branch can be taken Does not scale for large programs test_me(int x) { if ((x%10)*4!=17) { ERROR; } else { ERROR; } } Symbolic execution will say both branches are reachable: False positive Existing Approach II**Symbolic Execution**use symbolic values for input variables execute the program symbolically on symbolic input values collect symbolic path constraints use theorem prover to check if a branch can be taken Does not scale for large programs test_me(int x) { if (bbox(x)!=17) { ERROR; } else { ERROR; } } Symbolic execution will say both branches are reachable: False positive Existing Approach II**Concolic Testing Approach**int double (int v) { return 2*v; } void testme (int x, int y) { z = double (y); if (z == x) { if (x > y+10) { ERROR; } } } • Random Test Driver: • random values for x and y • Probability of reaching ERROR is extremely low**Concrete Execution**Symbolic Execution concrete state symbolic state path condition x = 22, y = 7 x = x0, y = y0 Concolic Testing Approach int double (int v) { return 2*v; } void testme (int x, int y) { z = double (y); if (z == x) { if (x > y+10) { ERROR; } } }**Concrete Execution**Symbolic Execution concrete state symbolic state path condition x = 22, y = 7, z = 14 x = x0, y = y0, z = 2*y0 Concolic Testing Approach int double (int v) { return 2*v; } void testme (int x, int y) { z = double (y); if (z == x) { if (x > y+10) { ERROR; } } }**Concrete Execution**Symbolic Execution concrete state symbolic state path condition x = 22, y = 7, z = 14 x = x0, y = y0, z = 2*y0 Concolic Testing Approach int double (int v) { return 2*v; } void testme (int x, int y) { z = double (y); if (z == x) { if (x > y+10) { ERROR; } } } 2*y0 != x0**Concrete Execution**Symbolic Execution concrete state symbolic state path condition x = 22, y = 7, z = 14 x = x0, y = y0, z = 2*y0 Concolic Testing Approach int double (int v) { return 2*v; } void testme (int x, int y) { z = double (y); if (z == x) { if (x > y+10) { ERROR; } } } Solve: 2*y0 == x0 Solution: x0 = 2, y0 = 1 2*y0 != x0**Concrete Execution**Symbolic Execution concrete state symbolic state path condition x = 2, y = 1 x = x0, y = y0 Concolic Testing Approach int double (int v) { return 2*v; } void testme (int x, int y) { z = double (y); if (z == x) { if (x > y+10) { ERROR; } } }**Concrete Execution**Symbolic Execution concrete state symbolic state path condition x = 2, y = 1, z = 2 x = x0, y = y0, z = 2*y0 Concolic Testing Approach int double (int v) { return 2*v; } void testme (int x, int y) { z = double (y); if (z == x) { if (x > y+10) { ERROR; } } }**Concrete Execution**Symbolic Execution concrete state symbolic state path condition x = 2, y = 1, z = 2 x = x0, y = y0, z = 2*y0 Concolic Testing Approach int double (int v) { return 2*v; } void testme (int x, int y) { z = double (y); if (z == x) { if (x > y+10) { ERROR; } } } 2*y0 == x0**Concrete Execution**Symbolic Execution concrete state symbolic state path condition x = 2, y = 1, z = 2 x = x0, y = y0, z = 2*y0 Concolic Testing Approach int double (int v) { return 2*v; } void testme (int x, int y) { z = double (y); if (z == x) { if (x > y+10) { ERROR; } } } 2*y0 == x0 x0 <= y0+10**Concrete Execution**Symbolic Execution concrete state symbolic state path condition x = 2, y = 1, z = 2 x = x0, y = y0, z = 2*y0 Concolic Testing Approach int double (int v) { return 2*v; } void testme (int x, int y) { z = double (y); if (z == x) { if (x > y+10) { ERROR; } } } Solve: (2*y0 == x0) and(x0 > y0 + 10) Solution: x0 = 30, y0 = 15 2*y0 == x0 x0 <=y0+10**Concrete Execution**Symbolic Execution concrete state symbolic state path condition x = 30, y = 15 x = x0, y = y0 Concolic Testing Approach int double (int v) { return 2*v; } void testme (int x, int y) { z = double (y); if (z == x) { if (x > y+10) { ERROR; } } }**Concrete Execution**Symbolic Execution concrete state symbolic state path condition x = 30, y = 15 x = x0, y = y0 Concolic Testing Approach int double (int v) { return 2*v; } void testme (int x, int y) { z = double (y); if (z == x) { if (x > y+10) { ERROR; } } } Program Error 2*y0 == x0 x0 > y0+10**Traverse all execution paths one by one to detect errors**assertion violations program crash uncaught exceptions combine with valgrind to discover memory errors T F T F T F F T T T F T Explicit Path (not State) Model Checking**Traverse all execution paths one by one to detect errors**assertion violations program crash uncaught exceptions combine with valgrind to discover memory errors T F T F T F F T T T F T Explicit Path (not State) Model Checking**Traverse all execution paths one by one to detect errors**assertion violations program crash uncaught exceptions combine with valgrind to discover memory errors T F T F T F F T T T F T Explicit Path (not State) Model Checking**Traverse all execution paths one by one to detect errors**assertion violations program crash uncaught exceptions combine with valgrind to discover memory errors T F T F T F F T T T F T Explicit Path (not State) Model Checking**Traverse all execution paths one by one to detect errors**assertion violations program crash uncaught exceptions combine with valgrind to discover memory errors T F T F T F F T T T F T Explicit Path (not State) Model Checking**Traverse all execution paths one by one to detect errors**assertion violations program crash uncaught exceptions combine with valgrind to discover memory errors T F T F T F F T T T F T Explicit Path (not State) Model Checking**Concrete Execution**Symbolic Execution concrete state symbolic state path condition x = 22, y = 7 x = x0, y = y0 Novelty: Simultaneous Concrete and Symbolic Execution int foo (int v) { return (v*v) % 50; } void testme (int x, int y) { z = foo (y); if (z == x) { if (x > y+10) { ERROR; } } }**Concrete Execution**Symbolic Execution concrete state symbolic state path condition Novelty: Simultaneous Concrete and Symbolic Execution int foo (int v) { return (v*v) % 50; } void testme (int x, int y) { z = foo (y); if (z == x) { if (x > y+10) { ERROR; } } } Solve: (y0*y0 )%50 == x0 Don’t know how to solve! Stuck? (y0*y0)%50!=x0 x = 22, y = 7, z = 49 x = x0, y = y0, z = (y0*y0)%50**Concrete Execution**Symbolic Execution concrete state symbolic state path condition Novelty: Simultaneous Concrete and Symbolic Execution void testme (int x, int y) { z = foo (y); if (z == x) { if (x > y+10) { ERROR; } } } Solve: foo (y0) == x0 Don’t know how to solve! Stuck? foo (y0)!=x0 x = 22, y = 7, z = 49 x = x0, y = y0, z = foo (y0)**Concrete Execution**Symbolic Execution concrete state symbolic state path condition Novelty: Simultaneous Concrete and Symbolic Execution int foo (int v) { return (v*v) % 50; } void testme (int x, int y) { z = foo (y); if (z == x) { if (x > y+10) { ERROR; } } } Solve: (y0*y0 )%50 == x0 Don’t know how to solve! Not Stuck! Use concrete state Replace y0 by 7 (sound) (y0*y0)%50!=x0 x = 22, y = 7, z = 49 x = x0, y = y0, z = (y0*y0)%50**Concrete Execution**Symbolic Execution concrete state symbolic state path condition Novelty: Simultaneous Concrete and Symbolic Execution int foo (int v) { return (v*v) % 50; } void testme (int x, int y) { z = foo (y); if (z == x) { if (x > y+10) { ERROR; } } } Solve: 49 == x0 Solution : x0 = 49, y0 = 7 49!=x0 x = 22, y = 7, z = 48 x = x0, y = y0, z = 49**Concrete Execution**Symbolic Execution concrete state symbolic state path condition x = 49, y = 7 x = x0, y = y0 Novelty: Simultaneous Concrete and Symbolic Execution int foo (int v) { return (v*v) % 50; } void testme (int x, int y) { z = foo (y); if (z == x) { if (x > y+10) { ERROR; } } }**Concrete Execution**Symbolic Execution concrete state symbolic state path condition x = 49, y = 7, z = 49 x = x0, y = y0 ,z = 49 Novelty: Simultaneous Concrete and Symbolic Execution int foo (int v) { return (v*v) % 50; } void testme (int x, int y) { z = foo (y); if (z == x) { if (x > y+10) { ERROR; } } } Program Error 2*y0 == x0 x0 > y0+10**+ Complex programs**+ Efficient - Less coverage + No false positive - Simple programs - Not efficient + High coverage - False positive Concolic Testing: A Middle Approach Random Testing Symbolic Testing Concolic Testing + Complex programs +/- Somewhat efficient + High coverage + No false positive**Implementations**• DART and CUTE for C programs • jCUTE for Java programs • Gotohttp://srl.cs.berkeley.edu/~ksen/ for CUTE and jCUTE binaries • MSR has four implementations • SAGE, PEX, YOGI, Vigilante • Similar tool: EXE at Stanford • Easiest way to use and to develop on top of CUTE • Implement concolic testing yourself**Another Example: Testing Data Structures**typedef struct cell { int v; struct cell *next; } cell; int f(int v) { return 2*v + 1; } int testme(cell *p, int x) { if (x > 0) if (p != NULL) if (f(x) == p->v) if (p->next == p) abort(); return 0; } • Random Test Driver: • random memory graph reachable from p • random value for x • Probability of reaching abort( ) is extremely low