1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190
|
// Copyright 2021 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "chrome/browser/privacy_budget/surface_set_with_valuation.h"
#include <cstddef>
#include "base/containers/contains.h"
#include "chrome/browser/privacy_budget/surface_set_equivalence.h"
#include "chrome/browser/privacy_budget/surface_set_valuation.h"
#include "chrome/common/privacy_budget/scoped_privacy_budget_config.h"
#include "chrome/common/privacy_budget/types.h"
#include "testing/gtest/include/gtest/gtest.h"
#include "third_party/blink/public/common/privacy_budget/identifiable_surface.h"
namespace {
constexpr auto kSurface1 = blink::IdentifiableSurface::FromTypeAndToken(
blink::IdentifiableSurface::Type::kCanvasRenderingContext,
3);
constexpr auto kSurface2 = blink::IdentifiableSurface::FromTypeAndToken(
blink::IdentifiableSurface::Type::kHTMLMediaElement_CanPlayType,
5);
// Usual budgets range from 20..40.
constexpr PrivacyBudgetCost kDefaultMediumBudget = 30.0;
struct ScopedValuation {
ScopedValuation()
: study_configuration(
test::ScopedPrivacyBudgetConfig::Presets::kEnableRandomSampling),
valuation(equivalence) {}
explicit ScopedValuation(
test::ScopedPrivacyBudgetConfig::Parameters parameters)
: study_configuration(parameters), valuation(equivalence) {}
test::ScopedPrivacyBudgetConfig study_configuration;
SurfaceSetEquivalence equivalence;
SurfaceSetValuation valuation;
};
IdentifiableSurfaceSet CreateSurfaceSetWithSize(size_t count) {
IdentifiableSurfaceSet set;
set.reserve(count);
for (auto token = 0u; token < count; ++token) {
set.insert(blink::IdentifiableSurface::FromTypeAndToken(
blink::IdentifiableSurface::Type::kWebFeature, token));
}
return set;
}
} // namespace
TEST(SurfaceSetWithValuation, BasicGetters) {
ScopedValuation fixture;
SurfaceSetWithValuation set(fixture.valuation);
EXPECT_TRUE(set.Empty());
EXPECT_TRUE(set.TryAdd(kSurface1, kDefaultMediumBudget));
EXPECT_FALSE(set.Empty());
EXPECT_EQ(1u, set.Size());
EXPECT_TRUE(set.contains(kSurface1));
EXPECT_FALSE(set.contains(kSurface2));
set.Clear();
EXPECT_TRUE(set.Empty());
}
TEST(SurfaceSetWithValuation, Idempotence) {
ScopedValuation fixture;
SurfaceSetWithValuation set(fixture.valuation);
ASSERT_TRUE(set.TryAdd(kSurface1, kDefaultMediumBudget));
ASSERT_EQ(SurfaceSetValuation::kDefaultCost, set.Cost());
ASSERT_EQ(1u, set.Size());
// Nothing should change.
ASSERT_TRUE(set.TryAdd(kSurface1, kDefaultMediumBudget));
ASSERT_EQ(SurfaceSetValuation::kDefaultCost, set.Cost());
}
TEST(SurfaceSetWithValuation, Overflow) {
ScopedValuation fixture;
SurfaceSetWithValuation set(fixture.valuation);
int token = 10; // Different surfaces just need to have different token
// values. The values themselves don't matter.
// Adds surfaces until we hit the budget ceiling. The only expected outcome of
// this exercise is that when the loop is done `set` can't accept any more
// surfaces.
//
// By default, ScopedValuation sets things up so that each surface
// independently costs kDefaultCost.
for (PrivacyBudgetCost cost = 0.0; cost < kDefaultMediumBudget;
cost += SurfaceSetValuation::kDefaultCost) {
ASSERT_TRUE(
set.TryAdd(blink::IdentifiableSurface::FromTypeAndToken(
blink::IdentifiableSurface::Type::kWebFeature, token),
kDefaultMediumBudget));
++token;
}
// Overflows
EXPECT_FALSE(
set.TryAdd(blink::IdentifiableSurface::FromTypeAndToken(
blink::IdentifiableSurface::Type::kWebFeature, token),
kDefaultMediumBudget));
}
TEST(SurfaceSetWithValuation, Fill) {
ScopedValuation fixture;
SurfaceSetWithValuation set(fixture.valuation);
int token = 10; // As before, this value doesn't matter. All we care about is
// that each surface is different.
while (set.TryAdd(blink::IdentifiableSurface::FromTypeAndToken(
blink::IdentifiableSurface::Type::kWebFeature, ++token),
kDefaultMediumBudget)) {
}
EXPECT_LE(kDefaultMediumBudget, set.Cost());
}
TEST(SurfaceSetWithValuation, AssignWithBudget_Fits) {
ScopedValuation fixture;
SurfaceSetWithValuation set(fixture.valuation);
const auto kRawSurfaceSet = CreateSurfaceSetWithSize(
kDefaultMediumBudget / SurfaceSetValuation::kDefaultCost);
auto representative_surface_set =
fixture.equivalence.GetRepresentatives(kRawSurfaceSet);
ASSERT_EQ(kRawSurfaceSet.size(), representative_surface_set.size());
// All the surfaces in representative_surface_set should exist as-is in `set`.
set.AssignWithBudget(std::move(representative_surface_set),
kDefaultMediumBudget);
ASSERT_EQ(kRawSurfaceSet.size(), set.Size());
}
TEST(SurfaceSetWithValuation, AssignWithBudget_Overflows) {
ScopedValuation fixture;
SurfaceSetWithValuation set(fixture.valuation);
// Contains twice as many surfaces as is expected to fit.
const auto kRawSurfaceSet = CreateSurfaceSetWithSize(
2 * kDefaultMediumBudget / SurfaceSetValuation::kDefaultCost);
auto representative_surface_set =
fixture.equivalence.GetRepresentatives(kRawSurfaceSet);
ASSERT_EQ(kRawSurfaceSet.size(), representative_surface_set.size());
set.AssignWithBudget(std::move(representative_surface_set),
kDefaultMediumBudget);
EXPECT_GT(kRawSurfaceSet.size(), set.Size());
EXPECT_GE(kDefaultMediumBudget, set.Cost());
for (const auto& s : set)
EXPECT_TRUE(base::Contains(kRawSurfaceSet, s.value()));
}
TEST(SurfaceSetWithValuation, RepresentativeSurface) {
const auto kEquivalenceSet = CreateSurfaceSetWithSize(10);
const auto kEquivalenceList =
IdentifiableSurfaceList(kEquivalenceSet.begin(), kEquivalenceSet.end());
test::ScopedPrivacyBudgetConfig::Parameters pb_parameters(
test::ScopedPrivacyBudgetConfig::Presets::kEnableRandomSampling);
pb_parameters.equivalence_classes.emplace_back(kEquivalenceList);
ScopedValuation fixture(pb_parameters);
SurfaceSetWithValuation set(fixture.valuation);
for (const auto& s : kEquivalenceSet) {
ASSERT_TRUE(set.TryAdd(s, kDefaultMediumBudget));
}
// Since all the surfaces are in the same equivalence class, `set` only
// retains a single representative surface.
EXPECT_EQ(1u, set.Size());
for (const auto& s : kEquivalenceSet) {
EXPECT_TRUE(set.contains(s));
}
const auto representative_surface =
fixture.equivalence.GetRepresentative(*kEquivalenceSet.begin());
EXPECT_TRUE(set.contains(representative_surface));
}
|