  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$-\textit{secretary problem} and
propose \algoname, a simple yet practical algorithm yielding a provably better
competitive ratio for $k=2$ over the current best single threshold algorithm.
We also introduce the \textit{stochastic $k$-secretary} -- effectively reducing
online blackbox attacks to a $k$-secretary problem under noise -- and prove
theoretical bounds on the competitive ratios of \textit{any} online algorithms
adapted to this setting. Finally, we complement our theoretical results by
conducting a systematic suite of experiments on MNIST and CIFAR-10 with both
vanilla and robust classifiers, revealing that, by leveraging online secretary
algorithms, like \algoname, we can get an online attack success rate close to
the one achieved by the optimal offline solution.
