  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.
