Thiết kế xây dựng hệ thống và thực nghiệm
4.1. Mô hình tổng quát của hệ
Hệ MAV được triển khai trên mạng cục bộ [16] qua ba giai đoạn (i) Học dữ
liệu, (ii) Xử lý dữ liệu và (iii) Báo cáo. Giai đoạn 1 cài đặt trên máy chủ dành cho
chuyên gia: đầu vào là tập mẫu và tri thức chuyên gia, đầu ra là CSDL và CSTT.
Giai đoạn 2 và 3 cài đặt trên máy khách. Giai đoạn 2 chứa phần lõi của hệ gồm hai
bước tiền xử lý và xử lý dữ liệu. Tiền xử lý có nhiệm vụ phân lớp dữ liệu và nhận
dạ
ng sơ khởi để loại bớt các trường hợp chắc chắn nhiễm. Tiếp theo, bước xử lý sẽ
áp dụng các thuật giải nhận dạng virus dựa trên luật để phát hiện virus mới. Mọi kết
quả nhận dạng, suy diễn, lập luận sẽ được kết xuất sang giai đoạn Báo cáo. Phân
tích kết quả chẩn đoán, hệ sẽ đặt một số câu hỏi và giả
i thích nhằm tham vấn, xác
nhận quyết định người dùng để có cách giải quyết thích hợp. Cuối cùng, thông báo
kết quả chẩn đoán (Hình 4.1).
4.2. Tổ chức cơ sở tri thức
CSTT chứa các mô tả đối tượng - virus máy tính và các luật nhận dạng.

4.2.1. Mô tả đối tượng
Có nhiều loại virus máy tính với nhiều kỹ thuật lây nhiễm (xem Phụ lục 1 -
Khảo sát virus máy tính) trên các định dạng dữ liệu khác nhau (xem Phụ lục 2 - Các

Hình 4.1.
Mô hình tổng quát của hệ Phòng chống virus máy tính
hướng tiếp cận Máy học và Hệ chuyên gia MAV
- Trích chọn đặc trưng
- Phân cụm dữ liệu
- Rút luật phân cụm
Tiếp nhận tri thức
Giai đoạn Xử lý dữ liệu
(máy trạm)
Giai đoạn Học dữ liệu
(máy chủ + chuyên gia)
Giai đoạn Báo cáo
(máy trạm + người dùng)

CSDLCSTT
- Tổ chức không gian
- Phân lớp dữ liệu
- Hợp nhất dữ liệu
- Chẩn đoán truyền thống
Tiền xử lý dữ liệu
- Chẩn đoán dựa trên luật
- Các thuật giải tìm kiếm
- Phân tích, suy diễn, lập luận
Động cơ suy diễn
Báo cáo kết quả
Dữ liệu
chẩn đoán
- Hội thoại
- Tham vấn
Giải thích


Phương thức
: Phép trích chọn dữ liệu của lớp
Mỗi lớp dữ liệu lại được tổ chức thành các lớp con. Ví dụ lớp Application có
hai lớp con là COM và EXE. Lớp EXE có bốn lớp con DOS-EXE, NE-EXE, PE-
EXE và LE-EXE (xem Phụ lục 2, hình P2.2). Mỗi lớp dữ liệu có quan hệ với một
lớp virus (ví dụ lớp Document có quan hệ 1-1 với lớp D-class) hoặc với nhiều lớp
virus (ví dụ lớp Application có quan hệ 1-n với các lớp A-class và E-class).
4.2.2. Luật nhận dạng virus
Dạng tri thức thứ hai được mô tả trong CSTT là tập luật nhận dạng. Để nhận
dạng virus, hệ sử dụng một thư viện mô tả đặc trưng virus (ID-virus library) tổ chức
dưới dạng tập các vector V
K
= {v
1
, v
2
, …, v
k
}. Chẩn đoán virus là quá trình truy vấn
các vector v
i
trong tập dữ liệu S theo các luật dẫn xuất (production rule) dạng:
R: p
1
^ p
2
^…^ p
n
→ q

j
là tập dữ liệu đặc trưng của virus v
i
(j ÷1..m; m∈N*)
Hàm này sẽ trích chọn tự động các đoạn mã đặc trưng của virus trong các tổ
chức thi hành. Ở giai đoạn xử lý, hàm này cũng được dùng để trích chọn mẫu dữ
liệu đặc trưng tương ứng với các lớp virus cần chẩn đoán (xem Bảng 4.1).
4.3.2. Phân cụm dữ liệu
Mục tiêu của bước này nhằm phát hiện sự giống nhau giữa các mẫu virus để
gom chúng thành từng nhóm có cùng đặc điểm. Quy luật phân bố nhóm dùng trong
giai đoạn Xử lý dữ liệu nhằm ước lượng đối tượng chẩn đoán có thuộc một trong
các nhóm virus đã phân hoạch hay không để quyết định các bước kiểm tra tiếp theo.
Có thể thực hiện việc này bằng phân cụm dữ liệu, kỹ thuật phân lo
ại dữ liệu phổ
biến trong các hệ học không giám sát.
- 66 -
Bảng 4.1:
Trích chọn dữ liệu đặc trưng từ các định dạng cơ bản

Stt Lớp dữ liệu Lớp virus Vật chủ Nội dung trích chọn
1 Văn bản C-class Văn bản 7-bit Toàn bộ nội dung
Dữ liệu byte < 64KB
Tập tin thi hành
2 Chương trình
A-class
E-class
Tập tin thư viện
Từ điểm vào lệnh (IP-
Instruction Pointer) của
chương trình

giá trị (Value Tree, ký hiệu là V-Tree).
Là mô hình thích hợp để lưu trữ dữ liệu vector dài, V-Tree có cấu trúc giống
B-Tree và được xem là biến thể của R-Tree. Khác với R-Tree, V-Tree không quan
tâm đến việc tối thiểu các chữ nhật chồng lấp như R-Tree.
- 67 -

Cho các số nguyên m>1, n>1, cây m-phân V-Tree bậc (m,n) là một cây có:
-
Tất cả các nút lá đều có số mức như nhau.

-
Mỗi nút lá chứa các điểm có giá trị từ n/2 đến n.

-
Mỗi nút trung gian có m/2 đến m nút con, trừ nút gốc có từ 2 đến m con.

x
1k
x
2k
x
3k
… x
pk

Hình 4.3:
Ma trận dữ liệu
a,b,c,d,e
a
b
c
e
a,b
d
d,e
c,d,e
Gộp
Tách
Hình 4.2:
Hai phương pháp phân cấp cụm
- 68 -
-

Khởi tạo nút gốc
-


IF Pos(x[i, j], Current_Node.Child_list)= 0 THEN
MakeNew(Node, x[i,j],nil, nil)
Current_Node.Child_List ← Current_Node.Child_List+ Node
ENDIF
Current_Node ← Node
Current_Node.Points_List ← Current_Node.Points_List+j
ENDFOR
ENDFOR
Hình 4.4:
Thuật toán ACV phân cụm CSDL virus bằng V-tree

Để minh họa, xét CSDL virus 10 mẫu tin (Bảng 4.2). Các thuộc tính Type,
Hooking, Host được chọn tham gia phân cụm. Đầu tiên, nút gốc được tạo với danh
sách các con Child_list rỗng, danh sách Points_list được khởi tạo chứa 10 phần tử. - 69 -
Bảng 4.2:
Ví dụ cơ sở dữ liệu virus mẫu
Ptr. Virus Name Type Hooking Host Code
1 Virus 1 DLL Registry Application 3F2D9A…
2 Virus 2 EXE StartUp Application E9124F…
3 Virus 3 EXE StartUp Service 60E89F…
4 Virus 4 DLL Registry Service 583E6F…
5 Virus 5 EXE Registry Service E8558B…
6 Virus 6 EXE WinFile Application C0317F…
7 Virus 7 DLL Registry Application 902D3F…
8 Virus 8 EXE WinFile Application 7E5D9B…
9 Virus 9 EXE StartUp Service 347A9C…
10 Virus 10 DLL Registry Application 4B80FF…


Từ CSDL 10 virus, kết quả rút luật thu được sáu nhóm virus:
Nhóm 1:
Virus 1, Virus 7, Virus 10
Nhóm 4:
Virus 3, Virus 9
Nhóm 2:
Virus 4
Nhóm 5:
Virus 5
Nhóm 3:
Virus 2
Nhóm 6:
Virus 6, Virus 8
Việc phân nhóm CSDL virus có ý nghĩa quan trọng trong quá trình chẩn

NIL
Hình 4.5
:
Cây V-Tree sau khi duyệt 2 mẫu tin
Type
Hooking
Host
Root
1-2-3-4-5-6-7-8-9-10
DLL
, EXE
DLL
1
Registry
Registry
1
Application
Application
1
NIL
EXE
2
Startup
Startup
2
Application
Application
2
NIL
i = 1

liệu đầu vào. Gọi:
-

T
j
(k) và T
i
(p) là thời gian thực hiện tương ứng của các vòng lặp theo j và i.
-

T
j
(k) = O(f(k)), T
i
(p) = O(g(p))
Hình 4.7
:
Kết quả phân cụm CSDL virus bằng V-Tree
Type
Hooking
Host
Root
1-2-3-4-5-6-7-8-9-10
DLL-EXE
DLL
1-4-7-10
Registry
Registry
1-4-7-10
Application-Service

- 72 -
Thời gian thực hiện của 2 vòng lặp lồng nhau là T = O(f(k).g(p)). (1)
Gọi n là số phần tử của ma trận dữ liệu. Ta có n = k × p (2)
Từ (1) và (2) suy ra độ phức tạp của thuật toán là O(n).
Số lần duyệt mỗi nút bằng chính số cụm mà nút chứa. Nút gốc chứa số cụm
nhiều nhất (k mẫ
u tin). Các nút trung gian chứa số cụm ít hơn. Kết thúc thuật toán,
các mẫu tin đều được phân nhóm. Bảng 4.3 cho thấy mỗi cột trên ma trận dữ liệu
được duyệt k lần. Ma trận có p cột nên tổng số lần duyệt các nút là n = k ×p lần.

Bảng 4.3:
Tính toán số lần ACV duyệt nút trên V-tree
Mức Cột Nút
Danh sách
cụm
Số lần
duyệt nút
Số lần
duyệt mức
Ghi chú
DLL 1-4-7-10 4
1 Type
EXE 2-3-5-6-8-9 6
10
1-4-7-10 4
Registry
5 1
Startup 2-3-9 3
2 Hooking
WinFile 6-8 2

Sử dụng các phép toán cơ bản trên cấu trúc dữ liệu cây như tạo nút, thêm nút,
tìm nút con… nên việc thiết kế ACV khá đơn giản. Trong khi các mô hình phân
cụm phân cấp khác thường mắc nhược điểm không khắc phục được các quyết định
sai lầm khi trộn tách nhóm, thuật toán ACV có thể tránh được tình trạng này. Thật
vậy, ngoại trừ nút lá, mỗi nút trên V-Tree có ít nhất một nút con. Nhờ có mệnh đề
IF kiểm tra điều kiện tồn t
ại nút con và do các nút lá luôn đồng mức nên thuật toán
ACV không tạo ra các nút sai lầm.
Bước tiếp theo là rút luật phân nhóm virus, sẽ được giới thiệu ngay sau đây.
- 73 -
4.3.3. Rút luật phân bố trị thuộc tính
Trong các hệ học, tri thức được biểu diễn phổ biến dưới dạng luật IF-THEN.
Dạng luật này được đặc tả hình thức bằng mệnh đề Horn:
H
←
(L
1
^ L
2
^ … ^ L
n
)
Trong đó:
-

H: gọi là phần đầu (head), hệ quả (consequent) hay điều kiện sau
(postcondition) của luật.
-

L

n) tỷ lệ với số nhánh (số cluster). Trường hợp xấu nhất, khi các
mẫu tin đều “tách rời” nhau và được phân vào k nhánh, số lần duyệt nút trên cây là
k×(p+1). Trường hợp tốt nhất, khi tất cả các mẫu tin đều “giống nhau” và được phân
vào một cụm, chỉ cần duyệt (p+1) nút là đã rút được luật phân bố đặc trưng dữ liệu.
- 74 -
Áp dụng thuật giải R2LTA trên V-Tree, ta thu được sáu luật như sau:

Luật 1: Cluster_1 ← (Type=DLL) ∧ (Hooking=Registry) ∧ (Host=Application)
Luật 2: Cluster_2 ← (Type=DLL) ∧ (Hooking=Registry) ∧ (Host=Service)
Luật 3: Cluster_3 ← (Type=EXE) ∧ (Hooking=StartUp) ∧ (Host=Application)
Luật 4: Cluster_4 ← (Type=EXE) ∧ (Hooking=StartUp) ∧ (Host=Service)
Luật 5: Cluster_5 ← (Type=EXE) ∧ (Hooking=Registry) ∧ (Host=Service)
Luật 6: Cluster_6 ←(Type=EXE) ∧ (Hooking=WinFile) ∧ (Host=Application)

Trong ví dụ trên, số nút duyệt để rút được 6 luật là (3 cột +1)×6 luật = 24 nút
Về mặt trực quan, 6 luật trên có dạng tổng quát:
ClusterNum ← Type, Hooking, Host
Trong đó: ClusterNum ∈ {Cluster_1, Cluster2, …, Cluster_6} = q
Type ∈ {DLL, EXE} = p
1

Hooking ∈ {Registry, Startup, WinFile} = p
2

Host ∈ {Application, Service} = p
3

Rõ ràng, dạng tri thức này phù hợp với luật (4.1), công cụ lập luận chủ đạo
xây dựng các phát biểu IF-THEN cho quá trình lập luận và suy diễn của hệ. Phần
tiếp theo sẽ trình bày phương án rút luật phân cụm không sử dụng V-Tree.