Bipartite graph-based control flow checking for COTS-based small satellites

Abstract Single event upset （SEU） effect, caused by highly energized particles in aerospace, threatens the reliability and security of small satellites composed of commercialofftheshelves （COTS）. SEU induced control flow errors （CFEs） may cause unpredictable behavior or crashes of COTSbased small satellites. This paper proposes a generic softwarebased control flow checking technique （CFC） and bipartite graphbased control flow checking （BGCFC）. To simplify the types of illegal branches, it transforms the conventional control flow graph into the equivalent bipartite graph. It checks the legal ity of control flow at runtime by comparing a global signature with the expected value and introduces consecutive IDs and bitmaps to reduce the time and memory overhead. Theoretical analysis shows that BGCFC can detect all types of internode CFEs with constant time and memory overhead. Practical tests verify the result of theoretical analysis. Compared with previous techniques, BGCFC achieves the highest error detection rate, lower time and memory overhead; the composite result in evaluation fac tor shows that BGCFC is the most effective one among all these techniques. The results in both theory and practice verify the applicability of BGCFC for COTSbased small satellites.

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 onboard 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.