randomized_encoder_unittest.cc | Explore in Territory

// Copyright 2018 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include <string_view>

#include "components/autofill/core/browser/randomized_encoder.h"
#include "base/numerics/safe_conversions.h"
#include "base/strings/stringprintf.h"
#include "components/autofill/core/common/signatures.h"
#include "components/unified_consent/pref_names.h"
#include "net/base/hex_utils.h"
#include "testing/gtest/include/gtest/gtest.h"

namespace {

constexpr size_t kBitsPerByte = …;
constexpr size_t kEncodedChunkLengthInBytes = …;
constexpr size_t kEncodedChunkLengthInBits = …;

// Get the |i|-th bit of |s| where |i| counts up from the 0-bit of the first
// character in |s|. It is expected that the caller guarantees that |i| is a
// valid bit-offset into |s|
bool GetBit(std::string_view s, size_t i) { … }

// This is a reference encoder implementation. This implementation performs the
// all bits encoding one full byte at a time and then packs the selected bits
// into a final output buffer.
std::string ReferenceEncodeImpl(std::string_view coins,
                                std::string_view noise,
                                std::string_view value,
                                size_t bit_offset,
                                size_t bit_stride) { … }

// A test version of the RandomizedEncoder class. Exposes "ForTest" methods.
class TestRandomizedEncoder : public autofill::RandomizedEncoder { … };

// Data structure used to drive the encoding test cases.
struct EncodeParams { … };

// A table to test cases, mapping encoding scheme to the reference encoder.
const EncodeParams kEncodeParams[] = …;

RandomizedEncoderTest;

}  // namespace

// As described in randomized_encoder.cc
// TODO(crbug.com/40570965): resolve circular dependency and remove
// hardcoded constant
TEST(RandomizedEncoderTest, CorrectUrlConsentFlag) { … }

TEST_P(RandomizedEncoderTest, Encode) { … }

TEST_P(RandomizedEncoderTest, EncodeLarge) { … }

INSTANTIATE_TEST_SUITE_P(…);

namespace {

// Data structure used to drive the decoding test cases.
struct DecodeParams { … };

// The fundamental idea of this algorithm is to count the number of reported 1s
// and 0s from a crowdsourced set of votes and look for a threshold that gives
// us confidence that we have seen enough 1s or 0s to assume that the actual
// value is a 1 or 0.
//
// Due to the symmetriy of the problem, we can conveniently choose the following
// null-hypothesis:
//
// N0: The true value of a bit is random on each pageload.
//
// In this case, we expect a binomial distribution B(n, 0.5), for which we can
// find a confidence interval that a sample of size n ends up in this interval.
// If a sample is outside of this interval, we can assume with the given
// confidence that we can reject the null-hypothesis and assume that the actual
// value is 0 or 1.
//
// For the confidence interval, we use the Wilson Score interval.
// https://en.wikipedia.org/wiki/Binomial_proportion_confidence_interval#Wilson_score_interval
//
// The confidence intervals are calculate as:
//
//   import scipy.stats as st
//   import math
//
//   def ConfidenceInterval(ph, n, confidence):
//     """
//     Args:
//       confidence: e.g. 0.95 for a 95% confidence
//       ph = p hat (see Wilson Score inverval link above)
//       n = number of samples
//     """
//     alpha = 1 - confidence
//     # for the 95% confidence interval this gives 1.96.
//     z = st.norm.ppf(1 - alpha/2)
//
//     base = (ph + z*z/(2*n)) / (1 + z*z/n)
//     offset = z / (1 + z*z/n) * math.sqrt(ph*(1-ph)/n + z*z/(4*n*n))
//
//     return [base - offset, base + offset]
//
// Note: The string being encoded/decoded for each "sample" consists of a common
// prefix followed by the decimal value of the sample number (i.e., "foo 25").
// Avoid test cases that skew the distribution of the appended noise to far
// from random (for example, using 0-199, more than 55% of the appended noise
// starts with the ASCII digit '1').
const DecodeParams kDecodeParams[] = …;

RandomizedDecoderTest;

// Generate a hex string representing the 128 bit value where each byte has
// value |i|. This lets us spread the seeds across the 128 bit space.
std::string Make128BitSeed(size_t i) { … }

}  // namespace

TEST(RandomizedEncoderTest, GetChunkCount) { … }

TEST_P(RandomizedDecoderTest, Decode) { … }

INSTANTIATE_TEST_SUITE_P(…);
chromium/components/autofill/core/browser/randomized_encoder_unittest.cc
