RAPPOR implementation

components/rappor/rappor_metric_unittest.cc

+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "components/rappor/rappor_metric.h"
+
+#include <stdlib.h>
+
+#include "base/rand_util.h"
+#include "base/strings/stringprintf.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace rappor {
+
+const RapporParameters kTestRapporParameters = {
+    "MyRappor",
+    16 /* Bloom filter size bytes */,
+    4 /* Bloom filter hash count */,
+    PROBABILITY_75 /* Fake data probability */,
+    PROBABILITY_50 /* Fake one probability */,
+    PROBABILITY_75 /* One coin probability */,
+    PROBABILITY_50 /* Zero coin probability */
+};
+
+const RapporParameters kTestStatsRapporParameters = {
+    "MyStatsRappor",
+    50 /* Bloom filter size bytes */,
+    4 /* Bloom filter hash count */,
+    PROBABILITY_75 /* Fake data probability */,
+    PROBABILITY_50 /* Fake one probability */,
+    PROBABILITY_75 /* One coin probability */,
+    PROBABILITY_50 /* Zero coin probability */
+};
+
+// Check for basic syntax and use.
+TEST(RapporMetricTest, BasicTest) {
+  RapporMetric testMetric(kTestRapporParameters);
+  testMetric.AddSample("Foo");
+  testMetric.AddSample("Bar");
+  EXPECT_EQ(0x20, testMetric.bytes()[1]);
+}
+
+TEST(RapporMetricTest, GetReportTest) {
+  RapporMetric metric(kTestRapporParameters);
+
+  ByteVector report = metric.GetReport("MySecret");
+  EXPECT_EQ(16u, report.size());
+}
+
+TEST(RapporMetricTest, GetReportStatistical) {
+  RapporMetric metric(kTestStatsRapporParameters);
+
+  for (char i = 0; i < 50; i++) {
+    metric.AddSample(base::StringPrintf("%d", i));
+  }
+  ByteVector real_bits = metric.bytes();
+  int real_bit_count = CountBits(real_bits);
+  EXPECT_EQ(real_bit_count, 153);
+
+  std::string secret = base::RandBytesAsString(128);
+  ByteVector report = metric.GetReport(secret);
+
+  // For the bits we actually set in the bloom filter, get a count of how
+  // many of them reported true.
+  ByteVector from_true_reports = report;
+  // Real bits AND report bits.
+  ByteVectorMerge(real_bits, real_bits, &from_true_reports);
+  int true_from_true_count = CountBits(from_true_reports);
+
+  // For the bits we didn't set in the bloom filter, get a count of how
+  // many of them reported true.
+  ByteVector from_false_reports = report;
+  ByteVectorOr(real_bits, &from_false_reports);
+  int true_from_false_count = CountBits(from_false_reports) - real_bit_count;
+
+  // The probability of a true bit being true after redaction =
+  //   [fake_prob]*[fake_true_prob] + (1-[fake_prob]) =
+  //   .75 * .5 + (1-.75) = .625
+  // The probablity of a false bit being true after redaction =
+  //   [fake_prob]*[fake_true_prob] = .375
+  // The probability of a bit reporting true =
+  //   [redacted_prob] * .75 + (1-[redacted_prob] * .5) =
+  //   0.65625 for true bits
+  //   0.59375 for false bits
+
+  // Binomial(153, 0.65625) CDF(74) <= 0.000005
+  EXPECT_GT(true_from_true_count, 74);
+  // Binomial(153, 0.65625) CDF(125) <= 0.999995
+  EXPECT_LE(true_from_true_count, 125);
+
+  // Binomial(247, 0.59375) CDF(112) <= 0.000005
+  EXPECT_GT(true_from_false_count, 112);
+  // Binomial(247, 0.59375) CDF(180) <= 0.999995
+  EXPECT_LE(true_from_false_count, 180);
+}
+
+}  // namespace rappor