The testing of large databases faces the test oracle problem, namely, that it is difficult to verify execution results against expected outcomes. Rigger and Su applied metamorphic testing through query partitioning and ternary logic partitioning techniques to alleviate the challenge. In Part (A) of our project, we conduct an in-depth investigation and have identified a gap between the two techniques. We propose a disjoint partitioning approach to address it. In Part (B), we conduct a comprehensive investigation into the metamorphic testing of DBMS by comparing disjoint partitioning with metamorphic relation output patterns (MROPs) by Segura et al. We propose an exhaustive collection of MROPs for DBMS. To the best of our knowledge, this is the first project to integrate in-depth and comprehensive approaches to tackle the diverse challenges in DBMS testing. In Part (C), we conduct an empirical case study of their applications to OceanBase, the DBMS associated with the world’s fastest online transaction processing system. Although OceanBase has been extensively tested and widely used in the industry, we have detected 12 hidden failures and 8 new crashes.

Metamorphic testing (MT) was introduced about a quarter of a century ago. It is increasingly being accepted by researchers and the industry as a useful testing technique. The studies, research results, applications, and extensions of MT have given us many insights and visions for its future. Our visions include: MRs will be a practical means to top up test case generation techniques, beyond the alleviation of the test oracle problem; MT will not only be a standalone technique, but conveniently integrated with other methods; MT and MRs will evolve beyond software testing, or even beyond verification; MRs may be anything that you can imagine, beyond the necessary properties of algorithms; MT research will be beyond empirical studies and move toward a theoretical foundation; MT will not only bring new concepts to software testing but also new concepts to other disciplines; MRs will alleviate the reliable test set problem beyond traditional approaches. These visions may help researchers explore the challenges and opportunities for MT in the next decade.

Software plays an integral part in our lives today because of its near-ubiquitous influence on our increasingly technological society. Taking appropriate steps to improve software quality is of paramount importance. This has fueled a surge of techniques in program testing and analysis. Unfortunately, these techniques still suffer from immaturity and impracticality, which have hindered truthful benefits to the software industry. The Special Sections on Software Testing and Program Analysis solicited original work that would provide novel techniques and/or comprehensive empirical validation applicable to real-world software. We successfully attracted more than 70 submissions covering diverse hot topics. After rigorous evaluations by hard-working reviewers, possibly with recommendations for major and minor revisions, we have published 26 articles in five issues of the IEEE Transactions on Reliability in June, September, and December 2018, January 2019, and June 2021. The articles represent a comprehensive cross section of testing and analysis techniques, as well as a wide variety of applications to practical projects. The present retrospective provides readers with interesting details about our great success and a small challenge.

Existing test case prioritization (TCP) techniques have limitations when applied to real-world projects, because these techniques require certain information to be made available before they can be applied. For example, the family of input-based TCP techniques are based on test case values or test script strings; other techniques use test coverage, test history, program structure, or requirements information. Existing techniques also cannot guarantee to always be more effective than random prioritization (RP) that does not have any precondition. As a result, RP remains the most applicable and most fundamental TCP technique. This article proposes an extremely simple, effective, and efficient way to prioritize test cases through the introduction of a dispersity metric. Our technique is as applicable as RP. We conduct empirical studies using 43 different versions of 15 real-world projects. Empirical results show that our technique is more effective than RP. Our algorithm has a linear computational complexity and, therefore, provides a practical solution to the problem of prioritizing very large test suites (such as those containing hundreds of thousands, or millions, of test cases), where the execution time of conventional nonlinear prioritization algorithms can be prohibitive. Our technique also provides a practical solution to TCP when neither input-based nor execution-based techniques are applicable due to lack of information.

We propose a robustness testing approach for software systems that process large amounts of data. Our method uses metamorphic relations to check software output for erroneous input in the absence of a tangible test oracle. We use this technique to test two major citation database systems: Scopus and the Web of Science. We report a surprising finding that the inclusion of hyphens in paper titles impedes citation counts, and that this is a result of the lack of robustness of the citation database systems in handling hyphenated paper titles. Our results are valid for the entire literature as well as for individual fields such as chemistry. We further find a strong and significant negative correlation between the journal impact factor (JIF) of IEEE Transactions on Software Engineering (TSE) and the percentage of hyphenated paper titles published in TSE. Similar results are found for ACM Transactions on Software Engineering and Methodology. A software engineering field-wide study reveals that the higher JIF-ranked journals are publishing a lower percentage of papers with hyphenated titles. Our results challenge the common belief that citation counts and JIFs are reliable measures of the impact of papers and journals, as they can be distorted simply by the presence of hyphens in paper titles.

CUDA is a parallel computing platform and programming model for the graphics processing unit (GPU) of NVIDIA. With CUDA programming, general purpose computing on GPU (GPGPU) is possible. However, the correctness of CUDA programs relies on the correctness of CUDA compilers, which is difficult to test due to its complexity. In this work, we propose CUDAsmith, a fuzzing framework for CUDA compilers. Our tool can randomly generate deterministic and valid CUDA kernel code with several different strategies. Moreover, it adopts random differential testing and EMI testing techniques to solve the test oracle problems of CUDA compiler testing. In particular, we lift live code injection to CUDA compiler testing to help generate EMI variants. Our fuzzing experiments with both the NVCC compiler and the Clang compiler for CUDA have detected thousands of failures, some of which have been confirmed by compiler developers. Finally, the cost-effectiveness of CUDAsmith is also thoroughly evaluated in our fuzzing experiment.

Deep neural networks (DNNs) have been widely used in classification tasks. Studies have shown that DNNs may be fooled by artificial examples known as adversaries. A common technique for testing the robustness of a classification is to apply perturbations (such as random noise) to existing examples and try many of them iteratively, but it is very tedious and time-consuming. In this paper, we propose a technique to select adversaries more effectively. We study the vulnerability of examples by exploiting their class distinguishability. In this way, we can evaluate the probability of generating adversaries from each example, and prioritize all the examples accordingly. We have conducted an empirical study using a classic DNN model on four common datasets. The results reveal that the vulnerability of examples has a strong relationship with distinguishability. The effectiveness of our technique is demonstrated through 98.90 to 99.68% improvements in the F-measure.

Adaptive random testing (ART) was developed as an enhanced version of random testing to increase the effectiveness of detecting failures in programs by spreading the test cases evenly over the input space. However, heavy computation may be incurred. In this paper, three enhanced algorithms for fixed-size-candidate-set ART (FSCS-ART) are proposed based on the k-dimensional tree (KD-tree) structure. The first algorithm Naive-KDFC constructs a KD-tree by splitting the input space with respect to every dimension successively in a round-robin fashion. The second algorithm SemiBal-KDFC improves the balance of the KD-tree by prioritizing the splitting according to the spread in each dimension. In order to control the number of traversed nodes in backtracking, the third algorithm LimBal-KDFC introduces an upper bound for the nodes involved. Simulation and empirical studies have been conducted to investigate the efficiency and effectiveness of the three algorithms. The experimental results show that these algorithms significantly reduce the computation time of the original FSCS-ART for low dimensions and for the case of high dimensions with low failure rates. The efficiency of SemiBal-KDFC is better than that of Naive-KDFC when the dimension is no more than 8, but LimBal-KDFC is the most efficient of all three. Although the limited backtracking leads only to an approximate nearest neighbor in LimBal-KDFC, its failure-detection effectiveness is, in fact, better than FSCS-ART in high-dimensional input spaces and has no significant deterioration in low-dimensional spaces.

Malicious software poses serious threats to our lives, and the activity to detect malware is becoming more and more important. An effective approach is to train a classifier using known software samples and malware samples, and recognize malware from new software. To do that, a recent popular trend is to use OpCode, which is extracted from executable modules, as an expression of software entities to drive machine learning. However, we found that the effectiveness of such a framework highly suffers from having insufficient samples, which is caused by the low success rate of disassembly due to the intrinsic complexity of the problem. In this paper, we propose to increase the success rate of disassembly by allowing inaccurate disassembling, with the attempt to increase the number of successful disassembled samples to improve OpCode-driven malware detection. We built a lightweight disassembler D-light based on the linear swap disassembly method to avoid known issues with the recursive descent manner of IDA Pro. We carried out experiment to evaluate the performance, effectiveness, and other design factors of adopting D-light and IDA Pro as disassemblers for malware detection. The empirical study shows the D-light is both more efficient and more effective than IDA Pro in supporting malware detection.

Effective testing is essential for assuring software quality. While regression testing is time-consuming, the fault detection capability may be compromised if some test cases are discarded. Test case prioritization is a viable solution. To the best of our knowledge, the most effective test case prioritization approach is still the additional greedy algorithm, and existing search-based algorithms have been shown to be visually less effective than the former algorithms in previous empirical studies. This paper proposes a novel Proportion-Oriented Randomized Algorithm (PORA) for test case prioritization. PORA guides test case prioritization by optimizing the distance between the prioritized test suite and a hierarchy of distributions of test input data. Our experiment shows that PORA test case prioritization techniques are as effective as, if not more effective than, the total greedy, additional greedy, and ART techniques, which use code coverage information. Moreover, the experiment shows that PORA techniques are more stable in effectiveness than the others.

Developing software systems to fulfill the requirements of various stakeholders is by no means a simple matter. Quality assurance is required in each phase of the software engineering process including requirements elicitation, software architecture design, program design, implementation, testing, and debugging, because every phase is closely linked with another. The quality of the artifacts from each development phase impacts on the rest of the system. The international conference series on quality software has a long tradition of bringing together researchers and practitioners to present and discuss innovative methods of assuring software quality. The 13th International Conference on Quality Software (QSIC 2013) was held in Nanjing, China, on July 29–30, 2013. The main theme was on the quality of evolving software. We emphasized a holistic view of quality assurance across different phases and aspects of software engineering. QSIC 2013 was technically sponsored by the IEEE Reliability Society. Jian Lv was the General Chair. Arnaud Gotlieb and Zhenyu Chen served as the Program Chairs. The keynote speakers were Mauro Pezzè of Università della Svizzera Italiana, Switzerland, and Magne Jorgensen of Simula Research Laboratory, Norway. Seventy-eight submissions from 21 countries were received. Nineteen regular papers were accepted, representing an acceptance rate of 24%. We had an industry track where experience reports from practitioners were presented. Roberto Bagnara of University of Parma, Italy, cofounder of BUGSENG, was the invited industry speaker. In addition, The Symposium on Engineering Test Harness (TSETH 2013), the workshop on Testing and Verification of Embedded Computing Systems (TVECS 2013), the workshop on Quality and Measurement of Software Model-Driven Developments (QUAMES 2013), and the workshop on Software Quality Assurance of Healthcare System and Embedded System (SQHE 2013) were also held. The proceedings of QSIC 2013 was published by the IEEE Computer Society. We shortlisted six papers from the main conference and invited the authors to submit extended versions to this Focus Section on Quality Software in Software: Practice and Experience. Two papers were accepted after going through up to three rounds of rigorous reviews involving two anonymous reviewers for each article. Automated tools are essential for every stage of the system development life cycle to support the computer-aided software engineering process. There is an abundance of tools to be selected for the different phases. Comparing their effectiveness and the ability to integrate with one another is a nontrivial task. The first paper, entitled ‘Selecting a Software Engineering Tool: Lessons Learnt from Mutation Analysis’ by Mickaël Delahaye and Lydie du Bousquet, studies the comparison and choice of mutation analysis tools as an illustration of their proposed methodology for tool selection. Mutation analysis involves the seeding of faults into programs under test and verifies whether the test suites can detect such faults. Mutation tools vary in the fault models used and their performance in regard to such issues as fault generation and test suite execution. The authors propose a list of comparison criteria for such tools and a list of usage profiles. They find the listing of criteria to be straightforward, but their appraisals to be much harder. They have evaluated the mutation tools for the Java platform. Generalizations to other platforms and other tools are also discussed. This paper is of interest to software testers working on mutation analysis as well as software developers who need to choose which automated tools to use. Safety requirements are crucial to every development phase of an avionic system. The second paper, entitled ‘A Modeling Methodology to Facilitate Safety-Oriented Architecture Design of Industrial Avionics Software’ by Ji Wu, Tao Yue, Shaukat Ali, and Huihui Zhang, presents a safety-oriented architecture modeling methodology to enforce adherence of the avionic system under development to published standards and industrial practices. The authors propose a UML profile to define the safety requirements in terms of a component-based architecture, a modeling environment to assure the implementation of such requirements, and design guidelines including objectives and processes for applying the model. The safety requirements are based on the DO-178B/C standard as well as a systematic domain analysis of current engineering practices. To evaluate the methodology, it has been applied to an industrial autopilot system. All the stereotypes in the safety profile have been verified. Thirty-two safety properties have been identified and are checked between the formal UML profile and the architectural model. Six faults previously unrevealed have been identified. This paper should be of interest not only to developers of avionics software but also serve as a good reference to others who are concerned about safety-critical systems. Finally, we would like to thank the editors of Software: Practice and Experience for kindly agreeing to publish this focus section.

Many composite workflow services utilize non-imperative XML technologies such as WSDL, XPath, XML schema, and XML messages. Regression testing should assure the services against regression faults that appear in both the workflows and these artifacts. In this paper, we propose a refinement-oriented level-exploration strategy and a multilevel coverage model that captures progressively the coverage of different types of artifacts by the test cases. We show that by using them, the test case prioritization techniques initialized on top of existing greedy-based test case prioritization strategy form a subsumption hierarchy such that a technique can produce more test suite permutations than a technique that subsumes it. Our experimental study of a model instance shows that a technique generally achieves a higher fault detection rate than a subsumed technique, which validates that the proposed hierarchy and model have the potential to improve the cost-effectiveness of test case prioritization techniques.

An external web service may evolve without prior notification. In the course of the regression testing of a workflow-based web service, existing test case prioritization techniques may only verify the latest service composition using the not-yet-executed test cases, overlooking high-priority test cases that have already been applied to the service composition before the evolution. In this paper, we propose Preemptive Regression Testing (PRT), an adaptive testing approach to addressing this challenge. Whenever a change in the coverage of any service artifact is detected, PRT recursively preempts the current session of regression test and creates a sub-session of the current test session to assure such lately identified changes in coverage by adjusting the execution priority of the test cases in the test suite. Then, the sub-session will resume the execution from the suspended position. PRT terminates only when each test case in the test suite has been executed at least once without any preemption activated in between any test case executions. The experimental result confirms that testing workflow-based web service in the face of such changes is very challenging; and one of the PRT-enriched techniques shows its potential to overcome the challenge.

Applications written by end-user programmers are hardly energy-optimized by these programmers. The end users of such applications thus suffer significant energy issues. In this paper, we propose CrowdAdaptor, a novel approach toward locating energy-efficient configurations to execute the applications hosted in virtual machines on handheld devices. CrowdAdaptor innovatively makes use of the development artifacts (test cases) and the very large installation base of the same application to distribute the test executions and performance data collection of the whole test suites against many different virtual machine configurations among these installation bases. It synthesizes these data, continuously discovers better energy-efficient configurations, and makes them available to all the installations of the same applications. We report a multi-subject case study on the ability of the framework to discover energy-efficient configurations in three power models. The results show that Crowd Adaptor can achieve up to 50% of energy savings based on a conservative linear power model.

In real life, a tester can only afford to apply one test case prioritization technique to one test suite against a service-oriented workflow application once in the regression testing of the application, even if it results in an adverse scenario such that the actual performance in the test session is far below the average. It is unclear whether the factors of test case prioritization techniques known to be significant in terms of average performance can be extrapolated to adverse scenarios. In this paper, we examine whether such a factor or technique may consistently affect the rate of fault detection in both the average and adverse scenarios. The factors studied include prioritization strategy, artifacts to provide coverage data, ordering direction of a strategy, and the use of executable and non-executable artifacts. The results show that only a minor portion of the 10 studied techniques, most of which are based on the iterative strategy, are consistently effective in both average and adverse scenarios. To the best of our knowledge, this paper presents the first piece of empirical evidence regarding the consistency in the effectiveness of test case prioritization techniques and factors of service-oriented workflow applications between average and adverse scenarios.

Context-aware pervasive software is responsive to various contexts and their changes. A faulty implementation of the context-aware features may lead to unpredictable behavior with adverse effects. In software testing, one of the most important research issues is to determine the sufficiency of a test suite to verify the software under test. Existing adequacy criteria for testing traditional software, however, have not explored the dimension of serial test inputs and have not considered context changes when constructing test suites. In this article, we define the concept of context diversity to capture the extent of context changes in serial inputs and propose three strategies to study how context diversity may improve the effectiveness of the data-flow testing criteria. Our case study shows that the strategy that uses test cases with higher context diversity can significantly improve the effectiveness of existing data-flow testing criteria for context-aware pervasive software. In addition, test suites with higher context diversity are found to execute significantly longer paths, which may provide a clue that reveals why context diversity can contribute to the improvement of effectiveness of test suites.

Software systems today are large and complex. At the same time, the time to market is extremely short because of competition. As a result, program debugging for real-life systems is very difficult. In general, the debugging process consists of three tasks, namely, fault localization, fault repair, and retesting. In particular, fault localization is generally considered to be the most challenging. It is recognized as time-consuming and tedious if conducted manually. On the other hand, formal methods suffer from scalability problems, and static techniques are imprecise. Automatic statistical fault localization techniques are regarded as the most promising option. They compare passed and failed executions of a faulty program and produce a suspiciousness ranking of program entities (such as statements or predicates). Developers may then follow up with the list sequentially to identify program faults. Unfortunately, although a large number of statistical fault localization techniques are available, they have not reached the maturity to pinpoint accurately and precisely the locations of faults. Also, the recording and replaying of passed and failed executions as well as fault repair without introducing new bugs remain unresolved issues. Furthermore, researchers often make unrealistic assumptions, and software subjects under study do not necessarily reflect the fault characteristics of large industrial applications. There is plenty of room for improvement. The 2nd International Workshop on Program Debugging (IWPD 2011) was a full day workshop held in conjunction with the 35th Annual International Computer Software and Applications Conference (COMPSAC 2011) in Munich, Germany in July 2011. It serves as a platform for researchers and practitioners to exchange ideas, present new advancements, and identify further challenges in program debugging. It brings to light the latest challenges and advances in research and practice in program debugging, with a special emphasis on methodology, technology, and environment. Two keynote speeches were given by internationally renowned researchers — T. Y. Chen of Swinburne University of Technology, Australia and W. K. Chan of City University of Hong Kong, Hong Kong. There were also sessions for paper presentations and panel discussions. We shortlisted three papers from the workshop and invited the authors to submit an extended version to Software: Practice and Experience. Two papers were accepted for this focus section after going through two rounds of rigorous reviews involving two to three anonymous reviewers for each article. Both accepted papers address the important area of statistical fault location. The first paper, entitled ‘In quest of the science in statistical fault localization’ by W. K. Chan and Yan Cai, is an extended version of the keynote speech delivered by the first author in IWPD 2011. A vital element in research is to know the shortcomings of the current state of the art. In this paper, the authors conduct a critical review of existing work on statistical fault localization (including their own), highlight misconceptions and unnecessary assumptions, and provide remedial measures to rectify such malpractices. The authors point out that a lot of current research in statistical fault localization does not consider coincidental correctness, which means that the execution of a faulty statement may not necessarily lead to a program failure, even though this important concept has been known to software testers for decades. Also, existing fault localization techniques compare the similarities and dissimilarities between passed and failed executions to locate faults. These similarity coefficients estimate the probability that a particular program entity causes a failure, but ignore the noise caused by other entities. The authors point out the importance of a noise-reduction mechanism for the similarity coefficients. Another issue is that existing researchers often assume that they are dealing with large samples, where the central limit theorem applies. Empirical studies by the authors show that this assumption is often invalid. It is unrealistic to expect the availability of execution profiles with thousands of test verdicts for the average programs. A developer needs to debug a program even if a small number of failures have been revealed. When the number of samples is small, nonparametric statistical techniques should be applied. The authors conclude the paper by giving an insightful summary of the challenges in statistical fault localization that may benefit researchers in software engineering and related software areas. The second paper is entitled ‘A consensus-based strategy to improve the quality of fault localization’ by Vidroha Debroy and W. Eric Wong. Quite a number of statistical fault localization techniques have been proposed. Each of them claims to be superior to others in one aspect or another using different data sets. There is, however, no single technique that is definitely better than others in all aspects. In this paper, the authors put forward an integrated approach to address the issue. Rather than proposing yet another new technique that captures the more promising features of existing techniques, the authors propose a consensus-based strategy, which combines the rankings of several techniques. Using the Borda method, a consolidated ranking is produced by integrating various statement rankings that result from individual techniques. The scale of the proposed approach can be easily extended or retracted because new fault localization techniques can be added by the inclusion of their rankings, or existing techniques can be excluded by the removal of their rankings. Also, because different techniques operate on the same input data set, the overhead of the consensus is minimal. The overall ranking can be determined in linear time. The effectiveness of the consensus-based approach has been validated using three popular fault localization techniques (Tarantula, Ochiai, and H3) on the Siemens suite of programs as well as the Ant, grep, gzip, make, and space programs. The empirical study shows that the performance of the proposed approach is close to the best results of the techniques under study. Finally, I would like to thank Professor Nigel Horspool and Professor Andy Wellings, Editors of Software: Practice and Experience, for kindly agreeing to publish this focus section.

Algebraic specifications have been used in the testing of object-oriented programs and received much attention since the 1990s. It is generally believed that class-level testing based on algebraic specifications involves two independent aspects: the testing of equivalent and nonequivalent ground terms. Researchers have cited intuitive examples to illustrate the philosophy that even if an implementation satisfies all the requirements specified by the equivalence of ground terms, it may still fail to satisfy some of the requirements specified by the nonequivalence of ground terms. Thus, both the testing of equivalent ground terms and the testing of nonequivalent ground terms have been considered as significant and cannot replace each other. In this paper, we present an innovative finding that, given any canonical specification of a class with proper imports, a complete implementation satisfies all the observationally equivalent ground terms if and only if it satisfies all the observationally nonequivalent ground terms. As a result, these two aspects of software testing cover each other and can therefore replace each other. These findings provide a deeper understanding of software testing based on algebraic specifications, rendering the theory more elegant and complete. We also highlight a couple of important practical implications of our theoretical results.

A workflow-based web service may use ultra-late binding to invoke external web services to concretize its implementation at run time. Nonetheless, such external services or the availability of recently used external services may evolve without prior notification, dynamically triggering the workflow-based service to bind to new replacement external services to continue the current execution. Any integration mismatch may cause a failure. In this paper, we propose Preemptive Regression Testing (PRT), a novel testing approach that addresses this adaptive issue. Whenever such a late-change on the service under regression test is detected, PRT preempts the currently executed regression test suite, searches for additional test cases as fixes, runs these fixes, and then resumes the execution of the regression test suite from the preemption point.

Dynamic race detectors can explore multiple thread schedules of a multithreaded program over the same input to detect data races. Although existing sampling-based precise race detectors reduce overheads effectively so that lightweight precise race detection can be performed in testing or post-deployment environments, they are ineffective in detecting races if the sampling rates are low. This paper presents CARISMA to address this problem. CARISMA exploits the insight that along an execution trace, a program may potentially handle many accesses to the memory locations created at the same site for similar purposes. Iterating over multiple execution trials of the same input, CARISMA estimates and distributes the sampling budgets among such location creation sites, and probabilistically collects a fraction of all accesses to the memory locations associated with such sites for subsequent race detection. Our experiment shows that, compared with PACER on the same platform and at the same sampling rate (such as 1%), CARISMA is significantly more effective.

SUMMARY Search services are the main interface through which people discover information on the Internet. A fundamental challenge in testing search services is the lack of oracles. The sheer volume of data on the Internet prohibits testers from verifying the results. Furthermore, it is difficult to objectively assess the ranking quality because different assessors can have very different opinions on the relevance of a Web page to a query. This paper presents a novel method for automatically testing search services without the need of a human oracle. The experimental findings reveal that some commonly used search engines, including Google, Yahoo!, and Live Search, are not as reliable as what most users would expect. For example, they may fail to find pages that exist in their own repositories, or rank pages in a way that is logically inconsistent. Suggestions are made for search service providers to improve their service quality. Copyright © 2010 John Wiley & Sons, Ltd.

This paper extends the choce relation framework, abbreviated as choc'late, which assists software testers in the application of category/choice methods to testing. choc'late assumes that the tester is able to construct a single choice relation table from the entire specification; this table then forms the basis for test case generation using the associated algorithms. This assumption, however, may not hold true when the specification is complex and contains many specification components. For such a specification, the tester may construct a preliminary choice relation table from each specification component, and then consolidate all the preliminary tables into a final table to be processed by choc'late for test case generation. However, it is often difficult to merge these preliminary tables because such merging may give rise to inconsistencies among choice relations or overlaps among choices. To alleviate this problem, we introduce a DividE-and-conquer methodology for identifying categorieS, choiceS, and choicE Relations for Test case generation, abbreviated as dessert. The theoretical framework and the associated algorithms are discussed. To demonstrate the viability and effectiveness of our methodology, we describe case studies using the specifications of three real-life commercial software systems.

Statistical fault localization techniques find suspicious faulty program entities in programs by comparing passed and failed executions. Existing studies show that such techniques can be promising in locating program faults. However, coincidental correctness and execution crashes may make program entities indistinguishable in the execution spectra under study, or cause inaccurate counting, thus severely affecting the precision of existing fault localization techniques. In this paper, we propose a Block Rank technique, which calculates, contrasts, and propagates the mean edge profiles between passed and failed executions to alleviate the impact of coincidental correctness. To address the issue of execution crashes, Block Rank identifies suspicious basic blocks by modeling how each basic block contributes to failures by apportioning their fault relevance to surrounding basic blocks in terms of the rate of successful transition observed from passed and failed executions. Block Rank is empirically shown to be more effective than nine representative techniques on four real-life medium-sized programs.

SUMMARY Model‐based testing helps test engineers automate their testing tasks so that they are more cost‐effective. When the model is changed because of the evolution of the specification, it is important to maintain the test suites up to date for regression testing. A complete regeneration of the whole test suite from the new model, although inefficient, is still frequently used in the industry, including Microsoft. To handle specification evolution effectively, we propose a test case reusability analysis technique to identify reusable test cases of the original test suite based on graph analysis. We also develop a test suite augmentation technique to generate new test cases to cover the change‐related parts of the new model. The experiment on four large protocol document testing projects shows that our technique can successfully identify a high percentage of reusable test cases and generate low‐redundancy new test cases. When compared with a complete regeneration of the whole test suite, our technique significantly reduces regression testing time while maintaining the stability of requirement coverage over the evolution of requirements specifications. Copyright © 2011 John Wiley & Sons, Ltd.

An early step for most black-box testing methods is to identify a set of categories and choices (or their equivalents) from the specification. The identification is often performed in an ad hoc manner, thus the quality of categories and choices is in doubt. Poorly identified categories and choices will affect the comprehensiveness of test cases. In this paper, we describe several comparative studies using three commercial specifications and discuss the major results. The objectives of our studies are (a) to investigate the differences in the types and amounts of mistakes made between inexperienced and experienced software testers in an ad hoc identification approach and (b) to determine the extent of mistake reduction after discussing the mistakes with the software testers and providing them with an identification checklist.

We present an integrated method for program proving, testing, and debugging. Using the concept of metamorphic relations, we select necessary properties for target programs. For programs where global symbolic evaluation can be conducted and the constraint expressions involved can be solved, we can either prove that these necessary conditions for program correctness are satisfied or identify all inputs that violate the conditions. For other programs, our method can be converted into a symbolic-testing approach. Our method extrapolates from the correctness of a program for tested inputs to the correctness of the program for related untested inputs. The method supports automatic debugging through the identification of constraint expressions that reveal failures.

Tabular expressions have been proposed as a notation to document mathematically precise but readable software specifications. One of the many roles of such documentation is to guide testers. This paper 1) explores the application of four testing strategies (the partition strategy, decision table-based testing, the basic meaningful impact strategy, and fault-based testing) to tabular expression-based specifications, and 2) compares the strategies on a mathematical basis through formal and precise definitions of the subsumption relationship. We also compare these strategies through experimental studies. These results will help researchers improve current methods and will enable testers to select appropriate testing strategies for tabular expression-based specifications.

Dynamic service compositions pose new verification and validation challenges such as uncertainty in service membership. Moreover, applying an entire test suite to loosely coupled services one after another in the same composition can be too rigid and restrictive. In this paper, we investigate the impact of service selection on service-centric testing techniques. Specifically, we propose to incorporate service selection in executing a test suite and develop a suite of metrics and test case prioritization techniques for the testing of location-aware services. A case study shows that a test case prioritization technique that incorporates service selection can outperform their traditional counterpart - the impact of service selection is noticeable on software engineering techniques in general and on test case prioritization techniques in particular. Further-more, we find that points-of-interest-aware techniques can be significantly more effective than input-guided techniques in terms of the number of invocations required to expose the first failure of a service composition.

Abstract Mesh simplification programs create three‐dimensional polygonal models similar to an original polygonal model, and yet use fewer polygons. They produce different graphics even though they are based on the same original polygonal model. This results in a test oracle problem. To address the problem, our previous work has developed a technique that uses a reference model of the program under test to train a classifier. Using such an approach may mistakenly mark a failure‐causing test case as passed. It lowers the testing effectiveness of revealing failures. This paper suggests piping the test cases marked as passed by a statistical pattern classification module to an analytical metamorphic testing (MT) module. We evaluate our approach empirically using three subject programs with over 2700 program mutants. The result shows that, using a resembling reference model to train a classifier, the integrated approach can significantly improve the failure detection effectiveness of the pattern classification approach. We also explain how MT in our design trades specificity for sensitivity. Copyright © 2009 John Wiley & Sons, Ltd.

Regression testing assures changed programs against unintended amendments. Rearranging the execution order of test cases is a key idea to improve their effectiveness. Paradoxically, many test case prioritization techniques resolve tie cases using the random selection approach, and yet random ordering of test cases has been considered as ineffective. Existing unit testing research unveils that adaptive random testing (ART) is a promising candidate that may replace random testing (RT). In this paper, we not only propose a new family of coverage-based ART techniques, but also show empirically that they are statistically superior to the RT-based technique in detecting faults. Furthermore, one of the ART prioritization techniques is consistently comparable to some of the best coverage-based prioritization techniques (namely, the "additional" techniques) and yet involves much less time cost.

Service computing has increasingly been adopted by the industry, developing business applications by means of orchestration and choreography. Choreography specifies how services collaborate with one another by defining, say, the message exchange, rather than via the process flow as in the case of orchestration. Messages sent from one service to another may require the use of different XPaths to manipulate or extract message contents. Mismatches in XML manipulations through XPaths (such as to relate incoming and outgoing messages in choreography specifications) may result in failures. In this paper, we propose to associate XPath Rewriting Graphs (XRGs), a structure that relates XPath and XML schema, with actions of choreography applications that are skeletally modeled as labeled transition systems. We develop the notion of XRG patterns to capture how different XRGs are related even though they may refer to different XML schemas or their tags. By applying XRG patterns, we successfully identify new data flow associations in choreography applications and develop new data flow testing criteria. Finally, we report an empirical case study that evaluates our techniques. The result shows our techniques are promising in detecting failures in choreography applications.

Coverage-based fault-localization techniques find the fault-related positions in programs by comparing the execution statistics of passed executions and failed executions. They assess the fault suspiciousness of individual program entities and rank the statements in descending order of their suspiciousness scores to help identify faults in programs. However, many such techniques focus on assessing the suspiciousness of individual program entities but ignore the propagation of infected program states among them. In this paper, we use edge profiles to represent passed executions and failed executions, contrast them to model how each basic block contributes to failures by abstractly propagating infected program states to its adjacent basic blocks through control flow edges. We assess the suspiciousness of the infected program states propagated through each edge, associate basic blocks with edges via such propagation of infected program states, calculate suspiciousness scores for each basic block, and finally synthesize a ranked list of statements to facilitate the identification of program faults. We conduct a controlled experiment to compare the effectiveness of existing representative techniques with ours using standard bench-marks. The results are promising.

Peer services depend on one another to accomplish their tasks, and their structures may evolve. A service composition may be designed to replace its member services whenever the quality of the composite service fails to meet certain quality-of-service (QoS) requirements. Finding services and service invocation endpoints having the greatest impact on the quality are important to guide subsequent service adaptations. This paper proposes a technique that samples the QoS of composite services and continually analyzes them to identify artifacts for service adaptation. The preliminary results show that our technique has the potential to effectively find such artifacts in services.

Regression testing assures the quality of modified service-oriented business applications against unintended changes. However, a typical regression test suite is large in size. Earlier execution of those test cases that may detect failures is attractive. Many existing prioritization techniques order test cases according to their respective coverage of program statements in a previous version of the application. On the other hand, industrial service-oriented business applications are typically written in orchestration languages such as WS-BPEL and integrated with workflow steps and web services via XPath and WSDL. Faults in these artifacts may cause the application to extract wrong data from messages, leading to failures in service compositions. Surprisingly, current regression testing research hardly considers these artifacts. We propose a multilevel coverage model to capture the business process, XPath, and WSDL from the perspective of regression testing. We develop a family of test case prioritization techniques atop the model. Empirical results show that our techniques can achieve significantly higher rates of fault detection than existing techniques.

Cloud computing is an emerging computing paradigm. It aims to share data, calculations, and services transparently among users of a massive grid. Although the industry has started selling cloud-computing products, research challenges in various areas, such as UI design, task decomposition, task distribution, and task coordination, are still unclear. Therefore, we study the methods to reason and model cloud computing as a step toward identifying fundamental research questions in this paradigm. In this paper, we compare cloud computing with service computing and pervasive computing. Both the industry and research community have actively examined these three computing paradigms. We draw a qualitative comparison among them based on the classic model of computer architecture. We finally evaluate the comparison results and draw up a series of research questions in cloud computing for future exploration.

Tabular expressions have been used in industry for many years to precisely document software in a readable notation. In this paper, we propose a fault-based testing technique that traces the propagation of faults from the expression in each cell of a tabular expression to the output of the program under test. The technique has been formalized in the form of abstract test case constraints also represented by tabular expressions, so that it can be easily applied and automated.

Predicate-based statistical fault-localization techniques locate fault-relevant predicates in a program by contrasting the statistics of the values of individual predicates between successful and failure-causing runs. While short-circuit evaluations are common in program execution, treating predicates as atomic units ignores this fact, masking out various types of important statistics. On the contrary, are such statistics useful for debugging? In this paper, we investigate experimentally the impact of the use of short-circuit evaluation information on fault localization. The results show that, by doing so, it significantly improves predicate-based statistical fault-localization techniques.

Pervasive computing software adapts its behavior according to the changing contexts. Nevertheless, contexts are often noisy. Context inconsistency resolution provides a cleaner pervasive computing environment to context-aware applications. A faulty context-aware application may, however, mistakenly mix up inconsistent contexts and resolved ones, causing incorrect results. This paper studies how such faulty context-aware applications may be affected by these services. We model how programs should handle contexts that are continually checked and resolved by context inconsistency resolution, develop novel sets of data flow equations to analyze the potential impacts, and thus formulate a new family of test adequacy criteria for testing these applications. Experimentation shows that our approach is promising.

WS-BPEL applications are a kind of service-oriented application. They use XPath extensively to integrate loosely-coupled workflow steps. However, XPath may extract wrong data from the XML messages received, resulting in erroneous results in the integrated process. Surprisingly, although XPath plays a key role in workflow integration, inadequate researches have been conducted to address the important issues in software testing. This paper tackles the problem. It also demonstrates a novel transformation strategy to construct artifacts. We use the mathematical definitions of XPath constructs as rewriting rules, and propose a data structure called XPath Rewriting Graph (XRG), which not only models how an XPath is conceptually rewritten but also tracks individual rewritings progressively. We treat the mathematical variables in the applied rewriting rules as if they were program variables, and use them to analyze how information may be rewritten in an XPath conceptually. We thus develop an algorithm to construct XRGs and a novel family of data flow testing criteria to test WS-BPEL applications. Experiment results show that our testing approach is promising.

In service computing, the behavior of a service may evolve. When an organization develops a service-oriented application in which certain services are provided by external partners, the organization should address the problem of uninformed behavior evolution of external services. This paper proposes an adaptive framework that bars problematic external services to be used in the service-oriented application of an organization. We use dynamic WSDL information in public service registries to approximate a snapshot of a network of services, and apply link analysis on the snapshot to identify services that are popularly used by different service consumers at the moment. As such, service composition can be strategically formed using the highly referenced services. We evaluate our proposal through a simulation study. The results show that, in terms of the number of failures experienced by service consumers, our proposal significantly outperforms the random approach in selecting reliable services to form service compositions.

Mesh simplification is a mainstream technique to render graphics responsively in modern graphical software. However, the graphical nature of the output poses a test oracle problem in testing. Previous work uses pattern classification to identify failures. Although such an approach may be promising, it may conservatively mark the test result of a failure-causing test case as passed. This paper proposes a methodology that pipes the test cases marked as passed by the pattern classification component to a metamorphic testing component to look for missed failures. The empirical study uses three simple and general metamorphic relations as subjects, and the experimental results show a 10 percent improvement of effectiveness in the identification of failures.

Testing is an important means to ensure the quality of software systems. Contract specification can be used to formally specify the cluster level of object-oriented software, which can then be tested using TACCLE, an advanced methodology for object-oriented testing. The use of formal specifications as a testing base has many advantages. However, such specifications are not easily understood and therefore not widely used in the software industry. On the other hand, UML, a semi-formal modeling language, is becoming increasingly popular and widely accepted. In particular, UML interaction diagrams specify the dynamic, interacting behavior among the objects of an object-oriented system. If the transformation of UML interaction diagrams into Contract specifications can be automated, the TACCLE methodology can be applied directly to test object-oriented software at the cluster level. In this paper, a method to transform UML interaction diagrams into contract specifications is proposed based on the UML meta- model. A prototype has been developed.

Software with graphics rendering is an important class of applications. Many of them use polygonal models to represent the graphics. Mesh simplification is a vital technique to vary the levels of object details and, hence, improve the overall performance of the rendering process. It progressively enhances the effectiveness of rendering from initial reference systems. As such, the quality of its implementation affects that of the associated graphics rendering application. Testing of mesh simplification is essential towards assuring the quality of the applications. Is it feasible to use the reference systems to serve as automated test oracles for mesh simplification programs? If so, how well are they useful for this purpose? We present a novel approach in this paper. We propose to use pattern classification techniques to address the above problem. We generate training samples from the reference system to test samples from the implementation. Our experimentation shows that the approach is promising

Pervasive context-aware software is an emerging kind of application. Many of these systems register parts of their context-aware logic in the middleware. On the other hand, most conventional testing techniques do not consider such kind of application logic. This paper proposes a novel family of testing criteria to measure the comprehensiveness of their test sets. It stems from context-aware data flow information. Firstly, it studies the evolution of contexts, which are environmental information relevant to an application program. It then proposes context-aware data flow associations and testing criteria. Corresponding algorithms are given. It uses a prototype testing tool to conduct experimentation on an RFID-based location sensing software running on top of context-aware middleware. The experimental results show that our approach is applicable, effective, and promising.

During the testing of context-sensitive middleware-based software, the middleware checks the current situation to invoke the appropriate functions of the applications. Since the middleware remains active and the situation may continue to evolve, however, the conclusion of some test cases may not easily be identified. Moreover, failures appearing in one situation may be superseded by subsequent correct outcomes and, therefore, be hidden. We alleviate the above problems by making use of a special kind of situation, which we call checkpoints, such that the middleware will not activate the functions under test. We recommend testers to generate test cases that start at a checkpoint and end at another. Testers may identify relations that associate different execution sequences of a test case. They then check the results of each test case to detect any contravention of such relations. We illustrate our technique with an example that shows how hidden failures can be detected. We also report the experimentation carried out on an RFID-based location-sensing application on top of a context-sensitive middleware.

Model-based software testing generally refers to test case selection and result evaluation based on a behavioral model of the target software. It may not, however, be possible to evaluate test results in some situations. For embedded software in a real-time environment, for instance, the results may only appear in a fraction of a second and cannot be observed by the tester. In this paper, we discuss the research opportunities for such situations despite the challenges.

The Software Engineering volume by the IEEE Computer Society/ACM Joint Task Force on Computing Curricula, otherwise known as the Computing Curriculum - Software Engineering (CCSE), has been finalized and approved. This work comments on the impacts of the volume on professional software engineering education.

Context-sensitive middleware-based software is an emerging kind of ubiquitous computing application. The components of such software communicate proactively among themselves according to the situational attributes of their environments, known as the "contexts". The actual process of accessing and updating the contexts lies with the middleware. The latter invokes the relevant local and remote operations whenever any context inscribed in the situation-aware interface is satisfied. Since the applications operate in a highly dynamic environment, the testing of context-sensitive software is challenging. Metamorphic testing is a property-based testing strategy. It recommends that, even if a test case does not reveal any failure, follow-up test cases should be further constructed from the original to check whether the software satisfies some necessary conditions of the problem to be implemented. This work proposes to use isotropic properties of contexts as metamorphic relations for testing context-sensitive software. For instance, distinct points on the same isotropic curve of contexts would entail comparable responses by the components. This notion of testing context relations is novel, robust, and intuitive to users.

Testing is the most commonly used approach to the assurance of software quality and reliability. The testing of object-oriented software is much more complex than that of conventional programs. Although we proposed previously a method called TACCLE for testing object-oriented software at the class and cluster levels, it did not cover concurrent or non-deterministic situations. This paper puts forward a strategy for selecting synchronization sequences to test concurrent object-oriented software, including non-deterministic cases. It is based on OBJSA net/CLOWN specifications. Experiments have been carried out in a case study to verify the efficacy of the strategy.

Program testing is the most widely adopted approach for assuring the quality and reliability of software systems. Despite the popularity of the objected-oriented programs, its testing is much more challenging than that of the conventional programs. We proposed previously a methodology known as TACCLE for testing object-oriented software. It has not, however, addressed the aspects of concurrency and non-determinism. In this paper, we propose a scheme for dynamically detecting and testing concurrency in object-oriented software by executing selected concurrent pairs of operations. The scheme is based on OBJSA nets and addresses concurrency and nondeterminism problems. An experimental case study is reported to show the effectiveness of the scheme in detecting deadlocks, race conditions and other coherence problems. The scheme supplements our previous static approach to detecting deadlock in Java multithreaded programs.

We describe in this paper a choice relation framework for supporting category-partition test case generation. We capture the constraints among various values (or ranges of values) of the parameters and environment conditions identified from the specification, known formally as choices. We express these constraints in terms of relations among choices and combinations of choices, known formally as test frames. We propose a theoretical backbone and techniques for consistency checks and automatic deductions of relations. Based on the theory, algorithms have been developed for generating test frames from the relations. These test frames can then be used as the basis for generating test cases. Our algorithms take into consideration the resource constraints specified by software testers, thus maintaining the effectiveness of the test frames (and hence test cases) generated.

We study the effect of applying metamorphic testing to alleviate the oracle problem for numerical programs. We discuss a case study on the testing of a program that solves an elliptic partial differential equation with Dirichlet boundary conditions. We identify a metamorphic relation for the equation and demonstrate the effectiveness of metamorphic testing in identifying the error. The relation identified should also be applicable to other numerical methods that yield better approximations on the refinement of grid points or step sizes.

We present a semi-proving method for verifying necessary conditions for program correctness. Our approach is based on the integration of global symbolic evaluation and metamorphic testing. It is relatively easier than conventional program proving, and helps to alleviate the problem that software testing cannot show the absence of faults.

Although testing is the most popular method for assuring software quality, there are two recognized limitations, known as the reliable test set problem and the oracle problem. Fault-based testing is an attempt by Morell to alleviate the reliable test set problem. In this paper, we propose to enhance fault-based testing to address the oracle problem as well. We present an integrated method that combines metamorphic testing with fault-based testing using real and symbolic inputs.

Object-oriented programming consists of several different levels of abstraction, namely, the algorithmic level, class level, cluster level, and system level. The testing of object-oriented software at the algorithmic and system levels is similar to conventional program testing. Testing at the class and cluster levels poses new challenges. Since methods and objects may interact with one another with unforeseen combinations and invocations, they are much more complex to simulate and test than the hierarchy of functional calls in conventional programs. In this paper, we propose a methodology for object-oriented software testing at the class and cluster levels. In class-level testing, it is essential to determine whether objects produced from the execution of implemented systems would preserve the properties defined by the specification, such as behavioral equivalence and nonequivalence. Our class-level testing methodology addresses both of these aspects. For the testing of behavioral equivalence, we propose to select fundamental pairs of equivalent ground terms as test cases using a black-box technique based on algebraic specifications, and then determine by means of a white-box technique whether the objects resulting from executing such test cases are observationally equivalent. To address the testing of behavioral nonequivalence, we have identified and analyzed several nontrivial problems in the current literature. We propose to classify term equivalence into four types, thereby setting up new concepts and deriving important properties. Based on these results, we propose an approach to deal with the problems in the generation of nonequivalent ground terms as test cases. Relatively little research has contributed to cluster-level testing. In this paper, we also discuss black-box testing at the cluster level. We illustrate the feasibility of using contract, a formal specification language for the behavioral dependencies and interactions among cooperating objects of different classes in a given cluster. We propose an approach to test the interactions among different classes using every individual message-passing rule in the given Contract specification. We also present an approach to examine the interactions among composite message-passing sequences. We have developed four testing tools to support our methodology.

The harmonization of professional standards usually means an attempt to unify the standards among different nations or states. It is a necessary step towards the maturity of a profession because of two factors: (a) that professional standards have been developed independently in different nations; and (b) that the standards thus developed are not uniform among nations. Since harmonization is not the only step before a mature software engineering profession, the author proposes to take a look at various constraints and conflicts against harmonized professional standards in software engineering.

This paper describes an integrated methodology for the construction of test cases from functional specifications using the classification-tree method. It is an integration of our extensions to the classification-hierarchy table, the classification tree construction algorithm, and the classification tree restructuring technique. Based on the methodology, a prototype system ADDICT, which stands for AutomateD test Data generation system using the Integrated Classification-Tree method, has been built.

There are two contradicting ideologies in software engineering (SE) education: one emphasizes popular methods, such as object-oriented analysis and design; the other advocates formal methods, which help to precisely specify and reason with the properties of software systems. Each of them, however, has its own problems. We advocate that the future of SE education lies in integrating these two worlds. SE education should not only be an engineering discipline in name, but also an engineering discipline in substance. SE students should not be artisans who regard their trade as an art and learn only from experience; nor should they be mathematics students who are more comfortable with theory than practice. They should be trained as genuine engineers, who are competent with industrial applications as well as the supporting theory.

Because of the growing importance of object-oriented programming, a number of testing strategies have been proposed. They are based either on pure black-box or white-box techniques. We propose in this article a methodology to integrate the black- and white-box techniques. The black-box technique is used to select test cases. The white-box technique is mainly applied to determine whether two objects resulting from the program execution of a test care are observationally equivalent. It is also used to select test cases in some situations. We define the concept of a fundamental pair as a pair of equivalent terms that are formed by replacing all the variables on both sides of an axiom by normal forms. We prove that an implementation is consistent with respect to all equivalent terms if and only if it is consistent with respect to all fundamental pairs. In other words, the testing coverage of fundamental pairs is as good as that of all possible term rewritings, and hence we need only concentrate on the testing of fundamental pairs. Our strategy is based on mathematical theorems. According to the strategy, we propose an algorithm for selecting a finite set of fundamental pairs as test cases. Given a pair of equivalent terms as a test case, we should then determine whether the objects that result from executing the implemented program are observationally equivalent. We prove, however, that the observational equivalence of objects cannot be determined using a finite set of observable contexts (which are operation sequences ending with an observer function) derived from any black-box technique. Hence we supplement our approach with a “relevant observable context” technique, which is a heuristic white-box technique to select a relevant finite subset of the set of observable contexts for determining the observational equivalence. The relevant observable contezxts are constructed from a data member relevance graph (DRG), which is an abstraction of the given implementation for a given specificatin. A semiautomatic tool hass been developed to support this technique.

Abstract In this paper, we investigate the feasibility of applying logic programming to structured design. We propose to use Prolog as a common machinery for the representation of various structured tools. We illustrate through examples how to produce structure charts from data flow diagrams, and evaluate them according to commonly recommended design guidelines. If the structure charts produced are not satisfactory, the inherent backtracking mechanism in Prolog will help to produce other versions for further evaluation.

In this paper we examine the features which are most desirable in requirements specification languages, and then use the framework to review six established languages: PSL, SADT, EDDA, SAMM, HOS and RSL.

In this paper, we describe a proposal for formalising data flow diagrams through extended Petri nets. We illustrate the usefulness of the approach by describing how it can be used to analyse the consistency of requirements specifications.

We introduce the concepts of fully embedded skeletons and partially overlapping skeletons in program flowgraphs. We show that only one simple criterion is necessary and sufficient for the identification of program unstructuredness. Namely, a program flowgraph is unstructured if and only if it contains partially overlapping skeletons.

Quite a number of papers have discussed the problems of identifying unstructured programs and turning them into structured programs. Most of the papers, however, are based on intuitive arguments rather than on formal proofs. The identification of program unstructuredness has remained a difficult task. In this paper we formally study the properties of skeletons, modules, branches, iteration exits and entry nodes in program flowgraphs. We prove that two simple conditions are sufficient and necessary for the identification of unstructuredness.