Luận án Tiến sĩ Kỹ thuật: Cải tiến chất lượng kiểm thử đột biến bậc cao

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:136

Thêm vào BST

Báo xấu

11
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án Tiến sĩ Kỹ thuật "Cải tiến chất lượng kiểm thử đột biến bậc cao" trình bày các nội dung chính sau: Tổng quan kiểm thử đột biến; Cải tiến chất lượng kiểm thử đột biến bậc cao dựa trên phân loại đột biến bậc một; Đánh giá toán tử đột biến và hiệu quả của các ca kiểm thử bằng kiểm thử đột biến; Dự báo chất lượng của kiểm thử đột biến bậc cao dựa trên học máy.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Kỹ thuật: Cải tiến chất lượng kiểm thử đột biến bậc cao

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐỖ VĂN NHỎ CẢI TIẾN CHẤT LƯỢNG KIỂM THỬ ĐỘT BIẾN BẬC CAO LUẬN ÁN TIẾN SĨ KỸ THUẬT Đà Nẵng – 2024
ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐỖ VĂN NHỎ CẢI TIẾN CHẤT LƯỢNG KIỂM THỬ ĐỘT BIẾN BẬC CAO Chuyên ngành: Khoa học máy tính Mã số: 9 48 01 01 LUẬN ÁN TIẾN SĨ KỸ THUẬT NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. PGS. TS. Nguyễn Thanh Bình 2. TS. Nguyễn Quang Vũ Đà Nẵng - 2024
i LỜI CAM ĐOAN Tôi tên là Đỗ Văn Nhỏ. Tôi xin cam đoan các kết quả trình bày trong luận án là công trình nghiên cứu của tôi dưới sự hướng dẫn của các giảng viên hướng dẫn. Các số liệu, các kết quả trình bày trong luận án hoàn toàn trung thực và chưa được công bố trong các công trình trước đây. Các dữ liệu tham khảo được trích dẫn đầy đủ. Đà Nẵng, ngày 21 tháng 10 năm 2024 Đỗ Văn Nhỏ
ii LỜI CẢM ƠN Trước tiên, tác giả xin gửi lời cảm ơn đến Phòng Đào tạo và Khoa Công nghệ Thông tin, Trường Đại học Bách khoa - Đại học Đà Nẵng đã tạo mọi điều kiện thuận lợi cho tác giả trong thời gian nghiên cứu và hoàn thành Luận án. Với lòng kính trọng và biết ơn sâu sắc, tác giả xin gửi lời cảm ơn tới hai thầy giáo hướng dẫn PGS. TS. Nguyễn Thanh Bình và TS. Nguyễn Quang Vũ đã tận tình giúp đỡ tác giả từ những bước đi đầu tiên xây dựng ý tưởng nghiên cứu, cũng như trong suốt quá trình nghiên cứu và hoàn thiện Luận án. Hai thầy đã luôn ủng hộ, động viên và hỗ trợ những điều kiện tốt nhất để tác giả hoàn thành luận án. Tác giả xin gửi lời cảm ơn chân thành tới các thầy, cô giáo và các bạn đồng nghiệp của Trường THPT chuyên Lê Quý Đôn - Đà Nẵng, Tổ Tin học đã tạo mọi điều kiện thuận lợi và giúp đỡ tác giả trong thời gian học tập và nghiên cứu. Cuối cùng, với tình yêu từ đáy lòng, tác giả xin gửi lời cảm ơn tới bố, mẹ, anh, chị, em cùng vợ và con của tác giả, những người thân yêu trong gia đình đã luôn ở bên cạnh tác giả, động viên tác giả về vật chất và tinh thần để tác giả vững tâm hoàn thành luận án của mình. NCS Đỗ Văn Nhỏ
iii MỤC LỤC LỜI CẢM ƠN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii MỤC LỤC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT . . . . . vi DANH MỤC CÁC HÌNH VẼ . . . . . . . . . . . . . . . . . . . . . vii DANH MỤC CÁC BẢNG BIỂU . . . . . . . . . . . . . . . . . . . vii MỞ ĐẦU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 CHƯƠNG 1. TỔNG QUAN KIỂM THỬ ĐỘT BIẾN 8 1.1 Giới thiệu kiểm thử phần mềm . . . . . . . . . . . . . . . . . . 8 1.2 Kiểm thử đột biến . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.1 Khái niệm kiểm thử đột biến . . . . . . . . . . . . . . . . . 10 1.2.2 Các giả thuyết cơ bản của kiểm thử đột biến . . . . . . . . 11 1.2.3 Quy trình kiểm thử đột biến . . . . . . . . . . . . . . . . . 13 1.2.4 Một số khái niệm liên quan . . . . . . . . . . . . . . . . . . 16 1.3 Hạn chế của kiểm thử đột biến . . . . . . . . . . . . . . . . . . 19 1.4 Các giải pháp giải quyết các hạn chế . . . . . . . . . . . . . . . . . 20 1.4.1 Giảm số lượng đột biến sinh ra . . . . . . . . . . . . . . . . 20 1.4.2 Tăng độ thực của lỗi . . . . . . . . . . . . . . . . . . . . . . 25 1.4.3 Giảm đột biến tương đương . . . . . . . . . . . . . . . . . . 25 1.4.4 Cải tiến quy trình kiểm thử đột biến . . . . . . . . . . . . . 29 1.5 Kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 CHƯƠNG 2. CẢI TIẾN CHẤT LƯỢNG KIỂM THỬ BẬC CAO DỰA TRÊN PHÂN LOẠI ĐỘT BIẾN BẬC MỘT 34 2.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2 Kiểm thử đột biến bậc cao . . . . . . . . . . . . . . . . . . . . . . . 35
iv 2.3 Các nghiên cứu về kiểm thử đột biến bậc cao . . . . . . . . . . . . 39 2.3.1 Các cải tiến đối với SOMT . . . . . . . . . . . . . . . . . . 39 2.3.2 Các cải tiến đối với HOMT . . . . . . . . . . . . . . . . . . 43 2.3.3 Vấn đề nghiên cứu . . . . . . . . . . . . . . . . . . . . . . . 48 2.4 Phương pháp đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.5 Triển khai thực nghiệm, đánh giá và phân tích kết quả . . . . . . 52 2.6 Kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 CHƯƠNG 3. ĐÁNH GIÁ TOÁN TỬ ĐỘT BIẾN VÀ HIỆU QUẢ CỦA CÁC CA KIỂM THỬ 57 3.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.2 Các nghiên cứu liên quan . . . . . . . . . . . . . . . . . . . . . . . . 58 3.2.1 Kiểm thử đột biến bậc cao . . . . . . . . . . . . . . . . . . . 58 3.2.2 Đánh giá hiệu quả toán tử đột biến và các ca kiểm thử . . 60 3.2.3 Vấn đề nghiên cứu . . . . . . . . . . . . . . . . . . . . . . . 60 3.3 Phương pháp đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.3.1 Các dự án kiểm thử . . . . . . . . . . . . . . . . . . . . . . 61 3.3.2 Công cụ hỗ trợ . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.3.3 Phương pháp đề xuất . . . . . . . . . . . . . . . . . . . . . 65 3.4 Kết quả thực nghiệm và phân tích . . . . . . . . . . . . . . . . . . 67 3.4.1 Câu trả lời cho câu hỏi nghiên cứu thứ nhất . . . . . . . . 67 3.4.2 Câu trả lời cho câu hỏi nghiên cứu thứ hai . . . . . . . . . 71 3.5 Kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 CHƯƠNG 4. DỰ BÁO CHẤT LƯỢNG CỦA KIỂM THỬ ĐỘT BIẾN BẬC CAO DỰA TRÊN HỌC MÁY 76 4.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.2 Các nghiên cứu liên quan . . . . . . . . . . . . . . . . . . . . . . . . 77 4.2.1 Kiểm thử đột biến áp dụng học máy . . . . . . . . . . . . . 77 4.2.2 Đề xuất vấn đề nghiên cứu . . . . . . . . . . . . . . . . . . 81
v 4.3 Giải pháp đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.3.1 Bộ dữ liệu thử . . . . . . . . . . . . . . . . . . . . . . . . . . 83 4.3.2 Công cụ hỗ trợ, thuật toán và phần mềm thực nghiệm . . 85 4.3.3 Đặc trưng đề xuất sử dụng . . . . . . . . . . . . . . . . . . 90 4.3.4 Quy trình thực nghiệm . . . . . . . . . . . . . . . . . . . . . 95 4.4 Kết quả thực nghiệm và đánh giá . . . . . . . . . . . . . . . . . . . 96 4.4.1 Huấn luyện và kiểm thử mô hình . . . . . . . . . . . . . . . 97 4.4.2 Thực hiện dự đoán chéo . . . . . . . . . . . . . . . . . . . . 100 4.5 Kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 KẾT LUẬN 104 CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ 106 TÀI LIỆU THAM KHẢO 108
vi DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ANN Artificial Neural Network (Mạng Neural Nhân Tạo) AST Abstract Syntax Tree (Cây cú pháp trừu tượng) AUC Area Under the Curve (Diện tích dưới đường cong) CEH Coupling Effect Hypothesis (Giải thuyết hiệu ứng liên kết) CPH Competent Programmer Hypothesis (Giải thuyết lập trình viên giỏi) FOM First Order Mutant (Đột biến bậc một) FOMT First Order Mutation Testing (Kiểm thử đột biến bậc một) HOM Higher Order Mutant (Đột biến bậc cao) HOMT Higher Order Mutation Testing (Kiểm thử đột biến bậc cao) MS Mutation Score (Tỷ lệ đột biến) MSI Mutation Score Indicator (Chỉ số tỷ lệ đột biến) L2F LastToFirst (Thuật toán LastToFirst) L2FS-Str LastToFirstSort Strategy NL Natural language (Ngôn ngữ tự nhiên) PCA Principal Component Analysis (Phân tích thành phần chính) PL Programming language (Ngôn ngữ lập trình) PUT Projects Under Test (Dự án thử nghiệm) RDomF Relaxed Dominator strategy (Chiến lược thống trị thoải mái) SDomF Strict Dominator strategy-SDomF (Chiến lược thống trị nghiêm ngặt) SOM Second Order Mutant (Đột biến bậc hai) SOMT Second Order Mutation Testing (Kiểm thử đột biến bậc hai) SS2OMs Strongly-Subsuming Second-Order Mutants () SVM Support Vector Machine (Máy vectơ hỗ trợ)
vii DANH MỤC CÁC HÌNH VẼ Hình 1.1 Quy trình kiểm thử đột biến truyền thống . . . . . . . . . . 14 Hình 1.2 Minh họa thuật toán LastToFirst . . . . . . . . . . . . . . . . 22 Hình 1.3 Minh họa thuật toán NeighPair . . . . . . . . . . . . . . . . . 24 Hình 1.4 Quy trình kiểm thử đột biến cải tiến . . . . . . . . . . . . . 31 Hình 2.1 Phân loại các đột biến bậc cao . . . . . . . . . . . . . . . . . 38 Hình 2.2 Qui trình tạo HOM với các chiến lược khác nhau . . . . . . 49 Hình 2.3 Phân bố tỷ lệ bị diệt của các đột biến bậc một . . . . . . . . 50 Hình 2.4 So sánh tỷ lệ đột biến của các phương án . . . . . . . . . . . 55 Hình 3.1 Quy trình đề xuất . . . . . . . . . . . . . . . . . . . . . . . . 67 Hình 3.2 Kết quả của AP_SOMT và EXP_SOMT . . . . . . . . . . . 70 Hình 3.3 MSI so sánh của AP_SOMT và EXP_SOMT . . . . . . . . 71 Hình 4.1 Đồ thị hàm Logistic với L = 1; k = 1; x0 = 0 . . . . . . . . . . 88
viii DANH MỤC CÁC BẢNG BIỂU Bảng 1.1 Ví dụ minh họa các đột biến . . . . . . . . . . . . . . . . . . 11 Bảng 1.2 Ví dụ đột biến tương đương . . . . . . . . . . . . . . . . . . . 17 Bảng 1.3 Các đề xuất cải tiến ba hạn chế của kiểm thử đột biến bậc một . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Bảng 2.1 Ví dụ minh họa về đột biến bậc hai . . . . . . . . . . . . . . 35 Bảng 2.2 Ví dụ về kết quả của đột biến bậc cao . . . . . . . . . . . . . 37 Bảng 2.3 So sánh kết quả của các nhóm tác giả sử dụng đột biến bậc hai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Bảng 2.4 Danh sách các dự án được kiểm thử (PUT) . . . . . . . . . . 52 Bảng 2.5 Số lượng đột biến được sinh ra . . . . . . . . . . . . . . . . . 54 Bảng 2.6 Tỷ lệ đột biến trung bình M SI (%) . . . . . . . . . . . . . . . 54 Bảng 3.1 Các dự án kiểm thử được bổ sung so với Bảng 2.4 . . . . . . 61 Bảng 3.2 Toán tử đột biến Judy . . . . . . . . . . . . . . . . . . . . . . 63 Bảng 3.3 Kết quả của FOMT . . . . . . . . . . . . . . . . . . . . . . . 68 Bảng 3.4 Danh sách “toán tử không thú vị” . . . . . . . . . . . . . . . 69 Bảng 3.5 Phân loại các ca kiểm thử . . . . . . . . . . . . . . . . . . . . 73 Bảng 3.6 Phân loại các ca kiểm thử . . . . . . . . . . . . . . . . . . . . 74 Bảng 4.1 Đánh giá các thuật toán phân lớp phổ biến qua 4 tiêu chí trong thực nghiệm của nghiên cứu . . . . . . . . . . . . . . . . . . 87 Bảng 4.3 Các dự án được sử dụng dự đoán chéo . . . . . . . . . . . . 90 Bảng 4.2 Các module được sử dụng trong thực nghiệm . . . . . . . . 91 Bảng 4.4 Danh sách các toán tử được MutPy cung cấp . . . . . . . . 94 Bảng 4.5 Số lượng SOM được sử dụng trong mô hình huấn luyện . . . 97
ix Bảng 4.6 Kết quả thực nghiệm huấn luyện mô hình và kiểm thử . . . 98 Bảng 4.7 Kết quả thực nghiệm dự đoán chéo sử dụng thuật toán LightGBM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Bảng 4.8 Kết quả thực nghiệm dự đoán chéo sử dụng thuật toán XGBoost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
1 MỞ ĐẦU Kiểm thử phần mềm là một hoạt động đóng vai trò rất quan trọng để bảo đảm chất lượng phần mềm và là hoạt động không thể thiếu trong các dự án sản xuất hoặc gia công phần mềm. Phần mềm ngày càng phát triển phức tạp thì yêu cầu chất lượng ngày càng cao, do đó vai trò của kiểm thử càng quan trọng. Hơn nữa, hầu hết các công ty phần mềm có uy tín đều đặt ra yêu cầu nghiêm ngặt là nếu một phần mềm không có tài liệu kiểm thử đi kèm thì sẽ không được chấp nhận. Tuy nhiên, hoạt động kiểm thử phần mềm lại thường gặp rất nhiều khó khăn. Thứ nhất, việc kiểm thử các hệ thống phức tạp đòi hỏi rất nhiều nguồn tài nguyên và chi phí cao. Chi phí cho hoạt động kiểm thử có thể chiếm 50% chi phí phát triển toàn dự án [1]. Thứ hai, 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ự mất mát 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. Thứ ba, kiểm thử chưa được chú trọng trong vấn đề đào tạo con người. Cuối cù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 hoàn toàn đúng đắn hay không chứa lỗi. Với mục đích phát hiện lỗi, kiểm thử phần mềm thường phải trải qua các bước: 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ú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ử? Khái niệm chất lượng bộ dữ liệu thử được sử dụng như là một phương tiện để đánh giá bộ dữ liệu thử như thế nào là “tốt” khi kiểm thử chương trình. Ở
2 đâ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à độ đo tỷ lệ bao phủ chương trình. Ví dụ, tiêu chuẩn bao phủ dòng 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ạo ra không đảm bảo chất lượng so với các tiêu chuẩn (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ì việc tạo lại bộ các ca kiểm thử là bắt buộc. Mục tiêu là tạo ra một tập các dữ liệu thử thực hiện đầy đủ tiêu chuẩn chất lượng. Kiểm thử đột biến [2] là một kỹ thuật được đề xuất nhằm đánh giá chất lượng bộ các ca kiểm thử T được xây dựng sẵn của một chương trình P . Ý tưởng của kỹ thuật này là tạo ra các phiên bản khác P ′ của chương trình P bằng cách thực hiện một thay đổi nhỏ trong chương trình, ví dụ thay đổi một toán tử bởi một toán tử khác. Sau đó, thực thi P và P ′ trên T để kiểm tra xem các ca kiểm thử này liệu có thể phát hiện ra sự sai khác giữa hai chương trình hay không bằng cách so sánh kết quả đầu ra của P và P ′ . Như vậy, kiểm thử đột biến là kỹ thuật kiểm thử dựa trên việc xây dựng các phiên bản lỗi của chương trình nhằm đánh giá chất lượng của các ca kiểm thử nhờ vào tỷ lệ phát hiện được sự sai khác của chương trình gốc và các phiên bản lỗi của nó. Tỷ lệ này được gọi là tỷ lệ đột biến [3, 4, 5]. Hay nói một cách khác, tỷ lệ đột biến có thể được sử dụng để đánh giá khả năng phát hiện lỗi của tập dữ liệu thử. 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 sự thay đổi nhỏ về 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. Để khẳng định 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ó bị phát hiện hay không. Dick Lipton [6] đề xuất ra 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 các DeMillo [4] và AT Acree [2].
3 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. Kỹ thuật kiểm thử đột biến truyền thống [7] (hay còn được gọi là kiểm thử đột biến bậc một) là một phương pháp có sự tự động hóa và hiệu quả cao trong việc đánh giá chất lượng của các bộ dữ liệu thử. Nó có thể được áp dụng cho kiểm thử phần mềm, với nhiều ngôn ngữ lập trình khác nhau và tại nhiều mức kiểm thử khác nhau [7]. Tuy nhiên, nó vẫn chưa được áp dụng rộng rãi vì vẫn còn tồn tại ba hạn chế chính [8]: (1) Số lượng các đột biến sinh ra quá nhiều; (2) Các đột biến có mô tả đúng các lỗi thực sự của phần mềm hay không; (3) Vấn đề về đột biến tương đương. Kiểm thử đột biến bậc cao là kỹ thuật có thể cải tiến được ba hạn chế vừa nêu [8, 9]. Mục tiêu của kiểm thử là phát hiện các lỗi ở giai đoạn sớm nhất có thể vì chi phí cho việc sửa lỗi sẽ tăng theo thời gian từ khi bắt đầu có lỗi cho đến lúc phát hiện nó. Vì vậy, thay vì chỉ quan tâm đến việc kiểm thử ở mức mã nguồn, thì gần đây các nhóm nghiên cứu đặc biệt quan tâm vấn đề dự báo chất lượng kiểm thử mà không cần thực thi các đột biến trên toàn bộ các ca kiểm thử đã được xây dựng. Dự báo chất lượng kiểm thử trở thành tiêu điểm của nhiều nỗ lực và nghiên cứu về sự kiểm chứng phần mềm hiện đại. Xuất phát từ tình hình thực tiễn trên, đề tài “Cải tiến chất lượng kiểm thử đột biến bậc cao” được chọn làm nội dung của luận án Tiến sỹ kỹ thuật nhằm đóng góp cho sự phát triển cũng như đưa vào ứng dụng thực tế trong ngành công nghiệp phần mềm của kiểm thử phần mềm nói chung và kiểm thử đột biến nói riêng - một hướng đi hứa hẹn mang lại hiệu quả cao trong vấn đề đảm bảo chất lượng phần mềm. 1. Mục tiêu, đối tượng và phạm vi nghiên cứu Mục tiêu của luận án là nghiên cứu các kỹ thuật kiểm thử đột biến thông qua tìm hiểu và đánh giá các kỹ thuật đột biến hiện có, cải tiến các kỹ thuật
4 kiểm thử đột biến bậc cao và nâng cao chất lượng kiểm thử đột biến bằng cách đánh giá chất lượng của các toán tử đột biến, dự báo chất lượng kiểm thử đột biến bậc cao. Trên cơ sở đó đề xuất áp dụng kiểm thử đột biến để phân loại, đánh giá chất lượng đột biến, các ca kiểm thử và dự báo chất lượng kiểm thử đột biến bậc cao. Đối tượng nghiên cứu của luận án là các kỹ thuật kiểm thử đột biến và cải tiến chất lượng kiểm thử đột biến bậc cao trong lĩnh vực phát triển phần mềm. Đối tượng nghiên cứu này cung cấp cơ sở lý thuyết và thực tiễn cho việc nghiên cứu, phát triển và cải tiến các kỹ thuật kiểm thử đột biến, từ đó nâng cao chất lượng và hiệu suất của quá trình kiểm thử phần mềm. Xác định mục tiêu và đối tượng nghiên cứu như trên, trong phạm vi nghiên cứu, luận án tập trung vào giải quyết các vấn đề sau: – Thứ nhất, luận án nghiên cứ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. – Thứ hai, tạo ra các đột biết bậc một (FOM - First Order Mutant) cho các dự án viết bằng ngôn ngữ Java và tính toán tỉ lệ diệt của các FOM; đề xuất quy trình tạo ra các đột biến bậc hai (SOM - Second Order Mutant) cấu thành từ các đột biến bậc một bằng cách sử dụng thuật toán LastToFirst; đề xuất cách phân nhóm, sắp xếp các đột biến bậc một trước khi kết hợp thành SOM, thực thi trên bộ dữ liệu thử để quan sát và phân tích kết quả. – Thứ ba, luận án tập trung vào việc nâng cao kỹ thuật kiểm thử đột biến, đặc biệt là kiểm thử đột biến bậc cao; đánh giá chất lượng của toán tử đột biến sử dụng để tạo ra các đột biến; xếp hạng các ca kiểm thử dựa trên khả năng phát hiện ra các lỗi thông qua phân tích đột biến của chúng; đề xuất một quy trình thử nghiệm cho phép lựa chọn các toán tử đột biến chất lượng cao khi tạo ra các đột biến bậc cao trong thử nghiệm đột biến cũng như ưu tiên các trường hợp thử nghiệm để phân bổ tài nguyên tốt hơn
5 trong hoạt động kiểm thử. – Thứ tư, nghiên cứu đề xuất giải pháp, mô hình để dự báo chất lượng kiểm thử đột biến bằng cách sử dụng các thuật toán học máy, mà không phải thực thi các đột biến nhằm giảm chi phí kiểm thử. 2. Nhiệm vụ nghiên cứu và kết quả đạt được Nhiệm vụ nghiên cứu tập trung vào các vấn đề chính sau đây: 1. Nghiên cứu tổng quan về kiểm thử phần mềm nói chung và kiểm thử đột biến nói riêng, cũng như các kỹ thuật kiểm thử đột biến. 2. Đề xuất quy trình tạo ra các đột biến bậc hai cấu thành từ các đột biến bậc một bằng cách sử dụng thuật toán LastToFirst; đề xuất cách phân nhóm, sắp xếp các đột biến bậc một trước khi kết hợp thành đột biến bậc hai, thực thi trên bộ dữ liệu thử để quan sát và phân tích kết quả. 3. Cải tiến kỹ thuật kiểm thử đột biến, đặc biệt là kiểm thử đột biến bậc cao; đánh giá chất lượng của toán tử đột biến sử dụng để tạo ra các đột biến. 4. Cải tiến, đánh giá các ca kiểm thử dựa trên khả năng phát hiện ra các lỗi thông qua phân tích đột biến của chúng; đề xuất một quy trình thử nghiệm cho phép lựa chọn các toán tử đột biến chất lượng cao khi tạo ra các đột biến bậc cao hơn trong thử nghiệm đột biến. 5. Cuối cùng, nghiên cứu, đề xuất, xây dựng, thử nghiệm mô hình và đánh giá kết quả của việc dự báo chất lượng kiểm thử đột biến. Nghiên cứu các đặc trưng được đề xuất trong kiểm thử đột biến; xây dựng quy trình huấn luyện mô hình và kiểm thử việc dự đoán cũng như dự đoán chéo.
6 3. Cấu trúc của luận án Trên cơ sở các nội dung nghiên cứu để đạt mục tiêu đề ra và đảm bảo tính logic và chỉnh thể của vấn đề nghiên cứu, ngoài phần mở đầu, phần kết luận và hướng phát triển, luận án đuợc cấu trúc gồm các chương như sau: Chương 1: Tổng quan kiểm thử đột biến. Chương này trình bày các khái niệm cơ bản về kiểm thử phần mềm nói chung và kiểm thử đột biến nói riêng; các kỹ thuật và ứng dụng của kiểm thử đột biến cũng như tình hình nghiên cứu về kỹ thuật kiểm thử này trong nước và trên thế giới. Chương 2: Cải tiến chất lượng kiểm thử đột biến bậc cao dựa trên phân loại đột biến bậc một. Chương này giới thiệu tổng quan về kiểm thử đột biến bậc cao. Trên cơ sở của các nghiên cứu kiểm thử đột biến bậc cao, đề xuất kỹ thuật cải tiến chất lượng kiểm thử đột biến bậc cao. Chương 3. Đánh giá toán tử đột biến và hiệu quả của các ca kiểm thử bằng kiểm thử đột biến. Để cải tiến chất lượng kiểm thử đột biến bậc cao, đã có nhiều kỹ thuật cải tiến được nghiên cứu, trong đó đánh giá chất lượng toán tử đột biến cũng như chất lượng ca kiểm thử được quan tâm và cho kết quả đáng ghi nhận. Chương 4. Dự báo chất lượng của kiểm thử đột biến bậc cao dựa trên học máy. Hạn chế của kiểm thử đột biến là chi phí cho việc sinh và thực thi đột biến cao. Một số kỹ thuật cải tiến chi phí thực thi được nghiên cứu, phân tích và từ đó đề xuất các giải pháp nhằm tự động hóa các hoạt động của kiểm thử đột biến cũng như cải thiện chi phí của các hoạt động này. Chương 4 trình bày giải pháp dự báo chất lượng của kiểm thử đột biến bậc cao dựa trên học máy mà không cần phải thực thi đột biến.
7 4. Đóng góp chính của Luận án – Trên cơ sở các cải tiến chất lượng kiểm thử đột biến bậc cao, luận án đề xuất kỹ thuật cải tiến đột biến bậc cao bằng cách đánh giá chất lượng đột biến bậc một, phân nhóm và sắp xếp các đột biến bậc một trước khi kết hợp thành đột biến bậc hai. – Nhằm cải tiến hiệu quả kiểm thử đột biến, luận án đã đánh giá chất lượng của các toán tử đột biến, các đột biến được tạo ra cũng như chất lượng các ca kiểm thử dựa trên khả năng diệt các đột biến để kết hợp thành đột biến bậc cao chất lượng hơn. – Để giảm các chi phí trong thực thi đột biến, luận án đã đề xuất giải pháp thay vì thực thi các đột biến để đánh giá chất lượng thì đưa ra dự báo chất lượng của kiểm thử đột biến bậc cao dựa trên học máy.
8 CHƯƠNG 1. TỔNG QUAN KIỂM THỬ ĐỘT BIẾN Chương này trình bày tổng quan về kiểm thử đột biến, các kỹ thuật nhằm cải tiến hiệu quả của kiểm thử đột biến và các ứng dụng trên cơ sở tổng hợp và phân tích các công trình nghiên cứu liên quan về kiểm thử đột biến. 1.1. Giới thiệu kiểm thử phần mềm Quy trình phát triển phần mềm thường trải qua nhiều giai đoạn khác nhau. Trong đó, kiểm thử phần mềm là hoạt động quan trọng nhằm phát hiện lỗi và đảm bảo chất lượng của phần mềm. Thất bại trong việc phát hiện lỗi có thể dẫn đến những tổn thất kinh tế hoặc thậm chí là thảm hoạ trong trường hợp hệ thống cần sự hoạt động an toàn tuyệt đối. Tuy nhiên, kiểm thử phần mềm là hoạt động rất tốn kém, nó chiếm khoảng từ 40%–50% tổng chi phí cho sự phát triển nói chung. Riêng các hệ thống đòi hỏi độ tin cậy, an toàn cao thì hoạt động này tiêu tốn chi phí nhiều hơn [10]. Với mục đích phát hiện lỗi, kiểm thử phần mềm thường phải trải qua các bước: 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ú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ử? Kiểm thử đóng một vai trò quan trọng trong quá trình phát triển phần mềm để đảm bảo chất lượng của nó. Kiểm thử đột biến nói chung và đột biến bậc cao nói riêng là những kỹ thuật tốt để đánh giá chất lượng của bộ dữ liệu thử, chẳng hạn, xác định xem bộ dữ liệu thử có bao phủ hết các lỗi không. Tuy nhiên, đột
9 biến bậc cao thường tốn chi phí rất lớn bởi số lượng đột biến khổng lồ được sinh ra. Kiểm thử đột biến [11] là một ví dụ của kỹ thuật kiểm thử dựa trên lỗi. Nói cách khác, phương pháp này bao gồm việc xây dựng dữ liệu kiểm thử nhằm mục đích phát hiện các lỗi cụ thể hoặc các lớp lỗi. Một số lượng lớn các thay đổi nhỏ (đột biến) được thực hiện trên chương trình, từng thay đổi một. Sau đó, dữ liệu kiểm thử cần được tìm kiếm để phân biệt các phiên bản đã bị đột biến với phiên bản gốc. Kiểm thử đột biến [6] đã được chứng minh là một kỹ thuật hiệu quả để đánh giá chất lượng của dữ liệu thử, tức là khả năng phát hiện lỗi [12], bằng cách chèn lỗi vào chương trình cần kiểm thử. Sau đó, kiểm tra xem dữ liệu thử có phát hiện được lỗi chèn vào không. Từ khi ra đời, kiểm thử đột biến đã được ứng dụng rộng rãi cho nhiều ngôn ngữ lập trình cũng như nhiều lĩnh vực phần mềm khác nhau. Đồng thời, nhiều nghiên cứu được đề xuất để cải tiến và nâng cao chất lượng của ứng dụng kiểm thử đột biến. Trong đó, kiểm thử đột biến bậc cao được đề xuất gần đây [13] cho phép giải quyết các hạn chế cơ bản của kiểm thử đột biến truyền thống, như số lượng đột biến lớn, sự phản ánh lỗi thực của đột biến và đột biến tương đương Một khảo sát gần đây về kiểm thử đột biến cung cấp minh chứng cho thấy rằng kỹ thuật này đang ngày càng hoàn thiện và ứng dụng thực tế [7]. Một lý do tại sao kiểm thử đột biến đã trở thành một kỹ thuật thử kiểm phổ biến vì nó là một quy trình đơn giản để áp dụng. Để đánh giá chất lượng của một bộ dữ liệu thử, các đột biến được tạo ra sẽ được thực thi đối với bộ dữ liệu thử đó. Nếu kết quả chạy một đột biến khác với kết quả chạy chương trình gốc đối với bất kỳ ca kiểm thử nào trong tập dữ liệu thử đầu vào, thì lỗi được tạo bởi đột biến đó sẽ được phát hiện. Kết quả của quy trình kiểm thử đột biến là tỷ lệ đột biến, cho biết chất lượng của bộ dữ liệu thử đầu vào. Tỷ lệ đột biến là tỷ lệ số lỗi được phát hiện trên tổng số lỗi được chèn vào [3]. Trong những năm gần đây, những nỗ lực nghiên cứu tập trung vào các kỹ