Java Bytecode Transformations for Efficient, Portable CPU Accounting

Resource management is essential to build reliable middleware and to host potentially untrusted software components. Resource accounting allows to study and optimize program performance and to charge users for the resource consumption of their deployed components, while resource control can limit the resource consumption of components in order to prevent denial-of-service attacks. In the approach presented here, program transformations enable resource management in Java-based environments, even though the underlying runtime system may not expose information concerning the resource consumption of applications. We present a fully portable program transformation scheme to enhance standard Java runtime systems with mechanisms for CPU management. We implemented several optimizations in order to reduce the overhead of our CPU accounting scheme. Detailed performance measurements quantify this overhead and show the impact of various optimizations.     

A Type System for the Java Bytecode Language and Verifier

The Java Virtual Machine executes bytecode programs that may have been sent from other, possibly untrusted, locations on the network. Since the transmitted code may be written by a malicious party or corrupted during network transmission, the Java Virtual Machine contains a bytecode verifier to check the code for type errors before it is run. As illustrated by reported attacks on Java run-time systems, the verifier is essential for system security. However, no formal specification of the bytecode verifier exists in the Java Virtual Machine Specification published by Sun. In this paper, we develop such a specification in the form of a type system for a subset of the bytecode language. The subset includes classes, interfaces, constructors, methods, exceptions, and bytecode subroutines. We also present a type checking algorithm and prototype bytecode verifier implementation, and we conclude by discussing other applications of this work. For example, we show how to extend our formal system to check other program properties, such as the correct use of object locks. This revised version was published online in August 2006 with corrections to the Cover Date.     

On the estimation of adequate test set size using fault failure rates

Test set size in terms of the number of test cases is an important consideration when testing software systems. Using too few test cases might result in poor fault detection and using too many might be very expensive and suffer from redundancy. We define the failure rate of a program as the fraction of test cases in an available test pool that result in execution failure on that program. This paper investigates the relationship between failure rates and the number of test cases required to detect the faults. Our experiments based on 11 sets of C programs suggest that an accurate estimation of failure rates of potential fault(s) in a program can provide a reliable estimate of adequate test set size with respect to fault detection and should therefore be one of the factors kept in mind during test set construction. Furthermore, the model proposed herein is fairly robust to incorrect estimations in failure rates and can still provide good predictive quality. Experiments are also performed to observe the relationship between multiple faults present in the same program using the concept of a failure rate. When predicting the effectiveness against a program with multiple faults, results indicate that not knowing the number of faults in the program is not a significant concern, as the predictive quality is typically not affected adversely.     

基于模型的软件接口故障注入测试平台技术

针对软件接口类型多、接口故障注入自动控制复杂的困难以及目前缺少有效的软件接口故障注入工具现状,对软件故障注入中的交联接口故障注入技术展开研究,提出了一种基于模型的软件接口故障注入测试平台技术。通过交联接口测试可视化建模和接口故障注入算子设计,自动生成XML 格式的测试用例,并且通过基于XSLT的脚本自动化生成与执行技术实现测试的控制与执行。故障注入测试主机与接口故障注入器网络连接,接口故障注入器将接口故障数据转换成以太网、串口或CAN网络数据注入到被测软件中,并返回被测件输出数据到测试主机实现测试数据收集与判断。基于模型的软件接口故障注入测试平台具有较强的通用性与易用性,提高了接口故障注入测试的效率,降低了接口测试的成本。     

Mining software repositories for comprehensible software fault prediction models

Software managers are routinely confronted with software projects that contain errors or inconsistencies and exceed budget and time limits. By mining software repositories with comprehensible data mining techniques, predictive models can be induced that offer software managers the insights they need to tackle these quality and budgeting problems in an efficient way. This paper deals with the role that the Ant Colony Optimization (ACO)-based classification technique AntMiner+ can play as a comprehensible data mining technique to predict erroneous software modules. In an empirical comparison on three real-world public datasets, the rule-based models produced by AntMiner+ are shown to achieve a predictive accuracy that is competitive to that of the models induced by several other included classification techniques, such as C4.5, logistic regression and support vector machines. In addition, we will argue that the intuitiveness and comprehensibility of the AntMiner+ models can be considered superior to the latter models.     

面向Java锁机制的字节码自动重构框架

Java语言提供了同步锁、可重入锁和读写锁等几种锁机制,在并行程序设计中不同的数据结构使用这几种锁机制时获得的性能通常是不同的。为了在不同的锁机制之间进行自动转换,进而帮助程序员了解程序的性能,提出了一种面向Java锁机制的字节码自动重构框架,并基于该框架实现了字节码重构工具Lock2Lock。Lock2Lock在Quad中间表示的基础上对字节码进行静态分析,并对分析的结果进行一致性验证,通过Javassist完成字节码的重构。使用红黑树、消费者生产者程序以及SPECjbb2005 3个测试程序对Lock2Lock重构工具进行了测试,结果表明,Lock2Lock可以成功地实现从同步锁到可重入锁或读写锁的重构。     

一种优化软件可靠性测试费用的模型研究

软件复用是提高软件开发效率和改善软件质量的一项重要技术。把领域工程中可复用思想应用到测试用例的复用中,提出了测试用例的复用技术模型。通过实例说明,该模型能提高测试的可靠性以及测试效率,具有可行性。     

Mutation-oriented test data augmentation for GUI software fault localization

ContextFault localization lies at the heart of program debugging and often proceeds by contrasting the statistics of program constructs executed by passing and failing test cases. A vital issue here is how to obtain these “suitable” test cases. Techniques presented in the literature mostly assume the existence of a large test suite a priori. However, developers often encounter situations where a failure occurs, but where no or no appropriate test suite is available for use to localize the fault.ObjectiveThis paper aims to alleviate this key limitation of traditional fault localization techniques for GUI software particularly, namely, it aims at enabling cost-effective fault localization process for GUI software in the described scenario.MethodTo address this scenario, we propose a mutation-oriented test data augmentation technique, which actually is directed by the “similarity” criterion in GUI software’s test case context towards the generation of test suite with excellent fault localization capabilities. More specifically, the technique mainly uses four proposed novel mutation operators to iteratively mutate some failing GUI test cases’ event sequences to derive new test cases potentially useful to localize the specific encountered fault. We then compare the fault localization performance of the test suite generated using this technique with that of an original provided large event-pair adequate test suite on some GUI applications.ResultsThe results indicate that the proposed technique is capable of generating a test suite that has comparable, if not better, fault localization effectiveness to the event-pair adequate test suite, but it is much smaller and it is generated immediately once a failure is encountered by developers.ConclusionIt is concluded that the proposed technique can truly enable quick-start cost-effective fault localization process under the investigated all-too-common scenario, greatly alleviating one key limitation of traditional fault localization techniques and prompting the test–diagnose–repair cycle.     

A semantic approach for automated test oracle generation

This paper presents the design, implementation, and applications of a software testing tool, TAO, which allows users to specify and generate test cases and oracles in a declarative way. Extended from its previous grammar-based test generation tool, TAO provides a declarative notation for defining denotational semantics on each productive grammar rule, such that when a test case is generated, its expected semantics will be evaluated automatically as well, serving as its test oracle. TAO further provides a simple tagging mechanism to embed oracles into test cases for bridging the automation between test case generation and software testing. Two practical case studies are used to illustrate how automated oracle generation can be effectively integrated with grammar-based test generation in different testing scenarios: locating fault-inducing input patterns on Java applications; and Selenium-based automated web testing.     

Generating minimal fault detecting test suites for general Boolean specifications

Context

Boolean expressions are a central aspect of specifications and programs, but they also offer dangerously many ways to introduce faults. To counter this effect, various criteria to generate and evaluate tests have been proposed. These are traditionally based on the structure of the expressions, but are not directly related to the possible faults. Often, they also require expressions to be in particular formats such as disjunctive normal form (DNF), where a strict hierarchy of faults is available to prove fault detection capability.

Objective

This paper describes a method that generates test cases directly from an expression’s possible faults, guaranteeing that faults of any chosen class will be detected. In contrast to many previous criteria, this approach does not require the Boolean expressions to be in DNF, but allows expressions in any format, using any deliberate fault classes.

Method

The presented approach is based on creating test objectives for individual faults, such that efficient, modern satisfiability solvers can be used to derive test cases that directly address the faults. Although the number of such test objectives can be high depending on the considered fault classes, a number of optimizations can be applied to reduce the test generation effort.

Results

Evaluation on a set of commonly used benchmarks shows that despite guaranteeing fault coverage, the number of test cases can be reduced even further than that produced by other state of the art strategies. At the same time, the fault detection capability is not affected negatively, and clearly improves over state of the art criteria for general form Boolean expressions.

Conclusion

The approach presented in this paper is shown to improve over the state of the art with respect to the types of expressions that can be handled, the fault classes that are guaranteed to be covered, and the sizes of test suites generated automatically. This has implications for several fields of software testing: A main application is specification based testing, but Boolean expressions also exist in normal source code and need to be tested there as well.     

An object based algebra for specifying a fault tolerant software architecture

In this paper we present an algebra of actors extended with mechanisms to model crash failures and their detection. We show how this extended algebra of actors can be successfully used to specify distributed software architectures. The main components of a software architecture can be specified following an object-oriented style and then they can be composed using asynchronous message passing or more complex interaction patterns. This formal specification can be used to show that several requirements of a software system are satisfied at the architectural level despite failures. We illustrate this process by means of a case study: the specification of a software architecture for intelligent agents which supports a fault tolerant anonymous interaction protocol.     

一种软件可靠性测试方法研究

为了缩短软件测试周期,本文把马尔可夫链模型运用于软件可靠性测试中,提出了这一技术进行软件可靠性测试的方法。在测试过程中使用了新的评判准则分析测试结果,通过实例证明了该评判准则的实用性和有效性。     

Mutant generation for embedded systems using kernel-based software and hardware fault simulation

Context

Mutation testing is a fault-injection-based technique to help testers generate test cases for detecting specific and predetermined types of faults.

Objective

Before mutation testing can be effectively applied to embedded systems, traditional mutation testing needs to be modified. To inject a fault into an embedded system without causing any system failure or hardware damage is a challenging task as it requires some knowledge of the underlying layers such as the kernel and the corresponding hardware.

Method

We propose a set of mutation operators for embedded systems using kernel-based software and hardware fault simulation. These operators are designed for software developers so that they can use the mutation technique to test the entire system after the software is integrated with the kernel and hardware devices.

Results

A case study on a programmable logic controller for a digital reactor protection system in a nuclear power plant is conducted. Our results suggest that the proposed mutation operators are useful for fault-injection and this is evidenced by the fact that faults not injected by us were discovered in the subject software as a result of the case study.

Conclusion

We conclude that our mutation operators are useful for integration testing of an embedded system.     

软件可靠性综合模型的分析和研究

软件可靠性是系统可信性的重要属性之一.首先讨论了传统软件可靠性模型的主要弱点,接着提出了一种新的软件可靠性估算模型.当前,传统的软件可靠性度量模型中并未涉及大多数软件的复杂性及测试用例的有效性,从而使得在评估软件可靠性时不够精确,甚至是错误的.因此,提出了一些改进软件可靠性度量的方法.这些方法的主要思想是将影响软件复杂性的因素和测试用例的有效性并入软件可靠性模型中,以便使得该模型能更精确地反映实际情况.最后,大量的实验结果也表明了该模型的合理性及有用性.     

Dynamic method for software test data generation

Test data generation in program testing is the process of identifying a set of test data which satisfies a given testing criterion. Existing pathwise test data generators proceed by selecting program paths that satisfy the selected criterion and then generating program inputs for these paths. One of the problems with this approach is that unfeasible paths are often selected; as a result, significant computational effort can be wasted in analysing those paths. In this paper, an approach to test data generation, referred to as a dynamic approach for test data generation, is presented. In this approach, the path selection stage is eliminated. Test data are derived based on the actual execution of the program under test and function minimization methods. The approach starts by executing a program for an arbitrary program input. During program execution for each executed branch, a search procedure decides whether the execution should continue through the current branch or an alternative branch should be taken. If an undesirable execution flow is observed at the current branch, then a real-valued function is associated with this branch, and function minimization search algorithms are used to locate values of input variables automatically, which will change the flow of execution at this branch.     

基于故障的布尔表达式测试技术综述

布尔表达式是软件规格说明与程序实现中的关键成份,严重影响软件的正确性。如何有效地测试布尔表达式是软件测试领域的一个重要研究方向。介绍了基于故障的软件测试的基本概念与原理,归纳了布尔表达式的各种故障类型,讨论了不同故障类型之间的检测包含关系;评述了几类代表性的面向布尔表达式的测试策略,提出了一种比较框架并比较了各种策略的适用情形、故障检测能力与测试用例精简程度。针对现有研究工作的不足,探讨了几个值得研究的问题,简要介绍了近年来此领域的研究工作。     

Evaluating the change of software fault behavior with dataset attributes based on categorical correlation

Utilization of data mining in software engineering has been the subject of several research papers. Majority of subjects of those paper were in making use of historical data for decision making activities such as cost estimation and product or project attributes prediction and estimation. The ability to predict software fault modules and the ability to correlate relations between faulty modules and product attributes using statistics is the subject of this paper. Correlations and relations between the attributes and the categorical variable or the class are studied through generating a pool of records from each dataset and then select two samples every time from the dataset and compare them. The correlation between the two selected records is studied in terms of changing from faulty to non-faulty or the opposite for the module defect attribute and the value change between the two records in each evaluated attribute (e.g. equal, larger or smaller). The goal was to study if there are certain attributes that are consistently affecting changing the state of the module from faulty to none, or the opposite. Results indicated that such technique can be very useful in studying the correlations between each attribute and the defect status attribute. Another prediction algorithm is developed based on statistics of the module and the overall dataset. The algorithm gave each attribute true class and faulty class predictions. We found that dividing prediction capability for each attribute into those two (i.e. correct and faulty module prediction) facilitate understanding the impact of attribute values on the class and hence improve the overall prediction relative to previous studies and data mining algorithms. Results were evaluated and compared with other algorithms and previous studies. ROC metrics were used to evaluate the performance of the developed metrics. Results from those metrics showed that accuracy or prediction performance calculated traditionally using accurately predicted records divided by the total number of records in the dataset does not necessarily give the best indicator of a good metric or algorithm predictability. Those predictions may give wrong implication if other metrics are not considered with them. The ROC metrics were able to show some other important aspects of performance or accuracy.     

基于FSM的测试用例生成算法

研究了基于FSM模型的测试用例自动生成算法来验证实现的FSM与规格FSM的一致性。基于状态机分解的思想提出了新的用例生成方法,DC-方法。相对其他通用方法而言,它不必依据测试树中所有的子路径集合,从而使得用例集减少,同时减少每次重置到初始态的次数,测试序列的长度也有所减少,节省了测试时间,提高了效率,并且具有良好的扩展性,可以方便应用于包含数据流的测试,只需在搜索到所有的DU-Path后直接经过运算就能得出测试用例。并给出了生成用例方法的正确性证明。     

模糊测试技术研究综述

软件中的安全漏洞可能导致非常严重的后果,因此漏洞挖掘已成为网络与信息安全领域的重大课题和研究热点。目前常用的漏洞挖掘技术包括静态分析、动态分析、二进制比对、模糊测试等。随着软件的规模和复杂度不断增大,模糊测试具有其它漏洞挖掘技术无法比拟的优势。首先介绍和分析了各种漏洞挖掘技术的优点和缺点;然后分别详细描述了模糊测试的研究进展、模糊测试的过程、测试用例的生成技术;最后介绍了模糊测试在各个领域的应用,并对其发展方向进行了展望。     

基于方法序列规范的测试用例生成

1 引言面向对象软件测试技术的研究是最近几年才引起重视的一个新领域。OO程序由于引入了封装、继承、多态等概念和机制,在程序的组织结构和运行机制上与传统的程序有很大差别,因而也对软件测试技术提出了新要求。无论是传统程序还是OO程序,测试活动通常分4个步骤进行:(1)确定测试准则;(2)基于测试准则构造