ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG

NGUYỄN VĂN DIỄN

NGHIÊN CỨU GIẢI PHÁP PHÁT HIỆN XÂM NHẬP MẠNG MÁY
TÍNH BẤT THƯỜNG DỰA TRÊN KHAI PHÁ DỮ LIỆU

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên - 2014
Số hóa bởi Trung tâm Học liệu

http://www.lrc-tnu.edu.vn/


i

LỜI CAM ĐOAN
Tôi xin cam đoan đề tài “Nghiên cứu Giải pháp phát hiện xâm nhập mạng máy
tính bất thường dựa trên Khai phá dữ liệu” là công trình nghiên cứu của riêng tôi.
Đề tài được hoàn thành dưới sự hướng dẫn của Thầy TS. Nguyễn Ngọc Cương.
Những kết quả nghiên cứu, thử nghiệm được thực hiện hoàn toàn khách quan
và trung thực. Các số liệu, kết quả trình bày trong luận văn là hoàn toàn trung thực
và chưa từng được công bố trong bất cứ công trình nào.
Các tài liệu tham khảo sử dụng trong luận văn đều được dẫn nguồn (có bảng
thống kê các tài liệu tham khảo) hoặc được sự đồng ý trực tếp của tác giả.
Nếu xảy ra bất cứ điều gì không đúng như những lời cam đoan trên, tôi xin
chịu hoàn toàn trách nhiệm.
Hà Nội, ngày 18 tháng 07 năm 2014
TÁC GIẢ

LỜI

CẢM

ƠN........................................................................................................................... ii DANH
MỤC TỪ VIẾT TẮT ..................................................................................................vi DANH
MỤC

BẢNG...............................................................................................................

vii

DANH MỤC HÌNH ..............................................................................................................
viii

MỞ

ĐẦU

...................................................................................................................................ix
TỔNG QUAN VỀ NHIỆM VỤ CỦA LUẬN VĂN ...............................................................xi
CHƯƠNG 1: HỆ THỐNG PHÁT HIỆN XÂM NHẬP MẠNG VÀ PHƯƠNG PHÁP PHÁT HIỆN XÂM
NHẬP MẠNG..........................................................................................1
1. 1

Hệ thống phát hiện xâm nhập mạng IDS (Intrusion Detection System) ............. 1

1.1.1.

Định nghĩa ...................................................................................................... 1


Phương pháp tiếp cận dựa trên trạng thái ................................................ 12

1.2.3

Phương pháp tiếp cận dựa trên hệ chuyên gia .......................................... 12

1.2.4

Phương pháp tiếp cận dựa trên khai phá dữ liệu ..................................... 13

1. 3

Khai phá dữ liệu trong IDS ................................................................................ 14

1.3.1

Định nghĩa khai phá dữ liệu........................................................................ 14


4

1.3.2

Nhiệm vụ của khai phá dữ liệu ................................................................... 16

1.3.3

Các loại dữ liệu được khai phá ................................................................... 17


2.2.1.

Một số thuật toán phát hiện dị biệt trong khai phá dữ liệu ..................... 30

2.2.2.

Mô hình phát hiện bất thường dựa trên kỹ thuật khai phá dữ liệu ........ 36

CHƯƠNG 3: ĐỀ XUẤT TRIỂN KHAI THỬ NGHIỆM HỆ THỐNG PHÁT HIỆN
XÂM NHẬP MẠNG.
..............................................................................................................42
3.1.

Bài toán phân cụm dữ liệu trong CSDL kết nối mạng .................................... 42

3.2.

Thuật toán sử dụng cho bài toán ứng dụng ...................................................... 42

3.3.

Đánh giá Thuật toán phân cụm ứng dụng trong bài toán ............................... 44

3.4.

Ứng dụng thuật toán phân cụm K-medoids trong KPDL ............................... 48

3.4.1.

Quy trình xử lý bài toán ứng dụng: ........................................................... 48

CSDL

Cơ sở dữ liệu

DdoS

Distributed Daniel of Servies

DOS

Daniel of Services

HIDS

Host Instrucsion Detection System

HTTP

Hypertext Markup Languge

ICMP

Internet Control Message Protocol

IDS

Intrucsion Detecton System IDDM

Intrucsion Detecton Data Mining IPS
Intrucsion Prevention System

UDP

User Datagram Protocol


vii

DANH MỤC BẢNG
Bảng 2.1: Danh sách các cảnh báo chưa rút gọn
Bảng 2.2: Danh sách các cảnh báo sau khi rút gọn
Bảng 3.1: Bảng thuộc tính CSDL mạng
Bảng 3.2: Thông tin chương trình cài đặt ứng dụng


8

DANH MỤC HÌNH
Hình 1.1: Mô hình IDS vật lý
Hình 1.2: Kiến trúc Modul trong IDS
Hình 1.3: Mô hình thu thập dữ liệu ngoài luồng
Hình 1.4: Mô hình thu thập dữ liệu trong luồng
Hình 1.5: Modul phân tích, phát hiện tấn công
Hình 1.6: Quá trình khám phá tri thức
Hình 2.1: Gán giá trị để lượng hóa các cuộc tấn công trên sơ đồ
Hình 2.2: Minh họa bài toán phát hiện phần tử dị biệt
Hình 2.3: Khoảng cách Reach – dist
Hình 2.4: Phương pháp LOF
Hình 2.5: Thuật toán LSC – Mine
Hình 2.6: Mô hình phát hiện bất thường sử dụng kỹ thuật KPDL
Hình 2.7: Mô hình Modul tổng hợp

Đã có nhiều hướng nghiên cứu và xây dựng hệ thống cảnh báo và thâm nhập
dựa trên các phương pháp thâm nhập như: phát hiện thâm nhập dựa vào luật;
kỹ thuật phân biệt ý định người dùng, phân tích trạng thái phiên, phương pháp
phân tích thống kê … Tuy nhiên đây là các phương pháp phát hiện xâm nhập dựa
trên các dấu hiệu bất thường. Tức là dựa trên các dấu hiệu của các vụ tấn công đã
biết, các phương pháp này phát hiện ra xâm nhập mạng bằng cách so sánh các giá
trị đặc tả với một dãy các ký tự tấn công được cung cấp bởi chuyên gia và được cập
nhật lại trong cơ sở dữ liệu. Điểm hạn chế của các phương pháp trên là chúng
không thể phát hiện ra các cuộc tấn công mới không có trong cơ sở dữ liệu. So với
các phương pháp trên thì phương pháp phân tích dựa trên kỹ thuật khai phá dữ
liệu có nhiều ưu điểm rõ rệt hơn. Phương pháp này có thể sử dụng với cơ sở dữ
liệu chứa nhiều nhiễu, dữ liệu không đầy đủ, biến đổi liên tục, đặc biệt phương
pháp này đòi hỏi mức độ sử dụng các chuyên gia không quá thường xuyên. Các ưu
điểm này đem lại


10

cho phương pháp sử dụng kỹ thuật khai phá dữ liệu có khả năng xử lý dữ liệu lớn,
sử dụng trong các hệ thống thời gian thực.
Đây là lý do để chúng tôi chọn đề tài “ Nghiên cứu giải pháp phát hiện xâm
nhập mạng máy tính bất thường dự trên khai phá dữ liệu”. Đề tài sẽ tập
trung nghiên cứu phương pháp phát hiện xâm nhập mạng máy tính bất thường
bằng kỹ thuật khai phá dữ liệu để phát hiện các hành vi xâm nhập một cách tự
động dựa trên dấu hiệu bất thường so với dữ liệu quá khứ.


11

TỔNG QUAN VỀ NHIỆM VỤ CỦA LUẬN VĂN

Hệ thống phát hiện xâm nhập mạng IDS (Intrusion Detection System)
1.1.1. Định nghĩa
Xâm nhập là một thuật ngữ dùng để chỉ các hành động đột nhập trái phép làm

ảnh hưởng tới hệ thống mạng hoặc các thiết bị máy tính điện tử của bạn.
Phát hiện xâm nhập là một tập hợp các kỹ thuật và phương pháp được sử
dụng để phát hiện các hành vi đáng ngờ ở cả trên mạng cũng như ở mức độ host.
Hệ thống phát hiện xâm nhập (IDS) là hệ thống có nhiệm vụ theo dõi, phát
hiện và (có thể) ngăn cản sự xâm nhập, cũng như các hành vi khai thác trái phép tài
nguyên của hệ thống được bảo vệ mà có thể dẫn đến việc làm tổn hại đến tính bảo
mật, tính toàn vẹn và tính sẵn sàng của hệ thống.
Như vậy, hệ thống phát hiện xâm nhập là một thành phần quan trọng trong
hệ thống bảo mật mạng, hệ thống này liên tục theo dõi các hoạt động diễn ra trong
mạng hay trên một máy nhất định, nó thu thập thông tin từ nhiều nguồn khác
nhau, phân tích, tổng hợp để tìm ra những hiểm họa hay những dấu hiệu có khả
năng đe dọa tính toàn vẹn, tính sẵn sàng hay tính xác thực của hệ thống, đồng thời
hệ thống cũng có thể đưa ra các phản ứng đối với mỗi hành vi hiểm họa phát hiện
được. Tất cả những thông tn thu thập được và các cơ chế phát hiện cũng như cơ
chế ngăn chặn hay cơ chế phản ứng đều phải tuân theo các chính sách bảo mật.
1.1.2. Vai trò, chức năng của IDS
- Phát hiện các nguy cơ tấn công và truy nhập trái phép
Đây là vai trò chính của một hệ thống phát hiện xâm nhập IDS, nó có nhiệm
vụ xác định những tấn công và truy nhập trái phép vào hệ thống mạng bên trong.
Hệ thống IDS có khả năng hỗ trợ phát hiện các nguy cơ an ninh đe dọa mạng mà
các hệ thống khác không có, kết hợp với hệ thống ngăn chặn xâm nhập IPS
(Intrusion


2


trung lưu trữ thông tn, dữ liệu do các bộ cảm ứng gửi về.
- Giao diện người dùng ( User Interface): giúp người quản trị mạng quản lý,
giám sát hệ thống.
1.1.4. Kiến trúc và hoạt động bên trong mô hình hệ thống IDS
Hệ thống phát hiện xâm nhập bao gồm 3 modul chính:
-

Modul thu thập thông tin, dữ liệu.

-

Modul phân tích, phát hiện tấn công.

-

Modul phản ứng.

Hình 1.2: Kiến trúc Modul trong IDS
+ Modul thu thập thông tin, dữ liệu: Modul này có nhiệm vụ thu thập các gói
tn trên mạng để đem phân tích. Trong hệ thống mạng thông thường IDS sẽ
được đặt ở vị trí mà ta cần giám sát.


4

Có hai mô hình chính để thu thập dữ liệu đó là : Mô hình ngoài luồng và Mô
hình trong luồng.
+ Mô hình thu thập dữ liệu ngoài luồng: Trong mô hình ngoài luồng không
can thiệp trực tếp vào luồng dữ liệu. Luồng dữ liệu vào ra hệ thống mạng sẽ được
sao một bản và được chuyển tới modul thu thập dữ liệu .

hoặc


6

cảnh báo các cuộc tấn công mới chưa có trong CSDL, chính vì vậy hệ thống luôn
phải cập nhật các mẫu tấn công mới.
Phát hiện tnh trạng bất thường (Anomaly detection models): hệ thống sẽ
thường xuyên lưu giữ các mô tả sơ lược về các quá trình hoạt động bình thường của
hệ thống. Khi có các cuộc tấn công xâm nhập gây ra các hoạt động bất bình thường
thì kỹ thuật này sẽ phát hiện ra các hoạt động bất bình thường dựa trên các phát
hiện bất thường nhờ: mức ngưỡng, phát hiện nhờ quá trình tự học, phát hiện dựa
trên bất thường về giao thức.
+ Cảnh báo: Quá trình này thực hiện sinh ra các cảnh báo tùy theo đặc điểm
và loại tấn công, xâm nhập mà hệ thống phát hiện được.
+ Modul phản ứng: Khi có dấu hiệu của sự tấn công hoặc xâm nhập, modul
phát hiện tấn công sẽ gửi tín hiệu báo hiệu sự tấn công hoặc xâm nhập đến modul
phản ứng, lúc này modul phản ứng gửi tín hiệu kích hoạt tường lửa để thực
hiện chức năng ngăn chặn cuộc tấn công hoặc cảnh báo tới người quản trị. Modul
phản ứng này tùy theo mỗi hệ thống thiết kế có các chức năng, phương pháp ngăn
chặn khác nhau.
1.1.5. Phân loại IDS
- Dựa trên phương thức phát hiện tấn công: bao gồm phát hiện lạm dụng và
phát hiện bất thường.
+ Phát hiện lạm dụng: thông thường còn có tên là phát hiện dựa trên dấu
hiệu. Phát hiện lạm dụng đòi hỏi những file mẫu của dấu hiệu để nhận dạng những
hành động xâm nhập. Những file mẫu của dấu hiệu sử dụng trong phương pháp
phát hiện lạm dụng phải được cập nhật thường xuyên.
Ưu điểm: có thể phát hiện và đưa ra cảnh báo chính xác cuộc tấn công
dựa trên sự so sánh tương xứng đối với bất kỳ dấu hiệu nào đã được định dạng

xác định những hoạt động bình thường. Bởi vì phát hiện dựa trên profile không
dựa trên những dấu hiệu đã biết, nó thực sự phù hợp cho việc phát hiện những
cuộc tấn công chưa hề được biết trước đây miễn là nó chệch khỏi profile bình
thường. Phát hiện


8

dựa trên profile được sử dụng để phát hiện những phương pháp tấn công mới
mà phát hiện bằng dấu hiệu không phát hiện được.
Nhược điểm: Khó khăn trong việc định nghĩa các hành động bình thường của
những profile nhóm người dùng, cũng như đảm bảo chất lượng của những profile
này. Dễ cảnh báo nhầm, gây ra sự phức tạp trong quá trình định nghĩa ngưỡng bình
thường và bất bình thường của từng profile và nhóm profile.
- Dựa trên phương thức bảo vệ: IDS được chia làm hai loại chính:
+ HIDS (Host Intrusion Detection System): triển khai trên máy trạm hoặc
server quan trọng, chỉ để bảo vệ riêng từng máy.
Ưu điểm: Phát hiện tốt các cuộc tấn công xâm nhập từ bên trong, phát
hiện dựa trên thông tn, dữ liệu trên Host.
Nhược điểm: Chỉ áp dụng được trong phạm vi một Host dẫn đến chi phí cao
và phải phụ thuộc nhiều vào hệ điều hành được cài đặt trên Host đó gây ra độ
phức tạp cao khi cài đặt và triển khai.
+ NIDS (Network Intrusion Detection System): đặt tại những điểm quan trọng
của hệ thống mạng, để phát hiện xâm nhập cho khu vực đó
Ưu điểm: Phát hiện tốt các cuộc tấn công xâm nhập từ bên ngoài, phát
hiện dựa trên thông tn, dữ liệu trên toàn bộ mạng. Tiết kiệm chi phí và dễ dàng
trong quá trình cài đặt và triển khai.
Nhược điểm: Khó tương thích với các Swich, router, hạn chế về hiệu năng vì
phải liên tục sử lý một lượng lớn thông tin, làm tăng lưu lượng mạng do các bộ
phận của IDS luôn phải thường xuyên trao đổi thông tn với nhau và thay đổi với

Asmodeus, … Việc thăm dò có thể thực hiện bằng cách “Ping” đến hệ thống cũng
như kiểm tra các cổng TCP và UDP để phát hiện ra các ứng dụng có những lỗi đã
được biết đến để tấn công hoặc xâm nhập.
Ta có thể sử dụng giải pháp của IDS như: Network-based IDS để phát hiện các
hành động xâm nhập bất hợp pháp này trước khi có sự xâm nhập xẩy
ra.
1.1.6.3. Tấn công vào mật mã (Password attack): là kiểu tấn công nhằm “ăn
cắp” các thông tn về User account, password của người sử dụng trên hệ
thống mạng, nhằm mang lại quyền hành và tính linh động cao nhất cho kẻ tấn
công để có


10

thể truy nhập tới mọi thông tn tại mọi thành phần trong mạng. Các hacker
thường sử dụng một chương trình đoán mã với thuật toán mã hóa chạy trên mạng,
cố gắng login vào các phần Share trên mạng. Các hacker thường tấn công
Password bằng một số phương pháp như: brute – force attack, chương trình
Trojan House, IP spoofing và packet snifer.
1.1.6.4. Tấn công chiếm đặc quyền (Privilege – grabbing): là dạng tấn công
nhằm mục đích đánh cắp dữ liệu, giành lấy một phiên giao dịch, phân tích trafic
trong mạng, từ chối dịch vụ, phá hỏng dữ liệu được truyền. Khi kẻ tấn công đã xâm
nhập được vào hệ thống, chúng sẽ chiếm quyền truy cập vào hệ thống. Đối với hệ
điều hành UNIX sẽ chiếm đặc quyền “root”, trong hệ điều hành Windows sẽ chiếm
đặc quyền “Administrator”, trong hệ điềi hành NetWare sẽ chiếm đặc quyền
“Supervisor”.
Một số kỹ thuật thường dùng cho việc tấn công chiếm đặc quyền: Đoán và bẻ
khóa của root hoặc administrator, gây tràn bộ đệm, khai thác registry của
Windows, truy nhập và khai thác console đặc quyền, thăm dò file và các lỗi của hệ
điều hành.

1. 2

Một số phương pháp phát hiện bất thường trong hệ thống IDS
1.2.1 Phương pháp tiếp cận dựa trên xác suất thống kê
Các phương pháp thống kê đo lường các hành vi của người dùng và của hệ

thống bằng một số các biến được lấy mẫu theo thời gian và xây dựng các profile
dựa trên các thuộc tính của hành vi bình thường. Các thông số theo dõi trên thực
tế sẽ được so sánh với các profile này, và các sai khác vượt qua một ngưỡng sẽ bị
coi là một bất thường.
Các hệ thống phát hiện bất thường như ADAM, NIDES, và SPADE có một
cách tếp cận trong đó hệ thống sẽ học một mô hình thống kê về lưu lượng bình
thường của mạng, và xem xét các sai khác so với mô hình này. Các mô hình thống
kê thường dựa trên sự phân bố của các thành phần như các địa chỉ IP nguồn và đích,
các cổng nguồn và đích trên mỗi giao tác (như các kết nối TCP, và đôi khi là các
gói tn UDP và ICMP). Các thành phần có xác suất càng nhỏ thì có mức độ bất
thường càng cao.
Các hệ thống phát hiện bất thường sử dụng các mô hình tần suất, trong đó xác
suất của một sự kiện đã được tính toán bằng tần suất trung bình của nó trong
quá trình huấn luyện dựa trên thời gian, trong đó xác suất của một sự kiện phụ
thuộc vào


12

thời điểm mà nó xảy ra lần cuối cùng. Đối với mỗi thuộc tính, chúng thu thập một
tập các giá trị cho phép, và sẽ coi các giá trị mới của thuộc tính đó là bất thường.
Một phương pháp tếp cận thống kê gần đây được đề nghị là việc thống kê mô
hình lưu lượng để phát hiện các tấn công loại mới trên mạng. Theo cách tếp cận
này, một mô hình hành vi của mạng được sử dụng để phát hiện một lượng lớn các

sự kiện an ninh nhạy cảm và xây dựng các luật để phát hiện các hành vi bất
thường. Nó sẽ kiểm tra các hành vi của người dùng theo một tập các luật mô tả
chính sách sử dụng bình thường của hệ thống, và sẽ kết luận các hành động không
phù hợp với các mẫu có thể chấp nhận được là bất thường.
Wisdom & Sense ( được phát triển tại phòng thí nghiệm Los Alamos Natonal)
phát hiện các bất thường có tính thống kê trong hành vi của người dùng. Đầu tên,
nó xây dựng một tập các luật mô tả một cách thống kê hành vi dựa trên việc ghi lại
các hành vi của người dùng theo một khoảng thời gian cho trước. Các chuỗi hành vi
nhỏ sau đó được so sánh với những luật này để phát hiện các hành vi mâu thuẫn.
Cơ sở tri thức luật được xây dựng lại một cách định kỳ để phù hợp với các mẫu sử
dụng mới.
1.2.4 Phương pháp tiếp cận dựa trên khai phá dữ liệu
Khai phá dữ liệu tập trung khai thác các thông tn hữu ích tềm tàng, chưa biết
trước từ các tập dữ liệu. Các hệ thống phát hiện xâm nhập có ứng dụng
phương pháp khai phá dữ liệu trong phát hiện bất thường là ADAM (Audit Data
Analysis and Mining, của Wu,2001, Barbara và cộng sự, 2001), IDDM (Intrusion
Detecton using Data Mining, của Abraham, 2001), và eBayes ( của Valdes và
Skinner,2000).
Trong cách tếp cận này, việc khai phá dữ liệu tìm kiếm các phiên kết nối và
nó khác so với cách tếp cận phát hiện bất thường dựa trên việc tìm kiếm thông tn
trên các gói tn riêng biệt. Phương pháp này sử dụng các công cụ và phương pháp
khai phá dữ liệu để phân biệt các phiên bất thường so với các phiên bình
thường theo cách sử dụng lặp đi lặp lại dữ liệu huấn luyện nó thu thập được như
một tham chiếu. Khai phá dữ liệu là một công nghệ có hiệu quả cao, mang lại khả
năng phát hiện các tấn công chưa biết và đã biết, nhưng lại khá phức tạp và đòi hỏi
giá thành cao.