1 /*
2 * Copyright 2020 Google LLC
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include <algorithm>
18 #include <memory>
19 #include <string>
20
21 #include "absl/status/status.h"
22 #include "fcp/secagg/server/secret_sharing_graph.h"
23 #include "fcp/secagg/server/secret_sharing_graph_factory.h"
24 #include "fcp/testing/testing.h"
25
26 namespace fcp {
27 namespace secagg {
28 namespace {
29
30 namespace secret_sharing_harary_graph_test_internal {
31 // Auxiliary function returning the index of j in the list of neighbors of i,
32 // in a graph g represented as an adjacency list
GetNeighborIndexFromAdjacencyList(const std::vector<std::vector<int>> & g,int i,int j)33 std::optional<int> GetNeighborIndexFromAdjacencyList(
34 const std::vector<std::vector<int>>& g, int i, int j) {
35 auto index = std::find(std::begin(g[i]), std::end(g[i]), j);
36 if (index != std::end(g[i])) {
37 return *index;
38 }
39 return {};
40 }
41 } // namespace secret_sharing_harary_graph_test_internal
42
43 static constexpr int kNumNodes = 10;
44 static constexpr int kDegree = 5;
45 static constexpr int kThreshold = 2;
46
TEST(SecretSharingHararyGraphTest,GetPermutationReturnsPermutation)47 TEST(SecretSharingHararyGraphTest, GetPermutationReturnsPermutation) {
48 SecretSharingGraphFactory factory;
49 auto graph = factory.CreateHararyGraph(kNumNodes, kDegree, kThreshold);
50 std::vector<int> permutation = graph->GetPermutationForTesting();
51 EXPECT_EQ(permutation.size(), kNumNodes);
52 std::vector<int> counters(kNumNodes, 0);
53 for (int i = 0; i < permutation.size(); ++i) {
54 counters[permutation[i]]++;
55 }
56 for (auto x : counters) {
57 EXPECT_EQ(x, 1);
58 }
59 }
60
TEST(SecretSharingHararyGraphTest,GetPermutationInDeterministicHararyGraphReturnsIdentityPermutation)61 TEST(SecretSharingHararyGraphTest,
62 GetPermutationInDeterministicHararyGraphReturnsIdentityPermutation) {
63 SecretSharingGraphFactory factory;
64 auto graph = factory.CreateHararyGraph(kNumNodes, kDegree, kThreshold, false);
65 std::vector<int> permutation = graph->GetPermutationForTesting();
66 for (int i = 0; i < permutation.size(); ++i) {
67 EXPECT_EQ(permutation[i], i);
68 }
69 }
70
TEST(SecretSharingHararyGraphTest,GetPermutationInRandomHararyGraphDoesNotReturnIdentityPermutation)71 TEST(SecretSharingHararyGraphTest,
72 GetPermutationInRandomHararyGraphDoesNotReturnIdentityPermutation) {
73 SecretSharingGraphFactory factory;
74 // We use a larger number of nodes so that the probability of getting the
75 // identity permutation by change is negligible
76 int larger_num_nodes = 100;
77 auto graph = factory.CreateHararyGraph(larger_num_nodes, kDegree, kThreshold);
78 std::vector<int> permutation = graph->GetPermutationForTesting();
79 // Find j so that permutation[j] != j. This will be the case for most i's (all
80 // but one in expectation), but one is sufficient in this test.
81 bool found = false;
82 for (int i = 0; i < permutation.size(); ++i) {
83 found = found || (i != permutation[i]);
84 }
85 EXPECT_EQ(found, true);
86 }
87
TEST(SecretSharingHararyGraphTest,AreNeighborsIsCorrectInRandomHararyGraph)88 TEST(SecretSharingHararyGraphTest, AreNeighborsIsCorrectInRandomHararyGraph) {
89 SecretSharingGraphFactory factory;
90 auto graph = factory.CreateHararyGraph(kNumNodes, kDegree, kThreshold);
91
92 EXPECT_EQ(graph->GetNumNodes(), kNumNodes);
93 EXPECT_EQ(graph->GetDegree(), kDegree);
94 EXPECT_EQ(graph->GetThreshold(), kThreshold);
95
96 std::vector<int> p = graph->GetPermutationForTesting();
97 std::vector<std::vector<int>> adjacency_list(kNumNodes,
98 std::vector<int>(kDegree));
99 adjacency_list[p[0]] = {p[8], p[9], p[0], p[1], p[2]};
100 adjacency_list[p[1]] = {p[9], p[0], p[1], p[2], p[3]};
101 adjacency_list[p[2]] = {p[0], p[1], p[2], p[3], p[4]};
102 adjacency_list[p[3]] = {p[1], p[2], p[3], p[4], p[5]};
103 adjacency_list[p[4]] = {p[2], p[3], p[4], p[5], p[6]};
104 adjacency_list[p[5]] = {p[3], p[4], p[5], p[6], p[7]};
105 adjacency_list[p[6]] = {p[4], p[5], p[6], p[7], p[8]};
106 adjacency_list[p[7]] = {p[5], p[6], p[7], p[8], p[9]};
107 adjacency_list[p[8]] = {p[6], p[7], p[8], p[9], p[0]};
108 adjacency_list[p[9]] = {p[7], p[8], p[9], p[0], p[1]};
109
110 for (int i = 0; i < kNumNodes; ++i) {
111 for (int j = 0; j < kNumNodes; ++j) {
112 bool are_neighbors =
113 secret_sharing_harary_graph_test_internal::
114 GetNeighborIndexFromAdjacencyList(adjacency_list, i, j)
115 .value_or(-1) >= 0;
116 EXPECT_EQ(graph->AreNeighbors(i, j), are_neighbors) << i << "," << j;
117 }
118 }
119 }
120
TEST(SecretSharingHararyGraphTest,AreNeighborsIsCorrectInDeterministicHararyGraph)121 TEST(SecretSharingHararyGraphTest,
122 AreNeighborsIsCorrectInDeterministicHararyGraph) {
123 SecretSharingGraphFactory factory;
124 auto graph = factory.CreateHararyGraph(kNumNodes, kDegree, kThreshold, false);
125
126 EXPECT_EQ(graph->GetNumNodes(), kNumNodes);
127 EXPECT_EQ(graph->GetDegree(), kDegree);
128 EXPECT_EQ(graph->GetThreshold(), kThreshold);
129
130 std::vector<int> p = graph->GetPermutationForTesting();
131 std::vector<std::vector<int>> adjacency_list(kNumNodes,
132 std::vector<int>(kDegree));
133 adjacency_list[0] = {8, 9, 0, 1, 2};
134 adjacency_list[1] = {9, 0, 1, 2, 3};
135 adjacency_list[2] = {0, 1, 2, 3, 4};
136 adjacency_list[3] = {1, 2, 3, 4, 5};
137 adjacency_list[4] = {2, 3, 4, 5, 6};
138 adjacency_list[5] = {3, 4, 5, 6, 7};
139 adjacency_list[6] = {4, 5, 6, 7, 8};
140 adjacency_list[7] = {5, 6, 7, 8, 9};
141 adjacency_list[8] = {6, 7, 8, 9, 0};
142 adjacency_list[9] = {7, 8, 9, 0, 1};
143
144 for (int i = 0; i < kNumNodes; ++i) {
145 for (int j = 0; j < kNumNodes; ++j) {
146 bool are_neighbors =
147 secret_sharing_harary_graph_test_internal::
148 GetNeighborIndexFromAdjacencyList(adjacency_list, i, j)
149 .value_or(-1) >= 0;
150 EXPECT_EQ(graph->AreNeighbors(i, j), are_neighbors) << i << "," << j;
151 }
152 }
153 }
154
TEST(SecretSharingHararyGraphTest,GetNeighborsIsCorrectInRandomHararyGraph)155 TEST(SecretSharingHararyGraphTest, GetNeighborsIsCorrectInRandomHararyGraph) {
156 SecretSharingGraphFactory factory;
157 auto graph = factory.CreateHararyGraph(kNumNodes, kDegree, kThreshold);
158
159 EXPECT_EQ(graph->GetNumNodes(), kNumNodes);
160 EXPECT_EQ(graph->GetDegree(), kDegree);
161 EXPECT_EQ(graph->GetThreshold(), kThreshold);
162
163 std::vector<int> p = graph->GetPermutationForTesting();
164 std::vector<std::vector<int>> adjacency_list(kNumNodes,
165 std::vector<int>(kDegree));
166 adjacency_list[p[0]] = {p[8], p[9], p[0], p[1], p[2]};
167 adjacency_list[p[1]] = {p[9], p[0], p[1], p[2], p[3]};
168 adjacency_list[p[2]] = {p[0], p[1], p[2], p[3], p[4]};
169 adjacency_list[p[3]] = {p[1], p[2], p[3], p[4], p[5]};
170 adjacency_list[p[4]] = {p[2], p[3], p[4], p[5], p[6]};
171 adjacency_list[p[5]] = {p[3], p[4], p[5], p[6], p[7]};
172 adjacency_list[p[6]] = {p[4], p[5], p[6], p[7], p[8]};
173 adjacency_list[p[7]] = {p[5], p[6], p[7], p[8], p[9]};
174 adjacency_list[p[8]] = {p[6], p[7], p[8], p[9], p[0]};
175 adjacency_list[p[9]] = {p[7], p[8], p[9], p[0], p[1]};
176
177 for (int i = 0; i < kNumNodes; ++i) {
178 for (int j = 0; j < kDegree; ++j) {
179 auto x = graph->GetNeighbor(i, j);
180 EXPECT_EQ(adjacency_list[i][j], x);
181 }
182 }
183 }
184
TEST(SecretSharingHararyGraphTest,GetNeighborsIsCorrectInDeterministicHararyGraph)185 TEST(SecretSharingHararyGraphTest,
186 GetNeighborsIsCorrectInDeterministicHararyGraph) {
187 SecretSharingGraphFactory factory;
188 auto graph = factory.CreateHararyGraph(kNumNodes, kDegree, kThreshold, false);
189
190 EXPECT_EQ(graph->GetNumNodes(), kNumNodes);
191 EXPECT_EQ(graph->GetDegree(), kDegree);
192 EXPECT_EQ(graph->GetThreshold(), kThreshold);
193
194 std::vector<int> p = graph->GetPermutationForTesting();
195 std::vector<std::vector<int>> adjacency_list(kNumNodes,
196 std::vector<int>(kDegree));
197 adjacency_list[0] = {8, 9, 0, 1, 2};
198 adjacency_list[1] = {9, 0, 1, 2, 3};
199 adjacency_list[2] = {0, 1, 2, 3, 4};
200 adjacency_list[3] = {1, 2, 3, 4, 5};
201 adjacency_list[4] = {2, 3, 4, 5, 6};
202 adjacency_list[5] = {3, 4, 5, 6, 7};
203 adjacency_list[6] = {4, 5, 6, 7, 8};
204 adjacency_list[7] = {5, 6, 7, 8, 9};
205 adjacency_list[8] = {6, 7, 8, 9, 0};
206 adjacency_list[9] = {7, 8, 9, 0, 1};
207
208 for (int i = 0; i < kNumNodes; ++i) {
209 for (int j = 0; j < kDegree; ++j) {
210 auto x = graph->GetNeighbor(i, j);
211 EXPECT_EQ(adjacency_list[i][j], x);
212 }
213 }
214 }
215
216 struct HararyGraphParams {
217 const std::string test_name;
218 const int kNumNodes;
219 const int kDegree;
220 const int kThreshold;
221 };
222
223 class SecretSharingHararyGraphParamTest_Valid
224 : public ::testing::TestWithParam<HararyGraphParams> {};
225
TEST_P(SecretSharingHararyGraphParamTest_Valid,GetNeighborIndexIsCorrectInHararyGraph)226 TEST_P(SecretSharingHararyGraphParamTest_Valid,
227 GetNeighborIndexIsCorrectInHararyGraph) {
228 const HararyGraphParams& graph_params = GetParam();
229 SecretSharingGraphFactory factory;
230 std::unique_ptr<SecretSharingGraph> graph = factory.CreateHararyGraph(
231 graph_params.kNumNodes, graph_params.kDegree, graph_params.kThreshold);
232
233 EXPECT_EQ(graph->GetNumNodes(), graph_params.kNumNodes);
234 EXPECT_EQ(graph->GetDegree(), graph_params.kDegree);
235 EXPECT_EQ(graph->GetThreshold(), graph_params.kThreshold);
236
237 for (int i = 0; i < graph_params.kNumNodes; ++i) {
238 for (int j = 0; j < graph_params.kDegree; ++j) {
239 auto x = graph->GetNeighbor(i, j);
240 EXPECT_EQ(graph->GetNeighborIndex(i, x), j);
241 }
242 }
243 }
244
245 INSTANTIATE_TEST_SUITE_P(
246 SecretSharingHararyGraphParamTests, SecretSharingHararyGraphParamTest_Valid,
247 ::testing::ValuesIn<HararyGraphParams>({
248 {"10_nodes__degree_1", 10, 1, 1},
249 {"10_nodes__degree_3", 10, 3, 2},
250 {"10_nodes__degree_5", 10, 5, 3},
251 {"100_nodes__degree_23", 100, 23, 10},
252 {"1000_nodes__degree_43", 1000, 43, 20},
253 {"10000_nodes__degree_300", 10000, 301, 100},
254 }),
255 [](const ::testing::TestParamInfo<
__anondd73ff660202(const ::testing::TestParamInfo< SecretSharingHararyGraphParamTest_Valid::ParamType>& info) 256 SecretSharingHararyGraphParamTest_Valid::ParamType>& info) {
257 return info.param.test_name;
258 });
259
260 class SecretSharingHararyGraphParamTest_InvalidDegree
261 : public ::testing::TestWithParam<HararyGraphParams> {};
262
TEST_P(SecretSharingHararyGraphParamTest_InvalidDegree,ConstructionFailsOnEvenDegree)263 TEST_P(SecretSharingHararyGraphParamTest_InvalidDegree,
264 ConstructionFailsOnEvenDegree) {
265 const HararyGraphParams& graph_params = GetParam();
266 SecretSharingGraphFactory factory;
267 EXPECT_DEATH(
268 factory.CreateHararyGraph(graph_params.kNumNodes, graph_params.kDegree,
269 graph_params.kThreshold),
270 absl::StrCat("degree must be odd, given value was ",
271 graph_params.kDegree));
272 }
273
274 INSTANTIATE_TEST_SUITE_P(
275 SecretSharingHararyGraphParamTests,
276 SecretSharingHararyGraphParamTest_InvalidDegree,
277 ::testing::ValuesIn<HararyGraphParams>({
278 {"10_nodes__degree_4", 10, 4, 2},
279 {"50_nodes__degree_20", 50, 20, 10},
280 }),
281 [](const ::testing::TestParamInfo<
__anondd73ff660302(const ::testing::TestParamInfo< SecretSharingHararyGraphParamTest_InvalidDegree::ParamType>& info) 282 SecretSharingHararyGraphParamTest_InvalidDegree::ParamType>& info) {
283 return info.param.test_name;
284 });
285
286 class SecretSharingHararyGraphParamTest_InvalidThreshold
287 : public ::testing::TestWithParam<HararyGraphParams> {};
288
TEST_P(SecretSharingHararyGraphParamTest_InvalidThreshold,ConstructionFailsOnThresholdOutOfObounds)289 TEST_P(SecretSharingHararyGraphParamTest_InvalidThreshold,
290 ConstructionFailsOnThresholdOutOfObounds) {
291 const HararyGraphParams& graph_params = GetParam();
292 SecretSharingGraphFactory factory;
293 EXPECT_DEATH(
294 factory.CreateHararyGraph(graph_params.kNumNodes, graph_params.kDegree,
295 graph_params.kThreshold),
296 "");
297 }
298
299 INSTANTIATE_TEST_SUITE_P(
300 SecretSharingHararyGraphParamTests,
301 SecretSharingHararyGraphParamTest_InvalidThreshold,
302 ::testing::ValuesIn<HararyGraphParams>({
303 {"10_nodes__degree_4_under", 10, 4, -1},
304 {"10_nodes__degree_4_over", 10, 4, 6},
305 {"50_nodes__degree_20_under", 50, 20, -1},
306 {"50_nodes__degree_20_over", 50, 20, 21},
307 }),
308 [](const ::testing::TestParamInfo<
__anondd73ff660402(const ::testing::TestParamInfo< SecretSharingHararyGraphParamTest_InvalidThreshold::ParamType>& info) 309 SecretSharingHararyGraphParamTest_InvalidThreshold::ParamType>& info) {
310 return info.param.test_name;
311 });
312
313 } // namespace
314 } // namespace secagg
315 } // namespace fcp
316