Revolutionising the process of software development

Suppose you wanted to have a new feature in your program, for example, you might want your chat client to provide support for multiple languages. There is already an abundance of language translators freely available online. Thus all that’s left to do is to pick one and adopt it for the chat client at hand. Currently such a task lies upon the shoulders of expert human software developers. As one might imagine, for the most popular pieces of software, like Facebook, there might be hunderds of request for new features coming in everyday. Programmers are then left to do the frequently daunting work of transplanting existing code implementing given functionality from one program to another. What if we could automate this process?

pidgin

The process of software transplantation has a nice analogy with human organ transplants – you extract an organ (required functionality) from the donor (program) and insert it into the host (program). The key difference is that human organ transplantaion is very costly, whilst software errors in the development process happen on a daily basis. Furthermore, there’s nothing stopping programmers from trying to transplant a feature hundreds if not thousands of times. However, this would keep them away from doing more creative tasks.

We have thus applied a technique for automated software transplantation called genetic improvement and obtained award-winning results. GI was used to transplant a linguistic translation feature into the Pidgin instant messaging system that simultaneously translates the user’s English language instant messages into Portuguese and Korean [1]. We have also used it to automatically specialise software for a concrete application [2] as well as transplant a video encoding feature into the popular VLC media player [3]. This work has also been covered by WIRED.

We envision a future where expert software developers can be relieved of the task of transplanting existing code, leaving them more time to develop new and exciting software.

GetFileAttachment

[1] Mark Harman,W B Langdon and Yue Jia. “Babel Pidgin: SBSE can grow and graft entirely new functionality into a real world system”. Symposium on Search-Based Software Engineering (SSBSE) 2014.

[2] Justyna Petke, Mark Harman, William B. Langdon and Westley Weimer. “Using Genetic Improvement & Code Transplants to Specialise a C++ Program to a Problem Class”. European Conference on Genetic Programming (EuroGP) 2014.

[3] Earl T. Barr, Mark Harman, Yue Jia, Alexandru Marginean and Justyna Petke. “Automated Software Transplantation”. International Symposium on Software Testing and Analysis (ISSTA) 2015.

DAASE SBSE Workshop – Day 2 – live blog

10am One minutes silence held at the beginning of the workshop for our beloved colleague Professor David Notkin who died yesterday. Our thoughts are with his family and friends at this very sad time.

Our first speaker this morning is Juergen Branke from Warwick Business School “Optimization in dynamic environments”

20130423-101939.jpg

Evolutionary algorithms have grown into a mature field of research in optimization and have proven to be effective and robust problem solvers for a broad range of static real world optimization problems. Yet, since they are based on the principles of natural evolution and since natural evolution is a dynamic process in a changing environment they are also well suited to dynamic optimization problems.

With appropriate adjustments evolutionary computation is able to continuously adapt and is promising for applications where very few function evaluations are possible.

Next is Robert Feldt from Chalmers University of Technology, Sweden with ” Interactive and Adaptive Automated Testing Environments”

15 years ago Robert wanted to automatically generate program code, He failed but learnt a lot from that. He developed an IDE where you could automatically generate test cases.

Fitness guidance – f-Equalizer – being developed which can compare test case similarity.

20130423-105226.jpg

It is implemented using a Javascript library called D3, it has a Ruby backend.

– break –

Next is Michael Orlov from Department of Computer Science, Ben-Gurion University, Israel

Evolving unrestricted Java software with FINCH

FINCH is a methodology for evolving Java bytecode enabling the evolution of extant unrestricted Java programs or programs.

Michael wanted to evolve some Java source code and improve some existing Java software.

The team decided to use Java – JVM bytecode rather than parse trees.

20130423-114734.jpg

They used bytecode because it is less fragile than source code but must be correct in order to run correctly so genetic operators are still delicate. Good genetic operators are needed to produce correct offspring.

20130423-122926.jpg

Java Wilderness, Artificial Ant

They found that completely unrestricted Java programs can be evolved via bytecode and extant Java programs can be improved.

– lunch –

First up after lunch is David White from Computing Sciences, University of Glasgow, UK talking about “The Programming Game: an alternative to GP for Expression Search”

David asks how well do we understand GP genetic programming search and talks about an alternative program search method. Monte Carlo tree search achieves some amazing results in the game of Go. It works by looking at game trees.

20130423-141235.jpg

Advantages of Monte Carlo tree search are concise solutions, the game tree is human readable and parallelisation.

Future work includes adapting Monte Carlo tree search for program search.

Our last speaker is Justyna Petke from CREST Centre, SSE Group, Department of Computer Science, UCL. She will be speaking about “Genetic improvement of software: a case study”

Genetic improvement programming aims to improve code. Code is changed by reusing lines of the original code and adding, deleting, mutation, crossover etc.

20130423-145049.jpg

Findings of the study were that genetic improvement programming automatically improves system behaviour in selected cases.

-Workshop wrap up –

Professor Mark Harman, DAASE project PI, thanks our speakers and everyone for coming.

20130423-151203.jpg

Our workshop is now finished. Many thanks to all of our speakers and session chairs and of course our audience. See you at #COW27 😃

Live Blog – Dynamic Adaptive Automated Search Based Software Engineering (joint DAASE/COW workshop)

Please refresh page for updates – Live blog commencing 10.30am on 22nd April 2013

The DAASE COW will be running all day 22nd and 23rd April at UCL

Program here: http://crest.cs.ucl.ac.uk/cow/26/

Professor Mark Harman, DAASE project PI introduces the day by welcoming everyone to UCL, to London and to #CREST26.

Prof Mark Harman welcomes everyone

Prof Mark Harman welcomes everyone

Professor Harman asks everyone at the workshop to introduce themselves.

20130422-110315.jpg

11:15 Keynote: Living with change and uncertainty, and the quest for incrementality. Prof Carlo Ghezzi, Dipartimento di Elettronica e Informazione, Politecnico di Milano, Italy

Prof Ghezzi begins by asking everyone to interrupt if they have any questions.

Basic findings from his research of the last 4 years. Software is everywhere, there are cyber-physical systems, new behaviours emerge dynamically and systems need to run continuously.

The challenge: continuous change and uncertainty in the requirements, the infrastructure, the platform. At the same time our systems need to be dependable.

Change and dependability don’t go together very well.

Slide: The questions and the answers

The traditional separation between development time and runtime must be broken.

20130422-111633.jpg

You need to convince yourself that your specification and your assumptions entail the specification of the requirements.

20130422-112151.jpg

Hidden assumptions need to be made explicit. Assumptions are heavily affected by change and uncertainty. Changes lead to software evolution, adaptation is a special case of evolution. Changes matter because they may affect dependability.

Professor Carlo Ghezzi on Google Scholar

Continuous verification needs to be performed to detect the need for evolution.

Q: is it possible to identify a subset of priorities at runtime?

A: verification needs to be made incremental. It is a challenge.

We have focused mainly on non-functional requirements quantitatively stated in probabilistic terms. These things all change out of your control and the users profile is also subject to change.

Prof Ghezzi’s team’s approach, there are several models with different viewpoints, focusing on non-functional properties and Markov models.

The DMTC Model

20130422-115606.jpg

The problem: is it affordable everytime you have a change to run the model checker from scratch? Can changes be handled incrementally? This requires revisiting verification procedures.

Running the model checker can be impractical. Verification needs to have an agile approach, it must be incremental.

Incrementality by parameterization: requires anticipation of changing parameters, you can do a partial evaluation of the model with transitions as variables. Things that may change are represented as variables. Values are partly numeric and partly symbolic represented in matrices.

Prof Ghezzi states we must move verification to runtime, thru incrementality formal specification/verification can be reconciled with agility.

[SB This reminds me of our 2009 paper “Formal vs Agile: survival of the fittest?”]

Summary: self adaptation requires continued reasoning and verification at runtime because of the detected changes. Verification has to be the driver, if you want it to be safe, the only way to be dependable is to use a model view. Mainstream verification approaches must be adapted.

Prof Carlo Ghezzi can be contacted via Twitter: @carloghezzi

Next is Gabriela Ochoa from Stirling University talking about “Hyper-heuristics and cross-domain optimisation”

20130422-124833.jpg

There are various autonomous/adaptive search approaches.

Hyper heuristics work well on different problems and are bespoke. They comprise heuristic selection followed by heuristic generation.

20130422-125608.jpg

Gabriela describes several case studies in hyper-heuristics. The university course timetabling case study which looked at minimising conflicts. Many operators were available which could be selected on the fly. The five best operators were identified.

Gabriela has found that good algorithms are hybrid and dynamic, adaptive approaches can beat state of the art algorithms.

LUNCH

Prof Marc Schonauer from INRIA speaks next about “Adaptive operator selection with rank based multi armed bandits”

Why do we want to set parameters online? Because there is no single best operator.

20130422-141331.jpg

Operator selection factors to consider: the exploration vs exploitation balance, dynamical setting, using a change detection test eg Page-Hinkley which enforces the efficient detection of changes in time series.

The Area Under the Curve AUC in machine learning can be used to evaluate binary classifiers with performance a percentage of missclassification. This is equivalent to the MannWhitneyWilcoxon test, where two sequences have the same order.

Rank based AUC can be used with Multi Armed Bandits MAB.

20130422-143134.jpg

The goals of the experiments, carried out were: performance, and robustness/generality.

The results show that MAB outperforms other methods.

Sasa Misailovic talks next about “Accuracy aware program transformations“.

Current trends are big data sets and energy consciousness.

This gives an opportunity to automatically transform snd adapt programs. This can also help with energy related problems like battery life etc.

20130422-145010.jpg

To optimize transformations a code perforation framework has been developed to enable automatic discovery of profitable trade-offs between the time required to perform a computation and the accuracy of the final result. The process has three main stages: find candidates, analyse effects, navigate tradeoff space.

Results of a code perforation experiment showed that performance improved by a factor of over two for a range of applications, but there is no guarantee of accuracy or safety with changing the result that the application produces by less than 10%.

TEA BREAK [Yay! This is thirsty work]

UCL CREST’s Yuanyuan Zhang is next presenting “Hyper-heuristic based strategic release planning”

Difficulties with release planning: complex constraints, incompletexinformation, multiple objectives and large decision space.

20130422-155424.jpg

Strategic Release Planning: using hyper heuristic algorithms in selecting and assigning requirements.

A model has been developed which has been used with five different data sets, including two from Motorola and Ericsson.

20130422-160840.jpg

The data sets all have multiple stakeholders with multiple needs and requirements. Yuanyuan presents a detailed breakdown of the results.

Another experiment compares the performance of hyper heuristic algorithms.

Leandro Minku from CERCIA, University of Birmingham presents on “Ensemble learning for software effort estimation: from static to dynamic analysis”

followed by

Simon Poulding from Iniversity of York on “Searching for strategies that verify MDE Toolchains”

DINNER and see you all tomorrow….