GECCO '18- Proceedings of the Genetic and Evolutionary Computation Conference

GECCO '18- Proceedings of the Genetic and Evolutionary Computation Conference

Full Citation in the ACM Digital Library

SESSION: Search-based software engineering

Multi-objective black-box test case selection for cost-effectively testing simulation models

  • Aitor Arrieta
  • Shuai Wang
  • Ainhoa Arruabarrena
  • Urtzi Markiegi
  • Goiuria Sagardui
  • Leire Etxeberria

In many domains, engineers build simulation models (e.g., Simulink) before developing code to simulate the behavior of complex systems (e.g., Cyber-Physical Systems). Those models are commonly heavy to simulate which makes it difficult to execute the entire test suite. Furthermore, it is often difficult to measure white-box coverage of test cases when employing such models. In addition, the historical data related to failures might not be available. This paper proposes a cost-effective approach for test case selection that relies on black-box data related to inputs and outputs of the system. The approach defines in total five effectiveness measures and one cost measure followed by deriving in total 15 objective combinations and integrating them within Non-Dominated Sorting Genetic Algorithm-II (NSGA-II). We empirically evaluated our approach with all these 15 combinations using four case studies by employing mutation testing to assess the fault revealing capability. The results demonstrated that our approach managed to improve Random Search by 26% on average in terms of the Hypervolume quality indicator.

On the effects of seeding strategies: a case for search-based multi-objective service composition

  • Tao Chen
  • Miqing Li
  • Xin Yao

Service composition aims to search a composition plan of candidate services that produces the optimal results with respect to multiple and possibly conflicting Quality-of-Service (QoS) attributes, e.g., latency, throughput and cost. This leads to a multi-objective optimization problem for which evolutionary algorithm is a promising solution. In this paper, we investigate different ways of injecting knowledge about the problem into the Multi-Objective Evolutionary Algorithm (MOEA) by seeding. Specifically, we propose four alternative seeding strategies to strengthen the quality of the initial population for the MOEA to start working with. By using the real-world WS-DREAM dataset, we conduced experimental evaluations based on 9 different workflows of service composition problems and several metrics. The results confirm the effectiveness and efficiency of those seeding strategies. We also observed that, unlike the discoveries for other problem domains, the implication of the number of seeds on the service composition problems is minimal, for which we investigated and discussed the possible reasons.

Test suite minimization for mutation testing of WS-BPEL compositions

  • Francisco Palomo-Lozano
  • Antonia Estero-Botaro
  • Inmaculada Medina-Bulo
  • Manuel Núñez

This paper presents an exact search-based technique to minimize test suites while maintaining their mutation coverage. The minimization of test suites is a hard problem whose solution is important both to reduce the cost of mutation testing and to precisely assess the quality of existing test suites. This problem can be addressed with Search-Based Software Engineering (SBSE) techniques, including metaheuristics and exact techniques. We have applied Integer Linear Programming (ILP) as an exact technique to reduce the effort of testing with very promising results. Our technique can be adapted to different formalisms but this paper focuses on testing WS-BPEL compositions, as it poses several interesting problems. Despite the fact that web service compositions are relatively small, as they just orchestrate web services, their execution can be very expensive because the deployment and execution of web services, and the underlying infrastructure, are not trivial. Therefore, although test suites for the compositions themselves are also usually small, it is fundamental to reduce, as much as possible and without losing coverage, their size.

Towards the automated recovery of complex temporal API-usage patterns

  • Mohamed Aymen Saied
  • Houari Sahraoui
  • Edouard Batot
  • Michalis Famelis
  • Pierre-Olivier Talbot

Despite the many advantages, the use of external libraries through their APIs remains difficult because of the usage patterns and constraints that are hidden or not properly documented. Existing work provides different techniques to recover API usage patterns from client programs in order to help developers understand and use those libraries. However, most of these techniques produce basic patterns that generally do not involve temporal properties. In this paper, we discuss the problem of temporal usage patterns recovery and propose a genetic-programming algorithm to solve it. Our evaluation on different APIs shows that the proposed algorithm allows to derive non-trivial temporal usage patterns that are useful and generalizable to new API clients.

A novel fitness function for automated program repair based on source code checkpoints

  • Eduardo Faria de Souza
  • Claire Le Goues
  • Celso Gonçalves Camilo-Junior

Software maintenance, especially bug fixing, is one of the most expensive problems in software practice. Bugs have global impact in terms of cost and time, and they also reflect negatively on a company's brand. GenProg is a method for Automated Program Repair based on an evolutionary approach. It aims to generate bug repairs without human intervention or a need for special instrumentation or source code annotations. Its canonical fitness function evaluates each variant as the weighted sum of the test cases that a modified program passes. However, it evaluates distinct individuals with the same fitness score (plateaus). We propose a fitness function that minimizes these plateaus using dynamic analysis to increase the granularity of the fitness information that can be gleaned from test case execution, increasing the diversity of the population, the number of repairs found (expressiveness), and the efficiency of the search. We evaluate the proposed fitness functions on two standard benchmarks for Automated Program Repair: IntroClass and ManyBugs. We find that our proposed fitness function minimizes plateaus, increases expressiveness, and the efficiency of the search.

Dependent input sampling strategies: using metaheuristics for generating parameterised random sampling regimes

  • Komsan Srivisut
  • John A. Clark
  • Richard F. Paige

Understanding extreme execution times is of great importance in gaining assurance in real-time embedded systems. The standard benchmark for dynamic testing---uniform randomised testing---is inadequate for reaching extreme execution times in these systems. Metaheuristics have been shown to be an effective means of directly searching for inputs with such behaviours but the increasing complexity of modern systems is now posing challenges to the effectiveness of this approach. The research reported in this paper investigates the use of metaheuristic search to discover biased random sampling regimes. Rather than search for test inputs, we search for distributions of test inputs that are then sampled. The search proceeds to discover and exploit relationships between test input variables, leading to sampling regimes where the distribution of a sampled parameter depends on the values of previously sampled input parameters. Our results show that test vectors indirectly generated from our dependent approach produce significantly more extreme (longer) execution times than those generated by direct metaheuristic searches.