Đề xuất cấu trúc cây phát hiện xung đột trong tập luật của tường lửa

Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
Đề xuất cấu trúc cây phát hiện xung đột
trong tập luật của tường lửa
Nguyễn Mạnh Hùng1, Vũ Duy Nhất2
1Phòng Sau đại học, Học viện Kỹ thuật Quân sự
2Cục Cơ yếu, Bộ Tổng tham mưu
Tác giả liên hệ: Vũ Duy Nhất, nhatbest@gmail.com
Ngày nhận bài: 31/05/2017, ngày sửa chữa: 11/04/2018, ngày duyệt đăng: 25/12/2018
Xem sớm trực tuyến: 28/12/2018, định danh DOI: 10.32913/rd-ict.vol3.no40.478
Biên tập lĩnh vực điều phối phản biện và quyết định nhận đăng: PGS. TS. Nguyễn Khánh Văn
Tóm tắt: Tường lửa là một thiết bị bảo mật mạng, trong đó sử dụng tập luật để kiểm soát các gói tin đi qua thiết bị. Cấu
hình các luật tường lửa là nhiệm vụ rất khó khăn ngay cả đối với các chuyên gia bảo mật, đặc biệt đối với các hệ thống
mạng phức tạp. Sai sót trong quá trình cấu hình thiết bị sẽ tác động tới hai khía cạnh: (i) làm ảnh hưởng tới sự an toàn
của hệ thống mạng cần được bảo vệ và (ii) làm suy giảm năng lực xử lý của thiết bị tường lửa. Bài báo này đề xuất cấu
trúc cây phát hiện xung đột (CDT: Conflict Detection Tree) có khả năng phát hiện tất cả các loại xung đột trong một tập
luật của tường lửa một cách hiệu quả. Tính chính xác và tính hiệu quả của cấu trúc CDT được giới thiệu và chứng minh
chi tiết trong bài báo. Cấu trúc CDT được triển khai và kiểm chứng với dữ liệu thực tế, cho thấy tính khả dụng của nó.
Từ khóa: Tường lửa, an ninh mạng, tiền tố, xung đột, chính sách an ninh.
Title: A New Conflict Detection Tree Structure in the Firewall Rule Set
Abstract: Firewall is a network security device that uses rules to control incoming and outgoing network traffic. Configuring
firewall rules is a very difficult task even for network security experts, especially for complex networks. Mistakes
made in the configuration process will cause two damaging effects: (i) affecting the security of the network that needs
protection, and (ii) reducing the performance of the firewall device. This article will introduce a Conflict Detection
Tree (CDT) structure that effectively detects all conflicts in a firewall rule set. The accuracy and effectiveness of the
CDT structure is presented and substantiated in the article. The proposed CDT structure has been implemented and
tested with real data.
Keywords: Firewall, network security, firewall rules, conflict, security policy.
I. GIỚI THIỆU
Tường lửa là một trong các loại thiết bị không thể thiếu
trong việc bảo đảm an ninh và an toàn cho các hệ thống
mạng. Thiết bị này có chức năng ngăn cách và bảo vệ cho
một mạng nội bộ của một đơn vị hay một tổ chức với các
mạng công cộng hay mạng của các tổ chức khác. Các gói
tin khi đi qua tường lửa được kiểm soát theo cả chiều vào
và chiều ra. Mỗi thiết bị tường lửa được trang bị một chính
sách an ninh cho mục đích kiểm soát các gói tin nêu trên.
Chính sách an ninh này tồn tại trên thiết bị tường lửa dưới
dạng một tập luật do người quản trị thiết lập. Mỗi luật trong
tập luật gồm các giá trị điều kiện của các trường thông tin
trong header của gói tin cần thỏa mãn, và một trường quan
trọng là hành động của luật đó đối với gói tin thỏa mãn.
Hành động này có thể là một trong hai giá trị: Accept (cho
phép gói tin đi qua) hoặc Deny (không cho phép gói tin
đi qua).
Một tập luật có thể được xây dựng bởi một người quản
trị khi triển khai thiết bị và nó có thể được bổ sung hay
xóa bỏ các luật ngay khi có sự thay đổi về chính sách an
ninh trong quá trình vận hành hệ thống. Số lượng các luật
trong tập luật tỷ lệ thuận với độ phức tạp của chính sách
an ninh được triển khai trên thiết bị. Trong thực tế hiện
nay, với việc phát triển mạnh mẽ về quy mô hệ thống và
về số lượng các loại hình dịch vụ triển khai, chính sách an
ninh cần được triển khai trên các thiết bị tường lửa ngày
càng phức tạp. Điều này cũng đồng nghĩa với việc tập luật
trong chính sách an ninh mà người quản trị phải triển khai
ngày càng tăng lên về số lượng luật và phức tạp về cấu
trúc. Nhiệm vụ xây dựng và quản lý chính sách an ninh
cho tường lửa trở nên khó khăn hơn.
Các luật trong tập luật có thể xung đột lẫn nhau như
dư thừa, mâu thuẫn về hành động,... Các xung đột trong
tập luật có thể làm ảnh hưởng trực tiếp đến an ninh của
19
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
hệ thống khi cho phép các gói tin không hợp pháp đi qua,
hoặc ảnh hưởng đến hoạt động bình thường của hệ thống
mạng khi loại bỏ các gói tin hợp lệ, hay sẽ làm ảnh hưởng
đến hiệu năng (về mặt lưu trữ và xử lý) của chính thiết bị
tường lửa khi tồn tại các luật dư thừa.
Tại thời điểm năm 2004, kết quả khảo sát được trình bày
trong [1] cho thấy số lượng lớn các xung đột trong các tập
luật của tường lửa là một thực tế phải chấp nhận, và hiện
nay con số này chắc chắn sẽ lớn hơn rất nhiều. Chính vì
vậy, việc nghiên cứu để phát hiện và xử lý các xung đột
trong tập luật của tường lửa là một vấn đề đã và đang được
nhiều nhà nghiên cứu quan tâm thực hiện.
Các kỹ thuật phát hiện xung đột trong tập luật của các
thiết bị mạng nói chung và tường lửa nói riêng có thể được
chia làm hai loại cơ bản khi căn cứ vào số chiều của tập
luật đó: (i) phát hiện xung đột trên các tập luật hai chiều
và (ii) phát hiện xung đột trên các tập luật nhiều chiều.
Các kỹ thuật phát hiện xung đột trên các tập luật hai
chiều tiêu biểu gồm có [2–9]. Các kỹ thuật này chỉ thực
hiện kiểm tra, phát hiện và xử lý các xung đột trong tập
luật với hai chiều địa chỉ IP nguồn và địa chỉ IP đích trên
các thiết bị mạng nói chung như thiết bị định tuyến, tường
lửa, bảo mật IPSec, v.v. Các kỹ thuật này có hạn chế là
không thể áp dụng cho trường hợp các tập luật có số chiều
lớn hơn và kiểu dữ liệu của các chiều bị hạn chế.
Các kỹ thuật dạng thứ hai bao gồm các công trình [10–
14]. Các kỹ thuật này đưa ra các giải pháp nhằm phát hiện
và xử lý các xung đột giữa các luật nhiều chiều trong tập
luật của thiết bị tường lửa. Riêng nhóm các tác giả trong
công trình [10] đề xuất hướng phát hiện và xử lý các xung
đột giữa các luật trên tập luật của một nhóm các thiết bị
tường lửa nằm trên đường di chuyển của các gói tin. Các
kỹ thuật này được đánh giá mang tính tổng quát hơn các
kỹ thuật dạng đầu.
Bài báo này đề xuất cấu trúc cây phát hiện xung đột
(CDT: Conflict Detection Tree) nhằm phát hiện các xung
đột trong tập luật theo nhiều chiều trên một thiết bị tường
lửa đơn lẻ. Cấu trúc CDT tối ưu về mặt lưu trữ, có thể thực
hiện với các dạng dữ liệu khác nhau của mỗi trường, có ưu
điểm về mặt thời gian trong quá trình xây dựng cây cũng
như phát hiện xung đột. Ưu điểm của cấu trúc CDT so với
các cấu trúc khác được chứng minh bằng lý thuyết và đánh
giá qua quá trình thực nghiệm.
Bài báo được tổ chức với các phần tiếp theo như sau.
Mục II giới thiệu kiến thức chung về xung đột và một số
thuật toán phát hiện và xử lý xung đột trong tập luật nhiều
chiều. Mục III đề xuất cấu trúc CDT cho việc phát hiện các
xung đột. Mục IV trình bày kết quả thử nghiệm và đánh
giá thuật toán đề xuất. Mục V là kết luận và xác định các
hướng nghiên cứu có thể tiếp tục.
Hình 1. Các mối quan hệ hình học của không gian luật của hai
luật: (a) R và P tách biệt nhau hoàn toàn; (b) R trùng khớp hoàn
toàn với P; (c) R chứa P; (d) R và P có một phần giao nhau.
II. CÁC KIẾN THỨC LIÊN QUAN
1. Một số khái niệm
1) Định dạng luật trong tường lửa:
Mỗi luật trong tập luật của tường lửa được tạo bởi tập
giá trị mẫu của các trường và một hành động đi kèm. Tập
giá trị mẫu này chính là điều kiện các trường thông tin
trong gói tin cần thỏa mãn nếu muốn khớp với luật này.
Các trường thông tin ở đây có thể là bất cứ trường nào của
IP, UDP hay TCP headers. Trong thực tế các trường này
thường là IP nguồn, IP đích, cổng nguồn, cổng đích và kiểu
giao thức. Hành động gắn mỗi luật có thể là Accept (cho
phép gói tin đi qua) hoặc Deny (cấm đi qua).
Về mặt hình thức, mỗi luật R có thể được biểu diễn bởi
R( f1, f2, . . . , fn,Action), trong đó fi là giá trị mẫu của trường
thứ i. Giá trị mẫu có thể được cho dưới dạng khoảng, tiền
tố, hay tập các giá trị khác nhau.
2) Không gian luật:
Không kể đến trường Action trong luật, xét trong không
gian n chiều thì mỗi luật sẽ thuộc một điểm hay một đa
diện hình học trong không gian đó. Mối quan hệ giữa hai
không gian của luật R và luật P sẽ thuộc một trong 4 trường
hợp được thể hiện ở hình 1.
3) Các loại xung đột trong tập luật tường lửa:
Các loại xung đột giữa các luật của tường lửa được xác
định từ mối quan hệ giữa không gian luật, thứ tự và hành
động của chúng. Al-Shaer và các cộng sự trong [10] đã
định nghĩa và công thức hóa năm loại mối quan hệ giữa
hai không gian luật, bao gồm phân tách hoàn toàn (Com-
pletely Disjoint), khớp hoàn toàn (Exactly Matched), bao
gồm (Inclusively Matched), phân tách vài phần (Partially
Disjoint) và tương quan (Correlated).
Tuy nhiên các tác giả trong công trình [12] đã chỉ ra
rằng có thể coi quan hệ phân tách hoàn toàn và phân tách
vài phần là một. Bốn mối quan hệ còn lại tương ứng với
bốn trường hợp mô tả hình học trong hình 1. Từ các mối
quan hệ trên, các tác giả trong các công trình [10] và [12]
đã chỉ ra bốn loại xung đột có thể có giữa hai luật, đó
là kiểu bóng (Shadowing), kiểu tương quan (Correlation),
kiểu tổng quát (Generalization), kiểu dư thừa (Redundancy).
20
Tập V-3, Số 40, 12.2018
Trong các kiểu xung đột trên, chúng ta có thể bỏ qua kiểu
tổng quát [12, 13].
Kiểu bóng: Luật R1 là bóng của luật hay một nhóm luật
R2 trước nó khi tất cả các gói tin khớp với R1 cũng khớp
với R2 và hành động của R1 khác với hành động của R2.
Mối quan hệ không gian luật giữa R1 và R2 tương ứng với
kiểu xung đột này là R2 trùng khớp với R1 hoặc R2 chứa
R1. Trong trường hợp này, tất cả các gói tin mà một luật
muốn cấm có thể lại được cho phép bởi các luật trước nó.
Do đó, luật bị bóng sẽ không bao giờ có tác dụng.
Kiểu tương quan: Luật R1 tương quan với luật R2 nếu
một phần gói tin khớp với R1 cũng khớp với R2 và hành
động của R1 và R2 là khác nhau. Mối quan hệ không gian
luật giữa R1 và R2 tương ứng với kiểu xung đột này là R2
và R1 có một phần giao nhau. Trong trường hợp này, các
gói tin khớp bởi phần chung giữa hai luật này có thể được
cho phép bởi luật này nhưng lại bị cấm bởi luật khác.
Kiểu dư thừa: Luật R1 là dư thừa khi tồn tại một luật
hay một nhóm luật R2 trước nó thỏa mãn điều kiện tất cả
các gói tin khớp với R1 cũng khớp với R2 và hành động
của R1 và R2 là giống nhau. Mối quan hệ không gian luật
giữa R1 và R2 tương ứng với kiểu xung đột này là R2 trùng
khớp với R1 hoặc R2 chứa R1. Kiểu xung đột này không
ảnh hưởng đến an ninh của thiết bị nhưng làm lãng phí
không gian lưu trữ các luật.
2. Một số kỹ thuật phát hiện xung đột trong tập luật
của tường lửa
1) Kỹ thuật FIREMAN:
Kỹ thuật FIREMAN được các tác giả trong công
trình [11] đề xuất nhằm phát hiện xung đột giữa các luật
trong tập luật trên một tường lửa đơn hay các tường lửa
trong một phân đoạn mạng. Trong FIREMAN, các luật
được lưu trữ bởi biểu đồ quyết định nhị phân (BDDs: Binary
Decision Diagrams). Kỹ thuật này phát hiện các xung đột
trong tập luật bằng cách phân tích mối quan hệ giữa một
luật cụ thể với các tập hợp các khoảng giá trị của gói tin
phù hợp với các luật đứng trước nó. Điều này làm cho
FIREMAN có hạn chế là với mỗi luật nó chỉ kiểm tra các
luật trước đó mà bỏ qua tất cả các luật đứng sau khi thực
hiện phân tích xung đột.
2) Kỹ thuật phân mảnh:
Kỹ thuật phân mảnh (Rule-Based Segmentation) được
các tác giả trong công trình [13] đề xuất. Trong đó, kỹ
thuật đi sâu vào phát hiện và xử lý các xung đột giữa các
luật qua việc tìm kiếm phần không gian luật giao nhau của
các luật. Các tác đã đưa ra thuật toán phân tách không gian
luật của tất cả các luật thuộc tập luật thành các miền tách
biệt trong đó gồm các miền không giao nhau và các miền
giao nhau. Trong các miền giao nhau, kỹ thuật phân mảnh
chia thành ba loại không gian, đó là Allow (cho các luật
có hành động là Allow), Deny (cho các luật có hành động
là Deny) và Conflict (các miền không gian của các luật mà
có hành động khác nhau) và xác định chỉ có miền Conflict
là chứa các luật xung đột. Với cách phân chia như vậy, kỹ
thuật phân mảnh có hạn chế là sẽ bỏ qua các loại xung đột
kiều dư thừa.
Một hạn chế nữa của kỹ thuật phân mảnh trong công
trình [13] là đưa ra thuật toán phân mảnh không gian luật
của các luật đầu vào nhưng vẫn đề cốt lõi là việc tính toán
xác định các biên của mỗi mảnh không gian luật đó theo
các chiều cụ thể của mỗi luật không được các tác giả mô
tả chi tiết, điều này làm giảm tính thuyết phục của đề xuất.
3) Cấu trúc FAT:
Các tác giả của công trình [14] đã đề xuất xây dựng
cấu trúc cây mới có tên là FAT (Firewall Anormaly Tree),
nhằm phát hiện và xử lý các xung đột trong tập luật của
tường lửa. Trong công trình [14], mỗi trường của một
luật được phân tách thành các element và mỗi element
lưu trữ thông tin về một byte của trường có định dạng là
((byte,mask)b, (dim,ord)o). Trong đó, mask là số bít được
sử dụng trong byte đang xét, byte là giá trị của mask bit của
byte, dim là trường đang xét (1: source IP, 2: destination IP,
v.v.), ord là vị trí của byte đang xét trong trường dim. Các
tác giả đưa ra định nghĩa về thứ tự giữa các element với
nhau, trong đó element đứng trước khi có mask lớn hơn,
trong trường hợp giá trị này bằng nhau thì element nào có
dim nhỏ hơn sẽ đứng trước.
Cấu trúc FAT được xây dựng từ tập tất cả các element
của các luật. Một luật được biểu diễn trên cấu trúc FAT
bằng một đường dẫn luật gồm các nút, mỗi nút được xây
dựng dựa trên thông tin của các element. Các element đứng
trước sẽ được ưu tiên lựa chọn trước cho việc xây dựng các
nút. Mỗi nút sẽ có ba tập, đó là tập P (Primary) chứa các
luật khớp với đường dẫn từ nút gốc đến nút đang xét, tập S
(Second) chứa các luật có không gian luật chứa không gian
không gian luật ở tập P và tập T (Tertiary) chứa các luật
có không gian luật giao với không gian không gian luật ở
tập P. Việc xây dựng cấu trúc FAT sẽ được thực hiện đến
khi tất cả các element đã được chọn hết và mối quan hệ
giữa các luật được xác định nhờ các tập P, S và T tại các
nút lá.
Kỹ thuật này có các hạn chế sau đây:
◦ Phức tạp khi áp dụng cho các trường dữ liệu được cho
dưới dạng khoảng như cổng nguồn và cổng đích vì cần
phải xây dựng tập các tiền tố đại diện cho khoảng giá
trị đó [15]. Điều này làm tăng chi phí cho tính toán
đối với việc xây dựng tập tiền tố và tổng hợp các xung
đột cho các luật ở bước cuối.
◦ FAT có cấu trúc cây phức tạp do mỗi nút phải lưu trữ
nhiều thông tin.
21
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
◦ Việc sử dụng element cho việc lưu trữ từng byte dẫn
đến số lượng các element khi chuyển đổi và lưu trữ
các luật trong tập luật là rất lớn. Do đó, cấu trúc này
yêu cầu chi phí cao về bộ nhớ, cũng như thời gian cho
việc xây dựng và thay đổi cây.
III. CẤU TRÚC CÂY PHÁT HIỆN XUNG ĐỘT
TRONG TẬP LUẬT TƯỜNG LỬA
Theo lý thuyết thì xung đột giữa hai luật được căn cứ vào
3 yếu tố: mối quan hệ không gian luật giữa chúng, hành
 ...  S, O của N .
◦ Trong trường hợp N.M chứa duy nhất chỉ số k có nghĩa
N là nút chỉ khớp duy nhất với luật R thì khi xóa R
cũng tương ứng N bị xóa. Các dòng từ 5 đến 9 thực
hiện tác vụ này.
◦ Dòng 11: xóa k khỏi các cây con của N .
◦ Dòng 13: xóa k khỏi nút con OtherChild của N .
4. Phát hiện xung đột trên CDT
Thông tin mối quan hệ về không gian luật giữa các luật
được chứa trong tất cả các nút lá của cây. Cụ thể, tại nút
lá N: Các luật thuộc tập N.M là có không gian luật trùng
nhau; Các luật thuộc tập N.S có không gian luật chứa không
gian luật của các luật thuộc N.M; Các luật thuộc tập N.O
có không gian luật giao với không gian luật của các luật
thuộc tập N.M.
Loại xung đột được xác định theo thuật toán 5, cụ thể
như sau:
◦ Trong tập M, một luật R trong M được kiểm tra với
các luật P còn lại trong M. Nếu R và P có cùng hành
động thì: R là dư thừa (khi R đứng sau P), P là dư
thừa (khi R đứng trước P); Nếu R và P có hành động
khác thì: R là bóng của P (khi R đứng sau P), P là
bóng của R (khi R đứng trước P);
◦ Trong tập S, tất cả các luật P trong S được kiểm tra
lần lượt với mỗi luật R trong M. Nếu R và P có cùng
hành động thì: R là dư thừa (khi R đứng sau P), P là
dư thừa (khi R đứng trước P). Nếu R và P có hành
động khác thì: R là bóng của P (khi R đứng sau P), P
là bóng của R (khi R đứng trước P);
◦ Trong tậpO, tất cả các luật P trongO được kiểm tra lần
lượt mỗi luật R trong M. Nếu R và P khác hành động
thì chúng xung đột với nhau theo kiểu tương quan.
Trong thuật toán 5, ký hiệu R.order là chỉ thứ tự của luật
R trong tập luật, ListOfAnomaly là đầu ra của thuật toán
và là danh sách các xung đột được phát hiện trong tập luật
và thủ tục ListOfAnomaly.add() thực hiện thêm xung đột
vừa phát hiện vào danh sách.
Phát hiện xung đột là một vấn đề phức tạp, nhưng giải
quyết dứt điểm các xung đột đó là một vấn đề khó khăn hơn
rất nhiều. Điều này được chỉ ra trong các công trình [10–
14]. Trong phạm vi của bài báo, chúng tôi không đi sâu
về phát triển phương pháp xử lý xung đột một cách tổng
quan mà chỉ đưa ra các phương án lựa chọn cho người quản
trị hệ thống theo nguyên tắc xem xét bảo đảm an ninh hệ
thống một cách tốt nhất. Các nguyên tắc xử lý là cách ứng
xử với từng loại xung đột:
◦ Xung đột dư thừa: Luật dư thừa bị xóa bỏ.
◦ Xung đột bóng: Loại xung đột này thuộc hai dạng cho
phép các gói tin đã bị cấm bởi luật trước đó hay ngược
lại cấm các gói tin đã được cho phép trước đó. Đây là
sự nhầm lẫn trong cấu hình và cần phải kiểm tra chính
sách an ninh, trong trường hợp cho phép thì xóa bỏ luật
bóng hay thay đổi lại luật đường trước. Trong [14], các
tác giả đề xuất thay đổi vị trí của hai luật tuy nhiên
điều này vẫn không giải quyết hết xung đột.
◦ Xung đột tương quan: Có thể sử dụng giải pháp được
đề xuất trong [12, 13], tạo một luật mới có không gian
luật là phần giao nhau và hành động của luật này phải
được quyết định bới người quản trị và luật này được
đặt trước các luật bị giao nhau; Các luật có không gian
giao nhau được có thể điều chỉnh cắt bỏ phần không
gian chung đó. Hoặc có thể thay đổi thứ tự luật để các
gói tin thỏa mãn phần không gian chung được quyết
định chính xác theo chính sách an ninh.
IV. CÀI ĐẶT VÀ ĐÁNH GIÁ
Với mục đích kiểm chứng tính đúng đắn và đánh giá cấu
trúc CDT, chúng tôi triển khai cài đặt và kiểm thử cấu trúc
CDT và FAT [14] là kỹ thuật được đề xuất mới nhất và
29
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
Thuật toán 5: DetectAnomaly
Input: CDTNode N;
Output: List Of Anomaly;
Begin
1: if (N = NULL) then
2: return;
3: end if
4: if (N is leaf) then
//Duyệt các luật trong N.M
5: for each R in N.M do
6: for each (P , R) in N.M do
7: if (R.Action = P.Action) then
8: if (R.order < P.order) then
9: P is Redanduncy of R;
10: else
11: R is Redanduncy of P
12: ListOfAnomaly.Add();
13: end if
14: else
15: if (R.order < P.order) then
16: P is Shadowing of R;
17: else
18: R is Shadowing of P;
19: ListOfAnomaly.Add();
20: end if
21: end if
22: end for each
23: end for each
có nhiều điểm tương đồng. Ngôn ngữ sử dụng cài đặt các
thuật toán là Visual C# 2013. Quá trình kiểm thử trên nền
tảng hệ điều hành Windows 10, 64 bit, phần cứng CPU
Intel Core i3 - 4010U, 1,7 GHz, 2 cores, 4 GB RAM.
Để đảm bảo sát với ứng dụng thực tế, chương trình sử
dụng các bộ dữ liệu nhân tạo được tạo bằng bộ công cụ
ClassBench do Taylor, Turner thuộc Phòng Nghiên cứu ứng
dụng, Khoa khoa học máy tính, Đại học Washington, Saint
Louis tạo ra []. Các bộ
dữ liệu bao gồm các tập luật và các tập tham số gói tin
được sinh bởi bộ công cụ trên có dữ liệu đầu vào là những
bộ dữ liệu thực của các nhà cung cấp dịch vụ Internet. Đây
là bộ công được cộng đồng nghiên cứu sử dụng để đánh giá
các thuật toán và các thiết bị phân loại gói tin. Trong quá
trình so sánh, vì FAT không thực hiện được với các trường
cổng nguồn và cổng đích cho dưới dạng một khoảng giá
trị nên chúng tôi chỉ lấy giá trị đầu tiên để có thể kiểm
thử với FAT. Ví dụ, trường cổng nguồn là 80:110 thì giá trị
trường này khi kiểm tra là 80 với FAT và là khoảng [80:80]
với CDT.
//Duyệt các luật trong N.S
24: for each P in N.S do
25: for each R in N.M do
26: if (R.Action = P.Action) then
27: if (R.order < P.order) then
28: P is Redanduncy of R;
29: else
30: R is Redanduncy of P;
31: ListOfAnomaly.Add();
32: end if
33: else
34: if (R.order < P.order) then
35: P is Shadowing of R;
36: else
37: R is Shadowing of P;
38: ListOfAnomaly.Add();
39: end if
40: end if
41: end for each
42: end for each
//Duyệt các luật trong N.O
43: for each P in N.O do
44: for each R in N.M do
45: if (R.Action , P.Action) then
46: R and P is Correlation
47: ListOfAnomaly.Add();
48: end if
49: end for each
50: end for each
51: else // Not (N is leaf)
52: for (i = 0; i < N .Childs.count; i + +) do
53: DetectAnomaly(N .Childs[i]);
54: DetectAnomaly(N .OtherChild);
55: end for
56: end if
End
1. Kiểm tra khả năng phát hiện xung đột
Quá trình kiểm tra khả năng phát hiện xung đột của hai
thuật toán sử dụng các cấu trúc FAT và CDT được thử
nghiệm trên các tập dữ liệu của Classbench. Kết quả cho
thấy số lượng xung đột được phát hiện trên hai cấu trúc là
như nhau và được thể hiện trong bảng IV.
2. So sánh về số nút trong cây
Về mặt trực quan, chúng ta dễ dàng nhận thấy trong cấu
trúc FAT, mỗi nút sẽ lưu thông tin liên quan đến một byte
giá trị thuộc một trường cụ thể. Với cấu trúc này và trong
trường địa chỉ là IPv4, số nút tối đa là 4 cho một địa chỉ.
Trong cấu trúc CDT mỗi nút sẽ lưu thông tin của một giá
30
Tập V-3, Số 40, 12.2018
Bảng IV
KẾT QUẢ PHÁT HIỆN XUNG ĐỘT
TRÊN CÁC TẬP LUẬT KHÁC NHAU
Tập luật Số luật
Số xung đột
FAT CDT
ACL1 17584 222396 222396
ACL2 16194 1948040 1948040
ACL3 18530 542839 542839
ACL4 19086 360136 360136
ACL5 15194 7501 7501
Hình 1. So sánh số lượng nút trên cây CDT và cây FAT 
Hình 2. So sánh thời gian xây dựng cây CDT và FAT 
0
10000
20000
30000
40000
50000
60000
ACL1 ACL2 ACL3 ACL4 ACL5
CDT FAT
0
50000
100000
150000
200000
250000
300000
ACL1 ACL2 ACL3 ACL4 ACL5
CDT FAT
Số node trên cây 
Thời gian xây dựng cây (ms) 
Hình 6. So sánh số lượng nút trên CDT và cây FAT.
trị trường. Việc thử nghiệm với tập luật ví dụ tại bảng II
trong [14] thì cấu trúc cây FAT gồm 74 nút, cấu trúc CDT
chỉ bao gồm 30 nút và số lượng các xung đột được phát
hiện ở hai cây đều là 22. Kết quả thử nghiệm với dữ liệu
thực tế, số nút trên FAT và CDT được thể hiện trong hình 6.
3. So sánh về thời gian xây dựng cây
Quá trình xây dựng các cấu trúc FAT và CDT gồm các
bước chính sau đây:
◦ Chuyển đổi từ tập luật nguyên thủy sang tập các
element (FAT) và các unit (CDT);
◦ Chèn dữ liệu luật vào cây các element (FAT) và các
unit (CDT).
Quá trình chèn dữ liệu luật sẽ bao gồm thời gian xây
dựng của tất cả các nút. Trong quá trình xây dựng một nút,
thời gian tính toán cho quá trình phân nhánh tới các nút
con là nhiều nhất mà trong đó việc tính toán cho các ứng
viên của các tập đầu vào (Primary, Secondary, Tertiary với
FAT; Match, Super, Overlap với CDT) chiếm thời gian chủ
yếu. Trong cùng một tập luật, số lượng các unit của CDT
ít hơn về số lượng các element của FAT nên chi phí cho
việc lựa chọn các ứng viên của các tập đầu vào trên CDT
là nhỏ hơn trên FAT.
Kết quả thực nghiệm tại hình 7, cho thấy thời gian xây
dựng CDT nhỏ hơn hơn thời gian xây dựng FAT.
Hình 1. So sánh số lượng nút trên cây CDT và cây FAT 
Hình 2. So sánh thời gian xây dựng cây CDT và FAT 
0
10000
20000
30000
40000
50000
60000
ACL1 ACL2 ACL3 ACL4 ACL5
CDT FAT
0
50000
100000
150000
200000
250000
300000
ACL1 ACL2 ACL3 ACL4 ACL5
CDT FAT
Số node trên cây 
Thời gian xây dựng cây (ms) 
Hình 7. So sánh thời gian xây dựng CDT và FAT.
Hình 3. So sánh thời gian phát hiện xung đột 
Hình 4. So sánh bộ nhớ sử dụng 
0
100
200
300
400
500
600
700
800
ACL1 ACL2 ACL3 ACL4 ACL5
CDT FAT
0
10000
20000
30000
40000
50000
60000
70000
80000
90000
100000
ACL1 ACL2 ACL3 ACL4 ACL5
CDT FAT
Thời gian phát hiện xung đột (ms) 
Bộ nhớ sử dụng (Kbyte) 
Hình 8. So sánh thời gian phát hiện xung đột.
4. So sánh thời gian phát hiện xung đột
Vì số lượng nút trên cấu trúc CDT ít hơn số nút trên
cấu trúc FAT nên thời gian di chuyển từ nút gốc đến nút lá
nhằm phát hiện xung đột giữa các luật trên CDT nhỏ hơn
so với trên FAT. Kết quả thực nghiệm cũng cho kết quả là
trên CDT thời gian phát hiện xung đột nhỏ hơn trên FAT
(hình 8).
5. So sánh bộ nhớ lưu trữ
Bộ nhớ sử dụng bởi các cấu trúc CDT và FAT phụ thuộc
vào cấu trúc của mỗi nút và tổng số lượng các nút trên
cây khi biểu diễn một tập luật. Kết quả thực nghiệm trong
hình 9, cho thấy CDT sử dụng bộ nhớ hiệu quả hơn FAT.
V. KẾT LUẬN
Bài báo đã có nghiên cứu và đánh giá về các kỹ thuật
phát hiện và xử lý các xung đột trên tập luật nhiều chiều
của tưởng lửa. Trên cơ sở chỉ ra hạn chế của các kỹ thuật
đã có, bài báo đã đề xuất cấu trúc CDT nhằm phát hiện
các xung đột dựa trên việc xác định có hiệu quả mối quan
hệ không gian luật giữa các luật trên tường lửa. Cấu trúc
CDT được xây dựng trên cơ sở chứng minh về lý thuyết.
Các loại xung đột được phát hiện trên CDT chính xác về
kiểu và đầy đủ về số lượng.
31
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
Hình 3. So sánh thời gian phát hiện xung đột 
Hình 4. So sánh bộ nhớ sử dụng 
0
100
200
300
400
500
600
700
800
ACL1 ACL2 ACL3 ACL4 ACL5
CDT FAT
0
10000
20000
30000
40000
50000
60000
70000
80000
90000
100000
ACL1 ACL2 ACL3 ACL4 ACL5
CDT FAT
Thời gian phát hiện xung đột (ms) 
Bộ nhớ sử dụng (Kbyte) 
Hình 9. So sánh bộ nhớ sử dụng.
Kết quả thử nghiệm cho thấy khi so sánh với cấu trúc
FAT thì hiệu quả của cấu trúc CDT được thể hiện trên
các mặt:
◦ Số lượng nút trên cây giảm: 13% − 41%;
◦ Thời gian xây dựng cây giảm: 6% − 83%;
◦ Thời gian phát hiện xung đột giảm: 15% − 54%;
◦ Bộ nhớ sử dụng giảm: 5% − 30%.
Cấu trúc CDT hoàn toàn có thể được triển khai trong thực
tế với mục đích xây dựng bộ công cụ nhằm phát hiện và
xử lý xung đột trong tập luật của các thiết bị tường lửa.
Đây là hướng nghiên cứu tiếp theo của chúng tôi.
TÀI LIỆU THAM KHẢO
[1] E. S. Al-Shaer and H. H. Hamed, “Modeling and manage-
ment of firewall policies,” IEEE Transactions on Network
and Service Management, vol. 1, no. 1, pp. 2–10, 2004.
[2] A. Hari, S. Suri, and G. Parulkar, “Detecting and resolving
packet filter conflicts,” in Proceedings of the Conference on
Computer Communications. Nineteenth Annual Joint Confer-
ence of the IEEE Computer and Communications Societies
(IEEE INFOCOM 2000), vol. 3, 2000, pp. 1203–1212.
[3] H. Lu and S. Sahni, “Conflict detection and resolution in
two-dimensional prefix router tables,” IEEE/ACM Transac-
tions on Networking, vol. 13, no. 6, pp. 1353–1363, 2005.
[4] A. Kwok and C. K. Poon, “Two-dimensional packet classifi-
cation and filter conflict resolution in the internet,” Theory
of Computing Systems, vol. 44, no. 3, pp. 289–303, 2009.
[5] C. Maindorfer, “Algorithms and data structures for IP
lookup, packet classification and conflict detection,” Ph.D.
dissertation, University of Freiburg, Germany, 2009.
[6] S. Thanasegaran, Y. Yin, Y. Tateiwa, Y. Katayama, and
N. Takahashi, “A topology-based conflict detection system
for firewall policies using bit-vector-based spatial calculus,”
International Journal of Communications, Network and Sys-
tem Sciences, vol. 4, no. 11, pp. 683–695, 2011.
[7] C.-L. Lee, G.-Y. Lin, and Y.-C. Chen, “An efficient conflict
detection algorithm for packet filters,” IEICE Transactions
on Information and Systems, vol. 95, no. 2, pp. 472–479,
2012.
[8] C.-Y. Lai and P.-C. Wang, “Fast and complete conflict detec-
tion for packet classifiers,” IEEE Systems Journal, vol. 11,
no. 2, pp. 1137–1148, 2017.
[9] Vũ Duy Nhất and Nguyễn Mạnh Hùng, “Đề xuất thuật toán
phát hiện xung đột giữa các luật hai chiều trong các thiết bị
mạng,” in Kỷ yếu Hội thảo Quốc gia lần thứ XIX: Một số
vấn đề chọn lọc của Công nghệ Thông tin và Truyền thông,
Oct. 2016.
[10] E. Al-Shaer, H. Hamed, R. Boutaba, and M. Hasan, “Con-
flict classification and analysis of distributed firewall poli-
cies,” IEEE Journal on Selected Areas in Communications,
vol. 23, no. 10, pp. 2069–2084, 2005.
[11] L. Yuan, H. Chen, J. Mai, C.-N. Chuah, Z. Su, and P. Mohap-
atra, “Fireman: A toolkit for firewall modeling and analysis,”
in IEEE Symposium on Security and Privacy (S&P’06).
IEEE, 2006, pp. 15–pp.
[12] M. Abedin, S. Nessa, L. Khan, and B. Thuraisingham,
“Detection and resolution of anomalies in firewall policy
rules,” in Proceedings of the IFIP Annual Conference on
Data and Applications Security and Privacy. Springer,
2006, pp. 15–29.
[13] H. Hu, G.-J. Ahn, and K. Kulkarni, “Detecting and resolving
firewall policy anomalies,” IEEE Transactions on Depend-
able and Secure Computing, vol. 9, no. 3, pp. 318–331, 2012.
[14] T. Abbes, A. Bouhoula, and M. Rusinowitch, “Detection of
firewall configuration errors with updatable tree,” Interna-
tional Journal of Information Security, vol. 15, no. 3, pp.
301–317, 2016.
[15] N. B. Neji and A. Bouhoula, “NAF conversion: an efficient
solution for the range matching problem in packet filters,” in
Proceedings of the 12th International Conference on High
Performance Switching and Routing, 2011, pp. 24–29.
Nguyễn Mạnh Hùng tốt nghiệp đại học
về Công nghệ Thông tin năm 1998 tại Học
viện Kỹ thuật Quân sự và bảo vệ luận án
tiến sĩ năm 2004 tại Trung tâm Tính toán,
Viện hàn lâm Khoa học Liên bang Nga.
Hiện nay, ông đang công tác tại Phòng Sau
đại học, Học viện Kỹ thuật Quân sự. Các
hướng nghiên cứu tác giả đang triển khai
là cấu trúc dữ liệu hiện đại, khai phá dữ liệu, xử lý song song và
khớp ontology.
Vũ Duy Nhất tốt nghiệp đại học về Công
nghệ Thông tin năm 2002 tại Học viện Kỹ
thuật Quân sự. Hiện nay, ông đang công tác
tại Cục Cơ yếu, Bộ tổng tham mưu. Lĩnh
vực nghiên cứu quan tâm của ông là bảo
mật công nghệ thông tin.
32