摘要 程序定义域的确定有利于指导测试用例的选取。虽然程序规范规定了输入变量的定义域，但程序实现本身也定义了其定义域，如果二者不能完全重合，那么某些软件错误就可诊断出来。为此，本文提出了一种基于数据流分析的程序定义域自动确定方法。通过对源程序进行数据流分析和相关性分析，求取输入变量的定义域。采用程序抽取技术，将与输入变量无关的语句和函数剔除，简化了源程序，提高了分析效率。采用动态模拟技术，实现了特殊情形下输入变量的定义域确定。实验证明该方法是行之有效的。
关键词 数据流分析、程序抽取、动态模拟、非数值变量、程序定义域
中图法分类号 TP311.5
A Method of Program Domain Automated Determination
Based on Data Flow Analysis
Ruilian Zhao and Yinghua Min
Abstract The determination of program's input domain is helpful to select test data. The implementation of a program defines the domain of input variables, though the specification of the program also specifies the domain. However, if they are not coincided with each other exactly, some software errors can be detected. This paper presents a novel approach of program domain automated determination based on data flow analysis. Using the techniques of data flow analysis and relevance analysis on given program the domain can automatically be identified. The program slicing method is employed to delete those statements and functions that are not related to input variables, so that the given program is simplified and analyzing efficiency is improved. The domain of input variables can be obtained under some particular circumstances by using dynamic stimulation strategy. A lot of experimental results show that the proposed approach is efficient.
Keyword data flow analysis, program slicing, dynamic stimulation, nonnumeric variable, program domain.
1 引言
尽管软件质量保证贯穿于软件生存期的各个阶段，但软件测试仍然是保证软件质量的重要措施，是对软件功能、设计和实现的最终审定。要检验开发的软件是否符合规格说明书的要求，可以采取各种不同的测试策略。例如：基于程序的白盒测试或基于规范的黑盒测试，随机测试或穷举测试，自顶向下测试或自底向上测试等等 [1] 。但是，不论采取哪一种测试策略，设计测试方案 (testing case) 都是测试阶段最关键的技术问题 [1,2,3] ，测试以前都需要从程序定义域 (domain) 中选取有代表性的测试数据。因此，程序定义域对于测试数据的选取，尤其对边界值分析有着直接的指导作用。程序定义域如何确定?就目前而言，大多是以程序规范 (specification) 说明的输入变量的取值范围为其定义域，其正确性依赖于规范的正确性。事实上，我们不能保证规范说明完全正确。虽然程序规范规定了输入变量的定义域，但程序实现本身也定义了其定义域。软件规范给定的功能是定义在输入空间的一个所谓功能域 D f 上，而被测程序本身定义了输入空间的一个所谓运行域 D p 。正如 [4] 指出的，在需求阶段，系统由功能 (function) 来给定，而在开发和运作中，系统将由运行 (operation) 来描述。功能域 D f 和运行域 D p 是否相等，如果两者不能完全重合，那么某些软件错误就可诊断出来。但是，两者完全重合，并不说明软件没有错误。对于那些不能从定义域中反映出来的错误，可采用等价划分、逻辑覆盖、错误推断等测试方法进行检测。
一般而言，输入空间可表示为： E = E 1
E 2
E 3
E 4 , 其中 E 1 =D f
D p , E 2 =
f
D p , E 3 =D f
p ， E 4 =
f
p 。 E 1 表明规范和程序有相同的输入子域，但实现与说明是否一致，还需进一步研究。 E 2 表明程序产生了一个结果，但规范并没有要求。对于这种情况，要么补充规范，要么缩小其程序的运行域。 E 3 表明规范的某些要求，程序没有处理。这显然是不允许的，应该修改程序。 E 4 关于例外处理，即规范既未要求，程序也无从处理。在高可靠的软件中，例外处理必不可少。如果我们能够得到被测程序的定义域，那么不仅可以进行程序定义域的重合验证，而且还可以得到输入子域 E 1 、 E 2 、 E 3 、 E 4 。根据其规范说明与程序实现之间的差异，选取测试用例，可以克服测试的盲目性，有效地提高测试效率。因此，从程序本身探讨其定义域非常必要，然而对于这一重要问题，很少有文献提及。
为此，本文提出了一种基于数据流分析的程序定义域自动确定方法，从程序结构本身出发，通过对源程序进行数据流分析和相关性分析，实现其定义域的自动确定;采用动态模拟( dynamic stimulation )技术确定一些特殊情形下输入变量的定义域。该方法的实现为边界值分析、测试数据的自动生成提供了一种新的、有效的途径，为程序定义域的重合验证奠定了基础。
2 基本概念
数据流分析 (data flow analysis) 在软件开发、测试和维护中起着十分重要的作用。它将程序中变量的出现分为变量的定义 (definition) 和引用 (use) ，若语句 I 实现对变量 v 存储单元的赋值，则称 I 定义变量 v ;若语句 I 引用变量 v 存储单元的值，则称 I 引用变量 v [5,6,7] 。
由于应用的领域不同，分析数据的属性也有所不同。我们的方法将每条程序语句看作一个结点，方法中涉及的有关概念定义如下：
定义 1 程序定义域 D:
程序各输入变量取值范围的笛卡尔乘积，构成其定义域 D [8] 。
即 D =Dx 1 ′ Dx 2 ′ … ′ Dx n ={ ( x 1 ， x 2 ， ... x n ) ? " x 1 ? Dx 1 , " x 2 ? Dx 2 , … , " x n ? Dx n } 。
其中 x i ( i=1 ， 2 ， n )是程序的输入变量， Dx i 是 x i 所有可能的取值。
定义 2 变量 v 的定义集 def (v) ：
def (v) 由定义变量 v 的所有结点组成。
即 def (v)={i ? 结点 i 定义了变量 v} 。
本方法中，定义不仅指对变量的赋值，变量的类型说明，函数入口结点对参数的说明都看作是对变量的定义。
定义 3 变量 v 的引用集 use (v) ：
use (v) 由引用变量 v 的所有结点组成。
即 use (v)={i ? 结点 i 引用了变量 v} 。
定义 4 定义变量 v 的引用变量集 indef (v) ：
indef (v) 由定义变量 v 时所引用的变量组成。
即 indef ( v)={x ? 变量 v 的定义中引用了变量 x} 。
例如： v = x + y - z ;
则 ： indef ( v) = { x , y , z }
定义 5 引用变量 v 的涉及变量集 inuse (v) ：
inuse (v) 由引用变量 v 时所涉及的变量组成。
即 inuse (v)={x ? 引用变量 v 时涉及了变量 x} 。
例如： if ( v > x + y ) ;
则 ： inuse (v) = { x , y }
定义 6 程序表示等价：
定义函数 exec 是从程序集及其定义域到输出的影射，即
program_set ′ input_set ? output_set
或 exec(program,input)=output,
如果对任意的 input ， exec(program_p , input)=exec(program_p' , input), 则称程序 P 和 P' 表示等价。
3 程序定义域自动确定的实现
我们以结构良好的 C 语言程序为例进行研究。同时要求源程序能通过编译并运行。
3 .1 主要算法思想
基于数据流分析的程序定义域自动确定方法，采用程序抽取技术，通过对源程序进行数据流分析及相关性分析，从中抽取出与自变量(输入变量)相关的部分，剔除与自变量无关的语句及函数。只分析与自变量相关的部分，可以简化程序定义域的求取，提高分析效率。
程序抽取 (program slicing) 是一种广泛应用于程序调试、软件测试及维护的技术。它从被测程序中抽取出与故障代码相关联的语句，忽略了许多与此无关的语句，减少了故障因素的分析范围，有利于故障原因的定位 [9,10,11,12] 。
本文方法采用两种程序抽取算法，基于自变量的程序抽取和基于标准 C = (I ， q ， V) [11,12] 的程序抽取 (q 为有特殊取值要求的表达式， I 为 q 对应的结点， V 为 q 中变量的集合 ) ，其主体结构如下：
while ( input file name)
{
create_table (filename_p);
program_slicing (filename_p,newfile_ p' );
create_table (newfile_ p' );
domain_determine (newfile_ p' , slicefile);
}
源程序 P 以文件形式读入，由 create_table (P) 生成关于 P 的各种表格;依据其信息， program_slicing ( ) 从 P 中抽取出与自变量有关的部分 P' ; domain_determine ( ) 根据 create_table (P') 生成的新表格，完成自变量的定义域确定。对一些特殊情形，进行基于标准 C = (I ， q ， V) 的程序抽取，动态模拟求其定义域。
3 .1 .1 建立源程序 P 的各种表格 create_table ( p )
逐行扫描源程序 P ，对其每一函数 i ，建立函数参数表、函数调用表、变量表、自变量表及复合语句表等。其中函数参数表记录与该函数有关的各种信息;如函数名、形参名、形参个数、函数中定义的变量数、涉及的自变量数、被调用函数的数目等。函数调用表记录被调用函数的名称、实参等信息;变量表是数据流分析中最关键的数据结构，记录函数所定义变量的名称、类型及其 def( ) 、 use( ) 、 indef( ) 、 inuse( ) 等信息;自变量表记录函数中出现的自变量，同时在变量表中有关于自变量定义、引用的详细信息。
对于数组变量，数组元素 a[e] 的定义看作是对数组 a 的定义，其 indef (a) 由表达式 e 中所引用的变量和赋值号右边所引用的变量组成;数组元素 a[e] 的引用看作是对数组 a 的引用，其 inuse (a) 由表达式 e 中所引用的变量及引用 a[e] 时所涉及的变量组成。
例如： a[ i + j ] = a [ k - 3 ] + v ;
则： indef ( a ) ={ i , j , a , k , v } 。
对于指针变量，其变量的定义、引用类似于简单变量的定义、引用，只是它的变量类型带有 * ，以表明是指针变量。
3 .1 .2 基于自变量的程序抽取 program_slicing( )
基于自变量的程序抽取，根据 create_table (P) 生成的表格信息，分析变量的定义引用关系、相关性以及函数调用关系等，从源程序 P 中抽取出与自变量相关的部分 P' ，剔出与自变量无关的函数和语句 (include ， break 等除外 ) ，并且保证 P' 结构完整;同时就自变量而言，抽取出的程序部分 P' 和源程序 P 二者表示等价，即 exec (P , input ) = exec (P' ,input ) 。
program_slicing( ) 实现基于自变量的程序抽取，其算法如下：
program_slicing( P ， P' )
{
从 P main( ) 函数的各种表格开始。
1 扫描变量表 variable_scan( )
对变量表中的每一个变量 v ;
if ( v为自变量 )
则 def(v), use(v) 中的结点， def(x) ? 变量 x ? inuse(v) 中的结点是 P' 中的结点。
else if (x 为自变量 ? x ? indef(v) ú x ? (indef...(indef(v)) ú x ? inuse(v) )
则 def(v), use(v) 中的结点是 P' 中的结点 .
2. 复合语句处理 component_process( ) // 保证程序结构完整 //
对每一个复合语句K
if ( 结点 i ? K ? i ? P' )
则K的源结点、开始点、结束点、 K 中的 break ， continue 等结点是 P' 中的结点。
// 源结点对应于条件或循环控制语句 //
else if ( K的源结点 ? P' ù K 中有 break 等结点时 ) 其 break 结点是 P' 中的结点。
else 将K的源结点从 P' 中去掉。 // 复合语句 K 与自变量无关 //
3 . if ( 结点 i ? P' ? i ? 函数 ) 则将函数的源结点、开始点、结束点放入 P' 中。
4 .被调用函数处理 called_func_ process( )
对函数调用表中未处理的被调用函数，根据其函数名，找到函数参数表，重复1、2、3、4步，将与自变量相关的结点放入 P' 中。
5 . P' 结点从小到大排序。
6 .根据 P' 的结点，从源程序中抽取出相应的语句，组成新程序 P' 。
}
例 1 给出源程序 P ，它由函数 main( ) 、 xpoint( ) 、 f( ) 及 power( ) 组成，其自变量为 x 。
例 2 给出新程序 P' ，去掉了与自变量 x 无关的变量 k 及其相关语句和函数 power( ) ， P' 变量和函数都与自变量 x 有关。
例 1 ：源程序 P ：
1 int power(int x, int i)
2 {
3 int p;
4 for(p=1;i>0;--i)
5 p=p*x;
6 return(p);
7 }
8 float f(float x)
9 {
10 float y;
11 y=((x-0.5)*x+16.0)*x-80.0;
12 return(y);
13 }
14
15 float xpoint(float x1)
16 {
17 float y;
18 y=x1*f(x1)/(f(x1)-f(3.453));
19 return(y);
例 2 ： 新程序 P' ：
1 float f(float x)
2 {
3 float y;
4 y=((x-0.5)*x+16.0)*x-80.0;
5 return(y);
6 }
7 float xpoint(float x1)
8 {
9 float y;
10 y=x1*f(x1)/(f(x1)-f(3.453));
11 return(y);
12 }
13 void main()
14 {
15 float x,y;
16 scanf("%f",&x);
17 y=xpoint(x);
18 printf("%f",y);
19 }
20 }
21 void main()
22 {
23 int k;
24 float x,y;
25 k=0;
26 scanf("%f",&x);
27 k++;
28 printf("%d%d%d\n",k,power(2,k),power(-3,k));
29 y=xpoint(x);
30 printf("%f",y);
31 }
3 .1 .3 建立程序 P' 的各种表格 create_table ( P' )
生成新程序 P' 的函数参数表、函数调用表、变量表、自变量表等。
3 .1 .4 程序 P' 的定义域确定 domain_determine ( )
按语法制导方法对程序 P' 进行词法和语法分析，根据自变量的类型说明及 create_table (P') 提供的信息，确定其自变量的定义域。但对一些特殊情形，应分别加以考虑。
1 字符串自变量
若程序中含有某些字符函数，比如 atoi( ) ， atol( ) ， atof( ) ， strtol( ) 等，将字符串转化为数值量，转化后的结果应在一定的取值范围内，这时字符串变量的取值应满足转化后数据的定义域要求。如例 3 。
例 3 ：程序 P' ： 例 4 ：程序部分 P" ：
1 void main()
2 {
3 char name[20];
4 char numstr[20] ;
5 unsigned short num;
6 float score;
7 gets(name);
8 gets(numstr);
9 num=atoi(numstr);
10 score=atof(numstr);
11 }
例 4 ：程序部分 P" ：
1 float f(float x)
2 {
3 float y;
4 y=((x-0.5)*x+16.0)*x-80.0;
5 return(y);
6 }
7 float func1(float x1)
8 {
9 float y;
10 y=f(x1)-f(3.453);
11 return(y);
12 }
例 3 中自变量 name, numstr 最多允许输入 19 个字符(缓冲存储器的最后一个字符为结束符)， numstr 转换后结果应在转化函数 atoi( ),atof( ) 限制的范围内，还应满足赋给变量的取值要求。如语句 9 ，不仅要求输入字符串转化后的结果在整数的范围内，而且还应是无符号的短整数。 domain_determine ( ) 给出其定义域见实验结果部分。
2 整型、实型自变量
若 P' 中自变量或与自变量相关 的式子，出现在一些有特殊取值要求的表达式中。例如表达式做除数或做一些标准函数的实参(如
、log (x)、acos (x)、asin (x)等)，要求变量x在一定范围内取值。
如果 P' 考虑了表达式的特殊取值要求，假设例 2 的语句 10 为：
if ( ( f(x1) - f(3.453) ) != 0 ) y = x1*f(x1)/(f(x1)-f(3.453) );
则自变量 x 的取值不受表达式 q: f(x1)-f(3.453) 的约束。由于程序设计非常灵活，条件判断 if ( f(x1) - f(3.453) ) ， if ( f(x1) != f(3.453) ) , if ( f(x1)f(3.453) ) 与上述条件判断等价。识别等价表达式又涉及语义分析，语言理解，其自动实现相当困难。但若不考虑 q 的取值限制，可能又会造成系统失效。因此，不论 P' 是否考虑了表达式 q 的特殊取值要求，我们都对其自变量进行取值分析。
已知表达式 q ： X ? Y 及值域 ran q ，由 q -1 可求其自变量的取值范围。即若存在逆函数 q -1 ： Y ? X ，则对于 " y y ? ran q 有 x = q -1 ( y ) ù x ? dom q ，自变量 x 的定义域 dom q = {x ? " y y ? ran q ù x = q -1 ( y ) } 。但对于 y ? ran q ， q -1 ( y )是否存在，即使存在，能否从 q 求出 q -1 。如例 2 中表达式 q = f(x1) - f(3.453) ，而 f = ( (x - 0.5)*x +16.0)*x - 80.0 ， q -1 计算十分复杂。通过函数求逆，分析自变量的取值范围，实现困难。为此，我们采用动态模拟， 确定 q中自变量的取值要求。
首先，进行 基于标准 C = (I ， q ， V) 的程序抽取(其中 I 为表达式 q 对应的结点， V 为 q 中变量的集合)。通过分析变量 v (v ? V) 的定义引用关系及其相关性，从 P' 中抽取出影响或间接影响 I 处表达式 q 及变量 v 的所有结点和函数，对其进行加工处理， 形成 可执行部分 P" 。 使得在结点 I ，对于任意的输入， P' 相对于表达式 q 的执行结果和 P" 相对于 q 的执行结果相同。 然后，根据表达式 q的值域要求，将 P" 与事先编制好的相应处理函数连接成一个完整的可执行程序。执行该程序，得到 q中自变量的取值范围。
为描述抽取算法，先定义几个关系和符号：( K ， J 均为结点)
DU 关系： 定义 (definition) ——引用 (use) 关系
K DU J ：结点 K 定义了变量 v ，结点 J 引用 v 。即 K ? def(v), J ? use(v) 。
PC 关系： 谓词 (predicate) ——控制 (control) 关系
K PC J ：结点 J 在谓词 K 的直接影响范围内，即 K 对 J 有最直接的控制行为。 主要针对： If K then B1 else B2
While K do B ( J ? B1 ú J ? B2 ú J ? B )
FC 关系： 函数 (function) ——控制 (control) 关系
K FC J ：结点 J 属于某一函数或调用了某一函数， K 为函数说明结点。
A 0 ： 对 V 中变量有直接影响的结点集。
A 0 = LD ( I ， V )
LT ( I )
其中： LD ( I ， V ) = 结点 I 之前，对 V 中变量最后一次赋值的结点;
即： LD ( I ， V ) = { K ? K = max { K ? def (v) ù ( K < I ) , v ? V} }
LT ( I ) = 对 I 有直接影响的控制行为。
即： LT(I) = { K ? K 满足( K PC I ) ú ( K FC I ) }
算法实现：
① 求A 0
② 令 S 0 = A 0
③ S i+1 = S i è A i+1
A i+1 ={K ? ( K < I ù K ? S i ù $ J J ? S i )满足 K R J ， R = DU
PC
FC }
重复第 3 步，直到 A i+1 为空。因程序语句有限， A i+1 最终变为空，算法终止。
定义在 P' 结点集上的并运算
具有封闭性，所以 S i+1 中的结点属于 P' 。 令 P" = S i+1
I，根据 P" 中结点， 从 P' 中抽取出相应的语句，并将q所在函数更名为 funci (第 i 个表达式 q ) , 以保证原函数的完整性;修改函数值为q，加上函数返回语句，形成完整的函数 funci 及 P" 。
如例 2 中，自变量 x 为函数 xpoint( ) 的实参，函数 xpoint( ) 中结点 10 对应的表达式 q ： f ( x1 ) - f ( 3.453 )作除数。 X 应如何取值才能保证 f ( x1 ) - f ( 3.453 )不为零?基于标准 C = ( 10 ， q ， {x1} )的程序抽取，从 P' 中抽取出影响表达式 q 及变量 x1 的所有结点和函数，对其进行加工处理，形成函数 func1 及 P" ，见例 4 。
3 .2 用动态模拟求取定义域
因表达式 q 只有几种可能情形，如作除数，开方，求导等。根据表达式 q 可能的出现情形，事先编制好相应的处理程序，放在相应的头文件中， 然后分析程序中表达式 q的具体出现情形及值域要求，将 P" 与相应处理函数连接成一个完整程序。运行该程序，即可得其输入变量的取值要求。
例如，例 2 结点 10 对应的表达式 q 作除数，其类型为 float ，将用模拟求解方法编制的实现浮点通用函数 divi_float( ) 求根及取值分析的处理函数 fdivi( ) ，放在头文件 float_divi.h 中，将头文件 float_divi.h 加入 P" ，定义函数 divi_float( ) 为 func1( ) ，在 main( ) 函数中调用浮点处理函数 fdivi ( ) ，实现对自变量 x 的取值分析。 完整程序 见例 5 。
例 5 ：完整的程序：
1 float f(float x)
2 {
3 float y;
4 y=((x-0.5)*x+16.0)*x-80.0;
5 return(y);
6 }
7 float func1(float x1)
8 {
9 float y;
10 y=f(x1)-f(3.453);
11 return(y);
12 }
13 #define divi_float func1
14 #include"float_divi.h"
15 void main()
16 {
17 fdivi();
18 }
运行 P" 与相应处理函数连接成的完整程序，即可得自变量 x 的取值范围。结果见第 4 部分。
所有自变量的取值范围构成了程序定义域。
4 实验结果
为验证本文所提方法的有效性，我们研制了 C 程序定义域自动确定系统，对多个 C 语言程序，进行了定义域模拟求取实验。虽然每个程序仅由几十行语句组成，但却涉及了复杂的控制关系以及单输入变量、多输入变量、自变量表达式、字符串自变量有特殊取值要求等情形，实验结果与预期结果相同，表明该方法有广泛的适用性，是确实可行的。
对例 1 ，定义域自动确定系统运行结果为：
3.452942 cannot be assigned to the input variable x.
对例 3 ，其运行结果如下：
The domain of string 'numstr' corresponding 'num' is between 0 and 65535.
The domain of string 'numstr' corresponding 'score' is between -1E308 and 1E308.
The length of string variable 'name' is between 0 and 20-1.
The length of string variable 'numstr' is between 0 and 20-1.
即：程序自变量 name, numstr 最多允许输入 19 个字符，相应于整数 num 的输入串 numstr 转化后的结果应在 0 和 65535 之间，相应于浮点数 score 的输入串 numstr 转化后的结果应在 -1E308 和 1E308 之间。
分析结果和实际定义域相符。
5 结论
本文介绍了一种基于数据流分析的程序定义域自动确定方法，该方法从程序结构本身出发，实现了输入变量定义域的自动确定。通过采用程序抽取技术，剔除与自变量无关的语句及函数，大大简化了程序定义域的求取，降低了分析成本，提高了分析效率;而且对被测源程序的结构、功能、性能均不产生任何影响。应用前景十分广泛，对软件测试过程的自动化有着积极的作用。为后续程序定义域的重合验证奠定了基础。当然，要想开发出一个高效、实用的程序定义域自动确定工具，还需做大量的工作和进一步扩充与完善。
参考文献
• Zheng Ren-jie, "The Technology of Computer Software Testing ", TsingHua University Press. Beijing ,1992.
( 郑人杰，计算机软件测试技术，北京：清华大学出版社， 1992 )
• Sandra Rapps and Elaine J.Weyuker, "Selecting Software Teat Data Using Data Flow Information", IEEE Trans. on Software Eng., vol. SE-11, No. 4, April 1985, pp. 367-374.
• B. Marick, "The Craft of Software Testing", PTR Prentice Hall, NJ, 1995.
• M.R.Lyu, Editor, "Handbook of software reliability engineering", IEEE Computer Society Press, CA, 1996, pp.850.
• M. S. Hecht, "Flow Analysis of Computer Program", Amsterdam, The Netherlands: North-Holland, 1977.
• P. G. Frankl and E. J. Weyuker, "A Data Flow Testing Tool", in Proc. IEEE Softfair II , San Francisco, CA, Dec.1985.
• Phyllis G. Frankl and Elaine J.Weyuker, "An Applicable Family of Data Flow Testing Criteria", IEEE Trans. on Software Eng., vol.14, No.10, Oct.1988, pp. 1483-1497.
• Bogdan Korel, "Automated Software Test Data Generation", IEEE Trans. on Software Eng., vol.16, No.8, Auguest.1990, pp. 870-879.
• Bogdan Korel and Janusz Laski, "Dynamic Slicing of Computer Program", J. Systems Software 13, 1990, pp. 187-195.
• Tip,F., "A Survey of Program Slicing Techniques", Journal of Programming Languages, Sept.1995, 3(3), pp. 121-189.
• Tibor Gyimothy, Arpad Beszedes and Istvan Forgacs, "An Efficient Relevant Slicing Method for Debugging", Software Engineering Notes, vol.24, No.6, 1999, pp.304-312
• Gerardo Canfora, Aniello Cimitile and Andrea De Lucia, "Conditioned Program Slicing", Information and Software Technology, 1998,40,pp.595-607.
文章来源于领测软件测试网 https://www.ltesting.net/
