TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THỰC PHẨM TP. HCM
KHOA CÔNG NGHỆ THƠNG TIN

NGHIÊN CỨU CÁC THUẬT TỐN MÁY HỌC ỨNG
DỤNG TRONG PHÁT HIỆN BẤT THƯỜNG

GVHD: TRẦN ĐẮC TỐT
SVTH:
NGUYỄN THỊ THU HÀ

MSSV: 2033180

ĐINH TRƯƠNG THANH TUYỀN

MSSV: 2033180137

TP HỒ CHÍ MINH, 2021


PHIẾU GIAO NHIỆM VỤ
Trang này đính kèm phiếu giao nhiệm vụ của GVHD


BẢN NHẬN XÉT CỦA GVHD
Trang này đính kèm bản nhận xét của GVHD


LỜI CAM ĐOAN
Chúng tôi cam đoan rằng báo cáo đồ án này là do chính chúng tơi thực hiện dưới sự
hướng dẫn của Thầy Trần Đắc Tốt Các số liệu và kết quả phân tích trong báo cáo là
trung thực, không sao chép từ bất cứ đề tài nghiên cứu khoa học nào.

TP.HCM, tháng 06 năm 2021
SINH VIÊN THỰC HIỆN
(Kí và ghi rõ họ tên)
NGUYỄN THỊ THU HÀ
ĐINH TRƯƠNG THANH TUYỀN

1


TÓM TẮT ĐỒ ÁN
Học máy (Machine learning) là kỹ thuật cho phép giải quyết vấn để hoặc ra quyết
định dựa trên dữ liệu và kinh nghiệm. Với học máy, chương trình máy tính sử dụng
kinh nghiệm, quan sát, hoặc dữ liệu trong quá khứ để cải thiện công việc của mình
trong tương lai thay vì chỉ thực hiện theo đúng các quy tắc đã được lập trình sẵn. Chính
vì thế, việc ứng dụng Học máy trong phát hiện bất thường, đặc biệt đối với phát hiện
bất thường, là phù hợp và cần thiết trong bối cảnh hiện nay. Chính vì vậy, nhóm em
chọn đề tài “Nghiên cứu thuật tốn máy học ứng dụng trong phát hiện bất thường”,
trong đó tập trung nghiên cứu ứng dụng học máy trong phát hiện xâm nhập mạng bất
thường.

2


MỤC LỤC
PHIẾU GIAO NHIỆM VỤ .........................................................................................ii
BẢN NHẬN XÉT CỦA GVHD ................................................................................ iii
LỜI CAM ĐOAN ........................................................................................................ 1
TÓM TẮT ĐỒ ÁN ...................................................................................................... 2
MỤC LỤC .................................................................................................................... 3
DANH MỤC HÌNH ẢNH ........................................................................................... 5

MỞ ĐẦU ...................................................................................................................... 6
Đặt vấn đề ...................................................................................................................... 6
Mục tiêu của đề tài ........................................................................................................ 6
Đối tượng nghiên cứu chính ......................................................................................... 6
Bố cục đồ án gồm có 3 phần ........................................................................................ 6
CHƯƠNG 1. TỔNG QUAN ....................................................................................... 8
1.1. Phát hiện bất thường ............................................................................................... 8
1.1.1. Định Nghĩa ................................................................................................. 8
1.1.2. Chức năng ................................................................................................... 8
1.2. Hệ thống nhật ký .................................................................................................... 8
1.2.1. Định nghĩa .................................................................................................. 8
1.2.2. Chức năng ................................................................................................... 8
1.2.3. Phát hiện bất thường với hệ thống nhật ký ................................................. 8
1.3. Máy học .................................................................................................................. 8
1.3.1. Định nghĩa .................................................................................................. 8
1.3.2. Chức năng ................................................................................................... 9
1.3.3. Phân loại ..................................................................................................... 9
1.4. Deep Learning ...................................................................................................... 10
1.4.1. Định nghĩa ................................................................................................ 10
1.5. Ví dụ một số thuật tốn máy học.......................................................................... 10
1.5.1. Ví dụ 1: K-Means Clustering ................................................................... 10
1.5.2. Ví dụ 2: k-Nearest-Neighbors (k-NN) ...................................................... 10
1.5.3. Ví dụ 3: Support Vector Machines (SVM)............................................... 11
CHƯƠNG 2. PHÁT HIỆN VÀ CHUẨN ĐOÁN BẤT THƯỜNG TỪ NHẬT KÝ
HỆ THỐNG (DEEPLOG) ........................................................................................ 12
2.1. Tóm tắt ................................................................................................................. 12
2.2. Khái niệm CSS ..................................................................................................... 12
2.3. Giới thiệu .............................................................................................................. 12
2.4. Mở đầu.................................................................................................................. 13
2.4.1. Log parser ................................................................................................. 13

2.4.2. Kiến trúc Deeplog ..................................................................................... 14
2.4.3. Theat model .............................................................................................. 15
2.5. Phát hiện bất thường (Anomaly detection) .......................................................... 15
2.5.1. Execution path anomaly ........................................................................... 15
2.5.2. Giá trị tham số và sự bất thường về hiệu xuất .......................................... 19
3


2.5.3. Cập nhật trực tuyến các mơ hình phát hiện bất thường ............................ 20
2.6. Workflow Construction from Multi-task Execution ............................................ 20
2.6.1. Tách mục nhật ký khỏi nhiều tác vụ ......................................................... 20
2.6.2. Sử dụng mơ hình phát hiện bất thường của deeplog ................................ 20
2.6.3. Sử dụng phương pháp phân nhóm dựa trên mật độ .................................. 22
2.6.4. Sử dụng mơ hình quy trình làm việc ........................................................ 23
CHƯƠNG 3. THỰC NGHIỆM VÀ KÉT LUẬN .................................................. 25
3.1. Thực nghiệm......................................................................................................... 25
3.1.1. Quá trình chuẩn bị .................................................................................... 25
3.1.2. Quá trình thực nghiệm .............................................................................. 26
3.1.3. Đánh giá kết quả ....................................................................................... 31
TÀI LIỆU THAM KHẢO ........................................................................................ 32
PHỤ LỤC ................................................................................................................... 33

4


DANH MỤC HÌNH ẢNH

5



MỞ ĐẦU
Đặt vấn đề
Hiện nay công nghiệp 4.0 đang ngày càng phát triển, việc chuyển đổi số trên tất cả các
phương diện từ kinh doanh, buôn bán nhỏ lẻ, đến giáo dục, chính trị… vì sự tiện lợi và
khả năng tăng doanh số, giải quyết các vấn đề nhanh chóng mà nó mang lại, song song
với nó là nhưng mối lo về vấn đề an tồn thơng tin đang rất được quan tâm, việc phát
triển nhanh chóng của mạng Internet tạo ra càng nhiều các hacker muốn lợi dụng những
lỗ hổng trên không gian mạng, những kĩ thuật tấn công ngày càng tinh vi, để đánh cắp
thông tin người dùng, những bí mật thương mại… vì một mục đích nào đó như tống
tiền hay phá hoại… ảnh hưởng đến cơng việc, doanh thu cũng như đời sống của người
bị tấn cơng…
Có rất nhiều phương pháp đã đước áp dụng để đảm bảo việc an toàn hệ thống mạng
như : hệ thống tường lửa (firewall), các hệ thống xác thực, hệ thống bảo mật thiết bị
đầu cuối(endpoint)… Trong đó phát hiện bất thường là hệ thống quan trọng và không
thể thiếu trong việc đảm bảo an tồn mạng an tồn thơng tin.
Có nhiều phương pháp kỹ thuật để triển khai hệ thống, trong đó phát hiện bất thường
dựa trên hệ thống nhật ký đang rất được nhiều nhà nghiện cứu quan tâm và phát triển
hiện nay.
Mục tiêu của đề tài
Nghiên cứu các phương pháp học máy; Nghiên cứu một số cách thức phát hiện xâm
nhập trái phép. Từ đó ứng dụng phương pháp học máy phát hiện bất thường nhật ký.
Cuối cùng xây dựng tài liệu hệ thống và cách sử dụng dành cho người dùng
Đối tượng nghiên cứu chính
Đối tượng nghiên cứu: Các phương pháp học máy; phương pháp phát hiện xâm nhập
trái phép đặc biệt là phát hiện bất thường nhật ký (deeplog); các luồng dữ liệu trên
mạng.
Phạm vi nghiên cứu: Phát hiện bất thường trong nhật ký (deeplog)
Bố cục đồ án gồm có 3 phần
Chương 1: Tổng quan
Chương 2: Phát hiện và chẩn đoán bất thường từ Nhật ký hệ thống (Deeplog)

Chương 3: Đánh giá

6


Phạm vi nghiên cứu(Khảo sát):
Đọc, phân tích, tổng hợp tài liệu về các phương các phương pháp học máy.
Đọc, phân tích, tổng hợp tài liệu về các cách thức phát hiện xâm nhập trái phép và cách
tiếp cận bằng phương pháp học máy trên các luồng dữ liệu

7


CHƯƠNG 1. TỔNG QUAN
1.1. Phát hiện bất thường
1.1.1. Định Nghĩa
Phát hiện bất thường là hoạt động theo dõi, phân tích và giám sát quét toàn bộ hệ thống
để phát hiện các mối đe dọa như: sự gia tăng đột ngột lượng truy cập hơn mức bình
thường hoặc so với phạm vi dữ liệu trong quá khứ.
1.1.2. Chức năng
-

Theo dõi các nguồn dữ liệu như thiết bị, nhật kí, máy chủ, mạng

-

Dự đoán và xác định các mối đe dọa

-


Theo dõi và báo cáo các hành vi bất thường trên các nguồn khơng thuộc radar

-

Khai thác người dùng lừa đảo

-

Phân tích thông tin máy chủ, người dung…

1.2. Hệ thống nhật ký
1.2.1. Định nghĩa
Hệ thống nhật ký (logs) là nơi ghi lại tất cả các hoạt động, trạng thái và các sự kiện của
hệ thống.
1.2.2. Chức năng
Hệ thống nhật kí giải quyết vấn đề về lỗi của hiệu suất, những mối đe dọa đến an tồn
hệ thống, phân tích ngun nhân gốc rễ và cảnh báo đến người quản trị hệ thống
1.2.3. Phát hiện bất thường với hệ thống nhật ký
Việc sử dụng hệ thống nhật ký trong phát hiện bất thường đang rất được quan tâm…
Các phương pháp có thể được chia thành 3 loại:
-

dựa trên PCA tiếp cận qua bộ đếm thông báo nhật ký.
dựa trên khai thác bất biến các phương pháp để nắm bắt các mẫu đồng xuất
hiện giữa các nhật ký khác nhau các khóa.
các phương pháp dựa trên quy trình làm việc để xác định các dị thường thực
thi trong các luồng logic chương trình.

1.3. Máy học
1.3.1. Định nghĩa

Máy học là 1 nhánh của trí tuệ nhân tạo và khoa học máy tính sử dụng dữ liệu và thuật
toán để bắt chước cách con người học, dần dần cải thiện độ chính xác của nó.
8


1.3.2. Chức năng
Học máy là một thành phần quan trọng của lĩnh vực khoa học dữ liệu đang phát
triển. Thông qua việc sử dụng các phương pháp thống kê, các thuật toán được đào tạo
để đưa ra phân loại hoặc dự đoán, khám phá những hiểu biết quan trọng trong các dự
án khai thác dữ liệu. Những thông tin chi tiết này sau đó thúc đẩy việc đưa ra quyết
định trong các ứng dụng và doanh nghiệp, tác động lý tưởng đến các chỉ số tăng trưởng
chính.
1.3.3. Phân loại
1.3.3.1 Phương pháp học máy có giám sát
Sử dụng các tập dữ liệu có nhãn dán để đào tạo các thuật tốn nhằm phân loại dữ liệu
hoặc dự đoán kết quả một cách chính xác. Giúp các tổ chức giải quyết nhiều vấn đề
trong thế giới thực trên quy mô lớn, chẳng hạn như phân loại thư rác trong một thư
mục riêng biệt từ hộp thư đến của bạn.
Ví dụ:
Một số phương pháp áp dụng như: neural networks, naïve bayes, linear regression,
logistic regression, random forest, support vector machine (SVM).
Các tác vụ :
•

Phân loại nhị phân: Chia dữ liệu thành hai loại.

•

Phân loại nhiều lớp: Lựa chọn giữa nhiều hơn hai loại câu trả lời.


•

Mơ hình hồi quy : Dự đốn các giá trị liên tục.

•

Ghép nối : Kết hợp các dự đốn của nhiều mơ hình học máy để đưa ra dự đốn
chính xác.

1.3.3.2 Phương pháp học máy khơng giám sát
Sử dụng các thuật tốn học máy để phân tích và phân cụm các tập dữ liệu không được
gắn nhãn. Sử dụng để giảm số lượng các tính năng trong một mơ hình thơng qua q
trình giảm kích thước; phân tích thành phần chính (PCA) và phân tích giá trị đơn lẻ
(SVD) là hai cách tiếp cận phổ biến cho việc này.

Ví dụ :
Một số phương pháp áp dụng: neural networks, k-means clustering, probabilistic
clustering methods.

9


Các tác vụ:
•

Phân cụm : Tách tập dữ liệu thành các nhóm dựa trên sự giống nhau.

•

Phát hiện bất thường : Xác định các điểm dữ liệu bất thường trong tập dữ liệu.


•

Khai thác liên kết : Xác định các tập hợp các mục trong tập dữ liệu thường
xuyên xảy ra cùng nhau.

•

Giảm kích thước: Giảm số lượng biến trong tập dữ liệu

1.4. Deep Learning
1.4.1. Định nghĩa
Là một nhánh của máy học, liên quan đến cấu trúc và chức năng của não bộ. Sự kết
nối của nhiều tế bào thần kinh tạo nên Deep Learning.
Ứng dụng:
Nhận diện giọng nói, hình ảnh, âm thanh, phân tích hình ảnh y tế,….
1.5. Ví dụ một số thuật tốn máy học
1.5.1. Ví dụ 1: K-Means Clustering
Là phương pháp gom cụm nổi tiếng.
Input: x1 , …, xn , k với mỗi xi là một điểm trong khơng gian đặc tính n-chiều
Bước 1: Chọn k tâm cụm c1 ,…, ck
Bước 2: Với mỗi điểm xi , xác định cụm của nó: Tìm tâm cụm gần nhất ( có thể sử
dụng khoảng cách Euclidean)
Bước 3: Cập nhật tất cả tâm cụm theo centroids

Lặp Bước 2 và Bước 3 cho đến khi tâm cụm khơng thay đổi
1.5.2. Ví dụ 2: k-Nearest-Neighbors (k-NN)
Lưu mỗi mẫu dữ liệu của tập huấn luyện như là một điểm trong không gian đặc tính
Phân lớp một mẫu mới bằng cách đưa vào phân lớp có các phần tử láng giềng gần nhất
(nearest neighbor) trong khơng gian đặc tính

Input: dữ liệu huấn luyện (x1 , y1 ), … , (xn , yn ); hàm khoảng cách d(); số lượng láng
giềng k; mẫu kiểm thử x*
10


1. Tìm k mẫu huấn luyện xi1 ,…xik gần nhất với x* theo d()
2. Cho đầu ra y* là lớp ưu thế của yi1 , …, yik

1.5.3. Ví dụ 3: Support Vector Machines (SVM)
SVM được dùng cho bài toán nhị phân.
Giả sử đầu bài cho tập hợp các điểm thuộc 2 loại trong môi trường N chiều, SVM là
phương pháp để tìm ra N-1 mặt phẳng để ngăn các điểm thành 2 nhóm.
Ví dụ: Cho một tập hợp các thuộc 2 loại như hình mơ tả phía dưới, SVM có nhiệm vụ
tìm ra một đường thẳng để phân tách những điểm đó thành 2 loại sao cho độ dài khoảng
cách giữa đường thẳng và những điểm là xa nhất có thể.

Hình 1. Ví dụ minh họa thuật tốn SVM

Xét trên quy mô SVM đã giải quyết được nhiều vấn đề lớn như hiển thị quảng cáo,
phát hiện ra giới tính bằng hình ảnh, phân loại hình ảnh có phạm vi rộng (cần sửa đổi
SVM cho phù hợp).

11


CHƯƠNG 2. PHÁT HIỆN VÀ CHUẨN ĐOÁN BẤT THƯỜNG TỪ
NHẬT KÝ HỆ THỐNG (DEEPLOG)
2.1. Tóm tắt
Phát hiện bất thường là một bước quan trọng để xây dựng một hệ thống an tồn
và đáng tin cậy. Mục đích chính của nhật ký hệ thống là ghi lại các trạng thái hệ thống

và các sự kiện đáng kể không thể xảy ra tại các điểm quan trọng khác nhau để giúp gỡ
lỗi hệ thống và thực hiện phân tích nguyên nhân gốc rễ. Dữ liệu nhật ký như vậy có
sẵn phổ biến trong hầu hết các hệ thống máy tính. Dữ liệu nhật ký là tài nguyên quan
trọng và có giá trị để hiểu các vấn đề về hiệu suất và trạng thái hệ thống. Điều này cho
phép DeepLog tự động tìm hiểu các phân tích nhật ký từ việc thực thi bình thường và
phát hiện các bất thường khi phân tích nhật ký đi chệch khỏi mơ hình được triển khai
từ dữ liệu nhật ký trong quá trình thực thi bình thường. Ngồi ra, nhóm trình bày cách
cập nhật từng bước mơ hình DeepLog theo cách trực tuyến để nó có thể thích ứng với
các bản ghi nhật ký mới theo thời gian. Hơn nữa, DeepLog xây dựng các quy trình làm
việc từ nhật ký hệ thống cơ bản để một khi phát hiện ra sự bất thường, người dùng có
thể chẩn đoán sự bất thường được phát hiện và thực hiện phân tích nguyên nhân gốc
rễ một cách chính xác. Các đánh giá thử nghiệm mở rộng trên dữ liệu nhật ký lớn đã
chỉ ra rằng DeepLog đã làm tốt hơn các phương pháp phát hiện bất thường dựa trên
nhật ký hiện có khác dựa trên các phương pháp khai thác dữ liệu truyền thống.
2.2. Khái niệm CSS
-

Hệ thống thông tin → Xử lý phân tích trực tuyến;
Bảo mật và quyền riêng tư → Phát hiện xâm nhập / bất thường và phần mềm
độc hại Mitiga tion;

2.3. Giới thiệu
Phát hiện bất thường là một nhiệm vụ thiết yếu nhằm xây dựng một hệ thống
máy tính an tồn và đáng tin cậy. Khi các hệ thống và ứng dụng ngày càng trở nên
phức tạp hơn bao giờ hết, chúng có nhiều lỗi và lỗ hổng bảo mật hơn mà kẻ thù có thể
khai thác để khởi chạy các cuộc tấn cơng. Những công cụ như vậy cũng ngày càng tinh
vi hơn. Do đó, việc phát hiện dị thường trở nên khó khăn hơn và nhiều phương pháp
phát hiện dị thường truyền thống dựa trên các phương pháp khai thác tiêu chuẩn khơng
cịn hiệu quả nữa.
Nhật ký hệ thống ghi lại các trạng thái hệ thống và các sự kiện đáng kể tại các

điểm quan trọng khác nhau để giúp gỡ lỗi các sự cố và lỗi hiệu suất, đồng thời thực
hiện phân tích nguyên nhân gốc rễ. Dữ liệu nhật ký như vậy có sẵn phổ biến trong hầu
hết các hệ thống máy tính và là một tài ngun có giá trị để hiểu tình trạng hệ thống.
Hơn nữa, vì nhật ký hệ thống ghi lại các sự kiện đáng chú ý khi chúng xảy ra từ các
quy trình đang chạy tích cực, chúng là nguồn thơng tin tuyệt vời để giám sát trực tuyến
12


và phát hiện bất thường.
Các phương pháp hiện có tận dụng dữ liệu nhật ký hệ thống để phát hiện bất
thường có thể được phân loại rộng rãi thành ba nhóm:
-

phương pháp dựa trên PCA qua bộ đếm thơng báo nhật ký
phương pháp dựa trên khai thác bất biến để nắm bắt các mẫu đồng xuất
hiện giữa các khóa nhật ký khác nhau
dựa trên quy trình các phương pháp xác định các dị thường thực thi trong
các luồng logic chương trình

DeepLog, một phương pháp tiếp cận theo hướng dữ liệu để phát hiện dị thường
nhằm thúc đẩy khối lượng lớn nhật ký hệ thống. Trực giác quan trọng đằng sau thiết
kế của DeepLog là từ quá trình xử lý lan guage tự nhiên: xem các mục nhập nhật ký là
các phần tử của một chuỗi tuân theo các mẫu và quy tắc ngữ pháp nhất định. Thật vậy,
nhật ký tem hệ thống được tạo ra bởi một chương trình tuân theo một tập hợp logic và
quy trình kiểm sốt chặt chẽ, và rất giống một ngôn ngữ tự nhiên (mặc dù có cấu trúc
hơn và bị hạn chế về từ vựng). Vì vậy, DeepLog là một mạng nơ-ron sâu mơ hình hóa
chuỗi các mục nhập nhật ký này bằng cách sử dụng Long Short-t-Term Memory
(LSTM). Điều này cho phép DeepLog tự động tìm hiểu mơ hình các mẫu nhật ký từ
q trình thực thi cũng khơng phải lỗi và gắn cờ các sai lệch so với thực thi hệ thống
bình thường như là bất thường. Hơn nữa, vì đây là một phương pháp tiếp cận hướng

đến việc học, nên có thể từng bước cập nhật mơ hình DeepLog để nó có thể thích ứng
với các phân đoạn nhật ký mới xuất hiện theo thời gian. Điều này cho phép DeepLog
tự động tìm hiểu mơ hình các mẫu nhật ký từ q trình thực thi cũng khơng phải lỗi và
gắn cờ các sai lệch so với thực thi hệ thống bình thường như là bất thường. Hơn nữa,
vì đây là một phương pháp tiếp cận hướng đến việc học, nên có thể từng bước cập nhật
mơ hình DeepLog để nó có thể thích ứng với các phân đoạn nhật ký mới xuất hiện theo
thời gian.
2.4. Mở đầu
2.4.1. Log parser
Phân tích cú pháp các mục nhập nhật ký văn bản tự do, khơng có cấu trúc thành
một biểu diễn có cấu trúc =>mơ hình tuần tự trên dữ liệu có cấu trúc.
Phương pháp trích xuất một “khóa nhật ký” (cịn được gọi là “message type”)
từ mỗi mục nhập nhật ký. Khóa nhật ký của một mục nhật ký nằm trong hằng số chuỗi
k từ câu lệnh in trong mã nguồn đã in ra e trong q trình thực thi mã đó.
Ví dụ, khóa nhật ký k cho mục nhập nhật ký e = “Mất 10 giây để tạo phiên bản.” là k
= Took * giây để xây dựng phiên bản., là hằng số chuỗi từ câu lệnh printf ("Took% f
seconds to build instance.", t). Lưu ý rằng (các) tham số được tóm tắt dưới dạng (các)
dấu hoa thị trong khóa nhật ký. Các giá trị số liệu này hoàn thiện trạng thái hệ thống
cơ bản và trạng thái hiệu suất. Giá trị của các tham số nhất định có thể đóng vai trò là
13


số nhận dạng cho một trình tự thực thi cụ thể, chẳng hạn như block_id trong nhật ký
HDFS và instance_id trong nhật ký OpenStack. Các số nhận dạng này có thể nhóm các
mục nhật ký lại với nhau hoặc gỡ rối các mục nhật ký được tạo ra bởi các quy trình
đồng thời để tách các chuỗi tuần tự đơn luồng. Phương pháp phân tích cú pháp nhật ký
hiện đại được đại diện bởi Spell, một trình phân tích cú pháp phát trực tuyến khơng
được giám sát có thể phân tích cú pháp đến ghi nhật ký các mục nhập theo kiểu trực
tuyến dựa trên ý tưởng về LCS.
Phân tích nhật ký đã loại bỏ số lần xáo trộn hoặc giá trị tham số trong mục nhập

nhật ký và chỉ sử dụng các khóa nhật ký để phát hiện những điểm bất thường. DeepLog
lưu trữ các giá trị thông số cho mỗi nhật ký mục nhập e, cũng như thời gian trơi qua
giữa e và tiền nhiệm của nó, thành một vectơ ⃗⃗⃗
𝑣𝑒 . Vectơ này được DeepLog sử dụng
ngoài chìa khóa nhật ký. Một ví dụ được đưa ra trong Bảng 1, hiển thị kết quả phân
tích cú pháp cho một chuỗi các mục nhập nhật ký từ nhiều vịng thực thi tác vụ xóa
máy ảo (VM) trong OpenStack.
Log message (log key underlined)

log key

parameter value vector

t1 Deletion of file1 complete

𝑘1

𝑡1 − 𝑡0 , 𝑓𝑖𝑙𝑒1𝐼𝑑

t2 Took 0.61 seconds to deallocate network …

𝑘2

𝑡2 − 𝑡1 , 0.61

t3 VM Stopped (Lifecycle Event)

𝑘3

𝑡3 − 𝑡2


…

…

…

Bảng 1: Ghi nhận từ nhiệm vụ xóa OpenStack VMdeletion tack

2.4.2. Kiến trúc Deeplog
Kiến trúc của DeepLog được thể hiện trong Hình 1 với ba thành phần chính: mơ
hình phát hiện bất thường khóa log, mơ hình phát hiện bất thường giá trị tham số và
mơ hình quy trình làm việc để chẩn đoán các bất thường được phát hiện

Hình 2.1 kiến trúc DeepLog

Mơ hình phát hiện bất thường để kiểm tra xem khóa nhật ký đến có bình thường
14


hay khơng. Nếu có, DeepLog sẽ kiểm tra thêm vectơ giá trị tham số bằng cách sử dụng
mơ hình phát hiện bất thường giá trị tham số cho khóa nhật ký đó. Mục nhập mới sẽ
được gắn nhãn là bất thường nếu khóa nhật ký hoặc vectơ giá trị tham số của nó được
dự đốn là bất thường. Cuối cùng, nếu nó được gắn nhãn là bất thường, thì mơ hình
quy trình làm việc của DeepLog sẽ cung cấp thơng tin ngữ nghĩa để người dùng chẩn
đoán sự bất thường. Các mẫu thực thi có thể thay đổi theo thời gian hoặc không được
đưa vào dữ liệu đào tạo ban đầu. DeepLog cũng cung cấp tùy chọn để thu thập phản
hồi của người dùng. Nếu người dùng báo cáo một điều bất thường được phát hiện là
dương tính giả, DeepLog có thể sử dụng nó như một bản ghi được gắn nhãn để từng
bước cập nhật các mơ hình của nó để kết hợp và thích ứng với phương pháp mới.

2.4.3. Theat model
DeepLog tìm hiểu các mối tương quan và mẫu phức tạp và toàn diện được nhúng
trong một chuỗi các mục nhập nhật ký được tạo ra bởi các đường dẫn thực thi hệ thống
thơng thường. Do đó, giả định rằng bản thân nhật ký hệ thống được bảo mật và bảo vệ,
và kẻ thù không thể lấy lại tính tồn vẹn của chính nhật ký đó. Và giả định rằng kẻ thù
không thể sửa đổi mã nguồn hệ thống để thay đổi hành vi và mẫu ghi nhật ký của nó.
nói chung, có hai loại cơng cụ là:
(1) Các lỗi dẫn đến hành vi thực thi sai của hệ thống và do đó các mẫu bất
thường trong nhật ký hệ thống. Ví dụ: các lỗi từ chối dịch vụ (DoS) có thể
gây ra tốc độ thực thi chậm và do đó phát sinh các bất thường của mance
được phản ánh trong sự khác biệt về dấu thời gian của nhật ký so với chuỗi
vectơ giá trị tham số;
(2) Các ngăn chứa có thể để lại dấu vết trong nhật ký hệ thống do các hoạt động
ghi nhật ký của các dịch vụ giám sát hệ thống. Một ví dụ là các hoạt động
đáng ngờ được ghi lại bởi Hệ thống phát hiện xâm nhập (IDS).
2.5. Phát hiện bất thường (Anomaly detection)
2.5.1. Execution path anomaly
Mô tả cách phát hiện sự bất thường của đường dẫn thực thi bằng cách sử dụng
chuỗi khóa nhật ký. Vì tổng số câu lệnh in riêng biệt (mục nhập nhật ký in) trong một
mã nguồn là khơng đổi, nên tổng số khóa nhật ký riêng biệt cũng vậy. Cho 𝐾 =
{𝑘1 , 𝑘2 , … , 𝑘𝑛 } là tập hợp các khóa nhật ký riêng biệt từ mã nguồn hệ thống tạo nhật
ký.
Khi các mục nhập nhật ký được phân tích cú pháp thành các khóa nhật ký, chuỗi
khóa nhật ký phản ánh một đường dẫn thực thi dẫn đến thứ tự thực thi cụ thể đó của
các câu lệnh in nhật ký. Gọi mi biểu thị giá trị của khóa ở vị trí thứ i trong chuỗi khóa
nhật ký.
𝑚𝑖 có thể lấy một trong n khóa có thể có từ K và phụ thuộc nhiều vào các khóa gần
đây nhất xuất hiện trước 𝑚𝑖 .
Chúng ta có thể lập mơ hình phát hiện bất thường trong chuỗi khóa nhật ký như
một bài tốn phân loại nhiều lớp, trong đó mỗi khóa nhật ký riêng biệt xác định một

lớp. Cho DeepLog như một bộ phân loại nhiều lớp dựa trên ngữ cảnh gần đây. Đầu
15


vào là lịch sử của các khóa nhật ký gần đây và đầu ra là phân phối xác suất trên n khóa
nhật ký từ K, đại diện cho xác suất để khóa nhật ký tiếp theo trong chuỗi là khóa 𝑘𝑖 K.
Hình 2 tóm tắt thiết lập phân loại. Giả sử t là id trình tự của khóa nhật ký tiếp
theo xuất hiện. Đầu vào cho phân loại là một cửa sổ w của h khóa nhật ký gần đây
nhất. Đó là, 𝑤 = {𝑚𝑡−ℎ , … , 𝑚𝑡−2 , 𝑚𝑡−1 }, trong đó mỗi 𝑚𝑖 nằm trong K và là khóa nhật
ký từ mục nhập nhật ký 𝑒𝑖 . Lưu ý rằng cùng một giá trị khóa nhật ký có thể xuất hiện
nhiều lần trong w. Đầu ra của giai đoạn huấn luyện là một mơ hình của phân phối xác
suất có điều kiện 𝑃𝑟 [𝑚𝑡 = 𝑘𝑖 |𝑤] cho mỗi 𝑘 𝑖 ∈ 𝐾(𝑖 = 1, … , 𝑁). Giai đoạn phát hiện
sử dụng mơ hình này để đưa ra dự đoán và so sánh kết quả dự đốn với giá trị khóa
nhật ký quan sát thực sự xuất hiện.

Hình 2.2 Tổng quan về mơ hình phát hiện bất thường khóa log.
Training stage
Dựa vào một phần nhỏ các mục nhập nhật ký được tạo ra bởi quá trình thực thi
bình thường của hệ thống cơ bản. Đối với mỗi chuỗi nhật ký có độ dài h trong dữ liệu
đào tạo, DeepLog cập nhật mơ hình của nó cho phân phối xác suất có 𝑘 𝑖 ∈ K là giá
trị khóa log tiếp theo.
Ví dụ: giả sử một tệp nhật ký nhỏ là kết quả của quá trình thực thi bình thường
được phân tích cú pháp thành một chuỗi các khóa nhật ký: {𝑘22 , 𝑘5 , 𝑘11 , 𝑘9 , 𝑘11 , 𝑘26 }.
Với kích thước cửa sổ h = 3, chuỗi đầu vào và cặp nhãn đầu ra để đào tạo DeepLog sẽ
là: {𝑘22 , 𝑘5 , 𝑘11 → 𝑘9 }, {𝑘5 , 𝑘11 , 𝑘9 → 𝑘11 }, {𝑘11 , 𝑘9 , 𝑘11 → 𝑘26 }.
Detectiom stage
Phát hiện bất thường trong cài đặt trực tuyến, phát trực tuyến.
Đầu vào gửi 𝑤 = {𝑚𝑡 − ℎ, … , 𝑚𝑡 − 1},
Đầu ra là phân phối xác suất Pr [𝑚𝑡 |𝑤] = {𝑘1 : 𝑝1 , 𝑘2 : 𝑝2 , … , 𝑘𝑛 : 𝑝𝑛 } mô tả xác
suất mỗi kháo log từ k đến dưới dạng giá trị khóa nhật ký tiếp theo.

Sắp xếp các khóa nhật ký K có thể có dựa trên xác suất Pr [mt | w] của chúng
và coi một giá trị khóa là bình thường nếu nó nằm trong số các ứng cử viên hàng
đầu.

16


2.5.1.1 Mơ hình ngơn ngữ N-gram truyền thống
Mỗi khóa nhật ký được xem như 1 từ được lấy từ K từ vựng.
N-gram là mơ hình hóa ngơn ngữ điển hình các chuỗi dài tùy ý được gán xác
suất.Mỗi chuỗi chỉ bị ảnh hưởng bởi các từ tiền nhiệm gần nhất hơn là toàn bộ lịch sử
𝑃𝑟 (mt = k i |m1 , … , Mt − 1) = 𝑃𝑟 (mt = k i |mt − N, … , Mt − 1)
trong đó N biểu thị độ dài của lịch sử gần đây được xem xét.
Có thể tính tốn xác suất này bằng cách sử dụng số lượng thời gian miễn phí
tương đối từ một kho dữ liệu lớn để cung cấp cho chúng tơi các ước tính khả năng xảy
ra tối đa.
Cho một dãy phím dài {𝑚1 , 𝑚2 , … , 𝑚𝑡 }, có thể ước tính xác suất quan sát khóa
thứ i bằng cách sử dụng tần suất đếm tương đối của {𝑚𝑡 − 𝑁, … , 𝑚𝑡 − 1, 𝑚𝑡 = 𝑘𝑖 } với
phổ lại dãy:
{𝑚𝑡 − 𝑁, … , 𝑚𝑡 − 1}. 𝑃𝑟 (mt = k i |mt − N, … , Mt − 1) = count (𝑚𝑡 − N, … , 𝑀𝑡 −
1, 𝑚𝑡 = 𝑘𝑖 )/count ( 𝑚𝑡 − N, … 𝑚𝑡 − 1).
Để áp dụng phương pháp ta sử dụng N là kích thước cửa sổ lịch sử, đặt h = N ,
trong đó h là kích thước cửa sổ trượt.
2.5.1.2 Phương pháp tiếp cân LSTM
Các mẫu phức tạp và xen kẽ các mục nhật ký từ các tác vụ đồng thời trong nhật
ký tem hệ thống có thể làm cho mơ hình ngơn ngữ truyền thống kém hiệu quả hơn. Do
đó, DeepLog sử dụng mạng nơ-ron LSTM để phát hiện bất thường từ chuỗi khóa nhật
ký.
Cho một chuỗi khóa log, mạng LSTM được cài đặt để tối đa hóa xác suất có ki
∈ K là giá trị khóa log tiếp theo bị ảnh hưởng bởi chuỗi dữ liệu huấn luyện. Nói cách

khác, nó học phân phối xác suất Pr(𝑚𝑡−ℎ , … , 𝑚𝑡−2 , 𝑚𝑡−1 )để tối đa hóa xác suất của
chuỗi khóa nhật ký cài đặt..
Hình 3 minh họa của mơ hình. Phần trên cùng của hình cho thấy một khối LSTM duy
nhất phản ánh bản chất lặp lại của LSTM. Mỗi khối LSTM ghi nhớ một trạng thái cho
đầu vào của nó dưới dạng vectơ có chiều cố định. Trạng thái của khối LSTM từ bước
thời gian trước cũng được đưa vào đầu vào tiếp theo của nó, cùng với đầu vào dữ liệu
(bên ngồi) của nó (mt-i trong ví dụ cụ thể này), để tính tốn trạng thái và đầu ra mới.
Đây là cách thông tin lịch sử được chuyển đến và duy trì trong một khối LSTM.

17


Hình 2.3 Hướng nhìn chi tiết về phát hiện bất thường khóa nhật ký mơ
hình sử dụng LSTM xếp chồng lên nhau.
Một loạt các khối LSTM tạo thành một phiên bản khơng được cuộn của mơ hình
lặp lại trong một lớp thể hiện ở Hình 3. Mỗi ơ duy trì một vectơ ẩn 𝐻𝑡−𝑖 và một vectơ
trạng thái ô C𝑡−𝑖 . Cả hai đều được chuyển đến khối tiếp theo để khởi tạo trạng thái của
nó. Trong bài nghiên cứu đã sử dụng một khối LSTM cho mỗi khóa nhật ký từ một
chuỗi đầu vào w (một cửa sổ gồm các khóa nhật ký h). Do đó, một lớp bao gồm h khối
LSTM chưa được cuộn.
Trong một khối LSTM duy nhất, đầu vào (ví dụ 𝑚𝑡−𝑖 ) và đầu ra (𝐻𝑡−𝑖−1 ) được
sử dụng để quyết định có bao nhiêu trạng thái ơ trước đó C𝑡−𝑖−1 được giữ lại ở trạng
thái C𝑡−𝑖 , cách sử dụng đầu vào hiện tại và đầu ra trước đó để ảnh hưởng đến trạng
thái, và cách xây dựng đầu ra 𝐻𝑡−𝑖 . Điều này được thực hiện bằng cách sử dụng một
tập hợp các chức năng kiểm soát để xác định động thái trạng thái bằng cách kiểm sốt
lượng thơng tin cần giữ từ đầu vào và đầu ra trước đó, và thơng tin để chuyển sang
bước tiếp theo. Mỗi hàm gating được tham số hóa bởi một tập hợp các trọng số được
học. Khả năng biểu đạt của một khối LSTM được xác định bởi số lượng đơn vị bộ nhớ
(tức là số chiều của vectơ trạng thái ẩn H).
Bước cài đặt đòi hỏi phải tìm các phép gán thích hợp cho các trọng số để đầu ra

cuối cùng của chuỗi LSTM tạo ra nhãn (output) đi kèm với các đầu vào trong tập dữ
liệu cài đặt. Trong quá trình train, mỗi cặp đầu vào hoặc đầu ra dần dần cập nhật các
trọng số này. Trong DeepLog, đầu vào bao gồm cửa sổ w gồm h khóa nhật ký và đầu
ra là giá trị khóa nhật ký đứng ngay sau w. Sau khi huấn luyện xong, chúng ta có thể
dự đốn đầu ra cho một đầu vào (𝑤 = {𝑚𝑡−ℎ , … 𝑀𝑡−1 }) bằng cách sử dụng một lớp h
khối LSTM. Mỗi khóa nhật ký trong w được cấp vào một khối LSTM tương ứng trong
18


lớp này.
Nếu xếp chồng lên nhau nhiều lớp và sử dụng trạng thái ẩn của lớp trước làm
đầu vào của mỗi khối LSTM tương ứng trong lớp tiếp theo, nó sẽ trở thành một mạng
nơ-ron LSTM sâu, như ở phần cuối của Hình 3. Để đơn giản, nó bỏ qua một lớp đầu
vào và một lớp đầu ra được xây dựng bởi các sơ đồ mã hóa-giải mã tiêu chuẩn. Lớp
đầu vào mã hóa n khóa nhật ký có thể có từ K dưới dạng vectơ một nóng. Nghĩa là,
một vectơ n chiều ⃗⃗⃗
𝑢𝑖 được xây dựng cho khóa log 𝑘𝑖 ∈ 𝐾, sao cho ⃗⃗⃗
𝑢𝑖 [𝑖] = 1 và ⃗⃗⃗
𝑢𝑖 [ 𝑗 ] =
0 với mọi j, i khác. Lớp đầu ra chuyển trạng thái ẩn € nal thành một hàm phân phối
xác suất bằng cách sử dụng một hàm đa thức chuẩn để biểu diễn 𝑃𝑟 [𝑚𝑡 = 𝑘𝑖 |𝑤] đối
với mỗi 𝑘𝑖 ∈ 𝐾.
2.5.2. Giá trị tham số và sự bất thường về hiệu xuất
Chuỗi khóa nhật ký rất hữu ích để phát hiện các bất thường của đường dẫn thực
thi. Tuy nhiên, một số điểm bất thường không được hiển thị dưới dạng độ lệch so với
đường dẫn thực thi bình thường mà là một giá trị tham số không đều. Các vectơ giá trị
tham số này (đối với cùng một khóa nhật ký) tạo thành một chuỗi vectơ giá trị tham số
và các chuỗi này từ các khóa nhật ký khác nhau tạo thành một không gian đặc trưng
đa chiều rất quan trọng để giám sát hiệu suất và phát hiện bất thường.
DeepLog train mô hình bất thường giá trị tham số bằng cách xem từng chuỗi

vectơ giá trị tham số (đối với một khóa nhật ký) như một chuỗi thời gian riêng
biệt.Trong Bảng 1. Chuỗi thời gian của chuỗi vector tham số của k2 là:{[𝑡2 −
𝑡1 , 0,01], [𝑡′2 − 𝑡′1 , 1]} .Do đó, vấn đề của chúng ta được rút gọn thành phát hiện bất
thường từ dữ liệu chuỗi thời gian nhiều biến thể. Có thể áp dụng lại cách tiếp cận dựa
trên LSTM. Sử dụng một mạng LSTM tương tự như trong Hình 3 để lập mơ hình dữ
liệu chuỗi thời gian nhiều biến thể.
Lưu ý rằng một mạng LSTM riêng biệt được xây dựng cho chuỗi vectơ giá trị tham số
của mỗi giá trị khóa nhật ký riêng biệt.
Input. Đầu vào ở mỗi bước thời gian là vectơ giá trị tham số từ dấu thời gian đó.
Output. Đầu ra là một vectơ giá trị thực làm dự đoán cho vectơ giá trị tham số tiếp
theo, dựa trên chuỗi các vectơ giá trị tham số từ lịch sử.
Chức năng mục tiêu để train. Đối với dữ liệu chuỗi thời gian nhiều biến thể, quá
trình train sẽ cố gắng điều chỉnh trọng số của mơ hình LSTM để giảm thiểu sai số giữa
một dự đoán và một vectơ giá trị tham số quan sát được. Do đó, suy hao bình phương
trung bình được sử dụng để giảm thiểu sai số trong quá trình cài đặt.
Phát hiện bất thường. Phân vùng dữ liệu train thành hai tập con: model training set
và validation set. Đối với mỗi vectơ 𝑣 trong tập validation set, áp dụng mơ hình được
tạo ra bởi tập model training set để tính tốn MSE giữa hành động trước (sử dụng chuỗi
vectơ từ trước 𝑣 trong tập xác nhận) và 𝑣 . Tại mỗi bước thời gian, sai số giữa vectơ
dự đốn và vectơ thực tế trong nhóm xác nhận được mơ hình hóa dưới dạng phân phối
Gaussian. Khi triển khai, nếu sai số giữa một dự đoán và một vectơ giá trị được phục
vụ nằm trong khoảng tin cậy cấp cao của phân phối Gaussian ở trên, thì vectơ giá trị
19


tham số của mục nhập nhật ký đến được coi là bình thường và được coi là bất thường.
Vì các giá trị tham số trong thông báo nhật ký ghi lại các chỉ số trạng thái hệ
thống quan trọng, nên phương pháp này có thể phát hiện nhiều dạng bất thường về hiệu
suất. Ví dụ: một sự bất thường về hiệu suất có thể phản ánh là "chậm lại".
2.5.3. Cập nhật trực tuyến các mơ hình phát hiện bất thường

Dữ liệu train có thể khơng bao gồm tất cả các chức năng thực thi bình thường
có thể có. Hành vi của hệ thống có thể thay đổi theo thời gian. Nên DeepLog cần cập
nhật từng bước trọng số trong các mơ hình LSTM của mình để kết hợp và thích ứng
với các mẫu nhật ký mới. DeepLog cung cấp một cơ chế để người dùng cung cấp phản
hồi. Điều này cho phép DeepLog sử dụng giá trị false positives để điều chỉnh trọng
lượng của nó.
2.5.3.1 Ví dụ
Giả sử h=3 =>chuỗi lịch sử gần đây là: {𝑘1 , 𝑘2 , 𝑘3 }, deeplog dự đốn khóa nhật
ký tiếp theo là 𝑘1 với khả năng xác suất 1, trong khi giá trị khóa nhật ký tiếp theo là
𝑘2 , sẽ là được gắn nhãn là bất thường.
Nếu người dùng phản hồi đây là false positives => input-output {𝑘1 , 𝑘2 , 𝑘3 →
𝑘2 } dùng để cập nhật trọng số và xuất ra 𝑘1 , 𝑘2 với xác suất được cập nhật.
Lưu ý: DeepLog không cần phải được train lại từ đầu. Sau q trình train ban đầu, các
mơ hình trong DeepLog tồn tại dưới dạng vectơ trọng lượng đa chiều sev-eral. Quá
trình cập nhật cung cấp dữ liệu train mới và điều chỉnh trọng số để giảm thiểu sai số
giữa đầu ra mơ hình và các giá trị quan sát thực tế từ các trường hợp false positives.
2.6. Workflow Construction from Multi-task Execution
2.6.1. Tách mục nhật ký khỏi nhiều tác vụ
Tách các mục nhật ký cho các tác vụ khác nhau trong một tệp nhật ký, sau đó
xây dựng mơ hình dịng cơng việc cho từng tác vụ dựa trên chuỗi khóa nhật ký của nó.
Cho thấy, đầu vào của vấn đề là tồn bộ chuỗi khóa nhật ký được phân tích cú pháp từ
tệp nhật ký thơ và đầu ra là một tập hợp các mơ hình quy trình làm việc, một mơ hình
cho mỗi tác vụ được xác định.
Ví dụ: Đối với mỗi phiên bản VM, vòng đời của nó bao gồm tạo máy ảo, dừng
máy ảo, xóa máy ảo và những thứ khác. Các tác vụ này không chồng chéo lên nhau,
tức là VM dừng chỉ có thể bắt đầu sau khi q trình tạo VM hồn tất. Tuy nhiên, cùng
một phím nhật ký có thể xuất hiện trong các tác vụ khác nhau.
2.6.2. Sử dụng mơ hình phát hiện bất thường của deeplog
2.6.2.1 Tách khóa nhật kí
Input: chuỗi các khóa nhật ký

20


Output: xác suất của tất cả các giá trị khóa nhật ký có thể có
Trong đó:
-

h: độ dài

-

w; chuỗi

-

k: khóa nhật ký

Nếu w không thể theo sau 1 giá trị k cụ thể trong quá trình train
 𝑃𝑟 [𝑚𝑡 = 𝑘 |𝑤] = 0
Ngược lại
 𝑃𝑟 [𝑚𝑡 = 𝑘 |𝑤] = 1
Ví dụ:
Giả sử trên một chuỗi “25 → 54”, dự output là “{57: 1.00}”
 “25 → 54 → 57” là từ một nhiệm vụ
Hoặc là khi một dãy w được theo sau bởi một giá trị khóa log từ một nhóm các
khóa khác nhau; xác suất của các khóa này xuất hiện tổng bằng 1.
Xét một chuỗi nhật ký “54 → 57” và giả sử phân phối xác suất dự đoán là “{18: 0.8,
56: 0.2}” => bước tiếp theo có thể là “18” hoặc “56”.
Ví dụ: Nếu hai tác vụ chia sẻ cùng một phân đoạn công việc “54 → 57”, tác vụ đầu
tiên có cụm từ “18 → 54 → 57 → 18” được thực thi 80% thời gian và tác vụ thứ hai

có mẫu “31 → 54 → 57 → 56” được thực hiện 20% thời gian. Điều này sẽ dẫn đến mơ
hình dự đốn “{18: 0.8, 56: 0.2}” dựa trên chuỗi “54 → 57”.
Chúng ta có thể giải quyết vấn đề này bằng cách huấn luyện các mơ hình có độ
dài chuỗi lịch sử khác nhau, ví dụ: sử dụng h = 3 thay vì h = 2 trong trường hợp này.
Trong quá trình xây dựng quy trình làm việc, sử dụng độ dài trình tự nhật ký dẫn đến
dự đốn chắc chắn hơn, ví dụ: trong ví dụ trên, chuỗi “18 → 54 → 57” sẽ dẫn đến dự
đoán {18: 1.00} và chuỗi “31 → 54 → 57” sẽ dẫn đến dự đốn {56: 1.00}.

Hình 2.4 Các ví dụ về việc sử dụng LSTM để phân tách nhiệm vụ và xây
dựng quy trình làm việc.
21


Nếu chúng ta đã loại trừ một chuỗi nhỏ là một phân đoạn được chia sẻ từ các
nhiệm vụ khác nhau (việc tăng độ dài chuỗi để huấn luyện và dự đốn khơng dẫn đến
dự đốn chắc chắn hơn), mục tiêu là tìm ra liệu đa -đầu ra dự đốn khóa được gây ra
bởi sự đồng thời trong cùng một tác vụ hoặc sự bắt đầu của một tác vụ khác. Gọi đây
là điểm phân kỳ.
Quan xát trong Hình 2.4a, nếu điểm phân kỳ được gây ra bởi sự đồng thời trong
cùng một nhiệm vụ, một mơ hình chung là các khóa có xác suất cao nhất trong kết quả
dự đoán sẽ lần lượt xuất hiện và độ chắc chắn (được đo bằng xác suất đối với số lượng
khóa ít hơn) cho các dự đốn sau sẽ tăng lên, vì khóa cho một số chủ đề đồng thời đã
xuất hiện. Dự đoán cuối cùng sẽ chắc chắn sau khi tất cả các khóa từ các chuỗi đồng
thời được đưa vào chuỗi lịch sử.
Mặt khác, nếu điểm phân kỳ là do bắt đầu một nhiệm vụ mới, như trong Hình
4b, thì nhật ký dự đốn (“24” và “26” trong ví dụ) sẽ khơng xuất hiện lần lượt.. Nếu
kết hợp từng khóa nhật ký như vậy vào chuỗi lịch sử, dự đoán tiếp theo là dự đốn xác
định về khóa nhật ký mới (ví dụ: “24 → 60”, “26 → 37”).
2.6.2.2 Xây dựng mơ hình quy trình làm việc
Khi chúng ta có thể phân biệt các điểm diver gence gây ra bởi sự đồng thời

(nhiều luồng) trong cùng một nhiệm vụ và các tác vụ mới, chúng ta có thể dễ dàng xây
dựng các mơ hình dịng cơng việc như được minh họa trong Hình 4a và Hình 4b. Cần
phải bổ sung để xác định các vòng lặp. Việc phát hiện một vòng lặp thực sự là khá đơn
giản. Một vòng lặp ln được hiển thị trong mơ hình dịng cơng việc ban đầu dưới
dạng một chuỗi chưa được cuộn; ví dụ như hình 2.4c. Trong khi chuỗi quy trình cơng
việc này ban đầu là “26 → 37 → 39 → 40 → 39 → 40”, có thể xác định các đoạn lặp
lại dưới dạng thực thi vòng lặp (39 → 40 trong ví dụ này).
2.6.3. Sử dụng phương pháp phân nhóm dựa trên mật độ
2.6.3.1 Tách khóa nhật ký
Phân cụm các khóa nhật ký dựa trên các mẫu đồng xuất hiện và tách các khóa
thành các tác vụ khác nhau khi tỷ lệ đồng xuất hiện thấp.
Xây dựng một ma trận đồng xuất hiện như trong Bảng 2, trong đó mỗi phần tử
𝑝𝑑 (i, j) đại diện cho xác suất xuất hiện hai khóa log 𝑘𝑖 và 𝑘𝑗 trong khoảng cách d trong
chuỗi đầu vào. Cụ thể, đặt f (𝑘𝑖 ) là tần số của ki trong chuỗi đầu vào và fd (𝑘𝑖 , kj) là
tần số của cặp (𝑘𝑖 , 𝑘𝑗 ) xuất hiện cùng nhau trong khoảng cách xa trong chuỗi đầu vào.
Xác định 𝑝𝑑 (𝑖, 𝑗) =

𝑓𝑑 (𝑘𝑖 ,𝑘𝑗 )
𝑑.𝑓(𝑘𝑖)

𝑘1
𝑘1

, cho thấy tầm quan trọng của 𝑘𝑗 đối với 𝑘𝑖 .
…

𝑘𝑗

𝑝𝑑 (1,1)


𝑝𝑑 (1, 𝑗)

22

…

𝑘𝑛