1// Copyright (c) 2011 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "chrome/browser/safe_browsing/safe_browsing_store.h"
6
7#include "testing/gtest/include/gtest/gtest.h"
8
9namespace {
10
11const SBFullHash kHash1 = SBFullHashForString("one");
12const SBFullHash kHash2 = SBFullHashForString("two");
13const SBFullHash kHash3 = SBFullHashForString("three");
14const SBFullHash kHash4 = SBFullHashForString("four");
15const SBFullHash kHash5 = SBFullHashForString("five");
16const SBFullHash kHash6 = SBFullHashForString("six");
17const SBFullHash kHash7 = SBFullHashForString("seven");
18
19const int kAddChunk1 = 1;  // Use different chunk numbers just in case.
20const int kSubChunk1 = 2;
21const int kAddChunk2 = 3;
22const int kSubChunk2 = 4;
23const int kAddChunk3 = 5;
24const int kSubChunk3 = 6;
25const int kAddChunk4 = 7;
26const int kSubChunk4 = 8;
27const int kAddChunk5 = 9;
28const int kSubChunk5 = 10;
29const int kAddChunk6 = 11;
30const int kAddChunk7 = 12;
31
32SBFullHash ModifyHashAfterPrefix(SBFullHash hash, unsigned char mask) {
33  hash.full_hash[sizeof(hash.full_hash) - 1] ^= mask;
34  return hash;
35}
36
37void ProcessHelper(SBAddPrefixes* add_prefixes,
38                   SBSubPrefixes* sub_prefixes,
39                   std::vector<SBAddFullHash>* add_full_hashes,
40                   std::vector<SBSubFullHash>* sub_full_hashes,
41                   const base::hash_set<int32>& add_chunks_deleted,
42                   const base::hash_set<int32>& sub_chunks_deleted) {
43  std::sort(add_prefixes->begin(), add_prefixes->end(),
44            SBAddPrefixLess<SBAddPrefix,SBAddPrefix>);
45  std::sort(sub_prefixes->begin(), sub_prefixes->end(),
46            SBAddPrefixLess<SBSubPrefix,SBSubPrefix>);
47  std::sort(add_full_hashes->begin(), add_full_hashes->end(),
48            SBAddPrefixHashLess<SBAddFullHash,SBAddFullHash>);
49  std::sort(sub_full_hashes->begin(), sub_full_hashes->end(),
50            SBAddPrefixHashLess<SBSubFullHash,SBSubFullHash>);
51
52  SBProcessSubs(add_prefixes, sub_prefixes, add_full_hashes, sub_full_hashes,
53                add_chunks_deleted, sub_chunks_deleted);
54}
55
56TEST(SafeBrowsingStoreTest, SBAddPrefixLess) {
57  // prefix dominates.
58  EXPECT_TRUE(SBAddPrefixLess(SBAddPrefix(11, 1), SBAddPrefix(10, 2)));
59  EXPECT_FALSE(SBAddPrefixLess(SBAddPrefix(10, 2), SBAddPrefix(11, 1)));
60
61  // After prefix, chunk_id.
62  EXPECT_TRUE(SBAddPrefixLess(SBAddPrefix(10, 1), SBAddPrefix(11, 1)));
63  EXPECT_FALSE(SBAddPrefixLess(SBAddPrefix(11, 1), SBAddPrefix(10, 1)));
64
65  // Equal is not less-than.
66  EXPECT_FALSE(SBAddPrefixLess(SBAddPrefix(10, 1), SBAddPrefix(10, 1)));
67}
68
69TEST(SafeBrowsingStoreTest, SBAddPrefixHashLess) {
70  // The first four bytes of SBFullHash can be read as a SBPrefix, which
71  // means that byte-ordering issues can come up.  To test this, |one|
72  // and |two| differ in the prefix, while |one| and |onetwo| have the
73  // same prefix, but differ in the byte after the prefix.
74  SBFullHash one, onetwo, two;
75  memset(&one, 0, sizeof(one));
76  memset(&onetwo, 0, sizeof(onetwo));
77  memset(&two, 0, sizeof(two));
78  one.prefix = 1;
79  one.full_hash[sizeof(SBPrefix)] = 1;
80  onetwo.prefix = 1;
81  onetwo.full_hash[sizeof(SBPrefix)] = 2;
82  two.prefix = 2;
83
84  // prefix dominates.
85  EXPECT_TRUE(SBAddPrefixHashLess(SBAddFullHash(11, one),
86                                  SBAddFullHash(10, two)));
87  EXPECT_FALSE(SBAddPrefixHashLess(SBAddFullHash(11, two),
88                                   SBAddFullHash(10, one)));
89
90  // After prefix, add_id.
91  EXPECT_TRUE(SBAddPrefixHashLess(SBAddFullHash(10, one),
92                                  SBAddFullHash(11, onetwo)));
93  EXPECT_FALSE(SBAddPrefixHashLess(SBAddFullHash(11, one),
94                                   SBAddFullHash(10, onetwo)));
95
96  // After add_id, full hash.
97  EXPECT_TRUE(SBAddPrefixHashLess(SBAddFullHash(10, one),
98                                  SBAddFullHash(10, onetwo)));
99  EXPECT_FALSE(SBAddPrefixHashLess(SBAddFullHash(10, onetwo),
100                                   SBAddFullHash(10, one)));
101
102  // Equal is not less-than.
103  EXPECT_FALSE(SBAddPrefixHashLess(SBAddFullHash(10, one),
104                                   SBAddFullHash(10, one)));
105}
106
107TEST(SafeBrowsingStoreTest, SBSubPrefixLess) {
108  // prefix dominates.
109  EXPECT_TRUE(SBAddPrefixLess(SBSubPrefix(12, 11, 1), SBSubPrefix(9, 10, 2)));
110  EXPECT_FALSE(SBAddPrefixLess(SBSubPrefix(12, 11, 2), SBSubPrefix(9, 10, 1)));
111
112  // After prefix, add_id.
113  EXPECT_TRUE(SBAddPrefixLess(SBSubPrefix(12, 9, 1), SBSubPrefix(9, 10, 1)));
114  EXPECT_FALSE(SBAddPrefixLess(SBSubPrefix(12, 10, 1), SBSubPrefix(9, 9, 1)));
115
116  // Equal is not less-than.
117  EXPECT_FALSE(SBAddPrefixLess(SBSubPrefix(12, 10, 1), SBSubPrefix(12, 10, 1)));
118
119  // chunk_id doesn't matter.
120}
121
122TEST(SafeBrowsingStoreTest, SBSubFullHashLess) {
123  SBFullHash one, onetwo, two;
124  memset(&one, 0, sizeof(one));
125  memset(&onetwo, 0, sizeof(onetwo));
126  memset(&two, 0, sizeof(two));
127  one.prefix = 1;
128  one.full_hash[sizeof(SBPrefix)] = 1;
129  onetwo.prefix = 1;
130  onetwo.full_hash[sizeof(SBPrefix)] = 2;
131  two.prefix = 2;
132
133  // prefix dominates.
134  EXPECT_TRUE(SBAddPrefixHashLess(SBSubFullHash(12, 11, one),
135                                  SBSubFullHash(9, 10, two)));
136  EXPECT_FALSE(SBAddPrefixHashLess(SBSubFullHash(12, 11, two),
137                                   SBSubFullHash(9, 10, one)));
138
139  // After prefix, add_id.
140  EXPECT_TRUE(SBAddPrefixHashLess(SBSubFullHash(12, 10, one),
141                                  SBSubFullHash(9, 11, onetwo)));
142  EXPECT_FALSE(SBAddPrefixHashLess(SBSubFullHash(12, 11, one),
143                                   SBSubFullHash(9, 10, onetwo)));
144
145  // After add_id, full_hash.
146  EXPECT_TRUE(SBAddPrefixHashLess(SBSubFullHash(12, 10, one),
147                                  SBSubFullHash(9, 10, onetwo)));
148  EXPECT_FALSE(SBAddPrefixHashLess(SBSubFullHash(12, 10, onetwo),
149                                   SBSubFullHash(9, 10, one)));
150
151  // Equal is not less-than.
152  EXPECT_FALSE(SBAddPrefixHashLess(SBSubFullHash(12, 10, one),
153                                   SBSubFullHash(9, 10, one)));
154}
155
156// SBProcessSubs does a lot of iteration, run through empty just to
157// make sure degenerate cases work.
158TEST(SafeBrowsingStoreTest, SBProcessSubsEmpty) {
159  SBAddPrefixes add_prefixes;
160  std::vector<SBAddFullHash> add_hashes;
161  SBSubPrefixes sub_prefixes;
162  std::vector<SBSubFullHash> sub_hashes;
163
164  const base::hash_set<int32> no_deletions;
165  SBProcessSubs(&add_prefixes, &sub_prefixes, &add_hashes, &sub_hashes,
166                no_deletions, no_deletions);
167  EXPECT_TRUE(add_prefixes.empty());
168  EXPECT_TRUE(sub_prefixes.empty());
169  EXPECT_TRUE(add_hashes.empty());
170  EXPECT_TRUE(sub_hashes.empty());
171}
172
173// Test that subs knock out adds.
174TEST(SafeBrowsingStoreTest, SBProcessSubsKnockout) {
175  // A full hash which shares prefix with another.
176  const SBFullHash kHash1mod = ModifyHashAfterPrefix(kHash1, 1);
177
178  // A second full-hash for the full-hash-sub test.
179  const SBFullHash kHash4mod = ModifyHashAfterPrefix(kHash4, 1);
180
181  SBAddPrefixes add_prefixes;
182  std::vector<SBAddFullHash> add_hashes;
183  SBSubPrefixes sub_prefixes;
184  std::vector<SBSubFullHash> sub_hashes;
185
186  // An add prefix plus a sub to knock it out.
187  add_prefixes.push_back(SBAddPrefix(kAddChunk1, kHash5.prefix));
188  sub_prefixes.push_back(SBSubPrefix(kSubChunk1, kAddChunk1, kHash5.prefix));
189
190  // Add hashes with same prefix, plus subs to knock them out.
191  add_hashes.push_back(SBAddFullHash(kAddChunk2, kHash1));
192  add_hashes.push_back(SBAddFullHash(kAddChunk2, kHash1mod));
193  sub_hashes.push_back(SBSubFullHash(kSubChunk2, kAddChunk2, kHash1));
194  sub_hashes.push_back(SBSubFullHash(kSubChunk2, kAddChunk2, kHash1mod));
195
196  // Adds with no corresponding sub.  Both items should be retained.
197  add_hashes.push_back(SBAddFullHash(kAddChunk6, kHash6));
198  add_prefixes.push_back(SBAddPrefix(kAddChunk7, kHash2.prefix));
199
200  // Subs with no corresponding add.  Both items should be retained.
201  sub_hashes.push_back(SBSubFullHash(kSubChunk3, kAddChunk3, kHash7));
202  sub_prefixes.push_back(SBSubPrefix(kSubChunk4, kAddChunk4, kHash3.prefix));
203
204  // Add hashes with the same prefix, with a sub that will knock one of them
205  // out.
206  add_hashes.push_back(SBAddFullHash(kAddChunk5, kHash4));
207  add_hashes.push_back(SBAddFullHash(kAddChunk5, kHash4mod));
208  sub_hashes.push_back(SBSubFullHash(kSubChunk5, kAddChunk5, kHash4mod));
209
210  const base::hash_set<int32> no_deletions;
211  ProcessHelper(&add_prefixes, &sub_prefixes, &add_hashes, &sub_hashes,
212                no_deletions, no_deletions);
213
214  ASSERT_EQ(1U, add_prefixes.size());
215  EXPECT_EQ(kAddChunk7, add_prefixes[0].chunk_id);
216  EXPECT_EQ(kHash2.prefix, add_prefixes[0].prefix);
217
218  ASSERT_EQ(2U, add_hashes.size());
219  EXPECT_EQ(kAddChunk5, add_hashes[0].chunk_id);
220  EXPECT_TRUE(SBFullHashEqual(kHash4, add_hashes[0].full_hash));
221  EXPECT_EQ(kAddChunk6, add_hashes[1].chunk_id);
222  EXPECT_TRUE(SBFullHashEqual(kHash6, add_hashes[1].full_hash));
223
224  ASSERT_EQ(1U, sub_prefixes.size());
225  EXPECT_EQ(kSubChunk4, sub_prefixes[0].chunk_id);
226  EXPECT_EQ(kAddChunk4, sub_prefixes[0].add_chunk_id);
227  EXPECT_EQ(kHash3.prefix, sub_prefixes[0].add_prefix);
228
229  ASSERT_EQ(1U, sub_hashes.size());
230  EXPECT_EQ(kSubChunk3, sub_hashes[0].chunk_id);
231  EXPECT_EQ(kAddChunk3, sub_hashes[0].add_chunk_id);
232  EXPECT_TRUE(SBFullHashEqual(kHash7, sub_hashes[0].full_hash));
233}
234
235// Test chunk deletions, and ordering of deletions WRT subs knocking
236// out adds.
237TEST(SafeBrowsingStoreTest, SBProcessSubsDeleteChunk) {
238  // A full hash which shares prefix with another.
239  const SBFullHash kHash1mod = ModifyHashAfterPrefix(kHash1, 1);
240
241  SBAddPrefixes add_prefixes;
242  std::vector<SBAddFullHash> add_hashes;
243  SBSubPrefixes sub_prefixes;
244  std::vector<SBSubFullHash> sub_hashes;
245
246  // An add prefix plus a sub to knock it out.
247  add_prefixes.push_back(SBAddPrefix(kAddChunk1, kHash5.prefix));
248  sub_prefixes.push_back(SBSubPrefix(kSubChunk1, kAddChunk1, kHash5.prefix));
249
250  // Add hashes with same prefix, plus subs to knock them out.
251  add_hashes.push_back(SBAddFullHash(kAddChunk1, kHash1));
252  add_hashes.push_back(SBAddFullHash(kAddChunk1, kHash1mod));
253  sub_hashes.push_back(SBSubFullHash(kSubChunk1, kAddChunk1, kHash1));
254  sub_hashes.push_back(SBSubFullHash(kSubChunk1, kAddChunk1, kHash1mod));
255
256  // Adds with no corresponding sub.  Both items should be retained.
257  add_hashes.push_back(SBAddFullHash(kAddChunk1, kHash6));
258  add_prefixes.push_back(SBAddPrefix(kAddChunk1, kHash2.prefix));
259
260  // Subs with no corresponding add.  Both items should be retained.
261  sub_hashes.push_back(SBSubFullHash(kSubChunk1, kAddChunk1, kHash7));
262  sub_prefixes.push_back(SBSubPrefix(kSubChunk1, kAddChunk1, kHash3.prefix));
263
264  // Subs apply before being deleted.
265  const base::hash_set<int32> no_deletions;
266  base::hash_set<int32> sub_deletions;
267  sub_deletions.insert(kSubChunk1);
268  ProcessHelper(&add_prefixes, &sub_prefixes, &add_hashes, &sub_hashes,
269                no_deletions, sub_deletions);
270
271  ASSERT_EQ(1U, add_prefixes.size());
272  EXPECT_EQ(kAddChunk1, add_prefixes[0].chunk_id);
273  EXPECT_EQ(kHash2.prefix, add_prefixes[0].prefix);
274
275  ASSERT_EQ(1U, add_hashes.size());
276  EXPECT_EQ(kAddChunk1, add_hashes[0].chunk_id);
277  EXPECT_TRUE(SBFullHashEqual(kHash6, add_hashes[0].full_hash));
278
279  EXPECT_TRUE(sub_prefixes.empty());
280  EXPECT_TRUE(sub_hashes.empty());
281
282  // Delete the adds, also.
283  base::hash_set<int32> add_deletions;
284  add_deletions.insert(kAddChunk1);
285  ProcessHelper(&add_prefixes, &sub_prefixes, &add_hashes, &sub_hashes,
286                add_deletions, no_deletions);
287
288  EXPECT_TRUE(add_prefixes.empty());
289  EXPECT_TRUE(add_hashes.empty());
290  EXPECT_TRUE(sub_prefixes.empty());
291  EXPECT_TRUE(sub_hashes.empty());
292}
293
294TEST(SafeBrowsingStoreTest, Y2K38) {
295  const base::Time now = base::Time::Now();
296  const base::Time future = now + base::TimeDelta::FromDays(3*365);
297
298  // TODO: Fix file format before 2035.
299  EXPECT_GT(static_cast<int32>(future.ToTimeT()), 0)
300    << " (int32)time_t is running out.";
301}
302
303}  // namespace
304