你的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哥友情客串。