Visualization of parallel control flows in RTOS analysis

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

Ai-Enhanced "fancy" version of a control flow graph

Context

Today's computing systems autonomously control vehicles, satellites, and critical infrastructure. To protect humans from danger, embedded safety-critical systems require a complex and extensive verification and analysis process before they are ready for production. In particular, for real-time operating systems (RTOS), where hard timing deadlines are mandatory for safe operation, programmers must know how their application and their operating system (OS) behave.

For this, we developed the Automatic Real-time Analyzer (ARA), a whole system static analysis framework, which is able to model applications and their interactions with the OS. It consists of different analysis steps, with the main goal of finding every OS-relevant system state using the System State Enumeration (SSE). ARA supports different RTOS using an internal OS-agnostic model, and it is also able to analyse parallel control flows and their timing behaviour in a multicore (MultiSSE) or virtualized system (HyperSSE).

Problem

Having multiple parallel control flows provides not only a challenge for the analysis, but is also exponentially more difficult to visualize. A linear control flow is drawn as a directed graph, where each node contains a section of source code or cpu instructions, which have one or more possible follow-up states. To make a graph understandable and readable for humans, we want few crossing edges, and logically related nodes should be drawn closely together.

Parallel flows mostly follow their isolated local control flow, which is drawn as one region in the graph. But sometimes they interact with another control flow, for example, when they interact with another system using a hypercall. This leads to a synchronisation point between the two flows, which requires connections to both local flows. Currently, ARA's drawing system splits local control flows up to display such connections in a 2-dimensional plane, but this makes it difficult to follow a given control flow.

Having a great analysis is only useful when its result can be quickly understood and acted upon. This is especially important in ongoing research, because much time is spent experimenting and debugging new features. With ARA supporting multiple interaction levels, it is more important to be able to have different views on the underlying data.

Goal

The goal of this thesis is to extend ARA's current output system. The main workflow of ARA is compiling an application into LLVM IR code, processing it using graph-tool data structures, outputting graphs in the dot format, and finally rendering them using graphviz. The first task is to overhaul the existing tooltip annotations in the graph, aggregating information from different analysis steps. For better visibility, a system shall be developed to filter out certain fields and to focus on a specific control flow of the graph. This can be done by editing the textual representation of dot, for example, by using a Python script.

As a second goal, graph-tool provides its own interactive view API, which renders its data structures without converting them into dot. Using the previously developed tooltips, a live debugging interface shall be developed, which provides access to different views of graph-tool graphs. This API allows viewing graphs during the analysis, but can also be exported into various formats. In the evaluation, both systems can be compared.

If there is time at the end, another parsing step is to add the LLVM IR code to the graph's tooltips. Because the analysis abstracts away the IR Code early in its analysis, the resulting graphs currently do not include the source code, but only derived basic blocks. The task is to reverse this mapping and include the source code in the resulting graphs.

Topics: static-analysis, graph-drawing, RTOS, Python, LLVM, C++

References

Papers

OSPERT Workshop B RTOS-Independent Interaction Analysis in ARA

Gerion Entrup, Jan Neugebauer, Daniel LohmannProceedings of the 16th Annual Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT '22)2022.
PDF Slides [BibTex]

RTSJ Journal Applied static analysis and specialization of cross-core syscalls for multi-core AUTOSAR OS

Gerion Entrup, Andreas Kässens, Björn Fiedler, Daniel LohmannReal-Time SystemsSpringer2024.
PDF Slides 10.1007/s11241-024-09429-1 [BibTex]

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)