Abstract According to the reachability–infection–propagation (RIP) model, three conditions must be satisfied for program failure to occur: (1) the defect's location must bereached, (2) the program's state must becomeinfectedand (3) the infection mustpropagateto the output.Weak coincidental correctness(orweak CC) occurs when the program produces the correct output, while condition (1) is satisfied but conditions (2) and (3) are not satisfied.Strong coincidental correctness(orstrong CC) occurs when the output is correct, while both conditions (1) and (2) are satisfied but not (3). The prevalence ofCCwas previously recognized. In addition, the potential for its negative effect on spectrum‐based fault localization (SBFL) was analytically demonstrated; however, this was not empirically validated. UsingDefects4J, this paper empirically studies the impact ofweakandstrong CCon three well‐researched coverage‐based fault detection and localization techniques, namely, test suite reduction (TSR), test case prioritization (TCP) and SBFL. Our study, which involved 52 SBFL metrics, provides the following empirical evidence. (i) The negative impact ofCCtests on TSR and TCP is very significant. In addition, cleansing theCCtests was observed to yield (a) a 100% TSR defect detection rate for all subject programs and (b) an improvement of TCP for over 92% of the subjects. (ii) The impact ofCCtests on SBFL varies widely w.r.t. the metric used. The negative impact was strong for 11 metrics, mild for 37, non‐measurable for 1 and non‐existent for 3 metrics. Interestingly, the negative impact was mild for the 9 most popular and/or most effective SBFL metrics. In addition, cleansing theCCtests resulted in the deterioration of SBFL for a considerable number of subject programs. (iii) Increasing the proportion ofCCtests has a limited impact on TSR, TCP and SBFL. Interestingly, for TSR and TCP and 11 SBFL metrics, small and large proportions ofCCtests are strongly harmful. (iv) Lastly,weakandstrong CCare equally detrimental in the context of TSR, TCP and SBFL.

Researchers have used execution profiles to enable coverage-based techniques in areas such as defect detection and fault localization. Typical profile elements include functions, statements, and branches, which are structural in nature. Such elements might not always discriminate failing runs from passing runs, which renders them ineffective in some cases. This motivated us to investigate alternative profiles, namely, substate profiles that aim at approximating the state of a program (as opposed to its execution path). Substate profiling is a recently presented form of state profiling that is practical, fine-grained, and generic enough to be applicable to various profile-based analyses. This paper presents an empirical study demonstrating how complementing structural profiles with substate profiles would benefit Test Suite Reduction (TSR), Test Case Prioritization (TCP), and Spectrum-based Fault Localization (SBFL). Using the Defects4J benchmark, we contrasted the effectiveness of TSR, TCP, and SBFL when using the structural profiles only to when using the concatenation of the structural and substate profiles. Leveraging substate profiling enhanced the effectiveness of all three techniques. For example: 1) For TSR, 86 more versions exhibited 100% defect detection rate. 2) For TCP, 22 more versions had one of their failing tests ranked among the top 20%. 3) For SBFL,substate profiling localized 14 faults that structural profiling failed to localize. Furthermore, our study showed that the improvement due to substate profiling was noticeably more significant in the presence of coincidentally correct tests than in their absence. This positions substate profiling as a promising basis for mitigating the negative effect of coincidental correctness.

Summary Coincidental correctness (CC) arises when a defective program produces the correct output despite the fact that the defect within was exercised. Researchers have recognized the negative impact of CC, and the authors have previously conducted a study demonstrating its prevalence in test suites. However, that study was limited to system tests, and small subjects seeded with artificial defects. In this paper, we conduct a wider scope study of CC that addresses the following research questions in the context of theDefects4Jbenchmark. RQ1: Is CC prevalent in Defects4J? RQ2: Is CC affected by the testing levels in Defects4J? RQ3: Do CC tests induce peculiar infection paths in Defects4J? Furthermore, we useJTidyandNanoXMLto address the following question. RQ4: Are the infections likely to be nullified within or outside the buggy method? To answer RQ1, we manually injected two code checkers for each of the 395Defects4Jdefects: (i) a weak checker that detects weak CC tests by monitoring whether the defect was reached; and (ii) a strong checker that detects strong CC tests by monitoring whether the defect was reached and the program has transitioned into an infectious state. Our results showed that CC is prevalent inDefects4J, as we observed 38.1× more strong CC tests than failing tests and 60.5× more weak CC tests than failing tests. Testing has traditionally been classified into several levels that include unit, module, integration, system, and acceptance. Meanwhile, the test cases inDefects4Jare not classified into any of the aforementioned testing levels. In addition, the boundaries between such levels are not clear because of the lack of a clear universal definition. Therefore, in order to answer RQ2, we derive the testing level of a test case from its method coverage information; specifically, we base it on the number and frequency of execution of the methods it covers. Our results showed that CC is present at all testing levels, but is more prevalent in high testing levels than in low testing levels. To answer RQ3, we contrasted the characteristics of the infection propagation paths induced by theDefects4Jfailing tests to those induced by the strong CC tests. We observed that the paths induced by the CC tests (i) were considerably longer on average and (ii) comprised a higher number of conditional, modulo, multiplication, division, and invocation statements. Finally, to answer RQ4, which relates to RQ2, we performed an experiment involvingJTidy,NanoXML, and their associated high‐level test suites. We used code checkers to determine whether, in the case of strong CC, the infections were nullified before exiting the buggy function or afterward. All of our observations showed that the infections were nullified after exiting the buggy function. © 2019 John Wiley & Sons, Ltd.

Test suite reduction (TSR) aims at removing redundant test cases from regression test suites. A typical TSR approach ensures that structural profile elements covered by the original test suite are also covered by the reduced test suite. It is plausible that structural profiles might be unable to segregate failing runs from passing runs, which diminishes the effectiveness of TSR in regard to defect detection. This motivated us to explore state profiles, which are based on the collective values of program variables. This paper presents Substate Profiling, a new form of state profiling that enhances existing profile-based analysis techniques such as TSR and coverage-based fault localization. Compared to current approaches for capturing program states, Substate Profiling is more practical and finer grained. We evaluated our approach using thirteen multi-fault subject programs comprising 53 defects. Our study involved greedy TSR using Substate profiles and four structural profiles, namely, basic-block, branch, def-use pair, and the combination of the three. For the majority of the subjects, Substate Profiling detected considerably more defects with a comparable level of reduction. Also, Substate profiles were found to be complementary to structural profiles in many cases, thus, combining both types is beneficial.

Summary The goal of regression testing is to ensure that the behaviour of existing code, believed correct by previous testing, is not altered by new program changes. This paper argues that the primary focus of regression testing should be on code associated with (1) earlier bug fixes and (2) particular application scenarios considered to be important by the developer or tester. Existing coverage criteria do not enable such focus, for example, 100% branch coverage does not guarantee that a given bug fix is exercised or a given application scenario is tested. Therefore, there is a need for a new and complementary coverage criterion in whichthe user can defineatest requirement characterizing a given behaviour to be coveredas opposed to choosing from a pool of pre‐defined and generic program elements. This paper proposes this new methodology and calls itUCov, auser‐defined coverage criterionwherein a test requirement is anexecution patternof program elements, and possibly predicates, that a test case must satisfy. The proposed criterion is not meant to replace existing criteria, but to complement them as it focuses the testing on important code patterns that could go untested otherwise.UCovsupportstest case intent verification. For example, following a bug fix, the testing team may augment the regression suite with the test case that revealed the bug. However, this test case might become obsolete due to code modifications not related to the bug. But if a test requirement characterizing the bug was defined by the user,UCovwould determine that test case intent verification failed. TheUCovmethodology was implemented for the Java platform, was successfully applied onto 10 real‐life case studies and was shown to have advantages overJUnit. The implementation comprises the following tools: (1)TRSpec: allows the user to easily specify complex test requirements; (2)TRCheck: checks whether user‐defined test requirements were satisfied, that is, supports test case intent verification; and (3)TRMigrate: migrates user‐defined test requirements to subsequent versions of a given program. Copyright © 2016 John Wiley & Sons, Ltd.

Summary The interest in leveraging data mining and statistical techniques to enable dynamic program analysis has increased tremendously in recent years. Researchers have presented numerous techniques that mine and analyze execution profiles to assist software testing and other reliability enhancing approaches. Previous empirical studies have shown that the effectiveness of such techniques is likely to be impacted by the type of profiled program elements. This work further studies the impact of the characteristics of execution profiles by focusing on their size; noting that a typical profile comprises a large number of program elements, in the order of thousands or higher. Specifically, the authors devised six reduction techniques and comparatively evaluated them by measuring the following: (1) reduction rate; (2) information loss; (3) impact on two applications of dynamic program analysis, namely, cluster‐based test suite minimization (App‐I), and profile‐based online failure and intrusion detection (App‐II). The results were promising as the following: (a) the average reduction rate ranged from 92% to 98%; (b) three techniques were lossless and three were slightly lossy; (c) reducing execution profiles exhibited a major positive impact on the effectiveness and efficiency of App‐I; and (d) reduction exhibited a positive impact on the efficiency of App‐II, but a minor negative impact on its effectiveness. Copyright © 2014 John Wiley & Sons, Ltd.

Researchers have argued that for failure to be observed the following three conditions must be met: C R = the defect was reached; C I = the program has transitioned into an infectious state; and C P = the infection has propagated to the output. Coincidental Correctness (CC) arises when the program produces the correct output while condition C R is met but not C P . We recognize two forms of coincidental correctness, weak and strong. In weak CC , C R is met, whereas C I might or might not be met, whereas in strong CC , both C R and C I are met. In this work we first show that CC is prevalent in both of its forms and demonstrate that it is a safety reducing factor for Coverage-Based Fault Localization (CBFL). We then propose two techniques for cleansing test suites from coincidental correctness to enhance CBFL, given that the test cases have already been classified as failing or passing. We evaluated the effectiveness of our techniques by empirically quantifying their accuracy in identifying weak CC tests. The results were promising, for example, the better performing technique, using 105 test suites and statement coverage, exhibited 9% false negatives, 30% false positives, and no false negatives nor false positives in 14.3% of the test suites. Also using 73 test suites and more complex coverage, the numbers were 12%, 19%, and 15%, respectively.

The majority of dynamic software analyses are implemented in the form of fully-automated techniques. Given the limited success of many of these techniques, we explore the use of visualization as the basis for alternative techniques. Specifically, we investigate the use of multivariate visualization scatter plots, which aim at presenting high dimensional data in low dimensions (e.g., 2D). For example, to visualize the similarity between test cases, where a test is represented as a scatter point, the execution profiles induced by the test cases are compared in order to calculate similarity metrics that will characterize the distances between the scatter points. This type of scatter plots was previously presented by other researchers who also suggested their use in several software analyses. This work considers these scatter plots in: 1) identifying coincidentally correct tests which are a safety reducing factor in coverage based fault localization, and 2) outlining a user aided visualization-based fault localization technique. Other applications of multivariate visualization to software analysis will also be discussed.

Researchers have argued that for failure to be observed the following three conditions must be met: 1) the defect is executed, 2) the program has transitioned into an infectious state, and 3) the infection has propagated to the output. Coincidental correctness arises when the program produces the correct output, while conditions 1) and 2) are met but not 3). In previous work, we showed that coincidental correctness is prevalent and demonstrated that it is a safety reducing factor for coverage-based fault localization. This work aims at cleansing test suites from coincidental correctness to enhance fault localization. Specifically, given a test suite in which each test has been classified as failing or passing, we present three variations of a technique that identify the subset of passing tests that are likely to be coincidentally correct. We evaluated the effectiveness of our techniques by empirically quantifying the following: 1) how accurately did they identify the coincidentally correct tests, 2) how much did they improve the effectiveness of coverage-based fault localization, and 3) how much did coverage decrease as a result of applying them. Using our better performing technique and configuration, the safety and precision of fault-localization was improved for 88% and 61% of the programs, respectively.

Preferences, which control our decisions in the daily life, have been widely studied and analyzed in computer science. In artificial intelligence, preferences are used in many domains such as decision theory, learning, etc. Several representations and reasoning techniques of preferences were proposed. One of these representations is the non-monotonic logic of preferences characterized by the ability to express several interpretations of preferences simultaneously. In relational databases, preferences are used for the personalization of queries to reduce the volume of data presented to the user by offering only the information that interests him. There, preferences are typically specified using binary preference relations among tuples. Binary preference relations are defined by preference formulas which can be embedded into classical relational queries. This paper is intended to discuss the encoding of relational database preference queries in the framework of the non-monotonic logic of preferences. We show that this framework allows the representation of binary preference relations that are asymmetric orders. In addition, it provides several mechanisms to manipulate preference queries efficiently.