Branch data Line data Source code
1 : : // $Id: Anon.cc 7075 2010-09-13 02:39:38Z vern $
2 : :
3 : : #include <stdlib.h>
4 : : #include <unistd.h>
5 : : #include <assert.h>
6 : : #include <sys/time.h>
7 : :
8 : : #include "util.h"
9 : : #include "net_util.h"
10 : : #include "md5.h"
11 : : #include "Anon.h"
12 : : #include "Val.h"
13 : : #include "NetVar.h"
14 : :
15 : :
16 : : AnonymizeIPAddr* ip_anonymizer[NUM_ADDR_ANONYMIZATION_METHODS] = {0};
17 : :
18 : 0 : static uint32 rand32()
19 : : {
20 : 0 : return ((random() & 0xffff) << 16) | (random() & 0xffff);
21 : : }
22 : :
23 : : // From tcpdpriv.
24 : 0 : int bi_ffs(uint32 value)
25 : : {
26 : 0 : int add = 0;
27 : : static uint8 bvals[] = {
28 : : 0, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1
29 : : };
30 : :
31 [ # # ]: 0 : if ( (value & 0xFFFF0000) == 0 )
32 : : {
33 [ # # ]: 0 : if ( value == 0 )
34 : : // Zero input ==> zero output.
35 : 0 : return 0;
36 : :
37 : 0 : add += 16;
38 : : }
39 : :
40 : : else
41 : 0 : value >>= 16;
42 : :
43 [ # # ]: 0 : if ( (value & 0xFF00) == 0 )
44 : 0 : add += 8;
45 : : else
46 : 0 : value >>= 8;
47 : :
48 [ # # ]: 0 : if ( (value & 0xF0) == 0 )
49 : 0 : add += 4;
50 : : else
51 : 0 : value >>= 4;
52 : :
53 : 0 : return add + bvals[value & 0xf];
54 : : }
55 : :
56 : : #define first_n_bit_mask(n) (~(0xFFFFFFFFU >> n))
57 : :
58 : 0 : ipaddr32_t AnonymizeIPAddr::Anonymize(ipaddr32_t addr)
59 : : {
60 : 0 : map<ipaddr32_t, ipaddr32_t>::iterator p = mapping.find(addr);
61 [ # # ]: 0 : if ( p != mapping.end() )
62 : 0 : return p->second;
63 : : else
64 : : {
65 : 0 : ipaddr32_t new_addr = anonymize(addr);
66 : 0 : mapping[addr] = new_addr;
67 : :
68 : 0 : return new_addr;
69 : : }
70 : : }
71 : :
72 : 0 : int AnonymizeIPAddr::PreserveNet(ipaddr32_t input)
73 : : {
74 [ # # # # ]: 0 : switch ( addr_to_class(ntohl(input)) ) {
75 : : case 'A':
76 : 0 : return PreservePrefix(input, 8);
77 : : case 'B':
78 : 0 : return PreservePrefix(input, 16);
79 : : case 'C':
80 : 0 : return PreservePrefix(input, 24);
81 : : default:
82 : 0 : return 0;
83 : : }
84 : : }
85 : :
86 : 0 : ipaddr32_t AnonymizeIPAddr_Seq::anonymize(ipaddr32_t /* input */)
87 : : {
88 : 0 : return htonl(seq++);
89 : : }
90 : :
91 : 0 : ipaddr32_t AnonymizeIPAddr_RandomMD5::anonymize(ipaddr32_t input)
92 : : {
93 : : uint8 digest[16];
94 : 0 : ipaddr32_t output = 0;
95 : :
96 : 0 : hmac_md5(sizeof(input), (u_char*)(&input), digest);
97 : :
98 [ # # ]: 0 : for ( int i = 0; i < 4; ++i )
99 : 0 : output = (output << 8) | digest[i];
100 : :
101 : 0 : return output;
102 : : }
103 : :
104 : :
105 : : // This code is from "On the Design and Performance of Prefix-Preserving
106 : : // IP Traffic Trace Anonymization", by Xu et al (IMW 2001)
107 : : //
108 : : // http://www.imconf.net/imw-2001/proceedings.html
109 : :
110 : 0 : ipaddr32_t AnonymizeIPAddr_PrefixMD5::anonymize(ipaddr32_t input)
111 : : {
112 : : uint8 digest[16];
113 : 0 : ipaddr32_t prefix_mask = 0xffffffff;
114 : 0 : input = ntohl(input);
115 : 0 : ipaddr32_t output = input;
116 : :
117 [ # # ]: 0 : for ( int i = 0; i < 32; ++i )
118 : : {
119 : : // PAD(x_0 ... x_{i-1}) = x_0 ... x_{i-1} 1 0 ... 0 .
120 : 0 : prefix.len = htonl(i + 1);
121 : 0 : prefix.prefix = htonl((input & ~(prefix_mask>>i)) | (1<<(31-i)));
122 : :
123 : : // HK(PAD(x_0 ... x_{i-1})).
124 : 0 : hmac_md5(sizeof(prefix), (u_char*) &prefix, digest);
125 : :
126 : : // f_{i-1} = LSB(HK(PAD(x_0 ... x_{i-1}))).
127 : 0 : ipaddr32_t bit_mask = (digest[0] & 1) << (31-i);
128 : :
129 : : // x_i' = x_i ^ f_{i-1}.
130 : 0 : output ^= bit_mask;
131 : : }
132 : :
133 : 0 : return htonl(output);
134 : : }
135 : :
136 : 0 : AnonymizeIPAddr_A50::~AnonymizeIPAddr_A50()
137 : : {
138 [ # # ][ # # ]: 0 : for ( unsigned int i = 0; i < blocks.size(); ++i )
[ # # ]
139 [ # # ][ # # ]: 0 : delete [] blocks[i];
[ # # ]
140 : :
141 : 0 : blocks.clear();
142 [ # # ][ # # ]: 0 : }
[ # # ]
143 : :
144 : 0 : void AnonymizeIPAddr_A50::init()
145 : : {
146 : 0 : root = next_free_node = 0;
147 : :
148 : : // Prepare special nodes for 0.0.0.0 and 255.255.255.255.
149 : 0 : memset(&special_nodes[0], 0, sizeof(special_nodes));
150 : 0 : special_nodes[0].input = special_nodes[0].output = 0;
151 : 0 : special_nodes[1].input = special_nodes[1].output = 0xFFFFFFFF;
152 : :
153 : 0 : before_anonymization = 1;
154 : 0 : }
155 : :
156 : 0 : int AnonymizeIPAddr_A50::PreservePrefix(ipaddr32_t input, int num_bits)
157 : : {
158 : 0 : DEBUG_MSG("%s/%d\n", dotted_addr(input), num_bits);
159 : :
160 [ # # ]: 0 : if ( ! before_anonymization )
161 : : {
162 : 0 : run_time("prefix perservation specified after anonymization begun");
163 : 0 : return 0;
164 : : }
165 : :
166 : 0 : input = ntohl(input);
167 : :
168 : : // Sanitize input.
169 : 0 : input = input & first_n_bit_mask(num_bits);
170 : :
171 : 0 : Node* n = find_node(input);
172 : :
173 : : // Preserve the first num_bits bits of addr.
174 [ # # ]: 0 : if ( num_bits == 32 )
175 : 0 : n->output = input;
176 : :
177 [ # # ]: 0 : else if ( num_bits > 0 )
178 : : {
179 : : assert((0xFFFFFFFFU >> 1) == 0x7FFFFFFFU);
180 : 0 : uint32 suffix_mask = (0xFFFFFFFFU >> num_bits);
181 : 0 : uint32 prefix_mask = ~suffix_mask;
182 : 0 : n->output = (input & prefix_mask) | (rand32() & suffix_mask);
183 : : }
184 : :
185 : 0 : return 1;
186 : : }
187 : :
188 : 0 : ipaddr32_t AnonymizeIPAddr_A50::anonymize(ipaddr32_t a)
189 : : {
190 : 0 : before_anonymization = 0;
191 : 0 : new_mapping = 0;
192 : :
193 [ # # ]: 0 : if ( Node* n = find_node(ntohl(a)) )
194 : : {
195 : 0 : ipaddr32_t output = htonl(n->output);
196 : 0 : return output;
197 : : }
198 : : else
199 : 0 : return 0;
200 : : }
201 : :
202 : 0 : AnonymizeIPAddr_A50::Node* AnonymizeIPAddr_A50::new_node_block()
203 : : {
204 [ # # ]: 0 : assert(! next_free_node);
205 : :
206 : 0 : int block_size = 1024;
207 : 0 : Node* block = new Node[block_size];
208 [ # # ]: 0 : if ( ! block )
209 : 0 : internal_error("out of memory!");
210 : :
211 : 0 : blocks.push_back(block);
212 : :
213 [ # # ]: 0 : for ( int i = 1; i < block_size - 1; ++i )
214 : 0 : block[i].child[0] = &block[i+1];
215 : :
216 : 0 : block[block_size - 1].child[0] = 0;
217 : 0 : next_free_node = &block[1];
218 : :
219 : 0 : return &block[0];
220 : : }
221 : :
222 : 0 : inline AnonymizeIPAddr_A50::Node* AnonymizeIPAddr_A50::new_node()
223 : : {
224 : 0 : new_mapping = 1;
225 : :
226 [ # # ]: 0 : if ( next_free_node )
227 : : {
228 : 0 : Node* n = next_free_node;
229 : 0 : next_free_node = n->child[0];
230 : 0 : return n;
231 : : }
232 : : else
233 : 0 : return new_node_block();
234 : : }
235 : :
236 : 0 : inline void AnonymizeIPAddr_A50::free_node(Node *n)
237 : : {
238 : 0 : n->child[0] = next_free_node;
239 : 0 : next_free_node = n;
240 : 0 : }
241 : :
242 : 0 : ipaddr32_t AnonymizeIPAddr_A50::make_output(ipaddr32_t old_output, int swivel) const
243 : : {
244 : : // -A50 anonymization
245 [ # # ]: 0 : if ( swivel == 32 )
246 : 0 : return old_output ^ 1;
247 : : else
248 : : {
249 : : // Bits up to swivel are unchanged; bit swivel is flipped.
250 : : ipaddr32_t known_part =
251 : 0 : ((old_output >> (32 - swivel)) ^ 1) << (32 - swivel);
252 : :
253 : : // Remainder of bits are random.
254 : 0 : return known_part | ((rand32() & 0x7FFFFFFF) >> swivel);
255 : : }
256 : : }
257 : :
258 : 0 : AnonymizeIPAddr_A50::Node* AnonymizeIPAddr_A50::make_peer(ipaddr32_t a, Node* n)
259 : : {
260 [ # # ][ # # ]: 0 : if ( a == 0 || a == 0xFFFFFFFFU )
261 : 0 : internal_error("0.0.0.0 and 255.255.255.255 should never get into the tree");
262 : :
263 : : // Become a peer.
264 : : // Algorithm: create two nodes, the two peers. Leave orig node as
265 : : // the parent of the two new ones.
266 : :
267 : : Node* down[2];
268 : :
269 [ # # ]: 0 : if ( ! (down[0] = new_node()) )
270 : 0 : return 0;
271 : :
272 [ # # ]: 0 : if ( ! (down[1] = new_node()) )
273 : : {
274 : 0 : free_node(down[0]);
275 : 0 : return 0;
276 : : }
277 : :
278 : : // swivel is first bit 'a' and 'old->input' differ.
279 : 0 : int swivel = bi_ffs(a ^ n->input);
280 : :
281 : : // bitvalue is the value of that bit of 'a'.
282 : 0 : int bitvalue = (a >> (32 - swivel)) & 1;
283 : :
284 : 0 : down[bitvalue]->input = a;
285 : 0 : down[bitvalue]->output = make_output(n->output, swivel);
286 : 0 : down[bitvalue]->child[0] = down[bitvalue]->child[1] = 0;
287 : :
288 : 0 : *down[1 - bitvalue] = *n; // copy orig node down one level
289 : :
290 : 0 : n->input = down[1]->input; // NB: 1s to the right (0s to the left)
291 : 0 : n->output = down[1]->output;
292 : 0 : n->child[0] = down[0]; // point to children
293 : 0 : n->child[1] = down[1];
294 : :
295 : 0 : return down[bitvalue];
296 : : }
297 : :
298 : 0 : AnonymizeIPAddr_A50::Node* AnonymizeIPAddr_A50::find_node(ipaddr32_t a)
299 : : {
300 : : // Watch out for special IP addresses, which never make it
301 : : // into the tree.
302 [ # # ][ # # ]: 0 : if ( a == 0 || a == 0xFFFFFFFFU )
303 : 0 : return &special_nodes[a & 1];
304 : :
305 [ # # ]: 0 : if ( ! root )
306 : : {
307 : 0 : root = new_node();
308 : 0 : root->input = a;
309 : 0 : root->output = rand32();
310 : 0 : root->child[0] = root->child[1] = 0;
311 : :
312 : 0 : return root;
313 : : }
314 : :
315 : : // Straight from tcpdpriv.
316 : 0 : Node* n = root;
317 [ # # ]: 0 : while ( n )
318 : : {
319 [ # # ]: 0 : if ( n->input == a )
320 : 0 : return n;
321 : :
322 [ # # ]: 0 : if ( ! n->child[0] )
323 : 0 : n = make_peer(a, n);
324 : :
325 : : else
326 : : {
327 : : // swivel is the first bit in which the two children
328 : : // differ.
329 : : int swivel =
330 : 0 : bi_ffs(n->child[0]->input ^ n->child[1]->input);
331 : :
332 [ # # ]: 0 : if ( bi_ffs(a ^ n->input) < swivel )
333 : : // Input differs earlier.
334 : 0 : n = make_peer(a, n);
335 : :
336 [ # # ]: 0 : else if ( a & (1 << (32 - swivel)) )
337 : 0 : n = n->child[1];
338 : :
339 : : else
340 : 0 : n = n->child[0];
341 : : }
342 : : }
343 : :
344 : 0 : internal_error("out of memory!");
345 : : return 0;
346 : : }
347 : :
348 : 0 : void init_ip_addr_anonymizers()
349 : : {
350 : 0 : ip_anonymizer[KEEP_ORIG_ADDR] = 0;
351 : 0 : ip_anonymizer[SEQUENTIALLY_NUMBERED] = new AnonymizeIPAddr_Seq();
352 : 0 : ip_anonymizer[RANDOM_MD5] = new AnonymizeIPAddr_RandomMD5();
353 : 0 : ip_anonymizer[PREFIX_PRESERVING_A50] = new AnonymizeIPAddr_A50();
354 : 0 : ip_anonymizer[PREFIX_PRESERVING_MD5] = new AnonymizeIPAddr_PrefixMD5();
355 : 0 : }
356 : :
357 : 0 : ipaddr32_t anonymize_ip(ipaddr32_t ip, enum ip_addr_anonymization_class_t cl)
358 : : {
359 : 0 : TableVal* preserve_addr = 0;
360 : 0 : AddrVal addr(ip);
361 : :
362 : 0 : int method = -1;
363 : :
364 [ # # # ]: 0 : switch ( cl ) {
365 : : case ORIG_ADDR: // client address
366 : 0 : preserve_addr = preserve_orig_addr;
367 : 0 : method = orig_addr_anonymization;
368 : 0 : break;
369 : :
370 : : case RESP_ADDR: // server address
371 : 0 : preserve_addr = preserve_resp_addr;
372 : 0 : method = resp_addr_anonymization;
373 : 0 : break;
374 : :
375 : : default:
376 : 0 : preserve_addr = preserve_other_addr;
377 : 0 : method = other_addr_anonymization;
378 : : break;
379 : : }
380 : :
381 : 0 : ipaddr32_t new_ip = 0;
382 : :
383 [ # # ][ # # ]: 0 : if ( preserve_addr && preserve_addr->Lookup(&addr) )
[ # # ]
384 : 0 : new_ip = ip;
385 : :
386 [ # # ][ # # ]: 0 : else if ( method >= 0 && method < NUM_ADDR_ANONYMIZATION_METHODS )
387 : : {
388 [ # # ]: 0 : if ( method == KEEP_ORIG_ADDR )
389 : 0 : new_ip = ip;
390 : :
391 [ # # ]: 0 : else if ( ! ip_anonymizer[method] )
392 : 0 : internal_error("IP anonymizer not initialized");
393 : :
394 : : else
395 : 0 : new_ip = ip_anonymizer[method]->Anonymize(ip);
396 : : }
397 : :
398 : : else
399 : 0 : internal_error("invalid IP anonymization method");
400 : :
401 : : #ifdef LOG_ANONYMIZATION_MAPPING
402 : 0 : log_anonymization_mapping(ip, new_ip);
403 : : #endif
404 : 0 : return new_ip;
405 : : }
406 : :
407 : : #ifdef LOG_ANONYMIZATION_MAPPING
408 : :
409 : : #include "NetVar.h"
410 : : #include "Event.h"
411 : :
412 : 0 : void log_anonymization_mapping(ipaddr32_t input, ipaddr32_t output)
413 : : {
414 [ # # ]: 0 : if ( anonymization_mapping )
415 : : {
416 : 0 : val_list* vl = new val_list;
417 : 0 : vl->append(new AddrVal(input));
418 : 0 : vl->append(new AddrVal(output));
419 : 0 : mgr.QueueEvent(anonymization_mapping, vl);
420 : : }
421 [ + - ][ + - ]: 6 : }
422 : 3 :
423 : : #endif
|