Using program slicing to simplify testing

Program slicing is a technique for automatically identifying the statements of a program which affect a selected subset of its variables. A large program can be divided into a number of smaller program (its slices), each constructed for different variable subsets. The slices are typically simpler than the original program, thereby simplifying the process of testing a property of the program which only concerns the corresponding subset of its variables. However, some aspects of a program's computation are not captured by a set of variables, rendering slicing inapplicable. To overcome this difficulty a program can be rewritten in a self-checking form by the addition of assignment statements to denote these ‘implicit’ computations. Initially this makes the program longer. However, slicing can now be applied to the introspective program, forming a slice concerned solely with the implicit computation. The simplification power of slicing is then improved using program transformation. To illustrate this approach, the implicit computation which dictates whether or not a program is robust is taken as an example. Whether or not a program is robust is not generally decidable making the approach described here particularly appealing because the slices constructed are approximate answers to the undecidable question ‘Is the program p robust?’.     

对象级粗粒度切片方法

基于面向对象程序的对象间语义级关系,提出了一种对象级粗粒度切片方法,用于解决以往传统程序切片构造过程复杂,切片结构庞大,可理解性不强等问题.该方法并非基于传统的程序依赖图或系统依赖图,而是建立在对象间的关联、组合等语义级关系的基础之上.依据对象间语义级关系构造程序的对象图,在对象图的基础上获取程序的前向对象级粗粒度切片和后向对象级粗粒度切片,并结合了对象间的组合关系使得所得后向对象级粗粒度切片更加精简.     

Estimation of failure rate using random and partition testing

Failure rate, given an operational profile, is a common measure of reliability. A number of approaches to estimating failure rate are described and it is demonstrated that, under certain conditions, a functional partition can provide a better estimator than random-testing-based estimators. © 1997 John Wiley & Sons, Ltd.     

Improved verification of hardware designs through antecedent conditioned slicing

Static slicing has shown itself to be a valuable tool, facilitating the verification of hardware designs. In this paper, we present a sharpened notion, antecedent conditioned slicing that provides a more effective abstraction for reducing the size of the state space. In antecedent conditioned slicing, extra information from the antecedent is used to permit greater pruning of the state space. In a previous version of this paper, we applied antecedent conditioned slicing to safety properties of the form G(antecedent ⇒ consequent) where antecedent and consequent were written in propositional logic. In this paper, we use antecedent conditioned slicing to handle safety and bounded liveness property specifications written in linear time temporal logic. We present a theoretical justification of our technique. We provide experimental results on a Verilog RTL implementation of the USB 2.0 functional core, which is a large design with about 1,100 state elements (10³³¹ states). The results demonstrate that the technique provides significant performance benefits over static program slicing using state-of-the-art model checkers.     

Using passive testing based on symbolic execution and slicing techniques: Application to the validation of communication protocols

This paper presents a new approach to perform passive testing based on the analysis of the control and data part of the system under test. Passive testing techniques are based on the observation and verification of properties on the behaviour of a system without interfering with its normal operation. Many passive testing techniques consider only the control part of the system and neglect data, or are confronted with an overwhelming amount of data values to process. In our approach, we consider control and data parts by integrating the concepts of symbolic execution and we improve trace analysis by introducing trace slicing techniques. Properties are described using Input–Output Symbolic Transition Systems (IOSTSs) and we illustrate in the paper how they can be tested on real execution traces optimizing the trace analysis. These properties can be designed to test the functional conformance of a protocol as well as security properties.     

基于分域测试的软件可靠性评估方法

软件可靠性评估通常是以可靠度的精确置信下限为主要依据。在求解可靠度置信限的方法中,排序方法是较理想的方法,但是现有的排序方法都存在计算量大和不易实现的缺点。通过对可靠度相关参量的分析,根据软件在进行分域测试时的特点给出一种新的排序方法。经过实例分析可知,此排序方法是合理的,并且计算简便和易于实现。     

Combining preprocessor slicing with C/C++ language slicing

Of the very few practical implementations of program slicing algorithms, the majority deal with C/C++ programs. Yet, preprocessor-related issues have been marginally addressed by these slicers, despite the fact that ignoring (or only partially handling) these constructs may lead to serious inaccuracies in the slicing results and hence in the program analysis task being performed. Recently, an accurate slicing method for preprocessor-related constructs has been proposed, which-when combined with existing C/C++ language slicers-can provide more complete slices and hence a more successful analysis of programs written in one of these languages. In this paper, we present our approach which combines the two slicing methods and, via practical experiments, describe its benefits in terms of the completeness of the resulting slices.     

Theoretical foundations of dynamic program slicing

This paper presents a theory of dynamic slicing, which reveals that the relationship between static and dynamic slicing is more subtle than previously thought. The definitions of dynamic slicing are formulated in terms of the projection theory of slicing. This shows that existing forms of dynamic slicing contain three orthogonal dimensions in their slicing criteria and allows for a lattice-theoretic study of the subsumption relationship between these dimensions and their relationship to static slicing formulations.     

划分测试用例选择的风险决策方法*

研究了划分测试中划分方案确定情形下,如何在各个子域中合理选择测试用例问题。在充分利用测试者对待测软件导致错误输入分布信息了解的基础上,提出了一种基于风险决策的测试用例选择模型,给出测试用例选择的期望风险准则,并证明了该方法选择的测试用例集具有较高的缺陷检测能力。最后采用蒙特卡罗方法进行仿真模拟,结果表明该方法明显优于划分测试用例的其他选择策略。     

Detecting safety‐related components in statecharts through traceability and model slicing

With rapid development in software technology, more and more safety‐critical systems are software intensive. Safety issues become important when software is used to control such systems. However, there are 2 important problems in software safety analysis: (1) there is often a significant traceability gap between safety requirements and software design, resulting in safety analysis and software design are often conducted separately; and (2) the growing complexity of safety‐critical software makes it difficult to determine whether software design fulfills safety requirements. In this paper, we propose a technique to address the above 2 important problems on the model level. The technique is based on statecharts, which are used to model the behavior of software, and fault tree safety analysis. This technique contains the following 2 parts, which are corresponding to the 2 problems, respectively. The first part is to build a metamodel of traceability between fault trees and statecharts, which is to bridge their traceability gap. A collection of rules for the creation and maintenance of traceability links is provided. The second part is a model slicing technique to reduce the complexity of statecharts with respect to the traceability information. The slicing technique can deal with the characteristics of hierarchy, concurrency, and synchronization of statecharts. The reduced statecharts are much smaller than their original statecharts, which are helpful to successive safety analysis. Finally, we illustrate the effectiveness and the importance of the method by a case study of slats and flaps control units in flight control systems.     

基于条件分类可执行切片谱的软件缺陷定位

基于条件执行切片谱的多错误定位（Multiple Fault Localization based on Conditioned Execution Slicing Spectrum，CESS-MFL）考虑了程序的依赖性，可以一定程度降低程序随着缺陷数的增多而效率降低的问题，但该技术仍受与缺陷无关语句的影响比较大。因此，提出了一种基于条件分类可执行切片的软件缺陷定位方法（Conditioned Classification Execution Slicing Spectrum-based Software Fault Localization，CCESS-SFL），该技术对CESS-MFL技术中的谓词条件进行了改进并分类。根据谓词条件与缺陷相关执行切片确定条件特征集，根据条件特征集进行分类得到条件分类执行切片谱，计算元素的可疑度，最后生成可疑度报告。CCESS-SFL技术在西门子7个套件中得到了有效的验证，它优于当前流行的Tarantula、Jaccard、Ochiai以及CESS-MFL技术，可以进一步降低与缺陷无关语句的影响。     

在程序理解中使用切片技术

对于遗产软件的理解和维护在软件研究领域中已经变得越来越重要，综述了程序理解的策略及工具，引入了程序切片的思想，并在此基础上对传统的切片方法进行改进以更好地完成程序理解的任务。     

Dynamic slicing of concurrent AspectJ programs: An explicit context‐sensitive approach

This paper presents a context‐sensitive dynamic slicing technique for the concurrent and aspectized programs. To effectively represent the concurrent aspect‐oriented programs, we propose an intermediate graph called the multithreaded aspect‐oriented dependence graph (MAODG). The MAODG is a dynamic graph generated from the execution trace of a given program with respect to a particular set of values given as an input. Interference dependencies between the statements are shown by a distinguished edge called the interference dependence edge in the MAODG. Based on this intermediate representation, we propose a precise and accurate dynamic slicing algorithm for the concurrent aspect‐oriented programs implemented using AspectJ. The proposed dynamic slicing algorithm is implemented in a slicing tool developed using the ASM framework. Several open source programs are studied and evaluated using the proposed technique along with some existing techniques. The experimentation shows that our proposed slicing algorithm generates slices of the same or smaller size, as compared with the existing algorithms. Furthermore, we found that the slice computation time is significantly less in our proposed algorithm, as compared with the existing algorithms.     

Using program slicing to assist in the detection of equivalent mutants

While mutation testing has proved to be an effective way of finding software faults, currently it is only applied to relatively small programs. One of the main reasons for this is the human analysis required in detecting equivalent mutants. Here program slicing is used to simplify this problem. Progam slicing is also used to reduce the number of equivalent mutants produced. Copyright © 1999 John Wiley & Sons, Ltd.     

基于ISDG的面向对象程序分片技术研究

程序分片是一种有效的程序分析技术,它能根据给定的分片准则从源程序中提取出所需部分进行分析,如进行程序调试、测试、程序重构分析等。程序分片技术在结构化程序中已有较广泛的应用,但对于面向对象语言程序,其研究与应用还存在一些待解决的问题。针对面向对象语言程序,提出了一种改进后的系统依赖图：ISDG,用来更好地表示面向对象程序中的依赖关系,从而解决了对象类型参数和属性的表示问题。基于ISDG模型,提出了一种新的面向对象语言程序的分片准则,以度相应的分片算法。     

基于条件执行切片谱的多错误定位

基于程序谱的错误定位技术由于其较高的定位效率已成为当前软件调试领域研究热点之一.这种技术通常根据测试覆盖信息计算程序语句发生错误的可疑度来进行错误定位.然而,这种技术会随着程序中错误数目的增多效率不断下降.鉴于此,提出了一种基于条件执行切片谱的多错误定位技术(conditioned execution slicing spectrum-based multiple fault localization, CESS-MFL),以提高多错误定位的效率.CESS-MFL技术首先根据输入变量的谓词条件构建错误相关条件执行切片的谱矩阵,然后依次计算错误相关条件执行切片中的元素(语句或语句块)的可疑度,并生成可疑度报告.实验验证了CESS-MFL技术比当前流行的基于程序谱的Tarantula技术、基于程序切片的Intersection技术、Union技术有更高的多错误定位效率,并且可在有效的时间和空间复杂度内完成.     

Techniques and applications of computation slicing

Writing correct distributed programs is hard. In spite of extensive testing and debugging, software faults persist even in commercial grade software. Many distributed systems should be able to operate properly even in the presence of software faults. Monitoring the execution of a distributed system, and, on detecting a fault, initiating the appropriate corrective action is an important way to tolerate such faults. This gives rise to the predicate detection problem which requires finding whether there exists a consistent cut of a given computation that satisfies a given global predicate.Detecting a predicate in a computation is, however, an NP-complete problem in general. In order to ameliorate the associated combinatorial explosion problem, we introduce the notion of computation slice. Formally, the slice of a computation with respect to a predicate is a (sub)computation with the least number of consistent cuts that contains all consistent cuts of the computation satisfying the predicate. Intuitively, slice is a concise representation of those consistent cuts of a computation that satisfy a certain condition. To detect a predicate, rather than searching the state-space of the computation, it is much more efficient to search the state-space of the slice.We prove that the slice of a computation is uniquely defined for all predicates. We also present efficient algorithms for computing the slice for several useful classes of predicates. For an arbitrary predicate, we establish that the problem of computing the slice is NP-complete in general. Nonetheless, for such a predicate, we develop an efficient heuristic algorithm for computing an approximate slice. Our experimental results demonstrate that slicing can lead to an exponential improvement over existing techniques for predicate detection in terms of time and space.Received: 19 November 2003, Revised: 29 July 2004, Published online: 7 February 2005Vijay K. Garg: Supported in part by the NSF Grants ECS-9907213, CCR-9988225, Texas Education Board Grant ARP-320, an Engineering Foundation Fellowship, and an IBM grant.Parts of this paper have appeared earlier in conference proceedings [GM01,MG01a,MG03a].     

Comparison of adaptive random testing and random testing under various testing and debugging scenarios

Adaptive random testing is an enhancement of random testing. Previous studies on adaptive random testing assumed that once a failure is detected, testing is terminated and debugging is conducted immediately. It has been shown that adaptive random testing normally uses fewer test cases than random testing for detecting the first software failure. However, under many practical situations, testing should not be withheld after the detection of a failure. Thus, it is important to investigate the effectiveness with respect to the detection of multiple failures. In this paper, we compare adaptive random testing and random testing under various scenarios and examine whether adaptive random testing is still able to use fewer test cases than random testing to detect multiple software failures. Our study delivers some interesting results and highlights a number of promising research projects. Copyright © 2011 John Wiley & Sons, Ltd.