ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
_______________________
Lê Đăng Nguyên
PHÁT TRIỂN MỘT SỐ KỸ THUẬT SO KHỚP
ỨNG DỤNG TRONG QUÁ TRÌNH PHÁT HIỆN
XÂM NHẬP VÀ GIẢ MẠO TRÊN MẠNG
Chuyªn ngµnh : Cơ sở toán học cho Tin học
M· sè: 62 46 01 10
LUẬN ÁN TIẾN SĨ TOÁN HỌC
Hà Nội - 2015
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
_______________________
Lê Đăng Nguyên
PHÁT TRIỂN MỘT SỐ KỸ THUẬT SO KHỚP
ỨNG DỤNG TRONG QUÁ TRÌNH PHÁT HIỆN
XÂM NHẬP VÀ GIẢ MẠO TRÊN MẠNG
Chuyªn ngµnh : Cơ sở toán học cho Tin học
M· sè: 62 46 01 10
LUẬN ÁN TIẾN SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
1. PGS.TS. Lê Trọng Vĩnh
2. PGS.TS. Đỗ Trung Tuấn
Hà Nội - 2015
i
LỜI CAM ĐOAN
Tôi xin cam đoan đây lcông trnh nghiên cu ca riêng tôi. Cc s liu, kt
qu nêu trong lun n ny l trung thc v chưa tng đưc ai công b trong bt k
công trnh nghiên cu no khc.
Tác giả luận án
Lê Đăng Nguyên
ii
LỜI CẢM ƠN
Tc gi xin đưc by tlng bit ơn chân thnh v sâu sc ti PGS.TS. Lê
Trọng Vĩnh, PGS.TS Đỗ Trung Tun đ tn tâm hưng dn v gip đ tc gi trong
sut qu trnh thc hin lun n ny.
Tc gi cng xin gi li cm ơn đn cc thy gio, cô gio trong bộ môn Tin
học, khoa Toán - Cơ - Tin học, trưng Đi học Khoa học T nhiên, Đi học Quc
gia H Nội đ góp qu bu gip đ tc gi trong qu trnh nghiên cu thc hin
lun n.
Tc gi cng xin chân thnh cm ơn tt c cc thy, các cô trong Ban Ch
nhim Khoa Ton - Cơ - Tin học, trưng Đi học Khoa học T nhiên, Đi học Quc
gia H Nội, Ban Gim hiu trưng Đi học Hi Phng, Phng Đo to, Khoa Công
ngh Thông tin, trưng Đi học Hi Phng cng ton th cc anh ch em đng
nghip, bn b đ luôn động viên, to mọi điu kin thun li đ gip đ tc gi
hon thnh lun n.
Cui cng, tc gi xin by t lng bit ơn vô hn đn b m anh ch v gia
đnh đ ht lng ng hộ, động viên, chia s nhng khó khăn thun li cng tc gi
trong sut qu trnh thc hin lun n.
Tác giả
Lê Đăng Nguyên
iii
MỤC LỤC
LỜI CAM ĐOAN ........................................................................................................i
LỜI CẢM ƠN ............................................................................................................ ii
MỤC LỤC ................................................................................................................. iii
DANH MỤC CÁC HÌNH VẼ....................................................................................vi
DANH MỤC CÁC BẢNG ...................................................................................... viii
DANH MỤC CÁC TỪ VIẾT TẮT ...........................................................................ix
LỜI NÓI ĐẦU ............................................................................................................ 1
CHƯƠNG 1. TỔNG QUAN VỀ SO KHỚP .............................................................. 6
1.1. So khớp chuỗi .............................................................................................. 6
1.1.1. Bài toán so khớp chuỗi ................................................................... 6
1.1.2 Các thuật toán so khớp chính xác cổ điển ....................................... 9
1.1.3 Các thuật toán so khớp chính xác dựa trên mô hình Automat ...... 13
1.1.4 Các thuật toán so khớp chính xác dựa trên bảng băm ................... 14
1.1.5 Các thuật toán so khớp gần đúng ................................................... 16
1.1.6 Một số nghiên cứu liên quan về ứng dụng thuật toán so khớp trong
phát hiện xâm nhập mạng ................................................................................. 17
1.2. So khớp đồ thị ............................................................................................ 26
1.2.1. Một số định nghĩa và ký hiệu ....................................................... 26
1.2.2. Bài toán so khớp đồ thị ................................................................. 28
1.2.3 Một số nghiên cứu liên quan về so khớp đồ thị ............................. 29
1.3. Kết chương ................................................................................................. 33
CHƯƠNG 2. ỨNG DỤNG SO KHỚP MẪU TRONG QUÁ TRÌNH PHÁT HIỆN
XÂM NHẬP MẠNG ................................................................................................ 34
2.1. Xâm nhập mạng ......................................................................................... 34