# A software control flow checking technique in multi-core processors

Mohammad Reza Heidari Iman, Yaghmaie Pejman

► To cite this version:

Mohammad Reza Heidari Iman, Yaghmaie Pejman. A software control flow checking technique in multi-core processors. International Journal of Embedded Systems, 2020, 13 (2), pp.136-147. hal-04867925

HAL Id: hal-04867925

https://hal.science/hal-04867925v1

Submitted on 6 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
# A software control flow checking technique in multi-core processors

## Mohammad Reza Heidari Iman*

Faculty of Engineering,
Ferdowsi University of Mashhad,
Mashhad, Iran
Email: mohammadreza.heidari@mail.um.ac.ir
*Corresponding author

## Pejman Yaghmaie

Faculty of Engineering,
Tarbiat Modares University,
Tehran, Iran
Email: yaghmaie.p@modares.ac.ir

**Abstract:** Multi-core processors can benefit performance, power consumption and level of parallelism, which is the primary reason why they are employed in safety-critical embedded systems. Nowadays the use of safety-critical multi-core embedded systems in different industries is growing significantly. In these systems, an error may result in a severe failure which can lead to disaster. In order to prevent such failure, the fault tolerance of the systems should be improved. Some of the important errors, which can cause failures, are the control flow errors changing the execution flow of a multi-core program and eventually leading to core failure. To detect them, different control flow checking techniques have been proposed, almost all of which have so far aimed to detect errors in single-core processors. In this paper, a software control flow checking technique in multi-core processors, called SCFC-MC, has been proposed wherein, in addition to executing the program, each thread monitors the execution flow of another thread, thereby eliminating every single point of failure. Experimental results show that applying SCFC-MC to a quad-core processor [Intel(R) Core(TM) i7-4710HQ] results in the detection of about 95% of control flow errors with less than 20% performance overhead.

**Keywords:** fault tolerance; multi-core processors; control flow errors; CFEs; software control flow checking techniques; SCFC-MC technique; safety-critical embedded systems.

**Reference** to this paper should be made as follows: Iman, M.R.H. and Yaghmaie, P. (2020) 'A software control flow checking technique in multi-core processors', *Int. J. Embedded Systems*, Vol. 13, No. 2, pp.136–147.

**Biographical notes:** Mohammad Reza Heidari Iman received his MSc in Computer Engineering from Ferdowsi University of Mashhad, Mashhad, Iran in 2015. His research interests include dependable embedded systems, fault tolerance, distributed and multi-core embedded systems, as well as human-computer interaction and software quality.

Pejman Yaghmaie received his BSc in Information Technology from Sadjad University of Technology, Mashhad, Iran in 2015 and his MSc in Information Technology from Tarbiat Modares University of Tehran in 2018. He is well-skilled in designing and implementing software solutions. His research interests are parallel and distributed computing, high performance computing and its applications.

# 1 Introduction

The advantages of multi-core processors have led to their abundant use in many applications. The increase in computational requirements of embedded systems has resulted in more use of multicore systems rather than single core systems (Digalwar et al., 2017; Pei et al., 2018). Multi-core processors improve computational performance and level of parallelism (Jena and Srinivas, 2012).

Moreover, they improve power consumption and heat generation, and also help in attaining near real-time response (Jena and Srinivas, 2012). Therefore, they have been employed in many embedded systems (Jena and Srinivas, 2012). Embedded systems are employed in different industries such as automotive and medical, as well as their general use in all safety-critical applications (Jena and Srinivas, 2012; Tong et al., 2017). In the case of the latter and the systems involved, a failure can have disastrous
results, from financial or ecological harm to even death or serious injury (Salloum et al., 2012). In order to avert disaster, embedded systems should be equipped with fault tolerance techniques which have been proposed to improve their reliability and safety (Pullum, 2001).

Control Flow Errors (CFEs) are processor errors which change the normal execution flow of the program (Maghsoudloo et al., 2012). Previous studies show that more than 70% of all errors occurring in a processor are CFEs (Maghsoudloo et al., 2012). Therefore, to improve the reliability of an embedded system, CFEs should be tolerated (Pullum, 2001). To tolerate and detect these kinds of errors, several techniques, known as control flow checking techniques, have been proposed in the literature. They fall into either of three general categories, namely software-based control flow checking (SCFC), hardware-based control flow checking (HCFC), and hybrid control flow checking techniques (Maghsoudloo et al., 2012). HCFC techniques employ hardware facilities to control the program flow of a processor (Farazmand et al., 2008), whereas in SCFCs several software codes are inserted into the main program to monitor its execution flow (Maghsoudloo et al., 2012). Hybrid techniques offer a trade-off between the aforementioned two methods (Azambuja et al., 2014). Since SCFC techniques are hardware-independent and more cost effective, not only are they more suitable for modern processors, but also they can be employed in other kinds of general-purpose processors (Maghsoudloo et al., 2012). They also provide a high detection rate and small memory overhead (Farazmand et al., 2008) which makes them more suited to the task of improving the fault tolerance of multi-core embedded systems (Maghsoudloo et al., 2012).

To the best of our knowledge, few techniques have been proposed to detect CFEs in multi-core processors (Maghsoudloo et al., 2012). Although these techniques have some advantages, they have some important drawbacks in their performance overhead and error detection coverage. In the technique proposed by Maghsoudloo et al. (2012), any error occurrence in the monitor can lead to monitor failure and thus the system will be susceptible to CFEs. Moreover, the experimental results reported by Khoshavi et al. (2011) indicate the high imposed performance overhead of their proposed technique, in addition to the need for a duplicate of the main program to run on another core, resulting in a hardware overhead. Therefore, considering the importance of multi-core processors in safety-critical embedded systems, as well as the shortcomings of previously proposed techniques in detecting CFEs, the formulation of a control flow checking technique in multi-core processors is of paramount importance.

In this paper, to improve the fault tolerance of multi-core embedded systems, a software control flow checking technique for multi-core processors (SCFC-MC) has been proposed. In the SCFC-MC technique, each thread monitors another in addition to executing its own programs. Moreover, in the proposed technique, if a monitor fails due to an error, its monitoring task is assigned to another thread.

Therefore, there is not a single point of failure and the technique can continue its monitoring job, even with only one error-free thread. Furthermore, SCFC-MC does not impose any hardware overhead. Experimental results indicate that SCFC-MC has a better error detection coverage and error detection latency with low performance overhead in multi-core processors.

The paper has been constructed in six sections as follows: In Section 2, some terms used in the paper are defined. Previous studies are introduced in Section 3. The proposed technique is explained in Section 4 and Section 5 gives the experimental results. Finally, Section 6 concludes the paper.

## 2 Terminology

In this section, some of the terms used in the literature (Maghsoudloo et al., 2012) and this paper have been introduced and defined:

* Basic block (BB): a sequence of non-branching instructions the execution of which begins from the first instruction and terminates at the last. There is no branching instruction in a BB except possibly for the last one.

* Partition block (PB): one composed of branch instructions or instructions which are the destination of the branch instructions, and resides between two consecutive BBs.

* Control flow graph (CFG): a directed edge graph extracted from the relations of BBs to show the flow of the program.

* Control flow error (CFE): a violation of run-time behaviour during the execution of a program.

<figure><img src="image_1.png" /><figcaption>**Figure 1** Possible types of CFEs</figcaption></figure>

Source: Maghsoudloo et al. (2012)
Based on the CFG extracted from the program, as shown in Figure 1, seven possible types of CFEs may occur (Maghsoudloo et al., 2012) which are as follows.

Type 1 An illegal branch from a BB to outside the program space in the memory.

Type 2 An illegal branch from a BB to itself.

Type 3 An illegal branch from a BB to another BB.

Type 4 An illegal branch from a BB to a PB.

Type 5 An illegal branch from a PB to a BB.

Type 6 An illegal branch from a PB to itself or to another PB.

Type 7 An illegal branch from a PB to outside the program space in the memory.

## 3 Previous studies

Considering the importance of improving the fault tolerance of the safety-critical embedded systems, many studies have been conducted on error detection capabilities. To this end, many different control flow checking techniques have been proposed which consist of HCFC, SCFC and hybrid techniques (Maghsoudloo et al., 2012). In HCFC techniques such as HAFT (Kuvaiskii et al., 2016), CFCET (Rajabzadeh and Miremadi, 2006), and ASIS (Eifert and Shen, 1995), continuous surveillance generally depends on a dedicated monitoring hardware (e.g., a watchdog processor), and memory references, bus contents or timing information of the program contents are used to monitor the control flow of the program (Farazmand et al., 2008). This renders them inappropriate for modern processors which exploit instruction level parallelism techniques such as pipelining, out of order execution, and speculative execution which make an uncertainty in the execution time of the running program (Farazmand et al., 2008). Moreover, HCFC techniques have more performance overhead and hardware costs than the SCFC techniques (Maghsoudloo et al., 2012).

In order to resolve the aforementioned problems, SCFC techniques were introduced. Generally, in these techniques, a program code is divided into BBs and a CFG is extracted from the control flow of the program (Oh et al., 2002). A unique arbitrary number is assigned to each BB as a signature (Oh et al., 2002) and these signatures are embedded in the program code during compilation (reference signatures) (Oh et al., 2002). In execution time, generally, another signature is generated as a run-time signature (Oh et al., 2002). To control the program flow, the SCFC techniques compare the run-time signature with the reference signature, and any mismatch means that a CFE has occurred (Farazmand et al., 2008). CFCSS (Oh et al., 2002), ECCA (Alkhalifa et al., 1999), CEDA (Vemu and Abraham, 2011), ACCE (Vemu et al., 2007), and the technique proposed by Asghari et al. (2014) are some of the important SCFC techniques proposed so far.

In addition to the above, a number of hybrid techniques such as the method proposed by Ďuriček and Krajčovič (2014), the method proposed by Duricek and Krajcovic (2015), and CFEDC (Farazmand et al., 2008) have been proposed. Due to the advantages of SCFC techniques over hardware-based ones, including their high error detection rate and lower costs, they are employed more frequently than the HCFC techniques (Maghsoudloo et al., 2012).

To the best of our knowledge, among all the SCFC and also hybrid techniques, few control flow checking techniques have been proposed for multi-core processors (Maghsoudloo et al., 2012). Maghsoudloo et al. (2012) have proposed a technique in which a watchdog thread has been developed to check the sequence of the signatures in parallel with the execution of main threads in order to control the program flow. Furthermore, to control the dependencies and communications of the threads, an array has been used to store the signatures. The monitor thread checks the array after executing a specified number of BBs, while additional instructions have been added in the middle of the BBs to improve the error detection coverage. This allows for some of the intra-block errors to be detected. Although this technique monitors the execution flow of running programs in multi-core processors, it involves some serious issues. Since there is only one monitor thread, any error in the monitor can lead to a monitor failure and the system will be left unprotected against faults. Additionally, employing a processor thread as a pure monitor imposes significant performance overhead.

Another proposed technique for multi-core processors has been introduced by Khoshavi et al. (2011), and is composed of two phases, namely basic and program-level control flow checking. In order to detect CFEs, in the basic-level phase, a unique signature is assigned to any of the BBs during design time. After that, the run-time signature is continuously updated in the executed BB. Finally, compile time and run-time signatures are compared to each other at the end of each BB. Any mismatch between these signatures will be a CFE. The basic-level phase of this technique is capable of detecting inter-block CFEs and does not have sufficient capability to detect intra-block CFEs. Program-level CFE detection has been used to detect intra-block CFEs in addition to any inter-block CFEs which are not detected at basic-level CFE detection phase. In this technique, a redundant program similar to the main program has been specified to detect the CFEs that are not detected in the basic-level phase. To reduce the probability of corruption in both the redundant and main programs, and also to achieve load balancing, the redundant program should be executed on a different core of the processor.

Considering the increase in the utilisation of multi-core processors in safety-critical embedded systems and the weaknesses of previous control flow checking techniques in multi-core processors, more studies are required in order to improve the fault tolerance of these systems. For this purpose, in this paper the SCFC-MC technique has been proposed with the capability of detecting about 95% of
CFEs. SCFC-MC is a software-based technique which does not have any single point of failure.

## 4 Proposed technique

In order to propose an SCFC technique for multi-core processors to improve the fault tolerance of safety-critical embedded systems, a technique called SCFC-MC has been proposed. SCFC-MC is a SCFC technique which uses software signatures to control the program flow in multi-core processors. In devising it, exclusive emphasis has been placed on how the threads are monitored. In SCFC-MC, each and every single thread is considered a monitor thread which executes its programs in addition to monitoring its subsequent thread. In other words, the first thread monitors the second thread; the second monitors the third, and so forth until the last thread which monitors the first one. Since in SCFC-MC any of the threads has the same two tasks (monitoring and executing the programs), the processing load can be balanced on any of the processor cores. Generally, the SCFC-MC provides a better opportunity for load balancing, compared to a single threaded monitoring technique like Maghsoudloo et al. (2012). The SCFC-MC technique increases efficiency by balancing the monitoring job on all slave threads. Since the monitoring job is not a resource consuming task, assigning a complete thread just for this job is not as efficient as balancing it on slave threads. In other words, in many applications, the monitoring task is not that heavy to use the maximum capacity of a CPU core for it, therefore, the leftover hardware resource usually remains unused. Using a single thread for monitoring is not a good practice in case of parallelisation and the SCFC-MC tries to address it by a better parallelised monitoring technique.

The monitoring mode in SCFC-MC eliminates the single point of failure problem. Since there is not just one single monitor thread, an error in one thread cannot lead to system failure. In fact, the monitoring mode here is such that if any of the threads is killed and disabled, other threads can continue their tasks. Therefore, the performance of the system will be improved.

In SCFC-MC, when a monitor thread is killed, another thread replaces it to monitor the next thread that the killed one was monitoring. In fact, this process is such that if only one thread is alive and all the other threads have been killed, the system can continue its execution with the only thread left alive. In this condition, the remaining thread has the monitor role, assigned with the task of monitoring itself, as well as executing its program. When a monitor thread wants to monitor another thread, it first checks whether the thread that is to be monitored is alive. If so, the monitor thread will monitor it. Otherwise, it examines the next thread to check whether it is alive. In this way, the monitoring task of the killed thread will be assigned to another alive thread, and also if only one alive thread remains, it can monitor itself. Figure 2 illustrates the process through which the alive-or-dead status of threads is checked.

<figure><img src="image_2.png" /><figcaption>**Figure 2** Checking whether threads are alive (see online version for colours)</figcaption></figure>

### 4.1 Control flow checking in SCFC-MC

Generally, most SCFC techniques assign software signatures to BBs in compile time and compare them with the run-time signature, with any mismatch between the two figures resulting in the detection of a CFE (Oh et al., 2002). In SCFC-MC, BBs and PBs are determined first, and additional instructions are then added to each BB to check the signatures. Next, program flow is controlled with the help of the program's CFG. As mentioned in Section 3, Maghsoudloo et al. (2012) have proven that if additional instructions are inserted into the middle of the BBs, error detection coverage, including Type 2 and Type 3 CFEs, will be improved, as well as reducing performance overhead and memory overhead. However, it can result in a small number of some other types of CFEs not being detected (Maghsoudloo et al., 2012). The experiments on SCFC-MC technique have shown similar results. Therefore, additional instructions are added in the middle of the BBs to improve the detection of CFEs and, especially, intra-block errors.

<figure><img src="image_3.png" /><figcaption>**Figure 3** Monitor log structure</figcaption></figure>

Since the investigated systems are equipped with multi-core processors, control flow checking should be according to the structure of multi-core processors. To control the program flow in SCFC-MC, a special structure called monitor log has been implemented for each thread to insert its signature. The structure of the monitor log is shown in Figure 3. All the necessary signatures for monitoring the program flow are inserted in this log. These signatures consist of the source and destination signatures of
the branch during compile time, run-time signature and the run-time adjusting signature (D) for branch-fan-in nodes – nodes (BBs) which receive more than one transfer from the other BBs (Oh et al., 2002). Furthermore, since each thread has a separate log, a pointer has been used for granting each thread access to its own monitor log.

In order to use the monitor log, when a BB is executed, the compile time signatures of the source and destination of the branch will be inserted into the log. During monitoring time, the monitor thread uses the monitor log of the thread which is to be monitored. In fact, at this time and in the destination BB, the source and destination signatures of the compile time are XOR'ed to calculate their differences. Then, this value is XOR'ed with the previous run-time signature to obtain the latest run-time signature. If the run-time signature does not match the destination compile time signature, a CFE is detected. Like the CFCSS technique (Oh et al., 2002), a run-time adjusting signature is also used for branch-fan-in nodes in the proposed technique.

It should be noted that the monitor logs have been employed independently from their threads. Therefore, if a thread is killed, its signatures will not be lost and thus, program flow is controlled correctly as far as the thread is executing. The structure of SCFC-MC technique is illustrated in Figure 4: each thread has access to the monitor logs array and has the index of the monitor log of the thread which is monitoring. Any thread inserts its own signatures

in its monitor log, after which the monitor thread first checks if the thread it wants to monitor is alive. If so, the monitor thread will read the signatures of that thread from its monitor log to control the program flow of the thread. It should be considered that since the monitor thread has the index of the monitored thread's monitor log and the size of the monitor logs array, it can do a circular shift to another thread's monitor log. Also, check alive function makes a performance overhead on the system, however, this overhead is unavoidable and negligible and also having this function is necessary for the monitoring system to act correctly.

<figure><img src="image_4.png" /><figcaption>**Figure 5** An example of SCFC-MC process (see online version for colours)</figcaption></figure>

<figure><img src="image_5.png" /></figure>
For better understanding, an example of SCFC-MC process has been shown in Figures 5(a) to 5(d). At first step, the initialisation code creates the monitor log array and slave threads [Figure 5(a)]. Each monitor log in the array is assigned to a specific thread to store signatures. Any of the threads, before starting the monitor procedure, checks if their next thread is alive. If the thread to be monitored is dead, monitor switches to the next one as shown in Figures 5(b) and 5(c). In Figure 5(b), Thread 3 is dead and the second thread switches to Thread 4 to monitor it. In 5(c), Thread 1 is dead and Thread 4 switches to Thread 2 to monitor it. Figure 5(d) shows what will happen if just one thread remains and how it switches to monitor itself while doing its job.

As mentioned before, in SCFC-MC, every thread executes its program and also monitors another thread. Although each thread does two separate tasks, one should note that there is no context switch and interrupt in this technique. This will significantly improve system performance. In SCFC-MC, all of the program codes are divided into two sets, namely benchmark codes (primary codes) and monitoring codes. The two are independent so that the former can execute independently and correctly without the latter. To control the program flow and detect CFEs, monitoring codes are added to the benchmark codes.

In order to add the monitoring codes to benchmark codes, a piece of code, which is called initialisation code, is added on top of the program. Furthermore, the aforementioned additional instructions that check the signatures with the help of the monitor log are added in all of the BBs. The definition of the data structures used for the additional instructions to control and monitor the program flow comprises the initialisation code, which is also responsible for memory allocation for these data structures and some initialisations. It is also where each monitor log is assigned to each thread.

<table><caption>**Table 1** Size of benchmarks code with and without monitoring code</caption><thead><tr><td>Benchmark</td><td>Size of original code</td><td>Size of original code with the monitoring code</td><td>Difference</td></tr></thead><tbody><tr><td>Merge sort</td><td>17.1 KBs</td><td>18.3 KBs</td><td>1.2 KBs</td></tr><tr><td>Quick sort</td><td>13.4 KBs</td><td>14.1 KBs</td><td>0.7 KBs</td></tr><tr><td>Matrix multiplication</td><td>15.7 KBs</td><td>16.5 KBs</td><td>0.8 KBs</td></tr><tr><td>Avg.</td><td>15.4 KBs</td><td>16.3 KBs</td><td>0.9 KBs</td></tr></tbody></table>

In order to control the program flow, additional instructions are inlined to each BB which leads to an increase in the size of each BB code. Inline function is an optimisation technique used by compilers to increase program speed by putting the instructions of a function's body where ever it is called and avoiding the overhead of its invocations.

Defining a function inline will increase the size of the executable file. Therefore, it should be used carefully in some cases in which final executable size is important (like embedded systems), because larger executable leads to higher memory consumption. Thus, taking advantage of inline functions necessitates paying attention to the size of the function to be inlined. In this work, adding all the required instructions including initialisations and monitoring codes to the benchmark codes increased the final executable size to an average of 0.9 KB. More details are presented in Table 1. Consequently, by adding additional instructions inlined, jumps and movements between benchmark codes and monitoring codes are reduced. In other words, this technique merges the contexts of the benchmark and the monitor, which in turn leads to improvement in system performance compared to cases which have extra functions for monitoring jobs and there are separate contexts for slave threads and monitor threads. Furthermore, it causes the benchmark codes and monitoring codes to form a monolithic code that eliminates the need for the allocation of additional memory and some additional instructions for switching between the benchmark code and monitoring code. Therefore, to monitor and control the program flow and run the monitoring codes, there is no need for any interrupt and context switch, and monitoring is performed in an executional routine which improves the performance of the system.

For better understanding, when a function is called the program needs to jump to a random location in memory where the instructions for the function body is located. The program needs to save the current cursor position into the run-time stack to be able to return after the function ends. This process takes a few CPU cycles and in cases like this which have more function calls than usual, using inline technique can improve the performance.

For periodicity in running the monitoring codes and more improvement of performance, a variable called block count is checked in each BB and if it has the intended amount (the amount from which monitoring should start), monitoring codes will run and the block count is reset to zero. Generally, by using inlined code, benchmark codes and monitoring codes are monolithic in a way that minimum performance overhead is imposed on the system. The proposed technique has been described in the algorithm in Figure 6.

Since SCFC-MC has been proposed to control the program flow in multi-core processors, all the programs should be implemented in multi-threaded form. Figure 7 illustrates the structure of the multi-threaded programs that have been used in SCFC-MC technique. This figure shows the multi-threaded merge-sort program whose main thread has been divided into slave threads. Any of these threads sorts part of the data and finally all the sorted data is merged.
<figure><img src="image_6.png" /><figcaption>**Figure 7** Structure of multi-threaded programs</figcaption></figure>

<figure><img src="image_7.png" /></figure>

## 4.2 Theoretical comparison between SCFC-MC and the technique proposed by Maghsoudloo et al. (2012)

Taking the explanations in the previous sections for SCFC-MC and the technique proposed by Maghsoudloo et al. (2012) into consideration, a number of the latter's important disadvantages come to light. These issues have been resolved in the SCFC-MC technique. General comparison between these two techniques is shown in Table 2 which shows some of the most important features and advantages of SCFC-MC that are important in

safety-critical systems. In SCFC-MC, since any of the cores is implicated in processes, all the processing load is balanced on all the cores and, in comparison with Maghsoudloo's, it maximises the performance of the system. Moreover, SCFC-MC uses the minimum possible number of threads, whereas the other technique uses one thread more than the SCFC-MC. In (Maghsoudloo et al., 2012), one of the threads is devoted only to checking the signatures for monitoring the other threads. It should be considered that in (Maghsoudloo et al., 2012), to implement the monitor, a thread has been employed solely as a hardware facility of the processor; therefore, this technique
can be categorised into hybrid techniques. Furthermore, unlike the proposed technique in (Maghsoudloo et al., 2012), there is not a single point of failure in SCFC-MC.

<table><caption>**Table 2** Theoretical comparison between SCFC-MC and the technique proposed in Maghsoudloo et al. (2012)</caption><thead><tr><td>SCFC-MC technique</td><td>The technique proposed in Maghsoudloo et al. (2012)</td></tr></thead><tbody><tr><td>All the threads are as the monitor</td><td>Has only one monitor</td></tr><tr><td>Used the minimum number of threads</td><td>Used one thread more than SCFC-MC</td></tr><tr><td>Has no single point of failure</td><td>Has single point of failure</td></tr><tr><td>Software technique</td><td>Hybrid technique</td></tr><tr><td>Used in processors with any number of cores</td><td>Used in processors with any number of cores</td></tr></tbody></table>

## 5 Experimental results

In order to evaluate the proposed technique a system with quad-core processor, with the following specifications has been used:

* CPU: Intel(R) Core(TM) i7-4710HQ CPU @ 2.50-3.5 GHz

* RAM: 1 × 8GB 1,600 MHz

This system has been used as the simulation environment with Arch Linux operating system. The investigated systems are safety-critical embedded systems and SCFC-MC has been proposed to detect the CFEs in these systems. These kinds of systems are generally industrial systems, and most software and programs used therein are usually implemented with programming languages such as C or C++ (Yuste et al., 2003). Therefore, in order to evaluate the proposed technique, all the benchmarks have been implemented with C++ language and compiled using GCC 5.2.0. Also, to investigate the effects of the injected faults and to observe what is going on inside a program after fault injection, the GNU Project Debugger (GDB 7.9.1) has been employed.

<table><caption>**Table 3** Descriptions of each benchmark</caption><thead><tr><td>Benchmark</td><td>Description</td></tr></thead><tbody><tr><td>Merge sort</td><td>All data are randomly inserted in the arrays and 10,000 pieces of data are sorted into four separate threads.</td></tr><tr><td>Quick sort</td><td></td></tr><tr><td>Matrix multiplication</td><td>The four threads undergo matrix multiplication. Two 64 × 64 matrices are used from which each of the four threads takes and sorts part of the data and saves the results in a third matrix.</td></tr></tbody></table>

In order to evaluate the SCFC-MC technique, three benchmarks have been implemented in multi-threaded structure. These benchmarks are merge sort, quick sort, and matrix multiplication. All benchmarks are implemented

with four threads to run on a quad-core processor. As mentioned in Section 4, SCFC-MC can be employed on systems with any number of cores. However, for better evaluation and comparison between SCFC-MC and the proposed technique in Maghsoudloo et al. (2012), all the benchmarks have been implemented with four threads. After implementation, additional instructions are added into the BBs to control the program flow. Table 3 shows the descriptions of each benchmark.

The important factors that should be measured to evaluate SCFC-MC are performance overhead, error detection coverage, error detection latency and method efficiency. To measure the error detection coverage, fault injection has been used, which changes the normal program flow, allowing the program execution to be observed in the presence of faults. Ten thousands faults are injected into the benchmarks at random times to evaluate the proposed technique. In order to inject the faults, program execution is interrupted at random times and program flow is moved to the injection function which changes the return address of the latest executed instruction. To perform this change, one of its bits is randomly XOR'ed with 1, the result of which will be the new return address that the program will be executed from upon exiting the injection function.

Two important parameters, namely confidence level and confidence interval, have been considered in the experiments. The figure for the former should be 95% and the latter must stand at 1. To achieve this level of precision, about 10,000 experiments are required. Therefore, 10,000 faults have been injected to the benchmarks. A confidence level of 95% and confidence interval of 1 mean that, with a probability of 95%, the experimental results will have a maximum error rate of 1%.

In order to evaluate SCFC-MC under heavy load and use the system on maximum power, 10,000 pieces of data (32-bit integers) have been given to the benchmarks as inputs. Since each thread performs two separate tasks, in order to reduce the performance overhead, each monitor thread has been set to monitor the threads on execution of 1, 5, and 10 BBs. Table 4 shows the performance overhead of the system for SCFC-MC technique for each benchmark and compares it with the proposed technique in Maghsoudloo et al. (2012). In this table, BC stands for the block count constant, and it can be observed that the least performance overhead was achieved in all of the benchmarks when BC was equal to 10. Although the performance overhead of SCFC-MC is slightly greater than that for the technique in Maghsoudloo et al. (2012), it should be considered that only four threads have been used in all of the evaluations for SCFC-MC, whereas five threads have been used in the evaluations of Maghsoudloo et al. (2012). In fact, in Maghsoudloo et al. (2012) one extra thread has been used to monitor the other four threads. However, in SCFC-MC all the processes have been balanced on only four threads, and they monitor each other, as well. Therefore, it is obvious that the performance overhead of Maghsoudloo et al. (2012) will be a little lower than SCFC-MC since it has used one more thread in
comparison with SCFC-MC. Nevertheless, the maximum difference in their overheads is less than 5%. Moreover, as mentioned before in SCFC-MC, additional instructions are added inline and since there is not any context switch and interrupt, the overall performance of the technique will be significantly improved.

Another important factor that should be measured is the error detection coverage, calculated results for which are shown in Figure 8. To evaluate SCFC-MC, injection has been done on all of the threads. The average figure for the

error detection coverage of SCFC-MC is 94.93% which has improved in comparison with Maghsoudloo et al. (2012). In Maghsoudloo et al. (2012), the error detection coverage is measured at about 93%. It should be considered that for measuring the error detection coverage of the proposed technique in Maghsoudloo et al. (2012), injection has not been done on the monitor thread. However, had this been performed, the error detection coverage of Maghsoudloo et al. (2012) would have been reduced dramatically.

<table><caption>**Table 4** Performance overhead of SCFC-MC</caption><thead><tr><th rowspan="3">Block count constant</th><th colspan="8">Performance Overhead (%)</th></tr><tr><th colspan="2">Merge sort</th><th colspan="2">Quick sort</th><th colspan="2">Matrix multiplication</th><th colspan="2">Average</th></tr><tr><th>SCFC-MC</th><th>The proposed technique in Maghsoudloo et al. (2012)</th><th>SCFC-MC</th><th>The proposed technique in Maghsoudloo et al. (2012)</th><th>SCFC-MC</th><th>The proposed technique in Maghsoudloo et al. (2012)</th><th>SCFC-MC</th><th>The proposed technique in Maghsoudloo et al. (2012)</th></tr></thead><tbody><tr><td>BC = 1</td><td>25.08</td><td>22.71</td><td>37.21</td><td>31.88</td><td>40.18</td><td>35.04</td><td>34.15</td><td>29.87</td></tr><tr><td>BC = 5</td><td>14.54</td><td>16.22</td><td>27.82</td><td>19.39</td><td>28.76</td><td>21.17</td><td>23.70</td><td>18.92</td></tr><tr><td>BC = 10</td><td>12.31</td><td>14.13</td><td>21.97</td><td>17.78</td><td>25.51</td><td>19.32</td><td>19.93</td><td>17.07</td></tr></tbody></table>

<figure><img src="image_8.png" /><figcaption>**Figure 9** Error detection coverage versus performance overhead of SCFC-MC (see online version for colours)</figcaption></figure>

<figure><img src="image_9.png" /></figure>
<figure><img src="image_10.png" /><figcaption>**Figure 11** Method efficiency (see online version for colours)</figcaption></figure>

<figure><img src="image_11.png" /></figure>

According to Figure 9, performance overhead is reduced by increasing the BC, because the BC constant defines the number of BBs to be executed before entering the monitoring state. When BC is equal to 1, related instructions to monitoring task will be executed for each BB. However, when BC is equal to 5 or 10, this task will be executed after execution of 5 or 10 BBs. On the other hand, BC has no effect on the error detection coverage, because it is not related to the frequency of executing the monitoring code.

Error detection latency is another important factor whose calculated results are shown in Figure 10, where for BC equals 10 latency is more than others. The results indicate that when the number of executed BBs is increased, the error detection latency is increased, too. Because in this situation, the execution of monitoring task will be reduced. However, in this condition the performance of the system has been improved. Since in SCFC-MC a monitor has been dedicated for each thread, the accuracy of the error detection, as well as the error detection latency, is improved.

In order to have a factor that allows for a general comparison among all the methods, method efficiency has been used which is defined to estimate the efficiency of the methods and calculated through (1) (Maghsoudloo et al., 2012).

$$ \text{Method Efficiency} = \frac{\left( \frac{1}{\% \text{Undetected Errors}} \right)}{\text{Performance Overhead}} \times 100 \quad (1) $$

The average figures for the method efficiency of SCFC-MC and the proposed technique in Maghsoudloo et al. (2012) are shown in Figure 11. All the calculated results are also collected together in Table 5. Considering the experimental results, SCFC-MC can be regarded as the efficient SCFC technique in multi-core processors as it can detect a significant proportion of the CFEs with low error detection latency. Furthermore, SCFC-MC has low performance overhead.
<table><caption>**Table 5** Experimental results of SCFC-MC</caption><thead><tr><th>Block count constant</th><th>Performance overhead (%)</th><th>Error detection coverage (%)</th><th>Error detection latency (cycle)</th><th>Method efficiency</th></tr></thead><tbody><tr><td>BC = 1</td><td>34.15</td><td>94.93</td><td>6.7</td><td>0.58</td></tr><tr><td>BC = 5</td><td>23.70</td><td>94.93</td><td>13.6</td><td>0.83</td></tr><tr><td>BC = 10</td><td>19.93</td><td>94.93</td><td>27.1</td><td>0.99</td></tr></tbody></table>

## 6 Conclusions and future study

In this paper, a software control flow checking technique in multi-core processors was proposed where, in addition to executing the program, each thread is employed as a monitor. SCFC-MC is an efficient SCFC technique which improves both error detection coverage and the performance of the system. The error detection coverage for the proposed technique is about 95% with low error detection latency and also it has less than 20% performance overhead. Unlike the hybrid technique which has been proposed in Maghsoudloo et al. (2012), SCFC-MC is a purely software-based technique without a single point of failure. Considering the experimental results of the proposed technique and the necessity of employing safety-critical multi-core embedded systems in industries, SCFC-MC seems to be an appropriate technique for these systems.

Technically, the SCFC-MC technique can be implemented for distributed computing systems, however it is not recommended. In SCFC-MC, all threads frequently access an array (monitor logs) for doing the monitoring job. The frequent access to monitor logs array and frequently checking thread aliveness is expected to produce more overhead on network communications. Additionally, there is more latency on network communications compared to the equivalent tasks within a computer system. Consequently, implementation of the SCFC-MC in distributed computing systems is not expected to have a good performance due to the need of frequent access to monitor log and checking the thread aliveness. The proposed technique focused on multi-core embedded systems and implementation and optimisation of control flow checking techniques for distributed systems needs some changes in the technique which can be studied in our future researches.

## Acknowledgements

We thank three ‘anonymous’ reviewers for their constructive comments and suggestions and Professor Yasser Sedaghat for his help and guidance.

## References

Alkhalifa, Z., Nair, V.S.S., Krishnamurthy, N. and Abraham, J.A. (1999) ‘Design and evaluation of system-level checks for on-line control flow error detection’, *IEEE Transactions on Parallel and Distributed Systems*, Vol. 10, No. 6, pp.627–641.

Asghari, S.A., Taheri, H., Pedram, H. and Kaynak, O. (2014) ‘Software-based control flow checking against transient faults in industrial environments’, *IEEE Transactions on Industrial Informatics*, IEEE, Vol. 10, No. 1, pp.481–490.

Azambuja, J.R., Kastensmidt, F. and Becker, J. (2014) *Hybrid Fault Tolerance Techniques to Detect Transient Faults in Embedded Processors*, Springer, Switzerland.

Digalwar, M., Gahukar, P., Raveendran, B.K. and Mohan, S. (2017) ‘Energy efficient real-time scheduling algorithm for mixed task set on multi-core processors’, *International Journal of Embedded Systems*, Vol. 9, No. 6, pp.523–534.

Ďuriček, M. and Krajčovič, T. (2014) ‘Interactive hybrid control-flow checking method’, *International Conference on Applied Electronics*, IEEE, Pilsen, Czech Republic.

Duricek, M. and Krajcovic, T. (2015) ‘Hybrid control-flow checking with on-line statistics’, *4th Eastern European Regional Conference on the Engineering of Computer Based Systems*, IEEE, Brno, Czech Republic.

Eifert, J. and Shen, J. (1995) ‘Processor monitoring using asynchronous signature instruction streams’, *International Symposium on Fault-Tolerant Computing*, June.

Farazmand, N., Fazeli, M. and Miremadi, S.G. (2008) ‘FEDC: control flow error detection and correction for embedded systems without program interruption’, *International Conference on Availability, Reliability and Security*, pp.33–38.

Jena, S.K. and Srinivas, M.B. (2012) ‘On the suitability of multi-core processing for embedded automotive systems’, *Cyber-Enabled Distributed Computing and Knowledge Discover*, Vol. 1, No. 1, pp.315–322.

Khoshavi, N., Zarandi, H.R. and Maghsoudloo, M. (2011) ‘Control-flow error detection using combining basic and program-level checking in commodity multi-core architectures’, *International Symposium on Industrial Embedded Systems*, IEEE, 15–17 June, pp.103–106.

Kuvaiskii, F., Faqeh, R., Bhatotia, P., Felber, P. and Fetzer, C. (2016) ‘HAFT: hardware-assisted fault tolerance’, *EuroSys ‘16 Proceedings of the Eleventh European Conference on Computer Systems*, ACM, London, UK.

Maghsoudloo, M., Zarandi, H.R. and Khoshavi, N. (2012) ‘An efficient adaptive software-implemented technique to detect control-flow errors in multi-core architectures’, *Microelectronics Reliability*, Vol. 52, No. 11, pp.2812–2828.

Oh, N., Shirvani, P.P. and Mccluskey, E.J. (2002) ‘Control-flow checking by software signatures’, *IEEE Transactions on Reliability*, Vol. 51, No. 2, pp.111–122.

Pei, S., Zhang, J., Xiong, N., Kim, M-S. and Gaudiot, J-L. (2018) ‘Energy efficiency of heterogeneous multicore system based on the enhanced Amdahl’s law’, *International Journal of High Performance Computing and Networking*, Vol. 12, No. 3, pp.261–269.
Pullum, L.L. (2001) *Software Fault Tolerance Techniques and Implementation*, Artech House Publishers, Norwood, MA, USA.

Rajabzadeh, A. and Miremadi, S. (2006) ‘CFCET: a hardware-based control flow checking technique in COTS processors using execution tracing’, *Microelectronics Reliability*, Vol. 46, Nos. 5–6, pp.959–972.

Salloum, C.E., Elshuber, M. and Hoftberger, O. (2012) ‘The across mpsoc – a new generation of multi-core processors designed for safety-critical embedded systems’, *Euromicro Conference on Digital System Design*, pp.105–113.

Tong, Y., Yang, X. and Li, Y. (2017) ‘Application of interactive evolutionary strategy in fault-tolerant system capable of online self-repairing’, *International Journal of Computational Science and Engineering*, Vol. 15, Nos. 1–2, pp.57–65.

Vemu, R. and Abraham, J.A. (2011) ‘CEDA: control-flow error detection using assertions’, *IEEE Transactions on Computers*, Vol. 60, No. 9, pp.1233–1245.

Vemu, R., Gurumurthy, S. and Abraham, J.A. (2007) ‘ACCE: automatic correction of control-flow errors’, *International Test Conference*, pp.1–10.

Yuste, P., Ruiz, J.C., Lemus, L. and Gil, P. (2003) ‘Non-intrusive software-implemented fault injection in embedded systems’, *Latin-American Dependable Computing*, 21–24 October, pp.23–38.