Document Open Access Logo

Low-Overhead Online Assessment of Timely Progress as a System Commodity

Authors Weifan Chen , Ivan Izhbirdeev, Denis Hoornaert , Shahin Roozkhosh , Patrick Carpanedo, Sanskriti Sharma, Renato Mancuso

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2023.13.pdf
  • Filesize: 1.39 MB
  • 26 pages

Document Identifiers

Author Details

Weifan Chen
  • Boston University, MA, USA
Ivan Izhbirdeev
  • Boston University, MA, USA
Denis Hoornaert
  • Technische Universität München, Germany
Shahin Roozkhosh
  • Boston University, MA, USA
Patrick Carpanedo
  • Boston University, MA, USA
Sanskriti Sharma
  • Boston University, MA, USA
Renato Mancuso
  • Boston University, MA, USA

Funding

  • Hoornaert, Denis: Denis Hoornaert was supported by the Chair for Cyber-Physical Systems in Production Engineering at TUM and the Alexander von Humboldt Foundation.
  • Mancuso, Renato: The material presented in this paper is based upon work supported by the National Science Foundation (NSF) under grants number CCF-2008799 and CNS-2238476.

Cite As Get BibTex

Weifan Chen, Ivan Izhbirdeev, Denis Hoornaert, Shahin Roozkhosh, Patrick Carpanedo, Sanskriti Sharma, and Renato Mancuso. Low-Overhead Online Assessment of Timely Progress as a System Commodity. In 35th Euromicro Conference on Real-Time Systems (ECRTS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 262, pp. 13:1-13:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ECRTS.2023.13

Abstract

The correctness of safety-critical systems depends on both their logical and temporal behavior. Control-flow integrity (CFI) is a well-established and understood technique to safeguard the logical flow of safety-critical applications. But unfortunately, no established methodologies exist for the complementary problem of detecting violations of control flow timeliness. Worse yet, the latter dimension, which we term Timely Progress Integrity (TPI), is increasingly more jeopardized as the complexity of our embedded systems continues to soar. As key resources of the memory hierarchy become shared by several CPUs and accelerators, they become hard-to-analyze performance bottlenecks. And the precise interplay between software and hardware components becomes hard to predict and reason about. How to restore control over timely progress integrity? We postulate that the first stepping stone toward TPI is to develop methodologies for Timely Progress Assessment (TPA). TPA refers to the ability of a system to live-monitor the positive/negative slack - with respect to a known reference - at key milestones throughout an application’s lifespan. In this paper, we propose one such methodology that goes under the name of Milestone-Based Timely Progress Assessment or MB-TPA, for short. Among the key design principles of MB-TPA is the ability to operate on black-box binary executables with near-zero time overhead and implementable on commercial platforms. To prove its feasibility and effectiveness, we propose and evaluate a full-stack implementation called Timely Progress Assessment with 0 Overhead (TPAw0v). We demonstrate its capability in providing live TPA for complex vision applications while introducing less than 0.6% time overhead for applications under test. Finally, we demonstrate one use case where TPA information is used to restore TPI in the presence of temporal interference over shared memory resources.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
Keywords
  • progress-aware regulation
  • hardware assisted runtime monitoring
  • timing annotation
  • control flow graph

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Powertrace iii. https://www.lauterbach.com/powertrace3.html. Accessed: 01-03-2023.
  2. Technology overview. https://www.ghs.com/products/probe.html. Accessed: 01-03-2023.
  3. Uprobe-tracer: Uprobe-based event tracing. URL: https://docs.kernel.org/trace/uprobetracer.html.
  4. Working draft of the risc-v processor trace specification. https://github.com/riscv-non-isa/riscv-trace-spec. Accessed: 01-03-2023.
  5. Jaume Abella, Carles Hernandez, Eduardo Quiñones, Francisco J. Cazorla, Philippa Ryan Conmy, Mikel Azkarate-askasua, Jon Perez, Enrico Mezzetti, and Tullio Vardanega. Wcet analysis methods: Pitfalls and challenges on their trustworthiness. In 10th IEEE International Symposium on Industrial Embedded Systems (SIES), pages 1-10, 2015. URL: https://doi.org/10.1109/SIES.2015.7185039.
  6. Seyed Mohammad Ali Zeinolabedin, Johannes Partzsch, and Christian Mayr. Analyzing arm coresight etmv4.x data trace stream with a real-time hardware accelerator. In 2021 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 1606-1609, 2021. URL: https://doi.org/10.23919/DATE51398.2021.9474035.
  7. ARM. Coresight components technical reference manual, 2004. URL: https://developer.arm.com/documentation/ddi0314/h/.
  8. ARM. CoreSight trace memory controller technical reference manual, 2010. URL: https://developer.arm.com/documentation/ddi0461/b/.
  9. ARM. AMBA ATB Protocol Specification, 2012. URL: https://developer.arm.com/documentation/ihi0032.
  10. ARM. Embedded trace macrocell architecture specification etmv4.0 to etm4.6, 2012. URL: https://developer.arm.com/documentation/ihi0064/h/?lang=en.
  11. ARM. Arm architecture reference manual for a-profile architecture, 2013. URL: https://developer.arm.com/documentation/ddi0487/latest.
  12. ARM. ARM CoreSight SoC-400 Technical Reference Manual, 2015. URL: https://developer.arm.com/Processors/CoreSight%20SoC-400.
  13. S. Baruah, V. Bonifaci, G. DAngelo, H. Li, A. Marchetti-Spaccamela, S. van der Ster, and L. Stougie. The preemptive uniprocessor scheduling of mixed-criticality implicit-deadline sporadic task systems. In 24th Euromicro Conference on Real-Time Systems (ECRTS 2012), pages 145-154, Los Alamitos, CA, USA, July 2012. IEEE Computer Society. URL: https://doi.org/10.1109/ECRTS.2012.42.
  14. S.K. Baruah, A. Burns, and R.I. Davis. Response-time analysis for mixed criticality systems. In 2011 IEEE 32nd Real-Time Systems Symposium, pages 34-43, 2011. URL: https://doi.org/10.1109/RTSS.2011.12.
  15. Andrea Bastoni, Björn B. Brandenburg, and James H. Anderson. Cache-related preemption and migration delays : Empirical approximation and impact on schedulability. In Proceedings of the 6th annual workshop on. Operating Systems Platforms for Embedded Real-Time Applications, volume 10 of OSPERT'10, pages 33-44, 2010. Google Scholar
  16. Emiliano Betti, Stanley Bak, Rodolfo Pellizzoni, Marco Caccamo, and Lui Sha. Real-time i/o management system with cots peripherals. IEEE Transactions on Computers, 62(1):45-58, 2013. URL: https://doi.org/10.1109/TC.2011.202.
  17. Reinder J. Bril, Sebastian Altmeyer, Martijn M. H. P. van den Heuvel, Robert I. Davis, and Moris Behnam. Fixed priority scheduling with pre-emption thresholds and cache-related pre-emption delays: integrated analysis and evaluation. Real-Time Systems, 53(4):403-466, July 2017. URL: https://doi.org/10.1007/s11241-016-9266-z.
  18. Alan Burns and Robert Ian Davis. Mixed Criticality Systems - A Review (13th Edition, February 2022). Universities of Leeds, Sheffield and York, February 2022. URL: https://eprints.whiterose.ac.uk/183619/.
  19. M. Caccamo, G. Buttazzo, and Lui Sha. Elastic feedback control. In Proceedings 12th Euromicro Conference on Real-Time Systems. Euromicro RTS 2000, pages 121-128, 2000. URL: https://doi.org/10.1109/EMRTS.2000.853999.
  20. Hugues Cassé and Pascal Sainrat. OTAWA, a Framework for Experimenting WCET Computations. In Conference ERTS'06, Toulouse, France, January 2006. URL: https://hal.science/hal-02270434.
  21. Intel Corp. Intel 64 and IA-32 Architectures Software Developer’s Manual Volume 3 (3A, 3B, 3C & 3D): System Programming Guide, 2022. URL: https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html.
  22. Edsger W Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269-271, 1959. Google Scholar
  23. Peter Dinges and Gul Agha. Targeted test input generation using symbolic-concrete backward execution. In Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering, ASE '14, pages 31-36, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2642937.2642951.
  24. Pontus Ekberg and Wang Yi. Outstanding paper award: Bounding and shaping the demand of mixed-criticality sporadic tasks. In 2012 24th Euromicro Conference on Real-Time Systems, pages 135-144, 2012. URL: https://doi.org/10.1109/ECRTS.2012.24.
  25. Lang Feng, Jeff Huang, Jiang Hu, and Abhijith Reddy. Fastcfi: Real-time control-flow integrity using fpga without code instrumentation. ACM Trans. Des. Autom. Electron. Syst., 26(5), June 2021. URL: https://doi.org/10.1145/3458471.
  26. Robert Gifford, Neeraj Gandhi, Linh Thi Xuan Phan, and Andreas Haeberlen. DNA: Dynamic resource allocation for soft real-time multicore systems. In 27th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS '21), May 2021. URL: https://doi.org/10.1109/RTAS52030.2021.00024.
  27. Giovani Gracioli, Ahmed Alhammad, Renato Mancuso, Antônio Augusto Fröhlich, and Rodolfo Pellizzoni. A survey on cache management mechanisms for real-time embedded systems. ACM Comput. Surv., 48(2), November 2015. URL: https://doi.org/10.1145/2830555.
  28. Xiaozhe Gu and Arvind Easwaran. Dynamic budget management with service guarantees for mixed-criticality systems. In 2016 IEEE Real-Time Systems Symposium (RTSS), pages 47-56, 2016. URL: https://doi.org/10.1109/RTSS.2016.014.
  29. Xiaozhe Gu, Arvind Easwaran, Kieu-My Phan, and Insik Shin. Resource efficient isolation mechanisms in mixed-criticality scheduling. In 2015 27th Euromicro Conference on Real-Time Systems, pages 13-24, 2015. URL: https://doi.org/10.1109/ECRTS.2015.9.
  30. Jan Gustafsson. Usability aspects of WCET analysis. In 2008 11th IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing (ISORC), pages 346-352, 2008. URL: https://doi.org/10.1109/ISORC.2008.55.
  31. Damien Hardy, Benjamin Rouxel, and Isabelle Puaut. The Heptane Static Worst-Case Execution Time Estimation Tool. In Jan Reineke, editor, 17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017), volume 57 of OpenAccess Series in Informatics (OASIcs), pages 8:1-8:12, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/OASIcs.WCET.2017.8.
  32. Augusto Hoppe, Jürgen Becker, and Fernanda Lima Kastensmidt. High-speed hardware accelerator for trace decoding in real-time program monitoring. In 2021 IEEE 12th Latin America Symposium on Circuits and System (LASCAS), pages 1-4, 2021. URL: https://doi.org/10.1109/LASCAS51355.2021.9459137.
  33. Tai-Yi Huang, J.W.-S. Liu, and D. Hull. A method for bounding the effect of DMA I/O interference on program execution time. In 17th IEEE Real-Time Systems Symposium, pages 275-285, 1996. URL: https://doi.org/10.1109/REAL.1996.563724.
  34. Marine Kadar, Gerhard Fohler, Don Kuzhiyelil, and Philipp Gorski. Safety-aware integration of hardware-assisted program tracing in mixed-criticality systems for security monitoring. In 2021 IEEE 27th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 292-305, 2021. URL: https://doi.org/10.1109/RTAS52030.2021.00031.
  35. Raimund Kirner and Peter P. Puschner. Discussion of misconceptions about WCET analysis. In Jan Gustafsson, editor, Proceedings of the 3rd International Workshop on Worst-Case Execution Time Analysis, WCET 2003 - A Satellite Event to ECRTS 2003, Polytechnic Institute of Porto, Portugal, July 1, 2003, volume MDH-MRTC-116/2003-1-SE, pages 61-64. Department of Computer Science and Engineering, Mälardalen University, Box 883, 721 23 Västerås, Sweden, 2003. Google Scholar
  36. Angeliki Kritikakou, Thibaut Marty, and Matthieu Roy. Dynascore: Dynamic software controller to increase resource utilization in mixed-critical systems. ACM Trans. Des. Autom. Electron. Syst., 23(2), October 2017. URL: https://doi.org/10.1145/3110222.
  37. Angeliki Kritikakou, Claire Pagetti, Olivier Baldellon, Matthieu Roy, and Christine Rochange. Run-time control to increase task parallelism in mixed-critical systems. In 2014 26th Euromicro Conference on Real-Time Systems, pages 119-128, 2014. URL: https://doi.org/10.1109/ECRTS.2014.14.
  38. Angeliki Kritikakou, Christine Rochange, Madeleine Faugère, Claire Pagetti, Matthieu Roy, Sylvain Girbal, and Daniel Gracia Pérez. Distributed run-time WCET controller for concurrent critical tasks in mixed-critical systems. In Proceedings of the 22nd International Conference on Real-Time Networks and Systems, RTNS '14, pages 139-148, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2659787.2659799.
  39. Don Kuzhiyelil, Philipp Zieris, Marine Kadar, Sergey Tverdyshev, and Gerhard Fohler. Towards transparent control-flow integrity in safety-critical systems. In International Conference on Information Security, pages 290-311. Springer, 2020. Google Scholar
  40. Chang-Gun Lee, Hoosun Hahn, Yang-Min Seo, Sang Lyul Min, Rhan Ha, Seongsoo Hong, Chang Yun Park, Minsuk Lee, and Chong Sang Kim. Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. IEEE Transactions on Computers, 47(6):700-713, 1998. URL: https://doi.org/10.1109/12.689649.
  41. Jaewoo Lee, Hoon Sung Chwa, Linh T. X. Phan, Insik Shin, and Insup Lee. Mc-adapt: Adaptive task dropping in mixed-criticality scheduling. ACM Trans. Embed. Comput. Syst., 16(5s), September 2017. URL: https://doi.org/10.1145/3126498.
  42. Di Liu, Jelena Spasic, Nan Guan, Gang Chen, Songran Liu, Todor Stefanov, and Wang Yi. Edf-vd scheduling of mixed-criticality systems with degraded quality guarantees. In 2016 IEEE Real-Time Systems Symposium (RTSS), pages 35-46, 2016. URL: https://doi.org/10.1109/RTSS.2016.013.
  43. Daniel Lo, Mohamed Ismail, Tao Chen, and G. Edward Suh. Slack-aware opportunistic monitoring for real-time systems. In 2014 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 203-214, 2014. URL: https://doi.org/10.1109/RTAS.2014.6926003.
  44. Chenyang Lu, John A. Stankovic, Sang H. Son, and Gang Tao. Feedback control real-time scheduling: Framework, modeling, and algorithms. Real-Time Systems, 23(1):85-126, July 2002. URL: https://doi.org/10.1023/A:1015398403337.
  45. Tamara Lugo, Santiago Lozano, Javier Fernández, and Jesus Carretero. A survey of techniques for reducing interference in real-time applications on multicore platforms. IEEE Access, 10:21853-21882, 2022. URL: https://doi.org/10.1109/ACCESS.2022.3151891.
  46. Mingsong Lv, Zonghua Gu, Nan Guan, Qingxu Deng, and Ge Yu. Performance comparison of techniques on static path analysis of wcet. In 2008 IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, volume 1, pages 104-111, 2008. URL: https://doi.org/10.1109/EUC.2008.178.
  47. Mingsong Lv, Nan Guan, Jan Reineke, Reinhard Wilhelm, and Wang Yi. A survey on static cache analysis for real-time systems. Leibniz Transactions on Embedded Systems, 3(1):05:1-05:48, June 2016. URL: https://doi.org/10.4230/LITES-v003-i001-a005.
  48. C. Maiza, H. Rihani, J. Rivas, J. Goossens, S. Altmeyer, and R. Davis. A Survey of Timing Verification Techniques for Multi-Core Real-Time Systems. ACM Comput. Surv., 52(3), June 2019. URL: https://doi.org/10.1145/3323212.
  49. R. Mancuso, R. Dudko, E. Betti, M. Cesati, M. Caccamo, and R. Pellizzoni. Real-time cache management framework for multi-core architectures. In 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 45-54, 2013. Google Scholar
  50. Hemendra Singh Negi, Tulika Mitra, and Abhik Roychoudhury. Accurate estimation of cache-related preemption delay. In Proceedings of the 1st IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis, CODES+ISSS '03, pages 201-206, New York, NY, USA, 2003. Association for Computing Machinery. URL: https://doi.org/10.1145/944645.944698.
  51. Mattia Nicolella, Denis Hoornaert, Shahin Roozkhosh, Andrea Bastoni, and Renato Mancuso. Know your enemy: Benchmarking and experimenting with insight as a goal. In 2022 IEEE Real-Time Systems Symposium (RTSS), RTSS 2022, 2022. URL: https://cs-people.bu.edu/rmancuso/files/papers/RTBench_RTSS22.pdf.
  52. Mattia Nicolella, Shahin Roozkhosh, Denis Hoornaert, Andrea Bastoni, and Renato Mancuso. Rt-bench: An extensible benchmark framework for the analysis and management of real-time applications. In Proceedings of the 30th International Conference on Real-Time Networks and Systems, RTNS 2022, pages 184-195, New York, NY, USA, 2022. Association for Computing Machinery. URL: https://doi.org/10.1145/3534879.3534888.
  53. Alessandro Papadopoulos, Enrico Bini, Sanjoy Baruah, and Alan Burns. Adaptmc: A control-theoretic approach for achieving resilience in mixed-criticality systems. In Sebastian Altmeyer, editor, Proceeding ECRTS Conference, pages 14:1-14:22, Dagstuhl, July 2018. LIPICS. URL: https://eprints.whiterose.ac.uk/133393/.
  54. J. Ren and L. Xuan Phan. Mixed-criticality scheduling on multiprocessors using task grouping. In 2015 27th Euromicro Conference on Real-Time Systems (ECRTS), pages 25-34, Los Alamitos, CA, USA, July 2015. IEEE Computer Society. URL: https://doi.org/10.1109/ECRTS.2015.10.
  55. Gero Schwaricke, Rohan Tabish, Rodolfo Pellizzoni, Renato Mancuso, Andrea Bastoni, Alexander Zuepke, and Marco Caccamo. A real-time virtio-based framework for predictable inter-vm communication. In 2021 IEEE Real-Time Systems Symposium (RTSS), pages 27-40, 2021. URL: https://doi.org/10.1109/RTSS52674.2021.00015.
  56. Hardik Shah, Kai Huang, and Alois Knoll. Timing anomalies in multi-core architectures due to the interference on the shared resources. In 2014 19th Asia and South Pacific Design Automation Conference (ASP-DAC), pages 708-713, 2014. URL: https://doi.org/10.1109/ASPDAC.2014.6742973.
  57. Yan Shoshitaishvili, Ruoyu Wang, Christopher Salls, Nick Stephens, Mario Polino, Audrey Dutcher, John Grosen, Siji Feng, Christophe Hauser, Christopher Kruegel, and Giovanni Vigna. SoK: (State of) The Art of War: Offensive Techniques in Binary Analysis. In IEEE Symposium on Security and Privacy, 2016. Google Scholar
  58. Soham Sinha, Richard West, and Ahmad Golchin. Pastime: Progress-aware scheduling for time-critical computing. arXiv preprint, 2019. URL: https://arxiv.org/abs/1908.06211.
  59. Parul Sohal, Rohan Tabish, Ulrich Drepper, and Renato Mancuso. E-warp: A system-wide framework for memory bandwidth profiling and management. In 2020 IEEE Real-Time Systems Symposium (RTSS), pages 345-357, 2020. URL: https://doi.org/10.1109/RTSS49844.2020.00039.
  60. J.A. Stankovic, Chenyang Lu, S.H. Son, and Gang Tao. The case for feedback control real-time scheduling. In Proceedings of 11th Euromicro Conference on Real-Time Systems. Euromicro RTS'99, pages 11-20, 1999. URL: https://doi.org/10.1109/EMRTS.1999.777445.
  61. Dharmesh Tarapore, Shahin Roozkhosh, Steven Brzozowski, and Renato Mancuso. Observing the invisible: Live cache inspection for high-performance embedded systems. IEEE Transactions on Computers, 71(3):559-572, 2022. URL: https://doi.org/10.1109/TC.2021.3060650.
  62. Prathap Kumar Valsan, Heechul Yun, and Farzad Farshchi. Taming non-blocking caches to improve isolation in multicore real-time systems. In 2016 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 1-12, 2016. URL: https://doi.org/10.1109/RTAS.2016.7461361.
  63. Sravanthi Kota Venkata, Ikkjin Ahn, Donghwan Jeon, Anshuman Gupta, Christopher Louie, Saturnino Garcia, Serge Belongie, and Michael Bedford Taylor. SD-VBS: The san diego vision benchmark suite. In 2009 IEEE International Symposium on Workload Characterization (IISWC), pages 55-64, 2009. URL: https://doi.org/10.1109/IISWC.2009.5306794.
  64. Xilinx. Zynq UltraScale+ Device Technical Reference Manual, 2023. URL: https://docs.xilinx.com/r/en-US/ug1085-zynq-ultrascale-trm/Components.
  65. H. Yun, R. Mancuso, Z. P. Wu, and R. Pellizzoni. PALLOC: DRAM bank-aware memory allocator for performance isolation on multicore platforms. In 2014 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 155-166, 2014. Google Scholar
  66. Heechul Yun, Gang Yao, Rodolfo Pellizzoni, Marco Caccamo, and Lui Sha. Memguard: Memory bandwidth reservation system for efficient performance isolation in multi-core platforms. In 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 55-64, 2013. URL: https://doi.org/10.1109/RTAS.2013.6531079.
  67. Matteo Zini, Giorgiomaria Cicero, Daniel Casini, and Alessandro Biondi. Profiling and controlling I/O-related memory contention in COTS heterogeneous platforms. Software: Practice and Experience, 52(5):1095-1113, 2022. URL: https://doi.org/10.1002/spe.3053.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact