2.1.1 常用的静态分析技术
静态分析技术的发展要早于静态测试用例生成技术,从20世纪50年代就已经开始发展,到现在无论是在工程应用还是理论研究方面都取得了长足的进步。静态分析技术采用“保守的”分析,得到的结果是可靠的(sound),通常是真实程序语义的超集。从静态分析领域的顶级期刊、会议的研究方向来看,该领域包括以下一些常用的技术和热点。
1.基于抽象解释的数据流分析技术
Rice定理表明,静态分析无法做到分析程序的所有非平凡属性,所以程序分析工具在分析过程中需要某种程度上的抽象,把无法分析的或较复杂的“具体”程序属性转化成可分析的或相对简单的“抽象”属性[2],从而在满足某种“保守性”的前提下完成原本“不可能完成的任务”。
抽象解释是P.Cousot[12-16]和R.Cousot[16-18]最先提出的一种针对计算机系统语义模型的近似理论。抽象解释的主要思想就是把实际程序语义的计算替换为抽象域上的计算,而抽象执行的结果能部分反映程序的实际运行信息。抽象域是来自抽象解释理论的一个重要概念,它包括一个特定类别的、计算机可以表示的对象(域)集合和用来操作这些对象的操作(域操作)集合。在程序分析中,程序的状态集合是通过抽象域中的域元素来近似的,而程序的动作语义,包括条件判断、赋值、循环等,则通过抽象域中的域操作建模。例如,区间抽象域把程序中某执行位置处变量取值抽象为离散区间,使用区间运算模拟变量间的各种运算,从而分析得到该位置处变量的取值范围[17]。
在计算机科学中,抽象解释基于有序集尤其是格上的单调函数,是计算机程序语义的可靠逼近理论。抽象解释在本质上是在计算的效率和精度之间寻求平衡,先通过损失计算精度来减少计算代价,再通过迭代增强精度。抽象解释在软件领域的主要应用是形式静态分析和程序可能执行信息的自动提取。在满足一定约束的条件下,抽象解释能保证分析的正确性、安全性和可计算性。对象域抽象、伽罗瓦链接(Galois connection)和完备格上的加宽(widening)算子以及收窄(narrowing)算子是抽象解释理论的基本概念[13]。
作者所在项目组CTS所依赖的静态分析技术也是基于抽象解释的,目前已经在程序的静态分析方面做了大量工作并取得了很好的效果。项目组在抽象理论的基础上,扩展了经典的区间抽象,首先提出区间集的概念,定义了新的数值型区间集代数、引用型及布尔型代数,给出了统一的变量值范围分析方法RABAI,并引入加宽算子计算循环体变量取值范围,对过程参数定义了特殊的未定义取值(undefined),采用函数摘要计算过程调用对上下文状态的影响[19,20]。这个方法能压缩变量取值空间,并有效地检测出程序中的矛盾语句节点和不可达路径。本书基于上述理论,依据抽象解释的不动点理论对区间运算技术进行了迭代优化,提高了对于不可达路径的预判和求解约束的精确度。
2.区间运算
对程序中的变量取值范围进行区间抽象得到区间抽象域(interval domain),区间抽象是一种非关联抽象,即变量之间被认为是互相独立的,所以忽略它们之间存在的关系。区间运算是用区间集合代替具体数值的数学方法,可以更保守地描述一种可能性取值。区间运算由Burkill[21]和Young提出[22]。此后在他们的研究基础上有了很多后续研究[23,24],其中做出最大贡献的是Moore[25-28]的研究。在数值分析领域,Moore利用区间运算解决了数值计算的可信边界问题,用来计算舍入误差[26]。近些年来,在Moore模型的基础上,区间运算也被更多地应用于工程计算、计算科学和金融经济等方面,并涌现出大量关于区间运算的文章和书籍。
区间运算在计算机领域主要用于图形处理和辅助设计等方面。Muder将区间运算技术应用到计算几何学中[29]。而Maekawa基于区间运算提出了一种解决计算几何学中外形分析的方法,这种方法对自动生成自由形态对象很有效[30]。在其他一些研究中,区间运算也在图形处理等方面做出了贡献[31-34]。
为了提高软件测试的精度,同时使测试结果是保守的,区间运算被应用到软件测试领域。Harrison将区间运算用于编译器分析,对不同语句给出确定的变量取值范围[35]。王志言将区间运算用于约束集求解,但他给出的方法的求解效率无法满足代码规模庞大的实际工程需求[36]。李福川将区间运算引入航天领域的软件测试,通过数值型的区间运算保守地估算数值表达式的可能取值范围[37]。高传平通过区间运算检测数组越界,但只给出了整数数组的模型,对其他数值类型及非数值类型没有进行分析[38]。Ghodratl通过区间运算限定变量和表达式的取值范围,检验算术表达式的等价性[39]。
区间运算通过静态分析,将路径上所有语句转换成变量表和正则约束式表。变量表保存路径上各语句的定值或引用的全部变量,包括临时变量和常量。正则约束式记录变量之间的约束关系,其形式为r=d 1 op d 2,其中op是算术运算符、关系运算符或逻辑运算符,d 1和d 2是数值变量或常量。
在基于区间运算的测试用例生成方法中,通过穷举布尔变量值和对参与乘除运算的变量分区间,确定各变量在所有可能情况下的取值范围,再根据正则约束式,用区间削减和区间对分穷举等方法逐渐缩小各变量的取值范围,直至发现问题的解或者发现路径不可达。由于正则约束式的引入,区间运算能够处理复杂的逻辑表达式,以及包含二次函数等的非线性约束。(https://www.daowen.com)
3.符号分析
符号分析技术在20世纪70年代就被引入程序分析领域[1,2,40-42]。符号分析用符号值代替程序变量的值模拟程序执行,也就是说并不实际执行程序。赋值语句被认为是符号分析的参数条件,条件语句被认为是符号值的约束系统。具体来说,符号执行包括前向替换(forward substitution)和后向替换(backward substitution)[41]。前向替换自顶向下依次执行程序语句,通过判断路径中的谓词得到路径约束,这种方法更符合真实的执行过程。后向替换从程序出口向前依次用赋值语句右侧的表达式替换判断语句中相应赋值表达式中被赋值变量,从而得到一个仅包含判断语句的约束集合,这就是目标路径关于输入变量的约束集合。具体的更新过程是:如果在布尔表达式中出现被赋值变量,则直接替换为赋值语句右端的值;若被赋值的是数组成员,还要考虑其下标和布尔表达式中同名数组下标是否相等,是就替换,否就不替换。当数组多层嵌套时,需要为数组标记层次,再从里向外更新。后向替换法无须保存各变量的符号值,但是两种方法得到的约束是一致的。
现有的符号分析理论主要面向变量间的线性关联问题求解[43],通常对变量间的逻辑关联不讨论。目前比较常见的符号分析工具GSE[44]和jCUTE[45]等可以将复杂数据类型作为输入,处理多线程复杂逻辑程序。符号分析技术的应用领域很广,包括软件测试、调试与维护、程序验证、故障定位等[46]。
符号分析的基本思想是用抽象的符号表示程序中变量的值并模拟程序执行,所以程序输出是符号表达式。符号分析技术的优势是在不执行被测程序的前提下,使用符号运算静态地模拟程序的实际运行情况。它可以描述程序中变量间的约束关系,发现程序中的不可达路径和分支。具体来说,就是在进行符号分析时,控制流图的分支条件隐含地赋予条件变量以约束,这些约束就是执行相应路径的条件;用代数中的抽象符号处理变量,结合路径约束推理出描述变量之间关系的表达式,并通过该表达式是否矛盾来判断这条路径是否可达。因为它在遍历数据流的过程中对所有变量在任何可达路径下的可能取值进行计算,所以其分析结果是保守的。对于大规模程序的处理,在计算数据流信息时,随着代码行的增加,程序可执行路径数呈指数级增长。为了防止数据爆炸,需要选择性地采用上限阈值等限制策略。
符号分析能精确地分析程序行为,但存在以下缺点:第一,当程序中包含字符串、结构体、数组等复杂数据结构时,为它们生成相应的符号值比较困难;第二,如果被测程序包含很多函数调用,而符号分析需要对程序进行逐句分析,从而消耗大量计算资源,进一步,如果这些函数的代码不可见,也没有相关的函数摘要,则符号分析就无法进行;第三,对于符号分析收集的路径约束进行求解需要一个功能非常强大的约束求解器。
为了减少符号分析的开销,在实际应用中多采用“晚初始化(lazy-initialization)”方式为变量生成符号,即在符号分析过程中首次访问该变量时才为其生成符号[10]。在本书提出的算法中,为了满足测试用例生成的需要,对符号分析技术进行了修改:不再采用“晚初始化”方式,而是在函数入口处为所有输入参数生成符号,并记录每个符号所代表的输入变量(逆向映射关系),这样在路径的尾节点处可以查看哪些符号代表了输入参数。
4.程序切片
程序切片技术(program slicing)[47-49]的应用涵盖了很多方面,如软件维护、程序调试、代码测试、代码理解和逆向工程等。1979年,Mark Weiser在他的博士论文中首次提出程序切片的原理及方法。他认为程序切片相当于人们在调试程序时所做的智力抽象,并认为程序P的切片S是个可执行程序,S在某个功能属性上与P完全等效。根据在分析和理解程序时的不同兴趣点,可以定义不同的切片准则,由此“按需”对源程序进行切片。这种“简化问题、缩小目标范围”的原则使程序切片成为提高静态分析的一个有效方法。
在这之后,出现了许多略有不同的定义和用于计算切片的算法。大体上说,程序切片的发展经历了从静态到动态、从非分布式程序到分布式程序、从前向到后向等几个阶段。S.Horwitz等人对程序切片的定义[50]是:“一个程序切片是由程序中的一些语句和判定表达式组成的集合。这些语句和判定表达式可能会影响在程序的某个位置p上所定义的或所使用的变量v的值。(p,v)称为切片准则(slicing criterion)。”
静态切片技术使用静态控制流和数据流分析方法来计算程序切片。该技术所做的分析完全依据程序的静态信息,不对程序输入做任何假设。而动态切片技术使用动态控制流和数据流分析方法,切片的计算过程依赖程序的具体输入。
1991年,K.B.Gallagher等人提出分解切片技术[51],其目的是把程序分解成不同模块。分解切片构成的集合仍是程序切片,它能够捕获程序中对某一变量的所有计算。使用这种技术,可以很直观地判断出可以安全地修改一个模块中哪些语句和变量,即这种修改不会向其他模块扩散,以及不能随意修改哪些语句和变量。
