bloom_filter_unittest.cc revision 3345a6884c488ff3a535c2c9acdd33d74b37e311 
1// Copyright (c) 2009 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/bloom_filter.h"
6
7#include <limits.h>
8
9#include <set>
10#include <vector>
11
12#include "base/file_util.h"
13#include "base/logging.h"
14#include "base/path_service.h"
15#include "base/rand_util.h"
16#include "base/ref_counted.h"
17#include "base/string_util.h"
18#include "testing/gtest/include/gtest/gtest.h"
19
20namespace {
21
22SBPrefix GenHash() {
23  return static_cast<SBPrefix>(base::RandUint64());
24}
25
26}
27
28TEST(SafeBrowsingBloomFilter, BloomFilterUse) {
29  // Use a small number for unit test so it's not slow.
30  int count = 1000;
31
32  // Build up the bloom filter.
33  scoped_refptr<BloomFilter> filter =
34      new BloomFilter(count * BloomFilter::kBloomFilterSizeRatio);
35
36  typedef std::set<SBPrefix> Values;
37  Values values;
38  for (int i = 0; i < count; ++i) {
39    SBPrefix value = GenHash();
40    values.insert(value);
41    filter->Insert(value);
42  }
43
44  // Check serialization works.
45  char* data_copy = new char[filter->size()];
46  memcpy(data_copy, filter->data(), filter->size());
47  scoped_refptr<BloomFilter> filter_copy =
48      new BloomFilter(data_copy, filter->size(), filter->hash_keys_);
49
50  // Check no false negatives by ensuring that every time we inserted exists.
51  for (Values::const_iterator i = values.begin(); i != values.end(); ++i)
52    EXPECT_TRUE(filter_copy->Exists(*i));
53
54  // Check false positive error rate by checking the same number of items that
55  // we inserted, but of different values, and calculating what percentage are
56  // "found".
57  int found_count = 0;
58  int checked = 0;
59  while (true) {
60    SBPrefix value = GenHash();
61    if (values.count(value))
62      continue;
63
64    if (filter_copy->Exists(value))
65      found_count++;
66
67    checked++;
68    if (checked == count)
69      break;
70  }
71
72  // The FP rate should be 1.2%.  Keep a large margin of error because we don't
73  // want to fail this test because we happened to randomly pick a lot of FPs.
74  double fp_rate = found_count * 100.0 / count;
75  CHECK(fp_rate < 5.0);
76
77  SB_DLOG(INFO) << "For safe browsing bloom filter of size " << count <<
78      ", the FP rate was " << fp_rate << " %";
79}
80
81// Test that we can read and write the bloom filter file.
82TEST(SafeBrowsingBloomFilter, BloomFilterFile) {
83  // Create initial filter.
84  const int kTestEntries = BloomFilter::kBloomFilterMinSize;
85  scoped_refptr<BloomFilter> filter_write =
86      new BloomFilter(kTestEntries * BloomFilter::kBloomFilterSizeRatio);
87
88  for (int i = 0; i < kTestEntries; ++i)
89    filter_write->Insert(GenHash());
90
91  // Remove any left over test filters and serialize.
92  FilePath filter_path;
93  PathService::Get(base::DIR_TEMP, &filter_path);
94  filter_path = filter_path.AppendASCII("SafeBrowsingTestFilter");
95  file_util::Delete(filter_path, false);
96  ASSERT_FALSE(file_util::PathExists(filter_path));
97  ASSERT_TRUE(filter_write->WriteFile(filter_path));
98
99  // Create new empty filter and load from disk.
100  BloomFilter* filter = BloomFilter::LoadFile(filter_path);
101  ASSERT_TRUE(filter != NULL);
102  scoped_refptr<BloomFilter> filter_read = filter;
103
104  // Check data consistency.
105  EXPECT_EQ(filter_write->hash_keys_.size(), filter_read->hash_keys_.size());
106
107  for (size_t i = 0; i < filter_write->hash_keys_.size(); ++i)
108    EXPECT_EQ(filter_write->hash_keys_[i], filter_read->hash_keys_[i]);
109
110  EXPECT_EQ(filter_write->size(), filter_read->size());
111
112  EXPECT_EQ(0,
113      memcmp(filter_write->data(), filter_read->data(), filter_read->size()));
114
115  file_util::Delete(filter_path, false);
116}
117