Finding bugsBug patternsConclusionsUsing Static Analysis to Find BugsDavid HovemeyerApril 28, 2005 — CMSC 433David Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusionsBugs in software•Programmers are smart people•We have good techniques for finding bugs early:•Unit testing, pair programming, code inspections•So, most bugs should b e subtle, and require sophisticate danalysis techniques to find•Right?David Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusions•Apache Ant 1.6.2,org.apache.tools.ant.taskdefs.optional.metamata.MAuditif (out == null) {try {out.close();} catch (IOException e) {}}David Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusions•Eclipse 3.0.1, org.eclipse.update.internal.core.ConfiguredSiteif (in == null)try {in.close();} catch (IOException e1) {}David Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusions•Eclipse 3.0.1,org.eclipse.jdt.internal.debug.ui.JDIModelPresentationif (sig != null ||sig.length() == 1) {return sig;}David Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusions•Eclipse 3.0.1,org.eclipse.jdt.internal.ui.compare.JavaStructureDiffViewerControl c= getControl();if (c == null && c.isDisposed())return;David Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusions•JBoss 4.0.0RC1, org.jboss .cache.TreeCacheint treeNodeSize=fqn.size();if(fqn == null) return null;David Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusionsOne more...David Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusions•J2SE version 1.5 build 63 (released version),java.lang.annotation.AnnotationTyp eMism atchExce ptionpublic String foundType() {return this.foundType();}Written by Josh Bloch, author of Effective JavaDavid Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusions•J2SE version 1.5 build 63 (released version),java.lang.annotation.AnnotationTyp eMism atchExce ptionpublic String foundType() {return this.foundType();}Written by Josh Bloch, author of Effective JavaDavid Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusionsBug-finding tools and techniques•Much research has b e en done on s tatic program analysistechniques to find bugs•Recent research has moved towards increasingly moresophisticated analysis techniques•Our question: what bugs can be found using simple analysistechniques?David Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusionsWhere is the low-hanging fruit?•Bug-driven research: start by looking atreal bugs, then think o f ways to findsimilar bugs•Using simplest possible analysistechniques•Try bug finders on real software•Result: we found a surprising number ofobvious bugs in production softwareDavid Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusionsTalk overviewIn this talk I will•Discuss ways to find bugs in software•Demonstrate that simple static analysis techniques can findlots of bugs in real softwareDavid Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusionsFinding bugs in softwareDavid Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusionsTesting•Run t he program, s ee if it b ehaves c orrectly•Limitations:•Error handling code is difficult to test•Threading bugs can be very hard to reproduce•Test scaffolding is time-consuming to createDavid Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusionsCode inspection•Manually examine source code, lo ok for bugs•Limitations:•Labor intensive•Subjective: source code might appear to be correct when it isis not•Can you spot the typo in this slide?•People have similar blind spots reading source codeDavid Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusionsCode inspection•Manually examine source code, lo ok for bugs•Limitations:•Labor intensive•Subjective: source code might appear to be correct when it isis not•Can you spot the typo in this slide?•People have similar blind spots reading source codeDavid Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusionsStatic analysis•Idea: automated code inspection•Use a program to analyze your program for bugs•Analyze statements, control flow, method calls•Advantages ov er te sting and manual code inspection:•Can analyze many potential program behaviors•Doesn’t get bored•Relatively objectiveDavid Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusionsLimits of static analysis•Nontrivial properties of programs are undecidable“Do e s program P have bug X ?”≡ “Can program P reach state X ?”≡ Halting problem•Static analysis can (in g eneral) never be fully precise, so itmust approximate the b ehavior of the programDavid Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusionsApproximating towards completeness•We could design a bug-finding analysis so that it alwaysoverestimates possible program behaviors•Never misses a bug, but might report some false warnings•Problem: the analysis may report so many false warnings thatthe real bugs cannot b e found!•Trivial version: report a bug at every point in the programDavid Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusionsApproximating towards soundness•We could design a bug-finding analysis so that it alwaysunderestimates possible program b ehaviors•Never reports a false warning, but might miss some real bugs•Problem: analysis may not find as many bugs as we would like•Trivial version: never report any warningsDavid Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusionsHeuristic analysis•A static analysis to find bugs do e s not ne ed to be consistentin its approximations•Neither complete nor sound: miss some real bugs, and reportsome false warnings•This gives the analysis more flexibility to estimate likelyprogram behaviors•May allow the analysis to be more precise in generalDavid Hovemeyer Using Static Analysis to Find BugsFinding bugsBug patternsConclusionsPractical issues•Say your program has 100 real bugs•Would you rather use•A tool that finds all 100 bugs, but reports 1,000,000 warnings•A tool that finds only 25 bugs, but reports 50 warnings•Using a bug-finding
View Full Document
Unlocking...