HyperSSE: Cross-Domain Static Analysis of Partitioned Real-Time Hypervisor Systems

Guaranteeing response times requires the analysis of applications’ execution timing, possible interruptions, blocking and interactions, especially in worst-case scenarios. For example, the dotted path in Figure 1 includes interactions between two domains which must be taken into account for the WCRT analysis. While many industrial applications may use dynamic approaches and estimations, hard real-time systems require guaranteed WCRT which can only be provided by static analysis [28]. For complex, mixed-criticality platforms with multiple software stacks, there is currently no method that can capture domain-local and global interactions for timing analysis. Therefore, we introduce our approach to this problem: HyperSSE is a cross-domain static analysis method for SPHs, that can be used to derive safe timing guarantees in mixed-criticality systems. With complete knowledge of all tasks, interactions and interrupts in the critical path, we can automatically and correctly analyze all cross-domain interactions to enable tightening of WCRT bounds compared to compositional static analysis [12].

For modern multicore and heterogeneous MPSoC systems, such an analysis must assume increasingly pessimistic response times due to many possible – although rare – causes for slowdowns: external interruptions [54], microarchitectural and cache effects [37], shared resources, or unreliable communication partners. In particular, cross-domain interactions [44] can lead to unpredictable delays, which can increase the WCRT bounds in traditional approaches. Because of this, we explicitly analyze domain-local and cross-domain interactions instead of treating them as side effects of abstraction by operating systems and hypervisors.

To focus on the most important parts, the domains are prioritized: In the automotive industry, for example, mixed-criticality is formalized using Automotive Safety Integrity Levels. Functional decomposition enables the displacement of complex functions in lower ASILs, but the supervision of safety-critical functionality must be part of a safe component [23]. As shown in Figure 1, a safety-critical component with the highest level (ASIL D) may need to communicate with less critical ASIL B components to enable autonomous driving assistance systems [13]. In this example, the HyperSSE can capture all interactions between these two real-time domains in detail, and also include other general-purpose domains for further analysis. This composition of precise real-time analysis with general-purpose domains is an important feature of our approach, because it enables a detailed analysis of complex platforms where necessary, but does not ignore interactions with other domains.

Similar to automotive systems, the ARINC-653 avionics standard expects temporally and spatially isolated partitions that communicate via devices or shared memory to exchange mission-critical messages, but timing-critical partitions must not suffer from interference at runtime [18, 21]. In the remainder of this paper, we will use the term domains interchangeably with partitions or VMs, as used by the Xen hypervisor.

We present the first approach to whole-platform static analysis for hypervisor-based platforms. In particular, we claim the following contributions in this paper:

1. 1.

   With HyperSSE, we describe an automatic static control-flow–sensitive analysis of explicit interactions in embedded real-time systems with multiple hypervised domains.

2. 2.

   We incorporate general-purpose domains, accelerators, coprocessors, or other peripherals to analyze mixed-criticality systems, by modeling their internal control flow.

3. 3.

   We implement HyperSSE into an open-source static analysis framework to show the applicability using an automotive case study.

4. 4.

   The implementation can compose different methods for domain-local control flow analysis, such as detailed RTOS models, OS interpreters, and abstract task models.

First, we introduce our system model and requirements in Section 2. In Section 3, we demonstrate the potential application of HyperSSE in an automotive scenario. Motivated by this, Section 4 contains the background and approach of HyperSSE. In Section 5 and 6, we describe our implementation into the existing open-source¹¹1https://github.com/luhsra/parrot Automatic Real-Time System Analyzer (ARA) analysis framework developed by Entrup et al. [16] and evaluate it using various test cases and the automotive scenario as a case study. We discuss the results and their impact in Section 7 and categorize related work in Section 8.

To understand the HyperSSE approach, we briefly introduce the core concepts of domain-local static analysis. First, the application-local Control-Flow Graph (CFG) is preprocessed to reduce the complexity of cross-kernel control flow traversal. Atomic Basic Blocks [39] are used to subsume the computational control flow regions in the application logic and make interactions with the OS explicitly visible to the analysis. Compared to basic blocks used for compiler optimizations, those ABBs can subsume larger application code blocks if they do not contain any system calls. Each ABB represents either a single system call or a single-entry/single-exit sequence of other (computational) instructions, optionally annotated with WCET/BCET retrieved by a local timing analysis. As a result, the interprocedural CFG contains only computation ABBs and (system) call ABBs, removing the application logic and sharpening the focus on interactions between application and operating system.

The SSE algorithm [11] traverses this processed CFG and updates the abstract system state, until a system call ABB is reached. The abstract system state is an abstract representation of the relevant system state, including task states, ready queues, resource locks, and interrupt states. Additionally, the values of system call parameters (constants or symbolic values calculated using the external SVF framework [47]) and the currently executed ABB are tracked in the CFG traversal. However, for complex, nested call parameters which cannot be derived statically, the interaction analysis is limited by the parameter value analysis. In real-time systems, the parameters are often constants, so we consider this to be a minor constraint.

Then, the effect of this system call must be interpreted using a predetermined operating system model to derive the follow-up abstract system state. In previous work, this model has been manually derived from a specification for OSEK/AUTOSAR [11] or generated at analysis runtime using IRx system call interpreter [24]. During traversal, the algorithm constructs a graph that contains the visited system states and their transitions, called the State Transition Graph (STG) [11]. In a system with finite states, the SSE terminates when all possible states and their transitions have been found and connected in the STG. This traversal is of exponential complexity, but there are techniques for reducing the state space, such as widening to imprecise states, limiting interrupt arrivals, or using per-task and interrupt timing information to rule out impossible system states.

In the MultiSSE, the SSE is executed for each core independently, without synchronization between cores during CFG traversal. Only when a system call affects two or more cores, the local STGs are synchronized using SPs, creating the Multicore State Transition Graph (MSTG). Additionally, interrupts are modeled as virtual CPU cores, which are synchronized using the same mechanism if interrupts occur. Using the control flow trace at a given abstract system state, the SP search can find a tighter limit of possible multicore system states, filtering out the ones that cannot exist based on the control flow. If timing properties are annotated per ABB, the search space can be reduced significantly. This leads to a much sparser MSTG, which they use to tailor the RTOS to the application by optimizing cross-core interactions in AUTOSAR systems such as locking and inter-processor-interrupts [14].

We build on the ABB, SSE, and SP foundations introduced in the aforementioned works and apply HyperSSE to SPHs with multiple real-time operating systems and general-purpose domains. The main advantage of HyperSSE is the composition of multiple, existing domain-local analyses, which we demonstrate in our example application. We generalize and extend the MultiSSE to achieve a platform-global static analysis by hierarchically combining the domain-local STGs into a cross-domain HSTG using SPs at cross-domain hypercalls. Conceptually, this adds a hypervisor-level analysis layer over OS-level analyses, mirroring the stack of hypervisor over OS and hypercall over system call. Where the MultiSSE connected parallel CPU cores with SP, the HyperSSE connects parallel operating systems.

We adopt its constraints in the platform model by restricting ourselves to real-time domains with static instance configurations. This requirement excludes unbounded dynamic creation and destruction of tasks or resources at runtime, which is typically disallowed or strongly discouraged in RTOSs. Additionally, we propose the abstraction of control flows as described in the following section for other domains which do not fit this requirement.

For complex control flows in non-static domains or systems without existing OS models, we can subsume all domain-local interactions, including system calls and core-local interrupts, into computation ABBs that are separated only by hypercalls. In contrast to the SSE, where we use detailed timing information like BCET and WCET per ABB, other domains with lower criticality may not require such fine-grained internal timing analysis, and a less precise analysis is sufficient. Therefore, we abstract away their internal control flow, and expose only hypercalls to the interaction analysis. Using a predetermined task model for the relevant task, HyperSSE can incorporate general purpose operating system domains, as well as hardware accelerators, coprocessors, or other peripherals, which we collectively describe as baremetal domains, because they do not need an OS model.

To summarize, we are able to compose a platform-global analysis containing all knowledge about existing real-time domains and modeled domains with an abstracted control flow.

Figure 2 illustrates the layering of system calls and hypercalls for the AUTOSAR domain in the running example. The local CFG contains explicit hypercall and system call ABBs, always interleaved with computation ABBs. The LLVM compiler toolchain [25] is used for local CFG creation, while the SVF [47] static value-flow analysis framework is needed for interprocedural control flows, for example, when the parameter of an upcoming system call is passed through multiple functions. Every OS-relevant call requires one of our specialized static analysis steps: hypercalls need to be handled at the hypervisor level using HyperSSE, while system calls are interpreted using the OS model by the (Multi-)SSE. Identical to the MultiSSE, we account for the time of the hypercall itself in the surrounding computation ABBs, so all events are analyzed atomically with a global sequence.

To analyze multiple domains, the abstract system state is extended by hypervisor-level elements, such as cross-domain event channels, interrupt states, and callback tasks. The global abstract system state must be split into domain-local states, and merged on cross-domain interactions. Without interactions, each domain updates independently using the local SSE, leaving the other domains as black boxes without affecting them. For the implementation, this allows for a local analysis, while the global abstract system state is constructed only at SPs. At cross-domain hypercalls, the global abstract system state is constructed and modified only when needed. This abstraction makes use of the enforced isolation, where only specific hypercalls can affect the state of another domain.

With the existing SP search developed for multicore AUTOSAR applications, we can mostly reuse a building block for synchronization of control flows at the ABB level. To apply this synchronization concept to control flows in isolated domains, we must define a common initial SP across those domains. In a SPH system, where all domains boot in parallel, we can simply incorporate the BCET and WCET of the boot time into the analysis. Alternatively, an explicit and dedicated startup handshake or barrier between partitions for initial synchronization is also possible (and common practice).

Analogous to (Multi-)SSE for a single system, HyperSSE enables control-flow–sensitive WCRT analysis by sharing knowledge of execution states at interactions across the boundaries of hypervisor isolation. Because we follow the cross-domain control flow and synchronize the state between the domains, a platform-wide view of all possible states is generated. This facilitates timing analyses like SysWCET [12] to calculate tighter WCRTs even for cross-domain paths. Furthermore, by examining the interaction patterns, whole-platform optimizations such as improved partitioning and placement of domains, hypervisor fast paths, or control-loop timing adaptations could be implemented.

With HyperSSE, we can synchronize arbitrary control flows across multiple interacting domains, as long as they match the system model described in Section 2. In general, these domains could be defined as CPUs managed by the same OS (as in the MultiSSE), virtual machines, accelerators, remote coprocessors, or even nodes in distributed systems. To demonstrate our approach, we implement it for hypervised automotive real-time systems, specifically a static partitioning Xen hypervisor with Linux, Zephyr, and AUTOSAR as guest virtual machines, as introduced in Figure 1. We chose the Xen hypervisor for our implementation for various reasons: Paravirtualized event channels enable inter-VM signaling with explicit interrupt-based communication, which is a requirement for synchronization points between domains. In a dom0less setup, Xen supports real-time domains to boot simultaneously without an additional control domain, which allows for very fast boot-up times and mitigates the dependency on low-criticality domains. Furthermore, Xen’s maturity and support for multiple architectures make it a good candidate for real-world applications, especially as the project aims to achieve compliance with functional safety standards like ASIL D [33].

Inspired by compiler optimization passes, the ARA whole-system-analyzer and compiler chains together steps that can analyze or modify the LLVM [25] intermediate representation of application code. These steps can be implemented in C++ to directly access the LLVM API or in Python, where operating system behavior at system call sites can be modeled on the abstract state more easily. The generated data is shared between all steps using graph-based data structures, for example the SVF graphs or ARA’s own instance graph and system state representations [16].

For HyperSSE, we implement a new step that performs the cross-domain interaction analysis for hypervisors and add a Xen hypervisor model. Furthermore, all preprocessing steps must be executed once for each domain to prepare the local CFG, as shown in Figure 3. This requires steps to be repeatable and work on the correct domain-local set of graph structures instead of global ones. We modify ARA to use domain-local structures and to allow multiple executions of the same step on different domains.

The SSE algorithm as described by Dietrich et al. [11] operates on single-core statically configured and event-triggered systems like OSEK/AUTOSAR. All tasks, ISRs and other OS objects are known in advance, which allows for the complete static analysis including all possible paths. In Figure 4 the SSE algorithm is depicted. Beginning from a defined initial system state, the application-local CFG is followed, including all possible branches, until a system call is detected. Then, the RTOS semantics are applied to interpret the system call behavior and to find all follow-up states. The traversal is continued until all states have been visited and the State Transition Graph (STG) is complete, including all possible paths, states and interactions between tasks. For simplicity, the triggering of possible interrupts, which is handled at the end of interpret_or_schedule is omitted. Possibly, every ABB could trigger an interrupt, leading to an exponential increase in the list of states. This state explosion has been mentioned in the original work already, and requires additional constraints like inter-interrupt times or activation limits. With the MultiSSE [14], the interrupts are not triggered during the CFG analysis anymore, but instead they are modeled as virtual CPU cores, which are synchronized when they arrive. The control flow of virtual interrupts should be annotated with minimum inter-arrival times or limited by activation counts, to mitigate the state explosion.

ARA’s internal design already provides RTOS-independent interfaces and data structures, to support various real-time operating systems and generic algorithms [15]. Each RTOS must implement a model of its system call behavior matching this specified interface, which can then be used by the (Multi-)SSE to interpret the system calls and to update the abstract system state, as described in Figure 4. This abstract OS model must implement the interface shown in Figure 5. It serves as a foundation for the cross-domain analysis, because state processing is independent of their underlying OS and the current state of hypervisor objects is shareable across different OSs.

In Figure 6, we show the implementation stack of analysis steps, with parallel domain-local analyses and the synchronization using HyperSSE. For each local SSE analysis, we mark Xen-specific hypercalls in addition to system calls. If a Synchronization Point (SP) between domains (or cores within one domain) is required, HyperSSE analyzes the cross-domain interaction (MultiSSE for cross-core within the domain) and generates the follow-up abstract system states in the HSTG.

The traversal algorithm for multiple domains closely resembles the MultiSSE [14] for multicore systems: As long as there are no interactions between domains, they can be analyzed independently, reducing synchronization effort. For the cross-domain analysis in Figure 7, all domain-local preparation steps need to be executed first for each domain before the HyperSSE step is executed.

We start HyperSSE from a defined initial cross-domain SP and then split the analysis into domain- and core-local CFG traversal for the SSE. When one domain initiates a cross-domain interaction, the potentially parallel abstract system states of the affected domains must be found: the pairing partners. The entry SPs synchronize the pairing partners, while associated exit SPs split the analysis again. To achieve this, we find and mark cross-domain hypercalls during the domain-local analysis, just as MultiSSE marks cross-core system calls. Because we follow the design of MultiSSE in ARA, we can reuse the existing implementation of the SP search algorithm based on a timing equation system with constraints to find the pairing partners for cross-domain interactions [16]. Finally, HyperSSE returns the HSTG, including STGs for all domains and SPs between them.

In order to analyze hypercalls in application code, we implement the Xen hypervisor as OS model in ARA, next to the unmodified actual RTOS models. Pragmatically, this allows the reuse of algorithms from the MultiSSE, especially the SP search. During CFG traversal, every state is first passed to the Xen model. There, the analysis processes hypercalls and their effects, while it forwards local system calls towards their respective OS model. This also allows for detailed checking of hypercall usage per domain, for example to verify the absence of policy violations regarding allowed hypercalls per context.

Although this design introduces some confusing naming (the OSState is actually a Hypervisor state within the Xen Model), it allows unlimited layering of interaction semantics between concurrent CPUs, domains or MPSoC (co-)processors, as long as they have an explicit interaction mechanism. For example, dedicated models could also analyze communication middleware or interactions in nested hypervisors, which could possibly be used in embedded ARM SoCs in the future [26].

We have also considered alternative designs such as a multi-level SP search. However, in practice this would require a complete reimplementation of the existing parts for multi-level data structures. To avoid complex synchronization edge cases, we can create SPs for cross-core and cross-domain interactions in the same way, because they work on the same global abstract system state.

For existing domain-local analyses, we extend the existing OS model interface from Figure 5 with helper functions related to hypervisors, as shown in Figure 8.

Because the domain-local analyses are not aware of the hypervisor, we need to rewrite the CPU IDs of OS objects to globally unique ones. For example, a dual-core-AUTOSAR domain with two additional interrupts modeled as virtual CPUs [14], and a single-core Zephyr domain with one additional local interrupt modeled as a virtual CPU, would require 6 unique IDs in total after move_context or move_irqhandler have been called for each of them.

With this minimal example of a sender and receiver domain in Figure 9, we go through the most important details of the implementation for the aforementioned interface.

To initialize OS objects and launch automatically started tasks or the main thread for each domain, get_initial_state must return an OSState. In the Xen hypervisor, this state is a combination of the initial states of all domains. To merge the initial states, we store the dependencies for local analysis per domain, such as the CFG and instance graph in a list indexed by the static domain identifier. As illustrated in Figure 10, we combine the contexts of all domains into a single global context.

As described in Figure 4, is_syscall matches the current system call against a predefined set of system calls from the model, and the respective OS model must interpret the system call semantics and update the abstract system state. Accordingly, we must check for hypercalls in the Xen model first. All other system calls are forwarded for local interpretation to the correct guest domain, identified by the CPU id of the current control flow.

The goal of our Xen model is not to simulate and interpret every possible usage of Xen hypercalls in all used OSs. Instead we abstract their effect on other domains using domain-independent system call wrapper functions, used across all domains. Each guest domain OS implements the wrapper function using existing system calls, or by calling Xen hypercalls directly in the wrapper. This step removes the complexity of OS specific data structures and implementation details, that are of no interest for our analysis and the effect on other domains. The disadvantage is that applications must be modified towards this unified interface, but we assume that RTOSs minimize unnecessary complex interaction patterns.

Currently, we support a subset of wrappers for Xen hypercalls related to event channels and shared memory interactions.

• $\mathrm{■}$

  evt_chn_{alloc_unbound,bind_interdomain} connect to remote domain with callback,

• $\mathrm{■}$

  event_channel_send send an event over the initialized channel,

• $\mathrm{■}$

  event_channel_poll as a minimal callback wrapper for event polling.

• $\mathrm{■}$

  share/recv_mem setup shared memory region (using Xen Grant Tables),

• $\mathrm{■}$

  read/write_mem explicit annotation for shared memory access.

Regarding shared memory, once a shared memory is set up, write system calls trigger a synchronization point with all domains that have access to the same memory, while read system calls are analyzed locally. Because of the exponential state count, we do not analyze the content of shared memory and only analyze the order of memory operations.

For the interpretation of event hypercalls, we define a CrossOSEvent as a common abstraction across domains. For each OS model, those can be implemented differently: In event-driven real-time systems with tasks like AUTOSAR, we model an OS event as a task, that is activated once a cross-domain event is registered (if the channel is not masked). Such asynchronous ActivateTask semantics are identical to cross-core ActivateTask calls, which are already supported by the MultiSSE. In general, a CrossOSEvent is a callback function or thread, which is called by the hypervisor once the event is triggered.

RTOS models must also implement their scheduling policy, which is done after system calls, usually based on task priorities, semaphores, etc. For SPH like dom0less Xen, we do not schedule domains. Instead, we just split the global abstract system state after a hypercall into local ones, which become scheduling points for the domain-local analyses.

Next to the Xen model, we also need to extend the ARA framework itself with a new HyperSSE step. Most importantly, we must extend the step management system to allow multiple executions of the same steps for different domains, as dependency for HyperSSE (compare Figure 6). We do this by iterating through the guest domains, and adding the required steps depending on the domain type. For example, the AUTOSAR domain requires parsing of the RTOS configuration (OIL-file) additionally to the usual steps for CFG and instance graph generation, while Zephyr needs other steps for its domain-local analysis.

While most of the steps written in Python can be run multiple times without modification, especially the ARA integration of the SVF analysis framework [47] requires some adjustments, because its singleton pattern could not process multiple domains. Similar to the existing debugging and visualization for the (Multi-)SSE, we have extended ARA with printing capabilities for HyperSSE, to visualize the generated HSTG using graphviz.

In summary, we have added $\mathrm{3\hspace{0.17em}019}$ lines of code to the ARA framework, with $\mathrm{1\hspace{0.17em}693}$ lines of Python in the Xen and OS models, and $\mathrm{1\hspace{0.17em}230}$ lines of Python/C++ in the ARA steps, including the HyperSSE logic.

For the various interaction scenarios in Table 1, we have examined the generated HSTGs manually for correctness. These tests cover the OS and hypervisor models, as well as the synchronization of control flows across domains. The HSTGs for all test cases are appended as Figure 12.

The first set of test cases (1–6) contains two domains without interactions, to verify the correct behavior of initialization, merging and splitting of local and global states. Then, we examine the correct detection and handling of cross-domain events for a set of domain combinations (7–18) with and without timing annotations (19–21). We also include some more complex interaction patterns such as events with polling, ping-pong and multiple channels (22–24). For analyzing shared memory synchronization, we have implemented a set of tests with different access patterns for a memory region shared between two domains (25–28). Finally, additional domain-local interrupts within the domains (29–30) are leading to additional SPs. With these tests, we were able to fix various bugs in domain-local analyses, especially in the Zephyr model, which was not designed to be instantiated multiple times.

For the running example in Figure 1, we apply HyperSSE to all three domains with exemplarily estimated timing annotations per ABB.

The complete HSTG with timing information is appended in Figure 13. It contains $13$ synchronization points, and $54$ local abstract system states in total, taking $5$ seconds for the analysis. We show a simplified version in Figure 11 for better readability.

Without any timing information, running HyperSSE for this example must lead to a state explosion because of the endless synchronization possibilities with the loop. If we manually unroll the control loop to two iterations, the HSTG already contains $719$ synchronization points between $201$ local abstract system states and takes $92$ seconds for the analysis on the AMD Ryzen 7 PRO 7840U.

After the inital SP and initialization of all domains is executed once (dotted line), the control loop is started in the critical AUTOSAR domain (red). After triggering the calculation within the Zephyr domain (blue), the HMI is updated in the Android domain (green). When the calculation is finished, the polling from the AUTOSAR domain is successful, and the measuring task can be started again (Path a). In the emergency case, the loop is discontinued and the emergency braking task is activated (Path b), also sending an event to the Zephyr domain. With this result, we can answer the questions raised in Section 3 with a manual inspection of the graph; we are confident that an automatic verification is also possible:

1. 1.

   For the worst case time until the speed adjustment is available for display to the driver, we look at the following state transition path in the HSTG. The timing annotations in milliseconds between states are added to the edges.

   At the end, the WCRT is $32\mathrm{ms}$ from measuring until the HMI is updated.

2. 2.

   To compare the response time from measuring to acknowledge against the critical loop cycle, we look at the control loop path in the HSTG:

   Because the WCRT $49\mathrm{ms}\le 50\mathrm{ms}$ is fast enough for the control loop, the system is always stable, and timely responses are guaranteed. If the calculation took longer (27-30), we would see an additional SP between and , leading to a timing violation as shown by the magenta edge.

3. 3.

   In order to check for possible interference of memory-intense calculation with critical accesses, we look at the critical ABB in the measuring task. As the other domains are in idle state during that time, we can be assured that there is no interference through transparently shared resources.

4. 4.

   Lastly, we can safely assume that the braking support ISR does not need to be considered in the WCRT analysis of the control loop, as it is only triggered when emergency braking is active and the control loop is not running. If there could be an interrupt during the control loop, we would see a new SP, and the interrupt handler would become part of the WCRT.