TypicalCPA

Formal performance analysis of embedded systems has shown great progress in recent years, mainly due to the introduction of compositional methods which can easily be applied to heterogeneous systems. Meanwhile, formal performance analysis is regularly used in the design of networks and systems at many automotive and avionics companies.

High assurance of formal performance analysis comes at the price of limited design efficiency because it only supports a worst case design style. Therefore, for non-critical system functions, worst case analysis is often complemented by less rigorous methods, such as random tests or simulation. Such analysis usually provides approximations of unknown accuracy rather than solid guarantees. The effective use of stochastic models and methods, on the other hand, requires system properties that are usually not met by highly dynamic embedded systems. In consequence, an approach is needed supporting higher design efficiency than worst case analysis but guarantees a maximum deviation from the worst case.

In preliminary work, we developed an approach, called Typical Worst Case Analysis, that is based on the theory of Weakly Hard Real-time Systems by Bernat and Burns. In such systems, there is an upper bound of m deadline misses out of k consecutive tasks or messages. Such guarantees, called (m,k) firm deadlines, are a good fit for important applications, such as feedback control, which are often robust against occasional loss of data. They are also suitable for modeling and analyzing the behavior of hardware/software platforms with temporary overload or occasional message loss.

Both are topics of the new research area of cyber-physical systems. Our preliminary work extended the original theory by non-periodic activations, mapped the problem to an optimization problem over deadlines, and applied it to the analysis of practical automotive buses were far higher design efficiency compared to a worst case design could be demonstrated.

At the state of research, Typical Worst Case Analysis is non-compositional meaning the current analysis for single components cannot be scaled to the analysis of complete systems. To remove this limitation, fundamental research is necessary, into event models, into optimization based end-to-end analysis and, eventually, into the underlying fixed point problem and its solution which must be reinvestigated because the underlying assumptions are different. The proposed project shall provide these contributions. The work program gradually extends the existing compositional worst case analysis methods by typical worst case models and analyses. The project ends with an extensive evaluation. An Ethernet-Backbone shall be used as a comprehensive example, as many data and methods are available for comparison.

Project Research Staff: Leonie Ahrendts

Cooperation Partner: Dr. Sophie Quinton

Funding:  Deutsche Forschungsgemeinschaft (DFG)