1 /***************************************************************************
2 * traceroute.cc -- Parallel multi-protocol traceroute feature *
3 * *
4 ***********************IMPORTANT NMAP LICENSE TERMS************************
5 * *
6 * The Nmap Security Scanner is (C) 1996-2020 Insecure.Com LLC ("The Nmap *
7 * Project"). Nmap is also a registered trademark of the Nmap Project. *
8 * *
9 * This program is distributed under the terms of the Nmap Public Source *
10 * License (NPSL). The exact license text applying to a particular Nmap *
11 * release or source code control revision is contained in the LICENSE *
12 * file distributed with that version of Nmap or source code control *
13 * revision. More Nmap copyright/legal information is available from *
14 * https://nmap.org/book/man-legal.html, and further information on the *
15 * NPSL license itself can be found at https://nmap.org/npsl. This header *
16 * summarizes some key points from the Nmap license, but is no substitute *
17 * for the actual license text. *
18 * *
19 * Nmap is generally free for end users to download and use themselves, *
20 * including commercial use. It is available from https://nmap.org. *
21 * *
22 * The Nmap license generally prohibits companies from using and *
23 * redistributing Nmap in commercial products, but we sell a special Nmap *
24 * OEM Edition with a more permissive license and special features for *
25 * this purpose. See https://nmap.org/oem *
26 * *
27 * If you have received a written Nmap license agreement or contract *
28 * stating terms other than these (such as an Nmap OEM license), you may *
29 * choose to use and redistribute Nmap under those terms instead. *
30 * *
31 * The official Nmap Windows builds include the Npcap software *
32 * (https://npcap.org) for packet capture and transmission. It is under *
33 * separate license terms which forbid redistribution without special *
34 * permission. So the official Nmap Windows builds may not be *
35 * redistributed without special permission (such as an Nmap OEM *
36 * license). *
37 * *
38 * Source is provided to this software because we believe users have a *
39 * right to know exactly what a program is going to do before they run it. *
40 * This also allows you to audit the software for security holes. *
41 * *
42 * Source code also allows you to port Nmap to new platforms, fix bugs, *
43 * and add new features. You are highly encouraged to submit your *
44 * changes as a Github PR or by email to the dev@nmap.org mailing list *
45 * for possible incorporation into the main distribution. Unless you *
46 * specify otherwise, it is understood that you are offering us very *
47 * broad rights to use your submissions as described in the Nmap Public *
48 * Source License Contributor Agreement. This is important because we *
49 * fund the project by selling licenses with various terms, and also *
50 * because the inability to relicense code has caused devastating *
51 * problems for other Free Software projects (such as KDE and NASM). *
52 * *
53 * The free version of Nmap is distributed in the hope that it will be *
54 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of *
55 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. Warranties, *
56 * indemnification and commercial support are all available through the *
57 * Npcap OEM program--see https://nmap.org/oem. *
58 * *
59 ***************************************************************************/
60
61 /*
62 Traceroute for Nmap. This traceroute is faster than a traditional traceroute
63 because it sends several probes in parallel and detects shared traces.
64
65 The algorithm works by sending probes with varying TTL values and waiting for
66 TTL_EXCEEDED messages. As intermediate hops are discovered, they are entered
67 into a global hop cache that is shared between targets and across host groups.
68 When a hop is discovered and is found to be already in the cache, the trace for
69 that target is linked into the cached trace and there is no need to try lower
70 TTLs. The process results in the building of a tree of Hop structures.
71
72 The order in which probes are sent does not matter to the accuracy of the
73 algorithm but it does matter to the speed. The sooner a shared trace can be
74 detected, and the higher the TTL at which it is detected, the fewer probes need
75 to be sent. The ideal situation is to start sending probes with a TTL equal to
76 the true distance and count downward from there. In that case it may only be
77 necessary to send two probes per target: one at the distance of the target to
78 get a response, and one at distance - 1 to get a cache hit. When the distance
79 isn't known in advance, the algorithm arbitrarily starts at a TTL of 10 and
80 counts downward, then counts upward from 11 until it reaches the target. So a
81 typical trace may look like
82
83 TTL 10 -> TTL_EXCEEDED
84 TTL 9 -> TTL_EXCEEDED
85 TTL 8 -> TTL_EXCEEDED
86 TTL 7 -> cache hit
87 TTL 11 -> TTL_EXCEEDED
88 TTL 12 -> TTL_EXCEEDED
89 TTL 13 -> SYN/ACK, or whatever is the target's response to the probe
90
91 The output for this host would then say "Hops 1-7 are the same as for ...".
92
93 The detection of shared traces rests on the assumption that all paths going
94 through a router at a certain TTL will be identical up to and including the
95 router. This assumption is not always true. Even if two targets are each one hop
96 past router X at TTL 10, packets may follow different paths to each host (and
97 those paths may even change over time). This traceroute algorithm will be fooled
98 by such a situation, and will report that the paths are identical up to
99 router X. The only way to be sure is to do a complete trace for each target
100 individually.
101 */
102
103 #include "nmap_dns.h"
104 #include "nmap_error.h"
105 #include "nmap_tty.h"
106 #include "osscan2.h"
107 #include "payload.h"
108 #include "timing.h"
109 #include "NmapOps.h"
110 #include "Target.h"
111 #include "tcpip.h"
112
113 #include "struct_ip.h"
114
115 #ifndef IPPROTO_SCTP
116 #include "libnetutil/netutil.h"
117 #endif
118
119 #include <dnet.h>
120
121 #include <algorithm>
122 #include <list>
123 #include <map>
124 #include <set>
125 #include <vector>
126
127 extern NmapOps o;
128
129 /* The highest TTL we go up to if the target itself doesn't respond. */
130 #define MAX_TTL 30
131 #define MAX_OUTSTANDING_PROBES 10
132 #define MAX_RESENDS 2
133 /* In milliseconds. */
134 #define PROBE_TIMEOUT 1000
135 /* If the hop cache (including timed-out hops) is bigger than this after a
136 round, the hop is cleared and rebuilt from scratch. */
137 #define MAX_HOP_CACHE_SIZE 1000
138
139 struct Hop;
140 class HostState;
141 class Probe;
142
143 /* An object of this class is a (TTL, address) pair that uniquely identifies a
144 hop. Hops in the hop_cache are indexed by this type. */
145 struct HopIdent {
146 u8 ttl;
147 struct sockaddr_storage addr;
148
HopIdentHopIdent149 HopIdent(u8 ttl, const struct sockaddr_storage &addr) {
150 this->addr = addr;
151 this->ttl = ttl;
152 }
153
operator <HopIdent154 bool operator<(const struct HopIdent &other) const {
155 if (ttl < other.ttl)
156 return true;
157 else if (ttl > other.ttl)
158 return false;
159 else
160 return sockaddr_storage_cmp(&addr, &other.addr) < 0;
161 }
162 };
163
164 /* A global random token used to distinguish this traceroute's probes from
165 those of other traceroutes possibly running on the same machine. */
166 static u16 global_id;
167 /* A global cache of known hops, indexed by TTL and address. */
168 static std::map<struct HopIdent, Hop *> hop_cache;
169 /* A list of timedout hops, which are not kept in hop_cache, so we can delete
170 all hops on occasion. */
171 /* This would be stack-allocated except for a weird bug on AIX that causes
172 * infinite loops when trying to traverse the list. For some reason,
173 * dynamically allocating it fixes the bug. */
174 static std::list<Hop *> *timedout_hops = NULL;
175 /* The TTL at which we start sending probes if we don't have a distance
176 estimate. This is updated after each host group on the assumption that hosts
177 across groups will not differ much in distance. Having this closer to the
178 true distance makes the trace faster but is not needed for accuracy. */
179 static u8 initial_ttl = 10;
180
181 static struct timeval get_now(struct timeval *now = NULL);
182 static const char *ss_to_string(const struct sockaddr_storage *ss);
183
184 struct Hop {
185 Hop *parent;
186 struct sockaddr_storage tag;
187 /* When addr.ss_family == 0, this hop represents a timeout. */
188 struct sockaddr_storage addr;
189 u8 ttl;
190 float rtt; /* In milliseconds. */
191 std::string hostname;
192
HopHop193 Hop() {
194 this->parent = NULL;
195 this->addr.ss_family = 0;
196 this->ttl = 0;
197 this->rtt = -1.0;
198 this->tag.ss_family = 0;
199 }
200
HopHop201 Hop(u8 ttl, const struct sockaddr_storage &addr, float rtt) {
202 this->parent = NULL;
203 this->addr = addr;
204 this->ttl = ttl;
205 this->rtt = rtt;
206 this->tag.ss_family = 0;
207 }
208 };
209
210 class HostState {
211 public:
212 enum counting_state { COUNTING_DOWN, COUNTING_UP };
213
214 Target *target;
215 /* A bitmap of TTLs that have been sent, to avoid duplicates when we switch
216 around the order counting up or down. */
217 std::vector<bool> sent_ttls;
218 u8 current_ttl;
219 enum counting_state state;
220 /* If nonzero, the known hop distance to the target. */
221 int reached_target;
222 struct probespec pspec;
223 std::list<Probe *> unanswered_probes;
224 std::list<Probe *> active_probes;
225 std::list<Probe *> pending_resends;
226 Hop *hops;
227
228 HostState(Target *target);
229 ~HostState();
230 bool has_more_probes() const;
231 bool is_finished() const;
232 bool send_next_probe(int rawsd, eth_t *ethsd);
233 void next_ttl();
234 void count_up();
235 int cancel_probe(std::list<Probe *>::iterator it);
236 int cancel_probes_below(u8 ttl);
237 int cancel_probes_above(u8 ttl);
238 Hop *insert_hop(u8 ttl, const struct sockaddr_storage *addr, float rtt);
239 void link_to(Hop *hop);
240 double completion_fraction() const;
241
242 private:
243 void child_parent_ttl(u8 ttl, Hop **child, Hop **parent);
244 static u8 distance_guess(const Target *target);
245 static struct probespec get_probe(const Target *target);
246 };
247
248 class Probe {
249 private:
250 /* This is incremented with each instantiated probe. */
251 static u16 token_counter;
252
253 unsigned int num_resends;
254
255 public:
256 HostState *host;
257 struct probespec pspec;
258 u8 ttl;
259 /* The token is used to match up probe replies. */
260 u16 token;
261 struct timeval sent_time;
262
263 Probe(HostState *host, struct probespec pspec, u8 ttl);
264 virtual ~Probe();
265 void send(int rawsd, eth_t *ethsd, struct timeval *now = NULL);
266 void resend(int rawsd, eth_t *ethsd, struct timeval *now = NULL);
267 bool is_timedout(struct timeval *now = NULL) const;
268 bool may_resend() const;
269 virtual unsigned char *build_packet(const struct sockaddr_storage *source,
270 u32 *len) const = 0;
271
272 static Probe *make(HostState *host, struct probespec pspec, u8 ttl);
273 };
274 u16 Probe::token_counter = 0x0000;
275
276 class TracerouteState {
277 public:
278 std::list<HostState *> active_hosts;
279 /* The next send time for enforcing scan delay. */
280 struct timeval next_send_time;
281
282 TracerouteState(std::vector<Target *> &targets);
283 ~TracerouteState();
284
285 void send_new_probes();
286 void read_replies(long timeout);
287 void cull_timeouts();
288 void remove_finished_hosts();
289 void resolve_hops();
290 void transfer_hops();
291
292 double completion_fraction() const;
293
294 private:
295 eth_t *ethsd;
296 int rawsd;
297 pcap_t *pd;
298 int num_active_probes;
299
300 std::vector<HostState *> hosts;
301 std::list<HostState *>::iterator next_sending_host;
302
303 void next_active_host();
304 Probe *lookup_probe(const struct sockaddr_storage *target_addr, u16 token);
305 void set_host_hop(HostState *host, u8 ttl,
306 const struct sockaddr_storage *from_addr, float rtt);
307 void set_host_hop_timedout(HostState *host, u8 ttl);
308 };
309
310 static Hop *merge_hops(const struct sockaddr_storage *tag, Hop *a, Hop *b);
311 static Hop *hop_cache_lookup(u8 ttl, const struct sockaddr_storage *addr);
312 static void hop_cache_insert(Hop *hop);
313 static unsigned int hop_cache_size();
314
HostState(Target * target)315 HostState::HostState(Target *target) : sent_ttls(MAX_TTL + 1, false) {
316 this->target = target;
317 current_ttl = MIN(MAX(1, HostState::distance_guess(target)), MAX_TTL);
318 state = HostState::COUNTING_DOWN;
319 reached_target = 0;
320 pspec = HostState::get_probe(target);
321 hops = NULL;
322 }
323
~HostState()324 HostState::~HostState() {
325 /* active_probes and pending_resends are subsets of unanswered_probes, so we
326 delete the allocated probes in unanswered_probes only. */
327 while (!unanswered_probes.empty()) {
328 delete *unanswered_probes.begin();
329 unanswered_probes.pop_front();
330 }
331 while (!active_probes.empty())
332 active_probes.pop_front();
333 while (!pending_resends.empty())
334 pending_resends.pop_front();
335 }
336
has_more_probes() const337 bool HostState::has_more_probes() const {
338 /* We are done if we are counting up and
339 1. we've reached and exceeded the target, or
340 2. we've exceeded MAX_TTL. */
341 return !(state == HostState::COUNTING_UP
342 && ((reached_target > 0 && current_ttl >= reached_target)
343 || current_ttl > MAX_TTL));
344 }
345
is_finished() const346 bool HostState::is_finished() const {
347 return !this->has_more_probes()
348 && active_probes.empty() && pending_resends.empty();
349 }
350
send_next_probe(int rawsd,eth_t * ethsd)351 bool HostState::send_next_probe(int rawsd, eth_t *ethsd) {
352 Probe *probe;
353
354 /* Do a resend if possible. */
355 if (!pending_resends.empty()) {
356 probe = pending_resends.front();
357 pending_resends.pop_front();
358 active_probes.push_back(probe);
359 probe->resend(rawsd, ethsd);
360 return true;
361 }
362
363 this->next_ttl();
364
365 if (!this->has_more_probes())
366 return false;
367
368 probe = Probe::make(this, pspec, current_ttl);
369 unanswered_probes.push_back(probe);
370 active_probes.push_back(probe);
371 probe->send(rawsd, ethsd);
372 sent_ttls[current_ttl] = true;
373
374 return true;
375 }
376
377 /* Find the next TTL we should send to. */
next_ttl()378 void HostState::next_ttl() {
379 assert(current_ttl > 0);
380 if (state == HostState::COUNTING_DOWN) {
381 while (current_ttl > 1 && sent_ttls[current_ttl])
382 current_ttl--;
383 if (current_ttl == 1)
384 state = HostState::COUNTING_UP;
385 }
386 /* Note no "else". */
387 if (state == HostState::COUNTING_UP) {
388 while (current_ttl <= MAX_TTL && sent_ttls[current_ttl])
389 current_ttl++;
390 }
391 }
392
cancel_probe(std::list<Probe * >::iterator it)393 int HostState::cancel_probe(std::list<Probe *>::iterator it) {
394 int count;
395
396 count = active_probes.size();
397 active_probes.remove(*it);
398 count -= active_probes.size();
399 pending_resends.remove(*it);
400 delete *it;
401 unanswered_probes.erase(it);
402
403 return count;
404 }
405
cancel_probes_below(u8 ttl)406 int HostState::cancel_probes_below(u8 ttl) {
407 std::list<Probe *>::iterator it, next;
408 int count;
409
410 count = 0;
411 for (it = unanswered_probes.begin(); it != unanswered_probes.end(); it = next) {
412 next = it;
413 next++;
414 if ((*it)->ttl < ttl)
415 count += this->cancel_probe(it);
416 }
417
418 return count;
419 }
420
cancel_probes_above(u8 ttl)421 int HostState::cancel_probes_above(u8 ttl) {
422 std::list<Probe *>::iterator it, next;
423 int count;
424
425 count = 0;
426 for (it = unanswered_probes.begin(); it != unanswered_probes.end(); it = next) {
427 next = it;
428 next++;
429 if ((*it)->ttl > ttl)
430 count += this->cancel_probe(it);
431 }
432
433 return count;
434 }
435
insert_hop(u8 ttl,const struct sockaddr_storage * addr,float rtt)436 Hop *HostState::insert_hop(u8 ttl, const struct sockaddr_storage *addr,
437 float rtt) {
438 Hop *hop, *prev, *p;
439
440 this->child_parent_ttl(ttl, &prev, &p);
441 if (p != NULL && p->ttl == ttl) {
442 hop = p;
443 /* Collision with the same TTL and a different address. */
444 if (hop->addr.ss_family == 0) {
445 /* Hit a timed-out hop. Fill in the missing address and RTT. */
446 hop->addr = *addr;
447 hop->rtt = rtt;
448 } else {
449 if (o.debugging) {
450 log_write(LOG_STDOUT, "Found existing %s", ss_to_string(&hop->addr));
451 log_write(LOG_STDOUT, " while inserting %s at TTL %d for %s\n",
452 ss_to_string(addr), ttl, target->targetipstr());
453 }
454 }
455 } else {
456 hop = new Hop(ttl, *addr, rtt);
457 hop->parent = p;
458 if (prev == NULL) {
459 size_t sslen;
460 this->hops = hop;
461 sslen = sizeof(hop->tag);
462 target->TargetSockAddr(&hop->tag, &sslen);
463 } else {
464 prev->parent = hop;
465 hop->tag = prev->tag;
466 }
467 hop_cache_insert(hop);
468 }
469
470 return hop;
471 }
472
link_to(Hop * hop)473 void HostState::link_to(Hop *hop) {
474 Hop *prev, *p;
475
476 this->child_parent_ttl(hop->ttl, &prev, &p);
477 if (hop == p) {
478 /* Already linked for this host. This can happen a reply for a higher TTL
479 results in a merge, and later a reply for a lower TTL comes back. */
480 return;
481 }
482 if (o.debugging > 1) {
483 log_write(LOG_STDOUT, "Merging traces below TTL %d for %s",
484 hop->ttl, ss_to_string(&hop->tag));
485 log_write(LOG_STDOUT, " and %s\n", target->targetipstr());
486 }
487 hop = merge_hops(&hop->tag, hop, p);
488 if (prev == NULL)
489 this->hops = hop;
490 else
491 prev->parent = hop;
492 }
493
completion_fraction() const494 double HostState::completion_fraction() const {
495 std::vector<bool>::iterator it;
496 unsigned int i, n;
497
498 if (this->is_finished())
499 return 1.0;
500
501 n = 0;
502 for (i = 0; i < sent_ttls.size(); i++) {
503 if (sent_ttls[i])
504 n++;
505 }
506
507 return (double) n / sent_ttls.size();
508 }
509
child_parent_ttl(u8 ttl,Hop ** child,Hop ** parent)510 void HostState::child_parent_ttl(u8 ttl, Hop **child, Hop **parent) {
511 *child = NULL;
512 *parent = this->hops;
513 while (*parent != NULL && (*parent)->ttl > ttl) {
514 *child = *parent;
515 *parent = (*parent)->parent;
516 }
517 }
518
distance_guess(const Target * target)519 u8 HostState::distance_guess(const Target *target) {
520 /* Use the distance from OS detection if we have it. */
521 if (target->distance != -1)
522 return target->distance;
523 else
524 /* initial_ttl is a variable with file-level scope. */
525 return initial_ttl;
526 }
527
528 /* Get the probe that will be used for the traceroute. This is the
529 highest-quality probe found in ping or port scanning, or ICMP echo if no
530 responsive probe is known. */
get_probe(const Target * target)531 struct probespec HostState::get_probe(const Target *target) {
532 struct probespec probe;
533
534 probe = target->pingprobe;
535 if (target->af() == AF_INET &&
536 (probe.type == PS_TCP || probe.type == PS_UDP || probe.type == PS_SCTP || probe.type == PS_ICMP)) {
537 /* Nothing needed. */
538 } else if (target->af() == AF_INET6 &&
539 (probe.type == PS_TCP || probe.type == PS_UDP || probe.type == PS_SCTP || probe.type == PS_ICMPV6)) {
540 /* Nothing needed. */
541 } else if (probe.type == PS_PROTO) {
542 /* If this is an IP protocol probe, fill in some fields for some common
543 protocols. We cheat and store them in the TCP-, UDP-, SCTP- and
544 ICMP-specific fields. */
545 if (probe.proto == IPPROTO_TCP) {
546 probe.pd.tcp.flags = TH_ACK;
547 probe.pd.tcp.dport = get_random_u16();
548 } else if (probe.proto == IPPROTO_UDP) {
549 probe.pd.udp.dport = get_random_u16();
550 } else if (probe.proto == IPPROTO_SCTP) {
551 probe.pd.sctp.dport = get_random_u16();
552 } else if (probe.proto == IPPROTO_ICMP) {
553 probe.pd.icmp.type = ICMP_ECHO;
554 } else if (probe.proto == IPPROTO_ICMPV6) {
555 probe.pd.icmp.type = ICMPV6_ECHO;
556 } else {
557 fatal("Unknown protocol %d", probe.proto);
558 }
559 } else {
560 /* No responsive probe known? The user probably skipped both ping and
561 port scan. Guess ICMP echo as the most likely to get a response. */
562 if (target->af() == AF_INET) {
563 probe.type = PS_ICMP;
564 probe.proto = IPPROTO_ICMP;
565 probe.pd.icmp.type = ICMP_ECHO;
566 probe.pd.icmp.code = 0;
567 } else if (target->af() == AF_INET6) {
568 probe.type = PS_ICMPV6;
569 probe.proto = IPPROTO_ICMPV6;
570 probe.pd.icmp.type = ICMPV6_ECHO;
571 probe.pd.icmp.code = 0;
572 } else {
573 fatal("Unknown address family %d", target->af());
574 }
575 }
576
577 return probe;
578 }
579
Probe(HostState * host,struct probespec pspec,u8 ttl)580 Probe::Probe(HostState *host, struct probespec pspec, u8 ttl) {
581 this->host = host;
582 this->pspec = pspec;
583 this->ttl = ttl;
584 token = Probe::token_counter++;
585 sent_time.tv_sec = 0;
586 sent_time.tv_usec = 0;
587 num_resends = 0;
588 }
589
~Probe()590 Probe::~Probe() {
591 }
592
send(int rawsd,eth_t * ethsd,struct timeval * now)593 void Probe::send(int rawsd, eth_t *ethsd, struct timeval *now) {
594 struct eth_nfo eth;
595 struct eth_nfo *ethp;
596 int decoy;
597
598 /* Set up the Ethernet handle if we're using that. */
599 if (ethsd != NULL) {
600 memcpy(eth.srcmac, host->target->SrcMACAddress(), 6);
601 memcpy(eth.dstmac, host->target->NextHopMACAddress(), 6);
602 eth.ethsd = ethsd;
603 eth.devname[0] = '\0';
604 ethp = ð
605 } else {
606 ethp = NULL;
607 }
608
609 for (decoy = 0; decoy < o.numdecoys; decoy++) {
610 struct sockaddr_storage source;
611 size_t source_len;
612 unsigned char *packet;
613 u32 packetlen;
614
615 if (decoy == o.decoyturn) {
616 source_len = sizeof(source);
617 host->target->SourceSockAddr(&source, &source_len);
618 sent_time = get_now(now);
619 } else {
620 source = o.decoys[decoy];
621 }
622
623 packet = this->build_packet(&source, &packetlen);
624 send_ip_packet(rawsd, ethp, host->target->TargetSockAddr(), packet, packetlen);
625 free(packet);
626 }
627 }
628
resend(int rawsd,eth_t * ethsd,struct timeval * now)629 void Probe::resend(int rawsd, eth_t *ethsd, struct timeval *now) {
630 num_resends++;
631 this->send(rawsd, ethsd, now);
632 }
633
is_timedout(struct timeval * now) const634 bool Probe::is_timedout(struct timeval *now) const {
635 struct timeval tv;
636
637 tv = get_now(now);
638
639 return TIMEVAL_MSEC_SUBTRACT(tv, sent_time) > PROBE_TIMEOUT;
640 }
641
may_resend() const642 bool Probe::may_resend() const {
643 return num_resends < MIN(o.getMaxRetransmissions(), MAX_RESENDS);
644 }
645
646 /* Probe is an abstract class with a missing build_packet method. These concrete
647 subclasses implement the method for different probe types. */
648
649 class ICMPProbe : public Probe
650 {
651 public:
ICMPProbe(HostState * host,struct probespec pspec,u8 ttl)652 ICMPProbe(HostState *host, struct probespec pspec, u8 ttl)
653 : Probe(host, pspec, ttl) {
654 }
655
build_packet(const struct sockaddr_storage * source,u32 * len) const656 unsigned char *build_packet(const struct sockaddr_storage *source, u32 *len) const {
657 const struct sockaddr_in *sin;
658 assert(source->ss_family == AF_INET);
659 sin = (struct sockaddr_in *) source;
660 return build_icmp_raw(&sin->sin_addr, host->target->v4hostip(), ttl,
661 0x0000, 0x00, false, NULL, 0, token, global_id,
662 pspec.pd.icmp.type, pspec.pd.icmp.code,
663 o.extra_payload, o.extra_payload_length, len);
664 }
665 };
666
667 class TCPProbe : public Probe
668 {
669 public:
TCPProbe(HostState * host,struct probespec pspec,u8 ttl)670 TCPProbe(HostState *host, struct probespec pspec, u8 ttl)
671 : Probe(host, pspec, ttl) {
672 }
build_packet(const struct sockaddr_storage * source,u32 * len) const673 unsigned char *build_packet(const struct sockaddr_storage *source, u32 *len) const {
674 const char *tcpopts;
675 int tcpoptslen;
676 u32 ack;
677
678 tcpopts = NULL;
679 tcpoptslen = 0;
680 ack = 0;
681 if ((pspec.pd.tcp.flags & TH_SYN) == TH_SYN) {
682 /* MSS 1460 bytes. */
683 tcpopts = TCP_SYN_PROBE_OPTIONS;
684 tcpoptslen = TCP_SYN_PROBE_OPTIONS_LEN;
685 } else if ((pspec.pd.tcp.flags & TH_ACK) == TH_ACK) {
686 ack = get_random_u32();
687 }
688
689 /* For TCP we encode the token in the source port. */
690 if (source->ss_family == AF_INET) {
691 const struct sockaddr_in *sin = (struct sockaddr_in *) source;
692 return build_tcp_raw(&sin->sin_addr, host->target->v4hostip(), ttl,
693 get_random_u16(), get_random_u8(), false, NULL, 0,
694 token ^ global_id, pspec.pd.tcp.dport, get_random_u32(), ack, 0x00,
695 pspec.pd.tcp.flags, get_random_u16(), 0, (const u8 *) tcpopts, tcpoptslen,
696 o.extra_payload, o.extra_payload_length, len);
697 } else if (source->ss_family == AF_INET6) {
698 const struct sockaddr_in6 *sin6 = (struct sockaddr_in6 *) source;
699 return build_tcp_raw_ipv6(&sin6->sin6_addr, host->target->v6hostip(),
700 0, 0, ttl,
701 token ^ global_id, pspec.pd.tcp.dport, get_random_u32(), ack, 0x00,
702 pspec.pd.tcp.flags, get_random_u16(), 0, (const u8 *) tcpopts, tcpoptslen,
703 o.extra_payload, o.extra_payload_length, len);
704 } else {
705 fatal("Unknown address family %u in %s.", source->ss_family, __func__);
706 }
707 }
708 };
709
710 class UDPProbe : public Probe
711 {
712 public:
UDPProbe(HostState * host,struct probespec pspec,u8 ttl)713 UDPProbe(HostState *host, struct probespec pspec, u8 ttl)
714 : Probe(host, pspec, ttl) {
715 }
build_packet(const struct sockaddr_storage * source,u32 * len) const716 unsigned char *build_packet(const struct sockaddr_storage *source, u32 *len) const {
717 const char *payload;
718 size_t payload_length;
719
720 payload = get_udp_payload(pspec.pd.udp.dport, &payload_length, 0);
721
722 /* For UDP we encode the token in the source port. */
723 if (source->ss_family == AF_INET) {
724 const struct sockaddr_in *sin = (struct sockaddr_in *) source;
725 return build_udp_raw(&sin->sin_addr, host->target->v4hostip(), ttl,
726 get_random_u16(), get_random_u8(), false, NULL, 0,
727 token ^ global_id, pspec.pd.udp.dport,
728 payload, payload_length, len);
729 } else if (source->ss_family == AF_INET6) {
730 const struct sockaddr_in6 *sin6 = (struct sockaddr_in6 *) source;
731 return build_udp_raw_ipv6(&sin6->sin6_addr, host->target->v6hostip(),
732 0, 0, ttl,
733 token ^ global_id, pspec.pd.udp.dport,
734 payload, payload_length, len);
735 } else {
736 fatal("Unknown address family %u in %s.", source->ss_family, __func__);
737 }
738 }
739 };
740
741 class SCTPProbe : public Probe
742 {
743 public:
SCTPProbe(HostState * host,struct probespec pspec,u8 ttl)744 SCTPProbe(HostState *host, struct probespec pspec, u8 ttl)
745 : Probe(host, pspec, ttl) {
746 }
build_packet(const struct sockaddr_storage * source,u32 * len) const747 unsigned char *build_packet(const struct sockaddr_storage *source, u32 *len) const {
748 struct sctp_chunkhdr_init chunk;
749
750 sctp_pack_chunkhdr_init(&chunk, SCTP_INIT, 0, sizeof(chunk),
751 get_random_u32() /*itag*/, 32768, 10, 2048, get_random_u32() /*itsn*/);
752
753 if (source->ss_family == AF_INET) {
754 const struct sockaddr_in *sin = (struct sockaddr_in *) source;
755 return build_sctp_raw(&sin->sin_addr, host->target->v4hostip(), ttl,
756 get_random_u16(), get_random_u8(), false, NULL, 0,
757 token ^ global_id, pspec.pd.sctp.dport, 0UL,
758 (char *) &chunk, sizeof(chunk),
759 o.extra_payload, o.extra_payload_length, len);
760 } else if (source->ss_family == AF_INET6) {
761 const struct sockaddr_in6 *sin6 = (struct sockaddr_in6 *) source;
762 return build_sctp_raw_ipv6(&sin6->sin6_addr, host->target->v6hostip(),
763 0, 0, ttl,
764 token ^ global_id, pspec.pd.sctp.dport, 0UL,
765 (char *) &chunk, sizeof(chunk),
766 o.extra_payload, o.extra_payload_length, len);
767 } else {
768 fatal("Unknown address family %u in %s.", source->ss_family, __func__);
769 }
770 }
771 };
772
773 class IPProtoProbe : public Probe
774 {
775 public:
IPProtoProbe(HostState * host,struct probespec pspec,u8 ttl)776 IPProtoProbe(HostState *host, struct probespec pspec, u8 ttl)
777 : Probe(host, pspec, ttl) {
778 }
build_packet(const struct sockaddr_storage * source,u32 * len) const779 unsigned char *build_packet(const struct sockaddr_storage *source, u32 *len) const {
780 /* For IP proto scan the token is put in the IP ID or flow label. */
781 if (source->ss_family == AF_INET) {
782 const struct sockaddr_in *sin = (struct sockaddr_in *) source;
783 return build_ip_raw(&sin->sin_addr, host->target->v4hostip(), pspec.proto, ttl,
784 token ^ global_id, get_random_u8(), false, NULL, 0,
785 o.extra_payload, o.extra_payload_length, len);
786 } else if (source->ss_family == AF_INET6) {
787 const struct sockaddr_in6 *sin6 = (struct sockaddr_in6 *) source;
788 return build_ipv6_raw(&sin6->sin6_addr, host->target->v6hostip(),
789 0, token ^ global_id, pspec.proto, ttl,
790 o.extra_payload, o.extra_payload_length, len);
791 } else {
792 fatal("Unknown address family %u in %s.", source->ss_family, __func__);
793 }
794 }
795 };
796
797 class ICMPv6Probe : public Probe
798 {
799 public:
ICMPv6Probe(HostState * host,struct probespec pspec,u8 ttl)800 ICMPv6Probe(HostState *host, struct probespec pspec, u8 ttl)
801 : Probe(host, pspec, ttl) {
802 }
803
build_packet(const struct sockaddr_storage * source,u32 * len) const804 unsigned char *build_packet(const struct sockaddr_storage *source, u32 *len) const {
805 const struct sockaddr_in6 *sin6;
806 assert(source->ss_family == AF_INET6);
807 sin6 = (struct sockaddr_in6 *) source;
808 return build_icmpv6_raw(&sin6->sin6_addr, host->target->v6hostip(), 0x00, 0x0000,
809 ttl, token, global_id, pspec.pd.icmp.type, pspec.pd.icmp.code,
810 o.extra_payload, o.extra_payload_length, len);
811 }
812 };
813
make(HostState * host,struct probespec pspec,u8 ttl)814 Probe *Probe::make(HostState *host, struct probespec pspec, u8 ttl)
815 {
816 if (pspec.type == PS_ICMP || (pspec.type == PS_PROTO && pspec.proto == IPPROTO_ICMP))
817 return new ICMPProbe(host, pspec, ttl);
818 else if (pspec.type == PS_TCP || (pspec.type == PS_PROTO && pspec.proto == IPPROTO_TCP))
819 return new TCPProbe(host, pspec, ttl);
820 else if (pspec.type == PS_UDP || (pspec.type == PS_PROTO && pspec.proto == IPPROTO_UDP))
821 return new UDPProbe(host, pspec, ttl);
822 else if (pspec.type == PS_SCTP || (pspec.type == PS_PROTO && pspec.proto == IPPROTO_SCTP))
823 return new SCTPProbe(host, pspec, ttl);
824 else if (pspec.type == PS_PROTO)
825 return new IPProtoProbe(host, pspec, ttl);
826 else if (pspec.type == PS_ICMPV6)
827 return new ICMPv6Probe(host, pspec, ttl);
828 else
829 fatal("Unknown probespec type in traceroute");
830
831 return NULL;
832 }
833
TracerouteState(std::vector<Target * > & targets)834 TracerouteState::TracerouteState(std::vector<Target *> &targets) {
835 std::vector<Target *>::iterator it;
836 struct sockaddr_storage srcaddr;
837 size_t sslen;
838 char pcap_filter[128];
839 int n;
840
841 assert(targets.size() > 0);
842
843 if ((o.sendpref & PACKET_SEND_ETH) && targets[0]->ifType() == devt_ethernet) {
844 /* No need to check for g_has_npcap_loopback on WIN32 because devt_loopback
845 * is checked earlier. */
846 ethsd = eth_open_cached(targets[0]->deviceName());
847 if (ethsd == NULL)
848 fatal("dnet: failed to open device %s", targets[0]->deviceName());
849 rawsd = -1;
850 } else {
851 #ifdef WIN32
852 win32_fatal_raw_sockets(targets[0]->deviceName());
853 #endif
854 rawsd = nmap_raw_socket();
855 if (rawsd < 0)
856 pfatal("traceroute: socket troubles");
857 ethsd = NULL;
858 }
859
860 /* Assume that all the targets share the same device. */
861 if((pd=my_pcap_open_live(targets[0]->deviceName(), 128, o.spoofsource, 2))==NULL)
862 fatal("%s", PCAP_OPEN_ERRMSG);
863 sslen = sizeof(srcaddr);
864 targets[0]->SourceSockAddr(&srcaddr, &sslen);
865 n = Snprintf(pcap_filter, sizeof(pcap_filter), "(ip or ip6) and dst host %s",
866 ss_to_string(&srcaddr));
867 assert(n < (int) sizeof(pcap_filter));
868 set_pcap_filter(targets[0]->deviceFullName(), pd, pcap_filter);
869 if (o.debugging)
870 log_write(LOG_STDOUT, "Packet capture filter (device %s): %s\n", targets[0]->deviceFullName(), pcap_filter);
871 for (it = targets.begin(); it != targets.end(); it++) {
872 HostState *state = new HostState(*it);
873 hosts.push_back(state);
874 active_hosts.push_back(state);
875 }
876
877 num_active_probes = 0;
878 next_sending_host = active_hosts.begin();
879 next_send_time = get_now();
880 }
881
~TracerouteState()882 TracerouteState::~TracerouteState() {
883 std::vector<HostState *>::iterator it;
884
885 if (rawsd != -1)
886 close(rawsd);
887 pcap_close(pd);
888
889 for (it = hosts.begin(); it != hosts.end(); it++)
890 delete *it;
891 }
892
next_active_host()893 void TracerouteState::next_active_host() {
894 assert(next_sending_host != active_hosts.end());
895 next_sending_host++;
896 if (next_sending_host == active_hosts.end())
897 next_sending_host = active_hosts.begin();
898 }
899
send_new_probes()900 void TracerouteState::send_new_probes() {
901 std::list<HostState *>::iterator failed_host;
902 struct timeval now;
903
904 now = get_now();
905
906 assert(!active_hosts.empty());
907 failed_host = active_hosts.end();
908 while (next_sending_host != failed_host
909 && num_active_probes < MAX_OUTSTANDING_PROBES
910 && !TIMEVAL_BEFORE(now, next_send_time)) {
911 if ((*next_sending_host)->send_next_probe(rawsd, ethsd)) {
912 num_active_probes++;
913 TIMEVAL_MSEC_ADD(next_send_time, next_send_time, o.scan_delay);
914 if (TIMEVAL_BEFORE(next_send_time, now))
915 next_send_time = now;
916 failed_host = active_hosts.end();
917 } else if (failed_host == active_hosts.end()) {
918 failed_host = next_sending_host;
919 }
920 next_active_host();
921 }
922 }
923
hop_cache_lookup(u8 ttl,const struct sockaddr_storage * addr)924 static Hop *hop_cache_lookup(u8 ttl, const struct sockaddr_storage *addr) {
925 std::map<struct HopIdent, Hop *>::iterator it;
926 HopIdent ident(ttl, *addr);
927
928 it = hop_cache.find(ident);
929 if (it == hop_cache.end())
930 return NULL;
931 else
932 return it->second;
933 }
934
hop_cache_insert(Hop * hop)935 static void hop_cache_insert(Hop *hop) {
936 if (hop->addr.ss_family == 0) {
937 timedout_hops->push_back(hop);
938 } else {
939 hop_cache[HopIdent(hop->ttl, hop->addr)] = hop;
940 }
941 }
942
hop_cache_size()943 static unsigned int hop_cache_size() {
944 return hop_cache.size() + timedout_hops->size();
945 }
946
traceroute_hop_cache_clear()947 void traceroute_hop_cache_clear() {
948 std::map<struct HopIdent, Hop *>::iterator map_iter;
949 std::list<Hop *>::iterator list_iter;
950
951 for (map_iter = hop_cache.begin(); map_iter != hop_cache.end(); map_iter++)
952 delete map_iter->second;
953 hop_cache.clear();
954 if (!timedout_hops) return;
955 for (list_iter = timedout_hops->begin(); list_iter != timedout_hops->end(); list_iter++)
956 delete *list_iter;
957 timedout_hops->clear();
958 }
959
960 /* Merge two hop chains together and return the head of the merged chain. This
961 is done when a cache hit finds that two targets share the same intermediate
962 hop; rather than doing a full trace for each target, one is linked to the
963 other. "Merged" means that, for example, if chain a has an hop at TTL 3 and
964 chain b has one for TTL 2, the merged chain will include both. Usually, the
965 chains will not have hops at the same TTL (that implies different routes to
966 the same host), but see the next paragraph for what we do when that happens.
967 Each hop in the merged chain will be tagged with the given tag.
968
969 There are many cases that must be handled correctly by this function: a and b
970 may be equal; either may be NULL; a and b may be disjoint chains or may be
971 joined somewhere. The biggest difficulty is when both of the chains have a
972 hop with the same TTL but a different address. When this happens we
973 arbitrarily choose one of the hops to unlink, on the presumption that any
974 route through the same intermediate host at a given TTL should be the same
975 and that differences aren't meaningful. (This has the same effect as if we
976 were to send probes strictly serially, because then there would be no parent
977 hops to potentially conflict, even if in fact they would if traced to
978 completion.) */
merge_hops(const struct sockaddr_storage * tag,Hop * a,Hop * b)979 static Hop *merge_hops(const struct sockaddr_storage *tag, Hop *a, Hop *b) {
980 Hop head, *p;
981
982 p = &head;
983
984 while (a != NULL && b != NULL && a != b) {
985 Hop **next;
986
987 if (a->ttl > b->ttl) {
988 next = &a;
989 } else if (b->ttl > a->ttl) {
990 next = &b;
991 } else {
992 Hop **discard, *parent;
993
994 if (b->addr.ss_family == 0) {
995 next = &a;
996 discard = &b;
997 } else if (a->addr.ss_family == 0) {
998 next = &b;
999 discard = &a;
1000 } else {
1001 next = &a;
1002 discard = &b;
1003 if (o.debugging) {
1004 log_write(LOG_STDOUT, "Warning: %s", ss_to_string(&(*next)->addr));
1005 log_write(LOG_STDOUT, " doesn't match %s at TTL %d;",
1006 ss_to_string(&(*discard)->addr), a->ttl);
1007 log_write(LOG_STDOUT, " arbitrarily discarding %s\n",
1008 ss_to_string(&(*discard)->addr));
1009 }
1010 }
1011 parent = (*discard)->parent;
1012 *discard = parent;
1013 }
1014 p->parent = *next;
1015 p->tag = *tag;
1016 p = p->parent;
1017 *next = (*next)->parent;
1018 }
1019 /* At most one branch of this is taken, even when a == b. */
1020 if (a != NULL)
1021 p->parent = a;
1022 else if (b != NULL)
1023 p->parent = b;
1024 for (; p != NULL; p = p->parent)
1025 p->tag = *tag;
1026
1027 return head.parent;
1028 }
1029
1030 /* Record a hop at the given TTL for the given host. This takes care of linking
1031 the hop into the host's chain as well as into the global hop tree. */
set_host_hop(HostState * host,u8 ttl,const struct sockaddr_storage * from_addr,float rtt)1032 void TracerouteState::set_host_hop(HostState *host, u8 ttl,
1033 const struct sockaddr_storage *from_addr, float rtt) {
1034 Hop *hop;
1035
1036 if (o.debugging > 1) {
1037 log_write(LOG_STDOUT, "Set hop %s TTL %d to %s RTT %.2f ms\n",
1038 host->target->targetipstr(), ttl, ss_to_string(from_addr), rtt);
1039 }
1040
1041 hop = hop_cache_lookup(ttl, from_addr);
1042 if (hop == NULL) {
1043 /* A new hop, never before seen with this address and TTL. Add it to the
1044 host's chain and to the global cache. */
1045 hop = host->insert_hop(ttl, from_addr, rtt);
1046 } else {
1047 /* An existing hop at this address and TTL. Link this host's chain to it. */
1048 if (o.debugging > 1) {
1049 log_write(LOG_STDOUT, "Traceroute cache hit %s TTL %d while tracing",
1050 ss_to_string(&hop->addr), hop->ttl);
1051 log_write(LOG_STDOUT, " %s TTL %d\n", host->target->targetipstr(), ttl);
1052 }
1053
1054 host->link_to(hop);
1055
1056 if (host->state == HostState::COUNTING_DOWN) {
1057 /* Hit the cache going down. Seek to the end of the chain. If we have the
1058 tag for the last node, we take responsibility for finishing the trace.
1059 Otherwise, start counting up. */
1060 struct sockaddr_storage addr;
1061 size_t sslen;
1062
1063 while (hop->parent != NULL) {
1064 hop = hop->parent;
1065 /* No need to re-probe any merged hops. */
1066 host->sent_ttls[hop->ttl] = true;
1067 }
1068 sslen = sizeof(addr);
1069 host->target->TargetSockAddr(&addr, &sslen);
1070 if (sockaddr_storage_equal(&hop->tag, &addr)) {
1071 if (o.debugging > 1) {
1072 log_write(LOG_STDOUT, "%s continuing trace from TTL %d\n",
1073 host->target->targetipstr(), host->current_ttl);
1074 }
1075 } else {
1076 host->state = HostState::COUNTING_UP;
1077 num_active_probes -= host->cancel_probes_below(ttl);
1078 }
1079 }
1080 }
1081 }
1082
1083 /* Record that a hop at the given TTL for the given host timed out. */
set_host_hop_timedout(HostState * host,u8 ttl)1084 void TracerouteState::set_host_hop_timedout(HostState *host, u8 ttl) {
1085 static struct sockaddr_storage EMPTY_ADDR = { 0 };
1086 host->insert_hop(ttl, &EMPTY_ADDR, -1.0);
1087 }
1088
1089 struct Reply {
1090 struct timeval rcvdtime;
1091 struct sockaddr_storage from_addr;
1092 struct sockaddr_storage target_addr;
1093 u8 ttl;
1094 u16 token;
1095 };
1096
parse_encapsulated_reply(const void * ip,unsigned len,Reply * reply)1097 static bool parse_encapsulated_reply(const void *ip, unsigned len, Reply *reply) {
1098 struct abstract_ip_hdr hdr;
1099 const void *data;
1100
1101 data = ip_get_data(ip, &len, &hdr);
1102 if (data == NULL)
1103 return false;
1104
1105 if (hdr.version == 4 && hdr.proto == IPPROTO_ICMP) {
1106 const struct icmp *icmp = (const struct icmp *) data;
1107 if (len < 8 || ntohs(icmp->icmp_id) != global_id)
1108 return false;
1109 reply->token = ntohs(icmp->icmp_seq);
1110 } else if (hdr.version == 6 && hdr.proto == IPPROTO_ICMPV6) {
1111 const struct icmpv6_msg_echo *echo = (struct icmpv6_msg_echo *) ((char *) data + sizeof(struct icmpv6_hdr));
1112 if (len < 8 || ntohs(echo->icmpv6_id) != global_id)
1113 return false;
1114 reply->token = ntohs(echo->icmpv6_seq);
1115 } else if (hdr.proto == IPPROTO_TCP) {
1116 const struct tcp_hdr *tcp = (const struct tcp_hdr *) data;
1117 if (len < 2)
1118 return false;
1119 reply->token = ntohs(tcp->th_sport) ^ global_id;
1120 } else if (hdr.proto == IPPROTO_UDP) {
1121 const struct udp_hdr *udp = (const struct udp_hdr *) data;
1122 if (len < 2)
1123 return false;
1124 reply->token = ntohs(udp->uh_sport) ^ global_id;
1125 } else if (hdr.proto == IPPROTO_SCTP) {
1126 const struct sctp_hdr *sctp = (const struct sctp_hdr *) data;
1127 if (len < 2)
1128 return false;
1129 reply->token = ntohs(sctp->sh_sport) ^ global_id;
1130 } else {
1131 if (len < 6)
1132 return false;
1133 /* Check IP ID for proto scan. */
1134 reply->token = hdr.ipid ^ global_id;
1135 }
1136
1137 reply->target_addr = hdr.dst;
1138
1139 return true;
1140 }
1141
decode_reply(const void * ip,unsigned int len,Reply * reply)1142 static bool decode_reply(const void *ip, unsigned int len, Reply *reply) {
1143 struct abstract_ip_hdr hdr;
1144 const void *data;
1145
1146 data = ip_get_data(ip, &len, &hdr);
1147 if (data == NULL)
1148 return false;
1149
1150 reply->from_addr = hdr.src;
1151 reply->ttl = hdr.ttl;
1152
1153 if (hdr.version == 4 && hdr.proto == IPPROTO_ICMP) {
1154 /* ICMP responses comprise all the TTL exceeded messages we expect from all
1155 probe types, as well as actual replies from ICMP probes. */
1156 const struct icmp_hdr *icmp = (const struct icmp_hdr *) data;
1157 if (len < 8)
1158 return false;
1159 if ((icmp->icmp_type == ICMP_TIMEXCEED
1160 && icmp->icmp_code == ICMP_TIMEXCEED_INTRANS)
1161 || icmp->icmp_type == ICMP_UNREACH) {
1162 /* Get the encapsulated IP packet. */
1163 const void *encaps = icmp_get_data(icmp, &len);
1164 if (encaps == NULL)
1165 return false;
1166 return parse_encapsulated_reply(encaps, len, reply);
1167 } else if (icmp->icmp_type == ICMP_ECHOREPLY
1168 || icmp->icmp_type == ICMP_MASKREPLY
1169 || icmp->icmp_type == ICMP_TSTAMPREPLY) {
1170 /* Need this alternate form of header for icmp_id and icmp_seq. */
1171 const struct icmp *icmp = (const struct icmp *) data;
1172
1173 if (ntohs(icmp->icmp_id) != global_id)
1174 return false;
1175 reply->token = ntohs(icmp->icmp_seq);
1176 /* Reply came directly from the target. */
1177 reply->target_addr = reply->from_addr;
1178 } else {
1179 return false;
1180 }
1181 } else if (hdr.version == 6 && hdr.proto == IP_PROTO_ICMPV6) {
1182 /* ICMPv6 responses comprise all the TTL exceeded messages we expect from
1183 all probe types, as well as actual replies from ICMP probes. */
1184 const struct icmpv6_hdr *icmpv6 = (const struct icmpv6_hdr *) data;
1185 if (len < 2)
1186 return false;
1187 /* TIMEXCEED, UNREACH */
1188 if ((icmpv6->icmpv6_type == ICMPV6_TIMEXCEED
1189 && icmpv6->icmpv6_code == ICMPV6_TIMEXCEED_INTRANS)
1190 || icmpv6->icmpv6_type == ICMPV6_UNREACH) {
1191 /* Get the encapsulated IP packet. */
1192 const void *encaps = icmpv6_get_data(icmpv6, &len);
1193 if (encaps == NULL)
1194 return false;
1195 return parse_encapsulated_reply(encaps, len, reply);
1196 } else if (icmpv6->icmpv6_type == ICMPV6_ECHOREPLY) {
1197 /* MASKREPLY, TSTAMPREPLY */
1198 const struct icmpv6_msg_echo *echo;
1199
1200 if (len < sizeof(*icmpv6) + 4)
1201 return false;
1202 echo = (struct icmpv6_msg_echo *) ((char *) icmpv6 + sizeof(*icmpv6));
1203 if (ntohs(echo->icmpv6_id) != global_id)
1204 return false;
1205 reply->token = ntohs(echo->icmpv6_seq);
1206 /* Reply came directly from the target. */
1207 reply->target_addr = reply->from_addr;
1208 } else {
1209 return false;
1210 }
1211 } else if (hdr.proto == IPPROTO_TCP) {
1212 const struct tcp_hdr *tcp = (const struct tcp_hdr *) data;
1213 if (len < 4)
1214 return false;
1215 reply->token = ntohs(tcp->th_dport) ^ global_id;
1216 reply->target_addr = reply->from_addr;
1217 } else if (hdr.proto == IPPROTO_UDP) {
1218 const struct udp_hdr *udp = (const struct udp_hdr *) data;
1219 if (len < 4)
1220 return false;
1221 reply->token = ntohs(udp->uh_dport) ^ global_id;
1222 reply->target_addr = reply->from_addr;
1223 } else if (hdr.proto == IPPROTO_SCTP) {
1224 const struct sctp_hdr *sctp = (const struct sctp_hdr *) data;
1225 if (len < 4)
1226 return false;
1227 reply->token = ntohs(sctp->sh_dport) ^ global_id;
1228 reply->target_addr = reply->from_addr;
1229 } else {
1230 return false;
1231 }
1232
1233 return true;
1234 }
1235
read_reply(Reply * reply,pcap_t * pd,long timeout)1236 static bool read_reply(Reply *reply, pcap_t *pd, long timeout) {
1237 const struct ip *ip;
1238 unsigned int iplen;
1239 struct link_header linkhdr;
1240
1241 ip = (struct ip *) readip_pcap(pd, &iplen, timeout, &reply->rcvdtime, &linkhdr, true);
1242 if (ip == NULL)
1243 return false;
1244 if (ip->ip_v == 4 || ip->ip_v == 6)
1245 return decode_reply(ip, iplen, reply);
1246 else
1247 return false;
1248 }
1249
read_replies(long timeout)1250 void TracerouteState::read_replies(long timeout) {
1251 struct sockaddr_storage ss;
1252 struct timeval now;
1253 size_t sslen;
1254 Reply reply;
1255
1256 assert(timeout / 1000 <= (long) o.scan_delay);
1257 timeout = MAX(timeout, 10000);
1258 now = get_now();
1259
1260 while (timeout > 0 && read_reply(&reply, pd, timeout)) {
1261 std::list<Probe *>::iterator it;
1262 struct timeval oldnow;
1263 HostState *host;
1264 Probe *probe;
1265 float rtt;
1266
1267 oldnow = now;
1268 now = get_now();
1269 timeout -= TIMEVAL_SUBTRACT(now, oldnow);
1270
1271 probe = this->lookup_probe(&reply.target_addr, reply.token);
1272 if (probe == NULL)
1273 continue;
1274 host = probe->host;
1275
1276 sslen = sizeof(ss);
1277 host->target->TargetSockAddr(&ss, &sslen);
1278 if (sockaddr_storage_equal(&ss, &reply.from_addr)) {
1279 adjust_timeouts2(&probe->sent_time, &reply.rcvdtime, &host->target->to);
1280 if (host->reached_target == 0 || probe->ttl < host->reached_target)
1281 host->reached_target = probe->ttl;
1282 if (host->state == HostState::COUNTING_DOWN) {
1283 /* If this probe was past the target, skip ahead to what we think the
1284 actual distance is. */
1285 int distance = get_initial_ttl_guess(reply.ttl) - reply.ttl + 1;
1286 if (distance > 0 && distance < host->current_ttl)
1287 host->current_ttl = MIN(distance, MAX_TTL);
1288 }
1289 num_active_probes -= host->cancel_probes_above(probe->ttl);
1290 }
1291
1292 rtt = TIMEVAL_SUBTRACT(reply.rcvdtime, probe->sent_time) / 1000.0;
1293 set_host_hop(host, probe->ttl, &reply.from_addr, rtt);
1294
1295 it = find(host->unanswered_probes.begin(), host->unanswered_probes.end(), probe);
1296 num_active_probes -= host->cancel_probe(it);
1297 }
1298 }
1299
cull_timeouts()1300 void TracerouteState::cull_timeouts() {
1301 std::list<HostState *>::iterator host_iter;
1302 struct timeval now;
1303
1304 now = get_now();
1305
1306 for (host_iter = active_hosts.begin(); host_iter != active_hosts.end(); host_iter++) {
1307 while (!(*host_iter)->active_probes.empty()
1308 && (*host_iter)->active_probes.front()->is_timedout(&now)) {
1309 Probe *probe;
1310
1311 probe = (*host_iter)->active_probes.front();
1312 if (o.debugging > 1) {
1313 log_write(LOG_STDOUT, "Traceroute probe to %s TTL %d timed out\n",
1314 probe->host->target->targetipstr(), probe->ttl);
1315 }
1316 set_host_hop_timedout(*host_iter, probe->ttl);
1317 (*host_iter)->active_probes.pop_front();
1318 num_active_probes--;
1319 if (probe->may_resend())
1320 (*host_iter)->pending_resends.push_front(probe);
1321 }
1322 }
1323 }
1324
remove_finished_hosts()1325 void TracerouteState::remove_finished_hosts() {
1326 std::list<HostState *>::iterator it, next;
1327
1328 for (it = active_hosts.begin(); it != active_hosts.end(); it = next) {
1329 next = it;
1330 next++;
1331 if ((*it)->is_finished()) {
1332 if (next_sending_host == it)
1333 next_active_host();
1334 active_hosts.erase(it);
1335 }
1336 }
1337 }
1338
1339 /* Dummy class to use sockaddr_storage as a map key. */
1340 struct lt_sockaddr_storage {
operator ()lt_sockaddr_storage1341 bool operator()(const struct sockaddr_storage& a, const struct sockaddr_storage& b) const {
1342 return sockaddr_storage_cmp(&a, &b) < 0;
1343 }
1344 };
1345
1346 /* Find the reverse-DNS names of the hops. */
resolve_hops()1347 void TracerouteState::resolve_hops() {
1348 std::set<sockaddr_storage, lt_sockaddr_storage> addrs;
1349 std::set<sockaddr_storage, lt_sockaddr_storage>::iterator addr_iter;
1350 std::vector<HostState *>::iterator host_iter;
1351 std::map<sockaddr_storage, const char *, lt_sockaddr_storage> name_map;
1352 Target **targets;
1353 Hop *hop;
1354 int i, n;
1355
1356 /* First, put all the IPv4 addresses in a set to remove duplicates. This
1357 re-resolves the addresses of the targets themselves, which is a little
1358 inefficient. */
1359 for (host_iter = hosts.begin(); host_iter != hosts.end(); host_iter++) {
1360 for (hop = (*host_iter)->hops; hop != NULL; hop = hop->parent) {
1361 if (hop->addr.ss_family != AF_UNSPEC)
1362 addrs.insert(hop->addr);
1363 }
1364 }
1365 n = addrs.size();
1366 /* Second, make an array of pointer to Target to suit the interface of
1367 nmap_mass_rdns. */
1368 targets = (Target **) safe_malloc(sizeof(*targets) * n);
1369 i = 0;
1370 addr_iter = addrs.begin();
1371 while (i < n) {
1372 targets[i] = new Target();
1373 targets[i]->setTargetSockAddr(&*addr_iter, sizeof(*addr_iter));
1374 targets[i]->flags = HOST_UP;
1375 i++;
1376 addr_iter++;
1377 }
1378 nmap_mass_rdns(targets, n);
1379 /* Third, make a map from addresses to names for easy lookup. */
1380 for (i = 0; i < n; i++) {
1381 struct sockaddr_storage ss;
1382 size_t ss_len;
1383 const char *hostname = targets[i]->HostName();
1384 if (*hostname == '\0')
1385 hostname = NULL;
1386 ss_len = sizeof(ss);
1387 targets[i]->TargetSockAddr(&ss, &ss_len);
1388 name_map[ss] = hostname;
1389 }
1390 /* Finally, copy the names into the hops. */
1391 for (host_iter = hosts.begin(); host_iter != hosts.end(); host_iter++) {
1392 for (hop = (*host_iter)->hops; hop != NULL; hop = hop->parent) {
1393 if (hop->addr.ss_family != AF_UNSPEC) {
1394 const char *hostname = name_map[hop->addr];
1395 if (hostname != NULL)
1396 hop->hostname = hostname;
1397 }
1398 }
1399 }
1400 for (i = 0; i < n; i++)
1401 delete targets[i];
1402 free(targets);
1403 }
1404
transfer_hops()1405 void TracerouteState::transfer_hops() {
1406 std::vector<HostState *>::iterator it;
1407 Hop *p;
1408
1409 for (it = hosts.begin(); it != hosts.end(); it++) {
1410 for (p = (*it)->hops; p != NULL; p = p->parent) {
1411 TracerouteHop hop;
1412
1413 /* Trim excessive hops. */
1414 if ((*it)->reached_target && p->ttl > (*it)->reached_target)
1415 continue;
1416
1417 hop.tag = p->tag;
1418 if (p->addr.ss_family == 0) {
1419 hop.timedout = true;
1420 } else {
1421 hop.timedout = false;
1422 hop.rtt = p->rtt;
1423 }
1424 hop.name = p->hostname;
1425 hop.addr = p->addr;
1426 hop.ttl = p->ttl;
1427 (*it)->target->traceroute_hops.push_front(hop);
1428 }
1429
1430 (*it)->target->traceroute_probespec = (*it)->pspec;
1431
1432 /* Set the hop distance for OS fingerprints. */
1433 if ((*it)->reached_target) {
1434 (*it)->target->distance = (*it)->reached_target;
1435 (*it)->target->distance_calculation_method = DIST_METHOD_TRACEROUTE;
1436 }
1437 }
1438 }
1439
lookup_probe(const struct sockaddr_storage * target_addr,u16 token)1440 Probe *TracerouteState::lookup_probe(
1441 const struct sockaddr_storage *target_addr, u16 token) {
1442 std::list<HostState *>::iterator host_iter;
1443 std::list<Probe *>::iterator probe_iter;
1444
1445 for (host_iter = active_hosts.begin(); host_iter != active_hosts.end(); host_iter++) {
1446 struct sockaddr_storage ss;
1447 size_t sslen;
1448
1449 sslen = sizeof(ss);
1450 (*host_iter)->target->TargetSockAddr(&ss, &sslen);
1451 if (!sockaddr_storage_equal(&ss, target_addr))
1452 continue;
1453 for (probe_iter = (*host_iter)->unanswered_probes.begin();
1454 probe_iter != (*host_iter)->unanswered_probes.end();
1455 probe_iter++) {
1456 if ((*probe_iter)->token == token)
1457 return *probe_iter;
1458 }
1459 }
1460
1461 return NULL;
1462 }
1463
completion_fraction() const1464 double TracerouteState::completion_fraction() const {
1465 std::vector<HostState *>::const_iterator it;
1466 double sum;
1467
1468 sum = 0.0;
1469 for (it = hosts.begin(); it != hosts.end(); it++)
1470 sum += (*it)->completion_fraction();
1471 return sum / hosts.size();
1472 }
1473
1474 /* This is a special case of traceroute when all the targets are directly
1475 connected. Because the distance to each target is known to be 1, we send no
1476 probes at all, only fill in a TracerouteHop structure. */
traceroute_direct(std::vector<Target * > targets)1477 static int traceroute_direct(std::vector<Target *> targets) {
1478 std::vector<Target *>::iterator it;
1479
1480 for (it = targets.begin(); it != targets.end(); it++) {
1481 TracerouteHop hop;
1482 const char *hostname;
1483 size_t sslen;
1484
1485 sslen = sizeof(hop.tag);
1486 (*it)->TargetSockAddr(&hop.tag, &sslen);
1487 hop.timedout = false;
1488 hop.rtt = (*it)->to.srtt / 1000.0;
1489 hostname = (*it)->HostName();
1490 if (hostname != NULL && hostname[0] != '\0')
1491 hop.name = hostname;
1492 hop.addr = hop.tag;
1493 hop.ttl = 1;
1494 (*it)->traceroute_hops.push_front(hop);
1495 }
1496
1497 return 1;
1498 }
1499
traceroute_remote(std::vector<Target * > targets)1500 static int traceroute_remote(std::vector<Target *> targets) {
1501 std::vector<Target *>::iterator target_iter;
1502
1503 if (targets.empty())
1504 return 1;
1505
1506 if (timedout_hops == NULL) {
1507 timedout_hops = new std::list<Hop *>;
1508 }
1509
1510 TracerouteState global_state(targets);
1511
1512 global_id = get_random_u16();
1513
1514 ScanProgressMeter SPM("Traceroute");
1515
1516 o.current_scantype = TRACEROUTE;
1517
1518 while (!global_state.active_hosts.empty()) {
1519 struct timeval now;
1520 long int timeout;
1521
1522 global_state.send_new_probes();
1523 now = get_now();
1524 timeout = TIMEVAL_SUBTRACT(global_state.next_send_time, now);
1525 global_state.read_replies(timeout);
1526 global_state.cull_timeouts();
1527 global_state.remove_finished_hosts();
1528
1529 if (keyWasPressed())
1530 SPM.printStats(global_state.completion_fraction(), NULL);
1531 }
1532
1533 SPM.endTask(NULL, NULL);
1534
1535 if (!o.noresolve)
1536 global_state.resolve_hops();
1537 /* This puts the hops into the targets known by the global_state. */
1538 global_state.transfer_hops();
1539
1540 /* Update initial_ttl to be the highest distance seen in this host group, as
1541 an estimate for the next. */
1542 initial_ttl = 0;
1543 for (target_iter = targets.begin();
1544 target_iter != targets.end();
1545 target_iter++) {
1546 initial_ttl = MAX(initial_ttl, (*target_iter)->traceroute_hops.size());
1547 }
1548
1549 if (hop_cache_size() > MAX_HOP_CACHE_SIZE) {
1550 if (o.debugging) {
1551 log_write(LOG_STDOUT, "Clearing hop cache that has grown to %d\n",
1552 hop_cache_size());
1553 }
1554 traceroute_hop_cache_clear();
1555 }
1556
1557 return 1;
1558 }
1559
traceroute(std::vector<Target * > & Targets)1560 int traceroute(std::vector<Target *> &Targets) {
1561 std::vector<Target *> direct, remote;
1562 std::vector<Target *>::iterator target_iter;
1563
1564 /* Separate directly connected targets from remote targets. */
1565 for (target_iter = Targets.begin();
1566 target_iter != Targets.end();
1567 target_iter++) {
1568 if ((*target_iter)->ifType() == devt_loopback)
1569 ; /* Ignore */
1570 else if ((*target_iter)->directlyConnected())
1571 direct.push_back(*target_iter);
1572 else
1573 remote.push_back(*target_iter);
1574 }
1575
1576 traceroute_direct(direct);
1577 traceroute_remote(remote);
1578
1579 return 1;
1580 }
1581
get_now(struct timeval * now)1582 static struct timeval get_now(struct timeval *now) {
1583 struct timeval tv;
1584
1585 if (now != NULL)
1586 return *now;
1587 gettimeofday(&tv, NULL);
1588
1589 return tv;
1590 }
1591
1592 /* Convert the address in ss to a string. The result is returned in a static
1593 buffer so you can't call this twice in arguments to printf, for example. */
ss_to_string(const struct sockaddr_storage * ss)1594 static const char *ss_to_string(const struct sockaddr_storage *ss) {
1595 return inet_ntop_ez(ss, sizeof(*ss));
1596 }
1597