ミニマムtracerouteをRubyで実装

パケットが宛先に移動するときに実際に経由するルートを検出するのに使う traceroute(Windows では tracert) というコマンドがある。
traceroute コマンドを使うと、下の出力結果のように、ホストまでのルート(hop)が出力される。

$ traceroute google.com
traceroute to google.com (74.125.235.130), 30 hops max, 60 byte packets
1 192.168.11.1 (192.168.11.1) 0.513 ms 0.501 ms 0.490 ms
2 210.151.255.142 (210.151.255.142) 4.952 ms 6.094 ms 6.660 ms
3 202.225.194.107 (202.225.194.107) 4.913 ms 4.903 ms 5.343 ms
4 133.205.60.86 (133.205.60.86) 5.997 ms 5.991 ms 6.242 ms
5 122.135.0.42 (122.135.0.42) 6.251 ms 122.135.0.22 (122.135.0.22) 6.871 ms 6.868 ms
6 111.168.0.10 (111.168.0.10) 7.150 ms 111.168.0.14 (111.168.0.14) 5.816 ms 5.802 ms
7 122.130.0.117 (122.130.0.117) 5.012 ms 122.130.0.185 (122.130.0.185) 5.056 ms 122.130.0.53 (122.130.0.53) 5.839 ms
8 122.130.0.165 (122.130.0.165) 6.271 ms 122.130.0.225 (122.130.0.225) 6.240 ms 122.130.0.221 (122.130.0.221) 6.203 ms
9 122.134.0.73 (122.134.0.73) 6.791 ms 122.134.0.13 (122.134.0.13) 6.795 ms 122.134.0.73 (122.134.0.73) 6.772 ms
10 210.147.255.146 (210.147.255.146) 6.743 ms 6.718 ms 6.978 ms
11 72.14.239.48 (72.14.239.48) 6.947 ms 6.951 ms 5.540 ms
12 209.85.241.129 (209.85.241.129) 5.522 ms 8.089 ms 5.644 ms
13 nrt19s11-in-f2.1e100.net (74.125.235.130) 5.215 ms 5.208 ms 6.062 ms

ふと、どうやって実現されているのか検索してみると、ksplice の技術者がプログラマー向けのチュートリアルを書いていたので、別言語(慣れない ruby)に移植して理解を深めてみる。(このプログラムも参考にさせてもらった)

Learning by doing: Writing your own traceroute in 8 easy steps
https://blogs.oracle.com/ksplice/entry/learning_by_doing_writing_your

The secret behind traceroute
 IP ヘッダーには TTL(time to live. IPv6 では hop limit に名称変更された) というフィールドが存在し、ルーターを経由するたびに1ずつ減らされ、目的地に辿り着く前に0になると、送信元に最終到達ルーターの IP とともに ICMP “Time Exceeded” パケットを送信する。

この仕組を利用し、 TTL を低い値( 初期値1 とか)にして unlikely ポートを UDP で叩き(probe)ながら目的地までルーターをホップする。TTL が 0 になり 11: “ICMP Time Exceeded” がかえってくるたびに初期値の TTL を増やし ICMP “Destination Unreachable” が戻ってくるか hop max を超えるまでこの操作を続けることで traceroute を実現できる。

Step 1: Build an infinite loop

まずは、ベースになる無限ループを用意

#!/usr/bin/ruby

require 'timeout'
require 'socket'
include Socket::Constants

def main(dest)
 while true
 # ... open connections ...
 # ... print data ...
 # ... break if useful ...
 end
end

if __FILE__ == $0
 main 'google.com'
end

Step 2: Create sockets for the connections.

データグラム送信用の UDP ソケットと受信用の ICMP ソケットを作成

#!/usr/bin/ruby

require 'timeout'
require 'socket'
include Socket::Constants

def main(dest)
 while true
 send_socket = UDPSocket.new
 recv_socket = Socket.new(Socket::AF_INET, Socket::SOCK_RAW, Socket::IPPROTO_ICMP)

 # ... print data ...
 # ... break if useful ...
 end
end

if __FILE__ == $0
 main 'google.com'
end

Step 3: Set the TTL field on the packets.

送信用 IP ヘッダーに TTL を設定。

#!/usr/bin/ruby

require 'timeout'
require 'socket'
include Socket::Constants

def main(dest)
 ttl = 1
 max_ttl = 30

while true
 send_socket = UDPSocket.new
 send_socket.setsockopt(Socket::SOL_IP, Socket::IP_TTL, [ttl].pack('i'))

 recv_socket = Socket.new(Socket::AF_INET, Socket::SOCK_RAW, Socket::IPPROTO_ICMP)
 # ... print data ...
 # ... break if useful ...
 ttl += 1
 end
end

if __FILE__ == $0
 main 'google.com'
end

Step 4: Bind the sockets and send some packets.

パケットを送受信する。ポートは 33434 を利用。
空文字を送信。
TTL を増やすたびに送信時のポートも増やすのがお作法のようなので、元記事にはない、ポート番号を増やす実装を入れている。

#!/usr/bin/ruby

require 'timeout'
require 'socket'
include Socket::Constants

def main(dest)
 port = 33434
 ttl = 1
 max_ttl = 30

 while true
  send_socket = UDPSocket.new
  send_socket.setsockopt(Socket::SOL_IP, Socket::IP_TTL, [ttl].pack('i'))

  recv_socket = Socket.new(Socket::AF_INET, Socket::SOCK_RAW, Socket::IPPROTO_ICMP)
  icmp_sockaddr = Socket.pack_sockaddr_in(port, '')
  recv_socket.bind(icmp_sockaddr)

  send_socket.send("", 0, dest, port)
  # ... print data ...
  # ... break if useful ...

  ttl += 1
  port += 1
 end
end

if __FILE__ == $0
 main 'google.com'
end

Step 5: Get the intermediate hosts’ IP addresses.
データを受信。
パケットフィルタやタイムアウトその他で失敗する可能性が高いため、例外処理を入れている。

#!/usr/bin/ruby

require 'timeout'
require 'socket'
include Socket::Constants

def main(dest)
 port = 33434
 ttl = 1
 max_ttl = 30

 while true
  send_socket = UDPSocket.new
  send_socket.setsockopt(Socket::SOL_IP, Socket::IP_TTL, [ttl].pack('i'))

  recv_socket = Socket.new(Socket::AF_INET, Socket::SOCK_RAW, Socket::IPPROTO_ICMP)
  icmp_sockaddr = Socket.pack_sockaddr_in(port, '')
  recv_socket.bind(icmp_sockaddr)

  curr_addr = nil

  send_socket.send("", 0, dest, port)
  begin
   data, sender = recv_socket.recvfrom(512)
   curr_addr = Socket.unpack_sockaddr_in(sender)[1].to_s
   # ... print data ...
   # ... break if useful ...
  rescue SocketError => err_msg
  end
 ttl += 1
 port += 1
 end
end

if __FILE__ == $0
 main 'google.com'
end

Step 6: Turn the IP addresses into hostnames and print the data.
Socket::getaddrinfo を使って逆引き

#!/usr/bin/ruby

require 'timeout'
require 'socket'
include Socket::Constants

def main(dest)
 port = 33434
 ttl = 1
 max_ttl = 30

 while true
  send_socket = UDPSocket.new
  send_socket.setsockopt(Socket::SOL_IP, Socket::IP_TTL, [ttl].pack('i'))

  recv_socket = Socket.new(Socket::AF_INET, Socket::SOCK_RAW, Socket::IPPROTO_ICMP)
  icmp_sockaddr = Socket.pack_sockaddr_in(port, '')
  recv_socket.bind(icmp_sockaddr)

  curr_addr = nil
  curr_name = nil

  send_socket.send("", 0, dest, port)
  begin
   data, sender = recv_socket.recvfrom(512)
   curr_addr = Socket.unpack_sockaddr_in(sender)[1].to_s
   curr_name = Socket.getaddrinfo(curr_addr, nil)[0][2]
   puts "#{ttl}\t#{curr_name}(#{curr_addr})"

   # ... break if useful ...
  rescue SocketError => err_msg
  end

  ttl += 1
  port += 1
 end
end

if __FILE__ == $0
 main 'google.com'
end

Step 7: End the loop.

レスポンスデータは先頭20バイトが IP ヘッダー。


その後ろに ICMP データが続いている。

ICMP 部分は1バイト目が Type(0:Echo Reply, 3:Destination Unreachable など)、2バイト目が Code(Subtype)、というようなデータ構成。
元記事では、dest のホストと逆引きしたホストが一致すれば終了するようになっているが、ここでは

  • Type : 3 : Destination Unreachable Message
  • Code : 3 : Port Unreachable

が渡ってくると終了するようにしている。

#!/usr/bin/ruby

require 'timeout'
require 'socket'
include Socket::Constants</pre>
def main(dest)
 port = 33434
 ttl = 1
 max_ttl = 30

 while ttl <= max_ttl
  send_socket = UDPSocket.new
  send_socket.setsockopt(Socket::SOL_IP, Socket::IP_TTL, [ttl].pack('i'))

  recv_socket = Socket.new(Socket::AF_INET, Socket::SOCK_RAW, Socket::IPPROTO_ICMP)
  icmp_sockaddr = Socket.pack_sockaddr_in(port, '')
  recv_socket.bind(icmp_sockaddr)

  curr_addr = nil
  curr_name = nil

  send_socket.send("", 0, dest, port)
  begin
   data, sender = recv_socket.recvfrom(512)
   curr_addr = Socket.unpack_sockaddr_in(sender)[1].to_s
   curr_name = Socket.getaddrinfo(curr_addr, nil)[0][2]
   puts "#{ttl}\t#{curr_name}(#{curr_addr})"

   icmp_type = data.unpack('@20C')[0]
   icmp_code = data.unpack('@21C')[0]

   exit 0 if (icmp_type == 3 and icmp_code == 3)
  rescue SocketError => err_msg
  end

  ttl += 1
  port += 1
 end
end

実行
最後に手製 traceroute を実行

$ sudo ruby traceroute.rb google.com
1 192.168.11.1 (192.168.11.1)
2 210.151.255.142 (210.151.255.142)
3 202.225.194.107 (202.225.194.107)
4 133.205.60.86 (133.205.60.86)
5 122.135.0.86 (122.135.0.86)
6 122.130.0.182 (122.130.0.182)
7 122.130.0.249 (122.130.0.249)
8 122.130.0.229 (122.130.0.229)
9 122.134.0.13 (122.134.0.13)
10 210.147.255.146 (210.147.255.146)
11 72.14.239.202 (72.14.239.202)
12 209.85.250.249 (209.85.250.249)
13 nrt19s01-in-f2.1e100.net (74.125.235.66)

Yay!

1e100.net というドメイン
google.com が nrt19s01-in-f2.1e100.net というホストになっている理由は google の次の FAQ を参照

What is 1e100.net?

1e100.net is a Google-owned domain name used to identify the servers in our network.

Following standard industry practice, we make sure each IP address has a corresponding hostname. In October 2009, we started using a single domain name to identify our servers across all Google products, rather than use different product domains such as youtube.com, blogger.com, and google.com. We did this for two reasons: first, to keep things simpler, and second, to proactively improve security by protecting against potential threats such as cross-site scripting attacks.

Most typical Internet users will never see 1e100.net, but we picked a Googley name for it just in case (1e100 is scientific notation for 1 googol).

8 bits = 1octet = 1 byte?
RFC 792 : Internet Control Message Protocol では 8 ビットは 1 オクテットに用語統一されており、バイトは一切使われていない。

“Foundations of Python Network Programming” の Ch. 5 “Network Data and Network Errors”によると、以下の理由かららしい

The reason that the Internet RFCs are so inveterate in their use of the term “octet” instead of “byte”is that the earliest of RFCs date from a very ancient era in which bytes could be one of several different lengths—byte sizes from as little as 5 to as many as 16 bits were used on various systems. So the term “octet,” meaning a “group of eight things,” is always used in the standards so that their meaning is unambiguous.

脱ミニマム

Linux に通常インストールされている traceroute だと、ホップごとのリクエスト数はデフォルト3だったり、 probe 方法を選べたり(Windows と同じ ICMP Echo や TCP SYNC など)、ipv6 に対応していたりと当然ながらより複雑な処理をしている。

References

Advertisements
Tagged with: , ,
Posted in web

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Archives
  • RT @__apf__: How to write a research paper: a guide for software engineers & practitioners. docs.google.com/presentation/d… /cc @inwyrd 4 months ago
  • RT @HayatoChiba: 昔、自然と対話しながら数学に打ち込んだら何かを悟れるのではと思いたち、専門書1つだけ持ってパワースポットで名高い奈良の山奥に1週間籠ったことがある。しかし泊まった民宿にドカベンが全巻揃っていたため、水島新司と対話しただけで1週間過ぎた。 それ… 5 months ago
  • RT @googlecloud: Ever wonder what underwater fiber optic internet cables look like? Look no further than this deep dive w/ @NatAndLo: https… 5 months ago
  • @ijin UTC+01:00 な時間帯で生活しています、、、 10 months ago
  • RT @mattcutts: Google's world-class Site Reliability Engineering team wrote a new book: amazon.com/Site-Reliabili… It's about managing produc… 1 year ago
%d bloggers like this: