中国科学院新疆理化技术研究所机构知识库
Advanced  
XJIPC OpenIR  > 多语种信息技术研究室  > 学位论文
题名: 基于约束的测试用例生成中可扩展性问题研究
作者: 王轶
答辩日期: 2013-05-24
导师: 蒋同海
专业: 计算机应用
授予单位: 中国科学院大学
授予地点: 北京
学位: 博士
关键词: 符号执行 ; 约束求解 ; 可扩展性问题 ; 中间计算结果重用
摘要: 软件测试作为保证软件质量的重要手段,一直是计算机工程领域科学界关注的一个重要问题,已经成为软件生命周期中的重要组成部分。其中测试用例的设计与生成 是决定软件测试效果的重要因素之一。基于约束的测试用例生成是一种基于符号执行与约束求解技术的形式化方法,能够生成高覆盖、无冗余的测试用例集。这一方 式是当前被广泛认可的一种测试用例自动生成方法,也是大多数现有测试用例自动生成工具的底层技术。但其仍然受到可扩展性等问题困扰,使其实际应用受到极大 限制。本文针对这一技术面临的可扩展性问题,提出了两项优化策略来提高用例生成的效率:1.共享的解匹配策略(Shared Solution Matching Strategy,SSM)昂贵的约束求解开销是引发测试用例生成中可扩展性问题的重要原因,复杂的路径条件表达式和用例生成过程中频繁的求解器调用也加 剧了这一现象。共享的解匹配策略使用一种中间计算结果的重用机制,来降低约束求解的开销,提高测试用例生成效率。SSM通过对符号执行中路径可行性验证过 程进行分析,将本应被抛弃的中间计算结果转化为测试路径的潜在解,用简单约束的可满足性匹配代替对整个路径条件的约束求解过程,降低测试路径可满足性验证 过程的时间开销。同时在符号执行的搜索过程中对潜在解进行传递和迁移,保证每一个潜在解都能够到达程序出口。这一过程实现了对表示路径条件的SMT表达式 优化,能够通过对不完整的路径条件求解获得最终的测试路径,并能够帮助符号执行提高应对复杂约束条件的能力。最终将两者结合构成共享的解匹配策略,完全消 除了不必要的约束求解调用,使符号执行过程中对求解器的调用次数仅为可行路径与约束冲突的和,有效的降低了测试用例生成中约束求解的开销。2.跳步的循环 边界覆盖策略(Jumping Boundary Coverage Strategy,JBC)在符号执行中,循环结构往往带来大量的测试路径和求解器调用,导致严重可扩展性问题。本文借鉴已经在业界广泛使用的手工白盒测 试中对循环结构的处理方式,提出一种跳步的循环边界覆盖策略来缓解这一问题。这一策略的实现分为两个过程:在搜索过程中对循环结构的探测和对非关键路径的 剪枝。本文通过对编译后循环结构的分析,提出了一种符号执行过程中循环结构的探测模型,能够在运行时同步的识别出被测代码的循环结构。然后应用共享的解匹 配策略,减少约束求解器调用次数,并且能够避免在循环入口处对因跳出循环导致的不可行路径进行约束求解验证,降低循环覆盖测试过程中的时间开销。最后提供 一种灵活的跳步剪枝策略来削减非关键路径,能够给测试人员提供更多的选择,在测试有效性和测试效率之间依照实际情况作出权衡。最后,本文以NASA的开源 项目SPF(Symbolic PathFinder)为基线系统,对上述两项优化策略进行评估。与SPF相比,SSM能够减少测试用例生成过程中约60%的约束求解器调用次数,降低约 30%的约束求解时间开销,极大的缓解了约束求解过程带来的可扩展性问题。在对循环结构进行覆盖测试时,JBC优化策略能够减少一部分对不可行路径的约束 求解判定次数,在本文中的例子中降低了至少20%的时间开销。配合灵活的跳步剪枝策略后,可以让测试人员依据测试任务的需求大量的削减循环结构产生的非关 键路径。
英文摘要: As an important means to ensure software quality, software testing has become an important part of the software life cycle. It has been an important issue of concern by the scientific community in the field of Computer Engineering. Test case generation is one of the important factors to determine the effect of software testing.Constraint-based test casegeneration is a formal method based on symbolic execution and constraint solving technology, capable of generating high-coverage and non-redundant set of test cases automatically. This is a widely recognized automatic test case generation method, as well as the underlying technology of most existing automatic test case generation tools. However, it still suffers from scalability problems and be limited in practice.
内容类型: 学位论文
URI标识: http://ir.xjipc.cas.cn/handle/365002/2467
Appears in Collections:多语种信息技术研究室_学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
王轶博士论文.pdf(2152KB)学位论文--暂不开放View 联系获取全文

作者单位: 中国科学院新疆理化技术研究所

Recommended Citation:
王轶. 基于约束的测试用例生成中可扩展性问题研究[D]. 北京. 中国科学院大学. 2013.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[王轶]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[王轶]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
文件名: 王轶博士论文.pdf
格式: Adobe PDF
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Powered by CSpace