Improving Software Quality with Static AnalysisWilliam PughProfessor, Univ. of Marylandhttp://www.cs.umd.edu/~pugh24Static Analysis•Analyzes your program without executing it•Doesn’t depend on having good test cases•or even any test cases•Generally, doesn’t know what your software is supposed to do•Looks for violations of reasonable programming•Shouldn’t throw NPE•Shouldn’t allow SQL injection•Not a replacement for testing•Very good at finding problems on untested paths•But many defects can’t be found with static analysis3Common Wisdom about Bugs and Static Analysis•Programmers are smart•Smart people don’t make dumb mistakes•We have good techniques (e.g., unit testing, pair programming, code inspections) for finding bugs early•So, bugs remaining in production code must be subtle, and finding them must require sophisticated static analysis techniques•I tried lint and it sucked: lots of warnings, few real issues4Can You Find The Bug? if (listeners == null) listeners.remove(listener);•JDK1.6.0, b105, sun.awt.x11.XMSelection•lines 243-244Why Do Bugs Occur?•Nobody is perfect•Common types of errors:•Misunderstood language features, API methods•Typos (using wrong boolean operator, forgetting parentheses or brackets, etc.)•Misunderstood class or method invariants•Everyone makes syntax errors, but the compiler catches them•What about bugs one step removed from a syntax error?6Bug Categories•Correctness - the code seems to be clearly doing something the developer did not intend•Bad practice - the code violates good practiceSelected categories for today's discussion7Bug Patterns•Some big, broad and common patterns•Dereferencing a null pointer•An impossible checked cast•Methods whose return value should not be ignored•Lots of small, specific bug patterns, that together find lots of bugs•Every Programming Puzzler•Every chapter in Effective Java•Many postings to http://thedailywtf.com/8Analysis Techniques•Local pattern matching•If you invoke String.toLowerCase(), don’t ignore the return value•Intraprocedural dataflow analysis•Null pointer, type cast errors•Interprocedural method summaries•This method always dereferences its parameter•Context sensitive interprocedural analysis•Interprocedural flow of untrusted data•SQL injection, cross site scriptingWhatever you need to find the bugs9Infinite recursive loop•Student came to office hours, was having trouble with his constructor:/** Construct a WebSpider */public WebSpider() { WebSpider w = new WebSpider(); }•A second student had the same bug•Wrote a detector, found 3 other students with same bug... Students are good bug generators10Double Check Against JDK1.6.0-b13•Found 5 infinite recursive loops•Including one written by Joshua Bloch public String foundType() { return this.foundType(); }•Smart people make dumb mistakes•27 across all versions of JDK, 40+ in Google’s Java code•Embrace and fix your dumb mistakes11Finding Null Pointer Bugs with FindBugs •FindBugs looks for a statement or branch that, if executed, guarantees a null pointer exception•Either a null pointer exception could be thrown, or the program contains a statement/branch that can’t be executed•Could look for exceptions that only occur on a path•e.g., if the condition on line 29 is true and the condition on line 38 is false, then a NPE will be thrown•but would need to worry about whether that path is feasible12Null Pointer Bugs Found by FindBugs•109 statements/branches that, if executed, guarantee NPE•We judge at least 54 of them to be serious bugs that could generate a NPE on valid input•Most of the others were deemed to be unreachable branches or statements, or reachable only with erroneous input•Only one case where the analysis was wrongJDK1.6.0-b10513Examples of null pointer bugs//com.sun.corba.se.impl.naming.cosnaming.NamingContextImplif (name != null || name.length > 0)//com.sun.xml.internal.ws.wsdl.parser.RuntimeWSDLParserif (part == null | part.equals(""))// sun.awt.x11.ScrollPanePeerif (g != null) paintScrollBars(g,colors);g.dispose();simple ones14Redundant Check For Null•Checking a value to see if it is null•When it can't possibly be null // java.awt.image.LoopupOp, lines 236-247public final WritableRaster filter( Raster src, WritableRaster dst) { int dstLength = dst.getNumBands(); // Create a new destination Raster, // if needed if (dst == null) dst = createCompatibleDestRaster(src); Also known as a reverse null dereference error15Redundant Check For Null• Check the JavaDoc for the method•Performs a lookup operation on a Raster.•If the destination Raster is null,•a new Raster will be created.•Is this case, a bug•particularly look for those cases where we know it can't be null because there would have been a NPE if it were nullIs it a bug or a redundant check?16Bad Method Invocation•Methods whose return value shouldn't be ignored•Strings are immutable, so functions like trim() and toLowerCase() return new String•Dumb/useless methods•Invoking toString or equals on an array•Lots of specific rules about particular API methods•Hard to memorize, easy to get wrong17Examples of bad method calls// com.sun.rowset.CachedRowSetImplif (type == Types.DECIMAL || type == Types.NUMERIC) ((java.math.BigDecimal)x).setScale(scale);// com.sun.xml.internal.txw2.output.XMLWritertry { ... }catch (IOException e) { new SAXException("Server side Exception:" + e); }18Type Analysis•Impossible checked casts•Useless calls•equals takes an Object as a parameter•but comparing a String to StringBuffer with equals(...) is pointless, and almost certainly not what was intended•Map<K,V>.get also takes an Object as a parameter•supplying an object with the wrong type as a parameter to get doesn't generate a compile time error•just a get that always returns null19Lots of Little Bug Patterns•checking if d == Double.NaN•Bit shifting an int by a value greater than 31 bits•Every Puzzler this year•more than half for most years20When Bad Code Isn't A Bug•Static analysis tools will sometimes find ugly, nasty code•that can't cause your application to misbehave•Cleaning this up is a good thing•makes the code easier to understand and maintain•But for ugly code already in production•sometimes you just don't want to touch it•We've found more cases like this than we expected21When
View Full Document
Unlocking...