面向Android 系統(tǒng)安全的在線學(xué)習(xí)算法研究

周穎穎

摘要：目前，移動(dòng)終端使用過(guò)程中存在諸多安全隱患，影響著整個(gè)系統(tǒng)的安全。因此，在面向Android移動(dòng)終端基礎(chǔ)上，研究一種新的入侵檢測(cè)算法顯得尤為重要。首先，通過(guò)Android平臺(tái)，收集移動(dòng)終端內(nèi)核信息，并進(jìn)行及時(shí)有效的預(yù)處理，借助快速核密度，正確估計(jì)Fast Kernel Density Estimation（FastKDE）算法壓縮收集到的大規(guī)模樣本，從而得到數(shù)量合理的訓(xùn)練樣本，為后面工作打下基礎(chǔ)。然后，以在線增量學(xué)習(xí)算法為基礎(chǔ)，通過(guò)支持向量機(jī)算法判別經(jīng)過(guò)處理的相關(guān)數(shù)據(jù)，從而識(shí)別出入侵?jǐn)?shù)據(jù)。最后，通過(guò)試驗(yàn)以及相關(guān)的數(shù)據(jù)分析，得出該方法有利于縮減訓(xùn)練時(shí)間，使檢測(cè)性能達(dá)到最佳效果，可擴(kuò)展性較好，且具有較好的自我提升能力。

關(guān)鍵詞：Android系統(tǒng) 在線學(xué)習(xí)算法；支持向量機(jī)；快速核密度；在線增量學(xué)習(xí)

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）26-0103-03

1 基本概述

截止2014年第一季度，以市場(chǎng)研究公司IDC發(fā)布的數(shù)據(jù)為依據(jù)，市場(chǎng)份額占有比例中，Android移動(dòng)終端高達(dá)78.9%。隨著我國(guó)經(jīng)濟(jì)發(fā)展，科學(xué)技術(shù)的突飛猛進(jìn)，3G、4G等到廣泛運(yùn)用，基于Android系統(tǒng)下的移動(dòng)終端更是日益豐富于互聯(lián)網(wǎng)上，并且PC機(jī)上的互聯(lián)網(wǎng)應(yīng)用均可移至移動(dòng)終端。雖然Android移動(dòng)終端與PC機(jī)間的差異逐日縮減，但PC機(jī)的安全問(wèn)題通過(guò)Android移動(dòng)終端日益凸顯。Android具有開(kāi)源性的特征，能夠借助內(nèi)核，查找系統(tǒng)存在的漏洞，并植入相關(guān)病毒，侵害Android移動(dòng)終端，獲得不正當(dāng)?shù)慕?jīng)濟(jì)效益。由此可見(jiàn)，基于移動(dòng)終端入侵檢測(cè)算法的研究成為該行業(yè)的一大重點(diǎn)與熱點(diǎn)。

2 相關(guān)算法的提出

1）2007年，Jerry Cheng等人提出利用移動(dòng)終端間的合作進(jìn)行病毒檢測(cè)與預(yù)警系統(tǒng)SmartSiren，該系統(tǒng)主要工作原理即為通過(guò)移動(dòng)終端的協(xié)作互助，以聯(lián)合分析方法為基礎(chǔ)，檢測(cè)單個(gè)終端或者整個(gè)系統(tǒng)的異常狀況。如果發(fā)現(xiàn)有病毒存在，對(duì)受到威脅的移動(dòng)終端直接發(fā)出警報(bào)，達(dá)到預(yù)防病毒擴(kuò)散整個(gè)移動(dòng)終端的目的。

2）傅德勝等學(xué)者提出輕量級(jí)的手機(jī)入侵檢測(cè)人系統(tǒng)，其主要工作原理如下：在手機(jī)平臺(tái)中運(yùn)用snort技術(shù)，實(shí)現(xiàn)監(jiān)聽(tīng)相關(guān)網(wǎng)絡(luò)數(shù)據(jù)的目的，借助完全自動(dòng)機(jī)匹配方式，提高入侵檢測(cè)的速度。

3） Asaf Shabtai等人于2010年利用Knowledge based temporal abstraction（即KBTA）算法構(gòu)建了入侵檢測(cè)模型，其主要通過(guò)監(jiān)控手機(jī)中的CPU、網(wǎng)絡(luò)數(shù)據(jù)以及用戶的活動(dòng)狀況等內(nèi)容實(shí)現(xiàn)的。在此前提下，依據(jù)時(shí)間趨勢(shì)圖，判斷用戶的正?；顒?dòng)與異?；顒?dòng)，充分發(fā)揮智能手機(jī)的時(shí)間序列的功能。

4） Jeffrey Bickford等人從智能手機(jī)在檢測(cè)惡意軟件過(guò)程中引起的額外能耗的問(wèn)題出發(fā)，在考慮攻擊監(jiān)控范疇和惡意軟件掃描頻率的基礎(chǔ)上，提出折中安全與能耗的檢測(cè)方法，通過(guò)較少的額外能量消耗，達(dá)到檢測(cè)出大部分惡意軟件的攻擊的效果。

5） 吳志中等人提出在分布式移動(dòng)設(shè)備異常檢測(cè)系統(tǒng)框架的基礎(chǔ)上，通過(guò)D-S理論，融合多個(gè)算法檢測(cè)結(jié)果，促進(jìn)檢測(cè)準(zhǔn)確率的提高。

Android移動(dòng)終端所收集的諸多數(shù)據(jù)均具有相似性，因此，在進(jìn)行數(shù)據(jù)檢測(cè)分析的過(guò)程中，以上所述的五種方法必須建立較大規(guī)模的樣本訓(xùn)練集，導(dǎo)致樣本收集工作復(fù)雜，花費(fèi)時(shí)間較長(zhǎng)，而且容易出現(xiàn)問(wèn)題。另外，在Android移動(dòng)終端收集到新數(shù)據(jù)后，必須經(jīng)過(guò)原始訓(xùn)練樣本集與新數(shù)據(jù)之間的融合，重新建立訓(xùn)練樣本集。由此可見(jiàn)，這些入侵檢測(cè)系統(tǒng)存在擴(kuò)展性較低，且不適用等問(wèn)題。

因此，在前面分析的基礎(chǔ)上，本文將以FastKDE算法為基礎(chǔ)，提出在線快速核密度估計(jì)的新方法，即Online Fast Kernel Density Estimation，OFastKDE，在此方法運(yùn)用中，通過(guò)FastKDE算法有效壓縮規(guī)模較大的數(shù)據(jù)樣本集，提取能夠代表樣本集分布特征的樣本，從而提煉出規(guī)模合理的新樣本集。支持向量機(jī)SVM算法處理小規(guī)模數(shù)據(jù)樣本時(shí)，能夠較好的進(jìn)行數(shù)據(jù)分析，因此，利用SVM對(duì)經(jīng)過(guò)FastKDE算法提煉出的新的數(shù)據(jù)樣本進(jìn)行分類，從而判斷出移動(dòng)終端手攻擊程度。如果收集到新的數(shù)據(jù)，移動(dòng)終端將在高維空間映射出表示這些數(shù)據(jù)的特征向量，從而計(jì)算出其到超平面的距離，用于作為分類的依據(jù)，實(shí)現(xiàn)樣本的有效替換，達(dá)到新數(shù)據(jù)在線學(xué)習(xí)的目的。本文借助實(shí)驗(yàn)，通過(guò)實(shí)驗(yàn)的具體數(shù)據(jù)分析，證明其具有較高的實(shí)用價(jià)值。

3 探究面向Android移動(dòng)終端的異常入侵檢測(cè)系統(tǒng)

如今使用的大部分移動(dòng)終端和PC機(jī)具有諸多相似的功能，而且PC機(jī)的功能移動(dòng)終端大致已經(jīng)具備，因此，兩者間的異常入侵檢測(cè)系統(tǒng)模型大致相似。

圖1 入侵檢測(cè)系統(tǒng)結(jié)構(gòu)

3.1 移動(dòng)終端主體活動(dòng)

移動(dòng)終端主體活動(dòng)即為數(shù)據(jù)收集模塊，在收集數(shù)據(jù)信息，檢測(cè)移動(dòng)終端是否遭受攻擊的過(guò)程中應(yīng)注意以下幾方面：首先，構(gòu)建Android系統(tǒng)的模擬環(huán)境；其次利用編程收集Android移動(dòng)終端的相關(guān)內(nèi)核信息，主要包括內(nèi)存、CPU、網(wǎng)絡(luò)等，得出與實(shí)驗(yàn)相關(guān)的數(shù)據(jù)。實(shí)驗(yàn)在用戶正常使用移動(dòng)終端的基礎(chǔ)上，提取相關(guān)數(shù)據(jù)，包括兩方面：一是終端未受到入侵時(shí)的主體活動(dòng)信息；二是終端受到入侵時(shí)的主體活動(dòng)信息。然而，智能手機(jī)受到攻擊主要包含三種情況：第一種，較短時(shí)間內(nèi)受到大量垃圾信息，導(dǎo)致通信堵塞；第二種，短時(shí)間內(nèi)下載大量圖片、文件，并且受到大量信息，導(dǎo)致用戶的資費(fèi)和流量浪費(fèi)；第三，短時(shí)間內(nèi)內(nèi)存卡被惡意文件損害。用戶正常使用智能手機(jī)的依據(jù)包括以下幾方面的操作：接打電話、玩游戲、收發(fā)短信、文檔編輯、音樂(lè)和視頻播放、文件上傳與下載、正常使用網(wǎng)絡(luò)、軟件及時(shí)更新等相關(guān)手機(jī)操作。

3.2 分析與建模方式以及決策規(guī)則

這兩部分即為數(shù)據(jù)分析模塊，屬于入侵檢測(cè)系統(tǒng)的核心，其主要內(nèi)容是分析、研究收集到的數(shù)據(jù)，并且構(gòu)建正常樣本的特征輪廓，為作比較提供依據(jù)。設(shè)定標(biāo)準(zhǔn)閾值，以供與正常特征輪廓和測(cè)試樣本的特征輪廓的偏離值比較，如果偏離值小于閾值，則為正常，如果偏離值大于閾值，則為被入侵。

下面將通過(guò)C-SVC和V-SVC兩種方法進(jìn)行數(shù)據(jù)分析：

1）C-SVC方法運(yùn)用研究

指定訓(xùn)練本集如下：[zi=（xi，yi）ni=1]，[xi∈Rd（1≤i≤n）]，[yi∈±1]，其中C-SVC的原始問(wèn)題我們可以通過(guò)如下公式進(jìn)行表示：

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

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

其中與之相對(duì)應(yīng)的對(duì)偶問(wèn)題可進(jìn)行如下表示：

[mina12a′Qa-e′a]

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

從這里的相關(guān)公式以及數(shù)據(jù)，我們可知Q為[n×n]的矩形方陣，最后利用公式展示其決策函數(shù)：

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

2）v-SVC方法運(yùn)用研究

v-SVC是一種支持向量方法，包含參數(shù)v，其主要優(yōu)點(diǎn)及作用在于有效控制向量的數(shù)目。 指定訓(xùn)練本集如下：[Zi=（xi，yni=1i）]，[xi∈Rd（1≤i≤n）]，[yi∈±1]，其中v-SVC的原始問(wèn)題我們可以通過(guò)如下公式進(jìn)行表示：

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

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

在此過(guò)程中V屬于[0，1]，與之對(duì)應(yīng)的對(duì)偶問(wèn)題可進(jìn)行如下表示：

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

在此過(guò)程中，[Qij=yiyjk（xi，xj）]，其中核函數(shù)為[k（xi，xj）=?（xi）′?（xj）]，最后利用公式展示其決策函數(shù)：[sgn（w′?（x）+b）=sgni=0nyiaik（xi，x）+b]。

從以上相關(guān)公式、實(shí)驗(yàn)可得知，訓(xùn)練樣本數(shù)據(jù)數(shù)量十分龐大，數(shù)據(jù)間的冗余度較高，極大程度上增加了訓(xùn)練的時(shí)間，導(dǎo)致算法增加難度，致使其精準(zhǔn)度難以達(dá)到標(biāo)準(zhǔn)。針對(duì)此問(wèn)題，以目前的較大數(shù)據(jù)處理方式為依據(jù)，在進(jìn)行原始訓(xùn)練樣本壓縮時(shí)，引進(jìn)快速核密度估計(jì)，即FastKDE算法。在此算法的基礎(chǔ)上，研究樣本數(shù)據(jù)，提高樣本數(shù)量選擇的合理性，節(jié)約算法時(shí)間的前提下，降低算法的復(fù)雜程度，提高算法精準(zhǔn)度，增加準(zhǔn)確率。

4 通過(guò)快速核密度估計(jì)進(jìn)行在線增量學(xué)習(xí)算法框架構(gòu)建

4.1 快速核密度估計(jì)

在Freedman提出的相關(guān)理論基礎(chǔ)上，提出快速核密度估計(jì)定理，并通過(guò)相關(guān)實(shí)驗(yàn)進(jìn)行證明。

1）核密度估計(jì)：其是實(shí)用價(jià)值較高的非參數(shù)密度估計(jì)算法，使用領(lǐng)域較廣。KDE算法直接根據(jù)訓(xùn)練樣本獲取樣本特征的分布情況，根本不需對(duì)數(shù)據(jù)進(jìn)行先驗(yàn)假設(shè)，其主要用于對(duì)任意形狀的密度函數(shù)進(jìn)行估計(jì)。其算法如下：

數(shù)據(jù)集為S∈Rd，其容量為N，表達(dá)式為[P（x）=1Ni=1Nk（x，xi）]，[k（x，xi）]是核函數(shù)，其正定帶寬矩陣表示為[H=h]2I，原始數(shù)據(jù)中的抽樣容量為m的一個(gè)子集，由抽樣子集m數(shù)據(jù)中得到的KDE為[p（x）]，其具體表示為：

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

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

D[（p（x），p（x））]表示的是當(dāng)m小于n時(shí)，[p（x）]與[p（x）]之間存在的誤差，相較于傳統(tǒng)的較復(fù)雜的算法，快速核密度估計(jì)更加簡(jiǎn)單、方便，使其具有產(chǎn)生的必要性。

2）快速核密度估計(jì)：當(dāng)S∈Rd，容量為n是借助相關(guān)數(shù)據(jù)得到的[p（x）]，以及在[k（x，xi）]下的[H=h]2I的核函數(shù)，在此基礎(chǔ)上，假設(shè)m集得到的KDE表達(dá)式為[p（x）]。那么[p（x）]與[p（x）]之間的積分平方誤差可用以下公式進(jìn)行表達(dá)：[J=E（p（x）-p（x）2dx]，因此，J≤[4Ah+A2h2V+Bmhd+ABVmhd-1]。

在此，需要強(qiáng)調(diào)A、B、V與m和[h]沒(méi)有具體聯(lián)系，屬于常量，而J的大小與m和h存在一定的關(guān)系，與N也無(wú)關(guān)系。從公式我們可以發(fā)現(xiàn)，當(dāng)m數(shù)值足夠大時(shí)，[h]數(shù)值適中，[p（x）]與[p（x）]之間的值將處于無(wú)限接近的狀態(tài)。

在前面假設(shè)情況的前提下，Wang[p（x）]與[p（x）]之間尚的積分平分誤差公式如下：

[J=E（p（x）-p（x））2dx+λE1-（P（x））2dx]，在此公式下，我們知道J的上界與d、m、[h]、[λ]有關(guān)，而與N無(wú)關(guān)。

除此之外，深入研究探究數(shù)值之間的關(guān)系，從實(shí)驗(yàn)結(jié)果可以分析發(fā)現(xiàn)，m數(shù)值的大小，影響著KDE的速度和準(zhǔn)確性，并且該方法較簡(jiǎn)單，利用較少的數(shù)據(jù)，得出解決問(wèn)題的方法，保證實(shí)驗(yàn)效果。

4.2 在線增量學(xué)習(xí)分析研究

Ivor Wai-Hung Tsang等相關(guān)研究者提出核向量機(jī)算法，即CVM（Core Vector Machine），其是一種借助[（1+ε）]的方法實(shí)現(xiàn)MEB的快速求解。Di Wang等人在此基礎(chǔ)上進(jìn)行優(yōu)化、升級(jí)，提出了新的在線核心向量機(jī)學(xué)習(xí)方法，但因每次需要增加訓(xùn)練，導(dǎo)致計(jì)算較復(fù)雜，實(shí)用性不高。在線球向量機(jī)，即Online Ball Vector Machine（OBVM），由楊海峰等學(xué)者提出，其主要原理為：首先將二分類問(wèn)題進(jìn)行轉(zhuǎn)化，形成兩個(gè)單分類。其次，通過(guò)BVM算法進(jìn)行訓(xùn)練向量迭代。最后，對(duì)球心進(jìn)行求解，借助球心的垂直平分進(jìn)行分類。

以上幾種方法均可運(yùn)用于在線學(xué)習(xí)，但如果運(yùn)用于增量學(xué)習(xí)，其存在幾方面的問(wèn)題：第一，對(duì)所有的歷史數(shù)據(jù)進(jìn)行考慮，缺少遺忘機(jī)制的設(shè)置；第二，如果大量增加樣本，在進(jìn)行樣本保存時(shí)，計(jì)算具有較大的復(fù)雜性，易出現(xiàn)數(shù)據(jù)上的錯(cuò)誤。針對(duì)以上問(wèn)題，筆者將以遺忘機(jī)制為基礎(chǔ)，提出具有實(shí)際意義的增量學(xué)習(xí)FastKDE算法，即OFastKDE。

1）簡(jiǎn)要分析OFastKDE算法

相較于之前的諸多算法，OFastKDE算法能較好的適應(yīng)不斷增加的數(shù)據(jù)集，有利于克服龐大數(shù)據(jù)的計(jì)算問(wèn)題。其主要原理如下：首先，利用FastKDE評(píng)估訓(xùn)練樣本的規(guī)模，獲得有效樣本。其次，通過(guò)在線增量學(xué)習(xí)算法，借助SVM，剔除難以成為支持向量的樣本，縮減學(xué)習(xí)過(guò)程，提高效率，從而判斷入侵情況。其具體算法的步驟如下所示：

第一步：制定恰當(dāng)?shù)臄?shù)據(jù)集[S=x1，...，xN∈Rd]，標(biāo)簽集[Yi=-1，+1，1≤i≤N]，初始化下的[S+，S-]均為空。

第二步：利用FastKDE，對(duì)數(shù)據(jù)集S進(jìn)行有效壓縮，得到[S0=x1，...，xm]。

第三步：代入[S0=x1，...，xm]，通過(guò)SVM算法，達(dá)到解決QP的問(wèn)題，獲得訓(xùn)練集對(duì)應(yīng)的超平面。

第四步：將新的訓(xùn)練向量[Xq]映射至高維[?（Zq）]中，如果[?（Zq）]標(biāo)簽為正，則可進(jìn)行第六步或者第七步。

第五步：計(jì)算d，即[Xq]與超平面之間的距離，如果距離大于[1+ε]，那么[S+=S+??（zq}]。

第六步：計(jì)算d，即[Xq]與超平面之間的距離，如果距離大于[1+ε]，那么[S-=S-??（zq}]。

第七步：如果[S+，S-]的元素超過(guò)閾值，將淘汰[S0]中的非支持向量，再將[S+，S-]的元素移至[S0]，保持[S+，S-]處于置空狀態(tài)，然后轉(zhuǎn)向第三步。

2）時(shí)間復(fù)雜度的研究分析

在給定的數(shù)據(jù)集N中，利用抽樣獲得的m數(shù)據(jù)點(diǎn)，經(jīng)過(guò)OFastKDE，借助時(shí)間復(fù)雜度解決QP及相關(guān)問(wèn)題。值得注意的是，時(shí)間復(fù)雜度僅受m的影響，與N無(wú)關(guān)。如果m遠(yuǎn)小于N，則OFastKDE會(huì)顯示出其強(qiáng)大的競(jìng)爭(zhēng)力。

5 小結(jié)

本文以Android智能手機(jī)所收集的數(shù)據(jù)為依據(jù)，通過(guò)OFastKDE方法有效評(píng)估訓(xùn)練樣本的規(guī)模，獲得較合理的樣本，縮減計(jì)算時(shí)間，降低復(fù)雜程度。在在線增量學(xué)習(xí)算法的基礎(chǔ)上，借助支持向量機(jī)在小數(shù)據(jù)處理方面的優(yōu)勢(shì)，剔除非支持向量的相關(guān)數(shù)據(jù)，實(shí)現(xiàn)學(xué)習(xí)過(guò)程過(guò)程的加速，對(duì)入侵情況進(jìn)行有效檢測(cè)。從實(shí)驗(yàn)得出的相關(guān)數(shù)據(jù)分析，OFastKDE具有較高的擴(kuò)展性，具有良好的自我提升能力，有助于Android智能手機(jī)異常檢測(cè)功能的優(yōu)化，實(shí)現(xiàn)高效維護(hù)手機(jī)安全。同時(shí)在此實(shí)驗(yàn)過(guò)程中，因數(shù)據(jù)采集受到模擬攻擊的種類影響，導(dǎo)致實(shí)驗(yàn)結(jié)果存在偏差，因此，為更好的進(jìn)行這方面的研究，需要相關(guān)企業(yè)公司加大對(duì)其的資金設(shè)備投入，為研究工作提供優(yōu)質(zhì)環(huán)境，保障實(shí)驗(yàn)結(jié)果的正確性，增加企業(yè)競(jìng)爭(zhēng)力，從而促進(jìn)企業(yè)發(fā)展，推動(dòng)國(guó)家經(jīng)濟(jì)發(fā)展。

參考文獻(xiàn)：

[1] 葛唯唯， 劉淵. 面向Android系統(tǒng)安全分析的在線學(xué)習(xí)算法研究[J]. 計(jì)算機(jī)應(yīng)用研究， 2015（9）.

[2] 張鋼， 謝曉珊， 黃英， 等. 面向大數(shù)據(jù)流的半監(jiān)督在線多核學(xué)習(xí)算法[J]. 智能系統(tǒng)學(xué)報(bào)， 2014（3）.

[3] 李彬， 榮學(xué)文. 單隱層前向神經(jīng)網(wǎng)絡(luò)在線學(xué)習(xí)算法綜述與性能分析[C]// 東北大學(xué)、IEEE新加坡工業(yè)電子分會(huì)、IEEE控制系統(tǒng)協(xié)會(huì)哈爾濱分會(huì).第25屆中國(guó)控制與決策會(huì)議論文集. 東北大學(xué)、IEEE新加坡工業(yè)電子分會(huì)、IEEE控制系統(tǒng)協(xié)會(huì)哈爾濱分會(huì)， 2013.

[4] 王愛(ài)平， 萬(wàn)國(guó)偉， 程志全， 等. 支持在線學(xué)習(xí)的增量式極端隨機(jī)森林分類器[J]. 軟件學(xué)報(bào)， 2011（9）.

[5] 孫博良， 李國(guó)輝. 一種具有遺忘特性的在線學(xué)習(xí)算法框架[J]. 國(guó)防科技大學(xué)學(xué)報(bào)， 2014（4）.

[6] 林金星， 沈炯， 李益國(guó). 基于免疫原理的徑向基函數(shù)網(wǎng)絡(luò)在線學(xué)習(xí)算法及其在熱工過(guò)程大范圍工況建模中的應(yīng)用[J]. 中國(guó)電機(jī)工程學(xué)報(bào)， 2006，26（9）.

[7] 趙強(qiáng)利. 基于選擇性集成的在線機(jī)器學(xué)習(xí)關(guān)鍵技術(shù)研究[D]. 長(zhǎng)沙： 國(guó)防科學(xué)技術(shù)大學(xué)， 2010.

[8] 李志杰， 李元香， 王峰， 等. 面向大數(shù)據(jù)分析的在線學(xué)習(xí)算法綜述[J]. 計(jì)算機(jī)研究與發(fā)展， 2015（8）.