基于不变量的并发错误检测技术

摘要

随着并发软件系统的广泛应用，由多线程的复杂交互所引发的并发错误无处不在，因此如何有效检测并发错误至关重要。对于多线程程序而言，并发错误的出现依赖于以小概率出现的线程之间特定的交互顺序，而并发错误通常会在错综复杂的多线程交互中蔓延与扩散，因此有效检测出并发错误的根源难度很大，需要消耗大量的人力与时间。目前，现有的并发错误检测技术大多针对数据竞争问题进行交错模式分析，它们的核心思想是抽取线程之间可疑的数据访问模式，即从不同线程对共享数据的读写顺序中抽取模式。然而这类技术有以下局限性:1）交错模式的数量可能非常庞大，2）交错模式一般只针对单变量的读写模式，3）所需要的能判断程序单个输出结果是否正确的机制oracle在程序的操作层面上不可得。
　　本文提出基于程序不变量的并发错误检测技术。首先对并发程序中的组件进行单元测试得到参照不变量，然后与组件在集成测试中得到的线上不变量进行对比后，得到失效不变量。接着在测试程序的函数调用图上应用本文提出的不变量降噪过程与基于深度搜索的错误定位策略，得到可疑代码块（函数本身或者函数与函数之间的代码块）。最后计算可疑代码块的怀疑度并排序，分析组件交互时产生的并发错误。为了验证该技术的有效性，本文在6个开源程序上进行实验。实验结果表明本文提出的方法能有效检测多种类型的并发错误，如违反原子性与死锁等。
　　本文提出的方法主要的贡献点:1）不需要oracle信息;2）可以在程序的操作层面上利用程序不变量检测多种类型的并发错误，如违反原子性错误和死锁等;3）将并发错误根源定位到线程中的可疑代码区域。

目录

声明

摘要

第一章 绪论

1．1 研究背景及意义

1．2 相关工作

1．3 本文主要研究内容

1．4 论文组织结构

第二章 方法概览

第三章 并发错误类型与程序不变量

3．1 定义并发错误

3．2 程序不变量

第四章 基于不变量的错误定位技术

4．1 不变量生成

4．2 建立函数调用图

4．3 计算调用顺序与深度

4．4 不变量降噪

4．5 定位可疑函数与怀疑度计算

4．6 降噪与错误定位策略的细节探讨

4．7 算法复杂度

第五章 实验

5．1 log4j2：违反原子性错误

5．2 log4j1：死锁问题

5．3 Dining Philosophers：死锁

5．4 Producer-Consumer：坏的组合

5．5 reorder：违反原子性

5．6 account：死锁问题

5．7 实验小结

5．8 威胁方法有效性的因素分析

第六章 结论与展望

6．1 结论

6．2 展望

参考文献

攻读学位期间的研究成果

致谢