基于并发程序数据竞争故障的变异策略

针对并发程序变异测试中并发变异算子触发数据竞争故障能力较低的问题,提出了基于数据竞争故障的变异策略。从并发变异算子设计的角度给出了面向锁对象的变异策略（LMS）和面向共享变量的变异策略（SMS）,设计了重置同步锁（SLRO）和移出共享变量操作（MSVO）两个并发变异算子。从变异点选取的角度给出了一种同步关系对变异点选取策略（SMPSS）。在12个Java类库并发程序上,应用SLRO和MSVO算子针对SMPSS选取出的变异点植入故障,生成变异体,并使用JPF检测工具,检测生成的变异体引发数据竞争故障的能力。实验结果表明,新设计的SLRO和MSVO变异算子对12个被测程序分别生成了121和122个有效变异体,变异算子的有效性分别为95.28%和99.19%。由此可知,新设计的并发变异算子能有效触发数据竞争故障。     

一种基于依赖分析的并发程序潜在死锁检测算法

死锁是并发程序特有的一种运行时错误,由于并发程序在执行时的不确定性,死锁的检测和定位是非常困难的.本文提出了一种基于依赖分析的并发程序潜在死锁检测算法,该算法是一种静态分析算法,能检测并发程序中是否存在潜在死锁,并能定位死锁发生时各线程可能被挂起的语句节点.本文给出了算法的形式化定义和时间复杂度分析,实验测试结果表明算法是正确且有效的.     

基于确定性重演的并发程序调试

并发程序执行的不确定性导致了程序错误的不可再现性,后续的执行无法再现前次执行的错误,这使得以反复执行程序,重复再现故障为核心的循环调试方法变得不再可用。本文提出了一种基于确定性重演的并发程序的调试方法,确定化并发程序的执行轨迹,重现程序初始运行的错误状态。     

并发计算重复问题与控制方法

数据竞争问题是并发程序开发与测试难题,发现数据竞争可能导致计算重复,重复会导致系统性能下降.从实例出发定义了并发计算重复问题(concurrent computation redundancy problem,简称CCRP),给出了相关性能指标和判断方法,设计了通用并发重复控制机制.并发程序一般都可以基于生产者-消费者模型进行CCRP分析.以带数据源的生产者-消费者为例详细分析了CCRP,给出了单条件、条件交叉两种重复控制算法,算法具有不同的适用范围,都可以作为固定模式来解决CCRP,基于Petri网作了相关性质的证明与仿真.并发程序实验结果说明了并发重复控制的必要性和有效性,比较了两种算法的差异.该研究对于数据竞争检测、并发程序设计具有参考价值.     

一种基于虚拟机技术的并发程序实现方法

基于一种虚拟机设计思想,用C语言实现了一个虚拟机平台,通过在虚拟机中加入管理程序以实现对用户作业的并发控制。该方法提供了利用串行程序设计语言进行并发程序开发的一种实现方法。通过实验证明不通过机器低层及硬件的手段也能有效地在顺序执行的平台上实现并发程序。     

基于上下文定界的Fork/Join并行性的并发程序可达性分析

随着多核技术日益发展,并发程序通过引入Fork/Join并行性,将任务分解为更细粒度的子任务并行执行,从而充分利用多核处理器提供的计算性能。并发执行线程之间的交错可能产生隐匿的程序设计错误,因此有必要对此类并发程序的正确性进行分析。上下文定界分析方法是一种检测并发程序中隐匿错误的高效方法,计算线程有限次上下文切换内的可达状态,确定错误状态是否可达。针对Fork/Join并行性的并发程序的可达性分析思想如下:首先,动态并发程序被建模为可模拟线程Fork/Join操作的动态并发下推系统P;然后从P中提取模拟其k-定界执行的并发下推系统Pk。现有的上下文定界可达算法可解决提取后的并发下推系统的k-定界可达性问题。     

获取访存依赖:并发程序动态分析基础技术综述

并发错误难触发、难调试、难检测.为应对这一挑战,已有动态程序分析技术通过观测或控制并发程序执行实现其质量保障.由于并发程序不确定性主要来自共享内存,实现其动态分析的基本问题即是获取线程访问共享内存的顺序,即获取访存依赖.提出访存依赖获取技术的综述框架,包含四个评价指标（即时性、准确性、高效性、简化性）、两种方法（在线追踪、离线合成）、两类应用（轨迹分析、并发控制）.通过对已有技术的总结和分析框架中的空白,对未来可能的研究方向予以展望.     

基于偏序约简程序可达图的并发程序切片方法

并发程序切片是一种重要的并发程序分析手段.基于程序可达图可构造以程序状态和语句二元组为节点的、依赖关系具有可传递性的并发程序依赖图,解决依赖关系的不可传递性问题,提高切片精度.程序可达图通过交织执行模拟并发活动,分析代价较高.偏序约简是一种十分有效的并发系统状态空间约简技术,约简的并发系统状态空间包含所有的并发程序执行代表.为提高效率,该文将偏序约简技术扩展到程序可达图的约简中,在偏序约简理论的基础上,证明了基于未约简和约简的并发程序可达图构造的并发程序依赖图在进行切片计算时是等价的.实验结果表明,采用偏序约简技术使基于程序可达图的并发程序切片方法在保证切片精度不受损失的前提下显著提高切片效率.与其它高精度切片方法相比,基于约简程序可达图的切片方法的精度更高,在大多数情况下,切片效率也有一定提高.     

基于嵌入式平台的并发虚拟机研究

并发程序对提高应用系统的处理能力具有重要作用,基于嵌入式平台的并发程序开发尚无统一的工具支持.本文提出了一种基于嵌入式平台的并发虚拟机(CVM)设计思想,并采用标准C实现了一个CVM模型.研究表明,它可以支持嵌入式平台中的并发程序,实现了嵌入式平台中并发程序的平台无关性和可移植性.     

基于六边形的自适应层次网格及其应用于点在球面多边形内的判断

软件测试是一种广泛使用的软件质量保证手段. 变异测试是一种基于故障的软件测试方法, 广泛用于评估测试用例集的充分性与软件测试技术的有效性. 数量庞大的变异体导致变异测试的成本非常高. 提出一种数据流分析指导的变异体精简方法(DFSampling), 设计了启发式规则, 基于这些规则对随机选择技术与基于路径感知的变异体精简技术(PAMR)进行了改进. 采用经验研究的方式评估了DFSampling的有效性, 比较了DFSampling与随机选择技术、PAMR技术的有效性, 实验结果表明DFSampling是一种有效的变异体精简策略, 提高了变异测试的效率.     

MuJava: an automated class mutation system

Several module and class testing techniques have been applied to object‐oriented (OO) programs, but researchers have only recently begun developing test criteria that evaluate the use of key OO features such as inheritance, polymorphism, and encapsulation. Mutation testing is a powerful testing technique for generating software tests and evaluating the quality of software. However, the cost of mutation testing has traditionally been so high that it cannot be applied without full automated tool support. This paper presents a method to reduce the execution cost of mutation testing for OO programs by using two key technologies, mutant schemata generation (MSG) and bytecode translation. This method adapts the existing MSG method for mutants that change the program behaviour and uses bytecode translation for mutants that change the program structure. A key advantage is in performance: only two compilations are required and both the compilation and execution time for each is greatly reduced. A mutation tool based on the MSG/bytecode translation method has been built and used to measure the speedup over the separate compilation approach. Experimental results show that the MSG/bytecode translation method is about five times faster than separate compilation. Copyright © 2004 John Wiley & Sons, Ltd.     

基于SOM神经网络的二阶变异体约简方法

二阶变异测试通过向源程序中人工注入两个缺陷来模拟程序实际的复杂缺陷,在软件测试中具有重要意义.但由一阶变异体组合形成二阶变异体后数量会急剧增长,极大地增加了程序的执行开销.为了减少二阶变异体数量,降低程序的执行开销,提出一种基于SOM神经网络的二阶变异体约简方法.该方法首先采用较为全面的二阶变异体错误组合策略,对一阶变异体组合形成二阶变异体;然后,根据二阶变异体执行过程中的中间值相似性,进行基于SOM神经网络的变异体聚类.使用经典的基准程序和开源程序进行了方法的验证,实验结果表明,一方面,使用错误覆盖更为全面的组合策略能够充分模拟程序的复杂缺陷,聚类约简后,二阶变异体的个数在极大减少的同时,二阶变异充分度和一阶变异充分度更加接近,但是因为执行的二阶变异体数目明显降低,从而使得运行聚类后的二阶变异体时间开销明显比执行全部二阶变异体降低;另一方面,实验过程发现了有利于增加测试组件的隐藏二阶变异体.     

Efficiency of mutation operators and selective mutation strategies: an empirical study

This paper investigates the mutation scores achieved by individual operators of the Mothra mutation system and their associated costs in order to determine the most efficient operators. The cost of mutation analysis includes both test set generation and equivalent mutant detection. The score and cost information is then used as a heuristic for choosing a subset of the operators for use in efficient selective mutation testing. Experiments were performed using a sample of 11 programs and a number of test sets for each program. The results show that the use of efficient operators can provide significant efficiency gains for selective mutation if the acceptable mutation score is not very close to one. When mutation scores very close to one are required, a randomly selected proportion of the mutants provides a more efficient strategy than a subset of efficient operators. Copyright © 1999 John Wiley & Sons, Ltd.     

基于统计占优分析的变异测试

为数众多的变异体产生的高昂测试代价严重影响了变异测试技术在实际程序中的应用.为了大幅度减少弱变异测试中变异体的数量,提出基于统计占优分析的变异体约简方法.该方法首先利用变异前后的语句构造变异分支,并将所有变异分支集成到原程序中,形成新的被测程序;然后,通过统计测试用例对各个变异分支的覆盖信息,确定变异分支之间的占优关系;最后得到非被占优分支集,其对应的变异体就是约简后的变异体.将该方法用于8个程序的测试,结果表明:该方法能够约简平均90%的变异体,从而显著提高了变异测试的效率.     

等价变异体的弱变异分析方法

变异测试通过执行变异体评价给定测试用例集的质量。然而,一定比例的等价变异体,不仅增加变异测试成本,也影响测试用例评价结果的准确性。鉴于此,提出基于弱变异分析的方法,以有效检测等价变异体。所提方法将变异前后语句组合为条件语句,以反映杀死变异体的必要性条件,并构造变异分支;将所有变异分支集成到原程序中;通过分析变异分支的可满足性,判定等价变异体。将所提方法用于6个程序的实验,结果表明,所提方法能够有效检测等价变异体。     

变异测试:原理、优化和应用

变异测试是一种基于缺陷的软件测试技术,在近四十年得到国内外学者的广泛关注,并取得了一些研究成果。对已有的研究工作进行总结,将其分为变异测试原理、优化和应用三个模块。其中在变异测试原理模块中,给出变异测试的基本假设,对变异测试分析流程进行介绍,并对其中的重要概念依次给出定义,从静态检测和动态检测两个角度对等价变异体检测技术进行总结。在变异测试优化模块中,从变异体选择优化和变异体执行优化两个角度对已有研究工作进行总结。在变异测试应用模块中,选择了测试用例集充分性评估、测试用例生成和回归测试三个应用领域,对研究工作进行分类总结。最后对变异测试的未来研究方向进行了展望。     

Automatically detecting equivalent mutants and infeasible paths

Mutation testing is a technique for testing software units that has great potential for improving the quality of testing, and thereby increasing the ability to assure the high reliability of critical software. It will be shown that recent advances in mutation research have brought a practical mutation testing system closer to reality. One recent advance is a partial solution to the problem of automatically detecting equivalent mutant programs. Equivalent mutants are currently detected by hand, which makes it very expensive and time-consuming. The problem of detecting equivalent mutants is a specific instance of a more general problem, commonly called the feasible path problem, which says that for certain structural testing criteria some of the test requirements are infeasible in the sense that the semantics of the program imply that no test case satisfies the test requirements. Equivalent mutants, unreachable statements in path testing techniques, and infeasible DU-pairs in data flow testing are all instances of the feasible path problem. This paper presents a technique that uses mathematical constraints, originally developed for test data generation, to detect some equivalent mutants and infeasible paths automatically. © 1997 John Wiley & Sons, Ltd.     

并发软件适应性随机测试方法

测试用例选择是软件测试中的关键问题之一.目前,测试用例选择在并发软件测试方面鲜有涉及.以多线程并发程序为研究对象,提出面向并发软件的适应性随机测试方法,通过优化测试用例选择,来提高并发软件测试的效率和错误发现能力.根据实验结果,我们提出的并发软件适应性随机测试方法比随机测试方法的测试效率更高,错误发现能力也更强.     

Parallel mutation testing

Despite the existing techniques to reduce the costs of mutation analysis, the computational cost to apply mutation testing with large applications can be very high. One effective technique to improve the efficiency of mutation without losing effectiveness is parallel execution, where mutants and tests are executed in parallel processors, reducing the total time needed to perform mutation analysis. This paper presents a study of this technique adapted to current technologies. Five algorithms to execute mutants in parallel are analysed with three studies that use different network configurations and different number of processors with diverse characteristics. The experiments are performed with Bacterio ^P, a tool that is also presented. Unlike previous studies about parallel mutant execution, which date from the mid‐1990s, in the studies in this paper, the communication time in parallel systems no longer acts as a bottleneck. Thus, dynamic strategies, which require more communication, combined with other mutant cost reduction techniques, are the best strategies to run mutants in parallel.Copyright © 2012 John Wiley & Sons, Ltd.