王研昊 馬媛媛 楊 明 羅軍舟

(1 東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京211189)

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

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

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

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

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

1.1 指紋生成方法

不同于顯性標(biāo)識(shí)符，單個(gè)隱性標(biāo)識(shí)符一般不能用來(lái)進(jìn)行唯一識(shí)別，即多個(gè)智能終端存在一定的概率共享同一屬性值.雖然單個(gè)隱性標(biāo)識(shí)符不具備唯一識(shí)別能力，但是將多個(gè)隱性標(biāo)識(shí)符組合起來(lái)，就可以顯著提高標(biāo)識(shí)能力.

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

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

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

1.2 理論分析

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

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

設(shè)備指紋由多個(gè)隱性標(biāo)識(shí)符組合而成，可以通過(guò)計(jì)算每個(gè)隱性標(biāo)識(shí)符的驚異值來(lái)判斷其區(qū)分效果.設(shè)某個(gè)隱性標(biāo)識(shí)符為s，其驚異值和信息熵分別為

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

2 指紋匹配算法

Android 智能終端設(shè)備指紋由多個(gè)隱性標(biāo)識(shí)符組合而成，可以通過(guò)2 個(gè)字典的精確匹配進(jìn)行識(shí)別，但該方法沒(méi)有考慮設(shè)備指紋可能發(fā)生的變化.

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

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

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

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

1 C=dict()，R=［］

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

3 C［j］=［］

4 end

5 for all e in S do //掃描整個(gè)指紋庫(kù)S

6 if x 與e 只有一個(gè)弱標(biāo)識(shí)j 不相等

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

8 end

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

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

11 for all e in C［j］do

12 R.append(e)

13 end

14 else if j in {字體列表，應(yīng)用列表}

15 Mf=NULL，Mp=0

16 for all e in C［j］do

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

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 的選取是通過(guò)收集測(cè)試用戶(hù)一段時(shí)間內(nèi)的指紋數(shù)據(jù)并統(tǒng)計(jì)前后2 條指紋中列表類(lèi)型數(shù)據(jù)的變化情況分析得到的，同時(shí)該取值與文獻(xiàn)［14］一致.

3 實(shí)驗(yàn)與結(jié)果分析

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

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

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

表2 隱性標(biāo)識(shí)符的信息熵

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

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.