  3D point cloud classification has many safety-critical applications such as
autonomous driving and robotic grasping. However, several studies showed that
it is vulnerable to adversarial attacks. In particular, an attacker can make a
classifier predict an incorrect label for a 3D point cloud via carefully
modifying, adding, and/or deleting a small number of its points. Randomized
smoothing is state-of-the-art technique to build certifiably robust 2D image
classifiers. However, when applied to 3D point cloud classification, randomized
smoothing can only certify robustness against adversarially {modified} points.
  In this work, we propose PointGuard, the first defense that has provable
robustness guarantees against adversarially modified, added, and/or deleted
points. Specifically, given a 3D point cloud and an arbitrary point cloud
classifier, our PointGuard first creates multiple subsampled point clouds, each
of which contains a random subset of the points in the original point cloud;
then our PointGuard predicts the label of the original point cloud as the
majority vote among the labels of the subsampled point clouds predicted by the
point cloud classifier. Our first major theoretical contribution is that we
show PointGuard provably predicts the same label for a 3D point cloud when the
number of adversarially modified, added, and/or deleted points is bounded. Our
second major theoretical contribution is that we prove the tightness of our
derived bound when no assumptions on the point cloud classifier are made.
Moreover, we design an efficient algorithm to compute our certified robustness
guarantees. We also empirically evaluate PointGuard on ModelNet40 and ScanNet
benchmark datasets.
