并发程序缺陷检测技术研究

摘要

在当前多核架构充分普及的硬并发时代，并发程序以其资源利用率高、计算速度快等优点，在现代软件开发中得到了广泛应用，已经成为软件开发行业的主流。然而，由于多线程调度的不确定性，并发程序容易产生各种类型的并发缺陷，甚至会造成严重的后果。因此，迫切需要高效自动化并发缺陷检测技术的支持，快速有效地发现各种并发缺陷，以保证并发软件的质量和可靠性。 近年来，并发软件测试在软件工程领域得到了广泛关注，并发缺陷检测也逐渐成为研究热点。研究人员从多种不同角度对并发缺陷检测进行了广泛且深入的探索，并取得了丰富的研究成果，但仍存在一些不足，如线程共享分析不准确，并发缺陷检测效率较低，并发程序执行轨迹上下文切换频繁等。本论文主要研究并发缺陷检测的一些关键问题，旨在进一步提高并发缺陷检测能力和检测效率。具体研究内容如下： 1．为了提高线程共享分析的准确性，提出一种细粒度动态线程共享分析方法，用于识别Java并发程序中的线程共享数据和共享访问点。通过平稳分析删除平稳域，然后区分不同的数组元素，最后过滤掉非共享访问点。在20个该领域广泛使用的多线程程序上开展实验，并与最新方法进行对比。结果表明，该方法能够提高线程共享分析的准确性，并且可以扩展到含有上百个线程的大型程序。 2．为了探究不同粒度的线程共享分析方法对数据竞争检测性能的影响程度，提出一种线程共享分析粒度影响分析方法。实验选取了对象粒度、对象域粒度和数组元素粒度，以及相应的动态线程共享分析方法获取共享数据和共享访问点，然后使用动态数据竞争检测器RVPredict进行竞争预测。结果表明，基于数组元素粒度线程共享分析的数据竞争检测性能最优，且不会降低数据竞争检测的有效性。 3．为了提高并发缺陷检测效率，提出一种缺陷驱动和覆盖指导的并发缺陷检测方法。首先通过静态分析移除不可能并发执行的方法对。然后将剩下的方法对基于缺陷驱动技术分为两组，分别具有两种不同的外部优先级。最后，迭代地执行并发测试生成和测试执行以检测线程安全类中的并发缺陷。我们设计了一种组内方法对选择优先级策略，每次选择优先级最高的方法对，为其生成并发测试用例，并执行该测试用例，通过线程安全预言验证并发缺陷。实验结果表明，该方法在不影响并发缺陷检测能力的情况下，能够显著提高并发缺陷检测效率。 4．为了减少并发程序执行轨迹中频繁的上下文切换，提出一种基于上下文切换链表的双向并发程序执行轨迹简化方法。首先准确识别原始轨迹中事件之间精确可靠的依赖关系，然后将初始链表抽象为简单的上下文切换链表，按顺序进行后向重构和前向检查，得到简化后等价轨迹。选取8个该领域广泛使用的大中小型基准程序作为实验对象，并与已有方法进行实验对比。结果表明，提出的方法在有效性方面明显优于已有方法。此外，该方法还可以扩展到百万量级的轨迹长度，且依然具有很好的效果。 综上所述，本论文旨在解决并发缺陷检测中的关键问题，在一定程度上丰富了并发程序测试理论，并为提高线程共享分析准确性、并发缺陷检测和诊断效率等科学问题提供了一条新思路和新方法。

目录

声明

致谢

变量注释表

1 绪论

1.1 研究背景及意义(Background and Significance)

1.2 国内外研究现状(Research Status)

1.3 存在问题(Existing Problems)

1.4 研究内容(Research Contents)

1.5 论文结构(Organization)

1.6 本章小结(Summary)

2 并发程序缺陷检测相关基础

2.1 基本概念(Basic Concepts)

2.2 线程共享分析(Thread Sharing Analysis)

2.3 并发测试生成(Concurrent Test Generation)

2.4 并发程序执行轨迹简化(Trace Simplification of Concurrent Programs)

2.5 评价指标(Evaluation Metrics)

2.6 本章小结(Summary)

3 细粒度动态线程共享分析方法

3.1 引言(Introduction)

3.2 研究动机(Motivation)

3.3 细粒度动态线程共享分析(Fine-grained Dynamic Thread Sharing Analysis)

3.4 实验评估(Experimental Evaluation)

3.5 本章小结(Summary)

4 线程共享分析粒度对数据竞争检测性能的影响分析

4.1 引言(Introduction)

4.2 性能影响分析(Performance Impact Analysis)

4.3 实证研究(Empirical Study)

4.4 本章小结(Summary)

5 缺陷驱动和覆盖指导的并发缺陷检测方法

5.1 引言(Introduction)

5.2 预备知识(Preliminary)

5.3 缺陷驱动和覆盖指导的并发缺陷检测(Bug-driven and Coverage-guided Concurrenty Bug Detection)

5.4 实验评估(Experimental Evaluation)

5.5 本章小结

6 基于上下文切换链表的双向并发程序执行轨迹简化方法

6.1 引言(Introduction)

6.2 研究动机(Motivation)

6.3 基于上下文切换链表的双向轨迹简化(Bidirectional Trace Simplification Based on a Context Switch Linked List)

6.4 实验评估(Experimental Evaluation)

6.5 本章小结(Summary)

7 总结与展望

7.1 论文工作(Achievements)

7.2 研究展望(Research Prospects)

参考文献

作者简历

学位论文数据集