2016年5月18日—20日的Google I/O大会上，谷歌官方透露，在过去一年时间里安卓用户通过Google Play商店下载安装应用的数量已超过650亿^[1]。应用市场下载量大，其中的应用程序下载量更是无法估量，其安全性也更加重要。如应用程序中的越权现象容易被恶意攻击者利用，将用户的隐私数据发送到用户未知的地方，给用户的隐私数据造成威胁。如果用户是企业级用户，则可能面临企业商业数据和资料泄漏等更严重的威胁^[2]。因此，待安装应用程序，均需进行隐私泄漏检测。

针对Android应用程序的隐私泄漏，目前最有效的研究方法之一就是污点分析。污点分析方法中主要由泄漏源(source)和泄漏点(sink)组成。污点分析中的泄漏源是一些涉及用户隐私的敏感信息，如电话簿、数据库、文件、电子邮箱、定位信息、SMS/MMS和用户手机信息(电话号码)等。而污点分析中的泄漏点则是隐私信息从用户系统流向未知方的API。泄漏给未知对象的Android系统中，最常见的泄漏点如Internet、SMS通信相关API等。污点分析方法的目的是在一个应用程序中寻找是否存在从泄漏源到泄漏点的一条畅通路径。如果存在一条路径，从泄漏源到泄漏点就可以定义为存在一个隐私泄漏的实例。

污点分析包括动态分析和静态分析2个方向。动态分析，即将应用程序安装在Android设备后，运行应用程序并实时跟踪数据流。动态分析研究方法有Enck等提出的TaintDroid^[3]、Hornyack等开发的AppFence^[4]，以及在TaintDroid的基础上进行改进的动态分析工具Kynoid^[5]等。但是，动态分析方法的不足在于只能检测出应用程序运行时的执行路径，对于未执行的代码，缺乏观察性，代码的覆盖率不是很高。此外，此类方法需要更改DVM，如TaintDroid在每次检测都要提前更改Android设备的DVM，如果Android设备的厂家(如Samsung)不同或同厂家不同版本(如Android 4.2和Android5.0)，则需要多次更改DVM。这样的方法平台普遍率低，在应用程序的实际检测中工作量会非常大。而静态分析方法，则是在应用程序安装在Android设备上之前，单纯对应用程序开发者提交的apk数据包进行分析。静态分析方法尝试覆盖应用程序的所有可执行路径，代码覆盖率高，并且独立于Android设备的厂家和版本，因此，在预先防范和代码覆盖率上，静态分析方法的效果更好。在静态分析隐私泄漏方面的研究有Yang等提出的静态分析工具LeakMiner^[6]、Zhao等提出的TrustDroid^[7]、Fritz等提出的FlowDroid^[8]，以及AndroidLeaks^[9]和ScanDal^[10]等。以FlowDroid为例，该工具是基于开源语义分析工具Soot^[11-13]开发的，并在一些含漏洞测试平台如DroidBench上进行了一定的测试。FlowDroid优点为运行速度快，代码覆盖率高，但实际应用中利用其进行隐私泄漏分析后，仍需要人工查询Android API文档，判断结果文件里的泄漏信息是否包含合法API，即是否误判。其他的静态分析工具也同样存在类似的问题。鲜晓东等^[14]根据乘客的运动行为判定公交的客流计数，为管理者提供决策的依据和评判公交运营质量的标准。据此思想，提出相似性分析思想，将Android应用程序进行分类化隐私泄漏分析。如“天气预报”应用程序和“美颜相机”应用程序分别类属于天气类应用程序和相机类应用程序。

本文在静态分析工具FlowDroid的基础上，设计并实现了自动化检测方法——LeakDetector，为第三方应用市场安全审核者、企业级用户或个人提供应用程序隐私泄漏分析。与其他静态污点分析方法相比，LeakDetector利用相似性思想，采用随机森林算法，通过森林中各CART树的投票，提高了隐私泄漏结果合法性的判断。并且生成的泄漏数据库集合和判断决策森林，都可以复用，减少了同类型应用程序检测的成本。除此之外，LeakDetector提供了逆向定位功能，满足检测人员对结果准确定位的要求。

1 LeakDetector系统的设计及实现 1.1 LeakDetector系统总体设计

LeakDetector整体流程图如图 1所示。

其主要流程有：

1)将应用程序存在的泄漏源/泄漏点规范化处理，然后把应用程序中存在的可疑隐私泄漏源/泄漏点即source/sink导入到泄漏数据库中。

2)利用泄漏数据库生成分类型判断决策森林，用以判断同类型的应用程序是否存在隐私泄漏情况，若有，则输出预测的隐私泄漏类型。

3)对于利用决策森林判断的结果，如果需要进一步定位泄漏点，LeakDetector提供了根据泄漏数据库逆向查找具体泄漏源/泄漏点位置的功能，输出具体的隐私泄漏类型、泄漏源/泄漏点的位置。

1.2 泄漏数据库的设计及相关实现 1.2.1 重构泄漏源/泄漏点apisum文件

泄漏源(source)和泄漏点(sink)在Android应用程序中以Android开发文档中敏感API的形式存在。提取source和sink，其实就是定义一个包含各种可能存在隐私泄漏的Android API的文件。在执行静态分析的过程中，用该文件对应用程序中的代码进行过滤和提取。如果存在文件中的一个source到一个sink的路径，则就可以定义为一条隐私泄漏实例。后面简称泄漏点/泄漏源apisum文件为apisum文件。设apisum文件中有n个source、m个sink，集合中source和sink一一映射，有n×m种泄漏可能，如图 2所示。

由于每个类型的Android应用程序的隐私泄漏情况不同，如在相机类应用程序中，检测到一个Location类API即source1的使用，存在一个sink1，如SMS中的sendMessage，且source1和sink1之间存在一个畅通的路径，就认为该应用程序存在一种隐私泄漏；而对于天气类的应用程序，必须通过Location类API定位到用户所在的地理位置，才能提供该应用程序的正常功能。根据相似性分析思想，将应用程序根据相似性功能进行分类。同功能的应用程序中如果某个可疑API (如上述天气类应用程序中的Location类API)的出现有普遍性，则认为该可疑API是正常请求的，将其从最初汇总的apisum文件中删除。

本文以天气类应用程序为例进行隐私泄漏分析。针对于天气类应用程序，着重在网络、文件(I/O)、SMS、本地数据库和日志方面的隐私泄漏进行检测。具体例子如下：

1) TelephonyManager尤其是getLine1Number ()是天气类应用程序不需要获取的信息。

2) android.os.Handler中的android.os.Handler:boolean sendMessage (Message msg)作为泄漏点，天气并不需要发送信息出去。同样地，也不需要读取短信，如android.os.Handler:android.os.Message obtainMessage ()此类方法即可定义为泄漏源。

3) java.io.OutputStream中的write方法，如void write (byte[])。

4) android.util.Log和java.io.FileOutputStream两个记录日志和文件输出控制流的相关方法。

5) android.database.sqlite.SQLiteDatabase:android.database.Cursor对数据库的访问需要警示，以防非法访问用户的隐私数据库。

1.2.2 规范化source和sink数据的输出格式

由于InfoflowResults中的ResultSinkInfo和ResultSourceInfo的类结构复杂，而机器学习评估的输入要求精简，所以需对ResultSinkInfo和ResultSourceInfo中的函数字段进行提取和简化。

简化规则如下：屏蔽ResultSinkInfo字段中的accessPath字段，只保留Stmt类型的sink字段。在其原有结构的基础上，用“❬”“❭”进行分割，仅提取所调用API的方法字段，包括包名、返回类型、方法名及其形参；考虑到Xml输出“❬”“❭”会出现转义误差，导致之后重复性判断错误，所以将如java.net.URL:void❬init❭(java.lang.String)方法中的“❬”“❭”替换成“0”。

ResultSourceInfo类的结构比ResultSinkInfo要复杂，一个sink可能对应多个source，所以ResultSourceInfo类中的source字段存储的是一个sink对应的一系列source组成的集合。故数据的处理过程先要解析集合、组建集合，然后返回一个由规范化格式后的多个source组成的集合。

1.2.3 建立泄漏数据库

根据相似性分析思想，为某一个类型的应用程序建立针对性的泄漏数据库，存储该类型应用程序可能存在的隐私泄漏数据流和泄漏类型。

在建立泄漏数据库时，需要消除泄漏数据库中的冗余信息。在检测一个应用程序app1的隐私泄漏情况时，将其中一条泄漏数据流，如从数据库读取数据到发送SMS，记为flow1。如果在app1的检测过程中多次出现flow1，之后将泄漏数据流导入到泄漏数据库时就会出现很大的冗余。为了消除这种冗余情况，提出了重复性判断方法。即每条泄漏数据流导入泄漏数据库前，先将其进行重复性判断，丢弃重复的泄漏数据流，将非重复的泄漏数据流导入到泄漏数据库中，由此保证泄漏数据库中的每条泄漏数据流的唯一化。为方便查找和构建，创立.xml类型泄漏数据库，以树的结构在本地磁盘上存储应用程序存在的漏洞数据流。初始化树的根节点为privacyflow。

具体的导入思想如下：

由于sink和source以一对多构成的集合组成了InfoflowResults，所以对给定一个sink2进行重复性判断，将sink2无冗余地导入到泄漏数据库的根节点(privacyflow)的分枝下，即如果sink2之前不存在，新添一个子节点，元素为sink，其值为sink2的值；如果sink2已经存在，则忽略。然后以sink2的值为搜索关键字，定位到值为sink2的sink节点，将其中的source列表中的每个值进行重复性判断，保证无冗余地加入到该sink节点下，方法同上所述，若存在则忽略，若不存在则添加。

以导入source2为例，sink2为泄漏数据流中source2对应的sink。定义ψ(sink)为泄漏数据库中所有sink组成的集合。若sink_i∈ψ(sink)，定义ψ(source_i)为sink_i对应的所有source_i组成的集合。t为Xml类型泄漏数据库。

上述方法不断循环，直到应用程序中的所有泄漏数据流全部无冗余地记录到泄漏数据库中。

算法1 重复性判断算法

1) Procedure SourceXml (Input:sink, source Output:t)

2) Begin

3) For sink_i∈ψ(sink) Then

4) Do遍历ψ(source_i)中元素

5) EndFor

6) If sink_i∈ψ(sink)且source_j∉ψ(source_i) Then

7) Do将source_j加入到对应sink_i子分枝下

8) EndIf

9) End SourceXml

1.3 判断决策森林的设计和生成

由于同类型应用程序样本泄漏数据库太多，数据分析量大，假设apisum文件中有n个source、m个sink，根据映射思想，泄漏数据库中最多有n×m条泄漏数据流记录。所以，引入机器学习的方法对泄漏数据库中的数据进行相似性投票分类，生成判断决策森林，根据分类结果对新的应用程序进行隐私泄漏合法性判断，实现自动化，并用随机森林中各树的投票进一步筛选相似性安全的/必需的API，并提高查询泄漏数据库的速率，减少误判。

1.3.1 构建机器学习输入用例

将泄漏数据库中的泄漏数据流，进一步简化(只录入方法名，忽略所在类、返回类型及形参)，将简化后的数据流录入到2维表中，并手动添加对应的泄漏数据类型。所有数据流添加完毕后，把文件转化为.arff文件，以作为随机森林算法的输入，使数据进行机器学习。泄漏数据流如表 1所示。

1.3.2 构建决策森林

为提高对泄漏数据流随机性评估的正确性，采用随机森林的算法。随机森林指的是利用多棵树对样本进行训练并预测的一种分类器。随机森林就是由多棵CART (lassification and regression tree)树构成的。对于每棵树，它们使用的训练集是从总的训练集中有放回地采样得出，这意味着总的训练集中的有些样本可能多次出现在一棵树的训练集中，也可能从未出现在一棵树的训练集中。

由于随机森林的算法结构，在判断泄漏类型时，森林中的每棵CART树进行投票，最后票数高的结果为最终泄漏类型。此种方式导致随机森林在平衡误差方面比决策树C4.5效果要好，故选取随机森林作为系统有效性的评估算法。

随机森林中决策树的伪代码见算法2。其中，datafile为在源数据中提取的训练样本，tree为生成的一棵决策树，ψ(remainAttrs)为目前剩余的特征，remainData为剩余样本数据，tV为以attr₁特征划分的结果类型，min为上次计算最小Gini指数。

算法2 随机森林部分伪代码

1) Function BuildTree (Input:datafile Output:tree)

2) Begin

3) For attr₁ ∈ψ(remainAttrs) Then

4) Do

5) $Gin{i_{attr1}} = 1 - {\sum\limits_{i = 1}^n {\left[ {\frac{{typ{e_i}}}{{tV + \neg tV}}} \right]} ^2}$

6) $Gin{i_{\neg attr1}} = 1 - {\sum\limits_{j = 1}^m {\left[ {\frac{{\neg typ{e_j}}}{{tV + \neg tV}}} \right]} ^2}$

7) $Tmp = Gin{i_{attr1}} * \frac{{tV}}{{tV + \neg tV}}$

8) $\neg Tmp = Gin{i_{\neg attr1}} * \frac{{\neg tV}}{{tV + \neg tV}}$

9) $Gini = Tmp + \neg Tmp$

10) If Gini < min Then

11) min=Gini

12) attr₁为目前最合适划分特征

13) EndIF

14) EndFor

15)tree=attr₁, attr₁为划分特征，remove attr₁构建子树

16) IF attr₁未重复Goto 3

17) End BuildTree

将第1.3.1节生成的文件作为输入，用随机森林算法对数据进行训练，生成用于天气类应用程序隐私泄漏检测的判断决策森林。并将出现概率为70%及以上的泄漏类型定义为正常使用API，利用相似性思想，将其排除到危险隐私泄漏类型之外。

2 测试模块的设计及实现

在15个应用市场中，收集了65个天气类型应用程序，根据apisum文件的过滤，将每个应用程序中所有的泄漏源方法和泄漏点方法组成的泄漏数据流无重复地导入到单样本泄漏数据库中，添加相应的泄漏类型，构成单样本泄漏数据库。将65个单样本泄漏数据库作为输入，输入到随机森林生成器中，训练泄漏数据记录，生成判断决策森林。给定一个新的同类型的(文中为天气类)应用程序，格式化输出泄漏数据流，提取单样本泄漏数据库，导入到判断决策森林中进行检测。如果得到检测结果后需准确定位，则运行逆向定位程序，根据判断决策森林输出的泄漏类型，定位到应用程序中存在的source到sink的数据流集合。

部分算法如下：定义threadres为泄漏类型，事先已自定义，用于记录应用程序存在的信息泄漏的泄漏类型。

算法3 逆向分析部分算法

1) Procedure SourceXmlCompare (Input:sink, source, apk Output:threadres)

2) Begin

3) For sink_i∈ψ(sink)

4) If

 ∃source₁∈ψ(source_i):source₁==source

 Then

5) If source₁存在子元素Then

6) threadres=source₁子元素的值

7) EndIf

8) EndIf

9) EndFor

10) End SourceXmlCompare

3 实验

本文基于开源语义分析工具Soot和静态污点分析工具FlowDroid设计了自动化隐私泄漏检测系统——LeakDetector。实现了泄漏数据库的构建、判断决策森林的生成和泄漏类型预测与逆向定位泄漏点3个功能。根据实例测试方法，收集65个天气类型应用程序，生成367例实例，并构建了.xml型泄漏数据库。以数据库的简版作为输入，采用基于随机森林算法的机器学习构建判断决策森林。取一个待检测的天气类Android应用程序“YM天气”，利用判断决策森林进行隐私泄漏分析。并利用逆向定位方法，准确定位泄漏源/泄漏点所在包、类及具体方法名。

将“YM天气”的泄漏数据输入到判断决策森林中，结果如图 3所示。

72条实例中，通过泄漏数据库筛选过滤，共12条泄漏警报，其中，4条phoneinfo-internet-thread (从网络泄漏设备信息)，4条phoneinfo-log-thread (将设备信息记录到本地数据库)，2条log-content-thread (将本地数据库内容通过上下文信息传出去)，1条log-internet-thread (将数据库中信息通过网络传出)，1条internet-file-thread (将文件中内容通过网络传出)。但是，只有1例泄漏数据被误报。隐私泄漏的判断正确率为91.6%。

(泄漏类型：sink，source)为一条记录，逆向定位泄漏源/点方法的输出是由上述记录形式组成的泄漏集合。定位泄漏源和泄漏点的部分结果如图 4所示。

图 4中，第1条数据显示将设备信息从网络API泄漏出。source为getDeviceId，即获取设备的IMEI；sink为初始化了URL的实例。并且source和sink间有完整路径，可以将用户的IMEI串通过URL泄漏出去。FlowDroid分析的结果存在冗余，且无相似性判断，会导致应用程序中正常使用的API被误报为隐私泄漏威胁。如第1.2.1节所述，天气类应用程序中的定位类API，是应用程序正常运行所必需的API，若提取到此类API，对用户发出警告，则会造成冗余困扰。用FlowDroid对“YM天气”应用程序的分析数据如下：80条隐私泄漏数据，包括55条正常API使用数据流、13条API冗余记录数据流，和12条隐私泄漏数据流。针对FlowDroid的不足，LeakDetector消除了隐私流的冗余，并通过决策森林的投票结果，进一步消除“正常使用且被误判”的API。同时提供逆向定位查找的功能。

目前，存在的隐私泄漏工具(如TaintChaser, 一个面向Android的隐私泄漏检测系统)，基于动态分析方法实现了对隐私数据的细粒度分析，精确跟踪数据的流向。但是，其仍存在之前动态分析方法存在的不足，即检测应用程序，需要污染DVM，平台的普遍性差，因为每个厂商的不同设备，都需要重新污染其DVM。而同类型的隐私泄漏静态分析工具，如Amandroid^[15]，缺乏分类性，对如天气类的应用程序中存在的“Location”类API仍会报错，此类合法性API的误报率略高。而且对于应用程序来说，每次分析全程单次有效，若分析大量同类型应用程序，成本较高。而LeakDetector通过收集同类型的应用程序对其进行相似性分析，降低上述误判率。并通过随机森林算法提高对合法API判断的精准度。对于生成的泄漏数据库和判断森林，仍可留作下次同类型应用程序的隐私泄漏情况检测，降低了分析成本。LeakDetector的逆向定位功能，能够方便应用程序审核人员对应用程序隐私泄漏情况的准确定位。

4 结论

LeakDetector是一个面向Android应用程序的自动化隐私泄漏检测方法，用于为第三方应用市场审核者提供分类化应用程序隐私泄漏的分析方法。主要包含3个部分：分类化泄漏数据库、泄漏分析决策森林以及泄漏类型预测与逆向定位泄漏源/泄漏点。将LeakDetector直接部署在第三方市场的服务器端，通过更新相应apisum文件便可在某应用类别的应用程序开发者提交应用程序apk时，对应用程序进行隐私泄漏检测。在发布到用户可见平台之前，对应用程序中存在的潜在隐私泄漏威胁进行一定的防范，从而为用户隐私的安全性提供一定的保障。

相比于传统的静态分析工具，LeakDetector简化了对人工的要求，如不需要对Android API文档的全面掌握，并且利用相似性分析提高了应用程序隐私泄漏误判的概率。

本系统只对常用应用程序的中应用程序进行了分析，如果应用程序使用了加壳或混淆代码的话，就会影响系统的正确率。因此，下一步研究工作将从复杂应用程序角度继续优化系统，为用户的隐私保护提供更高一层的保护。