方昭潭,苏 亭,李 博,经小川,张 伟
(1.华东师范大学 软件学院,上海200062;2.中国航天系统科学与工程研究院,北京100080)
在计算机语言发展过程中,类型系统用于定义如何将编程语言中的数值和表达式归类为许多不同的类型,如何操作这些类型,这些类型如何互相作用,类型系统的目的是防止在程序的执行过程中有运行时错误的发生。最初,高级语言并没有类型系统的概念,即语言中的变量x可以指向任何存储位置,而被引用的位置可以保存任意类型的信息[1]。Ocaml就是这样的高级语言,虽然它没有类型系统,但是运行时,变量的意义就会知道,这就造成编译器无法在编译时事先安排存储方案。所以,类型系统有助于提高编译效率。
对于软件开发过程,测试是一个非常重要的阶段,而测试用例是测试过程中重要的输出结果,在一定程度上检测软件程序的实现是否满足规范的要求。为了方便软件工程师的分析和调试,自动化测试已经是当前测试发展的前进趋势。工业 界工具,如 TESTBED和googletest[2-6],可将测试用例作为这些工具的输入,从而达到测试自动化。然而这些测试用例都需要测试人员的前期介入,并非真正的自动化[7,8]。本文基于类型理论背景讲述C语言的类型系统的构建过程,为真正的测试自动化解决前期工作问题。
本文有如下贡献:①出工具前端用于处理类型的类型收集系统模型,辅助工具后端收集变量信息。②提出类型收集系统中每个类型所占的内存块模型相关的数据结构。③实现关于程序中类型的收集,并完成对程序进行类型接口插桩,用于工具后端的处理。
CAUT (C analysis and unit testing toolkit)是一个基于动态符号执行开发的,用于C程序单元测试的测试输入数据生成工具,一个针对白盒测试标准的单元测试工具,可以生成测试输入以达到预期的覆盖标准。其主要功能包括两大部分:C程序的分析和变换,主要包括对C程序进行必要的简化和变换,将C程序解析成抽象语法树,从C函数单元中分析出控制流程图等;C程序的单元测试,自动生成测试用例,并且遵循两个测试覆盖标准 (分支覆盖和MC/DC覆盖)。从图1CAUT总流程,可以看出CAUT工具在程序开始阶段,首先完成各个数据结构的初始化操作,随后将一个路径输入前缀传入执行测试执行相关任务模块[9-11]。
图1 CAUT总流程
测试完成后根据执行次数决定程序流程:若执行次数已经达到预设的最大值,或已经符合相关覆盖标准,则完成本次测试并给出覆盖报告;若尚未达到最大执行次数,且尚未达到覆盖标准,则从路径选择模块中选择一条路径前缀,传入执行约束求解任务模块,并将求解结果作为下次输入,传入测试执行模块,继而循环执行本过程。
从上述过程可知,CAUT工作主要含有3个重要子模块:测试执行模块,主要负责运行时的数据收集工作;约束求解模块,对传入的路径前缀进行求解;路径选择模块,主要负责从路径池中挑选路径前缀。
由于本流程中默认输入为已经变形并插桩后的文件,所以在整体工作流程之前,本工程还涉及 “源代码变形分析”重要过程,主要由 CIL (C intermediate language)工具前端处理流程完成。
OCAML (object CAML)是目前语言CAML中最流行的一种变种语言,它是种函数式编程语言。它在CAML语言的基础上增加面向对象层,同时结合模块化思想,带有一个以类型推导为基础的多态类型系统。OCAML有一个巨大并强悍的标准库,可以很方便地开发应用程序。本工具针对C语言的解析和处理工作都是基于OCAML语言,所以需要安装该语言包。
CIL是C Intermediate Language的缩写,它是一个支持对C语言程序进行分析和变换的开源的工具包。CIL是由美国加利福尼亚伯克利大学设计和开发,CIL完整支持C99标准,另外也兼容GNU GCC扩展和 Microsoft VC扩展,实现语言为OCAML。它对C语言解析后的表示形式介于C语言本身和三地址代码之前,消去原始C程序中的复杂结构,但同时包含比三地址代码更丰富的程序信息。另外它也提供一系列的工具,比如StackGuard用于检查缓冲区溢出,Merger用于整个源代码工程代码合并为一个独立的可编译文件,便于进行程序的整体分析。
CAUT工具用于C程序单元测试输入数据自动生成,需要做到将测试用例可视化。在CAUT工具运行时阶段,约束求解器针对程序中的约束进行求解,返回约束中变量的值。但为了可视化测试用例,需要对程序中变量建立类型收集系统,以满足约束求解器返回的值与程序变量之间的对应关系。
在编译程序的过程中,变量的类型包含有用的信息,如类型指定变量的取值范围和对变量所进行的操作。对类型的检查可以大大提高程序的运行效率,例如类型检查可省去变量是否为空的检查。
基本上,类型可分为几个大类:原始类型 (最简单的类型种类,如整数和浮点数);整数类型 (数字的类型,如整数和自然数);浮点数类型;复合类型 (由基本类型组合成的类型,如数组或记录单元);子类型;派生类型 (如结构和联合);对象类型;递归类型;函数类型;全称量化类型;存在量化类型等等。其中,C的类型被分为3个主要组:对象类型、函数类型和不完整类型,对象类型基本上用来声明变量,函数类型用于声明函数,不完整类型是对象类型在一些重要信息,未被提供时的一种特殊情形。一个不完整类型通常需要在被补充上所需的信息后达到完整[12,13]。
类型系统在理论上主要的研究方向是把它作为研究语言的形式化工具和开发语言的形式化方法,建立研究的模型和实现语言的规范[14]。而在本项目中,注重类型系统关于收集类型的实现过程。
类型自身也有结构,把这种结构定义为类型表达式。它可以是基本类型,例如int等,也可以是通过把被称为类型构造算子的运算符作用于类型表达式而得到,例如struct、union等。
本项目基于Alfred V.Aho的Compilers中对类型表达式的递归定义,将其作为类型系统的理论框架,对待测程序中可能出现的类型进行详细分析和设计,包括基础类型和用户自定义类型。
基于Compilers关于类型及类型表达式的定义,需要在编译前端中,依靠CAUT前段工具CIL将C程序源码合并为一个单独的可编译文件,CIL对C语言程序分析并得到源代码的类型信息等相关信息,然后存储到对应的数据库中。
其中,CIL分析源码时,为了记录当前变量的相关信息,需要记录每个类型的信息,所以在此提出一个类型收集系统的构建方案。类型收集系统的一个直接应用就是用于编译程序的开发,本项目基于CIL编译待测程序,CIL作为一个开源程序,提供一套近乎完全的编译前端,也提供用户在其编译前端上做修改,以便用户得到自己所需要的数据结构。本项目欲编译待测程序后,收集运行时数据类型和数据值,以便后续打印。
基于CIL的编译前端中的C语言类型收集系统设计架构主要分为3个模块:Type Visitor、Record Type和Register Type模块。
表1Record Type模块是记录类型的算法:输入为一种类型,输出为包含所有类型的数组。首先检查传入的类型名称在数组中是否存在,如果当前的类型数组中没有,则将类型插入数组中,并分析类型种类,若为非函数类型的复杂类型,则分析当前类型的子类型,若为函数类型,则获取其返回值类型和参数类型。
表1 Record Type模块
表2Type Visitor模块是对待测程序中类型和全局对象分析算法:输入为待测程序,输出为程序中的类型集合。分析程序中的类型和全局对象,如果获取程序中的是全局对象,包括复杂类型和枚举类型,就记录该类型;如果获取的是类型,再分析是不是TNamed(用户自定义类型),如果是,则展开该类型,获取其子类型,如果不是,则直接记录。
表2 Type Visitor模块
表3Register Type模块主要对待测程序进行类型插桩,用于向编译后端提供类型接口:输入为待测程序类型集合,输出为类型插桩函数。首先在待测程序中打印类型插桩函数头,并打印临时变量,然后对记录好的类型数组进行遍历,打印其对应的类型函数,具体如图2所示。
表3 Register Type模块
该类型系统中还有一个辅助模块get_type_content,用以根据类型返回类型的名称和其元类型。类型包括primitive type、数组、函数、指针、复杂、枚举和unsigned long类型。
编译前端关于类型分析和记录的流程如图2类型前端总流程所示:源代码首先要经过Type Visitor调用,该模块会对程序中的类型和全局对象进行遍历,遍历过程中会调用Record_type模块,用于记录类型和全局对象。当遍历完待测程序后,模块Register_type会遍历当前的type_list,每获取其中的一个元素,就打印相对应的类型函数。
编译前端收集到C程序单元的类型系统,记录程序变量的数据类型,在CAUT约束求解模块中,求解器可以求解出在本次迭代中变量的运行时值,但在下一次迭代中该运行时值会被删除,故需要在编译后端先在运行时通过前端插桩函数的响应,完成对所有程序中出现的数据类型原型做记录,方便记录程序变量的每一次迭代所求解出的运行时值。
图2 类型前端总流程
CAUT的类型系统将基础类型、指针类型、结构体、联合体、数组、枚举以及函数类型进行封装,对外表示的数据类型定义为datatype_t(如图3datatype_t数据类型描述的类型信息所示),该数据类型的内部表示为每种类型标识Id,类型名称Name,类型对象所占内存大小Size,元类型Members和类型信息。其中,类型信息用于描述类型详细信息,包括有无符号整型与浮点型。
图3 datatype_t数据类型描述的类型信息
内核在运行时维护一张datatype_table表,该表记录每一个类型信息 (datatype_t指针)和其对应的id,有对应的接口使用指定的标识将类型注册到类型系统中,如果表中存在同一个id的注册,将采用覆盖已存在的注册类型机制。其它接口可以通过类型的标识或者类型名称就可以从该表中获取到类型对象,类型对象就包括该类型的所有信息,在获取结构体、联合体、数组及枚举类型的成员类型时,可按成员序号获取,结构体还可以按偏移量来获取成员类型。运行时结束时,需要释放并回收该表所占内存空间。
内核为了完全满足于可视化程序中变量的测试用例值,还需要存储变量名称以及其逻辑地址,这样,内核在可视化测试用例时候就可以用其逻辑地址在type model中查找运行时值。
类型系统定义了一个input_var_t结构体对象,其数据类型内部表示为变量名称、变量的逻辑地址以及变量在类型系统中注册的值。内核从前端提供的store_input_var接口将待测程序中所出现的输入变量名称、逻辑地址和其类型记录到一张g_input_var_set表中。当运行时结束时,需要清除并回收该表空间。
当约束求解器计算出变量的运行时值时,内核通过调用print_testcase接口输入变量的类型信息和地址值来将测试用例可视化,如表4测试用例可视化表所示,该可视化表显示迭代次数,变量名称,变量类型和变量的运行时值。该接口实现打印基础类型、指针、数组、结构体和联合体等类型的功能。打印结构体变量需要累加偏移,打印指针时,需要将其本身地址转化成其指向成员的真实地址。
表4 测试用例可视化
本项目已经在CAUT中实现类型系统,为了测试该类型系统设计的有效性,本文对一些开源程序进行编译测试,检查是否对待测程序中出现的类型有完整的收集和表达。
本文以开源程序grep中的grep_xrealloc_1.c文件作为示例,表5grep_xrealloc_1.c文件是该文件的代码。
表5 grep_xrealloc_1.c文件
在本项目下首先生成编译文件 (./configure),然后编译CAUT项目 (make),然后输入相应的命令执行,则该文件对应的类型文件grep_xrealloc_1.cil.c就存在该路径下,该文件详细记录待测程序中的变量类型,函数返回类型和函数参数类型以及类型插桩函数。表6待测程序类型表包括类型种类Type、类型名称Type_name和复杂类型的成员Member。
表6 待测程序类型
表7待测程序类型插桩函数包含类型插桩函数,其中__CAUT_ctype_t为CAUT工具自定义的类型,用于定义类型插桩函数__CAUT_create_primitive_type的返回值,该函数有4个参数,第一个为类型名,第二个为类型名长度,第三个为类型所占字节大小,第四个为类型id号。__CAUT_reg_ret为CAUT注册数据类型函数__CAUT_register_datatype的返回值,该函数有两个形参,第一个为id号,第二个为对应id号的类型插桩函数的返回值。
通过编译前端记录的这些类型信息,交给编译后端,编译后端通过接收前端传入的类型插桩函数来建立一张datatype_table表,这里只列出跟待测函数相关的变量类型datatype_name、类型名称var_name和在内存中所占的空间大小var_size。具体如表8datatype_table表所示。
表7 待测程序类型插桩函数
表8 datatype_table表
编译后端通过约束求解器根据不同的分支返回变量的值,类型系统通过获取内存中的值和对应的类型将值可视化。在dfs策略 (depth-first search)下,grep_xrealloc_1的测试用例如表9grep_xrealloc_1.c在dfs策略下的测试用例所示:该图可视化迭代次数,其中每行显示3个域,第一个是变量名称,第二个是变量类型,第三个是变量值。
表9 grep_xrealloc_1.c在dfs策略下的测试用例
目前对于类型系统的研究很广泛,本文首先介绍关于类型和类型系统的基本概念,并提出用CIL构建C语言程序的类型系统。解决当下测试自动化工具中测试用例可视化的问题,帮助测试工作完全的自动化,节省测试工作的投入。
对于研究和设计程序设计语言,类型系统为其提供形式化的工具和方法,对软件工程具有重要的意义。我们用实验验证该类型系统的有效性,将来我们的工作是有关于类型检查的研究。
[1]Boonstoppel P,Cadar C,Engler D.Rwset:Attacking path explosion in constraint-based test generation [C]//Proceedings of the Theory and Practice of Software,14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems,2008:351-366.
[2]Atif M Memon,Myra B Cohen.Automated testing of GUI applications:Models,tools and controlling flakiness [C]//Proceedings of the International Conference on Software Engineering,2013.
[3]Inderveer Chana,Priyanka Chawla.Testing perspectives for cloud-based applications [J].Software Engineering Frameworks for the Cloud Computing Paradigm Computer Communications and Networks,2013:145-164.
[4]Nguyen,CD,Marchetto A,Tonella P.Test Case prioritization for audit testing of evolving Web services using information retrieval techniques [C]//IEEE International Conference on Web Services,2011.
[5]Ho Cheng-Yuan,Wang Fu-Yu,Tseng Chien-Chao,et al.NAT-compatibility testbed:An environment to automatically verify direct connection rate [J].IEEE Communications Letters,2011,15 (1):4-6.
[6]Huang W Y,Hu J W,Lin S C,et al.Design and implementation of automatic network topology discovery system for international multi-domain future internet testbed [J].Journal of Internet Technology,2013,14 (2):181-188.
[7]Tarik Nahhal.A formal framework of hybrid test cases generation applied to embedded systems [J].IJCSI International Journal of Computer Science Issues,2013,10 (2):337-345.
[8]Burnim J,Sen K.Heuristics for scalable dynamic test generation [C]//Washington,DC,USA:Proceedings of the 23rd IEEE/ACM International Confere-nce on Automated Software Engineering.IEEE Computer Society,2008:443-446.
[9]Yu Xiao,Sun Shuai,Pu Geguang,et al.A parallel approach to concolic testing with low-cost synchronization [C]//Shanghai,China:Proc the 4th International Wokshop on Harnessing Theories for Tool Support in Software,2010.
[10]Wang Zheng,Yu Xiao,Sun Tao,et al.Test data generation for derived types in C program [C]//Tianjin,China:Proc the Third IEEE International Symposium on Theoretical Aspects of Software Engineering,2009.
[11]Anand S,Godefroid P,Tillmann N.Demand-driven compositional symbolic execution [C]//Procee-dings of the Theory and Practice of Software.14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems,2008:367-381.
[12]Indrdeep Ghosh,Nastaran Shafiei,Li Guodong,et al.JST:An automatic test generation tool for industrial Java applications with strings [C]//Proceedings of the International Conference on Software Engineering,2013.
[13]Tillmann N,De Halleux J.Pex:White box test generation for.Net [C]//Proceedings of the 2nd International Conference on Tests and Proofs,2008:134-153.
[14]Li Guodong,Li Peng,Geof Sawaya,et al.GKLEE:Concolic verification and test generation for GPUs [J].Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.2012,47 (8):215-224.