Arnaud Legrand

Denis Trystram

Salah Zrigui

Adapting Batch Scheduling to Workload Characteristics: What can we expect From Online Learning?

Despite the impressive growth and size of super-computers, the computational power they provide still cannot match the demand. Efficient and fair resource allocation is a critical task. Super-computers use Resource and Job Management Systems to schedule applications, which is generally done by relying on generic index policies such as First Come First Served and Shortest Processing time First in combination with Backfilling strategies. Unfortunately, such generic policies often fail to exploit specific characteristics of real workloads. In this work, we focus on improving the performance of online schedulers. We study mixed policies, which are created by combining multiple job characteristics in a weighted linear expression, as opposed to classical pure policies which use only a single characteristic. This larger class of scheduling policies aims at providing more flexibility and adaptability. We use space coverage and black-box optimization techniques to explore this new space of mixed policies and we study how can they adapt to the changes in the workload. We perform an extensive experimental campaign through which we show that (1) even the best pure policy is far from optimal and that (2) using a carefully tuned mixed policy would allow to significantly improve the performance of the system. (3) We also provide empirical evidence that there is no one size fits all policy, by showing that the rapid workload evolution seems to prevent classical online learning algorithms from being effective.

I. INTRODUCTION

The number of applications that require the usage of super-computers is increasing rapidly. Hardware producers, despite their best efforts, are simply unable to match this ever-growing demand. As a result, we have today a large number of applications competing for limited resources. Thus, ordering the jobs in a way that guarantees maximum efficiency and fairness is more crucial than ever.

Super-computers rely on Resource and Job Management Systems (RJMS), for monitoring and control. A major part of any RJMS is the job scheduler, whose main task is to decide in which order the jobs will be executed. However, taking the right decision is a complex problem that requires considering a large number of factors. Some of which are clear and visible but most are not. In the face of such growing complexity, many system administrators opt for the "simple" answer: use simple dispatching rules that are based on intuition and that offer certain guarantees, e.g First Come First Served (FCFS) to prevent starvation or Shortest processing time First (SPF) because it favors interactivity. However, they are far from optimal and many studies [START_REF] Tsafrir | Backfilling using system-generated predictions rather than user runtime estimates[END_REF]- [START_REF] Gaussier | Improving backfilling by using machine learning to predict running times[END_REF] show that there is still room for software optimization. A common practice for RJMS is to keep execution logs that detail the history of the platform: the characteristics of the submitted jobs, their arrival times and other important information. In this work, we explore the possibility of employing this historical data to adapt to future workload using more flexible scheduling policies. We base our experiments on EASY [START_REF] Mu | Utilization, predictability, workloads, and user runtime estimates in scheduling the ibm sp2 with backfilling[END_REF], which is one of the most popular backfilling schemes, and we propose a data-driven experimental campaign through which we exploit real execution traces in the form of logs extracted from the parallel workload archives [START_REF] Feitelson | Parallel workload archive[END_REF]. First, we show the limits of simple, index policies. Then, we propose a new class of policies, which we call "Mixed policies". Using this class we prove that simple policies are far from optimal and that under the correct conditions, we can obtain significant gains.

• We show that simple scheduling policies used in the scientific literature and in industrial applications like FCFS and SPF are far from optimal and that Smallest Area First (SAF), another simple policy, performs better overall. • We also prove that it is possible to generate policies that significantly outperform these pure policies by mixing job features such as the estimate processing time, the required resources, and the waiting time in a simple weighted linear combination. • We present a mapping of the space of possible policies through which we show that the evolution of the workload through time is very chaotic, which prevents online learning algorithms from being effective. The remainder of this paper is organized as follows. Section II presents the context under which the experimental campaign was performed. In Section III we provide a background on the works done to improve the performance of EASY and aggressive backfilling, and the works that implement machine learning techniques to improve the performance of schedulers in general. Sections IV and V respectively define the index policies and the methodology that was used throughout the work. In Section VI we compare a set of pure policies, and in Section VII we present and test the proposed method to obtain mixed scheduling policies. Finally, we give some concluding remarks and an open discussion in Section IX.

II. CONTEXT

A scheduler uses a scheduling heuristic to order the jobs in an execution queue and a metric, also called objective, to measure the quality of the scheduling method.

A. Jobs

We consider an online scheduling model, where the jobs arrive at different times unknown in advance. The information available about the job upon its arrival are: the requested resources (number of requested processors), the requested processing time also called the estimated processing time (an estimation/upper limit of the processing time given by the user) and the arrival time itself. The scheduler chooses one or more of the waiting jobs to execute at each time-step. The jobs cannot be preempted.

B. Scheduling heuristic: EASY-backfilling

Scheduling is the process of selecting the order in which the jobs will be executed. One of the most popular techniques used to perform such task is the backfilling algorithm [START_REF] Mu | Utilization, predictability, workloads, and user runtime estimates in scheduling the ibm sp2 with backfilling[END_REF]. Backfilling works by finding holes in the scheduling Gantt chart and moving forward smaller jobs to fill these holes.

EASY [START_REF] Mu | Utilization, predictability, workloads, and user runtime estimates in scheduling the ibm sp2 with backfilling[END_REF] is a scheduling algorithm that uses a queue to select and backfill jobs. Algorithm 1 recalls how it works. At any time a scheduling decision is required (i.e. job submission or termination), the scheduler goes through the job queue in a primary order predetermined by the selected index policy and starts them until it encounters a job that cannot be started immediately. At this point, the scheduler makes a reservation for this particular job which ensures that it will not be delayed from its initial position. Then, it goes through the rest of the job queue in a backfilling order and execute any jobs as long as it does not delay the unique reservation mentioned earlier. This is known as backfilling. One of the most popular variations of the EASY algorithm is EASY-FCFS-FCFS where the jobs are ordered and backfilled by their arrival time.

All the comparisons and the techniques in the remainder of this paper are applied to the primary queue and the backfilling policy to fixed to SPF. We chose this setting because in [START_REF] Lelong | Tuning EASY-Backfilling Queues[END_REF], Lelong et al. showed that reordering the primary queue is more beneficial than simply reordering the backfilling queue and in [START_REF] Srinivasan | Characterization of backfilling strategies for parallel job scheduling[END_REF], The authors showed that SPF is a good policy for backfilling.

C. Metric

Throughout this paper we use the bounded slowdown (BSLD) metric as it is accepted as one of the most popular one metrics to measure the performance of scheduling heuristics [START_REF] Feitelson | Metrics for parallel job scheduling and their convergence[END_REF], [START_REF] Carastan-Santos | Obtaining dynamic scheduling policies with simulation and machine learning[END_REF]. The BSLD of a job j is defined as follows:

BSLD j = max wait j + p j max(p j , τ ) , 1 , (1)
where wait j and p j are respectively the waiting time and the processing time of job j. τ is a constant that prevents the slowdown of smaller jobs from surging. We set τ to 10 seconds for the experiments.

For this paper, we focus on the average BSLD for all the jobs over a period of time. The average BSLD of n jobs is computed in the following way:

average BSLD = 1 n n j=1 BSLD j (2)
It is worth noting however that our work does not particularly depend on our choice of metric. The average BSLD could be replaced by any objective function or metric the user seeks to optimize.

III. RELATED WORK

A great amount of research has been devoted to improving the performance of EASY. Most are based on the idea of manipulating the main and/or the backfilling queues. In [START_REF] Perkovic | Randomization, speculation, and adaptation in batch schedulers[END_REF] Perkovic et al. proposed the use of speculative backfilling to counter the almost systematic overestimation of the execution time of submitted jobs. However, these works do not address dependencies between the workload and the objectives [START_REF] Aida | Effect of job size characteristics on job scheduling performance[END_REF]. The dynP scheduler [START_REF] Lelong | Tuning EASY-Backfilling Queues[END_REF] offers an online approach to tune EASY queue. dynP requires the full simulated schedule for each of the candidate policies in every scheduling step, which makes the scheduling cost much higher than simple EASY. Several works attempted to use machine learning techniques to predict and enhance HPC systems performance. In [START_REF] Papadopoulou | A machinelearning approach for communication prediction of large-scale applications[END_REF], Papadopoulou et al. developed an approach to predict the communication cost. They constructed a set of descriptive metrics and used a multiple variable regression model. Their approach proved to be successful in predicting and subsequently controlling the cost of communication.

Many researchers focused on predicting the running time of jobs as a mean to take better scheduling decisions. In [START_REF] Tsafrir | Modeling user runtime estimates[END_REF] Duan et al. proposes a hybrid Bayesianneural network approach to model and predict the run times of scientific application. It requires a detailed analysis of the system and the jobs. It also incorporates expert domain knowledge. The most relevant work that uses running time predictions is the EASY++ algorithm presented in [START_REF] Tsafrir | Backfilling using system-generated predictions rather than user runtime estimates[END_REF], where Tsafrir et al. used a historybased system generated predictions of jobs lengths to backfill instead of user estimations. This method proved to be quite successful despite its relative simplicity. This work was followed by Gaussier et al. [START_REF] Gaussier | Improving backfilling by using machine learning to predict running times[END_REF] where they used a machine learning technique to obtain even better predictions. In [START_REF] Tuncer | Diagnosing performance variations in hpc applications using machine learning[END_REF] a framework was proposed to automatically detect and diagnose performance anomalies in HPC systems.

Perhaps the most comparable works to the one presented in this paper are [START_REF] Mao | Resource management with deep reinforcement learning[END_REF] and [START_REF] Carastan-Santos | Obtaining dynamic scheduling policies with simulation and machine learning[END_REF]. In [START_REF] Mao | Resource management with deep reinforcement learning[END_REF], the authors developed DeepRM, a multi-resource cluster scheduler that uses deep reinforcement learning to solve the problem of packing with multiple resource demands. In [START_REF] Carastan-Santos | Obtaining dynamic scheduling policies with simulation and machine learning[END_REF] Carastan-Santos and Camargo used synthetic workloads to create general heuristics that improve the slowdown metric. They combined the basic job characteristics in a non-linear function and they used linear regression to devise new heuristics. Both [START_REF] Mao | Resource management with deep reinforcement learning[END_REF] and [START_REF] Carastan-Santos | Obtaining dynamic scheduling policies with simulation and machine learning[END_REF] rely on synthetic data to train their approach.

IV. INDEX POLICIES

We study two distinct types of index policies in this work, namely pure and mixed policies. Both types are based on job characteristics.

A. Job characteristics

We use the following job characteristics during the experimental campaign:

• q j : (requested resources) the number of processors the user requested. • pj : (requested/estimated processing time) the estimated processing time provided by the user, it also serves as an upper limit to the time the job is allowed to run. The actual processing time p j can only be obtained after the execution of the job. • wait j : (waiting time) How long a job j spent in the waiting queue: wait j = current time -submission time j • ρ j : (estimated ratio) pj qj . • a j : (estimated area j) pj q j . • exp j : (estimated expansion Factor) waitj + pj pj

: the ratio of the total time a job is expected to stay in the system (waiting time plus estimated processing time) normalized by its estimated processing time. This characteristic is rather special since it reflects the estimated value of the objective function. Note that the BSLD could have been used instead of the expansion Factor but it makes very little to no difference in term of ordering since only the smaller jobs (which usually have the least impact on performance) are marginally concerned. Scheduling using exp j is expected to be a good or at least an important strategy. But it is unknown how it will perform at this point since it does not account for q j .

B. Pure policies

With each of the six aforementioned job characteristics, we construct two scheduling policies: one that prioritizes the lowest score given by the characteristic and another the highest. So we have the following 12 pure policies:

• FCFS: First Come First Served In this work, we only focus on these 12 pure policies. Many others were not included. Our aim is not to do an exhaustive review of all the policies in the literature but to illustrate certain characteristics of generic scheduling policies.

C. Mixed policies

We now introduce the concept of mixed policies and the method we use to construct them.

A job j is characterized by a feature vector x j = (q j , pj , wait j , ρ j , exp j , a j ). At each scheduling decision, we define the score of any job j using Equation [START_REF] Gaussier | Improving backfilling by using machine learning to predict running times[END_REF].

score(w, x j ) = w T x j w ∈ R n ( 3
)
where w is the weight vector of the mixed policy: each feature x i has a corresponding weight w i . These weights are what determine how the mixed policy behaves. The absolute value of a weight |w i | indicates the importance of the corresponding characteristic x i when ordering the jobs. While the sign determines the ordering itself, a positive value means that shorter/smaller jobs are prioritized, while a negative value means that longer/larger jobs are prioritized. The scoring function is scale-invariant; the order given by score(λw, x j ) is the same as the order given by score(w, x j ) for all λ > 0. Hence, we normalize w and impose that ||w|| 1 = 1. This constraint reduces the size of the search space and stabilizes the learning process (which will be explained in detail in Section VIII-A). Every pure policy corresponds to a vertex of the polytope ||w|| 1 = 1. E.g. FCFS corresponds to (0,0,1,0,0,0) and LCFS corresponds to (0,0,-1,0,0,0).

Mixed policies are an alternative method to model the scheduling problem. We move from a discrete optimization to a continuous optimization problem. We construct a search space that is small in size and instead of finding the best ordering of n independent jobs we intend to find the best weight for i features where i is much smaller than n.

V. EXPERIMENTAL METHODOLOGY

We tried to be as transparent as possible and to make our work reproducible [START_REF] Stodden | Implementing Reproducible Research[END_REF]. We provide a snapshot of the workflow we used throughout this work as a link to a git repository 1 , which includes a nix [START_REF] Dolstra | Imposing a memory management discipline on software deployment[END_REF] file that describes all the dependencies and four R notebooks that allow regenerating all the figures.

We make several simplifying assumptions about the platform. We discard all topological information related to the platforms that generated the traces. We do not take into account the topology of the cluster and we treat it as a single collection of homogeneous resources where all processors are considered indistinguishable from each other and the cost of communication is considered nonexistent.

In this work, we replace the RJMS with a EASYbackfilling lightweight simulator 1 written in OCaml. It supports tuning the Primary, Backfilling queues and it discard all topological information from the machine. So equation 2 can be written in the following form:

average BSLD = 1 n n j=1 F (x j , w), (4)
where w represents the weight of the index policy, and F represents the simulator that will take all the jobs, execute them, and return the value of BLSD of each job.

A. workload and platform a) data: The goal is to improve scheduling performance using information extracted from job characteristics. For this reason, we choose real-world traces (from the parallel workload archives [START_REF] Feitelson | Parallel workload archive[END_REF]) instead of artificially generated data. Table I outlines the workload used throughout the experimental campaign.

For every trace, we ignore the first period since it generally corresponds to a benchmarking/testing phase and is not representative of the true workload of the system. Then, we split the trace on a weekly basis and remove the jobs that start in one week and finish in another.

B. Starvation

Starvation occurs when a job is denied the resources necessary for its execution for a very long (possibly unbounded) period of time. EASY, as defined in section II-B, has a risk of causing some jobs to starve. (e.g using SPF to order the primary queue may cause longer jobs to starve). The popularity of FCFS in RJMS stems mainly from its natural ability to prevent starvation.

To avoid starvation, we rely on a simple but effective thresholding mechanism. When the waiting time of a job exceeds a certain value, it is moved to the head of the queue immediately regardless of the scheduling heuristics in play. When fixing a threshold several factors needs to be taken into consideration (the size of the machine, the size of the jobs...). Choosing a very low value limits the scheduling policy and forces the system to a quasi-FCFS regime. A high threshold grants the scheduling policy a lot of freedom but low priority jobs risk starvation. In this work, the threshold is fixed at 2.10 5 seconds which roughly translates to 2.31 days [START_REF] Lelong | Tuning EASY-Backfilling Queues[END_REF].

For a more detailed explanation of our choice of the threshold value please refer to Section X of the research report [START_REF] Legrand | Adapting Batch Scheduling to Workload Characteristics: What can we expect From Online Learning?[END_REF]. q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0 50 100 (a) SDSC-SP2 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0 10 (b) SDSC-BLUE q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0 25 50 (c) CTC-SP2 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0 25 50

VI. PERFORMANCE EVALUATION OF PURE POLICIES A. Comparison

We compare the pure policies presented in Section IV using the traces from Table I. We consider 45 consecutive weeks from CTC-SP2 and KTH-SP2 and 100 consecutive weeks from SDSC-SP2 and SDSC-BLUE, and we simulate the execution of all the policies for each week and measure the weekly average BSLD given in Equation [START_REF] Tsafrir | Backfilling using system-generated predictions rather than user runtime estimates[END_REF].

Figure [START_REF] Tsafrir | Backfilling using system-generated predictions rather than user runtime estimates[END_REF] illustrates the performance for all the 4 traces. The order of the policies with regard to performance changes between the traces. In general, the policies that prioritize shorter jobs, namely SAF and SPF and LEXP, are better for the average BSLD. SAF comes on top for all the tested traces followed by SPF and LEXP.

As expected, FCFS is not a good policy for minimizing the average BSLD. Although its exact position changes between traces, it always ranks among the worst policies. Interestingly, LEXP, the policy that represents the estimate of the very metric we are trying to optimize, is not the top policy, which indicates the importance of considering the amount of required resources when taking a scheduling decision.

The good performance of SAF, SPF, and LEXP can be explained by the fact that the slowdown of a job is proportional to its length. Longer jobs can wait for a longer time without having their slowdown grow drastically. The slowdown of shorter jobs, however, increases very fast the longer they wait.

B. The one size fits all policy?

From the previous comparison, we can notice that SAF is overall better than all the other tested policies to optimize the average BLSD. It gives the lowest mean on an aggregation of weeks and its outliers are not as extreme as other policies.

Figure 2 illustrates a more detailed comparison between SAF and the other policies on a given workload. We compare the average BSLD of SAF with the average BSLD of the best pure policy for every week individually. As expected, SAF performs well for most weeks. It is either the best policy or very close to the best. However, we can spot many weeks where another pure policy performs better than SAF by a significant margin (e.g. 38, 44, 56, and 85 ). Regardless of which policy outperformed SAF, the observation is the same for the four studied traces; SAF is good overall but it remains far from the optimal in many cases.

Finally, it is worth noting that traces where SAF fails can be found. For example, for the ANL-Intrepid trace from the Parallel Workload Archive [START_REF] Feitelson | Parallel workload archive[END_REF], SPF is the best pure policy with an average slowdown of 35.92 while SAF ranks at 7 over 12 with 39.78. Likewise, with the Sandia trace, LAF is the best with an average slowdown of 7.353 while SAF ranks again at 7 over 12 with 10.396. We pick the traces in Table I to study due to their popularity in the literature [START_REF] Gaussier | Improving backfilling by using machine learning to predict running times[END_REF], [START_REF] Carastan-Santos | Obtaining dynamic scheduling policies with simulation and machine learning[END_REF]. Moreover, the focus of this work is not to show that a single pure policy is dominant but to study the possibility of improving the performance of schedulers using historical data. week average bounded slowdown Fig. 3. Comparing the performance of various policies on the SDSC-SP2 trace. w* represents the best policy in hindsight for every week. w* train is the policy obtained from learning on the Training weeks, and w greedy gives the results of testing the best policy of one week on the next.

Policy

Training 1) Learning over a long period of time: The idea is to divide the trace into two equal parts and see how the best policy on the first half performs on the second. For this particular trace, we decided to ignore the first 28 weeks because the workload at the beginning of the trace is rather light, hence all the tested policies perform similarly. So we consider the first 28 weeks as nonrepresentative of the actual workload. Then divide the 72 remaining weeks into two parts of equal sizes. We call the first part Training and the second part Testing. The aggregated results are illustrated in Table II and the details for each week are given in Figure 3.

Training: w* train , the learned policy, slightly outperforms SAF in general. But if we look at individual weeks we see that SAF still has a lower BSLD sometimes over the training period (e.g. 34 and 52).

Testing: Table II show that w* train performs quite well compared to other policies. But it is still surprisingly equivalent and even outperformed by SAF. Figure 3 shows the performance of both individual weeks. SAF is better for some weeks (namely 68, 81, and 82) but w* train is better for others like (e.g 73,79, 85). Sometimes both policies give similar results.

Although Training and Testing do not particularly appear as different, The best weights for Training are not the best for Testing: there is no one size fits all strategy. By comparing w* (see Section VII-A) and w* train in Figure 3, we observe that w* train is far from the best possible vector even for the weeks used for Training.

2) Learning over a short period of time: We investigate if the policy learned from one week can be effective on the next by evaluating the vector learned from week i (w* i ) on the next week i + 1.

In Figure 3, the policy w greedy represents the results of simulating the workload of one week using the top policy from the previous week. There are unfortunately no patterns to distinguish. The vectors learned from the previous week seem to evolve and perform in a chaotic manner. Sometimes they perform better than SAF (weeks 56, 83, and 89), sometimes worse (weeks 20 and 55), and sometimes on par with SAF.

Using the policy learned from the previous week does not lead to good performance at all. We hypothesize that the structure of the workload (the jobs submitted) changes substantially from one week to the next. Thus, online-learning the optimal weights may be very difficult.

C. Exploring the search space

In this section, we explain why there is no single vector of weights that is optimal for all cases. We visualize the search space and observe the position of the optimum for different weeks.

Figure 4 is a 2D representation of the search space for 4 consecutive weeks of the SDSC-SP2 trace. Each week is represented by two figures: the left figure displays the weekly average BLSD where q ≤ 0 and the right figure, where q ≥ 0. The and axes respectively represent the weights of p and wait. The optimal combination always lies in the lightest area and is represented by a red dot.

The coordinates of the optimal point change drastically from one week to another. Using the optimal point of week 72 to schedule week 73 give poor results because the optimal point in 72 lies in an area that has a very high slowdown in week 73. This explains why the short period learning failed.

Furthermore, with the exception of general similarities like the half where q ≥ 0 have a lower BSLD than q ≤ 0, we also observe that the position, shape, and even the size of the optimal area changes radically from one week to the next. This explains why online learning seems compromised without further information.

VIII. INCREASING THE SIZE OF THE SEARCH SPACE: USING MORE JOBS CHARACTERISTICS

In this section, we investigate the impact of using all six job characteristics on performance. Indeed, the experiments in all the previous sections were done with only the three basic job characteristics: p,q, and wait. In this Section we extend the search space to include the three other characteristics introduced in Section IV-A which are a,r,exp.

A. Black-box optimizers: a quick way to find the optimal 1) Algorithm: In the previous Section, finding the weekly best mixed policy was done using a uniformly "exhaustive" search. We made a fine discretization of the whole search space and we selected the weight vector w* that provides the lowest average BLSD. Performing an exhaustive space search becomes costly very fast because the size of the search space grows exponentially with the number of job characteristics we include in the linear combination. Thus another method to find the minimum is required.

Our goal is to find a combination of weights w* that minimize equation ( 4) while enforcing the constraint ||w|| 1 = 1. This can easily be done by optimizing the following objective function:

n j=1 F (score(w, x j )) + λ ||w|| 1 + 1 ||w|| 1 (6)
Function F has a priori no particular properties. Furthermore, we have seen in Section VII-C that the search space is not convex and it may exhibit several local minima. Therefore, gradient-based methods cannot be used and we have to rely on stochastic derivativefree methods. We initially tried the standard simulated annealing method [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF] but it got frequently stuck in local optimums. A study of the existing literature [START_REF] Bianchi | A survey on metaheuristics for stochastic combinatorial optimization[END_REF] led us to the evolutionary algorithms family that considers an ensemble of candidates. We tested several algorithms, Covariance Matrix Adaptation Evolution Strategy (CMA-ES) [START_REF] Hansen | The CMA evolution strategy: a comparing review[END_REF] and eXponential Natural Evolutionary Strategy (XNES) [START_REF] Glasmachers | Exponential natural evolution strategies[END_REF] provided the best results. Since XNES is faster than CMA-ES, we chose the former.

2) Performance: For each week we apply the XNES algorithm to obtain a solution of Equation ( 6) for a vector of dimension 3 (xnes3) and a vector of dimension 6 (xnes6) and we compare the results with the minimum obtained from the space coverage which we call w* 3 (corresponds to the w* used in SectionVII-A). Figure 5 illustrates the results.

For most weeks xnes3 and w* 3 give the same result. For few other weeks, xnes3 managed to slightly outperform w* 3 . This is due to the method used to cover the search space: Each dimension of the vector gets 200 points distributed uniformly over [-1,1]. XNES does not have that constraint, hence it can produce policies that are more "refined". The differences in performance are minor which indicate that XNES managed to find a vector that is the actual or at least very close to the optimum every time. Thus XNES can be considered as a viable option to find an optimal vector.

The BSLD of xnes3 and xnes6 are not very different from each other. For most of the weeks, both vectors perform equally. In some rare cases (weeks 86 for example), xnes3 gives a slightly better performance than xnes6 but the difference is marginal (XNES converged to a local optimum instead of the global optimum in the case of 6). On average xnes6 is better than xnes3 but not by a larger margin.

Increasing the size of the search space by adding job characteristics improves the results by a small very margin.

IX. CONCLUSION

Scheduling parallel jobs in a real HPC platform is a complex task plagued with many uncertainties. Determining an efficient scheduling strategy is difficult due to the volatile nature of the workload. The main result of this work was to optimize the EASY-Backfilling algorithm by reordering the primary queue using policies learned from historical data.

More precisely, we first showed that SAF (Smallest estimated Area First) performs overall better than more popular policies FCFS and SPF. Then, we looked at the scheduling problem from a new perspective by studying a larger class of heuristics obtained from mixed policies that enable us to move from a discrete to a continuous search space. We combined several characteristics extracted from the jobs in a linear expression and we determined the best weight for each characteristic. We showed, moreover, that pure policies are far from the optimal and that important gains can be obtained by using mixed policies. For some weeks in the simulation, we obtained results that are up to 3 times better than the best pure policy. Unfortunately, we observed that the structure of the workload changes too much over time and that whenever a policy performs well on a part of a trace, it does not mean necessarily that it will be efficient on another part of the trace.

Using historical data to predict good scheduling policies for future jobs is not a straightforward task. We observed that the workload itself changes drastically from one time period to the next. We have yet to identify any meaningful pattern to these changes, which raises the question of whether it is possible to apply machine learning on real execution logs or not. Choosing a proper metric to evaluate the performance of a policy in an online scheduling context is also an interesting (but hard) task. In particular, the average BSLD may be enriched since it does not consider the required resource into consideration.

X. ACKNOWLEDGMENT

Fig. 1 .

 1 Fig.1. Tukey box-plot of the weekly average bounded slowdown of pure policies for the 4 traces. The policies are sorted in an increasing order by the mean of the weekly average bounded slowdown for all the weeks. The three most efficient policies are highlighted.

w* train = argmin w 64 week=28average

 64 BSLD week (w)(5) Weeks 28 to 64 (Training): We aggregate using equation 5 and we find the weights w* train that minimizes the sum of the weekly average BSLD over all weeks. Weeks 65 to 100 (Testing): we evaluate w* train on the new Testing weeks.

Fig. 4 .

 4 Fig. 4. Visualization of the search space for 4 consecutive weeks 70, 71,72, and 73. The two diagonal axis represent p and wait. The lighter the area is, the better the performance (lower average BSLD). The optimal area change from one week to the next. The red dot (in the lightest area) represents w * and the blue triangle represents w * train .

Fig. 5 .

 5 Fig. 5. Comparing average BSLD of the vectors of the 3 original features (xnes3) with the extended vector of 6 features (xnes6) and the minimum we obtain space coverage (w* 3 )

TABLE I WORKLOADS

 I

TABLE II COMPARING

 II THE SUM OF THE AVERAGE BSLD FOR SDSC-SP2 FOR WEEKS: 65 TO 100. THE HIGHLIGHTED VALUES ARE OBTAINED IN HINDSIGHT.

The authors are sorted in an alphabetical order. The authors would like to thank Valentin Reis for his key contribution to the origin of this work and for providing the simulator used throughout the experimental campaign. We are also grateful for Danilo Carastan-Santos and Millian Poquet for their help and comments. We thank the contributors of the Parallel Workloads Archive, Victor Hazlewood (SDSC SP2), Travis Earheart and Nancy Wilkins-Diehr (SDSC Blue), Lars Malinowsky (KTH SP2), Dan Dwyer and Steve Hotovy (CTC SP2). This work was partially supported by the French research agency (Energumen ANR-18-CE25-0008)

SAF

week average bounded slowdown Fig. 2. Comparing SAF, the best pure policy on average, with the best pure policy for every week for the SDSC-SP2 trace.

To make the reading and the analysis easier and to avoid redundancy, all the experiments in the following sections are done using a single trace: SDSC-SP2. We refer the interested reader to Section XI of the research report [START_REF] Legrand | Adapting Batch Scheduling to Workload Characteristics: What can we expect From Online Learning?[END_REF] for a complete analysis of the other traces from which similar conclusions can be reached

VII. SCHEDULING USING MIXED POLICIES

In the previous Section, we showed that among all the pure evaluated policies there is no single policy that is dominant across all weeks. SAF offers a reasonable compromise but it fails in many cases. This motivates the need for developing a scheduling approach that adapts to the state of the system and the workload.

In this section, for the sake clarity, we limit the mixed policies vector to only three elements: x j = (q j , pj , wait j ). Further results involving all the six features will be presented in Section VIII.

A. Performance of pure and mixed policies

We consider a set of 100 weeks from SDSC-SP2 and we separate them in the same way as in Section VI. Then, for each week we perform the following:

• Simulate using the two pure policies: (1)FCFS because of its popularity (although it is not very effective for the Average BSLD), and (2)SAF because, as observed in Section VI-A, it is the best policy overall. • Generate a large number of weight by performing a uniform discretization of the search space. We take a sequence of 100 points from each dimension which can take a negative or a positive value. Thus, for three features we have 100 3 .2 3 = 8.10 6 points.

Then we simulate each point and we pick the best vector i.e. the one that gives the lowest scores for this week, and which we denote w*.

The results are shown in Figure 3. w* represents the average BLSD of the best weekly linear combination. The gain of w* compared to the pure policies varies significantly. We can classify the weeks into two types.

• Weeks where there is no or a very small difference in performance between both pure and mixed policies. The average BSLD of such weeks tends to be very close to 0. Weeks 43, 92 and 94 are good examples of this type. Their workload is so relaxed that no optimization is required. According to Figure 3, around half of the weeks of SDSC-SP2 belong to this type. • Weeks where there is a difference in performance between the policies. For weeks such as 64, 73, 79, and 100, we observe significant variation in performance and a much higher BLSD. For this type, we also notice that w* is significantly better than all other policies. In week 73, for example, w* reduces the average BLSD by a substantial margin, approximately 2.5 times less than SAF, the best pure policy for that week, and 3 times less than FCFS. Pure policies are thus far from the optimal and a carefully selected combination of features can give substantial improvement. However, the value for the best weight for each week can be quite different from the others (w* i = w* j ∀i = j ∈ 1..100). This shows the changing nature of the workload through time and will be discussed in detail in Section VII-C. B. Learning: scheduling using best combination learned from a previous part of the trace.

In this section, we evaluate the generalization capacity of our approach. We investigate how the best combination w* for a part of the trace performs on another part. We evaluate this ability by using two different strategies.


Keeyoung Kim
email: kykim@sunykorea.ac.kr

Simon S Woo
email: simon.woo@sunykorea.ac.kr

When George Clooney is not George Clooney: Using GenAttack to Deceive Amazon's and Naver's Celebrity Recognition APIs

Keywords: Adversarial Example, Black-box attack, Genetic Algorithm

In recent years, significant advancements have been made in detecting and recognizing contents of images using Deep Neural Networks (DNNs). As a result, many companies offer image recognition APIs for use in diverse applications. However, image classification algorithms trained with DNNs can misclassify adversarial examples, posing a significant threat to critical applications. In this work, we present a novel way to generate adversarial example images using an evolutionary genetic algorithm (GA). Our algorithm builds adversarial images by iteratively adding noise to the original images. Unlike DNN based adversarial example generations by other researchers, our approach does not require GPU resources and access to the target DNNs' parameters. We design, GenAttack, a simple yet powerful attack algorithm to create adversarial examples using complex celebrity images and evaluate those with realworld celebrity recognition APIs from Amazon and Naver. With our attack, we successfully deceive Amazon's and Naver's APIs with a success probability of 86.6% and 100%, respectively. Our work demonstrates the practicability of generating adversarial examples and successfully fooling the state-of-the-art commercial image recognition systems.

Introduction

Deep learning algorithms have been revolutionary in improving the performance of a wide range of applications, including computer vision, speech processing, and natural language processing. In particular, Convolutional Neural Networks (CNNs) have been extremely successful in detecting and recognizing the content of images [START_REF] Szegedy | Inception-v4, inceptionresnet and the impact of residual connections on learning[END_REF][START_REF] Ren | Faster r-cnn: Towards real-time object detection with region proposal networks[END_REF][START_REF] He | Mask r-cnn[END_REF]. Due to the success of deep learning, many companies including Amazon [START_REF]Amazon rekognition -deep learning-based image analysis[END_REF] and Naver [START_REF]Naver -clova face recognition[END_REF] have unveiled image recognition and analysis APIs to be used for various applications. However, as Szegedy et al. [START_REF] Szegedy | Intriguing properties of neural networks[END_REF] and Goodfellow et al. [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF] showed that an imperceptible small perturbation to an input image can arbitrarily change the prediction of a deep learning-based classifier. These examples are referred to as adversarial examples, which optimize perturbations to maximize prediction errors. Moreover, Goodfellow et al. [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF] showed that these adversarial examples are not difficult to generate, and are robust and generalizable. Therefore, the robustness and stability of DNNs when facing adversarial examples have recently drawn the attention of many researchers [START_REF] Szegedy | Intriguing properties of neural networks[END_REF][START_REF] Vidnerová | Evolutionary generation of adversarial examples for deep and shallow machine learning models[END_REF][START_REF] Carlini | Towards evaluating the robustness of neural networks[END_REF][START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF]. In particular, adversarial examples can be a serious threat to image processing applications such as airport security systems, self-driving cars, and user identification for financial transaction systems.

In this work, unlike other DNN-based attack methods [START_REF] Carlini | Towards evaluating the robustness of neural networks[END_REF], we propose an alternative approach to generate adversarial images using an evolutionary genetic algorithm (GA) to deceive the DNN based state-of-the-art image recognition APIs. We perform GenAttack, a simple yet powerful practical black-box attack using our GA to fool commercial APIs, and show that those commercial APIs are easily fooled with a high probability of success. Our contributions are summarized below:

1. We propose GenAttack, an attack algorithm using GA to generate adversarial images. We test GenAttack against larger, and more complex realistic images ranging from 200×300 to 2,100×2,800 pixels, unlike other research that utilizes the small image sizes. GenAttack adopts the heuristic optimization method so that it can easily deal with large number of pixels in parallel. 2. We evaluate our attacks with state-of-the-art commercial celebrity detection APIs from Amazon [START_REF]Amazon rekognition -deep learning-based image analysis[END_REF] and Naver [START_REF]Naver -clova face recognition[END_REF] as representative test cases. Our approach effectively creates adversarial images and deceives Amazon and Naver APIs with 86.6% and 100% success rate. 3. We also show transfer learning of an adversarial image. We demonstrate that an adversarial example successfully fools one classifier (e.g. Naver) can be used to fool another classifier (e.g. Amazon), which could not be deceived originally. Therefore, transfer learning can be maliciously used to fool a classifier more effectively.

This paper is organized as follows. We discuss related work of adversarial examples in Section 2. We explain our GA and GenAttack in Section 3, and describe our experiment in Section 4. Section 5 presents the results of our evaluation of GenAttack. In Section 6, additional experiment for transfer learning is presented. We provide the possible defense mechanism, discussion, and limitations in Section 7. Finally, Section 8 offers conclusions.

Related Work

Adversarial examples [START_REF] Szegedy | Intriguing properties of neural networks[END_REF] are examples, which machine learning models misclassify, where those examples are only slightly different from correctly classified examples. Applying an imperceptible perturbation to a test image can produce an adversarial example. Adversarial examples were first discussed and used against conventional machine learning algorithms by Barreno et al. [3] to evade handcrafted features. In particular, Biggio et al. [START_REF] Biggio | Evasion attacks against machine learning at test time[END_REF] created adversarial examples for a linear classifier, SVM, and neural network using a gradient-based method. Szegedy et al. [START_REF] Szegedy | Intriguing properties of neural networks[END_REF] first introduced the adversarial examples for the deep neural networks by adding small perturbations on the input images. They used the white-box L-BFGS method to generate adversarial examples using MNIST, ImageNet, AlexNet, and QuocNet with high probability. Since L-BFGS uses an expensive linear search, Fast Gradient Sign Method (FGSM) was proposed by Goodfellow et al. [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF], which can be computed using back-propagation. RAND-FGSM [START_REF] Tramèr | Ensemble adversarial training: Attacks and defenses[END_REF] is proposed to add randomness during the gradient update. Papernot et al. [START_REF] Papernot | The limitations of deep learning in adversarial settings[END_REF] presented an efficient saliency adversarial map (JSMA). Their approach can find the input features that make the most significant change to the output so that a small portion of features can fool DNNs. DeepFool was proposed by Moosavi-Dezfooli et al. [START_REF] Moosavi Dezfooli | Deepfool: a simple and accurate method to fool deep neural networks[END_REF], which determines the closest distance from original input to the decision boundary, and performs an iterative attack to approximate the perturbation. Moreover, Carlini and Wager [START_REF] Carlini | Towards evaluating the robustness of neural networks[END_REF] showed that the back propagation method with DNNs can generate adversarial examples more effectively, and demonstrated that existing defense methods are not effective. Papernot et al. [START_REF] Papernot | Practical black-box attacks against machine learning[END_REF] introduced the practical black-box attack approach. Their approach consists of training a local model to substitute for the target DNN, using inputs synthetically generated by an adversary and labeled by the target DNN. But, their evaluation results are based on the trivial MNIST dataset. Nguyen et al. [START_REF] Nguyen | Deep neural networks are easily fooled: High confidence predictions for unrecognizable images[END_REF] implemented the evolutionary algorithm to generate images that humans cannot recognize but DNNs can. In addition, Vidnerov and Neruda [START_REF] Vidnerová | Evolutionary generation of adversarial examples for deep and shallow machine learning models[END_REF] showed that the evolutionary method can generate adversarial examples from random noise. But they only tested classifiers to detect the trivial 0-9 digit images. Hosseini et al. [START_REF] Hosseini | Googles cloud vision api is not robust to noise[END_REF] showed that Google's Cloud Vision API can be deceived by images added with random noise. Our approach is more sophisticated than the approach by Hosseini et al. [START_REF] Hosseini | Googles cloud vision api is not robust to noise[END_REF] which simply adds uniform noise. In our approach, the GA locally optimizes the noise level at each iteration. Our advantage is that we generate adversarial images more effectively. We provide the comparison between our and random noise distribution in Section 5. Network distillation was proposed by Papernot et al. [START_REF] Papernot | Distillation as a defense to adversarial perturbations against deep neural networks[END_REF] to reduce the size of DNNs by extracting knowledge from DNNs to improve the robustness by 0.5% to 5% on MNIST and CIFAR10 dataset, respectively. Goodfellow et al. [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF] and Huang et al. [START_REF] Huang | Learning with a strong adversary[END_REF] introduce the adversarial training, an approach to include adversarial examples in the training stage. They incorporated adversarial examples in training sets, and showed it improved the robustness. Tramer et al. [START_REF] Tramèr | Ensemble adversarial training: Attacks and defenses[END_REF] proposed Ensemble Adversarial Training method to train a defense model with adversarial examples generated from multiple sources. However, they found that it is difficult to anticipate specific adversarial examples and include those during the training stage. Madry et al. [START_REF] Madry | Towards deep learning models resistant to adversarial attacks[END_REF] proved that adversarial training with large network capacity can defend the first-order adversary. Also, adversarial detection [START_REF] Lu | Safetynet: Detecting and rejecting adversarial examples robustly[END_REF][START_REF] Song | Pixeldefend: Leveraging generative models to understand and defend against adversarial examples[END_REF][START_REF] Bradshaw | Adversarial examples, uncertainty, and transfer testing robustness in gaussian process hybrid deep networks[END_REF] have been proposed by others to detect adversarial examples during testing.

Design of Our Approach

First, we define the adversarial example problem and the objective of our approach. Next, we present the details of the GA to generate adversarial examples, and GenAttack to deceive commercial APIs.

Adversarial Examples for Image Classification

Szegedy et al. [START_REF] Szegedy | Intriguing properties of neural networks[END_REF] shows the existence of targeted adversarial examples as follows: given a valid input image I, and a target t = C * (I), it is possible to find a similar input I such that C * (I ) = t, yet I and I are close according to some distance metric. In Untargeted adversarial examples, attacks only search for an input I so that C(I) = C * (I ) and I and I are close. Then, finding adversarial examples can formulated as follows similar to [START_REF] Szegedy | Intriguing properties of neural networks[END_REF][START_REF] Yuan | Adversarial examples: Attacks and defenses for deep learning[END_REF]:

min I ||I -I|| s.t. C(I) = C * (I ),
(1) where ||•|| is the distance between two samples, and C is a trained deep learning image classifier. The goal is to find the input I minimizes the distance between I with small perturbations. We aim to find adversarial examples for an untargeted case, where we find an image, I that C misclassifies from I to I .

Creating Adversarial Examples using Genetic Algorithm (GA)

In order to perform a black-box attack, we develop GA to effectively generate adversarial images against commercial APIs without access to any of their DNN model parameters, and do not require any GPU resources. The goal of our GA is to inject a small amount of optimum noise to an original image so that commercial APIs misclassify the original image, while humans can still easily recognize the original celebrity as shown in Fig. 1. We formulate our GA as follows: Population and Individuals: A population is a set of individuals, and they are defined as uniform noise matrices, where their size is the same as the original input celebrity image. To produce the noise-added adversarial images from the noise matrices, we use the modified method based on Carlini and Wagner [START_REF] Carlini | Towards evaluating the robustness of neural networks[END_REF], as follows:

X = tanh(tanh -1 ( I I max -0.5) + α × N) (2)
I = (X -min(X)) (max(X) -min(X)) × I max (3)
In Eq. 2, we transform an original (target) image I to tanh -1 space, and map it from -0.5 to 0.5 range by dividing by I max and subtracting 0.5, where I max is the maximum RGB pixel value. Next, we add I with a noise matrix N multiplied by the coefficient α. Then, we re-transform the noise added image back to the original space to obtain the adversarial example I in Eq. 3. As shown in Fig. 1, α adjusts a noise level in generating an adversarial image, and α is searched from multiplying by 2 or subtracting 0.05 in [0.0, 0.9] interval. Generally, a higher α increases the success rate of our attack, however, it will produce a very noisy image. Hence, minimize the noise amount, α, using the following fitness function.

Fitness function: We use the following L 1 loss as a distance measure between the original image I, and the adversarial image I :

L 1 = 1 n |(I -I )|, ( 4
)
where n is the number of pixels in the image I. Then, we define the fitness function f as follows in Eq. 5:

f = P o -P d + γ × L 1 , (5)
where P o is the predicted probability for the original label and P d is the predicted probability for any other wrong labels. We can obtain either one of P o or P d and set the other to zero, because the commercial APIs only return the highest probability of one of P o or P d . Next, we formulate our GA as a minimization problem with the value of the fitness function in Eq. 5. to produce the best individual which has high P d , and the low P o , and L 1 values. In Eq. 5, γ is another coefficient to balance the noise amount to deceive APIs by guiding a GA to find adversarial images with the least amount of noise, where γ can be chosen from 0.01 to 0.1 in this work. Also, we automatically choose γ, which is inversely proportional to α, because P o and P d always have the values between 0 to 1. In a default setting, we run 5 epochs to generate an adversarial example for a target image after fixing α, where α requires from several ten to three hundred steps. The number of steps in one epoch -children generated by crossover and then accepted to inherit to the next generation -is the same to the number of populations. The number of API calls per each step in the algorithm will be affected by the chance how much mutation will be called.

Selection: We implement a tournament selection, where we set the tournament size to four. Then, two of four individuals in one tournament will be selected. In our design, the more fit has 80% chance to win, and the less fit has 20% chance to maintain a good variety in the population and explore wider search areas to find a global optimum. After selection, two chosen parents move to the next crossover stage.

Crossover and Inheritance: Crossover permutes two selected parents. We design a simple crossover for 2D matrix as shown in Fig. 2. First, we obtain a random point (x, y) in the noise matrices of two selected individuals. We use this point as an origin point to start. Next, we throw a tetrahedron die. If we get N , between 1 to 4, the quadrant N of the noise matrices will be exchanged between two individuals.

Then, the newly generated children are chosen to inherit to the next generation, if they have a better fitness than their parents. To conserve the best fit individuals and not to lose them, we also added the following inheritance heuristics: if the best individual in the current generation is better than any individuals in the next generation, we copy the best individual in the current generation to the next generation.

Mutation: Mutation aims to reduce the noise level of adversarial images. We design two mutation methods based on the class labels of the newly produced individuals. The first mutation method is used, when the noise added image is still classified into the original class. Then, we add a small amount of random noise to individuals to produce more variations. We use the second mutation method, when a noise injected image is classified into another class. In this case, we try to reduce the noise slightly by using the following local optimization technique: We randomly choose 2% of the pixels in the noise matrix, and reduce their magnitude by 30%. If successful, we repeat the same process for up to 5 more times. In this local optimization step, we only accept mutated individuals with improved fitness values. We propose the GA-based attack, GenAttack, against commercial APIs, and present the details of our attack procedures. First, we test the commercial API with an original image, and check whether the API correctly recognizes the celebrity image from the returned initial output label, I.Label, and its confidence value. If it is correctly recognized, it becomes our target celebrity image to create an adversarial example. If not, we discard this image, since the API is wrong in the first place. Next, we initiate GenAttack and start querying each commercial API with the noise-added image. If the returned result produces an incorrect output label (i.e., some other celebrity), that means our attack is successful, and we successfully create an adversarial image. We label this output class as an adversarial label, A.Label. If it consistently returns the correct I.Label, we slightly increase and adjust α, and compute the fitness function, searching for the optimum noise combinations according to our GA. We iteratively repeat this process for several epochs. until we successfully force the API to produce an incorrect output (A.Label). Finally, if we can deceive an API, so that the API returns a different name from the I.Label, we declare the attack is successful. If we cannot deceive, or the API returns 'Unrecognized' (UNKR), the attack is not successful, and we fail to create an adversarial image. Our attack criteria is much stronger than prior research [START_REF] Hosseini | Deceiving google's cloud video intelligence api built for summarizing videos[END_REF][START_REF] Hosseini | Googles cloud vision api is not robust to noise[END_REF], which includes UNKR as a success.

Experiment

The goal of our experiment is to evaluate generated adversarial examples, and further test the robustness of commercial APIs using GenAttack. We used Amazon Rekognizer [START_REF]Amazon rekognition -deep learning-based image analysis[END_REF], and Naver Clover Service [START_REF]Naver -clova face recognition[END_REF] to provide a side-by-side attack success, and robustness comparison between these providers. In particular, we used the celebrity recognition APIs, which are offered from both providers, and celebrity images are relatively easy to find. Also, they are complex and realistic. Although Cloud Vision API by Google also provides the face image analysis information, and returns the top 20 relevant entities from the Internet, their returned labels are based on web search results, not images themselves. Hence, a side-by-side comparison to Amazon and Naver is difficult, therefore, we do not evaluate Google's API in this paper.

Dataset

We chose 119 famous celebrities (72 men and 47 women) as a dataset. Although we try to select celebrities that are both popular in America and Asia, we hypothesize that the Naver API based in Asia would be more optimized for Asian celebrities over American and European celebrities. Hence, we include several Asian celebrities to test, even though they may not be so well known in America or Europe. We use the practical image sizes ranging from 200×300 to 2,100×2,800 pixels. These are much larger than the small benchmark datasets such as MNIST (28×28), CIFAR-10 (32×32), and ImageNet (227×227) which have been used in prior research [START_REF] Carlini | Towards evaluating the robustness of neural networks[END_REF][START_REF] Nguyen | Deep neural networks are easily fooled: High confidence predictions for unrecognizable images[END_REF]. Some sample celebrity images and names are shown in Fig. 3 and Table 1.

Experimental Setup

We run 5 epochs to get an adversarial example for all 119 target images, starting with α= 0.1. Then we automatically adjust α from 0.05 to 0.9 based on the attack success and confidence value returned from the API. We run 5 more epochs to generate an adversarial example for a target image after obtaining α from the GA. If we consecutively fail to produce an adversarial image in the next 10 steps, we increase α and repeat the process again. If we find an adversarial images in 10 consecutive steps, we decrease α to reduce the noise.

Results

In this section, we report the attack success rate and analyze generated noise in adversarial examples from GenAttack.

Attack Success Rate

Table 1. summarizes our attack results for several celebrity images. Due to space limitations, we only present celebrities whose original image was correctly recognized by both APIs. In Table 1, the fist column is the correct celebrity name for each image followed by its initial I.Label and I.Pr., where those indicate the Fig. 3: Original vs. Generated Adversarial Images for 65 celebrities original input label and its confidence probability returned by each API. And A.Label and A.Pr. are the output label and its confidence probability for adversarial images we generate with our GenAttack. 'UNKR' means that the original image is successfully recognized, while the noise-added image is unrecognized. Amazon API correctly recognizes 112 images from the 119 input images. Our algorithm attacked those 112 images, and achieved the overall 86.61% success rate, successfully creating 97 adversarial examples. We find that GenAttack effectively adds and improves noise from a predicted label with a low initial confidence value returned for its initial adversarial example generation attempt. From Table 1, we can observe that GenAttack guides noise to find a path from one output celebrity class to another celebrity class with fairly high confidence values (A.Pr.) in many cases shown in the 5th column in Table 1.

On the other hand, the Naver API correctly recognizes only 45 out of the 119 original images, misclassifying many original celebrity images from America and Europe. Hence, we validate Naver is more localized to Asian faces. Among those correctly recognized 49 images, GenAttack successfully creates the adversarial images for all 49 images, yielding 100.00% success rate. Naver seems to generate different output labels for many Asian celebrities even with a small amount of added perturbations, and Naver is much easier to fool. However, their A.Pr. are generally lower than Amazon, which means Naver outputs the new label with smaller confidence value. With the Naver API, we observed that Tom Cruise was the most difficult one to find an adversarial example for. We hypothesize that Naver might not have many faces that are similar to Tom Cruises or have faces that are clearly distinctive. Therefore, Naver locks on to the features of Tom Cruise and we think GenAttack could not easy to find other similar classes. In Fig. 3, we present 65 original celebrity images (left) and adversarial images (right) generated from GenAttack side-by-side for a comparison. As we can examine, the generated adversarial images are very close to the original images, and humans can trivially recognize the generated adversarial examples.

Noise and Image Analysis

We carefully analyze the noise patterns of the adversarial images, where we add random noise in tanh space. Also, we compare our noise with uniform noise in tanh space to characterize differences. (c) and (h) are the uniformly generated noise for the same images. As we compare these two sets of images, we can clearly observe that our GA tends to better capture face features of the input and injects noise, while random noise spreads over all pixels. In order to analyze the differences more clearly, we zoom in the face areas. As we can observe from Figs. 4.(d) and (e), and (i) and (j), we find noise generated from the GA more closely changes the face features so that the CNNs based classifier can more easily make a mistake and steer towards another celebrity. On the other hand, random noise is distributed uniformly over all pixels. Hence, we clearly observe the differing noise distribution, and our generated noise appears to better learn the face features with the GA to optimize noise to increase a classification error.

Noise Filtering Defense and Generated image sizes: Generally, prefiltering can be an effective defense mechanism as proven in other research [START_REF] Hosseini | Deceiving google's cloud video intelligence api built for summarizing videos[END_REF]. However, it is not in our case. We applied both Gaussian (linear) and Median (non-linear) filters to remove added noise from GA, where these filters have been a successful defense shown from other research [START_REF] Hosseini | Deceiving google's cloud video intelligence api built for summarizing videos[END_REF]. In our case, noise filtering cannot prevent from generating adversarial examples for both Amazon and Naver, but generated adversarial images need slightly more noise than the non-filtered case. Also, we find that our approach effectively generates adversarial examples for any size of input celebrity images in our dataset, ranging from 200×300 to 2,100×2,800 in pixels. Hence, we demonstrate that our GA can generate almost size-invariant adversarial images without loss of any performance.

Transfer Learning for Attacks

We performed the transfer learning capability of our proposed method. If our algorithm can deceive one classifier, we hypothesize we can deceive another API. Hence, attackers can use this transfer learning for an attack, where adversarial features (noise matrices) learned from one DNNs (e.g. Naver) can be used to create an adversarial image for another classifier (e.g. Amazon), and vice versa. Among all 119 celebrity images, we obtained ten adversarial samples that successfully fool only one of the APIs, as shown in Table 2. In our attack, we query both Naver and Amazon APIs simultaneously, and calculate fitness as follows by extending the fitness function for the single API in Eq. 5:

f = P Amazon o -P Amazon d + P N aver o -P N aver d + γ × L 1 , (6)
where P Amazon o and P N aver o are the predicted probability for original label from Amazon and Naver, and P Amazon d are P N aver d are the predicted probability for other label produced from Amazon and Naver similar to Eq. 5. When optimizing α in Eq. 2, we only consider the adversarial image generation success rate of the target API, which was originally unsuccessful. For example, if we want to find adversarial examples for the Amazon API with the help from the Naver API, we optimize α based on the success rate of the Amazon API.

We performed the transfer learning attack experiment for all available 10 test cases. Overall, 7 out of 10 transfer learning attack were successful, improving the most of UNKR (originally failed attacks by the single API) to other celebrities. Among those, where Amazon API fails to recognize 8 of celebrities initially, our algorithm successfully fools Amazon API with the help from Naver API.

As shown in Table 2, six of (Before) 'UNKR' were successfully classified to (After) other celebrities. However, creating adversarial images for Kate Maria, and Kim Yuna were unsuccessful, even using Naver API. On the other two cases, where our algorithm successfully attacked Amazon API but not Naver API initially, we performed the transfer learning attack on Naver with the help from Amazon. Naver was originally correct for "Sohee" but Amazon led Naver to misclassify the correct label "Sohee" to "Park Soo-jin" (the same adversarial label in Amazon, as shown in blue). Hence, this shows that targeted attack is possible via transfer learning, making other celebrity to a specific victim label (e.g. Park Soo-jin). Also, Naver successfully launched the targeted attack for "Sooyoung" to be "Solji" (shown in blue) in the same way. This demonstrates that the same fake label can be exactly transferred from one classifier to another classifier. Hence, noise generated from our algorithm is transferable between classifiers for generating adversarial examples. Hence, attackers can practically leverage transfer learning to improve his attacks against DNNs. Robust DNNs and conservative reporting: One possible defense approach is to make DNNs more robust against noise via adversarial training with GA [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF]. Also, it is better to be more conservative in reporting an output label, when a confidence value is low. For example, if the confidence value is below 70%, APIs can generate 'UNKR'. In this way, APIs do not provide any feedback to attackers, and adversarial example generation cannot be proceeded. Instead of attempting to make the best guess always, it is important to know "when APIs do not know." From the defense perspective, it is better to be conservative and even not to report any results when confused. However, clear trade-offs among customers' service needs, performance, and security requirements have to be considered to better design the overall defense mechanisms. Network Level Rate Limiting and Noise Filtering: In order to create adversarial examples, several queries need to be made to obtain returned output labels and confidence values. The large number of API queries per sec. for the same or similar images can be a suspicious adversarial attack activity. Hence, various rate limiting techniques such as CAPTCHAs and network defense mechanisms can be employed. However, this cannot be effective for distributed GenAttack querying over multiple IPs or with slower rates. Also, we need a more sophisticated pre-filtering strategy to learn noise patterns generated from our GA, and remove those more effectively. Currently, we are investigating improved noise filtering techniques.

Limitations and future work: Even though GA searches for an optimum noise value, it is not guaranteed to find a global optimum noise. GA can resort on the local optimum, because of the nature of the evolutionary algorithm. Also, finding an optimum noise without access to DNN parameters is a challenging task. Further empirical experiments and theoretical analysis are needed to control different GA parameters to fine-tune the noise. For future work, we plan to compare GenAttack with other attack and defense mechanisms [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF][START_REF] Kurakin | Adversarial machine learning at scale[END_REF][START_REF] Madry | Towards deep learning models resistant to adversarial attacks[END_REF][START_REF] Tramèr | Ensemble adversarial training: Attacks and defenses[END_REF].

Conclusion

We introduce a simple yet powerful method, GenAttack, to generate adversarial images, which does not require any knowledge about DNNs or use GPU resources. GenAttack optimizes noise using a iterative approach and can provide significant benefits over other complex gradient based estimation attacks. Further, we show that GenAttack is highly practical, and is transferable to attack other classifiers.

Fig. 1 :

 1 Fig. 1: Amazon API misclassifies the noise-added Audrey Hepburn image I to Jack Kamen, while it correctly classifies the original image I to Audrey Hepburn

Fig. 2 :

 2 Fig. 2: Description of the Crossover Process 3.3 Genetic Algorithm-based Attack (GenAttack)

Fig. 4 :

 4 Fig. 4: Comparison of noise distribution (GenAttack vs. Uniform Noise) Figures 4.(a) and (f) are the adversarial examples we produced for Jack Ma and Jennifer Lawrence. In Fig. 4, brighter yellow represents a higher pixel value, and dark blue indicates a lower pixel value. Figures 4.(b) and (g) only show the generated L 2 noise, and Figs.(c) and (h) are the uniformly generated noise for the same images. As we compare these two sets of images, we can clearly observe that our GA tends to better capture face features of the input and injects noise, while random noise spreads over all pixels. In order to analyze the differences more clearly, we zoom in the face areas. As we can observe from Figs.4.(d) and (e), and (i) and (j), we find noise generated from the GA more closely changes the face features so that the CNNs based classifier can more easily make a mistake and steer towards another celebrity. On the other hand, random noise is distributed uniformly over all pixels. Hence, we clearly observe the differing noise distribution, and our generated noise appears to better learn the face features with the GA to optimize noise to increase a classification error.

Table 1 :

 1 Examples of attack result against Amazon and Naver APIs with each celebrity

	Celeb	I.Label	Amazon I.Pr. A.Label	A.Pr. I.Label	Naver I.Pr. A.Label	A.Pr.
	Sohee	Sohee	1.00 Park Soo-jin	0.60 Ahn Sohee	1.00 Ahn Sohee	1.00
	Alicia Keys	Alicia Keys	1.00 Cindy Bruna	0.79 Alicia	1.00 Alicia	0.28
	Kim Yuna	Kim Yuna	0.99 UNKR	0.00 Yuna Kim	1.00 Choi Ja-hye	0.24
	Kim Soo-hyun	Kim Soo-hyun	0.97 Kim Kiri	0.84 Kim Soo-hyun 1.00 Choi Yonggeun 0.74
	Kate Mara	Kate Mara	1.00 UNKR	0.00 Kate Mara	1.00 G. Atkinson	0.59
	Megan Fox	Megan Fox	1.00 Maimie McCoy 0.61 Megan Fox	1.00 G. Atkinson	1.00
	Jun Ji-hyun	Jun Ji-hyun	1.00 Yang Lan	0.70 Jun Ji-hyun	0.24 Gong Hyeon-ju 0.25
	Song Hye-kyo	Song Hye-kyo	0.99 Juri Ueno	0.77 Song Hye-kyo	0.87 Hirano Yuta	0.45
	Park Ji-sung	Park Ji-sung	0.74 Park Chuyoung 0.86 Park Ji-sung	1.00 Hwang In-hoo	0.27
	Im Yoon-ah	Im Yoon-ah	1.00 UNKR	0.00 Im Yoon-ah	1.00 Im Seong-eon	0.68
	ShinSoo Choo	ShinSoo Choo	0.99 Y. Tsutsugo	0.59 ShinSoo Choo	0.58 J. Hyeonseok	0.21
	Song Joong-ki	Song Joong-ki	1.00 Steven Ma	0.84 Song Joong-ki 1.00 Ji Jin-hee	0.16
	Seohyun	Seohyun	1.00 J-Min	0.89 Seohyun	1.00 Jo Yoon-hee	0.50
	Eric Mun	Eric Mun	1.00 Tao Lin	0.99 Eric Mun	1.00 Joo Sang-wook 0.34
	Lee Min-ho	Lee Min-ho	1.00 Lee Joon-gi	0.72 Lee Min-ho	1.00 K. Min-hyeok	0.99
	Hyun-jin Ryu	Hyun-jin Ryu	1.00 UNKR	0.00 Hyun-jin Ryu	1.00 Kim Dong-ju	0.46
	Yoo Jae Suk	Yoo Jae Suk	0.92 Marshall Allen	0.92 Yoo Jae-suk	1.00 Kim Dong-yeon 1.00
	Lee Seung-gi	Lee Seung-gi	1.00 Keisuke Koide	0.55 Lee Seung-gi	0.76 Kim Min-sang 0.73
	Ok Taecyeon	Ok Taecyeon	0.95 Huang Jingyu	0.86 Ok Taecyeon	1.00 Kim Min-soo	0.44
	Son Yeon-jae	Son Yeon-jae	1.00 Park So-youn	0.88 Son Yeon-jae	0.96 Kim Tae-ri	0.67
	Kang Ho-dong	Kang Ho-dong	1.00 Tommy Chang	0.80 Kang Ho-dong 1.00 Kim Yeongseok 0.49
	Kwon Yuri	Kwon Yuri	0.99 UNKR	0.00 Yuri	1.00 Lee Eun-jeong 0.21
	Lionel Messi	Lionel Messi	0.98 Paul Anderson	0.72 Messi	1.00 Lee Il-woong	0.33
	IU	IU	0.99 H. Jungeum	0.92 IU	0.97 Lee Ji-eun	0.76
	Lee Byung-hun	Lee Byung-hun	1.00 Kim Byung-man 0.89 Lee Byung-hun 1.00 Lee Sang-woo	0.27
	Matt Damon	Matt Damon	1.00 F. Marques	0.84 Matt Damon	1.00 Matt Damon	0.59
	Mark Wahlberg	Mark Wahlberg 1.00 Shawn Hatosy	0.75 Mark Wahlberg 1.00 Oh Ji-myeong	0.32
	Uli Stielike	Uli Stielike	1.00 D. Pleasence	0.99 Stielike	1.00 Oh Ji-myeong	0.24
	Lily Collins	Lily Collins	1.00 S. Carpenter	0.84 Lily Collins	1.00 Oh Seo-woon	0.45
	Tom Cruise	Tom Cruise	1.00 B. Daugherty	0.89 Tom Cruise	1.00 Olivier	0.61
	Jessica Jung	Jessica Jung	1.00 Shin Bora	0.89 Jessica Jung	1.00 Park High	1.00
	Lee Chungyong	Lee Chungyong 1.00 DongHyun Kim 0.69 Lee Chungyong 0.95 Park Se-jun	0.75
	Tang Wei	Tang Wei	0.99 Soyou	0.61 Tang Wei	0.63 Ryeowon Jung 0.28
	Shin Se-kyung	Shin Se-kyung	1.00 Akiko Suwanai	0.60 Shin Se-kyung 0.74 Sa Hee	0.23
	Kim Tae-hee	Kim Tae-hee	0.96 Kang So-ra	0.73 Kim Tae-hee	1.00 Seo Yeong-hee 0.74
	Taeyeon	Taeyeon	0.67 UNKR	0.00 Kim Taeyeon	1.00 Shihono Ryo	0.51
	Sooyoung	Sooyoung	0.99 UNKR	0.00 Sooyoung	1.00 Sol Ji	0.83
	Park Tae-hwan	Park Tae-hwan	1.00 UNKR	0.00 Park Tae-hwan 1.00 S. Changhwan 0.74
	Fedor Emelianenko Danny Wuerffel 0.60 UNKR	0.00 Fedor	1.00 Song Jae-ho	0.35
	José Mourinho	José Mourinho	0.99 Nicolás Lúcar	0.78 Mourinho	1.00 Song Yongtae	0.33
	Claudia Kim	Claudia Kim	1.00 Krystal Jung	0.92 Claudia Kim	1.00 Tae-im Lee	0.67
	Olivier Martinez	Olivier Martinez 0.92 Álvaro Medrán	0.79 Olivier	0.55 Yu Oh-seong	0.45
	Bae Suzy	Bae Suzy	0.99 Chae Soo-bin	0.91 Suzy	1.00 Yuu	0.33

Table 2 :

 2 Transfer Learning Attack, where one API assists in deceiving another API, which was originally unsuccessful

	Initial Correct Label Succ. Naver Adversarial Label	(Before) =⇒ (After):
			Fooling Amazon with Naver
	Park Tae-hwan	Song Chang-hwan	UNKR =⇒ Julio Cesar Ceodillo
	Hyun-jin Ryu	Kim Dong-ju	UNKR =⇒ Niarn
	Sooyoung	Solji	UNKR =⇒ Solji
	Kwon Yuri	Lee Eun-jeong	UNKR =⇒ Yoo Ara
	Im Yoon-ah	Im Seong-eon	UNKR =⇒ Lee Jin
	Taeyeon	Shihono Ryo	UNKR =⇒ Jin Se-yeon
	Kate Mara	Gemma Atkinson	UNKR =⇒ UNKR
	Kim Yuna	Choi Ja-hye	UNKR =⇒ UNKR
	Initial Correct Label Succ. Amazon Adversarial Label (Before) =⇒ (After):
			Fooling Naver with Amazon
	Sohee	Park Soo-jin	Sohee =⇒ Park Soo-jin
	Alicia Keys	Cindy Bruna	Alicia =⇒ Alicia
	7 Discussions, and Limitations

Acknowledgement

We would like to thank Adam Eisenstadt and anonymous reviewers for their valuable feedback. This research was supported by the MSIT(Ministry of Science and ICT), Korea, under the ICT Consilience Creative program(IITP-2017-R0346-16-1007) supervised by the IITP (Institute for Information & communications Technology Promotion), and by NRF funded by the MSIT(NRF-2017R1C1B5076474).