RAPPOR implementation

components/rappor/rappor_metric_unittest.cc

Index: components/rappor/rappor_metric_unittest.cc
diff --git a/components/rappor/rappor_metric_unittest.cc b/components/rappor/rappor_metric_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..fa55803b6540d68bc7972d147a09f0dfe9482010
--- /dev/null
+++ b/components/rappor/rappor_metric_unittest.cc
@@ -0,0 +1,112 @@
+// 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 "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 */
+};
+
+// Check for basic syntax and use.
+TEST(RapporMetricTest, BasicTest) {

[Alexei Svitkine (slow), 2014/01/21 18:14:04]

Nit: Keep all the TEST methods together (at the end), don't interleave with
other code or const params.

[Steven Holte, 2014/01/21 20:25:14]

Done.

+  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());
+}
+
+
+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 */
+};
+
+int CountBits(const ByteVector& v) {
+  int bit_count = 0;
+  for(size_t i = 0; i < v.size(); i++) {
+    uint8_t byte = v[i];
+    for (int j = 0; j < 8 ; j++) {
+      if(byte & 1 << j) {
+        bit_count++;
+      }
+    }
+  }
+  return bit_count;
+}
+
+TEST(RapporMetricTest, GetReportStatistical) {
+  RapporMetric metric(kTestStatsRapporParameters);
+
+  char sample[2] = "\0";
+  for (char i = 0; i < 50; i++) {
+    sample[0] = i;

[Alexei Svitkine (slow), 2014/01/21 18:14:04]

It's kind of weird to generate these non-human readable strings as samples...

I'd instead generate actual human readable strings instead to be more similar to
actual test data. Maybe via StringPrintf("%d", i). Or would that make the
assertions below harder to make?

[Steven Holte, 2014/01/21 20:25:14]

Done.

+    metric.AddSample(sample);
+  }
+  ByteVector real_bits = metric.bytes();
+  int real_bit_count = CountBits(real_bits);
+  EXPECT_EQ(real_bit_count, 149);
+
+  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(149, 0.65625) CDF(71) <= 0.000005
+  EXPECT_GT(true_from_true_count, 71);
+  // Binomial(149, 0.65625) CDF(122) <= 0.999995
+  EXPECT_LE(true_from_true_count, 122);
+
+  // Binomial(251, 0.59375) CDF(114) <= 0.000005
+  EXPECT_GT(true_from_false_count, 114);
+  // Binomial(251, 0.59375) CDF(183) <= 0.999995
+  EXPECT_LE(true_from_false_count, 183);
+}
+
+}  // namespace rappor