CS 201 Project
Handed Out: Oct 22, 2019
Due: Nov 26, 2019
Grade Weight: 30% of total course grade
This assignment can be done individually, or in a group of two.
Project Description
The goal of this project is to understand and implement the basic program analysis and program profiling techniques. In this project, you
are required to implement the followings:
Static Analysis:
1. For each program under analysis, you need to identify all of the loops in the program.
2. For each loop, identify the instructions where the definition of at least one use of a variable in that instruction might come from
outside of the loop.
Dynamic Analysis (Profiling)
3. Output the number of executions for instructions found at step 2.
You will carry out this project as follows:
1. Parse the input program, collect the control flow information and identify and output all the loops in the program.
2. For each loop, identify the instructions where the definition of at least one uses in that instruction might come from outside of the
loop.
3. Instrument the code to find the execution frequency of instructions you found in previous steps.
4. Run the instrumented code and output the profiling results.
More details about the languages, tools, output requirements and submission format can be found in the following:
Soot
Getting Started with Soot
Program Analysis and Profiling Using Soot: Setup and Program Template
Output Requirements
Submission
Reporting Problems
Soot
Soot is a Java optimization framework which is used to analyze, instrument, optimize and visualize Java programs. More detailed
information can be found in The Soot framework for Java program analysis: a retrospective paper. Soot can process code from Java
sources and produce (possibly transformed/instrumented/optimized) code in the following output formats:
Baf: a streamlined representation of bytecode which is simple to manipulate.
Jimple: a typed 3-address intermediate representation suitable for optimization.
Shimple: an SSA variation of Jimple.
Grimp: an aggregated version of Jimple suitable for decompilation and code inspection.
Below is an example of a simple Java program, and the corresponding Soot Jimple IR.
An unconventional hello world in Java
public class HelloWorld {
public static void main(String[] args) {
int x=10;
System.out.println("Hello World");
}
}
The Corresponding Jimple IR
public static void main(java.lang.String[])
{
java.lang.String[] args;
int x;
java.io.PrintStream temp$0;
args := @parameter0: java.lang.String[];
x = 10;
temp$0 = ;
virtualinvoke temp$0.("Hello World");
return;
}
public void ()
{
HelloWorld this;
this := @this: HelloWorld;
specialinvoke this.()>();
return;
}
Getting Started with soot
The prerequisites for working with Soot are as follows:
1. Familiarity with Java: The Java Tutorials
2. Familiarity with Eclipse: Eclipse Homepage
3. On-demand familiarity with Soot: Tutorials for Soot
4. Familiarity with compiler terminology like BasicBlocks etc.
You can find useful info about Soot in the following links:
1. Soot mailing list
2. Master's thesis describing Soot
3. Sample Soot programs
Program Analysis and Profiling Using Soot: Setup and Program Template
The following instructions will help you setup your computer for this project.
Important Note: (These instructions have been tested and verified on Ubuntu. In these instructions, Soot has been used as the Eclipse
plugin.
You are still free to use Soot as a command-line tool (e.g., via Maven) or you can use any other versions of Soot/Java but your
submission README file MUST contain complete information and instructions for compiling your code and running it. Please see
Submission section.)
1. Install JDK 7 (Works better for Soot Dava Decompile) and JDK 8 (Works better for Soot instrumentation and analysis) on your
computer if you do not have them.
2. Install Eclipse Kepler on your computer if you do not have it.
3. Open Eclipse. Select Help -> Install New Software -> In Work with: type the following link:
"http://www.sable.mcgill.ca/soot/eclipse/updates/" -> Select Add -> In Location type the same link -> Select OK -> Select the
Soot package -> Select Next -> Select Next -> Select "I accept the terms..." -> Select Finish and then Eclipse will be reinstalled.
4. Extract this sample project and import it to Eclipse (Select File -> Import -> select "Existing Projects into Workspace" -> Select
Next -> For root directory, select the extracted folder CS201Fall19 -> Select Finish.
5. Add one of the following Soot jar files to your project (Right click on your project and select Properties -> Select Java Build Path ->
Select Libraries -> Select Add External JARs -> Select the downloaded jar file -> Select OK -> Select OK)
1. soot-2.5.0.jar or
(In case if you use Java 7. Hence, you should select Java 7 as your JRE System Library in Eclipse (Right click on your project
and select Properties -> Select Java Build Path -> Select Libraries -> Select JRE System Library -> In Alternative JRE,
choose Installed JREs, select java-7-openjdk. If you do not have any Installed JRE listed, click Add and add a Standard VM by
navigating to your JRE directory))
2. sootclasses-trunk-jar-with-dependencies.jar
(In case if you use Java 8. Hence, you should select Java 8 as your JRE System Library in Eclipse (Right click on your project
and select Properties -> Select Java Build Path -> Select Libraries -> Select JRE System Library -> In Alternative JRE,
choose Installed JREs, select java-8-openjdk. If you do not have any Installed JRE listed, click Add and add a Standard VM by
navigating to your JRE directory))
6. Add the Analysis Folder to the soot –process-dir (Right click on the Main.java class -> Select Run as -> Select Run Configurations
-> Select Arguments -> In Program arguments type -allow-phantom-refs -process-dir
/your/Analysis/folder/path/in/your/project/directory/) -> Select Apply
7. Fill in the details for staticAnalysis() and dynamicAnalysis() methods and run your program.
8. Your instrumented .jimple file (e.g., Test1.jimple) will be written to sootOutput/Test1.jimple.
9. In Eclipse, right click on Test1.jimple -> Select Soot -> Select Dava Decompile App to create the instrumented java file. (At this step
you might get some errors if you are using Java 8, so it is recommended to set your Java to Java 7 for this step)
10. Your instrumented .java file (e.g., Test1.java) will be written to sootOutput/dava/src/Test1.java.
11. Run the instrumented Test1.java to print the dynamic analysis outputs.
Output Requirements
The output requirements are as follows: First, you need to report the loops in the program. This way, we will be able to identify whether or
not you have correctly identified the program control flow information. If these can't be determined from your output, your score will be
penalized accordingly. Second in each loop, you need to output the instructions where the definition of at least one use of a variable in
that instruction might come from outside of the loop. Third, you need to instrument the code to gather number of executions for such
instructions for a specific run of the program.
Instrumented programs should output the number of times those instructions were executed during the run of the program. Since there
are many reasonable ways this can be done, we are going to leave the specifics up to you.
Here is an example of a Java class that we might want to analyze:
Example Java Class
public class Test1 {
public static void main(String[] args) {
int a = 0;
int b = 95;
func1(a);
func1(b);
}
public static void func1 (int x) {
if(x != 0){
while(x % 4 != 0){
x = x/4;
}
}
}
}
Output example of loops
Method: