CS 451 Software Engineering Static AnalysisReferenceStatic AnalysisStatic Analysis (cont’d)About lintAbout lint (cont’d)BackgroundBackground (cont’d)How static analysis worksHow static analysis works (cont’d)How static analysis works (cont’d)FindBugsInfinite Recursive LoopsReturn value ignoredForget to throw an exceptionDereferencing null pointersDereferencing null pointers (cont’d)Dereferencing null pointers (cont’d)Comparing unrelated objectsExperience in practiceExperience in practice (cont’d)Experience in practice (cont’d)Limitations of Static AnalysisIn summary…CS 451Software EngineeringStatic Analysis 1ReferenceMaterial in this lecture references the paper:•N. Ayewah, D. Hovemeyer, J.D. Morgenthaler, J. Penix, W. Pugh, “Using Static Analysis to Find Bugs”, IEEE Software, 25 (5): 22-29, 2008.2Static Analysis•Analyze the program by just examining the source code (that is, the program does not execute).•Look for violations of good programming practices.•Look for specific programming errors.3Static Analysis (cont’d)•First useful and widely-used static analysis program was the Unix program lint for C.•Excellent progress over the last decade with tools becoming fairly sophisticated and supporting multiple different languages.•Static analysis is now considered an important verification method along with reviews/inspections and testing.4About lint“The lint utility attempts to detect features that are likely to be bugs, to be non-portable, or to be wasteful. It also performs stricter type checking than does the C compiler.”•Among the possible problems noted by lint:–Unreachable statements–Loops not entered at the top–Variables declared and not used–Logical expressions whose value is constant5About lint (cont’d)–Functions called with varying numbers of arguments–Function calls that pass arguments of a type other than the type the function expects to receive–Functions whose values are not used 6Background•The Halting problem asks whether the execution of a specific program for a given input will terminate.•The Halting problem is undecidable, that is, there is no algorithm to solve it for all programs and all inputs.•Alan Turing and Alonzo Church independently showed in 1936 that the halting problem is undecidable.7Background (cont’d)•As a result of the halting problem, essentially, predicting almost any program behavior is undecidable   •Examples of undecidable problems–Is a program statement reachable?–Is a path feasible?–Will an array index go out of bounds?–Are two functions equal?8How static analysis works•Although it is not possible to construct a general algorithm for the halting problem for all programs and all inputs,•It is possible to come up with an algorithm that works on some programs for:–some inputs –for all inputs.• The algorithm can say “yes”, “no”, or “not sure”9How static analysis works (cont’d)•For example, it is easy to determine that the program on the left terminates.•As for the program fragment on the right, it depends…function main() function main(){ {int x; while ( )read x; {print x; S1;} }}•F10How static analysis works (cont’d)•In the following case, it can be statically determined that the program will not terminate:function main(){y = 1;while (y > o){y = y +1;}}11FindBugs•An open source static-analysis tool for Java•Developed at the University of Maryland•Motivated by the observation that some Java programs contained blatant mistakes that were detectable with fairly trivial analysis.•Realized that even “production quality” software contained such mistakes, and that even experienced developers made them!•Recognizes ~300 programming mistakes and dubious coding idioms.–Does not try to prove that software does not contain a particular defect12Infinite Recursive Loopspublic String foundType() {return this.foundType();}This code should have been a getter method for the field foundType, but the extra parenthesis means it always recursively call itself until the stack overflows13Return value ignored•s.toLowerCase(), where s is a String.•Because Strings in Java are immutable, the toLowerCase() method has no effect on the String it’s invoked on, but rather returns a new String. •The developer probably intended to write s = s.toLowerCase().14Forget to throw an exceptiontry { ... }catch (IOException e) { new SAXException(....);}Program does not contain any throw statements associated with IOException.15Dereferencing null pointers•Using the wrong relational or Boolean operation (name != null || name.length > 0)Some languages use short circuit evaluation.If the left side is true, the right side does not get evaluated.If the left side is false, the right side will be evaluated leading to a null pointer (since name is null). 16Dereferencing null pointers (cont’d)if (g != null) paintScrollBars(g,colors);g.dispose();•If g is null then the next statement will dereference resulting in a null pointer exception.17Dereferencing null pointers (cont’d)ObjectName var = null;if () define var;If (); use var; •If the body of the first if is not executed, then a null pointer exception will occur.•Hard to tell from analysis whether a program path is feasible •F18Comparing unrelated objects•Finds places in which two objects guaranteed to be of unrelated types are compared for equality (for example, where a StringBuffer is compared to a String).19Experience in practice•FindBugs was used to analyze the official release of Java 1.6.0.•214 out of 379 medium- and high- priority warnings seemed to have either functional impact (176) or substantial functional impact (38).•FindBugs has also been used at Google (two of the authors of the paper work at Google).•Incorporating static analysis in the development process has required a phased approach.20Experience in practice (cont’d)•Phase 1: Automated FindBugs to run over all newly checked-in Java source code and store any generated warning.–Developers used a simple Web interface to check projects for possible bugs and mark false positives.•Phase 2: Two people spent half the time evaluating warnings and creating defect reports, as appropriate.–Created about 1000 defect reports in about 6 months.21Experience in practice (cont’d)•Phase 3: Moved the analysis feedback closer to the development workflow.–Integrated the results of the analysis with the