ĐẠ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

LỜI CAM ĐOAN

Tôi xin cam đoan đây là cô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

i

LỜI CẢM ƠN
Tác giả xin được bày tỏ lò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

ii

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

iii

2.1.1. Một số kỹ thuật xâm nhập trái phép .............................................35
2.1.2. Một số giải pháp kỹ thuật ngăn chặn xâm nhập ...........................38
2.1.3. Hệ thống phát hiện xâm nhập trái phép ........................................39
2.1.4. Một số nghiên cứu liên quan đến hệ thống phát hiện xâm nhập ..44
2.2 Thuật toán Aho-Corasick ............................................................................48
2.3. Một số nghiên cứu liên quan......................................................................54
2.4. Cải tiến thuật toán AC bằng kỹ thuật nén dòng và bảng chỉ số .................56
2.4.1. Biểu diễn không gian lưu trữ và tối ưu hóa bằng kỹ thuật nén dòng56
2.4.2. Cải tiến giai đoạn tiền xử lý của AC ............................................58
2.4.3. Thực nghiệm và đánh giá .............................................................62
2.5. Thuật toán đề xuất mới xây dựng biểu đồ hướng cấu trúc các mẫu kết hợp
với danh sách liên kết ................................................................................................64
2.5.1. Giai đoạn tiền xử lý ......................................................................64
2.5.2. Giai đoạn tìm kiếm .......................................................................66
2.5.3. Thuật toán đề xuất ........................................................................69
2.6. Kết chương .................................................................................................72
CHƯƠNG 3. ỨNG DỤNG SO KHỚP ĐỒ THỊ TRONG QUÁ TRÌNH PHÁT
HIỆN CÁC TRANG WEB GIẢ MẠO .....................................................................73
3.1. Giả mạo trên mạng .....................................................................................73
3.1.1. Giới thiệu ......................................................................................73
3.1.2. Một số kỹ thuật giả mạo ...............................................................73
3.1.3. Một số nghiên cứu liên quan đến giả mạo Web ...........................75
3.2. Một số nghiên cứu liên quan về so khớp đồ thị .........................................77
3.2.1 Tìm đẳng cấu đồ thị và đẳng cấu đồ thị con. .................................77
3.2.2. Thuật toán SI - COBRA cho bài toán so khớp đồ thị gán nhãn. ..80
3.2.3 Thuật toán Simple Tree Matching .................................................83

iv

3.2.4 Thuật toán Partial Tree Alignment ................................................87
3.2.5 Thuật toán NET .............................................................................89
3.2.6 Thuật toán di truyền .......................................................................92
3.3. Giải thuật di truyền cho bài toán so khớp đồ thị ........................................94
3.3.1. Giải thuật di truyền .......................................................................94
3.3.2. Kết quả mô phỏng với giải thuật di truyền ...................................99
3.4 Thuật toán đề xuất về ứng dụng so khớp đồ thị vào so khớp DOM-tree .107
3.4.1 Khái niệm cây DOM ....................................................................107
3.4.2 Xây dựng cây DOM từ trang Web ..............................................108
3.4.3. Phát hiện giả mạo dựa trên cây DOM ........................................111
3.5. Kết chương ...............................................................................................114
KẾT LUẬN .............................................................................................................115
Các kết quả của luận án ........................................................................115
Hướng phát triển luận án ......................................................................116
DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ LIÊN QUAN ĐẾN LUẬN ÁN ....117
TÀI LIỆU THAM KHẢO .......................................................................................118

v

DANH MỤC CÁC HÌNH VẼ
Hình 1.1. So khớp dựa trên tiền tố ......................................................................................... 8
Hình 1.2. So khớp dựa trên hậu tố ......................................................................................... 9
Hình 1.3. So khớp dựa trên thừa số ....................................................................................... 9
Hình 2.1. Kiến trúc hệ thống phát hiện xâm nhập mạng ..................................................... 40
Hình 2.2. Hệ thống phát hiện đột nhập cho mạng NIDS ..................................................... 41
Hình 2.3. Hệ thống phát hiện đột nhập cho trạm chủ - HIDS ............................................. 42
Hình 2.4. Kiến trúc hệ thống Snort ...................................................................................... 44
Hình 2.5 Quá trình so sánh của thuật toán KMP ................................................................. 49
Hình 2.6 Xây dựng mảng Next ứng với mẫu P = “aabaaa“ ................................................. 49
Hình 2.7 Xây dựng mô hình otomat cho tập mẫu P = {her, their, eye, iris, he, is} ............. 53
Hình 2.8. Không gian trạng thái của AC với tập mẫu P ...................................................... 57
Hình 2.9. Không gian trạng thái của thuật toán AC gốc ...................................................... 60
Hình 2.10. Không gian trạng thái của thuật toán AC sau khi tối ưu.................................... 61
Hình 2.11. So sánh không gian bộ nhớ của thuật toán AC với các cách tiếp cận lưu trữ
trạng thái khác nhau. ............................................................................................................ 63
Hình 2.12. Kết quả của giai đoạn tiền xử lý của thuật toán AC .......................................... 64
Hình 2.13. Kết quả giai đoạn tiền xử lý của thuật toán CW ................................................ 65
Hình 2.14. Kết quả giai đoạn tiền xử lý của thuật toán WM ............................................... 66
Hình 2.15. Kết quả giai đoạn tiền xử lý trong thuật toán của chúng tôi .............................. 66
Hình 2.16. Giai đoạn tìm kiếm của thuật toán CW và WM ................................................ 68
Hình 2.17. Giai đoạn tìm kiếm và so khớp trong thuật toán chúng tôi đề xuất ................... 69
Hình 2.18. So sánh về thời gian thực hiện khi cố định số lượng mẫu ................................. 71
Hình 2.19. So sánh về bộ nhớ sử dụng khi cố định số lượng mẫu ...................................... 71
Hình 3.1. Minh họa về các vector hàng - cột biểu diễn ma trận kề của một đồ thị G. ........ 77
Hình 3.2. Đồ thị GM và GD. ................................................................................................. 78
Hình 3.3. Cây quyết định biểu diễn tất cả các ma trận kề của đồ thị GD. ............................ 78
Hình 3.4. Cây quyết định biểu diễn hai đồ thị GM và GD .................................................... 80
Hình 3.5. Mô phỏng thuật toán tìm đồ thị đẳng cấu dựa vào danh sách các mã. ................ 81
Hình 3.6 Ví dụ về chiến lược tìm kiếm theo chiều rộng, chiều sâu sử dụng mã LVEV. ....... 83
Hình 3.7. Ví dụ về phép ánh xạ giữa 2 cây .......................................................................... 84

vi

Hình 3.8. Ví dụ về thuật toán Simple Tree Matching .......................................................... 86
Hình 3.9. Quá trình mở rộng cây ......................................................................................... 88
Hình 3.10. Quá trình so khớp các nút của thuật toán NET .................................................. 91
Hình 3.11 Thực nghiệm với đồ thị vô hướng có số đỉnh nhỏ hơn 10 ................................ 100
Hình 3.12 Đồ thị con tương ứng của cá thể. ...................................................................... 100
Hình 3.13 Thực nghiệm với đồ thị vô hướng có số đỉnh lớn hơn 10 và nhỏ hơn 20 ......... 101
Hình 3.14 Thực nghiệm với đồ thị vô hướng có số đỉnh lớn hơn 20................................. 101
Hình 3.15 Thực nghiệm với đồ thị vô hướng có trọng số nhỏ hơn 10 đỉnh ...................... 102
Hình 3.16 Thực nghiệm với đồ thị vô hướng có trọng số từ 10 đến 20 đỉnh .................... 103
Hình 3.17 Thực nghiệm với đồ thị vô hướng có trọng số lớn hơn 20 đỉnh ....................... 104
Hình 3.18 Thực nghiệm với đồ thị vô hướng có gán nhãn với số đỉnh nhỏ hơn 10 .......... 105
Hình 3.19 Thực nghiệm với đồ thị vô hướng có gán nhãn với số đỉnh từ 10 đến 20 ........ 106
Hình 3.20 Thực nghiệm với đồ thị vô hướng có gán nhãn với số đỉnh lớn hơn 20 ........... 106
Hình 3.20. Ví dụ cây DOM của một trang HTML ............................................................ 108
Hình 3.21 Ví dụ minh họa về sử dụng visual cue .............................................................. 110
Hình 3.22 Ví dụ minh họa về biểu diễn các đối tượng trang Web dưới dạng DOM-Tree 110
Hình 3.23 Biểu diễn 2 trang web thật và giả mạo dưới dạng cây DOM............................ 112

vii

DANH MỤC CÁC BẢNG
Bảng 2.1. Nén ma trận chuyển hàm Goto với CSR ............................................................. 57
Bảng 2.2. Nén hàm failure của AC dùng bảng chỉ số .......................................................... 57
Bảng 2.3. Thống kê không gian trạng thái thực nghiệm trên Snort với các tập luật chuẩn . 63
Bảng 3.1. Kết quả độ thích nghi ở một số thế hệ với số đỉnh nhỏ hơn 10 ......................... 100
Bảng 3.2. Kết quả độ thích nghi ở một số thế hệ với số đỉnh lớn hơn 10 nhỏ hơn 20 ...... 101
Bảng 3.3. Kết quả độ thích nghi ở một số thế hệ với số đỉnh lớn hơn 20.......................... 102
Bảng 3.4. Kết quả độ thích nghi ở một số thế hệ với số đỉnh nhỏ hơn 10 ......................... 103
Bảng 3.5. Kết quả độ thích nghi ở một số thế hệ với số đỉnh lớn hơn 10 nhỏ hơn 20 ...... 103
Bảng 3.6. Kết quả độ thích nghi ở một số thế hệ với số đỉnh lớn hơn 20.......................... 104
Bảng 3.7. Kết quả độ thích nghi ở một số thế hệ với số đỉnh nhỏ hơn 10 ......................... 105
Bảng 3.8. Kết quả độ thích nghi ở một số thế hệ với số đỉnh lớn hơn 10 nhỏ hơn 20 ...... 106
Bảng 3.9. Kết quả độ thích nghi ở một số thế hệ với số đỉnh lớn hơn 20.......................... 107
Bảng 3.10. Kết quả so sánh giữa GA và STM (%) ............................................................ 113
Bảng 3.11. Tỷ lệ % phát hiện đúng, sai với các ngưỡng khác nhau .................................. 114

viii

DANH MỤC CÁC TỪ VIẾT TẮT
Viết tắt

Ý nghĩa

AC

Thuật toán Aho-Corasick

AC-BM

Aho-Corasick Boyer-Moore

ACMS

Aho-Corasick with Magic states String matching

AC-OPT

Thuật toán Aho-Corasick – OPT

AC-RDF

Thuật toán Aho-Corasick – RDF

APWG

Anti Phishing Working Group

ARP

Address Resolution Protocol

ASCII

American Standard Code for Information Interchange

BDM

Thuật toán Backward Dawg Matching

BM

Thuật toán Boyer-Moore

BMH

Thuật toán Boyer-Moore Horspool

BO

Back - Office

BOM

Thuật toán Backward Oracle Matching

CIAC

Character Index Aho-Corasick

CW

Thuật toán Commentz-Walter

DDOS

Distributed Denial Of Service

DFA

Deterministic Finite Automata

DHCP

Dynamic Host Configuration Protocol

DNS

Domain Name Service

DOM

Document Object Model

DoS

Denial Of Service

DRDoS

Distributed Reflection DoS

GA

Genetic Algorithms

HIDS

Host – based IDS

HP

Honey Pots

HTML

HyperText Markup Language

ix

IDS

Intrusion Detection System

IP

Internet Protocol

IRC

Internet Relay Chat

KMP

Thuật toán Knuth-Morris-Pratt

KR

Thuật toán Karp-Rabin

MAC

Medium Address Control

MDH

Thuật toán Multi-Phase Dynamic Hash

NFA

Non-Deterministic Finite Automata

NIDS

Network - based Intrusion Detection System

NIPS

Network - based Intrusion Prevention System

PCA

Principle Component Analysis

PMT

Possible matching patterns

RSI

Thuật toán Recursive Shift Indexing

SBMH

Setwise Boyer Moore Horspool

SBOM

Set Backward Oracle Matching

SMB

Server Message Block

SMTP

Simple Mail Transfer Protocol

SNMP

Simple Network Management Protocol

STM

Simple Tree Matching

SVD

Singular Value Decomposition

TCP/IP

Transmission Control Protocol / Internet protocol

TCP/UDP

Transmission Control Protocol / User Datagram Protocol

TF-IDF

Term Frequency – Inverse Document Frequency

URL

Uniform Resource Locator

WM

Thuật toán Wu và Manner

XML

eXtensible Markup Language

Worm

Sâu, một loại virus máy tính

x

LỜI NÓI ĐẦU
Triển khai các ứng dụng và dịch vụ trên Internet là nhu cầu của rất nhiều
ngành kinh tế. Nhiều dịch vụ trực tuyến được phát triển mạnh mẽ trong thương mại
điện tử, thanh toán trực tuyến, kinh doanh, tài chính, công nghiệp, an ninh, y
tế,…cho phép người sử dụng truy cập, khai thác và chia sẻ thông tin mọi lúc mọi nơi.
Song song với những tiến bộ và lợi ích mang lại, Internet cũng là không gian rộng
mở cho kẻ xấu lợi dụng thực hiện những vụ tấn công, truy cập trái phép vào các hệ
thống máy tính và mạng của người dùng.
Theo báo cáo của các cơ quan an ninh mạng quốc tế, trong các năm gần đây,
chỉ trong năm 2012, thiệt hại về kinh tế do tội phạm mạng gây ra lên tới 388 tỷ USD
so với năm 2011 là 114 tỷ USD. Đặc biệt, số vụ tấn công mạng vào các hệ thống cơ sở
hạ tầng trọng yếu của nhiều quốc gia ngày càng gia tăng và không chỉ các thiết bị kết
nối Internet truyền thống, các thiết bị dân dụng như tivi thông minh, máy in,… cũng
trở thành mục tiêu tấn công mạng. Bên cạnh các yếu tố đe dọa an ninh truyền thống,
nguy cơ chiến tranh mạng đang trở nên hiện hữu. Đặc biệt đã có nhiều cuộc tấn công
trực tiếp vào các cơ quan trọng yếu của chính phủ, lấy đi nhiều tài liệu mật. Các thông
tin này hoặc bị công bố bừa bãi trên mạng gây bất lợi về mặt chính trị, tâm lý xã hội
hoặc bị sử dụng vào các mục đích chống lại chính phủ.
Mặt khác, nhiều cuộc tấn công vào ngân hàng trộm cắp từ các tài khoản lên tới
hàng trăm tỷ USD hay tấn công vào các công ty doanh nghiệp để đánh cắp các bí mật
kinh doanh, các bí quyết công nghệ mới gây ra các tổn hại lớn gấp bội. Năm 2013 là
năm nghi nhận các đợt tấn công DDoS với quy mô lớn nhất trong lịch sử (tháng
3/2013 với lưu lượng có lúc lên đến 300Gbps – trong khi lượng Internet ở Việt Nam
vào khoảng 361 Gbps) và cũng là năm chứng kiến vấn đề an ninh mạng trở nên căng
thẳng giữa các cường quốc với sự kiện PRISM, Ed Snowden. Đối với Việt Nam, là
quốc gia đứng vị trí 18/20 quốc gia có số người sử dụng Internet đông nhất trên thế
giới và đứng thứ 11 trên toàn cầu về các nguy cơ tấn công mạng. Số vụ tấn công chủ
đích gia tăng từ 77 cuộc mỗi ngày lên 82 cuộc mỗi ngày.

1

Hệ thống phát hiện xâm nhập mạng (Intrusion Detection System) có nhiệm vụ
phân tích các thông tin, theo dõi, phát hiện và ngăn chặn sự xâm nhập trái phép tài
nguyên 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. Có
nhiều cách tiếp cận khác nhau trong việc phát triển hệ thống IDS. Trong số đó, so
khớp mẫu là một kỹ thuật được sử dụng phổ biến trong các hệ thống phát hiện và ngăn
chặn xâm nhập mạng. Việc phát hiện các nguy cơ tiềm ẩn trong hệ thống phát hiện
xâm nhập mạng được thực hiện bằng cách so khớp nội dung gói tin với các mẫu đã
biết. Với sự đa dạng về số lượng các đợt tấn công, hình thức tấn công thì việc thu thập
đầy đủ các mẫu làm cho kích thước tập mẫu ngày càng tăng nhanh. Có rất nhiều thuật
toán so khớp mẫu [7][19] đã được sử dụng trong hệ thống phát hiện xâm nhập Snort
[4][5]. Tuy nhiên, các thuật toán này vẫn tồn tài một số vấn đề như hiệu năng giảm và
tiêu tốn nhiều thời gian thực hiện khi số lượng các mẫu tăng lên. Do vậy, việc nghiên
cứu cải tiến hay đề xuất các thuật toán so khớp mới đáp ứng việc so khớp đồng thời
nhiều mẫu trong các hệ thống phát hiện xâm nhập là một nhu cầu cấp thiết và đây là
mục tiêu thứ nhất của luận án này.
Một vấn đề khác cũng liên quan đến an toàn đó là vấn đề giả mạo (phishing
hay fake) nói chung và giả mạo web nói riêng. Giả mạo và phát tán trên mạng là một
loại tội phạm kỹ thuật xã hội đáng chú ý trên mạng. Giả mạo được báo cáo là vấn
nạn web lần đầu tiên vào năm 2001 của hiệp hội bảo vệ khách hàng, hiệp hội thương
mại liên bang của Mỹ và ngày nay nhóm làm việc chống giả mạo APWG (Anti
Phishing Working Group) đã đưa ra thông số những trang web giả đang tăng khoảng
50% mỗi năm.
Cũng giống như xâm nhập mạng, nhiệm vụ đầu tiên là phải nhận biết (phát
hiện) được các cuộc xâm nhập, việc đầu tiên để ngăn chặn và xóa bỏ các trang web giả
mạo là phát hiện ra chúng. Có rất nhiều các cách tiếp cận khác nhau để phát hiện các
trang web giả mạo. Các tác giả trong [17] sử dụng thuật toán TF-IDF (Term Frequency
/ Inverse Document Frequency) để xác định những từ khóa của một trang web, những
từ khóa này được đưa vào một máy tìm kiếm chẳng hạn Google và lấy ra nhóm những
URL trên cùng. Nếu trang web bị nghi ngờ nằm trong nhóm đó thì trang nay được coi
là hợp lệ, ngược lại nó sẽ bị cho là lừa đảo vì hầu hết các trang lừa đảo không có thứ
hạng cao trong các kết quả của máy tìm kiếm. Thuật toán này được ứng dụng trong

2

giải pháp Cantina [46] được phát triển bởi các nhà nghiên cứu của Đại học Carnegie
Mellon với việc sử dụng năm từ khóa có tần suất xuất hiện cao nhất trong trang. Nhóm
các nhà nghiên cứu thuộc Đại học Iowa [47] sử dụng là thuật toán lọc Bayesian. Lợi
thế chính của thuật toán này là có khả năng phát hiện được những đối tượng chưa từng
nhìn thấy trước đó. Việc sử dụng phép lọc Bayesian là một giải pháp hứa hẹn cho việc
phát hiện lừa đảo 0 ngày (zero-day) vì nó có thể phát hiện những trang web lừa đảo
mới và không dựa trên một danh sách đen. Một số tác giả ở Hồng Kông [48] quan tâm
đến thuật toán phát hiện sự giống nhau của hai trang web về mặt hình ảnh. Hướng tiếp
cận này kiểm tra sự hiển thị tương đồng của một trang web và so sánh những đặc trưng
hiển thị của nó với một trang web hợp lệ. Trong nghiên cứu mới nhất của mình, Kranti
và các đồng nghiệp đã đề xuất một giải pháp chống giả mạo mới bằng cách sử dụng
hai thuật toán K-mean và Naïve Bayes [49].
Một đặc tính nổi bật nhất của trang web giả mạo là nó phải tương tự như trang
web gốc. Điều này có nghĩa là hai trang web gốc và web giả mạo có cấu trúc giống
nhau. Mặt khác, DOM là tên gọi tắt của Document Object Model - Mô hình đối tượng
tài liệu - là một chuẩn được định nghĩa bởi W3C [22] dùng để truy xuất và thao tác
trên các tài liệu có cấu trúc dạng HTML hay XML bằng các ngôn ngữ lập trình như
Javascript, PHP, Python,... Do vậy, để so sánh hai trang web với nhau chúng ta có thể
so sánh hai DOM-Tree tương ứng của chúng. Vì vậy mục tiêu thứ hai của luận án là
nghiên cứu các phương pháp để so sánh nhanh nhất và hiệu quả nhất xem hai DOMTree có giống nhau hay không, tổng quát hơi là sẽ nghiên cứu việc so khớp hai đồ thị
với nhau vì “cây” chỉ là một dạng đặc biệt của đồ thị rồi áp dụng các kết quả của việc
so khớp đồ thị vào so khớp hai DOM-Tree với nhau.
Liên quan đến việc giải quyết vấn đề nêu trên, luận án hướng đến hai mục tiêu
chính như sau:
(1)

Nghiên cứu về hệ thống phát hiện xâm nhập. Phát triển và áp dụng các
thuật toán so khớp mẫu vào việc xây dựng các hệ thống phát hiện xâm
nhập.

(2)

Nghiên cứu về giả mạo Web. Phát triển các thuật toán so khớp đồ thị và
ứng dụng vào việc phát hiện các trang Web giả mạo.

Với mục tiêu (1), luận án sẽ:

3

(i)

Phân tích đánh giá về hiệu năng cũng như thời gian thực hiện các thuật
toán so khớp mẫu hiện có trên hệ thống phát hiện thâm nhập Snort;

(ii)

Đưa ra các cải tiến cho thuật toán so khớp đa mẫu Aho-Corasick bằng
cách sử dụng kỹ thuật nén dòng và bảng chỉ số nhằm nâng cao hiệu quả
của thuật toán, các phân tích và so sánh thực tế nhằm kiểm nghiệm lý
thuyết cũng đã được thực hiện trên hệ thống Snort;

(iii)

Đề xuất một thuật toán so khớp đa mẫu mới bằng cách xây dựng biểu đồ
của các mẫu kết hợp với danh sách liên kết làm giảm thời gian thực hiện
việc so khớp đồng thời đa mẫu. Việc cài đặt thực nghiệm của thuật toán
so sánh với một số thuật toán đã tồn tại cũng đã triển khai trên hệ thống
Snort.

Với mục tiêu (2), do cây là một dạng đặc biệt của đồ thị, vì vậy với mục tiêu
thứ hai, luận án nghiên cứu bài toán tổng quát hơn đó là so khớp đồ thị. Với mục tiêu
này, các kết quả của luận án đạt được là:
(i)

Đưa ra thuật toán mới dựa trên thuật toán di truyền để so khớp các đồ thị
không chính xác, thuật toán mới có thể áp dụng đối với lớp đồ thị vô
hướng, có hướng, có trọng số hay gán nhãn.

(ii)

Áp dụng việc so khớp đồ thị vào việc so khớp các DOM-Tree để phát
hiện các trang Web giả mạo.

Với các mục tiêu của luận án như trên, ngoài phần mở đầu, luận án được tổ
chức thành ba chương như sau.
-

Chương 1 trình bày tổng quan về so khớp chuỗi và so khớp đồ thị cùng các
ứng dụng. Trong đó, luận án tập trung giới thiệu các thuật toán so khớp đơn
mẫu và đa mẫu, so khớp chính xác và không chính xác được áp dụng trong
việc phát hiện xâm nhập mạng;

-

Chương 2 giới thiệu về các kỹ thuật xâm nhập mạng. Luận án đã phân tích,
đánh giá một số hướng tiếp cận liên quan đến hệ thống phát hiện xâm nhập
mạng để thấy được ưu, nhược điểm của từng giải pháp. Từ đó xác định được
mục tiếp, cách tiếp cận của luận án là. Luận án đã trình bày hai cải tiến thuật
toán bằng kĩ thuật nén dòng và bảng chỉ số, và đưa ra thuật toán mới dựa trên
kĩ thuật con trỏ được ứng dụng trong hệ thống phát hiện xâm nhập mạng.

4

-

Chương 3 luận án giới thiệu về các kỹ thuật giả mạo trang web. Từ đó đề xuất
ứng dụng thuật toán di truyền trong việc so khớp đồ thị, ứng dụng việc so
khớp đồ thị trong so sánh cây DOM để phát hiện giả mạo trong mạng.
Cuối luận án là phần kết luận và hướng phát triển của luận án. Danh mục các tài

liệu tham chiếu, trích dẫn và tham khảo của luận án, cùng danh sách các tài liệu do
nghiên cứu sinh công bố cùng tập thể cán bộ nghiên cứu, giáo viên hướng dẫn, được
liệt kê cuối luận án.

5

CHƯƠNG 1. TỔNG QUAN VỀ SO KHỚP
Trong bối cảnh tiến trình hội nhập, vấn đề an ninh mạng và bảo mật dữ liệu
đang trở nên rất được quan tâm. Khi cơ sở hạ tầng và các công nghệ mạng đã đáp ứng
tốt các yêu cầu về băng thông, chất lượng dịch vụ, đồng thời thực trạng tấn công trên
mạng đang ngày một gia tăng thì vấn đề bảo mật càng được chú trọng hơn. Không chỉ
các nhà cung cấp dịch vụ Internet, các cơ quan chính phủ mà các doanh nghiệp, tổ
chức cũng có ý thức hơn về an toàn thông tin.
Triển khai các ứng dụng và dịch vụ trên Internet cần có các cơ chế bảo vệ chặt
chẽ, an toàn, nhằm góp phần duy trì tính bền vững cho hệ thống thông tin của doanh
nghiệp đó. Tất cả chúng ta đều hiểu rằng giá trị thông tin của doanh nghiệp là tài sản
vô giá. Không chỉ thuần túy về mặt vật chất, những giá trị khác không thể đo đếm
được như uy tín của họ với khách hàng sẽ ra sao, nếu những thông tin giao dịch với
khách hàng bị đánh cắp, rồi sau đó bị lợi dụng với những mục đích khác nhau,… Các
thông tin và các dịch vụ này làm cho mạng máy tính trở thành mục tiêu hấp dẫn cho sự
lạm dụng và tổn thương đến cộng đồng người sử dụng. Thêm nữa, giả mạo trên mạng
là một loại tội phạm kỹ thuật xã hội đáng chú ý trên mạng. Giả mạo được báo cáo là
vấn nạn Web lần đầu tiên vào năm 2001 của hiệp hội bảo vệ khách hàng, hiệp hội
thương mại liên bang của Mỹ và ngày nay nhóm làm việc chống giả mạo APWG đã
đưa ra cảnh báo những trang Web giả đang tăng khoảng 50% mỗi năm.
Vì thế, bên cạnh việc phát triển các dịch vụ và ứng dụng trên mạng, an ninh
thông tin và an toàn hệ thống là một vấn đề hết sức quan trọng cần được quan tâm
nghiên cứu thường xuyên. Vấn đề an ninh thông tin và an toàn hệ thống bao gồm rất
nhiều chủ đề, tuy nhiên luận án này chỉ tập trung nghiên cứu chính về các thuật toán so
khớp ứng dụng trong phát hiện xâm nhập mạng và sự giả mạo trên mạng.

1.1. So khớp chuỗi
1.1.1. Bài toán so khớp chuỗi
So khớp chuỗi (hay đối sánh chuỗi) là việc so sánh một hoặc một vài chuỗi
(thường được gọi là mẫu hoặc pattern) với văn bản để tìm nơi và số lần xuất hiện của

6

chuỗi đó trong văn bản. Gọi Y là tập các dữ liệu và X là một mẫu. So khớp mẫu
(Pattern Matching) là tìm ra tất cả các lần xuất hiện của mẫu X trong tập dữ liệu Y.
Trong [7], bài toán so khớp mẫu được mô tả như sau: Cho một bảng chữ cái Σ
là một tập hữu hạn các ký tự, một mẫu P (P [1..m]) độ dài m và một chuỗi ký tự T (T
[1..n]) độ dài n (trong đó m<trong T hoặc P có khớp với một chuỗi con của T hay không?
Gọi Σ là một tập hữu hạn các ký tự. Thông thường, các ký tự của cả mẫu tìm
kiếm và đoạn văn bản gốc đều nằm trong Σ. Tập Σ tùy từng ứng dụng cụ thể có thể là
bảng chữ cái tiếng Anh từ A đến Z thông thường, cũng có thể là một tập nhị phân chỉ
gồm hai phần tử 0 và 1 (Σ = {0,1}) hay có thể là tập các ký tự DNA trong sinh học (Σ
= {A,C,G,T}). Phương pháp đầu tiên và đơn giản nhất có thể nghĩ đến ngay là lần lượt
xét từng vị trí i trong xâu ký tự gốc từ 1 đến n-m+1, so sánh T[i…(i+m-1)] với P[1..m]
bằng cách xét từng cặp ký tự một và đưa ra kết quả tìm kiếm. Dễ thấy độ phức tạp của
thuật toán là O(n*m)
Các thuật toán so khớp thường sử dụng cơ chế cửa sổ trượt (một khung có kích
thước bằng với kích thước của mẫu cần tìm) để so sánh các ký tự của mẫu trong cửa sổ
với các ký tự trong văn bản. Tất cả các thuật toán so khớp chuỗi đều có hai giai đoạn
là: tiền xử lý và tìm kiếm. Việc đánh giá các thuật toán được thực hiện dựa trên dung
lượng bộ nhớ sử dụng và tốc độ so khớp. Các thuật toán so khớp được phân loại theo
cách tiếp cận xây dựng thuật toán và số lượng mẫu. Các thuật toán so khớp chuỗi có
thể phân loại theo nhiều tiêu chí:
Dựa trên số lượng mẫu, chúng ta có hai loại: so khớp đơn mẫu (single pattern)
và so khớp đa mẫu (multiple patterns). Các thuật toán so khớp đơn mẫu chỉ tiến hành
so sánh lần lượt từng mẫu P trên văn bản T, còn so khớp đa mẫu cho phép so sánh
cùng lúc nhiều mẫu Pi (i=1..k) trên văn bản T. Các thuật toán so khớp đã mẫu thường
là những cải tiến của so khớp đơn mẫu nhằm nâng cao hiệu quả so khớp.
Dựa trên cơ sở thứ tự so sánh: thuật toán so khớp chuỗi có thể được thực hiện
theo các thứ tự sau: từ trái sang phải, từ phải sang trái, so sánh tại vị trí cụ thể và so
sánh không theo thứ tự nhất định.

7

Dựa trên độ chính xác của kết quả so khớp: các thuật toán so khớp được chia
thành hai loại: so khớp chính xác (Extract String Matching) và so khớp gần đúng
(Approximate String Matching). So khớp chính xác là khẳng định mẫu P có xuất hiện
ở trong chuỗi T hay không? Còn thuật toán so khớp xấp xỉ chỉ đánh giá sự tương đồng
của mẫu P so với mẫu T dựa trên một hàm đo khoảng cách nào đó. Đa số các thuật
toán so khớp không chính xác sử dụng khoảng cách Hamming hay khoảng cách
Levenshtein với k vị trí khác biệt được thiết lập trước [65].
Dựa trên cơ sở thiết kế thuật toán: Các thuật toán so khớp được chia thành ba
loại:
-

So khớp dựa trên tiền tố (prefix)

-

So khớp dựa trên hậu tố (suffix) và

-

So khớp dựa trên các nhân tố (factor).
Chuỗi văn bản T

Mẫu P
Cửa sổ trượt

Hình 1.1. So khớp dựa trên tiền tố

Quá trình so khớp của thuật toán so khớp dựa trên tiền tố được thực hiện bằng
cách tìm kiếm từ đầu cửa sổ trượt, tất cả các ký tự trong văn bản T đều được đọc và
kiểm tra, nếu không khớp thì dịch chuyển sang ký tự tiếp theo. Đây là chiến lược đơn
giản nhất nhưng số lượng phép so sánh lớn nên tốc độ thực hiện chậm (xem Hình 1.1).
Thuật toán so khớp dựa trên hậu tố thực hiện bằng cách tìm kiếm từ cuối cửa sổ
trượt, chúng ta không đọc tất cả các ký tự liên tiếp trong văn bản T mà dịch hay bỏ qua
các ký tự dựa vào kết quả so sánh các ký tự ở cuối cửa sổ (xem Hình 1.2). Đây là cơ sở
để giảm số lượng phép so sánh và giảm độ phức tạp của thuật toán.

8


Xemtailieu.com không chịu trách nhiệm liên quan đến các vấn đề bản quyền tài liệu được thành viên tự nguyện đăng tải lên.