Xem mẫu
- Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 09-10/8/2018
DOI: 10.15625/vap.2018.00064
TẠO LUẬT CHO CÁC BỨC TƯỜNG LỬA SỬ DỤNG CÁC KỸ THUẬT
KẾT HỢP DỰA TRÊN CÂY QUYẾT ĐỊNH
Hoàng Ngọc Thanh1, 3, Trần Văn Lăng2
1
Trường Đại học Lạc Hồng
2
Viện Cơ học và Tin học ứng dụng, VAST
3
Khoa Công nghệ Thông tin, Trường Đại học Bà Rịa - Vũng Tàu
thanhhn@bvu.edu.vn, langtv@vast.vn
TÓM TẮT: Các bức tường lửa hiện nay hoạt động chủ yếu dựa trên các luật đã được thiết lập trước. Những bức tường lửa này tìm
ra sự xâm nhập mạng bằng cách kiểm tra các đặc tính của dữ liệu cần phân tích với các luật đã biết và ngăn chặn nếu phát hiện tấn
công. Khi lưu lượng mạng phát triển nhanh chóng, việc cập nhật thủ công các luật ngày càng trở nên khó khăn, tẻ nhạt và tốn nhiều
thời gian. Kể từ đó, các phương pháp máy học đã được giới thiệu để giải quyết vấn đề này. Máy học đề cập đến các thuật toán máy
tính có khả năng học hỏi từ các mẫu dữ liệu trong quá khứ để nhận ra các mẫu tấn công mới, và từ đó tạo ra các luật mới cho các
bức tường lửa giúp ngăn chặn các cuộc tấn công mạng ngày càng phong phú, đa dạng và không ngừng thay đổi như hiện nay. Bài
báo đề cập đến việc sử dụng các kỹ thuật kết hợp nhiều mô hình máy học như: Boosting, Bagging, Stacking, Random Forest và
Decorate (Diverse Ensemble Creation by Oppositional Relabeling of Artificial Training Examples) để xây dựng các bộ phân lớp kết
hợp có chất lượng cao trong việc phát hiện các dấu hiệu tấn công, từ đó tạo ra các luật mới giúp các bức tường lửa ngăn chặn các
tấn công chưa từng biết. Kết quả thử nghiệm thực hiện trên các bộ dữ liệu NSL-KDD, bộ dữ liệu được nhiều học giả sử dụng nhất
và UNSW-NB, bộ dữ liệu hiện đại do Trung tâm An ninh mạng của Úc tạo ra năm 2015 cho thấy: các kỹ thuật kết hợp cho kết quả
tốt nhất trong đa số các trường hợp khi phát hiện các mẫu tấn công.
Từ khóa: Máy học; Cây quyết định; Bức tường lửa; Random Forest; Boosting; Bagging; Stacking; Decorate.
I. GIỚI THIỆU
Tấn công mạng là hình thức tấn công xâm nhập vào các hệ thống thông tin máy tính, cơ sở hạ tầng, mạng máy
tính hoặc các thiết bị cá nhân bằng nhiều cách khác nhau của các hành vi độc hại thường có nguồn gốc từ một nguồn
giấu tên, mà đánh cắp, thay đổi hoặc hủy hoại một mục tiêu cụ thể bằng cách hack vào một hệ thống dễ bị tổn thương
[1]. Tấn công mạng ngày càng trở nên phức tạp và nguy hiểm như những con sâu Stuxnet gần đây đã chứng minh [2].
Để ngăn chặn các cuộc tấn công mạng như vậy, người ta đã xây dựng các bức tường lửa đặt tại các cổng kết nối của hệ
thống thông tin máy tính, các bức tường lửa này tìm ra sự xâm nhập bằng cách so sánh các đặc tính của dữ liệu đi qua
cổng kết nối với các dấu hiệu tấn công đã biết, nếu phát hiện dấu hiệu tấn công, bức tường lửa sẽ loại bỏ các gói tin
tương ứng để ngăn ngừa xâm nhập. Tuy nhiên, kẻ xâm nhập cũng không ngừng tìm kiếm các hình thức xâm nhập mới,
điều đó làm cho hoạt động phát hiện xâm nhập của bức tường lửa trở nên khó khăn. Để khắc phục, các bức tường lửa
cần liên tục cập nhật các dấu hiệu tấn công mới và điều này thường không kịp thời và tốn nhiều chi phí. Kể từ đó, các
phương pháp máy học đã được giới thiệu để giải quyết vấn đề phát hiện xâm nhập. Máy học đề cập đến các thuật toán
máy tính có khả năng học hỏi từ các mẫu dữ liệu trong quá khứ để tự động phát hiện các mẫu tấn công mới. Dựa trên
máy học, các tường lửa đã hoạt động tốt hơn trong nhiều báo cáo cũng như thực tế triển khai [3].
Bên cạnh việc phát triển các mô hình máy học là các bộ phân lớp đơn sử dụng các thuật toán máy học như: cây
quyết định, mạng nơron, mạng Naïve Bayes, k láng giềng gần nhất, máy vectơ hỗ trợ, hồi quy luận lý,… Từ những
năm 1990, cộng đồng máy học đã nghiên cứu cách để kết hợp nhiều mô hình phân lớp thành tập hợp các mô hình phân
lớp để cho tính chính xác cao hơn so với chỉ một mô hình phân lớp. Mục đích của các mô hình tập hợp là làm giảm
phương sai (variance) và/hoặc độ lệch (bias) của các giải thuật học. Độ lệch là khái niệm về lỗi của mô hình học
(không liên quan đến dữ liệu học) và phương sai là lỗi do tính biến thiên của mô hình so với tính ngẫu nhiên của các
mẫu dữ liệu học. Năm 1992 Buntine [4] đã giới thiệu các kỹ thuật Bayes để giảm phương sai của các phương pháp học.
Phương pháp xếp chồng (Stacking) do Wolpert giới thiệu năm 1992 [5] hướng tới việc cực tiểu hóa độ lệch của các
giải thuật học. Trong khi Freund và Schapire [6] đưa ra Boosting năm 1995, Breiman [7] đề nghị ArcX4 năm 1998 để
cùng giảm độ lệch và phương sai, còn Bagging do Breiman [8] đề nghị năm 1996 thì giảm phương sai của giải thuật
học nhưng không làm tăng độ lệch quá nhiều. Tiếp cận rừng ngẫu nhiên (Random Forest) do Breiman đề xuất năm
2001 [9] là một trong những phương pháp tập hợp mô hình thành công nhất. Giải thuật rừng ngẫu nhiên xây dựng cây
không cắt nhánh nhằm giữ cho độ lệch thấp và dùng tính ngẫu nhiên để điều khiển tính tương quan thấp giữa các cây
trong rừng.
Việc ứng dụng các kỹ thuật kết hợp như Bagging, Boosting và Stacking nêu trên vào các hệ thống phát hiện
xâm nhập mạng (Network Intrusion Detection System: NIDS) cũng đã được các tác giả đề xuất trong [10].
Nội dung bài báo này đề cập đến việc sử dụng các kỹ thuật kết hợp nhiều mô hình phân lớp như: Boosting,
Bagging, Stacking, Random Forest và Decorate để xây dựng các bộ phân lớp kết hợp có chất lượng cao trong phát hiện
các dấu hiệu tấn công mới, từ đó tạo ra các luật mới giúp các bức tường lửa ngăn chặn các cuộc tấn công mạng ngày
càng phong phú, đa dạng và không ngừng thay đổi như hiện nay.
- 490 TẠO LUẬT CHO CÁC BỨC TƯỜNG LỬA SỬ DỤNG CÁC KỸ THUẬT KẾT HỢP DỰA TRÊN CÂY QUYẾT ĐỊNH
II. TẬP DỮ LIỆU
Trước khi các bộ phân lớp được đưa vào sử dụng để phát hiện xâm nhập mạng, các bộ phân lớp phải trải qua
quá trình huấn luyện và kiểm tra, việc huấn luyện và kiểm tra được thực hiện trên tập dữ liệu đã được gán nhãn trước.
Dưới đây là thông tin chi tiết về 2 tập dữ liệu được dùng trong các thí nghiệm.
2.1. Tập dữ liệu NSL-KDD
Mặc dù tập dữ liệu KDD99 đã hơn 15 năm tuổi, nhưng theo điều tra về mức độ sử dụng của tập dữ liệu trong
nghiên cứu máy học và hệ thống phát hiện xâm nhập giai đoạn 2010-2015 của Atilla Özgür và Hamit Erdem [11] cho
thấy: KDD99 là tập dữ liệu được sử dụng nhiều nhất. KDD99 được tạo ra bằng cách xử lý phần dữ liệu TCPDUMP lấy
được trong 7 tuần từ hệ thống phát hiện xâm nhập DARPA 1998. KDD99 gồm các tập dữ liệu huấn luyện và kiểm tra.
Tập dữ liệu huấn luyện có 4.898.431 bản ghi, mỗi bản ghi có 41 thuộc tính (loại giao thức, dịch vụ và cờ) và được dán
nhãn là bình thường hoặc một cuộc tấn công một cách chính xác với một kiểu tấn công cụ thể [12].
Tập dữ liệu huấn luyện chứa 22 kiểu tấn công và thêm 17 kiểu trong tập dữ liệu kiểm tra, được phân thành 4
nhóm:
(1). Denial of Service (DoS), gồm các kiểu tấn công như: neptune, smurf, pod, teardrop, … Ở đó, kẻ tấn công
làm cho các tài nguyên tính toán hoặc bộ nhớ quá tải để xử lý các yêu cầu hợp lệ, hoặc từ chối người dùng hợp lệ truy
cập máy.
(2). Remote to Local (R2L), gồm các kiểu tấn công như: guess-passwd, ftp-write, imap, phf, … Ở đó, kẻ tấn
công tuy không có tài khoản nhưng có khả năng gửi các gói tin đến một máy qua mạng, sẽ khai thác một số lỗ hổng để
đạt được quyền truy cập cục bộ như là người sử dụng của máy đó.
(3). User to Root (U2R), gồm các kiểu tấn công như: buffer-overflow, load-module, perl, rootkit, … Ở đó, kẻ
tấn công bắt đầu với một quyền truy cập bình thường và sau đó khai thác một số lỗ hổng để đạt được quyền truy cập
root trên hệ thống.
(4). Probe, gồm các kiểu tấn công như: port-sweep, ip-sweep, nmap, … Ở đó, kẻ tấn công nỗ lực thu thập thông
tin về mạng máy tính nhằm phá vỡ khả năng kiểm soát an ninh của nó.
Năm 2009, Tavallaee và các đồng nghiệp [12] đã tiến hành phân tích thống kê bộ dữ liệu KDD99. Các tác giả
tìm thấy một số lượng lớn các bản ghi dư thừa, 78% trong tập dữ liệu huấn luyện và 75% trong tập dữ liệu kiểm tra. Số
lượng bản ghi trùng lặp này có thể ngăn chặn các thuật toán máy học với các bản ghi không xuất hiện thường xuyên
như các cuộc tấn công U2R. Các tác giả cũng lưu ý rằng các bản ghi trùng lặp trong tập dữ liệu KDD99 cũng sẽ làm
cho kết quả đánh giá bị sai lệch, bởi các thuật toán sẽ phát hiện tốt hơn với các bản ghi xuất hiện thường xuyên.
Tavallaee và các đồng nghiệp [12] đã tạo bộ dữ liệu NSL-KDD từ tập dữ liệu KDD99 để giải quyết các vấn đề đã đề
cập ở trên, bằng cách loại bỏ các bản ghi dư thừa. Tập dữ liệu huấn luyện của NSL-KDD gồm 125.973 bản ghi và tập
dữ liệu kiểm tra gồm 22.544 bản ghi, ít hơn nhiều so với tập dữ liệu KDD99. Các tác giả cho rằng kích thước của tập
dữ liệu NSL-KDD là hợp lý, có thể được sử dụng như tập dữ liệu hoàn chỉnh mà không cần phải lấy mẫu ngẫu nhiên.
Điều này cho phép xem xét một cách nhất quán và có thể so sánh các công trình nghiên cứu khác nhau.
Thông tin chi tiết về mỗi kiểu tấn công trong tập dữ liệu NSL-KDD được mô tả ở Bảng 1.
Bảng 1. Thông tin tập dữ liệu huấn luyện và kiểm tra NSL-KDD.
Phân lớp Tên tấn công Số bản ghi Tỷ lệ
Normal 67.343 53,45%
Probe ipsweep, mscan, nmap, saint, satan, portsweep 11.656 9,26%
DoS apache2, back, land, mailbomb, neptune, pod, smurf, teardrop, 45.927 36,46%
processtable, udpstorm
U2R buffer_overflow, httptunnel, ps, loadmodule, perl, rootkit, xterm, 52 0,04%
sqlattack
R2L ftp_write, guess_passwd, imap, multihop, named, phf, sendmail, 995 0,79%
snmpgetattack, snmpguess, spy, warezclient, worm, xlock, xsnoop,
warezmaster
Tổng cộng 125.973 100,00%
2.2. Tập dữ liệu UNSW-NB
Tập dữ liệu UNSW-NB được phát triển bằng cách sử dụng công cụ IXIA để trích xuất các hành vi bình thường
và tấn công hiện đại do Trung tâm An ninh mạng (ACCS) Úc thực hiện năm 2015. Bộ dữ liệu này bao gồm 9 loại tấn
công và 49 thuộc tính [13].
- Hoàng Ngọc Thanh, Trần Văn Lăng 491
Tập dữ liệu UNSW-NB chứa 2.540.044 bản ghi. Một phần của tập dữ liệu này được chia thành các tập dữ liệu
huấn luyện và kiểm tra, được dùng nhiều trong các thí nghiệm của các học giả, thông tin chi tiết về các tập dữ liệu
được trình bày ở Bảng 2. Các tập dữ liệu huấn luyện và kiểm tra này chứa tổng cộng 9 loại tấn công: Analysis,
Backdoor, DoS, Exploits, Fuzzers, Generic, Reconnaissance, Shellcode và Worms.
Bảng 2. Thông tin tập dữ liệu UNSW-NB.
Tập huấn luyện Tập kiểm tra
Loại tấn công
Số bản ghi Tỷ lệ Số bản ghi Tỷ lệ
Normal 56.000 31,94% 37.000 44,94%
Analysis 2.000 1,14% 677 0,82%
Backdoor 1.746 1,00% 583 0,71%
DoS 12.264 6,99% 4.089 4,97%
Exploits 33.393 19,04% 11.132 13,52%
Fuzzers 18.184 10,37% 6.062 7,36%
Generic 40.000 22,81% 18.871 22,92%
Reconnaissance 10.491 5,98% 3.496 4,25%
Shellcode 1.133 0,65% 378 0,46%
Worms 130 0,07% 44 0,05%
Tổng cộng 175.341 100,00% 82.332 100,00%
Bộ dữ liệu UNSW-NB có một số lợi thế khi so sánh với bộ dữ liệu NSL-KDD. Thứ nhất, nó chứa những hành
vi bình thường hiện đại và các hoạt động tấn công tổng hợp đương đại. Thứ hai, phân bố xác suất của các tập huấn
luyện và kiểm tra là tương tự. Thứ ba, nó bao gồm một tập hợp các thuộc tính từ payload và header của các gói để phản
ánh các gói tin mạng có hiệu quả. Cuối cùng, sự phức tạp của việc đánh giá UNSW-NB đối với các hệ thống phân lớp
hiện tại cho thấy bộ dữ liệu này có các mẫu phức tạp. Điều này có nghĩa là bộ dữ liệu có thể được sử dụng để đánh giá
các phương pháp phân lớp hiện tại và mới một cách hiệu quả và đáng tin cậy.
Tuy nhiên, do bộ dữ liệu UNSW-NB còn khá mới, nên chưa được nhiều học giả sử dụng trong các nghiên cứu
của mình. Vì vậy, cũng có hạn chế khi so sánh kết quả với các nghiên cứu khác.
III. CÂY QUYẾT ĐỊNH VÀ CÁC KỸ THUẬT KẾT HỢP
3.1. Cây quyết định
Với những ưu điểm của mình, cây quyết định được đánh giá là một công cụ mạnh, phổ biến và đặc biệt thích
hợp cho khai thác dữ liệu nói chung và phân lớp dữ liệu nói riêng [14]. Ngoài những ưu điểm như: xây dựng tương đối
nhanh, đơn giản. Cây quyết định dễ dàng được chuyển đổi sang các câu lệnh SQL được sử dụng để truy nhập cơ sở dữ
liệu một cách hiệu quả. Cuối cùng, việc phân lớp dựa trên cây quyết định trong các NIDS đạt được sự tương tự, đôi khi
là chính xác hơn so với các phương pháp phân lớp khác [15, 16].
Cây ngẫu nhiên (Random Tree) được đề cập trong phần thí nghiệm là những cây được xây dựng ngẫu nhiên mà
không liên quan gì đến việc máy học. Tuy nhiên, khung máy học Weka sử dụng thuật ngữ này để chỉ một cây quyết
định được xây dựng dựa trên một tập hợp các thuộc tính được lựa chọn ngẫu nhiên.
3.2. Bootstrap
Là một phương pháp rất nổi tiếng trong thống kê được giới thiệu bởi Bradley Efron vào năm 1979. Phương
pháp này chủ yếu dùng để ước lượng lỗi chuẩn (standard errors), độ lệch (bias) và tính toán khoảng tin cậy (confidence
interval) cho các tham số. Phương pháp này được thực hiện như sau: Từ một quần thể ban đầu lấy ra một mẫu L = (x 1,
x2, …, xn) gồm n thành phần, tính toán các tham số mong muốn. Trong các bước tiếp theo lặp lại b lần việc tạo ra mẫu
Lb cũng gồm n phần tử từ L bằng cách lấy lại mẫu với sự thay thế các thành phần trong mẫu ban đầu sau đó tính toán
các tham số mong muốn.
3.3. Bagging (Bootstrap Aggregation)
Phương pháp này được xem như là một phương pháp tổng hợp kết quả có được từ các Bootstrap. Tư tưởng
chính của phương pháp này như sau: Cho một tập huấn luyện D={(xi, yi): i=1, 2, …, n} và giả sử chúng ta muốn có
một dự đoán nào đó đối với biến x.
Một mẫu gồm B tập dữ liệu, mỗi tập dữ liệu gồm n phần tử được chọn lựa ngẫu nhiên từ D với sự thay thế
(giống như bootstrap). Do đó B=(D1, D2, …, DB) trông giống như là một tập các tập huấn luyện được nhân bản;
Huấn luyện một máy hoặc một mô hình đối với mỗi tập Db (b=1, 2, …, B) và lần lượt thu thập các kết quả dự
báo có được trên mỗi tập Db;
- 492 TẠO LUẬT CHO CÁC BỨC TƯỜNG LỬA SỬ DỤNG CÁC KỸ THUẬT KẾT HỢP DỰA TRÊN CÂY QUYẾT ĐỊNH
Kết quả tổng hợp cuối cùng được tính toán bằng cách trung bình hóa (regression) hoặc thông qua số phiếu bầu
nhiều nhất (classification).
3.4. Boosting
Khác với phương pháp Bagging, xây dựng bộ phân lớp kết hợp với các ví dụ huấn luyện có trọng số bằng nhau,
phương pháp Boosting xây dựng bộ phân lớp kết hợp với các ví dụ huấn luyện có trọng số khác nhau. Sau mỗi bước
lặp, các ví dụ huấn luyện được dự đoán sai sẽ được đánh trọng số tăng lên, các ví dụ huấn luyện được dự đoán đúng sẽ
được đánh trọng số nhỏ hơn. Điều này giúp cho Boosting tập trung vào cải thiện độ chính xác cho các ví dụ được dự
đoán sai sau mỗi bước lặp.
Một thuật toán Boosting ban đầu được định nghĩa là một thuật toán dùng để chuyển một thuật toán máy học yếu
thành một thuật toán máy học mạnh. Có nghĩa là nó chuyển một thuật toán máy học giải quyết một bài toán phân lớp
nhị phân tốt hơn cách giải chọn ngẫu nhiên thành một thuật toán giải quyết rất tốt bài toán đó. Thuật toán Boosting ban
đầu của Schapire là một thuật toán đệ quy. Tại bước cuối của đệ quy, nó kết hợp các giả thuyết được tạo bởi thuật toán
máy học yếu. Xác suất lỗi của bộ kết hợp này được chứng minh là nhỏ hơn xác suất lỗi của các giả thuyết yếu.
Adaboost là một thuật toán kết hợp một tập các bộ phân lớp được làm đa dạng bằng việc chạy thuật toán máy
học với phân bố khác nhau trên tập huấn luyện.
3.5. Stacking
Stacking là một cách để kết hợp nhiều mô hình, giới thiệu khái niệm bộ phân lớp meta. Nó ít được sử dụng rộng
rãi hơn so với Bagging và Boosting. Không giống như Bagging và Boosting, Stacking có thể được sử dụng để kết hợp
các mô hình khác nhau. Quá trình thực hiện như sau:
(1). Chia tập huấn luyện thành hai bộ tách rời.
(2). Huấn luyện các bộ phân lớp cơ sở ở phần đầu.
(3). Kiểm tra bộ phân lớp cơ sở ở phần thứ hai.
(4). Sử dụng kết quả dự đoán ở (3) như là đầu vào và kết quả phân lớp đúng như là kết quả đầu ra để huấn luyện
một bộ phân lớp meta.
Trong Stacking, cơ chế kết hợp là đầu ra của các bộ phân lớp (các bộ phân lớp cấp 0) sẽ được sử dụng làm dữ
liệu huấn luyện cho một bộ phân lớp khác (bộ phân lớp cấp 1) để cho ra kết quả dự báo đúng nhất. Về cơ bản, chúng ta
cho phép bộ phân lớp cấp 1 (bộ phân lớp meta) tự tìm ra cơ chế kết hợp tốt nhất các bộ phân lớp cấp 0.
3.6. Random Forest
Random Forest (rừng ngẫu nhiên) là phương phân lớp được phát triển bởi Leo Breiman tại đại học California,
Berkeley.
Tóm tắt của giải thuật Random Forest cho phân lớp được diễn giải như sau:
- Lấy ra K mẫu bootstrap từ tập huấn luyện.
- Đối với mỗi mẫu bootstrap xây dựng một cây phân lớp không được tỉa (unpruned tree) như sau: Tại mỗi nút
thay vì chọn một phân chia tốt nhất trong tất cả các biến dự đoán, ta chọn ngẫu nhiên một mẫu m của các biến dự đoán
sau đó chọn một phân chia tốt nhất trong các biến này.
- Đưa ra các dự đoán bằng cách tổng hợp các dự đoán của K cây.
Quá trình học của Random Forest bao gồm việc sử dụng ngẫu nhiên giá trị đầu vào, hoặc kết hợp các giá trị đó
tại mỗi node trong quá trình dựng từng câyquyết định. Kết quả của Random Forest, qua thực nghiệm cho thấy, là tốt
hơn khi so sánh với các thuật toán Boosting, Bagging và Stacking. Trong đó Random Forest có một số thuộc tính mạnh
như:
(1). Độ chính xác cao;
(2). Thuật toán giải quyết tốt các bài toán có nhiều dữ liệu nhiễu;
(3). Thuật toán chạy nhanh hơn so với Stacking nhưng chậm hơn so với Bagging và Boosting;
(4). Có những sự ước lượng nội tại như độ chính xác của mô hình phỏng đoán hoặc độ mạnh và liên quan giữa
các thuộc tính.
(5). Dễ dàng thực hiện song song.
Tuy nhiên để đạt được các tính chất mạnh trên, thời gian thực thi của thuật toán khá lâu và phải sử dụng nhiều
tài nguyên của hệ thống.
- Hoàng Ngọc Thanh, Trần Văn Lăng 493
Qua những tìm hiểu trên về giải thuật Random Forest ta có nhận xét rằng Random Forest là một phương pháp
phân lớp tốt do: (1) Trong Random Forest, phương sai (variance) được giảm thiểu do kết quả của Random Forest được
tổng hợp thông qua nhiều người học (learner); (2) Việc chọn ngẫu nhiên tại mỗi bước trong Random Forest sẽ làm
giảm mối tương quan (correlation) giữa các người học trong việc tổng hợp các kết quả.
3.7. Decorate
Boosting và Bagging cung cấp sự đa dạng bằng cách xây dựng tập hợp các bộ phân lớp, mà ở đó mỗi bộ phân
lớp được huấn luyện với một tập dữ liệu huấn luyện con khác nhau được trích ngẫu nhiên từ tập dữ liệu huấn luyện.
Nếu tập huấn luyện nhỏ, điều này giới hạn sự đa dạng của tập hợp mà phương pháp này có thể đạt được. Decorate đảm
bảo tính đa dạng nhờ một lượng lớn các ví dụ nhân tạo bổ sung. Vì vậy, về mặt lý thuyết nó sẽ cho độ chính xác phân
lớp cao hơn khi tập huấn luyện nhỏ.
Trong Decorate, một kết hợp được tạo lặp lại, trước tiên hãy huấn luyện một bộ phân lớp và sau đó thêm nó vào
kết hợp hiện tại. Chúng ta khởi tạo kết hợp để chứa bộ phân lớp được huấn luyện với dữ liệu huấn luyện đã cho. Các bộ
phân lớp trong mỗi lần lặp liên tiếp được huấn luyện về dữ liệu huấn luyện ban đầu kết hợp với một số dữ liệu nhân
tạo. Trong mỗi lần lặp lại, các ví dụ huấn luyện nhân tạo được tạo ra từ việc phân phối dữ liệu; trong đó số lượng ví dụ
được tạo được xác định là một phần, Rsize, của kích thước tập huấn luyện. Các nhãn cho các ví dụ huấn luyện được tạo
giả tạo này được chọn để khác biệt tối đa so với các dự đoán của quần thể hiện tại [17].
Nhằm tăng cường tính đa dạng, nhưng vẫn duy trì độ chính xác huấn luyện, bộ phân lớp mới sẽ bị từ chối thêm
vào tập hợp hiện có nếu nó làm giảm độ chính xác phân lớp của tập hợp. Quá trình này được lặp lại cho đến khi đạt
được kích thước tập hợp mong muốn hoặc vượt quá số lần lặp tối đa.
IV. CÁC CHỈ SỐ ĐÁNH GIÁ
Nếu FP là số mẫu bị phân lớp sai là dương tính; TP là số mẫu được phân lớp đúng là dương tính; FN là số mẫu
bị phân lớp sai là âm tính; TN là số mẫu được phân lớp đúng là âm tính. Việc đánh giá hiệu năng của các bộ phân lớp
được thực hiện qua việc đo và so sánh các chỉ số [18]:
- Accuracy = (TP + TN) / (TP + FP + TN + FN)
- Sensitivity = Recall = TPR = TP / (TP + FN)
- Specificity = TNR = TN / (TN + FP)
- Efficiency = (Sensitivity + Specificity) / 2
- Precise = TP / (TP + FP)
- Thời gian huấn luyện và kiểm tra
Việc sử dụng Accuracy để đánh giá chất lượng phân lớp đã được nhiều học giả sử dụng. Tuy nhiên, sự phân bố
lớp trong hầu hết các bài toán phân lớp phi tuyến rất mất cân bằng. Vì vậy việc sử dụng Accuracy để đánh giá chất
lượng phân lớp của một mô hình không thực sự hiệu quả. Vì vậy, một thước đo toàn diện hơn được đề nghị sử dụng
cho việc đánh giá là: Quality = Sensitivity * Specificity [19].
Có nhiều kỹ thuật đánh giá độ chính xác dự báo như: đánh giá chéo K-fold, Holdout, Re-substitution và Leave-
one-out [20]. Trong đó, đánh giá chéo K-fold được xem là hiệu quả, phù hợp với các NIDS. Theo đó, các bản ghi được
phân ngẫu nhiên thành k tập con; một tập con được chỉ định là tập dữ liệu kiểm tra và các tập con còn lại được xử lý
như tập dữ liệu huấn luyện. Sau đó, quá trình đánh giá chéo lặp lại k lần, cũng như độ chính xác phân lớp có thể được
kiểm tra thông qua các độ chính xác phân lớp trung bình từ k lần đánh giá. Đánh giá chéo K-fold đặc biệt phù hợp với
nguồn dữ liệu huấn luyện lớn, trái với đánh giá Leave-one-out, tốn nhiều thời gian để thực hiện.
V. KẾT QUẢ THÍ NGHIỆM
Các chương trình, thuật toán trong thí nghiệm sử dụng ngôn ngữ lập trình Java, dựa trên thư viện, khung làm
việc máy học Weka do Đại học Waikato, New Zealand phát triển và cơ sở dữ liệu SQL Server 2014.
Về kỹ thuật máy học, chúng tôi sử dụng cây quyết định dựa trên thuật toán J48 (mã nguồn mở của C4.5) và các
kỹ thuật kết hợp được thực hiện như sau: Bagging, Boosting và Decorate sử dụng bộ phân lớp cơ sở là cây ngẫu nhiên
(Random Tree); Stacking sử dụng các bộ phân lớp cơ sở là cây ngẫu nhiên và k láng giềng gần nhất, bộ phân lớp meta
là k láng giềng gần nhất. Đây là những kết quả tốt nhất có được với nhiều bộ phân lớp cơ sở, bộ phân lớp meta được
chọn để chạy và so sánh kết quả dựa trên các thuật toán máy học như: cây quyết định, mạng nơron, mạng Naïve Bayes,
k láng giềng gần nhất, máy vectơ hỗ trợ, hồi quy luận lý,…
Kết quả thực hiện trên các tập dữ liệu NSL-KDD và UNSW-NB được thể hiện cụ thể như sau:
- 494 TẠO LUẬT CHO CÁC BỨC TƯỜNG LỬA SỬ DỤNG CÁC KỸ THUẬT KẾT HỢP DỰA TRÊN CÂY QUYẾT ĐỊNH
5.1. Với tập dữ liệu NSL-KDD
Chất lượng phân lớp (Qualtity) ứng với mỗi kiểu phân lớp cũng như kỹ thuật kết hợp được trình bày ở Bảng 3.
Theo đó, Decorate cho chất lượng phân lớp tốt nhất ở các kiểu phân lớp Normal, DoS, U2R và R2L; Stacking cho chất
lượng phân lớp tốt nhất ở các kiểu phân lớp Probe.
Bảng 3. Chất lượng phân lớp (Quality) của các thuật toán với tập dữ liệu NSL-KDD
Kiểu phân lớp Cây quyết định Random Forest Boosting Bagging Stacking Decorate
Normal 99,37% 99,62% 99,54% 99,59% 99,39% 99,63%
DoS 99,91% 99,95% 99,94% 99,95% 99,86% 99,95%
Probe 99,09% 99,10% 98,97% 99,04% 99,24% 99,19%
U2R 61,53% 42,31% 50,00% 50,00% 34,61% 67,31%
R2L 93,13% 93,86% 93,45% 94,16% 90,24% 95,06%
Bảng 4 là thời gian huấn luyện ứng với mỗi kiểu phân lớp cũng như kỹ thuật kết hợp. Dễ dàng nhận thấy các kỹ
thuật kết hợp có thời gian huấn luyện cao hơn, trong đó nhiều nhất là Stacking có thời gian huấn luyện cao nhất và cao
hơn nhiều lần so với các kỹ thuật kết hợp còn lại.
Bảng 4. Thời gian thực thi của các thuật toán kết hợp với tập dữ liệu NSL-KDD
Kiểu phân lớp Cây quyết định Random Forest Boosting Bagging Stacking Decorate
Normal 48.190 ms 213.042 ms 90.998 ms 56.691 ms 4.263.784 ms 264.192 ms
DoS 29.759 ms 193.541 ms 76.278 ms 51.471 ms 4.447.236 ms 214.927 ms
Probe 38.923 ms 204.573 ms 73.780 ms 58.484 ms 4.486.024 ms 251.195 ms
U2R 26.392 ms 122.016 ms 47.691 ms 36.876 ms 5.004.588 ms 244.853 ms
R2L 44.768 ms 143.053 ms 59.843 ms 40.096 ms 4.417.959 ms 256.266 ms
5.2. Với tập dữ liệu UNSW-NB
Chất lượng phân lớp ứng với mỗi kiểu phân lớp cũng như kỹ thuật kết hợp được trình bày ở Bảng 5. Theo đó,
Random Forest cho chất lượng phân lớp tốt nhất ở kiểu phân lớp Normal; Cây quyết định cho chất lượng phân lớp tốt
nhất ở các kiểu phân lớp Analysis, Reconnaissance, Shellcode và Worms; Stacking cho chất lượng phân lớp tốt nhất ở
các kiểu phân lớp Backdoor, DoS và Exploits; và cuối cùng Decorate cho chất lượng phân lớp tốt nhất ở các kiểu phân
lớp Generic và Fuzzers.
Bảng 5. Chất lượng phân lớp (Quality) của các thuật toán với tập dữ liệu UNSW-NB
Kiểu phân lớp Cây quyết định Random Forest Boosting Bagging Stacking Decorate
Normal 94,66% 95,96% 94,29% 95,74% 92,58% 95,77%
Analysis 7,98% 6,65% 7,24% 6,50% 5,46% 7,39%
Backdoor 3,09% 1,54% 1,89% 1,72% 4,12% 2,23%
DoS 7,97% 8,50% 9,56% 9,72% 35,00% 9,71%
Exploits 60,77% 62,44% 61,05% 60,90% 67,81% 62,23%
Generic 97,48% 97,39% 97,24% 97,36% 96,62% 97,59%
Fuzzers 62,46% 62,77% 61,24% 61,27% 60,41% 63,65%
Reconnaissance 78,44% 77,03% 77,90% 76,63% 78,17% 78,08%
Shellcode 39,90% 28,55% 28,53% 28,82% 19,04% 36,21%
Worms 47,72% 2,27% 22,72% 4,55% 2,27% 15,91%
Bảng 6 là thời gian huấn luyện ứng với mỗi kiểu phân lớp cũng như kỹ thuật kết hợp. Cũng tương tự như với tập
dữ liệu NSL-KDD, cây quyết định có thời gian huấn luyện ít nhất và ít hơn nhiều so với các kỹ thuật kết hợp còn lại,
trong khi Stacking vẫn có thời gian huấn luyện dài nhất và dài hơn nhiều lần so với các kỹ thuật kết hợp khác.
Bảng 6. Thời gian thực thi của các thuật toán kết hợp với tập dữ liệu UNSW-NB
Kiểu phân lớp Cây quyết định Random Forest Boosting Bagging Stacking Decorate
Normal 25.249 ms 118.131 ms 57.374 ms 34.344 ms 2.102.826 ms 122.094 ms
Analysis 12.407 ms 71.675 ms 29.733 ms 21.795 ms 2.100.604 ms 139.194 ms
Backdoor 20.523 ms 89.346 ms 39.977 ms 25.626 ms 2.109.406 ms 135.558 ms
DoS 26.376 ms 115.865 ms 49.634 ms 34.737 ms 2.586.286 ms 146.773 ms
Exploits 28.392 ms 125.116 ms 53.632 ms 35.595 ms 2.587.949 ms 130.523 ms
- Hoàng Ngọc Thanh, Trần Văn Lăng 495
Kiểu phân lớp Cây quyết định Random Forest Boosting Bagging Stacking Decorate
Generic 21.330 ms 105.349 ms 58.931 ms 29.095 ms 2.549.906 ms 123.340 ms
Fuzzers 18.610 ms 111.766 ms 47.785 ms 31.893 ms 2.544.552 ms 137.794 ms
Reconnaissance 18.360 ms 96.021 ms 43.348 ms 27.502 ms 2.557.509 ms 130.864 ms
Shellcode 9.281 ms 64.863 ms 29.406 ms 19.766 ms 2.535.442 ms 141.709 ms
Worms 9.626 ms 58.753 ms 28.287 ms 17.329 ms 2.546.612 ms 140.113 ms
VI. KẾT LUẬN
Từ kết quả thí nghiệm với cả hai tập dữ liệu NSL-KDD và UNSW-NB nêu trên, ta nhận thấy:
(1). Tùy tính chất đặc thù dữ liệu của mỗi kiểu tấn công, các bộ phân lớp kết hợp cho chất lượng phân lớp tốt
hơn các bộ phân lớp đơn trong phần lớn các trường hợp.
(2). Sự phân bố lớp trong bài toán phát hiện xâm nhập mạng rất mất cân bằng, vì vậy việc sử dụng độ chính xác
(accuracy) để đánh giá chất lượng phân lớp của một mô hình không thực sự hiệu quả. Vì vậy, việc sử dụng thước đo
toàn diện hơn được đề nghị là Quality = Sensitivity * Specificity trong thí nghiệm đã minh chứng điều đó.
(3). Thời gian huấn luyện của các bộ phân lớp kết hợp lớn, đặc biệt là khi so với các bộ phân lớp đơn.
(4). Việc sử dụng các bộ phân lớp yếu (weak learner) trong kết hợp cho kết quả tốt hơn việc sử dụng các bộ
phân lớp mạnh trong kết hợp.
(5). Kết quả đánh giá của tập dữ liệu UNSW-NB đối với các bộ phân lớp đơn và kết hợp cho thấy: bộ dữ liệu
này có nhiều mẫu phức tạp.
Đồng thời, kết quả thí nghiệm cũng đặt ra các vấn đề cần được tiếp tục nghiên cứu, đặc biệt là các nội dung:
(1). Việc nghiên cứu sử dụng các thuật toán học yếu khác khi xây dựng các bộ phân lớp kết hợp có thể sẽ đem
lại hiệu năng cao hơn trong các hệ thống phát hiện xâm nhập.
(2). Cần nghiên cứu tìm giải pháp giảm thiểu thời gian huấn luyện của các bộ phân lớp kết hợp.
(3). Cần tìm kiếm thuật toán xây dựng tập các ví dụ nhân tạo bổ sung (vào tập dữ liệu huấn luyện) để kỹ thuật
kết hợp Decorate có tính đa dạng cao hơn, từ đó cho chất lượng phân loại tốt hơn.
(4). Năng lực xử lý dữ liệu cũng như tính toán của hệ thống máy đóng vai trò quan trọng trong việc khai thác
thuật toán cũng như phương pháp máy học. Từ đó nâng cao hiệu quả xử lý, tiếp cận theo hướng trí tuệ nhân tạo.
VII. TÀI LIỆU THAM KHẢO
1. Lin Tom C. W.. Financial Weapons of War. Minnesota Law Review, 2016, vol. 100, pp. 1377-1440.
2. S. Karnouskos. Stuxnet Worm Impact on Industrial Cyber-Physical System Security. 37th Annual Conference of
the IEEE Industrial Electronics Society, Melbourne, Australia, 2014.
3. Aburomma A. A., Reaz M. B. I.. Evolution of Intrusion Detection Systems Based on Machine Learning Methods.
Australian Journal of Basic and Applied Sciences, 2013, vol. 7(7), pp. 799-813.
4. W. Buntine. Learning classification trees. Statistics and Computing, 1992, vol. 2, pp. 63-73.
5. D. Wolpert. Stacked generalization. Neural Networks, 1992, vol. 5, pp. 241-259.
6. Y. Freund and R. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting.
Computational Learning Theory, 1995, pp. 23-37.
7. L. Breiman. Arcing classifiers. The annals of statistics, 1998, vol. 26, no. 3, pp. 801-849.
8. L. Breiman. Bagging predictors. Machine Learning, 1996, vol. 24, no. 2, pp. 123-140.
9. L. Breiman. Random forests. Machine Learning, 2001, vol. 45, no. 1, pp. 5-32.
10. Iwan Syarif, Ed Zaluska, Adam Prugel-Bennett, Gary Wills. Application of Bagging, Boosting and Stacking to
Intrusion Detection. International Workshop on Machine Learning and Data Mining in Pattern Recognition, 2012,
pp. 593-602.
11. A Özgür, H Erdem. A review of KDD99 dataset usage in intrusion detection and machine learning between 2010
and 2015. PeerJ PrePrints, 2016.
12. Tavallaee, Mahbod; Bagheri, Ebrahim; Lu, Wei; Ghorbani, Ali A.. A detailed analysis of the KDD CUP 99 data
set. 2009 IEEE Symposium on Computational Intelligence for Security and Defense Applications, 2009, pp. 1-6.
13. Moustafa, N., & Slay, J.. UNSW-NB: A Comprehensive Data set for Network Intrusion Detection. Paper
presented at the Military Communications and Information Systems Conference, Canberra, Australia, 2015.
- 496 TẠO LUẬT CHO CÁC BỨC TƯỜNG LỬA SỬ DỤNG CÁC KỸ THUẬT KẾT HỢP DỰA TRÊN CÂY QUYẾT ĐỊNH
14. Guanghui S., Jiankang G., et al.. An Intrusion Detection Method Based on Multiple Kernel Support Vector
Machine. Network Computing and Information Security (NCIS), 2011 International Conference on, IEEE, 2011,
pp. 119-123.
15. Hoàng Ngọc Thanh, Trần Văn Lăng. Một tiếp cận máy học để phân lớp các kiểu tấn công trong hệ thống phát hiện
xâm nhập mạng. Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ IX “Nghiên cứu cơ bản và ứng dụng Công nghệ
thông tin (FAIR'9)”, 2016, pp. 502-508.
16. Hoàng Ngọc Thanh, Trần Văn Lăng. Rút gọn thuộc tính sử dụng độ lợi thông tin để tăng cường hiệu năng của các
hệ thống phát hiện xâm nhập mạng. Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ X “Nghiên cứu cơ bản và ứng
dụng Công nghệ thông tin (FAIR'10)”, 2017, pp. 823-831.
17. Prem Melville, Raymond J. Mooney. Constructing Diverse Classifier Ensembles using Artificial Training
Examples. Proceedings of the IJCAI-2003, Acapulco, Mexico, August 2003, pp. 505-510.
18. Marina Sokolova, Guy Lapalme. A systematic analysis of performance measures for classification tasks.
Information Processing and Management 45, 2009, pp. 427-437.
19. Yuk Ying Chung, Noorhaniza Wahid. A hybrid Network Intrusion Detection System using Simplified Swarm
Optimization (SSO). Publisher Elsevier, 2012, Applied Soft Computing 12 (2012), pp. 3014-3022.
20. Li W., Liu Z.. A method of SVM with Normalization in Intrusion Detection. Procedia Environmental Sciences 11,
2011, Part A(0) pp. 256-262.
CREATING RULES FOR FIREWALL USE OF DECISION TREE BASED
ENSEMBLE TECHNIQUES
Hoang Ngoc Thanh, Tran Van Lang
ABSTRACT: Firewalls now operate primarily based on pre-established rules. These firewalls detect network intrusion by
examining the characteristics of the data to be analyzed with the known rules. When network traffic grows, manual updating of rules
is becoming more and more difficult, tedious and time-consuming. Since then, machine learning methods have been introduced to
solve this problem. Machine learning refers to computer algorithms capable of learning from known patterns in order to identify
new patterns of attack and therefrom new rules are created for firewalls that help prevent network attacks that are increasingly rich,
varied and constantly changing as today. The paper deals with the use of decision tree based ensemble techniques such as Boosting,
Bagging, Stacking, Random Forests and Decorate (Diverse Ensemble Creation by Oppositional Relabeling of Artificial Training
Examples) to create high-performance classifiers. Test results are available on NSL-KDD dataset, the most widely used dataset and
UNSW-NB, a modern dataset created by the Australian Network Security Center in 2015, shows: ensemble techniques give the best
quality in most cases when detecting new patterns of attacks, thus helping to create better rules for firewalls.
nguon tai.lieu . vn
