BỘ GIÁO DỤC ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
TẠ THANH HẢI
XÂY DỰNG CÔNG CỤ SINH ĐỘT BIẾN
CHO CHƯƠNG TRÌNH LUSTRE
LUẬN VĂN THẠC SĨ KỸ THUẬT
Đà Nẵng - Năm 2017
BỘ GIÁO DỤC ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
TẠ THANH HẢI
XÂY DỰNG CÔNG CỤ SINH ĐỘT BIẾN
CHO CHƯƠNG TRÌNH LUSTRE
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01.01
LUẬN VĂN THẠC SĨ KỸ THUẬT
Người hướng dẫn khoa học: PGS.TS. NGUYỄN THANH BÌNH
Đà Nẵng - Năm 2017
i
LỜI CAM ĐOAN
Tôi xin cam đoan:
a. Những nội dung trong Luận văn này là do tôi thực hiện dưới sự hướng dẫn trực
tiếp của PGS.TS.Nguyễn Thanh Bình;
b. Mọi tham khảo dùng trong Luận văn đều được trích dẫn rõ ràng và trung thực
tên tác giả, tên công trình, thời gian, địa điểm công bố;
c. Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá, tôi xin chịu
hoàn toàn trách nhiệm.
Tác giả
Tạ Thanh Hải
ii
TÓM TẮT LUẬN VĂN
XÂY DỰNG CÔNG CỤ SINH ĐỘT BIẾN CHO
CHƯƠNG TRÌNH LUSTRE
Tóm tắt - Lustre là ngôn ngữ đồng bộ luồng dữ liệu, được sử dụng rộng rãi để phát
triển các hệ thống phản ứng, hệ thống điều khiển và hệ thống giám sát, như lò phản ứng
hạt nhân, máy bay dân sự, xe ôtô... Đặc biệt, Lustre rất thích hợp cho phát triển các hệ
thống thời gian thực. Trong các ứng dụng như vậy, các hoạt động kiểm thử để phát hiện
lỗi giữ một vai trò rất quan trọng. Trong đó, kiểm thử đột biến là một trong những kỹ
thuật được sử dụng phổ biến để đánh giá khả năng phát hiện lỗi của dữ liệu thử. Việc sinh
ra các đột biến từ bộ toán tử đột biến đã đề xuất là một công việc quan trọng và tốn nhiều
chi phí (thời gian, nhân lực), nếu ta thực hiện sinh đột biến bằng phương pháp thủ công.
Trong luận văn này, chúng tôi trình bày giải pháp sinh đột biến một cách tự động cho
chương trình Lustre dựa trên bộ toán tử đã được định nghĩa. Công cụ sinh đột biến tự
động là một yêu cầu cấp bách cho việc kiểm thử đột biến các chương trình Lustre, từ đó
có thể áp dụng kiểm thử đột biến cho chương trình Lustre với quy mô lớn hơn. Công cụ
được thử nghiệm sinh đột biến trên một số lớn các chương trình Lustre và cho kết quả
khả quan.
Từ khóa - Toán tử đột biến, MuLustre; Ngôn ngữ Lustre, Lập trình đồng bộ, Hệ thống
phản ứng.
GENERATING MUTANTS TOOL FOR LUSTRE PROGRAMS
Abstract - Lustre is a data flow synchronous language, which is widely used for the
development of reactive systems, control and monitoring systems, such as nuclear reactors,
civilian aircraft, cars. Especially, Lustre is suitable for developing real-time systems. In such
applications, testing activities for error detection play a very important role. In particular,
mutagenesis testing is one of the most techniques that commonly used for evaluating error
detection of test data. Creating mutations from a set mutant operator is an important and
costly (time, human) task, if applying manual method. In this thesis, we present a
automatically mutant solution for the Lustre program based on a set of defined operators.
Automated mutagenesis tools are an urgent requirement for testing the mutations in Lustre
programs, which can be used to test mutations Lustre program on the larger-scale. The tool
was tested for mutation on a large number of Lustre programs and showed positive results.
Key words - mutation operator; MuLustre; Lustre Programming Language; Synchronous
programming language; Reactive System.
iii
MỤC LỤC
LỜI CAM ĐOAN .............................................................................................................i
TÓM TẮT LUẬN VĂN ................................................................................................ ii
MỤC LỤC ..................................................................................................................... iii
DANH MỤC CÁC TỪ VIẾT TẮT ................................................................................vi
DANH MỤC CÁC BẢNG ........................................................................................... vii
DANH MỤC CÁC HÌNH ........................................................................................... viii
MỞ ĐẦU .........................................................................................................................1
1. Lý do chọn đề tài .....................................................................................................1
2. Mục tiêu và nhiệm vụ ..............................................................................................2
3. Đối tượng và phạm vi nghiên cứu ...........................................................................2
4. Phương pháp nghiên cứu.........................................................................................3
5. Ý nghĩa khoa học và thực tiễn của đề tài ................................................................3
6. Bố cục luận văn .......................................................................................................3
CHƯƠNG 1. TỔNG QUAN KIỂM THỬ ĐỘT BIẾN ...................................................5
1.1. Giới thiệu ..................................................................................................................5
1.2. Lý thuyết kiểm thử đột biến .....................................................................................6
1.2.1. Khái niệm kiểm thử đột biến ..............................................................................7
1.2.2. Cơ sở kiểm thử đột biến .....................................................................................8
1.2.3. Quy trình kiểm thử đột biến ...............................................................................9
1.2.4. Một số khái niệm cơ bản ..................................................................................11
1.2.4.1. Toán tử đột biến ........................................................................................11
1.2.4.2. Đột biến tương đương ...............................................................................12
1.2.4.3. Tỷ lệ đột biến ............................................................................................13
1.2.5. Một số vấn đề của kiểm thử đột biến ...............................................................13
1.3. Một số kỹ thuật cải tiến kiểm thử đột biến .............................................................14
1.3.1. Giảm chi phí tính toán .....................................................................................14
1.3.1.1. Các kỹ thuật làm “ít hơn” (A do “fewer” approach) .................................15
1.3.1.2. Các kỹ thuật làm nhanh hơn (A “do smarter” approach) ..........................17
1.3.2. Tăng tự động hóa .............................................................................................20
1.3.2.1. Tạo dữ liệu thử tự động .............................................................................20
1.3.2.2. Xác định các đột biến tương đương tự động .............................................21
1.4. Ứng dụng của kiểm thử đột biến ............................................................................22
1.4.1. Đột biến mã nguồn ...........................................................................................23
1.4.1.1. Kiểm thử đột biến cho ngôn ngữ Fortran ..................................................23
iv
1.4.1.2. Kiểm thử đột biến cho ngôn ngữ C ...........................................................23
1.4.1.3. Kiểm thử đột biến cho ngôn ngữ Java ......................................................24
1.4.1.4. Kiểm thử đột biến cho ngôn ngữ C# .........................................................24
1.4.1.5. Kiểm thử đột biến cho SQL ......................................................................25
1.4.2. Đột biến đặc tả .................................................................................................25
1.4.2.1. Kiểm thử đột biến cho đặc tả hình thức ....................................................25
1.4.2.2. Kiểm thử đột biến cho môi trường thực thi ..............................................26
1.4.2.3. Kiểm thử đột biến cho dịch vụ Web .........................................................26
1.4.2.4. Kiểm thử đột biến cho các hệ thống mạng................................................27
1.5. Kết luận...................................................................................................................27
CHƯƠNG 2. KIỂM THỬ ĐỘT BIẾN CHO CHƯƠNG TRÌNH LUSTRE ................28
2.1. Giới thiệu ngôn ngữ đồng bộ Lustre ......................................................................28
2.2. Các lớp lỗi của ngôn ngữ Lustre ............................................................................30
2.2.1. Các lỗi về kiểu dữ liệu (Type Faults) ...............................................................31
2.2.2. Các lỗi về biến (Variable Faults) ....................................................................31
2.2.3. Các lỗi về hằng số (Constant Faults) ..............................................................31
2.2.4. Các lỗi về biểu thức (Expression Faults) ........................................................31
2.3. Bộ toán tử đột biến cho chương trình Lustre..........................................................32
2.3.1. Phân loại toán tử đột biến ...............................................................................32
2.3.1.1. Đột biến biến .............................................................................................32
2.3.1.2. Đột biến hằng số........................................................................................32
2.3.1.3. Đột biến biểu thức số học..........................................................................33
2.3.1.4. Đột biến biểu thức quan hệ .......................................................................33
2.3.1.5. Đột biến biểu thức luận lý .........................................................................33
2.3.1.6. Đột biến biểu thức một ngôi......................................................................33
2.3.2. Bộ toán tử đột biến...........................................................................................33
2.4. Kết luận...................................................................................................................34
CHƯƠNG 3. CÔNG CỤ SINH ĐỘT BIẾN TỰ ĐỘNG CHO CHƯƠNG TRÌNH
LUSTRE ........................................................................................................................35
3.1. Giới thiệu ................................................................................................................35
3.2. Các kết quả nghiên cứu liên quan...........................................................................36
3.3. Công cụ sinh đột biến cho chương trình Lustre .....................................................38
3.3.1. Quy trình sinh đột biến cho chương trình Lustre.............................................38
3.3.2. Phát triển công cụ sinh đột biến ......................................................................39
3.3.2.1. Bộ phân tích cú pháp (Lustre Parser) ........................................................39
3.3.2.2. Công cụ sinh đột biến MuLustre ...............................................................43
v
3.4. Thử nghiệm và đánh giá .........................................................................................44
3.4.1. Thử nghiệm ......................................................................................................44
3.4.2. Dữ liệu thử .......................................................................................................45
3.4.3. Đánh giá ..........................................................................................................48
3.5. Kết luận...................................................................................................................49
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ....................................................................50
TÀI LIỆU THAM KHẢO .............................................................................................52
QUYẾT ĐỊNH GIAO ĐỀ TÀI
BẢN SAO KẾT LUẬN CỦA HỘI ĐỒNG, BẢN SAO NHẬN XÉT CỦA CÁC
PHẢN BIỆN.
vi
DANH MỤC CÁC TỪ VIẾT TẮT
AAR
ABS
ACR
ARO
AOR
ASR
BOFs
CAR
CBT
CNR
CRO
CRP
CSR
DDR
DSA
FSBs
FSM
GLR
LCR
LRO
MS
MSG
PFSM
ROR
RRO
RSR
SAN
SAR
SCR
SDL
SRC
SVR
UOI
UOD
VRO
Array Reference For Array Reference Replacement
Absolute Value Insertion
Array Reference For Constant Replacement
Arithmetic Replacement Operator
Arithmetic Operator Replacement
Array Reference For Scalar Variable Replacement
Buffer Overflows
Constant For Array Reference Replacement
Constraint-based testing
Comparable Array Name Replacement
Constant Replacement Operator
Constant Replacement
Constant For Scalar Variable Replacement
Dynamic Domain Reduction
Data Statement Alterations
Format String Bugs
Finite State Machines
Goto Label Replacement
Logical Connector Replacement
Logical Replacement Operator
Mutation Score
Mutant Schema Generation
Probabilistic Finite State Machines
Relational Operator Replacement
Relational Replacement Operator
Return Statement Replacement
Statement Analysis
Scalar Variable For Array Reference Replacement
Scalar For Constant Replacement
Statement DeLetion
Source Constant Replacement
Scalar Variable Replacement
Unary Operator Insertion
Unary Operator Delete
Variable Replacement Operator
vii
DANH MỤC CÁC BẢNG
Số hiệu
Tên bảng
hình
Trang
1.1.
Ví dụ minh họa các đột biến
7
1.2.
Ví dụ toán tử đột biến ROR
11
1.3.
Tập các toán tử đột biến đầu tiên dùng trong Mothra (cho
ngôn ngữ Fortran)
11
1.4.
Ví dụ đột biến tương đương
13
2.1.
Giá trị luồng X và luồng Y với chu kỳ ti (i=0..5)
30
2.2.
Các toán tử đề xuất cho Lustre
33
2.3.
Số đột biến sẽ được sinh ra
34
3.1.
Các công cụ đột biến đã được công bố
37
3.2.
Kết quả sinh đột biến
44
3.3.
Số đột biến được tạo ra từ bộ toán tử đột biến
46
3.4.
Kết quả thử nghiệm với bộ dữ liệu thử ngẫu nhiên
47
viii
DANH MỤC CÁC HÌNH
Số hiệu
hình
Tên hình
Trang
1.1.
Tiến trình thực hiện kiểm thử đột biến.
10
1.2.
Ví dụ phương thức chương trình gốc
19
1.3.
Phiên bản đột biến của chương trình gốc (Hình 1.2)
20
2.1.
Mô hình hệ thống phản ứng
28
2.2.
Ví dụ một đoạn chương trình Lustre
29
2.3.
Ví dụ một chương trình Lustre đơn giản
30
3.1.
Quy trình sinh đột biến cho Lustre
38
3.2.
Kiến trúc hệ thống công cụ sinh đột biến
39
3.3.
Các bước trình biên dịch thông thường thực hiện
40
3.4.
Quy trình xây dựng trình biên dịch dùng Lex và Yacc
41
3.5.
Cấu trúc một bộ phân tích từ vựng của Lex
42
3.6.
Cấu trúc một bộ phân tích cú pháp của Yacc
42
3.7.
Biểu đồ so sánh các đột biến được sinh ra
45
3.8.
Tỷ lệ đột biến của các bộ dữ liệu thử
48
1
MỞ ĐẦU
1. Lý do chọn đề tài
Trong đời sống xã hội ngày nay, công nghệ thông tin đã được ứng dụng trong tất
cả các lĩnh vực, từ quản lý kinh tế, giải trí, năng lượng đến an ninh quốc phòng. Việc
đảm bảo chất lượng phần mềm luôn là một yêu cầu tất yếu trong đời sống công nghệ,
đặc biệt với các hệ thống đòi hỏi sự an toàn cao như hệ thống điều khiển lò phản ứng
hạt nhân, điều khiển máy bay, điều khiển ô tô,… mọi sự cố sai sót của phần mềm điều
khiển sẽ gây ra những hậu quả nghiêm trọng.
Kiểm thử phần mềm, với mục tiêu tìm kiếm các lỗi chưa phát hiện và khắc phục
chúng, nhằm đảm bảo chất lượng và tăng độ tin cậy của phần mềm. Kiểm thử phần
mềm là giai đoạn rất tốn kém về chi phí và nhân lực, nó chiếm khoảng từ 40%-50%
tổng chi phí của dự án phần mềm. Riêng các hệ thống đòi hỏi độ tin cậy, an toàn cao
như lò phản ứng hạt nhân, máy bay dân sự, xe ôtô… thì chi phí và thời gian thực hiện
cho các hoạt động kiểm thử là rất lớn. Hoạt động kiểm thử giúp cho lập trình viên và
kiểm thử viên phát hiện càng nhiều lỗi và càng sớm càng tốt [1], [4].
Kiểm thử đột biến (mutation testing) là một kỹ thuật có khả năng phát hiện được
các lỗi của phần mềm từ những sai sót do lập trình viên phạm phải. Kiểm thử đột biến
tạo ra các phiên bản lỗi (đột biến) của chương trình gốc dựa vào bộ toán tử đột biến đã
được thiết kế. Với mục tiêu là chọn được bộ dữ liệu thử có khả năng phát hiện (diệt)
được các đột biến, đồng thời thực hiện đánh giá chất lượng bộ dữ liệu thử. Kiểm thử
đột biến là một trong những kỹ thuật được sử dụng khá phổ biến nhờ vào tính hiệu quả
và khả năng tự động hóa của nó. Kiểm thử đột biến chèn lỗi vào chương trình gốc để
tạo ra phiên bản lỗi. Sau đó, thực thi phiên bản lỗi và chương trình gốc trên cùng dữ
liệu thử để đánh giá chất lượng của dữ liệu thử, nghĩa là đánh giá khả năng phát hiện
lỗi của dữ liệu thử đó.
Hệ thống phản ứng (reactive system) là hệ thống mà khi hoạt động nó sẽ phản
ứng lại các sự kiện được tác động từ môi trường bên ngoài. Nó là một thành phần quan
trọng trong đời sống công nghệ, như: hệ thống ABS của xe ôtô, hệ thống kiểm soát
bay trong máy bay…[5]. Nó liên tục tương tác với môi trường bên ngoài và thực thi
“phản ứng” lại sự tác động đó. Hệ thống phản ứng có thể được xem là đang ở một
trạng thái nhất định và đợi thông tin đầu vào (input). Với mỗi đầu vào, nó thực hiện
tính toán để sinh đầu ra (output) và chuyển sang một trạng thái mới. Kỹ thuật lập trình
đồng bộ thường được sử dụng để phát triển các hệ thống phản ứng.
Lập trình đồng bộ [6] đã được giới thiệu vào cuối những năm của thập niên 80
như là một phương pháp tiếp cận để thiết kế các hệ thống phản ứng. Kể từ đó, nó đã
được sử dụng rộng rãi, chủ yếu trong các lĩnh vực đòi hỏi độ an toàn cao như hệ thống
điện tử, vận tải, sản xuất năng lượng. Một trong những lợi thế quan trọng của cách tiếp
2
cận đồng bộ này là nhằm cung cấp một khuôn khổ chính thức, hiệu quả và đồng nhất
cho các hoạt động phát triển - thiết kế, cài đặt và xác minh các hệ thống phản ứng. Một
số ngôn ngữ lập trình đồng bộ được phát triển, như: Esterel, Signal hoặc Lustre. Trong
đó, Lustre [7] là ngôn ngữ đồng bộ luồng dữ liệu, được thiết kế năm 1984 bởi Viện
IMAG tại Grenoble. Lustre được sử dụng phổ biến cho việc xây dựng các mô hình,
các thiết kế hệ thống điều khiển trong một số lĩnh vực công nghiệp như lĩnh vực điện
tử, ôtô và năng lượng… Đối với các hệ thống này, yếu tố an toàn phải được quan tâm
hàng đầu, bởi vì nếu có lỗi xảy ra có thể dẫn đến thảm họa nghiêm trọng. Vì vậy, vai
trò của hoạt động kiểm thử trong phát triển các hệ thống này càng quan trọng hơn.
Việc sinh ra các đột biến từ bộ toán tử đột biến đã đề xuất [2] là một công việc
quan trọng và tốn nhiều chi phí (thời gian, nhân lực), nếu ta thực hiện sinh đột biến
bằng phương pháp thủ công. Bên cạnh đó, việc sinh đột biến bằng phương pháp thủ
công, chúng ta cũng không thể áp dụng kiểm thử đột biến cho chương trình Lustre với
quy mô công nghiệp. Do đó, nhu cầu cần có công cụ sinh đột biến tự động là một yêu
cầu cấp bách cho việc kiểm thử đột biến các chương trình Lustre, từ đó có thể áp dụng
kiểm thử đột biến cho chương trình Lustre với quy mô lớn hơn. Từ các yêu cầu trên,
được sự hướng dẫn của Thầy PGS.TS Nguyễn Thanh Bình, tôi chọn đề tài “ Xây dựng
công cụ sinh đột biến cho chương trình Lustre” để nghiên cứu, báo cáo cho Luận văn
thạc sĩ của mình.
2. Mục tiêu và nhiệm vụ
a. Mục tiêu
Mục tiêu của Luận văn là nghiên cứu các kỹ thuật kiểm thử đột biến. Trên cơ sở
đó đề xuất áp dụng kiểm thử đột biến để sinh đột biến cho chương trình Lustre.
b. Nhiệm vụ
- Nghiên cứu kỹ thuật kiểm thử đột biến.
- Ngôn ngữ đồng bộ Lustre.
- Mã nguồn Lustre Parser.
- Phân tích và thiết kế hệ thống sinh đột biến tự động.
- Xây dựng công cụ sinh tự động đột biến cho chương trình Lustre từ bộ toán tử
đột biến đã được định nghĩa.
- Đánh giá kết quả thực nghiệm.
- Kết luận và hướng phát triển của đề tài.
3. Đối tượng và phạm vi nghiên cứu
a. Đối tượng nghiên cứu
- Kiểm thử phần mềm.
- Kiểm thử đột biến.
- Ngôn ngữ Lustre.
- Bộ phân tích cú pháp và văn phạm cho ngôn ngữ Lustre.
- Ngôn ngữ lập trình để phát triển công cụ sinh tự động đột biến.
3
- Kỹ thuật lập trình ngôn ngữ Lustre.
b. Phạm vi nghiên cứu
Tập trung nghiên cứu ngôn ngữ đồng bộ Lustre, bộ phân tích cú pháp cho ngôn
ngữ Lustre, xác định các lỗi mà người thiết kế chương trình phạm phải và sử dụng bộ
toán tử đột biến [2] cho Lustre; sử dụng giả thuyết lỗi đơn (tức tại mỗi thời điểm chỉ
xảy ra một lỗi) và xét lỗi trên các khối cơ bản của Lustre.
4. Phương pháp nghiên cứu
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ử đột
biến nói riêng.
- Nghiên cứu lý thuyết về ngôn ngữ lập trình Lustre.
- Nghiên cứu bộ toán tử đột biến cho chương trình Lustre đã được đề xuất trong
[2].
- Nghiên cứu bộ phân tích cú pháp và văn phạm cho ngôn ngữ Lustre.
- Nghiên cứu các giải pháp sinh tự động đột biến cho chương trình Lustre.
Phương pháp thực nghiệm
- Cài đặt module để thực hiện tối ưu hóa các đột biến được sinh ra cho chương
trình Lustre.
- Kiểm tra, thử nghiệm, nhận xét và đánh giá kết quả.
5. Ý nghĩa khoa học và thực tiễn của đề tài
Ý nghĩa khoa học
Góp phần hoàn thiện quy trình kiểm thử đột biến cho chương trình Lustre.
Ý nghĩa thực tiễn
Công cụ sinh đột biến tự động để sinh đột biến từ bộ toán tử đột biến đã đề xuất
cho chương trình Lustre.
6. Bố cục luận văn
Chương 1. TỔNG QUAN KIỂM THỬ ĐỘT BIẾN
Trong chương này giới thiệu tổng quan về kiểm thử đột biến và các kỹ thuật kiểm
thử đột biến, tình hình nghiên cứu và ứng dụng của kiểm thử đột biến trong nước và
trên thế giới.
Chương 2. KIỂM THỬ ĐỘT BIẾN CHO CHƯƠNG TRÌNH LUSTRE
Chương này tập trung nghiên cứu ngôn ngữ đồng bộ Lustre, bộ phân tích cú pháp
cho ngôn ngữ Lustre, xác định các lỗi mà người thiết kế chương trình phạm phải và sử
dụng bộ toán tử đột biến cho Lustre; sử dụng giả thuyết lỗi đơn (tức tại mỗi thời điểm
chỉ xảy ra một lỗi) và xét lỗi trên các khối cơ bản của Lustre.
Chương 3. XÂY DỰNG CÔNG CỤ SINH ĐỘT BIẾN CHO CHƯƠNG TRÌNH
LUSTRE
4
Trong chương này, nghiên cứu giải pháp để xây dựng công cụ sinh đột biến tự
động cho chương trình Lustre dựa trên bộ toán tử đột biến đã được định nghĩa. Thử
nghiệm khả năng sinh đột biến cho một số chương trình được phát triển bởi ngôn ngữ
Lustre. Từ đó, đánh giá khả năng sinh đột biến tự động của công cụ và tính tỷ lệ đột
biến dựa vào phương pháp sinh dữ liệu thử ngẫu nhiên cho một số ứng dụng Lustre.
Chương 1. TỔNG QUAN KIỂM THỬ ĐỘT BIẾN
Chương 1 giới thiệu tổng quan về kiểm thử đột biến và các kỹ thuật kiểm thử đột
biến, tình hình nghiên cứu và ứng dụng của kiểm thử đột biến trong nước và trên
thế giới.
1.1. Giới thiệu
Kiểm thử là một công đoạn rất quan trọng, quyết định đến việc đánh giá chất
lượng của một sản phẩm phần mềm. Đây là một quá trình tìm lỗi được tiến hành trong
tất cả các giai đoạn tạo nên một sản phẩm phần mềm và nó là sự đánh giá cuối cùng về
các đặc tả, thiết kế, mã hóa… Mục đích của kiểm thử nhằm đảm bảo rằng tất cả các
thành phần của phần mềm “ăn khớp”, vận hành như mong đợi và phù hợp với các tiêu
chuẩn thiết kế. Kiểm thử không chứng minh được phần mềm là hết lỗi mà nó chỉ giúp
cho người viết mã tìm ra và có biện pháp khắc phục càng nhiều lỗi, càng sớm, càng
tốt.
Để thực hiện tốt kiểm thử, ngoài việc nắm vững các kỹ thuật kiểm thử điển hình,
người kiểm thử cần xây dựng kế hoạch kiểm thử, chuẩn bị dữ liệu thử, tiến hành kiểm
thử, viết báo cáo về kết quả kiểm thử, và cần biết quản lý toàn bộ công việc kiểm thử.
Hiện nay, có rất nhiều kỹ thuật kiểm thử khác nhau đang được nghiên cứu, phát
triển và ứng dụng. Các kỹ thuật kiểm thử được chia thành hai nhóm chính: các kỹ
thuật kiểm thử hộp đen và các kỹ thuật kiểm thử hộp trắng. Với mục đích phát hiện lỗi,
hoạt động kiểm thử phần mềm thường phải trải qua các bước chính: tạo dữ liệu thử,
thực thi phần mềm trên dữ liệu thử và quan sát kết quả nhận được. Trong các bước
này, 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ỉ 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ột dữ liệu thử được xem là “tốt” theo nghĩa nó có khả năng phát hiện ra lỗi cụ
thể mà các dữ liệu thử khác không phát hiện ra. Ngược lại, một dữ liệu thử được xem
là “không tốt” theo nghĩa nó không có khả năng phát hiện một lỗi nào cả, nhưng rất
khó để xác định được bởi vì chúng ta không biết chương trình có lỗi hay không. Trong
cả hai trường hợp, chúng ta không có cách nào để đo được hiệu quả của dữ liệu thử.
Điều quan trọng là phải biết liệu có tồn tại lỗi để kiểm thử hay không, nhưng nếu biết
được điều này thì kiểm thử là dư thừa [8]. Để gỡ bỏ nghịch lý này, người ta sử dụng
các tiêu chuẩn để cung cấp các yêu cầu cho chất lượng dữ liệu thử, và vì vậy, đưa ra
một thước đo để đánh giá và cải tiến bộ dữ liệu thử. Ví dụ, các bộ dữ liệu thử được cải
tiến lặp đi lặp lại cho đến khi chúng thực hiện tất cả các câu lệnh trong chương trình
(kiểm thử câu lệnh), hoặc thực hiện tất cả các quyết định cho cả hai trường hợp đúng
và sai (kiểm thử nhánh). Nếu phù hợp với tiêu chuẩn được xem xét thì dữ liệu thử
6
được xem là có chất lượng (đối với tiêu chuẩn đó), và có nhiều khả năng chỉ ra các lỗi
hơn nếu chúng tồn tại.
Tuy nhiên, các tiêu chuẩn trên thường không tập trung vào nguyên nhân thất bại
của chương trình – được gọi là các lỗi. Tiêu chuẩn chất lượng đột biến là một loại tiêu
chuẩn mà cung cấp một thước đo để đánh giá tính hiệu quả của dữ liệu thử bằng cách
cho thấy các dữ liệu thử có thể làm lộ ra tất cả các lỗi đơn giản có thể có của một
chương trình (ví dụ, sự khác biệt một từ đơn hoặc thay thế tên biến sai), tương tự như
kiểm thử câu lệnh cho thấy tính hiệu quả của dữ liệu thử bằng cách đảm bảo rằng mọi
dòng lệnh đã được thực thi. Tuy nhiên, bộ dữ liệu thử có khả năng sẽ không thể xác
định được tất cả các lỗi. Trong trường hợp như vậy, tiêu chuẩn chất lượng đột biến
cung cấp một thước đo để xác định việc cải tiến bằng cách lựa chọn một bộ dữ liệu thử
mới. Ví dụ, một bộ dữ liệu thử phát hiện 80% lỗi sẽ cho phép tạo ra dữ liệu thử tập
trung vào 20% còn lại. Thước đo này cho phép kiểm soát, đánh giá và cải tiến dữ liệu
thử lặp đi lặp lại dựa trên cơ sở kiểm thử đột biến (mutation testing) [9].
Kiểm thử đột biến là một trong những kỹ thuật được phát triển rất sớm và đang
được ứng dụng rộng rãi. Đây là kỹ thuật kiểm thử dựa trên lỗi nhằm cung cấp một tiêu
chuẩn kiểm thử, được gọi là tỷ lệ đột biến. Tỷ lệ đột biến được sử dụng để đánh giá tập
dữ liệu thử theo khả năng phát hiện lỗi.
Nguyên tắc cơ bản của kiểm thử đột biến là các lỗi được sử dụng nhằm biểu diễn
các sai sót mà các lập trình viên thường phạm phải. Các lỗi như thế được chèn vào
trong chương trình gốc cần được kiểm thử, bởi một sự thay đổi cú pháp, nhằm tạo ra
tập các chương trình lỗi được gọi là các đột biến, trong đó mỗi đột biến chỉ chứa một
sự thay đổi cú pháp. Để đánh giá chất lượng của một tập dữ liệu thử, các đột biến được
thực thi trên tập các dữ liệu thử nhằm kiểm tra các lỗi được chèn vào có được phát
hiện.
Năm 1971, Dick Lipton đề xuất phương pháp kiểm thử đột biến, sau đó lĩnh vực
này được đánh dấu sự ra đời và phổ biến bởi DeMillo [8] và Sayward [9]. Kỹ thuật
này đã đạt được những kết quả đáng kể. Hiện nay, có nhiều công trình nghiên cứu phát
triển hơn nữa về khả năng ứng dụng và làm cho kiểm thử đột biến trở thành một kỹ
thuật kiểm thử thực tế hơn.
1.2. Lý thuyết kiểm thử đột biến
Trước khi trình bày lý thuyết kiểm thử đột biến, chúng ta bắt đầu bởi một ý tưởng
đơn giản để ước lượng số lượng cá có trong một cái hồ. Một cách để thực hiện việc đó
là chúng ta đánh dấu một số lượng cá và thả vào hồ (giả sử, 1000 con cá), sau đó đánh
bắt một số cá và đếm số con cá có đánh dấu. Nếu chúng ta bắt được 1000 con cá và
100 trong số đó bị đánh dấu, như vậy 1/10 số cá trong hồ bị đánh dấu, khi đó số cá
thực sự trong hồ có thể được ước lượng khoảng 10000 con. Nếu chúng ta bắt được tất
cả các cá bị đánh dấu, chúng ta có thể cho rằng toàn bộ cá trong hồ đã bị đánh bắt.
7
Kỹ thuật kiểm thử đột biến được xây dựng dựa trên ý tưởng này. Chúng ta đưa
vào mã nguồn một số lỗi “bị đánh dấu”, sau đó tìm cách xác định chúng. Nếu chúng ta
xác định được tất cả các lỗi này, “lưới” của chúng ta có thể cũng đã bắt được nhiều các
loại “cá” khác, đó chính là các lỗi chưa biết.
1.2.1. Khái niệm kiểm thử đột biến
Kiểm thử đột biến là một kỹ thuật kiểm thử hộp trắng, hay còn gọi kỹ thuật kiểm
thử cấu trúc. Nó là một công cụ hỗ trợ cho công việc kiểm thử, được tạo ra với mục
đích kiểm tra, đánh giá bộ dữ liệu thử và giúp cho việc tạo ra các bộ dữ liệu thử có khả
năng phát hiện lỗi của chương trình.
Trong khi thực hiện kiểm thử đột biến, chúng ta tạo ra các phiên bản lỗi của
chương trình gốc bằng cách chèn lỗi vào mã nguồn của chương trình cần kiểm thử.
Mỗi phiên bản chỉ chứa đúng một lỗi và được gọi là một đột biến (mutant). Mỗi đột
biến được tạo ra bởi chỉ một sự thay đổi cú pháp trong chương trình gốc. Mỗi sự thay
đổi cú pháp là một luật hay còn được gọi là một toán tử đột biến (mutation operator).
Các toán tử đột biến được định nghĩa sẵn để tạo ra sự thay đổi cú pháp dựa trên các lỗi
mà các lập trình viên thường phạm phải. Ví dụ, thay một biến bởi một biến khác cùng
kiểu, hoặc thay một toán tử số học bởi một toán tử số học khác,…
Một cách cụ thể, đột biến P’ của chương trình gốc P là một chương trình tương tự
với chương trình gốc P; P’ khác P do chỉ một thay đổi nhỏ về cú pháp trong chương
trình. Chẳng hạn, trong Bảng 1.1, P là chương trình gốc, P’ và P” là các đột biến của
P bằng cách thay đổi cú pháp trong phép toán số học, thay thế (s=a+b) bởi (s=a-b) đối
với P’; thay (s=a+b) bởi (s=a*b) đối với P”. Các câu lệnh bị đột biến được đánh dấu
bởi ký hiệu ∆.
Bảng 1.1. Ví dụ minh họa các đột biến
Chương trình gốc P
Đột biến P’
node sum(a,b:int)
returns (s:int);
let
s=a+b;
tel;
node sum(a,b:int)
returns (s:int);
let
∆ s=a-b;
tel;
Đột biến P’’
node sum(a,b:int)
returns (s:int);
let
∆ s=a*b;
tel;
Dựa trên tiêu chuẩn chất lượng đột biến, lần lượt các đột biến sẽ được thực hiện
với một bộ dữ liệu thử để xác định có bao nhiêu đột biến thất bại (tức là cung cấp đầu
ra không đúng cho đầu vào kiểm thử đó so với chương trình gốc). Thất bại càng nhiều,
càng lớn thì bộ dữ liệu thử càng chất lượng. Mục đích của kiểm thử viên là tạo ra dữ
liệu thử mới để cải tiến chất lượng của các dữ liệu thử hiện có. Một kết quả khá hữu
ích của phương pháp này là việc cải tiến chất lượng của dữ liệu thử sẽ cải thiện sự tin
tưởng của kiểm thử viên vào tính đúng đắn của chương trình gốc.
8
1.2.2. Cơ sở kiểm thử đột biến
Kiểm thử đột biến hứa hẹn sẽ hiệu quả trong việc xác định dữ liệu thử thích hợp
có thể được dùng để phát hiện các lỗi thực sự [10]. Tuy nhiên, số lượng các lỗi tiềm
năng cho một chương trình nhất định là rất lớn, không thể tạo ra đột biến đại diện cho
tất cả các lỗi. Vì vậy, kiểm thử đột biến truyền thống chỉ nhắm mục tiêu một tập con
của các phiên bản lỗi, là những phiên bản gần với phiên bản đúng của chương trình với
hy vọng rằng đó sẽ là đủ để mô phỏng cho tất cả các lỗi. Lý thuyết này dựa trên hai giả
thuyết cơ bản: giả thuyết “lập trình viên giỏi” (competent programmer hypothesis CPH) [8], [9] và giả thuyết “hiệu ứng liên kết” (coupling effect hypothesis - CEH) [8].
- Giả thuyết lập trình viên giỏi được giới thiệu đầu tiên vào năm 1978 do
DeMillo và các đồng nghiệp của ông [8]. Giả thuyết này cho rằng thông thường các
lập trình viên đều rất giỏi và họ sẽ không bao giờ viết ra các chương trình một cách tuỳ
tiện, cẩu thả. Như vậy, một lập trình viên trong quá trình viết lệnh cho chương trình
nếu có sai sót, thì cũng sẽ tạo ra được chương trình rất gần với phiên bản đúng của
chương trình, có nghĩa là một chương trình không đúng đó chỉ có một vài thay đổi về
cú pháp rất nhỏ so với chương trình đúng. Những thay đổi nhỏ này nếu không được
phát hiện và chỉnh sửa, nó sẽ làm cho kết quả đầu ra không như mong muốn. Các
chương trình này vẫn được biên dịch và thực thi một cách bình thường và lập trình
viên không thể phát hiện ra được lỗi của nó. Hơn thế, các chương trình này có thể
được đánh giá tốt trong các quá trình kiểm thử. Các lỗi phạm phải bởi lập trình viên
được gọi là các lỗi đơn giản. Do vậy, trong kiểm thử đột biến, chỉ các lỗi đơn giản
được tạo ra bởi việc thực hiện các thay đổi nhỏ về cú pháp được áp dụng, nhằm biểu
diễn các lỗi phạm phải bởi các “lập trình viên giỏi”. Chi tiết về CPH có thể được tìm
thấy trong công trình nghiên cứu của Acree và đồng nghiệp [11] và một thảo luận lý
thuyết sử dụng khái niệm các lân cận của chương trình cũng có thể được tìm thấy
trong công trình nghiên cứu của Budd và đồng nghiệp. [12].
- Giả thuyết hiệu ứng liên kết cũng được đề xuất bởi DeMillo và các đồng nghiệp
vào năm 1978 [8]. Không giống như các CPH liên quan đến hành vi của một lập trình
viên, hiệu ứng liên kết liên quan đến các lỗi được sử dụng trong phân tích đột biến.
Giả thuyết này cho rằng “các lỗi phức tạp được liên kết từ các lỗi đơn giản, như vậy bộ
dữ liệu thử đủ khả năng phát hiện tất cả các lỗi đơn giản trong chương trình thì cũng
có khả năng phát hiện các lỗi phức tạp với tỉ lệ cao”. Trên cơ sở giả thuyết trên, Offutt
[13], [14] đưa ra giả thuyết “hiệu ứng liên kết đột biến” (mutation coupling effect), với
định nghĩa chính xác hơn về lỗi đơn giản và lỗi phức tạp: lỗi đơn giản được biểu diễn
bởi một đột biến đơn giản bằng cách chỉ thực hiện một thay đổi nhỏ về cú pháp, trong
khi lỗi phức tạp được biểu diễn bởi một đột biến phức tạp bằng cách thực hiện một vài
thay đổi nhỏ về cú pháp. Theo Offutt, giả thuyết hiệu ứng liên kết là "lỗi phức tạp
được liên kết bởi các lỗi đơn giản theo cách mà một bộ dữ liệu thử có thể phát hiện tất
9
cả các lỗi đơn giản trong một chương trình sẽ phát hiện các lỗi phức tạp với một tỷ lệ
cao" [14]. Giả thuyết hiệu ứng liên kết đột biến trở thành: “các đột biến phức tạp được
liên kết từ các đột biến đơn giản, sao cho bộ dữ liệu thử đủ khả năng phát hiện tất cả
các đột biến đơn giản trong chương trình thì cũng có khả năng phát hiện các đột biến
phức tạp với tỉ lệ cao”. Theo giả thuyết này, các đột biến được sử dụng trong kiểm thử
đột biến chỉ giới hạn trong các đột biến đơn giản.
Có nhiều công trình nghiên cứu lý thuyết cũng như nghiên cứu thực nghiệm
khẳng định giả thuyết hiệu ứng liên kết là thực tế và đúng [13], [14], [15]. Lipton và
Sayward tiến hành một nghiên cứu thực nghiệm bằng cách sử dụng một chương trình
nhỏ, FIND [15]. Trong thử nghiệm của họ, một mẫu nhỏ của đột biến mức 2, đột biến
mức 3 và mức 4 được kiểm tra. Các kết quả cho thấy rằng một bộ dữ liệu thử đầy đủ
được tạo ra từ đột biến mức 1 cũng thích hợp cho các mẫu của đột biến mức k (k =
2;… 4). Offutt mở rộng thử nghiệm này bằng cách sử dụng tất cả đột biến mức 2 có
thể với hai chương trình, MID và TRITYP [13], [14]. Kết quả cho thấy rằng các dữ
liệu thử phát triển để diệt đột biến mức 1 đã diệt hơn 99% đột biến mức 2 và mức 3.
Nghiên cứu này ngụ ý rằng giả thuyết hiệu ứng liên kết đột biến là hợp lý cũng đồng
quan điểm với các nghiên cứu thực nghiệm của Morell [16]. Tính hợp lý của hiệu ứng
liên kết đột biến cũng được xem xét trong các nghiên cứu lý thuyết của Wash [17], [18]
và Kappoor [19].
1.2.3. Quy trình kiểm thử đột biến
Kiểm thử đột biến là một quy trình được thực hiện lặp đi lặp lại qua nhiều bước
khác nhau để cải tiến dữ liệu thử đối với một chương trình. Hình 1.1 minh họa quy
trình kiểm thử đột biến. Trong quy trình này, các bước biểu diễn bởi nét liền là có thể
tự động hóa, các bước biểu diễn bằng nét đứt thường được xử lý thủ công.
Các tham số ban đầu để xử lý là chương trình gốc P (cần được kiểm thử) và bộ
dữ liệu thử T. Trước tiên, bằng cách phán xét, chương trình gốc P phải được thực hiện
với các dữ liệu thử trong T. Nếu có bất kỳ kết quả đầu ra nào không đúng thì T đã
chứng minh rằng chương trình gốc P chứa lỗi. Các lỗi này phải được chỉnh sửa trước
khi tiếp tục quá trình.
Khi đã xác định được tất cả các dữ liệu thử trong T cung cấp các đầu ra chính xác,
công đoạn tiếp theo là tạo ra một tập M – tập các đột biến P’ của chương trình gốc P.
Sau khi tạo ra tập M chứa tất cả các đột biến, lần lượt các đột biến P’ này được thực
hiện với T và các kết quả đầu ra của chúng được so sánh với các kết quả đầu ra của
chương trình gốc P, lúc này có hai kịch bản khác nhau có thể xảy ra:
10
Hình 1.1. Tiến trình thực hiện kiểm thử đột biến.
- Một là, lỗi được chèn vào trong chương trình đột biến P’ được nhận biết, nghĩa
là chương trình P và đột biến P’ cho ra các kết quả khác nhau. Trong trường hợp này,
đột biến P’ được gọi là bị diệt (killed) bởi dữ liệu thử T. Khi đó, T được gọi là dữ liệu
thử thích hợp vì nó có khả năng phát hiện được sự khác nhau giữa chương trình gốc P
và đột biến P’. Các đột biến như vậy trở nên không cần thiết vì dữ liệu thử hiện có đã
phân biệt được chúng, và do đó chúng sẽ bị loại bỏ khỏi tập đột biến M.
- Hai là, chương trình gốc P và đột biến P’ cho ra kết quả hoàn toàn giống nhau.
Trong trường hợp này, có thể có hai khả năng xảy ra. Khả năng thứ nhất là dữ liệu thử
T không đủ tốt (hay được gọi là dữ liệu thử không thích hợp), chúng ta sẽ phải tiến
hành thực hiện kiểm thử lại với các dữ liệu thử tốt hơn. Khả năng thứ hai là chương
trình P và đột biến P’ là những chương trình tương tự nhau, mọi dữ liệu thử đều không
thể phân biệt sự khác nhau giữa chúng. Trong cả hai trường hợp này, đột biến P’ được
cho là còn sống (alive).
- Khi tất cả các dữ liệu thử trong T đã được thực hiện trên tất cả các đột biến
trong M, các đột biến đó vẫn còn sống (vẫn còn tồn tại trong M) tức là cho đến lúc này
vẫn không thể phân biệt chúng với chương trình gốc P. Nói cách khác, không tồn tại
dữ liệu thử trong T làm cho những đột biến còn sống tính toán kết quả đầu ra khác so
với P. Những đột biến này trở thành mục tiêu cho lần lặp tiếp theo, trong đó dữ liệu
thử mới sẽ được tạo ra với nỗ lực để phân biệt được chúng.
Quá trình này tiếp tục cho đến khi tất cả các đột biến trong M bị diệt. Tuy nhiên,
để diệt được các đột biến không phải là một công việc dễ dàng vì một số đột biến có
thể có ngữ nghĩa giống với chương trình gốc. Những đột biến này được gọi là đột biến
tương đương và sẽ luôn luôn tạo ra kết quả đầu ra giống với với bất kỳ dữ liệu vào
nào.
- Xem thêm -