面向Android 系统安全的在线学习算法研究

周颖颖

摘要：目前，移动终端使用过程中存在诸多安全隐患，影响着整个系统的安全。因此，在面向Android移动终端基础上，研究一种新的入侵检测算法显得尤为重要。首先，通过Android平台，收集移动终端内核信息，并进行及时有效的预处理，借助快速核密度，正确估计Fast Kernel Density Estimation（FastKDE）算法压缩收集到的大规模样本，从而得到数量合理的训练样本，为后面工作打下基础。然后，以在线增量学习算法为基础，通过支持向量机算法判别经过处理的相关数据，从而识别出入侵数据。最后，通过试验以及相关的数据分析，得出该方法有利于缩减训练时间，使检测性能达到最佳效果，可扩展性较好，且具有较好的自我提升能力。

关键词：Android系统 在线学习算法；支持向量机；快速核密度；在线增量学习

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）26-0103-03

1 基本概述

截止2014年第一季度，以市场研究公司IDC发布的数据为依据，市场份额占有比例中，Android移动终端高达78.9%。随着我国经济发展，科学技术的突飞猛进，3G、4G等到广泛运用，基于Android系统下的移动终端更是日益丰富于互联网上，并且PC机上的互联网应用均可移至移动终端。虽然Android移动终端与PC机间的差异逐日缩减，但PC机的安全问题通过Android移动终端日益凸显。Android具有开源性的特征，能够借助内核，查找系统存在的漏洞，并植入相关病毒，侵害Android移动终端，获得不正当的经济效益。由此可见，基于移动终端入侵检测算法的研究成为该行业的一大重点与热点。

2 相关算法的提出

1）2007年，Jerry Cheng等人提出利用移动终端间的合作进行病毒检测与预警系统SmartSiren，该系统主要工作原理即为通过移动终端的协作互助，以联合分析方法为基础，检测单个终端或者整个系统的异常状况。如果发现有病毒存在，对受到威胁的移动终端直接发出警报，达到预防病毒扩散整个移动终端的目的。

2）傅德胜等学者提出轻量级的手机入侵检测人系统，其主要工作原理如下：在手机平台中运用snort技术，实现监听相关网络数据的目的，借助完全自动机匹配方式，提高入侵检测的速度。

3） Asaf Shabtai等人于2010年利用Knowledge based temporal abstraction（即KBTA）算法构建了入侵检测模型，其主要通过监控手机中的CPU、网络数据以及用户的活动状况等内容实现的。在此前提下，依据时间趋势图，判断用户的正常活动与异常活动，充分发挥智能手机的时间序列的功能。

4） Jeffrey Bickford等人从智能手机在检测恶意软件过程中引起的额外能耗的问题出发，在考虑攻击监控范畴和恶意软件扫描频率的基础上，提出折中安全与能耗的检测方法，通过较少的额外能量消耗，达到检测出大部分恶意软件的攻击的效果。

5） 吴志中等人提出在分布式移动设备异常检测系统框架的基础上，通过D-S理论，融合多个算法检测结果，促进检测准确率的提高。

Android移动终端所收集的诸多数据均具有相似性，因此，在进行数据检测分析的过程中，以上所述的五种方法必须建立较大规模的样本训练集，导致样本收集工作复杂，花费时间较长，而且容易出现问题。另外，在Android移动终端收集到新数据后，必须经过原始训练样本集与新数据之间的融合，重新建立训练样本集。由此可见，这些入侵检测系统存在扩展性较低，且不适用等问题。

因此，在前面分析的基础上，本文将以FastKDE算法为基础，提出在线快速核密度估计的新方法，即Online Fast Kernel Density Estimation，OFastKDE，在此方法运用中，通过FastKDE算法有效压缩规模较大的数据样本集，提取能够代表样本集分布特征的样本，从而提炼出规模合理的新样本集。支持向量机SVM算法处理小规模数据样本时，能够较好的进行数据分析，因此，利用SVM对经过FastKDE算法提炼出的新的数据样本进行分类，从而判断出移动终端手攻击程度。如果收集到新的数据，移动终端将在高维空间映射出表示这些数据的特征向量，从而计算出其到超平面的距离，用于作为分类的依据，实现样本的有效替换，达到新数据在线学习的目的。本文借助实验，通过实验的具体数据分析，证明其具有较高的实用价值。

3 探究面向Android移动终端的异常入侵检测系统

如今使用的大部分移动终端和PC机具有诸多相似的功能，而且PC机的功能移动终端大致已经具备，因此，两者间的异常入侵检测系统模型大致相似。

图1 入侵检测系统结构

3.1 移动终端主体活动

移动终端主体活动即为数据收集模块，在收集数据信息，检测移动终端是否遭受攻击的过程中应注意以下几方面：首先，构建Android系统的模拟环境；其次利用编程收集Android移动终端的相关内核信息，主要包括内存、CPU、网络等，得出与实验相关的数据。实验在用户正常使用移动终端的基础上，提取相关数据，包括两方面：一是终端未受到入侵时的主体活动信息；二是终端受到入侵时的主体活动信息。然而，智能手机受到攻击主要包含三种情况：第一种，较短时间内受到大量垃圾信息，导致通信堵塞；第二种，短时间内下载大量图片、文件，并且受到大量信息，导致用户的资费和流量浪费；第三，短时间内内存卡被恶意文件损害。用户正常使用智能手机的依据包括以下几方面的操作：接打电话、玩游戏、收发短信、文档编辑、音乐和视频播放、文件上传与下载、正常使用网络、软件及时更新等相关手机操作。

3.2 分析与建模方式以及决策规则

这两部分即为数据分析模块，属于入侵检测系统的核心，其主要内容是分析、研究收集到的数据，并且构建正常样本的特征轮廓，为作比较提供依据。设定标准阈值，以供与正常特征轮廓和测试样本的特征轮廓的偏离值比较，如果偏离值小于阈值，则为正常，如果偏离值大于阈值，则为被入侵。

下面将通过C-SVC和V-SVC两种方法进行数据分析：

1）C-SVC方法运用研究

指定训练本集如下：[zi=（xi，yi）ni=1]，[xi∈Rd（1≤i≤n）]，[yi∈±1]，其中C-SVC的原始问题我们可以通过如下公式进行表示：

[minw，b，ξ12w2+ci=1nξi]

S.t.[yi（w′?（xi）+b）≥1-ξi，ξi≥0，1≤i≤n]

其中与之相对应的对偶问题可进行如下表示：

[mina12a′Qa-e′a]

S.t. [y′a=0，0≤ai≤c，1≤i≤n]

从这里的相关公式以及数据，我们可知Q为[n×n]的矩形方阵，最后利用公式展示其决策函数：

[sgn（w′?（x）+b）=sgn（i=0nyiaik（xi，x）+b）]

2）v-SVC方法运用研究

v-SVC是一种支持向量方法，包含参数v，其主要优点及作用在于有效控制向量的数目。 指定训练本集如下：[Zi=（xi，yni=1i）]，[xi∈Rd（1≤i≤n）]，[yi∈±1]，其中v-SVC的原始问题我们可以通过如下公式进行表示：

[minw，b，ξ，p12w2-vp+1ni=1nξi]

S.t. [yi（w′?（xi）+b）≥p-ξi]，其中[ξi≥0，1≤i≤n，p≥0]，

在此过程中V属于[0，1]，与之对应的对偶问题可进行如下表示：

[mina12a′Qay′a=0，e′a≥v，0≤ai≤1n，1≤i≤n]

在此过程中，[Qij=yiyjk（xi，xj）]，其中核函数为[k（xi，xj）=?（xi）′?（xj）]，最后利用公式展示其决策函数：[sgn（w′?（x）+b）=sgni=0nyiaik（xi，x）+b]。

从以上相关公式、实验可得知，训练样本数据数量十分庞大，数据间的冗余度较高，极大程度上增加了训练的时间，导致算法增加难度，致使其精准度难以达到标准。针对此问题，以目前的较大数据处理方式为依据，在进行原始训练样本压缩时，引进快速核密度估计，即FastKDE算法。在此算法的基础上，研究样本数据，提高样本数量选择的合理性，节约算法时间的前提下，降低算法的复杂程度，提高算法精准度，增加准确率。

4 通过快速核密度估计进行在线增量学习算法框架构建

4.1 快速核密度估计

在Freedman提出的相关理论基础上，提出快速核密度估计定理，并通过相关实验进行证明。

1）核密度估计：其是实用价值较高的非参数密度估计算法，使用领域较广。KDE算法直接根据训练样本获取样本特征的分布情况，根本不需对数据进行先验假设，其主要用于对任意形状的密度函数进行估计。其算法如下：

数据集为S∈Rd，其容量为N，表达式为[P（x）=1Ni=1Nk（x，xi）]，[k（x，xi）]是核函数，其正定带宽矩阵表示为[H=h]2I，原始数据中的抽样容量为m的一个子集，由抽样子集m数据中得到的KDE为[p（x）]，其具体表示为：

Min D[（p（x），p（x））]

S.t. [p（x）=1mi=1mk（x，xi）]

D[（p（x），p（x））]表示的是当m小于n时，[p（x）]与[p（x）]之间存在的误差，相较于传统的较复杂的算法，快速核密度估计更加简单、方便，使其具有产生的必要性。

2）快速核密度估计：当S∈Rd，容量为n是借助相关数据得到的[p（x）]，以及在[k（x，xi）]下的[H=h]2I的核函数，在此基础上，假设m集得到的KDE表达式为[p（x）]。那么[p（x）]与[p（x）]之间的积分平方误差可用以下公式进行表达：[J=E（p（x）-p（x）2dx]，因此，J≤[4Ah+A2h2V+Bmhd+ABVmhd-1]。

在此，需要强调A、B、V与m和[h]没有具体联系，属于常量，而J的大小与m和h存在一定的关系，与N也无关系。从公式我们可以发现，当m数值足够大时，[h]数值适中，[p（x）]与[p（x）]之间的值将处于无限接近的状态。

在前面假设情况的前提下，Wang[p（x）]与[p（x）]之间尚的积分平分误差公式如下：

[J=E（p（x）-p（x））2dx+λE1-（P（x））2dx]，在此公式下，我们知道J的上界与d、m、[h]、[λ]有关，而与N无关。

除此之外，深入研究探究数值之间的关系，从实验结果可以分析发现，m数值的大小，影响着KDE的速度和准确性，并且该方法较简单，利用较少的数据，得出解决问题的方法，保证实验效果。

4.2 在线增量学习分析研究

Ivor Wai-Hung Tsang等相关研究者提出核向量机算法，即CVM（Core Vector Machine），其是一种借助[（1+ε）]的方法实现MEB的快速求解。Di Wang等人在此基础上进行优化、升级，提出了新的在线核心向量机学习方法，但因每次需要增加训练，导致计算较复杂，实用性不高。在线球向量机，即Online Ball Vector Machine（OBVM），由杨海峰等学者提出，其主要原理为：首先将二分类问题进行转化，形成两个单分类。其次，通过BVM算法进行训练向量迭代。最后，对球心进行求解，借助球心的垂直平分进行分类。

以上几种方法均可运用于在线学习，但如果运用于增量学习，其存在几方面的问题：第一，对所有的历史数据进行考虑，缺少遗忘机制的设置；第二，如果大量增加样本，在进行样本保存时，计算具有较大的复杂性，易出现数据上的错误。针对以上问题，笔者将以遗忘机制为基础，提出具有实际意义的增量学习FastKDE算法，即OFastKDE。

1）简要分析OFastKDE算法

相较于之前的诸多算法，OFastKDE算法能较好的适应不断增加的数据集，有利于克服庞大数据的计算问题。其主要原理如下：首先，利用FastKDE评估训练样本的规模，获得有效样本。其次，通过在线增量学习算法，借助SVM，剔除难以成为支持向量的样本，缩减学习过程，提高效率，从而判断入侵情况。其具体算法的步骤如下所示：

第一步：制定恰当的数据集[S=x1，...，xN∈Rd]，标签集[Yi=-1，+1，1≤i≤N]，初始化下的[S+，S-]均为空。

第二步：利用FastKDE，对数据集S进行有效压缩，得到[S0=x1，...，xm]。

第三步：代入[S0=x1，...，xm]，通过SVM算法，达到解决QP的问题，获得训练集对应的超平面。

第四步：将新的训练向量[Xq]映射至高维[?（Zq）]中，如果[?（Zq）]标签为正，则可进行第六步或者第七步。

第五步：计算d，即[Xq]与超平面之间的距离，如果距离大于[1+ε]，那么[S+=S+??（zq}]。

第六步：计算d，即[Xq]与超平面之间的距离，如果距离大于[1+ε]，那么[S-=S-??（zq}]。

第七步：如果[S+，S-]的元素超过阈值，将淘汰[S0]中的非支持向量，再将[S+，S-]的元素移至[S0]，保持[S+，S-]处于置空状态，然后转向第三步。

2）时间复杂度的研究分析

在给定的数据集N中，利用抽样获得的m数据点，经过OFastKDE，借助时间复杂度解决QP及相关问题。值得注意的是，时间复杂度仅受m的影响，与N无关。如果m远小于N，则OFastKDE会显示出其强大的竞争力。

5 小结

本文以Android智能手机所收集的数据为依据，通过OFastKDE方法有效评估训练样本的规模，获得较合理的样本，缩减计算时间，降低复杂程度。在在线增量学习算法的基础上，借助支持向量机在小数据处理方面的优势，剔除非支持向量的相关数据，实现学习过程过程的加速，对入侵情况进行有效检测。从实验得出的相关数据分析，OFastKDE具有较高的扩展性，具有良好的自我提升能力，有助于Android智能手机异常检测功能的优化，实现高效维护手机安全。同时在此实验过程中，因数据采集受到模拟攻击的种类影响，导致实验结果存在偏差，因此，为更好的进行这方面的研究，需要相关企业公司加大对其的资金设备投入，为研究工作提供优质环境，保障实验结果的正确性，增加企业竞争力，从而促进企业发展，推动国家经济发展。

参考文献：

[1] 葛唯唯， 刘渊. 面向Android系统安全分析的在线学习算法研究[J]. 计算机应用研究， 2015（9）.

[2] 张钢， 谢晓珊， 黄英， 等. 面向大数据流的半监督在线多核学习算法[J]. 智能系统学报， 2014（3）.

[3] 李彬， 荣学文. 单隐层前向神经网络在线学习算法综述与性能分析[C]// 东北大学、IEEE新加坡工业电子分会、IEEE控制系统协会哈尔滨分会.第25届中国控制与决策会议论文集. 东北大学、IEEE新加坡工业电子分会、IEEE控制系统协会哈尔滨分会， 2013.

[4] 王爱平， 万国伟， 程志全， 等. 支持在线学习的增量式极端随机森林分类器[J]. 软件学报， 2011（9）.

[5] 孙博良， 李国辉. 一种具有遗忘特性的在线学习算法框架[J]. 国防科技大学学报， 2014（4）.

[6] 林金星， 沈炯， 李益国. 基于免疫原理的径向基函数网络在线学习算法及其在热工过程大范围工况建模中的应用[J]. 中国电机工程学报， 2006，26（9）.

[7] 赵强利. 基于选择性集成的在线机器学习关键技术研究[D]. 长沙： 国防科学技术大学， 2010.

[8] 李志杰， 李元香， 王峰， 等. 面向大数据分析的在线学习算法综述[J]. 计算机研究与发展， 2015（8）.