Shivam Bhasin

Jean-Luc Danger

Sylvain Guilley

Xuan Thuy Ngo

Laurent Sauvage

Hardware Trojan Horses in Cryptographic IP Cores

Keywords: Hardware trojan horses (HTH), HTH detection and insertion, optical pictures versus GDSII comparison technique, ECO place-and-route, core utilization rate (CUR)

Detecting hardware trojans is a difficult task in general. In this article we study hardware trojan horses insertion and detection in cryptographic intellectual property (IP) blocks. The context is that of a fabless design house that sells IP blocks as GDSII hard macros, and wants to check that final products have not been infected by trojans during the foundry stage. First, we show the efficiency of a medium cost hardware trojans detection method if the placement or the routing have been redone by the foundry. It consists in the comparison between optical microscopic pictures of the silicon product and the original view from a GDSII layout database reader. Second, we analyze the ability of an attacker to introduce a hardware trojan horse without changing neither the placement nor the routing of the cryptographic IP logic. On the example of an AES engine, we show that if the placement density is beyond 80%, the insertion is basically impossible. Therefore, this settles a simple design guidance to avoid trojan horses insertion in cryptographic IP blocks: have the design be compact enough, so that any functionally discreet trojan necessarily requires a complete re-place and re-route, which is detected by mere optical imaging (and not complete chip reverse-engineering).

I. Introduction

The semiconductor industry has spread across borders in the time of globalization. Different design phases of an Integrated Circuit (IC) may be performed at geographically dispersed locations. This coupled with the outsourcing design and fabrication to increase profitability has become a common trend in the semiconductors industry. However, this business model comes with an ample scope of introducing malicious behavior to a part of the IC. The adversary has enough scope to tamper the supply chain by maliciously implanting extra logic as Hardware Trojan Horse (HTH) circuitry into an IC [START_REF]Defense science board task force on high performance microchip supply[END_REF]. This raises serious concerns about security and trustworthiness of imported products employed in critical applications like military, health, transportation, etc. HTH can be introduced in an IC at several points right from the Register Transfer Level (RTL) source code to lithographic masks fabrication. An

C

C modified A B attacker can change a design netlist or subvert the fabrication process by manipulating design masks, without affecting the main functionality of the design [START_REF] Adee | The Hunt For The Kill Switch[END_REF].

Trojan active

Any HTH is composed of two main components [START_REF]Introduction to Hardware Security and Trust[END_REF]:

• Trigger: is the part of HTH used to activate the malicious activity, • Payload: is the part of HTH used to realize/execute the malicious activity. Fig. 1 gives an example of one simplistic HTH. In this archetype HTH, the trigger is a simple AND gate: it tests the equality of the inputs A and B to 1; the payload is an XOR gate: it inverts the intermediate net C if the trigger is active.

An adversary can introduce a HTH which might be designed to disable or destroy a system at some future time, or to leak confidential information such as secret keys covertly to an adversary [START_REF] Tehranipoor | A Survey of Hardware Trojan Taxonomy and Detection[END_REF] by putting them to output channels. In [START_REF] Skorobogatov | Breakthrough silicon scanning discovers backdoor in military chip[END_REF], the author demonstrates an attack on a (purported militarygrade) chip using a malicious backdoor. The backdoor allows the attacker to disable all the security of the chip, reprogram cryptographic part, access secret keys, modify low-level silicon features, access unencrypted configuration bitstream or permanently damage the device. Thus protection against HTH is an open problem and an active research topic.

HTH detection is an extremely challenging problem; traditional structural and functional tests do not seem to be effective in targeting and detecting HTHs. Since HTH can be introduced during different design phases, the nature of HTH differs from one design phase to the others. Therefore it is difficult to find a unique detection technique for all HTH. For instance Automatic Test Pattern Generation (ATPG) methods which are used in manufacturing test for detecting defects, generally operate on the netlist of the HTH-free circuit. Existing ATPG algorithms cannot target HTH activation/detection directly [START_REF] Wang | Detecting malicious inclusions in secure hardware: Challenges and solutions[END_REF] because HTH are designed such that they are silent most of their lifetime and have very small size relative to their host design, with featuring limited contribution into design characteristics. Such HTHs are most likely connected to nets with low controllability and/or observability [START_REF] Wang | Detecting malicious inclusions in secure hardware: Challenges and solutions[END_REF], [START_REF] Banga | A Novel Sustained Vector Technique for the Detection of Hardware Trojans[END_REF].

The state of the art principle in detection strategies of HTH can be widely classified in two categories, viz. invasive and non-invasive [START_REF] Hopkins | Hardware Trojans -Prevention, Detection, Countermeasures[END_REF].

Invasive methods try to (prophylactically) modify the design of IC to prevent the HTH or to assist another detection technique. Chakraborty et al. have proposed a design that aims to expose the presence of a HTH in a multi-module design [START_REF] Chakraborty | Ondemand transparency for improving hardware trojan detectability[END_REF]. Salmani et al. propose a procedure to insert dummy flip-flops into logic to increase HTH activity, making the detection easier using side-channel techniques [START_REF] Salmani | New design strategy for improving hardware Trojan detection and reducing Trojan activation time[END_REF]. Other researchers also suggest logic additions that will make it easier to detect a HTH utilising side-channel analysis, e.g., [START_REF] Li | At-speed delay characterization for IC authentication and Trojan Horse detection[END_REF] add extra logic for characterising delay times within an IC.

Non-invasive HTH detection is done by comparing the performance characteristics of an IC with a known good copy also known as the "golden circuit". Detecting HTH in a noninvasive manner can be done either at runtime or in the testing phase. The runtime detection mechanisms is combined with the countermeasures, as once a HTH is detected at runtime, attempts are made to try and continue operating by bypassing the HTH. For runtime, Bloom et al. detail a HTH detection approach that uses both hardware and software to detect two types of HTH which are DoS (Denial of Service) and combined hardware and software HTH [START_REF] Bloom | OS Support for Detecting Trojan Circuit Attacks[END_REF]. Abramovici and Bradley added reconfigurable DEsign-For-ENabling-SEcurity (DEFENSE) logic to the functional design to implement realtime security monitors [START_REF] Abramovici | Integrated circuit security: new threats and solutions[END_REF]. McIntyre et al. detect the presence of HTHs by executing functionally equivalent processes on multiple hardware processing elements [START_REF] Mcintyre | Dynamic evaluation of hardware trust[END_REF]. The testing phase detection methods attempt to enhance traditional IC testing, or use side-channel analysis. For logic testing, Jha and Jha present a randomisation-based technique which probabilistically compares the functionality of the design of the circuit with the implemented circuit [START_REF] Jha | Randomization Based Probabilistic Approach to Detect Trojan Circuits[END_REF]. Chakraborty et al. suggest to test rare occurrences on an IC rather than testing for correctness [START_REF] Chakraborty | MERO: A Statistical Approach for Hardware Trojan Detection[END_REF]. The tester determines rare states that can occur within a circuit module. For side-channel analysis, Agrawal et al. present a type of detection mechanism [START_REF] Agrawal | Trojan Detection using IC Fingerprinting[END_REF]. Some known good copies of the IC are obtained and fingerprinted using one or more side-channel parameters. Other chips can then be tested against these fingerprints like path delay in [START_REF] Jin | Hardware trojan detection using path delay fingerprint[END_REF]. Power supply transient signal analysis is used as the side channel by Rad et al. [START_REF] Rad | Sensitivity analysis to hardware Trojans using power supply transient signals[END_REF]. They aim at determining the smallest HTH that they can find using this technique, which can be as low as three additional gates. Banga and Hsiao [START_REF] Banga | A Novel Sustained Vector Technique for the Detection of Hardware Trojans[END_REF] propose the "sustained vector technique" that is able to magnify the sidechannel differences (based on power draw) between circuits infected with HTHs and those that are not.

Most of the abovementioned techniques are indirect detection methods (e.g. reviewed in Chapter 15 of [START_REF]Introduction to Hardware Security and Trust[END_REF]). Such methods observe the effect of the HTH on the timing, the side-channel emissions, etc. The presented indirect detection methods are, under ideal circumstances, able to detect a HTH even of small size. However, countermeasures protecting cryptographic implementations often rely on perturbing the power consumption by methods like random clock jitter or masking of sensitive data, etc. Therefore, the indirect method, though still feasible, will loose efficiency in such applications. Another requirement for the indirect method is the golden reference, which can be sometimes expensive to obtain. Also side-channel based techniques are often becoming less efficient because of factors like environmental/measurement noise, process variation, or algorithmic noise. Thus HTH detection may require a huge amount of traces. On the contrary, our direct observation technique is not affected by the randomization or variations brought by countermeasures.

In this paper, we develop a new HTH detection method at the layout level of integrated circuits by using a low-cost direct visual detection. We address the scenario where the HTH is inserted by an untrusted off-shore foundry just before the fabrication of a unit. We place ourselves in the role of a designer who sends a HTH-free layout (e.g. in GDSII format -Graphic Database System version II, format of Cadence Design Systems) to a third-party foundry for fabrication but is threatened by introduction of a HTH in the GDSII by the untrusted fab. Of course an untrusted founder introducing a HTH will not share the HTH-infected GDSII with the designer. To address this issue we propose a detection technique based on image processing/comparison techniques. These techniques are used to compare the final HTH-free layout with the highquality optical snapshots of the IC. We illustrate our technique on secret key block ciphers (modified to allow for a distant fault injection); but actually it can also allow to detect the modification made in the netlist of arithmetic operations, which can lead to "bug attacks" [START_REF] Biham | Bug attacks[END_REF] in asymmetric cryptography. Several works on insertion of HTH in cryptographic applications have been previously studied [START_REF] Gallais | Hardware trojans for inducing or amplifying side-channel leakage of cryptographic software[END_REF], [START_REF] Subidh | Multi-level attacks: An emerging security concern for cryptographic hardware[END_REF].

This paper describes a HTH based on a backdoor that can activate a bitflip compliant with a (remote) differential fault attack. It also discusses a visual or correlation based technique capable of detecting modifications in the layout (that can somehow be considered permanent faults).

The rest of this paper is organized as follows. Section II gives a general background on AES and how fault attacks can reveal its secret key. Also in this section, a small gate count HTH is given whose principle is to trigger an artificial fault injection. Section III presents the central contribution of the paper: it explains how a visual comparison between the chip and the original GDSII can reveal HTH insertions. An automated method for the HTH detection based on a similarity tool (namely the cross-correlation) is then presented. Based on this detection method, a case study of HTH and results are shown in Section IV; it is applied successfully to real images and layouts. Section V gives some recommendations for the designer to implement a cryptographic IP module that would resist to HTH insertion; that is either the HTH fails to be inserted by lack of resources, or it will be detected after fabrication with our low-cost visual detection based on layout/picture comparison. Finally conclusions and perspectives are drawn in Section VI. In the appendix A, the setup to test the proposed fault-based HTH is presented.

II. Proposal for a Low Gate Count Hardware Trojan Horse in AES

A. General Background on Differential Fault Analysis and AES Physical attacks which target the implementation of cryptographic circuits (in smartcards, pay-TV and SIM cards, etc.) have been known for some years now. They are widely classified as "observation" and "perturbation" attacks. Observation or side channel attacks (SCA) consist in observing physical emanations of the system, like power (Differential Power analysis, or DPA [START_REF] Paul | Differential Power Analysis[END_REF]) or E/H field (ElectroMagnetic Analysis, or EMA [START_REF] Quisquater | ElectroMagnetic Analysis (EMA): Measures and Counter-Measures for Smard Cards[END_REF]). Thereafter statistical tools are deployed to find dependency between the predicted and observed behavior. Perturbation or fault attacks consist in the injection of faults during the execution of a cryptographic algorithm [START_REF] Blömer | Fault Based Cryptanalysis of the Advanced Encryption Standard (AES) Financial Cryptography[END_REF]. From the knowledge of one or multiple couples {correct ciphertext, faulted ciphertext}, some hypotheses on the secret key can be discarded. This generic attack strategy is referred to as DFA (Differential Fault Analysis). DFA is very effective against some cryptographic algorithms. For example in AES, the number of faulty ciphertext required to break the key can be as low as two 1 . There are several techniques known for fault injection in a system [START_REF] Joye | Fault Analysis in Cryptography[END_REF]. The variations of the supply voltage, overclocking, temperature increase, or the irradiation by a laser beam will most probably lead to a wrong computation result that can be exploited to realize a DFA. This kind of attack represents a real threat for the implementation of cryptographic algorithms such as the AES.

In the sequel, and without loss of generality, we focus on the 128-bit version of AES. AES is a substitution permutation network (SPN) product block cipher. It has an iterative structure, consisting in the repetition of ten rounds which are applied to the 16 bytes data block to be encrypted. The 16 bytes are laid out as a matrix of four columns of four bytes s i, j , where 0 ≤ i ≤ 3 and 0 ≤ j ≤ 3. A round consists of a fixed sequence of transformations. Apart from the first and the last rounds, the other eight rounds are identical and consist of four transformations each. The first and last rounds are incomplete, so as to ease the decryption. The four round transformations are called SubBytes, ShiftRows, MixColumns and AddRoundKey.

Piret's DFA [START_REF] Piret | A Differential Fault Attack Technique against SPN Structures, with Application to the AES and Khazad[END_REF] assumes only a random "byte-flip" in the last or antepenultimate encryption round. This means that the state state 9 at the 9th round (in the case of AES-128), is replaced by state 9 ⊕ ǫ, where ǫ is a 16 byte vector where only one byte is nonzero:

state 9 fault injection -----------→ state 9 ⊕ ǫ . (1)
It is an attack that consists in solving a system of nonlinear equations with Boolean variables: the 128 + 8 unknown variables are the key and the fault, whereas the 128 + 128 known variables are the correct and the faulted ciphertexts.

In fact due to the linearity of the MixColumns transformation there are 255 × 4 possible differences at the output of the MixColumns. If we suppose a fault on one input byte of the last MixColumns it will affect 4 bytes of the output as shown in Fig. 2 and if we use a pair of correct ciphertext C and a faulty ciphertext F, we can make a guess about 4 bytes in the key using Piret's algorithm [START_REF] Piret | A Differential Fault Attack Technique against SPN Structures, with Application to the AES and Khazad[END_REF]. Eight single faults, located by pairs in the four columns before the MixColumns stage of the ninth round (further referred to as "Round 9") permits the unveiling of the whole key. Alternatively, for this attack, only two single faults located before the MixColumns of the eighth round (further denoted as "Round 8") allows the attacker to find the 16 bytes of the key.

B. DFA-based AES Hardware Trojan Horse

Fig. 3 shows an example of a HTH introduced in an AES coprocessor. The inserted HTH aids the attacker to perform faults compliant with Piret's DFA. It has three activation conditions:

1) First of all, an external switch (optional) should be activated; it allowed us to validate the design without and with the HTH, simply by moving a sliding lever of a DIP switch on a SASEBO-GII board (for details, please refer to appendix A). 2) Second, the HTH tests that the round counter is equal to 8. As already mentioned, in this round, the fault is scattered to all of the 128 bits of the ciphertext, and these faulted bits allow to retrieve the complete last round key.

3) The third activation condition is a pattern detected in the plaintext. Concretely, our HTH is generic: depending on a parameter N, N bits of the plaintext are tested for equality to one. Such genericity makes it possible for a trade-off: the larger N, the smaller the activation probability (1/2 N ) -by functional test for instancebut the larger the HTH (its size grows roughly speaking proportionally with N). A working example of this HTH on FPGA is shown in Appendix A for N = 16. The HTH payload is a single XOR gate which faults one bit of the AES in the inner eighth round. As a consequence, this HTH is more compact than other HTH that would (for instance) output one round key instead of the ciphertext; such strategy requires at least 128 multiplexers. In our setup, the attacker needs to activate the HTH for 2 encryptions to retrieve the whole key. The power of the attacker will be determined by the HTH activation circuit. The smaller the activation circuit (Trigger) is applied, the more difficult it is to detect HTH, thus the more dangerous it is.

We stress that some interpretation (in other words, little reverse-engineering) of a GDSII file is needed to identify the resources where to plug the HTH. However, we assume that the localization of the state register (128 flip-flops) is fairly easy, and thus understanding roughly speaking the organization of the layout should be feasible without too much pain.

To some extent, the principle of this fault-based HTH is the equivalent to the "intentionally leaky" blocks discussed in [START_REF] Kasper | Side channels as building blocks[END_REF] for side-channel analyses, but in the domain of fault injection attacks. Indeed, the side-channel (resp. fault injections) attacks are used for a constructive feature (although our HTH actually implements a malicious functionality!).

Finally, let us mention that, to our best knowledge, the first HTH that relies on the insertion of a distant fault injection mechanism is the "bug attack" [START_REF] Biham | Bug attacks[END_REF]. It consists in slightly altering a hardware integer multiplier, in such a way it delivers always the correct answer but for at least one configuration of the inputs. It has been shown by Biham, Carmeli and Shamir that this permits a remote Bellcore [START_REF] Boneh | On the Importance of Checking Cryptographic Protocols for Faults[END_REF] attack that allows, for the insider who inserted the HTH and under some circumstances (e.g. depending on the padding scheme), a retrieval of the private key. The HTH presented in this section is based on a similar idea that allows a remote DFA on symmetric block ciphers.

C. Text-Only DFA-Based Hardware Trojan Horse

The Hardware Trojan Horse described in the previous section II-B might seem awkward. Indeed, its trigger condition requires the conjunction of several events, including a specially crafted plaintext and an explicit binary activation. This choice had been motivated by the ease to test it on the SASEBO board. Nonetheless, it is possible to devise a hardware Trojan horse which does not require the binary activation input, while still allowing for a key extraction by DFA. One first method simply consists in designing the Trojan so that it is sequential. For instance, its trigger condition can be as follows:

• If the plaintext has such distinctive characteristic, then • inject a fault in the antepenultimate (i.e., last but two) round of the next encryption.

The attacker then simply sends twice the same plaintext with the activation condition. The first one will be encrypted correctly, while the second one will be corrupted. Hence a DFA attack is possible.

An alternative solution is to design an AES block which is able both to encrypt and decrypt. The Trojan activates after the second round (i.e., mirror to the antepenultimate round) of decryption, when some specially crafted ciphertext is submitted. Let us denote one of such ciphertexts as c. The (faulted) decryption yields an erroneous plaintext p ′ . However, owing to the invertibility of the AES rounds and of the fault injection (modeled as an exclusive-or with the staterecall Eqn. ( 1)), it can also be considered that c is the faulty ciphertext associated with the encryption of the plaintext p ′ , which unfolded without error until round nine (as for AES-128), where a fault is injected. Thus, it suffices for the attacker to request the encryption of p ′ , which will execute without fault (since the Trojan is only active in decryption mode). This encryption yields c ′ , the correct ciphertext associated with plaintext p ′ . Therefore, the pair (c, c ′ ) allows to mount a DFA attack.

Still, we notice a limitation. Both solutions have a drawback: they do not work in the presence of some modes of operation, because the inputs of the (trapped) AES cannot be chosen.

A. Reverse Engineering

Reverse engineering is often used in the semiconductor industry to extract technical or patent related information from a competitor's chip [START_REF]Silicon Investigations[END_REF]. The chip can be reverse engineered at different levels like: product components, systemlevel, process-level and circuit-level [START_REF] Torrance | The state-of-the-art in semiconductor reverse engineering[END_REF]. In our case we are interested with the circuit-level reverse engineering. Modern devices are fabricated in technology like 45 nm or lower which can have up to 12 layers of metal and several millions of transistors. The detail of the circuit are extracted in the following sequential steps:

• package removal; • delayering; • imaging.
In the state of the art, "destructive reverse-engineering" can be used to detect HTH for our scenario. Reverse-engineering is generally performed by Chemical Metal Polishing (CMP) followed by Scanning Electron Microscope (SEM) image reconstruction and analysis [START_REF] Torrance | The State-of-the-Art in IC Reverse Engineering[END_REF]. It helps to reconstruct exactly all via, metal and silicon layers. After, the determination of the "correctness" of a chip is performed through visual comparison with a known good example or "golden reference". But this technique is very expensive since it takes a lot of time (hence costs a lot) to realize properly: the mere error in a picture (because the delayering left pieces of material on the chip surface or because the recognition software [START_REF] Schobert | GNU software degate[END_REF] failed) makes the reverse engineering fail. In addition, modern devices are extremely small and densely packed, which makes the cost (in money and time) of reverse engineering even higher.

B. Medium Cost Hardware Trojan Horse Detection

In this paper, we demonstrate that HTH inserted at GDSII level can be spotted with a visual detection technique. The main argument is that the full reverse-engineering is overkill to detect a change in a layout. Mesoscopic imaging (obtained with a ×150 optical microscope) is enough to conduct a coarse imaging comparison between the GDSII file submitted for fabrication and the returned circuit. High-end visible-light microscope and camera are termed specialized equipments in the attacks quotation application note [15, §3.7] (for Common Criteria [START_REF]Common Criteria (aka CC) for Information Technology Security Evaluation[END_REF]), which means that they considered medium cost laboratory tools. Indeed, the low-level (masks drawing) "bitmap" comparison of two images is a more elementary task than a full-fledged reverse engineering (that in addition aims at interpreting the layout, i.e. reconstruct the netlist, by giving sense to the picture). Still said differently, reverse engineering is well suited to perform an "image versus netlist" comparison, whereas we research in this paper to make a sheer "image versus layout" comparison.

By optical observation, the M6 shape (topmost layer) can be recovered. For example, Fig. 4 shows the layout and the picture of the fabricated chip side-by-side. The layout is opened in Mentor Graphics Calibre Litho View tool (r2102-4.25), because it allows to set the color and the transparency level for each layer. Specifically, we decided to represent the topmost metal layer with a solid color, as this corresponds to the non-transparency of this layer by optical microscopy. The pictures were taken by a confocal microscope with a ×150 lens, and are presented in real colors (i.e. no image edition has been performed: the image is raw). In the picture view, the L shapes (that appear "white") are aluminium dummy fillings 2 . added to meet the density constraints of design rules. These (innocuous) shapes cannot be seen in the layout view because they are added by the silicon founder at masks preparation steps. The technological node is 130 nm, where the metal lines are in copper (that appear in "orange" color). The M6 lines are rather routed vertical (but for the ring). Their smallest width is 460 nm. To a lesser extent, the M5 lines can be seen: those are thiner lines (100 nm large). The L shapes slightly mask M6 / M5 layers, but still the lines can be seen. In the "side of the module" area of Fig. 4, various power and ground rings are visible. In the "middle of the module" area of Fig. 4, power strips and some signals of the AES core are visible. Some of them are very noticeable, as they are making turns or even zigzags (i.e. multiple jogs). If the chip has a shield layer (refer to [START_REF] Briais | Random active shield[END_REF]), then the image recognition might be harder.

Our experiments are low cost, insofar as the circuits are not depassivated (hence images are slightly blurred). Notwithstanding we see that the pictures and the GDSII remarkably match. Therefore, any single modification of the M6 (or M5) routing could be easily detected visually.

In addition, the analyzed circuit remains functional, and so it can be trusted alone. Indeed, in the case where both circuits with and without HTH are produced, then the absence of HTH 2 Given the orientation of the picture, each L shape appears like a Γ symbol. on one circuit cannot prove the absence of HTH on all the circuits. Now, if we extrapolate to technologies where the feature size is smaller (i.e. < 130 nm), a visual inspection might be more delicate, and probably more error-prone. This is why in the next section IV we use a statistical tool (viz. the crosscorrelation) instead of the exact shape recognition.

It can be argued that it is possible for the designer of a HTH to route it using the inner metal layers (<M6). For small HTHs, this is certainly true. However, when the HTH becomes larger and larger, then low-level metal layers (M1, M2, etc.) are already very crowded, and thus will feature a faster congestion. For instance, in our AES module, the routing density per layer for a core utilization rate of 95% is given in Tab. I. For reasonable size hardware HTHs, the higher metal layers are more likely to be used for routing the HTHs. Tab. I also shows for AES infected with HTHs of size N = 1 to N = 128. Obviously, some parts of the lower metal layers are also used for routing. For the success of our method of visual detection, it is sufficient that the higher layers are used for routing some part of the HTHs. The higher the layer used for routing the HTHs the simpler is it detection. Therefore if only a small part of the HTHs uses the M6 tracks for routing, our method can detect the presence. We do not need to go down the other layers. But if the HTH is routed in lower level metals, then circuit must be delayered. This operation is more costly, however, since the passivation has been removed, the layout stands out more clearly.

As a consequence, the strategy of an attacker is to make the HTH as furtive as possible. Typically, she cannot change the dimension of the IP block, because this will be the first check made by the designer. So, the attacker must meet the challenge to interleave the HTH gates and interconnections signals inside the existing layout. Moreover, to be as discreet as possible, low-level metal layers should be preferred.

However, as will be argued in the next section (and quantified with similarity metrics), it is extremely difficult to insert logic (even some a couple of tens) in a design that is already compact (density over 80%) without changing the appearance of the layout.

Side of the module

IV. AES Hardware Trojan Horse Layout Study

A. Experiment Setup

In this experiment, we evaluate the feasibility and impacts of HTH insertion at layout level. First, we create a circuit layout without HTHs and then we insert a HTH with different sizes in this layout while maintaining the IC placement and the routing. After, we calculate the cross-correlation between these layouts (layout without HTHs and layout with HTHs inserted) to see the impacts of HTH insertion. The Cross-Correlation CC is defined as the measure of similarity between two waveforms or processes f 1 and f 2 . It can be expressed as:

CC = Σ x,y f 1 (x, y) • f 2 (x, y)
However, for image processing, cross-correlation may not be an optimal metric. The problem arises from factors like light-ning and exposure conditions. In such cases, the Normalized Cross-Correlation (NCC) is recommended, which normalizes the images before applying correlation. It is expressed as:

NCC = 1 n x • n y • Σ x,y f 1 (x, y) -f 1 • f 2 (x, y) -f 2 σ f 1 • σ f 2 ,
where n x (resp. n y ) is the number of x (resp. y) values. NCC is relevant to compare two heterogeneous objects (e.g. image versus GDSII), unlike the "difference" that applies only to two homogeneous objects (e.g. GDSII versus GDSII). We also introduce another notion i.e. Reverse NCC or RNCC expressed as:

RNCC = 1 -|NCC| ∈ [0, 1] .
The sole purpose of defining RNCC is for better visibility of results. If the NCC between the image and the layout is low then RNCC will be high and it will be easy to distinguish the error.

An AES 128-bit algorithm, as shown in Fig. 3, is implemented to perform this experiment. Different AES layouts with different core utilization rates are generated thanks to Cadence Encounter (product SOC version 2012/8.1) software. Core utilization rate is the area occupied by the standard cells of the AES circuit relative to the total area of silicon. For each core utilization, 8 HTHs with different sizes are inserted. The structure of the HTH "trigger" consists in a series of AND gates, as depicted in Fig. 5. The size of HTH is the number of AND gates which varies from 1 gate to 128 gates. These HTHs will observe the N inputs of the AES circuit and inject a fault to the 8th AES round when the corresponding inputs are in the high state. Of course we are aware that less than (N -1) AND gates might be needed to observe N inputs (because of optimization with complex gates and use of inverted NAND gates instead of AND gates), but we use a 2 input AND tree to have a regular structure. It has the advantage of growing linearly with the number of input bits observed, which allows for a simple law to quantify the impact of HTH size on the AES layout. The next section shows the result of this experiment.

To maintain the placement and the routing of AES circuit, we use the "ECO Placement" function of Encounter software. The "ECO" option (short for "Engineering Change Order") is a local modification, customarily used to fine-tune a design before tape-out. It allows to modify a couple of gates / nets, without affecting the rest of the circuit, considered acceptable. First, this function verifies the layout (with Design Rule Checking, aka DRC). Second it inserts standard cells of HTHs in unused places in the circuit. At the end, it routes all HTH nets while minimizing the modification created to original layout. The core utilization rates used are 50%, 60%, 70%, 80%, 90%, 95% and 99%. Eight different HTHs used are 1, 2, 4, 8, 16, 32, 64, 128 AND gates HTHs. In total, 63 different AES layouts were generated thanks to this software (7 original layouts for each core utilization rate and 56, 8 for each core utilization rate (CUR), modified layouts).

B. Experiment Results

In reality, we can see only the last metal and isolation layers in the pictures taken by microscopy. Because of this, for the first experiment, all AES layouts generated show only the 6th metal layer (the last metal layer in our case) and hide others layer. Fig. 6(a), 6(b) and 6(c) show the original AES, and two modified AES layouts (with 1 AND gate and 128 AND gates HTHs) for 50% CUR. Visually, there is very little difference between these layouts. By using cross-correlation calculations, we can extract their differences.

The Tab. II indicates all NCC between these layouts. Each line shows NCC between AES with HTH and original layouts for the corresponding core utilization rate. Note that these coefficients are the comparisons between GDSII files so they are calculated in the best cases. This result shows that NCC decreases when core utilization rate and HTH size increases. We realize that for CUR more than 80% and for HTHs more than 64 gates, NCC decreases by about 10% or more. So these HTHs can be detected. In this experiment, 64 gates are equivalent to about 0.5% of AES circuit which is composed of 12, 267 standard cells . The values in bold correspond to the cases when "ECO placement" function cannot place and route HTHs without making errors in the layout. In these cases, we must replace and reroute of all standard cells (AES and HTH standard cells). This causes a big difference compared to the original layout (NCC equal to 0.4010 & 0.3798) and so the resulting HTH insertion is easy to detect. Values "X" mean that even with replace and reroute of all standard cells, Encounter cannot achieve the layout without errors.

The fact that "ECO placement" is able to place an HTH of 128 gates when CUR is 95% but fails for 90%, is a property specific to our design and not at all generic. Probably this would not hold for another design; actually, we expect that the NCC decreases with the CUR (provided we could estimate the NCC over a large number of circuits).

In addition, at the cost of depassivation and of the dissolution of the oxide layers 3 , it becomes possible to observe from the top the superimposition of all the metal layers [START_REF]SEMATECH Surface Preparation and Cleaning Conference[END_REF]. With such a preparation, the HTH will obviously be spotted more accurately. We recomputed the cross-correlation under this assumption. This time, all AES layouts (GDSII files) show all metal layers. Fig. 7(a), 7(b) and 7(c) show the original AES, and two modified AES layouts (with 1 AND gate and 128 AND gates HTHs) for 50% CUR. The Tab. III indicates all NCC coefficients between these layouts. By observing Tab. II and Tab. III, we notice that NCC coefficients for 6th metal layer AES layouts are better. This is expected because adding all metal layer into NCC computation is equivalent to adding noise to the computation. For a strong attacker who can restrict the HTH to lower metal levels, the computations for all metal layers layout can be applied for detection.

We also compute the pixel-wise difference between the two and Fig. 6(c). We notice that these differences are small but they are concentrated in areas where the HTH standard cells are actually placed. Following this observation, we realize a grid-wise RNCC calculations for these layouts. The principle is to split into several pictures of same size using a grid. Each sub-picture of a given layout is then correlated with the corresponding sub-picture of the reference layout. Grid-wise RNCC permits not only to detect the trojan but also localise it visually. The Fig. 9(a), 9(b), 10(a) and 10(b) show the grid-wise RNCC of the AES HTH layout (1 and 128 AND gates) for 50% and 95% core utilization rates. For these calculations, layouts are cut in 32 parts horizontally and in 31 parts vertically. So there are in total 32 × 31 = 992 pieces and also 992 correlation coefficients without overlap for each comparison. Note that these coefficients are reverse correlation coefficients (i.e. 1cross-correlation coefficients) for being seen better in the figures. We notice that the cross-correlation coefficients were improved. HTH standard cells can be also localized with this technique and also be detected easier (see in [START_REF] Kömmerling | Design Principles for Tamper-Resistant Smartcard Processors[END_REF] how to prepare a circuit accordingly with HF).

C. Validation on a Real Trojan Horse Insertion

In order to validate the relevance of NCC as a tool to measure the similarity between an observed image and a reference layout, we actually tested this metric in the real context of HTH recognition. Figure 11 shows two GDSII layouts, one infected and the other genuine.

Obtaining an infected GDSII is not a practical assumption. Fabricating a golden reference circuit in an trusted fab is neither a practical assumption. Thus, the detection shall be based only of the comparison between the genuine GDSII and the fabricated chip, that may (or not) contain a HTH. If the untrusted chip contains a HTH, the NCC value will indicate its presence to the designer. To validate our concept, we perform the following operations.

1) We fabricated a chip which contains a very tiny HTH (whose impact at the M6 topmost metal level is only to add two routing wires) and thus we have its GDSII. 2) Since we also know the HTH, we can obtain the genuine GDSII from the trojaned GDSII. 3) Then we take a photo of the chip placed under an optical microscope achieving a magnification zoom of 150×. 4) Finally, we compute the NCC between the photo of the real trojaned chip and the two GDSII available (Fig. 11).

The NCC with a picture (the same as in middle of the module part of Fig. 4, but rotated for the ease of presentation) is computed:

• it is 1.56% between the trojan infected GDSII (unknown to the designer, since forged at the silicon foundry) and the image, • and only 0.67% between the original GDSII (known by the designer) and the image.

We emphasize again that obtaining a trojan infected GDSII is not very realistic. Therefore a designer cannot know the largest cross-correlation that can be obtained between the trojaned GDSII (corresponding to the picture) and the picture. However, the grid-wise NCC method can detect the hardware trojan horse in such cases. It is expected that the grids that are not infected by the trojan, will yield about 1.56% NCC on the layout versus image comparison. Only the grids with a significant lower NCC (0.67%) will raise a concern. Thus, the local variation of cross-correlation, of order (1.56 -0.67)/1.56 = 57%, will allow to signal the presence of a HTH in the design; indeed, 57% is a large contrast. It is important to have such a large contrast, because eventually, the grid-based correlation will be noisy, for several reasons:

• the photographic picture can be blurry,

• the correlation values in areas without HTH might depend on the contents of this very area, • obstacles, like the superimposed L shapes in M7, might not be evenly distributed over the grid. However, if the M7 L shapes are clearly identifiable, the contrast can be increased by removing (i.e. by replacing them by black areas) from both the picture and the layout.

To further investigate, the designer can then focus on the infected area by repeating the same detection technique with magnified pictures (of local SEM imaging) to attest the presence of the HTH.

V. Recommendations

During this experiment, we realize that HTHs insertion at layout level is not easy for the attacker. Firstly, he must understand the functionality of the circuit from the GDSII file. Secondly, he must keep the original layout mainly unchanged, otherwise a "forensic" visual inspection is very likely to detect the HTH. Thus the HTH must be placed-and-routed inbetween the (unaltered) existing circuit. Results, given in Section IV, show that HTHs insertion become more and more difficult when core utilization rate increases. We recommend the designer to use more than 80% core utilization rate (CUR) for his design. From this CUR, the insertion of HTH is very unlikely because of HTH size. If the HTH size is small, this HTH can be accidentally activated and hence can be easily detected at test time. If the HTH has a reasonable size (for example superior to 64 gates in our study case), it is visually detected (NCC decreases by about 10% or less for a CUR superior to 80%). A similar observation was proposed in [START_REF] Wang | Detecting malicious inclusions in secure hardware: Challenges and solutions[END_REF], where the authors recommended to avoid dead space in an IC in order to prevent HTH insertion. We reconfirm the same observation and take it a bit further in order to quantify it in terms of core utilization rate. With this, either the HTH insertion fails (because it is too large w.r.t. the available placeand-route resources 4 ), or its insertion can be detected with a medium cost visual technique. Further, our criteria based on the CUR is "global" to a design, and can easily be set as a constraint in all P&R tools.

VI. Conclusion and Perspectives

In this paper, we have presented the feasibility and impacts of HTHs insertion to the circuit layout (especially for AES circuit). Additionally, we have demonstrated the possibility to detect HTHs with a medium cost visual technique; this technique can be automated thanks to a cross-correlation. In particular, the observation of the sole top-level metal layer suffices (for large enough HTHs); thus the method avoids mechanical or chemical preparation, known to produce dust of material that would cause many false positive detections. As a corollary, if no HTH is detected in the observed circuit, then this circuit can be trusted and used safely in an application, even if other circuits from a different batch happen to be infected by a HTH. The results show that the insertion complexity and the visibility of HTH increases with the core utilization rate of circuits. With a high CUR, HTH can be detected by comparing layout images and GDSII file. This technique cannot detect HTH inserted in specification or RTL level but it can be combined with others detection techniques to ensure the security of the full fabrication process.

Checking for the genuineness of an observed picture (such as the lefthand side of Fig. 4) against a known template (such as the layout at the righthand side of Fig. 4) can benefit from better decision strategies than a simple correlation. Indeed, the layout is rich of particular features. Thus, for instance, minutae analyses for fingerprint recognition can be used advantageously (using routing zigzags for instance); those techniques are also interesting insofar as they allow to tune the false acceptance/rejection rate(s). However, application of minutae-like features in context of HTH is an open research topic. In our case, as we do not want to accept as genuine a trojaned circuit, we intend to configure the technique to minimize its false acceptance rate.

Figure 1 .

 1 Figure 1. Minimalist Hardware Trojan Horse example

Figure 2 .

 2 Figure 2. Effect of a fault in last but one round of AES-128.

Figure 3 .

 3 Figure 3. Differential Fault Analysis (DFA) based HTH in AES -Illustration of a remote DFA enabled by the HTH

Figure 4 .

 4 Figure 4. Picture (left hand side) and GDSII layout (right hand side -M6 in orange for Middle and Side of the module, M5 in yellow for Side of the module) of an AES-128 cryptographic accelerator (area size: 67 µm × 60 µm)

Figure 5 .

 5 Figure 5. HTH with N -1 AND gates (AND tree) inserted in AES circuit

Figure 6 .Figure 7 .

 67 Figure 6. 6th metal layer AES layouts (1200 µm × 1200 µm) with 50% core utilization rate for (a) Original AES, (b) AES with 1 AND gate HTH, (c) AES with 128 AND gate HTH

Table I

 I Usage of routing resources per layer for the AES case-study with 95% core utilization rate

	Density	Layer	M1	M2	M3	M4	M5	M6
	N = 0		44% 22% 20% 17% 10% 5%
	N = 1		44% 22% 20% 17% 10% 5%
	N = 2		44% 22% 20% 17% 10% 5%
	N = 4		44% 22% 20% 17% 10% 5%
	N = 8		44% 22% 20% 17% 10% 5%
	N = 16	44% 22% 20% 17% 10% 5%
	N = 32	44% 22% 20% 17% 10% 5%
	N = 64	44% 22% 20% 17% 10% 6%
	N = 128	44% 22% 20% 18% 11% 6%

Table II NCC

 II Coefficients between 6th metal layer of Original and Infected AES layouts

					HTH size (Nb of AND gates)
			1	2	4	8	16	32	64	128
		50%	0.9991	0.9972	0.9981	0.9950	0.9933	0.9918	0.9815	0.9668
		60%	0.9987	0.9968	0.9959	0.9955	0.9944	0.9893	0.9788	0.9670
		70%	0.9989	0.9981	0.9918	0.9941	0.9881	0.9850	0.9594	0.9067
	CUR (Core Utilization Rate)	80%	0.9999	0.9965	0.9898	0.9957	0.9780	0.9711	0.8970	0.8509
		90%	0.9988	0.9990	0.9983	0.9962	0.9832	0.9572	0.8858	0.4010
		95%	0.9997	0.9984	0.9980	0.9889	0.9589	0.9115	0.8824	0.8202
		99%	0.9917	0.938	0.9714	0.9527	0.3798	X	X	X

Table III NCC

 III Coefficients between all metal layers of Original and Infected AES layouts

					HTH size (Nb of AND gates)
			1	2	4	8	16	32	64	128
		50%	0.9996	0.9788	0.9794	0.9770	0.9766	0.9760	0.9719	0.9708
		60%	0.9993	0.9975	0.9973	0.9970	0.9964	0.9923	0.9843	0.9783
		70%	0.9991	0.9987	0.9947	0.9952	0.9924	0.9889	0.9655	0.9272
	CUR (Core Utilization Rate)	80%	0.9997	0.9976	0.9942	0.9969	0.9868	0.9790	0.9291	0.8915
		90%	0.9990	0.9988	0.9981	0.9964	0.9878	0.9709	0.9255	0.5162
		95%	0.9995	0.9978	0.9974	0.9927	0.9742	0.9387	0.9159	0.8661
		99%	0.994	0.9965	0.9803	0.962	0.4905	X	X	X

Recently, some even stronger attacks have been presented[START_REF] Tunstall | Differential Fault Analysis of the Advanced Encryption Standard Using a Single Fault[END_REF]; the idea is to exploit further relationships from the key scheduling logic to end up with a Boolean equation system that solves the key with one fault, albeit at the cost of more computation. For the need of our HTH design, both types of DFA would be equally adequate.

Those oxide layers are also known as "inter-level dielectric" (ILD) or simply "passivation layers".

In particular, our experiments with the Cadence Encounter place-and-route tool show that even if there is "physically" some room for the insertion of the HTH, the routing-aware placer and the router itself can fail. This is because space on the die is not the limitating factor for the HTH, but rather the availability of free routing tracks.Besides, we could also profit of advanced techniques such as those used in steganalysis to detect a piece of information (the HTH) hidden in noise (the genuine layout).

Acknowledgments

This project has been funded by the French Government, under grant FUI #14 HOMERE (Hardware trOjans : Menaces et robustEsse des ciRcuits intEgrés). We acknowledge interesting inputs from the other members of the consortium, in particular Julien Francq (Cassidan Cyber Security) and Denis Réal (DGA). Also, while preparing the camera-ready version of the paper, we appreciated the positive inputs from Nicolas Bruneau, Guillaume Duc, Zakaria Najm, Pablo Rauzy and Youssef Souissi (crypto group of TELECOM-ParisTech). Besides, we are grateful to Yves Mathieu for the setup of the Calibre LITHO view tool, to Antoine Khy and Fabien Thomas-Brans for pictures, and to the CMP [13] staff (especially Kholdoun Torki and Jean-Franc ¸ois Paillotin) for an excellent support in the fabrication with STMicroelectronics HCMOS9GP technology and the after-sale maintenance of the SecMat-v2 ASIC [17, Fig. 1]. Eventually, we are grateful to Prof. David Naccache for the suggestion about a DFA-based hardware trojan that would trigger only on some plaintexts.

Appendix A Example of DFA on AES Infected Hardware Trojan Horse on SASEBO-GII

We implemented a HTH in an AES coprocessor to facilitate Piret's DFA. The HTH gets activated when the switch is on and the first two bytes of the plaintext are equal to 0xff; it is thus an instantiation of the generic HTH depicted in Fig. 3 with parameter N set to 16. This configuration leads us to a unique key in a total of 4 encryptions. The key used in our example is same as in Appendix B of the AES standard [START_REF]Advanced Encryption Standard (AES)[END_REF]. The design is tested on a SASEBO-GII board running on the Virtex-5 FPGA. Tab IV compares the cost and performance of a HTH as described before which gets activated when the first two bytes of the plaintext are equal to 0xff i.e. N = 16. The HTH is very small i.e. only 10 LUTs and causes speed degradation of 1.6% (indeed, our HTH adds one XOR gate on the critical path). This configuration helps us to easily implement Piret's Attack. Recall that the signal activation cond[0] is an input of the trigger part of the HTH; thus both a faulted and a fault-free ciphertext can be obtained (which is required for the DFA of Piret and Quisquater). In Tab V, we give the transcript of an example of the Piret's Attack on an AES implementation with our inserted HTH.


Luc Gwiazdzinski

Teenagers in the Contemporary City: Hypermodern Times, Spaces and Practices

Keywords: Youth, Everyday life practices, Public space, Mobility patterns, design, Spacetime use, Chrono-urbanism Adolescents, Temps des villes, Espace public, Design, Usages spatio-temporel, Chrono-urbanisme

This chapter aims to examine teenagers' practices in public space, the modes of appropriation that stigmatise certain types of places and worry parents and adults, particularly in the evening and at night. It is based for the most part on a study conducted for the French Union of Holiday Centres (UFCV) on 'teenagers' times and spaces of sociability' and on a more detailed survey conducted in the outskirt area of Besanc on, in Eastern France. Our study highlights the importance of a spatial and temporal approach to youth, at the level of living areas, so as to allow for the co-construction, locally and with the youth, their parents and residents, of projects and policies adapted to their needs. The chapter emphasises the necessity of transcending preconceived ideas about teenagers, to acknowledge and respect their temporalities, in order to be able to conceive a city and public spaces that are more accessible and welcoming, places where they can express themselves and places where they can hide: ordered times and places but also places and times for freedom and adventure. More generally, these populations, whose behaviour is increasingly mobile, fragmented and unstable -caricatures of a hypermodern society -call into question the urban fabric, the duality and diversity of urban times and spaces. Between the 'polytemporal city' and the 'a` la carte city', the boundaries are increasingly blurred.

Introduction

Each society produces its own temporal system (Sorokin 1964) that results from the combination of all the social activities conducted in it. Time is the product of social activities and is the abstract measure of concrete things [START_REF] Sue | Aube. Il a également dirigé une agence des temps et des mobilités, une agence de développement et une agence d'urbanisme et développement durable[END_REF]. When and where can we create and form a territory, a community, a family, in an increasingly fragmented society (Gwiazdzinski 2003(Gwiazdzinski , 2007a[START_REF] Gwiazdzinski | Nuits d'Europe. Pour des villes accessibles et hospitalie`res. Ministe`re des transports. UTBM Editions, Belfort Gwiazdzinski L[END_REF]? Acceleration, mobility and the disappearance of great collective rhythms all call into question the foundations of collective life. Even leisure time is under pressure. In this 'a` la carte society', we struggle to resist the demand for non-stop activity and individualism. Barriers emerge between individuals, groups and generations at the expense of social cohesion. Evenings, Sundays, meals and holiday times, for example, have become particular and fragmented times during which intergenerational sharing no longer necessarily occurs, and which need to be reexamined (Gwiazdzinski 2005;[START_REF] Gwiazdzinski | Les de fis de la citoyennete ́ augmente é[END_REF].

In the face of this acceleration, it seems necessary to take a pause and to examine, in particular, the times that characterise the lives of the youth and teenagers. The aim is not to envisage them as disparate tribes exclusively defined by their behaviour, or as mere targets of marketing, but rather to bring to light their practices, life rhythms, mobilities and needs without isolating them from the rest of society.

Everyone talks about the 'youth' but in actual fact no one really knows them, especially teenagers. There is a belief that we know who they are, what they want and what they do until they are about 13 years old. Later on, adults have more difficulty understanding them (Dubet 1991;[START_REF] Singly | Sociocultural causality space, time: a study of referential principles of sociology and social science[END_REF]Fize 2009). Parents no longer recognise them. Public representatives fear them, particularly when they gather at bus stops or in the lobbies of apartment buildings. Youth activity and support organisations do not really know how to take care of them anymore. The groups that form and dissolve within a few days, the short-lived fads, changing tastes, the need for freedom and emancipation which traditional support systems poorly satisfy and their mobility make for a difficult task (Gwiazdzinski 2007b). Grown-ups criticise them, fear them and fantasise over them -particularly in terms of sexuality -forgetting, in the process, the kind of youth they themselves used to be not so long ago. Even though everyone speaks 'in their name' or 'for their sake', the youth are given very little consideration in public policies, which currently focus on the other opposite end of the life span: old age.

A First Approach

The spaces, times and practices of teenagers remain to be explored, not only by researchers but also by the public authorities.

Strangers. It seems that only clothing brands have 'figured out' this population; they target, very successfully, the 'youth' and segment the 'potential market ' into 'pre-teen', 'teen' and 'adolescent' categories. In all cases, we often criticise young people, we observe and worry over them, and yet, we spend our time mimicking their likes, dislikes and behaviours in terms of fashion and music; we even use their language and beg for their expert help in matters of information and communication technologies -for better or for worse.

ANeedforExploration. Several changes in daily life can be analysed from the point of view of time [START_REF] Barclay Carlstein | La ville 24h/24? L'Aube, La Tour d'Aigues Gwiazdzinski L[END_REF][START_REF] Bonfiglioli | Villes et politiques temporelles[END_REF][START_REF] Lepetit | Temporalités urbaines. Anthropos[END_REF][START_REF] Henckel | Alles zu jeder Zeit. Die Städte auf dem Weg zur kontinuierlichen Aktivita ẗ[END_REF][START_REF] Boulin | La ville à mille temps. L'Aube[END_REF][START_REF] Barclay Carlstein | La ville 24h/24? L'Aube, La Tour d'Aigues Gwiazdzinski L[END_REF]Boulin 2008;[START_REF] Marregi | Ritmi urbani. Maggioli[END_REF]. This is the reason why it is necessary to perform chronotopic studies of young people and their spatial practices (Gwiazdzinski 2007c), using a 'rhythm-analytical' (Lefebvre 1992) approach that will take into account the territory, the uses and users at different times of the day, of the week or of the year. The first elements presented here are based for the most part on a study on the different time periods in the daily lives of teenagers, conducted as part of a national, experimental initiative and for the French Union of Holiday and Leisure centres (UFCV). A first series of studies conducted in ten holiday centres and extracurricular organisations had led to a number of conclusions concerning leisure times and the youth (Gwiazdzinski 2007b).

An Observed Evolution. The evolution of social times has an impact on the internal functioning of leisure centres as well as on the quality of life of parents, social workers and children. Pressure from outside the centres affects the workers and the children. The children and social workers are pressured by more and more demanding parents who want more activities, production or outings. Recovery times like breaks, naps, quiet times or mealtimes are under threat. The times allotted for being together with other individuals are fewer and fewer. The essential interactions with parents and local actors are more and more difficult, in a context in which those organisations are more and more used as babysitters. The importance and respect of individual choice have become central issues, in spite of, or because of, collective living. Finally and above all, the studies have raised the awareness of the difficulties facing the parents and traditional youth facilities in supporting or supervising a particular category of young individuals -teenagers -during their leisure times and have given rise to a desire to find out more about their temporalities, territories and practices, topics we had already explored in the context of participatory protocols in another region of France: In the Belfort area, through several research programmes on the mobility of young people, for the PREDIT (Programme of research, experimentation and innovation in land transport), in Nanterre, for the Youth Congress, and in other studies and programmes conducted at different scales in urban as well as in rural areas.

Objectives and Protocols of Exploration. The area chosen for this work is com-prised of five small towns in the north of Besançon, Eastern France. The area in question represents a population of 10,000 inhabitants, among whom 1,000 young people aged between 10 and 20. The aim is to gain a better knowledge and understanding of the practices, uses and needs of the teenagers living in these peri-urban small towns, so as to be able, later on, to develop, together with the youth, the professionals, the parents and elected representatives, suitable responses. The overall analytical approach to the times and spaces of teenagers rests on several cross protocols: a substantial awareness campaign, involving the creation and distribution of post cards, leaflets and posters designed with teenagers; a survey on the crossed representations of children and adults, conducted with about 20 families; a mobility analysis based on the GPS monitoring of 15 individuals (young and adult), for 1 week -so as to map their movements and whereaboutsfollowed by a session during which each individual comments the maps obtained; a survey of the territory and of the gathering places, conducted with the gendarmerie; periods of field observations, with adults meeting with the youth of the area, and a survey on the needs of the teenagers (200 questionnaires were analysed and the organisation of creativity sessions and public meetings every other month involving the local youth and grown-ups). This work pursues a strong participatory approach and in particular the setting up of thematic working groups and the involvement of the local actors at the different stages of the initiative.

Particular Ties to the Territory

On the face of it, one cannot say that the youth do not have any ties to the territory.

Territorial Presence. In reality, they are the ones who 'keep' the territory, the district and the village for part of the day; they do so jointly with housewives, retired and unemployed people, when the working residents have gone away to work somewhere else. The phenomenon is very common in peri-urban areas, city outskirts and dormitory suburbs, where, during the day, one only sees these specific population groups.

Territorial Synchronisation. It is also the youth that usually forms the largest battalions of members in sports or cultural associations. One cannot say that they have no ties to the town and society. When everything dissolves and splits (e.g. territories, working hours, organisations, families), the one institution that still stands, the only surviving great social rhythm, is that provided by school. The ringing of the bell provides the tempo for part of collective life and particularly for families with children whose holidays, weeks and days it regulates. School remains a 'time giver' (Sansot et al. 1983), a synchroniser, which, among other things, enables the population of a district or a village to meet.

Territorialised Memories. On a different scale, by taking a look at the work of writers or filmmakers, one can easily see the ties the latter have to their youth and the territories of their youth: a space of play, of transgression, which the child and later the teenager paces and measures; a space he discovers at the same time as he discovers and constructs himself; a space he experiences and in which the first boundaries and limits are erected. Let us remember the first words in Pagnol's trilogy in which he relates how he discovered the hills, with his father the rock partridge hunter, his mother Augustine, his uncle Jules, his aunt Rose, his brother little Paul, his friend Lili and his little sister: 'I was born beneath the goat-crowned Garlaban, in the days of the last goat-herds' (Pagnol 1957, p. 4). Or think of the urban trials and tribulations of the young Jean-Pierre Le áud in Franc ois Truffaut's 'Les quatre cents coups' (Truffaut 1959) or of Romain Duris' adventures in 'L'auberge espagnole' (Klapisch 2002), set at a time in life when the territory of young people opens up to the world.

To See the Particular Ties. That a young person has to the territory, we only need to relive our first school experiences, put a foot on the path we used to walk as a child, and later as a teenager. All we need to do is take a few steps and the memories come rushing back and we soon can feel where we come from. We once again experience a particular territory, which will forever be different to all the other spaces we have experienced since. The change in altitude, the landscape, the colours, noises and smells are all like Proust's little 'madeleines', they are like rugosities that catch the memory. Even though many things have changed, some buildings and people have disappeared, we remember the trees, the stairs, pavements, pedestrian crossings, the snails that stuck to walls on rainy days, the songs of birds in the spring, the moss covering fac ades, the people we bumped into, the baker's shop where we used to buy sweets, the butcher shop, the newsagent and the gardens in blossoms. We rediscover with emotion the hidden groves where we finally plucked up the courage to give our first kiss and the craggy spot where we built a shack or smoked our first cigarette. It was on those paths -which we often walked while playing truant, while we were rubbing ourselves to the land, its open and its concealed corners -that we stepped over the boundaries, tested our limits and that of others. 'We can only discover a place by discovering ourselves' (Maldiney 2007, p. 166) But the territory of childhood can also be a more male, a more warrior-like territory such as that depicted in Louis Pergaud's 'La guerre des boutons' (Pergaud 1912). It was into other spots of this territory that our teacher's 'object lessons' used to transport us and it was that teacher who skilfully introduced us to the trades of the local craftsmen and to the mysterious life of a pond. No one ventures there anymore for security and norm-related reasons. But there is no need here to depict a nostalgic view of youth and of the territory, which many have depicted before us. It was not better before and those who believe it was forget that in those days they were 20. Let us simply agree that strong ties develop between a young person and the territory, during their schooling times -which we have a relatively good insight into -and during leisure times, which we probably do not know quite as well.

Tricky Relations Between Teenagers and Grown-ups

It has to be said, first of all, that young people and adults have complex interactions, in which representations play a large role.

Caricatural Cross Representations. Beyond the cliche ś, young people develop in the image of our society and do so, sometimes, to the point of caricature. When their parents are questioned, rather unflattering words pour out: 'always tired', 'unstable', 'fickle', 'scatterbrained', 'individualist', 'elusive', 'complex', 'contradictory', 'glued to their cell phones' or 'stuck to their pc' (Gwiazdzinski 2007b). What do they express if not the contradictory tendencies of a hypermodern society that fosters complexity and paradoxes [START_REF] Barel | Le paradoxe et le système[END_REF]. When questioned about their parents, young people are not much more tolerant: 'old', 'tired', 'moaners', 'never here' and 'always in a rush' [START_REF] Gwiazdzinski | Nuits d'Europe. Pour des villes accessibles et hospitalie`res. Ministe`re des transports. UTBM Editions, Belfort Gwiazdzinski L[END_REF]. Return of the compliment. This is not to say that this play of cross representations means that the youth do not develop ties with the territory or that they do not engage locally. They do so differently from their seniors, in a more fractional and temporary way, at different scales and in different networks. They are fickle, sometimes seem to be elsewhere, often appear scattered, but they too get involved. The lack of understanding might result from a lack of intergenerational dialogue.

Difficult Dialogue. Teenagers hardly ever get the opportunity to have discussions with adults other than their parents or sometimes their parents' friends, or their cousins. Within the family, it is with their mother and older brothers and sisters that they interact the most. The favoured times for interaction with them are mealtimes and the evenings. They struggle to talk to their parents, particularly to their father. When dialogue does occur, the same issues keep cropping up, at the detriment of a serene exchange: school results, going out to parties and people they socialise with. They resent their parents for wanting to protect them and reproach them for continuing to often treat them like children and for being a little distant from them. They reckon that their parents do not move with the times, that they got stuck in the past. It is interesting to note that when adults are asked questions about their youth, they talk of freedom, of 'life on the wild side', of the first time they got plastered and of their first cigarettes and first kisses. The very people who criticise teenagers readily describe themselves as rebels and miss 'the good old days'.

A Specific Organisation in Space and in Time

TerritoriesofVariableSize. BymonitoringtheitinerariesofateenagerwithaGPS and examining on a map, the routes he travels, one can take a good measure of his life space. Beyond his daily trips to primary or high school, his comings and goings reveal a more or less wide territory and social relations depending on whether he walks or uses his bicycle, his moped, public transport, and according to whether he is a boy and a girl (see Figs. 5.1 and 5.2). This territory, which the young person has visited, figured out and appropriated, grows as years go by, whereas for elderly people it shrinks, 'From bed to window, then from bed to armchair, and then from bed to bed' (Brel 1964).

Practices that Differ from Gender to Gender. The practices, activities and social mobilities of the youth outside school also clearly differ according to gender. For example, time restrictions for going out and restrictions on where they may go are tighter for girls, whom parents watch more closely. Naturally, there are times and places when and where boys and girls meet, but it is interesting to note that the relations young people -as individuals or as part of groups -develop with their territory are strongly conditioned by their gender (see Figs. 5.1 and 5.2). Landmarks for Sociability and for Anchoring. Teenagers often gather in specific places on the territory. Naturally, sports places are part of this social geography: skateboarding parks, the sports field next to a school, the soccer field or even the high school. Consumption places, such as McDonald fast food restaurants, the movie theatres or shopping malls, are important in this geography and constitute real landmarks. The younger children meet at the leisure centres to take part in supervised activities. Later on, the bus stops, the public gardens or the old wash house are all places where young people can meet even in bad weather. They are the equivalent of buildings' lobbies in big cities.

Fig. 5.2 Life spaces, travel routes and modes of transport of a female student during the week (Sylvaine Schlienger, Luc Gwiazdzinski)

And it is those clearly visible gathering places that crystallise the adults' fantasies. Other, less welcoming places, like the fountain behind the graveyard, allow for more intimate meetings. An old, dilapidated caravan served as a landmark for a while. A secret shack plays this role but the caravan sticks in everybody's mind: that of the teenagers who are still angry about it and that of the adults who are glad that this 'gathering and drinking place' has finally disappeared. These gathering places are often marked with territorial graffiti and tags that serve as signals to others that 'this is our turf' and that they must 'stay out'. It is interesting to note that these places last and serve the same functions from generation to generation.

A Tendency of Territorial Control. Teenagers generally restrict their comings and goings to the towns in their area, and when they do go beyond, it is generally to visit the main city in the region. In the summer, a natural sandpit attracts the local teenagers but also those from other areas, who, in the adolescent Imaginary, only come to 'pick fights or take our girls'. Strange stories of drug dealing and of outside dealers circulate among teenagers as well as their parents. Exchanges develop between young people of different towns; parents give their 'big boy' or 'big girl' a lift to a bus stop and fetch them again later. Young people occasionally come from other towns to play soccer or basketball. Children invite one another to their homes; this is common particularly among girls, as it makes it easier for the parents to supervise their daughters' activities and friends.

Breakaways to the City. The teenagers go several times a month to Besanc on, in particular. The girls go for walks about the city and shop for clothes and shoes. The older boys tend to visit the public places of the city centre such as bars and pool halls. Boys and girls meet in the metropolitan temples that the ice skating rink and bowling alley constitute for them. The oldest ones go to nightclubs.

The Constraints Related to Leisure

The functional space of teenagers and their leisure-related practices are necessarily limited by a number of constraints: -A limited space-time budget. Young people claim to be very busy and to have heavy workloads during the week, and that they have very little time for hobbies and friends. Whereas many of the parents have a 35-h per week work schedule, the children themselves complain that they have to work over 40 h a week. -A limited financial budget. The majority of the teenagers get a pocket money allowance of less than AC30 per month. They spend most of their money on video games, airtime, DVDs, movie tickets, comic strips, clothes and sweets. -Going out hours. The days and number of hours children are allowed to go out are restricted and vary depending on their parents' flexibility. The teenagers generally have similar time restrictions. They are allowed out until 7 pm during the week and until 10.30 pm on weekends and a little later in the summer. The hours mostly vary depending on the age and gender of the teenagers. Many of the girls still have to stay at home in the evening until they are 18 years old. -Discriminatory transport modes. In this type of peri-urban territory, it is the parents who generally drive their children to their recreational activities when they take place outside their town. These 'taxi-parents' are not always available. For the other activities, closer to home, the children cycle, walk or use the public transports. For a minority of the children who have problems getting around, the difficulties are mostly related to a lack of public transport or to the fact that bus times might be unsuitable, particularly in the afternoons and evenings. Sociability strongly varies depending on whether the teenager has a scooter or not.

Particular Practices and Behaviours

Observing the recreational activities of teenagers over a given period of time reveals particular practices and behaviours.

Specific Temporalities. Teenagers generally meet on Saturdays,Wednesdays and in the holidays.

They hardly ever go out on Sundays, which are still days for family time; and this does not seem to bother them. They often meet at McDonald's or at the local Kebab place in the early evening.

They arrive at about 8 pm even though there is no prearranged meeting time. They seldom decide in advance what they are going to do and decide at the last minute, depending on the information they have and on what they feel like doing. They claim to get bored on weekends and wish they could go to Besanc on or to a lakeside or river bank. They also get bored in the holidays and get out of bed late.

Holidays. Sports are a large part of teenagers' recreational time, with soccer and basketball being the most popular. When interviewed about their activities when they are together, the teenagers claim that they 'don't do much'. When they can't go to Besanc on, they 'bum around' at the local shopping mall. When they 'go to town', they often just 'hang around'. They chat, laugh, go for strolls or walk to the shack. When asked what their activities are, they generally reply that they do not do anything in particular.

Generational and Territorial Identity. They outhaged between 13 and 18 feel like and call themselves 'teenagers'. Ninety percent of their hobbies are activities they share with other people their age. Most of them claim to be part of a 'group'. Most of them are high school, higher education, technical school students or apprentices. They all claim that they 'like the place' and that they feel attached to the territory even though it is not the place where they imagine living when they are older. The social relations and interactions they develop with other young people present on their territory do not seem to be determined, in any way, by the socio professional status of the parents.

Permanently Connected. Many of the children, particularly the girls, prefer cell phone to direct contact. Most teenagers have a computer (95 %) and a cell phone (90 %), except the youngest ones. They all use the Internet on a regular basis and have an email address. One third of them have a blog. They report spending on average half an hour a day on their cell phone (SMS) (mostly the girls), 2 h a day watching TV and two and a half hours on their computer (e.g. chat, email, discussion forum). The digital game enthusiasts (mostly boys) spend over 3 h a day playing (e.g. console, network games) but do not feel they spend much time doing so.

Instability. Though most teenagers are part of a mix-gender group of about ten friends, the composition of these groups (mostly boys) seems to change regularly, which poses a problem for a researcher. In the realm of friendship, the so-called friends for life sometimes only remain so for a week or so. The children often move from association to association and from club to club so as to try out new activities or new sports. When it comes to matters of the heart, the teenagers are relatively quiet but pride themselves in being unattached. Only a few couples make excessive displays of affection in public.

Presentism. Teenagers struggle to make medium-to long-term plans. They know they will meet at the end of the day or on weekends but generally decide what they are going to do and change plans at the last minute and prefer to decide in the moment according to the best offer or idea.

Space and Time-Related Claims

In the face of the space and time-related constraints that restrict their freedom, and of the absence of certain services, the teenagers have a number of claims.

The Right to Freedom and to Difference. They suggest that the grown-ups 'give them more freedom', 'avoid criticising them', 'stay calm' and 'not be too clingy'. They do not want to be judged or controlled. They do not want to be 'called drunks just because they have a bottle in their hand'. They do not want to be considered as delinquents even though they acknowledge that 'when someone entrusts something to young people, it often ends up being damaged'.

The Right to Idleness. Teenagers demand the right to not do anything, to relax without being deemed 'lazy'. They curse orders to 'get moving!', 'do something' and 'get some work done!'.

The Right to 'Relax'. They refute the adults' claims about alcohol or drugs even though, for the oldest teenagers, a fun evening always starts with the purchase of a bottle. They recognise being attracted to cigarettes, alcohol and even certain drugs. They teasingly remind us that their parents use tranquillizers and sleeping pills to be able to sleep.

The Right to Night Life and Mobility. Their demands revolve around three main areas: the lack of activities and events at night, particularly in winter ('everything shuts down before 11 pm', 'nothing happens at night, there are no parties for young people'); the lack of venues where young people could meet when the weather is bad (no hall or shelter, such as a caravan or bars where they could get together) and the difficulties of getting out of the territory: 'no trips to the swimming pool, to Europa-Park in Germany' and 'no buses in the evening'.

The Right to be Recognised as Equal Members of the Community. They would like to be able to discuss certain topics with their parents, about the 'challenges of life'. They acknowledge that they seldom express this need with their parents or other adults. They know little of the local representatives or their functions. The mayor seems rather unapproachable, and yet they reckon that they need to be able to express and discuss their needs with him. They think that the best way to understand young people is to meet them on their own ground and to ask them questions. More generally, they would like to share more activities, events and parties with the adults. Beyond their demands, the teenagers do offer some propositions.

Propositions to Expand Their Time Horizon and Territory. Their propositions revolve around the possibility to widen their 'play arena' by expanding their time horizon, i.e. by being able to go out for longer hours and to be able to venture further away (spatially), by gaining access to public transports and activities on offer beyond the neighbouring towns. The oldest teenagers (15-18year-olds) would like to go on camps, for example.

Simple Ideas. When they are asked to choose a project, they suggest the idea of a hall with lights, chairs, a sofa, an alcohol-free bar, just as a meeting place; and they also would like a end-of-year group outing. Most importantly, they express the wish to organise these projects themselves and to manage them without the grown-ups constantly peering over their shoulders.

Conformist Dreams. They all see themselves laterin life with a family, and some of them even have an idea of their future profession: doctor, nurse and even policeman.

Contributions to Society

The Advantage of Spatio-Temporal Approaches. Research confirms that a spatio-temporal approach is an asset for understanding individuals, groups, organisations and territories. Time is one of the rare public policy issues that is truly transversal to all public domains. All the sectors of collective life are concerned, whether they be transports, private and public services, housing, schools, nursery school, trade, cultural and recreational facilities, etc. A competence of everyone and no one, time is one of the only themes that make it possible to involve all public and private actors in the debate, without any tension or without anyone retreating behind institutional barriers. Time imposes partnership, from the observation phase to that of experimentation and of evaluation. A sensitive dimension, time naturally repositions man at the heart of the debate. It is an opportunity. Even though the data and observations collected and analysed cannot always be generalised to all teenagers, nor to all European territories, they still provide useful information about territories, society and territories.

Individuals Looking for Hyper Choice. The observation sand interviews conducted in this periurban territory revealed profiles of individuals who are mobile, unstable and connected, who more and more frequently make their decisions at the last minute. They reveal individuals who want more freedom, more mobility and wish to have a say in the decisions that concern them and to participate in projects, locally and elsewhere.

'InfluentialOutsiders'. These teenagers are the outpostsorthe caricatures oft heir seniors. Through their spatio-temporal practices, they outline the contours of a hypermodern society (Lipovetsky 2004; Aubert 2010) that fosters paradoxes: they stick to themselves but want to be more open to the world; they want to be consulted but are seldom available; they want services to be more open but demand the right to do nothing; they want to be surprised but get stuck in routines; they want to meet others but confine themselves at home, in a permanent tug of war between the 'I' and the 'We', the here and there, the real and the virtual.

ThePathstoHyperTerritories. The practices of teenagers outline the contours of a 'widened citizenship' [START_REF] Gwiazdzinski | Les de fis de la citoyennete ́ augmente é[END_REF] that knows no administrative boundaries, cliques or frontiers. They inscribe themselves within a 'hyper territory' in which they pack accumulation, connectivity and mobility, multiply connections and juggle with sociability scales and networks. They force their parents and elected representatives to rethink 'the institutional mechanic' and to make it more open and diverse.

Sentinels of the Future. Sometimes'influential outsiders', often out postsofsociety, teenagers have a lot to say about society and the world. The distorting mirrors and caricatures of the adult world, they are the transmitters of weak signals and also useful sentinels that we would be well advised to try and understand and to associate with the life of the city, rather than to judge or mimic. In this respect, listening more attentively to young people, as outposts of a society that will eventually imitate them, is a duty and a necessity. To understand them is also to identify the future possibilities, to avoid getting trapped in the dogmas of proximity and of urgency in terms of territory and of democracy. For them just as for us, there are a thousand and one ways of experiencing the spaces and times of hypermodern society and just as many new ways of getting involved in the life of the city, its networks, territories and places.

These observations point in the direction of a reflection on 'expanded territories' and on 'widened' citizens: in other words, on individuals capable of crossing networks, knowledge, competences and scales in order to be able to move beyond the here and now. Our society must not withdraw into idealised, but outdated, life territories. It has to adapt to the reality of our plural and poly-chronic life modes and cities, shift from a stock identity to a flow identity, move from the spot to the pathway, from permanence to situation without falling prisoner to the present while doing so. Teenagers invite us to join them on the paths of diversities and multitudes. Let's follow them!

Fig. 5 . 1

 51 Fig. 5.1 Life spaces, travel routes and modes of transport of a male student during the week (Sylvaine Schlienger, Luc Gwiazdzinski)