py-radixを使ったIPアドレスの高速探索[Python]
パケットを監視してて,この送信元IPってどこのホストなんだろうって思うこと,あるあるですよね.
ある調べたいIPアドレスがあって,それをIPアドレスとホスト名が紐付けされているのリストの中から探索するスクリプトです.
py-radix
py-radixは,pythonの外部モジュールで,ルーティングテーブルの検索(longest match)を行えます.このモジュールはIPv6とIPv4の両方に対応しています.
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.