Search Based Software Engineering

Traditionally, program analysis has been divided into two camps: Static techniques analyze code and safely determine what cannot happen; while dynamic techniques analyze executions to determine what actually has happened. While static analysis suffers from overapproximation, erring on whatever could happen, dynamic analysis suffers from underapproximation, ignoring what else could happen. In this talk, I suggest to systematically generate executions to enhance dynamic analysis, exploring and searching the space of software behavior. First results in fault localization and specification mining demonstrate the benefits of search-based analysis.

On certain classes of problems, recombination is more effective if the parents that are being recombined share common subsolutions. These common subsolutions can be used to decompose the recombination space into linearly independent subproblems. If a problem can be decomposed into k subproblems, a single greedy recombination can select the best of 2 ^k possible offspring. The idea of exploiting decomposability works well for the Traveling Salesman Problem, and appears to be applicable to other problems such as Graph Coloring. For Search Based Software Engineering, these ideas might be useful, for example, when applying Genetic Programming to fix software bugs in large programs. Another way in which we might achieve decomposability is by exploiting program modularity and reoccurring program patterns.

Search-Based Software Engineering (SBSE) has shown itself to be a promising and practical approach to address many long-standing software engineering problems (e.g., test case generation, automatic bug fixing, release planning). They must, however, be carefully evaluated through empirical studies, for example in terms of cost-effectiveness and scalability. Indeed, in most cases, there exist alternatives to solutions based on search, and a careful comparison is typically needed in order to better understand under which conditions each technique can be expected to perform best.

However, because search algorithms are randomized (e.g., metaheuristic search) and many contextual factors can affect their outcome, designing, running, and analyzing such empirical studies is fraught with issues and potential threats to validity. This tutorial aims at providing a number of introductory and fundamental principles to guide the design, execution, and analysis of empirical studies in SBSE. Though such principles will in many cases apply to contexts other than SBSE, the tutorial will target issues that are specific to that realm of research and use representative examples from its literature.

Despite preceding related publications, works dealing with the resolution of software engineering problems by search techniques has especially risen since 2001. By its first decade, the Search Based Software Engineering (SBSE) approach has been successfully employed in several software engineering contexts, using various optimization techniques. Aside the relevance of such applications, knowledge regarding the publication patterns on the field plays an important role to its understanding and identity. Such information may also shed light into SBSE trends and future. This paper presents the first bibliometric analysis to SBSE publications. The study covered 740 publications of the SBSE community from 2001 through 2010. The performed bibliometric analysis concerned mainly in four categories: Publication, Sources, Authorship, and Collaboration. Additionally, estimates for the next years of several publication metrics are given. The study also analyzed the applicability of bibliometric laws in SBSE, such as Bradfords and Lotka.

When applying search-based software engineering (SBSE) techniques one is confronted with a multitude of different parameters that need to be chosen: Which population size for a genetic algorithm? Which selection mechanism to use? What settings to use for dozens of other parameters? This problem not only troubles users who want to apply SBSE tools in practice, but also researchers performing experimentation – how to compare algorithms that can have different parameter settings? To shed light on the problem of parameters, we performed the largest empirical analysis on parameter tuning in SBSE to date, collecting and statistically analysing data from more than a million experiments. As case study, we chose test data generation, one of the most popular problems in SBSE. Our data confirm that tuning does have a critical impact on algorithmic performance, and over-fitting of parameter tuning is a dire threat to external validity of empirical analyses in SBSE. Based on this large empirical evidence, we give guidelines on how to handle parameter tuning.

Landscape theory provides a formal framework in which combinatorial optimization problems can be theoretically characterized as a sum of a special kind of landscape called elementary landscape. The decomposition of the objective function of a problem into its elementary components provides additional knowledge on the problem that can be exploited to create new search methods for the problem. We analyze the Test Suite Minimization problem in Regression Testing from the point of view of landscape theory. We find the elementary landscape decomposition of the problem and propose a practical application of such decomposition for the search.

One of the most important issues in a software development project is the requirements prioritization. This task is used to indicate an order for the implementation of the requirements. This problem has uncertain aspects, therefore Fuzzy Logic concepts can be used to properly represent and tackle the task. The objective of this work is to present a formal framework to aid the decision making in prioritizing requirements in a software development process, including ambiguous and vague data.

In the past few years, there has been a growing interest in automating refactoring activities using metaheuristic approaches. These current refactoring approaches involve source-to-source transformation. However, detailed information at source-code level makes precondition checking and source-level refactorings hard to perform. It also severely limits how extensively a program can be refactored. While design improvement tools can be used for a deep and fast design exploration, it is left to the programmer to manually apply the required refactorings to the source code, which is a burdensome task.

To tackle the above problems, our proposal is based on a multi-level refactoring approach that involves both design and source code in the refactoring process. Initially, the program design is extracted from the source code. Then, in a design exploration phase, using a metaheuristic approach, the design is transformed to a better one in terms of a metrics suite as well as the user perspective. The source code is then refactored based on both the improved design and the metrics suite. Using this approach, we expect a deeper and faster exploration of the program design space, that may result more opportunities for design improvement.

Automatically generated state machines are constrained by their complexity, which can be reduced via hierarchy generation. A technique has been demonstrated for hierarchy generation, although evaluation of this technique has proved difficult.

There are a variety of metrics that can be used to provide indicators of how complicated a state machine or statechart is, one such example is cyclomatic complexity (the number of edges - the number of states + 2). Despite this, the existing complexity metric for statecharts does not operate on the hierarchy, instead providing an equivalent cyclomatic complexity for statecharts by ignoring it.

This paper defines two new metrics; Top Level Cyclomatic Complexity and Hierarchical Cyclomatic Complexity. These metrics assess the complexity of a hierarchical machine directly, as well as allowing for comparison between the original, flat state machine and its hierarchical counterpart.

Model checking is a fully automatic technique for checking concurrent software properties in which the states of a concurrent system are explored in an explicit or implicit way. The main drawback of this technique is the high memory consumption, which limits the size of the programs that can be checked. In the last years, some researchers have focused on the application of guided non-complete stochastic techniques to the search of the state space of such concurrent programs. In this paper, we compare five metaheuristic algorithms for this problem. The algorithms are Simulated Annealing, Ant Colony Optimization, Particle Swarm Optimization and two variants of Genetic Algorithm. To the best of our knowledge, it is the first time that Simulated Annealing has been applied to the problem. We use in the comparison a benchmark composed of 17 Java concurrent programs. We also compare the results of these algorithms with the ones of deterministic algorithms.

Previous work has shown the efficacy of using Estimation of Distribution Algorithms (EDAs) to detect faults in concurrent software/systems. A promising feature of EDAs is the ability to analyse the information or model learned from any particular execution. The analysis performed can yield insights into the target problem allowing practitioners to adjust parameters of the algorithm or indeed the algorithm itself. This can lead to a saving in the effort required to perform future executions, which is particularly important when targeting expensive fitness functions such as searching concurrent software state spaces. In this work, we describe practical scenarios related to detecting concurrent faults in which reusing information discovered in EDA runs can save effort in future runs, and prove the potential of such reuse using an example scenario. The example scenario consists of examining problem families, and we provide empirical evidence showing real effort saving properties for three such families.

This paper describes a novel approach to the derivation of model-driven engineering (MDE) models using metaheuristic search, and illustrates it using a specific engineering problem: that of deriving computer game characters with desirable properties. The character behaviour is defined using a human-readable domain-specific language (DSL) that is interpreted using MDE techniques. We apply the search to the underlying MDE metamodels, rather than the DSL directly, and as a result our approach is applicable to a wide range of MDE models. An implementation developed using the Eclipse Modeling Framework, the most widely-used toolset for MDE, is evaluated. The results demonstrate not only the derivation of characters with the desired properties, but also the identification of unexpected features of the behavioural description language and the game itself.

This paper presents an approach to Search Based Software Project Management based on Cooperative Co-evolution. Our approach aims to optimize both developers’ team staffing and work package scheduling through cooperative co-evolution to achieve early overall completion time. To evaluate our approach, we conducted an empirical study, using data from four real-world software projects. Results indicate that the Co-evolutionary approach significantly outperforms a single population evolutionary algorithm. Cooperative co-evolution has not previously been applied to any problem in Search Based Software Engineering (SBSE), so this paper reports the first application of cooperative co-evolution in the SBSE literature. We believe that co-evolutionary optimization may fit many applications in other SBSE problem domains, since software systems often have complex inter-related subsystems and are typically characterized by problems that need to be co-evolved to improve results.

Ant Colony Optimization (ACO) has been successfully employed to tackle a variety of hard combinatorial optimization problems, including the traveling salesman problem, vehicle routing, sequential ordering and timetabling. ACO, as a swarm intelligence framework, mimics the indirect communication strategy employed by real ants mediated by pheromone trails. Among the several algorithms following the ACO general framework, the Ant Colony System (ACS) has obtained convincing results in a range of problems. In Software Engineering, the effective application of ACO has been very narrow, being restricted to a few sparse problems. This paper expands this applicability, by adapting the ACS algorithm to solve the well-known Software Release Planning problem in the presence of dependent requirements. The evaluation of the proposed approach is performed over 72 synthetic datasets and considered, besides ACO, the Genetic Algorithm and Simulated Annealing. Results are consistent to show the ability of the proposed ACO algorithm to generate more accurate solutions to the Software Release Planning problem when compared to Genetic Algorithm and Simulated Annealing.

While models are recognized to be crucial for business process management, often no model is available at all or available models are not aligned with the actual process implementation. In these contexts, an appealing possibility is recovering the process model from the existing system. Several process recovery techniques have been proposed in the literature. However, the recovered processes are often complex, intricate and thus difficult to understand for business analysts.

In this paper, we propose a process reduction technique based on multi-objective optimization, which at the same time minimizes the process complexity and its non-conformances. This allows us to improve the process model understandability, while preserving its completeness with respect to the core business properties of the domain. We conducted a case study based on a real-life e-commerce system. Results indicate that by balancing complexity and conformance our technique produces understandable and meaningful reduced process models.

As the majority of today’s software applications employ a graphical user interface (GUI), it is an important though challenging task to thoroughly test those interfaces. Unfortunately few tools exist to help automating the process of testing. Despite of their well-known deficits, scripting- and capture and replay applications remain among the most common tools in the industry. In this paper we will present an approach where we treat the problem of generating test sequences to GUIs as an optimization problem. We employ ant colony optimization and a relatively new metric called MCT (Maximum Call Tree) to search fault-sensitive test cases. We therefore implemented a test environment for Java SWT applications and will present first results of our experiments with a graphical editor as our main application under test.

The integration test of aspect-oriented systems involves the determination of an order to integrate and test classes and aspects, which should be associated to a minimal possible stubbing cost. To determine such order is not trivial because different factors influence on the stubbing process. Many times these factors are in conflict and diverse good solutions are possible. Due to this, promising results have been obtained with multi-objective and evolutionary algorithms that generally optimize two coupling measures: number of attributes and methods. However, the problem can be more effectively addressed considering as many as coupling measures could be associated to the stubbing process. Therefore, this paper introduces MECBA, a Multi-Evolutionary and Coupling-Based Approach to the test and integration order problem, which includes the definition of models to represent the dependency between modules and to quantify the stubbing costs. The approach is instantiated and evaluated considering four AspectJ programs and four coupling measures. The results represent a good trade-off between the objectives and an example of use of the obtained results shows how they can be used to reduce test effort and costs.

In this paper, we discuss how a search-based branch coverage approach can be used to design an effective test data generation approach, specifically targeting divide-by-zero exceptions. We first propose a novel testability transformation combining approach level and branch distance. We then use different search strategies, i.e. hill climbing, simulated annealing, and genetic algorithm, to evaluate the performance of the novel testability transformation on a small synthetic example as well as on methods known to throw divide-by-zero exceptions, extracted from real world systems, namely Eclipse and Android. Finally, we also describe how the test data generation for divide-by-zero exceptions can be formulated as a constraint programming problem and compare the resolution of this problem with a genetic algorithm in terms of execution time. We thus report evidence that genetic algorithm using our novel testability transformation out-performs hill climbing and simulated annealing and a previous approach (in terms of numbers of fitness evaluation) but is out-performed by constraint programming (in terms of execution time).

Despite claims of “embarrassing parallelism” for many optimisation algorithms, there has been very little work on exploiting parallelism as a route for SBSE scalability. This is an important oversight because scalability is so often a critical success factor for Software Engineering work. This paper shows how relatively inexpensive General Purpose computing on Graphical Processing Units (GPGPU) can be used to run suitably adapted optimisation algorithms, opening up the possibility of cheap scalability. The paper develops a search based optimisation approach for multi objective regression test optimisation, evaluating it on benchmark problems as well as larger real world problems. The results indicate that speed–ups of over 25x are possible using widely available standard GPUs. It is also encouraging that the results reveal a statistically strong correlation between larger problem instances and the degree of speed up achieved. This is the first time that GPGPU has been used for SBSE scalability.

Bytecode as produced by modern programming languages is well suited for search-based testing: Different languages compile to the same bytecode, bytecode is available also for third party libraries, all predicates are atomic and side-effect free, and instrumentation can be performed without recompilation. However, bytecode is also susceptible to the flag problem; in fact, regular source code statements such as floating point operations might create unexpected flag problems on the bytecode level. We present an implementation of state-of-the-art testability transformation for Java bytecode, such that all Boolean values are replaced by integers that preserve information about branch distances, even across method boundaries. The transformation preserves both the original semantics and structure, allowing it to be transparently plugged into any bytecode-based testing tool. Experiments on flag problem benchmarks show the effectiveness of the transformation, while experiments on open source libraries show that although this type of problem can be handled efficiently it is less frequent than expected.

The identification of cohesive segments in execution traces is an important step in concept location which, in turns, is of paramount importance for many program-comprehension activities. In this paper, we reformulate concept location as a trace segmentation problem solved via dynamic programming. Differently to approaches based on genetic algorithms, dynamic programming can compute an exact solution with better performance than previous approaches, even on long traces. We describe the new problem formulation and the algorithmic details of our approach. We then compare the performances of dynamic programming with those of a genetic algorithm, showing that dynamic programming reduces dramatically the time required to segment traces, without sacrificing precision and recall; even slightly improving them.

The application of multiobjective optimization to address Software Engineering problems is a growing trend. Multiobjective algorithms provide a balance between the ability of the computer to search a large solution space for valuable solutions and the capacity of the human decision-maker to select an alternative when two or more incomparable objectives are presented. However, when more than a single objective is available to be taken into account in a search process, the number of objectives to be considered becomes part of the decision. We have examined the effectiveness of using modularization quality (MQ) as an objective function in the context of the software module clustering problem. We designed and executed a set of experiments using both randomlygenerated and real-world instances of varying size and complexity and a fixed calculation budget set in a per instance basis. Results collected from these experiments show that using MQ as an extra objective can improve search results for small instances (few modules to be clustered), while it decreases search quality for larger instances (more than 100 modules to be clustered). Search quality was measure both in terms of the number of distinct solutions found and on their coverage of the solution space, according to the spread and hypervolume quality indicators. We correlated problem characteristics (number of modules, clusters, and dependencies), instance attributes (module dependency distribution patterns), and algorithmic measures (MQ conflict with cohesion and coupling) and found that these elements can only partially explain the effectiveness of using MQ as an extra objective.

We present a survey based on papers published in the first two editions of the Symposium on Search-Based Software Engineering (2009 and 2010). The survey addresses how empirical studies are being designed and used by researchers to support evidence on the effectiveness and efficiency of heuristic search techniques when applied to Software Engineering problems. The survey reuses the structure and research questions proposed by a systematic review published in the context of search-based software testing and covering research papers up to 2007. A list of validity threats for SBSE experiments is also proposed and the extent to which the selected research papers address these threats is evaluated. We have compared our results with those presented by the former systematic review and observed that the number of Search-based Software Engineering (SBSE) research papers supported by well-designed and well-reported empirical studies seems to be growing over the years. On the other hand, construct, internal, and external validity threats are still not properly addressed in the design of many SBSE experiments.

Although there is extensive literature in software defect prediction techniques, machine learning approaches have yet to be fully explored and in particular, Subgroup Discovery (SD) techniques. SD algorithms aim to find subgroups of data that are statistically different given a property of interest [1,2]. SD lies between predictive (finding rules given historical data and a property of interest) and descriptive tasks (discovering interesting patterns in data). An important difference with classification tasks is that the SD algorithms only focus on finding subgroups (e.g., inducing rules) for the property of interest and do not necessarily describe all instances in the dataset.

Automated software refactoring is known to be one of the “hard” combinatorial optimization problems of the search-based software engineering field. The difficulty is mainly due to candidate solution representation, objective function description and necessity of functional behavior preservation of software. The problem is formulated as a combinatorial optimization problem whose objective function is characterized by an aggregate of object-oriented metrics or pareto-front solution description. In our recent empirical study, we have reported the results of a comparison among alternative search algorithms applied for the same problem: pure random, steepest descent, multiple first descent, simulated annealing, multiple steepest descent and artificial bee colony searches. The main goal of the study was to investigate potential of alternative multiple and population-based search techniques. The results showed that multiple steepest descent and artificial bee colony algorithms were most suitable two approaches for an efficient solution of the problem. An important observation was either with depth-oriented multiple steepest descent or breadth-oriented population-based artficial bee colony searches, better results could be obtained through higher number of executions supported by a lightweight solution representation. On the other hand different from multiple steepest descent search, population-based, scalable and being suitable for parallel execution characteristics of artificial bee colony search made the population-based choices to be the topic of this empirical study. In this study, we report the search-based parallel refactoring results of an empirical comparative study among three population-based search techniques namely, artificial bee colony search, local beam search and stochastic beam search and a non-populated technique multiple steepest descent as the baseline. For our purpose, we used parallel features of our prototype automated refactoring tool A-CMA written in Java language. A-CMA accepts bytecode compiled Java codes as its input. It supports 20 different refactoring actions that realize searches on design landscape defined by an adhoc quality model being an aggregation of 24 object-oriented software metrics. We experimented 6 input programs written in Java where 5 of them being open source codes and one student project code. The empirical results showed that for almost all of the considered input programs with different run parameter settings, local beam search is the most suitable population-based search technique for the efficient solution of the search-based parallel refactoring problem in terms of mean and maximum normalized quality gain. However, we observed that the computational time requirement for local beam search becomes rather high when the beam size exceeds 60. On the other hand, even though it is not able to identify high quality designs for less populated search setups, time-efficiency and scalability properties of artificial bee colony search makes it a good choice for population sizes ≥ 200.

Software testing is the process of evaluating the quality of the software under test (SUT) by controlled execution, with the primary aim to reveal inadequate behavior. Despite the automation offered by modern development environments, the process of test data generation remains a largely manual task. In this paper we present a model-based approach for the generation of test data, using searchbased software engineering technique.

The Search Based Software Engineering (SBSE) field has emerged as an exciting and promising area by proposing the formulation of software engineering problems as optimization problems. Hitherto, metaheuristics have been widely employed for solving these problems, whilst little work has been done regarding the use of exact techniques in the area. This paper aims to fulfil this lack by presenting a comprehensive study on the theory and practice of the application of exact optimization in SBSE. A conceptual comparison of both optimization approaches in the software engineering context is presented. Problems’ aspects are analysed regarding suitability for use of exact techniques. As illustration, comparison experiments with exact technique and metaheuristics are conducted over a well-known SBSE problem. The results reveal the overall behaviour of exact techniques, regarding efficacy and efficiency, in the SBSE context considered, indicating its potential use.

We have developed a powerful tool [1,2,3] by which extant software, written in the Java programming language, or in a language that compiles to Java bytecode, can be evolved directly, without an intermediate genomic representation, and with no restrictions on the constructs used. We provide an overview of this system, some previous results, its usability, and the application of FINCH to evolving Java-written game heuristics.