Total Execution Order in Fault-Tolerant Real-Time Systems

Many real-time systems nowadays must not only tolerate accidental faults but also targeted attacks. Typically, techniques such as replication and diversification are used to mask the malicious behavior of compromised nodes behind a healthy majority. This work focuses on the replication of event-triggered real-time systems, where prioritized tasks are scheduled non-preemptively on nodes. In such systems, different execution times of replicated jobs on different nodes may lead to their different execution order and different state transitions on nodes. Total order protocols can be used to coordinate nodes to execute jobs in the same order. Previously published total order approaches do not meet all the requirements of real-time systems as a malicious node can inject priority inversion on other nodes in such a way that healthy nodes can no longer guarantee the timely completion of jobs. In this paper, we propose a novel coordination algorithm to detect and tolerate such attacks. In our approach, once jobs are inserted into the ready queues, nodes can proceed with their execution within a bound without further communication until the next release. This bound is updated over time, allowing more jobs from the ready queue to be executed. Upon task release, nodes use reliable communication to share their progress, so they insert the released jobs in the same position in their queues. Nodes evaluate each other’s progress before inserting jobs to verify that scheduling bounds have been respected and to detect any priority inversion injection attacks. We evaluate our approach and show that it can guarantee the schedulability of more task sets than other published total order protocols and exhibit low average response times at reasonable run-time overheads.