1
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
_______________________ Lê Đăng Nguyên NGHIÊN CỨU MỘT SỐ KỸ THUẬT
PHÁT HIỆN GIẢ MẠO TRÊN WEB

Chuyªn ngµnh : Cơ sở toán học cho Tin học
M· sè: 62 46 01 10 DỰ THẢO TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC
Hà Nội - 2014


của công nghệ thông tin và truyền thông. 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.
Hệ thống phát hiện xâm nhập mạng IDS (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
Error! Reference source not found.,50] đã được sử dụng trong hệ thống phát hiện xâm
nhập Snort Error! Reference source not found.,6]. 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. Với mục tiêu
này, luận án đã (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 đơn mẫu 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) Luận án
cũng đề 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 với trong sự 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.

Internet đã mở ra một làn sóng mới về xu hướng phát triển của xã hội - thời đại
của công nghệ thông tin và truyền thông. 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. Tất cả 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. Nói cách khác,
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, đột nhập, 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. 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ủ đề, do vậy luận án này chỉ tập trung nghiên
cứu chính về phát hiện xâm nhập mạng và sự giả mạo trên mạng.
1.2 Xâm nhập trái phép
1.2.1 Một số kỹ thuật xâm nhập trái phép
Tấn công (attack) là sự vi phạm chính sách an toàn bảo mật của hệ thống đó. Có rất
nhiều kỹ thuật được dùng để xâm nhập mạng như: - Trap-door; Logic Bomb; Trojan
Horse; Worm; Zombies; Man-in-the-Middle; Eavesdropping;IP Address Spoofing/ Identity
Spoofing
1.2.2 Một số giải pháp kỹ thuật ngăn chặn xâm nhập
Các biện pháp ngăn chặn đột nhập được sử dụng khá phổ biến gồm tường lửa,
xác thực, mã hóa,
Tường lửa (Firewall): Mã hóa dữ liệu (Data Encryption); Xác thực
(Authentication); Quyền truy cập (Access Rights):
1.2.3 Hệ thống phát hiện xâm nhập trái phép
1.2.3.1. Hệ thống phát hiện xâm nhập mạng
1.2.3.2. Phân loại hệ thống phát hiện xâm nhập mạng
5
Người ta thường phân loại các hệ thống IDS dựa trên nguồn cung cấp dữ liệu
cho phát hiện đột nhập. Có hai loại hệ thống phát hiện đột nhập (IDS) cơ bản:

1.3.3. Một số nghiên cứu liên quan đến giả mạo web
Phần lớn các trang web giả mạo đều cố gắng bắt trước các trang web hợp lệ đến
mức tốt nhất có thể để người dùng có đủ tự tin tiết lộ những thông tin nhạy cảm. Hầu
hết các trang lừa đảo đều làm tốt việc tạo giao diện hợp lệ bằng cách sao chép cách bố
trí trang, font, kiểu, logo và thậm chí các thông tin bảo mật của trang hợp lệ. Thực tế,
nhiều liên kết trong trang lừa đảo vẫn thực sự kết nối đến trang hợp lệ, điều này khiến
nó giống với các trang hợp lệ hơn.
Nhìn chung, cách tiếp cận để phát hiện các trang web giả mạo bước đầu là kiểm
tra xem “hình dáng” hay cấu trúc của chúng có giống nhau không, nếu giống thì sẽ sử
dụng thêm một số kỹ thuật khác để làm rõ các chi tiết kỹ thuật để phát hiện đó là trang
web giả mạo hay trang web hợp lệ. Mặt khác, DOM là tên gọi tắt của Document
Object Model - tạm dịch Mô hình đối tượng tài liệu - là một chuẩn được định nghĩa
bởi W3C Error! Reference source not found. 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 thông dịch
6
(scripting language) như Javascript, PHP, Python, Do vậy, hướng tiếp cận của chúng
tôi là sẽ chuyển các trang web về cấu trúc DOM của chúng dưới dạng cây (Tree), sau
đó so sánh xem hai trang web có giống nhau hay không bằng cách so sánh các DOM-
Tree. Nếu hai trang web có cấu trúc giống nhau thì có thể nghi ngờ, tiếp theo chúng tôi
sử dụng các thuật toán so khớp để so sánh các thành phần chi tiết của chúng để phát
hiện trang web giả mạo. Và đây là mục tiêu thứ hai của luận án.
1.4 Mục tiêu và cấu trúc của luận án
i) 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.
ii) Nghiên cứu về giả mạo web. Phát triển các thuật toán so khớp có cấu trúc
(đồ thị) vào việc 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ề xâm nhập mạng và giả mạo trên mạng.
Chương 2: Trình về các thuật toán so khớp đơn mẫu và đa mẫu áp dụng trong

trái phép dựa trên mã nguồn mở Snort – cái sẽ là nền tảng để triển khai thử nghiệm các
7
thuật toán đề xuất trong các chương tiếp theo. Các cách tiếp cận của cộng đồng khoa
học trong nước và trên thế giới cho việc nghiên cứu và phát triển hệ thống phòng
chống xâm nhập được phân tích và trình bày tóm tắt. Dựa vào sự phân tích này, luận
án cũng xác định được mục tiêu thứ nhất của luận án. Tiếp theo, luận án đã trình bày
về vấn nạn giả mạo đặc biệt là giả mạo web. Các cách tiếp cận của cộng đồng khoa
học trong nước và trên thế giới cho việc nghiên cứu và phát triển hệ thống phát hiện
web giả mạo được phân tích và trình bày tóm tắt. Từ đó, luận án cũng đã xác định
được mục tiêu thứ hai.

Chương 2. SO KHỚP TRONG PHÁT HIỆN XÂM
NHẬP MẠNG
2.1 Bài toán so khớp chuỗi
Các thuật toán so khớp chuỗi có thể phân loại theo hai tiêu chí:
- Dựa trên số lượng mẫu, có hai loại: so khớp đơn mẫu (Single Pattern) và so
khớp đa mẫu (Multiple Patterns).
- Dựa trên cơ sở thiết kế thuật toán, có ba loại: so khớp dựa trên tiền tố
(prefix), so khớp hậu tố (suffix) và so khớp thừa số (factor).
Tất cả các thuật toán so khớp chuỗi đều có 2 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 cho trong hình 2.4.
Thuật toán so khớp đầu tiên được biết đến là Brute ForceError! Reference
source not found
Void Brute_Force ( char *x, int m, char y, int n)
{
/* Searching */
For ( int j = 0 ; j <= n – m ; j++ )
{

for (i = 0, j = 0; j < M && i < N; i++, j++)
while ((j >= 0) && (t[i] != p[j]))
j = next[j];
if (j == M) return i - M;
else return i;
}
2.2.2 Thuật toán Boyer-Moore (BM)
Phát biểu thuật toán: Thuật toán sẽ lưu cách dịch thứ nhất trong mảng gs kích
thước m + 1 và cách dịch thứ hai được lưu trong mảng bc với kích thước 256 (tương
ứng với 256 ký tự của bảng mã ASCII).
Mảng bc được tính như sau:
int* PreBC (char *x,int m)
{ int i,j,*bc;
for (j=0;j<256;j++)
*(bc[j]) = m;
for (i=0;i<=m-2;i++)
*(bc[x[i]]) = m – i - 1;
return bc;
}
Việc tính mảng gs khá phức tạp, ta tính gián tiếp qua một mảng suff
int* Suffixes (char *x,int m)
{ int f,g,i,*suff;
*(suff + m - 1) = m ;
g = m - 1;
for (i=m-2;i>=0;i )
{if(( i > g)&& (*(suff+i+m–1–f)!= i–g))
*(suff+i)=min{*(suff+i+m–1–f),i–g};
else
{if (i < g) g = i;
f= i;

while ((i >=0)&&(x[i]==y[i + j])) i ;
if (i<0)
{ kq=j; j=j+gs[0];}
else j=j+max{gs[i],bc[y[i+j]] – m +i +1};
}
return kq;
}
2.2.3 Thuật toán Karp-Rabin
Phát biểu thuật toán
int ReHash(int a,int b,int h,int d)
{
return((h–a*d) << 1 ) + b;
}

intKarp_Rabin(char *x,int m,char *y,int n)
{ int d,hx,hy,i,j,kq;
d= 1;
for (i=1;i<=m-1;i++)
d=d<<1;
hx=hy=0;
for (i=0;i<=m-1;i++)
{
hx= ((hx<<1) + x[i]);
hy= ((hy<<1) + y[i]);
}
if ((hx == hy)&&(x== y[0 . . m – 1])) kq=0;
j= m;
while (j < n)
{
10

9: output I → This an accepting state, i.e. state
A
10: end if
11:end for
12:end procedure
2.3.2 Thuật toán Commentz-Walter (CW)
1. Procedure CW(y,n,m,p,root)
 Input:
 y ← array of n bytes representing the text input
 n ← integer representing the text length
 m ← array of keyword lengths
 p ← number of keywords
 root ← root node of the trie
2. v ← root The current node
3. i ← min {m[0], m[1], . . . , m[p-1]} i point to the current position in
y
4. j ← 0 j indicates depth of the current
node v
5. while i ≤ n do
6. while v has child v’ labeled y[i – j] do
7. v ← v’
8. j ← j + 1
11
9. if out(v) ≠ Ø then
10. Output i – j Path from v to root matches y[i-j] to
y[i]
11. end if
12. end while Shifting
13. i ← i + min {shift2(v), max { shift1(v), char(y[ i - j] – j – 1}}
14. j ← 0

j ← j + 1
end while
if j ≥ len then
output i – len + 1
end if
end if
p ← p + 1
end while
i ← i + 1 → Shift only by one place
else
i ← i + shift → Skip part of the text
end if
12
end while
end procedure
2.3.4 Thuật toán RSI (Recursive Shift Indexing)và MDH (Multi-Phase Dynamic
Hash)
2.3.5 Một số thuật toán khác
2.3.6 Các kết quả thực nghiệm
Để đánh giá thời gian thực thi và yêu cầu bộ nhớ của các thuật toán với các
hướng tiếp cận khác nhau, chúng tôi đã triển khai cài đặt các thuật toán AC, AC-BM,
SBMH, SBOM, WM, RSI, MDH trên ngôn ngữ lập trình C. Điều kiện thực nghiệm
kiểm chứng trên các máy tính có bộ xử lý Intel Pentium 4 tốc độ 3.0 GHz Dual Core,
bộ nhớ cache 512 KB, Ram dung lượng 2 GB. Số lượng mẫu thực nghiệm là 1000
mẫu, chiều dài các mẫu từ 8 đến 30 ký tự, độ dài chuỗi kiểm tra là 1000 ký tự (trong
đó có 500 ký tự được gieo ngẫu nhiên, sau khi gieo nhẫu nhiên chúng tôi chèn thêm
các ký tự vào cho đủ độ dài 1000). Bảng chữ cái thực hiện là |S|=256.
Kết quả thu được đánh giá theo tiêu chí về thời gian thực thi như hình 2.8
1
2
13
(b) Hàm Failure
i
2
9
6
4
Output(i)
he
she, he
his
hers
c) Hàm Output
Trạng
thái
Đầu vào
e
h
i
r
s
0
0
1
0
0
7
1

9
0
0
0
0
(d) Ma trận chuyển cho hàm Goto
Hình 2.3 Không gian trạng thái của AC với tập mẫu P
Rõ ràng, khi tập mẫu lớn với nhiều mẫu thì số trạng thái sẽ tăng lên rất nhanh.
Thêm nữa, chúng ta thấy trong ma trận trạng thái của NFA có rất nhiều thành phần có
giá trị 0. Do vậy, ý tưởng chính ở đây là sử dụng các kỹ thuật nén dòng (CSR:
Compressed Row Storage) Error! Reference source not found. để giảm bớt không
gian lưu trữ. Với tập mẫu P ở trên, không gian trạng thái của AC sau khi sử dụng kỹ
thuật CSR được trình bày trong bảng 3.
Bảng 1 : Nén ma trận chuyển hàm Goto với CSR
Giá trị
1
7
2
5
3
4
6
8
9
Cột
2
5
1
3
4

7
8
1
9
2
(b) Nén hàm Failure dùng bảng chỉ số 1 chiều
Số lượng mục
8
Chỉ số bắt đầu
4
Giá trị
7
0
7
0
1
2
Dải lưu trữ
8
4
7
0
7
0
1
2
(c) Nén hàm Failure dùng bảng chỉ số lưu trữ
Chúng ta hoàn toàn có thể áp dụng cách lưu trữ này cho mỗi dòng trong ma trận
để tối ưu không gian trạng thái, chúng ta biểu diễn bảng dịch chuyển bằng danh sách
các con trỏ vectơ trạng thái.

//Cấp phát trạng thái mới
// Thêm liên kết chuyển trạng thái các nút với ký tự vào w(j)
dfa.addTransition(*state,w(j),*NextState);}
*state = *NextState; }
dfa.addMatchlist(*state);}
return dfa;}
Trong đó, các hàm addMatchlist, addTransition có nhiệm vụ thêm
các trạng thái mới vào danh sách NextStatevàMatchlist ứng với ký tự đang xét
w(j) của mẫu P[i].
Thuật toán 2. Xây dựng bảng chỉ số con trỏ failure ứng với DFA
INPUT: DFA ứng với tập mẫu P được xây dựng trong thuật toán 1.
OUTPUT: Danh sách các trạng thái lỗi lưu trữ trong *failure.
Void FailureBuild(DFA dfa){
*dfa.Failurelist = new Failure();
Queue q = new Queue();
State state, nextState, s; char ch;
q.add(dfa.getStartState());
*dfa.Failurelist.setFailure(dfa.getStartState(), null);
while (! q.isEmpty()) {
state = q.remove();
for (int i = 0; i < 256; i++) {
ch = *dfa.Nextstate(i);
nextState=dfa.getTransition(state, ch);
if (nextState.isValid()){
s = *dfa.Failurelist.getFailure(state);
while((s!=null)&&!dfa.getTransition(s,ch).isValid()){
s = *dfa.Failurelist.getFailure(s);}
15
if (s ! = null)
{*dfa.Failurelist.setFailure(nextState, dfa.getTransition(s,ch));}

nextState = dfa.getTransition(s,ch);}
else {
nextState = dfa.getStartState();}}
if (nextState.isMatchlist()) {
r.add(M.getPosition(),*dfa.Matchlist);}
state = *dfa.NextState[state.getChar];}
return r;}
2.4.3. Thực nghiệm và đánh giá

16
Bảng 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
Tập luật
Số
lượng
mẫu
Số
lượng
ký tự
Thuật toán AC gốc
Thuật toán AC cải tiến
Tỷ lệ % tổng
số trạng thái
rút gọn được
Số lần
chuyển
trạng thái
Tổng số
trạng
thái

Oracle
337
11.128
6.793
6.804
4.512
3.957
41.84 %

Hình 2.5 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.
Trong việc làm này, chúng tôi đã phân tích kỹ thuật nén dòng để tối ưu không
gian trạng thái các thuật toán so khớp chuỗi AC dùng bảng chỉ số thay cho bảng chỉ số
trạng thái và thử nghiệm trên hệ thống phát hiện xâm nhập mạng Snort 2.4.2. Các kết
quả thực nghiệm cho thấy thuật toán mà chúng tôi đề xuất cho kết quả bằng và tốt hơn
thuật toán AC gốc và một số thuật toán AC đã được cải tiến AC-OPT Error!
Reference source not found. và AC-RDFError! Reference source not found Việc
hiểu rõ cấu trúc biểu diễn không gian trạng thái của thuật toán sẽ giúp chúng ta xây
dựng các hệ thống an ninh mạng đạt hiệu quả cao trong thực tế đáp ứng được sự phát
triển nhanh và đa dạng của các mẫu virus.
2.5 Thuật toán đề xuất
Để mô phỏng các quá trình của thuật toán, chúng ta quan tâm đến ví dụ sau:
Giả sử, chúng ta có tập mẫu P = {"search", "ear", "arch", "chart"}
Và dữ liệu đầu vào là xâu T= “strcmatecadnsearchof”.
2.5.1 Giai đoạn tiền xử lý
Chúng tôi xây dựng một biểu đồ cấu trúc để biểu diễn tập mẫu P. Biểu đồ cấu trúc
G có n mức (n là độ dài của mẫu dài nhất trong tập mẫu P), tại mỗi mức i (chẳng hạn)
chúng tôi chỉ phải giữ lại các ký tự khác nhau thứ i trong mỗi mẫu của tập P. Biểu đồ
cấu trúc của tập mẫu P = {"search", "ear", "arch", "chart"} được chỉ ra trong hình
2.19:

con trỏ P
i
(i tương ứng với vị trí của ký tự hiện hành đang được xét trong T). Nếu ký tự
hiện hành trùng khớp với ký thứ j trong mẫu thứ k thì thành phần thứ k trong con trỏ P
j

(lưu ý là j luôn luôn nhỏ hơn hoặc bằng i) tương ứng sẽ được giảm đi 1. Các con trỏ sẽ
bị xóa nếu tại bước thứ i mà không có bất cứ thành phần nào của nó bị giảm đi. Ngược
lại, chúng sẽ được duy trì trong các bước duyệt tiếp theo. Khi có một thành phần của
một con trỏ nào đó mà giá trị của nó giảm đến 0 thì mẫu tương ứng được tìm thấy. Các
thao tác tìm kiếm và so khớp của thuật toán được mô tả như sau (hình 2.21)
18 Hình 2.7 Giai đoạn tìm kiếm và so khớp trong thuật toán chúng tôi đề xuất
Số các bước cần thực hiện trong thuật toán của chúng tôi bằng với chiều dài của
xâu vào T. Với một xâu T độ dài n, độ dài của mẫu dài nhất L, và m là số lượng mẫu.
Trong trường hợp xấu nhất, thời gian thực hiện của thuật toán là O(n*m*L). Mặc dù
vậy, các trường hợp trung bình là thường bé hơn nhiều vì rất ít khi có m con trỏ P
i
tồn
tại đồng thời.
2.5.3 Thuật toán đề xuất
Algorithm 4. Our Algorithm
1:
Procedure DNL (T, n, m, p, G)
Input:
 T ← array of n byte representing the text input
 n ← integer represent the text length
 P[j] ← array of patterns

j
[position of T[i] in P[j]] = P
j
[position of T[i] in P[j]] -1;
8:
If (P
j
[k] = 0) then
9:
Output P[k] detected;
10:
Remove P
j
;
11:
endif
12:
If (P
j
inS) and (P
j
not change) then Remove P
j

13:
endif
19
14:
endif
15:

Xây dựng cây DOM từ những trang Web đầu vào là một bước cần thiết trang
nhiều giải thuật trích xuất dữ liệu Error! Reference source not found Có hai
phương pháp cơ bản để xây dựng các cây DOM là Sử dụng các thẻ riêng biệt Sử dụng
các thẻ và các hộp ảo (visual cue)
3.2. So khớp đồ thị
Một trang Web (hay trang HTML) có thể được biểu diễn dưới dạng một DOM
– Tree và ngược lại người ta có thể cập nhật các trang Web dễ dàng bằng việc sửa đổi
DOM-Tree của nó. Do vậy, việc xem xét hai trang web có giống nhau hay không,
chúng ta hoàn toàn có thể so sánh xem hai DOM-Tree tương ứng của chúng. Mặt khác,
20
cây chỉ là một dạng đặc biệt của đồ thị. Vì vậy, tổng quát hơn trong phần này chúng tôi
sẽ nghiên cứu bài toán so khớp đồ thị.
3.2.1. Một số khái niệm về đồ thị
3.2.2. Bài toán so khớp đồ thị
3.2.3. Một số cách tiếp cận
3.2.3.1. Một số định nghĩa và ký hiệu :
Cho đồ thị gán nhãn G ={V, E, L
V
, L
E
, } với |V| =n. Đồ thị G được biểu diễn
bởi ma trận kề M = (m
i,j
)
n*n
, i, j = , trong đó m
ii
= và m
i,j
=

D
) với |V
M
| =
m, |V
D
| = n (m < n) ta phải đi tìm một ánh xạ f: V
M
 V
D
phù hợp nhất biến mỗi cặp
đỉnh của đồ thị G
M
thành một cặp đỉnh của đồ thị G
D
. Nếu tổng số cặp đỉnh thỏa mãn
ánh xạ f càng lớn thì ánh xạ f càng phù hợp.
Ta nói f là song ánh nếu và chỉ nếu với mỗi cặp đỉnh (u E
M
, cho ta cặp
(f(u),f(v)) E
D
. Như vậy cung (f(u),f(v)) là ảnh của cung (u,v) trong đồ thị G
D
.
Mã giã của một thuật toán di truyền áp dụng cho bài toán so khớp đồ thị như
sau:
Bắt đầu
t=0;
P(0)=initial_Population();// khởi tạo quần thể ban đầu.

Độ thích nghi
G = 1
64
4 5 6 3
0.75
G = 3
32
6 7 2 3
0.75
G = 4
24
4 5 6 3
0.75
G = 7
16
6 7 2 3
0.75
Bảng 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
Số thế hệ đạt cá thể tốt nhất
Số lượng cá thể
Cá thể tốt nhất
Độ thích nghi
G = 1
128
1 2 3 4
0.75
G = 5
64
10 11 2 9
0.75

128
0.833
1 2 3 8 9

3.2.5.1. Đồ thị vô hướng có trọng số
Bảng 7 : Kết quả độ thích nghi ở một số thế hệ với số đỉnh nhỏ hơn 10
Thế hệ thứ
Độ thích nghi
Số cá thể có độ thích nghi cao nhất
2
0.667
Từ 0- 3 cá thể
3
0.75
Từ 0- 5 cá thể
4
0.75
Từ 0-8 cá thể 22
Bảng 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
Số lương quần thể
Thế hệ thứ
Cá thể tốt nhất
Độ thích nghi
P_Size = 64
G = 8
1 11 3 4
0.5

128
64
0.75
1 2 3 8 10
265
128
0.833
1 2 3 8 9
3.2.5.2. Đồ thị vô hướng có nhãn.
 Trường hợp 1: Đồ thị vô hướng có nhãn với số đỉnh <10, chúng tôi sử dụng hai
đồ thị trong hình vẽ sau

Đồ thị G
M
Đồ thị G
D
 Các kết quả thực nghiệm:
Bảng 10 : Kết quả độ thích nghi ở một số thế hệ với số đỉnh nhỏ hơn 10
Số lương quần thể
Thế hệ thứ
Cá thể tốt nhất
Độ thích nghi
P_Size = 64
G = 4
1 2 5 3
0.667
P_Size = 64
G = 8
1 2 5 4
0.75

64
0.75
1 2 3 4
265
64
0.833
1 2 3 4

Bảng 12 : Kết quả độ thích nghi ở một số thế hệ với số đỉnh lớn hơn 20
Số lương quần thể
Thế hệ thứ
Độ thích nghi
Cá thể tốt nhất
24
16
0.50
1 2 3 5 4
32
24
0.50
1 2 3 21 10
64
32
0.75
1 2 3 21 9
128
64
0.75
1 2 3 8 10
265

- Threshold δ
Output: -
 
|
i
iG
R G S



Begin
 
R 
;
for (i=1; i<=N; i++)
if (Computing similarity(G
i
)>δ)

 
i
R R G
;
ReturnR;
End.
Thuật toán của chúng tôi được viết bằng ngôn ngữ C. Chúng tôi kiểm tra cách
tiếp cận của chúng tôi trên một tập 5 trang web ví dụ (ký hiệu là p1,p2, p3, p4 và p5)
với ba kích thước khác nhau (DOM-Tree ít hơn 10 nút, DOM-Tree từ 10 đến 20 nút,
và DOM-Tree lớn hơn 20) và 10 trang web mẫu (ký hiệu là T1,T2, ,T10) với ba
24

100
100
T2
32
12
23
20
41
34
68
68
54
61
T3
52
43
28
13
76
62
27
18
39
34
T4
65
58
55
40
90

87
80
100
85
76
62
51
43
T8
49
41
91
86
61
51
41
31
92
81
T9
80
71
61
51
78
69
74
62
97
86

Nhận dạng đúng (%)
75
63
57
35
22
17
0
0
1
Nhận dạng sai (%)
0
0
0
0
0
0
21
48
92
Chúng ta có thể nhìn từ bảng 16 các kết quả là liên quan chặt chẽ đến việc phát
hiện trang web giả mạo với ngưỡng δ=0.6. Trong thực tế, nếu các trang web hợp pháp
chữa nhiều thành phần đặc biệt trong DOM-Tree, nó dễ dàng được phân biệt từ các
trang web khác.
3.4. Kết chương
Trong chương này, luận án đã trình bày về cấu trúc DOM của trang HTML và
XML và cách xây dựng DOM-Tree. Sau đó, luận án đã trình bày chi tiết bài toán so
khớp đồ thị không chính xác. Một số cách tiếp cận liên quan và những tồn tại của
chúng. Tiếp theo, luận án trình bày một cách tiếp cận mới cho việc so khớp đồ thị dựa
trên thuật toán di truyền trong chi tiết. Thuật toán đề xuất có thể áp dụng trên một số

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.
(v) Á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 kết quả này, luận án mới chỉ dừng lại ở việc so khớp cấu trúc của trang web
và phần nội dung là văn bản trong trang web. Các yếu tố về hình ảnh, âm thanh,…
thường được sử dụng trong các trang web như là những phần không thể thiếu. Việc so
khớp các thành phần này cần phải được thực hiện để so khớp hai trang web được chính
xác hơn. Đây là phần thiếu sót của luận án và cũng là một trong những định hướng
nghiên cứu tiếp của luận án.