Year: 2021

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 ksecretary problem in theoretical computer science and propose VIRTUAL+, a simple yet practical online algorithm. Our main theoretical result show VIRTUAL+ yields provably the best competitive ratio over all single-threshold algorithms for k < 5— extending previous analysis of the k-secretary problem. We also introduce the stochastic k-secretary—effectively reducing online blackbox transfer attacks to a ksecretary 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 not only the necessity of online algorithms in achieving near-optimal performance but also the rich interplay of a given attack strategy towards online attack selection, enabling simple strategies like FGSM to outperform classically strong whitebox adversaries.

text: 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 ksecretary problem in theoretical computer science and propose VIRTUAL+, a simple yet practical online algorithm. Our main theoretical result show VIRTUAL+ yields provably the best competitive ratio over all single-threshold algorithms for k < 5— extending previous analysis of the k-secretary problem. We also introduce the stochastic k-secretary—effectively reducing online blackbox transfer attacks to a ksecretary 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 not only the necessity of online algorithms in achieving near-optimal performance but also the rich interplay of a given attack strategy towards online attack selection, enabling simple strategies like FGSM to outperform classically strong whitebox adversaries.

heading: 1 INTRODUCTION
text: 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 et 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. (2017), where the attacker has complete access, and the less permissive blackbox threat model where an 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 (e.g., whitebox and blackbox) implicitly assume a 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 depicted in Fig. 1. Here, data is streamed between two endpoints—i.e., from sensors on an autonomous car to the actual control system. An adversary, in this example, would intercept the 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 on whether to attack and if she fails, or opts not to attack, then that datapoint is no longer available for further attacks. 2. Online Attack Budget: The adversary—to remain anonymous from stateful defences—is restricted to a small selection budget and must optimally balance a passive exploration phase before selecting high value items in the data stream (e.g. easiest to attack) to submit an attack on.
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 a data stream and thus cannot be applied in a realistic online setting where an adversary is forced into irrevocable decisions. Moreover, these approaches do not come with theoretical guarantees. Consequently, assessing the practicality of adversarial attacks— to better expose risks—in a truly online setting is still an open problem, and the focus of this paper.
Main Contributions. We formalize the online threat model to study adversarial attacks on streaming data. In our online threat model, the adversary must execute k successful attacks within n streamed data points, where k n. As a starting point for our analysis, we 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 a threat model, modulo the attack strategy, equates to the k-secretary problem known in the field of optimal stopping theory Dynkin (1963); 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 (k, n), 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 a suite of experiments on both toy and standard datasets and classifiers (i.e., MNIST, CIFAR-10, and Imagenet). Our empirical investigations reveal two 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 a online algorithm, demonstrating the importance of carefully selecting which data points to attack. We summarize our key contributions:
• We formalize the online adversarial attack threat model as an online decision problem and rigorously connect it to a generalization of the k-secretary problem. • We introduce and analyze VIRTUAL+, an extension of VIRTUAL for the k-secretary problem yielding a significant practical improvement (60%). We then provide, via novel techniques, a tractable formula for its competitive ratio, partially answering one of Albers & Ladewig (2020)’s open questions (see footnote 1) and achieving a new state-of-the-art competitive ratio for k < 5. • We propose Alg. 2 that leverages (secretary) online algorithms to perform efficient online adversarial attacks. We compare different online algorithms including VIRTUAL+ on MNIST, CIFAR-10, and Imagenet in the challenging Non-Interactive BlackBox transfer (NoBox) setting.

heading: 2 BACKGROUND AND PRELIMINARIES
text: 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 ∈ X and labels them with a class label y ∈ Y . The goal of an adversarial attack is then to produce an adversarial example x′ ∈ X , such that ft(x′) 6= y, and where the distance d(x, x′) ≤ γ. Then, equipped with a loss ` used to evaluate ft, an attack is said to be optimal if (Carlini & Wagner, 2017; Madry et al., 2017), x′ ∈ argmaxx′∈X `(ft(x′), y) , s.t. d(x, x′) ≤ γ . (1) 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. 1 is solved by following the gradient∇xft that maximizes `. 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 a 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 k 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.e., 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 a subset of items S∗ while having full knowledge of all n items, if asymptotically in n
Eπ∼Sn [V(SA)] ≥ (C + o(1))V(S∗) , (2) where V is a set-value function that determines the sum utility of each algorithm’s selection, and the expectations are over permutations sampled from the symmetric group of n 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.

heading: 3 ONLINE ADVERSARIAL ATTACKS
text: Motivated by our more realistic threat model, we now consider a novel adversarial attack setting where the data is no longer static but arrives in an online fashion.

heading: 3.1 ADVERSARIAL ATTACKS AS SECRETARY PROBLEMS
text: 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 ft—is 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 = {(x1, y1), . . . , (xn, 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 SA ⊂ D of items to maximize:
V(SA) := ∑
(x,y)∈SA
`(ft(ATT(x)), y) s.t. |SA| ≤ k, (3)
where ATT(x) denotes an attack on x crafted by a fixed attack method ATT that might or might not depend on ft. From now on we define x′i = ATT(xi). Intuitively, the adversary chooses k instances that are the “easiest" to attack, i.e. 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 γ 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 SA versus S∗.
If the adversary knows the true value of a datapoint then the online attack problem reduces to the original k-secretary. On the other hand, the adversary might not have access to ft and instead, the adversary’s value function may be an estimate of the true value—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 vi := `(ft(x′i), yi) for i ∈ {1, . . . , n} := [n] are known (§3.2), as well as the richer stochastic setting with only estimates of vi , i ∈ [n] (§4). 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 a strategy poses several critical problems when operating in real-world online attack scenarios. Chiefly, attacking any instance in D incurs a non-trivial risk that the adversary is detected by a defense mechanism. Indeed, when faced with stateful defense strategies (e.g. Chen et al. (2020)) every additional attacked instance further increases the risk of being detected and rendering future attacks impotent. Moreover, attacking every instance may be infeasible computationally for large n 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., `∞-attacks) 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 instance, in the
autonomous control system example, the adversary can choose to be active for a short interval—e.g., when the autonomous car is a certain 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 → Y , through adversarial examples that respect a chosen distance function, d, with tolerance γ. • The data stream D. The data stream D contains the n examples (xi, yi) 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 on a unique item in D. • A value function V . Each item in the dataset is assigned a value on arrival by the value function V : X × Y → R+ 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 a stochastic estimate of the incurred loss given by a surrogate model fs ≈ ft.
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 objective is then to use its value function towards selecting items inD that maximize the sum total value of selections V (Eq. 3).

heading: 3.2 VIRTUAL+ FOR ADVERSARIAL SECRETARY PROBLEMS
text: 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(xi, yi) = `(ft(x′i), yi) = vi i.e. the loss resulting from the adversary corrupting incoming data xi into x′i. Under a fixed attack strategy, the selection of high-value items from D is exactly the original k-secretary problem and thus the adversary may employ any A that solves the original k-secretary problem. Well known single threshold-based algorithms that solve the k-secretary problem include the VIRTUAL, OPTIMISTIC Babaioff et al. (2007) and the recent SINGLE-REF algorithm Albers & Ladewig (2020). In a nutshell, these online algorithm consists of two phases—a sampling phase followed by a selection phase—and an 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 to a pre-specified threshold t. Note that t itself is algorithm-specific 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).
Algorithm 1 VIRTUAL and VIRTUAL+ Inputs: t ∈ [k . . . n− k], R = ∅, SA = ∅ Sampling phase: Observe the first t data points and construct a sorted list R with the indices of the top k data points seen. The method sort ensures: V(R[1]) ≥ V(R[2]) · · · ≥ V(R[k]). Selection phase:{//VIRT+ removes L2-3 and adds L4 } 1: for i := t+ 1 to n do 2: if V(i) ≥ V(R[k]) and R[k] > t then 3: R = sort(R ∪ {i} \ {R[k]}) 4: else if V(i) ≥ V(R[k]) and |SA| ≤ k then 5: R = sort(R∪ {i} \ {R[k]}) {// Update R}
6: SA = SA ∪ {i} {// Select element i}
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 for varying values of n and k—in addition to being (1/e)-competitive (optimal for k = 1) make them suitable candidates for solving Eq. 3. However, the competitive ratio of both algorithms in the small k regime—but not
k = 1—has shown to be sub-optimal with SINGLE-REF provably yielding larger competitive ratios at the cost of an additional hyperparameter selected via combinatorial optimization when n→∞. 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-art 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 strikethrough. Concretely, the condition that is used by VIRTUAL but not by VIRTUAL+ updates R during the selection phase without actually picking the item as part of SA. Essentially, this condition is theoretically convenient and leads to a simpler analysis by ensuring that the VIRTUAL algorithm never exceeds k selections in SA. VIRTUAL+ removes this conservative R update criteria in favor of a simple to implement condition, |SA| ≤ k line 4 (in pink). Furthermore, the new selection rule also retains the simplicity of VIRTUAL leading to a painless application to online attack problems.
Competitive ratio of VIRTUAL+. What appears to be a minor modification in VIRTUAL+ compared to VIRTUAL leads to a significantly more involved analysis but a larger competitive ratio. In Theorem 1, we derive the analytic expression that is a tight lower bound for the competitive ratio of VIRTUAL+ for general-k. We see that VIRTUAL+ provably improves in competitive ratio for k < 5 over both VIRTUAL, OPTIMISTIC, and in particular the previous best single threshold algorithm, SINGLE-REF. Theorem 1. The competitive ratio of VIRTUAL+ for k ≥ 2 with threshold tk = αn can asymptotically be lower bounded by the following concave optimization problem,
Ck ≥ max α∈[0,1] f(α) := αk k−1∑ m=0 am ln m(α)− αa0 where am := ( kk (k−1)k−m − km ) (−1)m+1 m! .
(4) Particularly, we get C2 ≥ 0.427, C3 ≥ .457, C4 ≥ .4769 outperforming Albers & Ladewig (2020).
Connection to Prior Work. The full proof for Theorem 1 can be found in §B along with a simple but illustrative proof for k = 2 in §A. Theorem 1 gives a tractable way to compute the competitive ratio of VIRTUAL+ for any k, that improve the previous state-of-the-art (Albers & Ladewig, 2020) in terms of single threshold k-secretary algorithms for k < 5 and k > 100.1 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-secretary 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 Ω(nk2) parameters for each length of the data stream n, and the number of constraints grows to infinity as n→∞. Chan et al. (2014) showed that optimal algorithms with k2 thresholds could be obtained using infinite LPs and derived an optimal algorithm for k = 2 Nevertheless they require a large number of parameters and the scalability of infinite LPs for k > 2 remains uncertain. In this work, we focus on practical methods with a single threshold (i.e., with O(1) parameters, e.g. Algorithm 1) that do not require involved computations that grow with n.
Open Questions for Single Threshold Secretary Algorithms. By proposing new non-asymptotic results on the k-secretary problem that outperform asymptotically optimal algorithms, Albers & Ladewig (2020) opened a new range of open questions for the k-secretary problem. While this problem is considered solved when working with probabilistic algorithms2 with Θ(nK2) parameters (Buchbinder et al., 2014), finding optimal non-asymptotic single-threshold (O(1) parameters) algorithms is still an open question. As a step towards answering this question our work propose a practical algorithm that improves upon Albers & Ladewig (2020) for k = 2, . . . , 4 with an optimal threshold that can be computed easily as it has a closed form.
1Albers & 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 k is one direction of future work”. We partially answer this open question by expressing VIRTUAL+’s optimal threshold tk as the solution of a uni-dimensional concave optimization problem. In Table 3, we provide this threshold for a wide range of k ≥ 100.
2At each time-step a deterministic algorithm chooses a candidate according to a deterministic rule depending on some parameters (usually a threshold and potentially a rank to compare with). A probabilistic algorithm choose to accept a candidate according to qi,j,l the probability of accepting the candidate in i-th position as the jth accepted candidate given that the candidate is the l-th best candidate among the i first candidates (i ∈ [n], j, l ∈ [K].) See (Buchbinder et al., 2014) for more details on probabilistic secretary algorithms.

heading: 4 STOCHASTIC SECRETARY PROBLEM
text: 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 et al. (2017); Bose et al. (2020) we focus on modeling that partial knowledge by equipping the adversary with a surrogate model or representative classifier fs. Using fs as opposed to ft means that we can compute the value Vi := `(fs(x′i), yi) of an incoming data point. This value Vi acts as an estimate of the value of interest vi := `(ft(x′i), yi). The stochastic k-secretary problem is then to pick, under the noise model induced by using fs, the optimal subset SA of size k from D. Thus, with no further assumptions on fs 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 an estimate of vi. 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 to initialization or data sampling), making it impossible to perfectly replicate ft. Moreover, it have been observed that, in practice, adversarial examples transfer across models (Papernot et al., 2016; Tramèr et al., 2017). In that context, it is reasonable to assume that the random variable Vi := `(fs(x′i), yi) is likely to be close to vi := `(ft(x′i), yi). We formalize this idea in Assumption 1

heading: 4.1 STOCHASTIC SECRETARY ALGORITHMS
text: In the stochastic k-secretary problem, we assume access to random variables Vi and that vi are 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 a minor difference that in the stochastic case, the algorithm does not have access to the values vi but to Vi that is an estimate of vi. An algorithm is said to be Cs-competitive in the stochastic setting if asymptotically in n, Eπ∼Sn [V(SA)] ≥ (Cs + o(1))V(S∗) . Here the expectation is taken over Sn (uniformly random permutations of the datastream D of size n) and over the randomness of Vi , i = 1, . . . , n. SA and S∗ are the set of items chosen by the stochastic online and offline algorithms respectively (note that while the online algorithm has access to Vi, the offline algorithm picks the best vi) and V is a set-value function as defined previously.
Analysis of the algorithms. In the stochastic setting all online algorithms observe Vi that is an estimate of the actual value vi. Since the goal of the algorithm is to select the k-largest values by only observing random variables (Vi) it is requisite to make a feasibility assumption on the relationship between values vi and Vi. Let us denote topk{vi} as the set of top-k values among (vi). Assumption 1 (Feasibility). ∃γ > 0 such that P[Vi ∈ topk{Vi} | vi ∈ topk{vi}] ≥ γ, ∀n ≥ 0.3
Assumption 1 is a feasibility assumption as if the ordering of (Vi) does not correspond at all with the ordering of (vi) then there is no hope any algorithm—online or an offline oracle—would perform better than random when picking k largest vi by only observing (Vi). In the context 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 §C.1, for the empirical caliber of assumption 1). We can bound the competitive ratio in the stochastic setting. Theorem 2. Let us assume that VIRTUAL+ observes independent random variables Vi following Assumption 1. Its stochastic competitive ratio Cs can be bounded as follows,
C ≥ Cs ≥ γC (5)
The proof of Thm. 2 can be found in §C. Such a 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, Vi, not being faithful to the true ranking based on vi.

heading: 4.2 RESULTS ON SYNTHETIC DATA
text: We assess the performance of classical single threshold online algorithms and VIRTUAL+ in solving the stochastic k-secretary problem on a synthetic dataset of size n = 100 with k ∈ [1, 10]. The value
3Note that, for the sake of simplicity, the constant γ is assumed to be independent of n but a similar non-asymptotic analysis could be performed by considering a non-asymptotic definition of the competitive ratio.
of a data point is its index in D prior to applying any permutation π ∼ Sn plus noise N (0, σ2). We compute and plot the competitive ratio over 10k unique permutations of each algorithm in Figure 3.
1 2 3 4 5 6 7 8 k
0.30
0.35
0.40
0.45
0.50
0.55 0.60 Co m pe tit iv e R ati o
Virtual Optimistic Single-Ref Virtual+
As illustrated for k = 1 all algorithms achieve the optimal (1/e)-deterministic competitive ratio in the stochastic setting. Note that the noise level, σ2, appears to have a small impact on the performance of the algorithms (§E.2). This substantiates our result in Thm. 2 indicating that Cn-competitive algorithms only degrade by a small factor in the stochastic setting. For k < 5, VIRTUAL+ achieves the best competitive ratio—empirically validating Thm 1—after which SINGLE-REF is superior.

heading: 5 EXPERIMENTS
text: 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 ft. Instead, the adversary only has access to a surrogate fs which is similar to ft. In particular, we pick at random a ft and fs from an ensemble of pre-trained models from various canonical architectures. We perform experiments on the MNIST LeCun & Cortes (2010) and CIFAR-10 Krizhevsky (2009) datasets where we simulate a D by generating 1000 permutations of the test set and feeding each instantiation to Alg. 2. In practice, online adversaries compute the value Vi = `(fs(x′i), yi) of each data point in D by attacking fs using their fixed attack strategy (where ` is the cross-entropy), but the decision to submit the attack to ft is done using an online algorithm A (see Alg. 2). As representative attack strategies, we use the well-known FGSM attack (Goodfellow et al., 2015) 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 ft out of a possible of k attacks selected by A. The architectures used for fs, ft, and additional metrics (e.g. competitive ratios) can be found in §E.
Baselines. We rely on two main baselines, first we use a NAIVE baseline–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 fs, are submitted by using the true value vi 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 of the NAIVE baseline and an A as F NAIVEπ , FAπ respectively. In Fig. 4, we uniformly sample 20 permutations πi ∼ Sn, i ∈ [n], of D and plot a scatter graph of points with coordinates (F NAIVEπi , FAπi), for different A’s, attacks with k = 1000, and datasets. The line y = x corresponds to the NAIVE baseline performance —i.e.
coordinates (F NAIVEπ , F NAIVE π )—and each point above that line corresponds to an A that outperforms the baseline on a given πi. As observed, all A’s significantly outperform the NAIVE baseline with an average aggregate improvement of 7.5% and 34.1% on MNIST and CIFAR-10.
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 SINGLE-REF and our proposed VIRTUAL+ which approach the upper bound provided by OPT. For experiments with k < 5 please see §E.5. For k = 10 and k = 100, SINGLE-REF 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-REF which appears more sensitive to the choice of optimal thresholds and reference ranks, both of which are unknown beyond k = 100 and non-trivial to find in closed form (see §E.3 for details). On CIFAR-10, we 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 algorithms improve over the NAIVE baseline and approach saturation to the optimal offline algorithm and as a result all algorithms are equally performant—i.e. 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.
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 et al., 2017) to the online setting. We report the average performance of each A in Table 2. We observe that VIRTUAL+ is the best online algorithms, outperforming VIRTUAL and OPTIMISTIC, in all settings except for k = 10 on MNIST where SINGLE-REF is slightly better.
Q4: Differences between the online and offline setting. The online threat model presents several interesting phenomenon 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 et al. (2017), but we argue the online setting further exacerbates this phenomenon. We explain this phenomenon in Fig. 5a & 5b by plotting the ratio of unsuccessful attacks to total attacks as a function of loss values for PGD and FGSM. We see that for the PGD attack numerous unsuccessful attacks can be found even for high surrogate loss values and as a result can leadA further astray by picking unsuccessful data points—which may be top-k in surrogate loss values—to conduct a transfer attack. A similar initially counter-intuitive observation can be made when comparing the online fool rate on robust and non-robust classifiers. While it is natural to expect the online fool rate to be lower on robust model we empirically observe the opposite in Tab. 5 and 2. To understand this phenomena we plot the ratio of unsuccessful attacks to total attacks as a function fs’s loss in Fig. 5c and observe non-robust models provide a non-vanishing ratio of unsuccessful attacks for large values of Vi making it harder for A to pick successful attacks purely based on loss (see also §F).
0.0 0.2 0.4 0.6 0.8 1.0
Target model loss values vi (normalized)
0.00
0.02
0.04
0.06
0.08
D en
si ty
PGD ATTACK FGSM ATTACK
(a) Distribution of ft’s loss values.
0.0 0.2 0.4 0.6 0.8 1.0
Surrogate model loss values Vi (normalized)
0.000
0.005
0.010
0.015
0.020
Ra tio
o f u
ns uc
ce ss
fu l a
tta ck
s PGD ATTACK FGSM ATTACK
(b) Ratio of unsuccessful attacks.
0.0 0.2 0.4 0.6 0.8 1.0
Surrogate Loss values Vi (normalized)
0.0
0.2
0.4
0.6
0.8
1.0
Ra ti
o of
u n
su cc
es sf
u l a
tt ac
k s
Non-Robust Model
Robust Model Non-Robust Model
(c) Ratio of unsuccessful attacks.
Figure 5: For every example in MNIST we compute an attack using fs and submit it to ft. Left: The distribution of the normalized loss values of ft for all attacks where a higher loss is a stronger attack. Middle: The percentage of unsuccessful attacks as a function of fs normalized loss values. Right: smoothed ratio of unsuccessful attacks to total attacks as a function of the fs normalized loss values.

heading: 6 RELATED WORK
text: Adversarial attacks. The idea of attacking deep networks was first introduced in (Szegedy et al., 2014; Goodfellow et al., 2015), and recent years have witnessed the introduction of challenging threat models, such as blackbox Chen et al. (2017); Ilyas et al. (2018); Jiang et al. (2019); Bose et al. (2020); Chakraborty et al. (2018) as well as defense strategies Madry et al. (2017); Tramèr et al. (2018); Ding et al. (2020). Closest to our setting are adversarial attacks against real-time systems Gong et al. (2019a;b) and deep reinforcement learning agents Lin et al. (2017); Sun et al. (2020). However, unlike our work, these are not online algorithms and do not impose online constraints (see §G).
k-secretary. The classical secretary problem was originally proposed by Gardner (1960) and later solved in Dynkin (1963) with an (1/e)-optimal algorithm. Kleinberg (2005) introduced the k-secretary problem and an asymptotically optimal algorithm achieving a competitive ratio of 1−Θ( √ 1/k). As outlined in §3.2 for general k an optimal algorithms exist Chan et al. (2014), but requires the analysis of involved LPs that grow with the size of n. A parallel line of work dubbed the prophet secretary problem, considers online problems where—unlike §4.1—some information on the distribution of values is known a priori Azar et al. (2014; 2018); Esfandiari et al. (2017). Secretary problems have also been applied to machine learning by informing the online algorithm about the inputs before execution Antoniadis et al. (2020); Dütting et al. (2020). Finally, other interesting secretary settings include playing with adversaries Bradac et al. (2020); Kaplan et al. (2020).

heading: 7 CONCLUSION
text: In this paper, we 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 to select easy to fool data points while being theoretically the best single threshold algorithm for k < 5. We further introduce the stochastic k-secretary problem and prove fundamental results on the competitive ratio of any online algorithm operating in 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 a natural direction for future work.

heading: ETHICS STATEMENT
text: We introduce the online threat model which aims to capture a 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 to attacking a small subset of streamed data but still cause significant damage to downstream models e.g. the control system of an autonomous car. On the other hand our research also highlights the need and importance of stateful defence strategies that are capable of mitigating such online attacks. On the theoretical side the development and analysis of VIRTUAL+ has many potential applications outside of adversarial attacks broadly categorized as resource allocation problems. As a concrete example one can consider advertising auctions which provide the main source of monetization for a variety of internet services including search engines, blogs, and social networking sites. Such a scenario is amenable to being modelled as a secretary problem as an advertiser may be able to estimate accurately the bid required to win a particular auction, but may not be privy to the trade off for future auctions.

heading: REPRODUCIBILITY STATEMENT
text: Throughout the paper we tried to provide as many details as possible in order for the results of the paper to be reproducible. In particular, we provide a detailed description of VIRTUAL+in Alg. 1 and we explain how to combine any attacker (e.g. PGD) with an online algorithm to form an online adversarial attack in Alg. 2. We provide a general description of the experimental setup in §5, 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 to produce the experimental results is provided with the supplementary materials and will be made public after the review process.

heading: A PROOF OF COMPETITIVE RATIO FOR VIRTUAL+ALGORITHM
text: As an illustrative example that aids in understanding the full general-k proof for for the competitive ratio VIRTUAL+ we now prove Theorem 1 for k = 2 from the main paper. Theorem 3. For k = 2, the competitive ratio achieved by VIRTUAL+ algorithm is equal to,
Cn = t(t− 1)
n
n−1∑ j=t
1
j(j − 1)
( 1 + 2
j∑ p=t+1 1 p− 1
) (6)
Particularly for t = α · n , α ∈ (0, 1) we get Cn > α(3(1− α) + 2α ln(α)) +O(1/n) (7)
Thus, asymptotically we have
C > max α∈[0,1]
α(3(1− α) + 2α ln(α)) > .4273 > 1/e . (8)
Pick any top element at 2 j + 1Length of sampling phase
Proof. First note that by Albers & Ladewig (2020, Lemma 3.3) we can show that the competitive ratio for the k-secretary problem for a monotone algorithm is equal to
C = 1
k k∑ a=1 P(ia ∈ SA), (9)
where ia is the index of the ath secretary picked by the offline solution —i.e. ia is a top-k secretary of D. By Lemma 2 VIRTUAL+ is a monotone algorithm and we may use Eq. 9. Now, let us focus on the case k = 2. When calculating the probability of either of the top two items in D being picked by the VIRTUAL+ we must first compute the probability of one of the top-2 items being picked during the selection phase (time step t + 1 . . . n). Now notice that VIRTUAL+ picks an item at time step j + 1 if and only if this is a top-2 item with respect to all of D and |SA| ≤ 2 at time-step j + 1. Let top-2j denote the two largest elements observed by A up to and inclusive of time step j. Thus, for a ∈ {1, 2}, we have
P(ia ∈ SA) = n−1∑ j=t P(ia ∈ SA at time-step j + 1) (10)
= 1
n n−1∑ j=t P(|SA| < 2 at time-step j + 1)
Now, we compute P(|SA| ≤ 2 at time-step j+ 1) by decomposing this probability into the following two events: A.) |SA| = 0 where the selection set is empty and B.) the event |SA| = 1 where exactly one item has been picked. We now analyze each event in turn.
Event A. In order for the event |SA| = 0 to occur it implies that the algorithm does not select any items in the first j rounds. This means both two top-2j elements must have appeared in the sampling phase. Thus the probability for this event is exactly t(t−1)j(j−1) .
Event B. The second event is when |SA| = 1 —i.e. the algorithm picks exactly one element in the first j rounds. The computation of this event is illustrated in Figure 6. Let’s say that an element is picked at time step p. Now to compute the probability of Event B occurring we first make the following two observations:
Observation 1: In order for exactly one element to be picked at the time step p ≤ j, this element must be one of the top-2j elements. Furthermore, this implies the other of the top-2j element —i.e. the one not picked at p must have appeared in the sampling phase. Note that if both top-2j elements appear after the sampling phase, the condition would be satisfied twice and two elements would be selected instead of exactly one, and if they both appeared during the sampling phase we return to Event A. As a result, the probability for this condition is given by tj(j−1) . Observation 2: By observation 1. we know that the online algorithm A picks one of the top-2j at time step p and the fact that the event under consideration is |SA| = 1 the reference list R from time step p to j + 1 must contain both top-2j elements. However, for A to pick only at p we also need to ensure that no elements are picked prior t to p. Therefore, before time step p the reference list must contain top-2p . Again by observation 1, we know that R already contains one of the top-2j elements therefore we know it contains one of the top-2p elements. Thus the probability of ensuring that the second top-2p elements is also within R by time step p is (t−1) (p−2) . Finally,
since there are two top elements and they may appear in any order we must count the probability of Event B occurring twice.
Overall we get: t(t− 1) j(j − 1) + 2 j∑ p=t+1 1 j t j − 1 t− 1 p− 2 (11)
Total probability:
1
n n−1∑ j=t ( t(t− 1) j(j − 1) + 2 j∑ p=t+1 1 j t j − 1 t− 1 p− 2 ) = 1 n n−1∑ j=t ( 1 + 2 j−1∑ p=t 1 p− 1 )
= t(t− 1)
n
n−1∑ j=t
( 1
j(j − 1) + 2 j(j − 1) j−1∑ p=t 1 p− 1
)
> t(t− 1)
n
n−1∑ j=t
( 1
j2 + 2
1
j2 j∑ p=t+1 1 p− 1
)
> t(t− 1)
n
n−1∑ j=t ( 1 j2 + 2 j2 ∫ j+1 p=t+1 1 p− 1 dp )
> t(t− 1)
n
n−1∑ j=t ( 1 j2 + 2 j2 ln ( j t )) Now we will use the following lemma
Lemma 1. For any differentiable function f and any a < b, we have, b∑
j=a
f(j) ≥ ∫ b+1 a f(t)dt− |b+ 1− a| sup t∈[a,b+1] |f ′(t)| (12)
Proof.
|f(n)− ∫ n+1 n f(t)dt| ≤ ∫ n+1 n |f(n)− f(t)|dt ≤ sup t∈[n,n+1] |f ′(t)| (13)
Thus,
f(n) ≥ ∫ n+1 n f(t)dt− sup t∈[n,n+1] |f ′(t)| (14)
and by summing for n = a . . . b we get the desired lemma.
Applying this lemma to f(x) = 1+2 ln(x/t)x2 , a = t and b = n− 1, we get
1
n n−1∑ j=t t(t− 1) j(j − 1) + 2 j∑ p=t+1 1 j t j − 1 t− 1 p− 2 > t(t− 1) n n−1∑ j=t ( 1 j2 + 2 j2 ln ( j t )) (15)
≥ t(t− 1) n (∫ n t 1 + 2 ln(x/t) x2 dx− 2(n− t) sup x∈[t,n] ∣∣∣∣4 ln(x/t)x3 ∣∣∣∣ )
≥ t(t− 1) n (∫ n t 1 + 2 ln(x/t) x2 dx− 2(n− t) ∣∣∣∣ 163t3e4 ∣∣∣∣) = t(t− 1)
n
( 3
t − 2 ln(n/t) + 3 n − 2(n− t) ∣∣∣∣ 163t3e4 ∣∣∣∣)
(16)
Now for t = αn where α ∈ (0, 1) and as n −→∞, that lower-bound becomes C ≥ α(3− α(3− 2 ln(α))) +O(1/n) , ∀α ∈ (0, 1) (17)
The constant term of the RHS is a concave function of α that is maximized for α∗ ≈ 0.38240. Thus, our algorithms achieves competitive ratio larger than 0.42737.
B COMPETITIVE RATIO GENERAL k
We now prove our main result for the competitive ratio of VIRTUAL+ for k ≥ 2. The theorem statement is reproduced here for convenience. Theorem 1. The competitive ratio of VIRTUAL+ for k ≥ 2 with threshold tk = αn can asymptotically be lower bounded by the following concave optimization problem,
Ck > max α∈[0,1]
f(α) := αk ( k−1∑ m=0 am ln m(α) ) −αa0 where am =  kk(k−1)k−m − km m!  (−1)m+1 . Particularly, we get C2 ≥ 0.427, C3 ≥ .457, C4 ≥ .4769 outperforming Albers & Ladewig (2020).
Pick any top elements at k j + 1Length of sampling phase
Proof. First note that by Albers & Ladewig (2020, Lemma 3.3) we can show that the competitive ratio for the k-secretary problem for a monotone algorithm is equal to
C = 1
k k∑ a=1 P(ia ∈ SA), (18)
where ia is the index of the ath secretary picked by the optimal offline solution —i.e. ia is a top-k secretary of D. By Lemma 2 VIRTUAL+ is a monotone algorithm and we may use Eq. 18.
P(ia ∈ SA) = n−1∑ j=t P(ia ∈ SA at time-step j + 1) (19)
= 1
n n−1∑ j=t P(|SA| < k at time-step j + 1)
Now, we compute P(|SA| < k at time-step j + 1) by decomposing this probability into smaller events P(|SA| = ν at time-step j + 1) where ν ∈ [0, . . . , k − 1]. We may compute the probability of P(|SA| = ν at time-step j + 1) in the following manner. First, let us consider the scenario where ν elements are selected by VIRTUAL+ at time steps p1, p2, . . . , pν . Now, in order for an element to be selected at position pν that element must be one of the top k elements up to time-step j + 1. Therefore we have a factor k/j in our equation. Now, in order to guarantee that no elements are picked after the position pν we additionally need to ensure that the
remaining top-k up to j + 1 elements appear before pν which results in a factor of ( pν−1 k−1 ) / ( j−1 k−1 ) . Similarly, we may recursively calculate the corresponding factor for each position pν−1 . . . p1. However, we also need to guarantee that no elements are picked within the time interval [t+1 . . . p1− 1] —i.e. before p1. The probability for this occurring is then ( t k ) / ( p1−1 k ) as this corresponds an ordering where the top-k elements up to p1−1 all appear in the sampling phase. Thus, the probability pk,νt,j := P(|SA| = ν at time-step j + 1) is :
pk,νt,j = ∑
t+1≤p1<p2<···<pk−1≤j
k
j
( pν−1 k−1 )( j−1 k−1 ) k pν − 1 ( pν−1−1 k−1 )( pν−2 k−1 ) k pν−1 − 1 . . . k p2 − 1 ( p1−1 k−1 )( p2−2 k−1 ) (tk)( p1−1 k
) (20)
= t(t− 1) . . . (t− k + 1) j(j − 1) . . . (j − k + 1) ∑ t+1≤p1<p2<···<pν≤j
kν
(pν − k)(pν−1 − k) . . . (p1 − k) (21)
Therefore, the probability of not exceeding k-selections, pkt,j = ∑k−1 ν=0 p k,ν t,j , to get before time step j + 1 is:
pkt,j = t(t− 1)...(t− k + 1) j(j − 1) . . . (j − k + 1)
( 1 + k ∑ p1=t+1...j Λp1 + · · ·+ kk−1 ∑
p1=t+1...p2−1 ...
pk−1=t+1...j
Λp1 . . .Λpk−1
) ,
where we define Λpi := 1 pi−k . The total competitive ratio is then:
Ck = 1
n n−1∑ j=t t(t− 1) . . . (t− k + 1) j(j − 1) . . . (j − k + 1) ( 1 + k ∑ p1=t+1...j Λp1 + · · ·+ kk−1 ∑
p1=t+1...p2−1 ...
pk−1=t+1...j
Λp1 . . .Λpk−1
) ,
(22)
Now using Lemma 3 we can bound it:
Ck ≥ 1
n ∫ n j=t t(t− 1) . . . (t− k + 1) j(j − 1) . . . (j − k + 1) ( 1 + k 1! ln (j − k t ) + · · ·+ k k−1 (k − 1)! ln k−1 (j − k t )) (23)
≥ 1 n ∫ n j=t t(t− 1) . . . (t− k + 1) jk ( 1 + k 1! ln (j − k t ) + · · ·+ k k−1 (k − 1)! ln k−1 (j − k t )) (24)
Now notice that: ∫ 1
a!
lna(x)
xk dx = − 1 xk−1 a∑ m=0 1 m! (k − 1)m−1−a lnm(x) (25)
Using the identity in Eq. 25 we compute the competitive ratio as:
≥ t(t− 1) . . . (t− k + 1) n ( k−1∑ a=0 − 1 jk−1 ka a∑ m=0 1 m! (k − 1)m−1−a lnm (j − k t ))∣∣∣n j=t
(26)
= t(t− 1) . . . (t− k + 1)
n
( − 1 jk−1 k−1∑ m=0 1 m! ( k−1∑ a=m ka(k − 1)m−a−1 ) lnm (j − k t ))∣∣∣n j=t (27)
For threshold t = αn where α ∈ (0, 1) and as n −→∞ our competitive rate becomes:
α ( k−1∑ a=0 ka(k − 1)−1−a ) − αk ( k−1∑ m=0 1 m! ( k−1∑ a=m ka(k − 1)m−a−1 ) lnm ( 1 α )) (28)
= α
(( k
k − 1
)k − 1 ) − αk  k−1∑ m−0  kk(k−1)k−m − km m!  (−1)m+1 lnm(α)  (29)
Finally let us show that
f(α) := αk ( k−1∑ m=0 am ln m(α) ) − αa0 where am =  kk(k−1)k−m − km m!  (−1)m+1 (30) is concave. To do so we just compute it second derivative and show that f ′′(α) ≤ 0. We have,
f ′′(α) = αk−2 k−3∑ m=0 [k(k − 1)am + (2k − 1)(m+ 1)am+1 + (m+ 1)(m+ 2)am+2] lnm−2(α)
+ [k(k − 1)ak−2 + (2k − 1)(k − 1)ak−1] lnk−2(α) + k(k − 1)ak−1 lnk−1(α) . By using the definition of am, we can verify that
k(k − 1)am + (2k − 1)(m+ 1)am+1 + (m+ 1)(m+ 2)am+2 = 0 and k(k − 1)ak−2 + (2k − 1)(k − 1)ak−1 = 0 .
Thus we finally get, f ′′(α) = k(k − 1)ak−1 lnk−1(α) = − k2 ( αk log( 1α ) )k−1 αk! ≤ 0 (31)
where we use the fact that since α ∈ [0, 1], we have α log(1/α) ≥ 0. Definition B.1. An algorithm is called monotone if the probabilities of selecting items i and j satisfy pi ≥ pj whenever the item values vi > vj holds for any two items. Lemma 2. VIRTUAL+ is a monotone algorithm.
Proof. In order to prove that VIRTUAL+ is monotone as defined in Definition B.1 we must prove that pi ≥ pj (where pi is the probability of picking the item i) for any two items where vi > vj . Without loss of generality let us consider a decreasing ordering of n-elements based on their values —i.e. v1 > v2 > · · · > vn. We prove that pi ≥ pi+1 for all i ∈ [1, . . . , n−1] by showing that for each input sequence where vi+1 is accepted, there exists a unique input sequence where vi is accepted. Let us consider a permutation π where vi+1 appeared and was accepted at time step a while vi appeared at time step b. By swapping vi and vi+1 we obtain a new permutation π′ where vi now appears at a and vi+1 at b. We now study the two following cases.
Case 1: a < b.
If a < b notice that the reference set, R, and the selected set SA, are exactly the same at time step a for both permutations π and π′. Therefore, if vi+1 was accepted at time step a in permutation π then vi will also be accepted at time step a in permutation π′ since vi > vi+1.
Case 2: a > b.
If a > b notice that R—by definition of VIRTUAL+—at time step a contains top-k elements observed in the first a− 1 time steps. Now the k-th element in R at time-step a must satisfy,
Raπ[k] ≥ Raπ′ [k], where Ra[·][k] corresponds to the k-element in the reference set for a specific permutation at time step a. Hence, we know that vi > vi+1 ≥ Raπ[k] ≥ Raπ′ [k] as vi+1 was assumed to be picked.
Furthermore, the SA and R is the same for permutations π and π′ at time-step b. Now by our primary assumption that vi+1 is picked at time-step a > b in π this means that vi must be vi ≥ Rbπ[k] since vi > vi+1. However, observe that vi and Rbπ[k] cannot be consecutive in value as vi+1 appears at time-step a > b in permutation π. This implies that vi+1 must also be selected at time step b in permutation π′ since vi and vi+1 are consecutive in value. By a similar argument based on consecutive order of values between time steps a and b precisely the same elements will be selected in both π and π′. The argument that vi > vi+1 ≥ Raπ[k] ≥ Raπ′ [k] implies that if vi+1 is selected in permutation π, vi will also be selected in permutation π′. The claim then follows by applying the inequality pi ≥ pi+1 in an iterative fashion. Lemma 3. Let fi , i = 1 . . . k be decreasing positive functions then we have
b1∑ p1=a1 . . . pk−1∑ pk=ak f1(p1) . . . fk(pk) ≥ ∫ b1+1 x1=a1 . . . ∫ xk−1+1 xk=ak f1(x1) . . . fk(xk)dx1 . . . dxk (32)
Proof. The main proof step involves in first noticing that since the functions fi , i = 1 . . . k are decreasing and are positive we have,
f1(p1) . . . fk(pk) ≥ f1(p1) . . . fk−1(pk−1) ∫ pk+1 xk=pk fk(xk)dxk (33)
Thus, by summing this inequality for pk = ak . . . pk−1, we get pk−1∑ pk=ak f1(p1) . . . fk(pk) ≥ f1(p1) . . . fk−1(pk−1) ∫ pk−1+1 xk=ak fk(xk)dxk (34)
Now, because the functions fi , i = 1 . . . k are decreasing and positive we have,
S = pk−1∑ pk=ak f1(p1) . . . fk(pk) (35)
≥ f1(p1) . . . fk−2(pk−2) ∫ pk−1+1 xk−1=pk−1 fk−1(xk−1) ∫ pk−1+1 xk=ak fk(xk)dxk−1dxk (36)
≥ f1(p1) . . . fk−2(pk−2) ∫ pk−1+1 xk−1=pk−1 fk−1(xk−1) ∫ xk−1 xk=ak fk(xk)dxk−1dxk (37)
where for the last inequality we used the fact that xk−1 ∈ [pk−1, pk−1 + 1]. Finally, by summing for pk−1 = ak−1 . . . pk−2, we get,
pk−2∑ pk−1=ak−1 S = pk−2∑ pk−1=ak−1 pk−1∑ pk=ak f1(p1) . . . fk(pk) (38)
≥ f1(p1) . . . fk−2(pk−2) ∫ pk−1+1 xk−1=pk−1 fk−1(xk−1) ∫ xk−1 xk=ak fk(xk)dxk−1dxk (39)
Using a recursive argument we finally get,
b1∑ p1=a1 . . . pk−1∑ pk=ak f1(p1) . . . fk(pk) ≥ ∫ b1+1 x1=a1 . . . ∫ xk−1+1 xk=ak f1(x1) . . . fk(xk)dx1 . . . dxk (40)
B.1 ANALYTIC COMPUTATION OF Ck FOR VIRTUAL+

heading: C PROOF OF THEOREM 2 AND EMPIRICAL VERIFICATION
text: We now prove Theorem 2 in detail, reproduced here for convenience.
Theorem 2. Let us assume that VIRTUAL+ observes independent random variables Vi following Assumption 1. Its stochastic competitive ratio Cs can be bounded as follows,
C ≥ Cs ≥ γC (41)
Proof. In the Stochastic case we use the same beginning proof as in the non-stochastic case until Eq. 19. Let us consider ia such that Via ∈ topk{Vi},
P(ia ∈ SA) = n−1∑ j=t P(ia ∈ SA at time-step j + 1) (42)
Now, in the stochastic case P(ia ∈ SA at time-step j + 1) not only depends on the set SA not being full but also that ia corresponds to a top-k elements in {vi}. Because of the expectation over permutations, the event of the knapsack being fulled at time step j + 1 is independent from what happens at timestep j + 1. Thus we can write that
P(ia ∈ SA at time-step j + 1) = P(|SA| < k at time-step j + 1)P[Vi ∈ topk{Vi} | vi ∈ topk{vi}] ≥ P(|SA| < k at time-step j + 1)γ .
Finally, we just need to notice that P[Vi ∈ topk{Vi} | vi ∈ topk{vi}] does not depend on the value observed and thus leave to the same computation as in the non-stochastic case.
Similarly, we have
P(ia ∈ SA at time-step j + 1) = P(|SA| < k at time-step j + 1)P[Vi ∈ topk{Vi} | vi ∈ topk{vi}] ≤ P(|SA| < k at time-step j + 1) .
In conclusion it leads to C ≥ Cs ≥ γC (43)

heading: C.1 EMPIRICAL QUANTIFICATION OF ASSUMPTION 1
text: Assumption 1 requires that a percentage of top-k true values vi remain top-k under noise. We now empirically quantify the strength of this assumption in both of our datasets MNIST and CIFAR-10. Note that unlike in theorem we cannot enforce any structure on the random variables that act as surrogate losses as provided by fs. Despite this, we find that in all cases the overlap between the top-k sets is non-zero which enables the effective use of online algorithms for picking candidate attack points as shown in table 4.

heading: D CLASSICAL ONLINE ALGORITHMS FOR SECRETARY PROBLEMS
text: All single threshold online algorithm described in this paper include: VIRTUAL, OPTIMISTIC and SINGLE-REF. Each online algorithm consists of two phases —sampling phase followed by selection phase— and an optimal stopping point t which is used by the algorithm to transition between the phases. We now briefly summarize these two phases for the aforementioned online algorithms.
Sampling Phase - VIRTUAL, OPTIMISTIC and SINGLE-REF. In the sampling phase, the algorithms passively observe all data points up to a pre-specified time index t, but also maintains a sorted reference list R consisting of the k elements with the largest values V(i) seen. Thus the R contains a list of elements sorted by decreasing value. That is R[k] is the index of the k-th largest element in R and V(R[k]) is its corresponding value. The elements in R are kept for comparison but are crucially not selected in the sampling phase.
D.1 VIRTUAL ALGORITHM
Selection Phase - VIRTUAL algorithm. Subsequently, in the selection phase, i > t, when an item with value V(i) is observed an irrevocable decision is made of whether the algorithm should select i into S. To do so, the Virtual algorithm simply checks if the value of the k-th smallest element in R, V(R[k]), is smaller than V(i) in addition to possibly updating the set R. The full Virtual algorithm is presented in Algorithm 1.
Algorithm 3 VIRTUAL ALGORITHM Inputs: t ∈ [k . . . n− k], R = ∅, SA = ∅ Sampling phase: Observe the first t data points and construct a list R with the indices of the top k data points seen. sort ensures: V(R[1]) ≥ V(R[2]) · · · ≥ V(R[k]). Selection phase (at time i > t):
1: if V(i) ≥ V(R[k]) and R[k] > t then 2: R = sort{R ∪ {i} \ {R[k]}} {// Update R with element i and also take out R[k]} 3: else if V(i) ≥ V(R[k]) and R[k] ≤ t then 4: R = sort{R ∪ {i} \ {R[k]}} {// Update R with element i and also take out R[k]} 5: SA = {SA ∪ {i}} {// Select element i} 6: i← i+ 1

heading: D.2 OPTIMISTIC ALGORITHM
text: Selection Phase - OPTIMISTIC algorithm. In the optimistic algorithm, i is selected if and only if V(i) ≥ V(R[last]). Whenever i is selected, R[last] is removed from the list R, but no new elements are ever added to R. Thus, intuitively, elements are selected when they beat one of the remaining reference points from R. We call this algorithm “optimistic” because it removes the reference point R[last] even if V(i) exceeds, say, V(R[1]). Thus, it implicitly assumes that it will see additional very valuable elements in the future, which will be added when their values exceed those of the remaining, more valuable, R[a] , a ∈ [k].

heading: D.3 SINGLE-REF ALGORITHM
text: Selection Phase - SINGLE-REF algorithm. In the SINGLE-REF algorithm, i is selected if and only if V(i) ≥ V(R[r]) and we haven’t already selected k elements. We call this algorithm single
Algorithm 4 OPTIMISTIC ALGORITHM Inputs: t ∈ [k . . . n− k], R = ∅, SA = ∅. Sampling phase (up to time t): Observe the first t data points and construct a list R with the indices of the top k data points seen. sort ensures: V(R[1]) ≥ V(R[2]) · · · ≥ V(R[k]). Set last = k, to be the index of the last element in R. Selection phase (at time i > t):
1: if V(i) ≥ V(R[last]) then 2: R = {R \ {R[last]}} {// Update R by taking out R[k]} 3: SA = {SA ∪ {i}} {// Select element i} 4: last = last− 1 i← i+ 1
reference algorithm because we always compare incoming elements to one single reference element, that was determined in the sampling phase.
Algorithm 5 SINGLE-REF ALGORITHM Inputs: t ∈ [k . . . n− k], R = ∅, SA = ∅, r ∈ [k] (reference rank) Sampling phase (up to time t): Observe the first t data points and construct a list R with the indices of the top k data points seen. Let sr = R[r] be the r-th best item from the sampling phase. Selection phase (at time i > t):
1: if V(i) ≥ sr and |SA| ≤ k then 2: SA = {SA ∪ {i}} {// Choose the first k items better than sr} i← i+ 1

heading: E ADDITIONAL EXPERIMENTAL RESULTS
text: In this appendix we provide detailed results on all experiments against non-robust models. For MNIST and CIFAR-10 we compute the average online fool rate over 1000 runs while for Imagenet we used 5 runs due to the increased computational resources required.

heading: E.1 DETAILED RESULTS ON NON-ROBUST RESULTS

heading: E.2 ADDITIONAL RESULTS ON SYNTHETIC DATA
text: We now provide additional results on Synthetic Data with varying levels of noise added to each item in D. In particular, we investigate in figure 8 online algorithms in the face of no noise —i.e. σ2 = 0, σ2 = 1, and σ2 = 5 in addition to σ2 = 10 reported in figure 3. The deterministic setting corresponds to σ2 = 0 while σ2 = 1 and σ2 = 1 correspond to the stochastic setting as introduced in section 4.

heading: E.3 EXPERIMENTAL DETAILS
text: We provide more details about the experiments presented in section 5. For further details we also invite the reader to look at the code provided with the supplementary materials. The complete code to reproduce results can be found https://anonymous.4open.science/r/

heading: OnlineAttacks-4349
text: Attack strategies We use two different attack strategies the Fast Gradient Sign Method (FGSM) (Goodfellow et al., 2015) and 40 iterations of the PGD attack (Madry et al., 2017) with l∞.
Hyper-parameters of online algorithms All the online algorithms except SINGLE-REF have a single hyper-parameters to choose which is the length of the sampling phase t. For VIRTUAL and OPTIMISTIC we use t = b tec which is the value suggested by theory in Babaioff et al. (2007). For VIRTUAL+ we use t = αn as found by solving the maximization problem for a specific k in Theorem 1. SINGLE-REF has two hyper-parameters to choose the threshold t (c in the original paper) and reference rank r. For k = 1...100 the values are given in Albers & Ladewig (2020) and are numerical solutions to combinatorial optimization problems. However, for k = 1000 no values are specified and we choose c = 0.13 and r = 40 through grid search. Indeed, these values may not be optimal ones but we leave the choice of better values as future work.
MNIST model architectures For table 5, fs and ft are chosen randomly from an ensemble of trained classifiers. The ensemble is composed of five different architectures described in table 7, with 5 trained models per architecture.
CIFAR and Imagenet model architectures For table 5, fs and ft are chosen randomly from an ensemble of trained classifiers. The ensemble is composed of five different architectures: VGG-16
(Simonyan & Zisserman, 2015), ResNet-18 (RN-18) (He et al., 2016), Wide ResNet (WR) (Zagoruyko & Komodakis, 2016), DenseNet-121 (DN-121) (Huang et al., 2017) and Inception-V3 architectures (Inc-V3) (Szegedy et al., 2016), with 5 trained models per architecture.

heading: E.4 ADDITIONAL METRICS
text: In addition to the results provided in table 5, we also provide two other metrics here: the stochastic competitive ratio in table 8 and the knapsack ratio table 9. Where the knapsack ratio is defined as the sum value of SA —i.e. the sum of total loss, as selected by the online algorithm divided by the value of S∗ selected by the optimal offline algorithm. We observe that the competitive ratio is not always a good metric to compare the actual performance of the different algorithms, since sometimes the online algorithm with the best competitive ratio is not the algorithm with the best fool rate. The knapsack ratio on the other hand seems to be a much better proxy for the actual performance of the algorithms, this is due to the fact that we’re interested in picking elements that have have a good chance to fool the target classifier but are not necessarily the best possible attack.

heading: E.5 ADDITIONAL RESULTS
text: Same architecture In addition to table 5 we also provide some results on MNIST where fs and ft always have the same architecture but have different weights. This is a slightly less challenging setting as shown in Bose et al. (2020), we also observe that in this setting the adversaries are very effective against the target model.

heading: F DISTRIBUTION OF VALUES OBSERVED BY ONLINE ALGORITHMS
text: In this section we further investigate performance disparity of online algorithms against robust and non-robust models for CIFAR-10 as observed in Tables 5 and 2. We hypothesize that one possible explanation can be found through analyzing the ratio distribution of values Vi’s for unsuccessful and successful attacks as observed by the online algorithm when attacking each model type. However, note that eventhough an online adversary may employ a fixed attack strategy to craft an attack x′ = ATT(x) the scale of values in each setting are not strictly comparable as the attack is performed on different model types. In other words, given an ATT it is significantly more difficult to attack a robust model and thus we can expect a lower Vi when compared to attacking a non-robust model. Thus to investigate the difference in efficacy of online attacks we pursue a distributional argument.
Indeed, distributions of Vi’s observed, for a specific permutation of D, may drastically affect the performance of the online algorithms. Consider for instance, if the Vi’s that correspond to successful attacks cannot be distinguished from the ones that are unsuccessful. In such a case one cannot hope to use an online algorithm—that only observes Vi’s—to always correctly pick successful attacks. In Figure 9 we visualize the ratio of Vi’s of unsuccessful and successful attacks as the ratio of the densities of unsuccessful versus successful attack vectors (y-axis) as provided by a kernel density estimator for CIFAR-10 robust and non-robust models. It provides a non-normalized value of the ratio of unsuccessful attacks for a given value of Vi. As observed, there is a significant amount of non-successful attacks for large values of Vi in the non-robust case which indicates that there are many data points with high values that lead to unsuccessful attacks. Furthermore, this also suggests one explanation for the higher efficacy of online algorithms against robust models: fewer attacks are successful but they are easier to differentiate from unsuccessful ones because of their relatively larger loss value. Importantly, this implies that given an online attack budget k n higher online fool rates can be achieved against robust models as the selected data points turn adversarial with higher probability when compared to non-robust models.

heading: G FURTHER COMPARISON TO PRIOR WORK
text: While we consider —to the best of our knowledge—that our work is the only truly online threat model. Our setting is the only one considering that data points are only ever observed once, and a decision to attack must be made at the moment and cannot be reversed retroactively. For example, (Gong et al., 2019b) consider replay attacks on Voice-Controlled Systems whereby streamed audio input is captured with a recording device, and then the entire sequence is spoofed and replayed back. Unlike online attacks that we consider, they can manipulate the whole sequence retroactively and do not have to make an irreversible decision to attack at a given timestep. Similarly, both (Lin et al., 2017; Sun et al., 2020) consider adversarial attacks against deep reinforcement learning agents. Like us, they consider an adversarial budget that limits the number of points to attack to avoid detection. However, unlike us, they require whitebox access to the target model in order to train another predictive model by interacting with the environment, which can later be used to inform “when to attack”. Thus the datapoints appearing at test time may already be seen and scored during the training period. The
dichotomy between collecting data for potentially an infinite time horizon before attacking is at odds with our online threat model as a data point can only be observed once. As a result, none of these works can be used within our online threat model and are not appropriate baselines.

Review summaries:
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.

This paper focuses on the online attack problem, where two elements are emphasized that attackers must operate under partial knowledge of 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. 

 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.