Using Learning to Support the Development of Embedded Systems
The EPSRC funded project Using Learning to Support the Development of Embedded Systems (headed by Iain Bate) seeks to investigate the application of techniques from artificial intelligence and software testing to build models upon which the analysis of real-time systems, specifically the Worst Case Execution Times (WCET) of tasks can be based.
Approaches developed for WCET analysis must give conservative bounds but the degree of pessimism is typically too great for many purposes. All such analysis tools must ultimately rely on information about hardware instruction execution. However, modern processors are becoming very complex and the information needed to calculate WCETs is typically unavailable. Current analysis work seems to lag well behind the real world. Several researchers have identified measurement based approaches as a promising candidate to cope with modern-day engineering demands. Measurements can be taken freely, however the weakness is ensuring the results are safe.
Rather than directly inferring bounds on WCETs from execution trace timings, this project looks at how to use the measurements to infer a model of the underlying system that can form an input into further WCET calculations. Since the problem is in essence a learning problem, we investigate how well leading edge machine learning approaches can be adopted or adapted to this end. We believe that it may be possible to choose tests whose execution trace measurements contain sufficient information to allow abstract system models needed for WCET analysis to be automatically inferred.
So far, my work has specifically focussed on learning the number of times a nested loop executes as a function of its parameters. In general this is an undecidable problem, therefore we restrict ourselves to considering the Presburger subset. Using Inductive Logic Programming (ILP), we have created a tool provably capable of learning the number of loop iterations from a defined number of program traces.