基于混合符号执行和遗传算法的源代码漏洞挖掘技术研究

摘要

在互联网给人们带来这么多的便捷的同时，也伴随着各种病毒、网络攻击等安全问题。根据相关安全部门统计数据显示，75％的黑客攻击发生在应用层。黑客攻击主要手段是利用系统的各种漏洞进行渗透，据NIST的统计数据显示92%的漏洞出现在应用层而不是网络层。为了能够让人们能够安全放心的使用互联网，维护网络应用软件的安全就成为网络安全中的核心问题。
　　漏洞挖掘技术是解决应用软件安全的核心技术，根据测试对象的不同，可分为面向源代码的漏洞挖掘技术和二进制码的漏洞挖掘技术。近年来针对软件漏洞挖掘技术的研究已取得显著进展，但由于涉及到动态追踪、符号执行、路径约束收集和求解等多方面技术，仍然存在不少缺陷问题，主要包括：路径爆炸问题，由于在符号执行过程中，针对代码执行路径，会生成相应路径的约束条件，如果软件较大或存在大量循环操作，可能导致路径约束非常大，甚至呈现爆炸式增长；约束求解问题。在符号执行过程中，会生成大量约束条件，当符号数量较大时，或者存在非线性约束条件时，求解器将无法求解；测试效率问题，在符号执行过程中，需要动态监控程序指令执行过程，引入符号值并生成符号约束条件和求解，当软件较大时，指令数和符号数都非常大，测试效率比较低。
　　针对网络应用软件安全问题及漏洞挖掘中的非线性约束求解问题，本文做了基于混合符号执行和遗传算法的源代码漏洞挖掘技术研究，主要工作如下：
　　1.概述了混合符号执行的关键技术、系统框架及其在软件安全自动化测试中的应用，介绍了软件安全测试工具KLEE中的符号执行技术，介绍了KLEE的实现、LLVM框架、KLEE内存模型及KLEE中约束求解器。
　　2.针对KLEE中求解器无法对非线性约束条件进行求解的问题，对传统的遗传算法进行了改进。从编码方式、适应度函数及牛顿迭代终止条件三方面对遗传算法进行了改进，提高了对非线性约束条件求解的精确度和收敛速率。
　　3.引入改进的遗传算法，实现了KLEE中STP求解器与改进的遗传算法并行求解非线性约束条件。设计了遗传算法求解模块，对遗传算法求解模块接口进行了实现，实现了KLEE中并行求解模块、KQuery抽象解析层，最终利用KLEE调用并行求解模块生成测试用例。
　　4.针对改进后的KLEE在求解非线性约束条件这一问题上的可行性，在Linux系统下的LLVM框架上进行了实验验证。搭建了LLVM框架，并在LLVM框架上利用KLEE对含非线性约束条件的程序进行测试，利用基于遗传算法和混合符号执行改进后的KLEE调用并行求解模块对非线性约束条件进行求解，得出覆盖路径并自动生成测试用例，并将结果与KLEE测试的结果进行对比。实验结果表明，改进后的KLEE能够求解原KLEE无法求解的非线性约束条件，并且生成能够覆盖非线性约束条件所在路径的测试用例，有效的提高了测试覆盖路径及测试效率。最后利用改进后的KLEE实现了在内存泄漏检测中的应用。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪 论

1.1 研究背景与意义

1.2 研究现状

1.3 本文主要工作

第二章 混合符号执行与KLEE概述

2.1 混合符号执行概述

2.2 KLEE测试工具概述

2.3 本章小结

第三章 改进的遗传算法求解非线性约束条件

3.1 遗传算法

3.2 改进的遗传算法

3.3 非线性约束条件的求解

3.4 本章小结

第四章 改进遗传算法求解模块与STP并行求解实现

4.1 遗传算法求解模块

4.2 遗传算法求解模块接口实现

4.3 KLEE并行约束求解模块

4.4 KLEE调用并行求解模块生成测试用例

4.5 本章小结

第五章 实验与结果分析

5.1 实验环境

5.2 实验测试

5.3 改进后的KLEE在内存泄露检测中的应用

5.4 本章小结

第六章 总结与展望

6.1 全文总结

6.2 本文创新点总结

6.3 后续工作展望

致谢

参考文献

攻读硕士学位期间取得的成果