基于程序理解的软件测试方法

摘 要:为满足大规模软件开发的需要,自动化成为软件工程迫切的要求,并贯彻到软件设计、开发和维护的各个阶段。本文提出一种以可计算函数为基础的程序理解方法,最大程度地识别函数功能、验证组件的安全属性,实现对源代码、二进制代码的函数理解,以精简的函数表达式和并发赋值形式展示函数理解结果,提高人工阅读程序的效率,并且以可计算函数程序理解方法辅助软件测试用例生成,对软件安全的属性进行评估。将软件工程中的软件设计规范、软件产品、安全属性等转换成可计算过程实现软件工程的智能管理。

关键词:可计算函数语言 并发赋值形式 表达式传播

中图分类号:TP31文献标识码:A文章编号:1674-098X(2011)01(b)-0032-03

软件开发的复杂性和代价一直以来都是软件工程中的难题。由于软件产品中大量的底层代码细节和交错的关系迅速超过了理解和记忆的范围[1-2],复杂性极大地限制了软件开发规模,成为软件工程中的固有症结。特别是在软件测试过程中,测试人员阅读所有的设计文档、使用手册、甚至源代码,大量的时间消耗在软件功能理解上。软件复杂性也限制了测试工作的效率。软件开发代价与软件复杂性密切相关,未能正确地估计软件的复杂性常常使得软件开发的开销超过了预算。在现代软件工程中软件开发规模必须加以控制,才能保证软件的质量。

到21世纪,在开发超大规模软件的需求下,新一代软件工程急需要科学的自动化软件管理工具和技术,贯彻软件整个生命周期。下一代软件工程的主要目标是使得软件工程成为可计算过程。软件工程的每个过程都应该成为可计算的评估过程,这包括软件需求说明、软件设计规范、软件实现和软件测试的全过程,可计算过程能够在系统软件的控制下,实施精确计算和评估。

近几年来,人们已经关注到下一代软件工程理论基础和技术的研究。Linger、Pleszkoch和Hevner[1-4]等人提出了函数功能自动抽取技术,并应用到对恶意代码分析中。Function Extraction[8]项目成为Cert软件安全资助的在研项目之一。Function Extraction技术还被用于软件验证[1]、软件测试[2]和恶意程序辅助理解中[4]。Function Extraction将影响软件工程的多个方面[3]。

实现计算机对程序的自动理解一直是研究人员追求的目标之一。Pleszkoch提出使用函数抽象方法理解程序的功能[5],认为程序理解的基础是函数理论[6]。随着程序理解研究的深入,程序理解已经被应用到软件智能调试、软件自动测试和软件安全漏洞发掘等领域。随着符号执行和抽象解释等新方法的引入,程序自动理解将从外部和内部来自动识别程序的运行时的特征。其他的软件工程使用的技术如基于序列[7]、统计的软件验证技术、模型验证技术、可携带证明代码等都成为当前研究的热点。

本文主要讨论了下一代软件工程的最新研究领域:程序自动理解技术。函数功能理解是最大限度地理解函数功能、验证程序的正确性和控制软件质量。可计算函数程序理解是下一代软件工程的基础技术,只有让计算机从语义上理解了函数功能,才能真正做到软件工程自动化。

1 并发赋值形式

函数理论观点为函数功能计算提供了数学基础。按照可计算函数理论,程序具有普通函数特点,程序将数据从输入域映射为输出域,可以认为程序是函数的集合,不管程序处理的何种对象和使用何种编程语言,都是将输入映射到输出。函数理论方法的核心是识别程序每个基本结构的功能以及它们的组合关系。

计算机程序是一种典型的序列逻辑,语句的执行有严格的序列关系,这种冗长的序列逻辑关系影响了函数功能的理解。计算机程序运行的基本特点是按照指定的序列顺序执行,执行的上下文保存在动态内存中,计算机可以丝毫不差的按照程序规定的指令运行。

由于受到人的记忆的限制,程序运行时上下文环境和复杂的逻辑结构是人工程序理解的最大障碍,并发赋值是以并发程序为基础的程序表示形式,并发语句之间没有先后次序,每一条语句都是一个独立的功能单元,并发语句基本形式记做:

[C1→Assign1; C2→Assign2;…;]

并发赋值的函数理解就是将顺序执行的函数转换成并发语句形式,并发语句就是函数的独立功能,这种转换的过程就成为函数功能理解的过程之一。

2 可计算程序理解

程序是由多个有限大小的基本结构组成,每个基本结构都可以使用函数的方法表示输入到输出的转换,因而程序可以用函数的集合表示。函数功能理解是新一代软件工程的基础技术,只有让计算机从语义上理解了函数功能,才能真正做到软件工程的自动化。

可计算程序理解主要过程可以分为程序基本块计算、表达式传播和程序理解结果解释。程序理解结果解释主要是以合适的方式展示程序理解的结果,是程序理解的后端。

并发赋值程序最大的特点是与过程无关,使用可计算的函数表示软件的控制流和数据流,提供函数功能理解的基础。在通用程序设计语言中,顺序结构和条件语句结构能够直接转换成并发赋值语句;对于循环结构则使用递归等式和选择结构表示。例如在程序P中,条件语句q,分支操作语句分别是g和h,程序P可以转化成并发赋值程序f。

P: if q then g else h endif

f =T(P)

CCA: f=([q]=true→[g]|[q]=false→[h])

条件选择程序P转换成并发赋值程序f,可计算函数f是两个分别具有条件判断的并发语句。while语句是循环结构的典型形式,使用可终止递归函数表示while语句块功能[2]。

P1:while q

do g

end while

while循环语句转换成等价CCA形式程序f:

f＝T(P)

CCA: f = [ if q then g; while q do g enddo endif ]

简单赋值语句是并发赋值程序的基本形式,也是最简单的函数,是数据从输入到输出的不变转移。表达式传播是数据经过变换、转移到达目标变量的过程,传播的基础就是并发赋值语句。对于复杂的程序设计结构,如顺序和选择结构的程序可以直接使用函数组合的方法计算程序功能。函数组合使用基本的代数运算符号连接两个或多个可计算函数,如选择符号‘|’、并且符号‘&’、组合‘o’等等。可计算函数传播的过程是自底而上逐步构建整个函数树的抽象过程,程序控制结构最终转换成与过程无关的并发赋值形式。每一条并发赋值语句都是程序功能的一部分,并发赋值语句直接解释了程序功能。

3 软件测试

为保证软件使用的可靠性,通常在产品发布前要经过多种测试,目前软件测试的方法主要是黑盒测试、灰盒测试和白盒测试。软件测试和验证是既耗时又耗力的过程。无论使用何种软件测试方法,测试员都需要掌握测试对象的功能。软件设计和实现文档可以帮助测试人员了解软件的基本操作,但是难以提供代码级别的测试信息,测试员只能通过阅读源代码的方法,进一步获取函数内部功能信息。

因此全面反映程序功能的函数理解技术对软件测试过程和结果将产生巨大影响。由于软件测试的主要目标是验证软件的功能,可计算函数程序提取函数的语义信息,以增加人们对程序分析、验证和测试的能力。下面以一个例子阐述可计算函数程序在软件测试中的应用。

三角形的边长必须满足一定的条件才能够组成三角形,检查这三个整数的C程序,首先检查三个整数是否是正数,然后检查两边之和是否大于第三边。

int triangle(int a,int b,int c)

{

int answer = 1;

if(a<=0|b<=0|c<=0)

answer = 0;

if(a+b<=c|a+c<=b|b+c<=a)

answer = 0;

return answer;

}

经过VC＋＋ 6.0编译生成可执行文件。在对部分软件进行功能测试时,无法提供源代码,对软件功能的测试只能从二进制文件开始。可计算函数的程序理解可以直接对机器码进行翻译并进行功能分析。使用IDA pro对三角形判断函数反编译,结果如图1所示。按照二进制代码的可计算程序理解方法对IDA 反编译的结果进行并发赋值语句转换与表达式传播计算,程序理解输出计算后的结果。

[

1. Arg_0:=signed_32(M,4 +d ESP)

2. Arg_4:=signed_32(M,0c +d ESP)

3. Arg_8:=signed_32(M,18 +d ESP)

4. dl:=(Arg_4 +d Arg_8<=Arg_0)

5. bl:=(Arg_0 +d Arg_4<=Arg_8)

6. al:=(Arg_0 +d Arg_8<=Arg_4)

7. (Arg_0<=0|Arg_4<=0|Arg_8<=0) → return 0

8. (al|bl|dl)→ return 0

9. (┒(al|bl|dl| Arg_0<=0|Arg_4<=0|

Arg_8<=0)) → return 1

]

输出结果的开始部分是函数参数定义,参数Arg_0、Arg_4、Arg_8分别位于函数栈中,signed_32表示参数是双字大小,+d代表有符号32位整数加法,dl、bl、al保存了比较的结果。下半部分是函数返回时参数需满足的不同条件:如果任意一个参数小于等于0,则返回结果0;如果任意两个参数之和比第三个参数小,则返回0,其他情况返回1。相对于软件IDA pro 反编译的的代码,可计算函数分析结果清晰得多,也便于人员理解。

对于函数功能测试,根据可计算程序理解分析结果,在函数功能测试中7、8、9三条CCA语句分别代表了三个测试区域。可计算程序理解将大量的测试用例划分成三个区域,每个区域只需要选择代表性的例子就可以覆盖整个功能测试区域。如果对程序的安全性进行检查,还能够发现程序存在整数溢出的可能。例如在语句4,+d表示32位整数加法,实际上是dl:=((Arg_4 +d Arg_8)Mod32<=Arg_0),只要Arg_4、Arg_8之和超过2^32,则发生整数溢出,计算的结果可能不准确,例如参数为2^32-1、2^32-1、100,函数返回0,程序发生整数溢出而出现错误。而常规的软件覆盖测试,如语句覆盖、分支覆盖、和路径覆盖等不能发现此类漏洞。

4 总结与展望

函数编程语言、PCF、SSA等可计算函数方法作为计算机程序的形式研究的方法,以数学计算为基础,体现了数学公式精确、简洁等特点。可计算函数的程序理解方法将程序看作是一个数学函数,将输入数据映射为输出结果,用数学公式表述函数的执行过程,结合控制流图和表达式传播计算方法抽象出函数的最终功能,对函数功能按照特征分类存入功能数据库中。可计算函数的程序理解方法能够对源代码程序自动分析,对于二进制代码程序,需要在反编译工具的辅助下,直接分析汇编代码,减轻了软件维护和软件测试人员的负担。

受到人力的限制,下一代软件工程需要广泛的自动分析和验证软件产品的能力,从软件规范、设计到软件实现的各个环节,软件产品都需要在可控和可计算的范围内,可计算函数的程序理解以数学理论为基础,能够适应源代码、中间级代码、汇编代码等多个层次的对象,成为新一代软件工程的重要方面。

可计算函数的程序理解方法在新一代软件工程还能用于软件质量管理:

(1)软件组件正确性验证计算

提高软件工程中可靠组件的粒度,例如对于上亿行代码的系统,如果每个可靠组件大小是千行,那么系统就包含十万个单元组件。对于千行左右的组件,使用可计算函数理解的方法,短时间内就能够验证组件功能的正确性。

(2)软件质量属性计算

软件工程必须实时估计软件质量,例如对性能和安全属性检查。软件性能属性主要表现在算法的时间复杂度和空间复杂度,可计算函数程序理解方法将程序转换成数学公式形式,容易估算出算法时间和空间的开销。软件安全属性检查是验证操作用户身份、授权,保证程序运行时数据机密性以及不能对其他并行系统造成危害。使用可计算函数理解的方法,短时间内就能够估算出性能的优劣和安全的级别。

参考文献

[1]Linger R,Prowell S,Bartholomew R,et al. Function extraction: automated behavior computation for aerospace software verification and certification[C].California:IEEE Computer Society Press, Los Alamitos,2007.

[2]Pleszkoch M,Linger R,Hevner A.Introducing Function Extraction into Software Testing [J].The database for Advances in Information Systems,2008,39(3):41-50.

[3]Pleszkoch M,Linger R. Improving Network System Security with Function Extraction Technology for Automated Calculation of Program Behavior[C].Hawaii USA:IEEE Computer Society Press,Los Alamitos,2004.

[4]Collins R,Hevner A,Walton G, and Linger R.The Impacts of Function Extraction Technology on Program Comprehension:A Controlled Experiment.Information and Software Technology,2008.

[5]Hausler P,Pleszkoch M,Linger R et al.Using Function Abstraction to Understand Program Behavior[J].IEEE Software,1990,7(1):55-63

[6]Pleszkoch M,Hausler P,Hevner A et al.Function-Theoretic Principles of Program Understanding[C].Proceedings of the 23rd Annual Hawaii International Conference on System Science (HICSS35).Hawaii:IEEE Computer Society Press, Los Alamitos,CA,January,1990.

[7]Prowell S,Poore J.Foundations of Sequence-Based Software Specification [J].IEEE Transactions on Software Engineering,2003,29.

[8]Function Extraction Project .cn/qkpdf/kjdb/kjdb201102/kjdb20110222-1.pdf" style="color:red" target="_blank">原版全文

推荐访问:理解 测试 程序 方法 软件