1 #ifndef THIRD_PARTY_FCP_SECAGG_SERVER_GRAPH_PARAMETER_FINDER_TEST_CC_
2 #define THIRD_PARTY_FCP_SECAGG_SERVER_GRAPH_PARAMETER_FINDER_TEST_CC_
3
4 /*
5 * Copyright 2020 Google LLC
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License");
8 * you may not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 */
19
20 #include "fcp/secagg/server/graph_parameter_finder.h"
21
22 #include <algorithm>
23 #include <iostream>
24 #include <string>
25
26 #include "gtest/gtest.h"
27 #include "fcp/secagg/server/secagg_server_enums.pb.h"
28 #include "fcp/secagg/server/secagg_server_messages.pb.h"
29 #include "fcp/testing/testing.h"
30
31 namespace fcp {
32 namespace secagg {
33 namespace {
34
35 struct HararyGraphParameterFinderParams {
36 const std::string test_name;
37 const int kNumClients;
38 const double kAdversarialRate;
39 const double kDropoutRate;
40 const AdversaryClass kAdversaryClass;
41 const int kExpectedDegree;
42 const int kExpectedThreshold;
43 };
44
45 class HararyGraphParameterFinderTest_Feasible
46 : public ::testing::TestWithParam<HararyGraphParameterFinderParams> {};
47
TEST_P(HararyGraphParameterFinderTest_Feasible,ComputesParametersThatMatchPrecomputedValues)48 TEST_P(HararyGraphParameterFinderTest_Feasible,
49 ComputesParametersThatMatchPrecomputedValues) {
50 // This test computes parameters for feasible instances. It checks that the
51 // obtained degree (number of neighbors) and threshold match a precomputed
52 // value.
53 const HararyGraphParameterFinderParams& test_params = GetParam();
54 SecureAggregationRequirements threat_model;
55 int security_parameter = 40;
56 int correctness_parameter = 20;
57 FCP_LOG(INFO)
58 << "Running HararyGraphParameterFinder on instance with num. clients = "
59 << test_params.kNumClients
60 << ", adversarial rate = " << test_params.kAdversarialRate
61 << ", dropout rate = " << test_params.kDropoutRate
62 << ", security parameter = " << security_parameter
63 << ", correctness parameter = " << correctness_parameter
64 << ", adversary class = "
65 << (test_params.kAdversaryClass == AdversaryClass::CURIOUS_SERVER
66 ? "CURIOUS_SERVER"
67 : "SEMI_MALICIOUS_SERVER");
68 threat_model.set_adversarial_client_rate(test_params.kAdversarialRate);
69 threat_model.set_estimated_dropout_rate(test_params.kDropoutRate);
70 threat_model.set_adversary_class(test_params.kAdversaryClass);
71 auto computed_params =
72 ComputeHararyGraphParameters(test_params.kNumClients, threat_model);
73 EXPECT_EQ(computed_params.ok(), true);
74 int degree = computed_params.value().degree;
75 int threshold = computed_params.value().threshold;
76 FCP_LOG(INFO) << "Secure parameters were found: degree = " << degree
77 << ", threshold = " << threshold;
78 int expected_degree = test_params.kExpectedDegree;
79 int expected_threshold = test_params.kExpectedThreshold;
80 EXPECT_EQ(degree, expected_degree);
81 FCP_LOG(INFO) << "degree = " << degree
82 << " expected_degree = " << expected_degree;
83 EXPECT_LE(threshold, expected_threshold);
84 FCP_LOG(INFO) << "threshold = " << threshold
85 << " expected_threshold = " << expected_threshold;
86 }
87
TEST_P(HararyGraphParameterFinderTest_Feasible,ComputesParametersWithinExpectedRange)88 TEST_P(HararyGraphParameterFinderTest_Feasible,
89 ComputesParametersWithinExpectedRange) {
90 // This test computes parameters for feasible instances. It checks that the
91 // obtained degree (number of neighbors) is in between the analytical lower
92 // and upper bounds.
93 const HararyGraphParameterFinderParams& test_params = GetParam();
94 SecureAggregationRequirements threat_model;
95 int security_parameter = 40;
96 int correctness_parameter = 20;
97 FCP_LOG(INFO) << "Running HararyGraphParameterFinder on instance with num. "
98 "clients = "
99 << test_params.kNumClients
100 << ", adversarial rate = " << test_params.kAdversarialRate
101 << ", dropout rate = " << test_params.kDropoutRate
102 << ", security parameter = " << security_parameter
103 << ", correctness parameter = " << correctness_parameter
104 << ", adversary class = "
105 << (test_params.kAdversaryClass ==
106 AdversaryClass::CURIOUS_SERVER
107 ? "CURIOUS_SERVER"
108 : "SEMI_MALICIOUS_SERVER");
109 threat_model.set_adversarial_client_rate(test_params.kAdversarialRate);
110 threat_model.set_estimated_dropout_rate(test_params.kDropoutRate);
111 threat_model.set_adversary_class(test_params.kAdversaryClass);
112 auto computed_params =
113 ComputeHararyGraphParameters(test_params.kNumClients, threat_model);
114 EXPECT_EQ(computed_params.ok(), true);
115 int degree = computed_params.value().degree;
116 int threshold = computed_params.value().threshold;
117 FCP_LOG(INFO) << "Secure parameters were found: degree = " << degree
118 << ", threshold = " << threshold;
119
120 bool unconstrained_instance =
121 test_params.kAdversarialRate == 0 && test_params.kDropoutRate == 0;
122 bool small_instance = test_params.kNumClients < 20;
123 // The degree lower bound this enforces doesn't fit with the security
124 // guarantee that the rest of this code is designed to provide. Clearing up
125 // what the security guarantee should be is b/260400215 and this test should
126 // be cleared up in addressing that. Until then it is switched off for small
127 // variables where it behaves at odds with the model used elsewhere.
128 double degree_lower_bound =
129 unconstrained_instance || small_instance
130 ? 1
131 : log(test_params.kNumClients) + security_parameter * log(2) / 5.;
132
133 double beta = static_cast<double>(threshold) / degree;
134 double alpha = test_params.kNumClients / (test_params.kNumClients - 1);
135 double a = log(test_params.kNumClients) + correctness_parameter * log(2);
136 double b = 2 * pow(alpha * (1 - test_params.kDropoutRate) - beta, 2);
137 double c =
138 std::min(2 * pow(beta - alpha * test_params.kAdversarialRate, 2),
139 -log(test_params.kAdversarialRate + test_params.kDropoutRate));
140 double degree_upper_bound =
141 unconstrained_instance ? 3 : std::max(degree_lower_bound / c + 1, a / b);
142 // We increase the upper bound slightly for the semi-malicious variant
143 if (test_params.kAdversaryClass == AdversaryClass::SEMI_MALICIOUS_SERVER) {
144 degree_upper_bound += degree_upper_bound * 1. / 5;
145 }
146 EXPECT_GT(degree, degree_lower_bound);
147 EXPECT_LT(degree, degree_upper_bound);
148 EXPECT_GE(degree, threshold);
149 EXPECT_GT(threshold, 0);
150 }
151
152 INSTANTIATE_TEST_SUITE_P(
153 HararyGraphParameterFinderTests, HararyGraphParameterFinderTest_Feasible,
154 testing::ValuesIn<HararyGraphParameterFinderParams>({
155 // adversarial_rate = 0.45, dropout_rate = 0.45, adversary_class =
156 // semihonest, for number_of_clients in {10^i | i\in {2,3,4,5,6}}
157 {"100_clients__security_40__correctness_20__adversaryrate_045__"
158 "dropoutrate_045__adversary_class__semihonest",
159 100, 0.45, 0.45, AdversaryClass::CURIOUS_SERVER, 92, 46},
160 {"1000_clients__security_40__correctness_20__adversaryrate_045__"
161 "dropoutrate_045__adversary_class__semihonest",
162 1000, 0.45, 0.45, AdversaryClass::CURIOUS_SERVER, 822, 417},
163 {"10000_clients__security_40__correctness_20__adversaryrate_045__"
164 "dropoutrate_045__adversary_class__semihonest",
165 10000, 0.45, 0.45, AdversaryClass::CURIOUS_SERVER, 3494, 1771},
166 {"100000_clients__security_40__correctness_20__adversaryrate_045__"
167 "dropoutrate_045__adversary_class__semihonest",
168 100000, 0.45, 0.45, AdversaryClass::CURIOUS_SERVER, 5508, 2788},
169 {"1000000_clients__security_40__correctness_20__adversaryrate_045__"
170 "dropoutrate_045__adversary_class__semihonest",
171 1000000, 0.45, 0.45, AdversaryClass::CURIOUS_SERVER, 6240, 3156},
172 // adversarial_rate = 0.33, dropout_rate = 0.33, adversary_class =
173 // semihonest, for number_of_clients in {10^i | i\in {1,2,3,4,5,6}}
174 {"10_clients__security_40__correctness_20__adversaryrate_033__"
175 "dropoutrate_033__adversary_class__semihonest",
176 10, 0.33, 0.33, AdversaryClass::CURIOUS_SERVER, 8, 4},
177 {"100_clients__security_40__correctness_20__adversaryrate_033__"
178 "dropoutrate_033__adversary_class__semihonest",
179 100, 0.33, 0.33, AdversaryClass::CURIOUS_SERVER, 68, 34},
180 {"1000_clients__security_40__correctness_20__adversaryrate_033__"
181 "dropoutrate_033__adversary_class__semihonest",
182 1000, 0.33, 0.33, AdversaryClass::CURIOUS_SERVER, 286, 150},
183 {"10000_clients__security_40__correctness_20__adversaryrate_033__"
184 "dropoutrate_033__adversary_class__semihonest",
185 10000, 0.33, 0.33, AdversaryClass::CURIOUS_SERVER, 422, 221},
186 {"100000_clients__security_40__correctness_20__adversaryrate_033__"
187 "dropoutrate_033__adversary_class__semihonest",
188 100000, 0.33, 0.33, AdversaryClass::CURIOUS_SERVER, 480, 251},
189 {"1000000_clients__security_40__correctness_20__adversaryrate_033__"
190 "dropoutrate_033__adversary_class__semihonest",
191 1000000, 0.33, 0.33, AdversaryClass::CURIOUS_SERVER, 518, 270},
192 // adversarial_rate = 0.3, dropout_rate = 0.3, adversary_class =
193 // semimalicious, for number_of_clients in {10^i | i\in {2,3,4,5,6}}
194 {"100_clients__security_40__correctness_20__adversaryrate_03__"
195 "dropoutrate_03__adversary_class__semimalicious",
196 100, 0.3, 0.3, AdversaryClass::SEMI_MALICIOUS_SERVER, 92, 62},
197 {"1000_clients__security_40__correctness_20__adversaryrate_03__"
198 "dropoutrate_03__adversary_class__semimalicious",
199 1000, 0.3, 0.3, AdversaryClass::SEMI_MALICIOUS_SERVER, 872, 584},
200 {"10000_clients__security_40__correctness_20__adversaryrate_03__"
201 "dropoutrate_03__adversary_class__semimalicious",
202 10000, 0.3, 0.3, AdversaryClass::SEMI_MALICIOUS_SERVER, 4822, 3230},
203 {"100000_clients__security_40__correctness_20__adversaryrate_03__"
204 "dropoutrate_03__adversary_class__semimalicious",
205 100000, 0.3, 0.3, AdversaryClass::SEMI_MALICIOUS_SERVER, 9388, 6286},
206 {"1000000_clients__security_40__correctness_20__adversaryrate_03__"
207 "dropoutrate_03__adversary_class__semimalicious",
208 1000000, 0.3, 0.3, AdversaryClass::SEMI_MALICIOUS_SERVER, 11136, 7454},
209 // adversarial_rate = 0.05, dropout_rate = 0.33, adversary_class =
210 // semihonest, for number_of_clients in {10^i | i\in {1,2,3,4,5,6}}
211 {"10_clients__security_40__correctness_20__adversaryrate_005__"
212 "dropoutrate_033__adversary_class__semihonest",
213 10, 0.05, 0.33, AdversaryClass::CURIOUS_SERVER, 4, 2},
214 {"100_clients__security_40__correctness_20__adversaryrate_005__"
215 "dropoutrate_033__adversary_class__semihonest",
216 100, 0.05, 0.33, AdversaryClass::CURIOUS_SERVER, 28, 6},
217 {"1000_clients__security_40__correctness_20__adversaryrate_005__"
218 "dropoutrate_033__adversary_class__semihonest",
219 1000, 0.05, 0.33, AdversaryClass::CURIOUS_SERVER, 72, 24},
220 {"10000_clients__security_40__correctness_20__adversaryrate_005__"
221 "dropoutrate_033__adversary_class__semihonest",
222 10000, 0.05, 0.33, AdversaryClass::CURIOUS_SERVER, 86, 29},
223 {"100000_clients__security_40__correctness_20__adversaryrate_005__"
224 "dropoutrate_033__adversary_class__semihonest",
225 100000, 0.05, 0.33, AdversaryClass::CURIOUS_SERVER, 96, 32},
226 {"1000000_clients__security_40__correctness_20__adversaryrate_005__"
227 "dropoutrate_033__adversary_class__semihonest",
228 1000000, 0.05, 0.33, AdversaryClass::CURIOUS_SERVER, 102, 34},
229 // adversarial_rate = 0.05, dropout_rate = 0.33, adversary_class =
230 // semimalicious, for number_of_clients in {10^i | i\in {1,2,3,4,5,6}}
231 {"10_clients__security_40__correctness_20__adversaryrate_005__"
232 "dropoutrate_033__adversary_class__semimalicious",
233 10, 0.05, 0.33, AdversaryClass::SEMI_MALICIOUS_SERVER, 8, 5},
234 {"100_clients__security_40__correctness_20__adversaryrate_005__"
235 "dropoutrate_033__adversary_class__semimalicious",
236 100, 0.05, 0.33, AdversaryClass::SEMI_MALICIOUS_SERVER, 72, 39},
237 {"1000_clients__security_40__correctness_20__adversaryrate_005__"
238 "dropoutrate_033__adversary_class__semimalicious",
239 1000, 0.05, 0.33, AdversaryClass::SEMI_MALICIOUS_SERVER, 398, 223},
240 {"10000_clients__security_40__correctness_20__adversaryrate_005__"
241 "dropoutrate_033__adversary_class__semimalicious",
242 10000, 0.05, 0.33, AdversaryClass::SEMI_MALICIOUS_SERVER, 746, 420},
243 {"100000_clients__security_40__correctness_20__adversaryrate_005__"
244 "dropoutrate_033__adversary_class__semimalicious",
245 100000, 0.05, 0.33, AdversaryClass::SEMI_MALICIOUS_SERVER, 882, 496},
246 {"1000000_clients__security_40__correctness_20__adversaryrate_005__"
247 "dropoutrate_033__adversary_class__semimalicious",
248 1000000, 0.05, 0.33, AdversaryClass::SEMI_MALICIOUS_SERVER, 970, 545},
249 // adversarial_rate = 0.33, dropout_rate = 0.05, adversary_class =
250 // semihonest, for number_of_clients in {10^i | i\in {1,2,3,4,5,6}}
251 {"10_clients__security_40__correctness_20__adversaryrate_033__"
252 "dropoutrate_005__adversary_class__semihonest",
253 10, 0.33, 0.05, AdversaryClass::CURIOUS_SERVER, 4, 4},
254 {"100_clients__security_40__correctness_20__adversaryrate_033__"
255 "dropoutrate_005__adversary_class__semihonest",
256 100, 0.33, 0.05, AdversaryClass::CURIOUS_SERVER, 34, 29},
257 {"1000_clients__security_40__correctness_20__adversaryrate_033__"
258 "dropoutrate_005__adversary_class__semihonest",
259 1000, 0.33, 0.05, AdversaryClass::CURIOUS_SERVER, 78, 60},
260 {"10000_clients__security_40__correctness_20__adversaryrate_033__"
261 "dropoutrate_005__adversary_class__semihonest",
262 10000, 0.33, 0.05, AdversaryClass::CURIOUS_SERVER, 92, 70},
263 {"100000_clients__security_40__correctness_20__adversaryrate_033__"
264 "dropoutrate_005__adversary_class__semihonest",
265 100000, 0.33, 0.05, AdversaryClass::CURIOUS_SERVER, 102, 77},
266 {"1000000_clients__security_40__correctness_20__adversaryrate_033__"
267 "dropoutrate_005__adversary_class__semihonest",
268 1000000, 0.33, 0.05, AdversaryClass::CURIOUS_SERVER, 110, 83},
269 // adversarial_rate = 0.33, dropout_rate = 0.05, adversary_class =
270 // semimalicious, for number_of_clients in {10^i | i\in {1,2,3,4,5,6}}
271 {"10_clients__security_40__correctness_20__adversaryrate_033__"
272 "dropoutrate_005__adversary_class__semimalicious",
273 10, 0.33, 0.05, AdversaryClass::SEMI_MALICIOUS_SERVER, 4, 4},
274 {"100_clients__security_40__correctness_20__adversaryrate_033__"
275 "dropoutrate_005__adversary_class__semimalicious",
276 100, 0.33, 0.05, AdversaryClass::SEMI_MALICIOUS_SERVER, 42, 37},
277 {"1000_clients__security_40__correctness_20__adversaryrate_033__"
278 "dropoutrate_005__adversary_class__semimalicious",
279 1000, 0.33, 0.05, AdversaryClass::SEMI_MALICIOUS_SERVER, 132, 109},
280 {"10000_clients__security_40__correctness_20__adversaryrate_033__"
281 "dropoutrate_005__adversary_class__semimalicious",
282 10000, 0.33, 0.05, AdversaryClass::SEMI_MALICIOUS_SERVER, 178, 146},
283 {"100000_clients__security_40__correctness_20__adversaryrate_033__"
284 "dropoutrate_005__adversary_class__semimalicious",
285 100000, 0.33, 0.05, AdversaryClass::SEMI_MALICIOUS_SERVER, 196, 160},
286 {"1000000_clients__security_40__correctness_20__adversaryrate_033__"
287 "dropoutrate_005__adversary_class__semimalicious",
288 1000000, 0.33, 0.05, AdversaryClass::SEMI_MALICIOUS_SERVER, 212, 173},
289 // adversarial_rate = 0.05, dropout_rate = 0.05, adversary_class =
290 // semihonest, for number_of_clients in {10^i | i\in {1,2,3,4,5,6}}
291 {"10_clients__security_40__correctness_20__adversaryrate_005__"
292 "dropoutrate_005__adversary_class__semihonest",
293 10, 0.05, 0.05, AdversaryClass::CURIOUS_SERVER, 2, 2},
294 {"100_clients__security_40__correctness_20__adversaryrate_005__"
295 "dropoutrate_005__adversary_class__semihonest",
296 100, 0.05, 0.05, AdversaryClass::CURIOUS_SERVER, 12, 6},
297 {"1000_clients__security_40__correctness_20__adversaryrate_005__"
298 "dropoutrate_005__adversary_class__semihonest",
299 1000, 0.05, 0.05, AdversaryClass::CURIOUS_SERVER, 30, 17},
300 {"10000_clients__security_40__correctness_20__adversaryrate_005__"
301 "dropoutrate_005__adversary_class__semihonest",
302 10000, 0.05, 0.05, AdversaryClass::CURIOUS_SERVER, 34, 20},
303 {"100000_clients__security_40__correctness_20__adversaryrate_005__"
304 "dropoutrate_005__adversary_class__semihonest",
305 100000, 0.05, 0.05, AdversaryClass::CURIOUS_SERVER, 36, 21},
306 {"1000000_clients__security_40__correctness_20__adversaryrate_005__"
307 "dropoutrate_005__adversary_class__semihonest",
308 1000000, 0.05, 0.05, AdversaryClass::CURIOUS_SERVER, 38, 22},
309 // adversarial_rate = 0.05, dropout_rate = 0.05, adversary_class =
310 // semimalicious, for number_of_clients in {10^i | i\in {1,2,3,4,5,6}}
311 {"10_clients__security_40__correctness_20__adversaryrate_005__"
312 "dropoutrate_005__adversary_class__semimalicious",
313 10, 0.05, 0.05, AdversaryClass::SEMI_MALICIOUS_SERVER, 2, 2},
314 {"100_clients__security_40__correctness_20__adversaryrate_005__"
315 "dropoutrate_005__adversary_class__semimalicious",
316 100, 0.05, 0.05, AdversaryClass::SEMI_MALICIOUS_SERVER, 16, 11},
317 {"1000_clients__security_40__correctness_20__adversaryrate_005__"
318 "dropoutrate_005__adversary_class__semimalicious",
319 1000, 0.05, 0.05, AdversaryClass::SEMI_MALICIOUS_SERVER, 52, 37},
320 {"10000_clients__security_40__correctness_20__adversaryrate_005__"
321 "dropoutrate_005__adversary_class__semimalicious",
322 10000, 0.05, 0.05, AdversaryClass::SEMI_MALICIOUS_SERVER, 62, 44},
323 {"100000_clients__security_40__correctness_20__adversaryrate_005__"
324 "dropoutrate_005__adversary_class__semimalicious",
325 100000, 0.05, 0.05, AdversaryClass::SEMI_MALICIOUS_SERVER, 68, 48},
326 {"1000000_clients__security_40__correctness_20__adversaryrate_005__"
327 "dropoutrate_005__adversary_class__semimalicious",
328 1000000, 0.05, 0.05, AdversaryClass::SEMI_MALICIOUS_SERVER, 74, 52},
329 // adversarial_rate = 0.33, dropout_rate = 0.0, adversary_class =
330 // semihonest, for number_of_clients in {10^i | i\in {1,2,3,4,5,6}}
331 {"10_clients__security_40__correctness_20__adversaryrate_033__"
332 "dropoutrate_00__adversary_class__semihonest",
333 10, 0.33, 0.0, AdversaryClass::CURIOUS_SERVER, 4, 4},
334 {"100_clients__security_40__correctness_20__adversaryrate_033__"
335 "dropoutrate_00__adversary_class__semihonest",
336 100, 0.33, 0.0, AdversaryClass::CURIOUS_SERVER, 26, 25},
337 {"1000_clients__security_40__correctness_20__adversaryrate_033__"
338 "dropoutrate_00__adversary_class__semihonest",
339 1000, 0.33, 0.0, AdversaryClass::CURIOUS_SERVER, 38, 36},
340 {"10000_clients__security_40__correctness_20__adversaryrate_033__"
341 "dropoutrate_00__adversary_class__semihonest",
342 10000, 0.33, 0.0, AdversaryClass::CURIOUS_SERVER, 42, 40},
343 {"100000_clients__security_40__correctness_20__adversaryrate_033__"
344 "dropoutrate_00__adversary_class__semihonest",
345 100000, 0.33, 0.0, AdversaryClass::CURIOUS_SERVER, 46, 44},
346 {"1000000_clients__security_40__correctness_20__adversaryrate_033__"
347 "dropoutrate_00__adversary_class__semihonest",
348 1000000, 0.33, 0.0, AdversaryClass::CURIOUS_SERVER, 50, 47},
349 // adversarial_rate = 0.33, dropout_rate = 0.0, adversary_class =
350 // semimalicious, for number_of_clients in {10^i | i\in {1,2,3,4,5,6}}
351 {"10_clients__security_40__correctness_20__adversaryrate_033__"
352 "dropoutrate_00__adversary_class__semimalicious",
353 10, 0.33, 0.0, AdversaryClass::SEMI_MALICIOUS_SERVER, 4, 4},
354 {"100_clients__security_40__correctness_20__adversaryrate_033__"
355 "dropoutrate_00__adversary_class__semimalicious",
356 100, 0.33, 0.0, AdversaryClass::SEMI_MALICIOUS_SERVER, 26, 26},
357 {"1000_clients__security_40__correctness_20__adversaryrate_033__"
358 "dropoutrate_00__adversary_class__semimalicious",
359 1000, 0.33, 0.0, AdversaryClass::SEMI_MALICIOUS_SERVER, 38, 37},
360 {"10000_clients__security_40__correctness_20__adversaryrate_033__"
361 "dropoutrate_00__adversary_class__semimalicious",
362 10000, 0.33, 0.0, AdversaryClass::SEMI_MALICIOUS_SERVER, 42, 41},
363 {"100000_clients__security_40__correctness_20__adversaryrate_033__"
364 "dropoutrate_00__adversary_class__semimalicious",
365 100000, 0.33, 0.0, AdversaryClass::SEMI_MALICIOUS_SERVER, 46, 45},
366 {"1000000_clients__security_40__correctness_20__adversaryrate_033__"
367 "dropoutrate_00__adversary_class__semimalicious",
368 1000000, 0.33, 0.0, AdversaryClass::SEMI_MALICIOUS_SERVER, 50, 49},
369 // adversarial_rate = 0.0, dropout_rate = 0.33, adversary_class =
370 // semihonest, for number_of_clients in {10^i | i\in {1,2,3,4,5,6}}
371 {"10_clients__security_40__correctness_20__adversaryrate_00__"
372 "dropoutrate_033__adversary_class__semihonest",
373 10, 0.0, 0.33, AdversaryClass::CURIOUS_SERVER, 4, 2},
374 {"100_clients__security_40__correctness_20__adversaryrate_00__"
375 "dropoutrate_033__adversary_class__semihonest",
376 100, 0.0, 0.33, AdversaryClass::CURIOUS_SERVER, 26, 2},
377 {"1000_clients__security_40__correctness_20__adversaryrate_00__"
378 "dropoutrate_033__adversary_class__semihonest",
379 1000, 0.0, 0.33, AdversaryClass::CURIOUS_SERVER, 38, 2},
380 {"10000_clients__security_40__correctness_20__adversaryrate_00__"
381 "dropoutrate_033__adversary_class__semihonest",
382 10000, 0.0, 0.33, AdversaryClass::CURIOUS_SERVER, 42, 2},
383 {"100000_clients__security_40__correctness_20__adversaryrate_00__"
384 "dropoutrate_033__adversary_class__semihonest",
385 100000, 0.0, 0.33, AdversaryClass::CURIOUS_SERVER, 46, 2},
386 {"1000000_clients__security_40__correctness_20__adversaryrate_00__"
387 "dropoutrate_033__adversary_class__semihonest",
388 1000000, 0.0, 0.33, AdversaryClass::CURIOUS_SERVER, 50, 2},
389 // adversarial_rate = 0.0, dropout_rate = 0.33, adversary_class =
390 // none, for number_of_clients in {10^i | i\in {1,2,3,4,5,6}}
391 {"10_clients__security_40__correctness_20__adversaryrate_00__"
392 "dropoutrate_033__adversary_class__none",
393 10, 0.0, 0.33, AdversaryClass::NONE, 4, 2},
394 {"100_clients__security_40__correctness_20__adversaryrate_00__"
395 "dropoutrate_033__adversary_class__none",
396 100, 0.0, 0.33, AdversaryClass::NONE, 26, 2},
397 {"1000_clients__security_40__correctness_20__adversaryrate_00__"
398 "dropoutrate_033__adversary_class__none",
399 1000, 0.0, 0.33, AdversaryClass::NONE, 38, 2},
400 {"10000_clients__security_40__correctness_20__adversaryrate_00__"
401 "dropoutrate_033__adversary_class__none",
402 10000, 0.0, 0.33, AdversaryClass::NONE, 42, 2},
403 {"100000_clients__security_40__correctness_20__adversaryrate_00__"
404 "dropoutrate_033__adversary_class__none",
405 100000, 0.0, 0.33, AdversaryClass::NONE, 46, 2},
406 {"1000000_clients__security_40__correctness_20__adversaryrate_00__"
407 "dropoutrate_033__adversary_class__none",
408 1000000, 0.0, 0.33, AdversaryClass::NONE, 50, 2},
409 // adversarial_rate = 0.0, dropout_rate = 0.33, adversary_class =
410 // semimalicious, for number_of_clients in {10^i | i\in {1,2,3,4,5,6}}
411 {"10_clients__security_40__correctness_20__adversaryrate_00__"
412 "dropoutrate_033__adversary_class__semimalicious",
413 10, 0.0, 0.33, AdversaryClass::SEMI_MALICIOUS_SERVER, 8, 5},
414 {"100_clients__security_40__correctness_20__adversaryrate_00__"
415 "dropoutrate_033__adversary_class__semimalicious",
416 100, 0.0, 0.33, AdversaryClass::SEMI_MALICIOUS_SERVER, 68, 35},
417 {"1000_clients__security_40__correctness_20__adversaryrate_00__"
418 "dropoutrate_033__adversary_class__semimalicious",
419 1000, 0.0, 0.33, AdversaryClass::SEMI_MALICIOUS_SERVER, 228, 115},
420 {"10000_clients__security_40__correctness_20__adversaryrate_00__"
421 "dropoutrate_033__adversary_class__semimalicious",
422 10000, 0.0, 0.33, AdversaryClass::SEMI_MALICIOUS_SERVER, 326, 164},
423 {"100000_clients__security_40__correctness_20__adversaryrate_00__"
424 "dropoutrate_033__adversary_class__semimalicious",
425 100000, 0.0, 0.33, AdversaryClass::SEMI_MALICIOUS_SERVER, 372, 187},
426 {"1000000_clients__security_40__correctness_20__adversaryrate_00__"
427 "dropoutrate_033__adversary_class__semimalicious",
428 1000000, 0.0, 0.33, AdversaryClass::SEMI_MALICIOUS_SERVER, 410, 206},
429 // adversarial_rate = 0.0, dropout_rate = 0.0, adversary_class =
430 // semihonest, for number_of_clients in {10^i | i\in {1,2,3,4,5,6}}
431 {"10_clients__security_40__correctness_20__adversaryrate_00__"
432 "dropoutrate_00__adversary_class__semihonest",
433 10, 0.0, 0.0, AdversaryClass::CURIOUS_SERVER, 2, 2},
434 {"100_clients__security_40__correctness_20__adversaryrate_00__"
435 "dropoutrate_00__adversary_class__semihonest",
436 100, 0.0, 0.0, AdversaryClass::CURIOUS_SERVER, 2, 2},
437 {"1000_clients__security_40__correctness_20__adversaryrate_00__"
438 "dropoutrate_00__adversary_class__semihonest",
439 1000, 0.0, 0.0, AdversaryClass::CURIOUS_SERVER, 2, 2},
440 {"10000_clients__security_40__correctness_20__adversaryrate_00__"
441 "dropoutrate_00__adversary_class__semihonest",
442 10000, 0.0, 0.0, AdversaryClass::CURIOUS_SERVER, 2, 2},
443 {"100000_clients__security_40__correctness_20__adversaryrate_00__"
444 "dropoutrate_00__adversary_class__semihonest",
445 100000, 0.0, 0.0, AdversaryClass::CURIOUS_SERVER, 2, 2},
446 {"1000000_clients__security_40__correctness_20__adversaryrate_00__"
447 "dropoutrate_00__adversary_class__semihonest",
448 1000000, 0.0, 0.0, AdversaryClass::CURIOUS_SERVER, 2, 2},
449 // adversarial_rate = 0.0, dropout_rate = 0.0, adversary_class =
450 // none, for number_of_clients in {10^i | i\in {1,2,3,4,5,6}}
451 {"1000_clients__security_40__correctness_20__adversaryrate_00__"
452 "dropoutrate_00__adversary_class__none",
453 1000, 0.0, 0.0, AdversaryClass::NONE, 2, 2},
454 {"10000_clients__security_40__correctness_20__adversaryrate_00__"
455 "dropoutrate_00__adversary_class__none",
456 10000, 0.0, 0.0, AdversaryClass::NONE, 2, 2},
457 {"100000_clients__security_40__correctness_20__adversaryrate_00__"
458 "dropoutrate_00__adversary_class__none",
459 100000, 0.0, 0.0, AdversaryClass::NONE, 2, 2},
460 {"1000000_clients__security_40__correctness_20__adversaryrate_00__"
461 "dropoutrate_00__adversary_class__none",
462 1000000, 0.0, 0.0, AdversaryClass::NONE, 2, 2},
463 // adversarial_rate = 0.0, dropout_rate = 0.0, adversary_class =
464 // semimalicious, for number_of_clients in {10^i | i\in {1,2,3,4,5,6}}
465 {"10_clients__security_40__correctness_20__adversaryrate_00__"
466 "dropoutrate_00__adversary_class__semimalicious",
467 10, 0.0, 0.0, AdversaryClass::SEMI_MALICIOUS_SERVER, 2, 2},
468 {"100_clients__security_40__correctness_20__adversaryrate_00__"
469 "dropoutrate_00__adversary_class__semimalicious",
470 100, 0.0, 0.0, AdversaryClass::SEMI_MALICIOUS_SERVER, 2, 2},
471 {"1000_clients__security_40__correctness_20__adversaryrate_00__"
472 "dropoutrate_00__adversary_class__semimalicious",
473 1000, 0.0, 0.0, AdversaryClass::SEMI_MALICIOUS_SERVER, 2, 2},
474 {"10000_clients__security_40__correctness_20__adversaryrate_00__"
475 "dropoutrate_00__adversary_class__semimalicious",
476 10000, 0.0, 0.0, AdversaryClass::SEMI_MALICIOUS_SERVER, 2, 2},
477 {"100000_clients__security_40__correctness_20__adversaryrate_00__"
478 "dropoutrate_00__adversary_class__semimalicious",
479 100000, 0.0, 0.0, AdversaryClass::SEMI_MALICIOUS_SERVER, 2, 2},
480 {"1000000_clients__security_40__correctness_20__adversaryrate_00__"
481 "dropoutrate_00__adversary_class__semimalicious",
482 1000000, 0.0, 0.0, AdversaryClass::SEMI_MALICIOUS_SERVER, 2, 2},
483 }),
484 [](const ::testing::TestParamInfo<
__anon49e5ce270202(const ::testing::TestParamInfo< HararyGraphParameterFinderTest_Feasible::ParamType>& info) 485 HararyGraphParameterFinderTest_Feasible::ParamType>& info) {
486 return info.param.test_name;
487 });
488
489 class HararyGraphParameterFinderTest_InvalidOrUnfeasible
490 : public ::testing::TestWithParam<HararyGraphParameterFinderParams> {};
491
TEST_P(HararyGraphParameterFinderTest_InvalidOrUnfeasible,FailsOnIncorrectParameters)492 TEST_P(HararyGraphParameterFinderTest_InvalidOrUnfeasible,
493 FailsOnIncorrectParameters) {
494 // This test tries to compute parameters for invalid (parameters with
495 // incorrect values) or unfeasible (combinations of valid parameter values
496 // that make the problem unsolvable) instances.
497 const HararyGraphParameterFinderParams& test_params = GetParam();
498 SecureAggregationRequirements threat_model;
499 threat_model.set_adversarial_client_rate(test_params.kAdversarialRate);
500 threat_model.set_estimated_dropout_rate(test_params.kDropoutRate);
501 threat_model.set_adversary_class(test_params.kAdversaryClass);
502 auto computed_params =
503 ComputeHararyGraphParameters(test_params.kNumClients, threat_model);
504 EXPECT_EQ(computed_params.ok(), false);
505 }
506
507 INSTANTIATE_TEST_SUITE_P(
508 HararyGraphParameterFinderTests,
509 HararyGraphParameterFinderTest_InvalidOrUnfeasible,
510 ::testing::ValuesIn<HararyGraphParameterFinderParams>({
511 {"0_clients__security_40__correctness_20__adversaryrate_01__"
512 "dropoutrate_01__adversary_class__semihonest",
513 0, 0.1, 0.1, AdversaryClass::CURIOUS_SERVER, 0, 0},
514 {"1000_clients__security_40__correctness_20__adversaryrate_1__"
515 "dropoutrate_1__adversary_class__semihonest",
516 1000, 0.1, 1., AdversaryClass::CURIOUS_SERVER, 0, 0},
517 {"1000_clients__security_40__correctness_20__adversaryrate_01__"
518 "dropoutrate_minus1__adversary_class__semihonest",
519 1000, 0.1, -1., AdversaryClass::CURIOUS_SERVER, 0, 0},
520 // For semi_honest/honest-but-curious adversary, we need that
521 // adversary_rate + dropout_rate < 1 for the instance to be feasible
522 {"1000_clients__security_40__correctness_20__adversaryrate_05__"
523 "dropoutrate_05__adversary_class__semihonest",
524 1000, 0.5, 0.5, AdversaryClass::CURIOUS_SERVER, 0, 0},
525 // For semi_malicious adversary, we need that adversary_rate +
526 // 2*dropout_rate < 1 for the instance to be feasible
527 {"1000_clients__security_40__correctness_20__adversaryrate_05__"
528 "dropoutrate_05__adversary_class__semimalicious",
529 1000, 0.5, 0.5, AdversaryClass::SEMI_MALICIOUS_SERVER, 0, 0},
530 {"1000_clients__security_40__correctness_20__adversaryrate_033__"
531 "dropoutrate_033__adversary_class__semimalicious",
532 1000, 0.33, 0.33, AdversaryClass::SEMI_MALICIOUS_SERVER, 0, 0},
533 // For the no-adversary setting we expect adversary_rate == 0
534 {"1000_clients__security_40__correctness_20__adversaryrate_05__"
535 "dropoutrate_05__adversary_class__none",
536 1000, 0.5, 0.5, AdversaryClass::NONE, 0, 0},
537 }),
538 [](const ::testing::TestParamInfo<
__anon49e5ce270302(const ::testing::TestParamInfo< HararyGraphParameterFinderTest_InvalidOrUnfeasible::ParamType>& info) 539 HararyGraphParameterFinderTest_InvalidOrUnfeasible::ParamType>& info) {
540 return info.param.test_name;
541 });
542
TEST(FullGraphCeckParamsTest,ReturnsTrueOnValidThresholds)543 TEST(FullGraphCeckParamsTest, ReturnsTrueOnValidThresholds) {
544 SecureAggregationRequirements threat_model;
545 threat_model.set_adversarial_client_rate(.05);
546 threat_model.set_estimated_dropout_rate(.3);
547 threat_model.set_adversary_class(AdversaryClass::CURIOUS_SERVER);
548 int num_clients = 60;
549 for (int t = 42; t < num_clients; t++) {
550 EXPECT_THAT(CheckFullGraphParameters(num_clients, t, threat_model).ok(),
551 true)
552 << t;
553 }
554 }
555
TEST(FullGraphCeckParamsTest,ReturnsFalseOnInvalidThresholds)556 TEST(FullGraphCeckParamsTest, ReturnsFalseOnInvalidThresholds) {
557 SecureAggregationRequirements threat_model;
558 threat_model.set_adversarial_client_rate(.05);
559 threat_model.set_estimated_dropout_rate(.3);
560 threat_model.set_adversary_class(AdversaryClass::CURIOUS_SERVER);
561 int num_clients = 60;
562 for (int t = 0; t < 42; t++) {
563 EXPECT_THAT(CheckFullGraphParameters(num_clients, t, threat_model).ok(),
564 false);
565 }
566 }
567
568 } // namespace
569 } // namespace secagg
570 } // namespace fcp
571
572 #endif // THIRD_PARTY_FCP_SECAGG_SERVER_GRAPH_PARAMETER_FINDER_TEST_CC_
573