Keywords: Variable length pipeline, Variable stage pipeline, Pipeline stage unification, Low Power, Leakage, Energy, Throughput

Pipeline à étages variables dynamiquement: une implantation du contrôle

Résumé : Minimiser l'énergie pour effectuer une tâche donnée est critique dans l'industrie des sémiconducteurs, principalement à cause du coût, de la fiabilité et la faisabilité : la température et la puissance constituent les barrières principales au niveau des performances.

Les pipelines à profondeur reconfigurables dynamiquement permettent d'augmenter les performances en terme de débit des processeurs et des circuits flots de données usuels, tout en réduisant leur consommation d'énergie. Lorsque la fréquence d'horloge diminue, plus de calculs peuvent être effectués combinatoirement. Dans un tel cas, les signaux peuvent se propager bien plus loin que les barrières fixes nécessaires, afin d'assurer la correction du comportement du circuit lors de l'utilisation de fréquences élevées sur l'horloge. Les pipelines à profondeur reconfigurables dynamiquement permettent de diminuer la puissance dynamique ; l'horloge n'est plus nécessaire sur les registres outre-passables.

Ce rapport de recherche fournit une implantation distribuée du contrôle, et une autre centralisée. Elles permettent de traiter le cas des pipelines de très grandes profondeur, où des problèmes de faisabilité sont causés par les latences physiques associées aux signaux.

Mots-clés : pipeline à longueur variable, pipeline avec nombre d'étages variable, unification d'étages de pipeline

Introduction

Minimizing energy to achieve a given task is a key concern from huge data centers to trendy smart phones. Firstly, due to feasibility: temperature, power and battery capacities are limiting factors. Secondly, due to cost: lower energy enables smaller need for air-cooling, lower cost for ICs, packaging, space saving on PCB, etc. Thirdly, due to reliability: lower temperatures might enable to remove mechanical devices, then reducing risks of failure.

Dynamic Voltage Scaling [START_REF] Pouwelse | Dynamic voltage scaling on a low-power microprocessor[END_REF] (DVS) is a well-known technique to minimize energy. Sleep transistors [START_REF] Long | Distributed sleep transistor network for power reduction[END_REF], tri-gates [START_REF] Doyle | High performance fully-depleted tri-gate cmos transistors[END_REF] and different techniques helps to minimize leakage [START_REF] Siva | Leakage in Nanometer CMOS Technologies[END_REF] on the physical corner. Nevertheless, it is also possible to tackle this problem on the micro-architectural corner. When using DVS, both clock and voltage shrinks, but pipeline length is constant: most of signals may go further than the pipeline boundary needed for high clock frequency, because of a slower clock frequency. Moreover, the efficiency will be more limited due to smaller supply voltage range in the future, despite recent results [START_REF] Calhoun | Ultra-dynamic voltage scaling (udvs) using sub-threshold operation and local voltage dithering[END_REF] on such achievable lower voltage.

Recently, authors of [START_REF] Sasaki | Evaluation of low-energy and high-performance processor using variable stages pipeline technique[END_REF] have argued that it is possible to use bypassable registers (BR) as building blocks for Dynamic Variable Stages Pipelines. A BR is simply a register connected to a mux, as shown in Figure 1. This is a regular and well-known building block for VLIW, DSP and RISC processors to solve RAW (Read After Write), WAR, WAW issues caused by the pipelining scheme. Their straightforward implementation uses master and slave latches instead of a regular flip-flop, as shown in Figure 2; it alleviates glitches propagations that are highly energy consuming.

However, they do not provide a mechanism to handle switching from Low-Frequency/Short Pipeline (SP) to High-Fre-quency/Long Pipeline (LP) (up to our knowledge). This paper provides two implementations for such mechanism: one with distributed control, the other one with centralized control. Variable Length Pipelines (also known as Pipeline Stage Unification or Variable Stage Pipelines) are useful to improve the throughput. They can be used to reduce leakage with power-gating, as shown in [START_REF] Shimada | Pipeline stage unification: a low-energy consumption technique for future mobile processors[END_REF][START_REF] Yao | Optimal pipeline depth with pipeline stage unification adoption[END_REF]. It limits power consumption by reducing the load capacitance of clock drivers, which is achieved by stopping the clock of the bypassed registers; in case of a CPU, it reduces the clock cycle count of program execution by reducing the number of pipeline stages.

Implementation

First, we describe intuitively on a simple example how our design works. Then, we detail both implementations and their correctness. The basic idea to implement Dynamic Variable Length Pipe-line is to use clock-gating as follows:

An Intuitive Example

• When the pipeline is switching from LP to SP, we need to introduce bubbles.

• When the pipeline is switching from SP to LP, we need to remove bubbles.

In Figures 4 and5, plain boxes denotes pipeline stages with regular registers, and dashed boxes denotes stalled stages. Plain circles denotes pipeline stages with bypassable registers; dashed circles denotes bypassed stages.

Switching from LP to SP As shown in Figure 4, we turn off the clock of the first pipeline stage at first instant. At next clock cycle, we will have a bubble in the following BR, that will be switched to its bypassed mode; we also turn off the clock of the third pipeline stage. Then, we will have a bubble in the following BR, and so on. Finally, when reaching the tail of the pipeline, we send to the clock frequency controller a signal to switch to SP, and activate all stalled stages. The process is safe, since we stall the whole pipeline before switching clock frequency.

Switching from SP to LP As shown in Figure 5, we turn off the clock of the last pipeline stage, and we switch the previous BR in regular register mode, that will receive the new fresh data; at next clock cycle, we turn off the clock of the previous pipeline stage, and switch previous BR in regular register mode, and so on. Finally, when reaching the head of the pipeline, we send to the clock frequency controller a signal to switch to LP, and turn on the clock of all stalled stages.

Detailed Distributed Implementation

Now we provide mechanism details, implemented using a natural distributed style.

As shown in Figure 6, a local clock-gating stalls the stage upon reception of signal LP toSP or SP toLP , until receiving an enable signal (Done) from the clock generator. When it receives any of such input signal (LP toSP or SP toLP ), it simply repeats the signal at the next clock cycle: from a stage to the previous one for SP toLP , and from a stage to both next two stages for LP toSP . When the signal reaches the head (resp. the tail) of the pipeline, then we forward the signal to the clock generator, that will switch from SP to LP (resp. LP to SP). After the clock generator has switched the mode, it enables all stages of the pipeline during the same clock cycle by activation signals (Done). However, activation signals coming from the clock generator to all pipeline stages cannot be achieved within a clock cycle in general, especially in case of very deep pipelines. If turning on/off (through clock-gating) is not performed at the same clock cycle on all stages of the pipeline, there is a correctness issue. The intuitive idea to solve it is to know latencies from/to the clock generator to/from each stage of the pipeline and "equalize" them, with respect to the longest path (latency metric) adding flip-flops (or master/slave latches) when needed. In the example given in Figure 7: the longest paths have a latency of 2 clock cycles in LP mode. We add an additional flip-flop to second and fourth stages, and two flip-flops to third stage. Hence, all stages receive the Done during the same clock cycle.

We now detail building blocks used for this implementation (cf. Figure 8). The left one is used in case of regular buffer, while the right one is for bypassable buffers. They both have many common inputs/outputs to implement the distributed protocol. FF has only a Stall F F signal to clock-gate its regular buffer, whereas bypassable FF has an additional signal to drive the mux to bypass.

Each building block has a set of boolean equations that can be easily translated in Verilog, VHDL or SystemC. pre (t) equals the value of signal t during previous clock cycle.

In case of a regular buffer:

LP toSP out = (LP toSP -1 ∨ LP toSP ∨ pre (LP toSP out )) ∧Done SP toLP out = (SP toLP ∨ pre (SP toLP out )) ∧ Done Stall F F = LP toSP out ∨ SP toLP out
where LP toSP -1 is the output LP toSP out from the previous FF pipeline buffer, as shown in Figure 6.

Equations for the bypassable buffer control are as follows:

LP toSP out = (LP toSP ∨ pre (LP toSP out )) ∧ Done SP toLP out = (SP toLP ∨ pre (SP toLP out )) ∧ Done Stall F F = (SP toLP ∨ pre (Stall F F )) ∧ ¬LP toSP ∧Done Bypass F F = (LP toSP ∨ pre (Bypass F F )) ∧ ¬SP toLP
We assume that Done is not emitted while we are switching pipeline stage modes. This is true by construction, since both pipeline ends, sending LP toSP and SP toLP , are connected to the Clock Generator as shown in Figure 6.

We can put some room in the clock generator to introduce additional buffers, this will not break the current placement and routing; using distributed equalization seems better for area, but need to iterate during placement and routing. This equalization introduces mandatory latencies, in order to ensure correctness. The longest latency introduces additional cycles of stall in the pipeline when switching from a mode to the other. When switching from SP to LP, we can also use bypassable buffers accordingly to the latency of each path, in order to minimize the number of stalls in the pipeline (it has to be equalized too).

In such distributed implementations, the issue is when we have pipeline configurations that needs to turn off a lot of consecutive stages during the same clock cycle: this cannot be achieved in general, because of long wires. We solve this issue in the next implementation.

Detailed Centralized Implementation

We now discuss a centralized implementation that let us stall any number of pipeline stages during the same clock cycle. The reader should think of centralized as the root of a clock-tree.

Each pipeline stage has those inputs: LP toSP , SP toLP and Done. They enable the mode switching and the clock, stall the clock, or switch on/off bypasses. Instead of locally generating the stall as in the distributed implementation, now we generate the signal from a module. The module has two inputs associated to mode switching, and has many pair of outputs (LP toSP , SP toLP ) associated to each stage of the pipeline, as shown in Figure 9.

For instance, to switch from LP to SP, as shown in Figure 4, we have to count 10000, 11100, 11111, and finally to send Done to all stages. Another example is to switch from SP to LP as in Figure 5. We just need to count 00001, 00011, 00111, 01111, 11111, and finally to send Done to all stages (assuming here previous latency equalization).

In the centralized implementation, there is no protocol between pipeline stages. We just need a local clock-gating that will receive LP toSP , SP toLP and Done signals. It is no longer needed to equalize latencies from the clock generator to all pipeline stages. In the previous case, the clock generator was not supposed to know how many cycles the pipeline would be fully stalled after it has sent the switch signal. Here, the module can send LP toSP and SP toLP signals with respect to the different latencies of all wires.

Power-gating is an efficient technique to reduce leakage power of a chip. However, power-gating takes more than one clock cycle to be enabled, and also a careful design, as detailed in [START_REF] Keating | Low Power Methodology Manual: For System-on-Chip Design[END_REF]. The centralized implementation is a good candidate to apply power-gating: when switching from LP to SP, we have the opportunity to turn off a set of flip-flops or latches. Moreover, since both power-gating and switching from LP to SP (and from SP to LP) takes time, we can turn on/off bypassable buffers of pipeline stages, while at the same time we are switching from a pipeline length mode to the other one. This kind of scheme can apply naturally to long pipelines that are regularly found in digital filters for Video, Image and Signal processing, even if all bypassable buffers of such pipeline cannot be turned off because of its length.

INRIA

For instance, let us assume a 32-stages pipeline design, as shown in Figure 11. It takes 8 clock cycles to turn on/off a latch or a flip-flop.

We can neither turn off 8 first stages, nor turn on 8 last stages, because of previous constraints. We can still power-gate 8 stages in between, denoted as grey filled circles in Figure 11. There is an additional time constraint such that power-gate signal arrives on 9 th and 23 th stages within one clock cycle from the centralized scheme; in the first case to turn off, and the second case to turn on respectively. It takes 8 more clock cycles (then a total of 16) if we want to turn on/off all bypassable stages to save more leakage power.

The centralized implementation can be applied to any pipe-line configuration and clock-gating. This cannot be achieved in general using the distributed implementation.

In this implementation, there is only a local clock-gating (or a bypass) on each pipeline stage. There is less area overhead for each stage than in the distributed one (no protocol overhead). However, there are a lot of wires connected from the centralized module to enable/disable clock-gating. More bypassable buffers are also required on each pipeline stage. This means a higher area overhead than with the distributed implementation.

The centralized implementation can cope with any arbitrary latency in the clock-gating scheme, because we can send the enable or stall signals earlier, when building the sequence to switch from one mode to another one.

Correctness

In order to guarantee the correctness of the switch between the two modes of our design, we have assumed the following hypotheses:

• Only pipelined combinatorial logic can be bypassed. In general, we cannot bypass latches or flip-flops without affecting the behavior. Obviously, if the designer knows that it does not change the behaviour, then she/ he can use a bypass.

• There must be at least one latch or flip-flop in any circuit whenever bypasses are active or not. Otherwise, it creates a combinatorial cycle. This is not strictly necessary if shown correct, but most of EDA tools will complain in such a case.

• We can clock-gate any pipeline stage within a clock cycle. Otherwise, each pipeline stage could not be seen as a black-box, and a finer grain analysis of latencies and data dependencies would be needed. The centralized implementation can cope with such behaviour.

• Fast clock frequency is a multiple of the slower one. This way, both clocks are phase-aligned; this is a simplification.

• In case of distributed implementation, all the consecutive stages between two bubbles can be stalled within a clock cycle. A problem may occur if a few bubbles are inserted in a long pipeline, far from each other. All stages between two bubbles have to be stalled simultaneously, or there would be misplaced bubbles.

• Clock generator does neither change clock speed, nor send Done when the pipeline is switching from one mode to another.

• Clock tree between pipeline stages and the clock generator is latency equalized. Otherwise, there can be issues when the whole pipeline restarts, if the same clock instant does not arrive during the same instant at all pipeline stages.

Discussion

In this section, we discuss the timing issues to switch between modes, and hierarchical variable length pipeline.

Time for switching between modes It takes LP -SP + 1 clock cycles (with the clock frequency of the LP mode) to switch from LP to SP, where LP and SP are respectively the length of the long and short pipelines. Conversely, it takes the same number of clock cycles to switch from SP to LP, but with the clock frequency of the SP mode. The time for switching between modes is minimal, provided there is no latency from/to clock generator. If there exists such latency, then we have to minimize the latency of the following paths, in order to minimize the time spent for switching between modes:

• From the head of the pipeline, passing through the clock generator, reaching all stages of the pipeline.

• From the tail of the pipeline, passing through the clock generator, reaching all stages of the pipeline. Hierarchical variable length pipeline Our implementations can also be composed with more than two modes, as shown in Figure 12. The pipeline may have a depth of 5 stages (1 → 2 → 3 → 4 → 5), 3 stages (1 → 2 + 3 → 4 + 5) or 1 stage (1 + 2 + 3 + 4 + 5). A shorter pipeline is obtained by merging consecutive stages of its immediately longer configuration; in other words, there is kind of alignment of the non-bypassed stages from the slowest mode to the fastest.

INRIA

In this case, we come down to the general one, where the times for switching between modes are the same as given above.

Conclusion

We introduce two implementations for the control of a Dynamic Variable Length Pipeline through the use of bypassable buffers. The intuitive idea is as follows: when switching to Long Pipeline (LP) to Short Pipeline (SP), we introduce "bubbles" in bypassable buffers, starting from the head of the pipeline until reaching its tail, then finalizing clock frequency switch; conversely, when switching from Short Pipeline to Long Pipeline, we remove these "bubbles" starting from the tail of the pipeline until reaching its head.

We introduce both distributed and centralized implementation. The distributed implementation simply forwards the switch signal from LP to SP, until reaching the tail, and then re-enables the clock. When switching from SP to LP, we stall the tail of the pipeline, and go in the reverse direction until reaching the head.

All pipeline stages must restart during the same clock-cycle. However, this cannot be done in one clock cycle, when considering long pipelines. To solve this issue in the distributed implementation, we "equalize" latencies of enable paths (from the clock generator to each stage of the pipeline) and also the clock-tree, in between clock generator to stages of the pipeline : we add flip-flops in order to equalize its latency to the longest path, thus synchronizing arrival of all enable signals during the same clock cycle.

Nevertheless, we cannot turn on/off (through clock-gating) a lot of consecutive stages of the pipeline, because of physical latencies. Hence, we also introduce the centralized implementation, allowing more complex configurations that cannot be achieved with the distributed one. There is no need to equalize latencies of enable/stall paths from the clock generator to all pipeline stages in this implementation, but clock-tree equalization is still mandatory to ensure correctness.

Figure 1 :

 1 Figure 1: Bypassable flip-flop.

Figure 2 :

 2 Figure 2: Bypassable master/slave latches.

Figure 3 :

 3 Figure 3: DLX CPU with (a) 5 stages pipeline and (b) 3 stages pipeline.

First, we start

  with the intuitive example of a simple DLX processor. It is 5pipeline stages long in Long Pipeline mode, as shown in Figure 3 (a): Instruction fetch cycle (IF), Instruction decode/register fetch (ID), Execution/effective address cycle (EX), Memory access/branch completion cycle (MEM), Write-back cycle (WB). It has only 3 pipeline stages in Short Pipeline mode : (IF+ID), (EX+MEM) and (WB) as shown in Figure 3 (b).

INRIA

Figure 4 :

 4 Figure 4: Long Pipeline to Short Pipeline.

Figure 5 :

 5 Figure 5: Short Pipeline to Long Pipeline.

Figure 6 :Figure 7 :

 67 Figure 6: Distributed implementation.

INRIA

Figure 8 :

 8 Figure 8: Distributed implementation building blocks.

Figure 9 :

 9 Figure 9: Centralized implementation.

Figure 10 :

 10 Figure 10: Centralized implementation building blocks.

Figure 11 :

 11 Figure 11: Power-gating instance.

Figure 12 :

 12 Figure 12: Multi-length pipeline.

RR n°6918


Damien Couroussé

Bruno Robisson

Jean-Louis Lanet

Thierno Barry

Hassan Noura

Philippe Jaillon

Philippe Lalevee

Philippe Lalevée

COGITO: Code Polymorphism to Secure Devices

Keywords: Code Polymorphism, Runtime Code Generation, Physical Attacks, Embedded Devices

Introduction

Electronic devices have grown a huge interest for the average user thanks to the tremendous computation power and data storage that it is possible to put in a few square centimetres of silicon. Everybody has now the capability to put a lot of its personal and professional information in such devices, and the confidentiality of the 'secret' kept in electronic devices is of huge importance. As a consequence, security of such devices is one of the main concerns, on an equal footing with user interfaces and connectivity. Therefore, when thinking about security issues in electronic devices, smart card or Java Card are the words that first come to mind for historical reasons. But today, the landscape of electronic devices is composed of computing platforms of very different kinds. Hence, security is now an issue for a very large set of embedded devices, from nodes in wireless sensor networks to smartphones.

All of these electronic devices can be subject to "physical attacks" which are generally split in two steps, thereafter called 'first step' attacks and 'second step' attacks. 'First step' attacks consist in getting general information about the functioning of the devices: identifying which security functions are implemented, when they are launched and on which hardware blocks they are executed. The term 'reverse engineering', in the large meaning of the word, is also commonly used to refer to this step of the at-tack. In this step, the attacker can use three different kinds of techniques. The first one consists in getting information about the chip design by direct inspection of its hardware structure. This inspection may be performed by using any kind of imaging techniques or by using destructive means such as abrasion, chemical etching or focused ion beam. The second kind, called side channel attacks, consists in observing some physical characteristics (such as power consumption, electromagnetic radiation, response time, etc.) which are modified while the circuit is active. The third technique, called fault attacks, consists in disrupting the circuit's behaviour by using laser beams, voltage or clock glitches, electromagnetic pulses, etc. In the 'second step', the attack is focused on one or several security functions in order to bypass them [START_REF] Barbu | Attacks on Java Card 3.0 Combining Fault and Logical Attacks[END_REF], to recover the details of their implementation [START_REF] Novak | Side-channel attack on substitution blocks[END_REF] or to recover the manipulated data [START_REF] Genkin | RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis[END_REF]. These 'second step' attacks are very powerful but always rely on a very precise spatial and temporal control of the target. In particular, the success of a fault (resp. side channel) attack depends on the time precision required to inject the fault (resp. measure the physical characteristics) at the right time and on the right area during program execution.

Many protections (also called 'ad hoc') have been proposed to counter all these 'second step' attack schemes. But surprisingly, few protections have been proposed against 'first step' attacks, even if these ones constitute a crucial stepping stone for the success of an attack. We assume that polymorphism, which consists in regularly changing the behaviour of a secured component at runtime while maintaining unchanged its functional properties, can make attackers' lives more difficult. Our hypothesis is that polymorphism can tackle security issues at several levels: it increases the difficulty of reverse engineering, it provides dynamically changing temporal and spatial properties that also increase the difficulty of 'second step' physical attacks. Moreover, we assume that the use of polymorphic code is a realistic objective even for resource-constrained embedded devices, and illustrate how we plan to achieve this thanks to a tool for runtime code generation that fulfils the memory and computing constraints of embedded systems.

To demonstrate our hypothesis, the rest of this paper is organised as follows. Section 2 presents an overview of the general principles of protections and of the uses of polymorphism in the context of security. Section 3 introduces the solution envisioned in this paper and provides a simple illustrative case. Section 4 concludes.

State of the art

We make the distinction between general protections, which make reverse engineering of the target more difficult to achieve in 'first step' attacks, and ad hoc protections, which are specific defensive mechanisms implemented against a known attack usually performed as a 'second step' attack.

Ad hoc protections

Many protections have been proposed to counter 'second step' hardware attacks. Some protections (called 'sensors') give information about the state of the system either by measuring light [START_REF] Dutertre | Sensitivity tuning of a bulk built-in current sensor for optimal transient-fault detection[END_REF], voltage [START_REF] Zussa | Efficiency of a glitch detector against electromagnetic fault injection[END_REF], frequency or temperature or by detecting errors during computations. This detection is generally based on spatial redundancy, temporal redundancy or information redundancy. Several mechanisms are also proposed to detect a modification of the execution flow of a program [START_REF] Petroni | Automated detection of persistent kernel control-flow attacks[END_REF], or to avoid the effects of instruction skips caused by fault attacks [START_REF] Moro | Formal verification of a software countermeasure against instruction skip attacks[END_REF]. In some cases, an additional hardware block is dedicated to this task [START_REF] Arora | Secure Embedded Processing through Hardware-Assisted Run-Time Monitoring[END_REF]. To reduce sensitivity to side channel attacks, 'noise' is added to the power consumption, for example by using an internal clock, by shuffling operations or by masking the internal computations that could be predicted by the attacker [START_REF] Mangard | Power analysis attacks: Revealing the secrets of smart cards[END_REF], by using balanced data encoding or balanced place and route [START_REF] Guilley | Evaluation of power constant dual-rail logics countermeasures against DPA with design time security metrics[END_REF], by using power filters or electromagnetic shields [START_REF] Shamir | Protecting smart cards from passive power analysis with detached power supplies[END_REF], or by using software techniques called 'hiding' [START_REF] Mangard | Power analysis attacks: Revealing the secrets of smart cards[END_REF].

Obfuscation as a general protection

We propose to make the distinction between obfuscation mechanisms that do not modify the behaviour of the target at runtime, thereafter called static obfuscation, and dynamic mechanisms which purpose is to modify, at runtime, the apparent behaviour of the target. Polymorphism, by providing to a secure component the capability to change form on a regular basis, is considered as a dynamic obfuscation mechanism.

Static obfuscation

Obfuscation of hardware is a common practice, because the attacker can gain a lot of knowledge about the target by physical inspection of its structure [START_REF] Chakraborty | Harpoon: An obfuscation-based soc design methodology for hardware protection[END_REF] but we do not further consider this topic as it falls out of the scope of this paper.

Software obfuscation can involve modifications to the source code, to intermediate representations or to the binary code [START_REF] Collberg | A taxonomy of obfuscating transformations[END_REF] or encryption [START_REF] Sander | On software protection via function hiding[END_REF] in order to make it unintelligible or inaccessible to automatic analysis. At the theoretical level, it was demonstrated by Barak et al. that there is no general obfuscation technique that applies to any code function; in other words, there is no "universal obfuscating tool" [START_REF] Barak | On the (im) possibility of obfuscating programs[END_REF]. However, nothing in this theory forbids the existence of obfuscation techniques able to target the mostly used cryptographic algorithms such as DES, AES, RSA, ECC.

Dynamic obfuscation by polymorphism

Non-deterministic processors [START_REF] May | Nondeterministic processors[END_REF] achieve what we call polymorphic execution, that is, the shuffled execution of a program from a static binary input residing in program memory. May et al. achieve dynamic instruction shuffling [START_REF] May | Nondeterministic processors[END_REF] and random register renaming (May et al., 2001a). [START_REF] Bayrak | An architecture-independent instruction shuffler to protect against side-channel attacks[END_REF] describe an instruction shuffler: a dedicated IP inserted between the processor and the program memory (instruction cache).

Most (if not all) tools for program analysis and reverse engineering of software cannot handle programs that are dynamically modified at runtime [START_REF] Madou | Software protection through dynamic code mutation[END_REF]. Hence, despite the theoretical work of [START_REF] Barak | On the (im) possibility of obfuscating programs[END_REF], dynamically mutating code and polymorphic code are likely to make 'first step' attacks more challenging. [START_REF] Madou | Software protection through dynamic code mutation[END_REF] use runtime code rewriting scripts to restructure the contents of a procedure from binary programs under a scrambled form. However, this form of dynamic mutation is only effective against code analysis and not against physical attacks since the executed program always takes the same form.

To the best of our knowledge, only a few research works have studied the use of code polymorphism for security purposes. [START_REF] Amarilli | Can Code Polymorphism Limit Information Leakage? In WISTP[END_REF] propose to shuffle instructions and basic blocks of the program's control flow graph at runtime from a static version of the program. Their approach, applied to the shuffling of basic blocks only, is shown to increase the difficulty of DPA on AES. [START_REF] Agosta | A code morphing methodology to automate power analysis countermeasures[END_REF] use runtime code generation (described by the authors as code morphing) to protect an implementation of AES against DPA. A runtime code generator is generated at static compilation time, embedded in the application binary code. The polymorphic production of code variants involves register renaming, instruction shuffling and the production of semantically equivalent code fragments. The overhead of code generation is significantly high since each new code generation is reported to execute in 90 ms (11, 970.10 6 cycles at 133 MHz) on an ARM926 processor running GNU/Linux, in order to generate polymorphic versions corresponding to the 64 xor operations in the AES kernel. This approach is the closest to the approach that we envision in this paper, but as we will illustrate below, we expect our approach to better fit with the constraints of resource constrained embedded systems.

Code polymorphism for embedded systems

As explained in the previous section, the state of the art protections present the following limitations:

1. General protections, which make the code execution harder to interpret and so the knowledge about the circuit's functioning harder to recover, are a primary requirement in secure devices. However, state-of-the-art solutions present performance issues or are not applicable to secure devices because of resource constraints.

2. Security in a device is incrementally built by adding standalone ad hoc protections. Ad hoc countermeasures are often proven to be efficient when analysed independently, but are difficult to integrate in a device since each countermeasure comes with an additional performance overhead.

We postulate that code polymorphism is able to provide an efficient solution as a general protection against 'first step' attacks. Furthermore, 'second step' attacks, which rely on a precise behavioural (spatial and temporal) model of the target, are also more difficult to achieve if the target's behaviour is regularly modified. Indeed, the success of a fault attack depends on the temporal and spatial precision required to inject the fault at the right time during program execution, and on the right position on the chip; this should be more difficult in presence of polymorphism. Similarly, side channel attacks need to correlate a large number of activity traces to extract the target information; a polymorphic component is able to produce a larger set of different activity traces, and as a consequence, the attacker needs to gather a greater number of activity traces to achieve the attack.

In the work presented in this paper, our objective is to provide a realistic solution to achieve code polymorphism by introducing in a unique framework:

• Introduce alea during runtime code generation to produce polymorphic application components,

• Use semantic equivalences at the instruction level to produce different (but functionally equivalent) instances of code sequences

• Shuffle, at runtime, the machine instructions and randomise the mapping to physical registers

• Combine with hardware protections

• With limited memory consumption and fast code generation, so that it is applicable very small computing units such as secure elements

Sketching deGoal

deGoal is a framework for runtime code generation, whose initial motivation is the use of runtime code specialisation to improve program performance, e.g. execution time, energy consumption or memory footprint. In this section, we first sketch the characteristics of deGoal and then elaborate about its use in the context of security. [START_REF] Couroussé | Introduction to Dynamic Code Generation -an Experiment with Matrix Multiplication for the STHORM Platform[END_REF][START_REF] Aracil | Software acceleration of floating-point multiplication using runtime code generation[END_REF][START_REF] Charles | deGoal a Tool to Embed Dynamic Code Generators into Applications[END_REF] further elaborate about the use of deGoal in contexts or application domains that originated its design.

In classical frameworks for runtime code generation such as interpreters and dynamic compilers, the aim is to provide a generic infrastructure for code generation, bounded by the syntactic and semantic definition of a programming language. The generality of such solutions comes at the expense of an important overhead in runtime code generation, both in terms In deGoal, a different approach is used: code segments (thereafter called kernels) are generated and tuned at runtime by ad hoc runtime code generators, called compilettes. Each compilette is specialised to produce the machine code of one kernel. Syntactic and semantic analyses are performed at the time of static compilation, and compilettes embed only the processing intelligence that is required for the runtime optimisations selected. As a consequence, compilettes offer very fast code generation (10 to 100 times faster than typical frameworks for runtime code interpretation or dynamic compilation), present a very low memory footprint, can run on very small microcontroller architectures such as 8/16-bit microcontrollers [START_REF] Aracil | Software acceleration of floating-point multiplication using runtime code generation[END_REF], and are portable [START_REF] Charles | deGoal a Tool to Embed Dynamic Code Generators into Applications[END_REF].

In COGITO, we re-target the original purpose of deGoal in order to focus on security aspects: we exploit the flexibility brought by deGoal for runtime code generation to achieve code polymorphism.

Application building, runtime code generation and execution

The building and the execution of an application using deGoal consists of the following steps as illustrated in Figure 1: writing the source code using a mix of C source code and of our dedicated cdg language (described below); compiling the binary code of the application and the binary code of compilettes using static tools; at runtime, generating the binary code of kernels by compilettes and in the end running the kernels.

The Cdg language

Cdg is an assembly-like DSL. From the programmer's perspective, this represents a major paradigm shift: Cdg expressions describe the instructions that will be generated at runtime instead of the instructions to be executed.

Compilettes are implemented by using a mix of ANSI C and Cdg instructions. The C language is used to describe the control part of the compilette that will drive code generation, while Cdg instructions perform code generation. The Cdg instruction set includes a variable length register set, classical arithmetic instructions, load and store instructions. From this high-level instruction set, compilettes map the instructions to machine instructions according to (1) the characteristics of the data to process, (2) the characteristics of the execution context at the time of code generation, (3) the hardware capabilities of the target processor, (4) execution time and/or energy consumption performance criteria. In all cases, code generation is fast, produces efficient code, and is applicable to low-resource embedded systems such as micro-controllers.

In the case of the work presented in this paper, we remove the dependency of code generation to the input data, and make code generation dependant of an alea to introduce random polymorphism.

Main properties of the code generation backend

Considering that deGoal targets constrained embedded systems, drastic architecture choices have been made so that code generation can be fast and memory lightweight. At runtime, a compilette performs in this order: register allocation, instruction selection and instruction scheduling.

Register allocation. In dynamic compilers, register allocation is usually performed after instruction scheduling: instruction selection and instruction scheduling are performed on a SSA form. The SSA form is later analysed and register allocation is performed, using techniques that provide a reduced runtime computational cost of the register allocation as compared to graph colouring usually used in static compilers [START_REF] Kotzmann | Design of the java hotspot client compiler for java 6[END_REF]. On the contrary, in a compilette register allocation is done first, simply by using greedy algorithm. The idea is to lighten the pressure on instruction selection and instruction scheduling: if register allocation is done first, it becomes possible to perform instruction scheduling without intermediate representation1 . This comes at the expense of a potential reduced code quality: currently, compilettes do not support register spilling.

Instruction selection. Instruction selection is performed at runtime once the runtime constants have been evaluated by the compilette. Instruction selection is done at the level of Cdg instructions: each Cdg instruction can be mapped to one or more machine instructions depending on the data input of the compilette and/or processor capabilities (e.g. availability of SIMD units).

Instruction scheduling. The generated machine instructions can be either directly written in program memory in order to fasten code generation, or pushed into an intermediate instruction buffer that is processed by an instruction scheduler. We plan to exploit this feature in this work to perform instruction shuffling during runtime code generation. A functional overview of instruction scheduling is illustrated in [START_REF] Couroussé | Introduction to Dynamic Code Generation -an Experiment with Matrix Multiplication for the STHORM Platform[END_REF].

Implementation of code polymorphism with deGoal

present now the features that we plan to implement in deGoal in order to achieve code polymorphism for security purposes.

Introduce alea during runtime code generation. Code polymorphism has to present a fair level of randomness. Each new code generation should produce a code sequence with a different binary code, while preserving the functionality of the original implementation. At the same time, the process of code generation must remain deterministic, considering a selected random input.

Random generation of semantically equivalent sequences. Our runtime code generation technique is able to involve all the optimisation techniques usually employed in compiler backends, where the purpose is to optimise the machine code generated according to the characteristics of the target. In our case, we leverage this level of variability to increase the number of code variants possibly generated. We consider randomly changing the following code generation parameters:

• use of semantic equivalences; for example replacing a multiplication operation with a power of two with a left shift operation [START_REF] Agosta | A code morphing methodology to automate power analysis countermeasures[END_REF].

• insertion of dummy operations [START_REF] Mangard | Power analysis attacks: Revealing the secrets of smart cards[END_REF], that is, operations intended to vary the execution time and the power trace of the target, but which do not impact the result of the processing.

• mapping to physical registers,

• instruction scheduling, Ability to combine with hardware countermeasures. Use of dedicated hardware support or specialised instructions was a primary concern in the design of the Cdg language: hardware protections or hardware IPs (e.g. AES) are easily integrated in the implementation of a compilette. Furthermore, Cdg being a low-level programming language, it is easy to integrate software protections at the instruction level.

Limited memory consumption. deGoal compilettes embed only the necessary data to generate the instructions (and algorithmic equivalences in the case of this project) required for the target polymorphic code. For example, we achieved runtime code generation with deGoal on the evaluation board of the MSP430 micro-controller, which includes only 512 bytes of RAM [START_REF] Aracil | Software acceleration of floating-point multiplication using runtime code generation[END_REF].

Fast runtime code generation. Using deGoal, the current speed of code generation ranges from 10 to 100 cycles per instruction generated in an implementation that is not targeting secure devices [START_REF] Couroussé | Introduction to Dynamic Code Generation -an Experiment with Matrix Multiplication for the STHORM Platform[END_REF]. Even with the addition of extra processing to achieve the insertion of randomisation at various levels, we expect the speed of code generation to remain far above the state of the art.

Portability to very small processors and secure elements is achieved thanks to the small footprint of compilettes and the small amount of processing they require to achieve code generation.

Conclusion

In this paper we advocate the use of code polymorphism as a means to secure the sensitive components of embedded applications such as cryptographic primitives. We assume that code polymorphism can bring improvement to several security issues at the same time. Firstly, it is de facto a mean to obfuscation, hence making reverse engineering more difficult to achieve. Moreover, considering that physical attacks are strongly related to the temporal and spatial behaviour of the target, regularly modifying the target's behaviour will raise the level of security of a component against physical attacks.

In the scope of the COGITO project, we plan to implement code polymorphism in secure components thanks to deGoal, a framework for runtime code generation that is applicable to embedded devices even with limited memory and computing resources. We have presented the various ways to leverage polymorphism, and illustrated them with a simple case. A large body of the work planned in this project will also consist in the analysis of the potential flaws that runtime code generation could bring to secure devices.

Figure 1 :

 1 Figure 1: deGoal workflow: from the writing of application's source code to the execution of a kernel generated at runtime

or at least with a minimalist, much lighter intermediate representation Semantic equivalence can involve more complex patterns than a one-to-one relationship between equivalent operations, hence they can change the number of machuine instructions generated.

ACKNOWLEDGEMENTS

This work was partially funded by the French National Research Agency (ANR) as part of the program Digital Engineering and Security (INS-2013), under grant agreement ANR-13-INSE-0006-01.