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
|
#include "../src/BloomFilter.h"
#include <cassert>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
/* From Wikipedia */
std::vector<std::string> commonHeaders = {
"A-IM",
"Accept",
"Accept-Charset",
"Accept-Datetime",
"Accept-Encoding",
"Accept-Language",
"Access-Control-Request-Method",
"Access-Control-Request-Headers",
"Authorization",
"Cache-Control",
"Connection",
"Content-Encoding",
"Content-Length",
"Content-MD5",
"Content-Type",
"Cookie",
"Date",
"Expect",
"Forwarded",
"From",
"Host",
"HTTP2-Settings",
"If-Match",
"If-Modified-Since",
"If-None-Match",
"If-Range",
"If-Unmodified-Since",
"Max-Forwards",
"Origin",
"Pragma",
"Proxy-Authorization",
"Range",
"Referer",
"TE",
"Trailer",
"Transfer-Encoding",
"User-Agent",
"Upgrade",
"Via",
"Warning",
/* Put common non-standard ones here */
};
int main() {
/* Lowercase everything */
std::transform(commonHeaders.begin(), commonHeaders.end(), commonHeaders.begin(), [](std::string &header) {
std::transform(header.begin(), header.end(), header.begin(), ::tolower);
return header;
});
uWS::BloomFilter bf;
unsigned int totalCollisions = 0;
/* One on one */
for (int i = 0; i < commonHeaders.size(); i++) {
bf.reset();
assert(bf.mightHave(commonHeaders[i]) == false);
bf.add(commonHeaders[i]);
assert(bf.mightHave(commonHeaders[i]) == true);
for (int j = i + 1; j < commonHeaders.size(); j++) {
if (bf.mightHave(commonHeaders[j])) {
std::cout << commonHeaders[i] << " collides with " << commonHeaders[j] << std::endl;
totalCollisions++;
}
}
}
/* We don't want any direct one-one-one collisions (please) */
std::cout << "Total collisions: " << totalCollisions << std::endl;
assert(totalCollisions == 0);
unsigned int totalFalsePositives = 0;
/* Add all except the one we test */
for (int i = 0; i < commonHeaders.size(); i++) {
bf.reset();
/* Add all headers but our */
for (int j = 0; j < commonHeaders.size(); j++) {
if (j != i) {
bf.add(commonHeaders[j]);
}
}
/* Do we have false positives? */
if (bf.mightHave(commonHeaders[i])) {
std::cout << commonHeaders[i] << " has false positives" << std::endl;
totalFalsePositives++;
}
}
/* It is totally fine to have a few false positives */
std::cout << "Total false positives: " << totalFalsePositives << std::endl;
assert(totalFalsePositives == 0);
}
|
