cs259 ยป

CS259 Lesson4

01 l Scandal in Bohemia

Welcome back to our course on debugging. Today's topic is tracking origins, meaning how to start with a failure and track back origins of the failure until you find the defect that causes it. But before we get there, a bit of a story. If you are a fan of Sherlock Holmes, you may recall this famous scene in "A Scandal in Bohemia." Here we have Dr. Watson and Sherlock Holmes sitting by the fireplace. They haven't seen each other for some time, and Sherlock remarks that Watson has put on 7-1/2 pounds since they last met. And Watson says, "How do you know?" And Sherlock answers, "I see. I deduce it." Not only does Sherlock find out that Watson has put on 7 pounds, he also remarks that Watson has been getting very wet lately and that his servant girl is clumsy and careless. Again, Watson asks, "How on earth did you find that out?" "Oh, it is simplicity itself," Sherlock says. What Holmes sees is that on the inside of Dr. Watson's shoe there is a small number of scratches, which he can see in the firelight. He deduces that these scratches have been applied by somebody who very carelessly tried to clean the shoe, possibly Dr. Watson's servant. And since the shoe had to be cleaned with such a rough device, this likely came from mud through which Dr. Watson had to run while getting very wet. This is how Sherlock Holmes, from a single observation, can deduce all the events that led to this observation. I should add that, faced with this explanation, Dr. Watson exclaims, "When, Sherlock, I hear you give your reasons, the thing always appears to me to be so ridiculously simple that I could easily do it myself. Though, at each successive instance of your reasoning, I am baffled until you explain your process."

02 l Think Like Sherlock Holmes

What Sherlock Holmes reconstructs in his reasoning over here is a cause-effect chain. First, Dr. Watson ran across mud; therefore, the servant had to clean the shoe. And therefore there were scratches found in the shoe. In debugging, we also have such a cause-effect chain: from the defect to the infection--that is, an error in the state-- and finally to the failure, which can be observed by a user. The difference in the Sherlock Holmes story, however, is that Sherlock makes just one observation and deduces everything that must have happened before; whereas in debugging, so far, we have assumed that we can actually observe what has happened before in the way we assume that we have perfect control over our program and therefore can observe everything. But what happens if this information is not available? If all we know is that the failure occurred but we have no history, or means to observe what was going on? This is where the Sherlock Holmes method of debugging comes into play. For we must, like Sherlock Holmes, think backwards from our observations to find out what has really happened. In debugging, we start with the failure and think backwards what could be the possible cause such that we can finally discover the reason.

03 q Sherlock Who

What we're going to discuss today is how errors propagate in a program, that is, from one variable to another, because these very dependencies then help us in reasoning backwards. And this is our second topic: how we can trace back these dependencies from an observable failure to an earlier infection and then to a defect in the code. And for this we're going to use the Sherlock Holmes method which, of course, is: "Elementary, my dear Watson." But first, a quiz. Do you like Sherlock Holmes? Here are your options. Is it more like: "I'm his greatest fan!" Or: "Isn't he, like, outdated?" Or: "Actually, I find him annoying." Or: "Sherlock who?" Hint: The answer to this quiz will neither determine your grading nor will it determine the next step. Enjoy.

03 s Sherlock Who

And now for the answer. Well, of course, there is no real answer to that quiz. Any answer is fine in here. However, a few comments on the individual options. If you're a fan of Sherlock Holmes in solving puzzles and all, this lesson is right for you--as is debugging, for that matter. If you think that Sherlock Holmes is outdated, well, try and read one of the old stories and see how outdated they really are or check out one of the most recent adaptations of Sherlock Holmes. If you find Sherlock Holmes annoying because his way of reasoning is obnoxious or showing off his super-smartness, that's probably correct, but I think that Arthur Conan Doyle actually wanted to portray Sherlock Holmes as somebody who's not entirely likable. Finally, Sherlock Who? Here's something to discover for you. Enjoy.

04 q Art of Deduction

Needless to say, Sherlock Holmes would make an excellent program debugger if he were living these days. The problem in front of us can be stated as follows: "Something impossible occurred, and the only solid information is that it did occur. So we must think backwards from the result to discover the reasons." Quote from Kernighan and Pike, "The Practice of Programming" Thinking backwards from the result. This is the art of deduction applied to debugging. Let me illustrate this--how this works--using a familiar example. Here again we have a function to remove HTML markup. Just as a reminder, what this function is supposed to do is to take HTML input such as this one: a foo text enclosed into HTML tags, one to switch on bold rendering and one to switch off bold rendering, and to turn this into a text in which the HTML markup has been removed. This makes use of a number of variables: Tag checks whether we currently are processing a tag. That is, during these three characters, tag should be true. And only if we are not in tag mode do we actually add the characters to the out variable. And the out variable at the end is being returned. So while we are processing this code, tag would be true for these three characters. Then tag would be false. F-O-O would be added to the output. Finally, we would have 4 more tag characters which would not be added. In the end, what we get is this string: foo. Now let's practice the art of deduction on this example simply from the observation that this final assertion has failed. So all we know is that indeed this code can produce an output in which HTML markup is still present. This is the observation from which we start. Let's go and think backwards how the assertion possibly could have failed. What we know is that out contains an opening tag that is a less-than character. The only place where this character could have been added to the out variable is here. In order to reach that line, a number of conditions must be fulfilled. All of these conditions cannot have failed. Whereas this one must have failed. Let's focus on the tag variable here. What was the value of the tag variable when the less-than sign had been added? Over to you.

04 s Art of Deduction

Here comes the answer to the quiz. Since this here was executed and this condition up here is that tag cannot have been set, we can deduce that tag must have been false.

05 q Deduce More

But there is more that we can deduce from the code. Since the character was a less than sign, we have a condition which specifically checks for less than signs, up here. However, this condition apparently had not turned out to be true. Therefore, we can now deduce the value of the quote variable. What was the value of the quote variable here? Over to you.

05 s Deduce More

And now for the answer--c was a less than sign. This part of the condition is true, but this line was not executed. Instead this line was executed. And therefore, this whole condition must have been false. Since it was false, quote must have been true because that's the value which turns the entire condition to false. This is the correct answer.

06 q What Was The Value

So, at this point, we know that the quote variable must have been set to true at some point. Because initially it was false, but we already know that if it had stayed false, then the less than character would never have been added to the output. So we now have deduce that quote must have been set, and there is only one place in the program where quote is set, which is down here. So we can deduce that this long condition, which checks for quote, must have held at some earlier point before the less than sign. Why must it have been true at some earlier point? Well, because at the moment when symbols left was the less than sign then the condition did not hold That simply assumed it was the character right before the less than sign then the variable tag had never been set to true. It was false from the beginning and it was false till the very end. If you look at this condition, what was the value of c and again over to you.

06 s What Was The Value

We have assumed that tag was false all along, which looking at the intention of this condition means that this condition never ever should have turned out to be true anyway. With the eyes of Sherlock Holmes, however, we would immediately deduce that this condition can only hold when the first clause is true--that is c was a double quote.

07 q Can It Fail Now

Now, it seemed that this condition can only hold when c was in double quote. So first c was in double quote and then c was in less than sign. From all of this information, we can reconstruct the input that was passed over to remove HTML markup. It must have been something along the lines of first a double quote and then an opening tag. Between these two events, c being a double quote and c being an opening tag, there could also have been other characters before. But in our deduction, none of these matter. For us, it is sufficient to know that indeed there is an input, which can cause this assertion to fail. And second, while we are doing the reasoning, we actually also stumbled across the condition that was wrong here. From the line of our reasoning, we can now deduce that if this condition had not been true, then for this input the assertion would not have failed. By adding appropriate parenthesis here, we can make sure that this input will not cause the assertion to fail and thereby through deduction we have found a fix without executing the program even once. And now for a really tough quiz in which you can show how good your deduction skills are. If I have applied this fix with this parenthesis, can this assertion ever fail? If yes, provide an example. If no, write down the individual steps of your deduction and let's see whether this is elementary, my dear Watson.

07 s Can It Fail Now

That must have been a tough nut to crack. The correct answer is No. The assertion cannot fail. Let's see why this is the case in the next section of the course.

08 l Double Check

Indeed, with this fix applied, the assertion can no longer fail. This is how the argument goes. In order to for the assertion to fail, the out variable must contain a less than sign. Since this is the only place where characters are being added, tag cannot be set. The quote variable; however, must be set, because otherwise, we would have gone in that first branch over here. But then quote can only be set in this very location, but this can't be the case because from step 2, we already know that tag cannot be set, and therefore, we have a contradiction between the 2, which means that the assertion will never fail. Quote erat demonstratum meaning what was shown to be proved. This was a nice proof, wasn't it? I must confess that I don't entirely trust my own proof. It's very much like in the quote of Don Knuth who once said beware of bugs in the above code. I have only proven it correct, not tried it. So in order to check whether my code now would be really correct with respect to this assertion, I went and used an automated deduction tool. The tool I was using is named Pex. This is a experimental tool for Microsoft research, which is a very, very thorough tester, which gets possible inputs from the program code. So Pex does the same deduction steps as Sherlock Holmes would do or as I would do or as you would do in order to come up with inputs that cause a built in assertion to fail. And my idea was, if Pex doesn't find anything, then chances are my program is really correct. Let's go and see Pex in action. The Pex tool has its own webpage where you can try it out. It's called www.pexforfun.com. Here you can enter a code which you want to be tested automatically by Pex. And sense Pex works for the languages C sharp, visual basic, and F sharp, I converted our remove HTML markup function into C sharp. Here you see the function, I have renamed it to puzzle in order to match the Pex for fun conventions. Here is the precondition. The string that has passed must not be now, which is a special C sharp thing. And here we have the loop over all the individual elements, setting tag and setting quote, or adding the characters to the result. At the end, we have an assertion. The result must not contain a less than character. Let's first try this out on the buggy version and let's see whether Pex can find the bug. We click on ask Pex, and now you see a number of interesting inputs, and these would all be inputs which cover various parts of the code. At the very end, what you see here, is an error message. The assertion has failed, and the assertion fails precisely on our buggy input, double quote followed by a less than sign. So Pex has been able, by going through the code, to come up with the exact same failing input as in our deduction example. Now I have gone and fixed the program. The question is whether Pex can now find an input that makes the assertion fail. And again, we ask Pex. And again, it comes up with a number of interesting inputs. All of these interesting inputs cause the program to run properly. That is, despite its best efforts, and Pex is really, really good in detecting errors, Pex has not found a single input which causes the assertion to fail. So for the fixed program, even Pex says this is correct, and I myself also have said this is correct. If you don't believe an automated deduction tool, you can believe me, and if you don't believe me, you can believe an automated deduction tool. Together we create a big deal of confidence in this program.

09 q Still a Bug

Still, what automated tools can find and what humans can find, is only correct with regard to the specification. And at this point, we do not have a complete specification on what a remove html markup should really do. One of my PhD students sent me this input. Here is the html markup, and here is the actual text. If we feed this into the program, what is the output? What is the result of the remove html markup function when we give it this string? Over to you.

09 s Still a Bug

We have 2 ways of finding this out. We can either run the whole thing with this input or we can also go through it and figure out what's going on. The interesting thing about this input is that it mixes double quotes and single quotes. I am going to use the green color for section where tag mode on, and I'm going to use the pink color for sections where quote is on. So initially, we are in tag mode. It starts precisely here, and it goes up to the place where we find the quote. While we are processing the quote, quote mode is also turned on. But now we see the second quote in here, and quote mode ends. We are still in tag mode. Now we see another quote, you see where the problem is. We don't discriminate between double and single quotes, and therefore, a string that starts with a double quote can also end in a single quote. See, here again we are in tag mode, but now we also start quote mode. And now as we are at the greater than sign that is the end of the tag, we are still in quote mode, and therefore, tag mode does not end. And sense we stay in quote mode until the very end, all of this is considered to be part of the tag, and therefore, the answer is the result is the empty string. This is the correct result.

10 p Fix It For Good

What you can see now is that, although we have formally proven that our code cannot violate this assertion, there still may be other issues, which simply aren't properly specified yet. So any proof can only be as good as the specification it relies on. Which, of course, again is a call for good assertions. Because if you do have good assertions, you get good specifications, and this will not only help you a lot in debugging, you will also improve your testing, and as we have seen, it may even enable the use of automated deduction tool. But now, for a programming exercise. It really, really annoys me that this function isn't entirely done yet. Please go take this function and fix it such that this html markup is properly removed. I promise this will be the last time we are going to be fixing this function. Over to you.

10 s Fix It For Good

Here again, we do have our remove html markup function with the parentheses already in. Here is the input that doesn't work properly. Note the usage of a backslash in order to escape the single quote, which otherwise would be seen as a delimiter around that string. We can print this out to see whether it contains the right value, and you see it has the don't in here exactly as in our example. In order to address this issue, we need to record which quote character we actually had and which we need to check for again. For this we need to change these lines in here. What we're going to is, we are going to use the quote variable to store the quote character, you see? Now quote is either false or it contains a double quote or a single quote, and this makes it impressibly true. Now this does only work when the quote variable is false, and this is how we start a quoted string. When we see that very quote again, we set quote to false, and this is what should now finally fix the problem in this html input. Then we press run. And now the single quote and the double quote is properly handled, and what we get is just the text without the html markup.

11 l Dependencies

After this brief diversion, let's get back to the actual deduction process. When you are reasoning what could have happened in a program, we again see the program execution as a succession of states. And then we reason backwards from what we observe to what could have happened beforehand. This reasoning, this backwards reasoning is actually structured along the ways that earlier events in the program could have influenced later events. The most important concept when reasoning backwards is called data dependency. The idea is as follows: We do have 2 statements, say A and B in the program, and now A writes a variable, which is later read by B. In our example up here, A may have written this variable, and this will then be read by B. Then we say that these 2 statements are data dependent on each other. B is data dependent on A because there is a flow of data from the statement A to the statement B. This concept of data dependency allows us to trace back the possible locations in the state as well as the statements that cause them back within the program execution and therefore to isolate the possible causes for an infection and later the failure.

12 q Find Dependency

Let us take a look again at our remove html markup function. Here I'm going back to the earlier version, which is sort of fixed. Now let's take a look at this condition up here. We want to know where the quote value could possibly have come from. To do so, we follow the data dependencies. What are the statements that this statement is data dependent upon? To do so, we will look at the places where quote would be written. And which also would be executed before this statement will be executed. For instance, this statement would be data dependent on that earlier statement. Because here quote is being written, and here quote is being read. Therefore, the statement A up here sets the state that B later on keeps on processing. If you want to understand how B behaves, we follow the data dependencies to A and find that this is one of the statements that sets the state that B depends upon. Now for a quiz. Which are the other statements that B data depends upon? Is this for C in S, is this elf of C equals the greater sign and not quote, is this quote equals not quote, or is this out equals out plus C? Check all that apply.

12 s Find Dependency

Let's check the variables that are read by B. This is the variable C and the variable quote. Lets first check C.  Where is C being written? C is being assigned here in this for statement. Therefore, this statement indeed is what B is dependent upon. Next one down here. Here we have C and quote again, but they are only being read and not written. Therefore, these do not influence the data at B. Down here we have quote equals not quote.  This is obvious. Quote is being set, and therefore we have a data dependency. Finally here, we have out equals out plus C. Here the out variable is being written, but nothing in here reads the out variable. Therefore, there is no data dependency.

13 q Control Dependency

When we are reasoning about a program, our reasoning follows these dependencies. In this case, if we want to know where C comes from or where quote comes from, we follow the dependencies to the specific locations, and we can do so again. If we are up here, for instance, and we want to know where C comes from, well, C comes from S, and S comes from up here. S first goes down here, then defines C, and then C is being checked. Likewise, if we want to know where quote comes from, quote comes from this statement. So we see again, here quote is being written, here quote is being read. So this statement depends on itself, and quote, again, can either come from this location, or it can come from the original assignment. It is precisely along these relationships that we structure our reasoning. Where does this value come from, and where was it set? If we take a look at this statement, however, we will quickly find that data dependencies are not enough because the value of quote in here may depend on the earlier value of quote, but we also need to take into account that this statement had to be executed in the first place. In order to be executed, it depends on earlier conditions. This is the concept of control dependency. If there is some statement which controls whether the statement B is executed or not, then B is being control dependent on that very statement. In our example up here, for instance, the condition in A controls whether statement B is executed or not. Therefore, B is control dependent on A. Again, such dependencies guide our reasoning. We find that B was executed, and we want to know why it was executed, after all. In order to figure out why it was executed, we follow the control dependencies. Here is a quiz. Which other statement does B control depend upon? Is this for C in S? Is this the first if statement? Is this the first elif statement? Or is this the last elif statement? Check all that apply.

13 s Control Dependency

The for statement up here, indeed, controls whether this entire block is executed or not. Therefore, it also controls whether B is executed or not. If this condition holds, then tag is set to true. If it does not hold, execution resumes for the remaining conditions. And therefore, this if condition also controls whether this is executed. Same thing happens for the other condition. The last condition, however, only controls whether the character will be edited out or not. It has no influence on whether code is being set or not. Therefore, this statement does not influence whether B is executed or not. B is not control dependent on it.

14 l Follow The Dependencies

If you look again at our earlier steps in the deduction process, you will find that each of these steps precisely follows either the data dependency or a control dependency. Let me use red to show data dependencies and green to show control dependencies. We start with the failing assertion. Here, out has a less than character in there. Where does out come from? We can follow it back, using the data dependency, to this statement. We can also follow it back to the earlier statement, but that is not so much of interest, because here, out is just empty, and with an empty string, this assertion would not have fired. By following back the control dependency, we find the tag was false. This is step 2 in the deduction process. And we also know that C in here was a less than character, and since this up here controlled whether the addition to out was executed or not, we also get a control dependency up here. This statement was not executed, and this condition controlled it. Therefore, we can deduce that quote was true. This is step 3 in here. So we now find the place where quote was set. This was down here, again, the data dependency, and since this was executed, the governing condition with a double quote character must have been true. So we start with a failing assertion, follow back the data dependency to out, follow back the control dependency to quote, follow back another data dependency to quote, and then, finally get to the governing condition in here, which also is the place where the defect is.

15 q Backward Slice

If you keep on following data dependencies and control dependencies starting from a given statement, the set of statements that you get, that is, the set of statements that could have possibly influenced the statement in question, is also called a program slice, also called backward slice starting from statement, contains all of the statements that the statement S in question would transitively depend upon. You obtain a backward slice by starting with a statement S, and then following all the dependencies until you have reached a fixed point. The interesting thing about slices is that anything that is not in the slice cannot have influenced the stage at the statement S or whether S is being executed or not. Therefore, the slice can act as a filter. Let me illustrate this by an example. As an example, let's take a look at the statement, "tag is true". This is our statement S. Now, let's see what's all contained in the slice of tag. First of all, there is no direct data dependency because no variable is being read in here. However, this is control dependent on this F condition. This if condition, again, is dependent on the character C, so this is also part of the backward slice, and this condition up here reads from the variable S, which is passed as a parameter up here, so this is also part of the backward slice. Now let's go to quote. Where does quote come from? It is being initialized up here and set down here, so we end up in the place where quote is being set. Now, can you keep on doing this? Completing the backward slice of S? One by one, check all statements that are part of the backward slice.

15 s Backward Slice

Okay. Lets complete this thing.  We are here in quote equals not quote. This is control dependent on this earlier statement, which again reads from C, that we have seen the dependencies of C before, but it also reads from tag. So this is dependent on all the places that tag is being set, and then again this is up to this one up here, and then again whether tag is being set or not, implies a control dependency towards the governing conditions. What is usually more interesting in the backwards slice itself, is what is not contained in the backwards slice. That is, the statements that are not checked. What you are seeing here is the statements that are not part of the backwards slice, are statements that refer to out, setting out, checking out, and returning out, but nothing of what happens to out actually has any effect on tag at this point. And this is precisely what the backwards slice gives us. It tells us if we want to know why this statement was executed. Well, we know it can't depend on out, because there is no dependency of tag towards out in any way, or out cannot influence the value of tag in any way.

16 q Forward Slice

When there are backward slices, there are also forward slices. A forward slice contains all statements that depend on a specific statement. As an example, let's come up with a forward slice of the initialization of the out variable. Very obviously, the final return statement is part of the forward slice because it reads from a variable which is set over here, namely, out; therefore, it is data-dependent on this earlier statement. And, therefore, it's part of the forward slice. Now for the quiz: Which other statements are contained in the forward slice of S? Check all that apply.

16 s Forward Slice

That was fairly easy. What we need to check is simply statements that read the out variable up here, which is down here: out=out+c and the final assertion. We can now check whether anything else depends on the execution of these statements. The only one that's in the loop is here: out=out+c, but none of the other statements up here ret something from out. So if you want to know how this setting affects things downstream, the forward slice will tell you, "Well, it can only affect these 3 lines down here." Anything else in between will not be affected by the value of out.

17 p Dynamic Slice

The interesting thing about slices is that they can be determined automatically. That is, a slicing tool can automatically determine backward slices of individual statements and forward slices of individual statements. Such static slicing tools, therefore, can help you focus on specific parts of the program, telling you the possible influences either off a statement or the possible influences towards a statement. Such slices become even more interesting, though, when we apply them not only to programs but to actual executions. These are then called dynamic slices. These apply to executions instead of programs. That is, rather than reasoning in a program where a value came from, you look at the actual execution, typically the failing execution, and therefore not only know what could have happened but actually see what has happened. The base of a dynamic slice is not the program but a trace instead. A trace lists the statements in the program in the order in which they were executed. So, if line 3, for instance, was executed 4 times in a row, then the trace will contain line 3 four times followed by line 4, followed by line 5, and possibly going back to line 3 in case there's a loop. Within the trace, we can now look again at dependencies. That is, looking at which variables have been read and which variables have been written. And if we find, say, that at the bottom of the trace some variable is wrong, we can now trace back the dependencies in the execution and again use this as a base for debugging when following back the cause-effect chain through the program. The first thing we need for this is a trace. Let me show you how to get traces for Python programs. So here, again, we have our original remove HTML markup function, and what I've written down here is, again, a tracing function which accesses the file name of the code as well as the current line number that's executed, and we print this out on standard output. We record this as our tracing function. Let's use the "buggy" version of the remove HTML markup function here in order to have some more fun, and we feed it with this very simple input, just 2 characters, double quote and less-than sign, which should expose the error. If we go and execute this, then we should be able to see the sequence of lines as they're executed. And we click on Run. What we see here is that first line 4 was executed, then line 6, then line 9, then line 11, line 13, line 14, and this is how we progress through the program execution. Now for a bit of programming exercise. Complete the program which you've just seen such that it prints out the actual code lines instead of just the file name and number. That is, replace the output of file name and number by the actual code line that is in that file at this position.

17 s Dynamic Slice

So a very simple way--not really efficient, but it works-- is to open the file, read all the lines which then come in an array indexed by 0, and then we simply take the line number minus 1. In the array, the lines start with 0; however, in our trace the lines start with number 1. And since the lines already contain the required new-line character, we put in a comma at the end to suppress the second new-line character that would otherwise be issued by the print statement. Let's try this out. We run the whole thing, and now with every line the file name should be opened, line should be read, and the one, single executed line should be printed. We run the whole thing, and this is what we get. You see the first tag is false, being executed, then quote is false, being executed, out being set to the empty string is being executed, and here now you can see the entire program one by one as it produces the output. And this is then what makes the actual trace of the program.

18 q More Slicing

So here again we have our dynamic trace, now a bit bigger. Remember that the input was double quote followed by a less-than sign. What we get in the end is the output, which is just the less-than sign. In the dynamic trace, we can now, again, follow back the dependency. For instance, from out--out is being read here. Where was it last written? That's over here, so this depends on this earlier statement. Here we have out that's being read. Now in the dynamic trace you can actually follow this whole thing and see where it was last written, again, which is up here. And here we have the character c, which stems from the second iteration of the for loop. And this relates to s, which depends on the input. So, again, we have a chain of dependencies: out going up here, up here, up here, up here, and you can also see this as a cause-effect chain. S had this value; therefore, c became a less-than sign, which was edited out, which finally resulted in the input also having a less-than sign. Again, we can use these dependencies to build a slice. However, now the slice would be a dynamic slice because it is built on the dynamic trace. Starting with the assert statement, we see that out=out+c is being executed, and therefore part of our slice. We see that the initialization of out is part of our slice We see that the for loop is part of our slice. And, of course, when we call "remove HTML markup" where s is being set, this also becomes part of our dynamic slice. So far we only looked at dynamic data dependencies, but of course there are also dynamic control dependencies. Every condition that gets evaluated, that is, executed and controlled whether a statement in question is executed or not, builds a dynamic-control dependency. Therefore, since we executed out=out+c, the controlling conditions are also part of the dynamic slice. From these conditions, we again get more dynamic data dependencies, which you can look up, again, in our dynamic trace. For instance, here the tag variable, which is being read over here, was last set up here. Therefore, this condition is data-dependent on this initialization. So here's a quiz. Which other statements in the program are also part of the dynamic slice? Is it quote=false? Is it tag=true? Is it tag=false? Or is it quote=not quote?

18 s More Slicing

Again, the dynamic trace gives us the answer. We have the variable quote, which is read over here and last set up here. So this becomes part of the dynamic slice. Likewise, we have quote which is read up here, for instance, and set up here. This also becomes part of the dynamic slice. However, these two lines, tag being set to true and tag being set to false, are never executed and therefore the values they set into tag-- therefore, these two statements do not become part of the dynamic slice.

19 l Slices in Real World

In our example, the dynamic slice simply excluded only 2 lines out of the program, namely these 2 lines. This may not sound like much in terms of reduction. In a larger program, however, a dynamic slice can reduce the number of statements to look at considerably. First, they contain only executed lines. That is, lines that are executed don't become part of the dynamic slice in the first place. And, of course, a line that's never executed can't have anything to do with a bug. It may have something to do with a fix, though. Second, they only contain statements that actually influence the output. If your output contains several independent parts, then a dynamic slice of just that part will be much, much smaller than the entire program. In 2010, we did a study on 7 bugs in Java programs and measured how big their dynamic slices would be. To start with, on average only 7.3% of the lines were actually executed, which means that a simple coverage tool which tells you which statements are executed and which ones are not will really focus the search to a very small part of the program. When looking at the dynamic slice, the reduction in size becomes even more apparent because, again, on average the dynamic slice encompassed only 2.8% of the lines in the program. Since there are nice tools available which compute dynamic slices automatically, using such a tool in the first place will immediately tell you which places of the program you can safely ignore because they are not executed or because they cannot possibly have influenced the output with respect to the bug.

20 q Dependencies and Scientific Method

How do dependencies fit into our model of debugging? Well, that's fairly straight forward. When we see a failure, we see which part of the state is erroneous. Then we track back the dependencies to see which earlier states could possibly have caused that infection. We determine these possible states as well as the locations in the program where they would be caused through the dependencies. So, if we see an error down here, it could have come from here, from here, or from here. In one out of these three, or at least one out of these three, should contain the infection that we're looking for. So we use dependencies to find possible origins for each for each infection. In the second step we use the scientific method to track down infections. We have the choice between three possible origins here. So, we use the scientific method to find out which of these three parts of the state is at fault. We set up an experiment. We make up the appropriate observation, and we gradually refine or reject our hypothesis until we have come up with a diagnosis and figured out which part of the state is wrong. Then we repeat the whole thing back and back and back again. Again, choosing between multiple possible origins, following back the dependencies, and again using the scientific method to track down which of these actually is at fault. Instead of the scientific method, you can also use deduction to rule out specific possibilities. For instance, you may be able to show that neither this one nor this one can possibly have influenced the state under these circumstances. So, the only one that remains is the one up here. You repeat the process until you find a statement whose in-going state is all correct, but where the out-going state is infected. So, how do we call a statement whose in-going state is all correct, but its out-going state is infected? What is this? Is this a cause, a defect, or an infection?

20 s Dependencies and Scientific Method

Well first and foremost, this is a defect because if a statement produces an infection then it must be erroneous itself, and an error in the code is what we normally call a defect. Since a defect in this situation implies that we can actually fix it such that the infection goes away, it is also a cause, because it causes the infection in question. The term infection, however, only applies to program states. Therefore, it is no applicable in here.

21 l Likely Origin

Even if you do have dependencies and assertions that help you rule out large parts of state, you may still end up with a multitude of individual origins where a specific infection may come from. While you can rule them out one after the other using the scientific method, the question is of these origins are you going to look at first? The idea is to look at the most likely origins first. The question is what is a likely origin. What possible origin should I look at first? Here are a few guidelines: First and foremost, infections. If you know that some origin is wrong, go for it. Next is causes. If you know that some state causes the failure, because you can change it to another value. Such if the failure goes away, . which is something you can find out through Delta Debugging, for instance, follow it. Next up: Code smells--If you suspect some code to be wrong, or you have gotten warnings from a static checker, go for it. Next up is bug history. If you know that some piece of code has gotten a lot of problem reports lately, chances are what you're looking at will be another problem report. Next up is last changes. Code that has changed recently is way more likely to have errors. So go for code which has recently changed, and go for the state that comes out of this code. Finally, anomalies. If some code shows abnormal behavior before reaching the failure, for instance, by producing a log entry, follow this one as well. Of all these features infections are the strongest, because they are sure indicators of errors, followed by causes. Any cause implies a way to possibly work around the failure. As far as the others are concerned though, this is up to you and the specific project. In fact, this is where your knowledge about the specific project and its domain and the code comes into play. Being able to specifically focus on the most likely sources of a bug makes you a debugging expert for the specific project.

22 l Automate This

To close, we're going to use Delta Debugging to do something pretty cool, namely to give us a full diagnosis on what's happening when the program fails. Our diagnosis will look something like this: First this variable had this value. This caused this other variable to get this other value. Then this third variable gets set to this other value. That is what finally made the program crash. In other words, what we get is cause-effect chain throughout the program, which explains how the failure came to be in all of this automatically. This cause-effect chain may or may not include the infected values, but frequently it does. Even if it does not, it immediately helps you understand how the failure came to be. The basic idea is as follows: If we can change any of these variables such that the failure no longer occurs, then we have found a failure cause. How should we change a variable? After all, variables can take arbitrary values. The rule is not to make them use arbitrary values but to use values from a successful run. That is, during execution we change variables from the values found in the failing run to values found in a successful run. If we can change a variable value such that the failure goes away, we do have a failure cause.

23 q Minimum Set of Changes

Here again is our remove html markup program. If we invoke html markup with s being a single quote followed by a less-than sign, it passes. However, if it's a double quote followed by a less-than sign, it fails. So, this difference in the original input determines whether the run passes or fails. Let's go and execute the program a bit further but stop execution when the loop head is reached for the second time. Now again we can examine the state. The variable s stays unchanged at this point. The character c is still the first character being processed. Which is different? In the passing run, it's a single quote. In the failing run, it's a double quote. The variable tag is false in both cases. The variable quote is different. In the passing run, it is false. In the failing run, it is true. In the passing run, the out variable contains a single quote. Whereas, in the failing run, the out variable is empty. What you see at this point is that four variables, namely s, c, quote, and out, all have different values. You can now imagine that if we were in the passing run, and we would set these four variables to the values found in the failing run, then we would effectively make the passing run a failing run, meaning that these four variables, which defer, make up a cause for the failure. However, it suffices to set only a subset of these variables to the values found in the failing run. Only a subset of these variables need to be changed in order to cause the assertion to fail, and therefore, the entire run to fail. So, here is a quiz. Which of these four variables can be set to values from the failing run to make the passing run fail? Is it s--is it c--is it quote--is it out, or is it a combination of multiple variables? Hint: If you said all four, this is the correct answer. What I want is a minimum set of variables. Over to you.

23 s Minimum Set of Changes

Here again is a remove html markup program. Here's the input which normally passes. If I click on run, what I get is just a single quote. That is, the opening tag was probably stripped, and of course, the assertion didn't fire. I am now setting up a trace function, which specifically monitors for the moment. The loop head here in line 8 is hit for the second time. That's when I'm setting the quote variable to true as found in the failing run. So the question is whether by setting the quote variable to the value found in the in the failing run at this moment, we can already turn the previously passing run into failing run. We figure this out by clicking on run. As you can see, simply by setting the quote variable to true, we now have triggered the assertion. What this means is that simply setting the quote variable to true is sufficient to make the passing run now fail. We thus have identified quote as a cause for the failure.

24 l Path to Automation

The question is: Can we do such a thing automatically? The answer is yes. We can do so using Delta Debugging. The idea is as follows. At a given location we extract the state for the failing run as well as for a passing run. Then we go and compare the states. What we then get is a set of differences between states found in the passing run and states found in the failing run for each single variable. With Delta Debugging, we can now find a minimal subset of these differences that causes the passing run to fail. This minimal subset then at the given location is the variable that causes the failure.