基于两个等级分布的平均随机TBFL方法

运用测试集对程序错误语句定位算法,现在被统称为TBFL(testing based fault localization)方法。目前通行的算法,一般都没有利用测试员、程序员关于测试用例和程序的先验知识,致使这些"资源"白白浪费掉。随机TBFL方法是一类新的TBFL方法,其精神就是在随机理论的框架下,把这些先验知识和实际测试活动结合起来,从而对程序错误语句更好地定位。随机TBFL算法也可以看成是这种类型算法的一般"模式",人们可以从这个一般性的模式里,开发出不同的算法。基于Santelices等人的思想,对随机TBFL算法作了改进。主要是从测试结果里,构造执行矩阵E和功效矩阵F两个工具,通过它们结合测试集和程序先验知识,对程序语句出错可能性引入两个级别的排序,然后对这两个排序进行"平均",得到程序语句出错可能性的平均等级排序,它可以作为程序员改正程序错误的导向。还提出两个有关不同TBFL算法比较标准,就这两个标准,在一些具体实例上,该算法和其他一般方法以及随机TBFL方法对比,效果令人满意。     

等级平均随机TBFL方法

运用测试集对程序错误语句定位的算法,现在被统称为TBFL(testing based fault localization)方法。目前通行的算法一般都没有利用测试员、程序员关于测试用例和程序的先验知识,致使这些"资源"白白浪费掉。文献[12]引入了一类新的随机TBFL方法,其精神就是在随机理论的框架下,把这些先验知识和实际测试活动结合起来,从而对程序错误语句更好地定位。文献[12]提出的算法可以看成是这种类型算法的一般"模式",人们可以根据这个一般性的模式开发出不同的算法。基于文献[13]的思想,对文献[12]中的算法做了改进。主要是根据测试结果,构造执行矩阵E和功效矩阵F两个工具,并结合测试集和程序先验知识,对程序语句出错可能性引入两个级别的排序,然后对这两个排序进行"平均",得到程序语句出错可能性的平均等级排序,它可以作为程序员改正程序错误的导向。还提出两个有关不同TBFL算法的比较标准,根据这两个标准,在一些具体实例上,将所提算法和其他一般方法以及文献[12]中的方法进行了对比,结果显示所提算法的效果令人满意。     

基于定值-引用链的测试用例优先级排序算法

测试用例优先级排序作为一种高效实用的回归测试技术,通常以测试用例的覆盖度作为优先级排序的量化指标,忽略了测试用例的其他测试性能。针对该问题,提出一种基于DU链的测试用例优先级排序算法。该算法 综合考虑 测试用例的DU链覆盖度和回归测试的错误检测能力,对测试用例优先级进行量化。与已有算法相比,该算法基于数据流覆盖,充分利用了测试执行的历史信息和程序模块的耦合信息,在排序过程中动态计算测试用例的优先级量化值。实验结果表明,采用优先级排序算法的测试用例集能在测试过程中以较短的时间发现更多的错误,有效地提高了回归测试的检错效率。     

中文“非多字词错误”自动校对方法研究

针对目前中文文本中的“非多字词错误”自动校对方法的不足,提出了一种模糊分词的“非多字词错误”自动查错和自动校对方法。首先利用精确匹配算法与中文串模糊相似度算法对中文文本进行精确切分和模糊全切分,建立词图;然后利用改进的语言模型对词图进行最短路径求解,得到分词结果,实现“非多字词错误”的自动发现和自动纠正。实验测试集是由2万行领域问答系统日志语料构成,共包含664处“非多字词错误”。实验表明,所提方法能有效发现“非多字词错误”,包括由于汉字替换、缺字、多字引起的“非多字词错误”,该方法的查错召回率达到75.9%,查错精度达到85%。所提方法是一种将查错与纠错融于一体的方法。     

基于改进的N-gram模型和知识库的文本查错算法

针对语音识别引擎识别后文本容易发生散串错误和同音字错误,提出一种基于改进的N-gram模型和专业术语查错知识库的查错算法.采用Witten-Bell平滑算法解决N-gram模型训练过程中数据稀疏问题,并对N-gram模型增加权重分配,增强模型对散串错误的查错率.针对铁路特殊用语规定和同音字错误,构建一种适应关键字的专业术语查错知识库,实现知识库的自动更新.经过实验对比,该算法查错确率为87.9％,相比通用的N-gram查错模型提高52.8百分点.该算法的提出为后续的纠错以及语音识别准确率的提高奠定了基础,并对铁路车务系统语音识别技术的应用具有重要意义.     

基于通信多端口有限状态机的协议互操作性测试生成研究

协议测试是一种保证网络通信协议实现质量的重要技术,互操作性测试是一类常用的协议测试技术．文章提出了一种基于通信多端口有限状态机模型的协议互操作忡测试生成方法．首先采用已有的基于可达性分析的方法生成集中式测试序列;然后采用单一错误模型对其进行系统的错误覆盖分析,为达到更高的错误覆盖度,进一步提出一种增强的测试生成算法;最后讨论了互操作性测试巾的控制观察问题,选择适当的分布式测试架构,并进而生成分布式同步测试序列．实验结果表明：与原有方法相比,该方法可以有效地提高测试集的错误覆盖,并具备一定的可行性和有效性．     

基于多优化目标的软件测试用例约简方法研究

软件测试是软件工程的一个重要组成部分,其目标是能够及时发现软件中的错误,确保软件高质量。测试用例是软件测试的基础,覆盖度较高且精简的测试用例集可以提高测试效率和降低成本。软件测试覆盖标准较多,一个好的测试用例评价指标也存在多种,为了能够在约简测试用例集规模的同时获取较高的测试能力,本文提出了一种基于多优化目标的测试用例集约简算法,该算法旨在根据测试用例需求,构建多优化目标的测试用例模型,使用该模型获取一个最优解的测试用例子集,使用最小化用例集方法最小化测试用例,迭代执行直到测试用例集覆盖所有的测试需求,实验结果表明该算法可以约简测试用例集,获取较高的综合测试效果。     

基于冗余测试用例的最小测试用例集生成方法

提出一种最小测试用例集的生成方法。保留在某个测试标准下冗余,但在其他测试标准下不冗余的测试用例,即在测试用例集简化期间通过有选择性地保留测试用例来生成一个测试用例集。与已有方法相比,该方法能在不影响测试组大小范围的情况下有效提高错误检测效率。     

由需求得到回归测试用例排序技术

为了提高回归测试用例集的测试效率和有效性,提出由需求得到回归测试用例排序技术及其实现算法。由需求得到回归测试用例排序技术,将与软件需求相关的需求描述度、需求实现复杂度、需求稳定度和需求覆盖度等因素应用于测试用例排序,以缺陷检测加权平均百分比作为度量标准。通过实验,比较排序后用例和未排序用例缺陷检测情况,实验结果表明该技术排序后的回归测试用例集,能够尽早地发现更多的软件错误,有效提高回归测试效率,保证软件质量。     

由需求得到回归测试用例排序技术

为了提高回归测试用例集的测试效率和有效性,提出由需求得到回归测试用例排序技术及其实现算法。由需求得到回归测试用例排序技术,将与软件需求相关的需求描述度、需求实现复杂度、需求稳定度和需求覆盖度等因素应用于测试用例排序,以缺陷检测加权平均百分比作为度量标准。通过实验,比较排序后用例和未排序用例缺陷检测情况,实验结果表明该技术排序后的回归测试用例集,能够尽早地发现更多的软件错误,有效提高回归测试效率,保证软件质量。     

用遗传算法的测试用例最小化

回归测试就是验证对程序的修改是否迭到了预期的目的，同时检查修改是否损害了程序原有的正常功能。随着程序新版本的不断推出，测试用例集不断扩大，回归测试成本越来越高。测试用例最小化就是从已有的用例集中，找到一个测试运行代价最小的用例子集用于回归测试，并保持原来的测试覆盖率。本文主要研究用遗传算法解决测试用例最小化问题：基于测试历史数据，设计基因编码并构建初始种群；利用测试覆盖率和测试运行代价设计适应度函数；通过遗传算子完成进化过程并找到最优或近似最优解。最后本文给出了对算法进行实例研究的结果。结果表明，本文提出的用例最小化技术能有效缩减回归测试用例集，大幅度降低回归测试费用。     

测试用例最小化研究

给出了测试用例最小化问题的形式化描述,提出并实现了两个新的用于用例最小化的算法.与现有其他最小化算法不同,这两个算法在考虑了每个用例测试覆盖度的同时,还考虑了用例的测试运行代价,目的是提高最小化效率.最后给出了对这两个算法进行实例研究的实验结果.结果表明,用例最小化技术能有效缩减回归测试用例集的尺寸,大幅度降低回归测试费用,提高最小化效率.     

A test-suite reduction approach to improving fault-localization effectiveness

In order to improve the effectiveness of fault localization, researchers are interested in test-suite reduction to provide suitable test-suite inputs. Different test-suite reduction approaches have been proposed. However, the results are usually not ideal. Reducing the test-suite improperly or excessively can even negatively affect fault-localization effectiveness. In this paper, we propose a two-step test-suite reduction approach to remove the test cases which have little or no effect on fault localization, and improve the distribution evenness of concrete execution paths of test cases. This approach consists of coverage matrix based reduction and path vector based reduction, so it analyzes not only the test cases coverage but also the concrete path information. We design and implement experiments to verify the effect of our approach. The experimental results show that our reduced test-suite can improve fault-localization effectiveness. On average, our approach can reduce the size of a test-suite in 47.87% (for Siemens programs) and 23.03% (for space program). At the same time, on average our approach can improve the fault-localization effectiveness, 2.12 on Siemens programs and 0.13 on space program by Tarantula approach.     

Test-suite reduction and prioritization for modified condition/decision coverage

Software testing is particularly expensive for developers of high-assurance software, such as software that is produced for commercial airborne systems. One reason for this expense is the Federal Aviation Administration's requirement that test suites be modified condition/decision coverage (MC/DC) adequate. Despite its cost, there is evidence that MC/DC is an effective verification technique and can help to uncover safety faults. As the software is modified and new test cases are added to the test suite, the test suite grows and the cost of regression testing increases. To address the test-suite size problem, researchers have investigated the use of test-suite reduction algorithms, which identify a reduced test suite that provides the same coverage of the software according to some criterion as the original test suite, and test-suite prioritization algorithms, which identify an ordering of the test cases in the test suite according to some criteria or goals. Existing test-suite reduction and prioritization techniques, however, may not be effective in reducing or prioritizing MC/DC-adequate test suites because they do not consider the complexity of the criterion. This paper presents new algorithms for test-suite reduction and prioritization that can be tailored effectively for use with MC/DC. The paper also presents the results of empirical studies of these algorithms.     

On the effect of test-suite reduction on automatically generated model-based tests

Model checking techniques can be successfully employed as a test-case generation technique to generate tests from formal models. The number of tests-cases produced, however, is typically large for complex coverage criteria such as MC/DC. Test-suite reduction can provide us with a smaller set of test-cases that preserve the original coverage—often a dramatically smaller set. Nevertheless, one potential drawback with test-suite reduction is that this might affect the quality of the test-suite in terms of fault finding. Previous empirical studies provide conflicting evidence on this issue. To further investigate the problem and determine its effect when testing implementations derived from formal models of software we performed an experiment using a large case example of a Flight Guidance System, generated reduced test-suites for a variety of structural coverage criteria while preserving coverage, and recorded their fault finding effectiveness. Our results indicate that the size of the specification based test-suites can be dramatically reduced and that the fault detection of the reduced test-suites is adversely affected. In this report we describe our experiment, analyze the results, and discuss the implications for testing based on formal specifications. This work has been partially supported by NASA grant NAG-1-224 and NASA contract NCC-01001. We also want to thank the McKnight Foundation for their generous support over the years.

---

     

Connectivity Testing

This paper presents a new approach, connectivity testing, for testing embedded systems. Instead of testing the conformance of a system against its specification, which often turns out to be infeasible, we suggest to test only the composition of the software and the hardware. We assume the software to be correct so only the hardware component may be erroneous. Our framework is based on the notion of a (single fault) fault model, that is a model which formally captures errors in the interface between the hardware and the software. Output and input fault models are considered. An exhaustive test suite for a fault model is a test suite that detects the faults of the model with 100% coverage. We prove the problem of computing a smallest exhaustive test suite to be NP-hard and devise heuristic polynomial time algorithms computing minimal exhaustive test suites. We have carried out experiments with the algorithms implemented using Binary Decision Diagrams. Test generation from specifications containing more than 4.98 × 10¹⁰ states have been carried out.     

On the use of a similarity function for test case selection in the context of model‐based testing

Test case selection in model‐based testing is discussed focusing on the use of a similarity function. Automatically generated test suites usually have redundant test cases. The reason is that test generation algorithms are usually based on structural coverage criteria that are applied exhaustively. These criteria may not be helpful to detect redundant test cases as well as the suites are usually impractical due to the huge number of test cases that can be generated. Both problems are addressed by applying a similarity function. The idea is to keep in the suite the less similar test cases according to a goal that is defined in terms of the intended size of the test suite. The strategy presented is compared with random selection by considering transition‐based and fault‐based coverage. The results show that, in most of the cases, similarity‐based selection can be more effective than random selection when applied to automatically generated test suites. Copyright © 2009 John Wiley & Sons, Ltd.     

一种有效的EEPLA的测试算法

本文提出了一种硬件电路很少，故障覆盖率最高的ＥＥＰＬＡ的测试算法。同其他测试算法相比，该方法可以对每一个交叉点进行编程控制。所有单一的或多重的交叉点故障、线电位固定在“１”（“０”）、桥连故障都可以测试到，疽测试算法简单易行。