Static Analysis of Every Control Flow Sequence

• Typ der Arbeit: Masterarbeit
• Status der Arbeit: reserviert
• Projekte: AHA
• Betreuer: Mareike Burg, Daniel Lohmann

Prototype of graphical representation: each vertical line is one potential control flow sequence of the system, with each task having one of its possible execution times

Context

Real-time systems operate under timing constraints and are required to complete calculations in their Worst Case Execution Time (WCET). While developers try to use deterministic hardware and software, it is usually necessary to overestimate the execution time and add slack to the system. This guarantees that every run of the system meets the deadline, with its actual runtime being somewhere between its Best and Worst Case Execution Time [BCET, WCET].

We developed the Automatic Real-time Analyzer (ARA)¹ to statically analyze real-time systems and predict their BCETs and WCETs across different tasks and operating system functions. Compared to dynamic analysis, which executes and measures one run, static analysis formally checks all system states.

Problem

On their way to maximizing performance, modern CPUs and memory systems grew increasingly complex and indeterministic. This makes it more difficult for static analysis tools to predict their behavior and requires pessimistic overapproximations to give worst-case guarantees.

At the same time, the rise of multicore and virtualized embedded systems created new communication patterns and cause-effect task chains that span across more components. In order to analyze when events arrive at different steps on their way, it is important to know what their worst and best case arrival times are. Different side effects might occur depending on when the event arrives.

Ideally, indeterminism is minimized early in system development, requiring software tools that identify critical timepoints and automatically propose solutions. Dynamic tracing tools ^{2 3} exist to extract details about one given run of the system, but they cannot try out every possible control flow sequence and therefore lack an overview of the system.

Goal

The goal of this thesis is to address this gap and provide a toolchain to analyze and quantify the indeterminism of real-time systems. By using the results of ARA's static analysis, it should find every possible control flow sequence of the system and make this data accessible. Because the number of control flows grows exponentially for less deterministic systems, an algorithm needs to be developed that groups similar control flows and abstracts irrelevant details. This requires a metric to find the similarity between control flows and to decide on what to abstract.

Further, it shall develop a framework to measure the amount of indeterminism between different systems. This metric allows for grading different implementations and could be developed into a simulation environment, where existing data from the analysis is combined with potential modifications. Finally, an algorithm shall be developed that automatically finds the best modifications to minimize indeterminism.

Steps:

1. Create datamodel and visualization for given data in language of choice
2. Design, discuss, and test different merging algorithms to prevent state count explosion
3. Implement support for more complex control flows like multicore
4. Develop a system-wide metric for indeterminism and use it to grade and compare systems
5. Use the metric to design an algorithm to optimize systems towards determinism
6. [Bonus] Extend the visualization with interactivity
7. [Bonus] Extend the analysis to compare different configurations and scheduling algorithms

Topics: Real-Time System, Static Analysis, Visualization, Indeterminism, Algorithms

References

ECRTS Conference B Best Student Paper Award
HyperSSE: Cross-Domain Static Analysis of Partitioned Real-Time Hypervisor Systems

Andreas Kässens, Mareike Burg, Daniel LohmannProceedings of the 38th Euromicro Conference on Real-Time Systems (ECRTS '26)2026Best Student Paper Award.
PDF Details Slides 10.4230/LIPIcs.ECRTS.2026.23 [BibTex]

BibTex Entry

@inproceedings{kaessens:26:ecrts,
author = {Andreas Kässens and Mareike Burg and Daniel Lohmann},
booktitle = {Proceedings of the 38th Euromicro Conference on Real-Time Systems (ECRTS '26)},
date = {2026-07-02},
doi = {10.4230/LIPIcs.ECRTS.2026.23},
entrysubtype = {Conference},
series = {ECRTS '26},
title = {{HyperSSE:} Cross-Domain Static Analysis of Partitioned Real-Time Hypervisor Systems},
year = {2026},
}

HyperSSE: Static Analysis of Real-Time Hypervisor Systems

Complex embedded computing systems shift to partitioning multicore hardware e.g. using the Xen hypervisor. The static analysis in ARA shall be extended to support analyzing basic synchronization mechanisms of such systems. [PDF]

---

 

Typ

Masterarbeit

---

 

Status

abgeschlossen

---

 

Supervisors

Andreas Kässens
Daniel Lohmann

---

 

Project

AHA

---

 

Bearbeiter

Mareike Burg (abgegeben: 26. Sep 2025)