1Class 12• Questions about project• Assign (see Schedule for links)• Project proposal• Initial: due by e-mail 9/22/09• Final: due (written, 2 pages) 9/29/092Complex Data StructuresComplex Data Structuresy Arrays, structs, objectsy How to handle them in analysis (pointer, data-flow, …)?Example:1. struct Bar {2. int x;3. int y;4. };5. main() {6. struct Bar b; 7. b.x = read();8. print(b.y);9. }What is Def(7)?What is Use(8)?Depends on how entities are consideredAs a whole:Def(7) = {b}Use(8) = {b}Æ spurious du pairDistinguishing fieldsDef(7) = {b.x}Use(8) = {b.y}Complex Data Structuresy Arrays, structs, objectsy How to handle them in analysis (pointer, data-flow, …)?Example:1. struct Bar {2. int x;3. int y;4. };5. main() {6. struct Bar b; 7. b.x = read();8. print(b.y);9. }What is Def(7)?What is Use(8)?Depends on how entities are consideredAs a whole:Def(7) = {b}Use(8) = {b}Æ spurious du pairDistinguishing fieldsDef(7) = {b.x}Use(8) = {b.y}5Dynamic AnalysisDynamic Analysisy Definitionsy Comparison to static analysisy Need for dynamic analysisy Problemsy ExamplesStatic vs. Dynamic Analysisy Static analyses derives information about a product from an overall model of the product (without execution)y Results in definitive information about the product that holds for all inputsy Dynamic analyses gathers information about the product through instrumentation, actual execution, or simulated executiony Results in sampling information about the product that holds for those inputs sampledStatic vs. Dynamic Analysisy Static analyses y Intraproceduraly AST, control-flow, control-dependence, data-flow, etc.y Complicating factorsy Interprocedural, recursion, pointersy Slicing, demand analysisy Applications y Dynamic analyses y Instrumentation, profilingy Dynamic versions of control-flow, assertions, etc.y Applications such as testing, debugging,y Combinations of static and dynamic analysesEven if Proof of Correctness...y Need to test specifications and assumptions about the environmenty Need to determine performance in practice y Need to test for qualities such as usability, effectiveness of documentationy Need to simulate the execution of some systems (but limited)y Etc.Thus, dynamic analysis is necessary.Major Problemsy How do you instrument (insert probes) in an efficient way so as not to incur “too much” overhead?y How do you make sure that the probes don’t change the behavior of the system?y How do you select the inputs (test cases) for the analysis?y How do you know if the test cases are “adequate”?y How do you compare dynamic methods?y How do you know when to stop analyzing?Examples of Dynamic Analysisy Assertionsy Error seedingy Coverage criteriay Fault-based testingy Specification-based testingy Object-oriented testingy Regression testingy Invariant detection12Testing BasicsWhat is Testing?Testing: To execute a program with a sample of the input datay Dynamic technique: program must be executedy Optimistic approximationy The program under test is exercised with a (very small) subset of all the possible input datay We assume (hope) that the behavior with any other input is consistent with the behavior shown for the selected subset of input datay The opposite of conservative (pessimistic) analysisGoals of Testingy Improve software quality by finding errors“A test is successful if the program fails”(Goodeneogh, Gerhart, “Toward a Theory of Test Data Selection”, IEEE Transactions on Software Engineering, Jan. 85)Goals of Testingy Improve software quality by finding errors“A test is successful if the program fails”(Goodeneogh, Gerhart, “Toward a Theory of Test Data Selection”, IEEE Transactions on Software Engineering, Jan. 85)y Provide confidence in the dependability of the software product(A software product is dependable if it is consistent with its specification.)Testing TechniquesThere exists a number of techniquesy Different processesy Different artifactsy Different approachesThere are no perfect techniquesy Testing is a best-effort activityThere is no best techniquey Different contextsy Complementary strengths and weaknessesy Trade-offsVerification and Validationy Validation: Are we building the right product?To what degree the software fulfills its (informal) requirements? y Verification: Are we building the product right?To what degree the implementation is consistent with its (formalor semi-formal) specification?SystemFormal or semi-formal descriptionsValidation(usability, feedback from users, …)V e r i f i c a t i o n(testing, inspections, static analysis, …)ActualneedsDependabilityCorrectnessAbsolute consistency with a specificationReliabilityLikelihood of correct behavior in expected useRobustnessAbility of software systems to function even in abnormal conditionsSafetyAbility of the software to avoid dangerous behaviorsThe Problem of VerificationThe halting problem is not a purely theoretical resulty Most interesting properties of programs’ behavior can be reduced to the halting problemy Verification is almost always an undecidable problemWe must accept inaccuracy!But, what if we exhaustively test our program?Exhaustive Testing?How long would it take (approximately) to test exhaustively the following program?int sum(int a, int b) {return a + b;}Assume int is 32 bits, how many tests would you need?Exhaustive Testing?How long would it take (approximately) to test exhaustively the following program?int sum(int a, int b) {return a + b;}y 232x 232= 264=~ 1019testsy Assume 1 test per nanosecond (109tests/second)y we get 1010seconds…Assume int is 32 bits, how many tests would you need?Exhaustive Testing?How long would it take (approximately) to test exhaustively the following program?int sum(int a, int b) {return a + b;}y 232x 232= 264=~ 1019testsy Assume 1 test per nanosecond (109tests/second)y we get 1010seconds…y About 600 years!Assume int is 32 bits, how many tests would you need?Exhaustive Testing is Impossible“Many new testers believe thaty they can fully test each program, andy with this complete testing, they can ensure that the program works correctly.On realizing that they cannot achieve this mission, many testers become demoralized. [...] After learning they can’t do the job right, it takes some testers a while to learn how to do the job well.”(C. Kaner, J. Falk, and H. Nguyen, “Testing Computer Software”, 1999)Failure, Fault, ErrorFailureObservable incorrect behavior of a program. Conceptually related to the