TL;DR
Autonomous systems like self-driving cars need to be both functionally correct and temporally precise. This paper introduces "Data-flow Availability" (DFA), a new concept to ensure these systems meet their timing expectations by analyzing data flow. They built Kairos, a system that automatically detects and mitigates timing violations, significantly improving safety and predictability with minimal overhead.
What Problem Does This Paper Address?
Autonomous cyber-physical systems (CPS) are increasingly integrated into our lives, from self-driving cars to home robots. These systems interact with the physical world and must not only perform computations correctly but also do so within strict time constraints. Ensuring this "temporal correctness" is crucial for safety and reliability. While theoretical foundations for real-time computing exist, applying them in practice to complex CPS is challenging for developers, often requiring deep domain expertise. Existing systems frequently suffer from timing bugs, where the system's internal state (cyber) becomes misaligned with the real-world state (physical) due to timing issues. This paper aims to bridge the gap between theoretical real-time computing and practical CPS development by providing a more accessible and effective way to achieve timing assurance.
Methods
The authors introduce Data-flow Availability (DFA) as a novel concept to achieve timing assurance. DFA models timing expectations as constraints on data flows within a system.
- Timed Data-flow Graph (TDFG): They extend the concept of data-flow graphs to include a temporal dimension. Each data element is tagged with a timestamp, and the flow of data is governed by timing constraints defined on the edges of the graph.
- Key Temporal Properties: DFA focuses on three core temporal properties:
- Freshness: The latency between a physical event and its representation in the cyber system.
- Consistency: The temporal alignment of data from different sources converging at a point in the system.
- Stability: The variation in freshness or consistency over time (akin to jitter).
- Kairos System: To realize DFA, they designed and implemented Kairos, a system with two main components:
- DFA-embedding Tool: This component, integrated into the build process, constructs the TDFG and instruments the application code to detect timing constraint violations at runtime. Developers can manually annotate code with APIs or use dynamic profiling to specify temporal properties.
- Cross-layer Scheduling Infrastructure: When a timing violation is detected, Kairos employs a handler to mitigate it. This infrastructure bridges semantic gaps between different system layers (kernel, middleware, application) to coordinate schedulers for effective violation handling. They propose three policies:
abort(discarding the task),prioritize(raising task priority), andskip-next(skipping the next instance).
Datasets
The paper does not explicitly mention training datasets. For evaluation, they used:
- Real-world autonomous systems:
- Autoware.Auto (full-stack autonomous driving)
- Jackal UGV (mid-end autonomous system)
- Turtlebot3 (low-end indoor robot)
- Synthetic workloads: Used for scalability analysis.
- Existing bug studies: The paper's methodology is informed by a systematic study of 189 timing bugs found in 7 open-source CPS projects.
Key Insights and Ideas
- Data Flow as the Key: The core insight is that timing issues in CPS often stem from misalignments in the flow of data between cyber and physical components. Focusing on data flow provides a more intuitive and practical way to define and enforce timing requirements than traditional task-centric approaches.
- Three Pillars of Temporal Correctness: Identifying freshness, consistency, and stability as the fundamental temporal properties simplifies the problem space and provides a clear framework for defining timing constraints.
- Bridging Abstraction Layers: A significant challenge in timing enforcement is the disconnect between different system layers. Kairos's cross-layer scheduling infrastructure is crucial for effectively mitigating violations by coordinating actions across the entire system stack.
- Developer-Friendly Approach: By providing APIs and leveraging dynamic profiling, DFA and Kairos aim to make timing assurance more accessible to developers without deep real-time systems expertise.
Key Results
- Bug Fixability: Out of 189 timing bugs analyzed, 116 could be detected by DFA, and 76 could be mitigated directly by Kairos's default policies. 35 required customized handlers, and 23 were out of scope (infrastructure, design, or hardware issues).
- Runtime Overhead: Kairos introduces a minimal average runtime overhead of 2.8%. The overhead is generally proportional to the complexity of the task's TDFG (number of edges).
- Performance Under Overload: Kairos demonstrates faster and more stable response times in reacting to timing violations compared to ROS, ERDOS, and ghOSt, especially under high system overload.
- Safety Improvement: In abnormal timing situations (simulated by CPU overload), Kairos significantly reduces control deviations and the number of collisions. For example, it reduced collisions by 64.4% on Autoware and 83.3% on Jackal UGV.
- Reduced Programming Effort: Kairos simplifies the process of specifying timing constraints by removing the need for manual timestamp assignment and checks, reducing developer effort.
Limitations and Future Work
- Manual Annotation Effort: While Kairos offers dynamic profiling, manual annotation can still be time-consuming and requires developer guidance. The search space for identifying where to apply constraints is large.
- System Component Interdependency: Kairos relies on seamless collaboration across multiple scheduling layers. Failures or complexities in one layer can impact the entire system, and migrating to new platforms might require substantial engineering.
- Expressing Traditional Primitives: The authors suggest that DFA could be extended to more directly express traditional real-time computing primitives like execution time constraints and synchronization primitives, allowing developers to leverage existing real-time theory.
- Sophisticated Policies: Developing more sophisticated temporal violation handling policies beyond the current
abort,prioritize, andskip-nextis an area for future research. - Generality: While DFA is designed for CPS, its concept of imposing temporal expectations on data flow could be applied to other domains like distributed systems and data centers.
Summary updated