Keywords

1 Instance Space Analysis for SBSE

Instance Space Analysis (ISA) has two main goals:

  • to help designers of SBSE techniques (SBSET) gain insight into why some techniques are more or less suited to solve certain SBSE problems, thus devising new and better techniques that address any challenging areas, and

  • to help software developers select the most effective SBSET for their software system.

ISA provides a way for objective assessment of the effectiveness of SBSE techniques. It has been applied to Search-Based Software Testing [5, 6], Search-Based Program Repair [1], machine learning [3], and optimisation [7]. The concept of instance space analysis was first introduced by Smith-Miles in her seminal work looking at the strengths and weaknesses of optimisation problems [7]. Understanding the effectiveness of an SBSE technique is critical for selecting the most suitable technique for a particular SBSE problem, thus avoiding trial and error application of SBSE techniques.

An overview of the ISA for SBSE is presented in Fig. 1. It starts with a set of problems \(p\in P\) and a portfolio of SBSE techniques \(t\in T\). For example, P can be a set of buggy programs and T can be a portfolio of Search-Based Program Repair techniques. The performance of each Search-Based Software Engineering Technique (SBSET) is measured for each problem instance as y(t, p). For example, y can indicate whether a plausible patch has been found for a program p by the Search-Based Program Repair Technique t. The first step of ISA is to identify the significant features of problem instances (\(f(p)\in F\)) that have an impact on how easy or hard they are for a particular SBSET. A feature can be the complexity of code, as measured by code-based complexity metrics. An example is the coupling between object classes, which is a count of the number of other classes to which the current class is coupled [2]. In Search-Based Program Repair, features may include those that are related to the prediction of source code transformations on buggy code [10] and detection of incorrect patches [9].

Next, ISA constructs the footprints \((g(f(P)))\in R^2\) which indicate the area of strength for each SBSET. Finally, ISA applies machine learning techniques on the most significant features to learn a model that can be used for SBSET selection for future application.

Fig. 1.
figure 1

An overview of instance space analysis for analysing the effectiveness of SBSE techqniques.

Full size image

The features included in the feature space (\(\mathcal {F}\)) should be diverse and predictive of the performance of at least one algorithm. Hence, their selection requires careful consideration. They are domain specific and thus developing \(\mathcal {F}\) requires significant domain knowledge. Features should be highly correlated with algorithm performance, not highly correlated with other features, and cheaper to compute compared to the runtime of the algorithm. Features should also be capable of explaining the similarities and differences between instances, and should be interpretable by humans  [3, 4].

The portfolio of SBSE Techniques is constructed by selecting a set of methods, each one with its unique biases, capable of solving the given problem. The more diverse the SBSETs, the higher the chance of finding the most suitable SBSET for a given instance.

The SBSET performance space \(\mathcal {Y}\) includes the measures to report the performance of the SBSETs when solving the problem instances. Common performance measures for automated testing are coverage, length/size of the test suite and mutation score [8]. For Search Based Program Repair, a common measure is whether the techique produced a plausaible patch for a buggy program [1].

A critical step of ISA is identifying features of problem instances instances \(f(p) \in F\) that have an impact on the effectiveness of SBSE techniques. Features are problem dependent and must be chosen such that the varying complexities of the buggy program instances are exposed, any known structural properties of the software systems are captured, and any known advantages and limitations of the different SBSETs are related to features.

Fig. 2.
figure 2

SBSET footprint.

Full size image

ISA applies a Genetic Algorithm to select the set of features which result in an instance space – as defined by the 2-dimensional projection of the subset of features through Principal Component Analysis – with problem instances that show similar performance of SBSETs closer to each other in this 2D space (as shown in Fig. 2). The best subset of features is the one that can best discriminate between easy and hard buggy program instances for SBSE techniques. The subset of features that have large coefficients and therefore contribute significantly to the variance of each Principal Component (PC), will be identified as the significant features. Rather than reporting algorithm performance averaged across a chosen set of problem instances, ISA reports the SBSET’s footprint, which is the performance of a technique generalised across a diverse set of instances.

In the final step, ISA applies Machine Learning to predict the most effective SBSET for solving a particular SBSE problem. ISA uses the most significant features as an input to learn the relationship between the instance features and SBSET performance. A variety of machine learning algorithms can be used for this purpose, such as decision trees, or support vector machines for binary labels (effective/ineffective), or statistical prediction methods, such as regression algorithms or neural networks for continuous labels (e.g., time complexity of the approach). Previous work has reported Random Forest Classifier as the best performing method for Search-Based Program Repair [1], and Decisin Tree for Search-Based Software Testing [5].