ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2019, Vol. 56 ›› Issue (3): 480-495.doi: 10.7544/issn1000-1239.2019.20180071

• 网络技术 • 上一篇    下一篇

基于稀疏框架的静态污点分析优化技术

王蕾,何冬杰,李炼,冯晓兵   

  1. (计算机体系结构国家重点实验室(中国科学院计算技术研究所) 北京 100190) (中国科学院大学 北京 100049) (wanglei2011@ict.ac.cn)
  • 出版日期: 2019-03-01
  • 基金资助: 
    国家自然科学基金项目(61521092,61432016);国家重点研发计划项目(2017YFB0202002)

Sparse Framework Based Static Taint Analysis Optimization

Wang Lei, He Dongjie, Li Lian, Feng Xiaobing   

  1. (State Key Laboratory of Computer Architecture(Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190) (University of Chinese Academy of Sciences, Beijing 100049)
  • Online: 2019-03-01

摘要: 当前,隐私数据保护是信息系统安全的重要研究挑战,对应用程序进行隐私泄露检测是隐私泄露保护的有效方案.污点分析技术可以有效地对应用程序进行保密性和完整性的安全检测,提前报告出潜在的隐私泄露风险.然而,当前高敏感度的静态污点分析还存在开销过高的问题.通过对目前主流的污点分析工具FlowDroid进行深入分析,发现其污点分析计算中大量无关联污点传播是导致开销过高的重要原因,统计实验表明无关联传播占比高达85.2%.针对这一问题,尝试利用近年来一种有效的程序分析优化手段——稀疏优化——的方法,对静态污点分析中无关联的传播进行消除,达到时间和空间的开销优化.创新地将经典的数据流分析框架扩展成稀疏的形式,在此基础上提供了基于稀疏优化的污点分析方法.最后实现了工具FlowDroidSP,实验表明:FlowDroidSP在非剪枝模式下相比原FlowDroid具有平均4.8倍的时间加速和61.5%的内存降低.在剪枝模式下,具有平均18.1倍的时间加速和76.1%的内存降低.

关键词: 隐私泄露检测, 静态程序分析, 污点分析, 程序优化, 安卓

Abstract: At present, privacy preserving is an important research challenge of information system security. Privacy leak detection for applications is an effective solution for privacy preserving. Taint analysis can effectively protect the confidentiality and integrity of information in the system, and report the privacy leak risk of applications in advance. However, the existing static taint analysis tool still has the problem of high analysis overhead especially in high sensitive mode. This work first deeply analyzes that there exists a large number of unrelated propagation which leads to unnecessary expenses in current IFDS-based taint analysis, and statistical results show that the proportion of it is up to 85.5%. Aiming at this problem, this paper attempts to use an effective optimization method, sparse optimization in recent years, to eliminate the unrelated propagation in static taint analysis, and achieve the optimization of time and space cost. We have innovatively extended the classic data flow analysis framework (IFDS) into a sparse form, and provide a corresponding taint analysis algorithm. We implemented a tool called FlowDroidSP. Experimental results show that the tool has 4.8 times of time acceleration and 61.5% memory reduction compared with the original FlowDroid under the non-pruning mode. Under pruning mode, it has an average time of 18.1 times speedup and 76.1% memory reduction.

Key words: privacy leakage detection, static program analysis, taint analysis, program optimization, Android

中图分类号: