Computing For Life Sciences
Computing For Life Sciences CS 59000
Popular in Course
Popular in ComputerScienence
This 70 page Class Notes was uploaded by Nick Rowe on Saturday September 19, 2015. The Class Notes belongs to CS 59000 at Purdue University taught by Xiangyu Zhang in Fall. Since its upload, it has received 5 views. For similar materials see /class/208062/cs-59000-purdue-university in ComputerScienence at Purdue University.
Reviews for Computing For Life Sciences
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/19/15
Testing slides compiled from Alex Aiken s Neelam Gupta s Tao Xie s Why Testing CI Researchers investigate many approaches to improving software quality But the world tests gt 50 of the cost of software development is testing Testing is consistently a hot research topic CS590F Software Reliability Testinput generation 7 Specmcmmnymode rbased Komt dannov rU UC T951931KhursmdUTAHSUHECE NASA Java Paumnder wsssrNAsA Spec AsmwwsR FSE Coderbased Rostra SymstragtlteNCSU JCrashaCuCSmmagdakwsigeeurgwmech TGEMGUMQVQAHZOML B ast Bewke ey SLAM MSR CSSDEIF smwm Reliability El Fundamentally seems to be not as deep Over so many years simple ideas still deliver the best performance El Recent trends Testing XXX DAIKON CUTE El Messages conveyed Two messages and one conclusion El Difficuties Beat simple ideas sometimes hard Acquire a large test suite CS590F Software Reliability El Testing practice Goals Understand current state of practice 00 Boring 00 But necessary for good science Need to understand where we are before we try to go somewhere else El Testing Research El Some textbook concepts CS590F Software Reliability Testing Practice CS590F Software Reliability DDDDDD Manual testing Automated testing Regression testing Nightly build Code coverage Bug trends CS590F Software Reliability Manual Testing Test cases are lists of instructions test scripts Someone manually executes the script Do each action stepbystep 00 Click on login oz Enter username and password oz Click quotOKquot 00 And manually records results Lowtech simple to implement CS590F Software Reliability Manual Testing El Manual testing is very widespread Probably not dominant but very very common El Why Because Some tests can39t be automated 00 Usability testing Some tests shouldn39t be automated 00 Not worth the cost CS590F Software Reliability Manual Testing El Those are the best reasons El There are also notsogood reasons Notsogood because innovation could remove them Testers aren39t skilled enough to handle automation Automation tools are too hard to use The cost of automating a test is 10X doing a manual test CS590F Software Reliability Topics Manual testing Automated testing Regression testing Nightly build Code coverage DDDDDD Bug trends CS590F Software Reliability Automated Testing El Idea Record manual test Play back on demand El This doesn39t work as well as expected Eg Some tests can39tshouldn39t be automated CS590F Software Reliability Fragility El Test recording is usually very fragile Breaks if environment changes anything Eg location background color of textbox El More generally automation tools cannot generalize a test They literally record exactly what happened If anything changes the test breaks El A hidden strength of manual testing Because people are doing the tests ability to adapt tests to slightly modified situations is builtin CS590F Software Reliability Breaking Tests El When code evolves tests break Eg change the name of a dialog box Any test that depends on the name of that box breaks El Maintaining tests is a lot of work Broken tests must be fixed this is expensive Cost is proportional to the number of tests lmplies that more tests is not necessarily better CS590F Software Reliability Improved Automated Testing El Recorded tests are too low level Eg every test contains the name of the dialog box El Need to abstract tests Replace dialog box string by variable name X Variable name X is maintained in one place 00 So that when the dialog box name changes only X needs to be updated and all the tests work again CS590F Software Reliability Data Driven Testing for Web Applications El Build a database of event tuples lt Document Component Action Input Result gt El Eg lt LoginPage Password lnputText password OK gt El A test is a series of such events chained together El Complete system will have many relations As complicated as any large database CS590F Software Reliability Discussion El Testers have two jobs Clarify the specification Find important bugs El Only the latter is subject to automation El Helps explain why there is so much manual testing CS590F Software Reliability Topics Manual testing Automated testing Regression testing Nightly build Code coverage DDDDDD Bug trends CS590F Software Reliability Regression Testing El Idea When you find a bug Write a test that exhibits the bug And always run that test when the code changes 80 that the bug doesn39t reappear El Without regression testing it is surprising how often old bugs reoccur CS590F Software Reliability Regression Testing Cont El Regression testing ensures forward progress We never go back to old bugs El Regression testing can be manual or automatic Ideally run regressions after every change To detect problems as quickly as possible El But regression testing is expensive Limits how often it can be run in practice Reducing cost is a longstanding research problem CS590F Software Reliability Nightly Build El Build and test the system regularly Every night El Why Because it is easier to fix problems earlier than later Easier to find the cause after one change than after 1000 changes Avoids new code from building on the buggy code El Test is usually subset of full regression test smoke test Just make sure there is nothing horribly wrong CS590F Software Reliability A Problem El So far we have Measure changes regularly nightly build Make monotonic progress regression El How do we know when we are done Could keep going forever El But testing can only find bugs not prove their absence We need a proxy for the absence of bugs CS590F Software Reliability Topics Manual testing Automated testing Regression testing Nightly build Code coverage DDDDDD Bug trends CS590F Software Reliability Code Coverage El Idea Code that has never been executed likely has bugs El This leads to the notion of code coverage Divide a program into units eg statements Define the coverage of a test suite to be of statements executed by suite of statements CS590F Software Reliability Code Coverage Cont El Code coverage has proven value It39s a real metric though far from perfect El But 100 coverage does not mean no bugs Eg a bug visible after loop executes 1025 times El And 100 coverage is almost never achieved Infeasible paths Ships happen with lt 60 coverage High coverage may not even be desirable May be better to devote more time to tricky parts with good coverage CS590F Software Reliability Using Code Coverage El Code coverage helps identify weak test suites El Code coverage can39t complain about missing code But coverage can hint at missing cases 00 Areas of poor coverage gt areas where not enough thought has been given to speci cation CS590F Software Reliability More on Coverage CI CI CI CI Statement coverage Edge coverage Path coverage Defuse coverage CS590F Software Reliability Topics Manual testing Automated testing Regression testing Nightly build Code coverage DDDDDD Bug trends CS590F Software Reliability Bug Trends El Idea Measure rate at which new bugs are found El Rational When this flattens out it means 1 The costbug found is increasing dramatically 2 There aren39t many bugs left to nd CS590F Software Reliability The Big Picture El Standard practice Measure progress often nightly builds Make forward progress regression testing Stopping condition coverage bug trends CS590F Software Reliability Testing Research CS590F Software Reliability El Overview of testing research Definitions goals El Three topics Random testing Efficient regression testing Mutation analysis CS590F Software Reliability Overview El Testing research has a long history At least to the 196039s El Much work is focused on metrics Assigning numbers to programs Assigning numbers to test suites Heavily influenced by industry practice El More recent work focuses on deeper analysis Semantic analysis in the sense we understand it CS590F Software Reliability What is a Good Test El Attempt 1 If program P implements function F on domain D then a test set T g D is reliable if Vt E T Pt Ft gt Vt E D Pt Ft El Says that a good test set is one that implies the program meets its specification CS590F Software Reliability Good NewsBad News El Good News There are interesting examples of reliable test sets Example A function that sorts N numbers using comparisons sorts correcty iff it sorts all inputs consisting of 01 correctly This is a finite reliable test set El Bad News There is no effective method for generating finite reliable test sets CS590F Software Reliability El It s clear that reliable test sets must be impossible to compute in general El But most programs are not diagonalizing Turing machines El It ought to be possible to characterize finite reliable test sets for certain classes of programs CS590F Software Reliability Adequacy El Reliability is not useful if we don39t have a full reliable test set Then it is possible that the program passes every test but is not the program we want El A different definition lf program P implements function F on domain D then a test set T g D is adequate if Vprogs Q QD i FD gt 3 t e T Qt st Ft CS590F Software Reliability Adequacy El Adequacy just says that the test suite must make every incorrect program fail El This seems to be what we really want CS590F Software Reliability El Overview of testing research Definitions goals El Three topics Random testing Efficient regression testing Mutation analysis CS590F Software Reliability Random Testing El About of Unix utilities crash when fed random input strings Up to 100000 characters El What does this say about testing El What does this say about Unix CS590F Software Reliability What it Says About Testing El Randomization is a highly effective technique And we use very little of it in software El A random walk through the state spacequot El To say anything rigorous must be able to characterize the distribution of inputs Easy for string utilities Harder for systems with more arcane input 00 E g parsers for contextfree grammars CS590F Software Reliability What it Says About Unix El What sort of bugs did they find Buffer overruns Format string errors Wild pointersarray out of bounds Signedunsigned characters Failure to handle return codes Race conditions El Nearly all of these are problems with C Would disappear in Java Exceptions are races amp return codes CS590F Software Reliability A Nice Bug CI csh 08f is the history lookup operator No command beginning with 08f csh passes an error 08f Not foundquot to an error printing routine Which prints it with printf CS590F Software Reliability El Overview of testing research Definitions goals El Three topics Random testing Efficient regression testing Mutation analysis CS590F Software Reliability Efficient Regression Testing El Problem Regression testing is expensive El Observation Changes don39t affect every test And tests that couldn39t change need not be run El Idea Use a conservative static analysis to prune test suite CS590F Software Reliability The Algorithm Two pieces 1 Run the tests and record for each basic block which tests reach that block 2 After modifications do a DFS of the new control flow graph Wherever it differs from the original control flow graph run all tests that reach that point CS590F Software Reliability T1 1 3 T1 T3 Label each node of The control flow graph wiTh The se r of Tes rs Thai r each i r CS590F Software Reliability Example Cont When a s ra remen r is modified r39er39un jus r The Tes rs reaching Tha r s ra remen r CS590F Software Reliability Expe ence El This works And it works better on larger programs of test cases to rerun reduced by gt 90 El Total cost less than cost of running all tests Total cost cost of tests run cost of tool El Impact analysis CS590F Software Reliability El Overview of testing research Definitions goals El Three topics Random testing Efficient regression testing Mutation analysis CS590F Software Reliability Adequacy Review If program P implements function F on domain D then a test set T g D is adequate if Vprogs Q QD i FD gt 3 t e T Qt i Ft But we can39t afford to quantify over all programs CS590F Software Reliability From Infinite to Finite El We need to cut down the size of the problem Check adequacy wrt a smaller set of programs El Idea Just check a finite number of systematic variations on the program Eg replace x gt O by x lt 0 Replace l by 1 l1 El This is mutation analysis CS590F Software Reliability Mutation Analysis El Modify mutate each statement in the program in finitely many different ways El Each modification is one mutant El Check for adequacy wrt the set of mutants Find a set of test cases that distinguishes the program from the mutants f program P implements function F on domain D then a test set T g D is adequate if Vmutants Q QD FD gt 3 t e T Qt i Ft CS590F Software Reliability What Justifies This CI The competent programmer assumptionquot The program is close to right to begin With El It makes the infinite finite We will inevitably do this anyway at least here it is clear What we are doing El This already generalizes existing metrics If it is not the end of the road at least it is a step fonvard CS590F Software Reliability The Plan El Generate mutants of program P El Generate tests By some process El For each test t For each mutant M If Mt t Pt mark M as killed El If the tests kill all mutants the tests are adequate CS590F Software Reliability The Problem El This is dreadfully slow Lots of mutants Lots of tests Running each mutant on each test is expensive El But early efforts more or less did exactly this CS590F Software Reliability Simplifications El To make progress we can either Strengthen our algorithms Weaken our problem El To weaken the problem Selective mutation 00 Don39t try all of the mutants Weak mutation 00 Check only that mutant produces different state after mutation not different final output 00 50 cheaper CS590F Software Reliability Better Algorithms El Observation Mutants are nearly the same as the original program El Idea Compile one program that incorporates and checks all of the mutations simultaneously A socalled metamutant CS590F Software Reliability Metamutant with Weak Mutation El Constructing a metamutant for weak mutation is straightforward El A statement has a set of mutated statements With any updates done to fresh variables XYltlt1X1Yltlt2 X2Ygtgt1 After statement check to see if values differ X X1 X X2 CS590F Software Reliability Comments El A metamutant for weak mutation should be quite practical Constant factor slowdown over original program El Not clear how to build a metamutant for stronger mutation models CS590F Software Reliability Generating Tests El Mutation analysis seeks to generate adequate test sets automatically El Must determine inputs such that Mutated statement is reached Mutated statement produces a result different from original CS590F Software Reliability Automatic Test Generation El This is not easy to do El Approaches Backward approach 00 Work backwards from statement to inputs Take short paths through loops 00 Generate symbolic constraints on inputs that must be satis ed 00 Solve for inputs CS590F Software Reliability Automatic Test Generation Cont El Work forwards from inputs Symbolic execution Tao Program Concrete execution CUTE Arithmetic rep based gupta Linear arith rep of predicate function LetfXYaXbYc T Execute program rzpt of fXY to compute fX Y0 fXoAX o 61 fX0YcAY fXYIf XLZgtO fhen Compute a b amp c as follows a fXovAXYo fXoY0 AX b fXoY0AY fXoo M c fXOo a xo b yD CSS90F Software Reliability Comments on Test Generation El Apparently works well for Small programs Without pointers For certain classes of mutants El 80 not very clear how well it works in general Note Solutions for pointers are proposed CS590F Software Reliability A Problem El What if a mutant is equivalent to the original El Then no test will kill it El In practice this is a real problem Not easily solved 00 Try to prove program equivalence automatically 00 Often requires manual intervention Undermines the metric El How about more complicated mutants CS590F Software Reliability El Mutation analysis is a good idea For all the reasons cited before Also technically interesting And there is probably more to do El How important is automatic test generation Still must manually look at output of tests oz This is a big chunk of the work anyway Weaken the problem oz Directed ATG is a quite interesting direction to go Automatic tests likely to be weird oz Both good and bad CS590F Software Reliability El Testing research community trying to learn From programming languages community 00 Slicing data ow analysis etc From theorem proving community 00 Veri cation conditions model checking CS590F Software Reliability Some Textbook Concepts El About different levels of testing System test Model Test Unit test Integration Test El Black box vs White box Functional vs structural CS590F Software Reliability Boundary Value Test Given Fx1x2 wi rh cons rrain rs a b S S chZSd Boundary Value analysis focuses on The boundary of The inpu r space To iden rify Tes r cases Use inpu r var39iable value a r min jus r above min a nominal value jus r above max and a r max X39l CS590F Software Reliability Next Lecture El Program Slicing CS590F Software Reliability