Powered by
2013 1st International Workshop on Combining Modelling and Search-Based Software Engineering (CMSBSE),
May 20, 2013,
San Francisco, CA, USA
1st International Workshop on Combining Modelling and Search-Based Software Engineering (CMSBSE)
Preface
Foreword
Modelling plays a vital role in software engineering, enabling the creation of larger, more complex systems. Search-based software engineering (SBSE) offers a productive and proven approach to software engineering through automated discovery of near-optimal solutions to problems, and has proven itself to be effective on a wide variety of software engineering problems. The aim of this workshop is to highlight that SBSE and modelling have substantial conceptual and technical synergies, and to discuss and present opportunities and novel ways in which they can be combined, whilst fostering the growing community of researchers working in this area.
Keynotes
Harnessing Evolutionary Computation to Enable Dynamically Adaptive Systems to Manage Uncertainty (Keynote)
Betty H. C. Cheng, Andres J. Ramirez, and Philip K. McKinley
(Michigan State University, USA)
A dynamically adaptive system (DAS) must be able to monitor its environment,
adapt to changing conditions, and be resilient to component failures and attacks.
However, the designer of such an adaptive system is faced with a challenging set of tasks:
anticipating how and when the system will need to adapt in the future,
codifying this behavior in decision-making components to govern the adaptation,
and ensuring system integrity during and after adaptation.
These tasks are particularly difficult for systems that must operate safely
in the face of continuous dynamics and environmental uncertainty.
In the biological world, evolution has done a remarkable job of producing systems
that adapt to their environment and survive dynamic and adverse conditions.
In this talk, we discuss preliminary investigations and motivate future investigation for how to exploit this power by
integrating evolutionary computation into the model-based development and run-time support
of high-assurance, dynamically-adaptable systems
@InProceedings{CMSBSE13p1,
author = {Betty H. C. Cheng and Andres J. Ramirez and Philip K. McKinley},
title = {Harnessing Evolutionary Computation to Enable Dynamically Adaptive Systems to Manage Uncertainty (Keynote)},
booktitle = {Proc.\ CMSBSE},
publisher = {IEEE},
pages = {1--6},
doi = {},
year = {2013},
}
Modelling and Search: Efficient, Practical, and Innovative Approaches to Software Engineering (Invited Tutorial)
Simon Poulding
(University of York, UK)
An overview of the invited tutorial `Modelling and Search: Efficient, Practical, and Innovative Approaches to Software Engineering', presented at the First International Workshop on Combining Modelling and Search-Based Software Engineering (CMSBSE 2013).
@InProceedings{CMSBSE13p7,
author = {Simon Poulding},
title = {Modelling and Search: Efficient, Practical, and Innovative Approaches to Software Engineering (Invited Tutorial)},
booktitle = {Proc.\ CMSBSE},
publisher = {IEEE},
pages = {7--7},
doi = {},
year = {2013},
}
Testing
Testing Elastic Systems with Surrogate Models
Alessio Gambi, Waldemar Hummer, and Schahram Dustdar
(TU Vienna, Austria; University of Lugano, Switzerland)
We combine search-based test case generation and surrogate models for black-box system testing of elastic systems. We aim to efficiently generate tests that expose functional errors and performance problems related to system elasticity. Elastic systems dynamically change their resources allocation to provide consistent quality of service in face of workload fluctuations. However, their ability to adapt could be a double edged sword if not properly designed: They may fail to acquire the right amount of resources or even fail to release them. Black-box system testing may expose such problems by stimulating system elasticity with suitable sequences of interactions. However, finding such sequences is far from trivial because the number of possible combinations of requests over time is unbounded. In this paper, we analyze the problem of generating test cases for elastic systems, we cast it as a search-based optimization combined with surrogate models, and present the conceptual framework that supports its execution.
@InProceedings{CMSBSE13p8,
author = {Alessio Gambi and Waldemar Hummer and Schahram Dustdar},
title = {Testing Elastic Systems with Surrogate Models},
booktitle = {Proc.\ CMSBSE},
publisher = {IEEE},
pages = {8--11},
doi = {},
year = {2013},
}
Searching for Models to Evaluate Software Technology
Francisco Gomes de Oliveira Neto,
Robert Feldt, Richard Torkar, and Patricia D. L. Machado
(UFCG, Brazil; Chalmers, Sweden; Gothenburg University, Sweden)
Modeling and abstraction is key in all engineering processes and have found extensive use also in software engineering. When developing new methodologies and techniques to support software engineers we want to evaluate them on realistic models. However, this is a challenge since (1) it is hard to get industry to give access to their models, and (2) we need a large number of models to systematically evaluate a technology. This paper proposes that search-based techniques can be used to search for models with desirable properties, which can then be used to systematically evaluate model-based technologies. By targeting properties seen in industrial models we can then get the best of both worlds: models that are similar to models used in industry but in quantities that allow extensive experimentation. To exemplify our ideas we consider a specific case in which a model generator is used to create models to test a regression test optimization technique.
@InProceedings{CMSBSE13p12,
author = {Francisco Gomes de Oliveira Neto and Robert Feldt and Richard Torkar and Patricia D. L. Machado},
title = {Searching for Models to Evaluate Software Technology},
booktitle = {Proc.\ CMSBSE},
publisher = {IEEE},
pages = {12--15},
doi = {},
year = {2013},
}
Efficient Probabilistic Testing of Model Transformations using Search
Louis M. Rose and Simon Poulding
(University of York, UK)
Checking the output of a test case for correctness--applying a test oracle--is challenging for many types of software, including model transformations. Decreasing the number of test cases that are executed during testing will therefore reduce the costs involved in testing a model transformation. However, there is a trade-off: to be confident that the transformation fulfils its specification requires the execution of sufficient test cases to fully exercise the transformation. In this paper, we demonstrate a process that derives a method of sampling random models which enables the test engineer to balance testing cost and testing efficacy. The output of the process is an optimised probability distribution over the models on which the transformation acts; test sets that efficiently exercise the transformation may then be derived by sampling models from the optimised distribution. Furthermore, we describe benefits and challenges of combining model-driven engineering and search-based software engineering tools and techniques, which include conflating metamodels with grammars to enable grammar-based search techniques over a set of models, and the need to increase the scalability of model-driven engineering tools to make them more amenable to search.
@InProceedings{CMSBSE13p16,
author = {Louis M. Rose and Simon Poulding},
title = {Efficient Probabilistic Testing of Model Transformations using Search},
booktitle = {Proc.\ CMSBSE},
publisher = {IEEE},
pages = {16--21},
doi = {},
year = {2013},
}
Product Lines and Feature Models
Optimum Feature Selection in Software Product Lines: Let Your Model and Values Guide Your Search
Abdel Salam Sayyad, Joseph Ingram, Tim Menzies, and Hany Ammar
(West Virginia University, USA)
In Search-Based Software Engineering, well-known metaheuristic search algorithms are utilized to find solutions to common software engineering problems. The algorithms are usually taken off the shelf and applied with trust, i.e. software engineers are not concerned with the inner workings of algorithms, only with the results. While this may be sufficient is some domains, we argue against this approach, particularly where the complexity of the models and the variety of user preferences pose greater challenges to the metaheuristic search algorithms. We build on our previous investigation which uncovered the power of Indicator-Based Evolutionary Algorithm (IBEA) over traditionally-used algorithms (such as NSGA-II), and in this work we scrutinize the time behavior of user objectives subject to optimization. This analysis brings out the business perspective, previously veiled under Pareto-collective gauges such as Hypervolume and Spread. In addition, we show how slowing down the rates of crossover and mutation can help IBEA converge faster, as opposed to following the higher rates used in many other studies as rules of thumb.
@InProceedings{CMSBSE13p22,
author = {Abdel Salam Sayyad and Joseph Ingram and Tim Menzies and Hany Ammar},
title = {Optimum Feature Selection in Software Product Lines: Let Your Model and Values Guide Your Search},
booktitle = {Proc.\ CMSBSE},
publisher = {IEEE},
pages = {22--27},
doi = {},
year = {2013},
}
Representation of Software Product Line Architectures for Search-Based Design
Thelma Elita Colanzi and Silvia Regina Vergilio
(UFPR, Brazil; UEM, Brazil)
The Product-Line Architecture (PLA) is the main artifact of a Software Product Line (SPL). Search-based approaches can provide automated discovery of near-optimal PLAs and make its design less dependent on human architects. To do this, it is necessary to adopt a suitable PLA representation to apply the search operators. In this sense, we review existing architecture representations proposed by related work, but all of them need to be extended to encompass specific characteristics of SPL. Then, the use of such representations for PLA is discussed and, based on the performed analysis, we introduce a novel direct PLA representation for search-based optimization. Some implementation aspects are discussed involving implementation details about the proposed PLA representation, constraints and impact on specific search operators. Ongoing work addresses the application of specific search operators for the proposed representation and the definition of a fitness function to be applied in a multi-objective search-based approach for the PLA design.
@InProceedings{CMSBSE13p28,
author = {Thelma Elita Colanzi and Silvia Regina Vergilio},
title = {Representation of Software Product Line Architectures for Search-Based Design},
booktitle = {Proc.\ CMSBSE},
publisher = {IEEE},
pages = {28--33},
doi = {},
year = {2013},
}
Bi-criteria Genetic Search for Adding New Features into an Existing Product Line
Reza Karimpour and Guenther Ruhe
(University of Calgary, Canada)
Software product line evolution involves decisions like finding which products are better candidates for realizing new feature requests. In this paper, we propose a solution for finding trade-off evolution alternatives for products while balancing between overall value and product integrity. The purpose of this study is to support product managers with feature selection for an existing product line. For this purpose, first, the feature model of the product line is encoded into a single binary encoding. Then we employ a bi-criteria genetic search algorithm, NSGA-II, to find the possible alternatives with different value and product integrity. From the proposed set of trade-off alternatives, the product line manager can select the solutions that best fit with the concerns of their preference. The implementation has been initially evaluated by two product line configurations.
@InProceedings{CMSBSE13p34,
author = {Reza Karimpour and Guenther Ruhe},
title = {Bi-criteria Genetic Search for Adding New Features into an Existing Product Line},
booktitle = {Proc.\ CMSBSE},
publisher = {IEEE},
pages = {34--38},
doi = {},
year = {2013},
}
Metrics on Feature Models to Optimize Configuration Adaptation at Run Time
Luis Emiliano Sanchez, Sabine Moisan, and Jean-Paul Rigault
(UNCPBA, Argentina; INRIA, France)
Feature models are widely used to capture variability, commonalities and configuration rules of software systems. We apply this technique to model component-based systems with many variants during specification, implementation, or run time. This representation allows us to determine the set of valid configurations befitting a given context, especially at run time. A key challenge is to determine the configuration most suitable, especially with respect to non-functional aspects: quality of service, performance, reconfiguration time... We propose an algorithm for selecting the configuration that optimizes a given quality metrics. This algorithm is a variant of the Best-First Search algorithm, a heuristic technique suitable for feature model optimization. The algorithm is parameterized with several strategies and heuristics on feature models leading to different optimality and efficiency properties. We discuss the algorithm, its strategies and heuristics, and we present experimental results showing that the algorithm meets the requirements for our real time systems.
@InProceedings{CMSBSE13p39,
author = {Luis Emiliano Sanchez and Sabine Moisan and Jean-Paul Rigault},
title = {Metrics on Feature Models to Optimize Configuration Adaptation at Run Time},
booktitle = {Proc.\ CMSBSE},
publisher = {IEEE},
pages = {39--44},
doi = {},
year = {2013},
}
Challenge Problems and Position Statements
Complementing Metaheuristic Search with Higher Abstraction Techniques
Frank R. Burton and Simon Poulding
(University of York, UK)
Search-Based Software Engineering and Model-Driven Engineering are both innovative approaches to software engineering. The premise of Search-Based Software Engineering is to reformulate engineering tasks as optimisation problems that can be solved using metaheuristic search techniques. Model-Driven Engineering aims to apply greater levels of abstraction to software engineering problems. In this paper, it is argued that these two approaches are complementary and that both research fields can make further progress by applying techniques from the other. We suggest ways in which synergies between the fields can be exploited.
@InProceedings{CMSBSE13p45,
author = {Frank R. Burton and Simon Poulding},
title = {Complementing Metaheuristic Search with Higher Abstraction Techniques},
booktitle = {Proc.\ CMSBSE},
publisher = {IEEE},
pages = {45--48},
doi = {},
year = {2013},
}
Whither (Away) Software Engineers in SBSE?
Christopher L. Simons
(University of the West of England, UK)
This challenges and open problems paper discusses the role of software engineers when combining modeling with Search-Based Software Engineering (SBSE). With SBSE techniques increasingly providing insights into difficult software modeling problems, the role of the software engineer might be thought of as diminishing. However, given the crucial role of the model understanding in SBSE, we argue that the role of the software engineer will become more important through interactive SBSE, although exploiting this interaction remains a challenge for the field.
@InProceedings{CMSBSE13p49,
author = {Christopher L. Simons},
title = {Whither (Away) Software Engineers in SBSE?},
booktitle = {Proc.\ CMSBSE},
publisher = {IEEE},
pages = {49--50},
doi = {},
year = {2013},
}
Searching Models, Modeling Search: On the Synergies of SBSE and MDE
Marouane Kessentini, Philip Langer, and Manuel Wimmer
(Missouri University of Science and Technology, USA; TU Vienna, Austria)
In the past years, several researchers applied search-based optimization algorithms successfully in the software engineering domain to obtain automatically near-optimal solutions to complex problems posing huge solution spaces. More recently, such algorithms have also been proven useful for solving problems in model engineering. However, applying search-based optimization algorithms to problems in model engineering efficiently and effectively is a challenging endeavor demanding for expertize in both, search-based algorithms as well as model engineering formalisms and techniques. In this paper, we report on our experiences in applying such search-based algorithms for model engineering problems and propose a model-driven approach to ease the adoption of search-based algorithms for the area of model engineering.
@InProceedings{CMSBSE13p51,
author = {Marouane Kessentini and Philip Langer and Manuel Wimmer},
title = {Searching Models, Modeling Search: On the Synergies of SBSE and MDE},
booktitle = {Proc.\ CMSBSE},
publisher = {IEEE},
pages = {51--54},
doi = {},
year = {2013},
}
Advanced Techniques
MOS: An Integrated Model-Based and Search-Based Testing Tool for Function Block Diagrams
Eduard Paul Enoiu, Kivanc Doganay, Markus Bohlin, Daniel Sundmark, and Paul Pettersson
(Mälardalen University, Sweden; Swedish Institute of Computer Science, Sweden)
In this paper we present a new testing tool for safety critical applications described in Function Block Diagram (FBD) language aimed to support both a model and a search-based approach. Many benefits emerge from this tool, including the ability to automatically generate test suites from an FBD program in order to comply to quality requirements such as component testing and specific coverage measurements. Search-based testing methods are used to generate test data based on executable code rather than the FBD program, alleviating any problems that may arise from the ambiguities that occur while creating FBD programs. Test cases generated by both approaches are executed and used as a way of cross validation. In the current work, we describe the architecture of the tool, its workflow process, and a case study in which the tool has been applied in a real industrial setting to test a train control management system.
@InProceedings{CMSBSE13p55,
author = {Eduard Paul Enoiu and Kivanc Doganay and Markus Bohlin and Daniel Sundmark and Paul Pettersson},
title = {MOS: An Integrated Model-Based and Search-Based Testing Tool for Function Block Diagrams},
booktitle = {Proc.\ CMSBSE},
publisher = {IEEE},
pages = {55--60},
doi = {},
year = {2013},
}
Preference-Based Multi-objective Software Modelling
Mohamed W. Mkaouer, Marouane Kessentini, Slim Bechikh, and Daniel R. Tauritz
(Missouri University of Science and Technology, USA; University of Tunis, Tunisia)
In this paper, we propose the use of preference-based evolutionary multi-objective optimization techniques (P-EMO) to address various software modelling challenges. P-EMO allows the incorporation of decision maker (i.e., designer) preferences (e.g., quality, correctness, etc.) in multi-objective optimization techniques by restricting the Pareto front to a region of interest easing the decision making task. We discuss the different challenges and potential benefits of P-EMO in software modelling. We report experiments on the use of P-EMO on a well-known modeling problem where very promising results are obtained.
@InProceedings{CMSBSE13p61,
author = {Mohamed W. Mkaouer and Marouane Kessentini and Slim Bechikh and Daniel R. Tauritz},
title = {Preference-Based Multi-objective Software Modelling},
booktitle = {Proc.\ CMSBSE},
publisher = {IEEE},
pages = {61--66},
doi = {},
year = {2013},
}
Effectively using Search-Based Software Engineering Techniques within Model Checking and Its Applications
Jeremy S. Bradbury, David Kelk, and Mark Green
(University of Ontario, Canada)
In this position paper, we affirm that there are synergies to be gained by using search-based techniques within software model checking. We will show from the literature how meta-heuristic search based techniques can augment both the model checking process and its applications. We will provide evidence to support this assertion in the form of existing research work and open problems that may benefit from combining Search-Based Software Engineering (SBSE) techniques and software model checking.
@InProceedings{CMSBSE13p67,
author = {Jeremy S. Bradbury and David Kelk and Mark Green},
title = {Effectively using Search-Based Software Engineering Techniques within Model Checking and Its Applications},
booktitle = {Proc.\ CMSBSE},
publisher = {IEEE},
pages = {67--70},
doi = {},
year = {2013},
}
proc time: 0.05