动态符号执行约束求解优化设计与实现

摘要

从上个世纪至今，计算机的各个领域都取得了长足的进步，软件作为存储和管理信息的工具，已广泛深入到现实社会的各个领域，成为整个社会的支柱产业之一，正是因为软件的重要性日益提升，软件漏洞可能带来的损失也越来越大，特别是在对软件漏洞比较敏感的领域，例如：金融、瓦斯检测、航天等行业，任何一个不易察觉的漏洞都可能引灾难性事故。程序分析技术和软件测试技术的目的在于，确保待分析程序的正确性、一致性以及确保程序在安全状态下运行。软件测试的发展过程中，出现了一系列的测试技术，从最初的静态代码分析技术到曾经被广泛使用的糊测试技术，软件测试技术也随着现代计算机水平的进步和软件行业对安全需求的提升而不断地发展。
　　符号执行技术于上世纪70年代被提出，受限于当时的软硬件条件未被广泛应用，随着近些年计算机技术的发展，符号执行技术被再一次重视起来。动态符号执行技术是一种衍生于传统符号执行的新技术，采用符号与具体值相结合的方式，有着代码覆盖率高、可以自动生成测试用例等特点。动态符号执行技术一经提出就受到了众多软件公司和研究人员的重视，在学术界和产业界均取得了较大的进步，并且形成了了一系列工具，在实际应用中有着较好的效果。但是，目前为止，动态符号执行技术还存在一些难以解决的问题，例如，路径爆炸以及面对应用领域复杂性和程序设计语言复杂性时所受到的局限等等。
　　本文着眼于动态符号执行的约束求解优化问题，提出一种针对约束集合的基于线性规划技术的优化方法，通过此优化方法可以降低约束集合中约束条件的复杂性，降低后续求解生成测试用例过程的计算复杂度，从一定程度上提升了约束求解过程的效率，本文选择KLEE作为研究对象，为其约束求解部分增加一个LP_OP模块，在该模块中实现了线性规划优化过程，以达到提高动态符号执行约束求解过程效率的目的。
　　为验证LP_OP模块对KLEE约束求解效率的提升，本文选择几个常用工具作为分析对象，使用KLEE对这些程序进行程序分析并生成相应的测试用例。通过对比加入LP_OP模块前后约束求解过程消耗的时间和整个KLEE执行过程消耗的时间，证明了LP_OP模块对提升约束求解性能的有效性。

目录

1 绪 论

1.1 论文背景、研究内容及意义

1.2 国内外研究现状

1.3 本文主要工作

1.4 论文结构安排

2 符号执行基础理论

2.1 符号执行概述

2.2 符号执行基本原理

2.3 符号执行存在问题

2.4 约束求解过程

2.5 小结

3 基于线性规划的约束求解过程优化

3.1 线性规划基础理论

3.2 线性规划优化约束求解

3.3 小结

4 针对KLEE的约束求解优化设计与实现

4.1 KLEE概述

4.2 KLEE约束求解模块

4.3 KLEE约束求解模块优化设计与实现

4.4 小结

5 实验与结论分析

5.1 实验环境

5.2 实验过程

5.3 实验结果分析

5.4 小结

6 总结与展望

6.1 工作总结

6.2 下一步工作

致谢

参考文献

附录

A. 作者在攻读硕士学位期间发表的论文题目