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 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 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 textit{any} online algorithms adapted to this setting. Finally,
we complement our theoretical results by conducting experiments on both MNIST
and CIFAR-10 with both vanilla and robust 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

By admin