| // |
| // Copyright 2020 Google LLC |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| // |
| |
| package com.google.privacy.differentialprivacy; |
| |
| import static com.google.common.truth.Truth.assertThat; |
| import static com.google.privacy.differentialprivacy.proto.SummaryOuterClass.MechanismType.LAPLACE; |
| import static org.junit.Assert.assertThrows; |
| |
| import com.google.common.collect.ImmutableList; |
| import com.google.common.math.Stats; |
| import com.google.testing.junit.testparameterinjector.TestParameterInjector; |
| import com.google.testing.junit.testparameterinjector.TestParameters; |
| import java.security.SecureRandom; |
| import org.junit.Test; |
| import org.junit.runner.RunWith; |
| |
| @RunWith(TestParameterInjector.class) |
| public final class LaplaceNoiseTest { |
| private static final LaplaceNoise NOISE = new LaplaceNoise(); |
| private static final int NUM_SAMPLES = 100000; |
| private static final double LN_3 = Math.log(3); |
| private static final double DEFAULT_X = 0.0; |
| private static final double DEFAULT_EPSILON = LN_3; |
| private static final int DEFAULT_L_0_SENSITIVITY = 1; |
| private static final double DEFAULT_L_INF_SENSITIVITY = 1.0; |
| |
| /** Returns variance of Laplace noise for given parameters. */ |
| double getVariance(double epsilon, int l0sensitivty, double lInfSensitivty) { |
| double l1Sensitivity = l0sensitivty * lInfSensitivty; |
| return 2 * Math.pow(l1Sensitivity / epsilon, 2); |
| } |
| |
| @Test |
| public void addNoise_hasAccurateStatisticalProperties() { |
| ImmutableList.Builder<Double> samples = ImmutableList.builder(); |
| for (int i = 0; i < NUM_SAMPLES; i++) { |
| samples.add( |
| NOISE.addNoise( |
| DEFAULT_X, |
| DEFAULT_L_0_SENSITIVITY, |
| DEFAULT_L_INF_SENSITIVITY, |
| DEFAULT_EPSILON, |
| /* delta= */ null)); |
| } |
| Stats stats = Stats.of(samples.build()); |
| |
| double variance = |
| getVariance(DEFAULT_EPSILON, DEFAULT_L_0_SENSITIVITY, DEFAULT_L_INF_SENSITIVITY); |
| // The tolerance is chosen according to the 99.9995% quantile of the anticipated distributions |
| // of the sample mean and variance. Thus, the test falsely rejects with a probability of 10^-5. |
| double sampleMeanTolerance = 4.41717 * Math.sqrt(variance / NUM_SAMPLES); |
| double sampleVarianceTolerance = 4.41717 * Math.sqrt(5.0 * variance * variance / NUM_SAMPLES); |
| assertThat(stats.mean()).isWithin(sampleMeanTolerance).of(DEFAULT_X); |
| assertThat(stats.populationVariance()).isWithin(sampleVarianceTolerance).of(variance); |
| } |
| |
| @Test |
| public void addNoise_differentX_hasAccurateStatisticalProperties() { |
| ImmutableList.Builder<Double> samples = ImmutableList.builder(); |
| for (int i = 0; i < NUM_SAMPLES; i++) { |
| samples.add( |
| NOISE.addNoise( |
| /* x= */ 42.0, |
| DEFAULT_L_0_SENSITIVITY, |
| DEFAULT_L_INF_SENSITIVITY, |
| DEFAULT_EPSILON, |
| /* delta= */ null)); |
| } |
| Stats stats = Stats.of(samples.build()); |
| |
| double mean = 42.0; |
| double variance = |
| getVariance(DEFAULT_EPSILON, DEFAULT_L_0_SENSITIVITY, DEFAULT_L_INF_SENSITIVITY); |
| // The tolerance is chosen according to the 99.9995% quantile of the anticipated distributions |
| // of the sample mean and variance. Thus, the test falsely rejects with a probability of 10^-5. |
| double sampleMeanTolerance = 4.41717 * Math.sqrt(variance / NUM_SAMPLES); |
| double sampleVarianceTolerance = 4.41717 * Math.sqrt(5.0 * variance * variance / NUM_SAMPLES); |
| assertThat(stats.mean()).isWithin(sampleMeanTolerance).of(mean); |
| assertThat(stats.populationVariance()).isWithin(sampleVarianceTolerance).of(variance); |
| } |
| |
| @Test |
| public void addNoise_differentSensitivity_hasAccurateStatisticalProperties() { |
| ImmutableList.Builder<Double> samples = ImmutableList.builder(); |
| for (int i = 0; i < NUM_SAMPLES; i++) { |
| samples.add( |
| NOISE.addNoise( |
| DEFAULT_X, |
| DEFAULT_L_0_SENSITIVITY, |
| /* lInfSensitivity= */ 0.5, |
| DEFAULT_EPSILON, |
| /* delta= */ null)); |
| } |
| Stats stats = Stats.of(samples.build()); |
| |
| double variance = getVariance(DEFAULT_EPSILON, DEFAULT_L_0_SENSITIVITY, 0.5); |
| // The tolerance is chosen according to the 99.9995% quantile of the anticipated distributions |
| // of the sample mean and variance. Thus, the test falsely rejects with a probability of 10^-5. |
| double sampleMeanTolerance = 4.41717 * Math.sqrt(variance / NUM_SAMPLES); |
| double sampleVarianceTolerance = 4.41717 * Math.sqrt(5.0 * variance * variance / NUM_SAMPLES); |
| assertThat(stats.mean()).isWithin(sampleMeanTolerance).of(DEFAULT_X); |
| assertThat(stats.populationVariance()).isWithin(sampleVarianceTolerance).of(variance); |
| } |
| |
| @Test |
| public void addNoise_differentEpsilon_hasAccurateStatisticalProperties() { |
| ImmutableList.Builder<Double> samples = ImmutableList.builder(); |
| for (int i = 0; i < NUM_SAMPLES; i++) { |
| samples.add( |
| NOISE.addNoise( |
| DEFAULT_X, |
| DEFAULT_L_0_SENSITIVITY, |
| DEFAULT_L_INF_SENSITIVITY, |
| /* epsilon= */ 2 * LN_3, |
| /* delta= */ null)); |
| } |
| Stats stats = Stats.of(samples.build()); |
| |
| double variance = getVariance(2 * LN_3, DEFAULT_L_0_SENSITIVITY, DEFAULT_L_INF_SENSITIVITY); |
| // The tolerance is chosen according to the 99.9995% quantile of the anticipated distributions |
| // of the sample mean and variance. Thus, the test falsely rejects with a probability of 10^-5. |
| double sampleMeanTolerance = 4.41717 * Math.sqrt(variance / NUM_SAMPLES); |
| double sampleVarianceTolerance = 4.41717 * Math.sqrt(5.0 * variance * variance / NUM_SAMPLES); |
| assertThat(stats.mean()).isWithin(sampleMeanTolerance).of(DEFAULT_X); |
| assertThat(stats.populationVariance()).isWithin(sampleVarianceTolerance).of(variance); |
| } |
| |
| @Test |
| public void addNoise_integralX_hasAccurateStatisticalProperties() { |
| ImmutableList.Builder<Long> samples = ImmutableList.builder(); |
| for (int i = 0; i < NUM_SAMPLES; i++) { |
| samples.add( |
| NOISE.addNoise( |
| /* x= */ 0L, |
| DEFAULT_L_0_SENSITIVITY, |
| /* lInfSensitivity= */ 1L, |
| DEFAULT_EPSILON, |
| /* delta= */ null)); |
| } |
| Stats stats = Stats.of(samples.build()); |
| |
| double mean = 0.0; |
| double approxVariance = getVariance(DEFAULT_EPSILON, DEFAULT_L_0_SENSITIVITY, 1); |
| // The tolerance is chosen according to the 99.9995% quantile of the anticipated distributions |
| // of the sample mean and variance. Thus, the test falsely rejects with a probability of 10^-5. |
| double sampleMeanTolerance = 4.41717 * Math.sqrt(approxVariance / NUM_SAMPLES); |
| assertThat(stats.mean()).isWithin(sampleMeanTolerance).of(mean); |
| // Not testing for the variance because it is not clear what variance should be expected. |
| } |
| |
| @Test |
| public void addNoise_epsilonTooSmall_throwsException() { |
| assertThrows( |
| IllegalArgumentException.class, |
| () -> |
| NOISE.addNoise( |
| DEFAULT_X, |
| DEFAULT_L_0_SENSITIVITY, |
| DEFAULT_L_INF_SENSITIVITY, |
| /* epsilon= */ 1.0 / (1L << 51), |
| /* delta= */ null)); |
| } |
| |
| @Test |
| public void addNoise_epsilonPosInfinity_throwsException() { |
| assertThrows( |
| IllegalArgumentException.class, |
| () -> |
| NOISE.addNoise( |
| DEFAULT_X, |
| DEFAULT_L_0_SENSITIVITY, |
| DEFAULT_L_INF_SENSITIVITY, |
| /* epsilon= */ Double.POSITIVE_INFINITY, |
| /* delta= */ null)); |
| } |
| |
| @Test |
| public void addNoise_epsilonNan_throwsException() { |
| assertThrows( |
| IllegalArgumentException.class, |
| () -> |
| NOISE.addNoise( |
| DEFAULT_X, |
| DEFAULT_L_0_SENSITIVITY, |
| DEFAULT_L_INF_SENSITIVITY, |
| /* epsilon= */ Double.NaN, |
| /* delta= */ null)); |
| } |
| |
| @Test |
| public void addNoise_deltaNonnul_throwsException() { |
| assertThrows( |
| IllegalArgumentException.class, |
| () -> |
| NOISE.addNoise( |
| DEFAULT_X, |
| DEFAULT_L_0_SENSITIVITY, |
| DEFAULT_L_INF_SENSITIVITY, |
| DEFAULT_EPSILON, |
| /* delta= */ 0.0)); |
| } |
| |
| @Test |
| public void addNoise_lInfSensitivityTooHigh_throwsException() { |
| assertThrows( |
| IllegalArgumentException.class, |
| () -> |
| NOISE.addNoise( |
| DEFAULT_X, |
| DEFAULT_L_0_SENSITIVITY, |
| /* lInfSensitivity= */ Double.MAX_VALUE, |
| DEFAULT_EPSILON, |
| /* delta= */ null)); |
| } |
| |
| @Test |
| public void addNoise_lInfSensitivityNan_throwsException() { |
| assertThrows( |
| IllegalArgumentException.class, |
| () -> |
| NOISE.addNoise( |
| DEFAULT_X, |
| DEFAULT_L_0_SENSITIVITY, |
| /* lInfSensitivity= */ Double.NaN, |
| /* epsilon= */ 1.0, |
| /* delta= */ null)); |
| } |
| |
| @Test |
| public void addNoise_lInfSensitivityNegative_throwsException() { |
| assertThrows( |
| IllegalArgumentException.class, |
| () -> |
| NOISE.addNoise( |
| DEFAULT_X, |
| DEFAULT_L_0_SENSITIVITY, |
| /* lInfSensitivity= */ -1.0, |
| DEFAULT_EPSILON, |
| /* delta= */ null)); |
| } |
| |
| @Test |
| public void addNoise_lInfSensitivityZero_throwsException() { |
| assertThrows( |
| IllegalArgumentException.class, |
| () -> |
| NOISE.addNoise( |
| DEFAULT_X, |
| DEFAULT_L_0_SENSITIVITY, |
| /* lInfSensitivity= */ 0.0, |
| DEFAULT_EPSILON, |
| /* delta= */ null)); |
| } |
| |
| @Test |
| public void addNoise_l0SensitivityNegative_throwsException() { |
| assertThrows( |
| IllegalArgumentException.class, |
| () -> |
| NOISE.addNoise( |
| DEFAULT_X, |
| /* l0Sensitivity= */ -1, |
| DEFAULT_L_INF_SENSITIVITY, |
| DEFAULT_EPSILON, |
| /* delta= */ null)); |
| } |
| |
| @Test |
| public void addNoise_l0SensitivityZero_throwsException() { |
| assertThrows( |
| IllegalArgumentException.class, |
| () -> |
| NOISE.addNoise( |
| DEFAULT_X, |
| /* l0Sensitivity= */ 0, |
| DEFAULT_L_INF_SENSITIVITY, |
| DEFAULT_EPSILON, |
| /* delta= */ null)); |
| } |
| |
| @Test |
| public void addNoise_l1SensitivityNegative_throwsException() { |
| assertThrows( |
| IllegalArgumentException.class, |
| () -> |
| NOISE.addNoise( |
| DEFAULT_X, /* l1Sensitivity= */ -1.0, DEFAULT_EPSILON, /* delta= */ null)); |
| } |
| |
| @Test |
| public void addNoise_l1SensitivityZero_throwsException() { |
| assertThrows( |
| IllegalArgumentException.class, |
| () -> |
| NOISE.addNoise( |
| DEFAULT_X, /* l1Sensitivity= */ 0.0, DEFAULT_EPSILON, /* delta= */ null)); |
| } |
| |
| @Test |
| public void addNoise_l1SensitivityNan_throwsException() { |
| assertThrows( |
| IllegalArgumentException.class, |
| () -> |
| NOISE.addNoise( |
| DEFAULT_X, /* l1Sensitivity= */ Double.NaN, DEFAULT_EPSILON, /* delta= */ null)); |
| } |
| |
| @Test |
| public void addNoise_returnsMultipleOfGranularity() { |
| SecureRandom random = new SecureRandom(); |
| for (int i = 0; i < NUM_SAMPLES; i++) { |
| // The rounding pricess should be independent of the value of x. Set x to a value between |
| // -1*10^6 and 10^6 at random should covere a broad range of congruence classes. |
| double x = random.nextDouble() * 2000000.0 - 1000000.0; |
| |
| // The following choice of epsilon, l0 sensitivity and linf sensitivity should result in a |
| // granularity of 2^-10 |
| double noisedX = |
| NOISE.addNoise( |
| x, |
| /* l0Sensitivity= */ 1, |
| /* lInfSensitivity= */ 1.0, |
| /* epsilon= */ 4.7e-10, |
| /* delta= */ null); |
| assertThat(Math.floor(noisedX * 1024.0)).isEqualTo(noisedX * 1024.0); |
| |
| // The following choice of epsilon, l0 sensitivity and linf sensitivity should result in a |
| // granularity of 2^0 |
| noisedX = |
| NOISE.addNoise( |
| x, |
| /* l0Sensitivity= */ 1, |
| /* lInfSensitivity= */ 1.0, |
| /* epsilon= */ 9.1e-13, |
| /* delta= */ null); |
| assertThat(Math.floor(noisedX)).isEqualTo(noisedX); |
| |
| // The following choice of epsilon, l0 sensitivity and linf sensitivity should result in a |
| // granularity of 2^10 |
| noisedX = |
| NOISE.addNoise( |
| x, |
| /* l0Sensitivity= */ 1, |
| /* lInfSensitivity= */ 1.0, |
| /* epsilon= */ 8.9e-16, |
| /* delta= */ null); |
| assertThat(Math.floor(noisedX / 1024.0)).isEqualTo(noisedX / 1024.0); |
| } |
| } |
| |
| @Test |
| public void addNoise_integralX_returnsMultipleOfGranularity() { |
| SecureRandom random = new SecureRandom(); |
| for (int i = 0; i < NUM_SAMPLES; i++) { |
| // The rounding pricess should be independent of the value of x. Set x to a value between |
| // -1*10^6 and 10^6 at random should covere a broad range of congruence classes. |
| long x = (long) random.nextInt(2000000) - 1000000; |
| |
| // The following choice of epsilon, l0 sensitivity and linf sensitivity should result in a |
| // granularity of 2^1 |
| long noisedX = |
| NOISE.addNoise( |
| x, |
| /* l0Sensitivity= */ 1, |
| /* lInfSensitivity= */ 1, |
| /* epsilon= */ 4.6e-13, |
| /* delta= */ null); |
| assertThat(noisedX % 2).isEqualTo(0); |
| |
| // The following choice of epsilon, l0 sensitivity and linf sensitivity should result in a |
| // granularity of 2^10 |
| noisedX = |
| NOISE.addNoise( |
| x, |
| /* l0Sensitivity= */ 1, |
| /* lInfSensitivity= */ 1, |
| /* epsilon= */ 8.9e-16, |
| /* delta= */ null); |
| assertThat(noisedX % 1024).isEqualTo(0); |
| } |
| } |
| |
| @Test |
| public void getMechanismType_returnsLaplace() { |
| assertThat(NOISE.getMechanismType()).isEqualTo(LAPLACE); |
| } |
| |
| @Test |
| // quantile < mean |
| @TestParameters("{quantile: 0.6, mean: 1.0, l1Sensitivity: 4.9, epsilon: 2.7}") |
| // quantile > mean |
| @TestParameters("{quantile: 4.2, mean: 1.8, l1Sensitivity: 3.6, epsilon: 8.0}") |
| public void computeQuantile_inverseToCumulativeDensity( |
| double quantile, double mean, double l1Sensitivity, double epsilon) { |
| double actualQuantile = |
| LaplaceNoise.computeQuantile( |
| LaplaceNoise.cumulativeDensity(quantile, mean, l1Sensitivity, epsilon), |
| mean, |
| l1Sensitivity, |
| epsilon); |
| |
| assertThat(actualQuantile).isWithin(1e-10).of(quantile); |
| } |
| |
| @Test |
| // rank < 0.5 |
| @TestParameters("{rank: 0.2, mean: 7.7, l1Sensitivity: 1.3, epsilon: 0.8}") |
| // rank > 0.5 |
| @TestParameters("{rank: 0.9, mean: 9.2, l1Sensitivity: 6.6, epsilon: 2.7}") |
| public void cumulativeDensity_inverseToQuantile( |
| double rank, double mean, double l1Sensitivity, double epsilon) { |
| double actualRank = |
| LaplaceNoise.cumulativeDensity( |
| LaplaceNoise.computeQuantile(rank, mean, l1Sensitivity, epsilon), |
| mean, |
| l1Sensitivity, |
| epsilon); |
| |
| assertThat(actualRank).isWithin(1e-10).of(rank); |
| } |
| |
| @Test |
| // z < mean |
| @TestParameters("{z: -0.1, mean: 0.6, l1Sensitivity: 0.8, epsilon: 1.1, expectedP: 0.1909684}") |
| // z == mean |
| @TestParameters("{z: 4.2, mean: 4.2, l1Sensitivity: 6.1, epsilon: 1.5, expectedP: 0.5}") |
| // z > mean |
| @TestParameters("{z: 2.1, mean: 0.3, l1Sensitivity: 7.7, epsilon: 2.7, expectedP: 0.7340152}") |
| public void cumulativeDensity_sampleValues_computesCorrectly( |
| double z, double mean, double l1Sensitivity, double epsilon, double expectedP) { |
| double actualP = LaplaceNoise.cumulativeDensity(z, mean, l1Sensitivity, epsilon); |
| |
| assertThat(actualP).isWithin(1e-6).of(expectedP); |
| } |
| } |