Graph-tree-based software control flow checking for COTS processors on pico-satellites

This paper proposes a generic high-performance and low-time-overhead software control flow checking solution, graph-tree-based control flow checking (GTCFC) for space-borne commercial-off-the-shelf (COTS) processors. A graph tree data structure with a topology similar to common trees is introduced to transform the control flow graphs of target programs. This together with design of IDs and signatures of its vertices and edges allows for an easy check of legality of actual branching during target program execution. As a result, the algorithm not only is capable of detecting all single and multiple branching errors with low latency and time overheads along with a linear-complexity space overhead, but also remains generic among arbitrary instruction sets and independent of any specific hardware. Tests of the algorithm using a COTS-processor-based on-board computer (OBC) of in-service ZDPS-1A pico-satellite products show that GTCFC can detect over 90% of the randomly injected and all-pattern-covering branching errors for different types of target programs, with performance and overheads consistent with the theoretical analysis; and beats well-established preeminent control flow checking algorithms in these dimensions. Furthermore, it is validated that GTCGC not only can be accommodated in pico-satellites conveniently with still sufficient system margins left, but also has the ability to minimize the risk of control flow errors being undetected in their space missions. Therefore, due to its effectiveness, efficiency, and compatibility, the GTCFC solution is ready for applications on COTS processors on pico-satellites in their real space missions.