Ứng dụng kỹ thuật khai phá dữ liệu trong hệ thống IDS

ta có thể gửi nó tới thành phần phân tích như là một tấn công mà không có bất kỳ phân vân nào. Bây giờ nếu không có đấu hiệu tấn công của kiểu này thì chúng ta gửi bản ghi kết nối đó tới mudule phát hiện bất thường, cái sẽ thực hiện bước tiếp theo. Bước 3: phát hiện bất thường Trong bước này module phát hiện bất thường sẽ sử dụng thuật toán phát hiện outlier để chỉ định một tỷ lệ bất thường tới mỗi kết nối mạng. Nó chỉ định một mức độ về việc outlier cho mỗi điểm dữ liệu, được gọi là Local Outlier Factor (LOF). Đối với mỗi mẫu dữ liệu, mật độ của các láng giềng được tính trước tiên. LOF của một mẫu dữ liệu cụ thể p đại diện cho tỷ lệ trung bình mật độ mẫu p và mật độ các láng giềng của nó. LOF đòi hỏi các láng giềng của tất cả các điểm dữ liệu được xây dựng. Điều này bap hàm cả việc tính khoảng cách từng cặp điểm của tất cả các điểm dữ liệu, việc này có độ phức tạp O(n²). Khi có hàng triệu tập dữ liệu thì độ phức tạp sẽ rất lớn. Để giảm thiểu độ phức tạp mà một phương pháp chiến trong MINDS. Họ chuẩn bị một tập dữ liệu mẫu từ dữ liệu và tất cả các điểm dữ liệu được so sánh với tập dữ liệu nhỏ, điều này làm giảm độ phức tạp xuống O(n*m), với m là kích thước của tập dữ liệu nhỏ. Cụm C1 Cụm C2 Tập dữ liệu mẫu, p1 trong C1 Tập dữ liệu mẫu, p2 trong C2 Tập dữ liệu mẫu, p4 trong C2 Tập dữ liệu mẫu, p3 trong C1 Tập dữ liệu mẫu, p5 trong C2 Ví dụ ,For example, ở bảng trên chúng ta có thể thấy rằng cụm C2 dày hơn cụm C1. Do mật độ thấp ở cụm C1, hầu hết các mẫu q trong C1, khoảng cách giữa bất kỳ tập dữ liệu với các láng giềng của nó lớn hơn khoảng cách của C1. Ví dụ, khoảng cách giữa p1 và p3 cao hơn khoảng cách giữa p2 và p4. Do đó, cho nên p2 sẽ không được xem như là outlier. Bước thứ 4: phân tích mẫu kết hợp Sau khi chỉ định cho mỗi kết nối một tỷ lệ thì 10% các tỷ lệ đầu được đặt như là lớp bất thường và 30% các tỷ lệ cuối được xem như lớp các hành vi bình thường. 60% các tỷ lệ ở giữa được bỏ qua trong hệ thống của họ. Sau đó những kết nối được gán tỷ lệ này cho đi qua thành phần sinh các mẫu kết hợp. Figure 21: MINDS Association Analysis Module ([ELK+04] page: 14) Module này khái quát các kết nối mạng được xếp vào những hành vi bất thường cao bằng module phát hiện bất thường. Mục đích của việc khai phá các mẫu kết hợp là để khám phá các mẫu thường xảy ra trong lớp bất thường hay trong lớp bình thường. Trong bước này họ áp dụng luật kểt hợp để xây dựng các tập luật cho lớp bất thường và lớp bình thường. Ví dụ, xem xét các hành động cho một dịch vụ cụ thể có thể được tóm lược bằng một tập thường xuyên sau: sourceIP=X, destinationPort=Y Nếu có nhiều kết nói trong tập thường xuyên được xếp vào mức cao từ bước trước, thì những tập thường xuyên này có thể là một dấu hiệu thích hợp cho việc them vào một hệ thống dựa vào dấu hiệu. Hay nếu tập thường xuyên sau có tỷ lệ thấp hơn và xuất hiện nhiều lần thì chúng ta có thể nói nó bình thường cái mà là một hành vi duyệt Web. Protocol=TCP, destinationPort=80, NumPackets=3…6 Hệ thống của họ cũng tìm các mẫu trái ngược. Để tìm các mẫu trái ngược họ sử dụng một số phương thức như tỷ lệ, độ chính xác, phương tiện gợi nhớ và đìêu hoà của độ chính xác và gợi nhớ. Do các phương thức này module này sắp xếp các mẫu và nhóm các mẫu tương tự lại với nhau và biểu diễn chúng trước thành phần phân tích. Các phương pháp về việc sắp xếp các mẫu theo thứ tự được mô tả tổng quan như sau: Figure 22: Measures for ordering patterns ([ELK+04] page: 13) Xem xét một tập các đặc điểm xảy ra c1 lần trong lớp bất thường và c2 lần trong lớp bình thường. Đồng thời xét n1 và n2 là số các kết nối bất thường và bình thường trong tập dữ liệu. Giả sử rằng chúng ta chỉ quan tâm đến việc tìm các hồ sơ của lớp bất thường, tỷ lệ c1/n1 trên c2/n2 sẽ cho thấy là thế nào để các mẫu tốt có thể phân biẹt những kết nối bất thường với những kết nối bình thường. Tỷ lệ hay độ chính xác đơn lẻ là không đủ bởi vì chúng thường đặc trưng cho một số rất nhỏ các kết nối bất thường. Trong trường hợp rộng hơn, một mẫu hiếm được thực hiện chỉ một lần trong lớp bất thường và không xuất hiện trong lớp bình thường sẽ có giá trị cực đại của tỷ lệ và độ chính xác, và vẫn có thể là không quan trọng. Để giải thích cho độ quan trọng của một mẫu, phương pháp gợi nhớ có thể được sử dụng như là một phương tiện thay thế. Không may, một mẫu có sự gợi nhớ cai có thể không cần thiết là được nhận thức đúng đắn. Biện pháp F1 là một phương tiện điều hoà về độ chính xác và gợi nhớ, cung cấp một sự kết hợp tốt giữa hai biện pháp này. Sau đó trong bước cuối cùng tổng của tất cả các luật được biểu diễn trước thành phần phân tích và thành phần này có thể nâng cấp hoặc xây dựng hồ sơ bình thường hay có thể gán nhãn những dấu hiệu của một tấn công mới. Đây là cách mà MINDS làm việc như một hệ thống phát hiện xâm nhập không giám sát. TỔNG QUÁT CÁC NGHIÊN CỨU NIDS: Hệ thống Misuse/ Anomaly Dựa trên cảnh báo Công nghệ khai phá được sử dụng Dữ liệu huấn luyện được dùng Điểm mạnh Điểm yếu ADAM Anomaly Không Luật kết hợp, luật phân lớp TCPDump Nghiên cứu đi đầu Sinh ra các luật dư thừa, đòi hỏi lựa chọn cẩn thận minsupport MADAMID Misuse và anomaly Không Luật kết hợp, luật phân nhóm, luật phân đoạn thường xuyên TCPDump, BSM generated data Xây dựng các đặc điểm một cách tự động, hiệu quả Hệ thống Off-line, chỉ tính các mẫu thường xuyên của các bản ghi MINDS Anomaly Không Outlier, luật kết hợp Netflow Version 5 Anomaly Scores made it easy to determine anomalies Không xem xét 60% dữ liệu ở giữa có thể chứa các luật qua trọng Custom ID Filters Anomaly Có luật kết hợp, các phân đoạn thường xuyên Dữ liệu được dinh ra từ bộ cảm biến Có thể được thêm vào bất kỳ hệ thống nào Đòi hỏi chuẩn bị các bộ lọc tuỳ chỉnh cho các môi trường khác nhau LERAD Anomaly Không Kết hợp, phân lớp TCPDump Không có dư thừa Chọn lựa minsupport cẩn thận Entropy based Anomaly Không Entropy/ Graph based Dữ liệu kiểm toán nhị phân Cách thay thế của ADAM Đòi hỏi Minsupport phải được lựa chọn cẩn thận Chương 4 XÂY DỰNG CHƯƠNG TRÌNH PHÁT HIỆN TẤN CÔNG DoS SỬ DỤNG KỸ THUẬT KHAI PHÁ DỮ LIỆU 4.1 Thuật toán phân cụm 4.1.1 Dẫn nhập Dù hiện nay tình trạng phát tán virus đã trở nên phổ biến, 90% doanh nghiệp khẳng định những cuộc tấn công từ chối dịch vụ đang là vấn đề phiền toái và thường gặp nhất trong công ty. Từ cuối những năm 90 của thế kỷ trước. Hoạt động này bắt nguồn từ khi một số chuyên gia bảo mật, trong quá trình phát hiện khiếm khuyết hệ thống trên hệ điều hành Windows 98, đã phát hiện ra rằng chỉ cần gửi một gói dữ liệu ping có dung lượng lớn cũng đủ để làm tê liệt một server mục tiêu. Phát hiện này sau đó ngay lập tức được giới hacker sử dụng để triệt tiêu những đối tượng mà họ có ý định tấn công. Từ đây, hình thức sơ khai của DoS (Denial of Service) đã ra đời. Trong khi đó, dạng DDoS (Distributed Denial of Service) thì dựa vào việc gửi một lệnh ping tới một danh sách gồm nhiều server (kiểu này gọi là amplifier, tức là khuếch đại độ rộng mục tiêu), giả dạng là một gói ping để địa chỉ IP gốc được trá hình với IP của mục tiêu nạn nhân. Các server khi trả lời yêu cầu ping này khi đó sẽ làm “lụt” nạn nhân với những phản hồi (answer) gọi là pong. Do đó phần đồ án này chọn việc nghiên cứu và demo khai phá dữ liệu trong phát hiện tấn công từ chối dịch vụ và kỹ thuật được sử dụng ở đây là kỹ thuật phân cụm. Đây là kỹ thuật phát hiện bất thường không giám sát. Các thuật toán phát hiện bất thường không giám sát có thể được thực hiện trên dữ liệu không gán nhãn, cái mà dễ dàng để có được bởi vì nó chỉ đơn giản là thu thập các dữ liệu kểm toán thô từ một hệ thống. Trong thực tế, phát hiện bất thường không giám sát có nhiều lợi thế hơn hẳn phát hiện bất thường có giám sát. Các lợi thế chính là chúng không yêu cầu một tập dữ liệu hoàn toàn bình thường để huấn luyện. Hơn nữa, tập dữ liệu các hành vi bình thương của người dùng là vô cùng lớn và trong quá trình lấy tập dữ liệu sạch để huấn luyện trong kỹ thuật phát hiện có giám sát thì không thể đảm bảo rằng trong dữ liệu đó không có xâm nhập. Trong khi đó tập các hành vi được gọi là “xâm nhập” thì nhỏ hơn nhiều. Ngoài ra kỹ thuật này còn có rất nhiều ưu điểm như đã được trình bày ở các phần bên trên. 4.1.2 Các dạng dữ liệu trong phân tích cụm Giả sử một tập dữ liệu dùng để phân tích cụm chứa n đối tượng (các đối tượng có thể là con người, nhà, tài liệu...). Các thuật toán gom cụm thường xử lý trên một trong hai cấu trúc dữ liệu sau: (1) Ma trận dữ liệu: Biểu diễn n đối tượng, như con người, với p biến (còn được gọi là các phép đo hay các thuộc tính), như tuổi, chiều cao, cân nặng, giới tính. Ma trận này biểu diễn mối quan hệ đối tượng theo thuộc tính. (6.1) (2) Ma trận phân biệt: Để biểu diễn khoảng cách giữa hai điểm (đối tượng) trong không gian dữ liệu gồm n đối tượng theo p thuộc tính ta dùng ma trận phân biệt (6.2) Trong đó d(i,j) là khoảng cách giữa đối tượng i và đối tượng j. Trong trường hợp tổng quát, d(i,j) là một số không âm và dần về 0 khi 2 đối tượng i và j tương tự nhau. Bởi vì d(i,j) = d(j,i) và d(i,i) =0 nên ta có ma trận 6.2. 4.2.2.1 Biến trị khoảng Các biến trị khoảng là độ đo liên tục của các đại lượng tuyến tính đơn giản như trọng lượng, chiều cao, nhiệt độ, tuổi...Các đơn vị đo ảnh hưởng rất nhiều đến kết quả gom cụm. Ví dụ, thay đổi đơn vị đo: Mét thay cho inch cho chiều cao, kg thay cho pound cho cân nặng có thể dẫn đến các cấu trúc cụm khác nhau. Trong trường hợp tổng quát, biểu diễn một biến bởi đơn vị bé sẽ dẫn đến một khoảng lớn cho biến đó và nó ảnh hưởng lớn đến kết quả gom cụm. Để tránh sự phụ thuộc vào việc lựa chọn các đơn vị đo, dữ liệu cần phải được chuẩn hóa. Các phương pháp chuẩn hóa cố gắng đưa tất cả các biến một ảnh hưởng như nhau. Điều này rất hữu ích khi chúng ta chưa có một tri thức tiên nghiệm nào về dữ liệu. Tuy nhiên trong một số ứng dụng, người sử dụng có thể cho một tập các biến nào đó ảnh hưởng nhiều hơn các biến khác. Ví dụ, khi gom cụm các ứng viên cho môn bóng rổ thì chiều cao được ưu tiên hơn cả. Để chuẩn hóa các phép đo, một sự lựa chọn là chuyển các phép đo ban đầu thành các biến không đơn vị. Đối với một biến f có các số đo x1f, x2f...xnf, sự chuẩn hóa có thể được thực hiện theo các cách sau: Tính sai số tuyệt đối trung bình sf: (6.3) Trong đó mf là giá trị trung bình của f, có nghĩa là: (2) Tính độ đo chuẩn, hay z-score (chuẩn hóa z): (6.4) Dựa vào công thức (6.4) ta thấy rằng sai số tuyệt đối trung bình càng lớn thì hiện tượng cá biệt càng giảm. Do đó độ đo được chọn sẽ ảnh hưởng đến kết quả phân tich mẫu cá biệt. Các độ đo thông dụng cho biến trị khoảng: (1) Khoảng cách Euclide: (6.5) Trong đó i = (,,…,), j = (,,…,) là 2 đối tượng dữ liệu n chiều. Khoảng cách Manhattan: (6.6) Cả hai khoảng cách Euclide và Manhattan đều thõa các yêu cầu toán học của mộ phương trình khoảng cách: a. d(i,j)>=0: Khoảng cách phải là một số không âm. b. d(i,j) = 0: Khoảng cách của một đối tượng đến chính nó bằng không. c. d(i,j) =d(j,i): Khoảng cách là một hàm đối xứng. d. d(i,j) <= d(j,h) + d(h,j): Tính chất bất đẳng thức tam giác. Khoảng cách Minkowski: (6.7) Trong đó p là một số nguyên dương. Khoảng cách có trọng: (6.8) Khoảng cách có trọng là sự cải tiến của khoảng cách Minkowski, trong đó có tính đến ảnh hưởng của từng thuộc tính đến khoảng cách giữa hai đối tượng. Thuộc tính có trọng số w càng lớn thì càng ảnh hưởng nhiều đến khoảng cách d. Việc chọn trọng số tùy thuộc vào ứng dụng và mục tiêu cụ thể. Một biến nhị phân là bất đối xứng nếu có một trạng thái có ý nghĩa quan trọng hơn (thường được gán là 1). Lúc này thường có xu hướng thiên vị trạng thái ưu tiên đó. Ví dụ trong chuẩn đoán y khoa người ta thường ưu tiên một hướng kết luận hơn hướng kia. Do đó những trạng thái chưa rõ ràng (như triệu chứng bệnh chưa rõ ràng) thì cũng có thể kết luận là 1 để ưu tiên cho bước chuẩn đoán chuyên sâu hoặc cách ly theo dõi. Một ví dụ của biến nhị phân bất đối xứng là HIV có 2 trạng thái là dương tính (1) và âm tính (0). Object i Object j 1 0 sum 1 q r q + r 0 s t s + t sum q + s r + t p Bảng 3.8: Bảng sự kiện cho biến nhị phân Xét hai đối tượng i và j có các thuộc tính của đối tượng được biểu diễn bằng các biến nhị phân. Giả sử các biến nhị phân có cùng trọng số. Ta có bảng sự kiện như bảng 3.8. Trong đó q là số các biến nhị phân bằng 1 đối với cả 2 đối tượng i và j, s là số các biến nhị phân bằng 0 đối với i nhưng bằng 1 đối với j, r là số các biến nhị phân bằng 1 đối với i nhưng bằng 0 đối với j, t là số các biến nhị phân bằng 0 đối với cả hai i và j. 4.2.2.2 Các biến nhị phân Một biến nhị phân chỉ có hai trạng thái là 0 hoặc 1. Biến nhị phân là đối xứng nếu nếu cả hai trạng thái là tương đương (về mặt ý nghĩa của ứng dụng). Có nghĩa là không có xu hướng thiên vị trạng thái 1. Ví dụ thuộc tính gender có hai trạng thái là male hay female tương ứng với hai trạng thái là 0 và 1. Sự khác nhau của hai đối tượng dựa trên các biến nhị phân đối xứng (symmetric binary dissimilarity) là: (6.9) Sự khác nhau của hai đối tượng dựa trên các biến nhị phân bất đối xứng (asymmetric binary dissimilarity) (6.10) Chúng ta có thể đo khoảng cách giữa hai biến nhị phân dựa trên khái niệm tương tự nhau (similarity) thay vì không tương tự nhau sim(i,j) = 1 - d(i, j) (6.11) Hệ số sim(i,j) được gọi là hệ số jaccard. Ví dụ 6.1: Sự khác nhau giữa các biến nhị phân. Giả sử rằng một bảng các record của các bệnh nhân (bảng 3.9) chứa các thuộc tính name, gender, fever, cough, test-1, test-2, test-3 và test-4, trong đó name là thuộc tính định danh, gender là một thuộc tính đối xứng, và các thuộc tính còn lại là các thuộc tính nhị phân không đối xứng. Đối với các giá trị của các thuộc tính không đối xứng, cho các giá trị Y (yes) và P (positive) bằng 1, các giá trị N (no hay negative) bằng 0. Giả sử rằng khoảng các đối tượng (bệnh nhân) được tính dựa trên các thuộc tính không đối xứng. Name Gender Fever Cough Test-1 Test-2 Test-3 Test-4 Jack M Y N P N N N Mary F Y N P N P N Jim M Y Y N N N N … … … … … … … … Bảng 3.9: Một bảng quan hệ trong đó các bệnh nhân được mô tả bằng các biến nhị phân. Theo phương trình (6.10) khoảng cách giữa các cặp đối tượng là: Các phép đo chỉ ra rằng Marry và Jim có bệnh không giống nhau bởi vì d(Marry, Jim) là lớn nhất. 4.2.2.3 Các biến phân loại (biến định danh), biến thứ tự, và biến tỉ lệ theo khoảng 1. Các biến phân loại: Biến phân loại là biến có thể nhận dạng nhiều hơn hai trạng thái. Ví dụ biến màu sắc có thể có các trạng thái đỏ vàng lục và xanh. Cho số các trạng thái của một biến định danh là M. Các trạng thái có thể biểu thị bằng các chữ cái, kí hiệu, hay một tập các số nguyên như 1, 2, 3..., M. Chú ý rằng các số nguyên này chỉ dùng cho việc trình bày dữ liệu và không biểu diễn một giá trị nguyên cụ thể nào. Khoảng cách giữa 2 đối tượng i và j theo biến phân loại có thể được tính dựa trên hệ số đối xứng đơn giản: (6.12) Trong đó m là số thuộc tính phân loại có giá trị trùng khớp giữa hai đối tượng i và j, p là tổng số thuộc tính phân loại. Ví dụ 6.2: Sự khác nhau giữa các thuộc tính phân loại. Giả sử chúng ta có dữ liệu mẫu trong bảng 3.10, Ngoại trừ 2 biến object-identifier (biến định danh) và biến test-1 là biến phân loại đã xem xét (chúng ta sẽ sử dụng test-2 và test-3 trong các ví dụ sau). Object Identifier Test-1 (categorical) Test-2 (ordinal) Test-3 (ratio-scaled) 1 Code-A Excellent 445 2 Code-B Fair 22 3 Code-C Good 164 4 Code-A Excellent 1,210 Bảng 3.10: Bảng dữ liệu mẫu chứa các biến ở dạng hỗn hợp Ma trận phân biệt cho các đối tượng của bảng trên là: Ở đây chúng ta có một biến phân loại, test-1, nên p = 1. Do đó ma trận phân biệt sau khi tính toán là: 2. Biến thứ tự: Biến thứ tự là biến trên một tập giá trị có xác định quan hệ thứ tự trên đó, ví dụ hạng xếp loại huy chương vàng, bạc, đồng. Biến thứ tự có thể rời rạc hoặc liên tục. Các giá trị của một biến thứ tự f có Mf trạng thái. Các trạng thái được sắp xếp định nghĩa hạng (rank): 1,..., Mf. Giả sử rằng f là một biến từ một tập các biến thứ tự mô tả n đối tượng. Độ đo cho biến thứ tự f được xây dựng như sau: (1) Giá trị của biến f cho đối tượng thứ i là xif, và f có Mf trạng thái đã được sắp xếp, biểu diễn các cấp 1,..., Mf. Thay thế xif bởi cấp tương ứng của nó, rif{1,..., Mf}. (2) Ánh xạ hạng từng biến vào đoạn [0,1] bằng cách thay thế đối tượng i trong biến f bởi: (6.13) (3) Tính độ phân biệt theo các phương pháp đã biết đối với biến trị khoảng zif. Ví dụ 6.3: Sự khác nhau giữa các biến thứ tự. Giả sử chúng ta có dữ liệu mẫu cho trong bảng 6.3. Biến test-2 là biến thứ tự. Có 3 trạng thái cho biến test-2 theo trật tự sau: fair, good, và excellent, do đó Mf = 3. Đối với bước 1, chúng ta thay thế mỗi giá trị của test-2 bởi rank của nó, 4 đối tượng lần lượt được gán cho các rank: 3, 1, 2, 3. Bước 3 chuẩn hóa rank bằng cách ánh xạ theo công thức (6.13) ta được rank 1 --> 0 rank 2 --> 0,5 và rank 3 --> 1.0. Đối với bước 3, chúng ta sử dụng khoảng cách Euclide, kết quả thể hiện trong ma trận phân biệt sau đây: 3. Biến theo thang tỉ lệ (ratio-scaled variable): Biến tỉ lệ theo khoảng là độ đo dương trên các tỉ lệ phi tuyến. Ví dụ: Các đại lượng được biểu diễn theo hàm mũ chẳng hạn: AeBt. Trong đó A, B là các hằng số dương và t là biến biểu diễn thời gian. Trong đa số trường hợp ta không thể áp dụng trực tiếp phương pháp độ đo cho các biến trị khoảng cho loại biến này vì có thể gây sai số lớn. Phương pháp tốt hơn là tiền xử lý dữ liệu bằng cách chuyển sang logarit yif=log(xif) sau đó mới áp dụng trực tiếp cho các biến trị khoảng hoặc thứ tự. Ví dụ 6.4: Sự khác nhau giữa các biến tỉ lệ theo khoảng. Quay lại dữ liệu mẫu cho trong bảng 6.3. Biến test-3 là biến tỉ lệ theo khoảng. Áp dụng phương pháp chuyển đổi logarit ta thu được ma trận phân biệt sau: 4. Biến có kiểu hỗn hợp CSDL có thể chứa cả 6 loại biến nêu trên. Ta có thể dùng công thức được gán trọng để kết hợp các hiệu quả của các biến thành phần. Trong đó được tính như sau: - =0 khi xjf hay xif không tồn tại hoặc xif = xjf = 0. - = 1 trong các trường hợp khác. Ngoài ra dij(f) được tính như sau: - Đối với các biến trị khoảng hay thứ tự: dij(f) là khoảng cách đã được chuẩn hóa. - Đối với các biến nhị phân hay phân loại: + dij(f) = 0 khi xif = xjf = 0 + dij(f) = 1 trong các trường hợp khác 4.2.3 Các phương pháp gom cụm 4.2.3.1 Các phương pháp phân hoạch Đây là phương pháp phân hoạch CSDL D có n đối tượng thành k cụm sao cho i) Mỗi cụm chứa ít nhất một đối tượng. ii) Mỗi đối tượng thuộc về một cụm duy nhất. iii) k là số cụm được cho trước. Đây là tiêu chuẩn chung của các phương pháp phân hoạch truyền thống. Gần đây xuất hiện nhiều phương pháp phân hoạch dựa trên lý thuyết tập mờ thì tiêu chuẩn (ii) là không quan trọng mà thay vào đó là mức thuộc về một cụm của một đối tượng nào đó, mức độ này có giá trị từ 0 đến 1. Các phương pháp tiếp cận phân hoạch: K-means: Mỗi cụm được biểu diễn bằng giá trị trung bình của các đối tượng trong cụm. K-medoids: Mỗi cụm được biểu diễn bằng một trong các đối tượng nằm gần tâm của cụm. 4.2.3.2 Các phương pháp phân cấp Đây là các phương pháp tạo phân cấp cụm chứ không phải tạo các phân hoạch các đối tượng. Phương pháp này không cần xác định số cụm ngay từ đầu. Số cụm sẽ do khoảng cách giữa các cụm hoặc do điều kiện dừng quyết định. Hai cách tiếp cận gồm: Gộp và Tách. Gộp: (1) Xuất phát từ mỗi đối tượng và một cụm chứa nó. (2) Nếu 2 cụm đủ gần nhau (dưới một ngưỡng nào đó) sẽ được gộp lại thành một cụm duy nhất. (3) Lặp lại bước 2 đến khi chỉ tất cả các cụm được gộp lại thành 1 cụm hay đến khi điều kiện dừng. Tách: (1) Xuất phát từ một cụm duy nhất là toàn bộ không gian. (2) Chọn cụm có độ phân biệt cao nhất (ma trận phân biệt có phần tử lớn nhất hay trị trung bình lớn nhất) để tách đôi. Bước này sẽ áp dụng các phương pháp phân hoạch đối với cụm đã chọn. (3) Lặp lại bước 2 cho đến khi mỗi đối tượng thuộc một cụm hoặc đạt điều kiện dừng (đủ số cụm cần thiết hay khoảng cách giữa các cụm đạt ngưỡng đủ nhỏ). Ngoài ra còn có các phương pháp như: - Phương pháp dựa trên mật độ. - Phương pháp dựa trên mô hình. - Phương pháp dựa trên lưới. 4.2.4 Thuật toán gom cụm bằng phương pháp K-means Thuật toán k-means phân hoạch một tập n object vào trong k cluster sao cho các đối tượng trong một cluster có độ tương tự cao và các đối tượng trong các cluster khác nhau có độ tương tự thấp. Mỗi cluster được đại diện bởi trọng tâm (cluster mean) của nó. Phương pháp k-means phân hoạch một đối tượng vào các cụm dựa trên khoảng cách của đối tượng đó đến trọng tâm của các cụm. Một đối tượng được phân vào một cluster nếu khoảng cách từ đối tượng đó đến cluster đang xét là nhỏ nhất. Sau đó các cluster mean được cập nhật. Quá trình lặp đi lặp lại cho đến khi hàm mục tiêu đồng qui. Một cách điển hình, hàm mục tiêu square-error được sử dụng: Trong đó, p là đối tượng thuộc cluster Ci, mi là trọng tâm của cluster Ci. 4.2.4.1 Thuật toán k-means Input: + k: Số các cluster. + D: Một tập dữ liệu chứa n đối tượng Output: Một tập k cluster. Method: (1) Chọn ngẫu nhiên k đối tượng từ D làm trọng tâm ban đầu của k cluster; (2) repeat (3) Gán (hay gán lại) mỗi đối tượng cho cluster mà nó gần nhất, dựa trên việc so sánh các khoảng cách của đối tượng đó đến các cluster.. (4) Cập nhật các giá trị trung bình của các cluster (5) until không có sự thay đổi trong các cluster Ví dụ 6.5: Gom cụm bằng phân hoạch k-means. Giả sửu có một tập các đối tượng được phân bố trong không gian như hình (6.1 a). Cho k=3. Hình 3.5: Minh họa thuật toán k-means Hình 3.5 a: Chọn ngẫu nhiên 3 đối tượng làm 3 trọng tâm ban đầu của 3 cluster. Ba đối tượng này được đánh dấu +. Mỗi đối tượng còn lại được phân bổ vào một cluster nếu đối tượng đó gần trọng tâm của cluster đó nhất. Ta được 3 cluster được khoanh vùng bằng các đường gạch chấm như hình vẽ. Hình 3.5 b: Trọng tâm của mỗi cluster được cập nhật. các trọng tâm sau khi được cập nhất được đánh dấu +. Sử dụng các trọng tâm cluster mới, phân bổ lại các đối tượng vào các cluster dựa trên khoảng cách gần nhất của đối tượng đó với các trọng tâm cluster. Các cluster kết quả được khoanh bằng các đường chấm. Hình 3.5 c: Lặp lại như các bước trong hình 3.5 b. Các cluster kết quả được khoanh bằng các đường liền nét. Lặp lại như trong hình 3.5 b, kết quả không có sự thay đổi. Dừng thuật toán. Kết quả thu được là 3 cluster được khoanh bằng các đường liền nét. Ví dụ 6.6: Cho tập điểm x1= {1, 3} = {x11, x12} x2 = {1.5, 3.2} = {x21, x22} x3 = {1.3, 2.8} = {x31, x32} x4 = {3, 1} = {x41, x42} Dùng thuật toán k-means để gom cụm với k = 2. Bước khởi tạo: - Khởi tạo ma trận phân hoạch M có 4 cột tương ứng với 4 điểm và 2 dòng tương ứng với 2 cluster. Các phần tử trong ma trận ( mij với i = 1, 2; j= 1, 4) được gán giá trị khởi tạo 0. x1 x2 x3 x4 c1 0 0 0 0 c2 0 0 0 0 - Chọn x1, x2 lần lượt làm trọng tâm ban đầu cho 2 cluster c1, c2. Trọng tâm của 2 cluster lần lượt là: v1 = {1, 3} = {v11, v12}; v2 = {1.5, 3.2} = {v21, v22}. - Cập nhật ma trận phân hoạch M: x1 x2 x3 x4 c1 1 0 0 0 c2 0 1 0 0 Bước 1: - Gán các đối tượng vào các cluster: Tính các khoảng cách Euclide: Xếp x1 vào cụm c1. Xếp x2 vào cụm c2. Xếp x3 vào cụm c1. Xếp x4 vào cụm c2. - Cập nhật lại ma trận phân hoạch ta được: x1 x2 x3 x4 c1 1 0 1 0 c2 0 1 0 1 Bước 2: Cập nhật lại trọng tâm các cluster: Quay lại bước 1: - Gán các đối tượng vào các cluster: Tính các khoảng cách Euclide: Xếp x1 vào cụm c1. Xếp x2 vào cụm c2. Xếp x3 vào cụm c1. Xếp x4 vào cụm c2. - Cập nhật lại ma trận phân hoạch: x1 x2 x3 x4 c1 1 1 1 0 c2 0 0 0 1 Bước 2: Cập nhật lại trọng tâm cho các cluster Ma trận phân hoạch thay đổi do đó ta quay lại bước 2 và tiếp tục cho đến khi ma trận phân hoạch không thay đổi. * Ưu và nhược điểm của thuật toán a. Ưu điểm: + Tương đối nhanh. Độ phức tạp của thuật toán là O(tkn), trong đó: - n: Số đối tượng trong không gian dữ liệu. - k: Số cụm cần phân hoạch. - t: Số lần lặp (t thường khá nhỏ so vơi n). + K-means phù hợp với các cụm có dạng hình cầu. b. Khuyết điểm: + Không đảm bảo đạt được độ tối ưu toàn cục và kết quả đầu ra phụ thuộc nhiều vào việc chọn k điểm khởi đầu. Do đó phải chạy lại thuật toán với nhiệu bộ khởi đầu khác nhau để có được kết quả đủ tốt. + Cần phải xác định trước số cụm. + Khó xác định số cụm thực sự mà không gian dữ liệu có. Do đó có thể phải thử với các giá trị k khác nhau. + Khó phát hiện các loại cụm có hình dạng phức tạp khác nhau và nhất là các dạng cụm không lồi. + Không thể xử lý nhiễu và mẫu cá biệt. + Chỉ có thể áp dụng khi tính được trọng tâm. 4.2.4.2 Kỹ thuật dùng đối tượng đại diện: Phương pháp k-medoids Thuật toán k-means không chính xác trong trường hợp dữ liệu dữ liệu bị nhiễu bởi vì một đối tượng với giá trị rất lớn có thể ảnh hưởng rất nhiều trong việc phân bố dữ liệu vào các cụm. Để khắc phục lỗi trên, thay vì dùng giá trị trung bình của các đối tượng trong một cluster làm điểm đại diện cho cluster, chúng ta có thể dùng một đối tượng thực sự để đại diện cho cluster đó. Mỗi đối tượng còn lại được phân vào cụm mà đối tượng đại diện tương tự với nó nhất. Phương pháp phân hoạch dựa trên nguyên lý cực tiểu các sự khác nhau giữa mỗi đối tượng và đối tượng đại diện tương ứng. Do đó hàm mục tiêu absolute-error được sử dụng: Trong đó p là điểm trong không gian biểu diễn một đối tượng trong cluster Cj ; và oj là đối tượng đại diện của của Cj. Trong trường hợp tổng quát, thuật toán lặp cho đến khi mỗi đối tượng đại diện là một medoid thực sự, có nghĩa là nó nằm ở trung tâm của cluster tương ứng. Đây chính là ý tưởng cơ bản của phương pháp k-medois. Thuật toán k-medoids Input: Tập dữ liệu D; số cluster k. Output: k cluster. Method: (1) Chọn ngẫu nhiên k đối tượng Oi (i=1..k) làm trung tâm (medoids) ban đầu của cụm. (2) Repeat (3) Gán (hoặc gán lại) từng đối tượng còn lại vào cụm có trung tâm gần điểm đang xét nhất. (4) Với mỗi đối tượng trung tâm - Lần lượt xét các đối tượng không là trung tâm (non-medoids) x. - Tính độ lợi S khi hoán đổi Oi bởi x S được xác định như sau: S = Ex – EOi - Nếu S<0 thì thay thế Oi bởi x. (5) Until không có sự thay đổi trong các cluster. Ưu điểm: K-medoids làm việc được với nhiễu và biệt lệ. Khuyết điểm: K-medoid chỉ hiệu quả khi tập dữ liệu không quá lớn vì có độ phức tạp là O(k(n-k)2t). Trong đó: n: Số điểm trong không gian dữ liệu. k: Số cụm cần phân hoạch. t: Số lần lặp, t khá nhỏ so với n. 4.2 Sơ đồ phân tích thiết kế chương trình (các mẫu) Các tham số Các mẫu bất thường Dữ liệu bổ sung Tiến trình khai phá dữ liệu Dữ liệu được chuyển đổi Các cụm Raw Audit Data Cơ sở dữ liệu chuyển đổi Cơ chế xử lý Hình : Nguyên lý chung của một tiến trình phát hiện xâm nhập sử dung kỹ thuật phân cụm 4.2.1 Tập hợp dữ liệu và tiền xử lý 4.2.1.1 Tập hợp dữ liệu Đối với hệ thống *NIX có thể dùng công cụ rất thông dụng TCPDUMP cho mục đích thu thập dữ liệu và sàng lọc dữ liệu qua giao tiếp mạng. Tcpdump là một tiến trình chạy ở chế độ nền (background), nó sẽ kết xuất các thông tin cần thiết (qua các tham số dòng lệnh) ra tập tin. Cứ mỗi thời điểm có n packet được tập hợp và lưu trữ cho việc xử lý sau này cũng như nhằm phục vụ công việc phân lớp, sau đó tiến trình thu thập thông tin lại được tiếp diễn. Khi lưu các thông tin về packet thành tập tin trong mỗi chu kỳ xử lý, các thông tin cần thiết sẽ được đơn giản hóa sử dụng các tham số của tcpdump, ví dụ: tcpdump –c 50 –w dump host victim-machine Đối với mỗi packet Ethernet nhận được: { - phân giải lớp địa chỉ IP đích - phân giải lớp địa chỉ nguồn - lấy thông tin về giao thức } Địa chỉ IP của đích cũng như nguồn theo khuôn dạng 4 số thập phân phân cách nhau bởi dấu chấm, ví dụ 192.168.43.2. Một thông tin khác rất quan trọng trong quá trình thu lập là loại giao thức, đó là một trong hai loại giao thức TCP và UDP. Một số giáo thức dạng khác dựa trên TCP và UDP như ICMP, ARP, và RARP cũng sẽ được xét đến. Bảng sau cung cấp một ví dụ về kết xuất của tcpdump bao gồm các thông tin địa chỉ IP nguồn và đích, và tiếp đến là giao thức cho mỗi packet: 192.168.138.20.123 > 192.168.166.63.123: udp 48 192.168.166.63 > 19.168.138.20: icmp:192.168.166.63 udp port 123 unreachable (DF) arp who-has 192.168.138.1 tell 192.168.138.20 arp reply 192.168.138.1 is-at 0:0:c:7:ac:0 192.168.138.20.123 > 192.168.63.1.123: udp 48 192.168.138.20.123 > 192.168.63.2.123: udp 48 192.168.138.20.123 > 192.168.166.63.123: udp 48 192.168.133.46 > 192.168.138.20: icmp: echo request (DF) 192.168.138.20 > 192.168.133.46: icmp: echo reply 192.168.133.46 > 192.168.138.20: icmp: echo request (DF) 192.168.138.20 > 192.168.133.46: icmp: echo reply 192.168.133.46 > 192.168.138.20: icmp: echo request (DF) 192.168.138.20 > 192.168.133.46: icmp: echo reply Trên các máy HOST nếu sử dụng OS khác *NIX (dùng Windows) thì có thể dùng công cụ WinDump được xem là phiên bản của tcpdump trên Windows. Windump cũng tương thích hoàn toàn với tcpdump và cũng sử dụng để bắt, kiểm tra và lưu vào đĩa các network traffic. Windump tương thích với Windows 95, 98, ME, NT, 2000, XP, 2003 and Vista, dựa trên thư viện và các điều khiển của trình WinPcap ( Windump là miễn phí theo giấy phép BSD-style có tại Trong phần chương trình thiết kế trong đồ án có sử dụng dữ liệu thô thu được nhờ việc ghi dấu vết trên mạng DMZ Ethernet, dấu vết này được thu từ ngày 16/9/1993 đến 15/10/1993 và đã bắt được 782281 kết nối diện rộng giữa phòng thí nghiệm Berkeley Lawrence với phần còn lại của mạng. Dấu vết thô được lấy bằng cách sử dụng TCPdump trên một Sun Sparcstation sử dụng bộ lọc gói nhân BPF. 4.2.1.2 Tiền xử lý Dữ liệu thô ở đây được tập hợp dưới dạng một file .txt, mỗi khi có kết nối thì sẽ có một dòng được tự động thêm vào file. File ở phần đồ án này gồm có 9 phần được ngăn cách nhau bằng khoảng trắng: Trường Ý nghĩa TimeStamp Tem thời gian, ghi lại thời điểm kết nối xảy ra có độ chính xác Micro giây Duration Khoảng thời gian sống của kết nối tính bằgn giây Protocol Giao thức của kết nối Byte sent by origination Kích thước gói tin được gửi đi tính bằng byte, nếu không xác định được thay bằng “?” Byte sent by responder Kích thước gói tin phản hồi tính bằng byte, nếu không xác định được thay bằng “?” Remote host Địa chỉ IP của máy ở ngoài mạng, theo khuôn dạng 4 số thập phân cách nhau bằng dấu chấm Localhost Địa chỉ của máy nội bộ theo khuôn dạng 4 số thập phân cách nhau bằng dấu chấm. Ở đây chỉ số cuối trong địa chỉ thay vì phải dùng toàn bộ địa chỉ IP bởi vì các host nội bộ có ba số đầu là giống nhau. State Trạng thái của kết nối. Hai trạng thái quan trọng nhất là SF-mô tả một kết nối bình thường và REJ-một kết nối bị từ chối (khởi đầu SYN nhưng không nhận được một RST đáp lại), ngoài ra còn một số trạng thái khác như: S0, S1, S2, S3, S4, RSTOSn, RSTRSn, SHR, Sha, SS, OOS1, OOS2… Flag Cờ (có thể có hoặc không) cho biết kết nối giữa nội bộ hay với mạng ngoài. L-kết nối được bắt nguồn từ mạng nội bộ, N-kết nối với mạng gần, cò này chủ yếu được thiết lập cho các kết nối nntp Ví dụ: 748162802.427995 1.24383 smtp ? ? 1 128.97.154.3 REJ L 748162802.803033 3.96513 smtp 1173 328 3 128.8.142.5 SF 748162804.817224 1.02839 nntp 58 129 2 140.98.2.1 SF L 748162812.254572 138.168 nntp 363238 1200 4 128.49.4.103 SF L 748162817.478016 10.0858 nntp 230 100 4 128.32.133.1 SF N 748162833.453963 2.16477 smtp 2524 306 5 192.48.232.17 SF 748162836.735788 13.1779 smtp 16479 174 16 128.233.1.12 RSTRS3 L Dữ liệu thô ban đầu được đọc và lưu vào một bảng (TCP) trong cơ sở dữ liệu TCP Biến đổi “RemoteHost” về dạng số nguyên bằng cách thêm một bảng để tham chiếu Gom cụm dữ liệu theo một cửa sổ thời gian xác định và lưu kết quả nhóm cụm trong một bảng trung gian TCP_F 4.2.2 Khai phá dữ liệu phát hiện tấn công từ chối dịch vụ 4.2.2.1 Các mẫu bất thường của tấn công từ chối dịch vụ Từ khảo sát thực tế kết hợp với những kiến thức, các chuyên gia trong lĩnh vực an ninh cho thấy: Các tấn công từ chối dịch vụ chủ yếu tấn công qua giao thức HTTP. Các request của giao thức HTTP bình thường chỉ là các địa chỉ Web (URL) nên có kích thước rất nhỏ. Song có rất nhiều tấn công, kẻ tấn công thường chèn mã lệnh thực thi trên trình duyệt nạn nhân (cross site scripting), ví dụ: sử dụng các script (đoạn mã) dạng tập tin flash hay chèn các truy vấn SQL vào URL… Điều này làm cho các request này có kích thước lớn hơn bình thường. Vì thế theo nghiên cứu cho thấy thì các request của giao thức này có kích thước >=350 byte là những mẫu bất thường có khả năng là tấn công. Tấn công từ chối dịch vụ có rất nhiều dạng như Ping of Death, Teardrop, Aland Attack, Winnuke, Smurf Attack, UDP/ICMP Flooding, TCP/SYN Flooding, Attack DNS. Ping Of Death. Một số máy tính sẽ bị ngưng họat động, Reboot hoặc bị crash khi bị nhận những gói dữ liệu ping có kích thước lớn. • Ví dụ như : ping địachỉ -n 1000 trong đó : số 1000 là số lần gửi gói dữ liệu. TCP/SYN Flooding: Bước 1: Khách hàng gửi một TCP SYN packet đến cổng dịch vụ của máy chủ Khách hàng -> SYN Packet -> Máy chủ Bước 2 : Máy chủ sẽ phản hồi lại khách hàng bằng 1 SYN/ACK Packet và chờ nhận một 1 ACK packet từ khách hàng Máy chủ -> SYN/ACK Packet -> Khách hang Bước 3: Khách hàng phản hồi lại Máy chủ bằng một ACK Packet và việc kết nối hòan tất Khách hàng và máy chủ thực hiện công việc trao đổi dữ liệu với nhau. Khách hàng -> ACK Packet -> Máy chủ • Trong trường hợp Hacker thực hiện việc SYN Flooding bằng cách gửi tới tấp, hàng loạt TCP SYN packet đến cổng dịch vụ của máy chủ sẽ làm máy chủ bị quá tải và không còn khả năng đáp ứng được nữa UDP/ICMP Flooding: Hacker thực hiện bằng cách gửi 1 số lượng lớn các gói tin UDP/ICMP có kích thước lớn đến hệ thống mạng, khi hệ thống mạng chịu phải sự tấn công này sẽ bị qua tải và chiếm hết băng thông đường truyền đi ra bên ngoài của mạng này, vì thế nó gây ra những ảnh hưởng rất lớn đến đường truyền cũng như tốc độ của mạng, gây nên những khó khăn cho khách hàng khi truy cập từ bên ngoài vào mạng này. Þ Ta có mẫu bất thường là một “RemoteHost” trong một khoảng thời gian được xét gửi một lượng lớn gói tin tới một “LocalHost” tức là một “RemoteHost” gửi rất nhiều request tới một “LocalHost” trong khoảng cửa sổ thời gian. Tuỳ theo từng điều kiện hệ thống mạng cần bảo vệ mà ngưỡng số request này thay đổi, việc lựa chọn cẩn thận ngưỡng này sẽ cho ta các cảnh báo đúng và nó phụ thuộc rất nhiều vào kinh nghiệm thực tế. Nhưng với những tiện ích như Trinoo, TFN2K, Stacheldraht… người tấn công không phải chỉ dùng 1 nơi để tấn công mà sử dụng nhiều mạng lưới khác nhau để thực hiện việc tấn công đồng loạt vào máy nạn nhân. Tức là sẽ có một số lượng lớn các Request từ các địa chỉ mạng khác nhau tới cùng một khoảng thời gian trong một khoảng thời gian rất ngắn (DDoS). Þ Ta có mẫu bất thường có nhiều request đến một máy “LocalHost” trong một khoảng thời gian ngắn. Cũng tuỳ thuộc vào điều kiện của mạng và máy mà ngưỡng số request này thay đổi cho phù hợp. Ngoài ra còn có rất nhiều các mẫu bất thường của tấn tấn công từ chối dịch vụ với những đặc trưng khác nhau nhưng trong phạm vi của đồ án này chỉ sử dụng một số mẫu bất thường cơ bản trong tấn công từ chối mà thông qua quá trình phân tích thực tế đã thu được. 4.2.2.2 Khai phá dữ liệu Trong quá trình khai phá dữ liệu này, dữ liệu được sử dụng để huấn luyện ở đây chính là các mẫu bất thường mô tả các tấn công từ chối dịch vụ đã thu được ở trên với các tham số tuỳ chọn về số request cũng như khoảng thời gian xem xét để phù hợp với các hệ thống khác nhau. Kỹ thuật gom cụm được sử dụng trong phần demo này là kỹ thuật dùng đối tượng đại diện: Phương pháp k-medoids. Các mẫu bất thường ở đây sẽ được sử dụng là đại diện cho cụm “xâm nhập” và phần còn lại sẽ là cụm “bình thường”. Do đó ở đây ta sẽ có hai cụm. Dữ liệu sau tiến trình tiền xử lý đã được phân vào các nhóm thời gian với độ rộng tuỳ chọn trước. Đến đây tuỳ thuộc vào việc chọn các dấu hiệu để phát hiện tấn công từ chối dịch vụ mà ta có các cách xử lý phù hợp: Nếu lựa chọn dấu hiệu của tấn công từ chối dịch vụ là dấu hiệu trong sử dụng giao thức HTTP mà trong cơ sở dữ liệu demo là WWW thì ta sẽ sử dụng mẫu bất thường về tấn công từ chối dịch vụ trong giao thức này với các tham số đầu vào là ngưỡng kích thước gói tin request và số request thoả mãn ngưỡng kích thước này tới máy chủ Web mà ở đây chính là một máy trong mạng nội bộ cần được bảo vệ “Localhost” để làm các tham số đầu vào của thuật toán k-medoids. Đầu ra của thuật toán sẽ là hai cụm: cụm chứa các mẫu được xem là bất thường là các mẫu có số kết nối mà các kết nối này có kích thước gói request lớn hơn kích thước được đưa ra, lớn hơn ngưỡng số request trong một khoảng thời gian cụ thể được chọn và cụm các mẫu bình thường là các mẫu không có đặc điểm trên. Nếu lựa chọn dấu hiệu tấn công từ chối dịch vụ truyền thống DoS thì đầu vào của thuật toán chỉ là ngưỡng số request và thuộc tính được xem xét ở đây chính là thuộc tính “RemoteHost”. Đầu ra của thuật toán là hai cụm: cụm các bất thường chứa các mẫu mà số request từ một “RemoteHost” trong một khoảng thời gian xác định lớn hơn ngưỡng kết nối và cụm bình thường. Nếu lựa chọn dấu hiệu tấn công từ chối dịch vụ theo kiểu nhiều request từ nhiều địa chỉ IP khác nhau tới một máy cục bộ thì cũng tương tự như dấu hiệu tấn công DoS nhưng lúc này thuộc tính được xem xét ở đây là thuộc tính “LocalHost”. Sau khi thuật toán kết thúc sẽ cho ta hai cụm, một cụm các mẫu bất thường có số request đến một máy nội bộ lớn hơn ngưỡng kết nối được chọn. Bầy giờ ta đã thu được hai cụm phân tách: cụm bất thường và cụm bình thường. 4.2.3 Biểu diễn dữ liệu Sau khi dữ liệu đã được gom vào hai cụm như trên, dữ liệu cần được biểu diễn để người dùng có thể dễ dàng hiểu được. Có rất nhiều cách thức để biểu diễn dữ liệu này nhưng trong phần demo này chỉ biểu diễn các dữ liệu này dưới dạng các bản ghi của một bảng các mẫu bất thường. Ví dụ: Đối với lĩnh vực khai phá dữ liệu trong hệ thống phát hiên xâm nhập này, ngoài việc hiển thị kết quả thì các kết quả này sẽ được tiếp tục được dùng để xử lý ví dụ như đưa ra các cảnh báo, thực hiện một số hành động để chống lại những mối nguy hạn đã khai phá được này… Nhưng trong phạm vi của đồ án sẽ không đi sâu vào vấn đề này. Chương 5 KẾT QUẢ ĐẠT ĐƯỢC – ĐÁNH GIÁ, KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 5.1 Cài đặt Hệ thống chương trình được cài đặt bằng ngôn ngữ C# trên môi trường Microsoft Visual Studio .NET 2005 và hệ điều hành Windows XP. Bước đầu chương trình cũng hình thành được phần giao diện tương đối thân thiện với người dung. Cấu hình hệ thống: Chương trình nên được chạy trên hệ điều hành WinNT, Windows 2000 Advance Server, Windows 2000 Professional hay Win XP. Và đòi hỏi máy có cấu hình sau: Cấu hình máy tối thiểu: Tốc độ CPU: 1.5GHz Dung lượng bộ nhớ: 256 MB Không gian trống trên ổ cứng: 500 MB Cấu hình máy đề nghị: Tốc độ CPU: 3.2GHz Dung lượng bộ nhớ: 512 MB (hoặc lớn hơn) Không gian trống trên ổ cứng: 1 GB Thông tin chương trình cài đặt: Ngôn ngữ C Sharp (C#) Công cụ phát triển Microsoft Visual Studio 2005 Kiểu ứng dụng Ứng dụng Windows 32 bits Hệ điều hành WinNT, Windows 2000 Advance Server, Windows 2000 Professional hay Win XP Môi trường hoạt động MS .NET Framework 1.0 Cơ sở dữ liệu Microsoft SQL Server 7, 2000 Kết nối cơ sở dữ liệu ADO.NET 5.2 Kết quả đạt được Phần này sẽ giới thiệu qua về các giao diện của chương trình cũng như một số kết quả thu được thông qua thực thi chương trình. Giao diện chính của chương trình: Hình 5.1 Giao diện chính Trong giao điện này, chức năng của các thành phần cụ thể như sau: Buttom “Chọn file” cho phép ta chọn file dạng .txt hay .log để khai phá. File ở đây sẽ được khai phá theo dấu hiệu số kết nối từ một RemoteHost trong khoảng thời gian (cửa sổ thời gian) Nút “HTTP” sẽ cho phép ta đi vào một giao diện mới để khai phá theo dấu hiện bất thường trong giao thức HTTP cũng như một số lựa chọn khác “Tự động” sẽ đưa ta tới một giao diện mới cho phép thực thi việc khai phá một cách tự động cứ sau một khoảng thời gian tuỳ chọn “Gom dữ liệu” thực hiện việc đọc dữ liệu từ file được chọn vào bảng dữ liệu TCP đồng thời chuyển đổi một số thuộc tính từ dạng văn bản về dạng số như: tem thời gian, thời gian kết nối duy trì,… và thêm các dữ liệu còn thiếu “Tiền xử lý” mở ra một giao diện mới thực hiện chức năng tiền xử lý cho dữ liệu đã thu được ở trên “Làm lại” cho phép chọn lại file để thực hiện lại việc khai phá từ đầu “Thoát” cho phép thoát khỏi chương trình Giao diện Tiền xử lý: Hình 5.2 Tiền xử lý dữ liệu “Thời gian xử lý”: cho phép tuỳ chọn khoảng thời gian (cửa sổ thời gian) để xử lý, thời gian này tính bằng giây. Giá trị mặc định là 60 giây “Tiền xử lý”: đưa dữ liệu về các kết nối về dạng phù hợp với thuật toán như chuyển “RemoteHost” về dạng số, gom nhóm theo thời gian các kết nối này “Kết quả”: hiển thị kết quả “Tiền xử lý” trong phần “Kết quả tiền xử lý” ở bên “Khai phá”: mở ra giao diện để tiến hành khai phá tìm ra các bất thường “Thoát”: quay về màn hình chính Màn hình khai phá Hình 5.3 Giao diện khai phá “Độ phổ biến”: tuỳ chọn độ phổ biến của kết nối có dấu hiệu bất thường, chính là ngưỡng số kết nối dùng làm tham số đầu vào của thuật toán khai phá, tính theo đơn vị số lần xuất hiện. Để tránh những kết quả sai ta phải chọn giá trị này một cách thích hợp, chủ yếu là tuỳ vào thực nghiệm cũng như kinh nghiệm của người dung. Ở đây không dùng đơn vị của ngưỡng kết nối là % vì sẽ có rất nhiều trường hợp tổng số kết nối là vô cùng nhỏ chẳng hạn là 2 thì chắc chắn ở đây sẽ cho ta một dấu hiệu bất thường nếu ta chọn ngưỡng 50% thì lại cho kết quả sai lớn khi mà tổng kết nối trong một cửa sổ thời gian nào đó là rất lớn… “Kết quả”: hiểm thị kết quả khai phá được (cụm những bất thường) “Quay về”: quay về cửa sổ “Tiền xử lý” để có thể thực hiện lại quá trình tiền xử lý “Thoát”: thoát khỏi chương trình Cửa sổ khai phá dựa trên giao thức HTTP Hình 5.4 Màn hình khai phá dữ liệu của giao thức HTTP “Chọn file Audit”: có chức năng tương tự như trong giao diện chính “Chọn bảng trong cơ sở dữ liệu”: cho phép tiến hành khai phá trên dữ liệu đã có sẵn trong cơ sở dữ liệu của chúng ta (TCP) “Chọn khoảng thời gian”: Chức năng đã được đề cập trong màn hình “Tiền xử lý” “HTTP”: Nếu được lựa chọn thì sẽ thực thi khai phá theo dấu hiệu bất thường trên giao thức HTTP, khi chức năng này được chọn thì ta phải nhập ngưỡng kết nối và ngưỡng kích thước của các Request HTTP “Tất cả các giao thức”: thực thi khai phá dựa trên dấu hiệu số các request của tất cả các giao thức. “Khai phá”: nút thực hiện chức năng khai phá dựa trên dữ liệu thu được cùng với các thông số tuỳ chọn “Thực hiện lại”: chọn và thực quá trình khai phá “Quay về”: trở về màn hình chính “Thoát”: thoát khỏi chương trình Màn hình thực hiện chức năng khai phá tự động Hình 5.5 Màn hình tự động khai phá “Chọn file dữ liệu Audit”: tương tự như bên trên “Chọn khoảng thời gian”: tương tự như trên “Ngưỡng”: ngưỡng số kết nối “Mốc thời gian hiện tại”: Do dữ liệu khai phá là dữ liệu độc lập nên ta phải chọn mốc thời gian ban đầu để bắt đầu khai phá. Khi tích hợp vào hệ thống thực thì không phải thực hiện bước này vì nó lấy là thời gian của hệ thống hiện tại “Tự động”: thực hiện khai phá tự động với các thông số bên trên. Sẽ có sự kiểm tra tính đúng đắn của các thông số được nhập. “Stop”: tạm thời dừng việc thực thi khai phá tự động, trạng thái của chương trình sẽ được duy trì. Khi thực hiện tiếp nó sẽ tiếp tục khai phá từ vị trí đang đừng lại đó. “Làm lại”: thực hiện lại từ đầu quá trình tự động “Quay về”: trở về màn hình chính “Thoát”: thoát khỏi hệ thống Tốc độ thực thi: Cửa sổ thời gian: 60 giây Tổng số kết nối Thời gian xử lý (S) 18 0.046875 14 0.03125 11 0.0625 11 0.015625 16 0.03125 15 0.015625 24 0.03125 19 0.03125 20 0.03125 9 0.25 0 – 8 ~ 0 Cửa sổ thời gian: 120 giây Tổng số kết nối Thời gian xử lý (S) 28 0.40625 30 0.0625 22 0.046875 28 0.0625 31 0.03125 47 0.0625 25 0.03125 40 0.0625 26 0.015625 <10 ~ 0 10 - 20 ~ 0.015625 Cửa sổ thời gian: 300 giây Tổng số kết nối Thời gian xử lý (S) 69 0.3125 51 0.046875 31 - 45 0.03125 69 0.078125 106 0.078125 116 0.09375 170 0.140625 162 0.125 194 0.15625 249 0.1875 212 0.15625 278 0.203125 291 0.21875 364 0.265625 413 0.375 433 0.421875 Cửa sổ thời gian: 600 giây Tổng số kết nối Thời gian xử lý (S) 120 0.09375 202 0.15625 372 0.28125 245 0.1875 426 0.375 473 0.515625 551 0.4375 605 0.5 906 0.78125 799 0.671875 857 0.75 1145 0.9375 1426 1.296875 1776 1.59375 3293 2.96875 Ta có thể thấy tốc độ xử lý phụ thuộc vào nhiều yếu tố mà yếu quan trọng ta quan tâm ở đây là khoảng thời gian gom nhóm và số kết nối trong từng nhóm sẽ làm ảnh hưởng tới thời gian xử lý như thế nào. 5.3 Kết luận Trong quá trình hoàn thành đề tài này, dù đã đạt được những kiến thức nhất định, nhưng tôi nhận thấy Khai phá dữ liệu nói chung và khai phá dữ liệu trong hệ thống IDS/IPS nói riêng là một lĩnh vực nghiên cứu rộng lớn, nhiều triển vọng. Đề tài đã trình bày được các vấn đề cơ bản về khai phá dữ liệu: Tầm quan trọng của KPDL, các hướng tiếp cận khai phá dữ liệu và các kỹ thuật khai phá dữ liệu. Sử dụng thuật toán gom cụm mà cụ thể ở đây là phương thức k-medoids để ứng dụng vào khai phá dữ liệu để phát hiện xâm nhập. Với đề tài này, chứng tở khả năng ứng dụng trí tuệ nhân tạo trong ngành chuyên sâu của khoa học máy tính và các ngành khác, nhất là về mạng máy tính, mạng Internet. Đề tài đã đua ra mô hình hoạt động của một hệ thống thông minh trợ giúp người dùng và người quản trị mạng nhằm phát hiện các xâm nhập tiền ẩn khả năng tấn công tấn công từ chối dịch vụ. Tuy nhiên, do hạn chế về mặt thời gian và lượng kiến thức vốn có nên phần nghiên cứu mới chỉ dừng lại ở cấp độ demo hệ thống với một số kiểu tấn công tấn công từ chối dịch vụ đơn giản. Khi mà lượng dữ liệu thu thập và lưu trữ ngày càng tăng, cùng với nhu cầu nắm bắt thông tin, thì nhiệm vụ đặt ra cho Khai phá dữ liệu ngày càng quan trọng. Sự áp dụng được vào nhiểu lĩnh vực kinh tế xã hội, an ninh quốc phòng, an ninh mạng… cũng là một ưu thế của khai phá dữ liệu. Với những mong muốn đó tôi hy vọng sẽ dần đưa những kiến thức đã có từ đề tài này sớm trở thành thực tế, phục vụ cho cuộc sống con người chúng ta. Đề tài còn nhiều khiếm khuyết, cần thời gian để hoàn thiện và phát triển thêm. 5.4 Hướng phát triển Trên cơ sở đã trình bày, hiện thực một công cụ cảnh báo tấn công từ chối dịch vụ với giao diện đồ họa thân thiện và có khả năng phản ứng phù hợp với những hành vi được xem là bất thường đó. Cải tiến trở thành công cụ giám sát thời gian thực các cuộc tấn công DoS, cải tiến thuật toán để làm cho tốc độ tính toán nhanh hơn, không những mở rộng thêm nhiều các mẫu bất thường trong tấn công từ chối dịch vụ mà còn cả các mẫu của các kiểu tấn công khác. Thực nghiệm đánh giá rút ra kết luận thuật toán tối ưu cho từng loại tấn công DoS (back dos, u2r, r2l,...) Phát triển công cụ giám sát, cảnh báo các cuộc tấn công DDoS, DRDos. Xây dựng hệ thống xử lý song song để tăng tốc độ thực hiện đồng thời sẽ đưa ra những phản ứng nhanh cho các hành vi vi phạm. Có thể đưa vào tích hợp vào một hệ thống phát hiện lạm dụng truyền thống. TÀI LIỆU THAM KHẢO [1] PGS.TS Đỗ Phúc (2006), Giáo trình Khai thác Dữ liệu, Trường Đại học Công nghệ thông tin TP. Hồ Chí Minh, Đại học Quốc gia TP. Hồ Chí Minh. [2] Huỳnh Tuấn Anh, Bài giảng DATAWAREHOUSE AND DATA MINING, TRƯỜNG ĐẠI HỌC NHA TRANG (2008). [3] Ts.Nguyễn Đình Thúc. Trí tuệ nhân tạo - Mạng Nơron – Phương pháp và ứng dụng – NXB Giáo dục năm 2000 [4] PGS.TS Nguyễn Quang Hoan. Nhập môn trí tuệ nhân tạo. Học viện Công nghệ Bưu chính Viễn thông (2007) [5] Tuyển tập Báo cáo “Hội nghị Sinh viên Nghiên cứu Khoa học” lần thứ 6 .THUẬT GIẢI DI TRUYỀN VÀ ỨNG DỤNG. Đại học Đà Nẵng – 2008 [6] Ths. Phạm Nguyễn Anh Huy, Luận văn thạc sĩ tin học “Dùng một số thuật toán khai khoáng dữ liệu hỗ trợ truy xuất các địa chỉ Internet ở WebServer”. Trường Đại học Khoa học Tự nhiên - Đại học quốc gia TPHCM (2000). [7 ] PGS.TS Đỗ Phúc, Luận văn tiến sĩ toán học “Nghiên cứu và phát triển một số thuật giải, mô hình ứng dụng khai thác dữ liệu (DATA MINING)”. Trường Đại học Khoa học Tự nhiên - Đại học Quốc gia TPHCM (2002) [8] Nong Ye. The handbook of data mining. Arizona state University. LAWRENCE ERLBAUM ASSOCIATES(LEA), PUBLISHERS Mahwah, New Jersey London (2003). [9] Jiawei Han and Micheline Kamber, University of Illinois at Urbana-Champaign. Data Mining Concepts and Techniques 2nd. Morgan kaufmann Publishers (2006). [10] ZhaoHui Tang and Jamie MacLennan. Data Mining with SQL Server 2005. Wiley Publishing, Inc., Indianapolis, Indiana (2005). [11] D. Barbara, J. Cou to, S. Jajodia, và N.Wu. “Special sectionon data mining for intrusion detection and threat analysis: Adam: a testbed for exploring the use of data mining in intrusion detection”. ACM SIGMOD Record, vol. 30, page 15-42, Dec. 2001. [12] D. Barbara, N.Wu, và S. Jajodia. “Detection novel network intrusions using bayes estimators” Proceedings of the First SIAM International Conference on Data Mining (SDM 2001), Chicago, USA, Apr, 2001. [13] Ken. Toshida. “Entropy based intrusion detection”. Proceedings of IEEE Pacific Rim Conference on Communications, Computers and signal Processing (PACRIM2003), vol. 2, trang 840-843. IEEE, Aug. 2003. IEEE Explore. [14] S. B. Cho, “Incorporating soft computing techiniquesinto a probabilistic intrusion detection system”. IEEE Transactions on Systems, Man, and Cyberneticspart C: applications and reviews, vol. 32, trang 154-160, May 2002. [15] S. S. Ahmedur Rahman, Survey report association and classification rule mining for network intrusion detection, Schook of computer science University of Windsor (2006) [16] Wenke Lee, “A data mining framework for constructing feature and models for instrusion detection systems”, Columbia University (1999)