CMuJava:一个面向Java程序并发变异体生成系统

并发程序由多个共享存储空间并发执行的流程组成.由于流程之间执行次序的不确定性,使得并发软件系统的测试比较困难.变异测试是一种基于故障的软件测试技术,广泛用于评估测试用例集的充分性和测试技术的有效性.将变异测试应用于并发程序的一个关键问题是,如何高效地生成大量的模拟并发故障的变异体集合.给出了一种并发程序的变异测试框架,...     

使用共享变量分析和约束求解检测安卓应用数据竞争

安卓系统在移动端操作系统始终占据主导地位,在增强用户体验和提高程序性能的同时,其特有的事件驱动模型和多线程模型也造成了并发缺陷.并发程序中,线程调度的不确定性和难以再现性是并发缺陷检测困难的原因.现有技术主要在动态生成执行路径的基础上进行发生序（happens-before）分析,进而检测安卓应用的并发缺陷,但仍然存在低覆盖率、误报、漏报等问题.结合共享变量分析和约束求解方法实现了安卓应用数据竞争的检测,并实现了检测工具RaceDetector.该工具首先根据安卓系统的特性和数据竞争的定义,通过静态分析抽取相关信息,并进一步使用安卓共享变量分析来提高准确性和性能,继而进行可疑数据竞争分析,得出可疑的数据竞争集合;接着根据每一个可疑的数据竞争候选者,通过约束求解的方法在所有事件调度和线程调度解空间下识别发生序关系,并最终检测出真正的数据竞争.实验部分是从Google Play等来源收集了15个流行的应用APK文件作为数据集,RaceDetector平均报告了340个数据竞争,误报率为13%（44/340）.与现有工具EventRacer（默认产生300随机事件触发应用执行,平均检测2个有害数据竞争）相比,RaceDetector能够解析全部源码,覆盖了所有线程调度和事件调度,平均检测出15个有害数据竞争.     

并发程序设计概念和记法

近十年并发程序设计一直议论很多。本文说明了它的主要概念,描述了编写并发程序的一些较重要的语言记法。讨论了进程、通信和同步的作用。综述了表示并发执行和说明进程交互作用的语言记法,描述了-些基于共享变量和基于消息传递的同步原语。最后,总结和比较了三类流行的并发程序设计语言。     

一种基于发生序和锁集的BPEL数据竞争静态检测方法

BPEL利用flow和link提供了并发和同步的机制,而Isolated Scope则提供了并发情况下对共享变量访问的控制,同时BPEL还引入了死路删除等一些新的特性。对BPEL流程进行了建模,把BPEL流程转化为BCFG图,提出了一种结合发生序和锁集的静态检测BPEL流程数据竞争的方法。该方法利用向量时钟计算BPEL基本块的发生序关系,判断BPEL基本块是否可并发执行,然后根据BPEL基本块是否有锁保护以及对共享变量的访问情况,来判断BPEL流程是否存在数据竞争。锁集的引入提高了数据竞争判断的准确度,另外该方法还引入了对共享变量访问事件冗余度的分析,减少了算法的开销。     

一种并发程序可测试性分析框架

软件可测试性是对测试软件难易程度的预测，在测试、度量等许多领域中得到了广泛应用．由于并发程序执行的不确定性，其可测试性分析尚有很多难点有待解决．该文提出了一种并发程序可测试性分析框架．在充分分析程序内部数据流、控制流以及并发和同步对数据流和控制流影响的基础上，从单个并发单元、并发因素、共享变量因素及通信关系4个方面对并发程序的可测试性进行了分析，为综合度量并发程序的可测试性提供了依据．     

面向并发程序中锁机制的智能化推荐方法

软件开发人员在并发编程中面临着各种Java锁的选择。针对如何选择合适的锁机制进而提高程序性能的问题,提出了一种帮助并发程序开发人员选择锁机制的推荐方法LockRec。首先,采用程序静态分析技术,对并发程序中锁机制的使用进行分析并确定影响程序性能的程序特征属性;然后,使用改进的随机森林算法构建锁机制推荐模型,以帮助开发人员在同步锁、可重入锁、读写锁、邮戳锁这四种锁之中进行选择。分别选取了四种现有的机器学习数据集对LockRec进行了实验,所提方法的推荐准确率均值可达95.1%;此外使用真实并发程序对LockRec的推荐结果进行分析。实验结果表明LockRec可以有效提高并发程序的执行效率。     

Ada并发软件的图形化设计方法研究

研究的目标：为Ada并发软件的设计提供一种图形化的方法和支撑工具,以便用图形表达并发软件的设计,并生成并发程序的框架（并发程序单元的划分和它们之间的通信）。这样做的好处在于提高软件的生产率,改善软件质量。在提出用于并发软件理解的会合次序图的基础上,给出了并发设计语言CONDL的语法、语义描述和图形化表示（泳道）,并简单介绍了所研制的一个工具CONDLAS（生成Ada代码框架）。     

多核处理器YHFT-QDSP的调试系统

YHFT-QDSP是一款多核处理器。为满足其并发调试和实时调试的需要,在原有单核调试系统的基础上设计实现了多核同步调试系统和片上实时追踪系统（片上Trace）。多核同步调试提供了命令广播和断点同步触发等并发程序协同调试的功能;片上Trace通过专用硬件记录程序执行路径和数据读写等信息实现非入侵实时调试。本文从原理、结构和
软硬件实现等方面介绍了该调试系统。     

一种链状数据结构细粒度自动加锁方法

细粒度锁在并行编程与并发软件设计中起着重要的作用.然而,细粒度锁对程序员具有较高的要求,通常在设计细粒度锁并发程序时会带来算法复杂,编程困难,程序易出错等问题.提出一种链状数据结构的细粒度加锁方法,并实现自动转换含有形状和共享标注的程序为细粒度锁代码的翻译器,为了使生成的代码具有无死锁,引入了一致性加锁协议,实验结果表明,基于本文方法能够自动为链状数据结构操作添加细粒度锁,生成的代码具有较高的并发性.     

Java并发类库包的研究与应用

Java在其JDK5.0版本中推出了Concurrent并发类库包,该包为程序员提供了众多开发并发程序的新特征,如同步对象,并发集合,执行程序等,为并发程序的设计提供了更方便、安全的途径.本文在对并发类库包进行了分析与研究的基础上,运用并发包锁机制与原子操作实现了模拟电梯控制的仿真系统.     

Adaptive evolutionary programming based on reinforcement learning

This paper studies evolutionary programming and adopts reinforcement learning theory to learn individual mutation operators. A novel algorithm named RLEP (Evolutionary Programming based on Reinforcement Learning) is proposed. In this algorithm, each individual learns its optimal mutation operator based on the immediate and delayed performance of mutation operators. Mutation operator selection is mapped into a reinforcement learning problem. Reinforcement learning methods are used to learn optimal policies by maximizing the accumulated rewards. According to the calculated Q function value of each candidate mutation operator, an optimal mutation operator can be selected to maximize the learned Q function value. Four different mutation operators have been employed as the basic candidate operators in RLEP and one is selected for each individual in different generations. Our simulation shows the performance of RLEP is the same as or better than the best of the four basic mutation operators.     

改进进化策略及其在神经网络训练中的应用

进化策略是一类策略参数自适应进化算法。文章提出了一种改进进化策略(MES),MES采用基于个体排序的随机自适应Gaussian-Cauchy混合变异策略,将Gaussian和Cauchy变异算子结合起来以达到全局探索和局部搜索之间的动态平衡。此外,MES还使用重组算子以进一步提高算法的性能。将该算法用于多层前向神经网络训练,数值仿真结果显示了该算法的有效性。     

Combining weak and strong mutation for a noninterpretive Java mutation system

Because of the computationally expensive cost of mutation testing, automated system support is indispensable for conducting mutation testing. Mutation systems can be classified into interpretive and noninterpretive, but recent systems are noninterpretive. Weak mutation is a well‐known cost reduction method of mutation testing, but it is not directly applicable to noninterpretive mutation systems. To address the problem and take advantage of the efficiency of weak mutation, this paper presents a combined weak and strong mutation for noninterpretive Java mutation systems. The new term ‘serialmutant’ is defined as a specialized program to conduct weak mutation against all mutants in an execution and report only weakly killed mutants as strong mutation candidates. Then strong mutation is conducted only for those reported mutants. The paper also describes an implementation based on a previous Java mutation tool, MuJava. Method‐level mutation operators for Java are also redesigned. Experimental results show that the proposed approach efficiently improves the mutation cost in a noninterpretive mutation system. Copyright © 2012 John Wiley & Sons, Ltd.     

Adaptive chaos clonal evolutionary programming algorithm

1 Introduction Chaos is the essential character of a nonlinear system, and also has a series of its own properties such as randomicity,ergodicity and regulation, etc. With the profound influ-ence[1] to the development of the science, the chaos has been introduced into the evolu-tionary computation to construct new intelligent algorithms for providing some novel methods and offering some new fields[2,3] such as to overcome prematurity during the search process. Although these algorithms have hi…     

Interface Mutation Test Adequacy Criterion: An Empirical Evaluation

An experiment was conducted to evaluate an inter-procedural test adequacy criterion named Interface Mutation. Program SPACE, developed for the European Space Agency (ESA), was used in this experiment. The development record available for this program was used to find the faults uncovered during its development. Using this information the test process was reproduced starting with a version of SPACE containing several faults and then applying Interface Mutation. Thus we could evaluate the fault revealing effectiveness of Interface Mutation. Results from the experiment suggest that (a) the application of Interface Mutation favors the selection of fault revealing test cases when they exist and (b) Interface Mutation tends to select fault revealing test cases more efficiently than in the case where random selection is used.     

一种基于变异分析的BPEL程序故障定位技术

不同于传统C,C++或Java程序,BPEL(Business Process Execution Language)程序由一组活动及其之间的交互组成,同时引入了并发、序列化、XML表示等新特征,这些新特点使得定位BPEL程序的故障具有一定的挑战性.针对现有故障定位技术在有效性方面的不足,提出一种基于变异分析的BPEL...     

Selecting mutation operators with a multiobjective approach

The mutation score is an important measure to evaluate the quality of the test cases. It is obtained by executing a lot of mutant programs generated by a set of operators. A common problem, however, is that some operators can generate unnecessary and redundant mutants. Because of this, different strategies were proposed to find a set of operators that generates a reduced number of mutants without decreasing the mutation score. However, the operator selection, in practice, may include real constraints and is dependent on diverse factors besides the number of mutants and score, such as: number of test data, execution time, number of revealed faults, number of equivalent mutants, etc. In fact this is a multi-objective problem, which does not have a single solution. Different set of operators exist for multiple objectives to be satisfied, and some restrictions can be used to choose among the existing sets. To make this choice possible, in this paper, we introduce a multi-objective strategy. We investigate three multi-objective algorithms and introduce a procedure to establish a set of operators to prioritize mutation score. Better results are obtained in comparison with traditional strategies.     

A partitioned portfolio insurance strategy by a relational genetic algorithm

This paper proposes a new portfolio insurance (PI) strategy named partitioned portfolio insurance (PPI) strategy and a new relation-based genetic algorithm named relational genetic algorithm (RGA) to optimize the proposed PPI strategy. Our PPI strategy extends the traditional PI strategy to become a more aggressive one. In our PPI strategy, we attempt to correctly partition the portfolio into several similar sub-portfolios and then insure the sub-portfolios individually. It not only avoids the downside risk, but also further explores the upside profit successfully. In addition, our RGA which adopts a relational encoding and has a set of problem-independent operators is designed to solve the induced portfolio partitioning problem. The relational encoding eliminates the redundancy of previous GA representations for partitioning problems and improves the performance of genetic search. The problem-independent operators we redesigned manipulate the genes without requiring specific heuristics in the process of evolution. Moreover, our RGA works without requiring a preset number of subsets in advance. Experiments for developing optimized PPI strategies by RGA are performed. Experimental results show that our optimized PPI strategies are significantly better than the traditional PI strategy and our RGA works well for solving the portfolio partitioning problem.     

Ensemble strategies with adaptive evolutionary programming

Mutation operators such as Gaussian, Lévy and Cauchy have been used with evolutionary programming (EP). According to the no free lunch theorem, it is impossible for EP with a single mutation operator to outperform always. For example, Classical EP (CEP) with Gaussian mutation is better at searching in a local neighborhood while the Fast EP (FEP) with the Cauchy mutation performs better over a larger neighborhood. Motivated by these observations, we propose an ensemble approach where each mutation operator has its associated population and every population benefits from every function call. This approach enables us to benefit from different mutation operators with different parameter values whenever they are effective during different stages of the search process. In addition, the recently proposed Adaptive EP (AEP) using Gaussian (ACEP) and Cauchy (AFEP) mutations is also evaluated. In the AEP, the strategy parameter values are adapted based on the search performance in the previous few generations. The performance of ensemble is compared with a mixed mutation strategy, which integrates several mutation operators into a single algorithm as well as against the AEP with a single mutation operator. Improved performance of the ensemble over the single mutation-based algorithms and mixed mutation algorithm is verified using statistical tests.     

针对JavaScript浏览器兼容性的变异测试方法

针对JavaScript浏览器兼容性问题缺乏有效的测试方法的问题,基于变异测试技术,对Web应用程序中的JavaScript语言在主流浏览器中的兼容性进行了分析,设计了18个针对浏览器兼容性错误的变异算子并开发了自动化的测试工具Compatibility Mutator。该程序使用抽象语法树（AST）分析JavaScript语法,使用Selenium WebDriver自动调用多个浏览器核心并行执行变异测试。通过对7个广泛使用的JavaScript框架的实验,验证了此方法对每一个框架都能够生成一定数量的变异体,其中对jQuery和YUI框架的变异测试的变异得分分别为43.06%和7.69%,表明了所设计的变异算子能够触发浏览器兼容性方面的错误,并且能够评估测试用例集的完备性。