Search-based Software Engineering

Coordinator: Dr Brad Alexander

Many activities in software engineering involve some element of search. Some examples include selection of requirements, localisation and correction of defects, and the optimisation of test coverage. The fast-growing field of Search-Based Software Engineering (SBSE) applies computing resources to these search problems to improve the efficiency and quality of software engineering artefacts and processes.

OptLog is expanding its research in SBSE. Our current areas of interest including test coverage of verification systems, software defect repair and direct exploration of program design spaces.

Dynamic Adaptive Software Configuration

Our primary goal is to optimise energy consumption on Android mobile phones. To model the power usage, we use an event-based modelling technique. The internal battery fuel gauge chip is used to measure the amount of energy being consumed and accordingly the model is built on. We use the model to estimate components' energy usages. In addition, we use evolutionary computation to prolong the battery life. This can be achieved by using the power consumption model as a fitness function, re-configuring the smartphone's default settings and modifying existing code of applications.

Much of our current work in this area focusses on the optimisation of code for modern Android devices. This involves the use of running the optimisation on the phone ("in-vivo") -- at times with amplifications due to the small signal -- and also the use of custom models. During our work, we have encountered many stumbling stones, ranging from erratic tool-chains and temperature-dependent energy readings to system states and time-varying noise.

Test Coverage of Verifcation Systems

For verification systems to be used it is important for them to be demonstrated as reliable and correct. One way to test verification systems is to expose them to proof cases that drive them through their sets of axioms. The OptLog group has explored new ways to measure axiom coverage. We have also created novel methods of driving better axiom coverage with existing benchmark sets through the selective removal of axioms to drive proofs through alternative paths. Current research focuses on optimising the set of changes required to maximise axiom coverage.

Software Defect Repair

Manual localisation and repair of software defects is costly and time-consuming. Recently there has been strong interest in the develpment of processes and tools for automatic repair. The OptLog group has been successful in applying evolutionary search in the creation of patches to repair small applications programs. In future we would like to apply recent improvments in localisation techniques to boost current approaches.

Direct Exploration of Program Design Spaces

Direct search can be applied to specific problems in the discovery and improvement of substantial software artifacts. The OptLog group has applied search to the problem of improving strategies for the application of rewriting rules in an optimising compiler. More recently we have used search techniques to automate the discovery of non-trivial recurrences from hand-drawn trees. Future work will focus on leveraging more information from trees to expand the range of recurrences that can be inferred.

Optimisation in Security

Many problems in the greater security space can be formulated as optimisation problems, too. Moreover, the tools developed in the optimisation community can be used to better understand the characterstics of problems in securit. Among other, the OptLog group has used fitness landscape analyses to better understand S-boxes, and to rewrite AES cipher code as the assembly level to mitigate power-based leakage of information.

Rosita is our code rewrite engine that uses a leakage emulator ELMO which we amended to correctly emulate the micro-architecture of a target system. We use Rosita to automatically protect masked implementations of AES and Xoodoo and show the absence of observable leakage at only a 25% penalty to the performance.

Publications

• Rosita++: Automatic Higher-Order Leakage Elimination from Cryptographic Code, Madura Shelton, Niels Samwel, Łukasz Chmielewski, Markus Wagner, Lejla Batina, and Yuval Yarom, ACM CCS 2022 eprint, code
• Toward more efficient heuristic construction of Boolean functions, Domagoj Jakobovic, Stjepan Picek, Marcella S. R. Martins, Markus Wagner, Applied Soft Computing (accepted on 11 March 2021) Applied Soft Computing, PDF
• Rosita: Towards Automatic Elimination of Power-Analysis Leakage in Ciphers, Madura A Shelton, Niels Samwel, Lejla Batina, Francesco Regazzoni, Markus Wagner, and Yuval Yarom arxiv accepted at NDSS 2021 and at Real World Crypto 2021 (presentation-only conference), recording
• Genetic Improvement @ ICSE 2020, Langdon et al., ACM SIGSOFT Software Engineering Notes, Vol. 45, No. 4, PDF
• Human-Like Summaries from Heterogeneous and Time-Windowed Software Development Artefacts, Mahfouth Alghamdi, Christoph Treude, and Markus Wagner, PPSN 2020, arxiv.org, poster, video
• Optimising the Fit of Stack Overflow Code Snippets into Existing Code, Brittany Reid, Christoph Treude, and Markus Wagner, arxiv.org, ACM, Genetic Improvement Workshop GI@GECCO 2020
• An Annotated Dataset of Stack Overflow Post Edits, Sebastian Baltes and Markus Wagner, arxiv.org, ACM, dataset at Zenodo, YouTube video demonstrating access to the dataset, Genetic Improvement Workshop GI@GECCO 2020
• Genetic Improvement of Software Efficiency: The Curse of Fitness Estimation, Mahmoud A. Bokhari, Brad Alexander, and Markus Wagner, ACM, Genetic Improvement Workshop GI@GECCO 2020
• Towards Rigorous Validation of Energy Optimisation Experiments, Mahmoud A. Bokhari, Brad Alexander, and Markus Wagner, arxiv.org, GECCO 2020
• GECCO 2020 Tutorial "Genetic improvement: Taking real-world source code and improving it using genetic programming", by Sæmundur Ó. Haraldsson, John R. Woodward, and Markus Wagner
• Better Software Analytics via "DUO": Data Mining Algorithms Using/Used-by Optimizers, Amritanshu Agrawal, Tim Menzies, Leandro L. Minku, Markus Wagner, and Zhe Yu arxiv, | Springer
• CEC 2019 Tutorial "Genetic Improvement: Taking Real-World Source Code and Improving it Using Genetic Programming", by Sæmundur Ó. Haraldsson, John R. Woodward, Brad(ley) Alexander, Markus Wagner slides | GIN in teaching (check Assignment 3)
• A Survey of Genetic Improvement Search Spaces, Justyna Petke, Brad Alexander, Earl T. Barr, Alexander E.I. Brownlee, Markus Wagner, and David R. White PDF, GI@GECCO 2019
• Toward Human-Like Summaries Generated from Heterogeneous Software Artefacts, Mahfouth Alghamdi, Christoph Treude, and Markus Wagner PDF, GI@GECCO 2019
• The Quest for Non-Functional Property Optimisation in Heterogeneous and Fragmented Ecosystems: a Distributed Approach, Mahmoud A. Bokhari, Markus Wagner, and Brad Alexander PDF, GI@GECCO 2019
• Gin: Genetic Improvement Research Made Easy, Alexander E.I. Brownlee, Justyna Petke, Brad Alexander, Earl T. Barr, Markus Wagner, and David R. White PDF, GECCO 2019, Software: Version 1 (before this paper), Version 2 (this paper)
• A characterisation of S-box fitness landscapes in cryptography, Domagoj Jakobovic, Stjepan Picek, Marcella S. R. Martins, and Markus Wagner PDF, GECCO 2019
• Mind the gap -- a distributed framework for enabling energy optimisation on modern smart-phones in the presence of noise, drift, and statistical insignificance, Mahmoud Bokhari, Lujung Weng, Markus Wagner, Bradley Alexander, CEC 2019
• Predicting Good Configurations for GitHub and Stack Overflow Topic Models, Christoph Treude and Markus Wagner PDF, MSR 2019
• In-vivo and offline optimisation of energy use in the presence of small energy signals - A case study on a popular Android library, Mahmoud A. Bokhari, Brad Alexander, and Markus Wagner, PDF, MOBIQUITOUS 2018
• Deep Parameter Optimisation on Android Smartphones for Energy Minimisation - A Tale of Woe and a Proof-of-Concept, Mahmoud A. Bokhari, Bobby R. Bruce, Brad Alexander, and Markus Wagner, PDF, GI@GECCO 2017
• Validation of Internal Meters of Mobile Android Devices, Mahmoud A. Bokhari, Yuanzhong Xia, Bo Zhou, Brad Alexander, and Markus Wagner arXiv
• Optimising Energy Consumption Heuristically on Android Mobile Phones, Mahmoud Bokhari and Markus Wagner, GI@GECCO 2016
• Speeding up the proof strategy in formal software verification, Markus Wagner, GI@GECCO 2016
• An Improved Beam-Search for Testing Formal Verification Systems, Mahmoud Bokhari, Thorsten Bormer, and Markus Wagner, SSBSE 2015 (software)
• Boosting Search for Recursive Functions using Partial Call-Trees, Brad Alexander and Brad Zacher, PPSN 2014
• Maximising Axiomatization Coverage and Minimizing Regression Testing Time, Markus Wagner, WCCI/CEC 2014
• Heuristically Creating Test Cases for Program Verification Systems, Bernhard Beckert, Thorsten Bormer, and Markus Wagner, MIC 2013
• A Metric for Testing Program Verification Systems, Bernhard Beckert, Markus Wagner, and Thorsten Bormer, TAP 2013
• Evolving Patches for Software Repair, Thomas Ackling, Brad Alexander and Ian Grunert, GECCO 2011
• Constructing an Optimisation Phase Using Grammatical Evolution, Brad Alexander and Michael Gratton, 2009 IEEE Congress on Evolutionary Computation, CEC 2009