UCL rides the CREST of a wave with ‘Darwinian’ testing methods

29 October 2012

Evolutionary ideas have proved revolutionary at UCL’s Centre for Research on Evolution, Search and Testing (CREST), where its director, Mark Harman, has been working with nature-based algorithms for testing software for more than a decade.

Darwin

His successful collaboration with Daimler Chrysler and now Berner and Mattner on developing new methods for testing safety systems in cars has changed the way software engineering is understood and practised. He is now, with the help of UCL Enterprise, hoping to win EPSRC funding which will see search-based software testing change the way people develop software and improve the competitiveness of all British companies, from multinationals to start-ups.

To most people, the collection of ideas that make up Darwin’s theory of evolution is more commonly applied to living organisms. But scientists – starting with father of modern computing Alan Turing, more than 50 years ago – have long been applying the principles of natural selection or ‘survival of the fittest’ in fields as diverse as art, economics, marketing, music, physics and politics.

Until a decade ago, though, nature-based algorithms had not been widely used in software testing – an area to which they are almost, well, born. Professor Mark Harman, director of UCL’s Centre for Research on Evolution, Search and Testing (CREST) explains: “If you think about testing the ‘fitness function’ – the design solution that gives the best result for future survival – in humans, you have to wait at least nine months and then maybe a lot longer to see how you’ve done. It’s taken us four billion years to get to where we are. In software testing you can test thousands of ‘breeding’ scenarios in a matter of seconds.”

Mark first brought scientists working on genetic algorithms and software engineers together in a small EPSRC-funded project; a breakthrough came when Daimler Chrysler came on board. Mark says: “The testing requirements for a car’s safety features such as braking systems and air bag control are obviously very stringent. Using Darwin’s theory of evolution, we can breed exceptionally demanding test cases, ensuring that the car is thoroughly put through its paces in the design labs before being released onto the road.”

Mark still works with Dr. Joachim Wegener, now of Berner and Mattner in Berlin, to perfect these testing techniques, and expects to see them widely used throughout the automotive industry in five to ten years’ time.

The collaboration has led to a sea-change in the way in which software engineering is understood and practised. “Existing techniques, largely based on human intervention, could not cope with the complexity of the software systems we wanted to build. Our focus was on guiding the automated search, rather than performing it,” says Mark.

He and his team were awarded another EPSRC grant – at £2.7million, then the largest ever Computer Science grant in responsive mode, where scientists put their own ideas up for consideration – to research and address key issues in software engineering, including scalability, robustness, reliability and stability. In 2010, UCL bought CREST in its entirety from another London university.

Professor Anthony Finkelstein, Dean of Engineering at UCL, says: “Since 1999, the university has been a world leader in research in software engineering. The acquisition of CREST, with its track record of competitive grant funding and knowledge transfer, makes UCL a leader also in search-based software engineering. More than 800 authors have published on the topic, and world-leading companies such as Microsoft and Google are experimenting with algorithms in their labs.”

Mark is now working on a new grant application worth £6.4 million from the EPSRC, and he has enlisted the help of UCL Enterprise in making a business case for such a substantial sum of money. He says: “UCL Enterprise has provided intellectual leadership across many aspects of the process.” That includes securing a commitment from UCL to match EPSRC funding with support for two lecturers and 10 PhD students (EPSRC no longer funds project studentships). Andrew Clark, Director of Research Planning at UCL says: “If the technology fulfills its promise we want to be in a position to educate people at all levels to apply it.”

In addition, UCL Business will pay for a Business Development Manager in the second year of the six-year project, who will manage relationships with 50 or 60 SMEs as opposed to two or three large companies. Mark says this is vital if the new software testing is to move “beyond the Motorolas and Ericssons” and change the way people develop software. “We want to improve the competitiveness of all British companies, from multinationals to start-ups, by helping them to develop cutting-edge testing solutions. We want to do for the software industry what Henry Ford once did for cars.”