Inverted Branches technique

The Inverted Branches technique (AZAMBUJA 2010a) was proposed to detect faults affecting the decision of branch instructions. Such errors affect the transition between different BBs and are hard to be detected, since both paths (branch taken or not taken) are acceptable in the program flow graph. The simplest way to protect such instmctions is to replicate the whole branch instraction, just like the Variables technique does with variables. 

In order to evaluate the Inverted Branches technique, four applications algorithms were chosen as case-studies a 6 x 6 matrix multiplication, a bubble sort, a bit count, and a Dijkstra. The matrix multiplication and the Dijkstra algorithms require large data processing with only a few loops and therefore uses mostly the data path of the processor. The bubble sort and the bit count algorithms, on the other hand, use... 

Table 4.2 Characteristics for the Inverted Branches technique program transformation...

OCFCM is expected to detect control flow faults that either causing the PC to freeze at the same memory address (through the watchdog) and the ones that break the sequential evolution of the PC with an inconsistent destination address. Unfortunately, these two cases do not comprehend all types of control flow errors. An incorrect decision, whether to take or not the branch, cannot be detected by the module. Therefore, a software-based side is required, with the Inverted Branches technique. 

One hardened program for each case study was generated using the HPCT and implementing HETA. Tables 4.8 and 4.9 show the overhead in execution time, code size, and data size for the matrix multiplication and bubble sort algorithms, respectively. They compare the original unhardened program with versions hardened by HETA and HETA combined with the Variables and Inverted Branches techniques (Combined Techniques). 

Following the state-of-the-art review, the next step is to implement fault tolerance techniques. We will start by explaining in detail and implementing two known software-based techniques, called Variables and Inverted Branches (AZAMBUJA 2010b), which will later be used as a complement to hybrid fault tolerance techniques. These techniques have been proposed in the past years and achieved high fault detection rates at low performance degradation levels and therefore are useful not only as an introduction to software-based fault tolerance techniques, but also to be combined with hardware-based and hybrid techniques. Then, three novel hybrid techniques will be proposed and implemented, based on both software and hardware replication characteristics. The three hybrid techniques will be divided into their software and hardware sides and described in detail, concerning both operation description and implementation. 

In the following sections, we will present the HPCT tool to automatically transform program codes into hardened ones, two known software-based techniques, called Variables and Inverted Branches, and three novel hybrid techniques to detect transient faults in embedded processors, named PODER, OCFCM, and HETA, combined with the previous known software-based techniques. 

The PODER technique is the first novel hybrid technique presented in this book. It was initially based in the CCA technique and its two-element queue to keep track of the changes in the program s control flow, called BID and CFID. The technique aims at detecting a few types of control flow errors, such as (1) incorrect jumps to the beginning of a BB, (2) incorrect jumps inside the same BB, (3) incorrect jumps to unused memory addresses, and (4) control flow loops. It is important to mention that PODER cannot detect errors in branch instructions, where a path should have been taken, but was not taken, and vice versa. In order to do so, it must be combined with the Inverted Branches software-based technique, described previously in Sect. 4.3. 

OCFCM itself is defined as a non-intrasive hardware module and therefore corrld be considered a pure hardware-based technique. Irrstead, OCFCM alone cannot achieve its main objective, which is detecting control flow errors. To do so, it has to be complemented by the Inverted Branches software-based technique (described in Sect. 4.3) and configured by the apphcation running in the processor. Because of these characteristics, it is considered as a hybrid farrlt tolerant technique, even if not as tightly coupled with the software-side as PODER. 

The software-based side on OCFCM is responsible for choosing which module will be active (when using a set of OCFCM) and performing the transformation on the software that implements the Inverted Branches software-based technique. It also has to guarantee that the program code does not use jumps with dynamic destina-... 

It is important to note that HETA, like PODER and OCFCM, cannot detect incorrect but legal jumps (according to the program graph). In order to do that, the Inverted Branches software-based technique, described in Sect. 4.3 is required. Also, HETA may present aliasing, when the program code has many BBs. With big apphcations, some signatures may start to repeat themselves and an error may not be detected by the technique. 

In order to perform the experiments presented in this Chapter, we implemented the miniMIPS hardened with the novel hybrid HETA technique and the software-based techniques Variables and Inverted Branches on both flash-based and SRAM-based FPGAs. We visited three facilities, used two types of energetio particles, and performed tests for SEE and TID. In the following, each radiation experiment and its results are diseussed in detail. 

To protect the path where the branch is taken, the technique starts by inserting a branch instmction in the original branch instmction destination address, but inverted and with its destination address modified to the error subroutine. It means that if the original branch was taken, the inverted replica must not be taken. If it is taken, the technique automatically flags an error through its new destination address, which is the error subroutine. 

---