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 Oracles used for testing graphical user interface (GUI) programmes are required to take into consideration complicating factors such as variations in screen resolution or colour scheme when comparing observed GUI elements with expected GUI elements. Researchers proposed fuzzy comparison rules and computationally expensive image processing techniques to tame the comparison process because otherwise the naïve matching comparison would be too constraining and consequently impractical. Alternatively, this paper proposes GUICop, a novel approach with a supporting toolset that takes (1) a GUI programme and (2) user‐defined GUI specifications characterizing the rendering behaviour of the GUI elements and checks whether the execution traces of the programme satisfy the specifications. GUICop comprises the following: (1) a GUI Specification Language; (2) a Driver; (3) Instrumented GUI Libraries; 4) a Solver; and (5) a Code Weaver. The user defines the specifications of the subject GUI programme using the GUI Specification Language. The Driver traverses the GUI structure of the programme and generates events that drive its execution. The Instrumented GUI Libraries capture the GUI execution trace, ie, information about the positions and visibility of the GUI elements. And the Solver, enabled by code injected by the Code Weaver, checks whether the traces satisfy the specifications. GUICop was successfully evaluated using 4 open source GUI applications that included 8 defects, namely, Jajuk, Gason, JEdit, and TerpPaint.

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.

Abstract SQL injection attacks(SQLIAs) aim at exploiting vulnerabilities in web applications in order to execute malicious SQL commands. It is established thatprepared statementsare resilient to SQLIAs, and thus, developers are advised to use them when constructing SQL queries as opposed to applying string concatenation operations. Unfortunately, this recommended programming practice is not as pervasive as it should be. This paper addresses this shortcoming by presentingSQL injection Prevention by Input Labeling(SQLPIL), an effective, light, and fully automated tool that leverages prepared statements topreventSQLIAs at runtime. Given a Java program in which SQL queries are built as strings,SQLPILdynamically transforms the strings into secure prepared statements right before their execution, thus guaranteeing that malicious input will always be treated as data and never as SQL commands. We empirically evaluated our Java implementation ofSQLPILusing a benchmark that includes five JSP commercial applications, a number of legitimate queries, and a number of attacks of representative types. The results were promising as all attacks were prevented, and all legitimate runs executed successfully; in other words, the technique exhibitedno false alarmswhen applied on typical applications. Also, the runtime cost was acceptable, assuming typical settings. Copyright © 2015 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.

Typically, oracles used to test graphical user interface(GUI) programs highly depend on environmental factors that are not related to the functionality of the program, such as screen resolution and color schemes. To accommodate these on-functional variations, researchers suggested fuzzy comparison rules that determine whether the output of a GUI program matches the oracles. Others suggested computer vision based solutions that make use of computationally expensive image processing techniques to abstract the strict comparisons. Alternatively, we propose GUICOP, a system that checks whether a trace of a GUI execution violates a given GUI specification. GUICOP is composed of a GUI specification language, instrumented GUI libraries, and a checker. The alphabet of the specification language contains basic geometric shapes describing GUI components, events, and positional and temporal operators that express relative object positions and event timings, respectively. During program execution, the instrumented libraries capture positional and temporal information of components and associated triggered events in execution traces. The checker determines whether the traces satisfy the specifications. To evaluate GUICOP, we wrote 50 use cases that describe real GUI applications and used the GUICOP checker on the supported cases that successfully revealed violations.

Value prediction is a technique to increase parallelism by attempting to overcome serialization constraints caused by true data dependences. By predicting the outcome of an instruction before it executes, value prediction allows data dependent instructions to issue and execute speculatively, hence increasing parallelism when the prediction is correct. In case of a misprediction, the execution is redone with the corrected value. If the benefit from increased parallelism outweighs the misprediction recovery penalty, overall performance could be improved. Enhancing performance with value prediction therefore requires highly accurate prediction methods. Most existing general value prediction techniques are local, that is, future outputs of an instruction are predicted based on outputs from previous executions of the same instruction. In this article, we investigate leveraging strength-based dynamic information flow analysis to enhance data value prediction. We use dynamic information flow analysis (DIFA) to determine when a specific value predictor can perform well and even outperform other predictors. We apply information theory to mathematically prove the validity and benefits of correlating value predictors. We also introduce the concept of the linear value predictors, a new technique that predicts a new value from another one using a linear relation. We finally present a variant of stride predictor that we call update stride . We then conduct an empirical analysis using Pin , a dynamic binary instrumentation tool, and DynFlow , a dynamic information flow analysis tool, that we apply to programs from the SPECjvm2008 and Siemens benchmarks. Our empirical measurements support our mathematical theory and allow us to make important observations on the relation between predictability of data values and information flow. Our analysis and empirical results show that the values of a set of selected variables can be predicted with a very high accuracy, up to 100%. Such prediction is based on the previous history and/or the values of one or more other source variables that have strong information flow into the predicted variable. Using our selection criteria, we show that a DIFA-directed predictor outperforms hardware value prediction for all subject programs, and sometimes by a significant margin. This was observed even when using an ideal tagged hardware value prediction table that does not suffer from aliasing or capacity misses.

Value prediction is a technique to increase parallelism by attempting to overcome serialization constraints caused by true data dependences. By predicting the outcome of an instruction before it executes, value prediction allows data dependent instructions to issue and execute speculatively, hence increasing parallelism when the prediction is correct. In case of a misprediction, the execution is redone with the corrected value. If the benefit from increased parallelism outweighs the misprediction recovery penalty, overall performance could be improved. Enhancing performance with value prediction therefore requires highly accurate prediction methods. Most existing general value prediction techniques are local and future outputs of an instruction are predicted based on outputs from previous executions of the same instruction.

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.

Abstract Failures triggered by hard to debug defects usually involve complex interactions between many program elements. This paper hypothesizes that information flows present a good model for such interactions and presents a new fault localization technique based on information flow coverage. Using a test suite, the technique ranks the statements in a program in terms of their likelihood of being faulty by comparing the information flows induced by the failing runs with the ones induced by the passing runs. The ranking of the statements associated with a given flow is primarily determined by contrasting the percentage of failing runs to the percentage of passing runs that induced it. Generally, a higher percentage of failing runs implies a higher rank. To show its potential, the technique was applied to several open‐source Java programs and was compared, with respect to its fault localization effectiveness, with three other coverage techniques that use similar style metrics that are defined for statements, branches, and def–use pairs, respectively. The results revealed that information flow, branch, and def–use coverage performed consistently better than statement coverage. In addition, in a considerable number of cases information flow coverage performed better than branch and def–use coverage. Specifically, it was always safer but not always more precise. Copyright © 2009 John Wiley & Sons, Ltd.

Dynamic information flow analysis (DIFA) was devised to enable the flow of information among variables in an executing program to be monitored and possibly regulated. It is related to techniques like dynamic slicing and dynamic impact analysis . To better understand the basis for DIFA, we conducted an empirical study in which we measured the strength of information flows identified by DIFA, using information theoretic and correlation-based methods. The results indicate that in most cases the occurrence of a chain of dynamic program dependences between two variables does not indicate a measurable information flow between them. We also explored the relationship between the strength of an information flow and the length of the corresponding dependence chain, and we obtained results indicating that no consistent relationship exists between the length of an information flow and its strength. Finally, we investigated whether data dependence and control dependence makes equal or unequal contributions to flow strength. The results indicate that flows due to data dependences alone are stronger, on average, than flows due to control dependences alone. We present the details of our study and consider the implications of the results for applications of DIFA and related techniques.

Some software defects trigger failures only when certain local or nonlocal program interactions occur. Such interactions are modeled by the closely related concepts of information flows, program dependences, and program slices. The latter concepts underlie a 78variety of proposed test data adequacy criteria, and they form a potentially important basis for filtering existing test cases. We report the results of an empirical study of several test case filtering techniques that are based on exercising information flows. Both coverage-based and profile-distribution-based filtering techniques are considered. They are compared to filtering techniques based on exercising simpler program elements, such as basic blocks, branches, function calls, and call pairs, with respect to their effectiveness for revealing defects.

Forward computation of dynamic slices is necessary to support interactive debugging and online analysis of long running programs. However, the overhead of existing forward computing algorithms limits their use to non-processing intensive applications. Recent empirical studies have shown that slices tend to reoccur often during execution. This paper presents a new forward computing algorithm for dynamic slicing, which is based on the stronger assumption that the same set union operations need to be performed repeatedly during slice computation. We present the results of an empirical study contrasting the performance of our new algorithm to the performance of a basic forward computing algorithm that unconditionally merges slices influencing an executing statement. The results indicate that the new algorithm is substantially faster than the basic algorithm and often requires significantly less memory

Some software defects trigger failures only when certain complex information flows occur within the software. Profiling and analyzing such flows therefore provides a potentially important basis for filtering test cases. We report the results of an empirical evaluation of several test case filtering techniques that are based on exercising complex information flows. Both coverage-based and profile-distribution-based filtering techniques are considered. They are compared to filtering techniques based on exercising basic blocks, branches, function calls, and def-use pairs, with respect to their effectiveness for revealing defects.

A new approach to dynamic information flow analysis is presented that can be used to detect and debug insecure flows in programs. It can be applied offline to validate and debug a program against an information flow policy, or, when fast response is not critical, it can be applied online to prevent illegal flows in deployed programs. Since dynamic analysis alone is inherently unable to detect implicit information flows, our approach incorporates a static preprocessing phase that permits detection of most implicit flows at runtime, in addition to explicit ones. To support interactive debugging of insecure flows, it also incorporates a new forward computing algorithm for dynamic slicing, which is more precise than previous forward computing algorithms and is not restricted to programs with structured control flow. A prototype tool implementing the proposed approach has been developed for Java byte code programs. Case studies in which this tool was applied to several subject programs are described.

This paper proposes automated support for classifying reported software failures in order to facilitate prioritizing them and diagnosing their causes. A classification strategy is presented that involves the use of supervised and unsupervised pattern classification and multivariate visualization. These techniques are applied to profiles of failed executions in order to group together failures with the same or similar causes. The resulting classification is then used to assess the frequency and severity of failures caused by particular defects and to help diagnose those defects. The results of applying the proposed classification strategy to failures of three large subject programs are reported These results indicate that the strategy can be effective.