SEBASE: Software Engineering by Automated Search

Project: Research project (funded)Research

Project Details


Current software engineering practice is a human-led search for solutions which meet needs and constraints under limited resources. Often there will be conflict, both between and within functional and non-functional criteria. Naturally, like other engineers, we search for a near optimal solution. As systems get bigger, more distributed, more dynamic and more critical, this labour-intensive search will hit fundamental limits. We will not be able to continue to develop, operate and maintain systems in the traditional way, without automating or partly automating the search for near optimal solutions. Automated search based solutions have a track record of success in other engineering disciplines, characterised by a large number of potential solutions, where there are many complex, competing and conflicting constraints and where construction of a perfect solution is either impossible or impractical. The SEMINAL network demonstrated that these techniques provide robust, cost-effective and high quality solutions for several problems in software engineering. Successes to date can be seen as strong pointers to search having great potential to serve as an overarching solution paradigm. The SEBASE project aims to provide a new approach to the way in which software engineering is understood and practised. It will move software engineering problems from human-based search to machine-based search. As a result, human effort will move up the abstraction chain, to focus on guiding the automated search, rather than performing it. This project will address key issues in software engineering, including scalability, robustness, reliability and stability. It will also study theoretical foundations of search algorithms and apply the insights gained to develop more effective and efficient search algorithms for large and complex software engineering problems. Such insights will have a major impact on the search algorithm community as well as the software engineering community.

Key findings

The principal findings from York's work are given below.

Metaheuristic search is an important and potentially very powerful technique for solving a variety of problems in software engineering:

a) it can be used to evolve programs with multiple success criteria, e.g. we can engineer tradeoffs between functional criteria and non-functional criteria. Low resource programs can be attained at the cost of functional 'correctness'. Search techniques can find improvements to programs, e.g. making a program more time or power efficient.

b) it can be used to discover configurations of real-time systems that meet timing performance criteria, are robust against failure, and which are resilient to requirements change. Thus, 'robust' configurations can be discovered to allow some degree of future proofing.

c) it can be used to identify higher-level strategies for solving software engineering tasks. For example, rather than discover test data for testing a system, we can discover programs ('startegies') which when executed generate test data. This finds particular application in stress testing, but is a more general concept. A strategy is a very succinct artifact.

d) it can be used to find counter-examples efficiently in higher level formal models (in our case those of Java Pathfinder.)

e) the techniques find wider application, e.g. to the evolution of quantum algorithms and intrusion detection algorithms.

f) it can be used to evolve useful documentation from program traces (using genetic programming rather than the fixed templates of, say, Daikon). Furthermore, mutation can be used to identify 'interesting' invariants.

Effective start/end date28/06/064/07/12


  • EPSRC: £784,417.00