Static AnalysisPrinciples of Software System ConstructionJonathan AldrichSome slides from Ciera JaspanFind the Bug!disable interruptsSource: Engler et al., Checking System Rules Using System-Specific, Programmer-Written Compiler Extensions, OSDI ’00.29 November 201115-214: Principles of Software System Construction2disable interruptsre-enable interruptsERROR: returningwith interrupts disabledLimits of Inspection• People• …are very high cost• …make mistakes• …have a memory limitSo, let’s automate inspection!29 November 2011 315-214: Principles of Software System ConstructionMetal Interrupt Analysisis_enableddisableenableenable =>err(double enable)Source: Engler et al., Checking System Rules Using System-Specific, Programmer-Written Compiler Extensions, OSDI ’00.is_disableddisable =>err(double disable)end path =>err(end pathwith/intrdisabled)29 November 2011 415-214: Principles of Software System ConstructionApplying the Analysisinitial state is_enabledSource: Engler et al., Checking System Rules Using System-Specific, Programmer-Written Compiler Extensions, OSDI ’00.29 November 201115-214: Principles of Software System Construction5transition to is_disabledtransition to is_enabledfinal state is_enabled is OKfinal state is_disabled: ERROR!Empirical Results on Static Analysis• InfoSys study [Chaturvedi 2005]– 5 projects– Average 700 function points each– Compare inspection with and without static analysisAdapted from [Chaturvedi 2005]• Conclusions– Fewer defects– Higher productivity29 November 2011 615-214: Principles of Software System ConstructionStatic Analysis Finds “Mechanical” Errors• Defects that result from inconsistently following simple, mechanical design rules• Security vulnerabilities– Buffer overruns, unvalidated input…• Memory errors– Null dereference, uninitialized data…• Resource leaks–Memory, OS resources…–Memory, OS resources…• Violations of API or framework rules– e.g. Windows device drivers; real time libraries; GUI frameworks• Exceptions– Arithmetic/library/user-defined• Encapsulation violations– Accessing internal data, calling private functions…• Race conditions– Two threads access the same data without synchronization29 November 201115-214: Principles of Software System Construction7Outline• Why static analysis?– Automated– Can find some errors faster than people– Can provide guarantees that some errors are found• How does it work?•What are the hard problems?•What are the hard problems?• How do we use real tools in an organization?29 November 2011 815-214: Principles of Software System ConstructionOutline• Why static analysis?• How does it work?– Systematic exploration of program abstraction– Many kinds of analysis• AST walker•Control-flow and data-flow•Control-flow and data-flow• Type systems• Model checking– Specifications frequently used for more information• What are the hard problems?• How do we use real tools in an organization?29 November 2011 915-214: Principles of Software System ConstructionAbstract Interpretation• Static program analysis is the systematic examination of an abstraction of a program’s state space• Abstraction– Don’t track everything! (That’s normal interpretation)– Track an important abstraction•Systematic•Systematic– Ensure everything is checked in the same way• Let’s start small…29 November 2011 1015-214: Principles of Software System ConstructionA Performance AnalysisWhat’s the performance problem?public foo() {=logger.debug(“We have ” + conn + “connections.”);}public foo() {=if (logger.inDebug()) {logger.debug(“We have ” + conn + “connections.”);}Seems minor=but if this performance gain on 1000 servers means we need 1 less machine,we could be saving a a lot of moneylogger.debug(“We have ” + conn + “connections.”);}}29 November 2011 1115-214: Principles of Software System ConstructionA Performance Analysis• Check that we don’t create strings outside of a Logger.inDebug check• Abstraction– Look for a call to Logger.debug()– Make sure it’s surrounded by an if (Logger.inDebug())•Systematic•Systematic– Check all the code• Known as an AST walker– Treats the code as a text file– Ignores control flow, variable values, and the heap– Code style checkers work the same way• you should never be checking code style by hand– Simplest static analysis: grep29 November 2011 1215-214: Principles of Software System ConstructionAn interrupt checker• Check for the interrupt problem• Abstraction– 2 states: enabled and disabled– Program counter• Systematic–Check all paths through a function–Check all paths through a function• Error when we hit the end of the function with interrupts disabled• Known as a control flow analysis– More powerful than reading it as a raw text file– Considers the program state and paths29 November 2011 1315-214: Principles of Software System ConstructionAdding branching• When we get to a branch, what should we do?– 1: explore each path separately• Most exact information for each path• Leads to an exponential state explosion– 2: join paths back together• Less exact• But no state explosion• Not just conditionals!– Loops, switch, and exceptions too!29 November 2011 1415-214: Principles of Software System ConstructionExample: Bad1. int foo() {2. unsigned long flags;3. int rv;4. save_flags(flags);5. cli();6. rv = dont_interrupt();7. if (rv > 0) {8.do_stuff();Abstraction (before statement)2-4: enabled5: enabled6: disabled7: disabled8: disabled9: disabled8.do_stuff();9. restore_flags();10. } else {11. handle_error_case();12. }13. return rv;14. }9: disabled11: disabled13: unknownError: did not reenable interrupts on some path29 November 2011 1515-214: Principles of Software System ConstructionA null pointer checker• Prevent accessing a null value• Abstraction– Program counter– 3 states for each variable: null, not-null, and maybe-null• Systematic–Explore all paths in the program (as opposed to all paths in the –Explore all paths in the program (as opposed to all paths in the method)• Known as a data-flow analysis– Tracking how data moves through the program– Very powerful, many analyses work this way– Compiler optimizations were the first29 November 2011 1615-214: Principles of Software System ConstructionExample: Bad1. int foo() {2. Integer x = new Integer(6);3. Integer y