research-article

Cross-Kernel Control-Flow--Graph Analysis for Event-Driven Real-Time Systems

Authors:

Christian Dietrich,

Martin Hoffmann,

Daniel LohmannAuthors Info & Claims

LCTES'15: Proceedings of the 16th ACM SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems 2015 CD-ROM

Article No.: 6, Pages 1 - 10

https://doi.org/10.1145/2670529.2754963

Published: 04 June 2015 Publication History

Abstract

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.

In this paper, we present an approach that incorporates the RTOS semantics into the control-flow analysis, to cross the application--kernel boundary. By combining operating system semantics, the static system configuration and the application logic, we determine 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, enables us to tailor the operating system kernel more closely to the particular application scenario. On the example of a real-world safety-critical control system, we present two possible use cases: Run-time optimizations, by means of specialized system calls for each call site, allow to speed up the kernel execution path by 33 percent in our benchmark scenario. An automated generation of OS state assertions on the expected system behavior, targeting transient hardware fault tolerance, leverages significant robustness improvements.

References

[1]

AUTOSAR. Specification of Operating System (Version 5.1.0). Tech. rep. Automotive Open System Architecture GbR, Feb. 2013.

[2]

Frances E. Allen. "Control Flow Analysis". In: SIGPLAN Not. 5.7 (July 1970), pp. 1--19. ISSN: 0362-1340.

Digital Library

[3]

Volker Barthelmann. "Inter-Task Register-Allocation for Static Operating Systems". In: Proceedings of the Joint Conference on Languages, Compilers and Tools for Embedded Systems (LCTES/SCOPES '02). (Berlin, Germany). New York, NY, USA: ACM, 2002, pp. 149--154. ISBN: 1-58113-527-0.

Digital Library

[4]

A Benso, S. Di Carlo, G. Di Natale, P. Prinetto, and L. Tagliaferri. "Control-flow checking via regular expressions". In: 10th Asian Test Symposium 2001 (ATS '01). (Kyoto, Japan). Washington, DC, USA: IEEE, 2001, pp. 299--303.

[5]

Ramon Bertran, Marisa Gil, Javier Cabezas, Victor Jimenez, Lluis Vilanova, Enric Morancho, and Nacho Navarro. "Building a Global System View for Optimization Purposes". In: W'shop on the Interaction between Operating Systems and Computer Architecture (SCAWIOSCA '06). (Boston, USA). Washington, DC, USA: IEEE, 2006.

[6]

Manfred Broy. "Challenges in Automotive Software Engineering". In: 28th Int. Conf. on Software Engineering (ICSE '06). (Shanghai, China). New York, NY, USA: ACM, 2006, pp. 33--42. ISBN: 1-59593-375-1.

Digital Library

[7]

Jim Cooling. Software Engineering for Real-Time Systems. AW, 2003. ISBN: 0-201-59620-2.

Digital Library

[8]

Christoph Erhardt, Michael Stilkerich, Daniel Lohmann, and Wolfgang Schröder-Preikschat. "Exploiting Static Application Knowledge in a Java Compiler for Embedded Systems: A Case Study". In: JTRES '11: 9th Int. W'shop on Java Technologies for real-time & embedded systems. (York, UK). New York, NY, USA: ACM, Sept. 2011, pp. 96-- 105. ISBN: 978-1-4503-0731-4.

Digital Library

[9]

Guidelines for the Use of the C Language in Critical Systems (MISRAC: 2004). Oct. 2004. ISBN: 0-9524156-2-3.

[10]

Martin Hoffmann, Florian Lukas, Christian Dietrich, and Daniel Lohmann. "dOSEK: The Design and Implementation of a Dependability-Oriented Static Embedded Kernel". In: 21st IEEE Int. Symp. on Real-Time and Embedded Technology and Applications (RTAS '15). Accepted. Washington, DC, USA: IEEE, 2015.

[11]

Yanhong Huang, Yongxin Zhao, Longfei Zhu, Qin Li, Huibiao Zhu, and Jianqi Shi. "Modeling and Verifying the Code-Level OSEK/VDX Operating System with CSP". In: 5th Int. Symp. on Theoretical Aspects of Software Engineering (TASE'11). (Xi'an, China). Washington, DC, USA: IEEE, 2011, pp. 142--149.

Digital Library

[12]

Kevin P. Lawton. "Bochs: A Portable PC Emulator for Unix/X". In: Linux Journal 1996.29es (1996), p. 7.

Digital Library

[13]

Thomas Lengauer and Robert Endre Tarjan. "A fast algorithm for finding dominators in a flowgraph". In: ACM Trans. Program. Lang. Syst. 1.1 (1979), pp. 121--141. ISSN: 0164-0925.

Digital Library

[14]

Peter Marwedel. Embedded System Design. Heidelberg, Germany: Springer, 2006.

Digital Library

[15]

Dylan McNamee, Jonathan Walpole, Calton Pu, Crispin Cowan, Charles Krasic, Ashvin Goel, Perry Wagle, Charles Consel, Gilles Muller, and Renauld Marlet. "Specialization Tools and Techniques for Systematic Optimization of System Software". In: ACM Trans. Comp. Syst. 19.2 (May 2001), pp. 217--251. ISSN: 0734-2071. URL: http://doi.acm.org/10.1145/377769.377778.

Digital Library

[16]

OSEK/VDX Group. OSEK Implementation Language Specification 2.5. Tech. rep. http://portal.osek-vdx.org/files/pdf/specs/oil25.pdf, visited 2014-09-29. OSEK/VDX Group, 2004.

[17]

OSEK/VDX Group. Operating System Specification 2.2.3. Tech. rep. http://portal.osek-vdx.org/files/pdf/specs/os223.pdf, visited 2014-09-29. OSEK/VDX Group, Feb. 2005.

[18]

N. Oh, P.P. Shirvani, and E.J. McCluskey. "Control-flow checking by software signatures". In: IEEE Transactions on Reliability 51.1 (2002), pp. 111--122. ISSN: 0018-9529.

[19]

Calton Pu, Henry Massalin, and John Ioannidis. "The Synthesis Kernel". In: Computing Systems 1.1 (1988), pp. 11--32.

[20]

Fabian Scheler and Wolfgang Schröder-Preikschat. "The RTSC: Leveraging the Migration from Event-Triggered to Time-Triggered Systems". In: 13th IEEE Int. Symp. on OO Real-Time Distributed Computing (ISORC '10). (Carmona, Spain). Washington, DC, USA: IEEE, May 2010, pp. 34--41. ISBN: 978-0-7695-4037-5.

Digital Library

[21]

Horst Schirmeier, Martin Hoffmann, Rüdiger Kapitza, Daniel Lohmann, and Olaf Spinczyk. "FAIL*: Towards a Versatile Fault-Injection Experiment Framework". In: 25th Int. Conf. on Architecture of Computing Systems (ARCS '12), Workshop Proceedings. (Munich, Germany). Ed. by Gero Mühl, Jan Richling, and Andreas Herkersdorf. Vol. 200. Lecture Notes in Informatics. Gesellschaft für Informatik, Mar. 2012, pp. 201--210. ISBN: 978-3-88579-294-9.

[22]

O. Shivers. "Control Flow Analysis in Scheme". In: ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI '88). (Atlanta, GA, USA). PLDI '88. New York, NY, USA: ACM, 1988, pp. 164--174. ISBN: 0-89791-269-1.

Digital Library

[23]

Libor Waszniowski and Zdenek Hanzálek. "Formal Verification of Multitasking Applications Based on Timed Automata Model". In: Real-Time Systems 38.1 (Jan. 2008), pp. 39--65. ISSN: 0922-6443.

Digital Library

[24]

S.S. Yau and Fu-Chung Chen. "An Approach to Concurrent Control Flow Checking". In: IEEE TOSE SE-6.2 (1980), pp. 126--137. ISSN: 0098-5589.

Digital Library

Cited By

Entrup GKässens AFiedler BLohmann D(2024)Applied static analysis and specialization of cross-core syscalls for multi-core AUTOSAR OSReal-Time Systems10.1007/s11241-024-09429-160:3(491-533)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s11241-024-09429-1
Entrup GFiedler BLohmann D(2023)MultiSSE: Static Syscall Elision and Specialization for Event-Triggered Multi-Core RTOS2023 IEEE 29th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS58335.2023.00028(262-275)Online publication date: May-2023
https://doi.org/10.1109/RTAS58335.2023.00028
McDonald BMueller F(2022)T-SYS: Timed-Based System Security for Real-Time Kernels2022 ACM/IEEE 13th International Conference on Cyber-Physical Systems (ICCPS)10.1109/ICCPS54341.2022.00029(247-258)Online publication date: May-2022
https://doi.org/10.1109/ICCPS54341.2022.00029
Show More Cited By

Index Terms

Cross-Kernel Control-Flow--Graph Analysis for Event-Driven Real-Time Systems
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Embedded systems
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
  2. Software organization and properties
    1. Software system structures
      1. Embedded software
      2. Real-time systems software

Recommendations

Global Optimization of Fixed-Priority Real-Time Systems by RTOS-Aware Control-Flow Analysis
Special Issue on LCETES 2015, Special Issue on ACSD 2015 and Special Issue on Embedded Devise Forensics and Security

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 ...
Cross-Kernel Control-Flow--Graph Analysis for Event-Driven Real-Time Systems
LCTES '15

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 ...
Sloth on Time: Efficient Hardware-Based Scheduling for Time-Triggered RTOS
RTSS '12: Proceedings of the 2012 IEEE 33rd Real-Time Systems Symposium

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 ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

LCTES'15: Proceedings of the 16th ACM SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems 2015 CD-ROM

June 2015

149 pages

ISBN:9781450332576

DOI:10.1145/2670529

General Chair:
Sam H. Noh
Hongik University, Republic of Korea
,
Program Chairs:
Sebastian Fischmeister
University of Waterloo, Canada
,
Jason Xue
City University of Hong Kong, China

ACM SIGPLAN Notices Volume 50, Issue 5
LCTES '15
May 2015
141 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2808704
Editor:
Andy Gill
University of Kansas, Lawrence, KS
Issue’s Table of Contents

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

LCTES'15

Sponsor:

LCTES'15: SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems 2015

June 18 - 19, 2015

OR, Portland, USA

Acceptance Rates

Overall Acceptance Rate 116 of 438 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
268
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)4

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Entrup GKässens AFiedler BLohmann D(2024)Applied static analysis and specialization of cross-core syscalls for multi-core AUTOSAR OSReal-Time Systems10.1007/s11241-024-09429-160:3(491-533)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s11241-024-09429-1
Entrup GFiedler BLohmann D(2023)MultiSSE: Static Syscall Elision and Specialization for Event-Triggered Multi-Core RTOS2023 IEEE 29th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS58335.2023.00028(262-275)Online publication date: May-2023
https://doi.org/10.1109/RTAS58335.2023.00028
McDonald BMueller F(2022)T-SYS: Timed-Based System Security for Real-Time Kernels2022 ACM/IEEE 13th International Conference on Cyber-Physical Systems (ICCPS)10.1109/ICCPS54341.2022.00029(247-258)Online publication date: May-2022
https://doi.org/10.1109/ICCPS54341.2022.00029
Perez DLe W(2021)Specifying Callback Control Flow of Mobile Apps Using Finite AutomataIEEE Transactions on Software Engineering10.1109/TSE.2019.289320747:2(379-392)Online publication date: 1-Feb-2021
https://doi.org/10.1109/TSE.2019.2893207
Schirmeier HBorchert CHoffmann MDietrich CMartens AKapitza RLohmann DSpinczyk O(2020)Dependability Aspects in Configurable Embedded Operating SystemsDependable Embedded Systems10.1007/978-3-030-52017-5_4(85-116)Online publication date: 10-Dec-2020
https://doi.org/10.1007/978-3-030-52017-5_4
Li TMa JPei QMa CWei DSun C(2019)Privacy-Preserving Verification and Root-Cause Tracing Towards UAV Social NetworksICC 2019 - 2019 IEEE International Conference on Communications (ICC)10.1109/ICC.2019.8761716(1-6)Online publication date: May-2019
https://doi.org/10.1109/ICC.2019.8761716
Li TMa JPei QShen YSun C(2018)Log-based Anomalies Detection of MANETs Routing with Reasoning and Verification2018 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC)10.23919/APSIPA.2018.8659549(240-246)Online publication date: Nov-2018
https://doi.org/10.23919/APSIPA.2018.8659549
Dietrich CLohmann D(2017)OSEK-V: application-specific RTOS instantiation in hardwareACM SIGPLAN Notices10.1145/3140582.308103052:5(111-120)Online publication date: 21-Jun-2017
https://dl.acm.org/doi/10.1145/3140582.3081030
Dietrich CLohmann DNagarajan VShao Z(2017)OSEK-V: application-specific RTOS instantiation in hardwareProceedings of the 18th ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3078633.3081030(111-120)Online publication date: 21-Jun-2017
https://dl.acm.org/doi/10.1145/3078633.3081030
Dietrich CHoffmann MLohmann D(2017)Global Optimization of Fixed-Priority Real-Time Systems by RTOS-Aware Control-Flow AnalysisACM Transactions on Embedded Computing Systems10.1145/295005316:2(1-25)Online publication date: 2-Jan-2017
https://dl.acm.org/doi/10.1145/2950053
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents