EDA045F Program Analysis: Homework 1

Please try to track the time that you need for the homework assignment and report it, so that we can calibrate the effort for future classes.

Dataflow Analysis 1

This is a group project and intended to be worked on in a team of two. If you have no partner, you can also submit alone.

Background

In this excerise, you will work with the Soot framework to develop a small number of program analyses, including two dataflow analyses.

Soot already provides its own framework for dataflow analysis, but in this exercise we will only use Soot for access to its intermediate representation.

To validate your analyses, you will use a test suite that we provide. I recommend that you also test on some custom tests, too, as that may make it easier for you to trigger specific behaviour in the analysis.

For the analyses below, you may disregard the semantics of parameter-passing, method calls, exception handling, and field accesses. You must consider accesses to local variables.

Compatibility note: We are using Soot 3.1.0. This version of Soot supports Java 8, but no later versions of Java (the Soot team has an unreleased in-development version with support for Java 9 that we will not be using for this class). Make sure that you are compiling and running your Java code with Java 8, not with a later version.

Resources

Soot 3.1.0: [jar]
Soot 3.1.0 packaged documentation: [jar]
Soot 3.1.0a (3.1.0 without dead assignment elimination): [jar] (You can use this to test exercise 4 more easily)
JUnit 3.8.2: [jar] (used by some of the benchmarks)
Stub program: [java] Updated: v3 fixes two small but annoying bugs
Recommended starting point for implementing your own analysis.

Test suite:

Binary	Source	Description
EDAN045F-0.jar	EDAN045F-0-src.tar.gz	EDAN045F-0: Small sample programs (tiny)
javacc-5.0.jar	javacc-5.0-src.tar.gz	The JavaCC compiler generator (small)
bouncycastle-160.jar	bouncycastle-160-src.tar.gz	Bouncy Castle: Java Cryptography API (medium)

Use these files to test your analysis. Note that there is no `ground truth' available; you will have to check the source code to convince yourself that your analysis produces sensible output.

Soot documentation: [HTML] (local copy)
Soot survivor's guide: [pdf] (local copy, this is for an older version of Soot but still provides a helpful overview. Sections 1–4 are recommended reading for this exercise.)
Java language specification: [HTML] [PDF]

Using Soot

Since you are most likely new to Soot, I recommend that you use the stub program listed above to start implementing your analysis. If you rename it to MyMainClass and compile it (linking against Soot), you should be able to run your analysis on all classes in bin.jar as follows:

java MyMainClass -cp <soot-classpath> -process-dir ./bin.jar

where <soot-classpath> is the classpath of all classes that Soot needs to know about; this typically includes your Java's standard library: rt.jar. For example, I use:

java MyMainClass -cp ./bin.jar:/opt/jdk1.8.0_144/jre/lib/rt.jar:junit.jar:/opt/jdk1.8.0_144/jre/lib/jce.jar -process-dir ./bin.jar

(check the reosurces for a copy of junit.jar if you don't already have it on your system.)
Note that the Soot classpath is fundamentally different from the CLASSPATH environment variable (the Java classpath) that you can use to tell Java which libraries to use:

Java classpath (CLASSPATH=..., or alternatively java -cp ...): This tells the JVM what classes to make available to the Java run-time. For instance, you always want to include soot-3.1.0.jar, but usually not the program that you want to analyse.
Soot classpath (java MyMainClass -cp ...): This tells Soot what classes you want to be available to the analysis. For instance, if you want to analyse bouncycastle-160.jar, you will list that jar file here. You will not usually include soot-3.1.0.jar in the Soot classpath (unless you want to use Soot to analyse Soot itself, but we're not doing that in this exercise). This classpath must contain a superset of the classes that you actually want to analyse; for instance, it will include java.lang.Object, because this class is the superclass of all other classes and thus needed for any analysis even if you don't request the analysis of java.lang.Object itself.

To run on a single class that is in your Soot classpath, run:

java MyMainClass -cp <soot-classpath> MyClass

For debugging, you can ask Soot to output Jimple intermediate code by running:

java MyMainClass -f j -cp <soot-classpath> MyClass

This will generate the file sootOutput/MyClass.jimple, containing intermediate Jimple code. Try running Soot with -h for a more complete list of options.

Submission

Deadline: 4th of October (end-of-day)
Submission mechanism: Moodle

1. Finding Main Entry Points (0.5 points)

Execution of a Java program starts by executing a main method. For instance, when you write

  java -cp foo.jar MainClass a b c

Java will attempt to invoke the method MainClass.main(String[]) with the parameters ["a", "b", "c"]. If this is possible, then we refer to the method MainClass.main(String[]) as a main entry point of the program that it is part of.

However, not all methods called main are permitted as main entry points Java Language Specification. Conversely, many programs have several main entry points.

Task: Write a program analysis that discovers and prints out the main entry points of all classes passed to the Soot classpath.

2. Finding Deprecated Calls (0.5 points)

Java permits methods to be marked deprecated. The intent is to signal that these methods may be removed in the future, or that their use is discouraged for other reasons. Since libraries and application code often evolve separately, it can happen that an application relies on a library method that becomes deprecated, without the original application developer being aware of this evolution.

Task: Write a program analysis that discovers all calls to deprecated methods in classes passed to the Soot classpath.
Your solution should print the file names and line numbers to stdout (e.g., using System.out.println()) in the following format:
DEP <methodname> <linenr-or-nothing>
where the methodname is returned by Body.getMethod().getSignature() and the line number is returend by Unit.getJavaSourceStartLineNumber() (e.g., DEP <MyClass: int[] mymethod(int)> -1). You may omit the line number if it is not available, or otherwise print -1).

3. Simplified Array Bounds Checking (1.5 points)

Array-out-of-bounds checking tries to determine whether the index i in a[i] is invalid. In this exercise, you will implement a simplified version that detects whether i is guaranteed to be negative. To detect this property, you may want to build on one of the abstract domains that we discussed in class, but refine the domain model first (e.g., consider what happens when merging A⁰ and A⁺).

Consider using one of Soot's built in CFG generators, such as the class ExceptionalBlockGraph.

When designing your code for this task, make sure to also consider part 5 of this homework, which asks you to make your code reusable.

Task: Write a simplified out-of-bounds checker that detects reads and writes on arrays where the array index is definitely negative (aim for 100% precision). Your program should run the analysis of all methods of all classes passed to the Soot classpath.
Your solution should print the file names and line numbers to stdout (e.g., using System.out.println()) in the following format:
NBV <methodname> <linenr-or-nothing>
where the methodname is returned by Body.getMethod().getSignature() and the line number is returend by Unit.getJavaSourceStartLineNumber() (e.g., NBV <MyClass: int[] mymethod(int)> -1). You may omit the line number if it is not available, or otherwise print -1).

4. Finding Useless Assignments with Live Variables Analysis (1.5 points)

Live Variables Analysis is a backward analysis (and one of our examples from the second lecture) that can detect whether a variable is assigned to even though it is not needed later in the program. In this exercise you will implement this analysis (or, thanks to Mattias, you can alternatively implement an equivalent forward analysis).

Try to reuse your code from part 3 (if you have already completed part 3). See also part 5.

Task: Write a Live Variables analysis that checks for writes to local variables that can never read (aim for 100% precision). Your program should run the analysis of all methods of all classes passed to the Soot classpath.
Your solution should print the file names and line numbers to stdout (e.g., using System.out.println()) in the following format:
UVD <methodname> <linenr-or-nothing>
where the methodname is returned by Body.getMethod().getSignature() and the line number is returend by Unit.getJavaSourceStartLineNumber() (e.g., UVD <MyClass: int[] mymethod(int)> -1). You may omit the line number if it is not available, or otherwise print -1).

5. Reusing Your Code (1 point)

Task: Design a small API ((abstract) classes and interfaces) that allows clients to write a forward or backward analysis based on Soot, with clients specifying whether the analysis should be forward or backward, and specifying their abstract domain. Demonstrate that your API is effective by using it in your implementation of part 3 or part 4 of this assignment.