Tóm tắt Luận án Nghiên cứu một số kỹ thuật phát hiện giả mạo trên web

à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 việc phát hiện xâm nhập mạng. Chương 3: Trình bày về so khớp đồ thị và phát hiện các trang web giả mạo. Cuối cùng là phần kết luận và hướng phát triển của luận án. 1.5 Các kết quả của luận án Với mục tiêu áp dụng các thuật toán so khớp trong việc phát triển các hệ thống phát hiện xâm nhập trái phép, luận án đã đạt được các kết quả như sau: (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. Với mục tiêu phát hiện các trang web giả mạo, luận án đã đạt được các kết quả như sau: (iv) Đư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. (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. 1.6 Kết chương Trong chương này, luận án đã trình bày chi tiết việc phát hiện xâm nhập trái phép và giả mạo trên mạng. Về phát hiện xâm nhập trái phép, luận án đã trình bày lại các kỹ thuật xâm nhập trái phép hiện đã được sử dụng bởi kẻ tấn công; các giải pháp kỹ thuật nhằm ngăn chặn các kỹ thuật xâm nhập trái phép được biết; kiến trúc tổng quát của một hệ thống phát hiện xâm nhập và chi tiết một hệ thống phát hiện xâm nhập 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 (int i = 0; i < m && x[i] == y [ y + j ]; i++ ) { If ( i >= m ) OUTPUT (j); } } } 2.2 Các thuật toán so khớp đơn mẫu 2.2.1 Thuật toán Knuth-Morris-Pratt (KMP) Thuật toán tính mảng Next như sau: int* InitNext(char *p,int m) { int i,j,*kmpNext; i = -1; j = 0; *kmpNext = -1; while (j < m ) { while (i > -1)&&( p[i] != p[j]) i = *(kmpNext + i); i++; j++; 8 if (p[i]== p[j]) *( kmpNext + j) = *( kmpNext + i); else *( kmpNext + j) = i; } return kmpNext; } Thuật toán Knuth - Morris – Pratt int KMP(char *p, char *t) { int i, j, M = strlen(p), N = strlen(t); InitNext(p); 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 ((g>=0) && (x[g]==x[g+m–1–f])) g--; *(suff+i) = f – g; } } return suff; } int* PreGS (char *x,int m) { int *suff,*gs,i,j; 9 suff= Suffixes(x,m); for (i=0;i<m;i++) *(gs+i)=m; j=0; for (i=m-1;i>=-1;i--) if ((i==-1)||(*(suff+i)==i+1)) while (j<m-1-i) {if (*(gs+j)==m) *(gs+j)= m-1–i; j++; } for (i=0;i<=m-2;i++) *(gs+m-1– *(suff+i)) = m–1-i; return gs; } Thuật toán Boyer – Moore int Boyer_Moore(char *x,int m,char *y,int n) { int *gs, *bc, i, j, kq; gs= PreGS(x,m); bc=PreBC(x,m); j= 0; while (j<=n-m) { i= m -1; 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 hy = ReHash(y[j–m],y[j],hy,d); if ((hx==hy)&&(x==y[j–m+1..j])) kq=(j – m + 1); j++; } return kq; } 2.2.4 Thuật toán Boyer-Moore Horspool (BMH) 2.2.5 Thuật toán BDM và BOM 2.3 Các thuật toán so khớp đa mẫu 2.3.1 Thuật toán Aho-Corasick (AC) Algorithm 1 Aho-Corasick Algorithm 1: procedure AC (y,n,q0)  Input  y ← array of n bytes representing the text input  n ← integerrepresenting the text leght  q0← initial state 2: state ← q0 3: For i = 1 → n do → Matching 4: While g(state, y[i]) = fail do → whileg(state, y[i]) is undefined 5: state ← f(state) → use the failure function 6: end while 7: state←g(state, y[i]) 8: Ifo(state) ≠ then 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 15. end while 16. end procedure 2.3.3 Thuật toán Wu & Manner (WM) Algorithm 3 Wu and Manner Algorithm procedure WM (y,n,B, B’, SHIFT, HASH, PREFIX, PAT_POINT)  Input  y ← array of n bytes representing the text input  B ← integer representing the suffix block length  B’ ← integer representing the prefix block lenght  SHIFT ← SHIFT table (see description above)  HASH ← HASH table (see description above)  PREFIX ← PREFIX table (see description above)  PAT_POINT ← table of pointers to keywords (like our x it has m keywords) m ← min {length of all keywords} minlen i ← m-1 While i ≤ n do → Matching h ← hash (y[i – B + 1], , y[i]) → hash over B bytes back from index i in y shift ← SHIFT[h] If shift = 0 then → Suffix block matches text_prefix ← hash(y[i – m + 1], . . . , y [i – m + 1+ B’]) p ← HASH[h] → a C style pointer p_end ← HASH[h + 1] → a C style pointer while p < p_end do→ Matching if text_prefix = PREFIX[p] then → Prefix matches px ← PAT_POINT[p] → Pointer to the current keyword len ← length of px → Length of current keyword j ← 0 while j < len and y[i –len + 1 + j] = px[j] do 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 Hình 2.1 Đánh giá thời gian thực thi của các thuật toán Hình 2.2 Đánh giá yêu cầu bộ nhớ của các thuật toán 2.3.7 Phân tích và đánh giá các thuật toán so khớp chuỗi 2.4 Ứng dụng so khớp đa mẫu trong phát hiện thâm nhập mạng 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òng Mô hình NFA của AC biểu diễn tập mẫu P={hers, she, his, he} được cho trong hình 2.13. (a) Hàm Goto i 1 2 3 4 5 6 7 8 9 f(i) 0 0 0 7 0 7 0 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 2 0 5 0 0 2 0 0 0 3 0 3 0 0 0 0 4 5 0 0 0 0 6 7 0 8 0 0 0 8 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 5 5 2 1 Dòng 1 1 2 2 3 4 5 6 7 Bảng 2 : Nén hàm failure của AC dùng bảng chỉ số Giá trị 7 7 1 2 Chỉ số 4 6 8 9 (a) Nén hàm Failure dùng bảng chỉ số 2 chiều 8 4 7 6 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. 2.4.2. Cải tiến giai đoạn tiền xử lý của AC Do otomat đơn định DFA (Deterministic Finite Automata) yêu cầu xác định duy nhất trạng thái tiếp theo nào ứng với mỗi ký tự vào nên cho hiệu quả thực thi tốt 14 hơn nên trong Snort chúng tôi khai báo thuật toán AC sử dụng DFA. Mô tả cấu trúc dữ liệu danh sách liên kết của DFA như sau: struct DFA { struct State *NextState[256]; struct State *Failurelist; struct Matched *Matchlist; } Thuật toán 1. Xây dựng ma trận chuyển trạng thái dựa trên DFA ứng với tập mẫu P sử dụng cấu trúc bảng chỉ số ký tự. INPUT: Tập mẫu P có n mẫu. OUTPUT: Bảng chuyển trạng thái của DFA chấp nhận tất cả các mẫu trong P. DFA dfaBuild(Patterns P[], int n){ DFA dfa = new DFA(); String w; State *state, *NextState; //Cấp phát trạng thái mới state = dfa.newState(); //Thiết lập trạng thái ban đầu dfa.setStartState(state); for (int i = 0; i < n; i++){ w = P[i]; //Xử lý từng mẫu P[i] state = dfa.getStartState(); for (int j = 0; j < w.length(); i++){ *NextState = dfa.getTransition(*state, w(j)) if (!NextState.isValid()){ // Loại bỏ các trạng thái 0 *NextState = dfa.newState(); //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));} else {*dfa.Failurelist.setFailure(nextState, dfa.getStartState());} if (f.getFailure(nextState).isMatchlist()){ dfa.addMatchlist(nextState);} q.add(nextState);}}}} a) Không gian lữu trữ của thuật toán AC gốc b) Không gian lữu trữ của thuật toán AC khi tối ưu Hình 2.4 Không gian trạng thái của AC trước và sau tối ưu Cải tiến giai đoạn tìm kiếm của thuật toán AC Thuật toán 3. Tìm kiếm mẫu trên bảng chỉ số ký tự INPUT: Tập mẫu P có n mẫu. Gói tin cần kiểm soát M. OUTPUT: Danh sách các mẫu trong P xuất hiện trong nội dung gói tin M Results Search(Patterns P, Message M){ DFA dfa = dfaBuild(P, n); FailureBuild(DFA dfa) State state, nextState; char ch; Results r = new Results(); state = dfa.getStartState(); while (! M.eof()){ ch = M.getChar(); nextState = dfa.getTransition(state,ch); if (!NextState.isValid()){ nextState = *dfa.Failurelist.getFailure(state); while ((nextState!=null) && ! dfa.getTransition(nextState,ch).isValid()) {nextState=*dfa.Failurelist.getFailure(nextState);} if (nextState ! = null) { 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 Số lần chuyển trạng thái Tổng số trạng thái Ftp 96 466 402 406 391 375 7.63 % Smtp 104 989 715 719 613 602 16.27 % Web-misc 160 2.052 1.420 1.425 1.318 1.259 11.65 % 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: 17 Hình 2.6 Kết quả giai đoạn tiền xử lý trong thuật toán của chúng tôi Rõ ràng, với cách tiếp cận của chúng tôi, không gian lưu trữ sẽ được giảm do chỉ lưu trữ các ký tự khác nhau tại mỗi mức.Yêu cầu về bộ nhớ trong thuật toán của chúng tôi ở giai đoạn này là bằng hoặc nhỏ hơn không gian nhớ của DFA và hàm trạng thái và hàm goto trong các thuật toán AC, WM, CW. Thêm nữa, thuật toán của chúng tôi không sử dụng các bảng SHIFT và HASH và do đó giảm thời gian xây dựng các bảng và không gian lưu trữ của các bảng này. 2.5.2 Giai đoạn tìm kiếm Để phân tích quá trình tìm kiếm so khớp, chúng tôi giả sử đầu vào là xâu T= “strcmatecadnsearchof”. Quá trình tìm kiếm của thuật toán AC được thực hiện thông qua phép chuyển trạng thái của otomat nếu ký tự đang xét là khớp và sẽ làm thay đổi trạng thái dịch chuyển, ngược lại sẽ kiểm tra hàm failure để tính bước dịch chuyển tiếp theo. Trong pha tìm kiếm so khớp trong thuật toán của chúng tôi. Chúng tôi sử dụng một danh sách các con trỏ để tối ưu hóa không gian. Số lượng tối đa các thành phần trong con trỏ là bằng số lượng các mẫu (bằng lực lượng của tập P). Chúng tôi khởi tạo giá trị các thành phần này của con trò bằng độ dài tương ứng của các mẫu trong tập mẫu. Cấu trúc của một con trỏ được chỉ ra như sau: Pi 6 3 4 5 Trong quá trình duyệt trên dữ liệu vào T, tại mỗi bước chúng tôi khởi tạo một con trỏ Pi (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ỏ Pj (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ỏ Pi 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  P0← array of keyword lengths P0[j] (j=1m)  m ← number of patterns  G ← graph of pattern P  S ←Set of Pi 2: S = ∅; 3: for i=1 → n do 4: Init pointer Pi = P0; 5: S = S U {Pi} 6: If (T[i] in G) and (PjinS) then 7: Pj[position of T[i] in P[j]] = Pj[position of T[i] in P[j]] -1; 8: If (Pj[k] = 0) then 9: Output P[k] detected; 10: Remove Pj; 11: endif 12: If (PjinS) and (Pjnot change) then Remove Pj 13: endif 19 14: endif 15: end for 16: End procedure 2.5.4 Các kết quả thực nghiệm Hình 2.8 So sánh về thời gian thực hiện khi cố định số lượng mẫu Hình 2.9 So sánh về bộ nhớ sử dụng khi cố định số lượng mẫu 2.6 Kết chương Trong chương này, luận án đã trình bày chi tiết các thuật toán so khớp đơn mẫu như Knuth-Morris-Pratt, Boyer-Moore-Horspool, Karp-Rabin, Backward Dawg Matching và Backward Oracle Matching sử dụng trong hệ thống phát hiện xâm nhập Snort verion 2.0. Sau đó, luận án cũng trình bày trong chi tiết các thuật toán so khớp đa mẫu được sử dụng trong hệ thống Snort version 2.6. Sự đánh giá so sánh bằng lý thuyết và thực nghiệm của các thuật toán này cũng được triển khai. Tiếp theo luận án đề xuất một cải tiến cho thuật toán Aho-Corasick bằng kỹ thuật nén dòng và bảng chỉ số. Các thực nghiệm chỉ ra thuật toán cải tiến đã đạt được hiệu năng tốt hơn thuật toán ban đầu khi thực nghiệm trên hệ thống Snort. Cuối cùng, luận án trình bày đề xuất thuật toán mới cho so khớp đa mẫu dựa trên kỹ thuật xây dựng biểu đồ cấu trúc các mẫu kết hợp với danh sách liên kết. Các kết quả thực nghiệm chỉ ra thuật toán được đề xuất có hiệu quả tốt hơn một số thuật toán hiện hành cả về không gian và thời gian. Chương 3. SO KHỚP ĐỒ THỊ VÀ PHÁT HIỆN CÁC WEBSITE GIẢ MẠO 3.1. Cấu trúc DOM-Tree 3.1.1. Khái niệm 3.1.2. Xây dựng cây DOM 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, LV, LE, } với |V| =n. Đồ thị G được biểu diễn bởi ma trận kề M = (mi,j)n*n, i, j = , trong đó mii = và mi,j= với i j ( V). Ma trận M không phải là ma trận duy nhất biểu diễn đồ thị G. Nếu ma trận M biểu diễn đồ thị G thì các ma trận hoán vị của M cũng biểu diễn cho đồ thị G Error! Reference source not found.. 3.2.3.2. Tìm đẳng cấu đồ thị và đẳng cấu đồ thị con. 3.2.3.3. Thuật toán SI – COBRA cho bài toán so khớp đồ thị gán nhãn. Ý tưởng : Cho hai đồ thị gán nhãn G và G’ (tương ứng với hai đồ thị mô hình GM và đồ thị dữ liệu GD trong mục phát biểu bài toán) ta phải đi tìm một đồ thị con S của G sao cho S G. Bài toán này được gọi là bài toán tìm đẳng cấu đồ thị con. 3.2.4. Thuật toán di truyền cho bài toán so khớp đồ thị Thuật toán di truyền là một trong những thuật toán tiến hóa, hình thành dựa trên quan niệm cho rằng, quá trình tiến hóa tự nhiên là quá trình hoàn hảo và hợp lý nhất, tự nó đã mang tính tối ưu.. Như đã nói ở mục trên, với hai đồ thị GM = (VM , EM) và GD= (VD,ED) với |VM| = m, |VD| = n (m < n) ta phải đi tìm một ánh xạ f: VM  VD phù hợp nhất biến mỗi cặp đỉnh của đồ thị GM thành một cặp đỉnh của đồ thị GD. 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 EM , cho ta cặp (f(u),f(v)) ED. Như vậy cung (f(u),f(v)) là ảnh của cung (u,v) trong đồ thị GD. 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