孫 全 , 許 蕾 , 夏昕濛 , 張衛(wèi)豐

1(計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室(南京大學(xué)),江蘇 南京 210023)

2(南京大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系,江蘇 南京 210023)

3(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院,江蘇 南京 210023)

移動(dòng)互聯(lián)網(wǎng)時(shí)代,手機(jī)和平板逐漸普及,信息傳播和數(shù)據(jù)處理逐漸從電腦端向手機(jī)端遷移.

根據(jù)IDC(http://www.idc.com/prodserv/smartphone-os-market-share.jsp)關(guān)于智能手機(jī)操作系統(tǒng)的統(tǒng)計(jì)報(bào)告,截至2016 年第3 季度,安卓系統(tǒng)的市場(chǎng)份額高達(dá)86.8%.但由于安卓系統(tǒng)的開(kāi)源性、手機(jī)廠(chǎng)商快速迭代盈利、開(kāi)發(fā)者水平參差不齊,信息泄漏、惡意扣費(fèi)、系統(tǒng)崩潰常見(jiàn)于安卓應(yīng)用中.大量的技術(shù)和方法隨之被用于解決安卓系統(tǒng)存在的問(wèn)題,包括GUI 測(cè)試[1-4]、惡意軟件檢測(cè)[5-7]、并發(fā)缺陷檢測(cè)[8-10]等.安卓應(yīng)用并發(fā)缺陷檢測(cè)是近年興起的研究領(lǐng)域,早期多存在于Java,C/C++程序中.

在安卓應(yīng)用中,并發(fā)缺陷檢測(cè)不僅面臨線(xiàn)程調(diào)度不確定性的挑戰(zhàn),還面臨著事件調(diào)度不確定性的挑戰(zhàn).因?yàn)榘沧肯到y(tǒng)是事件驅(qū)動(dòng)的,需要監(jiān)聽(tīng)多種類(lèi)型的事件,這些事件來(lái)源于用戶(hù)的操作、傳感器和系統(tǒng)本身,并且這些事件是無(wú)序的、不可預(yù)計(jì)的、并發(fā)的.傳統(tǒng)的靜態(tài)分析[1,11-15]和動(dòng)態(tài)分析[16-18]都不能直接應(yīng)用于安卓系統(tǒng)中的并發(fā)缺陷檢測(cè).

并發(fā)程序具有效率高、速度快的特性,但由于并發(fā)程序內(nèi)多線(xiàn)程交互頻繁、調(diào)度復(fù)雜,存在缺陷的可能性也會(huì)更高,產(chǎn)生的結(jié)果也更嚴(yán)重.并發(fā)缺陷包括數(shù)據(jù)競(jìng)爭(zhēng)、死鎖、原子性違反等多種類(lèi)型,本文主要關(guān)注并發(fā)缺陷中的數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題.數(shù)據(jù)競(jìng)爭(zhēng)的發(fā)生需要滿(mǎn)足兩個(gè)條件:(1)至少兩個(gè)語(yǔ)句并發(fā)執(zhí)行,并訪(fǎng)問(wèn)同一個(gè)共享變量,其中一個(gè)是寫(xiě)操作;(2)沒(méi)有額外的同步機(jī)制進(jìn)行同步操作.

本文實(shí)現(xiàn)了工具RaceDetector 來(lái)檢測(cè)安卓應(yīng)用中的數(shù)據(jù)競(jìng)爭(zhēng),特別是關(guān)注空引用造成的有害數(shù)據(jù)競(jìng)爭(zhēng).因?yàn)闊o(wú)害的數(shù)據(jù)競(jìng)爭(zhēng)并不會(huì)有明顯的嚴(yán)重后果,不會(huì)造成損失和嚴(yán)重的危害;而有害的數(shù)據(jù)競(jìng)爭(zhēng)會(huì)嚴(yán)重影響用戶(hù)體驗(yàn),甚至?xí)斐刹豢深A(yù)計(jì)的損失,比如死機(jī)、系統(tǒng)應(yīng)用的重啟等.

工具RaceDetector 主要包括2 個(gè)階段的工作:第1 階段記錄信息,并根據(jù)數(shù)據(jù)競(jìng)爭(zhēng)的第1 個(gè)滿(mǎn)足條件產(chǎn)生可疑的數(shù)據(jù)競(jìng)爭(zhēng)候選集合(CS);第2 階段根據(jù)安卓應(yīng)用的先后序關(guān)系,使用約束求解方法識(shí)別真正數(shù)據(jù)競(jìng)爭(zhēng)(RS).本文使用靜態(tài)分析解析全部源碼并記錄相關(guān)的信息,并使用擴(kuò)展的共享變量分析來(lái)優(yōu)化性能和提高準(zhǔn)確率.

本文的主要貢獻(xiàn)如下:

(1)本文提出了安卓共享變量分析,優(yōu)化了傳統(tǒng)的逃逸分析去定位安卓共享變量,減小了分析的維度,提高了檢測(cè)的性能和準(zhǔn)確度.

(2)本文結(jié)合靜態(tài)分析和約束求解方法來(lái)檢測(cè)安卓應(yīng)用中的數(shù)據(jù)競(jìng)爭(zhēng).相對(duì)于現(xiàn)有工具EventRacer[8]、CAFA[9]、RaceDroid[10]使用動(dòng)態(tài)分析存在固有覆蓋率低的缺點(diǎn),靜態(tài)分析能夠解析全部的源碼,并使用約束求解計(jì)算了所有可能執(zhí)行的事件調(diào)度策略,提高了檢測(cè)覆蓋率.

(3)本文對(duì)數(shù)據(jù)競(jìng)爭(zhēng)的危害程度進(jìn)行了區(qū)分,重點(diǎn)關(guān)注由空引用造成的有害數(shù)據(jù)競(jìng)爭(zhēng).相對(duì)于無(wú)害數(shù)據(jù)競(jìng)爭(zhēng),有害數(shù)據(jù)競(jìng)爭(zhēng)會(huì)影響用戶(hù)體驗(yàn),造成不可預(yù)期的后果.本文重點(diǎn)闡述空引用造成的有害數(shù)據(jù)競(jìng)爭(zhēng).

(4)實(shí)驗(yàn)詳細(xì)闡述了安卓應(yīng)用中數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題,并實(shí)現(xiàn)了相關(guān)工具RaceDetector.本文從Google Play 收集了15 個(gè)流行的應(yīng)用APK 文件作為數(shù)據(jù)集,與現(xiàn)有工具EventRacer 默認(rèn)產(chǎn)生300 隨機(jī)輸入事件并平均檢測(cè)2 個(gè)有害數(shù)據(jù)競(jìng)爭(zhēng)相比,RaceDetector 平均報(bào)告了340 個(gè)數(shù)據(jù)競(jìng)爭(zhēng),誤報(bào)率為13%(44/340),其中,15 個(gè)為有害的數(shù)據(jù)競(jìng)爭(zhēng)(4%=15/340).

本文第1 節(jié)主要介紹安卓系統(tǒng)以及數(shù)據(jù)競(jìng)爭(zhēng)的基本概念.第2 節(jié)通過(guò)實(shí)例說(shuō)明數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)存在的挑戰(zhàn).第3 節(jié)重點(diǎn)闡述檢測(cè)工具RaceDetector 各個(gè)模塊的設(shè)計(jì)和實(shí)現(xiàn).第4 節(jié)是實(shí)驗(yàn)評(píng)估以及實(shí)驗(yàn)結(jié)果分析.第5 節(jié)介紹相關(guān)工作.第6 節(jié)總結(jié)全文.

1 基本概念

本節(jié)將介紹安卓系統(tǒng)相關(guān)的概念,并討論安卓應(yīng)用中的數(shù)據(jù)競(jìng)爭(zhēng).

安卓系統(tǒng)有4 大基本組件.

(1)活動(dòng)(activity):是安卓應(yīng)用中最常見(jiàn)的組件,用于展現(xiàn)用戶(hù)可見(jiàn)的界面.該組件展現(xiàn)了相關(guān)的視圖,用戶(hù)可與之進(jìn)行交互.

(2)服務(wù)(service):用于在后臺(tái)執(zhí)行耗時(shí)較多的任務(wù),并作相應(yīng)的數(shù)據(jù)處理工作.

(3)廣播接收器(broadcast receiver):用于發(fā)起廣播和監(jiān)聽(tīng)廣播,從而傳遞消息,并據(jù)此及時(shí)響應(yīng)和處理.

(4)內(nèi)容提供者(content provider):可公開(kāi)提供自己的數(shù)據(jù)存儲(chǔ)接口并提供路徑,其他組件可以通過(guò)路徑訪(fǎng)問(wèn)相應(yīng)的數(shù)據(jù).

活動(dòng)和服務(wù)有其自由的生命周期回調(diào)方法(onCreate(?),onStart(?),onBind(?),onUnBind(?),onDestroy(?)等).這些生命周期方法描述了組件不同的狀態(tài)和行為.所有的生命周期方法都被安卓系統(tǒng)所管理,不同的狀態(tài)和條件下,相關(guān)的組件會(huì)被創(chuàng)建或銷(xiāo)毀.

在安卓系統(tǒng)中,當(dāng)一個(gè)應(yīng)用啟動(dòng)的時(shí)候,會(huì)創(chuàng)建一個(gè)主線(xiàn)程去處理界面渲染、與用戶(hù)交互等不同事件.在主線(xiàn)程中,循環(huán)體(looper)、處置器(handle)和消息隊(duì)列(message queue)共同處理事件的分發(fā)和處置,也就是所謂的消息隊(duì)列模型.通常,處置器會(huì)對(duì)相關(guān)的數(shù)據(jù)以及任務(wù)執(zhí)行入隊(duì)操作;循環(huán)體則無(wú)限循環(huán)并取出消息隊(duì)列中的數(shù)據(jù)和任務(wù),然后分發(fā)給相關(guān)的處置器處理.圖1 展示了主線(xiàn)程和工作線(xiàn)程的運(yùn)行機(jī)制.因?yàn)橹骶€(xiàn)程要不斷處理用戶(hù)交互以及界面渲染等工作,通常會(huì)創(chuàng)建工作線(xiàn)程去執(zhí)行這些計(jì)算消耗型任務(wù),包括AsyncTask、HandleThread等.這些工作線(xiàn)程可在后臺(tái)并發(fā)地執(zhí)行相關(guān)任務(wù),并通過(guò)相關(guān)的接口與主線(xiàn)程進(jìn)行交互,從而更新界面.

Fig.1 Mutil-thread model of Android system圖1 安卓系統(tǒng)多線(xiàn)程模型

區(qū)別于過(guò)程驅(qū)動(dòng)編程模型,安卓應(yīng)用是事件驅(qū)動(dòng)編程模型,通過(guò)監(jiān)聽(tīng)不同的事件運(yùn)行并更新相關(guān)界面.用戶(hù)的操作、系統(tǒng)的事件、傳感器等都會(huì)作為輸入事件流[19].圖2 展現(xiàn)了安卓應(yīng)用中事件的構(gòu)成和相互間的關(guān)系.

Fig.2 Event driven model of Android system圖2 安卓系統(tǒng)事件驅(qū)動(dòng)模型

一個(gè)輸入事件可以產(chǎn)生于硬件或者軟件:產(chǎn)生于軟件的事件通常發(fā)生于應(yīng)用內(nèi)部,如Message和Runnable;大部分事件屬于硬件事件(分為輸入事件、傳感器事件和系統(tǒng)事件),其中,輸入事件定義了用戶(hù)的交互操作行為,傳感器硬件監(jiān)聽(tīng)環(huán)境的信息狀態(tài)并傳遞給安卓應(yīng)用,系統(tǒng)事件定義了安卓系統(tǒng)平臺(tái)自身狀態(tài)信息.這些事件被封裝成消息或者任務(wù),最終經(jīng)過(guò)消息隊(duì)列模型得到處置.通常,一個(gè)安卓應(yīng)用中會(huì)包含上千個(gè)各類(lèi)事件.

安卓應(yīng)用中,復(fù)雜的系統(tǒng)平臺(tái)以及眾多的用戶(hù)操作和對(duì)應(yīng)的事件處理函數(shù)使得數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)變得極為困難:一方面,數(shù)據(jù)競(jìng)爭(zhēng)可以發(fā)生在主線(xiàn)程和工作線(xiàn)程之間或者多個(gè)工作線(xiàn)程之間,即多線(xiàn)程數(shù)據(jù)競(jìng)爭(zhēng);另一方面,數(shù)據(jù)競(jìng)爭(zhēng)可以?xún)H發(fā)生在主線(xiàn)程中,也就是所謂的單線(xiàn)程數(shù)據(jù)競(jìng)爭(zhēng).單線(xiàn)程數(shù)據(jù)競(jìng)爭(zhēng)最初是網(wǎng)絡(luò)服務(wù)程序中的概念[20-25].此類(lèi)數(shù)據(jù)競(jìng)爭(zhēng)通常發(fā)生在界面組件以及監(jiān)聽(tīng)事件的回調(diào)方法之間.另外,安卓系統(tǒng)中不同應(yīng)用執(zhí)行在不同進(jìn)程當(dāng)中,由于不同應(yīng)用之間也可以交互,因此也存在多進(jìn)程交互的問(wèn)題,并造成多進(jìn)程數(shù)據(jù)競(jìng)爭(zhēng).由于在現(xiàn)實(shí)世界中出現(xiàn)較少,本文不討論多進(jìn)程數(shù)據(jù)競(jìng)爭(zhēng),只關(guān)注單線(xiàn)程數(shù)據(jù)競(jìng)爭(zhēng).

根據(jù)數(shù)據(jù)競(jìng)爭(zhēng)危害程度上的差異,本文把數(shù)據(jù)競(jìng)爭(zhēng)分為兩種類(lèi)型:有害的數(shù)據(jù)競(jìng)爭(zhēng)和良性的數(shù)據(jù)競(jìng)爭(zhēng).良性的數(shù)據(jù)競(jìng)爭(zhēng)常見(jiàn)于多線(xiàn)程程序中,并不會(huì)對(duì)程序本身造成嚴(yán)重后果.在實(shí)際研究中,只檢測(cè)良性數(shù)據(jù)競(jìng)爭(zhēng)意義不是很大.有害的數(shù)據(jù)競(jìng)爭(zhēng)可分為兩種類(lèi)型:一類(lèi)是有具體的、明顯的有害行為,這類(lèi)數(shù)據(jù)競(jìng)爭(zhēng)一旦發(fā)生,就會(huì)在應(yīng)用本身上所體現(xiàn),例如應(yīng)用卡頓、崩潰等行為;另一類(lèi)并不會(huì)展現(xiàn)明顯的有害行為,但是對(duì)應(yīng)用正常的邏輯和數(shù)據(jù)造成影響.本文關(guān)注的是第1 類(lèi)有害數(shù)據(jù)競(jìng)爭(zhēng),并且具體到空引用(free-use)這一類(lèi)問(wèn)題上.

2 案例分析

本節(jié)將根據(jù)一個(gè)案例來(lái)詳細(xì)說(shuō)明安卓應(yīng)用中存在有害數(shù)據(jù)競(jìng)爭(zhēng),并討論現(xiàn)有方法檢測(cè)數(shù)據(jù)競(jìng)爭(zhēng)的局限性.

我們選取了工具EventRacer 數(shù)據(jù)集中的一個(gè)應(yīng)用OI File Manager(從谷歌應(yīng)用市場(chǎng)下載了版本2.0.5).EventRacer 檢測(cè)OI File Manager 后,報(bào)告了785 個(gè)數(shù)據(jù)競(jìng)爭(zhēng):一部分是發(fā)生在輸入事件之間(Race #352,Race#12),一部分發(fā)生在IPC 事件之間(Race #784,Race #8).這些數(shù)據(jù)競(jìng)爭(zhēng)數(shù)量比較多,但都沒(méi)有造成嚴(yán)重后果.

我們發(fā)現(xiàn),在OI File Manager 中存在由空引用(使用了已經(jīng)釋放的對(duì)象)所導(dǎo)致的有害數(shù)據(jù)競(jìng)爭(zhēng),但是EventRacer 沒(méi)有檢測(cè)出來(lái).圖3 展示了相關(guān)信息.類(lèi)MultiDeleteDialog 是一個(gè)Fragment,綁定在相應(yīng)的Activity并繼承了DialogFragment.它展現(xiàn)了一個(gè)界面,用戶(hù)可以進(jìn)行相應(yīng)的操作.當(dāng)用戶(hù)點(diǎn)擊確定按鈕,會(huì)創(chuàng)建一個(gè)異步執(zhí)行的任務(wù),即繼承了AsyncTask 的RecursiveDeleteTask 類(lèi).在執(zhí)行異步任務(wù)的過(guò)程中,主界面會(huì)初始化一個(gè)進(jìn)度框,顯示任務(wù)執(zhí)行的進(jìn)度.具體的執(zhí)行過(guò)程在方法doInBackground(?)中進(jìn)行.最后會(huì)在onPostExecute(?)方法中執(zhí)行dismiss(?)方法中止進(jìn)度框.但是如果用戶(hù)在任務(wù)執(zhí)行過(guò)程中,點(diǎn)擊回退按鈕,則可能造成數(shù)據(jù)競(jìng)爭(zhēng).

在真實(shí)場(chǎng)景下,由于用戶(hù)可在任何時(shí)刻按下回退按鈕(其他操作也可能觸發(fā)onDestory等回調(diào)函數(shù),這里僅以按下回退按鈕舉例),繼而onPause(?),onStop(?),onDestroy(?)回調(diào)方法會(huì)被調(diào)用銷(xiāo)毀Activity,繼而銷(xiāo)毀進(jìn)度框(進(jìn)度框是在嵌入在A(yíng)ctivity 上繪制的,彼此共享同一個(gè)共享變量window).因此,當(dāng)異步任務(wù)執(zhí)行完成進(jìn)而調(diào)用dismiss(?)方法銷(xiāo)毀進(jìn)度框時(shí),就會(huì)獲得一個(gè)空對(duì)象,進(jìn)而引發(fā)異常,導(dǎo)致應(yīng)用崩潰.

工具EventRacer 默認(rèn)使用工具AndroidMonkey(http://developer.android.com/tools/help/monkey.html)產(chǎn)生300 個(gè)隨機(jī)事件去觸發(fā)相應(yīng)的回調(diào)方法獲取執(zhí)行軌跡.這些隨機(jī)的事件只能覆蓋到應(yīng)用中一部分代碼.因此,EventRacer 會(huì)遺漏許多數(shù)據(jù)競(jìng)爭(zhēng),即存在漏報(bào).如果增加隨機(jī)事件的數(shù)量,則EventRacer 的性能會(huì)急劇下降.

Fig.3 Harmful data races in application OI File Manager圖3 應(yīng)用OI File Manager 中的有害數(shù)據(jù)競(jìng)爭(zhēng)

這個(gè)案例說(shuō)明了動(dòng)態(tài)分析技術(shù)的局限性,即現(xiàn)有的檢測(cè)工具存在漏報(bào)的問(wèn)題.為此,本文通過(guò)靜態(tài)分析去識(shí)別所有的疑似數(shù)據(jù)競(jìng)爭(zhēng)(符合數(shù)據(jù)競(jìng)爭(zhēng)第1 個(gè)條件),即在不同的線(xiàn)程中訪(fǎng)問(wèn)同一個(gè)共享變量的2 個(gè)語(yǔ)句.此階段會(huì)覆蓋所有的源碼,達(dá)到最大的覆蓋率.在此基礎(chǔ)上,依據(jù)安卓應(yīng)用中的發(fā)生序規(guī)則去檢查每個(gè)疑似數(shù)據(jù)競(jìng)爭(zhēng)是否有同步措施,通過(guò)將其上下文語(yǔ)句轉(zhuǎn)化為相應(yīng)的約束條件,編碼后放入Z3 求解器進(jìn)行計(jì)算,從而檢測(cè)出盡可能多的數(shù)據(jù)競(jìng)爭(zhēng),并對(duì)其中有害數(shù)據(jù)競(jìng)爭(zhēng)進(jìn)行分析.

3 檢測(cè)工具的設(shè)計(jì)與實(shí)現(xiàn)

本節(jié)首先概述工具RaceDetector 的構(gòu)成,繼而詳細(xì)描述各組成模塊:安卓共享變量分析、可疑的數(shù)據(jù)競(jìng)爭(zhēng)集合分析、約束求解.

3.1 概述

圖4 概述了工具RaceDetector的工作流程.頂部方框展示了處理模塊,底部的方框則展示了相應(yīng)輸入以及輸出的數(shù)據(jù)結(jié)構(gòu),虛線(xiàn)箭頭展現(xiàn)了輸入關(guān)系,實(shí)線(xiàn)的箭頭展現(xiàn)了輸出關(guān)系,最后的方框展現(xiàn)了工具RaceDetector 的輸出結(jié)果.在圖4(a)中,RaceDetector 使用工具SOOT(一個(gè)安卓代碼分析框架,支持別名分析、SSA 分析和Jimple格式)解析識(shí)別安卓應(yīng)用的APK 文件,進(jìn)而匹配識(shí)別相應(yīng)的語(yǔ)句.在圖4(b)中,主要進(jìn)行靜態(tài)分析,記錄相關(guān)的組件信息、進(jìn)程信息、共享變量信息和回調(diào)方法信息.根據(jù)圖4(b)中記錄的信息以及安卓框架的發(fā)生序規(guī)則,在圖4(c)中進(jìn)行約束條件的編碼.最后,在圖4(d)中使用z3 求解器去識(shí)別真正的數(shù)據(jù)競(jìng)爭(zhēng),并分析得出數(shù)據(jù)競(jìng)爭(zhēng)報(bào)告.

Fig.4 Workflow of RaceDetector圖4 RaceDetector 的工作流程

3.2 安卓線(xiàn)程共享變量分析

在并發(fā)程序中,導(dǎo)致數(shù)據(jù)競(jìng)爭(zhēng)的根本原因是沒(méi)有處理好對(duì)共享變量的讀寫(xiě)操作.對(duì)共享變量的操作進(jìn)行分析是先決條件,也是靜態(tài)解析的第1 步,其分析結(jié)果也是提高檢測(cè)性能和準(zhǔn)確性的關(guān)鍵[26].EventRacer、CAFA、DroidRacer 等工具根據(jù)逃逸分析[26]在執(zhí)行軌跡上進(jìn)行安卓線(xiàn)程共享變量分析.逃逸分析方法用于判斷一個(gè)分配的對(duì)象作用域是否逃逸出創(chuàng)建它的方法或線(xiàn)程,即一個(gè)變量的作用域是否在多個(gè)線(xiàn)程之間.但是一方面,這些工具是基于執(zhí)行軌跡,有著其動(dòng)態(tài)執(zhí)行固有的低覆蓋率問(wèn)題;另一方面,傳統(tǒng)逃逸分析的局限性也影響其性能.

(1)一個(gè)線(xiàn)程逃逸的對(duì)象可能不會(huì)被多個(gè)線(xiàn)程訪(fǎng)問(wèn),例如靜態(tài)變量通常被視為逃逸的,但是大部分靜態(tài)變量只被訪(fǎng)問(wèn)在當(dāng)前線(xiàn)程中.

(2)一個(gè)對(duì)象是線(xiàn)程逃逸的并不意味著所有與此對(duì)象相關(guān)的數(shù)據(jù)都是共享的.

(3)一個(gè)線(xiàn)程逃逸的對(duì)象可能是不可變的,因?yàn)樵诔跏蓟?沒(méi)有語(yǔ)句對(duì)它進(jìn)行寫(xiě)操作.

因此,傳統(tǒng)逃逸分析中所定義的共享變量,在實(shí)際情況下,有一些共享變量并沒(méi)有真正被多個(gè)線(xiàn)程訪(fǎng)問(wèn).因此,合理優(yōu)化共享變量分析的方法,識(shí)別出真正被多個(gè)線(xiàn)程共同訪(fǎng)問(wèn)的共享變量,不僅能提高準(zhǔn)確性,而且能夠降低工具分析問(wèn)題的復(fù)雜性.

共享變量是指一個(gè)變量的作用域超出定義這個(gè)變量的所在線(xiàn)程.在安卓應(yīng)用中,除常規(guī)意義下的共享變量外,還需擴(kuò)展Java 語(yǔ)言中的線(xiàn)程共享類(lèi)型,以覆蓋安卓應(yīng)用特有場(chǎng)景.若符合以下情況之一,均為安卓共享變量.

(1)View 和Component:用來(lái)定義UI 界面的組件,例如TextView、EditText、ImageView 等.

(2)Window(窗口):在此基礎(chǔ)上定義了可視化的界面,例如Activity、Dialog 和Toast,它們共享同一個(gè)變量window.因此,當(dāng)Activity 被銷(xiāo)毀時(shí),Dialog 和Toast 也同樣會(huì)被銷(xiāo)毀.

(3)數(shù)據(jù)存儲(chǔ):包括Internet、SharedPreference、Sqlite、Content Provider 和SD card.

安卓共享變量給出了在安卓中可以在多個(gè)線(xiàn)程之間共享的變量類(lèi)型,但是在實(shí)際情形中,可以在多個(gè)線(xiàn)程之間共享的變量很多,而真正在多個(gè)線(xiàn)程之間共享的變量的數(shù)據(jù)則很少.因此降低共享變量的分析空間,識(shí)別出真正在多個(gè)線(xiàn)程之間共享的變量,有助于提高整體的性能.

定義1(安卓線(xiàn)程共享變量分析(ATSA)).在安卓應(yīng)用中,對(duì)共享變量的操作即為安卓線(xiàn)程共享變量分析(決定安卓應(yīng)用中程序語(yǔ)句是否讀取或?qū)懭胍粋€(gè)線(xiàn)程共享數(shù)據(jù)).在安卓應(yīng)用中,變量v定義在線(xiàn)程T中,如果v的作用域D超出線(xiàn)程T,則認(rèn)為變量v是線(xiàn)程可共享變量.如果存在2 個(gè)語(yǔ)句s1和s2,在不同的線(xiàn)程t1和t2中對(duì)變量v進(jìn)行訪(fǎng)問(wèn),并且有一個(gè)為WRITE 操作,則認(rèn)為該變量是線(xiàn)程真實(shí)共享變量.從可共享變量中獲取真實(shí)共享變量的過(guò)程,稱(chēng)為安卓線(xiàn)程共享變量分析.

具體操作時(shí),使用工具SOOT 解決Java 語(yǔ)言的別名問(wèn)題,并且基于三地址碼格式的Jimple 語(yǔ)句,可識(shí)別每一個(gè)語(yǔ)句的變量讀寫(xiě)情況.因此,使用SOOT 首先獲取所有的可共享變量,在解析源碼時(shí),使用全局的Map 記錄對(duì)可共享變量進(jìn)行讀寫(xiě)操作的線(xiàn)程和語(yǔ)句信息,用于標(biāo)記;繼而集成靜態(tài)優(yōu)化算法到傳統(tǒng)的逃逸分析中[26],并識(shí)別安卓特有的場(chǎng)景,然后過(guò)濾掉并沒(méi)有真正在多個(gè)線(xiàn)程之間傳遞的共享變量,從而獲取真實(shí)共享變量的集合.具體過(guò)程如算法1 所示.

算法1.安卓線(xiàn)程共享變量分析(ATSA).

定義2.線(xiàn)程真實(shí)共享變量TSO={O1,O2,O3,…,On},n是線(xiàn)程共享對(duì)象的數(shù)量.TSO中的每一個(gè)對(duì)象是一個(gè)四元組:O=〈o,ID,ClassName,Type〉,ID唯一標(biāo)識(shí)了真實(shí)共享變量對(duì)象o,ClassName信息定義了該共享變量o所處的線(xiàn)程信息,Type信息則定義了該對(duì)象o的類(lèi)型(View、Window、數(shù)據(jù)存儲(chǔ)或傳統(tǒng)線(xiàn)程等).例如,在圖2 的示例OI File Manager 中,真實(shí)共享變量為O1=〈window,ID(獨(dú)特整數(shù)標(biāo)識(shí)),RecursiveDeleteTask(AsyncTask),Window〉.

3.3 可疑的數(shù)據(jù)競(jìng)爭(zhēng)候選者集合

上文根據(jù)數(shù)據(jù)競(jìng)爭(zhēng)第1 個(gè)條件去獲取可疑的數(shù)據(jù)競(jìng)爭(zhēng)候選者集合.本節(jié)首先對(duì)真實(shí)共享變量進(jìn)行讀寫(xiě)分析,針對(duì)每一個(gè)真實(shí)共享變量,得出對(duì)該真實(shí)共享變量進(jìn)行讀寫(xiě)的回調(diào)方法集合.

讀寫(xiě)函數(shù)集合FS=〈F1,F2,…,Fm〉,m為FS集合中語(yǔ)句的數(shù)量.F為一個(gè)四元組:

?f是對(duì)真實(shí)共享變量o進(jìn)行讀寫(xiě)操作的回調(diào)方法,在該回調(diào)方法中,存在多次對(duì)真實(shí)共享變量o進(jìn)行讀寫(xiě)操作的語(yǔ)句.

?ID和ClassName分別定義了讀寫(xiě)函數(shù)的唯一標(biāo)簽和讀寫(xiě)函數(shù)所處的線(xiàn)程類(lèi)信息.

?SourceEvent是一個(gè)輸入事件,觸發(fā)了該回調(diào)方法的執(zhí)行,通過(guò)逆向查找匹配確定,即在確定觸發(fā)該回調(diào)函數(shù)的用戶(hù)輸入事件時(shí),如果是用戶(hù)輸入事件,會(huì)事先注冊(cè)事件監(jiān)聽(tīng)(每個(gè)Event 都有對(duì)應(yīng)的Listener),通過(guò)Listener 關(guān)聯(lián)到回調(diào)函數(shù),將可能的情況一起放在列表中,然后逐一確認(rèn).

具體到例子OI File Manager,存在兩個(gè)F,分別為F1=〈onDestroy,ID1,MultiDeleteDialog(Activity),back〉,F2=〈onPostExecute,ID2,RecursiveDeleteTask(AsyncTask),Button.onClick〉.針對(duì)每一個(gè)真實(shí)共享變量o,對(duì)應(yīng)著多個(gè)對(duì)它進(jìn)行讀寫(xiě)操作的回調(diào)函數(shù)F.為此,給出了定義3 來(lái)表示這種關(guān)系.

定義3.函數(shù)活動(dòng)FA=〈TID,F,O,H〉.回調(diào)方法F.f產(chǎn)生于F.SourceEvent,在TID標(biāo)志的線(xiàn)程中,對(duì)共享變量O.o執(zhí)行讀寫(xiě)操作H(READ,WRITE),由此產(chǎn)生了函數(shù)活動(dòng)集合.具體到OI File Manager,函數(shù)活動(dòng)對(duì)為FA1=〈TID1,F1,O1,WRITE〉和FA2=〈TID2,F2,O1,READ〉.然后,根據(jù)定義4 疑似數(shù)據(jù)競(jìng)爭(zhēng)判定規(guī)則,即數(shù)據(jù)競(jìng)爭(zhēng)定義的第1個(gè)競(jìng)爭(zhēng)條件,最終識(shí)別出可疑數(shù)據(jù)競(jìng)爭(zhēng)候選者集合.

定義4(疑似數(shù)據(jù)競(jìng)爭(zhēng)判定規(guī)則).若FAi=FA(TIDi,Fi,Oi,Hi)∧FAj=FA(TIDj,Fj,Oj,Hj)∧TIDi!=TIDj∧Oi=Oj∧(Hi=WRITE∨Hj=WRITE),即〈FAi,FAj〉發(fā)生在多線(xiàn)程之間,則為疑似多線(xiàn)程數(shù)據(jù)競(jìng)爭(zhēng);若〈FAi,FAj〉發(fā)生在一個(gè)線(xiàn)程和相關(guān)的監(jiān)聽(tīng)者之間并滿(mǎn)足上述條件,則為疑似單線(xiàn)程數(shù)據(jù)競(jìng)爭(zhēng).

由此產(chǎn)生數(shù)據(jù)競(jìng)爭(zhēng)候選者集合Data Race Candidate Set(CS),CS的每一個(gè)元素是一個(gè)函數(shù)活動(dòng)對(duì)〈FAi,FAj〉,如OI File Manager 的〈FAi,FAj〉,這個(gè)函數(shù)活動(dòng)對(duì)發(fā)生在主Activity 線(xiàn)程和相對(duì)應(yīng)的Listener 之間,且滿(mǎn)足定義4,因此為單線(xiàn)程數(shù)據(jù)競(jìng)爭(zhēng).

3.4 約束求解

安卓應(yīng)用中的發(fā)生序關(guān)系(happens-before,簡(jiǎn)稱(chēng)HB)形成了語(yǔ)句之間執(zhí)行的約束關(guān)系[18,27,28].文獻(xiàn)[10]首次把HB 關(guān)系應(yīng)用到安卓系統(tǒng)中,文獻(xiàn)[9]擴(kuò)展了HB 關(guān)系.它們基于安卓應(yīng)用中的HB 關(guān)系構(gòu)造全局的HB 關(guān)系圖,進(jìn)而去診斷2 個(gè)共享變量讀寫(xiě)操作是否滿(mǎn)足HB 關(guān)系.這些方法是基于動(dòng)態(tài)執(zhí)行的路徑構(gòu)造HB 關(guān)系圖,覆蓋率低.如果構(gòu)建全局HB 關(guān)系圖,則會(huì)嚴(yán)重影響性能.

得到包含相應(yīng)的共享變量、線(xiàn)程ID、方法語(yǔ)句、讀寫(xiě)操作等信息的可疑的數(shù)據(jù)競(jìng)爭(zhēng)集合之后,根據(jù)這些信息進(jìn)行約束編碼,借助求解器生成所有可能的線(xiàn)程調(diào)度方案,從而找出真正的數(shù)據(jù)競(jìng)爭(zhēng).對(duì)每一個(gè)可疑數(shù)據(jù)競(jìng)爭(zhēng)候選者,基于它們的上下文構(gòu)造局部HB 關(guān)系圖,能夠輕量地檢測(cè)到盡可能多的數(shù)據(jù)競(jìng)爭(zhēng).

針對(duì)安卓應(yīng)用事件(指除去SDK 提供的已有規(guī)則確定事件外的用戶(hù)事件和其他事件)回調(diào)方法,有定義5.

定義5(事件回調(diào)方法之間的次序關(guān)系).

(1)同一個(gè)事件產(chǎn)生的多個(gè)回調(diào)方法之間是有序的.

(2)不同事件產(chǎn)生的回調(diào)方法之間是沒(méi)有HB 關(guān)系的.

(3)事件的觸發(fā)會(huì)調(diào)用相應(yīng)的回調(diào)方法.然而事件的觸發(fā)是不可預(yù)計(jì)的,因此事件之間是沒(méi)有HB 關(guān)系的,事件所對(duì)應(yīng)的回調(diào)方法之間也沒(méi)有HB 關(guān)系.

因此,對(duì)于可疑的數(shù)據(jù)競(jìng)爭(zhēng)候選者〈FAi,FAj〉,由于它們的觸發(fā)事件不同,FAi和FAj之間是沒(méi)有HB 關(guān)系的.因此,如果沒(méi)有額外的同步機(jī)制,則FAi和FAj可能引發(fā)數(shù)據(jù)競(jìng)爭(zhēng).我們使用約束求解的方法來(lái)識(shí)別FAi,FAj的上下文中是否有額外的同步措施.

約束編碼廣泛應(yīng)用在程序中數(shù)據(jù)競(jìng)爭(zhēng)的檢測(cè)、再現(xiàn)和修復(fù)[29-31].基于安卓平臺(tái)以及事件驅(qū)動(dòng)特性和多線(xiàn)程模型,本文提出了以下相關(guān)約束:變量約束、條件約束、讀寫(xiě)約束、數(shù)據(jù)競(jìng)爭(zhēng)約束、同步約束.這些約束模擬了所有Java 語(yǔ)言程序語(yǔ)句的特性.首先給出約束系統(tǒng)的基本概念.

(2)符號(hào)變量Ok表示語(yǔ)句k的調(diào)度順序.

變量約束定義了賦值語(yǔ)句和定義語(yǔ)句中對(duì)共享變量的讀寫(xiě)約束.針對(duì)共享變量x,位置i語(yǔ)句x=v,表示為;語(yǔ)句x=y在i位置,并且y變量定義在j位置,表示為;語(yǔ)句z=x⊕y(⊕表示標(biāo)準(zhǔn)的二元運(yùn)算符,例如加減乘除等),x定義在位置j,y定義在位置k,語(yǔ)句發(fā)生在位置i,表示為zi=xi⊕yi∧xi=xj∧yi=yk.

條件約束定義了條件語(yǔ)句中的約束情況.對(duì)于語(yǔ)句if(z),會(huì)檢查條件z的值,進(jìn)而去判斷相關(guān)的分支語(yǔ)句塊是否被執(zhí)行,表示為:z∧z是一個(gè)條件語(yǔ)句.

讀寫(xiě)約束定義了所有對(duì)共享變量進(jìn)行讀寫(xiě)操作的語(yǔ)句約束情況.對(duì)于一個(gè)共享變量x,讀操作所得到的值等于之前最近一次對(duì)x寫(xiě)操作寫(xiě)入的值.因此,如果位置i讀取的值等于位置j寫(xiě)入的值,則(Oj?Oi),并且對(duì)于位置k對(duì)x的寫(xiě)操作,則有(Ok?Oj)或者(Oi?Ok).表示為

數(shù)據(jù)競(jìng)爭(zhēng)約束定義了兩個(gè)特殊的語(yǔ)句次序約束,這兩個(gè)語(yǔ)句共享同一個(gè)共享變量,并可能導(dǎo)致數(shù)據(jù)競(jìng)爭(zhēng)的發(fā)生.對(duì)于語(yǔ)句i和j,如果它們?cè)L問(wèn)同一個(gè)共享變量,并且其中一個(gè)是寫(xiě)操作.同時(shí)我們想去確定這兩個(gè)語(yǔ)句之間有沒(méi)有HB 關(guān)系.定義其數(shù)據(jù)競(jìng)爭(zhēng)約束為.

同步約束包括線(xiàn)程內(nèi)同步、鎖同步、Start/Join/Wait/Notify約束以及安卓中特殊的同步方法,具體介紹如下.

(1)線(xiàn)程內(nèi)同步:同一個(gè)線(xiàn)程中,所有的語(yǔ)句都是順序執(zhí)行的,表示為O1?O2?…?On.

(3)Start/Join/Wait/Notify約束:Start/Join/Wait/Notify是Java 語(yǔ)言中用于同步線(xiàn)程常用的操作,Start的操作用于開(kāi)啟運(yùn)行一個(gè)新的線(xiàn)程,Join操作用于通知該線(xiàn)程已經(jīng)執(zhí)行完畢;Wait操作用于等待獲取一個(gè)鎖,Notify操作用于通知已經(jīng)釋放了鎖.因此,表示為Start?Join,Wait?Notify.

(4)安卓中特殊的同步:對(duì)安卓HB 規(guī)則約束編碼,對(duì)于兩個(gè)語(yǔ)句i,j,如果它們遵循HB 規(guī)則,有Oi?Oj.

例如,我們會(huì)檢查如下線(xiàn)程間同步機(jī)制:startActivity,startService,AsyncTask.execute,addListener等,并用methodinit(m),methodexit(m)表示開(kāi)始執(zhí)行當(dāng)前方法和已經(jīng)執(zhí)行完畢當(dāng)前方法.

對(duì)所有的語(yǔ)句進(jìn)行約束編碼之后,將得到關(guān)于可疑數(shù)據(jù)競(jìng)爭(zhēng)候選者的約束文件.約束文件中,首先,對(duì)約束變量進(jìn)行定義;其次,根據(jù)以上規(guī)則對(duì)數(shù)據(jù)競(jìng)爭(zhēng)候選者的上下文語(yǔ)句進(jìn)行編碼;最后,將約束文件放入Z3solver(https://z3.codeplex.com/)中去檢測(cè)是否有解,從而去識(shí)別真正的數(shù)據(jù)競(jìng)爭(zhēng).

具體到本文示例OI File Manager,首先,通過(guò)線(xiàn)程共享變量分析,可以定位到共享變量window,根據(jù)共享變量相關(guān)的上下文以及其讀寫(xiě)集合,可以得到兩個(gè)事件回調(diào)方法onDestroy(?)和onPostExecute(?),對(duì)這兩個(gè)回調(diào)方法對(duì)語(yǔ)句進(jìn)行約束編碼.具體到super.onDestroy(?)和dialog.dismiss(?),可以得出window(write)=null和y=window(read);同時(shí),設(shè)定它們的調(diào)度序列O1,O2.針對(duì)數(shù)據(jù)競(jìng)爭(zhēng)約束條件,可以將此編碼為O1=O2,然后把兩個(gè)語(yǔ)句相關(guān)的約束語(yǔ)句和數(shù)據(jù)競(jìng)爭(zhēng)約束O1=O2輸出到一個(gè)約束文件中,并放入Z3 求解器中進(jìn)行求解,去判斷數(shù)據(jù)競(jìng)爭(zhēng)約束在安卓并發(fā)語(yǔ)義的Happens-Before 規(guī)則下面是否真實(shí)發(fā)生,即在所有的事件調(diào)度和線(xiàn)程調(diào)度解空間中是否有解.如果有解,則認(rèn)定它們?yōu)閿?shù)據(jù)競(jìng)爭(zhēng).

4 實(shí)驗(yàn)分析

本節(jié)主要介紹工具RaceDetector 的實(shí)現(xiàn)、數(shù)據(jù)集、實(shí)驗(yàn)及其結(jié)果分析,并結(jié)合案例討論與現(xiàn)有工具的異同.

4.1 工具RaceDetector的實(shí)現(xiàn)

本文使用Java 語(yǔ)言實(shí)現(xiàn)了工具RaceDetector.靜態(tài)分析模塊通過(guò)靜態(tài)解析整個(gè)安卓應(yīng)用APK 文件來(lái)大幅度地提高源代碼的覆蓋率.這里使用SOOT 工具將APK 文件轉(zhuǎn)換為三地址碼(Jimple 格式)的簡(jiǎn)單語(yǔ)義文件,繼而進(jìn)行安卓應(yīng)用線(xiàn)程共享變量分析,并優(yōu)化了傳統(tǒng)的逃逸分析算法(第4.2 節(jié)).根據(jù)線(xiàn)程共享變量,得出該共享變量的讀寫(xiě)語(yǔ)句集合,從而得出數(shù)據(jù)競(jìng)爭(zhēng)候選者集合(第4.3 節(jié)).在約束求解模塊中,我們根據(jù)安卓應(yīng)用的先后序關(guān)系規(guī)則對(duì)疑似數(shù)據(jù)競(jìng)爭(zhēng)對(duì)應(yīng)的兩個(gè)代碼片段進(jìn)行約束編碼,得到一個(gè)定義了兩個(gè)代碼片段發(fā)生序關(guān)系的約束文件,并通過(guò)Z3 求解器求解,判斷有數(shù)據(jù)競(jìng)爭(zhēng)約束的兩個(gè)語(yǔ)句是否有HB 關(guān)系,從而找到真正的數(shù)據(jù)競(jìng)爭(zhēng).

本文借助了兩個(gè)輔助工具——SOOT 和Z3 求解器.

?SOOT 是一個(gè)可以分析安卓應(yīng)用程序的框架平臺(tái),能夠?qū)沧繎?yīng)用的APK 文件解析為三地址碼格式.SOOT 還提供了別名分析和數(shù)據(jù)流分析等常用的靜態(tài)分析方法.SOOT 工具的API 可以識(shí)別安卓應(yīng)用每一個(gè)類(lèi)的信息、屬性信息、方法信息以及類(lèi)與類(lèi)之間、方法與方法之間的調(diào)用信息,從而可以進(jìn)行線(xiàn)程共享變量分析和疑似數(shù)據(jù)競(jìng)爭(zhēng)分析.

?Z3 求解器是一個(gè)在廣泛的解空間中檢測(cè)某些約束條件是否有解的工具.它接受一系列的約束條件作為輸入.這些約束條件定義了相關(guān)變量之間的關(guān)系.針對(duì)數(shù)據(jù)競(jìng)爭(zhēng)的約束文件,Z3 求解器輸出SAT,表明兩個(gè)包含數(shù)據(jù)競(jìng)爭(zhēng)約束條件的語(yǔ)句并沒(méi)有違反安卓應(yīng)用中的先后序關(guān)系規(guī)則,也即這兩個(gè)語(yǔ)句之間沒(méi)有先后序關(guān)系,因此它們是數(shù)據(jù)競(jìng)爭(zhēng).

4.2 數(shù)據(jù)集

本文根據(jù)以下標(biāo)準(zhǔn)挑選出了15 個(gè)流行的App 作為數(shù)據(jù)集.

(1)廣泛流行.這些App 來(lái)自Google Play Store 排行榜的前列,或者來(lái)自于其他論文中的數(shù)據(jù)集[8-10].

(2)不同的類(lèi)別,包含了媒體、工具到社交、新聞等類(lèi)別.

(3)不同的大小,小的有8k 多行,大的有400k 多行(這里是按照J(rèn)imple 格式顯示的代碼行).

表1 展示了這些App 的相關(guān)信息,按照J(rèn)imple 格式代碼行的大小,從小到大進(jìn)行排列.表1 的第2 列是代碼行數(shù).第3 列展示了每一個(gè)App 中的線(xiàn)程共享變量,斜線(xiàn)左邊的是可共享變量的數(shù)目,右邊是經(jīng)過(guò)ATSA 實(shí)際得出的、真實(shí)的共享變量數(shù)目.可以看出,線(xiàn)程可共享變量廣泛存在于A(yíng)pp 中,數(shù)量從幾百到幾千不等.但是真實(shí)共享變量數(shù)目遠(yuǎn)遠(yuǎn)小于可共享變量數(shù)目.第4 列～第7 列分別是安卓應(yīng)用的活動(dòng)、服務(wù)、異步任務(wù)和線(xiàn)程的數(shù)量信息.這些信息展現(xiàn)了每一個(gè)應(yīng)用中的線(xiàn)程數(shù)量:安卓應(yīng)用中,每一個(gè)活動(dòng)都運(yùn)行在主線(xiàn)程;每一個(gè)服務(wù)代表了一個(gè)在后臺(tái)執(zhí)行的任務(wù);AsyncTask 是安卓應(yīng)用中發(fā)起異步執(zhí)行任務(wù)的框架;Thread 則是傳統(tǒng)的Java 語(yǔ)言線(xiàn)程.最后一列是監(jiān)聽(tīng)器Listener 的數(shù)目,每個(gè)監(jiān)聽(tīng)器Listener 會(huì)監(jiān)聽(tīng)相應(yīng)的輸入事件,并引發(fā)一個(gè)或者多個(gè)回調(diào)函數(shù)的執(zhí)行.

由此可見(jiàn),大小應(yīng)用中均存在多線(xiàn)程運(yùn)行的場(chǎng)景,即多線(xiàn)程在安卓應(yīng)用中是普遍存在的.每個(gè)應(yīng)用都有相應(yīng)的監(jiān)聽(tīng)者,對(duì)應(yīng)著各種輸入事件,并且輸入事件的類(lèi)型多且復(fù)雜.因此,輸入事件的不可預(yù)期性、無(wú)序性以及相互之間的調(diào)度也是數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題產(chǎn)生的原因.

Table 1 Information statistics of data set表1 數(shù)據(jù)集信息統(tǒng)計(jì)

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

本文實(shí)驗(yàn)均使用處理器為Intel Core i5-4570 3.20GHz、內(nèi)存為8GB、操作系統(tǒng)為64 位Windows 7 專(zhuān)業(yè)版的計(jì)算機(jī)所完成.實(shí)驗(yàn)工具由Java 語(yǔ)言來(lái)實(shí)現(xiàn),使用的開(kāi)發(fā)環(huán)境為JDK 7.0,使用的IDE 為Eclipse Kepler.靜態(tài)分析部分的功能使用了SOOT 工具輔助,約束求解部分使用了Z3 求解器.表2 展示了相應(yīng)的實(shí)驗(yàn)結(jié)果.

Table 2 Information statistics of experimental results表2 實(shí)驗(yàn)結(jié)果信息統(tǒng)計(jì)

表2 的第2 列展現(xiàn)了工具的執(zhí)行時(shí)間,包括線(xiàn)程共享變量分析的時(shí)間、約束編碼的時(shí)間和求解器求解的時(shí)間.可以看出,工具的執(zhí)行時(shí)間隨著應(yīng)用大小近似線(xiàn)性增長(zhǎng).對(duì)于小的應(yīng)用,RaceDetector 基本都在1min 內(nèi)完成任務(wù).執(zhí)行時(shí)間最短的應(yīng)用是Tomdroid,僅需要6.3s.在表2 的底部區(qū)域,對(duì)于大的應(yīng)用來(lái)說(shuō),執(zhí)行時(shí)間幾乎都超過(guò)了1min,最慢的應(yīng)用是Pandora,其執(zhí)行時(shí)間超過(guò)了3min.除此以外,我們發(fā)現(xiàn)執(zhí)行時(shí)間也受到共享變量、數(shù)據(jù)競(jìng)爭(zhēng)候選者數(shù)目的影響,例如,Instagram 是15 個(gè)應(yīng)用中最大的,與Pandora 相比,其執(zhí)行時(shí)間少了近1min.這是因?yàn)樗臄?shù)據(jù)競(jìng)爭(zhēng)候選者數(shù)目(42)遠(yuǎn)小于Pandora 的候選者數(shù)目(239).另外我們發(fā)現(xiàn),約束求解執(zhí)行的時(shí)間平均在1min 左右,約束編碼占據(jù)了大部分時(shí)間.這是因?yàn)槲覀儼讶值南群笮蜿P(guān)系約束分解為針對(duì)每一個(gè)候選者的約束文件,有效降低了約束求解的執(zhí)行時(shí)間.隨著候選者數(shù)量的增多,約束求解執(zhí)行的時(shí)間也隨之增長(zhǎng).

表2 的第3 列是經(jīng)過(guò)ATSA 分析過(guò)后得到的實(shí)際情況下線(xiàn)程間共享變量的數(shù)目.在安卓應(yīng)用中,開(kāi)發(fā)人員經(jīng)常會(huì)定義作用域超出自身所在線(xiàn)程或者自身所在類(lèi)別的對(duì)象,但是實(shí)際情況下,真正能夠被多線(xiàn)程共同訪(fǎng)問(wèn)的共享變量數(shù)目是極少的.因此,優(yōu)化后的ATSA 分析方法極大地降低了需要分析的共享變量數(shù)目,減少了程序的空間消耗和時(shí)間消耗.

表2 的第4 列是可疑的數(shù)據(jù)競(jìng)爭(zhēng)候選者(函數(shù)對(duì))數(shù)目,對(duì)照表2 的第3 列可以看出,可疑的數(shù)據(jù)競(jìng)爭(zhēng)候選者數(shù)目大于線(xiàn)程共享變量的數(shù)目,即每一個(gè)線(xiàn)程共享變量會(huì)存在多個(gè)數(shù)據(jù)競(jìng)爭(zhēng)候選者.因此,會(huì)存在許多個(gè)線(xiàn)程或者Listener 共同訪(fǎng)問(wèn)同一個(gè)共享變量.每一個(gè)數(shù)據(jù)競(jìng)爭(zhēng)候選者對(duì)應(yīng)一個(gè)函數(shù)對(duì),符合數(shù)據(jù)競(jìng)爭(zhēng)定義的第1 個(gè)數(shù)據(jù)競(jìng)爭(zhēng)條件,針對(duì)每一個(gè)函數(shù)對(duì),我們會(huì)產(chǎn)生一個(gè)約束文件,并放入求解器中進(jìn)行求解.

表2 的第5 列～第8 列展現(xiàn)了具體檢查出的數(shù)據(jù)競(jìng)爭(zhēng)結(jié)果.本文將數(shù)據(jù)競(jìng)爭(zhēng)分類(lèi)成單線(xiàn)程數(shù)據(jù)競(jìng)爭(zhēng)和多線(xiàn)程數(shù)據(jù)競(jìng)爭(zhēng),并識(shí)別出其中有害的數(shù)據(jù)競(jìng)爭(zhēng)(第8 列).根據(jù)實(shí)驗(yàn)結(jié)果,可以得出以下結(jié)論.

(1)相對(duì)于安卓應(yīng)用中的單線(xiàn)程數(shù)據(jù)競(jìng)爭(zhēng),多線(xiàn)程數(shù)據(jù)競(jìng)爭(zhēng)的數(shù)目更多.

(2)每個(gè)函數(shù)對(duì)代表了針對(duì)一個(gè)共享變量的約束文件,平均每個(gè)約束變量都會(huì)引發(fā)5 個(gè)以上的數(shù)據(jù)競(jìng)爭(zhēng).

(3)在數(shù)據(jù)競(jìng)爭(zhēng)中,我們關(guān)心的有害數(shù)據(jù)競(jìng)爭(zhēng)(空引用)僅占據(jù)很小的比例.

(4)針對(duì)每個(gè)應(yīng)用,RaceDetector 平均報(bào)告了340 個(gè)數(shù)據(jù)競(jìng)爭(zhēng).針對(duì)應(yīng)用Pandora 檢測(cè)到的數(shù)據(jù)競(jìng)爭(zhēng)最多,達(dá)到1 939.結(jié)合表1 和表2 可以看出,Pandora 應(yīng)用使用了大量的線(xiàn)程并發(fā)執(zhí)行代碼.

表2 的最后一列展現(xiàn)了誤報(bào)的數(shù)據(jù)競(jìng)爭(zhēng)的數(shù)目,平均的誤報(bào)率為13%(44/340).誤報(bào)的數(shù)據(jù)競(jìng)爭(zhēng)數(shù)目是通過(guò)實(shí)驗(yàn)過(guò)后人工審查分析得出的結(jié)果.我們對(duì)這些誤報(bào)的數(shù)據(jù)競(jìng)爭(zhēng)特性進(jìn)行了總結(jié),具體原因分析如下.

(1)一些數(shù)據(jù)競(jìng)爭(zhēng)發(fā)生在用戶(hù)代碼和安卓系統(tǒng)API 調(diào)用之間,表現(xiàn)為多個(gè)線(xiàn)程共同訪(fǎng)問(wèn)同一個(gè)共享變量,訪(fǎng)問(wèn)的語(yǔ)句直接或間接調(diào)用系統(tǒng)API.我們認(rèn)為:這些數(shù)據(jù)競(jìng)爭(zhēng)對(duì)線(xiàn)程共享變量進(jìn)行了讀或?qū)懙牟僮?沒(méi)有同步措施.而真實(shí)情況是,系統(tǒng)API 對(duì)線(xiàn)程共享變量已采取了相應(yīng)的同步措施.由于本文未解析安卓API 代碼,因此產(chǎn)生誤報(bào).

(2)單線(xiàn)程數(shù)據(jù)競(jìng)爭(zhēng)往往發(fā)生在活動(dòng)Activity 和與相關(guān)的Listener 所觸發(fā)的回調(diào)方法之間,但只有當(dāng)活動(dòng)處于前端時(shí),用戶(hù)才可執(zhí)行交互;同時(shí),工作線(xiàn)程不能改變主進(jìn)程UI 組件的狀態(tài).具體展現(xiàn)的是在某些Listener 所監(jiān)聽(tīng)的事件處于活動(dòng)進(jìn)行前后臺(tái)切換情況下,處于前端的Activity 會(huì)轉(zhuǎn)入后臺(tái),并觸發(fā)調(diào)用一些回調(diào)方法進(jìn)行資源的釋放和銷(xiāo)毀.在實(shí)驗(yàn)中,我們未覆蓋到相關(guān)事件類(lèi)型所導(dǎo)致的額外回調(diào)方法的執(zhí)行,因此產(chǎn)生誤報(bào).

(3)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)階段所使用的Happens-Before 規(guī)則和安卓應(yīng)用的并發(fā)語(yǔ)義是基于前人的相關(guān)工作,但是隨著安卓系統(tǒng)的發(fā)展和更新,Happens-Before 規(guī)則和并發(fā)語(yǔ)義并沒(méi)有全方位覆蓋到.因此在實(shí)際排查中,我們發(fā)現(xiàn)具體實(shí)驗(yàn)過(guò)程中會(huì)遺漏一些Happens-Before 規(guī)則.

4.4 案例討論

表1 已列出的線(xiàn)程類(lèi)型有5 種:活動(dòng)(activity)、服務(wù)(service)、Thread、AsyncTask、Listener.我們進(jìn)一步統(tǒng)計(jì)了不同線(xiàn)程類(lèi)型之間的數(shù)據(jù)競(jìng)爭(zhēng),詳見(jiàn)表3.

Table 3 Information statistics of data race types表3 數(shù)據(jù)競(jìng)爭(zhēng)類(lèi)型信息統(tǒng)計(jì)

在所定義的數(shù)據(jù)競(jìng)爭(zhēng)中,數(shù)據(jù)競(jìng)爭(zhēng)可以發(fā)生在不同的線(xiàn)程之間.由于安卓應(yīng)用存在多種類(lèi)型的線(xiàn)程框架,根據(jù)發(fā)生數(shù)據(jù)競(jìng)爭(zhēng)所在的兩個(gè)線(xiàn)程的不同類(lèi)型,具體有8 個(gè)類(lèi)型:Act-Lis、Act-ST、Act-Async、ST-ST、ST-Async、ST-Lis、Async-Async、Async-Lis(Act:Activity,ST:Service 或者 Threads,Async:AsyncTask,Lis:Listener).因?yàn)锳syncTask、Service 和Thread 可以運(yùn)行在后臺(tái),而Listeners 一部分與Activity 綁定,一部分與Sensor 綁定.

表3 表明,Activity、Service、Listener 間的數(shù)據(jù)競(jìng)爭(zhēng)占據(jù)很大比例,數(shù)據(jù)競(jìng)爭(zhēng)大多集中在A(yíng)ct-Lis、Act-ST、ST-ST、ST-Lis 這幾個(gè)類(lèi)型,說(shuō)明了Listener 執(zhí)行的不可預(yù)計(jì)性.我們選取數(shù)據(jù)集中的3 個(gè)應(yīng)用進(jìn)行案例討論.

?OI File Manager

在表2 中,RaceDetector 報(bào)告了11 個(gè)數(shù)據(jù)競(jìng)爭(zhēng),其中有8 個(gè)有害數(shù)據(jù)競(jìng)爭(zhēng).它們發(fā)生在A(yíng)ctivity 和AsyncTask之間.當(dāng)Activity 正在執(zhí)行異步任務(wù)時(shí),會(huì)訪(fǎng)問(wèn)一個(gè)Dialog,這時(shí)用戶(hù)可能按下回退按鈕中止Activiy,同時(shí)中止相應(yīng)的Dialog.這樣,正在進(jìn)行異步任務(wù)的AsyncTask 訪(fǎng)問(wèn)Dialog 時(shí)會(huì)獲取一個(gè)null 值,從而導(dǎo)致有害數(shù)據(jù)競(jìng)爭(zhēng)的發(fā)生.

?Connectbot

數(shù)據(jù)競(jìng)爭(zhēng)發(fā)生在A(yíng)ctivity 和Listener 之間.這個(gè)應(yīng)用里,一個(gè)數(shù)據(jù)庫(kù)用來(lái)存儲(chǔ)數(shù)據(jù),相應(yīng)Listener 會(huì)監(jiān)聽(tīng)數(shù)據(jù)庫(kù)狀態(tài),從而會(huì)更新數(shù)據(jù)競(jìng)爭(zhēng)的狀態(tài).大部分?jǐn)?shù)據(jù)競(jìng)爭(zhēng)發(fā)生在A(yíng)ctivity 和Listener 的回調(diào)方法之間,多數(shù)為讀取數(shù)據(jù)庫(kù)狀態(tài)的操作,其中存在兩個(gè)有害數(shù)據(jù)競(jìng)爭(zhēng),都涉及到了對(duì)數(shù)據(jù)庫(kù)的寫(xiě)操作或者對(duì)數(shù)據(jù)庫(kù)進(jìn)行銷(xiāo)毀的操作,具體發(fā)生在A(yíng)ctivity 的onStop(?)方法和Listener 的回調(diào)方法之間.一旦用戶(hù)操作導(dǎo)致Activity 的中止,onStop(?)方法會(huì)銷(xiāo)毀數(shù)據(jù)庫(kù),此時(shí)數(shù)據(jù)庫(kù)更新數(shù)據(jù)的操作會(huì)獲取到一個(gè)null 值,從而導(dǎo)致有害的數(shù)據(jù)競(jìng)爭(zhēng).

?Music

這是一個(gè)音樂(lè)播放的應(yīng)用,用戶(hù)可以改變Music 音樂(lè)播放器的狀態(tài)或者下載更新相關(guān)的音樂(lè).所導(dǎo)致數(shù)據(jù)競(jìng)爭(zhēng)發(fā)生的核心共享變量由一個(gè)表示音樂(lè)播放器的狀態(tài)變量state所導(dǎo)致.該應(yīng)用中,有多個(gè)線(xiàn)程擁有訪(fǎng)問(wèn)該狀態(tài)變量的權(quán)限.多數(shù)的數(shù)據(jù)競(jìng)爭(zhēng)為正常的更新?tīng)顟B(tài)變量來(lái)改變應(yīng)用的狀態(tài),并不會(huì)導(dǎo)致有害的行為.有害的數(shù)據(jù)競(jìng)爭(zhēng)發(fā)生在后臺(tái)任務(wù)下載音樂(lè)和播放音樂(lè)之間,當(dāng)發(fā)起一個(gè)后臺(tái)任務(wù)下載音樂(lè)時(shí),用戶(hù)的不同操作會(huì)導(dǎo)致應(yīng)用處于前臺(tái)的不同狀態(tài).當(dāng)后臺(tái)任務(wù)下載完成更新數(shù)據(jù)時(shí),如果用戶(hù)銷(xiāo)毀相關(guān)頁(yè)面,將會(huì)導(dǎo)致數(shù)據(jù)競(jìng)爭(zhēng).

通過(guò)分析上述應(yīng)用中數(shù)據(jù)競(jìng)爭(zhēng)產(chǎn)生的具體情況可知,多線(xiàn)程并發(fā)執(zhí)行任務(wù)是安卓應(yīng)用中常見(jiàn)的場(chǎng)景,如果沒(méi)有完善的同步措施,數(shù)據(jù)競(jìng)爭(zhēng)很可能發(fā)生并導(dǎo)致不同程度的危害.

4.5 工具對(duì)比

本節(jié)將對(duì)相關(guān)的安卓應(yīng)用數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)工具進(jìn)行比較和分析,包括CAFA、DroidRacer 和EventRacer.

(1)分析方法和覆蓋率

DroidRacer、CAFA 和EventRacer 使用動(dòng)態(tài)分析方法進(jìn)行建模,對(duì)原App 插樁,并動(dòng)態(tài)執(zhí)行App 獲取相關(guān)的執(zhí)行軌跡.其中,CAFA 主要檢測(cè)空指針異常所導(dǎo)致的數(shù)據(jù)競(jìng)爭(zhēng);DroidRacer 主要關(guān)注發(fā)生在用戶(hù)代碼中的事件交互所導(dǎo)致的數(shù)據(jù)競(jìng)爭(zhēng);EventRacer 不僅識(shí)別了用戶(hù)代碼中的數(shù)據(jù)競(jìng)爭(zhēng),同時(shí)也對(duì)安卓框架SDK 進(jìn)行了分析.但是動(dòng)態(tài)分析覆蓋率較低,尤其在安卓應(yīng)用中,一方面,一次動(dòng)態(tài)執(zhí)行很難觸發(fā)所有事件去覆蓋回調(diào)方法;另一方面,一次事件執(zhí)行的軌跡是固定的,但多線(xiàn)程的事件和線(xiàn)程調(diào)度是不確定的,如果要觸發(fā)更多的執(zhí)行軌跡,將會(huì)顯著增加性能消耗.

考慮到動(dòng)態(tài)分析方法在覆蓋率方面的缺陷,RaceDetector 使用了靜態(tài)分析方法,能夠保證具有較高的覆蓋率,另外還使用了約束求解方法去動(dòng)態(tài)生成所有可能的事件和線(xiàn)程調(diào)度.

(2)執(zhí)行軌跡的產(chǎn)生和性能

CAFA、DroidRacer 和 EventRacer 都是通過(guò)插樁并執(zhí)行 App 來(lái)獲取執(zhí)行軌跡.這里,我們?cè)敿?xì)分析EventRacer 工具.EventRacer 通過(guò)AndroidMonkey 產(chǎn)生隨機(jī)的輸入事件觸發(fā)App 的執(zhí)行,相關(guān)的命令為adb shell monkey–s 42–throttle 60–v 1000.這里產(chǎn)生了1 000 個(gè)輸入事件,運(yùn)行時(shí)間在1min 左右.隨著輸入事件的增加,執(zhí)行時(shí)間也會(huì)相應(yīng)增加.由于這些事件是隨機(jī)產(chǎn)生的,而安卓應(yīng)用中界面的跳轉(zhuǎn)往往需要觸發(fā)特定的事件,因此隨機(jī)事件存在大量的冗余,通常只是在固定的幾個(gè)界面中執(zhí)行重復(fù)的動(dòng)作,而不能執(zhí)行特定事件,進(jìn)而覆蓋到其他界面.

相反,RaceDetector 抽取所有組件、線(xiàn)程和事件回調(diào)方法信息,并檢查所有的事件回調(diào)方法間是否會(huì)滿(mǎn)足數(shù)據(jù)競(jìng)爭(zhēng)定義的第1 個(gè)條件;另外,還通過(guò)求解器判斷是否滿(mǎn)足數(shù)據(jù)競(jìng)爭(zhēng)定義的第2 個(gè)條件,保證覆蓋率和性能.

(3)模型

CAFA、DroidRacer 和EventRacer 都使用發(fā)生序HB 模型,它們構(gòu)建了全局HB 圖.其中,EventRacer 擴(kuò)展了CAFA 和DroidRacer 的HB 圖,并優(yōu)化了圖查找識(shí)別算法.它們所構(gòu)造的HB 圖是基于動(dòng)態(tài)執(zhí)行產(chǎn)生執(zhí)行軌跡.

與此相反,考慮到構(gòu)造一個(gè)全局的HB 模型會(huì)對(duì)性能產(chǎn)生很大的影響,RaceDetector 對(duì)每一個(gè)可疑的數(shù)據(jù)競(jìng)爭(zhēng)候選者上下文構(gòu)建局的HB 圖,即把全局的HB 圖劃分為多個(gè)小的局部HB 圖,優(yōu)化了算法和執(zhí)行時(shí)間.

(4)實(shí)驗(yàn)結(jié)果

我們使用EventRacer 和RaceDetector 對(duì)本文的數(shù)據(jù)集進(jìn)行了對(duì)比實(shí)驗(yàn).因?yàn)橄嚓P(guān)安卓平臺(tái)和版本的差異,數(shù)據(jù)集中的部分應(yīng)用無(wú)法直接進(jìn)行對(duì)比,最終6 個(gè)應(yīng)用的比較結(jié)果展現(xiàn)在圖4 中.所有的實(shí)驗(yàn)都是在EventRacer默認(rèn)的設(shè)置下進(jìn)行的,EventRacer 默認(rèn)設(shè)置產(chǎn)生300 個(gè)輸入事件去獲取執(zhí)行軌跡.

表4 的第1 列顯示了6 個(gè)應(yīng)用名稱(chēng).第2 列顯示了EventRacer 和RaceDetector 執(zhí)行時(shí)間.EventRacer 的執(zhí)行時(shí)間包括以下幾個(gè)部分:啟動(dòng)安卓模擬器、執(zhí)行App、檢索執(zhí)行軌跡文件、分析執(zhí)行軌跡文件.EventRacer的平均執(zhí)行時(shí)間約為50s.這是由于其默認(rèn)生成的300 個(gè)輸入事件數(shù)量較少,事實(shí)上,某些App 的Listeners 就已經(jīng)遠(yuǎn)遠(yuǎn)超過(guò)了300 個(gè).如果EventRacer 產(chǎn)生更多隨機(jī)事件去覆蓋Listeners,相應(yīng)的執(zhí)行時(shí)間也會(huì)大為增加.RaceDetector 分析小的安卓應(yīng)用只需要極少的時(shí)間,最少的OI File Manager 只需要8s.RaceDetector 平均需要49.2s 的執(zhí)行時(shí)間,但考慮到RaceDetector 覆蓋了全部的Activity、Thread 和Listeners,這個(gè)時(shí)間還是可以接受的.

Table 4 Data race detection reports by EventRacer and RaceDetector表4 EventRacer 和RaceDetector 檢測(cè)的數(shù)據(jù)競(jìng)爭(zhēng)報(bào)告

表4 第3 列～第6 列是詳細(xì)的數(shù)據(jù)競(jìng)爭(zhēng)信息.EventRacer 對(duì)數(shù)據(jù)競(jìng)爭(zhēng)劃分了4 個(gè)不同的類(lèi)型.

EventRacer 和RaceDetector 檢測(cè)到的數(shù)據(jù)競(jìng)爭(zhēng)總數(shù)在第7 列.我們可以看出,RaceDetector 檢測(cè)出的數(shù)量遠(yuǎn)遠(yuǎn)小于EventRacer.這是由于RaceDetector 只檢測(cè)了用戶(hù)代碼,EventRacer 檢測(cè)了用戶(hù)代碼和安卓相應(yīng)版本的SDK 代碼.然而,安卓SDK 對(duì)線(xiàn)程共享變量已經(jīng)做了很好的同步,沒(méi)進(jìn)行同步的是良性的數(shù)據(jù)競(jìng)爭(zhēng),對(duì)App 的行為并沒(méi)有有害的影響.

表的最后一列顯示了有害的數(shù)據(jù)競(jìng)爭(zhēng),可以看出,EventRacer 檢測(cè)出的數(shù)據(jù)競(jìng)爭(zhēng)中,有害的數(shù)據(jù)競(jìng)爭(zhēng)極少.相反,RaceDetector 檢測(cè)出的有害數(shù)據(jù)競(jìng)爭(zhēng)則占據(jù)一定的比率.具體對(duì)于OI File Manager 和Tomdroid,EventRacer分別報(bào)告了785 個(gè)和1 605 個(gè)數(shù)據(jù)競(jìng)爭(zhēng),沒(méi)有一個(gè)是有害的數(shù)據(jù)競(jìng)爭(zhēng).相反,RaceDetector 報(bào)告了11 個(gè)和106 個(gè)數(shù)據(jù)競(jìng)爭(zhēng),其中,對(duì)于OI File Manager 有8 個(gè)有害的數(shù)據(jù)競(jìng)爭(zhēng),對(duì)于Tomdroid 有3 個(gè)有害的數(shù)據(jù)競(jìng)爭(zhēng).

針對(duì)Pandora,可以發(fā)現(xiàn),RaceDetector 報(bào)告的數(shù)據(jù)競(jìng)爭(zhēng)超過(guò)了EventRacer 報(bào)告的數(shù)據(jù)競(jìng)爭(zhēng).這是因?yàn)閷?duì)于小的應(yīng)用,EventRacer 通過(guò)分析執(zhí)行軌跡和安卓SDK 能夠分析出較多的數(shù)據(jù)競(jìng)爭(zhēng).我們靜態(tài)檢索了所有的用戶(hù)代碼,但是應(yīng)用小,報(bào)告的數(shù)據(jù)競(jìng)爭(zhēng)也少.對(duì)于Pandora,它是一個(gè)大的安卓應(yīng)用.僅僅檢索用戶(hù)代碼,RaceDetector 報(bào)告的數(shù)據(jù)競(jìng)爭(zhēng)就超過(guò)了EventRacer.因此對(duì)于越大的應(yīng)用,EventRacer 將會(huì)遺漏更多的有害數(shù)據(jù)競(jìng)爭(zhēng).本次對(duì)比實(shí)驗(yàn)中,與RaceDetector 相比,EventRacer 平均遺漏了近20 個(gè)有害的數(shù)據(jù)競(jìng)爭(zhēng).

5 相關(guān)工作

?數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)方法

早期的數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)方法是基于鎖的[16,32,33],最有代表性的工具為Eraser[33].但是基于鎖的數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)方法屬于保守策略,有很?chē)?yán)重的誤報(bào)問(wèn)題(false positive).另一種數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)方法是基于HB 關(guān)系[18,27,28].不同的工具通過(guò)靜態(tài)或者動(dòng)態(tài)分析構(gòu)造HB 圖.基于靜態(tài)分析的數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)方法[1,11,12,14,15,20,34]有很好的覆蓋率,因?yàn)樗鼈兡軌蚪馕鏊械脑创a和執(zhí)行路徑;但存在誤報(bào)問(wèn)題,因?yàn)闊o(wú)法確定動(dòng)態(tài)加載的代碼和實(shí)際執(zhí)行的路徑選擇.與此同時(shí),覆蓋率的提高意味著性能的下降,解析全部的源代碼在大規(guī)模應(yīng)用中對(duì)性能有嚴(yán)重影響.如何平衡、取舍,也是靜態(tài)分析方法所面臨的挑戰(zhàn)之一.基于動(dòng)態(tài)分析的數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)方法適合用于大的數(shù)據(jù)集,并且能夠產(chǎn)生比較精確的結(jié)果,但會(huì)受到低覆蓋率的影響,因?yàn)橥ㄟ^(guò)執(zhí)行程序所獲取的上下文信息只能覆蓋很少的一部分代碼,會(huì)面臨漏報(bào)問(wèn)題(false negative).綜合了靜態(tài)分析和動(dòng)態(tài)分析的優(yōu)點(diǎn),基于預(yù)測(cè)性分析的數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)方法[29-31,35,36]從動(dòng)態(tài)分析出發(fā)獲取執(zhí)行軌跡,進(jìn)而分析執(zhí)行軌跡所依賴(lài)的限制條件,在遵循限制條件的前提下,采取策略改變語(yǔ)句和線(xiàn)程的調(diào)度,生成新的執(zhí)行軌跡,從而提高覆蓋率,既緩解了靜態(tài)分析的誤報(bào)問(wèn)題,又緩解了動(dòng)態(tài)分析的低覆蓋率問(wèn)題.還有基于causally-precedes(CP)的方法[37],能夠避免誤報(bào),但還是會(huì)有漏報(bào).文獻(xiàn)[38]進(jìn)一步將抽象的控制流信息引入到執(zhí)行模型中,彌補(bǔ)了HB 和CP 方法的不足,增加了解空間.本文擴(kuò)展了預(yù)測(cè)性分析中的約束求解方法,并結(jié)合靜態(tài)分析、共享變量逃逸分析和優(yōu)化的HB 圖,實(shí)現(xiàn)了RaceDetector.

?安卓應(yīng)用數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)

針對(duì)安卓應(yīng)用中數(shù)據(jù)競(jìng)爭(zhēng),文獻(xiàn)[10]首次形式化出了安卓應(yīng)用中的并發(fā)語(yǔ)義,總結(jié)出了安卓應(yīng)用中的HB 關(guān)系,并針對(duì)多線(xiàn)程代碼片段以及安卓中特有的單線(xiàn)程代碼片段,構(gòu)建了安卓應(yīng)用的HB 圖.基于動(dòng)態(tài)插樁技術(shù)和HB 模型,文中實(shí)現(xiàn)了相關(guān)工具DroidRacer.文獻(xiàn)[9]基于安卓應(yīng)用中的事件驅(qū)動(dòng)模型系統(tǒng),實(shí)現(xiàn)了工具CAFA,動(dòng)態(tài)地獲取安卓應(yīng)用的執(zhí)行軌跡并分析檢測(cè)數(shù)據(jù)競(jìng)爭(zhēng).EventRacer[8]擴(kuò)展了DroidRacer 的HB 模型,并優(yōu)化了檢索算法.但是這些工具都是基于動(dòng)態(tài)分析方法,存在固有的低覆蓋率問(wèn)題,尤其針對(duì)安卓應(yīng)用,除了線(xiàn)程發(fā)生序關(guān)系,還面臨定位事件發(fā)生序和事件發(fā)生時(shí)機(jī)的挑戰(zhàn).因此,現(xiàn)有的安卓并發(fā)語(yǔ)義和發(fā)生序關(guān)系在真實(shí)面臨復(fù)雜的事件操作和線(xiàn)程調(diào)度往往也存在嚴(yán)重的誤報(bào)問(wèn)題.除此之外,這些方法構(gòu)造了全局的HB 圖,很難處理大的應(yīng)用程序.即在安卓應(yīng)用中檢測(cè)數(shù)據(jù)競(jìng)爭(zhēng),采用靜態(tài)分析所面臨的問(wèn)題是如何平衡好覆蓋率和性能,并需要對(duì)性能進(jìn)行優(yōu)化,為此,我們進(jìn)行了共享變量分析以縮小范圍;應(yīng)用動(dòng)態(tài)分析將面臨低覆蓋率的問(wèn)題,因?yàn)榘沧繎?yīng)用是基于事件驅(qū)動(dòng)的,相對(duì)于傳統(tǒng)的多線(xiàn)程程序,安卓應(yīng)用的一次動(dòng)態(tài)執(zhí)行只能覆蓋很小比例的事件,為此,我們采用約束求解的方法來(lái)提升覆蓋率.

6 總結(jié)

本文主要研究了安卓應(yīng)用中數(shù)據(jù)競(jìng)爭(zhēng)這類(lèi)并發(fā)缺陷,針對(duì)現(xiàn)有工具的不足,本文提出了改進(jìn)的方法.

我們首先使用SOOT 工具解析安卓應(yīng)用的APK,并記錄共享變量信息和線(xiàn)程、安卓組件等必要信息.針對(duì)線(xiàn)程共享變量信息,我們集成了安卓應(yīng)用中的共享變量,并優(yōu)化了傳統(tǒng)的共享變量分析方法:逃逸分析.提出了安卓線(xiàn)程共線(xiàn)變量分析方法ATSA,可以使得實(shí)際的線(xiàn)程共享變量數(shù)目遠(yuǎn)遠(yuǎn)小于可能的線(xiàn)程共享變量數(shù)目,極大地縮小了RaceDetector 的分析空間并提高了執(zhí)行性能.繼而,我們形式化定義了可疑的數(shù)據(jù)競(jìng)爭(zhēng)候選者集合,并針對(duì)每個(gè)可疑的數(shù)據(jù)競(jìng)爭(zhēng)以及其上下文進(jìn)行約束編碼.在約束編碼階段,我們集成了安卓應(yīng)用中的Happens-Before 規(guī)則,并提出了局部的Happens-Before 圖.約束編碼之后,我們將產(chǎn)生的約束文件放入Z3 求解器中進(jìn)行求解,Z3 求解器覆蓋了所有的事件調(diào)度和線(xiàn)程調(diào)度,極大地提高了RaceDetector 的覆蓋率.

相對(duì)于現(xiàn)有工具,本文所實(shí)現(xiàn)的RaceDetector 能夠有效檢測(cè)數(shù)據(jù)競(jìng)爭(zhēng),同時(shí),我們的工作還存在一些不足之處:RaceDetector 通過(guò)SOOT 進(jìn)行相關(guān)分析,相關(guān)的性能受到SOOT 的限制,SOOT 不能解析動(dòng)態(tài)加載的代碼,并且針對(duì)部分App 會(huì)出現(xiàn)分析失敗的結(jié)果;同時(shí),RaceDetector 基于現(xiàn)有的工具所提出的并發(fā)語(yǔ)義和Happens-Before 進(jìn)行HB 關(guān)系分析,相關(guān)的性能和準(zhǔn)確性也受此影響;另外,針對(duì)有害的數(shù)據(jù)競(jìng)爭(zhēng),我們并沒(méi)有準(zhǔn)確定義它和良性數(shù)據(jù)競(jìng)爭(zhēng)的邊界,我們只是從空引用這一個(gè)角度對(duì)有害數(shù)據(jù)競(jìng)爭(zhēng)進(jìn)行了定義和分析.因此,還需要更深入的研究和探索.

由于精力有限,本文未關(guān)注Android SDK 框架層代碼中的數(shù)據(jù)競(jìng)爭(zhēng).原因在于,一是框架層已經(jīng)具備了很好的同步措施,技術(shù)相對(duì)成熟,并發(fā)缺陷較少,而應(yīng)用層主要由用戶(hù)的代碼構(gòu)成,代碼快速迭代很容易產(chǎn)生并發(fā)缺陷;二是SDK 框架層代碼中即使有并發(fā)缺陷,也不易修改(因?yàn)镾DK 框架層過(guò)于復(fù)雜),但用戶(hù)層的用戶(hù)代碼可以修改并完成之后的修復(fù)工作.后續(xù)我們將繼續(xù)進(jìn)行安卓應(yīng)用數(shù)據(jù)競(jìng)爭(zhēng)重現(xiàn)和修復(fù)的研究.