### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Software Testing and Reliability CSC 712

NCS

GPA 3.94

### View Full Document

## 20

## 0

## Popular in Course

## Popular in ComputerScienence

This 48 page Class Notes was uploaded by Jaden Jakubowski on Thursday October 15, 2015. The Class Notes belongs to CSC 712 at North Carolina State University taught by Tao Xie in Fall. Since its upload, it has received 20 views. For similar materials see /class/223813/csc-712-north-carolina-state-university in ComputerScienence at North Carolina State University.

## Reviews for Software Testing and Reliability

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/15/15

Automated TestInput Generation Tao Xie North Carolina State University Department of Computer Science Sept 2006 httpWWWcscncsuedufacultyXie Why Automate Testing Software testing is important Software errors cost the US economy about 595 billion each year 06 of the GDP NIST 02 Improving testing infrastructure could save 13 cost Software testing is costly Account for even half the total cost of software development Beizer 90 Automated testing reduces manual testing effort Test generation Parasoft Jtest Agitar Agitator etc Test execution JUnit framework Testbehavior inspection Agitar Agitator Binary Search Tree Example public class BST implements Set static class Node int value Node left Node right Node root public void insert int value m public void remove int value m public bool contains int value m Approaches Methodsequence exploration Parasoft Jtest 45 and others Concretestate exploration ROStl a Xie et al ASE 04 NASA JPF Visser et al ISSTA 04 Symbolicstate exploration Symstra Xie et al TACAS 05 ConeoliCstate exploration DART Godefroid et al PLDI 05 EGT CadarampEngler SPIN 05 CUTE Sen et al FSE 05 Exploring Method Sequences 39 MCthOd arguments insert1 insert2 insert3 remove1 remove2 remove3 containsl i new BST Exploring Method Sequences 39 MCthOd arguments insert1 insert2 insert3 remove1 remove2 remove3 containsl new BSTU I se t3 r ve contains1 1nsert1 39nse 2 remo 1 r e3 Iteration 1 Exploring Method Sequences 39 MCthOd arguments insert1 insert2 insert3 remove1 remove2 remove3 containsl i new BST iqse t3 T x quot7 containsu lnSAW nserC2 removerfve r v xve3 ins t 1 co tains 1 Iteration 2 Generating Tests from Exploration Collect method sequence along the shortest path constructorcall edge 9 each methodcall edge luew BST rise t3 Tem ve39q contains insertl s sent 2 remove 1 1 love 3 ins A BST t new BST tinsert1 tinsert1 Iteration 2 Pruning StatePreserving Methods 39 MCthOd arguments insert1 insert2 insert3 remove1 remove2 remove3 containsl i new BST i llse t3 quot7 contains1 lnSAW nserc2 removerfvequot r v xve3 ins t 1 co tains 1 Iteration 2 Pruning StatePreserving Methods 39 MCthOd arguments insert1 insert2 insert3 remove1 remove2 remove3 containsl i new BST 3 contains 1 i39ise t3 rem vep 1niw nserd2 removau r tove3 ir7tlD contains 1 Iteration 2 Observation Some method sequences lead receiver object states back to earlier explored states i new BST 3 contains 1 k 39zse t3 r ve 1nwnse w remo 1 r e3 I 1 D remov 1 contains 1 Iteration 2 Rationale Focus on each method execution individually When method executions are deterministic unnecessary to test a method with the same inputs same inputs gt same behavior method inputs incoming program states receiverobject state transitivelyreachable eld values arguments accessible static elds Exploring Concrete States Method arguments insertl insert2 insert3 remove1 remove2 remove3 i new BST Exploring Concrete States Method arguments insertl insert2 insert3 remove1 i new BST 3 remove2 remove3 remove 1 remove 2 remove3 insertlLsertgt insert CD G G Iteration 1 Exploring Concrete States Method arguments insertl insert2 insert3 remove1 remove2 remove3 remove1 remove2 remove3 insertl insertigtnsert3 G o Iteration 2 Generating Tests from Exploration Collect method sequence along the shortest path constructorcall edge 9fach methodcall edge new BST 6 3 Lnsert1 G BST t new BST tinsert1 tinsert3 Issues of ConcreteState Exploration State explosion need at least N different insert arguments to reach a BST with size N run out of memory when N reaches 7 Relevantargument determination assume a set of given relevant arguments eg insert1 insert2 insert3 etc Exploring Concrete States i r Q Q G insel m6 9 Iteration 2 State Abstraction Symbolic States i new BSTO insert X1 new BST i Iteration 2 State Abstraction Symbolic States i i insert x2 V X1ltX2 Iteration 2 Symbolic Execution Execute a method on symbolic input values inputs insertSymbolicInt x Explore paths of the method PC P 4 if P PC P ampamp Q 4 if Q o Build a path condition for each path conjunct conditionals or their negations Produce symbolic states ltheap path conditiongt eg x1ltx2 Symbolic Execution Example public void insertSymbolicInt x if root null root new Nodex else Node t root while true if tvalue lt x explore the right subtree else if tvalue gt x explore the left subtree else return size Exploring Symbolic States public void insertSymbolicInt x Sl if root null root new Nodex else Hue Node t root while true if tvalue lt x explore the right subtree else if tvalue gt x explore the left subtree else return size Exploring Symbolic States public void insertSymbolicInt x if root null root new Nodex else Node t root while true if tvalue lt x explore the right subtree else if tvalue gt x explore the left subtree else return size Iteration 1 S1 Hue S2 insertx1 true Exploring Symbolic States public void insertSymbolicInt x Sl if root null tum root new Nodex else Node t root while true if tvalue lt x SZ explore the right subtree Hue else if tvalue gt x explore the left subtree else return 39 sertx2 size S3 X1ltX2 6 Iteration 2 Exploring Symbolic States public void insertSymbolicInt x Sl if root null tum root new Nodex else Node t root while true if tvalue lt x SZ explore the right subtree Hue else if tvalue gt x explore the left subtree else return 39 s x2 size S3 S4 X1ltX2 X1gtX2 6 Iteration 2 Exploring Symbolic States public void insertSymbolicInt x SI if root null tum root new Nodex else Node t root while true if tvalue lt x S2 explore the right subtree Hue else if tvalue gt x explore the left subtree else return se tx2 Size S3 S4 S5 X1ltX2 X1gtX2 X1X2 Iteration 2 Whlch States to Explore Next new BST public void insertSymbolicInt x SI if root null tum root new Nodex else Node t root while true a s if tvalue lt x SZ nsertx 39 explore the right subtree true else if tvalue gt x ltgt explore the left subtree else return size Iteration 3 Symbolic State Subsumption Symbolic state SzltH2 c2gt subsumes S5ltH5 35gt Heaps H2 and H5 are isomorphic Path condition C5 gt C2 checked using CVC Lite Omega If 82 has been explored 85 is pruned Still guarantee path coverage Within a method S2 x1 x2 gttrue S5 Symbolic true X1 X2 subsumes Concrete states Pruning Symbolic State public void insertSymbolicInt x 51 if root null tum root new Nodex else Node t root while true if tvalue lt x S2 explore the right subtree Hue else if tvalue gt x ltgt explore the left subtree else return in rt S size 5 X1 2 X2 Pruned Iteratlon 3 Generating Tests from Exploration new BST S1 Collect method sequence along the shortest path true constructorcall edge 9 each methodcall edge 1 insert x1 Generate concrete arguments by 2 using a constraint solver POOC 8 BST t new BST tinsertx1 tinsertxz insertx2 lti31 lt x2 S4 S5 X1ltX2 X1gtX2 X1X2 BST t new BST tinsert 1000000 tinsert 999999 Issue of Symbolic Execution Cannot handle large programs limitation of theorem prover limitation of constrain solver public static void methodint xint y int 2 xxx 3xx 9 if2 Y Systemoutprintln Good branch else Systemoutprintln Bad branch ConcreteSymbolic Execution Dynamically observe random execution and generate new test inputs to drive the next execution along an alternative path do dynamic analysis on a random execution collect symbolic constraints at branch points negate one constraint at a branch point say b call constraint solver to generate new test inputs use the new test inputs for next execution to take alternative path at branch b Check that branch b is indeed taken next DART Godefroid et al PLDI 05 EGT CadarampEngler SPIN 05 CUTE Sen et a1 FSE 05 Adapted from Koushik Sen s slide ConcreteSymbolic Execution public static void methodint xint y Let a yxgz3andy7 int 2 xxx 3xx 9 generated by random testdriver if2 Y Systemoutprintln Good branch else Systemoutprintln Bad branch Adapted from Koushik Sen s slide ConcreteSymbolic Execution public static void methodint xint y Let initially X 3 andy 7 int 2 xxx 3xx 9 generated by random testdriver if2 Y 0 concretez9 System out println Good branch Symbolic Z xxx 3xx9 else 0 take then branch with constraint Systemoutprintln Bad branch xxx3xx9kzy Adapted from Koushik Sen s slide ConcreteSymbolic Execution public static void methodint xint y Let initially X 3 andy 7 int 2 xxx 3xx 9 generated by random testdriver if2 Y 0 concretez9 System out println Good branch Symbolic Z xxx 3xx9 else 0 take then branch with constraint System out prlntln Bad branch xxx 3xx9 y 0 solve xxx 3xx9 y to take else branch 0 Don t know how to solve Stuck Adapted from Koushik Sen s slide ConcreteSymbolic Execution public static void methodint xint y Let n a yxgz3andyuz7 int 2 xxx 3xx 9 ifz y Systemoutprintln Good branch else Systemoutprintln Bad branch generated by random testdriver concrete z 9 thohczxxx3xx9 take then branch With constraint xxX 3XX9y y vexxx3xx9yto take else branch Don t know how to solve Stuck Need handle this smartly Adapted from Koushik Sen s slide ConcreteSymbolic Execution public static void methodint xint y Let a yxgz3and3n7 int 2 xxx 3xx 9 generated by random testdriver if2 y Systemoutprintln Good branch else Systemoutprintln Bad branch Adapted from Koushik Sen s slide ConcreteSymbolic Execution public static void methodint xint y Let n a yxgz3and3n7 int 2 xxx 3xx 9 generated by random testdriver if2 Y Systemoutprintln Good branch else Systemoutprintln Bad branch 0 concrete z 9 symbolic z xxx 3xx9 cannot handle symbolic value of z Adapted from Koushik Sen s slide ConcreteSymbolic Execution public static void method int x int y c Let initially X 3 and y 7 int 2 xxx 3xx 9 generated by random testdriver if2 Y 0 concretez9 System out println Good branch Symbolic Z xxx 3xx9 else cannot handle symbolic System out println Bad branch value OfZ make symbolic z 9 and proceed Adapted from Koushik Sen s slide ConcreteSymbolic Execution public static void methodint xint y int 2 xxx 3xx 9 ifz y Systemoutprintln Good branch else Systemoutprintln Bad branch Let initially X 3 and y 7 generated by random testdriver concrete z 9 symbolic z xxx 3xx9 cannot handle symbolic value of z make symbolic z 9 and proceed take then branch With constraint 9 l y Adapted from Koushik Sen s slide ConcreteSymbolic Execution public static void methodint xint y int 2 xxx 3xx 9 if2 Y Systemoutprintln Good branch else Systemoutprintln Bad branch Let initially x 3 and y 7 generated by random testdriver concrete z 9 symbolic z xxx 3xx9 cannot handle symbolic value of z make symbolic z 9 and proceed take then branch With constraint 9 l y solve 9 y to take else branch execute next run with x 3 and y 9 got error Adapted from Koushik Sen s slide ConcreteSymbolic Execution public static void methodint xint y int 2 xxx 3xx 9 if2 y Syste 39 el SY Replace symbolic expression by concrete value when symbolic expression becomes unmanageable ie nonlinear Let initially X 3 and y 7 generated by random testdriver concrete z 9 symbolic z xxx 3xx9 cannot handle symbolic value of z make symbolic z 9 and proceed take then branch With constraint 9 l y solve 9 y to take else branch execute next run with x 3 and y 9 got error Adapted from Koushik Sen s slide How to run jCUTE on your code You need to write a driver main method class Struct test driver function public static void mainString args int x cuteCuteinputInteger int y cuteCuteinputInteger methodxy public static void methodint xint y jCUTEGenerated Tests test driver function public class StructmainTest extends TestCase implements cuteInput private Object input private int i public testsStructmainTestString name supername public void test1 i0 inputi new Integer3 inputi new Integer9 i0 cuteCuteinput this Structmainnull How about BST You need to write a driver main method class BST public static void mainString args BST bl new BSTCuteinputInteger forint i0ilt4i switchCuteinputInteger case 0 b1insertCuteinputInteger break case 1 b1removeCuteinputInteger break default b1containsCuteinputInteger break Summary Methodsequence exploration Parasoft Jtest 45 and others Concretestate exploration ROStl a Xie et al ASE 04 NASA JPF Visser et al ISSTA 04 Symbolicstate exploration Symstra Xie et al TACAS 05 Conooliostate exploration DART Godefroid et al PLDI 05 EGT CadarampEngler SPIN 05 CUTE Sen et al FSE 05 Questions

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I made $350 in just two days after posting my first study guide."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.