Luận văn Phương pháp tối ưu đàn kiến để giải bài toán phát hiện xâm nhập
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
ĐÀO VĂN HẢI
PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN
ĐỂ GIẢI BÀI TOÁN PHÁT HIỆN XÂM NHẬP
Ngành:
Chuyên ngành: Khoa học máy tính
Mã số: 8480101.01
Công nghệ thông tin
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS.TS. Hoàng Xuân Huấn
Hà Nội, 2020
LỜI CẢM ƠN
Tôi xin gửi lời cảm ơn chân thành nhất tới PGS.TS. Hoàng Xuân Huấn,
người thầy đáng kính đã tận tình chỉ bảo, hướng dẫn tôi trong suốt quá trình tìm
hiểu, nghiên cứu và hoàn thiện luận văn. Thầy với nhiều năm nghiên cứu trong
lĩnh vực tối ưu hóa, với nhiều đề xuất, công trình được công nhận. Nghiên cứu
chuyên sâu về tối ưu hóa đàn kiến của thầy đã giúp tôi hiểu rõ những khó khăn
trong trong quá trình nghiên cứu tìm ra hướng giải quyết bài toán của mình. Thầy
cũng đưa ra những góp ý bổ ích, quý báu giúp cho tôi có thể hoàn thành quyển
luận văn này.
Tôi cũng xin được gửi lời cảm ơn sâu sắc đến TS.Trần Ngọc Hà người đã
giúp đỡ tôi trong quá trình viết luận văn và thực nghiệm chương trình.
Cuối cùng tôi xin được bày tỏ lòng biết ơn tới các thầy cô trường Đại học
Công nghệ đã tham gia giảng dạy và chia sẻ những kinh nghiệm quý báu cho tôi
trong suốt quá trình học. Tôi xin cảm ơn tới các thầy và các anh chị đã thường
xuyên giúp đỡ, trao đổi, góp ý về những vấn đề khoa học liên quan tới luận văn.
Hà Nội, tháng 7 năm 2020
HỌC VIÊN
ĐÀO VĂN HẢI
1
LỜI CAM ĐOAN
Tôi xin cam đoan rằng đây là công trình nghiên cứu của cá nhân tôi dưới
sự hướng dẫn giúp đỡ của PGS.TS. Hoàng Xuân Huấn và TS. Trần Ngọc Hà. Các
kết quả được viết chung với các tác giả khác đều được sự đồng ý của tác giả trước
khi đưa vào luận văn. Trong toàn bộ nội dung nghiên cứu của luận văn, các vấn
đề được trình bày đều là những tìm hiểu và nghiên cứu của chính cá nhân tôi hoặc
là được trích dẫn từ các nguồn tài liệu có ghi tham khảo rõ ràng, hợp pháp.
Trong luận văn, tôi có tham khảo đến một số tài liệu của một số tác giả
được liệt kê tại mục tài liệu tham khảo.
Hà Nội, tháng 7 năm 2020
HỌC VIÊN
ĐÀO VĂN HẢI
2
MỤC LỤC
LỜI CẢM ƠN ....................................................................................................... 1
LỜI CAM ĐOAN.................................................................................................. 2
DANH SÁCH CÁC BẢNG.................................................................................. 7
DANH SÁCH HÌNH VẼ ...................................................................................... 8
MỞ ĐẦU............................................................................................................... 9
1.1. Giới thiệu................................................................................................ 11
1.2. Xâm nhập................................................................................................ 11
1.2.1. Khái niệm...................................................................................... 11
1.5.1. Mô tả bài toán................................................................................ 16
2.1. Giới thiệu bài toán tối ưu tổ hợp .............................................................. 18
2.2. Bài toán người chào hàng......................................................................... 19
2.3.1. Tiếp cận truyền thống ........................................................................ 19
2.4. Phương pháp tối ưu đàn kiến.................................................................... 20
3
2.4.1. Kiến tự nhiên ..................................................................................... 20
2.4.2. Kiến nhân tạo (Artificial Ant) ........................................................... 22
2.4.5. Các hệ kiến......................................................................................... 26
2.4.5.1. Hệ kiến AS...................................................................................... 26
2.4.5.2. Hệ kiến ACS................................................................................... 26
2.4.5.3. Hệ kiến Max-Min ........................................................................... 29
2.4.5.4. Hệ kiến Max-Min trơn.................................................................... 29
3.1. Thuật toán DACS3-FS ............................................................................. 31
3.1.1. Đồ thị và cấu trúc............................................................................... 32
3.1.2. Xác suất chuyển tiếp.......................................................................... 32
3.1.3. Vết mùi và thông tin heuristic ........................................................... 33
3.1.4. Quy tắc cập nhật vết mùi ................................................................... 33
3.1.5. Lược đồ chung................................................................................... 35
3.2. Thuật toán SMMAS-FS............................................................................ 37
3.2.1. Quy tắc cập nhật vết mùi ................................................................... 37
3.2.2. Lược đồ thuật toán............................................................................. 38
3.2.3. Lựa chọn lời giải tốt nhất................................................................... 39
4.1. Tiến hành thực nghiệm............................................................................. 40
4.1.1. Dữ liệu đầu vào.................................................................................. 40
4.1.3. Các tham số đầu vào.......................................................................... 42
4.2. Kết quả chạy thực nghiệm........................................................................ 42
4
4.3. Nhận xét.................................................................................................... 45
4.4. Hướng nghiên cứu tiếp theo ..................................................................... 45
KẾT LUẬN......................................................................................................... 46
TÀI LIỆU THAM KHẢO................................................................................... 47
5
DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT
STT Từ viết tắt
Từ hoặc cụm từ
Ant Colony Optimization (Tối ưu hóa đàn kiến)
Ant System (Hệ kiến AS)
1
2
3
4
5
6
7
8
9
ACO
AS
ACS
Ant Colony System (Hệ kiến ACS)
MMAS
SMMAS
TSP
Max-Min Ant System (Hệ kiến MMAS)
Smooth-Max Min Ant System (Hệ kiến MMAS trơn)
Travelling Salesman Problem (Bài toán người chào hàng)
Tối ưu tổ hợp
TƯTH
IDS
Intrusion Detection System
DoS
Denial of Service (Tấn công từ chối dịch vụ)
User to Root (Tấn công chiếm quyền điều khiển)
Remote to Local (Tấn công điều khiển từ xa)
10 U2R
11 U2L
12 IDS
Intrusion Detection Systems (Hệ thống phát hiện xâm
nhập)
13 SVM
Support Vector Machine (Phân lớp SVM)
Cận trên của vết mùi
14
15
16
17
18
휏푚푎푥
휏푚푖푛
휏0
Cận dưới của vết mùi
Vết mùi được khởi tạo ban đầu
Vết mùi trên cạnh (i,j)
휏푖푗
3-LAS
Hệ kiến 3 mức
6
DANH SÁCH CÁC BẢNG
Hình 2.2: Thực nghiệm trên cây cầu đôi............................................................. 21
Hình 2.3: Thí nghiệm bổ sung............................................................................. 22
Hình 2.4: Lựa chọn đỉnh đi tiếp theo .................................................................. 24
Hình 3.1: Đồ thị cấu trúc lựa chọn đặc trưng...................................................... 32
Bảng 4.2: Thuộc tính bộ dữ liệu Kdd99.............................................................. 41
7
DANH SÁCH HÌNH VẼ
Hình 2.2: Thực nghiệm trên cây cầu đôi............................................................. 21
Hình 2.3: Thí nghiệm bổ sung............................................................................. 22
Hình 2.4: Lựa chọn đỉnh đi tiếp theo .................................................................. 24
Hình 3.1: Đồ thị cấu trúc lựa chọn đặc trưng...................................................... 32
Hình 4.1: Biểu đồ so sánh tỷ lệ chính xác giữa các phương pháp………………44
Hình 4.2: Biểu đồ so sánh tỷ lệ chính xác và số đặc trưng được lựa chọn……..44
8
MỞ ĐẦU
Ngày nay cùng với sự phát triển của Internet ngày một mở rộng, vấn đề tin
tặc đánh cắp thông tin đang ngày càng phổ biến. Đặc biệt với các thông tin quan
trọng và nhạy cảm thì việc phân loại phát hiện được các loại xâm nhập là nhiệm
vụ cần thiết.
Hệ thống phát hiện xâm nhập mạng (IDS) là một hệ thống giám sát, theo
dõi, thu thập thông tin nhằm đưa ra các cảnh báo, biện pháp phát hiện xâm nhập
mạng. IDS có nhiều cách tiếp cận nhưng đơn giản và phổ biến nhất vẫn là dựa
vào thống kê. Bài toán phát hiện xâm nhập trên tập các thông tin thực chất là bài
toán phân lớp và đưa ra dự đoán về sự xâm nhập khi gặp các thông tin mới. Một
trong những vấn đề của các thuật toán phân lớp đó là việc xử lý dữ liệu đầu vào,
các thông tin dư thừa dẫn đến việc tỷ lệ phát hiện bất thường không chính xác,
kết quả phân lớp thấp. Có thể cải thiện vấn đề dữ liệu đầu vào bằng các thuật
toán lựa chọn đặc trưng.
Thuật toán ACO là một thuật toán tốt sử dụng trong bài toán tối ưu hóa tổ
hợp. Mô phỏng cách tìm đường đi của các con kiến, thuật toán ACO sử dụng kết
hợp thông tin heuristic và học tăng cường thông qua vết mùi tạo nên nhờ các con
kiến di chuyển để giải bài toán tìm đường đi trong đồ thị cấu trúc. Việc sử dụng
thuật toán ACO để phát hiện xâm nhập đã được nhiều tác giả đề xuất trong đó
có nhóm tác giả Mehdi Hosseinzadeh Aghdam và Peyman Kabiri với đề xuất sử
dụng ACO-based Method năm 2016 [18]. Tiếp theo nhóm tác giả Helmi Md
Rais và Tahir Mehmood với đề xuất thuật toán DACS3-FS năm 2018 đề xuất
việc cập nhật vết mùi với ba cấp độ.
Trên cơ sở các thuật toán đã có tôi xin đề xuất một cải tiến nữa cho thuật
toán ACO dùng cho phát hiện xâm nhập là dùng quy tắc cập nhật vết mùi mới
mà ở đây là sử dụng phương pháp SMMAS. Phương pháp này giảm nhược điểm
của phương pháp MMAS là để vết mùi tiến dần về 휏min sau một số bước giảm
tính khám phá. Cũng như nhược điểm của các đề xuất thuật toán trên là phải tính
toán, cập nhật vết mùi nhiều lần làm tăng thời gian chạy thuật toán.
Trong luận văn này tôi sẽ trình bày lại các phương pháp lựa chọn đặc tính
bằng phương pháp ACO. Khảo cứu phương pháp DACS3-FS được Helmi Md
Rais và cộng sự đề xuất năm 2018 được coi là tối ưu cho bài toán này. Sử dụng
ý tưởng của nhóm tác giả [8] đề xuất phương pháp cập nhật vết mùi mới cho bài
toán. Và chứng minh quy tắc cập nhật vết mùi mới do nhóm tác giả [17] đề xuất
năm 2012 có hiệu quả hơn so với phương pháp trên.
9
Ngoài phần kết luận, cấu trúc của luận văn bao gồm:
Chương 1: Giới thiệu về phát hiện xâm nhập các khái niệm và các hướng
tiếp cận của bài toán phát hiện xâm nhập.
Chương 2: Giới thiệu tối ưu hóa tổ hợp và bài toán tối ưu hóa đàn kiến,
cách tiếp cận, các phương pháp tối ưu hóa đàn kiến
Chương 3: Trình bày thuật toán DACS3-FS, phương pháp xây dựng đồ
thị cấu trúc, cập nhật mùi. Đề xuất cải tiến thuật toán bằng phương pháp cập
nhật vết mùi mới SMMAS.
Chương 4: Tiến hành thực nghiệm trên bộ dữ liệu chuẩn, thống kê, đánh
giá kết quả thu được và so sánh giữa hai cách giải quyết bài toán ở trên. Đề xuất
một số cải tiến như tìm kiếm địa phương và cập nhật lại vết mùi.
10
CHƯƠNG 1: GIỚI THIỆU VỀ PHÁT HIỆN XÂM NHẬP MẠNG
1.1. Giới thiệu
Internet đã trở thành một phần của cuộc sống hiện đại và ngày càng có vai
trò quan trọng đối với con người, chúng ta có thể thấy được internet đã và đang
chi phối hầu như mọi lĩnh vực của cuộc sống từ kinh tế, giải trí đến giáo dục và
đào tạo… Đặc biệt ngày nay, internet được sử dụng như một thành phần quan
trọng trong các mô hình kinh doanh, trong đó cả doanh nghiệp và khách hàng đều
sử dụng các dịch vụ, ứng dụng, website, thư điện tử,… trong các hoạt động của
mình. Vì vậy, vấn đề an toàn thông tin khi sử dụng môi trường internet cần phải
được đặc biệt quan tâm. Phát hiện xâm nhập mạng là một vấn đề lớn cần nghiên
cứu cho cả mạng doanh nghiệp và cá nhân
Việc triển khai và quản lý hệ thống thông tin yêu cầu nhiều cơ chế bảo vệ
chặt chẽ, an toàn. Để một hệ thống an toàn ngoài việc hệ thống cần trang bị những
công cụ đủ mạnh và có người quản trị mạng am hiểu về phương thức xử lý các
cuộc tấn công thì cũng cần những hệ thống hỗ trợ cho việc phát hiện xâm nhập
giúp phòng ngừa các cuộc tấn công, đảm bảo an toàn cho hệ thống.
Bảo mật thông tin môi trường mạng gồm nhiều lĩnh vực nhưng trong đó có
bốn hướng chính là: An toàn phía máy chủ, an toàn phía máy khách, bảo mật trên
đường truyền, phát hiện xâm nhập. Trong đó phát hiện xâm nhập (intrusion
detection) là một lĩnh vực được nhiều sự quan tâm và đầu tư nghiên cứu, các giải
pháp giúp tối ưu hóa việc phát hiện xâm nhập được đưa ra nhằm cải tiến giúp việc
phát hiện xâm nhập chính xác và nhanh chóng hơn. Vì thế trong luận văn này, tôi
tập trung vào việc đưa ra cải tiến giúp việc phát hiện xâm nhập hiệu quả hơn
nhưng trước hết tôi xin đưa ra các giới thiệu để người đọc hiểu rõ hơn về các định
nghĩa tôi sẽ nêu trong bài viết.
1.2. Xâm nhập
1.2.1. Khái niệm
Vào năm 1999 Kendall có đưa ra một định nghĩa như sau: “Tấn công hay
còn gọi là xâm nhập mạng là những hoạt động có chủ đích, lợi dụng các tổn
thương của hệ thống thông tin nhằm phá vỡ tính sẵn sàng, tính toàn vẹn và tính
bảo mật của hệ thống”. Và đó có thể là một định nghĩa gần đúng nhất của tấn
công hay xâm nhập mạng
1.2.2. Các kiểu xâm nhập phổ biến
11
Trong thực tế có rất nhiều kiểu tấn công mạng khác nhau nhưng thường sẽ
được phân thành các nhóm chính như sau: tấn công kiểu từ chối dịch vụ, tấn công
kiểu thăm dò, tấn công kiểu chiếm quyền điều khiển, tấn công từ xa…
a) Tấn công từ chối dịch vụ
Tấn công từ chối dịch vụ DoS là một kiểu tấn công cơ bản bằng cách gửi
một loạt thông tin đến máy chủ hệ thống khiến nó bị quá tải không thể cung cấp
dịch vụ, làm gián đoạn hệ thống hoặc làm tê liệt hệ thống.
b) Tấn công thăm dò
Kiểu tấn công thăm dò (Probe), tin tặc quét mạng hoặc máy tính để tìm ra
các lỗ hổng giống như theo dõi, giám sát hệ thống. Phương thức phổ biến là việc
quét và theo dõi các cổng dịch vụ đang mở của máy tính ở đây sẽ có các thông tin
như IP, MAC, thông tin về tường lửa… Các kiểu tấn công thăm dò như: Sniffing,
Ping Sweep, Portsweep Satan,…
Ví dụ: Sniffer là một dạng tấn công nghe lén trên hệ thống mạng dựa trên
những đặc điểm của cơ chế TCP/IP. Ban đầu đây là một kỹ thuật bảo mật, được
phát triển nhằm giúp các nhà quản trị mạng khai thác mạng hiệu quả hơn và có
thể kiểm tra các dữ liệu ra vào mạng cũng như các dữ liệu trong mạng. Sau này,
phương thức này được lợi dụng để lấy cắp mật khẩu và các thông tin khác.
c) Tấn công U2R
Đơn giản là việc tin tặc tìm cách để truy cập được vào hệ thống với quyền
cao nhất một cách bất hợp pháp.
Kiểu tấn công này ít gặp hơn so với hai kiểu trên. Nhưng đây cũng là một
kiểu tấn công nguy hiểm vì khi có quyền cao nhất tin tặc có thể phá hoại hệ thống.
Trong bộ dữ liệu KDD99 mà tôi sẽ dùng để thực nghiệm trong luận văn có đề cập
đến một kiểu tấn công U2R là: buffer_overflow, loadmodule, perl, rootkit.
d) Tấn công R2L
Đây là kiểu tấn điều khiển máy tính từ xa. Từ việc khai thác các lỗ hổng
bảo mật tin tặc gửi các gói tin đến máy tính trong hệ thống mạng rồi tìm cách truy
cập trái phép hệ thống với tư cách là người dùng trong hệ thống mạng đó. Cách
tấn công phổ biến của loại này là đoán mật khẩu thông qua phương pháp từ điển,
FTP Write…
1.2.3. Các cách ngăn chặn xâm nhập truyền thống
Các biện pháp cũ hay dùng phổ biến như: tường lửa (firewall), mã hóa, xác
thực, quyền truy cập,…
12
a) Tường lửa (Firewall)
Tường lửa có thể là phần mềm hoặc phần cứng được thiết kế để ngăn chặn
hoặc cho phép những truy cập dựa trên các tiêu chuẩn, tập luật được lưu trên hệ
thống. Nó cũng có thể mã hóa, giải mã hay ủy quyền cho các giao dịch giữa các
miền bảo mật khác nhau. Một số loại tường lửa như: bộ lọc gói (Packet Filtering),
cổng ứng dụng (Application Gateway), cổng mức mạch (Circuit Level Gate)…
Tường lửa có một số điểm yếu như:
- Chỉ có tác dụng với các cuộc tấn công bên ngoài mạng.
- Không diệt được virus hay mã độc.
- Không chống được các cuộc tấn công mà không đi qua tường lửa.
b) Mã hóa dữ liệu (Encoding)
Mã hóa dữ liệu là phương pháp bảo vệ thông tin dữ liệu bằng cách chuyển
dữ liệu từ dạng thông thường sang dạng khác nhưng vẫn có thể giải mã tức là đưa
dữ liệu về dạng ban đầu được bằng một hình thức giải mã. Trong quá trình truyền
tin dữ liệu có thể bị ăn trộm bởi tin tặc nhưng chúng chỉ lấy được gói tin mã hóa
và không biết cách giải mã việc này giúp dữ liệu an toàn. Việc mã hóa và giải mã
được thực hiện bởi một bộ mã hóa giải mã thích hợp.
c) Xác thực (Authentication)
Xác thực là việc xem xét người dùng đang truy cập có phải là người dùng
đã được khai báo trong hệ thống không.
d) Quyền truy cập (Permission)
Đây coi như là mức bảo vệ cuối cùng, mỗi một người dùng sẽ được cấp các
quyền khác nhau đối với hệ thống hoặc đơn giản là một chức năng. Hệ thống sẽ
kiểm tra người dùng hiện tại có được khai báo sử dụng chức năng đó không từ đó
từ chối những người cố ý truy cập hệ thống hoặc sử dụng chức năng khi chưa
được phép.
1.3. Hệ thống phát hiện xâm nhập mạng
Hệ thống phát hiện xâm nhập mạng (Intrusion Detection System) là một hệ
thống (có thể là thiết bị phần cứng hay phần mềm) nhằm giám sát lưu lượng mạng
theo dõi, thu thập thông tin để phát hiện xâm nhập mạng và đưa ra cảnh báo..
1.3.1. Phân loại hệ thống phát hiện xâm nhập mạng
Hệ thống phát hiện xâm nhập được phân loại dựa trên cách thức thu thập
thông tin hoặc phương pháp phân tích.
13
Ta có thể phân loại thành hai dạng hệ thống phát hiện ở mức mạng NIDS
(Network -based IDS) và hệ thống phát hiện xâm nhập ở mức máy chủ HIDS
(Host – based IDS)
Network – based IDS (Hệ thống phát hiện xâm nhập ở mức mạng)
NIDS hoạt động độc lập, kiểm tra các luồng thông tin, truy cập vào luồng thông
tin trên mạng bằng cách kết nối vào các Hub, Switch được cấu hình Port mirroring
hoặc Network tap để bắt các gói tin, phân tích nội dung các gói tin từ đó phát hiện
các cuộc tấn công và đưa ra các cảnh báo.
Port mirroring được sử dụng để gửi một bản sao của tất cả các gói tin trên
mạng khi nó đi qua cổng của Switch tới một thiết bị giám sát mạng trên cổng khác
của Switch đó. Nó thường được dùng trong các thiết bị mạng cần giám sát luồng
trên mạng, ví dụ như hệ thống IDS, Port Analyzer (SPAN)…
Hình 1.1 Hệ thống phát hiện xâm nhập NIDS
Nhược điểm của hệ thống NIDS là giới hạn băng thông và có thể xảy ra
hiện tượng tắc nghẽn cổ chai khi lưu lượng mạng hoạt động ở mức cao.
Host – based IDS (Hệ thống phát hiện xâm nhập máy trạm chủ)
HIDS là một phần mềm chạy trên các trạm hoặc máy chủ có chức năng giám
sát tất cả các hoạt động trên máy đó. HIDS có thể được cài cục bộ trên một máy
tính và nó linh hoạt hơn so với NIDS. HIDS phân tích thông tin thu được trong
nội bộ hệ thống cung cấp một cơ chế phân tích toàn diện các hoạt động và phát
hiện một cách chính xác các thành phần tấn công.
14
1.4. Các cách tiếp cận cơ bản trong bài toán phát hiện xâm nhập
Có nhiều cách tiếp cập phổ biến cho bài toán phát hiện xâm nhập nhưng
trong giới hạn luận văn tôi sẽ nêu một số các cách tiếp cận phổ biến như: phát
hiện xâm nhập dựa vào luật, dựa vào phân tích thống kê.
1.4.1. Cách tiếp cận dựa vào luật
Phát hiện xâm nhập dựa vào luật (rule-based) là một trong những phương
pháp khá phổ biến và được sử dụng nhiều, việc phát hiện sẽ dựa vào các dấu hiệu
xâm nhập.
Phát hiện xâm nhập dựa tập luật thường được thực hiện như sau:
Bước 1: Hệ thống lựa chọn ra những tập luật mà theo luật đó là những dấu
hiệu của việc xâm nhập, những dữ liệu này được thu thập từ nhiều cuộc tấn công
trước đó.
Bước 2: Xây dựng cơ sở dữ liệu các luật với các kiểu xâm nhập khác nhau
theo dạng if-then như sau:
if {condition} then {atc}
Trong đó:
condition: các dấu hiệu (đặc trưng) liên quan tới các kiểu xâm nhập như:
duration, protocol, source port, destination port, service,...
atc: kiểu tấn công.
Bước 3: Sử dụng các thuật toán so khớp để tìm ra các bộ dữ liệu phù hợp
với tập luật.
Ví dụ:
Luật quy định các kiểu tấn công dos.
if(duration = “0:0:1” and protocol = “finger” and source_port = 18982
and destination_port = 79 and source_ip = “9.9.9.9” and destination_ip =
“172.16.112.50” and service =“private”) then (attack name = “dos”).
Luật quy định các kiểu tấn công probe.
if(duration = “0:0:1” and protocol = “telnet” and source_port = 18982
and destination_port = 79 and source_ip = “9.9.9.9” and destination_ip =
“172.16.112.50” and service =“fpt”) then (attack name = “probe”).
Ưu điểm của cách tiếp cận này là dễ cài đặt và đơn giản trong việc sử dụng.
Khi hệ thống mạng đứng trước những nguy cơ tấn công mới, người quan trị sẽ
cập nhật bổ sung tập luật mới vào hệ thống. Phương pháp này có tỷ lệ phát hiện
15
sai thấp vì các tập luật đã được lựa chọn kỹ và thuật toán chỉ có nhiệm vụ so sánh
chỉ ra thông tin nào phù hợp với tập luật đó.
Tuy nhiên, bên cạnh đó cách tiếp cận này cũng có nhiều nhược điểm điển
hình là việc đứng trước một nguy cơ tấn công mới mà không có trong tập luật hệ
thống sẽ không phát hiện được. Các cuộc tấn công của tin tặc luôn thay đổi việc
cập nhật các tập luật liên tục vào hệ thống gây mất thời gian của người quản trị.
1.4.2. Cách tiếp cận dựa vào thống kê
Phát hiện xâm nhập dựa vào thống kê là một trong những phương pháp phát
hiện xâm nhập dựa trên sự bất thường của dữ liệu. Hệ thống sẽ thống kê bằng
cách quan sát các hoạt động của đối tượng tạo lưu lại những hành vì hoạt động
của đối tượng, khi có các dữ liệu bất thường hệ thống sẽ đưa ra cảnh báo hoặc
ngăn chặn. Việc phát hiện bất thường dựa trên thống kế cơ bản là bài toán phân
lớp dữ liệu sử dụng các thuật toán phân lớp từ đó có thể đưa ra dự đoán đối với
các dữ liệu mới, các cuộc tấn công mới.
1.5. Bài toán phát hiện xâm nhập trong hệ thống mạng nội bộ
1.5.1. Mô tả bài toán
Trong một mạng nội bộ một công ty cần một hệ thống phát hiện xâm nhập
đưa ra các cảnh báo hoặc biệt pháp khi phát hiện có sự xâm nhập. Bộ phận quản
trị mạng trong công ty thường xuyên quản lý giám sát lưu lượng mạng và các
thông tin mạng bằng các kiểm tra các báo cáo gói tin được gửi trong giao thức
mạng. Công việc kiểm tra thông tin mạng bình thường rất khó để phân biệt được
trạng thái bị xâm nhập hoặc không. Cần một hệ thống phát hiện xâm nhập từ các
gói tin được nhận hoặc gửi đi trong mạng.
Đối tượng xâm nhập là một đối tượng nằm ngoài mạng cố gắng xâm nhập
và hệ thống để đánh cắp thông tin hoặc có hành vi phá hoại, cũng có thể là người
có tài khoản truy cập vào hệ thống nhưng có những hành vì truy cập vào tài liệu
không thuộc thẩm quyền, phá hoại hệ thống…
Ý tưởng sử dụng một hệ thống phát hiện xâm nhập có chức năng nhận và
đánh giá các gói tin nhận hoặc gửi trong mạng nội bộ công ty. Đưa ra cảnh báo
nếu gói tin đó có biểu hiện của việc xâm nhập.
1.5.2. Đề xuất hướng giải quyết
Xây dựng một hệ thống phát hiện xâm nhập.
Khi các gói tin được kiểm tra, nội dung các gói tin sẽ được đưa vào hệ thống
để phân lớp, kết quả trả về sẽ thuộc hai trạng thái: xâm nhập hoặc không xâm
nhập. Khi trạng là xâm nhập hệ thống sẽ gửi thông tin địa chỉ ip người dùng trong
16
mạng và đưa ra cảnh báo cho quản trị viên hoặc có các biện pháp ngăn chặn kịp
thời.
a. Dữ liệu đầu vào
Dữ liệu đầu là những thông tin thu thập được từ việc bắt các gói tin trong
dữ liệu lưu lượng mạng. Những thông tin dùng trong việc xác định một kết nối là
xâm nhập hay không xâm nhập có thể là: Duration, Protocol_type, Service, Flag,
Srv_count, Num_root…
Dữ liệu này có thể được lấy thông ứng dụng thu thập lưu lượng mạng như:
TCPDUMP...
b. Cách xác định phân lớp dữ liệu
Việc xác định xem một bộ dữ liệu có là xâm nhập hay không xâm nhập dựa
trên các hành vi đã biết trong thực tế. Khi tiến hành xây dựng hệ thống phát hiện
xâm nhập ta sử dụng các bộ dữ liệu đang được dán nhãn và công bố để tiến hành
huấn luyện (như bộ dữ liệu KDD99 được luận văn sử dụng trong phần thực
nghiệm).
17
CHƯƠNG 2: GIỚI THIỆU BÀI TOÁN TỐI ƯU HÓA TỔ HỢP
VÀ PHƯƠNG PHÁP TỐI ƯU HÓA ĐÀN KIẾN
2.1. Giới thiệu bài toán tối ưu tổ hợp
Các bài toán tiêu biểu của lớp bài toán tối ưu tổ hợp có thể kể ra như: bài
toán người giao hàng, bài toán lập thời khóa biểu, bài toán lập lịch sản xuất…
Đây là các bài toán trong thực tế để giải các bài toán dạng này ta cần mô
hình hóa chúng để có thể mô phỏng trên máy tính, từ đó có thể tìm ra lời giải tối
ưu. Đặc điểm chung nhất với mỗi bài toán là đều chứa n thành phần C={c1,…cn}
và hàm mục tiêu f. Các bài toán ứng dụng với bộ (S, f, Ω), trong đó S là tập hữu
hạn các trạng thái (phương án), f là hàm mục tiêu xác định trên S và Ω là tập các
ràng buộc. Mỗi phương án 푠 ∈ 푆 thỏa mãn các ràng buộc Ω gọi là phương án chấp
nhận được. Mục tiêu của chúng ta là tìm ra s* phương án tối ưu đối với hàm mục
tiêu f, nói cách khác chính là tìm phương án s* sao cho f(s*) ≤ f(s) với mọi 푠 ∈ 푆.
Đối với bài toán này ta có 3 cách giải quyết đó là: vét cạn, kỹ thuật ăn tham hoặc
phương pháp tối ưu trong lĩnh vực NP-hard.
Các thuộc tính của tập S, C và Ω như sau:
1. Ký hiệu X là tập các vector trên C có độ dài không quá h:
X={<u0,…,uk>ui ∀i≤k≤h}. Khi đó, mỗi phương án s trong S được xác
định nhờ ít nhất một vector trong X.
−1( )
2. Tồn tại tập con X* của X và ánh xạ 휑 từ X* lên S sao cho 휑 푠 không
rỗng với mọi 푠 ∈ 푆, trong đó tập X* có thể xây dựng được từ tập con C0
nào đó của C nhờ thủ tục mở rộng tuần tự dưới dây.
3. Từ C0 ta mở rộng tuần tự thành X* như sau:
i. Ta xem x0 = <u0> là mở rộng được với mọi u0∈C0
ii. Giả sử xk = <u0,…,uk> là mở rộng được và chưa thuộc X*. Từ tập
ràng buộc Ω, xác định tập con J(xk) của C, sao cho với mọi uk+1∈
J(xk) thì xk+1=<u0, …,uk, uk+1> là mở rộng được.
iii. Áp dụng thủ tục mở rộng từ các phần tử u0∈C0 cho phép ta xây
dựng được mọi phần tử của X*.
Ta thấy mỗi bài toán TƯTH được xem là một bài toán cực trị hàm có h
biến, trong đó mỗi biến nhận giá trị trong tập hữu hạn C kể cả giá trị rỗng. Nói
một cách khác là bài toán tìm kiếm trong không gian vector độ dài không quá h
trong đồ thị đầy đủ có các đỉnh có nhãn trong tập C.
18
2.2. Bài toán người chào hàng
Bài toán người chào hàng (Traveling Salesman Problem - TSP) là một bài
toán NP-hard thuộc thể loại tối ưu hóa rời rạc hay tổ hợp. Đây là bài toán TƯTH
điển hình, được nghiên cứu và xem như là bài toán chuẩn để đánh giá về hiệu quả
lời giải các bài toán TƯTH.
Có thể phát biểu bài toán đơn giản như sau:
Cho trước một danh sách thành phố và khoảng cách giữa chúng, tìm chu
trình ngắn nhất đi qua tất cả cách thành phố trong danh sách với điều kiện mỗi
thành phố chi được đi qua một lần.
Có thể thấy đây chính là bài toán tìm chu trình Hamilton với đồ thị đầy đủ
(
)
có trọng số 퐺 = 푉, 퐸 , với V là tập các đỉnh với nhãn là các thành phố trong C,
E là tập các cạnh nối các thành phố tương ứng, độ dài mỗi cạnh chính là độ dài
đường đi giữa hai thành phố tương ứng. Trong trường hợp này, tập S sẽ là tập các
chu trình Hamilton trên G, f là độ dài của chu trình, Ω là ràng buộc đòi hỏi chu
trình là chu trình Hamilton (qua tất cả các đỉnh, mỗi đỉnh đúng một lần), C là tập
(
)
thành phố được xét, C0 trùng với C, tập X là vectơ độ dài n: 푥 = 푥1, … , 푥푛 với
( )
푥푖 ∈ 퐶 ∀푖 ≤ 푛, còn X* là các vectơ trong đó 푥푖 khác 푥푗 đối với mọi cặp 푖, 푗 .
Do đó, lời giải tối ưu của bài toán TSP là một hoán vị π của tập đỉnh
{
}
푐1, 푐푛, … , 푐푛 sao cho hàm độ dài f(π) là nhỏ nhất, trong đó f(π) được tính theo
(1.1):
( ) ∑푛−1
푓 휋 =
( ) (
)
( ) ( )
푑(휋 푖 , 휋 푖 + 1 ) + 푑(휋 푛 , 휋 1 )
(1.1)
푖=1
2.3. Các cách tiếp cận giải quyết bài toán tối ưu tổ hợp
Các bài toán TƯTH có nhiều cách tiếp cận nhưng chúng ta có thể quy về
hai cách tiếp cận chính là: tiếp cận dựa trên phương pháp truyền thống và tiếp cập
dựa trên thực nghiệm.
2.3.1. Tiếp cận truyền thống
Tiếp cận này các thuật toán phải đảm bảo hội tự tới tối ưu địa phương, toàn
cục hoặc ước lượng được sai số trong trường hợp xấu nhất. Đối với bài toán tối
ưu hóa liên tục ta có thể tìm tối ưu hóa toàn cục dựa trên đặc điểm của hàm mục
tiêu chẳng hạn như: quy hoạch tuyến tính, quy hoạch lồi, quy hoạch toàn
phương…
Đối với bài toán tối ưu hóa tổ hợp khó cỡ nhỏ người ta thường dùng các
phương pháp như: vét cạn, tìm kiếm heuristic…đối với bài toán lớn thì thường
phải đề xuất các phương pháp heuristic và ước lượng được tỷ lệ tối ưu.
19
Tải về để xem bản đầy đủ
49 trang
12240
Free
Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Phương pháp tối ưu đàn kiến để giải bài toán phát hiện xâm nhập", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- luan_van_phuong_phap_toi_uu_dan_kien_de_giai_bai_toan_phat_h.pdf
