Mô hình kết hợp giữa học máy và giải thuật di truyền trong phát hiện mã độc

JOURNAL OF SCIENCE OF HNUE DOI: 10.18173/2354-1075.2015-0066 Educational Sci., 2015, Vol. 60, No. 7A, pp. 189-195 This paper is available online at MÔ HÌNH KẾT HỢP GIỮA HỌCMÁY VÀ GIẢI THUẬT DI TRUYỀN TRONG PHÁT HIỆN MÃ ĐỘC Lương Thế Dũng Khoa An toàn Thông tin, Học viện Kỹ thuật Mật mã Tóm tắt. Bài báo đề xuất một phương pháp phân lớp mã độc hiệu quả dựa trên sự kết hợp giữa kĩ thuật phân lớp dữ liệu với giải thuật di truyền. Quá trình thực nghiệm và phân tích trên cùng một tập dữ liệu huấn luyện đã chỉ ra rằng phương pháp đã đề xuất cho kết quả phân lớp chính xác hơn phương pháp phân lớp khi chưa kết hợp với giải thuật di truyền. Từ khóa:Mã độc, phát hiện mã độc, học máy, giải thuật di truyền, cây quyết định. 1. Mở đầu Mã độc đang là một trong những hiểm họa lớn nhất đối với các hệ thống thông tin trong thời kì hiện nay. Cùng với sự phát triển mạnh mẽ và tinh vi của các loại mã độc, thì phát hiện mã độc đã trở thành một trong những vấn đề quan trọng nhất trong lĩnh vực An toàn thông tin. Các phương pháp phát hiện mã độc truyền thống thường sử dụng kĩ thuật đối sánh mẫu, việc phát hiện được dựa trên một cơ sở dữ liệu các mẫu về mã độc đã định nghĩa trước, vì vậy có độ chính xác cao cũng như ít đưa ra các cảnh bảo nhầm. Tuy nhiên, với sự bùng nổ mạnh mẽ của mã độc, các cơ sở dữ liệu mẫu mã độc ngày càng có kích thước lớn hơn, nên việc sử dụng phương pháp này có các hạn chế là làm giảm hiệu năng của hệ thống và không thể phát hiện được các mã độc mới chưa được định nghĩa trong cơ sở dữ liệu hoặc các mã độc đa hình, siêu đa hình. Để khắc phục các hạn chế trên, nhiều phương pháp phát hiện mã độc mới đã được đề xuất, đặc biệt là phương pháp dựa trên các mô hình học máy và khai phá dữ liệu như: Phương pháp dựa trên Mạng Bayes [10], Máy Vecto hỗ trợ [12] và Cây quyết định [13]. Tuy nhiên các phương pháp này gặp phải một số hạn chế nhất định trong việc phân loại chính xác mã độc khi các mã độc được lai ghép, hoặc có sử dụng các giải thuật thông minh, vấn đề này đã được nhiều tác giả đề cập như trong [1,15]. Ngoài ra sự biến đổi của các kĩ thuật thiết kế mã độc như làm rối mã, sử dụng mã hóa mã nguồn hay nén mã nguồn. . . làm cho các đặc tính của mã độc khó bị phát hiện trong mã nguồn. Do đó, các kĩ thuật khai phá dữ liệu thông thường không còn hiệu quả trong việc xác định loại mã độc nếu chỉ dựa trên tập đặc tính dấu hiệu đại diện duy nhất, dẫn đến việc phân tích và xử lí mã độc trở nên khó khăn hơn [1]. Bài báo này đưa ra một kĩ thuật phân loại mã độc mới, hiệu quả hơn Ngày nhận bài: 8/7/2015. Ngày nhận đăng: 15/11/2015. Liên hệ: Lương Thế Dũng, e-mail: ltdung@bcy.gov.vn. 189 Lương Thế Dũng dựa trên việc kết hợp giữa kĩ thuật phân lớp cây quyêt đinh và giải thuật di truyền, áp dụng trên bộ dữ liệu các cuộc gọi hàm API của chương trinh mã độc. Nội dung bài báo được trình bày gồm 5 phần: Phần2 - trình bày việc phân tích và trích rút dữ liệu các hàm API; Phần 3 - trình bày phương pháp kết hợp giưa kĩ thuật phân lớp và giải thuật di truyền trong việc phát hiện mã độc; Phần 4 - trình bày kết quả thử nghiệm và đánh giá phương pháp; Phần 5 - kết luận của bài báo. 2. Nội dung nghiên cứu 2.1. Phát hiện mã độc dựa trên mô hình học máy 2.1.1. Xây dựng tập dữ liệu học từ các cuộc gọi hàm API của mã độc Dù mã nguồn của chương trình độc hại có bị biến đổi và sử dụng kĩ thuật nào đi nữa thì một nguyên tắc chung là chúng đều phải thực thi các hành vi mục tiêu chẳng hạn như: Sao chép tệp, gửi gói tin,. . . Hầu hết các hành vi này đều được thực hiện thông qua các lời gọi hàm API, chính vì vậy, việc phân tích các lời gọi hàm API là một kĩ thuật quan trọng trong việc phát hiện và phân loại mã độc. Một số phương pháp phân tích các lời gọi API được đưa ra trong [6 - 8]. Bước 1: Giải nén các phần mềm độc hại Các phần mềm độc hại thường thực hiện việc che dấu bằng kĩ thuật đóng gói nhằm chống lại quá trình dịch ngược chương trình, dẫn đến rất khó bị phát hiện, vì vậy bước này sử dụng các công cụ và kinh nghiệm để thực hiện các giải nén toàn bộ phần mềm nhằm xác định chính xác các thông tin của các tệp thực thi. Bước 2: Trích rút các cuộc gọi hàm API Bước này sử dụng một công cụ dịch ngược phần mềm tự động nhận dạng ra các lời gọi API cho các trình biên dịch khác nhau. Công cụ này sau đó thực hiện trích xuất các thông tin từ dạng nhị phân. Mỗi một phần sẽ bao gồm các thông tin khác nhau về nội dung nhị phân như tất cả các hàm API, chiều dài, các mã lệnh (OP), địa chỉ của chúng và các địa chỉ khối. Danh sách các API được tham khảo từ Microsoft - (MSDN) được sử dụng xác định các hàm API windows. Để liệt kê tất cả các cuộc gọi API có liên quan đến mã độc hại, việc thu thập được thực hiện bằng cách sử dụng các opcodes của các mã lệnh Jump và lệnh Call như là một kiểu hàm. Bước 3. Lựa chọn thuộc tính Bài báo này sử dụng phương pháp trích chọn các thuộc tính là các hàm API của Pujari và các cộng sự [8]. Mục đích là để xác định một bộ các cuộc gọi API phổ biến nhất trong các phần mềm độc hại và một bộ các cuộc gọi API phổ biến đối với các phần mềm không phải độc hại, việc trích rút này được thực hiện thông qua quá trình lựa chọn những bộ hàm API có tần suất xuất hiện nhiều nhất. 2.1.2. Xây dựng bộ phân lớp mã độc dựa trên học máy Sau khi đã có tập dữ liệu, một phương pháp học máy sẽ được sử dụng để thực hiện quá trình học và đưa ra các bộ phân lớp. Bộ phân lớp này sau đó được dùng để dự đoán xác định lớp mã độc của một chương trình chưa biết. Theo Bishop [7], quá trình học này được mô tả như việc đưa ra một kết luận từ kinh nghiệm sẵn có. Dưới đây là một số mô hình học máy so và sự sánh tương đối 190 Mô hình kết hợp giữa học máy và giải thuật di truyền trong phát hiện mã độc giữa các mô hình trong việc thực thi phân lớp dữ liệu nói chung và phân lớp mã độc nói riêng. Có thể thấy các thuật toán đều có những ưu nhược điểm riêng, trong bài báo chúng tôi lựa chọn giải thuật cây quyết định kết hợp với giải thuật di truyền để nâng cao hiệu quả và độ chính xác của hệ thống. 2.2. Ứng dụng cây quyết định và thuật giải di truyền trên tập dữ liệu hàm API để phân loại mã độc Giải thuật di truyền là giải thuật được thiết kế để giải các bài toán tối ưu tổ hợp và tìm kiếm dựa trên việc mô phỏng quá trình chọn lọc và tiến hóa trong tự nhiên. Thuật toán di truyền chuẩn được biểu diễn bằng các phép lai ghép và đột biến giữa các chuỗi nhị phân. Thuật toán di truyền giúp cho việc tìm kiếm các phương án giảm thiểu so với việc duyệt qua tất cả các tập ràng buộc của dữ liệu, thường được sử dụng để tiếp cận giải các bài toán tìm kiếm số, chẳng hạn sinh ra các phương án tối ưu cho bài toán tìm kiếm [19]. Trong giải thuật di truyền, một dãy các chuỗi được mã hóa thành các phương án chấp nhận đươc cho một bài toán tối ưu và được tiến hóa theo hướng ngày càng tốt hơn. Ta có thể mô tả giải thuật di truyền sơ bộ như sau: Sinh ra phương án khởi đầu G(0); Đánh giá độ thích nghi của G(0); t := 0; Bước lặp t := t+ 1; Sinh ra G(t) từ G(t− 1); Đánh giá độ thích nghi của G(t); Cho đến khi tìm được phương án cần tìm Với tập các dữ liệu về hàm API của chương trình ứng dụng đã được thu thập và tiền xử lí, thuật toán di truyền được sử dụng trong bài báo này nhằm cải tiến việc phân loại các mã độc khi chúng sử dụng kĩ thuật che dấu. Bằng việc kết hợp thuật toán di truyền với kĩ thuật học máy có thể cho phép phát hiện chính xác các mã độc mới chưa có trong cơ sở dữ liệu mẫu, bao gồm cả các dạng mã độc lai giữa các loại khác nhau, ví dụ: Những mã độc hoạt động giống cả Logic bomb và Trojan. Bằng cách mô phỏng sự lai ghép giữa các loại mã độc như toán tử lai và hoán vị trong thuật toán di truyền [20]. Kĩ thuật mới này có thể tiên đoán sự xuất hiện của các mã độc, phát hiện được các mã độc sử dụng các kĩ thuật che dấu phức tạp. Các mã độc được phân tích và trích rút thành dãy các hàm API, được tiền xử lí và thu được một dãy nhị phân. Ở đây ta coi mỗi dãy nhị phân đại diện cho dãy các hàm API là một nhiễm sắc thể của mã độc. Để thực hiện thuật toán di truyền, đầu tiên ta sinh một phương án khởi đầu bằng cách chọn một mẫu trong bộ dữ liệu mẫu, tiến hành lai ghép các đoạn trong mẫu. Sau quá trình lai ghép ta thu được một thế hệ con, mỗi thế hệ này cần phải được đánh giá bởi một giá trị thích nghi. Ở đây ta định nghĩa hàm thích nghi của mỗi cá thể như sau: 191 Lương Thế Dũng Thuật toán Tốc độ Độ chính xác Ưu điểm Nhược điểm Hàng xóm K-gần nhất Chậm Trung bình iệu quả khi biến độc lập có nhiều hơn hai giá trị và tập dữ liệu lớn Độ phức tạp tính toán cao Máy vector hỗ trợ Nhanh Cao Các kết quả có tính hồi quy và dày, hiệu quả tốt hơn trong phân lớp văn bản, đoạn mẫu Chi phí và thời gian huấn luyện dài Naı¨ve Bayes Rất nhanh Cao Nhanh, dễ hơn với các dữ liệu bền vững. Nhạy cảm với những thuộc tính có tương quan Cây quyết định Rất nhanh Cao Dễ hiểu, dễ sinh luật và giảm thiểu độ phức tạp tính toán Xảy ra sai lầm ở các mức cao hơn do các kết quả sai ở mức dưới Trong một chuỗi nhị phân đại diện cho sự xuất hiện của các hàm API, mỗi hàm API ta gán nó các giá trị trọng số wij, mỗi trọng số đại diện cho giá trị xác suất xuất hiện của một hàm API thứ j trong một loại mã độc thứ i : i = 1(V irus), i = 2(Trojan), i = 3(Worm), i = 4(Backdoor) và i = 5 (Normal - phần mềm không độc hại). Tổng các trọng số bằng 1 cho mỗi hàm API trong mỗi mấu được trích xuất. Khi đó ta định nghĩa hàm thích nghi của cá thể X là: F (X) = max ∑ wij số vị trí có giá trị là 1 Sắp xếp cá thể X vào lớp i, khi đó các cá thể được kết luận là phần mềm thông thường sẽ không tiếp tục sinh sản nữa, còn các cá thể thuộc lớp mã độc sẽ tiếp tục được lai ghép và phát sinh các thế hệ mới. Sau quá trình trên, ta thu được một tập dữ liệu mẫu được phân loại di truyền. Tập mẫu này sau đó được sử dụng để để học bộ phân lớp dựa trên thuật toán học cây quyết định để sử dụng cho quá trình phân loại các mẫu mới chưa biết. Quá trình phân tích bằng thực nghiệm cho thây thuật toán cây quyết định C4.5 cho hiệu quả cao hơn các thuật toán cây quyết định khác. 2.3. Thử nghiệm Để thử nghiệm mô hình đề xuất, bài báo sử dụng bộ dữ liệu học bao gồm 1000 mẫu, trong đó 600 mẫu là các tệp chứa mã độc lấy từ kho mã độc vxheaven.com và 200 mẫu là các tệp chương trình không nhiễm mã độc lấy từ windows system. Dữ liệu kiểm thư bao gồm 200 mẫu hỗn hợp, trong đó có 50 mẫu là tệp không nhiễm mã độc và 150 mẫu là tệp nhiễm mã độc. Thực hiện các thực nghiệm với sự thay đổi với số lượng mẫu khác nhau của tập huấn luyện lấy từ tập đã xây dựng cho thấy kết quả chính xác của phương pháp như bảng dưới đây: 192 Mô hình kết hợp giữa học máy và giải thuật di truyền trong phát hiện mã độc Số mẫu Độ chính xác của mô hình 400 93.8% 480 94.1% 560 95.6% 640 97.3% 720 97.5% Dưới đây là biểu đồ so sánh kết quả của việc phân lớp sau khi kết hợp cây quyết định và giải thuật di truyền với việc chỉ sử dụng cây quyết định: Kết quả cho thấy khi kích thước của tập dữ liệu càng lớn thì độ chính xác của phương pháp đã đề xuất trong bài báo đưa ra kết quả càng tốt hơn phương pháp chỉ sử dụng thuật toán cây quyết định cho quá trình học. 3. Kết luận Bài báo đề xuất phương pháp tốt hơn cho việc phát hiện và phân loại mã độc dựa trên sự kết hợp kĩ thuật cây quyết định và giải thuật di truyền. Kết quả thử nghiệm cho thấy độ chính xác cao hơn khi chỉ sử dụng một mình giải thuật cây quyết định. Phương pháp đã đề xuất có thể áp dụng cho việc phát hiện và phân lớp các mã độc mới và các mã độc lai ghép dựa trên dữ liệu các cuộc gọi hàm API của chương trình mã độc. TÀI LIỆU THAM KHẢO [1] OECD Ministerial Meeting Report, Malicious Software (Malware): A Security Threat to the Internet Economy, Korean Communication Commision, Final draft, May 2007, 193 Lương Thế Dũng [2] Vinod, P. Laxmi, V. and M. S. Gaur. 2009, Survey on Malware Detection Methods, In Proceedings of the Hacker 2009, pp. 74-79. [3] Zhu Kenan, Yin Baolin, 2012, Malware Behavior Classification Approach Based on Naive Bayes, Journal of Convergence Information Technology (JCIT) Volume7, pp. 218-315. [4] Gavrilut, D., Cimpoesu, M.; Anton, D.; Ciortuz, L. 2009, Malware Detection Using Perceptrons and Support Vector Machines, Future Computing, Service Computation, Cognitive, Adaptive, Content, Patterns. [5] Konrad Rieck, Philipp Trinius, Carsten Willems, and Thorsten Holz, 2011, Automatic Analysis of Malware Behaviorusing Machine Learning, Journal of Computer Security (JCS), 19 (4), 639–668, IOSPress. [6] Manoun Alazab, Robert Layton, Sitalakshmi Venkataraman, Paul Watters, 2013, Malware Detection Based on Structural and Behavioural Features of API Calls, In ternational Journal of Electronic Security and Digital Forensics Volume 5 Issue 2, p. 90-109. [7] Veeramani R, Nitin Rai, 2012, Windows API based Malware Detection and Framework Analysis, International Journal of Scientific & Engineering Research Volume 3, Issue 3. [8] Mamoun Alazab, Sitalakshmi Venkatraman, Paul Watters, Moutaz Alazab, 2011, Zero-day Malware Detection based on Supervised Learning Algorithms of API call Signatures, Proceedings of the 9-th Australasian Data Mining Conference (AusDM’11), Ballarat, Australia, pp. 171-182. [9] Wang. C, Pang. J, Zhao. R, Fu., Liu. X, 2009, Malware Detection Based on Suspicious Behavior Identification; First International Workshop on Education [10] Technology and Computer Science, pp. 198-202. Wuhan, Hubei: IEEE. [11] Dewan Md Farid, Nouria Harbi, Mohammad Zahidur Rahman., 2010, Combining Naive Bayes and Decision Tree for adaptive Intrusion Detection. Vol. 2, No. 2, pp. 12–25. [12] Mezghani, D., Boujelbene, S., Ellouze, N., 2010, Evaluation of SVM Kernels and Conventional Machine Learning Algorithms for Speaker Identification, International Journal of Hybrid Information Technology, Vol. 3, No. 3, pp. 23-34. [13] Komashinskiy, D., Kotenko, I., 2010, Malware Detection by Data Mining Techniques Based on Positionally Dependent Features, InternationalConference on Parallel, Distributed and Network-Based Processing, pp. 617-623. Pisa. [14] Hall, P., Park, B., Samworth, R., 2008, Choice of neighbor order in nearest-neighbor classification, An Official Journal of the Institute of Mathematical Statistics, Vol. 36, No. 5, pp. 2135–2152. [15] Mohd Najwadi Yusoff, Aman Jantan, 2011, Optimizing Decision Tree in Malware Classification System by using Genetic Algorithm, International Journal on New Computer Architectures and Their Applications (IJNCAA) 1(3): 694-713 [16] Shrenik Shah, DNA Computation and Algorithm Design, Harvard University ’09 Cambridge, 194 Mô hình kết hợp giữa học máy và giải thuật di truyền trong phát hiện mã độc MA 02138 [17] Noreen, S., Murtaza, S., Shafiq, M., Farooq, M. 2009, Evolvable Malware; 11th Annual Conference on Genetic and Evolutionary Computation. pp. 1569–1576. Montreal, Quebec, Canada: ACM. [18] Preda, M., Christodorescu, M., Jha, S., Debray, S.; 2008, A Semantics-Based Approach to Malware Detection; Transactions on Programming Languages and Systems, Vol 30, No 5, pp 25-54. [19] D. Krishna Sandeep Reddy, Arun K. Pujari, 2006, N-gram analysis for computer virus detection, Journal in Computer Virology, 231-239, Volume 2, Number 1, pp. 231-239. [20] Mehdi, S., Tanwani, A., Farooq, M.; 2009, IMAD:In-Execution Malware Analysis and Detection; 11th Annual Conference on Genetic and Evolutionary Computation. New York, USA: ACM, pp. 1553-1560. [21] Mohamad Fadli Zolkipli, Aman Jantan.; 2010, Malware Behavior Analysis: Learning and Understanding Current Malware Threats; Second International Conference on Network Applications, Protocols and Services. pp. 218–221. Kedah, Malaysia: IEEE. ABSTRACT Combining machine learning and generic algorithms for malware detection In this paper the author proposes a novel method of classifying malwares that combines data classification techniques and genetic algorithms. Experiments done show that classification using the proposed method is better than the classification obtained when genetic algorithms are not used. Keywords: Malware, Malware detection, Machine learning, Genetic algorithm, Decision tree. 195