Nghiên cu k thut sinh ca kim th t mô hình
máy hu hn trng thái
Research the method to generate test case from finite state machine model
 trang 58 tr. +  Thùy Linh i hc Công ngh
Lu: Công ngh phn mm; Mã s: 60 48 10
Cán b ng dn khoa hc: 
o v: 2012 Abstract. Trình bày v mô hình FSM và cách biu din mt FSM theo kiu li th hoc
dng bng. Ngoài ra, trình bày mt s tính cht ca mt máy hu hn trng thái. Nghiên cu mt
s nh chui kim chng trng thái ci vào  ra duy
nht (UIO), chui phân bit (DS), chuu mi quan h mô phng ca hai
FSM và kim th s mô phng ca hai FSM và tng hp các lng gt FSM.
 bao ph ca mô hình máy hu hn trng thái và la ch bao ph tt nh làm
ti sinh ca kim thm th   c th 
ng kt nhng kt qu ng phát trin nghiên cu tip theo.

Keywords: Công ngh phn mm; Kim th phn mm; K thut sinh ca; Mô hình máy

Content.
I. C1.  
A. 1.1. Đặt vấn đề
Hin nay có rt nhiu h thng có th c t t máy tr thng

cu tip theo.

II. C2. MÁY    THÁI (FSM)
A. 2.1. Định nghĩa FSM
Máy hu hn trng thái là mt b M = <S, I, O, s
o

 
 
 
 s
0
là tr
 
 
B. 2.2. Biểu diễn FSM
1) 2.2.1. Biểu diễn kiểu liệt kê
Cho FSM M
1
= <S, I, O, s
0

 
0

 
1
, s
2
, s

∈ S; ∀ i
k
∈ I; ∀o
t
∈ O

2) 2.2.2. Biểu diễn bằng đồ thị
Các FSM và các yu t c

c biu din b . 

 


gm:
 
























 

Ví d v biu din b th ca FSM M
1
:
Hình 2.1: Minh họa việc biểu diễn FSM M
1
bằng
đồ thị
3) 2.2.3. Biểu diễn bằng dạng bảng
Mt FSM có th biu din bng dng bng, b





, y) 
j
 j và ∀s
j
∈ M.
2) 3.1.2. Thuật toán sinh cây UIO
Input: 
Output: cây UIO.
Phương pháp: Thc hic sau
Bước 1: t ψ là mt tp các vec-ng da vec-u
c gán là không kt thúc.
Bước 2: Tìm mt phn t ∈ ψ 
Nu không tn ti phn t y thì thut toán kt thúc.
Bước 3: 
i
/b
i
ψ vi ∀a
i
/b
i
∈ L.
p nht cây UIO.
Bước 4: N
i
/b
i
 Bước 3 thu kin ct t
mt nút kt thúc.
Bước 5: Quay lc 2.

11010
00000
B. 3.2. Chuỗi phân biệt (Distinguishing sequence)
1) 3.2.1. Một số khái niệm
Cho FSM M = <S, I, O, s
0



i

j
∀s
i
, s
j
∈ S và s
i
= s
j
.
2) 3.2.2. Thuật toán sinh cây DS
Input : M = <S, I, O, s
0

Output: Cây DS.
Phương pháp: 
Bước 1: ψ ψ 

Bước 2: ψ ∈ ψ 

Chuỗi ra
A
11
00
B
11
11
C
11
10
D
11
01

C. 3.3. Chuỗi đặc trưng (Characterizing sequence)
1) 3.3.1. Một số khái niệm
 
trong FSM M
 -
k
là

1
, W
2
, , W
n
.

n

A. 4.1. Mối quan hệ mô phỏng của hai FSM
⊆ S
1
× S
2
là quan h mô phng t FSM M
S
= <S
1
, I, O, s
01

1

1
> thành FSM M
I
= <S
2
, I, O,
s
02

2

2
> nu:
1. (s
01
, s

S.
t M
I
M
S
, hay nói cách khác M
I
mô phng M
S
. Tuy nhiên vic
t M
I
có th có li dn M
I
không mô phng M
S
n tip theo s 
kim th  kim th xem M
I
có mô phng M
S
hay không.
B. 4.2. Kiểm thử dựa trên mô hình FSM
Mt h thc t bi FSM M
S
t bng M
I
. Kim th xem h thng M
I
t

ng cc th hi
Hình 4.3: Mô hình khái niệm kiểm thử với việc kiểm chứng trạng thái
C. 4.3. Một số lỗi thường gặp khi kiểm thử sự mô phỏng của 2 FSM
Khi có bc t FSM M
S
= < S
1
, I, O, s
01

1

1
> và h thng cài t FSM M
I
= < S
2
, I, O, s
02

2
,

2


∃
1
(s
1


2
(s
2
, a)]
∃
1
(s
2


2
(s
2

∃
1
(s
2
, x) =

2
(s
2

S


I
có mô phng M
S

y qua bng tng hp 4.1 ta có th thy mt s lng gp khi kim th s mô phng ca hai

1. Ln output: Output ng vi transition t s
2
s
2
a M
I
không ging vi output ng
vi transition s
1
s
1
a M
S
.
2. Ln trng thái:
- Tru ca M
I
không mô phng tru ca M
S

- Trng thái tip theo ca mt chuyn trng thái ca M

Nu n không phi là node lá thì tip tc xây dng nhánh này bng cách thêm mt nhánh t n ti
node mi m nu d(n, x) = m. Gán nhãn ca nhánh này là x/y v
Lp lc này vi tt c các nút  mc k

Tip theo ta tìm tp bao ph trng thái P t cây kim th. Tp bao ph trng thái P = {p
1
, p
2

n
} là
mt tp tt c các chui con p
i
th hing dn con bu t nút gc trong cây kim th, ni các
nhãn theo các cnh cng dc mt chui thuc P.
B. 5.3. Kỹ thuật sinh ca kiểm thử
Ca kim th tt là ca kim th có th bao ph toàn b mô hình FSM. Do vy ta ch bao ph chuyn
trng thái, n bao ph là 100% thì có th phát hic tt c các li v output và các li v trng
thái.
1) 5.1.3. Khuôn dạng ca kiểm thử
Thông ng khuôn dng ca mt ca kim th bao gm thông tin sau:
Bảng 5.1: Khuôn dạng ca kiểm thử
TC_ID
Pre-Con
Input
Expected
Output
Post-Con
TC_1
Thông tin tin

S
hay
không ta dùng chui kim ch kim th. Vì vu vào ca ca kim th này là chui kim
chng, kt qu i là output sinh ra t FSM M
S
.
D. 5.3. Ví dụ
Cho FSM M
S
c biu din b th sau: Hình 5.5: Đồ thị biểu diễn FSM M
SVà FSM M
I1
là bt ca FSM M
S
, gi s 

Hình 5.6: Mô hình máy hữu hạn trạng
thái M
I1
m th
 kim th xem M

, ta có kt qu kim th  Bảng 5.6: Kết quả kiểm thử của FSM M
I1

TC_ID
Pre-Con
Input
Expected Output
Actual result
Post-Con
TC0-1
N/A
11
00
00
A
TC1-11
Passed TC0-
011
011
011
A
TC1-21
Passed TC0-
111
001
001
A

TC3-21
Passed TC2-
10111
00100
00100
A

Nhn xét:
Theo kt qu kim th trên thì mi Actual result u giExpected Output ti ca kim th
g ng nên FSM M
I1
mô phng FSM M
S
.
VI. C6.  
Kim th phn mm, mt ni dung nghiên cc trin khai t rt sm và không phi là mi m i
vi th gi cp thit cho vic nâng cao chng phn mm.
Trong lu, tác gi ng quan v mô hình máy hu hn tr
cu v nh chui kim chng trnh Unique Input  Output
sequence, Distingguishing sequence, Characterizing sequence. Lu 
kim th da trên mô hình máy hu hn trng thái và dùng khái nim mô ph
 n ca h thng so vc t.
Luu v  bao ph ca mô hình máy hu hn trng thái, và t 
pháp sinh ca kim th  kim th xem h tht có mô phng bc t phn mm da trên mô
hình máy hu hn trng thái hay không.
ng phát trin tip theo ca lui tim th sao cho s ca
kim th là ít nh bao ph là ln nht có thng thi, tác gi s xây dng m
trình sinh ca kim th t ng dc ci tin.