Coverity Prevent SQS: Java Static Analysis Defect Detection
InfoQ spoke to Coverity CTO Ben Chelf to find the technical details:
we parse all of the bytecode and the corresponding source code to build up our representation of the software system (our Software DNA map). From here, we compute a complete control flow graph for every method and from the entire code base and we build a complete callgraph so that when we are analyzing the code, we know exactly who calls who and where. We use this representation of the code not only for analysis, but also for reporting so that when we discover a defect, we can point you to all the key places in the code that led the particular flaw that we found. As for the actual analysis, that's our secret sauce, but it is based on years and years of research that make our analysis techniques scale to millions of lines of code and report a very few number of false positives.Prevent SQS integrates into a desktop build or continous integration environment where Coverity claims that it scan millions of lines of Java code in a matter of hours. An Eclipse plugin also allows line of code problem-source detection. Some of the bugs it can find include:
- Runtime Exceptions
- Incorrect dereferences of null objects
- Improper use of list operations on arrays
- Improper down-casting of objects into subclass types
- Incorrect use of database connection APIs
- Unexpected Runtime Behavior
- Incorrect use of equality operators and functions
- Missing calls to super class implementations
- Incorrect management of Hibernate transactions
- Performance Degradations such as failure to correctly release resources including file handles, connections, semaphores, and streams
One such check that we perform that relies on this concept identifies places in the code where the developer fails to call the superclass implementation of an overridden method when the majority of overriders do call it. The contract that is implied by the code through its normal behavior of classes and their parents is picked up by Prevent SQS and then used to flag errant behavior. Of course, the user may also inform the system of the contracts that must be checked, but the fact that it can figure out it automatically a lot of times is rather new territory for any type of automatic checking technology.Asked how Coverity was able to transition the expertise they had built in the C/C++ domain to Java, Ben explained:
The ability to cross method boundaries during analysis also allows us to find examples in the code that are not self contained in any basic block or single method. If you call a method that calls a method that calls a method that opens a JDBC connection and then forget to close that connection, we're able to flag that down even if the open is not in the same class as the failure to close. Of course, not all bugs occur on all paths, and due to our path analysis, we're able to identify just the paths that contain defects without a lot of noise.
The underlying analysis techniques are similar -- we use a lot of the same tricks in Java that we do in C/C++ to analyze our representation of the software. One particular analysis feature that we treat a bit differently has to do with virtual method resolution. Since all calls to methods in Java are "virtual" (dynamically looked up based on type), we made sure that we had reasonable algorithms for computing the potential types of objects so that when analyzing code interprocedurallly, we knew where the code would branch at method calls. While virtual methods certainly exist in C++ as well, in practice, they are much less pervasive in most of the real world C++ code that we see out there. As such, the methodology and algorithms we chose for handling these cases are different between the two languages.Ben recommended that Prevent SQS be leveraged as early as possible in the development cycle as is possible, and cited themselves as an example. At Coverity their Java team has Prevent SQS integrated into their automatic build system. They also have it rigged to a big, old-school stop light; from time to time, SQS turns up a bug when one of our developer checks in their code, and the stop light turns from green to red. Our developers also can run it pre-checkin on their desktop with hopes to "avoid the red light of doom."
There are a number of commerical and open source tools in the static analysis space, including FindBugs, the open source analysis tool by Bill Pugh.