关键词:
循环分析
循环内界
符号执行
KLEE
软件测试
软件缺陷
摘要:
循环是软件中重要但又易于出错的程序结构,循环分析是程序分析领域的重要研究方向。首先,如何深入循环进行测试并发现循环深处存在的软件缺陷是一项极具挑战性的工作。因为在遍历循环时,路径的不同执行顺序可能会产生大量执行可能性,导致循环测试成本过高,但某些循环中的软件缺陷只有在分析深入循环时才会发生。其次,在循环分析中得到循环的最大迭代次数也具有重要作用。很多应用场景要求静态分析循环在程序中能达到的最大迭代次数,即循环边界(Loop Bound)。循环边界有很多应用场景,包括系统最坏情况执行时间分析、程序各代码段性能分析等等。在循环测试中,符号执行是目前最先进的测试用例生成方法,但程序中循环的出现(尤其是无限循环)可能会产生大量甚至无穷条符号执行路径。现有研究主要关注使符号执行快速遍历循环,避免符号执行深陷在某些循环中执行而不能继续分析其他循环,但如何使循环分析深入循环执行并发现循环深处存在的缺陷仍然很困难。此外,在循环边界分析中,已有的循环边界分析均使用保守方法进行循环外界分析,即产生略高于实际循环边界的近似值,这些方法只能保证循环边界的安全性而忽略了边界是否实际可达,从而会带来分析结果不准确、计算资源浪费等问题。基于以上现状,本文提出了一种符号执行制导的循环分析方法,该方法通过制导符号执行深入循环进行分析,可以发现循环中存在的软件缺陷并生成相应的测试用例。此外,该方法还可以自动分析循环内界,即产生略低于实际循环边界的近似值。本文方法甚至可以处理包含嵌套循环和多个组合条件的复杂循环。本文基于循环条件制导的符号执行(Symbolic Execution)技术实现了对循环的分析,该技术的本质在于它能够利用符号执行对程序输入进行符号化的特性,准确地求解循环在程序所有合法输入条件下的边界值,并由生成的测试用例来保证该边界值一定可达(即保证是循环内界)。如果在符号执行中发现诸如缓冲区溢出、数组越界等软件缺陷,本文方法会报告检测到的缺陷信息,然后会跳过该缺陷继续分析后面的循环。本文对符号执行制导技术进行了优化,并在多组已有研究采用的基准用例集上进行了实例评估,实验结果表明,在循环测试时,本文的循环分析方法可以比当前最先进的循环摘要技术发现更多的软件缺陷。且与多个现有循环边界分析技术相比,本文方法也可以执行达到循环最大迭代次数,生成循环内界。这些结果说明了本文符号执行制导的循环分析方法可以足够深入循环执行,并且可以有效发现循环中的缺陷并得到循环内界。