摘要
多线程编程技术在当今的软件开发领域得到广泛应用，由于多线程程序设计的复杂性，死锁等并发漏洞对软件系统的可靠性造成巨大挑战。死锁的发生会导致程序无法正常运行，严重情况下会引起系统瘫痪。因此，死锁检测成为软件分析领域的研究热点之一。死锁检测分为静态分析和动态分析两类。前者通过对程序源代码的分析实现死锁检测，漏报率低，但是由于难以获取程序的运行时信息，从而会导致大量的死锁误报。后者以程序某次运行产生的行为轨迹为出发点，据此对程序的潜在行为模式进行分析并检测死锁。由于该类方法可有效利用程序的运行时信息，因此检测的死锁存在较低的误报率。鉴于误报排除困难以及动态分析效率与自动化程度高的优点，针对其仍然存在部分死锁误报的现状，本文拟提出一种新型的多线程程序动态死锁检测和重演方法。论文的主要研究内容如下: (1)锁增广分段图和时序增广锁图的构建:对锁图、分段图、锁依赖关系等现有的动态死锁分析模型进行分析，探究他们导致误报的根源，据此对已有的锁图和分段图模型进行改进，在锁图基础上扩充语句的执行时序信息，在分段图的基础上扩充锁的获取和释放信息，并对段进行更细粒度的划分以建模“锁-start”耦合导致的线程操作问的依赖关系，由此提出了锁增广分段图和时序增广锁图的概念，并给出了由程序运行轨迹构建这两类模型的具体算法; (2)基于锁增广分段图和时序增广锁图的死锁检测:首先，基于时序增广锁图中的环路识别潜在死锁;之后，借助锁增广分段图判定环路操作间是否存在因果关系，再借助持有锁集信息和“历史持有锁-持有锁”耦合因果关系图识别环路操作间是否存在互斥关系;仅当环路的各个操作间既不存在因果关系、也不存在互斥关系时，将该环路视为一个潜在死锁; (3)基于锁授权线程序列的死锁重演:针对运行轨迹丢失程序语义信息导致的死锁误报，对上一阶段检测到的各个潜在死锁，设计算法计算能触发此死锁状态的锁授权线程序列，并以此序列作为程序的调度方案给出了一个确定性的死锁重演算法，每个重演成功的潜在死锁都是一个真实的死锁。 基于Java多线程程序主动测试平台CalFuzzer，设计并实现了死锁检测和重演的原型系统，并结合搜集到的公开程序实例，比较了本文所提方法与传统的动态分析方法在检测精度和时间性能方面的差异。实验结果证明，本文方法能有效地排除更多误报，并且重演效率更高。
NETL