Thomas Roche

Laurent Imbert

Victor Lomné

Side-channel Attacks on Blinded Scalar Multiplications Revisited

In a series of recent articles (from 2011 to 2017), Schindler et al. show that exponent/scalar blinding is not as effective a countermeasure as expected against side-channel attacks targeting RSA modular exponentiation and ECC scalar multiplication. Precisely, these works demonstrate that if an attacker is able to retrieve many randomizations of the same secret, this secret can be fully recovered even when a significative proportion of the blinded secret bits are erroneous. With a focus on ECC, this paper improves the best results of Schindler et al. in both the generic case of random-order elliptic curves and the specific case of structured-order elliptic curves. Our results show that larger blinding material and higher error rates can be successfully handled by an attacker in practice. This study also opens new directions in this line of work by the proposal of a three-steps attack process that isolates the attack critical path (in terms of complexity and success rate) and hence eases the development of future solutions.

Introduction

Nowadays, all modern tamper-resistant implementations of public-key algorithms embed relatively cheap, yet very strong countermeasures based on various randomization strategies. As a consequence, single-trace horizontal attacks have gained more and more attention from the side-channel community.

Single trace horizontal attacks apply to both elliptic curve scalar multiplication and modular exponentiation (RSA). Implemented in a supervised or nonsupervised setup, they provide the attacker with a randomized, or blinded scalar (resp. exponent) from the observation of a single scalar multiplication or exponentiation. Although these attacks do not yield the original scalar (resp. exponent), the disclosure of a blinded value may allow an attacker to counterfeit digital signatures or impersonate any party in a key exchange protocol.

This ultimate attack thus renders scalar (resp. exponent) randomization useless. However, it requires a very high signal-to-noise ratio to be successful in practice. Many recent publications claim successful single trace horizontal attacks on secure RSA or ECC [2, 8-12, 17, 19]. These attacks do not usually recover the whole blinded value. The missing bits are eventually recovered using brute-force. Therefore, the number of incorrect bits must remain relatively small for the attack to be successful. In single-trace horizontal attacks, this number of incorrect bits is dictated by the so-called bit error rate of the attack.

In this work, we consider the case where brute-forcing the incorrect bits is impracticable. We focus on ECC scalar multiplication but our analysis for random-order elliptic curves easily extends to RSA exponentiation. We assume that the attacker can observe several scalar multiplications with the same longterm secret scalar but each execution uses fresh randoms for scalar blinding. A typical example of such a context occurs in the public key generation of ECC cryptosystems. The attacker requests from a device many generations of the public key corresponding to the private key securely stored inside the device. We will also assume that the scalar randomization is done following [START_REF] Coron | Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems[END_REF] by adding to the secret scalar a random multiple of the elliptic curve order.

The first paper in the literature to tackle this problem is the seminal work of Schindler and Itoh [START_REF] Schindler | Exponent blinding does not always lift (partial) SPA resistance to higher-level security[END_REF] which exhibits a very efficient attack (in terms of number of traces and computational effort) when small blinding factors r are used. Over the past five years, this result was improved [START_REF] Schindler | Power attacks in the presence of exponent blinding[END_REF], applied to specific elliptic curves [START_REF] Feix | Side-channel analysis on blinded regular scalar multiplications[END_REF][START_REF] Schindler | Efficient Side-Channel Attacks on Scalar Blinding on Elliptic Curves with Special Structure[END_REF] and to RSA with CRT [START_REF] Schindler | Generic power attacks on RSA with CRT and exponent blinding: new results[END_REF]. In the present paper, we expand this line of results by suggesting several improvements that make it possible to recover scalars blinded with large random factors (> 32 bits), and high bit error rates (> 10%).

Preliminaries and Notations

In the following, we consider an elliptic curve defined over the finite field F p , with p a K-bit prime (typically K = 256). E denotes the order of the curve and d is the secret scalar, target of the attack. Both E and d can be represented on K bits. The term msb (resp. lsb) will be used to shorten most (resp. least) significant bits.

For each scalar multiplication, the scalar d is blinded by adding a random multiple of the group order, i.e. d ← d + r × E, where r is an R-bit random value. The blinded scalar d is then represented on K + R bits.

The attaker observes N scalar multiplications. These N side-channel observations, called traces, are denoted {T } <N3 . For each trace T , the attacker's horizontal side-channel attack outputs a noisy blinded scalar, denoted d . For all bit index i < K + R, it is assumed that the probability b for bit d [i] to be erroneous, called bit error rate, is independent of both and i. Depending on the context (supervised or nonsupervised horizontal attacks) b is considered known or unknown to the attacker.

In [START_REF] Schindler | Exponent blinding does not always lift (partial) SPA resistance to higher-level security[END_REF], the authors introduce a cornerstone tool for all subsequent attacks called Non-Adjacent-Form distinguisher. Given two noisy blinded scalars ( di , dj ) and two guesses (r i , rj ) on their respective blinding factors, the distinguisher provides a very robust way to assert the correctness of the guesses. We define

D NAF i,j
as follows:

D NAF i,j = HW(NAF( di -ri × E -( dj -rj × E))),
where NAF() is the non-adjacent form encoding (see e.g. [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]) and HW() is the natural extension of the Hamming Weight function to signed-digit representations.

Schindler and Itoh observed4 that D NAF i,j

is significantly smaller for correct values (r i , rj ). A detailed study of the distinguisher behaviour with respect to K + R and b can be found in [START_REF] Schindler | Exponent blinding does not always lift (partial) SPA resistance to higher-level security[END_REF][START_REF] Schindler | Power attacks in the presence of exponent blinding[END_REF], it allows to choose a bound B b ,K+R such that D NAF i,j < B b ,K+R implies that (r i , rj ) are correct with high probability. Clearly, this distinguisher will be more effective as K and R increase and b decreases. The non-adjacent-form distinguisher proves to be sufficient for parameters considered in the present study (K = 256, 32 R 128, 0.1 b 0.25).

Overall Attack Process

Our attack context is the gathering of three independent steps. Our contributions are solely related to the second step and, for completeness, we briefly describe the whole attack process below.

Step 1: The attacker acquires N traces corresponding to N independent scalar multiplications and performs a horizontal attack for each of them. The output of this first step is a set of noisy blinded scalars { d } <N together with a bit error rate b . In the supervised setting 5 (see e.g. [START_REF] Bauer | Horizontal and vertical side-channel attacks against secure RSA implementations[END_REF][START_REF] Carbone | Deep learning to evaluate secure RSA implementations[END_REF][START_REF] Weissbart | One trace is all it takes: Machine learningbased side-channel attack on eddsa[END_REF]) the attacker possesses a good estimation of the bit error rate b . Given b the attacker knows beforehand the number of acquisitions N that must be performed to have good chance of success. In the more general unsupervised setting (see e.g. [START_REF] Heyszl | Clustering algorithms for non-profiled single-execution attacks on exponentiations[END_REF][START_REF] Järvinen | Single-trace side-channel attacks on scalar multiplications with precomputations[END_REF][START_REF] Nascimento | Applying horizontal clustering side-channel attacks on embedded ECC implementations[END_REF][START_REF] Nascimento | Attacking embedded ECC implementations through cmov side channels[END_REF][START_REF] Perin | Attacking randomized exponentiations using unsupervised learning[END_REF][START_REF] Specht | Improving non-profiled attacks on exponentiations based on clustering and extracting leakage from multi-channel high-resolution EM measurements[END_REF]), the access to a training device is not possible. The attacker acquires as many traces as possible and induces a maximal value for b that can be handled through the attack. In both cases, this first step provides the attacker with N noisy blinded scalars together with a gross value for b .

Step 2: From each noisy blinded scalar d , the attacker guesses the blinding factor r or discards the corresponding data from the attack process. The output of this filtering step is a subset { d } ∈J along with guessed blinding factors {r } ∈J for some J ⊂ (Z ∩ [0, N -1]). All r do not have to be correct but some of them must be correctly guessed.

Step 3: The last step of the attack recovers the secret scalar d from { d } ∈J and {r } ∈J . These inputs may first be trimmed off using e.g. the NAF distinguisher. (The pair ( di , r i ) is removed if, for all j = i, D NAF i,j is larger than the predefined bound B b ,K+R .) After this optional pruning step, a vertical side-channel attack can be mounted on the remaining traces. Such an attack is described in [START_REF] Feix | Side-channel analysis on blinded regular scalar multiplications[END_REF] for specific elliptic curves but can be extended straightforwardly in our context to any elliptic curve and RSA. In Appendix A, we propose a simple vertical attack to confirm this claim and show that few tens of correctly guessed blinding factors are enough to successfully recover the secret scalar (resp. exponent).

Paper Organization and Contributions

This work focuses on improvements in Step 2 when R > 32. The first contribution applies to general elliptic curves without hypothesis on the curve order form. It is described in Section 2. This new proposal outperforms the current best attacks by Schindler and Wiemers [START_REF] Schindler | Power attacks in the presence of exponent blinding[END_REF][START_REF] Schindler | Generic power attacks on RSA with CRT and exponent blinding: new results[END_REF], e.g. we show that configurations where (R = 64, b = 0.2) and (R = 96, b = 0.15) can be successfuly attacked in practice. The second contribution applies to the specific case of elliptic curves whose order is close to a power of 2. Our strategy and results are presented in Section 3. Compared to the best known attack [START_REF] Schindler | Efficient Side-Channel Attacks on Scalar Blinding on Elliptic Curves with Special Structure[END_REF], our simulations show significant increases in the success rates for blinding factors up to K/2.

On Random-Order Elliptic Curves

In this section we consider elliptic curves without assumption on the form of their order. Based on previous work, our results can be extended to RSA implementations without CRT 6 and even implementations with CRT 7 .

We will first briefly describe the Alternate Attack [START_REF] Schindler | Power attacks in the presence of exponent blinding[END_REF] (also described in [START_REF] Schindler | Generic power attacks on RSA with CRT and exponent blinding: new results[END_REF]). To the best of our knowledge, this attack is the only known attack in the literature that works in practice for non-negligible values of b and large blinding factors (R > 32, typically R = 64 or R = 96). In Section 2.2, we present a new attack which, compared to [START_REF] Schindler | Power attacks in the presence of exponent blinding[END_REF], offers two advantages: 1. its simplicity. It allows to exhibit the computational cost of the algorithm for arbitrary chosen success rate without having to go through costly simulations. Hence providing a better understanding on the capability of the attack given the attacker's computational effort. 2. its efficiency. For an equivalent computational cost, it handles larger values of R and/or larger values of b than [START_REF] Schindler | Power attacks in the presence of exponent blinding[END_REF]. This comes at a price: increasing the number of observed scalar multiplications (i.e. N ).

Previous Work

Let us briefly recall the Alternate attack from Schindler and Wiemers (for more details see [START_REF] Schindler | Power attacks in the presence of exponent blinding[END_REF]Algorithm 3], also called sub-attack I ).

Given a blinded scalar d , Schindler and Wiemers define α = d /2 K-1 (thus α < 2 R+1 ) and β = d mod 2 w (for a chosen window size w < K). Since d = d + r × E, they demonstrate that the w lsb of d verify the following equation:

d mod 2 w = α 2 K-1 mod E + β -ω E mod 2 w ,
where ω takes an unknown value in {0, 1}.

From noisy blinded scalars d , we have access to noisy versions of α (say α ) and β (say β ). The idea is then to brute-force all error patterns (of Hamming Weight t) over α and β (t must be carefully chose given b ) as well as the values of ω . Each hypothesis on (α , β , ω ) will provide a candidate x for d mod 2 w . Over all N noisy blinded scalars, the correct d mod 2 w should be in the best ranked candidates x (those that appeared the most during the whole bruteforce).

If successful this attack outputs the w lsb of d, for w typically as large as R. To finish the attack (and recover the remaining bits of d), the authors of [START_REF] Schindler | Power attacks in the presence of exponent blinding[END_REF] apply iteratively another attack (so-called sub-attack II ). In our setup (see Section 1.2 for a description of the overall attack process), we would more likely use the knowledge of d mod 2 w to rewind the Alternate Attack and find the most likely blinding factors r . Indeed, for some scalars, the correct value of (α , β , ω ) must have been found during the brute-force and can be collected from the knowledge of d mod 2 w . Obtaining the random factor r is then straightforward as r = α 2 K-1 /E + ω . Then one would apply Step 3 of the overall attack process by suppressing the erroneous values of r based on the NAF distinguisher and following the approach described in Annex A.

The computational cost of the sub-attack I algorithm is 2M 0 N predictions of triplets (α , β , ω ), where M 0 = R+w t with t the number of erroneous bits tested by the brute-force over the ∼ R + w bits of (α , β ). The authors estimate the correct values of t, w and N for successful attacks and provide the following results (copied from [14, Table 12]) that gives the maximum value of R for various attack configurations.

N 2M0N b = 0.10 b = 0.15 b = 0.20 10

A New Generic Algorithm

From the bit error rate b and R it is easy to choose N such that there is a good chance that at least 2 noisy blinded scalars are correct on their R + 1 msb (i.e. α = α ). Indeed, in the idealized hypothesis where each bit of each d is erroneous with probability b independently from all other bits, the number of erroneous bits in the R + 1 msb of each d follows a Binomial distribution with parameters (R + 1, b ). Therefore, on average, the number of observations needed to acquire n noisy blinded scalars with t erroneous bits or less in their R + 1 msb is given by N = n/ CDF (R+1, b ) (t), where CDF (R+1, b ) (t) is the cumulative distribution function of the Binomial distribution with parameters (R + 1, b ). Equivalently, if the attacker observes N noisy blinded scalars, the average number of observations that have t or less erroneous bits in their R + 1 msb is given by n = N × CDF (R+1, b ) (t). Now, let us assume that N is large enough with respect to (R + 1, b ) such that there exists (with good probability) two indexes i < j < N such that the R + 1 most significant bits of di and dj are all correct. The idea is to identify the pair (i, j) based on the NAF distinguisher (see Section 1.1): for all l < N , estimate the blinding factor of dl as follows

rω l l = αl 2 K-1 /E + ω l ,
where αl is the R + 1 msb of dl and ω l takes value 0 or 1. The attacker possesses then two blinding factor candidates for each dl . Also, by hypothesis, there exists (ω i , ω j ) such that r i = rωi i and r j = rωj j . Computing the NAF distinguisher on all pairs of noisy blinded scalars for both of their blinding factors, one can identify the pair (i, j) if they do exist (D NAF i,j is significantly small compared to

D NAF k,l where r k = rω k k or r l = rω l l ). This costs 4 N (N -1)
2 computations of D NAF . Once the pair (i, j) is found, the corresponding masks r i and r j are known. It is now possible to run through the remaining N -2 noisy blinded scalar, for each of them, one can brute-force all error patterns with t erroneous bits or less among the R + 1 msb. For each error pattern, two blinding factors {r ω l l } ω l ∈{0,1} are computed from dl and the corresponding D NAF i,l (or D NAF j,l ) can be estimated asserting if the correct blinding factor r l was found. t must be chosen such that, at the end of this step, enough correct blinding factors are found (such that, e.g. the procedure described in Appendix A can be applied successfully). This step costs 2(N -2) × R t computations of D NAF . Since N was chosen large enough to yield the initial error-free scalars (i and j), small values of t (typically 1 or 2) are enough in practice to find few tens of correct r l . The overall complexity of the algorithm is then dominated by 2N (N -1) D NAF computations in practice.

Parameter Choices and Comparison with Alternate Attack [START_REF] Schindler | Power attacks in the presence of exponent blinding[END_REF] Table 2 displays the number of noisy blinded scalars (N ) such that, on average, at least 2 such scalars are error-free on their R + 1 msb 8 . Let us emphasize that these estimations are independent from both the size K of E and d. However the attack itself depends on K since the NAF distinguisher will work better as K increases. For instance, with K = 256, and bit error rates b > 0.25 the distinguisher looses effectivness and becomes totally ineffective when reaching b = 0.4. These offlimits cases are identified in Table 2 with blue cells. Also, one needs to take into account the attack complexity which grows quadratically with N . Gray cells in Without an efficient way to estimate the success rate of the Alternate Attack from [START_REF] Schindler | Power attacks in the presence of exponent blinding[END_REF], it is difficult to thoroughtly compare the two attacks. Nevertheless, one can observe from Table 1 that

On Structured-Order Elliptic Curves

In this section, we focus on elliptic curves with structured orders 9 .

Previous Works

In [START_REF] Schindler | Efficient Side-Channel Attacks on Scalar Blinding on Elliptic Curves with Special Structure[END_REF], Schindler and Wiemers study elliptic curves with order of the form E = 2 K ± E 0 , where E 0 is close to 2 K/2 . This case is pretty common in cryptography when the base field is defined using a pseudo-Mersenne prime for efficiency reasons. Most of the EC standards are of this form, e.g. SEC2 curves [START_REF]SEC 2 : Recommended Elliptic Curve Domain Parameters[END_REF], NIST curves [START_REF]Digital Signature Standard[END_REF].

A Devide and Conquer Algorithm Schindler and Wiemers observe that the problem of solving the N noisy blinded scalars can be done using a divide and conquer algorithm. This observation leads to a much more robust decoding algorithm than in the general case. Indeed, a blinded scalar d with blinding factor r can be written as follows:

d = r × E + d = r × (2 K ± E 0 ) + d = r × 2 K + (d ± r × E 0 )
Hence, if d ± r × E 0 is smaller than 2 K , then the R msb of d are exactly the R bits of r . As a side remark, if r × E 0 is smaller than d, then the most significant bits of d are not correctly masked (see e.g. [START_REF] Ciet | virtually) free randomization techniques for elliptic curve cryptography[END_REF]). Now, for a given window size w, if (d ± r × E 0 ) < 2 K , then d mod 2 w and d /2 K mod 2 w only involve the known w lsb of E and the unknown w lsb of d and r . From this observation, Schindler and Wiemers (see [START_REF] Schindler | Efficient Side-Channel Attacks on Scalar Blinding on Elliptic Curves with Special Structure[END_REF]) propose an efficient algorithm to recover the secret d that comprises three phases:

-Phase 1: find the R lsb of d as well as the most likely values of the blinding factor r for each noisy blinded scalar d . -Phase 2: select the values r that are the most likely to be correct based on the NAF distinguisher (see Section 1.1). -Phase 3: recover the full secret scalar d.

Phases 2 and 3 correspond exactly to step 3 of our overall attack scheme described in Section 1.2.

Schindler and Wiemers' Phase 1 Algorithm is described in [15, Algorithm 4] along with several empirical improvments discussed in the next sections. The algorithm processes iteratively over a small sliding window of size w (typically w is 8 or 10). Each iteration consists of two main steps recalled in Algorithm 1 and Algorithm 2 respectively.

In Algorithm 1, the call to EvaluateProbability(r , d , d , i, w, b ) computes the probability of observing d knowing the error rate b and the two w-bit words r and d which correspond respectively to the two w-bit words d /2 K+i-1 mod 2 w and d /2 i-1 mod 2 w . Hence, we have: After R iterations of Algorithms 1 and 2 the output is d mod 2 R if everything went correctly. As stated above, this is the most critical phase in Schindler and Wiemers's algorithm. They propose two empirical approaches to improve both its efficiency and effectivness. We will briefly present them in the next section. However, since these improvements are based on hand-picked thresholds by the authors of [START_REF] Schindler | Efficient Side-Channel Attacks on Scalar Blinding on Elliptic Curves with Special Structure[END_REF] without clear explanations on how to choose these limits (we are assuming that these thresholds must be adjusted in a case-by-case manner) we will not take them into account in our study. Nevertheless, since the improvements presented here can be applied on the core algorithms, the empirical improvements can always be added above them. We then focus on the low level algorithms and leave for future work the addition and study of these extra improvments.

EvaluateProbability(r , d , d , i, w, b ) = h b (1 -b ) 2w-h , where h = HammingDistance(r , d /2 K+i-1 mod 2 w ) + HammingDistance( d , d /2 i-

Empirical Improvements

The first improvement is added to Algorithm 2 to increase the effectivness of the attack. Concretely, the authors add an estimation of the correctness of r . When this estimation of correctness goes below a certain threshold, the corresponding noisy blinded scalar d is removed from the process. The question of how to choose the threshold is not discussed in [START_REF] Schindler | Efficient Side-Channel Attacks on Scalar Blinding on Elliptic Curves with Special Structure[END_REF] but several values are proposed depending on the bit error rate b and the iteration number i.

The second improvement is dedicated to efficiency. The algorithm cost is dominated by Step 1 (Algorithm 1), its complexity being O(2 2w N ). The authors propose to reduce the number of treated noisy blinded scalars in this step and apply the second step to all noisy blinded scalars. The idea is that, if costly, Step 1 is more robust than Step 2 and therefore does not need all the N noisy blinded scalars to correctly guess d mod 2 w+i-1 . The authors propose, again without justification, the "good" number of noisy blinded scalars to be used in Step 1 depending on the bit error rate b and the iteration number i. The above improvements were not tested in this paper. However, one can easily see that they can be applied pretty much similarly to our algorithms with adjusted thresholds.

Some Results

It is shown in [START_REF] Schindler | Efficient Side-Channel Attacks on Scalar Blinding on Elliptic Curves with Special Structure[END_REF] that Algorithms 1 and 2 allow to correct noisy blinded scalars with large values of R, typically 64 and large error rates 0.1 b 0.15. This result is very important since before [START_REF] Schindler | Efficient Side-Channel Attacks on Scalar Blinding on Elliptic Curves with Special Structure[END_REF], a value of R = 64 was considered perfectly safe from a side-channel point of view.

One crucial parameter of these algorithms is the choice of the window size w since the robustness of the procedure increases with w. However, since the algorithm complexity is dominated by O(2 2w N ), w cannot be very large either. Figure 1 provides simulation results for various values of w of Algorithms 1 and 2. It gives the average number of bits of d guessed correctly before a wrong bit appears, as a function of the number of traces N . These simulations were done with K = 256, R = 64 and b = 0.15 for curve secp-256-k1 [START_REF]SEC 2 : Recommended Elliptic Curve Domain Parameters[END_REF] (aka the Bitcoin's curve). In Figure 1, we represent mean values over 50 executions of the algorithms. Standard deviations to the average results are illustrated by error bars. These simulations are extremely time consuming as w increases. This is why results are missing for w > 7. This is probably why the simulation results in [START_REF] Schindler | Efficient Side-Channel Attacks on Scalar Blinding on Elliptic Curves with Special Structure[END_REF] are scattered over a few parameters. We believe that Figure 1 provides a complementary point of view on the efficiency of the correction algorithm of [START_REF] Schindler | Efficient Side-Channel Attacks on Scalar Blinding on Elliptic Curves with Special Structure[END_REF] 10 . Notably, it is interesting to remark that the impact of the window size is not regular and that window sizes ranging from 3 to 6 produce similar success rates.

We will see in next Section how the algorithms can be improved in both efficiency and effectivness.

Improved Algorithms

First Observations As remarked earlier (and in [START_REF] Schindler | Efficient Side-Channel Attacks on Scalar Blinding on Elliptic Curves with Special Structure[END_REF]) w cannot be too small for the algorithm to work. The reason is that the probability estimation (from the call to EvaluateProbability() in Algorithm 1) is better when w increases. As a matter of fact, the EvaluateProbability() procedure estimates the probability of observing the noisy blinded scalar d knowing two w-bit word predictions on two separate w-bit sections of d . Therefore, if w is too small this estimation is not good enough to distinguish good predictions from wrong ones (Figure 1 illustrates this behaviour).

Our proposal will nevertheless reduce w to its minimum (w = 1) and cope with the above mentioned issue by calling EvaluateProbability() (step 12 of Algorithm 1 and step 12 of Algorithm 2) over the two (w + i -1)-bit words r and d instead of the two w-bit words r and d .

However, doing this directly has a desastrous effect. On the first iteration of Algorithm 1, many r are actually wrongly estimated (even if they were the best candidates selected in Algorithm 2) and they remain wrong for the rest of the execution until the end. However, the original implementation deals naturally with them because future probability estimations with future w-bit predictions on these wrong r quickly decrease to give these wrong starts lower and lower weights in the computation of the best candidate for the bits of d. If we apply our first proposal directly, these wrong starts will keep their high probability estimations for more iterations (since we now involve their successful past in the computation). These wrong starts will then create more chance to choose a wrong candidate for the guessed bit of d. We propose here to solve this problem by loosening the selection procedure of the r .

Keeping a List of the Blinding Factors Best Candidates In a nutshell, the idea is to modify Algorithms 1 and 2 such that instead of working on a single value r (for each < N ) which is updated bit-by-bit at each iteration (step 14 of Algorithm 2), the algorithms will keep a pool of good estimates for r . Intuitively, if the list of potential candidates is large enough, it will contain the correct value of r for the current iteration. We will see that small list sizes are enough to match and exceed the original algorithm effectiveness.

Algorithms Improvements in Detail Algorithms 3 and 4 describe in detail the full improvements. Concretly, the modifications compared to Algorithms 1 and 2 are threefold:

the window size w is forced to its minimum (w = 1) and then does not appear in the algorithm anymore. the list of recovered blinding factors at iteration i, i.e. {r } <N where the r are defined over i -1 bits, is replaced by a 2D array (denoted Lr11 ) of N × L best candidates for each r . This array is updated at each iteration of Algorithm 4. Note that during the first iterations (i log 2 (L)), all possible candidates are kept until the list is full. the probability estimation is done over t msb of r and d instead of the w msb in Algorithm 1. Note that if t R, then all the bits of r and d are considered in the probability estimation at each iteration.

Together, the last two changes aim at decreasing the value of w to its minimum and therefore reduce the algorithm complexity without damaging too much the algorithm success rate. The overall complexity of steps 1 and 2 becomes then O(N × L). (More precisely, Step

Simulation Results and Comparisons

We conducted simulations in order to evaluate and compare the new algorithms to the original proposition of [START_REF] Schindler | Efficient Side-Channel Attacks on Scalar Blinding on Elliptic Curves with Special Structure[END_REF]. As in Figure 1, the results give the average (over 50 tentatives) number of bits of d guessed correctly before a wrong bit appears, as a function of the number of traces N used for the attack. This number of correct bits are majored by R since the algorithms studied here stop when the R lsb of d are found. Apart from R and K, various parameters have an impact on the efficiency and the effectivness of the algorithms, notably:

L: the maximum size of the best candidate pool for the blinding factors r for each noisy blinded scalar. We recall here that the complexity of Algorithms 3 and 4 increase linearly with L; w: the window size, only the original algorithms are affected by w, the complexity of Algorithms 1 and 2 increase exponentially with w; t: the number of bits involved in the probability estimation of r and d with respect to d .

Our first simulations are conducted to find the best empirical value for t. Once t is chosen, we will focus on the parameter L and its impact on the effectiveness (compared to the original algorithm when w changes).

Recall that t has no impact on the computational cost of the algorithms, so it can be chosen freely. Figure 2 displays simulation results for the new algorithm with the parameter t taking its values in {6, 8, 10, 16, 24, R} 12 and small values for L. It appears that t = 16 provides better results than greater or smaller values of t in our setup (K = 256, R = 64). A Brief Analysis of the Final Vertical Side-channel Analysis (Attack Step 3)

Assuming that the attacker went succesfully through the overall attack path described in Section 1.2, we analyse here the success rate of the last step of the attack: the vertical side-channel attack given a set of noisy blinded scalars (or exponents in the case of RSA) { dl } l<N and their corresponding blinding factors {r l } l<N . A simple attack algorithm follows: Set a small window size w (e.g. w = 4), the vertical attack will find each bit of the secret scalar (resp. exponent) d iteratively with predictions over w consecutive bits. In the case of ECC, where the order of the elliptic curve E is public, at iteration i the attacker possesses i -1 bits of d (as well as the blinding factors {r l } l<N ). Then, for each of the possible next w bits of d (denoted dw , which takes values in F 2 w ), the attacker can predict the ith to (i + w -1)th bit of the N real blinded scalars. The attacker can then select the hypothesis on dw that predicts the best 13 the observations { dl } l<N and only keep the first bit of it ( dw mod 2 which becomes the ith bit of d) and then move to the next iteration. The overall attack complexity is O(2 w N K).

In the case of RSA, the value of φ(n) (or φ(p) for a CRT implementation) is unkwown, the attack will then process similarly but guessing the bits of φ(n) (resp. φ(p)) simultaneously with the bits of d. Hence, at each iteration, the attacker will go through all values of the next w bits of d as well as the next w bits of φ(n) (resp. φ(p)) and, for each of them, predict w bits of the N blinded exponents and confront them to w bits of the N noisy blinded exponent. The overall attack complexity is O(2 2w N K).

Figure 5 shows the average number of correctly guessed bits of d for ECC (K = 256) and RSA (K = 1024) and for various values of w ∈ {1, 2, 4}. We conducted these simulations for three bit error rates, up to b = 0.3, which is larger than any bit error rate considered in this paper. These results confirm the claim that few tens of noisy blinded scalars (resp. exponents), given their blinding factors, are enough to find the secret scalar (resp. exponent). 13 in our simulations we simply used the majority rule: the number of matching bits between the predictions and the noisy blinded scalars. This step will perform even better by using the side-channel traces in a more classical side-channel attack but the majority rule was already enough for our needs.

  (R > 44, b = 0.2) and (R > 76, b = 0.15) cannot be handled successfully by the Alternate Attack whereas we have shown that (R = 64, b = 0.2) and (R = 96, b = 0.15) are achievable in practice when several millions of scalar multiplications can be observed.

Fig. 1 .

 1 Fig. 1. Simulations for K = 256, R = 64, b = 0.15 on curve secp-256-k1.

Fig. 2 .

 2 Fig. 2. Simulation Results K = 256, R = 64, b = 0.15.

Fig. 5 .

 5 Fig. 5. Average number of correct bits of d (over 20 trials).

Table 1 .

 1 Maximum R-values for Schindler and Wiemers's Algorithm 3[START_REF] Schindler | Power attacks in the presence of exponent blinding[END_REF] Table 12]

		2 40	36	16	4
	1000	2 45	96	52	28
	100000	2 50	136	76	44

Table 2

 2 identify parameters that would lead to 2 60 or larger number of D NAF computations, making this attack hardly possible in practice. 11.6 2 14.7 2 18.0 2 21.5 2 25.3 64 2 5.8 2 10.9 2 16.2 2 21.9 2 28.0 2 34.4 2 41.4 2 48.9 96 2 8.2 2 15.7 2 23.7 2 32.2 2 41.3 2 50.9 2 61.3 2 72.5 128 2 10.5 2 20.6 2 31.2 2 42.5 2 54.5 2 67.4 2 81.2 2 96.1

	b	0.05	0.10	0.15	0.20	0.25	0.30	0.35	0.40
	R
	32	2 3.5	2 6.0	2 8.7	2

Table 2 .

 2 Number of scalar multiplications (for a success rate > 50%)

  1 mod 2 w )

	Parameter	: Iteration i
	Parameter Input	: Window size w, bit error rate b : { d } <N : N noisy scalars
	Input	: {r } <N : i -1 lsb of the recovered blinding factors
	Input	: d mod 2 i-1 : i -1 lsb of the recovered scalar
	Output	: d

* : best guess for d mod 2 w+i-1 1 P ← float 1D array of size 2 w initialized with zeros; 2 // For each possible value of the next w bits of the secret scalar; 3 for d ← 0 to 2 w -1 do 4 // Prediction of the w + i -1 lsb of the scalar knowing the first i -1 bits;

5 d ← d × 2 i-1 + d mod 2 i-1 ;

6 // For each noisy blinded scalar; 7 for ← 0 to N -1 do 8 // For each possible value of the next w bits of the random r ; 9 for r ← 0 to 2 w -1 do 10 r ← r × 2 i-1 + r ; 11 // Predict w + i -1 lsb of d ; 12 d ← (r × E + d) mod 2 w+i-1 ; 13 // Define d , the w msb of d ; 14 d ← d /2 i-1 ; 15 // Compute the probability of observing d , knowing d blinded by r ; 16 p ← EvaluateProbability(r , d , d , i, w, b ); 17 P [ d] ← P [ d] + p; 18 d * ← argmax(P ) × 2 i-1 + (d mod 2 i-1 ); Return : d * Algorithm 1: Phase 1, Step 1 of [15, Algorithm 4]

  For each possible value of the next w bits of the random r ;

			: Iteration i
		Parameter Input	: Window size w, bit error rate b : { d } <N : N noisy scalars
		Input Input	: {r } <N : i -1 lsb of the recovered blinding factors : d * : w + i -1 lsb of the recovered scalar from Step 1
		Output	: d mod 2 i
		Output	: {r } <N : i lsb of the recovered blinding factors
	1 // For each noisy blinded scalar;
	2 for ← 0 to N -1 do
	3	P ← float 1D array of size 2 initialized with zeros;

4 // 5 for r ← 0 to 2 w do 6 r ← r × 2 i-1 + r ; 7 // Predict w + i -1 lsb of d ; 8 d ← (r × E + d * ) mod 2 w+i-1 ; 9 // Define d , the w msb of d ; 10 d ← d /2 i-1 ; 11 // Compute the probability of observing d , knowing d * blinded by r ; 12 p ← EvaluateProbability(r , d , d , i, w, b ); 13 P [r mod 2] ← P [r mod 2] + p; 14 r ← argmax(P ) × 2 i-1 + r ; 15 d * ← d * mod 2 i ; Return : d * , {r } <N Algorithm 2: Phase 1, Step 2 of [15, Algorithm 4]

  1 runs 4 × N × L loop iterations.)

		Parameter	: Iteration i
		Parameter	: Bit error rate b
		Parameter	: Max list size L for the candidate lists of r
		Parameter	: Window size t: this size defines the number of msb to select for probability
			estimations
		Input	: { d } <N : N noisy scalars
		Input	: Lr array of dimension N × L containing, for each < N , the L best
			candidates r
		Input	: d mod 2 i-1 : i -1 lsb of the recovered scalar
		Output	: d mod 2 i
	1 P ← float 1D array of size 2 initialized with zeros;
	2 // For each possible value of the next bit of the secret scalar;
	3 for d ← 0 to 1 do
	4	// Prediction of the i lsb of the scalar knowing the first i -1 bits;
	5	d ← d × 2 i-1 + d mod 2 i-1 ;
	6	// For each noisy blinded scalar;
	7	for ← 0 to N -1 do
	8	// For each possible value of the next bit of the random r ;
	9	for r ← 0 to 1 do
	10		// For each r in the list Lr[l];
	11		for s ← 0 to L -1 do
	12		r ← Lr[l][s];
	13		if r == -1 then
	14		// go to next r value;
	15		Break;

16 r ← r × 2 i-1 + r ; 17 // Predict w + i -1 lsb of d ; 18 d ← (r × E + d) mod 2 i ; 19 // Define d t , the t msb of d ; 20 d t ← d /2 max(0,i-t) ;

21 // Define r t , the t msb of r ; 22 r t ← r /2 max(0,i-t) ; 23 // Compute the probability of observing d , knowing d blinded by r t ; 24 p ← EvaluateProbability(r t , d t , d , max(0, i -t), min(t, i), b ); 25 P [ d] ← P [ d] + p; 26 d * ← argmax(P ) × 2 i-1 + d mod 2 i-1 ; Return : d * Algorithm 3: Improved Algorithm Step 1

A more formal notation would be {T } ∈Z;0 <N .

More precisely, they use this distinguisher to find blinding factor collisions (ri = rj) by computing HW(NAF( didj)) (which corresponds to D NAF i,j when ri = rj).

A learning phase is conducted prior to the attack on a similar device where scalar multiplication inputs and randoms can be chosen, e.g. a template building or a deep-learning training phase.

relying on the fact that an RSA modulus n and φ(n) share half of their msb. See[START_REF] Schindler | Power attacks in the presence of exponent blinding[END_REF] for more details.

the authors of[START_REF] Schindler | Generic power attacks on RSA with CRT and exponent blinding: new results[END_REF] managed to recover 2R msb of φ(p) based on continued fractions.

N is estimated as follows: N = 2/ CDF (R+1, b ) (0). To estimate the attack success rate, i.e. the chance that actually 2 or more noisy blinded scalars are correct on their R + 1 msb, it is equal to s = 1 -CDF (N,CDF (R+1, b ) (0))[START_REF] Bauer | Horizontal and vertical side-channel attacks against secure RSA implementations[END_REF]. Our values of N imply then a 60% success rate. Taking 2N instead of N in Table2would increase the attack success rate to

90%.

The array Lr must be initialized to an integer array of dimension N × L with all cells initialized to -1 but the first column (Lr[i][0] for all i < N ) which must be initialized to 0.

for t = R, at iteration i, all bits of r and d are considered for probability estimation, this version is labeled "Full"

Figure 3 compares the original algorithm for various values of w to the new algorithm (with t = 16) for various values of L. From these results, we have equivalent effectivness between the original alg. with w = 7 and the new alg. with L = 4. However, the new algorithm is 2 10 times more efficient than the original algorithm for these parameters. The gap of efficiency seems to increase with w and L since, for another pair of results (w = 8 for the original algorithm and L = 8 for the new algorithm) the multiplicative factor between both algorithm complexity is doubled (2 11 ) whereas the new algorithm clearly outperforms the original one. Finally, let us also remark that the new algorithm with L > 16 reaches the limit of 64-bit correctly recovered on average (i.e. a 100% success rate since 64 is the maximum number of recovered bits) in less than 10000 traces. We recall that these algorithms must reach the end with correct 64-bit lsb of d (since in our simulation we choose R = 64) for the overall attack to be successful.

Finally, Figure 4 provides simulation results for R = 64, 96, 120 for the new algorithm (t = 16, L = 32) and two different bit-error-rate ( b = 0.15 and b = 0.13). These results show, in accordance with original results from [START_REF] Schindler | Efficient Side-Channel Attacks on Scalar Blinding on Elliptic Curves with Special Structure[END_REF], that when elliptic curves with structured-order are used, R must be chosen strictly larger K/2 in practice for an effective side-channel countermeasure.

Conclusion and Future Work

In this paper we exhibited algorithms to recover a secret scalar from many noisy blinded scalars (e.g. outputs of horizontal side-channel attacks over blinded scalar multiplications) when blinding factors are over more than 32 bits and bit error rate is larger than 10%. Our propositions, both in the general case of random-order elliptic curves as well as in the specific case of structured-order elliptic curves, outperform the best known algorithms for these parameters.

Apart from a series of articles from Schindler et al. works on this topic are rather scarse in the literature. This is however a very important aspect of practical side-channel analysis over public key cryptography and we believe there are still room for improvements. Another interesting avenue for future work is to formulate theoretic bounds on the attacker capability to recover the secret scalar given a set of noisy blinded scalars.


Nicolas Jouandeau

Zhi Yan

Improved Trade-based Multi-robot Coordination

Team work is essential to multiple mobile robot systems. An important question is, which robot should implement which action? In our previous work, we presented a trade-based task allocation approach for coordinated multirobot exploration, which simulates the relationship between buyers and sellers in a business system, to achieve dynamic task allocation by using a mechanism of unsolicited bid. This paper still addresses the problem of coordinating multi-robot exploration while presents an improved trade-based approach to raise the efficiency of task allocation by using the Hungarian method. The proposed approach has been implemented and evaluated in simulation. The experimental results demonstrate the total exploration time can be significantly reduced by the improved trade-based approach compared to previous approaches.

I. INTRODUCTION

Exploration of an unknown environment is a fundamental problem in robotics. It requires an agent to cover the unknown area while building a model of the environment from sensor data so as to achieve the purpose of exploration. Some exploration missions are very well known, such as the Moon exploration and the Mars exploration.

Compared with single agent, using multiple agents has a number of potential advantages [START_REF] Dudek | A taxonomy for multi-agent robotics[END_REF], [START_REF] Cao | Cooperative mobile robotics: Antecedents and directions[END_REF]. For example, a team of robots is able to complete an exploration mission faster than a single robot. The key to gain the advantages is coordination. Without coordination, it will not only lower mission efficiency, but also lead to the failure of the entire mission in extreme cases. An essential problem of coordination is task allocation, in other words, we need to answer such a question: which agent should execute which task [START_REF] Gerkey | A formal analysis and taxonomy of task allocation in multi-robot systems[END_REF]? Fig. 1 shows an example of multi-agent coordination. Four robots explore an unknown environment cooperatively. The result of task allocation is that different robots are responsible for exploring different rooms.

There are generally two types of mechanisms for task allocation, centralized and decentralized. The advantage of centralized mechanism is that the optimal plans can be found. Nevertheless, this mechanism is ineffectual for large teams with more agents. There is no central planner in the decentralized mechanism. Robots use locally observable informations to make their plans. This mechanism has a good adaptability and strong robustness, but the solutions it got are often sub-optimal.

The investigation context of this paper is the problem of exploring an unknown environment with a homogeneous team of cooperative robots. The objective is to explore the entire environment, while minimizing the time needed to complete the overall exploration. In our previous work [START_REF] Yan | Multi-robot decentralized exploration using a trade-based approach[END_REF], we developed a lightweight and robust decentralized system based on trade rules for coordinated multi-robot exploration, which is designed to simulate the relationship between buyers and sellers in a business system. The robot which plays the role of buyer makes a request for an exploration task to the robot which plays the role of seller, then the seller robot analyzes the received requests and assigns the tasks to the buyer robots reasonably. An obvious characteristic of this technique is the ability to assign multiple tasks to multiple robots at a time. Nevertheless, the previous strategy can not guarantee the global optimal task allocation plan for the whole exploration mission will be found. Therefore, in this paper, we present an improved trade-based approach for efficient task allocation, in which the buyer robot is able to make a request for several exploration tasks to the seller robot, and the latter will assign the exploration tasks to the buyer robots by using the Hungarian method [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF].

The remainder of the paper is organized as follows: Section II describes an overview of some related works; followed by the discussion of the requirements of multirobot exploration, described in Section III; subsequently, Section IV describes our improved trade-based approach; Section V describes the experimental results obtained with our approach; the paper is concluded in Section VI.

II. RELATED WORK

Yamauchi [START_REF] Yamauchi | Frontier-based exploration using multiple robots[END_REF] presented a cooperative, decentralized and fault-tolerant multi-robot exploration strategy based on the concept of frontiers. In his approach, robots share perceptual information, but maintain separate global maps. Each robot makes its own decisions about where to navigate. Whenever a robot arrives at a new frontier, it sweeps its sensors and constructs a local evidence grid representing its current surroundings. This local grid is integrated with the robots global grid, and also broadcast to all of the other robots.

Burgard et al. [START_REF] Burgard | Collaborative multi-robot exploration[END_REF] designed a coordination component based on the approach of Yamauchi. This component applies a probabilistic method which takes the cost of reaching a frontier and its utility into account simultaneously. The cost is given by the distance of traveling to a frontier and the utility is given by the size of the unexplored area that a robot can cover from this frontier with its sensors. Whenever a frontier is assigned to a robot, the utility of the visible unexplored area of this frontier is reduced to all of the other robots.

Gerkey and Matarić [START_REF] Gerkey | Sold!: Auction methods for multirobot coordination[END_REF] proposed an auction-based task allocation approach for decentralized multi-robot coordination. The auction proceeds in five steps: task announcement, metric evaluation, bid submission, close of auction and progress monitoring/contract renewal. This strategy has been implemented and tested in a general task allocation system called MURDOCH, which is built upon a principled, resource centric and publish/subscribe communication model.

Zlot et al. [START_REF] Zlot | Multi-robot exploration controlled by a market economy[END_REF] introduced a market-based task allocation approach for multi-robot exploration. This technique borrows the market architecture which seeks to maximize benefit while minimizing cost, thus aiming to maximize utility. The benefit is information gained by visiting a goal point, the cost is the estimated distance traveled to reach the goal, then the utility is the difference between the benefit and the cost.

Besides, there are some other approaches developed with various policies [START_REF] Rekleitis | Multi-robot collaboration for robust exploration[END_REF], [START_REF] Ko | A practical, decision-theoretic approach to multi-robot mapping and exploration[END_REF], [START_REF] Wu | Voronoi-based space partitioning for coordinated multi-robot exploration[END_REF], [START_REF] Stachniss | Efficient exploration of unknown indoor environments using a team of mobile robots[END_REF], [START_REF] Yamauchi | Mobile robot exploration and map-building with continuous localization[END_REF].

III. MULTI-ROBOT EXPLORATION

There are two basic requirements in multi-robot exploration known as robot navigation and task allocation.

Mobile robot navigation includes three fundamental problems: map learning, localization and path planning. In a given environment, a robot should be able to determine a collision-free trajectory from its current location to a desired target location. This is known as path planning. To compute the path, a map of the environment should be known, it is built from a set of sensor data acquired by the mobile robot. The problem of map learning is commonly referred as simultaneous localization and mapping (SLAM). During the path following process, the mobile robot needs to know its exact position and orientation in the environment at all times. This is known as localization. A multi-robot navigation system should also address the possible interference between robots. For instance, a robot should take the motion of other robots into account to avoid congestion or collision [START_REF] Yan | Sampling-based multi-robot exploration[END_REF].

Multi-robot task allocation (MRTA) should handle the problem of determining an appropriate mapping between robots and tasks. A task can be an exploration of the unknown space of environment. The key of the effective task allocation for multi-robot systems is to iterate the assignment in order to deal with changes in the tasks, the robots and the environment [START_REF] Gerkey | A formal analysis and taxonomy of task allocation in multi-robot systems[END_REF].

IV. IMPROVED TRADE-BASED APPROACH

A business system is mainly made up of buyers and sellers. The relationship between them is known as exchange relation. Buyers can use money to purchase goods or services from sellers, then sellers collect money and sell goods or services to buyers. Our approach in this paper is built on the simulation of this relationship, the model is as follows:

Trade =< R, M, T, P,C > (1)
where R represents the mobile robots. M represents the whole mission to be completed, which consists of several tasks, M = {m 0 , m 1 , . . . , m n }. T represents the time needed (i.e. the benefit obtained) to complete the whole mission. P signifies the task allocation plan. C signifies the set of cost to complete the whole mission, C = {c 0 , c 1 , . . . , c n }.

The proposed approach contains two phases which are role allocation and task allocation.

A. Role allocation

The role allocation is to solve the problem of which robot should be buyer and which robot should be seller. A simple and effective way is to number the robots in the team, and the robot which is not in task broadcast its number, then evaluates the received numbers from others after a period of time. If there is a number smaller than its own, then this robot will play the role of buyer. The details of our implementation are given in Algorithm 1.

B. Task allocation

Once the idle robot has determined its own role, it should enter the task allocation phase. For the buyer robots, the first thing to do is to choose one or more tasks to bid for and estimate the corresponding task cost. In the present study, the task is to explore an unknown region identified by topologizing the grid map of the environment [START_REF] Yan | Sampling-based multi-robot exploration[END_REF], and the estimated task cost is the distance between the robots' current position and the target position computed by the wavefront propagation algorithm [START_REF] Lavalle | Planning Algorithms[END_REF]:

c m r = wave f ront(pos(r), pos(m)) (2)
where c m r represents the estimated task cost c for the robot r to complete the task m. After completing the cost estimate, the buyer robot should send a purchase request to seller robot Algorithm 1 Trade-based role allocation for robot r 1: if robot r is not in task then for each received number r do end if 15: end if for the new task. We called this model the unsolicited bid mechanism. The purchase message contains three information:

pums r = {r, M ,C } M = {m i , i ∈ N + },C = {c i , i ∈ N + } M wave f ront -→ C (3)
where pums r represents the purchase message pums sent by buyer robot r, r in the message means the number of the buyer robot, M signifies the set of identifiers of the task, and C denotes the set of estimated task cost c i where c i = c m i r . After the bidding process, the buyer robot will receive a message on whether to get the task from the seller robot or not. If the buyer robot gains a task, it will enter into the motion planning process. Otherwise, it will return to the role allocation phase for a new task.

For the seller robot, homogeneously, the first step is to select one or more tasks and estimate the corresponding task cost (the seller robot itself is also the object of task allocation). Then it should collect the purchase message from the buyer robot within a given bidding period. After this period, the seller robot will stop receiving the purchase message and evaluate the purchase requisitions received by using the Hungarian method, then assign the tasks to each buyer robot for reasonably. The Hungarian method is a combinatorial optimization algorithm which can solve assignment problems in polynomial time O(n 3 ). The implementation details can be summarized by the following four steps:

1) Construct a n × n cost matrix, n is the total number of the robots which have made task request. If there are more tasks than robots or conversely, we add zero columns or rows. 2) Subtract the elements of each row by the row minimum. Afterwards, subtract the elements of each column by the column minimum. 3) Find the minimum number of lines required to cover all the zeros across rows and columns. If the number of the lines is n, the optimal task allocation plan can be given by selecting a combination from the modified cost matrix in such a way that the sum is zero. Otherwise, go to step 4. 4) Find the smallest element which is not covered by any of the lines, then subtract it from each uncovered element and add it to each covered element. Go back to step 3. Suppose the seller robot has received two purchase messages: {r 1 , {m 0 , m 1 }, {c 0 , c 1 }} and {r 2 , {m 0 }, {c 0 }}, then the 3 × 3 cost matrix (include the seller itself, for example, {r 0 , {m 1 }, {c 1 }}) could be represented below:

A =   ∞ r 0 (c 1 ) 0 r 1 (c 0 ) r 1 (c 1 ) 0 r 2 (c 0 ) ∞ 0   (4)
The task allocation message sent to buyer robot includes two information:

tams r = {r, m} (5)
where tams r represents the task allocation message tams sent by seller robot r, r in the message means the number of the seller robot, m signifies the identifier of the task. The robot which has completed a task will update its task list, and also broadcast to all teammates.

V. EXPERIMENTS Our approach has been implemented and evaluated in Stage [START_REF] Gerkey | The player/stage project: Tools for multi-robot and distributed sensor systems[END_REF] a 2.5D multiple-robot simulator. The simulation experiments were conducted by using a group of Pioneer 2-DX robot equipped with a laser range finder which can provide 361 samples with 180 degrees field of view and a maximum range of 8 meters. Each robot can localize itself based on an abstract localization device which models the implementation of SLAM. The ratio between real-world time and simulation time is about 1:3. All experiments reported in this paper were carried out on a system with an Intel Core 2 Duo E8400 3.00GHz processor, an Intel Q43 Express chipset and two DDR2 800MHz 1024MB dual channel memory.

To evaluate our trade-based approach, we compared our approach to an auction-based approach and used a different number of robots to conduct several experiments in various environments, Fig. 2 depicts two maps used in our simulation which are enclosed spaces with 14 meters long and 16 meters wide. The exploration team size is varied from two to six robots. The results of our experiments is given in Fig. 3. Fig. 3. shows a comparison of the exploration time between our improved trade-based approach and an auctionbased approach respectively in the map A (top) and the map B (bottom). From this it can be seen that the exploration time by using our approach is successfully reduced compared to the auction-based approach. On the one hand, the proposed approach introduced the unsolicited bid mechanism to support the ability to assign multiple tasks to multiple robots at a time. On the other hand, it integrated the Hungarian method, which is an efficient method for solving assignment problems, to improve the coordinated planning of the entire multiple robot system. Moreover, due to the NP-hard of multi-robot exploration, the experimental results is an nonuniform linear dispersion.

VI. CONCLUSIONS

In this paper, we presented an improved trade-based task allocation approach for coordinated multi-robot coordination. The trade-based method is designed to simulate the relationship between buyers and sellers in a business system, and dynamically allocate the task by using a unsolicited bid mechanism. However, the origin version can not guarantee the global optimal solution will be found, i.e. the task allocation plan for the whole mission is sometimes not optimal. This paper introduced the Hungarian method to raise the efficiency of task allocation. In contrast to the previous strategy, this version allows the buyer robot sends the purchase request to the seller robot for several tasks, then the seller robot evaluates the purchase requisitions and assign the tasks by using the Hungarian method. The experimental results demonstrate that, the time needed to accomplish the exploration mission has been significantly reduced by the improved trade-based approach.

Fig. 1 .

 1 Fig. 1. Four robots explore an unknown environment cooperatively. The green robot has completed the exploration of room 0, is moving to next room. The yellow robot is exploring room 1. The red robot is exploring room 2, and the orange robot is moving to room 3.

Fig. 2 .

 2 Fig. 2. Two environment maps used in our simulation: map A (left) and map B (right).

Fig. 3 .

 3 Fig.3. Exploration time of our approach compared to an auction-based approach for the map A (top) and the map B (bottom).


Aurélien Cadiou
email: aurelien.cadiou@insa-lyon.fr

Sébastien Henry
email: sebastien.henry@univ-lyon1.fr

Vincent Cheutet
email: vincent.cheutet@insa-lyon.fr

Carole Eyssautier

A PLC Variable Identification Method by Manual Declaration of Time-stamped Events

The fourth industrial era, the digitisation of production and the emergence of digital twin involve the hyper-connection of all industrial equipment and especially Automated Production Systems (APSs). Nevertheless, the acquisition of data within these machines remains complicated. APS is an expensive invest, composed with many heterogeneous equipments, they are made for having a long lifespan. Hence, industries are composed with old equipment and it is not possible to wait new industry 4.0-compatible APSs to follow the digital evolution. A solution is to retrieve data from the APSs through its Programmable Logic Controller (PLC), with industrial network, like the Modbus. The PLC knows the APS state with sensors and pilots the APS with actuators, all this information is stocked into variables in memory of PLC, referenced with addresses. Due to several factors, such as heterogeneous data, lack of PLC program documentation or no automation specialist, the data collection is a complicated and time-consuming task. The difficulties are to link desired information and the memory address where it is stored. The aim of this contribution is to propose a method for identifying address, through photos of APS, an historical of memories values and an a posteriori declaration of viewed events with photos. This method must be suitable for non-specialists.

Introduction

The Industry 4.0 is a new industrial revolution, with the aim to improve industrial competitiveness, efficiency and flexibility. This important revolution has several aspects, such as smart factory, software/systems engineering, human-machine interaction, embedded systems, interconnection between equipment, communication technologies, big data, artificial intelligence or Digital Twin (DT) [START_REF] Negri | A Review of the Roles of Digital Twin in CPS-based Production Systems[END_REF][START_REF] Schlund | Describing the technological scope of Industry 4.0 -a review of survey publications[END_REF]. All of these require a large amount of data, sometimes collected in real-time, and data exchanges to drive production and achieve objectives [START_REF] Lucas-Estan | Communication and Data Management in Industry 4.0[END_REF].

The objective of industrial plants is to produce goods and this is done with Automated Production System (APS). An APS could be composed with many equipment, heterogeneous in role, functionalities, age, machine builder, Programmable Logic Controller (PLC), etc. Production systems are often composed by special machines, they are expensive and made to last, with the necessity to amortise them. They can be up to 10 or 15 years old. It is not possible for industrial companies to change all APSs for being "industry 4.0" and it is not possible to wait the depreciation of each equipment to change them individually. The smart-industry transformation would take then many and many years.

The APS are piloted with the PLCs, sensors are connected to it inputs and actuators are connected to it outputs. The PLCs pilotes its outputs depending on its inputs and its program, thus it changes the state of the APS.PLC are programmed with proprietary software and code downloaded into PLC often have not memories name nor comments. Furthermore, due to the long lifespan of APSs, the PLC programs are not well documented, the program evolves and documentation is not updated, or, sometimes, documentation is lost.

These difficulties can be overcome by adding Industrial Internet of Things (IIoT) sensors on APSs, in order to retrieve state. Even if this solution gains interest these last years, it is more expensive and requires an IIoT infrastructure, mechanical interventions on APSs for installation and long-term maintenance, involving production shutdowns.

Moreover, the installation of IIoT sensors is not possible in all industries and the PLC still the best supplier of APS state. Retrieving data from PLCs is applicable for industries such food-processing, where health standards are mandatory, production pace is high involving production stops are complex to plan and equipment is ageing and unique with little knowledge capitalised with time.

The presented difficulties are not always there. It is possible to classify three cases for retrieving APS state. The first is the most simple, it is when the PLC program is totally known, and in this case, the OPC-UA server could facilitate the collection of data. The OPC-UA is a machine-to-machine protocol and it specifies the structure of semantic information models and could be used by a constructor for open data exchange (like PackML [START_REF] Barbieri | A PackML-based Design Pattern for Modular PLC Code[END_REF] or AutomationML [START_REF] Henßen | Interoperability between OPC UA and AutomationML[END_REF]) with their equipment [START_REF] Ghazivakili | Industrial data-collector by enabling OPC-UA standard for Industry 4[END_REF].

The two other cases are appropriate when too little information about the PLC program are known, in such a way PLC is considered like a black-box. The PLC data collection is here complex. Several factors come into play, such as heterogeneity of data, multitude of industrial protocols, no knowledge of the PLC program, lack of documentation or up-to-date documentation [START_REF] Younis | Formalization of existing PLC Programs: A Survey[END_REF][START_REF] Barbieri | A PackML-based Design Pattern for Modular PLC Code[END_REF][START_REF] Hennig | Connecting programmable logic controllers (PLC) to control and data acquisition a comparison of the JET and Wendelstein 7-X approach[END_REF], low degree of automation in enterprises [START_REF] Uhlemann | The Digital Twin: Demonstrating the Potential of Real Time Data Acquisition in Production Systems[END_REF] as well as the seniority of many industrial equipment and their PLCs.

In this context, this contribution proposes a solution which purpose is to facilitate the data collection in PLC, in particular the identification of memory addresses of variables. Compared to the easiest possibility of adding IIoT sensors to obtain the desired information, the proposed solution aims at offering a simple and quick protocol, performed in two successive and punctual steps. Once these steps have been completed, variables are identified without the extra use of artifice. It consists of reverse-engineering of PLC programs. This contribution is focused on PLC with Modbus communication network.

This paper is structured as follows. After a brief analysis of the scientific literature on variable identification, section 3 describes the general scenario about usage and precise the entire procedure. Finally, an industrial case study is presented in section 5 with results detailed, analysed and discussed.

Related works

Reverse engineering of PLC programs is often necessary. This is mainly due to a lack of documentation: never created initially, lost or not updated once the modifications have been made. Information about PLC is used to make modifications to meet new production demands, re-implementations when new controller hardware is necessary [START_REF] Younis | A Formal Method Based Re-Implementation Concept for PLC Programs and Its Application[END_REF], establish connections for collecting data or Machine To Machine (M2M) connections [START_REF] Roblek | A Complex View of Industry 4.0[END_REF].

In the literature, reverse engineering could be classified in two categories, depending on knowledge about PLC.

For the first category, the PLC program is available, with or without a name or comments. In this situation, a static analysis of the program is performed. The code is converted and parsed to find addresses, labels, routines, contacts, coils, statements, etc. The result of this treatment is converted into XML files [START_REF] Younis | A Formal Method Based Re-Implementation Concept for PLC Programs and Its Application[END_REF] or used for automatic generation of OPC server tags [START_REF] Koehler | Automated, Nomenclature Based Data Point Selection for Industrial Event Log Generation[END_REF]. It is only possible when the PLC program is written in structured text or instruction list [START_REF] Younis | Formalization of existing PLC Programs: A Survey[END_REF][START_REF] Commission | International standard IEC 1131-3, Programmable Controllers, Part 3: Programming Languages[END_REF].

For the second category, the PLC program is not known or readable, then the PLC is considered as a black-box. Some research investigating the reverse engineering of PLC programs with the observation of inputs and outputs [START_REF] Estrada-Vargas | A Black-box Identification Method for Automated Discrete Event Systems[END_REF][START_REF] Bekrar | Off-line identification for a class of discrete event systems using safe Petri nets[END_REF]. The main goal is to obtain a model of the PLC program, without any consideration of inputs and outputs names. The internals signals of PLC are not used with these methods [START_REF] Theiss | PLC-integrated process monitoring and prediction of the resulting real-time load[END_REF].

The event sequence similarity can be helpful. Works about the representation of temporal information propose methods to compare and find similarities between several event sequences [START_REF] Lee | Signals and Systems[END_REF][START_REF] Hetland | A survey of recent methods for efficient retrieval of similar time sequences[END_REF]. They need a lot of data in order to compute and they use, for instance, data mining approaches [START_REF] Moen | Attribute, Event Sequence, and Event Type Similarity Notions for Data Mining[END_REF].

The latest seems pertinent in out context, but no current implementation is applicable and new perspectives can be explored.

General scenario

The outline of our method is based on recording the physical state of APS and the digital state of the machine, reflect on physical state, in order to compare and link them. When links are established, the user has the memories linked to different states of APS, such as "machine in fault", "conveyor running", "part produced", "temperature of furnace", etc.

The physical state is saved through photographs, and the digital state of APS, via data collection from PLC, both are saved at the same time. The data collection is possible using Modbus protocol, having a 4 normalised addresses ranges :

• coil numbers start with 0 and span from 00001 to 09999, • discrete input numbers start with 1 and span from 10001 to 19999, • input register numbers start with 3 and span from 30001 to 39999, • holding register numbers start with 4 and span from 40001 to 49999.

The proposed method consists into finding the right, or the best, memory address for a state. The method will compare the physical evolution of desired state with evolution of memories for finding the most convenient. The user describes the physical evolution by using photographs. A program was developed for taking photographs, retrieve values of memories and execute a scoring algorithm for determine the most relevant memories. Based of this classification, the final user can retrieve the most consistent addresses.

Retrieve state of the APS

A camera takes photographs of all the APS or a part of the APS. If the user wants to retrieve address of memory reflecting the state of a cylinder (extended, retracted), the camera could be focused on this, and particularly on sensors if there are any. In fact, sensors are the reflect of state of the cylinder, and they are connected to PLC inputs. For global state of the APS, it is possible to focus the camera on Human-Machine Interface (HMI) or an indicator light.

Records are launched at regular interval and they are synchronised with each other. Records frequency must be defined according to the occurrence frequency of events to retrieve. The Shannon theorem could be used for defining this parameter: the frequency of recording must be twice more than the frequency of events.

The user has to analyse photos to add an event when an evolution of the desired state is observed. Thus, all events are saved and they describe the evolution of APS. With this work doing by the user, a list of events was created and will be used as a reference of the evolution of the state of APS.

Identify memory addresses

The scoring algorithm compares all the value changes of all memories, called signals, with the declared events, in order to suggest most concordant of them. Each declared event must involve a value variation, because an event describes a modification of the physical state, and this modification is most probably due to the PLC order and/or detected by a sensor connected to the PLC. In order to avoid a time lag between the physical occurrence and manual declaration, a temporal window is created on both sides of each event. The width of this window is an input parameter for the algorithm.

There is no limitation regarding the type of states identified, the algorithm compares only value modification of memories with declared events. Nevertheless, it is possible to classify signals in two categories and events in two other categories. This classification provides a better interpretation of signal scores obtained with the algorithm. The first category concerns the occurrence frequency: the desired state could be periodic or aperiodic. A periodic state could assimilate from machine rate-depending state: parts counting, actuator sensor, etc. An aperiodic state could be assimilated to an intermittent state or a transitory state, it could be a fault state, an operating mode state, etc. The second classification concerns the event type and this observation: the event could be related to an action of PLC, as an actuator movement, or indirectly related to an action of PLC, like a new produced part, for these the user does not know exactly when the PLC gets or produces this piece of information.

The algorithm assigns a score to each variable, with for data the signals recorded, declared events and a parameter that is the temporal window width around each event (figure 1). Depending of the classification of event, the wide of windows could be defined. When the event is related to an action of PLC, this wide could be small. In the other case, a higher value must be used.

The algorithm is based on generating data during recording: signals, pictures of the production equipment and declared events.

The algorithm starts by demultiplexing 16 bit integer signals to generate 16 new binary signals. The integer signal and its bits will be analysed by the algorithm. It is common that binary variables are regrouped into one or more integer variables, for data exchange with Supervisory Control And Data Acquisition (SCADA), for example.

Then, the algorithm defines temporal windows, linked to the events. Each temporal window is defined for an event with a wide parameter, defined by , while each window has a width equal to 2 . Two or more overlapped windows will be combined in one single window, while keeping the information that it represents a serie of events.

For each window, the algorithm computes a score. It calculates the ratio, reduces it to zero, between the number of events included in the window and the number of changes in signal.

For each signal, the average of the obtained scores is calculated in order to have an overall score . The highest score is equal to 0. The algorithm then calculates the number of changes in signal value in out-ofwindows areas, this value being weighted by the width of these areas. This value must be as low as possible to correspond to the desired signal. Indeed, this signal must not change when no events are declared. Each out-of-windows area is defined between each window. The highest possible score is then 0, it corresponds to a signal that does not change the value in out-of-windows areas.

Scores of the desired signals could be altered by several elements, in such a way that the signal has not a equal to 0 and a equal to 0. The and the could not be equal to 0, if there an important offset between the signal and the event, in case of event unrelated to a PLC action or in the case of sampling frequency being too low, implying that some physical events were no recorded by the camera. The could evolve if the user omits to report an event or reports more events than the system evolution.

In the case of an aperiodic signal and events unrelated to an action of the PLC, it could appear as an offset between event declarations and signal evolving, then it will impact and . In order to sort out and give to the user a selection of best signals, the algorithm removes every signal that did not evolve during the period of recording. Then, it selects, according to the Pareto principle, the most relevant signals depending on their and order them by , from the best to the worst. With this ranking, the exploitation and analysis of results is simplified for the user, by focusing only on relevant signals, ordered by their score.

Case study

The aim of this case study is to validate the presented method with a specific case in terms of effectiveness (i.e. to validate the discriminating characterisation among address memories). It was realised on an APS filling bottles. This APS is supplied with empty bottles, caps and liquid and, it produces caped filled bottles at the outlet (figure 2). A degraded mode allows the production without bottle capping.

The goal is to retrieve two types of information: the number of parts produced and the state of conveyor. The first information is described with a periodic signal and events are unrelated to an action of PLC. The second information is described with an aperiodic signal and events are related to an action of the PLC. The APS is controlled by a Schneider Electric M340 PLC. Inputs and outputs are connected to an AS-i industrial network. Actuators are electric motors (dosing pump, conveyor, rotary table) and pneumatic actuators (linear cylinders, rotary cylinders and Venturi system). The PLC is connected to the OPC server with Modbus TCP-IP protocol.

The data collection is performed by the KEPServerEX 6.5 OPC server. The history of variable values is recorded with DataLogger plugin. Data are saved in MySQL database. The values of variables are saved in a table of a database with the following format: Unique ID;Date and time;Variable name;Value. Each record creates 400 lines in this table. The time is stored with a precision of ten milliseconds.

Protocol

In this case study, the OPC server and the created program are installed on the same computer. The PLC is connected to the same network as the computer. The first 100 boolean variables (%M) and the first 300 variables (%MW) of PLC are added in the OPC server. The APS production rate is about 400 parts per hour, the duration between each record is set to 1 second.

The camera is positioned in order to observe the two stations and the conveyor. A first sequence of 3 minutes of recording is made in the normal production mode. This sequence is used to determine the counting parts variable. A second sequence of 3 minutes of recordings is made with normal production times and conveyor start-up times in manual mode. This last sequence is used to determine the conveyor state variable.

The searched events are then added through the interface of the tool (figure 3). For the part counting, an event is declared as soon as a bottle leave station 2 and before they disappear from the picture frame. This reference is arbitrary, it depends on the user's selection because it is not possible to know where and when the PLC counts the bottle. For the conveyor, an event is declared as soon as the conveyor starts or stops.

The state of the conveyor is an aperiodic signal and events are directly related to an action of the PLC, the selected value of is low.

Results and Discussions

Counting parts

The type of signal corresponding to counting parts is periodic and events are unrelated to a PLC action, the selected value of is high. The is set to 10. The algorithm returns 88 variables that evolve during the recording and it selects 18 variables (figure 4). Obtained results show us three variables with an identical and Fig. 3 The HMI for the identification of variables. The figure shows the page for adding events depending on photographs. The developed program assists the user from the recording to the identification.

. The temporal analysis, with the graph, confirms that these three variables have identical values. This record does not allow to discriminate them. The next variables have a relatively distant score and can be eliminated by human. Temporal analysis confirms the found correspondence of variables (figure 5).

Part count can also be retrieved by the status of APS sensors. However, the declaration of events does not allow these variables to be collected. Indeed, when a sensor detects a part, the generated signal corresponds to a slot, meaning two changes in value: the rising edge and the falling edge. In this case, the user should have reported two consecutive events.

State of conveyor

The type of signal corresponding to the conveyor state being of the aperiodic type and related to an action of the PLC, the value of chosen is 4. The algorithm returns 49 potential variables and selects 9 of them (figure 6). The obtained results show a variable with a and a both at zero. The temporal analysis makes it possible to highlight the correlation between this variable and the events declared in the state of the conveyor (figure 7). During the recording, normal production mode and manual production mode are used. These modes are displayed with a different screen on HMI and are notified with several states of the green light indicator. This is why MW74.7, image of the green light indicator, and MW144, image of the screen number on HMI, obtain a good score. Nevertheless, the temporal analysis shows to the user values that do not correspond to the state of the conveyor. The obtained results make it possible to identify the corresponding variable (figure 6). The temporal analysis of potential variables allows the user to discriminate the best results thanks to their knowledge.

CONCLUSION AND FUTURE WORK

In this paper, a method to find variable addresses into PLC memory via industrial network is presented. The technique allows the identification of PLC variables, the representation of the physical state of the APS through the recording values of variables and photographs of the APS. The algorithms issued for the method is simple, with high efficiency and could be used to retrieve every state of system, as long as it is driven by the PLC.

This method addresses issues that are not covered by current scientific work. It could be used to complement the works identified in the state of the art to improve results by providing physical knowledge of the system that is generally ignored (physical correspondence between inputs and outputs).

The benefits of the proposed methods were experimented on a real industrial case, with tests performed on an automated production system. This approach brings progression for the industrial 4.0, it provides the ability to collect data from many devices that can be seen as a black-box.

The next step is the amelioration of the algorithm. Event sequences detection could improve the differentiation as it would present less results to the user. The detection of significant value corresponding to an event, in addition to variations of signals could also ameliorate the identification. An automatic declaration of events based on computer vision and movement detection will allow longer records without the necessity to check each picture by the user and, thus, obtain better results.

Moreover, this contribution will be integrated in a Digital Twin model for production equipment, as part of the identification phase in the design process of this type of model.

Fig. 1

 1 Fig. 1 Schema of signal scoring treatment

Fig. 2

 2 Fig. 2 Detailed view of the concerned two stations of the APS. At the left, the filling station. At the right, the capping station with cap pick-and-place and screwing.

Fig. 4

 4 Fig. 4 Results for counting parts and = 10. "Correspondence" column is not know by the user. The green gradient defines the ranking of the highest scores. MW33, MW32 and MW35 have the highest score in and the highest score out.

Fig. 5

 5 Fig. 5 Time graph of results for counting parts and = 10. Windows are in blue. Green dots on windows are events. The black line is MW35

Fig. 6

 6 Fig. 6 Results for conveyor and = 4. "Correspondence" column is not know by the user. The green gradient defines the ranking of the highest scores. MW74.0 has the highest score in and the highest score out.

Fig. 7

 7 Fig. 7 Time graph of results for conveyor and = 4. Windows are in blue. Green dots on windows are events. Black and green lines are MW74.0 and MW74.7 variables.