CN107301123A - A kind of signature arithmetic code error detection algorithm of table- driven - Google Patents

Abstract

The invention discloses a table-driven signature error detection algorithm. The algorithm is based on the theory of finite state automata (FSM), stores the information of the control flow graph in a two-dimensional table (CFID table), and compares the signatures in the basic blocks and the signature stored in the CFID table detects illegal instruction jumps. For the illegal instruction jump errors of shared branch fan-in nodes that cannot be detected by the CFCSS algorithm, the present invention can successfully detect such errors. Experimental results show that the average error detection coverage rate of the present invention reaches 98.1%, and the present invention inserts fewer error detection instructions in each basic block than that in CFCSS.

Description

A Table-Driven Signature Error Detection Algorithm

technical field

The present invention relates to the technical field of pure software error detection, specifically a table-driven signature error detection algorithm (EDSS), which is applied to legal branches, illegal branches and illegal branches with two shared branch fan-in nodes etc. error detection.

Background technique

As technology develops, improvements in microprocessor performance will increasingly rely on smaller, faster transistors while achieving low threshold voltages and tighter noise margins. However, this general need to improve performance and reduce power consumption often leads to many reliability problems. Unlike frequent errors such as manufacturing and design errors, temporary errors (also often referred to as soft errors), resulting from environmental effects such as electromagnetic interference, voltage glitches, or high-energy particles, often lead to unpredictable behavior . The most typical soft error is single event upset (SEU), which refers to bit flips that occur in sequential logic and single event transients (SET). The first and most important step in tolerating these errors is to detect these errors , there are quite a few error detection techniques.

Error detection can be realized by pure hardware, combination of software and hardware, and pure software. A common hardware-only approach to error detection uses a watchdog coprocessor that monitors the behavior of external buses and the host processor to enable concurrent system-level error detection, but results in increased time and area overhead. Large, and with the widespread use of microprocessors with internal caches and modern pipeline technology, this pure hardware error detection method has become unnecessary. There are also many mixed software and hardware error detection methods for error detection, such as Argus and CRAFT. Argus is based on the von Neumann processor core, which can detect other errors in the core except input and output, exception and interrupt. However, including control flow inspection through pure software signatures (CFCSS), control flow inspection through assertions (ACFC), enhanced control flow inspection using assertions (ECCA), error detection through redundant instructions (EDDI), etc. The pure software processing methods in the system are more widely used than the above two concepts, because these pure software error detection methods do not require specific hardware devices to provide support. ACFC assigns a parity bit to each basic block during execution, which can detect parity errors; EDDI verifies by copying instructions and inserting appropriate detection instructions, but this method easily leads to an increase in code capacity by nearly 100% and loss of performance.

Contents of the invention

The object of the present invention is to provide a table-driven signature error detection algorithm EDSS, which can detect illegal jump errors in the control flow diagram by using CFID tables, and the requirements for the use of two-dimensional tables are relatively simple. When an illegal jump occurs, control flow errors can be reliably detected by checking the signature assigned to the variable Reg and the signature of the target node stored in the table. According to this method, illegal instruction jump errors caused by sharing more than two fan-in nodes can also be detected by the algorithm. This algorithm well solves the problem of error detection of legal branches, illegal branches and illegal branches with fan-in nodes of two shared branches.

The purpose of the present invention is achieved like this:

A table-driven signature error detection algorithm is characterized in that the detection algorithm includes the following specific steps:

Step 1: Determine all basic blocks, that is, nodes, establish a control flow graph of program P, number each node, that is, the basic block identification number, and start with a natural number in the control flow graph, namely vi, i=1, 2.... N;

Step 2: Assign a signature SSi to each node vi, if i≠j, then SSi≠SSj, where i, j=1, 2,...N; each signature SSi and the corresponding basic block identify i in vi equal;

Step 3: For each vi,i=1,2,3..., do the following:

a) For each branch bri,j, its predecessor node is vi, and its successor node is vj; these branches are represented by a two-dimensional table called CFID[i,j]; in this table, the row i represents the predecessor node, column j represents the successor node;

b) If the branch bri,j is in the control flow graph, fill the signature SSj of the successor node into the position corresponding to CFID[i,j]; otherwise, the position of CFID[i,j] should be filled with 0;

c) The global variable stored in the Reg register is updated every time the basic block executes its detection instruction, so as to track the change of the signature during program execution;

d) Insert a judgment instruction at the initial position of the basic block, "if SSi≠CFID[Reg,SSi] error elseReg=SSi", that is to judge whether SSi is equal to CFID[Reg,SSi], if they are equal, assign SSi to Reg, if not equal, report an error.

The two-dimensional table is a two-dimensional array, and the value corresponding to row i and column j is CFID[i,j], which represents the position identifier and jump path in the control flow; the row value i represents the identification number of the predecessor node , the column value j represents the identification number of the current node;

The basic block refers to a series of continuous instructions, and the program starts to execute from the first instruction in the basic block, and leaves the basic block after executing the last instruction; except that the last instruction in the basic block is not required, The remaining instructions in the basic block are not allowed to be branch instructions, jump instructions or call instructions.

The control flow graph is composed of a node set V={v1,v2,...,vi,...vn} and a path set E={e1,e2,...,ei,...,em}, and the control flow graph accurately describes the program P Control flow, that is, the program P is expressed as P={V,E}; a node vi represents a basic block, where i is a positive integer, indicating the position of the basic block in the program; a path represents the branch bri from vi to vj, j; bri, j represents a branch instruction, a jump instruction, a subroutine call instruction or a return instruction.

The present invention proposes a table-driven signature error detection algorithm on the basis of the control flow error detection method (CFCSS) through software signature. The algorithm is based on the finite state automata theory (FSM), stores the information of the control flow graph in a two-dimensional table (CFID table), and detects illegal instruction jumps by comparing the signature in the basic block with the signature stored in the CFID table change. For the illegal instruction jump errors of shared branch fan-in nodes that cannot be detected by the CFCSS algorithm, the present invention (EDSS algorithm) can successfully detect such errors.

On the basis of CFCSS, the present invention combines the basic principles of finite state automaton theory (FSM) and control flow graph, which is completely different from the method previously used in CFCSS. When compiling, the information in the control flow graph, including the relationship between nodes, is expressed by constructing a two-dimensional CFID table. The table stores the signature of the target node in the legal path of the control flow graph. When an illegal jump occurs, control flow errors can be reliably detected by checking the signature assigned to the variable Reg and the signature of the target node stored in the table.

Beneficial effects of the present invention:

The invention uses the CFID table to detect illegal jump errors in the control flow diagram, and the requirements for the use of the two-dimensional table are relatively simple.

The advantage of the present invention lies in its succinctness. In the detection instruction, there is no need to calculate the dynamic signature by a bitwise XOR operation instruction, but only need to perform a comparison operation on each basic block.

The invention can realize error detection of legal branches, illegal branches, illegal branches with two shared branch fan-in nodes, and the like.

While typical reliable systems require hardware techniques to locate temporary errors, pure software techniques offer lower cost and more flexible options. The technology proposed by the invention is a pure software error detection technology, which uses a two-dimensional table and a signature to monitor the control flow of the target program. When the program is compiled, each basic block is given an integer value signature with different values, and these signatures are stored in the corresponding positions of the corresponding basic block and a two-dimensional table. Through the comparison of these signatures, the system can detect any abnormal situation in the control flow graph (CFG), and can take appropriate measures to avoid the output of erroneous results.

Compared with the existing CFCSS error detection technology, the present invention solves the problem of illegal jump of two or more shared fan-in nodes that cannot be detected by the CFCSS algorithm without increasing code space overhead and having less impact on program performance , improving the coverage of control flow error detection. The average error detection coverage rate of the present invention is 98.1% (1.3% higher than the CFCSS technology), and the number of instructions inserted for error detection in each basic block is relatively less.

Description of drawings

Fig. 1 is the detection schematic diagram of legal instruction jump among the present invention;

Fig. 2 is the detection schematic diagram of illegal instruction jump among the present invention;

FIG. 3 is a schematic diagram of detection of illegal instruction jumps of two shared branch fan-in nodes in the present invention;

Fig. 4 is the error detection coverage comparison figure of the present invention and CFCSS;

FIG. 5 is a comparison diagram of the error detection capabilities of CFCSS and the present invention in the multi-fan-in node problem in the present invention.

detailed description

The present invention will be described in detail below in conjunction with the accompanying drawings.

Accompanying drawing 1 is the detection of the allowed execution branch without shared fan-in nodes, and all basic blocks in the figure have been identified and numbered. As shown on the left side of FIG. 1 , each basic block is assigned a different value that is equal to its own position identifier. The right side of accompanying drawing 1 shows how the detection instruction performs error detection. When the program executes to v3, the comparison of SS3 with CFID[Reg, SS3] shall be performed first before proceeding to execute the instructions in v3. Reg is a global variable used to store dynamic signatures, which are stored in allocated registers. If the equality relationship between SS3 and CFID[Reg, SS3] is established, that is, if brReg,3 is a legal branch, Reg will be updated to SS3, and the original instructions in the basic block will continue to be executed until the program execution reaches Next basic block v6. The next comparison of SS6 with CFID[Reg, SS6] is performed as in the previous basic block. If brReg,6 is an illegal branch, the value corresponding to CFID[Reg,SS6] must be 0 instead of SS6, the error statement is executed, and the control flow error is detected.

Figure 2 shows the execution of an illegal jump instruction and how the error is detected. The control flow error in this case can be divided into two cases: one is an illegal jump pointing to the if conditional statement; the other is an illegal jump pointing to the middle of the next basic block. Before the illegal jump br1,4 is executed, Reg has the original value SS1. In the former case, when the program executes to the if statement of v4, CFID[Reg,SS4] is read from the two-dimensional CFID table stored in the cache, and since br1,4 is not allowed, CFID [Reg, SS4] corresponds to 0. Therefore, this mismatch causes the following "error" instruction to transfer control flow to the error handler.

In the latter case, the illegal jump to the middle part of the basic block can also be detected under the present invention (EDSS algorithm). But because the branch skips the v4 test instruction, the test is delayed. An illegal jump from v1 to v4 occurs, and program control is transferred to an instruction in v4. Reg keeps the signature in v1 unchanged until the program runs to v7 after executing the instructions in v4. Obviously, in this case, the corresponding value of CFID[Reg,v7] is 0, which is different from SS7, so the conditional branch instruction "if SS7≠CFID[Reg,SS7] error else Reg=SS7" should jump to error handling program.

Figure 3 shows a situation where multiple nodes share multiple branch fan-in nodes as target nodes. The problem of instruction jump confusion is prone to occur under the CFCSS technology, but the present invention (EDSS algorithm) provides a simple solution for it and avoids the occurrence of the confusion problem. In the accompanying drawing 3, v7 is a branch fan-in node with 3 precursor nodes v3, v4, v5 (pred(v7)={v3,v4,v5}). According to the algorithm of the present invention, SS7 is filled in CFID[3,7], CFID[4,7] and CFID[5,7] respectively. Node v8 is also a branch fan-in node, but there are only two precursor nodes v4, v5, excluding v3, that is, pred(v8)={v4, v5}. Therefore, SS8 is stored in both CFID[4,8] and CFID[5,8], while 0 is stored in CFID[3,8]. The program-allowed jump instructions br4,7, br5,8 are detected and executed in the same manner as shown in FIG. 2 . Assume that an illegal jump br3,8 occurs, and executes to the detection instruction position of v8, where CFID[Reg,8] is compared with SS8. The value of Reg before the execution of the illegal jump is SS3, and the corresponding value of CFID[3,8] in the two-dimensional CFID table is 0, so the control flow error is detected. If the illegal instruction branch points to the target Control flow errors generated in basic blocks other than if-else detection instructions can also be detected through the global variable Reg that has not been updated in v8. From this point of view, as long as each node is given a signature and the two-dimensional CFID table of the present invention (EDSS algorithm) is established, the newly generated illegal command jump error that cannot be detected in the CFCSS can be avoided.

Similar to the algorithm design of CFCSS, the present invention (EDSS algorithm) is more concise and efficient in comparison. There are no instructions embedded in nodes to compute signatures at runtime dynamically, and likewise, there are no redundant instructions to adjust signatures on the fly. When a program is compiled, the present invention assigns a signature to each node in the program control flow diagram, and N is equal to the total number of nodes in the program.

Figure 4 shows that the present invention (EDSS algorithm) has the same error detection coverage as CFCSS, so it can be seen that the present invention has the same error detection capability as CFCSS and meets the requirements of error detection.

Accompanying drawing 5 shows the comparison in the code space overhead that the algorithm increases, and the present invention (EDSS algorithm) is better than CFCSS. In terms of signature calculation, the present invention does not require inserting instructions for calculating dynamic signatures in the program, which reduces the number of inserted instructions correspondingly. In this respect, the CFCSS technology sets 3 instructions for each basic block, but the present invention only sets 2 instructions for each basic block.

The protection content of the present invention is not limited to the above embodiments. Without departing from the spirit and scope of the inventive concept, changes and advantages conceivable by those skilled in the art are all included in the present invention, and the appended claims are the protection scope.

Claims (4)

1. the signature arithmetic code error detection algorithm of a kind of table- driven, it is characterised in that the detection algorithm includes step in detail below：

Step 1：All basic blocks, i.e. node are determined, program P controlling stream graph is set up, is each node serial number, i.e. basic block Identification number, is started in controlling stream graph with natural number, i.e. vi, i=1,2 ... .N；

Step 2：A signature SSi is assigned to each node vi, if i ≠ j, SSi ≠ SSj, wherein i, j=1,2 ... N；Each signature SSi is equal with the i in corresponding basic block identification vi；

Step 3：To each vi, i=1,2,3 ..., proceed as follows：

a）To each branch bri, j, its predecessor node is vi, and descendant node is vj；These branches are by a bivariate table Represent, the bivariate table is referred to as CFID [i, j]；In the table, row i represents predecessor node, and row j represents descendant node；

b）If branch bri, j are in controlling stream graph, the signature SSj of descendant node is inserted into the corresponding positions of CFID [i, j]； Otherwise CFID [i, j] position should insert 0 value；

c）The global variable stored in Reg registers basic block perform each time its detection instruction when all updates once, with The change signed in track program process；

d）A decision instruction is inserted in the initial position of basic block, judges whether SSi and CFID [Reg, SSi] is equal, if It is equal, then SSi is assigned to Reg, if unequal, reported an error.

2. detection algorithm according to claim 1, it is characterised in that the bivariate table is a two-dimensional array, correspondence i rows Numerical value on j column positions is CFID [i, j], represents the station location marker in controlling stream and redirects path；Line number value i represents forerunner The identification number of node, columns value j represents the identification number of present node.

3. detection algorithm according to claim 1, it is characterised in that the basic block refers to a string of continuous instructions, Program is performed since first instruction in basic block, and basic block is left after the last item instruction has been performed；Except basic The last item instruction in block does not require outer, remaining instruction in basic block do not allow for branch instruction, jump instruction or Person's call instruction.

4. detection algorithm according to claim 1, it is characterised in that the controlling stream graph by node set V=v1, V2 ..., vi ... vn } and set of paths E={ e1, e2 ..., ei ..., em } compositions, controlling stream graph accurate description program P control Stream, i.e. program P is expressed as P={ V, E }；One node vi represents a basic block, and wherein i is positive integer, represents basic block in journey Position in sequence；One paths represent the branch bri from vi to vj, j；Bri, j represent branch instruction, jump instruction, subprogram Call instruction or return instruction.