5.4.1 问题的描述
1.问题的提出
以图5-16为例来说明路径中包含库函数约束求解的测试用例生成问题。图5-16中是一个被测程序test及其对应的控制流图。其中if_out_5、if_out_6、if_out_7、exit_9是虚节点。如果采用分支覆盖,则有4条待覆盖路径,分别是Path1:0→1→3→4→5→8→9、Path2:0→1→2→3→5→8→9、Path3:0→1→2→6→8→9、Path4:0→1→7→8→9(路径上的数字均对应控制流图的节点)。
如果令Path1为待覆盖路径(加粗部分),就要同时满足路径上所有if节点上的约束。约束1和约束2将x的取值域限定在[91,149],if_head_3节点中的约束是ctype.h中的一个库函数,其功能是判定ASSIC为x的字符是不是大写字母,此项约束将x的取值域限定在[65,90]。由此可知,不存在这样一个能为x选出合适的值的区间,可生成正确的用例并成功覆盖Path1,即输入参数x的取值域为空,Path1为不可达路径。
由于符号执行无法对isupper()函数生成能够表示其语义的符号,区间运算也无法根据其语义为其参数x的取值域做相应的运算,因此只能将x的值域确定为[91,149],并在此区间内做浪费时间和资源的无用功。
图5-16 被测程序test及其控制流图
2.问题的定义
基于以上提出的问题,结合求解包含库函数约束需确定其函数具体功能的特点,提出了基于语义分析的库函数区间运算的求解模型,以便扩展区间运算的处理范围。
定义5-14 基于语义分析的库函数区间运算的求解模型是一个四元组(E,L,X,D)。
·E表示当前处理的约束表达式。
·L表示E所在的库函数反操作集合,若E为普通约束即约束中不包含库函数,则L为空。
·X={x 1,x 2,x 3,…,x n},表示当E为包含库函数的约束表达式时其输入参数的符号集合,若E为普通约束,则其为空。
·D={dom(x 1),dom(x 2),dom(x 3),…,dom(x n)},表示当E为包含库函数的约束表达式时其输入参数对应的值域集合,若E为普通约束,则其为空。
求解路径上节点中的约束E时,若判定约束中包含库函数,经过库函数反操作集合L处理,对此库函数的输入参数列表X进行求解,得出适当的区间集合D。(https://www.daowen.com)
定义5-15 库函数求反操作集L是一个五元组(E,F,X,I,O)。
·E表示当前处理的包含库函数的约束表达式。
·F表示当前库函数的语义。
·X={x 1,x 2,x 3,…,x n},表示包含库函数的输入参数的符号集合。
·I={dom(x 1),dom(x 2),dom(x 3),…,dom(x n)},表示库函数输入参数符号满足库函数约束时的库函数值域。
·O={dom(x 1),dom(x 2),dom(x 3),…,dom(x n)},表示经过区间运算后的库函数输入参数符号的输出区间集(由区间interval构成,为了简便以下把区间集均称为区间)。
经过语义解析,得出当前约束表达式E中库函数的函数语义F,根据F对库函数输入参数列表X的输入区间I进行区间运算即可得出其输出区间O。
定义5-16 对于一个库函数LF(x 1,x 2,x 3,…,x n),存在一个域D={dom(x 1),dom(x 2),dom(x 3),…,dom(x n)},对于任意库函数参数x i,都有当x i∈dom(x i)(其中i=1,2,…,n)时,保证此库函数LF能够正确执行其函数功能,这个dom(x i)即称为x i的定义域,D即为x 1~x n的参数定义域。
将包含库函数的约束表达式形式定义为E=(LF(x 1,x 2,x 3,…,x n)op N)op M,其中LF(x 1,x 2,x 3,…,x n)为库函数表达式,x 1~x n为库函数的输入参数,M、N为任意符号表达式,op为操作符。那么存在任意的包含库函数的约束表达式E,库函数表达式LF(x 1,x 2,x 3,…,x n)的值域均可用表达式M、N的值域来表示。
函数库是具有一定功能的函数的集合,因此为库函数的输入参数生成合适的测试用例必须依据其函数功能来确定其输入参数的定义域,只有生成的用例在其定义域内,这个用例对此库函数才是有效的。库函数的反操作集合就是这样根据库函数语义确定库函数输入参数定义域的一组操作。
求库函数参数定义域的操作即求反操作借鉴了数学领域中反函数的思想,下面给求反操作的定义。
定义5-17 令库函数为F(X)(X∈I)的值域是C,若找到一组操作Li(i=1,2,3,…,n),能够令C经过区间运算求得输入参数的定义域O,这样的一组操作即为库函数的求反操作。
根据对约束表达式语义分析后得出的库函数类型F_type,可以在求反操作集L中找到与此库函数对应的求反操作L i,并由此得到满足库函数参数定义域的参数取值区间O={dom(x 1),dom(x 2),…,dom(x n)},保证最后生成的用例取值V={V 1,V 2,…,V n}一定在此区间内,即V i∈dom(x i),满足库函数的约束要求。
