基于抽象内存模型的非数值型数据的计算方法

摘要

本发明提供了一种基于抽象内存模型的非数值型数据的计算方法，包括：A、设计抽象内存模型用于模拟数值型变量和非数值型变量的内存结构，以及存储变量操作中包含的语义信息和约束关系；B、提取数值型变量和非数值类型变量的类型操作中包含的语义信息，并将语义信息映射到抽象内存模型中；C、提取数值型变量和非数值类型变量的类型操作中包含的变量间约束和变量内约束，并将约束关系映射到抽象内存模型；D、从抽象内存模型中提取变量的语义信息和约束关系，使用测试用例构建算法和第三方的约束求解器构建测试用例。采用本发明，可以克服现有技术无法精确支持非数值型变量程序语义的不足，实现包含非数值型的程序自动生成测试用例的目的。

说明书

技术领域

本发明涉及软件测试技术，尤其涉及基于抽象内存模型的非数值型数据的 计算方法，属于单元测试中对含非数值型数据程序的语义模拟和约束提取技术 领域。

背景技术

软件测试分为动态测试和静态测试两种。动态测试是通过运行软件来检测 软件的动态行为和运行结果的正确性；静态测试是收集、查找程序的信息，对 被测程序进行特征分析，其主要优点是在程序运行之前就可以收集程序的语义 信息。在实际的软件测试中，实际的程序逻辑可以非常复杂的。基于静态分析 的测试用例生成方案可以很好的支持数值型的程序，对非数值类型的程序，该 方案不能很好的记录程序的语义信息，导致自动生成非数值类型的测试用例困 难。尤其是指针的别名问题和数组的变下标引用，是符号执行的难点问题。

发明内容

有鉴于此，本发明的主要目的在于提供一种基于抽象内存模型的非数值型 数据的计算方法，其采用抽象内存建模技术存储路径分析过程中变量相关语义 信息，在抽象内存中为每个变量分配一个抽象内存单元，并将与该变量相关的 指令操作映射为对抽象内存的操作，精确记录变量的结构语义和操作语义。

为达到上述目的，本发明的技术方案是这样实现的：

本发明所提供的基于抽象内存模型的非数值型数据的计算方法，具有以下 优点：

静态分析和符号执行相结合的测试用例自动生成技术，是自动化单元测试 常用的测试用例自动生成技术，但该技术的缺点是对非数值型的程序支持不完 善，生成测试用例困难。而本发明则属于基于路径的单元测试中为非数值类型 （含非数值型数据程序的语义模拟和约束提取）自动生成测试用例的方法，其 使用抽象内存建模的技术存储路径分析过程中变量相关语义信息，在抽象内存 中为每个变量分配一个抽象内存单元，并将与该变量相关的指令操作映射为对 抽象内存的操作，精确记录变量的结构语义和操作语义。采用该方法能够弥补 传统的基于静态分析的测试用例生成方法无法精确支持非数值型变量（结构体、 指针和数组等）程序语义的缺憾，以及能够克服传统的符号执行和静态分析相 结合测试用例生成方法无法精确支持非数值型变量（结构体、指针和数组等） 程序语义的不足，实现为包含非数值型的程序自动生成测试用例的目的。

附图说明

图1为本发明基于抽象内存模型的非数值型数据的计算方法的流程图；

图2本发明中抽象内存的结构示意图。

具体实施方式

下面结合附图及本发明的实施例对本发明的方法作进一步详细的说明。

本发明的基本思想为：首先从被测函数的控制流图上得到一条路径作为被 测路径，然后为被测函数的输入域参数分配抽象内存单元；之后逐个对路径上 的节点进行语义模拟，将每条指令映射为对应的抽象内存操作，提取语义信息 存入抽象内存中，将符号间的数值型约束关系存入约束集中；在路径分析结束 后，从抽象内存中提取各个输入域参数的结构信息，从约束集中提取和该参数 相关的数值型约束，按测试用例生成算法为该参数构建测试用例。

图1为本发明基于抽象内存模型的非数值型数据的计算方法的流程图，如 图1所示，其方法主要包括：

步骤1：设计抽象内存模型用于模拟数值型变量和非数值型变量的内存结 构，以及存储变量操作中包含的语义信息和约束关系。其具体包括：

使抽象内存主要用于存储变量的语义信息，按C数据类型将抽象内存模型 分为四个区：数值区、数组区、结构体区和指针区。

这里，由于数据类型的特征不同，每个区都设有特有的数据结构，以便能 够记录相关变量足够的语义信息。抽象内存中的每一条数据称之为一条记录， 每条记录有唯一的地址标示，通过地址标示，访问对应的抽象内存单元，该设 计类似于数据库的层次化存储。以指针变量int*p为例，在抽象内存的指针区 和数值区将会分别生成一条记录。

表1抽象内存模型核心属性

addr aliases source varName type dm0        

其属性及其含义如下：

表2数值型抽象内存表

addr aliases source varName type expr constraint Mn_i           

其属性及其含义如下：

表3结构体抽象内存表

addr aliases source varName type mem1 …… mem_nMs_i             

其属性及其含义如下：

表4指针的抽象内存表

addr aliases source varName type initPT initState pt state Mp_i               

其属性及其含义如下：

表5数组的抽象内存表

其属性及其含义如下：

步骤2：提取数值型变量和非数值类型变量的类型操作中包含的语义信 息，并将语义信息映射到抽象内存模型中；其具体包括：

步骤21、结构体的操作包括取成员操作(.)和赋值操作(=)等。进一步的，包 括：

步骤211、结构体的取成员操作(.)，包含的语义信息为取结构体的成员。 获取结构体变量的抽象内存单元，按成员变量名获取成员变量的抽象内存地址， 返回抽象内存地址对应的抽象内存单元。

步骤212、结构体的赋值操作=，分别获取操作符左右变量的抽象内存单 元，遍历右变量的各个成员的抽象内存单元，将其语义信息赋值给左变量的对 应单元。

步骤22、指针的取值操作（*）、指针的赋值操作(=)、指针的条件判断操作 (==,!=)、指针的算术运算操作(++、--、+、-)、指针的比较操作(>、>=、<、<=) 等。具体包括：

步骤221、指针的取值*操作,指针p的取值操作符*是一元操作符，包含的 程序语义信息为：a)指针p不为NULL；b)读取*p的内容,即p的指向域有取 值域。

将该操作的语义信息映射到抽象内存中的步骤为：读取p的抽象内存地址 Pm_p，然后在结构体内存区新建内存单元Sm_p，建立Pm_p到Sm_p的指向Mp_ppt= Ms_p,设定指针状态Pm_pstate=NOTNULL；

步骤222、结构体指针p的取值->操作是一元操作符，与操作符*相同，它 含的程序语义信息为：a)指针p不为NULL；b)读取(*p)的内容,即p的指向域 有取值域。

将该操作的语义信息映射到抽象内存中的步骤为：读取p的抽象内存地址 Pm_p，然后在结构体内存区新建内存单元Sm_p，建立Pm_p到Sm_p的指向Mp_ppt= Ms_p,设定指针状态Pm_pstate＝NOTNULL；

步骤223、指针的赋值操作符p=q，包含的程序语义信息为：

a)p和q不为NUILL，b)如果p指向某抽象内存空间，解除和该抽象内存 空间的指向关系。c)p指向q指向的抽象内存空间。

将该操作的语义信息映射到抽象内存中的步骤为：首先清除p的非数值型 约束Clear(Mp_p,Mp_ppt)，然后针对指针q的三种不同状态做不同处理：a)q的状 态为空：设定p的状态为NULL。b)q的状态不确定：设定p的状态为UNSURE， 为*q新建一块抽象内存单元mi，p和q均指向mi。c)q的状态为非空：设定p 的状态为NOTNULL，p指向q指向的抽象内存单元。

步骤224、指针条件判断操作(==,!=),判定条件取真时，例如p==q，包含 的程序语义信息为合并p和q的指向的抽象内存x和y。具体的合并原则为a)

将p和q的别名集合并，并将所有别名的指向抽象内存x。b)按符号运算 的规则合并数值型抽象内存中的符号表达式。c)删除抽象内存y。判定条件取假 时p!=q,获取p和q的抽象内存单元，添加这两个抽象内存单元不能合并的约束。

将该操作的语义信息映射到抽象内存中的步骤为：根据p和q状态的不同， 分别进行处理（p和q的抽象内存地址分别为Mp_p,Mp_q）：a)p和q的状态均为 不确定：新建抽象内存单元Ms₀，设置Mp_ppt,Mp_qpt为Ms₀。b)p和q的状态一 个为非空，一个为不确定：假设p的状态为NOTNULL，读取Mp_ppt的抽象内 存单元Ms₀，设置Mp_qpt为Ms₀,Mp_qstate=NOTNULL。c)p和q均为非空：读 取Mp_ppt和Mp_qpt的指向Ms_p和Ms_q，合并Sm_p和Sm_q，然后释放无用的抽象 内存单元Ms_p，将Mp_ppt和Mp_qpt的指向域pt均设置为Sm_q。d)p和q均为空： 约束已经满足。e)p和q一个为非空，一个为空：矛盾，此次测试用例生成失 败。

步骤225、指针的条件判断p>q操作，包含的语义信息为：p和q均为非 空，p和q的地址存在前后或者间距约束。

将该操作的语义信息映射到抽象内存中的步骤为：设定p和q的状态为非 空：Mp_pstate＝NOTNULL；Mp_qstate＝NOTNULL；新建抽象内存单元分别作为p 和q的指向域：Mp_ppt=Create(*p);Mp_qpt=Create(*q);然后使用虚拟数组处理指 针地址间约束：创建虚拟数组vam;p和q分别对用虚拟数组的地址VAddrp和 VAddrq，虚拟数组的长度VLen=max{0，VAddrp，VAddrq}+1，Mpppt和Mp_qpt 分别是地址VAddr_p和VAddr_q处的虚拟数组单元。因此，可以用VAddr_p-VAddr_q<5 表示指针纸箱内存地址的间距。

步骤226、指针的条件判断p<q操作，包含的程序语义信息与p>q类似。

步骤227、指针的条件判断p>=q操作，包含的程序语义信息与p>q类似。

步骤228、指针的条件判断p<=q操作，包含的程序语义信息与p>q类似。

步骤229、指针的地址位移运算p+offset,包含的程序语义信息为它指向一块 连续的内存，即它是数组中第offset个元素的别名。

将该操作的语义信息映射到抽象内存中的步骤为：如果数组已经定义，分 配一块抽象内存单元表示*(p+offset)，对应的数组下标为p的下标加offset；如 果数组不存在，首先新建一块数组抽象内存am₀，分配p（对应的下标为s₀，s₀为新生成的符号）和p+offset(对应的下标为s₀+offset)的两块内存空间pm₀和 pim₀。在am₀中记录<s₀,pm₀>和<s₀+i,pim₀>的索引信息。

步骤2210、指针的地址位移运算-,包含的程序语义信息与指针的地址位移 运算+类似。

步骤2211、指针的地址位移运算++,包含的程序语义信息与指针的地址位移 运算+类似。

步骤2212、指针的地址位移运算--,包含的程序语义信息与指针的地址位移 运算+类似。

下面以具体的程序insertnodec说明抽象内存模型是如何在路径分析中记录 程序执行的语义的。

如，选择路径7-8-12-13-14-15，根据输入域参数初始化抽象内存。 指针抽象内存表为：

addr aliases source name type initPT initState pt state pm₀{} INPUT head struct Node* sm₀UNSURE    

结构体抽象内存表：

addr aliases source name type <mem,memory> sm₀{pm0} INPUT_ANNOMY var0 struct Node*  

数值型抽象内存表：

addr aliases source name type Expression dm₀{} INPUT e int factor0

符号因子：

symbol domain constraints factor0 (-inf，+inf)  

执行语句7-8后的抽象内存：

指针抽象内存表：

addr aliases source name type initPT initState pt state pm0 {} INPUT head struct Node* sm0 UNSURE     pm1 {} LOCAL eNode struct Node* sm1 NOT_NULL    

结构体抽象内存表：

addr aliases source name type <mem,memory> sm0 {pm0} INPUT_ANNOMY var0 struct Node   sm1 {pm1} LOCAL_ANNOMY var1 struct Node <”data”,dm0>

数值型抽象内存表：

addr aliases source name type Expression dm0 {} INPUT e int factor0 dm1 {} LOCAL_ANNOMY var2 int factor1

符号因子：

执行语句13-15后的抽象内存表：

指针抽象内存表：

addr aliases source name type initPT initState pt state pm₀{} INPUT head struct Node* sm₀NOT_NULL     pm₁{} LOCAL eNode struct Node* sm₁NOT_NULL     pm₂{} LOCAL var4 struct Node* sm₂UNSURE     pm₃{} LOCAL var4 struct Node* sm₁UNSURE    

结构体抽象内存表：

数值型抽象内存表：

addr aliases source name type Expression dm₀{} INPUT e int factor₀dm₁{} LOCAL_ANNOMY var₂int factor₁dm₂{} INPUT_ANNOMY var₃int facotr₂

符号因子：

执行条件判断if(head->data>eNode->data)，选择真分支后，则：

指针抽象内存表：

结构体抽象内存表：

数值型抽象内存表：

addr aliases source name type Expression dm₀{} INPUT e int factor0 dm₁{} LOCAL_ANNOMY var₂int factor1 dm₂{} INPUT_ANNOMY var₃int facotr2

符号因子：

如下为测试用例生成过程：

第一步：计算与input(source值)相关的符号表达式；

factor2>factor0;=>factor2=5,factor0=3;

第二步：为输入域生成测试用例；

e=3;

步骤23、数组的运算操作主要是[]，数组是常量指针，它还包含一些指针 的操作如*、+等。

步骤231、数组的读取成员元素操作[],数组取成员操作[]建立两个维度上的 约束，a)下标和长度的约束0=<sub<len；b)建立数组元素和其它变量间的约 束，如a[i]<a[j];

将该操作的语义信息映射到抽象内存中的步骤为：获取数组变量的抽象内 存单元，通过下标获取对应成员元素的抽象内存地址。若下标在该数组元素中 还不存在，则为其对应的成员元素分配新的抽象内存单元，并将<下标,抽象内 存地址>添加到数组变量的抽象内存中。返回下标对应数组元素的抽象内存单 元。

步骤232、数组的读取成员元素操作符（*），包含的语义信息与指针的*操 作类似。

步骤233、数组的算术运算符（+），如a+i，表示首地址偏移i的元素，包 含的语义信息类似于指针的+操作。

下面以具体的程序arrc说明抽象内存模型是如何在路径分析中记录程序执 行的中数组语义的。

数组的抽象内存表：

addr aliases source name type len <sub,abs_mem> am0 {} INPUT a int[]    

数值型抽象内存表：

addr aliases source name type Expression dm0   INPUT i int factor0 dm1   INPUT j int factor1

符号因子：

执行i＜j和a[i]=a[j]后的抽象内存表：

数组的抽象内存表：

数值型抽象内存表：

addr aliases source name type Expression dm0 {} INPUT i int factor0 dm1 {} INPUT j int factor1 dm2 {} INPUT_ANONY am0[factor0] int factor2 dm3 {} INPUT_ANONY am0[factor1] int factor3

符号因子：

如下为测试用例生成：

第一步：计算与input(source值)相关的符号表达式

factor0=3;

factor1=10;

factor2=5;

factor3=8;

factor_am0_len=max{factor0，factorl}+1=11;

第二步：为输入域生成测试用例

i=3;j=10;

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]       5             8

步骤3：提取数值型变量和非数值类型变量的类型操作中包含的变量间约 束和变量内约束，并将约束关系映射到抽象内存模型中。具体包括：

步骤31、数值类型的操作包含算术运算+、-、*、/等，逻辑运算&&、||、! 等，条件判断>、>=、<、<=、==等，赋值语句=,+=,-＝,*＝,/=等。按步骤21描述 的方式获取表示数值类型取值的符号表表达式，将符号表达式代入到操作表达 式中，生成约束关系，存入数值抽象内存区的约束集中。

步骤32、数组类型的操作包含取值操作[]，下标可能是常量，可能是变量。 进一步的，包括如下步骤：

步骤321、按步骤231描述的方式获取数组变量的抽象内存单元，如果下 标是常量const，建立数组长度len>=const的约束关系，按步骤232描述的方式 为数组抽象内存单元添加下标为const的成员元素。

步骤322、下标是变量var,为下标分配一块数值型抽象内存，用var>=0初 始化，并和数组长度len建立约束len>=var，按步骤233描述的方式为数组抽 象内存单元添加下标为const的成员元素。

步骤33、指针的赋值操作(=)、指针的条件判断操作(==,!=)、指针的算术运 算操作(++、--、+、-)、指针的比较操作(>、>=、<、<=)等。

步骤331、对于指针的赋值操作(=)，如步骤243所述的语义操作，添加了 左右指针互为别名的约束。

步骤332、对于指针的条件判断操作(==,!=)，取真值时，添加左右指针互 为别名的约束，取假值时，添加左右指针不可以相同抽象内存单元的约束。

步骤333、指针的算术运算操作(++、--、+、-)，如步骤245所述的语义操 作，添加了指针变量与算术运算后的指针变量的地址偏移约束。

步骤334、指针的比较操作(>、>=、<、<=)，如步骤246所述的语义操作， 添加了左右指针的地址偏移约束。

步骤4：从抽象内存模型中提取变量的语义信息和约束关系，使用测试用 例构建算法和第三方的约束求解器构建测试用例。具体包括：

步骤41、路径分析结束后，变量的非数值型约束和数值型约束都保存在了 抽象内存模型中，测试用例生成算法就是从抽象内存中按一定规则分别提取变 量的数值型约束和非数值型约束，构建测试用例。进一步的，包括：

步骤411、如果变量var是数值型（数值型变量，费数值型变量的数值型成 员变量），获取变量var的抽象内存单元Mni，读取他的expr值，以及与expr 中符号相关的约束集，调用第三方约束求解器求解出满足所有约束的某个具体 的值。

步骤412、如果变量var为指针类型，获取对应的抽象内存Mpi，如果指针 变量的状态Mpistate为空或不确定，则var=null；指针变量的状态Mpistate为 非空，获取指向域Mpipt，如果Mpipt的inputFlag属性取值为F，表明其指向 的内存单元是在函数内存分配的，不属于测试用例的一部分，因此var=null； 如果取值为T，则var!=null；递归调用buildTestCase为指向域生成测试用例。

步骤413、如果变量var为结构体类型，逐个为结构体的成员域递归调用 buildTestCase生成测试用例。

步骤414、如果变量var为数组类型，首先调用约束求解器求解下标和数组 长度之间的约束，生成合适的长度和具体的下标，构建数组的形状，然后逐个 为下标对应的元素递归调用buildTestCase生成测试用例。

测试用例生成算法中各函数的作用如下：

buildTestCase：测试用例生成的顶层函数。

solveConstraint：调用第三方约束求解器求解约束。

build：构建测试用例的形状或者数值域的取值。

算法1：测试用例构建算法。

步骤333演示的程序arrc的测试用例生成过程为：

第一步：计算与input(source值)相关的约束关系。

a)访问数组变量的抽象内存单元，获取所有的下标相关约束，利用约束求 解器求解出一组满足所有约束的值如下：

factor0=3;

factor1=10;

factor2=5;

factor3=8;

b)访问数组的抽象内存单元，获取数组长度的相关约束，上一个步骤中将 数组的下标值求出，数组长度取下标最大值加1。

factor_am0_len=max{factor0，factor1}+1=11;

第二步：组建测试用例

i=3;j=10;

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]       5             8

以上所述，仅为本发明的较佳实施例而已，并非用于限定本发明的保护范 围。