基于遗传算法的Android系统服务漏洞挖掘

张志威,甘 刚

(成都信息工程大学网络空间安全学院，四川 成都 610225)

0 引 言

Android系统因其智能化的操作和应用广受各大厂商推崇与二次开发，手机市场占有率逐年攀升。智能移动终端承载着亿万移动用户的生产生活，良好的便携性及系统生态获得了广大用户的喜爱。但与此同时，暴露出的Android漏洞数目也随之增长。因此，Android系统的安全性也一直是安全研究人员关注的重点。

据CNVD(China Nation Vulnerability Database)及其他知名漏洞提交平台查询发现，以往提交的Android漏洞集中于应用层，大多为组件暴露[1]、信息泄露、二次重打包[2]、权限提升等类型，但对系统服务层面的研究探索较少。而Android系统服务作为运行在系统底层的核心进程，一旦被恶意程序获取到相关权限，则可能会导致隐私泄露。此外如果服务在运行过程中接收使用了传入的非法参数，则可能会致使系统重启、拒绝服务甚至内存损坏等不可知结果。文献[3]在对Android系统服务漏洞挖掘的过程中使用了模糊测试的方法，但测试数据类型单一，未对通信过程中复杂的参数类型进行构造，某种程度上导致了参数用例覆盖的不全面。文献[4]同样利用模糊测试的方法对系统服务进行漏洞挖掘，但对系统服务中多维参数的变异[5]没有进行合理的控制处理，可能会导致组合爆炸等问题。如何解决模糊测试过程中用例覆盖率低及多维参数变异的问题也一直是漏洞挖掘人员的研究重点。

因此，本文将遗传算法与模糊测试技术结合起来，通过适应度函数对参数进行变异指导，保证了参数的多样性，并且根据数据类型变异优先级表对不同参数也进行相应的组合变异操作。该方法在一定程度上减小了组合爆炸对参数遗传变异的影响，提高了测试用例的覆盖率。

1 背景知识介绍

1.1 Android系统服务

Android终端的流畅运行离不开系统服务的支持，如短信的接收与发送需要短信管理服务SmsManager,窗口的打开与关闭需要窗口管理服务WindowManager等，各种服务Manager提供对底层的访问接口，方便了上层应用的调用。Android系统服务主要分为守护进程服务、本地系统服务和Java系统服务。守护进程是为处理系统多任务请求而在后台运行的Server程序。此类进程在系统启动初始化中生成，常驻系统后台，直至系统运行结束。其中典型的有用于图像合成显示的SurfaceFlinger服务、管理Binder对象的ServiceManager等。第二类本地系统服务数量较少，一般使用C/C++编写，运行在LIBRARIES层中[6]，包括AudioFlinger音频服务、CameraService相机服务等其他重要服务。最后就是Java系统服务，该类服务由SystemServer系统进程启动，并以线程的形态运行在SystemServer进程中。Java系统服务又分为核心平台服务和硬件系统服务。核心系统服务提供了系统正常运行基本的功能，与应用程序交互较少，但却是Android Framework运行所必需依赖的。而硬件服务则为上层应用提供接口，用于控制底层硬件提供服务。常用的Android系统服务如表1所示。

表1 常用系统服务

SystemServer进程中运行着诸多Java系统服务，应用如果想调用系统服务，就要以跨进程的方式与系统服务进行通信。Android系统不同进程间的信息交互要使用Binder通信机制，例如当上层应用要调用发送短信的API,其底层实现就是通过Binder对象调用短信的系统服务。每个系统服务中封装定义了实现相应功能的方法，而这些接口方法则是本文进行模糊测试漏洞挖掘的研究对象。

1.2 Binder通信机制

Android为保证进程安全采用了沙箱隔离的机制[7]，但不同进程间往往需要信息数据交换。传统的通信方式如管道、消息队列等是通过读写内核缓冲区的方式获取数据，2次复制过程存在效率问题，而套接字资源开销较大，多用于网络相关传输。此外，这些通信方式无法确认双方的身份，容易被攻击。而Binder通信机制使用内存映射的方式只对内容拷贝一次，发送过程中会添加身份识别ID，并且采用C-S架构，是一种安全高效的进程通信方式[8]。系统服务想要被调用，要先通过Binder通信机制跨进程在ServiceManager中注册，这样上层就可以通过Binder对象直接从用户空间到底层访问服务。

Binder通信架构主要由客户端进程、服务端进程、ServiceManager、Binder驱动4个部分组成。前3者运行在用户空间，服务端进程在ServiceManager中注册后，由客户端进程发出服务请求，进而才能使用服务[9]。ServiceManager主要提供辅助管理的功能，而Binder驱动运行在内核空间以负责各个进程间通信。当跨进程通信发生时，Server进程拥有Binder对象，而Client进程会调用其关联BinderProxy对象实例的transact方法发起请求[10]，通过IPC的方式传递到Server端。Server接收到参数后调用服务端的transact方法，最终由onTransact执行相应的逻辑并将结果返回给Client端。Binder通信模型如图1所示。

图1 Binder通信模型

2 系统服务模糊测试技术分析

模糊测试是基于黑盒的安全测试技术[11]，通过向程序输入随机数据导致程序崩溃或产生异常，进而发现应用中的潜在漏洞。对于Android系统服务的模糊测试，首先要确定用例参数的数据入口。经过分析，上层应用对系统服务的调用是通过Binder实现的，请求服务都会调用到transact方法。可以考虑将底层transact方法作为测试入口，但该方法存在于系统底层，用例参数无法直接传入，不适合作为入口的选择。通过分析底层transact函数的上下文调用关系，发现Java上层Binder类实际是对底层功能实现的封装，上层使用Binder调用服务会使用Binder代理类的transact方法，层层传递最终仍会调用到底层的transact函数，且参数是原样传入底层。该方法符合测试接口低权限、参数透传性好的要求，且代码容易实现，因此可以选择上层Binder类的transact方法作为模糊测试的数据入口。

transact函数原型为bool transact(int code,Parcel data,Parcel reply,int flags)[4]，方法返回值为布尔型。其中code是int类型，对应的是Aidl文件中定义接口的方法号，从1开始，依次递增。data是Parcel类型，用来保存接口的各个参数数据。reply也是Parcel数据类型，用来保存服务端返回的数据。而flag为通信类型标志位，0表示请求发起后需要等待返回的普通RPC(Remote Procedure Call)类型，1则表示为单向的RPC通信，即不需要接收返回信息。其中data中所存放的参数则是要进行构造填充Fuzz的数据。如在某服务中定义了接口号为10的方法：test(int a,String b，double c)。则transact方法的构造如图2所示。

图2 transact方法构造示例

测试模块获取到接口参数类型后构造初始测试用例，并通过trancact函数调用系统服务，然后监控手机是否发生异常，这样就完成一次基本的模糊测试。

3 ASFuzzer系统设计与实现

3.1 设计思想与架构

遗传算法[12]是模拟生物自然进化的一种求解复杂问题的通用计算模型，通过适应度函数对个体差异进行评价，从而对其进行个体优选、基因交叉、数据变异操作。遗传过程中逐渐将劣质个体淘汰，优秀个体遗传给下一代，使个体最终趋于最优。本文根据系统服务漏洞挖掘实际场景，将遗传算法思想巧妙运用到测试用例的生成过程中，设计实现了Android系统服务漏洞挖掘工具ASFuzzer。该工具将单次测试结果作为适应度函数的评判标准[13]，指导参数进行变异，保证了新一轮测试参数用例的有效遗传，而对于无效的参数则抛弃并重新生成有效数据；并且在单个数据变异有效的前提下，通过排列组合的方式，对不同参数也进行相应的变异，有效提升测试用例覆盖率。

ASFuzzer是一款针对Android系统服务安全测试的半自动化工具，可以安装到不同Android版本系统进行测试，包括谷歌原厂镜像及第三方定制系统。该工具分为模糊测试和遗传变异2个模块。模糊测试模块主要是对服务接口进行测试并进行结果反馈。该模块首先使用反射机制获取到系统服务信息，同时将服务接口、参数等信息保存在数据库以供调用。而后，根据接口参数类型构造生成初始测试用例，通过Binder调用transact方法对服务进行测试，而测试结果则会输出到日志中，最终反馈给遗传变异模块。遗传变异模块则主要对参数用例进行优化、变异。在获取到前次的结果反馈后，根据相应的策略，对单个参数或者多个参数进行变异，然后再次循环测试，直至发现漏洞或到达变异次数。其整体设计框架如图3所示。

图3 ASFuzzer整体设计框架

3.2 模糊测试模块

该模块功能主要对服务接口进行测试，并将结果进行反馈。

1)服务接口信息获取。

系统服务相关信息主要是通过对ServiceManager反射来获取的。ServiceManager是系统服务的管理者，其内部维护了已注册系统服务的Binder对象列表，这样可以通过反射android.os.ServiceManager的方式获取其对象实例，再反射[14]调用listservices方法就可以得到系统中运行的服务信息。而调用getService则会得到相应服务的Binder句柄。

对于测试用例的构造，需要获得测试服务的接口号及对应参数。当获取到服务的Binder句柄后,可以通过反射“接口描述符+＄Stub”的方法获取服务中的各种方法属性。其中会有以“TRANSACTION_”开头的方法及属性描述，而属性中int型就是该方法对应的接口号[4]。最后通过将接口描述符传入Class.forname进而反射调用getDeclaredMethods和getParameterTypes的方式获取服务所定义的接口方法及参数类型。

2)测试用例的构造与发送。

测试用例的构造直接关乎数据能否顺利通过目标的参数校验[15]。通过对数据库中参数类型分析统计可得，除了常规类型外，还有一些Binder、Component Name、Intent等系统类类型。对于可以构造的参数类型，通过常识去进行构造或者对其进行反射构造函数获取，而对于无法直接或间接构造的类型，使用null值对其填充。为了大概率构造异常数据，初始值的选择一般选择边界值或者0值附近的值，样本初始数据构造如表2所示。

表2 初始数据构造表

测试用例的构造即transact需要发送的内容。第一个填充的是方法接口号，第二个data则要填充各种类型的参数数据。但data要先填充该服务的接口描述符，以保证数据顺利通过底层校验，然后再根据参数类型选择初始数据填充。replay默认为空，而flag参数一般填充0。最后获取到待测服务的Binder句柄，调用transact方法即可对接口号对应的方法发起测试。

3)日志异常监控。

日志异常反馈对测试用例的遗传变异具有重要的指导作用[16]。ASFuzzer在测试过程中可能会出现各种异常，如参数不合法、Binder失活、系统进程崩溃、手机重启等其他不可知后果，因此需要对ASFuzzer及系统状态进行监控记录。主要记录有2部分内容：

①ASFuzzer模糊测试过程中所发送的测试用例，transact的返回值，replay接收服务端的返回信息，以及其他异常。该部分异常信息，需要反馈给遗传变异模块，作为前次测试用例的适应度评判。

②系统相关日志，用来记录系统崩溃或重启以及其他未知异常。

ASFuzzer实现了日志记录的功能，将测试结果等信息导出到文件中。这样有利于事后快速定位异常发生的服务接口及其当次所发送的参数等，提高了确认漏洞的效率。

3.3 遗传变异模块

遗传算法不断优化个体的思想，可以应用到系统服务测试数据生成中。整体过程可分为初始化样本，适应度函数评价、变异、交叉、选择等。其流程如图4所示。

图4 遗传变异模块流程

1)编码方案与适应度函数的确定。

编码是将问题空间的解转化为遗传过程中所能识别的基因个体，是对问题解的一种表现形式[17]。作为遗传算法中个体进化变异的基础，编码形式往往会根据实际问题情况而采取不同的方案。对于系统服务的漏洞挖掘，测试用例中的参数没有固定的数据类型。为了更好地被底层接口识别，可以将参数类型作为编码方案的选取，直接采用对应数据类型的实数作为编码个体的选择[18]。每个参数即为编码个体，不用对其解码，简化了算法过程。

适应度函数是对个体进行优良判断的定量准则，以个体适应度的大小来确定该个体在选择阶段被选中的概率[19]。适应度值越大，被选为优秀个体进行遗传的概率也越大，进而引导程序向最优解方向发展。常规适应度函数的选取会直接采用待求函数，通过待求函数对当前用例的直接反应来判断个体的好坏。这种用待求解问题的标准来对个体适应性进行评估的方法，可以充分表达求解问题的需求。

系统服务模糊测试的目的是通过不断发送异常参数来挖掘漏洞。触发漏洞是最终目标，而触发漏洞的异常参数就是待求的解。遗传算法的选择变异过程可以生成各种正常或非正常参数，测试参数取值的多样化往往能够大概率发现漏洞。结合系统服务实际情况，可以将适应度函数定义如下:

(1)

其中，n为测试样例中参数个数，该模型适用于单参数和多参数的场景。当只有一个参数时，适应度函数就是一个二项分布函数。测试用例中有多个参数时，每种类型参数的适应度都为参数数目分之一，原因是每个类型的参数有可能是优异个体或者是劣质个体。在未触发到异常之前，无法片面去评判某种类型参数的优劣，所以在后续过程中要使用合适的选择算子对个体做出挑选。如果测试用例触发异常，遗传概率则为0，即不对其进行变异，此时需要对参数变进行观察，判断参数应该选择抛弃还是触发了漏洞，选择抛弃则需要重新生成初始数据，而触发漏洞则说明已经达到了测试效果，获取到问题的最优解。未触发异常时，测试用例适用度为1/n，则需要对测试用例进行选择交叉变异等操作，再次进行测试。

2)选择算子的选取。

选择操作是使用选择算子从前次测试群体中选择优秀个体，进行交叉变异后遗传给下一代的一种选择机制，是遗传变异过程中保优去劣的重要一环。常用的选择模式有轮盘赌选择[20]、最佳个体保存、排序模型、联赛选择模型等[21]。每种模式都有其优缺点，对于单个参数的测试用例，在初始样本未触发到系统异常或漏洞的情况下，根据适应度函数计算，其值为1。选择算子模式为确定性选择，即当前测试用例个体U为优异个体，将会遗传给下一代进行交叉变异。后续单个参数的用例同样采取该选择模式。

实际测试中，单个参数的测试用例较少，多为2个及以上参数。用例Group(U1,U2,U3，…，UN)初始群体经过首轮测试，代入适应度函数得出每个个体Ui的适应度值均为1/n。在个体适应度相等的情况下，如何选择优异个体对于后续用例的遗传尤为重要。为了减小多维参数同时变异对遗传选择过程的干扰，在结合类型概率排序的前提下，提出一种基于组合的遗传算子挑选模型。该模型首先对测试用例中的参数类型进行一个变异优先级排序，再根据组合公式挑选每次测试需要变异的个体。参数类型排序是根据其在服务接口中出现频数及参数个体的可变异空间分配优先级。参数个体有所属的数据类型，每种参数类型有其特定的数据范围。如布尔型只有false和true，字节型取值范围为(-128,127),而整型、浮点型等类型的取值范围就很大。为更快收敛到最优解，挖掘到漏洞，将出现频数高且变异空间取值范围小的数据类型分配高优先级，而将需要构造的参数类型的默认为低优先级。因此定义了类型变异选择优先级如表3所示，其中数值越小代表其被优先挑选的概率越大。

表3 类型变异选择优先级表

测试用例中的参数首先根据类型变异选择优先级表对参数类型进行一个排序，然后再根据选择算子挑选算法选出该次需要变异的个体。挑选算法过程具体如下。

定义：

PriorityMap//根据表3定义

Group(ParaType_U1,ParaType_U2,…,ParaType_Un)

PriorityList=[] //用来保存参数对应的优先级

ParaTypePriorityMap

M=Group.length //参数群体个数

算法：

输入：当前测试参数群体Group(ParaType…)

for(i=0;i

{

Priority=PriorityMap.get(Group[i])

if(PriorityList.exist(Priority))//判断同类型

Priority=Priority+"-"+i; //同优先级添加标志

ParaTypePriorityMap.put(Group[i]:Priority)

PriorityList.add(Priority)

}

PriorityList=Sort(PriorityList) //从小到大排序

for(j=1;j<=M;j++)

{Combination_select(PriorityList,M,j)}

Combination_select函数以组合公式为原型：

输出：被挑选的优先级数字序列[x]。

下面以输入group(int,byte,long)为例：

①根据类型选择优先级映射表得到：

ParaTypePriorityMap(int:6,byte:2,long:8)

PriorityList[6,2,8]

②排序：

PriorityList[2,6,8]

代入组合公式(1<=j<=3)：

Combination_select([2,6,8],3,j)

③当j=1,输出:[2],[6],[8]

当j=2,输出:[2,6],[2,8],[6,8]

当j=3,输出:[2,6,8]

④根据ParaTypePriorityMap可得：

第一次被选择类型为byte

第二次被选择类型为int

…

第四次被选择类型为int，byte

…

第七次被选择类型为int,byte,long

初始群体根据对应的参数类型生成优先级序列，在对应过程中要注意种群中可能存在相同参数类型，可添加相应标志进行区分。然后序列排序后代入组合公式函数进行挑选。最后被挑选的优先级序列再对照找到其对应的数据类型。要注意的是该算法选择的是多个参数中哪些类型的参数需要改变，并不影响测试模块中数据的填充顺序。在一组测试用例遗传变异过程中，被选择到的个体默认是被选中的优秀个体，即将对其进行交叉变异操作，而用例中没有被选中的个体则保持原值传递，直至次数达到或者触发漏洞。此种遗传算子挑选模型在一定程度上避免了组合爆炸带来的混乱问题，也保证了优秀个体的有效传递。

3)交叉变异操作。

参数用例的多样性越好，触发漏洞的几率就越大。而交叉变异就是使不同个体向较为优化的局部叠加，生成新个体的主要过程。作为被挑选的优秀个体，需要对其进行相应的交叉变异操作。结合遗传算法编码方案的选取，为简化算法和保留个体有效性，对个体不采取交叉操作，只对其进行变异操作。常用的变异策略有随机变异、边界变异、多项式变异等[22]。结合模糊测试实际情况，参数个体都有不同的数据类型，所以根据参数所属类型的差别也采取相应的变异策略。对于int、float、long、double等常规类型参数，变异算子如图5所示。

图5 变异算子选择模型

数值根据[1,2,3,4,5]元素排列组合生成的序列执行不同的操作，其中为保证生成的数据能发散到各个数据段，constant值也根据类型相应变化赋值。该次变异后的数据会被保存作为下次的初始值输入，保证数据有效性地传递。而对于int[]、float[]等数组类型的数据，其中变异的不只是数据，还有数组的长度。对于数据的填充，仍可以采用以上的常规类型的遗传算子进行生成。长度的控制则每次动态生成，可以通过该测试次数对自定义的最大长度取余加1确定。

对于Binder、ComponentName等非常规数据类型，变异方式采用随机变异。Binder是各种服务的句柄，可以通过反射得到。ComponentName类型的参数，可以根据系统内置的一些固定用法进行构造。而对于存在多个构造函数的参数类，构造函数的选取可以使用随机变异，但构造函数中常规类型参数的构造仍采用图5所示的变异算子进行构造填充。

4)终止条件。

ASFuzzer框架默认下一代用例更优，即要对用例进行遗传变异操作。当测试用例中的异常参数触发漏洞，则可终止测试[23]。但大多数测试用例可以顺利通过接口测试，对于这种情况，就需要对变异次数进行一定的限制。对于单个参数的变异，次数区间建议设置在[300,500]，而对于多个参数的变异，则主要是根据接口参数类型的不同组合进行次数限制。每种不同的参数类型变异组合测试可设置为300次。而对于那些接口有权限检测或者参数校验的情况，当用例测试到一定次数即可停止测试，判定此接口安全。

4 实验结果与验证分析

4.1 实验环境

ASFuzzer测试框架采用Java语言开发，并将其安装在不同系统的手机上进行测试，包括谷歌原生Android系统及第三方定制系统。实验均采用真机测试，以保证结果的真实可靠。其中Nexus5x手机搭载谷歌原生系统版本分别为bullhead Android 6.0.0、bullhead Android 7.1.1和bullhead Android 8.1.0。Pixel手机搭载谷歌原生系统sailfish Android 9.0.0和sailfish Android 10.0.0。小米机型为MI3,系统为MIUI8 7.6.11|开发版。OPPO机型为OPPO-R9s-Plus,操作系统为ColorOS。

4.2 系统服务漏洞列表

ASFuzzer共发现25个Android系统服务安全漏洞，漏洞行为主要有手机重启、应用拒绝服务、手机黑屏、系统应用进程停止运行等。目前已将相关漏洞提交给厂家确认。漏洞详细信息如表4和表5所示。

表4 谷歌原生Android系统漏洞

表5 第三方定制系统漏洞

4.3 挖掘能力分析

从实验结果分析来看，ASFuzzer框架挖掘到的漏洞数量在相同系统版本情况下，多于文献[3]使用的常规模糊测试挖掘到的系统服务漏洞数目，并且在第三方厂家定制系统上测试也取得了一定的成果。遗传算法变异生成高多样化的测试用例，大大提高了触发漏洞的可能性。通过分析产生异常的接口及其参数，在25个漏洞中有19个是因为多参数组合变异所引起的漏洞，即只有当特定数据被填充才会引发异常。实验结果说明基于遗传算法的模糊测试在系统服务的漏洞挖掘中远优于常规的模糊测试方法，具有一定的高效性与优越性。

在遗传算法挖掘策略上，文献[13]在选择算子阶段采用随机的方式对当前种群中的个体进行挑选。作为即将进入下一轮的个体，随机挑选可能会错失优异个体，进而误导测试的方向，影响挖掘效率。而本文充分利用单个参数的可变异范围及参数的数量关系，并结合排列组合的方式对遗传算法过程中的选择运算进行指导，保证了优秀个体的及时输入，从而引导挖掘测试向高效的方向发展。

4.4 系统服务安全性分析

SystemServer系统进程运行着大量的基本服务，单个服务引起的异常极易引起系统进程的崩溃，从而影响到Android系统的稳定。通过对服务端返回的reply信息以及系统日志等分析发现，系统服务出现的安全异常主要体现在以下4个方面：

1)存在少量不合法参数异常。原因是有些参数类型无法构造或者使用了null填充，无法通过底层目标函数的参数校验。

2)出现较多安全异常。说明目标函数对调用者的身份权限做了判断，对接口增加了防护。

3)日志信息无明显异常。说明参数通过了目标函数的参数校验或权限判断。此类接口默认低权限可以调用，接口对外暴露，是漏洞挖掘的重点。

4)严重异常信息。如系统重启、拒绝服务、系统应用崩溃等，表明该接口存在严重漏洞。

综合以上结果及漏洞成因分析，可以得出系统服务安全防护的3要素：参数校验、权限判断、异常处理。做好以上3点可以在一定程度上加强Android系统服务的安全性。

5 结束语

本文在Binder与系统服务之间的通信基础上设计了ASFuzzer系统服务漏洞挖掘工具。经过遗传算法对用例的持续优化，使其生成更全面、更多样化的用例去测试目标函数，进而触发漏洞。在不同系统上测试结果显示，ASFuzzer测试框架可以有效地对系统服务进行漏洞挖掘，进而发现其中潜在的一些安全问题；同时也表明了该方案相比常规模糊测试挖掘方法效率的优越性。但该工具仍存在一些不足，如对异常信息的记录及分析不能做到完全自动化，测试结果对遗传算法的反馈处理不够细腻等。这些不足之处都需要在未来对其进行改进和优化，以便提高测试效率。