Static Analysis Team Project

What the project does

This project's goal is creating an easy-to-use framework to implement static analysis algorithms on Java source code. It uses SootUp under the hood. The results of analyses can then be displayed using the DOT-format.

Why the Project is Useful

This project serves to improve teaching in TU Darmstadt's Static Analysis course. Static Analysis is the act of analysing source code regarding method calls and structure rather than running it to visualize and improve the program's structure. For the students to gain experience in implementing static analysis algorithms on Java code, a suitable framework is required. To this day however, there is no appropriate API for this, as current solutions are too complex to be used in teaching.

Quick start

Every analysis starts with loading a package. The main method already contains a skeleton to run an analysis and generate a graph from the result of the analysis. An analysis is performed in three steps:

1. Call Util.loadPackage() to load a package, consisting of Java classes
2. A different class implements a run method, which receives the loaded package as its argument and optionally a class name or method name, performs the analysis and returns a graph (e.g. a call graph)
3. Render the generated graph to HTML.

For CHA and RTA, this project provides reference implementations to automatically test that a self-written implementation is working. To compare graphs, GraphEquivalency provides some methods for checking and printing differences of graphs.

The code below loads a package called foo and then performs a ReachableAnalysis (see further below). After that the resulting graph is rendered to HTML.

public class Main {
    
    public static void main(String[] args) {
        // load the package
        Package pkg = Util.loadPackage("foo");
        
        // run the analysis
        Graph<String> graph = ReachableAnalysis.run(pkg);
        
        // render the result in HTML
        String dotString = DotFileGenerator.generateDotString(graph);
        DotFileGenerator.writeDotFile("output.dot", dotString);
        DotToHtmlGenerator.embedDotFileInHtml("output.dot", "output.html", "ReachableAnalysisGraph");
        
        // optional: check if the result graph is equivalent 
        // to the graph generated by a reference implementation
        Graph<String> referenceGraph = ReferenceReachableAnalysis.run(pkg);
        if (!GraphEquivalency.isEquivalent(referenceGraph, graph)) {
            System.out.println(GraphEquivalency.differenceToString(referenceGraph, graph));
        }
    }
}

The actual analysis is implemented in the class ReachableAnalysis (the name can be freely chosen). In this case, the analysis analyses the method HaltingProblemDecider.doesThisProgramHalt(...) for unreachable code. After that, a rather trivial graph containing all reachable basic blocks is generated and returned.

public class ReachableAnalysis {
    
    public static Graph<String> run(Package pkg) {
        // we want to analyze a specific method
        JavaClass javaClass = pkg.getClassByName("HaltingProblemDecider");
        Method method = javaClass.getMethodByName("doesThisProgramHalt");

        ControlFlowGraph cfg = method.getControlFlowGraph();
        BasicBlock entry = cfg.getEntryBlock();

        // the cfg has been loaded, now do something with it
        List<BasicBlock> worklist = new ArrayList<>();
        Set<BasicBlock> reachable = new HashSet<>();

        worklist.add(entry);
        while (!worklist.isEmpty()) {
            // retrieve next block to work on
            BasicBlock currentBlock = worklist.remove(0);

            // do some work with the block
            reachable.add(currentBlock);

            // add all not yet visited successors
            for (BasicBlock successor : currentBlock.getSuccessors())
                if (!reachable.contains(successor))
                    worklist.add(successor);
        }

        // do something with the result of the analysis
        Graph<String> graph = new Graph<String>();
        for (BasicBlock basicBlock : reachable) {
            graph.addNode(new Node<>(basicBlock.toString()));
        }
        
        return graph;
    }
    
}

pkg contains all classes of the loaded package. They can be retrieved using pkg.getClasses() or, if a specific class is needed, pkg.getClassByName(...). Each class contains information about name, attributes, methods and inheritance.

Methods contain information on the types of their parameters (but not their names), return type and the method's control flow graph. They can be retrieved using javaClass.getMethods() or javaClass.getClassByName(...). Parameters can be retrieved using method.getParameters(), the order is the same as in the code.

A control flow graph contains all basic blocks and the entry node. Basic blocks contain info on its statements, successors and predecessors. All basic blocks (except the exit block), end with a GotoStatement or a BranchStatement.