Race Conditions, Distribution, Interactions: Testing the Hard Stuff and Staying Sane
Hughes, John
Even the best test suites can't entirely prevent nasty surprises: race conditions, unexpected interactions, faults in distributed protocols and so on, still slip past them into production. Yet writing even more tests of the same kind quickly runs into diminishing returns. I'll talk about new automated techniques that can dramatically improve your testing, letting you focus on what your code should do, rather than which cases should be tested-with plenty of war stories from the likes of Ericsson, Klarna and Basho Technologies, to show how these new techniques really enable us to nail the hard stuff.
 Okay, I guess it's about time I got started. My name is John Hughes. I have been doing functional programming for many years. I've been a professor at Chalmers University in Gothenburg for the last 20 and for the last seven years or so I've also been working at my company, Cubic, on testing techniques. So I want to start off by asking who really, really loves testing? Oh, more hands than usual, but still very few. So why is that? Why is testing hard? Well, imagine that your testing code that has N features, let's say. And you write maybe three or four tests per feature. That's okay. That's a linear amount of work. No problem. But we all know you won't find all the bugs that way. We all know there are bugs that only appear when you use two features in combination. So how many tests are you going to have to write to test all pairs of features? Quadratically many. That's starting to sound like quite a bit of work. And you know, not all bugs appear when you test two things together. Sometimes you need combinations of three features. Oh, that's not good at all. And that's just for sequential code. When you come to race conditions, by definition, those are interactions between at least two features. And what's worse, they don't even appear every time you run the test. Ah! Testing is awful. So what's the solution? Well, obviously, if writing test is hard, don't write tests. Okay, I have a bit more time. Generate them. And that's what this talk is about. I'm going to tell you about a tool called QuickCheck that I began there. I couldn't class it on myself, invented a little more than, well, I guess 14 years ago now, for Haskell for purely functional code. And I've been working more and more with this approach ever since starting the company in 2006. I'm going to show you the version of the company markets because that's the one I've used most nowadays. And I've been having lots of fun solving challenging testing problems in the field. So what does it do? I'm going to show you a QuickCheck demo. If you were in my talk yesterday, you will have seen a QuickCheck demo. Don't worry, this is a different one. So what we do is we have some API under test, and we generate test cases, sequences of calls from that API, random ones. And keep doing that until we find one that fails. When a test fails, it's very rarely because of every API call in that sequence. It's usually just the few of them that interact badly. So the next thing that we do is identify those few, filter them out, and create a minimal failing example. And those minimal failing examples are typically really easy to debug. There's a problem, though. If we're going to generate tests, when you write test cases by hand, you're writing a particular test, and you can predict what the expected output should be. When you're generating a test, you don't know, as you're writing the test code, you don't know how you're going to invoke your system. So how can you tell whether an arbitrary test has passed or failed? Well, you can't use expected results in general, because you don't know what they'll be. You don't know what test you're going to run. What we have to do instead is come up with some general properties of the code that should be true whichever test we run, and then test those instead. So because of that, when we do this test case generation, then we have to formulate properties of our code, and for that reason, I call this property-based testing. Okay. So let me show you a demo. I am going to test a little bit of C code. Here it is. So today I'm going to test a queue implemented as a circular buffer. So I'm sure you all read C better than I do. Here is the representation of the queue. There's the pointer to the area where we're going to store data. This is the index where we're going to put things in, the index where we're going to take things out, and the size of the buffer. Here's the code to create a new queue. We allocate space for the data. We initialize the fields. We allocate the space for the struct. Initialize the struct in memory, and then return the pointer. Okay. So here's how we put something into the queue. We write it to the buffer at the input index, and we increment the input index more to the size. Okay. What could be simpler? Here's how we take something out. We read from the queue at the output index. We increment the output index modular to the size. So this is really simple code. Here's how we tell how many items are in the queue. We take the difference between the input and output indices modular to the size. Okay. So this is all obviously correct. There's nothing up my sleeve. It's just an example to show you how we can test this kind of code with QuickCheck. So in order to test it, I'm going to be using the Erlang version of QuickCheck, which means I'm going to need to load this code into the Erlang shell. So let me do that. And we've built something to make it very easy to test C code from Erlang. So now that I've done that, I can call the C code and create a queue of size 5. There we are. It returns a pointer to a struct queue. And then I can put one into it, let's say. Let's put two into it. Whoops. Sorry about that. Let's get something out of it. What? Okay. Thank you. Let's get an item from the queue. We get one. Get another one. We get two. Uninitialized memory. Some more uninitialized memory. There's the one again. There's the two. It's a circular buffer, right? So I just want to show you. It really is the C code running there. There's nothing funny going on. We've compiled it with GCC in this case. So it's running in the background there. Okay. So how are we going to test this? Well, we model the behavior of this kind of code in Erlang as a kind of state machine. So we generate test cases that are these sequences of API calls, but we also model what state the code should be in at each point. And for every API call, we write a state transition function that specifies how the model state changes. And then we write post conditions to compare the actual results from the running C code with what the model state says. And if all those post conditions are true, then the test passes. So in all of the specification stuff is in Erlang, even though the code under test is in C. For example, here's a test case for the queue. Put one, put two, do a get, put three, do another get. How can I model the queue? Well, what about the list of elements that should be in it? That's a very simple declarative model of how the queue should behave. And at the beginning, it should be empty. Then after put one, it should contain just one. After put two, it should contain one and two. After the get, it'll only have the two and so on. And then when we check the post conditions, in this case, only get has an interesting post condition. And it just says that the result that get returns should be the first element in the list of elements in the queue. How do we write this code? Well, here's a couple of fragments. Here are the state transition functions for put and get. I know most of you probably don't read Erlang, but I hope this stuff will make sense anyway. What does the first line say? It says, well, when you do a put, the next state, after you put x into the queue, takes the, okay, I can't resist, it takes the old list of elements and adds x to the end. And you end up in a state in which the list of elements has been replaced by this extension. It's the extended list. Here's the one for get. We just take the tail of the list of elements. So we discard the first one. It's very, very easy to write these functions. Here are the post conditions of interest. The one for get says that the result that's returned should be equal to the first element of the list of elements. The one for size says the result we get should be the length of the list of elements. Once again, very, very simple to model this stuff using, in particular, we use lists a lot because Erlang has such rich operations on them. Okay. Let's run some tests. Where's my Erlang? Here it is. Okay. So I will need to compile the code which I haven't shown you. Well, the code I showed you fragments of, that's my specification. And having done so, I can use QuickCheck to test the property that I've written in that code. And darn, it fails. So what happens here is that I've generated a lot of random tests. Some of them passed. You can see there, those dots represent passing tests. And then, blah, this random test failed. But before we start analyzing it, then QuickCheck has actually done something we call shrinking. So it's searched for a simpler test derived from the random one that also fails. And this is what we end up with here. Right? So this shows us what happened. We called Q new to create a Q of size one. We put zero into the Q. We put one into the Q. What does the Q contain? Zero one, right? We call get. What should we get? Zero. What did we get? One. And this reason here tells us that the post condition failed. We got one. We should have got zero. Okay. So now I'd like you to put on your debugging hats and see if you can tell me what went wrong. Yeah, the Q is only one element long. And I put two things into it. It's a circular buffer. So the second thing overwrote the first. So of course it didn't work. But whose fault is that? Right? So obviously my fault. But the model, yes. So in fact, you shouldn't do this. And my test shouldn't do this either. Of course it's not going to work. And so what we have to do is we have to exclude this test, which I can do now. If I go to my model and here you can see the code fragments I showed you. Here is a precondition for get that says, okay, it says the state pointer has must be defined. That is you have to have a Q. You must have called new first. And the list of elements must not be empty. Of course you can't do get if the list of elements is empty. But here's the precondition for put. All it says is that you must have a Q pointer. Well, that's not enough, of course. You shouldn't do put unless the length of the list of elements is less than the size of the Q. So let me add that precondition. The effect of that is going to be if I recompile my spec, that when I rerun the same test, so this doesn't generate random tests, this just reruns the last one that failed. It fails for a different reason. It fails because the precondition of put was not true. So it was a bad test. And now if I generate tests, they'll all pass. Okay? That's cool. What you see here is some statistics on which operations we tested. We tested a few more puts than gets because you can't do a get until you've done a put. But we didn't test size at all. Why was that? That was because for simplicity, I commented out the specification of size. So let me just comment that back in again. Okay? You can see the precondition says you have to have a Q. This says how to generate a call of size, or how to call it. And this says the postcondition that I showed you before. So let me recompile that and now rerun my random tests. Darn! Another one failed. Okay, what happened here? We created a Q of size one. That's fine. It returned this pointer. We put zero into it. How many things are in the Q? One. I asked for the size. It returned zero. Okay. Whose fault is this? Mine. Yes, of course. But is it the model? No. No, this is really a wrong result. This is the code. We've put one thing into the Q, but the size function has returned zero. How is that even possible? Let's look at the code. Okay, here's the code for the size function. I've put one thing in. This returns zero. Size is one. How could it possibly return zero? Oh, return something, module one. That's always zero. So when the Q is of size one, this is always going to return zero. That can't be right, can it? So if you think about it, even when I put one thing into the Q, I incremented my input pointer and it wrapped around immediately. So my full Q looks just the same as an empty Q. And what's worse, this isn't just a question of Q's of size one. If I had a Q of any size, when I fill it full and the input pointer wraps around, both my input and output pointer are zero again and it looks empty. So the problem here is that I can't distinguish a full Q from an empty one. My representation isn't rich enough. Okay, how shall I fix it? Any ideas? So I could put a flag in there, couldn't I? But that would be so ugly. Let me show you a beautiful hack. When I am asked to create a Q of size n, do you know what I'm going to do? I'm going to make one of size n plus one. Don't tell anybody. Now, as long as the clients respect my preconditions, they can never see this bug because they can never put n plus one things in the Q. And if they do, it's their fault. Cool. Okay, so let me recompile the C code after making that fix and rerun the last failed test. Now it passes. And just to make sure, let's run some random ones. Darn, another test failed. Okay, put your debugging hats on. What happened here? I made a Q of size one. That's really two. I put a zero into it. Now it's full, pretending to be size one. I did a get to take that zero out. Now it's not full. I did another put. Okay, that's the second one. And then I asked for the size and it returned. Well, I've done two puts and one get. How many things are in the Q? One. Size returned minus one. How is that possible? Here's the size function. What went wrong? Anybody care to debug that? Right. The input pointer, I put two things in. The Q is really size two. The input pointer has wrapped around. The output pointer has not. So we get zero minus one, module two. But just a minute, minus one, module two should be plus one, right? Let's just check that. Darn. It's not. It's not an error length. Neither in C. So the problem is that when this expression becomes negative, I get a negative result out of size. So I have to make sure that this expression is never negative. How shall I fix the code? Absolute value. Of course. Let's recompile the C code. Let's rerun that test. Now it passes. Okay. So now I found the bug. I created a test that revealed the bug. I've amended my code. Now the test passes. All my tests are green. I'm done, right? Shall I run some random ones just for fun? Let's try that. It still fails. Look what's happened here. Here I created a Q of size two now. That's one step bigger. So that's an improvement. I've done three puts. That makes the input point to wrap around. One get. Three puts, one get. How many things are in the queue? Two. What did size return? One. And why was that? Because absolute value is the wrong thing to do here. Because it changes the value modulo size. What I need to do is to make sure that this expression is positive without changing the result of mod. And I can do that if I add Q size here. Because the difference between input and output will never be greater than Q size. So this will be always positive. And if I now test this, that previous test that failed now passes and so do all of the others. And I could run any number of tests now. They will all pass. So it's surprisingly how often we see the effects of what I just did in real code. Where we find some code, it's complicated. We can't understand why. And obviously what's happened is that somebody had a bug. They had a bug report and a test case. And they made the code work in that case without really understanding what the problem was. So all they've managed to do is make the code more complicated. They haven't managed to make it work. Okay. That was my demo. And the lessons I want to draw out from this are that first of all, the same properties can find many different bugs. And also those minimal failing tests make diagnosing things very easy. You know that if you delete any one step, then the test would pass. It is possible that if you deleted at the same time, you know, five steps from the middle of 12, and you picked just the right five, that you might be able to shrink it further. So we don't, we can't explore every possible simpler test. That would take far too long. So you have a weak guarantee. But usually it really is the minimal case. So we think of the shrinking process that has produced these minimal failures as extracting the signal from the noise of random tests. You get a lot of noise in random tests. And if you try and debug randomly generated stuff, it's impossible. But when you extract the signal, it's quite easy. Yesterday I talked about a big project that we've done in the last couple of years when we tested C code going into cars. Protocol stacks and other components that are part of the AutoSAR standard. Thousands of pages of PDFs we converted into specifications of the kind I've shown you. We have code from six different vendors to test. And we found hundreds of issues in the code. And of those, all of this code was supposed to implement the same standard. We found more than a hundred bugs in the standard. So that was a really, that's a really exciting project. But I talked about it yesterday. So I'm not going to say any more about that today. What I do want to do is show you a couple of other examples of database testing that we've done. And first of all, let me kick off with React. React is a no SQL distributed key value store. It's very scalable and fault tolerant and lots of good stuff. But it's only eventually consistent. So what does that mean? It means it's very hard to test. Because what does it even mean? I mean, suppose you do something with the database and then the result at the end of the test is not consistent. Well, it's only supposed to be consistent eventually. Maybe it's not eventually yet. So because of the nature of the beast, it's fundamentally quite hard to test. And so a year and a bit ago, then I did some work with the bash guys on trying to develop properties for testing React. We deliberately kept our tests as simple as we possibly could. So we realized that we would start off by testing the database. It's a key value store with only one key and one value. Maybe that sounds rather pathetic. But look at it this way. If we don't understand what the database does with one key, how can we possibly understand what it does with many? So we were deliberately taking a very simple model and then we would complicate the model only when we were really forced to by a failed test. I think that was a really good strategy for developing a good model of this complex software. Okay, so let me explain the React API. It has put and get operations. I'm not going to show the keys because there is only one. So you might put zero, one client put zero, another client does a get and on the same key and that client will see zero. And then maybe that second client might put one and the first client might do a get and will see one. I think we understand what React is supposed to do now, right? So here's an example that QuickCheck concocted. You put zero, it's all one client, you put zero, you put one, you put zero again and you do get. What will you see? One. Huh. That wasn't really what our simplest model was expecting. Now actually I'm pulling the wool over your eyes a little bit here because the API doesn't let you put a key and a value into the database. You put a React object into the database that contains a key and a value. And that means there's two different ways that you can do a put. You can create a new React object and put that in or you can take a React object you've already got, for example, because you just put it in the database and modify it. Modify the value and put the modified React object in. And in this test case, the first and last puts were putting a new value, so creating a new object, whereas the middle one was updating the first one. So we generated this test and I said, look, it shouldn't do this. And my friends at Bashow said, what are you thinking of? You shouldn't do that. This isn't a new key anymore. Why are you calling put new after you know the thing is in the database? So don't do it. So why didn't it work? Because all of these values are data or timed, timestamped with vector clocks. And at the time, React kept track of how many times each client had manipulated the value of that key. So if you think about it, we do a put new, then we do a put update. When we put the one, the one has been touched twice by this client, but the last zero has been touched only once because it's a new object. Touch twice is more than touched once. Therefore the one is newer than the zero. Therefore React discarded the zero. Okay. Well, so my friends at Bashow insisted this was the right behavior. But after we discussed it, they said, you know, there's this design rule for how you use the API that once you, for example, read an object from the database, you mustn't create a new object with the same key. You must modify it and write it back. So you have to be careful using the API. And then they were started thinking, I wonder if all our users know that. And not even they had thought about the fact that if you didn't follow the design rule, you could lose data. So it was quite good to at least elucidate that design rule. So that was our first step. So now what are we going to do, right? What are we going to do about this test that fails? Should we put vector clocks into the model? No, of course not. The model is supposed to be simple. It's supposed to be something that the user can use to understand how the database should behave. It shouldn't talk about vector clocks in the implementation to figure out what's going to happen. So the only other thing that we could do was put into the model, you shouldn't do that. And we did that. We made the model record each client's last view of the value. That is, every time we did a get, we would record what the client saw. And then we added a precondition that said that if a client has a view of the value, then it must update that view when it does a put. So you're not allowed to do a put new. And then we generate tests that respect that precondition and they all pass. So that was good. Okay. So let me tell you more about React. React supports, it's a very fault tolerant database, so it supports redundancy. When you do a put, it doesn't just go to one node, it by default goes to three. And if one of those nodes goes down and you do the put, then it will pick another node somewhere and store the value there instead. So at this point, you can see that there is a down node that has a stale value on it. Now, React remembers that that fourth value is in the wrong place. And it remembers where it should be sent back to. And when the node that was disconnected comes back, then there's a process called handoff that returns the value to the correct place. But handoff is not immediate. So there is a period when a node can come back and contain stale values. That's why it's eventually consistent. The other thing I have to explain to you is conflicts in React. So what happens if two clients put different values at the same time to a key? Well, you might say, ah, it looks as though the one arrived a little later will say that one wins. But no. Instead, React saves both values. It's called a conflict. And the next client to do a get will see them both. And the idea is that the client will then resolve the conflict by putting a single value back again. And future clients will then see the resolve value. So why do it this way? The idea comes from the original Dynamo database that Amazon developed. And the model here was the Amazon shopping basket. So suppose you're shopping on Amazon on your phone and your laptop at the same time. And they may be connected to different networks, going to different servers in maybe different clusters within Amazon. So what if you put one book in your shopping basket on the phone and another book in your shopping basket on the laptop? But the servers can't talk to each other. Now you've got a conflicted value for your shopping basket. But when you go to check out which value do you want to see? Which books do you want to see in your shopping basket? Obviously both, right? At least that's what Amazon wants you to see. So the conflict resolution there is just to gather everything up and smush them all together. But there are lots of examples where that's application dependent conflict resolution is useful. So we wanted to test React for eventual consistency. What we did was that means we were testing its behavior when nodes would become unavailable. So we generated random sequences of React calls, but also for each call, a random collection of nodes that would fail during that call. And then we tested to see whether at the end of execution we saw the correct values. Now when a test fails, normally here it's because of only a few of the calls, but also because of only a few of the node failures. And so we would shrink down these tests to get a minimal failing test with a minimal sequence of calls and a minimal set of node failures that you need to make the test fail. Let me show you the case we found. Here we are, two clients. This one puts a zero and then gets it back again. Now this client gets the zero and puts a one back. This client puts a two. Now those two puts are in conflict because the client on the left has not seen the one that the client on the right put. So when we do a get, we should see both values. What did we see? Only the one. Now why did that happen? To explain it, I have to show you the node failures. So let's bring in the three nodes now. I'm going to consider a cluster with only three nodes. When we did the first put, two of the nodes were down. Or maybe there was a network partition that meant the message didn't reach those two. When we did the first get, those two nodes answered and the other one was down. So the first client saw, oh, the value is not there anymore. That might seem strange if you put a value in the database and then you do a get and it's not there, but somebody else could have deleted it, of course. Now for the other operations, all three nodes respond. So the second client does a get and sees the zero because one of the nodes has it. The second client does a put, all the nodes hold one. The first client does a put now. Now think back to the first bug I showed you. That client is doing a put of a value that has only been touched by the client on the left because the last time the client searched for this key, it was not found. So that's a new React object. The one, though, that's been touched by both the client on the left and the client on the right. So the one is newer and the two can be discarded. That's why React just returned the one. So it's the same bug. It's the bug. You shouldn't do that. But who's doing it now? It's not me, the ignorant programmer. It's React itself doing it in response to node failures. So shock horror. React is not eventually consistent. Well, the truth, of course, is that it was not eventually consistent at this time. So what have we found? We found an extreme failure scenario. I want to emphasize that. We found a failure that arises when you have two different network partitions in quick succession with no time to heal the database in between. But it had bad results. It led to loss of data, a failure of eventual consistency, which is an important selling point for React. But it also provided a test framework that was immensely helpful when the redesign that fixed this problem was performed. Because for every attempt at a redesign, it was possible to run it through the same generated tests and in the end, to be pretty darn sure that the problem was fixed. So I just want to ask a meta question now. We found a lot of bugs in React. Does that mean React is buggy? Once I gave a talk about this material and in the discussion at the end, then one of the people in the audience said, well, I was going to use React, but I'm not sure I will now that I know it's so buggy. I just want to ask if you would rather use a database that has not been tested in this kind of way. So we've done a lot of work with Bashow and I feel React must be one of, if not the best tested database around as a result of that. So just because you managed to find and fix bugs, it doesn't mean that the product is then buggy. Okay, so that was a nice example of using React. I want to tell you one more story. It's about another database. This story starts with a message to the Adlang mailing list in 2007. We know there's a lurking bug somewhere in the debt's code. We've got bad objects and premise your end of file every other month the last year. We haven't been able to track the bug down because the file is repaired automatically next time it's opened. This was posted by a man called tupiternqvist from Klarna. Okay, so I'm sure we all feel tupiternqvist pain. But what's the context? Well Klarna develops an application that provides invoicing services for web shops. Maybe that doesn't sound terribly exciting, but since they're being founded in the mid-2000s, they've grown to more than 700 people. So it's a tremendously successful start-up. They're serving seven European countries now, and they built their entire system in Adlang. They stored their data in the database that comes together with the Adlang distribution, which is called Menezia, and that gives you transactions and replication and lots of good stuff, but it needs a back end to store its data. The disk back end is called debts. It provides tuple storage in files. Debt is the component that tupiternqvist talking about. Debt is the component that's failing every month or two. And when I heard about this, I thought failures every month or two, that sounds like a race condition. Let's see if we can track them down. Okay, so I'm going to show you how we test for race conditions with generated tests. And to do that, I'm going to go from the sublime to the ridiculous. Imagine testing these. So we have a lot of these in Sweden. Do we have them in Norway, too? You have them at a delicatessen counter, for example. So you take a ticket, and then you know when it's your turn to be served. Suppose I wanted to model that in Adlang. I'd need an operation to take a ticket, and every now and then the role of tickets runs out, so I'd need an operation to reset the dispenser back to zero. And now I could write a standard unit test for this quite easily. This is how it might appear in Adlang, where I perform a sequence of calls and I match each result against the expected value. And, well, you can see how I expect the thing to behave. But wait a minute. What is the point of a ticket dispenser? Its whole purpose is to regulate the flow of a lot of concurrent customers to one delicatessen counter, right? So what am I doing running sequential tests? Well, okay, it's good to test the sequential behavior, but this misses out on an important part of the dispenser's behavior that it should work when it's used in parallel. Okay. So if I wanted to test the dispenser, I can test it by modeling with the state machine in just the same way that we've seen before. If I've got a test case like this, then I can model the dispenser's state just by a single integer. It's really easy. And the state transition is you do an increment when there's a take, you set it to zero when there's a reset. And then the post condition will just check that the value that take returns is one more than the state when it's called. So that's really easy. But what I would like to do is to run tests like this instead. So this is supposed to represent a parallel test where first of all, I reset the dispenser and then one customer comes along and takes two tickets for some reason at the same time as another customer is taking a ticket. Okay. So what might happen here? Well, the customer on the left might get tickets one and two. The customer on the right might get ticket three. But that's not the only thing that can happen. The customer on the right might get ticket two and the one on the left might get one and three. That's also correct, isn't it? But this should not happen. If both customers get ticket number one, then something has gone wrong. So if you think about it, there are three possible correct outcomes for this test. So what are the expected results going to be? Well, of course, in this case you could just record the three tickets and then compare against the three possibilities and see have you got one of those correct outcomes. But this is a very tiny test. I don't want to run tests like this. I want to run tests like this. How many correct outcomes are there of this test? Can you figure it out? Luckily I've done it for you. Forty-two, of course. So now think about enumerating the forty-two possible correct outcomes. Nobody in their right minds would do that. And anybody who tried would get at least one of them wrong. So you fundamentally can't do that. You can't figure out the expected results for a parallel test. The only thing you can do is try and detect whether a test has passed or failed with some kind of property. So race condition testing, I think, is a killer app for property based testing. Okay. So let's go back to the parallel test that I drew before. I've turned it on its side here and asked ourselves, how do I know that this test succeeded? Well, I know because there is some order in which I could have performed those calls where the results would match the model. That is, if I interleave the calls and results like this, then they become consistent with the model. So that's what we do. We generate parallel tests and then we ask, is there any interleaving that can explain what happened? If so, we say the test passed. If not, it must have failed. I will just do one more quick demo here. I have my dispenser code. Just compile it. And I'll run, first of all, some sequential tests. So those sequential tests demonstrate that my implementation and my model match. And now if I run parallel tests, I'm using exactly the same model so it's a very slight difference to run parallel tests instead. Well, there's a race condition. And if you look at what happened, you can see we did two things in parallel. Two calls of take ticket, they both returned one. Now, the original random test was more complex. It's up here. But after shrinking, we get down to this minimal case that provokes the race. And I just want to run this test a number of times so I'll get different random tests that fail. But see where I end up. After shrinking, it's always the same minimal example. So that means that tells us that this example probably really is the minimal one. And if I go back to my presentation, that's the failing test. Here's the code I wrote for taking a ticket. So it's reading a shared global variable and then writing M plus one. It's a critical section. Where's the synchronization? There isn't any. So of course there's a race condition here. And the point is not how stupid code I wrote. The point is that given this kind of race condition, we can find it very quickly and reliably by this method. So let's go back and talk about debts instead. Debt provides a tuple store. It stores Airdlang tuples which have curly brackets around them. And the first component is the key. And it's got an API with a kind of operation you would expect. You know, you can insert a list of tuples into the table. You can delete all the tuples with a given key. Insert new is like insert except that if any of the keys is already present, then it's a no op. And it's atomic. So that's kind of nice. And there's some more. Nothing that will surprise you. So now I have to model the behavior of debts and it's really simple to do that. It's almost enough just to have a list of the tuples that I think should be in the table. So that's what I did. I wrote a spec in the same style that you've seen. It was less than 100 lines of code for the core of the debt's API. And in comparison, the implementation of debts is more than 6,000 lines of code in four different modules. Why? Because it's keeping hash tables on the disk and of course it's complicated stuff. But the intended behavior is quite simple. So I wrote my spec. I ran my sequential tests. They all passed. And I started running parallel ones. And what do you know? As soon as I did that, I found a race condition. So what's happening here? Well, in a prefix, I'm opening the file, surprise, surprise. And then I'm doing two things in parallel. I'm inserting an empty list of tuples. I'm just going to get my pointer back here. I'm inserting an empty list of tuples. That's a no op and it returned okay. And I'm using insert new to insert another empty list of tuples. That's also a no op. And that returned okay too. And QuickCheck says there's no possible interleaving of these calls that can explain this result. Okay, wait a minute. But they both returned okay. What's wrong? Sometimes there's just no alternative. You have to read the manual. Here's what it says about insert new. Look at the result type. Even in Erdlang, a bool is either true or false. It's not okay. And in thousands of sequential tests, insert new returned true or false every time. As soon as I ran it in parallel, it returned okay. Where did that come from? Okay, so I went on, ran some more tests. I found this one. In the prefix, we opened the file. And now in parallel, we do two insertions. One using insert. We insert a tuple 00. And at the same time, we do an insert new 00. So the insert new maybe could succeed or maybe could fail depending on which one of them goes first. But it shouldn't time out. And we shouldn't see a message. Error report, bug was found. So that seemed to be pretty conclusive that I'd come across another bug. So at this point, I decided that insert new just doesn't work. And I excluded it from my tests. And I found this one. Okay. So here in the prefix, we open the file. And now in parallel, one process opens the file again. You might think that seems odd. But it's not. This database is designed to be used in Erlang systems which are very highly concurrent. Many processes may use the table at the same time. Each of them must make sure it's open. So it's okay for one process to reopen the database while another one is using it. The other process is inserting a tuple into the table and then getting the entire contents and where's that 00? I just put it in. And it's gone. So I found this bug in several forms. That if one process was reopening the table, another sequential process could see an inconsistent view of the database contents where its own operations had no effect. So I sent these bugs to Hassel Bolynder at Ericsson, the man who was responsible for the code. And he said, oh, thank you very much. Here's a new version. He sent me a fixed version the next day. He said, that's great. But I don't think these are the bugs that Klarna are experiencing because the symptoms are not the same. At Klarna, the file is being corrupted. Okay. File corruption. I added one line to my test that said, after we've run the parallel operations, just check that the file is not corrupt. There was an easy way to do that. And I started running more tests. This time I had to run a few thousand. And then I found this. Look at this. In the prefix, we open the file. We close it. We open it again. Then we do three things in parallel, a lookup of something that's not there, and two insertions of the same, that same tuple, in fact. All of the results are consistent with my model. But when I check the file for corruption, what do you know? I got to prevert your end of file. So I want to emphasize, this is the smallest example that can provoke this bug. I looked at it and I thought, open, close, open, you've got to be kidding. It must fail if I just open the file and then do the three things in parallel. But no, I ran tens of thousands of tests. They all passed. Nowadays I know why. The first open creates the file. Then we close it. The second open opens an existing file. It leaves the code in a slightly different state and that difference is critical to this bug. So I really love this example because can you imagine anybody writing this test in a test suite? Why would you test this collection of six calls for goodness sake? So anyway, I was very happy to find this. I sent it off to Hassek. I got a correct version of the code back next day and then I was giving a talk at a conference in Orhooves. I was supposed to talk about something else but I thought this is such a great story. I have to tell it. Only I hadn't saved the output from running QuickCheck. So I had to sit in my hotel room making new slides and I rerun my tests and copied and pasted the output onto my slides and as I was doing that, guess what? I found this one. Okay in the prefix, we open the file and we insert a tuple and then in parallel, one process is just reopening the file again. The other one is looking up something that's not there and deleting the thing that is. Once again, all the results, all the return values are consistent with the model but when I checked for corruption, I got a bad object. I want to remind you of the mailing list message. We know there's a lurking bug somewhere. We've got bad objects and premedure in the file every other month for last year. I sent that example off to Hasse as well. Next day I got a fixed version. That fixed version has been in service at Glarner for more than a year now. There has been, well, before it was installed, the problem got worse. It was happening once a week and every time this happened, the main server went down. Its database was corrupt. All the data could be restored from a replica but it took hours to bring that machine back up again. Since the new code has been installed, they've had bad object once when accessing a file that had not been written since before the new code went into service. So it looks as though we really did nail those bugs. So a lot of work had gone into searching for these bugs beforehand, of course. I've talked to the people who did it. The developer spent six weeks at Glarner trying to figure out what on earth was going wrong. At the end of that time, they thought it seems to happen when the file is about one gigabyte. Maybe it's something to do with rehashing. Afterwards, we could reproduce the failures with a database with either zero or one records. It took either five or six calls to reproduce each of those serious bugs. And it took less than one day to fix the problem given that minimal example. And I think this really shows two things. One, the enormous value of minimal failing cases and secondly, how hopeless it is to try and debug this kind of race condition from failures in production. Where billions of irrelevant things have happened as well as the five or six calls that are actually responsible for the problem. Yeah. So I did it now and then over a period of a few days if I had an hour spare, I would spend a little time on it. But probably less than a day's work in total. It was only a hundred lines of code. So, yeah. I will just skip over this little bit I think because I've now said most of what I wanted to say. So my point is property based testing like this, you find more bugs because you can do better testing and it's less effort. Don't write tests, generate them. That's my message. And I'm happy to take questions. So you had that example that had 42 different possible legal interleavings. Do you have a way of keeping track and verifying that you've covered some fraction of the legal ones? Without feel more confident if I hit all 42 of those and not have a problem as opposed to I would have found seven. So the question is whether we have some way of being confident that we've actually seen a lot of those 42 possible interleavings. And the answer is no. So one problem with testing for race conditions is of course that the interleavings that you get can be very deterministic. If you run on a single core machine, it's amazing how deterministic the scheduler can be. So maybe your race condition will just never show. What we found, we've done two things. With airline code, we have a randomizing scheduler that we can use instead. And that provokes race conditions a lot more often. The other thing that we do is we just run on a multi core. The more cores you have, the easier the race conditions are to provoke. And in order to make race conditions appear, we just run each test a lot of times. And that has actually worked very well for us. Maybe partly because it's an airline, airline race conditions are maybe they're not quite as tough to provoke as race conditions, data races on shared data. Yeah. So we have interoperated with other languages. There's something we've used to interoperate with Java, which is fairly smooth. At Ericsson, this has been used to interoperate with C++ generated from Rational Rose RT. So we've made connections to a number of languages, but for the C connection, then we've put quite a lot of work into making it very smooth so that I can do it here in front of you. In the other cases, it's a bit less, it's a bit more ad hoc and there's a bit more work to be done in each case. So we should really put the work in and make a smooth connection to.NET and to Java, but we haven't done that yet. Oh, yeah. I know. So I meant to also show you this. If you'd like to find out more about this, about this kind of testing, then Haskell QuickCheck was the original version. There's a paper back in ICFP in 2000 that you can look at. Of course, we have our cubic commercial tools, so we're very happy to talk to people about this. But there are also many, many tools that have been inspired by the basic ideas. The ScalaCheck, there's FSCheck for F sharp, ClosureCheck, Test.Generate. I meant to add that to my slide. Darn. Which too was talking about before lunch. So there are lots of instances of the idea. It was, I guess you know you have a good idea when lots of people copied. And that's certainly what's happened. So the question is, what about intermittent failures and how do those interact with shrinking? So what shrinking does is we take the original random test and then there's a number of simpler tests shrinking candidates, simpler tests that we try. We run each one and if one of those fails, then we say, oh, now we've got a simpler test, let's start shrinking from here. But what if the test only fails intermittently? Then by sheer bad luck, all of the shrunk tests might pass. And what happens then is that shrinking stops and you end up with a so-called minimal test that is very big. So it's normally quite easy to recognize when that is happening because you see that shrinking did not work. So what we do is while we're shrinking, we can turn up the number of executions of each test. So if something shows, you know, once in a hundred runs, well, during the shrinking search, we'll run each test 500 times. It takes a little time, but compared to scratching ahead and trying to understand what the problem is otherwise, you know, it's much, much better unless just to let QuickCheck spend a few minutes shrinking. Sorry? So the Haskell QuickCheck is open source and I think these other tools are open source. The tool that I showed you, that's a commercial product. Oh, yes. So the question is how do we simulate node failures in the React case? We spend some time trying to make nodes go up and down or trying to reconfigure the kind of Erlang networking so that nodes would appear to go up and down. That turned out, A, to be very difficult. For a start, Erlang is very fault tolerant, so we would make a node go down or simulate a node going down and then it would come back up again. But secondly, we want to run thousands of tests and really taking nodes up and down is quite slow. So what we did at the time that I was working with the BASHA team on this was we took the React logic and we extracted it and tested it separately. And that meant that we could very easily just, you know, tell this piece of React logic, these are the nodes that you should use because the others are simulated to be down. And so in the end when we found the bugs, we were not testing the same code that was actually in React. After the time that I spent at BASHA, what the BASHA guys did next was refactor React so that the logic was separated out and could be tested separately. So now we are testing the real code in React. Well, I think that was also quite a nice lesson that running these tests demonstrated that a refactoring of the structure of React could make it a lot more testable. So the question is the example I showed you ran pretty fast, but how do the runtime scale when we get on to more realistic examples? So a lot of the React tests would, you'd also run several tests a second. So very often we're testing, you know, parts of larger systems and the tests do run fast. In the testing of the code from cars that I talked about, then we can run, you know, thousands of tests in half an hour. So of course things do get a little bit slower, but not so much as to be a problem for usability. question, would you agree to the model that you have to apply easily or simple in terms Okay, so the question is whether when you take real complex systems with complex business logic, yeah, whether the models get much, much larger and whether you end up, whether it's economic to model them. So yes, of course, they do get larger. Yesterday, I mentioned that when we were testing the Outisar code, which is specified by thousands of pages of PDFs, we ended up with 20,000 lines of model, which is still a lot smaller than the PDFs, much, much smaller. So that was manageable. One of the traps you can run into with this kind of testing is if your model begins to resemble the real code too much, because then, of course, there's a risk that you just replicate the same mistakes that you've made in the real code. If it's the same person writing the tests in the real code. So we always try to make sure that there's a difference in level of abstraction. And one of the things we've discovered is that you often don't need a very precise model to find a lot of bugs. That is, maybe you can, with a small amount of work, create a model that models your behavior approximately, and with 10 times as much work, model behavior more exactly. Now in that kind of case, it's often better just to make the partial model, because that will can still find an awful lot of bugs. I have an example from the first Ericsson product that we tested, which was a firewall base. It would connect phone calls. And you could add and subtract callers to a call. And we found a bug where you added two callers, subtracted one, added a third, subtracted that, added a fourth, and subtracted the fourth. So sequence of seven calls that made the system crash. Now actually, it was already wrong after the first subtract, subtract corrupted data structures. It wasn't found in normal testing because the most usual case, which was what people were testing, was add, add, subtract, subtract. And that second subtraction would then throw away the corrupt data before it had a chance to cause a problem. So if we had written a model that checked those data structures, we could have caught that problem after three operations, two adds and one subtract, or maybe after two, after one add and one subtract. Because we had a more partial model, it took seven operations to find the bug. But if you compare the time it would have taken us to make a more precise model, with the short time it took to find and debug this sequence of seven cases, it made a lot more sense to work with the partial model. And that happened surprisingly often that partial models can find the bugs you want to find anyway. Maybe we should take it offline because I realized that we're seven minutes into the break. I'm sorry about that. Thank you. Thank you.
 Okay, I guess it's about time I got started. My name is John Hughes. I have been doing  functional programming for many years. I've been a professor at Chalmers University in  Gothenburg for the last 20 and for the last seven years or so I've also been working at  my company, Cubic, on testing techniques. So I want to start off by asking who really,  really loves testing? Oh, more hands than usual, but still very few. So why is that? Why is  testing hard? Well, imagine that your testing code that has N features, let's say. And  you write maybe three or four tests per feature. That's okay. That's a linear amount of work.  No problem. But we all know you won't find all the bugs that way. We all know there are  bugs that only appear when you use two features in combination. So how many tests are you  going to have to write to test all pairs of features? Quadratically many. That's starting to  sound like quite a bit of work. And you know, not all bugs appear when you test two things  together. Sometimes you need combinations of three features. Oh, that's not good at all.  And that's just for sequential code. When you come to race conditions, by definition,  those are interactions between at least two features. And what's worse, they don't even  appear every time you run the test. Ah! Testing is awful. So what's the solution? Well, obviously,  if writing test is hard, don't write tests. Okay, I have a bit more time. Generate them.  And that's what this talk is about. I'm going to tell you about a tool called QuickCheck that  I began there. I couldn't class it on myself, invented a little more than, well, I guess  14 years ago now, for Haskell for purely functional code. And I've been working more and more  with this approach ever since starting the company in 2006. I'm going to show you the  version of the company markets because that's the one I've used most nowadays. And I've  been having lots of fun solving challenging testing problems in the field. So what does  it do? I'm going to show you a QuickCheck demo. If you were in my talk yesterday, you will  have seen a QuickCheck demo. Don't worry, this is a different one. So what we do is we have  some API under test, and we generate test cases, sequences of calls from that API, random  ones. And keep doing that until we find one that fails. When a test fails, it's very rarely  because of every API call in that sequence. It's usually just the few of them that interact  badly. So the next thing that we do is identify those few, filter them out, and create a minimal  failing example. And those minimal failing examples are typically really easy to debug.  There's a problem, though. If we're going to generate tests, when you write test cases  by hand, you're writing a particular test, and you can predict what the expected output  should be. When you're generating a test, you don't know, as you're writing the test  code, you don't know how you're going to invoke your system. So how can you tell whether  an arbitrary test has passed or failed? Well, you can't use expected results in general,  because you don't know what they'll be. You don't know what test you're going to run.  What we have to do instead is come up with some general properties of the code that should  be true whichever test we run, and then test those instead. So because of that, when we  do this test case generation, then we have to formulate properties of our code, and for  that reason, I call this property-based testing. Okay. So let me show you a demo. I am going  to test a little bit of C code. Here it is. So today I'm going to test a queue implemented  as a circular buffer. So I'm sure you all read C better than I do. Here is the representation  of the queue. There's the pointer to the area where we're going to store data. This is the  index where we're going to put things in, the index where we're going to take things  out, and the size of the buffer. Here's the code to create a new queue. We allocate space  for the data. We initialize the fields. We allocate the space for the struct. Initialize  the struct in memory, and then return the pointer. Okay. So here's how we put something  into the queue. We write it to the buffer at the input index, and we increment the input  index more to the size. Okay. What could be simpler? Here's how we take something out.  We read from the queue at the output index. We increment the output index modular to the  size. So this is really simple code. Here's how we tell how many items are in the queue.  We take the difference between the input and output indices modular to the size. Okay.  So this is all obviously correct. There's nothing up my sleeve. It's just an example  to show you how we can test this kind of code with QuickCheck. So in order to test it, I'm  going to be using the Erlang version of QuickCheck, which means I'm going to need to load this  code into the Erlang shell. So let me do that. And we've built something to make it very  easy to test C code from Erlang. So now that I've done that, I can call the C code and  create a queue of size 5. There we are. It returns a pointer to a struct queue. And then  I can put one into it, let's say. Let's put two into it. Whoops. Sorry about that. Let's  get something out of it. What? Okay. Thank you. Let's get an item from the queue. We  get one. Get another one. We get two. Uninitialized memory. Some more uninitialized memory. There's  the one again. There's the two. It's a circular buffer, right? So I just want to show you.  It really is the C code running there. There's nothing funny going on. We've compiled it  with GCC in this case. So it's running in the background there. Okay. So how are we going  to test this? Well, we model the behavior of this kind of code in Erlang as a kind of state  machine. So we generate test cases that are these sequences of API calls, but we also  model what state the code should be in at each point. And for every API call, we write  a state transition function that specifies how the model state changes. And then we write  post conditions to compare the actual results from the running C code with what the model  state says. And if all those post conditions are true, then the test passes. So in all  of the specification stuff is in Erlang, even though the code under test is in C. For example,  here's a test case for the queue. Put one, put two, do a get, put three, do another get.  How can I model the queue? Well, what about the list of elements that should be in it?  That's a very simple declarative model of how the queue should behave. And at the beginning,  it should be empty. Then after put one, it should contain just one. After put two, it  should contain one and two. After the get, it'll only have the two and so on. And then  when we check the post conditions, in this case, only get has an interesting post condition.  And it just says that the result that get returns should be the first element in the  list of elements in the queue. How do we write this code? Well, here's a couple of fragments.  Here are the state transition functions for put and get. I know most of you probably don't  read Erlang, but I hope this stuff will make sense anyway. What does the first line say?  It says, well, when you do a put, the next state, after you put x into the queue, takes  the, okay, I can't resist, it takes the old list of elements and adds x to the end. And  you end up in a state in which the list of elements has been replaced by this extension.  It's the extended list. Here's the one for get. We just take the tail of the list of  elements. So we discard the first one. It's very, very easy to write these functions.  Here are the post conditions of interest. The one for get says that the result that's  returned should be equal to the first element of the list of elements. The one for size  says the result we get should be the length of the list of elements. Once again, very,  very simple to model this stuff using, in particular, we use lists a lot because Erlang  has such rich operations on them. Okay. Let's run some tests. Where's my Erlang? Here it  is. Okay. So I will need to compile the code which I haven't shown you. Well, the code  I showed you fragments of, that's my specification. And having done so, I can use QuickCheck to  test the property that I've written in that code. And darn, it fails. So what happens  here is that I've generated a lot of random tests. Some of them passed. You can see there,  those dots represent passing tests. And then, blah, this random test failed. But before we  start analyzing it, then QuickCheck has actually done something we call shrinking. So it's searched  for a simpler test derived from the random one that also fails. And this is what we end  up with here. Right? So this shows us what happened. We called Q new to create a Q of  size one. We put zero into the Q. We put one into the Q. What does the Q contain? Zero  one, right? We call get. What should we get? Zero. What did we get? One. And this reason  here tells us that the post condition failed. We got one. We should have got zero. Okay.  So now I'd like you to put on your debugging hats and see if you can tell me what went  wrong. Yeah, the Q is only one element long. And I put two things into it. It's a circular  buffer. So the second thing overwrote the first. So of course it didn't work. But whose fault  is that? Right? So obviously my fault. But the model, yes. So in fact, you shouldn't  do this. And my test shouldn't do this either. Of course it's not going to work. And so  what we have to do is we have to exclude this test, which I can do now. If I go to my model  and here you can see the code fragments I showed you. Here is a precondition for get  that says, okay, it says the state pointer has must be defined. That is you have to have  a Q. You must have called new first. And the list of elements must not be empty. Of course  you can't do get if the list of elements is empty. But here's the precondition for put.  All it says is that you must have a Q pointer. Well, that's not enough, of course. You shouldn't  do put unless the length of the list of elements is less than the size of the Q. So let me  add that precondition. The effect of that is going to be if I recompile my spec, that  when I rerun the same test, so this doesn't generate random tests, this just reruns the  last one that failed. It fails for a different reason. It fails because the precondition  of put was not true. So it was a bad test. And now if I generate tests, they'll all pass.  Okay? That's cool. What you see here is some statistics on which operations we tested.  We tested a few more puts than gets because you can't do a get until you've done a put.  But we didn't test size at all. Why was that? That was because for simplicity, I commented  out the specification of size. So let me just comment that back in again. Okay? You can see  the precondition says you have to have a Q. This says how to generate a call of size,  or how to call it. And this says the postcondition that I showed you before. So let me recompile  that and now rerun my random tests. Darn! Another one failed. Okay, what happened here?  We created a Q of size one. That's fine. It returned this pointer. We put zero into it.  How many things are in the Q? One. I asked for the size. It returned zero. Okay. Whose  fault is this? Mine. Yes, of course. But is it the model? No. No, this is really a wrong  result. This is the code. We've put one thing into the Q, but the size function has returned  zero. How is that even possible? Let's look at the code. Okay, here's the code for the  size function. I've put one thing in. This returns zero. Size is one. How could it possibly  return zero? Oh, return something, module one. That's always zero. So when the Q is of size  one, this is always going to return zero. That can't be right, can it? So if you think  about it, even when I put one thing into the Q, I incremented my input pointer and it wrapped  around immediately. So my full Q looks just the same as an empty Q. And what's worse,  this isn't just a question of Q's of size one. If I had a Q of any size, when I fill  it full and the input pointer wraps around, both my input and output pointer are zero  again and it looks empty. So the problem here is that I can't distinguish a full Q from  an empty one. My representation isn't rich enough. Okay, how shall I fix it? Any ideas?  So I could put a flag in there, couldn't I? But that would be so ugly. Let me show you  a beautiful hack. When I am asked to create a Q of size n, do you know what I'm going  to do? I'm going to make one of size n plus one. Don't tell anybody. Now, as long as the  clients respect my preconditions, they can never see this bug because they can never  put n plus one things in the Q. And if they do, it's their fault. Cool. Okay, so let me  recompile the C code after making that fix and rerun the last failed test. Now it passes.  And just to make sure, let's run some random ones. Darn, another test failed. Okay, put  your debugging hats on. What happened here? I made a Q of size one. That's really two.  I put a zero into it. Now it's full, pretending to be size one. I did a get to take that  zero out. Now it's not full. I did another put. Okay, that's the second one. And then  I asked for the size and it returned. Well, I've done two puts and one get. How many things  are in the Q? One. Size returned minus one. How is that possible? Here's the size function.  What went wrong? Anybody care to debug that? Right. The input pointer, I put two things  in. The Q is really size two. The input pointer has wrapped around. The output pointer has  not. So we get zero minus one, module two. But just a minute, minus one, module two should  be plus one, right? Let's just check that. Darn. It's not. It's not an error length.  Neither in C. So the problem is that when this expression becomes negative, I get a  negative result out of size. So I have to make sure that this expression is never negative.  How shall I fix the code? Absolute value. Of course. Let's recompile the C code. Let's  rerun that test. Now it passes. Okay. So now I found the bug. I created a test that revealed  the bug. I've amended my code. Now the test passes. All my tests are green. I'm done,  right? Shall I run some random ones just for fun? Let's try that. It still fails. Look  what's happened here. Here I created a Q of size two now. That's one step bigger. So that's  an improvement. I've done three puts. That makes the input point to wrap around. One  get. Three puts, one get. How many things are in the queue? Two. What did size return?  One. And why was that? Because absolute value is the wrong thing to do here. Because it  changes the value modulo size. What I need to do is to make sure that this expression  is positive without changing the result of mod. And I can do that if I add Q size here.  Because the difference between input and output will never be greater than Q size. So this  will be always positive. And if I now test this, that previous test that failed now passes  and so do all of the others. And I could run any number of tests now. They will all pass.  So it's surprisingly how often we see the effects of what I just did in real code. Where  we find some code, it's complicated. We can't understand why. And obviously what's happened  is that somebody had a bug. They had a bug report and a test case. And they made the  code work in that case without really understanding what the problem was. So all they've managed  to do is make the code more complicated. They haven't managed to make it work.  Okay. That was my demo. And the lessons I want to draw out from this are that first  of all, the same properties can find many different bugs. And also those minimal failing  tests make diagnosing things very easy.  You know that if you delete any one step, then the test would pass. It is possible that  if you deleted at the same time, you know, five steps from the middle of 12, and you  picked just the right five, that you might be able to shrink it further. So we don't,  we can't explore every possible simpler test. That would take far too long. So you have  a weak guarantee. But usually it really is the minimal case.  So we think of the shrinking process that has produced these minimal failures as extracting  the signal from the noise of random tests. You get a lot of noise in random tests. And  if you try and debug randomly generated stuff, it's impossible. But when you extract the  signal, it's quite easy.  Yesterday I talked about a big project that we've done in the last couple of years when  we tested C code going into cars. Protocol stacks and other components that are part  of the AutoSAR standard. Thousands of pages of PDFs we converted into specifications of  the kind I've shown you. We have code from six different vendors to test. And we found  hundreds of issues in the code. And of those, all of this code was supposed to implement  the same standard. We found more than a hundred bugs in the standard.  So that was a really, that's a really exciting project. But I talked about it yesterday.  So I'm not going to say any more about that today. What I do want to do is show you a  couple of other examples of database testing that we've done. And first of all, let me  kick off with React. React is a no SQL distributed key value store. It's very scalable and fault  tolerant and lots of good stuff. But it's only eventually consistent. So what does that mean?  It means it's very hard to test. Because what does it even mean? I mean, suppose you do  something with the database and then the result at the end of the test is not consistent.  Well, it's only supposed to be consistent eventually. Maybe it's not eventually yet.  So because of the nature of the beast, it's fundamentally quite hard to test. And so a  year and a bit ago, then I did some work with the bash guys on trying to develop properties  for testing React. We deliberately kept our tests as simple as we possibly could. So we  realized that we would start off by testing the database. It's a key value store with  only one key and one value. Maybe that sounds rather pathetic. But look at it this way.  If we don't understand what the database does with one key, how can we possibly understand  what it does with many? So we were deliberately taking a very simple model and then we would  complicate the model only when we were really forced to by a failed test. I think that was  a really good strategy for developing a good model of this complex software.  Okay, so let me explain the React API. It has put and get operations. I'm not going to show  the keys because there is only one. So you might put zero, one client put zero, another  client does a get and on the same key and that client will see zero. And then maybe  that second client might put one and the first client might do a get and will see one. I  think we understand what React is supposed to do now, right?  So here's an example that QuickCheck concocted. You put zero, it's all one client, you put  zero, you put one, you put zero again and you do get. What will you see? One. Huh. That  wasn't really what our simplest model was expecting. Now actually I'm pulling the wool  over your eyes a little bit here because the API doesn't let you put a key and a value  into the database. You put a React object into the database that contains a key and  a value. And that means there's two different ways that you can do a put. You can create  a new React object and put that in or you can take a React object you've already got,  for example, because you just put it in the database and modify it. Modify the value and  put the modified React object in. And in this test case, the first and last puts were putting  a new value, so creating a new object, whereas the middle one was updating the first one.  So we generated this test and I said, look, it shouldn't do this. And my friends at Bashow  said, what are you thinking of? You shouldn't do that. This isn't a new key anymore. Why  are you calling put new after you know the thing is in the database? So don't do it.  So why didn't it work? Because all of these values are data or timed, timestamped with  vector clocks. And at the time, React kept track of how many times each client had manipulated  the value of that key. So if you think about it, we do a put new, then we do a put update.  When we put the one, the one has been touched twice by this client, but the last zero has  been touched only once because it's a new object. Touch twice is more than touched once.  Therefore the one is newer than the zero. Therefore React discarded the zero.  Okay. Well, so my friends at Bashow insisted this was the right behavior. But after we  discussed it, they said, you know, there's this design rule for how you use the API that  once you, for example, read an object from the database, you mustn't create a new object  with the same key. You must modify it and write it back. So you have to be careful using  the API. And then they were started thinking, I wonder if all our users know that. And not  even they had thought about the fact that if you didn't follow the design rule, you could  lose data. So it was quite good to at least elucidate that design rule.  So that was our first step. So now what are we going to do, right? What are we going to  do about this test that fails? Should we put vector clocks into the model? No, of course  not. The model is supposed to be simple. It's supposed to be something that the user  can use to understand how the database should behave. It shouldn't talk about vector clocks  in the implementation to figure out what's going to happen. So the only other thing that  we could do was put into the model, you shouldn't do that. And we did that. We made the model  record each client's last view of the value. That is, every time we did a get, we would  record what the client saw. And then we added a precondition that said that if a client  has a view of the value, then it must update that view when it does a put. So you're not  allowed to do a put new. And then we generate tests that respect that precondition and they  all pass. So that was good. Okay. So let me tell you more about React.  React supports, it's a very fault tolerant database, so it supports redundancy. When  you do a put, it doesn't just go to one node, it by default goes to three. And if one of  those nodes goes down and you do the put, then it will pick another node somewhere and  store the value there instead. So at this point, you can see that there is a down node  that has a stale value on it. Now, React remembers that that fourth value is in the wrong place.  And it remembers where it should be sent back to. And when the node that was disconnected  comes back, then there's a process called handoff that returns the value to the correct  place. But handoff is not immediate. So there is a period when a node can come back and  contain stale values. That's why it's eventually consistent.  The other thing I have to explain to you is conflicts in React. So what happens if two  clients put different values at the same time to a key? Well, you might say, ah, it looks  as though the one arrived a little later will say that one wins. But no. Instead, React  saves both values. It's called a conflict. And the next client to do a get will see them  both. And the idea is that the client will then resolve the conflict by putting a single  value back again. And future clients will then see the resolve value. So why do it this  way? The idea comes from the original Dynamo database that Amazon developed. And the model  here was the Amazon shopping basket. So suppose you're shopping on Amazon on your phone and  your laptop at the same time. And they may be connected to different networks, going  to different servers in maybe different clusters within Amazon. So what if you put one book  in your shopping basket on the phone and another book in your shopping basket on the laptop?  But the servers can't talk to each other. Now you've got a conflicted value for your  shopping basket. But when you go to check out which value do you want to see? Which  books do you want to see in your shopping basket? Obviously both, right? At least that's  what Amazon wants you to see. So the conflict resolution there is just to gather everything  up and smush them all together. But there are lots of examples where that's application  dependent conflict resolution is useful. So we wanted to test React for eventual consistency.  What we did was that means we were testing its behavior when nodes would become unavailable.  So we generated random sequences of React calls, but also for each call, a random collection  of nodes that would fail during that call. And then we tested to see whether at the end  of execution we saw the correct values. Now when a test fails, normally here it's because  of only a few of the calls, but also because of only a few of the node failures. And so  we would shrink down these tests to get a minimal failing test with a minimal sequence  of calls and a minimal set of node failures that you need to make the test fail. Let me  show you the case we found. Here we are, two clients. This one puts a zero and then gets  it back again. Now this client gets the zero and puts a one back. This client puts a two.  Now those two puts are in conflict because the client on the left has not seen the one  that the client on the right put. So when we do a get, we should see both values. What  did we see? Only the one. Now why did that happen? To explain it, I have to show you  the node failures. So let's bring in the three nodes now. I'm going to consider a cluster  with only three nodes. When we did the first put, two of the nodes were down. Or maybe  there was a network partition that meant the message didn't reach those two. When we did  the first get, those two nodes answered and the other one was down. So the first client  saw, oh, the value is not there anymore. That might seem strange if you put a value in the  database and then you do a get and it's not there, but somebody else could have deleted  it, of course. Now for the other operations, all three nodes respond. So the second client  does a get and sees the zero because one of the nodes has it. The second client does a  put, all the nodes hold one. The first client does a put now. Now think back to the first  bug I showed you. That client is doing a put of a value that has only been touched by the  client on the left because the last time the client searched for this key, it was not found.  So that's a new React object. The one, though, that's been touched by both the client on  the left and the client on the right. So the one is newer and the two can be discarded.  That's why React just returned the one. So it's the same bug. It's the bug. You shouldn't  do that. But who's doing it now? It's not me, the ignorant programmer. It's React itself  doing it in response to node failures. So shock horror. React is not eventually consistent.  Well, the truth, of course, is that it was not eventually consistent at this time. So  what have we found? We found an extreme failure scenario. I want to emphasize that. We found  a failure that arises when you have two different network partitions in quick succession with  no time to heal the database in between. But it had bad results. It led to loss of data,  a failure of eventual consistency, which is an important selling point for React. But  it also provided a test framework that was immensely helpful when the redesign that fixed  this problem was performed. Because for every attempt at a redesign, it was possible to  run it through the same generated tests and in the end, to be pretty darn sure that the  problem was fixed. So I just want to ask a meta question now. We found a lot of bugs  in React. Does that mean React is buggy? Once I gave a talk about this material and in the  discussion at the end, then one of the people in the audience said, well, I was going to  use React, but I'm not sure I will now that I know it's so buggy. I just want to ask if  you would rather use a database that has not been tested in this kind of way. So we've  done a lot of work with Bashow and I feel React must be one of, if not the best tested  database around as a result of that. So just because you managed to find and fix bugs,  it doesn't mean that the product is then buggy. Okay, so that was a nice example of using  React. I want to tell you one more story. It's about another database. This story starts  with a message to the Adlang mailing list in 2007. We know there's a lurking bug somewhere  in the debt's code. We've got bad objects and premise your end of file every other  month the last year. We haven't been able to track the bug down because the file is  repaired automatically next time it's opened. This was posted by a man called tupiternqvist  from Klarna. Okay, so I'm sure we all feel tupiternqvist pain. But what's the context?  Well Klarna develops an application that provides invoicing services for web shops. Maybe that  doesn't sound terribly exciting, but since they're being founded in the mid-2000s, they've  grown to more than 700 people. So it's a tremendously successful start-up. They're serving  seven European countries now, and they built their entire system in Adlang. They stored  their data in the database that comes together with the Adlang distribution, which is called  Menezia, and that gives you transactions and replication and lots of good stuff, but it  needs a back end to store its data. The disk back end is called debts. It provides tuple  storage in files. Debt is the component that tupiternqvist talking about. Debt is the  component that's failing every month or two. And when I heard about this, I thought failures  every month or two, that sounds like a race condition. Let's see if we can track them  down. Okay, so I'm going to show you how we test for race conditions with generated tests.  And to do that, I'm going to go from the sublime to the ridiculous. Imagine testing  these. So we have a lot of these in Sweden. Do we have them in Norway, too? You have them  at a delicatessen counter, for example. So you take a ticket, and then you know when  it's your turn to be served. Suppose I wanted to model that in Adlang. I'd need an operation  to take a ticket, and every now and then the role of tickets runs out, so I'd need an operation  to reset the dispenser back to zero. And now I could write a standard unit test for this  quite easily. This is how it might appear in Adlang, where I perform a sequence of calls  and I match each result against the expected value. And, well, you can see how I expect  the thing to behave. But wait a minute. What is the point of a ticket dispenser? Its whole  purpose is to regulate the flow of a lot of concurrent customers to one delicatessen  counter, right? So what am I doing running sequential tests? Well, okay, it's good to  test the sequential behavior, but this misses out on an important part of the dispenser's  behavior that it should work when it's used in parallel. Okay. So if I wanted to test  the dispenser, I can test it by modeling with the state machine in just the same way that  we've seen before. If I've got a test case like this, then I can model the dispenser's  state just by a single integer. It's really easy. And the state transition is you do an  increment when there's a take, you set it to zero when there's a reset. And then the  post condition will just check that the value that take returns is one more than the state  when it's called. So that's really easy. But what I would like to do is to run tests like  this instead. So this is supposed to represent a parallel test where first of all, I reset  the dispenser and then one customer comes along and takes two tickets for some reason  at the same time as another customer is taking a ticket. Okay. So what might happen here?  Well, the customer on the left might get tickets one and two. The customer on the right might  get ticket three. But that's not the only thing that can happen. The customer on the  right might get ticket two and the one on the left might get one and three. That's also  correct, isn't it? But this should not happen. If both customers get ticket number one, then  something has gone wrong. So if you think about it, there are three possible correct  outcomes for this test. So what are the expected results going to be? Well, of course, in this  case you could just record the three tickets and then compare against the three possibilities  and see have you got one of those correct outcomes. But this is a very tiny test. I  don't want to run tests like this. I want to run tests like this. How many correct outcomes  are there of this test? Can you figure it out? Luckily I've done it for you. Forty-two,  of course. So now think about enumerating the forty-two possible correct outcomes. Nobody  in their right minds would do that. And anybody who tried would get at least one of them wrong.  So you fundamentally can't do that. You can't figure out the expected results for a parallel  test. The only thing you can do is try and detect whether a test has passed or failed  with some kind of property. So race condition testing, I think, is a killer app for property  based testing. Okay. So let's go back to the parallel test that I drew before. I've turned  it on its side here and asked ourselves, how do I know that this test succeeded? Well,  I know because there is some order in which I could have performed those calls where the  results would match the model. That is, if I interleave the calls and results like this,  then they become consistent with the model. So that's what we do. We generate parallel  tests and then we ask, is there any interleaving that can explain what happened? If so, we  say the test passed. If not, it must have failed. I will just do one more quick demo  here. I have my dispenser code. Just compile it. And I'll run, first of all, some sequential  tests. So those sequential tests demonstrate that my implementation and my model match.  And now if I run parallel tests, I'm using exactly the same model so it's a very slight  difference to run parallel tests instead. Well, there's a race condition. And if you  look at what happened, you can see we did two things in parallel. Two calls of take  ticket, they both returned one. Now, the original random test was more complex. It's up here.  But after shrinking, we get down to this minimal case that provokes the race. And I just want  to run this test a number of times so I'll get different random tests that fail. But  see where I end up. After shrinking, it's always the same minimal example. So that means  that tells us that this example probably really is the minimal one. And if I go back to my  presentation, that's the failing test. Here's the code I wrote for taking a ticket. So it's  reading a shared global variable and then writing M plus one. It's a critical section.  Where's the synchronization? There isn't any. So of course there's a race condition here.  And the point is not how stupid code I wrote. The point is that given this kind of race  condition, we can find it very quickly and reliably by this method. So let's go back  and talk about debts instead. Debt provides a tuple store. It stores Airdlang tuples which  have curly brackets around them. And the first component is the key. And it's got an API  with a kind of operation you would expect. You know, you can insert a list of tuples  into the table. You can delete all the tuples with a given key. Insert new is like insert  except that if any of the keys is already present, then it's a no op. And it's atomic.  So that's kind of nice. And there's some more. Nothing that will surprise you. So now I have  to model the behavior of debts and it's really simple to do that. It's almost enough just  to have a list of the tuples that I think should be in the table. So that's what I did.  I wrote a spec in the same style that you've seen. It was less than 100 lines of code for  the core of the debt's API. And in comparison, the implementation of debts is more than 6,000  lines of code in four different modules. Why? Because it's keeping hash tables on the disk  and of course it's complicated stuff. But the intended behavior is quite simple. So I wrote  my spec. I ran my sequential tests. They all passed. And I started running parallel ones.  And what do you know? As soon as I did that, I found a race condition. So what's happening  here? Well, in a prefix, I'm opening the file, surprise, surprise. And then I'm doing two  things in parallel. I'm inserting an empty list of tuples. I'm just going to get my pointer  back here. I'm inserting an empty list of tuples. That's a no op and it returned okay.  And I'm using insert new to insert another empty list of tuples. That's also a no op.  And that returned okay too. And QuickCheck says there's no possible interleaving of these  calls that can explain this result. Okay, wait a minute. But they both returned okay.  What's wrong? Sometimes there's just no alternative. You have to read the manual. Here's what  it says about insert new. Look at the result type. Even in Erdlang, a bool is either true  or false. It's not okay. And in thousands of sequential tests, insert new returned true  or false every time. As soon as I ran it in parallel, it returned okay. Where did that  come from? Okay, so I went on, ran some more tests. I found this one. In the prefix, we  opened the file. And now in parallel, we do two insertions. One using insert. We insert  a tuple 00. And at the same time, we do an insert new 00. So the insert new maybe could  succeed or maybe could fail depending on which one of them goes first. But it shouldn't time  out. And we shouldn't see a message. Error report, bug was found. So that seemed to be  pretty conclusive that I'd come across another bug. So at this point, I decided that insert  new just doesn't work. And I excluded it from my tests. And I found this one. Okay. So here  in the prefix, we open the file. And now in parallel, one process opens the file again.  You might think that seems odd. But it's not. This database is designed to be used in Erlang  systems which are very highly concurrent. Many processes may use the table at the same  time. Each of them must make sure it's open. So it's okay for one process to reopen the  database while another one is using it. The other process is inserting a tuple into the  table and then getting the entire contents and where's that 00? I just put it in. And  it's gone. So I found this bug in several forms. That if one process was reopening the  table, another sequential process could see an inconsistent view of the database contents  where its own operations had no effect. So I sent these bugs to Hassel Bolynder at Ericsson,  the man who was responsible for the code. And he said, oh, thank you very much. Here's  a new version. He sent me a fixed version the next day. He said, that's great. But I  don't think these are the bugs that Klarna are experiencing because the symptoms are  not the same. At Klarna, the file is being corrupted. Okay. File corruption. I added  one line to my test that said, after we've run the parallel operations, just check that  the file is not corrupt. There was an easy way to do that. And I started running more  tests. This time I had to run a few thousand. And then I found this. Look at this. In the  prefix, we open the file. We close it. We open it again. Then we do three things in  parallel, a lookup of something that's not there, and two insertions of the same, that  same tuple, in fact. All of the results are consistent with my model. But when I check  the file for corruption, what do you know? I got to prevert your end of file. So I want  to emphasize, this is the smallest example that can provoke this bug. I looked at it  and I thought, open, close, open, you've got to be kidding. It must fail if I just open  the file and then do the three things in parallel. But no, I ran tens of thousands of tests.  They all passed. Nowadays I know why. The first open creates the file. Then we close  it. The second open opens an existing file. It leaves the code in a slightly different  state and that difference is critical to this bug.  So I really love this example because can you imagine anybody writing this test in a  test suite? Why would you test this collection of six calls for goodness sake? So anyway,  I was very happy to find this. I sent it off to Hassek. I got a correct version of the  code back next day and then I was giving a talk at a conference in Orhooves. I was supposed  to talk about something else but I thought this is such a great story. I have to tell  it. Only I hadn't saved the output from running QuickCheck. So I had to sit in my hotel room  making new slides and I rerun my tests and copied and pasted the output onto my slides  and as I was doing that, guess what? I found this one.  Okay in the prefix, we open the file and we insert a tuple and then in parallel, one process  is just reopening the file again. The other one is looking up something that's not there  and deleting the thing that is. Once again, all the results, all the return values are  consistent with the model but when I checked for corruption, I got a bad object. I want  to remind you of the mailing list message. We know there's a lurking bug somewhere. We've  got bad objects and premedure in the file every other month for last year. I sent that  example off to Hasse as well. Next day I got a fixed version. That fixed version has been  in service at Glarner for more than a year now. There has been, well, before it was installed,  the problem got worse. It was happening once a week and every time this happened, the main  server went down. Its database was corrupt. All the data could be restored from a replica  but it took hours to bring that machine back up again. Since the new code has been installed,  they've had bad object once when accessing a file that had not been written since before  the new code went into service. So it looks as though we really did nail those bugs.  So a lot of work had gone into searching for these bugs beforehand, of course. I've talked  to the people who did it. The developer spent six weeks at Glarner trying to figure out  what on earth was going wrong. At the end of that time, they thought it seems to happen  when the file is about one gigabyte. Maybe it's something to do with rehashing. Afterwards,  we could reproduce the failures with a database with either zero or one records. It took either  five or six calls to reproduce each of those serious bugs. And it took less than one day  to fix the problem given that minimal example. And I think this really shows two things.  One, the enormous value of minimal failing cases and secondly, how hopeless it is to  try and debug this kind of race condition from failures in production. Where billions  of irrelevant things have happened as well as the five or six calls that are actually  responsible for the problem. Yeah. So I did it now and then over a period of a few days  if I had an hour spare, I would spend a little time on it. But probably less than a day's  work in total. It was only a hundred lines of code. So, yeah. I will just skip over this  little bit I think because I've now said most of what I wanted to say. So my point is property  based testing like this, you find more bugs because you can do better testing and it's  less effort. Don't write tests, generate them. That's my message. And I'm happy to take  questions. So you had that example that had 42 different possible legal interleavings.  Do you have a way of keeping track and verifying that you've covered some fraction of the legal  ones? Without feel more confident if I hit all 42 of those and not have a problem as  opposed to I would have found seven. So the question is whether we have some way of being  confident that we've actually seen a lot of those 42 possible interleavings. And the answer  is no. So one problem with testing for race conditions is of course that the interleavings  that you get can be very deterministic. If you run on a single core machine, it's amazing  how deterministic the scheduler can be. So maybe your race condition will just never  show. What we found, we've done two things. With airline code, we have a randomizing scheduler  that we can use instead. And that provokes race conditions a lot more often. The other  thing that we do is we just run on a multi core. The more cores you have, the easier  the race conditions are to provoke. And in order to make race conditions appear, we just  run each test a lot of times. And that has actually worked very well for us. Maybe partly  because it's an airline, airline race conditions are maybe they're not quite as tough to provoke  as race conditions, data races on shared data. Yeah.  So we have interoperated with other languages. There's something we've used to interoperate  with Java, which is fairly smooth. At Ericsson, this has been used to interoperate with C++  generated from Rational Rose RT. So we've made connections to a number of languages,  but for the C connection, then we've put quite a lot of work into making it very smooth so  that I can do it here in front of you. In the other cases, it's a bit less, it's a bit  more ad hoc and there's a bit more work to be done in each case. So we should really  put the work in and make a smooth connection to.NET and to Java, but we haven't done that  yet. Oh, yeah. I know. So I meant to also show you this. If you'd like to find out more  about this, about this kind of testing, then Haskell QuickCheck was the original version.  There's a paper back in ICFP in 2000 that you can look at. Of course, we have our cubic  commercial tools, so we're very happy to talk to people about this. But there are also many,  many tools that have been inspired by the basic ideas. The ScalaCheck, there's FSCheck  for F sharp, ClosureCheck, Test.Generate. I meant to add that to my slide. Darn. Which  too was talking about before lunch. So there are lots of instances of the idea. It was,  I guess you know you have a good idea when lots of people copied. And that's certainly  what's happened. So the question is, what about intermittent failures and how do those  interact with shrinking? So what shrinking does is we take the original random test and  then there's a number of simpler tests shrinking candidates, simpler tests that we try. We  run each one and if one of those fails, then we say, oh, now we've got a simpler test,  let's start shrinking from here. But what if the test only fails intermittently? Then  by sheer bad luck, all of the shrunk tests might pass. And what happens then is that  shrinking stops and you end up with a so-called minimal test that is very big. So it's normally  quite easy to recognize when that is happening because you see that shrinking did not work.  So what we do is while we're shrinking, we can turn up the number of executions of each  test. So if something shows, you know, once in a hundred runs, well, during the shrinking  search, we'll run each test 500 times. It takes a little time, but compared to scratching  ahead and trying to understand what the problem is otherwise, you know, it's much, much better  unless just to let QuickCheck spend a few minutes shrinking. Sorry? So the Haskell QuickCheck  is open source and I think these other tools are open source. The tool that I showed you,  that's a commercial product. Oh, yes. So the question is how do we simulate node failures  in the React case? We spend some time trying to make nodes go up and down or trying to  reconfigure the kind of Erlang networking so that nodes would appear to go up and down.  That turned out, A, to be very difficult. For a start, Erlang is very fault tolerant,  so we would make a node go down or simulate a node going down and then it would come back  up again. But secondly, we want to run thousands of tests and really taking nodes up and down  is quite slow. So what we did at the time that I was working with the BASHA team on  this was we took the React logic and we extracted it and tested it separately. And that meant  that we could very easily just, you know, tell this piece of React logic, these are  the nodes that you should use because the others are simulated to be down. And so in  the end when we found the bugs, we were not testing the same code that was actually in  React. After the time that I spent at BASHA, what the BASHA guys did next was refactor  React so that the logic was separated out and could be tested separately. So now we  are testing the real code in React. Well, I think that was also quite a nice lesson  that running these tests demonstrated that a refactoring of the structure of React could  make it a lot more testable. So the question is the example I showed you ran pretty fast,  but how do the runtime scale when we get on to more realistic examples? So a lot of the  React tests would, you'd also run several tests a second. So very often we're testing,  you know, parts of larger systems and the tests do run fast. In the testing of the  code from cars that I talked about, then we can run, you know, thousands of tests in  half an hour. So of course things do get a little bit slower, but not so much as to  be a problem for usability.  question, would you agree to the model that you have to apply easily or simple in terms  Okay, so the question is whether when you take real complex systems with complex business  logic, yeah, whether the models get much, much larger and whether you end up, whether  it's economic to model them.  So yes, of course, they do get larger.  Yesterday, I mentioned that when we were testing the Outisar code, which is specified by thousands  of pages of PDFs, we ended up with 20,000 lines of model, which is still a lot smaller  than the PDFs, much, much smaller.  So that was manageable.  One of the traps you can run into with this kind of testing is if your model begins to  resemble the real code too much, because then, of course, there's a risk that you just replicate  the same mistakes that you've made in the real code.  If it's the same person writing the tests in the real code.  So we always try to make sure that there's a difference in level of abstraction.  And one of the things we've discovered is that you often don't need a very precise model  to find a lot of bugs.  That is, maybe you can, with a small amount of work, create a model that models your behavior  approximately, and with 10 times as much work, model behavior more exactly.  Now in that kind of case, it's often better just to make the partial model, because that  will can still find an awful lot of bugs.  I have an example from the first Ericsson product that we tested, which was a firewall  base.  It would connect phone calls.  And you could add and subtract callers to a call.  And we found a bug where you added two callers, subtracted one, added a third, subtracted  that, added a fourth, and subtracted the fourth.  So sequence of seven calls that made the system crash.  Now actually, it was already wrong after the first subtract, subtract corrupted data structures.  It wasn't found in normal testing because the most usual case, which was what people  were testing, was add, add, subtract, subtract.  And that second subtraction would then throw away the corrupt data before it had a chance  to cause a problem.  So if we had written a model that checked those data structures, we could have caught  that problem after three operations, two adds and one subtract, or maybe after two, after  one add and one subtract.  Because we had a more partial model, it took seven operations to find the bug.  But if you compare the time it would have taken us to make a more precise model, with  the short time it took to find and debug this sequence of seven cases, it made a lot more  sense to work with the partial model.  And that happened surprisingly often that partial models can find the bugs you want  to find anyway.  Maybe we should take it offline because I realized that we're seven minutes into the  break.  I'm sorry about that.  Thank you.  Thank you.
John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_0_59.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_60_107.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_108_7055.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_7056_7127.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_7128_7187.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_7188_9395.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_9396_9455.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_9456_9683.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_9684_9731.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_9732_11363.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_11364_15539.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_15540_15587.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_15588_15635.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_15636_16523.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_16524_16583.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_16584_16763.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_16764_17075.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_17076_17135.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_17136_17639.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_17640_19043.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_19044_19259.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_19260_20279.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_20280_21251.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_21252_26195.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_26196_27647.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_27648_27695.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_27696_27743.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_27744_27791.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_27792_27839.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_27840_27899.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_27900_28223.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_28224_28607.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_28608_29147.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_29148_31199.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_31200_31343.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_31344_31403.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_31404_32279.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_32280_46751.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_46752_48311.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_48312_53183.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_53184_54959.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_54960_58199.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_58200_58463.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_58464_64835.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_64836_64919.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_64920_65279.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_65280_66239.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_66240_66287.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_66288_66539.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_66540_66599.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_66600_67151.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_67152_69479.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_69480_69995.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_69996_76283.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_76284_78383.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_78384_78947.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_78948_79043.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_79044_100367.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_100368_100427.png John_Hughes_-_Race_Conditions__Distribution__Interactions--Testing_the_Hard_Stuff_and_Staying_Sane-6_100428_100465.png
Okay, I guess it's about time I got started. My name is John Hughes. I have been doing functional programming for many years. I've been a professor at Chalmers University in Gothenburg for the last 20 and for the last seven years or so I've also been working at my company, Cubic, on testing techniques. So I want to start off by asking who really, really loves testing? Oh, more hands than usual, but still very few. So why is that? Why is testing hard? Well, imagine that your testing code that has N features, let's say. And you write maybe three or four tests per feature. That's okay. That's a linear amount of work. No problem. But we all know you won't find all the bugs that way. We all know there are bugs that only appear when you use two features in combination. So how many tests are you going to have to write to test all pairs of features? Quadratically many. That's starting to sound like quite a bit of work. And you know, not all bugs appear when you test two things together. Sometimes you need combinations of three features. Oh, that's not good at all. And that's just for sequential code. When you come to race conditions, by definition, those are interactions between at least two features. And what's worse, they don't even appear every time you run the test. Ah! Testing is awful. So what's the solution? Well, obviously, if writing test is hard, don't write tests. Okay, I have a bit more time. Generate them. And that's what this talk is about. I'm going to tell you about a tool called QuickCheck that I began there. I couldn't class it on myself, invented a little more than, well, I guess 14 years ago now, for Haskell for purely functional code. And I've been working more and more with this approach ever since starting the company in 2006. I'm going to show you the version of the company markets because that's the one I've used most nowadays. And I've been having lots of fun solving challenging testing problems in the field. So what does it do? I'm going to show you a QuickCheck demo. If you were in my talk yesterday, you will have seen a QuickCheck demo. Don't worry, this is a different one. So what we do is we have some API under test, and we generate test cases, sequences of calls from that API, random ones. And keep doing that until we find one that fails. When a test fails, it's very rarely because of every API call in that sequence. It's usually just the few of them that interact badly. So the next thing that we do is identify those few, filter them out, and create a minimal failing example. And those minimal failing examples are typically really easy to debug. There's a problem, though. If we're going to generate tests, when you write test cases by hand, you're writing a particular test, and you can predict what the expected output should be. When you're generating a test, you don't know, as you're writing the test code, you don't know how you're going to invoke your system. So how can you tell whether an arbitrary test has passed or failed? Well, you can't use expected results in general, because you don't know what they'll be. You don't know what test you're going to run. What we have to do instead is come up with some general properties of the code that should be true whichever test we run, and then test those instead. So because of that, when we do this test case generation, then we have to formulate properties of our code, and for that reason, I call this property-based testing. Okay. So let me show you a demo. I am going to test a little bit of C code. Here it is. So today I'm going to test a queue implemented as a circular buffer. So I'm sure you all read C better than I do. Here is the representation of the queue. There's the pointer to the area where we're going to store data. This is the index where we're going to put things in, the index where we're going to take things out, and the size of the buffer. Here's the code to create a new queue. We allocate space for the data. We initialize the fields. We allocate the space for the struct. Initialize the struct in memory, and then return the pointer. Okay. So here's how we put something into the queue. We write it to the buffer at the input index, and we increment the input index more to the size. Okay. What could be simpler? Here's how we take something out. We read from the queue at the output index. We increment the output index modular to the size. So this is really simple code. Here's how we tell how many items are in the queue. We take the difference between the input and output indices modular to the size. Okay. So this is all obviously correct. There's nothing up my sleeve. It's just an example to show you how we can test this kind of code with QuickCheck. So in order to test it, I'm going to be using the Erlang version of QuickCheck, which means I'm going to need to load this code into the Erlang shell. So let me do that. And we've built something to make it very easy to test C code from Erlang. So now that I've done that, I can call the C code and create a queue of size 5. There we are. It returns a pointer to a struct queue. And then I can put one into it, let's say. Let's put two into it. Whoops. Sorry about that. Let's get something out of it. What? Okay. Thank you. Let's get an item from the queue. We get one. Get another one. We get two. Uninitialized memory. Some more uninitialized memory. There's the one again. There's the two. It's a circular buffer, right? So I just want to show you. It really is the C code running there. There's nothing funny going on. We've compiled it with GCC in this case. So it's running in the background there. Okay. So how are we going to test this? Well, we model the behavior of this kind of code in Erlang as a kind of state machine. So we generate test cases that are these sequences of API calls, but we also model what state the code should be in at each point. And for every API call, we write a state transition function that specifies how the model state changes. And then we write post conditions to compare the actual results from the running C code with what the model state says. And if all those post conditions are true, then the test passes. So in all of the specification stuff is in Erlang, even though the code under test is in C. For example, here's a test case for the queue. Put one, put two, do a get, put three, do another get. How can I model the queue? Well, what about the list of elements that should be in it? That's a very simple declarative model of how the queue should behave. And at the beginning, it should be empty. Then after put one, it should contain just one. After put two, it should contain one and two. After the get, it'll only have the two and so on. And then when we check the post conditions, in this case, only get has an interesting post condition. And it just says that the result that get returns should be the first element in the list of elements in the queue. How do we write this code? Well, here's a couple of fragments. Here are the state transition functions for put and get. I know most of you probably don't read Erlang, but I hope this stuff will make sense anyway. What does the first line say? It says, well, when you do a put, the next state, after you put x into the queue, takes the, okay, I can't resist, it takes the old list of elements and adds x to the end. And you end up in a state in which the list of elements has been replaced by this extension. It's the extended list. Here's the one for get. We just take the tail of the list of elements. So we discard the first one. It's very, very easy to write these functions. Here are the post conditions of interest. The one for get says that the result that's returned should be equal to the first element of the list of elements. The one for size says the result we get should be the length of the list of elements. Once again, very, very simple to model this stuff using, in particular, we use lists a lot because Erlang has such rich operations on them. Okay. Let's run some tests. Where's my Erlang? Here it is. Okay. So I will need to compile the code which I haven't shown you. Well, the code I showed you fragments of, that's my specification. And having done so, I can use QuickCheck to test the property that I've written in that code. And darn, it fails. So what happens here is that I've generated a lot of random tests. Some of them passed. You can see there, those dots represent passing tests. And then, blah, this random test failed. But before we start analyzing it, then QuickCheck has actually done something we call shrinking. So it's searched for a simpler test derived from the random one that also fails. And this is what we end up with here. Right? So this shows us what happened. We called Q new to create a Q of size one. We put zero into the Q. We put one into the Q. What does the Q contain? Zero one, right? We call get. What should we get? Zero. What did we get? One. And this reason here tells us that the post condition failed. We got one. We should have got zero. Okay. So now I'd like you to put on your debugging hats and see if you can tell me what went wrong. Yeah, the Q is only one element long. And I put two things into it. It's a circular buffer. So the second thing overwrote the first. So of course it didn't work. But whose fault is that? Right? So obviously my fault. But the model, yes. So in fact, you shouldn't do this. And my test shouldn't do this either. Of course it's not going to work. And so what we have to do is we have to exclude this test, which I can do now. If I go to my model and here you can see the code fragments I showed you. Here is a precondition for get that says, okay, it says the state pointer has must be defined. That is you have to have a Q. You must have called new first. And the list of elements must not be empty. Of course you can't do get if the list of elements is empty. But here's the precondition for put. All it says is that you must have a Q pointer. Well, that's not enough, of course. You shouldn't do put unless the length of the list of elements is less than the size of the Q. So let me add that precondition. The effect of that is going to be if I recompile my spec, that when I rerun the same test, so this doesn't generate random tests, this just reruns the last one that failed. It fails for a different reason. It fails because the precondition of put was not true. So it was a bad test. And now if I generate tests, they'll all pass. Okay? That's cool. What you see here is some statistics on which operations we tested. We tested a few more puts than gets because you can't do a get until you've done a put. But we didn't test size at all. Why was that? That was because for simplicity, I commented out the specification of size. So let me just comment that back in again. Okay? You can see the precondition says you have to have a Q. This says how to generate a call of size, or how to call it. And this says the postcondition that I showed you before. So let me recompile that and now rerun my random tests. Darn! Another one failed. Okay, what happened here? We created a Q of size one. That's fine. It returned this pointer. We put zero into it. How many things are in the Q? One. I asked for the size. It returned zero. Okay. Whose fault is this? Mine. Yes, of course. But is it the model? No. No, this is really a wrong result. This is the code. We've put one thing into the Q, but the size function has returned zero. How is that even possible? Let's look at the code. Okay, here's the code for the size function. I've put one thing in. This returns zero. Size is one. How could it possibly return zero? Oh, return something, module one. That's always zero. So when the Q is of size one, this is always going to return zero. That can't be right, can it? So if you think about it, even when I put one thing into the Q, I incremented my input pointer and it wrapped around immediately. So my full Q looks just the same as an empty Q. And what's worse, this isn't just a question of Q's of size one. If I had a Q of any size, when I fill it full and the input pointer wraps around, both my input and output pointer are zero again and it looks empty. So the problem here is that I can't distinguish a full Q from an empty one. My representation isn't rich enough. Okay, how shall I fix it? Any ideas? So I could put a flag in there, couldn't I? But that would be so ugly. Let me show you a beautiful hack. When I am asked to create a Q of size n, do you know what I'm going to do? I'm going to make one of size n plus one. Don't tell anybody. Now, as long as the clients respect my preconditions, they can never see this bug because they can never put n plus one things in the Q. And if they do, it's their fault. Cool. Okay, so let me recompile the C code after making that fix and rerun the last failed test. Now it passes. And just to make sure, let's run some random ones. Darn, another test failed. Okay, put your debugging hats on. What happened here? I made a Q of size one. That's really two. I put a zero into it. Now it's full, pretending to be size one. I did a get to take that zero out. Now it's not full. I did another put. Okay, that's the second one. And then I asked for the size and it returned. Well, I've done two puts and one get. How many things are in the Q? One. Size returned minus one. How is that possible? Here's the size function. What went wrong? Anybody care to debug that? Right. The input pointer, I put two things in. The Q is really size two. The input pointer has wrapped around. The output pointer has not. So we get zero minus one, module two. But just a minute, minus one, module two should be plus one, right? Let's just check that. Darn. It's not. It's not an error length. Neither in C. So the problem is that when this expression becomes negative, I get a negative result out of size. So I have to make sure that this expression is never negative. How shall I fix the code? Absolute value. Of course. Let's recompile the C code. Let's rerun that test. Now it passes. Okay. So now I found the bug. I created a test that revealed the bug. I've amended my code. Now the test passes. All my tests are green. I'm done, right? Shall I run some random ones just for fun? Let's try that. It still fails. Look what's happened here. Here I created a Q of size two now. That's one step bigger. So that's an improvement. I've done three puts. That makes the input point to wrap around. One get. Three puts, one get. How many things are in the queue? Two. What did size return? One. And why was that? Because absolute value is the wrong thing to do here. Because it changes the value modulo size. What I need to do is to make sure that this expression is positive without changing the result of mod. And I can do that if I add Q size here. Because the difference between input and output will never be greater than Q size. So this will be always positive. And if I now test this, that previous test that failed now passes and so do all of the others. And I could run any number of tests now. They will all pass. So it's surprisingly how often we see the effects of what I just did in real code. Where we find some code, it's complicated. We can't understand why. And obviously what's happened is that somebody had a bug. They had a bug report and a test case. And they made the code work in that case without really understanding what the problem was. So all they've managed to do is make the code more complicated. They haven't managed to make it work. Okay. That was my demo. And the lessons I want to draw out from this are that first of all, the same properties can find many different bugs. And also those minimal failing tests make diagnosing things very easy. You know that if you delete any one step, then the test would pass. It is possible that if you deleted at the same time, you know, five steps from the middle of 12, and you picked just the right five, that you might be able to shrink it further. So we don't, we can't explore every possible simpler test. That would take far too long. So you have a weak guarantee. But usually it really is the minimal case. So we think of the shrinking process that has produced these minimal failures as extracting the signal from the noise of random tests. You get a lot of noise in random tests. And if you try and debug randomly generated stuff, it's impossible. But when you extract the signal, it's quite easy. Yesterday I talked about a big project that we've done in the last couple of years when we tested C code going into cars. Protocol stacks and other components that are part of the AutoSAR standard. Thousands of pages of PDFs we converted into specifications of the kind I've shown you. We have code from six different vendors to test. And we found hundreds of issues in the code. And of those, all of this code was supposed to implement the same standard. We found more than a hundred bugs in the standard. So that was a really, that's a really exciting project. But I talked about it yesterday. So I'm not going to say any more about that today. What I do want to do is show you a couple of other examples of database testing that we've done. And first of all, let me kick off with React. React is a no SQL distributed key value store. It's very scalable and fault tolerant and lots of good stuff. But it's only eventually consistent. So what does that mean? It means it's very hard to test. Because what does it even mean? I mean, suppose you do something with the database and then the result at the end of the test is not consistent. Well, it's only supposed to be consistent eventually. Maybe it's not eventually yet. So because of the nature of the beast, it's fundamentally quite hard to test. And so a year and a bit ago, then I did some work with the bash guys on trying to develop properties for testing React. We deliberately kept our tests as simple as we possibly could. So we realized that we would start off by testing the database. It's a key value store with only one key and one value. Maybe that sounds rather pathetic. But look at it this way. If we don't understand what the database does with one key, how can we possibly understand what it does with many? So we were deliberately taking a very simple model and then we would complicate the model only when we were really forced to by a failed test. I think that was a really good strategy for developing a good model of this complex software. Okay, so let me explain the React API. It has put and get operations. I'm not going to show the keys because there is only one. So you might put zero, one client put zero, another client does a get and on the same key and that client will see zero. And then maybe that second client might put one and the first client might do a get and will see one. I think we understand what React is supposed to do now, right? So here's an example that QuickCheck concocted. You put zero, it's all one client, you put zero, you put one, you put zero again and you do get. What will you see? One. Huh. That wasn't really what our simplest model was expecting. Now actually I'm pulling the wool over your eyes a little bit here because the API doesn't let you put a key and a value into the database. You put a React object into the database that contains a key and a value. And that means there's two different ways that you can do a put. You can create a new React object and put that in or you can take a React object you've already got, for example, because you just put it in the database and modify it. Modify the value and put the modified React object in. And in this test case, the first and last puts were putting a new value, so creating a new object, whereas the middle one was updating the first one. So we generated this test and I said, look, it shouldn't do this. And my friends at Bashow said, what are you thinking of? You shouldn't do that. This isn't a new key anymore. Why are you calling put new after you know the thing is in the database? So don't do it. So why didn't it work? Because all of these values are data or timed, timestamped with vector clocks. And at the time, React kept track of how many times each client had manipulated the value of that key. So if you think about it, we do a put new, then we do a put update. When we put the one, the one has been touched twice by this client, but the last zero has been touched only once because it's a new object. Touch twice is more than touched once. Therefore the one is newer than the zero. Therefore React discarded the zero. Okay. Well, so my friends at Bashow insisted this was the right behavior. But after we discussed it, they said, you know, there's this design rule for how you use the API that once you, for example, read an object from the database, you mustn't create a new object with the same key. You must modify it and write it back. So you have to be careful using the API. And then they were started thinking, I wonder if all our users know that. And not even they had thought about the fact that if you didn't follow the design rule, you could lose data. So it was quite good to at least elucidate that design rule. So that was our first step. So now what are we going to do, right? What are we going to do about this test that fails? Should we put vector clocks into the model? No, of course not. The model is supposed to be simple. It's supposed to be something that the user can use to understand how the database should behave. It shouldn't talk about vector clocks in the implementation to figure out what's going to happen. So the only other thing that we could do was put into the model, you shouldn't do that. And we did that. We made the model record each client's last view of the value. That is, every time we did a get, we would record what the client saw. And then we added a precondition that said that if a client has a view of the value, then it must update that view when it does a put. So you're not allowed to do a put new. And then we generate tests that respect that precondition and they all pass. So that was good. Okay. So let me tell you more about React. React supports, it's a very fault tolerant database, so it supports redundancy. When you do a put, it doesn't just go to one node, it by default goes to three. And if one of those nodes goes down and you do the put, then it will pick another node somewhere and store the value there instead. So at this point, you can see that there is a down node that has a stale value on it. Now, React remembers that that fourth value is in the wrong place. And it remembers where it should be sent back to. And when the node that was disconnected comes back, then there's a process called handoff that returns the value to the correct place. But handoff is not immediate. So there is a period when a node can come back and contain stale values. That's why it's eventually consistent. The other thing I have to explain to you is conflicts in React. So what happens if two clients put different values at the same time to a key? Well, you might say, ah, it looks as though the one arrived a little later will say that one wins. But no. Instead, React saves both values. It's called a conflict. And the next client to do a get will see them both. And the idea is that the client will then resolve the conflict by putting a single value back again. And future clients will then see the resolve value. So why do it this way? The idea comes from the original Dynamo database that Amazon developed. And the model here was the Amazon shopping basket. So suppose you're shopping on Amazon on your phone and your laptop at the same time. And they may be connected to different networks, going to different servers in maybe different clusters within Amazon. So what if you put one book in your shopping basket on the phone and another book in your shopping basket on the laptop? But the servers can't talk to each other. Now you've got a conflicted value for your shopping basket. But when you go to check out which value do you want to see? Which books do you want to see in your shopping basket? Obviously both, right? At least that's what Amazon wants you to see. So the conflict resolution there is just to gather everything up and smush them all together. But there are lots of examples where that's application dependent conflict resolution is useful. So we wanted to test React for eventual consistency. What we did was that means we were testing its behavior when nodes would become unavailable. So we generated random sequences of React calls, but also for each call, a random collection of nodes that would fail during that call. And then we tested to see whether at the end of execution we saw the correct values. Now when a test fails, normally here it's because of only a few of the calls, but also because of only a few of the node failures. And so we would shrink down these tests to get a minimal failing test with a minimal sequence of calls and a minimal set of node failures that you need to make the test fail. Let me show you the case we found. Here we are, two clients. This one puts a zero and then gets it back again. Now this client gets the zero and puts a one back. This client puts a two. Now those two puts are in conflict because the client on the left has not seen the one that the client on the right put. So when we do a get, we should see both values. What did we see? Only the one. Now why did that happen? To explain it, I have to show you the node failures. So let's bring in the three nodes now. I'm going to consider a cluster with only three nodes. When we did the first put, two of the nodes were down. Or maybe there was a network partition that meant the message didn't reach those two. When we did the first get, those two nodes answered and the other one was down. So the first client saw, oh, the value is not there anymore. That might seem strange if you put a value in the database and then you do a get and it's not there, but somebody else could have deleted it, of course. Now for the other operations, all three nodes respond. So the second client does a get and sees the zero because one of the nodes has it. The second client does a put, all the nodes hold one. The first client does a put now. Now think back to the first bug I showed you. That client is doing a put of a value that has only been touched by the client on the left because the last time the client searched for this key, it was not found. So that's a new React object. The one, though, that's been touched by both the client on the left and the client on the right. So the one is newer and the two can be discarded. That's why React just returned the one. So it's the same bug. It's the bug. You shouldn't do that. But who's doing it now? It's not me, the ignorant programmer. It's React itself doing it in response to node failures. So shock horror. React is not eventually consistent. Well, the truth, of course, is that it was not eventually consistent at this time. So what have we found? We found an extreme failure scenario. I want to emphasize that. We found a failure that arises when you have two different network partitions in quick succession with no time to heal the database in between. But it had bad results. It led to loss of data, a failure of eventual consistency, which is an important selling point for React. But it also provided a test framework that was immensely helpful when the redesign that fixed this problem was performed. Because for every attempt at a redesign, it was possible to run it through the same generated tests and in the end, to be pretty darn sure that the problem was fixed. So I just want to ask a meta question now. We found a lot of bugs in React. Does that mean React is buggy? Once I gave a talk about this material and in the discussion at the end, then one of the people in the audience said, well, I was going to use React, but I'm not sure I will now that I know it's so buggy. I just want to ask if you would rather use a database that has not been tested in this kind of way. So we've done a lot of work with Bashow and I feel React must be one of, if not the best tested database around as a result of that. So just because you managed to find and fix bugs, it doesn't mean that the product is then buggy. Okay, so that was a nice example of using React. I want to tell you one more story. It's about another database. This story starts with a message to the Adlang mailing list in 2007. We know there's a lurking bug somewhere in the debt's code. We've got bad objects and premise your end of file every other month the last year. We haven't been able to track the bug down because the file is repaired automatically next time it's opened. This was posted by a man called tupiternqvist from Klarna. Okay, so I'm sure we all feel tupiternqvist pain. But what's the context? Well Klarna develops an application that provides invoicing services for web shops. Maybe that doesn't sound terribly exciting, but since they're being founded in the mid-2000s, they've grown to more than 700 people. So it's a tremendously successful start-up. They're serving seven European countries now, and they built their entire system in Adlang. They stored their data in the database that comes together with the Adlang distribution, which is called Menezia, and that gives you transactions and replication and lots of good stuff, but it needs a back end to store its data. The disk back end is called debts. It provides tuple storage in files. Debt is the component that tupiternqvist talking about. Debt is the component that's failing every month or two. And when I heard about this, I thought failures every month or two, that sounds like a race condition. Let's see if we can track them down. Okay, so I'm going to show you how we test for race conditions with generated tests. And to do that, I'm going to go from the sublime to the ridiculous. Imagine testing these. So we have a lot of these in Sweden. Do we have them in Norway, too? You have them at a delicatessen counter, for example. So you take a ticket, and then you know when it's your turn to be served. Suppose I wanted to model that in Adlang. I'd need an operation to take a ticket, and every now and then the role of tickets runs out, so I'd need an operation to reset the dispenser back to zero. And now I could write a standard unit test for this quite easily. This is how it might appear in Adlang, where I perform a sequence of calls and I match each result against the expected value. And, well, you can see how I expect the thing to behave. But wait a minute. What is the point of a ticket dispenser? Its whole purpose is to regulate the flow of a lot of concurrent customers to one delicatessen counter, right? So what am I doing running sequential tests? Well, okay, it's good to test the sequential behavior, but this misses out on an important part of the dispenser's behavior that it should work when it's used in parallel. Okay. So if I wanted to test the dispenser, I can test it by modeling with the state machine in just the same way that we've seen before. If I've got a test case like this, then I can model the dispenser's state just by a single integer. It's really easy. And the state transition is you do an increment when there's a take, you set it to zero when there's a reset. And then the post condition will just check that the value that take returns is one more than the state when it's called. So that's really easy. But what I would like to do is to run tests like this instead. So this is supposed to represent a parallel test where first of all, I reset the dispenser and then one customer comes along and takes two tickets for some reason at the same time as another customer is taking a ticket. Okay. So what might happen here? Well, the customer on the left might get tickets one and two. The customer on the right might get ticket three. But that's not the only thing that can happen. The customer on the right might get ticket two and the one on the left might get one and three. That's also correct, isn't it? But this should not happen. If both customers get ticket number one, then something has gone wrong. So if you think about it, there are three possible correct outcomes for this test. So what are the expected results going to be? Well, of course, in this case you could just record the three tickets and then compare against the three possibilities and see have you got one of those correct outcomes. But this is a very tiny test. I don't want to run tests like this. I want to run tests like this. How many correct outcomes are there of this test? Can you figure it out? Luckily I've done it for you. Forty-two, of course. So now think about enumerating the forty-two possible correct outcomes. Nobody in their right minds would do that. And anybody who tried would get at least one of them wrong. So you fundamentally can't do that. You can't figure out the expected results for a parallel test. The only thing you can do is try and detect whether a test has passed or failed with some kind of property. So race condition testing, I think, is a killer app for property based testing. Okay. So let's go back to the parallel test that I drew before. I've turned it on its side here and asked ourselves, how do I know that this test succeeded? Well, I know because there is some order in which I could have performed those calls where the results would match the model. That is, if I interleave the calls and results like this, then they become consistent with the model. So that's what we do. We generate parallel tests and then we ask, is there any interleaving that can explain what happened? If so, we say the test passed. If not, it must have failed. I will just do one more quick demo here. I have my dispenser code. Just compile it. And I'll run, first of all, some sequential tests. So those sequential tests demonstrate that my implementation and my model match. And now if I run parallel tests, I'm using exactly the same model so it's a very slight difference to run parallel tests instead. Well, there's a race condition. And if you look at what happened, you can see we did two things in parallel. Two calls of take ticket, they both returned one. Now, the original random test was more complex. It's up here. But after shrinking, we get down to this minimal case that provokes the race. And I just want to run this test a number of times so I'll get different random tests that fail. But see where I end up. After shrinking, it's always the same minimal example. So that means that tells us that this example probably really is the minimal one. And if I go back to my presentation, that's the failing test. Here's the code I wrote for taking a ticket. So it's reading a shared global variable and then writing M plus one. It's a critical section. Where's the synchronization? There isn't any. So of course there's a race condition here. And the point is not how stupid code I wrote. The point is that given this kind of race condition, we can find it very quickly and reliably by this method. So let's go back and talk about debts instead. Debt provides a tuple store. It stores Airdlang tuples which have curly brackets around them. And the first component is the key. And it's got an API with a kind of operation you would expect. You know, you can insert a list of tuples into the table. You can delete all the tuples with a given key. Insert new is like insert except that if any of the keys is already present, then it's a no op. And it's atomic. So that's kind of nice. And there's some more. Nothing that will surprise you. So now I have to model the behavior of debts and it's really simple to do that. It's almost enough just to have a list of the tuples that I think should be in the table. So that's what I did. I wrote a spec in the same style that you've seen. It was less than 100 lines of code for the core of the debt's API. And in comparison, the implementation of debts is more than 6,000 lines of code in four different modules. Why? Because it's keeping hash tables on the disk and of course it's complicated stuff. But the intended behavior is quite simple. So I wrote my spec. I ran my sequential tests. They all passed. And I started running parallel ones. And what do you know? As soon as I did that, I found a race condition. So what's happening here? Well, in a prefix, I'm opening the file, surprise, surprise. And then I'm doing two things in parallel. I'm inserting an empty list of tuples. I'm just going to get my pointer back here. I'm inserting an empty list of tuples. That's a no op and it returned okay. And I'm using insert new to insert another empty list of tuples. That's also a no op. And that returned okay too. And QuickCheck says there's no possible interleaving of these calls that can explain this result. Okay, wait a minute. But they both returned okay. What's wrong? Sometimes there's just no alternative. You have to read the manual. Here's what it says about insert new. Look at the result type. Even in Erdlang, a bool is either true or false. It's not okay. And in thousands of sequential tests, insert new returned true or false every time. As soon as I ran it in parallel, it returned okay. Where did that come from? Okay, so I went on, ran some more tests. I found this one. In the prefix, we opened the file. And now in parallel, we do two insertions. One using insert. We insert a tuple 00. And at the same time, we do an insert new 00. So the insert new maybe could succeed or maybe could fail depending on which one of them goes first. But it shouldn't time out. And we shouldn't see a message. Error report, bug was found. So that seemed to be pretty conclusive that I'd come across another bug. So at this point, I decided that insert new just doesn't work. And I excluded it from my tests. And I found this one. Okay. So here in the prefix, we open the file. And now in parallel, one process opens the file again. You might think that seems odd. But it's not. This database is designed to be used in Erlang systems which are very highly concurrent. Many processes may use the table at the same time. Each of them must make sure it's open. So it's okay for one process to reopen the database while another one is using it. The other process is inserting a tuple into the table and then getting the entire contents and where's that 00? I just put it in. And it's gone. So I found this bug in several forms. That if one process was reopening the table, another sequential process could see an inconsistent view of the database contents where its own operations had no effect. So I sent these bugs to Hassel Bolynder at Ericsson, the man who was responsible for the code. And he said, oh, thank you very much. Here's a new version. He sent me a fixed version the next day. He said, that's great. But I don't think these are the bugs that Klarna are experiencing because the symptoms are not the same. At Klarna, the file is being corrupted. Okay. File corruption. I added one line to my test that said, after we've run the parallel operations, just check that the file is not corrupt. There was an easy way to do that. And I started running more tests. This time I had to run a few thousand. And then I found this. Look at this. In the prefix, we open the file. We close it. We open it again. Then we do three things in parallel, a lookup of something that's not there, and two insertions of the same, that same tuple, in fact. All of the results are consistent with my model. But when I check the file for corruption, what do you know? I got to prevert your end of file. So I want to emphasize, this is the smallest example that can provoke this bug. I looked at it and I thought, open, close, open, you've got to be kidding. It must fail if I just open the file and then do the three things in parallel. But no, I ran tens of thousands of tests. They all passed. Nowadays I know why. The first open creates the file. Then we close it. The second open opens an existing file. It leaves the code in a slightly different state and that difference is critical to this bug. So I really love this example because can you imagine anybody writing this test in a test suite? Why would you test this collection of six calls for goodness sake? So anyway, I was very happy to find this. I sent it off to Hassek. I got a correct version of the code back next day and then I was giving a talk at a conference in Orhooves. I was supposed to talk about something else but I thought this is such a great story. I have to tell it. Only I hadn't saved the output from running QuickCheck. So I had to sit in my hotel room making new slides and I rerun my tests and copied and pasted the output onto my slides and as I was doing that, guess what? I found this one. Okay in the prefix, we open the file and we insert a tuple and then in parallel, one process is just reopening the file again. The other one is looking up something that's not there and deleting the thing that is. Once again, all the results, all the return values are consistent with the model but when I checked for corruption, I got a bad object. I want to remind you of the mailing list message. We know there's a lurking bug somewhere. We've got bad objects and premedure in the file every other month for last year. I sent that example off to Hasse as well. Next day I got a fixed version. That fixed version has been in service at Glarner for more than a year now. There has been, well, before it was installed, the problem got worse. It was happening once a week and every time this happened, the main server went down. Its database was corrupt. All the data could be restored from a replica but it took hours to bring that machine back up again. Since the new code has been installed, they've had bad object once when accessing a file that had not been written since before the new code went into service. So it looks as though we really did nail those bugs. So a lot of work had gone into searching for these bugs beforehand, of course. I've talked to the people who did it. The developer spent six weeks at Glarner trying to figure out what on earth was going wrong. At the end of that time, they thought it seems to happen when the file is about one gigabyte. Maybe it's something to do with rehashing. Afterwards, we could reproduce the failures with a database with either zero or one records. It took either five or six calls to reproduce each of those serious bugs. And it took less than one day to fix the problem given that minimal example. And I think this really shows two things. One, the enormous value of minimal failing cases and secondly, how hopeless it is to try and debug this kind of race condition from failures in production. Where billions of irrelevant things have happened as well as the five or six calls that are actually responsible for the problem. Yeah. So I did it now and then over a period of a few days if I had an hour spare, I would spend a little time on it. But probably less than a day's work in total. It was only a hundred lines of code. So, yeah. I will just skip over this little bit I think because I've now said most of what I wanted to say. So my point is property based testing like this, you find more bugs because you can do better testing and it's less effort. Don't write tests, generate them. That's my message. And I'm happy to take questions. So you had that example that had 42 different possible legal interleavings. Do you have a way of keeping track and verifying that you've covered some fraction of the legal ones? Without feel more confident if I hit all 42 of those and not have a problem as opposed to I would have found seven. So the question is whether we have some way of being confident that we've actually seen a lot of those 42 possible interleavings. And the answer is no. So one problem with testing for race conditions is of course that the interleavings that you get can be very deterministic. If you run on a single core machine, it's amazing how deterministic the scheduler can be. So maybe your race condition will just never show. What we found, we've done two things. With airline code, we have a randomizing scheduler that we can use instead. And that provokes race conditions a lot more often. The other thing that we do is we just run on a multi core. The more cores you have, the easier the race conditions are to provoke. And in order to make race conditions appear, we just run each test a lot of times. And that has actually worked very well for us. Maybe partly because it's an airline, airline race conditions are maybe they're not quite as tough to provoke as race conditions, data races on shared data. Yeah. So we have interoperated with other languages. There's something we've used to interoperate with Java, which is fairly smooth. At Ericsson, this has been used to interoperate with C++ generated from Rational Rose RT. So we've made connections to a number of languages, but for the C connection, then we've put quite a lot of work into making it very smooth so that I can do it here in front of you. In the other cases, it's a bit less, it's a bit more ad hoc and there's a bit more work to be done in each case. So we should really put the work in and make a smooth connection to.NET and to Java, but we haven't done that yet. Oh, yeah. I know. So I meant to also show you this. If you'd like to find out more about this, about this kind of testing, then Haskell QuickCheck was the original version. There's a paper back in ICFP in 2000 that you can look at. Of course, we have our cubic commercial tools, so we're very happy to talk to people about this. But there are also many, many tools that have been inspired by the basic ideas. The ScalaCheck, there's FSCheck for F sharp, ClosureCheck, Test.Generate. I meant to add that to my slide. Darn. Which too was talking about before lunch. So there are lots of instances of the idea. It was, I guess you know you have a good idea when lots of people copied. And that's certainly what's happened. So the question is, what about intermittent failures and how do those interact with shrinking? So what shrinking does is we take the original random test and then there's a number of simpler tests shrinking candidates, simpler tests that we try. We run each one and if one of those fails, then we say, oh, now we've got a simpler test, let's start shrinking from here. But what if the test only fails intermittently? Then by sheer bad luck, all of the shrunk tests might pass. And what happens then is that shrinking stops and you end up with a so-called minimal test that is very big. So it's normally quite easy to recognize when that is happening because you see that shrinking did not work. So what we do is while we're shrinking, we can turn up the number of executions of each test. So if something shows, you know, once in a hundred runs, well, during the shrinking search, we'll run each test 500 times. It takes a little time, but compared to scratching ahead and trying to understand what the problem is otherwise, you know, it's much, much better unless just to let QuickCheck spend a few minutes shrinking. Sorry? So the Haskell QuickCheck is open source and I think these other tools are open source. The tool that I showed you, that's a commercial product. Oh, yes. So the question is how do we simulate node failures in the React case? We spend some time trying to make nodes go up and down or trying to reconfigure the kind of Erlang networking so that nodes would appear to go up and down. That turned out, A, to be very difficult. For a start, Erlang is very fault tolerant, so we would make a node go down or simulate a node going down and then it would come back up again. But secondly, we want to run thousands of tests and really taking nodes up and down is quite slow. So what we did at the time that I was working with the BASHA team on this was we took the React logic and we extracted it and tested it separately. And that meant that we could very easily just, you know, tell this piece of React logic, these are the nodes that you should use because the others are simulated to be down. And so in the end when we found the bugs, we were not testing the same code that was actually in React. After the time that I spent at BASHA, what the BASHA guys did next was refactor React so that the logic was separated out and could be tested separately. So now we are testing the real code in React. Well, I think that was also quite a nice lesson that running these tests demonstrated that a refactoring of the structure of React could make it a lot more testable. So the question is the example I showed you ran pretty fast, but how do the runtime scale when we get on to more realistic examples? So a lot of the React tests would, you'd also run several tests a second. So very often we're testing, you know, parts of larger systems and the tests do run fast. In the testing of the code from cars that I talked about, then we can run, you know, thousands of tests in half an hour. So of course things do get a little bit slower, but not so much as to be a problem for usability. question, would you agree to the model that you have to apply easily or simple in terms Okay, so the question is whether when you take real complex systems with complex business logic, yeah, whether the models get much, much larger and whether you end up, whether it's economic to model them. So yes, of course, they do get larger. Yesterday, I mentioned that when we were testing the Outisar code, which is specified by thousands of pages of PDFs, we ended up with 20,000 lines of model, which is still a lot smaller than the PDFs, much, much smaller. So that was manageable. One of the traps you can run into with this kind of testing is if your model begins to resemble the real code too much, because then, of course, there's a risk that you just replicate the same mistakes that you've made in the real code. If it's the same person writing the tests in the real code. So we always try to make sure that there's a difference in level of abstraction. And one of the things we've discovered is that you often don't need a very precise model to find a lot of bugs. That is, maybe you can, with a small amount of work, create a model that models your behavior approximately, and with 10 times as much work, model behavior more exactly. Now in that kind of case, it's often better just to make the partial model, because that will can still find an awful lot of bugs. I have an example from the first Ericsson product that we tested, which was a firewall base. It would connect phone calls. And you could add and subtract callers to a call. And we found a bug where you added two callers, subtracted one, added a third, subtracted that, added a fourth, and subtracted the fourth. So sequence of seven calls that made the system crash. Now actually, it was already wrong after the first subtract, subtract corrupted data structures. It wasn't found in normal testing because the most usual case, which was what people were testing, was add, add, subtract, subtract. And that second subtraction would then throw away the corrupt data before it had a chance to cause a problem. So if we had written a model that checked those data structures, we could have caught that problem after three operations, two adds and one subtract, or maybe after two, after one add and one subtract. Because we had a more partial model, it took seven operations to find the bug. But if you compare the time it would have taken us to make a more precise model, with the short time it took to find and debug this sequence of seven cases, it made a lot more sense to work with the partial model. And that happened surprisingly often that partial models can find the bugs you want to find anyway. Maybe we should take it offline because I realized that we're seven minutes into the break. I'm sorry about that. Thank you. Thank you.
really, really loves testing? Oh, more hands than testing hard? Well, imagine that your testing state the code should be in at each point. And should behave. It shouldn't talk about vector not the best tested database around as a result them down. Okay, so I'm going to show you how we test for race conditions with generated tests. And to do that, I'm going to go from the sublime there any interleaving that can explain what about insert new. Look at the result type. Even think these are the bugs that Klarna are not there, and two insertions of the same, that Ericsson product that we tested, which was a