Modeling Control Flow of Real-Time Tasks for Static Analysis

• Typ der Arbeit: Masterarbeit
• Status der Arbeit: laufend
• Projekte: AHA
• Betreuer: Andreas Kässens, Daniel Lohmann

[Generated with AI]

Context

Within the AHA project, we research specialized embedded systems with real-time requirements. Using the Automatic Real-time Analyzer (ARA), we perform static analysis to find interactions between different tasks, resulting in a State Transition Graph (STG)¹.

With the latest extension, we can analyze interactions between isolated virtual machines (domains) on a static partitioning hypervisor (SPH). This allows for timing analysis of cross-domain interactions between multiple RTOSes, accelerators, coprocessors or dynamic, general-purpose OSes like Linux.

Problem

ARA uses Control Flow Graphs (CFGs) for domain-local analysis and synchronizes these graphs at interactions between domains. However, we may not always have the complete source code of the application to generate CFGs (black-box domain), or the control flow may be too complex for detailed static analysis. For such domains, we must model the control flow from an abstract description and feed it into the ARA analysis. Effectively, we need a separation of the ARA preprocessing frontend (application code compiled to LLVM, CFG, ValueAnalysis, etc.) from the middleend (control-flow-based static analysis). Then, modelled application control flows can be used in parallel to the current frontend.

Goal

In this thesis, the student shall examine existing high-level real-time task models and how they can be modeled as CFGs. In particular, established real-time task models like sporadic and periodic tasks, arrival curves, or self-suspending tasks are of interest.

For example, periodic tasks are modeled by (at least) two parameters: the WCET bound $C$ and the period $T$. Additionally, we assume a given set of interactions $I$ characterized by their relative point in time (BCET/WCET), interaction type, and parameters $(t_i, T_i, P_i)$. This task model could be translated into a very simple while-loop, however this could affect the timing properties.

As a result, a given set of task models can be automatically generated into an ARA-compatible CFG format, providing an alternative to the current LLVM-based preprocessing frontend.

The following steps are required for a bachelor's thesis:

• Understand ARAs preprocessing steps and data structures
• Research real-time task models
• Parse parametrized ($C, T$) task descriptions (e.g. yaml) with Python
• Generate artificial CFGs in ARA, matching the task model
• Include relevant interactions $I$ into the CFG (system calls, hypercalls, interrupts)

At this point, the analysis pipeline can generate output (dot-graphs of CFGs) for a set of task models. To evaluate the implementation, the student shall qualitatively examine and compare resulting CFGs. There can be different variants for each model! Additionally, real-world task models (automotive benchmarks) can be used to evaluate the scalability.

For a complete integration with the ARA middleend, the additional requirements for a master's thesis are:

• Add timing information $t_i$ to the CFG
• Extend the value analysis with the provided parameters $P_i$
• End-to-end static analysis including interactions between multiple domains.

Disclaimer: The ARA framework is quite complex with a steep learning curve. Familiarity with compilation steps in LLVM, and Python can be helpful for working with this project.

Topics: Static Analysis, Real-Time, C++, Python, LLVM

References

RTAS Conference A
MultiSSE: Static Syscall Elision and Specialization for Event-Triggered Multi-Core RTOS

Gerion Entrup, Björn Fiedler, Daniel LohmannProceedings of the 29th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'23)2023.
PDF Details Slides 10.1109/RTAS58335.2023.00028 [BibTex]

BibTex Entry

@inproceedings{entrup:23:rtas,
author = {Gerion Entrup and Björn Fiedler and Daniel Lohmann},
booktitle = {Proceedings of the 29th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'23)},
doi = {10.1109/RTAS58335.2023.00028},
entrysubtype = {Conference},
month = {May},
title = {{MultiSSE}: Static Syscall Elision and Specialization for Event-Triggered Multi-Core {RTOS}},
year = {2023},
}

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)