随着多核处理器和并行技术的普及，并发软件系统可以更好的提高系统资源利用率，实现“低能耗、高性能”的目标。多线程编程技术被广泛应用于各大领域，例如构建数据中心、云平台等。尽管多线程程序可以有效提高系统性能、降低能耗，然而仍难以保证程序正确性。由于不能控制线程调度而导致程序执行结果不可预期，存在多种线程交织方式，并且软件错误难以复现。为了有效测试多线程程序，本文提出基于约束求解的多线程程序局部交织链覆盖方法和基于约束求解的多线程程序Def-Use穷举方法，从交织覆盖和路径覆盖两方面入手，以期完全覆盖多线程程序状态空间。
首先，介绍多线程程序行为模型，将程序行为转化为一阶逻辑表达式用以描述满足约束条件的可行线程交织空间。其次，提出基于约束求解的多线程程序局部交织链覆盖方法，通过约束求解生成覆盖局部交织链的线程交织集合，完全覆盖特定路径下线程交织空间。最后，提出基于约束求解的多线程程序Def-Use穷举方法，通过约束求解指导路径分支取反，覆盖多线程程序路径空间。遍历路径空间，穷举每条路径的Def-Use约束关系，同时依照局部交织链覆盖方法覆盖该路径的线程交织空间，以完全覆盖多线程程序状态空间。
为验证方法可行性，开发基于LLVM编译框架和KLEE符号执行工具的原型工具，使用通用测试案例集实验验证。实验结果表明，局部交织链覆盖方法可以有效覆盖特定路经的线程交织空间。与随机执行实验结果相比，Def-Use穷举方法可以有效构建Def-Use测试案例集，完全覆盖程序状态空间。