参数配对及n-way组合覆盖算法研究

组合测试是软件测试数据生成研究的一个重要领域,其中参数配对组合测试的应用最为广泛.对常用的参数配对组合覆盖方法进行了综述分析.目前主流的配对覆盖算法AETG和IPO所存在的主要问题是在确定水平取值时,具有盲目性和随机性,从而难以控制测试用例的规模.为此提出了改进的AETG算法和IPO算法,改进算法通过对参数进行预处理以及综合考虑各因素的水平组合等手段,对测试用例的规模进行控制,采用更加完备的方法尽早确定水平取值.为验证新算法的有效性,进行了仿真实验和实际测试,结果表明,改进算法所生成的测试用例数量要少于原算法,测试用例约减效果更为明显;测试用例数与配对数之间、测试用例数与因素水平数之间存在着某些规律性的联系,分析得出了一系列相关的结论.在配对覆盖的基础上,提出了遗传算法与AETG算法相结合的n-way组合覆盖算法,证明了其时间复杂性较已有算法得到了改善.     

A practical model‐based statistical approach for generating functional test cases: application in the automotive industry

With the growing complexity of industrial software applications, industrials are looking for efficient and practical methods to validate the software. This paper develops a model‐based statistical testing approach that automatically generates online and offline test cases for embedded software. It discusses an integrated framework that combines solutions for three major software testing research questions: (i) how to select test inputs; (ii) how to predict the expected results of a test; and (iii) when to stop testing software. The automatic selection of test inputs is based on a stochastic test model that accounts for the main particularity of embedded software: time sensitivity. Software test practitioners may design one or more test models when they generate random, user‐oriented, or fault‐oriented test inputs. A formal framework integrating existing and appropriate specification techniques was developed for the design of automated test oracles (executable software specifications) and the formal measurement of functional coverage. The decision to stop testing software is based on both test coverage objectives and cost constraints. This approach was tested on two representative case studies from the automotive industry. The experiment was performed at unit testing level in a simulated environment on a host personal computer (automatic test execution). The two software functionalities tested had previously been unit tested and validated using the test design approach conventionally used in the industry. Applying the proposed model‐based statistical testing approach to these two case studies, we obtained significant improvements in performing functional unit testing in a real and complex industrial context: more bugs were detected earlier and in a shorter time. Copyright © 2012 John Wiley & Sons, Ltd.     

A threat model‐based approach to security testing

Software security issues have been a major concern in the cyberspace community, so a great deal of research on security testing has been performed, and various security testing techniques have been developed. Threat modeling provides a systematic way to identify threats that might compromise security, and it has been a well‐accepted practice by the industry, but test case generation from threat models has not been addressed yet. Thus, in this paper, we propose a threat model‐based security testing approach that automatically generates security test sequences from threat trees and transforms them into executable tests. The security testing approach we consider consists of three activities in large: building threat models with threat trees; generating security test sequences from threat trees; and creating executable test cases by considering valid and invalid inputs. To support our approach, we implemented security test generation techniques, and we also conducted an empirical study to assess the effectiveness of our approach. The results of our study show that our threat tree‐based approach is effective in exposing vulnerabilities. Copyright © 2012 John Wiley & Sons, Ltd.     

基于解空间树的组合测试数据生成

在组合覆盖测试模型的基础上提出：将所有的可用测试数据表示为一棵解空间树,利用回溯法对解空间树进行路径搜索来生成测试数据,然后使用贪心算法补充生成测试数据,以满足两两组合覆盖标准.并且实现了基于该方法的测试数据生成工具,所生成的测试数据集与同类工具相比具有一定的特点和优势.     

关于两两测试的研究

在软件开发过程中软件测试的成本是很高的。但是，在许多情况下两两测试可用于减少测试的成本，并对于许多软件系统在实践中证明是实用和有效的。它要求对于系统的每一对输入参数，这两个参数有效值的每一个组合至少要被一个测试用例覆盖。介绍了两两测试的概念以及生成测试用例的两个算法。最后，对应用两两测试时应注意的一些问题进行了讨论．两两测试的许多思想可以扩展到t路测试．     

软件回归测试中的自动测试生成方法

软件回归测试一般使用现有的测试用例集进行测试,如何有效利用这些用例成为回归测试的关键。研究自动对现有测试用例集的扩展,包括自动改变测试用例的执行顺序、自动进行测试用例数目的增减等,提出基于现有测试用例随机生成新的测试用例集的方法。实验证明,该方法生成的测试文件能在原有环境下成功执行,能实现自动测试范围的扩大或缩小,以及测试时间的增加或减少,为软件回归测试提供了有用的自动化工具。     

基于两两覆盖准则的遗传算法测试用例生成

软件参数的组合测试是发现参数组合问题的重要方法,但是参数组合测试面临着组合爆炸问题,成对测试可以有效降低测试成本。提出了一种基于遗传算法的成对测试生成方法,该方法用于选择当前局部优化覆盖的测试用例,在此基础上构建满足成对测试基准的测试用例套,结果表明该方法能在不降低测试覆盖精度的情况下有效降低了测试用例数量。     

The AETG system: an approach to testing based on combinatorialdesign

This paper describes a new approach to testing that uses combinatorial designs to generate tests that cover the pairwise, triple, or n-way combinations of a system's test parameters. These are the parameters that determine the system's test scenarios. Examples are system configuration parameters, user inputs and other external events. We implemented this new method in the AETG system. The AETG system uses new combinatorial algorithms to generate test sets that cover all valid n-way parameter combinations. The size of an AETG test set grows logarithmically in the number of test parameters. This allows testers to define test models with dozens of parameters. The AETG system is used in a variety of applications for unit, system, and interoperability testing. It has generated both high-level test plans and detailed test cases. In several applications, it greatly reduced the cost of test plan development     

Simulation-based Testing of Communication Protocols for Dependable Embedded Systems

We present a novel approach to testing fault-tolerant and real-time protocol implementations. Cesium, our testing environment, executes the protocols in a centralized simulator of the distributed system. It simulates the occurrence of inputs and the failure scenarios the protocols are designed to tolerate, while automatically verifying that the required safety and timeliness properties hold at all times during test experiments. Within this framework, the human tester can define failure operations that simulate every failure class studied in the literature. We apply our approach to two fault-tolerant protocols typical in embedded systems. The results show that Cesium can pinpoint implementation errors that would be very difficult to identify in a real system, and can also compute accurate performance predictions that would be problematic to measure in the real embedded platform without ad hoc hardware instrumentation.     

Manual test case derivation from UML activity diagrams and state machines: A controlled experiment

ContextIt is a difficult and challenging task to fully automatize model-based testing because this demands complete and unambiguous system models as input. Therefore, in practice, test cases, especially on the system level, are still derived manually from behavioral models like UML activity diagrams or state machines. But this kind of manual test case derivation is error-prone and knowing these errors makes it possible to provide guidelines to reduce them.ObjectiveThe objective of the study presented in this paper therefore is to examine which errors are possible and actually made when manually deriving test cases from UML activity diagrams or state machines and whether there are differences between these diagram types.MethodWe investigate the errors made when deriving test cases manually in a controlled student experiment. The experiment was performed and internally replicated with overall 84 participants divided into three groups at two institutions.ResultsAs a result of our experiment, we provide a taxonomy of errors made and their frequencies. In addition, our experiment provides evidence that activity diagrams have a higher perceived comprehensibility but also a higher error-proneness than state machines with regard to manual test case derivation. This information helps to develop guidelines for manual test case derivation from UML activity diagrams and state machines.ConclusionMost errors observed were due to missing test steps, conditions or results, or content was written into the wrong field. As activity diagrams have a higher perceived comprehensibility, but also more error-prone than state machines, both diagram types are useful for manual test case derivation. Their application depends on the context and should be complemented with clear rules on how to derive test cases.     

一种改进的两两组合测试用例生成方法

本文针对多因素二水平系统提出:将所有的测试数据表示为一棵二叉解空间树,用回溯法对二叉解空间树进行路径搜索来生成测试用例,然后使用贪心算法生成补充的测试用例,以满足两两组合覆盖标准。使用这种方法生成的测试数据集具有很高的覆盖率。     

Robustness testing for software components

Component-based development allows one to build software from existing components and promises to improve software reuse and reduce costs. For critical applications, the user of a component must ensure that it fits the requirements of the application. To achieve this, testing is a well-suited means when the source code of the components is not available. Robustness testing is a testing methodology to detect the vulnerabilities of a component under unexpected inputs or in a stressful environment. As components may fail differently in different states, we use a state machine based approach to robustness testing. First, a set of paths is generated to cover transitions of the state machine, and it is used by the test cases to bring the component into a specific control state. Second, method calls with invalid inputs are fed to the component in different states to test the robustness. By traversing the paths, the test cases cover more states and transitions compared to stateless API testing. We apply our approach to several components, including open source software, and compare our results with existing approaches.     

Formal firewall conformance testing: an application of test and proof techniques

Firewalls are an important means to secure critical ICT infrastructures. As configurable off‐the‐shelf products, the effectiveness of a firewall crucially depends on both the correctness of the implementation itself as well as the correct configuration. While testing the implementation can be done once by the manufacturer, the configuration needs to be tested for each application individually. This is particularly challenging as the configuration, implementing a firewall policy, is inherently complex, hard to understand, administrated by different stakeholders and thus difficult to validate. This paper presents a formal model of both stateless and stateful firewalls (packet filters), including NAT , to which a specification‐based conformance test case generation approach is applied. Furthermore, a verified optimisation technique for this approach is presented: starting from a formal model for stateless firewalls, a collection of semantics‐preserving policy transformation rules and an algorithm that optimizes the specification with respect of the number of test cases required for path coverage of the model are derived. We extend an existing approach that integrates verification and testing, that is, tests and proofs to support conformance testing of network policies. The presented approach is supported by a test framework that allows to test actual firewalls using the test cases generated on the basis of the formal model. Finally, a report on several larger case studies is presented. Copyright © 2014 John Wiley & Sons, Ltd.     

SimFuzz: Test case similarity directed deep fuzzing

Fuzzing is widely used to detect software vulnerabilities. Blackbox fuzzing does not require program source code. It mutates well-formed inputs to produce new ones. However, these new inputs usually do not exercise deep program semantics since the possibility that they can satisfy the conditions of a deep program state is low. As a result, blackbox fuzzing is often limited to identify vulnerabilities in input validation components of a program. Domain knowledge such as input specifications can be used to mitigate these limitations. However, it is often expensive to obtain such knowledge in practice. Whitebox fuzzing employs heavy analysis techniques, i.e., dynamic symbolic execution, to systematically generate test inputs and explore as many paths as possible. It is powerful to explore new program branches so as to identify more vulnerabilities. However, it has fundamental challenges such as unsolvable constraints and is difficult to scale to large programs due to path explosion. This paper proposes a novel fuzzing approach that aims to produce test inputs to explore deep program semantics effectively and efficiently. The fuzzing process comprises two stages. At the first stage, a traditional blackbox fuzzing approach is applied for test data generation. This process is guided by a novel test case similarity metric. At the second stage, a subset of the test inputs generated at the first stage is selected based on the test case similarity metric. Then, combination testing is applied on these selected test inputs to further generate new inputs. As a result, less redundant test inputs, i.e., inputs that just explore shallow program paths, are created at the first stage, and more distinct test inputs, i.e., inputs that explore deep program paths, are produced at the second stage. A prototype tool SimFuzz is developed and evaluated on real programs, and the experimental results are promising.     

Pattern‐based GUI testing: Bridging the gap between design and quality assurance

Software systems with a graphical user interface (GUI) front end are typically designed using user interface (UI) Patterns, which describe generic solutions (with multiple possible implementations) for recurrent GUI design problems. However, existing testing techniques do not take advantage of this fact to test GUIs more efficiently. In this paper, we present a new pattern‐based GUI testing (PBGT) approach that formalizes the notion of UI Test Patterns, which are generic test strategies to test UI patterns over their different implementations. The PBGT approach is evaluated via 2 case studies. The first study involves 2 fielded Web application subjects; findings show that PBGT is both practical and useful, as testing teams were able to find real bugs in a reasonable time interval. The second study allows deeper analysis by studying software subjects seeded with artificial faults; the findings show that PBGT is more effective than a manual model‐based test case generation approach.     

面向ROS的差分模糊测试方法

机器人操作系统（Robot Operating System,简称ROS）是一种广泛应用于机器人开发的开源系统,它可以为开发者提供硬件抽象、设备驱动、库函数、可视化、消息传递和软件包管理等诸多功能,具有重要而广阔的应用前景.ROS集成了可以实现不同功能的功能包,例如定位绘图、行动规划、感知、模拟等等,但其中可能存在一些漏洞破坏整个机器人系统的安全性和可靠性;本文提出了一种差分模糊测试方法对ROS不同版本的功能包进行测试,找出其中的漏洞.我们的方法包括测试用例生成和差分模糊测试执行两个模块.首先,对于输入文件进行加载、处理并基于策略生成的方法生成测试用例文件;其次,节点间使用话题通讯机制实现通讯,使用上一模块生成的测试用例文件作为统一的模糊输入,对ROS不同版本的功能包进行差分模糊测试;接着,对测试结果中的不一致输出进行差异计算并评估,符合评估指标的种子将被保留并反馈给用例生成模块循环生成测试用例,有效提高种子质量及代码覆盖率;最后分析不一致输出原因,找出漏洞.我们将该方法应用在机器人坐标转换的实验中,实现对不同参考系下坐标转换的功能包TF和TF2的测试;最终实验表明,与TF2相比,TF在功能实现上更加准确.TF2实现坐标旋转变换的函数存在漏洞.     

嵌入式软件结构化测试方法及其相关案例研究

嵌入式软件的测试是当今计算机软件测试领域的一个热点。该文首先分析了在嵌入式系统中进行软件测试的重要性以及目前进行嵌入式软件测试所面临的困难,接着介绍嵌入式软件的一种结构化测试方法——TEmb方法,并在此基础上根据一个实例——火控系统测试来具体应用嵌入式软件结构化测试方法。     

关于蜕变测试和特殊用例测试的实例研究

提出了基于蜕变测试方法的集成测试环境MTest,进而为检验蜕变测试方法的能力和效率,以稀疏矩阵乘法程序为例设计了一组实验.该实验基于变异分析技术,分别以mutation score和错误发现率为度量指标,定量地分析和对比了特殊用例测试,以特殊测试用例和随机测试用例为源测试用例的蜕变测试这3种方法的测试能力和效率.该实验可在MTest测试环境下自动完成.实验结果表明,蜕变测试与特殊用例测试之间是互补的,而且就蜕变测试的源测试用例而言,随机测试用例在测试能力和效率上优于特殊测试用例.     

两两组合覆盖测试数据自动生成集成工具的设计与实现

两两组合覆盖测试方法是一种科学有效的软件测试方法,相应的测试数据生成算法是人们研究的一个重点问题,本文在人们已有的研究基础上,结合我们在这个方面的研究成果,设计实现了一个两两组合覆盖测试数据自动生成工具,所产生的测试数据集与同类工具相比具有一定的特点和优势。