Journal of software软件学报Vol.30,No.1, January2019 串4、动态数据结构14-14等方面的支持 在可行性方面环境建模和多形态分析目标的支持是目前的主要问题在环境建模方面,已有的工作基本都 是在分析的精确性、可靠性、建模工作量以及可扩展性之间进行权衡和折中,包括手工建模030、自动合 成1、动态执行1、全栈执行108等在多形态分析目标方面主要是应对多语言和多应用领域的复杂性包括 二进制程序10815.2、脚本语言程序、分布式程序、数据库操作程序15、无线传感器网络程序156、 并发或并行程序35158、嵌入式程序19、PLC程序1等符号执行方法 同时,面向新的分析需求,也有一些新的符号执行技术出现,其中比较有代表性的是概率符号执行技 术16-16,其基本思想是通过符号执行来得到程序的路径,然后使用SMT解空间体积计算技术来计算每条路径 的路径条件的解的个数,通过每条路径对应的解的个数,可以计算每条路径的概率基于此可以开展包括低概 率缺陷查找、低概率路径的测试用例生成、生成程序的性能分布6、刻画代码变迁16等活动 随着符号执行技术近些年的发展符号执行技术在工业界也得到了实际的采纳和应用,其中有代表性的工 作有微软公司把自己开发的二进制动态符号执行工具SAGE用于Win7的测试发现了文件模糊测试中1/3的 16由于SAGE通常是微软公司最后使用的缺陷检测工具,因此这些由SAGE发现的缺陷,很多都没有被 之前在开发过程中使用的静态分析工具、黑盒测试工具所发现微软公司多个开发小组已把SAGE作为日常 具在使用,SAGE目前也被商业化为微软公司的安全风险检测( microsoft security risk detection)服务微软公司在 Visual studio2015中正式发布了基于动态符号执行的C#自动单元测试工具 IntelliTestl6,可大幅度提高C#程 序单元的测试效率C程序符号执行工具KLEE0对 GnU Coreutils程序集进行了自动测试可自动达到94%的 语句覆盖率并发现3个程序崩溃问题 analyze6s在开源软件中发现数百个真实缺陷并在工业界嵌入式系统 中发现两个缺陷2016年8月,在美国 DARPA举办的网络空间安全竞赛(CGC中最终排名前三的参赛队伍全 部使用了符号执行技术,用于自动发现并利用二进制程序中的漏洞美国 GrammaTech公司开发的商业程序分 析工具 Codesonar中也使用了符号执行技术,用以发现程序中的深层缺陷 未来,符号执行技术将进一步在软件工程、安全、系统、网络等相关领域的实际需求驱动下不断发展面 向大规模软件的高效符号执行方法、技术和工具将是下一步研究所面临的挑战和重点同时符号执行搜索策 略的更加智能化1也将是下一步的研究重点此外,与其他技术在不同层面的密切结合1013,以进一步提高 件分析效果,也将成为符号执行后续的研究趋势之 2.5动态分析 动态分析是指通过在指定测试用例下运行给定的程序,并分析程序运行过程或结果用于缺陷检测等与静 态分析相比,动态分析能够更好地处理编程语言中的动态属性例如指针、动态绑定、面向对象语言中的多态 与继承、线程交替等动态分析在一定程度上弥补了静态分析的不足之处 基本的程序动态分析可以简单地分为在线 online)动态分析与离线( Offline)动态分析在线动态分析是指 在程序的运行过程中分析当前程序行为;而离线动态分析需要记录程序的运行行为在程序运行结束后再进行 分析两者的基本思想都是通过对程序运行过程或者结果的分析,查找定位缺陷.具体来说,一方面可以将程序 运行结果和预知结果对比确定程序中是否含有缺陷;另一方面,可以通过插桩或其他监控技术分析程序的运行 行为,查找错误的行为前者很直观但是对于被触发了却没有反映在输出中的缺陷无法检测后者则可以直 观察到程序中缺陷的触发,即使该次触发并没有导致错误的输出但是后者需要提前定义错误的行为,其对于非 常见的缺陷无法检测已有文献中有大量这方面的介绍174 程序动态分析,从报告缺陷的准确性出发也可以分为(1)缺陷动态检测、(2)缺陷动态预测.一般所指的缺 陷动态査找方法是缺陷动态检测,是指在程序的运行过程中某个缺陷已经发生了之后的检测,即,缺陷已经反映 在程序行为中或者运行结果中其关注点是:如何设计检测算法等保证将所有己经发生的缺陷检测出来然而 程序中的不同缺陷不会都在有限的若干测试用例中被触发因此,为了提高缺陷动态检测的有效性需要从程序 若干次运行中预测出该程序潜在的某些行为,并判断这些潜在行为是否会触发缺陷这种方法称为缺陷的动态 预测例如:某个程序中存在一个缓冲区溢出缺陷,该缺陷只有在输入 Input大于128时发生那么,如果我们可以88 Journal of Software 软件学报 Vol.30, No.1, January 2019 串[146]、动态数据结构[147149]等方面的支持. 在可行性方面,环境建模和多形态分析目标的支持是目前的主要问题.在环境建模方面,已有的工作基本都 是在分析的精确性、可靠性、建模工作量以及可扩展性之间进行权衡和折中,包括手工建模[105,106]、自动合 成[150]、动态执行[102]、全栈执行[108]等.在多形态分析目标方面,主要是应对多语言和多应用领域的复杂性,包括 二进制程序[108,151,152]、脚本语言程序[153]、分布式程序[154]、数据库操作程序[155]、无线传感器网络程序[156]、 并发或并行程序[135,157,158]、嵌入式程序[159]、PLC 程序[160]等符号执行方法. 同时,面向新的分析需求,也有一些新的符号执行技术出现,其中比较有代表性的是概率符号执行技 术[161163],其基本思想是:通过符号执行来得到程序的路径,然后使用 SMT 解空间体积计算技术来计算每条路径 的路径条件的解的个数,通过每条路径对应的解的个数,可以计算每条路径的概率.基于此,可以开展包括低概 率缺陷查找、低概率路径的测试用例生成、生成程序的性能分布[164]、刻画代码变迁[165]等活动. 随着符号执行技术近些年的发展,符号执行技术在工业界也得到了实际的采纳和应用,其中有代表性的工 作有:微软公司把自己开发的二进制动态符号执行工具 SAGE 用于 Win 7 的测试,发现了文件模糊测试中 1/3 的 缺陷[166].由于 SAGE 通常是微软公司最后使用的缺陷检测工具,因此,这些由 SAGE 发现的缺陷,很多都没有被 之前在开发过程中使用的静态分析工具、黑盒测试工具所发现.微软公司多个开发小组已把 SAGE 作为日常工 具在使用,SAGE 目前也被商业化为微软公司的安全风险检测(microsoft security risk detection)服务.微软公司在 Visual Studio 2015 中正式发布了基于动态符号执行的 C#自动单元测试工具 IntelliTest[167],可大幅度提高 C#程 序单元的测试效率.C 程序符号执行工具 KLEE[105]对 GNU Coreutils 程序集进行了自动测试,可自动达到 94%的 语句覆盖率,并发现 3 个程序崩溃问题;Canalyze[168]在开源软件中发现数百个真实缺陷,并在工业界嵌入式系统 中发现两个缺陷.2016 年 8 月,在美国 DARPA 举办的网络空间安全竞赛(CGC)中,最终排名前三的参赛队伍全 部使用了符号执行技术,用于自动发现并利用二进制程序中的漏洞.美国 GrammaTech 公司开发的商业程序分 析工具 CodeSonar 中也使用了符号执行技术,用以发现程序中的深层缺陷. 未来,符号执行技术将进一步在软件工程、安全、系统、网络等相关领域的实际需求驱动下不断发展.面 向大规模软件的高效符号执行方法、技术和工具将是下一步研究所面临的挑战和重点.同时,符号执行搜索策 略的更加智能化[169]也将是下一步的研究重点.此外,与其他技术在不同层面的密切结合[170173],以进一步提高 软件分析效果,也将成为符号执行后续的研究趋势之一. 2.5 动态分析 动态分析是指通过在指定测试用例下运行给定的程序,并分析程序运行过程或结果,用于缺陷检测等.与静 态分析相比,动态分析能够更好地处理编程语言中的动态属性,例如指针、动态绑定、面向对象语言中的多态 与继承、线程交替等.动态分析在一定程度上弥补了静态分析的不足之处. 基本的程序动态分析可以简单地分为在线(online)动态分析与离线(offline)动态分析[1].在线动态分析是指 在程序的运行过程中分析当前程序行为;而离线动态分析需要记录程序的运行行为,在程序运行结束后再进行 分析.两者的基本思想都是通过对程序运行过程或者结果的分析,查找定位缺陷.具体来说,一方面可以将程序 运行结果和预知结果对比,确定程序中是否含有缺陷;另一方面,可以通过插桩或其他监控技术分析程序的运行 行为,查找错误的行为.前者很直观,但是对于被触发了却没有反映在输出中的缺陷无法检测;后者则可以直接 观察到程序中缺陷的触发,即使该次触发并没有导致错误的输出.但是后者需要提前定义错误的行为,其对于非 常见的缺陷无法检测.已有文献中有大量这方面的介绍[174]. 程序动态分析,从报告缺陷的准确性出发,也可以分为:(1) 缺陷动态检测;(2) 缺陷动态预测.一般所指的缺 陷动态查找方法是缺陷动态检测,是指在程序的运行过程中某个缺陷已经发生了之后的检测,即,缺陷已经反映 在程序行为中或者运行结果中.其关注点是:如何设计检测算法等,保证将所有已经发生的缺陷检测出来.然而, 程序中的不同缺陷不会都在有限的若干测试用例中被触发.因此,为了提高缺陷动态检测的有效性,需要从程序 若干次运行中预测出该程序潜在的某些行为,并判断这些潜在行为是否会触发缺陷.这种方法称为缺陷的动态 预测.例如:某个程序中存在一个缓冲区溢出缺陷,该缺陷只有在输入 input 大于 128 时发生.那么,如果我们可以