Jacques M Bahi
email: jacques.bahi@univ-fcomte.fr

Xiole Fang

Christophe Guyeux
email: christophe.guyeux@univ-fcomte.fr

Qianxue Wang
email: qianxue.wang@univ-fcomte.fr

Xiaole Fang
email: xiaole.fang@univ-fcomte.fr

Suitability of chaotic iterations schemes using XORshift for security applications

Keywords: pseudorandom number generators, Chaotic sequences, Statistical tests, Discrete chaotic iterations, Information hiding

Suitability of chaotic iterations schemes using XORshift

for security applications

I. INTRODUCTION

To use a pseudorandom number generator (PRNG) with a large level of security is necessary to satisfy the Internet security requirements to support activities as e-Voting, information hiding, and the protection of intellectual property [START_REF] Bahi | A new chaos-based watermarking algorithm[END_REF], [START_REF] Liu | An image fragile watermark scheme based on chaotic image pattern and pixel-pairs[END_REF], [START_REF] Yi | Practical internet voting system[END_REF]. This level depends on the proof of theoretical properties and results of numerous statistical tests. Many PRNGs, based for instance on linear congruential methods and feedback shiftregisters [START_REF] Knuth | The Art of Computer Programming[END_REF], [START_REF]Comparison of point sets and sequences for quasi-monte carlo and for random number generation[END_REF], [START_REF] Blaszczyk | Experimental validation of a true random binary digit generator fusion with a pseudo random number generator for cryptographic module application[END_REF], have been proven to be secure, following a probabilistic approach. More recently, several researchers have explored the idea of using chaotic dynamical systems to reinforce the security of these important tools [START_REF] Falcioni | Properties making a chaotic system a good pseudo random number generator[END_REF], [START_REF] Cecen | A new hybrid nonlinear congruential number generator based on higher functional power of logistic maps[END_REF], [START_REF] Li | Pseudo-random bit generator based on couple chaotic systems and its applications in stream-cipher cryptography[END_REF]. But the number of generators claimed as chaotic, which actually have been proven to be unpredictable (as it is defined in the mathematical theory of chaos) is very small. This paper extends a study initiated in [START_REF] Bahi | A novel pseudo-random generator based on discrete chaotic iterations[END_REF], [START_REF] Wang | Randomness quality of CI chaotic generators. application to internet security[END_REF], [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF], in which we tried to fill this gap. In [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF], it is proven that chaotic iterations (CIs), a suitable tool for fast computing iterative algorithms, satisfies the topological chaotic property, as it is defined by Devaney [START_REF] Devaney | An Introduction to Chaotic Dynamical Systems[END_REF]. In [START_REF] Bahi | A novel pseudo-random generator based on discrete chaotic iterations[END_REF] the chaotic behavior of CIs is exploited in order to obtain an unpredictable PRNG, which depends on two logistic maps. Lastly, in [START_REF] Wang | Randomness quality of CI chaotic generators. application to internet security[END_REF], a new version of this generator using decimations has been proposed and * Authors in alphabetic order XORshift has replaced the logistic map. We have shown that, in addition of being chaotic, this generator can pass the NIST (National Institute of Standards and Technology of the U.S. Government) battery of tests [START_REF][END_REF], widely considered as a comprehensive and stringent battery of tests for cryptographic applications.

In this paper, a new version of this chaotic PRNG is introduced. It is based on a Lookup Table (LUT) method. After having introduced it, we will give a comparison of the speed, of the statistical properties, and of the security for all of these generators based on XORshift generator [START_REF] Marsaglia | Xorshift rngs[END_REF]. These results added to its chaotic properties allow us to consider that this new generator has good pseudorandom characteristics and is able to withstand attacks. After having presented the theoretical framework of the study and a security analysis, we will give a comparison based on new statistical tests. Finally a concrete example of how to use these pseudorandom numbers for information hiding through the Internet is detailed.

The remainder of this paper is organized in the following way. In Section II, some basic definitions concerning chaotic iterations and PRNGs are recalled. Then, the generator based on LUT discrete chaotic iterations is presented in Section III. In Section IV, various tests are passed to make a statistical comparison between this new PRNG and other existing ones. In the next sections, a potential use of this PRNG in some Internet security field is presented, namely in information hiding. The paper ends with a conclusion section where the contribution is summarized and intended future work is presented.

II. REVIEW OF BASICS

A. Notations 1; N → {1, 2, . . . , N} S n → the n th term of a sequence S = (S 1 , S 2 , . . .) v i → the i th component of a vector: v = (v 1 , v 2 , . . . , v n ) f k → k th composition of a function f strategy → a sequence which elements belong in 1; N S → the set of all strategies

C k n → the binomial coefficient n k = n! k!(n-k)! ∧
→ the bitwise exclusive or

+
→ the integer addition and → the usual shift operators (X, d) → a metric space x → returns the highest integer smaller than

x n! → the factorial n! = n × (n -1) × • • • × 1 N * → the set of positive integers {1,2,3,...} &
→ the bitwise AND

B. Chaotic iterations

Definition 1 The set B denoting {0, 1}, let f : B N -→ B N be an "iteration" function and S ∈ S be a chaotic strategy. Then, the so-called chaotic iterations are defined by [START_REF] Robert | Discrete Iterations. A Metric Study[END_REF]:

         x 0 ∈ B N , ∀n ∈ N * , ∀i ∈ 1; N , x n i = x n-1 i if S n i f (x n-1 ) S n if S n = i. (1)
In other words, at the n th iteration, only the S n -th cell is "iterated". Note that in a more general formulation, S n can be a subset of components and f (x n-1 ) S n can be replaced by f (x k ) S n , where k < n, describing for example delays transmission. For the general definition of such chaotic iterations, see, e.g., [START_REF] Robert | Discrete Iterations. A Metric Study[END_REF].

Chaotic iterations generate a set of vectors (Boolean vectors in this paper), they are defined by an initial state x 0 , an iteration function f , and a chaotic strategy S .

Algorithm

1 An arbitrary round of the old CI(XORshift1,XORshift2) generator

a ← XORshi f t1() m ← a mod 2 + c while i = 0, . . . , m do b ← XORshi f t2() S ← b mod N x S ← x S end while r ← x Return r C. Old CI(XORshift, XORshift) algorithm
The basic design procedure of the old CI generator [START_REF] Bahi | A novel pseudo-random generator based on discrete chaotic iterations[END_REF] is recalled in Algorithm 1. The internal state is x (N bits), the output state is r (N bits), a and b are computed by two XORshift generators. Finally, N and c 3N are constants defined by the user.

D. New CI(XORshift, XORshift) algorithm

Algorithm 2 summarizes [START_REF] Wang | Randomness quality of CI chaotic generators. application to internet security[END_REF] the basic design procedure of the new generator. The internal state is x (a Boolean vector of size N), the output state is r (N bits). a and b are those computed by the two XORshifts. The value f (a) is an integer, defined as in Equation 2. Lastly, N is a constant defined by the user.

m n = f (y n ) =                            0 if 0 y n 2 32 < C 0 N 2 N , 1 if C 0 N 2 N y n 2 32 < 1 i=0 C i N 2 N , 2 if 1 i=0 C i N 2 N y n 2 32 < 2 i=0 C i N 2 N , . . . . . . N if N-1 i=0 C i N 2 N y n 2 32 < 1.
(2)

Algorithm 2 An arbitrary round of the new CI(XORshift1,XORshift2) generator 1: while i = 0, . . . , N do 2:

d i ← 0 3: end while 4: a ← XORshi f t1() 5: m ← f (a) 6: k ← m 7: while i = 0, . . . , k do 8: b ← XORshi f t2() mod N 9: S ← b 10: if d S = 0 then 11: x S ← x S 12: d S ← 1 13: else if d S = 1 then 14: k ← k + 1 15:
end if 16: end while 17: r ← x 18: Return r

III. LUT CI(XORSHIFT,XORSHIFT) ALGORITHMS AND EXAMPLE

A. Introduction

The LUT CI generator is an improved version of the new CI generator. The key-ideas are:

• To use a Lookup Table for a faster generation of strategies. These strategies satisfy the same property than the ones provided by the decimation process. • And to use all the bits provided by the two inputted generators (to discard none of them). These key-ideas are put together by the following way.

Let us firstly recall that in chaotic iterations, only the cells designed by S n -th are "iterated" at the n th iteration. S n can be either a component (i.e., only one cell is updated at each iteration, so S n ∈ 1; N ) or a subset of components (any number of cells can be updated at each iteration, that is, S n ⊂ 1; N ). The first kind of strategies are called "unary strategies" whereas the second one are denoted by "general strategies". In the last case, each term S n of the strategy can be represented by an integer lower than 2 N , designed by S n , for a system having N bits: the k th component of the system is updated at iteration number n if and only if the k th digit of the binary decomposition of S n is 1. For instance, let us consider that S n = 5, and that we iterate on a system having 6 bits (N = 6). As the integer 5 has a binary decomposition equal to 000101, we thus conclude that the cells number 1 and 3 will be updated when the system changes its state from x n to x n+1 . In other words, in that situation, S n = 5 ∈ 0, 2 6 -1 ⇔ S n = {1, 3} ⊂ 1, 6 . To sum up, to provide a general strategy of 1; N is equivalent to give an unary strategy in 0; 2 N -1 . Let us now take into account this remark.

Until now the proposed generators have been presented in this document by using unary strategies (obtained by the first inputted PRNG S ) that are finally grouped by "packages" (the size of these packages is given by the second generator m): after having used each terms in the current package S m n , ..., S m n+1 -1 , the current state of the system is published as an output. Obviously, when considering the new CI version, these packages of unary strategies defined by the couple (S , m) ∈ 1; N × 0; N correspond to subsets of 1; N having the form S m n , ..., S m n+1 -1 , which are general strategies. As stated before, these lasts can be rewritten as unary strategies that can be described as sequences in 0; 2 N -1 .

The advantage of such an equivalency is to reduce the complexity of the proposed PRNG. Indeed the new CI(S ,m) generator can be written as:

x n = x n-1 ∧ S n . ( 3
)
where S is the unary strategy (in 0; 2 N -1 ) associated to the couple (S , m) ∈ 1; N × 0, N . The speed improvement is obvious, the sole issue is to understand how to change (S , m) by S. The problem to consider is that all the sequences of 0; 2 n -1 are not convenient. Indeed, the properties required for the couple (S , m) (S must not be uniformly distributed, and a cell cannot be changed twice between two outputs) must be translated in requirements for S if we want to satisfy both speed and randomness. Such constrains are solved by working on the sequence m and by using some well-defined Lookup Tables presented in the following sections.

B. Sequence m

In order to improve the speed of the proposed generator, the first plan is to take the best usage of the bits generated by the inputted PRNGs. The problem is that the PRNG generating the integers of m n does not necessary takes its values into 0, N , where N is the size of the system.

For instance, in the new CI generator presented previously, this sequence is obtained by a XORshift, which produces integers belonging into 0, 2 32 -1 . However, the iterated system has 4 cells (N = 4) in the example proposed previously thus, to define the sequence m n , we compute the remainder modulo 4 of each integer provided by the XORshift generator. In other words, only the last 4 bits of each 32 bits vector generated by the second XORshift are used. Obviously this stage can be easily optimized, by splitting this 32-bits vector into 8 subsequences of 4 bits. Thus, a call of XORshift() will now generate 8 terms of the sequence m, instead of only one term in the former generator.

This common-sense action can be easily generalized to any size N 32 of the system by the procedure described in Algorithm 3. The idea is simply to make a shift of the binary vector a produced by the XORshift generator, by 0, N, 2N,... bits to the right, depending on the remainder c of n modulo N/32 (that is, a (N × c)), and to take the bits between the positions 32 -N and 32 of this vector (corresponding to the right part "&(2 N -1)" of the formula). In that situation, all the bits provided by XORshift are used when N divide 32.

Algorithm 3 Generation of sequence b n 1: c = n mod 32/N 2: if c = 0 then 3: a ← XORshi f t() 4: end if 5: b n ← (a (N × c))&(2 N -1) 6: Return b n
This Algorithm 3 produces a sequence (b n ) n∈N of integers belonging into 0, 2 N -1 . It is now possible to define the sequence m by adapting the Equation 2 as follows.

m n = f (b n ) =                        0 if 0 b n < C 0 N , 1 if C 0 N b n < 1 i=0 C i N , 2 if 1 i=0 C i N b n < 2 i=0 C i N , . . . . . . N if N-1 i=0 C i N b n < 2 N . (4)
This common-sense measure can be improved another time if N is not very large by using the first Lookup Table of this document, which is called LUT-1. This improvement will be firstly explained through an example.

Let us consider that N = 4, so the sequence (b n ) n∈N belongs into 0, 15 . The function f of Equation 4 must translate each b n into an integer m n ∈ 0, 4 , in such a way that the nonuniformity exposed previously is respected. Instead of defining the function f analytically, a table can be given containing all the images of the integers into 0, 15 (see Table I for instance). As stated before, the frequencies of occurrence of the images 0,1,2, 3, and 4 must be respectively equal to

C 0 4 2 4 , C 1 4 2 4 , C 2 4 2 4 , C 3 4 2 4 ,

and

C 4 4 2 4 . This requirement is equivalent to demand C i
N times the number i, which can be translated in terms of permutations. For instance, when N = 4, any permutation of the list [0,1,1,1,1,2,2,2,2,2,2,3,3,3,3,4] is convenient to define the image of [0,1,2,..., [START_REF][END_REF][START_REF] Marsaglia | Xorshift rngs[END_REF] by f . This improvement is implemented in Algorithm 4, which return a table lut1 such that m n = lut1[b n ].

Algorithm 4 The LUT-1 table generation

1: for j = 0...N do

2: i = 0 3: while i < C j N do 4: lut1[i] = j 5: i = i + 1 6:
end while 7: end for 8: Return lut1

m n 0 1 1 1 1 2 2 2 2 2 2 3 3 3 3 4
C. Defining the chaotic strategy S with a LUT The definition of the sequence m allows to determine the number of cells that have to change between two outputs of the LUT CI generator. There are C m N possibilities to change m bits in a vector of size N. As we have to choose between these C m N possibilities, we thus introduce the following sequence:

w n = XORshi f t2() mod C m N (5)
With this material it is now possible to define the LUT that provides convenient strategies to the LUT CI generator. If the size of the system is N, then this table has N + 1 columns, numbered from 0 to N. The column number m contains C m N values. All of these values have in common to present exactly m times the digit 1 and Nm times the digit 0 in their binary decomposition. The order of appearance of these values in the column m has no importance, the sole requirement is that no column contains a same integer twice. Let us remark that this procedure leads to several possible LUTs. end for 15: end if 16: End Procedure An example of such a LUT is shown in Table III, when Algorithm 6 gives a concrete procedure to obtain such tables. This procedure makes recursive calls to the function LUT 21 defined in Algorithm 5. The LUT 21 uses the following variables. b is used to avoid overlapping computations between two recursive calls, v is to save the sum value between these calls, and c counts the number of cells that have already been processed. These parameters should be initialized as 0. For instance, the LUT presented in Table III is the lut2 obtained in Algorithm 5 with N = 4.

D. LUT CI(XORshift,XORshift) Algorithm

The LUT CI generator is defined by the following dynamical system:

x Call LUT21(i, N, 0, 0, 0) 3: end for 4: Return lut2

n = x n-1 ∧ S n . ( 6
)
m 0 3 2 1 c 0 2 5 2 S 0 13 12 4 x 0 x 0 x 1 x 2 x 3 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 1 1 Binary Output: x 0 1 x 0 2 x 0 3 x 0 4 x 1 1 x 1 2 x 1 3 x 1 4 x 2 1 x 2 2 ... = 0100100101010001... Integer Output: x 0 , x 1 , x 2 , x 3 ... = 4, 11, 8, 1... TABLE IV EXAMPLE OF A LUT CI(XORSHIFT,XORSHIFT) GENERATION where x O ∈ 0, 2 N -1 is a seed and S n = lut2[w n ][m n ] = lut2[w n ][lut1[b n ]], in which b n is provided by Algorithm 3 and w n = XORshi f t2() mod C m
N . An iteration of this generator is written in Algorithm 7. Let us finally remark that the two inputted XORshift can be replaced by any other operating PRNG.

Algorithm 7 LUT CI (XORshift,XORshift) algorithm 1: c = n mod 32/N 2: if c = 0 then 3: a ← XORshi f t1() 4: end if 5: b n ← (a (N × c))&(2 N -1) 6: m n = lut1[b n ] 7: d n = XORshi f t2() 8: w n = b n mod C m N 9: S n = lut2[m][w] 10: x = x ∧ S n 11: Return x E. LUT CI(XORshift,XORshift) example of use
In this example, N = 4 is chosen another time for easy understanding. As before, the initial state of the system x 0 can be seeded by the decimal part t of the current time. With the same current time than in the examples exposed previously, we have x 0 = (0, 1, 0, 0) (or x 0 = 4).

Algorithm 4 provides the LUT-1 depicted in Table I. The first XORshift generator has returned y = 0, 11, 7, 2, 10, 4, 1, 0, 3, 9, .... By using this LUT, we obtain m = 0, 3, 2, 1, 2, 1, 1, 0, 1, 2, .... Then the Algorithm 6 is computed, leading to the LUT-2 given by Table III.

So chaotic iterations of Algorithm 7 can be realized, to obtain in this example: 0100100101010001... or 4,9,5,1...

IV. STATISTICAL ANALYSIS

In order to make a fair comparison, we decided to choose the best parameters for each generator. According to the experiments, these values are N = 4 for the old CI, N = 32 for the new one, and finally N = 8 for the LUT CI generator (see Sections IV-A, IV-B, and IV-C respectively). A. NIST

In our experiments, 100 sequences (s = 100) of 1,000,000 bits are generated and tested. If the value P T of any test is smaller than 0.0001, the sequences are considered to be not good enough and the generator is unsuitable. Table V shows P T of sequences based on discrete chaotic iterations using different schemes. If there are at least two statistical values in a test, this test is marked with an asterisk and the average value is computed to characterize the statistics. We can see in Table V that old, new, and LUT CI(XORshift, XORshift) generators have successfully passed the NIST statistical test suite. In particular, the score of the XORshift generator is better when this last is embedded into any of the three proposed scheme (indeed, XORshift alone fails one of the NIST tests).

B. Diehard

Table II gives the results derived from applying the DieHARD battery [START_REF] Marsaglia | Diehard: a battery of tests of randomness[END_REF] of tests to the PRNGs considered in this work. As it can be observed, all the generator presented in this document can pass the DieHARD battery of tests.

C. Comparative test parameters

We show in Table VI a comparison in comparative test parameters [START_REF] Wang | Randomness quality of CI chaotic generators. application to internet security[END_REF] among the generators LUT CI(XORshift, XORshift), New CI (XORshift, XORshift), their old version: Old CI(XORshift, XORshift), and a PRNG based on a simple XORshift. Time (in seconds) is related to the duration needed by each algorithm to generate a 2×10 8 bits long sequence. The test has been conducted using the same computer and compiler with the same optimization settings for both algorithms, in order to make it as fair as possible. The results confirm that the proposed LUT CI is the fastest CI PRNG, while the statistical results is better for most of the parameters, leading to the conclusion that this new PRNGs is more secure than the other ones.

In addition, a comparison of overall stability from 5 × 10 4 to 8 × 10 5 for these generators has been given in Figure 1. It can be seen that LUT CI and new CI are dominant in all, especially when the sequences are very long.

D. Varying the output size

The size of the outputs (N, in number of bits) produced by each of the proposed generators only depend on the size of the initial state x 0 . Moreover, as the "CI process" is fundamentally a negation of bits, the size of the system does not really impact the speed of these PRNGs, at least for reasonable values of N. As various N values can be relevant, depending on the application, we thus investigate whether the statistical performances of the CI generators are impacted when N changes.

We can show in Table VII that, for the three CI generators, various N lead to success for both the NIST and DIEHARD tests. Concerning the whole TestU01 [START_REF] Simard | Testu01: A software library in ansi c for empirical testing of random number generators[END_REF], various consequences can be dressed. Firstly, the LUT CI generator is unsuitable for N = 32, due to its too large consumption of memory resources when generating and using the LUTs. Secondly, this last generator is the only one capable to pass the whole TestU01 with only N = 4 cells. Finally, all the proposed generators have better scores than the XORshift they use.

E. Devaney's chaos property

Generally, the quality of a PRNG depends, to a large extent, on the following criteria: randomness, uniformity, independence, storage efficiency, and reproducibility. A chaotic sequence may satisfy these requirements and also other chaotic properties, as ergodicity, entropy, and expansivity. A chaotic sequence is extremely sensitive to the initial conditions. That is, even a minute difference in the initial state of the system can lead to enormous differences in the final state, even over fairly small timescales. Therefore chaotic sequences fit the requirements of pseudorandom sequences well. Contrary to XORshift, our generator possesses these chaotic properties [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF], [START_REF] Bahi | A novel pseudo-random generator based on discrete chaotic iterations[END_REF]. However, despite a large number of papers published in the field of chaos-based pseudorandom generators, the impact of this research is rather marginal. This is due to the following reasons: almost all PRNG algorithms using chaos are based on dynamical systems defined on continuous sets (e.g., the set of real numbers). So these generators are usually slow, requiring considerably more storage space and lose their chaotic properties during computations. These major problems restrict their use as generators [START_REF] Kocarev | Chaos-based cryptography: a brief overview[END_REF].

In this paper we don't simply integrate chaotic maps hoping that the implemented algorithm remains chaotic. Indeed, the PRNG we conceive is just discrete chaotic iterations and we have proven in [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF] that these iterations produce a topological chaos as defined by Devaney: they are regular, transitive, and sensitive to initial conditions. This famous definition of a chaotic behavior for a dynamical system implies unpredictability, mixture, sensitivity, and uniform repartition. Moreover, as only integers are manipulated in discrete chaotic iterations, the chaotic behavior of the system is preserved during computations, and these computations are fast.

V. APPLICATION EXAMPLE IN DIGITAL WATERMARKING

Information hiding has recently become a major information security technology, especially with the increasing importance and widespread distribution of digital media through the Internet [START_REF] Wu | A novel digital watermark algorithm based on chaotic maps[END_REF]. It includes several techniques like digital watermarking. The aim of digital watermarking is to embed a piece of information into digital documents, such as pictures or movies. This is for a large panel of reasons, such as: copyright protection, control utilization, data description, content authentication, and data integrity. For these reasons, many different watermarking schemes have been proposed in recent years. Digital watermarking must have essential characteristics, including: security, imperceptibility, and robustness. Chaotic methods have been proposed to encrypt the watermark before embedding it in the carrier image for these security reasons. In this paper, a watermarking algorithm based on the chaotic PRNG presented above is given, as an illustration of use of this family of CI PRNG.

A. Most and least significant coefficients

Let us first introduce the definitions of most and least significant coefficients. For example, in a spatial description of a grayscale image, a definition of MSCs can be the sequence constituted by the first three bits of each pixel as shown in Figure 2(b). In a discrete cosine frequency domain description, each 8 × 8 block of the carrier image is mapped to a list of 64 coefficients. The energy of the image is contained in the first of them. After binary conversion, the first fourth coefficients of all these blocks can constitute a possible sequence of MSCs. Definition 3 By least significant coefficients (LSCs), we mean a translation of some insignificant parts of a medium in a sequence of bits (insignificant can be understand as: "which can be altered without sensitive damages"). These LSCs can be for example, the last three bits of the gray level of each pixel, in the case of a spatial domain watermarking of a grayscale image, as in Figure 2(c). Discrete cosine, Fourier, and wavelet transform can be used to define LSCs and MSCs, in the case of frequency domain watermarking, among other possible choices. Moreover, these definitions are not limited to image media, but can easily be extended to the audio and video media as well. LSCs are used during the embedding stage: some of the least significant coefficients of the carrier image will be chaotically chosen and replaced by the bits of the mixed watermark. With a large number of LSCs, the watermark can be inserted more than once and thus the embedding will be more secure and robust, but also more detectable. The MSCs are only useful in the case of authentication: encryption and embedding stages depend on them. Hence, a coefficient should not be defined at the same time, as a MSC and a LSC; the last can be altered, while the first is needed to extract the watermark.

B. Stages of the algorithm

Our watermarking scheme consists of two stages: (1) mixture of the watermark and (2) its embedding.

1) Watermark mixture: Firstly, for safety reasons, the watermark can be mixed before its embedding into the image. A common way to achieve this stage is to use the bitwise exclusive or (XOR), for example, between the watermark and the above PRNG. In this paper, we will use another mixture scheme based on chaotic iterations. Its chaotic strategy, defined with our PRNG, will be highly sensitive to the MSCs, in the case of an authenticated watermark, as stated in [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF].

2) Watermark embedding: Some LSCs will be substituted by all bits of the possibly mixed watermark. To choose the sequence of LSCs to be altered, a number of integers, less than or equal to the number N of LSCs corresponding to a chaotic sequence U k k , is generated from the chaotic strategy used in the mixture stage. Thus, the U k -th least significant coefficient of the carrier image is substituted by the k th bit of the possibly mixed watermark. In the case of authentication, such a procedure leads to a choice of the LSCs which are highly dependent on the MSCs. For the detail of this stage see Section VI-A2.

3) Extraction: The chaotic strategy can be regenerated, even in the case of an authenticated watermarking because the MSCs have not been changed during the stage of embedding the watermark. Thus, the few altered LSCs can be found, the mixed watermark can then be rebuilt, and the original watermark can be obtained. If the watermarked image is attacked, then the MSCs will change. Consequently, in the case of authentication and due to the high sensitivity of the embedding sequence, the LSCs designed to receive the watermark will be completely different. Hence, the result of the recovery will have no similarity with the original watermark: authentication is reached.

VI. EVALUATION OF THE PROPOSED SCHEME

In this section, a complete application example of the above chaotic watermarking method is given and its robustness to some attacks is studied. This case study enables us to precise the details of the algorithm and evaluate it.

A. Stages and details 1) Images description: Carrier image is Lena, a 256 grayscale image of size 256 × 256 (see Figure 2(a)). The watermark is the 64×64 pixels binary image depicted in Figure 3(a). The embedding domain will be the spatial domain. The selected MSCs are the four most significant bits of each pixel and the LSCs are the three last bits (a given pixel will at most be modified of four levels of gray by an iteration). Before its embedment, the watermark is mixed with chaotic iterations. The system to iterate, chaotic strategy S n and iterate function are defined below.

2) Embedding of the watermark: To embed the watermark, the sequence (U k ) k∈N of altered bits taken from the M LSCs must be defined. To do so, the strategy (S k ) k∈N of the encryption stage is used as follows:

U 0 = S 0 U n+1 = S n+1 + 2 × U n + n (mod M) (7)
to obtain the result depicted in Figure 4(b). The map θ → 2θ of the torus, which is a famous example of topological Devaney's chaos [START_REF] Devaney | An Introduction to Chaotic Dynamical Systems[END_REF], has been chosen to make (U k ) k∈N highly sensitive to the chaotic strategy (S k ) k∈N . As a consequence, (U k ) k∈N is

B. Robustness results

To prove the efficiency and the robustness of the proposed algorithm, some attacks are applied to our chaotically watermarked image. For each attack, a similarity percentage with the original watermark is computed. This percentage is the number of equal bits between the original and the extracted watermark, shown as a percentage. A result less than or equal to 50% implies that the image has probably not been watermarked.

1) Cropping attack: In this kind of attack, a watermarked image is cropped. In this case, the results in Table VIII have been obtained. In Figure 4, the decrypted watermarks are shown after a crop of 50 pixels and after a crop of 10 pixels, in the authentication case. By analyzing the similarity percentage between the original and the extracted watermark, we can conclude that in the case of unauthentication, the watermark still remains after a cropping attack. The desired robustness is reached. It can be noticed that cropping sizes and percentages are rather proportional. In the case of authentication, even a small change of the carrier image (a crop by 10 × 10 pixels) leads to a really different extracted watermark. In this case, any attempt to alter the carrier image will be signaled, thus the image is well authenticated.

2) Rotation attack: Let r θ be the rotation of angle θ around the center (128, 128) of the carrier image. So, the transformation r -θ •r θ is applied to the watermarked image. The results in Table VIII have been obtained. The same conclusion as above can be declaimed.

3) JPEG compression: A JPEG compression is applied to the watermarked image, depending on a compression level. This attack leads to a change of the representation domain (from spatial to DCT domain). In this case, the results in Table VIII have been obtained, illustrating a good authentication through JPEG attack. As for the unauthentication case, the watermark still remains after a compression level equal to 10. This is a good result if we take into account the fact that we use spatial embedding.

4) Gaussian noise: A watermarked image can be also attacked by the addition of a Gaussian noise, depending on a standard deviation. In this case, the results in Table VIII are obtained.

C. Security study of the proposed information hiding scheme

For the sake of completeness, and to show the effectiveness of the method, we will now introduce two other strategies different from the one given in Eq. 7. The proposed scheme will be rewritten too, in order to give a more theoretical evaluation of the security of the proposed information hiding algorithm.

1) Reformulation of the scheme: Let us consider the phase space X = 1; N N × B N and the map G f (S , E) = σ(S ), F f (i(S ), E) , where σ is defined by σ : (S n ) n∈N ∈ S → (S n+1 ) n∈N ∈ S, and i is the map i : (S n ) n∈N ∈ S → S 0 ∈ 1; N . Using this rewriting of the chaotic iterations presented previously, let:

• (K, N) ∈ [0; 1] × N be an embedding key, • X ∈ B N be the N least significant coefficients (LSCs) of a given cover media C, • (S n ) n∈N ∈ 1, N N be a strategy, which depends on the message to hide M ∈ [0; 1] and K, • f 0 : B N → B N be the vectorial logical negation. So the watermarked media is C whose LSCs are replaced by Y K = X N , where [START_REF] Friot | Chaotic iterations for steganographystego-security and chaos-security[END_REF]:

X 0 = X ∀n < N, X n+1 = G f 0 (X n ) .
2) New examples of strategies: a) CIIS strategy: Let us first introduce the Piecewise Linear Chaotic Map (PLCM, see [START_REF] Shujun | Statistical properties of digital piecewise linear chaotic maps and their roles in cryptography and pseudo-random coding[END_REF]), defined by: Definition 4 (PLCM)

F(x, p) =            x/p if x ∈ [0; p] (x -p)/( 1 2 -p) if x ∈ p; 1 2 F(1 -x, p) else.
where p ∈ 0; 1 2 is a "control parameter". Then, we can define the general term of the strategy (S n ) n in Chaotic Iterations with Independent Strategy (CIIS) setup by the following expression: S n = N × K n + 1, where:

           p ∈ 0; 1 2 K 0 = M ⊗ K K n+1 = F(K n , p), ∀n ≤ N 0
in which ⊗ denotes the bitwise exclusive or (XOR) between two floating part numbers (i.e., between their binary digits representation). Lastly, to be certain to enter into the chaotic regime of PLCM [START_REF] Shujun | Statistical properties of digital piecewise linear chaotic maps and their roles in cryptography and pseudo-random coding[END_REF], the strategy can be preferably defined by: S n = N × K n+D + 1, where D ∈ N large enough: we thus iterate the PLCM a certain number of times before taking terms of the strategy.

b) CIDS strategy: The same notations as above are used. We define Chaotic Iterations with Dependent Strategy (CIDS) strategy as follows: ∀k N,

• if k N and X k = 1, then S k = k, • else S k = 1. In this situation, if N N, then only two watermarked contents are possible with the scheme proposed previously, namely: Y K = (0, 0, • • • , 0) and Y K = (1, 0, • • • , 0). Indeed, in CIIS, the strategy is independent from the cover media X, whereas in CIDS the strategy will be dependent on X.

3) Evaluation of the stego-security: Let K be the set of embedding keys, p(X) the probabilistic model of N 0 initial host contents, and p(Y|K 1 ) the probabilistic model of N 0 watermarked contents. We suppose that each host content has been watermarked with the same key K 1 and the same embedding function e.

Definition 5

The embedding function e is stego-secure if and only if [START_REF] Cayre | Kerckhoffs-based embedding security classes for woa data hiding[END_REF]: ∀K 1 ∈ K, p(Y|K 1 ) = p(X).

Let us now study the stego-security of the scheme. We will prove that, Proposition 1 The information hiding scheme using the CIIS strategy is stego-secure, whereas CIDS is not stego-secure.

Proof: Let us suppose that X ∼ U B N in a CIIS setup. We will prove by a mathematical induction that ∀n ∈ N, X n ∼ U B N . The base case is immediate, as X 0 = X ∼ U B N . Let us now suppose that the statement X n ∼ U B N holds for some n. Let e ∈ B N and B k = (0, • • • , 0, 1, 0, • • • , 0) ∈ B N (the digit 1 is in position k). So P X n+1 = e = N k=1 P (X n = e + B k , S n = k) . These two events are independent in CIIS setup, thus: P X n+1 = e = N k=1 P (X n = e + B k ) × P (S n = k). According to the inductive hypothesis: P X n+1 = e = 1 2 N N k=1 P (S n = k). The set of events {S n = k} for k ∈ 1; N is a partition of the universe of possible, so N k=1 P (S n = k) = 1. Finally, P X n+1 = e = 1 2 N , which leads to X n+1 ∼ U B N . This result is true ∀n ∈ N, we thus have proven that, ∀K ∈ [0; 1], Y K = X N 0 ∼ U B N when X ∼ U B N , which concludes the first claim of the proposition. Let us now prove the second part of it.

Due to the definition of CIDS, we have P(Y K = (1, 1, • • • , 1)) = 0. So there is no uniform repartition for the stego-contents Y K .

VII. CONCLUSION AND FUTURE WORK

In this paper, the pseudorandom generator proposed in our previous works has been improved in terms of speed and randomness. By using some well-defined Lookup Tables and due to a rewrite of the way to generate strategies, the generator based on chaotic iterations works faster and is more secure. The speed and randomness of this new LUT CI PRNG has been compared to its former versions and to XORshift. This comparison shows that LUT CI(XORshift, XORshift) offers a sufficient speed and level of security for a whole range of Internet usages as cryptography and data hiding. This generator has been used to develop a scheme in the information hiding domain, whose robustness and security has been detailed in the previous section. Further readings about the security of such a chaos-based watermarking scheme can be found in, e.g., [START_REF] Bahi | Lyapunov exponent evaluation of a digital watermarking scheme proven to be secure[END_REF], [START_REF] Bahi | Steganography: a class of algorithms having secure properties[END_REF].

In future work, we will continue to explore new strategies and iteration functions. Its chaotic behavior will be deepened by using the various tools provided by the mathematical theory of chaos. New statistical tests will be used to compare this PRNG to existing ones. Additionally a probabilistic study of its security will be done. Lastly, new applications in computer science will be proposed, especially in the Internet security field.

Algorithm 5

 5 LUT 21 procedure 1: Procedure LUT21(M, N, b, v, c) 2: count ← c 3: value ← v 4: if count == M then 5: lut2[M][num] = value 6: num = num + 1 7: else 8: for i = b....N do 9: value = value + 2 i 10: count = count + 1 11:Call recurse LUT21(M, N, i + 1, value, count)

Algorithm 6

 6 LUT-2 generation 1: for i = 0....N do 2:

  m = 1 m = 2 m = 3 m = 4

Definition 2

 2 For a given image, the most significant coefficients (in short MSCs), are coefficients that allow the description of the relevant part of the image, i.e. its most rich part (in terms of embedding information), through a sequence of bits.

Fig. 2 .

 2 Fig. 2. Spatial MSCs and LSCs of Lena

Fig. 1 .

 1 Fig. 1. Overall Sequence Stability Comparison

Fig. 3 .

 3 Fig. 3. Watermarked Lena and differences

Fig. 4 .

 4 Fig. 4. Extracted watermark after a cropping attack (zoom ×2)

TABLE I A

 I

TABLE FOR N

 FOR = 4

	b n	0	1 2 3 4	5 6 7 8 9	10 11 12	13 14 15

TABLE VI COMPARISON

 VI BETWEEN THE PRESENTED PRNGS FOR A 2 × 10 8 BITS

		SEQUENCE
	Methods	XORshift	Old CI	New CI	LUT CI
	Monobit	0.6055	0.5689	0.0029	0.0471
	Serial	0.7021	1.5765	0.3845	0.2232
	Poker	7.957	6.3683	5.882	5.166
	RunS	26.1022	28.4237	24.8094	21.9861
	Autocorrelation	1.1628	0.3403	1.4220	0.4410
	Time	9.33s	49.55s	28.82s	11.24s


Jacques M Bahi
email: jacques.bahi@femto-st.fr

Christophe Guyeux
email: christophe.guyeux@femto-st.fr

Kamel Mazouzi
email: kamel.mazouzi@univ-fcomte.fr

Laurent Philippe
email: laurent.philippe@femto-st.fr

Computational investigations of folded self-avoiding walks related to protein folding

Keywords: Self avoiding walks, protein folding, protein structure prediction

  L'archive ouverte pluridisciplinaire

Introduction

Self-avoiding walks (SAWs) have been studied over decades for the extent and difficulty of the mathematical problems they provide [START_REF] Madras | The pivot algorithm: A highly efficient monte carlo method for the self-avoiding walk[END_REF][START_REF] Bacher | Weakly directed self-avoiding walks[END_REF][START_REF] Beaton | Some new selfavoiding walk and polygon models[END_REF], and for their various contexts of application in physics, chemistry, and biology [START_REF] Slade | The self-avoiding walk: a brief survey[END_REF][START_REF] De Gennes | Exponents for the excluded volume problem as derived by the Wilson method[END_REF][START_REF] Flory | The Configuration of Real Polymer Chains[END_REF]. Among other things, they are used to model polymers such as DNA, RNAs, and proteins. Numerous protein structure prediction (PSP) software iterate on selfavoiding walk subsets, often not clearly defined, of various lattices. The last produced SAW S has the length of the targeted protein P. When labeling S with the amino acids of P, S is (one of) the best solution(s) according to a scoring function that associates a value to a 2D or 3D conformation (depending on physical properties of the conformation as hydrophobic neighboring residues, etc.).

In previous studies [START_REF] Guyeux | Is protein folding problem really a NP-complete one? first investigations[END_REF][START_REF] Bahi | Protein folding in the 2D hydrophobic-hydrophilic (HP) square lattice model is chaotic[END_REF][START_REF] Bahi | Chaos of protein folding[END_REF], authors of this manuscript have investigated some dynamic protein folding models. They have shown that the possible sets of conformations reachable by these numerous PSP software are not equal. This raises severe questionings on what is indeed really predicted by such software. In particular, they have shown that software that iteratively stretch the conformation from one amino acid until a self-avoiding walk having the length n of the protein, can reach all the n-step SAWs G n . Contrarily, the ones that iterate ±90 • pivot moves on the n-step straight line can only reach what they call the subset of folded self-avoiding walks f SAW(n). It has been clearly established that, for some well-defined small n's, f SAW(n) G n . After having obtained this result, the authors' intention was then to investigate more deeply these new kind of self-avoiding walks and other related subsets of walks they called unfolded SAWs, and to determine consequences of these investigations regarding the protein structure prediction problem.

This article is the third of a series of three researches we publish in that field. In [START_REF] Bahi | Protein structure prediction software generate two different sets of conformations. Or the study of unfolded self-avoiding walks[END_REF] we provide a general presentation of folded and unfoldable SAWs, and the collection of results we have obtained on these objects using both theoretical and computational approaches. Article [START_REF] Bahi | Consequences for the protein structure prediction problem[END_REF] focuses more specifically on the mathematical study of theses subsets of self-avoiding walks, by proving in particular that the number of unfolded SAWs is infinite. This article presents our computational investigations in detail.

After recalling in the next section the basis of self-avoiding walks, of folded SAWs, and of unfoldable SAWs, we explain in Section 3 how the number of folded self-avoiding walks has been computed and how we checked the unfoldable property in practice. The various methods that have been implemented to find the shortest currently known unfoldable SAW are presented too in this section. Then, in Section 4, some heuristics that could be determinant in further studies concerning these subsets of walks are introduced. The next section contains the last contribution of this research work: a free software realized to facilitate the study of folded and unfoldable SAWs. This document ends by a conclusion section, in which all these contributions are summarized and intended future work is proposed.

Presentation of Folded Self-Avoiding Walks

We recall in this section various notions and properties of self-avoiding walks and of some of theirs folded subsets: folded SAWs obtained by iterating pivot moves on the straight line and unfoldable SAWs on which no pivot move can be applied without breaking the self-avoiding property. Authors that would investigate more deeply these walks are referred to [START_REF] Madras | The self-avoiding walk, Probability and its applications[END_REF][START_REF] Slade | The self-avoiding walk: a brief survey[END_REF][START_REF] Hughes | Random walks and random environments[END_REF] for the SAWs in general, and to [START_REF] Bahi | Protein structure prediction software generate two different sets of conformations. Or the study of unfolded self-avoiding walks[END_REF][START_REF] Bahi | Consequences for the protein structure prediction problem[END_REF] for the folded case.

Definitions and Terminologies

Let N be the set of all natural numbers, N * = {1, 2, . . .} the set of all positive integers, and for a, b ∈ N, a b, the notation a, b stands for the set {a, a + The n-th term of a sequence s is denoted by s(n). Finally, ♯X is the cardinality of a finite set X. Using this material, self-avoiding walk can be defined as follows [START_REF] Madras | The self-avoiding walk, Probability and its applications[END_REF][START_REF] Slade | The self-avoiding walk: a brief survey[END_REF][START_REF] Hughes | Random walks and random environments[END_REF].

Definition 1 (Self-Avoiding Walk) Let d 1. A n-step self-avoiding walk from x ∈ Z d to y ∈ Z d is a map w : 0, n → Z d with:

• w(0) = x and w(n) = y,

• |w(i + 1) -w(i)| = 1,
• ∀i, j ∈ 0, n , i j ⇒ w(i) w( j) (self-avoiding property).

Notations

In absolute encoding [START_REF] Hoque | Genetic algorithm in ab initio protein structure prediction using low resolution model: A review[END_REF][START_REF] Backofen | Algorithmic approach to quantifying the hydrophobic force contribution in protein folding[END_REF], a n-step walk w = w(0), ..., w(n) ∈ Z 2 n+1 with w(0) = (0, 0) is a sequence s = s(0), ..., s(n -1) of elements belonging into Z/4Z, such that:

• s(i) = 0 if and only if w(i + 1) 1 = w(i) 1 + 1 and w(i + 1) 2 = w(i) 2 , that is, w(i + 1) is at the East of w(i).
• s(i) = 1 if and only if w(i + 1) 1 = w(i) 1 and w(i + 1) 2 = w(i) 2 -1: w(i + 1) is at the South of w(i).

• s(i) = 2 if and only if w(i + 1) 1 = w(i) 1 -1 and w(i + 1) 2 = w(i) 2 , meaning that w(i + 1) is at the West of w(i).

• Finally, s(i) = 3 if and only if w(i + 1) 1 = w(i) 1 and w(i + 1) 2 = w(i) 2 + 1 (w(i + 1) is at the North of w(i)).

Let us now define the following functions [START_REF] Guyeux | Is protein folding problem really a NP-complete one? first investigations[END_REF].

Definition 2

The anticlockwise fold function is the function f : Z/4Z -→ Z/4Z defined by f (x) = x -1 (mod 4) and the clockwise fold function is f -1 (x) = x + 1 (mod 4).

Using the absolute encoding sequence s of a n-step SAW w that starts from the origin of the square lattice, a pivot move of +90°on w(k), k < n, simply consists to transform s into s(0), . . . , s(k -1), f (s(k)), . . . , f (s(n)). Similarly, a pivot move of -90°consists to apply f -1 to the queue of the absolute encoding sequence, like in Figure 2.

A graph structure for SAWs folding process

We can now introduce a graph structure that fits the description of iterations for ±90°pivot moves on a given self-avoiding walk.

Given n ∈ N * , the graph G n , formerly introduced in [START_REF] Guyeux | Is protein folding problem really a NP-complete one? first investigations[END_REF], is defined as follows:

• its vertices are the n-step self-avoiding walks, described in absolute encoding;

• there is an edge between two vertices s i , s j if and only if s j can be obtained by one pivot move of ±90°on s i , that is, if there exists k ∈ 0, n -1 s.t.:

either s j (0), . . . , s j (k -1), f (s j (k)), . . . , f (s j (n)) = s i or s j (0), . . . , s j (k -1), f -1 (s j (k)), . . . , f -1 (s j (n)) = s i .

Such a digraph is depicted in Figure 3. The circled vertex is the straight line whereas strikeout vertices are walks that are not self-avoiding. Depending on the context, and for the sake of simplicity, G n will also refers to the set of SAWs in G n (i.e., its vertices). Using this graph, the folded SAWs introduced in the previous section can be redefined more rigorously. Definition 3 f SAW n is the connected component of the straight line 00 . . . 0 (n times) in G n , whereas S n is constituted by all the vertices of G n .

The Figure 1 shows that the connected component f SAW(223) of the straight line in G 223 is not equal to the whole graph: G 223 is not connected. More precisely, this graph has a connected component of size 1: it is unfoldable whereas the SAW of Fig. 4 can be folded exactly once. Indeed, to be in the same connected component is an equivalence relation R n on G n , ∀n ∈ N * , and two SAWs w, w ′ are considered equivalent (with respect to this equivalence relation) if and only if there is a way to fold w into w ′ such that all the intermediate walks are self-avoiding. When existing, such a way is not necessarily unique.

These remarks lead to the following definitions.

(a) 000111

(b) 001222 = 00 f -1 (0) f -1 (1) f -1 (1) f -1 (1)
Figure 2: Effects of the clockwise fold function applied on the four last components of an absolute encoding.

Definition 4 Let n ∈ N * and w ∈ S n . We say that:

• w is unfoldable if its equivalence class, with respect to R n , is of size 1;

• w is a folded self-avoiding walk if its equivalence class contains the n-step straight walk 000 . . . 0 (n -1 times);

• w can be folded k times if a simple path of length k exists between w and another vertex in the same connected component of w.

Moreover, we introduce the following sets:

• f SAW(n) is the equivalence class of the n-step straight walk, or the set of all folded SAWs.

• f SAW(n, k) is the set of equivalence classes of size k in (G n , R n ).

• USAW(n) is the set of equivalence classes of size 1 (G n , R n ), that is, the set of unfoldable walks.

• f 1 SAW(n) is the complement of USAW(n) in G n .

6

♯G n of all possible SAWs has been computed until n = 71 is not the goal of this article. Let us just remark that they have rewritten the generating function for SAWs on the lattice using 5 irreducible components, whose generating functions are easier to calculate (see Formula 2.17 of [START_REF] Conway | Algebraic techniques for enumerating self-avoiding walks on the square lattice[END_REF]). These irreducible components are obtained by considering projections of walks onto the y axis, and classify irreducible segments by the number of y bonds they span. The obtained cardinality of G n , is recalled in Table 2 for n 31. For further detail, the reader is referred to [START_REF] Conway | Algebraic techniques for enumerating self-avoiding walks on the square lattice[END_REF].

Authors of this research work have tried to adapt this very interesting approach by searching a way to decompose the generating function of folded self-avoiding walks in other generating functions easier to calculate. The way to take into account pivot moves that define such folded SAWs however has not yet been discovered. This is why the algebraic method has been abandoned after unsuccessful attempts to the benefit of a constructive brute force approach detailed in the following sections.

At each of our investigations, a draft program in Python language has been released first, to test rapidly the correctness of the approach. This code has been translated in an optimized C program and deployed on the supercomputer facilities of the Mésocentre de calcul de Franche-Comté. For readability and compactness, only the python programs are presented thereafter.

Preliminaries

Python function called walks (Listing 5) produces the list of all possible nstep walks as follows: the n-step walks are the walks of length n -1 with 0, 1, 2, or 3 added to their tails (recursive call). The return is a list of walks, that is, a list of integers lists. To obtain the walks belonging into G n , we first introduce the function points which aim is to produce the list of points (two coordinates) of the square lattice that corresponds to a given walk C. The encodes function that encodes a walk described as a list of points in its absolute encoding is provided in Listing 6 with its decodes associated function.

On Listing 7, Function is_saw returns a Boolean: it is true if and only if the walk C satisfies the self-avoiding property. To do so, the list of its points in the lattice (its support) is produced, and it is regarded whether this list contains Function saws produces a generator. It returns the next SAW at each call of the next method on the generator. To do so, an exhaustive iteration of the list produced by walks is realized, and the is_saw function is applied to each element of this list, to test if this walk is self-avoiding. These functions have been written and optimized in C language.

def encodes ( p o i n t s ) : L = [ ] f o r k in range ( 1 , l e n ( p o i n t s ) ) : i f p o i n t s [ k -1][0]== p o i n t s [ k ] [ 0 ] : i f p o i n t s [ k -1 ] [ 1 ] < p o i n t s [ k ] [ 1 ] : L . append (

A backtracking method to discover unfoldable walks

The folding property is checked thanks to the functions given on Listing 8. All the possible pivot moves (either in the clockwise direction, or in the anticlockwise) are checked to determine if a self-avoiding walk is unfoldable. The fold function tests, considering a given walk, a pivot move on residue number position following the given direction (+1 or -1, if clockwise or not). Function is_unfoldable applies the fold function to each residue of the candidate, Listing 9 details how to enumerate walks in f 1 SAW(n) (the complement of USAW(n)) by constructing with a backtracking method all the k-step walks for k lower than a given threshold n, and increasing a counter at each time the walk is not unfoldable and of length n. The factor 4 at the end of the program is necessary as we always consider the first step of these walks to be 1 (South). Backtracking method of Listing 9 has been translated in C language, optimized, paralleled, and launched on the supercomputer facilities (at each time, SAWs are separated over available processors using MPI routines) as follows.

A first version of the program, with the print line above turned as non commented, has been launched with N = 14 and N = 20. By doing so, all the walks of G N that start in the East direction have been obtained (for N = 20, they represent 224424291 walks stored in 3 gigabytes of data). Then each of these |G N |/4 self-avoiding walks has been the starting point of another backtracking discovery until n > N, and the unfoldable property of each of these n-step walk has been finally tested. This systematic approach as been successively launched until reaching n = 28, see Table 2. For (N, n) = (20, 28), 64 processors have been used during 70 hours in order to test the unfoldable property of 2351378582244 28-step self-avoiding walks, whereas no result has been obtained after 20 days of computation using the same facilities with (N, n) = (28, 30). We can summarize these results as follows.

Proposition 1 ∀n 28, f 1 SAW(n) = G n .

Investigating the f SAW(n) set

In the previous section, self-avoiding walks that can be folded at least once have been enumerated. That is, the cardinality of f 1 SAW(n) has been obtained for n 28. A breadth first search is now presented to show how G n = f SAW(n) has been obtained for n 14. The graph structure used in the Python draft program has been provided by the networkx library [START_REF] Hagberg | Exploring network structure, dynamics, and function using NetworkX[END_REF], which is thus imported in the first line of Listing 10. The graph G representing G(n) is instantiated in the first line of Listing 12, and the three following lines of this listing adds the node of the n-step straight line, shown as a word of n zeros. The association between relative encoding of a n-step walk described as an integer list and words on the alphabet {0, 1, 2, 3} of length n in the nodes of G is provided by function toString of Listing 10.

Let us recall that there is an edge between two nodes in G if and only if the SAW of the second node can be obtained by a pivot move on the first walk. This pivot moves is realized on the integer lists of the relative encoding of the walk using the fold function presented in the previous section. This latter must Figure 11: The breadth first search explore function be adapted a little, to match with the fact that G contains words (not lists of integers). This adaptation is also given in Listing 10.

Then the whole connected component of the straight line is constructed using a breadth first search approach: at each iteration, the list of new walks that result from a fold on the last added nodes is obtained (with function explore of Listing 11) and required connections are provided between last added walks and new discovered ones. The main issue in this approach is to prevent from visiting twice a given node, which is verified with the G.has_node method. More precisely, given a last added node, function explore realizes a one depth exploration starting from this node, adds the new discovered nodes to G with related edges, and returns G with the list of these new nodes x. This x is used in Listing 12 to constitute the next depth of exploration.

In search of the shortest unfoldable self-avoiding walks

The current smallest unfoldable self-avoiding walk is a 107-step walk, as depicted in Figure 13. The production of this counterexample and the systematic exploration of the connected component of the straight walk of G n for small n's presented previously allows us to claim that (see Table 2 The key idea leading to our first discovery of an unfoldable self-avoiding walk is represented in Figure 14(a): a SAW constituted by two sub-walks that both fill almost 50% of a disc (approximately the same radius for the two subwalks), when concatenated, can lead to an unfoldable self-avoiding walk if:

• when superposed, they fill almost 100% of the disc,

• the extremities of the concatenated walks are near the center of the superposed disc.

Additionally, it is required that the first sub-walk ends itself by visiting its boundary circle whereas the second sub-walk starts by visiting this circle (more precisely, an equivalent circle with a slight different radius). These two subwalks have been obtained by following two closed spiral trajectories in the opposite direction. By this way, no pivot move should be realized without breaking the selfavoiding property. Indeed, due to the compactness of the resulting walk having the form of a disc, no pivot move should be achieved inside the disc, whereas a pivot move at its bounds (the circle) separates the whole disc in two overlapping ones, as depicted in Figure 14(a). A first realization of such an unfoldable SAW is shown in Figure 14(b).

After obtaining our first unfoldable self-avoiding walks, the second stage was to reduce their number of steps by removing the central part of the discs and reducing, bit by bit, its radius. The first operation has been realized by removing the head of the first sub-walk and the tail of the second one, whereas the second operation consists in removing the end (resp., the beginning) of the spirals mentioned above. After having found a self-avoiding walk having the form of a smaller disc, the use of the backtracking program of Listing 9 has often been required to make this SAW as unfoldable. 1840 unfoldable self-avoiding walks have been discovered by doing so, a few of them being represented in Table 1, while they are counted according to their number of steps in Table 2.

A second approach to obtain unfoldable SAWs is to take a compact unfoldable SAW bounded by a kind of circle, and to extend it by two connected spirals covered in opposite direction, as depicted in Figure 15. A proof of the correctness of this approach, leading to an infinite number of unfoldable self-avoiding walks, is detailed in [START_REF] Bahi | Consequences for the protein structure prediction problem[END_REF]. However, as by this extension-based method it is obviously impossible to obtain the shortest unfoldable self-avoiding walk, such an approach will not be discussed in detail in this research work (for further details about this approach, the reader is referred to [START_REF] Bahi | Consequences for the protein structure prediction problem[END_REF]).

Toward Heuristic Approaches

A first quite optimistic heuristic method to discover smaller unfoldable self-avoiding walks is to follow a Monte-Carlo approach, as described in what follows. Starts first with the origin (0, 0), then at each iteration:

1. Pick randomly a stretching direction among the {0, 1, 2, 3} set. 2. If it is possible to extend the current walk in that direction while preserving the self-avoiding property, then:

• do the extension;

• if the obtained walk has the targeted number of steps, then tests if it is unfoldable. the next one is picked in {0, 1, 3}, as direct reversals are banished to preserve the self-avoiding property.

An implemented improvement of this Monte-Carlo based approach for finding unfoldable self-avoiding walks is to consider that such walks are perhaps more compact than other SAWs, as any pivot move must meet the tail of the structure. To take benefits of such an assessment, assuming that to be true, we have required in a new version of the Monte-Carlo program that the walks must stay in a N × N lattice, restarting the process at each time a SAW has an height or a width exceeding N. We have experimentally limited the lattice to a square of size 13 × 13 and to self-avoiding walks having a number of steps lower than 100. However, no smaller unfoldable SAW has been discovered after 15 days of computation on the supercomputer facilities.

Remark that a second version of the backtracking algorithm has been written too, to take into account restrictive N×N square lattices. However, this program has not allow the author's to discover smaller unfoldable self-avoiding walks than the one depicted in Figure 13.

Other investigated approaches encompass stretching method presented in Figure 16, the computing of the fact that the extremities of the walk should be closed one to each other, and an adaptable probability distribution of the stretching direction set {0, 1, 2, 3} for favoring the ones that stretch the walk in the center of the walk. They all have lead to a failure in discovering shorter unfoldable self-avoiding walks.

PySAW software

To investigate folded and unfoldable self-avoiding walks, we have developed a Python [18] interface hosted in https://code.google.com/p/pysaw Figure 15: Generating walks that cannot be folded out and freely available2 . The interface is depicted in Figure 17 and its current functionality is detailed below. The interface is divided in four parts: a sandbox where the SAW is drawn, two frames for configuration and backtracking, and the relative encoding of the depicted self-avoiding walk at the bottom of the window. A menu bar with common File, Edit, and Help items completes the interface.

n ♯G n ♯ f 1 SAW(n) ♯USAW(n) = ♯ f 1 SAW(n) ♯ f SAW(n) 1 4
In the sandbox frame, is is possible to construct a SAW step by step by using arrow keys (left, right, up, bottom). The initial vertex is the black square while the green square represents the last vertex. Other vertices and the remainder of the walk are represented in blue. A vertex V is represented by a circle when at least one of the two ±90 • pivot moves on V leads to a new walk Figure 16: Yet another stretching method satisfying the self-avoiding property, whereas it is a square when this vertex is unfoldable. Intersections in the walk, for its part, are depicted by a red square, as represented in Figure 17.

Various modification capabilities of the depicted walk have been added. Del key removes the last vertex whereas Back Space one deletes the first vertex. An item in the Edit menu allows the deletion of a sub-walk between two vertices selected by the right mouse button: the two remainder sub-walks are then concatenated. The Edit menu contains also an item that reverses the walk (maps w(0)...w(n) in w(n)...w(0). A click on the left mouse button on a vertex realizes a +90 • pivot move on this point whereas a right click makes a pivot move in the reverse direction. Another computed facility is the capability to extend a walk between two points by a right button drag-and-drop: the walk between the two extremities (vertices) of this drag-and-drop is replaced by the walk of the mouse motion. Control-s is a fast save of the walk in length.txt file, while Control-q quit the program. Finally, Control-z combination undoes the last modification whereas Control-Z redoes it. Let us remark that, at each modification, the relative encoding of the walk provided at the bottom of the window is naturally updated.

The representation of the walk in the sandbox can be altered by two check boxes in the Configuration panel. The Vertices check box enables or not the representation of the vertices as circles. When enabled, a second check box entitled "Unfoldable" enables the computation of each vertex: unfoldable (square) or not (circle). In Figure 17 this check box is enabled whereas it is disabled in Figure 18. To disable this check box is a necessity for very long walks, due to computation time. Another check box specifies if origin and axes must be represented in the sandbox (the origin can be changed in the Edit menu). Other information represented in the Configuration panel are the number of steps of the walk (length), its width and height, its number of intersections and of unfoldable vertices. Such information is used when representing the walk. Indeed, when the check box "Figure adaptation" is enabled, then the representation of the walk is modified in such a way that this walk is always contained in the frame: the length of the step and the position of the walk are adapted to the frame, depending on the width and height of the walk. If not enabled, the walk can goes outside the frame during a pivot move (for instance), which can be desired to understand the effects of a given pivot move: the head of the The position of the mouse is given too in the Configuration panel, depending on the chosen origin. Initially, this origin is set to the first node of the walk but, as stated before, it is possible to change it using New origin of the Edit menu. When the mouse is positioned on a vertex w(k) of the walk, its position k is informed in parenthesis and, if the "Show future intersection" check box is enabled, the list of intersections implied by ±90 • pivot moves on w(k) is provided at the bottom of the Configuration panel.

Other functionality of the PyUSAW software encompasses a backtracking search of unfoldable SAWs, based on Listing 9. The self-avoiding walk of the sandbox is extended systematically until reaching the specified deepness and, at each time an unfoldable SAW is found, its relative encoding is printed on the terminal. Drawn self-avoiding walks can be saved as a relative encoding text file, which can contain or not the position of w(0) in the square lattice, and naturally these text files can be opened by PyUSAW. Finally, the walk can be exported too in various image formats (SAWs represented in this research work have been obtained using this interface).

Conclusion

In this article, various computational methods have been proposed to investigate the newly discovered folded and unfoldable subsets of walks. These methods encompass backtracking, breadth first search, and Monte-Carlo approaches. The targeted goals was to find when the set of folded SAWs becomes different from the set of all self-avoiding walks, and to discover the shortest unfoldable SAWs. Significant advances have been achieved and explained with details, and an original Python tool to facilitate the study of these important SAW subsets has finally been presented.

In future work, the authors' intention is to restrict the range of uncertainties regarding the smallest n such that f SAW(n) G n , which is currently known to belong in 15, 107 . To do so, computational methods presented in this article, often quite naive, will be enhanced and optimized. Heuristic approaches encompassing swarm particles and genetic algorithms, will be regarded too to discover shorter unfoldable SAWs, if exist. Theoretically speaking, a complexity study of the protein structure prediction problem in the subset of folded SAWs will be realized, and we will try to rewrite the generating function of folded SAWs in other generating functions easier to calculate. Finally, consequences regarding the best ways to make protein structure prediction will be investigate.

Figure 1 :

 1 Figure 1: The first SAW shown to be not connected to any other SAW by 90°rotations (Madras and Sokal, [1]).

Example 1

 1 This is the set of SAWs on which we can apply at least one pivot move of ±90 • . Fig.4shows the two elements of a class belonging into f SAW(219, 2) whereas Fig.1is an element of USAW(223).

3. Computing the number of folded self-avoiding walks 3 . 1 .

 31 The number ♯G n of all possible s-step SAWs In[START_REF] Conway | Algebraic techniques for enumerating self-avoiding walks on the square lattice[END_REF], Conway et al. have presented an algebraic technique for enumerating self-avoiding walks on a rectangular lattice. To recall in detail how the number

Figure 3 :

 3 Figure 3: The digraph G(3)

Figure 4 :

 4 Figure 4: A self-avoiding walk in f SAW(219, 2)

Figure 5 :

 5 Figure 5: Obtaining all the walks

Figure 6 :

 6 Figure 6: Encoding and decoding walks

Figure 7 :

 7 Figure 7: Finding the self-avoiding walks

  and for the two possible directions. The function returns True if and only if no pivot move is possible. def f o l d ( walk , p o s i t i o n , d i r e c t i o n ) : i f p o s i t i o n == 0 : r e t u r n walk new = [ ] f o r k in range ( l e n ( walk ) ) : i f k<abs ( p o s i t i o n ) : new . append ( walk [ k ] ) e l s e : new . append ( ( walk [ k]+ d i r e c t i o n ) %4) r e t u r n decodes ( new ) def i s _ u n f o l d a b l e ( saw ) : f o r k in range ( 1 , l e n ( saw ) ) : i f is_saw ( f o l d ( saw , k , -1) ) : r e t u r n F a l s e e l i f is_saw ( f l o d ( saw , k , +1) ) : r e t u r n F a l s e r e t u r n True

Figure 8 :

 8 Figure 8: Testing whether a self-avoiding walk is unfoldable

  def s t r e t c h ( P , c ) : i f c == 0 : r e t u r n ( P [ 0 ] + 1 , P [ 1 ] ) e l i f c == 1 : r e t u r n ( P [ 0 ] , P [ 1 ] -1 ) e l i f c == 2 : r e t u r n ( P [ 0 ] -1 , P [ 1 ] ) e l s e : r e t u r n ( P [ 0 ] , P [ 1 ] + 1 ) def b a c k t r a c k (w, n ) : g l o b a l nb i f l e n (w)>=n : r e t u r n f o r a in range ( 4 ) : u = s t r e t c h (w[ -1 ] , a ) i f u not in s e t (w) : w1 = w+[u ] i f not i s _ u n f o l d a b l e ( encodes (w1) ) : i f l e n (w1)==n -1: nb += 1 # p r i n t ' ' . j o i n ( [ s t r ( k ) f o r k i n w1 ] ) b a c k t r a c k (w1 , n ) nb=0 n=13 b a c k t r a c k ( decodes ( [ 1 ] ) , n+2) p r i n t n , 4 * nb

Figure 9 :

 9 Figure 9: Backtracking method of USAW(n)

fromFigure 10 :

 10 Figure 10: Preliminaries for f SAW(n) investigations

  def e x p l o r e (G, node ) : f u t u r e _ n o d e s = [ ] f o r k in range ( 1 , l e n ( node ) ) : f o r d i r e c t i o n in [ -1 , 1 ] : new = f o l d ( node , k , d i r e c t i o n ) newString = t o S t r i n g ( new ) i f not G. has_node ( newString ) : i f is_saw ( new ) : f u t u r e _ n o d e s . append ( new ) G. add_edge ( t o S t r i n g ( node ) , newString ) e l s e : G. add_edge ( t o S t r i n g ( node ) , newString ) r e t u r n (G, f u t u r e _ n o d e s )

G

  = Graph ( ) n=6 nodes = [ [ 0 ] * n ] G. add_node ( t o S t r i n g ( nodes [ 0 ] ) ) while nodes != [ ] : new_nodes = [ ] f o r node in nodes : [G, x ] = e x p l o r e (G, node ) f o r k in x : i f k not in new_nodes : new_nodes . append ( k ) nodes = new_nodes p r i n t ( 4 * l e n (G) )

Figure 12 :

 12 Figure 12: Main program to compute the size of the connected component of the straight line.

): Proposition 2

 2 Let ν n the smallest n 2 such that USAW(n) ∅. Then 15 ν n 107. In other words, ∀n 14, f SAW(n) = G n , whereas f SAW(107) G 107 .

Figure 13 :

 13 Figure 13: Current smallest (107-step) unfoldable SAW

  (a) Pivot move at the border of a walk constituted by two intricately linked discs. (b) First unfoldable SAW found, obtained by this approach.

Figure 14 :

 14 Figure 14: Obtaining unfoldable SAW constituted by two overlapped discs

  (a) w 0 (239-step walk) (b) w 1 (391-step walk) (c) w 2 (575-step walk) (d) w 3 (791-step walk)

Figure 17 :

 17 Figure 17: PySAW software

Figure 18 :

 18 Figure 18: PySAW software

Table 1 :

 1 A short list of unfoldable SAWs

	3. If not, try to pick a new stretching direction again until reaching a pre-
	defined number of attempts. If this number is reached, then restart the
	whole process.
	Of course, when picking a new direction in {0, 1, 2, 3}, the previous one is
	considered beforehand and the set is adapted: if the previous move was 0, then

This python code is maintained by Christophe Guyeux (christophe.guyeux@univ-fcomte.fr, any feedback is welcome).

Acknowledgment

The authors wish to thank Thibaut Cholley, Raphaël Couturier, Jean-Marc Nicod, and Alain Giorgetti for their help in understanding folded and unfoldable SAWs. All the computations presented in the paper have been performed on the supercomputer facilities of the Mésocentre de calcul de Franche-Comté.


Julien Bourgeois
email: julien.bourgeois@univ-fcomte.fr

Seth Copen Goldstein

Distributed Intelligent MEMS: Progresses and perspectives

MEMS research has until recently focused mainly on the engineering process, resulting in interesting products and a growing market. To fully realize the promise of MEMS, the next step is to add embedded intelligence. With embedded intelligence, the scalability of manufacturing will enable distributed MEMS systems consisting of thousands or millions of units which can work together to achieve a common goal. However, before such systems can become a reallity, we must come to grips with the challenge of scalability which will require paradigm-shifts both in hardware and software. Furthermore, the need for coordinated actuation, programming, communication and mobility management raises new challenges in both control and programming. The objective of this article is to report the progresses made by taking the example of two research projects and by giving the remaining challenges and the perspectives of distributed intelligent MEMS.

Introduction

Microelectromechanical systems (MEMS) have reached a state of design maturity which has led to some interesting prototypes and profitable products. While most MEMS devices have been used as independent elements of a larger system, this article deals with distributed MEMS systems composed of many MEMS devices which work together to achieve a global goal. The distinguishing feature of MEMS devices is that they are small and that they can be efficiently mass-produced. This naturally engender thinking of how they can be used together as a distributed system. Due to their small size, their low-cost and the fact that they can be mass-produced, millions of units can be used in very small space. For example, a volume of less than 1 m 3 of 1mm-diameter silicon balls contains as many nodes as in the Internet. This characteristic requires paradigm-shifts both in hardware and software parts.

Past research focused on challenges of the engineering process, future challenges will consist in adding embedded intelligence to MEMS systems, so that they will be able to collaborate efficiently. This will require embedding MEMS sensors/actuators, electronics, communication capabilities, control of actuators and programs in the same unit. We suggest the use of the phrase "distributed intelligent MEMS (diMEMS)" when referring to such systems. DiMEMS systems will certainly contain heterogeneous units. However, to simplify the programming challenge, we consider in this article only systems composed of homogeneous units.

Designing and managing diMEMS inherently requires multiple disciplines (e.g. hardware and software research). The challenges are therefore present in every field of research as well as in the integration of all the parts. In the 90's, DARPA Information Science and Technology funded a study on the state of the art and the perspectives of distributed MEMS. The conclusions of this report [START_REF] Berlin | Distributed mems: New challenges for computation[END_REF], published in 1997, were that the challenges involved in realizing diMEMS were mainly in controlling large numbers of MEMS sensors and actuators, the emergence of distributed intelligence, the use of MEMS devices as computational elements and the multiple-energy-domain simulation, analysis, and design. This article examines these challenges and the new ones that have been identified since 1997 using the results of two projects that have been conducted in the field.

Challenges

Many of the challenges raised by diMEMS have been studied in isolation in different research fields. However, in diMEMS they must be examined together and they become even more extereme. The scale of diMEMS needs new software paradigms as well as requiring new hardware capabilities. In the main, scaling up is the main concern of software challenges, while scaling down is the main concern of hardware challenges.

Software challenges, scaling up

Scalability Scalability is the main concern of diMEMS as the number of units will likely number in the millions. Scalability therefore impacts the way units will communicate. Systems using synchronous communications can't scale as well as those using asynchronous communications because the constraints of synchronization lower the system efficiency [START_REF] Baz | Distributed part differentiation in a smart surface[END_REF]. Synchronous communication is therefore difficult to achieve and asynchronous communications have already shown better results.

To ensure scalability, the programming model and the language must hide the complexity from the programmer and the compiler should enable programming the system as a single ensemble. Within the Claytronics project, new languages like LDP [START_REF] De Rosa | Programming modular robots with locally distributed predicates[END_REF] and Meld [START_REF] Ashley-Rollman | A language for large ensembles of independently executing nodes[END_REF] been have developed to cope with this challenge.

As scalability has to be tested up to millions of units, simulation tools also have to scale up. Dprsim [START_REF] Rister | Integrated debugging of large modular robot ensembles[END_REF] which has been developed within the Claytronics project has successfully simulated millions of units.

Uncertainty tolerance

Faulty behavior is inherent to any diMEMS system. This is due to several factors. The batch process used in MEMS fabrication creates different levels of reliability. While some of the devices will have no defects, most of them have a high percentage of failed units. On the software side, this characteristic has to be handled and fault-tolerance has to be implemented.

In the case of mobile distributed MEMS a logical topology has to be maintained in order to communicate between the units. Maintaining a logical topology over a physical one is the concern of many research topics like P2P [START_REF] Andersen | Resilient Overlay Networks[END_REF], swarm intelligence [START_REF] Gro | Autonomous self-assembly in swarm-bots[END_REF][START_REF] Lewis | The behavioral self-organization of nanorobots using local rules[END_REF], ad hoc networks [START_REF] Royer | A review of current routing protocols for ad hoc mobile wireless networks[END_REF] or wireless sensor networks [START_REF] Wang | Topology control for wireless sensor networks[END_REF]. Mobile distributed intelligent MEMS is even more complex than these examples. Mobility, scalability, fault-tolerance and limited processing capability are the main challenges to solve in order to create and maintain a logical topology.

Communications

The tradeoff between computation/communication/sensing is a challenge that has already been studied in wireless sensor networks but it needs some adaptation to take into account the scalability factor which is inherent to diMEMS.

Each diMEMS project has its own communication model directly linked to the application. The question here would be to study the cost and the interest of having some abstraction layer.

Control

When each unit of a system is mobile, the changes in the physical topology modify the logical topology by changing network connectivity. This is one of the main concerns of MANET. The inverse is also true, the logical topology can drive the mobility. This is usually done by covering an area which needs to be sensed [START_REF] Schwager | Decentralized, adaptive control for coverage with networked robots[END_REF] but it can also be used for modifying the logical topology, for example to keep connectivity in a sensor network [START_REF] Derbakova | Decentralized self-repair to maintain connectivity and coverage in networked multi-robot systems[END_REF].

DiMEMS are composed of actuators which needs control and a degree of synchronization. Three synchronization schemes can be used: no synchronization between MEMS units, means that the control loop doesn't have to synchronize with other units, local synchronization means that a MEMS unit has to be synchronized with its neighbors while global synchronization means that all the MEMS units have to act synchronously.

Having actuators to control requires real-time deadlines. Some applications need a very high frequency from the controler. If the control is fully decentralized like it is the case in distributed intelligent MEMS and that different modules requires a local or a global synchronization, the time to communicate has to be very short.

Reliability through properties verification

Reliability is difficult to achieve in any information technology project. The approach taken to achieve it often uses modularity which allows one to define interfaces and to segment the causes of failures. In diMEMS, this modularity is limited. Methods to model the whole system with VHDL-AMS and UML/SysML would allow one to verify some properties of the system and to increase its reliability.

CPS and IoT, relations with macro world

DiMEMS are systems that can interact with other intelligent systems. This interaction is the focus of cyber-physical systems (CPS) [START_REF] Lee | Cyber physical systems: Design challenges. Object-Oriented Real-Time Distributed Computing[END_REF] and Internet of Things (IoT) [START_REF] Ashton | That 'internet of things' thing[END_REF]. The new challenge with distributed inteligent MEMS systems is to manage the different density of communication between the macro-objects (low density) and the micro-objects (high density).

Hardware challenges, scaling down

Seamless integration of MEMS and logic

Integrating MEMS with CMOS is still a challenge in the fabrication process [START_REF] Witvrouw | Cmos-mems integration: why, how and what?[END_REF][START_REF] Ghosh | On integrated cmos-mems system-on-chip[END_REF]. Most of the MEMS-CMOS integration follow a hybrid integration through wire-bonding but this approach is not well-suited for diMEMS which requires too many connections. DiMEMS requires a monolithic integration for two reasons. First of all, only a monolithic approach can guarantee scalable and affordable fabrication process whereas hybrid approaches often requires manual intervention. Secondly, the weight of a hybrid system is more important than a monolithic one. MEMS actuation requires higher voltages than logic which can create problems. Some solutions have been proposed [START_REF] Karagozler | Electrostatic actuation and control of micro robots using a post-processed high-voltage soi cmos chip[END_REF] to tackle this problem but a real voltage difference management between actuation and logic is still a challenge.

Designing robust MEMS

Due to their size, MEMS are very sensitive to external factors (e.g., dust and air quality) which can change the behavior of certain types of MEMS actuators. Modeling and simulation have proven to be efficient to solve design issues [START_REF] Chapuis | FPGA-in-the-loop for control emulation of distributed MEMS simulation using VHDL-AMS[END_REF] but new solutions have to be found to increase MEMS robustness.

Building micro-communication devices

DiMEMS needs communication capabilities, but integrating communication and MEMS is still a significant challenge. Some of them are linked to the previous challenges described here like the voltage difference between the actuation and the logic and the integration of MEMS and logic but scalability is also an issue. One-way communication to the MEMS has been implemented, for example, in DMD where each micro-mirror has to be oriented is the right direction [START_REF] Hornbeck | Digital Light Processing for high-brightness high-resolution applications[END_REF]. While this approach works for a fixed topology and even for a regular network of actuators, it doesn't scale for more complex devices or mobile units. Building a real micro-communication device is still a challenge that haven't been solved yet.

Examples

Many projects have been built around MEMS but no killer application has yet been realized. Two active projects which are studying diMEMS are the Smart projects (Smart Surface and Smart Blocks) [START_REF] Boutoustous | Distributed control architecture for smart surfaces[END_REF] and Claytronics [START_REF] Goldstein | Beyond audio and video: Using claytronics to enable pario[END_REF].

The Claytronics project

Introduction

The past several decades have demonstrated the remarkable power of programmability: general-purpose computers have enabled new application domains that were not anticipated when these computers were designed. As impressive as cyberspace is these days, it is useful to remember that we live in a world that is physical and not merely virtual. To enable new classes of exciting applications that may stretch our imaginations (e.g., shape-shifting medical instruments, hands-on interactive 3D design, etc.), the claytronics project aims to bring the power of general-purpose programmability to everyday physical artifacts in a fundamental way through a new form of programmable matter. In the long term, our goal is to construct the programmable matter such that its shape, motion, appearance, and response to human touch can be arbitrarily controlled by software.

Our vision for realizing programmable matter is to harness the collective power of a vast number (perhaps millions) of tiny (e.g., millimeter sized) spherical robots that can stick together and move around each other to form an overall material with somewhat fluid properties that we call "claytronics". The name "claytronics" was inspired by the word "claymation," since the material might resemble a form of modeling clay that can shape itself. We refer to the individual robots that make up this ensemble as "catoms", which is short for "claytronics atoms".

Hardware results

At first glance the ability to create a coherent ensemble of millions of units appears fantastical. But, if we step back and examine it, the question is not "if" we can manufacture it, but "when." It is clearly possible to do so in principle, e.g., biology builds ensembles of units which coordinate together to form dynamic 3D shapes which can interact in the real world. And, we already have MEMS processes which creates 3D devices. Reid has constructed spherical shapes by first printing a projection of the sphere and then, by harnessing the inherent stresses in thin film silicon dioxide, causes the projection to self-assemble into a sphere (See Figure 1) [START_REF] Reid | Building micro-robots: A path to submm 3 autonomous systems[END_REF][START_REF] Vasilyev | Microfabrication of si/sio2-spherical shells as a path to sub-mm 3 autonomous robotic systems[END_REF]. This same process can be applied to a pre-fabricated CMOS wafer to create 3D units with integrated processors and actuators.

Software results

In pursuit of our goal we are exploring different programming approaches and have developed two new programming languages: LDP [START_REF] De Rosa | Programming modular robots with locally distributed predicates[END_REF][START_REF] Ashley-Rollman | Declarative programming for modular robots[END_REF] and Meld [START_REF] Ashley-Rollman | Meld: A declarative approach to programming ensembles[END_REF].

1mm

Fig. 1 An example of a spherical shell (with diameter of ˜0.9mm) made using standard photolithography and stress induced curling. The shell (in the upper left) is sitting on a circuit board which can move the shell using electrostatic forces. Included with the permission of Rob Reid. Both of these languages are declarative in nature and result in programs which are about 20x shorter than equivalent imperative programs. They each take an ensemble perspective, allowing a programmer to create simple, concise, programs that are automatically compiled down to programs that run on each unit. One of the advantages of concise programs is the ability of the programmer to focus on the program logic, facilitating correctness and affording greater opportunity for algorithm enhancements (like optimizations). In the case of larger programs we often see better performance in the Meld implementation than an equivalent C++ one. The main reason for this is that Meld and LDP make it easier to write a parallel program than a sequential one, utilizing much of the latent parallelism inherent in the algorithm, while the C++ implementation is limited to the parallelism that the programmer can manage and explicitly encodes.

The Smart Surface project

Introduction

The objective of the Smart Surface project is to design a distributed and integrated micro-manipulator based on an array of micro-modules in order to realize an automated positioning and conveying surface. Each micro-module will be composed of a micro-actuator, a micro-sensor and a processing unit. The cooperation of these micro-modules thanks to an integrated network will allow to recognize the parts and to control micro-actuators in order to move and position accurately the parts on the Smart Surface. The parts are small, they cover a few numbers of micro-modules (e.g. 4 × 4).

Figure 3 shows one prototype of Smart Surface. The rectangular holes seen on the front-side are the air nozzles. Air-flow comes through a microvalve in the back-side of the device and then passes through the nozzle. The advantage of this solution is that the micro-actuators, the most fragile part of the surface, are protected.

Hardware results

Three prototypes have been built within the Smart Surface project, these prototypes have different kinds of actuators, but their main difference can be found in the way the actuators can be controled.

Remotely placed actuators surface.

Each cell has oriented holes in 4 directions which means that each can create an airflow in the 4 directions. There is only one actuator per column so that all the cells of a column have the same behavior. The cells are therefore passives as they don't have an actuator.

Grouped control of actuators. This type of prototype is composed of actuators that can create airflow in 2 directions (see figure 3)and as the previous one, the actuators are controlled by column.

Individual control of actuators.

The more advanced prototype has the same actuators as the previous one, i.e. 2 directions but each actuator can be controlled directly which allows a finer control. This last prototype is the more complex to build as each actuator as to be connected to the controller.

Software results

Even in a technological project, software plays an major role. Four aspects have been studied within this project, sensor feedback, communications, control and modeling.

Sensor feedback.

Each cell that compose the surface comprises a processing unit, communication capabilities, an actuator and sensing capabilites. Sensing gives an indication on the presence of an object on top of it. More precisely, each sensor sends a binary information to its processing unit regarding the presence or the absence of the object. The object is therefore highly discretized. The first work has been to work on the differentiation possibility of highly discretized objects and on the choice of the best criteria to do so. The Exhaustive Comparison Framework (ECO) [START_REF] Boutoustous | An exhaustive comparison framework for distributed shape differentiation in a MEMS sensor actuator array[END_REF] has been designed in order to test exhaustively the efficiency of different differentiation criteria, in term of differentiation efficiency, memory and processing power needed. The second work has been to set the optimal number of sensors that have to be embedded inside the surface. The Sensor Network Calibrator (SNC) [START_REF] Dedu | Simulation to help calibration of a mems sensor network[END_REF] allows to test different number and organization of sensors.

Communications.

The physical topology of the Smart Surface is a rectangle, and where each cell is connected to its four neighbours, the network topology is then a mesh 2D. As the network topology is known and fixed, the challenges are in the algorithmic part. A mathematical model of discrete state acquisition and several distributed iterative algorithms have been proposed and tested [START_REF] Baz | Distributed part differentiation in a smart surface[END_REF]. Synchronous and asynchronous state acquisition methods and the asynchronous ones have shown better results. Simple initial points and convergence results for distributed algorithms have been proposed. In both the synchronous and asynchronous cases, stopping criteria have been designed. The Smart Surface Simulator has been designed to evaluate and to validate experimentally the proposed distributed algorithms Control.

Controlling the Smart Surface is very challenging as pneumatic actuation has many problems that need to be solved. The reinforcement learning method which has been implemented is decentralized and addresses the global-local trade-off [START_REF] Matignon | Designing decentralized controllers for distributed-air-jet mems-based micromanipulators by reinforcement learning[END_REF]. An integration of sensing, communications and control has been proposed [START_REF] Boutoustous | Distributed control architecture for smart surfaces[END_REF] and the experiments have shown good properties of the system.

Modeling

The VHDL-AMS model [START_REF] Chapuis | FPGA-in-the-loop for control emulation of distributed MEMS simulation using VHDL-AMS[END_REF] that have been developed inside the Smart Surface project can simulate the behavior of the surface while the SysML model [START_REF] Giorgetti | Using SysML for smart surface modeling[END_REF] gives a more higher-level description of the architecture. The SysML model is derived from the VHDL-AMS one and the objective is to link the SysML description of the hardware to the UML description of the software. This would allow properties verification for the whole system.

Conclusion

The concept of diMEMS has been proposed 15 years ago but only few of the challenges have been fully addressed. One reason is that diMEMS is a multidisciplinary field of research involving the topics of MEMS sensors/actuators design and fabrication, electronics, networking, programming and control. Having all these skills in one project is diffficult. Another reason is that the topic of diMEMS relies on MEMS technology and it couldn't exist until MEMS research reaches its complete maturity. This time of maturity has come and we think that the time for pushing further the topic of diMEMS has come as well.

•Fig. 2

 2 Fig. 2 An example of a complete cylindrical catom. On the left if a cad drawing of the silicon shell and compelted robot. On the right, the realized result: you can see the logic die inside the exterior silicon shell. Included with the permission of M. Karagozler.

Fig. 3

 3 Fig. 3 Smart Surface prototype with grouped control of actuators

Acknowledgements We would like to thank all the Smart Surface and Claytronics groups and in particular Eugen Dedu, Kahina Boutoustous and Didier El Baz, Michael Ashely-rollman, and Mustafa Emre Karagozler. This work was supported in part by ANR (ANR-06-ROBO-0009), DARPA (FA87501010215), NSF (CNS-0428738) and Intel Corporation.