質素なtracerouteを作ってみた

ネットワークスペシャリストの勉強中にtraceroute(windowsの場合はtracert)の説明があり、このくらいなら作れるかなと思い作成してみました。
その際に苦労したこと（raw_socketの扱い方）とその情報が少なく感じたためメモとして残します

動作確認はubuntu16.04, x86_64で行っています

使い方と注意点

使い方は以下のとおりです

$ gcc traceroute.c -o traceroute
$ sudo ./traceroute <IP>

注意点ですが、プログラム内部でsock_rawを使っているため実行時にはルート権限を必要とします
また本来のtracerouteならホスト名でアクセスできますが、以下ソースの場合はIPの文字列のみ受け付けます

ソースコード

traceroute.c

#include <stdio.h>                                                                                                                                                                                                    
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <unistd.h>

#include <netinet/ip.h>
#include <netinet/ip_icmp.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <netdb.h>
#include <sys/epoll.h>
#include <sys/time.h>

struct packet {
  struct ip ip_hdr;
  struct icmphdr icmp_hdr;
};

#define FIRST_TTL (1)
#define TIMEOUT_MSEC (3000) // 3sec

unsigned short checksum(unsigned short *buf, int size)
{
  unsigned long sum = 0;
  while(size > 1){
    sum += *buf;
    buf++;
    size -= 2;
  }

  if(size){
    sum += *(u_int8_t *) buf;
  }

  sum = (sum & 0xffff) + (sum >> 16);
  sum = (sum & 0xffff) + (sum >> 16);

  return ~sum;
}

void perror_exit(const char * const msg)
{
    perror(msg);
    exit(EXIT_FAILURE);
}

int main(int argc, char const* argv[])
{
  if (argc != 2) {
    printf("usage : %s IPADDR\n", argv[0]);
    return EXIT_FAILURE;
  }

  // sockaddr
  struct sockaddr_in to;
  memset(&to, 0, sizeof(to));

  // dest addr
  to.sin_family = AF_INET;
  to.sin_addr.s_addr = inet_addr(argv[1]);

  // create send socket
  int send_sock; // send (ICMP) socket
  if((send_sock = socket(AF_INET, SOCK_RAW, IPPROTO_RAW)) < 0){
    perror_exit("raw socket");
  }

  // create recv socket
  struct protoent *proto;
  if((proto = getprotobyname("icmp")) == NULL){
    perror_exit("icmp unknown");
  }
  int recv_sock; // recv (ICMP) socket
  if((recv_sock = socket(AF_INET, SOCK_RAW, proto->p_proto)) < 0){
    perror_exit("raw socket");
  }

  // icmp_id
  u_int16_t ident = htons(getpid() & 0xFFFF);

  for(int ttl = FIRST_TTL; ttl < 30; ttl++){
    // packet
    struct packet packet_buf;
    memset(&packet_buf, 0, sizeof(packet_buf));

    // set ip header
    struct ip *ip_hdr = &packet_buf.ip_hdr;
    ip_hdr->ip_hl = 5;
    ip_hdr->ip_v = 4;
    ip_hdr->ip_tos = 0;
    ip_hdr->ip_off = IP_DF && !IP_OFFMASK;
    ip_hdr->ip_ttl = ttl;
    ip_hdr->ip_p = proto->p_proto;
    ip_hdr->ip_sum = 0;                                                                                                                                                                                               
    memcpy(&ip_hdr->ip_dst, &to.sin_addr, sizeof(to.sin_addr));

    // set icmp header
    struct icmphdr *icmp_hdr = &packet_buf.icmp_hdr;
    icmp_hdr->type = ICMP_ECHO;
    ident = (ident + 1) & 0xffff;
    icmp_hdr->un.echo.id = ident;
    icmp_hdr->checksum = checksum((unsigned short *)icmp_hdr, sizeof(*icmp_hdr));

    // send
    size_t data_len = sizeof(packet_buf);
    sendto(send_sock, (char *)&packet_buf, data_len, 0, (struct sockaddr*)&to,
        sizeof(struct sockaddr));

    // timeout related process
    int epfd;
    struct epoll_event ev;

    epfd = epoll_create1(0); //NOTE: ptiential problem point
    if(epfd == -1){
      perror_exit("epoll_create");
    }

    ev.data.fd = recv_sock;
    ev.events = EPOLLIN;
    if(epoll_ctl(epfd, EPOLL_CTL_ADD, recv_sock, &ev) == -1){
      perror_exit("epoll_ctl");
    }

    // recv repeatedly til timeout
    int timeout = TIMEOUT_MSEC;
    struct epoll_event evlist[1];
    int ready = 0;
    struct timeval tv_start, tv_end, tv_gap;

    do{
      gettimeofday(&tv_start, NULL);
      ready = epoll_wait(epfd, evlist, 1, timeout);

      // in some error case
      if(ready == -1){
        perror_exit("epoll_wait");
      }

      // in case of timeout
      if(ready == 0){
        printf("*\n");
        break;
      }                                                                                                                                                                                                               
      gettimeofday(&tv_end, NULL);
      timersub(&tv_end, &tv_start, &tv_gap);
      timeout -= tv_gap.tv_sec + (tv_gap.tv_usec / 1000); // next timeout

      /* following is other case */
      for(int i = 0; i < ready; i++){
        if(evlist[i].data.fd == recv_sock){
          // recv
          char recv_buf[512];
          int recv_count = recvfrom(recv_sock, (void*)recv_buf, sizeof(recv_buf), 0, (struct sockaddr *)NULL, 0);

          // cast byte sequence to ip and icmp header
          struct ip *recv_ip_hdr = (struct ip*)recv_buf;
          struct in_addr ip_src = recv_ip_hdr->ip_src;
          struct icmphdr *recv_icmp_hdr = (struct icmphdr*)(recv_buf + recv_ip_hdr->ip_hl * 4);
          u_int8_t icmp_type = recv_icmp_hdr->type;

          switch (icmp_type) {
            case ICMP_ECHOREPLY:
              {
                u_int16_t recv_id = recv_icmp_hdr->un.echo.id;
                if(recv_id == ident){
                  printf("%s\n", inet_ntoa(ip_src));
                  goto LABEL_2;
                }
              }
              goto LABEL_1;
              break;
            case ICMP_TIME_EXCEEDED:
              printf("%s\n", inet_ntoa(ip_src));
              goto LABEL_1;
              break;
            default:
              break;
          }
        }
      }
    }while(1); // timeout loop

LABEL_1:
  ;
  } // ascend ttl loop
LABEL_2:                                                                                                                                                                                                              

  return 0;
}

上記ソースの大まかな処理は以下のとおりです

24〜41行

ヘッダのチェックサムを算出する関数です
このページ( http://www.fenix.ne.jp/~thomas/memo/ip/checksum.html )のをそのまま使いました

56〜62行

宛先アドレスの情報をコマンドライン引数から生成します

64〜68行

送信用ソケットを生成します
この際、自作のIPパケットを送信するために、第二引数にSOCK_RAW、第三引数にIPPROTO_RAWを与えます
参考 https://linuxjm.osdn.jp/html/LDP_man-pages/man7/raw.7.html

70〜78行

受信用ソケットを生成します
送信用と異なり、受信用のソケットはicmpパケットのみを受け取りたいためgetprotobynameを利用します。
参考 https://linuxjm.osdn.jp/html/LDP_man-pages/man3/getprotoent.3.html

80〜81行

ICMPヘッダに追加するidを作成します
受信時にこの作成したプロセスが送信したメッセージに対する返信かどうかを確認するために使います

83〜188行

ttlを1ずつ増加することで、経由するルータ数を増加させます

85〜104行

IPのヘッダおよびICMPのヘッダを作成します
IPのヘッダにttlを設定します

106〜109行

作成したパケットを相手へ送信します

111〜134行

セキュリティの観点でICMPの問い合わせを拒否するルータも存在します
途中にそのようなルータがあった場合はそのルータから返信が帰ってきません
メッセージを待ち続けて止まることを防ぐためにタイムアウトを設定します
今回はepollを使いましたがselectやpollでも多分できます
他の手法もあるかもしれません

141〜145行

タイムアウト発生時です
この場合は*(アスタリスク)を印字して次のメッセージを送信します

133行および147〜149行

なにかメッセージを受け取った場合には、どのくらいの間待っていたのかを計測します

152〜183行

epoll_waitの返り値分繰り返します
・・・が、今回の場合はsocket一つしか監視していないので152行めのループ及び153行目の比較は本来なら不要だと思います

154〜162行

ソケットからメッセージを受け取ります
受け取ったバイト列をipヘッダ及びicmpヘッダとして認識できる形にキャストします
最後にicmpのメッセージタイプを取得します

164〜181行

受け取ったicmpタイプによって処理を分岐します

受け取ったメッセージがecho replyの場合にはicmpヘッダのidを自身が送信したidと比較します
例えば本プロセス実行時にpingを実行していた場合にもここに到達してしまうので、正しく本プロセスへの返信であることを確かめる必要があります
本プロセスへの返信であれば、ipヘッダの送信元ipを表示して終了します

※本プロセスへの返信メッセージかどうかの判定をicmpヘッダのidで行っているのですが、1/65536 (2^-16)の確率では誤って認識してしまうはずです。本家の方はどうやっているのでしょう・・・

受け取ったメッセージがtime exceededの場合には、その送信元のipを表示します
そしてttlをインクリメントし再度メッセージ送信を行います

以上がtracerouteの概要です
間違いやバグがあればお手数ですがご指摘お願いいたします