1 /*
2 * scamper_dealias.c
3 *
4 * $Id: scamper_dealias.c,v 1.53 2021/08/28 21:36:31 mjl Exp $
5 *
6 * Copyright (C) 2008-2010 The University of Waikato
7 * Copyright (C) 2012-2013 The Regents of the University of California
8 * Copyright (C) 2021 Matthew Luckie
9 * Author: Matthew Luckie
10 *
11 * This code implements alias resolution techniques published by others
12 * which require the network to be probed; the author of each technique
13 * is detailed with its data structures.
14 *
15 * This program is free software; you can redistribute it and/or modify
16 * it under the terms of the GNU General Public License as published by
17 * the Free Software Foundation, version 2.
18 *
19 * This program is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU General Public License for more details.
23 *
24 * You should have received a copy of the GNU General Public License
25 * along with this program; if not, write to the Free Software
26 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
27 *
28 */
29
30 #ifdef HAVE_CONFIG_H
31 #include "config.h"
32 #endif
33 #include "internal.h"
34
35 #include "scamper_addr.h"
36 #include "scamper_list.h"
37 #include "scamper_icmpext.h"
38 #include "scamper_dealias.h"
39 #include "utils.h"
40
scamper_dealias_ipid(const scamper_dealias_probe_t ** probes,uint32_t probec,scamper_dealias_ipid_t * ipid)41 int scamper_dealias_ipid(const scamper_dealias_probe_t **probes,
42 uint32_t probec, scamper_dealias_ipid_t *ipid)
43 {
44 const scamper_dealias_probe_t *p;
45 const scamper_dealias_reply_t *r;
46 uint32_t bs_mind = 0x30000;
47 uint32_t bs_maxd = 0;
48 uint32_t bs_sum = 0;
49 uint32_t mind = 0x30000;
50 uint32_t maxd = 0;
51 uint32_t sum = 0;
52 uint32_t diff;
53 uint32_t cur, prev;
54 uint32_t i;
55 int echo, cons;
56
57 ipid->type = SCAMPER_DEALIAS_IPID_UNKNOWN;
58
59 echo = 1;
60 cons = 1;
61
62 if(probec == 0 || probes[0] == NULL || probes[0]->replyc != 1)
63 return 0;
64
65 prev = probes[0]->replies[0]->ipid;
66 for(i=1; i<probec; i++)
67 {
68 if((p = probes[i]) == NULL)
69 return 0;
70
71 if(p->replyc != 1)
72 return 0;
73
74 if((r = p->replies[0]) == NULL)
75 return 0;
76
77 /* non byteswap case */
78 cur = r->ipid;
79 if(cur > prev)
80 diff = cur - prev;
81 else if(cur < prev)
82 diff = 0x10000 + cur - prev;
83 else
84 diff = 0;
85 if(diff < mind)
86 mind = diff;
87 if(diff > maxd)
88 maxd = diff;
89 sum += diff;
90
91 /* byteswap case */
92 cur = byteswap16(r->ipid);
93 prev = byteswap16(prev);
94 if(cur > prev)
95 diff = cur - prev;
96 else if(cur < prev)
97 diff = 0x10000 + cur - prev;
98 else
99 diff = 0;
100 if(diff < bs_mind)
101 bs_mind = diff;
102 if(diff > maxd)
103 bs_maxd = diff;
104 bs_sum += diff;
105
106 if(echo != 0 && p->ipid != r->ipid && p->ipid != byteswap16(r->ipid))
107 echo = 0;
108 else if(cons != 0 && probes[i-1]->replies[0]->ipid != r->ipid)
109 cons = 0;
110
111 prev = r->ipid;
112 }
113
114 if(cons == 0 && echo == 0)
115 {
116 /* figure out which byte ordering best explains the sequence */
117 if(sum < bs_sum)
118 {
119 ipid->mind = mind;
120 ipid->maxd = maxd;
121 }
122 else
123 {
124 ipid->mind = bs_mind;
125 ipid->maxd = bs_maxd;
126 }
127 ipid->type = SCAMPER_DEALIAS_IPID_INCR;
128 }
129 else if(cons != 0)
130 {
131 if(probes[0]->replies[0]->ipid == 0)
132 ipid->type = SCAMPER_DEALIAS_IPID_ZERO;
133 else
134 ipid->type = SCAMPER_DEALIAS_IPID_CONST;
135 }
136 else if(echo != 0)
137 {
138 ipid->type = SCAMPER_DEALIAS_IPID_ECHO;
139 }
140
141 return 0;
142 }
143
dealias_probedef_free(scamper_dealias_probedef_t * probedef)144 static void dealias_probedef_free(scamper_dealias_probedef_t *probedef)
145 {
146 if(probedef->src != NULL)
147 {
148 scamper_addr_free(probedef->src);
149 probedef->src = NULL;
150 }
151 if(probedef->dst != NULL)
152 {
153 scamper_addr_free(probedef->dst);
154 probedef->dst = NULL;
155 }
156 return;
157 }
158
dealias_mercator_free(void * data)159 static void dealias_mercator_free(void *data)
160 {
161 scamper_dealias_mercator_t *mercator = (scamper_dealias_mercator_t *)data;
162 dealias_probedef_free(&mercator->probedef);
163 free(mercator);
164 return;
165 }
166
dealias_ally_free(void * data)167 static void dealias_ally_free(void *data)
168 {
169 scamper_dealias_ally_t *ally = (scamper_dealias_ally_t *)data;
170 dealias_probedef_free(&ally->probedefs[0]);
171 dealias_probedef_free(&ally->probedefs[1]);
172 free(ally);
173 return;
174 }
175
dealias_radargun_free(void * data)176 static void dealias_radargun_free(void *data)
177 {
178 scamper_dealias_radargun_t *radargun = (scamper_dealias_radargun_t *)data;
179 uint32_t i;
180
181 if(radargun->probedefs != NULL)
182 {
183 for(i=0; i<radargun->probedefc; i++)
184 {
185 dealias_probedef_free(&radargun->probedefs[i]);
186 }
187 free(radargun->probedefs);
188 }
189 free(radargun);
190 return;
191 }
192
dealias_prefixscan_free(void * data)193 static void dealias_prefixscan_free(void *data)
194 {
195 scamper_dealias_prefixscan_t *prefixscan = data;
196 uint16_t i;
197
198 if(prefixscan == NULL)
199 return;
200
201 if(prefixscan->a != NULL) scamper_addr_free(prefixscan->a);
202 if(prefixscan->b != NULL) scamper_addr_free(prefixscan->b);
203 if(prefixscan->ab != NULL) scamper_addr_free(prefixscan->ab);
204
205 if(prefixscan->xs != NULL)
206 {
207 for(i=0; i<prefixscan->xc; i++)
208 if(prefixscan->xs[i] != NULL)
209 scamper_addr_free(prefixscan->xs[i]);
210 free(prefixscan->xs);
211 }
212
213 if(prefixscan->probedefs != NULL)
214 {
215 for(i=0; i<prefixscan->probedefc; i++)
216 dealias_probedef_free(&prefixscan->probedefs[i]);
217 free(prefixscan->probedefs);
218 }
219
220 free(prefixscan);
221
222 return;
223 }
224
dealias_bump_free(void * data)225 static void dealias_bump_free(void *data)
226 {
227 scamper_dealias_bump_t *bump = (scamper_dealias_bump_t *)data;
228 dealias_probedef_free(&bump->probedefs[0]);
229 dealias_probedef_free(&bump->probedefs[1]);
230 free(bump);
231 return;
232 }
233
scamper_dealias_probedef_method_tostr(const scamper_dealias_probedef_t * d,char * b,size_t l)234 const char *scamper_dealias_probedef_method_tostr(const scamper_dealias_probedef_t *d,
235 char *b, size_t l)
236 {
237 static const char *m[] = {
238 NULL,
239 "icmp-echo",
240 "tcp-ack",
241 "udp",
242 "tcp-ack-sport",
243 "udp-dport",
244 "tcp-syn-sport",
245 };
246 if(d->method >= sizeof(m) / sizeof(char *) || m[d->method] == NULL)
247 {
248 snprintf(b, l, "%d", d->method);
249 return b;
250 }
251 return m[d->method];
252 }
253
scamper_dealias_probedef_alloc(void)254 scamper_dealias_probedef_t *scamper_dealias_probedef_alloc(void)
255 {
256 size_t size = sizeof(scamper_dealias_probedef_t);
257 return (scamper_dealias_probedef_t *)malloc_zero(size);
258 }
259
scamper_dealias_probedef_free(scamper_dealias_probedef_t * probedef)260 void scamper_dealias_probedef_free(scamper_dealias_probedef_t *probedef)
261 {
262 dealias_probedef_free(probedef);
263 free(probedef);
264 return;
265 }
266
scamper_dealias_probe_alloc(void)267 scamper_dealias_probe_t *scamper_dealias_probe_alloc(void)
268 {
269 size_t size = sizeof(scamper_dealias_probe_t);
270 return (scamper_dealias_probe_t *)malloc_zero(size);
271 }
272
scamper_dealias_probe_free(scamper_dealias_probe_t * probe)273 void scamper_dealias_probe_free(scamper_dealias_probe_t *probe)
274 {
275 uint16_t i;
276
277 if(probe->replies != NULL)
278 {
279 for(i=0; i<probe->replyc; i++)
280 {
281 if(probe->replies[i] != NULL)
282 scamper_dealias_reply_free(probe->replies[i]);
283 }
284 free(probe->replies);
285 }
286
287 free(probe);
288 return;
289 }
290
scamper_dealias_reply_alloc(void)291 scamper_dealias_reply_t *scamper_dealias_reply_alloc(void)
292 {
293 size_t size = sizeof(scamper_dealias_reply_t);
294 return (scamper_dealias_reply_t *)malloc_zero(size);
295 }
296
scamper_dealias_reply_free(scamper_dealias_reply_t * reply)297 void scamper_dealias_reply_free(scamper_dealias_reply_t *reply)
298 {
299 if(reply->src != NULL)
300 scamper_addr_free(reply->src);
301 free(reply);
302 return;
303 }
304
scamper_dealias_reply_count(const scamper_dealias_t * dealias)305 uint32_t scamper_dealias_reply_count(const scamper_dealias_t *dealias)
306 {
307 uint32_t rc = 0;
308 uint16_t i;
309 for(i=0; i<dealias->probec; i++)
310 {
311 if(dealias->probes[i] != NULL)
312 rc += dealias->probes[i]->replyc;
313 }
314 return rc;
315 }
316
dealias_probe_tx_cmp(const scamper_dealias_probe_t * a,const scamper_dealias_probe_t * b)317 static int dealias_probe_tx_cmp(const scamper_dealias_probe_t *a,
318 const scamper_dealias_probe_t *b)
319 {
320 return timeval_cmp(&a->tx, &b->tx);
321 }
322
dealias_probe_seq_cmp(const scamper_dealias_probe_t * a,const scamper_dealias_probe_t * b)323 static int dealias_probe_seq_cmp(const scamper_dealias_probe_t *a,
324 const scamper_dealias_probe_t *b)
325 {
326 if(a->seq < b->seq)
327 return -1;
328 if(a->seq > b->seq)
329 return 1;
330 if(a->def->id < b->def->id)
331 return -1;
332 if(a->def->id > b->def->id)
333 return 1;
334 return 0;
335 }
336
dealias_probe_def_cmp(const scamper_dealias_probe_t * a,const scamper_dealias_probe_t * b)337 static int dealias_probe_def_cmp(const scamper_dealias_probe_t *a,
338 const scamper_dealias_probe_t *b)
339 {
340 if(a->def->id < b->def->id)
341 return -1;
342 if(a->def->id > b->def->id)
343 return 1;
344 if(a->seq < b->seq)
345 return -1;
346 if(a->seq > b->seq)
347 return 1;
348 return 0;
349 }
350
scamper_dealias_probes_sort_tx(scamper_dealias_t * dealias)351 void scamper_dealias_probes_sort_tx(scamper_dealias_t *dealias)
352 {
353 array_qsort((void **)dealias->probes, dealias->probec,
354 (array_cmp_t)dealias_probe_tx_cmp);
355 return;
356 }
357
scamper_dealias_probes_sort_seq(scamper_dealias_t * dealias)358 void scamper_dealias_probes_sort_seq(scamper_dealias_t *dealias)
359 {
360 array_qsort((void **)dealias->probes, dealias->probec,
361 (array_cmp_t)dealias_probe_seq_cmp);
362 return;
363 }
364
scamper_dealias_probes_sort_def(scamper_dealias_t * dealias)365 void scamper_dealias_probes_sort_def(scamper_dealias_t *dealias)
366 {
367 array_qsort((void **)dealias->probes, dealias->probec,
368 (array_cmp_t)dealias_probe_def_cmp);
369 return;
370 }
371
scamper_dealias_probe_add(scamper_dealias_t * dealias,scamper_dealias_probe_t * probe)372 int scamper_dealias_probe_add(scamper_dealias_t *dealias,
373 scamper_dealias_probe_t *probe)
374 {
375 size_t size = (dealias->probec+1) * sizeof(scamper_dealias_probe_t *);
376 if(realloc_wrap((void **)&dealias->probes, size) == 0)
377 {
378 dealias->probes[dealias->probec++] = probe;
379 return 0;
380 }
381 return -1;
382 }
383
scamper_dealias_reply_add(scamper_dealias_probe_t * probe,scamper_dealias_reply_t * reply)384 int scamper_dealias_reply_add(scamper_dealias_probe_t *probe,
385 scamper_dealias_reply_t *reply)
386 {
387 size_t size = (probe->replyc+1) * sizeof(scamper_dealias_reply_t *);
388 if(realloc_wrap((void **)&probe->replies, size) == 0)
389 {
390 probe->replies[probe->replyc++] = reply;
391 return 0;
392 }
393 return -1;
394 }
395
scamper_dealias_ally_alloc(scamper_dealias_t * dealias)396 int scamper_dealias_ally_alloc(scamper_dealias_t *dealias)
397 {
398 if((dealias->data = malloc_zero(sizeof(scamper_dealias_ally_t))) != NULL)
399 return 0;
400 return -1;
401 }
402
scamper_dealias_mercator_alloc(scamper_dealias_t * dealias)403 int scamper_dealias_mercator_alloc(scamper_dealias_t *dealias)
404 {
405 if((dealias->data = malloc_zero(sizeof(scamper_dealias_mercator_t))) != NULL)
406 return 0;
407 return -1;
408 }
409
scamper_dealias_radargun_alloc(scamper_dealias_t * dealias)410 int scamper_dealias_radargun_alloc(scamper_dealias_t *dealias)
411 {
412 if((dealias->data = malloc_zero(sizeof(scamper_dealias_radargun_t))) != NULL)
413 return 0;
414 return -1;
415 }
416
scamper_dealias_prefixscan_alloc(scamper_dealias_t * dealias)417 int scamper_dealias_prefixscan_alloc(scamper_dealias_t *dealias)
418 {
419 dealias->data = malloc_zero(sizeof(scamper_dealias_prefixscan_t));
420 if(dealias->data != NULL)
421 return 0;
422 return -1;
423 }
424
scamper_dealias_bump_alloc(scamper_dealias_t * dealias)425 int scamper_dealias_bump_alloc(scamper_dealias_t *dealias)
426 {
427 if((dealias->data = malloc_zero(sizeof(scamper_dealias_bump_t))) != NULL)
428 return 0;
429
430 return -1;
431 }
432
dealias_ipid16_diff(uint16_t a,uint16_t b)433 static uint16_t dealias_ipid16_diff(uint16_t a, uint16_t b)
434 {
435 if(a <= b)
436 return b - a;
437 return (0xFFFFUL - a) + b + 1;
438 }
439
dealias_ipid16_inseq2(uint16_t a,uint16_t b,uint16_t fudge)440 static int dealias_ipid16_inseq2(uint16_t a, uint16_t b, uint16_t fudge)
441 {
442 if(a == b || dealias_ipid16_diff(a, b) > fudge)
443 return 0;
444 return 1;
445 }
446
dealias_ipid16_inseq3(uint32_t a,uint32_t b,uint32_t c,uint32_t f)447 static int dealias_ipid16_inseq3(uint32_t a,uint32_t b,uint32_t c,uint32_t f)
448 {
449 if(a == b || b == c || a == c)
450 return 0;
451
452 if(a > b)
453 b += 0x10000;
454 if(a > c)
455 c += 0x10000;
456
457 if(a > b || b > c)
458 return 0;
459 if(f != 0 && (b - a > f || c - b > f))
460 return 0;
461
462 return 1;
463 }
464
dealias_ipid32_diff(uint32_t a,uint32_t b)465 static uint32_t dealias_ipid32_diff(uint32_t a, uint32_t b)
466 {
467 if(a <= b)
468 return b - a;
469 return (0xFFFFFFFFUL - a) + b + 1;
470 }
471
dealias_ipid32_inseq2(uint32_t a,uint32_t b,uint32_t fudge)472 static int dealias_ipid32_inseq2(uint32_t a, uint32_t b, uint32_t fudge)
473 {
474 if(a == b || dealias_ipid32_diff(a, b) > fudge)
475 return 0;
476 return 1;
477 }
478
dealias_ipid32_inseq3(uint64_t a,uint64_t b,uint64_t c,uint64_t f)479 static int dealias_ipid32_inseq3(uint64_t a,uint64_t b,uint64_t c,uint64_t f)
480 {
481 if(a == b || b == c || a == c)
482 return 0;
483
484 if(a > b)
485 b += 0x100000000ULL;
486 if(a > c)
487 c += 0x100000000ULL;
488
489 if(a > b || b > c)
490 return 0;
491 if(f != 0 && (b - a > f || c - b > f))
492 return 0;
493
494 return 1;
495 }
496
dealias_ipid16_bo(scamper_dealias_probe_t ** probes,int probec)497 static int dealias_ipid16_bo(scamper_dealias_probe_t **probes, int probec)
498 {
499 scamper_dealias_probe_t **s = NULL;
500 uint16_t a, b, c = 1, max_bs = 0, max_nobs = 0, u16;
501 int i, rc = 2;
502
503 if((s = memdup(probes, sizeof(scamper_dealias_probe_t *) * probec)) == NULL)
504 return -1;
505 array_qsort((void **)s, probec, (array_cmp_t)dealias_probe_def_cmp);
506
507 for(i=0; i<probec; i++)
508 {
509 if(i+1 == probec || s[i]->def != s[i+1]->def)
510 {
511 if(c >= 3)
512 {
513 if(max_nobs < max_bs)
514 rc = 0;
515 else if(max_nobs > max_bs)
516 rc = 1;
517 if(rc == 0)
518 goto done;
519 }
520 c = 1; max_nobs = 0; max_bs = 0;
521 }
522 else
523 {
524 a = s[i]->replies[0]->ipid; b = s[i+1]->replies[0]->ipid;
525 u16 = dealias_ipid16_diff(a, b);
526 if(u16 > max_nobs || max_nobs == 0)
527 max_nobs = u16;
528 u16 = dealias_ipid16_diff(byteswap16(a), byteswap16(b));
529 if(u16 > max_bs || max_bs == 0)
530 max_bs = u16;
531 c++;
532 }
533 }
534
535 done:
536 if(s != NULL) free(s);
537 return rc;
538 }
539
dealias_ipid16_inseq(scamper_dealias_probe_t ** probes,int probec,uint16_t fudge,int bs)540 static int dealias_ipid16_inseq(scamper_dealias_probe_t **probes,
541 int probec, uint16_t fudge, int bs)
542 {
543 uint16_t a, b, c;
544 int i;
545
546 /*
547 * do a preliminary check to see if the ipids could be in sequence with
548 * two samples.
549 */
550 if(probec == 2)
551 {
552 /* if it is a strict sequence check, we don't actually know */
553 if(fudge == 0)
554 return 1;
555
556 a = probes[0]->replies[0]->ipid;
557 b = probes[1]->replies[0]->ipid;
558 if(bs != 0)
559 {
560 a = byteswap16(a);
561 b = byteswap16(b);
562 }
563 if(dealias_ipid16_inseq2(a, b, fudge) != 0)
564 return 1;
565 return 0;
566 }
567
568 for(i=0; i+2<probec; i++)
569 {
570 a = probes[i+0]->replies[0]->ipid;
571 b = probes[i+1]->replies[0]->ipid;
572 c = probes[i+2]->replies[0]->ipid;
573 if(bs != 0)
574 {
575 a = byteswap16(a);
576 b = byteswap16(b);
577 c = byteswap16(c);
578 }
579 if(dealias_ipid16_inseq3(a, b, c, fudge) == 0)
580 return 0;
581 }
582
583 return 1;
584 }
585
dealias_ipid32_bo(scamper_dealias_probe_t ** probes,int probec)586 static int dealias_ipid32_bo(scamper_dealias_probe_t **probes, int probec)
587 {
588 scamper_dealias_probe_t **s = NULL;
589 uint32_t a, b, c = 1, max_bs = 0, max_nobs = 0, u32;
590 int i, rc = 2;
591
592 if((s = memdup(probes, sizeof(scamper_dealias_probe_t *) * probec)) == NULL)
593 return -1;
594 array_qsort((void **)s, probec, (array_cmp_t)dealias_probe_def_cmp);
595
596 for(i=0; i<probec; i++)
597 {
598 if(i+1 == probec || s[i]->def != s[i+1]->def)
599 {
600 if(c >= 3)
601 {
602 if(max_nobs < max_bs)
603 rc = 0;
604 else if(max_nobs > max_bs)
605 rc = 1;
606 if(rc == 0)
607 goto done;
608 }
609 c = 1; max_nobs = 0; max_bs = 0;
610 }
611 else
612 {
613 a = s[i]->replies[0]->ipid32; b = s[i+1]->replies[0]->ipid32;
614 u32 = dealias_ipid32_diff(a, b);
615 if(u32 > max_nobs || max_nobs == 0)
616 max_nobs = u32;
617 u32 = dealias_ipid32_diff(byteswap32(a), byteswap32(b));
618 if(u32 > max_bs || max_bs == 0)
619 max_bs = u32;
620 c++;
621 }
622 }
623
624 done:
625 if(s != NULL) free(s);
626 return rc;
627 }
628
dealias_ipid32_inseq(scamper_dealias_probe_t ** probes,int probec,uint16_t fudge,int bs)629 static int dealias_ipid32_inseq(scamper_dealias_probe_t **probes,
630 int probec, uint16_t fudge, int bs)
631 {
632 uint32_t a, b, c;
633 int i;
634
635 /*
636 * do a preliminary check to see if the ipids could be in sequence with
637 * two samples.
638 */
639 if(probec == 2)
640 {
641 /* if it is a strict sequence check, we don't actually know */
642 if(fudge == 0)
643 return 1;
644
645 a = probes[0]->replies[0]->ipid32;
646 b = probes[1]->replies[0]->ipid32;
647 if(bs != 0)
648 {
649 a = byteswap32(a);
650 b = byteswap32(b);
651 }
652 if(dealias_ipid32_inseq2(a, b, fudge) != 0)
653 return 1;
654 return 0;
655 }
656
657 for(i=0; i+2<probec; i++)
658 {
659 a = probes[i+0]->replies[0]->ipid32;
660 b = probes[i+1]->replies[0]->ipid32;
661 c = probes[i+2]->replies[0]->ipid32;
662 if(bs != 0)
663 {
664 a = byteswap32(a);
665 b = byteswap32(b);
666 c = byteswap32(c);
667 }
668 if(dealias_ipid32_inseq3(a, b, c, fudge) == 0)
669 return 0;
670 }
671
672 return 1;
673 }
674
scamper_dealias_ipid_inseq(scamper_dealias_probe_t ** probes,int probec,uint16_t fudge,int bs)675 int scamper_dealias_ipid_inseq(scamper_dealias_probe_t **probes,
676 int probec, uint16_t fudge, int bs)
677 {
678 static int (*const inseq[])(scamper_dealias_probe_t **,int,uint16_t,int) = {
679 dealias_ipid16_inseq,
680 dealias_ipid32_inseq,
681 };
682 static int (*const bo[])(scamper_dealias_probe_t **, int) = {
683 dealias_ipid16_bo,
684 dealias_ipid32_bo,
685 };
686 int i, x;
687
688 if(probec < 2)
689 return -1;
690
691 if(SCAMPER_ADDR_TYPE_IS_IPV4(probes[0]->def->dst))
692 x = 0;
693 else if(SCAMPER_ADDR_TYPE_IS_IPV6(probes[0]->def->dst))
694 x = 1;
695 else
696 return -1;
697
698 if(bs == 3 && fudge == 0)
699 {
700 if((i = bo[x](probes, probec)) == -1)
701 return -1;
702 return inseq[x](probes, probec, fudge, i);
703 }
704
705 if(bs == 2 || bs == 3)
706 {
707 if(inseq[x](probes, probec, fudge, 0) == 1)
708 return 1;
709 return inseq[x](probes, probec, fudge, 1);
710 }
711
712 return inseq[x](probes, probec, fudge, bs);
713 }
714
scamper_dealias_probes_alloc(scamper_dealias_t * dealias,uint32_t cnt)715 int scamper_dealias_probes_alloc(scamper_dealias_t *dealias, uint32_t cnt)
716 {
717 size_t size = cnt * sizeof(scamper_dealias_probe_t *);
718 if((dealias->probes = malloc_zero(size)) == NULL)
719 return -1;
720 return 0;
721 }
722
scamper_dealias_replies_alloc(scamper_dealias_probe_t * probe,uint16_t cnt)723 int scamper_dealias_replies_alloc(scamper_dealias_probe_t *probe, uint16_t cnt)
724 {
725 size_t size = cnt * sizeof(scamper_dealias_reply_t *);
726 if((probe->replies = malloc_zero(size)) == NULL)
727 return -1;
728 return 0;
729 }
730
scamper_dealias_radargun_probedefs_alloc(scamper_dealias_radargun_t * rg,uint32_t probedefc)731 int scamper_dealias_radargun_probedefs_alloc(scamper_dealias_radargun_t *rg,
732 uint32_t probedefc)
733 {
734 size_t len = probedefc * sizeof(scamper_dealias_probedef_t);
735 if((rg->probedefs = malloc_zero(len)) == NULL)
736 return -1;
737 return 0;
738 }
739
740 typedef struct dealias_resolv
741 {
742 scamper_dealias_probe_t **probes;
743 int probec;
744 int probet;
745 } dealias_resolv_t;
746
dealias_fudge_inseq(scamper_dealias_probe_t * pr_a,scamper_dealias_probe_t * pr_b,int bs,int fudge)747 static int dealias_fudge_inseq(scamper_dealias_probe_t *pr_a,
748 scamper_dealias_probe_t *pr_b,
749 int bs, int fudge)
750 {
751 uint32_t a = pr_a->replies[0]->ipid;
752 uint32_t b = pr_b->replies[0]->ipid;
753
754 if(bs != 0)
755 {
756 a = byteswap16(a);
757 b = byteswap16(b);
758 }
759
760 if(a > b)
761 b += 0x10000;
762
763 if((int)(b - a) > fudge)
764 return 0;
765
766 return 1;
767 }
768
scamper_dealias_prefixscan_xs_add(scamper_dealias_t * dealias,scamper_addr_t * addr)769 int scamper_dealias_prefixscan_xs_add(scamper_dealias_t *dealias,
770 scamper_addr_t *addr)
771 {
772 scamper_dealias_prefixscan_t *prefixscan = dealias->data;
773 int tmp;
774
775 if(array_find((void **)prefixscan->xs, prefixscan->xc, addr,
776 (array_cmp_t)scamper_addr_cmp) != NULL)
777 return 0;
778
779 if((tmp = prefixscan->xc) == 65535)
780 return -1;
781
782 if(array_insert((void ***)&prefixscan->xs, &tmp, addr,
783 (array_cmp_t)scamper_addr_cmp) != 0)
784 return -1;
785
786 scamper_addr_use(addr);
787 prefixscan->xc++;
788 return 0;
789 }
790
scamper_dealias_prefixscan_xs_in(scamper_dealias_t * dealias,scamper_addr_t * addr)791 int scamper_dealias_prefixscan_xs_in(scamper_dealias_t *dealias,
792 scamper_addr_t *addr)
793 {
794 scamper_dealias_prefixscan_t *prefixscan = dealias->data;
795 if(array_find((void **)prefixscan->xs, prefixscan->xc, addr,
796 (array_cmp_t)scamper_addr_cmp) != NULL)
797 return 1;
798 return 0;
799 }
800
scamper_dealias_prefixscan_xs_alloc(scamper_dealias_prefixscan_t * p,uint16_t xc)801 int scamper_dealias_prefixscan_xs_alloc(scamper_dealias_prefixscan_t *p,
802 uint16_t xc)
803 {
804 if((p->xs = malloc_zero(sizeof(scamper_addr_t *) * xc)) != NULL)
805 return 0;
806 return -1;
807 }
808
scamper_dealias_prefixscan_probedefs_alloc(scamper_dealias_prefixscan_t * p,uint32_t probedefc)809 int scamper_dealias_prefixscan_probedefs_alloc(scamper_dealias_prefixscan_t *p,
810 uint32_t probedefc)
811 {
812 size_t len = probedefc * sizeof(scamper_dealias_probedef_t);
813 if((p->probedefs = malloc_zero(len)) != NULL)
814 return 0;
815 return -1;
816 }
817
scamper_dealias_prefixscan_probedef_add(scamper_dealias_t * dealias,scamper_dealias_probedef_t * def)818 int scamper_dealias_prefixscan_probedef_add(scamper_dealias_t *dealias,
819 scamper_dealias_probedef_t *def)
820 {
821 scamper_dealias_prefixscan_t *prefixscan = dealias->data;
822 size_t size;
823
824 /* make the probedef array one bigger */
825 size = sizeof(scamper_dealias_probedef_t) * (prefixscan->probedefc+1);
826 if(realloc_wrap((void **)&prefixscan->probedefs, size) != 0)
827 return -1;
828
829 /* add the probedef to the array */
830 memcpy(&prefixscan->probedefs[prefixscan->probedefc],
831 def, sizeof(scamper_dealias_probedef_t));
832
833 /* update the probedef with an id, and get references to the addresses */
834 def = &prefixscan->probedefs[prefixscan->probedefc];
835 def->id = prefixscan->probedefc++;
836 scamper_addr_use(def->src);
837 scamper_addr_use(def->dst);
838
839 return 0;
840 }
841
scamper_dealias_radargun_fudge(scamper_dealias_t * dealias,scamper_dealias_probedef_t * def,scamper_dealias_probedef_t ** defs,int * cnt,int fudge)842 int scamper_dealias_radargun_fudge(scamper_dealias_t *dealias,
843 scamper_dealias_probedef_t *def,
844 scamper_dealias_probedef_t **defs, int *cnt,
845 int fudge)
846 {
847 scamper_dealias_radargun_t *rg = dealias->data;
848 scamper_dealias_probe_t *pr, *pr_a, *pr_b;
849 scamper_dealias_reply_t *re, *re_a, *re_b, *re_c;
850 dealias_resolv_t *dr = NULL;
851 dealias_resolv_t *drd;
852 uint32_t pid, x;
853 int i, j, k, bs, inseq, d = 0;
854
855 if(dealias->method != SCAMPER_DEALIAS_METHOD_RADARGUN)
856 goto err;
857
858 if((dr = malloc_zero(sizeof(dealias_resolv_t) * rg->probedefc)) == NULL)
859 goto err;
860
861 for(x=0; x<dealias->probec; x++)
862 {
863 pr = dealias->probes[x];
864 pid = pr->def->id;
865
866 /*
867 * if this probedef has already been determined to be useless for
868 * alias resolution, skip it
869 */
870 if(dr[pid].probec < 0)
871 continue;
872
873 if(pr->replyc > 1)
874 {
875 if(dr[pid].probes != NULL)
876 free(dr[pid].probes);
877 dr[pid].probec = -1;
878
879 if(pr->def == def)
880 goto done;
881 continue;
882 }
883
884 /* total number of probes transmitted */
885 dr[pid].probet++;
886
887 if(pr->replyc == 0)
888 continue;
889
890 re = pr->replies[0];
891
892 /*
893 * with three replies, do some basic checks to see if we should
894 * continue considering this probedef.
895 */
896 if(dr[pid].probec == 2)
897 {
898 pr_a = dr[pid].probes[0];
899 pr_b = dr[pid].probes[1];
900 re_a = pr_a->replies[0];
901 re_b = pr_b->replies[0];
902
903 if((re->ipid == pr->ipid && re_a->ipid == pr_a->ipid &&
904 re_b->ipid == pr_b->ipid) ||
905 (re->ipid == re_a->ipid && re->ipid == re_b->ipid))
906 {
907 free(dr[pid].probes);
908 dr[pid].probec = -1;
909
910 if(pr->def == def)
911 goto done;
912 continue;
913 }
914 }
915
916 if(array_insert((void ***)&dr[pid].probes,&dr[pid].probec,pr,NULL) != 0)
917 goto err;
918 }
919
920 /* figure out if we should byteswap the ipid sequence */
921 if(dr[def->id].probec < 3)
922 goto done;
923 re_a = dr[def->id].probes[0]->replies[0];
924 re_b = dr[def->id].probes[1]->replies[0];
925 re_c = dr[def->id].probes[2]->replies[0];
926 if(re_a->ipid < re_b->ipid)
927 i = re_b->ipid - re_a->ipid;
928 else
929 i = 0x10000 + re_b->ipid - re_a->ipid;
930 if(re_b->ipid < re_c->ipid)
931 i += re_c->ipid - re_b->ipid;
932 else
933 i += 0x10000 + re_c->ipid - re_b->ipid;
934 if(byteswap16(re_a->ipid) < byteswap16(re_b->ipid))
935 j = byteswap16(re_b->ipid) - byteswap16(re_a->ipid);
936 else
937 j = 0x10000 + byteswap16(re_b->ipid) - byteswap16(re_a->ipid);
938 if(byteswap16(re_b->ipid) < byteswap16(re_c->ipid))
939 j += byteswap16(re_c->ipid) - byteswap16(re_b->ipid);
940 else
941 j += 0x10000 + byteswap16(re_c->ipid) - byteswap16(re_b->ipid);
942 if(i < j)
943 bs = 0;
944 else
945 bs = 1;
946
947 /* for each probedef, consider if it could be an alias */
948 drd = &dr[def->id]; d = 0;
949 for(pid=0; pid<rg->probedefc; pid++)
950 {
951 if(&rg->probedefs[pid] == def || dr[pid].probec < 3)
952 continue;
953
954 j = 0; k = 0;
955
956 /* get the first ipid */
957 if(timeval_cmp(&drd->probes[j]->tx, &dr[pid].probes[k]->tx) < 0)
958 pr_a = drd->probes[j++];
959 else
960 pr_a = dr[pid].probes[k++];
961
962 for(;;)
963 {
964 if(timeval_cmp(&drd->probes[j]->tx, &dr[pid].probes[k]->tx) < 0)
965 pr_b = drd->probes[j++];
966 else
967 pr_b = dr[pid].probes[k++];
968
969 if((inseq = dealias_fudge_inseq(pr_a, pr_b, bs, fudge)) == 0)
970 break;
971
972 if(j == drd->probec || k == dr[pid].probec)
973 break;
974 }
975
976 /*
977 * if the pairs do not appear to have insequence IP-ID values, then
978 * abandon
979 */
980 if(inseq == 0)
981 continue;
982
983 defs[d++] = &rg->probedefs[pid];
984 if(d == *cnt)
985 break;
986 }
987
988 done:
989 *cnt = d;
990 for(x=0; x<rg->probedefc; x++)
991 if(dr[x].probec > 0)
992 free(dr[x].probes);
993 free(dr);
994 return 0;
995
996 err:
997 if(dr != NULL)
998 {
999 for(x=0; x<rg->probedefc; x++)
1000 if(dr[x].probec > 0)
1001 free(dr[x].probes);
1002 free(dr);
1003 }
1004 return -1;
1005 }
1006
scamper_dealias_method_tostr(const scamper_dealias_t * d,char * b,size_t l)1007 const char *scamper_dealias_method_tostr(const scamper_dealias_t *d, char *b, size_t l)
1008 {
1009 static const char *m[] = {
1010 NULL,
1011 "mercator",
1012 "ally",
1013 "radargun",
1014 "prefixscan",
1015 "bump",
1016 };
1017 if(d->method >= sizeof(m) / sizeof(char *) || m[d->method] == NULL)
1018 {
1019 snprintf(b, l, "%d", d->method);
1020 return b;
1021 }
1022 return m[d->method];
1023 }
1024
scamper_dealias_result_tostr(const scamper_dealias_t * d,char * b,size_t l)1025 const char *scamper_dealias_result_tostr(const scamper_dealias_t *d, char *b, size_t l)
1026 {
1027 static const char *t[] = {
1028 "none",
1029 "aliases",
1030 "not-aliases",
1031 "halted",
1032 "ipid-echo",
1033 };
1034 if(d->result >= sizeof(t) / sizeof(char *) || t[d->result] == NULL)
1035 {
1036 snprintf(b, l, "%d", d->result);
1037 return b;
1038 }
1039 return t[d->result];
1040 }
1041
scamper_dealias_free(scamper_dealias_t * dealias)1042 void scamper_dealias_free(scamper_dealias_t *dealias)
1043 {
1044 static void (*const func[])(void *) = {
1045 dealias_mercator_free,
1046 dealias_ally_free,
1047 dealias_radargun_free,
1048 dealias_prefixscan_free,
1049 dealias_bump_free,
1050 };
1051
1052 uint32_t i;
1053
1054 if(dealias == NULL)
1055 return;
1056
1057 if(dealias->probes != NULL)
1058 {
1059 for(i=0; i<dealias->probec; i++)
1060 {
1061 if(dealias->probes[i] != NULL)
1062 scamper_dealias_probe_free(dealias->probes[i]);
1063 }
1064 free(dealias->probes);
1065 }
1066
1067 if(dealias->cycle != NULL) scamper_cycle_free(dealias->cycle);
1068 if(dealias->list != NULL) scamper_list_free(dealias->list);
1069
1070 if(dealias->data != NULL)
1071 {
1072 assert(dealias->method != 0);
1073 assert(dealias->method <= 5);
1074 func[dealias->method-1](dealias->data);
1075 }
1076
1077 free(dealias);
1078 return;
1079 }
1080
scamper_dealias_alloc(void)1081 scamper_dealias_t *scamper_dealias_alloc(void)
1082 {
1083 return (scamper_dealias_t *)malloc_zero(sizeof(scamper_dealias_t));
1084 }
1085