  We propose two general methods for constructing robust permutation tests
under data corruption. The proposed tests effectively control the
non-asymptotic type I error under data corruption, and we prove their
consistency in power under minimal conditions. This contributes to the
practical deployment of hypothesis tests for real-world applications with
potential adversarial attacks. One of our methods inherently ensures
differential privacy, further broadening its applicability to private data
analysis. For the two-sample and independence settings, we show that our kernel
robust tests are minimax optimal, in the sense that they are guaranteed to be
non-asymptotically powerful against alternatives uniformly separated from the
null in the kernel MMD and HSIC metrics at some optimal rate (tight with
matching lower bound). Finally, we provide publicly available implementations
and empirically illustrate the practicality of our proposed tests.
