1
ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
KHOA KHOA HỌC MÁY TÍNH
__________
TIỂU LUẬN MÔN HỌC:
THUẬT TOÁN VÀ PHƯƠNG PHÁP
GIẢI QUYẾT VẤN ĐỀ
ỨNG DỤNG MÁY HỌC
ĐỂ NHẬN DẠNG VIRUS MÁY TÍNH
Giảng viên hướng dẫn : PGS.TS ĐỖ VĂN NHƠN
Học viên thực hiện: NGUYỄN THỊ DIỄM AN
MSHV: CH1301075
1
GVHD: PGS.TS Đỗ Văn Nhơn SVTH: Nguyễn Thị Diễm An CH1301075
2
TP. Hồ Chí Minh, tháng 10 năm 2014
LỜI MỞ ĐẦU
Trong những năm gần đây cùng với sự phát triển mạnh mẽ của công
nghệ thông tin thì các hình thức virus cũng trở nên đa dạng và phong phú.Khi
một loại virus mới ra đời thì các nhà lập trình phải mất một khoảng thời gian
khá lâu để nhận diện và tiêu diệt nó, đủ lâu để các virus gây hại trên diện rộng
cho các hệ thống máy tính.
Thuật toán để cho máy học là một phạm trù rất rộng lớn, trong tiểu luận
này em chủ yếu tập trung vào mô hình hệ miễn dịch nhân tạo, mạng neuron để
phân tích, nhận dạng virus và dự báo virus mới.
Việc vận dụng mạng neron mô phỏng hoạt động của mạng neuron con
người, có khả năng ghi nhớ và nhận biết, từ đó hỗ trợ chương trình nhận dạng
được các loại virus.
2
GVHD: PGS.TS Đỗ Văn Nhơn SVTH: Nguyễn Thị Diễm An CH1301075

nó đã kịp lây lan và gây ra những hậu quả nghiêm trọng. Bởi vậy, cần một
hướng tiếp cận mới là đưa ra các phán đoán và dự báo kịp thời về các loại
virus mới. Áp dụng thuật toán máy học trong phát triển phần mềm nhằm hỗ trợ
phát hiện virus trên máy tính và có hướng giải quyết tiêu diệt virus đã phát
hiện, điều này đáp ứng được nhu cầu đặt ra.
1.2 Ý tưởng
Từ lý do các loại virus luôn luôn được đổi mới và phát triển để qua mặt
các hệ thống antivirus, bên cạnh đó đi kèm với virus là rất nhiều những biến
thể. Bởi vậy, yêu cầu đặt ra là làm thế nào một chương trình có khả năng học
hỏi và thích nghi với nhiều loại virus mới được phát triển và đưa ra những dự
báo kịp thời trước khi máy tính bị nguy hại.
Để đáp ứng được những yêu cầu đó thì em mô phỏng hệ miễn dịch
nhân tạo sinh học.Tương tự như trường hợp tiêm vacxin vào con người, từ đó
con người tiết ra kháng thể tiêu diệt được virus xâm nhập vào.Đồng thời kết
hợp khả năng mạnh mẽ của mạng nơ-ron trong quá trình học cũng như ghi nhớ
lại các loại virus đã phát hiện. Mạng nơ-ronđược nghiên cứu dựa trên cơ sở bộ
não con người, mỗi nơ-ron hoạt động như một bộ xử lý đơn giản. Chính sự
tương tác khổng lồ giữa tất cả các nơ-ron này cùng với quá trình xử lý song
5
GVHD: PGS.TS Đỗ Văn Nhơn SVTH: Nguyễn Thị Diễm An CH1301075
6
song của chúng tạo nên khả năng học và ghi nhớ.
1.3 Mục tiêu của đề tài
Với định hướng đó thì em có những mục tiêu sau:
- Tìm hiểu về cơ chế phát hiện virus bằng chuỗi nhận dạng.
- Tìm hiểu về các thuật toán di truyền (chọn lọc âm tính, ) để xây dựng
hệ miễn dịch nhân tạo, nhằm rút trích các chuỗi virus.
- Mục tiêu quan trong nhất là tìm hiểu về mạng no-ron, đặc biệt là mạng
lan truyển ngược để xây dựng chương trình nhận dạng virus.
CHƯƠNG 2: CƠ SỞ LÝ THUYẾT

Hệ miễn dịch là hệ thống sinh học bảo vệ cơ thể chống lại những tấn
công liên tục của các sinh vật từ bên ngoài, với hai chức năng chính là nhận
diện và loại bỏ những vi sinh vật xâm nhập vào cơ thể.
- Chức năng của hệ miễn dịch
7
GVHD: PGS.TS Đỗ Văn Nhơn SVTH: Nguyễn Thị Diễm An CH1301075
Miễn dịch
Bẩm sinh
Bạch cầu hạt
Ái kiềm
Ưa eosin
Tế bào lympho
Thích nghi
B-cell
T-cell
Đại thực bào
Trung &nh
8
Sinh học là nhận dạng tế bào và phân chia chúng thành hai nhóm khác
nhau: self (những tế bào của cơ thể tạo ra) và non-self (những tế bào lạ), đồng
thời loại bỏ các tế bào thuộc loại non-self.
- Thành phần hệ miễn dịch
Các dòng miễn dịch và thành phần của hệ miễn dịch
- Nhận diện và cơ chế kích hoạt
8
GVHD: PGS.TS Đỗ Văn Nhơn SVTH: Nguyễn Thị Diễm An CH1301075
9
Sự nhận diện và cơ chế kích hoạt đơn giản
o APC (Antigen Presenting Cell): Tế bào trình diện kháng nguyên
o MHC (Major Histocompatibility Complex): Phức hợp các phần

số lượng lớn. Những kháng thể này sẽ vô hiệu hoá tác nhân gây bệnh.Một số
B-cell và T-cell được kích hoạt này sẽ chuyển thành các tế bào ghi nhớ
(memory cell).
Chúng sẽ tiếp tục lưu thông trong cơ thể trong một khoảng thời gian
dài, giúp cơ thể chống lại những kháng nguyên tương tự lây nhiễm sau đó, nhờ
có sự “suy luận” (elicit) của hệ miễn dịch.
- Một số thuật toán
Có nhiều thuật toán áp dụng trong hệ miễn dịch nhân tạo như thuật toán
chọn lọc tiêu cực, chọn lọc tích cục, thuật toán nhân bản, đột biến …
trong phần này em chỉ đi nghiên cứu về thuật toán chọn lọc tiêu cực.
10
GVHD: PGS.TS Đỗ Văn Nhơn SVTH: Nguyễn Thị Diễm An CH1301075
11
- Thuật toán chọn lọc tiêu cực (Negative Selection Algorithm)
Có các bước tiến hành như sau:
Bước 1. Khởi tạo: Sản sinh một quần thể tiềm năng P những T-
cell chưa trưởng thành. Giả thiết tất cả các phần tử (các cơ quan thụ
cảm và các self-peptide) được biểu diễn bằng một chuỗi nhị phân L bit.
Bước 2. Đánh giá độ thích hợp: Xác định độ thích hợp của tất cả
T-cell trong P với mọi phần tử của tập self-set S
Bước 3. Tạo một quần thể có giá trị: Nếu độ thích hợp của một
T-cell chưa trưởng thành với ít nhất một phần tử self-peptide lớn hơn
hoặc bằng một ngưỡng tương tác chéo
ε
nào đó, thì T-cell nhận diện
được self-peptide này và bị loại bỏ, trái lại T-cell được bổ sung vào
quần thể có giá trị A.
Thuật toán lựa chọn tiêu cực
2.3 Mạng nơ-ron nhân tạo
- Mạng nơ-ron nhân tạo

q
w
ij
là trọng số nối từ
q-
1
w
j
đến
q
y
i
.
Đầu vào: các cặp huấn luyện {x
(k)
, d
(k)
| k=1,2, ,p}, ở đó giá trị đầu vào
của phần tử cuối cùng bằng -1, tức là
1
)(
1
−=
+
k
m
x
.
o Bước 0 (Đặt giá trị ban đầu)
Lựa chọn bước tính (Hằng số học) 0<η<1 và E

).()(
1
∑
−
==
j
j
q
ij
q
i
q
i
q
ywanetay
(2.30)
o Bước 3 (Đo lường sai số đầu ra)
Tính toán giá trị sai lệch và tín hiệu sai lệch
i
Q
δ
cho lớp đầu ra như sau:
13
GVHD: PGS.TS Đỗ Văn Nhơn SVTH: Nguyễn Thị Diễm An CH1301075
14
EydE
i
Q
n
i

)(
)'(
i
Q
i
Q
netd
da
neta =
o Bước 4 (lan truyền ngược sai số)
Các sai số lan truyền ngược với mục đích để cập nhật các trọng số và tính
toán các tín hiệu sai lệch
i
q
δ
1−
cho các lớp xử lý:
j
q
i
q
ij
q
yw
1

−
=∆
δη
;

14
GVHD: PGS.TS Đỗ Văn Nhơn SVTH: Nguyễn Thị Diễm An CH1301075
15
- là giá trị trọng số liên kết cũ từ phần tử thứ j của lớp (q-1)
đến phần tử i của lớp q.
- là tín hiệu ra của phần tử j của lớp (q-1).
o Bước 5 (Sau mỗi vòng lặp)
Kiểm tra xem đã lặp hết các giá trị mẫu huấn luyện chưa, nếu chưa quay
vòng hết (tức là k<p) tăng k=k+1, và nhảy tới bước 1, ngược lại (tức k=p) thì
chuyển sang bước 6.
o Bước 6 (Kiểm tra tổng sai số)
Kiểm tra sự khác nhau giữa tổng sai số và sai số cho phép:
Nếu tổng sai số nhỏ hơn sai số cho phép (tức là E < E
max
) thì kết thúc quá
trình huấn luyện, và ghi lại các giá trị trọng số cuối cùng.
Trái lại, thì lại gán E = 0, k = 1 và bắt đầu một quá trình huấn luyện mới
bằng cách nhảy tới bước 1.
Nói cách khác, mạng nơ-ron
tiếp tục quá trình huấn luyện tất cả
các mẫu lặp đi lặp lại cho đến khi
tổng sai số giảm dưới một giá trị
đích đã định trước rồi dừng. Khi tính
toán tổng sai số cho điều kiện dừng
của mạng, cần chuyển các sai số về
giá trị dương.
Sau khi mạng nơ-ron được
huấn luyện, nó sẽ có khả năng nhận
ra được không chỉ các mẫu ví dụ
hoàn thiện mà còn có thể nhận dạng

nhận dạng và cách mã hóa đầu ra. Vấn đề còn lại là kích thước lớp ẩn. Theo ví
dụ nhận dạng kí tự với mạng nơ-ron dùng để huấn luyện ghi nhớ 26 chữ trong
bảng chữ cái và mỗi chữ cái là một hình chữ nhật với chiều rộng là 5 ô vuông
và chiều cao là 7 ô vuông thì ta có 5 x7 ô vuông, sẽ cần 35 đầu vào, để nhận
dạng 26 kí tự ta sẽ cần 26 nơ-ron xuất. Mạng sẽ được huấn luyện để nhận dạng
tất cả 26 kí tự với số nơ-ron lớp ẩn trong khoảng 6 đến 22. Dưới 6 nơ-ron thì
mạng không đủ trọng số để chứa tất cả mẫu, trên 22 sẽ khiến tính hiệu quả của
mạng giảm sút. Cuối cùng, số lượng nơ-ron lớp ẩn cần được thực nghiệm để
đạt kết quả tốt nhất.
- Ưu và nhược điểm
o Ưu điểm
Của mạng sử dụng giải thuật lan truyền ngược là khả năng nhận dạng
mẫu (như chúng ta đã bàn ở trên). Các mẫu được trình diện trực tiếp cho mạng
được xác định vị trí trên lưới ô vuông và đúng kích thước.
o Nhược điểm
Trong nhận dạng mẫu của nó là khả năng xử lý các mẫu trong các quan
cảnh hỗn loạn như nhận dạng khuôn mặt trong đám đông hay 1 kí tự trong một
trang in. Do đó, chúng ta sẽ phải cần tiền xử lý dữ liệu để có được định dạng
chuẩn trước khi áp dụng cho mạng.
17
GVHD: PGS.TS Đỗ Văn Nhơn SVTH: Nguyễn Thị Diễm An CH1301075
18
CHƯƠNG 3: XÂY DỰNG CHƯƠNG TRÌNH
3.1 Phân tích yêu cầu
- Danh sách các yêu cầu:
Xử lý dữ liệu đầu vào
Xây dựng hệ miễn dịch nhân tao
Xây dựng mạng nơ-ron
Xây dựng tính năng nhận diện virus
- Đặc tả yêu cầu:

GVHD: PGS.TS Đỗ Văn Nhơn SVTH: Nguyễn Thị Diễm An CH1301075
22
- Hệ miễn dịch
o Xây dựng cấu trúc các tế bào T và tế bào B như sau:
Chương trình xây dựng bộ phát hiện (tế bào T, B) với chiều dài chuỗi l
= n* 32. Các chuỗi này là các chuỗi bít nhị phân, tùy thuộc vào việc phân biệt
độ dài giữa kháng nguyên và kháng thể mà ta có sự lựa chọn n sao cho thích
hơp. Điều này làm linh động cấu trúc của các tế bào bạch cầu, như vậy sẽ phù
hợp với cấu trúc của nhiều mầm bệnh (kháng nguyên) khi xâm nhập vào hệ
thống.
Cấu trúc nhỏ nhất mà ta quy định là 32 bít, như vậy, chiều dài của mỗi
tế bào là bội của 32.
Trước tiên ta rút trích từ các tệp tin virus theo chiều dài cố định là 32 bit
theo nguyên tắc không trùng lặp, để tăng độ chính xác khi ta lấy chiều dài
chuỗi l. Giả sử ta có 2 đơn vị 32 bít liên tục trưởng thành trong quá trình tôi
luyện ở chọn lọc âm tính, như thế l = 2* 32. Trong trường hợp này, khi ta rút
trích dữ liệu với đơn vị là 32 bit không lặp thì ta sẽ có chuỗi l không bị trùng
lặp như trong hình 5.6, còn nếu mà ta rút trích dữ liệu có trùng lặp thì khi đó
tập dữ liệu của ta sẽ bị trùng rất nhiều bit.
Như vậy, trong quá trình rút trích này, ta chọn rút trích dữ liệu không
trùng nhau.
Quy tắc rút trích được mô tả như sau:
Cắt không lặp
l = l1 hoặc l = l2 hoặc l = l1 + l2.
Nếu như ta rút trích tệp tin virus theo kiểu trùng lặp (giả sử trùng lặp 16
bít) có thể sẽ tăng bộ phát hiện nhưng sẽ không chính xác khi ta nối chuổi tạo
thành bộ nhận dạng.
22
GVHD: PGS.TS Đỗ Văn Nhơn SVTH: Nguyễn Thị Diễm An CH1301075
23

n-s
= ø với U
s
là tập con chứa toàn những dữ liệu của mình tức là dữ liệu sạch
và U
n-s
là tập con chứa toàn những dữ liệu không phải của mình tức là dữ liệu
bị nhiễm virus(mầm bệnh).
Như vậy, việc xây dựng cấu trúc các tế bào T và tế bào B trở thành việc
đi xây dựng các bộ phát hiện.Khi đã xây dựng cấu trúc các tế bào, ta đi qua
quá trình trưởng thành và chọn lọc âm tính.
o Chọn lọc âm tính
23
GVHD: PGS.TS Đỗ Văn Nhơn SVTH: Nguyễn Thị Diễm An CH1301075
24
Quá trình chọn lọc âm tính
Cơ chế chọn lọc âm tính của hệ miễn dịch là cơ sở cho việc phát hiện
các yếu tố bất bình thường. Điều này được mô hình hóa bằng việc yêu cầu
những bộ phát hiện hợp lệ là những cái không hợp lệ phát hiện ra yếu tố của
mình trong thời gian huấn luyện để trưởng thành .
Ví dụ quá trình chọn lọc
24
GVHD: PGS.TS Đỗ Văn Nhơn SVTH: Nguyễn Thị Diễm An CH1301075
25
- Mạng nơ-ron nhân tạo – mạng lan truyền ngược: (nhận dạng
virus)
Đầu vào chính là dữ liệu đã được chọn lọc trong hệ thống miễn dịch
nhân tạo như đã trình bày ở trên.
Cho mạng nơ-ron học và ghi nhớ các trọng số
Đầu ra mong muốn là chương trình hỗ trợ nhận diện tệp tin nhiêm virus