Abstract
The reliable operation of systems with both timing and energy requirements is a fundamental challenge in the area of safety-critical embedded systems. In order to provide guarantees for the execution of tasks within given resource budgets, these systems demand bounds of the worst-case execution time (WCET) and the worst-case energy consumption (WCEC). While static WCET analysis techniques are well established in the software development process of real-time systems nowadays, these program analysis techniques are not directly applicable to the fundamentally different behavior of energy consumption and the determination of the WCEC. Besides the missing approaches for WCEC bounds, the domain of worst-case analyses generally faces the problem that the accuracy and validity of reported analysis bounds are unknown: Since the actual worst-case resource consumption of existing benchmark programs cannot be automatically determined, a comprehensive validation of these program analysis tools is not possible.
This summary of my dissertation addresses these problems by first describing a novel program analysis approach for WCEC bounds, which accounts for temporarily power-consuming devices, scheduling with fixed real-time priorities, synchronous task activations, and asynchronous interrupt service routines. Regarding the fundamental problem of validating worst-case tools, this dissertation presents a technique for automatically generating benchmark programs. The generator combines program patterns so that the worst-case resource consumption is available along with the generated benchmark. Knowledge about the actual worst-case resource demand then serves as the baseline for evaluating and validating program analysis tools. The fact the benchmark generator helped to reveal previously undiscovered software bugs in a widespread WCET tool for safety-critical systems underlines the relevance of such a structured testing technique.
Chapter PDF
Similar content being viewed by others
References
AbsInt: aiT WCET analyzers. https://www.absint.com/ait/
Bachmann, O., Wang, P.S., Zima, E.V.: Chains of recurrences—a method to expedite the evaluation of closed-form functions. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC ’94), pp. 1–8 (1994)
Chu, D.H., Jaffar, J.: Symbolic simulation on complicated loops for WCET path analysis. In: Proceedings of the 9th International Conference on Embedded Software (EMSOFT ’11), pp. 319–328 (2011)
Cohen, A. et al.: Inter-disciplinary research challenges in computer systems for the 2020s. Tech. rep., USA (2018)
Dietrich, C., Wägemann, P., Ulbrich, P., Lohmann, D.: SysWCET: Whole-system response-time analysis for fixed-priority real-time systems. In: Proceedings of the 23nd Real-Time and Embedded Technology and Applications Symposium (RTAS ’17), pp. 37–48 (2017)
Eichler, C., Distler, T., Ulbrich, P., Wägemann, P., Schröder-Preikschat, W.: TASKers: A whole-system generator for benchmarking real-time-system analyses. In: Proceedings of the 18th International Workshop on Worst-Case Execution Time Analysis (WCET ’18), pp. 6:1–6:12 (2018)
Eichler, C., Wägemann, P., Schröder-Preikschat, W.: GenEE: a benchmark generator for static analysis tools of energy-constrained cyber-physical systems. In: Proceedings of the 2nd Workshop on Benchmarking Cyber-Physical Systems and Internet of Things (CPS-IoTBench ’19) (2019)
Falk, H., Altmeyer, S., Hellinckx, P., Lisper, B., Puffitsch, W., Rochange, C., Schoeberl, M., Sørensen, R., Wägemann, P., Wegener, S.: TACLeBench: a benchmark collection to support worst-case execution time research. In: Proceedings of the 16th International Workshop on Worst-Case Execution Time Analysis (WCET ’16), pp. 1–10 (2016)
Gustafsson, J., Betts, A., Ermedahl, A., Lisper, B.: The Mälardalen WCET benchmarks: Past, present and future. In: Proceedings of the 10th International Workshop on Worst-Case Execution Time Analysis (WCET ’10), pp. 137–147 (2010)
Huber, B., Prokesch, D., Puschner, P.: Combined WCET analysis of bitcode and machine code using control-flow relation graphs. In: Proceedings of the 14th Conference on Languages, Compilers and Tools for Embedded Systems (LCTES ’13), pp. 163–172 (2013)
Kashyap, V., Ruchti, J., Kot, L., Turetsky, E., Swords, R., Pan, S.A., Henry, J., Melski, D., Schulte, E.: Automated customized bug-benchmark generation. In: Proceedings of the 19th International Working Conference on Source Code Analysis and Manipulation (SCAM ’19), pp. 103–114 (2019)
Knoop, J., Kovács, L., Zwirchmayr, J.: WCET squeezing: On-demand feasibility refinement for proven precise WCET-bounds. In: Proceedings of the 21st Conference on Real-Time Networks and Systems (RTNS ’13), pp. 161–170 (2013)
Lattner, C., Adve, V.: LLVM: A compilation framework for lifelong program analysis & transformation. In: Proceedings of the International Symposium on Code Generation and Optimization (CGO ’04), pp. 75–86 (2004)
Li, Y.T.S., Malik, S.: Performance analysis of embedded software using implicit path enumeration. In: ACM SIGPLAN Notices, vol. 30, pp. 88–98 (1995)
McCabe, T.J.: A complexity measure. IEEE Trans. Softw. Eng. 4, 308–320 (1976)
Ouyang, H., Liu, Z., Li, N., Shi, B., Zou, Y., Xie, F., Ma, Y., Li, Z., Li, H., Zheng, Q., Qu, X., Fan, Y., Wang, Z.L., Zhang, H., Li, Z.: Symbiotic cardiac pacemaker. Nat. Commun. 10, 1821 (2019)
Pallister, J., Kerrison, S., Morse, J., Eder, K.: Data dependent energy modeling for worst case energy consumption analysis. In: Proceedings of the 20th International Workshop on Software and Compilers for Embedded Systems (SCOPES ’17), pp. 51–59 (2017)
Puschner, P., Prokesch, D., Huber, B., Knoop, J., Hepp, S., Gebhard, G.: The T-CREST approach of compiler and WCET-analysis integration. In: Proceedings of the 9th Workshop on Software Technologies for Future Embedded and Ubiquitious Systems (SEUS ’13), pp. 33–40 (2013)
Raffeck, P., Eichler, C., Wägemann, P., Schröder-Preikschat, W.: Worst-case energy-consumption analysis by microarchitecture-aware timing analysis for device-driven cyber-physical systems. In: Proceedings of the 19th International Workshop on Worst-Case Execution Time Analysis (WCET ’19), pp. 6:1–6:12 (2019)
Rice, H.G.: Classes of recursively enumerable sets and their decision problems. Trans. Am. Math. Soc. 74(2), 358–366 (1953)
Scheler, F.: Atomic Basic Blocks: Eine Abstraktion für die gezielte Manipulation der Echtzeitsystemarchitektur. Ph.D. Thesis, Friedrich-Alexander-Universität Erlangen-Nürnberg, Technische Fakultät (2011)
Scheler, F., Schröder-Preikschat, W.: The real-time systems compiler: migrating event-triggered systems to time-triggered systems. Softw. Practice Exp. 41(12), 1491–1515 (2011)
Sieh, V., Burlacu, R., Hönig, T., Janker, H., Raffeck, P., Wägemann, P., Schröder-Preikschat, W.: An end-to-end toolchain: from automated cost modeling to static WCET and WCEC analysis. In: Proceedings of the 20th International Symposium on Real-Time Distributed Computing (ISORC ’17), pp. 1–10 (2017)
Wägemann, P., Dietrich, C., Distler, T., Ulbrich, P., Schröder-Preikschat, W.: Whole-system WCEC analysis for energy-constrained real-time systems (artifact). Dagstuhl Artifacts Series 4(2), 7:1–7:4 (2018)
Wägemann, P., Dietrich, C., Distler, T., Ulbrich, P., Schröder-Preikschat, W.: Whole-system worst-case energy-consumption analysis for energy-constrained real-time systems. In: Proceedings of the 30th Euromicro Conference on Real-Time Systems (ECRTS ’18), vol. 106, pp. 24:1–24:25. Dagstuhl (2018)
Wägemann, P., Distler, T., Eichler, C., Schröder-Preikschat, W.: Benchmark generation for timing analysis. In: Proceedings of the 23rd Real-Time and Embedded Technology and Applications Symposium (RTAS ’17), pp. 319–330 (2017)
Wägemann, P., Distler, T., Hönig, T., Janker, H., Kapitza, R., Schröder-Preikschat, W.: Worst-case energy consumption analysis for energy-constrained embedded systems. In: Proceedings of the 27th Euromicro Conference on Real-Time Systems (ECRTS ’15), pp. 105–114. IEEE, Piscataway (2015)
Wägemann, P., Distler, T., Hönig, T., Sieh, V., Schröder-Preikschat, W.: GenE: A benchmark generator for WCET analysis. In: Proceedings of the 15th International Workshop on Worst-Case Execution Time Analysis (WCET ’15), vol. 47, pp. 33–43 (2015)
Wägemann, P., Distler, T., Janker, H., Raffeck, P., Sieh, V.: A kernel for energy-neutral real-time systems with mixed criticalities. In: Proceedings of the 22nd Real-Time and Embedded Technology and Applications Symposium (RTAS ’16), pp. 25–36 (2016)
Wägemann, P., Distler, T., Janker, H., Raffeck, P., Sieh, V., Schröder-Preikschat, W.: Operating energy-neutral real-time systems. ACM Trans. Embedded Comput. Syst. 17(1), 11:1–11:25 (2018)
Wägemann, P., Distler, T., Raffeck, P., Schröder-Preikschat, W.: Towards code metrics for benchmarking timing analysis. In: Proceedings of the 37th Real-Time Systems Symposium Work-in-Progress Session (RTSS WiP ’16) (2016)
Wilhelm, R. et al.: The worst-case execution-time problem—overview of methods and survey of tools. ACM Trans. Embedded Comput. Syst. 7(3), 1–53 (2008)
Wägemann, P.: Energy-constrained real-time systems and their worst-case analyses. Ph.D. Thesis, Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU) (2020). https://nbn-resolving.org/urn:nbn:de:bvb:29-opus4-146935
Yang, X., Chen, Y., Eide, E., Regehr, J.: Finding and understanding bugs in C compilers. In: Proceedings of the 32nd Conference on Programming Language Design and Implementation (PLDI ’11), pp. 283–294 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2022 The Author(s)
About this chapter
Cite this chapter
Wägemann, P. (2022). Static Worst-Case Analyses and Their Validation Techniques for Safety-Critical Systems. In: Felderer, M., et al. Ernst Denert Award for Software Engineering 2020. Springer, Cham. https://doi.org/10.1007/978-3-030-83128-8_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-83128-8_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-83127-1
Online ISBN: 978-3-030-83128-8
eBook Packages: Computer ScienceComputer Science (R0)