Traceroute - Using RAW Socket & UDP

• Download demo - 13.2 KB
• Download source - 8 KB

Fig 1: Tracing route to Google

Fig 2: discovery.india.com doesn't exist. Probe stops at an intermediate host

Fig 3: Host after 12^th hop doesn't respond. Traceroute continues with the next hop.

Introduction

Traceroute is a utility to discover the hosts and/or traffic on the path to the destination. Along the path that the packet travels to the destination, it may pass through zero or more hosts. The path taken by the packet can be useful to determine the time taken for a typical communication with that host. The response from the host also gives an indication of the traffic between two hosts. It can also be found out if a host/router in the path is down (as shown in Fig. 2).

Two things led me to my first CodeProject article. First, I wanted to write a program that will use a RAW Socket. Second, having read many great CodeProject articles, I also desired to have my article posted. I hope that this would be useful for someone wanting to learn RAW Socket programming. I believe there are (and will be) other articles that explain Raw Sockets in a far better way. This is not a introduction to RAW Socket programming, but an application that makes use of a RAW Socket. Traceroute, as such, can be implemented without using RAW Sockets.

Mechanism

The PING utility determines if the destination host is up and running. For this PING sends an ICMP echo packet to the destination host. The destination host, on receiving an echo packet, sends an echo response to the source. Traceroute makes use of this PING functionality.

ICMP is carried as a payload by the IP packet. The TTL value of the IP Header determines the number of hops to the destination. Usually, the kernel sets the TTL value. A host, on receivng an IP packet, decrements the TTL value. If it's not the intended destination, the IP header is modified with the new TTL values and sent to the next host in the path to the destination.

When the host recevies a packet with a TTL value 1, not intended for it, the packet is dropped. An ICMP time-exceeded reponse is sent to the packet originator to inform about the dropped packet. The TTL field determines that a packet doesn't remain in the network for too long, all old packets are dropped, and network resources are available for fresh traffic.

Traceroute uses TTL and ICMP responses (to UDP/ICMP probes) to do its work. By gradually increasing the TTL value, all the hosts in between the source and destination are identified. Note that the path taken by the probes shown above are for that particular time and place when it was taken. It may vary depending upon the place, time, destination IP address, intermediate hosts, and the routing used whenever the probe is taken.

Implementation

Traceroute is a utility provided by the Operating System. Windows calls it tracert. Tracert uses ICMP echo requests. As such, any transport protocol of family AF_INET can be used. In this article, UDP packets are used to accomplish the task. The UDP packets sent by Traceroute are targeted at strange port numbers that nothing will be listening on (hopefully). The target host, therefore, ignores the packet after generating the Port Unreachable message. The UDP port number used by Traceroute in its first probe is incremented by one for each subsequent request. Change the port range if a program on the target host might be using ports in roughly the 33434-33534 ranges.

Traceroute sends packets until a packet reaches the final destination host. If it cannot reach the destination from an intermediate host, it terminates. Using UDP has its own pitfalls. Sometimes a host (not target host) will send a "Destination Unreachable" ICMP packet. This happens when an application is listening on the port on which we sent the UDP packet. In such intances, a fallback to the ICMP probe is helpful to continue the traceroute functionality.

Initiation

Traceroute uses a RAW IP Socket to send probes and read responses. The IP header as well as the UDP or ICMP packets are constructed by the application.

Using a RAW UDP or UDP Socket will not suffice as one would not be able to read the ICMP responses in such cases.

For providing our own IP header rather than letting the kernel do it, enable the IP_HDRINCL option.

// provide our own IP header and not let the kernel provide one
int on = 1; 
setsockopt(sock, IPPROTO_IP, IP_HDRINCL, (const char *)&on, sizeof(on));

Driver State Transitions

The Driver first tries with UDP packets. The following unwanted states can occur after sending a UDP packet.

• The socket doesn't get any response. After timeout, Traceroute tries sending ICMP echo requests for the same hop. After getting a response, trace begins for the next hop.
• The socket doesn't get any response. After timeout, Traceroute tries sending ICMP echo requests. If there is no response, then further MAX_CONQ_ICMP_TIMEOUT hops are checked for responses. If there is any response, Traceroute proceeds further.
• The socket doesn't get any response. After timeout, Traceroute tries sending ICMP echo requests. If there is no response, then further MAX_CONQ_ICMP_TIMEOUT hops are checked for responses. If no response, Traceroute terminates.
• The socket gets a response. The response turns out to be a "Destination Unreachable" ICMP packet. Try further packets with ICMP echo requests. Further, a valid response is received.
• The socket gets a response. The response turns out to be a "Destination Unreachable" ICMP packet. Try further packets with ICMP echo requests. If still getting a "Destination Unreachable" ICMP packet, then no use proceeding further.

A flag FALLBACK_TO_ICMP can be set or unset, thereby controlling ICMP generation.

while(dest_reached == 0)
  {
     settraceinfo(traceinfo, packetid + count, count+1, proto, 
                  dest.sin_addr.s_addr, src.sin_addr.s_addr, pack_size);

      if((pack_size = construct_proto_pack(data, traceinfo)) > 0)
      {
          RequestTime      = GetTickCount();
          written          = sendto(sock,data,pack_size,0,
                                   (struct sockaddr *)&dest,sizeof(dest));

          if (written == SOCKET_ERROR) 
          {
              printf("\n Sending packet failed. " 
                     "Check permissions on this system");
              printf("\n Admin rights are required on XP");
              return 1;
          }

          sockreadible     = IsSocketReadible(sock);

          if(sockreadible)
          {
              timed_out_cnt = 0;
              ResponseTime  = GetTickCount();
              latency       = ResponseTime - RequestTime;
              dest_reached  = processResponse(sock,dest.sin_addr.s_addr);

              // If destination is unreachable then switch to ICMP

              if((DESTINATION_UNREACHABLE && 
                     (proto != IPPROTO_ICMP) && FALLBACK_TO_ICMP)) {
                  proto                   = IPPROTO_ICMP;
                  DESTINATION_UNREACHABLE = 0;
              }
              else if (DESTINATION_UNREACHABLE){
                  printf("\n Destination unreachable, " 
                         "so cannot proceed further");
                  return 1;
              }

              count ++;
          }
          else if(written > 0 && proto == IPPROTO_ICMP)
          {
              //request timed out even with ICMP packets then 
              //stop after MAX_CONQ_ICMP_TIMEOUT hops
              timed_out_cnt ++;

              // If after consequtive MAX_CONQ_ICMP_TIMEOUT hops, 
              // request has timed out then stop

              if(timed_out_cnt >= MAX_CONQ_ICMP_TIMEOUT) {
                printf("\n Request has timed out even after %d hops, " 
                       "so not proceeding further\n",
                       MAX_CONQ_ICMP_TIMEOUT);
                return 1;
              }
              else {
               printf("\n Request timed out");
               count ++;
              }
          }
          else if(written > 0 && FALLBACK_TO_ICMP)
          {
              // Try again with ICMP if UDP has failed for the ttl

              if(proto != IPPROTO_UDP)
                  count ++;

              proto          = IPPROTO_ICMP; // Don't go with UDP hereafter
          }
          else if(FALLBACK_TO_ICMP == 0)
              count ++;
      }
  }

Packet Constructor

The IP Header is first constructed. The TTL values for the trace are updated in the TTL header field. The protocol header field is updated with the appropriate protocol number.

IPHeader *ip           = (IPHeader *)(pack_data);

ip->ip_version      = 4;
ip->ip_header_len   = 5;  // in words (size is always 20 bytes for IPv4)
ip->ip_tos          = 0x0;
ip->ip_total_length = htons(trace.size);
ip->ip_frag_offset  = 0x0;
ip->ip_protocol     = trace.proto;
ip->ip_destaddr     = trace.daddr;
ip->ip_srcaddr      = trace.saddr;
ip->ip_checksum     = 0;    // Don't worry, Kernel will do the needful
ip->ip_id           = htons(trace.packetid);
ip->ip_ttl          = trace.ttl;

Next, the Raw UDP/ICMP packets are constructed. Each transport protocol has its own header fields which are specified in their structure definitions. icmp_hdr and udp_hdr represent the structure of ICMP and UDP headers, respectively.

if(trace.proto == IPPROTO_UDP)
  {
      //struct udp_hdr *udp         = (struct udp_hdr *)(ip + 1);
      if(portincr > 100)       // 33434 to 33534
          portincr = 0;

      UDP_PACKET *udp_pack          = (UDP_PACKET *) (ip + 1);

      strcpy(udp_pack->messg, "Hello there!");

      udp_pack->udp.dest_port       = htons(UDP_DEST_PORTNO + portincr++);
      udp_pack->udp.source_port     = htons(0);
      udp_pack->udp.udp_checksum    = 0; 
      udp_pack->udp.udp_length      = htons(sizeof(*udp_pack));

      // UDP Packet length = UDP header len + data len

      int udp_hdr_n_data_len        = sizeof(*udp_pack);
      packet_length                 = ((int)(ip + 1)  - (int)ip) + 
                                        udp_hdr_n_data_len;

      ip->ip_total_length           = packet_length;
      udp_pack->udp.udp_checksum    = CalculatePseudoChecksum(
          (char *)udp_pack,udp_hdr_n_data_len,trace.daddr,trace.saddr);
  }
  else if(trace.proto == IPPROTO_ICMP)
  {
      //struct icmp_hdr *icmp       = (struct icmp_hdr *)(ip + 1);
      ICMP_PACKET     *icmp_pack    = (ICMP_PACKET *) (ip + 1);

      icmp_pack->icmp.code          = 0;
      icmp_pack->icmp.type          = 8;
      icmp_pack->icmp.checksum      = 0;
      icmp_pack->icmp.id            = ICMP_SEQNO;
      icmp_pack->icmp.seq           = ICMP_SEQNO++;
      icmp_pack->dwTime             = GetTickCount();
      strcpy(icmp_pack->cData, "Hello there!");

      // ICMP Packet length = ICMP header len + data len
      int icmp_hdr_n_data_len       = sizeof(*icmp_pack);
      packet_length                 = ((int)(ip + 1)  - (int)ip)     + 
                                        icmp_hdr_n_data_len;

      ip->ip_total_length           = packet_length;
      icmp_pack->icmp.checksum      = CalculateChecksum(
           (USHORT *)icmp_pack,icmp_hdr_n_data_len);
  }

Failover & Recovery

Most traceroute programs have a default maximum-hops value. As of now, this utility stops only after reaching the destination. But reaching the destination is not the only goal to use this tool. Sometimes, a host/router in between will not respond with an ICMP time-exceeded message, but the next host in the path will (as shown in Fig. 3). To check for such conditions and to limit them, MAX_CONQ_ICMP_TIMEOUT can be set appropriately.

Limitation

Like all other Traceroute's, this will not work behind a NAT or firewall.

This has been tested on Windows 2000. For XP, administrative login or access is required for sending packets using a RAW socket.

History

• Version 0.02 - source host name/IP address lookup is automated.
• Version 0.03 - send-to return value checked for error; changed program return value to 1 whenever an exception is encountered.

Comments and suggestions are welcome. Please do rate this article. Contact me at vinod_vijayanvin(at)hotmail.com.