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

Khai phá dữ liệu được định nghĩa là quá trình trích xuất các thông tin có giá trị tiềm ẩn bên trong lượng lớn dữ liệu được lưu trữ trong các cơ sở dữ liệu, kho dữ liệu. Cụ thể hơn đó là tiến trình trích lọc, sản sinh những tri thức hoặc những mẫu tiềm ẩn, chưa biết nhưng hữu ích từ các cơ sở dữ liệu lớn. Đồng thời là tiến trình khái quát các sự kiện rời rạc trong dữ liệu thành các tri thức mang tính khái quát, tính qui luật hỗ trợ tích cực cho các tiến trình ra quyết định. Hiện nay, ngoài thuật ngữ khai phá dữ liệu, người ta còn dùng một số thuật ngữ khác có ý nghĩa tương tự như: Khai phá tri thức từ CSDL, trích lọc dữ liệu, phân tích dữ liệu/mẫu, khảo cổ dữ liệu (data archaeology), nạo vét dữ liệu (data dredredging). Nhiều người coi khai phá dữ liệu và một số thuật ngữ thông dụng khác là khám phá tri thức trong CSDL (Knowledge Discovery in Databases-KDD) là như nhau. Tuy nhiên trên thực tế khai phá dữ liệu chỉ là một bước thiết yếu trong quá trình Khám phá tri thức trong CSDL.

Để hình dung vấn đề này ta có thể sử dụng một ví dụ đơn giản như sau: Khai phá dữ liệu được ví như tìm một cây kim trong đống cỏ khô. Trong ví dụ này, cây kim là một mảnh nhỏ tri thức hoặc một thông tin có giá trị và đống cỏ khô là một kho cơ sở dữ liệu rộng lớn. Như vậy, những thông tin có giá trị tiềm ẩn trong kho cơ sở dữ liệu sẽ được chiết xuất ra và sử dụng một cách hữu ích nhờ khai phá dữ liệu. Chức năng khai phá dữ liệu gồm có gộp nhóm phân loại, dự báo, dự đoán và phân tích các liên kết.

Nguồn dữ liệu phục vụ cho KTDL có thể là các CSDL lớn hay các kho dữ liệu (Datawarehouse) có hay không có cấu trúc. Các tác vụ khai phá dữ liệu có thể được phân thành hai loại: miêu tả và dự báo

- Các tác vụ khai phá miêu tả mô tả các đặc tính chung của dữ liệu trong cơ sở dữ liệu. Kỹ thuật khai phá dữ liệu mô tả: Có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có. Các kỹ thuật này gồm có: phân cụm (clustering), tóm tắt (summerization), trực quan hoá (visualiztion), phân tích sự phát triển và độ lệch (Evolution and deviation analyst), phân tích luật kết hợp (association rules)

- Các tác vụ khai phá dự báo thực hiện việc suy luận trên dữ liệu hiện thời để đưa ra các dự báo. Kỹ thuật khai phá dữ liệu dự đoán: Có nhiệm vụ đưa ra các dự đoán dựa vào các suy diễn trên dữ liệu hiện thời. Các kỹ thuật này gồm có: Phân lớp (classification), hồi quy (regression)


MỤC LỤC

MỤC LỤC 1

DANH MỤC CÁC TỪ VIẾT TẮT 3

DANH MỤC CÁC BẢNG 4

DANH MỤC HÌNH VẼ 5

LỜI NÓI ĐẦU 6

Chương 1 7

TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 7

1.1 Giới thiệu về khai phá dữ liệu 7

1.2 Các nhiệm vụ của khai phá dữ liệu 8

1.3 Các loại dữ liệu được khai phá 9

1.4 Lịch sử phát triển của Khai phá dữ liệu 9

1.5 Ứng dụng của Khai phá dữ liệu 9

1.6 Phân loại 11

1.7 Một số thách thức đặt ra cho việc khai phá dữ liệu 11

Kết chương 11

Chương 2 12

QUY TRÌNH VÀ PHƯƠNG THỨC THỰC HIỆN KHAI PHÁ DỮ LIỆU 12

2.1 Quy trình tổng quát thực hiện Khai phá dữ liệu 12

2.2 Tiến trình khám phá tri thức khi đi vào một bài toán cụ thể 13

2.3 Tiền xử lý dữ liệu 14

2.3.1 Làm sạch dữ liệu 15

2.3.1.1 Các giá trị thiếu 15

2.3.1.2 Dữ liệu nhiễu 16

2.3.2 Tích hợp và chuyển đổi dữ liệu 17

2.3.2.1 Tích hợp dữ liệu 17

2.3.2.2 Biến đổi dữ liệu 19

2.3.3 Rút gọn dữ liệu (Data reduction) 20

2.3.3.1 Rút gọn dữ liệu dùng Histogram 21

2.3.3.2 Lấy mẫu (Sampling) 22

2.3.4 Rời rạc hóa dữ liệu và tạo lược đồ phân cấp khái niệm 24

2.3.4.1 Rời rạc hóa bằng cách phân chia trực quan dùng cho dữ liệu dạng số 25

2.3.4.2 Tạo hệ thống phân cấp khái niệm cho dữ liệu phân loại 26

2.3 Phương pháp khai phá dữ liệu 26

2.4 Một số kỹ thuật dùng trong Data Mining 28

2.4.1 Cây quyết định 28

2.4.1.1 Giới thiệu chung 28

2.4.1.2 Các kiểu cây quyết định 29

2.4.1.3 Ưu điểm của cây quyết định 31

2.4.2 Luật kết hợp 31

2.4.2.1 Phát biểu bài toán khai phá luật kết hợp 32

2.4.2.2 Các hướng tiếp cận khai phá luật kết hợp 34

2.4.3 Mô hình dữ liệu đa chiều 35

2.4.3.1 Định nghĩa: 35

2.4.3.2 Các thao tác trên các chiều của MDDM 36

2.4.4 Khoảng cách ngắn nhất 37

2.4.5 K-Láng giềng gần nhất 38

2.4.6 Phân cụm 39

2.4.7 Kỹ thuật hiển thị dữ liệu 40

2.4.8 Mạng Neural 41

2.4.8.1 Tổng quan 41

2.4.8.2 Mô hình mạng Nơron 42

2.4.9 Thuật toán di truyền 43

2.4.9.1 Giới thiệu chung 43

2.4.9.2 Các bước cơ bản của giải thuật di truyền 44

Kết chương 46

Chương 3 47

ỨNG DỤNG KỸ THUẬT KHAI PHÁ DỮ LIỆU TRONG HỆ THỐNG IDS 47

3.1 Hệ thống IDS 47

3.1.1 Giới thiệu 47

3.1.2 Hệ thống phát hiện xâm nhập - IDS 47

3.1.2.1 IDS là gì? 47

3.1.2.2 Vai trò, chức năng của IDS 48

3.1.2.3 Mô hình hệ thống IDS mức vật lý 49

3.1.2.4 Cấu trúc và hoạt động bên trong của hệ thống IDS: 49

3.1.2.5 Phân loại 53

3.2 Khai phá dữ liệu trong IDS 54

3.2.1 NIDS dựa trên khai phá dữ liệu 54

3.2.1.1. Source of Audit Data: 54

3.2.1.2 Xử lý dữ liệu kiểm toán thô và xây dựng các thuộc tính 56

3.2.1.3 Các phương thức khai phá dữ liệu trong NIDS 57

3.2.2 Tình hình trong nước 61

3.3.3 Tình hình thế giới 61

3.3.3.1 Nghiên cứu sớm nhất 61

3.3.3.2 Nghiên cứu muộn hơn 64

3.3.3.3 Nghiên cứu gần đây và hiện nay 68

Chương 4 79

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 79

4.1 Thuật toán phân cụm 79

4.1.1 Dẫn nhập 79

4.1.2 Các dạng dữ liệu trong phân tích cụm 79

4.2.2.1 Biến trị khoảng 80

4.2.2.2 Các biến nhị phân 82

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 83

4.2.3 Các phương pháp gom cụm 85

4.2.3.1 Các phương pháp phân hoạch 85

4.2.3.2 Các phương pháp phân cấp 86

4.2.4 Thuật toán gom cụm bằng phương pháp K-means 86

4.2.4.1 Thuật toán k-means 87

4.2.4.2 Kỹ thuật dùng đối tượng đại diện: Phương pháp k-medoids 90

4.2 Sơ đồ phân tích thiết kế chương trình (các mẫu) 91

4.2.1 Tập hợp dữ liệu và tiền xử lý 92

4.2.1.1 Tập hợp dữ liệu 92

4.2.1.2 Tiền xử lý 93

4.2.2 Khai phá dữ liệu phát hiện tấn công từ chối dịch vụ 94

4.2.2.1 Các mẫu bất thường của tấn công từ chối dịch vụ 94

4.2.2.2 Khai phá dữ liệu 96

4.2.3 Biểu diễn dữ liệu 97

Chương 5 99

KẾT QUẢ ĐẠT ĐƯỢC – ĐÁNH GIÁ, KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 99

5.1 Cài đặt 99

5.2 Kết quả đạt được 99

5.3 Kết luận 104

5.4 Hướng phát triển 105

TÀI LIỆU THAM KHẢO 106