基于云计算与动态符号执行的大型软件自动化测试研究

Testing for large-scale software has received significant importance from academe and industry both in China and abroad. In recent years, for its strong and automated analysis, dynamic symbolic execution (DSE) becomes the research hotspot of automated software testing. However, path explosion is the core issue which limits the scalability of DSE. Consequently, DSE cannot handle large-scale software. Taking advantages of computing scale, parallelization and high scalability etc, cloud computing provides a novel methodology to relieve path explosion. This project researches cloud-computing-based parallel DSE algorithm and its related optimizations from three aspects. Firstly, we will research the allocation and storage of program variables, as well as memory reorganization to track the propagation of symbols. We plan to lower the time complexity of tracking from log(2n) to constant. Secondly, we will parallelize DSE based on mapreduce programing model and then optimize the transitions of subtasks. Thirdly, we plan to research coordination of the global objective for task and the local objectives for working nodes. Then we will design demand-driven global cache algorithm, which takes advantage of the distributed file storage inherited from cloud computing. This project has important significance in solving path explosion and promoting the application of DSE in large-scale software testing.

大型软件的自动化测试一直受到国内外学术界和工业界的极大重视。动态符号执行因强大的分析能力与自动化的分析方式，近年来成为了该领域的研究热点。但是，路径爆炸问题严重影响了该技术的可扩展性，导致无法处理大型软件，是该技术面临的核心问题。云计算在计算规模、并行化和高可扩展性等上的优势，为解决该问题提供了全新的切入点。本项目从三个方面研究基于云计算的并行动态符号执行算法及优化：一、深入分析程序变量的分配和存储方式，研究一种内存重组织方法以跟踪符号传播，将时间复杂度从log(2n)降至常数级；二、基于云计算的mapreduce编程模型研究动态符号执行的并行化算法，并提出一种优化的子任务迁移方法；三、研究全局任务目标与局部节点目标的一致性协调方法，并利用云计算的分布式文件存储机制，设计一种需求驱动的全局缓存算法。本项目的研究对解决路径爆炸问题，推动动态符号执行在大型软件自动化测试领域的应用具有重要意义。

软件测试是保障软件可靠性和安全性的主要方法。为提高软件测试效率，自动化的测试方法受到了国内外学术界和工业界的极大重视。近10年来，动态符号执行成为了软件自动化测试领域的研究热点。然而，路径爆炸问题是动态符号执行面临的最主要难题之一，它严重的制约了动态符号执行的可伸缩性，导致其无法处理大型软件。鉴于近年来云计算的快速发展及其使用成本的大幅下降，本项目研究基于云计算的并行动态符号执行算法及多种优化方法，旨在缓解路径爆炸问题，具有重要的理论和应用意义。本项目的研究主要针对三个方面：一、深入分析程序变量的分配和存储方式，研究内存重组织方法以跟踪符号传播，将时间复杂度从log(2n)降至常数级；二、基于云计算的mapreduce编程模型研究动态符号执行的并行化，并提出优化的子任务迁移方法；三、研究任务全局目标与工作节点局部目标的一致性协调方法，并利用云计算的分布式文件存储机制，设计需求驱动的全局缓存算法。.我们的研究结果表明，基于mapreduce的云计算框架对动态符号执行进行并行化是可行的，除了在可扩展性方面表现良好，我们的方法还表现出对计算资源变动的弹性以及对节点失效的鲁棒性。