软件学报ISSN 1000-9825, CODEN RUXUEW E-mail:************ Journal of Software,2021,32(6):1701−1716 [doi: 10.13328/jki.jos.006245] ©中国科学院软件研究所版权所有. Tel: +86-10-62562563
基于污染变量关系图的Android应用污点分析工具∗
张捷,  田聪,  段振华
(西安电子科技大学计算机科学与技术学院，陕西西安  710071)
通讯作者: 田聪,E-mail:*****************.edu
摘要: 污点分析技术是检测Android智能手机隐私数据泄露的有效方法，目前主流的Android应用污点分析工具主要关注分析的精度，常常忽略运行效率的提升.在分析一些复杂应用时，过大的开销可能造成超时或程序崩溃等问题，影响工具的广泛使用.为了减少分析时间、提高效率，提出一种基于污染变量关系图的污点分析方法.该方法定义了污染变量关系图用于描述程序中污染变量及其关系，摒弃了传统数据流分析框架，将污点分析和别名分析进行结合，从程序中抽象出污染变量关系图和潜在污染流，并在控制流图上对潜在污染流进行验证以提高精度.详细描述了基于该方法所实现的工具FastDroid的架构、模块及算法细节.实验使用了3个不同的测试集，分别为DroidBench-2.0,MalGenome以及Google Play上随机下载的1517个应用.实验结果表明:FastDroid在DroidBench-2.0测试集上的查准率和查全率分别达到93.3%和85.8%，比目前主流工具FlowDroid更高，并且在3个测试集上所用的分析时间更少且更稳定.
关键词: 静态分析；污点分析；软件安全；隐私保护;Android应用
中图法分类号: TP311
中文引用格式: 张捷，田聪，段振华.基于污染变量关系图的Android应用污点分析工具.软件学报,2021,32(6):1701−1716. /1000-9825/6245.htm
英文引用格式: Zhang J, Tian C, Duan ZH. Taint analysis tool of Android applications based on tainted value graph. Ruan Jian Xue Bao/Journal of Software, 2021,32(6):1701−1716 (in Chinese).www.j
Taint Analysis Tool of Android Applications Based on Tainted Value Graph
ZHANG Jie, TIAN Cong, DUAN Zhen-Hua
(School of Computer Science and Technology, Xidian University, Xi’an 710071, China)
Abstract: The taint analysis technology is an effective method to detect the privacy data leakage of Android smart phones. However, the state-of-the-art tools of taint analysis for Android applications mainly focus on the accuracy with few of them addressing the importance of the efficiency and time cost. Actually, the high cost may cause problems such as timeouts or program crashes when the tools analyze some complex applications, which block them from wide usage. This study proposes a novel taint analysis approach based on the tainted value graph, which reduces the time cost and improves the efficiency. The tainted value graph is formalized to describe the tainted values and their relationships and the taint analysis and alias analysis are combined together without using the traditional data flow analysis framework. In addition, the taint flows are verified on the control flow graph to improve accuracy. The architecture, modules, and algorithmic details of the proposed tool FastDroid are also described in this paper. The tool is evaluated on three test suites: DroidBench-2.0,
MalGenome, and 1517 apps randomly downloaded from Google Play. The experimental results show that, compared
∗基金项目: 科技部重点研发计划(2018AAA0103202); 国家自然科学基金(61732013, 61751207); 陕西省科技创新团队(2019TD-001)
Foundation item: Major Program of the Ministry of Science and Technology of China (2018AAA0103202); National Natural Science Foundation of China (61732013, 61751207); Key Science and Technology Innovation Team of Shaanxi Provience (2019TD-001) 本文由“形式化方法与应用”专题特约编辑邓玉欣教授推荐.
收稿时间: 2020-08-29; 修改时间: 2020-10-26, 2020-12-19; 采用时间: 2021-01-18; jos在线出版时间: 2021-02-07
1702 Journal of Software软件学报 V ol.32, No.6, June 2021
with the tool FlowDroid, FastDroid has a higher precision of 93.3% and a higher recall of 85.8% on DroidBench-2.0, and the time cost for analysis is less and more stable on all the test suites.
Key words: static analysis; taint analysis; software security; privacy protection; Android applications
近年来，智能手机得到了广泛的普及和应用，智能手机成为人类生活工作中不可或缺的重要工具.在智能手机的操作系统中,Android系统占据主要份额，据统计，在全球手机操作系统中,Android系统的市场份额达到74.1%[1].智能手机的普及，离不开丰富多样的应用，用户可以通过安装在智能手机上的各种应用，实现其社交、娱乐、管理、支付等多种需求.然而，根据360安全公司2019年手机安全状况报告的数据,2019年新增的恶意程序样本约180.9万个，其中，隐私窃取类的恶意程序占41.9%[2].因此，智能手机应用的安全问题备受工业界和学术界的关注，特别是隐私数据保护问题成为安全问题的研究重点和热点.Android应用由于功能的需要，经常会存储和访问用户的隐私数据，例如通讯录、短消息、地理位置、账户密码等等.应用在获取用户授予的相关权限后，可以访问隐私数据并提供相应服务，比如：导航应用会实时获取用户的地理位置，从而计算道路规划并进行导航.然而，一些应用可能会过度申请权限或滥用权限，违规违法泄露和使用用户的隐私数据并造成严重的问题.比如：用户的银行账户密码泄露可能造成财产的损失，通讯录的泄露会严重侵犯用户的隐私.因此，智能手机的隐私数据保护具有十分重要的意义.
对于应用本身造成的隐私数据泄露(不包括用户使用不当、操作系统漏洞或网络攻击等)，有效地检测应用中代码包含的隐私泄露行为，是保护隐私数据的前提.污点分析(taint analysis)作为一种信息流分析技术，近年来被广泛应用于隐私数据泄露的检测[3].污点分析能够追踪应用程序中隐私数据从获取到泄露的整个传播过程，其中涉及诸多方面的研究，包括应用程序反编译、危险权限使用、隐私数据获取与泄露
方式、污染变量传播方式等等.虽然污点分析结果不能直接判定某项隐私数据的泄露是否是恶意的，但可以从中了解应用程序使用和泄露隐私数据的相关细节，从而帮助判定是否构成恶意行为.另外，恶意行为的判定，还需要根据应用功能及其行为发生的上下文(context)等具体情况进行具体分析[4].例如：地图类型的应用访问用户地理位置这一隐私数据是合理的，而要求获取用户通讯录通常是不正常的.总之，污点分析提供了应用获取和使用隐私数据的全貌，可为进一步深入分析应用、保护隐私打下基础.
目前已有的面向Android应用的精确的静态污点分析工具[5−8]往往关注分析的精度，忽略了分析效率和运行时间.在分析大规模复杂应用时，效率问题可能造成分析超时甚至程序崩溃[9,10]等问题，影响工具在现实中的广泛应用.本文提出一种基于污染变量关系图的Android应用静态污点分析方法，该方法摒弃了传统数据流分析框架，将污点分析和别名分析进行结合，从程序中抽象出污染变量关系图和潜在污染流，并在控制流图上对潜在污染流进行验证.实验表明：基于该方法实现的工具FastDroid在保证较高精度的同时，大大减少了分析时间，并且分析时间更加稳定.
本文的主要贡献包括以下3点:
(1)定义了用于描述污染变量及其关系的污染变量关系图;
(2)提出一种新的基于污染变量关系图的高效准确的静态污点分析方法;
(3)基于该方法实现了工具FastDroid，实验表明:FastDroid能够准确检测Android应用中的隐私数据泄露,
并且在运行时间上优于当前主流的静态污点分析工具.
本文第1节简要介绍Android应用污点分析的相关背景.第2节阐述基于污染变量关系图的污点分析方法的研究动机，给出污染变量关系图和污染传播规则的定义，并介绍方法的实施步骤.第3节详细介绍基于该方法的工具实现.第4节给出工具的实验和分析结果.第5节介绍相关工作.第6节总结全文并展望未来工作.
1  Android应用污点分析的相关背景
1.1  污点分析简介
污点分析是一种信息流分析技术，通过插桩、数据流分析等方法追踪程序中带污点标记的数据的传播以及
张捷等：基于污染变量关系图的Android应用污点分析工具1703
泄露情况[3,10].污点分析目前广泛应用于Android应用的隐私泄露检测，总体上可分为动态和静态两种方法[3]：动态方法主要在程序运行过程中对程序的行为进行监控，及时发现隐私数据的泄露，典型的面向Android应用的动态方法有TaintDroid[11],TaintEraser[12]等；静态方法是在不运行软件的前提下，对隐私数据泄露行为进行分析，分析的对象可以是源码、中间代码或目标代码等[13]，目前比较流行的面向Android应用的静态方法有FlowDroid[6],Amandroid[8]等.本文主要研究静态污点分析方法，相比动态方
法，静态方法拥有如下优势:(1) 覆盖全部代码，分析更加全面、准确;(2) 某些恶意应用能够检测出动态分析的运行环境，之后隐藏恶意行为从而逃避检测，而在静态分析中则不会出现此情况.
下面对污点分析用于隐私泄露检测中的常见概念进行解释.程序中，隐私数据的获取接口被称为污点源(source).隐私数据的泄露接口被称为泄露点(sink).程序在获取隐私数据之后，可以通过赋值、计算等方式在变量中对其进行传播，这些变量被称为污染变量(tainted value).污染变量可以是局部变量、静态变量或者对象的域等.隐私数据从污点源经过污染变量到达泄露点的传播过程形成的数据流可称为污染流(taint flow).图1是一个应用中两个函数的代码片段，图1(a)中的onStart生命周期函数调用了一个污点源getDeviceID用于获取设备ID 号，该隐私数据随后经过a,b,x,y等污染变量的传播，到达图1(b)中Send函数的一个泄露点sendTextMessage，该API可将隐私数据通过短信方式进行发送.图中，污染变量用红圈标记，污染流用蓝实线示意.这条污染流跨越两个函数，通过赋值、函数参数传递、字符串计算等不同方式进行传播.这些传播方式在污点分析方法中，一般需要抽象成为污染传播规则用于检测污染变量.
android软件1  )
getDeviceID
String b
//sink
b);
(a)(b)
Fig.1 An example of inter-procedural taint analysis
图1  过程间的污点分析示意图
1.2  Android应用污点分析工具实现的关键问题
(1) Android系统环境的模拟
Android应用具有事件驱动、多入口、多组件等特点，严格来说，应用不是一个能够独立运行的程序，甚至可以看作是Android操作系统的插件[14].应用中没有类似Java程序的main函数，各组件的生命周期函数或者回调函数根据用户互动或设备事件触发而由系统环境直接调用，在代码中缺少这些函数之间明确的调用关系.因此，传统Java程序分析工具不能直接使用在Android应用上.为了准确分析Android应用，我们需要对Android系统环境进行模拟，生成完整准确的函数调用图、控制流图等程序结构.另外，一个Android应用可由多个组件构成，隐私数据可在不同组件间传播，通常将隐私数据封装在用于组件间通信的专用对象Intent中，显式或隐式地传送到另一个组件.因此,Android应用的污点分析需要获得所有组件间通信信息用于支持组件间分析.目前，研究人员已经提出一些分析组件间通信的工具，例如IC3[15],Epi
cc[16]等.
(2) APK文件的反编译
Android应用的安装文件是Android应用程序包(Android application package)，文件格式是APK文件.该文件由多个文件组合压缩而成，包含dex文件、文件资源、证书、manifest文件等.其中，与源代码最为相关的是dex文件，它是在Android的Dalvik虚拟机上运行的可执行文件.因为dex文件中的字节码不利于直接分析，工具往往首先将该文件反编译为中间代码(IR)或者源码方便操作.常见工具和中间代码有Soot[17]生成的Jimple、APKtool生成的Smali[18]、Androguard[19]生成的DEX_ASSEMBLER等等.比较成熟的反编译工具不仅可以生成中间代码，而且提供在中间代码层面上进行程序分析的操作接口，用于获取程序中的语句、变量等详细信息，甚至可以直接生成函数调用关系和控制流图等信息.
1704 Journal of Software软件学报 V ol.32, No.6, June 2021
(3) 污点源和泄露点的识别
Android应用中存在许多污点源和泄露点的方法，污点分析需要准确识别出程序中的污点源和泄露点.常见的污点源可通过调用Android SDK中相关API获取隐私数据，有些隐私数据可通过Android组件内容提供器(content provider)获取，例如通讯录数据，但最终访问数据时仍需调用相应的API.研究初期的检测
方法主要从Android的SDK中手工筛选出与污点源和泄露点相关的API，但这种方式收集的API并不完整.Rasthofer等人[20]针对这个问题提出了一个较全面的方案，基于对污点源和泄露点的规范定义开发了工具SUSI，利用机器学习的方法出Android所有API中存在的符合定义的大量污点源和泄露点并进行归类.
(4) 污染传播规则的定义
污点分析需要根据污染变量传播的特征归纳出污染传播规则，并依据规则设计相应算法追踪污染变量.一般来说，污染传播规则包括污点源和泄露点的识别规则、污染变量的数据流规则和别名规则等.例如:FlowDroid 工具[21]定义了基于污染传播规则的流方程，并为别名分析专门设计了独立的流方程.在IFDS框架下，流方程实际上实现了分析语句时所采用的规则.同样,Apposcopy工具[5]的静态污点分析模块专门定义了污点源、泄露点和污染传播的谓词和规则，并基于此规则进行污点分析.如果从污染变量的传播关系上看，隐私数据在污染变量之间的常见传播方式可包括赋值、参数传递、计算、别名等.需要注意的是：别名分析是污点分析中需要解决的重要问题，当某变量被污染后(即被传入隐私数据)，它的别名变量同样会被污染，因为在Java中，堆变量的所有别名都指向同一块内存.另外，工具的实现需要考虑Android或Java平台的一些特殊污染方式，并单独设计对应的污染传播规则，比如应用中存在涉及线程、隐式污染流、native代码、组件间通信、反射机制等特殊的传播方式，这些方式无法归纳到通常的规则当中，需要根据具体特征来定义规则.总之，为了识别不同污染传播方式所产生的污染变量，污点分
析应尽可能全面地定义污染传播规则以提高分析精度.
(5) 敏感性的支持
静态分析方法，对不同敏感性的支持直接影响分析的精度和速度，例如流敏感、对象敏感、域敏感、上下文敏感、路径敏感等敏感性[10].具体来说，支持流敏感需要在分析中考虑各语句的执行顺序，一般要求工具获得准确的控制流图.支持对象敏感的方法能够准确识别某个对象，在分析该对象的域或者方法时，不会与相同类的其他对象混淆，即工具需要区分同一类的不同对象.支持域敏感的方法在分析中能够区分对象中的每个域，工具需记录域的信息.支持上下文敏感需要分析函数在不同位置调用所产生的影响，工具需记录函数调用点相关信息.支持路径敏感需要分析程序各执行路径不同所导致的不同结果，工具需考虑程序分支等细节.静态分析方法对敏感性的支持在设计和实现中的精度和复杂性差异很大，一般来说，敏感性支持得越多，分析精度越高，但随之，工具实现越复杂、分析成本越大、速度越慢.精度与速度之间往往存在矛盾，需要在二者间进行平衡[13].
2  基于污染变量关系图的污点分析方法
2.1  研究动机
目前，精确的静态污点分析方法大多基于数据流分析框架，在控制流图上对隐私数据进行追踪和分析，
另外单独对污染变量进行别名分析.例如:Amandroid[8]提前对所有变量进行大规模的别名分析之后，再进行污点分析；而FlowDroid[6]则是在发现污染变量是堆变量后，才按需进行反向的别名搜索.虽然FlowDroid仅针对污染变量进行别名分析，开销相对Amandroid小一些，但在实验中我们发现:FlowDroid在分析大规模复杂的应用时，一个应用花费的时间常常达到几分钟至几十分钟，甚至出现超时或运行失败的情况.所以我们认为，目前的方法在运行效率上仍存在提升空间：一方面，当程序中污染变量的别名较多时，独立运行的别名分析将不可避免地产生很大的开销；另一方面，传统的数据流分析框架不是专门为污点分析定制的，框架本身的运行开销很大.
为了提高工具效率，我们提出一种新的污点分析方法，该方法摒弃了传统数据流分析框架，采用一种轻量级的算法构建出污染变量关系图，将别名分析和污点分析同步进行，也就是在追踪污染变量的同时识别污染变量的别名.方法的大致步骤如下：首先，从一个应用的程序中抽象出一个树形结构，扫描所有树形结构的叶子节点(即语句)，基于污染传播规则检测所有可能的污染变量及其别名变量；然后，根据变量关系生成污染变量关系图,
张捷等：基于污染变量关系图的Android应用污点分析工具1705
确定潜在污染流；最后，在控制流图上对污染流进行验证，得到程序中真实存在的污染流.为此，我们形式化定义了污染变量关系图，设计了污染传播规则和验证污染流的算法.
2.2  污染变量关系图
我们提出污染变量关系图(tainted value graph，简称TVG)用于描述程序中所有可能存在的污染变量、别名变量及变量间的污染传播关系.直观来看，所有污染变量都是由污点源传播得到的，污染变量及其别名变量通过各种污染传播方式不断扩散，最终传播到一个泄露点，形成一条泄露隐私数据的污染流.为准确表达这样的污染传播过程，我们使用图的结构记录变量及其传播关系.下面给出污染变量关系图的定义：污染变量关系图是一个简单有向连通图TVG=(V,E)，其中，顶点v∈V表示一个污染变量、污点源或泄露点，边e∈E表示两个变量的污染传播关系、变量被污点源污染或者污染变量传播给泄露点的关系.另外，我们要求TVG满足以下性质.
•有且仅有一个入度为零的顶点，即污点源顶点SC i；存在零或若干泄露点顶点SK j;
•除了SC i以外的所有顶点都至少存在一条从SC i到该顶点的路径;
•图中不含回路.
从性质来看，每个TVG对应一个污点源在程序中的传播过程.当一个应用中存在多个污点源时，则可生成相同数量的TVG，而污染流能否形成取决于图中是否有污染变量被泄露.例如，图2显示了图1程序中的TVG，整个程序中存在许多变量，用空心圆圈表示，其中，红空心圆圈是污染变量，红实心圈表示
污点源，蓝实心圈表示泄露点.该TVG的顶点集V={SC1,a,b,x,y,SK1}，边集E={(SC1,a),(a,b),(b,x),(x,y),(y,SK1)}.在现实中，污染变量之间的关系可能更加复杂，存在一对一、一对多和多对一的情况.举例来说：当某污染变量分别污染多个不同变量，或者作为参数传入到多个函数，此时，该变量的顶点将连接多条边到其他顶点；当两个不同的污染变量都
作为同一参数调用某函数时，此时，两个污染变量的顶点将各自连接一条边到该函数形参的顶点上
.
Fig.2 An example of tainted value graph
图2  污染变量关系图示例
2.3  污染传播规则
我们定义了一系列污染传播规则用于发现污点源、污染变量及泄露点，并创新性地将别名规则也作为一类污染传播方式加入到规则中.这样，在分析中可同时寻污染变量及其别名，并一同构成TVG.污染传播规则采用类似Datalog的语言来定义,Datalog[22]是一种应用于数据库查询的语言，由于其较强的逻辑性，被广泛应用于各类研究领域，例如程序分析、信息提取等.一段Datalog程序由一套规则和一组事实组成，事实由谓词描述.每条规则由左右两部分构成，中间用:-符号分隔开.当右部所有谓词都成立时，左部的谓词为真.对于污染传播规则来说，当语句及其包含的变量满足某项规则右部的所有谓词时，左部的变量污染传播关系存在或者某个描述变量或方法性质的谓词成立.
我们定义了S,IN,Param,Return,ReturnP,Clean,hp等谓词用于描述程序中语句或者变量的性质.S(stmt)谓词描述了语句stmt的类型，当满足特定类型的语句时，谓词为真;IN(x)为真，表示变量x是污染变量;Param(f,x,i)为真，表示函数f第i个参数被传入污染变量x;Return(f,x)为真，表示函数f返回污染变量x;ReturnP(f,x,i)为真，表示函数f第i个实参在函数内被变量x污染;Clean(x)为真，表示污染变量x被清除;hp(x)表示x为堆变量.规则中的Source,Sink分别表示污点源和泄露点方法的集合,TW表示污染封装方法集合.污染封装方法是指在Java和

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。