基于回放分析的并发错误重现与检测

摘要

随着多线程等并发技术的发展,多线程编程技术被越来越广泛地应用于实际中。多线程技术通过提高CPU的利用率,减少资源的浪费,从而大大提高了程序执行的效率。各种编程语言,如Java, C++等,也提出了各自的并发编程模型。这些并发编程模型,也被越来越多地应用于实际的开发之中,并且被证明可以极大地提高程序运行速度。但是与此同时,并发程序也由于其执行行为的不确定性,在发生错误后很难被开发人员定位；而错误发生后也往往需要花费开发人员大量的时间来重现错误发生的场景。典型的如数据竞争(Data Race),死锁(Deadlock)以及操作原子性的违反(Atomicity Violation),这些并发程序独有的错误大大增加了测试及修正并发程序的难度。基于以上几点,很大一部分传统的程序测试方法在并发程序中并不适用。而线程间调度的不可确定性,也对并发程序的测试提出了新的要求。为了更加方便地调试并发程序,记录及回放(Record & Replay)的方法被引入到了并发程序的测试之中。对于并发程序的记录及回放,目前存在两种方法：基于内容(Content-based)的以及基于顺序(Order-based)的方法。基于内容的方法可以准确地重现对于内存的读写内容,而基于顺序的方法则关注于线程间(inter-thread)事件的执行顺序。这两种方法有各自的优点及局限性：基于内容的方法由于内存读写数量的巨大,往往会生成过大的记录文件；而基于顺序的记录回放方法则需要线程执行过程中准确地重现线程间所有事件的执行顺序。对于并发程序中的程序错误(Software Bugs),目前已有的方法主要是通过长时间的压力测试(Stress Testing)重现错误。但是这样的方法除了需要耗费大量的时间以外,也无法保证能重现特定的并发错误。基于以上的需求,本文特别关注于并发程序中对于程序错误的记录及确定性的回放。使用Soot对Java字节码进行插装,将在原始程序的基础上生成两个版本的程序：记录及回放版本。运行记录版本的程序,将在程序运行同时记录下线程间事件的执行逻辑顺序。通过研究及扩展单线程程序错误重现架构,本文提出了工具ConCrash以在并发程序崩溃后自动生成多线程的测试用例以及程序运行的逻辑时钟顺序记录文件。通过运行这些测试用例并调用回放版本的程序,并发程序的崩溃场景可以被确定性地重现。本文的主要贡献在于以下几点：提出了一个轻量级及可扩展的对于多线程程序错误的捕捉重现技术,并可以同时与其他静态分析的前端技术相结合。实现了基于Java语言的原型,ConCrash,并且可以在程序崩溃后自动生成模拟多线程场景的JUnit测试用例。通过对基准程序及实际应用的测试使用,全面评估了ConCrash的有效性及性能额外开销,提出了未来工作的方向。

目录

摘要

Abstract

插图目录

表格目录

第一章 绪论

1.1 背景介绍

1.1.1 并发程序的发展

1.1.2 软件测试及其在并发程序中的应用

1.2 课题的研究意义

1.2.1 对于基于Java 语言的并发程序的记录及回放

1.2.2 自动生成可以重现并发错误的单元测试用例

1.3 国内外研究现状

1.3.1 并发程序的错误检测

1.3.2 并发程序的记录及回放

1.3.3 对于程序错误的重现及相关技术

1.4 论文基本思想和成果

1.5 论文组织结构

1.6 本章小结

第二章 并发程序的错误类型

2.1 概述

2.2 数据竞争

2.2.1 数据竞争的定义与示例

2.2.2 对于数据竞争的检测

2.3 原子性违反

2.3.1 原子性违反的定义及示例

2.3.2 对于原子性违反的检测与重现

2.4 程序死锁

2.4.1 程序死锁的定义及示例

2.4.2 对于程序死锁的检测技术

2.5 本章小结

第三章 并发程序的执行记录及确定性回放技术.

3.1 概述

3.2 基于内容的记录及回放技术

3.3 基于顺序的记录及回放技术

3.4 两种方法的比较分析

3.5 本章小结

第四章 并发程序错误重现工具CONCRASH 的设计及实现

4.1 概述

4.2 CONCRASH 总体架构及流程

4.2.1 总体架构图.

4.2.2 实例执行流程介绍

4.3 CONCRASH 预处理模块

4.3.1 Java 字节码及Soot 介绍

4.3.2 插装点的识别及字节码插装的实现

4.4 CONCRASH 记录及回放模块

4.4.1 Lamport 时钟及逻辑线程执行时序

4.4.2 记录及确定性回放算法

4.5 CONCRASH 测试用例生成模块

4.6 本章小结

第五章 实验评估

5.1 实验程序介绍

5.2 实验方法及过程

5.3 实验结果及讨论

5.3.1 重现错误能力结果

5.3.2 时间及空间开销结果

5.4 本章小结

第六章 经验及总结

6.1 本文主要贡献

6.2 研究展望

参考文献

致谢

攻读硕士学位期间已发表或录用的论文