改進(jìn)粒子群算法應(yīng)用于Android惡意應(yīng)用檢測

霍 林，陸寅麗

廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，南寧530004

1 引言

Android 惡意應(yīng)用威脅著廣大Android 系統(tǒng)使用者的財(cái)產(chǎn)安全和隱私安全，如何快速有效地檢測惡意應(yīng)用成為防止此類威脅的重要手段。隨著機(jī)器學(xué)習(xí)的快速發(fā)展，越來越多的學(xué)者將機(jī)器學(xué)習(xí)算法應(yīng)用于Android惡意應(yīng)用檢測。文獻(xiàn)[1-2]提取Android應(yīng)用程序中的權(quán)限信息作為特征后使用機(jī)器學(xué)習(xí)分類器對其進(jìn)行分類。Cen 等人[3]提取Android 應(yīng)用程序的權(quán)限和API 為特征，并分別使用信息增益（IG）和卡方校驗(yàn)（CHI）進(jìn)行特征選擇后使用機(jī)器學(xué)習(xí)分類器進(jìn)行分類。

特征選擇作為機(jī)器學(xué)習(xí)的關(guān)鍵環(huán)節(jié)，通過去除冗余特征實(shí)現(xiàn)數(shù)據(jù)集精簡，提高機(jī)器學(xué)習(xí)分類器的分類效率和分類正確率。特征選擇方式可分為四種：Filter（過濾式）、Wrapper（包裹式）、Embedding（嵌入式）和混合式[4]。過濾式方法使用統(tǒng)計(jì)量先對數(shù)據(jù)集進(jìn)行特征選擇再訓(xùn)練分類器，特征選擇過程與后續(xù)分類器訓(xùn)練無關(guān)。包裹式直接將最終要使用的分類器的性能作為特征子集的評價(jià)指標(biāo)，需要更多的計(jì)算資源。嵌入式特征選擇將特征選擇過程與分類器訓(xùn)練過程融為一體；混合式是過濾式和包裹式的組合形式。

特征選擇的目的是尋找最適合分類的特征組合。如果一個(gè)數(shù)據(jù)集有N 個(gè)特征，那么將有2N種組合形式，要從這2N種組合中找到最優(yōu)組合是NP 難題[5]。故很多學(xué)者將目光轉(zhuǎn)向了智能算法，利用智能算法的尋優(yōu)能力進(jìn)行特征選擇。連續(xù)型和二進(jìn)制型的智能算法均可以用于進(jìn)行特征選擇，它們的主要區(qū)別是個(gè)體的表現(xiàn)形式不同。在二進(jìn)制智能算法中，個(gè)體是一個(gè)0-1向量，向量長度為特征集大小，1表示選擇該特征，0表示不選擇。連續(xù)型智能算法的搜索空間是實(shí)數(shù)空間，算法根據(jù)給定閾值選擇特征，只有某個(gè)特征的系數(shù)大于一定閾值時(shí)才選擇該特征。二進(jìn)制型智能算法是特征選擇較為常用的方式[6]。

粒子群算法（PSO）因其參數(shù)少，全局搜索能力強(qiáng)，受到了廣大學(xué)者的關(guān)注。例如，文獻(xiàn)[7]利用BPSO進(jìn)行特征選擇后使用樸素貝葉斯分類算法進(jìn)行Android惡意應(yīng)用檢測。許艷萍[8]針對細(xì)粒度、高維度的Android 應(yīng)用特征會(huì)降低機(jī)器學(xué)習(xí)分類器效率問題，提出了一種基于L2正則化和離散二進(jìn)制粒子群（BPSO）算法結(jié)合的聯(lián)合特征挖掘算法，提高了分類器的效率和性能。文獻(xiàn)[9]提取Android應(yīng)用程序中的權(quán)限信息為特征，并分別使用粒子群（PSO）、進(jìn)化計(jì)算（EC）和信息增益（IG）進(jìn)行特征選擇，最后發(fā)現(xiàn)使用粒子群算法進(jìn)行特征選擇的效果最好。

但是，和其他智能算法一樣，BPSO也存在早熟易收斂等缺點(diǎn)。為解決這個(gè)問題，文獻(xiàn)[10-11]引入了遺傳算法中的交叉變異操作；文獻(xiàn)[12]提出了一種鯰魚BPSO，如果全局最優(yōu)一直不改變就用鯰魚粒子替換最差粒子。還有的是將局部搜索算法和全局搜索算法結(jié)合起來，例如文獻(xiàn)[13]將黑洞算法作為局部搜索策略融入粒子群算法中。上述算法增加了計(jì)算的復(fù)雜度，收斂速度變慢。

本文通過研究不同的映射函數(shù)對于二進(jìn)制粒子群算法的影響，從映射函數(shù)層面對二進(jìn)制粒子群算法進(jìn)行改進(jìn)，在保證正確率的基礎(chǔ)上，提高了收斂速度，減少了計(jì)算量。

2 離散二進(jìn)制粒子群算法及其改進(jìn)

2.1 離散二進(jìn)制粒子群算法

粒子群算法（Particle Swarm Optimization，PSO）是Kennedy 和Eberhart 受鳥類覓食過程啟發(fā)，在1995 年提出的一種元啟發(fā)優(yōu)化算法[14]，并于1997年提出其二進(jìn)制版本（Binary Particle Swarm Optimization，BPSO）[15]。每個(gè)粒子具有位置和速度兩種屬性，分別表示為：Xi(t)=(xi1,xi2,…,xid,…,xin)和Vi(t)=(vi1,vi2,…,vid,…,vin)。其中，t 表示當(dāng)前迭代次數(shù)，i 表示第i 個(gè)粒子，d 表示第d 位，所以xid表示第i 個(gè)粒子在第d 位的位置值，vid表示第i 個(gè)粒子第d 位的速度。在BPSO中，粒子的位置只能取值為0或1。速度變化公式如下所示：

其中，w 為慣性權(quán)重，反映了粒子當(dāng)前速度更新時(shí)受上一次更新時(shí)速度的影響，當(dāng)慣性權(quán)重值較大，表示粒子有較強(qiáng)的全局搜索能力，當(dāng)慣性權(quán)重值較小，表示粒子具有較強(qiáng)的局部搜索能力。在粒子群算法中，權(quán)重的更新通常是一個(gè)遞減函數(shù)。c1和c2為學(xué)習(xí)因子，通常取值為2。rand()是[0，1]上滿足均勻分布的隨機(jī)數(shù)。Pbestid(t)是到第t 代為止第i 個(gè)粒子取得最優(yōu)值時(shí)在d位的取值，Gbestd是種群所有粒子迄今為止取得最優(yōu)值時(shí)在d 位的取值。

為保證粒子的位置只能取值為0或1，使用sigmoid函數(shù)將速度壓縮到[0，1]區(qū)間，表示粒子取1的概率，sigmoid函數(shù)如公式（2）所示。位置變化公式如公式（3）所示：

同時(shí)為了避免s( vid)太靠近1或0，還設(shè)置了一個(gè)速度最大值Vmax，令vid∈[- Vmax,Vmax]。

2.2 離散二進(jìn)制粒子群算法的改進(jìn)

離散二進(jìn)制粒子群算法的核心就是將連續(xù)搜索空間映射到離散搜索空間的映射函數(shù)[16-17]，也就是公式（3），文獻(xiàn)[17]引入了4種S型和4種V型映射函數(shù)，如表1所示。

表1 S型和V型映射函數(shù)

使用S型映射函數(shù)時(shí)xid的變化公式為公式（3）；使用V型映射函數(shù)時(shí)xid的變化公式為公式（4）：

在這里，(xid)-1表示對xid取反，即，若原來xid為0則將其變成1，或者相反操作。

定理S型映射函數(shù)對應(yīng)的二進(jìn)制PSO算法是全局搜索算法，V型映射函數(shù)對應(yīng)的二進(jìn)制PSO算法是局部搜索算法。

證明1 根據(jù)文獻(xiàn)[18]，速度為0時(shí)位變異率為0.5的映射函數(shù)對應(yīng)的二進(jìn)制粒子群算法全局搜索能力強(qiáng)，速度為0 時(shí)，位變異率為0 的映射函數(shù)對應(yīng)的二進(jìn)制粒子群算法局部搜索能力強(qiáng)。而位變異率公式為：

p(t)用來求第t 次迭代時(shí)第i 個(gè)粒子第d 位的位變異率。當(dāng)vid(t)=0時(shí)，S1～S4 均取值為0.5，p(t)為0.5；當(dāng)vid(t)=0時(shí)，V1～V4 均取值為0，p(t)為0。

故S 型映射函數(shù)對應(yīng)的二進(jìn)制PSO 算法是全局搜索算法，V型映射函數(shù)對應(yīng)的二進(jìn)制PSO算法是局部搜索算法。

證明2 為驗(yàn)證以上分析，使用具體實(shí)驗(yàn)進(jìn)行驗(yàn)證。

為觀測S 型和V 型映射函數(shù)的二進(jìn)制粒子群算法的速度變化和位變異率變化，利用二進(jìn)制粒子群算法求解基準(zhǔn)函數(shù)J.D.Schaffer函數(shù)，其函數(shù)形式如下：

實(shí)驗(yàn)在二維空間上利用二進(jìn)制粒子群算法計(jì)算函數(shù)的最小值。首先對搜索空間每一維編碼，每一維用1 000位二進(jìn)制表示，迭代次數(shù)為3 000，粒子個(gè)數(shù)為50，最大速度限制Vmax=9。每個(gè)粒子有二維，每一維區(qū)間[-5.12，5.12]被編碼成2 000 位。粒子的平均速度為每個(gè)粒子每一次迭代時(shí)在所有位置上的速度的平均。粒子的位變異率則是計(jì)算每個(gè)粒子的位改變數(shù)，再除以2 000位。經(jīng)仿真演示，S型和V型映射函數(shù)的BPSO的速度變化和位變異率變化如圖1和圖2所示。

圖1 S型和V型映射函數(shù)的平均速度的迭代變化

從圖1 可以看到，不管映射函數(shù)是怎樣的，粒子的平均速度都隨迭代次數(shù)增加趨向于0，從圖2可以看到，當(dāng)速度趨向于0 時(shí)，S 型映射函數(shù)的位變異率趨向于0.5，而V型的位變異率趨向于0。證畢。

圖2 S型和V型映射函數(shù)的位變異率的迭代變化

文獻(xiàn)[18]前期使用S 型映射函數(shù)進(jìn)行全局搜索，后期使用V 型映射函數(shù)進(jìn)行局部搜索。這就需要確定S型和V型的比例，而且只在最后進(jìn)行局部搜索。故本文提出了一種SVBPSO算法，在S型二進(jìn)制粒子群算法的搜索過程中，每隔一定迭代次數(shù)進(jìn)行一次局部搜索，這樣增強(qiáng)了局部搜索的頻率，充分利用了全局搜索和局部搜索的優(yōu)勢，有利于避免陷入局部最優(yōu)，提高了收斂效率和收斂精度。具體流程如下：

算法1 SVBPSO

1.初始化算法參數(shù)，包括種群規(guī)模、個(gè)體維度、最大迭代次數(shù)，迭代間隔等。

2.隨機(jī)初始化粒子種群，設(shè)置粒子的位置和速度，粒子的個(gè)體極值Pbest 和種群的全局極值Gbest。

3.求種群中每一個(gè)粒子的適應(yīng)度，如果適應(yīng)度優(yōu)于個(gè)體極值的適應(yīng)度，更新個(gè)體極值Pbest；如果適應(yīng)度優(yōu)于全局極值的適應(yīng)度，更新全局極值Gbest。

4.如果當(dāng)前迭代次數(shù)對迭代間隔取模為0，則使用V型映射函數(shù)和公式（4）更新粒子的位置和速度；否則使用S型映射函數(shù)和公式（3）更新粒子的位置和速度。

5.是否滿足停止條件，若是則輸出Gbest 及其適應(yīng)度；否則重復(fù)步驟3、4。

3 基于SVBPSO算法的Android混淆惡意應(yīng)用檢測

基于SVBPSO算法的Android混淆惡意應(yīng)用檢測主要由三部分組成：特征提取、特征向量化、特征選擇與分類器訓(xùn)練。

3.1 特征提取

特征提取部分提取Android應(yīng)用程序的三類信息作為特征：Permission、API 調(diào)用和source-sink 流。選擇這些信息作為特征的原因是：Android系統(tǒng)利用權(quán)限機(jī)制保護(hù)敏感API，應(yīng)用程序可根據(jù)自身需要申請permission，故分析應(yīng)用程序申請的權(quán)限可以簡單判斷它是否有惡意企圖；在Android系統(tǒng)上，一個(gè)應(yīng)用程序要實(shí)現(xiàn)某種功能需要通過系統(tǒng)提供的API來完成，不同的代碼范圍和API使用層級反映了對應(yīng)的代碼功能，能夠推測出模塊在運(yùn)行過程中具有的行為屬性和表現(xiàn)形式；此外，因?yàn)閼?yīng)用程序有可能使用了代碼混淆，而Flowdroid[19]的source-sink流表現(xiàn)了敏感信息source是流出外界所使用的API，所以在一定程度上能夠抵御代碼混淆。

這三類信息的具體提取過程為：

（1）使用“aapt dump permissions*.apk”命令獲取permission信息。

（2）使用backsmali 工具將.apk 文件逆向成一個(gè)個(gè)smali文件，再掃描文件中使用了“invoke-virtual”語句調(diào)用的API以獲取API信息。

（3）使用flowdroid 獲取source-sink 流，并用python將其格式化。

3.2 特征向量化

設(shè)樣本空間為X，包含n 個(gè)良性樣本Xbenign，m 個(gè)惡意樣本Xmalware，表示為：

對任意良性樣本xBi∈Xbenign，其permission集合為，API 集合為，source-sink 集合為，則該樣本的特征全集表示為：

同樣，對任意的惡意樣本xMi∈Xmalware，其特征全集為：

對于整個(gè)樣本空間X，樣本特征全集F 表示為所有良性樣本特征全集FB與所有惡意樣本特征全集F M的并集，即：

式中假設(shè)特征總數(shù)為t。因此，每一個(gè)樣本就是一個(gè)t維向量，若樣本中存在特征fi，則它的第i 位為1，否則為0，最后構(gòu)成一個(gè)(m+n)×t 的特征矩陣。

3.3 特征選擇與分類器訓(xùn)練

在前面的特征提取部分，為能夠描述應(yīng)用程序行為獲取了三類特征信息。但是即使一個(gè)很小的應(yīng)用程序，這三類特征數(shù)量總和也是非常龐大的，可達(dá)上萬個(gè)，這樣將使特征矩陣的維數(shù)非常高。高維特征矩陣會(huì)包含大量冗余信息，同時(shí)會(huì)引起維數(shù)災(zāi)難，造成計(jì)算困難，所以需要進(jìn)行特征選擇。

本文采用過濾式加包裹式的混合特征選擇形式。先使用L1正則化過濾一部分特征，再使用SVBPSO 包裹式訓(xùn)練分類器。使用L1正則化進(jìn)行特征選擇，具體來說就是使用L1正則化方法計(jì)算出每個(gè)特征的系數(shù)，一個(gè)特征的系數(shù)在一定程度上表現(xiàn)了該特征對于分類模型的重要性，故可以將特征系數(shù)進(jìn)行降序排列，然后選擇系數(shù)較大的特征形成特征子集。

使用SVBPSO 智能算法進(jìn)行特征選擇，就是將特征選擇作為一個(gè)優(yōu)化問題，關(guān)鍵在于如何定義適應(yīng)度函數(shù)。本文中，將SVBPSO 中的每一個(gè)粒子當(dāng)作一個(gè)特征集合，并使用機(jī)器學(xué)習(xí)分類器的分類正確率作為每一個(gè)粒子的適應(yīng)度，故SVBPSO 算法中的適應(yīng)度函數(shù)fitness()如下：

算法2 fitness()

輸入：粒子位置xi=(xi1,xi2,…,xit)，訓(xùn)練樣本的特征矩陣train_sample，訓(xùn)練樣本的標(biāo)簽train_label，測試樣本的特征矩陣test_sample，測試樣本的標(biāo)簽test_label。

輸出：粒子的適應(yīng)度。

1.查找xi中取值為1的維度indexes；

2.將train_sample 和test_sample 中對應(yīng)于indexes 的列抽取出來，形成訓(xùn)練樣本子矩陣sub_trainSample 和測試樣本子矩陣sub_testSample；

3.使用sub_trainSample 和train_label 構(gòu)建機(jī)器學(xué)習(xí)分類器；

4.用構(gòu)建好的機(jī)器學(xué)習(xí)分類器預(yù)測sub_testSample 的標(biāo)簽，記為predict_label；

5.比較predict_label和test_label的相似度，也就是機(jī)器學(xué)習(xí)分類器的分類器正確率，這個(gè)正確率就是粒子的適應(yīng)度。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 樣本選擇

實(shí)驗(yàn)所用的惡意樣本從virusshare 下載，良性樣本從Google Play Store和小米應(yīng)用市場下載。同時(shí)，為確保良性樣本的絕對干凈，將下載下來的良性樣本都上傳到virustotal 掃描，選擇無危險(xiǎn)的樣本為最終良性樣本。最終是良性樣本和惡意樣本各449個(gè)。

4.2 評價(jià)指標(biāo)

在Android 惡意應(yīng)用檢測中，常用的分類器評價(jià)指標(biāo)有正確率、召回率、精確率、F1、ROC和AUC。對于二分類問題，根據(jù)樣例的真實(shí)類別與機(jī)器學(xué)習(xí)分類器預(yù)測類別的組合，可以得到一個(gè)混淆矩陣，如表2所示。

表2 分類結(jié)果混淆矩陣

正確率Accuracy、精確率Precision、召回率Recall、F1 的計(jì)算公式分別如下：

從公式可以看出，正確率反映了分類器正確分類的能力；召回率反映了分類器正確判定正例占總體正例的比例關(guān)系；精確率反映了分類器判定的正例占真實(shí)正例的比例；F1 是精確率和召回率的調(diào)和均值，反映了分類器的綜合性能。

4.3 參數(shù)選擇

采用L1與SVBPSO 進(jìn)行混合特征選擇，其模型效果受多因素的影響。采用L1選取不同的數(shù)量的特征會(huì)有不同的效果。對于SVBPSO，其適應(yīng)度值是分類器的分類正確率，而不同的分類器對不同的分類問題具有不同的效果。還有，何時(shí)進(jìn)行局部探測也會(huì)對算法產(chǎn)生不同的影響，局部探測太頻繁就會(huì)退化成局部搜索算法，太稀疏則會(huì)變成全局搜索算法。另外，不同的映射函數(shù)具有不同的搜索能力，如何將它們進(jìn)行組合也是一個(gè)需要考慮的問題。故本節(jié)利用實(shí)驗(yàn)確定采用何種分類器，何時(shí)進(jìn)行局部探測，L1選擇多少的特征數(shù)量，以及SV最佳組合。

為消除隨機(jī)性，本文所有實(shí)驗(yàn)均采用十折交叉驗(yàn)證法進(jìn)行實(shí)驗(yàn)，將數(shù)據(jù)集分成10 份，每次輪流取其中1 份為測試集，其余9份為訓(xùn)練集。實(shí)驗(yàn)取10次實(shí)驗(yàn)的平均值為最終結(jié)果。算法基礎(chǔ)參數(shù)設(shè)置為：粒子個(gè)數(shù)10，最大迭代次數(shù)200。同時(shí)，為了簡單起見，本節(jié)實(shí)驗(yàn)僅考慮分類器正確率和分類器構(gòu)建時(shí)間。

4.3.1 分類器的確定

根據(jù)文獻(xiàn)[6]，使用智能算法進(jìn)行特征選擇時(shí)，用得最多的分類器是支持向量機(jī)（SVM）。但是還有其他機(jī)器學(xué)習(xí)分類器，例如決策樹分類器（DT）、樸素貝葉斯分類器（NB）、KNN分類器。為確定最合適的分類器，對上述4類分類器分別進(jìn)行了實(shí)驗(yàn)，各分類器的平均構(gòu)建時(shí)間和平均正確率如表3所示。

表3 不同分類器的構(gòu)建時(shí)間和正確率

從表3 可以看到，SVM 的平均正確率最高，同時(shí)其構(gòu)建時(shí)間也最長，而KNN的分類器構(gòu)建時(shí)間最短，但是其正確率稍遜于DT 和SVM。為平衡正確率和分類器構(gòu)建時(shí)間，本文選擇DT為分類器。

4.3.2 局部搜索間隔的確定

局部搜索是利用全局搜索的探索結(jié)果進(jìn)行局部開發(fā)，所以不同的迭代間隔會(huì)對算法效果造成不一樣的影響。為了確定最合適的迭代間隔，使用的S1 和V1 映射函數(shù)進(jìn)行了以下實(shí)驗(yàn)。實(shí)驗(yàn)中測試了從5 到50 的迭代間隔對算法效果的影響，結(jié)果如圖3所示。從圖中可以看到，當(dāng)?shù)g隔為35時(shí)，算法效果最好。

4.3.3 L1 選擇的數(shù)量

圖3 不同局部搜索間隔對算法效果的影響

為了減少分類器構(gòu)建的時(shí)間，也為了防止過擬合，本文使用L1進(jìn)行過濾式特征選擇，并以此為智能算法進(jìn)行包裹式特征選擇的起點(diǎn)，而智能算法的起點(diǎn)影響著算法的收斂速度和收斂精度。故使用L1選擇不同數(shù)量的特征對算法的影響是不一樣的。為了尋找最合適的數(shù)量，對L1取不同數(shù)量進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖4和圖5所示。

圖4 L1 選擇的特征數(shù)量對分類器正確率的影響

圖5 L1 選擇的特征數(shù)量對分類器構(gòu)建時(shí)間的影響

從圖中可以看到，在特征數(shù)量大于480 以后，分類器的正確率并沒有很大的提高，但是分類器的構(gòu)建時(shí)間一直隨著數(shù)量的增加而增加。故L1選擇的特征數(shù)量為480最合適。

4.3.4 SV組合的確定

不同的S 型和V 型映射函數(shù)對于最優(yōu)解的挖掘能力是不一樣的，它們的不同組合也會(huì)對算法效果造成不同的影響。為了尋找最合適的SV 組合，進(jìn)行了以下實(shí)驗(yàn)。迭代間隔使用上一節(jié)的實(shí)驗(yàn)結(jié)果，每隔35 次進(jìn)行一次局部探測。實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 不同SV組合對分類器正確率的影響

從圖中可以看到，當(dāng)S型映射函數(shù)為S4，V型映射函數(shù)為V3時(shí)，算法的正確率最高，故最佳的SV組合是S4V3。

4.4 算法比較

為證明算法的有效性，將本文提出的方法和文獻(xiàn)[8]和文獻(xiàn)[9]中的方法進(jìn)行了比較。文獻(xiàn)[9]中僅使用了粒子群算法進(jìn)行特征選擇，文獻(xiàn)[8]中使用L2進(jìn)行過濾式特征選擇后再使用二進(jìn)制粒子群算法進(jìn)行包裹式特征選擇。實(shí)驗(yàn)結(jié)果如表4所示。

表4 不同算法實(shí)驗(yàn)結(jié)果比較 %

從表4 可以看到，使用本文算法進(jìn)行Android 惡意應(yīng)用檢測具有較高的正確率、精確率、召回率和F1 值。

5 結(jié)束語

本文從二進(jìn)制粒子群算法的映射函數(shù)出發(fā)，觀測不同的映射函數(shù)的速度和位變異率的變化趨勢，提出了一種改進(jìn)的粒子群算法SVBPSO。該算法利用S 型映射函數(shù)的全局搜索能力尋找最優(yōu)解的大致位置，并在迭代過程中，間隔性地使用V型映射函數(shù)進(jìn)行局部搜索。最后，利用SVBPSO進(jìn)行Android惡意應(yīng)用檢測，經(jīng)過實(shí)驗(yàn)證明使用SVBPSO 進(jìn)行特征選擇能高效準(zhǔn)確地檢測出Android惡意應(yīng)用。