Points-to analysis for partial call graph construction
 
" /> 支持局部调用图生成的指针分析
Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)
计算机技术﹑电信技术     
支持局部调用图生成的指针分析
万志远, 周波
浙江大学 计算机科学与技术学院,浙江 杭州 310027
Points-to analysis for partial call graph construction
 
WAN Zhi-yuan, ZHOU Bo
College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China
 全文: PDF(1114 KB)   HTML
摘要：

在不分析库代码方法体的前提下,提出一种支持应用部分局部调用图生成的指针分析方法. 该方法通过构建一系列规则,对应用部分和库部分的交互行为进行建模,推导库部分的指针信息. 基于Soot程序分析框架实现该方法,并在14个Java基准程序上对其性能以及所生成调用图的完整性和精确性进行评估. 实验结果表明：该方法的运行速度比Averroes和Spark调用图生成方法分别快4.9倍和13.7倍,并且能够创建完整且精确的局部调用图.
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.
出版日期: 2015-06-01
:  TP 309  
通讯作者: 周波，男，副教授     E-mail: bzhou@zju.edu.cn
作者简介: 万志远(1984—)，女，博士生，从事软件安全和程序分析研究. E-mail: wanzhiyuan@zju.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

万志远, 周波. 支持局部调用图生成的指针分析[J]. 浙江大学学报(工学版), 10.3785/j.issn.1008-973X.2015.06.005.

WAN Zhi-yuan, ZHOU Bo.

Points-to analysis for partial call graph construction
 
. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 10.3785/j.issn.1008-973X.2015.06.005.

链接本文:

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

［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] 蒋煦, 张长胜, 戴大蒙, 阮婧, 慕德俊. Android应用程序隐私数据泄露检测[J]. 浙江大学学报(工学版), 2016, 50(12): 2357-2363.
[2] 马春来, 单洪, 李志, 朱立新. 移动用户下一地点预测新方法[J]. 浙江大学学报(工学版), 2016, 50(12): 2371-2379.
[3] 万志远, 周波. 基于静态信息流跟踪的输入验证漏洞检测方法[J]. 浙江大学学报(工学版), 2015, 49(4): 683-691.
[4] 王友卫, 刘元宁, 朱晓冬. 用于图像内容认证的半脆弱水印新算法[J]. J4, 2013, 47(6): 969-976.
[5] 李卓,陈健,蒋晓宁,曾宪庭,潘雪增. 基于多域特征的JPEG图像盲检测算法[J]. J4, 2011, 45(9): 1528-1538.
[6] 马晨华, 王进, 裘炅, 陆国栋. 基于情景约束的工作流柔性访问控制模型[J]. J4, 2010, 44(12): 2297-2308.
[7] 陈珂， 胡天磊， 陈刚. 基于角色的信任证覆盖网络中高效信任链搜索[J]. J4, 2010, 44(12): 2241-2250.
[8] 周天舒, 李劲松, 杨一兵, 陈运奇, 薛万国, 赵军平. 区域医疗系统数据真实性保障流程优化[J]. J4, 2010, 44(8): 1484-1489.
[9] 彭志宇, 李善平, 杨朝晖, 林欣. 信任管理中的匿名授权方法[J]. J4, 2010, 44(5): 897-902.
[10] 姜励, 陈健, 平玲娣, 陈小平. 多线程程序的信息抹除和降密安全策略[J]. J4, 2010, 44(5): 854-862.
[11] 付剑晶, 王珂. 基于交叉控制流混淆技术的编译方法[J]. J4, 2010, 44(5): 903-909.
[12] 余利华, 陈刚, 王伟, 陈柯, 董金祥. 一种基于容器的自组织存储模型[J]. J4, 2010, 44(5): 915-922.
[13] 江颉, 张杰, 陈德人. 基于推理的上下文感知RBAC模型设计和实现[J]. J4, 2009, 43(09): 1609-1614.
[14] 陈珂, 邵峰, 陈刚, 等. XML结构化匹配中的位图过滤加速法[J]. J4, 2009, 43(09): 1549-1556.
[15] 黄勇, 陈小平, 陈文智, 等. 支持动态调节的保密性和完整性统一模型[J]. J4, 2009, 43(8): 1377-1382.