基于譜聚類的重打包應(yīng)用檢測

蔡昆杰,李呂牧之,李帥,常錦才

(華北理工大學(xué) 理學(xué)院,河北 唐山 063210)

Android操作系統(tǒng)已經(jīng)是當(dāng)今世界上最受歡迎、使用最廣泛的移動(dòng)操作系統(tǒng),Android智能手機(jī)占全球智能手機(jī)中的一半以上。與此同時(shí),Android應(yīng)用(Applications,APP)的數(shù)量也在快速增長。在谷歌Android市場,Android應(yīng)用程序從2018年9月的280萬個(gè)激增至2021第一季度的340萬個(gè)[1]。此外,根據(jù)卡巴斯基的安全惡意軟件威脅報(bào)告[2],2020年第三季度,檢測到大約35萬個(gè)新的惡意應(yīng)用。根據(jù)一項(xiàng)研究[3],Android惡意應(yīng)用占所有智能手機(jī)威脅的98%,其中99%的惡意應(yīng)用來自許多第三方市場。因此,Android應(yīng)用的檢測必須得到加強(qiáng),特別是第三方應(yīng)用市場。

Android系統(tǒng)是一個(gè)開源系統(tǒng),因此,與其他操作系統(tǒng)相比,Android操作系統(tǒng)更容易受到惡意軟件攻擊。Android操作系統(tǒng)更容易受到惡意攻擊的2個(gè)主要原因是:其廣泛性和漏洞的數(shù)量的增加。其廣泛性是指Android操作系統(tǒng)和Android應(yīng)用廣泛使用在日常生活中的各個(gè)方面,包括但不限于銀行和社交網(wǎng)絡(luò)在內(nèi)的各種重要內(nèi)容,涉及大量敏感和私人數(shù)據(jù)。因此,Android操作系統(tǒng)和應(yīng)用程序已經(jīng)成為剽竊者非常有吸引力的目標(biāo),目的是從應(yīng)用程序中竊取隱私和敏感信息。另一方面,Android中的漏洞數(shù)量不斷增加是其易受攻擊的另一個(gè)原因,Android操作系統(tǒng)中的漏洞數(shù)量過去幾年急劇增加[4],漏洞的增加可能會(huì)導(dǎo)致剽竊者更容易盜取用戶的信息和更頻繁地攻擊Android系統(tǒng)。

在Android操作系統(tǒng)中,敏感信息(包括賬號、密碼、銀行卡信息、個(gè)人照片和其他私人信息)存儲(chǔ)在Android移動(dòng)設(shè)備中,這使得剽竊者可以利用Android操作系統(tǒng)的漏洞獲取用戶的隱私。剽竊者使用多種方法來獲取這些敏感信息,而重打包應(yīng)用是最常用方法之一。因?yàn)锳ndroid市場上的大多數(shù)應(yīng)用都可以免費(fèi)下載,這使得剽竊者很容易獲得想要的應(yīng)用。在重新打包應(yīng)用的過程中,剽竊者會(huì)在重新打包的應(yīng)用程序中留下病毒或后門[5],以此獲取用戶的敏感信息。此外,隨著Java逆向工程的發(fā)展,如果在發(fā)布應(yīng)用前開發(fā)人員不注意反逆向,或者他們使用的反逆向工程技術(shù)落后,剽竊者可以很容易地對應(yīng)用進(jìn)行反編譯,然后對其進(jìn)行修改,例如插入病毒和廣告,然后重新打包并發(fā)布應(yīng)用程序。重打包應(yīng)用就是未經(jīng)開發(fā)人員同意就被修改,然后重新發(fā)布在應(yīng)用市場上的應(yīng)用。

由于重打包應(yīng)用的成本低、難度小,它們在第三方應(yīng)用市場上的數(shù)量逐漸增多。因此,加大重打包應(yīng)用的檢測力度是非常必要的。根據(jù)最近的一項(xiàng)研究[6],作者從6個(gè)第三方Android市場中抽取了22 906款應(yīng)用,發(fā)現(xiàn)其中5%至13%是重打包應(yīng)用。此外,通過對這些重打包應(yīng)用的人工分析,發(fā)現(xiàn)這些應(yīng)用主要是通過插入廣告、植入后門和病毒來牟利。根據(jù)另一項(xiàng)研究[7],在分析的1 260個(gè)惡意軟件樣本中,作者發(fā)現(xiàn)其中1 083個(gè)是帶有惡意病毒的合法應(yīng)用的重打包版本。這一結(jié)果表明,重打包應(yīng)用是惡意軟件傳播的有益工具,對重打包應(yīng)用的檢測和預(yù)防具有重要的研究價(jià)值和現(xiàn)實(shí)意義。首先,檢測重打包的應(yīng)用在一定程度上也等同于檢測惡意應(yīng)用,這對維護(hù)網(wǎng)絡(luò)安全具有重要意義。其次,檢測重打包的應(yīng)用可以維護(hù)開發(fā)者的版權(quán),這對于維護(hù)Android應(yīng)用程序市場的公平性非常重要。最后,如果不重視重打包應(yīng)用,不對重包裝應(yīng)用進(jìn)行打擊懲罰,將會(huì)有越來越多的重打包應(yīng)用在Android應(yīng)用程序市場上發(fā)布,這將不利于Android應(yīng)用程序的開發(fā)或創(chuàng)新。

1方法

重新包裝的應(yīng)用程序在外觀和功能上與原始應(yīng)用程序非常相似[8],用戶很難辨別。因此,檢測重打包應(yīng)用的工作應(yīng)該由特殊的檢測工具或算法來完成?，F(xiàn)有的重打包檢測算法根據(jù)檢測過程中是否需要安裝應(yīng)用分為動(dòng)態(tài)檢測[9]和靜態(tài)檢測[10]。也就是說,在不運(yùn)行Android的情況下對應(yīng)用進(jìn)行分析和檢測的算法稱為靜態(tài)檢測算法,其它算法稱為動(dòng)態(tài)檢測。動(dòng)態(tài)檢測算法在分析重打包應(yīng)用的具體行為和檢測準(zhǔn)確率方面比靜態(tài)檢測算法具有優(yōu)勢[11],而靜態(tài)檢測在檢測速度具有較大的優(yōu)勢,該項(xiàng)研究討論的算法主要是靜態(tài)檢測算法。

在檢測重打包的應(yīng)用時(shí),靜態(tài)檢測算法是廣泛使用的算法。靜態(tài)檢測算法主要是在無需或無法實(shí)際部署應(yīng)用時(shí),通過提取Android應(yīng)用的特征來檢測應(yīng)用。因此,這項(xiàng)技術(shù)只需處理Android應(yīng)用的APK文件,并通過分析文件內(nèi)容來發(fā)現(xiàn)潛在的安全隱患。APK文件是Android應(yīng)用的安裝包,包含該應(yīng)用的所有的資源文件,包括代碼、圖片、音頻和其他資源文件,幾乎所有的靜態(tài)檢測算法都是圍繞APK文件開發(fā)的。目前,重新包裝的應(yīng)用程序檢測研究取得了良好進(jìn)展,著名的靜態(tài)重打包檢測算法有Androguard[12]、FSquaDRA[13]、SimiDroid[14]和DNADroid[15]等,這些算法都是通過兩兩比對的方式進(jìn)行檢測。例如,現(xiàn)有一個(gè)應(yīng)用,疑是n個(gè)原應(yīng)用(即合法應(yīng)用,非重打包應(yīng)用)中的某一個(gè)應(yīng)用的重打包應(yīng)用,則現(xiàn)有的重打包應(yīng)用的檢測方法是將這個(gè)應(yīng)用與所有的原應(yīng)用都進(jìn)行一次檢測,即要進(jìn)行n次檢測。顯然,這n次檢測中有很多次檢測是無效的,也就是說如果可以通過有效的方法避免這些無效的檢測,減少檢測次數(shù),便能在提高這類需要兩兩對比的檢測算法的檢測效率。

SpectDroid對所有的需要進(jìn)行兩兩對比的重打包檢測算法都有效。以Androguard檢測算法為例,對SpectDroid的有效性進(jìn)行詳細(xì)分析。

1.1 Androguard

Androguard是一個(gè)用于處理Android文件的完整python工具,它提供惡意應(yīng)用程序分析、重打包檢測和其它功能。Android應(yīng)用的代碼由多個(gè)函數(shù)(或方法)組成。Androguard通過使用SHA256過濾相同的函數(shù)以及NCD(歸一化壓縮距離,一種計(jì)算二進(jìn)制文件相似性的算法)[16]過濾相似的函數(shù)來檢測重新打包的應(yīng)用程序。圖1所示為Androguard的檢測過程。

圖1 Androguard的檢測過程

SHA256是一種哈希算法,常用于檢校數(shù)據(jù)的完整性、快速查找和加密。該算法通過單向數(shù)學(xué)函數(shù)將任意長的輸入消息映射到固定長的輸出消息,也就是摘要。SHA256對于消息的變化特別敏感,當(dāng)輸入消息產(chǎn)生微小的變化,摘要就會(huì)產(chǎn)生非常大的變化,因此它可以過濾相同的函數(shù)。NCD是一個(gè)字符串的標(biāo)準(zhǔn)化值,常用于計(jì)算2個(gè)字符串之間的相似程度,因此可以用于查找功能相同的相似的函數(shù)。NCD可以通過計(jì)算獲得,NCD與字符串的相似程度呈負(fù)相關(guān),也就是說NCD值越小,字符串的相似程度越大。其計(jì)算公式如式(1)所示。

(1)

其中x和y是輸入的消息,L(s)是消息的長度,Comp(x)將消息x進(jìn)行壓縮,Comp(x|y)是消息x和y一起的壓縮,min(x,y)是取x和y中的最小值,max(x,y)是取x和y中的最大值。

在圖1所示的步驟之后,Androguard根據(jù)其NCD值和SHA256值將應(yīng)用程序的功能分為new、deleted、identical和similar這4類。具有相同SHA256值的函數(shù)被分類為identical。NCD小于0.4的功能將被歸類為similar。app1剩余的函數(shù)被分類為deleted,app2剩余的函數(shù)被分類為new。然后可以通過式(2)獲得2個(gè)應(yīng)用程序的相似度值。

(2)

其中|x|是類別x的函數(shù)的個(gè)數(shù),|base on option|是|deleted|或|new|。當(dāng)其為|deleted|時(shí),相似度結(jié)果為sim(1,2),當(dāng)其為|new|時(shí)相似度結(jié)果為sim(2,1)。顯然,sim(1,2)=sim(2,1)并不總是成立。對于同一對應(yīng)用程序,如果輸入順序不同,結(jié)果也不同。

通過式(2)可以得到2個(gè)應(yīng)用的相似度,若相似度大于閾值,則檢測應(yīng)用為重打包應(yīng)用。閾值的大小需要通過實(shí)驗(yàn)確定。

1.2 譜聚類

聚類分析是機(jī)器學(xué)習(xí)領(lǐng)域中的一個(gè)重要分支[18],常用于挖掘一組表面毫無規(guī)律的數(shù)據(jù)集的潛在規(guī)律,從而挖掘出數(shù)據(jù)的潛在價(jià)值。該類算法通過樣本之間的相似程度將樣本劃分為若干個(gè)互不相交的類簇,也就是每個(gè)樣本只能映射到一個(gè)簇。同一個(gè)簇內(nèi)的樣本的相似性較大,差異性較小;不同簇的樣本相似性較小,差異性較大。隨著大數(shù)據(jù)的發(fā)展,越來越多的數(shù)據(jù)可以用圖表示,因此關(guān)于圖聚類的問題應(yīng)運(yùn)而生。譜聚類具有實(shí)現(xiàn)簡單、聚類效果良好的優(yōu)點(diǎn),因此常用于解決圖聚類問題。譜聚類算法的本質(zhì)是譜圖理論[19],能應(yīng)用于任意形狀的樣本空間。

在譜聚類中,通常會(huì)根據(jù)數(shù)據(jù)集中各個(gè)樣本之間的關(guān)系得到一個(gè)加權(quán)圖G=(V,E)。其中,每一個(gè)頂點(diǎn)V都可以對應(yīng)為數(shù)據(jù)集中的一個(gè)樣本,兩點(diǎn)之間的邊E為對應(yīng)相連頂點(diǎn)對應(yīng)的樣本之間的關(guān)系,樣本間的相似度為E的賦權(quán)值W。在數(shù)據(jù)集轉(zhuǎn)化為圖之后,數(shù)據(jù)集的聚類問題就轉(zhuǎn)換為圖劃分問題。圖劃分的最優(yōu)結(jié)果是使得分成的所有子圖中,任意一個(gè)子圖的內(nèi)部頂點(diǎn)的相似度較大,任意2個(gè)子圖之間的相似度較小。因此,聚類結(jié)果與劃分準(zhǔn)則直接相關(guān),好的劃分準(zhǔn)則聚類結(jié)果較好,反之亦然。常見的劃分準(zhǔn)則有Ratio cut和MNcut等[20]。

現(xiàn)有的求圖劃分準(zhǔn)則的求解方法一般都是將數(shù)據(jù)集轉(zhuǎn)化為相似矩陣或Laplacian矩陣,從而將其轉(zhuǎn)換成求解相似矩陣問題或求解Laplacian矩陣的譜分解問題,所以這類方法統(tǒng)稱為譜聚類,求圖劃分的NP困難問題也就轉(zhuǎn)變?yōu)閷D劃分準(zhǔn)則的逼近。雖然譜聚類的不同的具體實(shí)現(xiàn)方法使用不同劃分準(zhǔn)則和譜映射方法,步驟或有不同,但其大致的算法過程都可以歸納如下[21]:

(1)根據(jù)樣本之間的關(guān)系得到表示樣本之間關(guān)系的矩陣L;

(2)計(jì)算出樣本關(guān)系矩陣L的前k個(gè)特征值與特征向量,構(gòu)建特征向量空間;

(3)用其它聚類算法對特征向量空間中的特征向量進(jìn)行聚類。

本文的譜聚類方法使用的矩陣是Laplacian矩陣,聚類方法是K-means。首先,計(jì)算Laplacian矩陣L=D-A,其中A是鄰接矩陣,D是對角矩陣;然后計(jì)算L的k個(gè)最小特征向量,忽略矩陣L的第一個(gè)特征向量并使用剩下的特征向量創(chuàng)建包含特征向量v1,v2,...,vn的矩陣V,最后使用k均值將V中的行聚類為k個(gè)社區(qū)。k值因測試樣本的不同而可能不同,該項(xiàng)研究通過實(shí)驗(yàn)獲取最優(yōu)k值。

2實(shí)驗(yàn)結(jié)果與討論

涉及到的實(shí)驗(yàn)在華碩筆記本電腦[Windows 10 x64, RAM 8GB, Intel(R) Core(TM) i5-7300HQ CPU 2.50GHz]上進(jìn)行。

2.1 Androguard閾值的確定

由1.1可知,Androguard主要通過計(jì)算可以得到2個(gè)應(yīng)用的相似度,然后用這個(gè)相似度跟既定的閾值進(jìn)行比較,如果相似度大于閾值,則待檢測應(yīng)用為重打包應(yīng)用,否則不是。閾值的確定需要找到召回率和精確率的平衡點(diǎn)。召回率又名查全率,是指檢索結(jié)果中真實(shí)為正例的樣本中預(yù)測結(jié)果為正例的比例;精確率也叫查準(zhǔn)率,為檢索結(jié)果中預(yù)測結(jié)果為正例樣本中真實(shí)為正例的比例。一般情況下,召回率與精確率呈負(fù)相關(guān),高召回率會(huì)導(dǎo)致低精確率,反之亦然。因此,閾值的確定就是尋找召回率和精確率的平衡點(diǎn)。召回率和精確率的計(jì)算需要用到混淆矩陣的相關(guān)知識(shí)。

混淆矩陣也稱誤差矩陣,是機(jī)器學(xué)習(xí)中常用的一種可視化方法,特別用于監(jiān)督學(xué)習(xí),在無監(jiān)督學(xué)習(xí)中一般叫做匹配矩陣。混淆矩陣通過用n行n列的矩陣來表示分類結(jié)果,能夠簡單直觀地呈現(xiàn)出分類結(jié)果,對于后續(xù)的分類結(jié)果的好壞起到關(guān)鍵作用。在重打包檢測中,可以通過閾值將實(shí)例分為正類、負(fù)類,結(jié)合分類的正確與否,有TP、FN、FP和TN共4種分類結(jié)果:

(1)TP:真正類,樣本的真實(shí)類別是正類,并且模型識(shí)別的結(jié)果也是正類;

(2)FN:假負(fù)類,樣本的真實(shí)類別是正類,但是模型將其識(shí)別為負(fù)類;

(3)FP:假正類,樣本的真實(shí)類別是負(fù)類,但是模型將其識(shí)別為正類;

(4)TN:真負(fù)類,樣本的真實(shí)類別是負(fù)類,并且模型將其識(shí)別為負(fù)類。

根據(jù)4種分類結(jié)果,便可以計(jì)算召回率和精確率,其計(jì)算公式如式(3)和式(4)所示。有時(shí)候準(zhǔn)確率也會(huì)作為判定閾值的一個(gè)衡量標(biāo)準(zhǔn),準(zhǔn)確率的計(jì)算公式如式(5)所示。

(3)

(4)

(5)

分別使用了50對應(yīng)用(21個(gè)原應(yīng)用和50個(gè)重打包應(yīng)用,一個(gè)原應(yīng)用可能有一個(gè)或多個(gè)重打包應(yīng)用)和100對應(yīng)用(34個(gè)原應(yīng)用和100個(gè)重打包應(yīng)用),從1%～99%,以1%為增幅設(shè)置了99個(gè)閾值,準(zhǔn)確率、召回率和精確率隨著閾值(threshold)的增加的變化情況如圖2和圖3所示。

圖2 50對應(yīng)用的準(zhǔn)確率、召回率和精確率的變化折線圖

圖3 100對應(yīng)用的準(zhǔn)確率、召回率和精確率的變化折線圖

由圖2和圖3可知,準(zhǔn)確率隨著閾值的增加而增加,但召回率在閾值達(dá)到一定程度后會(huì)開始急劇下降,因此,準(zhǔn)確率不適合用于作為閾值取值的衡量標(biāo)準(zhǔn),閾值的取值應(yīng)該取在召回率下降的拐點(diǎn)。為了綜合考慮準(zhǔn)確率和召回率,使用F-Score來權(quán)衡精確率和召回率。一般來說,精確度和召回率之間是矛盾的,這里引入F-Score作為綜合指標(biāo),就是為了平衡準(zhǔn)確率和召回率的影響,較為全面地評價(jià)一個(gè)分類器,F-Score越大說明模型質(zhì)量更高,其計(jì)算公式如式(6)所示。

(6)

如果β=1,表示Precision與Recall一樣重要;如果β<1,表示Precision比Recall重要;否則Recall比Precision重要。需要綜合考慮Precision與Recall,因此取β=1。F-Score隨著閾值的增加的變化情況如圖4和圖5所示。

圖4 50對應(yīng)用的F-Score變化折線圖

圖5 100對應(yīng)用的F-Score變化折線圖

當(dāng)以50對應(yīng)用作為樣本時(shí),F-Score在閾值為74%時(shí)取得最大值0.354 6,因此閾值可以定位74%,當(dāng)以100對應(yīng)用作為樣本時(shí),F-Score在閾值為74%時(shí)取得最大值0.259 1,因此閾值可以定為74%。

2.2 SpectDroid

使用1 000對應(yīng)用(275個(gè)原應(yīng)用和1 000個(gè)重打包應(yīng)用,將原應(yīng)用從1-199,以1為增幅設(shè)置了199個(gè)k值,準(zhǔn)確率隨著k值的增加的變化情況如圖6所示。

圖6 準(zhǔn)確率隨k值變化折線圖

3結(jié)論

(1)Androguard的閾值為74%。

(2)SpectDroid具有較高的準(zhǔn)確率和較快的檢測速度,其準(zhǔn)確率為81%,低于Androguard的97.3%,但計(jì)算量相對減少了74.18%。

(3)SpectDroid的準(zhǔn)確率和檢測速度呈負(fù)相關(guān),較快的檢測速度將會(huì)導(dǎo)致較低的準(zhǔn)確率。