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));
}
|
