Static Analysis on Steroids: Parasoft BugDetective

• Download a printable PDF version of this article

Introduction

There are three main types of software bugs:

• Poorly implemented requirements: The software does not operate as expected because the functionality defined in the requirements was implemented incorrectly.
• Missing or incomplete requirements: The software does not perform necessary operations or handle feasible scenarios because the stakeholders/designers did not anticipate the need for such functionality and did not specify requirements for it, or because the developers failed to implement a specified requirement.
• Confused user: The software was designed in a way that allows confused users to take unexpected paths.

Building a robust regression suite is the best way to identify poorly implemented requirements, and performing negative testing is the best way to identify confused user errors. However, finding missing requirements is difficult because it’s not clear what you are looking for. Flow analysis, which basically analyzes paths through the code without executing it, is the only known automated testing technique that leads you to such problems. For instance, assume that flow analysis identified a NullPointerException in a Java application. If you examine the path that led to the exception and then consider under which conditions the program might end up in the starting point of this problem, you might find a missing requirement— for instance, the exception could be caused by a certain situation which is feasible, but was never anticipated during the design/planning phase. Such problems would not be noticed if testing focused solely on writing tests that verify requirements.

In addition to pointing to missing requirements, flow analysis also can expose construction problems and logical flaws in the application. It is designed to be used as part of a comprehensive regression test suite, which also includes pattern-matching static analysis, unit tests, HttpUnit tests, in-container tests, module tests, and API tests, and any other tests you use to verify the software. Running the complete regression test suite — including flow analysis and all the other tests — automatically and regularly (e.g., every 24 hours) is the most effective way to determine if code modifications/additions introduced new problems, broke existing functionality, or caused unexpected side effects.

This paper examines why and how to add flow analysis to your existing testing strategies. After introducing the general concept and benefits of flow analysis, it explains how flow analysis can be performed using Parasoft BugDetective™ technology, and demonstrates how it can be applied to bolster both your static analysis and unit testing efforts.

Static Code Flow Analysis - Background

The term static code analysis means different things to different people in the software industry. There seems to be two main static analysis approaches: (1) program execution or flow-based analysis and (2) pattern-based analysis. For program execution adherents, static analysis means trying to logically execute the program — sometimes symbolically — to uncover code problems such as memory corruption, leaks, and exceptions. This type of testing largely focuses on identifying code problems without creating test cases. It provides developers with the "instant feedback" they need to quickly address defects and security vulnerabilities on the desktop — while they are still working on the code and it is fresh in their minds — and it prevents defects and vulnerabilities from making their way further downstream in the software development process, which is where they are much more expensive to identify and remediate.

Parasoft Static Analysis and BugDetective Technology

Parasoft’s static analysis technologies support both flow-based static analysis and pattern-based static analysis. Parasoft’s flow-based static analysis technology, called BugDetective, provides effortless early detection of runtime problems and application instabilities (such as NullPointerExceptions, SQL and other injections, resource leaks, and inefficient iterator usage for Java) in paths that span multiple methods, classes, or packages. Parasoft BugDetective technology is available in Parasoft Jtest (for Java code), C++test (for C and C++ code), and .TEST (for .NET code). This paper focuses on BugDetective as it is implemented in Jtest, but the same general concepts and principles apply to all implementations of BugDetective.

By automatically tracing and simulating execution paths through even the most complex applications — those with paths that span multiple methods, classes, and/or packages and contain dozens of sequence calls — BugDetective exposes defects that would be very difficult and time-consuming to find through manual testing or inspections, and would be exponentially more costly to fix if they were not detected until runtime. Using BugDetective, developers can find, diagnose, and fix classes of software errors that can evade pattern-based static analysis and/or unit testing. Exposing these defects early in the software development lifecycle saves hours of diagnosis and potential rework.

BugDetective static analysis has two applications within Parasoft Jtest:

1. It is used as a part of Jtest’s static analysis to identify flow-based defects in the code as described above.
2. It is used in cooperation with Jtest’s unit testing to validate whether exceptions reported in the course of unit testing could actually be triggered by real application paths.

Benefits of Using BugDetective

Using BugDetective, development teams gain the following key benefits:

• Perform more comprehensive testing with existing resources: BugDetective complements other testing techniques by allowing you to find problems that would otherwise require the development, execution, and maintenance of complex test cases. BugDetective investigates various branching possibilities in a program, providing a level of path coverage that is difficult to accomplish with traditional testing. As a result, BugDetective often identifies problems that occur while handling rare situations that are typically not covered during testing. Moreover, if the code functionality changes, you can search for defects in the modified version without updating or regenerating test cases.
• Automatically identify defects that pass through multiple classes: Traditional automated unit test generation helps you identify the defects within a class. This is critical. Most developers have performed thorough testing on a class, corrected all apparent problems, integrated the code, then later encountered problems, such as NullPointerExceptions, that took days to diagnose because they resulted from an obscure or complex execution path that passed through multiple methods or even multiple packages. Using BugDetective, the same problem could be identified in seconds.
• Focus on actual defects and misuses: BugDetective automatically identifies data-dependent or flow-dependent defects with reasonable certainty. In most cases, BugDetective's reported violations indicate actual misuses (as opposed to the possible/hypothetical misuses that might be reported during unit testing). For example, BugDetective would not report a violation for the following code unless there was a method in the source code calling strlen and passing it a null value, but unit testing would report a problem regardless by passing null to the strlen method in the test:

    public int strlen(String str)
    {
        return str.length();
    }

In The Trenches with BugDetective

BugDetective’s unique breed of static analysis determines whether an application’s execution paths match “suspicious behavior” profiles, which are implemented as rules. For each defect found, a hierarchical flow path details the complete execution path that leads to the identified defect, ending with the exact line of code where the bug manifests itself. To reduce the time and effort required to diagnose and correct each problem found, flow path details are supplemented with extensive annotations (for example, a NullPointerException violation description contains annotations describing which variables contain null values at each point in the flow path).

To make the analysis process more flexible and tailored to your unique project needs, some rules can be parameterized. As a result, BugDetective can even be used to detect violations bound to usage of very specific APIs.

Understanding Flow Paths

In the Jtest GUI, each BugDetective violation is represented by a hierarchical flow path that precisely describes the code that leads to the identified problem. Each element in the path is a line of code that is executed during runtime. If a flow path has a call to a method, the element representing that method call is a node whose sub-nodes represent execution flow within the called method. The final element in the execution path is always the point where the bug manifests itself. The complete path is presented in order to explain why there is a bug at the final point.

Flow path elements are marked with icons that help explain exception handling behavior. If a path has a call to a method that happens to throw an exception on that path, the path element corresponding to the method call is marked by a red sphere. This red sphere indicates that the flow proceeds to a catch or finally block instead of proceeding as normal.

Each element in the flow path has a tool tip that describes the variables related to the violation. For example, a NullPointerException violation description contains annotations describing which variables contain null values at each point in the flow path. To view a tool tip for a flow path element, place your cursor over it.

If you want to navigate through the code related to a reported execution path, use the Next Violation Element and Previous Violation Element buttons in the Jtest view toolbar.

Understanding and Accessing the Violation Origin and Violation Point

The violation itself is represented by an execution path with two marked points:

• Violation origin: This is the "source" of the violation. Normally this is the point which is the source of the "bad data." For instance, in the NullPointerException rule, the violation origin is the source of the null value.
• Violation point: This is the point of "bad data" usage which normally results in a bug in the program. For the NullPointerException rule, this is the point where the variable with the null value is dereferenced.

You can easily access the violation origin and violation point by right-clicking a reported violation (the node with the yellow caution icon) and then choosing the appropriate command from the shortcut menu (either Show Violation Origin or Show Violation Point). For example, a "Null pointer exception" rule violation has the commands Show Violation Origin (Point of Null Assignment) and Show Violation Point (NullPointerException Point) in order to help you understand why the exception may occur in the code.

Running BugDetective Static Flow Analysis

In its primary application, BugDetective can be used as a part of Jtest static analysis to statically simulate execution paths through an application and to look for vulnerabilities by analyzing these paths. The depth of the analysis can be decreased for a faster analysis and can be increased for a more thorough and in-depth analysis.

To better understand the types of defects that BugDetective flow analysis can expose, consider how Jtest’s BugDetective analysis can be applied to sample Java classes. One sample class involves a class instance field that can be null (Example 1 – TestField class) and the second one involves the same class with a local variable that can be null (Example 2 – TestLocal class). Both classes call a LocalHelper class. The goal is to demonstrate how BugDetective handles (1) intra-procedural calls, and (2) inter-procedural calls (a) within one class and (b) which cross class boundaries.

Both of the examples contain instance field and local variable variations of the same defects. The methods named falsePositive contain false positives and the methods named truePositive contain true positives.

BugDetective flags the following defects in the two sample files:

X indicates that Jtest BugDetective did not report a violation in the method and √ indicates that Jtest did report a violation in that method.

Example 1

public class TestFields {
    
    Object x;
    TestFields(Object x) {
        this.x = x;
    }
    int falsePositive1(int level) {
        x = null;
        if (level > 0)
            x = new Object();
        if (level > 4)
            return x.hashCode();
        return 0;
    }

    int truePositive1(int level) {
        x = null;
        if (level > 0)
            x = new Object();
        if (level < 4)
            return x.hashCode();
        return 0;
    }
    int falsePositive2(boolean b) {
        x = null;
        if (b)
            x = new Object();
        if (b)
            return x.hashCode();
        return 0;
    }
    int truePositive2(boolean b) {
        x = null;
        if (b)
            x = new Object();
        if (!b)
            return x.hashCode();
        return 0;
    }

    int falsePositive3(boolean b) {
        Object y = null;
        if (x != null)
            y = new Object();
        if (y != null)
            return x.hashCode() + y.hashCode();
        else
            return 0;
    }
    int truePositive3(boolean b) {
           Object y = null;
        if (x != null)
            y = new Object();
        if (y != null)
            return x.hashCode() + y.hashCode();
        else
            return x.hashCode();
    }
    int falsePositive4(boolean a, boolean b) {
           x = null;
        Object y = null;
        if (a) x = "x";
        if (b) y = "y";
        if (y != null)
            return x.hashCode() + y.hashCode();
        else
            return 0;
    }

    int truePositive4(boolean a, boolean b) {
        x = null;
        Object y = null;
        if (a) x = "x";
        if (b) y = "y";
        if (y != null)
            return x.hashCode() + y.hashCode();
        else
            return x.hashCode();
    }
    
    int truePositive5() {
        if (x == null) return x.hashCode();
        return 0;
    }
   
    int truePositive6() {
        if (x == null) {
            Object y = x;
            return y.hashCode();
        }
        return 0;
    }

    int ifalsePositive1(boolean b) {
        x = null;
        if (!b)x = new Object();
        return LocalHelper.helper1(x, b); 
    }

    int itruePositive1(boolean b) {
        x = null;
        if (b) x = new Object();
        return LocalHelper.helper1(x, b);
    }
    
    int itruePositive2() {
        x = null;
        return LocalHelper.helper2(x);
    }

    int itruePositive3(boolean b) {
        x = null;
        if (b) x = "x";   
        return LocalHelper.helper3(x);
    }
    
}

Example 2

public class TestLocal {

    int falsePositive1(int level) {
        Object x = null;
        if (level > 0)
            x = new Object();
        if (level > 4)
            return x.hashCode();
        return 0;
    }

    int truePositive1(int level) {
        Object x = null;
        if (level > 0)
            x = new Object();
        if (level < 4)
            return x.hashCode();
        return 0;
    }

    int falsePositive2(boolean b) {
        Object x = null;
        if (b)
            x = new Object();
        if (b)
            return x.hashCode();
        return 0;
    }

    int truePositive2(boolean b) {
        Object x = null;
        if (b)
            x = new Object();
        if (!b)
            return x.hashCode();
        return 0;
    }

    int falsePositive3(Object x, boolean b) {
        Object y = null;
        if (x != null)
            y = new Object();
        if (y != null)
            return x.hashCode() + y.hashCode();
        else
            return 0;
    }

    int truePositive3(Object x, boolean b) {
           Object y = null;
        if (x != null)
            y = new Object();
        if (y != null)
            return x.hashCode() + y.hashCode();
        else
            return x.hashCode();
    }

    int falsePositive4(boolean a, boolean b) {
           Object x = null;
        Object y = null;
        if (a) x = "x";
        if (b) y = "y";
        if (y != null)
            return x.hashCode() + y.hashCode();
        else
            return 0;
    }

    int truePositive4(boolean a, boolean b) {
        Object x = null;
        Object y = null;
        if (a) x = "x";
        if (b) y = "y";
        if (y != null)
            return x.hashCode() + y.hashCode();
        else
            return x.hashCode();
    }
    
    int truePositive5(Object x) {
        if (x == null) {
            return x.hashCode();
        }
        return 0;
    }
   
    int truePositive6(Object x) {
        if (x == null) {
            Object y = x;
            return y.hashCode();
        }
        return 0;
    }

    int ifalsePositive1(boolean b) {
        Object x = null;
        if (!b) x = new Object();
        return LocalHelper.helper1(x, b); 
    }

    int itruePositive1(boolean b) {
        Object x = null;
        if (b) x = new Object();
        return LocalHelper.helper1(x, b);
    }
    
    int itruePositive2() {
        return LocalHelper.helper2(null);
    }

    int itruePositive3(boolean b) {
        Object x = null;
        if (b) x = "x";   
        return LocalHelper.helper3(x);
    }

}

public class LocalHelper {
    
//     Bug when x is null and b is false
    public static int helper1(Object x, boolean b) {
        if (b) return 0;
        return x.hashCode();
    }

    public static int helper2(Object x) {
        return x.hashCode();
    }
    
    public static int helper3(Object x) {
        return x.hashCode();
    }

}

Taking a closer look at the results, notice that BugDetective flagged no false positives in these examples. As Parasoft was developing BugDetective, one of our main goals was to ensure that the level of noise (with respect to reporting of false positives) was minima l— even if this meant that fewer defects would be reported. In this specific case, all ten of the false positives were not reported; this is a very good result, and it shows how this design decision manifests itself in BugDetective.

Along those lines, BugDetective considers the defects in the truePositive3 method to be false positives even though other technologies may report them as true errors.

Consider the following code from the TestFields class:

Object x; //NPE origin

TestFields(Object x) {
    this.x = x;
}

int truePositive3(boolean b) {
       Object y = null;
        if (x != null)
            y = new Object();
        if (y != null)
            return x.hashCode() + y.hashCode();
        else
            return x.hashCode(); //NPE
}

The instance variable x is initially initialized to null, but it gets reassigned to the value of argument x in the constructor call.

Jtest BugDetective does not flag this violation because when simulating execution paths through the code, it sees a potential violation point on the path (the line marked with //NPE) but it does not see a path from the violation origin statement (the line marked with //NPE origin) to that line without going through a constructor. Jtest BugDetective does not flag this violation because it didn't find a path in the source code that contains the following sequence of steps:

TestFields tf = new TestFields();
tf.truePositive3(true|false);

Nor did it find a path such as this:

TestFields tf = new TestFields(null);
tf.truePositive3(true|false);

However, assume that the following method is added to the TestFields class:

void callerTruePositive3() {
    TestFields tf = new TestFields(null);
tf.truePositive3(true);

}

Jtest BugDetective now flags this violation since it sees the violation origin and violation point, as well as a code path that leads from one to the other. If the callerTruePositive3 method is not in the code, Jtest would not flag the violation in truePositive3 unless it was assuming that the field x can possibly be null (rather than looking for the explicit path). If you enable an extra configuration option for Jtest BugDetective’s Avoid NullPointerExceptions rule, BugDetective will make this assumption and flag the violation; however, this option is not enabled by default since it flags what we consider to be false positives.

Moreover, even though BugDetective does not flag this violation by default, Jtest’s unit testing will report this defect as a unit testing defect; code similar to that in the callerTruePositive3 method exists in Jtest’s automatically-generated JUnit test case for the truePositive3 method. This is discussed in the following section.

Using BugDetective in Cooperation with Jtest Unit Testing

BugDetective can also be used to check whether reported exceptions could actually be triggered by real application paths. If a reported exception is validated by BugDetective, its severity level is elevated, and it is specially marked in the Jtest view. This helps users determine whether reported exceptions are “real defects.”

If you configure Jtest to validate exceptions with BugDetective, Jtest will automatically collect the runtime exceptions reported from test case execution, then use BugDetective to try to determine if they can really occur when the code is executed.

For example, assume that you have an application A which has a module M with a class C. Also assume that when Jtest automatically generated unit test cases for each of the classes in the application, Jtest's test cases for class C revealed a number of runtime exceptions. Each of these exceptions could indicate one of two things:

• There is a defect in class C because it should properly handle the input supplied by the test case.
• Class C is not designed to handle data supplied by the test case and should not be passed that data.

With exception validation enabled, Jtest can distinguish between these two categories of reported exceptions. This way, you can instantly tell if a reported exception is a real defect— without having to ana¬lyze the code.

The value of the cooperation between BugDetective and Jtest unit testing is highlighted in the following four scenarios:

• Exceptions reported by unit testing will be filtered out when BugDetective cannot find a path in the actual code where the test case conditions could really occur. At the same time, it will raise the severity of reported unit testing exceptions if it can find an actual path in the code that validates that exception.
• BugDetective flags a false positive, but the false positive is filtered out during unit testing due to a lack of confirming unit tests.
• Unit testing points to suspicious places in the code, and BugDetective (based on that information) performs a more exhaustive analysis of those places than it would in a regular BugDetective run. This allows Jtest to find more defects than would have detected by BugDetective alone.

BugDetective finds violation paths that it cannot determine whether to report (according to its heuristics), but then these defects are reported because unit testing flags the same paths.

Unit testing exceptions that were validated with BugDetective will be marked with a red shadow in the Jtest view, and their severity level will also be elevated by the degree specified in the Test Configuration’s Execution> Severities tab. This allows customers to configure reporting of exceptions to suit their own environment and applications.

Unit testing exceptions validated by BugDetective point to actual defects, and should be corrected. Exceptions that were checked with BugDetective, but not validated, indicate that the class is not designed to handle the data that was supplied by the test case and should not be passed that data. Contracts should be added to specify that such data is not permitted.

BugDetective Promotes Exceptions Reported by Unit Testing

Example 3

public class SimpleNeverHappenedAndNotAcknowledgeByBD {
    
    private class Name { 
        String _name;
        
        Name (String name) { 
            _name = name;
        } 
        
        public String toString() { 
            return _name;
        } 
    } 
    
    Name _objectName; 
        
    public String getName () { 
        return _objectName.toString(); 
    } 
    
    void initialize (String name) { 
        _objectName = new Name (name); 
    } 

    /**
    public static void main(String[] args) { 
        SimpleNeverHappenedAndNotAcknowledgeByBD obj = 
        new SimpleNeverHappenedAndNotAcknowledgeByBD(); 
        System.out.println(obj.getName()); //NPE 
    } */

}

Example 3 demonstrates how exceptions reported by unit testing are promoted by BugDetective. First, we ran the built-in “BugDetective” Test Configuration on Example 3, then we ran the built-in “Generate and Execute Unit Tests” Test Configuration, then we ran a user-defined “Generate and Execute Unit Tests” Test Configuration that had BugDetective validation enabled.

With the code in the main() method commented out, BugDetective does not report any defects because there is no place in the code where getName() is called before initialize() is called.

When unit testing is performed with the built-in “Generate and Execute Unit Tests” Test Configuration, Jtest reports one java.lang.NullPointerException. The test case for the NullPointerException is:

public void testGetName5() throws Throwable { 
SimpleNeverHappenedAndNotAcknowledgeByBD testedObject = 
    new SimpleNeverHappenedAndNotAcknowledgeByBD(); 
String result = testedObject.getName(); 
// NullPointerException thrown 
// at example.A.SimpleNeverHappenedAndNotAcknowledgeByBD.getName
(SimpleNeverHappenedAndNotAcknowledgeByBD.java:36) 
// jtest_unverified 
}

When unit testing is performed with the user-defined “Generate and Execute Unit Tests” Test Configuration with BugDetective validation enabled, Jtest reports exactly the same results. In this case, that is expected. Since BugDetective found no violation paths in this example, no unit testing exceptions could be promoted.

Now, let’s repeat the same test with the main() method uncommented. BugDetective alone reports a possible NullPointerException on line 13, which is marked with // NPE. Unit testing with the built-in “Generate and Execute Unit Tests” Test Configuration generates two more test cases — one of which causes another NullPointerException. That test case is listed below.

public void testMain1() throws Throwable { 
String[] strings = new String[] {}; 
SimpleNeverHappenedAndNotAcknowledgeByBD.main(strings); 
// NullPointerException thrown 
// at example.A.SimpleNeverHappenedAndNotAcknowledgeByBD.getName(
//     SimpleNeverHappenedAndNotAcknowledgeByBD.java:36) 
// at example.A.SimpleNeverHappenedAndNotAcknowledgeByBD.main(
//     SimpleNeverHappenedAndNotAcknowledgeByBD.java:50) 
// jtest_unverified 
} 

Running unit testing with the user-defined “Generate and Execute Unit Tests” Test Configuration with BugDetective validation enabled indeed increases the severity of both unit test cases that were reporting NullPointerExceptions. In each case, this is because BugDetective finds an actual path leading to the NullPointerException. In a large code base, this promotion process would typically make it significantly easier to zero in on the real bugs and focus resources accordingly.

Unit Testing and BugDetective in Cooperation Filter Out Exceptions Reported by BugDetective

Example 4

public class BDBogusNotApprovedByUT {
    
    private boolean B = true; 
    BDBogusNotApprovedByUT() { 
        B = false; 
    } 
    
    public void test() { 
        Object o = null; 
        if (B) { 
        o.toString(); //NPE 
        } 
        else { 
    // we should go into this method (violation search method analysis guide) 
    // CallFromAnotherFile.methodWithNpe(o); 
        } 
    }
}

One could argue about the value of BugDetective filtering, since BugDetective was already catching this NullPointerException. Therefore let’s look at an example (Example 4) in which BugDetective reports a false positive on its own, but no defects are reported when BugDetective works in cooperation with unit testing.

BugDetective triggers a warning on line 17, which is marked with //NPE. This is because BugDetective can see that field B is set to true and it does not realize that the default constructor sets field B to be false before the test() method is called.

Unit testing on its own does not report any exceptions, and hence unit testing with BugDetective validation enabled does not report any exceptions either. Therefore, even though BugDetective by itself reports this false positive, it is filtered out when BugDetective works in cooperation with unit testing. This is a very simple example and one can claim that such a case should be fixed. Perhaps — but there are many possibilities where BugDetective’s heuristics can make a mistake and report a false positive. In such cases, unit testing can successfully be used to either validate or filter out these exceptions.

Conclusion

The unique breed of flow analysis that BugDetective provides helps software development teams find critical runtime bugs without executing code, as well as validate whether exceptions exposed by unit test cases are “real bugs” that could actually surface in the field. BugDetective exposes bugs that would often evade pattern-matching static analysis and unit testing, yet would be very difficult and time-consuming to find through manual testing or inspections

When BugDetective is applied as part of a comprehensive regression test suite that also includes pattern-matching static analysis, unit testing, in-container testing (for Java), API testing, module testing, and so forth, it helps development teams to:

• Modify existing code quickly, and with confidence: By enabling teams to quickly build a regression safety net that will expose defects immediately upon introduction and determine if code modifications break existing functionality — even if the team has a large existing code base with no tests or minimal tests.
• Control development costs and schedules: By exposing errors as early as possible, which is when they are fastest and cheapest to fix, and by testing a broad range of potential user paths to uncover difficult-to-find problems that could delay releases or require post-release patches.
• Optimize development resources: By automatically vetting approximately 80% of coding issues so developers can spend less time on line-by-line inspections and debugging, and more time on design, algorithms, and implementation.
• Leverage the power of the latest technologies while controlling their risks: By reducing the difficulty of testing complex enterprise applications (such as SOA/Web services and Java EE applications).
• Gain instant visibility into Java code's quality and readiness: By providing on-demand objective code assessments and tracks progress towards quality and schedule targets.

Parasoft Corporation

For 20 years, Parasoft has investigated how and why software errors are introduced into applications. Our solutions leverage this research to deliver quality as a continuous process throughout the SDLC. This promotes strong code foundations, solid functional components, and robust business processes. Whether you are delivering Service-Oriented Architectures (SOA), evolving legacy systems, or improving quality processes—draw on our expertise and award-winning products to increase productivity and the quality of your business applications. For more information, visit the Parasoft homepage.

• Download a printable PDF version of this article