Search

Combinatorial interaction testing (CIT) is an important technique for testing highly configurable software systems with demonstrated effectiveness in practice. The goal of CIT is to generate test cases covering the interactions of configuration options, under certain hard constraints. In this context, constrained covering arrays (CCAs) are frequently used as test cases in CIT. Constrained Covering Array Generation (CCAG) is an NP-hard combinatorial optimization problem, solving which requires an effective method for generating small CCAs. In particular, effectively solving t-way CCAG with t > 4 is even more challenging. Inspired by the success of automated algorithm configuration and automated algorithm selection in solving combinatorial optimization problems, in this paper, we investigate the efficacy of automated algorithm configuration and automated algorithm selection for the CCAG problem, and propose a novel, automated CCAG approach called AutoCCAG. Extensive experiments on public benchmarks show that AutoCCAG can find much smaller-sized CCAs than current state-of-the-art approaches, indicating the effectiveness of AutoCCAG. More encouragingly, to our best knowledge, our paper reports the first results for CCAG with a high coverage strength (i.e., 5-way CCAG) on public benchmarks. Our results demonstrate that AutoCCAG can bring considerable benefits in testing highly configurable software systems. [ABSTRACT FROM AUTHOR]

Recently, there has been extensive research on mobile devices and stream cipher to increase security. The Rabbit stream cipher was selected for the final eSTREAM portfolio organized by EU ECRYPT and as one of algorithms of the ISO/IEC 18033-4 Stream Ciphers on ISO Security Standardization. As the Rabbit evaluated the complexity of side-channel analysis attack as 'medium' in a theoretical approach, the method of correlation power analysis attack and the feasibility of a practical power analysis attack in the experiments are described in this paper. We also propose a countermeasure with random masking and hiding schemes for linear operation. We construct the algorithm of the countermeasure with an additional operating time of 24% with 12.3% increased memory requirements to maintain high-speed performance. We use an eight-bit RISC AVR microprocessor (ATmega 128L) to implement our methods to show that the proposed method is secure against correlation power analysis attacks in practical experiments. [ABSTRACT FROM AUTHOR]

In Continuous Integration (CI), regression testing is constrained by the time between commits. This demands for careful selection and/or prioritization of test cases within test suites too large to be run entirely. To this aim, some Machine Learning (ML) techniques have been proposed, as an alternative to deterministic approaches. Two broad strategies for ML-based prioritization are learning-torank and what we call ranking-to-learn (i.e., reinforcement learning). Various ML algorithms can be applied in each strategy. In this paper we introduce ten of such algorithms for adoption in CI practices, and perform a comprehensive study comparing them against each other using subjects from the Apache Commons project.We analyze the influence of several features of the code under test and of the test process. The results allow to draw criteria to support testers in selecting and tuning the technique that best fits their context. [ABSTRACT FROM AUTHOR]

When a program fails to process an input, it need not be the program code that is at fault. It can also be that the input data is faulty, for instance as result of data corruption. To get the data processed, one then has to debug the input data--that is, (1) identify which parts of the input data prevent processing, and (2) recover as much of the (valuable) input data as possible. In this paper, we present a general-purpose algorithm called ddmax that addresses these problems automatically. Through experiments, ddmax maximizes the subset of the input that can still be processed by the program, thus recovering and repairing as much data as possible; the difference between the original failing input and the "maximized" passing input includes all input fragments that could not be processed. To the best of our knowledge, ddmax is the first approach that fixes faults in the input data without requiring program analysis. In our evaluation, ddmax repaired about 69% of input files and recovered about 78% of data within one minute per input. [ABSTRACT FROM AUTHOR]

We would like to welcome you to this, the first workshop on Developing Tools as Plug-Ins (TOPI 2011). Tools and environments to increase software quality and productivity have always been an important aspect of software engineering. There are two major ways for programmers to communicate with the computer - programming languages and tools. Through languages, programmers encode decisions, actions and algorithms, while tools have the added advantage of providing analysis, synthesis and visualization. At the same time, software development environments have grown in power: today's environments, such as Visual Studio, Eclipse or an Emacs configuration, bear little resemblance to those of two decades ago. Syntactic and documentation support, recommendations for fixes and re-factorings, relatively seamless integration with version control and debugging tools, and more, are not only available, but are expected by modern programmers. Plug-ins are the modern approach towards incrementally adding new tools into these rich environments. Proving for plug-ins is necessary because it is at best very hard to get programmers to try a new tool without integrating it into an existing environment. Indeed, our knowledge of how to solve software engineering problems is increasingly being encapsulated in tools. These tools are at their strongest when they operate in a pre-existing development environment. This approach allows integration with existing elements such as compilers, debuggers, profilers, visualizers as well as numerous other development and, often, runtime tools. However, building tools as plug-ins can be challenging. How do they interact with the core environment? How do they interact with one another - especially since each developer may choose a different set of plug-ins? How can we share tools across different, and future, core development environments? These are all questions that will be addressed during TOPI 2011. The workshop received 32 submissions from 21 countries. They attested to the interest in the topic and to the diversity of IDEs currently in use today, including Visual Studio 2010, Eclipse and MonoDevelop. Each paper was reviewed by three member of the PC, and then there followed a vigorous online meeting. From this, we selected 14 full papers and 8 short papers, giving an acceptance rate of 68%. Through these papers, we shall address the following themes: *identify recent successful tools as plug-ins *categorize the characteristics of good plug-ins *understand interoperability requirements to making tools available across platforms *list which tools lend themselves best to the plug-in approach *specify the medium and long term challenges of tools as plug-ins So, while we are more concerned in this workshop with understanding the characteristics and creation of tools as plug-ins, than of the tools themselves, we did accept some papers with very interesting tools, including those from industry. The workshop will be opened with a welcoming session by the chairs, followed by a keynote by Tom Ball from Microsoft Research on the Software Engineering of Plug-in Architectures. The talk will be punctuated by personal insights and Tom's long experience as a research leader. In the following two sessions, selected papers describing successful plug-in experience and practice will be presented. We want to try and identify patterns and commonalities that could be used to characterize "good" plug-ins. The goal was to come out with a first version of a framework that could be used to classify plug-in tools. During the third session we invited a discussion around presentations that tackled the barriers of making plug-ins available across different platforms. Rather than arguing for an agnostic approach, the goal is to better understand the differences and identify opportunities to interact and cooperate. The last session of the workshop is dedicated to presentations that look into the future of tools as plug-ins, followed by a brainstorming session on medium and long term challenges of plug-in development. The papers to be presented at TOPI 2011 indicate that developing better ways to plug tools into modern environments, and developing better ways for those tools to interact with other related tools in these environments, is definitively a critical research topic. [ABSTRACT FROM AUTHOR]

Multithreaded programs can have deadlocks, even after deployment, so users may want to run deadlock tools on deployed programs. However, current deadlock predictors such as MagicLock and UnDead have large overheads that make them impractical for enduser deployment and confine their use to development time. Such overhead stems from running an exponential-time algorithm on a large execution trace. In this paper, we present the first lowoverhead deadlock predictor, called AirLock, that is fit for both in-house testing and deployed programs. AirLock maintains a small predictive lock reachability graph, searches the graph for cycles, and runs an exponential-time algorithm only for each cycle. This approach lets AirLock find the same deadlocks as MagicLock and UnDead but with much less overhead because the number of cycles is small in practice. Our experiments with real-world benchmarks show that the average time overhead of AirLock is 3.5%, which is three orders of magnitude less than that of MagicLock and UnDead. AirLock's low overhead makes it suitable for use with fuzz testers like AFL and on-the-fly after deployment. [ABSTRACT FROM AUTHOR]

Concurrency is a requirement for much modern software, but the implementation of multithreaded algorithms comes at the risk of errors such as data races. Programmers can prevent data races by documenting and obeying a locking discipline, which indicates which locks must be held in order to access which data. This paper introduces a formal semantics for locking specifications that gives a guarantee of race freedom. A notable difference from most other semantics is that it is in terms of values (which is what the runtime system locks) rather than variables. The paper also shows how to express the formal semantics in two different styles of analysis: abstract interpretation and type theory. We have implemented both analyses, in tools that operate on Java. To the best of our knowledge, these are the first tools that can soundly infer and check a locking discipline for Java. Our experiments compare the implementations with one another and with annotations written by programmers, showing that the ambiguities and unsoundness of previous formulations are a problem in practice. [ABSTRACT FROM AUTHOR]

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. The applicability of model projection rests upon three critical concerns: correctness, effectiveness, and efficiency, all of which are addressed in this paper. We introduce four related algorithms for model projection and prove each correct. We also present an empirical study of effectiveness and efficiency using ten models, including widely studied benchmarks as well as industrial models. Results show that a typical projection includes about half of the states and a third of the transitions from the original model. [ABSTRACT FROM AUTHOR]

Randomized algorithms have been used to successfully address many different types of software engineering problems. This type of algorithms employ a degree of randomness as part of their logic. Randomized algorithms are useful for difficult problems where a precise solution cannot be derived in a deterministic way within reasonable time. However, randomized algorithms produce different results on every run when applied to the same problem instance. It is hence important to assess the effectiveness of randomized algorithms by collecting data from a large enough number of runs. The use of rigorous statistical tests is then essential to provide support to the conclusions derived by analyzing such data. In this paper, we provide a systematic review of the use of randomized algorithms in selected software engineering venues in 2009. Its goal is not to perform a complete survey but to get a representative snapshot of current practice in software engineering research. We show that randomized algorithms are used in a significant percentage of papers but that, in most cases, randomness is not properly accounted for. This casts doubts on the validity of most empirical results assessing randomized algorithms. There are numerous statistical tests, based on different assumptions, and it is not always clear when and how to use these tests. We hence provide practical guidelines to support empirical research on randomized algorithms in software engineering [ABSTRACT FROM AUTHOR]

Mutation testing is widely recognized as being extremely powerful, but is considered difficult to automate enough for practical use. This paper theoretically addresses two possible reasons for this: the generation of redundant mutants and the lack of integration of mutation analysis with other test criteria. By addressing these two issues, this paper brings an important mutation operator, relational-operator-replacement (ROR), closer to practical use. First, we develop fault hierarchies for the six relational operators, each of which generates seven mutants per clause. These hierarchies show that, for any given clause, only three mutants are necessary. This theoretical result can be integrated easily into mutation analysis tools, thereby eliminating generation of 57% of the ROR mutants. Second, we show how to bring the power of the ROR operator to the widely used Multiple Condition-Decision Coverage (MCDC) test criterion. This theoretical result includes an algorithm to transform any MCDC-adequate test set into a test set that also satisfies RORG, a new version of ROR appropriate for the MCDC context. The transformation does not use traditional mutation analysis, so can easily be integrated into existing MCDC tools and processes. [ABSTRACT FROM AUTHOR]

syntax tree (AST) mapping algorithms are widely used to analyze changes in source code. Despite the foundational role of AST mapping algorithms, little effort has been made to evaluate the accuracy of AST mapping algorithms, i.e., the extent to which an algorithm captures the evolution of code. We observe that a program element often has only one best-mapped program element. Based on this observation, we propose a hierarchical approach to automatically compare the similarity of mapped statements and tokens by different algorithms. By performing the comparison, we determine if each of the compared algorithms generates inaccurate mappings for a statement or its tokens. We invite 12 external experts to determine if three commonly used AST mapping algorithms generate accurate mappings for a statement and its tokens for 200 statements. Based on the experts' feedback, we observe that our approach achieves a precision of 0.98-1.00 and a recall of 0.65-0.75. Furthermore, we conduct a large-scale study with a dataset of ten Java projects containing a total of 263,165 file revisions. Our approach determines that GumTree, MTDiff and IJM generate inaccurate mappings for 20%-29%, 25%-36% and 21%-30% of the file revisions, respectively. Our experimental results show that state-of-the-art AST mapping algorithms still need improvements [ABSTRACT FROM AUTHOR]

One of the main challenges of reactive synthesis, an automated procedure to obtain a correct-by-construction reactive system, is to deal with unrealizable specifications. One means to deal with unrealizability, in the context of GR(1), an expressive assume-guarantee fragment of LTL that enables efficient synthesis, is the computation of an unrealizable core, which can be viewed as a fault-localization approach. Existing solutions, however, are computationally costly, are limited to computing a single core, and do not correctly support specifications with constructs beyond pure GR(1) elements. In this work we address these limitations. First, we present QuickCore, a novel algorithm that accelerates unrealizable core computations by relying on the monotonicity of unrealizability, on an incremental computation, and on additional properties of GR(1) specifications. Second, we present Punch, a novel algorithm to efficiently compute all unrealizable cores of a specification. Finally, we present means to correctly handle specifications that include higher-level constructs beyond pure GR(1) elements. We implemented our ideas on top of Spectra, an opensource language and synthesis environment. Our evaluation over benchmarks from the literature shows that QuickCore is in most cases faster than previous algorithms, and that its relative advantage grows with scale. Moreover, we found that most specifications include more than one core, and that Punch finds all the cores significantly faster than a competing naive algorithm. [ABSTRACT FROM AUTHOR]

Differencing tools are highly relevant for a series of software engineering tasks, including analyzing developers' activities, assessing the changeability of software artifacts, and monitoring the maintenance of critical assets such as source clones and vulnerable instructions. This tool demonstration shows the features of l-diff, an enhanced, language-independent line differencing tool. L-diff builds upon the Unix diff and overcomes its limitations in determining whether an artifact line has been changed or is the result of additions and removals, and in tracking artifact fragments that have been moved upward or downward within the file. The paper describes the tool and shows its capability of analyzing changes on different kinds of software artifacts, including use cases, code developed with different programming languages, and test cases. [ABSTRACT FROM AUTHOR]

Despite a decade of active research, there has been a marked lack in clone detection techniques that scale to large repositories for detecting near-miss clones. In this paper, we present a token-based clone detector, SourcererCC, that can detect both exact and near-miss clones from large interproject repositories using a standard workstation. It exploits an optimized inverted-index to quickly query the potential clones of a given code block. Filtering heuristics based on token ordering are used to significantly reduce the size of the index, the number of code-block comparisons needed to detect the clones, as well as the number of required token-comparisons needed to judge a potential clone. We evaluate the scalability, execution time, recall and precision of SourcererCC, and compare it to four publicly available and state-of-the-art tools. To measure recall, we use two recent benchmarks: (1) a big benchmark of real clones, BigCloneBench, and (2) a Mutation/Injection-based framework of thousands of fine-grained artificial clones. We find SourcererCC has both high recall and precision, and is able to scale to a large inter-project repository (25K projects, 250MLOC) using a standard workstation. [ABSTRACT FROM AUTHOR]

The problem of checking a logged event trace against a temporal logic specification arises in many practical cases. Unfortunately, known algorithms for an expressive logic like MTL (Metric Temporal Logic) do not scale with respect to two crucial dimensions: the length of the trace and the size of the time interval of the formula to be checked. The former issue can be addressed by distributed and parallel trace checking algorithms that can take advantage of modern cloud computing and programming frameworks like MapReduce. Still, the latter issue remains open with current stateof- the-art approaches. In this paper we address this memory scalability issue by proposing a new semantics for MTL, called lazy semantics. This semantics can evaluate temporal formulae and boolean combinations of temporal-only formulae at any arbitrary time instant. We prove that lazy semantics is more expressive than point-based semantics and that it can be used as a basis for a correct parametric decomposition of any MTL formula into an equivalent one with smaller, bounded time intervals. We use lazy semantics to extend our previous distributed trace checking algorithm for MTL. The evaluation shows that the proposed algorithm can check formulae with large intervals, on large traces, in a memory-efficient way. [ABSTRACT FROM AUTHOR]

In recent years, researchers have intensively investigated various topics in test prioritization, which aims to re-order tests to increase the rate of fault detection during regression testing. While the main research focus in test prioritization is on proposing novel prioritization techniques and evaluating on more and larger subject systems, little effort has been put on investigating the threats to validity in existing work on test prioritization. One main threat to validity is that existing work mainly evaluates prioritization techniques based on simple artificial changes on the source code and tests. For example, the changes in the source code usually include only seeded program faults, whereas the test suite is usually not augmented at all. On the contrary, in real-world software development, software systems usually undergo various changes on the source code and test suite augmentation. Therefore, it is not clear whether the conclusions drawn by existing work in test prioritization from the artificial changes are still valid for real-world software evolution. In this paper, we present the first empirical study to investigate this important threat to validity in test prioritization. We reimplemented 24 variant techniques of both the traditional and time-aware test prioritization, and investigated the impacts of software evolution on those techniques based on the version history of 8 real-world Java programs from GitHub. The results show that for both traditional and time-aware test prioritization, test suite augmentation significantly hampers their effectiveness, whereas source code changes alone do not influence their effectiveness much. [ABSTRACT FROM AUTHOR]

Conventional concolic testing has been used to provide high coverage of paths in statically typed languages. While it has also been applied in the context of JavaScript (JS) programs, we observe that applying concolic testing to dynamicallytyped JS programs involves tackling unique problems to ensure scalability. In particular, a naive type-agnostic extension of concolic testing to JS programs causes generation of large number of inputs. Consequently, many executions operate on undefined values and repeatedly explore same paths resulting in redundant tests, thus diminishing the scalability of testing drastically. In this paper, we address this problem by proposing a simple yet effective approach that incorporates type-awareness intelligently in conventional concolic testing to reduce the number of generated inputs for JS programs. We extend our approach inter-procedurally by generating preconditions for each function that provide a summary of the relation between the variable types and paths. Employing the function preconditions when testing reduces the number of inputs generated even further. We implement our ideas and validate it on a number of open-source JS programs (and libraries). For a significant percentage (on average 50%) of the functions, we observe that type-aware concolic testing generates a minuscule percentage (less than 5%) of the inputs as compared to conventional concolic testing approach implemented on top of Jalangi. On average, this approach achieves over 97% of line coverage and over 94% of branch coverage for all the functions across all benchmarks. Moreover, the use of function preconditions reduces the number of inputs generated by 50%. We also demonstrate the use of function preconditions in automatically avoiding real crashes due to incorrectly typed objects. [ABSTRACT FROM AUTHOR]

Analyzing performance and understanding the potential bestcase, worst-case and distribution of program execution times are very important software engineering tasks. There have been model-based and program analysis-based approaches for performance analysis. Model-based approaches rely on analytical or design models derived from mathematical theories or software architecture abstraction, which are typically coarsegrained and could be imprecise. Program analysis-based approaches collect program profiles to identify performance bottlenecks, which often fail to capture the overall program performance. In this paper, we propose a performance analysis framework PerfPlotter. It takes the program source code and usage profile as inputs and generates a performance distribu- tion that captures the input probability distribution over execution times for the program. It heuristically explores high- probability and low-probability paths through probabilistic symbolic execution. Once a path is explored, it generates and runs a set of test inputs to model the performance of the path. Finally, it constructs the performance distribution for the program. We have implemented PerfPlotter based on the Symbolic PathFinder infrastructure, and experimentally demonstrated that PerfPlotter could accurately capture the bestcase, worst-case and distribution of program execution times. We also show that performance distributions can be applied to various important tasks such as performance understanding, bug validation, and algorithm selection. [ABSTRACT FROM AUTHOR]

Many defect prediction techniques are proposed to improve software reliability. Change classification predicts defects at the change level, where a change is the modifications to one file in a commit. In this paper, we conduct the first study of applying change classification in practice. We identify two issues in the prediction process, both of which contribute to the low prediction performance. First, the data are imbalanced--there are much fewer buggy changes than clean changes. Second, the commonly used cross-validation approach is inappropriate for evaluating the performance of change classification. To address these challenges, we apply and adapt online change classification, resampling, and updatable classification techniques to improve the classification performance. We perform the improved change classification techniques on one proprietary and six open source projects. Our results show that these techniques improve the precision of change classification by 12.2-89.5%or 6.4-34.8 percentage points (pp.) on the seven projects. In addition, we integrate change classification in the development process of the proprietary project. We have learned the following lessons: 1) new solutions are needed to convince developers to use and believe prediction results, and prediction results need to be actionable, 2) new and improved classification algorithms are needed to explain the prediction results, and insensible and unactionable explanations need to be filtered or refined, and 3) new techniques are needed to improve the relatively low precision. [ABSTRACT FROM AUTHOR]

Numerous trace retrieval algorithms incorporate the standard tf-idf (term frequency, inverse document frequency) technique to weight various terms. In this paper we address Grand Challenge C-GC1 by comparing the effectiveness of computing idf based only on the local terms in the query, versus computing it based on general term usage as documented in the American National Corpus. We also address Grand Challenges L-GC1 and L-GC2 by setting ourselves the additional task of designing and conducting the experiments using the alpha-release of TraceLab. TraceLab is an experimental workbench which allows researchers to graphically model and execute a traceability experiment as a workflow of components. Results of the experiment show that the local idf approach exceeds or matches the global approach in all of the cases studied. [ABSTRACT FROM AUTHOR]

Most log files are of one format - a flat file with the events of execution recorded one after the other. Each line in the file contains at least a timestamp, a combination of one or more event identifiers, and the actual log message with information of which event was executed and what the values for the dynamic parameters of that event are. Since log files have this trace information, we can use it for many purposes, such as operational profiling and anomalous execution path detection. However the current flat file format of a log file is very unintuitive to detect the existence of a repeating pattern. In this paper we propose a transformation of the current serial order format of a log file to a directed cyclic graph (such as a non-finite state machine) format and how the operational profile of a system can be built from this representation of the log file. We built a tool (in C++), that transforms a log file with a set of log events in a serial order to an adjacency matrix for the resulting graphical representation. We can then easily apply existing graph theory based algorithms on the adjacency matrix to analyze the log file of the system. The directed cyclic graph and the analysis of it can be visualized by rendering the adjacency matrix with graph visualization tools, like Graphviz. [ABSTRACT FROM AUTHOR]

Efficient algorithms are extremely important and can be crucial for certain software projects. Even though many source code search engines have been proposed in the literature to help software developers find source code related to their needs, to our knowledge there has been no effort to develop systems that keep abreast of the latest algorithmic developments. In this paper, we describe our initial effort towards developing such an algorithm search engine. The proposed system extracts and indexes algorithms discussed in academic literature and their associated metadata. Users can search the index through a free text query interface. The source code of proposed system, being developed as a part of a larger open source toolkit, SeerSuite, will be released in due course. We also provide directions for further research and improvements of the current system. [ABSTRACT FROM AUTHOR]

Testing scientific software involves dealing with special challenges like missing test oracle and different possible sources of a problem. When testing scientific frameworks, additionally a large variety of mathematical algorithms and possible applications for the framework has to be handled. We propose to use concepts of software product line engineering to handle this variability. The contribution of this paper is a two-step process for reengineering a variability model out of a framework for scientific software. This process is explained with a real case study. Furthermore, we sketch how the variability model can be used to systematically derive system test applications for the framework. [ABSTRACT FROM AUTHOR]

Service-oriented systems live in an open world, one in which their functionality and quality of service depend on how the services they interact with evolve. System adaptation has been indicated as a way to cope with the evolution these partner services may have. When a partner does not behave as expected, in an adaptable system we can substitute it with an alternative compatible one. Finding a compatible alternative, however, is a difficult task if we consider conversational services that impose a specific interaction protocol and specific data-types. In this paper we introduce Interaction Sequence Charts (ISC) as an effective notation for describing the interactions a service has with its partners, and an algorithm that uses these charts to establish a "degree of compatibility" between interacting services. The algorithm considers both interaction protocol requirements and datatype similarity, for which fuzzy techniques are adopted. The expressive power of ISC is validated by using it to describe the complex behaviour that can be defined using BPEL 2.0, while the algorithm is validated on an example in the field of Tele-Radiology, and shown to be advantageous in practice. [ABSTRACT FROM AUTHOR]

The FixCache algorithm, introduced in 2007, effectively identifies files or methods which are likely to contain bugs by analyzing source control repository history. However, many open questions remain about the behaviour of this algorithm. What is the variation in the hit rate over time? How long do files stay in the cache? Do buggy files tend to stay buggy, or can they be redeemed? This paper analyzes the behaviour of the FixCache algorithm on four open source projects. FixCache hit rate is found to generally increase over time for three of the four projects; file duration in cache follows a Zipf distribution; and topmost bug-fixed files go through periods of greater and lesser stability over a project's history. [ABSTRACT FROM AUTHOR]

Many software defect prediction models have been built using historical defect data obtained by mining software repositories (MSR). Recent studies have discovered that data so collected contain noises because current defect collection practices are based on optional bug fix keywords or bug report links in change logs. Automatically collected defect data based on the change logs could include noises. This paper proposes approaches to deal with the noise in defect data. First, we measure the impact of noise on defect prediction models and provide guidelines for acceptable noise level. We measure noise resistant ability of two well-known defect prediction algorithms and find that in general, for large defect datasets, adding FP (false positive) or FN (false negative) noises alone does not lead to substantial performance differences. However, the prediction performance decreases significantly when the dataset contains 20%-35% of both FP and FN noises. Second, we propose a noise detection and elimination algorithm to address this problem. Our empirical study shows that our algorithm can identify noisy instances with reasonable accuracy. In addition, after eliminating the noises using our algorithm, defect prediction accuracy is improved. [ABSTRACT FROM AUTHOR]

We study the problem of model checking software product line (SPL) behaviours against temporal properties. This is more difficult than for single systems because an SPL with n features yields up to 2n individual systems to verify. As each individual verification suffers from state explosion, it is crucial to propose efficient formalisms and heuristics. We recently proposed featured transition systems (FTS), a compact representation for SPL behaviour, and defined algorithms for model checking FTS against linear temporal properties. Although they showed to outperform individual system verifications, they still face a state explosion problem as they enumerate and visit system states one by one. In this paper, we tackle this latter problem by using symbolic representations of the state space. This lead us to consider computation tree logic (CTL) which is supported by the industry-strength symbolic model checker NuSMV. We first lay the foundations for symbolic SPL model checking by defining a feature-oriented version of CTL and its dedicated algorithms. We then describe an implementation that adapts the NuSMV language and tool infrastructure. Finally, we propose theoretical and empirical evaluations of our results. The benchmarks show that for certain properties, our algorithm is over a hundred times faster than model checking each system with the standard algorithm. [ABSTRACT FROM AUTHOR]

Merge conflicts are inevitable in collaborative software development and are disruptive. When they occur, developers have to stop their current work, understand the conflict and the surrounding code, and plan an appropriate resolution. However, not all conflicts are equally problematic--some can be easily fixed, while others might be complicated enough to need multiple people. Currently, there is not much support to help developers plan their conflict resolution. In this work, we aim to predict the difficulty of a merge conflict so as to help developers plan their conflict resolution. The ability to predict the difficulty of a merge conflict and to identify the underlying factors for its difficulty can help tool builders improve their conflict detection tools to prioritize and warn developers of difficult conflicts. In this work, we investigate the characteristics of difficult merge conflicts, and automatically classify them. We analyzed 6,380 conflicts across 128 java projects and found that merge conflict difficulty can be accurately predicted (AUC of 0.76) through machine learning algorithms, such as bagging. [ABSTRACT FROM AUTHOR]

In automotive software and system design, explicit system and especially software models have only recently found their way into the development process. This paper will try to give an overview for what such models have so-far been used and which advantages they brought to vehicle manufacturers and suppliers. Another focus of this paper is the comparison to functional models which are already used in the automotive industry to define control algorithms and function implementation. In many cases too strong analogies have been seen between the existing functional control algorithm models and the new system models { leading to suboptimal development processes and tools. This paper will therefore try to outline differences between these model types. Finally, a synthesis between functional, system, and software models will be sketched. [ABSTRACT FROM AUTHOR]

Scalability is a major challenge for existing behavioral log analysis algorithms, which extract finite-state automaton models or temporal properties from logs generated by running systems. In this paper we present statistical log analysis, which addresses scalability using statistical tools. The key to our approach is to consider behavioral log analysis as a statistical experiment. Rather than analyzing the entire log, we suggest to analyze only a sample of traces from the log and, most importantly, provide means to compute statistical guarantees for the correctness of the analysis result. We present the theoretical foundations of our approach and describe two example applications, to the classic k-Tails algorithm and to the recently presented BEAR algorithm. Finally, based on experiments with logs generated from real-world models and with real-world logs provided to us by our industrial partners, we present extensive evidence for the need for scalable log analysis and for the effectiveness of statistical log analysis. [ABSTRACT FROM AUTHOR]

Many software engineering problems are multi-objective in nature, which has been largely recognized by the Search-based Software Engineering (SBSE) community. In this regard, Paretobased search algorithms, e.g., Non-dominated Sorting Genetic Algorithm II, have already shown good performance for solving multi-objective optimization problems. These algorithms produce Pareto fronts, where each Pareto front consists of a set of nondominated solutions. Eventually, a user selects one or more of the solutions from a Pareto front for their specific problems. A key challenge of applying Pareto-based search algorithms is to select appropriate quality indicators, e.g., hypervolume, to assess the quality of Pareto fronts. Based on the results of an extended literature review, we found that the current literature and practice in SBSE lacks a practical guide for selecting quality indicators despite a large number of published SBSE works. In this direction, the paper presents a practical guide for the SBSE community to select quality indicators for assessing Pareto-based search algorithms in different software engineering contexts. The practical guide is derived from the following complementary theoretical and empirical methods: 1) key theoretical foundations of quality indicators; 2) evidence from an extended literature review; and 3) evidence collected from an extensive experiment that was conducted to evaluate eight quality indicators from four different categories with six Pareto-based search algorithms using three real industrial problems from two diverse domains. [ABSTRACT FROM AUTHOR]

Compilers, as one of the most important infrastructure of today's digital world, are expected to be trustworthy. Different testing techniques are developed for testing compilers automatically. However, it is unknown so far how these testing techniques compared to each other in terms of testing effectiveness: how many bugs a testing technique can find within a time limit. In this paper, we conduct a systematic and comprehensive empirical comparison of three compiler testing techniques, namely, Randomized Differential Testing (RDT), a variant of RDT--Different Optimization Levels (DOL), and Equivalence Modulo Inputs (EMI). Our results show that DOL is more effective at detecting bugs related to optimization, whereas RDT is more effective at detecting other types of bugs, and the three techniques can complement each other to a certain degree. Furthermore, in order to understand why their effectiveness differs, we investigate three factors that in uence the effectiveness of compiler testing, namely, efficiency, strength of test oracles, and effectiveness of generated test programs. The results indicate that all the three factors are statistically significant, and efficiency has the most significant impact. [ABSTRACT FROM AUTHOR]

The area of clone detection has considerably evolved over the last decade, leading to approaches with better results, but at the same time using more elaborate algorithms and tool chains. In our opinion a level has been reached, where the initial investment required to setup a clone detection tool chain and the code infrastructure required for experimenting with new heuristics and algorithms seriously hampers the exploration of novel solutions or specific case studies. As a solution, this paper presents CloneDetective, an open source framework and tool chain for clone detection, which is especially geared towards configurability and extendability and thus supports the preparation and conduction of clone detection research. [ABSTRACT FROM AUTHOR]

One of the difficulties in understanding and debugging spreadsheets is due to the invisibility of the data flow structure which is associated with cell formulas. In this paper, we present a spreadsheet visualization approach that is mainly based on the Markov Clustering (MCL) algorithm in an attempt to help spreadsheet users understand and debug their spreadsheets. The MCL algorithm helps in visualizing large graphs by generating clusters of cells. In our visualization approach, we also use compound fisheye views and tree-maps to help in the navigation of the generated clusters. Compound fish eye views help to view members of a particular cluster while showing their linkages with other clusters. Tree-maps help to visualize the depth we are at while navigating a cluster tree. Our initial experiments show that graph-based spreadsheet visualization using the MCL algorithm generates clusters which match with the corresponding logical areas of a given spreadsheet. Our experiments also show that analysis of the clusters helps us to identify some errors in the spreadsheets. [ABSTRACT FROM AUTHOR]

One of the major problems with software project management is the difficulty to predict accurately the required effort for developing software applications. Analogy Software effort estimation appears well suited to model problems of this nature. The analogy approach may be viewed as a systematic development of the expert opinion through experience learning and exposure to analogue case studies. The accuracy of such model depends on characteristics of datasets. This paper examines the impact of feature subset selection algorithms on improving the accuracy of analogy software effort estimation model. We proposed a feature subset selection algorithm based on fuzzy logic for analogy software effort estimation models. Validation using two established datasets (ISBSG, Desharnais) shows that using fuzzy features subset selection algorithm in analogy software effort estimation contribute to significant results as other algorithms: Hill climbing, Forward subset selection, and backward subset selection do. [ABSTRACT FROM AUTHOR]

Program specifications are important in many phases of the software development process, but they are often omitted or incomplete. An important class of specifications takes the form of temporal properties that prescribe proper usage of components of a software system. Recent work has focused on the automated inference of temporal specifications from the static or runtime behavior of programs. Many techniques match a specification pattern (represented by a finite state automaton) to all possible combinations of program components and enumerate the possible matches. Such approaches suffer from high space complexity and have not scaled beyond simple, two-letter alternating patterns (e.g. (ab)*). In this paper, we precisely define this form of specification mining and show that its general form is NP-complete. We observe a great deal of regularity in the representation and tracking of all possible combinations of system components. This motivates us to introduce a symbolic algorithm, based on binary decision diagrams (BDDs), that exploits this regularity. Our results show that this symbolic approach expands the tractability of this problem by orders of magnitude in both time and space. It enables us to mine more complex specifications, such as the common three-letter resource acquisition, usage, and release pattern ((ab+ c)*) We have implemented our algorithm in a practical tool and used it to find significant specifications in real systems, including Apache Ant and Hibernate. We then used these specifications to find previously unknown bugs. [ABSTRACT FROM AUTHOR]

Conducting controlled experiments about programming activities often requires the use of multiple tasks of similar difficulty. In previously reported work about a controlled experiment investigating software exploration tools, we tried to select two change tasks of equivalent difficulty to be performed on a medium-sized code base. Despite careful effort in the selection and confirmation from our pilot subjects finding the two tasks to be of equivalent difficulty, the data from the experiment suggest the subjects found one of the tasks more difficult than the other. In this paper, we report on early work to create a metric to estimate the cognitive difficulty for a software change task. Such a metric would help in comparing between studies of different tools, and in designing future studies. Our particular approach uses a graph-theoretic statistic to measure the complexity of the task solution by the connectedness of the solution elements. The metric predicts the perceived difficulty for the tasks of our experiment, but fails to predict the perceived difficulty for other tasks to a small pro- gram. We discuss these differences and suggest future approaches. [ABSTRACT FROM AUTHOR]

The C++ Standard Library implementation provided with the free GNU C++ compiler, libstdc++, provides a \parallel mode" as of version 4.3. Using this mode enables existing serial code to take advantage of many parallelized STL algorithms, an approach to making use of multi-core processors which are now or will soon will be ubiquitous. This paper describes the software engineering issues discovered during implementation, the results of user testing, and presents possible solutions to outstanding issues. Design issues with configuring the software environment to a wide variety of multi-core hardware options, in uencing algorithm and parameter choices at compile and run time, standards compliance, and the interplay between execution speed, the executable size, the library code size, and the compilation time are addressed. [ABSTRACT FROM AUTHOR]

The new software retesting concept which bases on the idea of the hidden program errors detection was described in this paper. Purpose of this concept is the program hidden errors identification after basic testing. As a result, the software life cycle was supplemented, because customer realizes retesting at incoming inspection stage. We use special architecture of artificial neural net for estimation of the software retesting necessity. It is a multi-layer-perceptron, which is composed with a simple Rosenblatt perceptron. The most effective training algorithms for this architecture are CGB on base conjugate-gradient method, one-step algorithm of secant method, algorithm SCG and threshold back-propagation error algorithm. The trained neural net gives information about total quantity and importance of the different levels errors in program. [ABSTRACT FROM AUTHOR]

It is widely known that the general matching problem on graphs is a non-polynomial optimization problem. Thus all differencing algorithms we know of use heuristics to identify corresponding elements (e.g.[2],[6]) apart from those that rely on unique identifiers (e.g.[5],[3]). We wonder if an exact algorithm can be designed which computes a minimal cost matching between the elements of the class diagrams and which, although it shows a non-polynomial worst case behaviour, delivers its solution much faster in most cases. In this position paper we describe our ongoing work, the idea of an algorithm which works with estimated transformation costs in order to reduce the computation costs. The algorithm has not been implemented yet; it has only been manually tested on a few examples. [ABSTRACT FROM AUTHOR]

State machines and similar state models are heavily used model types in model-driven development. This paper discusses how state models can be compared, more precisely how the difference between two state models should be defined, how it can be eficiently computed, and how it can be displayed. Some of the issues result from an inappropriate design of the UML metamodels and can be solved by switching to a more appropriate metamodel. Another issue are move operations, which raise the question how to optimize a difference. We argue in favour of simple heuristics and the interactive correction of a difference. [ABSTRACT FROM AUTHOR]

Unrealizability is a major challenge for GR(1), an expressive assume-guarantee fragment of LTL that enables effi- cient synthesis. Some works attempt to help engineers deal with unrealizability by generating counter-strategies or computing an unrealizable core. Other works propose to repair the unrealizable specification by suggesting repairs in the form of automatically generated assumptions. In this work we present two novel symbolic algorithms for repairing unrealizable GR(1) specifications. The first algorithm infers new assumptions based on the recently introduced JVTS. The second algorithm infers new assumptions directly from the specification. Both algorithms are sound. The first is incomplete but can be used to suggest many different repairs. The second is complete but suggests a single repair. Both are symbolic and therefore efficient. We implemented our work, validated its correctness, and evaluated it on benchmarks from the literature. The evaluation shows the strength of our algorithms, in their ability to suggest repairs and in their performance and scalability compared to previous solutions. [ABSTRACT FROM AUTHOR]

Many modern applications require low-latency processing of large data sets, often by using approximate algorithms that trade accuracy of the results for faster execution or reduced memory consumption. Although the algorithms provide probabilistic accuracy and performance guarantees, a software developer who implements these algorithms has little support from existing tools. Standard profilers do not consider accuracy of the computation and do not check whether the outputs of these programs satisfy their accuracy specifications. We present AXPROF, an algorithmic profiling framework for analyzing randomized approximate programs. The developer provides the accuracy specification as a formula in a mathematical notation, using probability or expected value predicates. AXPROF automatically generates statistical reasoning code. It first constructs the empirical models of accuracy, time, and memory consumption. It then selects and runs appropriate statistical tests that can, with high confidence, determine if the implementation satisfies the specification. We used AXPROF to profile 15 approximate applications from three domains -- data analytics, numerical linear algebra, and approximate computing. AXPROF was effective in finding bugs and identifying various performance optimizations. In particular, we discovered five previously unknown bugs in the implementations of the algorithms and created fixes, guided by AXPROF. [ABSTRACT FROM AUTHOR]

Concurrent data structures are widely used but notoriously difficult to implement correctly. Linearizability is one main correctness criterion of concurrent data structure algorithms. It guarantees that a concurrent data structure appears as a sequential one to users. Unfortunately, linearizability is challenging to verify since a subtle bug may only manifest in a small portion of numerous thread interleavings. Model checking is therefore a potential primary candidate. However, current approaches of model checking linearizability suffer from severe state space explosion problem and are thus restricted in handling few threads and/or operations. This paper describes a scalable, fully automatic and general linearizability checking method based on [16] by incorporating symmetry and partial order reduction techniques. Our insights emerged from the observation that the similarity of threads using concurrent data structures causes model checking to generate large redundant equivalent portions of the state space, and the loose coupling of threads causes it to explore lots of unnecessary transition execution orders. We prove that symmetry reduction and partial order reduction can be combined in our approach and integrate them into the model checking algorithm. We demonstrate its efficiency using a number of real-world concurrent data structure algorithms. [ABSTRACT FROM AUTHOR]

In modern software systems, programs are obtained by dynamically assembling components. This has made it necessary to subject component providers to access-control restrictions. What permissions should be granted to each component? Too few permissions may cause run-time authorization failures, too many constitute a security hole. We have designed and implemented a composite algorithm for precise static permission analysis for Java and the CLR. Unlike previous work, the analysis is modular and fully integrated with a novel slicing-based string analysis that is used to statically compute the string values defining a permission and disambiguate permission propagation paths. The results of our research prototype on production-level Java code support the effectiveness, practicality, and precision of our techniques, and show outstanding improvement over previous work. [ABSTRACT FROM AUTHOR]

Context: There are many methods that input static code features and output a predictor for faulty code modules. These data mining methods have hit a "performance ceiling"; i.e., some inherent upper bound on the amount of information offered by, say, static code features when identifying modules which contain faults. Objective: We seek an explanation for this ceiling effect. Perhaps static code features have "limited information content"; i.e. their information can be quickly and completely discovered by even simple learners. Method: An initial literature review documents the ceiling effect in other work. Next, using three sub-sampling techniques (under-, over-, and micro-sampling), we look for the lower useful bound on the number of training instances. Results: Using micro-sampling, we find that as few as 50 instances yield as much information as larger training sets. Conclusions: We have found much evidence for the limited information hypothesis. Further progress in learning defect predictors may not come from better algorithms. Rather, we need to be improving the information content of the training data, perhaps with case-based reasoning methods. [ABSTRACT FROM AUTHOR]

We present two scalable algorithms for identifying program locations that access thread-shared data in concurrent programs. The static algorithm, though simple, and without performing the expensive whole program information ow analysis, is much more efficient, less memory-demanding, and even more precise than the classical escape analysis algorithm. The dynamic algorithm, powered by a locationbased approach, achieves significant runtime speedups over a precise dynamic escape analysis. Our evaluation on a set of large real world complex multithreaded systems such as Apache Derby and Eclipse shows that our algorithms achieve unprecedented scalability. Used by client applications, our algorithms reduce the recording overhead of a record-replay system by 9X on average (as much as 16X) and increase the runtime logging speed of a data race detector by 32% on average (as much as 52%). [ABSTRACT FROM AUTHOR]

While tremendously useful, automated techniques for tuning the precision of floating-point programs face important scalability challenges. We present Blame Analysis, a novel dynamic approach that speeds up precision tuning. Blame Analysis performs floating-point instructions using different levels of accuracy for their operands. The analysis determines the precision of all operands such that a given precision is achieved in the final result of the program. Our evaluation on ten scientific programs shows that Blame Analysis is successful in lowering operand precision. As it executes the program only once, the analysis is particularly useful when targeting reductions in execution time. In such case, the analysis needs to be combined with search-based tools such as Precimonious. Our experiments show that combining Blame Analysis with Precimonious leads to obtaining better results with significant reduction in analysis time: the optimized programs execute faster (in three cases, we observe as high as 39.9% program speedup) and the combined analysis time is 9x faster on average, and up to 38x faster than Precimonious alone. [ABSTRACT FROM AUTHOR]

We introduce a bi-objective effort estimation algorithm that combines Confidence Interval Analysis and assessment of Mean Absolute Error. We evaluate our proposed algorithm on three different alternative formulations, baseline comparators and current state-of-the-art effort estimators applied to five real-world datasets from the PROMISE repository, involving 724 different software projects in total. The results reveal that our algorithm outperforms the baseline, state-of-the-art and all three alternative formulations, statistically significantly (p < 0:001) and with large effect size ( Å12 ≥ 0:9) over all five datasets. We also provide evidence that our algorithm creates a new state-of-the-art, which lies within currently claimed industrial human-expert-based thresholds, thereby demonstrating that our findings have actionable conclusions for practicing software engineers. [ABSTRACT FROM AUTHOR]

Current requirements elicitation techniques do not deal with an essential part of context awareness: comprehension of the relationships among the numerous contextual elements of a certain domain and how they can positively influence the user task. As a result, solution providers continuously miss the opportunity to delight users by identifying contextual behaviors that will lead to better recommendations or adaptations. This paper discusses this problem and proposes a data-based solution. The expected scientific contributions of the ongoing research are delineated as well. [ABSTRACT FROM AUTHOR]