基于密度聚類和隨機森林的移動應用識別技術

朱 迪，陳丹偉

南京郵電大學 計算機學院、軟件學院、網絡空間安全學院，南京210023

1 引言

近年來，隨著智能移動終端硬件性能的大幅提升，軟件功能的日益豐富，智能移動終端的使用量也在持續增長。美國調查公司IDC的統計報告顯示，2016年全世界智能設備總銷售量高達14億7 060萬部[1]。另一家調查公司Statista統計報告顯示，截至2017年3月，Google Play中已包含280萬種不同類型的應用程序[2]。如今智能移動終端已經是人們日常生活中不可或缺的工具，人們通過手機進行基本的語音通話、短信交流以及互聯網相關的電子郵件、社交網絡等日常的通信活動，與此同時各種基于移動設備的攻擊手段應運而生，例如多年來屢見不鮮的間諜技術和獲取個人定位的手段[3-5]等。

傳統的攻擊防范技術中，最典型的方法即從源頭出發，通過識別和隔離移動終端中運行的惡意代碼[6-8]，減少來自網絡的攻擊和威脅。然而，隨著網絡攻擊防范技術的不斷提高，許多攻擊手段不需要控制終端設備就可以竊取用戶隱私，甚至實施定向攻擊。本文主要討論一種被動攻擊方式，即攻擊者通過監聽和分析網絡通信數據，獲取用戶的敏感信息?，F如今大多數移動應用程序都采用SSL/TLS（Secure Sockets Layer/Transport Layer Security）協議進行數據加密，即便如此，攻擊者仍然可以通過分析加密流量，間接推斷用戶的敏感信息，例如通過加密流量分析實現對當前網絡中某個特定用戶身份的識別[9]。

本文致力于通過加密流量分析，實現Android平臺下移動應用程序的類型識別。一般情況下，用戶根據自己的喜好安裝應用程序，因此獲取了用戶在移動設備上安裝的應用程序類型，即可間接盜取類似用戶興趣、偏好這類隱私信息[10]。這類敏感信息對廣告市場調研、網絡監控和管理、網絡攻擊防范、網絡規劃、流量工程等相關工作具有重要的參考價值和實際意義。

2 相關工作

近年來，國內外信息安全領域針對加密流量分類、移動應用程序類型識別等相關課題取得了諸多研究成果，這類相關算法大致可以分為基于數據包負載信息的流量分類和基于數據流通信模式的流量分類。其中，前者利用數據包IP地址、端口號以及數據包負載中的信息實現流量分析和分類[11-12]，然而這類方法并不能適用于加密環境；后者僅利用數據流向、數據包長度以及某些與數據包長度相關的統計特性即可有效地實現加密流量中應用程序或流量類型的識別[13]。

文獻[14]實現了一種基于802.11協議的移動應用類型識別方法。作者采集目標應用程序所產生的數據包，對原始數據進行特征提取，并用于訓練應用程序識別模型，但僅對13種應用程序進行了建模。文獻[15]中的實驗表明，在應用程序數量增加到110種的情況下，該方法識別準確率大幅下降。

文獻[16]提出了一種移動應用中用戶行為類型識別算法。首先利用加密數據流中的數據包長度和數據流向等信息描述每個數據流樣本，接著利用層次聚類算法（Hierarchical Clustering）對所有加密數據流進行聚類，再將聚類產生的簇標簽映射到每個用戶動作產生的多個流中，最后將簇標簽表示的數據集作為輸入，訓練隨機森林模型實現用戶行為識別。實驗表明該算法識別準確率高達95%。

文獻[15]分別嘗試利用支持向量機（Support Vector Machine，SVM）和隨機森林（Random Forest）兩種算法，實現了對Google Play中110種應用程序的識別。作者指出不同應用程序會產生相似流量模式的數據流，例如各類應用程序產生的廣告數據流和相同API產生的通信數據流，這些數據流樣本被視為相似干擾樣本。因此，通過設置“預測概率閾值”，過濾分類模型預測概率較低的干擾樣本。

事實上，訓練后的分類模型對某些樣本的預測概率較低，其原因除了該樣本不具有較明顯的類別辨識特征之外，也可能意味著算法模型訓練不充分。因此，本文在文獻[15]的基礎上，將聚類算法和信息熵概念相結合，提出了一種聚類簇純度分析方案過濾干擾樣本，緩解由于模型訓練不充分而造成的干擾樣本誤判的問題，提高數據集利用率。

3 Android移動應用類型識別算法

在加密環境下，可以通過對數據流通信模式的建模實現移動應用類型識別。為了克服干擾數據流的誤判問題，本文在文獻[15]的基礎上，引入基于信息熵的聚類簇純度分析思想，提出了一種將DBSCAN（Density-Based Spatial Clustering of Applications with Noise）密度聚類算法與隨機森林算法相結合的移動應用程序識別算法。

3.1 加密數據流特征提取

3.1.1 相關概念

為了將連續的網絡流量合理地離散化，文獻[16]提出了突發的概念。突發（Burst）是指發送或接收的時間間隔小于某個閾值的一系列相臨分組，該閾值稱為突發閾值（Burst Threshold）。

文獻[15]提出了數據流的概念。在一個突發中，與同一對網絡四元組相關的所有分組組成一條數據流。與傳輸控制協議（Transmission Control Protocol，TCP）會話的不同之處在于，一個TCP會話可能會跨越多個突發，而一個數據流是在某個突發中的部分TCP會話通信內容。

文獻[16]提出一條數據流可以從數據流向的角度，用三個分組時間序列來描述，分別為：（1）由數據流中流入的每個分組的長度按時間順序排列的序列；（2）由數據流中流出的每個分組的長度按時間順序排列的序列；（3）數據流中流入和流出的每個分組的長度按時間順序排列的序列。

3.1.2 加密數據流的統計特征提取

加密流特征提取方法分為兩大類：（1）以數據流的數據包長度時間序列作為特征；（2）計算包長度時間序列的統計量作為特征。方案一有效地體現了數據流中數據包大小隨時間的變化關系，但信息單一后續分類算法難以學習；方案二通過計算包長度序列的統計量，提供了豐富的統計信息，但損失了數據流的時序信息。文獻[15]提出了一種將二者相結合的特征提取方案，提取原始包長度及包長度序列統計信息共計18個特征，既保留了部分包長度時序信息，又通過統計計算豐富了特征信息。其中，9個數據包長度序列統計特征包括平均值、中位數、方差、最小值、最大值、絕對偏差、標準偏差、偏斜、峰度。另外，以10%為間隔，跳躍截取數據流的9個數據包長度作為原始包長度特征，即數據流中第10%，20%，…，90%個數據包的長度?；嶂匾裕℅ini Importance）是隨機森林中常用的特征重要性度量指標，表示以屬性a作為特征，并以該屬性的取值劃分的V個數據子集{D1,D2,…,DV}的純度提升程度。通常，若某個屬性的基尼重要性大于1%，則該屬性能夠為算法模型提供一定的有效信息[17]。圖1為文獻[15]中18個特征的基尼重要性分布圖，可以看出76%的統計特征的基尼重要性大于1.26%，因此本文將繼續采用文獻[15]提出的特征提取方案。

圖1 統計特征的基尼重要性分布圖

加密數據流的特征提取具體分為以下步驟：

（1）將加密流量離散化為若干個突發，并對每個突發進行數據流分離，形成若干條數據流，該過程如圖2所示。

（2）將每個加密流表示為3個分組時間序列。

（3）分別計算3個分組時間序列的18個特征，那么每個加密數據流樣本特征維度為54。

3.2 干擾樣本的過濾

如前文所述，不同移動應用可能產生相似的加密數據流，這些相似的加密流不足以區分移動應用類型，相反這些樣本對后續的機器學習建模過程造成了干擾。本文提出了一種聚類簇純度分析思想，將DBSCAN聚類算法和信息熵相結合，實現了對干擾樣本的有效過濾。

3.2.1 DBSCAN密度聚類算法

DBSCAN是一種密度聚類算法，其基本思想是利用鄰域參數(ε,MinPts)描述數據集樣本的聚集程度。設數據集，則相關概念有：

圖2 連續網絡流量的離散和分離過程

（1）ε-鄰域：對xj∈D，由樣本集D中與xj的距離不大于ε的樣本所組成的集合稱為ε-鄰域，公式表達如下：

（2）核心對象（Core Object）：若xj的ε-鄰域至少包含MinPts個樣本，那么xj是一個核心對象，即：

（3）密度直達（Directly Density-Reachable）：若xj位于xi的ε-鄰域中，且xi是核心對象，則稱xj由xi密度直達。

（4）密度可達（Density-Reachable）：對于樣本序列p1,p2,…,pn，若存在p1=xi,pn=xj且pi+1由pi密度直達，則稱xj由xi密度可達。

DBSCAN算法首先根據給定的鄰域參數(ε,MinPts)找出全部核心對象，接著任選一個核心對象，根據密度可達原則生成聚類簇，直至所有核心對象遍歷完成為止。

3.2.2 聚類簇純度度量

信息熵（Information Entropy）是度量樣本集合純度的常用指標，本文將利用信息熵為聚類算法形成的每個聚類簇進行純度打分。

設數據集D中共有M種不同類型的樣本，聚類算法將數據集D聚合為N個簇，每個聚類簇樣本集記為Di(i=1,2,…,N)，隨機變量Xi表示聚類簇樣本集Di中樣本的標簽類型j=1,2,…,M)表示類型xj在Di中的出現概率。那么，聚類簇樣本集Di的信息熵計算公式如下：

由上述信息熵計算公式可知，Ent(Di)的值越小，則聚類簇樣本集Di的純度越高。具體來說，信息熵較大的聚類簇所包含的樣本所體現的通信模式是許多應用程序所共有的模式。因此，這些樣本不宜用于應用程序類型識別。本文通過設置信息熵閾值，過濾信息熵超過信息熵閾值的簇中所包含的樣本，從而提高后續分類算法的識別準確率。

3.3 隨機森林算法

3.3.1 決策樹與隨機森林

隨機森林算法是Bagging算法的擴展變形，該算法將決策樹（Decision Tree）作為基學習器，在Bagging集成的基礎上，進一步為決策樹的訓練過程引入了隨機屬性選擇。對于每一個基學習器而言，屬性節點的選擇是決策樹學習的關鍵，常用的劃分屬性優劣度量指標主要有三種：

（1）信息增益（Information Gain）

假設某離散屬性a有V種取值{a1,a2,…,aV}，D中所有在屬性a上取值為av的樣本所組成的集合，記為Dv，則信息增益定義為：

一般將信息增益最大的屬性作為劃分屬性。

（2）增益率（Gain Ratio）

增益率計算公式為：

其中，IV(a)稱為屬性a的固有值（Instrinsic Value）。增益率越大意味著該屬性越適宜作為劃分屬性。

（3）基尼指數（Gini Index）

基尼指數的計算公式為：

基尼指數較小的屬性適宜作為劃分屬性。

3.3.2 基于隨機森林的移動應用識別算法

移動終端的加密流量按產生方式可以分為交互式流量和非交式流量[15]，本文主要關注加密流量中的交互式流量?，F如今移動應用程序種類豐富，主要包括社交軟件、購物軟件、辦公軟件以及游戲軟件等，由于移動應用的需求和功能各不相同，產生的加密數據流傳輸模式則有所不同。本文所采用的隨機森林算法適合學習種類繁多、錯綜復雜的數據樣本關系。隨機森林算法利用多個決策樹模型集成一個強學習器，由于該算法在決策樹的基礎上引入了隨機劃分屬性選擇，使得弱分類器具有較強的多樣性，利于捕捉復雜多樣的移動應用通信模式。具體算法流程結構如圖3所示。

圖3 算法流程結構

將經過第3.2節干擾樣本過濾處理的數據集D，作為隨機森林算法的輸入數據，依次訓練每個決策樹分類模型。訓練期間引入隨機劃分屬性選擇機制，即對于基決策樹的每個劃分屬性，首先從當前節點的屬性集合中隨機選擇一個包含k個屬性的屬性子集，接著在該子集中選擇一個最優屬性作為劃分屬性。在測試模型時，所有基決策樹投票得出最終決策。

4 實驗

4.1 實驗環境及數據

實驗所用的計算機操作系統為Ubuntu 14.04，CPU為i5-6500，內存16 GB，主頻3.2 GHz，開發環境為Python 2.7，使用scikit-learn 0.2.0進行機器學習建模。

本文采用文獻[15]中的數據集進行移動應用類型識別。該數據集包含110種Google Play中的最流行移動應用，共計131 736個數據流。該數據集具有一定的普適性和真實性，能夠較好地驗證本文所述方法的有效性和實用性，另一方面也可以更好地對比本文和文獻[15]所述算法的識別準確率。

4.2 聚類簇純度分析

首先，利用DBSCAN聚類算法對原始數據集進行聚類分析。為合理設置算法的ε和MinPts參數，對數據集中樣本間距離進行統計分析，分析結果如圖4。由圖4可知，超過95%的樣本與其最鄰近的樣本間距小于0.7，因此ε取值為0.7。

圖4 樣本與其最近樣本距離分布圖

圖5為ε=0.7時，每個樣本的ε-鄰域所包含的樣本數量。其中6.6%的樣本周圍的臨近樣本數量低于33，由于臨近樣本數量較少，這些樣本可以視為DBSCAN聚類中的噪聲樣本，從而MinPts應設為33。

圖5 樣本的ε-鄰域所包含的樣本數量分布圖

以ε=0.7,MinPts=33為參數進行DBSCAN密度聚類，聚類完成后計算每個聚類簇的信息熵。樣本所在簇的信息熵與樣本數量的關系如圖6所示。

圖6 聚類后樣本的信息熵分布圖

4.3 評價指標

對于機器學習的分類問題，常用的評價指標有準確率（Accuracy）、召回率（Recall）和精確率（Precision），具體公式如下：

其中，TP（True Positive）表示正例預測為正例的樣本數；FP（False Positive）表示反例預測為正例的樣本數；TN（True Negative）表示正例預測為反例的樣本數；FN（False Negative）表示反例預測為反例的樣本數。

4.4 實驗結果

由第4.2節的聚類簇純度分析可知，約有75%的樣本其所屬聚類簇的信息熵小于2.6 bit。在此基礎上，本文分別設置不同熵閾值進行實驗。表1為不同熵閾值下的應用識別效果。

表1 不同熵閾值的實驗結果

本文提出聚類簇純度分析思想，通過信息熵為聚類簇純度打分，過濾信息熵較大的簇樣本，提高分類準確率。隨著熵閾值減小，過濾的樣本數量和分類準確率逐漸增加，樣本利用率逐漸降低，如圖7所示。

圖7 應用識別效果與熵閾值的關系曲線

本文在文獻[15]的基礎上提出了改進。文獻[15]提出的基于預測概率閾值的干擾樣本過濾方法，存在干擾樣本誤判的問題。而本文提出的基于聚類簇信息熵閾值的樣本過濾方法，降低了干擾樣本的誤判概率，因此過濾較少的樣本即可達到較好的識別效果，提高了樣本利用率。在相同樣本利用率的情況下，本文方法與文獻[15]應用識別效果對比如圖8所示。當樣本利用率大于90%時，由于兩種算法均采用隨機森林算法進行建模，準確率和召回率差異較??；當樣本利用率小于85%時，本文方法的準確率和召回率基本穩定高于文獻[15]所述方法。本文提出的基于信息熵的聚類簇純度分析方法，減少了干擾樣本的誤判，從而有效地提高了樣本利用率。

5 結束語

圖8 兩種算法的識別效果比較

本文提出了一種基于DBSCAN和隨機森林的移動應用程序識別算法，提出了一種基于信息熵的聚類簇純度分析方案，緩解了由于模型訓練不充分導致的干擾樣本誤判問題，提高了對移動加密流量中不同應用間的相似干擾加密流的過濾效果。最后，本文通過實驗與文獻[15]提出的基于預測閾值和隨機森林的移動應用識別方法進行對比，實驗結果表明，本文方案在相同樣本利用率的情況下，算法的識別準確率和召回率均優于文獻[15]所述方法。