Đ I H CăĐÀăN NG
TR

NGăĐ I H C BÁCH KHOA

---------------------------------------

PH MăVĔNăTệNH

PH MăVĔNăTệNH

KHOA H C MÁY TÍNH

NG D NG GI I THU T DI TRUY N SINH D
LI U TH BAO PH C U TRÚC C AăCH
NGă
TRÌNH JAVA

LU NăVĔNăTH CăSƾ
KHOA H C MÁY TÍNH

KHỐ 32
ĐƠăN ng ậ Nĕm 2018


Đ I H CăĐÀăN NG
TR

NGăĐ I H C BÁCH KHOA

---------------------------------------

PH MăVĔNăTệNH

NG D NG GI I THU T DI TRUY N SINH D LI U TH
BAO PH C U TRÚC C AăCH
NGăTRỊNHăJAVA

Chuyên ngành: KHOA H C MÁY TÍNH
Mã s : 8480101

LU NăVĔNăTH CăSƾ

NG

IăH

NG D N KHOA H C:

PGS.TS. Nguy n Thanh Bình

ĐƠăN ng ậ Nĕmă2018


-i-

L IăCAMăĐOAN
Tôiăxinăcamăđoan rằngănh ng n iădungătrongălu năvĕnănƠyălƠ nghiênăc uăc aăriêngă
tôi, do tôi t ăth căhi năd iăs ăh ng d nătr căti păc aăPGS.TS.ăNguy năThanhăBình.
TrongătoƠnăb ălu năvĕn,ănh ngăn iădungăđ cătrìnhăbƠyălƠăc aăchínhăcáănhơnătơiăho călƠă
đ cătổngăh păt ănhi uăngu năt ăli uăkhác.ăM iătƠiăli u thamăkh oădùngătrongălu năvĕnă

đ uăđ cătríchăd nărõărƠngătênătác gi ,ătênăcơngătrình,ăth iăgian,ăđ aăđi măcơngăb .
Tơi xin hồn tồn chịu trách nhiệm và chịu mọi hình th c kỷ luật theo
quy định cho lời cam đoan này.
NG

IăCAMăĐOAN

Ph măVĕnăTính


-ii-

L IăC Mă N
L iăđ u tiên tôi xin trân tr ng g i l i c mă năđ n cán b , giáo viên c a PhòngăĐƠoă
t o và Khoa Công ngh thông tin, Tr ngăĐ i h c Bách khoa ĐƠăN ng đưăt o m iăđi u
ki n thu n l i cho tôi trong th i gian nghiên c u và hồn thành Lu năvĕn.
V i lịng kính tr ng và bi tă năsơuăs c, tơi xin g i l i c mă năđ n th yăgiáoăh ng
d n PGS. TS. Nguy năThanhăBìnhăđưăt nătìnhăgiúpăđỡ tơi xây d ngăýăt ng nghiên c u,
cũngănh ătrongăsu t quá trình nghiên c u và hồn thi n Lu năvĕn.ăTh yăđưăln ng h ,
đ ng viên và hỗ tr nh ngăđi u ki n t t nh tăđ tơi hồn thành Lu năvĕn.ăBênăc nhăđó,ă
tơiăcũngăxinăg i l i c mă năđ n Ti năsƿăLêăTh Mỹ H nh và b năbè,ăđ ng nghi păđưăgiúpă
đỡ, hỗ tr tơi nghiên c u, hồn thành lu năvĕn.
Xin chân thƠnh c mă n các th y, cô trong H iăđ ngăđư cho tơi nh ngăđóng góp q
báuăđ hoƠn ch̉nh lu năvĕnănƠy.
Xin trân tr ng c mă n!
TÁC GI

Ph măVĕnăTính



-iii-

M CăL C
L IăCAMăĐOAN ......................................................................................................i
L I C Mă N .......................................................................................................... ii
M C L C .............................................................................................................. iii
DANH M C CÁC KÝ HI U VÀ CH

VI T T T ........................................... viii

DANH M C CÁC B NG ......................................................................................ix
DANH M C CÁC HÌNH V VĨăĐ TH ............................................................. x
M Đ U .................................................................................................................. 1
1. Lý do ch năđ tài .............................................................................................. 1
2. M căđíchănghiênăc u ........................................................................................ 3
3. M c tiêu và nhi m v nghiên c u .................................................................... 3
a) M c tiêu ........................................................................................................ 3
b) Nhi m v ...................................................................................................... 3
4.ăĐ iăt
5.ăPh

ng và ph m vi nghiên c u .................................................................... 3
ngăphápănghiênăc u .................................................................................. 4

a)ăPh

ngăphápălýăthuy t .................................................................................. 4

b)ăPh


ngăphápăth c nghi m ............................................................................ 4

6. ụănghƿaăkhoaăh c và th c ti n c aăđ tài .......................................................... 4
a)ăụănghƿaăkhoaăh c .......................................................................................... 4
b)ăụănghƿaăth c ti n .......................................................................................... 4
7. B c c c a lu năvĕn .......................................................................................... 5
CH

NGă1.ăC ăS LÝ THUY T ......................................................................... 7

1.1 Ki m th ph n m m........................................................................................ 7
1.1.1 Khái ni m v ki m th ph n m m ........................................................... 7
1.1.2

Cácăb

c ki m th ............................................................................... 7

1.1.2.1 L p k ho ch ki m th ...................................................................... 7
1.1.2.2 Thi t k ca ki m th ......................................................................... 8
1.1.2.3 Th căthiăch

ngătrình ....................................................................... 8


-iv1.1.2.4 Phân tích k t qu ki m th và l p báo cáo ....................................... 8
1.1.3 Các ho tăđ ng ki m th ph n m m ......................................................... 9
1.1.4 Các kỹ thu t ki m th ph n m m .......................................................... 10
1.2 Ki m th c u trúc.......................................................................................... 11
1.2.1 Khái ni m v đ th ki m th ................................................................ 11

1.2.2 Tiêu chí bao ph .................................................................................... 12
1.2.3 Ki m th d aătrênăđ th lu ngăđi u khi n ............................................ 13
1.2.4 Ki m th d aătrênăđ th lu ng d li u.................................................. 14
1.3 Gi i thu t di truy n ....................................................................................... 15
1.3.1 Các khái ni m ........................................................................................ 15
1.3.1.1 Khái ni m v Gi i thu t di truy n................................................... 15
1.3.1.2 Các toán t di truy n ....................................................................... 15
1.3.1.3 Các công th c c a gi i thu t di truy n ........................................... 16
1.3.1.4 Các tiêu chu năđ k t thúc thu t toán ............................................. 16
1.3.1.5ăS ăđ c u trúc gi i thu t di truy n .................................................. 17
1.3.2 Kh i t o qu n th ................................................................................... 18
1.3.3 Hàm m c tiêu ......................................................................................... 18
1.3.4 Cách t o qu n th m i ........................................................................... 19
1.3.4.1 L a ch n theo t̉ l bánh xe Roulette .............................................. 19
1.3.4.2 L a ch n x p h ng .......................................................................... 19
1.3.4.3 L a ch nătheoăc ăch l y m u ng u nhiên ..................................... 20
1.3.4.4 L a ch nătranhăđ u ......................................................................... 20
1.4 K t lu n ......................................................................................................... 20
CH

NGă2.ăKI M TH

2.1 Gi i thi uămôiătr

C UăTRÚCăTRONGăMỌIăTR

NG JAVA ............ 21

ng ngơn ng Java ........................................................... 21


2.1.1 Java là gì? ............................................................................................... 21
2.1.2

ng d ng c a Java ................................................................................. 21

2.1.3 Nh ngăđ căđi măc ăb n c a Java .......................................................... 21
2.1.3.1ăH

ngăđ iăt

ng hoàn toàn ............................................................ 21


-v2.1.3.2ăĐ c l p ph n c ng và h đi u hành ................................................ 22
2.1.3.3 Ngôn ng thông d ch ...................................................................... 22
2.1.3.4ăC ăch thu gom rác t đ ng ............................................................ 23
2.1.3.5ăĐaălu ng .......................................................................................... 23
2.1.3.6 Tính an tồn và b o m t .................................................................. 23
2.1.4 Java Virtual Machine (JVM) ................................................................. 24
2.1.5 Các kh iăđi u khi năc ăb n trong Java .................................................. 24
2.2 Tổngăquanăph

ngăphápăki m th c u trúc d aătrênăđ th lu ngăđi u khi n

25
2.3 Xây d ngăđ th lu ngăđi u khi n t mã ngu n Java ................................... 26
2.4 Xây d ng t p l trình ki m th ..................................................................... 27
2.4.1 Xây d ng t p l trìnhăđ c l p ................................................................ 27
2.4.2 Xây d ng l trình ki m th vịng l p ..................................................... 28
2.4.2.1 L trình ki m th cho vịng l păđ n ............................................... 29

2.4.2.2 L trình ki m th cho vịng l p l ng nhau ..................................... 30
2.5 K t lu n ......................................................................................................... 31
CH

NGă3.ăGI I PHÁP SINH D

LI U TH

D A TRÊN GI I THU T DI

TRUY N ....................................................................................................................... 32
3.1 Phát bi uăbƠiătoánăđ t ra ................................................................................ 32
3.2 Bi u di n nhi m s c th ................................................................................ 32
3.3 Kh i t o qu n th (Initial population) .......................................................... 34
3.4 Xây d ng hàm thích nghi .............................................................................. 34
3.5 L a ch n (Selection) ..................................................................................... 35
3.6 K t h p l i (Recombination) ........................................................................ 36
3.7 L a ch n t iă uă(Elitist) ................................................................................ 37
3.8 Thu t toán tổng quát ..................................................................................... 37
3.9 K t lu n ......................................................................................................... 39
CH

NGă4.ăCĨIăĐ T VÀ TH

NGHI M ......................................................... 40

4.1ăCƠiăđ t gi iăphápăđưăđ xu t .......................................................................... 40


-vi4.2 Tri n khai mô phỏng th c nghi m ................................................................ 43

4.3 K t qu vƠăđánhăgiáăk t qu .......................................................................... 46
4.4 K t lu n ......................................................................................................... 49
K T LU NăVĨăH

NG PHÁT TRI N .............................................................. 50

TÀI LI U THAM KH O ...................................................................................... 51


-vii-

NGăD NGăGI IăTHU TăDIăTRUY NăSINHăD ăLI UăTH ăBAOăPH ă
C UăTRÚCăC AăCH
NGăTRỊNHăJAVA
H căviên: Ph măVĕnăTính
Mưăs :ă8480101, Khóa: K32, Tr

Chun ngành: Khoaăh cămáyătính
ngăĐ iăh căBáchăkhoaă- ĐHĐN

Tómăt tă- Ki măth ăph năm mălƠăho tăđ ngăđóngăvaiătrịăr tăquanătr ngănhằmăđánhăgiáătínhăđúngă
đ n,ăs ăhoƠnăthi năvƠăb oăđ măch tăl ngăph năm m.ăVi căki măth ăph năm măt năchiăphíăr tăl n,ă
nênăvi căsinhăd ăli uăth ăt ăđ ngăcóăkh ănĕngăphátăhi nălỗiăc aăch ngătrìnhăcaoăs ăgiúpănơngăcaoă
hi uăqu ăđ iăv iăvi căgi măchiăphíăvƠătĕngăch tăl ngăki măth .
Ki măth ăc uătrúcălƠăkỹăthu tăki măth ăchoăphépăki mătraăc uătrúcăbênătrongăc aăph năm măv iă
m căđíchăđ măb oărằngăt tăc ăcácăcơuăl nhăvƠăđi uăkhi năs ăđ căth căhi năítănh tăm tăl n.ăT oăd ă
li uăki măth ăđóngăvaiătrịăquanătr ngănh tătrongăki măth ăc uătrúc,ălƠmăsaoăđ ăchúngătaăcóăth ăt oă
raăcácăd ăli uăth ăcóăkh ănĕngăphátăhi nălỗiăcaoănh t,ăđ măb oăcácătiêuăchíăbaoăph ănh :ăbaoăph ă
cơuăl nh,ăbaoăph ăr ănhánh,ăbaoăph ăl ătrìnhăc aăch ngătrìnhăc năk măth .
Lu năvĕnătrìnhăbƠyăkỹăthu tăt oăd ăli uăth ănghi măt ăđ ngăs ăd ngăthu tătoánădiătruy năd aătrênă

đ ăth ălu ngăđi uăkhi năchoăch ngătrìnhăjava.ăKỹăthu tănƠyăd aăvƠoăm iăquanăh ăth ngătr ăgi aăcácă
nútătrênăđ ăth ăđ ăxácăđ nhăm tăhƠmăthíchănghiănhằmăđánhăgiáăd ăli uăki măth ăđ ăgi măchiăphíă
ki măth ăph năm m.ăK tăqu ăth cănghi măchoăth y,ăt păd ăli uăki măth ăđ căsinhăraăm tăcáchăt ă
đ ngănh ngăv năđ măb oăđ tăđ ăbaoăph ăcao,ăđ tăđ ătinăc yătrongăki măch ngătínhăđúngăđ năc a
mưăngu n.
T ăkhóaă- ki măth ăph năm m; ki măth ăc uătrúc; đ ăth ălu ngăđi uăkhi n; tiêuăchíăbaoăph ; thu tă
tốnădiătruy n.

APPLICATION OF GENETIC ALGORITHMS IN GENERATING TEST
DATA COVERAGE JAVA PROGRAM STRUCTURE
Abstract - Software testing is an important action in order to estimate the righteous, completeness
and to assure the quality of software. Software testing cost very high, therefore the auto-generated
test data which helps detection of program errors with high accuracy could help the effectiveness
in the task of reducing software testing cost and improve the quality of testing procedure.
Structural testing is the testing technique allowed verification of the inner structure of program with
the purpose to guarantee every single line of code will be executed at least once. Creation of testing
data plays the most important role in structural testing, for many purpose such as: code coverage,
conditional state coverage and programming execution coverage.
In this thesis, it will present the technique of automatic test data generating method using genetic
algorithms based on the control flow graph for Java program. This technique is mostly based on the
relationship between nodes in the graph to define an accommodation function with the purpose of
judging test data for testing cost reduction. The practical results show that the data set is although
automatic generated however guarantees a high level of coverage and meet the standard
requirement of confidence in the process of assuring the righteous of codes.
Keywords - software testing; structural testing; control flow graph; coverage criteria; genetic
algorithms.


-viii-


DANHăM CăCÁCăKụăHI UăVÀăCH ăVI TăT T
Stt T vi t t t

T /c mt g c

1

GA

Genetic Algorithm

2

CFG

Control Flow Graph

3

NST

Nhi m s c th

4

JVM

Java Virtual Machine

5


JRE

Java Runtime Environment

6

CNTT

Công ngh thông tin


-ix-

DANHăM CăCÁCăB NG
B ng 4.1.

B ng các l trình ki m th sinh ra t CFG c a bài toán tam giác ..... 45

B ng 4.2.

K t qu th c thi sinh d li u th ........................................................ 46

B ng 4.3.

K t qu l trình th c thi ng v i d li u th ...................................... 47

B ng 4.4.

Tỷ l bao ph l trình c a d li u ki m th ....................................... 48



-x-

DANHăM CăCÁCăHỊNHăVẼăVÀăĐ ăTH
Hình 1.1.

CFG c a các c uătrúcăđi u khi n thơng d ng..................................... 12

Hình 1.2.

Quy trình t o ca ki m th d aătrênăđ th lu ngăđi u khi n .............. 14

Hình 1.3.

S ăđ th c hi n gi i thu t di truy năđ năgi n .................................... 17

Hình 2.1.

Quy trình biên d ch, thơng d ch và th c thi mã ngu n Java............... 22

Hình 2.2.

Quy trình ki m th m t hàm Java d aătrênăđ th lu ngăđi u khi n.. 26

Hình 2.3.

Thu t tốn sinh CFG t mã ngu n ..................................................... 27

Hình 2.4.


Thu t tốn sinh t p l trìnhăđ c l p t CFG ....................................... 28

Hình 2.5.

Thu t tốn sinh l trình ki m th vịng l p ........................................ 30

Hình 2.6.

Thu t tốn sinh l trình ki m th vịng l p trong ............................... 30

Hình 2.7.

Thu t tốn sinh l trình ki m th vịng l p ngồi .............................. 31

Hình 4.1.

Thu t tốn tổng quát sinh d li u th bằng GA ................................. 39

Hình 4.2.

Mã ngu n l p Chromosome ............................................................... 40

Hình 4.3.

Mã ngu n hàm createInitialPopulation .............................................. 41

Hình 4.4.

Mã ngu n hàm crossOver................................................................... 41


Hình 4.5.

Mã ngu n hàm mutation..................................................................... 42

Hình 4.6.

Mã ngu n hàm evaluatePopulation .................................................... 42

Hình 4.7.

Mã ngu n hàm fitnessOfTestCase ..................................................... 43

Hình 4.8.

Mã ngu n hàm testSuiteGenerationByGA ......................................... 43

Hình 4.9.

Mã ngu n bài tốn phân lo i tam giác ............................................... 44

Hình 4.10. Bi uăđ lu ngăđi u khi n CFG c a bài tốn tam giác ........................ 45
Hình 4.11. Bi uăđ bi u di n tỷ l bao ph l trình ki m th .............................. 48


1

M ăĐ U
1. Lý do ch năđ tài
Hi n nay, ph n m m (hay ng d ng công ngh thơngătin)ăđangăđóngăvaiătrịăh t

s c quan tr ng và khơng th thi uătrongăcácălƿnhăv c c aăđ i s ng xã h i. Ph n m m
gi đơyăđưăđ c ng d ng r ng rãi nhi uăph ngădi n trong cu c s ng, t khoa h c,
kỹ thu t,ăth ngăm iăđ năvĕnăhóa,ăxư h i vƠ giáo d c.ăDoăđó,ăvi căđ m b o cho ph n
m m ho tăđ ng t t,ăđápă ng t t yêu c u c aăng i s d ng là r t quan tr ng. Ki m th
ph n m m là ho tăđ ngăđóngăvaiătrịăr t quan tr ng nhằmăđánhăgiáătínhăđúngăđ n, s
hồn hi n và b oăđ m ch tăl ng ph n m m. Vì v y, ki m th ph n m măđưătr thành
quy trình b t bu c trong các d án phát tri n ph n m m trên th gi i.
Vi t Nam, cùng v i s phát tri n c a ngành công nghi p ph n m m, ngành ki m
th ph n m măcũngăđangăcóăti mănĕngăphátătri n. T nĕmă2010,ăm t s t păđoƠnăCNTTă
l n trên th gi iăđangăthuêăcácăcôngătyăph n m m t i Vi t Nam gia công ki m th ph n
m m cho h . Nhu c u s d ng d ch v ki m th ph n m m,ăđ c bi t là ki m th ph n
m m t đ ng t i Vi tăNamăđangăgiaătĕng.
Vai trò ki m th ph n m m r t quan tr ng trong ho tăđ ng phát tri n ph n m m,
nh ngăho tăđ ng ki m th th ng g p nhi uăkhóăkhĕn:
- Ki m th các h th ng ph c t p t n r t nhi u ngu n tài nguyên và chi phí cao.
- Ti n trình phát tri n ph n m m luôn tr i qua nhi u ho tăđ ng bi năđổi thông tin,
s sai l ch thông tin trong quá trình bi năđổi là y u t chính làm cho ho tăđ ng ki m th
khóăkhĕn.
- nhi u doanh nghi p phát tri n ph n m m, vi c ki m th ch aăđ
trongăđƠoăt oăconăng i.

c chú tr ng

- Không t n t i kỹ thu t ki m th cho phép khẳngăđ nh m t ph n m m hồn tồn
đúngăđ n hay khơng ch a lỗi.
Có nhi u kỹ thu t ki m th đ c ng d ng trong vi c phân tích, thi t k , xây d ng
và phát tri n ph n m m,ătrongăđóăki m th c u trúc (structural testing) là kỹ thu tăc ă
b nă đ xây d ng các ca ki m th (test cases). Kỹ thu t chính đơyă lƠă phơnă tíchă mưă
ngu n,ăxácăđ nh các lu ngăđi u khi n t input đ n output. D a trên vi căxácăđ nh các l
trìnhăđ đ aăraăcácăcaăki m th nhằm m căđíchăki m tra t t c các l trình có th . Ki m

th c u trúc d a vào thu t gi i c th , vào c u trúc bên trong c aăđ năv ph n m m c n
ki m th đ xácăđ nh ca ki m th nhằm xácăđ nhăđ năv ph n m măđóăcóăth c hi năđúngă
hay khơng. Bên c nhăđó,ăki m th c uătrúcăđ m b o các thành ph nănh ăcơuăl nh, r
nhánh, l trìnhătrongăđ năv ph n m măđ c th c thi.


2
Tuy nhiên, ki m th c uătrúcăkhôngăđ m b o 100% rằng th c thi các thành ph n
trongăch ngătrìnhăs phát hi năđ c t t c các lỗi có th phát sinh. B iăvì,ăch ngătrìnhă
th c thi m t câu l nh lỗi thì có th khơng phát sinh lỗi, do có th lỗi khơng xu t hi n khi
th c thi câu l nh v i m t s d li uăđ uăvƠoănƠoăđóăho c câu l nh lỗiăđó khi th c thi
khơng làm th t b iăch ngătrình.ăV i m căđíchătìmăvƠăphátăhi n lỗi, ki m th c u trúc
th ng ph i tr iăquaăcácăb c: t o d li u th , th c thi ph n m m v i d li u th và
quan sát k t qu nh năđ c.ăTrongăđó,ăb c t o d li uăđóngăvaiătrịăquan tr ng nh t,
b i vì chúng ta khơng th t o ra m i d li u t mi n vào c aăch ngătrình,ămƠăchúngătaă
ch̉ có th t o ra các d li u th có kh nĕngăphátăhi n lỗi cao nh t. V năđ đ t ra là làm
th nƠoăđ đánhăgiáăđ c kh nĕngăphátăhi n lỗi c a m t b d li u th ?
Đ giúp gi i quy t v năđ này, ta s d ng khái ni m ch tăl ng b d li u th đ
đánhăgiáăb d li u th nh ăth nƠoălƠăắt t”ăkhiăki m th ch ngătrình.ă đơy,ăắt t”ă
đ căđánhăgiáăliênăquanăđ n tiêu chu n ch tăl ngăđ căđ nhătr c,ăth ng là m t s
tiêu chí bao ph (coverage)ăch ngătrình,ănghƿaălƠăth c thi các thành ph nătrongăch ngă
trìnhănh ăbaoăph l nh, bao ph r nhánh, bao ph l trìnhầ.ăVíăd , tiêu chu n bao ph
l nhăđòiăhỏi b d li u th th c hi n m i dịng l nhătrongăch ngătrìnhăítănh t m t l n.
N u b d li u th đ c tìm th y khơng đápă ng tiêu chu n này (t c là không ph i t t
c các câu l nhăđ uăđ c th c hi n ít nh t m t l n), thì b t bu c ph i th c hi n ki m th
thêm.ăDoăđó,ăm c tiêu là t o ra m t t p các ki m th th c hi năđ yăđ tiêu chu n ch t
l ng,ănơngăcaoăđ tin c y c aăch ngătrìnhăc năđ c ki m th .
Ki m th c uătrúcăđưăđ c áp d ng cho nhi u ngôn ng l pătrìnhăkhácănhau,ănh :ă
ngơn ng l p trình PHP, Ruby, VB, các ngơn ng C/C++/C#, ngơn ng Javaầătrongă
đó,ăJavaălƠăngơnăng l pătrìnhăđ c s d ng r ng rãi và phổ bi năđ phát tri n ph n

m m. Vi c ki m th mã ngu năJavaăđ đ m b oătínhăđúngăđ n là r t quan tr ng và c n
thi t.
Đưăcóăr t nhi u nghiên c u nhằm nâng cao hi u qu c a ki m th c uătrúcănh ăt
đ ng hóa m t s ho tăđ ng trong quy trình ki m th c uătrúcăhayăxácăđ nh d li u th
đ m b o các tiêu chí bao ph nh :ăbaoăph câu l nh, bao ph r nhánh, bao ph l trình.
M t trong nh ng gi i pháp d a trên gi i pháp phát sinh d li u th đ m b o các tiêu chí
bao ph bằng cách áp d ng gi i thu t di truy năđ sinh ra d li u th .
Thu t gi i di truy n (Genetic Algorithm - GA) là m t trong nh ng kỹ thu t tìm
ki m l i gi i t iă uăđưăđápă ngăđ c yêu c u c a nhi u bài toán và ng d ng. Hi n nay,
thu t toán di truy n cùng v i logic m đ c ng d ng r t r ngărưiătrongăcácălƿnhăv c
ph c t p.ăNgƠyănay,ăGAăđ c ng d ng khá nhi uătrongăcácălƿnhăv cănh ăkhoaăh c,
kinh doanh và gi iătrí,ătrongăđó,ăcóă ng d ng cho vi c t đ ng sinh d li u th đ c l y
ra d a trên c u trúc bên trong c aăch ngătrình,ăv i m căđíchălƠăđiăquaăcácăl nh, l trình,
đi u khi n.ăĐi m m nh c a GA là vi c x lý d li uăđ u vào có c u trúc là s ph c, v


3
t ph c t p,ăhƠmăch aăbi tăđ n bi năđ u vào. Vì v y, vi c sinh d li u th là v năđ c n
t iă uăhóa.ăKi m th ng uănhiênăđ c s d ngănh ăm t so sánh v hi u qu d li u th
đ c sinh ra b i GA. L i th c a GA là thơng qua vi c tìm ki m và q trình t iă uăhóa,ă
ch tăl ng các b d li u th đ c nâng cao.
Vì nh ng lý doănh ătrên, tôi ch năđ tài lu năvĕnăth căsƿ: ắ ng dụng giải thuật di
truyền sinh dữ liệu thử bao ph cấu trúc c a chương trình Java”.
2. M căđíchănghiên c u
Đ tài tìm hi uăc ăs lý thuy t v gi i thu t di truy n, lý thuy t v ki m th cũngă
nh ăcáchăt o ra d li u ki m th đ m b o các tiêu chí bao ph nhằm gi m nhân l c ki m
th nh ngăv năđ m b oăđ c ch tăl ng ph n m măh năv i công vi c t o d li u ki m
th bằng th cơng.
M c tiêu chính c aăđ tài là nghiên c u và ng d ng gi i thu t di truy năđ sinh
d li u th đ m b o các tiêu chí bao ph c a mã ngu năJavaăvƠăđ m b oănơngăcaoăđ

tin c y c aăch ngătrìnhăc năđ c ki m th .
3. M c tiêu và nhi m v nghiên c u
a) Mục tiêu
M c tiêu chính c aăđ tài là xây d ngăđ c b d li u th đ m b o các tiêu chí
bao ph đ căsinhăra.ăĐ tho mãn m c tiêu này thì c năđ tăđ c nh ng m c tiêu c th
sau:
- N m v ng kỹ thu t ki m th c u trúc và các tiêu chí bao ph c u trúc.
- Xây d ngăđ c b d li u th đ m b o các tiêu chí bao ph bằng vi c áp d ng
t t gi i thu t di truy n trong vi c sinh d li u ki m th trongăch ngătrìnhăJava.
b) Nhiệm vụ
Đ đ tăđ

c nh ng m c tiêu trên th nhi m v đ t ra c aăđ tài là:

- Nghiên c u thu t toán di truy n, kỹ thu t ki m th c u trúc và nguyên t c sinh
d li u th đ m b o các tiêu chí bao ph .
- Phát bi u,ăphơnătíchăvƠăcƠiăđ t gi i thu tăchoăbƠiătoánăđ t ra.
- Xây d ng gi i thu t và ng d ng ki m th các thi t k c aăch

ng trình Java.

- Đánhăgiáăk t qu theo yêu c u c aăđ tài.
4. Đ iăt

ng và ph m vi nghiên c u

Trong khuôn khổ c a lu năvĕnăthu c lo i nghiên c u và ng d ng, tôi ch̉ gi i h n
nghiên c u các v năđ sau:
- Kỹ thu t ki m th c u trúc.



4
- Các tiêu chí bao ph và kỹ thu t sinh d li u th .
- Gi i thu t di truy n.
5. Ph

ngăphápănghiênăc u

a) Phương pháp lý thuyết
- Ti n hành thu th p và nghiên c u các tài li uăcóăliênăquanăđ năđ tài.
- Nghiên c u lý thuy t ki m th ph n m m nói chung và kỹ thu t ki m th c u
trúc nói riêng.
- Nghiên c u các tiêu chí bao ph vƠăc ăch sinh d li u th .
- Nghiên c u gi i thu t di truy n và vi c ng d ng gi i thu t di truy n trong các
bài toán t iă u.
- Nghiên c u các gi i pháp sinh d li u th t đ ng trong mã ngu n Java.
b) Phương pháp thực nghiệm
- Nghiên c uăđ xu t gi iăphápăđ m b o các tiêu chí bao ph d li u sinh ra s
d ng gi i thu t di truy n khi ki m th mã ngu nătrongămôiătr ng Java.
- CƠiăđ tămoduleăđ th c hi n vi c sinh d li u th đ m b o các tiêu chí bao ph
c a ch ngătrìnhăc n ki m th .
- Ki m tra, th nghi m, nh năxétăvƠăđánhăgiáăk t qu .
6. ụănghĩaăkhoaăh c và th c ti n c aăđ tài
a) Ý nghĩa khoa học
- N m v ng và v n d ng t t kỹ thu t ki m th c u trúc trong ki m th ph n m m.
- N m v ng các tiêu chí bao ph trong ki m th c u trúc.
- N m v ng và ng d ng t t gi i thu t di truy n trong các bài toán t iă u.
- K t qu có th làm tài li u tham kh o cho các ki m th viên,ăcácăđ năv phát tri n
ph n m m, ho c các h c viên ậ sinh viên trong vi c nghiên c u ki m th ph n m m.
b) Ý nghĩa thực tiễn

Thi t k vƠăcƠiăđ t công c sinh d li u th t đ ngăđ m b o t t c các tiêu chí bao
ph trongăch ngătrìnhăJava.


5
7. B c c c a lu năvĕn
Lu năvĕnăđ

c trình bày bao g m các ph năchínhănh ăsau:

M CL C
DANH M C CÁC KÝ HI U VÀ CH

VI T T T

DANH M C CÁC B NG
DANH M C CÁC HÌNH VẼ VÀăĐ
M
CH

TH

Đ U
NGă1:ăC ăS

LÝ THUY T

1.1. Ki m th ph n m m
1.2. Ki m th c u trúc
1.2.1. Khái ni m v đ th ki m th

1.2.2. Tiêu chí bao ph
1.2.3. Ki m th d aătrênăđ th lu ng đi u khi n
1.2.4. Ki m th d aătrênăđ th lu ng d li u
1.3. Gi i thu t di truy n
1.3.1. Các khái ni m
1.3.2. Kh i t o qu n th
1.3.3. Hàm m c tiêu
1.3.4. Cách t o qu n th m i
CH

NGă2:ăKI M TH
2.1. Gi i thi u mơiătr

C UăTRÚCăTRONGăMỌIăTR

NG JAVA

ng ngơn ng Java

2.1.1. Java là gì?
2.1.2.

ng d ng c a Java

2.1.3. Nh ngăđ căđi măc ăb n c a Java
2.1.4. Java Virtual Machine (JVM)
2.1.5. Các kh iăđi u khi năc ăb n trong Java
2.2. Tổngăquanăph

ngăphápăki m th c u trúc d aătrênăđ th lu ngăđi u khi n


2.3. Xây d ngăđ th lu ngăđi u khi n t mã ngu n Java
2.4. Xây d ng t p l trình ki m th
2.4.1 Xây d ng t p l trìnhăđ c l p
2.4.2 Xây d ng l trình ki m th vịng l p
CH

NGă3:ăGI I PHÁP SINH D
3.1. Phát bi uăbƠiătoánăđ t ra
3.2. Bi u di n nhi m s c th

LI U TH D A TRÊN GI I THU T DI TRUY N


6
3.3 Kh i t o qu n th
3.4 Xây d ng hàm thích nghi
3.5 L a ch n
3.6 K t h p l i
3.7 L a ch n t iă u
3.8 Thu t toán tổng quát
CH

NGă4: CÀIăăĐ T VÀ TH

NGHI M

4.1. CƠiăđ t gi iăphápăđưăđ xu t
4.2. Tri n khai mô phỏng th c nghi m
4.3.ăSoăsánh,ăđánhăgiáăk t qu

K T LU NăVÀăH

NG PHÁT TRI N

TÀI LI U THAM KH O


7

CH
NGă1.
C ăS ăLụăTHUY T
1.1 Ki m th ph n m m
1.1.1 Khái niệm về kiểm thử phần mềm
Ki m th ph n m m (ki m tra, th nghi m) là m t cu c ki m tra đ c ti n hành
đ cung c p cho các bên liên quan thông tin v ch tăl ng c a s n ph m ho c d ch v
đ c ki m th . Ki m th có th cung c p cho doanh nghi p m tăquanăđi m, m t cách
nhìnăđ c l p v ph n m măđ t đóăchoăphépăđánhăgiáăvƠăth u hi uăđ c nh ng r i ro
trong quá trình tri n khai ph n m m [16].
Trong kỹ thu t ki m th không ch̉ gi i h n vi c th c hi n m tă ch ngătrìnhă
ho c ng d ng v i m căđíchăđiătìmăcácălỗi ph n m m (bao g m các lỗi và các thi u sót)
mà cịn là m t q trình phê chu n và xác minh m tăch ngătrìnhămáyătính/ă ng d ng/
s n ph m nhằm:
- Đápă ngăđ

c m i yêu c uăh

ng d n khi thi t k và phát tri n ph n m m.

- Th c hi n cơng vi căđúngănh ăkỳ v ng.

- Có th tri năkhaiăđ
- VƠăđápă ngăđ

c v i nh ngăđ cătínhăt

ngăt .

c m i nhu c u c a các bên liên quan.

Tùy thu c vào t ngăph ngăpháp,ăvi c ki m th có th đ c th c hi n b t c lúc
nào trong quá trình phát tri n ph n m m. Theo truy n th ng thì các nỗ l c ki m th
đ c ti n hành sau khi các yêu c uăđ căxácăđ nh và vi c l pătrìnhăđ c hồn t tănh ngă
trong Agile (là m t t p h păcácăph ngăphápăphátătri n ph n m m linh ho t d a trên
vi c l păđiăl p l iăvƠăgiaătĕngăgiáătr ) thì vi c ki m th đ c ti n hành liên t c trong su t
quá trình xây d ng ph n m m.ăNh ăv y, mỗi m tăph ngăphápăki m th b chi ph i
theo m t quy trình phát tri n ph n m m nh tăđ nh [16].
1.1.2 Các bước kiểm thử
1.1.2.1 Lập kế hoạch kiểm thử
K ho ch ki m th choăphépăxácăđ nh m c tiêu ki m th ,ăđ iăt ng ki m th , kỹ
thu t ki m th , ngu n tài nguyên, l ch ki m th ... M t k ho ch ki m th t t s gi m
đ c chi phí, c i thi năđ c quan h v i l pătrìnhăviênăvƠănơngăcaoăđ c ch tăl ng c a
ki m th [12].


8
1.1.2.2 Thiết kế ca kiểm thử
Ca ki m th (test case) là các thông tin g m dữ liệu thử, điều kiện thực thi/các
bước thực thi và kết quả mong đợi.
- Thiết kế dữ liệu thử: Tùy theo m c tiêu ki m th , kỹ thu t ki m th vƠăđ iăt ng
ki m th mà các d li u th s đ c thi t k d aătrênăđ c t yêu c u, thi t k ch ngă

trình hay mã ngu n. Thi t k d li u th đ c xem là ho tăđ ng quan tr ng nh t, vì các
d li u th ph i có kh nĕngăphátăhi n lỗi cao.
- Xác định điều kiện thực thi: vi căxácăđ nhăđi u ki n ki m th hayăcácăb
thi có th đ năgi n hay ph c t p,ătùyătheoăđ iăt ng c năđ c ki m th .

c th c

- Xác định kết quả mong đợi: c năxácăđ nh k t qu chúngătaămongăđ i khi th c thi
ph n m m v i d li u th đ c thi t k [12].
1.1.2.3 Thực thi chương trình
Ki m th viên c n ph i chu n b mơiătr ngăđ th căthiăch ngătrìnhăc n ki m
th .ăSauăđó,ăki m th viên th căthiăch ngătrìnhăv i các d li uăđ c thi t k và ghi
nh n l i k t qu th căthiăch ngătrìnhălƠăthƠnhăcơngăhayăth t b i.
1.1.2.4 Phân tích kết quả kiểm thử và lập báo cáo
Ho tăđ ng cu i cùng là phân tích k t qu c a vi c th c hi n ca ki m th . Cơng
vi c chính là so sánh k t qu th căthiăch ngătrìnhăv i k t qu mongăđ i.ăĐ ph c t p
c a vi c so sánh ph thu căvƠoăđ ph c t p c a d li u c năđ c quan sát và phân tích.
Sauăb c này, phán xét ki m th đ căgánăchoăch ngătrìnhăkhiăth c hi n ca ki m th .
Cóăbaăphánăxétăchínhăđ c gán g m: thành công, thất bại và chưa kết luận.
- N uăch ngătrìnhăt o ra k t qu gi ng v i k t qu mongăđ i thì phán xét thành
cơng đ c gán.
đ

- N uăch
c gán.

ngătrìnhăt o ra k t qu khác v i k t qu mongăđ i thì phán xét thất bại

- Trong m t s tr ng h p khơng th xácăđ nhăđ căch ngătrìnhăthƠnhăcơngăhayă
th t b i khi th c hi n ca ki m th ,ănghƿaălƠăc n ph i th c hi n thêm các ki m th khác

đ lƠmărõăch ngătrìnhăthƠnhăcơngăhayăth t b i.ăKhiăđó,ăphánăxétăchưa kết luận đ c
gán.
b c này, ki m th viên c n ph i l p báo cáo lỗiăcũngănh ăbáoăcáoăki m th .
Báo cáo lỗi (bug report) ph iăđ c l p ngay sau khi phân tích mỗi lỗi. Báo cáo lỗi nên
ch a các thông tin v ng iăxácăđ nh lỗi, th iăgianăxácăđ nh lỗi, s n ph m (g m c phiên
b n) b lỗi, mô t lỗi, cách tái t o lỗi,ăđ nghiêm tr ng c a lỗi, tr ng thái lỗiăcũngănh ă
các thông tin khác hỗ tr vi c s a lỗi. Báo cáo kiểm thử (test report) tổng h p k t qu


9
ki m th , nêu rõ nh ngăgìăđưăđ c ki m th , nh ngăgìăch aăđ
các lỗiăđ c tìm th y, l ch và th i gian ki m th th c t [12].

c ki m th , danh sách

1.1.3 Các hoạt động kiểm thử phần mềm
Hoạt động kiểm thử (test activity) hay m c kiểm thử (test level) là m t k ho ch
nhằmăđ nhănghƿaăm c tiêu c a c aăcácăgiaiăđo n ki m th cũngănh ăcácăkỹ thu t ki m
th đ c s d ng. Ho tăđ ng ki m th ngăđ c quy tăđ nh d a vào Tiêu chu n v đ
tin c y c a ph n m m và chi phí cho vi c phát tri n ph n m m. M t chi năl c ki m
th s ph thu căkíchăth c c aăđ iăt ngăđ c ki m th cũngănh ăquanăđi m c a chúng
ta v đ iăt ngăđ c ki m th . Các ho tăđ ng ki m th bao g m 4 ho tăđ ng chính sau:
- Kiểm thử đơn vị (unit testing): là ki m th m tăcáchăđ c l p các thành ph nă(đ nă
v ) c u t o nên ph n m m, chúng ta ch̉ quanătơmăđ n t ngăđ năv ph n m mănh ăhƠm,ă
th t c hay l p. Ki m th đ năv đ c th c hi n b i các l p trình viên. Các kỹ thu t
ki m th ch cănĕngăvƠăki m th c uătrúcăđ u có th đ c s d ng cho ki m th đ năv .
- Kiểm thử tích hợp (integration testing): là ki m th s k t h p c a các thành ph n
c u t o nên ph n m m. Ki m th tích h p h ngăđ n phát hi n lỗi giao ti p gi a các
thành ph n, các module. Ki m th tích h păth ngăđ c th c hi n b i các l p trình viên
và/ho c các ki m th viên. Các kỹ thu t ki m th ch cănĕngăth ngăđ c s d ng cho

ki m th tích h p. Trongătr ng h p c n thi t, các kỹ thu t ki m th c uătrúcăcũngăcóă
th đ c s d ng cho ki m th tích h p nh ngăchi phí ki m th s cao.
- Kiểm thử hệ thống (system testing): nhằmăđ m b o h u h t các lỗiăđưăđ c phát
hi n và s a ch a, ph n m măđápă ngăđ c yêu c uăđ t ra. Ki m th h th ngăth ng là
giaiăđo n cu i trong các quy trình phát tri n ph n m m. Ki m th h th ng có th bao
g m nhi u lo i ki m th khácănhau,ănh ăki m th ch cănĕng,ăki m th b o m t, ki m
th c u hình, ki m th kh nĕngăch u t i, ki m th hi uănĕng,ăki m th đ tin c y, ki m
th tài li u... Ki m th h th ngăđ c th c hi n b i các ki m th viên.
- Kiểm thử chấp nhận (acceptance testing): đ đánhăgiáăch tăl ng c a ph n m m,
ng i s d ng s th c hi n các ki m th ph n m m sau khi h th ng ph n m măđ c
chuy năgiaoăchoăng i s d ng. Khi ki m th ch p nh n,ăng i s d ng có th đ nh
nghƿaăcácătiêuăchíăch p nh n d aătrênămongăđ i c a h v ph n m m.
Trong các quá trình ho tăđ ng ki m th , khi ki m th phát hi n ra lỗi, thì vi c s a
lỗiăsauăđóăcóăth phát sinh các lỗi khác. Vì v y chúng ta c n ph i th c hi n ho tăđ ng
kiểm thử hồi quy (regression testing) nhằm th c hi n các ki m th khácăđ đ m b o
các lỗi m i không xu t hi n. Ki m th h i quy có th th c hi n trong su t quá trình phát
tri n ph n m m và có th đ c th c hi n khi m t thành ph n c a h th ngăthayăđổi [12].


10
1.1.4 Các kỹ thuật kiểm thử phần mềm
- Kiểm thử ch c năng (functional testing) hay còn g i là ki m th h păđenă(blackbox testing): là kỹ thu t ki m th t p trung vào yêu c u v m t ch cănĕngăc a ph n
m m,ăđơyălƠăkỹ thu t t o ra các t p d li u th ch̉ d a trên k t qu c a vi c th c thi các
ch cănĕng,ăcácămodules c a ph n m m mà không c n quanătơmăđ n c u trúc bên trong
c a các ch cănĕng,ămodulesăph n m m. Kỹ thu t ki m th này d aătrênăđ c t ph n
m m, các ch cănĕngăđ c ki m th bằng cách nh p vào các giá tr đ u vào và ki m tra
k t qu đ uăraăvƠăítăquanătơmăđ n c u trúc bên trong c a ph n m m.ăĐơyălƠăm t quy
trình nhằm c g ng tìm ra các khác bi t gi aăđ c t bên ngoài c a ph n m m và k t qu
th c t mà ph n m m cung c p [12].
- Kiểm thử cấu trúc (structual testing) hay còn g i là ki m th h p tr ng (whitebox testing): là kỹ thu t ki m th cho phép ki m tra c u trúc bên trong c a ph n m m

v i m căđíchăđ m b o rằng t t c các câu l nhăvƠăđi u khi n s đ c th c hi n ít nh t
m t l n. Ki m th h p tr ng d a vào thu t toán c th , vào c u trúc bên trong c a đ nă
v ch ngătrìnhă(chẳng h n hàm hay th t c) c n ki m th đ xácăđ nh đ năv ch ngă
trình đóăcóăth c hi n có đúngăhay khơng.ăDoăđóăng i ki m th c u trúc ph i có kỹ
nĕng,ăki n th c nh tăđ nh v ngôn ng l pătrìnhăđ c s d ng, v thu t gi iăđ c dùng
trong t ng đ năv ch ngătrình đ có th hi u chi ti t v đo n mã ngu n c n ki m th .
Kỹ thu t này ch y u đ cădùngăđ ki m th đ năv và là kỹ thu tăc ăb năđ xây d ng
các ca ki m th [12].
- Kiểm thử hộp xám (grey-box testing): là kỹ thu t ki m th đ c k t h p gi a kỹ
thu t ki m th ch cănĕngăhayăki m th h păđen (black-box) và kỹ thu t ki m th c u
trúc hay ki m th h p tr ng (white-box). Trong ki m th h p xám, c u trúc bên trong
ph n m m ch̉ đ c bi t m t ph n, ki m th viên có th truy c p vào c u trúc d li u
bên trong và thu t tốn c aăch ngătrìnhăv i m căđíchălƠăđ thi t k ca ki m th ,ănh ngă
khi ki m th thì ki m th viênăđóngăvaiătrị nh ălƠăng i dùng cu i ho c là m c h p
đen. Kỹ thu t ki m th h păxámăth ng s d ng các kỹ thu t ki m th ch cănĕngătrongă
cácăb căđ u,ăsauăđóăcácăph n cịn l i c a mã ngu năđ c ki m th b i kỹ thu t ki m
th c u trúc.
- Kiểm thử động (dynamic testing): là kỹ thu t ki m th nhằm th c thi mã ngu n
ph n m m v i d li u th , quan sát và so sánh v i k t qu mongăđ i. Ki m th đ ng có
th yêu c u th c thi mã ngu n c a ph n m m thông qua vi c s d ng máy ch yăch ngă
trìnhăđ đi u tra tr ng thái t ngăđ ng tác c aăch ngătrình.
- Kiểm thử tĩnh (static testing): là kỹ thu t ki m th nhằmăđánhăgiáăcácăs n ph m
c a d án ph n m mănh ăđánhăgiáătƠiăli uăđ c t yêu c u, tài li u phân tích - thi t k , k
ho ch ki m th hayăđánhăgiáămưăngu nătr c khi th căthiầăKi m th tƿnhălƠăph ngă
ti năđ ki m th s m các s n ph m liên quan c a ph n m m trong quy trình phát tri n,


11
giúp chúng ta t p trung s m vào ch tăl ng ngay t khi b tăđ u d án, cho phép xác
đ nh và lo i bỏ các lỗi hay sai sót. N u lỗiăđ c phát hi n s m trong quá trình phát tri n

ph n m m thì chi phí s a lỗi th păh n,ăhi u qu phát tri n s n ph măđ c c i ti n và các
lỗi gi m nhăh ngăđ n khách hàng.
- Kiểm thử phi ch c năng (non-functional testing): là kỹ thu t ki m th nhằm ki m
tra kh nĕngăs n sàng c a h th ng,ăt ngă ng v i m t lo t các yêu c u mà không th
đ c bao ph b i vi c ki mătraăcácătínhănĕngăch cănĕng. Cácătínhănĕngăphiăch cănĕngă
là m t ph n c a d án ph n m m c năđ c ki m tra và xác nh năđ ch c ch năđúngăv i
yêu c uăvƠămongăđ i c a khách hàng. Ki m th phi ch cănĕngăg m nhi u lo i khác nhau
nh ăki m th kh nĕngăs d ng, ki m th cƠiăđ t, ki m th kh nĕngăt ngăthích,ăki m
th c u hình, ki m th hi uănĕng,ăki m th b o m tầ [12].
1.2 Ki m th c u trúc
1.2.1 Khái niệm về đồ thị kiểm thử
- Đ th ki m th lƠăđ th cóăh ngăđ c s d ngăđ đ nhănghƿaănhi u tiêu chí
ki m th c u trúc. T c uătrúcăch ngătrìnhă(chẳng h n hàm, th t căhayăph ngăth c),
lƠăđ iăt ng c n ki m th , chúng ta xây d ngăđ th ki m th t ngă ng. Các ca ki m
th choăđ iăt ng c n ki m th đ c xây d ngăt ngă ng v i m t l trìnhătrongăđ th .
Tiêu chí bao ph d aătrênăđ th đánhăgiáăt p ca ki m th choăđ iăt ngăki m th v
m t các l trìnhăt ngă ng các ca ki m th bao ph đ th .
- M tăđ th Găđ

căđ nhănghƿaăg m [12]:

+ T păcácăđ̉nh N,

+ T păcácăđ̉nhăđ u N0, v i N0  N,
+ T păđ̉nh cu i Nf, v i Nf  N,

+ T păcácăcungăE,ătrongăđóăEălƠăt p con c a N x N.
- Một lộ trình (path) là m t chuỗiăcácăđ̉nh [n1, n2,ăầ,ănk],ătrongăđóămỗi c păđ̉nh
li n k (ni, nj), 1 ≤ăi, j ≤ k, thu c t p các cung E [12].
- Lộ trình kiểm thử (testpath) là m t l trình xu t phát t m tăđ̉nhăđ u thu c N0 và

k t thúc t i m tăđ̉nh cu i Nf. M t l trình ki m th bi u di n s th c thi c a m t ca
ki m th .
- Đồ thị luồng điều khiển:
+ăĐ th đ c s d ng phổ bi n nh t trong ki m th c uătrúcălƠăđ th lu ng đi u
khi n (Control Flow Graph - CFG).ăĐ th nƠyăđ c xây d ng t mã ngu n c a ch ngă
trình/đ năv ch ngătrình.ăCFGălƠăm tăđ th cóăh ng g m cácăđ̉nhăt ng ng v i các
câu l nh/ nhóm câu l nh và các c nhălƠăcácădịngăđi u khi n gi a các câu l nh/nhóm câu


12
l nh. N uăiăvƠăjălƠăcácăđ̉nh c aăđ th dòngăđi u khi n thì t n t i m t c nh t iăđ n j n u
l nhăt ngă ng v i j có th đ c th c hi n ngay sau l nhăt ng ng v i i [12, 14].
+ Các thành ph năc ăb n c a c aăđ th lu ng đi u khi n bao g m: điểm bắt đầu
c aăđ năv ch ngătrình,ăkhối xử lý ch a các câu l nh khai báo ho c tính tốn, điểm
quyết định ng v i các câu l nhăđi u ki n trong các kh i l nh r nhánh ho c vòng l p,
điểm nối ng v i các câu l nh ngay sau các l nh r nhánh và điểm kết thúc ng v i đi m
k t thúc c aăđ năv ch ngătrình [14].
+ Các c uătrúcăđi u khi n trong m tăCFGăth ng g m tu n t , r nhánhă(ifăầ
else), l p (while...do, do...while, for). Hình 1.1 minh h a các CFG c a các c uătrúcăđi u
khi n thông d ng c a mã l nhăch ngătrình.ăTrongăđóăđ̉nhăcóănhưnăcăt ngătr ngăchoă
câu l nhăđi u ki n.ăCácăđ̉nh còn l i t ngătr ngăcơuăl nh gán, khai báo, v.v.
Tu n t

if .. then

if .. then .. else

c

c


case statement

while .. do

c

c

Vịng l p for
c

do .. while

c

Hình 1.1.

CFG c a các cấu trúc điều khiển thông dụng

1.2.2 Tiêu chí bao ph
- M t trong nh ngănh căđi m c a ki m th d aătrênăđ c t (ki m th ch cănĕng)
là chúng ta không bi t s l ng ca ki m th có th a hay thi u so v iăch ng trình cài
đ t hay không, và thi u th a m căđ nƠo.ăNg c l i, trong ki m th c uătrúc,ăđ đoă
ki m th là m t công c giúpătaăđoăm căđ bao ph ch ng trình c a m t t p ca ki m
th choătr c. T p ca ki m th khi n mã ngu năcóăđ ph caoăđ căđánhăgiáălƠăt tăh nă
so v i t p ca ki m th khác khi n mã ngu n cóăđ ph th păh n.ăCh tăl ng mã ngu n
đ căđánhăgiáăt̉ l thu n v iăđ bao ph [14].



13
- Đ bao ph đ căđánhăgiáăd a trên hai thông s g m tiêu chí bao ph ki m
th và t p các ca ki m th . Công th cătínhăđ bao ph là t̉ l các thành ph năđ c
ki m th trên tổng s các thành ph n c n ki m th sauăkhiăđưăth c hi n t p các ca ki m
th .
- Có nhi u tiêu chí bao ph ki m th đ căđ aăra.ăTuy nhiên, trong khuôn khổ
lu năvĕnănƠy, tôi s d ng b n tiêu chí ph ki m th phổ bi năđ đánhăgiáăch tăl ng mã
ngu n g m [12]:
+ Tiêu chí bao ph đỉnh (hay tiêu chí bao ph câu lệnh): yêu c u th c thi các l
trình ki m th sao cho t t c cácăđ̉nhătrongăđ th đ c th c hi n,ănghƿaălƠăyêuăc u mỗi
câu l nh ph iăđ c th c thi ít nh t m t l n sau khi ch y ca ki m th .
+ Tiêu chí bao ph cung (hay tiêu chí bao ph nhánh): yêu c u c a t t c các cung
(hay l trình ch̉ ch a m t cung) ph iăđ c bao ph ,ănghƿaălƠămỗiăcungătrênăđ th ki m
th đ uăđ căđiăquaăítănh t m t l n sau khi ch y ca ki m th . Tiêu chí này khơng ch̉
u c u th c thi m i câu l nh mà cịn th c thi m i r nhánhătrongăch ngătrình.
+ Tiêu chí bao ph lộ trình: u c u t t c các l trình ph iăđ c bao ph ,ănghƿaă
là t t c các l trìnhă(đ ngăđi)ăph i th c thi ít nh t m t l n sau khi ch y ca ki m th .
Tuy nhiên, chúng ta có th nh n th y tiêu chí bao ph l trình khơng th thỏaămưnăđ c
trongătr ng h p có vịng l p, do s l trìnhăth ng là vơ h n.
+ Tiêu chí bao ph lộ trình độc lập:ăđ i v iăch ngătrìnhăcóăvịngăl p, s l trình
th ng vơ h n. Tuy nhiên, t n t i m t t p con (nhỏ nh t) các l trình cho phép t o ra t t
c các l trình cịn l i, t p con các l trình này g i là tập các lộ trình độc lập. S l trình
đ c l p c a m tăđ th lu ngăđi u khi n G, ký hi u v(G), bằng s đi u ki n c ng v i 1.
Tiêu chí bao ph l trìnhăđ c l p u c u bao ph đúngăv(G) l trình [12].
1.2.3 Kiểm thử dựa trên đồ thị luồng điều khiển
Ki m th c u trúc d aătrênăđ th lu ngăđi u khi n nhằm t o ra d li u th thỏa
mãn tiêu chí bao ph các thành ph nătrênăđ th nh ăcácăđ̉nh, các cung hay các l trình.
Tùy theo tiêu chí bao ph , chúng ta ph iăxácăđ nh các l trình ki m th c năđ c th c
thi, t đó,ăcácăcaăki m th đ c t oăraăđ th c thi các l trình ki m th t ngă ng. Quy
trình chung áp d ng cho ki m th d aătrênăđ th lu ngăđi u khi năđ t o ra các ca ki m

th đ c minh h a trong Hình 1.2 [12].