Hélène Le Bouder

Gaël Thomas

Ronan Lashermes

Yanis Linge

Bruno Robisson

Assia Tria

An Evaluation Tool for Physical Attacks

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

When talking about the security of a device, numerous tools allow the developers to prove the security of algorithms and the software design. Unfortunately, physical attacks introduce another dimension: the interaction of the implemented algorithm with the physical environment. Physical attacks are a real threat, even for algorithms proved secure mathematically. They are divided in two families: the Side Channel Analysis (SCA) and the Fault Injection Attacks (FIA).

SCA are based on observations of the circuit behaviour during the computation. The first attacks were the Simple, the Differential and the Correlation, Power Analysis (SPA, DPA and CPA) [START_REF] Mangard | A simple power-analysis (SPA) attack on implementations of the AES key expansion[END_REF][START_REF] Kocher | Differential Power Analysis[END_REF][START_REF] Brier | Correlation Power Analysis with a Leakage Model[END_REF]. SCA exploit the fact that some physical values of a circuit depend on intermediary values of the computation. This is the so-called leakage of information of the circuit. Leakage examples are timing [START_REF] Paul | Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[END_REF], power consumption [START_REF] Mangard | Power analysis attacks: Revealing the secrets of smart cards[END_REF] and electromagnetic emissions (EM) [START_REF] Quisquater | Electromagnetic analysis (EMA): Measures and counter-measures for smart cards[END_REF].

FIA consist in disturbing the circuit behaviour in order to alter the correct progress of the algorithm [START_REF] Biham | Differential Fault Analysis of Secret Key Cryptosystems[END_REF][START_REF] Giraud | DFA on AES[END_REF]. Faults are injected into the device using various means such as laser [START_REF] Sergei | Optical fault induction attacks[END_REF], clock glitches [START_REF] Zussa | Power supply glitch induced faults on FPGA: An in-depth analysis of the injection mechanism[END_REF], spikes on the power supply or electromagnetic perturbations [START_REF] Moro | Electromagnetic fault injection: towards a fault model on a 32-bit microcontroller[END_REF].

Motivation and Contribution: The question that naturally arises is: how to evaluate and compare all physical attacks? Several works have been proposed to describe them with a common framework [START_REF] Micali | Physically Observable Cryptography[END_REF][START_REF] Standaert | How to compare profiled side-channel attacks?[END_REF][START_REF] Abdelaziz | Practical improvements of profiled sidechannel attacks on a hardware crypto-accelerator[END_REF]. However, these works only cover SCA. In [START_REF] Mangard | One for allall for one: unifying standard differential power analysis attacks[END_REF][START_REF] Whitnall | The myth of generic dpa...and the magic of learning[END_REF], the authors propose to write various SCA as DPA, a lot of work has been done to compare distinguishers as in [START_REF] Maghrebi | Comparison between Side-Channel Analysis Distinguishers[END_REF]. Likewise, there are frameworks for FIA [START_REF] Verbauwhede | The Fault Attack Jungle-A Classification Model to Guide You[END_REF][START_REF] Moradi | A generalized method of differential fault attack against AES cryptosystem[END_REF][START_REF] Sakiyama | Information-Theoretic Approach to Optimal Differential Fault Analysis[END_REF]. In [START_REF] Standaert | A unified framework for the analysis of side-channel key recovery attacks[END_REF], Standaert et al. underline the interface between theory and practice for SCA, our work enlarges this vision for both families. The improvement of our paper is to unify the evaluation for the two families (SCA and FIA). A new tool evaluates the theoretical attacks separately form the real practical attacks.

Description of the attacks in three steps

Physical attacks are decomposed in the following 3-step process. The target noted K is the goal of the attack, its domain of definition is noted K.

Step 1: Campaign. An experiment E is a pair (O S , O R ) (S for Stimuli and R for Reaction) of observables, taken during the execution of an algorithm. A set of n experiments is called a campaign. The observables could be data as plaintext, ciphertext, faulty ciphertext; or physical measurements as EM traces, power traces, signal provided by a micro-probe, computation time etc. The attack path is an exploitable relation R between the observables and the target K.

O R = R(O S , K) . ( 1
)
This relation is composed of physical functions f and algorithm functions. The physical functions f cannot always be described with a mathematical expression since they are often non deterministic. There is often only one physical function.

Step 2: Predictions. In the attack path R there are two unknowns: the target K and the physical functions f . The attacker make guesses k on the target K. The good guess is noted k. A divide and conquer approach is generally chosen. The domain of definition of the target, K, should be short enough so that all guesses can be tested. As already pointed out, physical functions do not always have a mathematical expression. But they can be approximated by mathematical functions called models or by a phase of characterization called template as in [START_REF] Chari | Template attacks[END_REF]. In FIA, models are called error functions and leakage functions in SCA. Several models m can be tested for one physical function f . Commonly, one or a small set of models is used. Finally, predictions are built with the attack path for each guess k on the secret, where the physical functions are replaced by models.

P m,k = R m (O S , k) (2)
Step 3: Confrontation. For each hypothesis k and a model m, P m,k is confronted to the observables O R with a distinguisher. A distinguisher is a statistical tool which is able to find the correct guess on the target. The distinguisher highlights links between physical function f and mathematical model m, they are based on different statistical criteria. P m,k and O R can be considered as random variables. The distinguisher returns the guess k d , if k d = k the attack succeeds.

The evaluate and compare tool

Generally different distinguishers are compared on a same device; or different campaigns with a same distinguisher; or different models with a same distinguisher. This paper presents a different approach. First, in a theoretical study, the models are evaluated independently from the physical functions; i.e R m in equation ( 2) is studied. Then the adequacy of the models with respect to the physical functions is evaluated.

Evaluation of the theoretical attack. The set of predictions has a cardinal p. One has to remark that it is possible that p = card (K). Indeed two guesses can have the same prediction during an attack. Let Θ m be an oracle associated with a model m as illustrated in Fig. 1(a). The oracle Θ m returns P m, k the prediction which corresponds to the good guess k under model m for an chosen observable O s . The required number of queries (on average) to Θ m in order to retrieve the target K is noted q. It is a measure of how efficient is the theoretical attack path R m . An oracle can combine sets of models.

Evaluation of the attack in practice. This section deals with the link between observables O R and the good prediction P m, k. More precisely the two codomains, for the attack path R and for R m are compared. Additionally there is not necessarily a bijection between the codomains (the prediction P m, k and the observables O R ), as it has already been shown in [START_REF] Micali | Physically Observable Cryptography[END_REF][START_REF] Standaert | A unified framework for the analysis of side-channel key recovery attacks[END_REF][START_REF] Whitnall | The myth of generic dpa...and the magic of learning[END_REF].

A contingency table is filled with the results of n experiments. All the possible values of P m, k are noted 1, the value at the corresponding row i (prediction is equal to P i ) and the column j (reaction is equal to O j ) is incremented. At the end, the value a i,j is the number of times the attacker computed the prediction P i in conjunction with the measurement of the reaction O j , i.e. the number of experiments with P m, k = P i and O R = O j .

P i , i ∈ [[1, p]] and the possible values of O R are noted O j , j ∈ [[1, o]]. For each experiment E = (O S , O R ), the reaction O R is stored and P m, k is computed. Then in the contingency table, shown in Table
Up to normalization by a factor n, this contingency table can be understood as the joint distribution of P m,k and O R . Given an experiment (O S , O R ), the correct prediction P m, k(O S ) is given by Θ m (O S ) and does not depend on O R . Denote by î, the row index corresponding to P m, k, so that P m, k = P î; and by , the column index corresponding to the observed O R = O . The probability of guessing the correct prediction P m, k with O R is:

P P m, k|O R = a î, A  , where A  = p i=1 a i, . (3)
A new oracle Θ (Fig. 1(b)) is introduced. Given an observable O S , it returns a (guessed) prediction P m,k with probability given by P (P m,k |O R ), and with O R = R(O S , k). The probability (3) is then the probability of the oracle returning the correct prediction P m, k. This probability P is called the matching probability of O S . The average number q of queries to Θ required to gather q correct guesses is evaluated. The oracle Θ m allows to evaluate the quality of an attack path R m with the model m. A smaller q means a better adequacy between the attack path and the model. P represents the quality of the measures O R with respect to the predictions P m, k. Finally this probability and the oracle are combined to globally evaluate the experimental attack with respect to the models thanks to q .

OR = O1 OR = O2 • • • OR = Oo total P m, k = P1 a1,1 a1,2

Practical Examples

Targeted algorithm: Advanced Encryption Standard (AES).

The AES is a standard established by the NIST [START_REF]Specification for the Advanced Encryption Standard[END_REF]. It is a block cipher. The encryption first consists in mapping the plaintext T of 128 bits into a twodimensional array of bytes, called the State. Then, after a preliminary XOR between the input and the key, AES 128 executes 10 times a round function that operates on the State. The operations used during these rounds are: SubBytes composed of non-linear transformations: 16 s-boxes noted SB; ShiftRows (SR), a byte shifting operation on each row of the State; MixColumns (M C), a linear matrix multiplication working on each column of the State; and a byte-wise xor ⊕ between the State and K r , r ∈ [[0, 10]], the derived key used at round r.

Targeted device. In this paper, the target is the cipher key of an AES 128 . It is implemented on an ARM-based STM32F100RB micro-controller embedding a Cortex-M3 core and running in our case at 24MHz. The board used is the STM32VLDICOVERY. This chip does not embed any countermeasures against physical attack but it is a popular choice for IoT applications.

Differential Power Analysis

Experimental protocol. An electromagnetic emissions analysis bench is composed of an EM probe from Langer (RF-R0,3-3) to capture the leakage, a preamplifier from Langer (PA 303) and an oscilloscope to measure it. The oscilloscope is a DSOS404A from Keysight. It achieves 10-bit resolution with a 20 Giga samples per second and 4GHz bandwidth. Finally, a control computer is used to orchestrate the measurements and perform the analysis.

Description of the attack. The first attack presented is the classic DPA/CPA attack [START_REF] Brier | Correlation Power Analysis with a Leakage Model[END_REF] by electromagnetic analysis on the first round of the AES. The target is a byte k of the key K 0 . There are only 256 possible values. The observable stimuli is a plaintext byte O S = T . The reaction is the measured electromagnetic field, O R = EM traces. The attack path is illustrated in Fig. 2 (left). The theoretical path uses Hamming Weight (HW) as model.

R(T, k) = f (SB(T ⊕ k) , with f the physical function. R m (T, k) = HW (SB(T ⊕ k)) = P m,k .
The distinguisher can be a difference of mean, a correlation, a mutual information, a principal component or a linear discriminant. Evaluation of the attack. The oracle Θ m returns a Hamming weight. On average, q = 4 queries to Θ m are required to retrieve a key byte. Then the oracle Θ is called. It returns a guessed Hamming weight. With the measures O R collected in this experiment, an average of q = 17.8 calls to Θ are required to have q = 4 correct guesses.

Differential Fault Analysis

Experimental protocol. The fault injection bench used electromagnetic pulses. These electromagnetic pulses are sent to the target thank to the inductive coupling of an EM probe with the target metal layers. Our bench is able to inject a pulse of ≈ 3 ns at the minimum and to repeat this pulse in order to achieve multi-faults if wanted.

Description of the attacks. The second attack presented is an attack of type DFA. Our bench can produce faults at the end of the round 9. We wanted to realize the attack of Giraud [START_REF] Giraud | DFA on AES[END_REF]. The target is a byte k of the key K

R m (C, k) = SB SB -1 (C ⊕ k) ⊕ 2 i ⊕ k .
In the case of the Giraud's attack, the distinguisher could be a sieve [START_REF] Biham | Differential Fault Analysis of Secret Key Cryptosystems[END_REF] or a counter [START_REF] Giraud | DFA on AES[END_REF]. Unfortunately with our experimental protocol we cannot obtain single-bit faults , therefore the Non-Uniform Error Value Analysis (NUEVA) attack from [START_REF] Lashermes | A DFA on AES Based on the Entropy of Error Distributions[END_REF] is chosen. The main idea in this attack comes from the fact that fault injection are never random. The stimuli is a pair of a ciphertext byte and a faulty ciphertext byte O S = (C, C * ). The reaction is the error observed, O R = e. The attack path ans theoretical attack path are:

R (C, C * ), k = f SB -1 C ⊕ k , SB -1 C * ⊕ k , R m ((C, C * ), k) = SB -1 (C ⊕ k) ⊕ SB -1 (C * ⊕ k) .
The model is ⊕e (256 models). The distinguisher is an entropy.The goal is to detect if the distribution of the errors is uniform or not.

Evaluation of the attacks In the case of Giraud attack, the oracle Θ m is build with 8 models, so it returns 8 guess values. In average, q = 2.4 queries are necessary to retrieve one byte (result given in [START_REF] Giraud | DFA on AES[END_REF]). This model is very good but very hard to realize in practice with our fault injection bench. In the case of NUEVA, the oracle Θ m returns an error. In theory, an infinity of queries (q = ∞) are necessary to evaluate if a distribution is uniform or not. Θ returns a guessed error. A faulty value can always be represented with a ⊕, so the matching probability is always equal to 1. So q = q = ∞, and this model seems very bad. But in practice with our fault injection bench, 2500 faults are required in average.

Conclusion

A new technique to evaluate physical attacks has been presented. The main idea is to evaluate the attack at different levels and not only on the final result. In a first time, only the models are studied, looking at the average number q of queries to an oracle that always returns the correct prediction. A smaller q means a better theoretical attack path. Then in a second time, only the predictions and the reactions are confronted, before using a distinguisher. Another oracle is introduced that returns a prediction but, contrary to the previous oracle, may return an incorrect one. The distribution of the returned predictions depends on the measures collected. The average number q of queries to the new oracle to have q correct predictions evaluates the quality of the model with respect to the measures. At the end of this two-step evaluation, different distinguishers can be tested and a success rate can be computed. In case of failure, the advantage of our tool is to underline what part of an attack is weak.

Fig. 1 .

 1 Fig. 1. (a): Oracle Θm. (b): Oracle with matching probability P.

  10 . There are only 256 possible values. The stimuli is a ciphertext byte O S = C. The reaction is a faulty ciphertext byte O R = C * 6 . The attack path is illustrated in Fig 2 (right). The theoretical attack path uses a single-bit fault model, i.e 8 possible models: ⊕2 i with i ∈ [[0, 7]], are considered together 7 . R(C, k) = SB f SB -1 C ⊕ k ⊕ k ,with f the fault injection process.

Fig. 2 .

 2 Fig. 2. Attack path of DPA (left) and DFA (right).

Table 1 .

 1 Contingency table of the measured OR and the predicted values P m, k .

	• • •	a1,o	o j=1 a1,j

In this paper a faulty variable is denoted by an asterisk * .

The function SR shift bytes, so it is omitted for the simplicity of the equation.


Bruno Stévant
email: bruno.stevant@imt-atlantique.fr

Jean-Louis Pazat
email: jl.pazat@irisa.fr

Alberto Blanc
email: alberto.blanc@imt-atlantique.fr

Optimizing the performance of a microservice-based application deployed on user-provided devices

Keywords: Edge computing, Performance modelization, QoS-aware placement, Particle Swarm Optimization, Microservice application design

It is now feasible for consumers to buy inexpensive devices that can be installed at home and accessed remotely thanks to an Internet connection. Such a simple "self-hosting" can be an alternative to traditional cloud providers, especially for privacy-conscious users. We discuss how a community of users can pool their devices in order to host microservices-based applications, where each microservice is deployed on a different device. The performance of such an application depends heavily on the computing and network resources that are available and on the placement of each microservice. Finding the placement that minimizes the application response time is an NP-hard problem. We show that, thanks to well known optimization techniques (Particle Swarm Optimization), it is possible to quickly find a service placement resulting in a response time close to the optimal one. Thanks to an emulation platform, we evaluate the robustness of this solution to changes in the Quality of Service under conditions typical of a residential access network.

I. INTRODUCTION

Over the last decade, the number of public cloud providers has increased significantly. It is now possible to rent resources located in one or more data-center. Such an infrastructure can satisfy the needs of a large number of users, but it does have the downside that data must be moved (and often stored) in these shared data-centers, raising doubts about the privacy of the data and, potentially, its ownership (for instance, in the case of providers going out of business).

Data-centers are not alone in taking advantage of technological progress: user devices, including personal computer and set-top boxes, have ever increasing computing and storage capabilities. Computer networks offer higher data rates to the wider public, with the spread of Fiber To The Home (FTTH) solutions and high speed wireless networks. Thanks to all this, it is conceivable for the devices hosted on the user premises to offer services to their owners, even remotely. Such a solution has the added advantage of addressing the data privacy and ownership issues mentioned above.

An obvious shortcoming of such an approach is that it introduces two single points of failures, namely the user device and the corresponding network connection. Either one can fail, rendering the service unavailable remotely. While modern hardware is reasonably reliable, such a solution is no match for the public cloud providers that can offer highly available services thanks to their redundant infrastructure.

A possible solution to overcome these limitations is for several users to cooperate, by pooling their individual resources to form a larger (redundant) system. A few devices (for instance between 10 and 20) can already be enough to significantly increase the availability and, potentially, the performance with respect to a single device. As an example, let us consider a sport club, whose members would like to share pictures and other materials related to the club activities. One member decides to use the storage space available on one of his devices connected at home to let other members store and retrieve their photos. When comparing this solution with the service provided by a public platform, two limitations stand out. First, as these devices are provisioned for individual usage, they might not have enough local resources (CPU, storage, network) for a larger number of users. In our example, the storage space and the residential network will become bottlenecks as members of the club are uploading and browsing more photos. The second limitation comes from the lower availability of these on-premise devices. The photo-sharing storage will be unavailable anytime the device is powered off or experiencing a network outage. If multiple members of the sport club are willing to share their devices and network connectivity, they could significantly improve the situation, provided they have a large enough variety of network providers and usage patterns. Extended functionalities like generating thumbnails and presenting them in a web gallery can be offered to the community as the different devices contribute to the application with their computing and networking resources.

Members of the community will fully benefit from the cooperation between the devices as the application can be distributed over these devices. Many frameworks for distributing applications over user-provided devices have been already proposed, such as Cloud@Home [START_REF] Cunsolo | Volunteer Computing and Desktop Cloud: The Cloud@Home Paradigm[END_REF], Nebulas [START_REF] Chandra | Nebulas: Using Distributed Voluntary Resources to Build Clouds[END_REF], Community Cloud [START_REF] Amin | Towards Distributed Architecture for Collaborative Cloud Services in Community Networks[END_REF] or CNMC [START_REF] Selimi | Towards Network-Aware Service Placement in Community Network Micro-Clouds[END_REF]. These solutions aim at creating an Infrastructure-as-a-Service (IaaS) interface on top of the userprovided devices where applications embedded inside virtual machines can be deployed and managed the same way as in a data-center. Such solutions however tends to be complex as they have to adapt to devices and networks which are much more heterogeneous and with a lower availability rate than the infrastructure of a data-center.

In this paper we focus on a higher level solution where the application is based on a microservice architecture [START_REF] Fowler | Microservices[END_REF]. In such an architecture, each basic functionnality of the application is provided by a separate microservice. The application can be considered as a composition of these different microservices. Distributing the application on the user-provided devices is then possible by deploying each microservice on the different devices. Once each microservice is deployed and accessible from any other devices, the composition of these services offers a fully functional application.

Such a distribution solution is very flexible as many possible placements of the services of the application are possible. The performance of application is however highly dependent of the chosen placement. Each service may indeed be deployed on devices with CPU and network resources that are insufficient for the task handled by the service. Finding the devices where to deploy the microservices which result in the optimal performance of the application is a difficult problem. The choice of a placement of the service has to match the requirements of the services and the resources available on the devices.

As a first contribution of this paper, we describe in Section III a model to evaluate the performance of the application depending on the capabilities of devices chosen for hosting the microservices. In section IV we define the problem of finding the placement of the services that optimize the performance as defined by our model. The Particle Swarm heuristic is used to find acceptable solutions to this problem in constant time.

A second contribution of this paper is the evaluation of the results of this heuristic on a platform emulating user-provided devices interconnected by a network with similar capabilities to residential networks. We demonstrate in Section V that with relatively little information on the infrastructure and on the application, the heuristic can find good solutions close to 15% of the optimal performance.

II. A CONCRETE EXAMPLE: A PHOTO SHARING APPLICATION

In this paper, we consider a photo sharing application, allowing users to upload their photos and browse a web gallery with thumbnails of the stored photos. Such an application could be used, for instance, by the people belonging to a sport club. As Figure 1 (a) shows, we have implemented the application using four microservices:

• WebUI (UI): provides a web photo gallery with thumbnails and a form to upload photos. • PhotoHub (PH): stores the photos.

• ThumbHub (TH): produces the thumbnail of a photo by resizing the original photo. • MetaHub (MH): stores the photo metadata. It is important to note that the microservices are interdependent: in order to accomplish a task, a microservice may need to call other services to get some data or perform other tasks. For example, the ThumbHub service relies on the PhotoHub service to retrieve the original bitmap of the photo and on the MetaHub service for the metadata of the photo.

We want to distribute these microservices on different userprovided devices, characterized by heterogeneous CPU and network capabilities. Figure 1 (b) shows a representation of these devices interconnected by the Internet. Each device offers a different amount of CPU resources, depending on its hardware profile. The residential access networks that connect the device to the Internet also have heterogeneous capabilities in terms of bandwidth and latency, depending on the technology used by the access network (DSL or Fiber).

Figure 1 (c) gives an example of a deployment of the application over these devices. Some devices are selected to host a service of the application, for example by using a placement algorithm such as the one that we describe later. Once the services are deployed, an external registry service, not described in this paper, is used to make the deployed services known and reachable from the other services. The services, being able to communicate directly with each other, are then capable of cooperating in order to offer all the functions of the photo sharing application.

Many deployments are possible, each one potentially resulting in a different performance of the application. The time for a service to handle a request depends on the computing capabilities of the hosting device, especially when this task requires some computations. For example, the ThumbHub service, which has to generate thumbnails by resizing an photo, will perform better if located on a device with more CPU resources.

As the microservices communicate through a wide-area network, the time spent in forwarding the requests and responses over the network can have a significant impact on the performance of the application. In the photo sharing application, given that both the UI and the TH services use the PH service, the available bandwidth on the links connecting them to the PH service can influence heavily the performance and hence the user experience. Compared to the PH service, the MH service requires the transfer of a smaller amount of data, namely the metadata of the photos. This service is therefore more impacted by the network latency. Table I gives an overview of the impact of the available CPU resources and of the network Quality of Service (QoS) parameters on the performance of the different services.

For these reasons, the global performance of the application depends on the placement of each microservice. Deciding on which devices one should deploy the microservices, in order to maximize the performance of the application, is a difficult problem. The choice of a placement should consider the requirements of each microservice in terms of computing and communication resources, as well as the interactions between the different services.

III. PERFORMANCE METRICS

In this section we compute the response time of the application, from the point of view of its users. That is, the time needed to accomplish different tasks, such as displaying the photo gallery, downloading (or uploading) a photo. We model the performance of the application as a weighted average of the response times of all the possible user actions. This is a proxy for the Quality of Experience (QoE) experienced by the user [START_REF] Egger | Time is bandwidth ? Narrowing the gap between subjective time perception and Quality of Experience[END_REF]. Such an approach requires knowing the response time of each microservice, on which device each microservice is running, as well as the characteristics of the network paths (available bandwidth and delay) between the devices hosing the microservices. The response time of each microservice depends itself on the resources (CPU, memory) available on the device on which it is running but these factors can be incorporated in the response time of the microservice, if its value is sufficiently stable. This is the case if the network is the bottleneck rather than the computing devices. As reasonably powerful devices are not very expensive, we believe that the network will indeed be the bottleneck most of the times, especially for devices connected by a wide area network, resulting in response times that depend mainly on the network QoS, as long as the devices are not overloaded.

In [START_REF] Nishio | Service-oriented Heterogeneous Resource Sharing for Optimizing Service Latency in Mobile Cloud[END_REF] the authors propose to use the response time of a service deployed on a particular device as a unified utility function to evaluate the performance of a service. This metric unifies in a single value parameters such as CPU ressources and network QoS. In our case, we can apply the same metric to evaluate the performance of a service deployed on a userprovided device. This metric depends on the service itself, on the device where the service is deployed and on the device requesting the service.

We assume that it is possible to estimate the response time of each service, more precisely that it is possible to estimate how long it would take for a service s, running on device n, to call service s , running on device n . This could be done, for instance, by deploying each service on each node and then by running a series of measurements. While such a solution is potentially time consuming, it is feasible and, by repeating it periodically, one could keep up with any changes in the network and/or devices.

Each client can evaluate the performance of the application as the sum of the response times of the calls to the application. In the case of the photo-sharing application, the different calls are: browsing the gallery of photos, downloading a full-size photo, downloading a thumbnail of a photo and uploading one photo.

By knowing the values of the response times for the different services, we can evaluate the response time of the application as the sum of the response times for each microservices involved in the application. We need the following definitions in order to define the objective function f :

• Let N be the set of devices in the infrastructure.

• Let C be the set of devices used as clients of the application (C ⊂ N ). • Let S be the set of services composing the application.

• Let D(s i , s j ) be the dependency between each service s i and s j ; D(s i , s j ) = 1 if s i needs to call s j , otherwise D(s i , s j ) = 0. • Let P (s) be the chosen placement for service s (s ∈ S, P (s) ∈ N ) • Let R s (n i , n j ) be the response time of a service s requested by device n i when running on device n j . The objective function for one user is the response time for this user requesting the front-end service s 0 from its own node c. For the sake of simplicity, we consider that one service makes requests to the other services sequentially. In this case, the response time is the sum of the response time of the others required services seen from the front-end s 0 . These others services may also call other services, implying that the objective function to be computed recursively.

f (c, s 0 ) = R s0 (c, P (s 0 )) + s k ∈S D(s 0 , s k ) × f (P (s 0 ), s k )
The global objective function is the weighted sum of the objective function for each user. Let W (c) be the weight applied to user c:

f (s 0 ) = c∈C W (c)f (c, s 0 )
In the case of the photo-sharing application the set of services is:

S = {s 0 , s 1 , s 2 , s 3 , s 4 }
where s 0 is the UI service, s 1 is the MH service, s 2 the PH service used to download a photo, s 3 the PH service used to upload a photo and s 4 the TH service.

The dependency function D is built from the call graph of the application, depicted in figure 1 (a):

D(s 0 , s 1 ) = 1 D(s 0 , s 2 ) = 1 D(s 0 , s 3 ) = 1 D(s 0 , s 4 ) = 1 D(s 4 , s 1 ) = 1 D(s 4 , s 2 ) = 1 (1)
These values show that the UI service (s 0 ) calls each of the other services and the TH service (s 4 ) calls services MH (s 1 ) and PH (s 2 ).

The objective function for one user can be expressed as:

f (c, s 0 ) = R s0 (c, P (s 0 )) + R s1 (P (s 0 ), P (s 1 ))

+ R s2 (P (s 0 ), P (s 2 )) + R s3 (P (s 0 ), P (s 3 ))

+ R s1 (P (s 4 ), P (s 1 )) + R s2 (P (s 4 ), P (s 2 ))

IV. OPTIMIZING OF THE PERFORMANCE OF THE APPLICATION objective function 2, presented in the previous section, gives the response time of the application for one client located on a given device. The placement P opt (s) that results in the optimal performance of the application is the one that minimizes the objective function f (s 0 ). Finding P opt (s) requires finding the values of P (s i ) ∈ N ; s i ∈ S which minimize the sum in the objective function 2. The number of possible placements is equal to |N | |S| . The complexity of an exhaustive search for the optimal placement P opt (s) is therefore polynomial in the number of devices and exponential in the number of services.

As this problem is NP-hard, it is necessary to use a heuristic in order to find acceptable solutions in constant or linear time. We found that nature-inspired metaheuristics have shown good results for the problem of QoS-aware service composition [START_REF] Jatoth | Computational Intelligence based QoS-aware Web Service Composition: A Systematic Literature Review[END_REF], to which our problem can be considered as equivalent. For such problems with a very large solution space, heuristics based on Genetic Algorithms or Ants-colony optimization are indeed particulary efficient as they can find acceptable solution in constant time. We selected Particle Swarm Optimization (PSO) [START_REF] Eberhart | A new optimizer using particle swarm theory[END_REF] as a candidate for a metaheuristic to be applied to our problem. This algorithm has already been previously used [START_REF] Li | Resource virtualization and service selection in cloud logistics[END_REF] to solve the problem of choosing a composition of services based on QoS parameters.

By applying the PSO metaheuristic, we define a particle location as a placement P (s i ) ∈ N ; s i ∈ S. At the first iteration, the PSO algorithm initializes a swarm of k particles by randomly selecting their location, i.e., choosing a random placement for the services. The objective function 2 is evaluated for each of these placements and the result is assigned to the corresponding particle as its current score. At each iteration, the PSO algorithm defines a new generation of the swarm where each particle is updated with a new location. The new location for a particle is computed from parameters such as its previous location, its velocity and the minimal score found in the previous iteration. By so doing, the particles will converge at each iteration to the particle with the current minimum score. Other local minima may also be found as new placements are evaluated. The algorithm stops either when all particles have converged to the same minimum score or when it reaches a maximum number of iterations fixed as a parameter of the algorithm.

In order to validate the choice for this heuristic, we tested the PSO algorithm by using as input synthetic values for the response times of the service. We generated these values using a simple model described below. We then compare the score of the placement found by the heuristic to the score of the optimal placement found by exhaustive search. For the heuristic to be considered as valid, the score of the placement found by PSO should be relatively close to the optimal score compared to the score evaluated for others possible placements. We evaluated the scalability of the heuristic by checking if the minimal score found by PSO does not deviate from the optimal solution when the number of devices increases.

We generate the inputs for this test using a simple model for the response times of the service running on the different devices. For one pair (n i , n j ), the value of R s (n i , n j ) follows a Pareto distribution whose parameters depend on the nature of the service s and of the interconnecting network between the devices n i and n j . In order to add some diversity in these values we use two types of network technology with different QoS parameters: Fiber (high symmetrical bandwidth, low latency) and DSL (low assymetrical bandwidth, high latency). Table II gives the parameters of the Pareto distributions (minimum and average value) used to generate the response time R s (n i , n j ) of each service s depending of the type of network connecting the devices calling the service (n i ) and the device hosting the service (n j ). These values have been deduced from measurements on real deployed services. We choose that 50% of the devices use a DSL network and the In addition to these parameters, we introduce some constraints on the solution. A first constraint is related to the PhotoHub service that is represented in our model by two virtual services: downloading an existing photo file and uploading a new photo file. These virtual services are defined in our model as s 2 and s 3 . As these services are offered by the same microservice, they must be deployed on the same device. The first constraint for the heuristic is therefore P (s 2 ) = P (s 3 ). A second constraint is defined to avoid trivial solutions where all services are deployed on the same device. Such solutions give good results in our model but are not realistic as the concurrency between the services reduces the performance. To reduce concurrency, all services must be deployed on different devices, except for s 3 which is colocated with s 2 . The second constraint applied to PSO solutions is P (s i ) = P (s j ) ∀i, j ∈ {1, 2, 4}

Based on these inputs, and constraints, the PSO algorithm is able to produce a result which is the placement with the minimal score. It is important to note that several executions of the algorithm with the same parameters and input data may produce different results. It can be explained as the particles may not have converged before the algorithm reaches the maximum number of 100 iterations that we configured. By increasing the number of iterations, the algorithm produces more stable results. However it also increase the execution time. We established that, in our case, 100 iterations is a reasonable compromise for the PSO algorithm to produce consistent results.

We tested the PSO algorithm in different cases by increasing the number of devices from 10 to 100. The execution time of the PSO algorithm was constant as the number of iterations is limited and the evaluation of the objective function does not depend on the number of devices. The execution time was below 1 second on a 3GHz four-core server. We also performed an exhausive search for the optimal solution by evaluating the score of all possible deployments, in order to find the optimal solution for the test cases. Figure 2 shows the results of both PSO and exhaustive search algorithms for the different test cases. The score of the optimal solution for each test case found with exhaustive search is marked with a blue dot. The two red horizontal lines delimit the score interval containing 90% of the solutions found by 50 different executions of the PSO algorithm. The boxes show the distribution (5-percentile, 25-percentile, average, 75-percentile, 95-percentile) of the scores of all the possible placements (found with exhaustive search).

From these results we can conclude that the PSO heuristic is able to find placements for which the performance for the application is very close to the optimal solution found with an exhaustive search. These placements are included in the 5% of the possible placements with the lowest score. Moreover the PSO heuristic is able to find such placement in a maximum of 100 iterations.

The code used for this test is written in Python1 and uses the pyswarm implementation of the PSO algorithm.

V. TEST AND VALIDATION ON AN EMULATED NETWORK

The results presented in the previous section are meant only to evaluate the efficacy of the PSO algorithm in our specific use case. The response times of the services R s (n i , n j ) are static values generated using a simple model. But, in a real-life systems, the response time of a service is a random process that depends on the device hosting the service and the network traffic.

In order to evaluate the impact of such variations on the objective function defined in our model, we use a network emulation platform reproducing the QoS parameters of different technologies for residential access networks (DSL, Fiber) and the variations of the network performance (jitter, packet loss). By measuring the response time of actual microservices connected to such a network emulator, we can have a realistic evaluation of the performance of the application.

We selected Containernet 2 as the network emulation plateform for this evaluation. Containernet is a fork of the wellknown Mininet network emulator, which can connect Docker containers to the emulated network. This platform allows its users to define the QoS parameters such as the bandwidth, latency, jitter and packet loss ratio, for each emulated network. Containernet allows us to define network topologies emulating devices on user-premise interconnected with different network technologies. An example of such topology is shown in Figure 3. The network connection of each user-provided device is emulated by a virtual switch. When a microservice is to be located on a particular device, the container embedding the actual implementation of the service is connected to the corresponding virtual switch. Each virtual switch is then attached to a central switch with a link emulating the residential access network. This link is configured with the QoS parameters of the network technology (DSL or Fiber) chosen for the device. The QoS parameters defined for each type of link are listed in Table III Using this platform for network emulation, we are able to define different test cases by specifying the number of devices and the access network technology for each device. Once the topology is defined, the resulting emulated network interconnects containers running the actual implementation of the microservices of the photo sharing application. With all the needed microservices deployed, it is possible to measure the performance of the application in realistic conditions. We performed these measurements by generating independent requests to the application from each client and measuring the time needed by the application to provide a response.

For the PSO heuristic to find optimal placements of the microservices, we need the values for R s (n i , n j ); n i , n j ∈ N ; s ∈ S used by the objective function to evaluate a placement. Two methods can be applied to bootstrap these values. It is possible to measure them exhaustively by deploying the service on each device and measuring its response time from the other devices. This process is cumbersome and can be relatively expensive when the number of devices is important. Another solution is to estimate the value for the response time based on the QoS parameters given to the platform. We first made sample measurements of the response time of the service on different devices. Then we infered the response time for the other devices by linear regression on the bandwidth and latency parameters.

In addition to the values for R s (n i , n j ) inferred using the method described above, we defined the following parameters for the PSO algorithm: • Constraints: P (s 2 ) = P (s 3 ); P (s i ) = P (s j ) ∀i, j ∈ {1, 2, 4} Configured with these parameters, the PSO heuristic is able to produce a placement for the microservices of the photosharing application. The containers embedding these services are deployed on the virtual devices specified by the placement. The real performance of the application is then measured from the clients as the sum of the response times of the calls to the application.

To evaluate the stability of the system, we introduce some variations on the performance of the network by adding a jitter parameter. In wide-area network the measured transmission delay for a packet shows variations as the packet is forwarded in the network among many other packets. In order to produce variations in the transmission delay, the network emulator uses the well-known netem 3 module. The delay variation (or We evaluated the solution found by PSO algorithm on a single test case (same topology, same devices used as clients) with jitter increasing from 0% to 40% of the nominal latency for the link. The performance of the application is measured by the clients requesting the different services of the application 10 times each. The values of the optimal performance estimated by PSO and the global performance measured by all clients are shown in Figure 4. These measurements show that for a jitter below 20% of the nominal latency of the link, the performance measured for the application is stable at approximatively 15% of the optimal performance. For jitter above 20%, the measured response times increase and deviate from the optimal performance.

We can conclude from this measurement that the performance of the photo sharing application, as defined in our model, is not impacted by the fluctuation of the network. With a jitter below 20% of the nominal latency, the measured performance of the application stays in the same interval of 15% of the optimal performance estimated by PSO. In such conditions, we can be confident that the PSO heuristic is able to find an acceptable service placement.

VI. RELATED WORK

The contribution of this article is connected to various areas of research which have studied performance optimization for application distributed on edge devices.

Volunteer computing and Grid computing are well established areas of research with many contributions. Some of them are focused on performance considerations [START_REF] Anderson | The Computational and Storage Potential of Volunteer Computing[END_REF], [START_REF] Essafi | An Efficient Algorithm for Scheduling Jobs in Volunteer Computing Platforms[END_REF]. In such a context, the performance is measured as task throughput. Job scheduling strategies are defined by considering resource availability and reliability. These papers proposed to optimize the throughput of the application by reducing the idle time at the device level. The optimization target is different in our case as we are focused on application responsiveness.

In a service-oriented approach, a distributed application can be considered as a composition of service executing a workflow. Choosing a service composition that optimizes the global QoS of the workflow is a problem considered by many contributions listed in [START_REF] Nabiel Alkhanak | Cost-aware challenges for workflow scheduling approaches in cloud computing environments: Taxonomy and opportunities[END_REF]. Some proposed solutions to this problem are based on Linear or Mixed Integer Programming [START_REF] Wang | A QoS-Aware Middleware for Dynamic and Adaptive Service Execution[END_REF], [START_REF] Alrifai | Combining Global Optimization with Local Selection for Efficient QoS-aware Service Composition[END_REF]. Other heuristics to this problem have been proposed such as Genetic Algorithms [START_REF] Klein | SanGA: A Self-Adaptive Network-Aware Approach to Service Composition[END_REF] or Particle Swarm Optimization [START_REF] Li | Resource virtualization and service selection in cloud logistics[END_REF]. The problem of service composition and workflow scheduling is however slightly different from our problem. In such case the services locations are given as input to the scheduling strategy that should decide which service instance to use in the workflow. In our case, the services can be located on any device, increasing the complexity of the problem.

The placement of services considering devices with heterogeneous CPU and network capabilities also has been studied in various articles. In [START_REF] Famaey | Network-aware service placement and selection algorithms on large-scale overlay networks[END_REF] the placement is considered in the case of servers connected by an overlay network over a wide area network whereas in [START_REF] Steiner | Network-aware Service Placement in a Distributed Cloud Environment[END_REF] the servers are located in different public clouds. Each article proposes a heuristic to find an optimal placement by using a fine-grain model of the performance considering the network QoS parameters and the CPU resources. In [START_REF] Selimi | Towards Network-Aware Service Placement in Community Network Micro-Clouds[END_REF] the authors present the use case of hosting the service in edge micro-clouds. This article proposes as a heuristic to select in the model the significant parameters according to the requirement of the services (e.g., bandwidth demanding or latency sensitive services). In our approach we adopt a higher level model by the use of the response time as the single metric for the evaluation of the performance.

Fog computing [START_REF] Vaquero | Finding your way in the fog: Towards a comprehensive definition of fog computing[END_REF] is an emerging area of research that focuses on task migration from the cloud to the edge. In [START_REF] Choy | A hybrid edge-cloud architecture for reducing on-demand gaming latency[END_REF], the use case of deploying a game service on edge servers to optimize the player latency is presented. These edge servers are selected in a decentralized way using a distributed voting protocol. This approach is interesting as our centralized approach may have some limitations if the number of devices participating in the system increases. Our problem is yet more complex as we consider the placement of inter-dependent services, while the game service is standalone.

VII. CONCLUSION AND FUTURE WORKS

In this article, we have considered the use case of running an application, comprised of several microservices, on a collection of user-provided devices, interconnected by a wide area network. The application response time is a key element for the QoE of it users. Given that placing each microservice instance in order to minimize the total application response time is an NP-hard problem, we have used the PSO algorithm to find a solution. We have first shown, using simulations, that this algorithm gives satisfactory results in constant time. In order to show that such a solution is applicable in a real network, we evaluated the performance of the application on an emulated network, whose parameters represent different type of Internet connections (FTTH and DSL). When deployed according to the result of the PSO algorithm, the performance of the application is stable for reasonable jitter values. We conclude that even if the PSO heuristic use static values for the response times of the services, the selected placement still results in acceptable performance for the application even if the network QoS is fluctuating.

In addition to the response time of the services, the client behavior is another key parameter to our model for the performance evaluation of the application. In this work, we assumed that all the users are using the application with equal probability, and that each client makes the same number of requests. Some parameters of the model should be adjusted to better capture the average behavior of the client. It is important to evaluate how fluctuations in the request distribution impact the performance of the application. The network emulation platform can be used to emulate concurrent requests from different clients to the services. As our model considers an unloaded system, it should be extended to avoid concurrency. One solution is to define for the same service multiple instances that share the load of processing the incoming requests. The placement should then decide where the different instances should be located.

Fig. 1 :

 1 Fig. 1: Deployement of an application based on microservices over user-provided devices.

Fig. 2 :

 2 Fig. 2: Results of PSO heuristics compared to exhaustive search.

Fig. 3 :

 3 Fig.3: Example of a topology used in the network emulator for evaluating a deployment of microservices over devices on user-premise.

•

  Number of devices: |N | = 50 • Number of clients: |C| = 10 • Weight applied to clients: W (c) = 1 ∀c • Number of particles: 100 • Maximum number of iterations: 100

TABLE I

 I

: Impact of CPU resources and network QoS on the performance of the services

TABLE II :

 II Min/Average values for the response times (in ms) for the different services depending on the network used by client n i and server n j

	other 50% use a Fiber network.
	We initialize the algorithm with the following parameters:

• Number of devices: |N | ∈ {10, 20, 30, . . . , 100} • Number of clients: |C| = 0.2 * |N | • Weight applied to clients: W (c) = 1 ∀c • Number of particles: 100 • Maximum number of iterations: 100

TABLE III :

 III QoS parameters for emulation of residential access networks.

  ) is defined in netem by providing the interval for the possible values of the transmission delay. As the link in the emulator have different latency values, we define the jitter as a percentage of the nominal latency for the link. The value for the delay applied to a packet on a link is a random value uniformly distributed between (1 -jitter) × latency and (1 + jitter) × latency.

		Estimated Score (PSO)
	22,000	Measured Score
	20,000
	Score
	18,000
	16,000
	0	10	20	30	40	60
			% Jitter
	Fig. 4: PSO score compared to measured performance on a
	emulated network with different jitter values.
						3 netem module: https://wiki.linuxfoundation.org/networking/netem

jitter

Code available at https://github.com/bstevant/eval-pso-photosharing