1
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

LƯU THỊ HỒNG QUYÊN

SỬ DỤNG CHUỖI MARKOV ĐÁNH GIÁ
ĐỘ TIN CẬY PHẦN MỀM WEB-BASED

Chuyên ngành: TRUYỀN DỮ LIỆU VÀ MẠNG MÁY TÍNH
Mã số: 60.48.15
Người hướng dẫn khoa học: PGS. TS HUỲNH QUYẾT THẮNG

TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI – 2012
2
MỞ ĐẦU
Trong thời đại ngày nay, hệ thống dựa trên máy tính
thường được sử dụng cho việc bảo vệ và điều khiển trong các
ngành công nghiệp khác nhau như: ngành công nghiệp hạt
nhân, công nghiệpđiện, cơ khí, dân dụng, y tế … Do hệ thống
bộ điều khiển dựa trên phần mềmlà phổ biến nên phần mềm là
nguyên nhân của hầu hết các vấn đề về hệ thống.
Chúng ta biết rằng chất lượng và tuổi thọ của một hệ thống
CHƯƠNG 1: TỔNG QUAN VỀ ĐỀ TÀI
4
1.1 Lý thuyết chuỗi Markov và các ứng dụng trong bài toán
dự đoán
1.1.1 Định nghĩa chuỗi Markov
Chuỗi Markov:Trong toán học, một chuỗi Markov (thời
gian rời rạc), đặt theo tên nhà toán học người Nga: Andrei
Andreyevich Markov, là một quá trình ngẫu nhiên thời gian rời
rạc với tính chất Markov. Trong một quá trình như vậy, quá
khứ không liên quan đến việc tiên đoán tương lai mà việc đó
chỉ phụ thuộc theo kiến thức về hiện tại.
Ta nói rằng dãy các ĐLNN (X
n
) là một chuỗi Markov nếu
với mọi n
1
< < n
k
< n
k+1
và với mọi i
1
,i
2
, ,i

= j|X
n
= i} ; P
ij
(n) = P{X
m+n
= j|X
m
= i} và U(n)=(u
1
(n), , u
d
(n)) là vector hàng d - chiều mô tả
phân bố của X
n
, U = U(0) = (u
1
,u
2
, , u
d
) là vector hàng d -
chiều mô tả phân bố ban đầu (phân bố của X
0
). Ta có một số
tính chất sau:
 P(X
0
= i
0,

, …., S
N
) gọi là tập tất cả
các trạng thái ẩn.
2) A= [a
ij
] xác suất chuyển trạng thái.
3) p= [p
i
] xác suất khởi trạng.
4) q
t
- Trạng thái ở thời điểm t.
5) O
t
(ký hiệu) Quan sát tại thời điểm t.
1.1.2 Tính chất chuỗi Markov
Đặc điểm của một xích Markov được biểu diễn bởi phân
bố điều kiệnP(X
n+1
|X
n
)đó là xác suất chuyển dịch của quy
trình.Xác suất của một chuyển dịnh trong hai, ba, hoặc nhiều
bước hơn được rút ra từ xác suất chuyển dịch một bước và
thuộc tính Markov[25]:
P(X
n+1
|X
n

Tương tự,
P(X
n+3
|X
n
)=
∫

(


)
|

∫

(


|


)
(
(


|



)


(1.6)
1.1.3 Ứng dụng của chuỗi Markov
Các hệ thống Markov xuất hiện nhiều trong vật lí, đặc biệt
là cơ học thống kê. Chuỗi Markov có thể dùng để mô hình hóa
nhiều quá trình trong lí thuyết hàng đợi và thống kê.
PageRank của một trang web dùng bởi Google được định
nghĩa bằng một chuỗi Markov
Chuỗi Markov cũng có nhiều ứng dụng trong mô hình sinh
học, đặc biệt là trong tiến trình dân số.
Một ứng dụng của chuỗi Markov gần đây là ở thống kê địa
chất.
Chuỗi Markov cũng có thể ứng dụng trong nhiều trò game.
Trong ngành quản lý đất đai: người ta còn ứng dụng GIS,
RS và chuỗi Markov vào phân tích sự thay đổi sử dụng đất
(land use change).
1.2 Tổng quan và giới hạn những dự đoán ban đầu về độ
tin cậy của phần mềm trong giai đoạn thiết kế kiến trúc.
1.2.1 Giới thiệu
Độ tin cậy miền giới hạn an toàn và hệ thống độ tin cậy có
liên quan là những điều quan trọng hàng đầu dựa trên hệ thống
7
máy tính. Vì thế, phần mềm sử dụng trong các hệ thống phải
đáng tin cậy.
Những lý do mà các mô hình độ tin cậy này không đủ mạnh
để vượt trội trong việc loại bỏ các sự cố trong môi trường phần
mềm là:
1) Các quan niệm sai lầm về hiện tượng lỗi và hỏng hóc. [20]

đưa ra cái nhìn tổng quan về các phương pháp tiếp cận hiện có
của phần mềm dự đoán độ tin cậy ban đầu, và mô tả tính thông
dụng và khác biệt của những phương pháp tiếp cận này. Sau
đó, chúng ta đã dự kiến các phương pháp tiếp cận mà có thể
giúp trong việc giải quyết các hạn chế được trình bày.
CHƯƠNG 2: PHƯƠNG PHÁP KỊCH BẢN DỰ
ĐOÁN ĐỘ TIN CẬY PHẦN MỀM
9
2.1. Giới thiệu chung
Độ tin cậy là một đặc trưng động của hệ thống, nó là một
hàm của số các thất bại phần mềm
Kỹ thuật độ tin cậy phần mềm là một khía cạnh quan
trọng của rất nhiều những nỗ lực phát triển hệ thống.
Kịch bản (Scenarios) đã được sử dụng phổ biến như là
phương thức để thu thập các yêu cầu hành vi hệ thống.
Cách tiếp cận này bắt đầu với một tập hợp các scenarios và
high-level message sequence chart – biểu đồ trình tự tin nhắn
cấp cao (HMSC).
2.2. Quy trình chi tiết kỹ thuật kịch bản
2.2.1 Scenarios (Các kịch bản)
Các ký hiệu Scenario ví dụ như Message Sequence Charts
(Biểu đồ trình tự tin nhắn) được sử dụng ở giai đoạn đầu phát
triển chotài liệu. Các kịch bản một phần mô tả về cách các
thành phần tương tác để cung cấp chức năng mức hệ
thống.Khái niệm cơ bản của sự hợp thành kịch bản là các kịch
bản đơn có thể được sử dụng như xây dựng các khối mô tả mới
phức tạp hơn, kịch bản hơn. Dãy hành vi đơn giản được mô tả
bằng cách sử dụng Basic Message Sequence Charts (BMSCs).
(Biểu đồ tuần tự tin nhắn cơ bản)BMSC được hình thành bởi
các đường dọc đại diện cho dòng thời gian thành phần và mũi

một sự dẫn ra bởi C của một dịch vụ được cung cấp bởi C'.
iv. Chỉ có duy nhất một kịch bản ban đầu và một kịch bản cuối
cùng cho hệ thống trong HMSC.
2.3.1. Các chú thích kịch bản
Trong bước đầu tiên, chúng tadiễn giải các kịch bản (tức
là, HMSC và các BMSCs) với hai loại xác suất,xác suất của
quá trình chuyển đổi giữa các kịch bản PTS
ij
và độ tin cậy của
các thành phần RC.
2.3.2. Tổng hợp xác suất LTS
Bước thứ hai trong phương pháp này là tổng hợp một xác
suất LTS từ các thông số kĩ thuật của kịch bản được diễn giải.
Bao bao gồm các bước sau:
1) Đối với mỗi thành phần C
i
và mỗi S
j
BMSC, một hệ thống
chuyển tiếp có nhãn (LTS) C
i
S
j
được dựng bằng cách chiếu các
chế độ địa phương của C
i
trong S
j
.
2) Đối với mỗi thành phần C

2.3.3. Dự đoán độ tin cậy
Trong bước cuối cùng của phương pháp dự đoán, mô hình
kiến trúc tổng hợp trong bước trước đó được giải thích giống
như một mô hình Markov, và chúng tôi áp dụng phương pháp
của Cheung để tính toán độ tin cậy.Đặc biệt, sự chuyển đổi
trọng lượng xác suất của mô hình kiến trúc được ánh xạ vào
một ma trận vuông quá trình chuyển đổi M' mà hàng nhập vào
tổng bằng 1.Điều này được sử dụng như ma trận M' được miêu
tả tại mục 2.2, với N = {E, -1, 0, 1, , n - 1} tập hợp của các
trạng thái trong tổng hợp LTS, thiết bị đầu cuối E của trạng
thái thực hiện chính xác (trạng thái tương ứng C được mô tả
trong mục 2.2), trạng thái lỗi thiết bị đầu – 1 (trạng thái F của
mục 2.2), và trạng thái n - 1 mà từ đó chuyển đổi sang trạng
13
thái E được thực hiện khi hành động kết thúc (trạng thái N
n

của mục 2.2).
2.4. Kịch bản được bao hàm
Kịch bản mô tả hai khía cạnh của một hệ thống.Một mặt,
chúng mô tả một tập hợp các dấu hiệu của hệ thống có xu
hướng bộc lộ ra ngoài.Mặt khác, nó mô tả các thành phần sẽ
cung cấp mức độ chức năng của hệ thống và giao diện của
chúng.
Sự tồn tại của scenario bao hàm như là một kết quả của
mối quan hệ chặt chẽ giữa hành vi và kiến trúc trong kịch bản
dựa trên sự hỗ trợ về thông số kĩ thuật.
CHƯƠNG 3: ĐÁNH GIÁ ĐỘ TIN CẬY PHẦN
MỀMWEB-BASED
3.1 Đề xuất áp dụng phương pháp kịch bản và chuỗi

hình Markov là một ma trận, được gọi là ma trận chuyển đổi,
15
trong đó các hàng các cột tương ứng với các trạng thái và giá
trị P
ij
trong hàng thứ i, cột thứ j là xác suất chuyển đổi từ
trạng thái isang trạng tháij. Chúng ta sử dụng ma trận biểu
diễn chuyển đổi trong các thuật toán tính độ tin cậy.
3.1.3 Mô hình hình thức
Web là một hệ thống phản ứng, đặc trưng bởi hai thuộc
tính quan trọng sau :
Đồng bộ hóa kích thích:.
Đồng bộ hóa phản ứng:.
Các đối tượng Web truyền tín hiệu thông qua các tin nhắn.
Một tin nhắn từ một đối tượng này đến một đối tượng khác
trong hệ thống được gọi là một tín hiệu và được đại diện bởi
một bộ dữ liệu <e
i
, p
i
, t
i
>, biểu thị rằng biến cố e
i
xảy ra ở thời
gian t
i
, tại cổng p
i
. Trạng thái của một đối tượng ở bất kỳ thời

⎯

OS
1
〈


,

,

〉

⎯
⎯
⎯
⎯
⎯

………
16
Thông thường, các hệ thống Web là không kết thúc, do đó, một
phép toán nói chunglà một chuỗi vô hạn.
3.1.4 Một mô hình Web đơn giản.
Chúng tôi trừu tượng kiến trúc nhiều lớp của các ứng dụng
Web vào ba thành phần Web: người sử dụng, trình duyệt, và
máy chủ (User, Browser, Server).
3.1.4.1 Mô hình User
3.1.4.2 Mô hình Browser
3.1.4.3 Mô hình Serv

1
, … l
n
} của cùng loại (chia sẻ/ nội bộ) từ trạng thái i tới
trạng thái j, thì quá trình chuyển đổi nói trên được thay thế
bởi một quá trình khác có xác suất là:
P= 1 – (1- P{l
1
}) x … (1- P{l
n
}) (3.1)
3. Xác suất của tất cả các quá trình chuyển đổi cho một trạng
thái phải có tổng là 1.
Bước 2: Mô hình Markov cho cặp đối tượng
*Thuật toán ma trận chuyển đổi cho Máy sản xuất đồng
bộ
18
Thuật toánSPM
Bước 1:P=1; // tổng hàng
Bước 2:x
1
= { e| e là sự kiện được chia sẻ xảy ra ở trạng
thái i (P) và ở trạng thái j (Q)}
x
2
= {e| e là sự kiện bên ngoài được xảy ra ở trạng thái
i(P)} U {e|e là sự kiện bên ngoài xảy ra ở trạng thái j(Q)}
Bước 3: If x
1
≠ ∅ // Tính toán các xác suất cho quá trình

2
≠ ∅ // Tính toán các xác suất cho các quá
trình chuyển đổi do các sự kiện nội bộ
Then NF’ =0 (Hệ số tiêu chuẩn hóa); set
2
=∅
Với mỗi sự kiện e ∈ x
2
, if e∈ M
1
then
Tìm trạng tháii’ (M
1
)sao choi

→ i’;
y=y ∩{i’, j} if {i’, j} ∉ y;
19
M[(i,j)(i’,j)]= M
1
[i,i’]; NF’ = NF’ +M[(i,j)(i’,j)];
Set
2
=set
2
∩(i,i’)
Else
Tìm trạng tháij’ (M
2
) sao cho j

′
,′)]
′

Bước 7.If x
1
≠ ∅ ∧ x
2
=∅
For each (i’, j’) )∈ set
1
do
M[(i,j),(i’,j’)]=
[
(
,
)
,(
′
,′)]


Bước 8. If x
1
≠ ∅ ∧ x
2
≠ ∅
For each (i’, j’) )∈ set
2
do

Reliability(System)=min{Reliability(Subsystem
i
)}
i
m
(3.4)
3.2 Thử nghiệm công cụ đánh giá độ tin cậy của phần mềm.
3.2.1 Giới thiệu công cụ SMERFS
SMERFS là một công cụ để mô hình hóa độ tin cậy phần
mềm. Công cụ này đã phát triển và ra mắt một số phiên bản,
mới nhất là SMERFS V.
SMERFS cho phép người dùng nhập dữ liệu, chỉnh sửa và
chuyển đổi dữ liệu, xác định sự phù hợp của mô hình bằng
cách sử dụng các kỹ thuật thống kê và đồ họa, đưa ra dự đoán
độ tin cậy khác nhau dựa trên mô hình được trang bị, và cố
gắng thử các mô hình khác nhau nếu mô hình ban đầu chứng
minh không đầy đủ.
21
3.2.2 Cài đặt và cách sử dụng phần mềm
3.2.2.1Càiđặt
3.2.2.2Hướngdẫnsửdụng
3.3 Thử nghiệm và đánh giá kết quả.
3.3.1 Mô tả các Use-case của website thương mại điện tử
Để đơn giản trong quá trình xử lý nhưng vẫn thể hiện được
tư tưởng của một chương trình phần mềm website thương mại
điện tử, hệ thống có 3 Actor chính
1) Admin
2) Customer
3) ClientCustomer
4) Các hệ thống khác

6) Tìm kiếm sản phẩm
7) Xem thông tin sản phẩm
8) Quản lý giỏ hàng
9) Quản lý đặt hàng
10) Xem tin tức
23
3.3.2 Thử nghiệm và đánh giá kết quả

Hình 3.18 Giao diện tính toán tổng hợp cho một hệ
thống website

Hình 3.19 Đồ thị biểu diễn dữ liệu với đường dự đoán
(đường cân bằng) cho hệ thống website
24

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
A. Kết luận
Luận văn tốt nghiệp với đề tài: “Sử dụng chuỗi Markov
đánh giá độ tin cậy phần mềm web-Based” đã cơ bản hoàn
thành. Đề tài đã giải quyết được các vấn đề sau:
- Tìm hiểu, nghiên cứu lý thuyết chuỗi Markov và ứng dụng
trong đánh giá, dự đoán độ tin cậy phần mềm.
- Tìm hiểu, làm chủ các công cụ ứng dụng chuỗi Markov để
đánh giá chất lượng phần mềm.
- Xây dựng phương pháp và ứng dụng trong đánh giá độ tin
cậy phần mềm Web-Based (Web-Based Software).
Các kết quả chính đạt được trong đề tài:
1. Đề tài mới chỉ đi sâu nghiên cứu về mô hình chuỗi Markov.
Trên cơ sở đó ứng dụng vào việc phân tích đánh giá chất lượng
độ tin cậy phần mềm Web-Base.