Nghiên Cứu Phát Hiện Hot-Ips Trên Mạng Ip Và Ứng Dụng

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (5.45 MB, 26 trang )

Trang 1<div class="page_container" data-page="1">

HỌC VIỆN CƠNG NGHỆ BƯU CHÍNH VIỄN THÔNG

PHAM HONG KY

NGHIEN CUU PHAT HIEN HOT-IPS TREN MANG IP VA UNG DUNG

Chuyén nganh: Khoa hoc may tinh

Mã số: 60.48.01.01

TÓM TẮT LUẬN VĂN THẠC SĨ

HÀ NỘI - 2015

</div>Trang 2<div class="page_container" data-page="2">

Luận văn được hồn thành tại:

HỌC VIỆN CƠNG NGHỆ BƯU CHÍNH VIỄN THƠNG

Người hướng dẫn khoa học: Tiến sĩ. Hoàng Xuân Dậu

Phản biện 1: TS. Lương Thế Dũng

Phan biện 2: PGS.TS. Hà Quốc Trung

Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Cơng nghệ

Bưu chính Viễn thơng

Vào lúc: 14 giờ 30 ngày 27 tháng 2 năm 2016

Có thể tìm hiểu luận văn tại:

- Thư viện của Học viện Công nghệ Bưu chính Viễn thơng

</div>Trang 3<div class="page_container" data-page="3">

MỞ ĐẦU

Vấn đề đảm bảo an tồn cho thơng tin, hệ thống và người dùng mạng máy tính và

rộng hơn là mạng Internet đã và đang nhận được nhiều sự quan tâm của các cơ quan, tổ chức và đông đảo người dùng trong những năm gan đây do sự pho biến của các dạng phan mềm độc hại như virus, sâu mạng và các dạng tấn công mạng. Nhiều giải pháp và cơng cụ đảm bảo an tồn đã được đề xuất và triển khai như các giải pháp dựa trên mã hóa thơng tin, các giải pháp xác thực và điều khiển truy cập, và các giải pháp giám sát, phát hiện tan cơng, xâm nhập trái phép. Trong đó, giải pháp giám sát, phát hiện tấn công, xâm nhập thường được sử dụng như lớp phòng vệ thứ 2 trong mơ hình phịng vệ nhiều lớp có chiều sâu. Các kỹ thuật thường được sử dụng trong phát hiện tấn công, xâm nhập bao gồm thống kê, học máy, mạng nơ ron nhân tạo và lập trình tiến hóa. Luận văn này ứng dụng phương pháp thống kê tìm các Hot-IP là các địa chỉ IP có tần suất xuất hiện lớn trong luồng dữ liệu trao đổi trên mạng máy tính, hoặc mạng Internet dé phát hiện đích hoặc nạn nhân của tấn công

Luận văn được chia làm 3 phan:

Chương 1: Luận văn trình bày khái niệm về Hot-IP, các phương pháp tìm phan tử có tần suất cao và một số nghiên cứu có liên quan. Từ đó đưa ra được bài toán cần phải

giải quyết của luận văn.

Chương 2: Luận văn trình bày phương pháp phát hiện Hot-IPs dựa trên một số thuật toán tim phan tử có tần suất cao. Sau đó, đưa ra so sánh về độ phức tạp giữa các thuật toán, và thực nghiệm thuật toán dé đưa ra so sánh về thời gian thực tế.

Chương 3: Luận văn trình bày khái quát về tấn công DDoS, các phương pháp tấn công DDoS và một số phương án phịng chống tấn cơng DDoS. Từ đó, triển khai phương pháp phịng chống tan cơng DDoS dựa trên phát hiện nhanh Hot-IPs.

</div>Trang 4<div class="page_container" data-page="4">

CHUONG 1: TONG QUAN VE HOT-IPS

1.1. Giới thiệu về Hot-IPs

Ngày nay, công nghệ thông tin đã và đang phát triển một cách mạnh mẽ đem lại

những lợi ích và ứng dụng to lớn cho con người. Mạng máy tính ra đời, mở rộng và phát

triển không ngừng tạo nên mạng Internet tồn cầu. Lợi ích mà Internet mạng lại là rất lớn,

như chia sẻ tài nguyên, trao đồi và tìm kiếm thơng tin hiệu quả, nhanh chóng, tiết kiệm thời

gian, chỉ phí. Internet đã trở thành một phần khơng thể thiếu trong cuộc sống của loài

Sự phát triển mạnh mẽ của Internet kéo theo nhiều mối hiểm họa trong đó có tấn cơng từ chối dịch vụ. Các cuộc tan công từ chối dịch vụ hay sự phát tán của sâu mạng ngày càng đa dạng và dễ thực hiện nhưng có khả năng gây tác hại rất lớn. Việc phát hiện sớm các

cuộc tấn công từ chối dịch vụ hay sự phát tán sâu mạng là rất cần thiết, đặc biệt với các mạng có lưu lượng lớn, tốc độ cao dé có các giải pháp phản ứng và giảm thiêu thiệt hại. Dựa vào dòng dữ liệu lưu thông qua các thiết bị mạng, thông qua các thông tin về địa chỉ nguồn

(IP nguồn) và địa chỉ đích (IP đích) của các gói tin, có thé xác định các IP đích được truy

xuất với tần suất cao (Hot-IP), từ đó đưa ra khả năng các máy chủ này đang bị tấn công từ chối dịch vụ.

1.2. Khái niệm Hot-IP

Mỗi một máy tính khi kết nối vào mạng Internet đều có một địa chỉ IP duy nhất. Địa chỉ này dùng đề phân biệt máy tính đó với các máy tính cịn lại trên mạng Internet. Nói ngắn gọn thì /P /a địa chi dung dé định danh cho các thiết bị trên mạng Internet.

Trên đường truyền xác định, dịng gói tin IP là một dãy tuần tự các gói tin IP ai, ao,

..., am. Dựa vào bài tốn xác định nạn nhân tấn công từ chối dịch vụ hay phát tán sâu mạng

mà aj sẽ có địa chỉ s¡ với si là địa chỉ nguồn hoặc dia chỉ đích. Khi s¡ xuất hiện với tần suất

cao trong dịng gói tin IP thì s; được gọi là Hot-IP.

Hot-IP trong dịng gói tin IP trên mang may tính là những IP xuất hiện với tần suất

cao. Cho một dịng gói tin IP: S = (a1, a2, ..., am), trong đó có n địa chi IP phân biệt. Gọi fj là

tần suất của gói tin có địa chỉ IP là si trong S, ƒ = |UIs; = si}| với i<f<mn và 1<j<

m. Ta có ƒ¡ + fo +++ f, =m và cho một ngưỡng ø, Hot-IP = {s,|ƒ; = gm} [5][6].

</div>Trang 5<div class="page_container" data-page="5">

1.3. Khái quát về phương pháp tìm phần tử có tần suất cao

1.3.1. Thuật tốn Majority

Thuật tốn Majority được đề xuất bởi Boyer-Moore năm 1982[1][10]. Phan tử phổ

biên được định nghĩa là phân tử có tơng sơ lân xt hiện nhiêu hơn nửa tơng sơ các gói

trong dịng đữ liệu.

Thuật tốn Majority được tóm tắt như sau: Cho dong dtr liệu P = (aj, ..., am) với N phan tử phân biệt có vector tần suất f = (fi,...,fn) và ƒ¡ + ...+ fa = m. Phan tử có tần suất cao được xác định bởi j | ý > m/2,j chính là phan tử cần tìm.

1.3.2. Thuật toán Frequent

Thuật toán Frequent được đề xuất bởi Misra và Gries năm 1982[7][12] dé tìm ra tat cả các phần tử có tần suất xuất hiện lớn hơn m/k với k là số phần tử có tần suất cao cần tìm. Thuật tốn sử dụng k cặp (phan tử - biến đếm) dé giám sát k phan tử.

Thuật toán thực hiện như sau: Cho một phần tử trong dòng dữ liệu, nếu phần tử đó đã tồn tại trong k cặp thì tăng biến đếm tại phần tử đó lên 1. Nếu số phần tử đã được lưu nhỏ hơn k thì phần tử mới có biến đếm là 1. Ngược lại, giảm tất cả các bộ đếm, nếu tồn tại bộ đếm băng 0 thì ta xóa phần tử đó đi. Kết thúc thuật tốn ta sẽ có được nhiều nhất k phần tử có tần suất lớn hơn m/k.

1.3.3. Thuật toán LossyCounting

Thuật toán LossyCounting được đề xuất bởi Manku và Motwani năm 2002[4]. Thuật toán sử dụng cấu trúc lưu trữ được quy định bởi ba thuộc tính sau: phần tử, chặn dưới L (Lower Bound) và chặn trên H (Higher Bound). Gọi P = H — L, khi xử lý phan tử thứ i trong dòng dữ liệu, nếu phần tử đã được lưu thì L = L +1, ngược lại tao một cau trúc mới cho phan tử này và L = 1, P = i/k. Nếu H < i⁄k thì phan tử ¡ sẽ bị xóa. Kết thúc thuật tốn sẽ nhận được kết quả là các phần tử có tần suất lớn hơn n/k.

1.3.4. Thuật toán Space Saving

Thuật toán Space Saving được đề xuất bởi Metwally năm 2005[11]. Thuật toán sử

dụng cấu trúc lưu trự gồm kbộ (phần tử, biến đếm). Ban đầu, k bộ đếm này được khởi tạo

với k phần tử riêng biệt và biến đếm tương ứng bằng 1. Nếu một phần tử mới chưa được lưu trữ, thay thé phan tử có giá trị đếm nhỏ nhất và khởi tạo bộ đếm bang giá trị nhỏ nhất cộng

thêm 1. Thuật toán này gần giống với việc sử dụng cấu trúc heap dé lưu trữ phan tử theo thứ tự giảm dần. Kết quả nhận được là k phần tử có tần suất giảm dần từ lớn đến bé.

</div>Trang 6<div class="page_container" data-page="6">

1.3.5. Thuật toán Count Sketch

Thuật toán Count Sketch được đề xuất bởi Charika năm 2002[12]. Mỗi một phần tử

được xác định vi trí bởi ham băm, giá tri đếm của các phần tử được tăng lên khi được đưa vào. Thuật toán sử dung cấu trúc dit liệu sketch dé tìm k phan tử có tần suất cao trong dong dữ liệu. Thuật tốn nhận vào dịng dữ liệu S, một số nguyên k, số thực € và số thực 6, sau đó tính tốn trả về k phần tử có tần suất thỏa mãn có tần suất lớn hơn (1-e)nx trong đó nx là tần suất của phần tử thứ k trong dòng dữ liệu. Count Sketch sử dụng cấu trúc dữ liệu là một mảng một chiều d * w, d hàm băm và w bộ đếm. Ước lượng tần suất của Count Sketch là

trung bình của hj với 1 <=j = d.

1.3.6. Thuật tốn Count Min

Thuật toán Count Min được đề xuất bởi Cormode và Muthukrishnan năm 20052]. Tương tự như Counter Sketch, thuật toán này sử dụng cấu trúc dữ liệu sketch là mảng 2 chiều gồm d dòng va w bộ đếm, sử dụng d hàm băm hj, mỗi dòng là mộ hàm băm. Mỗi khi có phan tử thứ j đến thì phan tử đó sẽ được ánh xạ tương ứng hj và bộ đếm tai hj sẽ được tăng lên. Ước lượng tần suất của counter min là giá trị nhỏ nhất của hj với 1 <= j <= d.

1.3.7. Thuật tốn thi nhóm

Thuật tốn thử nhóm được cải tiễn từ thuật toán Count Min và ứng dụng lý thuyết

thử nhóm của Dorfman năm 1943 do nhóm tác giả Cormode và Muthukrishnan [3] thực

hiện để cải thiện bài tốn tìm phần tử có tần suất cao. Thuật tốn được thiết kế với t phép

thử dé tìm d phần phan tử có tần suất cao trong m phan tử trong dịng dữ liệu. Mỗi một phép thử tại ¡ sẽ có một biến đếm c¡ tương ứng. Phần tử ¡ có tần suất cao nếu thỏa mãn c¡ >

1.4. Một sô nghiên cứu có liên quan

Năm 2012, vấn đề phát hiện nhanh Hot-IPs sử dụng phương pháp thử nhóm (group

testing) do nhóm tác gia Huỳnh Ngun Chính [5] được dé xuất trong bài báo “Finding

Hot-IPs in network using group testing method — a review”. Bai báo nay đã trình bày việc khảo

sát sử dụng lý thuyết thử nhóm dé phát hiện các Hot-IP trong một số trường hợp: tan công từ chối dich vụ (DoS), worm, virus trong mạng và thực hiện các phép thử để tối ưu hóa thời gian chạy của thuật toán dé tăng hiệu qua cho việc phát hiện nhanh các Hot-IP.

Tác giả đã sử dụng phương pháp thử nhóm bat ứng biến dé tìm hot-ip. Giả sử có t

</div>Trang 7<div class="page_container" data-page="7">

Năm 2013, nhóm tác giả triển khai ứng dụng phát hiện nạn nhân của tấn công DDoS dựa trên phương pháp phát hiện nhanh Hot-IP đã đề xuất [6]. Các kết quả trình bày trong

bài báo “Fast Detection Of DDos Attacks Using Non-Adaptive Group Testing”[6] khá kha

1.5. De xuat bài toán của luận văn

Luận văn này tập trung nghiên cứu ba phương pháp phát hiện nhanh Hot-IP là Counter

Sketch, Counter Min và phương pháp thử nhóm (Group testing) để giải quyết bài tốn phát

hiện nhanh đích tấn cơng DDoS dựa trên phát hiện Hot-IPs.

Bài toán của luận văn được chia ra làm hai phân chính là:

- Co sở lý thuyết của 3 thuật tốn, sau đó tiễn hành cài đặt, thử nghiệm và đánh giá dựa trên tập dữ liệu gói tin IP có sẵn.

- Thu nghiệm kha năng phát hiện Hot-IP của ba thuật toán dé đưa ra được một số kết luận về khả năng phát hiện, thời gian xử lý thực tế của từng phương pháp và đưa ra

lựa chọn phương pháp phù hợp.

1.6. Tổng kết chương

Chương này giới thiệu tổng quan về Hot-IP, trong đó bao gồm khái niệm về Hot-IP, các trình bày về địa chỉ IP và các đặc điểm của nó trong dịng gói tin IP. Luận văn cũng đề cập tới bài tốn tìm phần tử có tần suất cao trong dịng dữ liệu và cũng trình bày các thuật

tốn thường được sử dụng như: Majority, Frequent, Lossy Counting, Space Saving, Count

Sketch, Count Min va thử nhóm. Bài tốn phát hiện Hot-IP là bài tốn có nhiều ứng dụng quan trọng trên mạng như phát hiện các thiết bị hoạt động bất thường trên mạng, phát hiện nhanh nạn nhân trong tấn công từ chối dịch vụ hay phát hiện nguồn phát tán sâu mạng. Luận văn cũng phân tích các nghiên cứu của nhóm tác giả Huỳnh Nguyên Chính nghiên cứu triển khai ứng dụng phương pháp thử nhóm để phát hiện Hot-IP trên mạng IP và nêu nội dung của bài toán giải quyết trong đề tài.

</div>Trang 8<div class="page_container" data-page="8">

CHUONG 2: CAC PHƯƠNG PHÁP PHÁT HIỆN NHANH

HOT-IPs

2.1. Phương pháp Counter-Sketch2.1.1. Giới thiệu phương pháp

Phương pháp Counter-Sketch được giới thiệu đầu tiên bởi Charikar Chen và Faranch Colton năm 2002 và phiên bản cải tiến vào năm 2004 [12]. Counter Sketch được đưa ra nhằm giải quyết bài tốn tìm k phan tử có tần suất lớn trong dịng dữ liệu. Đặc điểm của cau

trúc dữ liệu sketch là nhỏ gọn, q trình xử lý nhanh và đảm bảo việc tính xấp xỉ tần suất của phần tử trong luồng đữ liệu là cực kỳ đơn giản.

Thuật toán Counter Sketch được thực hiện qua 3 bước

Bướóc 1: Khoi tạo: Initial(e, 6)

Bước 2: Vòng lặp xử lý luồng dữ liệu: Process(j, c) với c là một phan tử trong dòng dữ liệu Bước 3: Xử lý kết quả: Estimate(j) lẫy trung bình của các biến tại C[hQ)]

Kết quả trung bình này chính là sap xi tần suất xuất hiện của phan tử j.

2.1.2. Ung dung phat hién nhanh Hot-IPs

Bài toán xác định nhanh Hot-Ips có thé được mơ hình như sau: Giả sử dịng gói tin

gồm M địa chỉ IP được xem xét, từ IP header ta sẽ lay được dia chi IP UP nguồn hoặc đích

tùy thuộc vào ứng dụng) và có N địa chi IP phân biệt trong M dia chi IP này. Mục tiêu là

phát hiện được k Hot-IP trong luồng địa chỉ IP.

Counter Sketch có ba thủ tục chính để tìm hot-ip

Bước 1: Khởi tạo

Gia sử có luồng dữ liệu IP gồm M = 200.000 địa chi IP trong đó có N = 2214 địa chỉ

</div>Trang 9<div class="page_container" data-page="9">

Bước 3: Tính tan suất xuất hiện của từng IP

Đây là bước tính tần suất xuất hiện của từng IP. Tại đây, thuật tốn sẽ tìm trung bình của các biến đếm tại [j, h(j)]. Giá trị trung bình này sẽ là tần suất xuất hiện của IP j cần tìm.

Kết quả nhận được sau 3 bước thực hiện thuật toán Counter Sketch với t = 10.000

Bảng 2.1: Kết qua tìm Hot-IP với Counter Sketch và t = 10000

STT Địa chỉ IP Tần suất xuất hiện 2.2.1. Giới thiệu phương pháp

Phương pháp Counter Min hay còn gọi là Count-Min Sketch được đề xuất lần đầu tiên bởi G.Cormode và S. Muthukrishnan vào năm 2005, để thay thế cho một số phương

pháp sử dụng dữ liệu sketch khác như Counter Sketch và AMS Sketch[3]. Mục đích chính

là cung cấp một cấu trúc sketch đơn giản, gọn nhẹ với đặc trưng là độ chính xác vào các

tham sơ đâu vào.

Cấu trúc dữ liệu Counter Min là một ma trận các biến đếm đơn giản với độ rộng w và

độ sâu đ, CM[1,1] ... C[dw]. Tương tự với các cấu trúc sketch khác, Counter Min cũng

được xác định thông qua 3 thủ tục chính.Thuật tốn Counter Min

Bước 1: Khởi tạo

- _ Tất cả giá trị của biến đếm trong CM được gan bang 0.

- Khởi tạo đ hàm băm ngẫu nhiên từ cặp số (a, b) độc lập với nhau.

hị ...hạ:{1...đ} — {1...w}

Với mỗi w và đ, ta sẽ có được mộ mang 2 chiêu w*d biên đêm và d hàm băm.Bước 2: Cập nhật dữ liệu Update(afi;])

</div>Trang 10<div class="page_container" data-page="10">

Cho một vector a là tập hợp của nhiều luồng dit liệu. Vector này có n chiều. ứng với thời điểm / ta có a(t) = [ai(t),..ai(t), ...dn(t)]. Ban đầu z(0) là một vector rong, vi vậy a¡(0) =

Bước 3. Tính tan suất xuất hiện của IP

Tại bước này Counter Min sử dụng truy vấn điểm. Truy vấn điểm là việc tính tần suất xuất hiện một giá tri trong vector a;. Việc ước lượng giá tri tại điểm ¡ được thực hiện bởi việc tìm giá trị nhỏ nhất tại tất cả các điểm j tương ứng với h(i).

â¡ = mmim<;<a(CM[J, hy DO)

2.2.2. Ung dụng phát hiện nhanh Hot-IPs

Tương tự như Counter Sketch, Counter Min cũng sử dụng dit liệu đầu vào là luồng M gói tin IP. Mục tiêu là phát hiện được k Hot-IP trong luồng N địa chi IP phân biệt. Luận văn áp dụng phương pháp Counter Min ở trên dé phát hiện k Hot-IP trong N địa chi IP phân

biệt này.

Bước 1: Khởi tạo

Gia sử có luồng dữ liệu IP gồm M = 200.000 địa chỉ IP trong đó có N = 2214 dia chỉ

</div>Trang 11<div class="page_container" data-page="11">

Đề tính tần suất xuất hiện của phan tử Ipj, thuật tốn tìm giá trị nhỏ nhất của tat cả các phần

từ CM[j, hG)] với 1 <=j <= d.

Kết quả nhận được sau 3 bước thực hiện thuật toán Counter Min với t = 10.000

Bảng 2.2: Kết quả tìm Hot-IP với Counter Min và t = 10000

STT Dia chi IP Tan suat xuat hién2.3.1. Giới thiệu phương pháp

Bài tốn sử dụng phương pháp thử nhóm bắt ứng biến được phát biéu như sau: Cho dong dit liệu a có M phan tử, trong đó N phan tử phân biệt (M >> N). Giả sử có tối đa d phan tử có tần suất cao, ta cần thiết kế t phép thử cho N phan tử này. Xây dựng ma trận nhị phân Mixn trong đó các cột của ma trận đại diện cho các phần tử và các hàng đại diện cho các phép thử. Nếu TU] = 1 tức là 1 thuộc về phép thử thứ j và ngược lại T[I][J] = 0 tức là 1 không thuộc về phép thử thứ j.

2.3.1.1. Ma trận d phân cách

Ma trận nhị phân TụụN là ma trận d phân cách khi và chỉ khi hội của d cột bất kỳ

khơng chứa bat kỳ cột nào trong ma trận.

Ví dụ dưới đây là một ma trận 2 phân cách Tox7.âOoơ

1x; |

RPRPRrRoOCOC oOCOoOOrRrRRrROCOoooococorrF

CC CC CCcCccCcCcC'CCCcCcC CC.CO CC CC

</div>Trang 12<div class="page_container" data-page="12">

2.3.1.2. Mã Reed Solomon

Reed Solomon(RS) là một bộ mã [n, k]„ với k <n <q, định nghĩa như sau. Mỗi

một thông điệp m = (mạ, ...,?ny_+) € Fy có thé xem như một da thức bậc k — 1 trên vành

P„(X) = My + mịX + ---+ 1ny_+X*~1

Mã Reed Solomon là một ánh xạ RS: Ff — Fj định nghĩa như sau. Cố định n phan tử khác nhau a, ...@, € F. Định nghĩa:

RS(m) = (Pa(01), ney Pm(en))

Một đa thức bậc k - 7 có nhiều nhất k - 7 nghiệm trên trường bất kỳ. Do đó hai đa thức khác nhau chi có thé trùng giá trị ở nhiều nhất lak - 7 điểm ø,. Vi thế, mã Reed Solomon có khoảng cách ít nhất lad = n —k + J. Vì thế, mã Reed Solomon là một mã

[n, k,n — k + 1],. Mã Reed Solomon đạt đến chặn Singleton, và vì thế cịn được gọi là

một mã phân ly khoảng cách tối da.

2.3.1.3. Phương pháp nối mã

Năm 1964, Kautz và Singleton đề xuất cách xây dựng ma trận d - phân cách dựa trên hai ý tưởng chính. Thứ nhất là nếu các cột của ma trận có “trọng số” đủ lớn và nếu hai cột bat kỳ có khoảng các đủ nhỏ thì ma trận sẽ là ma trận phân cách. Thứ hai là ta có thể dùng phương pháp nói mã dé xây dựng một ma trận thỏa tính chất thứ nhất.

Goi Cou là một mã (m1, ki)q nghĩa là một ánh xạ từ Fj vao F)", trong đó q = 2⁄2.

Xét n¡ mã (na, k2)2 ký hiệu là Cin’, Cin’, ..., Cin’. Tức là, với mọi i € [ny] thì Cn! là

một ánh xạ Ch: Ff? > F*?. Các mã Cin!, Cin?, ..., Cn! được gọi là mã trong.

~ Ke 2 ~ x: ` ~ Z ` ` n ` ^ ~

Mã noi của mã ngoài và mã trong ký hiêu là Co, 9 (Ci, „ „€¡„} là một mã (nino, kik2)2

được định nghĩa như sau.

Cho thông điệp m € Fi"? = (E21, gọi (x1,..., Xn1) = Cou(m), với x; € Fy? thì

Cout 9 (Cấu, .... Cặp } = (Cin a)» Ci (Xn,))

2.3.2. Ứng dụng phát hiện nhanh Hot-Ips

Yêu cầu đầu vào của bài toán phát hiện nhanh Hot-IP sử dụng phương pháp thử nhóm bao gồm:

- Ma trận d phân cách kích thước tx N: T[, NỊ

- Luéng M dia chi IP, N dia chi IP phan biét.

</div>Trang 13<div class="page_container" data-page="13">

- Khoi tạo bộ đếm C[z] và vector kết quả R[¢].

Xây dựng ma trận d phân cách sử dụng mã Reed Solomon

Bài toán này ta sử dụng mã RS[n = 15, k = 3]¡ø, với số IP tối đa là M = 10000.

Sau khi đã tạo được mã Reed Solomon và ma trận don vi J, ta phải sử dụng phép nối mã dé

có được ma trận d phân cách.

Thuật tốn 1: Tính tốn kết quả của phép thử

Ta đặt ¢ = n * ạ = số hàng của ma trận d phân cách.

Như đã giới thiệu ở trên, T[/][7] = 1, tức là JP] thuộc về phép thử thứ i, ngược lại

T[i][j] = 0 tức là [Pj không thuộc về phép thử thứ i. Ta lần lượt kiểm tra từng giá trị IP trong luồng M giá tri IP. Nếu T[i][j] = 1, ta sẽ tăng biến đếm tại C[i] lên 1 đơn vị. Xác định khả năng là hot-ip cho từng IP. Điều kiện dé IPj có khả năng là Hot-IP là C[i] > M/(d+1).

Thuật tốn 2: Xác định hot-ip

Sau khi có được R là danh sách các IP có thé là Hot-IP, thuật tốn sẽ kết hợp với phép thử tại ma trận d phan cach dé lay ra những IP là Hor-IP thực sự.

Với R[i] = 1 tức là mà JP; thuộc về phép thử thứ i có kha năng là Hør-IP, do vậy ta

sử dụng phép thử dé loại đi những khả năng không phải là Hot-JP. Với R[i] = 0, mà tại đó

IP; thuộc về phép thử thứ i, thì tức là /Pj khơng phải là Hot-IP. Thuật tốn tiến hành loại bỏ IP; ra khỏi tập N giá trị IP. Kết quả cuối cùng, Hot-IP chính là những IP cịn lại trong tập IP.

Kết quả khi thực hiện với bộ dữ liệu RS[15, 3]¡s, M = 10000, N = 2214, luồng dữ liệu IP

2.4. So sánh các phương pháp phát hiện nhanh Hot-IPs2.4.1. So sánh dựa trên độ phức tạp thuật toán

</div>