The WebAssembly standard aims to form a portable compilation target, enabling the cross-platform distribution of programs written in a variety of languages. This paper introduces and evaluates novel slicing approaches for WebAssembly, including dynamic and hybrid approaches. Given a program and a location in that program, a program slice is a reduced program that preserves the behavior at the given location. A static slice does so for all possible inputs, while a dynamic slice does so for a fixed set of inputs. Hybrid slicing is a combination of static and dynamic slicing. We build on Observational-Based Slicing (ORBS), where we explore the design space for instantiating ORBS for WebAssembly. For example, ORBS can be applied to the whole program or to only the function containing the slicing criterion, and it can be applied before compilation to WebAssembly or afterwards. We evaluate the slices produced using various options quantitatively and qualitatively. Our evaluation reveals that dynamic slicing at the level of a function from a WebAssembly binary finds a sweet spot in terms of slice time and slice size, and that a combination of static and dynamic slicers achieves the best trade-off in terms of slicing time and slice size.

Discovering how program components affect one another plays a fundamental role in aiding engineers comprehend and maintain a software system. Despite the fact that the degree to which one program component depends upon another can vary in strength, traditional dependence analysis typically ignores such nuance. To account for this nuance in dependence-based analysis, we propose Causal Program Dependence Analysis (CPDA), a framework based on causal inference that captures the degree (or strength) of the dependence between program elements. For a given program, CPDA intervenes in the program execution to observe changes in value at selected points in the source code. It observes the association between program elements by constructing and executing modified versions of a program (requiring only light-weight parsing rather than sophisticated static analysis). CPDA applies causal inference to the observed changes to identify and estimate the strength of the dependence relations between program elements. We explore the advantages of CPDA's quantified dependence by presenting results for several applications. Our further qualitative evaluation demonstrates 1) that observing different levels of dependence facilitates grouping various functional aspects found in a program and 2) how focusing on the relative strength of the dependences for a particular program element provides a detailed context for that element. Furthermore, a case study that applies CPDA to debugging illustrates how it can improve engineer productivity.

Correcting bugs using modern Automated Program Repair (APR) can be both time-consuming and resource-expensive. We describe a program repair approach that aims to improve the scalability of modern APR tools. The approach leverages program reduction in the form of program slicing to eliminate code irrelevant to fixing the bug, which improves the APR tool's overall performance. We investigate slicing's impact on all three phases of the repair process: fault localization, patch generation, and patch validation. Our empirical exploration finds that the proposed approach on average enhances the repair ability of the TBar APR tool, but we also discovered a few cases where it was less successful. Specifically, on examples from the widely used Defects4J dataset, we obtain a substantial reduction in median repair time, which falls from 80 minutes to just under 18 minutes. We conclude that program reduction can improve the performance of APR without degrading repair quality, but this improvement is not universal.

The recently introduced WebAssembly standard aims to form a portable compilation target, enabling the cross-platform distribution of programs written in a variety of languages. In this paper, we propose and investigate the first dynamic slicing approaches for WebAssembly. Given a program and a location in that program, a program slice is a reduced version of the program that preserves the behavior at the given location. Slicing has numerous applications in software maintenance and evolution, including reverse engineering, code comprehension, and quality assurance.Our dynamic approaches are built on Observational-Based Slicing (ORBS). We explore the design space for instantiating ORBS for WebAssembly: for example, it can be applied to the whole program or to only the function containing the slicing criterion, and it can be applied before compilation to WebAssembly or afterwards. We evaluate the slices produced quantitatively and qualitatively, and compare them to those obtained by a state-of-the-art static slicer for WebAssembly. Our evaluation reveals that dynamic slicing at the level of a function from a WebAssembly binary finds a sweet spot in terms of slice time and slice size.

The recently introduced WebAssembly standard aims to be a portable compilation target, enabling the cross-platform distribution of programs written in a variety of languages. We propose an approach to slice WebAssembly programs in order to enable applications in reverse engineering, code comprehension, and security among others. Given a program and a location in that program, program slicing produces a minimal version of the program that preserves the behavior at the given location. Specifically, our approach is a static, intra-procedural, backward slicing approach that takes into account WebAssembly-specific dependences to identify the instructions of the slice. To do so it must correctly overcome the considerable challenges of performing dependence analysis at the binary level. Furthermore, for the slice to be executable, the approach needs to ensure that the stack behavior of its output complies with WebAssembly's validation requirements. We implemented and evaluated our approach on a suite of 8 386 real-world WebAssembly binaries, finding that the average size of the 495 204 868 slices computed is 53% of the original code, an improvement over the 60% attained by related work slicing ARM binaries. To gain a more qualitative understanding of the slices produced by our approach, we compared them to 1 956 source-level slices of benchmark C programs. This inspection helps to illustrate the slicer's strengths and to uncover potential future improvements.

Program slicing reduces a program to a smaller version that retains a chosen computation, referred to as a slicing criterion. One recent multi-lingual slicing approach, observation-based slicing (ORBS), speculatively deletes parts of the program and then executes the code. If the behavior of the slicing criteria is unchanged, the speculative deletion is made permanent. While this makes ORBS language agnostic, it can lead to the production of some non-intuitive slices. One particular challenge is when the execution environment plays a role. For example, ORBS will delete the line “$\mathrm{a}=0$” if the memory location assigned to a contains zero before executing this statement, because the deletion does not affect the value of a and thus the slicing criterion. Consequently, slices can differ between execution environments due to factors such as initialization and call stack reuse. The technique considered,$\boldsymbol{n}$VORBS, attempts to ameliorate this problem by validating a candidate slice in$\boldsymbol{n}$different execution environments. We conduct an empirical study to collect initial insights into how often the execution environment leads to slice differences. Specifically, we compare and contrast the slices produced by seven different instantiations of$\boldsymbol{n}$VORBS. Looking forward, the technique can be seen as a variation on metamorphic testing, and thus suggests how ideas from metamorphic testing might be used to improve dynamic program analysis.

Predicting vulnerable source code helps to focus the attention of a developer, or a program analysis technique, on those parts of the code that need to be examined with more scrutiny. Recent work proposed the use of function names as semantic cues that can be learned by a deep neural network (DNN) to aid in the hunt for vulnerability of functions. Combining identifier splitting, which we use to split each function name into its constituent words, with a novel frequency-based algorithm, we explore the extent to which the words that make up a function’s name can be used to predict potentially vulnerable functions. In contrast to the lightweight prediction provided by a DNN considering only function names, avoiding the need for a DNN provides featherweight prediction. The underlying idea is that function names that contain certain “dangerous” words are more likely to accompany vulnerable functions. Of course, this assumes that the frequency-based algorithm can be properly tuned to focus on truly dangerous words. Because it is more transparent than a DNN, which behaves as a “black box” and thus provides no insight into the rationalization underlying its decisions, the frequency-based algorithm enables us to investigate the inner workings of the DNN. If successful, this investigation into what the DNN does and does not learn will help us train more effective future models. We empirically evaluate our approach on a heterogeneous dataset containing over 73 000 functions labeled vulnerable, and over 950 000 functions labeled benign. Our analysis shows that words alone account for a significant portion of the DNN’s classification ability. We also find that words are of greatest value in the datasets with a more homogeneous vocabulary. Thus, when working within the scope of a given project, where the vocabulary is unavoidably homogeneous, our approach provides a cheaper, potentially complementary, technique to aid in the hunt for source-code vulnerabilities. Finally, this approach has the advantage that it is viable with orders of magnitude less training data.

Program slicing aims to reduce a program to a minimal form that produces the same output for a given slicing criterion. Program slicing approaches divide into static and dynamic approaches: whereas static approaches generate an over-approximation of the slice that is valid for all possible program inputs, dynamic approaches rely on executing the program and thus generate an under-approximation of the slice that is valid for only a subset of the inputs. An important limitation of static approaches is that they often do not generate an executable program, but rather identify only those program components upon which the slicing criterion depends (referred to as a closure slice). In order to overcome this limitation, we propose a novel approach that combines static and dynamic slicing. We rely on observation-based slicing, a dynamic approach, but protect all statements that have been identified as part of the static slice by the static slicer CodeSurfer. As a result, we obtain slices that cover at least the behavior of the static slice, but that can be compiled and executed. We evaluated this new approach on a set of 57 C programs and report our preliminary findings.

We introduce Web Service Slicing, a technique that captures a functional subset of a large-scale web service using an interface slice captured as a WSDL slice (a subset of a service's WSDL). An interface (WSDL) slice provides access to an interoperable slice, which is a functional subset of the service's code. The technique uses intra-operational and inter-operational analysis to identify web service changes. With the aid of an associative code-test mapping, we leverage the identification of affected operations to reduce the cost of web-service regression testing by extracting a subset of the existing test cases. Used in conjunction with a web service slice, this subset reduces the cost of web-service regression testing by enabling the running of fewer tests. Furthermore, we exploit two approaches: Operationalized Regression Testing of Web Services (ORTWS) and Parameterized Regression Testing of Web Services (PRTWS). ORTWS effectively tests intra-operational changes at the WSDL and WS-code levels, while PRTWS tests inter-operational changes involving inter-operational dependencies due to primary parameters. Finally, we present results obtained using our prototype implementation, AWSCM (Automated Web Service Change Management), in two case-study experiments that serve to illustrate the reduction potential of the technique using eight real-world web services.

The following topics are dealt with: program diagnostics; program verification; Java; software maintenance; program debugging; public domain software; Internet; program testing; learning (artificial intelligence); and object-oriented programming.

As the complexity of a software system grows, it becomes harder for developers to be aware of all the dependencies between its artifacts (e.g., files or methods). Change impact analysis helps to overcome this challenge, by recommending relevant source-code artifacts related to a developer’s current changes. Association rule mining has shown promise in determining change impact by uncovering relevant patterns in the system’s change history. State-of-the-art change impact mining typically uses a change history of tens of thousands of transactions. For efficiency, targeted association rule mining constrains the transactions used to those potentially relevant to answering a particular query. However, it still considers all the relevant transactions in the history. This paper presents Atari, a new adaptive approach that further constrains targeted association rule mining by considering a dynamic selection of the relevant transactions. Our investigation of adaptive change impact mining empirically studies fourteen algorithm variants. We show that adaptive algorithms are viable, can be just as applicable as the start-of-the-art complete-history algorithms, and even outperform them for certain queries. However, more important than this direct comparison, our investigation motivates and lays the groundwork for the future study of adaptive techniques, and their application to challenges such as on-the-fly impact analysis at GitHub-scale.

Naming conventions are generally adopted in an effort to improve program comprehension. Two of the most popular conventions are alternatives for composing multi-word identifiers: the use of underscores and the use of camel casing. While most programmers have a personal opinion as to which style is better, empirical study forms a more appropriate basis for choosing between them. The central hypothesis considered herein is that identifier style affects the speed and accuracy of manipulating programs. An empirical study of 135 programmers and non-programmers was conducted to better understand the impact of identifier style on code readability. The experiment builds on past work of others who study how readers of natural language perform such tasks. Results indicate that camel casing leads to higher accuracy among all subjects regardless of training, and those trained in camel casing are able to recognize identifiers in the camel case style faster than identifiers in the underscore style.

While dependency analysis is foundational to many applications of program analysis, the static nature of many existing techniques presents challenges such as limited scalability and inability to cope with multi-lingual systems. We present a novel dependency analysis technique that aims to approximate program dependency from a relatively small number of perturbed executions. Our technique, called MOAD (Modeling Observation-based Approximate Dependency), reformulates program dependency as the likelihood that one program element is dependent on another, instead of a more classical Boolean relationship. MOAD generates a set of program variants by deleting parts of the source code, and executes them while observing the impacts of the deletions on various program points. From these observations, MOAD infers a model of program dependency that captures the dependency relationship between the modification and observation points. While MOAD is a purely dynamic dependency analysis technique similar to Observation Based Slicing (ORBS), it does not require iterative deletions. Rather, MOAD makes a much smaller number of multiple, independent observations in parallel and infers dependency relationships for multiple program elements simultaneously, significantly reducing the cost of dynamic dependency analysis. We evaluate MOAD by instantiating program slices from the obtained probabilistic dependency model. Compared to ORBS, MOAD's model construction requires only 18.7% of the observations used by ORBS, while its slices are only 16% larger than the corresponding ORBS slice, on average.

Software engineering researchers have been applying tools and techniques from information retrieval (IR) to problems such as bug localization to lower the manual effort required to perform maintenance tasks. The central challenge when using an IR-based tool is the formation of a high-quality query. When performing bug localization, one easily accessible source of query words is the bug report. A recent paper investigated the sufficiency of this source by using a genetic algorithm (GA) to build high quality queries. Unfortunately, the GA in essence "cheats" as it makes use of query performance when evolving a good query. This raises the question, is it feasible to attain similar results without "cheating?" One approach to providing cheat-free queries is to employ automatic summarization. The performance of the resulting summaries calls into question the sufficiency of the bug reports as a source of query words. To better understand the situation, Information Need Analysis (INA) is applied to quantify both how well the GA is performing and, perhaps more importantly, how well a bug report captures the vocabulary needed to perform IR-based bug localization. The results find that summarization shows potential to produce high-quality queries, but it requires more training data. Furthermore, while bug reports provide a useful source of query words, they are rather limited and thus query expansion techniques, perhaps in combination with summarization, will likely produce higher-quality queries.

As the complexity of a software system grows, it becomes increasingly difficult for developers to be aware of all the dependencies that exist between artifacts (e.g., files or methods) of the system. Change impact analysis helps to overcome this problem, as it recommends to a developer relevant source-code artifacts related to her current changes. Association rule mining has shown promise in determining change impact by uncovering relevant patterns in the system's change history. State-of-the-art change impact mining algorithms typically make use of a change history of tens of thousands of transactions. For efficiency, targeted association rule mining focuses on only those transactions potentially relevant to answering a particular query. However, even targeted algorithms must consider the complete set of relevant transactions in the history. This paper presents ATARI, a new adaptive approach to association rule mining that considers a dynamic selection of the relevant transactions. It can be viewed as a further constrained version of targeted association rule mining, in which as few as a single transaction might be considered when determining change impact. Our investigation of adaptive change impact mining empirically studies seven algorithm variants. We show that adaptive algorithms are viable, can be just as applicable as the start-of-the-art complete-history algorithms, and even outperform them for certain queries. However, more important than the direct comparison, our investigation lays necessary groundwork for the future study of adaptive techniques and their application to challenges such as the on-the-fly style of impact analysis that is needed at the GitHub-scale.

As the complexity of software systems grows, it becomes increasingly difficult for developers to be aware of all the dependencies that exist between a system's artifacts (e.g., its files or methods). Change impact analysis has been proposed as a technique to overcome this problem, as it suggests to a developer relevant source-code artifacts related to his/her changes. Association rule mining has shown promise for determining change impact by uncovering relevant patterns in a system's change history.

Software change recommendation seeks to suggest artifacts (e.g., files or methods) that are related to changes made by a developer, and thus identifies possible omissions or next steps. While one obvious challenge for recommender systems is to produce accurate recommendations, a complimentary challenge is to rank recommendations based on their relevance. In this paper, we address this challenge for recommendation systems that are based on evolutionary coupling. Such systems use targeted association-rule mining to identify relevant patterns in a software system's change history. Traditionally, this process involves ranking artifacts using interestingness measures such as confidence and support. However, these measures often fall short when used to assess recommendation relevance. We propose the use of random forest classification models to assess recommendation relevance. This approach improves on past use of various interestingness measures by learning from previous change recommendations. We empirically evaluate our approach on fourteen open source systems and two systems from our industry partners. Furthermore, we consider complimenting two mining algorithms: Co-Change and Tarmaq. The results find that random forest classification significantly outperforms previous approaches, receives lower Brier scores, and has superior trade-off between precision and recall. The results are consistent across software system and mining algorithm.

Observation-based slicing is a recently-introduced, language-independent slicing technique based on the dependencies observable from program behavior.The original algorithm processed traditional source code at the line-of-text level.A recent variation was developed to slice the tree-based XML representation of executable models.We ported the model slicer to source code using srcML to construct a tree-based representation of traditional source code.We present the results of a comparison of the two slicers using four experiments involving seventeen different programs, including classic benchmarks and larger production systems.The resulting slices had essentially the same size and quite often the same content.Where they differ, the use of tree structure traded an ability to remove unnecessary parts of a statement for the requirement of maintaining aspect of the code structure.Comparing the slicers finds that each has its advantages.For example, when the tree representation facilitates the deletion of large chunks of code, the tree slicer was over eight times faster.In contrast, when slicing C++ code it was over nine times slower because of the multitude of small trees created to support C++ syntax.Given the pros and cons of the two, the results suggest the value of their hybrid combination.

Model-driven software engineering raises the abstraction level making complex systems easier to understand than if written in textual code. Nevertheless, large complicated software systems can have large models, motivating the need for slicing techniques that reduce the size of a model. We present a generalization of observation-based slicing that allows the criterion to be defined using a variety of kinds of observable behavior and does not require any complex dependence analysis. We apply our implementation of generalized observational slicing for tree-structured representations to Simulink models. The resulting slice might be the subset of the original model responsible for an observed failure or simply the sub-model semantically related to a classic slicing criterion. Unlike its predecessors, the algorithm is also capable of slicing embedded Stateflow state machines. A study of nine real-world models drawn from four different application domains demonstrates the effectiveness of our approach at dramatically reducing Simulink model sizes for realistic observation scenarios: for 9 out of 20 cases, the resulting model has fewer than 25% of the original model's elements.

This paper presents PORBS, a parallelised observation-based slicing tool. The tool itself is written in Java making it platform independent and leverages the build chain of the system being sliced to avoid the need to replicate complex compiler analysis. The target audience of PORBS is software engineers and researchers working with and on tools and techniques for software comprehension, debugging, re-engineering, and maintenance.

Association rule mining is an unsupervised learning technique that infers relationships among items in a data set. This technique has been successfully used to analyze a system's change history and uncover evolutionary coupling between system artifacts. Evolutionary coupling can, in turn, be used to recommend artifacts that are potentially affected by a given set of changes to the system. In general, the quality of such recommendations is affected by (1) the values selected for various parameters of the mining algorithm, (2) characteristics of the set of changes used to derive a recommendation, and (3) characteristics of the system's change history for which recommendations are generated.

A dependence cluster is a set of mutually inter-dependent program elements. Prior studies have found that large dependence clusters are prevalent in software systems. It has been suggested that dependence clusters have potentially harmful effects on software quality. However, little empirical evidence has been provided to support this claim. The study presented in this paper investigates the relationship between dependence clusters and software quality at the function-level with a focus on effort-aware fault-proneness prediction. The investigation first analyzes whether or not larger dependence clusters tend to be more fault-prone. Second, it investigates whether the proportion of faulty functions inside dependence clusters is significantly different from the proportion of faulty functions outside dependence clusters. Third, it examines whether or not functions inside dependence clusters playing a more important role than others are more fault-prone. Finally, based on two groups of functions (i.e., functions inside and outside dependence clusters), the investigation considers a segmented fault-proneness prediction model. Our experimental results, based on five well-known open-source systems, show that (1) larger dependence clusters tend to be more fault-prone; (2) the proportion of faulty functions inside dependence clusters is significantly larger than the proportion of faulty functions outside dependence clusters; (3) functions inside dependence clusters that play more important roles are more fault-prone; (4) our segmented prediction model can significantly improve the effectiveness of effort-aware fault-proneness prediction in both ranking and classification scenarios. These findings help us better understand how dependence clusters influence software quality.

Past research has proposed association rule mining as a means to uncover the evolutionary coupling from a system's change history. These couplings have various applications, such as improving system decomposition and recommending related changes during development. The strength of the coupling can be characterized using a variety of interestingness measures. Existing recommendation engines typically use only the rule with the highest interestingness value in situations where more than one rule applies. In contrast, we argue that multiple applicable rules indicate increased evidence, and hypothesize that the aggregation of such rules can be exploited to provide more accurate recommendations.

For over two decades, software engineering (SE) researchers have been importing tools and techniques from information retrieval (IR). Initial results have been quite positive. For example, when applied to problems such as feature location or re-establishing traceability links, IR techniques work well on their own, and often even better in combination with more traditional source code analysis techniques such as static and dynamic analysis. However, recently there has been growing awareness among SE researchers that IR tools and techniques are designed to work under a different set of assumptions than those that hold for a software system. Thus it may be beneficial to consider IR inspired tools and techniques that are specifically designed to work with software. One aim of this work is to provide quantitative empirical evidence in support of this observation. To do so a new technique is introduced that captures the level of difficulty found in an information need, the true, often latent, information that a searcher desires to know. The new technique is used to compare two test collections: the natural language TREC 8 collection and the software engineering JabRef collection. Analysis of the data leads to three significant findings. First, the variation in difficulty of the SE information needs is much larger than that of the natural language information needs, second, the most challenging of the SE information needs is far easier than the least challenging of the natural language information needs, and finally, variations of the queries used to uncover a latent information need have far less impact in the natural language collection than in the software engineering collection.

The goal of Software Change Impact Analysis is to identify artifacts (typically source-code files) potentially affected by a change. Recently, there is an increased interest in mining software change impact based on evolutionary coupling. A particularly promising approach uses association rule mining to uncover potentially affected artifacts from patterns in the system's change history. Two main considerations when using this approach are the history length, the number of transactions from the change history used to identify the impact of a change, and history age, the number of transactions that have occurred since patterns were last mined from the history. Although history length and age can significantly affect the quality of mining results, few guidelines exist on how to best select appropriate values for these two parameters. In this paper, we empirically investigate the effects of history length and age on the quality of change impact analysis using mined evolutionary couplings. Specifically, we report on a series of systematic experiments involving the change histories of two large industrial systems and 17 large open source systems. In these experiments, we vary the length and age of the history used to mine software change impact, and assess how this affects precision and applicability. Results from the study are used to derive practical guidelines for choosing history length and age when applying association rule mining to conduct software change impact analysis.

Software change impact analysis aims to find artifacts potentially affected by a change. Typical approaches apply language-specific static or dynamic dependence analysis, and are thus restricted to homogeneous systems. This restriction is a major drawback given today's increasingly heterogeneous software. Evolutionary coupling has been proposed as a language-agnostic alternative that mines relations between source-code entities from the system's change history. Unfortunately, existing evolutionary coupling based techniques fall short. For example, using Singular Value Decomposition (SVD) quickly becomes computationally expensive. An efficient alternative applies targeted association rule mining, but the most widely known approach (ROSE) has restricted applicability: experiments on two large industrial systems, and four large open source systems, show that ROSE can only identify dependencies about 25% of the time. To overcome this limitation, we introduce TARMAQ, a new algorithm for mining evolutionary coupling. Empirically evaluated on the same six systems, TARMAQ performs consistently better than ROSE and SVD, is applicable 100% of the time, and runs orders of magnitude faster than SVD. We conclude that the proposed algorithm is a significant step forward towards achieving robust change impact analysis for heterogeneous systems.

Abstract Latent Dirichlet allocation (LDA) has seen increasing use in the understanding of source code and its related artifacts in part because of its impressive modeling power. However, this expressive power comes at a cost: The technique includes several tuning parameters whose impact on the resulting LDA model must be carefully considered. The aim of this work is to provide insights into the tuning parameters' impact. Doing so improves the comprehension of both researchers who look to exploit the power of LDA in their research and those who interpret the output of LDA‐using tools. It is important to recognize that the goal of this work isnotto establish values for the tuning parameters because there is no universalbest setting. Rather, appropriate settings depend on the problem being solved, the input corpus (in this case, typically words from the source code and its supporting artifacts), and the needs of the engineer performing the analysis. This work's primary goal is to aid software engineers in their understanding of the LDA tuning parameters by demonstrating numerically and graphically the relationship between the tuning parameters and the LDA output. A secondary goal is to enable more informed setting of the parameters. Copyright © 2016 John Wiley & Sons, Ltd.

Dependence clusters are (maximal) collections of mutually dependent source code entities according to some dependence relation. Their presence in software complicates many maintenance activities including testing, refactoring, and feature extraction. Despite several studies finding them common in production code, their formation, identification, and overall structure are not well understood, partly because of challenges in approximating true dependences between program entities. Previous research has considered two approximate dependence relations: a fine-grained statement-level relation using control and data dependences from a program's System Dependence Graph and a coarser relation based on function-level control-flow reachability. In principal, the first is more expensive and more precise than the second. Using a collection of twenty programs, we present an empirical investigation of the clusters identified by these two approaches. In support of the analysis, we consider a hybrid cluster type that works at the coarser function-level but is based on the higher-precision statement-level dependences. The three types of clusters are compared based on their slice sets using two clustering metrics. We also perform extensive analysis of the programs to identify linchpin functions - functions primarily responsible for holding a cluster together. Results include evidence that the less expensive, coarser approaches can often be used as effective proxies for the more expensive, finer-grained approaches. Finally, the linchpin analysis shows that linchpin functions can be effectively and automatically identified.

Observation-based slicing is a recently-introduced, language-independent slicing technique based on the dependencies observable from program behaviour. Due to the well-known limits of dynamic analysis, we may only compute an under-approximation of the true observation-based slice. However, because the observation-based slice captures all possible dependence that can be observed, even such approximations can yield insight into the limitations of static slicing. For example, a static slice, S, that is strictly smaller than the corresponding observation based slice is potentially unsafe. We present the results of three sets of experiments on 12 different programs, including benchmarks and larger programs, which investigate the relationship between static and observation-based slicing. We show that, in extreme cases, observation-based slices can find the true minimal static slice, where static techniques cannot. For more typical cases, our results illustrate the potential for observation-based slicing to highlight limitations in static slicers. Finally, we report on the sensitivity of observation-based slicing to test quality.

The hierarchical method of organizing information has proven beneficial in learning in part because it maps well onto the human brain's memory. Exploiting this organizational strategy may help engineers cope with large software systems. In fact such an strategy is already present in source code and is manifested in the class hierarchies of objected-oriented programs. However, an engineer faced with fixing a bug or any similar need to locate the implementation of a particular feature in the code is less interested in the syntactic organization of the code and more interested in its conceptual organization. Therefore, a conceptual hierarchy would bring clear benefit. Fortunately, such a view can be extracted automatically the source code. The hierarchy generating tool HierIT performs this task using an information-theoretic approach to identify “content-bearing” words and associate them hierarchically. The resulting hierarchy enables an engineer to better understand the concepts contained in a software system. To study their value, an experiment was conducted to quantitatively and qualitatively investigate the value that hierarchies bring. The quantitative evaluation first considers the Expected Mutual Information Measure (EMIM) between the set of topic words and natural language extracted from the source code. It then considers the Best Case Tree Walk (BCTW), which captures how “expensive” it is to find interesting documents. Finally, the hierarchies are considered qualitatively by investigating their perceived usefulness in a case study involving three engineers.

Abstract Software development, evolution, and maintenance depend on ever increasing tool support. Recent tools have incorporated increasing analysis of the natural language found in source code, predominately in the identifiers and comments. However, when coders combine abbreviations and acronyms to form multi‐word identifiers, they, in essence, invent new vocabulary making the source code's vocabulary differ from that of other software artifacts. This vocabulary mismatch is a potential problem for many techniques imported from information retrieval and natural language processing, which implicitly assume the use of a single common vocabulary. Vocabulary normalization aims to bring the vocabulary of the source in line with that of other artifacts. A prior small‐scale experiment demonstrated the value of vocabulary normalization for C code. A more comprehensive experiment using Java code is presented where normalization fails to bring benefit. To investigate the potential underlying causes, over 20,000 non‐dictionary words extracted from the program JabRef were normalized by hand (often requiring significant external information). The experiment, repeated using the hand‐normalized identifiers, again found that normalization brought no improvement. In response to this unexpected result, the vocabulary differences between Java and C codes are considered and used to help frame directions for future work. Copyright © 2015 John Wiley & Sons, Ltd.

Learning to Rank (LtR) encompasses a class of machine learning techniques developed to automatically learn how to better rank the documents returned for an information retrieval (IR) search. Such techniques offer great promise to software engineers because they better adapt to the wider range of differences in the documents and queries seen in software corpora. To encourage the greater use of LtR in software maintenance and evolution research, this paper explores the value that LtR brings to two common maintenance problems: feature location and traceability. When compared to the worst, median, and best models identified from among hundreds of alternative models for performing feature location, LtR ubiquitously provides a statistically significant improvement in MAP, MRR, and MnDCG scores. Looking forward a further motivation for the use of LtR is its ability to enable the development of software specific retrieval models.

Latent Dirichlet Allocation (LDA) has seen increasing use in the understanding of source code and its related artifacts in part because of its impressive modeling power. However, this expressive power comes at a cost: the technique includes several tuning parameters whose impact on the resulting LDA model must be carefully considered. An obvious example is the burn-in period; too short a burn-in period leaves excessive echoes of the initial uniform distribution. The aim of this work is to provide insights into the tuning parameter's impact. Doing so improves the comprehension of both, 1) researchers who look to exploit the power of LDA in their research and 2) those who interpret the output of LDA-using tools. It is important to recognize that the goal of this work is not to establish values for the tuning parameters because there is no universal best setting. Rather, appropriate settings depend on the problem being solved, the input corpus (in this case, typically words from the source code and its supporting artifacts), and the needs of the engineer performing the analysis. This work's primary goal is to aid software engineers in their understanding of the LDA tuning parameters by demonstrating numerically and graphically the relationship between the tuning parameters and the LDA output. A secondary goal is to enable more informed setting of the parameters. Results obtained using both production source code and a synthetic corpus underscore the need for a solid understanding of how to configure LDA's tuning parameters.

Program slicing has seen a plethora of applications and variations since its introduction over thirty years ago. The dominant method for computing slices involves significant complex source-code analysis to model the dependences in the code. A recently introduced alternative, Observation-Based Slicing (ORBS), sidesteps this complexity by observing the behavior of candidate slices. ORBS has several other strengths, including the ability to slice multi-language systems. However, ORBS remains rooted in tradition as it captures semantics by comparing sequences of values. This raises the question of whether it is possible to extend slicing beyond its traditional semantic roots. A few existing projects have attempted this, but the extension requires considerable effort. If it is possible to build on the ORBS platform to more easily generalize slicing to languages with non-traditional semantics, then there is the potential to vastly increase the range of programming languages to which slicing can be applied. ORBS supports this by reducing the problem to that of generalizing how semantics are captured. Taking Picture Description Languages as a case study, the challenges and effectiveness of such a generalization are considered. The results show that not only is it possible to generalize the ORBS algorithm, but the resulting slicer is quite effective removing from 27% to 98% of the original source code with an average of 85%. Finally a qualitative look at the slices finds the technique very effective, at times producing minimal slices.

Current slicing techniques cannot handle systems written in multiple programming languages. Observation-Based Slicing (ORBS) is a language-independent slicing technique capable of slicing multi-language systems, including systems which contain (third party) binary components. A potential slice obtained through repeated statement deletion is validated by observing the behaviour of the program: if the slice and original program behave the same under the slicing criterion, the deletion is accepted. The resulting slice is similar to a dynamic slice. We evaluate five variants of ORBS on ten programs of different sizes and languages showing that it is less expensive than similar existing techniques. We also evaluate it on bash and four other systems to demonstrate feasible large-scale operation in which a parallelised ORBS needs up to 82% less time when using four threads. The results show that an ORBS slicer is simple to construct, effective at slicing, and able to handle systems written in multiple languages without specialist analysis tools.

This paper presents the results of a large scale empirical study of coherent dependence clusters. All statements in a coherent dependence cluster depend upon the same set of statements and affect the same set of statements; a coherent cluster's statements have ‘coherent’ shared backward and forward dependence. We introduce an approximation to efficiently locate coherent clusters and show that it has a minimum precision of 97.76%. Our empirical study also finds that, despite their tight coherence constraints, coherent dependence clusters are in abundance: 23 of the 30 programs studied have coherent clusters that contain at least 10% of the whole program. Studying patterns of clustering in these programs reveals that most programs contain multiple substantial coherent clusters. A series of subsequent case studies uncover that all clusters of significant size map to a logical functionality and correspond to a program structure. For example, we show that for the program acct, the top five coherent clusters all map to specific, yet otherwise non-obvious, functionality. Cluster visualization also brings out subtle deficiencies in program structure and identifies potential refactoring candidates. A study of inter-cluster dependence is used to highlight how coherent clusters are connected to each other, revealing higher-level structures, which can be used in reverse engineering. Finally, studies are presented to illustrate how clusters are not correlated with program faults as they remain stable during most system evolution.

Software engineers produce code that has formal syntax and semantics, which establishes its formal meaning. However, the code also includes significant natural language found primarily in identifier names and comments. Furthermore, the code is surrounded by non-source artifacts, predominantly written in natural language. The NaturaLiSE workshop focuses on natural language analysis of software. The workshop brings together researchers and practitioners interested in exploiting natural language information to create improved software engineering tools. Participants will explore natural language analysis applied to software artifacts, combining natural language and traditional program analysis, integration of natural language analyses into client tools, mining natural language data, and empirical studies focused on evaluating the usefulness of natural language analysis.

There is a growing interest in software summarization and tools for automatically producing summaries. Discussions of relevant papers at recent conferences led to the observation that software summarization needs to consider migrating away from ``is this a good summary?" and towards ``is this a useful summary?" As a result, it has been suggested that to judge usefulness, one needs to view the summary through the lens of a particular task. A preliminary investigation of this suggestion was undertaken at the 2013 ICSE workshop NaturaLiSE. Initial results and lessons learned from this investigation support the notion that task plays a significant role and thus should be considered by researchers building and accessing automatic software summarization tools.

Feature location is a fundamental step in software evolution tasks such as debugging, understanding, and reuse. Numerous automated and semi-automated feature location techniques (FLTs) have been proposed, but the question remains: How do we objectively determine which FLT is most effective? Existing evaluations frequently use bug fix data, which includes the location of the fix, but not what other code needs to be understood to make the fix. Existing evaluation measures such as precision, recall, effectiveness, mean average precision (MAP), and mean reciprocal rank (MRR) will not differentiate between a FLT that ranks higher these related elements over completely irrelevant ones. We propose an alternative measure of relevance based on the likelihood of a developer finding the bug fix locations from a ranked list of results. Our initial evaluation shows that by modeling user behavior, our proposed evaluation methodology can compare and evaluate FLTs fairly.

Software engineering and evolution techniques have recently started to exploit the natural language information in source code. A key step in doing so is splitting identifiers into their constituent words. While simple in concept, identifier splitting raises several challenging issues, leading to a range of splitting techniques. Consequently, the research community would benefit from a dataset (i.e., a gold set) that facilitates comparative studies of identifier splitting techniques. A gold set of 2,663 split identifiers was constructed from 8,522 individual human splitting judgements and can be obtained from www.cs.loyola.edu/~binkley/ludiso. This set's construction and observations aimed at its effective use are described.

SUMMARY Recently, different methods and tools have been proposed to automate or semi‐automate test‐to‐code traceability recovery. Among these, Slicing and Coupling based Test to Code trace Hunter (SCOTCH) exploits slicing and conceptual coupling to identify the classes tested by a JUnit test. However, until now the evaluation of test‐to‐code traceability recovery methods has been limited to experiments assessing their tracing accuracy rather than the actual support these methods provide to a software engineer during traceability recovery tasks. Indeed, a research method or tool has a better chance of being transferred to practitioners if it is supported by empirical evidence. In this paper, we present the results of two controlled experiments carried out to evaluate the support given by SCOTCH during traceability recovery, when compared with other traceability recovery methods. The results show that SCOTCH is able to suggest a higher number of correct links with higher accuracy, thus sensibly improving the performances of software engineers during test‐to‐code traceability recovery tasks. Copyright © 2012 John Wiley & Sons, Ltd.

Several authors have found evidence of large dependence clusters in the source code of a diverse range of systems, domains, and programming languages. This raises the question of how we might efficiently locate the fragments of code that give rise to large dependence clusters. We introduce an algorithm for the identification of linchpin vertices, which hold together large dependence clusters, and prove correctness properties for the algorithm’s primary innovations. We also report the results of an empirical study concerning the reduction in analysis time that our algorithm yields over its predecessor using a collection of 38 programs containing almost half a million lines of code. Our empirical findings indicate improvements of almost two orders of magnitude, making it possible to process larger programs for which it would have previously been impractical.

Unit testing represents a key activity in software development and maintenance. Test suites with high internal quality facilitate maintenance activities, such as code comprehension and regression testing. Several guidelines have been proposed to help developers write good test suites. Unfortunately, such rules are not always followed resulting in the presence of bad test code smells (or simply test smells). Test smells have been defined as poorly designed tests and their presence may negatively affect the maintainability of test suites and production code. Despite the many studies that address code smells in general, until now there has been no empirical evidence regarding test smells (i) distribution in software systems nor (ii) their impact on the maintainability of software systems. This paper fills this gap by presenting two empirical studies. The first study is an exploratory analysis of 18 software systems (two industrial and 16 open source) aimed at analyzing the distribution of test smells in source code. The second study, a controlled experiment involving twenty master students, is aimed at analyzing whether the presence of test smells affects the comprehension of source code during software maintenance. The results show that (i) test smells are widely spread throughout the software systems studied and (ii) most of the test smells have a strong negative impact on the comprehensibility of test suites and production code.

Tool support is crucial to modern software development, evolution, and maintenance. Early tools reused the static analysis performed by the compiler. These were followed by dynamic analysis tools and more recently tools that exploit natural language. This later class has the advantage that it can incorporate not only the code, but artifacts from all phases of software construction and its subsequent evolution. Unfortunately, the natural language found in source code often uses a vocabulary different from that used in other software artifacts and thus increases the vocabulary mismatch problem. This problem exists because many natural-language tools imported from Information Retrieval (IR) and Natural Language Processing (NLP) implicitly assume the use of a single natural language vocabulary. Vocabulary normalization, which goes well beyond simple identifier splitting, brings the vocabulary of the source into line with other artifacts. Consequently, it is expected to improve the performance of existing and future IR and NLP based tools. As a case study, an experiment with an LSI-based feature locator is replicated. Normalization universally improves performance. For the tersest queries, this improvement is over 180% (p <; 0.0001).

This paper introduces Model Projection. Finite state models such as Extended Finite State Machines are being used in an ever increasing number of software engineering activities. Model projection facilitates model development by specializing models for a specific operating environment. A projection is useful in many design-level applications including specification reuse and property verification.

Maintaining modern software requires significant tool support. Effective tools exploit a variety of information and techniques to aid a software maintainer. One area of recent interest in tool development exploits the natural language information found in source code. Such Information Retrieval (IR) based tools compliment traditional static analysis tools and have tackled problems, such as feature location, that otherwise require considerable human effort. To reap the full benefit of IR-based techniques, the language used across all software artifacts (e.g., requirements, design, change requests, tests, and source code) must be consistent. Unfortunately, there is a significant proportion of invented vocabulary in source code. Vocabulary normalization aligns the vocabulary found in the source code with that found in other software artifacts. Most existing work related to normalization has focused on splitting an identifier into its constituent parts. The next step is to expand each part into a (dictionary) word that matches the vocabulary used in other software artifacts. Building on a successful approach to splitting identifiers, an implementation of an expansion algorithm is presented. Experiments on two systems find that up to 66% of identifiers are correctly expanded, which is within about 20% of the current system's best-case performance. Not only is this performance comparable to previous techniques, but the result is achieved in the absence of special purpose rules and not limited to restricted syntactic contexts. Results from these experiments also show the impact that varying levels of documentation (including both internal documentation such as the requirements and design, and external, or user-level, documentation) have on the algorithm's performance.

Maintaining traceability links between unit tests and tested classes is an important factor for effectively managing the development and evolution of software systems. Exploiting traceability links helps in program comprehension and maintenance by ensuring consistency between unit tests and tested classes during maintenance activities. Unfortunately, it is often the case that such links are not explicitly maintained and thus they have to be recovered manually during software evolution. A novel automated solution to this problem, based on dynamic slicing and conceptual coupling, is presented. The resulting tool, SCOTCH (Slicing and Coupling based Test to Code trace Hunter), is empirically evaluated on three systems: an open source system and two industrial systems. The results indicate that SCOTCH identifies traceability links between unit test classes and tested classes with a high accuracy and greater stability than existing techniques, highlighting its potential usefulness as a feature within a software development environment.

Recent software development tools have exploited the mining of natural language information found within software and its supporting documentation. To make the most of this information, researchers have drawn upon the work of the natural language processing community for tools and techniques. One such tool provides part-of-speech information, which finds application in improving the searching of software repositories and extracting domain information found in identifiers.

Search-Based Testing is a widely studied technique for automatically generating test inputs, with the aim of reducing the cost of software engineering activities that rely upon testing. However, search-based approaches degenerate to random testing in the presence of flag variables, because flags create spikes and plateaux in the fitness landscape. Both these features are known to denote hard optimization problems for all search-based optimization techniques. Several authors have studied flag removal transformations and fitness function refinements to address the issue of flags, but the problem of loop-assigned flags remains unsolved. This article introduces a testability transformation along with a tool that transforms programs with loop-assigned flags into flag-free equivalents, so that existing search-based test data generation approaches can successfully be applied. The article presents the results of an empirical study that demonstrates the effectiveness and efficiency of the testability transformation on programs including those made up of open source and industrial production code, as well as test data generation problems specifically created to denote hard optimization problems.

This paper presents an approach to automatically distinguish the copied clone from the original in a pair of clones. It matches the line-by-line version information of a clone to the pair's other clone. A case study on the GNOME Desktop Suite revealed a complex flow of reused code between the different subprojects. In particular, it showed that the majority of larger clones (with a minimal size of 28 lines or higher) exist between the subprojects and more than 60% of the clone pairs can be automatically separated into original and copy.

Large clusters of mutual dependence can cause problems for comprehension, testing and maintenance. This paper introduces the concept of coherent dependence clusters, techniques for their efficient identification, visualizations to better understand them, empirical results concerning their practical significance. As the paper will show, coherent dependence clusters facilitate a fine grained analysis of the subtle relationships between clusters of dependence.

During execution, an objected-oriented program typically creates a large number of objects. This research considers the distribution of those objects that share a common superclass. If this distribution is uniform then all subclasses are equally likely to be instantiated. However, if not, then the lack of uniformity can be exploited by giving preferential treatment to the dominant class (or classes). For example, a tester might spend greater testing resources on the dominant class while an engineer refactoring the code might begin with a more dominant class. An experiment designed to investigate the distribution of subclass instantiations was performed using eight Java programs containing almost half a million lines of code and just over three thousand classes. The results show that outside a few infrequent instances, most distributions are heavily skewed.

Naming conventions are generally adopted in an effort to improve program comprehension. Two of the most popular conventions are alternatives for composing multi-word identifiers: the use of underscores and the use of camel casing. While most programmers have a personal opinion as to which style is better, empirical study forms a more appropriate basis for choosing between them. The central hypothesis considered herein is that identifier style affects the speed and accuracy of manipulating programs. An empirical study of 135 programmers and non-programmers was conducted to better understand the impact of identifier style on code readability. The experiment builds on past work of others who study how readers of natural language perform such tasks. Results indicate that camel casing leads to higher accuracy among all subjects regardless of training, and those trained in camel casing are able to recognize identifiers in the camel case style faster than identifiers in the underscore style.

A dependence cluster is a maximal set of program components that all depend upon one another. Previous work has highlighted the prevalence of large dependence clusters in source code, presenting potential problems for comprehension, testing, and maintenance. This paper is concerned with source code analysis techniques for identifying the causes of large dependence clusters. The paper presents results of a study of low-level causes of dependence clusters, which reveals that a large cluster can be caused by the smallest atomic unit source code: a single vertex or edge of the program's dependence graph. These are termed the linchpin vertices and edges in this paper.

This paper describes the implementation and evaluation of a program that uses active recruiting and peer-led team learning to try to increase the participation and success of women and minority students in undergraduate computer science. These strategies were applied at eight universities starting in the fall of 2004. There have been some impressive results: We succeeded in attracting under-represented students who would not otherwise have taken a CS course.Evaluation shows that participation in our program significantly improves retention rates and grades, especially for women.Students in the program, as well as the students who served as peer leaders, are uniformly enthusiastic about their experience.

A dependence cluster is a set of program statements, all of which are mutually inter-dependent. This article reports a large scale empirical study of dependence clusters in C program source code. The study reveals that large dependence clusters are surprisingly commonplace. Most of the 45 programs studied have clusters of dependence that consume more than 10% of the whole program. Some even have clusters consuming 80% or more. The widespread existence of clusters has implications for source code analyses such as program comprehension, software maintenance, software testing, reverse engineering, reuse, and parallelization.

Evolutionary testing is an approach to automating test data generation that uses an evolutionary algorithm to search a test object's input domain for test data. Nested predicates can cause problems for evolutionary testing, because information needed for guiding the search only becomes available as each nested conditional is satisfied. This means that the search process can overfit to early information, making it harder, and sometimes near impossible, to satisfy constraints that only become apparent later in the search. The article presents a testability transformation that allows the evaluation of all nested conditionals at once. Two empirical studies are presented. The first study shows that the form of nesting handled is prevalent in practice. The second study shows how the approach improves evolutionary test data generation.

Since early variable mnemonics were limited to as few as six to eight characters, many early programmers abbreviated concepts in their variable names. The past thirty years has seen a steady increase in permitted name length and, slowly, an increase in the actual length of identifiers. However, in theory names can be too long. Most obviously, in object-oriented programs, names often involve chaining of method calls and field selectors (e.g., class.firstAssignment().name.trim()). While longer names bring the potential for easier comprehension through more embedded sub-words, there are practical limits to length given limited human memory resources. The central hypothesis studied herein is that names used in modern programs have reached this limit. Statistical models derived from an experiment involving 158 programmers of varying degrees of experience show that longer names extracted from production code take more time to process and reduce correctness in a simple recall activity. This has clear negative implications for any attempt to read, and hence comprehend or manipulate, the source code of modern software. The experiment also evaluates the advantage of identifiers having ties to a programmer's persistent memory. Combined these results reinforce past proposals advocating the use of limited, consistent, and regular vocabulary in identifier names. In particular, good naming limits length and reduces the need for specialized vocabulary.

Key Statement Analysis extracts from a program, statements that form the core of the program’s computation. A good set of key statements is small but has a large impact. Key statements form a useful starting point for understanding and manipulating a program. An empirical investigation of three kinds of key statements is presented. The three are based on Bieman and Ott’s principal variables. To be effective, the key statements must have high impact and form a small, highly cohesive unit. Using a minor improvement of metrics for measuring impact and cohesion, key statements are shown to capture about 75% of the semantic effect of the function from which they are drawn. At the same time, they have cohesion about 20 percentage points higher than the corresponding function. A statistical analysis of the differences shows that key statements have higher average impact and higher average cohesion (p≪0.001).

Abstract Readers of programs have two main sources of domain information: identifier names and comments. In order to efficiently maintain source code, it is important that the identifier names (as well as comments) communicate clearly the concepts they represent. Deißenböck and Pizka recently introduced two rules for creating well‐formed identifiers: one considers the consistency of identifiers and the other their conciseness. These rules require a mapping from identifiers to the concepts they represent, which may be costly to develop after the initial release of a system. An approach for verifying whether identifiers are well formed without any additional information (e.g., a concept mapping) is developed. Using a pool of 48 million lines of code, experiments with the resulting syntactic rules for well‐formed identifiers illustrate that violations of the syntactic pattern exist. Two case studies show that three‐quarters of these violations are ‘real’. That is, they could be identified using a concept mapping. Three related studies show that programmers tend to use a rather limited vocabulary, that, contrary to many other aspects of system evolution, maintenance does not introduce additional rule violations, and that open and proprietary sources differ in their percentage of violations. Copyright © 2007 John Wiley & Sons, Ltd.

This article presents results from a study of techniques that improve the performance of graph-based interprocedural slicing of the System Dependence Graph (SDG). This is useful in “massive slicing” where slices are required for many or all of the possible set of slicing criteria. Several different techniques are considered, including forming strongly connected components, topological sorting, and removing transitive edges. Data collected from a test bed of just over 1,000,000 lines of code are presented. This data illustrates the impact on computation time of the techniques. Together, the best combination produces a 71% reduction in run-time (and a 64% reduction in memory usage). The complete set of techniques also illustrates the point at which faster computation is not viable due to prohibitive preprocessing costs.

This article presents results from a study of all slices from 43 programs, ranging up to 136,000 lines of code in size. The study investigates the effect of five aspects that affect slice size. Three slicing algorithms are used to study two algorithmic aspects: calling-context treatment and slice granularity. The remaining three aspects affect the upstream dependencies considered by the slicer. These include collapsing structure fields, removal of dead code, and the influence of points-to analysis. The results show that for the most precise slicer, the average slice contains just under one-third of the program. Furthermore, ignoring calling context causes a 50% increase in slice size, and while (coarse-grained) function-level slices are 33% larger than corresponding statement-level slices, they may be useful predictors of the (finer-grained) statement-level slice size. Finally, upstream analyses have an order of magnitude less influence on slice size.

Software reengineering is a costly endeavor, due in part to the ambiguity of where to focus reengineering effort. Coupling and Cohesion metrics, particularly quantitative cohesion metrics, have the potential to aid in this identification and to measure progress. The most extensive work on such metrics is with slice-based cohesion metrics. While their use of semantic dependence information should make them an excellent choice for cohesion measurement, their wide spread use has been impeded in part by a lack of empirical study. Recent advances in software tools make, for the first time, a large-scale empirical study of slice-based cohesion and coupling metrics possible. Four results from such a study are presented. First, “head-to-head” qualitative and quantitative comparisons of the metrics identify which metrics provide similar views of a program and which provide unique views of a program. This study includes statistical analysis showing that slice-based metrics are not proxies for simple size-based metrics such as lines of code. Second, two longitudinal studies show that slice-based metrics quantify the deterioration of a program as it ages. This serves to validate the metrics: the metrics quantify the degradation that exists during development; turning this around, the metrics can be used to measure the progress of a reengineering effort. Third, baseline values for slice-based metrics are provided. These values act as targets for reengineering efforts with modules having values outside the expected range being the most in need of attention. Finally, slice-based coupling is correlated and compared with slice-based cohesion.

SOFTWARE maintenance and evolution are relevant to users, engineers, and researchers who come into contact with software beyond Version 1. The International Conference on Software Maintenance and Evolution (ICSM) is the premiere forum for software maintenance researchers and practitioners to examine, discuss, and exchange ideas regarding the key issues facing the software maintenance community. During the conference, participants from academia, government, and industry share ideas and experiences solving critical software maintenance problems. ICSM 2006 was held in Philadelphia on 24-27 September 2006 in cooperation with several colocated workshops. These included the Eighth IEEE International Symposium on Web Site Evolution (WSE), the Sixth IEEE International Workshop on Source Code Analysis and Manipulation (SCAM), the Second International IEEE Workshop on Software Evolvability, and the Second International Workshop on Predictive Models of Modern Industrial Software Engineering. ICSM 2006’s technical program was anchored by 45 papers selected from 147 submissions. The program also included keynote addresses from three distinguished speakers: Patrick Lardieri, David Notkin, and Richard Stallman. Of the 45 papers, seven were invited to this special issue with five passing the rigorous TSE review process. These five selected papers include two that discuss frameworks and three that present new techniques. The frameworks support the creation of language-independent program analyses and evolvable test suites. Two of the techniques consider source-code reengineering and the final one the challenging problem of making live updates to a software system while it is running. The first of the two framework papers, “An Extensible Metamodel for Program Analysis” by D. Strein, R. Lincke, J. Lundberg, and W. Lowe, describes a language-independent framework for building new analyses. The resulting architecture supports the construction of specific analyses (e.g., refactorings) and is easily extensible through the addition of new front ends to support new languages. This flexibility and the use of loose coupling between components of the existing framework support the easy integration of new components. The paper uses the implementation of the tools VIZZANALYZER and XDEVELOP as a proof of concept. Looking forward, further work includes empirical study (e.g., considering running time and memory consumption) and the incorporation of dynamic analysis into the framework (e.g., to support debuggers and profilers). This paper was published in the September 2007 issue of TSE; however, the abstract of this paper is included in this special section. The paper can be found in the Computer Society Digital Library at http://computer.org/tse/ archives.htm. In the second framework paper, “On the Detection of Test Smells: A Metrics-Based Approach for General Fixture and Eager Test” by B. Van Rompaey, B. Du Bois, S. Demeyer, and M. Rieger, a framework for evaluating the evolvability of white box tests suites alongside the program is presented. The goal of this approach is to avoid the (often significant) cost incurred when test cases must be coevolved with the program. The framework accomplishes this by describing a collection of test smells. Akin to code smells, test smells allow the concrete expression of what a good evolvable test is by exploiting the principles that underlie white box testing. The paper proposes a formal description of test smells by means of metric predictors, empirically evaluated for two example test smells. Looking forward, future work will consider the interplay between test smells and frequently changing test cases. Understanding how test smells emerge and grow should help in proactively detecting current and future smells. The third and fourth papers address reengineering, a problem into which significant software evolution energy is invested. The first of these two papers, “API-Evolution Support with Diff-CatchUp” by Z. Xing and E. Stroulia, addresses the API evolution problem. In short, reusable components, and thus their APIs, must evolve in response to client needs for improved functionality, quality, and generality. Applications using an API which evolve independently can thus “break.” To tackle the API-evolution problem, the paper presents a technique and a tool that automatically recognizes API changes in a reused component and proposes plausible fixes based on working examples of the framework code base. Looking forward, planned extensions to the work IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 33, NO. 12, DECEMBER 2007 797

This paper introduces the Species per Path approach to search-based software test data generation. The approach transforms the program under test into a version in which multiple paths to the search target are factored out. Test data are then sought for each individual path by dedicated 'species' operating in parallel. The factoring out of paths results in several individual search landscapes, with feasible paths giving rise to landscapes that are potentially more conducive to test data discovery than the original overall landscape.The paper presents the results of two empirical studies that validate and verify the approach. The validation study supports the claim that the approach is widely applicable and practical. The verification study shows that it is possible to generate test data for targets with the approach that are troublesome for the standard evolutionary method.

The goal of this research is to apply language processing techniques to extend human judgment into situations where obtaining direct human judgment is impractical due to the volume of information that must be considered. On aspect of this is leveraged quality assessments, which can be used to evaluate third-party coded subsystems, to track quality across the versions of a program, to assess the compression effort (and subsequent cost) required to make a change, and to identify parts of a program in need of preventative maintenance. A description of the QALP tool, its output from just under two million lines of code, and an experiment aimed at evaluating the tool's use in leveraged quality assessment are presented. Statistically significant results from this experiment validate the use of the QALP tool in human leverage quality assessment

Readers of programs have two main sources of domain information: identifier names and comments. When functions are uncommented, as many are, comprehension is almost exclusively dependent on the identifier names. Assuming that writers of programs want to create quality identifiers (e.g., include relevant domain knowledge) how should they go about it? For example, do the initials of a concept name provide enough information to represent the concept? If not, and a longer identifier is needed, is an abbreviation satisfactory or does the concept need to be captured in an identifier that includes full words? Results from a study designed to investigate these questions are reported. The study involved over 100 programmers who were asked to describe twelve different functions. The functions used three different "levels" of identifiers: single letters, abbreviations, and full words. Responses allow the level of comprehension associated with the different levels to be studied. The functions include standard algorithms studied in computer science courses as well as functions extracted from production code. The results show that full word identifiers lead to the best comprehension; however, in many cases, there is no statistical difference between full words and abbreviations

Abstract A formal relationship between program slicing and partial evaluation is established. It is proved that for terminating programs, a residual program produced by partial evaluation is semantically equivalent to a conditioned slice.

Aspect-oriented programming (AOP) provides mechanisms for the separation of crosscutting concerns - functionalities scattered through the system and tangled with the base code. Existing systems are a natural testbed for the AOP approach since they often contain several crosscutting concerns which could not be modularized using traditional programming constructs. This paper presents an automated approach to the problem of migrating systems developed according to the object-oriented programming (OOP) paradigm into aspect-oriented programming (AOP). A simple set of six refactorings has been defined to transform OOP to AOP and has been implemented in the AOP-migrator tool, an Eclipse plug-in. A set of enabling transformations from OOP to OOP complement the initial set of refactorings. The paper presents the results of four case studies, which use the approach to migrate selected crosscutting concerns from medium-sized Java programs (in the range of 10K to 40K lines of code) into equivalent programs in AspectJ. The case study results show the feasibility of the migration and indicate the importance of the enabling transformations as a preprocessing step

This paper presents a human-guided automated approach to refactoring object oriented programs to the aspect oriented paradigm. The approach is based upon the iterative application of four steps: discovery, enabling, selection, and refactoring. After discovering potentially applicable refactorings, the enabling step transforms the code to improve refactorability. During the selection phase the particular refactorings to apply are chosen. Finally, the refactoring phase transforms the code by moving the selected code to a new aspect. This paper presents the results of an evaluation in which one of the crosscutting concerns of a 40,000 LoC program (JHotDraw) is refactored.

A dependence cluster is a set of program statements all of which are mutually inter-dependent. Such clusters can cause problems for maintenance, because a change to any statement in the cluster will have a potential impact on all statements in the cluster. This paper introduces the concept of dependence clusters and dependence pollution and shows how a simple visualisation can be used to quickly and effectively locate them. The paper presents the results of two empirical studies and several case studies which evaluate the approach. The results indicate the importance of dependence cluster analysis: for a set of 20 programs, ranging in size from 1,170 LoC to 179,623 LoC, 99.6% of clusters identified were within 1% tolerance of being identical, while dependence clusters were found to be surprisingly common: 80% of the programs studied contained clusters of 10% or more of the program.

Abstract Program slicing and concept assignment have both been proposed as source code extraction techniques. Unfortunately, each has a weakness that prevents wider application. For slicing, the extraction criterion is expressed at a very low level; constructing a slicing criterion requires detailed code knowledge which is often unavailable. The concept assignment extraction criterion is expressed at the domain level. However, unlike a slice, the extracted code is not executable as a separate subprogram in its own right. This paper introduces a unification of slicing and concept assignment which exploits their combined advantages, while overcoming these two individual weaknesses. Our ‘concept slices’ are executable programs extracted using high‐level criteria. The paper introduces four techniques that combine slicing and concept assignment and algorithms for each. These algorithms were implemented in two separate tools used to illustrate the application of the concept slicing algorithms in two very different case studies. The first is a commercially‐written COBOL module from a large financial organization, the second is an open source utility program written in C. Copyright © 2005 John Wiley & Sons, Ltd.

Evolutionary testing is an effective technique for automatically generating good quality test data. However, for structural testing, the technique degenerates to random testing in the presence of flag variables, which also present problems for other automated test data generation techniques. Previous work on the flag problem does not address flags assigned in loops.This paper introduces a testability transformation that transforms programs with loop--assigned flags so that existing genetic approaches can be successfully applied. It then presents empirical data demonstrating the effectiveness of the transformation. Untransformed, the genetic algorithm flounders and is unable to find a solution. Two transformations are considered. The first allows the search to find a solution. The second reduces the time taken by an order of magnitude and, more importantly, reduces the slope of the cost increase; thus, greatly increasing the complexity of the problem to which the genetic algorithm can be applied. The paper also presents a second empirical study showing that loop--assigned flags are prevalent in real world code. They account for just under 11% of all flags.

Empirical data concerning the qualitative and quantitative nature of program dependence is presented for a set of 20 programs ranging from 600 lines of code to 167,000 lines of code. The sources of dependence considered are global variables and formal parameters and the targets considered are a program's predicate nodes. The results show that as the number of formal parameters available to a predicate increases, there is a decrease in the proportion of these formal parameters which are depended upon by the predicate. No such correlation was found for global variables. Results from theoretical and actual computation time analysis indicate that the computation of dependence information is practical, suggesting that the analysis may be beneficial to several application areas. The paper also presents results concerning correlations that provide strong evidence that the global and formal dependence sources are independent of one another and that the numbers of globals and formals are independent of the size of the procedure that contains them. Finally, two visualization techniques for displaying dependence information are introduced. Illustrations show how these visualizations and predicate dependence analysis can assist in activities such as testing, comprehension, and evolution.

Many source code analyses are closely related to and strongly influenced by interdependence among program components. This paper reports results from an empirical study of the interdependences involving program predicates and the formal parameters and global variables which potentially affect them. The findings show that it is possible to eliminate from consideration approximately 30% of the formal parameters, 50% of the 'touched' global variables, and 97% of the 'visible' global variables. Another important and encouraging finding is a strong inverse correlation between the number of formal parameters and dependence level. The fact that no such correlation was found for global variables provides evidence to support the conjecture that global variables are harmful.

A large-scale study of 43 C programs totaling just over 1 million lines of code is presented. The study includes the forward and backward static slice on every executable statement. In total 2353598 slices were constructed, with an average slice size being just under 30% of the original program. The results also show that ignoring calling-context led to a 50% increase in average slice size and, in contrast to previous results, a 66-77% increase in computation time (due to the increased size). Though not the principal focus of the study, the results also show an average pace for the slicing engine, on a standard PC, of 3 million lines of code per second thereby providing additional evidence for static slicing's practicability.

Software maintainers face a wide range of difficult tasks including impact analysis and regression testing. Understanding semantic relationships, such as the semantic cohesiveness in a program or the semantic differences between two programs, can help a maintainer address these problems. However, semantic analysis is a difficult problem. For example, few semantic differencing algorithms and even fewer implementations exist. The first semantic differencing implementation for the C language is presented and studied. A large collection of semantic differences of 10 programs are computed. The average size reduction was 37.70%. The study presented illustrates the practicality of semantics differencing. Finally, the application of semantic differencing in the area of program testing and impact analysis is considered.

Software maintainers are faced with the task of regression testing: retesting a modified program on an often large number of test cases. The cost of regression testing can be reduced if the size of the program is reduced and if old test cases and results can be reused. Two complimentary algorithms for reducing the cost of regression testing are presented. The first produces a program called Differences that captures the semantic change between Certified, a previously tested program, and Modified, a changed version of Certified. It is more efficient to test Differences, because it omits unchanged computations. The program Differences is computed using a combination of program slices. The second algorithm identifies test cases for which Certified and Modified produce the same output and existing test cases that test new components in Modified. The algorithm is based on the notion of common execution patterns. Program components with common execution patterns have the same execution pattern during some call to their procedure. They are computed using a calling context slice. Whereas an interprocedural slice includes the program components necessary to capture all possible executions of a statement, a calling context slice includes only those program components necessary to capture the execution of a statement in a particular calling context. Together with Differences, it is possible to test Modified by running Differences on a smaller number of test cases. This is more efficient than running Modified on a large number of test cases. A prototype implementation has been built to examine and illustrate these algorithms.

Software maintainers are faced with the task of regression testing: retesting a modified program on a (large) number of test cases. The cost of regression testing can be reduced if old test cases and old test results can be reused. Reuse avoids the costly construction of new test cases and the unproductive rerunning of existing test cases when it can be guaranteed that the modified and original programs will produce the same results. An algorithm that uses language semantics to provide such a guarantee is presented. This algorithm uses semantic (not syntactic) differences and similarities between the old and new programs. The algorithm is based on the notion of common execution patterns, which is the interprocedural extension of equivalent execution patterns. Program components with common execution patterns are computed using a new type of interprocedural slice called a calling context slice. Whereas an interprocedural slice includes the program components necessary to capture all possible executions of a statement, a calling context slice includes only those program components necessary to capture the execution of a statement in a particular calling context (i.e., a particular call to the procedure).

Given a program Base and two variants, A and B, each created by modifying separate copies of Base, the goal of program integration is to determine whether the modifications interfere, and if they do not, to create an integrated program that incorporates both sets of changes as well as the portions of Base preserved in both variants. Text-based integration techniques, such as the one used by the Unix diff3 utility, are obviously unsatisfactory because one has no guarantees about how the execution behavior of the integrated program relates to the behaviors of Base, A, and B. The first program integration algorithm to provide such guarantees was developed by Horwitz, Prins, and Reps. However, a limitation of that algorithm is that it only applied to programs written in a restricted language—in particular, the algorithm does not handle programs with procedures. This article describes a generalization of the Horwitz-Prins-Reps algorithm that handles programs that consist of multiple (and possibly mutually recursive) procedures. We show that two straightforward generalizations of the Horwitz-Prins-Reps algorithm yield unsatisfactory results. The key issue in developing a satisfactory algorithm is how to take into account different calling contexts when determining what has changed in the variants A and B. Our solution to this problem involves identifying two different kinds of affected components of A and B: those affected regardless of how the procedure is called, and those affected by a changed or new calling context. The algorithm makes use of interprocedural program slicing to identify these components, as well as components in Base, A, and B with the same behavior.

An algorithm is presented that reduces the cost of regression testing by reducing the number of test cases that must be rerun and by reducing the size of the program that they must be run on. The algorithm uses dependence graphs and program slicing to partition the components of the new program into two sets: preserved points-components that have unchanged run-time behaviour; and affected points-components that have changed run-time behavior. Only test cases that test the behavior of affected points just be rerun; the behavior of the preserved points is guaranteed to be the same in the old and new versions of the program. Furthermore, the algorithm produces a program 'difference', which captures the behavior of (only) the affected points. Thus, rather than restricting the (large) new program on a large number of test cases, it is possible to certify the new program by running the (smaller) program 'differences' on a (smaller) number of test cases.>

The notion of a program slice , originally introduced by Mark Weiser, is useful in program debugging, automatic parallelization, and program integration. A slice of a program is taken with respect to a program point p and a variable x ; the slice consists of all statements of the program that might affect the value of x at point p . This paper concerns the problem of interprocedural slicing—generating a slice of an entire program, where the slice crosses the boundaries of procedure calls. To solve this problem, we introduce a new kind of graph to represent programs, called a system dependence graph , which extends previous dependence representations to incorporate collections of procedures (with procedure calls) rather than just monolithic programs. Our main result is an algorithm for interprocedural slicing that uses the new representation. (It should be noted that our work concerns a somewhat restricted kind of slice: rather than permitting a program to b e sliced with respect to program point p and an arbitrary variable, a slice must be taken with respect to a variable that is defined or used at p .) The chief difficulty in interprocedural slicing is correctly accounting for the calling context of a called procedure. To handle this problem, system dependence graphs include some data dependence edges that represent transitive dependences due to the effects of procedure calls, in addition to the conventional direct-dependence edges. These edges are constructed with the aid of an auxiliary structure that represents calling and parameter-linkage relationships. This structure takes the form of an attribute grammar. The step of computing the required transitive-dependence edges is reduced to the construction of the subordinate characteristic graphs for the grammar's nonterminals.