Kaïs Ïs Ammari
email: kais.ammari@fsm.rnu.tn

AND Denis Mercier
email: denis.mercier@univ-valenciennes.fr

Virginie Régnier
email: virginie.regnier@univ-valenciennes.fr

Virginie Régnier Spectral

Virginie R Égnier

SPECTRAL ANALYSIS OF THE SCHRÖDINGER OPERATOR ON BINARY TREE-SHAPED NETWORKS AND APPLICATIONS

Keywords: 1991 Mathematics Subject Classification. 35L05, 35M10, 35R02, 47A10, 93D15, 93D20 tree, dissipative Schrödinger operator, Riesz basis, boundary feedback stabilization, transfer function

whether they are published or not. The documents may come

First of all, we introduce some notation needed to formulate the problem under consideration, which is simply that of [START_REF] Dáger | Wave propagation, observation and control in 1-d flexible multi-structures[END_REF]. We refer to [START_REF] Dáger | Wave propagation, observation and control in 1-d flexible multi-structures[END_REF] for more details. To construct the binary tree T which will be considered in the following, we need some definitions (recall that a tree is a planar connected graph without paths). A multi-index ᾱ is a k-tuple (α 1 , . . . , α k ) if k lies in N -{0} and it is empty if k = 0. For a fixed integer n, we choose for I the set of multi-indices ᾱ, with length k in {0, 1, . . . , n}, such that, if k = 0, α j ∈ {1; 2}, for all j in {1, . . . , k}. Then the set of vertices V of the tree T is V := (∪ ᾱ∈I O ᾱ) ∪ {R} where R is an additional vertex which will be the root of the tree T . The edges are denoted by e ᾱ with ᾱ in I. Note that the number of edges is the cardinal of I and it holds:

|I| = N = 2 n+1 -1.
Define, for any non-empty multi-indices ᾱ = (α 1 , ..., α k ) and β = (β 1 , ..., β m ), the multi-index ᾱ• β := (α 1 , ..., α k , β 1 , ..., β m ) of length (k + m). Then, for a non-empty multi-index ᾱ = (α 1 , ..., α k ), the edge e ᾱ is chosen to have the extremities O ᾱ and O ᾱ′ with ᾱ = ᾱ′ • (α k ) and the edge e (corresponding to the case ᾱ = ∅) has the extremities R and O.

See Figure 1 for a representation in the case n = 2.

By the multiplicity of a vertex of T we mean the number of edges that branch out from that vertex. If the multiplicity is equal to one, the vertex is called exterior. Otherwise, it is said to be interior. We denote by Int the set of the interior vertices of the tree T and by Dir the set of the exterior vertices, except R, which has a particular status in our problem. Dir is chosen for Dirichlet (see the problem below). A dissipation law is imposed at the root R which explains why it is isolated from the other exterior vertices. Define I Int = {ᾱ; O ᾱ ∈ Int}, I Dir = {ᾱ; O ᾱ ∈ Dir} which are the sets of the indices of the interior and exterior vertices, except R, respectively. Note that the multiplicity of each interior point of the tree T is equal to 3 and that the integer (n + 1) represents the maximum level of the binary tree T . Furthermore, the length of the edge e ᾱ is equal to 1. Then, e ᾱ will be parametrized by its arc length by means of the functions π ᾱ, defined in [0, 1] such that π ᾱ(0) = O ᾱ and π ᾱ [START_REF] Abdallah | Stabilization and approximation of some distributed systems by either dissipative or indefinite sign damping[END_REF] is the other vertex of this edge. This choice seems unconventional but it is made for technical reasons.

In this paper, we study the dissipative Schrödinger operator under the tree-shaped network T introduced above. The case N ≥ 3 is the one we are interested in: it corresponds to n ≥ 1. The case N = 1 is well-known. See [START_REF] Lagnese | Modeling, Analysis of dynamic elastic multi-link structures[END_REF] and [START_REF] Dáger | Wave propagation, observation and control in 1-d flexible multi-structures[END_REF] concerning the model. More precisely, we consider the following initial and boundary value problem:

(1.1) ∂u ᾱ ∂t (x, t) + i ∂ 2 u ᾱ ∂x 2 (x, t) = 0, 0 < x < 1, t > 0, ᾱ ∈ I,

(1.2) i u(1, t) + ∂u ∂x (1, t) = 0, u ᾱ(0, t) = 0, ᾱ ∈ I Dir , t > 0, (1.3) u ᾱ•(β) (1, t) = u ᾱ(0, t), t > 0, β = 1, 2, ᾱ ∈ I Int , (1.4
)

2 β=1 ∂u ᾱ•(β) ∂x (1, t) = ∂u ᾱ ∂x (0, t), t > 0, ᾱ ∈ I Int ,
(1.5) u ᾱ(x, 0) = (u ᾱ) 0 (x), 0 < x < 1, ᾱ ∈ I, where u ᾱ : [0, 1] × (0, +∞) → R, ᾱ ∈ I, is the transverse displacement of the edge e ᾱ. These functions allow us to identify the network with its rest graph. In this sense, the vertices of T are called nodes and the edges are called branches.

Note that in the problem above, (1.1) is the Schrödinger equation imposed on all the branches of the tree, (1.2) concerns the root and the other exterior nodes (recall that u = u ᾱ with ᾱ = ∅ and that this empty multi-index is In the last few years various physical models of multi-link flexible structures consisting of finitely many interconnected flexible elements such as strings, beams, plates, shells have been of great interest. See the references by Ali Mehmeti, von Below and Nicaise in [START_REF] Mercier | Boundary controllability of a chain of serially connected Euler-Bernoulli beams with interior masses[END_REF] as well as [START_REF] Chen | Modeling, stabilization and control of serially connected beams[END_REF], [START_REF] Dáger | Wave propagation, observation and control in 1-d flexible multi-structures[END_REF], [START_REF] Lagnese | Modeling, Analysis of dynamic elastic multi-link structures[END_REF] and the references therein. The spectral analysis of such structures has some applications to control or stabilization problems (cf. [START_REF] Lagnese | Modeling, Analysis of dynamic elastic multi-link structures[END_REF]). For interconnected strings (corresponding to a second-order operator on each string), a lot of results have been obtained: the asymptotic behaviour of the eigenvalues (see the references by Ali Mehmeti, von Below and Nicaise in [START_REF] Mercier | Boundary controllability of a chain of serially connected Euler-Bernoulli beams with interior masses[END_REF] as well as [START_REF] Ali Mehmeti | Partial differential equations on multi-structures[END_REF]), the relationship between the eigenvalues and algebraic theory (cf. papers by von Below, Nicaise and [START_REF] Lagnese | Modeling, Analysis of dynamic elastic multi-link structures[END_REF]), qualitative properties of solutions (see papers by von Below cited in [START_REF] Mercier | Boundary controllability of a chain of serially connected Euler-Bernoulli beams with interior masses[END_REF] for example) etc... For interconnected beams (corresponding to a fourth-order operator on each beam), some results on the asymptotic behaviour of the eigenvalues and on the relationship between the eigenvalues and algebraic theory were obtained by Nicaise and Dekoninck with different kinds of connections using the method developed by von Below in [START_REF] Below | A characteristic equation associated to an eigenvalue problem on C 2 -networks[END_REF] to get the characteristic equation associated to the eigenvalues. Mercier and Régnier used the same method in [START_REF] Mercier | Spectrum of a network of Euler-Bernoulli beams[END_REF] to compute the spectrum for a hybrid system of N flexible beams connected by n vibrating point masses. This type of structure was studied by Castro and Zuazua in many papers (see [START_REF] Castro | Analyse spectrale et contrôle d'un systèheterme hybride composé de deux poutres connectées par une masse ponctuelle[END_REF] and the papers by the same authors cited in [START_REF] Mercier | Boundary controllability of a chain of serially connected Euler-Bernoulli beams with interior masses[END_REF] as well as one by Castro and Hansen also cited there). In another paper (see [START_REF] Mercier | Boundary controllability of a chain of serially connected Euler-Bernoulli beams with interior masses[END_REF]), Mercier and Régnier used the technique of exterior matrices due to W. H. Paulsen (presented for other purposes in [START_REF] Paulsen | The exterior matrix method for sequentially coupled fourth-order equations[END_REF]) which D. Mercier had already used in the same type of context in [START_REF] Mercier | Spectrum analysis of a serially connected Euler-Bernoulli beams problem[END_REF]. The aim of these papers was to establish controllability. Later on, they have investigated the same problem as in [START_REF] Chen | Modeling, stabilization and control of serially connected beams[END_REF]. In that paper, Chen and al. have established the exponential stability of the problem but with an assumption on the material constants. They seem to think that the exponential stability can not hold without this assumption. Mercier and Régnier prove, using another method (that of the exterior matrices -Chen and al. had used a moment method), that in fact, the exponential stability always holds.

In this paper a feedback stabilization problem for Schrödinger equations in networks is studied. See [START_REF] Ammari | Boundary feedback stabilization of a chain of serially connected strings[END_REF]- [START_REF] Ammari | Stabilization of generic trees of strings[END_REF], [START_REF] Lagnese | Modeling, Analysis of dynamic elastic multi-link structures[END_REF]. In [START_REF] Banica | Dispersion for the Schrödinger equation on networks[END_REF], Banica and Ignat consider the Schrödinger equation on a network formed by a tree with the last generation of edges formed by infinite strips. They prove dispersive estimates which are useful for solving the linear Schrödinger equation. Let us also cite [START_REF] Zhang | A New Approach for the Stability Analysis of Wave Networks[END_REF], a paper in which Zhang and Xu study the stability of wave networks. They give recursive expressions that can be used to establish the stability of any given tree-shaped network. The geometry of their problem is close to ours but we give a general result of stability on binary trees with the Schrödinger equation and not the wave equation.

This paper is organized as follows:

In Section 2, the proper functional setting for system (1.1)-(1.5) is given: in particular a dissipative operator is defined. The system is proved to be well-posed. A notion of energy is defined by (2.11) and the energy of the solution of the system is proved to be a non-increasing function of the variable t. In Section 3, the spectrum of the Schrödinger operator associated to the dissipative system (1.1)-(1.5) is studied. The families of eigenvalues and the dimension of the corresponding eigenspaces are given for the dissipative operator as well as for the associated conservative operator. The localization and the asymptotic behaviour of the large eigenvalues are also studied. All the properties of the spectrum developed in this section are useful for the applications. In Section 4, some of the eigenfunctions of the dissipative operator associated to system (1.1)- (1.5) are proved to form a Riesz basis of the space they span. The rewriting of the solution in this Riesz basis allows to prove, in Section 5, that the energy of the solution decreases exponentially to a non-vanishing value depending on the initial datum. The decay rate is explicitly given in Theorem 5.1. Section 6 is dedicated to the transfer function of the dissipative operator associated to system (1.1)-(1.5).

We study, in Section 7, the stabilization result for (7.65)-(7.70) (which is system (1.1)-(1.5) with another feedback law) by the frequency domain technique. The explicit decay rate of the energy of the solution is given.

Well-posedness of the system

In order to study system (1.1)-(1.5) we need a proper functional setting. We define the following space

H = ᾱ∈I L 2 (0, 1)
equipped with the inner product

(2.6) < u, ũ > H = ᾱ∈I 1 0 u ᾱ(x) ūᾱ (x) dx.
It is well-known that system (1.1)-(1.5) may be rewritten as the first order evolution equation

(2.7) u ′ = A d u, u(0) = u 0 ,
where the operator

A d : D(A d ) ⊂ H → H (the index d is for dissipative) is defined by A d u := (-i ∂ 2 x u ᾱ) ᾱ∈I , with D(A d ) := u ∈ ᾱ∈I H 2 (0, 1) : satisfies (2.8) to (2.10) hereafter , (2.8) i u(1) + du dx (1) = 0, u ᾱ(0) = 0, ᾱ ∈ I Dir , (2.9) u ᾱ•(β) (1) = u ᾱ(0), β = 1, 2,
(2.10)

2 β=1 du ᾱ•(β) dx (1) = du ᾱ dx (0), ᾱ ∈ I Int .
The natural energy E(t) of a solution u = (u ᾱ) ᾱ∈I of (1.1)-(1.5) is defined by:

(2.11)

E(t) = 1 2 ᾱ∈I 1 0 |u ᾱ(x, t)| 2 dx. Proposition 2.1. (i) For an initial datum u 0 ∈ H, there exists a unique solution u ∈ C([0, +∞), H) to problem (2.7). Moreover, if u 0 ∈ D(A d ), then u ∈ C([0, +∞), D(A d )) ∩ C 1 ([0, +∞), H).
(ii) The solution u of (1.1)-(1.5) with initial datum in D(A d ) satisfies the dissipation law:

(2.12)

E ′ (t) = -u(1, t) 2 ≤ 0,
(recall that u = u ᾱ with ᾱ = ∅ and that this empty multi-index is chosen for the edge containing the root R).

Therefore the energy is a non-increasing function of the time variable t.

Proof. (i) By Lumer-Phillips' theorem (see [START_REF] Pazy | Semigroups of linear operators and applications to partial differential equations[END_REF][START_REF] Tucsnak | Observation and control for operator semigroups[END_REF]), it suffices to show that A d is dissipative and maximal.

We first prove that A d is dissipative. Take u ∈ D(A d ). Then

A d u, u H = ᾱ∈I 1 0 -i ∂ 2 x u ᾱ(x)u ᾱ(x)dx.
By integration by parts and using the transmission and boundary conditions, it holds:

(2.13)

ℜ ( A d u, u H ) = -|u(1)| 2 ≤ 0.
This shows the dissipativeness of A d (recall that u(1) is the value of the solution at the root R).

Let us now prove that A d is maximal, i.e. that λI -A d is surjective for some λ > 0.

Let f ∈ H. We look for u ∈ D(A d ) solution of

(2.14) (λI -A d )u = f , or equivalently (2.15) λ u ᾱ + i ∂ 2 x u ᾱ = f ᾱ, ∀ ᾱ ∈ I.
Multiplying this identity by a test function φ, integrating in space and using integration by parts, it follows, since u ∈ D(A d ), (2.16)

ᾱ∈I 1 0 λu ᾱ(x)φ ᾱ(x) + i ∂ x u ᾱ(x)∂ x φ ᾱ(x) dx + u(1)φ(1) = ᾱ∈I 1 0 f ᾱ(x)φ ᾱ(x) dx.
This problem has a unique solution u ∈ V := u ∈ ᾱ∈I H 1 (0, 1) : u ᾱ(0) = 0, ᾱ ∈ I Dir , and satisfies (2.9) by Lax-Milgram's lemma, because the left-hand side of (2.16) is coercive on (2.16) and integrating by parts lead to:

V . If we consider φ ∈ ᾱ D(0, 1) ⊂ V , then u satisfies λu ᾱ + i ∂ 2 x u ᾱ = f ᾱ in D ′ (0, 1), ᾱ ∈ I. This directly implies that u ∈ V ∩ ᾱ∈I H 2 (0, 1). Coming back to
ᾱ∈I i ∂ x u ᾱ(1)φ ᾱ(1) -i ∂ x u ᾱ(0)φ ᾱ(0) + u(1)φ(1) = 0.
Consequently, by taking particular test functions φ, we obtain

i u(1) + du dx (1) = 0, 2 β=1 du ᾱ•(β) dx (1) = ∂u ᾱ ∂x (0), ᾱ ∈ I Int .
In summary we have found u ∈ D(A d ) satisfying (2.14), which finishes the proof of (i).

(ii) To prove (ii), it suffices to derive the energy (2.11) for regular solutions and to use system (1.1)-(1.5). The calculations are analogous to those of the proof of the dissipativeness of A d in (i), and then, are left to the reader.

Spectral analysis

The goal of this section is to look for the eigenvalues and eigenvectors of the dissipative operator A d as well as those of the associated conservative operator A 0 . To that end, the operator A ǫ is defined like A d in Section 2 except for equation (2.8) which is replaced by:

(3.17) iǫ u(1) + du dx (1) = 0, u ᾱ(0) = 0, ᾱ ∈ I Dir .

Thus A 0 and A d are A ǫ with ǫ = 0 and ǫ = 1 respectively.

The main result (which is proved at the end of the section) is the following one:

Theorem 3.1. (Spectra of A 0 and A d ) i) Let σ (0) be the spectrum of the conservative operator A 0 , then

(3.18) σ (0) = σ (0) 1 ∪ σ (0)
2 , where

σ (0) 1 = {i(kπ) 2 : k ∈ Z * } ∪ i kπ + π 2 2 : k ∈ Z ,
and, if n is even,

σ (0) 2 = i kπ + 1 2 arg(z (n) A,j ) 2 : j = 2, ..., n + 1, k ∈ Z if n is odd, σ (0)
2 = i kπ + 1 2 arg(z (n) A,j ) 2 : j = 1, ..., n + 1, k ∈ Z, n odd where z (n)
A,j , j = 1, ..., n + 1 is the family of the complex roots of the polynomial P A,n defined in Proposition 3.4.

ii) Let σ be the spectrum of the dissipative operator A d , then

(3.19) σ = σ 1 ∪ σ 2 ∪ σ2 ,
where

σ 1 = σ (0) 1 , σ2 = {(λ k ) k∈S : S is finite, ℜ(λ k ) < 0} and σ 2 = {i(ω j,k ) 2 : j = 1, ..., n + 1, k ∈ Z, |k| ≥ k 0 }, k 0 being an integer. Moreover ℜ(i(ω j,k ) 2 ) < 0, ∀i(ω j,k ) 2 ∈ σ 2 ,
and the following asymptotic behaviour holds:

(3.20) i(ω j,k ) 2 = i k 2 π 2 + kπ arg(z (n) A,j ) + (arg(z (n) A,j )) 2 4 + 2πγ j + o(1)
where γ j is a real negative number (its expression is given by (3.36)). The polynomial P A,n defined in Proposition 3.4 admits n + 1 distinct complex roots z (n)

A,j = 1, j = 1, ..., n + 1 with modulus equal to 1.

Note that when n is even, (-1) is a root of P A,n which is denoted by z (n)

A,1 (cf. Lemma 3.6). Since kπ + 1 2 arg(z

(n) A,1 ) = kπ + π
2 , when n is even, the index j starts from 2 in the definition of σ and T := 1 0 0 2 .

The complex λ = iω 2 (ω ∈ C * , ω = kπ, k ∈ Z and ω = (π/2) + kπ, k ∈ Z) is an eigenvalue of the operator A ǫ defined at the beginning of the section on the binary tree T with level (n + 1) (constructed in the introduction) if and only if (3.21) (iǫ 1)e M (ω) T . . . e M (ω) T e M (ω) T e M (ω) 0 1 = 0 with (n + 1) matrices e M (ω) in the product.

Proof. First, the vector

F ᾱ(x) := φ ᾱ(x) ∂ x φ ᾱ(x)
is introduced to reduce the order of the eigenvalue problem which reads: λ = iω 2 (ω ∈ C) is an eigenvalue of A ǫ with associated eigenvector φ ∈ D(A ǫ ) if and only if φ satisfies the transmission and boundary conditions (3.17), (2.9) and (2.10) of Section 2 and (EP ) : F ′ ᾱ(x) = M (ω)F ᾱ(x) on (0, 1), ∀ᾱ ∈ I. In the following, ω is supposed to be different from 0 (0 is not an eigenvalue, cf. the proof of Theorem 3.3). Thus F ᾱ(x) = e M (ω)x F ᾱ(0) where e M (ω)x = cos(ωx) sin(ωx) ω -ω sin(ωx) cos(ωx) .

For simplicity, the computations to establish the characteristic equation are first presented in the case I Dir = {(1, 1); (1, 2); (2, 1); (2, 2)} (n = 2, see Figure 1. The results will then be generalized to any tree defined as in the introduction.

The Dirichlet condition at the exterior vertices (except the root, see the second part of (3.17

) for ᾱ ∈ I Dir ) im- plies F ᾱ(0) = 0 ∂ x φ ᾱ(0) for ᾱ ∈ I Dir . Then F ᾱ(1) = e M (ω) F ᾱ(0) i.e. F ᾱ(1) = φ ′ ᾱ(0) sin(ω) ω cos(ω)
, for ᾱ ∈ I Dir and ω = 0. Now the continuity at the interior vertices O 1 and O 2 (condition (2.9)) implies:

(3.22) φ ′ j,1 (0) • sin(ω) ω = φ ′ j,2 (0) • sin(ω) ω for j = 1 and j = 2.
Either ω = kπ with k ∈ Z * (first family of eigenvalues which is studied in the proof of Theorem 3.3) or the following condition is imposed:

(3.23) φ ′ j,1 (0) = φ ′ j,2 (0) for j = 1 and j = 2.
Then the second transmission condition at the interior vertices O 1 and O 2 (condition (2.10)) implies, for j = 1 and j = 2:

F j (0) = φ ′ j,1 (0) sin(ω) ω 2 cos(ω)
. Once more, this vector is multiplied by e M (ω) and it follows from the continuity at the vertex O:

either ω = π 2 + kπ, k ∈ Z (second family of eigenvalues which is studied in the proof of Theorem 3.3) or (3.24) φ ′ 1,1 (0) = φ ′ 2,1 (0).
Using the diagonal matrix T , it can be written as:

(3.25) F (1) = φ ′ 1,1 (0)e M (ω) T e M (ω) T e M (ω) 0 1 . At last, for ω ∈ C * , ω = kπ, k ∈ Z and ω = (π/2) + kπ, k ∈ Z, the dissipation law (first part of condition (3.17))
imposed at the root R gives the characteristic equation:

(3.26) (iǫ 1)e M (ω) T e M (ω) T e M (ω) 0 1 = 0.
And for a general tree as described in the introduction, the characteristic equation is:

(3.27) (iǫ 1)e M (ω) T . . . e M (ω) T e M (ω) T e M (ω) 0 1 = 0.
with (n + 1) matrices e M (ω) in the product where (n + 1) is the maximum level of the binary tree T defined in the introduction.

Note that the cases ω = kπ, k ∈ Z * and ω = (π/2) + kπ, k ∈ Z are treated in next section where the dimension of the associated eigenspace is computed. For the other values of ω, the condition ∂ x φ ᾱ(0) = ∂ x φ γ (0) for any ᾱ and γ in I Dir is imposed. Thus the dimension of the corresponding eigenspace is one.

3.2.

The families of eigenvalues. This section is devoted to the characterization of the different types of eigenvalues for both the conservative and the dissipative operators defined at the beginning of this section. The geometric multiplicity of each eigenvalue is also computed. The operators A 0 and A d are defined in Section 3.1 on the binary tree T with level (n + 1) constructed in the introduction.

(1) The complex λ = iω 2 (ω ∈ C) is an eigenvalue of the operator A 0 if and only if

• either ω = kπ, k ∈ Z * and the dimension of the corresponding eigenspace is equal to:

2 n -1,
• or ω = (π/2) + kπ, k ∈ Z and the dimension of the corresponding eigenspace is equal to:

1 3 2 n + 2 3 if n is even and 1 3 (2 n -2) if n is odd,
• or ω = ((arg(z

(n) A,j )/2) + kπ, k ∈ Z where z (n) A,j (j = 1, . . . , n if n is odd, j = 2, . . . , n if n is even)
is the family of the roots of the polynomial P A,n defined in Proposition 3.4 below (if n is even, the first root z (n)

A,1 = -1 is excluded). The dimension of the eigenspace associated to each eigenvalue is one.

(2) The complex λ = iω 2 (ω ∈ C) is an eigenvalue of the operator A d if and only if

• either ω = kπ, k ∈ Z * and the dimension of the corresponding eigenspace is equal to: 2 n -1,

• or ω = (π/2) + kπ, k ∈ Z and the dimension of the corresponding eigenspace is equal to:

1 3 (2 n -1) if n is even and 1 3 (2 n -2) if n is odd, • or ω satisfies ω = kπ, ω = (π/2) + kπ, k ∈ Z and (3.28) P A,n (z) + P B,n (z) ω = 0.
where z = e 2iω and the polynomials P A,n and P B,n are defined in Proposition 3.4 below. The localization of the corresponding eigenvalues is studied in Proposition 3.1. The dimension of the eigenspace associated to each eigenvalue is one.

Note that the first two families of eigenvalues of A ǫ lie on the imaginary axis. The third one also lies on the imaginary axis for the conservative operator. The third family of eigenvalues of the dissipative operator lies on the half-plane of complex numbers with a negative real part.

Proof. Let us begin by proving that λ = 0 is not an eigenvalue. If 0 is an eigenvalue associated to the eigenvector u = (u ᾱ) ᾱ∈I , then

0 = A d u, u H = ᾱ∈I 1 0 -i ∂ 2 x u ᾱ(x)u ᾱ(x)dx.
By integration by parts and using the transmission and boundary conditions, it holds

(3.29) 0 = -i|u(1)| 2 - ᾱ∈I Dir ∂ x u ᾱ(0)u ᾱ(0) - ᾱ∈I 1 0 |∂ x u ᾱ(x)| 2 dx.
Since u ᾱ(0) = 0 for any ᾱ ∈ I Dir , u(1) = 0 and ∂ x u ᾱ ≡ 0 for any ᾱ ∈ I. It follows u ᾱ ≡ 0 for any ᾱ ∈ I which is a contradiction with the fact that 0 is an eigenvalue associated to the eigenvector u.

The characteristic equation is established in the latest section and studied in Section 3.3. We are interested only in the dimension properties here.

(1) First case ω = kπ, k ∈ Z * :

We use here the notation introduced in Proposition 3.2 and its proof.

The matrix e M (ω) is (-1) k I where I is for the 2 × 2 identity matrix. The "eigenvector" F ᾱ for ᾱ in I Dir is:

F ᾱ(x) := 0 f ᾱ = f ᾱ 0 1 with f ᾱ = ∂ x φ ᾱ(0).
Recall that I Dir contains 2 n elements. Then condition (2.9)

is satisfied at all the interior nodes since the multiplication by (-1) k I does not change the first component of F ᾱ which is always zero. The other transmission condition (2.10) at the interior nodes is translated into a sum of the second components. At last the dissipation law at the root leads to one equation: (-1) k(n+1) ᾱ∈I Dir f ᾱ = 0 hence the announced dimension.

(2) Second case ω = (π/2) + kπ, k ∈ Z:

There are 2 n degrees of freedom as in the first case (cardinal of I Dir ) but the number of constraints increases.

The "eigenvector" F ᾱ for ᾱ in I Dir is still:

F ᾱ(0) := f ᾱ 0 1 with f ᾱ = ∂ x φ ᾱ(0). But the matrix e M (ω) is not diagonal any more. It is: e M (ω) := (-1) k 0 ω -1 -ω 0 .
Thus, for ᾱ in I Dir (i.e. for any ᾱ ∈ I such that

| ᾱ| = n), F ᾱ(1) = e M (ω) F ᾱ(0) = (-1) k ω -1 f ᾱ 1 0 .
Step n -1: The continuity at the interior nodes O ᾱ where the length | ᾱ| is equal to n -1 implies the 2 n-1 independent equations:

f ᾱ•(1) = f ᾱ•(2) for any ᾱ ∈ I such that | ᾱ| = n -1.
Then the value

f ᾱ•(1) is renamed f ᾱ and F ᾱ(1) = e M (ω) F ᾱ(0) = -f ᾱ 0 1 .
Step n -2: At the next 2 n-2 interior nodes, no continuity condition is needed and the other transmission condition is translated into a sum at each node:

F ᾱ(0) = f ᾱ 0 1 , where -(f ᾱ•(1) +f ᾱ•(2) ) is renamed f ᾱ and | ᾱ| = n-2. Then F ᾱ(1) = (-1) k 1 ω f ᾱ 1 0 .
The process continues. Two cases are to be envisaged: (a) Case of an even n. The number of equations is:

2 1 + 2 3 + . . . + 2 n-1 = 2(1 + 2 2 + . . . + 2 n-2 ) = 2(4 0 + 4 1 + . . . + 4 n/2-1 ) = 2 4 n/2 -1 3 = 2 3 (2 n -1). At last, for ᾱ ∈ I, such that | ᾱ| = 0, F (0) = f 0 1 where -(f (1) + f (2) ) is renamed f and F (1) = (-1) k 1 ω f 1 0
. This means, by definition, that φ(1) = -f (-1) k ω and ∂ x φ(1) = 0 where φ ᾱ is the eigenfunction.

For the conservative operator A 0 , the dissipation law (3.17) is then satisfied since ǫ = 0. Thus the dimension of the corresponding eigenspace is:

2 n - 2 3 (2 n -1) = 1 3 2 n + 2 3 .
For the dispersive operator A d (ǫ = 1), the dissipation law is satisfied if f = 0. Thus the dimension of the corresponding eigenspace is:

2 n -1 + 2 3 (2 n -1) = 1 3 2 n - 1 3 .
(b) Case of an odd n. The number of equations is:

2 0 + 2 2 + . . . + 2 n-1 = 4 (n-1)/2+1 -1 3 = 2 n+1 -1 3 . At last, for ᾱ ∈ I, such that | ᾱ| = 0, F (0) = (-1) k 1 ω f 1 0 where f (1) = f (2) is renamed f and F (1) = -f 0 1
. This means, by definition, that φ(1) = 0 and ∂ x φ(1) = -f .

For both operators A 0 and A d , the dissipation law is satisfied if f = 0. Thus the dimension of the corresponding eigenspace is:

2 n -1 + 2 n+1 -1 3 = 1 3 2 n - 2 3 .
Note that the constraints are always independent from one another. This can be proved by iteration on p for the two separate cases n = 2p and n = 2p + 1.

(3) Third case: it is treated in next section. Cf. the end of the proof of Proposition 3.2 for the dimension of the corresponding eigenspace.

3.3.

Iterative study of the characteristic equation. where z = e 2iω and the polynomials P A,n and P B,n are defined by:

• R • O • O1 • O2 • O1 • O2 • O1,1 • O1,2 • O2,2 • O2,1
(3.31) P A,m+1 (z) = 2(z + 1) P A,m (z) + (z -1) P B,m (z), ∀m ∈ N, (3.32) P B,m+1 (z) = 2(z -1) P A,m (z) + (z + 1) P B,m (y), ∀m ∈ N, (3.33) P A,0 (z) = z + 1, P B,0 (z) = z -1.
Proof. The iterative procedure follows from the rewriting of the product e M (ω) T with z = e 2iω . Indeed, if s = e iω , using the classical trigonometric formulae leads to:

e M (ω) T = 1 2     s + 1 s - 2i ω s - 1 s iω s - 1 s 2 s + 1 s     and e M (ω) 0 1 = 1 2     - i ω s - 1 s s + 1 s     .
Since z = s 2 , it is also:

e M (ω) T = 1 2s z + 1 - 2i ω (z -1) iω(z -1) 2(z + 1) and e M (ω) 0 1 = 1 2s - i ω (z -1) z + 1
Now, for m = 0, the characteristic equation reads:

(iǫ 1)e M (ω) 0 1 = 0 or (z + 1) + ǫ ω (z -1) = 0,
which is the announced result. By iteration, the rest follows.

The rewriting of the characteristic equation as (3.30) gives the expression of the eigenvalues of both operators as well as their asymptotic behaviour: the conservative one, A 0 and the dissipative one, A d , using Rouché's Theorem. Hence Theorem 3.1 announced at the beginning of Section 3 which is proved in the following.

Proof. i) Let ω be a solution of (3. By iteration the characteristic equation (3.27) is: 1)) = 0 when y tends to -∞. This is a contradiction with the behaviour of the exponential function. So we have proved that ℑ(ω) is bounded from below.

e -(n+1)y 2 n+1 (3 n • e -i(n+1)x + o(
ii) First asymptotic behaviour of the solution of (3.30).

Let us define the complex-valued functions f and g, respectively by: f (ω) = P A (e 2iω ) and g(ω) = P B (e 2iω ) ω . From the previous step, the solutions ω of (3.30) such that |ω| → ∞ satisfy lim |ω|→∞ g(ω) = 0. Moreover the large roots of

f are w 0 j,k = kπ + 1 2 arg(z (n)
A,j ), j = 1, ..., n, k ∈ Z, |k| → ∞. Thus, we can apply Rouché's Theorem to the functions f and g as follows: we fix j and k large enough and we consider the disk Γ k with center ω 0 j,k and radius r k = 1 |k| .

Now we prove that there exist k 1 ∈ N and c 1 > 0 such that for all |k| ≥ k 1 then

(3.34) ∀ω ∈ ∂Γ k , |f (ω| > c 1 r k .
Indeed, for such a ω it holds

f (w) = P A,n (e 2iw 0 j,k +r k e iθ ), θ ∈ [0, 2π]. But e 2iw 0 j,k +r k e iθ = z (n) A,j e r k e iθ = z (n) A,j + z (n) A,j r k e iθ + O( 1 |k|
). Consequently,

f (w) = P A,n (z (n) A,j ) + (P A,n ) ′ (z (n) A,j )r k e iθ + O( 1 |k| ),
and we get (3.34) since P A,n (z

(n) A,j ) = 0 and (P A,n ) ′ (z (n)
A,j ) = 0 (see Lemma 3.6). Finally, f and f + g have the same number of zeroes on Γ, where each zero is counted as many times as its multiplicity, since there exist c 2 > 0 and

k 0 ∈ N, k 0 ≥ k 1 such that if |k| ≥ k 0 then |g(ω)| ≤ c 2 |k| ≤ c 1 r k < |f (ω)|, ∀ω ∈ Γ k .
Hence we deduce the following asymptotic behaviour of the roots of (3.30):

ω j,k = kπ + 1 2 arg(z (n) A,j ) + o(1), j = 1, ..., n, k ∈ Z, |k| ≥ k 0 .
iii) Second asymptotic behaviour of the solution of (3.30).

From the previous step we can write for a fixed j = 1, ..., n :

ω j,k = kπ + 1 2 arg(z (n) A,j ) + ǫ k , lim |k|→∞ ǫ k = 0.
Thus (3.30) gives 0 = P A,n (e 2ikπ+i arg(z (n) A,j )+2iǫ k ) + P B,n (e 2ikπ+i arg(z (n) A,j )+2iǫ k ) kπ + 1 2 arg(z

(n) A,j ) + ǫ k = P A,n (z (n) A,j + 2iz (n) A,j ǫ k + o(ǫ k )) + P B,n (z (n) A,j + o(1)) kπ + o 1 k = 2iz (n) A,j ǫ k (P A,n ) ′ (z (n) A,j ) + o(ǫ k ) + P B,n (z (n) A,j ) kπ + o 1 k , which leads to (3.35) ω j,k = kπ + 1 2 arg(z (n) A,j ) -i γ j k + o 1 k , where (3.36) γ j = - P B,n (z (n) A,j ) 2πz (n) A,j (P A,n ) ′ (z (n) A,j )
. Now, from Property (v) of the following Lemma, γ j is real and non-vanishing. Note that (3.35) implies

i(ω j,k ) 2 = i k 2 π 2 + kπ arg(z (n) A,j ) + (arg(z (n) A,j )) 2 4 + 2πγ j + o(1).
Thus γ j is negative since the problem we consider is dissipative. The proof is complete. or if λ ∈ σ2 ∪ σ 2 (see Theorem 3.1 for the notation) then the geometrical multiplicity of λ is one.

Obviously, if λ ∈ σ (0)
2 , then its algebraic multiplicity is also one since A 0 is skew-adjoint. The part ii) of the previous proof shows that the large eigenvalues of σ 2 have an algebraic multiplicity equal to one. Moreover, without loss of generality, we can assume that all the eigenvalues of σ 2 are algebraically simple (see the definition of σ 2 in Theorem 3.1: the integer k 0 may be chosen large enough in order that σ 2 does not contain any eigenvalue with an algebraic multiplicity different from one).

On the other hand, the algebraic multiplicity of each eigenvalue of the finite set σ2 remains an open question.

For convenience, let us recall that if λ ∈ σ2 has an algebraic multiplicity µ λ ≥ 2 and since the geometrical multiplicity is one then there exists a Jordan chain φ 0 , φ 1 , ..., φ µ λ -1

(λI -A d )φ 0 = 0, (λI -A d )φ j = φ j-1 , j = 1, ..., µ λ -1, {φ 0 , φ 1 , ..., φ µ λ -1 } providing a basis of N [(λI -A d ) µ λ ].
Later on, we will refer to such a family as the set of generalized eigenfunctions associated to λ. Lemma 3.6. (Properties of the polynomials P A and P B ) The polynomials P A,n and P B,n defined in the latter proposition have the following properties:

(i) deg P A,n = deg P B,n = n + 1.
(ii) P A,n admits n + 1 distinct complex roots z (n) A,j = 1, j = 1, ..., n + 1 with modulus equal to 1.

(iii) P A,n (-1) = 0 if n is even (this root is chosen to be z (n) A,1 in the main Theorem).

(iv) P B,n (z

(n) A,j ) = 0, j = 1, ..., n + 1. (v) The quotient P B,n (z (n) A,j ) z (n) A,j P ′ A,n (z (n) A,j )
is a real number different from 0, for j = 1, ..., n + 1.

Proof. First 1 is not a root of P A,n . The proof is done by descending induction. Using (3.31), it is clear that if 1 is a root of P A,n+1 , it is also a root of P A,n . But 1 is not a root of P A,0 . Hence the result.

For the other results, let us construct other sequences of polynomials which are easier to study. The first step is to use the transformation ϕ defined on (iR) by ϕ(u) = u + 1 u -1 . Then we define the following two sequences:

q A,n (u) = P A,n (ϕ(u)) and q B,n (u) = P B,n (ϕ(u)).

At last the sequences of polynomials r A,n and r B,n are given by:

(3.37)

       q A,n (u) = 2 u -1 n+1 r A,n (u), q B,n (u) = 2 u -1 n+1 r B,n (u).
Calculations left to the reader lead to:

(3.38)    r A,0 (u) = u, r B,0 (u) = 1, r A,n+1 (u) = 2ur A,n (u) + r B,n (u), r B,n+1 (u) = 2r A,n (u) + ur B,n (u).
Now define the following two sequences of polynomials:

(3.39) Q A,n (y) = (-i) n+1 r A,n (iy), Q B,n (y) = (-i) n r B,n (iy).
They satisfy the iteration laws:

(3.40)    Q A,0 (y) = y, Q B,0 (y) = 1, Q A,n+1 (y) = 2yQ A,n (y) -Q B,n (y), Q B,n+1 (y) = 2Q A,n (y) + yQ B,n (y).
From Lemma 3.7 follow Properties (i), (ii) and (iv). Property (iii) comes from Property (i.2) of Lemma 3.7 above: n even implies Q A,n is odd. Thus Q A,n (0) = 0 which is equivalent to P A,n (-1) = 0. As for (v), it requires the rewriting of the quotient in terms of

Q A and Q B . Introduce u (n) j := ϕ(z (n) A,j ), then P B,n (z (n) A,j ) = q B,n (u (n) j ) since the reciprocal function of ϕ is ϕ itself. And (3.41) P ′ A,n (z) = d dz (q A,n )(ϕ(z)) = ϕ ′ (z)(q A,n ) ′ (ϕ(z)) = - 2 (z -1) 2 (q A,n ) ′ (ϕ(z)) = - 2 (ϕ(u) -1) 2 (q A,n ) ′ (u) = - 1 2 (u -1) 2 (q A,n ) ′ (u).
The quotient is:

(3.42) P B,n (z (n) A,j ) z (n) A,j P ′ A,n (z (n) A,j ) = q B,n (u (n) j ) (-1/2)ϕ(u (n) j )(u n j -1) 2 (q A,n ) ′ (u (n) j ) = - 2
((u (n) j ) 2 -1)
q B,n (u

(n) j ) (q A,n ) ′ (u (n) j )
. Now, since u (n) j lies in (iR), (u (n) j ) 2 -1 is real and non-positive. Thus the first factor is real and non-negative. It remains to be seen whether the other factor is well defined, real and non-vanishing. To this end, it is rewritten in terms of the other sequences of polynomials: Q A,n and Q B,n .

Since (q A,n ) ′ (u) = 2 n+1 (u -1) n+1 - 1 (n + 1)(u -1)
r A,n (u) + (r A,n ) ′ (u) and since r A,n (u

(n) j ) = 0 (by definition of u (n) j ), it holds: (3.43) q B,n (u (n) j ) (q A,n ) ′ (u (n) j ) = r B,n (u (n) j ) (r A,n ) ′ (u (n) j ) = Q B,n (y (n) j ) (Q A,n ) ′ (y (n) j )
, where u

(n) j = iy (n) j .
Thus the quotient (3.42) is real since y (n) j is real. It is well defined and non-vanishing due to Lemma 3.7 below: the multiplicity of the roots of Q A,n is one and both polynomials Q A,n and Q B,n have no common root. This ends the proof.

Lemma 3.7. (Properties of the polynomials Q A and Q B ) Let {Q A,n } n∈N and {Q B,n } n∈N be two sequence of polynomials defined for all y ∈ R as follows:

(3.44) Q A,n+1 (y) = 2 y Q A,n (y) -Q B,n (y), ∀n ∈ N, (3.45) Q B,n+1 (y) = 2 Q A,n (y) + y Q B,n (y), ∀n ∈ N, (3.46) Q A,0 (y) = y, Q B,0 (y) = 1
Then the following properties hold:

(i) (i.1) deg Q A,n = n + 1 and deg Q B,n = n. (i.
2) If n is even (resp. odd) then Q A,n is odd (resp. even) and Q B,n is even (resp. odd).

(i.3) lim y→+∞ Q A,n (y) = lim y→+∞ Q B,n (y) = +∞.
(ii) Q A,n admits n + 1 distinct real roots y A,j , j = 1, ..., n + 1.

(iii) Q B,n admits n distinct real roots y B,j , j = 1, ..., n.

(iv) The roots of Q A,n and Q B,n are ordered alternately, i.e;

y (n) A,1 < y (n) B,n,1 < y (n) A,2 < y (n) B,2 < ... < y (n) B,n < y (n) A,n+1 .
Proof. (i) is easily checked by iteration. We will prove (ii), (iii) (iv) by iteration. For convenience we start the iteration at n = 1, since n = 0 is a particular case.

For n = 1, Q A,1 = 2y 2 -1 and Q B,1 (y) = 3y so the basis hypothesis is satisfied.

Let n ≥ 1, be fixed and assume that we have the inductive hypothesis, i.e Q A,n and Q B,n satisfy, (ii),(iii), (iv).

From (3.44) and (iv) we see that the sign of Q A,n+1 changes at each root of Q A,n and we deduce that Q A,n+1 has at least n distinct real roots y (n+1)

A,j , j = 2, ..., n + 1 such that

y (n) A,1 < y (n+1) A,2 < y (n) A,2 < y (n+1) A,3 < ... < y (n+1) A,n+1 < y (n) A,n+1 .
Now from (i.3) and (iv) we have Q A,n+1 (y

(n) A,n+1 ) = -Q B,n (y (n)
A,n+1 ) < 0. Therefore again from (i.3) we see that Q A,n+1 admits a supplementary root y (n+1) A,n+2 greater than y (n) A,n+1 and by symmetry Q A,n+1 admits also another root y (n+1) A,1 smaller than y (n) A,1 . At this step we have proved that Q A,n+1 has exactly n + 2 distinct real roots alternately with the roots of Q A,n , i.e (3.47) y

(n+1) A,1 < y (n) A,1 < y (n+1) A,2 < y (n) A,2 < y (n+1) A,3 < ... < y (n+1) A,n+1 < y (n) A,n+1 < y (n+1)
A,n+2 .

Now, for any root y (n+1)

A,j of Q A,n+1 , j ∈ {1, ..., n + 2} we have from (3.44)

0 = 2 y (n+1) A,j Q A,n (y (n+1) A,j ) -Q B,n (y (n+1)
A,j ), therefore from (3.45)

Q B,n+1 (y (n+1) A,j ) = 2 1 + (y (n+1) A,j ) 2 Q A,n (y (n+1)
A,j ). From (3.47) we see that the sign of Q A,n changes at each root y (n+1) A,j of Q A,n+1 , then the previous identity shows that the same fact holds also for Q B,n+1 . Consequently, between two consecutive roots y (n+1) A,j and y

(n+1) A,j+1 of Q A,n+1
, there is a root of Q B,n+1 . Finally the inductive hypothesis is true for n + 1. [START_REF] Ammari | Boundary feedback stabilization of a chain of serially connected strings[END_REF] (y) = 16y 5 -49y 3 + 16y.

Q A,3 Q B,3 Q A,4 Figure 3. Q A,3 (y) = 8y 4 -17y 2 + 2, Q B,3 (y) = 15y 3 -12y, Q A,

Riesz basis

In this section, it is proved that the generalized eigenfunctions of the dissipative operator A d associated to the eigenvalues in σ 2 ∪ σ2 (introduced in Section 2 and Theorem 3.1 for the spectrum) form a Riesz basis of the subspace of H which they span (denoted by H 2 in next section). To this end, we use Theorem 1.2.10 of [START_REF] Abdallah | Stabilization and approximation of some distributed systems by either dissipative or indefinite sign damping[END_REF] which is a rewriting of Guo's version of Bari Theorem with another proof (see [START_REF] Guo | Riesz basis approach to the stabilization of a flexible beam with a tip mass[END_REF]). The resolvent of the conservative operator A 0 restricted to H 2 is compact since the domain of A 0 is compactly embedded in H. Thus, it is enough to show that the eigenfunctions of A 0 associated to the eigenvalues in σ (0) 2 and those of the dissipative operator A d associated to the eigenvalues in σ 2 ∪ σ2 are quadratically close to one another, except from a finite number of eigenfunctions.

The parity of n plays a role in the proof: if n is even, one eigenfunction has a different form. It is, for any fixed value of k in Z, the eigenfunction ϕ 0 (ω

0 1,k , •). It is associated to ω 0 1,k = kπ + π 2 (i(ω 0 1,k ) 2 is an eigenvalue in σ (0) 1
and not in σ

(0)
2 ) and this function has the same form as the eigenfunctions associated to the eigenvalues of σ

(n) A,j ) which is such that i(ω 0 ) 2 ∈ σ (0) 2
(except from the case n = 2 and

j = 1: i(ω 0 1,k ) 2 is an eigenvalue in σ (0)
1 ). Denote by ω := ω j,k the value which is such that i(ω j,k ) 2 ∈ σ 2 ∪ σ2 . The indices j and k are dropped for simplicity since they are fixed here. Denote by ϕ 0 (ω 0 , •) (resp. ϕ(ω, •)) the eigenfunction of A 0 (resp. A d ) associated to the eigenvalue i(ω 0 ) 2 (resp. iω 2 ).

For an odd n and any i = 1, . . . , n, there exists an integer k 0 such that, for any j = 1, . . . , n:

|k|>k0 ϕ i (ω j,k , •) -ϕ 0 i (ω 0 j,k , •) 2 2 < ∞.
The index i comes from an indexation based on the level of the vertices of the tree which is read from the leaves to the root here and not the other way round as before (see the proof ).

For an even n and any i = 1, . . . , n, there exists an integer k 0 such that, for any j = 2, . . . , n:

|k|>k0 ϕ i (ω j,k , •) -ϕ 0 i (ω 0 j,k , •) 2 2 < ∞.
For an even n and any ᾱ ∈ I, there exists an integer k 0 such that:

|k|>k0 ϕ n-| ᾱ|+1 (ω 1,k , •) -ϕ 0 ᾱ(ω 0 1,k , •) 2 2 < ∞.
For an even n, the eigenfunction ϕ

0 (ω 0 1,k , •) associated to ω 0 1,k = kπ+ π 2 in σ (0)
1 has the same form as the eigenfunctions associated to the eigenvalues of σ (0) 1 (cf. Proof of Theorem 3.3 and the proof of this Theorem). The index is ᾱ as in the preceding sections.

Proof. For both operators, the "eigenvector" F ᾱ for ᾱ in I Dir is: F ᾱ(0) := f 0 1 with f = ∂ x φ ᾱ(0) for any ᾱ ∈ I Dir (cf. the beginning of the proof of Proposition 3.2 for the definition of F ᾱ and the end for its form in this case). Let us rename F ᾱ(0) the vector ω(1/f ) × F ᾱ(0) which is denoted by F 0 , for simplicity.

For ᾱ in I Dir (i.e. for any ᾱ ∈ I such that | ᾱ| = n), F ᾱ(x) = e M (ω)x F 0 which can be denoted by F 1 (x) since it does not depend on ᾱ. Likewise F 0 1 (x) := e M (ω 0 )x F 0 . Then F 2 (x) = e M (ω)x T F 1 (1) with F 2 (x) := F ᾱ(x) for any ᾱ ∈ I such that | ᾱ| = n -1 and T defined in Proposition 3.2. Idem for F 0 2 (x) with ω 0 instead of ω. And so on... The first component of F i (x) (resp. F 0 i (x)) gives the expression of the eigenfunction ψ ᾱ(x) of the dissipative operator A d on the adequate branch (resp. φ ᾱ(x), eigenfunction of the conservative operator A 0 on the appropriate branch) with the new indexation. Let call them respectively ϕ i (x) and ϕ 0 i (x).

Since e M (ω)x = cos(ωx) sin(ωx) ω -ω sin(ωx) cos(ωx) , it holds:

(4.48) ϕ i (ω, x) = cos(ωx)q i (ω) + sin(ωx) ω h i (ω) (4.49) ϕ 0 i (ω 0 , x) = cos(ω 0 x)q i (ω 0 ) + sin(ω 0 x) ω 0 h i (ω 0 )
and the construction of ϕ i has been done in such a way that the sequences q i and h i are defined iteratively by: (4.50) q i+1 (ω) = cos(ω)q i (ω) + sin(ω)

ω h i (ω), ∀i ∈ N, (4.51) h i+1 (ω) = -2ω sin(ω)q i (ω) + 2 cos(ω)h i (ω), ∀i ∈ N, (4.52) q 1 (ω) = 0, h 1 (ω) = ω.
Denoting by

Q i (ω) := q i (ω) h i (ω) ω
, equations (4.50), (4.51) and (4.52) are equivalent to:

(4.53) Q i+1 (ω) = T R(ω)Q i (ω), ∀i ∈ N, (4.54) Q 1 (ω) = 0 1
with T defined as in Proposition 3.2 and R(ω) the rotation matrix: R(ω) := cos(ω) sin(ω) sin(ω) cos(ω) .

Denote by Q 0 i (ω) := Q i (ω 0 ). Using Lemma 4.2 below ends the proof except for the particular case n even and j = 1. Indeed, with the notation introduced in the Theorem

ϕ i (ω j,k , •) -ϕ 0 i (ω 0 j,k , •) 2 ≤ cos(ω•)(q i (ω) -q i (ω 0 )) 2 + (cos(ω•) -cos(ω 0 •))q i (ω 0 ) 2 + sin(ω•)(h i (ω)/ω -h i (ω 0 )/ω 0 ) 2 + h i (ω 0 )/ω 0 )(sin(ω•) -sin(ω 0 •) 2 .
Note that both the norms of ϕ i (ω j,k , •) and ϕ 0 i (ω 0 j,k , •) in H are bounded from above and below by a constant number independent of k. Now, when n is even, the dimension of the eigenspace for the conservative operator is different from that of the eigenspace for the dispersive operator. Let us construct an eigenfunction for A 0 which is not an eigenfunction for A d . We start as in the beginning of this proof. The "eigenvector" F 0 ᾱ for ᾱ in I Dir is:

F 0 ᾱ(0) := f ᾱ 0 1 with f ᾱ = ∂ x φ ᾱ(0).
Let us rename F 0 ᾱ(0) the vector ω 0 × F ᾱ(0). Thus, for any ᾱ ∈ I Dir , F 0 ᾱ(x) = e M (ω 0 )x f ᾱ 0 ω 0 i.e.

(4.55)

ϕ 0 ᾱ(ω 0 , x) = h ᾱ(ω 0 ) ω 0 sin(ω 0 x) where h ᾱ(ω 0 ) ω 0 = 1, if | ᾱ| = n.
Using the transmission conditions and denoting by q ᾱ and h ᾱ the new resulting coefficients as we have done in the proof of Theorem 3.3 lead to:

ϕ 0 ᾱ(ω 0 , x) = q ᾱ(ω 0 ) cos(ω 0 x) + h ᾱ(ω 0 ) ω 0 sin(ω 0 x)
with q ᾱ(ω 0 ) = 0 when | ᾱ| is even and h ᾱ(ω 0 ) = 0 when | ᾱ| is odd. Thus the particular case n even and j = 1 is treated as soon as we have proved Lemma 4.3 below.

Lemma 4.2. Let A and B be real numbers. The notation A B means the existence of a positive constant C, which is independent of A and B such that A ≤ CB. Then it holds:

(1)

|q i (ω)-q i (ω 0 )|, |h i (ω)/ω-h i (ω 0 )/ω 0 |, cos(ω•)-cos(ω 0 •) 2
and sin(ω•)-sin(ω 0 •) 2 have the same asymptotic behaviour when k tends to infinity:

|q i (ω) -q i (ω 0 )| 1 k
(idem for the other expressions).

(2) |q i (ω 0 )| and |h i (ω 0 )/ω 0 | have the same asymptotic behaviour when k tends to infinity:

|q i (ω 0 )| 1 (idem for the second expression). (3) |ϕ 0 n+1 (ω 0 , 1)| 1. Proof. It is equivalent to prove that |Q 0 i | 1 and |Q i -Q 0 i | 1 k
where Q i and Q 0 i have been introduced in the latest proof (all these expressions depend on ω that we drop for simplicity). The proof is done by induction.

• Base case: Since |Q 1 -Q 0 1 | = 0 and since |Q 0 1 | does not depend on ω (and thus on k), both assertions hold for i = 1.

• Inductive step: Suppose the statement holds for some natural number i, then for i + 1:

|Q 0 i+1 | = |T R 0 Q 0 i | 1 since T does not depend on k and the terms of R 0 := R(ω 0 ) are bounded with respect to k. Now |Q i+1 -Q 0 i+1 | = |T R(ω)Q i -T R(ω 0 )Q 0 i | = |T (R(ω) -R(ω 0 ))Q i + T R(ω 0 )(Q i -Q 0 i )|. Since |Q i | 1, |R(ω 0 )| 1 and |Q i -Q 0 i | 1 k , it remains to prove: |R(ω) -R(ω 0 )| 1 k .
Recall the dependence of ω with respect to k:

(4.56) ω := ω j,k = kπ + 1 2 arg(z (n) A,j ) -i γ j k + o 1 k = ω 0 -i γ j k + o 1 k .
Using the classical trigonometric difference identities for the sine and cosine functions, it holds, for any x ∈ [0; 1]:

cos(ω•) -cos(ω 0 •) 2 1 k and sin(ω•) -sin(ω 0 •) 2 1 k .
Hence the result.

Lemma 4.3. Suppose that n is even and choose the particular value

ω 0 = ω 0 1,k = kπ + π 2 .
Then, with the notation of Lemma 4.2:

(1) |q i (ω)| for an odd i, |h i (ω)/ω| for an even i, |h i (ω)/ωh ᾱ(ω 0 )/ω 0 | for an odd i and | ᾱ| = ni + 1 and |q i (ω 0 )q ᾱ(ω 0 )| for an even i and | ᾱ| = ni + 1, have the same asymptotic behaviour when k tends to infinity:

|q i (ω)| 1 k
(idem for the other expressions).

(2) |q i (ω)| for an even i and |h ᾱ(ω 0 )/ω 0 | for an odd | ᾱ| have the same asymptotic behaviour when k tends to infinity: |q i (ω)| 1 (idem for the second expression).

Proof.

(1) First the fact that |q i (ω)| for an odd i and |h i (ω)/ω| for an even i are both bounded from above by a constant times (1/k) follows from Lemma 4.2 and q i (ω 0 ) = 0 for an odd i and h i (ω 0 )/ω 0 = 0 for an even i and ω 0 = kπ + π 2 (the latest property is proved by induction, using cos(ω 0 ) = 0). Now, to prove that |h i (ω)/ωh ᾱ(ω 0 )/ω 0 | (1/k) for an odd i and |q i (ω 0 )q ᾱ(ω 0 )| (1/k) for an even i (where | ᾱ| = ni + 1), we proceed by induction on i. The base case is i = 1 for h and i = 2 for q. Both differences are equal to |1f ᾱ|.

It is enough to choose the f ᾱ's such that |1-f ᾱ| (1/k), for any ᾱ, such that | ᾱ| = n. Indeed the construction procedure explained in the proof of Theorem 4.1 for an even n guarantees that it is sufficient to get the desired estimate.

To explicit this iterative procedure, let us detail the example n = 4: there are 6 independent eigenfunctions (cf. Theorem 3.3 for the dimension). Choose

f 1,1,1 , f 1,1,2 , f 1,2,1 , f 2,1,1 , f 2,1,2 and f 2,2,1 all satisfying |1 -f ᾱ| (1/k), then if | ᾱ| = 4
, there exists β and j in {1; 2} such that | β| = 3 and ᾱ = β • (j). Then choose

f ᾱ := f β and f 1,2,2 := f 1,1,1 + f 1,1,2 -f 1,2,1 and f 2,2,2 := f 2,1,1 + f 2,1,2 -f 2,2,1 . At last f 1 := f 1,1,1 + f 1,1,2 and f 2 := f 2,1,1 + f 2,1,2 .
Moreover q ᾱ(ω 0 ) = 0 when | ᾱ| is even and q ᾱ(ω 0 ) = (-1) k |f ᾱ| when | ᾱ| is odd whereas h ᾱ(ω 0 ) = 0 when | ᾱ| is odd. When | ᾱ| = 4, h ᾱ(ω 0 ) = f β ω 0 where ᾱ = β•(j), j = 1; 2 and when

| ᾱ| = 2, h ᾱ(ω 0 ) = -(f ᾱ•(1) +f ᾱ•(2) )ω 0 . Now q 1 (ω 0 ) = 0, h 1 (ω 0 ) = ω 0 , q 2 (ω 0 ) = sin(ω 0 ) = (-1) k , h 2 (ω 0 ) = 2ω 0 cos(ω 0 ) = 0, q 3 (ω 0 ) = 0, h 3 (ω 0 ) = -2ω 0 , q 4 (ω 0 ) = -2(-1) k , h 4 (ω 0 ) = 0.
Thus, for i = 2 and so | ᾱ| = 3, |q 2 (ω 0 )q ᾱ(ω 0 )| = |1f ᾱ| (1/k) and for i = 4 and so

| ᾱ| = 1, |q 4 (ω 0 ) -q ᾱ(ω 0 )| = | -2 -f j | (1/k), since f j := f j,1,1 + f j,1,2 , j = 1; 2.
And, for i = 1 and so

| ᾱ| = 4, |h 1 (ω)/ω -h ᾱ(ω 0 )/ω 0 | ≤ |h 1 (ω)/ω -h 1 (ω 0 )/ω 0 | + |h 1 (ω 0 )/ω 0 -h ᾱ(ω 0 )/ω 0 | = |h 1 (ω)/ω -h 1 (ω 0 )/ω 0 | + |1 -f β | (1/k), due to Lemma 4.2. At last, for i = 3 and so | ᾱ| = 2, |h 3 (ω)/ω - h ᾱ(ω 0 )/ω 0 | ≤ |h 3 (ω)/ω -h 3 (ω 0 )/ω 0 | + |h 3 (ω 0 )/ω 0 -h ᾱ(ω 0 )/ω 0 | = |h 3 (ω)/ω -h 3 (ω 0 )/ω 0 | + | -2 + (f ᾱ•(1) + f ᾱ•(2) )| (1/k), due to Lemma 4.2.
(2) Since h ᾱ(ω 0 )/ω 0 = 0 for an odd | ᾱ| (cf. Proof of Theorem 4.1), it is bounded from above by a constant independent of k.

For an even i, |q i (ω)| is proved to satisfy the same property by induction on m where i = 2m. It is enough to assume that both |q 2m (ω)| and |h 2m (ω)/ω| are bounded from above by a constant independent of k and to use the recursive definition of q i and h i twice to compute the same expressions with indices 2m + 1 and 2m + 2 ((4.50) and (4.51)).

Energy decreasing

Using the Riesz basis constructed in the latest section, the energy is proved to decrease exponentially to a non-vanishing value depending on the initial datum. The decay rate is explicitly given at the end of Theorem 5.1 below since the ω's satisfying iω 2 ∈ (σ 2 ∪ σ2 ) are the solutions of (3.28). For any fixed value of n, the constant C is computable numerically. Its value is given for n = 2.

5.1. Energy decreasing using the Riesz basis. (1) H 1 is orthogonal to H 2 .

(2) Let u 0 in H be the initial condition of the boundary value problem given in the introduction and u 1 0 its orthogonal projection onto H 1 . Then E(t) decreases exponentially to E 1 (0) := u 1 0 2

H when t tends to +∞. More precisely

(5.57) E(t) ≤ E 1 (0) + e -2Ct E 2 (0)
where -C := sup iω 2 ∈(σ2∪ σ2) ℜ(iω 2 ) < 0.

Proof. First part: Above all, it is easy to see that the operator A * d is obtained by changing i by -i in A d . Thus, if A d ψ 1 (ω, .) = λψ 1 (ω, .), with λ = iω 2 then A * d ψ 1 (ω, .) = -λψ 1 (ω, .). Now, to prove that H 1 is orthogonal to H 2 , it suffices to check that any generalized eigenfunction ψ 2 (ω ′ , .) of H 2 is orthogonal to any eigenfunction ψ 1 (ω, .) of H 1 . First we assume that ψ 2 (ω ′ , .) is an eigenfunction, i.e

A d ψ 2 (ω ′ , .) = λ ′ ψ 2 (ω ′ , .)
with λ ′ = iω ′2 . Therefore, since λ is purely imaginary,

λ ′ < ψ 2 (ω ′ , .), ψ 1 (ω, .) > H = < A d ψ 2 (ω ′ , .), ψ 1 (ω, .) > H = < ψ 2 (ω ′ , .), A * d ψ 1 (ω, .) > H = -< ψ 2 (ω ′ , .), A d ψ 1 (ω, .) > H = -λ < ψ 2 (ω ′ , .), ψ 1 (ω, .) > H = λ < ψ 2 (ω ′ , .), ψ 1 (ω, .) > H .
Consequently < ψ 2 (ω ′ , .), ψ 1 (ω, .) > H = 0.

Secondly, we assume that λ ′ is not simple. Let ψ 2 (ω ′ , .) be an associated generalized eigenfunction of order p ≥ 2, in the sense that

(A d -λ ′ ) p ψ 2 (ω ′ , .) = 0, (A d -λ ′ ) p-1 ψ 2 (ω ′ , .) = 0. Setting ψ = (A d -λ ′ )ψ 2 (ω ′ , .
), then ψ is a generalized eigenfunction associated to λ ′ of order p -1, so arguing by iteration with respect to the order p we can assume that < ψ, ψ 1 (ω, .) > H = 0. Therefore λ ′ < ψ 2 (ω ′ , .), ψ 1 (ω, .) > H = < A d ψ 2 (ω ′ , .) + ψ, ψ 1 (ω, .) > H = < A d ψ 2 (ω ′ , .), ψ 1 (ω, .) > H = λ < ψ 2 (ω ′ , .), ψ 1 (ω, .) > H , as previously. Consequently < ψ 2 (ω ′ , .), ψ 1 (ω, .) > H = 0.

Second part: the spectrum of the dissipative operator A d is the union of σ 1 -set of the purely imaginary eigenvalues and σ 2 ∪ σ2 -set of the other eigenvalues (see Theorem 3.1). The initial condition u 0 := (u ᾱ) ᾱ∈I 0 is written as a sum of two terms:

u 0 := iω 2 ∈σ1 u 1 0 (ω, •)ψ 1 (ω, •) + iω 2 ∈(σ2∪ σ2) u 2 0 (ω, •)ψ 2 (ω, •)
where ψ 1 (ω, •) (respectively ψ 2 (ω, •)) is a normalized (in H) eigenfunction of A d associated to the eigenvalue iω 2 in σ 1 (resp. σ 2 ). Note that the sum takes into account the multiplicities of the eigenvalues here. Thus the solution of the boundary value problem given in the introduction is:

u(t) := iω 2 ∈σ1 u 1 0 (ω, •)e iω 2 t ψ 1 (ω, •) + iω 2 ∈(σ2∪ σ2) u 2 0 (ω, •)e iω 2 t ψ 2 (ω, •).
The energy, defined in the introduction, by (2.11) is:

E(t) = E 1 (t) + E 2 (t) with E 1 (t) := iω 2 ∈σ1 u 1 0 (ω, •) 2 H |e iω 2 t | 2 , E 2 (t) := iω 2 ∈(σ2∪ σ2) u 2 0 (ω, •) 2 H |e iω 2 t | 2 .
Now, since σ 1 contains only purely imaginary eigenvalues (see Theorem 3.1), |e 2iω 2 t | = 1, for any ω such that iω 2 ∈ σ 1 and any t > 0. Thus E 1 (t) = E 1 (0) for any t > 0.

The real part of iω 2 is a non-positive real number if ω is such that iω 2 ∈ (σ 2 ∪ σ2 ) (see Theorem 3.1). In the proof of Theorem 3.1, this real part is proved to be equal to 2γ j π with γ j independent of k if iω 2 ∈ σ 2 . Since σ2 is a finite set and since j belongs to a finite set, there exists C > 0 such that, for any ω such that iω

2 ∈ (σ 2 ∪ σ2 ): -ℜ(iω 2 ) ≥ C > 0. It holds |E 2 (t)| ≤ e -2Ct E 2 (0)
. Thus E 2 (t) decreases exponentially to 0 when t tends to +∞ and the total energy E(t) decreases exponentially to E 1 (0) when t tends to +∞.

5.2. Energy decreasing: a numerical example. Let us explicit the case n = 2 which corresponds to Figure 1. The polynomials P A,2 and P B,2 defined in Proposition 3.4 are:

P A,2 (z) = 9z 3 + 7z 2 + 7z + 9, P B,2 (z) = 9z 3 + z 2 -z -9.
The polynomial P A,2 has 3 roots which are: 5) .

z (2) A,1 = -1 = e iπ , z (2)
A,2 = 1 9 (1 -4i √ 5) = e -i arctan(4 √ 5) , z (2)
A,3 = 1 9 (1 + 4i √ 5) = e i arctan(4 √
Thus the spectrum of the conservative operator A 0 introduced at the beginning of Section 3 is given by (3.18) with The values of γ j defined by (3.36) are:

σ (0) 2 = {i(kπ ± arctan(4 √ 5
γ 1 = - 2 5π , γ 2 = γ 3 = - 3 10π
.

Then the set σ 2 which is a part of the spectrum of the dissipative operator A d (see the beginning of Section 3 and Theorem 3.1) has two vertical asymptots:

ℜ(λ) = 2πγ 1 = - 4 5 , ℜ(λ) = 2πγ 2 = 2πγ 3 = - 3 5 ,
which is consistent with the numerical computation of the spectrum (see Figure 4).

At last, numerically the eigenvalue of A d with the largest real part is λ ≈ -0.37459+0.873125i. Hence the approximate value for the decay rate: C ≈ 0.37459.

a k,l (λ) = < Bg, φ 0 k,l (kπ, •) > D(A0) ′ ,D(A0) λ + λ k = < g, B * φ 0 k,l (kπ, •) > C N λ + λ k , ∀ k ∈ Z * b k,l (λ) = < Bg, φ 0 k,l (kπ + π 2 , •) > D(A0) ′ ,D(A0) λ + λ k = < g, B * φ 0 k,l (kπ + π 2 , •) > C N λ + λ k , ∀ k ∈ Z c j,k (λ) = < Bg, φ 0 k (ω j,k , •) > D(A0) ′ ,D(A0) λ + λ j,k = < g, B * φ 0 k (ω j,k , •) > C N λ + λ j,k , ∀ k ∈ Z, j = 2, • • • , n Which implies that H(λ)g = i(ω 0 ) 2 ∈σ (0) ϕ 0 n+1 (ω 0 , 1) λ + i(ω 0 ) 2 g,
where ϕ 0 n+1 (ω 0 , •) is defined by (4.49). It holds

H(λ) = k∈Z ϕ 0 n+1 (ω 0 , 1) λ + λ k 0 ... 0 , ∀ λ such that ℜ λ = γ. sup ℜλ=γ |H(λ)| = sup ℜλ=γ i(ω 0 ) 2 ∈σ (0) ϕ 0 n+1 (ω 0 , 1) λ + i(ω 0 ) 2 ≤ √ 2 sup ℜλ=γ i(ω 0 ) 2 ∈σ (0) ϕ 0 n+1 (ω 0 , 1) γ + |(ω 0 ) 2 + ℑ(λ)| .
It is known that |ϕ 0 n+1 (ω 0 , 1)| 1 (cf. Lemma 4.2). The spectrum of A 0 can be split into a finite union of sets of the form i(kπ + θ) 2 k∈Z * or k∈Z , where θ is a real number, (cf. Theorem 3.1) and the multiplicity of the eigenvalues is uniformly bounded. Thus, if we set λ = γ + iy, it suffices to show (6.62) sup

y∈R k∈N 1 γ + |(kπ + θ) 2 + y| < ∞.
First we consider the case y ≥ 0 and we set Σ(y) = k∈N 1 γ + |(kπ + θ) 2 + y| . Then (6.63) Σ(y) ≤ k∈N 1 (kπ + θ) 2 < ∞, y ≥ 0. Now, we assume that y < 0 and we set y

= -Y 2 , Y > 0. If Y ≥ |θ|, we have Σ(y) = Σ 1 (Y ) + 1 γ + (E[ Y -θ π ]π + θ) 2 -Y 2 + Σ 2 (Y ),
where

Σ 1 (Y ) = k≤E[ Y -θ π ]-1 1 γ + Y 2 -(kπ + θ) 2 , Σ 2 (Y ) = k≥E[ Y -θ π ]+1 1 γ + (kπ + θ) 2 -Y 2 .
First, we have

(6.64) Σ(y) ≤ Σ 1 (Y ) + 1 γ + Σ 2 (Y ),
and the following estimates for Σ i (Y ), i = 1, 2 :

Σ 1 (Y ) ≤ k≤E[ Y -θ π ]-1 1 Y 2 -(kπ + θ) 2 , = k≤E[ Y -θ π ]-1 1 π( Y -θ π -k)(Y + kπ + θ) , ≤ 1 π k≤E[ Y -θ π ]-1 1 Y , 1, Σ 2 (Y ) ≤ k≥E[ Y -θ π ]+1 1 (kπ + θ) 2 -Y 2 = k∈N 1 ((k + E[ Y -θ π ] + 1)π + θ) 2 -Y 2 = k∈N 1 (k + E[ Y -θ π ] + 1)π + θ -Y (k + E[ Y -θ π ] + 1)π + θ + Y ≤ k∈N 1 (k + Y -θ π )π + θ -Y × kπ = π 6 .
So, we have proved that Σ(y) is uniformly bounded for large values of |y|, consequently (6.62) holds with a continuity argument.

Application to feedback stabilization with another feedback law

This section is dedicated to some stability properties of the solutions of system (7.65)-(7.70). We obtain an exponential stability result in the energy space. As in Section 2, the operator A d generates a C 0 semigroup of contractions on H.

• R • O • O1 • O2 • O1,1 • O2,2 • O1,2 • O2,1 ❉✐ss✐♣❛t✐♦♥ •❛✇ ❉✐r✐❝❤•❡t ❜♦✉♥❞❛r② ❝♦♥❞✐t✐♦♥ ❉✐ss✐♣❛t✐♦♥ •❛✇
In this section, we show that the semigroup e tA d decays to the null steady state with an exponential decay rate.

To obtain this, our technique is based on a frequency domain approach method and combines a contradiction argument with the multiplier technique to carry out a special analysis for the resolvent.

Theorem 7.1. There exist constants C, τ > 0 such that the semigroup e tA d satisfies the following estimate (7.76) e tA d L(H) ≤ C e -τ t , ∀ t > 0.

We will employ from [START_REF] Prüss | On the spectrum of C 0 -semigroups[END_REF][START_REF] Huang | Characteristic conditions for exponential stability of linear dynamical systems in Hilbert space[END_REF] the following frequency domain theorem for uniform stability of a C 0 semigroup of contractions on a Hilbert space: i.e., (7.85) iβ n z ᾱ,n + i d 2 z ᾱ,n dx 2 ≡ f ᾱ,n → 0 in L 2 (0, 1), ᾱ ∈ I. Our goal is to derive from (7.84) that ||Z ᾱ,n || H converges to zero. Thus there will be a contradiction.

We notice that from (7.80), it holds: By using the continuity and transmission conditions, we deduce by iteration and by the same way as above:

z ᾱ,n → 0, in L 2 (0, 1), ᾱ ∈ I.

Which contradicts the fact that Z n H = 1. Now, we assume that no subsequence of β n converges towards +∞, (i.e lim n→∞ β n = -∞). Since z ᾱ satisfies the first equality of (7.81), we multiply it by z ᾱ, and then integrating by parts, summing over all ᾱ ∈ I, using the boundary and transmission conditions as well as (7.86) and (7.88), we get

iβ n Z n 2
H -i ᾱ∈I 1 0 | dz ᾱ dx | 2 dx + o(1) = 0,
which also contradicts the fact that Z n H = 1.

1 .

 1 The characteristic equation 3.2. The families of eigenvalues 3.3. Iterative study of the characteristic equation 4. Riesz basis 5. Energy decreasing 5.1. Energy decreasing using the Riesz basis 5.2. Energy decreasing: a numerical example 6. Transfer function analysis 7. Application to feedback stabilization with another feedback law References 1. Introduction

Figure 1 .

 1 Figure 1. A Tree-Shaped network

2 = 3 . 1 .

 231 ∅ for any value of n ≥ 1. The characteristic equation. In order to prove Theorem 3.1, we establish the characteristic equation. Proposition 3.2. (The characteristic equation) Define, for ω ∈ C, M (ω) and T the matrices M (ω)

Theorem 3 . 3 .

 33 (Families of eigenvalues of A 0 and A d )

Figure 2 .

 2 Figure 2. Iterative strategy for analysing the spectrum Proposition 3.4. (Iterative rewriting of the characteristic equation) The complex λ = iω 2 (ω ∈ C * , ω = kπ, k ∈ Z and ω = (π/2) + kπ, k ∈ Z) is an eigenvalue of the operator A ǫ defined in Section 3.1 on the binary tree T with level (n + 1) (constructed in the introduction) if and only if (3.30) P A,n (z) + ǫ P B,n (z) ω = 0.

2 

 2 30) then ℑ(ω) is bounded from below. Indeed, the characteristic equation involves the matrix e M (ω) = cos(ω) sin(ω) ω -ω sin(ω) cos(ω) . If ω = x + iy with y tending to -∞, it follows e M (ω) e ix + o(1) -2 y e ix + o(1/y) -ye ix + o(y) 2e ix + o(1)   and e M (ω) T e M (ω) 0 1 = e -2y 4 e 2ix (-3/y) + o(1/y) 3e 2ix + o(y) .

Remark 3 . 5 .

 35 Existence of generalized eigenfunctions. As announced in Theorem 3.3 the dimension of the eigenspace associated to each eigenvalue of the third family of the eigenvalues of A 0 and A d is one. In other words, if λ ∈ σ (0) 2

Figure 3

 3 Figure 3 represents the polynomials Q A,3 , Q B,3 and Q A,4 :

  the notation of the spectra and the proof of Theorem 3.3 for the construction of the eigenfunctions.

Theorem 4 . 1 .

 41 (Riesz basis for the operator A d )The notation of Theorem 3.1 for the spectra of both operators A 0 and A d is kept here.Denote by ω 0 the number ω 0 j,k := kπ +

Theorem 5 . 1 .

 51 (Energy decreasing of the solution) Let E(t) be the energy defined by(2.11) in the introduction and H the Hilbert space introduced at the beginning of Section 2. Keeping the notation of Theorem 3.1, let H 1 (respectively H 2 ) be the subspace of H spanned by the ψ 1 (ω, •)'s (resp. ψ 2 (ω, •)'s), which are the normalized (in H) eigenfunctions of A d associated to the eigenvalues iω 2 in σ 1 (resp. σ 2 ∪ σ2 ).

)) 2 :Figure 4 .

 24 Figure 4. n = 2 : the spectrum σ 2 ∪ σ2 .

Figure 5 .

 5 Figure 5. A Tree-Shaped network with exponential stabilizing feedback Let ᾱ * be an arbitrary element of I Dir . We consider the following initial and boundary value problem : (7.65)∂u ᾱ ∂t (x, t) + i ∂ 2 u ᾱ ∂x 2 (x, t) = 0, 0 < x < 1, t > 0, ᾱ ∈ I,(7.66) i u(1, t) + ∂u ∂x (1, t) = 0, i u ᾱ(0, t) -∂u ᾱ ∂x (0, t) = 0, ᾱ ∈ I Dir , ᾱ = ᾱ * , t > 0,

Lemma 7 . 2 . 2 ,

 722 A C 0 semigroup e tL on a Hilbert space H satisfies ||e tL || L(H) ≤ C e -τ t , for some constant C > 0 and for τ > 0 if and only if(7.77) ρ(L) ⊃ iβ β ∈ R ≡ iR, ) < ∞,where ρ(L) denotes the resolvent set of the operator L. Lemma 7.3. The spectrum of A d contains no point on the imaginary axis. Proof. Since the resolvent of A d is compact, its spectrum σ(A d ) only consists of eigenvalues of A d . We will show that the equation (7.79) A d Z = iβZ with Z ∈ D(A d ) and β = 0 has only the trivial solution.By taking the inner product of (7.79) with Z and using(7.80) ℜ (< A d Z, Z > H ) = -|z(1)| 2ᾱ * = ᾱ∈I Dir |z ᾱ(0)|we obtain that z(1) = 0, z ᾱ(0) = 0, ᾱ * = ᾱ ∈ I Dir . Next, we get the following ordinary differential equation:ᾱ(x) + i d 2 z ᾱ dx 2 (x) = 0, x ∈ (0, 1), ᾱ ∈ I, z(1) = dz dx (1) = 0, z ᾱ(1) = dz ᾱ dx (1) = 0, ᾱ * = ᾱ ∈ I Dir , z ᾱ * (0) = 0, z ᾱ•β (1) = z ᾱ(0), β = 1, 2, ᾱ ∈ I Int , , ᾱ ∈ I Int .And the above system has only the trivial solution.Proof of Theorem 7.1. By Lemma 7.2, it suffices to show that A d satisfies the following two conditions:(7.82)ρ(A d ) ⊃ i β β ∈ R ≡ iR, and(7.83) lim sup |β|→∞(iβ -A d ) -1 L(H) < ∞,where ρ(A d ) denotes the resolvent set of the operator A d . By Lemma 7.3 the condition (7.82) is satisfied. Suppose that condition (7.83) is false. By the Banach-Steinhaus Theorem (see [17]), there exist a sequence of real numbers β n → ∞ and a sequence of vectors Z n ∈ D(A d ) with Z n H = 1 such that (7.84) ||(iβ n I -A d )Z n || H → 0 as n → ∞,

( 7 .z n ( 1 )

 71 86) ||(iβn I -A d )Z n || H ≥ |ℜ ( (iβ n I -A d )Z n , Z n H ) | = |z n (1→ 0, z ᾱ,n (0) → 0, ᾱ * = ᾱ ∈ I Dir → 0, ᾱ * = ᾱ ∈ I Dir .First we assume that the sequence (or a subsequence) of β n converges towards +∞. According to (7.85):z ᾱ,n = A ᾱ,n sin β n x + B ᾱ,n cos β n x -(7.89) i x 0 sin √ β n (xy) √ β n f ᾱ,n (y) dx, x ∈ (0, 1), ᾱ ∈ I,where A ᾱ,n and B ᾱ,n are constants.Moreover, for ᾱ = ᾱ * , (7.90)z ᾱ * ,n = A ᾱ * ,n sin β n xi x 0 sin √ β n (xy) √ β n f ᾱ * ,n (y) dx, x ∈ (0, 1).According to (7.87)-(7.88), it holds for ᾱ * = ᾱ ∈ I Dir , (7.91)A ᾱ sin √ β n + B ᾱ cos √ β n → 0 A ᾱ √ β n cos √ β n -√ β n B ᾱ sin √ β n → 0,which implies that, for ᾱ * = ᾱ ∈ I Dir , (7.92) A ᾱ,n , B ᾱ,n → 0 and that (7.93) z ᾱ,n → 0, in L 2 (0, 1), ᾱ * = ᾱ ∈ I Dir .

Transfer function analysis

The transfer function of the conservative operator A 0 introduced at the beginning of Section 3 is proved to be bounded from above. Let us recall the definition of this operator:

0, 1) : satisfies (6.58) to (6.60) hereafter , (6.58) du dx (1) = 0, u ᾱ(0) = 0, ᾱ ∈ I Dir , (6.59)

, where the duality is obtained by means of the inner product in H.

Theorem 6.1. (Estimate of the transfer function) Let A 0 : D(A 0 ) ⊂ H → H and B be the operators defined above. The transfer function is given by:

Proof. In order to compute the transfer function and to prove that it satisfies sup

We denote ψ λ = (λI + A 0 ) -1 Bg.

We consider the decomposition, for an even n (an odd value for n leads to a similar expression and this case is left to the reader):

where the φ 0 k,l (kπ, •)'s (respectively φ 0 k,l (kπ + π 2 , •)'s and the φ 0 k (ω j,k , •)'s) are the normalized (in H) eigenfunctions of A 0 with the corresponding eigenvalues λ k = i(ω k ) 2 with ω k ∈ σ 0 1 (resp. λ j,k = i(ω j,k ) 2 ∈ σ 0 2 ). See Theorems 3.1 and 3.3 for the details and note that, for simplicity, the same notation is used for eigenfunctions which do not have the same form. Now the above coefficients in the decomposition of ψ λ are equal to:


Ingrid Exurville

Jacques Fournier

Jean-Max Dutertre

Bruno Robisson

Assia Tria
email: assia.tria@cea.frdutertre@emse.fr

Practical measurements of data path delays for IP authentication & integrity verification

This paper describes the results of the practical measurements done to determine the path delay associated with each bit of a hardware AES FPGA implementation using a clock glitch injection tool. We illustrate how the measured path delays can constitute a characteristic fingerprint of an Intellectuel Property (IP) and can be used to detect the insertion of hardware trojans. The influence of synthesis options and inter die variations on the measurements is also studied. Compared to trojan detection schemes based on path delay characterisations already proposed in the literature, our approach does not require any additional test circuit to be inserted in the IP. Moreover our results are based on practical measurements.

I. INTRODUCTION

The authenticity and integrity of hardware modules has become a hot topic lately, in particular for security-related applications. The first phenomenon justifying this is the delocalisation of production facilities: even though a particular design is specified and implemented within one's own premises, the manufacturing of the hardware chip might be done in some (far away) different facility being less securitystringent leading to one having doubts on whether the chip sent back is the original design or whether a trojan has not been inserted into the original design. The second phenomenon is the "de-materialization" of hardware designs due to the advent of cheap and powerful FPGAs. The design of complex systems for such programmable devices might involve the integration of several blocks (or IPs) from different design houses. End users of such systems might want to make sure that the critical blocks (like encryption machines) used in the end system is actually the one coming from a trusted/certified provider and that it is not a rogue functional copy or that it has not been modified through the insertion of a trojan.

In this paper we illustrate how measured path delays can constitute a characteristic fingerprint of a IP and be used to detect the insertion of hardware trojans. We describe the results of the practical measurements done to determine the path delay associated with each bit of a hardware AES FPGA implementation using a clock glitch insertion tool. The influence of synthesis options and inter die variations on the measurements is also studied. Our scheme is based on practical measurements and does not require the addition of any dedicated circuitry in the IP under test. This paper is organised as follows: we first review the principles already proposed for authenticating and verifying the integrity of integrated circuits (or IPs), with a focus on the use of path delays for detecting hardware trojans. Next we describe our design under test, a straight forward hardware implementation of the AES encryption algorithm and some of the trojans devised for our measurements. The practical setup used is then detailed and the practical results obtained are covered. Then we conclude with a discussion on the potential of our proposed scheme.

II. INTEGRITY FOR IP VERIFICATION

We shall use the term Intellectual Property (IP) to refer to the implementation of some mathematical functionality or state machine, designed using some hardware abstraction language (VHDL, Verilog, etc.) that is intended to be embedded into an FPGA (The FPGA target is the main target of our study) or to be synthesized into some integrated circuit (IC) technology.

A hardware trojan is composed of two parts, the trigger and the payload [START_REF] Jin | Experiences in hardware trojan design and implementation[END_REF]. The trigger is the mechanism that determines the condition under which the 'malicious' effect of the trojan should start. The trigger can either be generated externally (external signal or a special external physical condition) or internally (internal state of the IC, special data configurations, etc.). Moreover the trigger can either be combinational where the sought condition is the result of a logical operation among several signals or sequential where the signal is generated by a state machine. The payload is the 'malicious' effect of the trojan: it can either be explicit where signals or logic blocks are directly added, removed or de-activated [START_REF] Jin | Hardware trojan detection using path delay fingerprint[END_REF] or implicit where the effect cannot be directly observed like, for example, the thinning of particular wires or hiding information into one of the side channels of the IC [START_REF] Lin | Moles: malicious off-chip leakage enabled by side-channels[END_REF].

Most research works have indeed focused on the detection of trojans. Detecting trojans is a complex, multi-dimensional problem which depends on the type of the trojan (functional or parametric), its size, its distribution over the IC's surface and its structure. A taxonomy for detecting trojans is proposed in [START_REF] Wang | Detecting malicious inclusions in secure hardware: Challenges and solutions[END_REF]. Apart from classical IC analysis techniques either based on Failure Analysis or on ATPG (Automatic Test Pattern Generation) which are limited in terms of coverage of the IC, novel techniques have been proposed. For example side channels have been studied in [START_REF] Agrawal | Trojan detection using ic fingerprinting[END_REF], [START_REF] Rad | Sensitivity analysis to hardware trojans using power supply transient signals[END_REF]. However such techniques are limited by the size of the trojan with respect to the IC under analysis. More sophisticated region-based analyses have been proposed in [START_REF] Banga | A region based approach for the identification of hardware trojans[END_REF]. In [START_REF] Jin | Hardware trojan detection using path delay fingerprint[END_REF], the authors propose a method of detecting trojans by measuring the delay paths of a DES circuit.

Althought there is framework which does not require a Reconfigurable and Communication-Centric Systems-on-Chip (ReCoSoC), 2013 8th International Workshop on http://dx.doi.org/10.1109/ReCoSoC.2013.6581551

golden IC [START_REF] Li | A sensor-assisted selfauthentication framework for hardware trojan detection[END_REF], most of the techniques proposed in the literature rely on the availability of a "golden reference". The "golden reference" is an implementation of the IC which is trojanfree and onto which the reference side-channel or delay path measurements are made and later used as a reference when implementing the trojan detection scheme onto other instantiations of the IC. Such a "golden" is only available once the circuit has been fabricated and totally reverse-engineered (which is an expensive and time consuming process) to make sure that it contained no trojan.

III. USE OF PATH DELAYS' MEASUREMENTS AS AN IP'S

FINGERPRINT

Lately, several research papers have proposed schemes for detecting trojans based on the measurement of path delays within an IC. The use of "shadow registers" is very widespread. In [START_REF] Rai | Performance of delay-based trojan detection techniques under parameter variations[END_REF], the "shadow registers" worked with a "shadow clock" which runs at the same frequency as the main clock. A ajustable phase offset permits to measure path delays along an arbitrary large number of paths in the design. In [START_REF] Li | At-speed delay characterization for ic authentication and trojan horse detection[END_REF], the authors propose a mechanism where "shadow registers" are added to a given set of critical data paths. Those "shadow registers", whose sampling times are monitored via a dedicated clock signal, are used to measure the associated delay path: if a trojan is present on this particular path, then the measured delay path is expected to be different from the data path without trojan. By extending this principle to several data paths and by considering that the monitoring of the sampling time of each "shadow register" as a Challenge, then the IC can be authenticated through a PUF-like challengeresponse pair CRP. A similar philosophy is proposed in [START_REF] Lamech | Trojan detection based on delay variations measured using a high-precision, low-overhead embedded test structure[END_REF] where existing test structures are modified to introduce "embedded test structures" that detect delay anomalies introduced by a trojan.

A detection of trojans based on path delays without additional circuitry is discussed in [START_REF] Jin | Hardware trojan detection using path delay fingerprint[END_REF]: the measurement of the path delays corresponding to each of the 64 bits of the DES ciphertext are determined by simulation.

In this paper, we pushed forward the principle lain in [START_REF] Jin | Hardware trojan detection using path delay fingerprint[END_REF] to show that the path delays associated with the data bits of an IC running an encryption algorithm like the AES can be measured in practice and can be used to detect modifications within the circuit. Our first contribution is to perform concrete measurements of the path delays associated with individual bits of the principal data path. The main advantages and differentiators of using this technique are the following:

• We only require an access to the clock of the targeted IP and to the inputs and outputs of its principal data path. We do not need any additional circuit or modification of any existing scan chain.

• We do not actually determine the delay incurred by the longest path of the IP but the delay corresponding to each bit of the longest data path.

• The trojans don't need to be activated for being detected by our scheme.

IV. DEVISING PROOF-OF-CONCEPT TROJANS FOR A HARDWARE AES

To investigate about our proposed methodology, practical clock glitch injections were done on a hardware AES imple- With erroneous ciphertexts, & their corresponding correct ones, the attacker can perform differential cryptanalysis (like proposed in [START_REF] Ali | Multi-level attacks: An emerging security concern for cryptographic hardware[END_REF]).

Outputting M1 for a known plaintext

The key is recovered by the XOR between M1 and the known plaintext. Forcing all round keys to zero K1 to K10 are known, only K0 is unknown & can be calculated. Fixing the value of the state matrix M1 to M10 are hence known, the original key can be calculated.

TABLE I. TROJANS IN A HARDWARE AES

mented in VHDL and synthesized for and tested on a SpartanIII FPGA. The AES is a standard established by the NIST [START_REF]Specification for the Advanced Encryption Standard[END_REF] for symmetric key cryptography.

A. Trojan definitions for AES

In our use case, we view the AES block as an IP where we only have access to the inputs (plaintext, key), outputs (ciphertext) and configuration bits (start, process end). We hence do not cover trojans that use covert channels like the power consumption or electromagnetic emissions to convey sensitive information out the chip [START_REF] Lin | Moles: malicious off-chip leakage enabled by side-channels[END_REF]. In order to exhaustively search for the trojans that could be implemented on such an AES IP, we performed a security analysis of such a design. Two main asset were identified:

• The plaintext is an asset in the case the AES IP is used to protect the confidentiality of data. The attacker may want to insert a trojan that would output the plaintext itself instead of the ciphertext and hence have access to any sensitive data that was meant to be encrypted by the AES IP.

• The key is the secret that is used by the AES IP to encrypt/sign the plaintext. An attacker might want to output the secret key in order to then be able to decrypt the ciphertext.

Table I summarizes how the above assets could be output by a trojan. Note that the table only looks at the payload of the trojan and not its trigger as there are in our opinion too many different possibilities of the later.

B. Description of implemented trojans [14]

We implemented two kinds of trojans inserted at RTL level. Both of them have the same trigger. The activation mecanism of the trojan relies a specific plaintext sent externally.

• The first one allows us to directly have the key K0 instead of the ciphertext (Figure 1). We inserted a multiplexer into the AES block. When the trigger is activated, the key is written into the ciphertext register.

• The second one gives the subkey K10 instead of the ciphertext (Figure 2). To do so the state matrix is zeroed at the tenth round in the AddRoundKey transformation. Thus, insofar as this step is composed of an XOR operation between the State matrix and the subkey K10, we get K10 in place of the ciphertext. Each of the above trojans' only add less than 3% to the number of slices occupied by our original AES implementation. From now on AES INT shall refer to the original AES without trojan, AES HT1 to the AES with the first trojan and AES HT2 to the AES with the second trojan.

V. M EASUREMENT TOOL & SET-UP USED

Clock glitches are a well known fault injection means that endanger data integrity of secure circuits [START_REF] Yoshikawa | A hardware trojan for cryptographic countermeasure circuits[END_REF]. However, it can also be turned into a path delay measurement tool used to detect hardware trojans. We used a clock glitch generator similar to the one presented in [START_REF] Agoyan | When clocks fail: on critical paths and clock faults[END_REF] and [START_REF] Endo | An onchip glitchy-clock generator for testing fault injection attacks[END_REF] to allow such measurements. In this section, the basics of timing constraints and how their violation may be used to measure path delays are given. Next we show how the uncertainty of the measurement may be almost nullified. The device under test is described. Finally, the way we have conducted measurement experiments is reported.

A. Principle of path delay measurement with clock glitches

Data is released from the first register bank on a clock rising edge and then processed through the logic before being latched into the next register bank on the next clock rising edge. Thus, in a first approximation the clock period (T clk ) has to be longer than the maximum data propagation time through the logic (D pM ax ) to ensure correct operation. Besides, a precise writing of the timing constraint equation requires to take into account three other parameters: D the delay between the clock rising edge and the actual update of a register's output; T skew the skew or slight phase difference that may exist between the clock signals at the clock's inputs of two different registers; T setup the set-up time which is the amount of time for which a D flip-flop input must be stable before the clock's rising edge to ensure reliable operation. There also exists a hold time (T hold ) which expresses the same constraint but after the clock edge. Hence, the timing constraint equation (eq. 1) is obtained:

T clk >D clk2q + D pM ax + T setup -T skew (1)
A set-up time violation arises if the last signal transition is too close to the clock's rising edge. Then the DFF's output goes into a metastable behaviour [START_REF] Horstmann | Metastability behavior of cmos asic flip-flops in theory and test[END_REF]: it may stabilize either on a high or low state generating an error or not. Consequently the violation of the timing constraint is a straightforward means to inject faults into a circuit. This may be achieved by reducing progressively the clock period (a so called clock glitch) until a setup time violation occurs.

B. Delay measurements model

As mentioned above, path delay measurement is not deterministic. However, we developed a measurement methodology intended to reduce this uncertainty. Several measurements are done with the same experimental settings. These measurements lie within the interval limited by T setup + T hold , arranged in what we call a timing distribution. Moreover, provided that there is enough measurements (a few thousands as revealed by our experiments) they feature a Gaussian-like shape. Using GNU Octave tool [START_REF]Gnu octave[END_REF], we approximated these distributions with Gaussian curves and saw that these approximations fitted well in all cases. One of these approximated Gaussian is depicted in Figure 3.

C. Description of the device under test

As explained before, we have chosen a programmable circuit (FPGA) running the AES algorithm as a test vehicle to conduct this study. The test chip's nominal clock period is 100 MHz, and its core nominal voltage is 1.2V. As the delays in the encryption module are greater than the delays in the cipher's other modules we can assume that the encryption module will be faulted before any other module (FSM, UART, ...). Hence, the path delays of the encryption module will be measured first by using clock glitches. These path delays will be used in our trojan detection methodology.

The set-up and hold times of the device's DFFs have minimum values of 180ps and zero respectively (for a speed grade -5 component). Hence, the minimal measurement's uncertainty is 180ps. Note that, the width of the Gaussian's bottom in Figure 3 is around 200ps which is close to the measurement's uncertainty.

D. Measurement experiments

In our implementation, an AES round is executed in one clock cycle. For every bit in the cipher block, the propagation delay varies depending on the data processed. Thus the critical path may change at each clock cycle. Path delay measurements were consequently done with the same plaintext and key in order to obtain fair comparisons between the tested ICs. A measurement series is done by progressively reducing the clock period during the 10 th AES round by steps of 35ps until it becomes too short to comply with the timing constraints. Hence, the value of the ciphertext stored in the register is corrupted. As a consequence, a progressive increase of the stress applied (i.e. the stepwise reduction of the clock period) successively induces an increasing number of faults into the longest paths. At the bit level, the clock period related to the first fault occurrence is then recorded for every bit to build the aforementioned timing distributions. As enough measurements are achieved, the corresponding Gaussian curves are calculated and the mean path delay of every faulted bit is retrieved.

Note that for some bits, which we shall call the ghost bits, measurement errors occurred and no associated measured path delays were available. The reason for this is that for such bits, at some point, the generated glitch corrupted the state machine of the AES in addition to the data path resulting in the chip not responding: this of course is an artefact due to our measurement tool, artefact which, as we shall discuss later, might provide useful information in the end.

VI. PRACTICAL RESULTS

For a constant plaintext (all ones) and a known constant key, we ran 4000 tests whereby for each test the clock glitch is increased by steps of 35 ps and the resulting corrupted ciphertext recorded and analysed (We determined which bit/s of the State matrix has/ve been corrupted [START_REF] Agoyan | When clocks fail: on critical paths and clock faults[END_REF]). For each test, one or several bits of the measured ciphertext is corrupted and for each of those bits the corresponding number of steps (which gives the duration of the clock glitch, which in turn gives the associated delay path) is recorded as a measured path delay (MPD). Hence for each of the 128 bits, we have a distribution of measured delay paths as shown in Figure 3 for the AES INT.

A. Distribution of measured path delays for all 128 bits

We also chose to have a graphical representation where we represent the mean (associated with the Gaussian approximation as explained earlier) of the measured path delay associated with each bit of the State matrix of the AES. Such a representation (Figure 4) gives a characteristic picture of the MPDs associated with each bit of the AES State Matrix, along with a distribution of the ghost bits (In our representation, we tried to have a "curve" linking the values of each bit's MPD, but could not show values for ghost bits resulting in the curve being discontinuous) relative to our measurement tool. Such a representation shall be called measured path delays' -MPDdistributions. • The value of the chosen plaintext and key: in our experiment we kept the value of the key and plaintext constant (Figure 4).

• The external physical conditions like temperature, voltage, etc.: this aspect was covered. Voltage glitchs have the same effect as clock glitches. The minor variation of the voltage and the temperature has no significant effect on the measurements done. The experiments were performed at room temperature with almost no fluctuations in the voltage supplied [START_REF] Zussa | From physical stresses to timing constraints violation[END_REF].

• The VHDL code of the IP: Our measurements showed that recompiling a same VHDL code, while keeping all synthesis options the same, generated MPD's distributions which were the same showing that this factor shall have no effect on our trojan detection scheme.

• Synthesis options: We looked at the effect of playing with synthesis options like the KEEP HIERARCHY [START_REF]Synthesis options (xst)[END_REF]. As expected when this option was switched on, on average, the MPD associated with each bit was longer but at the same time, the path delays' distribution was also modified. This phenomenon is illustrated in Figure 5.

• The FPGA: due to "inter-die" process variations, we expected to have to subtle variations in propagation times for a same bitstream being run on different dies of the same FPGA. For doing so, we had four different SpartanIII boards (labelled B1 to B4) onto which we loaded the same AES INT bitstream and performed the measurements. The dispersion phenomenon observed is illustrated in Figure 6 for bit 32 of the State matrix (similar trends are observed on the other bits).

The mean path delay associated with each bit is hence shifted when the same bitstream is transported from one board to another. This phenomenon is better illustrated by looking at the MPDs' distributions for all 128 bits. (We only show the first 32 bits in figure 7 for a matter of clarity, but this presented behaviour is the same for the 128 bits of the State matrix): the "orders of appearances" are the same, the ghost bits are the same, with just the 'curves' being shifted vertically. Furthermore, this figure emphasizes the differences between the used boards despite our Gaussian approximation.

Experiments showed that the inter-die variability was always limited to a 300ps range. Futhermore, due to the change of delay caused by the synthesis, the gaussian model allows us to observe easily the differences between the curves. The same measurements were done on the IP AES HT1. Then we compared the MPDs distributions of the AES INT and that of AES HT1 on the same board B1 (Figure 8 (For a matter of clarity, we only show the first 32 bits but the trend is the same for all 128 bits of the State matrix.)): we not only see that the mean path delay associated with each bit has significantly changed but also that their "orders of appearances" and the distribution of the ghost bits have also been changed.

The modification in the MPDs' distribution incurred by the addition of the trojan (in this case modification of the VHDL code) is more important than that incurred by simply porting a same bitstream from one board to another. On a bit level, this is illustrated in Figure 9 where, for the bit 32 of the state matrix, on the left we have the four measurements for AES INT on four different boards and on the right we have measurements made on the same boards with AES HT1. This shows that this tool is able, at least for the four samples we had, to detect a significant change in the VHDL code beyond the variations incurred by inter-die variations (Figure 10). Of course, this needs to be confirmed on a much larger set of samples. With respect to synthesis options (KEEP HIERARCHY option in our case), measurements showed that in each of the cases where the option was activated or deactivated, the measured MPDs' distributions were significantly modified by the presence of the trojan showing that the activation of such an option does not reduce the detectability capacity of our approach (Figure 11) even when the KEEP HIERARCHY option is set.

Note that in this paper we reported results with respect In this paper we illustrated how a tool used to inject clock glitches into a cryptographic module can be used to perform practical measurements of the mean path delay corresponding to each bit of the principal data path of an AES IP. The distribution of those propagation times is a characteristic "fingerprint" of the module, suggesting that this might be a practical means of authenticating a IP. Moreover since this distribution is influenced by the addition of trojan horses, it might also be used to qualify the integrity of a given IP, without adding any other circuit to the IP. In this paper, this "characteristic fingerprint" consists in visually comparing MPD distribution curves. Future work shall consist of giving a quantitative aspect of this "characteristic fingerprint", such as looking at the classification of the different bits in order of increasing or decreasing propagation times or the distribution of the "ghost bits"or even at the correlation between the curves corresponding to the mean path delays. More experiments shall also be conducted using other types of trojans. Our approach could also be the base for devising a method/tool that would automatically introduce in a given sensitive IP some test chain that would give end users a (secure) access to a clock PIN and the IP's IOs to perform such characterisations and authenticate and verify the IP under test. Ultimately we shall see if the MPDs can be constructed by simulation which could get rid of the "golden reference" problem.

Fig. 1 .Fig. 2 .

 12 Fig. 1. First trojan implemented: AES HT1.

Fig. 3 .

 3 Fig. 3. Distribution for bit 32 of State matrix This allowed us to choose to represent the distribution corresponding to each measured path delay by the mean of the best fitted Gaussian curve.

Fig. 4 .

 4 Fig. 4. Distribution for the first 32 bits for two different keys and plaintexts B. Factors impacting the measurements of the MPDs When performing such measurements, several factors influence the measured propagation time for each bit of the State matrix:

Fig. 5 .Fig. 6 .

 56 Fig. 5. Distribution for the first 32 bits without (thick brown line) & with (thin blue line) KEEP HIERARCHY

Fig. 7 .

 7 Fig. 7. Path delays for first 32 bits of the State matrix on 4 different boards C. Impact of the hardware trojans

Fig. 8 .

 8 Fig. 8. Path delays distributions without (thick brown line) & with (thin orange line) trojan for the first 32 bits of the State matrix

Fig. 9 .

 9 Fig. 9. Path delay measured for bit 128 on 4 boards without (left) and with (right) trojan.

Fig. 10 .

 10 Fig. 10. Path delay distributions for the first 32 bits on 4 boards without (thick brown line) & with (thin orange line) trojan.

Fig. 11 .

 11 Fig. 11. Path delay distributions for the first 32 bits with KEEP HIERARCHY without (thick blue line) & with (thin green line) trojan to AES HT1 only as similar behaviours were obtained with AES HT2. CONCLUSION & DISCUSSION FOR FUTURE WORK

ACKNOWLEDGMENT

This work is supported by the DGA (Délégation Générale de l'Armement, Paris, France) and the HOMERE project (Hardware trOjans : Menaces et robustEsse des ciRcuits In-tEgrés, FUI 14).