2007/1/13

Spamassassin plugin --> FuzzyOCR 偵測圖像式垃圾郵件

垃圾郵件無所不在,由早期文字形態的信件,進化到圖文並貌的HTML格式。而由於anti-spam技術的進步,幾乎可達到九成的攔阻率。但「道高一尺、魔高一丈」,spammer開始大量運用圖片形態的方式來寄送郵件。圖像式垃圾郵件在圖片內容加入大量的雜訊資料(noisy data),藉以迴避掃描引擎的偵測。

以目前anti-spam市場所推出的產品,若是缺少掃描圖像式垃圾郵件的功能,相信也無法在市場上生存,例如:IronPort、Sophos PureMessage等廠商皆推出具備相,關功能的產品。

中正大學 吳昇教授的研究團隊推出了「無痛式垃圾郵件過濾系統: Nopam」,其設計理念是「垃圾郵件與正常郵件最大的分野在於行為而非內容。」。等於是利用行為模式進行垃圾郵件的偵測,不知是否能有效判別圖像式垃圾郵件呢?

當然,開放源碼的SpamAssassin也不能在此一功能上缺席,也出現了不少相對應的solution,例如:OcrPlugin。

而此篇文章所要介紹的 FuzzyOCR,是一套修改自OcrPlugin的Spamassassin plugin。同樣是利用光學字元辨認(OCR)的方式,來識別圖像式郵件所包含的「文字訊息」,並利用Fuzzy word matching演算法判斷辨識出來的文字。

主要具備了下列的功能:

  • Optical Character Recognition using different engines and settings
  • Fuzzy word matching algorithm applied to OCR results
  • Image hashing system to learn unique properties of known spam images
  • Dimension, size and integrity checking of images
  • Content-Type verification for the containing email
Matching and learning techniques
  1. 可彈性支援不同的OCR interface,並利用fuzzy word matching演算法來處理辨識的結果。
  2. 支援DB,可將處理過的圖片,以feature vectors的形態儲存在資料庫。因此相同或是類似的圖片,便可以利用儲存在DB的特徵向量來處理。
  3. 能檢測不同維度、size與整合性的測試。
  4. 郵件內容檢測。
Resource saving techniques

  1. 僅掃描郵件,而非辨認該封信件是否為垃圾信件。信件的分類仍交由spamassassin所判別的分數高低來決定。
  2. 對於已達到spam分數門檻的郵件,FuzzyOCR在處理該封郵件時會忽略該封信件而不進行掃描,進而減輕系統負載。(3.5版之後提供)
  3. 藉由比對儲存於DB的feature vectors(dimensions and file size)。若比對成功,則忽略該封信件,而不再進行OCR辨識與處理。
Safety measures
  1. 可設定掃描郵件timeout的時間,藉以避免Denial of Service的攻擊。
  2. 使用word sets取代simple lists,避免FuzzyOCR錯判的可能。


列出幾張FuzzyOCR網站的範例圖片供各位參考:

An animated gif is scanned for the first time
normal_result

The same gif is scanned a second time
known_hash

Various tricks of Image Spammers
broken

FuzzyOcr Debug output when running SpamAssassin with -D (or enabling debug mode in the config)
debug

BitTornado 封鎖所有 BitComet User Connection 的心得

最近在測試 P2P cache 的設備,其中使用了二套 bt client:BitComet與比特精靈(BitSpirit)。

由於之前都是使用BitComet,所以想測試一下其他套bt client software的效能如何!

但據同事測試的結果,上述二套bt client捉取檔案的速度,的確如「BitTornado Bans All BitComet Users」所提到的,BitComet比較快。

「BitTornado Bans All BitComet Users」一文提到,BitComet使用了欺騙系統的方法,來盜取用放寶貴的網路頻寬。並且還有利用super seeding的原理來增快BitComet user的下載速度。但相對的,卻使得其他非屬BitComet的User降低了下載的速度。

因此,Shad0w決定要ban掉所有使用BitComet Client連線到 BitTornado Client的connection。
同時也呼籲BitComet developer能拿到那些惡意的code。

P2P下載,本來就該遵循一套規則,互謀其利的分享方式。現在BitComet破壞規則,想利用一些小手段,讓使用BitComet的使用者能獲得較快的下載速度。但卻拖慢了其他BT Client的下載速度,這不僅是侵犯了non-BitComet的使用權益,更是破壞了BT下載的體制真是令人髮指。

但是在台灣,BitComet仍擁有一群為數不少的擁護者。筆者僅能建議各位能選擇一個適合自己的BT Client。

2007/1/8

搬家公告:由Xuite搬家到BlogSpot

測試BlogSpot一段時間了,由之前的beta版本,一直到正式版推出。

BlogSpot提供使用者較大的客製化空間,也內建了許多基本的功能,其中筆者認為最有用的便是HTML/JavaScript的模塊。

之前使用的 BSP(Blog Service Provider) 是 Xuite ,該平台所提供的功能還算完整,但由於 Xuite 日誌沒有提供 blog 文章備份的機制。等於是間接綁架使用者所發佈的文章。

加上,前陣子也發生幾件 BSP 的大事,像是「Yam、樂多、天空部落」、「有名大站」,造成了許多 blogger 出走的事件。在在都顯示了,一個穩定的blog分享平台的重要性。

因此將 BSP 轉移到 Google 的 BlogSpot。

而 BlogSpot平台,有搜尋引擎龍頭--> Google 的加持,相信能提供十分穩定的服務。

期間也servey了 Wordpress 的免費空間,但由於提供客製化的程度不高,因此測試了 BlogSpot 一段時間,就決定將新家設在 BlogSpot。

最重要的是再也不用擔心無法備份blog資料的問題了。

也趁著此次Blog搬家的機會,把之前貼在 Xuite 上,一些對我比較有意義的文章給轉貼到BlogSpot。

這些文章主要是筆者就讀研究所時,所做的相關研究的一些心得。像是 LIBSVM、Intrusion Detection、model selection、parameter selection…等。伴隨筆者渡過許多既充實又痛苦的日子。

libsvm-easy.py, grid.py and parameter selection雜談

上一篇大概介紹了LibSVM這套軟體,在這一篇裡,我將介紹一下LibSVM底下附的幾隻好用的tool:easy.py、grid.py!

[easy.py]
林智仁老師為了能讓使用者能更方便的使用libsvm,因此開發了easy.py這隻程式,使用者只要將dataset格式處理成libsvm看得懂的格式,再執行easy.py,便能自動替使用者執行svmscale、grid.py( do cross-validation to find the best parameter)、svmtrain、svmpredict,最後會產生預測的結果。

至於.py的程式要如何執行,那就必須先安裝Python這套好用的程式語言。這是一套非常強大的工具,屬於Open Source的軟體。能夠撰寫OO的程式,也能撰寫scripts。最重要的是只要有安裝python就可以執行了,目前在Unix-like、 win32、Mac OS上面都有,跨平台的能力十分強大,尤其在linux上面,更是屬於內建的一套軟體,真是棒啊!

想想…小弟的研究dataset由於資料量非常大,因此利用文書處理軟體來進行處理的話,常常會發生遺失資料的情況,小弟猜想是不是在windows平台上的文字檔有檔案大小及行數的限制。所以小弟在處理資料的時候,也常常利用linux來進行處理。就連把資料餵進資料庫來做處理,SQL Server 2000遇到幾十、幾百萬的資料筆數,也是受不了…So...小弟就回歸最原始的方式來進行處理:寫幾隻小程式就解決了!

小弟是覺得easy.py是比較適合初學者來使用,因為可以下的參數不多,再加上程式自動化程度高,因此小弟未曾使用過這隻程式!倒是接下來要介紹的grid.py這隻程式,小弟還比較感興趣呢!

[grid.py]
由於Support Vector Machine predict的正確率的高低,有很大一部份取決於參數的選擇。parameter selection也是一項很值得研究的議題!

所以我們直接使用林智仁老師提供的工具來選擇最佳的參數。其實在實驗的過程中,可以發現參數的選取其實是很不容易的一件事…有時候利用grid.py找出的best parameter並不見得會比自己亂try的結果來的好!

我們來探討一下grid.py這隻程式好了(雖然我也沒看得很熟),主要是利用2個參數:cost、gamma,來對於使用C-SVC(RBF kernel function)尋找最佳參數!

參數V:指定cross validation的方式,預設是5。這代表什麼意思呢?代表著程式會將train dataset分成5個部份,然後利用4個部份的資料當做新的training data、1個部份當做testing data…依此類推來找尋參數

參數log2C:Cost的值,看給定的是多少?

參數log2G:Gamma的值,同樣也是看使用者要給多少值

========================================================================

程式呢?就是利用log2C、log2G的組合值來找參數,說了這麼多似乎都是廢話…不過值得注意的一點就是…事先分析自己要研究的資料特性,然後來給予參數的範圍…如果範圍給太大的話,浪費時間;如果範圍給的不好的話,不見得找得出最好的參數!因此在svm裡頭找參數真的是一件非常困難的一件事,似乎至今仍未有一個合理且通用的參數找尋方法!

========================================================================

ps.可能是libsvm的效率問題,我的實驗利用grid.py(by default parameter),跑了一個月…仍未有結果,試想…如果是加大參數的範圍或是利用10-fold的方式,是不是更浪費時間呢?

anyway....參數的確是一件很重要的問題,試問如果有人問你:參數怎麼來的,有理論依據嗎?我想這就會考倒很多人…

為瞭解決grid.py的計算問題,目前有實驗室的功能clustering…不過僅限於unix-like平台上面可以執行,藉由同時發送多個計算任務到不同的電腦系統,得出結果的時間也縮短的多!

矣,寫到不知道在說什麼了…我想還是等網友們發問吧!看大家想知道什麼…不過目前我的主力研究領域是feature selection…為的是解決計算時間、資料量、複雜度的問題!

不過…還是希望今年能畢業!

關於libsvm--回覆網友kenny

您好..謝謝您這麼快回應我這問題..:),我的研究是關於網路的,所以我必須收集網路封包在將它分類...研究過相關paper,最近幾年似乎SVM很紅,分類的效果也很好,所以就想利用它來分類。

如果想收集網路封包來做研究的話,這部份的data preprocessing loading會很重哦!而且也很花時間…因為光是要萃取特徵值出來,並且轉換成svm可以吃的格式,應該會花上你許多的時間!

anyway...你可以建立一個模擬的環境,利用sniffer or tcpdump…等等的工具來capture網路封包!然後再做feature extract的動作…

的確,據我研究的結果,svm拿來作分類的效果真的不錯,有許多文獻也支持此一說法!不過還是要看研究領域及資料的特性囉!

不過您可能誤會我意思了,我意思不是要將libsvm寫成php,因為我網頁是用php寫的,所以我想利用網頁來訓練data,但是不知道要怎麼呼叫 libsvm程式執行?...不過我想應該是不可能吧..哈...或許用java的applet還有一點可能...但是我看原始碼並沒有 svm_scale.java檔...真是麻煩...因為我的資料要scale過才能train(不知道您的會不會有這問題?)

小弟認為…svmscale這隻程式其實不難,主要是先找出每個特徵值的最大、最小值,然後再針對欄位的資料進行標準差…把特徵值的範圍scale到+1~-1之間!做scale有什麼好處呢?

1.計算較容易

2.增加預測正確率

如果你是要訓練網頁的話,那肯定是需要繁雜的資料前置處理了…如果我猜得沒錯的話,svmscale這支程式應該不會是難倒你的問題…反而是前置處理才最麻煩,因為這個步驟包含了特徵值萃取,如果你特徵值萃取得當的話,我想後續的實驗結果應該都會很不錯哦!

any...svmscale這隻程式原理不難,大概才300多行而已!主要處理的動作也很少…你可以去看一下程式!然後試著改寫囉!

我覺得最麻煩的是參數的選擇,因為要一直try...=.=||,之前將一組資料train再用其他資料test,train那組的參數來test反而很低,就感覺每組資料都需要自己的參數....哀...怎麼會這樣呢?

參數的選擇本來就需要不斷的try and error囉!依你的敘述的話,我想你應該有發生overfitting and underfitting之類的問題!你可以survey一下這部份的文獻…看能不能試著解決這個問題(前者應該比較容易發生吧,我猜)

good luck...

ps.我之前有規畫寫一些關於overfitting and underfitting的文章,因為我打算寫的完整有理論一點,所以可能會稍微慢一點吧!哈…

LIBSVM model selection tool--grid.py 心得參考

看過許多關於SVM尋找最佳參數的方法,很多都是用「猜」的…沒錯就是用猜的!

不過要猜參數也要有個系統化的方法的找最佳參數,LIBSVM所提供的model selection tool-- grid.py這個工具大家可以參考使用!

為什麼說參考使用呢?因為在我們實驗室裡頭…用這個tool所找出來的參數,往往都不是最好的,哭…還跑了那麼久!

不過既然是LIBSVM所附的工具,相信有他的價值,只是就目前結果而言,我只會把這個工具當成一種尋找最佳參數的「參考」而已!

大概前二個月吧…使用LIBSVM的grid.py來找參數…使用預設的設定值

近50萬筆資料…以5-fold的設定來執行,CPU是p4-2.8,RAM 512mb!終於在這個星期跑完了!我相信我的設定是沒錯的…dataset也經過scale的步驟

跑了這麼長的一段時間,說真的,我只是想知道這個工作能幫我到哪個程度!雖然讓我失望了(還花了二個月),不過呢?我想應該可以給大家參考吧!

針對大量dataset的,之前在kernel-machine看到…有一套heroSVM!看過這套svm tool的paper,覺得速度真的很快…只可惜,目前不提供…接下來要收費才能使用那套軟體…而且似乎也沒有用在非商業環境底下可以免費使用的條款…失望了!

或許接下來我會交叉測試一下SVMlight and LIBSVM or others...看何者的效能表現好!到時候再跟各位分享囉!

ps...累啊,只因為LIBSVM用的熟…所以懶得換其他的來試…呵!

Intrusion Detection in SVM's Research...

利用support vector machine來做classification and regression,已經有許多的實證研究,證明在某些領域的應用上,效果比decision tree、Neural Network、來得好!

因此我們利用由台大資工 林智仁老師所發展的LibSVM這套工具來進行研究,林智仁老師首頁:http://www.csie.ntu.edu.tw/~cjlin。此套軟體主要包含了svmtrain、svmpredict、svmscale這幾隻程式,當然還有easy.py、grid.py...等等的好用工具!

LibSVM工具簡單說明:

假設我們有train及test dataset,首先我們會先使用svmscale這隻程式,把feature給scaling到+1及-1二值之間。下列是林智仁老師在Kernel-Machine中所提到的重點。

Scaling is related to two issues:
1. whether learning results can be better
2. whether numerical difficulties in training svm are avoided

It's more difficult to see the effect of 1, so essential we are asking which of your two methods better handle the numerical problems..

If we think that larger attributes usually cause more numerical problems, the 2nd approach may be better.
For the 1st one, you may scale one set to [-1,1], and then
have another set to be [-1000,1000]..
Using the second if you decide everything should be in
[-10, 10], then one set becomes in [-0.01, 0.01] and another
in [-10,10].

待scaling完之後,便使用svmtrain來進行分類model的建立,在這個過程之中,必須指定最佳的參數給svmtrain (parameter selection的部份下篇文章再跟大家分享囉!),參數的選擇是很重要的,儘可能給予svmtrain一個best parameter,或許能得到一個比較好的結果。

最後再利用svmpredict.exe這隻程式來進行預測,進而得出預測的正確率…眾多學者、專長都喜歡看到很高的預測率。

當然囉…我也是希望論文所做出來的數據是很漂亮的…不然的話,都不知道怎麼才能順利畢業哦!

ps.接下來會有數篇相關的內容簡介,也許小弟不了解SVM這東西的精髓,所以有說錯的…希望各位大大能給予小弟一些建議或是更正。