An Approach for Generating Call Graph of Java/Android Programs

摘要

对于包括Java和Android程序在内的任何编程语言的分析，一幅精确的方法调用图是人们理解和跟踪程序的异常的关键因素。调用图用于表示可调用的子单元之间的关系，特别是在Java或Android编程中各种方法的调用关系。换句话说，调用图是一个表示递归方法调用的有向图，其中，每一条边(x，y)表示方法x调用方法y，节点代表方法。
　　本文提出了一种能够生成任何Java或Android程序调用图的工作模型，作为一种生成调用图的方法。并将该方法与类层次分析方法、快速类型分析方法、以及包括ASM和Soot在内的类类型分析方法进行了测试对比。ASM和Soot被实现为一个接口，并且这些算法可以根据每个用户的需求进行定制。本文主要关注Java和Android程序的方法调用图的生成方法。
　　在程序的核心分析部分，本文获得了自身数据结构中的所有细节，并存储程序所有基本的信息（包括类、方法、变量和声明语句）。其允许一个独立的方法存在于现有的所有方法中，生成调用图。在一个可到达的方法通过字节码阅读器阅读具体程序的字节码来调用每个方法后，生成的数据结构将允许处理字节码阅读器依赖，以创建任何程序的调用图，因为所有的数据都累积收集了基于使用的方法和预先定义的数据结构的字节码程序，这些都是不可或缺的。
　　最后，通过使用用户指定的算法生成调用图，这也是本文的唯一目的。此外，采用了不同的java和android程序与三个现有算法即类层次分析、快速类型分析和类类型分析在不同条件下进行了实验分析，并通过程序处理和优化工具评估实验结果。

目录

声明

摘要

Abstract

TABLE OF CONTENTS

Chapter 1 Introduction

1．1 Overview

1．2 Call Graph

1．3 Algorithms for Generating Call Graphs

1．3．1 Reaehability Analysis(RA)

1．3．2 Class Hierarchy Analysis(CHA)

1．3．3 Rapid Type Analysis(RTA)

1．3．4 Class Type Analysis(CTA)

1．4 Motivation

1．5 Contribution of Dissertation

1．6 Related Work

1．7 Dissertation Organization

Chapter 2 PROBLEM DEFINITIONS

2．1 Overview

2．2 An Approach Overview

2．3 Implementation on existing algorithms

2．3．1 Class Hierarchy Analysis(CHA)

2．3．2 Rapid Type Analysis(RTA)

2．3．3 Class Type Analysis(CTA)

Chapter 3 DESIGN

3．1 Overview

3．2 Goals of the Approach

3．3 An Approach

3．4 Interface Requirements

3．5 Experiments Design

3．5．1 Tested Programs

3．5．2 Approach Testing

Chapter 4 IMPLEMENTATIONS

4．1 Overview

4．2 The Soot Framework

4．3 The ASM Framework

4．4 Results

4．4．1 Call Graph Nodes

4．4．2 Call Graph Edges

4．4．3 Consumed Time

4．4．4 Consumed Memory

Chapter 5 PROOF OF CONCEPT

5．1 Experimental Setup

5．2 Characteristic of Call Graphs

5．3 Result Summary

Chapter 6 CONCLUSION AND FUTURE WORKS

6．1 Conclusion

6．2 Future Works

Acknowledgments

References

My Publications

Appendix