<div style=

doi:10.3785/j.issn.1008-973X.2015.06.005

JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE)

Points-to analysis for partial call graph construction

WAN Zhi-yuan, ZHOU Bo

College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China

Download:

PDF(1114KB) HTML
Export: BibTeX | EndNote (RIS)

Abstract

A points-to analysis approach was proposed to generate partial call graphs of application part without analyzing the method bodies of libraries. A set of rules was bulit to model the interaction between application and libraries in order to infer the pointer information libraries. The approach was implemented based on the Soot program analysis framework. The performance, completeness and precision of generated call graphs were evaluated on 14 Java benchmarks. The experimental results showed that the proposed approach was faster than Averroes and Spark call graph construction approaches by a factor of 4.9x and 13.7x respectively. Meanwhile, the proposed approach can construct complete and precise partial call graphs.

Published: 01 June 2015

CLC:

TP 309

	Service
	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors

Cite this article:

WAN Zhi-yuan, ZHOU Bo.

Points-to analysis for partial call graph construction

. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2015, 49(6): 1031-1040.

URL:

http://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2015.06.005 OR http://www.zjujournals.com/eng/Y2015/V49/I6/1031

支持局部调用图生成的指针分析

在不分析库代码方法体的前提下,提出一种支持应用部分局部调用图生成的指针分析方法. 该方法通过构建一系列规则,对应用部分和库部分的交互行为进行建模,推导库部分的指针信息. 基于Soot程序分析框架实现该方法,并在14个Java基准程序上对其性能以及所生成调用图的完整性和精确性进行评估. 实验结果表明：该方法的运行速度比Averroes和Spark调用图生成方法分别快4.9倍和13.7倍,并且能够创建完整且精确的局部调用图.

［1］ GROVE D, CHAMBERS C. A framework for call graph construction algorithms ［J］. ACM Transactions on Programming Languages and Systems, 2001, 23(6): 685-746.

［2］ LHOTK O. Comparing call graphs ［C］∥ Proceedings of the 7th ACM SIGPLANSIGSOFT Workshop on Program Analysis for Software Tools and Engineering. San Diego: ACM, 2007: 37-42.

［3］ T.J. Watson libraries for analysis (WALA) \[EB/OL\]. \[2014-03-21\]. http:∥wala.sourceforge.net.

［4］ VALLE-RAI R, GAGNON E, HENDREN L J, et al. Optimizing Java bytecode using the soot framework: is it feasible？［C］∥ Proceedings of the 9th International Conference on Compiler Construction. Berlin: Springer, 2000: 18-34.

［5］ DEAN J, GROVE D, CHAMBERS C. Optimization of object-oriented programs using static class hierarchy analysis ［C］∥ Proceedings of the 9th European Conference on Object-Oriented Programming. London: Springer, 1995: 77-101.

［6］ BACON D F, SWEENEY P F. Fast static analysis of C++ virtual function calls ［C］∥ Proceedings of the 11th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages and Applications. San José: ACM, 1996: 324-341.

［7］ DIWAN A, MOSS J, MCKINLEY K S. Simple and effective analysis of statically-typed object-oriented programs ［C］∥ Proceedings of the 11th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages and Applications. San José: ACM, 1996: 292-305.

［8］ SUNDARESAN V, HENDREN L, RAZAFIMAHEFA C, et al. Practical virtual method call resolution for Java ［C］∥ Proceedings of the 15th ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages and Applications. Minneapolis: ACM, 2000: 264-280.

［9］ YAN D, XU G, ROUNTEV A. Rethinking Soot for summary-based whole-program analysis ［C］∥ Proceedings of ACM SIGPLAN International Workshop on State of the Art in Java Program Analysis. Beijing: ACM, 2012: 9-14.

［10］ ANDERSEN L O. Program analysis and specialization for the C programming language ［D］. Denmark: University of Copenhagen, 1994: 635.

［11］ LHOTK O, HENDREN L. Scaling Java points-to analysis using SPARK ［C］∥ Proceedings of the 12th International Conference on Compiler Construction. Warsaw: Springer, 2003: 153-169.

［12］ ALI K, LHOTK O. Averroes: whole-program analysis without the whole program ［C］∥ Proceedings of the 27th European Conference on Object-Oriented Programming. Montpellier: Springer, 2013: 378-400.

［13］ BLACKBURN S M, GARNER R, HOFFMAN C, et al. The DaCapo benchmarks: Java benchmarking development and analysis ［C］∥ Proceedings of the 21st Annual ACM SIGPLAN International Conference on Object-Oriented Programing, Systems, Languages and Applications. Portland: ACM, 2006: 169-190.

［14］ Standard Performance Evaluation Corporation: SPEC JVM98 benchmarks ［EB/OL］. ［2014-03-21］. http:∥www.spec.org/jvm98.

［15］ ALI K, LHOTK O. Application-only call graph construction ［C］∥ Proceedings of the 26th European Conference on Object-Oriented Programming. Beijing: Springer, 2012: 688-712.

［16］ BODDEN E, SEWE A, SINSCHEK J, et al. Taming reflection: aiding static analysis in the presence of reflection and custom class loaders ［C］∥ Proceedings of the 33rd International Conference on Software Engineering. Honolulu: ACM, 2011: 241-250.

［17］ DUFOUR B, HENDREN L, VERBRUGGE C. *J: a tool for dynamic analysis of Java programs ［C］∥ Proceedings of Companion of the 18th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications. Anaheim: ACM, 2003: 306-307.

［18］ TIP F, PALSBERG J. Scalable propagation-based call graph construction algorithms ［C］∥ Proceedings of the 15th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages and Applications. Minneapolis: ACM, 2000: 281-293.

［19］ GROTHOFF C, PALSBERG J, VITEK J. Encapsulating objects with confined types ［C］∥ Proceedings of the 16th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages and Applications. Tampa Bay: ACM, 2001: 241-255.

［20］ ROUNTEV A, MILANOVA A, RYDER B G. Fragment class analysis for testing of polymorphism in Java software ［J］. IEEE Transactions on Software Engineering, 2004, 30(6): 372-387.

［21］ ZHANG W, RYDER B G. Automatic construction of accurate application call graph with library call abstraction for Java ［J］. Journal of Software Maintenance and Evolution: Research and Practice, 2007, 19(4): 231-252.

[1]	JIANG Xu, ZHANG Chang sheng, DAI Da meng, RUAN Jing, MU De jun. Privacy data leakage detection for Android application[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(12): 2357-2363.

[2]	MA Chun lai, SHAN Hong, LI Zhi, ZHU Li xin. New next place prediction method for mobile users[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(12): 2371-2379.

[3]	WAN Zhi-yuan, ZHOU Bo. Static information flow tracking based approach to detect input validation vulnerabilities[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2015, 49(4): 683-691.

[4]	WANG You-wei, LIU Yuan-ning, ZHU Xiao-dong. Novel semi-fragile watermarking algorithm for image content authentication[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2013, 47(6): 969-976.

[5]	LI Zhuo, CHEN Jian, JIANG Xiao-ning, ZENG Xian-ting, PAN Xue-zeng. Blind JPEG steganalysis based on multi-domain features[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2011, 45(9): 1528-1538.

[6]	MA Chen-hua, WANG Jing, QIU Jiong, LU Guo-dong. Flexible context-constraint-based access control model for workflows[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2010, 44(12): 2297-2308.

[7]	CHEN Ke, HU Tian-lei, CHEN Gang. Fast trust chain search in role-based credential overlay network[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2010, 44(12): 2241-2250.

[8]	ZHOU Tian-Shu, LI Jin-Song, YANG Yi-Bing, CHEN Yun-Ai, XUE Mo-Guo, DIAO Jun-Beng. Improvement of data authenticity assurance process in regional health information system[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2010, 44(8): 1484-1489.

[9]	BANG Zhi-Yu, LI Shan-Beng, YANG Chao-Hui, LIN Xin. Anonymous authorization in trust management[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2010, 44(5): 897-902.

[10]	JIANG Li, CHEN Jian, BENG Ling-Di, CHEN Xiao-Beng. Security policy for information erasing and leaking in multithreaded codes[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2010, 44(5): 854-862.

[11]	FU Jian-Jing, WANG Ke. Compiling method for obfuscation technology based on crossing control-flow[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2010, 44(5): 903-909.

[12]	TU Li-Hua, CHEN Gang, WANG Wei, CHEN Ke, DONG Jin-Xiang. Containerbased self-organizing storage model[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2010, 44(5): 915-922.

[13]	JIANG Jia, ZHANG Jie, CHEN De-Ren. Design and implementation of context-aware RBAC model based on reasoning[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2009, 43(09): 1609-1614.

[14]	CHEN Ke, SHAO Feng, CHEN Gang, et al. Accelerating XML structural matching using bitmap filtration[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2009, 43(09): 1549-1556.

[15]	HUANG Yong, CHEN Xiao-Ping, CHEN Wen-Zhi. Dynamically modified union model combining confidentiality and integrity[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2009, 43(8): 1377-1382.

Viewed

Full text

Abstract

Cited

Shared

Discussed