Chống tấn công từ chối dịch vụ phân tán tần suất thấp

  • 52 trang
  • file .pdf
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
PHẠM VĂN HỢI
CHỐNG TẤN CÔNG TỪ CHỐI DỊCH VỤ PHÂN
TÁN TẦN SUẤT THẤP
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
HÀ NỘI - 2013
1
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
PHẠM VĂN HỢI
CHỐNG TẤN CÔNG TỪ CHỐI DỊCH VỤ PHÂN
TÁN TẦN SUẤT THẤP
Ngành: Công nghệ thông tin
Chuyên ngành: Truyền dữ liệu và Mạng máy tính
Mã số: 60 48 15
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. NGUYỄN ĐẠI THỌ
HÀ NỘI - 2013
2
TÓM TẮT
Ngày nay, an ninh Internet là một mối quan tâm đặc biệt vì tất cả các hình
thức của các doanh nghiệp và truyền thông được liên kết với Internet trong dạng
này hay dạng khác, sự an toàn của các tài sản này (bao gồm cả cơ sở hạ tầng và
nội dung thông tin) là quan trọng hàng đầu. Một số hậu quả nổi tiếng của một
cuộc tấn công bao gồm tiếp cận với một mạng, trộm cắp sở hữu trí tuệ, và từ
chối dịch vụ. Hầu hết các cuộc tấn công DoS quản lý tận dụng lợi thế của những
điểm yếu trong giao thức TCP/IP. Theo truyền thống, các cuộc tấn công gửi một
số lượng lớn các gói tin giả mạo với mục tiêu tiêu hao băng thông mạng hoặc
khả năng xử lý và nạn nhân không còn có thể cung cấp dịch vụ cho người dùng
hợp pháp. Như vậy, gây ra bất thường về mặt thống kê của các thiết bị giám sát
mạng, luồng tấn công có thể phát hiện khá dễ dàng và giảm thiểu thiệt hại của
cuộc tấn công
Một phân loại mới cuộc tấn từ chối dịch vụ, được gọi là từ chối dịch vụ tần
suất thấp, sẽ là mấu chốt trong đề tài nghiên cứu này. Tần suất trung bình của
cuộc tấn công này là quá thấp nên hầu hết các router hoặc nạn nhân không phát
hiện ra các cuộc tấn công. Cuộc tấn công cố gắng để gây giảm chất lượng của
dịch vụ TCP bằng cách định kỳ gửi các vụ nổ của các gói tin để tạo ra tắc nghẽn.
Giai đoạn của luồng DoS được chọn để phù hợp với RTO (thời gian hết hạn
truyền lại) của luồng TCP để các tắc nghẽn sẽ trùng với truyền lại gói tin, dẫn
đến việc mất gói dữ liệu và thời gian chờ kết nối liên tục. Vì vậy, tần suất tấn
công tổng thể là đủ thấp để để tránh bị phát hiện. Mục đích của luận văn này
chúng tôi nghiên cứu hiện trạng các biện pháp phòng chống tấn công từ chối
dịch vụ phân tán tần suất thấp, từ đó đề xuất giải pháp mới hiệu quả hơn. Tính
hiệu quả của giải pháp mới sẽ được so sánh và đối chiếu với các giải pháp cũ
thông qua mô phỏng trên phần mềm chuyên dụng NS-2.
Từ khóa: Denial of Service, Low-Rate TCP-Targeted Denial of Service
Attacks, Shrew Attacks, TCP Congestion Control, TCP Retransmission
Timeout, Robust RED Algorithm.
i
MỤC LỤC
LỜI CẢM ƠN ............................................................... Error! Bookmark not defined.
TÓM TẮT ................................................................................................................... i
MỤC LỤC ..................................................................................................................ii
DANH MỤC HÌNH VẼ ............................................................................................ iv
DANH SÁCH THUẬT NGỮ VÀ TỪ VIẾT TẮT .................................................... v
GIỚI THIỆU .............................................................................................................. 1
Chƣơng 1 - BACKGROUND .................................................................................... 5
1.1. Điều khiển tắc nghẽn TCP............................................................................... 5
1.1.1 Các giai đoạn TCP........................................................................................ 5
1.1.2 Cơ chế Timeout TCP .................................................................................... 5
1.2. AQM (Active Queue Management) ................................................................ 9
1.2.1 Kiểm soát tắc nghẽn ..................................................................................... 9
1.2.2 Quản lý hàng đợi tích cực ........................................................................... 10
1.3 RED (Random Early Detection) .................................................................... 12
Chƣơng 2 TẤN CÔNG TỪ CHỐI DỊCH VỤ ......................................................... 15
2.1 Khái niệm tấn công từ chối dịch vụ ............................................................... 15
2.2 Cách thức chung tấn công từ chối dịch vụ .................................................... 15
2.2.1 Khai thác các điểm yếu của mục tiêu .......................................................... 15
2.2.2 Tấn công vào giao thức............................................................................... 16
2.2.3 Tấn công vào Middleware .......................................................................... 17
2.2.4 Tấn công vào ứng dụng .............................................................................. 17
2.2.5 Tấn công vào tài nguyên ............................................................................. 18
2.2.6 Pure Flooding ............................................................................................. 18
2.3 Cách thức tấn công LDoS ............................................................................... 19
2.4 Các phƣơng pháp chống tấn công LDoS ....................................................... 21
2.4.1 Cơ chế router-assisted ................................................................................ 22
2.4.2 Cơ chế End-point........................................................................................ 22
2.5 Thuật toán Robust RED (RRED) .................................................................. 23
Chƣơng 3 - ĐỀ XUẤT GIẢI PHÁP VÀ KẾT QUẢ MÔ PHỎNG ........................ 26
3.1. Nhƣợc điểm của thuật toán RRED ............................................................... 26
3.2. Ý tƣởng ........................................................................................................... 26
3.3. Phƣơng pháp .................................................................................................. 28
3.4 Kết quả mô phỏng .............................................................................................. 30
ii
3.4.1 Kịch bản mô phỏng ......................................................................................... 30
3.4.2 Kết quả biến thiên theo chu kỳ ....................................................................... 31
3.4.3 Kết quả biến thiên theo độ rộng bùng nổ tấn công.......................................... 32
3.4.4 Kết quả biến thiên theo tốc độ bùng nổ tấn công ............................................ 33
KẾT LUẬN .............................................................................................................. 36
PHỤ LỤC ................................................................................................................. 37
TÀI LIỆU THAM KHẢO ....................................................................................... 44
iii
DANH MỤC HÌNH VẼ
Hình 1. Hoạt động điều khiển tắc nghẽn TCP .............................................................. 5
Hình 2. Hoạt động của đồng hồ truyền lại TCP ............................................................ 8
Hình 3. Nguyên lý hoạt động của RED ...................................................................... 13
Hình 4. Sơ đồ loại bỏ gói tin của RED theo  ............................................................ 14
Hình 5. Mô hình tấn công DoS tần suất thấp .............................................................. 21
Hình 6. Kiến trúc của RRED...................................................................................... 24
Hình 7. Tấn công DoS theo chu kỳ với T*=1ms ........................................................ 27
Hình 8. Tấn công DoS theo chu kỳ với T*=50ms ...................................................... 27
Hình 9. Mã giả của thuật toán RRED cải tiến ............................................................. 29
Hình 11. Giao thức mạng thử nghiệm ........................................................................ 30
Hình 12. Kết quả thông lượng TCP dưới tấn công khi
Ta = [0.2, 2] (s), Tb = 200(ms), Rb = 0.25 (Mbps) ..................................................... 31
Với Ta = 1(s), Tb = [0,600](ms), Rb = 0.25(Mbps) ...................................................... 32
Hình 13. Kết quả thông lượng TCP dưới tấn công khi
Ta = 1(s), Tb = [0,600](ms), Rb = 0.25(Mbps)............................................................. 33
Hình 14. Kết quả thông lượng TCP dưới tấn công khi
Ta = 1(s), Tb = 200(ms), Rb = [0.1,0.5] (Mbps)........................................................... 34
Hình 10. Cấu trúc của NS-2 ....................................................................................... 37
iv
DANH SÁCH THUẬT NGỮ VÀ TỪ VIẾT TẮT
ACK Acknowledgement Biên nhận
AIMD Additive-increase multiplicative- Tăng cấp số cộng giảm cấp
decrease số nhân
AQM Active Queue Management Quản lý hàng đợi tích cực
DDoS Distributed Denial of Service Tấn công từ chối dịch vụ
phân tán
DoS Denial of Service Tấn công từ chối dịch vụ
FTP File transfer protocol Giao thức truyền tệp
ICMP Internet Control Message Protocol giao thức xử lý các thông báo
trạng thái cho IP
Kbps kilobit per second Kilôbit trên giây
LDoS Low-rate DoS Attack Tấn công từ chối dịch vụ tần
suất thấp
Mbps Megabit per second Mêgabit trên giây
ms Millisecond Mini giây
RED Random Early Detection Phát hiện sớm ngẫu nhiên
RRED Robust Random Early Detection Phát hiện sớm ngẫu nhiên
mạnh mẽ
RTO retransmission timeout Thời gian hết hạn truyền lại
s second giây
RTT Round-Trip Time Thời gian trễ khứ hồi
TCP Transmission Control Protocol Giao thức kiểm soát truyền
tải
v
GIỚI THIỆU
Tấn công từ chối dịch vụ đã ngày càng trở thành mối đe dọa nghiêm trọng
đối với sự tin cậy của mạng Internet. Là các cuộc tấn công sử dụng nhiều cách
thức tổ chức và thực hiện khác nhau, từ việc dùng chỉ một máy tới việc thu thập
các máy agent dưới quyền với số lượng lên đến hàng chục ngàn máy phục vụ tấn
công, mục đích của các cuộc tấn công là làm tê liệt các ứng dụng, máy chủ, toàn
bộ mạng lưới, hoặc làm gián đoạn kết nối của người dùng hợp pháp. Một kẻ tấn
công DoS gửi một số lượng lớn các gói tin đến một nạn nhân sử dụng nhiều
zombie. Như một kết quả của các cuộc tấn công, các nguồn tài nguyên xung
quanh nạn nhân như băng thông mạng và sức mạnh tính toán bị giảm và sử dụng
không thể truy cập vào các dịch vụ hợp pháp được cung cấp bởi các nạn nhân.
Ngày nay, có các biện pháp đối phó khác nhau của cuộc tấn công DoS để loại lũ
lụt thông thường đã được đề xuất. Đặc biệt, phân tích thống kê về tỷ lệ truyền tải
mạng rất hữu ích để phát hiện các gói lớn truyền tải lũ lụt.
Tấn công từ chối dịch vụ (DoS) là một nỗ lực để phá vỡ các chức năng
bình thường của hệ thống mạng và ngăn chặn truy cập hợp pháp cho các dịch vụ
hoặc đơn giản là làm giảm chất lượng của dịch vụ được cung cấp..
Một nghiên cứu tại UCSD [23] đã chỉ ra rằng ngay từ đầu thập niên này các
cuộc tấn công từ chối dịch vụ đã diễn ra với một tỷ lệ lên tới 4000 cuộc tấn công
mỗi tuần. Trong năm 2002, một cuộc tấn công từ chối dịch vụ [22] đã làm sập
tới 9 trong số 13 máy chủ DNS root của toàn thế giới.
Mức độ ảnh hưởng nghiêm trọng của các cuộc tấn công từ chối dịch vụ, mà
đặc biệt được nhắc đến nhiều nhất là tấn công từ chối dịch vụ phân tán DDoS,
đã dẫn đến một loạt các nghiên cứu nhằm hiểu rõ hơn về các cơ chế tấn công, để
đưa tới các cách thức giúp có thể phòng chống ảnh hưởng tiêu cực của nó.
Có nhiều phương pháp đã được đề xuất nhằm chống lại các cuộc tấn công
từ chối dịch vụ, từ việc lọc các gói tin để tránh giả mạo địa chỉ nguồn, chuyển
hướng tấn công, đẩy ngược luồng giao thông tấn công trở lại mạng, cách ly để
phân biệt máy khách và giao thông máy chủ. Mỗi giải pháp đó đều rất tốt, và
cung cấp kĩ thuật giúp chúng ta nhận ra các vấn đề của tấn công từ chối dịch vụ.
Tuy nhiện, các phương pháp chỉ có thể bảo vệ lại từng khía cạnh của các tấn
công từ chối dịch vụ.
Tuy nhiên, trong những năm gần đây, một lớp mới của tấn công từ chối
dịch vụ khó phát hiện bằng các phương pháp thông thường, đó là loại tấn công
từ chối dịch vụ phân tán tần suất thấp (LDoS) [2] [3]. Kẻ tấn công DoS gửi bùng
1
nổ ngắn của lưu lượng của luồng theo kỳ, thay vì lũ lụt gói liên tục như các cuộc
tấn công DoS/DDoS thông thường. Vụ nổ như vậy điền vào bộ đệm của router
trung gian và gây ra tổn thất gói của các luồng TCP hợp pháp. Những khó khăn
trong việc phát hiện các cuộc tấn công DoS là kẻ tấn công có tốc độ trung bình
thấp so với các cuộc tấn công DoS truyền thống. Hơn nữa, kẻ tấn công có thể
kiểm soát mức độ thiệt hại gây ra bởi các cuộc tấn công, bằng cách điều chỉnh
sự bùng nổ và khoảng cách giữa mỗi lần bùng nổ. Do đó, rất khó khăn cho các
nạn nhân tự tìm các cuộc tấn công. Vì vậy, nếu kẻ tấn công mục tiêu một trang
web thương mại điện tử và kết nối TCP giữa các trang web và khách hàng của
mình, trang web có thể bỏ lỡ những lợi nhuận tiềm năng và khách hàng mới.
Cho đến nay, các cuộc tấn công DoS là một trong những mối đe dọa lớn
nhất đối với an ninh mạng do là dễ thực hiện với chi phí thấp. Mặt khác, phát
hiện tấn công DoS tần suất thấp là khó khăn hơn vì tốc độ trung bình thấp. Các
thuật toán phát hiện cho tấn công DoS lũ lụt dường như không áp dụng cho các
cuộc tấn công DoS tần suất thấp. Vì vậy, nó rất có thể là cuộc tấn công DoS tần
suất thấp sẽ là cuộc tấn công chính trong tương lai.
Để phát hiện các cuộc tấn công và giảm thiểu thiệt hại, biện pháp đối phó
khác nhau đã được đề xuất. Phương pháp chính ở thời điểm hiện tại cố gắng
phát hiện và lọc các cuộc tấn công vào một bộ định tuyến trung gian. Tuy nhiên,
tất cả các phương pháp tiếp cận dựa trên bộ định tuyến có vấn đề triển khai.
Luận văn của tôi trình bày một phương pháp chống tấn công từ chối dịch vụ
phân tán tần suất thấp. Bằng cách phân tích các luồng đến dựa trên các thuật
toán cơ bản của router. Hệ thống sẽ nhận diện các luồng tấn công DoS hoặc các
luồng hợp pháp.
Với các cuộc tấn công DoS truyền thống, những kẻ tấn công sử dụng một
số lượng lớn các máy bị xâm nhập hoặc các đại lý và gửi điện cao tỷ lệ các gói
dữ liệu đến nút nạn nhân. Có khả năng mạnh mẽ nhưng có khả năng rất có hại
mà bản chất cao tỷ lệ các cuộc tấn công như vậy có thể được phát hiện bởi thiết
bị giám sát mạng vì số liệu thống kê bất thường. Vì vậy, những kẻ tấn công có
thể được xác định và ảnh hưởng của các cuộc tấn công được giảm thiểu. Khi bị
tấn công bởi các cuộc tấn công tràn ngập, giao thông của các mạng được tiêu thụ
khá cao và máy chủ vào trạng thái bận. Với các tấn công DoS tần suất thấp, các
nút trong mạng bị lừa dối với tín hiệu bận và để điều chỉnh trạng thái hệ thống
của nó và sau đó luồng trở nên tương đối rỗng. Các máy chủ sẽ được rỗi trong
các cuộc tấn công, kết quả là mạng có thể bị tấn công trong một thời gian dài mà
người dùng không nhận biết được.
2
Tuy nhiên, tấn công DoS tần suất thấp khai thác khoảng thời gian chậm
hơn của đồng hồ truyền lại TCP để làm giảm thông lượng TCP. Mục đích của nó
là để phá vỡ sự cân bằng của dịch vụ mạng hơn là để chiếm dịch vụ. Với tốc độ
trung bình của gói thấp, rất khó cho mạng lưới giám sát để phát hiện ra những sự
kiện đặc biệt và đó là lý do chính tại sao tấn công DoS tần suất thấp rất dễ dàng
để thoát khỏi phát hiện.
Gần đây một phương pháp chống tấn công từ chối dịch vụ phân tán tần suất
thấp được cho thấy khá hiệu quả trong việc lọc các gói tin tấn công và cho qua
các gói tin hợp pháp. Thuật toán mới hơn RED đã được đề xuất để phát hiện và
lọc ra các cuộc tấn công LDoS. Thuật toán này sẽ giúp trong việc tìm ra nguồn
gốc của các tấn công LDoS và làm gián đoạn luồng tấn công từ hệ thống. Mục
tiêu của thuật toán đề xuất là xác định và loại bỏ các luồng tấn công trước khi
vào thuật toán truyền thống RED. Công việc tương tự đã được thực hiện trong
thuật toán RRED [1]. Bằng một tập hợp các thí nghiệm khác nhau, thuật toán
RRED được chứng minh là mạnh mẽ chống lại các cuộc tấn công LDoS và duy
trì thông lượng TCP ổn định. Tuy nhiên, thuật toán xác định một khoảng thời
gian cố định tính từ thời điểm gói tin bị loại nghi ngờ là gói tin tấn công. Thời
gian cố định có thể bị kẻ tấn công xác định và bỏ qua. Do đó, một luồng là một
luồng tấn công nếu các gói tin đến từ luồng này được gửi trong một khoảng thời
gian sau khi một gói tin khác trong cùng một luồng bị loại bỏ. Khi một gói tin
đến nghi ngờ là gói tin tấn công phụ thuộc vào khoảng thời gian xác định trong
RRED là T*=10ms. Kẻ tấn công có thể dự đoán được giá trị hằng số này khi khi
đưa các gói tin tấn công và như vậy rất có khả năng kẻ tấn công có thể điều
chỉnh thời gian đến của gói tin tấn công sao cho RRED không dễ dàng phát hiện
và nguy cơ tiềm ẩn tấn công LDoS vẫn là cao.
Vì nhược điểm này, chúng tôi đề xuất cải tiến thay đổi giá trị biến thiên của
trong khoảng thời gian trên để xác định loại bỏ gói tin là gói tin tấn công và cho
đi qua hầu hết gói tin bình thường. Bằng cách cải tiến giá trị hằng số T* của
thuật toán RRED trên là một giá trị thời gian Tout động. Khi phát hiện mất gói tin
tại một luồng mà nghi ngờ là gói tin tấn công, người gửi sẽ chờ hết thời gian
timeout để tiếp tục gửi lại, trong khoảng thời gian Tout tính từ thời điểm gói tin bị
loại bỏ đến khi gói tin được phát tiếp theo nghi ngờ là gói tin tấn công (được
trình bày chi tiết trong chương 4).
Qua mô phỏng trong NS2 và phân tích cho thấy RRED sau khi cải tiến là
tương đối hiệu quả và có khả năng cải thiện hiệu suất TCP đáng kể trong các
cuộc tấn công DoS tần suất thấp so với thuật toán RRED ban đầu.
3
Phần tiếp theo của luận văn được tổ chức như sau:
Chương 2: Background
Trình bay tổng quan về TCP, kiểm soát tắc nghẽn TCP, tiếp theo trình bày
quản lý hàng đợi tích cực (AQM) và cuối cùng là trình bày thuật toán RED.
Chương 3: Tấn công từ chối dịch vụ.
Trong chương này trình bày khái niệm về tấn công từ chối dịch vụ, cách
thức chung tấn công từ chối dịch vụ. Tiếp theo là trình bày cách thức tấn công từ
chối dịch vụ tần suất thấp. Các phương pháp chống tấn công từ chối dịch vụ tần
suất thấp và cuối cùng tập trung một thuật toán chống tấn công từ chối dịch vụ
tần suất thấp là RRED.
Chương 4: Phương pháp cải tiến đề xuất.
Trong chương này trình bày về ý tưởng cải tiến thuật toán RRED, phân tích
nhược điểm của RRED, khai thác nhược điểm để từ đó đề xuất phương pháp cải
tiến. Tiếp theo trình bày mã giả của thuật toán và cuối cùng là bình luận phương
pháp cải tiến
Chương 5: Kết quả mô phỏng
Chương này trình bày kịch bản mô phỏng, kết quả biến thiên theo chu kỳ
tấn công, theo độ rộng tấn công và tốc độ tấn công. Trong chương này, chúng tôi
cũng so sánh phương pháp cải tiến của chúng tôi so với thuật toán RRED.
Phần cuối cùng là kết luận và hướng nghiên cứu trong tương lai.
4
Chƣơng 1 - BACKGROUND
1.1. Điều khiển tắc nghẽn TCP
Phần này cung cấp đánh giá điều khiển tắc nghẽn TCP. Đầu tiên giải thích
cơ bản của giai đoạn điều khiển truyền tải và sau đó thảo luận ngắn về lớp giao
thức điều khiển tắc nghẽn chậm mà có liên quan đến công việc được trình bay
trong mục 3.4. Tiếp theo, trình bày cơ bản về cơ chế thời gian hết hạn truyền lại
(RTO) mà là nguồn gốc của việc dễ bị tấn công trong tấn công DoS tần suất
thấp.
1.1.1 Các giai đoạn TCP
Hình 1 biểu diễn thời gian cửa sổ tắc nghẽn TCP hoạt động tại các giai
đoạn khác nhau với các điểm trên đỉnh là gói tin mất. Dữ liệu truyền tải bắt đầu
với giai đoạn khởi động chậm (slow-start) trong TCP tăng nó gửi tóc độ đơn vị
hàm mũ nó đếm gói tin mất đầu tien hoặc kích thức cửa sổ lớn nhất. Từ điểm
này, TCP vào giai đoạn tránh tắc nghẽn (congestion-avoidance) và sử dụng
chính sách tăng cấp số cộng giảm cấp số nhân AIMD để tránh tắc nghẽn. Mất
gói được phát hiện qua thời gian hết hạn từ không nhận được biên nhận hoặc
nhận được 3 biên nhận. Nếu mất gói xuất hiện và ít hơn 3 gói tin ACK trùng lặp
nhận được, TCP giảm cửa sổ tắc nghẽn tới một phân đoạn và đợi giai đoạn của
thời gian hết hạn phát lại (RTO), sau đó gói tin được gửi lại. Trong trường hợp
khác thời gian hết hạn xuất hiện trước khi gửi lại thành công gói tin, TCP vào
giai đoạn rút lui theo hàm mũ (exponential-backoff) và nhân đôi RTO cho đến
khi gói tin được biên nhận thành công.
Hình 1. Hoạt động điều khiển tắc nghẽn TCP
1.1.2 Cơ chế Timeout TCP
5
[16] TCP áp dụng một số cơ chế để đạt được hiệu suất cao và một trong
những khía cạnh quan trọng là điều khiển tắc nghẽn. Tùy thuộc vào mức độ tắc
nghẽn, nó có thể thực hiện trong hai khoảng thời gian. Vào khoảng thời gian nhỏ
hơn của thời gian trễ khứ hồi (RTT- Round Trip Times), TCP thực hiện điều
khiển tăng cấp số cộng giảm cấp số nhân (AIMD – Additive Increase
Multiplicative Decrease) nhằm buộc mỗi luồng truyền tải với tốc độ hợp lý của
liên kết nút cổ chai. Khi thời điểm tắc nghẽn nghiêm trọng, TCP sẽ hoạt động
trên khoảng thời gian dài hơn là thời gian hết hạn phát lại gói tin (RTO –
Retransmission Ttime Out), mà tấn công DoS tần suất thấp cố gắng để khai thác.
Cơ chế điều khiển tắc nghẽn TCP áp dụng khái niệm về cửa sổ tắc nghẽn
(CWnd). Mỗi người gửi TCP sẽ sử dụng cửa sổ tắc nghẽn để tính toán cửa số
truyền dựa trên những phản hồi nhận được từ mạng. Cơ chế này giúp tránh tình
trạng tắc nghẽn vì cả hai khả năng của người nhận và các đặc tính mạng được
đưa vào tài khoản của người gửi.
Để giải quyết với sự tắc nghẽn tạm thời, khi TCP nhận ba ACK trùng lặp
cho một gói tin, nó sử dụng cơ chế truyền lại nhanh chóng (fast-retransmit).
Trong trường hợp tắc nghẽn nặng, khi ba ACK trùng lặp không thể với tới người
gửi, cơ chế thời gian chờ được kích hoạt, có nghĩa rằng một gói tin không được
công nhận mặc mặc dù thời gian của RTO đã hết hạn.
TCP phát hiện mất gói tin thông qua thời gian hết hạn (timeout) từ không
nhận được gói tin ACK, hoặc nhận được ba bản sao ACK. Nếu mất gói tin xảy
ra và ít hơn ba ACK trùng lặp được nhận, TCP chờ đợi trong một khoảng thời
gian chờ truyền lại hết hạn, làm giảm cửa sổ tắc nghẽn một gói tin và gửi lại gói
tin.
Lựa chọn giá trị thời gian chờ đòi hỏi một sự cân bằng: nếu quá thấp,
truyền lại giả sẽ xảy ra khi các gói tin là không chính xác giả bị mất khi trong
thực tế, dữ liệu hoặc ACK chỉ đơn thuần bị trì hoãn. Tương tự như vậy, nếu đặt
quá cao, luồng sẽ chờ đợi lâu không cần thiết để suy luận và phục hồi từ tình
trạng tắc nghẽn.
Để giải quyết các yếu tố đầu, Allman và Paxson thực nghiệm cho thấy rằng
TCP đạt thông lượng gần như tối đa nếu có tồn tại một cận dưới với RTO của
một giây [2]. Trong khi có khả năng duy trì với các luồng small-RTT, nghiên
cứu phát hiện ra rằng tất cả các luồng nên có giá trị thời gian chờ ít nhất 1 giây
để đảm bảo tình trạng tắc nghẽn mà được xóa bỏ, từ đó đạt được hiệu suất tốt
nhất.
6
Để giải quyết các yếu tố thứ hai, bên gửi TCP duy trì hai biến trạng thái,
SRTT (smoothed round-trip time) và RTTVAR (round-trip time variation). Theo
[32], các quy định về việc tính toán SRTT, RTTVAR, và RTO như dưới đây.
Cho đến khi một phép đo RTT đã được thực hiện đối với các gói tin được gửi
giữa bên gửi và bên nhận, bên gửi đặt RTO đến ba giây.
Khi đo RTT lần đầu tiên là R’, hệ thống thiết lập SRTT=R’,
RTTVAR=R’/2 và RTO = SRTT + max(G,4RTTVAR), ở đây G biểu thị xung
đồng hồ (≤ 100 ms). Khi RTT sau đo R’ hệ thống thiết lập:
RTTVAR = (1 − β)RTTVAR + β |SRTT – R|

SRTT = (1 − α)SRTT + α R
ở đây α = 1/8 và β = 1/4, chú thích trong [17].
Như vậy, kết hợp hai phần, bên gửi TCP thiết lập giá trị của RTO như sau:
RTO = max(minRT O, SRT T + max(G,4RTTVAR)).
Trong công thức trên:
 RTO: (thời gian hết giờ để phát lại) là khoảng thời gian Router sẽ truyền
lại gói tin nếu không nhận được phản hồi. Thời gian này phải lớn hơn
RTT để đủ thời gian cho gói tin đến bên nhận và gói tin Ack từ bên nhận
gửi về.
 RTT: là thời gian trễ khứ hồi đo được đối với gói tin được biên nhận mới
nhất.
 RTTVAR: giá trị biến thiên của round-trip time (RTT)
 SRTT: ước lượng thời gian trễ khứ hồi được làm trơn, được cập nhật mỗi
khi có một gói tin được biên nhận.
7
Retransmission Timer
2s
2 s - RTT
Multiplicative
Exponentioal
decrease
backoff
1s
1 s - RTT
Pa
ck
ag
e
Lo
0 s s 1 s+ 2RTT
Time
1s
Hình 2. Hoạt động của đồng hồ truyền lại TCP
Minh họa quản lý RTO qua trục thời retransmission-timer (đồng hồ phát
lại) trong Hình 2 như sau. Giả sử một gói tin với số thứ tự n được gửi bởi bên
gửi TCP tại tham chiếu thời gian t = 0, và đồng hồ phát lại 1 giây được khởi tạo
khi truyền tải. Nếu gói n bị mất và ít hơn ba bản sao ACK nhận được của bên
gửi, luồng "hết thời gian" khi thời gian kết thúc tại thời điểm t = 1 giây. Tại thời
điểm này, bên gửi đi vào giai đoạn rút lui theo hàm mũ: nó làm giảm cửa sổ tắc
nghẽn một, tăng gấp đôi giá trị RTO đến 2 giây theo thuật toán Karn của [21],
truyền lại gói tin không được biên nhận với số thứ tự n, và thiết lập lại đồng hồ
phát lại với giá trị RTO mới này. Nếu gói dữ liệu bị mất một lần nữa (không thể
hiện trong Hình 2), tiếp tục rút lui theo hàm mũ như bên gửi chờ đợi 2 giây dài
đồng hồ truyền lại đến hết hạn. Tại t = 3 giây, bên gửi lại áp dụng thuật toán của
Karn, tăng gấp đôi giá trị RTO đến 4 giây và lặp đi lặp lại quá trình này.
Ngược lại nếu gói tin n là thành công phát lại tại thời điểm t = 1 giây như
được minh họa trong Hình 2, ACK của nó sẽ đến cho bên gửi tại thời điểm t = 1
+ RTT. Tại thời điểm này, bên gửi TCP thoát khỏi giai đoạn rút lui theo hàm mũ
và đi vào khởi đầu chậm (slow start), tăng gấp đôi kích thước cửa sổ đến hai,
truyền hai gói mới n + 1 và n + 2, và đặt lại đồng hồ truyền lại với các giá trị
RTO hiện tại của 2 giây. Nếu hai gói dữ liệu không bị mất, chúng được nhận tại
thời điểm t = 1 + 2 RTT, và SRTT, RTTVAR và RTO được tính toán lại như mô
tả ở trên. Với điều kiện là minRTO > SRTT + max(G, 4 RTTVAR), RTO một
lần nữa thiết lập 1 giây. Như vậy, trong trường hợp này, trong đó xuất hiện thời
8
gian chờ nhưng không rút lui theo hàm mũ, giá trị của RTO lệch không quá RTT
từ minRTO cho t > minRTO + 2 RTT.
Tóm lại, khi tắc nghẽn nặng, TCP giảm cửa sổ tắc nghẽn xuống còn 1 phân
đoạn và giá trị của RTO được thiết lập ở giá trị tối thiểu (minRTO). Theo RFC-
2988[6], giá trị tối thiểu được đề nghị cho minRTO là 1 giây.
Nếu RTO hết hạn và các gói tin bị bỏ lỡ một lần nữa, rút lui theo hàm mũ
tiếp tục và người gửi sẽ tăng gấp đôi giá trị của RTO (từ 1 giây đến 2 giây) và
truyền lại các gói tin. Sau đó bên gửi đợi cho đến 2 giây RTO hết hạn, nếu gói
tin vẫn chưa được gửi đi thành công rút lui theo hàm mũ tiếp tục (RTO được
thiết lập để 4 giây và vv). Cơ chế này đã được lựa chọn để đối phó với các
trường hợp tắc nghẽn nghiêm trọng vì nó là hành vi bên gửi bảo thủ nhất.
Cơ chế thời gian chờ TCP là rất thích hợp để đối phó với tình trạng tắc
nghẽn cao, tuy nhiên, nó cũng có những rủi ro tiềm năng vì một sai lầm cơ bản.
Dựa trên cơ chế này, các giá trị được xác định trước của RTO là hằng số. Giá trị
tối thiểu là 1 giây và trong rút lui theo hàm mũ, nó có thể nhận được những giá
trị mà là bội số của 1 giây. Do tính năng này của thuật toán, kẻ tấn công có thể
tấn công hệ thống bằng cách sử dụng bùng nổ tốc độ cao trong thời gian ngắn
của gói tin để điền vào bộ đệm nút cổ chai, ngay trước khi RTO hết hạn. Nếu kẻ
tấn công biết thời gian của người gửi có thể thực hiện tấn công "sóng vuông"
(tốc độ cao, bùng nổ thời gian ngắn) và liên tục đưa người gửi vào tình trạng
thời gian chờ phát lại trong khi thông lượng của máy chủ là xấp xỉ bằng số
không.
1.2. AQM (Active Queue Management)
Phần này chúng tôi mô tả các loại khác nhau của cơ chế điều khiển tắc
nghẽn thường được sử dụng trong Internet với sự nhấn mạnh trên các thuật toán
của cơ chế AQM.
1.2.1 Kiểm soát tắc nghẽn
Mục tiêu của điều khiển tắc nghẽn là để đạt được hiệu quả tức là sử dụng
kích thước hàng đợi tối đa, tối thiểu và gói loại bỏ tối thiểu trong khi cho phép
truy cập công bằng cho tất cả các nguồn. Có chủ yếu là hai cách tiếp cận để điều
khiển tắc nghẽn - điều khiển tắc nghẽn hệ thống đầu cuối và điều khiển tắc
nghẽn mạng lưới trung tâm.
Điều khiển tắc nghẽn hệ thống đầu cuối, người gửi phát hiện sự tắc nghẽn
và phản ứng với nó cho phù hợp. TCP là một ví dụ quan trọng của phương pháp
9
này. Khi một gói được loại bỏ, người gửi giả định rằng tình trạng tắc nghẽn đã
xảy ra và giảm tốc độ gửi. Khi một gói được truyền thành công, người gửi tăng
tốc độ gửi.
Phương pháp thứ hai là điều khiển tắc nghẽn mạng lưới trung tâm. Ý tưởng
của phương pháp này là khi các bộ định tuyến có nhiều thông tin về trạng thái
của mạng, họ có thể phát hiện ùn tắc và nên tham gia vào các quyết định của
điều khiển tắc nghẽn. Bộ định tuyến thực sự đo mức độ ùn tắc giao thông bằng
cách so sánh khả năng đầu vào và bằng cách dựa vào kích thước hàng đợi, do
đó, họ có thể gửi thông tin phản hồi ngay sau khi họ nhận thấy chiều dài hàng
đợi đang gia tăng. Vì vậy, chiều dài hàng đợi trung bình không phải là lớn như
trong cách tiếp cận trước. Bộ định tuyến cũng có thể được sử dụng để ưu tiên
cho một số nguồn so với những điều kiện khác. Một ví dụ quan trọng của điều
khiển tắc nghẽn mạng lưới trung tâm là quản lý xếp hàng đăng nhập.
1.2.2 Quản lý hàng đợi tích cực
Quản lý hàng đợi tích cực (AQM) là một cơ chế phát hiện sự tắc nghẽn
trong hệ thống mạng. Những giải thuật quản lý hàng đợi tích cực chạy bên trong
những bộ định tuyến và phát hiện sự tắc nghẽn phôi thai điển hính bằng cách
theo dõi chiều dài hàng đợi tức thời hay chiều dài hàng đợi trung bình. Khi kích
thước hàng đợi trung bình vượt quá một ngưỡng nhất định nhưng vẫn còn ít hơn
khả năng xử lý của hàng đợi, những giải thuật quản lý hàng đợi tích cực xem xét
sự tắc nghẽn trên mối liên kết và thông báo trở lại cho những hệ thống bằng
cách thả một số gói tin chuyển đến bộ định tuyến. Các giải thuật AQM có thể
cũng đặt một bit vào header của một gói tin nào đó rồi chuyển nó về phía thiết bị
nhận của gói đó sau khi sự tắc nghẽn được phát hiện. Khi thiết bị thu nhận được
gói tin đã được đánh dấu này, nó sẽ gửi trở lại bên phát gói tin đó một bit khác
trong phiên làm việc giữa nó và bên phát. Khi bên phát nhận được tín hiệu này,
nó sẽ giảm bớt tín hiệu truyền dữ liệu. Quá trình đặt một bit đặc biệt trong
header của gói tin bởi những giải thuật AQM và việc chuyển gói tin đã được
đánh dấu đó đến bên nhận gọi là sự đánh dấu (mark). Gói tin chứa bit đặc biệt
trong quá trình trên gọi là gói tin được đánh dấu. Những hệ thống trải qua việc
bị đánh dấu hoặc bị mất mát gói tin sẽ giảm nhịp độ truyền dữ liệu để giải tỏa sự
tắc nghẽn và ngăn việc tràn hàng đợi.
Mục tiêu quan trọng nhất của các giải thuật AQM là ngăn ngừa sự tắc
nghẽn trước khi nó thực sự xuất hiện. Như vậy, việc sử dụng hiệu quả các giải
thuật quản lý hàng đợi sẽ đem lại những hiệu quả đó là: giảm bớt sự mất mát các
10
gói tin, đạt được một lưu lượng truyền dữ liệu cao và một độ trễ hàng đợi thấp.
Điều này thật sự là một cải thiện rất tốt cho những ứng dụng tương tác như
duyệt Web hay các cuộc hội thoại trực tiếp.
Một mục tiêu quan trọng khác của quản lý hàng đợi tích cực là quản lý tắc
nghẽn với yêu cầu ngăn ngừa sự đồng bộ hóa toàn cục bằng sự ngẫu nhiên trong
quyết định đánh dấu hay loại bỏ gói tin. Khi một sự tắc nghẽn được nghi ngờ
trên một mối liên kết nào đó, đa số những giải thuật quản lý hàng đợi không
đánh dấu hay loại bỏ gói tin một cách tất định mà là ngẫu nhiên. Xác suất đánh
dấu hay loại bỏ của một gói tin được chuyển đến thông thường phụ thuộc vào độ
ước tính của sự tắc nghẽn trên một mối liên kết.
Trong phần này chúng tôi trình bày một vài thuật toán quan trọng AQM
đang được đề xuất trong thập kỷ qua. Việc thực hiện các cơ chế điều khiển tắc
nghẽn TCP trong mạng lưới đó thực hiện thả đuôi (drop-tail) loại bỏ gói có một
số hạn chế, chẳng hạn như đồng bộ hóa luồng, phân phối không công bằng mất
gói tin giữa các luồng, và sử dụng ít tài nguyên mạng. Vì vậy, ngay cả với hệ
thống đầu cuối được trang bị các thuật toán quan trọng như các cơ chế tránh tắc
nghẽn TCP, khởi đầu chậm (slow start), truyền lại nhanh (fast retransmit), và
phục hồi nhanh (fast recovery), việc thực hiện các thuật toán điều khiển tắc
nghẽn TCP trên mạng drop-tail hiện tại có thể vẫn không đạt yêu cầu. Quản lý
hàng đợi tích cực đã được khuyến cáo của Internet Engineering Task Force
(IETF) như một cách để giảm thiểu những hạn chế hoạt động nêu trên của giao
thức TCP trên mạng drop-tail. Phát hiện sớm ngẫu nhiên (RED) [19] là một
thuật toán quản lý hàng đợi tích cực đầu tiên đề xuất cho việc triển khai trong
mạng TCP/IP. Ý tưởng cơ bản thuật toán quản lý hàng đợi tích cực là để truyền
đạt thông báo tắc nghẽn sớm tới các giao thức TCP điểm cuối (end-point) để họ
có thể làm giảm tốc độ truyền trước khi hàng đợi tràn và xảy ra liên tục mất gói
tin. Ngày nay được chấp nhận rộng rãi là RED kiểm soát hàng đợi thực hiện tốt
hơn so với một hàng đợi thả đuôi (drop-tail). Tuy nhiên, RED có một số vấn đề
điều chỉnh tham số cần phải được giải quyết một cách cẩn thận để cung cấp cho
hiệu suất tốt theo các kịch bản mạng khác nhau. Kết quả là một số thuật toán,
như BLUE [29] và Stabilized RED (SRED) [28], đã được phát triển nhằm thay
thế cho RED. Mặc dù các thuật toán cũng kiểm soát tắc nghẽn bằng cách loại bỏ
các gói tin với một tải trọng phụ thuộc vào khả năng bất cứ khi nào một hàng
đợi trong mạng dường như tắc nghẽn, chúng được thiết kế với mục tiêu duy trì
hàng đợi mạng ổn định, do đó giảm thiểu sự xuất hiện của hàng đợi tràn luồng.
Tuy nhiên, không giống như SRED và BLUE, thuật toán quản lý hàng đợi tích
11
cực mới này sử dụng một điều khiển phản hồi đơn giản tiếp cận để tính toán xác
suất thả được sử dụng để loại bỏ các gói trong thời gian tắc nghẽn hàng đợi.
Mặc dù các thuật toán AQM là rất mạnh mẽ với các điều kiện mạng khác
nhau, hầu hết trong số chúng đã được thiết kế mà không xem xét mạnh mẽ của
họ chống lại các cuộc tấn công mạng, chẳng hạn như các công từ chối dịch vụ
(DoS) cuộc tấn công đã được xác định như một mối đe dọa lớn các dịch vụ
Internet ngày nay. Các cuộc tấn công DoS ví dụ bao gồm TCP cuộc tấn công
SYN, quảng bá trực tiếp ICMP và các cuộc tấn công lũ DNS. Những cuộc tấn
công thường tạo ra truyền tốc độ cao của các gói dữ liệu tới nút nạn nhân. Gần
đây, một loại mới của tấn công DoS, tấn công DoS tần suất thấp, đã được đề
xuất trong khai thác TCP cơ chế thời gian hết hạn truyền lại để giảm thông
lượng TCP mà không bị phát hiện (chúng ta sẽ nghiên cứu tấn công DoS tần
suất thấp kỹ trong chương 3). So với tấn công lũ lụt dựa truyền thống DoS, tấn
công DoS tần suất thấp không sử dụng một phương pháp tiếp cận "búa tạ" của
truyền tải các gói tin tần suất cao, và do đó dễ bị phát hiện. Các thuật toán thuộc
họ RED thực sự dễ bị tấn công DoS tần suất thấp.
1.3 RED (Random Early Detection)
Chúng tôi nghiên cứu và đánh giá họ RED AQM với một số lý do: Thứ
nhất, với RED, DRED, và BLUE không sử dụng đúng các hàng đợi trung bình
để tính toán tắc nghẽn, chúng có mục tiêu hiệu suất tương tự như của họ RED
AQM. Thứ hai, từ khi cơ chế kiểm soát tắc nghẽn RED được biết đến và thường
được sử dụng như một chuẩn mực để đánh giá các cơ chế AQM khác, tiếp tục
mở rộng sự hiểu biết về cơ chế họ RED và minh họa kết quả có thể của RED sẽ
giúp các nhà nghiên cứu thiết kế các thí nghiệm tương đối so sánh RED với cơ
chế AQM khác. Thứ ba, với sự giúp đỡ của một sửa đổi chung, nó rất dễ dàng
cấu hình họ RED AQM để tạo ra kịch bản thử nghiệm khác nhau cho thấy vấn
đề kiểm soát tắc nghẽn AQM thú vị. Cuối cùng, vì RED đã được thực hiện trong
một số bộ định tuyến thương mại, RED tối ưu có thể được sử dụng để điều chỉnh
các thiết bị định tuyến.
Thuật toán RED lần đầu đã được mô tả và phân tích bởi Floyd và Jacobson
trong [25]. Ý tưởng chính của thuật toán này là nó bắt đầu bỏ các gói dữ liệu
ngẫu nhiên trước khi đệm được đầy đủ. Do đó, nó buộc các kết nối để quay trở
lại trước khi bộ đệm đầy và nhiều gói được loại bỏ. Thuật toán RED được thực
hiện trong các bộ định tuyến để giúp quản lý không gian đệm trong hàng đợi. Nó
đã được phát triển để được phối hợp sử dụng với giao thức TCP để cảnh báo về
tắc nghẽn tiềm năng trước. RED nguyên tắc là để thả ngẫu nhiên một vài gói tin
12
trước khi một bộ đệm được thực sự quá tải. Khi nguồn TCP phát hiện những tổn
thất này, họ có thể chậm lại tốc độ truyền của họ (tin rằng mạng tắc nghẽn). Như
vậy, tình trạng tắc nghẽn thực có thể tránh được.
RED chứa hai module: module dự báo tắc nghẽn và module hiện trạng loại
bỏ gói tin. Đây là 2 thành phần trung tâm của RED.
Chức năng chính của module dự báo tắc nghẽn là làm thế nào để ước lượng
được hay đánh giá được hành vi của lưu lượng trong bộ đệm theo thời gian và
phát hiện khả năng tắc nghẽn. Cách tiếp cận đơn giản nhất là dựa vào chiều dài
hàng đợi (N) và xác định trạng thái tắc nghẽn dựa trên cơ sở hàng đợi bị đầy hay
không bằng cách so sánh với kích thước bộ đệm hàng đợi (B). Một phương pháp
khác được sử dụng để dự đoán tắc nghẽn dựa trên thuật toán thời gian trung bình
của hàng đợi, đầu ra của module dự đoán tắc nghẽn là chiều dài hàng đợi trung
bình trọng số (ηN). Gọi α là phần trăm bộ đệm bị đầy và được tính theo công
thức sau: α= ηN/B.
Chức năng chính của module hiện trạng loại bỏ gói tin là đưa ra ngưỡng
khống chế αmin, αmax từ đó đánh dấu hoặc loại bỏ gói tin theo hàm xác suất p.
Module dự đoán tắc nghẽn Module hiện trạng loại bỏ gói tin
% bộ đềm đầy
(α) Xác suất loại bỏ gói tin
()
Chiều dài
hàng đợi (N)
Loại bỏ gói tin
Gói tin đi vào Gói tin đi ra
Chiều dài hàng đợi – N
Kích thước bộ đệm – B
Gói tin loại bỏ
ngẫu nhiên
Hình 3. Nguyên lý hoạt động của RED
Thuật toán RED làm việc với hai ngưỡng đại diện cho một số lượng nhất
định các gói dữ liệu được lưu trữ trong bộ đệm. Trong khi số lượng các gói được
thêm vào cuối hàng đợi không vượt quá ngưỡng đầu tiên, tất cả các gói được
chuyển tiếp. Khi số lượng các gói tin thái quá ngưỡng đầu tiên nhưng không
13