ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
-------------------

LÊ HỮU DŨNG

PHÁT HIỆN BẤT THƯỜNG CỦA MẠNG
THEO CÁCH TIẾP CẬN HỌC MÁY

LUẬN VĂN THẠC SĨ KHOA HỌC

Hà Nội – Năm 2014


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
-------------------

LÊ HỮU DŨNG

PHÁT HIỆN BẤT THƯỜNG CỦA MẠNG
THEO CÁCH TIẾP CẬN HỌC MÁY

Chuyên ngành: Cơ sở Toán học cho Tin học
Mã số:

60460110

LUẬN VĂN THẠC SĨ KHOA HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS.TS. Lê Trọng Vĩnh


3.2.1

Bằng số liệu thống kê ......................................................................... 14

3.2.2

Theo cách tiếp cận học máy ............................................................... 15

CHƯƠNG 2: THUẬT TOÁN HỌC MÁY SUPPORT VECTOR MACHINE
(SVM).............................................................................................................. 16
2.1. Giới thiệu ............................................................................................ 16
2.2. Ý tưởng của SVM............................................................................... 16
2.3. Nội dung của SVM ............................................................................. 17
2.3.1. Cơ sở lý thuyết ................................................................................ 17
2.3.2. Bài toán phân 2 lớp với SVM.......................................................... 19
2.3.3. Phân nhiều lớp với SVM ................................................................. 23
2.3.4. Các bước chính của thuật toán SVM............................................... 24
2.3.5. Thuật toán SVM trong trường hợp dữ liệu được phân tách tuyến
tính. 25
2.3.6. Thuật toán SVM trong trường hợp dữ liệu không phân tách tuyến
tính trong không gian đặc trưng ................................................................... 36
2.3.6.1. Nhận xét ....................................................................................... 36

1


2.3.6.2. Dạng 1 của thuật toán SVM, bài toán C – SVC........................... 36
2.3.6.3. Dạng 2 của thuật toán SVM, bài toán v-SVC .............................. 41
2.3.7. SVM nhiều lớp ................................................................................ 43

Hình 2.4. Bài toán SVM trong trường hợp dữ liệu mẫu không phân tách tuyến
tính ................................................................................................................... 22
Hình 2.5. Minh họa về sự phân tách dữ liệu trong không gian đặc trưng ...... 25
Hình 2.7. Dữ liệu phân tách tuyến tính trong không gian đặc trưng qua phép
ánh xạ  .......................................................................................................... 28
Hình 3.1. Cấu trúc tổng thể mô hình phát hiện bất thường trong giai đoạn
huấn luyện ....................................................................................................... 47
Hình 3.2 Phát hiện gói tin bất thường trong thời gian thực ............................ 48
Hình 3.3: Cấu trúc gói tin [8] .......................................................................... 53
Hình 3.4: Quá trình thêm header cho dữ liệu truyền qua các tầng của mạng . 54
Hình 3.5: Thuật toán bóc tách header từ một gói tin ...................................... 60
Hình 3.6: Một phần tệp dữ liệu theo khuôn dạng đầu vào LibSVM .............. 61
Hình 4.1: Giao diện chương trình thực nghiệm .............................................. 63
Hình 4.2: Một phần nội dung tệp header của dữ liệu ngày thứ 2, tuần thứ 1
(xem ở dạng Hexa) .......................................................................................... 64
Hình 4.3: Tệp dữ liệu phục vụ huấn luyện ...................................................... 64
Hình 4.4: Giao diện chương trình khi tiến hành huấn luyện........................... 66
Hình 4.5: Giao diện chương trình khi đang chạy bước dự đoán (prediction)
với dữ liệu kiểm tra ......................................................................................... 69

3


Danh mục bảng biểu
Bảng 3.1: Các bộ dữ liệu năm 1999 của dự án DARPA intrusion detection
evaluation........................................................................................................ 49
Bảng 3.2: Bảng mô tả các kiểu tấn công đã được triển khai trong tuần 2 của
bộ dữ liệu năm 1999 trong dự án DARPA intrusion detection evaluation ... 49
Bảng 3.3: Ý nghĩa các thành phần trong một gói tin ...................................... 53
Bảng 3.4: IP Header ........................................................................................ 54

Tôi xin cam đoan luận văn là công trình nghiên cứu của bản thân. Các số liệu,
kết quả được trình bày trong luận văn này là trung thực và chưa từng được
công bố trong bất kỳ luận văn nào trước đây.
Học viên

Lê Hữu Dũng

6


LỜI NÓI ĐẦU

Các hoạt động kinh tế, xã hội của con người ngày càng sử dụng nhiều
đến máy tính và các thiết bị công nghệ. Cùng với điều này, nhu cầu sử dụng
mạng máy tính để trao đổi thông tin, chia sẻ tài nguyên cũng ngày càng tăng
cao. Bên cạnh đó, vấn đề đảm bảo cho sự an toàn của thông tin cũng như của
mạng máy tính ngày càng trở nên bức thiết. Để đảm bảo an toàn cho thông tin
và hoạt động của mạng máy tính thì cần triển khai nhiều giải pháp đồng bộ.
Trong đó, phát hiện sớm các bất thường của mạng được coi là một khâu quan
trọng giúp đảm bảo an toàn cho một mạng máy tính. Có nhiều cách hiện đang
được nghiên cứu, triển để phát hiện bất thường trong mạng như sử dụng
phương pháp nhận diện dấu hiệu, phương pháp thống kê và phương pháp sử
dụng các thuật toán học máy. Trong đó, các phương pháp học máy cho phép
đưa ra những kết quả phát hiện bất thường có độ chính xác cao và đặc biệt là
luôn có thể cải tiến để cho kết quả cao hơn.
Luận văn này với tên gọi “Phát hiện bất thường của mạng theo cách
tiếp cận học máy” tập trung tìm hiểu việc phát hiện các gói tin trong mạng là
bình thường hay bất thường bằng cách áp dụng thuật toán học máy để phân
lớp các gói tin.
Luận văn bao gồm 5 chương với nội dung như sau:

tin – truyền thông phát triển cùng với khả năng tiếp cận các sản phẩm công
nghệ của người dân đã tạo ra những điều kiện thuận lợi để nhiều nước triển
khai chính phủ điện tử và thành công. Ngay ở nước ta, nhiều dịch vụ hành
chính công đã được triển khai trực tuyến, mang lại nhiều lợi ích cho người
dân như: tờ khai Hải quan điện tử, khai thuế trực tuyến, đăng ký cấp Hộ chiếu
trực tuyến tại Công an TP Hà Nội, …
Các dịch vụ trên nền “Đám mây”: Trong vài năm qua, Công nghệ thông tin
(IT) đã bắt đầu một mẫu hình mới - điện toán đám mây. Mặc dù điện toán
đám mây chỉ là một cách khác để cung cấp các tài nguyên máy tính, chứ
không phải là một công nghệ mới, nhưng nó đã châm ngòi một cuộc cách
mạng trong cách cung cấp thông tin và dịch vụ của các tổ chức. Điện toán
đám mây là một giải pháp toàn diện cung cấp công nghệ thông tin như một

9


dịch vụ. Nó là một giải pháp điện toán dựa trên Internet ở đó cung cấp tài
nguyên chia sẻ giống như dòng điện được phân phối trên lưới điện. Các máy
tính trong các đám mây được cấu hình để làm việc cùng nhau và các ứng
dụng khác nhau sử dụng sức mạnh điện toán tập hợp cứ như thể là chúng
đang chạy trên một hệ thống duy nhất. Những lợi ích mà điện toán đám mây
mang lại gồm:
- Chi phí giảm: Điện toán đám mây có thể làm giảm cả chi phí vốn lẫn
chi phí vận hành vì các tài nguyên chỉ được mua khi cần và chỉ phải trả
tiền khi sử dụng.
- Cách sử dụng nhân viên được tinh giản: Việc sử dụng điện toán đám
mây giải phóng đội ngũ nhân viên quý giá cho phép họ tập trung vào
việc cung cấp giá trị hơn là duy trì phần cứng và phần mềm.
- Khả năng mở rộng vững mạnh: Điện toán đám mây cho phép khả năng
điều chỉnh quy mô ngay lập tức hoặc tăng lên hoặc giảm xuống, bất cứ

Sau đây là một vài ví dụ về rất nhiều cách mà kẻ tấn công có thể truy cập bất
hợp pháp hoặc ngăn cản người khác truy cập vào một mạng
Kĩ nghệ xã hội: kẻ tấn công có thể truy cập vào hệ thống bằng cách lừa một
người sử dụng cung cấp thông tin có thể sử dụng được để đột nhập vào hệ
thống. Ví dụ: kẻ tấn công có thể gọi cho một cá nhân với tư cách của một
người quản trị mạng lưới trên điện thoại mạo danh với nỗ lực thuyết phục cá
nhân tiết lộ thông tin bí mật (như mật khẩu, tên tập tin, các chính sách bảo
mật ). Hoặc kẻ tấn công có thể cung cấp một phần mềm cho người sử dụng hệ
thống dưới dạng phần mềm hay bản tin hấp dẫn trên mạng nhưng có chứa mã
độc hại để cung cấp những thông tin cần thiết hay mở cửa hậu (backdoor) cho
kẻ tấn công truy cập hệ thống.

11


Thực hiện lỗi: Những lỗi trong những chương trình đáng tin cậy có thể bị
khai thác bởi kẻ tấn công để lấy được cách truy cập trái phép đến 1 hệ thống
máy tính. Ví dụ như lỗi tràn bộ đệm hay xử lý sai các tập tin tạm thời.
Lạm dụng tính năng: Có những hành động hợp pháp người ta có thể thực
hiện bình thường nhưng khi đưa đến cực độ có thể dẫn đến lỗi của hệ thống.
Ví dụ khi mở hàng trăm kết nối Telnet để máy tính có thể điền vào bẳng tiến
trình của nó hoặc làm cho máy tính rơi vào trạng thái chờ đợi vô hạn hoặc
làm ngập lụt hệ thống bằng các email rác.
Cấu hình sai: kẻ tấn công có thể truy cập bởi một lỗi trong cấu hình của hệ
thống. Ví dụ: cấu hình mặc định của một số hệ thống bao gồm tài khoản
“khách” (guest) hay “quản trị viên” (Administrator) mà không được bảo vệ
bởi mật khẩu đủ mạnh.
Giả mạo: Trong một số trường hợp, kẻ tấn công có thể đánh lừa 1 hệ thống
cho phép truy cập bằng cách giả mạo một hệ thống khác. Một ví dụ là về việc
gửi 1 gói tin TCP có 1 địa chỉ nguồn được cài đặt làm như gói tin đó xuất hiện

chống lại sự xâm nhập.

3

Các phương pháp phát hiện xâm nhập mạng hiện có

Một hệ thống phát hiện xâm nhập sẽ thu thập thông tin từ một máy tính hoặc
mạng máy tính và cố gắng phát hiện kẻ xâm nhập hay lạm dụng hệ thống.
Thông thường, một hệ thống phát hiện xâm nhập sẽ cảnh báo con người về
truy cập khả nghi và không thực hiện gì thêm nhưng một số hệ thống mới như
Real Secure 2.5 hay Mc Afee Virus Scan Enterprise Edition có thể chủ động
ngăn chặn kẻ xâm nhập ngay khi phát hiện ra
Các phương pháp xâm nhập hiện có được xếp vào hai loại chính: nhận diện
dấu hiệu và phát hiện bất thường.
13


3.1

Nhận diện dấu hiệu

Trong kĩ thuật phát hiện bất thường dựa trên nhận diện dấu hiệu, những đặc
điểm bình thường của hệ thống được định nghĩa trước. Thêm vào đó, những
đặc điểm của những kiểu tấn công phổ biến cũng được ghi nhận để phục vụ
mục đích so sánh, phát hiện bất thường sau này. Sự bất thường có thể do một
hoạt động đã được định nghĩa là bình thường nhưng lại diễn ra ở thời điểm
không bình thường ví dụ như sự truy cập của một người dùng vào hệ thống
mạng của một tổ chức vào 3 giờ sáng – giờ mà ở tổ chức đó không có ai làm
việc thì có thể coi là một dấu hiệu bất thường. Hoặc cũng có thể là sự gia tăng
của dữ liệu bình thường trên hệ thống ví dụ như sự gia tăng kích thước của

chúng phù hợp với lớp bình thường hay bất thường để đưa ra cảnh báo.
Phương pháp này có những ưu điểm như:
• Có khả năng thay đổi chiến lược để đáp ứng được nhiều trường hợp
khác nhau (cả đã biết và chưa biết)
• Hiệu quả cao hơn do luôn có thể sử dụng các dữ liệu mới để bổ sung
vào tập dữ liệu huấn luyện nhằm cải thiện mô hình phân lớp ban đầu.
Bên cạnh đó, phương pháp này cũng còn một số nhược điểm như
• Chất lượng của mô hình phân lớp phụ thuộc tập dữ liệu huấn luyện, dữ
liệu kiểm tra và các đặc trưng được lựa chọn
• Tỉ lệ báo động giả (sai số) cao với phương pháp học máy phi giám sát.
Luận văn này lựa chọn nội dung Phát hiện bất thường trong mạng theo cách
tiếp cận học máy làm đề tài nghiên cứu. Chương tiếp theo, chúng ta sẽ tìm
hiểu về thuật toán Support Vector Machine (SVM) – một thuật toán học máy
có nhiều ứng dụng rộng rãi hiện nay.

15


CHƯƠNG 2: THUẬT TOÁN HỌC MÁY
SUPPORT VECTOR MACHINE (SVM)
2.1. Giới thiệu
Vấn đề phân lớp (Classification) và dự đoán (Prediction) là hai bài toán
cơ bản và có rất nhiều ứng dụng trong tất cả các lĩnh vực. Có nhiều phương
pháp đã được nghiên cứu và ứng dụng cho các bài toán dạng này như: mạng
rron nhân tạo, phương pháp học thống kê,… Trong chương này, chúng ta sẽ
đi sâu nghiên cứu thuật toán Support Vector Machines (SVM), một thuật toán
học máy rất hiệu quả hiện nay.
Thuật toán SVM được coi là công cụ mạnh cho những bài toán phân
lớp phi tuyến được các tác giả Vapnik và Chervonenkis phát triển mạnh mẽ
năm 1995. Phương pháp này thực hiện phân lớp dựa trên nguyên lý Cực tiểu

Ta có, phương trình siêu phẳng chứa véc tơ xl trong không gian:
xl . w  b  0


1, xl . w  b  0
Đặt f ( xl )  sign( xl . w  b)  

1, xl . w  b  0

17


Như vậy, f ( xl ) biểu diễn sự phân lớp của xl vào hai lớp như đã nêu.
Ta nói yi   1 nếu xl  lớp I và yi   1 nếu xl  lớp II. Khi đó để có siêu
phẳng f ta sẽ phải giải bài toán sau:
Tìm min w với w thỏa mãn điều kiện sau:





yi sign( xl .w  b)  1,  i  1, n
Bài toán SVM có thể giải bằng kỹ thuật sử dụng nhân tử Lagrange để
biến đổi về thành dạng đẳng thức. Một đặc điểm thú vị của SVM là mặt
phẳng quyết định chỉ phụ thuộc vào các Support Vector và nó có khoảng cách
đến mặt phẳng quyết định là

1

. Cho dù các điểm khác bị xóa đi thì thuật

f ( x)  wt x  b

(2.1)

với w là véc tơ n chiều và b là véc tơ vô hướng.
Siêu phẳng phân tách thỏa mãn:
yi (w t xi  b)  1 với i  1, 2, ..., l

(2.2)

Siêu phẳng phân chia tối ưu là siêu phẳng chia hai lớp với với khoảng
cách giữa hai lớp là lớn nhất.

Hình 2.2. Minh họa cho bài toán phân hai lớp
Siêu phẳng tối ưu có thể xác định được bằng việc giải bài toán tối ưu
bậc hai sau:
Cực tiểu

1 2
w
2

(2.3)

19


với mọi ràng buộc yi (wxi  b)  1
Nếu số thuộc tính của các mẫu dữ liệu là lớn, chúng ta có thể đơn giản
hóa phép tính bằng cách chuyển bài toán với điều kiện Kuhn-Tucker tương


1 M
Cực đại W(α)   i   i  k yi yk xi xk
2 i ,k  0
i 1

Với ràng buộc

M

 yii  0,
i 1

(2.7)

i  0, i  1,...,M

Số lượng biến trong bài toán tối ưu trên chính là số mẫu trong tập dữ
liệu huấn luyện.
20


Giả sử ta tìm được cặp nghiệm tối ưu là

,

. Theo lý thuyết Karush-

Tucker, điều kiện xảy ra đẳng thức (2.2) tương ứng với mỗi cặp huấn luyện
vào – ra ( ,

hình 2.3:

21


Hình 2.3. Minh họa bài toán phân hai lớp với Thuật toán SVM
Để xác định hàm phân lớp dựa trên thuật toán SVM, ta sẽ tiến hành
tìm hai siêu phẳng song song (tương ứng với 2 đường nét đứt trong hình 2.3
ở trên) sao cho khoảng cách y giữa chúng là lớn nhất có thể để phân tách
hai lớp này ra làm hai phía. Hàm phân tách tương ứng với phương trình siêu
phẳng nằm giữa hai siêu phẳng tìm được (đường nét đậm trên hình 2.3).
Hình 2.3 thể hiện trường hợp có thể tìm được siêu phẳng phân tách, dữ
liệu trong trường hợp này gọi là phân tách tuyến tính. Bây giờ ta xét trường
hợp dữ liệu không phân tách tuyến tính như trong hình 2.4 như sau:

Hình 2.4. Bài toán SVM trong trường hợp dữ liệu mẫu không phân tách tuyến
tính
22


Ta thấy rằng trong hình 2.4 ở trên có những mẫu mặc dù có nhãn +1,
nhưng lại bị “rơi” vào phía các mẫu có nhãn 1 và ngược lại.
Trong trường hợp này, thuật toán SVM sẽ sử dụng một phép ánh xạ dữ
liệu mẫu vào không gian mới có số chiều lớn hơn sao cho tập mẫu này sẽ là
phân tách tuyến tính trong không gian đó (ta gọi không gian mới này là
không gian đặc trưng). Trong không gian đặc trưng này, ta vẫn tiến hành tìm
khoảng cách cực đại giữa hai siêu phẳng song song để phân tách dữ liệu mẫu.
Các điểm mà nằm trên hai siêu phẳng phân tách được gọi là các
Support Vector. Các điểm này sẽ quyết định đến hàm phân tách dữ liệu.
Trong thực tế, để thuận tiện cho quá trình tính toán, dữ liệu mẫu sẽ