使用共享变量分析和约束求解检测安卓应用数据竞争

安卓系统在移动端操作系统始终占据主导地位,在增强用户体验和提高程序性能的同时,其特有的事件驱动模型和多线程模型也造成了并发缺陷.并发程序中,线程调度的不确定性和难以再现性是并发缺陷检测困难的原因.现有技术主要在动态生成执行路径的基础上进行发生序（happens-before）分析,进而检测安卓应用的并发缺陷,但仍然存在低覆盖率、误报、漏报等问题.结合共享变量分析和约束求解方法实现了安卓应用数据竞争的检测,并实现了检测工具RaceDetector.该工具首先根据安卓系统的特性和数据竞争的定义,通过静态分析抽取相关信息,并进一步使用安卓共享变量分析来提高准确性和性能,继而进行可疑数据竞争分析,得出可疑的数据竞争集合;接着根据每一个可疑的数据竞争候选者,通过约束求解的方法在所有事件调度和线程调度解空间下识别发生序关系,并最终检测出真正的数据竞争.实验部分是从Google Play等来源收集了15个流行的应用APK文件作为数据集,RaceDetector平均报告了340个数据竞争,误报率为13%（44/340）.与现有工具EventRacer（默认产生300随机事件触发应用执行,平均检测2个有害数据竞争）相比,RaceDetector能够解析全部源码,覆盖了所有线程调度和事件调度,平均检测出15个有害数据竞争.     

基于测试例生成的Android应用数据竞争验证方法

Android应用是一种事件驱动的并发程序。后台线程与异步事件执行顺序的不确定,导致数据竞争在Android应用中普遍存在。现有的针对Android应用的竞争检测工具会产生大量误报,且不能确定地重现竞争。针对以上问题,在现有的竞争检测结果的基础上,提出了一种基于测试用例生成的Android应用数据竞争验证方法。该方法首先构建应用的状态转化图,并基于状态转化图和现有竞争检测工具的检测结果自动生成包含潜在数据竞争的测试用例,然后在测试用例执行的过程中通过控制事件分发和线程的执行顺序来暴露竞争,观察竞争是否会引起程序异常。实验结果表明,该方法能有效地重现数据竞争引起的并发错误,并指出检测结果中的误报。     

一种路径敏感的静态缺陷检测方法

提出一种多项式复杂度的路径敏感静态缺陷检测算法.该方法采用变量的抽象取值范围来表示属性状态条件,通过属性状态条件中的变量抽象取值范围为空来判断不可达路径.在控制流图(control flow graph,简称CFG)中的汇合节点上合并相同属性状态的状态条件,从而避免完整路径上下文分析的组合爆炸问题.该算法已应用于缺陷检测系统DTS(defect testing system).实际测试结果表明,该方法能够减少误报.     

多线程程序数据竞争检测与证据生成方法

数据竞争是多线程程序最为常见的问题之一。由于线程交织导致状态空间爆炸,多线程程序数据竞争引起的错误检测难度大、成本高、精度低;此外,即使检测到数据竞争,由于线程调度难以控制、执行过程难以复现,错误难以复现和定位。提出了一种多线程程序数据竞争检测与证据生成方法,基于程序语义分析和执行过程监测,构建程序的执行路径约束模型和数据竞争条件,将多线程程序数据竞争检测问题转化为约束求解问题,降低检测难度,提高检测精度;利用SMT求解器计算可能的数据竞争,并生成触发该数据竞争的程序执行序列,协助程序员定位和验证错误。实验中对10个程序进行了测试,相比现有数据竞争检测工具threadsanitizer和helgrind,本方法检测出的数据竞争多出287.5%和264.7%,且没有误报,而其他方法平均误报率为10.5%和9.8%。     

多线程程序数据竞争的静态检测

多线程并发程序的广泛使用带来了更多的数据竞争错误．传统的数据竞争静态检测由于对并发语义和别名信息的保守分析会导致很多假错误．因此,提出了一个精确有效的静态检测框架：分析应用了精确的别名分析并静态模拟了访问事件发生序;为提高分析效率,检测算法提出了一个以对象为中心,结合Escape分析缩小检测范围的检测算法并配合设计了压缩的别名等价类表示．检测框架在一个静态Java编译器JTool上做了实现,对于测试程序取得了很好的分析结果．     

动态容忍和检测非对称数据竞争

非对称数据竞争是数据竞争中一种常见的类型.当一个线程在临界区内访问某个共享变量,另外一个线程在临界区外或不同的临界区内同时也访问这个共享变量时,就触发了非对称数据竞争.多线程程序中的非对称数据竞争往往是有害的.为了解决非对称数据竞争引入的问题,提出了ARace.它使用共享变量保护和写缓冲区来动态容忍和检测非对称数据竞争.其中,共享变量保护用于保护临界区内只读和先读后写的共享变量,防止这些变量在临界区外被修改;写缓冲区用于缓存临界区内对共享变量的写操作.ARace不仅可以容忍临界区内和临界区外之间的非对称数据竞争,还可以对并发临界区之间的非对称数据竞争进行检测.ARace既不依赖程序源代码和编译器的支持,也不依赖额外硬件的支持.此外,还提出了一种通过动态二进制插桩技术实现ARace的方法.实验结果表明,ARace在保证容忍和检测非对称数据竞争的同时,并未引入很大的性能开销和内存开销.     

并发Java程序同步操作的有效删除

同步操作是并发Java程序非常大的一部分开销.在现有程序分析方法的基础上,提出了一种精确而有效的冗余同步操作的静态删除方法.该方法分为基本处理和线程间时序分析两个阶段,充分考虑了控制流结构和线程交互时序对同步删除的影响.构造了一个Java编译器JTool,并在其上实现了同步删除算法.对于确定的单线程程序,同步删除率达到100%;对于多线程程序,同步删除率高于现有的分析工具.     

基于污染变量关系图的Android应用污点分析工具

污点分析技术是检测Android智能手机隐私数据泄露的有效方法,目前主流的Android应用污点分析工具主要关注分析的精度,常常忽略运行效率的提升.在分析一些复杂应用时,过大的开销可能造成超时或程序崩溃等问题,影响工具的广泛使用.为了减少分析时间、提高效率,提出了一种基于污染变量关系图的污点分析方法.该方法定义了污染变量关系图用于描述程序中污染变量及其关系,摒弃了传统数据流分析框架,将污点分析和别名分析进行结合,从程序中抽象出污染变量关系图和潜在污染流,并在控制流图上对潜在污染流进行验证以提高精度.本文详细描述了基于该方法所实现的工具FastDroid的架构、模块及算法细节.实验使用了三个不同的测试集,分别为DroidBench-2.0,MalGenome以及Google Play上随机下载的1517个应用.实验结果表明,FastDroid在DroidBench-2.0测试集上的查准率和查全率分别达到93.3%和85.8%,比目前主流工具FlowDroid更高,并且在三个测试集上所用的分析时间更少且更稳定.     

提高静态缺陷检测精度方法

误报率和漏报率是静态缺陷检测的关键技术指标,提高分析精度是降低误报和漏报的主要手段.文中介绍了缺陷模式及其有限状态机描述,提出基于传统数据流分析的缺陷检测方法.采用变量抽象取值来近似地表示程序动态执行信息,通过状态条件中的变量抽象取值范围为空来判断不可达路径,以实现路径敏感分析;使用缺陷相关的函数摘要来表示缺陷检测所需函数调用信息,其中缺陷相关的函数摘要包括前置约束信息、后置约束信息和函数特征信息三部分,实现了上下文敏感的跨函数分析.文中方法已在缺陷检测系统DTS中实现,在大型开源软件分析中的实验结果表明,该方法能减少误报和漏报.     

基于约束依赖图的并发程序模型检测工具

模型检测是一种基于状态空间搜索的自动化验证方法,可以有效地提升程序的质量.然而,由于并发程序中线程调度的不确定性以及数据同步的复杂性,对该类程序验证时存在更为严重的状态空间爆炸问题.目前,大多采用基于独立性分析的偏序约简技术缩小并发程序探索空间.针对粗糙的独立性分析会显著增加需探索的等价类路径问题,开发了一款可细化线程迁移依赖性分析的并发程序模型检测工具CDG4CPV.首先,构造了待验证可达性性质对应的规约自动机;随后,根据线程迁移边的类型和共享变量访问信息构建约束依赖图;最后,利用约束依赖图剪裁控制流图在展开过程中的独立可执行分支.在SV-COMP 2022竞赛的并发程序数据集上进行了对比实验,并对工具的效率进行比较分析.实验结果表明,该工具可以有效地提升并发程序模型检测的效率.特别是,与基于BDD的程序分析算法相比,该工具可使探索状态数目平均减少91.38%,使时间和空间开销分别平均降低86.25%和69.80%.     

高精度的大规模程序数据竞争检测方法

随着技术的不断发展,软件系统的非确定性(uncertainty)不断增强,数据竞争是并发系统这一类典型的非确定性软件系统中常见的缺陷.尽管数据竞争静态检测近年来取得了巨大进展,但其面临的重要问题仍然存在.先前的静态技术要么以分析精度为代价达到高扩展性,要么由于高精度分析而导致可扩展性问题.提出一种解决上述矛盾的分段分析...     

基于静态检测工具的源代码安全缺陷检测研究*

针对已有的使用单个静态检测工具进行源代码安全缺陷检测存在的漏报率和误报率很高的问题,提出了一种基于多种静态检测工具的检测方法。该方法通过对多种工具的检测结果进行统计分析,有效地降低了漏报率和误报率。设计和实现了一个可扩展的源代码静态分析工具平台,并通过实验表明,相对于单个工具的检测结果而言,该平台明显降低了漏报率和误报率。     

基于Petri网展开的多线程程序数据竞争检测与重演

数据竞争是多线程程序的常见漏洞之一,传统的数据竞争分析方法在查全率和准确率方面难以两全,而且所生成检测报告难以定位漏洞的根源.鉴于Petri网在并发系统建模和分析方面具有行为描述精确、分析工具丰富的优点,提出一种基于Petri网展开的新型数据竞争检测方法.首先,对程序的某一运行轨迹进行分析和挖掘,构建程序的一个Petri网模型,它由单一轨迹挖掘得到,却可隐含程序的多个不同运行轨迹,由此可在保证效率的同时降低传统动态分析方法的漏报率;其次,提出基于Petri网展开的潜在数据竞争检测方法,相比静态分析方法在有效性上有较大提升,而且能明确给出数据竞争的产生路径;最后,对上一阶段检测到的潜在数据竞争,给出基于CalFuzzer平台的潜在死锁重演调度方法,可剔除误报,保证数据竞争检测结果的真实性.开发相应的原型系统,结合公开的程序实例验证了所提方法的有效性.     

基于数据融合的源代码静态分析漏洞检测技术

针对目前现有静态分析方法存在的漏报率和误报率较高的问题,提出一种基于数据融合的源代码静态分析漏洞检测技术.该技术通过对不同检测方法的分析结果进行解析和数据融合,有效地降低误报率和漏报率.设计与实现了一个可扩展的源代码静态分析工具原型,可通过用户的反馈信息自动寻优.实验结果表明:相对于单个漏洞检测方法而言,该方法的误报率和漏报率明显降低.     

X10并行程序中静态数据竞争检测

在多线程程序中,当2个以上线程在没有顺序约束的条件下访问同一个存储单元时,且其中至少有一个为写访问,则可能会发生数据竞争。为此,提出一种针对X10并行程序的静态数据竞争检测算法,包括源访存对计算、可达访存对计算、时钟同步访存对计算和逃逸访存对计算4个阶段。通过在WALA框架中分析构建程序的调用图,计算源访存对集合,检测出内存访存中可能发生数据竞争的无序对。实验结果表明,该算法可以在不显著增加X10并行程序总体运行时间的情况下,达到比较理想的数据竞争检测效果。     

DigHR: precise dynamic detection of hidden races with weak causal relation analysis

Present advanced precise race detection techniques leverage strict causal relation to locate data races, leading to false negatives and missing many hidden races. In this paper, we present a novel race detection technique, called DigHR, which can detect more hidden races than existing precise techniques. DigHR is based on a weak causal relation, called afterward-confirm (AC) relation, which relaxes restrictions of existing causal relations and is proved to be sound. To represent AC relations between events, we propose a new data structure, called water-flow graph, which enable DigHR to analyze AC relations and detect hidden races at run-time. We have implemented DigHR in C/C++ and evaluated the effectiveness of DigHR by detecting races from real-world benchmarks and applications. The experimental results show that DigHR can precisely detect 21% more races than previous techniques, including FastTrack and CP.