1 /* 2 * scamper_dealias.h 3 * 4 * $Id: scamper_dealias.h,v 1.45 2013/08/28 05:23:47 mjl Exp $ 5 * 6 * Copyright (C) 2008-2011 The University of Waikato 7 * Copyright (C) 2012-2013 The Regents of the University of California 8 * Author: Matthew Luckie 9 * 10 * This code implements alias resolution techniques published by others 11 * which require the network to be probed; the author of each technique 12 * is detailed with its data structures. 13 * 14 * This program is free software; you can redistribute it and/or modify 15 * it under the terms of the GNU General Public License as published by 16 * the Free Software Foundation, version 2. 17 * 18 * This program is distributed in the replye that it will be useful, 19 * but WITHOUT ANY WARRANTY; without even the implied warranty of 20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 21 * GNU General Public License for more details. 22 * 23 * You should have received a copy of the GNU General Public License 24 * along with this program; if not, write to the Free Software 25 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 26 * 27 */ 28 29 #ifndef __SCAMPER_DEALIAS_H 30 #define __SCAMPER_DEALIAS_H 31 32 #define SCAMPER_DEALIAS_METHOD_MERCATOR 1 33 #define SCAMPER_DEALIAS_METHOD_ALLY 2 34 #define SCAMPER_DEALIAS_METHOD_RADARGUN 3 35 #define SCAMPER_DEALIAS_METHOD_PREFIXSCAN 4 36 #define SCAMPER_DEALIAS_METHOD_BUMP 5 37 38 #define SCAMPER_DEALIAS_PROBEDEF_METHOD_ICMP_ECHO 1 39 #define SCAMPER_DEALIAS_PROBEDEF_METHOD_TCP_ACK 2 40 #define SCAMPER_DEALIAS_PROBEDEF_METHOD_UDP 3 41 #define SCAMPER_DEALIAS_PROBEDEF_METHOD_TCP_ACK_SPORT 4 42 #define SCAMPER_DEALIAS_PROBEDEF_METHOD_UDP_DPORT 5 43 #define SCAMPER_DEALIAS_PROBEDEF_METHOD_TCP_SYN_SPORT 6 44 45 #define SCAMPER_DEALIAS_RESULT_NONE 0 46 #define SCAMPER_DEALIAS_RESULT_ALIASES 1 47 #define SCAMPER_DEALIAS_RESULT_NOTALIASES 2 48 #define SCAMPER_DEALIAS_RESULT_HALTED 3 49 #define SCAMPER_DEALIAS_RESULT_IPIDECHO 4 50 51 #define SCAMPER_DEALIAS_ALLY_FLAG_NOBS 1 52 #define SCAMPER_DEALIAS_RADARGUN_FLAG_SHUFFLE 1 53 #define SCAMPER_DEALIAS_PREFIXSCAN_FLAG_NOBS 1 54 #define SCAMPER_DEALIAS_PREFIXSCAN_FLAG_CSA 2 55 56 #define SCAMPER_DEALIAS_REPLY_FLAG_IPID32 1 57 58 #define SCAMPER_DEALIAS_PROBEDEF_PROTO_IS_ICMP(def) ( \ 59 (def)->method == SCAMPER_DEALIAS_PROBEDEF_METHOD_ICMP_ECHO) 60 61 #define SCAMPER_DEALIAS_PROBEDEF_PROTO_IS_UDP(def) ( \ 62 (def)->method == SCAMPER_DEALIAS_PROBEDEF_METHOD_UDP || \ 63 (def)->method == SCAMPER_DEALIAS_PROBEDEF_METHOD_UDP_DPORT) 64 65 #define SCAMPER_DEALIAS_PROBEDEF_PROTO_IS_TCP(def) ( \ 66 (def)->method == SCAMPER_DEALIAS_PROBEDEF_METHOD_TCP_ACK || \ 67 (def)->method == SCAMPER_DEALIAS_PROBEDEF_METHOD_TCP_ACK_SPORT || \ 68 (def)->method == SCAMPER_DEALIAS_PROBEDEF_METHOD_TCP_SYN_SPORT) 69 70 #define SCAMPER_DEALIAS_PROBEDEF_VARY_TCP_SPORT(def) ( \ 71 (def)->method == SCAMPER_DEALIAS_PROBEDEF_METHOD_TCP_ACK_SPORT || \ 72 (def)->method == SCAMPER_DEALIAS_PROBEDEF_METHOD_TCP_SYN_SPORT) 73 74 #define SCAMPER_DEALIAS_PROBEDEF_PROTO_IS_TCP_ACK(def) ( \ 75 (def)->method == SCAMPER_DEALIAS_PROBEDEF_METHOD_TCP_ACK || \ 76 (def)->method == SCAMPER_DEALIAS_PROBEDEF_METHOD_TCP_ACK_SPORT) 77 78 #define SCAMPER_DEALIAS_PROBEDEF_PROTO_IS_TCP_SYN(def) ( \ 79 (def)->method == SCAMPER_DEALIAS_PROBEDEF_METHOD_TCP_SYN_SPORT) 80 81 #define SCAMPER_DEALIAS_REPLY_IS_ICMP(reply) ( \ 82 ((reply)->proto == 1 || (reply)->proto == 58)) 83 84 #define SCAMPER_DEALIAS_REPLY_IS_TCP(reply) ( \ 85 ((reply)->proto == 6)) 86 87 #define SCAMPER_DEALIAS_REPLY_IS_ICMP_TTL_EXP(reply) ( \ 88 ((reply)->proto == 1 && (reply)->icmp_type == 11) || \ 89 ((reply)->proto == 58 && (reply)->icmp_type == 3)) 90 91 #define SCAMPER_DEALIAS_REPLY_IS_ICMP_UNREACH(reply) ( \ 92 ((reply)->proto == 1 && (reply)->icmp_type == 3) || \ 93 ((reply)->proto == 58 && (reply)->icmp_type == 1)) 94 95 #define SCAMPER_DEALIAS_REPLY_IS_ICMP_UNREACH_PORT(reply) ( \ 96 ((reply)->proto == 1 && \ 97 (reply)->icmp_type == 3 && (reply)->icmp_code == 3) || \ 98 ((reply)->proto == 58 && \ 99 (reply)->icmp_type == 1 && (reply)->icmp_code == 4)) 100 101 #define SCAMPER_DEALIAS_REPLY_IS_ICMP_ECHO_REPLY(reply) ( \ 102 ((reply)->proto == 1 && (reply)->icmp_type == 0) || \ 103 ((reply)->proto == 58 && (reply)->icmp_type == 129)) 104 105 #define SCAMPER_DEALIAS_METHOD_IS_MERCATOR(d) ( \ 106 (d)->method == SCAMPER_DEALIAS_METHOD_MERCATOR) 107 108 #define SCAMPER_DEALIAS_METHOD_IS_ALLY(d) ( \ 109 (d)->method == SCAMPER_DEALIAS_METHOD_ALLY) 110 111 #define SCAMPER_DEALIAS_METHOD_IS_RADARGUN(d) ( \ 112 (d)->method == SCAMPER_DEALIAS_METHOD_RADARGUN) 113 114 #define SCAMPER_DEALIAS_METHOD_IS_PREFIXSCAN(d) ( \ 115 (d)->method == SCAMPER_DEALIAS_METHOD_PREFIXSCAN) 116 117 #define SCAMPER_DEALIAS_METHOD_IS_BUMP(d) ( \ 118 (d)->method == SCAMPER_DEALIAS_METHOD_BUMP) 119 120 #define SCAMPER_DEALIAS_RESULT_IS_NONE(d) ( \ 121 (d)->result == SCAMPER_DEALIAS_RESULT_NONE) 122 123 #define SCAMPER_DEALIAS_RESULT_IS_ALIASES(d) ( \ 124 (d)->result == SCAMPER_DEALIAS_RESULT_ALIASES) 125 126 #define SCAMPER_DEALIAS_RESULT_IS_NOTALIASES(d) ( \ 127 (d)->result == SCAMPER_DEALIAS_RESULT_NOTALIASES) 128 129 #define SCAMPER_DEALIAS_ALLY_IS_NOBS(d) ( \ 130 (((scamper_dealias_ally_t *)(d)->data)->flags) & \ 131 SCAMPER_DEALIAS_ALLY_FLAG_NOBS) 132 133 #define SCAMPER_DEALIAS_PREFIXSCAN_IS_NOBS(d) ( \ 134 (((scamper_dealias_prefixscan_t *)(d)->data)->flags) & \ 135 SCAMPER_DEALIAS_PREFIXSCAN_FLAG_NOBS) 136 137 #define SCAMPER_DEALIAS_REPLY_FROM_TARGET(p, r) ( \ 138 (SCAMPER_DEALIAS_PROBEDEF_PROTO_IS_UDP((p)->def) && \ 139 SCAMPER_DEALIAS_REPLY_IS_ICMP_UNREACH_PORT((r))) || \ 140 (SCAMPER_DEALIAS_PROBEDEF_PROTO_IS_ICMP((p)->def) && \ 141 SCAMPER_DEALIAS_REPLY_IS_ICMP_ECHO_REPLY((r))) || \ 142 (SCAMPER_DEALIAS_PROBEDEF_PROTO_IS_TCP((p)->def) && \ 143 SCAMPER_DEALIAS_REPLY_IS_TCP((r)))) 144 145 typedef struct scamper_dealias_reply 146 { 147 scamper_addr_t *src; 148 struct timeval rx; 149 150 uint8_t flags; 151 uint8_t proto; 152 uint8_t ttl; 153 uint8_t icmp_type; 154 uint8_t icmp_code; 155 uint8_t icmp_q_ip_ttl; 156 uint8_t tcp_flags; 157 158 uint16_t ipid; 159 uint32_t ipid32; 160 161 struct scamper_icmpext *icmp_ext; 162 163 } scamper_dealias_reply_t; 164 165 typedef struct scamper_dealias_probedef_udp 166 { 167 uint16_t sport; 168 uint16_t dport; 169 } scamper_dealias_probedef_udp_t; 170 171 typedef struct scamper_dealias_probedef_icmp 172 { 173 uint16_t csum; 174 uint16_t id; 175 } scamper_dealias_probedef_icmp_t; 176 177 typedef struct scamper_dealias_probedef_tcp 178 { 179 uint16_t sport; 180 uint16_t dport; 181 uint8_t flags; 182 } scamper_dealias_probedef_tcp_t; 183 184 typedef struct scamper_dealias_probedef 185 { 186 scamper_addr_t *src; 187 scamper_addr_t *dst; 188 uint32_t id; 189 uint8_t method; 190 uint8_t ttl; 191 uint8_t tos; 192 uint16_t size; 193 uint16_t mtu; 194 union 195 { 196 scamper_dealias_probedef_udp_t udp; 197 scamper_dealias_probedef_tcp_t tcp; 198 scamper_dealias_probedef_icmp_t icmp; 199 } un; 200 } scamper_dealias_probedef_t; 201 202 typedef struct scamper_dealias_probe 203 { 204 scamper_dealias_probedef_t *def; 205 uint32_t seq; 206 struct timeval tx; 207 scamper_dealias_reply_t **replies; 208 uint16_t replyc; 209 uint16_t ipid; 210 } scamper_dealias_probe_t; 211 212 typedef struct scamper_dealias_mercator 213 { 214 scamper_dealias_probedef_t probedef; 215 uint8_t attempts; 216 uint8_t wait_timeout; 217 } scamper_dealias_mercator_t; 218 219 typedef struct scamper_dealias_ally 220 { 221 scamper_dealias_probedef_t probedefs[2]; 222 uint16_t wait_probe; 223 uint8_t wait_timeout; 224 uint8_t attempts; 225 uint8_t flags; 226 uint16_t fudge; 227 } scamper_dealias_ally_t; 228 229 /* 230 * scamper_dealias_radargun 231 * 232 * the following variables define a radargun measurement. radargun was 233 * first defined in the following paper: 234 * 235 * Fixing ally's growing pains with velocity modeling. Adam Bender, Rob 236 * Sherwood, Neil Spring. Proc. IMC 2008, pages 337-342. 237 * 238 * probedefs : structures defining the form of a probe packet 239 * attempts : number of times to send each probe packet 240 * wait_probe : minimum length of time (ms) to wait between probes in a round 241 * wait_round : minimum length of time (ms) to wait between attempts 242 * wait_timeout : minimum length of time (sec) to wait for a response 243 * flags : flags to adjust the behaviour of radargun 244 */ 245 typedef struct scamper_dealias_radargun 246 { 247 scamper_dealias_probedef_t *probedefs; 248 uint32_t probedefc; 249 uint16_t attempts; 250 uint16_t wait_probe; 251 uint32_t wait_round; 252 uint8_t wait_timeout; 253 uint8_t flags; 254 } scamper_dealias_radargun_t; 255 256 /* 257 * scamper_dealias_prefixscan 258 * 259 * given an IP link defined by `a' and `b', try and find an alias for `a' 260 * that would be found on the same subnet as `b'. if such an alias is 261 * found, store it in `ab'. 262 */ 263 typedef struct scamper_dealias_prefixscan 264 { 265 scamper_addr_t *a; /* hop a */ 266 scamper_addr_t *b; /* hop b */ 267 scamper_addr_t *ab; /* alias found */ 268 scamper_addr_t **xs; /* ifaces to exclude */ 269 uint16_t xc; /* # ifaces to exclude */ 270 uint8_t prefix; /* range of IPs to scan */ 271 uint8_t attempts; /* how many attempts */ 272 uint8_t replyc; /* replies required */ 273 uint16_t fudge; /* ipid fudge */ 274 uint16_t wait_probe; /* how long b/w probes */ 275 uint8_t wait_timeout; /* when to declare lost */ 276 uint8_t flags; /* flags */ 277 scamper_dealias_probedef_t *probedefs; /* probedefs used */ 278 uint16_t probedefc; /* how many were used */ 279 } scamper_dealias_prefixscan_t; 280 281 /* 282 * scamper_dealias_bump 283 * 284 * given two IP addresses thought to be aliases, try and confirm this by 285 * attempting to bump their IP-ID counters out of synchronisation. 286 */ 287 typedef struct scamper_dealias_bump 288 { 289 scamper_dealias_probedef_t probedefs[2]; 290 uint16_t wait_probe; 291 uint16_t bump_limit; 292 uint8_t attempts; 293 } scamper_dealias_bump_t; 294 295 typedef struct scamper_dealias 296 { 297 scamper_list_t *list; 298 scamper_cycle_t *cycle; 299 uint32_t userid; 300 struct timeval start; 301 uint8_t method; 302 uint8_t result; 303 void *data; 304 scamper_dealias_probe_t **probes; 305 uint32_t probec; 306 } scamper_dealias_t; 307 308 scamper_dealias_t *scamper_dealias_alloc(void); 309 void scamper_dealias_free(scamper_dealias_t *); 310 311 scamper_dealias_probe_t *scamper_dealias_probe_alloc(void); 312 void scamper_dealias_probe_free(scamper_dealias_probe_t *); 313 314 scamper_dealias_probedef_t *scamper_dealias_probedef_alloc(void); 315 void scamper_dealias_probedef_free(scamper_dealias_probedef_t *); 316 317 scamper_dealias_reply_t *scamper_dealias_reply_alloc(void); 318 void scamper_dealias_reply_free(scamper_dealias_reply_t *); 319 uint32_t scamper_dealias_reply_count(const scamper_dealias_t *); 320 321 const char *scamper_dealias_method_tostr(const scamper_dealias_t *, char *, size_t); 322 const char *scamper_dealias_result_tostr(const scamper_dealias_t *, char *, size_t); 323 const char *scamper_dealias_probedef_method_tostr(const scamper_dealias_probedef_t *, 324 char *, size_t); 325 326 int scamper_dealias_probes_alloc(scamper_dealias_t *, uint32_t); 327 int scamper_dealias_replies_alloc(scamper_dealias_probe_t *, uint16_t); 328 329 /* these functions allow the probes recorded to be ordered to suit */ 330 void scamper_dealias_probes_sort_tx(scamper_dealias_t *); 331 void scamper_dealias_probes_sort_seq(scamper_dealias_t *); 332 void scamper_dealias_probes_sort_def(scamper_dealias_t *); 333 334 int scamper_dealias_probe_add(scamper_dealias_t *, 335 scamper_dealias_probe_t *); 336 int scamper_dealias_reply_add(scamper_dealias_probe_t *, 337 scamper_dealias_reply_t *); 338 339 int scamper_dealias_ally_alloc(scamper_dealias_t *); 340 int scamper_dealias_mercator_alloc(scamper_dealias_t *); 341 int scamper_dealias_radargun_alloc(scamper_dealias_t *); 342 int scamper_dealias_prefixscan_alloc(scamper_dealias_t *); 343 int scamper_dealias_bump_alloc(scamper_dealias_t *); 344 345 /* 346 * scamper_dealias_ipid_inseq 347 * 348 * convenience function to consider if a sequence of IPIDs are in sequence 349 * (given a fudge value). 350 * 351 * the first two parameters: array of probes and its length. 352 * the third parameter: fudge factor 353 * the fourth parameter: 0: no byteswap, 1: byteswap, 2: don't care 354 * 355 */ 356 int scamper_dealias_ipid_inseq(scamper_dealias_probe_t **, int, uint16_t, int); 357 358 int scamper_dealias_prefixscan_xs_add(scamper_dealias_t *, scamper_addr_t *); 359 int scamper_dealias_prefixscan_xs_in(scamper_dealias_t *, scamper_addr_t *); 360 int scamper_dealias_prefixscan_xs_alloc(scamper_dealias_prefixscan_t *, 361 uint16_t); 362 363 int scamper_dealias_prefixscan_probedef_add(scamper_dealias_t *, 364 scamper_dealias_probedef_t *); 365 366 int scamper_dealias_prefixscan_probedefs_alloc(scamper_dealias_prefixscan_t *, 367 uint32_t); 368 369 int scamper_dealias_radargun_fudge(scamper_dealias_t *, 370 scamper_dealias_probedef_t *, 371 scamper_dealias_probedef_t **, int *, int); 372 373 int scamper_dealias_radargun_probedefs_alloc(scamper_dealias_radargun_t *, 374 uint32_t); 375 376 #define SCAMPER_DEALIAS_IPID_UNKNOWN 0 377 #define SCAMPER_DEALIAS_IPID_ZERO 1 378 #define SCAMPER_DEALIAS_IPID_CONST 2 379 #define SCAMPER_DEALIAS_IPID_ECHO 3 380 #define SCAMPER_DEALIAS_IPID_INCR 4 381 382 typedef struct scamper_dealias_ipid 383 { 384 uint8_t type; 385 uint32_t mind; 386 uint32_t maxd; 387 } scamper_dealias_ipid_t; 388 389 int scamper_dealias_ipid(const scamper_dealias_probe_t **probes, 390 uint32_t probec, scamper_dealias_ipid_t *ipid); 391 392 #endif /* __SCAMPER_DEALIAS_H */ 393