## 4 QuEry Attack
### Crossover  
We experimented both with single-point and two-point crossover, eventually settling on the latter as it performed better. The operator works by flattening both (two-dimensional image) parents, randomly picking two indices, then swapping the pixels between the chosen pixels. The EA then proceeds by evaluating the fitness of each individual, selecting parents, and performing crossover and mutation to generate the next generation. This latter is obtained by adding one elite individual from the current generation, with all other next-generation individuals derived through crossover and mutation. The process is repeated until a successful perturbation is found or until the termination condition is met. A major advantage of QuEry Attack is its amenability to parallelization--due to being evolutionary--in contrast to most other adversarial, iterative (non-evolutionary) attacks in this field. ```
1:\(x\leftarrow\) original image
2:\(y\leftarrow\) original label
3:\(\epsilon\leftarrow\) maximum \(l_{\infty}\) distance
4:\(p\leftarrow\) proportion of elements in \(x\) to be perturbed
5:\(N\leftarrow\) population size
6:\(G\leftarrow\) maximum number of generations
7:\(T\leftarrow\) tournament size
8:Output:\(\hat{x}\leftarrow\) adversarial image
9:Main loop
1:\(gen\gets 0\)
2:\(pop\leftarrow\) init()
3:while not termination_condition(\(pop,gen\)) do
4:for\(\hat{x}\in pop\)do
5: compute fitness of \(\hat{x}\) using Equation (4)
6:\(new\_pop\leftarrow\emptyset\)
7:\(\mathit{elite}\leftarrow\) elitism(\(pop\))
8: add elite to new_pop
9:for\(i\gets 1\) to \(\frac{p-1}{3}\)do
10:\(parent_{1}\leftarrow\) selection(\(pop\))
11:\(parent_{2}\leftarrow\) selection(\(pop\))
12:\(\mathit{offspring}_{1}\),\(\mathit{offspring}_{2}\leftarrow\) crossover(\(pop\))
13:\(mut_{1}\leftarrow\) square_mutation(\(\mathit{offspring}_{1}\))
14:\(mut_{2}\leftarrow\) square_mutation(\(\mathit{offspring}_{2}\))
15: add offspring\({}_{1}\),\(mut_{1}\),\(mut_{2}\) to new_pop
16:\(pop\gets new\_pop\)
17:\(gen\gets gen+1\)
18:
19:return best \(\hat{x}\) from \(pop\) # QuEry Attack's final output
20:functioninit()
21:\(pop\leftarrow\emptyset\)
22:for\(i\gets 1\) to \(N\)do
23:\(\hat{x}\leftarrow\) stripes_init(\(x\))
24: add \(\hat{x}\) to \(pop\)
25:return\(pop\)
26:functionelitism(\(pop\))
27:return best \(\hat{x}\) from \(pop\)
```  
**Algorithm 1**QuEry Attack  
```
28:functiontermination_condition(_pop_, _gen_)
39:if\(gen=G\)then
40:return true
41:for\(\hat{x}\in pop\)do
42:\(\hat{y}\leftarrow\) predicted label of \(\hat{x}\)
43:if\(\hat{y}\
eq y\)then
44:return true
45:return false
46:functionselection(_pop_)
47:\(\mathit{tournament}\leftarrow\) randomly and uniformly pick \(T\) individuals from _pop_
48:return best \(\hat{x}\) from \(\mathit{tournament}\)
49:functionstripes_init(\(\hat{x}\))
50:for\(i\gets 1\) to \(c\)do\(\#\) c is the image's number of channels
51:\(\mathit{stripe}\leftarrow\) create a vertical stripe of width 1, randomly positioned, with random values \(\in\{-\epsilon,\epsilon\}\)
52:\(\hat{x}\leftarrow\hat{x}+\mathit{stripe}\)
53:\(\hat{x}\leftarrow\Pi_{\epsilon}(\hat{x})\)\(\#\)\(\Pi_{\epsilon}\): clipping operator to ensure pixel values are within \(\epsilon\)-ball
54:return\(\hat{x}\)
55:functionsquare_mutation(\(\hat{x}\))
56:\(c\leftarrow\) number of channels
57:\(f\leftarrow\) number of features (\(h\times w\))\(\#\)\(h\): height, \(w\): width
58:\(k\leftarrow\lceil\sqrt{p\cdot f}\rceil\)
59:\(\delta\leftarrow\) array of ones of size \(k\times k\times c\).