资源描述
Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Symstra:A Framework for Generating Object-Oriented Unit Tests using Symbolic Execution,Tao Xie,Darko Marinov,Wolfram Schulte,and David Notkin,University of WashingtonUniversity of Illinois at Urbana-Champaign Microsoft Research,1,2,3,1,1,2,3,1,Motivations,Object-oriented unit tests consist of sequences of method invocations.,Behavior of an invocation depends on the methods arguments and the state of the receiver at the beginning of the invocation.,Automated test-input generation needs to produce:,Method sequences building relevant receiver object states,Relevant method arguments,2,Motivations,Object-oriented unit tests consist of sequences of method invocations.,Behavior of an invocation depends on the methods arguments and the state of the receiver at the beginning of the invocation.,Automated test-input generation needs to produce:,Method sequences building relevant receiver object states,Relevant method arguments,Symstra,achieves both tasks using symbolic execution of method sequences with symbolic arguments,3,Outline,Motivations,Example,Test generation by exploring concrete states,Symstra:exploring symbolic states,Evaluation,Conclusion,4,Binary Search Tree Example,public class,BST,implements,Set,Node,root;,int,size;,static class,Node,int,value;,Node,left;,Node,right;,public void,insert(,int,value),public void,remove(,int,value),public bool,contains(,int,value),public int,size(),5,Previous Test-Generation Approaches,Straightforward approach:generate all(bounded)possible sequences of calls to the methods under test,too many and many are redundant,Xie et al.04,Concrete-state exploration approach,Willem et al.04,Xie et al.04,assume a given set of method call arguments,explore new receiver-object states with method calls(in breadth-first manner),Test 1:BST t1=new BST();t1.size();,Test 2:BST t2=new BST();t2.size();,t2.size();,6,Exploring Concrete States,Method arguments:,insert(1),insert(2),insert(3),remove(1),remove(2),remove(3),new BST(),7,Exploring Concrete States,Method arguments:,insert(1),insert(2),insert(3),remove(1),remove(2),remove(3),new BST(),insert(1),2,insert(2),remove(2),remove(1),3,insert(3),remove(3),1,The first iteration,8,Exploring Concrete States,Method arguments:,insert(1),insert(2),insert(3),remove(1),remove(2),remove(3),new BST(),insert(1),2,insert(2),remove(2),remove(1),3,insert(3),remove(3),1,1,2,insert(3),1,3,The second iteration,insert(2),insert(1),remove(3),remove(2),remove(1),9,Generating Tests from Exploration,Collect method sequence along the shortest path (constructor-call edge,each method-call edge,),new BST(),insert(1),2,insert(2),remove(2),remove(1),3,insert(3),remove(3),1,1,2,insert(3),1,3,insert(2),insert(1),remove(3),remove(2),remove(1),BST t=new BST();,t.insert(1);,t.insert(3);,10,Issues of Concrete-State Exploration,State explosion(still),need at least,N,different,insert,arguments to reach a BST with size,N,run out of memory when,N,reaches 7,Relevant-argument determination,assume a set of given relevant arguments,e.g.,insert(1),insert(2),insert(3),etc.,11,Exploring Concrete States,new BST(),insert(1),2,insert(2),3,insert(3),1,1,2,insert(3),insert(2),1,3,The second iteration,12,State Abstraction:Symbolic States,new BST(),insert(1),2,insert(2),3,insert(3),1,1,2,x1,insert(x,1,),1,3,new BST(),The second iteration,insert(3),insert(2),13,State Abstraction:Symbolic States,new BST(),insert(1),2,insert(2),3,insert(3),1,1,2,insert(3),insert(2),x1,x1,x2,x,1,x,2,insert(x,1,),insert(x,2,),1,3,new BST(),The second iteration,14,Symbolic Execution,Execute a method on symbolic input values,inputs:,insert(SymbolicInt x),Explore paths of the method,Build a,path condition,for each path,conjunct conditionals or their negations,Produce,symbolic states,(),e.g.,if(P).;,if(Q),.;,PC:P,PC:P&Q,x1,x2,x,1,x,2,15,Symbolic Execution Example,public void insert(SymbolicInt x),if(root=null),root=new Node(x);,else,Node t=root;,while(true),if(t.value x),/explore the left subtree,.,else,return;,size+;,16,Exploring Symbolic States,public void insert(SymbolicInt x),if(root=null),root=new Node(x);,else,Node t=root;,while(true),if(t.value x),/explore the left subtree,.,else,return;,size+;,new BST(),S,1,true,17,Exploring Symbolic States,public void insert(SymbolicInt x),if(root=null),root=new Node(x);,else,Node t=root;,while(true),if(t.value x),/explore the left subtree,.,else,return;,size+;,new BST(),x,1,S,2,insert(x,1,),S,1,The first iteration,true,true,18,Exploring Symbolic States,public void insert(SymbolicInt x),if(root=null),root=new Node(x);,else,Node t=root;,while(true),if(t.value x),/explore the left subtree,.,else,return;,size+;,new BST(),x,1,S,2,insert(x,1,),S,1,The second iteration,true,true,x,1,x,1,x,2,x,2,insert(x,2,),S,3,19,Exploring Symbolic States,public void insert(SymbolicInt x),if(root=null),root=new Node(x);,else,Node t=root;,while(true),if(t.value x),/explore the left subtree
展开阅读全文