论文部分内容阅读
宽带无线接入技术和移动终端技术的飞速发展使世界进入移动互联网时代,Android、IOS、WindowPhone三大操作系统应运而生。其中,安卓(Android)系统平台以其开源性占据主导地位,其事件驱动模型和多线程模型在增强用户体验和提高程序性能的同时,也造成了诸多并发缺陷,如数据竞争、死锁、原子性违反等,使应用崩溃、卡死,影响用户体验,甚至会带来严重的灾害。由于并发程序线程调度的不确定性和复杂性,并发缺陷的检测和再现显得尤为困难,本文主要关注安卓应用中数据竞争这一类并发缺陷。数据竞争,即多线程并发访问同一共享变量,且没有额外的同步机制。针对数据竞争检测,现有工具如CAFA、DROIDRACER、EVENTRACER等,通常插桩安卓应用并通过AndroidMonkey工具动态执行应用程序,获取执行轨迹。然后基于安卓平台的发生序(Happens-Before)规则构建执行轨迹的Happens-Before图,并通过判断对共享变量访问的2个语句是否存在Happens-Before关系来检测数据竞争。现有工作定义了安卓应用的并发语义并扩充了安卓平台的Happens-Before规则,在安卓应用中检测数据竞争。但也存在需要改进的地方:(1)基于动态分析的现有技术始终存在覆盖率低的问题;(2)现有技术并未对安卓应用数据竞争的有害性进行区分;(3)现有工具没有考虑数据竞争的再现。本文结合静态分析和动态分析,不仅检测数据竞争并通过生成测试用例再现数据竞争,还对其有害行为进行相关分析,同时,实现了相应的工具DRHDR(Detecting and Replaying Harmful Data Races in Android Applications)。论文的主要工作包括:(1)数据竞争检测包括静态分析和约束求解2个部分:静态分析阶段首先解析应用APK,记录应用相关信息,并通过安卓线程共享变量分析获取实际线程共享变量的最小集合,进而获取其读写集合,并定位符合数据竞争第一个条件的可疑数据竞争候选集合;约束求解阶段基于安卓平台的Happens-Before规则对可疑数据竞争候选者进行约束编码,并放入Z3求解器,最终得出检测的数据竞争集合。其中,数据竞争阶段使用静态分析提高覆盖率,使用约束求解覆盖所有线程调度和事件调度。(2)数据竞争再现包括 LCCG 图构建(Listener Callback Control-Flow Graph)、事件序列分析、测试脚本的生成、记录回放等过程。LCCG图展现了安卓应用事件驱动和回调方法的关系。针对可疑数据竞争候选者,可以在LCCG图中求得可达路径,并通过事件序列分析得出事件输入流的依赖关系。最后使用工具Monkey Runner生成测试脚本以触发安卓应用中特定的事件,并通过工具Reran再现数据竞争。论文实现了工具DRHDR。实验部分采用从Google Play等来源收集的15个流行的应用APK文件作为数据集。在数据竞争检测阶段,DRHDR平均报告了340个数据竞争,误报率为13%(44/340),其中4%为有害的数据竞争(15/340);在数据竞争再现阶段,相比于现有检测工具EVENTRACER(只通过单次执行路径覆盖线程调度,默认使用AndroidMonkey发送300个随机事件覆盖事件调度、覆盖率低、平均检测出2个有害数据竞争且没做再现研究),DRHDR在覆盖率上解析全部源码并使用约束编码覆盖所有线程调度和事件调度的解空间,在准确性上DRHDR平均检测15个有害数据竞争、平均再现出5个有害数据竞争。