Instead of introducing extra hardware or
Instead of introducing extra hardware or hardware modification, software-based CFC techniques just insert extra checking instructions into the source code of the target program at compile time so as to have the target program do checking jobs itself. Preeminent software-based CFC techniques proposed in the recent and past years include software-based control flow checking (SCFC), graph-tree-based control flow checking (GTCFC), relationship signatures for control flow checking (RSCFC), yet another control flow checking using assertions (YACCA), control flow checking by software signatures (CFCSS) and enhanced control flow checking by assertions (ECCA) etc., which are listed in chronological order. All these techniques except CFCSS can detect all inter-node CFEs; they are useful in industrial environments but restrictive or impractical to small satellites. Details of their drawbacks are described as follows. Both SCFC and RSCFC employed an N-bit bitmap (represented as an integer) to store the successors for each basic block, where N is the total number of basic blocks in the target program. Each basic block is assigned an ID from 1 to N respectively and the basic block with ID i corresponds to the ith bit in the bitmap. The bitmap is effective in exploiting bit-level parallel operation. Nevertheless, in practice, N is usually larger than the word length of the processor (usually 8, 16 or 32), so that a bitmap consists of multiple registers, then a single operation on the bitmap decomposes to multiple operations on registers, which increases the time and memory overhead. GTCFC, which claimed to be dedicated for pico-satellites, introduced virtual basic blocks for the basic blocks that have multiple predecessors to ensure that each basic block has only one predecessor, and introduced an array to store the predecessors for each (virtual) basic block. The array occupies a linear memory space, which is considerable for resource constrained small satellites. The inserted checking instructions in virtual basic blocks consume extra time and memory. Moreover, Ampicillin Trihydrate access in the array needs indirect addressing, which is the slowest one among addressing modes of processors. Thus, GTCFC is restrictive to small satellites. YACCA and ECCA represent predecessors of each basic block as the product P of their IDs, and then expose CFEs by checking the divisibility of P and divided-by-zero exception respectively. In practice, P may be a big integer and exceed the word length, so the operation and storage may lead to extra time and memory overhead. Furthermore, multiplication and division will cause a huge performance decay for processors without multipliers like ADuC841, which is adopted by ZDPS-1A pico-satellite.16, 17 Thus, YACCA and ECCA may be time and memory consuming in practice. CFCSS performed simple XOR and AND operations at the beginning of each basic block to check CFEs, so spores has a low time and memory overhead. However, the detection rate is low due to the lack of checking instructions at the end of basic blocks and the aliasing problem. To overcome the drawbacks of previous techniques in small satellite applications, we propose a generic high-performance and low-overhead SCFC technique named bipartite graph-based control flow checking (BGCFC). BGCFC partitions the target program into basic blocks and builds its control flow graph as previous techniques.10, 11, 12, 13, 14, 15 A conventional basic block consists of a cluster of instructions, and the illegal jump can start from or end at any instruction of the basic block. So illegal branches, start from or end at the beginning, inside and end of the basic block are different. To simplify illegal branches, BGCFC transforms the control flow graph into an equivalent bipartite graph by splitting each basic block into two sub-blocks, so that only illegal branches between sub-blocks need to be handled. BGCFC employs a bitmap to store the predecessors of each basic block in the corresponding bits as SCFC and RSCFC. However, because usually one basic block has only a few predecessors, storing all basic blocks in a single bitmap causes most bits in the bitmap wasted. Hence, BGCFC only stores the predecessors of the basic block with multiple predecessors into the bitmap to reduce the length. Furthermore, to increase the storage density of the bitmap, BGCFC assigns IDs to predecessors of each basic block as consecutive as possible. Along with the execution of the target program, BGCFC does check at each sub-blocks by merely performing XOR, AND, SUB and SHIFT operations, which are the fastest among the instruction set and ubiquitous in processors. BGCFC inherits the advantages of SCFC, RSCFC and CFCSS, and overcomes their shortages. As a result, BGCFC is not only capable of detecting all inter-node CFEs with low time and memory overhead, but also generic among arbitrary COTS processors, and independent of any specific hardware. Consequently, BGCFC is applicable and useful in COTS-based small satellites.