NGUYỄN THỊ BÍCH NGỌC
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

NGUYỄN THỊ BÍCH NGỌC
HỆ THỐNG THÔNG TIN 2012 – 2013 HÀ NỘI
NGHIÊN CỨU THUẬT TOÁN ĐỐI SÁNH CHUỖI LAI
VÀ ỨNG DỤNG TRONG PHÁT HIỆN ĐỘT NHẬP
LUẬN VĂN THẠC SĨ KỸ THUẬT
HÀ NỘI - 2014
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

NGUYỄN THỊ BÍCH NGỌC
NGHIÊN CỨU THUẬT TOÁN ĐỐI SÁNH CHUỖI LAI
VÀ ỨNG DỤNG TRONG PHÁT HIỆN ĐỘT NHẬP
Chuyên ngành: Hệ thống thông tin
Mã số: 60.48.01.04
LUẬN VĂN THẠC SĨ KỸ THUẬT
NGƯỜI HƯỚNG DẪN KHOA HỌC : TS. HOÀNG XUÂN DẬU
HÀ NỘI - 2014
3
LỜI CAM ĐOAN
Tôi 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 văn là trung thực và chưa từng được ai
công bố trong bất kỳ công trình nào khác.
Tác giả luận văn ký và ghi rõ họ tên
Nguyễn Thị Bích Ngọc
4
5
LỜI CẢM ƠN
Để hoàn thành được luận văn, ngoài sự nghiên cứu và cố gắng của bản thân,
em xin gửi lời cảm ơn tới TS Hoàng Xuân Dậu _ giáo viên trực tiếp hướng dẫn, tận

Giao thức điều khiển
thông điệp Internet
TCP Transmission Control Protocol Giao thức điều khiển
truyền vận
NIDS Network – based Intrusion
Detection
Hệ thống phát hiện đột
nhập cho mạng
P Pattern Mẫu
RK Rabin – Karp algorithm Thuật toán Rabin Karp
T Text Văn bản
8
DANH MỤC CÁC HÌNH
Số hiệu hình vẽ Tên hình vẽ Trang
1.1 Các dạng phần mềm phá hoại 7
1.2 Minh họa kiểu tấn công gián đoạn 9
1.3 Minh họa tấn công nghe trộm 10
1.4 Minh họa tấn công thay đổi gói tin 10
1.5 Minh họa tấn công giả mạo 10
1.6 NIDS 12
1.7 HIDS 13
1.8 Các thành phần của hệ thống phát hiện đột nhập 14
1.9 Bước kiểm tra của phát hiện đột nhập dựa trên chữ ký 15
1.10 Bước kiểm tra của phát hiện đột nhập dựa trên bất thường 15
1.11 Mô hình mô tả bài toán luận văn 16
2.1 Xây dựng hàm Goto 39
2.2 Xây dựng hàm Failure 40
2.3 Xây dựng hàm Output 40
2.4 Ví dụ xây dựng hàm goto 41
2.5 Ví dụ xây dựng hàm Failure 45

hợp của hai thuật toán đối sánh chuỗi Horspool [5] và Karp-Rabin [8] với mục tiêu
tăng tốc độ đối sánh chuỗi trong đề tài "Nghiên cứu thuật toán đối sánh chuỗi lai và
ứng dụng trong phát hiện đột nhập mạng". Tuy nhiên, khi triển khai nghiên cứu
thực tế, kết quả đánh giá cho thấy thuật toán đối sánh chuỗi đa mẫu Aho-Corasick
[1] có hiệu năng vượt trội so với thuật toán đối sánh chuỗi lai. Được sự đồng ý của
thầy hướng dẫn, tác giả đã sử dụng thuật toán đối sánh chuỗi đa mẫu Aho-Corasick
thay cho thuật toán đối sánh chuỗi lai để cài đặt thử nghiệm trong luận văn.
2. Luận văn bao gồm 3 chương và phần kết luận:
Chương 1: Tổng quan về đối sánh chuỗi và ứng dụng trong phát hiện đột
nhập:
10
Giới thiệu tổng quan về đối sánh chuỗi, phát hiện đột nhập, và ứng dụng
của đối sánh chuỗi vào phát hiện đột nhập.
Chương 2: Các kỹ thuật đối sánh chuỗi:
Trình bày chi tiết về các kỹ thuật đối sánh chuỗi.
Chương 3: Xây dựng mô hình phát hiện đột nhập dựa vào đối sánh chuỗi:
Chương này trình bày việc xây dựng mô hình phát hiện đột nhập ứng dụng
các kỹ thuật đối sánh chuỗi đã nghiên cứu ở chương 2 và việc áp dụng kỹ thuật đối
sánh chuỗi vào hệ thống Snort.
3. Mục đích nghiên cứu
• Nghiên cứu các thuật toán đối sánh chuỗi và ứng dụng.
• Nghiên cứu thuật toán đối sánh chuỗi đa mẫu hiệu năng cao.
• Xây dựng mô hình phát hiện đột nhập mạng dựa trên thuật toán đối sánh
chuỗi đa mẫu hiệu năng cao, cài đặt thử nghiệm và đánh giá kết quả.
4. Đối tượng và phạm vi nghiên cứu
• Đối tượng nghiên cứu: các thuật toán đối sánh chuỗi, các chuỗi hoặc mẫu
chữ ký tấn công/đột nhập, các luật phát hiện tấn công đột nhập.
• Phạm vi nghiên cứu: Nghiên cứu giới hạn trong môi trường mô phỏng và
thực.
5. Phương pháp nghiên cứu

P xuất hiện với độ dịch s (bắt đầu tại s+1) :
P[1] = T[s+1], P[2] = T[s+2],… , P[m] = T[s+m].
Do đó, chúng ta gọi s là giá trị dịch, ngược lại, chúng ta gọi là không có
giá trị dịch.
Ví dụ:
12
P = “abab” , T = “abcabababbc”, P xuất hiện tại s = 3 và s = 5.
Theo tính chính xác của phép đối sánh, có 2 loại đối sánh chuỗi:
- Đối sánh chuỗi chính xác (Exact string matching):
Cho một chuỗi văn bản T có độ dài n, và một chuỗi mẫu P có độ dài m.
Bài toán đối sánh chuỗi chính xác chính là việc tìm ra sự xuất hiện chính xác của P
trong T.
Ví dụ: T = “DABCDEADBACABAD” P = “AB”
- Đối sánh chuỗi gần đúng (Approximate string matching):
Tìm một chuỗi phù hợp với mẫu gần đúng (chứ không phải là chính xác)
mà sự so khớp là tốt nhất với mẫu. Một vài sai khác có thể chấp nhận được.
Chính thức hơn : Đưa một văn bản T, một mẫu P, và một hàm khoảng
cách D. Tìm tất cả các chuỗi con s của T sao cho D(s, P) < k.
Sự sai khác cho phép được ở đây có thể là :
• Thêm (ran  rain) .
• Bớt (brain  rain) .
• Thay thế (brain  train)
Ví dụ: T = “brainaaranastraindshanb” P = “ran”.
1.1.3 Lịch sử phát triển
Trong năm 1970, S.A. Cook [2] đã chứng minh một kết quả lý thuyết giúp
suy ra sự tồn tại của một thuật toán để giải bài toán đối sánh mẫu có thời gian tỷ lệ
với (M+N) trong trường hợp xấu nhất.
D.E.Knuth và V.R.Pratt [2] đã kiên trì theo đuổi kiến trúc mà Cook đã
dùng để chứng minh cho định lý của ông và nhận được một thuật toán tương đối
đơn giản. Đồng thời J.H.Morris [2] cũng khám phá ra thuật toán này.

• Các thuật toán điển hình bao gồm Shift – Or, …
14
Thuật toán băm (Hashing algorithms): là các thuật toán sử dụng kỹ thuật
băm, tránh việc so sánh các ký tự có độ phức tạp bậc 2.
• Các thuật toán điển hình bao gồm Karp – Rabin.
1.1.6 Độ phức tạp tính toán
Độ phức tạp tính toán của thuật toán phụ thuộc vào 3 yếu tố sau: chiều dài
của mẫu, chiều dài của văn bản, độ lớn của tập các ký tự.
Trên thực tế có nhiều loại ký tự khác nhau như: binary, DNA, Alphabet,
numeric… và mỗi loại ký tự có độ phức tạp khác nhau.
Độ phức tạp tính toán tỉ lệ thuận với chiều dài của mẫu, chiều dài của văn
bản và độ lớn của tập các ký tự.
1.1.7 Ứng dụng của đối sánh chuỗi
Đối sánh chuỗi là một trong những bài toán cơ bản và “tự nhiên” nhất của
ngành Tin học. Đối sánh chuỗi được sử dụng rộng rãi trong nhiều ứng dụng và lĩnh
vực khác nhau như:
• Chức năng search trong các trình soạn thảo văn bản và web browser.
• Các công cụ tìm kiếm như: Google Search, Yahoo Search,….
• Sinh học phân tử như trong tìm kiếm các mẫu trong DNA, protein,….
• Tìm kiếm cơ sở dữ liệu như trong GenBank [7].
• Trong nhiễu kênh với cho phép chấp nhận được.
• Trong tìm kiếm mẫu hoặc vết của tấn công, đột nhập và các phần mềm độc hại
trong lĩnh vực an toàn mạng và an toàn thông tin….
1.2 Tổng quan về đột nhập và phát hiện đột nhập
Tấn công (attack) hay đột nhập (intrusion) lên một hệ thống chính là sự vi
phạm chính sách an toàn bảo mật của hệ thống đó. Tùy thuộc vào yêu cầu bảo mật
của mỗi hệ thống mà một tấn công, đột nhập có thể vi phạm một, hoặc nhiều thuộc
tính bảo mật của hệ thống.
1.2.1 Các dạng tấn công, đột nhập
Ngày nay, tấn công, đột nhập vào hệ thống máy tính, mạng và thông tin

năng nhân bản và lây lan trên toàn bộ hệ thống. Nếu virus chưa gây ra những hậu
quả hữu hình, thì người dùng không thể nhận biết được sự có mặt của chúng. Một
số dấu hiệu nhận biết có sự tồn tại của virus : xuất hiện thông báo lạ; phát hiện một
số tệp nào đó bị phá hoại; hệ điều hành trở nên chậm chạp, bị xung đột hoặc không
thể khởi động được. Một số loại virus ẩn mình trong một khoảng thời gian và sau
đó được kích hoạt vào một ngày định trước nào đó. Một số loại virus có khả năng
lây nhiễm vào các tệp thực thi, các tệp kịch bản, các tệp tài liệu, hoặc lây nhiễm vào
phân vùng khởi động hay một phân vùng nào đó của một ổ đĩa. Một số loại virus
được nạp vào bộ nhớ và sau đó tiếp tục lây nhiễm vào các tệp khác đang được thực
thi.
Các phần mềm phá hoại độc lập chương trình chủ bao gồm 2 dạng chính
là Worm và Zombie.
• Worm: Là một chương trình độc lập, có khả năng tự nhân bản giống như virus máy
tính, chúng sử dụng mạng Internet để tự lây lan sang các máy tính khác trên mạng
mà không cần sự tác động của người dùng. Hầu hết Worm được dùng để khai thác
khả năng truyền thông của mạng và thường mang theo các phần mềm gián điệp để
tạo backdoor trên các máy tính bị nhiễm.
• Zombie: Là một chương trình độc lập có thể điều khiển từ xa một cách trực tiếp
hoặc gián tiếp bởi tin tặc. Zombie cũng có khả năng lây nhiễm vào các máy tính kết
nối Internet khác tạo thành một hệ thống mạng các máy tính "ma", hay các botnet
chịu sự điều khiển của tin tặc. Tin tặc có thể sử dụng các botnet để gửi thư rác, hoặc
thực hiện các cuộc tấn công DDoS với quy mô rất lớn.
17
1.2.1.2 Các dạng tấn công máy tính, mạng
Hiện nay, các dạng tấn công mạng rất đa dạng và tinh vi, nhưng có thể
chia các dạng tấn công thành 4 loại chính: tấn công gián đoạn, tấn công nghe trộm,
tấn công thay đổi và tấn công giả mạo.
• Tấn công gián đoạn (Interruption) là tấn công lên tính khả dụng của hệ thống. Đây
là hình thức tấn công dễ phát hiện nhất, làm ngắt kết nối giữa 2 trạm trên mạng.
Hình 1.2 Minh họa kiểu tấn công gián đoạn

1.2.2.1 Phân loại phương pháp phát hiện đột nhập
Có hai phương pháp khác nhau để phân loại phát hiện đột nhập: Phân loại
dựa trên kỹ thuật phân tích dữ liệu và Phân loại dựa trên nguồn dữ liệu.
a. Phân loại dựa trên kỹ thuật phân tích dữ liệu:
Dựa trên kỹ thuật phân tích dữ liệu, có thể chia phát hiện đột nhập thành
phát hiện đột nhập dựa trên các dấu hiệu hoặc chữ ký và phát hiện đột nhập dựa trên
bất thường.
• Phát hiện đột nhập dựa trên các dấu hiệu (còn gọi là chữ ký): Phương pháp này
nhận dạng các sự kiện hoặc tập hợp các sự kiện phù hợp với một mẫu các sự kiện
đã được định nghĩa là tấn công hoặc đột nhập. Phát hiện đột nhập dựa trên chữ ký
có khả năng phát hiện hiệu quả các tấn công, đột nhập đã biết, nhưng không có khả
năng phát hiện các tấn công, đột nhập mới do chữ ký của chúng chưa được định
nghĩa.
• Phát hiện đột nhập dựa vào bất thường: Phương pháp này thiết lập một hồ sơ các
hành vi bình thường của đối tượng cần giám sát. Nếu hành vi hiện tại của đối tượng
cần giám sát khác biệt đủ lớn với hồ sơ các hành vi bình thường, có thể kết luận có
tấn công, đột nhập xảy ra. Phát hiện đột nhập dựa trên bất thường có tiềm năng phát
hiện các tấn công, đột nhập mới do nó không yêu cầu có trước các thông tin về tấn
công, đột nhập. Tuy nhiên, phương pháp này thường có tỷ lệ cảnh báo sai cao và
yêu cầu chi phí tính toán lớn để xây dựng hồ sơ các hành vi bình thường.
b. Phân loại dựa trên nguồn dữ liệu:
Dựa trên nguồn dữ liệu, có thể chia các hệ thống phát hiện đột nhập thành
hệ thống phát hiện đột nhập mạng và hệ thống phát hiện đột nhập máy trạm.
• Hệ thống phát hiện đột nhập mạng (Network – based instrusion detection system -
NIDS) có khả năng phát hiện đột nhập cho một mạng hoặc một phần mạng. Nguồn
dữ liệu thu nhập là các thông tin về lưu lượng mạng được lấy từ hub, switch, hoặc
router đã được cấu hình để theo dõi cổng hoặc các nút mạng.
Ưu điểm của NIDS:
 Quản lý được cả một đoạn mạng (gồm nhiều host).
20

 Cần tài nguyên trên host để hoạt động.
 Có thể không hiệu quả khi bị tấn công DoS.
1.2.2.2 Các thành phần của hệ thống phát hiện đột nhập
Các hệ thống phát hiện đột nhập khác nhau thường dựa vào việc phát hiện
các dấu hiệu của xâm nhập trái phép, hoặc những hành động dị thường. Một hệ
thống phát hiện đột nhập điển hình thường gồm 3 thành phần chính: Bộ phận thu
thập thông tin, bộ phận phân tích và bộ phận phản ứng/cảnh báo, như minh họa trên
hình 1.8.
• Bộ phận thu nhập thông tin (Information collection): Thu thập các thông tin cho
phát hiện đột nhập, như các gói tin truyền trên mạng, các logs hệ thống.
• Bộ phận phân tích (Analysis) : Phân tích thông tin đã thu thập để nhận biết hành
động nào là tấn công, đột nhập.
• Bộ phận phản ứng/ cảnh báo (Response) : Cảnh báo tấn công, đột nhập được phân
tích ở trên đến người quản trị hệ thống.
22
Hình 1.8 Các thành phần của hệ thống phát hiện đột nhập
1.3 Ứng dụng đối sánh chuỗi trong phát hiện đột nhập
Các phương pháp phát hiện đột nhập thường được triển khai thành hai
bước: bước huấn luyện và bước kiểm tra. Trong bước huấn luyện, chúng ta thu
được một tập các hành vi bình thường của hệ thống hoặc tập các chữ ký (các mẫu)
đột nhập đã biết – những thông tin thường được biểu diễn dưới dạng các chuỗi.
Trong bước kiểm tra, các kỹ thuật đối sánh chuỗi khác nhau được áp dụng để so
sánh hành vi hiện tại của hệ thống với tập hành vi thu được ở bước huấn luyện, và
đưa ra kết quả hành vi hiện tại là đột nhập hay không. Độ chính xác và hiệu năng
của các phương pháp đối sánh chuỗi có ảnh hưởng quyết định đến hiệu quả của phát
hiện đột nhập.
Hình 1.9 mô tả bước kiểm tra của kỹ thuật phát hiện đột nhập dựa trên chữ
ký. Hành vi hiện tại của hệ thống trích trọn từ thông tin đầu vào (Audit Data) được
so sánh với tập các chữ ký đột nhập đã biết. Nếu tìm thấy sự trùng hợp, một đột
nhập được phát hiện.

2.1 Phân loại các kỹ thuật đối sánh chuỗi
Có nhiều cách để phân loại các kỹ thuật đối sánh chuỗi. Căn cứ vào số
lượng mẫu sử dụng, các kỹ thuật đối sánh chuỗi có thể được chia thành 3 loại: đối
sánh sử dụng đơn mẫu, đối sánh sử dụng đa mẫu với số lượng có hạn, đối sánh sử
dụng đa mẫu với số lượng vô hạn.
Các kỹ thuật đối sánh chuỗi sử dụng đơn mẫu chỉ cho phép một mẫu trong
mỗi phép đối sánh.
• Một số kỹ thuật đối sánh chuỗi sử dụng đơn mẫu là: thuật toán sơ khai (Naïve string
matching), thuật toán Knuth – Morris – Pratt, thuật toán Boyer – Moore – Horspool,
thuật toán Rabin – Karp,…
Các kỹ thuật đối sánh chuỗi sử dụng đa mẫu với số lượng hữu hạn cho
phép một số mẫu nhất định trong mỗi phép đối sánh
• Một số kỹ thuật đối sánh chuỗi sử dụng đa mẫu với số lượng có hạn là: thuật toán
Commentz – Walter, thuật toán Aho – Corasick,…
Các kỹ thuật đối sánh chuỗi sử dụng đa mẫu với số lượng vô hạn cho phép
không hạn chế số mẫu nhất định trong mỗi phép đối sánh .
• Dĩ nhiên, các mẫu không được liệt kê cụ thể trong trường hợp này. Chúng thường
được biểu diễn bởi cấu trúc thông thường hoặc một biểu thức thông thường.
Ngoài cách phân loại trên còn có các cách phân loại khác như: Kỹ thuật
đối sánh chuỗi chính xác và Kỹ thuật đối sánh chuỗi gần đúng; Kỹ thuật đối sánh
chuỗi có tiền xử lý dữ liệu và Kỹ thuật xử lý chuỗi không có tiền xử lý dữ liệu; Kỹ
thuật xử lý chuỗi từ trái qua phải và Kỹ thuật xử lý chuỗi từ phải qua trái,…