  Randomized smoothing is a general technique for computing sample-dependent
robustness guarantees against adversarial attacks for deep classifiers. Prior
works on randomized smoothing against L_1 adversarial attacks use additive
smoothing noise and provide probabilistic robustness guarantees. In this work,
we propose a non-additive and deterministic smoothing method, Deterministic
Smoothing with Splitting Noise (DSSN). To develop DSSN, we first develop SSN, a
randomized method which involves generating each noisy smoothing sample by
first randomly splitting the input space and then returning a representation of
the center of the subdivision occupied by the input sample. In contrast to
uniform additive smoothing, the SSN certification does not require the random
noise components used to be independent. Thus, smoothing can be done
effectively in just one dimension and can therefore be efficiently derandomized
for quantized data (e.g., images). To the best of our knowledge, this is the
first work to provide deterministic "randomized smoothing" for a norm-based
adversarial threat model while allowing for an arbitrary classifier (i.e., a
deep model) to be used as a base classifier and without requiring an
exponential number of smoothing samples. On CIFAR-10 and ImageNet datasets, we
provide substantially larger L_1 robustness certificates compared to prior
works, establishing a new state-of-the-art. The determinism of our method also
leads to significantly faster certificate computation.
