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

作　　者：Wang Honghao Wang Huiquan Jin Zhonghe 

机构地区：[1]Micro-satellite Research Center, Zhejiang University

出　　处：《Chinese Journal of Aeronautics》2015年第3期883-893,共11页中国航空学报（英文版）

基　　金：support from the National Natural Science Foundation of China;the Fundamental Research Funds for the Central Universities of China

摘　　要：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.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.

关 键 词：Bipartite graph Control flow checking Commercial-off-the-shelves（COTS） Error injection Fault tolerant Illegal branch Small satellites 

分 类 号：V448.2[航空宇航科学与技术—飞行器设计]