..

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
---------------------------------------

LƯƠNG QUỐC TRUNG

PHÂN TÍCH LƯU LƯỢNG TRÊN INTERNET

Chuyên ngành: Kỹ Thuật Máy Tính Và Truyền Thơng

LUẬN VĂN THẠC SĨ KỸ THUẬT
Kỹ thuật Máy Tính Và Truyền Thơng

NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS.TS. NGÔ HỒNG SƠN

Hà Nội – 2015


MỤC LỤC
DANH MỤC CÁC HÌNH ...........................................................................................3
DANH MỤC CÁC BẢNG..........................................................................................4
DANH MỤC CÁC TỪ VIẾT TẮT ............................................................................5
LỜI CẢM ƠN .............................................................................................................6
LỜI CAM ĐOAN .......................................................................................................6
TÓM TẮT ...................................................................................................................7
GIỚI THIỆU ...............................................................................................................8
CHƯƠNG I. CƠ SỞ LÝ THUYẾT .........................................................................10
1. Bất thường và Phát hiện bất thường................................................................10

1.1.

Giới thiệu ..................................................................................................10

1.2.

Phân loại dựa trên các kỹ thuật phát hiện bất thường ..............................15

1.3.

Kỹ thuật phát hiện bất thường dựa trên phân nhóm .................................17

1.4.

Kỹ thuật phát hiện bất thường bằng thống kê ..........................................19

1.5.

Các thông tin kỹ thuật lý thuyết phát hiện bất thường .............................21

1.6.

Kỹ thuật phát hiện bất thường dựa trên phân tích phổ .............................23

2. Phát hiện bất thường theo mơ hình cân bằng ..................................................25
2.1.

Xác định vấn đề ........................................................................................25

2.2.


Cơ sở dữ liệu và bất thường .....................................................................28

2.3. Thuật toán phát hiện ....................................................................................30
2.4. Khảo sát các khoảng thời gian và các khung thời gian của tính dừng ........32
2.5. Đánh giá ......................................................................................................33
3. Kỹ thuật bắt gói tin .........................................................................................35
3.1. Tổng quan về bắt gói tin ..............................................................................35
3.2. Cách thức hoạt động ....................................................................................37
4. Các nghiên cứu liên quan ................................................................................41
4.1. Phịng chống sniffer....................................................................................41
CHƯƠNG II. XÂY DỰNG CHƯƠNG TRÌNH .......................................................43
1. Pcap – Mức network adapter ..........................................................................44
2. Winpcap ..........................................................................................................44
2.1. Khái niệm ....................................................................................................44

Trang 1


2.2. Làm việc với winpcap .................................................................................46
3. Thực hiện chương trình ...................................................................................47
3.1. Bắt gói tin ....................................................................................................48
3.2. Tách phần Header ........................................................................................48
3.3. Phân tích tổng hợp Header .........................................................................49
3.4. Hiển thị, thống kê và báo cáo ......................................................................49
4. Giao diện .........................................................................................................49
Chương III. THỰC HIỆN ĐÁNH GIÁ ....................................................................53
1. Thu thập dữ liệu với các thông tin lưu lượng thực nghiệm ............................53
2. Áp dụng cơng thức tính tốn của mơ hình cân bằng vào dữ liệu chuẩn của
MAWI....................................................................................................................54

3. Kết quả khi chạy chương trình ........................................................................56
4. So sánh với kết quả của MAWI ......................................................................58
Kết luận .....................................................................................................................59
TÀI LIỆU THAM KHẢO .........................................................................................59

Trang 2


DANH MỤC CÁC HÌNH
Hình 1. Các thành phần chính liên kết với một kỹ thuật phát hiện bất thường. .......13
Hình 2. Các thơng số mang đặc tính thống kê của một gói tin trên mạng ...............26
Hình 3. Quy mơ thời gian của tính dừng ..................................................................33
Hình 4. 512 byte dữ liệu của một gói tin Ethernet ở dạng Hex ................................38
Hình 5. Thơng tin trên gói tin sau khi phân tích .......................................................40
Hình 6. Cơ chế hoạt động của WinPcap ...................................................................46
Hình 7. Mô hình chung của chương trình xử lý ........................................................48
Hình 8. Giao diện chính của chương trình ...............................................................50
Hình 9. Danh sách card mạng ..................................................................................50
Hình 10. Capture gói với thời gian nhất định (20 giây) và lưu vào Packet.dump ...51
Hình 11. Phân tích tập tin Packet.dump ...................................................................51
Hình 12. Thông tin được in ra tệp tin văn bản..........................................................52
Hình 13. Mối quan hệ giữa thời gian bin và lưu lượng trung bình tương ứng ........56
Hình 14. So sánh kết quả phát hiện bất thường trong một số tập tin .......................58

Trang 3


DANH MỤC CÁC BẢNG

Bảng 1. Một số thông tin dấu vết lưu lượng lấy từ MAWI ........................................54

Bảng 2. Thông tin trung bình lấy từ bảng 1 ..............................................................54
Bảng 3. Kết quả tính tốn áp dụng mơ hình cân bằng..............................................55
Bảng 4. Kết quả thu được khi phân tích gói tin với mơ hình cân bằng ....................57

Trang 4


DANH MỤC CÁC TỪ VIẾT TẮT
TỪ VIẾT

ĐẦY ĐỦ
Ý NGHĨA
Density-based spatial
Một thuật toán phân cụm dữ liệu của Martin
clustering of
DBSCAN
Ester, Hans-Peter Kriegel, Jörg Sander và
applications with
Xiaowei Xu đề xuất vào năm 1996.
noise
Robust Clustering
Thuật tốn phân cụm đó thuộc một nhóm của
ROCK
using links
thuật toán phân cụm phân cấp agglomerative.
Shared Nearest
Một phương pháp khác để xác định sự giống nhau
SNN
Neighbors
giữa một cặp điểm gần nhau nhất.

Một loại mạng noron nhân tạo được đào tạo sử
dụng học không giám sát để sản xuất một (thường
SOM Self-Organizing Maps là hai chiều), đại diện rời rạc cho chiều không
gian đầu vào thấp của các mẫu huấn luyện, được
gọi là một bản đồ.
Phương pháp lặp để tìm kiếm khả năng tối đa
hoặc tối đa một hậu nghiệm ước lượng các tham
Expectation
EM
số trong mơ hình thống kê, nơi mà các mơ hình
Maximization
phụ thuộc vào các biến tiềm ẩn không quan sát
được.
Cluster-Based Local Một biện pháp được thiết kế để xác định ý nghĩa
CBLOF
Outlier Factor
vật lý của một giá trị.
Một quy trình thống kê có sử dụng một chuyển
đổi trực giao để chuyển đổi một tập hợp các quan
Principal Component
PCA
sát của các biến thể tương quan vào một tập hợp
Analysis
các giá trị của các biến khơng tương quan tuyến
tính.
Một thừa số của một ma trận thực và phức tạp,
Singular Value
SVD
với nhiều ứng dụng hữu ích trong xử lý tín hiệu
Decomposition

và thống kê.
Widely Integrated
WIDE
Distributed
Một dự án Internet tại Nhật Bản.
Environment
Transmission Control
TCP
Giao thức điều khiển giao vận.
Protocol

Trang 5


LỜI CẢM ƠN
Lời đầu tiên, tôi xin chân thành cảm ơn PGS.TS Ngô Hồng Sơn – giảng viên bộ
môn Truyền thơng và Mạng máy tính và NCS Lê Hồn – đã hết sức quan tâm, tận
tình giúp đỡ cũng như chỉ bảo, định hướng và tạo mọi điều kiện thuận lợi nhất giúp
tơi hồn thành luận văn của mình.
Tơi cũng xin cảm ơn các thầy giáo, cô giáo trong trường Đại học Bách Khoa Hà
Nội, Viện Đào tạo Sau đại học, đặc biệt là các thầy cô giáo của Viện Cơng nghệ thơng
tin và Truyền thơng đã hết lịng dạy bảo, truyền đạt những kiến thức kinh nghiệm cho
tôi trong suốt thời gian học tập ở bậc Cao học.
Cuối cùng tôi xin được gửi lời cảm ơn sâu sắc nhất tới gia đình và người thân đã
hết lịng ủng hộ, khích lệ tinh thần và ln động viên tơi vào những lúc khó khăn nhất
để tơi có thêm động lực hồn thành luận văn này.

LỜI CAM ĐOAN
Tơi – Lương Quốc Trung – xin cam đoan kết quả đạt được trong luận văn là sản
phẩm nghiên cứu, tìm hiểu của cá nhân tơi và giảng viên hướng dẫn. Trong tồn bộ

nội dung của luận văn, những điều được trình bày hoặc là của cá nhân tôi hoặc là
được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ
rõ ràng và được trích dẫn hợp pháp.
Tơi xin hồn tồn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định
cho lời cam đoan của mình.
Hà Nội, tháng 4 năm 2015
Tác giả Luận văn Thạc sỹ

Lương Quốc Trung

Trang 6


TĨM TẮT
Cơng nghệ thơng tin và Internet phát triển dẫn đến việc trao đổi thông tin trên
Internet ngày một nhiều hơn và có nhiều thơng tin quan trọng được truyền đi trên
mạng, điều này đặt ra nhiều vấn đề quan trọng về an ninh mạng và an toàn trong
truyền tin để ngăn chặn rò rỉ hoặc ngăn chặn truy cập trái phép vào các dữ liệu quan
trọng, gây thiệt hại về kinh tế. Quản lý băng thông để tăng khả năng đáp ứng thông
tin, giao dịch với khách hàng và tránh ùn tắc trên mạng. Vì vậy, việc phân tích lưu
lượng mạng Internet là điều cần thiết. Từ việc phân tích lưu lượng mạng Internet, ta
sẽ phát hiện ra những bất thường trên mạng.
Có rất nhiều phương pháp phát hiện bất thường dựa trên các phân tích lưu
lượng mạng. Trong phạm vi của đề tài này sẽ tập trung vào phân tích lưu lượng mạng
Internet bằng phương pháp phát hiện bất thường dựa trên mơ hình cân bằng. Ưu điểm
lớn nhất của phương pháp này so với các phương pháp khác là khơng địi hỏi q
trình tạo dữ liệu giúp tiết kiệm thời gian phát hiện với độ chính xác cao hơn so với
các phương pháp khác. Ngoài ra, trong đề tài này, chúng tơi sẽ phát triển một chương
trình đơn giản áp dụng cho mơ hình cân bằng để phát hiện bất thường. Chương trình
sẽ phân tích các gói dữ liệu bằng mơ hình cân bằng. Từ đó rút ra những kết luận và

đánh giá những ưu điểm, nhược điểm và hiệu quả ứng dụng của mơ hình cân bằng so
với các phương pháp khác.

Trang 7


GIỚI THIỆU
Sự bùng nổ của cơng nghệ thơng tin có tác động sâu sắc đến mọi lĩnh vực của
cuộc sống. Đặc biệt với sự phát triển của Internet, rất nhiều dịch vụ trực tuyến cũng
như sự phát triển mạnh mẽ của các dịch vụ thương mại điện tử, thanh toán trực tuyến
... Internet mang đến cách thức mới để truy cập và chia sẻ, khai thác thơng tin, vì vậy
vấn đề an tồn và an ninh thơng tin mạng chính là một thách thức. Thông tin trao đổi
qua mạng nếu máy tính khơng được bảo vệ có thể sẽ bị truy cập trái phép để lấy cắp
thơng tin và có thể thay đổi các nội dung thông tin. Thông tin bị đánh cắp khơng chỉ
ảnh hưởng lợi ích cá nhân mà có thể cịn ảnh hưởng đến cả lợi ích quốc gia và cho
thấy những hạn chế của các phương pháp bảo mật hiện nay, điều này nói lên sự cần
thiết cho các hệ thống phát hiện xâm nhập cho phép phát hiện các phương thức tấn
công mới dựa trên phân tích lưu lượng Internet để phát hiện bất thường.
MỤC TIÊU NGHIÊN CỨU

Mục tiêu chính của đề tài là để tìm hiểu về các phương pháp phân tích lưu
lượng Internet để phát hiện bất thường, từ đó thử nghiệm cách tiếp cận phát triển
chương trình phân tích lưu lượng mạng bằng cách phân tích các gói tin đã bị bắt và
đánh giá của các chuyên gia trước đó.
Trong phạm vi của đề tài này, chúng tơi tìm hiểu các phương pháp phân tích
lưu lượng Internet trong đó tập trung phát hiện bất thường dựa trên mơ hình cân bằng.
Ưu điểm lớn nhất của phương pháp này so với các phương pháp khác đó là khơng
địi hỏi q trình học dữ liệu giúp tiết kiệm thời gian đưa ra kết quả chính xác.

TĨM TẮT NỘI DUNG


Trang 8




Chương I. Cơ sở lý thuyết

Trong chương này, chúng tôi sẽ trình bày một cái nhìn tổng quan của hầu hết các
phương pháp để phát hiện một số loại bất thường bao gồm định nghĩa, phân loại, giả
định, phương pháp tính tốn (computational complexity), những ưu và nhược điểm
của từng loại. Phương pháp phát hiện bất thường bằng phương pháp thống kê thơng
qua mơ hình cân bằng. Các nghiên cứu liên quan.


Chương II. Xây dựng chương trình

Cài đặt chương trình thí điểm, đưa ra các kết quả đạt được trong chương trình thử
nghiệm.


Chương III. Thực hiện đánh giá

Đánh giá kết quả thu được trong chương II, trong đó bao gồm các đề xuất để cải thiện
chương trình.

Trang 9


CHƯƠNG I. CƠ SỞ LÝ THUYẾT

1. Bất thường và Phát hiện bất thường
1.1. Giới thiệu
Phát hiện bất thường đề cập đến các vấn đề của việc tìm kiếm các mẫu trong
dữ liệu mà không phù hợp với hành vi dự kiến. Những mơ hình khơng phù hợp thường
được gọi là dị thường, giá trị ngoại lai, quan sát nghịch, trường hợp ngoại lệ, quang
sai, bất ngờ, đặc thù, hoặc tạp chất trong các lĩnh vực ứng dụng khác nhau. Trong số
này, bất thường và sự chênh lệch là hai thuật ngữ được sử dụng phổ biến nhất là trong
bối cảnh phát hiện bất thường; đôi khi thay thế cho nhau. Phát hiện bất thường sử
dụng rộng rãi trong một loạt các ứng dụng như phát hiện gian lận thẻ tín dụng, bảo
hiểm, chăm sóc sức khỏe, phát hiện xâm nhập trong an ninh mạng, phát hiện lỗi trong
hệ thống an toàn quan trọng, và giám sát các hoạt động quân sự của đối phương.
Tầm quan trọng của phát hiện bất thường trong thực tế là do bất thường trong
dữ liệu có biến dạng đáng kể, thường xuyên thay đổi, giúp xử lý thông tin trong một
loạt các lĩnh vực ứng dụng. Phát hiện giá trị ngoại lai hoặc bất thường trong các dữ
liệu đã được nghiên cứu trong cộng đồng thống kê vào đầu thế kỷ 19 [Edgeworth
1887] . Theo thời gian, một loạt các kỹ thuật phát hiện bất thường đã được phát triển
trong một số nhóm nghiên cứu. Rất nhiều những kỹ thuật này đã được phát triển một
cách đặc biệt cho các lĩnh vực ứng dụng nhất định. Chương này sẽ cố gắng để cung
cấp một cái nhìn tổng quan và tồn diện cấu trúc của các nghiên cứu về phát hiện bất
thường.
1.1.1. Bất thường là gì
Bất thường là các mẫu trong dữ liệu mà không phù hợp với một khái niệm
được xác định rõ ràng là hành vi bình thường. Bất thường có thể được gây ra trong
các dữ liệu cho một loạt các lý do, như các hành động cố ý phá hoại, ví dụ: gian lận
thẻ tín dụng, xâm nhập mạng, hoạt động khủng bố hoặc phá hủy hệ thống, tuy nhiên
tất cả những lý do có đặc điểm chung là chúng đáng để ta quan tâm và phân tích. Các

Trang 10



thơng tin liên quan của dị thường là một tính năng quan trọng của phát hiện bất
thường.
1.1.2 Thách thức
Ở một mức độ chung, một sự bất thường được định nghĩa như là một mơ hình
mà khơng phù hợp với hành vi dự kiến thông thường. Một cách tiếp cận phát hiện bất
thường đơn giản, là để xác định một khu vực đại diện cho hành vi bình thường và xác
định bất kỳ quan sát trong các dữ liệu mà không thuộc khu vực bình thường này là
một sự bất thường. Tuy nhiên một số yếu tố làm cho cách tiếp cận này tưởng như đơn
giản nhưng lại rất khó khăn:


Xác định một khu vực bình thường bao gồm tất cả các hành vi có thể bình
thường là rất khó khăn. Ngồi ra, ranh giới giữa hành vi bình thường và bất
thường thường là khơng chính xác. Vì vậy, một quan sát bất thường nằm gần
ranh giới có thể là bình thường, và ngược lại.



Khi bất thường là kết quả của các hành động độc hại, những thông tin nguy
hại thường thích ứng để làm cho các quan sát bất thường xuất hiện bình
thường, do đó khiến cho cơng việc xác định hành vi bình thường khó khăn
hơn.



Trong nhiều lĩnh vực hành vi bình thường ln tiến triển và một khái niệm
hiện tại của hành vi bình thường có thể khơng có đủ đại diện trong tương lai.




Các khái niệm chính xác của một sự bất thường là khác nhau cho các lĩnh vực
ứng dụng khác nhau. Ví dụ, trong lĩnh vực y tế một sự sai lệch nhỏ từ bình
thường (EEG, biến động về nhiệt độ cơ thể) có thể là một sự bất thường, trong
khi độ lệch tương tự trong lĩnh vực thị trường chứng khốn (ví dụ, biến động
về giá trị của một cổ phiếu) có thể được coi là bình thường. Vì vậy việc áp
dụng cùng một kỹ thuật cho các lĩnh vực khác nhau là không hề đơn giản.

Trang 11




Dữ liệu sẵn có phục vụ cho q trình học/ kiểm chứng của các mơ hình là một
vấn đề lớn trong các kỹ thuật phát hiện bất thường.



Thường thì dữ liệu có chứa nhiễu và nhiễu này thường có xu hướng tương tự
như các dị thường thực tế và do đó rất khó để phân biệt và loại bỏ.
Do những thách thức này, các vấn đề phát hiện bất thường, ở dạng chung nhất

của nó, khơng phải dễ giải quyết. Trong thực tế, hầu hết các kỹ thuật phát hiện bất
thường hiện nay đều giải quyết một trường hợp cụ thể của vấn đề. Và như vậy, việc
xây dựng được tạo ra bởi các yếu tố khác nhau như bản chất của dữ liệu, dữ liệu dán
nhãn sẵn, loại bất thường được phát hiện. Thông thường, những yếu tố này được xác
định bởi các lĩnh vực ứng dụng, trong đó bất thường cần phải được phát hiện. Do đó
các nhà nghiên cứu đã áp dụng các khái niệm từ những lĩnh vực khác nhau như thống
kê, học máy, khai thác dữ liệu, lý thuyết thơng tin, lý thuyết phân tích phổ và đã áp
dụng chúng vào trường hợp vấn đề cụ thể. Hình 1 cho thấy các thành phần quan trọng
liên quan đến bất kỳ kỹ thuật phát hiện bất thường nào.


Trang 12


Hình 1. Các thành phần chính liên kết với một kỹ thuật phát hiện bất thường.
1.1.3 Nhãn dữ liệu
Các nhãn kết hợp với một trường dữ liệu biểu thị cho dù nó là bình thường hay
bất thường. Cần lưu ý rằng việc có được dữ liệu dán nhãn chính xác cũng như các đại
diện của tất cả các loại hành vi thường rất tốn kém. Ghi nhãn thường được thực hiện
bằng tay nên việc này mất rất nhiều công sức do đó việc tập hợp những hệ thống dữ
liệu dán nhãn sẵn là rất cần thiết. Thông thường, nhận được một tập nhãn của trường
dữ liệu bất thường bao gồm tất cả các loại có thể của hành vi bất thường khó khăn
hơn so với việc dán nhãn cho hành vi bình thường. Hơn nữa, những hành vi bất
thường thường biến đổi trong tự nhiên, ví dụ, các loại mới của các dị thường có thể
phát sinh, mà khơng có nhãn dữ liệu. Trong một số trường hợp, chẳng hạn như an
tồn hàng khơng, trường hợp bất thường sẽ tạo ra thảm họa và do đó rất hiếm có nhãn
cho các sự kiện bất thường này.

Trang 13


Căn cứ vào mức độ các nhãn được có sẵn, kỹ thuật phát hiện bất thường có
thể hoạt động trong một trong ba phương thức sau đây:
Giám sát phát hiện bất thường (Supervised Anomaly Detection). Kỹ thuật được
đào tạo trong chế độ giám sát giả định dữ liệu sẵn có của một tập dữ liệu huấn luyện
đã dán nhãn cho các trường hợp bình thường cũng như các trường hợp bất thường.
Một cách tiếp cận điển hình trong trường hợp này là xây dựng một mơ hình dự đốn
cho các trường hợp bất thường so với bình thường. Các dữ liệu được so sánh với các
mơ hình để xác định lớp nó thuộc về. Có hai vấn đề chính phát sinh trong giám sát
phát hiện bất thường. Thứ nhất, các trường hợp bất thường là rất ít so với các trường

hợp bình thường trong dữ liệu học được. Các vấn đề phát sinh do sự phân bố lớp mất
cân bằng đã được giải quyết trong các tài liệu khai thác dữ liệu và dữ liệu học máy
[Joshi et al. 2001, 2002; Chawla et al. 2004; Phua et al. 2004; Weiss and Hirsh 1998;
Vilalta and Ma 2002]. Thứ hai, lấy nhãn chính xác và đại diện, đặc biệt là cho các lớp
bất thường thường là một thử thách lớn. Một số kỹ thuật đã sử dụng phương pháp
thêm các dị thường nhân tạo vào một dữ liệu bình thường thiết lập để có được một
tập dữ liệu huấn luyện gắn nhãn [Theiler and Cai. 2003; Abe et al. 2006; Steinwart et
al. 2005]. Khác với hai vấn đề này, các vấn đề phát hiện bất thường giám sát là tương
tự để xây dựng mơ hình dự báo. Do đó, chúng tơi sẽ khơng nói đến các kỹ thuật này.
Bán giám sát phát hiện bất thường (Semi supervised Anomaly Detection). Các
kỹ thuật hoạt động trong một chế độ bán giám sát, giả định rằng dữ liệu huấn luyện
đã được dán nhãn chỉ cho các lớp dữ liệu bình thường. Vì họ khơng cần nhãn cho các
lớp dữ liệu bất thường nên chúng được áp dụng rộng rãi hơn so với các kỹ thuật giám
sát khác. Các cách tiếp cận điển hình được sử dụng trong kỹ thuật này là xây dựng
một mơ hình cho các lớp tương ứng với hành vi bình thường, và sử dụng các mơ hình
để xác định bất thường trong các dữ liệu thử nghiệm. Một số hạn chế trong các kỹ
thuật phát hiện bất thường trên là tính sẵn sàng của các trường hợp bất thường chỉ
dùng cho đào tạo [Dasgupta và Nino 2000; Dasgupta and Majumdar 2002; Forrest et
al. 1999]. Kỹ thuật như vậy thường không được sử dụng, chủ yếu là bởi vì nó khó tạo

Trang 14


ra được một tập dữ liệu huấn luyện bao gồm tất cả các hành vi bất thường có thể xảy
ra trong các dữ liệu.
Phát hiện bất thường không giám sát (Unsupervised Anomaly Detection). Các
kỹ thuật hoạt động trong chế độ không giám sát không yêu cầu dữ liệu huấn luyện do
đó nó được áp dụng rộng rãi nhất. Các kỹ thuật trong phương pháp này làm cho các
giả định rằng các trường hợp bình thường là thường xuyên hơn so với các trường hợp
bất thường trong các dữ liệu thử nghiệm. Nếu giả định này là không đúng so với thực

tế thì kỹ thuật này có xác xuất bị sai khá lớn.
Nhiều kỹ thuật bán giám sát có thể được điều chỉnh để hoạt động trong một
chế độ không giám sát bằng cách sử dụng một mẫu của các dữ liệu khơng có nhãn
thiết lập như là dữ liệu huấn luyện. Như vậy giả định rằng các dữ liệu thử nghiệm có
chứa rất ít bất thường và các mơ hình trong quá trình đào tạo là đủ linh hoạt để thể
hiện một vài bất thường.
1.2. Phân loại dựa trên các kỹ thuật phát hiện bất thường
Phân loại [Tan et al. 2005; Duda et al. 2000] được sử dụng để tìm hiểu một
mơ hình từ một tập hợp các dữ liệu đã được dán nhãn sau đó phân loại mỗi trường
hợp thử nghiệm vào các lớp khác nhau bằng cách sử dụng mơ hình học. Kỹ thuật phát
hiện bất thường phân loại dựa trên hoạt động bao gồm hai giai đoạn. Giai đoạn đào
tạo phân lớp sử dụng các dữ liệu đào tạo nhãn có sẵn. Giai đoạn thử nghiệm phân loại
xem trường hợp thử nghiệm là bình thường hay bất thường bằng cách sử dụng trình
phân loại.
Phân loại dựa trên các kỹ thuật phát hiện bất thường hoạt động theo các giả
định chung sau đây:
Giả thuyết. Một phân loại có thể phân biệt giữa các lớp bình thường và bất
thường có thể được học trong khơng gian đặc trưng nhất định. Dựa trên nhãn có sẵn
cho các giai đoạn huấn luyện, kỹ thuật phát hiện bất thường phân loại dựa trên giả

Trang 15


thuyết có thể được chia thành hai loại lớn: Kỹ thuật phát hiện bất thường đa lớp và
Kỹ thuật phát hiện bất thường đơn lớp.
Kỹ thuật phát hiện bất thường đa lớp dựa trên phát hiện bất thường giả định
rằng dữ liệu huấn luyện bao gồm các trường hợp dán nhãn thuộc nhiều lớp thông
thường [Stefano et al. 2000; Barbara et al. 2001b]. Kỹ thuật phát hiện bất thường như
dạy một phân loại để phân biệt giữa mỗi lớp bình thường và phần còn lại của lớp.
Phân loại dựa trên các kỹ thuật phát hiện bất thường đơn lớp giả định rằng tất

cả các trường đào tạo chỉ có một nhãn lớp. Kỹ thuật như học một ranh giới phân biệt
xung quanh các trường hợp bình thường bằng cách sử dụng một thuật toán phân loại
một lớp. Bất kỳ trường hợp nào kiểm tra mà dữ liệu đó khơng nằm trong ranh giới
đã học được là bất thường.
Độ phức tạp tính tốn. Sự phức tạp tính tốn của các kỹ thuật phân loại dựa
trên phụ thuộc vào các thuật toán phân loại được sử dụng. Đối với một cuộc thảo luận
về sự phức tạp của phân lớp đào tạo, [Kearns 1990]. Giai đoạn thử nghiệm của kỹ
thuật phân loại thường rất nhanh khi sử dụng mơ hình để phân loại.
Ưu điểm và nhược điểm của kỹ thuật phân loại .
Những ưu điểm của kỹ thuật phân loại :


Phân loại dựa trên cơ sở kỹ thuật, đặc biệt là các kỹ thuật đa lớp, có thể sử
dụng các thuật tốn mạnh có thể phân biệt giữa các trường thuộc các lớp khác
nhau.



Giai đoạn thử nghiệm các kỹ thuật phân loại cơ sở diễn ra rất nhanh, vì mỗi
trường hợp thử nghiệm cần được so sánh với các mơ hình đã được tính tốn
trước.

Những nhược điểm của kỹ thuật phân loại :

Trang 16




Kỹ thuật phân loại cơ sở đa lớp dựa vào sự sẵn có của các nhãn chính xác cho

các lớp với giá trị bình thường khác nhau thường là khơng thể có điều này.



Kỹ thuật phân loại cơ sở dựa trên phương pháp gán nhãn cho mỗi trường hợp
kiểm tra, cũng có thể trở thành một bất lợi khi một số điểm bất thường có ý
nghĩa trong các trường hợp thử nghiệm.

1.3. Kỹ thuật phát hiện bất thường dựa trên phân nhóm
Phân nhóm (Clustering) [Jain and Dubes 1988; Tan et al. 2005] được sử dụng
để nhóm các trường dữ liệu tương tự thành các cụm. Phân nhóm chủ yếu là một kỹ
thuật khơng có giám sát dù phân nhóm bán giám sát (semisupervised) [Basu et al.
2004] cũng mới được khám phá gần đây. Mặc dù nhóm và phát hiện bất thường về
cơ bản là khác nhau, nhưng một số kỹ thuật phát hiện bất thường dựa trên phân nhóm
đã được phát triển. Kỹ thuật phát hiện bất thường dựa trên phân nhóm có thể được
nhóm lại thành ba loại.
Các loại đầu tiên của kỹ thuật phân nhóm dựa trên dựa trên giả định sau đây:
Giả thuyết. Trường hợp dữ liệu bình thường thuộc về một cụm trong các dữ
liệu, trong khi bất thường không thuộc về bất cứ cụm nào.
Kỹ thuật dựa trên giả định này áp dụng một thuật tốn phân nhóm dựa trên các
dữ liệu được biết đến với thiết lập và tuyên bố bất kỳ trường hợp dữ liệu không thuộc
về bất cứ cụm nào là bất thường. Một số thuật tốn phân cụm khơng buộc mỗi trường
hợp dữ liệu thuộc về một cụm, như DBSCAN [Ester et al. 1996], ROCK [Guha et al.
2000], và SNN phân nhóm [ERT oz et al. 2003] có thể được sử dụng. Các thuật toán
findout [Yu et al. 2002] là một phần mở rộng của thuật toán WaveCluster
[Sheikholeslami et al. 1998], trong đó các cụm phát hiện được loại bỏ từ các dữ liệu
và các trường hợp còn lại được khai báo là bất thường.

Trang 17



Một bất lợi của kỹ thuật này là chúng không được tối ưu hóa để tìm bất thường,
vì mục đích chính của thuật tốn phân nhóm cơ bản là tìm.
Loại thứ hai của các kỹ thuật phân nhóm dựa trên dựa trên giả định sau đây:
Giả thuyết. Bình thường các trường hợp dữ liệu nằm gần cụm trọng tâm gần
nhất của chúng, trong khi bất thường ở xa trung tâm cụm .
Kỹ thuật dựa trên giả định này bao gồm hai bước. Trong bước đầu tiên, các dữ
liệu được nhóm sử dụng một thuật toán phân cụm. Trong bước thứ hai, dữ liệu cho
mỗi trường hợp, khoảng cách của nó tới cụm trọng tâm gần nhất của nó được tính
như điểm bất thường của nó.
Lưu ý rằng nếu các dị thường trong cụm mẫu dữ liệu của mình, những kỹ thuật
này sẽ không thể phát hiện dị thường như vậy. Để giải quyết vấn đề này, loại thứ ba
về các kỹ thuật phân nhóm dựa trên đã được đề xuất, dựa trên các giả định sau đây:
Giả thiết. Bình thường các trường hợp dữ liệu thuộc về cụm lớn và dày đặc,
trong khi bất thường hoặc thuộc về cụm nhỏ hoặc thưa thớt.
Kỹ thuật dựa trên giả định này tuyên bố các trường hợp thuộc cụm có kích
thước và / hoặc mật độ dưới ngưỡng, là bất thường.
Ưu điểm và nhược điểm của kỹ thuật phân nhóm
Các ưu điểm của kỹ thuật phân nhóm như sau:


Kỹ thuật Clustering trên có thể hoạt động ở chế độ không giám sát.



Kỹ thuật như vậy thường có thể được thích nghi với các kiểu dữ liệu phức tạp
khác bằng cách đơn giản là đưa vào một thuật tốn phân nhóm mà có thể xử
lý các loại dữ liệu cụ thể.

Trang 18





Giai đoạn thử nghiệm các kỹ thuật phân nhóm là nhanh vì số lượng các cụm
trong mỗi trường hợp thử nghiệm cần được so sánh là một hằng số ít.

Những nhược điểm của kỹ thuật phân nhóm như sau:


Thực hiện các kỹ thuật phân nhóm phụ thuộc rất nhiều vào tính hiệu quả của
thuật tốn phân nhóm trong việc nắm bắt cấu trúc nhóm các trường hợp bình
thường.



Nhiều kỹ thuật phát hiện dị thường như là một sản phẩm phụ của nhóm, và do
đó khơng tối ưu hóa cho phát hiện bất thường.



Một số thuật tốn phân nhóm buộc mọi cá thể được gán cho một số cụm. Điều
này có thể dẫn đến bất thường bị gán cho một cụm lớn, do đó được coi là
trường hợp bình thường bằng các kỹ thuật hoạt động theo giả định rằng sự bất
thường không thuộc về bất cứ cụm lớn nào.



Một số kỹ thuật phân nhóm dựa trên chỉ có hiệu lực khi các dị thường khơng
hình thành các cụm lớn với nhau.




Các tính tốn phức tạp để phân nhóm các dữ liệu thường bị hiện tượng nút cổ
chai.

1.4. Kỹ thuật phát hiện bất thường bằng thống kê
Các nguyên tắc cơ bản của bất kỳ kỹ thuật phát hiện bất thường bằng thống kê
là: "Một sự bất thường là một quan sát mà bị nghi là một phần hoặc tồn bộ khơng
thích hợp vì nó khơng được tạo ra bởi các mơ hình ngẫu nhiên giả định" [Anscombe
and Guttman 1960]. Kỹ thuật phát hiện bất thường bằng thống kê dựa trên giả thiết
quan trọng sau đây:

Trang 19


Giả thiết. Trường hợp dữ liệu bình thường xảy ra trong khu vực xác suất cao
của một mơ hình ngẫu nhiên, trong khi bất thường xảy ra trong vùng xác suất thấp
của các mơ hình ngẫu nhiên.
Các kỹ thuật thống kê phù hợp với một mơ hình thống kê (thường cho hành vi
bình thường) để các dữ liệu nhất định và sau đó áp dụng một thử nghiệm suy luận
thống kê để xác định xem một thể vơ hình thuộc về mơ hình này hay khơng. Trường
hợp mà có một xác suất thấp được tạo ra từ các mẫu đã học được, dựa trên các số liệu
thống kê thử nghiệm đã áp dụng, được tuyên bố là bất thường. Cả hai tham số cũng
như kỹ thuật không tham số đã được áp dụng để phù hợp với mơ hình thống kê. Trong
khi kỹ thuật tham số giả những kiến thức cơ bản về sự phân bố và ước lượng các
thông số từ các dữ liệu nhất định.
Độ phức tạp trong tính tốn. Sự phức tạp trong tính tốn của các kỹ thuật phát
hiện bất thường bằng thống kê phụ thuộc vào bản chất của các mơ hình thống kê được
u cầu phải được trang bị trên các dữ liệu. Tham số phân phối duy nhất phù hợp từ

các họ theo hàm, ví dụ, phân phối Gaussian, Poisson, Multinomial, và như vậy,
thường là tuyến tính với kích thước dữ liệu cũng như số lượng các thuộc tính. Phân
phối phức tạp phù hợp (như mơ hình hỗn hợp, HMM, vv) sử dụng kỹ thuật ước lượng
lặp đi lặp lại như EM, cũng thường tuyến tính mỗi lần lặp lại, mặc dù chúng có thể
được làm chậm trong hội tụ phụ thuộc vào vấn đề chuẩn hội tụ. Kỹ thuật cốt lõi khả
năng có thể có độ phức tạp bậc hai về thời gian tính tốn và kích thước dữ liệu.
Ưu điểm và nhược điểm của kỹ thuật thống kê
Các ưu điểm của kỹ thuật thống kê là:


Nếu các giả định liên quan đến việc phân phối dữ liệu cơ bản là đúng, kỹ thuật
thống kê cung cấp một giải pháp hợp lý về mặt thống kê để phát hiện bất
thường.

Trang 20




Điểm số bất thường được cung cấp bởi một kỹ thuật thống kê gắn với một
khoảng tin cậy, có thể được sử dụng như thông tin bổ sung trong khi thực hiện
một quyết định liên quan đến bất kỳ trường hợp thử nghiệm nào.



Nếu các bước ước lượng phân phối rất linh hoạt trong dữ liệu, kỹ thuật thống
kê có thể hoạt động trong một mơi trường khơng có giám sát mà không cần
đến dữ liệu đã được dán nhãn trong quá trình học.

Những nhược điểm của kỹ thuật thống kê là:



Nhược điểm chính của kỹ thuật thống kê là họ dựa trên giả thuyết rằng dữ liệu
được tạo ra từ một phân bố cụ thể. Giả định này thường không giữ đúng, đặc
biệt cho không gian bộ dữ liệu thực.



Ngay cả khi giả định thống kê có thể được hợp lý hóa, có một số liệu thống kê
kiểm định giả thuyết rằng có thể được áp dụng để phát hiện dị thường; lựa
chọn các số liệu thống kê tốt nhất thường không phải là một nhiệm vụ dễ dàng
[Motulsky 1995].



Kỹ thuật biểu đồ là tương đối đơn giản để thực hiện, nhưng vấn đề quan trọng
của các kỹ thuật đó cho dữ liệu đa biến là nó khơng có khả năng nắm bắt các
mối tương tác giữa các thuộc tính khác nhau. Một sự bất thường có thể có
thuộc tính giá trị riêng rất thường xun, nhưng có sự kết hợp rất hiếm gặp,
tuy nhiên kỹ thuật biểu đồ dựa trên thuộc tính sẽ khơng thể phát hiện bất
thường như vậy.

1.5. Các thông tin kỹ thuật lý thuyết phát hiện bất thường
Thơng tin kỹ thuật phân tích nội dung thông tin của một tập hợp dữ liệu sử
dụng các thông tin giải pháp lý thuyết khác nhau như sự phức tạp mô tả
(Kolomogorov), mức độ hỗn loạn trong một tín hiệu lấy từ một sự kiện ngẫu nhiên
(Entropy). Kỹ thuật như vậy dựa trên giả thiết quan trọng sau đây:

Trang 21



Giả thiết. Dị thường trong dữ liệu gây ra bất thường trong những nội dung
thông tin của tập dữ liệu.
Cho C (D) biểu thị sự phức tạp của một tập dữ liệu cho trước, D. Một thông
tin cơ bản của lý thuyết kỹ thuật có thể được mơ tả như sau. Cho một tập dữ liệu D,
tìm tập con tối thiểu của các trường hợp, I , như vậy là C (D) - C (D - I) là tối đa. Tất
cả các trường hợp trong tập hợp con đó thu được, được coi là bất thường. Vấn đề giải
quyết bằng kỹ thuật cơ bản này là tìm một giải pháp tối ưu , mà khơng có một tối ưu
duy nhất, vì có hai mục tiêu khác nhau cần phải được tối ưu hóa.
Độ phức tạp trong tính tốn. Như đã đề cập trước đó, các thơng tin cơ bản kỹ
thuật phát hiện bất thường của lý thuyết có độ phức tạp theo hàm mũ, mặc dù kỹ thuật
tương đối đã được đề xuất rằng có độ phức tạp tuyến tính theo thời gian.
. Ưu điểm và nhược điểm của thông tin kỹ thuật lý thuyết
Những ưu điểm của thông tin kỹ thuật lý thuyết:


Chúng có thể hoạt động trong một mơi trường khơng có giám sát.



Chúng khơng thực hiện bất kỳ giả định về phân bố thống kê cơ bản cho các dữ
liệu.

Những nhược điểm của kỹ thuật thông tin lý thuyết:


Việc thực hiện các kỹ thuật phụ thuộc vào sự lựa chọn của các thông tin biện
pháp lý thuyết. Thơng thường, các biện pháp này có thể phát hiện sự hiện diện
của các dị thường chỉ khi có một số lượng lớn đáng kể các dị thường có mặt
trong dữ liệu.




Thông tin kỹ thuật lý thuyết áp dụng cho các trình tự, các bộ dữ liệu khơng
gian dựa trên kích thước của cấu trúc hạ tầng, mà thường dễ dàng có được.



Rất khó để kết hợp một số điểm bất thường với một trường hợp thử nghiệm
bằng cách sử dụng một thông tin kỹ thuật của lý thuyết.

Trang 22


1.6. Kỹ thuật phát hiện bất thường dựa trên phân tích phổ
Kỹ thuật phân tích phổ cố gắng tìm kiếm một tập gần đúng của các dữ liệu
bằng cách sử dụng kết hợp các thuộc tính thu được với số lượng lớn của các biến
trong dữ liệu. Kỹ thuật như vậy dựa trên giả định quan trọng sau đây:
Giả thiết. Dữ liệu có thể được nhúng vào một khơng gian con chiều thấp hơn,
trong đó các trường hợp bình thường và dị thường xuất hiện khác nhau đáng kể.
Do đó, cách tiếp cận chung được thông qua bởi các kỹ thuật phát hiện bất
thường phổ là để xác định không gian con như vậy (embeddings, Projections, vv),
trong đó các trường hợp bất thường có thể dễ dàng xác định [Agovic et al. 2007]. Kỹ
thuật như vậy có thể làm việc trong cả thiết lập không giám sát cũng như bán giám
sát.
Độ phức tạp trong tính tốn. Tiêu chuẩn kỹ thuật dựa trên PCA thường tuyến
tính với kích thước dữ liệu nhưng có cấp số nhân về kích thước. Kỹ thuật phi tuyến
có thể cải thiện mức độ phức tạp thời gian để được tuyến tính trong số chiều nhưng
đa thức trong số các thành phần chính [Gunter et al. 2007]. Kỹ thuật thực hiện các
SVD trên các dữ liệu thường có cấp số nhân trong kích thước dữ liệu.

Ưu điểm và nhược điểm của kỹ thuật phân tích phổ
Các ưu điểm của kỹ thuật phát hiện bất thường dựa trên phân tích phổ:


Kỹ thuật phân tích phổ tự động thực hiện giảm chiều và do đó rất thích hợp để
xử lý các bộ dữ liệu lớn. Hơn nữa, chúng cũng có thể được sử dụng như là
bước tiền xử lý tiếp theo áp dụng cho bất kỳ kỹ thuật phát hiện bất thường nào
tồn tại trong không gian chuyển đổi.



Kỹ thuật phân tích phổ có thể được sử dụng trong thiết lập khơng có giám sát.

Những nhược điểm của kỹ thuật phát hiện bất thường dựa trên phân tích phổ như sau:

Trang 23




Kỹ thuật phân tích phổ chỉ có ích nếu các trường hợp bình thường và bất
thường được phân chia và tồn tại trong các dự liệu kích thước nhỏ.



Kỹ thuật phân tích phổ thường có độ phức tạp tính tốn cao.

Trang 24