基于时序逻辑的编译优化测试用例生成方法.docx

基于时序逻辑的编译优化测试用例生成方法.docx基于时序逻辑的编译优化测试用例生成方法摘要:提出一种基于时序逻辑公式的关键节点控制图生成方法,生成的测试用例针对性强,容易扩展;并以该方法改进了一种编译优化自动化测试工具,在很大程度上消除了其测试冗余,提高了测试效率。关键词:编译优化;测试用例;时序逻辑;基本块;关键节点控制图中图分类号:TP301文献标志码:A文章编号:1001-3695(2007)07-0046-030引言??编译器是软件开发的基础支撑工具,其正确性直接影响到应用软件的可靠性。它需要通过充分测试以保证其质量。编译器测试用例生成方法可以分为针对前端语法语义的用例生成方法和针对后端优化算法的用例生成方法两大类[1]。??针对前端语法语义的测试用例生成方法的基本思想是基于语言文法生成测试用例,用于编译器前端翻译功能的测试[2,3]。随着编译技术的发展,优化技术逐渐成为编译技术研究的核心内容,出现了一些针对后端优化的测试用例生成方法,文献[4]介绍一种针对编译后端优化的基于文法生成代码的优化测试用例生成方法。首先基于文法生成标准的源程序,再根据具体的优化技术特点加入新的语句以满足特定优化条件。该方法仍属于基于文法的用例生成方法,针对性较弱,具有较大局限性。文献[5,6]对不同的优化类型进行建模,再将模型映射到程序文本作为测试用例。此方法有较好的针对性,但其建模过程和模型映射过程需要对不同的优化进行不同的定制,实现较为复杂。由中国科学院软件所研制的JTT是一个面向编译优化的自动化测试工具,它用于嵌入式环境下的C++优化编译器的系统测试和回归测试[7]。JTT在自动生成程序控制结构的基础上,通过某些特定的随机策略添加计算赋值语句,从而生成完整的测试用例。它缺乏对特定优化精确的形式化描述,难以生成有针对性的优化测试用例,存在大量测试冗余。文献[8]使用基于时序逻辑的条件重写规则LHS→RHSifΦ精确刻画了编译优化。其中条件Φ用时序逻辑公式描述。??1基于时序逻辑的编译优化描述??典型的优化变换能采用基于时序逻辑的条件重写规则LHS→RHSifΦ来作精确刻画[9]。变换由两部分组成,即变换的一系列动作和保证变换正确性的条件。变换动作通过程序控制流图中节点和连接边的变化表示;有四种基本动作,即节点替代(Replace)、边删除(Remove_edge)、边添加(Add_edge)和边分裂(Split_edge)。如图1所示,节点替代是用一系列的节点替代控制流图中的某个节点;删除边和添加边分别是移除和添加控制流图中的连接边;分裂边是在相连接的两节点间插入中间节点。??3讨论及应用??上述算法分为两个阶段:公式规整化和节点生成。其中公式规整化阶段将每个条件的公式转换为标准形式,以便节点生成阶段的处理;节点生成阶段则生成关键节点及关键节点之间的控制流。该算法需要的内存空间与公式中所涉及到的节点数量成正比,需要的时间与条件数目以及节点数目成正比。因此,算法一定可以在有限时间内结束。??构造出一个基本块的关键节点控制图后,可以此为模板很方便地生成大量有针对性的测试用例;可以使用随机策略或启发式策略,在关键节点控制图的节点之间插入新的节点。插入的新节点需要满足插入点之前紧邻关键节点的前向属性,也需要满足插入点之后紧邻关键节点的后向属性。??本文基于前面介绍的方法对JTT工具作了改进,用脚本描述了基于CTL的