sonickun.log

備忘録

py-radixを使ったIPアドレスの高速探索[Python]

 パケットを監視してて,この送信元IPってどこのホストなんだろうって思うこと,あるあるですよね.
 
 ある調べたいIPアドレスがあって,それをIPアドレスとホスト名が紐付けされているのリストの中から探索するスクリプトです.

py-radix

 py-radixは,pythonの外部モジュールで,ルーティングテーブルの検索(longest match)を行えます.このモジュールはIPv6IPv4の両方に対応しています.
 py-radix - radix tree data structure for Python
 
 py-radixの特徴は,Radix tree(基数木)というデータ構造を使って高速にIPアドレスの探索ができることです.
 Radix tree - Wikipedia, the free encyclopedia
 
 

Input Data

 まず,IPアドレスとホスト名が紐付けされたリストを用意する必要があります.今回は,以下のような世界の教育機関のIPアドレスのリストの一部を使います.詳しくは過去記事を参照.
 任意のIPv4アドレスRangeをPrefix表記に変換する[はじめてのRuby] - sonickun.log

iplist.txt
China Education and Research Network - Nanjing:1.51.0.0/16
Jinan University:1.184.0.0/17
China Education and Research Network - Guangzhou:1.184.0.0/15
Istituto Statale Secondario Superiore Pacifici de Magistris Priverno:2.119.234.168/29
s0-1.championsschoolofrea.bbnplanet.net:4.0.32.62/31
s0-1.championsschoolofrea.bbnplanet.net:4.0.32.64/26
s0-1.championsschoolofrea.bbnplanet.net:4.0.32.128/25
s0-1.championsschoolofrea.bbnplanet.net:4.0.33.0/30
s0-1.championsschoolofrea.bbnplanet.net:4.0.33.4/32
Education Management Corporation:4.2.144.0/27
Concordia University:4.2.160.32/27
American Education Centers:4.2.161.32/29
United Schools District:4.2.161.96/27
Education Management Corporation:4.2.170.0/27
American Education Centers, Inc:4.2.173.16/29
United Schools District:4.2.173.96/27
Sewickley Academy:4.2.174.0/23
City of Pittsfield Schools:4.2.176.192/27
Taft School:4.2.176.240/28
Taft School:4.2.179.128/26
Alice Lloyd College:4.2.224.160/28
Learning Tree:4.2.225.0/26
Kennedy Krieger Institute:4.17.69.128/27
New Bedford Public Schools:4.17.112.0/24


 次に,このリストから探索したいIPアドレスのリストを用意します.今回はiplist.txtに含まれていないIPも含めて,以下の様なサンプルデータにしました.

search.txt
4.2.160.40
1.2.3.4
4.2.173.16
4.2.176.245
8.8.8.8
1.184.0.3
192.168.0.1

 
 

Script

 Pythonで書きました.

import radix

rtree = radix.Radix()

f = open("iplist.txt","r")
g = open("search.txt","r")

org = []
print "Making Tree.."
for line in f:
	line = line.replace("\r\n","")
	cols = line.split(':')
	rtree.add(cols[1])
	org.append([cols[0],cols[1]])
print "Tree Completed.\n--------------------"

print "Now Matching.."
for line in g:
	line = line.replace("\r\n","")
	rnode = rtree.search_best(line)
	if(str(rnode) != "None"):
		for row in org:
			if(row[1] == rnode.prefix):
				print line + "\t:" + row[1] + "\t:" + row[0]
print "Finished."

f.close()
g.close()

 ご覧のとおり,Radix treeの中に組織名が紐付けされていないので,探索の結果がTrueならばfor文を使って配列から組織名を引っ張ってくるという,なんとも(速度的にもメモリ的にも)効率の悪いクソコードに仕上がっております.プロpythonistaに教えてもらいたいものです..
 
 

Result

Making Tree..
Tree Completed.
--------------------
Now Matching..
4.2.160.40      :4.2.160.32/27  :Concordia University
4.2.173.16      :4.2.173.16/29  :American Education Centers, Inc
4.2.176.245     :4.2.176.240/28 :Taft School
1.184.0.3       :1.184.0.0/17   :Jinan University
Finished.

 こんなかんじで,探索に成功したものは,IPアドレスIPアドレス(Prefix),組織名の順に表示するようにしました.