设为首页 | 加入收藏夹

八文网 - 汇聚八方文档 - 做最优秀的免费文档下载网站

论文分类号

文档类型：

Microsoft Word 文档文档大小：1.05M

论文分类号TP31 单位代码10183密级内部研究生学号吉林大学硕士学位论文小型面向对象语言程序测试用例自动生成技术Test Case Auto Generation Technique ofSmall Language Program
作者姓名:田晨
专业:计算机软件与理论导师姓名刘磊及职称教授
论文起止年月: 2001年12月至2003年4月提要程序测试是保证软件系统和产品达到高质量和高可靠性的重要手段,它代表了对规约,设计和编码的最终审查.
本文使用信息流分析技术,对面向对象语言编写的程序自动生成测试用例.信息流分析技术又称程序流分析技术,是一种静态分析技术,即在一个程序没有被实际运行之际、通过静态分析去发现它的一些运行行为方面的特性.信息流分析包括控制流分析和数据流分析两种、其中控制流分析侧重于对程序结构的分析,而数据流分析侧重于对变量控制结构下的定值,使用以及传播情况的分析.
本文属于基于代码的白盒测试.首先定义了一个面向对象语言Small 然后通过自己建造的词法和语法分析器对SOOL构造出语法树,接下来在语法树上进行数据流分析和控制流分析,利用部分求值技术和程序分析技术找到满足条件组合覆盖策略和类覆盖策略的执行路径,分析可能产生分支的语句,构造包含所有执行路径的路径二叉树,对路径二叉树上的条件表达式进行分类和化简整理,由规范条件表达式生成梯度表达式,最后根据梯度表达式生成测试用例.
目录
第一章引言
1.1 程序测试技术
程序设计行家说:任何程序,无论多么小,都有错误.如果小到了只能执行单一功能,这样的程序不会有任何意义、假如这样的程序存在,操作系统最终也会由于一个错识而失效.没有错误的程序是荒唐可笑的,是不可能存在的.假如存在没有任何错误的程序,那么世界也不复存在.①无论怎样强调软件测试的重要性和它对软件可靠性的影响都不过分.在开发大型软件系统的漫长过程中、面对着极其错综复杂的问题,人的主观不可能完全符合客观现实,与工程密切相关的各类人员之间的通信和配合也不可能完美无缺、因此,在软件生命周期的每个阶段都不可避免地会产生差错.我们力求在每一个阶段结束之前通过严格的技术审查,尽可能早地发现并纠正差错;但是,经验表明审查并不能发现所有的差错,此外在编码过程中还不可避免地引入新的错误.如果的软件投入生产性运行之前、没有发现并纠正软件中的大部分差错,那么这些差错迟早会在生产过程中暴露出来,那时不仅改正这些错误的代价更高,而且往往会造成很恶劣的后果.测试的目的就是在软件投入生产性运行之前、尽可能多地发现软件中的错误.目前软件测试仍然是保证软件质量的关键步骤,它是对软件规格说明,设计和编码的最后复审.⑦面向对象测试是面向对象技术的重要方面.随着面向对象开发方法和面向对象程序设计语言的广泛使用,用户采用对象技术开发的软件和产品也日益增多.测试是保证软件系统和产品达到高质量和高可靠性的重要方面,它代表了对规约,设计和编码的最终审查.有关面向对象测试研究也受到软件界的重视.
正如对于过程式程序设计语言、从过去几十年有时甚至是痛苦的经历中所认识到的,每一个进步都有其代价;就面向对象而言、导致更大灵活性,健壮性,一般性和高生产率的真实东西,也是要求测试的东西,如果不是更为困难,至少也更具挑战性.在过程式语言中、单元测试处于重要地位、而集成测试次之,但在面向对象语言中、这种相对重要性恰好相反.面向对象程序设计给测试者带来很多新的问题,这些问题是过程式语言中没有的.在这些问题中、多态、继承和动态绑定是最容易出问题的地方、而它们又是面向对象的核心.
本文主要针对继承,发消息机制对程序进行基于类覆盖策略的测试用例生成,生成的测试用例侧重于覆盖类中所有的数据成员及成员函数.
1.2 测试用例自动生成技术软件测试是十分繁重困难的脑力劳动过程,测试工作量通常占软件开发总量的40%以上.为了既快又好地完成测试工作,开发自动测试工具是十分必要的.自动化的程度及其发挥的作用取决于测试目标,预算,软件过程,开发的应用类型以及开发环境和目标环境的细节.
下面介绍几种典型的应用:
1.2.1 测试数据生成程序这种程序可以为测试某个系统而自动产生量的输入数据,但是它不能自动产生预期的输出、因此用途有限制.当必须测试某个系统在实际环境中的性能时,测试数据生成程序特别有用.例如,为了测试一个数据库管理系统,应该使用非常大的数据库,在这种情况下,可以使用测试数据生成程序,产生需要的大量数据.当能够形式地说明某个系统的输出数据的语法时,测试数据生成程序也很有用,因为在这种情况下可以写一个程序自动校核被测系统的输出结果.例如,在测试一个编译程序的语法分析功能时,如果输入语法正确的源程序,则编译程序的输出应该就是输入的程序,否则输出中还应该包含指示错误的信息.测试数据生成程序接受被编译的语言的语法说明,根据语法产生正确和错误的源程序作为测试数据.在这种情况下,它可以自动检验被测试的编译程序的输出.
1.2.2 动态分析程序动态分析程序的主要功能是分析被测试程序中每个句的执行次数.它有两个基本部分:1,检测部分:它往往被分析的程序中插入检测语句,当程序执行时,这些语句收集和整理有关的每个语句执行次数的信息.2,显示部分:它汇集检测语句提供的信息,并以某种容易理解的形式印出这些信息.为了检测执行次数,应该找出所有判定语句和循环语句,并在每个循环和判定的开始处放置检测代码.不包含循环或分支的一串顺序语句,只需在它们的开始处放置检测代码.为了设置检测代码、需要了解这种语言的语法,所以在普通的编译程序中、增加检测功能是实现这种功能的一种方便途径,用户可以通过编译命信令选择使用这个功能.另一种途径是用预处理程序在被测试程序中插入高级语言、以便收集有关程序执行的信息.动态分析程序在软件测试中很有用,利用它可以发现测试过程中没有执行的语句,以便增加相应的测试数据.在调试过程中动态分析程序也能起到重要作用,利用它可以发现不按预定要求终止的笔循环,也可以发现不应执行而实际执行的代码、或者应该执行而实际上没有执行的代码.
1.2.3 静态分析程序静态分析程序不需要执行测试的程序,它仅仅扫描被测试程序的正文,从中寻找可能导致错误的异常情况,例如,使用了一个尚未赋值的变量;赋了值的变量始终未被使用;实在参数和形参的类型或个数不符;永远执行不到的程序段对于像FORTRAN这样的语言、因为在编译期间可以做的检查不多,所以静态分析程序很有用.DAVE,AUDIT和FACES等系统都是用于FORTRAN程序的典型静态分析程序.当然,静态分析程序并不仅限于FORTRAN程序,LINT系统就是为分析C程序开发的.因为LINT可以对C程序进行的静态检查的严格程度,相当于ALGOL68编译程序可以对ALGOL68源程序提供的检查的严格程度,所以它把一种严格类型语言的可靠性优点、与系统实现语言生成非常高效代码的能力结合起来.
1.2.4 文件比较程序一般说来,测试过程需要检查的输出结果数量极大.这是一件非常单调乏味的工作,而且由于一时疏忽而漏过错误的输出.因此,检查测试结果的过程应该尽可能自动化.自动检查测试结果的过程主要由下述几步组成:1,建立一个文件存放预期的正确结果;2,执行测试,并把输出数据存在一个文件;3,使用文件比较程序来比较上述两个文件,印出两者之间的差异.
本文大体上属于第一种和第三种工具的结合,利用信息流分析技术,对程序进行静态分析,生成测试用例.
1.3 信息流分析技术信息流分析技术又称程序流分析技术,是一种静态分析技术,即在一个程序没有被实际运行之际、通过静态分析去发现它的一些运行行为方面的特性.信息流分析包括控制流分析和数据流分析两种、其中控制流分析侧重于对程序结构的分析,而数据流分析侧重于对变量控制结构下的定值,使用以及传播情况的分析.二者相辅相承,不可分开.
信息流分析技术最早被用于编译优化,目前除编译优化外,在程序测试,程序理解,程序验证、程序调试以及程序分片等许多领域,信息流分析都有广泛的应用.
下面介绍几个信息流分析的应用:
1.3.1 编译优化编译优化是信息流分析最早的应用领域.当程序设计发展到出现高级程序设计语言时,程序设计者不再关注那些依赖于具体机器的实现细节,用高级语言编写程序更为容易,程序的通用性和可读性大大增强.但是,用高级语言编写的程序的执行效率却大大不如用汇编语言编写的程序.这也正是因为它不依赖于具体机器的通用性阻碍了程序员利用某一机器的物理特性去编写更有效的代码.虽然如此,程序设计科学的发展方向仍然是应该朝着在更为抽象的层次上去设计程序,从而增强其通用性和可读性这一主要方向的.因此,要提高程序的执行效率,就必须从改进编译器入手,改进由编译器产生的目标程序的效率,进行编译优化.这里所说的优化并不是修补拙劣的程序,而是在合理的限内应用提高目标代码的效率.利用信息流分析技术,可以对程序进行优化.如常表达式的优化,公共了表达式的优化,无关代码移动,削减运算强度和寄存器的分配等.
1.3.2 程序测试程序测试是软件开发的重要环节,程序静态信息流分析是程序测试所采用的一种主要手段.利用数据流分析可以找出数据流中的异常现象,如引用在前定值在后,重复定值以及只定值不使用等情况;利用控制流分析,可以确定测试路径,对于路径覆盖策略,点覆盖策略,条件组合策略,语句覆盖策略,具有有效的手段.
1.3.3 程序理解规模庞大的软件系统是难于理解和维护的.目前已经有了许多不同的方法和自动化工具,它们或者在体系结构层,或者在代码层,建立存在系统的概念模型,帮助人们对系统进行理解和维护.信息流分析技术可以给用户提供分析程序的有关信息,从而有助于用户对程序的理解.
1.3.4 程序分片程序分片工具是基于代码分析的,它允许将程序分解成片,用户能够从中提取信息并且使维护中改变代码所带来的影响变得更加直观.利用信息流分析进行分片是程序分片技术的一个重要分支,值得一提的是最早的分片算法就是WEISER的以控制流图作为中间表示的基于数据流关系的分片算法.
1.4 模型语言我们的分析对象是一种小型的面向对象程序设计语言SOOL,它是从C简化和修改得来.我们保留程序的主干,即保留顺序,分支,循环语句以及简单的面向对象机制,即类,继承,发消息.考虑到实现的方便,SOOL只保留了基本数据类型和基本算术运算.
下面我们给出SOOL语言的语法描述:
program:
(class_sect) main_program;
head_file;
head_file:
MAIN
MAIN statement_sect;
|VOID;
|BOOL;
{ (declare_sect) stm_sect ;
varible ; ( type varible ;);
|class_type;
;
;
|IDENTIFIER [ NUMBER ;
|statement stm_sect;
|if_statement||io_statement||skip_statement;CLASS
class_sect:
CLASS class_name ( : PUBLIC class_name)
{ : ) ;
;|PROTECTED|PRIVATE;|;
varible;
function_name ( ){ (RETURN varible ;) } ;
{ basic_stm_sect ;
varible ; ( varible ;);
{ { basic_stm_sect ;
|skip_statement|new_statement|;
function_name:
;EXPRESSION
sign:
expression:
|||IDENTIFIER; expression;
|NOT_EQUAL||LESS_EQUAL|GREAT_EQUAL;
(expression) bool_operator expression;
|OR|NOT;
(sign) item item);
item:factor factor);
factor:
varible|NUMBER|( expression ) | ;
. ;
( );
(, ;
|TRUE|FALSE|varible; = expression ; ;
if_statement:
IF ( expression ) basic_stm_sect ELSE basic_stm_sect;
( expression ) basic_stm_sect;
io_statement:
class_name ;
class_name ;
说明:
从形式语言的角度看,一个语言不过是字符串集.如果字符串集是有穷的,那么我们就可用枚举的办法来表示.但当集合为无穷时枚举的办法就不再适用.
文法是表示无穷字符串集的强有力的一种有限办法.表示文法需要工具,其中最常用的工具是所谓的巴克斯范式(BNF).
这里的文法是用一种类似于巴克斯范式方式给出、但它又不是纯粹的巴克斯范式.之所以表示成这种形式是在不影响其清晰性的前提下考虑到实现方便,具体地说这种文法能够为下面要介绍的工具ACCENT所识别、而且表达比较简捷.
该文法中大写的单词是终极符,小写的单词是非终极符,号加号表示重复0到多次,号加号表示重复0到一次,号中的是单字符终极符.
非终极符是指既可出现于产生式的左部,又可出现于产生式右部的符号;终极符是指只能出现于产生式右部的符号.在非终极符中有一个特殊符号,称之为文法的初始符号,在SOOL文法中就是Program.
1.5 本文的主要工作
1,用巴克斯范式构造出模型语言SOOL;
2,建造SOOL的语法树;
3,对程序进行信息流分析,从条件组合覆盖策略和类覆盖策略出发,依据SOOL的语法树建造路径二叉树;
4,对路径二叉树上的条件表达式进行分类,化简、对不同的情况采用各种办法生成测试用例.
第二章测试用例自动生成器的体系结构
2.1 使用工具介绍
2.1.1 ACCENT简介ACCENT是类似于YACC(Bison)的编译器构造工具,是一个共享软件,附有程序源代码、它是在unix(linux)上开发的,其全称为A Compiler Compiler for the Entire Class of Context-Free Languages.其功能是能自动产生某个语言的语法分析器.使用时,按照ACCENT所要求的格式给出输入文件,主要是指出语言的文法描述,ACCENT会自动产生出该语言的语法分析器yyparse.其网址为
2.1.2 ACCENT与YACC的比较ACCENT对文法不加任何限制,能处理所有的上下文无关文法;YACC只能处理LALR(1)类文法.ACCENT在处理文法时不会产生任何冲突;YACC受所处理文法类的限制,可能会产生SR或RR冲突.ACCENT产生的语法分析器分析效率略低;由YACC生成的分析器分析效率高.
2.1.3 ACCENT输入文件的格式全局定义部分token声明部分规则部分.
全局定义部分:用来定义一些函数,全局变量以及类型,这部分可空.
格式%prelude { c_code }用花括号括起来的部分为任意的C代码、它会原封不动的复制到ACCENT产生的语法分析器文件的首部.
token声明部分:用来声明文法中出现的所有的终极符(称为tokens),可空.
格式%token tk1,tktkn ;
ACCENT中的tokens分为两种:
(1). 多字符终极符,这类token必须用%token关键字声明如%token 等;
(2). 单字符终极符,称为literal token,这类token不必声明,用单引号引起来即可,可直接出现在产生式中.
如 = exp| IF exp THEN statement ELSE statement|
规则部分:文法中的产生式,应至少有一条规则.
格式:rule1 rulrulen
rulei: left_hand :right_hand ;文法中的每个非终极符都用一条规则来定义、第一条规则的左部为整个文法的开始符.
2.1.4 词法分析函数yylex 语法分析程序的输入是经词法分析后的token序列,而不是用户直接写的源程序,因此必须为ACCENT产生的语法分析器提供词法分析函数,函数名固定为yylex.yylex可以自己编写,也可以用Lex自动生成,其返回值为一个整数,表示所识别单词的类别.
Lex生成一个C文件,里面有词法分析函数yylex.
2.1.5 ACCENT中可以使用的文法描述手段1).局部选择(Local Alternatives)
格式:(alt_1 | | alt_n),可以避免引入新的非终极符.
如 NUMBER;
利用局部选择可以写成 | -) NUMBER;
2).可选符(Optional Elements)
格式:(M_1 .M_n)
意义:括号中的M_1 .M_n 可出现在输入中、也可以不出现.
例如 NUMBER;则123和123都是正确的输入.3). 星闭包(Repetitive Elements)
意义:表示括号中项目的任意次重复(包括0次).
例如 ( , NUMBER) ;
则都是合法的输入.
2.1.6 ACCENT语义动作ACCENT会根据文法产生语法分析程序来对用户的源程序进行语法分析:它拒绝所有不符合文法的输入.
为了对输入进行语义处理,需要指定语义动作.语义动作可以嵌套在文法的任意位置,当指定的分支匹配时,对应的语义动作也被执行.语义动作为用花括号括起来的任意C代码、这些C代码将会被原文拷贝到语法分析程序的适当位置.
例如有如下文法:
则对于输入ab,语法分析程序会产生如下输出:
3
2.1.7 ACCENT中非终极符的属性与程序设计语言中的函数类似,非终极符也可以有参数,这些参数可以在语义动作内访问.参数有两种模式:
1).in模式:是将信息从上下文传递到非终极符中、即继承属性.
2).out模式:将信息从非终极符传递到上下文中、称作综合属性.
下面是产生式左,右部参数的格式和用法:
a.若规则左部的非终极符带有参数,则其格式如下:left_hand
类型名参数名、类型名参数名.
其中类型名可选、如果类型名不写,则默认为YYSTYPE类型,YYSTYPE是一个宏,代表long类型,用户可对其重定义.如果一个参数既不加%in修饰,也不加%out,则默认为是综合属性.
例: Nb.产生式右部的非终极符如果有参数,则将其用尖括号括起来跟在该非终极符的后面.
例:N1).参数能在语义动作内访问,输入参数的值必须在语义动作内定义或者是其它文法符号的输出参数.
2).若非终极符有综合属性,则其每个分支都要定义输出参数并在语义动作内给其赋值.
3).在语义动作内使用左部非终极符的输出参数,需用操作符访问.
4).参数变量均不需定义.
例如:
demo:{}N{printf(%d\}N{;
经ACCENT产生的语法分析程序如下:demo{int actual_context; 参数变量不需定义int actual_result;{; 输入参数必须有值 actual_result); Printf(%d\;
}break; context;int result;; 输出参数必须赋值
2.1.8 ACCENT中Tokens的属性用%token语句声明的token都有一个YYSTYPE类型的输出参数,若要在规则的右部使用token,则可以为其指定一个实参来访问其语义值.
例如: Value: NUMBER{printf(%d\n,n)}这里n就表示NUMBER的数值(语义值),可以在语义动作内使用.
token语义值的计算:
一个token的语义值是在该token的词法规则的语义动作内被计算的,其值必须赋给YYSTYPE类型的系统变量yylval.比如我们想访问上例中的NUMBER的语义值,则相应LEX中的规则应改为:
[0-9] {; return NUMBER}变量yytext为当前匹配单词的字符串值.atoi是标准的C函数,将一个字符串转变成整数.
2.1.9 ACCENT中局部变量定义(Rule Prelude)
规则中使用的属性变量都不需定义.如果想在语义动作内声明其它变量即局部变量,则分下面两种情况:1). 该变量只对某一分支可见
如demo:2). 对规则内所有分支可见(但对其它规则不可见)
2.2 测试用例生成系统的总体结构
1. 系统读入用SOOL编写的源程序,这个程序存在一个文本文件上.
2. 作预处理.找到源程序中所有的WHILE语句,转化成三个IF语句,并填加循环标记.
3. 词法分析.使用工具FLEX,使源程序生成TOKEN序列.
4. 语义分析和生成语法树.根据文法表达和语义信息,建立SOOL语言的语法树,这样,读入程序后,可在语法树上识别和存储程序中的各个部分,所有的叶结点存储的即是程序源代码的TOKEN序列.
5. 类覆盖的路径查找处理.按照条件组合覆盖策略,类覆盖策略和路径覆盖策略,在SOOL语法树上静态查找程序可能执行到的路径.大体上细分为:
5.1 基本数据结构的建立与使用.基本数据结构是指五种表:类信息表,对象生存期表,变量信息表,函数信息表,输入变量表.
5.2 赋值,发消息语句处理.解决赋值,发消息语句对变量,函数以及对类的影响.
5.3 IF,WHILE语句处理.IF语句是产生执行分支的重要语句,根据IF语句的判断条件,寻找可能产生分支的判断.WHILE语句已经由预处理替换成带有循环标记的IF语句,要针对不同的情况分析其对判断条件的影响.
5.4 嵌套函数展开及处理.嵌套函数可出现在赋值语句,发消息语句以及IF语句的判断条件中;嵌套的函数可能是类中的函数,也可能是某个父类中的函数,要针对不同的情况,使用函数展开所需的函数展开栈进行处理.
5.5 路径二叉树的建立与使用.由IF语句产生的分支连在一起就组成了若干程序可能执行到的路径,用二叉树的方式把这些分支存下来,遍历二叉树就得到了所有的路径.
5.6 条件表达式的化简.在每一条路径上存在数个判断条件,经过代入计算,得到输入变量之间的条件表达式,化简至规范的形式.
6. 测试用例的生成.对每条路径上判断条件进行分类,对不同的类,按不同的策略生成测试用例.大体上细分为:
6.1 表达式梯度值的计算.对路径上条件判断表达式进行偏微分计算,结果为方向导数值,得到各表达式的梯度.
6.2 大于(等于)关系测试用例生成.对路径上条件判断表达式中为大于或大于等于关系的由梯度值生成测试用例.
6.3 等于关系测试用例生成.对路径上条件判断表达式中为等于关系的,按一元方程取相反数,二元方程用求根公式的方法生成测试用例.
6.4 用例回代变量链表求值.按一个条件判断表达式生成的用例,需要回代入后面的表达式中、检查是否满足.只有满足一条路上所有判断表达式的一组值,才是一条路上的测试用例.
6.5 回溯及遍历的控制.处理两种情况,一种是条路上到某一判断表达式不能满足的情况;另一种是一条路处理完毕,进行下一条路的处理,直至遍历.
7. 输出生成的测试用例结果.结果表示将以若干组输入值的形式给出、每一组输入值对应执行一条路径.
第三章SOOL的语法树结构
3.1 SOOL的语法树
3.1.1抽象语法树与中间代码测试用例生成系统面对的是一个SOOL文本源程序(经词法分析程序FLEX词法分析后生成TOKEN序列,但其结构与源程序相同)、要对源程序进行分析必须将其转换成中间表示形式.抽象语法树(AGT)是用于代码生成的最一般的中间代码形式,主要用来表示语句中出现的表达式.
某些语言需要多遍扫描,以便检查静态语义、这是因为该语言允许使用在定义之前.为了实现方便,我们规定SOOL不可以使用在前定义在后.对于使用在前定义在后的情形,第一遍扫描可以进行语法和词法分析,并建立抽象语法树和符号表;第二遍扫描可进行属性的计算和静态语义检查;再通过简单的树遍历,可进行独立于机器的优化,它是树到树的转换;最后,通过树遍历可直接产生目标代码、或产生更适合实际代码生成器或优化器的不同表示.
抽象语法树可使用于语义分析,中间代码优化和代码生成等方面.实际上,它的应用可以更为广泛.很多Ada实现都基于实际的抽象语法表示、称之为Diana.它的目的不仅仅在于编译器描述,而且还在于描述分别编译单位(包和过程)程序库的表示和作为其它的工具间公共界面.我们称Diana是抽象语法表示、而不称之为抽象语法树表示、原因是它是一个DAG而不是树.DAG实际上是从AGT发展而来的,其主要优点是能够描述共享问题.④假设有e =abcd 则其抽象语法树如下图:
三元式,四元式和抽象语法树之间存在着简单的互换性,其中抽象语法树的特点是没有固定计算顺序,而三元式和四元式则不同、故抽象语法树更具有一般性.
3.1.2 SOOL的语法树结构
SOOL语法树的主要部分结点结构:
1. SOOL程序由三部分组成:预包含部分,类部分和主函数部分.程序结点结构如下:其中标识为整型;其它三部分为指针,指向程序中各个部分.
2. 主函数部分结点结构如下:其中标识为整型;返回值类型为整型或布尔型;语句部分为指针,它指向主函数语句块.
3. 预包含部分结点结构如下:其中标识为整型;头文件名为字符型.
4. 类部分结点结构如下:
其中标识为整型;本类名为字符型;父类名为字符型,前面有访问控制符,是直接父类;类体部分指针,指向类中语句块.
5. 主函数语句块结构如下:
其中标识为整型;函数声明部分为指针,指向函数声明语句;语句块为指针,指向主函数语句.主函数语句分为赋值语句,IF语句,WHILE语句,输入输出语句,类函数调用语句以及空语句.
6. 类中语句块结点结构如下:
其中标识为整型;访问控制符为指针,指向或PRIVATE;类函数声明部分为指针,指向类中的函数声明语句;类语句块为指针,指向类中语句.类中语句分为赋值语句,IF语句,WHILE语句,类函数调用语句以及空语句.
7. 函数声明部分结点结构如下:其中标识为整型;类型为指针,指向类型结构;变量为指针,指向变量结构.
8. 赋值语句结点结构如下:其中标识为整型;变量为指针,指向变量结构;表达式为指针,指向表达式结构.
9. IF语句结点结构如下:
其中标识为整型;表达式为指针,指向表达式结构;语句块1为指针,指向语句块结构,这是当表达式为真时执行的语句块;语句块2为指针,指向语句块结构,这是当表达式为假时执行的诗句块.
10. WHILE语句结点结构如下:
其中标识为整型:表达式为指针,指向表达式结构;语句块为指针,指向语句块结构.在本文中、由于进行了预处理,WHILE语句全都被替换成带有循环标志的IF语句,这一部分实际没有用到.
11. 类函数发消息语句结点结构如下:其中标识为整型;类名为字符串型;函数名为字符串型;实参表为指针,指向函数发消息实参表结构.
12. 输入语句结点结构如下:其中标识为整型;输入变量表为指针,指向输入变量表结构.
13. 输出语句结点结构如下:其中标识为整型;输出变量表为指针,指向输出变量表结构.
14. 表达式结点是一个联合体,其结构如下:
其中标识为整型;简单表达式为指针,指向简单表达式结构;关系表达式为指针,指向关系表达式结构;布尔表达式为指针,指向布尔表达式结构.
15. 关系表达式结点结构如下:
其中标识为整型;表达式1为指针,指向表达式结构;关系操作符为指针,指向关系操作符结构;表达式2为指针,指向表达式结构.
16. 布尔表达式结点结构如下:
其中标识为整型;表达式1为指针,指向表达式结构;布尔操作符为指针,指向布尔操作符结构;表达式2为指针,指向表达式结构.
17. 简单表达式结构如下:
其中标识为整型;正负号为指针,指向正负号结构;项1为指针,指向乘除表达式结构;加减操作符为指针,指向加减操作符结构;项2为指针,指向乘除表达式结构.
18. 乘除表达式结构如下:
其中标识为整型;因子1为指针,指向变量,常数或带括号的表达式;乘除操作符为指针,指向乘除操作符结构;因子2为指针,指向变量,常数或带括号的表达式.
3.2 自动生成器存储信息的基本数据结构
3.2.1 类信息表结构
1. 类信息表结点结构如下:
其中类名为字符型;父类表为指针,指向直接继承的父类信息表;类中变量表为指针,指向类中成员变量表结点结构;类中函数表为指针,指向类中成员函数表结点结构;下一结点为指针,指向下一个类信息表结点结构.
2. 类中成员变量表结点结构如下:其中变量信息表为指针,指向变量信息表结构;下一结点为指针,指向下一个类中变量表结点结构.
3. 类中成员函数表结点结构如下:其中函数信息表为指针,指向函数信息表结点结构;下一结点为指针,指向下一个类中成员函数表结点结构.
3.2.2 对象生存期表结构
1. 对象生存期表结点结构如下:
其中对象名为字符型;类表为指针,指向自己拷贝的类信息表结点结构;对象中变量表为指针,指向对象中成员变量表结点结构;对象中函数表指针,指向对象中成员函数表结点结构;下一结点为指针,指向下一个对象生存期表结点结构.
2. 对象中成员变量表结点结构如下:其中变量信息表为指针,指向变量信息表结点结构;下一结点为指针,指向下一个对象中成员变量表结点结构.
3. 对象中成员函数表结点结构如下:其中函数信息表为指针,指向函数信息表结点结构;下一结点为指针,指向下一个对象成员函数表结点结构.
3.2.3 变量信息表结构变量信息表结点结构相对复杂,这主要是因为用它存储的信息较多.它可以用来存常数,一元运算操作符,算术操作符,变量的系数,输入变量表结点结构指针,函数信息表结点结构指针,以及指向自身结构即变量信息表结点结构的指针.其结构如下:
其中变量名为字符型;状态为整型,其值为分别表示该变量值为未知,已知,与循环有关,由输入变量决定;系数或常量,变量类型,输入变量表,函数信息表,变量信息表为一个联合体,这个联合体与操作符组成另一个联合体;操作符为字符型,存储一元算术运算符分,算术运算符及括号;系数或常量为整型;输入变量表为指针,指向输入变量表结点结构;函数信息表为指针,指向函数信息表结点结构;变量信息表为指针,指向变量信息表结点结构;下一结点为指针,指向下一个变量信息表结点结构.
3.2.4 函数信息表结构
函数信息表结点结构如下:
其中函数名为字符型;状态为整型,其值为分别表示该函数值为未知,已知,与循环有关,由输入变量决定;变量信息表为指针,指向变量信息表结点结构,用来存储函数参数信息;函数展开栈和变量信息表是一个联合;函数展开栈为指针,用来指向函数展开栈结点结构;变量信息表为指针,用来指向变量信息表结点结构;类信息表为指针,用来指向类信息表结点结构;下一结点为指针,指向下一个函数信息表结点结构.
3.2.5 输入变量表结构
输入变量表结点结构如下:
其中输入变量名为字符型;引用状态为整型,其值为0或1,表示在生成测试用例的时候在前面的判断中是否用到该变量;变量类型为整型,其值为0或1,表示其为实型或布尔型;变量值为整型,用来存储最终结果;下一结点为指针,指向下一个输入变量表结点结构.
3.3 计算条件表达式所用数据结构
3.3.1 操作符栈
操作符栈结构如下:其中操作符数组为字符型数组;栈顶为整型,用来记录栈顶位置;栈底为整型,用来记录栈底位置.
3.3.2 操作变量栈
操作变量栈结构如下:其中操作变量数组为整型数组;栈顶为整型,用来记录栈顶位置;栈底为整型,用来记录栈底位置.
操作符栈和操作数栈用来计算表达式的值.涉及到运算优先级问题,后面有详细说明.
3.4 嵌套函数展开所需的函数展开栈
函数展开栈结点结构如下:
其中函数名为字符型;对象名为字符型;变量值为指针,指向下一层函数的函数信息表;返回地址为指针,指向SOOL语法树中该函数的下一条语句;下一结点为指针,指向下一个函数展开栈结点结构.
3.5 路径二叉树
3.5.1 路径二叉树的结点结构路径二叉树是测试用例生成器重要环节,条件表达式的化简、规范表达式梯度的形成以及测试用例的最终生成都离不开路径二叉树.因此,路径二叉树的结点结构要适于这些操作.路径二叉树结点结构如下:
其中访问状态标志位为整型,其值为0,1,表示在测试用例生成的时候该路径被访问与否;条件表达式为指针类型,指向条件表达式表结点结构,在这里存储的条件表达式为一个链表;梯度表达式为指针类型,指向梯度表达式表结点结构,在这里可以存储规范条件表达式的梯度值,对于非规范条件表达式指向NULL;左子树为指针类型,指向路径二叉树结点结构;右子树为指针类型,指向路径二叉树结点结构.
3.5.2 条件表达式表结点结构
条件表达式表结点结构:
其中状态位为整型,其作用有二、一个是标识一个变量是否展开为全部为输入变量表示的状态、另一个作用是标识一个条件表达式是否化简为最简状态、即对于大于关系,大于等于关系,小于关系,小于等于关系的条件表达式要化简成规范条件表达式,对于等于关系及不等于关系的条件表达式要化简成等号或不等号一边为乘积项代数和的形式,另一边为0;变量指针,运算及关系操作符和指数为一个联合体,变量指针为指针类型,指向变量信息表或输入变量表;运算及关系操作符为字符类型,用来存算术运算符,关系运算符和等号;指数为整型,用来在表达式化简以后存变量的幂次;下一结点为一个指针,指向下一个条件表达式表结点结构.
3.5.3 偏微分向量(即梯度)的存储结构偏微分向量的存储结构即梯度表达式表的结点结构如下:
其中操作符,系数或常数及输入变量表和系数为一个联合体,操作符为字符类型,用来存算术运算符和关系运算符;系数或常数为整型,用来存梯度表达式中变量的系数或梯度表达式中的常量表达式;输入变量表及系数为联合体中的一个结构体,输入变量表为指针,指向输入变量表结点结构;指数为整型,用来存输入变量的幂次;下一结点为一个指针,指向下一个梯度表达式有结点结构.
第四章条件组合覆盖及类覆盖的路径查找
4.1 条件组合覆盖,类覆盖及路径覆盖策略表面看来,软件测试的目的与软件工程所有其它阶段的目的都相反.软件工程的其他阶段都是建设性的:软件工程师力图从抽象的概念出发,逐步设计出具体的软件系统,直到用一种适当的程序设计语言写出可以执行的程序代码.但是,在测试阶段测试人员努力设计出一系列测试方案,目的却是为了破坏已经建好的软件系统,竭力证明程序中有错误不能按照预定要求正确工作.当然,这种现象仅仅是表面的.暴露问题并不是软件测试的最终目的,发现问题是为了解决问题,测试阶段的根本目标是尽可能多地发现并排除软件中潜藏的错误,最终把一个高质量的软件系统交给用户使用.测试是为了发现程序中的错误而执行程序的过程.
测试任何产品都有两种方法:如果已经知道了产品应该具有的功能,可以通过测试来检验是否每个功能都能正常使用;如果知道产品内部工作过程,可以通过测试来检验产品内部动作是否按照说明书的规定正常进行.前一个方法称为黑盒测试,后一个方法称为白盒测试.对于软件测试而言、黑盒测试把程序看成一个黑盒子,完全不考虑程序的内部结构和处理过程.也就是说,黑盒测试是在程序接口进行的测试,它只是检查程序功能是否是能按照规格说明书的规定正常使用,程序是否是能适当地接入输入数据产生正确的输出信息,并且保持外部信息(如,数据库或文件)的完整性.黑盒测试又称为功能测试.与黑盒测试法相反、白盒测试法的前提是可以把程序看成装在一个透明的白盒子里、也就是完全了解程序的结构和处理过程.这种方法按照程序内部的逻辑测试程序,检验程序中的每条通路是否都能按预定要求正确工作.白盒测试又称为结构测试.
使用白盒测试法,为了做到穷尽测试,程序中每条可能的通路至少都应该执行一次,或者严格地说每条通路都应该在每种可能的输入数据下执行一次,即使测试很小的程序,通常也是不可能的.因此,软件测试不可能进行穷尽测试,也就不可能发现程序中的所有错误,也就是说通过测试并不能证明程序是正确的.我们测试的目的是要通过测试保证软件达到一定的可靠性.
设计测试方案是测试阶段的关键技术问题.所谓测试方案包括预定要测试的功能,应该输入的测试数据和预期的结果.其中最困难的问题是设计测试用的输入数据(即测试用例).不同的测试数据发现程序错误的能力差别很大,为了提高测试效率降低测试成本,应该选用高效的测试数据,选用少量最有效的测试数据,做到尽可能完备的测试.设计测试方案的基本目标是,确定一组最可能发现某个错误的测试数据.已经研究出许多设计测试数据的技术,这些技术各有优缺点、没有哪一种是最好的,更没有哪一种可以代替其余所有技术;同一种技术在不同的应用场合可能相差很大,因些、通常需要联合使用多种设计测试数据的技术.通常的做法是用黑盒设计基本的测试方案,再用白盒补充一些方案.
有选择地执行某些最有代表性的通路是对穷尽测试的唯一可行的替代办法.所谓逻辑覆盖的对一系列测试过程的总称,这组测试过程逐渐进行起来越完整的通路测试.测试数据执行(或叫覆盖)程序逻辑的程序可以化分成不同的等级.从覆盖源程序的详尽程序分析角度,大致有以下一些不同的覆盖标准:1. 语句覆盖:为了暴露程序中的错误,至少每个语句应该执行一次.语句覆盖对程序的逻辑覆盖很少,语句覆盖只关心判定表达式的值,而没有分别测试判定表达式中每个条件取不同的值的情况.语句覆盖是很弱的覆盖标准;2. 判定覆盖:判定覆盖又叫分支覆盖,它的含义是不仅每个语句必须至少执行一次,而且每个判定的每种可能结果都应该至少执行一次,也就是每个判定的每个分支都至少执行一次.判定覆盖比语句覆盖强、但是对程序逻辑的覆盖程度仍然不高;3. 条件覆盖:其含义是不仅每个语句至少执行一次,而且使判定表达式中的每个条件都取到各种可能的结果.条件覆盖通常比判定覆盖强、因为它使判定表达式中每个条件都取到了两个不同的结果,判定覆盖却只关心表达式的值;4. 判定条件覆盖:既然判定覆盖不一定包含条件覆盖,条件覆盖也不一定包含判定覆盖,自然会提出一种同时满足这两种覆盖标准的逻辑覆盖,这就是判定条件覆盖.它的含义是,选取足够多的测试数据,使得判定表达式中的每个条件都取到可能的值,而且每个判定表达式也都取到各种可能的结果.有时判定,条件覆盖也并不比条件覆盖更强;5. 条件组合覆盖:条件组合覆盖是更强的逻辑覆盖标准,它要求选取足够多的测试数据,使得每个判定表达式中条件的各种组合都至少出现一次.显然,满足条件组合标准的测试数据,也一定满足语句覆盖,判定覆盖,条件覆盖和判定条件覆盖标准.因此,条件组合覆盖是前述几种覆盖标准最强的.但是,满足条件组合覆盖标准的测试数据并不一定使程序中的每个路径都执行到.
以上根据测试数据对源程序语句检测的详尽程序,简单讨论了几种逻辑覆盖标准,测试数据可以检测的程序路径的多少,也反映了对程序测试的详尽程序.从对路径的覆盖程度分析,能够提出下述一些主要的逻辑覆盖策略:1. 点覆盖:如果连通图G的子图G是连通的,而且包含G的所有节点、则称G是G的点覆盖.在正常情况下程序图是连通的有向图,图中每个节点相当于程序流程图的一个框(一个或多个语句).满足点覆盖策略要求选取足够多的测试数据,使得程序执行路径至少经过程序图中每个节点一次.显然,点覆盖策略和语句覆盖标准是相同的.2. 边覆盖:如果连通图G的子图G连通的,而且包含G的所有边、则称G是G的边覆盖.为了满足边覆盖的测试策略,要求选取足够多的测试数据,使得程序执行至少经过程序图中每条边一次.通常边覆盖和判定覆盖是一致的.3. 路径覆盖:路径覆盖的含义是,选取足够多的测试数据,使程序的每条可能路径都至少执行一次(如果程序中有环,则要求每个环至少经过一次).路径覆盖是相当强的逻辑覆盖标准,它保证程序中每条可能的路径都至少执行一次,因此这样的测试数据更具有代表性,暴露错误的能力也比较强.但是,为了做到路径覆盖中需考虑每个判定表达式的取值,并没有检验表达式中条件的各种组合情况.如果把路径覆盖和条件组合覆盖结合起来,可以设计出检错能力更强的测试用例.
类覆盖指的是覆盖类中的成员变量和成员函数,是一种面向对象语言的点覆盖策略.本文测试用例生成策略是把路径覆盖,条件组合覆盖策略结合起来,兼顾点覆盖策略.
4.2 信息流分析技术及部分求值技术介绍信息流分析技术在程序优化,程序静态分析,程序测试等许多方面都有重要的应用.应用领域的不同、分析数据的属性也不同.我们的方法是通过对程序中变量值的获取与传播的分析,着重描述变量与表达式,表达式与变量,变量与变量之间的关系.
我们所研究的语言SOOL基本是从C化简而来,这种面向对象式语言与函数式语言和逻辑式语言有很大的区别.其中、重要区别之一是:SOOL程序中变量的值是随着程序的执行而动态变化的.这使我们不能采用其它类语言的部分求值技术.
基于面向对象语言自身的特点、我们对面向对象语言求值,我们必须知道一个语句是否应被执行和一个表达式是否可计算.下面,我们给出部分求值技术的描述:
首先,我们引入状态STA和环境ENV: STA:V→{k,u} ENV:V→VALSTA是变量到状态的映射,k表示变量已知,u表示变量值未知(初始状态所有变量为u);ENV是变量到其值的映射.
我们引入一个表达式求值函数:
具体定义如下:
若E=n,且n为常数或E=V,且s(v)=k, env(v)=n ;
(v,u) 若E=V,且s(v)=u; 若E=E1 op E2,且 i=1,2.
(n,k) 若w1=w2=k, 且x1 op x2=n;
(x1 op x2,u) 若w1=u或w2=u.
语句求值函数定义如下:
TRANS: StmSTAENV→StmSTAENV在下面的语句求值函数中、(xy)表示用x代替y 的值.语句求值函数具体定义如下:其中xi为部分输入,val(xi)为xi的输入值.i=n;= (v=E,s[uv,env) 若 (skip,s[kv,env[nv]) 若其中若若若若vi∈Ds1∧env(vi)=ni∧((s(vi)=k∧s(vi)=u)∨若vi∈Ds2∧env(vi)=ni∧((s(vi)=k∧s(vi)=u)∨其中Ds表示S定义的所有变量之集.s(v)=k若s(v)=s(v)=ku若s(v)=u 或s(v)=uenv(v)=n若s(v)=k∧n=env(v)若s(v)=u;
(6)循环语句的求值函数定义如下:
我们把循环语句视为:(WHILEEDO A,N)其中、N=max(as(v)|v∈DA)1,as(v)是变量v的稳定长度.
(a)若则
(b)若且n≥0,则 A,s,env)
(c)若则 (A;WHILEEDO A)ELSE SKIP; ,s,env)
其中、函数TRANS为一个新函数,它的定义与函数TRANS基本相同、其不同之处在于赋值语句与循环语句的处理.
其中 A,s,env)其中
信息流分析技术通过对变量值的获取与传播的分析,分析输入变量和输出变量之间的关系,变量值的获取及变量值的传播.本文使用信息流分析技术和部分求值技术主要是用于寻找输入变量与判定表达式变量之间的关系以及程序中常量赋值的影响.
4.3 创建及使用存储信息的基本数据结构
4.3.1 创建及使用类信息表在SOOL程序中规定只能在类中声明和实现函数,给函数发消息的时候一定标明给哪一个类的哪一个对象中的函数发消息,若该类的父类中有同名函数,以该类中的函数为准;若该类中无这一函数,而某个父类中有这一函数,向上查找,以最近的父类为准,由于SOOL语言中规定只能单继承,所以这里不存在歧义的问题.由此可知,类与函数关系密切,类变化会影响类中的函数,进而影响函数中的变量,影响程序执行路径上的条件表达式的值,因此必须创建和使用类信息表.
在SOOL语言中规定声明和实现必须在同一位置,不允许声明与实现分离即先声明后实现的情况.在语法树中类声明和实现处创建类信息表,填写类信息表结点结构中各项值:填写类名;把其指向父类的指针指向其父类,若其没有父类,则为NULL;把类中成员变量表的指针指向该类的成员变量表,同时填写类中成员变量表,成员变量表结点结构见前文,其中的变量信息表指针指向一个为该成员变量新建的变量信息表;把类中成员函数表的指针指向该类的成员函数表,同时填写类中成员函数表,成员函数表结点结构见前文,其中的函数信息表指针指向一个为该成员函数新建的函数信息表;把下一结点指针暂时置为NULL,当有下一个类出现时,指向下一个类结点、同时把上一个类信息表中的下一结点指针指向该类信息表.
在用类声明对象时,把类中所有成员变量,成员函数以及该类所有继承的父类中成员变量,成员函数拷贝一份给这个对象,这时就需查类信息表,查找所需信息用来填写该对象的对象生存期表.
4.3.2 创建及使用对象生存期表一个类可以声明不同的对象,同一个类中的不同对象可以有不同的成员变量和成员函数,类发生变化时,类的对象一定发生变化;反之,对象发生变化时类不一定发生变化.在使用类中成员变量和成员函数时实际上是使用类的对象的成员变量和成员函数.对象与变量,函数发生直接联系,对象中的变量和函数发生变化,最终会影响程序执行路径上的条件表达式的取值,因此必须创建和使用对象生存期表.
在SOOL语法树中变量声明处,若声明的变量类型为类类型,也就是某一个类名时,被声明变量为一个对象,此时创建对象生存期表,填写对象生存期表结点结构中各项值:填写对象名;把类信息表指针指向拷贝给该对象的类信息表;把对象中的成员变量表指针指向该对象的成员变量表,同时填写对象中成员变量表;把对象中成员函数表的指针指向该对象的成员函数表,同时填写对象中成员函数表;把下一结点指针暂时置为NULL,当有下一个对象出现时,指向下一个对象结点、同时把上一个对象生存期表中的下一结点指针指向该对象生存期表.
在给对象中的成员函数发消息时,去查该对象的对象生存期表,对该函数影响到的成员函数和成员变量查对象生存期表中的成员函数表和成员变量表进行修改、同时对该对象的类信息表中的受到影响的部分进行修改;在使用对象中的成员变量时,若改变其值,去查该对象的对象生存期表,修改对象生存期表中的成员变量表中对应的项.
4.3.3 创建及使用变量信息表在SOOL语法树中变量声明处创建变量信息表,填写变量信息表结点结构各项值:填写变量名;填写变量状态、变量状态共有四种它们表示变量为未知变量(U),已知变量(K),输入变量(I)和与循环有关的变量(L).这里的未知变量(U)的与前文中介绍的部分求值技术中未知变量的意义相同、所有变量的变量状态初始值为U;这里的已知变量(K)与前文中介绍的部分求值技术中的已知变量的意义相近,若一个变量被赋值或由于给类中成员函数发消息引起的隐式变量赋值,则该变量状态为K;这里的输入变量(I)表示一个变量是输入变量,这是我们生成测试用例所最需要的部分,在程序输入语句中的变量为输入变量,把变量状态位填写为I,同时填写输入变量表并把指针指向输入变量表;与循环有关的变量(L)是指对变量赋值的过程中、或者赋值过程出现在循环体中、或者赋值表达式有与循环有关的成分,此时令变量状态为L;填写变量信息表中的变量联合体(其结点结构见前文介绍):对于,及括号填写在操作符结构中;填写系数项、默认值为1,若多元函数乘积项有系数,那么填写系数,若为常数项在其上填写常数;填写表中的联合体内容、这一部分是变量信息表的主要内容、它包含的信息是组成该中间变量值的输入变量信息,某个对象的成员变量信息,成员函数信息,中间变量信息,填写不同的指针值,分别指向输入变量表,函数信息表和其它的变量信息表,这里需说明的是对于多个为同一变量名的变量信息表,指向哪一个变量信息表由该变量所在的类或属于哪一个对象确定:若同类中有为这一名称的成员变量,那么就指向这一成员变量的变量信息表;若同类中没有这一名称的成员变量,那么就沿着继承关系向上去找,以找到的第一个同名成员函数为准;若在主函数中使用了中间变量,这时分两种情况,一种情况是变量直接使用的情况,这时要使用主函数中定义的变量或全局变量,指向这些变量的变量信息表或输入变量表即可,另一种情况是在给类中函数发消息时引起的间接变量使用,这时也是要使用主函数中定义的变量或全局变量,指向这些变量的变量信息表或输入变量表即可;同一变量名的输入变量只能有一个输入变量表,当还没确定是输入变量时可当作中间变量处理,可能会出现多个中间变量的变量信息表都指向同一个输入变量的输入变量表的情况,但是只要程序是正确的,就不会产生冲突错误;由于在SOOL程序中规定所有函数声明和实现都只能在类中进行、在给类中函数发消息的时候必有标明是给哪一个对象中的成员函数发消息,而在不同对象中同一名称的成员函数只的一个,因此不会出现歧义;把下一结点指针暂时置为NULL,当有下一个中间变量出现时,指向下一个中间变量的变量信息表结点、同时把上一个变量信息表中的下一结点指针指向该变量信息表.
4.3.4 创建及使用函数信息表函数信息表不仅影响中间变量和其它函数的值,而且是函数嵌套展开的依据,而函数嵌套展开是本文中的难点、函数信息表建造的好坏与否对函数嵌套能否正确展开影响很大,因此建造函数信息表时应尽量全地记录函数相关信息.
在SOOL语法树中函数声明和实现处创建函数信息表,填写函数信息表结点结构各项值:填写成员函数名;填写函数状态值,函数状态共有四种它们表示函数为未知函数值函数(U),已知函数值函数(K),函数值组成全部为输入变量(及函数)或已知变量(及函数)(I)和与循环有关的函数(L).这里的处理与前文中变量的处理相类似,值得一提的是与循环有关的函数是指函数实现的时候函数中有循环体或函数的实现在某一个循环体中或函数中包含L型的变量或函数;填写参数表指针,它指向变量信息表,若函数没有参数指针指向空NULL,若函数有多个参数,指针指向的是变量信息表链;填写函数值表指针,初值置为NULL,在有函数嵌套的时候它指向函数展开栈,也可能指向变量信息表;填写类信息表指针,指向函数所属对象的对象生存期表,这主要是用来在需要的时候进行父类查找;把下一结点指针暂时置为NULL,当有下一个成员函数出现时,指向下一个成员函数的函数信息表结点、同时把上一个函数信息表中的下一结点指针指向该函数信息表.
4.3.5 创建及使用输入变量表在SOOL语法树上输入函数处创建输入变量表,输入函数的参数表中的参数即是输入变量表中的输入变量,输入变量表相对简单但是最后的生成测试用例的进候都是围绕输入变量表进行的.由于在变量声明的时候已经建立了变量信息表,所以在填写输入变量表时可以从变量信息表中拷贝两表中相同的顶,填写输入变量名;填写引用状态位、初值为0,表示在生成测试用例的时候路径上前面的条件表达式没有出现这一输入变量,因而没有给这一输入变量生成一个值,若条件表达式出现这一输入变量,而给这一输入变量赋一个值,那么要把引用状态位改为1;填写变量类型;填写输入变量初值,置为0;把下一结点指针暂时置为NULL,当有下一个输入变量出现时,指向下一个输入变量的输入变量表结点、同时把上一个输入变量表中的下一结点指针指向该输入变量表.
4.4 运行过程中程序中各种信息的存储,查找与处理SOOL程序测试用例生成器在运行过程中要对SOOL语法树进行遍历操作,查找所有的条件判断表达式存储在路径二叉树上,由于利用ACCENT工具已经在语法树上建立了类信息表,对象生存期表,变量信息表,函数信息表和输入变量表等基本数据结构,这时要利用这些基本的数据结构对路径二叉树上的条件判断表达式进行计算,化简、削去那些不会产生分支的条件表达式,形成新的路径二叉树,然后根据化简后的路径二叉树生成测试用例.
4.4.1 常量的存储,查找与处理对路径上条件表达式影响最大的是常量,它对表达式的影响主要体现在四个方面,一是某些表达式中的变量的值全部由常量组成,这样经过计算后得到表达式的值,这个条件表达式不会产生分支;二是某些变量的值的一部分为常数项、只需化简常数项;三是某些变量带有系数,这时要化简需判断同类项、而且这些系数影响条件表达式梯度;四是某些变量为高次幂,在求取条件表达式梯度及等式生成测试用例的时候都会对结果产生影响.
对于前三种情况,常量存储在变量信息表中、对于第四种情况,变量的指数存储在路径二叉树中的条件表达式结构中、在生成梯度表达式的时候利用前面这些值得到结果,把前三种情况存在系数或常量位中、把梯度中变量的指数存储在指数位中.
4.4.2 变量的存储,查找与处理变量要区分中间变量与输入变量,每当程序中有变量声明的时候,就产生中间变量,中间变量填在变量信息表中、每当新产生一个中间变量,就在变量信息表中填加一项;输入变量开始时也作为中间变量填在变量信息表中、当在输入函数中确定输入变量时,把变量信息表中的相应指针指向输入变量表,同时填写输入变量表,在输入变量表中增加一项.
在对程序进行信息流分析的时候,中间变量的值发生改变,修改变量信息表的内容记录这些改变,中间变量值表示成一个链表的形式,这一链表由算术运算符,括号以及指向变量信息表的指针,指向函数信息表的指针和指向输入变量表的指针组成.显然,在进行化简之前、随着对程序信息流分析的深入,这一链表会越来越长.
在路径二叉树中进行条件表达式计算和化简的时候,由前文介绍的条件表达式结点结构可知,条件表达式是一条由算术运算符,括号,关系运算符以及指向变量信息表的指针,指向函数信息表的指针,指向输入变量表的指针和变量的指数组成的符号链.
路径二叉树上的条件表达式经过计算,化简和削减后,所有的条件表达式中都不再含有括号,指向函数信息表的指针,而只包含算术运算符,关系运算符及指向变量信息表的指针,指向输入变量表的指针和输入变量指数.
4.4.3 函数的存储,查找与处理函数信息存储在函数信息表中、函数若有嵌套需得使用函数展开栈.在对程序进行信息流分析的时候,函数的值发生改变,修改函数信息表的内容记录这些改变,函数值表示成一个链表的形式,这一链表由算术运算符,括号以及指向变量信息表的指针,指向函数信息表的指针和指向输入变量表的指针组成.显然,同中间变量的变量信息表一样,在进行化简之前、随着对程序信息流分析的深入,这一链表会越来越长.
对嵌套函数的展开本文后面有详细介绍.路径二叉树上条件表达式经过计算,化简后,所有指向函数信息表的指针均被消掉、函数不会对化简后的条件表达式产生影响.
4.5 赋值语句及发消息语句的处理为了生成测试用例,我们考虑的主要方面是赋值语句和发消息语句对条件表达式的影响、因此在这里发消息语句可以看作是多个赋值语句,类似地,函数返回值也可以看作是对函数的赋值语句.
赋值语句的一般形式把一个表达式赋给一个中间变量,该表达式为一个链表,这一链表由算术运算符,括号以及指向变量信息表的指针,指向函数信息表的指针和指向输入变量表的指针组成,赋值的时候把这一个链表赋给这个变量,实现的时候只需修改该中间变量的变量信息表中的指针即可;同时要修改变量信息表的状态位、若表达式中所有变量信息表和函数信息表的状态位均为K,则把该中间变量的状态位置为K;若表达式中有一个变量信息表或函数信息表的状态位为L,则把该中间变量的状态位置为L;若表达式中所有变量信息表和函数信息表的状态位或者为K或者为I(可以没有K,但不能没有I),则把该中间变量的变量信息表的状态位置为I.
4.6 分支语句的处理及路径二叉树的建立
4.6.1 程序块中出现的IF语句的处理这里所说的程序块中出现的IF语句,是指区别后面的非函数体中的程序块.IF语句是产生程序执行路径分支的原因,由前文的叙述可知并不是每一个IF都会产生分支,并且由于IF语句相互影响、我们在开始建立路径二叉树的时候并不确定哪些IF语句产生分支,我们的做法是对在程序块中出现的IF语句均先假定其产生分支,把IF语句中BOOL表达式作为路径二叉树上的条件表达式,假定表达式成立和表达式不成立产生两条分支,分别沿两条分支填写分支路径上的条件表达式.
由于这样形成的条件表达式不一定产生分支,所以在对表达式计算和化

doc文档的标签：论文分类

更多推荐标签：金融函电写作食品设备日语教案直效营销测比热实验富士通电脑贸易政策招贴广告質性研究潮流计算程序安全生产标志导游年审时间入股说明书固井工程论文图片欣赏产品设计需求产品评估合资证明私人合作合同警察伦理学考研组成原理黄色小书网摘宪法学张千帆客户表格现代科技概要聊天程序开发自信的作用仪器清洁程序自存书现代