RAPPOR implementation

components/rappor/rappor_reporter.cc

+// Copyright (c) 2013 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 <assert.h>
+#include <limits.h>
+#include <math.h>
+
+#include <bitset>
+#include <map>
+#include <string>
+#include <vector>
+
+#include "base/logging.h"
+#include "base/strings/string_number_conversions.h"
+#include "components/rappor/bytevector.h"
+#include "components/rappor/rappor.h"
+#include "components/rappor/rappor_reporter.h"
+#include "crypto/hmac.h"
+#include "crypto/random.h"
+
+#define HMAC_SEED 10

[Alexei Svitkine (slow), 2013/12/19 19:47:02]

Use a const int in the anon namespace instead and follow kConstant naming
convention. Add a comment.

[Steven Holte, 2013/12/20 03:03:55]

Done.

+
+namespace rappor {
+
+namespace {
+
+// A utility object for generating random binary data with different
+// likelihood of bits being true.
+class ByteVectorGenerator {
+ public:
+  explicit ByteVectorGenerator(size_t byte_count);
+  // Generates a random byte vector where each bit is independently set with
+  // the given probability.
+  ByteVector GetWeightedRandomByteVector(Probability probability);
+
+ protected:
+  // Generates a random byte from a uniform distribution.
+  virtual uint8_t RandByte();
+
+ private:
+  // Generates a random vector of bytes from a uniform distribution.
+  ByteVector GetRandomByteVector();
+  size_t byte_count_;
+};
+
+ByteVectorGenerator::ByteVectorGenerator(size_t byte_count)
+    : byte_count_(byte_count) {}
+
+uint8_t ByteVectorGenerator::RandByte() {
+  uint8_t randomBits;
+  crypto::RandBytes(&randomBits, sizeof(uint8_t));
+  return randomBits;
+}
+
+ByteVector ByteVectorGenerator::GetRandomByteVector() {
+  ByteVector bytes(byte_count_);
+  for (size_t i = 0; i < byte_count_; i++) {
+    bytes[i] = RandByte();
+  }
+  return bytes;
+}
+
+ByteVector ByteVectorGenerator::GetWeightedRandomByteVector(
+    Probability probability) {
+  switch (probability) {
+    case PROBABILITY_87_5:
+      return GetRandomByteVector().Or(GetRandomByteVector()).Or(
+          GetRandomByteVector());
+    case PROBABILITY_75:
+      return GetRandomByteVector().Or(GetRandomByteVector());
+    case PROBABILITY_50:
+      return GetRandomByteVector();
+    case PROBABILITY_25:
+      return GetRandomByteVector().And(GetRandomByteVector());
+    case PROBABILITY_12_5:
+      return GetRandomByteVector().And(GetRandomByteVector()).And(
+          GetRandomByteVector());
+    default:
+      // Invalid probability for coin flips
+      abort();
+  }
+}
+
+// A ByteVectorGenerator that uses a psuedo-random function to generate
+// deterministicly random bits.
+class HmacByteVectorGenerator : public ByteVectorGenerator {
+ public:
+  HmacByteVectorGenerator(size_t byte_count, const std::string& secret);
+
+ protected:
+  virtual uint8_t RandByte();
+
+ private:
+  crypto::HMAC hmac_;
+  uint64_t hmac_state_;
+};
+
+HmacByteVectorGenerator::HmacByteVectorGenerator(size_t byte_count,
+                                                 const std::string& secret)
+    : ByteVectorGenerator(byte_count), hmac_(crypto::HMAC::SHA256) {
+  if (!hmac_.Init(secret)) {
+    abort();
+  };
+  assert(hmac_.DigestLength() > sizeof(uint64_t));
+  hmac_state_ = uint64_t(HMAC_SEED);
+}
+
+uint8_t HmacByteVectorGenerator::RandByte() {
+  uint8_t randomBits;

[Alexei Svitkine (slow), 2013/12/19 19:47:02]

Nit: random_bits

[Steven Holte, 2013/12/20 03:03:55]

Done.

+  std::string state = base::Uint64ToString(hmac_state_);
+  if (!hmac_.Sign(state, &randomBits, sizeof(uint8_t))) {
+    abort();
+  }
+  ++hmac_state_;
+  return randomBits;
+}
+
+}  // namespace
+
+RapporReporter::RapporReporter(const std::string& secret) : secret_(secret) {}
+
+std::vector<uint8_t> RapporReporter::GetReport(const Rappor& rappor) {
+  const ByteVector realbits(rappor.GetBytes());

[Alexei Svitkine (slow), 2013/12/19 19:47:02]

Nit: real_bits, use this naming convention throughout.

[Steven Holte, 2013/12/20 03:03:55]

Done.

+  size_t size = realbits.size();
+  HmacByteVectorGenerator hmacGenerator(

[Alexei Svitkine (slow), 2013/12/19 19:47:02]

Nit: hmac_generator

[Steven Holte, 2013/12/20 03:03:55]

Done.

+      size, secret_ + rappor.parameters()->rappor_name);
+  const ByteVector fakebits =
+      hmacGenerator.GetWeightedRandomByteVector(rappor.parameters()->fake_prob);
+  const ByteVector fakeones = hmacGenerator.GetWeightedRandomByteVector(
+      rappor.parameters()->fake_one_prob);
+  const ByteVector onebits =
+      (realbits.And(fakebits.Not())).Or(fakeones.And(fakebits));

[Alexei Svitkine (slow), 2013/12/19 19:47:02]

Nit: No need for outer ()'s.

[Steven Holte, 2013/12/20 03:03:55]

Done.

+
+  ByteVectorGenerator coinGenerator(size);
+  const ByteVector zero_coins = coinGenerator.GetWeightedRandomByteVector(
+      rappor.parameters()->zero_coin_prob);
+  const ByteVector one_coins = coinGenerator.GetWeightedRandomByteVector(
+      rappor.parameters()->one_coin_prob);
+  return (zero_coins.And(onebits.Not())).Or(one_coins.And(onebits));
+
+  return std::vector<uint8_t>();
+}
+
+}  // namespace rappor