privacy_math.cc | Explore in Territory

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

#include "components/attribution_reporting/privacy_math.h"

#include <stdint.h>

#include <algorithm>
#include <cmath>
#include <functional>
#include <iterator>
#include <limits>
#include <map>
#include <optional>
#include <utility>
#include <vector>

#include "base/check_op.h"
#include "base/notreached.h"
#include "base/numerics/byte_conversions.h"
#include "base/numerics/checked_math.h"
#include "base/numerics/safe_conversions.h"
#include "base/rand_util.h"
#include "base/ranges/algorithm.h"
#include "base/types/expected.h"
#include "base/types/expected_macros.h"
#include "components/attribution_reporting/attribution_scopes_data.h"
#include "components/attribution_reporting/event_report_windows.h"
#include "components/attribution_reporting/max_event_level_reports.h"
#include "components/attribution_reporting/source_type.mojom.h"
#include "components/attribution_reporting/trigger_config.h"
#include "components/attribution_reporting/trigger_data_matching.mojom.h"
#include "third_party/abseil-cpp/absl/types/variant.h"

namespace attribution_reporting {

namespace {

// Although the theoretical maximum number of trigger states exceeds 32 bits,
// we've chosen to only support a maximal trigger state cardinality of
// `UINT32_MAX` due to the randomized response generation rate being close
// enough to 1 for that number of states to not warrant the extra cost in
// resources for larger ints. The arithmetic in this file mostly adheres to that
// by way of overflow checking, with only certain exceptions applying. If the
// max trigger state cardinality is ever increased, the typings in this file
// must be changed to support that.

// Controls the max number of report states allowed for a given source
// registration.
uint32_t g_max_trigger_state_cardinality = …;

// Controls the max number bits of information that can be associated with
// a single source.
double g_max_channel_capacity_navigation = …;
double g_max_channel_capacity_scopes_navigation = …;
double g_max_channel_capacity_event = …;
double g_max_channel_capacity_scopes_event = …;

// Let B be the trigger data cardinality.
// For every trigger data i, there are wi windows and ci maximum reports.
// Let A[C, w1, ..., wB, c1, ..., cB] be the function which counts the number
// of output states.
//
// The following helper function memoizes the recurrence relation which computes
// this:
//
// 1. A[C,w1,...,wB,c1,...,cB] = 1 if B = 0
// If there are no trigger data types to consider, there is only one possible
// output, the null output.
//
// 2. A[C,w1,...,wB,c1,...,cB] = A[C,w1,...,w{B-1},c1,...,c{B-1}] if wB = 0
// If there are no windows to consider for a particular trigger data type, then
// consider only the remaining trigger data types.
//
// 3. A[C,w1,...,wB,c1,...,cB] = sum(A[C - j,w1,...,wB - 1,c1,...,cB - j],
//                                   for j from 0 to min(c_B, C))
// Otherwise, we look at the number of possible outputs assuming we emit some
// number of reports (up to the max) for the current trigger data type under
// consideration. Given that each choice produces a distinct output, we sum
// these up.
base::CheckedNumeric<uint32_t> GetNumStatesRecursive(TriggerSpecs::Iterator it,
                                                     int max_reports,
                                                     int window_val,
                                                     int max_reports_per_type,
                                                     internal::StateMap& map) { … }

// A variant of the above algorithm which samples a report given an index.
// This follows a similarly structured algorithm.
base::expected<void, RandomizedResponseError> GetReportsFromIndexRecursive(
    TriggerSpecs::Iterator it,
    int max_reports,
    int window_val,
    int max_reports_per_type,
    uint32_t index,
    std::vector<FakeEventLevelReport>& reports,
    internal::StateMap& map) { … }

base::expected<uint32_t, RandomizedResponseError> GetNumStatesCached(
    const TriggerSpecs& specs,
    internal::StateMap& map) { … }

}  // namespace

RandomizedResponseData::RandomizedResponseData(double rate,
                                               RandomizedResponse response)
    : … { … }

RandomizedResponseData::~RandomizedResponseData() = default;

RandomizedResponseData::RandomizedResponseData(const RandomizedResponseData&) =
    default;

RandomizedResponseData& RandomizedResponseData::operator=(
    const RandomizedResponseData&) = default;

RandomizedResponseData::RandomizedResponseData(RandomizedResponseData&&) =
    default;

RandomizedResponseData& RandomizedResponseData::operator=(
    RandomizedResponseData&&) = default;

uint32_t MaxTriggerStateCardinality() { … }

double GetMaxChannelCapacity(mojom::SourceType source_type) { … }

double GetMaxChannelCapacityScopes(mojom::SourceType source_type) { … }

bool GenerateWithRate(double r) { … }

double GetRandomizedResponseRate(uint32_t num_states, double epsilon) { … }

base::expected<uint32_t, RandomizedResponseError> GetNumStates(
    const TriggerSpecs& specs) { … }

base::expected<RandomizedResponseData, RandomizedResponseError>
DoRandomizedResponse(const TriggerSpecs& specs,
                     double epsilon,
                     mojom::SourceType source_type,
                     const std::optional<AttributionScopesData>& scopes_data) { … }

bool IsValid(const RandomizedResponse& response, const TriggerSpecs& specs) { … }

namespace internal {

base::CheckedNumeric<uint32_t> BinomialCoefficient(int n, int k) { … }

// Computes the `combination_index`-th lexicographically smallest k-combination.
// https://en.wikipedia.org/wiki/Combinatorial_number_system

// A k-combination is a sequence of k non-negative integers in decreasing order.
// a_k > a_{k-1} > ... > a_2 > a_1 >= 0.
// k-combinations can be ordered lexicographically, with the smallest
// k-combination being a_k=k-1, a_{k-1}=k-2, .., a_1=0. Given an index
// `combination_index`>=0, and an order k, this method returns the
// `combination_index`-th smallest k-combination.
//
// Given an index `combination_index`, the `combination_index`-th k-combination
// is the unique set of k non-negative integers
// a_k > a_{k-1} > ... > a_2 > a_1 >= 0
// such that `combination_index` = \sum_{i=1}^k {a_i}\choose{i}
//
// We find this set via a simple greedy algorithm.
// http://math0.wvstateu.edu/~baker/cs405/code/Combinadics.html
std::vector<int> GetKCombinationAtIndex(
    base::StrictNumeric<uint32_t> combination_index,
    int k) { … }

base::expected<std::vector<FakeEventLevelReport>, RandomizedResponseError>
GetFakeReportsForSequenceIndex(const TriggerSpecs& specs,
                               base::StrictNumeric<uint32_t> index,
                               StateMap& map) { … }

base::CheckedNumeric<uint32_t> GetNumberOfStarsAndBarsSequences(int num_stars,
                                                                int num_bars) { … }

base::expected<std::vector<int>, absl::monostate> GetStarIndices(
    int num_stars,
    int num_bars,
    base::StrictNumeric<uint32_t> sequence_index) { … }

std::vector<int> GetBarsPrecedingEachStar(std::vector<int> out) { … }

double BinaryEntropy(double p) { … }

double ComputeChannelCapacity(
    const base::StrictNumeric<uint32_t> num_states_strict,
    const double randomized_response_rate) { … }

double ComputeChannelCapacityScopes(
    const base::StrictNumeric<uint32_t> num_states,
    const uint32_t max_event_states,
    const uint32_t attribution_scope_limit) { … }

base::expected<std::vector<FakeEventLevelReport>, RandomizedResponseError>
GetFakeReportsForSequenceIndex(
    const TriggerSpecs& specs,
    base::StrictNumeric<uint32_t> random_stars_and_bars_sequence_index) { … }

base::expected<RandomizedResponseData, RandomizedResponseError>
DoRandomizedResponseWithCache(
    const TriggerSpecs& specs,
    double epsilon,
    StateMap& map,
    mojom::SourceType source_type,
    const std::optional<AttributionScopesData>& scopes_data) { … }

}  // namespace internal

ScopedMaxTriggerStateCardinalityForTesting::
    ScopedMaxTriggerStateCardinalityForTesting(
        uint32_t max_trigger_state_cardinality)
    : … { … }

ScopedMaxTriggerStateCardinalityForTesting::
    ~ScopedMaxTriggerStateCardinalityForTesting() { … }

ScopedMaxNavigationChannelCapacityForTesting::
    ScopedMaxNavigationChannelCapacityForTesting(
        double max_navigation_channel_capacity)
    : … { … }

ScopedMaxNavigationChannelCapacityForTesting::
    ~ScopedMaxNavigationChannelCapacityForTesting() { … }

ScopedMaxEventChannelCapacityForTesting::
    ScopedMaxEventChannelCapacityForTesting(double max_event_channel_capacity)
    : … { … }

ScopedMaxEventChannelCapacityForTesting::
    ~ScopedMaxEventChannelCapacityForTesting() { … }

ScopedMaxScopesNavigationChannelCapacityForTesting::
    ScopedMaxScopesNavigationChannelCapacityForTesting(
        double max_scoped_navigation_channel_capacity)
    : … { … }

ScopedMaxScopesNavigationChannelCapacityForTesting::
    ~ScopedMaxScopesNavigationChannelCapacityForTesting() { … }

ScopedMaxScopesEventChannelCapacityForTesting::
    ScopedMaxScopesEventChannelCapacityForTesting(
        double max_scoped_event_channel_capacity)
    : … { … }

ScopedMaxScopesEventChannelCapacityForTesting::
    ~ScopedMaxScopesEventChannelCapacityForTesting() { … }

}  // namespace attribution_reporting
chromium/components/attribution_reporting/privacy_math.cc
