霍 林，陸寅麗

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

1 引言

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

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

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

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

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

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

2 離散二進制粒子群算法及其改進

2.1 離散二進制粒子群算法

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

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

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

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

2.2 離散二進制粒子群算法的改進

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

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

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

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

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

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

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

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

證明2 為驗證以上分析，使用具體實驗進行驗證。

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

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

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

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

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

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

算法1 SVBPSO

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

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

3.求種群中每一個粒子的適應(yīng)度，如果適應(yīng)度優(yōu)于個體極值的適應(yīng)度，更新個體極值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)限機制保護敏感API，應(yīng)用程序可根據(jù)自身需要申請permission，故分析應(yīng)用程序申請的權(quán)限可以簡單判斷它是否有惡意企圖；在Android系統(tǒng)上，一個應(yīng)用程序要實現(xiàn)某種功能需要通過系統(tǒng)提供的API來完成，不同的代碼范圍和API使用層級反映了對應(yīng)的代碼功能，能夠推測出模塊在運行過程中具有的行為屬性和表現(xiàn)形式；此外，因為應(yīng)用程序有可能使用了代碼混淆，而Flowdroid[19]的source-sink流表現(xiàn)了敏感信息source是流出外界所使用的API，所以在一定程度上能夠抵御代碼混淆。

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

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

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

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

3.2 特征向量化

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

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

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

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

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

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

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

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

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

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

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

4 實驗與結(jié)果分析

4.1 樣本選擇

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

4.2 評價指標(biāo)

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

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

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

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

4.3 參數(shù)選擇

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

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

4.3.1 分類器的確定

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

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

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

4.3.2 局部搜索間隔的確定

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

4.3.3 L1 選擇的數(shù)量

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

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

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

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

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

4.3.4 SV組合的確定

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

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

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

4.4 算法比較

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

表4 不同算法實驗結(jié)果比較 %

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

5 結(jié)束語

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