Timing Analysis of Dynamically Adaptable Component-based Systems

Motivation

Software operating in domains such as process management systems, wireless sensor networks and spacecraft control systems are expected to continue uninterrupted operation over extended periods, without any manual supervision, maintenance or external intervention. However, unexpected events or changes in the operating environment over time, require the software to occasionally update itself to ensure correct operation over a prolonged interval. These updates to software behaviour may be achieved by a process known as dynamic software adaptation. Adapting software dynamically allows systems to respond to unexpected operational challenges, to update unwanted or unnecessary functionality, and to optimize their behaviour to fit the prevailing operating conditions. However, adaptations can also unintentionally alter the execution time of the software. In this way, the timeliness of the software may become uncertain, with timing delays, missed deadlines and functional errors being unwittingly introduced into an otherwise dependable codebase. Estimating the likely execution time of dynamically-adaptable software is critical to avoid functional interference caused by timing uncertainty. Unfortunately, predicting the execution time of dynamically-adaptable software cannot be accomplished using traditional timing analysis methods, without halting the system or restricting the set of adaptable software behaviours. Static timing analysis methods cannot re-evaluate timing estimates at runtime, since they require a lengthy offline analysis period. Conversely, measurement-based dynamic timing analysis methods cannot provide any timing estimates immediately following an adaptation, until a large number of observations have been recorded and evaluated.

Scientific Basis

To address these difficulties, we apply a selection of statistical methods at runtime to forecast the timing behaviour of dynamically-adaptable software. Using a dynamically-generated predictive model, forecasts are made about the likely execution time of the current configuration of the software, as well as allowing estimates to be generated describing the probabilistic timing impact of functional adaptations.

Since the underlying software can change unexpectedly during run-time, and the resulting configuration of the software may have been previously unforeseen, our dynamic timing analysis process must respond to any functional adaptations without relying on any a priori timing information, or pre-processing.

Results

Timing behaviour of a dynamically-adaptable software system can be accurately and precisely predicted at runtime using statistical methods. These predictions can be generated with limited prior warning and without halting the system to perform the analysis, restricting the scope of adaptations or relying on extensive offline generated measurements.

By applying a diverse collection of statistical models at different times during run-time, an estimate can be produced, with a variable level of associated confidence. Since our approach is a purely measurement-based timing analysis method, the accuracy and precision of our results are directly correlated with the amount of timing data available. However, even in cases where there is limited timing data, a timing estimate may still be produced.

Even between different configurations of a dynamically-adaptable system, with differing timing behaviours (see above), our approach can predict the likely timeliness of the software with a high level of accuracy, even when executing within resource-constrained embedded devices. By combining a low memory footprint, with a variable data cache, the timing analysis process can be configured to run within both small-scale and large-scale systems, as well as being tailored to provide an overall expected minimum level of accuracy and precision.

The histogram (right) illustrates the recorded accuracy of 32,000 timing estimates, generated at run-time within a live embedded system. With an expected accuracy of 95% for average-case estimates, and 99% for worst-case timing estimates, the timing analysis approach achieves its target within both stable as well as more highly-variable execution-time conditions. The timing estimates produced at run-time show that the accuracy and precision are only slightly below what would be achieved using a well-established static timing analysis method executed offline under ideal circumstances.

Timing predictions for dynamically adaptable software can also be used as feedback into the adaptation process itself, to select the most appropriate configuration of the software for the prevailing operating conditions. For example, a software configuration showing a poor overall timeliness may be replaced with a more timely alternative.

Publications

Shane Brennan and Serena Fritsch and Yu Liu and Ashley Sterritt and Jorge Fox and Éamonn Linehan and Cormac Driver and René Meier and Vinny Cahill and William Harrison and Siobhán Clarke,
A Framework for Flexible and Dependable Service-Oriented Embedded Systems
7th Book on Architecting Dependable System (ADS 7), pp. 123--145, Springer-Verlag, 2010, 6420, Lecture Notes in Computer Science, Berlin, Germany, nov, ISBN 978-3-642-172,

Brennan, Shane and Cahill, Vinny and Clarke, Siobhan,
Applying non-constant volatility analysis methods to software timeliness
In Proceedings of the 12th Euromicro Conference on Real-Time Systems, Work-in-progress Session, 2009,