你的App敵得過我單身二十年的手速嗎：Android App中的並發Bug淺析

從一個真(虛)實(構)的例子說起

(故事中的人物、事件均過於真實，請勿對號入座)

又到了周末，Da哥準備去看異地的女朋友。坐在火車上，他決定清理一下手機，刪掉一些可能會引起慘案的東西。他打開了他的文件下載工具，發現在已下載列表裡有兩個文件，第一個是Da哥下載的動作電影，而第二個是女朋友傳給他讓他幫忙修改的代碼。自然的，Da哥決定刪掉第一個會出事的文件，於是他點擊了文件圖標上的刪除按鈕。可是Da哥因為長期異地戀，練出了一手好手速，於是他習慣性地快速又點擊了一次。結果Da哥驚奇(恐)地發現，不光第一個文件被刪除了，第二文件也不見了。於是，Da哥因為弄丟了女朋友的代碼，度過了一個痛苦的周末。

這個場景類似於我們在開源應用中找到的「手速」bug。

這是怎麼回事？為什麼在第一個文件上點擊了兩次，會把第二個文件也刪除？這正是App中存在的並發bug所導致的。為了讓App儘可能像德芙一樣絲滑，App會有多個線程處理不同的任務，外界發送的事件會由不同的線程來處理。比如耗費時間的從網上下載一個文件這一任務，會被放到後台線程執行，而主線程來相應用戶的輸入事件(比如點擊一個按鈕)。這樣一來，即使下載文件要花費很長世間，App的界面依舊會流暢地響應用戶的輸入。然而我們都知道，多線程會引入許多非常讓人頭疼的問題，比如原子性違反(atomicity violation)或執行順序的違反(order violation)。

原子性違反和執行順序違反是並發程序中最常見的兩種bug。在Shan Lu等人的研究[2]中調研了大量真實程序中的並發bug，其中97%的非死鎖bug都屬於這兩種類型：

• 原子性違反(atomicity violation)：原子性是指某個線程中的一段代碼的執行在其它線程看來應當是瞬間完成的，無法在其執行過程中影響或獲取其執行狀態。原子性破壞則是違反了應有的原子性。
• 執行順序違反(order violation)：兩段代碼(同一線程或不同線程)在執行時應有確定的執行順序，然而在實際執行中執行順序被顛倒了。

上面的例子中正是Da哥的操作(快速點擊兩次刪除按鈕)導致了App的原子性違反。在點擊刪除之後，App會確認用戶點擊了列表中的哪一項(以序號進行標記)，找到這一項對應的文件，刪除文件與列表中相應的項，更新其它項的序號。這一過程應當是原子的，不應當有其他操作來獲取其執行狀態。然而因為Da哥的快速點擊，兩個相同的刪除事件(從App角度來看是兩個刪除列表中的第一項事件)被發送給了App。App在正常刪除第一個文件之後，更新了列表中其他文件的序號，因而第二文件成為了第一個文件，接著就被第二個刪除事件刪除了。

發現問題了嗎？ App正是違反了處理刪除事件的原子性，在處理第二個刪除事件時錯誤地基於處理第一個事件的中間狀態(即第一個文件依舊是動作電影)，因而錯誤地將新的第一個文件(即代碼文件)刪除了。

App中並發bug的檢測

想必這些bug讓程序員非常頭疼。要是能自動找到這些bug就好了。這當然也是辦得到得啦！

如何檢測App中的並發bug呢？好了，放猴子，讓Monkey來瞎點不就好了么？很遺憾，對於一個需要特定事件組合的bug來說，Monkey觸發它的概率太低了。在我們的實驗中，即便給Monkey相當多的時間，很多並發bug也是找不到的。

目前更有效的檢測技術大多都是基於預測執行路徑分析(Predictive Trace Analysis，即PTA) [3, 4, 5]的。簡單的說，就是向App隨機輸入事件，記錄App的執行路徑(trace，比如方法的調用關係，線程間共享變數的讀寫等)，之後靜態地分析這些執行路徑，探究執行中哪些操作的執行順序或執行時機發生改變，會導致原子性違反或執行順序違反，從而預測可能存在的並發bug。

Android App是事件驅動的。其中一類比較有代表性的技術就是檢測事件上的「數據競爭」 (data race)：如果兩個事件 和 之間沒有happens-before的先後關係，並且它們都訪問了同一個共享資源，而且至少有一個事件以寫的方式訪問，那麼按照 和 的執行順序，就可能導致不同的執行結果，從而可能導致bug。報告這些事件競爭能幫助開發者更好地診斷其中是否存在並發相關的bug。定義事件之間的happens-before不是一件特別容易的事情，技術細節請移步參考文獻 [5]。

這類方法可以有效地找到很多並發相關的bug。然而，缺乏實錘的爆料難免都是造謠。基於PTA的技術因為是靜態地分析有限的執行路徑，App內含的一些執行順序的限制、執行原子性的保護都會被忽略，從而導致預測出的結果中有很多誤報，而且多到有專門的工作來鑒別這些誤報[6]。所以，我們提出了一種有實錘的方法：通過在實際執行中觸發並發bug的方式檢測這些Bug。這樣一來，我們可以保證所有檢測到的Bug都是真實的Bug，並且有實際可行的輸入事件序列和線程調度來重現這些Bug。

同時產生事件和調度

那麼，如何在實際執行觸發這些Bug呢？我們發現，可以通過特定的事件-調度組合來觸發它們。比如在Da哥的例子中，觸發這一併發bug需要兩個點擊第一個文件的刪除按鈕的事件，並且需要一個特殊的調度，即第二個點擊事件必須在處理第一個點擊事件的任務完成前輸入給App。於是，要觸發並發bug，就有兩個關鍵點: (1) 確定有哪些事件可能會觸發App中的並發Bug；(2)在App的實際執行中枚舉這些事件及處理這些事件的任務的所有調度序列來觸發潛在的並發bug。

針對這兩個關鍵點，我們提出了一個兩階段的方法，分成預處理階段和觸發階段。

預處理階段

在這一階段，我們試圖確定哪些事件可能會觸發App中的並發Bug。我們知道，線程執行時互相影響狀態主要是通過共享變數的讀寫。那麼，我們只要找到有哪些事件會觸發讀寫共享變數的任務，那麼它們就可能與並發bug相關。

那麼如何獲取這些信息呢？還是採用分析執行路徑的方法。我們利用GreenDroid[7]來生成輸入事件，記錄App的執行路徑。GreenDroid是一個檢測App中能耗問題的工具，它能夠生成事件序列系統地探索App的狀態空間，我們正是藉助了這一點。在獲取了執行路徑後，我們分析App中方法的調用關係以及對共享變數的讀寫，再結合實踐序列，就可以輕鬆獲得所有可能與並發bug相關的事件和處理他們的任務啦。

觸發階段

有了這些可能觸發並發bug的事件，接下來我們就要在實際運行中枚舉它們的調度組合，看看是不是能夠觸發潛在的並發bug。我們首先按照DFS的方式探索App的GUI狀態空間。在每個狀態，我們找到所有的可能與並發bug的，當前狀態可作為輸入的事件。我們每次選取最多k個這樣的事件，為他們枚舉事件-調度組合。

我們首先枚舉這些事件所有的排列，多次按順序將他們輸入給應用。在每次輸入的過程中，我們為一對不同線程任務中的共享變數讀寫產生調度。我們在兩個任務將要讀寫共享變數時分別阻塞兩個任務所在的線程，然後按照不同的順序釋放它們，這樣就可以獲得不同的執行順序，也就是調度了。我們反覆恢復應用的狀態，為每一對不同線程任務中的每一對共享變數產生不同的調度，就可以觸發潛在的並發bug了。

實際程序的測試結果

實驗結果

我們一共選取了選取了32個Android App作為測試用例，其中15個App具有已知的並發bug，另外17個App是隨機選取的App。在15個具有一個並發bug的App中，我們成功檢測出了10個App中的並發bug。而在17個隨機選取的App中，我們檢測出了11個App中的並發bug，其中有7個是前所未知的Bug。我們將這些Bug報給給開發者，其中有3個獲得了確認。這些數據都比傳統的App自動測試工具Monkey和DFS好很多。

有趣的發現

我們進一步分析了這些並發bug的相關代碼，獲得了一些有趣的發現：

1. 儘管開發者和Android系統都花了很大的精力確保應用正確的原子性和執行順序，測試用例中的所有的並發bug都是由於原子性或執行順序違反所導致的。因而並發bug檢測工具應當至少關注這兩種Bug。
2. Android App中的生命周期事件(life-cycle events)會改變應用模塊的狀態，從而使App的並行執行情況更加複雜，也導致了很多並發bug的出現。開發者需要深入理解這些生命周期事件，並更加註意這類並發bug。
3. 開發者可能會錯誤地假設一個任務序列具有原子性，並且沒有很好地保證這一原子性。特別的，一個只應該執行一次的任務可能會因為一個特定的事件-調度組合而被多次執行，導致並發bug。文章一開始提到的例子，就屬於這種情況。開發者要對這一類Android特有的並發bug加以注意。
4. 開發者會在一些場合錯誤地使用Android提供的並發機制，從而導致執行順序的違反。比如AsyncTask，其doInBackgroud方法會在後台執行，而onPosExecute在主線程執行，且一定會在doInBackground方法執行完畢後才會運行。然而開發者可能會在啟動AsyncTask之後接著就對doInBackground中處理的數據進行操作，從而導致應有的執行順序出現了違反。

參考文獻

[1] J. Wang, Y. Jiang, C. Xu, Q. Li, T. Gu, J. Ma, X. Ma, J Lu. AATT+: Effectively Manifest Concurrency Bugs in Android Apps. Science of Computer Programming, to appear, 2018.

[2] S. Lu, S. Park, E. Seo, Y. Zhou, Learning from mistakes: a comprehensive study on real world concurrency bug characteristics, in Proc. of ASPLOS, 2008.

[3] P. Bielik, V. Raychev, M. Vechev, Scalable race detection for Android applications, in Proc. of OOPSLA, 2015.

[4] C.-H. Hsiao, J. Yu, S. Narayanasamy, Z. Kong, Race detection for event-driven mobile applications, in Proc. of PLDI, 2014.

[5] P. Maiya, A. Kanada, R. Majumdar, Race detection for Android applications, in Proc. of PLDI, 2014.

[6] Y. Hu, I. Neamtiu, A. Alavi, Automatically verifying and reproducing event-based races in Android apps, in Proc. of ISSTA, 2016.

[7] Y. Liu, C. Xu, S. C. Cheung, J. Lu, Greendroid: Automated diagnosis of energy inefficiency for smartphone applications, IEEE Transactions on Software Engineering, 40 (9), 2014.

論文信息: 「AATT+: Effectively manifesting concurrency bugs in Android apps」即將發表在2018年的Science of Computer Programming期刊上。工具的代碼也已經發布啦。

作者簡介：本文作者包括南京大學的博士生王珏、蔣炎岩博士，碩士畢業生李其瑋，許暢教授，馬駿博士，馬曉星和呂建教授。感謝Da哥友情客串。