Using compiler optimization techniques to detect equivalent mutants

Mutation analysis is a software testing technique that requires the tester to generate test data that will find specific, well-defined errors. Mutation testing executes many slightly differing versions, called mutants, of the same program to evaluate the quality of the data used to test the program. Although these mutants are generated and executed efficiently by automated methods, many of the mutants are functionally equivalent to the original program and are not useful for testing. Recognizing and eliminating equivalent mutants is currently done by hand, a time-consuming and arduous task. This problem is currently a major obstacle to the practical application of mutation testing. This paper presents extensions to previous work in detecting equivalent mutants; specifically, algorithms for determining several classes of equivalent mutants are presented, an implementation of these algorithms is discussed, and results from using this implementation are presented. These algorithms are based on data flow analysis and six compiler optimization techniques. Each of these techniques is described together with how they are used to detect equivalent mutants. The design of the tool and some experimental results using it are also presented.     

Symbolic Testing and the DISSECT Symbolic Evaluation System

Symbolic testing and a symbolic evaluation system called DISSECT are described. The principle features of DISSECT are outlined. The results of two classes of experiments in the use of symbolic evaluadon are summarized. Several classes of program errors are defined and the reliability of symbolic testing in finding bugs is related to the classes of errors. The relationship of symbolic evaluation systems like DISSECT to classes of program errors and to other kinds of program testing and program analysis tools is also discussed. Desirable improvements in DISSECT, whose importance was revealed by the experiments, are mentioned.     

Anomaly detection in concurrent Java programs using dynamic data flow analysis

Concurrency constructs are widely used when developing complex software such as real-time, networking and multithreaded client–server applications. Consequently, testing a program, which includes concurrency constructs is a very elaborate and complex process. In this work, we first identify the different classes of synchronization anomalies that may occur in concurrent Java programs. We then consider testing concurrent Java programs against synchronization anomalies using dynamic data flow analysis techniques. Moreover, we show how the data flow analysis technique can be extended to detect such anomalies.     

An evaluation of the effectiveness of symbolic testing

The effectiveness in discovering errors of symbolic evaluation and of testing sad static program analysis are studied. The three techniques are applied to a diverse collection of programs and the results compared. Symbolic evaluation is used to carry out symbolic testing and to generate symbolic systems of path predicates. The use of the predicates for automated test data selection is analysed. Several conventional types of program testing strategies are evaluated. The strategies include branch testing, structured testing and testing on input values having special properties. The static source analysis techniques that are studied include anomaly analysis and interface analysis. Examples are included which describe typical situations in which one technique is reliable but another unreliable. The effectiveness of symbolic testing is compared with testing on actual data and with the use of an integrated methodology that includes both testing and static source analysis. Situations in which symbolic testing is difficult to apply or not effective are discussed. Different ways in which symbolic evaluation can be used for generating test data are described. Those ways for which it is most effective are isolated. The paper concludes with a discussion of the most effective uses to which symbolic evaluation can he put in an integrated system which contains all three of the validation techniques that are studied.     

An empirical, path-oriented approach to software analysis and testing

Error flow analysis and testing techniques focus on the introduction of errors through code faults into data states of an executing program, and their subsequent cancellation or propagation to output. The goals and limitations of several error flow techniques are discussed, including mutation analysis, fault-based testing, PIE analysis, and dynamic impact analysis. The attributes desired of a good error flow technique are proposed, and a model called dynamic error flow analysis (DEFA) is described that embodies many of these attributes. A testing strategy is proposed that uses DEFA information to select an optimal set of test paths and to quantify the results of successful testing. An experiment is presented that illustrates this testing strategy. In this experiment, the proposed testing strategy outperforms mutation testing in catching arbitrary data state errors.     

Emulation of Software Faults: A Field Data Study and a Practical Approach

The injection of faults has been widely used to evaluate fault tolerance mechanisms and to assess the impact of faults in computer systems. However, the injection of software faults is not as well understood as other classes of faults (e.g., hardware faults). In this paper, we analyze how software faults can be injected (emulated) in a source-code independent manner. We specifically address important emulation requirements such as fault representativeness and emulation accuracy. We start with the analysis of an extensive collection of real software faults. We observed that a large percentage of faults falls into well-defined classes and can be characterized in a very precise way, allowing accurate emulation of software faults through a small set of emulation operators. A new software fault injection technique (G-SWFIT) based on emulation operators derived from the field study is proposed. This technique consists of finding key programming structures at the machine code-level where high-level software faults can be emulated. The fault-emulation accuracy of this technique is shown. This work also includes a study on the key aspects that may impact the technique accuracy. The portability of the technique is also discussed and it is shown that a high degree of portability can be achieved     

变长检错码

本文提出变长错误模型和变长错误检错码的概念，具体给出两类变长检错码，分析了其检测变长错误的能力，并介绍了其在计算机病毒防治中的实际应用．     

Weak Mutation Testing and Completeness of Test Sets

Different approaches to the generation of test data are described. Error-based approaches depend on the definition of classes of commonly occurring program errors. They generate tests which are specifically designed to determine if particular classes of errors occur in a program. An error-based method called weak mutation testing is described. In this method, tests are constructed which are guaranteed to force program statements which contain certain classes of errors to act incorrectly during the execution of the program over those tests. The method is systematic, and a tool can be built to help the user apply the method. It is extensible in the sense that it can be extended to cover additional classes of errors. Its relationship to other software testing methods is discussed. Examples are included.     

内存泄漏检测工具与评估方法

内存泄漏是软件系统中常见的一种错误,会持续消耗内存,致使系统运行效率下降,甚至导致系统崩溃。内存泄漏的检测工具主要可以分为两类:一类是使用基于程序扫描分析技术的静态工具;另一类则是监视实时内存分配状态进行判别的动态工具。如何评估工具检测内存泄漏的能力,相关的标准并不明确。通过对内存泄漏的认识与了解,对相关工具能力进行了调研与分析,提出了一个内存泄漏工具的评估标准。     

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.     

Anomaly Detection in Concurrent Software by Static Data Flow Analysis

Algorithms are presented for detecting errors and anomalies in programs which use synchronization constructs to implement concurrency. The algorithms employ data flow analysis techniques. First used in compiler object code optimization, the techniques have more recently been used in the detection of variable usage errors in dngle process programs. By adapting these existing algorithms, the sane classes of variable usage errors can be detected in concurrent process programs. Important classes of errors unique to concurrent process programs are also described, and algorithms for their detection are presented.     

一种面向容侵系统的并行错误检测方法——PBL方法

面向入侵容忍的错误检测是系统安全最前沿的研究热点之一，它是保障容侵系统无边界退化、提供全部或降级服务的核心技术．分布式复杂网络环境中，错误的并发性和噪声信息的干扰使传统错误检测方法不再适用，在研究目前错误检测方法的基础上，结合容侵系统特性，提出了一种基于改进的贝叶斯并行学习的并行错误检测方法——PBL方法．该方法既能有效检测分布式环境下的并发错误，又能排除噪声数据的干扰．对PBL方法实现的关键问题进行了详细的讨论和分析．     

A Recovery Technique for Distributed Communicating Process Systems

This paper presents a recovery technique for distributed communicating processsystems.It handles both hardware faults and software faults uniformly.Differing fromother recovery techniques,it brings an extremely small amount of execution overheadto nonfailing processes and can be implemented easily.It can be applied to aprogramming procedure to mask the software design errors or imbeded into anoperating system to enhance the reliability of the whole system.The theoretical workis carried out first,then the implementation problems are considered and theevaluation techniques are discussed last.     

Text Classification for Azerbaijani Language Using Machine Learning

Text classification systems will help to solve the text clustering problem in the Azerbaijani language. There are some text-classification applications for foreign languages, but we tried to build a newly developed system to solve this problem for the Azerbaijani language. Firstly, we tried to find out potential practice areas. The system will be useful in a lot of areas. It will be mostly used in news feed categorization. News websites can automatically categorize news into classes such as sports, business, education, science, etc. The system is also used in sentiment analysis for product reviews. For example, the company shares a photo of a new product on Facebook and the company receives a thousand comments for new products. The systems classify comments like positive or negative. The system can also be applied in recommended systems, spam filtering, etc. Various machine learning techniques such as Naive Bayes, SVM, Multi-layer Perceptron have been devised to solve the text classification problem in Azerbaijani language.     

Research on dynamic update transaction for Java classes

Dynamic software updating is critical for many systems that must provide continuous service. In addition, the Java language is gaining increasing popularity in developing distributed systems. Most previous works on updating are concerned with safely updating one class every time. It has many limitations on updating classes, such as not allowing deleting methods invoked in other classes. In this paper, the update transaction is purposed to dynamically update the class set, and some of its properties are discussed, such as atomicity, consistency, isolation, and durability (ACID). Then the property of type-safety is proven formally. In order to update without changing the Java Virtual Machine (JVM) and the Java programming language, this paper proposes a new implementation method. The method makes use of the Java class loading mechanism and reflection mechanism. We also present how to design an updatable Java program and a Java updating program. At the end of the paper, an experiment is made for analysis.     

A model‐driven approach to automatic conversion of physical units

When physical quantities are used in programs they are typically represented as raw numbers, with the units in which they were measured only being given in comments, if at all. This can lead to errors from the use of dimensionally inconsistent expressions, or the comparison of two quantities of the same dimension but measured in different units, which are not discovered until run time. Any program working with the physical world has this issue, with scientific modelling being a major application. Implementors of models have the time‐consuming and error‐prone task of adding in dynamic units checks and conversions manually. Most existing programming languages do not provide support for representing units explicitly (although extensions to some have been proposed). With the advent of domain‐specific modelling languages, incorporating code generation techniques, we propose checking physical units at the level of the modelling language, removing the need for such a support in the underlying implementation language. We present our work in the context of one such modelling language: CellML, developed at the University of Auckland with a focus on modelling biological systems. We have developed an intuitive algorithm for performing automatic conversions between quantities measured in different units. It both requires fewer conversion operations than current approaches and makes more sensible choices about which quantities to convert. Uniquely, by using partial evaluation techniques it is also capable of dealing robustly with quantities raised to arbitrary powers, even where the exponent is given by an expression. We demonstrate our algorithm on various examples. Copyright © 2007 John Wiley & Sons, Ltd.     

Transformation-based diagnosis of student programs for programming tutoring systems

A robust technology that automates the diagnosis of students' programs is essential for programming tutoring systems. Such technology should be able to determine whether programs coded by a student are correct. If a student's program is incorrect, the system should be able to pinpoint errors in the program as well as explain and correct the errors. Due to the difficulty of this problem, no existing system performs this task entirely satisfactorily, and this problem still hampers the development of programming tutoring systems. This paper describes a transformation-based approach to automate the diagnosis of students' programs for programming tutoring systems. Improved control-flow analysis and data-flow analysis are used in program analysis. Automatic diagnosis of student programs is achieved by comparing the student program with a specimen program at the semantic level after both are standardized. The approach was implemented and tested on 525 real student programs for nine different programming tasks. Test results show that the method satisfies the requirements stated above. Compared to other existing approaches to automatic diagnosis of student programs, the approach developed here is more rigorous and safer in identifying student programming errors. It is also simpler to make use of in practice. Only specimen programs are needed for the diagnosis of student programs. The techniques of program standardization and program comparison developed here may also be useful for research in the fields of program understanding and software maintenance.     

Data mining for defects in multicore applications: an entropy‐based call‐graph technique

Multicore computers are ubiquitous. Expert developers as well as developers with little experience in parallelism are now asked to create multithreaded software to exploit parallelism in mainstream shared‐memory hardware. However, finding and fixing parallel programming errors is a complex and arduous task. Programmers thus rely on tools such as race detectors that typically focus on reporting errors due to incorrect usage of synchronization constructs or due to missing synchronization. This arsenal of debugging techniques, however, is incomplete. This article presents a new perspective and addresses a largely unexplored direction of defect localization where a wrong usage of nonparallel programming constructs might cause wrong parallel application behavior. In particular, we make a contribution by showing how to use data‐mining techniques to locate defects in multithreaded shared‐memory programs. Our technique analyzes execution anomalies in a condensed representation of the dynamic call graphs of a multithreaded object‐oriented application and identifies methods that contain a defect. Compared with race detectors that concentrate on finding incorrect synchronization, our method is able to reveal a wider range of defects that affect the control flow of a parallel program. Results from controlled experiments show that our data‐mining approach finds not only race conditions in different types of multicore applications but also other errors that cause incorrect parallel program behavior. Data‐mining techniques offer a fruitful new ground for parallel program debugging, and we also discuss long‐term directions for this interesting field. Copyright © 2012 John Wiley & Sons, Ltd.     

Efficient Symbolic Analysis for Parallelizing Compilers and Performance Estimators

Symbolic analysis is of paramount importance for parallelizing compilers and performance estimators to examine symbolic expressions with program unknowns such as machine and problem sizes and to solve queries based on systems of constraints (equalities and inequalities). This paper describes novel techniques for counting the number of solutions to a system of constraints, simplifying systems of constraints, computing lower and upper bounds of symbolic expressions, and determining the relationship between symbolic expressions. All techniques target wide classes of linear and non-linearsymbolic expressions and systems of constraints. Our techniques have been implemented and are used as part of a parallelizing compiler and a performance estimator to support analysis and optimization of parallel programs. Various examples and experiments demonstrate the effectiveness of our symbolic analysis techniques.