王研昊 馬媛媛 楊 明 羅軍舟

(1 東南大學計算機科學與工程學院，南京211189)

(2 國網(wǎng)智能電網(wǎng)研究院，南京211106)

目前智能終端呈現(xiàn)普及化趨勢，其中Android系統(tǒng)占據(jù)了主導地位［1］.在其發(fā)展過程中，智能終端識別技術(shù)(即在終端設備中提取設備指紋從而將不同的終端進行區(qū)分)被廣泛應用于移動廣告精確投放、安全認證和訪問控制等領(lǐng)域.然而，現(xiàn)有的Android 智能終端識別技術(shù)均基于顯性標識符［2］，例如操作系統(tǒng)信息(Android_ID)、設備相關(guān)信息(IMEI，Build.Serial)和Sim 卡相關(guān)信息(IMSI、手機號碼)等.這些顯性標識符存在2 方面問題:①Android_ID，Build.Serial 并不完全可靠，可以被硬件制造商設置［3］，也較容易被人為篡改、偽造;②其他顯性標識符(如IMEI、IMSI、手機號碼等)都需要獲取READ_PHONE_STATE 這一敏感權(quán)限，會導致權(quán)限濫用和用戶隱私泄露等問題［4］.為此，研究人員提出了包含物理層、協(xié)議層、應用層、用戶層的一系列使用隱性標識符(特征)的設備識別方法，這些特征可以通過以下2 種方式獲取:①在終端內(nèi)部通過運行程序獲取;②在終端外部通過對其產(chǎn)生的流量、信號進行分析獲取.

基于物理層的特征主要來源于設備硬件上的差異［5］.基于此，Dey 等［6］在研究Android 智能終端的三軸加速度器時發(fā)現(xiàn)，即使同一個型號的加速度器也會因為制造等原因產(chǎn)生細微的差別，但其所需相同振動刺激的條件較為理想，且采集程序需要常駐后臺，采集周期較長;Zhou 等［7-8］通過智能終端麥克風記錄聲音來抽取特征，但在記錄聲音前需要申請RECORD_AUDIO 權(quán)限.基于協(xié)議層的特征主要來源于協(xié)議棧參數(shù)或協(xié)議驅(qū)動算法［9］.基于應用層的特征主要來源于所運行應用類型及其行為［10］;基于此，St?ber 等［11］在研究Android 智能終端領(lǐng)域時，通過比對后臺運行程序所產(chǎn)生的流量模式發(fā)現(xiàn)智能終端安裝的應用程序列表.基于用戶層的特征主要來源于用戶操作［12-13］.上述4 個層次的特征不是相互隔離的.Eckersley［14］針對瀏覽器指紋進行研究時，選取的特征涵蓋了物理層、應用層以及用戶層.

本文將在零權(quán)限的前提下針對Android 智能終端進行識別.由于研究的應用場景基于Android應用程序，故需要在Android 智能終端內(nèi)部獲取隱性標識符.基于物理層、應用層以及用戶層，選擇合適的隱性標識符形成設備指紋，并提出了相應的指紋識別算法，從而完成終端識別.

1 零權(quán)限指紋生成

1.1 指紋生成方法

不同于顯性標識符，單個隱性標識符一般不能用來進行唯一識別，即多個智能終端存在一定的概率共享同一屬性值.雖然單個隱性標識符不具備唯一識別能力，但是將多個隱性標識符組合起來，就可以顯著提高標識能力.

本文提出了一種基于隱性標識符組合的Android 智能終端指紋生成方法，這些隱性標識符可以在零權(quán)限前提下通過調(diào)用系統(tǒng)API 以及執(zhí)行Linux Shell 命令獲取.所有隱性標識符與其獲取結(jié)果形成〈key，value〉鍵值對形式的字典，從而構(gòu)成對應智能終端的設備指紋.參考Google 提供的Android 官方文檔并借鑒瀏覽器終端識別的相關(guān)工作［13-14］，選用表1所示的隱性標識符組合.

表1 零權(quán)限獲取的隱性標識符組合

如果不同用戶使用的Android 智能終端來自不同廠商，可以利用隱性標識符1，2 進行區(qū)分.如果不同用戶使用同一款智能終端，不同批次出貨的設備所帶操作系統(tǒng)信息可能會存在差異，尤其是當用戶進行刷機操作時，通過隱性標識符3，4 便可進行區(qū)分.如果用戶恰巧使用了同一批次的同一款智能終端，且沒有進行刷機操作，但由于用戶的使用習慣并非完全一樣，不同用戶對于系統(tǒng)語言、字體顯示的需求以及使用的應用程序都會存在差異，故可通過隱性標識符5 ～8 進行區(qū)分.尤其是對于用戶應用程序列表，除了應用包名外，還包含對應UID 號，即使用戶選擇安裝的應用列表完全相同，安裝順序的不同也會導致對應的UID 號不同，發(fā)現(xiàn)其中差異便可實現(xiàn)不同用戶間的區(qū)分.除應用程序列表外，其他7 個隱性標識符單獨使用時區(qū)分能力較弱，組合使用時便能獲得良好的區(qū)分效果.

1.2 理論分析

令F(y)為Android 設備y 所對應的設備指紋，P(fn)為F(y)分布所對應的離散概率密度函數(shù)，fn為可能出現(xiàn)的設備指紋，且n∈［0，1，…，N］.

首先，引入信息論中驚異值I 的概念，其定義如下:

設備指紋由多個隱性標識符組合而成，可以通過計算每個隱性標識符的驚異值來判斷其區(qū)分效果.設某個隱性標識符為s，其驚異值和信息熵分別為

針對某一特定的設備指紋，計算其中隱性標識符的驚異值，可得到各隱性標識符在該特定組合中的貢獻信息;而針對總體樣本，則計算隱性標識符的信息熵(即驚異值的期望)，得到該隱性標識符總體上所具有的信息量.

2 指紋匹配算法

Android 智能終端設備指紋由多個隱性標識符組合而成，可以通過2 個字典的精確匹配進行識別，但該方法沒有考慮設備指紋可能發(fā)生的變化.

為了解決由于用戶操作導致設備指紋發(fā)生變化影響匹配結(jié)果的問題，需要在精確匹配無法找到結(jié)果的情況下，引入關(guān)聯(lián)匹配算法.令已有指紋庫為S，新到來的設備指紋為x，則根據(jù)關(guān)聯(lián)匹配算法，在指紋庫中找到指紋q，滿足x 與q 對應同一個設備，且由于用戶操作等原因，x 和q 不完全相同.考慮到設備指紋變化的幅度不會太大，本文借鑒Eckersley［14］針對瀏覽器指紋的相關(guān)工作，提出了一種僅允許1 個隱性標識符發(fā)生變化且變化前后相似程度大于0.85 時的Android 設備指紋關(guān)聯(lián)匹配算法.

算法1 Android 設備指紋關(guān)聯(lián)匹配算法

輸入:已有設備指紋庫S，待關(guān)聯(lián)的設備指紋x.

輸出:關(guān)聯(lián)上的設備指紋，或NULL(關(guān)聯(lián)匹配失敗).

1 C=dict()，R=［］

2 for all j in {設備型號，屏幕信息，系統(tǒng)內(nèi)核，User Agent，系統(tǒng)語言，字體大小，字體列表，應用列表}do

3 C［j］=［］

4 end

5 for all e in S do //掃描整個指紋庫S

6 if x 與e 只有一個弱標識j 不相等

7 C［j］.append(e) //形成只有1 個隱性標識符變化的待選設備指紋集合C

8 end

9 for all j in C do //在C 中進行篩選找出最有可能變成x 的設備指紋，用列表R 存儲

10 if j in {設備型號，屏幕信息，系統(tǒng)內(nèi)核，User Agent，系統(tǒng)語言，字體大小}

11 for all e in C［j］do

12 R.append(e)

13 end

14 else if j in {字體列表，應用列表}

15 Mf=NULL，Mp=0

16 for all e in C［j］do

17 p=ListSimilarity(x［j］，e［j］)//ListSimilarity用杰卡德距離計算

18 if p ＞0.85 and p ＞Mp//選擇相似程度最大且不低于0.85 的加入R

19 Mp=p，Mf=e

20 end

21 if Mf!=NULL

22 R.append(Mf)

23 end

24 if len(R)==1

25 return R［0］

26 else

27 return NULL

需要指出的是，算法中閾值0.85 的選取是通過收集測試用戶一段時間內(nèi)的指紋數(shù)據(jù)并統(tǒng)計前后2 條指紋中列表類型數(shù)據(jù)的變化情況分析得到的，同時該取值與文獻［14］一致.

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

3.1 指紋數(shù)據(jù)的采集與分析

本實驗設計了Android 數(shù)據(jù)采集模塊DeviceFingerprint，收集設備指紋數(shù)據(jù)，同時該模塊申請了READ_PHONE_STATE 權(quán)限以獲取設備的IMEI 值.IMEI 值是可靠的顯性標識符，會隨著設備指紋一起上傳，由此便可為數(shù)據(jù)集進行標記，以備后續(xù)評估分析設備指紋識別算法的效果.為了采集真實用戶數(shù)據(jù)，該模塊被集成到東南大學先聲網(wǎng)客戶端內(nèi)，在全校范圍內(nèi)進行實驗.2014年9月22日開始，截止到2014年11月26日，共收集到22 798 條上傳的設備指紋數(shù)據(jù)，其中共出現(xiàn)了1 268 個不同的IMEI 值，即對應了1 268 個不同的Android 智能終端.

由1.2 節(jié)中的理論分析可知，根據(jù)式(1)計算數(shù)據(jù)集中不同設備指紋的驚異值，數(shù)據(jù)集中沒有完全相同的2 個設備指紋，故每臺設備指紋驚異值均為10.308 bit.然后，根據(jù)式(2)和(3)分別計算設備指紋中各個隱性標識符的驚異值和信息熵.信息熵越大，表示該隱性標識符所包含的信息量越大.隱性標識符的信息熵和發(fā)生變化的次數(shù)U 見表2.由表可知，應用程序列表的信息熵最大，變化次數(shù)也最多，其他應用層和用戶層隱性標識符也會發(fā)生變化.

表2 隱性標識符的信息熵

設備指紋與其發(fā)生變化隱性標識符數(shù)量的對應關(guān)系見圖1.由圖可知，不超過1 個隱性標識符發(fā)生變化的指紋數(shù)占所有指紋數(shù)的97.7%，說明算法1 中只允許1 個隱性標識符發(fā)生變化的限制是合理的.

圖1 數(shù)據(jù)集中設備指紋與發(fā)生變化隱性標識符數(shù)量間的關(guān)系

3.2 匹配算法結(jié)果分析

為了驗證匹配算法的執(zhí)行效果，需要在數(shù)據(jù)集上進行測試.按照每條指紋到來的時間順序進行測試，對于新來的一條設備指紋，如果在指紋庫中查找到匹配上的設備指紋，可依據(jù)IMEI 值驗證結(jié)果屬于真陽性還是假陽性;如果在指紋庫中沒有找到，也可依據(jù)IMEI 值驗證結(jié)果屬于真陰性還是假陰性;該條指紋匹配完成后，根據(jù)其IMEI 值更新指紋庫.將準確率RAccuracy、誤報率RFPR、漏報率RFNR作為匹配算法執(zhí)行效果的評價指標，其計算公式分別為

式中，NTP，NFP，NTN，NFN分別表示結(jié)果屬于真陽性、假陽性、真陰性、假陰性的數(shù)量.

精確匹配算法和關(guān)聯(lián)匹配算法的測試結(jié)果見表3.由表可知，采用精確匹配算法時，在22 798 條指紋中有15 977 條指紋被正確匹配，1 268 條指紋被正確識別出不在指紋庫中，5 553 條指紋被錯誤認為不在指紋庫中;識別準確率為75.6%，誤報率為0，漏報率為24.4%.這說明精確匹配總體效果不甚理想，誤報率為0 是期望的結(jié)果，但漏報率較高，究其原因在于沒有考慮設備指紋發(fā)生變化的情況.采用關(guān)聯(lián)匹配算法時，識別準確率為94.52%，誤報率為0.03%，漏報率為5.45%.相比精確匹配算法，關(guān)聯(lián)匹配算法的識別準確率明顯提高，同時漏報率也顯著下降.需要指出的是，結(jié)果中存在漏報是不可避免的，這是因為關(guān)聯(lián)匹配算法僅允許1個隱性標識符發(fā)生變化，如果用戶操作使得超過1個隱性標識符發(fā)生變化，算法便無法將同一個設備的2 條指紋進行關(guān)聯(lián).

表3 2 種算法的測試結(jié)果

4 結(jié)語

本文提出了一種在零權(quán)限條件下基于隱性標識符的Android 設備識別技術(shù)，將多個隱性標識符組合形成設備指紋，并對指紋識別算法進行了研究.實驗結(jié)果表明，隱性標識符組合具有較強的標識能力，所提的指紋匹配算法具有較好的識別效果.在后續(xù)工作中，將盡可能挖掘潛在的隱性標識符，利用特征選擇算法確定最優(yōu)特征子集，并嘗試其他機器學習識別算法.

References)

［1］ IDC.Smartphone OS market share［EB/OL］.(2015-01-15)［2015-01-31］.http://www.idc.com/prodserv/smartphone-os-market-share.jsp.

［2］ Han S，Jung J，Wetherall D.An empirical study of third-party tracking by mobile applications in the wild［R］.San Jose，CA，USA:NSDI，2012.

［3］ Google Inc.Identifying app installations［EB/OL］.(2011-03-01)［2015-01-31］.http://android-developers.blogspot.jp/2011/03/identifying-app-installations.html.

［4］ Grace M C，Zhou W，Jiang X，et al.Unsafe exposure analysis of mobile in-app advertisements［C］//Proceedings of the Fifth ACM Conference on Security and Privacy in Wireless and Mobile Networks.Tucson，Arizona，USA，2012:101-112.

［5］ Kohno T，Broido A，Claffy K C.Remote physical device fingerprinting［J］.IEEE Transactions on Dependable and Secure Computing，2005，2(2):93-108.

［6］ Dey S，Roy N，Xu W，et al.AccelPrint:imperfections of accelerometers make smartphones trackable［C］//Proceedings of the Network and Distributed System Security Symposium.San Diego，CA，USA，2014:1-16.

［7］ Zhou Z，Diao W，Liu X，et al.Acoustic fingerprinting revisited:generate stable device ID stealthily with inaudible sound［C］//Proceedings of the 2014 ACM SIGSAC Conference on Computer ＆Communications Security.New York，USA，2014:429-440.

［8］ Das A，Borisov N，Caesar M.Do you hear what I hear?Fingerprinting smart devices through embedded acoustic components［C］//Proceedings of the 2014 ACM SIGSAC Conference on Computer ＆ Communications Security.New York，USA，2014:441-452.

［9］ Franklin J，McCoy D，Tabriz P，et al.Passive data link layer 802.11 wireless device driver fingerprinting［C］//Proceedings of the 15th Conference on USENIX Security Symposium.Vancouver，Canada，2006:167-178.

［10］ Erman J，Arlitt M，Mahanti A.Traffic classification using clustering algorithms［C］//Proceedings of the 2006 SIGCOMM Workshop on Mining Network Data.Pisa，Italy，2006:281-286.

［11］ St?ber T，F(xiàn)rank M，Schmitt J，et al.Who do you sync you are smartphone fingerprinting via application behaviour［C］//Proceedings of the Sixth ACM Conference on Security and Privacy in Wireless and Mobile Networks.Budapest，Hungary，2013:7-12.

［12］ Pang J，Greenstein B，Gummadi R，et al.802.11 user fingerprinting［C］//Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking.Montreal，Canada，2007:99-110.

［13］ Acar G，Juarez M，Nikiforakis N，et al.FPDetective:dusting the web for fingerprinters［C］//Proceedings of the 2013 ACM SIGSAC Conference on Computer ＆Communications Security.Berlin，Germany，2013:1129-1140.

［14］ Eckersley P.How unique is your web browser?［C］//Proceedings of the 10th International Conference on Privacy Enhancing Technologies.Berlin，Germany，2010:1-18.