作者： Yuhong Nan, Zhemin Yang, Xiaofeng Wang, Yuan Zhang, Donglai Zhu, Min Yang
单位： Fudan University, Shanghai Insitute of Intelligent Electronics & Systems, Shanghai Key Laboratory of Data Science
出处： NDSS’18
对于检测移动应用中的隐私泄露问题来说，自动化检测是一个长期存在的挑战。现有的解决方案则是通过系统API和APP服务端返回内容去着手分析。本文作者提出了一种分析Android APP的新方案。作者认为，程序代码中的方法名、变量名、常量等信息，尽管在轻量级混淆的情况下依旧包含着丰富的语义信息。所以作者通过自然语言处理（NLP）去自动化地定位程序中变量名、方法名等敏感元素，然后使用基于学习的程序框架分析这些真正存在敏感内容的代码。作者通过这种方法分析了445668个app。
I. INTRODUCTION
许多移动APP都是采用了使用第三方SDK的方式组合在一起而不是直接编写的方式，这些SDK通常建立在现有Web服务之上（例如，分析或单点登录）。 然而这种功能组合就有可能通过第三方的SDK泄露用户的隐私。大多数研究员都揭示了第三方lib，例如广告lib，和和数据收集软件会手机敏感设备信息，例如IMEI，手机号，GPS定位数据。作者给出了一个国产的新闻APP——The-Paper使用第三方的ShareSDK去分享新的文章到微博的流程示例。
不同于获取用户的密码需要用户与UI的交互，示例中的ShareSDK可以在The-Paper分享文章的时候，从微博获取用户微博账号的Token和资料。整个过程对于第三方的ShareSDK来说是完全暴露的。ShareSDK是有可能在用户以及The-Papre开发者不知情的情况下把用户的隐私数据上传到ShareSDK上的。作者所做的事情就是使用自动化的方式去分析此类SDK是否可能在其代码中包含此类功能的实现。
Leakage analysis: challenges
要想发现隐私泄露的地方，首先要定位到获取用户隐私，例如IMEI、GPS数据，的API所在的地方。此类代码通常是使用系统API去获取数据的。但是单独定位这些API是不够的。作者认为还有很大一部分的数据是用户输入数据到文本框来获取的，例如UI上一个Password或者Home Address这样字符串标注的文本框。还有更复杂的情况，比如APP通过本地存放用户数据的文件，或者通过APP内的逻辑代码向服务器获取数据。
作者研究的关键点是APP中包含的大量语义信息。例如下面一个SnapTee APP的代码：
这些双引号引起来的字符串包含了丰富的语义信息揭示与之相关的参数的含义。更进一步，这些程序的元素会被以一种特殊的格式排列，例如LOC:12-16中的代码，是多组键值对的形式存储在哈HashMAp中的数据，这些语义信息有助于数据流的追踪。
Semantic clue discovery
基于以上的分析，作者把包含敏感隐私数据的语义叫做clue，并构建了一个叫做ClueFinder的自动化分析框架。ClueFinder会使用关键字，词头，和特殊的缩略词去分析程序中的元素（方法名，变量名，常量等）。在分析这些元素所包含的语义的时候，作者使用自然语言处理（Natural Language Processing - NLP）去排除不包含敏感信息语义的代码。
Learning-Based identification
尽管使用NLP去解决语义分析的问题，但是还是会不可避免地会出现误报和漏报。例如对于一个语句setMessage(“are you sure to delete account?”)，其实与用户的账户信息无关，但是会出现误报的情况。为了解决这个问题，ClueFinder使用机器学习的方法，根据一组关键程序结构特征对包含这些元素的程序语句进行分类。例如上图中的LOC:14，basicInfo.put()中包含了敏感关键词location和与之对应的数据类型locationStr，这种形式就类似一种键值对的展示。这种情况就可以帮助排除前面提到的setMessage(“are you sure to delete account?”)的误报情况。最后ClueFinder对APP中包含敏感数据操作的代码识别率可以达到91.5%。
Measurement and findings
此部分描述了作者所选取的样本，作者从两个不同的APP商店选取了445668个应用。检测结果显示26.5%的应用暴露了他们客户的隐私信息给3502个第三方lib。在2015年Google Play上13500个最受欢迎的APP中，39.9%的应用暴露用户隐私给了709个第三方lib。每个APP平均分享了7.6条隐私数据条目（地址，资料等）给至少两个第三方lib。只有很少一部分APP只是在本地使用这些数据而没有上传到云端。
Contributions
本论文中，作者一共有以下贡献：
- 使用了一种新型的技术去检测敏感数据泄露；
- 设计并实现了一种予以驱动的技术去自动化地检测APP中敏感数据相关的代码；
- 大规模地分析了APP中第三方库隐私泄露的风险。
II. BACKGROUND
App leakage analysis
现在所使用的自动化的隐私泄露分析有很多都是基于数据流的污点跟踪去分析APP代码，但是这样的做法依赖于Android API返回的敏感值，所以需要手动地对数据源进行标记，如果使用代码中相关的语义去辅助分析的话，会对精确度有很大的提升。
Natural language processing
CLueFinder使用了自然语言处理中一些关键技术去处理代码中的语义：
- Stemming
因为变量名中会有很多的缩写，所以使用词干来对单词进行分类可以获得较大的命中率。比如说，change就是changing和changed的词干。而addr就是address的词干，那么addr就可以匹配到user_addr。
- Parts-Of-Speech
POS技术用来定位这些单词所组成的语句中是否是和隐私泄露相关，例如address是一个敏感的单词，但是address this problem中，则是不敏感的语句。
- Dependency relation parsing
对整个语句进行依赖关系解析，实际上就是把自然语言的语句经过编译器前端的语法分析生成AST一样生成类似的parse-tree。
Assumptions
作者并不考虑那些经过了很强的混淆的APP，因为它们移除了绝大部分丰富的语义信息。作者只考虑被轻量级混淆的应用或者开发者所使用的第三方lib没有被混淆的应用。事实上许多APP开发者处于避免影响自己应用正常运行的目的， 并没有混淆自己应用中数据相关的代码和第三方lib。
III. CLUEFINDER DESIGN
A. Design Overview
ClueFinder有三部分组成：Semantic Locater，Semantic Checker， Structure Analyzer， Leakage Tracker。对于一个APP，Semantic Locater首先会反汇编然后确定程序是否包含敏感的token。这些敏感元素包含字符串常量，变量，和方法名在内都是由Semantic Chekcer使用NLP进行识别处理。接下来会判断这些元素，是否是敏感的。最后通过Tracker结合APP代码中语义信息使用数据流和可达分析这些敏感信息的传播。
B. Semantic Clue Locating
Semantics Locator
为了确认程序中的元素是否是隐私相关的，作者使用数据集去判断是否敏感并使用关键词与之绑定。作者使用Google Privacy Policies 去区分35种数据是否是隐私内容。这些数据进一步被被ClueFinder分成四类，包括用户ID，用户属性，定位信息和账户信息。一共有121个关键词或关键词对，如下表所示：
对于反编译的程序代码中的所有元素，ClueFinder对它们进行分词， 然后使用四种数据类别及其表示的token匹配这些元素。 涉及隐私相关标记的元素会在接下来进行的语义分析步骤中进一步分析。因为这并不一定意味着这些元素确实与隐私有关。 例如，getStreetViewActivity方法包含敏感关键字street，但实际上与用户的位置信息无关。 为了消除这些误报，作者使用Semantic Checker来进一步分析这些元素的语义。
Semantics Checker
Checker运行POS机制去标记于语句中的依赖关系，简单地说就是分析语句的真是语义而不是仅仅靠关键字来判断语句是否是设计用户隐私。Checker会把这些语句之间的关系描述为使用如下几种方式：
- Direct-object relation (Dobj)：动词短语的直接对象是名词短语:1,2,3
- Nominal subject (Nsubj)：句子的主语是一个名词短语：5
- Negation modifier (Neg)：否定修饰词是否定词与它所修饰的词之间的关系
- 其他关系：依赖 (Dep) or 复合 (Compound) ：1,2,3,6
这些元素接下来还会被Analyzer分析进一步降低误报率。
C. Sensitive Data Discovery and Tracking
Structure Analyzer
尽管语义分析是很重要的一个步骤，但是单独的语义分析还是会带来误报，例如图四中第五行的代码if(userJson .contains("home_addr"))，只是判断Json中的key——home addr对应的value是否是为空。因此还要判断包含关键元素的代码的行为是否是属于敏感操作。
因为用户的敏感数据是被第三方库使用方法调用的方式访问的，所以作者使用关注那些调用隐私数据的方法名的方式去进一步判断是否有对隐私数据进行操作。首先定位到代码中包含敏感元素的代码LOC:5,6,8,10，然后提取这些访问敏感元素语句的功能。对于包含敏感元素的语句，作者会把整条语句所包含的变量名和字符串认为是潜在的敏感信息源。对于一条被标记的语句，作者使用如下一些特性去判断是否是属于对敏感数据进行操作：
- Method name
方法名中包含如下关键字：get/set/put/add/insert/delete/remove/read/write/save
- Parameter type
方法名的参数类型：String, HashMap, Json, etc.
- Return type
方法名的返回值类型：String, HashMap, Json, etc.
- Base value type
许多程序会使用特殊的Java lib，其中会使用一些包含HashMap之类基本数据类型的自定义数据类型
- Constant-variable pattern
字符串和变量拼接在一起的形式，例如hashMap.put(“user”, $u)
Analyzer使用支持向量机（SVM）分类器去区分一条语句是否包含隐私数据。分类器训练了从100个APP中随机选取的4326条语句，在第五部分会详细描述。
Leakage Tracker
以上的过程会输出被标记好的涉及敏感操作的语句。Tracker分析的目的是找到这些敏感数据有没有被未授权的第三方lib所使用。最理想的情况下，第三方不信任的lib会使用API发送被标记的数据到服务端。但是使用数据流跟踪的方式去深入到第三方lib中去分析缺乏精度并且效率上得不偿失。 作者使用一种叫做expsure risk的表示方式，当被标记的数据流进入到不受信任的lib的时候，这个数据就不再安全并且它的内容就有可能被通过多种方式暴露出去。
IV. EVALUATION OF CLUEFINDER
这部分是测评和实验部分，以及implementation。
A. Experiment Setting
ClueFinder的实现是基于FlowDroid框架使用Jimple格式分析反编译的dex。对于自然语言处理分析部分，ClueFinder使用Stanford Parser去处理。Structure Analyzer部分在对Jimple 语句进行提取之后，使用基于Python的SVM分类器Scikit-Learn去训练分类器。实验环境是64 GB、内存32 Core的服务器，操作系统是内核版本为2.6.32的Linux。
Training Data
分类器使用的4326条语句（一般为阴性一般为阳性）是2016年八月份从Google Play随机选取的100个APP中提取并标记好的。
B. Effectiveness
作者首先在已经标记的数据集上进行ten-fold交叉验证，ClueFinder的准确率达到92.7％，召回率达到97.2％，F1-Score达到94.8％。之后作者又随机选取了100个APP，得到的结果是2775个语句中又320个是假阳性，准确率为92.5%。分析的时间为97分钟，平均每个APP的时间少于1分钟。
False positives and false negatives
作者认为大部分误报的原因是数据集的覆盖面不够高，导致有些情况下的语句不能有效地排除。简单地说就是分类的细化程度不够高。例如图五中的第二行方法saveAppKeyAndAppSecret，包含敏感关键字key和secret，但是此类私有数据仅出现在方法中，并且调用语句实际上是非敏感的。
漏报的例子如第四行中，方法的getUserGender会返回整形数值代表性别信息（1表示男性，-1表示女性），但是这不符合一个获取性别的方法应该返回string类型的期望。所以其实ClueFinder发现的只是真正敏感数据的一个子集，并不能覆盖所有的敏感数据。
Code obfuscation
作者虽然并没有考虑重量级混淆之后的代码，但是被轻量级混淆（ProGuard）的代码还是可以分析的，图六显示了使用ProGuard混淆之后的代码。在作者的100个训练样本中，有11.3%的代码是被混淆过的，但是并不影响整个分析的过程，因为在分析的过程中，作者并没有刻意地区分是否被混淆过（在能够分析的限度之内）。其实在某种程度上，尤其是大规模使用的第三方lib中开发者为了避免带来程序在执行时候的错误会尽量不使用混淆工具。就比如说作者发现Inmobi（国外第三方广告SDK）的代码为了保证开发者较为容易地使用他们的SDK鲜有混淆SDK中代码。
C. Comparing with Prior Approaches
API-based labeling
基于API的检测，作者是和SUSI进行比较。作者随机选取了100个APP提取了10116条语句。其中SUSI检测出来的77.6% (7,850)条语句都是误报。ClueFinder的准确率是92.7%回归检测准确率是97.2%。
UI-based labeling
基于UI的标记的检测，作者和UIPicker以及SUPOR进行比较。作者在100个应用程序上运行了ClueFinder，这些应用程序报告了2388个独特的敏感数据源。 作者进一步手动验证表明在大多数情况下ClueFinder会识别所有UIPicker和SUPOR的来源，并且能够检测出UIPicker和SUPOR等方案无法检测出的非UI敏感数据源。
Semantics-based taint tracking
表三显示了
