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

đa chiều, khoảng cách ngắn nhất, K-láng giềng gần nhất, phân cụm, kỹ thuật hiển thị dữ liệu, mạng Neural và thuật toán di truyền. Chương sau sẽ trình bày về ứng dụng của kỹ thuật khai phá dữ liệu trong hệ thống IDS/IPS. Chương 3 ỨNG DỤNG KỸ THUẬT KHAI PHÁ DỮ LIỆU TRONG HỆ THỐNG IDS 3.1 Hệ thống IDS 3.1.1 Giới thiệu Ngày nay, sự phát triển liên tục của công nghệ máy tính là không thể phủ nhận. Có rất nhiều công ty thiết lập các cổng giao dịch Internet và các khách hàng ngày càng quan tâm hơn đến việc mua bán trên mạng, các thông tin thu thập được phát triển nhanh chóng. Mạng Internet đã trở thành một công cụ thông dụng cho việc giao tiếp. Cùng với sự phát triển của công nghệ thì chúng ta lại phải đối mặt với sự cần thiết phải tăng cường công tác an ninh. Tính gần gũi, mở rộng và sự phức tạp của Internet làm cho sự cần thiết của an ninh hệ thống thông tin càng trở nên cấp thiết hơn bao giờ hết. Việc kết nối hệ thống mạng thông tin vào các hệ thống mạng như Internet và các hệ thống điện thoại công cộng làm tăng thêm khả năng tiềm ẩn rủi ro đối với hệ thống. Đồ án này có tham vọng khám phá và kiểm tra các vấn đề có thể có đối với một Hệ thống phát hiện xâm nhập (IDS), một phần rất quan trọng của an ninh máy tính nói riêng và an ninh mạng nói chung. Một IDS tự bản thân nó không thể ngăn cản các security brake, nhưng nó phát hiện các mối hiểm họa bằng cách kiểm soát các hoạt động không mong muốn. Mục tiêu của đồ án này, kết hợp với kinh nghiệm thực tế và các tham khảo trên mạng, là nhằm xây dựng một hệ thống IDS có khả năng “học” các hành vi tấn công và có thể xác định được các cuộc tấn công mới mà không cần phải cập nhật lại hệ thống. Điều này là khả quan. Một hệ thống uyển chuyển như vậy sẽ không cần thiết phải có một cơ sở dữ liệu cập nhật thủ công của các dấu hiệu tấn công, bên cạnh đó nó còn có thể xác định các cuộc tấn công mới dựa trên các mẫu học và không bị phụ thuộc vào các luật lọc của hãng thứ ba. 3.1.2 Hệ thống phát hiện xâm nhập - IDS 3.1.2.1 IDS là gì? Khi bạn đặt một đồng hồ báo động trên những cánh cửa và trên những cửa sổ trong nhà của bạn, giống như việc bạn đang cài đặt một hệ thống phát hiện xâm nhập (IDS) trong nhà bạn vậy. Hệ thống phát hiện xâm nhập được dùng để bảo vệ mạng máy tính của bạn điều hành trong một kiểu đơn giản. Một IDS là một phần mềm và phần cứng một cách hợp lí để mà nhận ra những mối nguy hại có thể tấn công chống lại mạng của bạn. Chúng phát hiện những hoạt động xâm phạm mà xâm nhập vào mạng của bạn. Bạn có thể xác định những hoạt động xâm nhập bằng việc kiểm tra sự đi lại của mạng, những host log, những system call, và những khu vực khác mà phát ra những dấu hiệu chống lại mạng của bạn. Bên cạnh việc phát hiện những cuộc tấn công, hầu hết hệ thống phát hiện xâm nhập cũng cung cấp vài loại cách đối phó lại những tấn công, như việc thiết lập những kết nối TCP. 3.1.2.2 Vai trò, chức năng của IDS * Phát hiện các nguy cơ tấn công và truy nhập trái phép - Đây là vai trò chính của một hệ thống phát hiện xâm nhập IDS, nó có nhiệm vụ xác định những tấn công và truy nhập trái phép vào hệ thống mạng bên trong. - Hệ thống IDS có khả năng hỗ trợ phát hiện các nguy cơ an ninh đe dọa mạng mà các hệ thống khác (như bức tường lửa) không có, kết hợp với hệ thống ngăn chặn xâm nhập IPS giúp cho hệ thống chặn đứng, hạn chế các cuộc tấn công, xâm nhập từ bên ngoài. * Tăng khả năng hiểu biết về những gì đang hoạt động trên mạng IDS cung cấp khả năng giám sát xâm nhập và khả năng mô tả an ninh để cung cấp kiến thức tổng hợp về những gì đang chạy trên mạng từ góc độ ứng dụng cũng như góc độ mạng cùng với khả năng liên kết với phân tích, điều tra an ninh nhằm đưa ra các thông tin về hệ thống nhờ đó giúp người quản trị nắm bắt và hiểu rõ những gì đang diễn ra trên mạng. * Khả năng cảnh báo và hỗ trợ ngăn chặn tấn công - IDS có thể hoạt động trong các chế độ làm việc của một thiết bị giám sát thụ động (sniffer mode) hỗ trợ cho các thiết bị giám sát chủ động hay như là một thiết bị ngăn chặn chủ động (khả năng loại bỏ lưu lượng khả nghi). - IDS hỗ trợ cho các hệ thống an ninh đưa ra các quyết định về lưu lượng dựa trên địa chỉ IP hoặc cổng cũng như đặc tính của tấn công. - Ví dụ: Như mẫu tấn công hoặc bất thường về giao thức hoặc lưu lượng tương tác đến từ những máy chủ không hợp lệ. - IDS còn có thể cảnh báo và ghi lại các biến cố cũng như thực hiện bắt giữ gói lưu lượng khi phát hiện tấn công để cung cấp cho nhà quản trị mạng các thông tin để phân tích và điều tra các biến cố. - Ngay sau khi các phép phân tích và điều tra được thực hiện, một quy tắc loại bỏ lưu lượng sẽ được đưa ra dựa trên kết quả phân tích, điều tra đó. - Tổ hợp của những thuộc tính và khả năng này cung cấp cho nhà quản trị mạng khả năng tích hợp IDS vào mạng và tăng cường an ninh đến một mức độ mà trước đây không thể đạt đến bằng các biện pháp đơn lẻ như bức tường lửa. 3.1.2.3 Mô hình hệ thống IDS mức vật lý * Hệ thống phát hiện xâm nhập mức vật lý bao gồm ba thành phần chính sau đây: - Bộ cảm ứng (Sensor): giám sát các lưu lượng bên trong các khu vực mạng khác nhau, nhằm thu thập các thông tin, dữ liệu và hoạt động trong mạng. - Máy chủ lưu trữ dữ liệu tập trung ( Centralize database server): nơi tập trung lưu trữ thông tin, dữ liệu do các bộ cảm ứng gửi về. - Giao diện người dùng ( User Interface): giúp người quản trị mạng quản lý, giám sát hệ thống. 3.1.2.4 Cấu trúc và hoạt động bên trong của hệ thống IDS: Hệ thống phát hiện xâm nhập bao gồm 3 modul chính: - Modul thu thập thông tin, dữ liệu - Modul phân tích, phát hiện tấn công - Modul phản ứng * Modul thu thập thông tin, dữ liệu: - Modul này có nhiệm vụ thu thập các gói tin trên mạng để đem phân tích. - Vấn đề đặt ra trong thực tế là chúng ta cần triển khai hệ thống phát hiện xâm nhập IDS ở vị trí nào trong mô hình mạng của chúng ta. Thông thường chúng ta sẽ đặt IDS ở những nơi mà chúng ta cần giám sát. - Có hai mô hình chính để thu thập dữ liệu đó là : + Mô hình ngoài luồng. + Mô hình trong luồng. Mô hình thu thập dữ liệu ngoài luồng - Trong mô hình ngoài luồng không can thiệp trực tiếp vào luồng dữ liệu. Luồng dữ liệu vào ra hệ thống mạng sẽ được sao một bản và được chuyển tới modul thu thập dữ liệu . - Theo cách tiếp cận này hệ thống phát hiện xâm nhập IDS không làm ảnh hưởng tới tốc độ lưu thông của mạng. Mô hình thu thập dữ liệu trong luồng - Trong mô hình này, hệ thống phát hiện xâm nhập IDS được đặt trực tiếp vào luồng dữ liệu vào ra trong hệ thống mạng, luồng dữ liệu phải đi qua hệ thống phát hiện xâm nhập IDS trước khi đi vào trong mạng. - Ưu điểm của mô hình này, hệ thống phát hiện xâm nhập IDS trực tiếp kiểm soát luồng dữ liệu và phản ứng tức thời với các sự kiện an toàn... tuy nhiên nó có nhược điểm là ảnh hưởng đáng kể đến tốc độ lưu thông của mạng. * Module phân tích, phát hiện tấn công Đây là modul quan trọng nhất nó có nhiệm vụ phát hiện các tấn công. Modul này được chia thành các giai đoạn: Tiền xử lý, phân tích, cảnh báo. Tiền xử lý: Tập hợp dữ liệu, tái định dạng gói tin. Dữ liệu được sắp xếp theo từng phân loại, phân lớp. Xác định định dạng của của dữ liệu đưa vào (chúng sẽ được chia nhỏ theo từng phân loại). Ngoài ra, nó có thể tái định dạng gói tin (defragment), sắp xếp theo chuỗi. Phân tích: - Phát hiện sự lạm dụng (Misuse detection models): dựa trên mẫu, ưu điểm chính xác. + Phân tích các hoạt động của hệ thống, tìm kiếm các sự kiện giống với các mẫu tấn công đã biết trước. + Ưu điểm: phát hiện các cuộc tấn công nhanh và chính xác, không đưa ra các cảnh báo sai làm giảm khả nǎng hoạt động của mạng và giúp các người quản trị xác định các lỗ hổng bảo mật trong hệ thống của mình. + Nhược điểm: là không phát hiện được các cuộc tấn công không có trong cơ sở dữ liệu, các kiểu tấn công mới, do vậy hệ thống luôn phải cập nhật các mẫu tấn công mới. - Phát hiện tình trạng bất thường (Anomaly detection models): dựa trên sự bất thường: Ban đầu chúng lưu giữ những mô tả sơ lược về các hoạt đọng bình thường, các cuộc tấn công xâm nhập gây ra các hoạt động bất bình thường và kỹ thuật này phát hiện ra các hoạt động bất bình thường đó. + Ban đầu, chúng lưu giữ các mô tả sơ lược về các hoạt động bình thường của hệ thống. + Các cuộc tấn công xâm nhập gây ra các hoạt động bất bình thường và kỹ thuật này phát hiện ra các hoạt động bất bình thường đó. Phát hiện dựa trên mức ngưỡng Phát hiện nhờ quá trình tự học Phát hiện dựa trên những bất thường về giao thức + Ưu điểm: có thể phát hiện ra các kiểu tấn công mới, cung cấp các thông tin hữu ích bổ sung cho phương pháp dò sự lạm dụng. + Nhược điểm: thường tạo ra một số lượng các cảnh báo sai làm giảm hiệu suất hoạt động của mạng. Cảnh báo: Quá trình này thực hiện sinh ra các cảnh báo tùy theo đặc điểm và loại tấn công, xâm nhập mà hệ thống phát hiện được. * Modul phản ứng: - Đây là một điểm khác biệt giữa hệ thống phát hiện xâm nhập IDS và một hệ thống ngăn chặn xâm nhập IPS. - Đối với hệ thống IDS, chúng thường chỉ có khả năng ngăn chặn rất hạn chế bởi vì chúng dựa trên cơ chế phản ứng thụ động (passive response). - Cơ chế phản ứng thụ động không thể ngăn chặn được tổn thất vì nó chỉ được đưa ra sau khi tấn công đã ảnh hưởng tới hệ thống. - Khi có dấu hiệu của sự tấn công hoặc thâm nhập, modul phát hiện tấn công sẽ gửi tín hiệu báo hiệu có sự tấn công hoặc thâm nhập đến modul phản ứng. - Lúc đó modul phản ứng gửi tín hiệu kích hoạt tường lửa thực hiện chức nǎng ngǎn chặn cuộc tấn công hay cảnh báo tới người quản trị. - Tại modul này, nếu chỉ đưa ra các cảnh báo tới các người quản trị và dừng lại ở đó thì hệ thống này được gọi là hệ thống phòng thủ bị động. Modul phản ứng này tùy theo hệ thống mà có các chức nǎng và phương pháp ngǎn chặn khác nhau. 3.1.2.5 Phân loại IDS được chia làm hai loại chính: • HIDS (Host Intrusion Detection System): triển khai trên máy trạm hoặc server quan trọng, chỉ để bảo vệ riêng từng máy. • NIDS (Network Intrusion Detection System): đặt tại những điểm quan trọng của hệ thống mạng, để phát hiện xâm nhập cho khu vực đó * So sánh giữa hệ thống HIDS và NIDS: NIDS HIDS Áp dụng trong phạm vi rộng (theo dõi toàn bộ hoạt động của mạng) Áp dụng trong phạm vi một Host Phát hiện tốt những tấn công, xâm nhập từ bên ngoài Phát hiện tốt những tấn công, xâm nhập từ bên trong. Phát hiện dựa trên các dữ liệu, thông tin thu thập trong toàn bộ mạng Phát hiện dựa trên thông tin, dữ liệu trên Host Độc lập với hệ điều hành Phụ thuộc vào hệ điều hành trên Host đó Tiết kiệm kinh phí khi triển khai Yêu cầu chi phí cao Dễ dàng cài đặt, triển khai Phức tạp khi cài đặt, triển khai 3.2 Khai phá dữ liệu trong IDS 3.2.1 NIDS dựa trên khai phá dữ liệu Tất cả các hệ thống phát hiện xâm nhập đều dựa trên cơ sở chính là phân tích thống kê hay khai phá dữ liệu. Ở phương pháp này chúng ta có một kho các mẫu hành vi bình thường hay các hành vi vô hại của người dung. Bất kỳ một sự kiện mới nào diễn ra với hệ thống cũng được so sánh với những hồ sơ bình thường này và hệ thống xác định độ lệch của các sự kiện này với những mẫu bình thường. Sau đó nó xác định xem liệu sự kienj này có thể được gán cờ như một hành động xâm nhập hay không. Ở đây có hai kịch bản có thể xảy ra: 1) các hành vi bất thường (hành vi bình thường nhưng được xem như là đáng nghi) không phải là một hành động xâm nhập được gán cờ như một hành động xâm nhập. Điều này sẽ cho kết quả chắc chắn sai. 2) Các hành vi xâm nhập trái phép không được gán nhãn xâm nhập sẽ cho kết quả chắc chắn sai, điều này sẽ gây ra tình trạng nguy hiểm hơn. Trong hệ thống phát hiện xâm nhập dự trên khai phá dữ liệu, chúng ta cần một cơ sở dữ liệu, tốt nhất là một cơ sở dữ liệu lớn vì khai phá dữ liệu là vô hướng với cơ sở dữ liệu, cái mà sẽ chứa tất cả các hành vi hay các dấu hiệu vô hại. Sau đó kỹ thuật khai phá dữ liệu có thể được áp dụng trên cơ sở dữ liệu này để xác định các mối tương quan và liên kết trong dữ liệu để tìm kiếm một luật mới. 3.2.1.1. Source of Audit Data: Nguồn dữ liệu kiểm toán chính là các sensor của mạng. Một sensor mạng có thể là internal hay external. Các Internal sensor chủi yếu được sử dụng để xác định các tấn công tới một host xác định. Các External sensor thường dung để giám sát bất kỳ một host nào đó trên mạng. Những sensor này giám sát lưu thông mạng và ghi lại các dữ liệu đó. Các bản ghi dữ liệu chứa nhiều thuộc tính. Khi thực hiện khai phá dữ liệu cho việc phát hiện xâm nhập có thể sử dụng dữ liệu ở mức độ của TCPDUMP hay cấp độ cảnh báo. Ở cả hai kiểu dữ liệu này chúng ta sẽ tìm thấy những trường về địa chỉ IP nguồn, địa chỉ IP đích, cổng nguồn, cổng đích, giao thức (TCP, UDP ...), thời gian xảy ra và thời gian sống của giao tác. Các thuộc tính nền tảng này cho ta một cái nhìn tốt về các kết nối hoặc các cảnh báo riêng lẻ. Ví dụ, các sensor là một loại phần mềm được cài đặt trên máy trạm hay trên máy cổng kết nối mạng. Nó quét các cổng, tính băng thông của kết nối và nếu có một sự chênh lệch lứn thì nó sẽ nhận dạng như là một tấn công và kết quả là nó sẽ chặn truy cập tới một cổng xác định hay có thể chuyển tiếp vấn đề tới thành phần quản trị hệ thống . Một ví dụ về loại phần mềm này là BSM (Basic Security Module), nó như một phần trong hệ điều hành UNIX Solaris. Một loại phần mềm tương tự cũng có khả năng sử dụng với hệ điều hành Windows, được gọi là BAM (Basic Auditing Module), được phát triển bởi trường Đại học Columbia. Một ví dụ khác về một hệ thống sensor là Network Flight Recorder (NFR), một hệ thống giám sát mạng thương mại mà gồm cả một bộ máy sniffing các gói trong mạng với một ngôn ngữ cấp cao để phiên dịch gói dữ liệu mạng. Bây gời chúng ta đi vào xem dữ liệu kiểm toán này trong như thế nào. Khi một sensor mạng thu thập dữ liệu của một kết nối, nó sẽ lấy dữ liệu ở dạng không chuẩn. Giả sử rằng một sensor phát hiện rằng một kết nối được thiết lập hay một ai đó đang truy cập mạng thông qua một cổng, nó sẽ lấy các dữ liệu về địa chỉ IP đích, địa chỉ IP nguồn, cổng đích, cổng nguồn, giao thức (TCP, UDP etc.), thời gian thực hiện và khoảng thời gian sống của giao dịch… Tất cả các dữ liệu này vẫn giữ nguyên trong cùng một nơi với nhau chẳng hạn như ở dạng mà con người có thể sẽ không hiểu được dữ liệu bằng cách xem chúng. Chúng ở dạng nhị phân và chúng là các dữ liệu header TCP/IP. Hình sau chỉ cho thấy định dạng header TCP/IP và hình tiếp theo sẽ cho thấy kết quả dữ liệu thu được từ một TCP DUMP. Do đó các phần mềm như BSM, BAM, NFR tổ chức chúng và chỉ cho ta thấy ở dạng mà chúng ta có thể hiểu được và có thể xem các trường thuộc tính như IP nguồn, IP đích, cổng nguồn, cổng đích, thời gian sống…Trước khi tổ chức chúng ta gọi là dữ liệu kiểm toán thô. Figure 1: TCP Header Format/ Format of raw audit binary data Hình 2: Mẫu dữ liệu TCP DUMP 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 Các dữ liệu kiểm toán được thu thập từ các sensor mạng hoặc từ một nguồn nào đó ở dạng thô và ở định dạng nhị phân. Trước khi sử dụng chúng chúng ta cần xử lý chúng và cần lấy được các luật từ chúng. Nội dung hang đầu và cơ bản ở đây là chúng ta phải xây dựng một cơ sở dữ liệu từ dữ liệu kiểm toán và có một số hiểu biết ban đầu về các luật. Với sự trợ giúp của hai điều này và với thuật toán luật kết hợp chúng ta sẽ có được các tập luật mới về ác tấn công có thể. Sau đó chúng ta có thể ứng dụng những luật này cho các sự kiện sắp xảy ra để phát hiện các tấn công mới chưa được biết. Trước khi ứng dụng một luật khai phá dữ liệu nào chúng ta cần tiền xử lý dữ liệu kiểm toán thô dạng nhị phân thu được từ các sensor. Việc này được thực hiện bởi TCPDUMP hay BSM. Để tiền xử lý những dữ liệu kiểm toán thô này nhóm làm việc ở trường Đại học Columbia đã sử dụng BAM (Basic Auditing Model) thay vì BSM (Basic Security Model), cái mà được chính họ tạo ra. Tiền xử lý có nghĩa là đầu vào là các dữ liệu kiểm toán thôi và đầu ra sẽ là những dữ liệu kiểm toán đó nhưng ở dạng được tổ chức với các thuộc tính như IP nguồn, IP đích, cổng nguồn, cổng đích, giao thức (TCP, UDP ...), thời gian và khoảng thời gian tồn tại. Bước tiếp theo là áp dụng một số thuật toán khai phá dữ liệu để tiền xử lý dữ liệu. Những thuật toán này như là thuật toán luật phân nhóm chung, luật phân nhóm, luật kêt hợp và thuật toán frequent episodes. Một vài nghiên cứu đã tập trung vào một luật cụ thể, một số tập trung vào một kết hợp của hai hay ba luật hay một số tập trung vào một vài luật được cải tiến như là luật tạo ra các bất thường nhân tạo. Qua một số phần đã được trình bày, chúng ta sẽ có cái nhìn tổng quát về một số các luật này (luật phân nhóm và luật kết hợp). 3.2.1.3 Các phương thức khai phá dữ liệu trong NIDS 1. Luật phân lớp: Phát hiện xâm nhập có thể được xem như là một vấn đề phân nhóm: ta phải chia mỗi bản ghi của dữ liệu kiểm toán vào một tập rời rạc các hạng mục có thể, bình thường hay một kiểu xâm nhập cụ thể. Căn cứ vào tập các bản ghi, cái mà có một thuộc tính là lớp nhãn, thuật toán phân lớp có thể tính một mô hình mà sử dụng các giá trị thuộc tính đúng đắn nhất để biểu diễn cho mỗi khái niệm. Ví dụ, xét các bản ghi kết nối sử dụng giao thức telnet ở hình dưới. Ở đây, hot là đếm số truy cập vào thư mục hệ thống, tạo và thực hiện các chương trình… compromise là thuộc tính đến số lỗi “không tìm thấy” file hay đường dẫn, và “Jump to” các xâm nhập… RIPPER (một thuật toán học máy dựa trên luật chuẩn được phát triển tại trung tâm nghiên cứu ATT) một chương trình học luật phân nhóm, các luật tạo ra cho việc phân nhóm các kết nối telnet và một số các luật được hiển thị trong bảng sau Figure 3: Telnet Records ([LS00] page: 232) Figure 4: Example RIPPER Rules from Telnet Records ([LS00] page: 233) Ở đây, chúng ta thấy rằng quả thật RIPPER chọn các giá trị thuộc tính duy nhất để xác định các xâm nhập. Những luật này trước tiên có thể được xem xét kỹ và chỉnh sửa bởi các chuyên gia an toàn, sau đó là được kết hợp vào trong hệ thống phát hiện sự lạm dụng. Sự chính xác của một môt hình phân nhóm phụ thuộc trực tiếp vào tập các thuộc tính được cung cấp trong quá trình huấn luyện dữ liệu. Ví dụ nếu các thuộc tính hot, compromised and root shell được chuyển dịch từ các bản ghi trong bảng trên, RIPPER sẽ có thể thực hiện các luật chính xác để nhận dạng các kết nối tràn bộ đệm. Vì thế, việc lựa chọn đúng tập các thuộc tính hệ thống là một bước quan trọng khi thực hiện việc phân nhóm. 2. Luật kết hợp: Một luật kết hợp chủ yếu là luật toán học được tìm thấy hữu ích trong hệ thống phát hiện xâm nhập dựa trên khai phá dữ liệu. Mỗi và mọi mô hình được phát triển tới một mức độ nào đó trong ngữ cảnh này có mối liên hệ theo cách này hay cách khác với một luật kết hợp. Trong cơ sở dữ liệu, mối liên kết giữa các thành phần dữ liệu có nghĩa là chúng ta suy ra rằng phần tử dữ liệu cụ thể tồn tại bởi vì sự xuất hiện của một số các phần tử dữ liệu trong một giao tác. Mục đích của việc khai phá các luật kết hợp là để tìm ra tất cả các luật kết hợp tiềm ẩn giữa các phần tử dữ liệu. Nói chung, trong hệ thống phát hiện xâm nhập dựa trên khai phá dữ liệu chúng ta tạo một cơ sở dữ liệu của các sự kiện không có sự xâm nhập và sau đó áp dụng kỹ thuật luật kết hợp vào trong tập dữ liệu đó để tìm ra tất cả các luật khác hoặc các sự kiện sẽ không có sự xâm nhập. Điều này sẽ giúp tìm ra tất cả các hành vi bình thường tiềm ẩn. Sau đó những luật này sẽ được so sánh với bất kỳ một tập phần tử dữ liệu đi vào để xác định liệu đó có phải là một sự xâm nhập hay không. Nhân tố then chốt nhất ở đây là chúng ta phải thiết lập ngưỡng tối thiểu cho mức độ hỗ trợ và tin cậy tối thiểu 3. Láng giềng gần nhất K-NN xác định liệu hoặc là không một điểm nằm trong một khu vực thưa thớt của các thuộc tính bằng cách tính tổng của các khoảng cách đến những K-láng giềng gần nhất của điểm đó, được gọi tắt là K-NN. Bằng trực giác các điểm trong khu vực dày đặc sẽ có nhiều điểm gầnchúng và sẽ có một điểm nhỏ KNN. Nếu kích cỡ của K vượt quá mức độ thường xuyên của bất cứ loại tấn công trong tập dữ liệu và hình ảnh của các yếu tố tấn công là khác xa các yếu tố dữ liệu thì ngay sau đó phương thức làm việc. Thuật toán được mô tả như sau: for each data instance i do for each data instance j do find D(i, j)=distance between j and i end Keep the top k-D(i,.) and sum them to get K − NNi if k − NNi > threshold Intrusion occurred end Các vấn đề chính với các thuật toán này là nó có độ phức tạp tính toán O(N2) thời gian. Chúng ta có thể tăng tốc độ xử lý bằng cách sử dụng một kỹ thuật tương tự với phân cụm CANOPY. Phân cụm CANOPY được sử dụng như một phương tiện để chia không gian thành các không gian con nhỏ hơn để loại bỏ sự cần thiết phải kiểm tra tất cả các điểm dữ liệu. Chúng ta sử dụng các cụm như là một công cụ để làm giảm thời gian tìm kiếm k-láng giềng gang nhất. Trước tiên chúng ta phân cụm dữ liệu bằng cách sử dụng thuật toán phân cụm có chiều rộng cố định của phần trước với một biến mà chúng ta đặt mỗi phần tử váo chỉ có một nhóm. Sau khi dữ liệu được phân cụm chiều rộng w, chúng ta có thể tính các k-láng giềng gần nhất cho một điểm x bằng cách tận dụng các ưu điểm của các thuộc tính. Chúng ta biểu diễn c(x) như là điểm trung tâm của nhóm có chứa một điểm x. Đối với một nhóm c và một điểm x chúng ta sử dụng các ký hiệu d(x; c) để biểu diễn khoảng cách giữa điểm và điểm trung tâm cụm. Đối với bất kỳ hai điểm x1 và x2 , nếu các điểm nằm trong cùng một cụm dφ (x1 , x2 ) ≤ 2w và trong tất cả các trường hợp dφ(x1 , x2 ) ≤ dφ(x1 , c(x2 )) + w dφ(x1 , x2 ) ≥ dφ(x1 , c(x2 )) − w Cho C là một tập hợp các cụm. Ban đầu C có chứa tất cả các cụm trong các dữ liệu. Tại bất cứ bước nào trong thuật toán, chúng ta có một tập hợp các điểm có khả năng là một trong những điểm k-láng giềng gần nhất. Chúng ta biểu diễn tập này là P. Chúng ta cũng có một tập các điểm trong thực tế, là một trong các điểm k-láng giềng gần nhất. Chúng ta biểu diễn bằng tập K. Ban đầu K và P là rỗng. Chúng ta tính khoảng cách từ x đến từng cụm. Đối với các cụm với các trung tâm gần với x nhất, chúng ta xoá bỏ nó từ C và thêm vào tất cả các điểm của nó vào P. Chúng ta tham khảo hoạt động này như là "mở rộng" nhóm. Chìa khóa của các thuật toán này là chúng ta có thể có được một ràng buộc thấp hơn khoảng cách từ tất cả các điểm trong các cụm của tập C bằng cách sử dụng công thức trên: Các thuật toán thực hiện sau đây. Đối với mỗi điểm xi P, chúng ta tính d(x;xi). Nếu d(x; xi) <dmin , chúng ta có thể đảm bảo rằng xi là điểm gần x hơn sau đó tất cả các điểm trong các cụm của C. Trong trường hợp này, chúng ta loại bỏ xi khỏi P và thêm nó vào K. Nếu chúng ta không thể đảm bảo việc này cho bất kỳ phần tẻ của P (bao gồm cả các trường hợp mà nếu P là trống rỗng), sau đó chúng ta "mở" cụm gần nhất bằng cách thêm tất cả các điểm vào P, và bỏ cụm đó khỏi C. Chú ý rằng khi chúng ta loại bỏ các cụm khỏi C, dmin sẽ tăng. Sau khi K có k phần tử, chúng ta kết thúc. Hầu hết các tính toán được chi phí kiểm tra khoảng cách giữa các điểm trong D tới trung tâm của cụm. Điều này có hiệu quả đáng kể hơn việc tính khoảng cách giữa các cặp điểm của tất cả các điểm. Sự lựa chọn của chiều rộng w hiện không ảnh hưởng đến kết quả k-NN, nhưng thay vì chỉ ảnh hưởng đến các kết quả tính toán. Bằng trực giác, chúng ta muốn chọn một w cái mà chia dữ liệu vào các cụm có kích thước hợp lý. 4. Phân cụm Mặc dù đã được đề cập đến, nhưng phân cụm huấn luyện trung tâm phát hiện bất thường không giám sát. Điều này là bởi vì phân cụm tìm kiếm các bất thường theo mặc định và không có yêu cầu làm việc cao được thực hiện. Chúng ta sẽ xem xét một trong những phương pháp tiếp cận. Mục tiêu đầu tiên của các thuật toán của chúng ta là tính có bao nhiêu điểm là "gần" với từng điểm trong không gian thuộc tính. Một tham số cho các thuật toán là một bán kính w còn gọi tắt là chiều rộng cụm. Đối với bất kỳ một cặp điểm x1 và x2 , chúng ta xem xét hai điểm "gần" nhau, nếu khoảng cách giữa chúng là nhỏ hơn hoặc bằng w, d (x1 , x2 ) <w với khoảng cách được xác định trong phạm vi hàm hạt nhân. Đối với mỗi điểm x, chúng ta xác định N (x) là số điểm mà nằm trong vòng w của điểm x. Một cách hình thức hơn ta xác định như sau: (1) Những tính toán đơn giản của N(x) cho tất cả các điểm có một phức tạp tính toán O(N2) trong đó N là số điểm. Lý do là chúng ta phải tính đến những khoảng cách giữa các cặp tất cả các điểm. Tuy nhiên, bởi vì chúng ta là chỉ quan tâm đến việc xác định các outliers là gì, chúng ta có thể tính toán gần đúng một cách có hiệu quả như sau. Trước tiên chúng ta thực hiện phân cụm chiều rộng cố định trên toàn bộ dữ liệu với cụm có chiều rộng w. Sau đó, chúng ta gán nhãn các điểm vào trong các cụm nhỏ như các bất thường. Một thuật toán phân cụm chiều rộng cố định được mô tả như sau. Điểm đầu tiên là trung tâm đầu tiên của nhóm. Đối với tất cả các điểm tiếp theo, nếu nó cách điểm trung tâm của cụm không quá w, nó sẽ được thêm vào cụm đó. Nếu không nó là một trung tâm của một nhóm mới. Lưu ý rằng một số điểm có thể được thêm vào nhiều cụm. Thuật toán phân cụm chiều rộng cố định đòi hỏi chỉ có một trải qua tập dữ liệu (only one pass through the data). Độ phức tạp c