Timing analysis for embedded real-time systems is crucial to guarantee the correct behavior and to calculate the Worst-Case Response Time (WCRT) of safety-critical applications. With the increasing requirements of such systems in automotive, industrial or avionic industries, consolidation of multiple real-time and general-purpose operating systems on a single high-performance Multiprocessor System-on-Chip (MPSoC) platform using Static Partitioning Hypervisors (SPHs) is becoming more prevalent. Although the strong separation is well suited to reduce interference between isolated domains in such mixed-criticality systems, cross-domain interactions must still be considered in real-time analysis. Previous work has focused on dynamic monitoring and enforcement of timing constraints in virtualized environments. In this paper, we present HyperSSE, the first approach for the static analysis of cross-domain interactions in hypervisor-based real-time systems. By hierarchically combining existing domain-local static analyses, and synchronizing the control flow at cross-domain interactions, we enable control-flow-sensitive whole-platform analysis including multiple real-time domains. Using abstract task models, this approach can integrate a coarser analysis of general-purpose operating systems, accelerators, and coprocessors with the precise timing analysis. We demonstrate the applicability of HyperSSE in an automotive case study with mixed-criticality software stacks running on Xen in a static partitioning configuration. The resulting Hypervisor State Transition Graph (HSTG) exposes deep knowledge about the platform interactions, enabling cross-domain timing analysis with reduction of pessimistic WCRT calculations. Additionally, HyperSSE can be used for placement optimizations for better predictability, verification of critical interaction paths, and is the foundation for further platform-level analyses, such as analysis of implicit interactions through transparent resource sharing.

The provisioning of the right amount of DRAM to virtual machines (VMs) is still a major challenge and cost driver in virtualization settings. Many VMs run applications with highly volatile memory demands, which either leads to massive overprovisioning in low-demand phases or poor QoS in high-demand phases. Memory hotplugging and ballooning have become established techniques (in Linux/KVM available via virtio-mem and virtio-balloon) to dynamically de/inflate the physical memory of a VM cooperatively, by having the guests give back unused memory to the hypervisor. However, current VM deflation techniques are either not DMA-safe, preventing the passthrough of important devices like GPUs or NICs, or are not flexible or fast enough to cope with the frequently changing demands of the guest.

The Apple M1 ARM processor family incorporates two memory consistency models: the conventional ARM weak memory ordering and the Total store ordering (TSO) model from the x86 architecture utilized by Apple’s x86 emulator, Rosetta 2. The presence of both memory ordering models on the same hardware enables us to thoroughly benchmark and compare their performance characteristics and worst-case workloads. In this paper, we assess the performance implications of TSO on the Apple M1 processor architecture. Based on the multi-threading workloads of the SPEC2017 CPU FP benchmark suite, our findings indicate that TSO is, on average, 8.94 percent slower than ARM’s weaker memory ordering. Through synthetic benchmarks, we further explore the workloads that experience the most significant performance degradation due to TSO. We also take a deeper look into the specific atomic instructions provided by the ARMv8.3 specification and their synchronization overheads.

Abstract The development of static real-time control systems often follows a closed-world assumption, allowing extensive RTOS-aware whole-program optimization. For single-core systems, previous work could show the high potential of control-flow-aware static system-call tailoring. However, due to an exponential state explosion in the analysis phase, it cannot simply be extended to a multi-core setting, since the core’s relative timing to each other is undetermined. In this work, we present MultiSSE, a multi-core capable and RTOS-aware static whole-system optimization. First, MultiSSE analyzes the system by determining the relative positions of multiple cores only when necessary. For that, it exploits structural control flow and optionally timing information to handle each core separately as much as possible. Based on the analysis result, a synthesis applies lock elision and system-call optimization to generate specialized multi-core real-time systems for AUTOSAR OS. To enable a static prediction of the run-time reduction, we additionally provide cost models for the optimized cross-core system calls and evaluate the approach with synthetic benchmarks and a real-world quadrotor application. MultiSSE was able to optimize or even completely elide costly cross-core system calls and system objects leading to a reduction of up to 14% of a task’s execution time. In this extended version of a conference publication (Entrup et al. 2023), we provide an advanced description, new cost models, and an end-to-end measurement by developing a synthesis complementing the analysis.

ARMv8.3-A has introduced the pointer authentication (PA) feature, a new set of measures and instructions to sign and validate pointers. PA is already used and supported by the major compilers to protect the return addresses on the stack as a measure against memory corruption attacks. As more and more SoCs implement ARMv8.3-A and code compiled with PA is even fully backwards compatible on CPUs without (where the new instructions are just ignored), we can expect PA-enabled binaries to become standard in the near future. This gives rise to the question, if and how also systems without the native PA could benefit from the extra security provided by the return address protection. In this article, we explore KPAC, a set of efficient software-based approaches to bring the PA-based return-address protection onto the platforms without the hardware support in an easily adoptable (binary-compatible) and scalable manner. Technically, KPAC achieves this by either a synchronous trap-based emulation inside the kernel or an asynchronous novel memory-based invocation of a dedicated CPU core. Our experiments with the CortexSuite benchmarks, Chromium, and Memcached on a variety of platforms running Linux ranging from a Xilinx ZCU102 board over a Raspberry Pi 4 up to an 80-core Ampere Altra demonstrate the broad applicability and scalability of our approach. Furthermore, we discuss how the principles of KPAC can be generalized to the other suited problem areas.

Existing debloating techniques designed to prevent buffer-overflow exploits through return-oriented programming do not differentiate roles within a process or binary, allowing all threads access to the full program functionality. For example, a worker thread that handles client connections (highest attack exposure) still has access to all the code that the management thread needs (highest potential fallout).

The implementation of static real-time control systems often allows for extensive compile-time optimizations based on RTOS-aware whole-program analyses. Previous work has shown the high optimization potential of control-flow aware static system-call tailoring, but is restricted to single-core systems due to the inherent problem of an exponentially growing analysis state in multicore settings. We present MultiSSE, a multi-core capable and RTOS-aware static whole-system analysis that makes such analyses also feasible on multi-core systems. MultiSSE exploits structural and optional timing information to analyze the core-level control flows as independently as possible from each other, synchronizing their states only when necessary. Thereby, MultiSSE provides means to realize compile-time deadlock detection, lock elision, and systemcall optimization also on multi-core systems. We evaluate our approach with synthetic benchmarks and a real-world quadrotor application. In all cases, we were able to optimize or even completely elide costly cross-core system calls and system objects.

We describe TASTING, an approach for efficiently selecting and reusing regression-test executions across program changes, branches, and variants in continuous integration settings. Instead of detecting changes between two variants of the software-under-test, TASTING recursively composes hashes of the defining elements with all their dependencies on AST-level at compile time into a semantic fingerprint of the test and its execution environment. This fingerprint is easy to store and remains stable across changes if the test’s run-time behavior is not affected. Thereby, we can reuse test results across the history, multiple branches, and static compile-time variants. We applied TASTING to three open-source projects (Zephyr, OpenSSL, FFmpeg). Over their development history, we can omit between 10 percent (FFmpeg) and 95 percent (Zephyr) of all test executions at a moderate increase in build time. Furthermore, TASTING enables even higher savings across multiple checkouts (e.g., forks, bra nches, clones) and static software variants. Over the first changes to 131 OpenSSL forks, TASTING avoids 56 percent redundant test executions; for the Zephyr test matrix (64 variants), we reduce the number of test executions by 94 percent.

While processing external events, in the form of interrupt requests (IRQs), is a key concern of digital control systems, processing these events can be of different importance for a system’s functionality. Therefore, it is necessary, especially for real-time systems, to ensure that the handling of low-priority IRQs does not interfere with high-priority interrupt-service routines (ISRs) to prevent priority inversions. While prioritizing ISRs on single-core machines is a long-solved problem, priority-strict IRQ handling in multi-core systems is, as we will show, quite challenging with current interrupt controllers.With PSIC, we propose a hardware/software co-design that ensures the priority-strict execution of the top-m ISRs on an m-core machine at minimal interruption-induced overheads. We developed a drop-in replacement for an off-the-shelf interrupt controller that delivers IRQs in strict priority order while achieving low delivering delays at moderate hardware costs. Combined with a minimal IRQ software subsystem, which requires no inter-core synchronization, PSIC guarantees a priority-strict ISR execution on multiple cores.

In the domain of safety-critical systems, fault injection campaigns on ISA-level have become a widespread approach to systematically assess the resilience of a system with respect to transient hardware faults. However, experimentally injecting all possible faults to achieve full fault-space coverage is infeasible in practice. Hence, pruning techniques, such as def/use pruning are commonly applied to reduce the campaign size by grouping injections that surely provoke the same erroneous behavior. We describe data-flow pruning, a new data-flow sensitive fault-space pruning method that extends on def/use-pruning by also considering the instructions’ semantics when deriving fault-equivalence sets. By tracking the information flow for each bit individually across the respective instructions and considering their fault-masking capability, data-flow pruning (DFP) has to plan fewer pilot injections as it derives larger fault-equivalence sets. Like def/use pruning, DFP is precise and complete and it can be used as a direct replacement/alternative in existing software-based fault-injection tools. Our prototypical implementation so far considers local fault equivalence for five types of instructions. In our experimental evaluation, this already reduces the number of necessary injections by up to 18 percent compared to def/use pruning.

After power-on, crash or reboot, the system-setup point is the first deadline that a safety-critical system has to reach. Up to this point, the application not only initializes its own state but it also creates all necessary system objects (e.g., threads, mutexes, alarms, ...) in the real-time operating system. And, while the strict requirements for real-time analyses often result in a rather static set of created system objects, the commonly-provided real-time operating system (RTOS) interfaces force developers to execute these creations at run time, resulting in an unnecessarily prolonged boot process. With ARA, we present a static whole-system transformation that discovers pseudo-dynamic system-object creations (SOCs) which yield the same object on every boot. By modifying the application and by RTOS specialization, we transform these SOCs to semantically equivalent static SOCs, which moves their instantiation from the run time to the compile time. Thereby, we maintain the well-known RTOS interfaces for dynamic SOCs but let developers enjoy the benefits that static initialization provides. In our case studies with FreeRTOS applications, we could reduce the boot time by up to 43 percent at a moderate increase of flash usage.

System software, such as the Linux kernel, typically provides a high degree of versatility by means of static and dynamic variability. While static variability can be completely resolved at compile time, dynamic variation points come at a cost arising from extra tests and branches in the control flow. Kernel developers use it (a) only sparingly and (b) try to mitigate its overhead by run-time binary code patching, for which several problem/architecture-specific mechanisms have become part of the kernel.

A considerable corpus of research on software evolution focuses on mining changes in software repositories, but omits their pre-integration history. We present a novel method for tracking this otherwise invisible evolution of software changes on mailing lists by connecting all early revisions of changes to their final version in repositories. Since artefact modifications on mailing lists are communicated by updates to fragments (i.e., patches) only, identifying semantically similar changes is a non-trivial task that our approach solves in a language-independent way. We evaluate our method on high-profile open source software (OSS) projects like the Linux kernel, and validate its high accuracy using an elaborately created ground truth. Our approach can be used to quantify properties of OSS development processes, which is an essential requirement for using OSS in reliable or safety-critical industrial products, where certifiability and conformance to processes are crucial. The high accuracy of our technique allows, to the best of our knowledge, for the first time to quantitatively determine if an open development process effectively aligns with given formal process requirements.

Due to shrinking structure sizes and operating voltages, hardware becomes more susceptible to transient faults. Fault injection campaigns are a common approach to systematically assess the resilience of a system and the effectiveness of software-based counter measures. However, experimentally injecting all possible faults to achieve full fault-space coverage is infeasible in practice. While precise pruning techniques, such as def/use pruning, already provide a significant reduction of the campaign size, the number of injections remains still challenging for even medium-sized systems. We propose fault-space regions (FSRs) as a method to approximately cover the complete fault space with a significantly lower number of required injections. Instead of probabilistic subsampling of the fault space, our approximation exploits the actual program structure and execution trace (e.g., flow of basic blocks) to identify injection points that are representatives for a larger set of faults. We identify such data-flow regions and inject only data values that flow across region boundaries. Thereby, we can further reduce the number of injections by up to 76 percent, while the results divert only by less than 2.7 percent from those of a complete and precise fault-injection campaign. Furthermore, we keep the locality of the results regarding silent data corruptions to a deviation of less than 6.9 percent.

For billions of deployed browsers, JavaScript provides the platform-independent lingua franca that enabled the triumphal march of web-based applications. Originally intended for simple UI-event processing, JavaScript comes with an event-driven programming model, where event-callback functions are executed in strict sequential order. However, with applications getting more complex and tasks becoming more computation intensive, its first-come-first-serve and run-to-completion semantic is hitting a limit, when reactions to user inputs are delayed beyond the human perception threshold. With the rise of the Internet of Things, this leads to friction-filled user experiences in everyday situations. With RT.js, we selectively introduce pseudo-preemption points into JavaScript functions and sequence the execution of event callbacks with well-known real-time scheduling policies, like EDF. Thereby, we provide a soft real-time abstraction that mitigates the described shortcomings of the JavaScript execution model without modifying the actual engine; making RT.js compatible with billions of devices. Applied to generated real-time task sets, we can almost eliminate the 30-percent deadline-miss ratios of baseline JavaScript at moderate costs. In a browser-based macro benchmark, we could diminish the influence of computation-intensive background tasks on the page-rendering performance.

In the operation and maintenance phase of a deployed software component, security and bug-fix updates are regular events. However, for many high-availability services, costly restarts are no acceptable option as the induced downtimes lead to a degradation of the service quality. One solution to this problem are live updates, where we inject the desired software patches directly into the volatile memory of a currently running process. However, before the actual patch gets applied, most live-update methods use a stop-the-world approach to bring the process into a safe state; an operation that is highly disruptive for the execution of multi-threaded programs.

In the embedded domain, industrial sectors (i.e., automotive industry, avionics) are undergoing radical changes. They broadly adopt commodity hardware and move away from special-purpose control units. During this transition, heterogeneous software components are consolidated to run on commodity operating systems. To efficiently consolidate such components, a modular encapsulation of common functionality into reusable binary files (i.e., shared libraries) is essential. However, shared libraries are often unnecessarily large as they entail a lot of generic functionality that is not required in a narrowly defined scenario. As the source code of proprietary components is often unavailable and the industry is heading towards binary-only distribution, we propose an approach towards lightweight binary tailoring . As demonstrated in the evaluation, lightweight binary tailoring effectively reduces the amount of code in all shared libraries on a Linux-based system by 63 percent and shrinks their files by 17 percent. The reduction in size is beneficial to cut down costs (e.g., lower storage and memory footprint) and eases code analyses that are necessary for code audits.

With shrinking structure sizes, soft-error mitigation has become a major challenge in the design and certification of safety-critical embedded systems. Their robustness is quantified by extensive fault-injection campaigns, which on hardware level can nevertheless cover only a tiny part of the fault space.

Memory is an expensive and, therefore, limited resource in deeply embedded real-time systems. Thread stacks substantially contribute to the RAM requirements. To reduce the system's worst-case stack consumption (WCSC), it is state of the art to exploit thread-level preemption constraints to let multiple threads share the same stack. However, deriving a tight, yet correct bound for the shared stack is a difficult undertaking and stack sharing is currently restricted to run-to-completion threads, which are preemptable, but cannot block (i.e., passively wait for an event) at run time. With semi-extended tasks (SETs), we propose a solution for efficient stack sharing among blocking and non-blocking threads on the system level. For this, we refine the stack-sharing granularity from the thread to function level. We provide an efficient intra-thread stack-switch mechanism and an ILP-based WCSC analysis that considers fine-grained preemption constraints and possible function-level switching points from the private to the shared stack. A genetic algorithm then selects switching points that lead to the reduction of the overall WCSC. Compared to systems that run only non-blocking threads on the shared stack, semi-extended tasks decrease the WCSC in our benchmarks on average by 7 percent and up to 52 percent for some systems.

The OSEK industrial standard governs the design of embedded real-time operating systems in the automotive domain. We report on efforts to develop verification methods for OSEK-conformant compilers, specifically of a code generator that weaves system calls and application code using a static configuration file, producing a stand-alone application that incorporates the relevant parts of the kernel. Our methodology involves two verification steps: On the one hand, we extract an OS-application interaction graph during the compilation phase and verify that it conforms to the standard, in particular regarding prioritized scheduling and interrupt handling. To this end, we generate from the configuration file a temporal specification of standard-conformant behaviour and model check the arising formulas on a labelled transition system extracted from the interaction graph. On the other hand, we verify that the actual generated code conforms to the interaction graph; this is done by graph isomorphism checking of the interaction graph against a dynamically-explored state-transition graph of the generated system.

The employment of a real-time operating system (RTOS) in an embedded control systems is often an all-or-nothing decision: While the RTOS-abstractions provide for easier software composition and development, the price in terms of event latencies and memory costs are high. Especially in HW/SW codesign settings, system developers try to avoid the employment of a full-blown RTOS as far as possible. In OSEK-V, we mitigate this trade-off by a very aggressive tailoring of the concrete RTOS instance into the hardware. Instead of implementing generic OS components as custom hardware devices, we capture the actually possible application-kernel interactions as a finite-state machine and integrate the tailored RTOS semantics directly into the processor pipeline. In our experimental results with an OSEK-based implementation of a quadrotor flight controller into the Rocket/RISC-V softcore, we thereby can significantly reduce event latencies, interrupt lock times, and memory footprint at moderate costs in terms of FPGA resources.

The worst-case response time (WCRT) – the time span from release to completion of a real-time task – is a crucial property of real-time systems. However, WCRT analysis is complex in practice, as it depends not only on the realistic examination of worst-case execution times (WCET), but also on system-level overheads and blocking/preemption times. While the implicit path enumeration technique (IPET) has greatly improved automated WCET analysis, the resulting values still need to be aggregated manually with the system-level overheads – an errorprone and tedious process that yields overly pessimistic results. With SysWCET, we provide an integrated approach for the automated WCRT analysis across multiple threads of execution, locks, interrupt service routines, and the real-time operating system (RTOS) in particular. Our approach spans a single IPET formulation over the whole system and exploits RTOS and scheduler semantics to derive cross-kernel flow facts in order to significantly reduce pessimism in the WCRT analysis. We evaluate our approach with a fully functional implementation of SysWCET for the automotive OSEK-OS standard (ECC1), including threads, alarms, interrupt-service routines, events, and PCP-based resource management.

Cyber--physical systems typically target a dedicated purpose; their embedded real-time control system, such as an automotive control unit, is designed with a well-defined set of functionalities. On the software side, this results in a large amount of implicit and explicit static knowledge about the system and its behavior already at compile time. Compilers have become increasingly better at extracting and exploiting such static knowledge. For instance, many optimizations have been lifted up to the interprocedural or even to the whole-program level. However, whole-program optimizations generally stop at the application--kernel boundary: control-flow transitions between different threads are not yet analyzed. In this article, we cross the application--kernel boundary by combining the semantics of a real-time operating system (RTOS) with deterministic fixed-priority scheduling (e.g., OSEK/AUTOSAR, ARINC 653, μITRON, POSIX.4) and the explicit application knowledge to enable system-wide, flow-sensitive compiler optimizations. We present two methods to extract a cross-kernel, control-flow--graph that provides a global view on all possible execution paths of a real-time system. Having this knowledge at hand, we tailor the operating system kernel more closely to the particular application scenario. For the example of a real-world safety-critical control system, we present three possible use cases. (1) Runtime optimizations, by means of specialized system calls for each call site, allow one speed up the kernel execution path by 28% in our benchmark scenario. Furthermore, we target transient hardware fault tolerance with two automated software-based countermeasures: (2) generation of OS state assertions on the expected system behavior, and (3) a system-wide dominator-region based control-flow error detection, both of which leverage significant robustness improvements.

Testing a software product line such as Linux implies building the source with different configurations. Manual approaches to generate configurations that enable code of interest are doomed to fail due to the high amount of variation points distributed over the feature model, the build system and the source code. Research has proposed various approaches to generate covering configurations, but the algorithms show many drawbacks related to run-time, exhaustiveness and the amount of generated configurations. Hence, analyzing an entire Linux source can yield more than 30 thousand configurations and thereby exceeds the limited budget and resources for build testing.

Large-scale intra-organizational, yet decentralized software projects that involve various self-contained organizational units require architecture guidelines to coordinate development. Tool support allows for managing architecture-guideline violations to ensure software quality. However, the decentralized development across units results in significant violation-management hurdles that must be considered. In this paper, we present a set of capabilities required to manage guideline violations within two of these large-scale software projects at Siemens. Their main purpose is process support for resolving violations, aiming to reduce the architects' and developers' effort required to handle them. Moreover, we present a prototype that implements the capabilities.

Modifications to open-source software (OSS) are often provided in the form of "patch stacks" -- sets of changes (patches) that modify a given body of source code. Maintaining patch stacks over extended periods of time is problematic when the underlying base project changes frequently. This necessitates a continuous and engineering-intensive adaptation of the stack. Nonetheless, long-term maintenance is an important problem for changes that are not integrated into projects, for instance when they are controversial or only of value to a limited group of users.

Rendering performance is an everlasting goal of computer graphics and significant driver for advances in both, hardware architecture and algorithms. Thereby, it has become possible to apply advanced computer graphics technology even in low-cost embedded appliances, such as car instruments. Yet, to come up with an efficient implementation, developers have to put enormous efforts into hardware/problem-specific tailoring, fine-tuning, and domain exploration, which requires profound expert knowledge. If a good solution has been found, there is a high probability that it does not work as well with other architectures or even the next hardware generation. Generative DSL-based approaches could mitigate these efforts and provide for an efficient exploration of algorithmic variants and hardware-specific tuning ideas. However, in vertically organized industries, such as automotive, suppliers are reluctant to introduce these techniques as they fear loss of control, high introduction costs, and additional constraints imposed by the OEM with respect to software and tool-chain certification. Moreover, suppliers do not want to share their generic solutions with the OEM, but only concrete instances. To this end, we propose a light-weight and incremental approach for meta programming of graphics applications. Our approach relies on an existing formulation of C-like languages that is amenable to meta programming, which we extend to become a lightweight language to combine algorithmic features. Our method provides a concise notation for meta programs and generates easily sharable output in the appropriate C-style target language.

Embedded real-time control systems generally have a dedicated purpose and fixed set of functionalities. This manifests in a large amount of implicit and explicit static knowledge, available already at compile time. Modern compilers can extract and exploit this information to perform extensive whole-program analyses and interprocedural optimizations. However, these analyses typically end at the application--kernel boundary, thus control-flow transitions between different threads are not covered, yet. This restriction stems from the pessimistic assumption of a probabilistic scheduling policy of the underlying operating system, impeding detailed predictions of the overall system behavior. Real-time operating systems, however, do provide deterministic and exactly specified scheduling decisions, as embedded control systems rely on a timely and precise behavior.

Because of shrinking structure sizes and operating voltages, computing hardware exhibits an increasing susceptibility against transient hardware faults: Issues previously only known from avionics systems, such as bit flips caused by cosmic radiation, nowadays also affect automotive and other cost-sensitive “ground-level” control systems. For such cost-sensitive systems, many software-based measures have been suggested to harden applications against transient effects. However, all these measures assume that the underlying operating system works reliably in all cases. We present software-based concepts for constructing an operating system that provides a reliable computing base even on unreliable hardware. Our design is based on two pillars: First, strict fault avoidance by static tailoring and elimination of susceptible indirections. Second, reliable fault detection by fine-grained arithmetic encoding of the complete kernel execution path. Compared to an industry-grade off-the-shelf RTOS, our resulting dOSEK kernel thereby achieves a robustness improvement by four orders of magnitude. Our results are based on extensive fault-injection campaigns that cover the entire space of single-bit faults in random-access memory and registers.

This paper presents AUTOBEST, a united AUTOSAR-OS and ARINC 653 RTOS kernel that addresses the requirements of both automotive and avionics domains. We show that their domain-specific requirements have a common basis and can be implemented with a small partitioning microkernel-based design on embedded microcontrollers with memory protection (MPU) support. While both, AUTOSAR and ARINC 653, use a unified task model in the kernel, we address their differences in dedicated user space libraries. Based on the kernel abstractions of futexes and lazy priority switching, these libraries provide domain specific synchronization mechanisms. Our results show that thereby it is possible to get the best of both worlds: AUTOBEST combines avionics safety with the resource-efficiency known from automotive systems.

State-machine replication has received widespread attention for the provisioning of highly available services in data centers. However, current production systems focus on tolerating crash faults only and prominent service outages caused by state corruptions have indicated that this is a risky strategy. In the future, state corruptions due to transient faults (such as bit flips) become even more likely, caused by ongoing hardware trends regarding the shrinking of structure sizes and reduction of operating voltages. In this paper we present Crosscheck, an approach to tolerate arbitrary state corruption (ASC) in the context of fault-tolerant replication of multithreaded services. Crosscheck is able to detect silent data corruptions ahead of execution, and by crosschecking state changes with co-executing replicas, even ASCs can be detected. Finally, fault tolerance is achieved by a fine-grained recovery using fault-free replicas. Our implementation is transparent to the application by utilizing fine-grained software-hardening mechanisms using aspect-oriented programming. To validate Crosscheck we present a replicated multithreaded key-value store that is resilient to state corruptions.

Multi-core operating systems inherently face the problem of concurrent access to internal kernel state held in shared memory. Previous work on the Sloth real-time kernel proposed to offload the scheduling decisions to the interrupt hardware, thus removing the need for a software scheduler, no state has to be managed in software. While our existing design covers single-core platforms only, we now present Multi Sloth, a multi-core AUTOSAR OS implementation. In this paper, we show that our hardware-centric approach enables us to easily make the transition to multi-core platforms without the need for explicitly synchronizing kernel data. Even in the case of cross-core interactions, Multi Sloth keeps the unique Sloth properties of strict priority obedience and complete prevention of rate-monotonic priority inversions. AUTOSAR OS mandates only unordered spin locks, which do not guarantee predictable timing. We show the advantages of the Multi Sloth design by additionally providing a wait-free and efficient implementation of the priority-aware Multiprocessor Priority Ceiling Protocol (MPCP). On our reference platform, we achieve overheads as low as 1.1 μs for acquiring a globally shared resource using the MPCP and round-trip times of 1.4 μs for cross-core task activations.

System software can typically be configured at compile time via a comfortable feature-based interface to tailor its functionality towards a specific use case. However, with the growing number of features, this tailoring process becomes increasingly difficult: As a prominent example, the Linux kernel in v3.14 provides nearly 14 000 configuration options to choose from. Even developers of embedded systems refrain from trying to build a minimized distinctive kernel configuration for their device – and thereby waste memory and money for unneeded functionality. In this paper, we present an approach for the automatic use-case specific tailoring of system software for special-purpose embedded systems. We evaluate the effectiveness of our approach on the example of Linux by generating tailored kernels for well-known applications of the Rasperry Pi and a Google Nexus 4 smartphone. Compared to the original configurations, our approach leads to memory savings of 15–70 percent and requires only very little manual intervention.

Developers of embedded (real-time) systems can choose from a variety of operating systems. While some embedded operating systems provide very flexible APIs, e.g., a POSIX-compliant interface for run-time management, others have a completely static structure, which is generated at compile time by utilizing detailed application knowledge. A prominent example for the latter class from the domain of automotive operating systems is OSEK/OS and its successor AUTOSAR/OS. As we have shown in previous work, the design of the operating system has a strong impact on its vulnerability for system failure caused by hardware faults. This observation is gaining importance, because there is an ongoing trend towards low-power and low-cost, yet less reliable, hardware. This work quantifies the difference in vulnerability for soft errors in main memory of a flexible (dynamic) operating systems (eCos) and a static system (CiAO), which has an OSEK-compliant structure. We also analyze the additional degree of robustness that is achieved by hardening an operating system with software-based and hardware-based fault-tolerance measures and the corresponding costs. Covering this design space gives developers a better chance for good design decisions with respect to the trade-off between fault tolerance, resource consumption, and interface convenience. Our results indicate that with a combination of hardware- and software-based fault-tolerance measures, silent data corruptions in both operating systems can be reduced to below one percent (compared to eCos). However, the analyzed fault-tolerance mechanisms are expensive for the dynamic system, whereas the statically designed operating system can be hardened at much lower price.

The goal of the SLOTH family of operating system kernels is to provide a unified priority space to the real-time applications. By automated mapping of tasks to interrupts, we eliminate rate-monotonic priority inversion and increase execution determinism. In its standard implementation, however, SLOTH has been criticized for being unsafe, since interrupt service routines are executed in supervisor mode. SAFER SLOTH mitigates this shortcoming-while keeping the favorable properties of SLOTH-and provides a safe and isolated execution environment for application tasks. Adopting the SLOTH philosophy of embracing and exploiting hardware particularities, its generative approach automatically tailors the system to both the application and the target architecture. We achieve efficient MPU-based memory protection at reduced latency and low performance overhead by leveraging code inlining and compiler optimizations. In comparison to a commercial AUTOSAR OS, SAFER SLOTH achieves speedups between 8x (worst case) and 23x (best case) on kernel latencies while retaining the SLOTH advantages of strict priority obedience, excellent determinism and small memory footprints.

The idea of software ecosystems encourages organizations to open software projects for external businesses, governing the cross-organizational development by architectural and other measures. Even within a single organization, this paradigm can be of high value for large-scale decentralized software projects that involve various internal, yet self-contained organizational units. However, this intra-organizational decentralization causes architecture challenges that must be understood to reason about suitable architectural measures. We present an in-depth case study on collaboration and architecture challenges in two of these large-scale software projects at Siemens. We performed a total of 46 hours of semi-structured interviews with 17 leading software architects from all involved organizational units. Our major findings are: (1) three collaboration models on a continuum that ranges from high to low coupling, (2) a classification of architecture challenges, together with (3) a qualitative and quantitative exposure of the identified recurring issues along each collaboration model. Our study results provide valuable insights for both industry and academia: Practitioners that find themselves in one of the collaboration models can use empirical evidence on challenges to make informed decisions about counteractive measures. Researchers can focus their attention on challenges faced by practitioners to make software engineering more effective.

The reduction of structure sizes in microcontollers, environmental conditions or low supply voltages increase the susceptibility of embedded systems to soft errors. As a result, the employment of fault-detection and fault-tolerance measures is becoming a mandatory task even for moderately critical applications. Accordingly, software-based techniques have recently gained in popularity, and a multitude of approaches that differ in the number and frequency of tolerated errors as well as their associated overhead have been proposed. Using type-safe programming languages to isolate critical software components is very popular among those techniques. An automated application of fault-detection and fault-tolerance measures based on the type system of the programming language and static code analyses is possible. It facilitates an easy evaluation of the protection characteristics and costs, as well as the migration of software to new hardware platforms with different failure rates. Transient faults, however, are not bound to the application code secured by the type system, but can also affect the correctness of the type system itself. Thereby, the type system might lose its ability to isolate critical components. As a consequence, it is essential to also protect the type system itself against soft errors. In this paper, we show how soft errors can affect the integrity of the type system. Furthermore, we provide means to secure it against these faults, thus preserving its isolating character. These measures can be applied selectively to achieve a suitable tradeoff between level of protection and resource consumption.

The Linux kernel is one of the largest configurable open source software systems implementing static variability. In Linux, variability is scattered over three different artifacts: source code files, Kconfig files, and Makefiles. Previous work detected inconsistencies between these artifacts that led to anomalies in the intended variability of Linux. We call these variability anomalies. However, there has been no work done to analyze how these variability anomalies are introduced in the first place, and how they get fixed. In this work, we provide an analysis of the causes and fixes of variability anomalies in Linux. We first perform an exploratory case study that uses an existing set of patches which solve variability anomalies to identify patterns for their causes. The observations we make from this dataset allow us to develop four research questions which we then answer in a confirmatory case study on the scope of the whole Linux kernel. We show that variability anomalies exist for several releases in the kernel before they get fixed, and that contrary to our initial suspicion, typos in feature names do not commonly cause these anomalies. Our results show that variability anomalies are often introduced through incomplete patches that change Kconfig definitions without properly propagating these changes to the rest of the system. Anomalies are then commonly fixed through changes to the code rather than to Kconfig files.

Recent automotive systems exhibit an increased susceptibility against transient hardware faults. As a consequence, dependability measures are mandatory to provide appropriate fault detection or masking properties fulfilling the required safety standards. On the other and, production costs are still a crucial factor in this domain, which leads to hardware consolidation and therefore mixed-criticality systems. An existing dependability approach, supporting such systems, combines triple modular redundancy with encoded operations, but still leaves the operating system as single point of failure. We intend to close this gap by extending the encoded operations throughout the kernel execution, and additionally integrate the analyzed system behavior into the code.

Internet protocols are constantly gaining relevance for the domain of mobile and embedded systems. However, building complex network protocol stacks for small resource-constrained devices is more than just porting a reference implementation. Due to the cost pressure in this area especially the memory footprint has to be minimized. Therefore, embedded TCP/IP implementations tend to be statically configurable with respect to the concrete application scenario. This paper describes our software engineering approach for building CiAO/IP - a tailorable TCP/IP stack for small embedded systems, which pushes the limits of static configurability while retaining source code maintainability. Our evaluation results show that CiAO/IP thereby outperforms both lwIP and uIP in terms of code size (up to 90% less than uIP), throughput (up to 20% higher than lwIP), energy consumption (at least 40% lower than uIP) and, most importantly, tailorability.

Traditional time-triggered operating systems are implemented by multiplexing a single hardware timer - the system timer - in software, having the kernel maintain dispatcher tables at run time. Our Sloth on Time approach proposes to make use of multiple timer cells as available on modern micro controller platforms to encapsulate dispatcher tables in the timer configuration, yielding low scheduling and dispatching latencies at run time. Sloth on Time instruments available timer cells in different roles to implement time-triggered task activation, deadline monitoring, and time synchronization, amongst others. By comparing the Sloth on Time kernel implementation to two commercial kernels, we show that our concept significantly reduces the overhead of time-triggered operating systems. The speed-ups in task dispatching that it achieves range up to a factor of 171x, and its dispatch latencies go as low as 14 clock cycles. Additionally, we demonstrate that Sloth on Time minimizes jitter and increases schedulability for its real-time applications, and that it avoids situations of priority inversion where traditional kernels fail by design.

With more than 11,000 optional and alternative features, the Linux kernel is a highly configurable piece of software. Linux is generally perceived as a textbook example for preprocessor-based product derivation, but more than 65 percent of all features are actually handled by the build system. Hence, variability-aware static analysis tools have to take the build system into account.

Much system software can be configured at compile time to tailor it with respect to a broad range of supported hardware architectures and application domains. A good example is the Linux kernel, which provides more than 10,000 configurable features, growing rapidly.

Type-safe high-level languages such as Java have not yet found their way into the domain of deeply embedded systems, even though numerous attempts have been made to make these languages cost attractive. One major challenge that remains is the huge existing code base in many industries. Completely reengineering this code base is not viable for cost and time reasons. We present an approach that allows to isolatedly combine legacy software components and safe software components in an embedded system using the two most common communication idioms found in this domain. Our approach allows the developer to freely choose between hardware- and software-based isolation mechanisms. We demonstrate the feasibility of our approach by porting a non-trivial part of a real-world, hard real-time embedded avionics application. Our results show that the cost of this mixed-mode operation is on the same scale as the pure operation.

Many years of research on dependable, fault-tolerant software systems yielded a myriad of tool implementations for vulnerability analysis and experimental validation of resilience measures. Trace recording and fault injection are among the core functionalities these tools provide for hardware debuggers or system simulators, partially including some means to automate larger experiment campaigns. We argue that current fault-injection tools are too highly specialized for specific hardware devices or simulators, and are developed in poorly modularized implementations impeding evolution and maintenance. In this article, we present a novel design approach for a fault-injection infrastructure that allows experimenting researchers to switch simulator or hardware back ends with little effort, fosters experiment code reuse, and retains a high level of maintainability.

Event latency is considered to be one of the most important properties when selecting an event-driven real-time operating system. This is why in previous work on the Sloth kernel, we suggested treating threads as ISRs -- executing all application code in an interrupt context -- and thereby reducing event latencies by scheduling and dispatching solely in hardware. However, to achieve these benefits, Sloth does not support blocking threads or ISRs, but requires all control flows to have run-to-completion semantics. In this paper, we present Sleepy Sloth, an extension of Sloth that provides a new generalized thread abstraction that overcomes this limitation, while still letting the hardware do all scheduling and dispatching. Sleepy Sloth abolishes the (artificial) distinction between threads and ISRs: Threads can be dispatched as efficiently as interrupt handlers and interrupt handlers can be scheduled as flexibly as threads. Our Sleepy Sloth implementation of the automotive OSEK OS standard provides much more flexibility to application developers while maintaining efficient execution of application control flows. Sleepy Sloth runs on commodity off-the-shelf hardware and outperforms a leading commercial OSEK implementation by a factor of 1.3 to 19.

System software, especially operating systems, tends to be highly configurable. Like every complex piece of software, a considerable amount of bugs in the implementation has to be expected. In order to improve the general code quality, tools for static analysis provide means to check for source code defects without having to run actual test cases on real hardware. Still, for proper type checking a specific configuration is required so that all header include paths are available and all types are properly resolved.

The C Preprocessor (CPP) is the tool of choice for the implementation of variability in many large-scale configurable software projects. Linux, probably the most-configurable piece of software ever, employs more than 10,000 preprocessor variables for this purpose. However, this de-facto variability tends to be "hidden in the code"; which on the long term leads to variability defects, such as dead code or inconsistencies with respect to the intended (modeled) variability of the software. This calls for tool support for the efficient extraction of (and reasoning over) CPP-based variability.

Managing and developing a set of software products jointly using a software product line approach has achieved significant productivity and quality gain in the last decade. More and more, product lines now are becoming themselves entities that are sold and bought in the software supply chain. Customers build more specialized product lines on top of them or derive themselves the concrete products. As customers have different requirements, whole product lines now may vary depending on customer needs—they need to be customized. Current approaches going beyond the scope of one product line do not provide appropriate means for customization. They either are tailored to specific implementation techniques, only regard customization on few levels (e.g., only source code level), or imply a lot of manual effort for performing the customization.

A common problem in event-triggered real-time systems is caused by low-priority tasks that are implemented as interrupt handlers interrupting and disturbing high-priority tasks that are implemented as threads. This problem is termed rate-monotonic priority inversion, and current software-based solutions are restricted in terms of more sophisticated scheduler features as demanded for instance by the AUTOSAR embedded-operating-system specification.

Traditional operating systems differentiate between threads, which are managed by the kernel scheduler, and interrupt handlers, which are scheduled by the hardware. This approach is not only asymmetrical in its nature, but also introduces problems relevant to real-time systems because low-priority interrupt handlers can interrupt high-priority threads. We propose to internally design all threads as interrupts, thereby simplifying the managed control-flow abstractions and letting the hardware interrupt subsystem do most of the scheduling work. The resulting design of our very light-weight Sloth system is suitable for the implementation of a wide class of embedded real-time systems, which we describe with the example of the OSEK-OS specification. We show that the design conciseness has a positive impact on the system performance, its memory footprint, and its overall maintainability.

In theory, the expressive power of an aspect language should be independent of the aspect deployment approach, whether it is static or dynamic weaving. However, in the area of strictly statically typed and compiled languages, such as C or C++, there seems to be a feedback from the weaver implementation to the language level: dynamic aspect languages offer noticeable fewer features than their static counterparts. Especially means for generic aspect implementations are missing, as they are very difficult to implement in dynamic weavers. This hinders reusability of aspects and the application of AOP to scenarios where both, runtime and compile-time adaptation is required. Our solution to overcome these limitations is based on a novel combination of static and dynamic weaving techniques, which facilitates the support of typical static language features, such as generic advice, in dynamic weavers for compiled languages. In our implementation, the same AspectC++ aspect code can now be woven statically or dynamically into the Squid web proxy, providing flexibility and best of bread for many AOP-based adaptation scenarios.

We describe the implementation of memory protection by means of aspect-oriented programming (AOP) in CiAO, an AUTOSAR-like family of embedded operating systems. The use of AOP was originally motivated by the fact that memory protection is a cross-cutting policy, which, furthermore, has to be configurable at build-time in AUTOSAR. We learned, however, that besides switching between full protection and no protection, an AOP-based approach also makes it easy to apply completely different models of protection. For the domain of statically configured embedded systems, where certain failure scenarios can often be excluded by means of code analysis or even probability, this facilitates tailored and light-weight "pay-as-you-use" protection strategies.

Nearly ten years after its first presentation and five years after its first application to operating systems, the suitability of Aspect-Oriented Programming (AOP) for the development of operating system kernels is still highly in dispute. While the AOP advocacy emphasizes the benefits of AOP towards better configurability and maintainability of system software, most kernel developers express a sound skepticism regarding the thereby induced runtime and memory costs: Operating system kernels have to be lean and efficient.We have analyzed the runtime and memory costs of aspects in general, on the level of μ-benchmarks, and by refactoring and extending the eCos operating system kernel using AspectC++, an AOP extension to the C++ language. Our results show that most AOP features do not induce a intrinsic overhead and that the actual overhead induced by AspectC++ is very low. We have also analyzed a test case with significant aspect-related costs. This example shows how the structure of the underlying kernel can have a negative impact on aspect implementations and how these costs can be avoided by an aspect-aware design.Based on this analysis, our conclusion is that AOP is suitable for the development of operating system kernels and other kinds of highly efficient infrastructure software.