Nicolas Moro
email: nicolas.moro@cea.fr

Amine Dehbaoui
email: amine.dehbaoui@mines-stetienne.fr

Karine Heydemann
email: karine.heydemann@lip6.fr

Bruno Robisson
email: bruno.robisson@cea.fr

Emmanuelle Encrenaz
email: emmanuelle.encrenaz@lip6.fr

Electromagnetic fault injection: towards a fault model on a 32-bit microcontroller

Keywords: microcontroller, timing fault, electromagnetic glitch, fault attack, fault model

Injection of transient faults as a way to attack cryptographic implementations has been largely studied in the last decade. Several attacks that use electromagnetic fault injection against hardware or software architectures have already been presented. On microcontrollers, electromagnetic fault injection has mostly been seen as a way to skip assembly instructions or subroutine calls. However, to the best of our knowledge, no precise study about the impact of an electromagnetic glitch fault injection on a microcontroller has been proposed yet. The aim of this paper is twofold: providing a more in-depth study of the effects of electromagnetic glitch fault injection on a state-of-the-art microcontroller and building an associated register-transfer level fault model.

I. INTRODUCTION

Physical attacks aim at breaking cryptosystems by gaining information from their implementation instead of using theoretical weaknesses. Those attack schemes were introduced in the late 1990s. There are two main subclasses of physical attacks: passive and active ones. In passive attacks, an attacker uses the fact that some measurable data may leak information about manipulated secret data such as cryptographic keys. Physical quantities which can be used for passive attacks include execution time [START_REF] Kocher | Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[END_REF], electromagnetic radiations [START_REF] Agrawal | The EM Side-Channel(s)[END_REF], power consumption [START_REF] Kocher | Differential power analysis[END_REF] or light emissions [START_REF] Schlösser | Simple Photonic Emission Analysis of AES Photonic Side Channel Analysis for the Rest of Us[END_REF]. In active attacks, an attacker modifies the circuit's behaviour in order to perform its attack scheme. Fault attacks are a subset of active attacks in which an attacker injects a transient fault in a circuit's computation.

Faults attacks were introduced in 1997 by Boneh et al. [START_REF] Boneh | On the Importance of Checking Cryptographic Protocols for Faults[END_REF]. They consist in modifying a circuit environment in order to c 2013 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. change its behaviour or to induce faults into its computations [START_REF] Bar-El | The Sorcerer's Apprentice Guide to Fault Attacks[END_REF] [7] [START_REF] Barenghi | Fault Injection Attacks on Cryptographic Devices: Theory, Practice, and Countermeasures[END_REF]. Many means are of common use to inject such faults, especially laser shots [START_REF] Skorobogatov | Optical Fault Induction Attacks[END_REF] [10] [START_REF] Canivet | Glitch and Laser Fault Attacks onto a Secure AES Implementation on a SRAM-Based FPGA[END_REF], overclocking [START_REF] Agoyan | How to Flip a Bit?[END_REF] [13], chip underpowering [START_REF] Fournier | Security Evaluation of Asynchronous Circuits[END_REF] [START_REF] Zussa | Investigation of timing constraints violation as a fault injection means[END_REF], temperature increase [START_REF] Skorobogatov | Local Heating Attacks on Flash Memory Devices[END_REF] or electromagnetic glitches [START_REF] Schmidt | Optical and EM Fault-Attacks on CRT-based RSA: Concrete Results[END_REF] [START_REF] Dehbaoui | Electromagnetic Transient Faults Injection on a Hardware and a Software Implementations of AES[END_REF].

There are three main subclasses of fault attacks: algorithm modifications, safe error and differential fault analysis. Algorithm modifications aim at skipping [START_REF] Schmidt | A Practical Fault Attack on Square and Multiply[END_REF] or replacing [START_REF] Balasch | An Indepth and Black-box Characterization of the Effects of Clock Glitches on 8-bit MCUs[END_REF] some instructions executed by a microcontroller to circumvent its security features. Safe-error attacks aim at evaluating whether or not a fault injection has an impact on the output [START_REF] Yen | Checking before output may not be enough against fault-based cryptanalysis[END_REF]. Differential fault analysis (DFA) aims at retrieving the keys used by an encryption algorithm by comparing correct ciphertext and faulty ciphertexts (i.e. ciphertexts obtained from a faulted encryption). This technique was first introduced for public key encryption algorithms [START_REF] Boneh | On the Importance of Checking Cryptographic Protocols for Faults[END_REF], and quicky extended to secret key algorithms [START_REF] Biham | Differential Fault Analysis of Secret Key Cryptosystems[END_REF].

From that time, many attack schemes have been proposed to attack various encryption algorithms. They all rely on an attacker's fault model which defines the type of faults the attacker can perform [START_REF] Barenghi | Countermeasures against fault attacks on software implemented AES[END_REF]. Thus, they require a high accuracy in the fault injection process. If the faults are not induced at the proper time in the algorithm, or affect the wrong bits, the entire attack process fails. As a consequence, the ability to precisely control the fault injection process is a key element in carrying out any fault attack. Common fault models include instruction skips [START_REF] Schmidt | A Practical Fault Attack on Square and Multiply[END_REF], single bit faults or single word faults [START_REF] Verbauwhede | The Fault Attack Jungle -A Classification Model to Guide You[END_REF].

In this work, we report the use of electromagnetic pulses to induce faults into the computations of an up-to-date microcontroller. We also report a study of the local effect of electromagnetic pulses. Moreover, the underlying effects behind common fault models are not always clearly understood and may highly depend on the target architecture. As a consequence, this work finally aims at defining a precise fault model and providing an understanding of the faults an electromagnetic glitch can induce on an embedded program.

The rest of this paper is organized as follows. Section II introduces our fault injection experimental setup and details the approach we use. Section III describes the influence of some experimental parameters on injected faults. Section IV details the effects of the injected faults on the program flow and data flow. Finally, the resulting register-transfer level fault model is presented in section V. Section VI gives details about some related research papers.

II. APPROACH

This section starts by describing our experimental setup choices in II-A. This experimental setup enables us to provide the results presented in section III which show the influence of the different experimental parameters. Then, we detail the approach we use to precisely characterize the faults we injected. This characterization method, which matches experimental results obtained from the microcontroller with simulation data, is detailed in II-B.

A. Experimental setup 1) Electromagnetic fault injection bench: The electromagnetic glitch fault injection platform shown in Fig. 1 is composed of a control computer, the target device, a motorized stage, a pulse generator, and a magnetic antenna. The target (described in II-A2) is mounted on the X Y Z motorized stage. The computer controls both the pulse generator (through a RS-232 link) and the target board (through a USB link). The pulse generator is used to deliver voltage pulses to the magnetic coil. It has a constant rise and fall transition time of 2 ns. The amplitude range of the generated pulses extends from -200 V to 200 V, their width extends from 10 ns to 200 ns. The magnetic antenna we use is composed of a few turns with a diameter of 1 mm. We use it in order to disturb a small part of the target device. This spatial accuracy is possible thanks to a high accuracy X Y Z stage.

2) Target: The chosen target is an up-to-date 32-bit microcontroller designed in a CMOS 130 nm technology. It is based on the ARM Cortex-M3 processor [START_REF] Yiu | The Definitive Guide To The ARM Cortex-M3. Elsevier Science[END_REF]. Its operating frequency is set to 56 MHz. This microcontroller does not embed any cache memory.

Choice of target: The target we use is a state-of-theart microchip, based on a recent technology. ARM Cortex processors are already very widespread for both mainstream and secure microcontrollers. Although we did not choose a smartcard version of the microcontroller, this target embeds some basic security mechanisms against clock perturbations and voltage glitches. Moreover, several interrupt vectors have been defined which can handle some hardware faults and can be used for a basic fault detection. Hence, we can consider this target as reasonably secured against some of the most common low-cost fault injection means. However, this target does not embed any protective shield against reverse engineering or electromagnetic injection. Since this research aims at understanding the effects of fault injection on a recent microcontroller, we do not work on a highly-secure version of this microcontroller.

Instruction set: Cortex-M3 processors run the ARM Thumb2 instruction set [START_REF] Arm | ARM Architecture Reference Manual -Thumb-2 Supplement[END_REF]. Thumb2 is actually the successor to both ARM and Thumb instruction sets, and contains both 16-bit and 32-bit instructions.

Hardware interrupts: Several fault exceptions can catch illegal memory accesses or illegal program behaviour. Those fault exceptions are Hard Fault, Bus Fault, Usage Fault and Memory Management Fault. Each of these exceptions can be triggered for several subtypes of hardware faults. In the following experiments, every exception handler function executes an infinite loop.

B. Experimental process

Working with a microcontroller in such a black-box approach requires to develop a specific experimental approach. This approach aims at enabling us to deduce the effects of faults by observing some internal data from the microcontroller. This observation must be done with a non-invasive technique. Since a faults may have an impact on the program flow and since we need to access some accurate data such as registers or cycle count, the communication cannot be done with a serial link. We use the JTAG-equivalent non-instrusive SWD debug link to retrieve data from the microcontroller. Besides, we also use the hardware exceptions defined in II-A2 as a way to get some extra data about the injected faults.

1) Microcontroller's internal state observation: The experimental measurement process we use is the following:

• Reset the microcontroller The following paragraphs detail the important elements of this experimental process.

Trigger window: In order to have a correct view of the microcontroller's internal data, we have created an assembly subroutine containing some test instructions (which will be detailed in section III). For our experiments, the microcontroller sets a trigger signal for the electromagnetic injection. With this technique, we can target the executed program at the scale of a single instruction. By observing the microcontroller's clock during this trigger window, we can focus the injection on a single clock cycle. Besides, the pulse injection time is defined by reference to the beginning of the trigger signal temporal window.

Watchpoint and program end: In this experimental process, the program normally stops because of a breakpoint set after the target code. This watchpoint is defined before popping the stack at the end of the assembly subroutine and after the trigger window. However, with our experimental setup and target code, two other scenarios may happen because of a fault: an unconditional jump and an infinite loop due to the triggering of an exception. These two scenarios modify the control flow, and the program may not reach the defined breakpoint. Moreover, the unconditional jump scenario makes the setting of breakpoints very hard. To handle these issues, our control computer stops the microcontroller after a fixed delay.

Internal data: With the SWD debug link, the internal data we get from the microcontroller at a watchpoint for our experiments are: the general-purpose registers (r0 to r12), the stack pointer (r13), the link register (r14), the program counter (r15), the program status register (xPSR), some chosen variables in memory and the number of clock cycles taken by our experiment. This number of clock cycles is counted from the beginning of the target subroutine. The xPSR register gives us information about the processor flags and the exceptions that may have been triggered. Since we only inject transient faults and since the watchpoint is set several clock cycles after our attack, we can reasonably assume that the debugging module embedded in the chip is not corrupted when recovering the internal data from the microcontroller.

However, some internal data such as the instruction register cannot be accessed. When working at the scale of a single instruction, we may need to determine which instruction has been actually executed by the core. To get a list of suitable instructions, we need to rely on an exhaustive instruction simulation.

2) Fault model simulation:

We propose to use simulation to explain the effects of electromagnetic fault injection. Our approach aims at comparing the experimental faulty outputs with outputs from a fault model simulation. Thus, we can validate the interpretation of these effects by comparing the outputs with the internal data. This scheme is summarized in Fig. 2 Simulations aim at finding output states which could be compatible with the output states we observed. In order to match simulations with measurements, we define a binary relation between experimental output states and simulated output states.

Definition. One instruction replacement can explain an experimental measurement if the output states ([r0-r12],

xPSR) at the defined watchpoint are the same for the measurement and the simulation In the rest of this article, two classes of faults can be distinguished: faults on the data flow and faults on the program flow [START_REF] Verbauwhede | The Fault Attack Jungle -A Classification Model to Guide You[END_REF]. Faults that lead to the replacement of an instruction by another one are faults on the program flow. They may result in an algorithm modification, depending on the context and the replaced instruction. On the contrary, faults which only modify a piece of data without modifying an instruction are faults on the data flow.

Nevertheless, this difference might not be clear for many cases since both fault classes may lead to very similar visible outputs. Thus, defining whether a resulting faulty output is a consequence of a fault on the data flow or the control flow is generally a tough task. Nevertheless, a single assembly instruction can only output a very limited set of data. As a consequence, it is possible to tell whether or not a faulty output is the consequence of a fault on the control flow. Thus, every faulty output which cannot be explained by an instruction replacement is considered to come from a fault on the data flow.

The Thumb2 instruction set is composed of both 16-bit and 32-bit instructions. 16-bit instructions can be exhaustively tested. 32-bit instruction start with the prefixes 11101 or 1111, which reduces the complexity of an exhaustive test. Moreover, the 32-bit part of the instruction set is mostly sparse, we can remove many branches in the search space.

It should be noted that this simulation is performed on the Obviously, many instruction replacements may be able to explain one single measurement. Nevertheless, being able to simulate instruction replacement will enable us to explain the effects we observed and then to define a fault model more clearly. To sum up, an exhaustive simulation over the instruction set is practical and can be performed in real conditions. Moreover, it enables to distinguish faults on the control flow from faults on the data flow.

III. EXPERIMENTAL STUDY OF THE INJECTION

PARAMETERS

In this section, we provide a study of the influence of several experimental parameters on the final outputs. Since metastability phenomena appear, we first start by describing them in the following paragraph.

A. Metastability phenomena

Since electromagnetic glitch fault injection leads to timing faults [START_REF] Dehbaoui | Electromagnetic Transient Faults Injection on a Hardware and a Software Implementations of AES[END_REF], we obtained some metastability phenomena. For this experiment, the pulse's voltage was set to 190 V, the clock frequency was set to 56 MHz, the pulse's injection time was fixed to an arbitrary value, and the pulse width was set to 10 ns. The probe position was found by a trialand-reset approach. The results for 10000 executions of our experimental process are presented in Table I, every observed output value is associated to its occurrence rate.

They show a metastability phenomenon for a single load instruction from the Flash memory which correct loaded value is 0x12345678 since several values appear for the same fixed configuration of the experimental parameters.

B. Study of the injection parameters

In the case of an electromagnetic fault injection on a microcontroller, many experimental parameters can have an influence on the final outputs. The main parameters we can control in these experiments and which may have an influence are detailed in Table II. For all the following experiments except the one that studies the voltage's influence, the pulse voltage was set to 190 V. The pulse width was set to 10 ns, which is shorter than the 17 ns clock period (for a 56 MHz clock frequency). In the following paragraphs, we detail the separate influence of some of these parameters. This experiment is performed at the scale of a single load instruction which loads the value 0x12345678 from the Flash memory into the register R8. This fault injection has been performed over a 20 ns time interval, by steps of 200 ps. The probe browsed a 3 mm square over the circuit's die, by steps of 200 µm. Fig. 3 shows the results for this experiment.

Table II: Experimental parameters

The experiment shows that there are four kinds of outputs, depending on the probe position and the injection time : no fault on the loaded value, a crash of the microcontroller, the triggering of a Usage Fault exception, and a fault on the value in R8. Very few faults on the register R0 were also observed. Except from R8 and R0, no other register was faulted in this experiment. Moreover, those two registers were never faulted together. Every faulty output we observed on R8 has a higher Hamming weight than the 0x12345678 expected value. On Fig. 3, yellow areas led to a small increase in this Hamming weight and red areas led to a high increase. This experiment highlights the local effect of electromagnetic fault injection on a microcontroller, with different effects depending on the probe's position. Since very few probe positions can lead to a successful fault injection, this spatial cartography also helps us to find some suitable X Y Z configurations for the following experiments.

2) Injection time: This experiment has been performed on the following test program for a fixed X Y Z position. This program uses a loop to sum the elements of an array that contains eight powers of two. array[i] contains 2 i . At the end of the computation, the result stored at the address pointed by r0 contains 0xF F . This test program requires about 3.5 µs to complete. We performed this fault injection over this time interval, by steps of 200 ps. • BusFault or UsageFault hardware interrupts • A fault on the output value • A normal behaviour with no fault Every fault we observed on the output value corresponds to an execution in which only one power of two has not been added. However, many faults could explain such results. That is why the precise effect of electromagnetic fault injection at the scale of a single instruction is studied precisely in section IV.

3) Pulse characteristics: In the following paragraphs, we study the separate influence of the pulse parameters. For these paragraphs, a fixed position was set for the injection probe. This position had been found thanks to the spatial cartography presented in III-B1.

Pulse width: The pulse width does have an influence on the outputs. According to Faraday's law of induction, the electromotive force induced in a loop (e.g. inside the power grid) corresponds to the time-derivative of the magnetic flux transmitted by the injection antenna. This magnetic flux is proportional to the current sent into the injection solenoid. Thus, the electromagnetic glitch that is transmitted to the circuit depends on the current's variations. We also observed that sending longer pulses reduces the stress applied to the circuit.

Pulse voltage: To evaluate the influence of the pulse voltage, the test program has been set to a single LDR assembly instruction. LDR R_o,[R_i,#offset] loads the value pointed by R_i with offset #offset into the register R_o. For the test instruction, the register R_i pointed to a Flash memory address. To perform an analysis of the impact of the pulse's voltage, we needed to fix a suitable configuration for the other parameters. Those other parameters were set to some fixed values: we chose a configuration in which a fault occurs on the loaded value. For this experiment, the tested instruction was LDR R4,[PC,#44]. The inital value of R4 was 0x0 and PC+44 was a Flash memory address which contained 0x12345678. Since metastability This pattern is highlighted by Fig. 5, which shows the Hamming distance with the 0x12345678 expected value versus the pulse's voltage. The same kind of trend has been obtained for different values for the probe position and the injection time. However, it seems that only instructions which loads a value from the Flash memory can lead to this kind of set at 1 fault. Indeed, we did not manage to inject similar faults in case of a data transfer from the SRAM memory. 4) Type of the executed instructions: Our experiments highlighted a significant trend: we managed to inject faults on different types of instructions such as branch instructions, ALU instructions or load-store instructions. However, load instructions from the Flash memory were significantly easier to fault. The microcontroller we use has a Harvard architecture. Every instruction fetch uses the instruction bus. Moreover, load instructions also use the data bus in the decode pipeline phase. As a consequence, section IV provides a more detailed study of the consequences of this fault injection in two cases: one case to highlight a fault on the instruction bus, another one to highlight a fault on the data bus. On the one hand, we study the effects on a generic single instruction. On the other hand, we study the specific case of a load instruction from the Flash memory.

IV. EXPERIMENTS ON THE DATA AND INSTRUCTION BUS

The two following subsections detail the results we obtained when trying to inject faults into the control flow or the data flow of the target program. In order to minimize the side effects which may happen when studying a big number of assembly instructions, the following results have been obtained for two classes of test applications. To highlight faults on the control flow, we use a sequence of NOP instructions [START_REF] Spruyt | Building fault models for microcontrollers[END_REF]. Since NOP instructions have no effect, a faulty output will be easier to notice and to explain. To highlight faults on the data flow, the test application we use is a single LDR instruction which loads data from memory into a register. The initial values at the beginning of our target function are detailed in Table IV. Those beginning values are the same for the two following experiments. The comparison between the initial values, the output ones and the expected ones helps us to have a better understanding of possible instruction replacements effects.

Table IV: Initial values at the beginning of the execution

Piece of data Value r0

A memory address in RAM r1 to r4 0x1 to 0x4 r5 and r6

Not relevant r7 0x100 r8 to r12 0x00 Address pointed by r0 0x00

A. Faults on the program flow

Faults on the program flow can be observed through instruction replacement faults thanks to the simulation. However, studying instruction replacement with two possible instruction sizes is a very tough task. Since every fetch from the code memory is 32-bit wide, we need to consider several instruction replacement scenarios. With this approach, we can simulate the replacement of a 16-bit or 32-bit instruction by another 16-bit or 32-bit instruction. However, two 16bit instructions might be replaced by two different 16-bit instructions. Similarly, a 32-bit instruction might be replaced by two 16-bit instructions. Those two cases would imply performing an almost-exhaustive search over 32 bits, which is not practical in our case. Though, we could partially bypass this problem by recording the number of clock cycles in our experiments. However, guessing the number of executed instructions from the clock cycle count is not an easy task because of the complex instruction set. Observing this clock cycle count could theoretically enable us to exclude some replacement scenarios in further experiments. To highlight the possibility to inject faults on the program flow, the following experiment targeted a NOP sled. Since different position probes and different injection times lead to different results, the following results have been found for different experimental configurations of these parameters.

1) Hardware exceptions: Our fault injection sometimes led to an exception triggering. However, only Usage Fault exceptions were observed. More precisely, the No coprocessor exception and the Undefined instruction exception where the only subclasses of Usage Fault which could be observed. Both of these exceptions happen in the case of an invalid opcode. A possible explanation would be that a fault has been injected during the fetch or decode pipeline phases.

2) Memory address: In the initial state before the target instruction, r0 points to a memory address in SRAM. The value of r0 has been observed at this address instead of the expected value. For this particular case, instruction replacement simulation showed that the only possible instruction replacement is STR r0,[r0,#0], which stores the value of r0 at the address pointed by r0 without any offset. Moreover, the value 0x100 has also been observed for another configuration. It turns out that 0x100 is also the value in r7.

3) Other faults: We also obtained faults on the generalpurpose register r7 and the program counter r15. These faults can also be explained by at least one assembly instruction replacement.

4) Summary: Obviously, the previous paragraphs do not aim at providing a complete list of the possible faults. Because of the huge number of possible configurations for the injection parameters, computing fault occurrence percentages would not be relevant. Nevertheless, these paragraphs highlight the fact that very few fault patterns were observed. We never got any fault on r1-r6 and r8-r14. In an informal way, faults on r7 and r15 (pc) appeared much more often than faults on the memory address pointed by r0. Most of the 16-bit instructions can only manipulate the registers r0 to r7. For example, a MOVS r7, #FF operation is assembled into a 16-bit instruction, while a MOVS r8, #FF is assembled into a 32-bit instruction. In a 16-bit instruction, r7 is encoded by a 111 binary sequence. The fact that registers r0-r6 are encoded with a smaller number of 1 in their encoding slot might explain this higher fault occurrence rate on the r7 register. Similarly, branch instructions have many 1 in their slot. As a conclusion for this set of experiments, every faulty result we observed has at least one instruction replacement which can explain it. The first intuition of a set at 1 fault model we saw for data fetches leads us to a more detailed analysis of the pipeline stages in section V.

B. Faults on the data flow

For this experiment, we targeted a single LDR r4,[PC,#44] instruction. The inital value of R4 was 0x0 and PC+44 was a Flash memory address which contained 0x12345678 (this experiment used the same configuration as the one we had defined in III-B3). We obtained several faulty outputs such as 0xFE345678 or 0xFFF45678. We consider that every fault which cannot be explained by an instruction replacement is a fault on the data flow. In this experiment, the target LDR r4,[PC,#44] is a 16-bit instruction, followed by a 16-bit NOP instruction. The Thumb2 instruction set can only output a limited set of constants in a single data-processing instruction [START_REF] Arm | ARM Architecture Reference Manual -Thumb-2 Supplement[END_REF]. Thus, some of the faulty output values we observe, such as 0xFFF45678, could theoretically only be loaded with a single load from indirect register. Since the whole memory does not contain any FFF4 pattern, a single load instruction could not explain this result. We performed an exhaustive search over the 16-bit and 32-bit instructions. No single instruction can lead to a result of 0xFFF45678. However, fault injection might have had an impact on two 16-bit instructions. To handle this issue, we performed another experiment, in which the target instruction was a LDR r8,[PC,#44], with 0x12345678 stored at the address PC+44. Using r8 instead of r4 makes this instruction be assembled as a 32-bit instruction. Except the stack manipulation instructions, no 16-bit instruction can write a value into registers between r8 and r12. For this new configuration, we were able to obtain several faulty values, such as 0xFFF45679 or 0xFFFC5679. With an exhaustive simulation, we can now guarantee that no single instruction can lead to such a result. Since a part of the faulty value is similar to the expected one, we can assume this fault injection had an impact on the data flow.

C. Analysis at a lower abstraction level

Underpowering a circuit or overclocking it leads to the same kind of timing violation faults [START_REF] Zussa | Investigation of timing constraints violation as a fault injection means[END_REF], but knowing which among the clock tree or the power grid has been faulted is a tough task. To the best of our knowledge, recent research papers such as [START_REF] Poucheret | Local electromagnetic coupling with CMOS integrated circuits[END_REF] claimed that the coupling between the injection probe and the circuit lies mainly in the power distribution network. According to the experiments from the previous section, electromagnetic glitch fault injection seems to enable us to perform attacks whose effect is equivalent to voltage or clock glitches, with a local effect that enables us to target either the instruction bus or the data bus. The following section deeply studies the bus transfers and provides an explanation for the faults we observed at a register-transfer level. The results presented in section IV lead us to the basics of a definition of a fault model at the assembly level. By using this fault injection technique, an attacker can inject faults in two ways: modify the instruction to be executed or modify a data value in the case of a load instruction.

Clock

Our experiments also highlight another trend: we only managed to inject faults on data and instruction transfers from the Flash memory. The Flash memory has a slower reponse time than the SRAM memory. The fetch pipeline phase always requires a transfer from the instruction memory [START_REF] Yiu | The Definitive Guide To The ARM Cortex-M3. Elsevier Science[END_REF]. The operand fetch operation is performed during the decode phase. For load instructions, the decode phase requires a transfer from the data memory.

The microcontroller we use is based on a modified Harvard architecture, with separate buses for instruction and data. The buses are 32-bit wide and use the AMBA AHB-Lite structure [START_REF] Arm | AMBA 3 AHB-Lite Protocol[END_REF]. Since electromagnetic glitch injection creates timing faults [START_REF] Dehbaoui | Electromagnetic Transient Faults Injection on a Hardware and a Software Implementations of AES[END_REF], we propose an explanation of the experimental faults we obtained based on a bus transfer analysis.

A. Instruction fetches

Fetching a piece of data or an instruction from the memory (either SRAM or Flash) requires at least two clock cycles. Fig 6 shows a chronogram of the AHB bus tranfers when executing the target program. In this case, the target program is a NOP sled. Since instruction fetches are 32-bit wide, two 16-bit NOP instructions are fetched at each execution of the fetch pipeline stage. In the case of instruction which do not require an operand fetch, the decode and execute pipeline stages require at most half a clock cycle. The fetch stage requires one clock cycle during which the instruction address is written on the HADDRI bus. It also requires an extra clock cycle in which 32 bits from the instruction memory are written on the HRDATAI bus [START_REF] Arm | AMBA 3 AHB-Lite Protocol[END_REF]. In the event of a transfer from the SRAM memory, the values are written on the HRDATAI bus at the beginning of this extra clock cycle. Since the Flash memory has a longer response time, this value is written on the bus at the end of this clock cycle for a Flash transfer. In this situation, since electromagnetic fault injection leads to timing faults [START_REF] Dehbaoui | Electromagnetic Transient Faults Injection on a Hardware and a Software Implementations of AES[END_REF], the critical path appears to be this HRDATAI bus transfer. We now consider the result presented in IV-A, in which a NOP is replaced by a STR r0,[r0,#0]. The binary encodings for the NOP and STR r0,[r0,#0] instructions are presented in Table V. As seen for an attack which targets the value loaded by a load instruction, it seems that the higher the stress we apply, the higher the fetched word's Hamming weight is. However, the situation seems different for instruction fetches. The fault models seems more complex than the set at 1 model we had seen for data fetches.

The bus precharge values are not specified in the AHB bus intellectual property. They are chosen by the circuit's manufacturer. For the microcontroller we use, the HRDATAI bus does not seem to be precharged at 1, since a NOP instruction with a Hamming weight of 7 has been replaced by another instruction whose Hamming weight is 2. Moreover, since there must be some skew on this bus, some metastability phenomena (as presented in III-A) also appear. Considering this single example, a possible precharge value would be 0, or the microcontroller might use a more complex precharge strategy. For the moment, we are not able to infer more details about a possible HRDATAI bus precharge. To sum up, in the case of a bus transfer from the Flash memory, the critical path that is faulted by an electromagnetic fault injection seems to be the HRDATAI bus transfer. Thus, this fault injection can target any instruction fetch from the Flash memory, which potentially makes this attack scenario very harmful.

B. Data fetches

The situation for data fetches is very similar to the one we describe for instruction fetches. Since electromagnetic fault injection has a local effect, it is possible to find a probe position where we only inject faults on the data bus and do not reach the instruction bus. For this attack scenario, the critical path seems to be the HRDATA bus transfer. Fig. 7a shows data bus transfers in the case of a single LDR instruction (similar to the previous experiments) without fault injection. Fig. 7b shows the same bus transfers in the case of a fault injection.

Metastability phenomena also appear for this fault injection, but the global trend corresponds to a set at 1 fault model. This value depends on the microcontroller's bus precharge strategy, which is specific to each implementation. This trend enables us to define a more precise fault model for data fetches, in which the attacker can bring the loaded value closer to the value of the bus precharge.

VI. RELATED WORKS

This section outlines some research papers that are related to the study we presented in this paper. These papers are grouped into three subcategories: electromagnetic fault injection techniques, fault models on microcontrollers and proposed contermeasures against a given fault model.

1) Electromagnetic fault injection: In [START_REF] Dehbaoui | Electromagnetic Transient Faults Injection on a Hardware and a Software Implementations of AES[END_REF], Dehbaoui et al. do a practical fault injection on a software implementation of the AES algorithm by using electromagnetic glitches. In [START_REF] Carlier | Electro Magnetic Fault Injection[END_REF], Carlier performs a study of the effects of electromagnetic fault injection on two microcontrollers at an electric level. His work mostly explains the influence of several parameters related to the coil. He also studies the influence of the injection time. However, his study does not focus on the faults that were produced.

2) Fault models on microcontrollers: In [START_REF] Barenghi | Low Voltage Fault Attacks on the RSA Cryptosystem[END_REF], Barenghi et al. study the effects on low-voltage fault attacks on an ARM9 microprocessor. They describe several effects on loads from memory or on instruction replacement. In [START_REF] Balasch | An Indepth and Black-box Characterization of the Effects of Clock Glitches on 8-bit MCUs[END_REF], Balasch et al. present a black-box approach which is quite similar to the one proposed in this paper. They use clock glitches as a fault injection mean and perform their experiment on a 8-bit microcontroller. We also use the same kind of in-depth analysis. However, their study is performed on a very different architecture with a different bus precharge configuration. We also automated the instruction replacement search by performing an exhaustive instruction replacement simulation over the instruction set. In [START_REF] Spruyt | Building fault models for microcontrollers[END_REF], Spruyt proposes an approach whose aim is to define a generic method on how to build a fault model for microcontrollers. His situation is also quite similar to the one presented in this paper. Since having access to some internal data on a real microcontroller may be hard, he proposes a way to obtain information about the induced faults by analyzing the faulty outputs of different groups of instructions. Several articles have been published in which the authors assume an attacker can skip or replace an instruction by another one [START_REF] Schmidt | A Practical Fault Attack on Square and Multiply[END_REF] [START_REF] Schmidt | A Fault Attack on ECDSA[END_REF]. For example, in [START_REF] Berzati | Fault analysis of Rabbit: toward a secret key leakage[END_REF], Berzati et al. suppose an attacker can replace an addition instruction by an exclusive or instruction.

3) Countermeasures: Several countermeasures schemes have been defined to protect embedded processor architectures against specific fault models. All those countermeasure schemes might be reinforced by studies similar to the one presented in this paper, which could provide a more precise knowledge about the fault model. At a hardware level, [START_REF] Nguyen | Low-cost recovery for the code integrity protection in secure embedded processors[END_REF] proposes to use integrity checks to ensure that no instruction replacement took place. Nevertheless, many countermeasures to protect assembly code without modifying the microcontroller's architecture have been defined. In [START_REF] Barenghi | Countermeasures against fault attacks on software implemented AES[END_REF], Barenghi et al. propose three countermeasure schemes based on instruction duplication, instruction triplication and parity checking. Their countermeasures enable different levels of fault detection and correction against instruction skips or some instruction modifications. In [START_REF] Medwed | A Generic Fault Countermeasure Providing Data and Program Flow Integrity[END_REF], Medwed et al. propose a generic approach based on the use of specific algebraic structures named AN+B codes. Their approach enables to protect both the control and data flow. An application to an AES implementation has also been detailed in [START_REF] Medwed | A Continuous Fault Countermeasure for AES Providing a Constant Error Detection Rate[END_REF].

VII. CONCLUSION

We have presented a detailed study about the effects of an electromagnetic glitch fault injection on a state-of-the-art microcontroller. However, working with a real microcontroller in a black-box approach creates several constraints when trying to build a practical experimental process. Because of the lack of details about the microcontroller's design and architecture, we have proposed this top-down approach which aims at building a suitable lower-level explanation for the faults we observed at an assembly level. Moreover, we also lack information about the bus precharge strategy on the microcontroller we use. Future experiments will try to use more advanced debug techniques in order to get more accurate information about the executed instructions.

Finally, we do not claim this register-transfer level hypothesis is the only reason why faults appear at an assembly level. This paper aims at providing a first understanding of the faults an electromagnetic glitch fault injection can induce on an embedded program. And the lower-level model we propose could explain all the previous experimental results we obtained. Furthermore, this fault model looks very similar to the ones which can be found in previous works about clock or voltage glitches. Hence, electromagnetic glitches seem to induce timing constraints violations on the bus transfers from the Flash memory. Thus, on a standard circuit, electromagnetic fault injection could enable an attacker to bypass some countermeasures against traditional timing fault injection means such as clock or voltage glitches.

These experiments confirm the fact that an attacker could change an instruction into another one and change the value of a piece of data loaded from the Flash memory. But they also provide a more accurate fault model, in which some instructions or registers seem to be more vulnerable than others. On this architecture, faults on the data flow lead to an increased Hamming weight on the loaded piece of data. This behaviour highly depends on the microcontroller's bus precharge strategy. These observations can lead to the definition of an assembly-level fault model, and enable to build more specific and accurate countermeasures. These ideas will be studied more precisely in future works.

Figure 1 :

 1 Figure 1: Electromagnetic fault injection bench

Figure 2 :

 2 Figure 2: Our approach to characterize the injected faults

Figure 3 :

 3 Figure 3: Impact of the probe's position

Figure 4 :

 4 Figure 4: Influence of the pulse's injection time for an array sum whose expected result is 0xFF

1 a 5 s

 15 d d i t i o n l o o p : 2 l d r r4 , [ r2 , r1 , l s l #2 ] ; r4 = array[i] 3 l d r r3 , [ r0 , #0 ] ; r3 = result 4 add r3 , r 4 ; r3 = r3 + r4 a d d i t i o n l o o p This test program enables us to perform an electromagnetic fault injection on a sample made of different instructions. The results for this experiment are shown in Fig. 4. Three kinds of situations have been observed:

Figure 5 :

 5 Figure 5: Hamming distance with 0x12345678 versus pulse's voltage

FETCHFigure 6 :

 6 Figure 6: Bus transfers on the AHB bus for instruction memory

Figure 7 :

 7 Figure 7: Bus transfers on the AHB bus for data memory

  .

		Exhaustive instruction simulation
		(finds instructions which could
		enable to reach B' from A)
				B'	Experimental fault (depends on the
		Fault injection			experimental parameters)
	Initial state	A	Instruction	B	Expected state

Table I :

 I Metastability phenomenon for a single load instruction

	Loaded value	Occurrence rate
	1234 5678 (no fault)	60.1%
	FFF4 5679	27.4%
	FFFC 5679	12.3%
	FFFC 567b	0.1%
	FFFC 7679	0.1%

Table III :

 III Influence of the pulse's voltage

	Pulse voltage	Loaded value	Occurrence rate
	170 V	1234 5678 (no fault)	100%
	172 V	1234 5678 (no fault)	100%
	174 V	9234 5678	73%
	176 V	FE34 5678	30%
	178 V	FFF4 5678	53%
	180 V	FFFD 5678	50%
	182 V	FFFF 7F78	46%
	184 V	FFFF FFFB	40%
	186 V	FFFF FFFF	100%
	188 V	FFFF FFFF	100%
	190 V	FFFF FFFF	100%

Table V :

 V Binary encoding of NOP and STR r0,[r0,#0]

	Mnemonic	Inst.	Binary instruction	Hamming w.
	NOP	BF00	10111111 00000000	7
	STR r0,[r0,#0]	6000	01100000 00000000	2


Rafik Makhloufi

Guillaume Doyen

Grégory Bonnet

Dominique Gaïti

Impact of Dynamics on Situated and Global Aggregation Schemes

Keywords: Autonomic Networking, Decentralized Aggregation, Situated View, Management Information

Recently, numerous management approaches have emerged in order to manage networks and services in a decentralized and autonomous way. Some of them propose to minimize their cost by using a situated view when collecting aggregates for the decision making process, while others propose to improve their accuracy by using a more conventional approach which is global view. So far, little attention is given to the evaluation of situated view while many studies propose to evaluate global approaches. As a consequence, there is no work in the literature that compares the performance of situated and global aggregation schemes. Being able to choose the suitable approach for a given context is still a real challenge. Mastering it will ensure the efficiency of the autonomous management system. In this paper, we present a comparative study of situated and global schemes deployed over large scale and dynamic networks. We consider two factors: network and information dynamics. We implement typical aggregation schemes from each category and then we compare them according to the accuracy of the estimated aggregates and the efficiency of the decision making process.

Introduction

In the context of autonomous network management which is one of the most relevant class of management approches, the decentralized Autonomic Managers (AMs) are based on the control loop functions Monitor, Analyze, Plan, Execute (MAPE) [START_REF] Kephart | The Vision of Autonomic Computing[END_REF]. Information used in the monitoring can come from both the local managed element itself or be the result of an aggregation of environmental informations provided by remote AMs. Two concurrent strategies are commonly deployed for this purpose. On one hand, it can be the result of a process involving all nodes in the network, thus providing a global view (GV), standard supporting algorithms that rely on tree and gossip schemes. These global schemes are expected to provide a good accuracy at the cost of a larger convergence time and overhead. On the other hand, the monitoring process can only consider a limited neighborhood, thus providing a situated view (SV). Approaches based on SV are expected to minimize their cost and to provide a high reactivity to AMs with a low accuracy.

To date, there is no evaluation in the literature that compares the cost and the performance of situated and global aggregation schemes since the former have appeared recently. Thus, we do not know the exact behavior and the performance of these schemes while it is essential to precisely identify the appropriate context in which each of the aggregation categories performs better to design and deploy efficient autonomous management frameworks.

In this paper, we provide a comparative performance analysis of situated and global aggregation schemes. Since results coming from the use of such schemes in a static context are given by the protocols complexity, we focus our work on the resilience of such schemes to both the network and aggregated information dynamics. To this end, we implement three typical aggregation schemes, one situated view based and two global view based, i.e., gossip and tree. Then, we compare them according to two important performance criteria related to autonomous monitoring and control which are respectively the accuracy of the estimated aggregates and the efficiency of the decision making process.

The remainder of the paper is organized as follows. Section 2 presents the related work on the evaluation of aggregation schemes. Section 3 describes the aggregation schemes that we implement from each category. In section 4, we propose an evaluation of the developed schemes. Finally, in Section 5 we conclude and we present our working perspectives.

Related work

Several research efforts propose to compare the performance of global aggregation schemes. The closest works to ours are given below.

In [START_REF] Bawa | Estimating aggregates on a Peer-to-Peer network[END_REF], the authors propose a set of aggregation schemes for estimating aggregates on a P2P network. They compare one gossip-based scheme Propagate2All to two other tree-based schemes: SingleTree and MultipleTree. This comparison shows that tree schemes outperform gossip ones in terms of convergence time, communication and computation costs, but they are less resilient to faults under a dynamic network. However, this study does not discuss the situated schemes.

A second work [START_REF] Wuhib | Robust monitoring of networkwide aggregates through gossiping[END_REF] proposes a comparison between GAP (Generic Aggregation Protocol), a basic tree-based aggregation protocol and G-GAP (Gossipbased GAP), a gossip-based protocol for continuous monitoring of aggregates. Surprisingly, in opposition to the first study, this evaluation shows that, for comparative overhead, the tree-based scheme GAP outperforms the gossip protocol G-GAP both in terms of accuracy and robustness even under a dynamic network.

Another study of the performance of aggregation schemes [START_REF] Birman | The promise, and limitations, of gossip protocols[END_REF] discusses the strengths and limitations of gossiping. According to this characterization, gossip schemes present simplicity, bounded load on nodes, topology independence, ease of local information discovery and finally robustness to transient network disruptions. But, the small bounded message sizes and the relatively slow periodic exchanges limit the information carrying capacity of a gossip algorithm. Furthermore, gossip scales well in some dimensions but not for all. A node failure can also delay or even defeat the aggregation. This study provides only a qualitative analysis of the gossip's limitations and strengths without giving any quantitative result.

We recently proposed in [START_REF] Makhloufi | Situated vs. global aggregation schemes for autonomous management systems[END_REF] an evaluation study of typical global and situated aggregation schemes that we implemented in the context of a static environment. This work offers quantitative results on the costs and the performance of aggregation. However, this study does not compare these schemes in the context of a dynamic environment.

Globally, these studies address the global aggregation schemes but never compare them to the situated ones while the latter is massively used in autonomous management frameworks. Thus, we do not know the exact behavior and the performance of the situated schemes in comparison to the global ones. Situated schemes are expected to provide a high reactivity to AMs by minimizing the amount of maintained information by each AM. As for global schemes, they are expected to provide a good accuracy at the cost of a larger convergence time. Through this, we clearly observe that it is essential to precisely identify the appropriate context in which each category performs better in order to be able to design efficient management frameworks.

Developed aggregation schemes

In order to show under which conditions an aggregation approach outperforms the others, we implement and compare state of the art typical schemes that can be used for the computation of any aggregate function. In this section, we give a brief overview of them. The notations used in these algorithms are summarized in Figure 1.a.

Global view

In global aggregation schemes, each node collects information from the entire network. According to the global data structure, these schemes are either tree or gossip-based.

Tree We implemented a simple push tree-based aggregation scheme that uses the typical aggregation process of GAP under the DHT-based deployment topology proposed in [START_REF] Makhloufi | Towards a P2P-based Deployment of Network Management Information[END_REF]. The latter is a structured P2P overlay where nodes communicate their local aggregates to a single root node that computes an overall aggregate and spreads it on all the interested nodes through a publish-subscribe mechanism. As shown in Algorithm 1, which describes the developed tree-based scheme, one active and one passive threads are executed on each node. The first one initiates the aggregation process by sending the value of each node to its parent. The second one waits for messages sent by an initiator to process them. Initially, each node i selects its parent p with the help of the getParent() method and sends it a couple < X i , 1 > on the form < aggregate, weight > as given in lines a.1 and a.2. A node i that receives a message from a child node j computes a new partial aggregate according to a given aggregate function, updates its local state with the new values and then forwards them to its parent p as shown in lines b.2 to b.5. If node i is the root then it waits until it receives all its children's aggregates and it diffuses the computed global aggregate X i over a publish-subscribe system on all the interested nodes as given in lines b.6 to b.9. Thus, each node that receives X i from the root updates its partial aggregate with the global one as shown in lines a.3 and a.4. Gossip Unlike tree-based techniques where nodes are organized into a tree, gossip-based schemes do not require a particular structure to perform aggregation. In each round of a gossip, a node contacts one or more of its neighbors usually chosen randomly and exchanges information with them [START_REF] Birman | The promise, and limitations, of gossip protocols[END_REF][START_REF] Dietzfelbinger | Gossiping and broadcasting versus computing functions in networks[END_REF][START_REF] Kempe | Gossip-based computation of aggregate information[END_REF]. Initially, each node in the network has only its own raw management information. When messages are exchanged, nodes compute new partial aggregate and then decrease the variance over the set of all aggregates in the system. The gossip aggregation algorithm converges when the global aggregate is computed and available across all the network nodes.

In this category, we implemented a push-pull gossip scheme based on a typical gossip scheme [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF]. As illustrated in Algorithm 2, with the help of the getNeighbors(1) method that selects uniformly at random one node j from a list of direct neighbors D i , each node i sends to j a message containing its partial aggregate X i and waits for a response as shown in lines a.2 and a.3. When i receives a response (X j , j) from j, it updates its local state through the update() method that computes a new partial aggregate according to the selected aggregate function as given in lines a.4 and a.5. The node i waits for a certain time and repeats the same process (line a.6). Similarly, when the passive thread of a node i receives an exchange request message, it replies with its local aggregate X i and then it updates its local state as shown in lines b.2 to b.4.

Situated view

In opposition to the global schemes where global aggregates are computed over the entire network, situated view approaches like [START_REF] Leitao | Large-Scale Peer-to-Peer Autonomic Monitoring[END_REF][START_REF] Macedo | A Knowledge Plane for wireless ad hoc networks[END_REF][START_REF] Bullot | A situatedness-based knowledge plane for autonomic networking[END_REF] propose to reduce the costs of aggregation by limiting the knowledge of a node to a bounded neighborhood. Thus, apart its own local information each node collects data from its direct neighbors or a subset of the network nodes to compute a partial aggregate representing its view.

In this category, we implemented a typical situated scheme inspired from the membership protocol HyParView (Hyper Partial View) [START_REF] Leitao | Large-Scale Peer-to-Peer Autonomic Monitoring[END_REF] where each node maintains two views. In our implementation, each node executes Algorithm 3 to collect information from its view and then to compute a partial aggregate. As shown in Algorithm 3, each node i sends a query message containing the maximum number of hops h to all its direct neighbors obtained through the getNeighbors(all) method as given in lines a.1 and a.2. A node i that receives a request from j verifies if it does not previously answer to the same request (line b.2). If so, i answers by sending a response (X rawi , j) directly to the requesting node j (line b.3). The node i decrements the value h and tests if the maximum number of hops is not reached and then forwards the received request to all its direct neighbors as given is lines b.4 to b.8. When a requesting node i receives an answer (X rawj , j) from a neighbor j, it computes a new partial aggregate and updates its own state as shown in lines a.3 and a.4. send (Xraw i , j) 4:

h←h -1 5:

if (h > 0) then 6:

Di←getNeighbors(all)-{j} 7:

send(h, Di) 8:

end if 9: end loop

In this section, we present the evaluation study that we carried out to compare the performance of the previously described aggregation schemes in terms of the accuracy of the estimated aggregated and the efficiency of the decision making process in a dynamic environment.

Dynamics factors

We identify two important factors that can affect the performance of an aggregation process: network and information dynamics. For this, we propose to use the following models.

Network dynamics The network dynamics, or churn, consists in the nodes arrivals in the system and their departures that can be planned or due to a sudden failure. Based on the analysis of the traces on different systems like mobile ad-hoc networks (MANETs) and P2P ones, many prior studies assumed a Poisson process of parameter λ for the node arrivals and an exponential distribution of parameter µ for the departures [START_REF] Leonard | On lifetime-based node failure and stochastic resilience of decentralized peer-to-peer networks[END_REF][START_REF] Li | A performance vs. cost framework for evaluating DHT design tradeoffs under churn[END_REF][START_REF] Rhea | Handling churn in a dht[END_REF]. Thus, we adopt the same models in our experiments and we choose the values of arrival and departure rates so that they accurately represent existing networks. The values of λ and µ are chosen so that the average number of nodes, given by N=λ/µ, will always be equal to 500. Thus, in our study λ varies in [0.0041;0.4166] and µ is ranging in [8.33 × 10 -6 ;8.33 × 10 -4 ], corresponding respectively to average inter-arrivals (1/λ) ranging in [2.4;240] seconds and to average lifetime durations (1/µ) in the range [20;2000] minutes.

Information dynamics It determines the evolution degree of a management information over the time. It can be characterized through two criteria: (1) the changing frequency of the values on managed elements, for example a value X rawi that changes every 1sec; (2) the changing degree of these values that is defined by the distance between two consecutive values. We generate realistic local values according to a triangular signal that could stand for a gauge associated, for example, to the quantity of traffic in a network. Thus, X rawi is periodically incremented by α until reaching 100 and it is then decremented by the same α until 0. This allows us to control the information dynamics level. The local values are ranging in [0;100] for an α that we vary in [0.02;5].

Simulation setup and evaluation scenarios

In order to evaluate the performance of the investigated aggregation schemes under realistic conditions, we carry out our experiments on the FreePastry simulator, an implementation of the Pastry DHT [START_REF] Rowstron | Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems[END_REF]. All simulations are done under the Euclidean network topology model, where nodes are randomly placed within a 2-dimensional plane in a uniform way. Concerning the tree-based scheme, we also rely on Scribe [START_REF] Castro | Scribe: a large-scale and decentralized application-level multicast infrastructure[END_REF] to build and maintain a multicast tree that allows the diffusion of the root's global aggregates on all nodes that subscribed to the same diffusion group concerning the monitored variable.

Based on the realistic parameters summarized in Figure 1.b, we create a network where each node executes the previously described aggregation schemes to compute an average aggregate of the local values on nodes. We execute the situated scheme with a view limited to the direct neighbors (SV1) and also with a neighborhood limited to 2 hops (SV2). The gossip process is executed with rounds of duration 600ms that corresponds to the maximum time for to exchange and process an information between two nodes. The neighborhood degree in each scheme is limited to 8 neighbors per node. It is on the form 2×2 b of Pastry where b=2. The maintenance frequency of this neighborhood is fixed to 60 seconds like the one used by FreePastry to maintain the leaf sets. Concerning the local raw values, we assume that each 1sec a new value is generated on each node. In all our simulations, a 95% confidence interval is computed for each average value represented in the curves. These intervals are plotted as error bars.

Evaluation results

We propose here to compare the developed aggregation schemes according to their costs and according to two other important criteria, the accuracy of estimated aggregates and the efficiency of the decision making process.

Cost of situated and global schemes Considering the cost of the aggregation schemes in a static context allows us to have a first idea on their expected performance in a realistic dynamic environnement. To this end, we compare the previously described schemes in the context of a static environment according to convergence time and communication cost. We notice in Figure 2.a that the convergence time is proportional to the number of nodes in the network. Under a network of 1000 nodes, gossip's convergence time is about 6 times higher than the one of the tree and about 23 times the one of SV2. This high delay is caused by the blind communication used to exchange messages at each round of gossip. As expected, the situated scheme, with a comparable delay between SV1 and SV2, is more scalable and converges more quickly than the global ones, because in a situated view only partial aggregates are computed by nodes. However, we see in Figure 2.b that SV2 involves more messages than the global schemes because it is based on a broadcast algorithm where each node floods its request message on all its h-hops neighbors. Numerically, under a network of 1000 nodes, the communication cost of SV2 is almost 3 times higher than the one obtained in the case of gossip and about 42 times the one of the tree. The tree causes the lowest communication cost, which corresponds to the messages sent in a bottom-up fashion to the root and those used by Scribe to spread the global aggregate. Accuracy of estimated aggregates We define it as the precision level of the aggregation scheme when computing global or situated aggregates. In order to evaluate the impact of network and information dynamics on this criterion, we look at the distribution of estimates over all the network nodes and we measure the distance between estimated aggregates and the actual global aggregate that should be computed. Thus, we show how far these estimates lie from the real average value by computing the average deviation

D X = 1 N N i=1 |X i -X|.
By varying the information dynamics level within a static network of 1000 nodes, we obtained the results shown in Figure 3.a. We see that, with a deviation that reaches 2 when α=5, tree is about 5 times more accurate than SV1, about 3 times more than SV2 and almost twice more than gossip. Thus, it is the most accurate scheme under dynamic information. The situated scheme is less accurate than the global ones. This is caused by the computation of partial aggregates. Indeed, the deviation never reaches 0 like in the case of global schemes even under a static network and information. As predicted in [START_REF] Birman | The promise, and limitations, of gossip protocols[END_REF], gossip is more sensitive to the information dynamics than the tree. But we do not clearly see here the evolution of the accuracy in function of the information dynamics level. When we consider random fixed values on nodes (i.e. α=0) and we vary the network churn level, we obtain the deviation measures illustrated in Figure 3.b. We notice that in the case of the tree-based scheme, the network dynamics dramatically affects the accuracy of estimated aggregates with a deviation that reaches 24. This sensibility is caused by the departures and arrivals of nodes causing the continuously maintenance and reconstruction of the tree, whatever the churn level. The situated scheme is more resilient to churn than gossip and tree since we register the same deviation for it in the case of static and dynamics environments. Thus, SV2 is about 4 times more accurate than the tree and about twice more than SV1. This is explained by the fact that, in the situated scheme, a departure or an arrival of a node does not necessarily affect other nodes if it is not in their view. For the gossip, the deviation is proportional to the churn level because it is a community process where nodes are dependent upon the correct behavior of all other nodes. However, it is still the most accurate scheme under a low churn level where the average lifetime and inter-arrival are respectively higher than 200min and 24sec. In the other interval, SV2 is the most accurate.

Efficiency of the decision making process In order to evaluate the efficiency of the decision making mechanism when using each of the implemented aggregation schemes, we implemented a simple threshold-based decision mechanism standing for a realistic case of control operations where each node makes decisions according to its last computed aggregate. The local values of managed elements are periodically retrieved by the AM to be used by the aggregation process (AP) and then by the decision process (DMP), as shown in Figure 4. According to Algorithm 4, each node i consults its local aggregate and makes a decision according to the defined threshold 50 (lines 2 to 7). Node i waits a certain time before renewing the same operation (line 8). At the end of the aggregation process, we compare the resulting decisions on each node to the one that should be made in the case where we use the current actual global aggregate. Thus, we count the number of decentralized decisions that do not match with the actual one (i.e. the number of faulty decisions). Under the same test conditions as in the evaluation of the aggregation accuracy, we obtain the results presented in Figure 5. We observe in figure 5.a that the number of faulty decisions increases according to the information dynamics level. The information dynamics affects the aggregation process and then the decision making one. One can note that for all the aggregation schemes, the number of faulty decisions is ranging in [5;12]% when α=0.02, but when α=1 or 2 the number of faulty decisions reaches the interval [45;50]% where the decision making process is unable to take the right decisions. Globally, this error percentage is larger in the situated view while gossip offers the best quality of the decision making. Under churn, Figure 5.b shows that, in the case of gossip and SV2, the number of faulty decisions is com-parable and lower than the one registered when using a tree or SV1. Moreover, it is proportional to the churn level. We also observe that churn hugely affects the quality of the decision making process on the tree where the average number of faulty decisions is about 45%. Thus, it is more relevant to use gossip or SV2 on a dynamic network.

To conclude, as expected, the situated view provides a higher reactivity to AMs than the global ones at the cost of a higher communication. SV1's convergence time is about 5 times lower than the one of tree and 33 times lower than the one of gossip. Concerning the communication cost, the one of SV2 can be almost 3 times higher than the one obtained in the case of gossip and about 42 times the one of tree. As for the global schemes, under dynamic information, they offer more accuracy in the computation of aggregates and in the decision making. With a deviation that reaches 2 when α=5, the tree-based scheme provides the best accuracy. It is about 5 times more accurate than SV1, about 3 times more than SV2 and almost twice more than gossip. Concerning the efficiency of the decision making, gossip provides the best performance. For all the aggregation schemes, the number of faulty decisions is ranging in [5;12]% when α=0.02, but when α=1 or 2 the number of faulty decisions reaches the interval [45;50]%. In the presence of an acceptable churn, gossip performs better than the other schemes in terms of the aggregation accuracy and the efficiency of the decision making mechanism, followed by the situated view and then the tree. When the average lifetime and inter-arrival are respectively higher than 200min and 24sec, gossip is about 4 times more accurate than the tree and about twice more than SV1, with a comparable accuracy with SV2. However, when the average lifetime and inter-arrival are respectively lower than 200min and 24sec, gossip has a comparable accuracy with the one of SV1, and SV2 becomes the most accurate scheme. Thus, SV2 has a comparable performance of the decision making mechanism to the one of gossip. As for tree, it is dramatically affected by churn since the average number of faulty decisions is about 45%.

Conclusion and future work

In the context of autonomous network management, two concurrent approaches are commonly used to achieve the aggregation of management information which are situated and global views. However, we do not know the exact behavior and the performance of these different schemes. Moreover, it is crucial to precisely identify the appropriate context in which each of the aggregation categories performs better. To this end, we provide in this paper a comparative performance analysis of typical situated and global aggregation schemes. This work represents a first step in the evaluation of aggregation schemes. In an effort to enhance it, we are looking for ways to consolidate the obtained results by considering additional impacting parameters (e.g. the changing frequency of local values or various neighborhood degrees). On a long term, we will pursue this work by designing an adaptive system that combines the use of situated and global aggregation schemes. Such an autonomous management system would adapt itself to the supporting network operational behavior, bringing it self-optimization capabilities. A decentralized process will continuously analyze its environment to discover the current context of the management information and its environment and then selects the appropriate aggregation scheme that gives the best performance, in order to build efficient autonomous management frameworks.

Algorithm 3

 3 Pull situated view algorithm executed on a node i (a) Active thread 1: Di←getNeighbors(all) 2: send (h, Di) 3: receive(Xraw j , j) 4: statei←update(Xraw j ) (b) Passive thread 1: loop 2: receive(h, j) 3:

Fig. 1 .

 1 Fig. 1. Notations (a) and simulation parameters (b)

Fig. 2 .

 2 Fig. 2. Cost of SV and GV: (a) Convergence time; (b) Communication cost

Fig. 3 .

 3 Fig. 3. Accuracy of estimated aggregates: (a) Information dynamics; (b) Churn level

Fig. 4 .

 4 Fig. 4. Decision making process

Fig. 5 .

 5 Fig. 5. Efficiency of the decision making: (a) Information dynamics; (b) Churn level

  Algorithm 1 Push tree-based algorithm executed on a node i

	(a) Active thread	(b) Passive thread
	1: p←getParent()	1: loop
	2: send (< Xi, 1 >, p)	2:	receive (< Xj, wj >, j)
	3: receive(Xj, j)	3:	statei←update(Xj, wj)
	4: statei←update(Xj)	4:	p←getParent()
		5:	send (< Xi, wi >, p)
		6:	if (getParent()=null) then
		7:	wait until receive all aggregates
		8:	diffuse (Xi)
		9:	end if
		10: end loop

  Algorithm 2 Push-pull gossip-based algorithm executed on a node i

	(a) Active thread	(b) Passive thread
	1: loop	1: loop
	2:	j←getNeighbors(1)	2:	receive(Xj, j)
	3:	send (Xi, j)	3:	send (Xi, j)
	4:	receive(Xj, j)	4:	statei←update(Xj)
	5:	statei←update(Xj)	5: end loop
	6:	wait(round duration)
	7: end loop