As modern web services increasingly rely on REST APIs, their thorough testing has become crucial. Furthermore, the advent of REST API documentation languages, such as the OpenAPI Specification, has led to the emergence of many black-box REST API testing tools. However, these tools often focus on individual test elements in isolation (e.g., APIs, parameters, values), resulting in lower coverage and less effectiveness in fault detection. To address these limitations, we present AutoRestTest, the first black-box tool to adopt a dependency-embedded multi-agent approach for REST API testing that integrates multi-agent reinforcement learning (MARL) with a semantic property dependency graph (SPDG) and Large Language Models (LLMs). Our approach treats REST API testing as a separable problem, where four agents-API, dependency, parameter, and value agents-collaborate to optimize API exploration. LLMs handle domain-specific value generation, the SPDG model simplifies the search space for dependencies using a similarity score between API operations, and MARL dynamically optimizes the agents' behavior. Our evaluation of AutoRestTest on 12 real-world REST services shows that it outperforms the four leading black-box REST API testing tools, including those assisted by RESTGPT (which generates realistic test inputs using LLMs), in terms of code coverage, operation coverage, and fault detection. Notably, AutoRestTest is the only tool able to trigger an internal server error in the Spotify service. Our ablation study illustrates that each component of AutoRestTest-the SPDG, the LLM, and the agent-learning mechanism-contributes to its overall effectiveness.

Web Application Programming Interfaces (APIs) allow services to be accessed over the network. RESTful (or REST) APIs, which use the REpresentation State Transfer (REST) protocol, are a popular type of web API. To use or test REST APIs, developers use specifications written in standards such as OpenAPI. However, creating and maintaining these specifications is time-consuming and error-prone, especially as software evolves, leading to incomplete or inconsistent specifications that negatively affect the use and testing of the APIs. To address this problem, we present Respector (REST API specification generator), the first technique to employ static and symbolic program analysis to generate specifications for REST APIs from their source code. We evaluated Respector on 15 real-world APIs with promising results in terms of precision and recall in inferring endpoint methods, endpoint parameters, method responses, and parameter attributes, including constraints leading to successful HTTP responses or errors. Furthermore, these results could be further improved with additional engineering. Comparing the Respector-generated specifications with the developer-provided ones shows that Respector was able to identify many missing end-point methods, parameters, constraints, and responses, along with some inconsistencies between developer-provided specifications and API implementations. Finally, Respector outperformed several techniques that infer specifications from annotations within API implementations or by invoking the APIs.

User-defined functions (UDFs) are widely used to enhance the capabilities of DBMSs. However, using UDFs comes with a significant performance penalty because DBMSs treat UDFs as black boxes, which hinders their ability to optimize queries that invoke such UDFs. To mitigate this problem, in this paper we present LAMBDA, a technique and framework for improving DBMSs' performance in the presence of UDFs. The core idea of LAMBDA is to statically infer properties of UDFs that facilitate UDF processing. Taking one such property as an example, if DBMSs know that a UDF is pure, that is it returns the same result given the same arguments, they can leverage a cache to avoid repetitive UDF invocations that have the same call arguments.

Pretrained models of code, such as CodeBERT and CodeT5, have become popular choices for code understanding and generation tasks. Such models tend to be large and require commensurate volumes of training data, which are rarely available for downstream tasks. Instead, it has become popular to train models with far larger but less realistic datasets, such as functions with artificially injected bugs. Models trained on such data, however, tend to only perform well on similar data, while underperforming on real-world programs. In this paper, we conjecture that this discrepancy stems from the presence of distracting samples that steer the model away from the real-world task distribution. To investigate this conjecture, we propose an approach for identifying the subsets of these large, yet “unrealistic” datasets that are most similar to examples in real-world datasets based on their learned representations. Our approach extracts high-dimensional embeddings of both real-world and artificial programs using a neural model and scores artificial samples based on their distance to the nearest real-world sample. We show that training on only the nearest, representationally most similar samples while discarding samples that are not at all similar in representations yields consistent improvements across two popular pretrained models of code on two code understanding tasks. Our results are promising, in that they show that training models on a representative subset of an unrealistic dataset can help us harness the power of large-scale synthetic data generation while preserving downstream task performance. Finally, we highlight the limitations of applying AI models for predicting vulnerabilities and bugs in real-world applications.

RESTful services are commonly documented using OpenAPI specifications. Although numerous automated testing techniques have been proposed that leverage the machine-readable part of these specifications to guide test generation, their human-readable part has been mostly neglected. This is a missed opportunity, as natural language descriptions in the specifications often contain relevant information, including example values and inter-parameter dependencies, that can be used to improve test generation. In this spirit, we propose NLPtoREST, an automated approach that applies natural language processing techniques to assist REST API testing. Given an API and its specification, NLPtoREST extracts additional OpenAPI rules from the human-readable part of the specification. It then enhances the original specification by adding these rules to it. Testing tools can transparently use the enhanced specification to perform better test case generation. Because rule extraction can be inaccurate, due to either the intrinsic ambiguity of natural language or mismatches between documentation and implementation, NLPtoREST also incorporates a validation step aimed at eliminating spurious rules. We performed studies to assess the effectiveness of our rule extraction and validation approach, and the impact of enhanced specifications on the performance of eight state-of-the-art REST API testing tools. Our results are encouraging and show that NLPtoREST can extract many relevant rules with high accuracy, which can in turn significantly improve testing tools’ performance.

Modern web services increasingly rely on REST APIs. Effectively testing these APIs is challenging due to the vast search space to be explored, which involves selecting API operations for sequence creation, choosing parameters for each operation from a potentially large set of parameters, and sampling values from the virtually infinite parameter input space. Current testing tools lack efficient exploration mechanisms, treating all operations and parameters equally (i.e., not considering their importance or complexity) and lacking prioritization strategies. Furthermore, these tools struggle when response schemas are absent in the specification or exhibit variants. To address these limitations, we present an adaptive REST API testing technique that incorporates reinforcement learning to prioritize operations and parameters during exploration. Our approach dynamically analyzes request and response data to inform dependent parameters and adopts a sampling-based strategy for efficient processing of dynamic API feedback. We evaluated our technique on ten RESTful services, comparing it against state-of-the-art REST testing tools with respect to code coverage achieved, requests generated, operations covered, and service failures triggered. Additionally, we performed an ablation study on prioritization, dynamic feedback analysis, and sampling to assess their individual effects. Our findings demonstrate that our approach outperforms existing REST API testing tools in terms of effectiveness, efficiency, and fault-finding ability.

One of the primary mechanisms by which developers receive feedback about in-field failures of software from users is through bug reports. Unfortunately, the quality of manually written bug reports can vary widely due to the effort required to include essential pieces of information, such as detailed reproduction steps (S2Rs). Despite the difficulty faced by reporters, few existing bug reporting systems attempt to offer automated assistance to users in crafting easily readable, and conveniently reproducible bug reports. To address the need for proactive bug reporting systems that actively aid the user in capturing crucial information, we introduce a novel bug reporting approach calledEBug.EBugassists reporters in writing S2Rs for mobile applications by analyzing natural language information entered by reporters in real-time, and linking this data to information extracted via a combination of static and dynamic program analyses. As reporters write S2Rs,EBugis capable of automatically suggesting potential future steps using predictive models trained on realistic app usages. To evaluateEBug, we performed two user studies based on 20 failures from 11 real-world apps. The empirical studies involved ten participants that submitted ten bug reports each and ten developers that reproduced the submitted bug reports. In the studies, we found that reporters were able to construct bug reports 31%fasterwithEBugas compared to the state-of-the-art bug reporting system used as a baseline.EBug's reports were alsomore reproduciblewith respect to the ones generated with the baseline. Furthermore, we comparedEBug's prediction models to other predictive modeling approaches and found that, overall, the predictive models of our approach outperformed the baseline approaches. Our results are promising and demonstrate the feasibility and potential benefits provided by proactively assistive bug reporting systems.

Android apps interact with their environment extensively, which can result in flaky, slow, or hard-to-debug tests. Developers often address these problems using test doubles---developer-defined objects that replace app or library classes during test execution. Although test doubles are widely used, there is limited understanding of how they are used in practice. To bridge this gap, we present an in-depth empirical study that aims to shed light on how developers create and use test doubles in Android apps. In our study, we first analyze a dataset of 1,006 apps with publicly available test suites to identify which frameworks and approaches developers most commonly use to create test doubles. We then investigate several research questions by studying how test doubles defined using these popular frameworks are created and used in the ten apps in the dataset that define the highest number of test doubles using these frameworks. Our results, based on the analysis of 2,365 test doubles that replace a total of 784 classes, provide insight into the types of test doubles used within Android apps and how they are utilized. Our results also show that test doubles used in Android apps and traditional Java test doubles differ in at least some respect. Finally, our results show that test doubles can introduce test smells and even mistakes in the test code. In the paper, we also discuss some implications of our findings that can help researchers and practitioners working in this area and guide future research.

Because modern data-intensive applications rely heavily on database systems (DBMSs), developers extensively test these systems to eliminate bugs that negatively affect functionality. Besides functional bugs, however, there is another important class of faults that negatively affect the response time of a DBMS, known as performance bugs. Despite their potential impact on end-user experience, performance bugs have received considerably less attention than functional bugs. To fill this gap, we present Amoeba, a technique and tool for automatically detecting performance bugs in DBMSs. The core idea behind Amoeba is to construct semantically equivalent query pairs, run both queries on the DBMS under test, and compare their response time. If the queries exhibit significantly different response times, that indicates the possible presence of a performance bug in the DBMS. To construct equivalent queries, we propose to use a set of structure and expression mutation rules especially targeted at uncovering performance bugs. We also introduce feedback mechanisms for improving the effectiveness and efficiency of the approach. We evaluate Amoeba on two widely-used DBMSs, namely PostgreSQL and CockroachDB, with promising results: Amoeba has so far discovered 39 potential performance bugs, among which developers have already confirmed 6 bugs and fixed 5 bugs.

Before releasing updated software, developers typically run regression test suites to verify that the code changes behave as intended and do not introduce unintended behaviors. Regression test suites, however, are often incomplete and can miss relevant software behaviors. To mitigate this issue, we introduce a technique for detecting potentially unintended behavioral changes. Given two versions of the software, our technique first finds functions that reach modified code in either version. It then performs underconstrained symbolic execution on both the original and revised programs, starting from the identified functions. If the execution reaches changed code, the technique compares corresponding program states across versions and logs differences. Because the so-generated raw log can contain a large number of redundant entries and a mixture of both intended and unintended differences, our technique clusters, orders, and ranks the logged differences to help developers identify feasible, unintended differences. We evaluated our technique by (1) applying it to a large set of known regressions, (2) comparing our results with those of a state-of-the-art approach, and (3) applying it to a popular program, Redis. Our results are promising: for the known regressions, our technique automatically identified more than half of the regressions, generated a low number of false positives, ranked the true positives above the false positives in most cases, and reported more regressions than the state-of-the-art technique we used as a baseline; for the refactored Redis versions, our technique reported no regressions.

Modern web services routinely provide REST APIs for clients to access their functionality. These APIs present unique challenges and opportunities for automated testing, driving the recent development of many techniques and tools that generate test cases for API endpoints using various strategies. Understanding how these techniques compare to one another is difficult, as they have been evaluated on different benchmarks and using different metrics. To fill this gap, we performed an empirical study aimed to understand the landscape in automated testing of REST APIs and guide future research in this area. We first identified, through a systematic selection process, a set of 10 state-of-the-art REST API testing tools that included tools developed by both researchers and practitioners. We then applied these tools to a benchmark of 20 real-world open-source RESTful services and analyzed their performance in terms of code coverage achieved and unique failures triggered. This analysis allowed us to identify strengths, weaknesses, and limitations of the tools considered and of their underlying strategies, as well as implications of our findings for future research in this area.

Existing approaches for program debloating often use a usage profile, typically provided as a set of inputs, for identifying the features of a program to be preserved. Specifically, given a program and a set of inputs, these techniques produce a reduced program that behaves correctly for these inputs. Focusing only on reduction, however, would typically result in programs that are overfitted to the inputs used for debloating. For this reason, another important factor to consider in the context of debloating is generality, which measures the extent to which a debloated program behaves correctly also for inputs that were not in the initial usage profile. Unfortunately, most evaluations of existing debloating approaches only consider reduction, thus providing partial information on the effectiveness of these approaches. To address this limitation, we perform an empirical evaluation of the reduction and generality of 4 debloating techniques, 3 state-of-the-art ones, and a baseline, on a set of 25 programs and different sets of inputs for these programs. Our results show that these approaches can indeed produce programs that are overfitted to the inputs used and have low generality. Based on these results, we also propose two new augmentation approaches and evaluate their effectiveness. The results of this additional evaluation show that these two approaches can help improve program generality without significantly affecting size reduction. Finally, because different approaches have different strengths and weaknesses, we also provide guidelines to help users choose the most suitable approach based on their specific needs and context.

The paper titled “Are Automated Debugging Techniques Actually Helping Programmers?” was published in the proceedings of the International Symposium on Software Testing and Analysis (ISSTA) in 2011, and has been selected to receive the ISSTA 2021 Impact Paper Award. The paper investigated, through two user studies, how developers used and benefited from popular automated debugging techniques. The results of the studies provided (1) evidence that several assumptions made by automated debugging techniques did not hold in practice and (2) insights on limitations of existing approaches and how these limitations could be addressed. In this talk, we revisit the original paper and the work that led to it. We then assess the impact of that research by reviewing how the area of automated debugging has evolved since the paper was published. Finally, we conclude the talk by reflecting on the current state of the art in this area and discussing open issues and potential directions for future work.

In-house tests are hardly representative of the rich variety of software behaviors exercised by real users in the field. To bridge the gap between in-house tests and field executions, we need ways to (1) identify behavior exercised in the field but not in-house, and (2) generate new tests that exercise such (or at least similar) behavior. In this context, we propose Replica, a technique that uses field execution data to guide test generation. Replica instruments the software before deploying it, so that field data collection is triggered when a user exercises an untested behavior. Then, when it receives the collected field data, Replica uses guided symbolic execution to generate executions that exercise this previously untested behavior. Our empirical evaluation shows that Replica can successfully generate tests that mimic field executions in terms of both behaviors exercised and faults detected. Our results also show that Replica can outperform a state-of-the-art input-generation technique that does not leverage field data.

Dynamic slicing and its underlying dynamic dependence analysis have been extensively studied and used as the foundation for numerous automated-debugging techniques. One limitation of dynamic slicing, when used for debugging, is that it only considers program dependences that are actually observed during the execution(s) of interest. Some faults, however, involve potential, rather than actual dependences-dependences that would be observed if the correct program was executed but are missing when the faulty program is executed. In particular, traditional dynamic slicing may fail to locate faults that involve assignments that should have occurred in a correct execution and did not occur in the failing execution being debugged. Relevant slicing techniques partially address this problem by identifying missing assignments due to incorrect control-flow. However, they do not consider the case of assignments that do occur but modify the wrong memory location (e.g., the wrong element of an array). Debugging techniques based on existing dynamic slicing approaches may therefore miss faults in the presence of this kind of incorrect assignments. To address this problem, we introduce the concept of potential memory-address dependence (PMD). Intuitively, PMDs represent the dependence relationship between an instruction s that affects the computation of a memory-address ma (e.g., by defining an array index or a pointer offset) and memory read instructions that are not observed to be dependent on s but could be affected by s (i.e., access the memory at ma) in a counterfactual execution of s. We also present a technique that computes PMDs and represents them on standard dynamic dependence graphs. To assess the effectiveness of our technique for debugging, we implemented PMD-Slicer, a dynamic slicer that accounts for PMDs, and performed an empirical evaluation on a benchmark of 364 real faults and 880 fault-revealing test cases. Our results are promising, in that almost 10% of the failing tests contained cases in which PMD-Slicer generated slices that included the corresponding fault, while a traditional dynamic slicer did not. Furthermore, considering PMDs only moderately increased slice sizes.

Experience paper: Testing of mobile apps is time-consuming and requires a great deal of manual effort. For this reason, industry and academic researchers have proposed a number of test input generation techniques for automating app testing. Although useful, these techniques have weaknesses and limitations that often prevent them from achieving high coverage. We believe that one of the reasons for these limitations is that tool developers tend to focus mainly on improving the strategy the techniques employ to explore app behavior, whereas limited effort has been put into investigating other ways to improve the performance of these techniques. To address this problem, and get a better understanding of the limitations of input-generation techniques for mobile apps, we conducted an in-depth study of the limitations of Monkey-arguably the most widely used tool for automated testing of Android apps. Specifically, in our study, we manually analyzed Monkey's performance on a benchmark of 64 apps to identify the common limitations that prevent the tool from achieving better coverage results. We then assessed the coverage improvement that Monkey could achieve if these limitations were eliminated. In our analysis of the results, we also discuss whether other existing test input generation tools suffer from these common limitations and provide insights on how they could address them.

Mobile apps interact with their environment extensively, and these interactions can complicate testing activities because test cases may need a complete environment to be executed. Interactions with the environment can also introduce test flakiness, for instance when the environment behaves in non-deterministic ways. For these reasons, it is common to create test mocks that can eliminate the need for (part of) the environment to be present during testing. Manual mock creation, however, can be extremely time consuming and error-prone. Moreover, the generated mocks can typically only be used in the context of the specific tests for which they were created. To address these issues, we propose MOKA, a general framework for collecting and generating reusable test mocks in an automated way. MOKA leverages the ability to observe a large number of interactions between an application and its environment and uses an iterative approach to generate two possible, alternative types of mocks with different reusability characteristics: advanced mocks generated through program synthesis (ideally) and basic record-replay-based mocks (as a fallback solution). In this paper, we describe the new ideas behind MOKA, its main characteristics, a preliminary empirical study, and a set of possible applications that could benefit from our framework.

Because creating and maintaining an in-house test lab is expensive and time-consuming, companies and app developers often use device clouds to test their apps. Because quality-assurance activities depend on such device clouds, it is important to understand possible issues related to their use. To this end, in this paper we present a preliminary study that investigates issues and highlights research opportunities in the context of managing and maintaining device clouds. In the study, we analyzed over 12 million test executions on 110 devices. We found that the management software of the cloud infrastructure we considered affected some test executions, and almost all the cloud devices had at least one security-related issue.

Programs are becoming increasingly complex and typically contain an abundance of unneeded features, which can degrade the performance and security of the software. Recently, we have witnessed a surge of debloating techniques that aim to create a reduced version of a program by eliminating the unneeded features therein. To debloat a program, most existing techniques require a usage profile of the program, typically provided as a set of inputs I. Unfortunately, these techniques tend to generate a reduced program that is over-fitted to I and thus fails to behave correctly for other inputs. To address this limitation, we propose DomGad, which has two main advantages over existing debloating approaches. First, it produces a reduced program that is guaranteed to work for subdomains, rather than for specific inputs. Second, it uses stochastic optimization to generate reduced programs that achieve a close-to-optimal tradeoff between reduction and generality (i.e., the extent to which the reduced program is able to correctly handle inputs in its whole domain). To assess the effectiveness of DomGad, we applied our approach to a benchmark of ten Unix utility programs. Our results are promising, as they show that DomGad could produce debloated programs that achieve, on average, 50% code reduction and 95% generality. Our results also show that DomGad performs well when compared with two state-of-the-art debloating approaches.

In previous work, we introduced zero-overhead profiling (ZOP), a technique that leverages the electromagnetic emissions generated by the computer hardware to profile a program without instrumenting it. Although effective, ZOP has several shortcomings: it requires test inputs that achieve extensive code coverage for its training phase; it predicts path profiles instead of complete execution traces; and its predictions can suffer unrecoverable accuracy losses. In this paper, we present zero-overhead path prediction (ZOP-2), an approach that extends ZOP and addresses its limitations. First, ZOP-2 achieves high coverage during training through progressive symbolic execution (PSE)-symbolic execution of increasingly small program fragments. Second, ZOP-2 predicts complete execution traces, rather than path profiles. Finally, ZOP-2 mitigates the problem of path mispredictions by using a stateless approach that can recover from prediction errors. We evaluated our approach on a set of benchmarks with promising results; for the cases considered, (1) ZOP-2 achieved over 90% path prediction accuracy, and (2) PSE covered feasible paths missed by traditional symbolic execution, thus boosting ZOP-2's accuracy.

Repairing broken tests in evolving software systems is an expensive and challenging task. One of the main challenges for test repair, in particular, is preserving the intent of the original tests in the repaired ones. To address this challenge, we propose a technique for test repair that models and considers the intent of a test when repairing it. Our technique first uses a search-based approach to generate repair candidates for the broken test. It then computes, for each candidate, its likelihood of preserving the original test intent. To do so, the technique characterizes such intent using the path conditions generated during a dynamic symbolic execution of the tests. Finally, the technique reports the best candidates to the developer as repair recommendations. We implemented and evaluated our technique on a benchmark of 91 broken tests in 4 open-source programs. Our results are promising, in that the technique was able to generate intentpreserving repair candidates for over 79% of those broken tests and rank the intent-preserving candidates as the first choice of repair recommendations for almost 70% of the broken tests.

Mobile apps rely heavily on the application programming interface (API) provided by their underlying operating system (OS). Because OS and API can change frequently, developers must quickly update their apps to ensure that the apps behave as intended with new API and OS versions. To help developers with this tedious, error prone, and time consuming task, we developed a technique that can automatically perform app updates for API changes based on examples of how other developers evolved their apps for the same changes. Given a target app to be updated and information about the changes in the API, our technique performs four main steps. First, it analyzes the target app to identify code affected by API changes. Second, it searches existing code bases for examples of updates to the new version of the API. Third, it analyzes, ranks, and transforms into generic patches the update examples found in the previous step. Finally, it applies the generated patches to the target app in order of ranking, while performing differential testing to validate the update. We implemented our technique and performed an empirical evaluation on 15 real-world apps with promising results. Overall, our technique was able to update 85% of the API changes considered and automatically validate 68% of the updates performed.

The use of mobile apps is increasingly widespread, and much effort is put into testing these apps to make sure they behave as intended. To reduce this effort, and thus the overall cost of mobile app testing, we propose APPTESTMIGRATOR, a technique for migrating test cases between apps in the same category (e.g., banking apps). The intuition behind APPTESTMIGRATOR is that many apps share similarities in their functionality, and these similarities often result in conceptually similar user interfaces (through which that functionality is accessed). APPTESTMIGRATOR leverages these commonalities between user interfaces to migrate existing tests written for an app to another similar app. Specifically, given (1) a test case for an app (source app) and (2) a second app (target app), APPTESTMIGRATOR attempts to automatically transform the sequence of events and oracles in the test for the source app to events and oracles for the target app. We implemented APPTESTMIGRATOR for Android mobile apps and evaluated it on a set of randomly selected apps from the Google Play Store in four different categories. Our initial results are promising, support our intuition that test migration is possible, and motivate further research in this direction.

Numerous automated techniques have been proposed to reduce the cost of software debugging, a notoriously time-consuming and human-intensive activity. Among these techniques, Statistical Fault Localization (SFL) is particularly popular. One issue with SFL is that it is based on strong, often unrealistic assumptions on how developers behave when debugging. To address this problem, we propose Enlighten, an interactive, feedback-driven fault localization technique. Given a failing test, Enlighten (1) leverages SFL and dynamic dependence analysis to identify suspicious method invocations and corresponding data values, (2) presents the developer with a query about the most suspicious invocation expressed in terms of inputs and outputs, (3) encodes the developer feedback on the correctness of individual data values as extra program specifications, and (4) repeats these steps until the fault is found. We evaluated Enlighten in two ways. First, we applied Enlighten to 1,807 real and seeded faults in 3 open source programs using an automated oracle as a simulated user; for over 96% of these faults, Enlighten required less than 10 interactions with the simulated user to localize the fault, and a sensitivity analysis showed that the results were robust to erroneous responses. Second, we performed an actual user study on 4 faults with 24 participants and found that participants who used Enlighten performed significantly better than those not using our tool, in terms of both number of faults localized and time needed to localize the faults.

In recent years, there has been a growing interest in making education widely accessible using Internet technologies. Whether it is Massive Open Online Courses (MOOCs) or simply college courses offered to a large student population using an online platform, both education-focused companies and universities, often in collaboration with one another, have been investing massively in online education. The fact that hundreds, and more often thousands, of students take these online courses raises scalability challenges in assessing student assignments. In this paper, in particular, we present a technique (GUITestMigrator) that addresses the challenge of assessing mobile app coding assignments. Given a set of apps that implement the same specification, but can have completely different user interfaces, instructors normally have to manually run and check each app to make sure it behaves correctly and according to the specification. GUITestMigrator, conversely, allows for developing tests for one of these apps and automatically migrating these tests to the other apps, thus dramatically reducing the burden on the instructor. We implemented GUITestMigrator for Android apps and evaluated it on three sets of apps developed over three different semesters by students of an online graduate-level software engineering course. Our initial results show that our approach is promising and motivates further research in this direction. The paper also discusses possible applications of this approach for test evolution and test migration for real-world apps.

When users experience a software failure, they have the option of submitting a bug report and provide information about the failure and how it happened. If the bug report contains enough information, developers can then try to recreate the issue and investigate it, so as to eliminate its causes. Unfortunately, the number of bug reports filed by users is typically large, and the tasks of analyzing bug reports and reproducing the issues described therein can be extremely time consuming. To help make this process more efficient, in this paper we propose Yakusu, a technique that uses a combination of program analysis and natural language processing techniques to generate executable test cases from bug reports. We implemented Yakusu for Android apps and performed an empirical evaluation on a set of over 60 real bug reports for different real-world apps. Overall, our technique was successful in 59.7% of the cases; that is, for a majority of the bug reports, developers would not have to study the report to reproduce the issue described and could simply use the test cases automatically generated by Yakusu. Furthermore, in many of the remaining cases, Yakusu was unsuccessful due to limitations that can be addressed in future work.

As modern attacks become more stealthy and persistent, detecting or preventing them at their early stages becomes virtually impossible. Instead, an attack investigation or provenance system aims to continuously monitor and log interesting system events with minimal overhead. Later, if the system observes any anomalous behavior, it analyzes the log to identify who initiated the attack and which resources were affected by the attack and then assess and recover from any damage incurred. However, because of a fundamental tradeoff between log granularity and system performance, existing systems typically record system-call events without detailed program-level activities (e.g., memory operation) required for accurately reconstructing attack causality or demand that every monitored program be instrumented to provide program-level information.

Because mobile apps are extremely popular and often mission critical nowadays, companies invest a great deal of resources in testing the apps they provide to their customers. Testing is particularly important for Android apps, which must run on a multitude of devices and operating system versions. Unfortunately, as we confirmed in many interviews with quality assurance professionals, app testing is today a very human intensive, and therefore tedious and error prone, activity. To address this problem, and better support testing of Android apps, we propose a new technique that allows testers to easily create platform independent test scripts for an app and automatically run the generated test scripts on multiple devices and operating system versions. The technique does so without modifying the app under test or the runtime system, by (1) intercepting the interactions of the tester with the app and (2) providing the tester with an intuitive way to specify expected results that it then encode as test oracles. We implemented our technique in a tool named Barista and used the tool to evaluate the practical usefulness and applicability of our approach. Our results show that Barista (1) can faithfully encode user defined test cases as test scripts with built-in oracles that can run on multiple platforms and (2) outperforms two popular tools with similar functionality. Barista and our experimental infrastructure are publicly available.

Software testing is the most widely used approach for assessing and improving software quality, but it is inherently incomplete and may not be representative of how the software is used in the field. This paper addresses the questions of to what extent tests represent how real users use software, and how to measure behavioral differences between test and field executions. We study four real-world systems, one used by endusers and three used by other (client) software, and compare test suites written by the systems' developers to field executions using four models of behavior: statement coverage, method coverage, mutation score, and a temporal-invariant-based model we developed. We find that developer-written test suites fail to accurately represent field executions: the tests, on average, miss 6.2% of the statements and 7.7% of the methods exercised in the field, the behavior exercised only in the field kills an extra 8.6% of the mutants, finally, the tests miss 52.6% of the behavioral invariants that occur in the field. In addition, augmenting the in-house test suites with automatically-generated tests by a tool targeting high code coverage only marginally improves the tests' behavioral representativeness. These differences between field and test executions—and in particular the finer-grained and more sophisticated ones that we measured using our invariantbased model—can provide insight for developers and suggest a better method for measuring test suite quality.

Testing of Android apps is particularly challenging due to the fragmentation of the Android ecosystem in terms of both devices and operating system versions. Developers must in fact ensure not only that their apps behave as expected, but also that the apps' behavior is consistent across platforms. To support this task, we propose DiffDroid, a new technique that helps developers automatically find cross-platform inconsistencies (CPIs) in mobile apps. DiffDroid combines input generation and differential testing to compare the behavior of an app on different platforms and identify possible inconsistencies. Given an app, DiffDroid (1) generates test inputs for the app, (2) runs the app with these inputs on a reference device and builds a model of the app behavior, (3) runs the app with the same inputs on a set of other devices, and (4) compares the behavior of the app on these different devices with the model of its behavior on the reference device. We implemented DiFFDRoiD and performed an evaluation of our approach on 5 benchmarks and over 130 platforms. our results show that DiFFDRoiD can identify CPis on real apps efficiently and with a limited number of false positives. DiFFDRoiD and our experimental infrastructure are publicly available.

This paper presents an approach for zero-overhead profiling (ZOP). ZOP accomplishes accurate program profiling with no modification to the program or system during profiling and no dedicated hardware features. To do so, ZOP records the electromagnetic (EM) emanations generated by computing systems during program execution and analyzes the recorded emanations to track a program’s execution path and generate profiling information. Our approach consists of two main phases. In the training phase, ZOP instruments the program and runs it against a set of inputs to collect path timing information while simultaneously collecting waveforms for the EM emanations generated by the program. In the profiling phase, ZOP runs the original (i.e., uninstrumented and unmodified) program against inputs whose executions need to be profiled, records the waveforms produced by the program, and matches these waveforms with those collected during training to predict which parts of the code were exercised by the inputs and how often. We evaluated an implementation of ZOP on several benchmarks and our results show that ZOP can predict path profiling information for these benchmarks with greater than 94% accuracy on average.

Web applications often handle sensitive user data, which makes them attractive targets for attacks such as cross-site scripting (XSS). Content security policy (CSP) is a content-restriction mechanism, now supported by all major browsers, that offers thorough protection against XSS. Unfortunately, simply enabling CSP for a web application would affect the application's behavior and likely disrupt its functionality. To address this issue, we propose AutoCSP, an automated technique for retrofitting CSP to web applications. AutoCSP (1) leverages dynamic taint analysis to identify which content should be allowed to load on the dynamically-generated HTML pages of a web application and (2) automatically modifies the server-side code to generate such pages with the right permissions. Our evaluation, performed on a set of real-world web applications, shows that AutoCSP can retrofit CSP effectively and efficiently.

Software debugging is tedious and time consuming. To reduce the manual effort needed for debugging, researchers have proposed a considerable number of techniques to automate the process of fault localization; in particular, techniques based on information retrieval (IR) have drawn increased attention in recent years. Although reportedly effective, these techniques have some potential limitations that may affect their performance. First, their effectiveness is likely to depend heavily on the quality of the bug reports; unfortunately, high-quality bug reports that contain rich information are not always available. Second, these techniques have not been evaluated through studies that involve actual developers, which is less than ideal, as purely analytical evaluations can hardly show the actual usefulness of debugging techniques. The goal of this work is to evaluate the usefulness of IR-based techniques in real-world scenarios. Our investigation shows that bug reports do not always contain rich information, and that low-quality bug reports can considerably affect the effectiveness of these techniques. Our research also shows, through a user study, that high-quality bug reports benefit developers just as much as they benefit IR-based techniques. In fact, the information provided by IR-based techniques when operating on high-quality reports is only helpful to developers in a limited number of cases. And even in these cases, such information only helps developers get to the faulty file quickly, but does not help them in their most time consuming task: understanding and fixing the bug within that file.

Like all software, mobile applications ("apps") must be adequately tested to gain confidence that they behave correctly. Therefore, in recent years, researchers and practitioners alike have begun to investigate ways to automate apps testing. In particular, because of Android's open source nature and its large share of the market, a great deal of research has been performed on input generation techniques for apps that run on the Android operating systems. At this point in time, there are in fact a number of such techniques in the literature, which differ in the way they generate inputs, the strategy they use to explore the behavior of the app under test, and the specific heuristics they use. To better understand the strengths and weaknesses of these existing approaches, and get general insight on ways they could be made more effective, in this paper we perform a thorough comparison of the main existing test input generation tools for Android. In our comparison, we evaluate the effectiveness of these tools, and their corresponding techniques, according to four metrics: ease of use, ability to work on multiple platforms, code coverage, and ability to detect faults. Our results provide a clear picture of the state of the art in input generation for Android apps and identify future research directions that, if suitably investigated, could lead to more effective and efficient testing tools for Android.

The structure of preferences for modern highly-configurable software systems has become extremely complex, usually consisting of multiple layers of access that go from the user interface down to the lowest levels of the source code. This complexity can lead to inconsistencies between layers, especially during software evolution. For example, there may be preferences that users can change through the GUI, but that have no effect on the actual behavior of the system because the related source code is not present or has been removed going from one version to the next. These inconsistencies may result in unexpected program behaviors, which range in severity from mild annoyances to more critical security or performance problems. To address this problem, we present SCIC (Software Configuration Inconsistency Checker), a static analysis technique that can automatically detect these kinds of inconsistencies. Unlike other configuration analysis tools, SCIC can handle software that (1) is written in multiple programming languages and (2) has a complex preference structure. In an empirical evaluation that we performed on 10 years worth of versions of both the widely used Mozilla Core and Firefox, SCIC was able to find 40 real inconsistencies (some determined as severe), whose lifetime spanned multiple versions, and whose detection required the analysis of code written in multiple languages.

This special issue includes extended versions of four of the best papers of ICST 2013. The conference attracted over 150 submissions, including both research and industry papers, which demonstrates the strong ongoing interest in the field. Each submission was evaluated by at least three members of the Technical Program Committee. Based on these reviews, and on extensive on-line discussions involving the entire technical Program Committee, we finally accepted 30 research papers and eight industry papers, two of which were short. The selected papers cover a variety of topics, including test-input generation, formal verification, mutation testing, debugging, fault localization and repair, concurrency testing, model based testing, test-case selection, prioritization and minimization, program analysis, and crowdsourcing based testing. After selecting these 30 papers, the entire Technical Program Committee voted to select the best papers amongst the ones accepted. The vote focused on a selection of papers that had at least one strong champion and did not receive any negative scores. Votes had to consider the scores, the relevance of the paper, and the originality of the work. The five papers that received the highest number of votes were invited for this special issue. The authors of one of the papers declined the invitation; revised versions of the other four papers went through the standard STVR review process and are included here. In the rest of this foreword, we summarize these four contributions. In the paper “Are Concurrent Coverage Metrics Effective for Testing: A Comprehensive Empirical Investigation,” Hong and colleagues explore the impact of concurrent coverage metrics on testing effectiveness. They also examine the relationship between coverage, fault detection, and test suite size. Their results (1) indicate that the metrics are moderate to strong predictors of concurrent testing effectiveness and (2) highlight the need for additional work on concurrent coverage. In the paper ”Coverage-Based Regression Test Case Selection, Minimisation and Prioritisation: An Industrial Case Study,” Di Nardo and colleagues apply coverage-based regression testing techniques on a real-world system with real regression faults. Their main insight is that test suite minimization performed using finer grained coverage criteria can provide a good trade-off between savings in execution cost and fault-detection capability. In the paper “CHECK-THEN-ACT Misuse of Java Concurrent Collections,” Lin and colleagues present an extensive empirical study of CHECK-THEN-ACT idioms in Java concurrent collections. Their analysis of 6.4M lines of code that use Java concurrent collections shows that (1) CHECK-THEN-ACT idioms are commonly misused in practice, and (2) correcting them is important. In the paper “Defect Prediction as a Multi-Objective Optimization Problem,” Canfora and colleagues formalize the defect prediction problem as a multi-objective optimization problem. Their multi-objective approach allows software engineers to choose predictors that achieve a specific trade-off between the number of likely defect-prone classes and the number of lines of code to be analyzed/tested. Many members of our community contributed to this special issue and we would like to extend our most heartfelt thanks to everyone who worked hard to make this possible. In particular, we want to thank the authors, who devoted significant time and effort to extending their ICST papers. We also want to thank the reviewers, who wrote detailed reviews and provided extremely valuable feedback that the authors took into account when preparing the final version of the papers that are presented here.

As confirmed by a recent survey conducted among developers of the Apache, Eclipse, and Mozilla projects, two extremely challenging tasks during maintenance are reproducing and debugging field failures—failures that occur on user machines after release. To help developers with these tasks, in this article we present an overall approach that comprises two different techniques: B ug R edux and F 3 . B ug R edux is a general technique for reproducing field failures that collects dynamic data about failing executions in the field and uses this data to synthesize executions that mimic the observed field failures. F 3 leverages the executions generated by B ug R edux to perform automated debugging using a set of suitably optimized fault-localization techniques. To assess the usefulness of our approach, we performed an empirical evaluation of the approach on a set of real-world programs and field failures. The results of our evaluation are promising in that, for all the failures considered, our approach was able to (1) synthesize failing executions that mimicked the observed field failures, (2) synthesize passing executions similar to the failing ones, and (3) use the synthesized executions to successfully perform fault localization with accurate results.

Being able to automatically repair programs is at the same time a very compelling vision and an extremely challenging task. In this paper, we present MintHint, a novel technique for program repair that is a departure from most of today’s approaches. Instead of trying to fully automate program repair, which is often an unachievable goal, MintHint performs statistical correlation analysis to identify expressions that are likely to occur in the repaired code and generates, using pattern-matching based synthesis, repair hints from these expressions. Intuitively, these hints suggest how to rectify a faulty statement and help developers find a complete, actual repair.

To isolate and fix failures that occur in the field, after deployment, developers must be able to reproduce and investigate such failures in-house. In practice, however, bug reports rarely provide enough information to recreate field failures, thus making in-house debugging an arduous task. This task becomes even more challenging for programs whose input must adhere to a formal specification, such as a grammar. To help developers address this issue, we propose an approach for automatically generating inputs that recreate field failures in-house. Given a faulty program and a field failure for this program, our approach exploits the potential of grammar-guided genetic programming to iteratively find legal inputs that can trigger the observed failure using a limited amount of runtime data collected in the field. When applied to 11 failures of 5 real-world programs, our approach was able to reproduce all but one of the failures while imposing a limited amount of overhead.

With the emergence of new computing platforms, software written for traditional platforms is being re-targeted to reach the users on these new platforms. In particular, due to the proliferation of mobile computing devices, it is common practice for companies to build mobile-specific versions of their existing web applications to provide mobile users with a better experience. Because the differences between desktop and mobile versions of a web application are not only cosmetic, but can also include substantial rewrites of key components, it is not uncommon for these different versions to provide different sets of features. Whereas some of these differences are intentional, such as the addition of location-based features on mobile devices, others are not and can negatively affect the user experience, as confirmed by numerous user reports and complaints. Unfortunately, checking and maintaining the consistency of different versions of an application by hand is not only time consuming, but also error prone. To address this problem, and help developers in this difficult task, we propose an automated technique for matching features across different versions of a multi-platform web application. We implemented our technique in a tool, called FMAP, and used it to perform a preliminary empirical evaluation on nine real-world multi-platform web applications. The results of our evaluation are promising, as FMAP was able to correctly identify missing features between desktop and mobile versions of the web applications considered, as confirmed by our analysis of user reports and software fixes for these applications.

Web applications are popular among developers because of the ease of development and deployment through the ubiquitous web browsing platform. However, differences in a web application's execution across different web browsers manifest as Cross-browser Inconsistencies (XBIs), which are a serious concern for web developers. Testing for XBIs manually is a laborious and error-prone process. In this demo we present X-PERT, which is a tool to identify XBIs in web applications automatically, without requiring any effort from the developer. X-PERT implements a comprehensive technique to identify XBIs and has been found to be effective in detecting real-world XBIs in our empirical evaluation. The source code of X-PERT and XBI reports from our evaluation are available at http://gatech.github.io/xpert.

Automated debugging techniques aim to help developers locate and understand the cause of a failure, an extremely challenging yet fundamental task. Most state-of-the-art approaches suffer from two problems: they require a large number of passing and failing tests and report possible faulty code with no explanation. To mitigate these issues, we present MIMIC, a novel automated debugging technique that combines and extends our previous input generation and anomaly detection techniques. MIMIC (1) synthesizes multiple passing and failing executions similar to an observed failure and (2) uses these executions to detect anomalies in behavior that may explain the failure. We evaluated MIMIC on six failures of real-world programs with promising results: for five of these failures, MIMIC identified their root causes while producing a limited number of false positives. Most importantly, the anomalies identified by MIMIC provided information that may help developers understand (and ultimately eliminate) such root causes.

Due to the increasing popularity of web applications, and the number of browsers and platforms on which such applications can be executed, cross-browser incompatibilities (XBIs) are becoming a serious concern for organizations that develop web-based software. Most of the techniques for XBI detection developed to date are either manual, and thus costly and error-prone, or partial and imprecise, and thus prone to generating both false positives and false negatives. To address these limitations of existing techniques, we developed X-PERT, a new automated, precise, and comprehensive approach for XBI detection. X-PERT combines several new and existing differencing techniques and is based on our findings from an extensive study of XBIs in real-world web applications. The key strength of our approach is that it handles each aspects of a web application using the differencing technique that is best suited to accurately detect XBIs related to that aspect. Our empirical evaluation shows that X-PERT is effective in detecting real-world XBIs, improves on the state of the art, and can provide useful support to developers for the diagnosis and (eventually) elimination of XBIs.

Test suites, just like the applications they are testing, evolve throughout their lifetime. One of the main reasons for test-suite evolution is test obsolescence: test cases cease to work because of changes in the code and must be suitably repaired. There are several reasons why it is important to achieve a thorough understanding of how test cases evolve in practice. In particular, researchers who investigate automated test repair - an increasingly active research area - can use such understanding to develop more effective repair techniques that can be successfully applied in real-world scenarios. More generally, analyzing testsuite evolution can help testers better understand how test cases are modified during maintenance and improve the test evolution process, an extremely time consuming activity for any nontrivial test suite. Unfortunately, there are no existing tools that facilitate investigation of test evolution. To tackle this problem, we developed TestEvol, a tool that enables the systematic study of test-suite evolution for Java programs and JUnit test cases. This demonstration presents TestEvol and illustrates its usefulness and practical applicability by showing how TestEvol can be successfully used on real-world software and test suites. Demo video at http://www.cc.gatech.edu/~orso/software/testevol/.

Reproducing and debugging field failures--failures that occur on user machines after release--are challenging tasks for developers. To help the first task, in previous work we have proposed BugRedux, a technique for reproducing, in-house, failures observed in the field. Although BugRedux can help developers reproduce field failures, it does not provide any specific support for debugging such failures. To address this limitation, in this paper we present F3, a novel technique that builds on BugRedux and extends it with support for fault localization. Specifically, in F3 we extend our previous technique in two main ways: first, we modify BugRedux so that it generates multiple failing and passing executions "similar" to the observed field failure; second, we add to BugRedux debugging capabilities by combining it with a customized fault-localization technique. The results of our empirical evaluation, performed on a set of real-world programs and field failures, are promising: for all the failures considered, F3 was able to (1) synthesize passing and failing executions and (2) successfully use the synthesized executions to perform fault localization and, ultimately, help debugging.

Reproducing field failures in-house, a step developers must perform when assigned a bug report, is an arduous task. In most cases, developers must be able to reproduce a reported failure using only a stack trace and/or some informal description of the failure. The problem becomes even harder for the large class of programs whose input is highly structured and strictly specified by a grammar. To address this problem, we present SBFR, a search-based failure-reproduction technique for programs with structured input. SBFR formulates failure reproduction as a search problem. Starting from a reported failure and a limited amount of dynamic information about the failure, SBFR exploits the potential of genetic programming to iteratively find legal inputs that can trigger the failure.

SUMMARY Plug‐ins have become an important part of today's Integrated Development Environments (IDEs). They are useful not only for extending the IDEs’ functionality but also for customizing the IDEs for different types of projects. In this paper, we discuss some features that IDEs should provide to support the development of a specific kind of plug‐ins—plug‐ins that implement program analysis and software testing techniques. To guide the discussion, we first provide a survey of existing testing and analysis plug‐ins and, for each of these plug‐ins, discuss the details of the IDE support they use. We then present a case study based on our personal experience with building a regression‐testing plug‐in for two different IDEs. Finally, we use our findings to make a generalized discussion on the kind of capabilities a platform should provide to better support the development of program analysis and software testing plug‐ins.Copyright © 2012 John Wiley & Sons, Ltd.

A recent survey conducted among developers of the Apache, Eclipse, and Mozilla projects showed that the ability to recreate field failures is considered of fundamental importance when investigating bug reports. Unfortunately, the information typically contained in a bug report, such as memory dumps or call stacks, is usually insufficient for recreating the problem. Even more advanced approaches for gathering field data and help in-house debugging tend to collect either too little information, and be ineffective, or too much information, and be inefficient. To address these issues, we present BugRedux, a novel general approach for in-house debugging of field failures. BugRedux aims to synthesize, using execution data collected in the field, executions that mimic the observed field failures. We define several instances of BugRedux that collect different types of execution data and perform, through an empirical study, a cost-benefit analysis of the approach and its variations. In the study, we apply BugRedux to 16 failures of 14 real-world programs. Our results are promising in that they show that it is possible to synthesize in-house executions that reproduce failures observed in the field using a suitable set of execution data.

The workshops of ICSE 2012 provide a forum for researchers and practitioners to exchange and discuss scientific ideas before they have matured to warrant conzference or journal publication. ICSE Workshops also serve as incubators for scientific communities that form and share a particular research agenda.

One of the consequences of the continuous and rapid evolution of web technologies is the amount of inconsistencies between web browsers implementations. Such inconsistencies can result in cross-browser incompatibilities (XBIs)-situations in which the same web application can behave differently when run on different browsers. In some cases, XBIs consist of tolerable cosmetic differences. In other cases, however, they may completely prevent users from accessing part of a web application's functionality. Despite the prevalence of XBIs, there are hardly any tools that can help web developers detect and correct such issues. In fact, most existing approaches against XBIs involve a considerable amount of manual effort and are consequently extremely time consuming and error prone. In recent work, we have presented two complementary approaches, WEBDIFF and CROSST, for automatically detecting and reporting XBIs. In this paper, we present CROSSCHECK, a more powerful and comprehensive technique and tool for XBI detection that combines and adapts these two approaches in a way that leverages their respective strengths. The paper also presents an empirical evaluation of CROSSCHECK on a set of real-world web applications. The results of our experiments show that CROSSCHECK is both effective and efficient in detecting XBIs, and that it can outperform existing techniques.

Since web applications are easily accessible, and often store a large amount of sensitive user information, they are a common target for attackers. In particular, attacks that focus on input validation vulnerabilities are extremely effective and dangerous. To address this problem, we developed ViewPoints--a technique that can identify erroneous or insufficient validation and sanitization of the user inputs by automatically discovering inconsistencies between client- and server-side input validation functions. Developers typically perform redundant input validation in both the front-end (client) and the back-end (server) components of a web application. Client- side validation is used to improve the responsiveness of the application, as it allows for responding without communicating with the server, whereas server-side validation is necessary for security reasons, as malicious users can easily circumvent client-side checks. ViewPoints (1) automatically extracts client- and server-side input validation functions, (2) models them as deterministic finite automata (DFAs), and (3) compares client- and server-side DFAs to identify and report the inconsistencies between the two sets of checks. Our initial evaluation of the technique is promising: when applied to a set of real-world web applications, ViewPoints was able to automatically identify a large number of inconsistencies in their input validation functions.

To manage and integrate information gathered from heterogeneous databases, an ontology is often used. Like all systems, ontology-driven systems evolve over time and must be regression tested to gain confidence in the behavior of the modified system. Because rerunning all existing tests can be extremely expensive, researchers have developed regression-test-selection (RTS) techniques that select a subset of the available tests that are affected by the changes, and use this subset to test the modified system. Existing RTS techniques have been shown to be effective, but they operate on the code and are unable to handle changes that involve ontologies. To address this limitation, we developed and present in this paper a novel RTS technique that targets ontology-driven systems. Our technique creates representations of the old and new ontologies, compares them to identify entities affected by the changes, and uses this information to select the subset of tests to rerun. We also describe in this paper OntoRetest, a tool that implements our technique and that we used to empirically evaluate our approach on two biomedical ontology-driven database systems. The results of our evaluation show that our technique is both efficient and effective in selecting tests to rerun and in reducing the overall time required to perform regression testing.

Manual debugging is driven by experiments—test runs that narrow down failure causes by systematically confirming or excluding individual factors. The BUGEX approach leverages test case generation to systematically isolate such causes from a single failing test run—causes such as properties of execution states or branches taken that correlate with the failure. Identifying these causes allows for deriving conclusions as: “The failure occurs whenever the daylight savings time starts at midnight local time.” In our evaluation, a prototype of BUGEX precisely pinpointed important failure explaining facts for six out of seven real-life bugs.

Test suites, once created, rarely remain static. Just like the application they are testing, they evolve throughout their lifetime. Test obsolescence is probably the most known reason for test-suite evolution---test cases cease to work because of changes in the code and must be suitably repaired. Repairing existing test cases manually, however, can be extremely time consuming, especially for large test suites, which has motivated the recent development of automated test-repair techniques. We believe that, for developing effective repair techniques that are applicable in real-world scenarios, a fundamental prerequisite is a thorough understanding of how test cases evolve in practice. Without such knowledge, we risk to develop techniques that may work well for only a small number of tests or, worse, that may not work at all in most realistic cases. Unfortunately, to date there are no studies in the literature that investigate how test suites evolve. To tackle this problem, in this paper we present a technique for studying test-suite evolution, a tool that implements the technique, and an extensive empirical study in which we used our technique to study many versions of six real-world programs and their unit test suites. This is the first study of this kind, and our results reveal several interesting aspects of test-suite evolution. In particular, our findings show that test repair is just one possible reason for test-suite evolution, whereas most changes involve refactorings, deletions, and additions of test cases. Our results also show that test modifications tend to involve complex, and hard-to-automate, changes to test cases, and that existing test-repair techniques that focus exclusively on assertions may have limited practical applicability. More generally, our findings provide initial insight on how test cases are added, removed, and modified in practice, and can guide future research efforts in the area of test-suite evolution.

Programs written in languages allowing direct access to memory through pointers often contain memory-related faults, which cause nondeterministic failures and security vulnerabilities. We present a new dynamic tainting technique to detect illegal memory accesses. When memory is allocated, at runtime, we taint both the memory and the corresponding pointer using the same taint mark. Taint marks are then propagated and checked every time a memory address m is accessed through a pointer p; if the associated taint marks differ, an illegal access is reported. To allow always-on checking using a low overhead, hardware-assisted implementation, we make several key technical decisions. We use a configurable, low number of reusable taint marks instead of a unique mark for each allocated area of memory, reducing the performance overhead without losing the ability to target most memory-related faults. We also define the technique at the binary level, which helps handle applications using third-party libraries whose source code is unavailable. We created a software-only prototype of our technique and simulated a hardware-assisted implementation. Our results show that 1) it identifies a large class of memory-related faults, even when using only two unique taint marks, and 2) a hardware-assisted implementation can achieve performance overheads in single-digit percentages.

The articles in this special section contain selected papers from the International Symposium on Software Testing and Analysis 2010.

Privacy and security concerns have adversely affected the usefulness of many types of techniques that leverage information gathered from deployed applications. To address this issue, we present an approach for automatically anonymizing failure-inducing inputs that builds on a previously developed technique. Given an input I that causes a failure f, our approach generates an anonymized input I′ that is different from I but still causes f. I′ can thus be sent to developers to enable them to debug f without having to know I. We implemented our approach in a prototype tool, camouflage, and performed an extensive empirical evaluation where we applied camouflage to a large set of failure-inducing inputs for several real applications. The results of the evaluation are promising, as they show that camouflage is both practical and effective at generating anonymized inputs; for the inputs that we considered, I and I′ shared no sensitive information. The results also show that our approach can outperform the general technique it extends.

Regression testing is an important activity performed to validate modified software, and one of its key tasks is regression test selection (RTS) -- selecting a subset of existing test cases to run on the modified software. Most existing RTS techniques focus on changes made to code components and completely ignore non-code elements, such as configuration files and databases, which can also change and affect the system behavior. To address this issue, we present a new RTS technique that performs accurate test selection in the presence of changes to non-code components. To do this, our technique computes traceability between test cases and the external data accessed by an application, and uses this information to perform RTS in the presence of changes to non-code elements. We present our technique, a prototype implementation of our technique, and a set of preliminary empirical results that illustrate the feasibility, effectiveness, and potential usefulness of our approach.

Typically, dynamic-analysis techniques operate on a small subset of all possible program behaviors, which limits their effectiveness and the representativeness of the computed results. To address this issue, a new paradigm is emerging: execution hijacking, consisting of techniques that explore a larger set of program behaviors by forcing executions along specific paths. Although hijacked executions are infeasible for the given inputs, they can still produce feasible behaviors that could be observed under other inputs. In such cases, execution hijacking can improve the effectiveness of dynamic analysis without requiring the (expensive) generation of additional inputs. To evaluate the usefulness of execution hijacking, we defined, implemented, and evaluated several variants of it. Specifically, we performed an empirical study where we assessed whether execution hijacking could improve the effectiveness of a common dynamic analysis: memory error detection. The results of the study show that execution hijacking, if suitably performed, can indeed improve dynamic analysis.

Debugging is notoriously difficult and extremely time consuming. Researchers have therefore invested a considerable amount of effort in developing automated techniques and tools for supporting various debugging tasks. Although potentially useful, most of these techniques have yet to demonstrate their practical effectiveness. One common limitation of existing approaches, for instance, is their reliance on a set of strong assumptions on how developers behave when debugging (e.g., the fact that examining a faulty statement in isolation is enough for a developer to understand and fix the corresponding bug). In more general terms, most existing techniques just focus on selecting subsets of potentially faulty statements and ranking them according to some criterion. By doing so, they ignore the fact that understanding the root cause of a failure typically involves complex activities, such as navigating program dependencies and rerunning the program with different inputs. The overall goal of this research is to investigate how developers use and benefit from automated debugging tools through a set of human studies. As a first step in this direction, we perform a preliminary study on a set of developers by providing them with an automated debugging tool and two tasks to be performed with and without the tool. Our results provide initial evidence that several assumptions made by automated debugging techniques do not hold in practice. Through an analysis of the results, we also provide insights on potential directions for future work in the area of automated debugging.

Abstract Penetration testing is widely used to help ensure the security of web applications. Using penetration testing, testers discover vulnerabilities by simulating attacks on a target web application. To do this efficiently, testers rely on automated techniques that gather input vector information about the target web application and analyze the application's responses to determine whether an attack was successful. Techniques for performing these steps are often incomplete, which can leave parts of the web application untested and vulnerabilities undiscovered. This paper proposes a new approach to penetration testing that addresses the limitations of current techniques. The approach incorporates two recently developed analysis techniques to improve input vector identification and detect when attacks have been successful against a web application. This paper compares the proposed approach against two popular penetration testing tools for a suite of web applications with known and unknown vulnerabilities. The evaluation results show that the proposed approach performs a more thorough penetration testing and leads to the discovery of more vulnerabilities than both the tools. Copyright © 2011 John Wiley & Sons, Ltd.

Most existing leak detection techniques for C and C++ applications only detect the existence of memory leaks. They do not provide any help for fixing the underlying memory management errors. In this paper, we present a new technique that not only detects leaks, but also points developers to the locations where the underlying errors may be fixed. Our technique tracks pointers to dynamically-allocated areas of memory and, for each memory area, records several pieces of relevant information. This information is used to identify the locations in an execution where memory leaks occur. To investigate our technique's feasibility and usefulness, we developed a prototype tool called LEAKPOINT and used it to perform an empirical evaluation. The results of this evaluation show that LEAKPOINT detects at least as many leaks as existing tools, reports zero false positives, and, most importantly, can be effective at helping developers fix the underlying memory management errors.

Cross-browser (and cross-platform) issues are prevalent in modern web based applications and range from minor cosmetic bugs to critical functional failures. In spite of the relevance of these issues, cross-browser testing of web applications is still a fairly immature field. Existing tools and techniques require a considerable manual effort to identify such issues and provide limited support to developers for fixing the underlying cause of the issues. To address these limitations, we propose a technique for automatically detecting cross-browser issues and assisting their diagnosis. Our approach is dynamic and is based on differential testing. It compares the behavior of a web application in different web browsers, identifies differences in behavior as potential issues, and reports them to the developers. Given a page to be analyzed, the comparison is performed by combining a structural analysis of the information in the page's DOM and a visual analysis of the page's appearance, obtained through screen captures. To evaluate the usefulness of our approach, we implemented our technique in a tool, called WEBDIFF, and used WEBDIFF to identify cross-browser issues in nine real web applications. The results of our evaluation are promising, in that WEBDIFF was able to automatically identify 121 issues in the applications, while generating only 21 false positives. Moreover, many of these false positives are due to limitations in the current implementation of WEBDIFF and could be eliminated with suitable engineering.

Web applications have gained increased popularity in the past decade due to the ubiquity of the web browser across platforms. With the rapid evolution of web technologies, the complexity of web applications has also grown, making maintenance tasks harder. In particular, maintaining cross-browser compliance is a challenging task for web developers, as they must test their application on a variety of browsers and platforms. Existing tools provide some support for this kind of test, but developers are still required to identify and fix cross-browser issues mainly through manual inspection. Our WEBDIFF tool addresses the limitations of existing tools by (1) automatically comparing the structural and visual characteristics of web pages when they are rendered in different browsers, and (2) reporting potential differences to developers. When used on nine real web pages, WEBDIFF automatically identified 121 issues, out of which 100 were actual problems. In this demo, we will present WEBDIFF, its underlying technology, and several examples of its use on real applications.

When a program is modified during software evolution, developers typically run the new version of the program against its existing test suite to validate that the changes made on the program did not introduce unintended side effects (i.e., regression faults). This kind of regression testing can be effective in identifying some regression faults, but it is limited by the quality of the existing test suite. Due to the cost of testing, developers build test suites by finding acceptable tradeoffs between cost and thoroughness of the tests. As a result, these test suites tend to exercise only a small subset of the program's functionality and may be inadequate for testing the changes in a program. To address this issue, we propose a novel approach called Behavioral Regression Testing (BERT). Given two versions of a program, BERT identifies behavioral differences between the two versions through dynamical analysis, in three steps. First, it generates a large number of test inputs that focus on the changed parts of the code. Second, it runs the generated test inputs on the old and new versions of the code and identifies differences in the tests' behavior. Third, it analyzes the identified differences and presents them to the developers. By focusing on a subset of the code and leveraging differential behavior, BERT can provide developers with more (and more detailed) information than traditional regression testing techniques. To evaluate BERT, we implemented it as a plug-in for Eclipse, a popular Integrated Development Environment, and used the plug-in to perform a preliminary study on two programs. The results of our study are promising, in that BERT was able to identify true regression faults in the programs.

Developers often make multiple changes to software. These changes are introduced to work cooperatively or to accomplish separate goals. However, changes might not interact as expected or may produce undesired side effects. Thus, it is crucial for software-development tasks to know exactly which changes interact. For example, testers need this information to ensure that regression test suites test the combined behaviors of changes. For another example, teams of developers must determine whether it is safe to merge variants of a program modified in parallel. Existing techniques can be used to detect at runtime potential interactions among changes, but these reports tend to be coarse and imprecise. To address this problem, in this paper, we first present a formal model of change interactions at the code level, and then describe a new technique, based on this model, for detecting at runtime such interactions with accuracy. We also present the results of a comparison of our technique with other techniques on a set of Java subjects. Our results clearly suggest that existing techniques are too inaccurate and only our technique, of all those studied, provides acceptable confidence in detecting real change interactions occurring at runtime.

During maintenance, software is modified and evolved to enhance its functionality, eliminate faults, and adapt it to changed or new platforms. In this demo, we present BERT, a tool for helping developers identify regression faults that they may have introduced when modifying their code. BERT is based on the concept of behavioral regression testing: given two versions of a program, BERT identifies behavioral differences between the two versions through dynamic analysis, in three steps. First, it generates a large number of test inputs that focus on the changed parts of the code. Second, it runs the generated test inputs on the old and new versions of the code and identifies differences in the tests' behavior. Third, it analyzes the identified differences and presents them to the developers. By focusing on a subset of the code and leveraging differential behavior, BERT can provide developers with more detailed information than traditional regression testing approaches---approaches that rely exclusively on existing test suites, which may be limited in scope and may not adequately test the changes in a program. BERT is implemented as a plug-in for Eclipse, a popular Integrated Development Environment, and is freely available. This demo presents BERT, its underlying technology, and examples of its usage.

Test-suite minimization techniques aim to eliminate redundant test cases from a test-suite based on some criteria, such as coverage or fault-detection capability. Most existing test-suite minimization techniques have two main limitations: they perform minimization based on a single criterion and produce suboptimal solutions. In this paper, we propose a test-suite minimization framework that overcomes these limitations by allowing testers to (1) easily encode a wide spectrum of test-suite minimization problems, (2) handle problems that involve any number of criteria, and (3) compute optimal solutions by leveraging modern integer linear programming solvers. We implemented our framework in a tool, called MINTS, that is freely-available and can be interfaced with a number of different state-of-the-art solvers. Our empirical evaluation shows that MINTS can be used to instantiate a number of different test-suite minimization problems and efficiently find an optimal solution for such problems using different solvers.

Penetration testing is widely used to help ensure the security of web applications. It discovers vulnerabilities by simulating attacks from malicious users on a target application. Identifying the input vectors of a Web application and checking the results of an attack are important parts of penetration testing, as they indicate where an attack could be introduced and whether an attempted attack was successful. Current techniques for identifying input vectors and checking attack results are typically ad-hoc and incomplete, which can cause parts of an application to be untested and leave vulnerabilities undiscovered. In this paper, we propose a new approach to penetration testing that addresses these limitations by leveraging two recently-developed analysis techniques. The first is used to identify a web application's possible input vectors, and the second is used to automatically check whether an attack resulted in an injection. To empirically evaluate our approach, we compare it against a state-of-the-art, alternative technique. Our results show that our approach performs a more thorough penetration testing and leads to the discovery of more vulnerabilities.

Most existing automated debugging techniques focus on reducing the amount of code to be inspected and tend to ignore an important component of software failures: the inputs that cause the failure to manifest. In this paper, we present a new technique based on dynamic tainting for automatically identifying subsets of a program's inputs that are relevant to a failure. The technique (1) marks program inputs when they enter the application, (2) tracks them as they propagate during execution, and (3) identifies, for an observed failure, the subset of inputs that are potentially relevant for debugging that failure. To investigate feasibility and usefulness of our technique, we created a prototype tool, PENUMBRA, and used it to evaluate our technique on several failures in real programs. Our results are promising, as they show that PENUMBRA can point developers to inputs that are actually relevant for investigating a failure and can be more practical than existing alternative approaches.

As web applications become more widespread, sophisticated, and complex, automated quality assurance techniques for such applications have grown in importance. Accurate interface identification is fundamental for many of these techniques, as the components of a web application communicate extensively via implicitly-defined interfaces to generate customized and dynamic content. However, current techniques for identifying web application interfaces can be incomplete or imprecise, which hinders the effectiveness of quality assurance techniques. To address these limitations, we present a new approach for identifying web application interfaces that is based on a specialized form of symbolic execution. In our empirical evaluation, we show that the set of interfaces identified by our approach is more accurate than those identified by other approaches. We also show that this increased accuracy leads to improvements in several important quality assurance techniques for web applications: test-input generation, penetration testing, and invocation verification.

Most existing fault-localization techniques focus on identifying and reporting single statements that may contain a fault. Even in cases where a fault involves a single statement, it is generally hard to understand the fault by looking at that statement in isolation. Faults typically manifest themselves in a specific context, and knowing that context is necessary to diagnose and correct the fault. In this paper, we present a novel fault-localization technique that identifies sequences of statements that lead to a failure. The technique works by analyzing partial execution traces corresponding to failing executions and identifying common segments in these traces, incrementally. Our approach provides developers a context that is likely to result in a more directed approach to fault understanding and a lower overall cost for debugging.

One activity performed by developers during regression testing is test-suite augmentation, which consists of assessing the adequacy of a test suite after a program is modified and identifying new or modified behaviors that are not adequately exercised by the existing test suite and, thus, require additional test cases. In previous work, we proposed MATRIX, a technique for test-suite augmentation based on dependence analysis and partial symbolic execution. In this paper, we present the next step of our work, where we (I) improve the effectiveness of our technique by identifying all relevant change-propagation paths, (2) extend the technique to handle multiple and more complex changes, (3) introduce the first tool that fully implements the technique, and (4) present an empirical evaluation performed on real software. Our results show that our technique is practical and more effective than existing test-suite augmentation approaches in identifying test cases with high fault-detection capabilities.

Quality assurance techniques for web applications have be-come increasingly important as web applications have gained in popularity and become an essential part of our daily lives. To integrate content and data from multiple sources, the components of a web application communicate exten-sively among themselves. Unlike traditional program mod-ules, the components communicate through interfaces and invocations that are not explicitly declared. Because of this, the communication between two components can fail due to a parameter mismatch between the interface invoked by a calling component and the interface provided by the called component. Parameter mismatches can cause serious errors in the web application and are difficult to identify using tra-ditional testing and verification techniques. To address this problem, we propose a static-analysis based approach for identifying parameter mismatches. We also present an em-pirical evaluation of the approach, which we performed on a set of real web applications. The results of the evalua-tion are promising; our approach discovered 133 parameter mismatches in the subject applications.

Many software systems have evolved to include a web-based component that makes them available to the public via the Internet and can expose them to a variety of web-based attacks. One of these attacks is SQL injection, which can give attackers unrestricted access to the databases underlying web applications and has become increasingly frequent and serious. This paper presents a new, highly automated approach for protecting web applications against SQL injection that has both conceptual and practical advantages over most existing techniques. From a conceptual standpoint, the approach is based on the novel idea of positive tainting and on the concept of syntax-aware evaluation. From a practical standpoint, our technique is precise and efficient and has minimal deployment requirements. We also present an extensive empirical evaluation of our approach performed using WASP, a tool that implements our technique. In the evaluation, we used WASP to protect a wide range of web applications while subjecting them to a large and varied set of attacks and legitimate accesses. WASP was able to stop all attacks and did not generate any false positives. Our studies also show that the overhead imposed by WASP was negligible in most cases.

It is difficult to fully assess the quality of software in- house, outside the actual time and context in which it will execute after deployment. As a result, it is common for software to manifest field failures, failures that occur on user machines due to untested behavior. Field failures are typically difficult to recreate and investigate on developer platforms, and existing techniques based on crash reporting provide only limited support for this task. In this paper, we present a technique for recording, reproducing, and minimizing failing executions that enables and supports in- house debugging of field failures. We also present a tool that implements our technique and an empirical study that evaluates the technique on a widely used e-mail client.

Because of software's increasing dynamism and the heterogeneity of execution environments, the results of in-house testing and maintenance are often not representative of the way the software behaves in the field. To alleviate this problem, we present a technique for capturing and replaying partial executions of deployed software. Our technique can be used for various applications, including generation of test cases from user executions and post-mortem dynamic analysis. We present our technique and tool, some possible applications, and a preliminary empirical evaluation that provides initial evidence of the feasibility of our approach.

Dynamic taint analysis is gaining momentum. Techniques based on dynamic tainting have been successfully used in the context of application security, and now their use is also being explored in different areas, such as program understanding, software testing, and debugging. Unfortunately, most existing approaches for dynamic tainting are defined in an ad-hoc manner, which makes it difficult to extend them, experiment with them, and adapt them to new contexts. Moreover, most existing approaches are focused on data-flow based tainting only and do not consider tainting due to control flow, which limits their applicability outside the security domain. To address these limitations and foster experimentation with dynamic tainting techniques, we defined and developed a general framework for dynamic tainting that (1) is highly flexible and customizable, (2) allows for performing both data-flow and control-flow based tainting conservatively, and (3) does not rely on any customized run-time system. We also present DYTAN, an implementation of our framework that works on x86 executables, and a set of preliminary studies that show how DYTAN can be used to implement different tainting-based approaches with limited effort. In the studies, we also show that DYTAN can be used on real software, by using FIREFOX as one of our subjects, and illustrate how the specific characteristics of the tainting approach used can affect efficiency and accuracy of the taint analysis, which further justifies the use of our framework to experiment with different variants of an approach.

Programs written in languages that provide direct access tomemory through pointers often contain memory-related faults, which may cause non-deterministic failures and even security vulnerabilities. In this paper, we present a new technique based on dynamic tainting for protecting programs from illegal memory accesses. When memory is allocated, at runtime, our technique taints both the memory and the corresponding pointer using the same taint mark. Taint marks are then suitably propagated while the program executes and are checked every time a memory address m is accessed through a pointer p; if the taint marks associated with mand p differ, the execution is stopped and the illegalaccess is reported. To allow for a low-overhead, hardware-assisted implementation of the approach, we make several key technical and engineering decisions in the definition of our technique. In particular, we use a configurable, low number of reusable taint marks instead of a unique mark for each area of memory allocated, which reduces the overhead of the approach without limiting its flexibility and ability to target most memory-related faults and attacks known to date. We also define the technique at the binary level, which lets us handle the (very) common case of applications that use third-party libraries whose source code is unavailable. To investigate the effectiveness and practicality of our approach, we implemented it for heap-allocated memory and performed a preliminary empirical study on a set of programs. Our results show that (1) our technique can identify a large class of memory-related faults, even when using only two unique taint marks, and (2)a hardware-assisted implementation of the technique could achieve overhead in the single digits

With the growing complexity of web applications, identifying web interfaces that can be used for testing such applications has become increasingly challenging. Many techniques that work effectively when applied to simple web applications are insufficient when used on modern, dynamic web applications, and may ultimately result in inadequate testing of the applications' functionality. To address this issue, we present a technique for automatically discovering web application interfaces based on a novel static analysis algorithm. We also report the results of an empirical evaluation in which we compare our technique against a traditional approach. The results of the comparison show that our technique can (1) discover a higher number of interfaces and (2) help generate test inputs that achieve higher coverage.

Abstract Increasingly, modern‐day software systems are being built by combining externally‐developed software components with application‐specific code. For such systems, existing program‐analysis‐based software engineering techniques may not directly apply, due to lack of information about components. To address this problem, the use of component metadata has been proposed. Component metadata are metadata and metamethods provided with components, that retrieve or calculate information about those components. In particular, two component‐metadata‐based approaches for regression test selection are described: one using code‐based component metadata and the other using specification‐based component metadata. The results of empirical studies that illustrate the potential of these techniques to provide savings in re‐testing effort are provided. Copyright © 2006 John Wiley & Sons, Ltd.

There is an increasing interest in techniques that support analysis and measurement of fielded software systems. These techniques typically deploy numerous instrumented instances of a software system, collect execution data when the instances run in the field, and analyze the remotely collected data to better understand the system's in-the-field behavior. One common need for these techniques is the ability to distinguish execution outcomes (e.g., to collect only data corresponding to some behavior or to determine how often and under which condition a specific behavior occurs). Most current approaches, however, do not perform any kind of classification of remote executions and either focus on easily observable behaviors (e.g., crashes) or assume that outcomes' classifications are externally provided (e.g., by the users). To address the limitations of existing approaches, we have developed three techniques for automatically classifying execution data as belonging to one of several classes. In this paper, we introduce our techniques and apply them to the binary classification of passing and failing behaviors. Our three techniques impose different overheads on program instances and, thus, each is appropriate for different application scenarios. We performed several empirical studies to evaluate and refine our techniques and to investigate the trade-offs among them. Our results show that 1) the first technique can build very accurate models, but requires a complete set of execution data; 2) the second technique produces slightly less accurate models, but needs only a small fraction of the total execution data; and 3) the third technique allows for even further cost reductions by building the models incrementally, but requires some sequential ordering of the software instances' instrumentation.

AMNESIA is a tool that detects and prevents SQL injection attacks by combining static analysis and runtime monitoring. Empirical evaluation has shown that AMNESIA is both effective and efficient against SQL injection.

The testing of database applications poses new challenges for software engineers. In particular, it is difficult to thoroughly test the interactions between an application and its underlying database, which typically occur through dynamically-generated database commands. Because traditional code-based coverage criteria focus only on the application code, they are often inadequate in exercising these commands. To address this problem, we introduce a new test adequacy criterion that is based on coverage of the database commands generated by an application and specifically focuses on the application-database interactions. We describe the criterion, an analysis that computes the corresponding testing requirements, and an efficient technique for measuring coverage of these requirements. We also present a tool that implements our approach and a preliminary study that shows the approach's potential usefulness and feasibility

SQL injection attacks pose a serious threat to the security of Web applications because they can give attackers unrestricted access to databases that contain sensitive information. In this paper, we propose a new, highly automated approach for protecting existing Web applications against SQL injection. Our approach has both conceptual and practical advantages over most existing techniques. From the conceptual standpoint, the approach is based on the novel idea of positive tainting and the concept of syntax-aware evaluation. From the practical standpoint, our technique is at the same time precise and efficient and has minimal deployment requirements. The paper also describes wasp, a tool that implements our technique, and a set of studies performed to evaluate our approach. In the studies, we used our tool to protect several Web applications and then subjected them to a large and varied set of attacks and legitimate accesses. The evaluation was a complete success: wasp successfully and efficiently stopped all of the attacks without generating any false positives.

As software evolves, impact analysis estimates the potential effects of changes, before or after they are made, by identifying which parts of the software may be affected by such changes. Traditional impact-analysis techniques are based on static analysis and, due to their conservative assumptions, tend to identify most of the software as affected by the changes. More recently, researchers have begun to investigate dynamic impact-analysis techniques, which rely on dynamic, rather than static, information about software behavior. Existing dynamic impact-analysis techniques are either very expensive---in terms of execution overhead or amount of dynamic information collected---or imprecise. In this paper, we present a new technique for dynamic impact analysis that is almost as efficient as the most efficient existing technique and is as precise as the most precise existing technique. The technique is based on a novel algorithm that collects (and analyzes) only the essential dynamic information required for the analysis. We discuss our technique, prove its correctness, and present a set of empirical studies in which we compare our new technique with two existing techniques, in terms of performance and precision.

The use of web applications has become increasingly popular in our routine activities, such as reading the news, paying bills, and shopping on-line. As the availability of these services grows, we are witnessing an increase in the number and sophistication of attacks that target them. In particular, SQL injection, a class of code-injection attacks in which specially crafted input strings result in illegal queries to a database, has become one of the most serious threats to web applications. In this paper we present and evaluate a new technique for detecting and preventing SQL injection attacks. Our technique uses a model-based approach to detect illegal queries before they are executed on the database. In its static part, the technique uses program analysis to automatically build a model of the legitimate queries that could be generated by the application. In its dynamic part, the technique uses runtime monitoring to inspect the dynamically-generated queries and check them against the statically-built model. We developed a tool, AMNESIA, that implements our technique and used the tool to evaluate the technique on seven web applications. In the evaluation we targeted the subject applications with a large number of both legitimate and malicious inputs and measured how many attacks our technique detected and prevented. The results of the study show that our technique was able to stop all of the attempted attacks without generating any false positives.

Safely updating software at remote sites is a cautious balance of enabling new functionality and avoiding adverse effects on existing functionality. A useful first step in this process would be to evaluate the performance of a new version of a component on the current workload before enabling its functionality. This step would let the engineers assess the component's performance over more (and more realistic) data points than by simply performing regression testing in-house.In this paper we propose to evaluate the performance of a new version of a component by (1) deploying it to remote sites, (2) running it in a controlled environment with the actual workloads being generated at that site, and (3) reporting the results back to the development engineers. Running the new version can either be done on-line, alongside the current system, or offline, using capture-replay techniques. By running at the remote site and reporting concise results, issues of data security, protection, and confidentiality are diminished, yet the new version can be evaluated on real workloads.

There is an increasing interest in techniques that support measurement and analysis of fielded software systems. One of the main goals of these techniques is to better understand how software actually behaves in the field. In particular, many of these techniques require a way to distinguish, in the field, failing from passing executions. So far, researchers and practitioners have only partially addressed this problem: they have simply assumed that program failure status is either obvious (i.e., the program crashes) or provided by an external source (e.g., the users). In this paper, we propose a technique for automatically classifying execution data, collected in the field, as coming from either passing or failing program runs. (Failing program runs are executions that terminate with a failure, such as a wrong outcome.) We use statistical learning algorithms to build the classification models. Our approach builds the models by analyzing executions performed in a controlled environment (e.g., test cases run in-house) and then uses the models to predict whether execution data produced by a fielded instance were generated by a passing or failing program execution. We also present results from an initial feasibility study, based on multiple versions of a software subject, in which we investigate several issues vital to the applicability of the technique. Finally, we present some lessons learned regarding the interplay between the reliability of classification models and the amount and type of data collected.

Impact analysis - determining the potential effects of changes on a software system - plays an important role in software engineering tasks such as maintenance, regression testing, and debugging. In previous work, two new dynamic impact analysis techniques, CoverageImpact and PathImpact, were presented. These techniques perform impact analysis based on data gathered about program behavior relative to specific inputs, such as inputs gathered from field data, operational profile data, or test-suite executions. Due to various characteristics of the algorithms they employ, CoverageImpact and PathImpact are expected to differ in terms of cost and precision; however, there have been no studies to date examining the extent to which such differences may emerge in practice. Since cost-precision tradeoffs may play an important role in technique selection and further research, we wished to examine these tradeoffs. We therefore designed and performed an empirical study, comparing the execution and space costs of the techniques, as well as the precisions of the impact analysis results that they report. This paper presents the results of this study.

To investigate the program-execution data efficiently, we must be able to view the data at different levels of detail. In our visualization approach, we represent software systems at three different levels: statement level, file level, and system level. At the statement level, we represent the actual code. The representation at the file level provides a miniaturized view of the source code similar to the one used in the SeeSoft system (Eick et al., 1992). The system level uses treemaps (Shneiderman, 1992 and Bruls et al., 2000) to represent the software and is the most abstracted level in our visualization. At each level, coloring is used to represent one- or two-dimensional information about the code, using the colors' hue and brightness components. The coloring technique that we apply is a generalization of the coloring technique defined for fault-localization by Jones and colleagues (2001). GAMMATELLA is a toolset that implements our visualization approach and provides capabilities for instrumenting the code, collecting program-execution data from the field, and storing and retrieving the data locally. GAMMATELLA is written in Java, supports the monitoring of Java programs, and consists of three main components: an instrumentation, execution, and coverage tool, a data collection daemon, and a program visualizer.

Although object-oriented languages can improve programming practices, their characteristics may introduce new problems for software engineers. One important problem is the presence of implicit control flow caused by exception handling and polymorphism. Implicit control flow causes complex interactions, and can thus complicate software-engineering tasks. To address this problem, we present a systematic and structured approach, for supporting these tasks, based on the static and dynamic analyses of constructs that cause implicit control flow. Our approach provides software engineers with information for supporting and guiding development and maintenance tasks. We also present empirical results to illustrate the potential usefulness of our approach. Our studies show that, for the subjects considered, complex implicit control flow is always present and is generally not adequately exercised.

When software is modified, during development and maintenance, it is regression tested to provide confidence that the changes did not introduce unexpected errors and that new features behave as expected. One important problem in regression testing is how to select a subset of test cases, from the test suite used for the original version of the software, when testing a modified version of the software. Regression-test-selection techniques address this problem. Safe regression-test-selection techniques select every test case in the test suite that may behave differently in the original and modified versions of the software. Among existing safe regression testing techniques, efficient techniques are often too imprecise and achieve little savings in testing effort, whereas precise techniques are too expensive when used on large systems. This paper presents a new regression-test-selection technique for Java programs that is safe, precise, and yet scales to large systems. It also presents a tool that implements the technique and studies performed on a set of subjects ranging from 70 to over 500 KLOC. The studies show that our technique can efficiently reduce the regression testing effort and, thus, achieve considerable savings.

Understanding data dependences in programs is important for many software-engineering activities, such as program understanding, impact analysis, reverse engineering, and debugging. The presence of pointers can cause subtle and complex data dependences that can be difficult to understand. For example, in languages such as C, an assignment made through a pointer dereference can assign a value to one of several variables, none of which may appear syntactically in that statement. In the first part of this article, we describe two techniques for classifying data dependences in the presence of pointer dereferences. The first technique classifies data dependences based on definition type, use type, and path type. The second technique classifies data dependences based on span. We present empirical results to illustrate the distribution of data-dependence types and spans for a set of real C programs. In the second part of the article, we discuss two applications of the classification techniques. First, we investigate different ways in which the classification can be used to facilitate data-flow testing. We outline an approach that uses types and spans of data dependences to determine the appropriate verification technique for different data dependences; we present empirical results to illustrate the approach. Second, we present a new slicing approach that computes slices based on types of data dependences. Based on the new approach, we define an incremental slicing technique that computes a slice in multiple steps. We present empirical results to illustrate the sizes of incremental slices and the potential usefulness of incremental slicing for debugging.

Software products are often released with missing functionality, errors, or incompatibilities that may result in failures, inferior performances, or user dissatisfaction. In previous work, we presented the Gamma approach, which facilitates remote analysis and measurement of deployed software and permits gathering of program-execution data from the field. In this paper, we investigate the use of the Gamma approach to support and improve two fundamental tasks performed by software engineers during maintenance: impact analysis and regression testing. We present a new approach that leverages field data to perform these two tasks. The approach is efficient in that the kind of field data that we consider require limited space and little instrumentation. We also present a set of empirical studies that we performed, on a real subject and on a real user population, to evaluate the approach. The results of the studies show that the use of field data is effective and, for the cases considered, can considerably affect the results of dynamic analyses.

The characteristics of object-oriented software affect type and relevance of faults. In particular the state of the objects may cause faults that cannot be easily revealed with traditional testing techniques. This paper proposes a new technique for interclass testing, that is, the problem of deriving test cases for suitably exercising interactions among clusters of classes. The proposed technique uses data-flow analysis for deriving a suitable set of test case specifications for interclass testing. The paper then shows how to automatically generate feasible test cases that satisfy the derived specifications using symbolic execution and automated deduction. Finally, the paper demonstrates the effectiveness of the proposed technique by deriving test cases for a microscope controller developed for the European Space Laboratory of the Columbus Orbital Facility.

During maintenance, systems are updated to correct faults, improve functionality, and adapt the software to changes in its execution environment. The typical software update process consists of stopping the system to be updated, performing the update of the code, and restarting the system. For systems such as banking and telecommunication software, however the cost of downtime can be prohibitive. The situation is even worse for systems such as air-traffic controllers and life-support software, for which a shut-down is in general not an option. In those cases, the use of some form of on-the-fly program modification is required. In this paper, we present a new technique for dynamic updating of Java software. Our technique is based oil the use of proxy classes and requires no support from the runtime system. The technique allows for updating a running Java program by substituting, adding, and deleting classes. We also present DUSC (dynamic updating through swapping of classes), a tool that we developed and that implements our technique. Finally, we describe an empirical study that we performed to validate the technique of a real Java subject. The results of the study show that our technique can be effectively applied to Java software with only little overhead in both execution time and program size.

In this paper, we present the GAMMA system, which facilitates remote monitoring of deployed software using a new approach that exploits the opportunities presented by a software product being used by many users connected through a network. GAMMA splits monitoring tasks across different instances of the software, so that partial information can be collected from different users by means of light-weight instrumentation, and integrated to gather the overall monitoring information. This system enables software producers (1) to perform continuous, minimally intrusive analyses of their software's behavior, and (2) to use the information thus gathered to improve and evolve their software.

Software products are often released with missing functionality or errors that result in failures in the field. In previous work, we presented the Gamma technology, which facilitates remote monitoring of deployed software and allows for a prompt reaction to failures. In this paper, we investigate one of the principal technologies on which Gamma is based: software tomography. Software tomography splits monitoring tasks across many instances of the software, so that partial information can be (1) collected from users by means of light-weight instrumentation and (2) merged to gather the overall monitoring information. After describing the technology, we illustrate an instance of software tomography for a specific monitoring task. We also present two case studies that we performed to evaluate the presented technique on a real program. The results of the studies show that software tomography can be successfully applied to collect accurate monitoring information using only minimal instrumentation on each deployed program instance.

Component based software technologies are viewed as essential for creating the software systems of the future. However, the use of externally-provided components has serious drawbacks for a wide range of software engineering activities, often because of a lack of information about the components. Previously (A. Orso et al., 2000), we proposed the use of component metacontents: additional data and methods provided with a component, to support software engineering tasks. The authors present two new metacontent based techniques that address the problem of regression test selection for component based applications: a code based approach and a specification based approach. First, we illustrate the two techniques. Then, we present a case study that applies the code based technique to a real component based system. On the system studied, on average, 26% of the overall testing effort was saved over seven releases, with a maximum savings of 99% for one version.

Program slicing is useful for assisting with many software-maintenance tasks. The presence and frequent usage of pointers in languages such as C causes complex data dependences. To function effectively on such programs, slicing techniques must account for pointer-induced data dependences. Existing slicing techniques do not distinguish data dependences based on their types. This paper presents a new slicing technique, in which slices are computed based on types of data dependences. This new slicing technique offers several benefits and can be exploited in different ways, such as identifying subtle data dependences for debugging, computing reduced-size slices quickly for complex programs, and performing incremental slicing. This paper describes an algorithm for incremental slicing that increases the scope of a slice in steps, by incorporating different types of data dependences at each step. The paper also presents empirical results to illustrate the performance of the technique in practice. The results illustrate that incremental slices can be significantly smaller than complete slices. Finally, the paper presents a case study that explores the usefulness of incremental slicing for debugging.

Regression testing is applied to modified software to provide confidence that the changed parts behave as intended and that the unchanged parts have not been adversely affected by the modifications. To reduce the cost of regression testing, test cases are selected from the test suite that was used to test the original version of the software---this process is called regression test selection. A safe regressiontest -selection algorithm selects every test case in the test suite that may reveal a fault in the modified software. Safe regression-test-selection techniques can help to reduce the time required to perform regression testing because they select only a portion of the test suite for use in the testing but guarantee that the faults revealed by this subset will be the same as those revealed by running the entire test suite. This paper presents the first safe regression-test-selection technique that, based on the use of a suitable representation, handles the features of the Java language. Unlike other safe regression test selection techniques, the presented technique also handles incomplete programs. The technique can thus be safely applied in the (very common) case of Java software that uses external libraries or components

Programs developed with object technologies have unique features that often make traditional testing methods inadequate. Consider, for instance, the dependence between the state of an object and the behavior of that object: The outcome of a method executed by an object often depends on the state of the object when the method is invoked. It is therefore crucial that techniques for testing of classes exercise class methods when the method's receiver is in different states. The state of an object at any given time depends on the sequence of messages received by the object up to that time. Thus, methods for testing object-oriented software should identify sequences of method invocations that are likely to uncover potential defects in the code under test. However, testing methods for traditional software do not provide this kind of information.

Formal specification methods are not often applied in industrial projects, despite their advantages and the maturity of theories and tools.The scarce familiarity of practitioners with formal notations and the difficulties of their use are main causes of the limited success of formal specification methods.Approaches based on the use of popular front-end notations formally defined with mappings on formal models can solve practical problems.However the absence of flexibility of the mappings proposed so far limits the applicability of such approaches to the few environments that match exactly these solutions.This paper presents an original solution based on formalisms to define mappings from front-end notations to formal models.The proposed framework works with different front-end notations and formal models and supports mappings of analysis results obtained on the formal model to the front-end notation chosen by the practitioners.The approach described in this paper has been validated in industrial environments using pilot applications.The paper presents some of the industrial results obtained so far and ongoing experimentations.

Rigorous formal methods and intuitive graphical notations can greatly enhance the development of complex computer systems. Formal methods guarantee non-ambiguity and support powerful analysis techniques. Intuitive graphical notations facilitate the communications between engineers preventing errors due to misunderstandings. Unfortunately, tools and techniques based on formal methods do not usually support adequate graphical notations; while tools and methods based on powerful graphical notations often lack formal foundations. This paper proposes a technique that allows kernel formalisms to be accessed through powerful graphical notations. The proposed technique allows graphical notations to be tailored to the needs of the specific application domain. This paper focuses on the tool support.