random_sphere() samples points in the ball (not on the sphere)

[Framartin]

Describe the bug The name and documentation of the function art.utils.random_sphere() suggest that the function samples points on the Lp-sphere, but it samples points in the Lp-ball.

To Reproduce Steps to reproduce the behavior:

1. Sample N points in D dimensions using art.utils.random_sphere
2. Compute their p-norm

import numpy as np
from art.utils import random_sphere
d=10
for p in [1, 2, np.inf]:
    points = random_sphere(nb_points=5, nb_dims=d, radius=10, norm=p)
    norm = np.linalg.norm(points, ord=p, axis=1)
    print(f'{p}-norm of {d}-dim points: {norm}')
# 1-norm of 10-dim points: [1.90252354 7.96682405 9.87868038 2.48234154 4.31938079]
# 2-norm of 10-dim points: [9.5777607  7.62736975 9.69089633 8.89324436 9.77982516]
# inf-norm of 10-dim points: [8.13604454 9.64728559 9.98291139 9.81341037 9.71205873]

I do agree that in high dimension, the issue becomes negligible for the 2 and inf norms, but it is not for the 1-norm.

# 1-norm of 10000-dim points: [8.84152977 5.19254224 7.03462032 1.38944847 6.84087878]
# 2-norm of 10000-dim points: [9.99832332 9.99853434 9.99970224 9.99974475 9.99949171]
# inf-norm of 10000-dim points: [9.99979021 9.99997746 9.99857432 9.99995599 9.99925035]

Expected behavior I expect the p-norm of all points to be equal to radius.

System information (please complete the following information):

• OS: any
• Python version: 3.8.8
• ART version or commit number: 1.11.0

[beat-buesser]

Hi @Framartin Thank you very much for raising this issue and the code to reproduce your results!

@nmegiddo What do you think?

[nmegiddo]

I am not sure what the intended use of this function is, but it clearly produces points in the ball rather than on the sphere. The question is what to do: Change the name of the function to random_ball? Change the code so it produces points on the sphere? Both can creates problems.

Further comments:

1. The inf-norm is the most transparent case:
   res = np.random.uniform(-radius, radius, (nb_points, nb_dims)) means a uniform distribution on the ball. As the dimension increases, the maximum tends to the radius, hence the sample point is approaches the sphere with high probability.
2. I suspect the 1-norm code does not produce a uniform distribution on the L1-ball. The sample here should also approach the boundary with high probability as the dimension increases.

[beat-buesser]

@nmegiddo Thank you very much!

@Framartin I think the intended application was sampling inside the norm-ball and that the docstring needs to be updated accordingly. Do you have a specific application for random samples on the surface?

[Framartin]

Thank you so much for your nice and quick replies!

I agree that the easiest would be to update the docstring. And I think that the current behaviour is correct for most attacks, like the random init of PGD which should be done uniformly in the Lp ball.

@nmegiddo I agree with your point that the code might not produce a uniform distribution in the L1-ball. My guess is that the radius sampled line 549 is only correct in 2D. But it is not in other dimensions. My intuition is that the square and square root functions should be replaced respectively by the d-power and d-th root functions to keep the proportionality between the probability of a hypercube and its volume. But I did not prove it. https://github.com/Trusted-AI/adversarial-robustness-toolbox/blob/main/art/utils.py#L549

@beat-buesser I was thinking of implementing a simple brute-force attack, i.e., sampling randomly in the ball/sphere. It is a sanity check recommanded by "On Evaluating Adversarial Robustness" (section 4.11). I guess it would make more sense to sample uniformly on the sphere than in the ball, to better control the size of perturbations. But I might be wrong. Anyway, in high dimensions, random samples should be almost on the sphere with high probability.

[beat-buesser]

@Framartin I think that's a great idea to implement the sanity check as evasion attack in ART. Would you be interested to implement it (but no pressure to say yes)?

We could extend the random_sphere function with an option to sample only on the surface and I think it would be good to have accurate sampling/numbers also in low dimensions.

[Framartin]

@nmegiddo #1800 should fix the sampling in the L1 ball. Could you check that my fix is correct? Thanks :)

@beat-buesser Yes, I will try to implement a brute force attack in the following weeks :) I have a draft version on my side, but I need to clean first.

I agree that adding an option to sample on the sphere would be useful. However, I don't have time to do it at this moment.