基于譜聚類的重打包應用檢測

2023-06-23 09:40:08蔡昆杰李呂牧之李帥常錦才

華北理工大學學報(自然科學版) 2023年3期

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

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

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

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

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

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

1方法

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

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

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

1.1 Androguard

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

圖1 Androguard的檢測過程

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

(1)

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

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

(2)

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

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

1.2 譜聚類

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

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

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

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

(2)計算出樣本關系矩陣L的前k個特征值與特征向量,構建特征向量空間;

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

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

2實驗結果與討論

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

2.1 Androguard閾值的確定

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

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

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

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

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

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

根據(jù)4種分類結果,便可以計算召回率和精確率,其計算公式如式(3)和式(4)所示。有時候準確率也會作為判定閾值的一個衡量標準,準確率的計算公式如式(5)所示。

(3)

(4)

(5)

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

圖2 50對應用的準確率、召回率和精確率的變化折線圖

圖3 100對應用的準確率、召回率和精確率的變化折線圖

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

(6)

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