Program Analysis of Google Chrome

Program Analysis of Google Chrome

Tested Android Application

The android Chrome application is taken as demonstration application originally developed by the Goolgle Team on Android platform. It features 4552 classes, 14184 methods and was written in Java code. The first method used is conversion of java codes in to soot’s intermediate representation Jimple files for each 4552 java classes and graphical representation for each 14184 methods which further converted in to control flow graph and call graph based on nodes and edges inside the method. Secondly, the generated Dalvik bytecode contains Dalvik instructions.

From the Dalvik bytecode of the Chrome application I generate Jimple code in one second (duration for the Dalvik to Jimple conversion only). Then I ask Soot to generate Java bytecode from the Jimple representation. I convert the Java bytecode back to Dalvik, repackage an Android application and launch it on the Android emulator. The application runs smoothly and the app is working.

Static Analysis on Chrome

I use Soot to generate a call graph of the Chrome application, portion of the control flow graph represented in Figure 2.

Control Flow analysis Graph (Call Graph) for  org.chromium.chrome.browser.preferences.website.WebsitemergePermissionInfoForTopLevelOrigin(org.chromium.chrome.browser.preferences. website.WebsiteAddress,java.util.List) Method Extracted from the Generated Jimple Representation. .36 seconds (duration from the launch time of Soot until Soot has finished). I perform this to check that the generated call graph and CFG correspond to the original code meaning that the conversion from Dalvik to Jimple is correct for this code.

I have successfully tested Soot as IR Jimple conversion to and another tool Dalvik bytecode to an Android application.

Figure 2: Partial Call graph for (chrome.browser.preferences.website) method

Process Analysis

Firstly, I used soot for conversion of Chrome.apk i.e. downloads from google play store to Soot’s Intermediate Representation Jimple and Soot’s CFG Viewer to produce graphical representation of all the methods from classes as dot files based on existing works of Droiddel[7].

Second Method, since there no existing tool directly converts Dalvik bytecode to Jimple. I either found tools to convert Dalvik bytecode to Java bytecode or tools to disassemble and/or assemble assemble Dalvik bytecode using an intermediate representation [4].

Dalvik to Java Bytecode Converter Ded is a Dalvik bytecode to Java bytecode converter. Once the Java bytecode is generated, Soot is used to optimize the code. Dex2jar also generates Java bytecode from Dalvik bytecode but no not use any external tool to optimize the resulting Java bytecode [5]. Undx is also a Dalvik to Java bytecode converter but seems to be unavailable. I on the other hand do not directly generate Java bytecode but Jimple code.

From there, since the Jimple code is within Soot, I can generate Java bytecode as well. Dalvik Assembler/Disassembler Smali or Androguard can be used to reverse engineer Dalvik bytecode. They use their own representation of the Dalvik bytecode: they cannot leverage existing analysis tools. This tool, use Soot’s internal representation which allows existing tools to analyze/transform the Dalvik bytecode [7].

Conclusion

Here we introduced a new analysis that integrates and enhances existing Android app static analyses. I have presented the phenomena of static analysis of android apps based on the control flow graphs by using soot. I successfully use conversion of an android app (java byte code) into dalvik bytecode (android app). And generate the control flow graphs from java methods and perform the static analysis.

This can further be used for static analysis of any android apps or java programs and computation of nodes and edges for the analysis of the complex algorithm. Finally, it is also can be used on static fields, implicit flow, distinguish different receive intents as well as other data channels.

Static Analysis of Android Apps Using Soot

Static Analysis of Android Apps Using Soot

Related Work

There are some previous works were done on this fields but all are yet to be conclusive to fully analysis android application. Some of the research that follows parital analysis works are:

Flow Droid: It is a context-sensitive, flow-based, field-based, object-sensitive, and lifecycle aware static taint analysis tool for java as well as android programming. Unlike many other static-analysis approaches for android it aims for an analysis with very high recall and accuracy of android programs  To achieve the main goal it accomplished two main challenges as increase in precision and builds an analysis that is context-, flow-, field- and object-sensitive; to increase recall It create a complete model of program lifecycle. 

However, the analysis [10] uses the application instrumentation tools such as Soot and Heros. The Flow Droid uses a very precise call graph which helps us to ensure flow-sensitive and context-sensitivity. Its IFDS-based flow functions guarantee field and object sensitivity. As a result of the highly precise and efficient alias, the procedure for searching is crucial for contextsensitivity in conjunction with field-sensitivity.

Inter-procedural Analysis: While analyzing the resemblance of the efficiency and effectiveness for the inter-procedural class analysis based on the Cartesian product algorithm and   profileguided class which are predicted for the optimizing self-program[8].

But it is the fact that it has very little difference in term of the outcome or performance among the three configurations optimization i.e. using only profile-guided class prediction, using only inter-procedural class analysis, and using both techniques [8]. 

Iterative algorithms: As of now, the main iterative algorithm that has really been executed is Plevyak's iterative algorithms [9]. Various papers proposing new call graph generating calculations have exactly surveyed the adequacy of their calculation by executing them in an improving compiler and utilizing the subsequent control flow graph to perform at least one or more inter-procedural analyses

Soot

Soot [1] was created at McGill University as a java compiler, further developed and become an android static analysis and transformation tool. Soot can be used for multiple tasks i.e. code analyze, transformation of java programs or android apps, instrumentation of an android apps, check that certain properties hold or guarantee correctness of programs.

Multiple tools based on Soot have been developed to perform transformations such as translation of Java to C, instrumentation of android apps or java programs, obfuscator for Java, software watermarking, Soot accepts Java source code, Java bytecode and Jimple source code as input files[1].

Any input format is converted into Soot’s internal representation: Jimple, Baf Grimph and Shimple. Java SIMPLE, is a stack-less, three address representation which features only 15 instructions. Any method code can be viewed as a graph of Jimple statements associated with a list of Jimple local variables.

Dalivk bytecode

Android uses Dalvik Virtual Machine [2, 3] as a main component which is a kind of Java Virtual Machine specially designed and optimized for Android applications. The Dalvik VM makes uses features like memory management and multi-threading, which is intrinsic in the Java language from Linux core system.

The Dalvik VM enables every Android application to run in its own process, with its own instance of the Dalvik virtual machine. Android application developers write Android applications using standard Java programming language with the set of core libraries, which enabled by the Android runtime.

Converting Dot files into Control Flow Graphs using GraphViz

Generate Control Flow Graph Using Graphviz

To convert android apk into dot files and do analysis by using soot click here. 

To generate control flow graph using graphviz, you need dot files which is generated from all methods of android apks. you can find them on sootOutput directory, now you need to go to command line and type following commands if you have already set graph viz path. 

To convert into pdf:

> dot Tpdf -o Example.pdf Example.dot

To convert into png:

> dot Tpng -o Example.png Example.dot

Note: if you haven't set path you need to set path (to know how to set path see installation post) or go to bin folder of graph viz installation folder and find dot file from command line and type above commands.

commands:

>dot : executable dot file (also MS word old file format for graph)

> -Tpdf, -Tpng: converting file format

> -o: Optimization

> Example.pdf, .png: Name of Control flow graph you wanna give after conversion.

>Example.dot : Name of dot file you wanna convert


Note: Graphviz not only use dot file format and executable files you can convert various different files into control flow graph. This post is on the context of program analysis of smart phone apps i.e. android apps using Soot as analysis tool.

Create Control Flow Graph from Android apk Using Soot

Control Flow Graph(Call graphs) Using Soot

Lets look at command to convert any android apk file into Control flow graph or call graphs using soot as a command line tool. This will creates Jimple files for all the classes from apk and dot files for all the methods which is graphical representation as Control Flow Graph (CFG) or call graphs.

For conversion, you need to:

> Download any .apk file

> Download android sdk from android developer site or download android jars

> Download Soot's nightly build version from Soot- Github

Before applied command, you need to know right path for android sdk -platforms directory, .apk file located directory and nightly build version of soot at right directory

Set CLASSPATH of Soot.jar or go to the directory that contains Soot.jar file then type following Command:

> java -Xmx2g -jar soot-trunk.jar soot.tools.CFGViewer -w -allow-phantom-refs       -android-jars "D:\sdk\platform" -src-prec apk -output-format dex         -process-dir "C:\apkpath\example.apk"

If you have already set CLASSPATH for jar then type following

>java -Xmx2g soot.tools.CFGViewer -w -allow-phantom-refs -android-jars "D:\sdk\platform" -src-prec apk -output-format dex -process-dir "C:\apkpath\example.apk"

Details: -Xmx2g it represents memory of 2GB which is normally sufficient for any apk process.

-jar can be replaced by -cp which means CLASSPATH or it represent command prompt's current directory.

-W stands for writing

-allow-phantom-refs creates phantom classes for missing or unprocessed classes

-android-jars leads to path for android sdk or jars to process apks

-src-prec represents the file format you are trying to process

-output-format dex is responsible for converting all the classes from apk into dex format

-process-dir shows the path for processing directory or apk located directory

   

This will generate Jimple and dot files in sootOutput directory. The dot files are further used to create control flow graphs by using tools like graphviz .(More about Grphviz click here) 

Creating Control Flow Diagram from Java Class files Using Soot.

Creating Control Flow Diagram from Java Class files Using Soot.

In order to create control flow diagram you need to convert Java class file into dot files by using control flow viewer soot tool. You can get HelloWorld.java file from previous posts(here). Convert it in to class file and type following commands on command prompt inside soot directory where HelloWorld is located:

>Java soot.tools.CFGViewer HelloWorld

And if you do not set classpath then type following inside soot directory where HelloWorld  and soot jars are located:

>Java -cp soot-2.5.0.jar soot.tools.CFGViewer HelloWorld

you will see following if it succeed:

It will create graphical representation of control flow graph of dot file format for each method from the class files. 

Java.lang.String[] Method:

digraph "void main(java.lang.String[])" {
    label="void main(java.lang.String[])";
    node [shape=box];
    "0" [style=filled,fillcolor=gray,label="r0 := @parameter0",];
    "1" [label="$r1 = new HelloWorld",];
    "0"->"1";
    "2" [label="specialinvoke $r1.<init>()",];
    "1"->"2";
    "3" [label="HelloWorld.helloObj = $r1",];
    "2"->"3";
    "4" [label="$r2 = java.lang.System.out",];
    "3"->"4";
    "5" [label="$r3 = HelloWorld.helloObj",];
    "4"->"5";
    "6" [label="$r4 = $r3.printMessage()",];
    "5"->"6";
    "7" [label="$r2.println($r4)",];
    "6"->"7";
    "8" [style=filled,fillcolor=lightgray,label="return",];
    "7"->"8";
}
 

Print Message() Method:

digraph "java.lang.String printMessage()" {
    label="java.lang.String printMessage()";
    node [shape=box];
    "0" [style=filled,fillcolor=gray,label="r0 := @this",];
    "1" [label="$r1 = r0.output",];
    "0"->"1";
    "2" [style=filled,fillcolor=lightgray,label="return $r1",];
    "1"->"2";
}

Jimple files Codes - Static Analysis of Android Applications Using Soot

Jimple files Codes

From previous example (Click Here  to view)HelloWorld.Jimple contains located at sootOutput directory following: 

public class HelloWorld extends java.lang.Object

{

    java.lang.String output;

    static HelloWorld helloObj;

    public void <init>()

    {

        HelloWorld r0;

  

      r0 := @this: HelloWorld;

        

specialinvoke r0.<java.lang.Object: void <init>()>();

        

r0.<HelloWorld: java.lang.String output> = "";

        

r0.<HelloWorld: java.lang.String output> = "Hello world";

        

return;

    

}

    public java.lang.String printMessage()

    {

        HelloWorld r0;

        

java.lang.String $r1;

        

r0 := @this: HelloWorld;

        

$r1 = r0.<HelloWorld: java.lang.String output>;

        

return $r1;

    

}

    public static void main(java.lang.String[])

    {

    java.lang.String[] r0;

        

HelloWorld $r1, $r3;

        

java.io.PrintStream $r2;

        

java.lang.String $r4;

        r0 := @parameter0: java.lang.String[];

        

$r1 = new HelloWorld;

        

specialinvoke $r1.<HelloWorld: void <init>()>();

        

<HelloWorld: HelloWorld helloObj> = $r1;

        

$r2 = <java.lang.System: java.io.PrintStream out>;

        

$r3 = <HelloWorld: HelloWorld helloObj>;

        

$r4 = virtualinvoke $r3.<HelloWorld: java.lang.String printMessage()>();

       

virtualinvoke $r2.<java.io.PrintStream: void println(java.lang.String)>($r4);

        

return;

    

}

}