Automatic Test GenerationProf. Aiken CS295 Lecture 3 1Lecture 3CS295The Idea• Automatically generate tests for software•Why?–Find bugs more quicklyProf. Aiken CS295 Lecture 3 2Find bugs more quickly– Conserve resources• No need to write tests• If software changes, no need to maintain tests• No need for testers?!The Problem• Automated testing is hard to do• Probably impossible for whole systemsProf. Aiken CS295 Lecture 3 3• Certainly impossible without specificationsPre- & Post-Conditions•A pre-conditionis a predicate – assumed to hold before a function executes•A post-condition is a predicate Prof. Aiken CS295 Lecture 3 4A postcondition is a predicate – Known to hold after a function executes– Whenever the precondition also holdsExamplePre: member(x,l)List remove(x : Elem ,l: List) {if (x == head(l))Prof. Aiken CS295 Lecture 3 5return tail(l);elsereturn cons(head(l),remove(x,tail(l)));}Post: !member(x,l)More on Pre- and Post-Conditions• Most useful if they are executable – Written in the programming language itself– A special case of asserts•Recommended by punditsProf. Aiken CS295 Lecture 3 6Recommended by pundits– And academics• Need not be precise– Full pre- and post-conditions may be more complex than the code!– But useful even if they do not cover every situationUsing Pre- and Post-Conditions• Pre-/Post-Conditions are specifications• To perform a test:–Check that the test input satisfies pre-conditionProf. Aiken CS295 Lecture 3 7Check that the test input satisfies precondition–Run test– Check that the test result satisfies post-condition• Doesn’t help write tests, but it helps run themThree Automatic Techniques• Randomized testing• Mutation analysisProf. Aiken CS295 Lecture 3 8•KoratRandom Testing• Feed random inputs to a program• Observe whether it behaves “correctly”–Execution satisfies pre & post conditionsProf. Aiken CS295 Lecture 3 9Execution satisfies pre & post conditions– Or just doesn’t crash• A simple pre/post condition• E.g., the Fuzz experiment on Unix utilitiesRandom Testing: Good News & Bad News• Randomization is a highly effective technique– Easy to implement– Provably good coverage for enough testsProf. Aiken CS295 Lecture 3 10•But– To say anything rigorous, must be able to characterize the distribution of inputs– Easy for string utilities– Harder for systems with more arcane input• E.g., parsers for context-free grammarsRandom Testing: Example100% .1% .0001%Prof. Aiken CS295 Lecture 3 11• The lexer is very heavily tested by random inputs• But testing of subsequent stages is much less efficientMutation Analysis• How do we know our test suite is any good?• Idea: Test variations on the program–Eg replace x > 0by x < 0Prof. Aiken CS295 Lecture 3 12E.g., replace x > 0by x < 0–Replace I by I+1, I-1• If the test suite is good, it should report failed tests in the variants–This is mutation analysisMutation Analysis• Modify (mutate) each statement in the program in finitely many different ways• Each modification is one mutantProf. Aiken CS295 Lecture 3 13• Check for adequacy wrt the set of mutants– Find a set of test cases that distinguishes the program from the mutantsWhat Justifies This?• The “competent programmer assumption”The program is close to right to begin with• It makes the infinite finiteW ill i it bl d thi t l t h it i Prof. Aiken CS295 Lecture 3 14We will inevitably do this anyway; at least here it is clear what we are doing• This already generalizes existing metricsIf it is not the end of the road, at least it is a step forwardThe Plan• Generate mutants of program P• Generate tests–By some processProf. Aiken CS295 Lecture 3 15•For each test t–For each mutant M•If M(t)  P(t) mark M as killed• If the tests kill all mutants, the tests are adequateGenerating Tests• Mutation analysis seeks to generate adequate test sets automatically• Must determine inputs such that– Mutated statement is reachedProf. Aiken CS295 Lecture 3 16– Mutated statement produces a result different from originals, s’Automatic Test Generation• This is not easy to do• Approaches–Use weakest-preconditionsProf. Aiken CS295 Lecture 3 17Use weakestpreconditions– Work backwards from statement to inputs• Take short paths through loops– Generate symbolic constraints on inputs that must be satisfied–Solve for inputsA Problem• What if a mutant is equivalent to the original?• Then no test will kill itProf. Aiken CS295 Lecture 3 18• In practice, this is a real problem– Not easily solved• Try to prove program equivalence automatically• Often requires manual interventionKorat• A test-generation research project•Idea– Leverage pre- and post-conditions to generate Prof. Aiken CS295 Lecture 3 19gppgtests automatically•But how?The Problem• There are infinitely many tests– Which finite subset should we pick?• And even finite subsets can be hugeProf. Aiken CS295 Lecture 3 20g– Need a subset which gives good coverage– Without a lot of redundancy• Many tests will just test the same thing• Need a way to select a diverse test suiteAn Insight• We can often do a good job by testing all inputs up to a certain, small size• The “small test case” hypothesisProf. Aiken CS295 Lecture 3 21– If there is any test that causes the program to fail, there is a small test• If a list function works on lists of length 0, 1, 2, and 3, it probably works on all lists.– E.g., because the function is oblivious to the lengthHow Do We Generate Test Inputs?Class BinaryTree {Node root;class Node {• Use the types• The class declaration shows what values (or null) can fill each fieldProf. Aiken CS295 Lecture 3 22Node left;Node right;}}null) can fill each field• Simply enumerate all possible shapes with a fixed set of Nodes.A Simple Algorithm• User selects maximum input size k• Generate all possible inputs up to size kProf. Aiken CS295 Lecture 3 23• Discard inputs where precondition is false• Run program on remaining predicates• Check the results using the postconditionExample: Binary Trees• How many binary trees are there of size <= 3?•Calculation:–3 nodes2 sl ts p r n dProf. Aiken CS295 Lecture 3 24–2 slots per node• Left and right children– 4 possible values (one of the