5.2.1　背景介绍

程序中的不可达路径,指的是在实际运行时任何输入参数都无法执行到的程序轨迹。循环结构会导致程序路径发生爆炸,不可达路径也随之增多[8]。不可达路径会导致静态分析的结果不准确和效率低下,例如,在自动测试用例生成问题中,不可达路径使自动用例生成在有限时间内达到覆盖率的要求变得困难,因此需要对不可达路径进行分析和检测。

在基于符号执行的静态测试用例生成中,会在路径搜索的过程中对路径条件的可满足性进行判定,抛弃不可达的路径条件组合,达到缩小路径搜索空间、提高效率的目的。根据分析方向的不同,可将符号执行技术分为两种:正向符号执行[9]和反向符号执行[10]。正向符号执行技术从程序入口开始,沿着控制流图的正方向生成路径和分析路径可达性。反向符号执行技术从一个指定的程序位置出发,沿着控制流图的反方向进行路径搜索和可达性判定。

导致不可达路径的直接原因是路径中存在着矛盾的约束条件,路径的可达性判定问题本质上是约束可满足性问题(Constraint Satisfaction Problem,CSP),而CSP是不可判定问题,因此不存在通用的算法对所有不可达路径问题给出确定的结论。现有的不可达路径判定技术包括矛盾片段识别[11]、约束求解[12]、动态执行[13]等。不同的不可达判定技术的效果受到被测程序的结构、约束类型、路径搜索策略等多方面因素的影响。例如,假设一个程序中存在循环结构,有一条程序路径经过此循环结构,此时路径长度可能很长,假设路径的最后两个谓词条件相互矛盾,导致此路径是不可达路径,若使用分析路径谓词条件的技术判定不可达路径,则不同的分析顺序会导致不可达路径的判定时间不同。例如,使用反向不可达判定则能够立即检测到矛盾的谓词条件的存在,而使用正向分析方法则需要分析一条完整的路径。P.Dinge在其研究工作[10]中使用了图5-8中的程序来说明反向不可达判定方法在特定情况下的优势。图中的语句“error();”被指定为覆盖目标,由于“if(y＞0)”和“if(y==0)”两个条件语句无法同时成立,所以所有包含此目标的程序语句都是不可达路径。利用正向分析寻找可达路径时,需要判定2n条路径的可达性,很可能因此超时;而从目标点出发进行反向分析可以立即判定出矛盾的条件。随着不可达路径长度的增长,这种差异会更加明显。(https://www.daowen.com)

图5-8　适合使用反向分析进行不可达判定的示例程序

以上初步分析表明,不可达路径的特征会影响应用什么分析方法进行不可达判定,但是目前缺少针对不可达路径特征的相关研究。因此,本章首先对不可达路径判定问题进行重定义,然后对不可达路径的特征进行归纳,研究程序特征和不可达路径之间的关联关系,给出适合的不可达路径判定技术。