使用指向分析的安卓库函数数据流摘要方法

高颖慧,杨亚东,张 源,杨 珉

1(复旦大学 软件学院,上海 201203) 2(上海通用识别技术研究所,上海 201100) E-mail:yuanxzhang@fudan.edu.cn

1 引 言

近年来,移动智能手机在人们的日常生活中发挥着越来越重要的作用,其中Android是现在最受欢迎的智能手机操作系统.手机上的应用软件以其不断丰富的功能吸引着用户的同时也能访问到更多的用户隐私信息,而这些敏感数据的泄漏将给用户的安全造成一定的威胁.

针对海量应用软件隐私泄漏的问题,研究人员提出了多种自动化程序分析方法和工具,其中静态数据流分析是一种非常常用的技术手段.Android平台为了减轻应用程序开发者的负担和增加代码复用,提供大量的Android应用程序编程接口(Application Programming Interface,简称API).应用程序的开发和执行过程中会大量使用到这些API.为了更加精确地分析软件的行为,静态数据流分析工具不仅要分析应用程序的代码,也要分析这些API对应的库函数代码.

然而,库函数数目众多、逻辑复杂,分析库代码将会为程序分析引入大量的开销,远超过应用程序本身的开销,往往使得分析最终以超时或内存不足而告终.同时,针对每一个应用软件都需要对库代码重新分析,严重制约了静态数据流分析技术应用于海量应用软件的分析.

处理库函数的分析一个比较好的办法是为库函数生成数据流摘要,摘要能对每个库函数的行为建模,使得分析应用程序时无需再分析库函数代码,只需要使用库函数摘要就可以得到库函数对应用程序产生的效果.同时,数据流摘要在生成

1http://wala.sf.net/

后,可以被重复运用于分析各个应用程序.但是Android平台提供的库函数数量巨大,如何为这些函数生成精确的数据流摘要是一个非常重要的问题.通过人工方式编写函数摘要需要理解大量代码才能进行数据流建模,无法应对百万级API的数据流摘要生成.简单地基于启发式规则去建模库函数数据流摘要粒度太粗,无法精确表征库函数代码的实际行为,也不能反应各个API之间的差异性行为.

StubDroid[1]是第一个针对Android数据流分析问题自动化生成库函数摘要的工具.通过自动化地分析库函数代码执行期间对数据流传播的影响,StubDroid可以为每个API生成数据流摘要,并且应用于以FlowDroid[2]为代表的静态分析工具中.然而,本文发现StubDroid只对库函数的数据依赖关系建模,并未为库函数内指针指向信息生成摘要.Java语言的动态绑定机制使得Android应用程序必须根据对象的实际类型调用相应的函数,是以静态分析为了得到精确的函数调用图,需要通过指向分析确定变量在运行时可能指向的对象信息.使用StubDroid生成摘要的静态数据流分析工具由于不再分析库代码,将缺失库函数中的指针指向信息,从而生成不精确的函数调用关系并且采取比较保守的方式加载库函数摘要中的数据流,而这些都将会产生不正确的数据流传播,为数据流分析引入假阴性和假阳性的结果.

因此,本文设计并实现了一种融合指向分析的自动化数据流摘要生成与使用工具Point2Droid.Point2Droid生成的摘要不仅包含库函数的数据依赖关系,也为其中的指向关系建立模型,从而有效补充了StubDroid的不足.同时,我们设计了四组实验对Point2Droid的性能进行测试,实验结果显示,Point2Droid能在平均30s内为单个库类生成摘要,生成的摘要经人工验证正确模拟了库函数对数据流的影响.使用Point2Droid生成的摘要使得静态隐私检测工具的分析效率大大提高,并且检测出了更多的隐私泄露路径.

2 背景与相关工作

2.1 数据流分析与指针指向分析

数据流分析指的是一组用来获取有关数据如何沿着程序执行路径流动的相关信息的静态分析技术(基于变量作用域的数据流分析)[3].它能提取出程序的语义信息,在不实际运行应用程序的情况下,推测其运行时可能发生的所有可能的行为,掌握应用程序的功能,具有批量化分析、覆盖率高等优点.

指针指向分析是指通过不断解析赋值语句,根据右值的指向信息计算和更新左值的指向信息,得到程序运行时各引用变量可能指向的对象,从而确定程序根据动态绑定实际所执行的函数的过程.指针指向分析算法主要包括:Steensgaards[5]风格算法,一种基于等价(equivalence-based)的指向分析,算法复杂度为Ο(n),但准确度不高;Andersen[4]风格算法,一种基于子集(subset-based)的指向分析,它认为赋值语句将左右两边的引用变量产生一种集合包含关系,即左边引用变量指针指向集合(Points-to Set)是右边引用变量Points-to Set的子集,算法复杂度是Ο(n3),但准确度相对Steensgaards算法好一些.经过效率和精度的权衡,静态分析会选择其中一种算法进行优化和改进,现有的静态分析框架也提供了基于两种算法的指针指向分析框架,如本文选择的Soot Pointer Analysis Research Kit(SPARK)[8]是Soot基于Andersen风格算法提供的指向分析框架.

2.2 相关工作

在静态分析方面,Vallée-Rai等人提出了Soot[6]和Fink等人提出的WALA1[7]是最为广泛使用的两大Java开源静态分析框架,它们将Java字节码转化成不同形式的中间表达式,并在此之上实现对应用程序进行过程内和过程间的分析.随着对Android安全研究的深入,学术界提出各种Android静态分析框架:Arzt等人和Gordon等人基于Soot框架分别提出FlowDroid[2]和DroidSafe[9].Lu等人和Wei等人基于WALA框架分别提出了CHEX[10]和Amandroid[11].这些静态分析工具虽然在设计思想、性能及检测结果上存在差异,但都需要使用模型加速对库函数的分析.其中FlowDroid和CHEX使用一些过于简单的规则概括部分库函数对数据流的影响,Amandroid和DroidSafe则人工精确建模常用的库函数.由于人工需要耗费极大的精力且版本更新需要重新分析,而简单规则过于粗粒度,所以这些工具都并未很好解决库函数的问题.

在库函数摘要方面,Juan Zhai等人[12]根据Java库函数中的文档说明对库函数行为进行了人工建模,但这种人工方法精度不高且费时费力,无法大规模应用.Yinzhi Cao等人提出EdgeMiner[13],将库函数对应用程序的回调总结在一些规则中,能自动化地得到Android中的回调函数,这虽然能协助建立完整控制流图,但无法改进对库函数的数据流分析.Hao Tang等人[14]认为库函数的分析结果使用依赖于上下文,他们提出了一种新的形式化语言TAL来描述这一类库函数行为.但此工作目前仍然处于形式化表述的阶段,未能生成可用的工具.

3 StubDroid以及存在的问题

StubDroid是为库函数中数据流关系建模的全自动工具.它每次只针对一个库函数,为函数内的变量之间的数据依赖关系建立模型,生成摘要存储到文件中.当静态污点分析工具稍后处理在应用程序代码中对库函数调用时,只需要简单地插入从摘要文件中得到的信息,在截断其进一步对被调用的库函数和所有传递被调用者(即库函数内调用的函数)分析的情况下,依然可以精确地计算得到这些被调用的库函数和传递的被调用者对污点传播产生的影响.

具体做法是以对当前库函数的参数、当前对象的this引用和全局变量所涉及的访问路径(access path)的数据读取(如图1第5行的p1)作为source,并以对当前库函数的参数、当前对象的this引用和返回值和全局变量所涉及的访问路径(access path)的数据写入(如图1第5行的this.mX)作为sink,使用FlowDroid执行污点分析生成source到sink的数据流映射,每一条数据流映射表明source和sink之间存在数据依赖关系(即数据传播关系,如a⟹b表明变量b依赖于变量a,变量a的数据传播到变量b).如图1所示,StubDroid在分析完XYHolder构造函数以后会生成参数1与this.mX、参数2与this.mY之间的数据流映射.分析完成之后将这些数据流映射存储到摘要文件中,之后在静态数据流分析工具分析应用程序代码遇到库函数调用时会加载相应的摘要文件,遍历从摘要中获取到数据流映射,根据被依赖变量(source)当前在程序中的状态,计算依赖变量(sink)的状态,这样就完成了根据数据流映射做数据传播,在所有的数据流映射处理完之后,就能得到目标库函数对程序产生影响后的数据状态.

对于简单的库函数,StubDroid能够很容易使用上述方法建模生成摘要,但当库函数内存在回调,即库函数将通过客户端传入的指针调用函数,由于StubDroid为该库函数生成摘要时不会分析客户端代码,所以无法确定实际回调的函数,进而无法得到它的数据流传播.如图1的evaluate函数,StubDroid为其生成摘要时无法确定传入对象引用所指向的对象的具体类型,因而不能确定实际调用的是哪个类的getX()函数和getY()函数,导致无法进一步分析.为了解决这个问题,避免回调函数数据流信息的缺失对生成摘要产生的影响,StubDroid使用gap对每一个无法确定的回调函数进行占位,并且记录该函数签名,同时建模从source到gap以及从gap到sink之间的数据流映射.当对应用程序的静态分析使用到摘要时,才在gap处插入对应的回调函数的数据流传播.因此,图1的evaluate函数的摘要文件中会包含签名分别为和的gap.

然而,在使用摘要时,由于不再分析库代码,失去了库函数内对象的指向信息,StubDroid只能保守地根据摘要中gap对应的函数签名依据以下步骤查找所有可能的回调函数:

1)从摘要文件目录查找所有可能的实现或者继承了该签名的方法所包含的数据流映射.

2)若1中没有成功加载到数据流映射,则遍历程序,获取客户端代码中实现或者继承了该签名的方法,然后对每一个方法进行静态数据流分析.

这种保守的方法会产生不正确的数据流传播,从而对数据流分析的准确性产生影响.如图2所示的应用程序代码,当静态分析到第8行语句时会加载库函数evaluate(图1)的摘要信息,而evaluate的摘要文件中存在签名为的gap,StubDroid没有该gap的指向信息,只能根据步骤1从XYHolder的摘要文件中找到 getX()(图1的8～10行)方法并加载其中包含的数据流映射,得到返回值this.mX.然而程序在实际运行中,调用的是BenignXYHolder的getX()(图2的18到20行)函数,该函数返回的是常量.于是在这种情况下,将会使得静态分析到图2的第10行产生假阳性的结果.

4 Point2Droid基本架构

为了建模库函数行为,本文基于StubDroid设计并实现了一种融合指向分析的自动化数据流摘要生成与使用工具Point2Droid.如图3所示,Point2Droid根据功能主要分成两个模块:摘要生成模块和摘要使用模块.

4.1 摘要生成模块

该模块以库的二进制代码作为输入,通过库代码中每一个公开(public)函数执行一遍摘要生成所需要的分析得到相应的函数模型摘要,并依此代表每个API会对应用程序分析产生的效果.为了进一步提高分析效率,摘要生成过程中会将一个类中所有函数的摘要输出到同一个摘要文件中,以节省内存占用、方便共享和复用.

图3 Point2Droid系统架构示意图Fig.3 System architecture of Point2Droid

库函数模型摘要主要分成两部分:指针指向摘要和数据依赖摘要,其中数据依赖摘要由StubDroid生成.为了生成指针指向摘要,Point2Droid首先为当前分析构造入口函数,然后从该入口函数出发执行指针指向分析,指向分析能得到当前分析中所有变量的指向对象集合,通过对结果的处理,得到目标库函数在调用前后对引用变量指向对象所作出的该改变,并将这一改变记录下来,建模成函数指针指向摘要.

4.2 摘要使用模块

该模块应用于应用程序的静态分析中,当分析到应用程序调用API时,摘要使用模块截断其对库代码的进一步分析,通过加载和解析摘要文件中的库函数模型,得到API对应用程序产生的影响,然后根据如下公式计算出应用程序在函数调用后的状态.这样既能保证分析的精度,又能节省对库函数分析所浪费的时间和内存.

Statusbefore+Changesummary=Statusafter

摘要使用模块也分成两部分:指针指向摘要的使用和数据依赖摘要的使用.

5 Point2Droid设计与实现

Point2Droid通过改进Soot[6]内置的指向分析框架SPARK[8]生成库函数的指向信息摘要,同时基于StubDroid生成数据依赖摘要,最后将得到的库函数指针指向信息和数据传播信息应用于静态污点分析工具FlowDroid中.

5.1 构造入口函数

为库函数生成指针指向摘要时,由于单个库函数不是完整的可执行程序,没有main方法,因而需要构造一个DummyMain方法,并且在方法体内构造调用当前被分析库函数的语句.然后Soot将统一以DummyMain为入口函数并作为起点,执行接下来的分析.

5.2 摘要生成模块的指针指向分析

为了得到库函数中所有指针指向对象的信息,需要通过如图4所示的指针指向分析流程为库函数生成指针指向摘要.其核心是迭代式地根据当前可达函数构建指针赋值图(Pointer Assignment Graph,PAG),然后沿着图中的边不断更新节点对应的引用变量的指向信息.与此同时,依次访问图中节点获取更新后的指向信息,更新函数调用图,从而添加新的可达函数.最初的可达函数为入口函数DummyMain.

图4 摘要生成的指针指向分析流程图Fig.4 Points-to analysis of summarization

5.2.1 创建PAG

PAG是用来描述变量与对象指向关系的有向图,在Soot中PAG图中有三类节点:内存分配节点(Allocation Node,AllocNode),代表代码中创建一个新的对象(new C());变量节点(Variable Node,VarNode),代表代码中的本地变量、方法参数、 返回值及静态域(dst);域引用节点(Field Dereference Node,FieldRefNode),代表代码中的域变量(src.f)[8].节点的指向信息由集合表示,称为指针指向集合(Points-to Set).指向分析根据分析语句的不同来生成不同类型的边,并对不同类型的边产生不同的Points-to Set传播规则,具体如表1所示.

表1 Points-to Set传播规则
Table 1 Rules of Points-to Set propagation

语句类型边(a表示newC())边类型传播规则dst=newC()a→dstAllocNode→VarNodeAllocationa→pt(dst)dst=srcsrc→dstVarNode→VarNodeAssignmentpt(src)→pt(dst)dst.f=srcsrc→dst.fVarNode→FieldRefNodeFieldStoreptsrc()→pta.f()a∈pt(dst)dst=src.fsrc.f→dstFieldRefNode→VarNodeFieldLoadpta.f()→ptdst()a∈pt(src)

5.2.2 创建DummyAllocNode

由于库函数做指向分析生成摘要时,缺失参数以及this引用的指向信息,且库函数生成的摘要需要适用于所有可能的应用和使用上下文中,Point2Droid会在创建PAG时为被分析函数的参数和this引用创建DummyAllocNode节点抽象表示变量在函数调用之前所有可能的指向信息,并且在DummyAllocNode和变量节点之间添加一条Allocation边(表示为该变量new了一个新对象,见表1).此外,由于参数和this引用相关的域变量(如this.f)在函数调用前的指向信息也是缺失的,为了区分二者,当库函数内使用这些变量时,Point2Droid会为其创建DummyFieldAllocNode节点.其中DummyFieldAllocNode类继承自DummyAllocNode类,表示DummyFieldAllocNode节点是一种特殊的DummyAllocNode节点.

5.2.3 Points-to Set的传播与函数调用图的更新

指针指向分析会以所有AllocNode为起点遍历PAG的边,使用表1中的规则传播和更新节点的Points-to Set.同时,在节点更新Points-to Set以后,访问以该节点表示的变量为调用基的调用点,添加相应的函数调用边,更新函数调用图.如调用点v.m(…)在v更新指向信息后,可以得到v实际指向的对象类型,根据该类型以及调用语句声明的函数子签名,解析得到的函数即为其实际调用的函数(callee).

5.2.4 为无法确定的函数调用创建gap

由于Points-to Set中存在DummyAllocNode节点,它是抽象出来的对象,其实际类型需要在客户端代码运行时才能确定,所以以指向该节点的引用变量为调用基的调用点在摘要生成阶段无法确定其实际的callee,这也将无法计算该callee对指针指向信息所产生的影响,从而影响到整个库函数的分析.为了消除不确定callee的影响,Points2Droid借用StubDroid中gap的概念,使用gap为该函数占位,并且记录进入gap前与gap相关引用变量(调用点的调用基、传入的参数和返回值)的指向信息,以及创建DummyAllocNode为离开gap之后的相关引用变量所有可能的指向信息抽象建模.

5.3 生成指针指向摘要

在指针指向分析得到各引用变量的Points-to Set以后,需要计算出整个目标库函数对指针指向对象所做的改变,并将其记录为摘要.这样应用程序的分析就不再需要库代码只需要摘要即可完成Points-to Set的更新与传播.

由于库函数通过参数、返回值和this引用(统称为对外开放引用变量)与应用程序传递指针且会保存gap相关引用变量的指向信息,所以库函数的摘要只需要关心库函数对上述6种引用变量及其域变量的指向信息改变.对于对外开放引用变量及其域变量而言,由于其函数调用前指向信息不确定,均使用DummyAllocNode建模其指向信息,所以其函数调用前的Points-to Set(用pt(before)表示)只有一个与变量唯一对应的DummyAllocNode节点;而对于gap相关变量及其域变量而言,其函数调用前指向信息为空,pt(after)-pt(before)=pt(after).所以,库函数的摘要就是记录上述6种引用变量及其域变量的Points-to Set.

Points-to Set中主要存储了两类节点,一类是指向库函数内部实例化的对象AllocNode节点,另一类是为了建模引用变量可能的指向信息所创建的DummyAllocNode,表示当前变量与被建模的引用变量指向同一对象.这两类节点都可以表述为映射关系,前者为对象和变量之间的映射,后者为变量与变量之间的映射.因此最终生成的摘要应是一种多对多的指向映射关系,为了方便,Point2Droid使用多对一的Map来存储.

综上所述,Point2Droid首先找到上面提到的6种基本变量,然后根据这6种基本变量找到其域变量,在得到这些变量的Points-to Set之后,遍历Points-to Set中的节点,提取出如下所示关系(→表示指向关系映射),存储在Map中.

6种引用变量及其域变量→6种引用变量及其域变量

实例类型→6种引用变量及其域变量

5.4 生成摘要文件

Point2Droid使用StubDroid生成数据依赖摘要,当一个库类分析完成以后,它将类中所有函数的指针指向摘要和数据依赖摘要一起存储到xml格式文件中.xml作为可扩展标记语言,具有结构清晰,读写方便等优点.

Point2Droid针对图1示例中的XYEvaluator类生成的摘要文件结构如图5所示,由于篇幅,只选取了其中部分映射关系.methods元素是一个类中所有函数摘要的合集,每一个函数对应一个method元素,属性signature是该函数的签名.每一个函数摘要包含两类信息,指针指向关系映射和数据依赖关系映射,这两类信息由三类元素表示.

•baseobject:该类元素主要是为了简化object中的访问路径,代表库函数中的六种引用变量.

•object: 该类元素使用属性p2set和属性field代表多对一的指针指向关系映射,表示如下所示Points-to Set的传播规则.

src∈p2set,pt(src)→pt(field)

•flow: 该类元素使用属性from和属性to代表数据依赖映射,表示to变量的数据依赖于from变量.

Methods之后的gaps元素是类中所有使用到的gap的合集,被baseobject和flow元素中的gap属性引用到.

5.5 指针指向摘要的使用

指针指向摘要将应用于应用程序静态分析的指针指向分析阶段,图6是使用摘要的指针指向分析流程的示意图,图中虚线部分与摘要生成的指针指向分析相同.

图6 使用摘要的指针指向分析流程图Fig.6 Points-to Analysis of using summary

5.5.1 加载解析摘要文件

对摘要文件的使用不是直接将目录下所有的摘要文件都加载到内存中,而是当分析程序检测到应用程序调用API时,Point2Droid才会从磁盘请求此类的摘要文件并将其加载到内存中.如果磁盘上存在大量(或许多不同)库的摘要,则可以大大降低内存消耗.

5.5.2 创建DummyVarNode

为了将摘要中指向信息映射到PAG上,我们需要创建DummyVarNode来代表库函数中的变量节点,DummyVarNode继承自VarNode,表示一个在程序中不存在代码的变量.但摘要中具有映射关系的不仅有变量还有域变量和实例对象,是以要分情况生成不同的节点:

·实例对象,解析出该对象的具体类型,创建AllocNode.

·基本变量,直接创建DummyVarNode.

·域变量,从左到右依次解析访问路径,拿到或者创建被引用变量的DummyVarNode,并且根据DummyVarNode和域创建FieldRefNode,再为域变量创建DummyVarNode,然后在两个新创建的节点之间添加一条Load类型的边.

5.5.3 构造PAG

首先为当前库函数生成一个过程内的指针赋值图MethodPAG,并在其中根据函数签名信息创建this引用、参数和返回值对应的VarNode节点.然后根据摘要中指针指向关系的映射,在MethodPAG创建相应的DummyVarNode节点,并在两个具有指向关系的节点之间添加一条Assignment边.最后根据应用程序中的调用语句按照图7所示的关系将MethodPAG与整个应用程序的PAG连接起来.这样就能在不需要库函数代码的情况下依然可以构建出完整的PAG,同时得到每个节点的Points-to Set.

5.5.4 处理Gap和生成GapEdge

由于gap的存在,在DummyVarNode更新得到它的Points-to Set后,需要解析以这个节点为调用基的gap所对应的callee.遍历节点的Points-to Set,取出每个AllocNode,判断AllocNode的类型是对应一个库函数类还是一个应用程序类.库函数类则从摘要文件中加载相应文件取出对应摘要信息,应用程序类则根据类型和子签名得到真正的函数.解析得到gap调用的callee之后,则为这一调用生成一个特殊的函数调用边GapEdge并保存在函数调用图中,然后再沿着GapEdge更新PAG.

图7 连接PAG和Method PAGFig.7 Add Method PAG into PAG

5.6 数据流摘要的使用

Point2Droid基于StubDroid使用数据依赖摘要.但是本文提到过,StubDroid之前因为缺乏指针指向信息,会使用一些保守的方法查找调用点或者gap所调用的函数,并且加载所有可能的数据依赖,从而产生不正确的数据传播.而Point2Droid能获得程序完整的指向信息,生成精确的函数调用图,因此将StubDroid改进为根据调用点或者gap真实调用的函数加载数据依赖,得到准确的数据传播,应用于数据流分析中.

6 实验与分析

本部分,我们将从摘要生成和摘要使用两个方面对Point2Droid的性能进行实验,摘要生成方面将从摘要生成效率和摘要准确性的角度进行衡量,摘要使用方面也将就使用摘要对静态分析工具的分析效率和分析结果方面产生的影响进行评估.

实验环境为:具有40核心(Intel Xeon E7-4830,2.13Ghz),内核版本3.16.0,物理内存大小为128G的Linux服务器.服务器的操作系统为64位的CentOS 7,运行Java版本为1.8的64位HotSpot虚拟机(build 25.111-b14,mixed mode).在针对摘要生成的测评时将最大内存(-Xmx)设置为16G,在针对摘要使用的测评时将最大内存设置为96G.

6.1 摘要生成的效率测试

我们使用Point2Droid为Android SDK和Oracle JDK中的库代码中17个常用类生成摘要文件,并统计其时间开销.实验用的测试样本是由摘要生成相关实验的样本是Android AOSP 4.2手动构建的android.jar(Google分发的SDK只有Stub没有具体函数实现),和Java 8(1.8.0_91)使用的rt.jar.

表2的测试结果显示Point2Droid能在平均30s内为一个类生成摘要,这表明Point2Droid生成摘要不是一个耗时耗力的工作.Android SDK和Oracle JDK所产生的结果几乎一致,但有些微的差别,这表明两者在库函数的实现上略有差别,但它们的库函数对应用程序影响是差不多的.此外可以看到生成摘要的时间与objects、flows的数目不是一个正相关的关系,这是因为库函数代码的复杂程度与指向关系映射、数据流映射条数没有关系.

表2 摘要生成效率测试的结果
Table 2 Experiment result of summarization efficiency

类名OracleJDKAndroidSDKobject数目flow数目生成时间(s)object数目flow数目生成时间(s)java.util.ArrayDeque6415143.156815736.30java.util.ArrayList3811135.484311430.43java.util.HashMap5312523.748212118.77java.util.HashSet7112722.827111918.86java.util.IdentityHash-Map416218.15456517.74java.util.WeakHashMap6514230.367111918.16java.util.Hashtable699128.386013821.54java.util.Stack7520960.986216947.12java.util.Vector6118550.945715543.14java.util.concurrent.Concur-rentHashMap6526559.306616839.81java.util.concurrent.CopyOn-WriteArraySet506927.92397216.87java.io.BufferedReader1614117.652018717.26java.io.CharArrayWriter347538.57337327.71java.io.DataInputStream4516528.753512127.78java.io.ByteArrayInput-Stream22513.6922414.80java.io.BufferedArray-OuputStream134111.01123911.44java.io.FilterOutput-Stream8209.9482110.41平均4511830.644611024.60

6.2 摘要的准确性测试

为了验证Point2Droid生成指针指向摘要的准确性,我们人工追踪库函数中的指针传递,并为库函数最终产生的指向关系建模,然后对比人工建模的指向关系映射与Point2Droid生成结果的差异.由于库函数比较复杂,人工追踪指针传递将花费极大的精力,所以我们只分析了Android SDK中五个类(见表3 )的函数实现,最后结果显示Point2Droid生成的指针指向摘要完全与人工分析的结果完全一致.这证明Point2Droid这样的自动化摘要生成工具可以为库函数生成正确的指向信息,避免人工去编写摘要.

表3 摘要准确性测试的样本
Table 3 Test sample of summarization accuracy

类名函数数目object数目指向关系映射数目java.util.Observable81617java.util.ArrayDeque286868java.util.Hashtable176066java.io.BufferedWriter173944java.lang.Integer152122

6.3 摘要对静态数据流分析效率的测试

为了验证Point2Droid生成的摘要对应用程序数据流分析性能产生的影响,我们随机选取的5个大小合适的样本分别在不使用摘要且加入整个库函数的分析、使用StubDroid工具生成的摘要以及使用Point2Droid生成的摘要三种模式下使用静态分析工具FlowDroid执行数据流分析,并且将它们各自的超时(timeout,时间限制)设为一小时,其它所有运行环境和参数均保持一致,最后统计各个分析的时间开销.

表4 静态分析在三种模式下的时间开销对比
Table 4 Compare time overhead of static analysis in three modes

应用程序应用程序大小(M)运行时间(s)分析整个库函数的FlowDroid使用StubDroid生成摘要的FlowDroid使用Point2Droid生成摘要的FlowDroidDroidCoupon0.86超时57.1124.56ADRD1.62超时28.098.78DroidKungFuSapp2.14超时37.1115.81DogWars4.39超时40.4620.34Plankton8.54超时34.0110.94平均3.51N/A39.3616.09

表4是本次实验的结果,由结果我们可以看到,若应用程序的分析中加入对库函数的分析往往会导致超时从而得不到分析结果,而使用摘要替代库代码的分析能将整个数据流分析的时间开销降低为几十秒.此外,我们还注意到,使用Point2Droid生成的摘要模式下执行的数据流分析将明显快于在使用StubDroid生成的摘要模式下的分析,前者平均16s而后者平均39s.因此,我们可以认为Point2Droid生成的摘要对静态数据流分析的效率有显著的提升.

表5 静态污点分析在三种模式下检测到的隐私泄漏对比
Table 5 Compare leak detection of static analysis in three modes

应用程序使用Point2Droid生成摘要使用StubDroid生成摘要不分析库函数库函数/数据流隐私泄漏数目库函数/数据流隐私泄漏数目隐私泄漏数目DroidKungFuUp-date13485115753Endofday324662851954N/A28DogWars17841830240175Plankton62771614874DroidKungFu1151511318352138DroidKungFu22712234455962010DroidKungFu3197727348632727DroidCoupon20911936791196DroidDreamLight1413632162243219GoldDream189132229932RogueSPPush134758212635837Asroot42441514744CoinPirate1910258346365856Zsone104121243852121GingerMaster159353262505350BeanBot3015023395162311KMin2719244365804240YZHC1819869252726932DroidKungFuSapp159574284627040DroidDream317855845055平均1811629424

6.4 摘要对静态数据流分析效果的测试

为了测试Point2Droid生成的摘要对静态数据流分析的检测效果产生的影响,我们随机从Android恶意软件基因组项目[15]中挑选了20个样本分别在不使用摘要且不分析库函数、使用StubDroid工具生成的摘要以及使用Point2Droid生成的摘要三种模式下使用FlowDroid执行污点分析,并且统计分析检测到的隐私泄漏数目.

本次实验结果(表5)显示,使用Point2Droid的摘要相比于使用StubDroid生成的摘要,需要加载的库函数数目和数据流数目明显减少,而分析出的隐私泄漏数目不仅没有减少,反而有所提高.其中,利用StubDroid生成的摘要进行测试的EndofDay出现了超时,而其它两种模式下没有,这是因为使用StubDroid生成的摘要会加载更多的数据流从而使得静态污点分析将更多的数据打上污点,分析的时间增加,导致超时,这也验证了6.3的结果.在StubDroid生成摘要模式下和在Point2Droid生成摘要模式下检测到的隐私泄漏均多于未使用摘要且不分析库函数模式下的检测结果.

7 总 结

为了避免库函数为程序分析带来的过多开销,需要为库函数建模生成摘要.针对现有的自动化摘要技术StubDroid中因缺乏对库函数中指向信息建模而产生的数据流分析的精确度和覆盖率上的问题,本文提出了Point2Droid系统.Point2Droid实现了对库函数的指向信息进行自动化的摘要生成并且在静态数据流分析过程中自动加载指向信息摘要,通过库函数中指向信息的支持,静态数据流分析工具能生成准确的函数调用图,加载正确的库函数信息流,有效地解决了StubDroid系统中存在的精确性和覆盖率问题.

[1] Arzt S,Bodden E.StubDroid:automatic inference of precise data-flow summaries for the android framework[C].Proceedings of the 38th International Conference on Software Engineering,ACM,2016:725-735.

[2] Arzt S,Rasthofer S,Fritz C,et al.Flowdroid:precise context,flow,field,object-sensitive and lifecycle-aware taint analysis for android apps[J]. ACM Sigplan Notices,2014,49(6):259-269.

[3] Alfred V A,Monica S L,Ravi S,et al.Compilers principles,techniques and tools(2nd )[M].Beijing:China Machine Press,2009:382-402

[4] Andersen L O.Program analysis and specialization for the C programming language[D].University of Cophenhagen,1994.

[5] Steensgaard B.Points-to analysis in almost linear time[C].Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages,ACM,1996:32-41.

[6] Vallée-Rai R,Co P,Gagnon E,et al.Soot-a Java bytecode optimization framework[C].Proceedings of the 1999 Conference of the Centre for Advanced Studies on Collaborative Research,IBM Press,1999:13.

[7] Fink S,Dolby J.WALA-the TJ watson libraries for analysis[EB/OL].https://wala.sourceforge.net,2017.

[8] Lhoták O,Hendren L.Scaling Java points-to analysis using Spark[C].International Conference on Compiler Construction.Springer Berlin Heidelberg,2003:153-169.

[9] Gordon M I,Kim D,Perkins J,et al.Information-flow analysis of Android applications in droid safe[C]. Network and Distributed System Security Symposium.2015.

[10] Lu L,Li Z,Wu Z,et al.CHEX:statically vetting Android apps for component hijacking vulnerabilities[C]. ACM Conference on Computer and Communications Security,ACM,2012:229-240.

[11] Wei F,Roy S,Ou X,et al.Amandroid:a precise and general inter-component data flow analysis framework for security vetting of Android apps[C]. ACM Sigsac Conference on Computer and Communications Security,ACM,2014:1329-1341.

[12] Zhai J,Huang J,Ma S,et al.Automatic model generation from documentation for Java API functions[C]. International Conference on Software Engineering,ACM,2016:380-391.

[13] Cao Y,Fratantonio Y,Bianchi A,et al.EdgeMiner:automatically detecting implicit control flow transitions through the Android framework[C]. Network and Distributed System Security Symposium,2015.

[14] Tang H,Wang X,Zhang L,et al.Summary-based context-sensitive data-dependence analysis in presence of callbacks[C].ACM SIGPLAN Notices,ACM,2015,50(1):83-95.

[15] Zhou Y,Jiang X.Dissecting android malware:Characterization and evolution[C].Security and Privacy (SP),2012 IEEE Symposium on.IEEE,2012:95-109.

附中文参考文献：

[3] Alfred V A,Monica S L,Ravi S,et al.编辑原理[M].北京：机械工业出版社，2009:382-402.