Abstract
Cyber-physical systems (CPS) are typically implemented as a set of real-time control tasks with periodic activation. When a control task misses it’s deadline, policies for handling deadline miss – e.g. delayed scheduling of the task instance – may still lead the CPS into an unsafe or sub-optimal state. We present a technique for exact checking of such control safety and reachability properties, for a class of CPS, under common deadline miss handling and control update policies. In particular, we propose a joint encoding of control and scheduling behaviour as a satisfiability-modulo-theory formulation and a novel abstraction-refinement procedure with incremental solving to scale the analysis. Case studies with realistic systems show the utility of our approach.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
While our method can be adapted to handle preemptions, we focus on NP scheduling for ease of presentation and leave the extension as future work.
- 2.
We assume a time-triggered hardware implementation of sensing/actuation, outside the scheduling purview, with values stored in buffers accessed by the control task.
- 3.
Under NP-RM, priority (period) must be higher (lower): \(P_i \le P_{i'} ~\vee ~ s^i_j < r^{i'}_{j'}\).
- 4.
Under NP-RM, this is \(P^{i'}<P^i\).
References
Abate, A., et al.: Automated formal synthesis of digital controllers for state-space physical plants. In: Majumdar, R., Kunčak, V. (eds.) CAV 2017. LNCS, vol. 10426, pp. 462–482. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63387-9_23
Bjørner, N., Phan, A., Fleckenstein, L.: \(\nu \)z - an optimizing SMT solver. In: TACAS, pp. 194–199 (2015)
Dai, X., Burns, A.: Period adaptation of real-time control tasks with FP scheduling in cyber-physical systems. J. Syst. Arch. 103, 101691 (2020)
Dai, X., Zhao, S., Jiang, Y., Jiao, X., Hu, X.S., Chang, W.: Fixed-priority scheduling and controller co-design for time-sensitive networks. In: CAV (2020)
Frehse, G., Hamann, A., Quinton, S., Woehrle, M.: Formal analysis of timing effects on closed-loop properties of control software. In: RTSS, pp. 53–62 (2014)
Frehse, G., et al.: SpaceEx: scalable verification of hybrid systems. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol. 6806, pp. 379–395. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22110-1_30
Gabel, R.A., Roberts, R.A.: Signals and Linear Systems, 2nd edn. Wiley, Hoboken (1980)
Hobbs, C., Ghosh, B., Xu, S., Duggirala, P.S., Chakraborty, S.: Safety analysis of embedded controllers under implementation platform timing uncertainties, IEEE TCAD (2022). (To appear)
Lunniss, W., Altmeyer, S., Davis, R.: Comparing FP and EDF accounting for cache related pre-emption delays. Leibniz Trans. Emb. Syst. 1(1), 01:1–01:24 (2014)
Maggio, M., Hamann, A., Mayer-John, E., Ziegenbein, D.: Control system stability under consecutive deadline misses. In: ECRTS, vol. 165, pp. 21:1–21:24 (2020)
Messner, W., Tilbury, D.: Control Tutorials for MATLAB and Simulink: A Web-Based Approach. Addison-Wesley (1999)
Minaeva, A., Roy, D., Akesson, B., Hanzálek, Z., Chakraborty, S.: Control performance optimization for application integration. In: IEEE ToC (2021)
Murphy, K.N.: Analysis of robotic vehicle steering and controller delay (1994)
O’Kelly, M., Zheng, H., Karthik, D., Mangharam, R.: F1tenth: an evaluation environment for continuous control and reinforcement learning. In: NeurIPS (2019)
Pazzaglia, P., Pannocchi, L., Biondi, A., Natale, M.D.: Beyond the weakly hard model: cost of deadline misses. In: ECRTS, vol. 106, pp. 10:1–10:22 (2018)
Roy, D., Ghosh, S., Zhu, Q., Caccamo, M., Chakraborty, S.: GoodSpread: criticality-aware static scheduling of CPS with multi-QoS. In: RTSS, pp. 178–190 (2020)
Roy, D., Hobbs, C., Anderson, J.H., Caccamo, M., Chakraborty, S.: Timing debugging for cyber-physical systems. In: DATE, pp. 1893–1898 (2021)
Vreman, N., Cervin, A., Maggio, M.: Stability and performance analysis of control systems subject to deadline misses. In: ECRTS, vol. 196, pp. 15:1–15:23 (2021)
Vreman, N., Mandrioli, C., Anton, C.: Deadline-miss-adaptive controller implementation for real-time control systems. In: RTAS (2022)
Vreman, N., Mandrioli, C.: Evaluation of burst failure robustness of control systems in the fog. In: Workshop on Fog-IoT. OASIcs, Schloss Dagstuhl (2020)
Zhang, L., Lu, P., Kong, F., Chen, X., Sokolsky, O., Lee, I.: Real-time attack-recovery for CPS using linear-quadratic regulator. ACM TECS 20(5s), 1–24 (2021)
Acknowledgement
Hobbs and Chakraborty were funded by NSF grant 2038960.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Yeolekar, A., Metta, R., Hobbs, C., Chakraborty, S. (2022). Checking Scheduling-Induced Violations of Control Safety Properties. In: Bouajjani, A., Holík, L., Wu, Z. (eds) Automated Technology for Verification and Analysis. ATVA 2022. Lecture Notes in Computer Science, vol 13505. Springer, Cham. https://doi.org/10.1007/978-3-031-19992-9_7
Download citation
DOI: https://doi.org/10.1007/978-3-031-19992-9_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-19991-2
Online ISBN: 978-3-031-19992-9
eBook Packages: Computer ScienceComputer Science (R0)