基于優(yōu)化K-means的Android系統(tǒng)惡意軟件檢測的研究與設(shè)計(jì)*

趙中軍，曾涌泉，王運(yùn)兵

（中國電子科技集團(tuán)公司第三十研究所，四川 成都 610041）

0 引 言

隨著科技的發(fā)展和移動互聯(lián)網(wǎng)的普及，各種便攜式智能移動終端設(shè)備和移動應(yīng)用已經(jīng)成為人們身體的延伸，并極大地改變著人們的生活方式。Android系統(tǒng)因?yàn)槠溟_放性、開源性及其相對簡單的檢查機(jī)制[1]，極大地方便了應(yīng)用軟件的自由開發(fā)和發(fā)布，使其成為便攜式智能移動終端的主流操作系統(tǒng)。但是，也正是這些特點(diǎn)，極大地方便了各種病毒、木馬、流氓軟件等惡意程序的滋生[2]，直接或者間接造成用戶的隱私泄露或者經(jīng)濟(jì)損失，嚴(yán)重?fù)p害用戶的利益。因此，對入侵Android系統(tǒng)的惡意軟件進(jìn)行檢測尤為重要和迫切。

1 系統(tǒng)總體設(shè)計(jì)框架

惡意軟件的檢測主要有靜態(tài)檢測和動態(tài)檢測兩種方法[3]。動態(tài)檢測方法一般是利用沙箱技術(shù)和后臺監(jiān)聽機(jī)制來監(jiān)控并記錄程序所有行為，對行為數(shù)據(jù)建模并與已有惡意代碼模式進(jìn)行匹配實(shí)現(xiàn)檢測，從而判斷是否是惡意軟件。靜態(tài)檢測方法是指在不運(yùn)行軟件的前提下，對待測軟件所包含的源碼以及其他文件進(jìn)行分析，從中提取特征數(shù)據(jù)來構(gòu)建檢測模型?；贏ndroid平臺的惡意軟件靜態(tài)檢測技術(shù)，根據(jù)特征類型目前可分為兩類：基于語法特征分析和基于語義特征分析。語法特征分析是指以單獨(dú)或多個特征（簽名、Action和Permission三種）建立模型；語義特征分析是指將軟件解壓反編譯后對源碼進(jìn)行分析[4]，構(gòu)建對應(yīng)的控制流圖和數(shù)據(jù)流圖等。本文使用靜態(tài)檢測方法提取應(yīng)用軟件特征。

通過靜態(tài)或動態(tài)方法獲取程序的特征數(shù)據(jù)后，模型的建立和匹配可以使用聚類方法、分類方法和相似度計(jì)算，以區(qū)分正常程序和惡意程序。使用聚類算法可識別惡意程序具體屬于哪一類家族，分類算法和相似度計(jì)算往往只給出程序是否是惡意程序的答案，無法將其歸類。K_means聚類算法[5]因其理論簡單易懂、計(jì)算速度快等優(yōu)點(diǎn)而被廣泛引用。本文重點(diǎn)研究基于K_means聚類算法的惡意軟件檢測。

基于以上分析，設(shè)計(jì)的整個惡意軟件檢測系統(tǒng)如圖1所示。系統(tǒng)主要由特征提取過程和特征聚類過程兩部分組成。特征提取過程是指以Apk文件為輸入，經(jīng)過解壓獲得AndroidManifest和.dex和文件再將其反編譯。特征聚類過程則使用K-means算法進(jìn)行聚類劃分。

本文在完成特征提取的基礎(chǔ)上，重點(diǎn)實(shí)現(xiàn)對應(yīng)用軟件的聚類過程，能夠快速準(zhǔn)確地檢測出惡意軟件。

2 傳統(tǒng)的K-means聚類檢測算法

2.1 K-means算法的基本原理及實(shí)現(xiàn)流程

K-means算法的基本原理[6]如下。首先指定需要劃分的簇數(shù)為K，并且需要從含有n個數(shù)據(jù)對象的數(shù)據(jù)集中隨機(jī)選取K個數(shù)據(jù)對象作為初始聚類中心；其次，一般釆用距離特征來計(jì)算其余各個數(shù)據(jù)對象到所選取的K個初始聚類中心的距離，根據(jù)最近鄰原則，將數(shù)據(jù)對象逐個劃分到距離它最近的中心所在的簇中形成新的簇；再次，分別計(jì)算新生成的簇中數(shù)據(jù)對象的均值，將此均值作為各個簇新的聚類中心；最后，比較新生成的聚類中心與上次的聚類中心，如果沒有發(fā)生變化或者變化滿足一定的閾值，說明此時所采用的聚類準(zhǔn)則函數(shù)收斂，算法終止，否則要根據(jù)新的聚類中心對所有數(shù)據(jù)對象重新進(jìn)行劃分，直到滿足算法的收斂條件才終止。

圖1 系統(tǒng)總體設(shè)計(jì)

K-均值聚類算法的基本步驟描述如下：

輸入?yún)?shù)：含有n個數(shù)據(jù)對象的數(shù)據(jù)集X，所需要分簇的數(shù)目K。

輸出參數(shù)：K個分類數(shù)據(jù)。

步驟1：從含有n個數(shù)據(jù)對象的數(shù)據(jù)集X中隨機(jī)選擇K個數(shù)據(jù)對象作為初始聚類中心；

步驟2：分別計(jì)算數(shù)據(jù)集中各數(shù)據(jù)對象到各個聚類中心的距離（本文采用歐氏距離），根據(jù)最近鄰原則，將數(shù)據(jù)對象逐個劃分到距其最近的聚類中心所在的簇中，計(jì)算聚類準(zhǔn)則函數(shù)E的值。本文采用誤差平方和準(zhǔn)則函數(shù)作為聚類準(zhǔn)則函數(shù)，表示如下：

其中，xi是簇Ci的數(shù)據(jù)對象，ci表示簇Ci的均值。

步驟3：分別計(jì)算各個簇中所有數(shù)據(jù)對象的均值作為各個簇的新的中心，以新的聚類中心來計(jì)算誤差平方和準(zhǔn)則函數(shù)E的值，更新聚類中心；

步驟4：將步驟3計(jì)算得到的E值和上次計(jì)算得到的E值進(jìn)行比較，如果二者的差值小于預(yù)先設(shè)定的閾值，即聚類準(zhǔn)則函數(shù)收斂，轉(zhuǎn)下一個步驟，否則轉(zhuǎn)到步驟2。

步驟5：輸出滿足條件的聚類結(jié)果。

2.2 K-means算法的缺點(diǎn)

K-means聚類算法的缺點(diǎn)[7]主要體現(xiàn)在以下幾個方面。

（1）算法中聚類個數(shù)K需要事先指定。實(shí)際應(yīng)用中，需要分類的個數(shù)K值是不確定的，并不知道數(shù)據(jù)集被分為多少類最合適，所指定的K值很可能會大于或小于實(shí)際需要聚類的個數(shù)，而K值的不準(zhǔn)確會直接導(dǎo)致分類結(jié)果的不正確。因此，聚類個數(shù)K值的確定是K-means聚類算法面對的一個難題。

（2）算法對初始化聚類中心的選取依賴性極大，且算法容易陷入局部極小解。由K-means算法的基本原理可知，除了需要指定聚類數(shù)K值外，還需要隨機(jī)選取K個點(diǎn)作為初始聚類中心，再通過不斷的迭代、重定位等尋找最優(yōu)的聚類中心，直到算法收斂。因此，隨機(jī)選取的初始聚類中心可能會導(dǎo)致最終聚類效果的不穩(wěn)定。此外，K-means算法采用的聚類準(zhǔn)則函數(shù)通常是誤差平方和準(zhǔn)則函數(shù)。它是一個非凸函數(shù)，存在很多個局部極小值點(diǎn)，因此最終收斂函數(shù)可能會陷入局部極小值點(diǎn)而不是全局最小值點(diǎn)，導(dǎo)致聚類效果不佳。

（3）算法對噪聲點(diǎn)和孤立點(diǎn)非常敏感。在獲得新的聚類中心時，往往是計(jì)算簇中數(shù)據(jù)對象的平均值。對遠(yuǎn)離密集區(qū)域的噪聲點(diǎn)來說，這將會導(dǎo)致新的聚類中心偏離真正的數(shù)據(jù)密集區(qū)。所以，算法對噪聲點(diǎn)和孤立點(diǎn)非常敏感。

（4）聚類算法一般只能發(fā)現(xiàn)球狀簇。算法一般通過計(jì)算數(shù)據(jù)對象的歐式距離并采用誤差平方和準(zhǔn)則函數(shù)來作為聚類的判斷。當(dāng)簇之間特征差別明顯且分布相對集中時，效果較好。但是，如果特征差別不大且分布相對分散時，聚類可能會出現(xiàn)將本來屬于同一簇中的數(shù)據(jù)分割為多個簇的現(xiàn)象。

（5）對于大數(shù)據(jù)量，算法開銷非常大。從算法流程可以看出，該算法需要不斷調(diào)整數(shù)據(jù)分類，并計(jì)算調(diào)整后新的聚類中心。因此，當(dāng)數(shù)據(jù)集中數(shù)據(jù)對象數(shù)量非常大時，需要的迭代次數(shù)和計(jì)算量將非常大。

本文主要針對（1）和（2）進(jìn)行改進(jìn)。

3 優(yōu)化的K-means聚類檢測算法設(shè)計(jì)

3.1 聚類數(shù)K的改進(jìn)方案

K-means聚類算法是通過計(jì)算給定數(shù)據(jù)集合中各個數(shù)據(jù)對象到各自聚類中心的距離來分配數(shù)據(jù)對象。如果設(shè)置的聚類數(shù)目超過了最佳聚類個數(shù)，最后的聚類結(jié)果將使原本屬于同一個聚類的數(shù)據(jù)對象被劃分為若干個小的聚類，而這些小的聚類之間的類間距離也將相對接近。因此，可以通過計(jì)算類間距離來判斷兩個小的聚類是否應(yīng)該屬于同一個聚類[8]。

該改進(jìn)算法的基本思想是采用基于類間距離和類內(nèi)距離的方法，在給定K值的一個范圍(2≤K≤Kmax)內(nèi)找到滿足條件的最佳聚類個數(shù)K值。首先，需要預(yù)先指定一個K的初值，通過數(shù)據(jù)集合X運(yùn)行K-means聚類算法即可得到K個聚類，通過計(jì)算D(mi, mj)、d(Xi, mj)、int(Xi, Xj)和ave的值判斷兩兩聚類是否屬于同一個類，最后輸出最佳聚類個數(shù)Kopt。下面詳細(xì)介紹各個參數(shù)所代表的意義。

對于數(shù)據(jù)集X，其K個聚類子集定義為X1,X2,…,XK；各子集中數(shù)據(jù)的個數(shù)分別為n1,n2,…,nK；各子集的聚類中心點(diǎn)為m1,m2,…,mK。D(mi, mj)表示Xi、Xj兩個子集的聚類中心點(diǎn)mi、mj之間的距離；d(Xi, mj)表示子集Xi中數(shù)據(jù)到另外一個子集Xj中心點(diǎn)的最短距離；int(Xi, Xj)為兩個聚類子集之間的類間距離，即可以表示為：

ave表示每個簇中數(shù)據(jù)對象之間的平均相鄰距離，可用最小生成樹的辦法求得，即首先求出每個數(shù)據(jù)對象與其他數(shù)據(jù)的兩兩距離，然后求出距離每個數(shù)據(jù)對象的最小距離，將所有對象的最小距離求和后進(jìn)一步得出平均相鄰距離。

對于Kmax的值的確定，目前還沒有明確的理論指導(dǎo)。對于含有n個數(shù)據(jù)對象的數(shù)據(jù)集合來說，通常多數(shù)學(xué)者使用的經(jīng)驗(yàn)規(guī)則為Kmax≤。

對于優(yōu)化K值的算法的具體實(shí)現(xiàn)流程如下：

（1）給出K值的初始聚類數(shù)為Kmax；

（2）完成Kmax聚類數(shù)下的聚類分簇；

（3）計(jì)算兩聚類子集間的中心距離D(mi, mj)、某類到另一個類中心的最近距離d(Xi, mj)、兩個子集之間的類間距離int(Xi, Xj)和每個類中的數(shù)據(jù)對象的平均相鄰距離ave的值；

（4）根據(jù)式（3）判斷兩兩聚類是否屬于同一聚類，如果滿足條件，則屬于同一聚類，Kmax-1；否則，不成立。

（5）輸出優(yōu)化的最佳聚類個數(shù)Kopt。

3.2 初始化中心點(diǎn)的改進(jìn)方案

由于傳統(tǒng)的初始化聚類中心點(diǎn)是隨機(jī)選取的，因此不可避免可能會出現(xiàn)所選擇的中心點(diǎn)挨的過近，導(dǎo)致聚類結(jié)果不穩(wěn)定[9]。本文主要是針對此問題進(jìn)行優(yōu)化，具體實(shí)現(xiàn)流程如下：

（1）從含有n個數(shù)據(jù)對象的數(shù)據(jù)集X中隨機(jī)的選取K個值組成一個集合，重復(fù)操作M次，得到M個集合，分別表示為：{a11,a12,…,a1K}，{a21,a22,…,a2K}…{aM1,aM2,…,aMK}；

（2）分別求出每個集合中K個數(shù)據(jù)對象中兩兩之間的距離的最小值，即min1(d(ai,aj))，min2(d(ai,aj))…minM(d(ai,aj))；

（3）找出上述最小值中的最大值所對應(yīng)的集合，即將這K個數(shù)據(jù)作為初始化聚類中心；

（4）按照傳統(tǒng)的K-means聚類算法進(jìn)行后面聚類分析。

4 優(yōu)化K-means算法的整體設(shè)計(jì)方案及仿真

4.1 設(shè)計(jì)方案及流程

將設(shè)計(jì)的優(yōu)化聚類數(shù)K和改進(jìn)的初始化聚類中心方案相結(jié)合，得到本文設(shè)計(jì)的優(yōu)化K-means算法的方案，具體實(shí)現(xiàn)流程如下：

（1）從含有n個數(shù)據(jù)對象的數(shù)據(jù)集X中隨機(jī)的選取K個值組成一個集合，重復(fù)操作M次，得到M個集合，分別表示為{a11,a12,…,a1K}，{a21,a22,…,a2K}…{aM1,aM2,…,aMK}；

（2）分別求出每個集合中K個數(shù)據(jù)對象中兩兩之間的距離的最小值，即min1(d(ai,aj))，min2(d(ai,aj))…minM(d(ai,aj))；

（3）找出上述最小值中的最大值所對應(yīng)的集合，即將這K個數(shù)據(jù)作為初始化聚類中心；

（4）給出K值的初始聚類數(shù)為Kmax，初始化聚類中心選擇步驟（3）所選取的結(jié)果；

（5）根據(jù)最近鄰原則，將數(shù)據(jù)對象逐個劃分到距其最近的聚類中心所在的簇中，根據(jù)式（1）計(jì)算聚類準(zhǔn)則函數(shù)E的值；

（6）分別計(jì)算各個簇中所有數(shù)據(jù)對象的均值作為各個簇的新的中心，以新的聚類中心來計(jì)算誤差平方和準(zhǔn)則函數(shù)E的值，更新聚類中心；

（7）將兩次得到的E值進(jìn)行比較，如果二者的差值小于預(yù)先設(shè)定的閾值，即聚類準(zhǔn)則函數(shù)收斂，則轉(zhuǎn)下一個步驟，否則轉(zhuǎn)到步驟（5）；

（8）輸出滿足條件的聚類結(jié)果；

（9）計(jì)算兩聚類子集間的中心距離D(mi, mj)、某類到另一個類中心的最近距離d(Xi, mj)、兩個子集之間的類間距離int(Xi, Xj)和每個類中的數(shù)據(jù)對象的平均相鄰距離ave的值；

（10）根據(jù)式（3）判斷兩兩聚類是否屬于同一聚類，如果滿足條件，則屬于同一聚類，Kmax-1，否則不成立。

（11）判斷連續(xù)兩次聚類數(shù)不發(fā)生變化，若不變化，則輸出最佳聚類個數(shù)Kopt及相應(yīng)的聚類結(jié)果；若變化，則繼續(xù)迭代，直到不發(fā)生變化為止。

實(shí)現(xiàn)的流程圖如圖2所示。

圖2 優(yōu)化K_Means算法實(shí)現(xiàn)流程

4.2 聚類算法仿真及分析

4.2.1 聚類算法仿真

為了驗(yàn)證優(yōu)化的聚類算法的準(zhǔn)確性，分別對特征明顯的兩組數(shù)據(jù)和特征差異性小的兩組數(shù)據(jù)進(jìn)行仿真。仿真的數(shù)據(jù)集為50，其中“o”表示聚類中心。

圖3是對具有明顯特征差異的兩組數(shù)據(jù)進(jìn)行的仿真，初始聚類數(shù)K為7，第二次迭代后聚類數(shù)為4?？梢?，經(jīng)過第三次迭代輸出了最終的聚類結(jié)果2，將數(shù)據(jù)準(zhǔn)確分成2組。

圖4是對特征差異性相對比較小的兩組數(shù)據(jù)進(jìn)行的仿真，初始聚類數(shù)K為7，第二次迭代后聚類數(shù)為3?？梢姡?jīng)過第三次迭代輸出了最終的聚類結(jié)果2，將數(shù)據(jù)準(zhǔn)確分成2組。

圖3 特征明顯的2組數(shù)據(jù)的仿真

圖4 特征差異小的2組數(shù)據(jù)的仿真

4.2.2 聚類效果評估

由于聚類數(shù)K的不確定性，當(dāng)使用K-means聚類算法對數(shù)據(jù)對象集合進(jìn)行分類的過程中，可能會分出不同聚類數(shù)的聚類結(jié)果。就像前面仿真中多次迭代出現(xiàn)的不同結(jié)果，最終哪次的迭代結(jié)果是最佳的分類效果，這個問題屬于聚類有效性問題。聚類有效性是指評價聚類結(jié)果的質(zhì)量并確定最適合特定數(shù)據(jù)集的劃分。通常采用聚類有效性指標(biāo)來評價聚類算法產(chǎn)生的哪個聚類結(jié)果是最優(yōu)的，并將最優(yōu)的聚類結(jié)果對應(yīng)的聚類數(shù)目作為最佳聚類數(shù)。目前，常用的檢驗(yàn)聚類有效性的指標(biāo)有CH指標(biāo)、Wint指標(biāo)、IGP指標(biāo)和Sil指標(biāo)等。Sil指標(biāo)具有簡單、易用以及良好的評價能力，因此被廣泛使用。Sil指標(biāo)反映了聚類結(jié)構(gòu)的類內(nèi)緊密性和類間分離性，既可用于評價聚類質(zhì)量，也可用于估計(jì)最佳聚類數(shù)。

Sil指標(biāo)的定義為：

其中，a(i)表示數(shù)據(jù)對象i與類內(nèi)所有其他樣本的平均距離；b(i)表示數(shù)據(jù)對象i與到其他每個類中樣本平均距離的最小值。

從式（4）可以看出，Sil的值在[-1,1]范圍內(nèi)變動。數(shù)據(jù)集中，所有樣本Sil值的平均值越大，則表示聚類效果越好，其最大值對應(yīng)的聚類數(shù)即是最佳聚類數(shù)。

上述仿真中，特征明顯的2組數(shù)據(jù)的Sil值為0.743 740 566 544 095，特征差異性小的兩組數(shù)據(jù)的Sil值為0.617 091 006 175 474。從仿真結(jié)果可以看出，在不用指定特定聚類數(shù)K的情況下，經(jīng)過多次迭代，均可以準(zhǔn)確得到聚類結(jié)果，驗(yàn)證了優(yōu)化的聚類數(shù)和初始中心點(diǎn)方案的正確性和可行性。

5 系統(tǒng)實(shí)驗(yàn)分析

為了驗(yàn)證所設(shè)計(jì)系統(tǒng)的可行性，將設(shè)計(jì)的改進(jìn)算法與傳統(tǒng)算法進(jìn)行對比測試，樣例從國內(nèi)的第三方Android市場上下載，共2 000個惡意軟件，3 000個正常軟件，測試的對比結(jié)果如表1所示。

表1 算法測試對比

從測試結(jié)果可以看出，優(yōu)化后的K-means算法大大提高了對惡意軟件檢測的正確率，驗(yàn)證了所設(shè)計(jì)系統(tǒng)的有效性。

6 結(jié) 語

本文在采用靜態(tài)檢測方法提取了Android應(yīng)用程序的特征參數(shù)后，重點(diǎn)對K-means聚類算法進(jìn)行優(yōu)化，包括對聚類數(shù)K的確定和初始化中心點(diǎn)。經(jīng)仿真驗(yàn)證，優(yōu)化算法可以快速、準(zhǔn)確地檢測出惡意軟件，對惡意軟件有良好的識別能力，具有重要的理論和應(yīng)用價值。