Failure-dependent timing analysis - a new methodology for probabilistic worst-case execution time analysis

Embedded real-time systems are growing in complexity, which goes far beyond simplistic closed-loop functionality. Current approaches of worst-case execution time (WCET) analysis are used to verify the deadlines of such systems, especially when they are safety-critical. These approaches calculate or measure WCET as a single value that is expected to be an upper bound for a system's execution time. Overestimations are taken into account to make this upper bound a safe bound, but modern processor architectures with caches, multi-threading, and instruction pipelines often expand those overestimations for safe upper bounds into unrealistic areas. Some approaches try to overcome this problem by calculating multiple upper bounds and argue that each single upper bound will hold for a certain probability (probabilistic worst-case execution time). Even though some of them tackle the problem of obtaining reliable probabilistic values for such upper bounds, more effort is required. Therefore, a method is presented in this thesis that combines probabilities of safety analysis models and elements of system development models in order to calculate a probabilistic worst-case execution time. Since safety analysis models are used to document the reliability or safety of safety-critical systems, they provide reliable probabilistic values. These probabilities are used here to calculate a probabilistic worst-case execution time that provides safe and reliable probabilities. The approach can be applied to systems that use mechanisms belonging to the area of fault tolerance, since such mechanisms are usually quantified in safety analyses to certify the system as being highly reliable or safe. A tool implementing this approach is also presented in this thesis. The tool provides reliable safe upper bounds by performing a static WCET analysis and overcomes the frequently encountered problem of dependence structures by using a fault injection approach. The tool can handle popular Simulink models and combines them with fault tree elements, a safety analysis model that is widely accepted by authorities, to derive probabilistic worst-case execution times. These execution times with probabilities provide information such as the probability of the system terminating within a given deadline.

Die Arbeit bedient sich der Quantifizierung von Sicherheitsanalysen, um genauere Schranken für die maximale Ausführungszeit eingebetteter Systeme ermitteln zu können. Dabei stehen vor allem sicherheitskritische eingebettete Systeme im Vordergrund. Bei Systemen dieser Art kommen oft Fehlertoleranzmechanismen zu Einsatz, die mittels herkömmlicher Verfahren typischerweise sehr konservativ behandelt werden nur schwer zu analysieren sind.