Online Adversarial Attacks
Authors: Andjela Mladenovic
Joey Bose
Hugo Berard
William L. Hamilton
Simon Lacoste-Julien
Pascal Vincent
Gauthier Gidel
Venue: ICLR 2022 Poster (2022)
Keywords: Online Algorithms
Adversarial Attacks

Abstract: Adversarial attacks expose important vulnerabilities of deep learning models, yet little attention has been paid to settings where data arrives as a stream. In this paper, we formalize the online adversarial attack problem, emphasizing two key elements found in real-world use-cases: attackers must operate under partial knowledge of the target model, and the decisions made by the attacker are irrevocable since they operate on a transient data stream. We first rigorously analyze a deterministic variant of the online threat model by drawing parallels to the well-studied $k$-secretary problem in theoretical computer science and propose Virtual+, a simple yet practical online algorithm. Our main theoretical result shows Virtual+ yields provably the best competitive ratio over all single-threshold algorithms for $k<5$---extending the previous analysis of the $k$-secretary problem. We also introduce the \textit{stochastic $k$-secretary}---effectively reducing online blackbox transfer attacks to a $k$-secretary problem under noise---and prove theoretical bounds on the performance of Virtual+ adapted to this setting. Finally, we complement our theoretical results by conducting experiments on MNIST, CIFAR-10, and Imagenet classifiers, revealing the necessity of online algorithms in achieving near-optimal performance and also the rich interplay between attack strategies and online attack selection, enabling simple strategies like FGSM to outperform stronger adversaries.

Published as a conference paper at ICLR 2022
ONLINE ADVERSARIAL ATTACKS
Andjela Mladenovic* Mila, Université de Montréal
Avishek Joey Bose Mila, McGill University
Hugo Berard
Mila, Université de Montréal
William L. Hamilton Mila, McGill University
Simon Lacoste-Julien Mila, Université de Montréal
Pascal Vincent
Mila, Université de Montréal
Meta AI Research
Gauthier Gidel Mila, Université de Montréal
ABSTRACT
Adversarial attacks expose important vulnerabilities of deep learning models, yet little attention has been paid to settings where data arrives stream. In this paper, we formalize the online adversarial attack problem, emphasizing two key elements found in real-world use-cases: attackers must operate under partial knowledge of the target model, and the decisions made by the attacker are irrevocable since they operate on transient data stream. We first rigorously analyze deterministic variant of the online threat model by drawing parallels to the well-studied k- secretary problem in theoretical computer science and propose VIRTUAL+, a simple yet practical online algorithm. Our main theoretical result shows VIRTUAL+ yields provably the best competitive ratio over all single-threshold algorithms for k 5 5-extending the previous analysis of the k-secretary problem. We also introduce the stochastic t--secreary--fffctttvvee attacks to k-secretary problem under noise-and and prove theoretical bounds the performance of VIRTUAL+ adapted to this setting. Finally. we complement our theoretical results by conducting experiments MNIST, CIFAR-10, and Imagenet classifiers, revealing the necessity of online algorithms in achieving near-optimal performance and also the rich interplay between attack strategies and online attack selection, enabling simple strategies like FGSM to outperform stronger adversaries.
reducing online blackbox transfer
INTRODUCTION
In adversarial attacks, an attacker seeks to maliciously disrupt the performance of deep learning systems by adding small but often imperceptible noise to otherwise clean data (Szegedy al. 2014 Goodfellow et al., 2015). Critical to the study of adversarial attacks is specifying the threat model Akhtar & Mian 2018). which outlines the adversarial capabilities of an attacker and the level of information available in crafting attacks. Canonical examples include the whitebox threat model Madry et al. (017)), where the attacker has complete access, and the less permissive blackbox threat model where attacker only has partial information, like the ability to query the target model (Chen et al. 2017 Ilyas et al. 2019 Papernot et al.) 2016).
Previously studied threat models (c.g., whitebox and blackbox) implicitly assume static setting that permits full access to instances in a target dataset at all times (Tramèr et al.) 2018). However, such an assumption is unrealistic in many real-world systems. Countless real-world applications involve streaming data that arrive in an online fashion (e.g.. financial markets or real-time sensor networks). Understanding the feasibility of adversarial attacks in this online setting is an essential question.
As a motivating example, consider the case where the adversary launches a man-in-the-middle attack depieted in Fig. Here, data is streamed between two endpoints-i.e. from sensors an autonomous car to the actual control system. An adversary, in this example, would intercept the
* "Equal Contribution. Corresponding authors: I ficey.bose, bose, andjela mladenovic émi maila.. quebec 1 Work done while an intern at Meta Al Research
1 Canada CIFAR AT Chair

---

Published as a conference paper at ICLR 2022
sensor data, potentially perturb it, and then send it to the controller. Unlike classical adversarial attacks, such a scenario presents two key challenges that are representative of all online settings.
1. Transiency: At every time step, the attacker makes an irrevocable decision whether to attack. and if she fails, or opts not to attack, then that datapoint is no longer available for further attacks. remain anonymous from stateful defenses -is re- stricted to a small selection budget and must optimally balance passive exploration phase before selecting high-value items in the data stream (e.g. easiest to attack) to submit an attack on.
2. Online Attack Budget: The adversary-
To the best of our knowledge, the only existing approaches that craft adversarial examples on streaming data (Gong et al. 2019a Lin et al., 2017; Sun et al. 2020) require multiple passes through data stream and thus cannot be applied in a realistic online setting where an adver- sary forced into irrevocable decisions. Moreover, these approaches do not come with theoretical guarantees. Con- sequently, assessing the practicality of adversarial attacks- to better expose risks-in truly online setting is still an open problem, and the focus of this paper.
Adversonial Attack
Organnl
LiCHY Genter
Figure 1:
Mhddde Attack.
Main Contributions. We formalize the online threat model to study adversarial attacks streaming data. In our online threat model, the adversary must execute successful attacks within n streamed data points, where k < n. As a starting point for our analysis, study the deterministic online threat model in which the actual value of an input-i.e.. the likelihood of a successful attack is revealed along with the input. Our first insight elucidates that such threat model, modulo the attack strategy, equates to the k-secretary problem known in the field of optimal stopping theory Dynkin (1633; Kleinberg (2005), allowing for the application of established online algorithms for picking optimal data points to attack. We then propose a novel online algorithm VIRTUAL+ that is both practical, simple to implement for any pair (ks, n2), and requires no additional hyperparameters.
Besides, motivated by attacking blackbox target models, we also introduce a modified secretary problem dubbed the stochastic k-secretary problem, which assumes the values an attacker observes are stochastic estimates of the actual value. We prove theoretical bounds on the competitive ratio under mild feasibility assumptions-for VIRTUAL+in this setting. Guided by our theoretical results, we conduct suite of experiments on both toy and standard datasets and classifiers (i.e., MNIST, CIFAR- 10, and Imagenet). Our empirical investigations reveal two counter-ing counter-intuitive phenomena that are unique to the online blackbox transfer attack setting: 1.) In certain cases attacking robust models may in fact be easier than non-robust models based on the distribution of values observed by an online algorithm. 2.) Simple attackers like FGSM can seemingly achieve higher online attack transfer rates than stronger PGD-attackers when paired with an online algorithm, demonstrating the importance of carefully selecting which data points attack. We summarize our key contributions:
We formalize the online adversarial attack threat model as an online decision problem and rigorously connect it to generalization of the k-secretary problem.
We introduce and analyze VIRTUAL+, an extension of VIRTUAL for the k-secretary problem yielding significant practical improvement (60%).
We then provide, via novel techniques, a tractable formula for its competitive ratio, partially answering one of Albers & Ladewig (020)'s open questions (see footnote and achieving a new
state-of-the-art competitive ratio for 5.
We propose Alg. 2 that leverages (secretary) online algorithms to perform efficient online adversar- ial attacks. We compare different online algorithms including VIRTUAL+ on MNIST, CIFAR-10, and Imagenet in the challenging Non-Interactive BlackBox transfer (NoBox) setting.
2 BACKGROUND AND PRELIMINARIES
Classical Adversarial Attack Setup. We are interested in constructing adversarial examples against some fixed target classifier ft X + y which consumes input data points x E X' and labels them with class label y E V. The goal of an adversarial attack then to produce an adversarial example x' E X' such that fa(x') # y. and where the distance d(x, x²) < 7. Then, equipped with loss & used to evaluate ft, an attack is said to be optimal if (Carlini & Wagner| 2017 Madry et al. 2017).
a E argmaxx/ex (()(()))))) s.t. d(x, S 7-
2

---

Published as a conference paper at ICLR 2022
Note that the formulation above makes no assumptions about access and resource restrictions imposed upon the adversary. Indeed, if the parameters of ft are readily available, we arrive at the familiar whitebox setting, and problem in Eq. D is solved by following the gradient fe that maximizes f.
k-Secretary Problem. The secretary problem is a well-known problem in theoretical computer science Dynkin (1963); Ferguson et al. (1989). Suppose that we are tasked with hiring secretary from a randomly ordered set of n potential candidates to select the secretary with maximum value. The secretaries are interviewed sequentially and reveal their actual value on arrival. Thus, the decision to accept or reject a secretary must be made immediately, irrevocably, and without knowledge of future candidates. While there exist many generalizations of this problem, in this work, we consider one of the most canonical generalizations known as the k-secretary problem Kleinberg (2005). Here, instead of choosing the best secretary, we are tasked with choosing & candidates to maximize the expected sum of values. Typically, online algorithms that attempt to solve secretary problems are evaluated using the competitive ratio, which is the value of the objective achieved by an online algorithm compared to an optimal value of the objective that is achieved by an ideal "offline algorithm." i... an algorithm with access to the entire candidate set. Formally, an online algorithm A that selects a subset of items SA is said to be C-competitive to the optimal algorithm OPT which greedily selects subset of items S* while having full knowledge of all n items, if asymptotically in n
Ex (V())) 2 (C' + o(1))
where V is a set-value function that determines the sum utility of each algorithm's ''s selection, and the expectations are over permutations sampled from the symmetric group of elements, Sn, acting on the data. In $4 we shall further generalize the k-secretary problem to its stochastic variant where the online algorithm is no longer privy to the actual values but must instead choose under uncertainty.
3 ONLINE ADVERSARIAL ATTACKS
Motivated by our more realistic threat model, we now consider a novel adversarial attack setting where the data is longer static but arrives in online fashion.
3.1 ADVERSARIAL ATTACKS AS SECRETARY PROBLEMS
The defining feature of the online threat model-in addition to streaming data and the fact that we may not have access to the target model f- the online attack budget constraint. Choosing when to attack under a fixed budget in the online setting can be related to a secretary problem. We formalize this online adversarial attack problem in the boxed online threat model below.
In the online threat model we are given a data stream D = {(#1,y1),.. y/),..., (In, yn)} of n samples ordered by their time of arrival. In order to craft an attack against the target model ft, the adversary selects, using its online algorithm A, a subset S C DD of items to maximize:
V(SA)= = Σ ((fe(AT((z)).)) v) s.t. |AAl S k;
(x.D)SSA
where ATT(x: denotes an attack x crafted by fixed attack method ATT that might might not depend on ft. From now on we define x' = ATT(2,). Intuitively, the adversary chooses & instances that are the "easiest" to attack, i.c. samples with the highest value. Note that selecting an instance to attack does not guarantee a successful attack. Indeed, a successful attack vector may not exist if the perturbation budget 7 is too small. However, stating the adversarial goal as maximizing the value of SA leads to the measurable objective of calculating the ratio of successful attacks in S versus S*.
If the adversary knows the true value of datapoint then the online attack problem reduces to the original k-secretary. On the other hand, the adversary might not have access to St, and instead, the adversary's 's value function may be an estimate of the true value-e.a e.g. the loss of a surrogate classifier, and the adversary must make selection decisions in the face of uncertainty. The theory developed in this paper will tackle both the case where values i := f(f((x)) y1) for E {l,.... _n ;= [n]] are known ( 3.2). well the richer stochastic setting with only estimates of v; E [m]
Practicality of the Online Threat Model. It is tempting to consider whether in practice the adversary should forego the online attack budget and instead attack every instance. However, such strategy poses several critical problems when operating in real- world online attack scenarios. Chiefly, attacking any instance in D incurs non-trivial risk that the adversary is detected by defense mechanism.
3

---

Published as a conference paper at ICLR 2022
Indeed, when faced with stateful defense strategies (e.g. Chen et al. (0200) ) every additional attacked instance further increases the risk of being detected and rendering future attacks impotent. Moreover, attacking every instance may be infeasible computationaly for large or impractical based on other real-world constraints. Generally speaking, as conventional adversarial attacks operate by restricting the perturbation to a fraction of the maximum possible change (e.g., -attackk,,),, online attacks analogously restrict the time window to a fraction of possible instances to attack. Similarly, knowledge of n is also a factor that the adversary can easily control in practice. For example, in the autonomous control system example, the adversary can choose to be active for a short interval- e.g.. when the autonomous car is at a particular geospatial location and thus set the value for n.
Online Threat Model. The online threat model relies on the following key definitions:
The target model ft- The adversarial goal is to attack some target model ft X - V, through adversarial examples that respect chosen distance function, d, with tolerance 7/- The data stream D. The data stream D contains the n examples (Ii, ys) ordered by their time of arrival. At any timestep i, the adversary receives the corresponding item in 'D and must decide whether to execute an attack or forever forego the chance to attack this item.
Online attack budget k. The adversary is limited to a maximum of k attempts to craft attacks within the online setting, thus imposing that each attack is a unique item in D. value function V. Each item in the dataset is assigned value on arrival by the value function V X x y - TR,, which represents the utility of selecting the item to craft an attack. This can be the likelihood of a successful attack under ft (true value) or stochastic estimate of the incurred loss given by surrogate model Js Rs Jt-
The online threat model corresponds to the setting where the adversary seeks to craft adversarial attacks (i) against a target model ft F. (ii) by observing items in D that arrive online, (iii) and choosing k optimal items to attack by relying on (iv) an available value function V. The adversary's 's objective then to use its value function towards selecting items in that maximize the sum total value of selections V (Eq. 3
3.2 VIRTUAL+ FOR ADVERSARIAL SECRETARY PROBLEMS
Let us first consider the deterministic variant of the online threat model, where the true value is known on arrival. For example consider the value function V(r,, V1) = ((f( y;) v; i.e. the loss resulting from the adversary corrupting incoming data z; into ote Under fixed attack strategy, the selection of high-value items from D exactly the original k-secretary problem and thus the adversary may employ any A that solves the original k-secretary problem.
Well-known single preeshodd-bssed algorithms that solve the k-secretary problem include the VIR- TUAL, OPTIMISTIC Babaioff al. (2077) and the recent SINGLE-REF algorithm Albers & Ladewig 2020). In a nutshell, these online algorithm consists of two phases- a sampling phase followed by selection phase- and optimal stopping point t (threshold) that is used by the algorithm to transition between the phases. In the sampling phase, the algorithms passively observe all data points up pre-specified threshold L. Note that / itself is algorithm-specife and can be chosen by solving a separate optimization problem. Additionally, each algorithm also maintains a sorted reference list R containing the top-k elements. Each algorithm then executes the selection phase through comparisons of incoming items to those in R and possibly updating R itself in the process (see $D)
Indeed, the simple structure of both the VIRTUAL and OPTIMISTIC algorithms-e.g. having few hyperparameters and not requiring the algorithm to involve Linear Program's 's for varying values of n and k-in addition to being (1/e) competiiiee (optimal for 1) make them suitable candidates for solving Eq. 3 However, the competitive ratio of both algorithms in the small & regime- not has shown to be sub-optimal with SINGLE- -FF REF provably yielding larger competitive ratios at the cost of an additional hyperparameter selected via combinatorial optimization when - co.
We now present a novel online algorithm, VIRTUAL+, that retains the simple structure of VIRTUAL and OPTIMISTIC, with no extra hyperparameters, but leads to a new state-of-the-arr competitive ratio for k < 5. Our key insight is derived from re-examining the selection condition in the VIRTUAL algorithm and noticing that it is overly conservative and can be simplified. The VIRTUAL+ algorithm is presented in Algorithm 1, where the removed condition in VIRTUAL (L2-3) is in pink stinkttstikth Concretely, the condition that is used by VIRTUAL. but not by VIRTUAL+ updates R during the
4

---

Published as a conference paper at ICLR 2022
selection phase without actually picking the item part of SΛ. Essentially, this condition is theoretically convenient and leads to a simpler analysis by ensuring that the VIRTUAL algorithm never exceeds & selections in SA- VIRTUAL+ removes this conservative R update criteria in favor of a simple to implement condition, |Sall S line (in pink). Furthermore, the new selection rule also retains the simplicity of VIRTUAI. leading painless application online attack problems.
Algorithm 1 VIRTUAL and VIRTUAL+
Passive Observation Phase
Selection Phase
Inputs: t [k... lb.. R 0, SA =
Sampling phase: Observe the first data points and construct a sorted list H with the indices of the top & data points seen. The method sort ensures: ((R(1)) 2 ((R(2)) 2 V (-({))
11
Selection Rule
2
Selection phase: (/VIRT+ removes L2-3 and adds L4
1: for = t + n do
R
L
Update R
S
2:
2 and R then-
Discard
3:
-R=sort(RU-(j) (
4:
else-if 2 (( and SA & & then
Figure VIRTUAL+ observes ey (or estimates) and maintains R during the sampling phase. Items are then picked into S., after threshold
5:
R= == (i) (R[A)) (#/ Update R)
6:
SA=SAU {8}
Select element i)
Competitive ratio of VIRTUAL+ What appears to be minor modification in VIRTUAL+ compared VIRTUAL leads to a significantly more involved analysis but a larger competitive ratio. In Theorem 1, we derive the analytic expression that is tight lower bound for the competitive ratio of VIRTUAL+ for general-ki We see that VIRTUAL+ provably improves in competitive ratio for < over both VIRTUAL, OPTIMISTIC, and in particular the previous best single threshold algorithm, SINGLE-RES
Theorem 1. The competitive ratio of VIRTUAL+ for k 2 2 with threshold tx an can asymptoti- cally be lower bounded by the following concave optimization problem,
(-1)m=1
C 2 max f(a) = a* ac(0,1]
Σ m==
am In - 0:00 where am = 76-11 km))
m!!
Particularly, we get C2 2 0.427, C2 2 ..55, C2 2 .4769 outerroormngg Albers & Ladewig 2020
Connection to Prior Work. The full proof for Theorem I can be found in $B along with a simple but illustrative proof for k = 2 in ş Theorem T gives tractable way to compute the competitive ratio of VIRTUAL+ for any k. that improve the previous state-of-the-arr (Albers & Ladewig 2020) in terms of single threshold k-secretary algorithms for k < 5 and A: >> 100 However, it is also important to contextualize VIRTUAL+ against recent theoretical advances in this space. Most prominently, Buchbinder et al. (2014) proved that the k-sscretary problem can be solved optimally (in terms of competitive ratio) using linear programs (LPs), assuming a fixed length of n. But these optimal algorithms are typically not feasible in practice. Critically, they require individually tuning multiple thresholds by solving a separate LP with l(nk?) parameters for each length of the data stream n, and the number of constraints grows to infinity algorithms with k22 thresholds could be obtained using infinite LPs and derived an optimal algorithm for i = 2 Nevertheless they require a large number of parameters and the scalability of infinite LPs for l >> 2 remains uncertain. In this work, we focus on practical methods with a single threshold (i.c., with (11) parameters, e.g. Algorithm I) that do not require involved computations that grow with n.
+ ao. CCan al. (2014) showed that optimal
Open Questions for Single Threshold Secretary Algorithms. Albers & Ladewig (0200) proposed new non-asymptotic results on the k- k-secretary problem that outperform asymptotically optimal iigorithms-openeee a new range of open questions for the k-secretary problem. While this problem is considered solved when working with probabilistic algorithms with (nk²²) parameters (Buch) binder et al. 2014), finding optimal non-asymptotic single-threshold (0(1) parameters) algorithms
Albers & Ladewig (2020) only provide competitive ratios of SINGLE- REF for k < 100 and conclude that "a closed formula for the competitive ratio for any value of is one direction of future work". We partially answer this open question by expressing VIRTUAL+'S optimal threshold t the solution of uni-dimensional concave optimization problem. Table 3
we provide this threshold for a wide range of k 100.
At each timestep deterministic algorithm chooses candidate according to deterministic rule depending on some parameters (usually a threshold and potentially rank compare with). prohabilistic algorithm
5

---

Published as a conference paper at ICLR 2022
is still open question. As step towards answering this question, our work proposes practical algorithm that improves upon Albers & Ladewig (2020) for lt = 2..... . with an optimal threshold that can be computed easily it has a closed form.
4 STOCHASTIC SECRETARY PROBLEM
In practice, online adversaries are unlikely to have access to the target model ft. Instead, it is reasonable to assume that they have partial knowledge.
Following Papernot al. (2017); Bose et al. 2020) we focus on modeling that partial knowledge by equipping the adversary with surrogate model or representative classifier fs- Using fa as opposed to ft means that we can compute the value V, == ((f((xz),, ys) of an incoming data point. This value Vi acts as an estimate of the value of interest t; :- (x)),, Vi). The stochastic k-secretary problem then to pick, under the noise model induced by using [s. the optimal subset S.A of size l from D. Thus, with no further assumptions on fa it is unclear whether online algorithms, as defined in $3.2 are still serviceable under uncertainty.
Sources of randomness. Our method relies on the idea that we can use the surrogate model fs to estimate the value of some adversarial examples on the target model ft. We justify here how partial knowledge on ft could provide us estimate of e₁. For example, we may know the general architecture and training procedure of ft. but there will be inherent randomness in the optimization (e.g., due initialization or data sampling), making it impossible to perfectly replicate ft-
Moreover, it has been observed that, in practice, adversarial examples transfer across models (Pa pernot et al. 2016: Tramer et al. (017). In that context, it is reasonable assume that the random variable V. ((f((1)) 96) is likely to be close to := {(f(2z)) y:). We formalize this idea in
Assumption
4.1 STOCHASTIC SECRETARY ALGORITTMS
In the stochastic k-secretary problem, we assume access random variables V; and that it fixed for i = 1...., n and the goal is to maximize a notion of stochastic competitive ratio. This notion is similar to the standard competitive ratio defined in Eq. 2 with minor difference that in the stochastic case, the algorithm does not have access to the values o but to V; that is an estimate of u; An algorithm is said to be Cg-competitive in the stochastic setting asymptotically in n,
S. [V(Sa)] (C. + +(1))
Here the expectation is taken over Sn (uniformly random permutations of the datastream D of size n) and over the randomness of V/, i = =1,,...... I,..., n.. SA and 5* are the set of items chosen by the stochastic online and offline algorithms respectively (note that while the online algorithm has access to V., the offline algorithm picks the best 22) and V is a set-value function as defined previously.
Analysis of algorithms. In the stochastic setting, all online algorithms observe V that is estimate of the actual value v. Since the goal of the algorithm is to select the k-largest values by only observing random variables (V:) it is requisite make feasibility assumption on the relationship between values e; and V, Let us denote topk { v. as the set of top-k values among (v:).
Assumption (Feasibilityy. By > 0 such that P(V; E topx 0 E tops (u:)] 2 7, Vn oF]
Assumption 1 is feasibility assumption as if the ordering of (V,) does not correspond at all with the ordering of (v:) then there is hope any algorithm- oonlin or an offline oracle-would perform better than random when picking & largest i2 by only observing (Vt). In the context of adversarial attacks, such an assumption is quite reasonable as in practice there is strong empirical evidence between the transfer of adversarial examples between surrogate and target models (see IC. for the empirical caliber of assumption D}. We can bound the competitive ratio in the stochastic setting. Let us assume that VIRTUAL+ observes independent random variables V following Assumption 7 Its stochastic competitive ratio C. can be bounded as follows,
Theorem 2.
(5) choose to accept a candidate according to 4E.j. the probability of accepting the candidate in i-th position the 5thh accepted candidate given that the candidate is the l-th best candidate among the first candidates (i E [m], j. [K)) See (Buchhinder et al. (2014) for more details on prohabilistic secretary algorithms. NNote that, for the sake of simplicity, the constant y is assumed to he independent of n but similar non-asymptotic analysis could be performed by considering a non-asymptotic definition of the competitive ratio.
C2 C2C 2-

---

Published as a conference paper at ICLR 2022
can The proof of Thm. 2 can be found in c Such theoretical result is quite interesting as the stochastic setting initially appears significantly more challenging due to the non-zero probability that the observed ordering of historical values. V, not being faithful to the true ranking based 2;--
4.2 RESULTS ON SYNTHETIC DATA
We assess the performance of classical single threshold online algorithms and VIRTUAL+ in solving the stochastic k-secretary problem synthetic dataset of size 100 with & E [1, 10). The value of a data point is its index in D prior to applying any permutation π ~ S, plus noise (0,00%) We compute and plot the competitive ratio over 10k unique permutations of each algorithm in Figure
0.60
Algorithm 2 Online Adversarial Attack
Vinual Opteiete Sigle-Rd Rd
Raio
0.55
Inputs: Permuted Datastream: Da. Online Algo-
0.50
Vinall
rithm: A, Surrogate classifier: far Target classifier: ft. Attack method: ATT, Loss: f, Budget: k, Online Fool
0.45
rate: F-A = 0.
0.40
for (# vi) in Dz do
0.35
2:
d + ATT(Z;)
(// Compute the attack)
3:
V. +- (z)),
(// Estimate n;
4:
if A(V Vi,k) == TRUE then
Figure 3: Estimation of the competitive ratio of online algorithms in the stochastic k-secretary problem with o² 10.
5:
FA &- F 1(fee//
(/l Submit xf)
return: FAA (IAA always submits & attacks]
As illustrated for i- 1 all algorithms achieve the optimal (1/e)ddetrte determiiiiiiii competitive ratio in the stochastic setting. Note that the noise level, o², appears to have a small impact on the performance of the algorithms ($E.2). This substantiates our result in Thm. 2 indicating that Cn-commetitive algorithms only degrade by small factor in the stochastic setting. For k < 5, VIRTUAL+ achieves the best competitive rapir-empiyycally validating Thm -fter which SINGLE-REF superior.
EXPERIMENTS
We investigate the feasibility of online adversarial attacks by considering an online version of the challenging NoBox setting (Bose et al. 2020) in which the adversary must generate attacks without any access, including queries, to the target model fr- Instead, the adversary only has access to a surrogate fa which is similar to ft- In particular, we pick at random ft and f. from an ensemble of pre-trained models from various canonical architectures. We perform experiments on the MNIST
LeCun & Cortes (2010) and CIFAR-10 10 Krizhevsky (2009) datasets where we simulate D by generating 1000 permutations of the test set and feeding each instantiation to Alg. 2 In practice, (x.), 34) of each data point in D by attacking f. using their fixed attack strategy (where is the cross-entropy). but the decision to submit the attack to fi is done using an online algorithm (see Alg. 2 As representative attack strategies, the well-known FGSM attack (Goodfellow et al. (0155) and a universal whitebox attack in PGD (Madry et al., 2017). We are most interested in evaluating the online fool rate, which is simply the ratio of successfully executed attacks against fi out of a possible of k attacks selected by A. The architectures used for f.. ft. and additional metrics (e.g. competitive ratios) can be found in $E
online adversaries compute the value V,
use
Baselines. We rely on two main baselines, first we use NAIVE baseline-a a lower bound-where the data points are picked uniformly at random, and an upper bound with the OPT baseline where attacks, while crafted using Ss. are submitted by using the true value n and thus utilizing ft-
Q1: Utility of using an online algorithm. We first investigate the utility of using an online algorithm, A. in selecting data points to attack in comparison to the NAIVE baseline. For a given permutation π and an attack method (FGSM or PGD), we compute the online fool rate the NAIVE baseline and an A as /NAVVE FA respectively. In Fig. 4 we uniformly sample 20 permutations of and plot a scatter graph of points with coordinates (F FFA)) for different A's, attacks with k 1000, and datasets. The line y corresponds to the NAIVE baseline performance -ie coordinates (F NAIVE) and each point above that line corresponds to an A that outperforms
Sn, E [n],
*Code can be found https: //gp::////ttbb// com httm///faeoooorreeeeeee rch/On1 wtw.c////oonnnccccccc..c. neAttacks

---

Published as a conference paper at ICLR 2022
CIFAR-10
15.0
VarrOAL
12.5
Gemmene
UNLINE 1o0 Mare
VIRETAL-
10.0
SINGLE- Ray
7.5
FCSM Attack
NAIVa Spaden
3.0
0.5
1.0
1.5
9.5
3.0
3.5
40
15.0
97.5
30.0
32.
35.0
37.5
10.0
42.5
45.0
NaIv Bazaline Foot Rato
NAIV Bassiinc Fool Rasz
Figure 4: Plot of online fool rates for = 1000 against PGD-robust models using different online algorithms A, attacks, datasets, and 20 different permutations. For a given z-coordinate, a higher y-coordinate is better.
the baseline on a given n. As observed, all A's significantly outperform the NAIVE baseline with an average aggregate improvement of 7.5% and 34.15 1% on MNIST and CIFAR-10.
MNIST (Online fool rate in %6)
CIFAR-10 (Online fool rate %)
Imagenet (Online fool rate in %))
Algorithm
k
102
10
102
10
10
10"
10"
NAIVE
64.1
47.8
45.7
60.7
59.2
59.2
66.0
66.3
65.0
OPT
87.9
84.7
83.6
86.6
87.3
86.5
98.7
95.3
96.2
79.0
80.4
79.9
FGSM
VIRTUAL
78.6
79.1
77.4
76.1
77.1
75.4
85.3
84.9
84.3
SINGLE-ROP
85.1
83.0"
72.3
66.0
94.0"
92.4"
72.5
VIRTUAL+
80.4
82.5
82.9
82.9
86.3
85.2
96.0"
95.0"
95.8
69.7
67.2
67.9
72.5
72.5
OPT
73.6
49.8
49.6
83.7
80.6
79.9
82,5
80.2
76.8
OPTIMISTIC
66.2
48.2
45.1
79.1
76.6
76.0
87.5"
78.0'
74.5"
VIRTUAL
63.4
46.2
46.8
78.3
77.5
76.9
80.0
74.0"
75.6"
SINGLE-REF
71.5
49.7"
42.9
80.2"
79.6"
74.5
77.5"
79.5"
75.2"
VIRTUAL+ 68.2
49.3"
49.7
81.2"
$0.1
79.5
77.5"
79.0"
76.4"
Table Online fool rate of various online algorithms on non-robust models. For given attack and value of at least 97%, at least 95%, at least 90%, less than 90% of the optimal performance. indicates when there is several best methods with overlapping error bars. Detailed results with error bars can be found in E
Q2: Online Attacks on Non-Robust Classifiers. We now conduct experiments on non-robust MNIST, CIFAR-10, and Imagenet classifiers. We report the average performance of all online algorithms, and the optimal offline algorithm OPT in Tab. [5] For MNIST, we find that the two best online algorithms are SINGLF--REF and our proposed VIRTUAL+ which approach the upper bound provided by OPT. For experiments with SINGLE--RE RFF is slightly superior while for k 1000 VIRTUAL+ is the best method with an average relative improvement of 15.3%. This is unsurprising as VIRTUAL+ does not have any additional hyperparameters unlike SINGLE-RE REF which appears more sensitive to the choice of optimal thresholds and reference ranks, both of which are unknown beyond & = 100 and non non-trivia triviil to find in closed form (see for details). On CIFAR-10, 10, observe that VIRTUAL+ is the best approach regardless of attack strategy and the online attack budget k. Finally, for ImageNet we find that all online the NAIVE baseline and approach saturation to the optimal offline algorithm, and as result, all algorithms are equally performant-i.c. within error bars (see $E.1 for more details). A notable observation is that even conventional whitebox adversaries like FGSM and PGD become strong blackbox transfer attack strategies when using an appropriate A.
please see $F.5 For k:
and = 100,
algorithms improve
Q3: Online Attacks on Robust Classifiers. We now test the feasibility of online attacks against classifiers robustified using adversarial training by adapting the public Madry Challenge (Madry al.) 2017) the online setting. We report the average performance of each A in Table ?? We observe that VIRTUAL+ is the best online algorithms, outperforming VIRTUAL and OPTIMISTIC, in all settings except for à 10 on MNIST where SINGLF--REF slightly better.
Q4: Differences between the online and offline setting. The online threat model presents several interesting phenomena that we now highlight. First, we observe that a stronger attack (e.g. PGD)-in comparison to FGSM-in the offline setting doesn't necessarily translate to an equivalently stronger attack in the online setting. Such an observation was first made in the conventional offline transfer setting by Madry al. (2017), but argue the online setting further exacerbates this phenomenon. We explain this phenomenon in Fig. 5a & by plotting the ratio of unsuccessful attacks to total attacks function of loss values for PGD and FGSM. We that for the PGD attack numerous
8

---

Published as a conference paper at ICLR 2022
MNIST (Online fool rate in %6)
CIFAR-I0 (Online fool rate in %)
Algorithm
h: == 10
A = 100 & = 1000
== 10
k: = 100
== 1000
NAIVE
2.1 + 4.5
2.1 1.4
2.1 + 0.4
31.9 + 14.2
32.6 + 4.7
32.5 + 1.5
OPT
80.0 + 0.0
55.0 + 0.0
18.9 + 0.0
100.0 + 0.0
100.0 + 0.0
97.2 + 0.0
FGSM
OPTIMISTIC
49.7
25.7 25.7
9.7
72,4 0.5
64.6 - 0.1
61.9 0.0
VIRTUAL
49.8 1
27.8
8.1
75.1 + 0.5
74.3 = 0.1
68.9 + 0.0
SINGLE- REF
6.70
4.2
1..2
84.3 0.6
90.9 0.3
48.6 =
VIRTUAL+
68.2 4
42.2 +
12.7 0.0
91.5 0.4
96.5 0.1
91.7
NAIVE
1.1
1.9 1.4
1.9 0.4
39.1 14.2
38.9 4.4
38.7
OPT
58.9 - 0.4
39. 0.1
16.1 0.0
100.0 + 0.0
100.0 + 0.0
98.0 = 0.0
PGD
OPTIMISTIC
34.9 14.9:00.5
19.2
8.2
75.4 1.9
68.5 + 0.4
66.0 + 0.1
VIRTUAL
+5.400.5
0.1
7.2
78.1 + 1.7
77.3 - 0.5
72.8 + 0.1
SINGLE-RED REF
44.1
33.9 0.2
8.3
86.2 + 2.2
91.9 0.9
53.2 + 0.3
VIRTUAL+
48.3 0.5
32.8
11.1
92.2
1.3
97.1 = 0.4
94.2 = 0.1
Table 2: Online fool rate of various online algorithms robust models. For given attack and value of k: least 90%, least 80%, least 70%." less than 70% of the optimal performance.
unsuccessful attacks can be found even for high surrogate loss values and as result, can lead A further astray by picking unsuccessful data points-which may be top-k in surrogate loss values-to conduct transfer attack. A similar ionuttr-intuitive observation online fool rate on robust and non-robust classifiers. While is natural to expect the online fool rate to be lower robust models we empirically observe the opposite in Tab. and
be made when comparing the
?? this phenomenon we plot the ratio of unsuccessful attacks to total attacks as a function fa 's loss in Fig. and observe non-robust models provide a non-vanishing ratio of unsuccessful attacks for large values of V; making it harder for A to pick successful attacks purely based on loss (see also I
To understand
Nan-Balore Modil
PGD AFLACK
PGD ATTACK
016
ATTACK
0111
FOSM ATTMSS
2
10b
(a) Distribution of fi's loss values.
(b) Ratio of unsuccessful attacks.
(c) Ratio of unsuccessful attacks.
For every example in MNIST we compute an attack using fs and submit it to fc- Left: The distribution of the normalized loss values of fe for all attacks where a higher loss is stronger attack. Middle: The percentage of unsuccessful attacks function of f- normalized loss values. Right: smoothed ratio of unsuccessful attacks to total attacks a function of the fa normalized loss values.
Figure 5:
CONCLUSION
In this paper, formulate the online adversarial attack problem, a novel threat model to study adversarial attacks on streaming data. We propose VIRTUAL+, a simple yet practical online algorithm that enables attackers select easy fool data points while being theoretically the best single threshold algorithm for & < 5. We further introduce the stochastic k-secretary problem and prove fundamental results the competitive ratio of any online algorithm operating this new setting. Our work sheds light on the tight coupling between optimally selecting data points using an online algorithm and the final attack success rate, enabling weak adversaries to perform on par with stronger ones at no additional cost. Investigating, the optimal threshold values for larger values of k along with competitive analysis for the general setting is natural direction for future work.
ETHICS STATEMENT
We introduce the online threat model which aims to capture new domain for adversarial attack research against streaming data. Such a threat model exposes several new security and privacy risks. For example, using online algorithms, adversaries may now tailor their attack strategy attacking small subset of streamed data but still cause significant damage to downstream models e.g. the control system of an autonomous On the other hand our research also highlights the need and importance

---

Published as a conference paper at ICLR 2022
of stateful defence strategies that capable of mitigating such online attacks. On the theoretical side the development and analysis of VIRTUAL+ has many potential applications outside of adversarial consider
attacks broadly categorized as resource allocation problems. As concrete example advertising auctions which provide the main source of monetization for a variety internet services including search engines, blogs, and social networking sites. Such scenario is amenable to being modelled as secretary problem as an advertiser may be able to estimate accurately the bid required win a particular auction, but may not privy the trade off for future auctions.
REPRODUCIBILITY STATEMENT
Throughout the paper tried to provide many details possible in order for the results of the paper to be reproducible. and explain how to combine any attacker (e.g. PGD) with online algorithm to form an online adversarial attack in Alg. 2 We provide a general description of the experimental setup in $ further details with the specific architecture of the models and hyper-parameters used are provided in |E.3 We also provided confidence intervals with our experiments every time it was possible to do so. Finally the code used produce the experimental results is provided with the supplementary materials and will be made public after the review process.
particular, we provide a detailed description of VIRTUAL+in Alg. [
ACKNOWLEDGEMENTS
The authors would like to acknowledge Manuella Girotti, Pouya Bashivan, Reyhane Askari Hemmat, Tiago Salvador and Noah Marshall for reviewing early drafts of this work.
Funding. This work is partially supported by the Canada CIFAR AI Chair Program (held at Mila), Joey Bose was also supported by an IVADO PhD fellowship. Simon Lacoste-Julien and Pascal Vincent are CIFAR Associate Fellows in the Learning in Machines & Brains program. Finally, we thank Facebook for access computational resources.
CONTRIBUTIONS
Andjela Mladenovic and Gauthier Gidel formulated the online adversarial attacks setting by drawing parallels to the k-secretary problem, with Andjela Mladenovic leading the theoretical investigation and theoretical results including the competitive analysis for VIRTUAL+ for the general-k setting, Avishek Joey Bose conceived the idea of online attacks, drove the writing of the paper and helped Andjela Mladenovic with experimental results on synthetic data. Hugo Berard was the chief architect behind all experimental results MNIST and CIFAR-10. William I.. Hamilton, Simon Lacoste-Julics and Pascal Vincent provided feedhack and guidance over this research while Gauthier Gidel supervised the core technical execution of the theory.
10

---

Published as a conference paper at ICLR 2022
REFERENCES
Naveed Akhtar and Ajmal Mian. Threat of adversarial attacks on deep learning in computer vision: A survey. IEEE Access, 2018.
Susanne Albers and Leon Ladewig. New results for the k-secretary problem. arXiv preprint arXiv:2012.00488,, 2020.
Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. arXiv preprint 2xXiv:2006.01026 2020.
Pablo D Azar, Robert Kleinberg, and $ Matthew Weinberg. Prophet inequalities with limited infor- mation. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 2014.
Yossi Azar, Ashish Chiplunkar, and Haim Kaplan. Prophet secretary: Surpassing the 1-1/e barrier. In Proceedings of the 2018 ACM Conference Economics and Computation, 2018.
Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. A knapsack secretary problem with applications. In Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Springer, 2007.
Avishek Joey Bose, Gauthier Gidel, Hugo Berard, Andre Cianflone, Pascal Vincent, Simon Lacoste- Julien, and William L Hamilton. Adversarial example games. Thirty-fourth Conference on Neural Information Processing Systemx, 2020.
Domagoj Bradac, Anupam Gupta, Sahil Singla, and Goran Zuzic. Robust Algorithms for the Secretary Problem. In /TCS, 2020.
Niv Buchbinder, Kamal Jain, and Mohit Singh. Secretary problems via linear programming, Mathe- matics of Operations Research, 39(1):190-200 2014.
Nicholas Carlini and David Wagner. Magnet and efficient defenses against adversarial attacks are not robust to adversarial examples. arXiv preprint urXiv: 1t//11111000 1.08478, 2017.
Anirban Chakraborty, Manaar Alam, Vishal Dey, Anupam Chattopadhyay, and Debdeep Mukhopad- hyay. Adversarial attacks and defences: A survey, arXiv preprint arXiv: 1810.00069, 2018
TH Hubert Chan, Fei Chen, and Shaofeng H-C Jiang. Revealing optimal thresholds for generalized secretary problem via continuous Ip: impacts on online k-item auction and bipartite k-matching with random arrival order. In Proceedings of the Twenty-Sixth Annual ACM-SIAN Symposium on Discrete Algorithms, 2014.
Pin- Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the tenth ACM Workshop on Artificial Intelligence and Security. ACM, 2017.
Steven Chen, Nicholas Carlini, and David Wagner. Stateful detection of black-box adversarial attacks. In Proceedings of the 1st ACM Workshop on Security and Privacy on Artificial Intelligence, pp. 30-39, 2020.
Gavin Weiguang Ding, Yash Sharma, Kry Yik Chau Lui, and Ruitong Huang. MMA training: Direct input space margin maximization through adversarial training. In International Conference on Learning Representations, 2020.
Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. arXiv preprint arXiv:2011.06726, 2020.
Evgenii Borisovich Dynkin. The optimum choice of the instant for stopping markov process. Soviet Mathematics, 1963.
Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Morteza Monemizadeh. Prophet secretary. SIAM Journal on Discrete Mathematics, 2017.
Thomas S Ferguson et al. Who solved the secretary problem? Statistical science, 1989.
11

---

Published as a conference paper at ICLR 2022
Martin Gardner. Mathematical games. Scientific American, 1960.
Yuan Gong, Boyang Li, Christian Poellabauer, and Yiyu Shi. Real-time adversarial attacks. Pro- ceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence IJCAI-19, 2019a.
Yuan Gong, Jian Yang, Jacob Huber, Mitchell MacKnight, and Christian Poellabauer. ReMASC: Realistic Replay Attack Corpus for Voice Controlled Systems. In Proc. Interspeech 2019, 2019b.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. Third International Conference of Learning Representations (ICLR), 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, 2016.
Gao Huang. Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4705 2017.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. Thirty-fifth International Conference on Machine Learning (ICML), 2018
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Query-efficient black-box adversarial examples. In ICLR, 2019.
Linxi Jiang, Xingjun Ma, Shaoxiang Chen, James Bailey, and Yu-Gang Jiang. Black-box adversarial attacks video recognition models. In Proceedings of the twenty-seventh ACM International Conference on Multimedia, 2019.
Haim Kaplan, David Naori, and Danny Raz. Competitive analysis with a sample and the secretary problem. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium Discrete Algorithms. SIAM, 2020.
Robert D Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In SODA, 2005.
Alex Krizhevsky. Learning multiple layers of features from tiny images. In Tech Report, UofT, 2009.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL attp::/yan.
lecun. htam/exxb/mma /misst/
Yen-Chen Lin, Zhang- Wei Hong, Yuan-Hong Liao, Meng-Li Shib, Ming- Yu Liu, and Min Sun. Tactics of adversarial attack deep reinforcement learning agents. In Proceedings of the Twenty- Sixth International Joint Conference on Artificial Intelligence, 1JCAI-17, 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. Sixth International Conference on Learning Representations (ICLR), 2017.
Nicolas Papernot, Patrick McDaniel, and Ian Goodfellow. Transferability in machine learning: from phenomena to black-box attacks using adversarial samples. arXiv preprint 16X.v:1605.07277. 2016.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the ACM on Asia Conference on Computer and Communications Security. ACM, 2017.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. Third International Conference on Learning Representations (ICLR), 2015.
Jianwen Sun, Tianwei Zhang, Xiaofei Xie, Lei Ma, Yan Zheng, Kangjie Chen, and Yang Liu. Stealthy and efficient adversarial attacks against deep reinforcement learning. The Thirty-Four Fourth AAAI Conference Artificial Intelligence (AAAI-20), 2020.
12

---

Published as a conference paper at ICLR 2022
Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfellow, and Rob Fergus. Intriguing properties of neural networks. Second International Conference on Learning Representations (ICLR), 2014.
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818-2822 2016.
Florian Tramèr, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick McDaniel. The space of transferable adversarial examples. arXiv preprint arXiv: (rXXvv/704.03455 2017.
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick Mc- Daniel. Ensemble adversarial training: Attacks and defenses. Sixth International Conference on Learning Representations (ICLR), 2018.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In British Machine Vision Conference 2016. British Machine Vision Association, 2016.
13


Reviews:
[{"review_id": "m3HSDrvwtP7", "reviewer": "Reviewer_82UN", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. This paper is technically solid and detailed. It is in well structure and easy to follow. The whole story is complete with the theory supported.\n2. The experiments are also good. Some findings in the paper do motivate us further reflecting on the difference of online attack and offline attack. This may provide a new perspective why deep learning model is so fragile.\n\nHowever, i still have some concerns w.r.t. experiments. \n1. As mentioned in the introduction, several works also study the online attack problem, more detailed description about the difference between their cases and this paper should be discussed, maybe in the related works? To be honest, i did not get the difference well.\n\n2. Even previous works study a slightly different setting. Could their methods be adapted as more strong baselines for comparison?\n\n3. How are the FGSM and PGD implemented in this paper？do we perform FGSM or PGD directly on the selected samples?\n\n4. As discussed in Section 4, a surrogate function is used when the true model is unaccessible. How the surrogate function is selected in the experiment? have you tried different surrogate functions?\n\n5. In the experiments,  counter-intuitive results are obtained. Have you tried different defence strategies for comparison? \n\n6. I notice that the experiments are conducted on MNIST and CIFAR only, is the proposed method can be efficiently implemented on large-scaled dataset?", "summary_of_the_paper": "This paper focuses on the online attack problem, where two elements are emphasized that attackers must operate under partial knowledge\nof the target model, and the decisions made by the attacker are irrevocable. To solve this problem, they propose VIRTUAL+ and give theoretical guarantee on competitive ratio. The findings in the related experiments also validate the necessity and efficacy of proposed method in online setting.\n", "summary_of_the_review": "This paper is solid and well written, however, there are some points i am confused. I thus give the score of 6.\n\n====================================update========================================\n\nFirst of all, I appreciate the authors' hard work in the rebuttal. Most of my concerns have been addressed in the discussion. I would like to raise the score to accept.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "dxA3m9ZqjgL", "reviewer": "Reviewer_XV1X", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The new algorithm VIRTUAL+ is interesting, but I vote for weak reject given its motivation and novelty towards adversarial learning. The explanations towards some observations in the experiments do not convince me either.\n\n(1) It is not clear why this paper considers the online adversarial attack. The main contributions are built upon the proposed new algorithm towards k-secretary problem, and the online adversarial attack is only one of the possible applications of this k-secretary problem. Different from most literature in adversarial training, it does not deepen the understanding of attack method or robust features. The current title and abstract are somewhat not accurate to describe the main interest of this paper. Please consider polish the writing.\n\n(2) Given the problem setup of \"selecting k samples to attack in a stream of data to mislead a fixed neural network to make wrong predictions\", the proposed problem forumlation in this paper is a natural solution. However, in reality, e.g. filtering system to detect spam email, the classifier is updated along the time. It is more interesting to consider a changing f_t rather than a fixed target f_t. Similarly, we can also train f_s through receiving the streaming data.\n\n(3) In the experiment, the authors observe a much-better-than-PGD performance for FSGM. In theory a PGD attack is always not weaker than FSGM. I checked the code and found that the PGD attack setup is (nb_iter=40,eps_iter=0.01) for eps=0.3 in MNIST. This setup is used in other literature, but could you please try to increase nb_iter to see its performance? It is possible that the attack is hard to train for some data, so a larger nb_iter may help diagnose this. The current explanation for this observation does not convince me. \n\n(4) In the experiment, the authors observe that in CIFAR-10, the robust model is more vulnerable to online attack compared to the non-robust model. To explain this, the authors mention that in Fig. 5c the non-robust models have a heavier tail making it harder for A to pick successful attacks. I do not understand this explanation. If the non-robust models have a heavier tail, does this mean that more data are easy to attack in the non-robust model? Or do you mean that the loss does not reflect the exact decision? Since this observation is counter-intuitive, please have some detailed and convincing explanation for it.\n\n\nMinor things:\n\n(5) The paper provides motivation and intuition of the proposed VIRTUAL+ algorithm. It would be great if discussions can be provided for the technical difficulties of Theorem 1.\n \n(6) The title \"Non-Robust Model\" in Figure 5(c) is misleading. Please remove it. Also the caption of Figure 5 says \"MNIST (or CIFAR)\", please make it clear which dataset the subfigures are using.\n", "summary_of_the_paper": "This paper formulates an online threat model and use the VIRTUAL+ algorithm their proposed to solve this k-secretary problem. The proposed method is supported by theoretical justifications, and the numerical experiment shows a better performance of VITRUAL+ over other existing algorithms.", "summary_of_the_review": "The new algorithm VIRTUAL+ is interesting, but please make it clear about the motivation and novelty of this work towards adversarial learning. Please also provide convincing explanations towards some observations in the experiments.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KGfWEgBfyAH", "reviewer": "Reviewer_VskD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- This paper proposed a new threat model called online adversarial attacks, which could open the door for a new research direction.\n- Based on existing algorithms, the authors proposed Virtual+. This algorithm could also be used for tackling other online problems.\n- The experiments show the proposed algorithm achieves better results than other baseline method.\n- The theoretical analysis is thorough and technically sound. \n\nWeaknesses:\n- I feel hard to understand the motivation of studying online adversarial attack. I agree it is a new problem, but I am not sure about what kind of attacker need to launch online attack on what type of dataset? Please give a concrete example.\n- The proposed method seems disconnected with the adversarial attack scenario. Which part of the Virtual+ algorithm is tailored for adversarial attacks? If the Virtual+ is a generalized algorithm which can be deployed on any k-secretary problem, why not position this paper as an algorithm paper instead of concentrating on adversarial attacks?\n- The experiment only evaluated on simple image datasets like MNIST and CIFAR. This does not support the author's motivation that \"Countless real-world applications involve streaming data that arrive in an online fashion (e.g., financial markets or real-time sensor networks).\" Even for the image domain, MNIST and CIFAR-10 are considered to be insufficient.", "summary_of_the_paper": "This paper proposed a new threat model for adversarial attacks called online adversarial attacks. Unlike traditional threat models, the online attack model assumes the data feed as stream and the decision made by the attacker are irrevocable. Towards this, the author made a connection between the online adversarial attack and the k-secretary problem, and proposed a new algorithm Virtual+. The experiments show that Virtual+ achieves better online fool rate than other baseline methods.", "summary_of_the_review": "I am on the fence about this paper. On the one hand, the authors proposed a new threat model and provided with theoretically-grounded algorithm for tackling that problem. On the other hand, the motivation of the problem is not clear to me and the evaluation is also insufficient. I'd like to see other reviewer's opinion and the author's comment before making my final recommendation.\n\nPost rebuttal:\nI appreciate the author's effort on addressing my concerns and answering my questions. Most of my questions has been addressed. Thus, I'd like to raise my score to 6. However, I am still not fully convinced about the significance and motivation of studying online adversarial attack. My final recommendation is perhaps we could accept this paper and see how it can inspire future research on this direction.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6-ajaie3CV", "reviewer": "Reviewer_4rG9", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Instead of studying how to craft an adversarial example x', this work supposes that the attacking strategy of finding x' is given and focuses on finding the right subset of data points to attack in an online fashion. \n\nOne question the audience may have is under what real-world circumstances, the attacks can be carried out in such an online fashion. \n\n* The authors mentioned networked control systems. I agree that control systems operate in real-time. But it does not mean that the attack model here can be applied to attacks on control systems, because in control systems current state depends on previous states (so do the data points, which means data points are not independently ordered). Also, in control systems, usually, the goal is not to optimize certain loss functions but to ensure stability. \n\n* Can the authors provide more real-world examples/situations where the attack model studied here can be applied? If possible, please consider conducting experiments on these examples.\n\n* For MNIST and CIFAR-10, data points usually arrive in batches instead of single data points. Can the authors also justify that in the manuscript? How would the authors deal with data batches? Can the current model extend seamlessly to the \"batched data\" situation?\n\nAnother major concern is the performance of the VIRTUAL+ algorithm. The theoretical results show that the algorithm produces the best competitive ratio only when k<5. In real applications, the number of data points involved can reach millions if not billions. The number of data points being attacked can easily go beyond 5. Does it mean that the VIRTUAL+ algorithm can only perform relatively better under some extreme cases and the application of the algorithm is limited?\n\nOther minor concerns include:\n* In C.1, it is not clear how table 4 is produced. In particular, it is not clear how the surrogate model is generated.\n* please mention several ways of counter-attack in the conclusion section, e.g., arranging data points in a way such that the effect of  VIRTUAL+ attacks is mitigated.\n* Figure 4 appears before figure 3", "summary_of_the_paper": " This paper studies the online adversarial attacks on deep learning (DL) models. Unlike other works that focused on adversarial attacks on  DL models, this work studies, on half of the attacker, how to choose a subset of data points to attack in an online fashion. Since the data arrives as a stream, the attacker has to make an irrevocable decision on whether to attack when each data point comes. This setting aligns with the situation given in the well-studied k-secretary problem. Built on top of a famous algorithm in the k secretary problem called VIRTUAL, an algorithm called VIRTUAL+ is proposed by the authors, which provably generates the best competitive ratio among all the single threshold-based algorithms (when the number of data points being attacked is less than 5). The attacker may not have access to the target deep learning model but can estimate the query value. Hence, the authors obtain theoretical bounds on the performance of the proposed VIRTUAL+ algorithm for the stochastic setting. This paper conducts experiments on both MNIST and CIFAR-10 with both vanilla and robust classifiers.\n", "summary_of_the_review": "In the review, I proposed two major concerns toward the paper along with some minor ones. I did not check the proof carefully but they look correct.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper opens the area of adversarial-attack research on streaming data (e.g., real-world settings such as self-driving cars and robotic visual tasks for a robot). For instance, online adversaries can focus their attack on a small subset of the streamed/online data, but still cause much damage to downstream models. This work highlights the need for stateful defense strategies. Connections to online algorithms and the k-secretary problem are made, along with improvements to some online-algorithms work of Albers and Ladewig.  

Overall, the attack model introduced is important, and the bridge to online algorithms would be useful for the ICLR community. I also believe this topic lends diversity to the typical set of ICLR papers.
Decision: Accept (Poster)