Áp dụng hệ miễn dịch nhân tạo trong phân cụm cơ sở dữ liệu
KDD CUP 99
Luận văn tốt nghiệp 2013.
MỤC LỤC
Trang
1
1
DANH SÁCH KÍ HIỆU, TỪ VIẾT TẮT
Viết tắt Viết đầy đủ
HMD Hệ miễn dịch
KDD Knowledge Discovery and Data Mining
DoS Denial of Services
R2L Remote to Local
U2R User to Root
DANH MỤC HÌNH
Trang
2
2
3
3
MỞ ĐẦU
I. Lí do chọn đề tài
Cùng với sự phát triển của ngành công nghệ thông tin là nhiều thách thức đặt
ra trong vấn đề bảo vệ hệ thống máy tính khỏi sự xâm nhập của các đoạn mã độc
hại. Có nhiều kỹ thuật khác nhau được sử dụng cho mục đích bảo vệ sự an toàn của
hệ thống máy tính như tường lửa, phần mềm chống virus và các hệ thống phát hiện
xâm nhập. Ta có thể áp dụng hệ miễn dịch (HMD) nhân tạo để làm tăng khả năng
phát hiện và loại bỏ những đoạn mã độc hại trong máy tính
Việc áp dụng HMD nhân tạo vào bảo mật, an ninh mạng mang lại hiệu quả
tối ưu hơn so với việc bảo mật bằng các phương pháp truyền thống trước đây. Khi
có xâm nhập mạng, HMD nhân tạo sẽ tự động phân tích những hoạt động lạ không
Anh về lĩnh vực nghiên cứu.
− Tham khảo ý kiến chuyên gia: Tham khảo ý kiến từ các thầy cô trong
trường, các chuyên gia về bảo mật mạng cũng như những chuyên gia nghiên
cứu lý thuyết về hệ miễn dịch nhân tạo.
− Thực nghiệm: cài đặt các thuật toán và đánh giá chương trình trên một
số tệp dữ liệu KDD.
V. Cấu trúc của đề tài
Mở đầu
Chương 1: Trình bày tổng quan về miễn dịch sinh học và hệ miễn dịch nhân
tạo.
Chương 2: Tìm hiểu về cơ sở dữ liệu KDD CUP 99
Chương 3: Rời rạc hóa dữ liệu và cài đặt chương trình, thực nghiệm với bộ
dữ liệu KDD cụ thể
Kết luận
Tài liệu tham khảo
5
5
Chương 1
HỆ MIỄN DỊCH NHÂN TẠO
I. Hệ miễn dịch
1.2.1. Khái niệm hệ miễn dịch
Miễn dịch học bắt đầu được biết đến vào năm 1976 khi Edward Jenner làm
thí nghiệm tiêm một lượng nhỏ virus đậu mùa vào động vật, sau đó động vật này có
thể chống lại virus đậu mùa lây nhiễm từ lần thứ hai trở đi. Quá trình này được gọi
là quá trình tiêm chủng. Từ đó khoa học về miễn dịch liên tục phát triển đến nay nó
đã đạt được rất nhiều thành tựu cả về mặt lý thuyết cũng như thực tế. Có thể định
nghĩa HMD như sau:
HMD là hệ thống sinh học bảo vệ cơ thể chống lại những tấn công liên tục
của các sinh vật từ bên ngoài, với hai chức năng chính là nhận diện và loại bỏ
những vi sinh vật xâm nhập vào cơ thể [2].
đủ, chỉ biết chúng có khả năng nuốt các hạt lạ, có mặt với số lượng lớn trong niêm
mạc và các cơ quan bề mặt bao phủ trong cơ thể đồng thời có liên quan đến các đáp
ứng dị ứng.
− Bạch cầu ái kiếm (Basophils): Chức năng của bạch cầu ái kiếm chưa được biết rõ,
chỉ biết chúng có khả năng nuốt các vật lạ có chứa histamine và heparin.
− Lymphô bào (Lymphocyte): Là thành phần của HMD thích nghi. Là một loại bạch
cầu ở trong các hạch bạch huyết, lách, tuyến ức, thành ruột, và tuỷ xương. Các
lymphô bào có nhân đặc và bào tương màu xanh lạt sáng. Lymphô bào có thể chia
ra lymphô bào B sản sinh ra kháng thể và lymphô bào T liên quan đến việc loại thải
mô ghép. Lymphô bào có nhiệm vụ nhận diện và loại bỏ tác nhân gây bệnh.
7
7
1.2.3. Các cơ chế kích hoạt (hoạt hoá) và nhận diện miễn dịch cơ bản
HMD chứa một tập tế bào (cells) và phần tử (molecules) bảo vệ cơ thể chống
lại sự lây nhiễm. Khi bị các kháng nguyên tấn công HMD thích nghi sẽ được kích
hoạt. Kháng nguyên có thể là những phần tử bên ngoài (antigen) như các phần tử
trên bề mặt của các tác nhân gây bệnh hoặc các kháng nguyên do tế bào của cơ thể
tạo ra (self-antigen) [2].
Hình 1.2 là một ví dụ đơn giản về cơ chế kích hoạt và nhận diện của HMD.
Phần 1 của sơ đồ cho thấy cách thức hoạt động các tế bào trình diện kháng nguyên
(Antigen presenting Cells – APC). Đầu tiên những kháng nguyên sẽ bị các cơ quan
trình diện kháng nguyên như đại thực bào nuốt và tiêu hoá, phân ra thành các
peptide kháng nguyên. Một phần của những peptide này kết hợp với các phần tử
MHC (major histocompatibility complex – phức hợp các phần tử có nhiệm vụ trình
diện peptide kháng nguyên cho T-cell) trên bề mặt của APC tạo thành phức hợp
MHC/peptide (II).
T-Cell mang những cơ quan thụ cảm bề mặt cho phép chúng nhận dạng các
phức hợp MHC/peptide khác nhau (III). Mỗi khi nhận diện được MHC/peptide, T-
cell sẽ được kích hoạt, phân chia và tạo ra các lymphokine (là một loại bạch cầu)
hoặc các tín hiệu hoá học (chemical signals) kích thích các thành phần khác của
nước mắt chứa những enzym có thể loại bỏ kháng nguyên. Các axit trong vùng da
cùng với nhiệt độ của cơ thể cũng ngăn cản sự sống và kháng sinh của một kháng
nguyên.
HMD thích nghi và bẩm sinh:
− HMD bẩm sinh: Hoạt động dựa vào bạch cầu huyết là đại thực bào và bạch cầu
trung tính (có chức năng nuốt và tiêu diệt các vi trùng, tạo ra một cơ chế bảo vệ
quan trọng chống lại các bệnh truyền nhiễm). Những bạch huyết này có các cơ
quan thụ cảm trên bề mặt có thể nhận diện và bám vào các phần tử gây bệnh.
Với những vi khuẩn thông thường, HMD bẩm sinh có thể nhận diện và
loại bỏ.
HMD bẩm sinh không có cơ chế ghi nhớ, hoạt động của HMD bẩm sinh
đối với các vi sinh vật xâm nhập vào cơ thể lần thứ hai không có gì khác so với
lần thứ nhất.
− HMD thích nghi: hoạt động với các thành phần chính là các lymphô bào
(Lymphocyte – là một loại bạch cầu) bao gồm B-cell và T-cell. Các B-cell và T-
cell trên bề mặt của chúng có những cơ quan thụ cảm chuyên dụng cho một loại
kháng thể nào đó. Khi kháng nguyên xâm nhập vào cơ thể các cơ quan thụ cảm
trên bề mặt của lymphô bào sẽ kết hợp với kháng nguyên làm cho các lymphô
bào này được kích hoạt và thực hiện quá trình nhân rộng, đột biến sau đó tạo ra
những kháng thể thích hợp có khả năng nhận diện và loại ổ kháng nguyên. Một
số lymphô bào sẽ trở thành self có khả năng ghi nhớ lưu thông trong cơ thể. Khi
có loại kháng nguyên tương tự lây nhiễm, sau đó HMD thích nghi có thể nhanh
chóng phát hiện và loại bỏ chúng. Khả năng này giúp cho cơ thể không mắc lại
những bệnh cũ, do đó đáp ứng miễn dịch thích nghi cho phép HMD tự hoàn
thiện sau mỗi lần đụng độ với kháng nguyên. Tóm lại, lympho bào gồm lympho
10
10
bào B sản sinh ra kháng thể và lympho bào T liên quan đến việc loại thải mô
ghép. Lympho bào có tác dụng nhận diện và loại bỏ tác nhân gây bệnh.
Như vậy, tế bào chịu trách nhiệm phát hiện mầm bệnh trong HMD là
1.2.1. Hệ miễn dịch nhân tạo là gì?
Có rất nhiều định nghĩa về HMD nhưng định nghĩa sau là rõ ràng và chặt chẽ
hơn cả và phù hợp với những nội dung mà đề tài sẽ trình bày:
“HMD nhân tạo là một hệ thống thích nghi lấy ý tưởng của miễn dịch học
thuyết và những chức năng, nguyên tắc, mô hình miễn dịch quan sát được, áp dụng
giải các bài toán thực tế” (Castro & Timmis - 2002).
Hệ miễn dịch sinh học bảo vệ các sinh vật sống trước các tác nhân gây bệnh
từ bên ngoài như vi khuẩn, virus, kí sinh trùng và độc tố. Vai trò của hệ thống bảo
mật trong máy tính cũng tương tự như vai trò của HMD trong cơ thể các sinh vật
sống, Các đối tượng này có sự tương đồng ở cơ chế và biện pháp bảo vệ chính mình
khỏi các xâm nhập.
1.2.2. Cấu trúc cơ bản của hệ miễn dịch nhân tạo
1.2.2.1. Mô hình chung cho các hệ thống phỏng tiến hoá sinh học
Trong các thuật toán phỏng tiến hoá sinh học nói chung, đối tượng chính của
chúng là một tập nhiễm sắc thể nhân tạo (một quần thể), quần thể này trải qua quá
trình chọn lọc, sản sinh và đột biến gien. Quá trình này lặp lại nhiều lần, mỗi lần
như thế là một quần thể tiến hóa hơn xuất hiện. Để xây dựng được cấu trúc cơ bản
12
12
của mô hình này người ta phải biểu diễn được gien các cá thể trong quần thể, cùng
với các thủ tục lựa chọn, sản sinh và đột biến gien.
Cấu trúc cơ bản của hệ thống phỏng sinh học cần có 3 yếu tố cơ bản sau:
− Biểu diễn các thành phần của hệ thống.
− Cơ chế đánh giá tương tác của các cá thể với môi trường và các cá thể với
nhau. Môi trường thường mô phỏng bởi một tập kích thích vào, một hoặc
nhiều hàm đo độ thích nghi của cá thể với môi trường.
− Các thủ tục thích nghi điều khiển tính động của hệ thống, tức là làm cho
hoạt động của hệ thống thay đổi theo thời gian.
1.2.2.2. Mô hình cho hệ miễn dịch nhân tạo
Hình 1.5. Cấu trúc phân tầng của HMD nhân tạo
Loại bỏ
Cho vào quần thể có giá trị A
Không khớp
Khớp
Phần tử p trong P nhận diện được một phần tử nào đó trong S
S
Quần thể tiềm năng P
1.2.4.1.Thuật toán chọn lọc tích cực (Positive Selection Algorithms)
Ý tưởng của thuật toán khá đơn giản, đó là chọn lọc những T-cell có thể
nhận diện các peptide (một phần của kháng nguyên xâm nhập vào cơ thể), mà
peptide này đã kết hợp với MHC (Major Histocompatibility Complex - phức hợp
các phần tử có nhiệm vụ trình diện peptide kháng nguyên cho T-cell) để tạo thành
MHC/peptide. Giả thiết có tập MHC/peptide, kí hiệu là tập S, các cơ quan thụ cảm
T-cell sẽ phải được kiểm tra về khả năng kết hợp với các phần tử thuộc tập S này.
Nếu một T-cell không nhận diện được bất kỳ phần tử nào, nó sẽ bị loại bỏ. Trái lại
nó được chọn như một self có khả năng miễn dịch và bổ sung vào quần thể A.
Thuật toán chọn lọc tích cực được minh họa như trong sơ đồ 2 và nó có thể
tóm tắt như sau:
Bước 1. Khởi tạo: Sản sinh một quần thể tiềm năng P những T-cell chưa
trưởng thành. Giả thiết tất cả các phần tử được biểu diễn như các chuỗi nhị phân có
cùng độ dài L, 2
L
phần tử khác nhau được tạo ra.
Bước 2. Đánh giá độ thích hợp: Xác định độ thích hợp của tất cả phần tử
trong quần thể P với tất cả phần tử trong tập S.
Bước 3. Tạo một quần thể có giá trị: Nếu độ thích hợp của một phần tử trong
P với một phần tử trong S lớn hơn hoặc bằng một ngưỡng tương tác chéo e nào đó
thì T-cell có khả năng nhận diện kháng nguyên, sẽ được chọn vào quần thể giá trị A
trái lại T-cell bị loại bỏ.
Hình 1.7. Thuật toán chọn lọc tích cực
16
0111
0101
1000
1001
Không khớp
Khớp
0111
1000
……
0010
1000
1001
0000
0100
0010
1001
0011
0111
1000
0101
1000
………
(lấy)
(loại)
Tập bộ dò R
Sinh ngẫu nhiên các chuỗi R0
Các chuỗi self S
Hình 1.9. Quá trình chọn lọc tiêu cực
1.2.5. Sự tương quan giữa hệ miễn dịch với môi trường mạng
biệt giữa kết nối "xấu" được gọi là sự xâm nhập hoặc tấn công, và "tốt" kết nối bình
thường.
Năm 1998 Chương trình đánh giá phát hiện xâm nhập đã được DARPA chuẩn
bị và quản lý bởi MIT Lincoln Labs. Mục tiêu là để khảo sát và đánh giá nghiên cứu
trong việc phát hiện xâm nhập. Một tập hợp các tiêu chuẩn của dữ liệu được kiểm
toán, bao gồm một loạt các mô phỏng của sự xâm nhập được cung cấp trong một
môi trường mạng quân sự. Cuộc thi phát hiện xâm nhập KDD 1999 sử dụng một
phiên bản của tập dữ liệu này. Lincoln Labs thiết lập một môi trường để có được
chín tuần dữ liệu thô TCP dump cho một mạng cục bộ (LAN) mô phỏng một mạng
LAN không quân Mỹ điển hình. Họ hoạt động mạng LAN như thể nó là một môi
trường Air Force nhưng nó rải rác với nhiều cuộc tấn công.
Dữ liệu huấn luyện thô là khoảng 4 gigabyte nén dữ liệu nhị phân TCP dump
lấy từ bảy tuần lưu lượng mạng. Điều này đã được xử lý vào khoảng 5.000.000 bản
ghi kết nối. Tương tự như vậy, hai tuần của dữ liệu thử nghiệm bắt được khoảng hai
triệu bản ghi kết nối.
18
18
Một kết nối là một chuỗi các gói tin TCP bắt đầu và kết thúc tại một số thời
gian được xác định rõ ràng, giữa những luồng dữ liệu đến và đi từ một địa chỉ IP
nguồn đến một địa chỉ IP đích theo một số giao thức được xác định rõ. Mỗi kết nối
được dán nhãn hoặc là bình thường, hoặc là một tấn công, với chính xác một loại
tấn công cụ thể. Mỗi bản ghi kết nối bao gồm khoảng 100 byte.
Các cuộc tấn công thuộc bốn loại chính sau:
− DOS: tấn công từ chối dịch vụ, ví dụ như SYN Flood;
− R2L: truy cập trái phép từ một máy từ xa, ví dụ như đoán mật khẩu;
− U2R: phép truy cập vào cục bộ (root) để đặc quyền siêu người dùng, ví dụ như
các cuộc tấn công khác nhau như "tràn bộ đệm";
− Probing: giám sát và các thăm dò khác, ví dụ như quét cổng.
Điều quan trọng cần lưu ý là các dữ liệu thử nghiệm không phải là từ phân
phối xác suất giống như dữ liệu huấn luyện, và nó bao gồm các kiểu tấn công cụ thể
Có thể sử dụng kiến thức miền để thêm thuộc tính tìm kiếm các hành vi đáng ngờ
trong các phần dữ liệu, chẳng hạn như số lần đăng nhập thất bại. Những thuộc tính
này được gọi là thuộc tính "nội dung".
2.2. Phân tích chi tiết về tập dữ liệu KDD 99
2.2.1. Giới thiệu
Với sự tăng trưởng to lớn của việc sử dụng mạng máy tính và sự gia tăng rất
lớn số các ứng dụng chạy trên nó, an ninh mạng ngày càng trở nên quan trọng. Tất
cả các hệ thống máy tính bị lỗi bảo mật trong đó có cả khó khăn về mặt kỹ thuật và
tốn kém về kinh tế đều được giải quyết bởi các nhà sản xuất. Do đó, vai trò của hệ
thống phát hiện xâm nhập (IDS) được ví như là các thiết bị chuyên dụng dùng để
phát hiện sự bất thường và các tấn công mạng. Những nghiên cứu trong lĩnh vực
phát hiện xâm nhập có được tập trung chủ yếu là dựa trên sự bất thường và lạm
dụng dựa trên kỹ thuật phát hiện trong một thời gian dài. Trong khi lạm dụng phát
hiện bất thường được ưa chuộng trong các sản phẩm thương mại do khả năng dự
đoán của nó và độ chính xác cao của nó, thì trong nghiên cứu lý thuyết phát hiện bất
thường hay được hình thành như là một phương pháp mạnh do tiềm năng lý thuyết
của nó cho địa chỉ tấn công mới.
Tiến hành phân tích sâu các xu hướng nghiên cứu gần đây trong việc phát hiện
bất thường, người ta sẽ bắt gặp một vài phương pháp học máy có một tỷ lệ phát
20
20
hiện rất cao 98% trong khi vẫn giữ tỷ lệ cảnh báo sai ở mức 1%. Tuy nhiên, khi
xem xét giải pháp IDS kiểu hiện đại và thương mại công cụ thì có vài sản phẩm sử
dụng phương pháp phát hiện bất thường và các học viên thì vẫn cho rằng nó không
phải là một công nghệ hoàn thiện. Để tìm ra lý do tương phản này thì chúng ta sẽ
nghiên cứu các chi tiết nghiên cứu được thực hiện trong phát hiện bất thường và
xem xét các khía cạnh khác nhau như phương pháp học máy và phương pháp tiếp
cận phát hiện, tập hợp dữ liệu huấn luyện, tập hợp dữ liệu thử nghiệm, và phương
pháp đánh giá. Nghiên cứu cho thấy rằng có một vấn đề vốn có trong bộ dữ liệu
KDDCUP 99, nó được sử dụng rộng rãi như là một tập dữ liệu công bố công khai
chi phí là phải chăng để chạy hoàn thành các thí nghiệm trên mà không phải chọn
ngẫu nhiên một phần nhỏ trong các tập huấn luyện và các tập thử nghiệm hợp lý.
Do đó, đánh giá kết quả các công trình nghiên cứu khác nhau sẽ phù hợp và có thể
so sánh.
Các phiên bản mới của bộ dữ liệu KDD, NSL-KDD là công khai có sẵn cho
các nhà nghiên cứu thông qua website1. Mặc dù, tập hợp dữ liệu vẫn còn tồn tại
một số các vấn đề và có thể không là một đại diện hoàn hảo của mạng hiện có thật
sự, vì thiếu dữ liệu công cộng đặt IDS dựa trên mạng, họ tin rằng nó vẫn có thể
được áp dụng như một tập dữ liệu chuẩn để giúp các nhà nghiên cứu so sánh
phương pháp phát hiện xâm nhập khác nhau.
2.2.2. Mô tả tập dữ liệu KDD
Từ năm 1999, tập dữ liệu KDD 99 đã được sử dụng nhiều nhất cho việc thẩm
định các phương pháp phát hiện bất thường. Tập hợp dữ liệu này được chuẩn bị và
được xây dựng dựa trên các dữ liệu bắt được trong chương trình đánh giá Hệ thống
phát hiện bất thường DARPA’98. DARPA có khoảng 4GB nén thô (nhị phân) dữ
liệu tcpdump của 7 tuần lưu thông mạng có thể được xử lý thành khoảng 5 triệu bản
ghi kết nối, với mỗi bản ghi khoảng 100 byte. Hai tuần của dữ liệu thử nghiệm có
khoảng 2 triệu bản ghi kết nối. Tập dữ liệu KDD huấn luyện bao gồm khoảng
4.900.000 vectơ kết nối đơn trong đó chứa 41 thuộc tính và được dán nhãn là bình
thường hoặc một loại tấn công cụ thể nào đó với sự chính xác là một loại tấn công
cụ thể. Các cuộc tấn công được mô phỏng xếp vào một bốn loại sau đây:
22
22
Tấn công từ chối dịch vụ (DoS): là một cuộc tấn công mà trong đó kẻ tấn
công làm cho một số máy tính hoặc bộ nhớ tài nguyên quá bận hoặc quá đầy để xử
ý các yêu cầu hợp lệ, hoặc từ chối người dùng hợp pháp truy cập vào một máy tính.
Tấn công người dùng vào thư mục gốc (U2R): là một lớp khai thác trong đó
kẻ tấn công bắt đầu với truy cập bình thường vào tài khoản người dùng trên hệ
thông (có thể thu được bằng cách can thiệp mật khẩu, một cuộc tấn công từ điển,
hoặc kỹ thuật xã hội) và có thể khai thác một số lỗ hổng để đạt được thư mục gốc
Kết quả là, các cuộc tấn công không sản xuất mô hình xâm nhập với một cửa sổ
thời gian 2 giây. Để giải quyết vấn đề này, thuộc tính "cùng máy chủ" và “cùng
dịch vụ" tính toán lại dựa trên cửa sổ kết nối của 100 của 100 kết nối chứ không
phải là một cửa sổ thời gian 2 giây. Những tính năng này được gọi là thuộc tính
“lưu thông” dựa trên kết nối.
3. Các thuộc tính nội dung: Không giống hầu hết các cuộc tấn công DoS và
Probing, các cuộc tấn công R2L và U2R không có bất kỳ xâm nhập thường
xuyên nào theo mô hình tuần tự. Điều này là do các cuộc tấn công Dos và
Probing liên quan đến nhiều kết nối của một số máy chủ trong một thời gian rất
ngắn. Tuy nhiên các cuộc tấn công R2L và U2R được nhúng trong các phần dữ
liệu của các gói dữ liệu, và thường liên quan đến việc chỉ có một kết nối duy
nhất. Để phát hiện các loại tấn công, cần một số thuộc tính để có thể tìm ra
những hành vi đáng ngờ trong các phần dữ liệu, ví dụ: số lượng cố gắng đăng
nhập thất bại, các thuộc tính này được gọi là các thuộc tính nội dung.
2.2.3. Vấn đề có thể có trong tập dữ liệu KDD 99
Như đề cập trong phần trước, KDD 99 được xây dựng dựa trên các dữ liệu
DARPA'98, do các dữ liệu là tổng hợp nên kết quả là một số vấn đề có trong
DARPA'98 vẫn còn tồn tại trong KDD 99. Tuy nhiên, có một vài cải tiến hơn nó có
thể là có chủ ý hoặc vô ý, và cùng với một số vấn đề bổ sung nữa. Trong phần sau
đây, xem xét lại các vấn đề trong DARPA'98 và sau đó thảo luận về sự tồn tại của
các vấn đề có thể có trong KDD 99. Cuối cùng là thảo luận các vấn đề mới quan sát
thấy trong các tập hợp dữ liệu KDD.
1. Đối với mục đích riêng: các thí nghiệm đã lựa chọn tổng hợp trên cả hai dữ
liệu: dữ liệu nền và dữ liệu tấn công, và dữ liệu được khẳng định là tương tự như
một số dữ liệu mẫu quan sát được từ trong một số cơ sở dữ liệu của lực lượng
24
24
không quân. Tuy nhiên, không phân tích cũng không thí nghiệm xác nhận các đặc
điểm của dữ liệu cảnh báo sai. Hơn nữa, khối lượng công việc của dữ liệu tổng hợp
có vẻ không giống như lưu lượng truy cập trong các mạng thực sự.
Copyright: Tài liệu đại học ©