title: Minimal Adversarial Examples for Deep Learning on 3D Point Clouds
authors: Jaeyeon Kim Binh-Son Hua Duc Thanh Nguyen Sai-Kit Yeung
text: 
  
  
  
  
  
  
  Minimal Adversarial Examples for Deep Learning on 3D Point Clouds
      Jaeyeon Kim^1     Binh-Son Hua^2,3     Duc Thanh Nguyen^4     Sai-Kit Yeung^1
  	
  
  
  	^1Hong Kong University of Science and Technology       ^2VinAI Research, Vietnam 
  
  	^4Deakin University                                 ^3VinUniversity, Vietnam
  	
  
  
  
      
  ============================================================================================================================================================================================================================================================
  
  
  
  empty
  
  
  
     With recent developments of convolutional neural networks, deep learning for 3D point clouds has shown significant progress in various 3D scene understanding tasks, e.g., object recognition, semantic segmentation. In a safety-critical environment, it is however not well understood how such deep learning models are vulnerable to adversarial examples. In this work, we explore adversarial attacks for point cloud-based neural networks. We propose a unified formulation for adversarial point cloud generation that can generalise two different attack strategies. Our method generates adversarial examples by attacking the classification ability of point cloud-based networks while considering the perceptibility of the examples and ensuring the minimal level of point manipulations. Experimental results show that our method achieves the state-of-the-art performance with higher than 89% and 90% of attack success rate on synthetic and real-world data respectively, while manipulating only about 4% of the total points.
  
  
  
  
  
  § INTRODUCTION
  
  
  Deep learning has shown great potentials in solving a wide spectrum of computer vision tasks. In life-crucial applications, one concern is that deep neural networks can be vulnerable to adversarial examples, a special kind of inputs that can fool the networks to make undesirable predictions. Several adversarial attack techniques have been proposed to generate such examples. In contrast, adversarial defense methods have been developed to detect and neutralise adversarial examples. Therefore, understanding how adversarial attacks and defenses operate is of great importance to make deep learning techniques more reliable and robust. 
  
  With the growing popularity of low-cost 3D sensors and light-field cameras, the community has started investigating the vulnerability of deep networks on 3D data, especially 3D point clouds <cit.>. However, existing works focus on common scenarios, such as generating adversarial point clouds by perturbing points. While such approaches have high attack success rates, the perturbations are not imperceptible and can be identified easily by outlier detection or noise removal algorithms. In addition, existing adversarial attack methods do not perform optimally since all points in a point cloud are involved in the manipulation.
  
  In this work, we study 3D adversarial attack in a more extreme but practical setting: how to generate an adversarial point cloud with minimum number of points perturbed from an original point cloud while maintaining the perceptibility of the original point cloud (see Figure <ref>). To address this problem, we propose a new formulation for adversarial point cloud generation that can be adapted to different attack strategies. The novelty of our work lies in both the research problem and proposed solution. Specifically, minimal 3D point cloud attack is an unexplored problem. We are also the first to propose a formulation that (i) considers both the perceptibilty and optimality of adversarial samples, and (ii) generalises both point perturbation and addition in a unified framework. In summary, our contributions include:
  
  
  
  
  
  
  
    * A new technique to generate minimal 3D adversarial point clouds;
  
  
    * A unified formulation that generalises two adversarial point cloud generation strategies: point perturbation and point addition;
  
  
    * A vulnerability analysis on the relation between the perturbed points found by our method and the concept of critical points in PointNet <cit.>;
  
  
    * A benchmark of adversarial attacks on both synthetic and real-world 3D point clouds, which shows our method achieves consistent performance over both domains.
   
  
  
  
  
  
  § RELATED WORK
  
  
  
  
    
  3D Deep Learning. 
  Recent availability of 3D datasets <cit.> has led to significant advances in deep learning on 3D data. In this domain, most existing works focus on designing convolution operations that enable convolutional neural networks to learn features directly from point clouds <cit.>. Several attempts have been made to create rotation invariant convolutions <cit.>. Such convolutions allow scene understanding tasks, e.g., object recognition, semantic segmentation, to be trained directly with various input point clouds. Other improvements have also been found in the literature. For instance, Liu et al. <cit.> proposed an  RNN-based model to extract the correlations of local areas. Yan et al. <cit.> extended the pointwise MLP network by adopting adaptive sampling to handle outilers and noise.
  
  
  
  In this work, we adopt PointNet <cit.> as a target neural network to investigate important aspects of our method due to its popularity. However, we also verify our method with different deep learning models including  PointNet++ <cit.>, DGCNN <cit.>, SpiderCNN <cit.>, and PointASNL <cit.>.
  
  
  
  
  
    
  Adversarial Point Clouds.
  There exist studies on adversarial attacks and defenses for point cloud classification <cit.>. For instance, Xiang et al. <cit.> proposed an algorithm for point perturbation and addition based on the attack framework in <cit.> using Chamfer and Hausdorff distance. Liu et al. <cit.> extended the fast gradient sign method in <cit.> for constructing 3D adversarial examples using mesh and clipping norm. The basic ideas in these works follow previous adversarial attack techniques in 2D domain, which focus on how a point cloud should be perturbed to make an adversarial example. Readers are referred to <cit.> for a comprehensive review on adversarial attacks and defenses on images, and to <cit.> for a general analysis and proof of existence of adversarial examples.
  
  It is also possible to mix newly added points with perturbed points in a point cloud to make adversarial examples <cit.>. Yuxin et al. <cit.> considered the consistency of local curvatures in a loss function to guide perturbed points lean towards object surfaces. Tsai et al. <cit.> incorporated the K-Nearest Neighbor loss in  <cit.> to constrain adversarial samples to become physical objects. Zhao et al. <cit.> showed the vulnerability of isometry transformation by making perturbations on isometry matrix. Hadmi et al. <cit.> applied auto-encoders in perturbation to improve the transferability of adversarial examples across networks. Lee et al. <cit.> added perturbation noise into the latent space of auto-encoders to maintain the shape of input point clouds. Zhou et al. <cit.> employed GAN <cit.> in generating adversarial point clouds with predefined target labels. 
  
  In addition to creating adversarial examples by perturbing existing points or adding new points into point clouds, one can fool classification techniques by removing points from input data <cit.>. For instance, Zheng et al. <cit.> eliminated important points on saliency map of an input object. Matthew et al. <cit.> iteratively removed critical points from an input point cloud until a target classification technique failed to classify the point cloud.
  
  In contrast to adversarial attacks, countermeasures for adversarial point clouds have been so far scarce. Typical defense approaches include outlier or salient point removal <cit.> and noise removal <cit.>. Recently, Dong et al. <cit.> used relative position of each local part of a clean point cloud to global object center as adversarial indicator. Wu et al. <cit.> proposed a method to predict implicit functions capturing clean shapes of point clouds. 
  
  
  
    
  Minimal Adversarial Attacks.
  In 2D domain, there is a specific family of techniques that focus on perturbing a minimum number of pixels in adversarial attacks. 
  
  For instance, Papernot et al. <cit.> perturbed pixels on saliency maps. Carlini et al. <cit.> extended this method and used ℓ_0-norm optimisation to minimise the number of pixels to perturb. Recently, Modas et al. <cit.> and Croce et al. <cit.> focused on how to perturb a sparse set of pixels while still achieving good perceptibility. Local search and evolutionary algorithms were also applied to obtain sparse perturbations in <cit.>. 
  
  In this paper, we also explore adversarial attacks that only manipulate a minimal set of points. However, unlike the above works, we propose a new formulation that is general and can be adapted to various adversarial point cloud generation strategies. In addition, we also consider the perceptibility of adversarial examples in our formulation.
  
  
  § PROPOSED METHOD
  
  
  
  Our problem of interest can be stated as follows. Let P={𝐩_1,...,𝐩_N} be an input set of N points where each point 𝐩_i is represented by a vector of its coordinates 𝐩_i=[p_i,x, p_i,y, p_i,z]^⊤∈ℝ^3. Let F denote a point-based neural network, e.g., PointNet <cit.>, and F_i(P) denote the probability that the point set P is classified into the i-th class. Ideally, if i^* is the true class label of the point cloud P, then i^*=argmax_i F_i(P). Let P' be an adversarial example generated from P. We aim to find P' that satisfies the following conditions:
  
  
    (i) The perceptibility of P is maintained, i.e., the generated point cloud P' should not much deform from P;
  
    (ii) A minimum number of points in P are manipulated;
  
    (iii) *argmax_i F_i(P) ≠*argmax_i' F_i'(P'), i.e., P' and P are classified into different classes by the network F. 
  
  
  Note that generation of adversarial point clouds by compromising the attack success rate and perceptibility of adversarial samples has been investigated in the literature, e.g., <cit.>. However, our work differs from <cit.> in the following points. First, our focus
  is untargeted attack while that is targeted attack in <cit.>.
  Second, the number of manipulated points is not considered in <cit.>, leading to extremely high numbers of points are manipulated (as shown in our experiments). Third, while critical points proposed in PointNet <cit.> are used to drive the solution in <cit.>, we show that our method could reach those critical points yet occupy a small portion, proving the capability of our method of finding compact yet vulnerable point sets.
  
  In the following, we present a new formulation to generate P' using ℓ_0-norm optimisation and describe in details how our formulation can be applied to point perturbation and point addition.
  
  
  
  
  
   §.§ Point Perturbation
  
  
  
  
  
    §.§.§ Formulation
   
  
  Given a point cloud P, we aim to find a minimal set of points that can be shifted to generate an adversarial point cloud P' to attack the network F. We express the selection of points in P for perturbation by a binary indication vector 𝐚 = [a_1,...,a_N]^⊤∈{0,1}^N where a_i is 1 if 𝐩_i is selected, and 0 otherwise. Suppose that E = {𝐞_1,...,𝐞_N} is the set of perturbations, in which 𝐞_i=[e_i,x, e_i,y, e_i,z]^⊤∈ℝ^3 is the perturbation vector to be applied on 𝐩_i to obtain 𝐩_i'. Applying perturbation set E on the point cloud P results in an adversarial point cloud P' as
  
      P'={𝐩'_i = 𝐩_i + a_i 𝐞_i |𝐩_i ∈ P} .
  
  
  
  The process of generation of P' can be formulated as,
  
      min_𝐚, E f(P,𝐚, E) = min_𝐚, E{λ_1 𝐚_0 + λ_2 D(P,P') }
         s.t.  *argmax_i F_i(P) ≠*argmax_i' F_i'(P')
  
  where 𝐚_0=#{i:a_i ≠ 0, i=1,...,N} is the ℓ_0-norm of 𝐚 (i.e., the number of non-zero elements in 𝐚) and D(P,P') is some distance between P and P'.
  
  The optimisation problem defined in Eq. (<ref>) covers all the aforementioned conditions. In particular, the first term, 𝐚_0 in the objective function f(P,𝐚, E) imposes the quantity of selected points in the point selection process while the second term, D(P,P') constrains the perceptibility of the adversarial point cloud P' w.r.t. the original point cloud P. As will be explained later in this section, D(P,P') can be defined using different distance metrics. The constraint *argmax_i F_i(P) ≠*argmax_i' F_i'(P') ensures the generated point cloud P' can fool the network F, i.e., F would not classify P and P' into the same class. 
  
  
  
    §.§.§ Perceptibility
  
  There are several ways to realise the perceptibility D(P,P') in Eq. (<ref>). If we assume the correspondence between each point 𝐩_i ∈ P and its perturbed point 𝐩'_i ∈ P' defined in Eq. (<ref>) is maintained, then we can define D(P,P') using the Euclidean distances between 𝐩_i and 𝐩'_i as,
  
      D_Euclidean(P,P') = 1/N∑_i=1^N (a_i ‖𝐞_i ‖_2 )  .
  
  
  
  However, such correspondences are not always well defined, e.g., when the number of points changes in the case of point addition, making Euclidean distance not a valid choice. We further propose to use Chamfer distance and Hausdorff distance to measure perceptibility. Specifically, we can define D(P,P') as
  
      D_Chamfer(P, P')
      =max{1/|P|∑_𝐩_i ∈ Pmin_𝐩'_j ∈ P'‖𝐩_i - 𝐩'_j ‖_2,
      1/|P'|∑_𝐩'_j ∈ P'min_𝐩_i ∈ P‖𝐩'_j - 𝐩_i ‖_2  }
  
  or
  
      D_Hausdorff(P,P')
      =max{max_𝐩_i ∈ P{min_𝐩'_j ∈ P'‖𝐩_i - 𝐩'_j ‖_2},
      max_𝐩'_j ∈ P'{min_𝐩_i ∈ P‖𝐩'_j - 𝐩_i ‖_2  }} .
  
  
  As shown in Eq. (<ref>)-(<ref>), both Chamfer distance and Hausdorff distance do not require the same of number of points in the point clouds P and P'. Hence, they can be adapted easily to different point generation methods, e.g., point addition as presented in Section <ref>. 
  
  
  
    §.§.§ Relaxed Formulation
  
  To solve the constrained optimisation problem in Eq. (<ref>), we convert it into an unconstrained optimisation problem using a Lagrange multiplier-like form as: 
  
      min_𝐚, E f(P,𝐚, E) 
      
      =    min_𝐚, E{λ_1 𝐚_0 + λ_2 D(P,P') + h(P') }
  
  where, like <cit.>, we define,
  
      h(P') = max{0, F_i^*(P') - max_i^* ≠ i' F_i'(P')}
  
  where i^* is the true class label of the point set P.
  
  Since the problem in Eq. (<ref>) is NP-hard in general <cit.>, we further relax it as ℓ_1-norm optimisation <cit.> as:
  
      min_â, E f(P,â, E)
      
      =    min_â, E{λ_1 â_1 + λ_2 D(P,P') + h(P') }
  
  where 𝐚̂ = [â_1,...,â_N]^⊤∈ [0,1]^N,  and â_1=∑_i=1^N â_i is the ℓ_1-norm of â.
  
  
  To solve Eq. (<ref>), we apply the iterative gradient method in <cit.>. Since the final aim is to obtain a binary vector for 𝐚, we randomly initialise 𝐚̂ with near-binary values, i.e., â_i is randomly set to either 0.0001 or 0.9999. Near-binary values are used to give â_i chances to turn into 1 (or 0) if 𝐩_i is selected (or otherwise). Finally, we achieve the final solution for 𝐚 as,
  
      a_i = 
      0,    if â_i = 0 
      
      1,    otherwise .
  
  
  
  Note that we aim to find solutions for both 𝐚 and 𝐞. Given 𝐚 obtained from Eq. (<ref>), we only consider perturbations e_i if a_i = 1.
  
  The optimisation problem defined in Eq. (<ref>) formulates our proposed adversarial generation method. This formulation is general and can be adapted conveniently to other adversarial generation strategies, e.g., point addition.
  
  
  
   §.§ Point Addition
  
  
  
  In addition to point perturbation, we can generate an adversarial example P' by extending P with a minimum number of additional points. We show that our proposed formulation in Eq. (<ref>) can also be applied in this task. 
  Specifically, suppose that there are no more than K points added to the original point cloud P. We can construct a new point set P including all the points in P and K new points. These K new points can be generated by randomly choosing K points in P and adding them to P. We note that this way of construction of P does not change the perceptiblity of P as D(P, P)=0 for either the Chamfer distance or Hausdorff distance used to define D(P, P). In addition, both P and P are treated equally by the network F, i.e., ∀ i, F_i(P) = F_i(P), as the geometric structure of the point clouds remains unchanged.
  
  Similarly, we also construct a vector 𝐚=[a_1,...,a_N+K]^⊤∈ [0,1]^N+K and a perturbation set E={𝐞_1,...,𝐞_N+K} by extending 𝐚 and E with K new elements and solve the optimisation problem in Eq. (<ref>) with a new objective function f(P, 𝐚, E). The vector 𝐚 is initialised as follows, a_i is set to 0 for i ∈{1,..,N}, and to a random value in {0.0001,0.9999} for i ∈{N+1,..,N+K}. Furthermore, during the optimisation process, we fix a_i=0,  ∀ i=1,..,N, i.e., original points in P will not be changed. Finally, the adversarial point cloud P' is obtained by including points 𝐩_i ∈P such that a_i=1.
  
  
  § EXPERIMENTS AND RESULTS
  
  
  
  
   §.§ Experiment Setup
  
  
  
    
  Datasets.
  
  We experimented our method on  ModelNet40 <cit.> and ScanObjectNN <cit.> dataset. ModelNet40 is a benchmark dataset for classification of 3D CAD models. It consists of 9,843 models for training and 2,468 models for testing. We followed the experimental setup in <cit.> to sample the surfaces of the models in ModelNet40 uniformly and normalised points into a unit cube. ScanObjectNN is an object dataset from real-world indoor scans including practical challenges such as view occlusions and object partiality. It has 15,000 objects organised in five challenging variants, e.g., objects with background, translated objects, rotated objects, and scaled objects. In our experiments, we used `OBJ_BG', the most challenging variant including objects with background. We followed Uy et al. <cit.> to normalise the point clouds containing background using mean and furthest point distance.
  
  
  
    
  Implementation Details.
  
  We adopted PointNet <cit.> as a test base network to conduct important experiments. To adapt with point clouds of varying sizes, we modified the max-pooling operator and batch norm accordingly. We used Adam optimiser with learning rate of 0.01. For our adversarial attack algorithm, we performed exhaustive search for the parameters in Eq. (<ref>) and empirically set them as λ_1 = 0.15 and λ_2 = 50. Iterative gradient method in <cit.> with 250 iterations was employed to solve Eq. (<ref>). 
  
  
  
   §.§ Evaluation and Comparison
  
  
  We evaluated our method based on attack success rate, perceptibility of adversarial examples, and average number of manipulated points. The perceptibility of adversarial examples was measured using Chamfer and Hausdorff distance. We report the performance of our method on ModelNet40 and ScanObjectNN dataset in Table <ref> & <ref> respectively. 
  
  
  
  
  
  
  We also compared our method with existing methods. In particular, we tested the method by Xiang et al. <cit.>, which also generated adversarial examples by point perturbation and addition. Since this method aimed for targeted attack, for fair comparison, we altered it to untargeted attack. We re-implemented the method by Liu et al. <cit.> which made attacks in two manners: adversarial sink (i.e., pulling points towards a sink point) and adversarial stick (i.e., resampling points on added sticks). In addition, we evaluated the method by Wicker and Kwiatkowska <cit.>, and by Zheng et al. <cit.>. Since both <cit.> and <cit.> created adversarial examples by removing points, for fair comparison, we applied their point selection strategies but then replaced the point removal by point perturbation and point addition. In detail, the authors in <cit.> selected points either randomly or from a critical point set determined by PointNet <cit.>. In <cit.>, selected points were sampled from saliency maps of input point clouds in three different ways: (i) critical frequency (i.e., points frequently chosen by the max-pooling operator in PointNet <cit.>), (ii) low-score (i.e., points having small loss gradient for a target network), and (iii) high-score (i.e., point having large loss gradient). We will further discuss the “critical points” in Section <ref>.
  We used 250 iterations for  <cit.> and <cit.>. For other baseline methods, we perturbed the objects until a successful attack is made.
  
  
  
  
  
  
  
  As shown in Table <ref> & <ref>, compared with other methods, our method achieves the highest success rate yet lowest number of processing points for both point perturbation and point addition, and on both ModelNet40 and ScanObjectNN. Specifically, our method uses only 4% of the total input points (1,024) to reach > 89% and > 90% of success rate on ModelNet40 and ScanObjectNN respectively. We notice that our method performs consistently (in terms of both the attack rate and the number of points) on both synthetic and real-world datasets. The adversarial sink and adversarial stick in <cit.> respectively take the second place w.r.t. the success rate in point perturbation on ModelNet40 and ScanObjectNN. However, both of them require great numbers of points, especially the adversarial sink. The method in <cit.> is ranked third for its success rate but also incurs heavy point manipulations. In addition, we observe this method often generated obvious outliers, which could be detected easily by outlier removal methods. The saliency map-based attack method <cit.> and the one in <cit.> with random point selection require roughly 10× larger point sets than our method while achieving much lower success rates. The method in <cit.> with critical point selection shows relatively small number of points (though still more than our method), but the success rate is well below par. To further explore the performance trend, we plot the success rate over different numbers of points selected for point perturbation in Figure <ref>. As shown in the graphs, our method significantly outperforms existing ones with a small set of points.
  
  Experimental results also show that our method generates high-imperceptibility adversarial samples, evident by their Chamfer and Hausdorff distances to input point clouds (see Table <ref> & <ref>). We empirically observe that Hausdorff distance results in less outlier points than Chamfer distance.
  Figure <ref> qualitatively compares adversarial samples generated by our method and others. As shown, our method less likely produces outliers. This is due to the use of object perceptibility and minimal point set in our formula. We observe that, adversarial examples created from real-world data (see Figure <ref>(b)) are neither noticeable in perception nor distinguishable from common noise.
  
  
  
  
  
  
   §.§ Vulnerability Analysis
  
  
  
  Qi et al. <cit.> proposed a notion called “critical points” that characterise the shape of a point cloud. These points can be identified from the max pooling layer in PointNet <cit.>. It is also indicated in <cit.> that, critical points play role as an indicator for object recognition. Therefore, modification of critical points may lead to wrong classification results.
  
  We found that our adversarial generation algorithm could somehow reach those critical points. To confirm this, we measured the coincidence of our selected points and PointNet's critical points. Specifically, we counted the duplicates in the two point sets, and the number of our selected points found within the 5 nearest points of a critical point. Recall that our algorithm randomly initialises the selected points (i.e., the vector â in Eq. (<ref>)).  Figure <ref> provides the numerical data of this experiment. It is shown that about 50% of the selected points are identical to the critical points and 80% of the selected points are close to the critical points. Figure <ref> visualises our selected points and critical points. As shown, our selected points are close to critical points yet occupy a small portion, proving the capability of our method of finding compact yet vulnerable point sets.
  
  
  
  
  
  
  
  
  
  
  We also experimented our method with two additional initialisation schemes for the selected points: critical points-based initialisation and all point-based initialisation (i.e., taking all points in a point cloud to initialise the vector â). Table <ref> reports the performance of various initialisation schemes. As shown in the results, the critical points-based initialisation results in the least number of points but incurs the lowest success rate. Moreover, this scheme deteriorates the perceptibility of adversarial examples (as shown in the Chamfer distances). Utilising all points for initialisation shows the opposite, i.e., more points are selected but high success rate is achieved. Our initialisation scheme compromises all the criteria, i.e., adversarial examples are created with low number of points, high attack rate, and acceptable perceptibility. In addition, random initialisation can be applied to other networks which do not support critical points.
  
  
  
   §.§ Attack Performance to other Architectures
  
  
  We also applied our adversarial example generation algorithm to attack existing point cloud architectures other than PointNet. Those architectures include PointNet++ <cit.>,  DGCNN <cit.>, SpiderCNN <cit.>, and PointASNL <cit.>. 
  
  We report the attack performance of our method to these network architectures in Table <ref>. Amongst all the models, DGCNN <cit.> is shown to be the most robust one, which requires the greatest number of points to be fooled while maintaining low attack success rate. PointNet <cit.>, on the other hand, appears to be the most fragile model, which can be fooled easily with less points to achieve high success rate. The remaining models can be attacked by slightly different numbers of points. Table <ref> also shows that the attack performance of our method to a network architecture is consistent across both synthetic and real-world datasets.
  
  
  § CONCLUSION
  
  
  
  In this paper, we propose a unified  formulation for minimal adversarial 3D point clouds generation that can generalise two attack strategies including point perturbation and point addition. We experimented our method on benchmark datasets, and showed that existing point cloud neural networks, e.g., PointNet, are vulnerable to attacks that perturb only 4% of the points in a point cloud to reach more than 89% and 90% of success rate on synthetic and real-world data respectively. These results pose a  challenge in developing countermeasures to defend against such attacks. 
  
  With increasingly more 3D data used in consumer devices, we envision that adversarial attack and defense for point clouds will become diverse, making this topic worthy for future research. For example, in this paper, we only investigated attacks by perturbing point cloud coordinates. For real-world point clouds, color could be another vulnerable channel for adversarial attacks. Besides, it is important to study how to create adversarial point clouds in physical world. The results of our work show that such a task could be practical as only a few percentages of an input point cloud need to be modified. 
  
  
  Acknowledgment.
  Sai-Kit Yeung was partially supported by an internal grant from HKUST (R9429).
  
  
  ieee_fullname
  
  
  
  