Network programming in Linux

Implementing traceroute


Introduction
Getting started with libpcap

Extracting Ethernet information
Internet Protocol (IP)

Filtering captured datagrams
Capturing datagrams offline

Address Resolution Protocol (ARP)
Internet Control Message Protocol (ICMP)
Transmission Control Protocol (TCP)
User Datagram Protocol (UDP)
Trivial File Transfer Protocol (TFTP)

Injecting datagrams with libnet
Implementing ping
Implementing traceroute

Download source code


traceroute is a computer network diagnostic tool for displaying the route and measuring transit delays of datagrams across a network. The route is recorded as the round-trip times of datagrams received from each successive intermediate host in the route to a destination. The traceroute command is available on most operating systems, including Windows, Mac OS and Linux.

traceroute sends a sequence of ICMP Echo Request packets addressed to a destination host. The time-to-live (TTL) value, also known as hop limit, is used in determining the intermediate routers being traversed towards the destination. traceroute works by sending ICMP Echo Request packets with gradually increasing TTL value, starting with TTL value 1. The first router receives the packet, decrements the TTL value and drops the packet because its TTL value is down to zero. The router sends an ICMP Time Exceeded packet back to the source. The next packet is given a TTL value of 2, so the first router forwards the packet, but the second router drops it and replies with ICMP Time Exceeded. Proceeding this way, traceroute uses the returned ICMP Time Exceeded packets to build a list of routers that packets traverse, until the destination is reached and returns an ICMP Echo Reply packet.

Since routers and firewalls are often configured not to respond to ICMP Echo Request packets (to minimize risks related to network discovery performed in hacking attempts), traceroute uses a default wait time of 5 seconds for a reply to a request. When there is timeout (i.e. an intermediate host has dropped the packet but not returned an ICMP Time Exceeded packet), traceroute displays asterisks and proceeds to the next TTL value.

Since traceroute essentially performs successive pings of increasing TTL values and expects ICMP Time Exceeded responses as well as ICMP Echo Reply packets, the following traceroute implementation is an enhanced version of the previous ping implementation (ping.cpp). All grayed out code is (mostly) identical to ping.cpp.

traceroute.cpp
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
#include <iostream>
#include <sstream>
#include <cstdlib>        // sprintf, exit
#include <signal.h>       // Ctrl+C handling
#include <sys/time.h>     // gettimeofday

#include "datagram.h"     // Datagram
#include "ippacket.h"     // IPPacket
#include "icmppacket.h"   // ICMPPacket
#include "exceptions.h"   // EBadTransportException

#include <libnet.h>       // libnet
#include <pcap.h>         // libpcap

using namespace std;

libnet_t    *libnet_ctx  = NULL;    // libnet session context
pcap_t      *pcap_ctx    = NULL;    // libpcap session context
bpf_program  pcap_filter;           // libpcap filter for echo replies

// Function releasing all resources before ending program execution
void shutdown(int error_code) {
  // Free libnet session context
  if (libnet_ctx) 
    libnet_destroy(libnet_ctx);

  // Free libpcap filter
  if (pcap_ctx) 
    pcap_freecode(&pcap_filter);

  // Free libpcap session context
  if (pcap_ctx) 
    pcap_close(pcap_ctx);

  exit(error_code); // we're done!
}

// Ctrl+C interrupt handler
void bypass_sigint(int sig_no) {
  cout << endl << "*** Interrupted by user..." << endl;

  shutdown(0); // we're done!
}

// Returns current time in milliseconds
unsigned long get_clock() {
  struct timeval tv;
  gettimeofday(&tv, NULL);

  return tv.tv_sec * 1000 + tv.tv_usec / 1000;
}

// Implementation of traceroute
int main(int argc, char *argv[]) {
  const unsigned int MAX_HOPS = 30;      // max nuber of hops tried
  const unsigned int TIMEOUT  = 5000;    // max time waiting for echo reply
  
  char       *device = NULL;             // device to sniff
  u_int32_t   target_addr;               // IP of target host
  u_int32_t   host_addr;                 // IP of local host
  bpf_u_int32 netp,                      // network IP of local device 
              maskp;                     // network IP mask of local device

  // We must make error buffer large enough to hold both libpcap and libnet messages
  char errbuf[PCAP_ERRBUF_SIZE > LIBNET_ERRBUF_SIZE? PCAP_ERRBUF_SIZE : LIBNET_ERRBUF_SIZE];  
  
  // Make sure we have a target to ping
  if (argc < 2) {
    cerr << "error - no target to ping" << endl;
    shutdown(-1);    // Cleanup and quit
  }

  // Install Ctrl+C handler
  struct sigaction sa, osa;
  memset(&sa, 0, sizeof(sa));
  sa.sa_handler = &bypass_sigint;
  sigaction(SIGINT, &sa, &osa);

  // Identify device to use
  if ((device = pcap_lookupdev(errbuf)) == NULL) {
    cerr << "error - pcap_lookupdev() failed (" << errbuf << ")" << endl;
    shutdown(-2);    // Cleanup and quit
  }

  // Get libpcap session context and validate
  pcap_ctx = pcap_open_live(device, 1600, 0, TIMEOUT, errbuf);
  if (pcap_ctx == NULL) {
    cerr << "error - pcap_open_live() failed (" << errbuf << ")" << endl;
    shutdown(-3);    // Cleanup and quit
  }

  // Get libnet session context and validate 
  libnet_ctx = libnet_init(LIBNET_RAW4, device, errbuf);
  if (libnet_ctx == NULL) {
    cerr << "error - libnet_init() failed (" << errbuf << ")" << endl;
    shutdown(-4);    // Cleanup and quit
  }
   
  // Get network mask of local device
  if ((pcap_lookupnet(device, &netp, &maskp, errbuf)) == -1) {
    cerr << "error - libnet_lookupnet() failed (" << errbuf << ")" << endl;
    shutdown(-5);    // Cleanup and quit
  }

  // Get IPv4 address given to device
  host_addr = libnet_get_ipaddr4(libnet_ctx);
  if (host_addr == -1) {
    cerr << "error - libnet_get_ipaddr4 failed (" << libnet_geterror(libnet_ctx) << ")" << endl;
    shutdown(-6);    // Cleanup and quit
  }

  // Convert target IP into integer form (with DNS resolution if needed)
  if ((target_addr = libnet_name2addr4(libnet_ctx, argv[1], LIBNET_RESOLVE)) == -1) {
    cerr << "error - can't resolve " << argv[1] << endl;
    shutdown(-6);    // Cleanup and quit
  }
  
  // Build filter to capture only returned echo replies from target host with
  // this process' PID as identifier, or TTL exceeded from any host
  char filter[255];
  sprintf(filter, "icmp && ((icmp[0]=0 && src host %s && icmp[4:2]=%d) or icmp[0]=11)", 
                  libnet_addr2name4(target_addr, LIBNET_DONT_RESOLVE), getpid());

  // Compile BPF filter expression into program if one provided
  if (pcap_compile(pcap_ctx, &pcap_filter, filter, 0x100, maskp) < 0) {
    cerr << "error - pcap_compile() failed (" << pcap_geterr(pcap_ctx) << ")" << endl;
    shutdown(-7);    // Cleanup and quit 
  }

  // Install compiled filter
  if (pcap_setfilter(pcap_ctx, &pcap_filter) < 0) {
    cerr << "error - pcap_setfilter() failed (" << pcap_geterr(pcap_ctx) << ")" << endl; 
    shutdown(-8);    // Cleanup and quit 
  }

  // Display target info
  cout << "TRACEROUTE to " << argv[1] << " (" << libnet_addr2name4(target_addr, LIBNET_DONT_RESOLVE) 
       << "), " << MAX_HOPS << " hops max" << endl;
       
  // Injection loop
  for (unsigned int ttl = 1; ttl < MAX_HOPS; ttl++) {
    // Tags for handling datagram building
    libnet_ptag_t icmp_ptag = LIBNET_PTAG_INITIALIZER;
    libnet_ptag_t ip_ptag   = LIBNET_PTAG_INITIALIZER;

    // Construct an ICMP Echo Request datagram
    icmp_ptag = libnet_build_icmpv4_echo(ICMP_ECHO, 0, 0, getpid(), ttl, NULL, 0, libnet_ctx, icmp_ptag);
    if (icmp_ptag == -1) {
      cerr << "error - can't build ICMP header (" << libnet_geterror(libnet_ctx) << ")" << endl;
      shutdown(-9); 
    }

    // Construct an IP packet to encapsulate the ICMP datagram
    ip_ptag = libnet_build_ipv4(LIBNET_IPV4_H + LIBNET_ICMPV4_ECHO_H, 0, getpid(), 0, ttl, IPPROTO_ICMP,
                                0, host_addr, target_addr, NULL, 0, libnet_ctx, ip_ptag);
    if (ip_ptag == -1) {
      cerr << "error - can't build IP header (" << libnet_geterror(libnet_ctx) << ")" << endl;
      shutdown(-10); 
    }

    // Inject the resulting datagram and make sure it worked
    int bytes = libnet_write(libnet_ctx);
    if (bytes == -1){
      cerr << "error - failed to inject (" << libnet_geterror(libnet_ctx) << ")" << endl;

      continue;  // proceed to next ping
    }
    
    unsigned int delay = get_clock();  // record time of packet departure

    cout << ttl << ": " << flush;

    // Capture upcoming echo reply. We use a do-while loop since pcap_next
    // sometimes fails to read... Dunno why!
    struct pcap_pkthdr hdr;
    u_char * packet;   
    do { 
      packet = (u_char *)pcap_next(pcap_ctx, &hdr);
    } while (!packet && (get_clock() - delay < TIMEOUT));
    
    delay = get_clock() - delay;       // calculate response delay
    
    // Make sure we got a response (we may have got a timeout)
    if (packet) {
      try {
        Datagram pkt(packet, hdr.caplen);    // initialized Datagram instance       
        IPPacket ip = pkt.ethernet().ip4();  // get captured IP packet
        ICMPPacket icmp = ip.icmp();         // get captured ICMP packet

        // Reverse DNS to get domain name (if there is one)
        ostringstream ostr;
        ostr << ip.source_ip();

        char buff[255];
        strcpy(buff, ostr.str().c_str());
        u_int32_t ip_addr = libnet_name2addr4(libnet_ctx, buff, LIBNET_DONT_RESOLVE);

        // Display intermediate host's IP and domain name
        cout << libnet_addr2name4(ip_addr, LIBNET_RESOLVE) 
             << " (" << ip.source_ip() << ")  " << delay << " ms" << endl;

        // Have we reached the target?
        if (icmp.type() == 0) {
          cout << " >>> target reached" << endl;
          break;
        }
      }
      catch (EBadTransportException) {
        cerr << "error - unexpected returned datagram!" << endl;
      }
    }
    else
      cout << "* * *" << endl;

    libnet_clear_packet(libnet_ctx);   // clear datagram associated to context (optional)
  }
  
  // Shutdown the application
  shutdown(0);
}

Here are the main characteristics of the above code:

  • Two constants are defined at line #055: MAX_HOPS imposes a maximum number of TTL value to attempt, and TIMEOUT fixes maximum reply wait time to 5 seconds (i.e. 5000 ms).

  • The maximum time to wait for a response (TIMEOUT) is assigned to the libpcap context.

  • The BPF filter defined at line #121 limits the datagram captures to ICMP Echo Reply (as in ping.cpp) sent by the target host or ICMP Time Exceeded packets sent by any host.

  • The injection loop tries to reach the target host with increasing TTL values, until either the maximum number of hops is reached (in which case the target hasn't been reached) or the target responds as tested on line #203.

  • The datagram capture loop waits for a reply until it gets one or until the capture routine times out. If no packet is captured (i.e. packet == NULL), we make sure it's because the capture has timed out, not because pcap_next() has failed for some obscure reason, as it sometimes happens!

  • At line #186, the captured datagram is mapped into an ICMPPacket instance to check whether it's an Echo Reply or a Time Exceeded packet. The ICMP information is displayed at line #199.

  • And finally, line #213 displays three asterisks (* * *) to indicate the ICMP Echo Request has not been replied to, neither with an ICMP Echo Reply nor an ICMP Time Exceeded.

Here is the program used to trace route www.google.com:

%root> g++ -o traceroute *.cpp -lnet -lpcap
%root> ./traceroute www.google.com
TRACEROUTE to www.google.com (74.125.226.145), 30 hops max
1: 10.98.1.254 (10.98.1.254)  54 ms
2: 192.168.7.49 (192.168.7.49)  13 ms
3: 173-195-54.5.tel-ott.com (173.195.54.5)  10 ms
4: * * *
5: * * *
6: 69.63.250.97 (69.63.250.97)  37 ms
7: 72.14.222.87 (72.14.222.87)  18 ms
8: 209.85.255.232 (209.85.255.232)  19 ms
9: 209.85.250.7 (209.85.250.7)  24 ms
10: yyz08s14-in-f17.1e100.net (74.125.226.145)  47 ms
 >>> target reached
%root> 

Note that some intermediate routers have no domain names (e.g. TTL values 2, 6, 7, 8 and 9), while some others do not return ICMP Time Exceeded (as denoted by the asterisks at TTL values 4 and 5). The target host is reached by the time TTL gets up to 10.

As we mentioned earlier, many routers and firewalls are configured not to inform source hosts when dropping datagrams because of TTL values. Consequently, when running traceroute.cpp you may end up with a lot of asterisks instead of intermediate IP addresses. Even your gateway firewall may block all relevant incoming ICMP traffic, in which case traceroute.cpp won't be able to identify any intermediate router! Many traceroute implementations use UDP or TCP segments instead of ICMP packets (but they usually offer a command line option to force the use of ICMP) and therefore do a better job at overcoming these obstacles and identifying intermediate hosts on path to a given destination.


Home  |  Previous  |  Next

 
Copyright © 2014 Marco Lavoie