DART: Directed Automated Random Testing – 2

[Music] good day again carrying on with from where we left in the final lecture on dart I had entered with this rationalization the place we talked about the execution mannequin of Dart i’ll through in brief recapping what we ended with within the last lecture we assume for simplicity sake that every application has best undertaking statements or an if condition which is represented as a conditional assertion venture statement is represented in the set a conditional statements are represented in the set capital C so application execution is a series of venture statements and statements and always ends with an abort or a halt assertion precise speed can be proposal of as an execution tree that contains all software executions which we noticed an instance of inverted symbolic execution mission nodes can have only one successor considering the fact that the there’s an on the spot next announcement and that is just one conditional nodes may have a department out situated on whether the is correct or false and leaves will all be labeled by way of a bottle holder so now we will be able to see how dot symbolically evaluates the expression in an effort to symbolically assessment the expression dart maintains what is known as a symbolic reminiscence what’s a symbolic reminiscence symbolic reminiscence basically tells you for each variable which is a reminiscence address wherein the variable is saved so it Maps memory addresses to expressions for inputs it’s the instantly the title of the variable itself but do not forget once we did that illustration for internal variables are the variables shall we say when you had Z is equal to X plus y then you definately must replace the worth of x with the aid of utilizing an expression for X plus y as X naught plus y naught where X naught is the symbolic expression for x and y naught is the symbolic expression for Y so that is what we mean by way of a symbolic memory symbolic memory denoted through s is a map from reminiscence addresses to expressions after they’ve dot algorithm runs it is going to overview symbolic route constraints utilising the algorithm and solve the path constraint to get directed generate experiment circumstances fixing it is going to give it to a third-get together constraint solver to begin with the preliminary the inputs will all be in s the mapping of s is accomplished via evaluating expressions symbolically so for every style of expression and tell you how you can symbolically review the expression earlier than we comprehend what easy methods to symbolically overview the expressions relatively simple whenever an genuine variable comes in the expression you replacement the symbolic variable as an alternative of the precise variable within the expression however then ultimately when you had been gonna replacement use these expressions in your direction constraints to get give it to a constraint solver that’s where the problem starts offevolved I advised you constraint solvers are not able to handle all sorts of course constraints in view that the situation is undecidable in detailed constraint solvers cannot handle route constraints that aren’t linear let this path constraints of the shape 5x squared is not equal to zero 3x cubed is higher than 0 any variety of nonlinear expression it is no longer excellent at placing so dot will keep in mind this as probably the most hazards of symbolic testing so each time it encounters a nonlinear course constraint it drops it within the sense that direction constraints grow to be nonlinear algorithm the dart algorithm will directly use the concrete values instead of symbolic values that is the way it that is why dot continues the concrete values at all so here is how symbolic evaluation of expressions occur there’s a operate known as evaluate symbolic which symbolically evaluates an expression Yi in the context of a memory M and already on hand symbolic expressions capitalists so what might be quite a lot of sorts of expressions if you go back and see the quite a lot of varieties of expressions would be just a variable a constant an arithmetic expression a relational expression a logical expression or a pointer expression we’ve written handiest multiplication however as I advised you in the final class represents all arithmetic operators this represent all relational operators this represents all logical operators so we will be able to do a case-by-case analysis of the way it happens so if it is only a variable then you definately directly assign it to the symbolic expression and you come back the up to date memory if it is a arithmetic expression which is represented via the superstar AE top please read the superstar a standing for + – / mod megastar or all of the arithmetic operators then it has two operand an expression he and one other expression e prime which first have to be evaluated symbolically themselves so E is evaluated symbolically top is e high is evaluated symbolically e double top is evaluated symbolically that is the recursive name evaluation symbolic symbolic calls itself however now if shall we say this can be a multiplication operator proper on this distinctive case so if each x and y are variables shall we say F and F top contain variables let’s say F and was 5x y F double prime F prime inverse 5x and F double top entails Y then 5 X Y will end up a non linear expression and i just instructed you the non linear expressions are problematic to clear up by using constraint solvers so dart has this situation it says that if one in all F and F top is a not a regular now not one of F for F prime is a steady if one of them is not a steady as I simply instructed you now you’ll be able to get a nonlinear expression so if each are non constants or one of them will not be a consistent you then say now i have an expression which isn’t linear so dot continues a particular flag which it calls all linear sets that flag to 0 if it is let’s that flag to 0 which means that what it is intuitively pronouncing the dot is encountered an expression that is nonlinear so dart will now do concrete evaluation which is evaluate concrete of that expression replace the memory and go ahead is not going to retailer the nonlinear symbolic expression in any respect why will it no longer retailer seeing that there’s no factor in storing it dart is aware of that the constraint solvers that it’s going to use are not able to manage these expressions if each F and F prime are constants then there is not any expression involving variables in any respect so dart does not have a choice however to immediately evaluate it concretely that’s what it does here updates the reminiscence and go saying if one among them is a consistent then what it’ll do is it will competently review that expression and greater now this is the case the relaxation of the operators that we noticed in expressions were relational and logical operators the one different expressions was once a pointer related stuff so this is the 2nd case if it is pointer if it is the expression of the form superstar E prime then it has to first symbolically assessment e prime so it calls itself recursively this can be a continuation of this code on this line if F top is a steady if it belongs to the area of s then it returns something value that is or else it’s going to return a pointer to the memory region if it can’t verify either of those then it will set an additional flag learn it as all locations definite because of this it is aware of the areas of all the variables within the experience that if there’s a point of a pointer that it does not comprehend then it will say there is a place that I do not know which means that it is going to set this flag or areas specific to 0 so and then it’s going to evaluate the concrete price and go ahead so what is that this part that i’m describing in take into account just to recap what does it takes a application in writes a driver instruments it to first generate one random enter runs the software on that random input as the software is walking on the random input dart symbolically executes the software to symbolically execute the application it has to symbolically assessment all the expressions that is the part that i’m describing right here so symbolic analysis is fairly straightforward it’s going to preserve substituting some thing expressions that it bought the traditional variables with symbolic variables that is what the recursive call does but there’s another thing that this pseudocode establishes it says that if as i am executing if I encounter an expression that is likely to be nonlinear that’s if i’m symbolically evaluating a main and e double high and one in every of them after symbolically evaluating come to be each come to be non now not constants then i’ll say i have encountered a linear expression so i’m going to set this flag most effective close to zero return and replacement concrete values i will not assessment it symbolically in any respect now not store it within the parkin string in any other case i’ll do anything average analysis is in a similar fashion right here when dart is handling pointer arithmetic if it encounters a obstacle the place the reminiscence deal with just isn’t effectively recognized that little set to set flag which says all areas usually are not obviously recognized due to the fact that right here it does not review all of them so there could be places where it doesn’t realize it’ll go ahead and substitute concrete values otherwise it does traditional symbolic execution why does it do the substitution of concrete values because by way of doing this upfront dart will make sure that if the path constraint that it collides is at all times solvable via the constraint solver that it is utilising so this fashion it overcomes some of the hazards of symbolic checking out so this is the phase that I used to be making an attempt to give an explanation for to you the within the algorithm that symbolically evaluates expressions there have been two completeness flags that dart saved one flag was once known as all linear which is about to zero each time symbolic expressions turn out to be non linear the next flag all locks particular or all places exact is about to zero every time the value of a targeted variable and accordingly the memory region of the variable will not be recognized when we when will one of these main issue come up for illustration you would bear in mind a software which dereferences a pointer whose worth is dependent upon enter parameters then i’ll surely not be aware of the worth of a specific variable right so these instances might particularly most of the time arise now let’s seem on the primary algo to maneuver that how does the test driver of not reply so that is the most important program of not referred to as the experiment driver or flawed dot so what does it do first it initializes all these boolean flags to 1 learn that is shorthand for pronouncing all linear which is a boolean variable to be one or two all locations particular which is another boolean variable is assigned to one or two forcing ok which is one other boolean variable that i will provide an explanation for now is also assigned to 1 or two so that is shorthand for 3 assignment statements which assigns three different boolean variables each and every of them to the worth two then dad goes into its most important loop what is the essential route the essential loop is a repeat except loop it is a repeat unless this situation is true which means that what each the flags or linear and all logs specific keep as one you then maintain on repeating this route the second one in every of them becomes zero you exit and throughout the loop what is dark darkish keeps a stack we’ll see what the stack contains it initializes the stack to empty is the enter vector the vector of all inputs it initializes it to empty it uses another boolean variable referred to as directed which it initializes to at least one or two after which it enters a at the same time loop so at the same time this directed directed stands for directed search so why i’m doing directed search it has this try seize exception so what’s are attempting capture exception do are trying if at some point this this boolean flag forcing go kick is ever set to one then that has already observed an error in the program it’ll print this and exit in any other case dart will go on instrumenting the software here so it will name this approach referred to as instrument application with the stack and so is it clear please what darkness dad uses three boolean flags all of them said to true and it goes into its important loop until the entire course constraints that it is encountering is linear and it knows precisely the places of the entire variables inside this loop as a way to instrument the program and do what directed such at any factor in time if dad has located the worm then on the way to say i have determined a computer virus it is going to print this message and are available out so this is how the scan driver looks love it combines random testing which is this repeat loop with directed search which is the inside even as loop if the instrumented program throws an exception above this been discovered so dart will print that message and exit if one of the crucial completeness flag is being set to zero way what dot is encountered a bad drawback it is encountered a nonlinear constraint it’s encountered the place where course the reminiscence of a special variable will not be recognized its encountered some dangerous crisis so if the directed search terminates then the directed variable which is that this variable of this internal loop not holds then the outer loop will also terminate furnished the completeness flag still preserve that’s clear from this code i am hoping in this case dart terminates and safely reports that the entire feasible program paths were explored however in case some of the completeness flags were grew to become off which is this all linear or all places exact the outer loop will proceed ceaselessly so there could be three choices dot will explore all feasible software paths efficaciously dot will to find an error and stop pronouncing that I observed an error or dot can run eternally that’s not too surprising due to the fact there’s a program analysis tools and the situation that it can be trying to handle which is exploring all software paths is almost always an undecidable predicament so we will be able to now seem at this code what is the code akin to instrumented software within the most important experiment driver of Dart appears like so right here is how instrumented software code appears find it irresistible takes a stack and a vector of inputs so first it does a random initialization of uninitialized input parameters in the memory location so it says for each input X with I of X underneath uninitialized do random that is the preliminary random scan vector that dart generates it initializes memory to this worth that it’s observed it units up the symbolic reminiscence which is s sets the preliminary application goes and says they i have now not but encountered any course constraint and starts offevolved at the first assertion and so long as it can be no longer encountering an abort or a halt dot will come across both an task declaration or it can come upon a statement considering we’ve got assumed that program execution is a series of i’m going to return to that slide for a 2nd we have now assumed that the software execution is a series of assignments and stipulations ending with an abort or a halt so that’s what this instrumented software does so it sets up the memory in units its stack counter to be 0 after which it starts offevolved so it says as long as statements will not be a couple of halt it is both an venture declaration or a condition declaration so there is a swap case line so if s is matched to an task declaration what’s going to it do it it already has a symbolic reminiscence uploaded here’s a new assignment assertion that it is encountered for instance this would be the case that it says that Z is the same as X plus y so the memory vicinity for Z which is M wants to be updated with the expression it is no longer for X not plus y now not so the reminiscence place for M is up-to-date after evaluating symbolically the expression e with the memory vicinity capital M and the symbolic set of expressions is it also desires to evaluate the expression e concretely considering you don’t know when at some point it is going to have the substitute so it’ll overview it symbolically it will evaluation it concretely it’s going to replace the reminiscence area and it says I completed with the announcement so it is going to replace the application counter to at least one so let’s consider dot stumble upon as a announcement if the healthy occurs to be a situation so it says if e then go to L high then what it’s going to do is that it’ll assessment e symbolically and concretely shall we embrace B is the symbolic effect of some concrete analysis of e C is the effect of symbolic evaluation of B e if B is right then the then route is taken by way of the program if B is false then the else direction is taken by way of the program so if B is right then it already has a route constraint which it has initialized here it’ll go forward and and the condition that it acquired via symbolically evaluating it to the path constraint learn this as what about the path constraint that used to be earlier now C is introduced to it with an finish and then it is going to now put this within the stack saying i have an extra route constraint to update I located on the way the application took a branch here is a course constraint the program took her then branch so i’m placing a 1 here and including this constraint to the stack and it is going to exchange the statement to whichever that it has to head to n time however believe the situation evaluates to false then to the trail constraint it had negation of that this is route constraint ended with negation of C it is updated stack by means of saying the program took the else branch with a 0 and add this to the stack and alter the statement quantity on account that it is like skipping so assertion number now turns into n plus 1 and it would go ahead and do it’s this clear so sincerely this phase what it does is that it grows the trail constraint separately one at a time when what is the stack do stack keeps track off which is the trail constraint that used to be delivered the trendy because that is the path constraint the dot goes to flip to be in a position to get the next execution of the application that is what dot does here right it will flip it within the in the main factor when it does the subsequent execution of the software so if s is an abort or a halt defenses an abort then dart raises an exception if s is a halt then it just directly calls the constraint solver with the path constraint that it is connected because it takes it from the stack now in this it used this events referred to as compare an replace stack what does that try this tells you the right way to replace the stack right here is the code for that so stack has a max ability this section says so long as you have not reached the maximum capacity if the stack department is not equal to branch then there is a crisis for set forcing okay to zero and raise an exception the place is this boolean variable forcing okay it was right here say forcing okay is ever said then that you can say about that is found else if stack is like this you then go forward and as a rule update the stack branch you say you dispose of it from the stack pop it off and then add this that is smooth this normally simply the usual stack operations that you’re doing proper clear up path constraint which is what it calls here correct solve course constraint what does that appear like that you just in actual fact call a constraint solver which is 0.33 celebration constraints on so what it does is that it takes the brand new course constraint from present day factor from the stack and it says if J is minus 1 then I finished my search you terminated most of the time otherwise this do you are taking this something course constraint that you simply located at the high of the stack negate that route constraint delivered to the branch now you call it once more so that it explores the opposite such that is the section that forces to do that directed search this is an evidence of what the instrumented application does every run of the instrumented application the first one does a random search so besides for the first one each run of the instrumented software how is it finished you might have a stack of all the conditions that you’ve got encountered within the direction within the previous run so we file a department worth and a performed price department value is 1 as I instructed you when the 10 phase is correct or the situation is true and branch worth is 0 if the condition is false carried out value 0 handiest when the branch of the situation is achieved within the prior runs because of this i’ve explored this section already so then you definitely say then utterly finished with this application constraint knowledge related to every conditional announcement of the final execution path is stored in a variable referred to as stack which is what we’ve been watching at and that is saved in a file that’s shared between executions after which at any point in time the whatever is to be had on the prime of the stack is pulled flipped and that is the alternate direction that dot tries to take so if it is explored both the choices then it units the done price to zero eliminates it from the stack and takes the subsequent available instrumental software what does it do it essentially executes the original application interleaved with a gathering of symbolic constraints and every conditional declaration it tests it calls this compare and replace stock events it exams whether the present execution route suits the one who it envisioned at the end of the prior execution and if it is then it does not repeat but when it now not then it explores this new execution path but if some difficulty occurs then it units the flag forcing alright to zero and in actual fact then it’ll restart this run dot which is the fundamental scan driver with one other fresh randomly generated enter when will this sourcing ok be set to zero that may be most effective due to a earlier incompleteness and darts directed search it went along a part that it couldn’t whole so it’ll start everywhere again so when the original application holds new enter values are generated from the remedy route constraint routine a good way to try to force the following run to execute the last unexplored department of the stack the sort of department exists then it’s explode or else it eliminates it from the stack and goes to the next route constraint that it was once false so i hope the code for dart is clear so the principal code for dart is that this experiment driver which does one random search adopted by a program instrumentation which symbolically execute the application connects the path constraint and does a directed search this was the code for that which tells you how one can symbolically replace an execute a software it wants a stack to be ready to hold track of the trail constraints it is a update that is the events procedure that continues the stack this is the movements that calls the constraint solver and dart could as I advised you’ve gotten three results so here is the primary theorem that talks concerning the correctness of my watch if dart runs if dart at any factor in time says print trojan horse observed then there’s some input to P that leads to an abort state it is particularly determined in error you could have runned out terminates out printing computer virus discovered then this means that or dot has explored the entire execution elements of P or else run dart will run endlessly an individual has to manually go and abort it the 1/3 section is an undesirable habits of dart which we can not prevent considering the fact that the underlying difficulty is undecidable what we’ll do next time is i will explain how dart truck works for C by utilising an example and inform you how this interface extraction experiment driver extraction and directed search implementation simply occurs by way of an example so we’ll discontinue with this for now thank you [Music] [Music] [Music]

Add Comment