  As machine learning (ML) systems become pervasive, safeguarding their
security is critical. However, recently it has been demonstrated that motivated
adversaries are able to mislead ML systems by perturbing test data using
semantic transformations. While there exists a rich body of research providing
provable robustness guarantees for ML models against $\ell_p$ norm bounded
adversarial perturbations, guarantees against semantic perturbations remain
largely underexplored. In this paper, we provide TSS -- a unified framework for
certifying ML robustness against general adversarial semantic transformations.
First, depending on the properties of each transformation, we divide common
transformations into two categories, namely resolvable (e.g., Gaussian blur)
and differentially resolvable (e.g., rotation) transformations. For the former,
we propose transformation-specific randomized smoothing strategies and obtain
strong robustness certification. The latter category covers transformations
that involve interpolation errors, and we propose a novel approach based on
stratified sampling to certify the robustness. Our framework TSS leverages
these certification strategies and combines with consistency-enhanced training
to provide rigorous certification of robustness. We conduct extensive
experiments on over ten types of challenging semantic transformations and show
that TSS significantly outperforms the state of the art. Moreover, to the best
of our knowledge, TSS is the first approach that achieves nontrivial certified
robustness on the large-scale ImageNet dataset. For instance, our framework
achieves 30.4% certified robust accuracy against rotation attack (within $\pm
30^\circ$) on ImageNet. Moreover, to consider a broader range of
transformations, we show TSS is also robust against adaptive attacks and
unforeseen image corruptions such as CIFAR-10-C and ImageNet-C.
