用python擷取MSN訊息

為了做無線網路的期末專題，寫了個小程式來抓MSN的訊息..

別問我這跟無線網路有什麼關係.. 因為我也不知道

我是使用python+pcap來做，這邊就介紹一下是怎麼做的

測試環境：

Windows 7

Windows Live Message (MSN) version 2009 (Build 14.0.8117.416)

環境要求：

Python 2.6 

Pcap version 1.1 for win32-py2.6

WinPcap 4.1.2

Appserv 2.5.10

其中pcap是Python的WinPcap API，再找要用哪個lib的時候也是考慮了很久

這個lib看起來許久沒更新了，資料也是很久以前的

但這個似乎是最簡便的，資料也比較多，最後在時間壓力下還是用他了


以下是pcac一些參考的資料，不過其實都大同小異
用法並不困難
http://devbbs.doit.com.cn/thread-11317-1-1.html
http://www.iteye.com/topic/372874
http://python.6.n6.nabble.com/CPyUG-85013-pcap-dpkt-python-td2854242.html
http://blog.sina.com.cn/s/blog_4b5039210100gnlu.html

原理

MSN是用1863port，以TCP的方式傳送、接收資料。我們用wireshark找到這點後，用python監聽1863port，並用regex濾出我們想要的訊息(登入訊息及談話內容)。最後存入遠端網頁(測試時是本機)，模擬MSN被惡意軟體監聽的情況。

程式碼

A star algorithm

A*常用在找「地圖路線」或是「電玩內的NPC移動路徑」
原因是因為，跟許多演算法比起來，A*會從現有找到的路挑最好的出來(Best-First)，並且猜測接下來最好的路是哪一條(Greedy)

也就是說，A*是一種結合Best-First和Greedy的聰明演算法

評估方法如下: (節錄自: http://blog.minstrel.idv.tw/2004/12/star-algorithm.html)
f(n) = g(n) + h(n)

g(n): 從啟始點到目前節點的距離
h(n): 預測目前節點到結束點的距離(此為 A* 演算法的主要評價公式)
f(n): 目前結點的評價分數

其中, h(n) 主導著A* 演算法的表現方式. 有以下幾種情形:
1. h(n)=0: A* 演算法這時等同 Dijkstra演算法, 並且保證能找到最短路徑
2. h(n)<目前節點到結束點的距離: A* 演算法保證找到最短路徑, h(n)越小, 搜尋深度越深
3. h(n)=目前節點到結束點的距離: A* 演算法僅會尋找最佳路徑, 並且能快速找到結果
4. h(n)>目前節點到結束點的距離: 不保證能找到最短路徑, 但計算比較快
5. h(n)與g(n)高度相關: A* 演算法此時成為 BFS (Best-First Search)


A*的優點從以下圖可明顯看出 :

(圖片節錄自: http://blog.minstrel.idv.tw/2004/12/star-algorithm.html)

A*的搜尋範圍明顯的比Dijkstra小

但是也有一點缺點:

(圖片節錄自: http://ndltd.ncl.edu.tw/cgi-bin/gs32/gsweb.cgi/login?o=dnclcdr&s=id=%22097NCCU5394024%22.&searchmode=basic)

A*有可能沒辦法找到最好的路徑