基于动态符号执行的控制流图和调用图提取

作     者：房可昭 

作者单位：电子科技大学 

学位级别：硕士

导师姓名：张小松

授予年度：2020年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：动态符号执行 并行路径探索算法 路径爆炸 控制流图 调用图 

摘      要：随着生活水平的不断提高和科技的不断发展,我们的生活与软件变得密不可分,不管是平时的通讯、听音乐,又或者我们的学习和工作,软件在我们的生活中发挥着越来越不可替代的作用,但是现在的软件存在着越来越来越多的不安全因素,可能是软件存在漏洞或者有些软件本身是恶意的。所以需要对程序进行详细的分析和检测来找到它们中潜在的威胁。而对于二进制的程序分析来说,控制流图和调用图的提取是很重要的一个环节,因为控制流图和调用流图能表示一个程序的基本结构和调用关系,能为后续的程序分析提供很大的便利。首先为了能够更完整的提取一个二进制程序的控制流图和调用图,本文比较了当前可以应用的技术的优缺点,最后采用了当前很受欢迎的动态符号执行技术,因为在理论上动态符号执行的技术能够探索到所有的路径。基于当前先进的Angr平台,本文开发出来了一套控制流图和调用图提取的系统。当前的系统采用了动态符号执行的技术,能够完成中间语言的转化,程序的控制流和调用流的提取。然后为了缓解动态符号执行中路径指数增长造成的时间消耗,同时也是为了缓解动态符号执行过程中的路径爆炸问题,本文提出了多进程共同探索的路径探索算法,基于当前的CPU多核心的特性,在充分利用计算机的计算资源的前提下,对路径探索的时间进行优化。同时经过详细的分析发现,如果让主进程直接把分割出来的路径信息传递给子进程会造成时间和内存上的浪费,所以又提出了将所需要传输的路径信息进行编码,然后在子进程运行的时候再进行解码的方式去进行多进程的路径探索。最后通过对比其他的工具发现本文所开发的动态符号执行工具确实在路径探索中存在比较大的优势。但在时间的消耗上也确实很不理想,随后对本文所提出的多进程并行探索的算法进行了详细的测试和对比,发现当前的算法在不增加内存消耗的情况下能够增快路径探索的速度。并且有比较显著的效果。