基于内存建模的复杂结构类型测试数据自动生成方法

针对链表、树和图等这类复杂结构类型的测试数据自动生成问题,提出一种面向路径的基于内存建模的测试数据生成方法.采用一种将结构变量和数值变量分别建模的抽象内存模型,并利用此模型辅助符号执行被测路径;把路径执行过程中语句的语义操作映射到对抽象内存的操作,解决指针引起的别名问题,并且在抽象内存中精准地记录了路径的约束条件;最后通过约束求解得到测试数据.文中方法已应用于自主开发的自动单元测试系统——UATS,通过实验证明了该方法的可行件.     

基于存储访问模型的细粒度存储变量识别算法

现阶段对变量的识别通常采用基于特定编译习惯及内存访问地址模式匹配的方法,或基于内存模型和抽象解释的分析方法。前者针对性太强,不具备普适性;后者通常采用损失算法精度的方法来得到结果,这往往会造成识别变量粒度过大、漏识别和误识别率较高。首先定义一种存储访问模型,对存储操作进行细粒度的模拟;然后给出基于存储访问模型的抽象状态生成算法,实现了基于高级中间语言HBRIL的细粒度数据信息(抽象状态)的跟踪和记录;基于这些抽象状态设计了存储区域内的细粒度变量实体识别算法;最后通过测试给出变量识别的细化比例和识别率。由测试结果可以看出,该算法在动态分配变量的识别率方面具有明显优势。     

一种基于双约束传播的面向路径自动随机测试方法

随机测试是一种常用的软件测试自动化方法。该方法随机地从程序输入域中选取测试输入,其自动测试实现容易。但随机地从输入域中选取满足某种测试准则的输入数据,测试生成效率较低。为此提出了一种基于双约束传播的面向路径自动随机测试方法,通过对输入变量的取值范围进行切分,执行两次约束传播来求取指定路径的输入域,在此基础上开发了一个自动随机测试生成系统,并与PRT方法进行了实验对比分析。结果表明,该方法计算出的路径输入域更加精确,可有效地减少对无效域的测试生成,提高了随机测试的效率。     

基于局部堆内存抽象表示的堆操作程序内存泄露检测

堆操作程序通过共享易变数据结构可灵活地申请、合并、删除堆内存.这类程序的内存泄漏检测要求精确的域敏感的指针别名信息,变得尤其复杂和难以处理.针对这个问题,提出了基于"指针扩展类型"域敏感的堆内存抽象方法,对指针变量在形态上的排列关系进行抽象以支持堆的局部推理.首先,定义了各种基本语句的操作语义,然后基于该抽象方法采用前向数据流迭代算法提出了一种新的内存泄露检测算法.在Crystal编译框架下实现了面向C程序的内存泄漏检测原型工具Heapcheck,该工具支持复杂数据结构内指针型数据域上的内存泄露检测.在典型基准C程序上的实验结果分析表明,该方法与现有的技术相比在效率和精度上都具有优势.     

一种面向堆操作程序内存安全性的域敏感内存模型

堆操作程序具有通过共享易变数据结构动态操纵堆内存单元的特性,使得内存安全性难以保证。针对这个问题,提出了一种域敏感的k-limit内存抽象模型,以支持动态调整抽象的粒度,取得静态分析在精度和效率上的平衡。分别从框架、性质、操作方面介绍了该内存模型,然后结合内存安全性的定义,在基于该模型的操作语义框架内定义了4种与内存安全性相关的错误类型,最后设计了基于该模型内存安全性检测的数据流迭代算法。     

路由协议的符号化测试生成

协议一致性测试用于验证协议实现的正确性.文中根据路由协议的消息复杂特点,提出基于on-the-fly策略符号测试生成与动态执行的算法:建立了一种新的统一符号语义模型,该模型把数据操作和控制都抽象为动作行为;以该语义模型为基础,扩展了行为之间的关系以及一致性测试关系;给出了基于on-the-fly策略符号测试生成与符号动态执行的算法,在符号动态执行中,使用了统计的聚类算法来进行符号的数据选择.论文最后用具体的测试例说明该算法在OSPFv3协议一致性测试上的应用.     

一种用于类测试的改进型EFSM模型

扩展有限状态机(EFSM)中迁移存在前置条件和相应操作,而前置条件和相应操作中变量的相互依赖性导致了EFSM中存在不可达路径,不利于基于EFSM模型的类的测试。通过把UML状态图转换成EFSM模型,提出一种消除EFSM模型不可达路径算法,从而建立一种用于面向对象软件的类测试模型,通过该模型可以应用传统的数据流和控制流分析技术对类进行测试。     

基于抽象符号表的内存模型

符号执行技术在软件测试和程序验证中发挥着重要作用。如何抽象和处理程序中各种数据类型和语法成分是符号执行必须解决的问题。本文提出抽象符号表的概念,以及基于抽象符号表建模内存的方法。抽象符号表记录可寻址对象的名称、类型、抽象地址和符号值,是一种简单、精确的内存抽象机制。内存模型是所有使用符号执行的技术的前提,本文系统给出了一个面向符号执行的内存模型。基于抽象符号表的内存模型能够统一处理各种数据类型和语法成分,包括函数和类,能够直接处理指针别名问题,不需要额外的别名分析算法。经过一些性能优化处理,基于抽象符号表的内存模型具有较好的性能。     

EFSM模型的字符串类型测试数据自动生成

基于软件描述模型的测试数据自动生成研究中,字符串类型测试数据生成是一个研究热点和难点。EFSM模型是一种重要的软件描述模型。分析了EFSM模型的特点,针对面向EFSM模型目标路径的字符串测试数据生成,建立了字符串输入变量模型和操作模型,结合静态测试的特点,给出了通过字符串变量模型在目标路径上的符号执行结果生成字符串类型测试数据的方法。实验结果表明,该方法能够达到预期效果,提高测试生成效率。     

航天软件测试模型构建与应用

针对航天软件高可靠性的特点,构建一种输入与输出模型测试方案,提出基于覆盖测试算法的测试方法,测试覆盖算法主要包含三种功能测试方法和三种结构测试方法。功能测试主要使用基于边界的方法、定义等价类、使用决策表分析三种方法。结构测试主要使用基于路径的测试、数据流测试、片测试三种方法。实例验证,该方法清晰明了、便于发现航天软件缺陷、降低航天软件开发风险与代价以及保证航天软件质量。     

基于自适应粒子群优化算法的测试数据扩增方法

针对在回归测试中原有测试数据集往往难以满足新版本软件测试需求的问题,提出一种基于自适应粒子群算法（APSO）的测试数据扩增方法。首先,根据原有测试数据在新版本程序上的穿越路径与目标路径的相似度,在原有的测试数据集中选择合适的测试数据,作为初始种群的进化个体;然后,利用初始测试数据的穿越路径与目标路径的不同子路径,确定造成两者路径偏离的输入分量;最后,根据路径相似度构建适应度函数,利用APSO操作输入分量,生成新的测试数据。该方法针对四个基准程序与基于遗传算法（GA）和随机法的测试数据扩增方法相比,测试数据扩增效率分别平均提高了约56%和81%。实验结果表明,所提方法在回归测试方面有效地提高了测试数据扩增的效率,增强了其稳定性。     

时间Petri网在渗透测试中的应用

渗透测试攻击模型作为渗透测试的重要环节,受到学术界和工业界的共同关注。现有的渗透测试攻击模型未考虑渗透测试攻击过程中的动态参数,无法描述漏洞的发生时间。本文以漏洞为基本单元,以时间Petri网中库所的时间区间表示漏洞的发生区间,构建以时间Petri网为基础模型的渗透测试攻击模型。首先,将漏洞列表作为输入来构建单漏洞模型;然后,将单漏洞模型集合通过模型整合算法形成完整的渗透测试攻击模型;最后,给出渗透攻击路径选择算法,并通过模拟实验验证本文所提渗透攻击路径选择算法的有效性。     

一种面向形式化表格需求模型的测试用例生成方法

现代安全关键性系统的软件规模和复杂性的快速增长给这类安全关键性软件系统的开发带来了很多挑战。传统文本文档的需求描述方法无法保证此类系统的开发进度和系统可靠性要求。为此文中提出了一种兼具可读性和可自动分析的形式化表格需求建模方法。文中介绍了一种针对这种表格模型测试用例的自动生成方法,工作包括对该形式化需求表格模型展开语义分析,建立需求模型的控制树结构,得到其测试等价类;为了减少不必要的测试,定义了不同安全级别的软件需求模型的测试覆盖标准,并针对不同覆盖率准则分别给出基于控制树结构的测试路径约束选择方法;对于每条路径约束测试等价类,提出了基于域错误的测试用例选择方法,能够自动生成所需的检测域错误的测试用例集。最后,通过一个需求模型实例展示了所提方法的有效性。     

基于抽象内存模型的内存相关漏洞检测方法

针对现有的内存相关漏洞检测方法中存在依赖指针数据流而导致大量误报漏报、缺乏漏洞特征的形式化描述以及漏洞特征描述不全面的问题,提出一种基于抽象内存模型的内存相关漏洞检测方法.对抽象内存模型进行相关定义;基于抽象内存模型,对内存泄露、重复释放内存和读写释放后的内存这三种与内存相关的漏洞类型的特征进行形式化符号表示;基于代码...     

基本路径测试用例设计算法

McCabe提出的基本路径测试法(McCABE T J. A complexity measure. IEEE Transactions on Software Engineering, 1976, SE-2(4): 308-320)是动态白盒测试技术中严谨而有效的方法,但存在测试用例设计效率较低的问题,影响了该方法在工程项目中的广泛应用。为了解决这一问题,从被测程序的基本结构出发,提出一种基于组合的基本路径测试用例设计方法。创建一种基于Z路径覆盖的基本单元图,构建由基本单元图组合形成控制流图的组合规则,以此为基础提出了基本路径组合算法,该算法只需一次扫描程序得到程序基本结构的路径集,将这些路径进行组合即可生成被测程序的基本路径集。该方法比McCabe所提出的方法构造过程简洁,能有效提高基本路径测试用例设计的效率。     

Java自动化基本路径测试研究

针对Java单元测试自动化程度和测试效率较低的问题,对基于Java程序的基本路径测试方法进行研究,提出了基于Java代码的基本路径生成方法和程序插桩方法,给出了插桩节点和控制流图节点的定义。首先,通过对Java源代码进行分析,构建程序的控制流图,进而对控制流图进行遍历生成基本路径集合;然后,对被测程序进行插桩,以获取程序的执行路径,插桩过程中保持节点和基本路径中的节点一致,使得插桩后的被测程序执行时得到的路径能够和基本路径集合进行自动化比对;最后,通过以测试数据为输入执行被测程序,对执行路径和基本路径进行比较,判断测试数据集对基本路径的覆盖度。通过实验,验证了所提出方法的有效性。     

改进的潜在语义分析中文摘录方法

中文摘录是一种实现中文自动文摘的便捷方法,它根据摘录规则选取若干个原文句子直接组成摘要。通过优化输入矩阵和关键句子选取算法,提出了一种改进的潜在语义分析中文摘录方法。该方法首先基于向量空间模型构建多值输入矩阵;然后对输入矩阵进行潜在语义分析,并由此得出句子与潜在概念(主题信息的抽象表达)的语义相关度;最后借助改进的优选算法完成关键句子选取。实验结果显示,该方法准确率、召回率和F度量值的平均值分别为75.9%、71.8%和73.8%,与已有同类方法相比,改进后的方法实现了全程无监督且在整体效率上有较大提升,更具应用潜质。