In this video we're going to talk about automated test case generation in a little bit more detail. And these slides that I'm going to present are in part due to Professor Gregory Gay in South Carolina. So thanks to Greg for letting me use them. So software testing, we've been looking at this now for months, and what it comes down to in some degree is fundamentally we try an input, and we we see what happens. And we can try any number of almost an infinite number of inputs. So, we don't want to just try any input, we want to try creating test cases that find faults, errors in program behavior, obtain coverage over structural elements like branch coverage, or stadium coverage, cover combinations of representative values. So when we talked about pairwise testing, and partition testing, model important use case scenarios. So when we do tester in development, we're trying to exercise the user behavior that we expect of the system, and in some cases to establish reliability measurements. So we run thousands and thousands of test cases, and if none of them fail then we can claim to have some level of reliability of the software. So, what do these have in common? Well, in every case, we're searching for something. We're searching for faults, we're searching for tests that allow us to cover more of the program structure, we're searching from some other criteria. And so the question you have to ask yourself is, do you have a goal in mind when testing? And in almost all the cases that we look at we do. And can that goal be measured? Well sure. We can talk about how many branches we've covered, or how many faults we found, or how many pairs we've tested. And in this case, we're searching for a test suite that achieves that goal. And what we would like, is we'd like to find a relatively small test suite that achieves the goal as well as possible. So, finding a test suite that obeys certain properties, that covers all branches, try's all two way represented values et cetera. There are any number of criteria, and they can be combined that you can use as a measure for how good a test suite is. Well, if we consider it in this way, testing is a search problem. And the question that we're really trying to figure out at the end of the day is, to find out all the faults that are in the program. But this is something that we can't measure. It's very difficult to make any kind of objective statement about the number of remaining faults in a program. Which is why we have all these different structural metrics that we tend to use for judging the goodness of our test suite. So, we use them instead. We can talk about the number of properties in the set of requirements that we've tested, how well we've tested them, how well we've tested the structure of the program, the coverage that we've obtained. And what we can do is, now that we have a goal in mind, we can ask the computer to try and achieve this goal in lots of different ways, and that's really the basis of automated test generation. Our different heuristics that we can use to try and get the computer to solve the testing goal that we have set in front of it for us. And there are lots of different techniques that we'll look at for automated test generation. So let's look at the search process a little bit more. The idea for a lot of these test generation strategies is we start from a test suite. So, where does this suite come from? Well, we could create it randomly. And we look at it and it says, you know, boy, this doesn't do very well at all, it doesn't cover most of the program's structure, or it doesn't give us boundary values or other things. So maybe we can refine that, and we can keep trying new solutions until the goal is achieved, or all the solutions are tried. But, that's not practically efficient because we know that there are many millions or billions of possible tests. So, the order that solutions are tried as is key to finding an efficient solution for testing. So, we have different strategies that we use for finding these test suites that we call heuristics, and the idea is that when we can use heuristic to choose solutions and ignore solutions that we know aren't going to help us achieve our goal. And the mechanism that we use to do this is a search budget. So, if we had infinite time and patience we could try everything but we don't. So, we want to bind the search process to a budget, and this budget can be in terms of either time, or the number of tests, or the number of attempts that you make to generate tests. And so, what we try and do is find as good a solution as we can before the time budget expires. So, that brings in this idea of optimization. And what we're really trying to do with automated testing is an optimization problem, we want to try and find the best solution given the possible search budget. And it turns out that different techniques will allow us to more thoroughly test programs in certain conditions than others, but it depends a lot on the structure of the program and the things that we're trying to establish. So, the search heuristic that we use is important. If it's a time bound then we want to try and execute as many tests as we can to achieve a higher level of coverage, but do it in a systematic way so we're not sort of running down the same paths over and over. If it's the number of attempts, then what we want to do is we want to try and make sure that every test we choose to explore is one that's likely to increase our relevance. So, why would we be concerned about attempts versus time? Well in some situations it's actually, there's a certain cost to running any given test. And so, what we want to do and thinking of test generation is we want to make sure that every test that we suggest is a possibility, is one that's likely to increase value. And in practice, both of these categories actually tend to matter, and it depends on the program that we're executing and the goal that we have. So, in the next few lectures, we're going to look at different automated test generation strategies, and describe where they're strong and where they're weak, and where we might be able to use each in combination to make really good test suites that thoroughly test our program.