HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------

NGUYỄN HOÀNG GIANG

NGHIÊN CỨU CÁC PHƯƠNG PHÁP HỌC MÁY VÀ ỨNG DỤNG
TRONG PHÁT HIỆN XÂM NHẬP TRÁI PHÉP

LUẬN VĂN THẠC SĨ KỸ THUẬT
(Theo định hướng ứng dụng)

HÀ NỘI - 2016


HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------

NGUYỄN HOÀNG GIANG

NGHIÊN CỨU CÁC PHƯƠNG PHÁP HỌC MÁY VÀ ỨNG DỤNG
TRONG PHÁT HIỆN XÂM NHẬP TRÁI PHÉP

CHUYÊN NGÀNH : HỆ THỐNG THÔNG TIN
MÃ SỐ:

0

60.48.01.04

LUẬN VĂN THẠC SĨ KỸ THUẬT
(Theo định hướng ứng dụng)

Em xin chân thành cảm ơn toàn thể các thầy cô Khoa Quốc tế và Đào tạo Sau
Đại học; Khoa Công nghệ thông tin I – Học viện Công nghệ Bưu chính viễn thông
đã truyền đạt những kiến thức bổ ích và lý thú, giúp ích cho em trên con đường học
tập và nghiên cứu của mình.
Cuối cùng, tôi cũng xin cảm ơn tất cả những người bạn đã đóng góp ý kiến,
động viên, giúp đỡ tôi hoàn thành luận văn này.
Hà Nội, ngày 15 tháng 06 năm 2016
Tác giả luận văn

Nguyễn Hoàng Giang


iii

MỤC LỤC
LỜI CAM ĐOAN

i

LỜI CẢM ƠN

ii

MỤC LỤC

iii

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT

vi

Giới thiệu về học máy
1.2.
Phân loại các phương pháp học máy
1.2.1. Phương pháp học máy có giám sát
1.2.2. Phương pháp học máy không có giám sát
1.3.
Một số thuật toán học máy
1.3.1. Thuật toán học máy có giám sát: Support Vector Machine (SVM)
1.3.1.1. Tổng quan về SVM
1.3.1.2. Phân lớp tuyến tính
1.3.1.3. Phân lớp tuyến tính với trường hợp không phân tách được
1.3.1.4. Phân lớp phi tuyến tính
1.3.2. Thuật toán học máy có giám sát: K-Nearest Neighbor (K-NN)
1.3.2.1. Tổng quan về K láng giềng gần nhất
1.3.2.2. Thuật toán K-NN
1.3.2.3. Hàm tính khoảng cách
1.3.2.4. Chọn K
1.3.3. Thuật toán học máy không có giám sát: One-class SVM
1.3.3.1. Tổng quan về One-class SVM
1.3.3.2. Thuật toán One-class SVM
1.4.
Kết luận chương 1.

1
2
2
2
3
4


2.1.2.2. Thành phần của hệ thống IDS

30
30
31
31
32


iv

2.2.
Phân loại phát hiện xâm nhập trái phép theo nguồn dữ liệu
2.2.1. Phát hiện xâm nhập trái phép trên mạng (Network-based)
2.2.2. Phát hiện xâm nhập trái phép trên máy chủ (Host-based)
2.3.
Phân loại phát hiện xâm nhập trái phép theo kỹ thuật phân tích dữ liệu
2.3.1. Misuse Detection
2.3.2. Anomaly Detection
2.4.
Phát hiện xâm nhập trái phép tiếp cận băng phương pháp học máy (Machine
Learning Approach)
2.4.1. Phát hiện xâm nhập trái phép dựa vào học máy có giám sát
2.4.2. Phát hiện xâm nhập trái phép dựa vào học máy không có giám sát
2.5.
Mô tả bài toán đề xuất trong luận văn
2.5.1. Lựa chọn luồng dữ liệu Net-Flow
2.5.2. Phát hiện bất thường bằng K-NN, SVM và One-class SVM
2.6.
Kết luận chương 2.

3.2.3. Trích chọn đặc trưng
3.2.4. Cài đặt
3.3.
Kết quả và đánh giá
3.3.1. Tiêu chí đánh giá hệ thống IDS
3.3.2. Kết quả thử nghiệm
3.3.3. Đánh giá
3.4.
Kết luận chương 3.
KẾT LUẬN

1.
2.

Kết quả đạt được.
Hướng nghiên cứu trong tương lai.

44
45
45
46
47
50
50
52
52
54
54
54
56

75


v

4. Kết quả thử nghiệm với bộ dữ liệu ISCX Netflow
4.1.
Thuật toán K-NN
4.2.
Thuật toán SVM
4.3.
Thuật toán One-class SVM
PHỤ LỤC 02 : CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ

75
75
78
82
83


vi

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT

Viết tắt/Thuật ngữ

Ý nghĩa

Bộ dữ liệu nghiên cứu phát hiện xâm nhập

Thuật toán học máy Máy hỗ trợ Vector
Định dạng dữ liệu được thu thập qua việc bắt
Tcpdump
giữ gói tin ở dạng Packet
Phần mềm học máy của trường đại học
Weka
Waikato
Dataset


vii

DANH SÁCH BẢNG
Bảng 3.1: Các nhóm xâm nhập trái phép trong dữ liệu DARPA ............................ 46
Bảng 3.2: Bộ dữ liệu ISCX .................................................................................... 47
Bảng 3.3: Các thông số cơ bản của bộ dữ liệu netflow máy chủ Pascal .................. 50
Bảng 3.4: Số lượng tấn công từ từng máy chủ tới máy chủ Pascal ......................... 51
Bảng 3.5: Số lượng tấn công theo các cổng đích tới máy chủ Pascal...................... 51
Bảng 3.6: Các thông số cơ bản của bộ dữ liệu ISCX Netflow ................................ 52
Bảng 3.7: Số lượng tấn công theo các cổng đích với bộ dữ liệu ISCX ................... 52
Bảng 3.8: Các đặc trưng lựa chọn trong phát hiện xâm nhập trái phép ................... 53
Bảng 3.9: Thông tin bộ dữ liệu thử nghiệm DARPA Netflow máy chủ Pascal ....... 53
Bảng 3.10: Thông tin bộ dữ liệu thử nghiệm ISCX Netflow ngày 14/6 .................. 53
Bảng 3.11: Confusion Matrix ................................................................................ 55
Bảng 3.12: Đánh giá kết quả thử nghiệm với bộ dữ liệu DARPA Netflow ............. 57
Bảng 3.13: Đánh giá kết quả thử nghiệm với bộ dữ liệu ISCX Netflow ................. 58


viii


Hình 0.3: Chuẩn hóa dữ liệu Octet DARPA Netflow với Discretize ...................... 64
Hình 0.4: Chuẩn hóa dữ liệu Protocol DARPA Netflow với Normalize ................. 64
Hình 0.5: Chuẩn hóa dữ liệu Packets DARPA Netflow với Normalize .................. 65
Hình 0.6:Chuẩn hóa dữ liệu Octets DARPA Netflow với Normalize ..................... 65
Hình 0.7: Chuẩn hóa dữ liệu Protocol ISCX Netflow với Discretize ...................... 66
Hình 0.8: Chuẩn hóa dữ liệu Packet ISCX Netflow với Discretize......................... 66
Hình 0.9: Chuẩn hóa dữ liệu Octet ISCX Netflow với Discretize........................... 67
Hình 0.10: Chuẩn hóa dữ liệu Protocol ISCX Netflow với Normalize ................... 67


ix

Hình 0.11: Chuẩn hóa dữ liệu Packets ISCX Netflow với Normalize..................... 68
Hình 0.12: Chuẩn hóa dữ liệu Octets ISCX Netflow với Normalize ...................... 68
Hình 0.13: ROC của thuật toán K-NN với K=1 với bộ dữ liệu DARPA Netflow ... 69
Hình 0.14: ROC của thuật toán K-NN với K=4 với bộ dữ liệu DARPA Netflow ... 70
Hình 0.15: ROC của thuật toán SVM Linear với bộ dữ liệu DARPA Netflow ....... 71
Hình 0.16: ROC của thuật toán SVM Polynominal với bộ dữ liệu DARPA Netflow
.............................................................................................................................. 72
Hình 0.17: ROC của thuật toán SVM-RBF với bộ dữ liệu DARPA Netflow.......... 73
Hình 0.18: ROC của thuật toán SVM-Sigmoid với bộ dữ liệu DARPA Netflow .... 74
Hình 0.19: Kết quả phân loại với thuật toán One-class SVM với bộ dữ liệu DARPA
Netflow ................................................................................................................. 75
Hình 0.20: ROC của thuật toán K-NN với K=1 với bộ dữ liệu ISCX Netflow ....... 75
Hình 0.21: ROC của thuật toán K-NN với K=4 với bộ dữ liệu ISCX Netflow ....... 77
Hình 0.22: ROC của thuật toán SVM Linear với bộ dữ liệu ISCX Netflow ........... 78
Hình 0.23: ROC của thuật toán SVM Polynominal với bộ dữ liệu ISCX Netflow .. 79
Hình 0.24: ROC của thuật toán SVM-RBF với bộ dữ liệu ISCX Netflow .............. 80
Hình 0.25: ROC của thuật toán SVM-Sigmoid với bộ dữ liệu ISCX Netflow ........ 81
Hình 0.26: Kết quả phân loại với thuật toán One-class SVM với bộ dữ liệu ISCX

cách thức này có nhược điểm là không phát hiện được các cuộc tấn công không có
trong cơ sở dữ liệu, các kiểu tấn công mới, do vậy hệ thống luôn phải cập nhật các


2

mẫu tấn công mới. Trong khi đó cách thức phát hiện bất thường là kỹ thuật phát hiện
thông minh, nhận dạng ra các hành động không bình thường của mạng. Quan niệm
của cách thức này về các cuộc tấn công là khác so với các hoạt động thông thường.
Ban đầu, chúng lưu trữ các mô tả sơ lược về các hoạt động bình thường của hệ thống.
Các cuộc tấn công sẽ có những hành động khác so với bình thường và cách thức phát
hiện này có thể nhận dạng. Do đó, cách thức phát hiện xâm nhập trái phép dựa trên
bất thường mạng hiện nay đang trở thành hướng nghiên cứu chủ yếu đối với các hệ
thống phát hiện xâm nhập trái phép.
Học máy (Machine learning) là kỹ thuật cho phép giải quyết vấn để hoặc ra
quyết định dựa trên dữ liệu và kinh nghiệm. Với học máy, chương trình máy tính sử
dụng kinh nghiệm, quan sát, hoặc dữ liệu trong quá khứ để cải thiện công việc của
mình trong tương lai thay vì chỉ thực hiện theo đúng các quy tắc đã được lập trình
sẵn. Chính vì thế, việc ứng dụng Học máy trong phát hiện xâm nhập trái phép, đặc
biệt đối với phát hiện bất thường, là phù hợp và cần thiết trong bối cảnh hiện nay.
Chính vì vậy, học viên chọn đề tài luận văn “Nghiên cứu các phương pháp học
máy và ứng dụng trong phát hiện xâm nhập trái phép”, trong đó tập trung nghiên cứu
ứng dụng học máy trong phát hiện xâm nhập mạng bất thường.

2. Mục đích nghiên cứu
Nghiên cứu các phương pháp học máy;
Nghiên cứu một số cách thức phát hiện xâm nhập trái phép. Từ đó ứng dụng
phương pháp học máy phát hiện bất thường mạng.

3. Đối tượng nghiên cứu và phạm vi nghiên cứu

máy
Trong chương này, luận văn sẽ trình bày khái niệm về xâm nhập trái phép;
phân loại phát hiện xâm nhập trái phép dựa trên nguồn dữ liệu (Network-based, Hostbased) và dựa theo phương pháp xử lý (Misuse Detection, Anomaly Detection); cách
tiếp cận phát hiện xâm nhập trái phép dựa trên bất thường bằng phương pháp học
máy; Mô tả bài toán đề xuất trong luận văn.
Chương 3: Ứng dụng phương pháp học máy KNN, SVM và One-class SVM để
phát hiện bất thường
Trong chương này, luận văn sẽ trình bày về việc thử nghiệm ứng dụng phương
pháp học máy để phát hiện xâm nhập mạng bất thường: giới thiệu về mô hình thử
nghiệm, trong đó giới thiệu về cách thức xây dựng các bộ dữ liệu thử nghiệm ở dạng
Netflow (từ bộ dữ liệu thử nghiệm dạng Tcpdump của DARPA, ISCX); cách thức cài
đặt thử nghiệm; kết quả thử nghiệm và đánh giá kết quả thử nghiệm.


4

CHƯƠNG 1.

TỔNG QUAN VỀ CÁC PHƯƠNG PHÁP HỌC
MÁY

1.1. Giới thiệu về học máy
Theo định nghĩa của Wikipedia, Học máy, còn gọi là Máy học, (tiếng
Anh: Machine Learning) là một lĩnh vực của trí tuệ nhân tạo liên quan đến việc nghiên
cứu và xây dựng các kĩ thuật cho phép các hệ thống "học" tự động từ dữ liệu để giải
quyết những vấn đề cụ thể. Ví dụ như các máy có thể "học" cách phân loại thư điện
tử xem có phải thư rác (spam) hay không và tự động xếp thư vào thư mục tương ứng.
Học máy rất gần với suy diễn thống kê (statistical inference) tuy có khác nhau về
thuật ngữ.
Theo định nghĩa được nêu tại [2], Học máy là khả năng của chương trình máy


Thứ hai, nhiều ứng dụng đòi hỏi chương trình máy tính phải có khả năng thích
nghi. Ví dụ, hành vi mua sắm của khách hàng có thể thay đổi theo thời điểm
cụ thể trong ngày, trong năm, hoặc theo tuổi tác. Việc xây dựng thuật toán cố
định cho những ứng dụng cần thích nghi và thay đổi là không phù hợp. Học
máy mang lại khả năng thích nghi nhờ phân tích dữ liệu thu thập được.

-

Thứ ba, việc tìm được chuyên gia và thu thập được tri thức cần thiết cho việc
thiết kế thuật toán để giải quyết các vấn đề tương đối khó, trong khi dữ liệu
ngày càng nhiều và có thể thu thập dễ dàng hơn. Khả năng lưu trữ và tính toán
của máy tính cũng ngày càng tăng, cho phép thực hiện thuật toán học máy trên
dữ liệu có kích thước lớn.

-

Cuối cùng, bản thân khả năng học là một hoạt động trí tuệ quan trọng của con
người, do vậy học tự động hay học máy luôn thu hút được sự quan tâm khi xây
dựng hệ thống thông minh.

1.2. Phân loại các phương pháp học máy
1.2.1. Phương pháp học máy có giám sát
Học có giám sát (supervised learning): là một kĩ thuật của ngành học máy để
xây dựng một hàm (function) từ dữ liệu huấn luyện. Dữ liệu huấn luyện bao gồm các
cặp gồm đối tượng đầu vào (thường dạng vec-tơ), và đầu ra mong muốn. Đầu ra của
một hàm có thể là một giá trị liên tục (gọi là hồi qui), hay có thể là dự đoán một nhãn
phân loại cho một đối tượng đầu vào (gọi là phân loại). Nhiệm vụ của chương trình
học có giám sát là dự đoán giá trị của hàm cho một đối tượng bất kì là đầu vào hợp
lệ, sau khi đã xem xét một số ví dụ huấn luyện (nghĩa là, các cặp đầu vào và đầu ra

Ngoài phân cụm, một dạng học không giám sát phổ biến khác là phát hiện
luật kết hợp (association rule). Luật kết hợp có dạng P(A | B), cho thấy xác suất hai
tính chất A và B xuất hiện cùng với nhau. Ví dụ, qua phân tích dữ liệu mua hàng ở
siêu thị, ta có luật P(Bơ | Bánh mỳ) =80%, có nghĩa là 80% những người mua bánh
mỳ cũng mua bơ.
Các phương pháp học máy không có giám sát thông dụng:
-

One-class SVM;

1.3. Một số thuật toán học máy
Trong phần này, luận văn sẽ trình bày một số thuật toán học máy thuộc phương


7

pháp học máy có giám sát và phương pháp học máy không có giám sát trong đó đi
sâu vào trình bày các thuật toán học máy sẽ được ứng dụng trong phát hiện xâm nhập
trái phép ở chương 3 như: Support Vector Machine (SVM), K – Nearest Neighbor
(K-NN), và One-class SVM.

1.3.1. Thuật toán học máy có giám sát: Support Vector Machine
(SVM)
SVM là một công cụ mạnh và phổ biến để phân lớp dữ liệu lớn và nhiều chiều.
Máy vector hỗ trợ (SVM) được đề xuất bởi V.Vapnik và các đồng nghiệp vào những
năm 1970 ở Nga, và sau đó đã trở nên nổi tiếng trong những năm 90 của thế kỉ trước.

1.3.1.1. Tổng quan về SVM
Cho một tập dữ liệu huấn luyện biểu diễn trong không gian vector, trong đó
mỗi dữ liệu được biểu diễn là một điểm. Đặc điểm cơ bản của thuật toán SVM là tìm

trong không gian như sau:
(1.1)

+b=0

Trong đó w là vector pháp tuyến n chiều và b là giá trị ngưỡng.
Vector pháp tuyến w xác định chiều của siêu phẳng h(x), còn giá trị ngưỡng b
xác định khoảng cách giữa siêu phẳng và gốc.
Đặt ( ) =

( .

+ b) =

+1
1

.
.

+b> 0
+b

+

Từ đó rút ra siêu phẳng phân chia thỏa mãn công thức sau:
(

+

≥1 ớ

= 1, 2, … . ,

(1.5)


11

Về mặt hình học, các phần tử của không gian đầu vào X sẽ thuộc một trong
hai phần được phân tách bởi siêu phẳng xác định bởi biểu thức <w.x> + b = 0 với
<w.x> là tích vô hướng.
Trong không gian hai chiều thì các điểm có phương trình <w,x> = 0 tương ứng
với một đường đi qua gốc tọa độ, còn trong không gian ba chiều thì nó là một mặt
phằng qua gốc tọa độ. Biến b dịch chuyển mặt phẳng đi một khoảng so với mặt phẳng
gốc tọa độ.
Như đã đề cập ở trên, vấn đề cốt lõi là làm sao để tìm được siêu phẳng h(x) tối
ưu, tức là tìm w và b để khoảng cách biên là cực đại.
Gọi m là độ rộng của biên. Ta phải tìm w và b sao cho m là lớn nhất.

Hình 1.5: Minh họa độ rộng của biên


+

+

ủ
+

Từ đó ta có:
=

|1|
1
=
à
‖ ‖ ‖ ‖

=

| 1|
1
=
‖ ‖ ‖ ‖

Suy ra:
=

+

=


với α là một hệ số nhân Lagrange

( )≤0

Nếu có nhiều ràng buộc đẳng thức gi(x) = 0 với i = 1…r thì cần một hệ số nhân
Lagrange cho mỗi ràng buộc:
( )+

( )

=0

với α là một hệ số nhân Lagrange

( )≤0

Hàm L được gọi là hàm Lagrange:
=

( )+

( )

Như vậy theo công thức (1.6) hàm L được định nghĩa:
=

(1.7)

1
‖ ‖