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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
#include "domain-lookup.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
static unsigned long range_rand(unsigned long min, unsigned long max)
{
unsigned long base_random, range, remainder, bucket;
base_random = rand();
if (RAND_MAX == base_random)
return range_rand(min, max);
range = max - min;
remainder = RAND_MAX % range;
bucket = RAND_MAX / range;
if (base_random < RAND_MAX - remainder)
return min + base_random / bucket;
return range_rand(min, max);
}
static char* make_domain(char **dictionary, size_t size, size_t max_components)
{
char *domain;
int i;
domain = malloc(512);
domain[0] = 0;
/* strcat can overflow. I don't care. */
for (i = 0; i < range_rand(2, max_components + 1); ++i) {
if (i > 0)
strcat(domain, ".");
strcat(domain, dictionary[range_rand(0, size)]);
}
return domain;
}
static void* old_find_dlt(char *domain, char **domains, size_t domains_size)
{
unsigned int namelen, matchlen, domainlen, i;
char *matchstart, *out;
namelen = strlen(domain);
matchlen = 0;
out = 0;
for (i = 0; i < domains_size; ++i) {
domainlen = strlen(domains[i]);
matchstart = domain + namelen - domainlen;
if (namelen >= domainlen &&
(domainlen == 0 || namelen == domainlen || *(matchstart - 1) == '.' ) &&
domainlen >= matchlen && !strcmp(matchstart, domains[i])) {
matchlen = domainlen;
out = domains[i];
}
}
return out;
}
#define DICTIONARY_INITIAL_SIZE 250000
#define DICTIONARY_TRUNCATED_SIZE 300
#define INSERTED_DOMAINS_SIZE 100000
#define QUERIED_DOMAINS_SIZE 100000
#define INSERTED_DOMAINS_COMPONENTS 3
#define QUERIED_DOMAINS_COMPONENTS 5
#define DICTIONARY_PATH "/usr/share/dict/words"
int main()
{
FILE *dictionary_file;
char **dictionary, **inserted_domains, **queried_domains;
void **verification_new, **verification_old;
char *word;
size_t dictionary_size, word_size, i;
struct domain_lookup_tree *head;
clock_t start, old_time, new_time;
srand(time(NULL) + 42);
printf("[+] Populating in-memory word list from " DICTIONARY_PATH ".\n");
dictionary = malloc(DICTIONARY_INITIAL_SIZE * sizeof(char *));
dictionary_file = fopen(DICTIONARY_PATH, "r");
if (!dictionary_file || !dictionary)
return 1;
for (dictionary_size = 0; dictionary_size < DICTIONARY_INITIAL_SIZE; ++dictionary_size) {
word_size = 256;
word = malloc(word_size);
if (!word)
return 1;
if (getline(&word, &word_size, dictionary_file) < 0)
break;
word_size = strlen(word);
if (word[word_size - 1] == '\n')
word[word_size - 1] = 0;
dictionary[dictionary_size] = word;
}
fclose(dictionary_file);
printf("[+] Truncating in-memory word list to %d random words.\n", DICTIONARY_TRUNCATED_SIZE);
for (i = 0; i < DICTIONARY_TRUNCATED_SIZE; ++i)
dictionary[i] = dictionary[range_rand(0, dictionary_size)];
printf("[+] Creating random lists of %d domains to insert and %d domains to query.\n", INSERTED_DOMAINS_SIZE, QUERIED_DOMAINS_SIZE);
inserted_domains = malloc(INSERTED_DOMAINS_SIZE * sizeof(char *));
queried_domains = malloc(QUERIED_DOMAINS_SIZE * sizeof(char *));
verification_new = malloc(QUERIED_DOMAINS_SIZE * sizeof(char *));
verification_old = malloc(QUERIED_DOMAINS_SIZE * sizeof(char *));
if (!inserted_domains || !queried_domains || !verification_new || !verification_old)
return 1;
for (i = 0; i < QUERIED_DOMAINS_SIZE; ++i)
queried_domains[i] = make_domain(dictionary, DICTIONARY_TRUNCATED_SIZE, QUERIED_DOMAINS_COMPONENTS);
for (i = 0; i < INSERTED_DOMAINS_SIZE; ++i)
inserted_domains[i] = make_domain(dictionary, DICTIONARY_TRUNCATED_SIZE, INSERTED_DOMAINS_COMPONENTS);
printf("[+] Populating domain lookup tree.\n");
head = init_dlt();
for (i = 0; i < INSERTED_DOMAINS_SIZE; ++i)
insert_dlt(head, inserted_domains[i], inserted_domains[i]);
printf("[+] Performing lookup benchmarks:\n");
start = clock();
for (i = 0; i < QUERIED_DOMAINS_SIZE; ++i)
verification_new[i] = find_dlt(head, queried_domains[i]);
new_time = clock() - start;
printf(" [*] New method took %.2f seconds.\n", (double)new_time / CLOCKS_PER_SEC);
start = clock();
for (i = 0; i < QUERIED_DOMAINS_SIZE; ++i)
verification_old[i] = old_find_dlt(queried_domains[i], inserted_domains, INSERTED_DOMAINS_SIZE);
old_time = clock() - start;
printf(" [*] Old method took %.2f seconds.\n", (double)old_time / CLOCKS_PER_SEC);
printf(" [*] The new method is %f times faster than the old method.\n", (double)old_time / (double)new_time);
printf("[+] Verifying that new and old methods produced identical results:\n");
for (i = 0; i < QUERIED_DOMAINS_SIZE; ++i) {
if (verification_old[i] != verification_new[i]) {
printf(" [!] New and old method produced different results!\n");
return 1;
}
}
printf(" [*] New and old methods produced the same results.\n");
return 0;
}
|
