基於特徵向量之快速病毒資料庫搜尋演算法及其實現

A Fast Malware Database Searching Algorithm and Implementation based on the Feature Vectors Method

邱嗣儒

指導教授 ： 李程輝

國立交通大學/電機學院/電信工程系所/碩士(2012年)

https://doi.org/10.6842/NCTU.2012.00801

摘要

隨著行動裝置與網路快速的成長，越來越多的使用者會使用行動裝置來上網或儲存重要資訊，卻也成為攻擊者所想要攻擊的目標，因此對於保護使用者個人隱私，如何有效地偵測惡意軟體是個很重要的問題。本論文引用Anthony團隊所開發的Androguard程式去建立應用程式的控制流字串。且引用Silvio Cesare 及 Yang Xiang所提出的特徵向量法將控制流字串轉成特徵向量來代表這個應用程式的特性。本論文之目的，為發展一套有效率的偵測方法，我們設計了一套快速病毒資料庫搜尋演算法。可以依據被偵測程式的特徵向量算出其曼哈頓距離，並判斷其落於我們預先制定的某個曼哈頓距離區間中，進而給予預先制定的二進位樹去搜尋，而不用對整個病毒資料庫去做搜尋，可減少搜尋時間，並且利用特徵向量的相似度去偵測已知病毒的變種。本論文使用兩種計算相似度的方法，一種是用來判斷是否為已知惡意軟體的變種，另一種是用來計算曼哈頓距離區間交界的值。

關鍵字

惡意軟體 ； 控制流字串 ； 特徵向量法 ； 病毒資料庫搜尋演算法 ； 曼哈頓距離 ； 二進位樹 ； 變種

並列摘要

With the rapid growth of mobile devices and Internet, more and more users will use mobile devices to access the Internet or store important information. However, these users become the attackers’ targets. Therefore, it is important to detect malwares effectively for protecting users’ privacies. In this thesis, we quote “Androguard” (developed by Anthony’s team) to build the application’s control flow strings. In addition, we quote the “feature vectors method” (proposed by Silvio Cesare and Yang Xiang) for transforming the control flow strings to feature vectors that can represent the characteristic of the application. In this thesis, we design a fast malware database searching algorithm for detecting malwares effectively. First, we can calculate the query’s Manhattan distance from its feature vector, and determine which section it locates at. Then we do not have to search the total malware database, but just search the specific tree for decreasing the searching time. In addition, we use the similarities of feature vectors to detect the malwares’ variants. We use two methods to calculate similarity between applications. One is used to determine the application is malware or not. Another is used to calculate the Manhattan distance sections’ boundaries.

並列關鍵字

malwares ； control flow strings ； feature vectors method ； malware database searching algorithm ； Manhattan distances ； binary trees ； variants

參考文獻

[1] S.Cesare and Y.Xiang “ Malware Variant Detection Using Similarity Search over Sets of Control Flow Graphs”, Trust, Security and Privacy in Computing and Communications (TrustCom), 2011 IEEE 10th International Conference.

[4] A.Shabtai et.al, “Google Android: A comprehensive Security Assessment”, 2010 IEEE.

[6] S. Cesare and Y. Xiang, "A Fast Flowgraph Based Classification System for Packed and Polymorphic Malware on the Endhost," in IEEE 24th International Conference on Advanced Information Networking and Application (AINA 2010), 2010.

[2] Androguard ,http://code.google.com/p/androguard/

[3] Peter N.Yianilos” Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces” , SODA '93 Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, Pages 311 – 321.