Tóm tắt 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:33

Thêm vào BST

Báo xấu

48
lượt xem 2
download

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

Tóm tắt 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" được nghiên cứu với mục tiêu: 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; 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; Đề xuất giải pháp, mô hình để dự báo chất lượng kiểm thử đột biến sử dụng các thuật toán học máy Logistic Regression, Random Forest Classifier, XGBoost và LightGBM để thực hiện huấn luyện, dự báo tỷ lệ đột biến MS.

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt 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 Chuyên ngành: Khoa học máy tính Mã số: 9 48 01 01 TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT Đà Nẵng – 2023
Công trình được hoàn thành tại TRƯỜNG ĐẠI HỌC BÁCH KHOA, ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học: 1. PGS. TS Nguyễn Thanh Bình 2. TS Nguyễn Quang Vũ Phản biện 1:............................................................................................ Phản biện 2:............................................................................................ Phản biện 3:............................................................................................ Luận án sẽ được bảo vệ trước Hội đồng chấm luận án cấp Trường, Trường Đại học Bách khoa Vào hồi . . . giờ . . . . ngày . . . tháng . . . năm 2023. Có thể tìm hiểu luận án tại: - Thư viện quốc gia Việt Nam. - Trung tâm Thông tin - Học liệu & Truyền thông- Đại học Đà Nẵng. Đà Nẵng - 2023
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 mang 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. 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ử đột biến [1] 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 thay đổi một toán tử trong chương trình P bằng 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 ′ . 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 [2] đề 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 [3] và AT Acree [1]. 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 [4] (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 [4]. 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 [5]: (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 [5, 6]. 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
2 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, cải tiến các kỹ thuật kiểm thử đột biến bậc cao, 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. Như vậy, đối tượng nghiên cứu của luận án là 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. Xác định mục tiêu và đối tượng nghiên cứu như trên, 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 hơn 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 trong hoạt động thử nghiệm. – 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 sử dụng các thuật toán học máy Logistic Regression, Random Forest Classifier, XGBoost và LightGBM để thực hiện huấn luyện, dự báo tỷ lệ đột biến M S. 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.
3 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. 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 và 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 khá 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 sinh và thực thi đột biến. 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.
4 – 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ự trên học máy. Luận án đã đề xuất quy trình mô hình huấn luyện và kiểm thử theo dự đoán, quy trình thực hiện kiểm tra chéo. CHƯƠNG 1. TỔNG QUAN KIỂM THỬ ĐỘT BIẾN 1.1. Giới thiệu kiểm thử phần mềm 1.2. Kiểm thử đột biến 1.2.1. Khái niệm kiểm thử đột biến Kiểm thử đột biến được giới thiệu lần đầu trong một công bố của Richard Lipton [2], cũng như trong các công bố của Hamlet [7], DeMillo cùng các đồng sự [3] và Allen T Acree cùng các đồng sự [1]. Kiểm thử đột biến là một kỹ thuật kiểm thử hộp trắng được sử dụng để đánh giá chất lượng của các bộ kiểm thử dựa trên một tham số được gọi là tỷ lệ đột biến. Nói một cách khác, tỷ lệ đột biến được sử dụng để tính toán khả năng phát hiện lỗi của một bộ dữ liệu thử. 1.2.2. Các giả thuyết cơ bản của kiểm thử đột biến Kiểm thử đột biến được xây dựng dựa trên hai giả thuyết cơ bản: giả thuyết “lập trình viên giỏi” [3, 8] và giả thuyết “hiệu ứng liên kết” [3]. 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 [9, 10, 11, 12, 13, 14, 15, 16]. 1.2.3. Quy trình kiểm thử đột biến 1.2.4. Một số khái niệm liên quan 1.2.4.1. Toán tử đột biến Toán tử đột biến (Mutation operator) [17] hay còn được gọi là luật đột biến (mutation rule) là một luật được áp dụng vào chương trình gốc để tạo ra các phiên bản đột biến. Nó có thể là việc thay thế một toán tử này bằng một toán tử khác, thay đổi toán hạng của biểu thức, xoá toàn bộ các biểu thức, thay đổi câu lệnh. . . hoặc có thể được tạo ra bằng cách thay đổi nhỏ về cú pháp của chương trình theo hướng mà lập trình viên thường phạm phải. Các toán tử đột biến được xây dựng dựa trên ngôn ngữ dùng để cài đặt chương trình được kiểm thử.
5 1.2.4.2. Đột biến tương đương Đột biến tương đương (Equivalent mutants) [3, 7] là một đột biến tương đương về mặt ngữ nghĩa so với chương trình gốc được sinh ra nhưng không có dữ liệu thử nào có thể diệt được. 1.2.4.3. Tỷ lệ đột biến Tỷ lệ đột biến (Mutation Score), được ký hiệu M S, của chương trình P và dữ liệu thử T là tỷ lệ các đột biến không tương đương (so với chương trình gốc) bị diệt bởi dữ liệu thử T , được mô tả bởi công thức sau [18, 3, 7, 19]: MK MS = (1.1) MT − ME Tỷ lệ đột biến tính cả đột biến tương đương (MSI - Mutation Score Indicator) [20, 21, 22, 23] MK M SI = (1.2) MT trong đó, MK : số đột biến bị diệt, MT : tổng số các đột biến được tạo ra, ME : số đột biến tương đương. Tỷ lệ đột biến (M S hoặc M SI) cho phép đo chất lượng của tập dữ liệu thử. Tỷ lệ đột biến tiến gần hơn tới 1.0, hầu hết các đột biến bị diệt bởi tập dữ liệu thử, tức là tập dữ liệu thử có khả năng phát hiện hầu hết các lỗi được chèn. Mục tiêu của kiểm thử viên là xây dựng bộ dữ liệu thử sao cho có thể diệt tất cả các đột biến không tương đương hay đạt tỷ lệ đột biến cao (tức tỷ lệ đột biến tiến gần tới 1.0 hay gần bằng 100%). 1.3. Hạn chế của kiểm thử đột biến Kỹ thuật kiểm thử đột biến truyền thống [4] (hay còn được gọi là kiểm thử đột biến bậc một) được đề cập ở trên như 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, như kiểm thử đơn vị, kiểm thử tích hợp, kiểm thử hệ thống, kiểm thử chấp nhận,. . . [4] 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 [5] dưới đây: – Số lượng các đột biến được sinh ra quá nhiều. – Độ chính xác của các đột biến được tạo ra để mô tả các lỗi thực sự của phần mềm. – Vấn đề về các đột biến tương đương. 1.4. Các giải pháp giải quyết các hạn chế Đã có nhiều giải pháp giải quyết được các hạn chế của kiểm thử đột biến, sau đây là tổng hợp một số giải pháp đó.
6 1.4.1. Giảm số lượng đột biến sinh ra 1.4.2. Tăng độ thực của lỗi 1.4.3. Giảm đột biến tương đương 1.4.4. Cải tiến quy trình kiểm thử đột biến Bảng 1.1: Các đề xuất cải tiến ba hạn chế của kiểm thử đột biến bậc một Giảm số lượng đột biến Tăng độ thực của lỗi Giảm đột biến tương đương - Đột biến bậc cao [24, 25, 26, 27, - Đột biến bậc cao [24, - Đột biến bậc cao [24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] 25, 26, 27, 28, 29, 30, 28, 30, 33, 34, 38] - Đột biến mẫu [8, 39, 40, 41, 42, 31, 32, 33, 34, 35, 36, - Tối ưu hóa biên dịch [46, 47] 43, 44, 45] 37] - Đột biến lựa chọn [51, 58] - Đột biến lựa chọn [48, 49, 41, - Sử dụng mô hình kiểm tra 50, 51, 52, 53, 54, 55, 56, 44, 57] Lesar [64] - Gom cụm đột biến [59, 60, 61, - Ràng buộc toán học [73, 74] 62, 63] - Đồng tiến hóa [75] - Đột biến yếu [65, 66, 67, 68, 69, - Phân tích phụ thuộc chương 70, 71, 72] trình [76] - Điều kiện tương đương [77] - Phân cấp lỗi [78] - Phân cấp ngữ nghĩa ngoại lệ [79] Trong các giải pháp giải quyết các hạn chế của kiểm thử đột biến (xem Bảng 1.1) thì kỹ thuật kiểm thử đột biến bậc cao không chỉ là kỹ thuật duy nhất có thể cải tiến được hạn chế thứ hai mà còn là kỹ thuật duy nhất đồng thời có thể cải tiến cả ba hạn chế của kỹ thuật đột biến truyền thống [80, 81, 82]. Chi tiết về đột biến bậc cao sẽ được trình bày trong Chương 2. 1.5. Kết luận chương Nội dung Chương 1 trình bày các vấn đề cơ bản về kiểm thử đột biến, các kỹ thuật để cải tiến hiệu quả của kiểm thử đột biến cũng như các ứng dụng của nó. Các nghiên cứu liên quan đến cải tiến hiệu quả của kiểm thử đột biến được tổng hợp, phân tích và đánh giá.
7 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 Trong Chương 2 này, chúng tôi tập trung áp dụng kỹ thuật đột biến bậc cao để giảm thiểu chi phí của kiểm thử bằng cách giảm số lượng đột biến và tăng hiệu quả trong việc kiểm thử. 2.1. Giới thiệu 2.2. Kiểm thử đột biến bậc cao Theo Harman cùng các cộng sự [34, 24], các đột biến được phân thành hai loại: Đột biến bậc một (FOM - First Order Mutants) và Đột biến bậc cao (HOM - Higher Order Mutants). FOM được tạo bằng cách áp dụng toán tử đột biến một lần duy nhất và được sử dụng trong kiểm thử đột biến bậc một, trong khi đó HOM sử dụng nhiều hơn một đột biến và được sử dụng trong kiểm thử đột biến bậc cao. 2.3. Các nghiên cứu về kiểm thử đột biến bậc cao 2.3.1. Các cải tiến đối với SOMT Các nghiên cứu cải tiến với SOMT được tổng hợp ở Bảng 2.1. Kết quả đạt được của các nghiên cứu này với số lượng đột biến giảm đến 50% và số đột biến tương đương giảm đến 70% tuy nhiên số lượng đột biến vẫn còn cao và cần được tiếp tục cải tiến. Bảng 2.1: So sánh kết quả của các nhóm tác giả sử dụng đột biến bậc hai Tác giả Số đột biến giảm (%) Số đột biến tương đương giảm (%) Polo et al [31] 56.06 74 Papadaki và Malevris [30] 53.23 73 Kintis et al [27] Không đề cập 78 Omar và Ghost [29] Không đề cập 40 Madeyki et al [28] 53.39 57 2.3.2. Các cải tiến đối với HOMT Các nghiên cứu cải tiến đối với HOMT [34, 33, 33, 34, 32, 38, 35, 36, 25, 26, 6, 80, 81, 82, 83, 84, 85, 86, 87, 88] đã được thảo luận. Kết quả nghiên cứu của các nhóm tác giả được phân thành hai nhóm chính: – Nhóm thứ nhất: số lượng đột biến tương đương giảm nhưng số đột biến sinh ra tăng theo cấp số mũ của bậc đột biến [17], [18];
8 – Nhóm thứ hai: số lượng đột biến sinh ra đã giảm đi rất nhiều so với số lượng đột biến bậc một, tuy nhiên số lượng đột biến khó bị diệt (có thể bao gồm cả đột biến tương đương) vẫn còn khá cao, chiếm khoảng 35% tổng số lượng đột biến được sinh ra. 2.3.3. Vấn đề nghiên cứu Nhiều nghiên cứu cải tiến hiệu quả của kiểm thử đột biến bậc cao đã được đề xuất như đã thảo luận trong các mục 2.3.1 và 2.3.2. Tuy nhiên, cho đến nay chưa có nghiên cứu nào sử dụng phương pháp tạo ra các đột biến bậc cao trên cơ sở đánh giá, phân loại các đột biến bậc một dựa vào tỷ lệ đột biến M SI. Do đó, trong chương này, chúng tôi đưa ra các vấn đề nghiên cứu sau: 1. Có thể cải tiến hiệu quả của HOM bằng cách sắp xếp các FOM dựa trên tỷ lệ đột biến M SI trước khi kết hợp chúng thành HOM? 2. Chất lượng của các HOM sẽ ra sao khi tạo các HOM từ các nhóm FOM khác nhau dựa trên tỷ lệ đột biến M SI? 2.4. Phương pháp đề xuất Hình 2.1: Các chiến lược tạo HOM
9 2.5. Triển khai thực nghiệm, đánh giá và phân tích kết quả Bảng 2.2: Số lượng đột biến được sinh ra Project FOM- L2F- L2FS- L2FA- L2FB- L2FC- Str Str Str Str Str Str Antomology 77 38 33 21 11 8 Commons-cli-1.3.1-src 2,633 1,320 680 255 157 408 Commons-csv 1,677 839 306 140 96 287 Commons-chain-1.2-src 2,075 1,047 1,047 389 92 216 Commons-dbutils 1,245 589 260 166 52 131 Commons-digester3-3.2-src 4,013 1,343 1,676 346 86 380 Commons-email 1,075 541 441 96 33 97 Commons-lang3-3.4-src 26,975 13,428 12,063 4,706 665 2,637 Commons-text 7,433 3,719 3,411 948 155 636 Commons-validator 4,268 2,068 1,726 666 312 490 Java-util 3,768 1,872 1,660 447 82 192 Jettison 2,577 1,294 1,069 395 77 304 TỔNG: 57,816 28,098 24,372 8,575 1,818 5,786 Bảng 2.3: Tỷ lệ đột biến trung bình M SI(%) Strategy FOM- L2F- L2FS- L2FA- L2FB- L2FC- Str Str Str Str Str Str MSI 53.42 70.90 73.92 99.33 97.27 48.58 2.6. Kết luận chương Kết quả của nghiên cứu thực nghiệm với 12 dự án nguồn mở trong thực tế cho thấy hiệu quả của HOMT sẽ tăng đáng kể khi sắp xếp các FOM (dựa trên giá trị của M SI) trước khi thực hiện HOMT bằng cách kết hợp các FOM để xây dựng HOM, đặc biệt là kết hợp các FOM có giá trị MSI cao (trong chương này, giá trị đề xuất của MSI bằng hoặc cao hơn 40%). 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 BẬC CAO Trong chương 3 này, chúng tôi tập trung đánh giá chất lượng của các toán tử đột biến cũng như các đột biến được tạo ra và chất lượng của các ca kiểm thử dựa trên khả năng
10 diệt các đột biến. Điều này có thể giúp các nhà phát triển phân bổ các nguồn lực một cách thích hợp trong giai đoạn kiểm thử. 3.1. Giới thiệu 3.2. Các nghiên cứu liên quan Phần này tập trung vào một số nghiên cứu chính liên quan đến kiểm tra đột biến bậc cao và đề xuất vấn đề nghiên cứu. 3.2.1. Kiểm thử đột biến bậc cao Các nghiên cứu được thảo luận trong mục 2.3.2 đã đề xuất các cách khác nhau để cải tiến chất lượng kiểm thử đột biến bậc cao. Các chiến lược trên đều cho kết quả khả quan, với số đột biến giảm trung bình 54%, và số đột biến tương đương giảm vào khoảng 40% đến 78%. 3.2.2. Đánh giá hiệu quả toán tử đột biến và các ca kiểm thử bằng phương pháp kiểm thử đột biến 3.2.3. Vấn đề nghiên cứu Trong phần trình bày các chương trước, chúng ta đã thấy rằng nhiều nghiên cứu gần đây quan tâm đến HOM. Một số nghiên cứu đề xuất các chiến lược khác nhau để tạo ra HOM từ FOM do đó số lượng HOM được giảm xuống và HOM vẫn giữ được chất lượng trong điều kiện không phát hiện ra các nhược điểm. Nhưng không có công trình nào dựa trên chất lượng của từng toán tử đột biến được sử dụng để tạo ra đột biến. Đây là mục tiêu đầu tiên của chúng tôi trong luận án này. Hầu hết các nghiên cứu này đánh giá chất lượng của tập hợp các ca kiểm thử bằng cách sử dụng tỷ lệ đột biến làm tiêu chuẩn kiểm thử đầy đủ. Tuy nhiên, không có công trình nào đánh giá riêng khả năng khắc phục lỗi của mỗi ca kiểm thử. Đó là mục tiêu thứ hai của chương này. Để xem xét hai mục tiêu nêu trên, trong chương này sẽ đặt ra các câu hỏi nghiên cứu sau: 1. Có thể đánh giá chất lượng của toán tử tạo đột biến thông qua tỉ lệ đột biến không? Các toán tử đột biến chất lượng có tạo ra HOM chất lượng không? 2. Có thể đánh giá chất lượng của từng ca kiểm thử thông qua khả năng diệt đột biến của nó không? Có thể ưu tiên thứ tự chạy các ca kiểm thử không? 3.3. Phương pháp đề xuất Trong phần này, trước tiên chúng tôi trình bày bộ 12 dự án được sử dụng để thử nghiệm. Sau đó, chúng tôi giới thiệu công cụ Judy [84] để thiết lập thử nghiệm. Phần cuối cùng được dành cho quy trình đề xuất để tiến hành đánh giá các toán tử đột biến cũng như các trường hợp thử nghiệm.
11 3.3.1. Các dự án kiểm thử 3.3.2. Công cụ hỗ trợ 3.3.3. Phương pháp đề xuất Để tiến hành thực nghiệm này, chúng tôi đã thiết kế quy trình (Hình 3.1) với hai thuật toán khác nhau (LastToFirst [20] và NeighPair [8,19]) để trả lời câu hỏi các câu hỏi nghiên cứu đã đề cập trong phần 3.2.3. Quy trình gồm 16 bước nhằm đạt cả 2 mục tiêu: đánh giá chất lượng toán tử đột biến và đánh giá chất lượng từng ca kiểm thử. Các bước này được mô tả như Hình 3.1: Hình 3.1: Quy trình đề xuất
12 3.4. Kết quả thực nghiệm và phân tích 3.4.1. Đánh giá chất lượng của toán tử tạo đột biến Câu hỏi đầu tiên được đưa ra là: Có thể đánh giá chất lượng của toán tử tạo đột biến thông qua tỉ lệ đột biến không? Các toán tử đột biến chất lượng có tạo ra HOM chất lượng không? Bảng 3.1: Kết quả của FOMT Dự án Số lượng của Số lượng diệt MSI (%) FOM của FOM Commons-email 1,075 310 28.84 Commons-validator 4,013 1,085 27.04 Java-util 1,300 534 41.08 Commons-csv 2,577 1,156 44.86 Commons-chain-1.2-src 3,768 1,772 47.03 Jettison 1,677 794 47.35 Commons-net 8,595 4,690 54.57 Commons-digester3-3.2-src 4,268 2,348 55.01 Antomology 111 73 65.77 Commons-exec 1,094 781 71.39 Commons-cli-1.3.1-src 2,633 1,905 72.35 Jra 77 70 90.91 Σ = 31, 188 Σ = 15, 518 µ = 53.85 Bảng 3.2: Danh sách “toán tử không thú vị” Toán tử Số lượng của Số lượng diệt MSI (%) FOM của FOM CSR 5 0 0.00 ISI 263 0 0.00 OMR 558 2 0.36 EMM 141 2 1.42 OMD 413 7 1.69 IOD 229 5 2.18 Σ = 1, 608 Σ = 16 µ = 0.94 Trong Hình 3.2 và Hình 3.3, chúng tôi mô tả dữ liệu thử nghiệm liên quan đến số lượng SOM được tạo ra và số lượng SOM bị diệt (Hình 3.2) cũng như MSI (Hình 3.3). Với kết quả trình bày ở trên, chúng tôi một lần nữa khẳng định rằng có thể sử dụng tỉ lệ đột biến như một tham số để đánh giá chất lượng của các toán tử đột biến. Chất lượng của toán tử có ảnh hưởng trực tiếp đến chất lượng của các đột biến về việc giảm số lượng các đột biến được tạo ra (SOM) và giảm số lượng các đột biến còn sống (có khả năng tương đương). Điều này là do MSI của EXP_SOMT cao hơn MSI của AP_MSI (cho cả hai thuật toán).
13 Hình 3.2: Kết quả của AP_SOMT và EXP_SOMT Hình 3.3: MSI so sánh của AP_SOMT và EXP_SOMT 3.4.2. Đánh giá chất lượng của từng ca kiểm thử Nội dung câu hỏi nghiên cứu thứ hai bao gồm: Có thể đánh giá chất lượng của từng ca kiểm thử thông qua khả năng diệt đột biến của nó không? Có thể ưu tiên thứ tự chạy các ca kiểm thử không? Trong Bảng 3.3, nội dung trình bày dữ liệu liên quan đến 4 tham số: – Số lượng các ca kiểm thử: Số lượng ca kiểm thử tích hợp trong các dự án. – Số lượng các ca kiểm thử hiệu quả: Số lượng các ca kiểm thử có thể diệt tất cả các SOM đã tạo (100% ) – Số lượng các ca kiểm thử không hiệu quả: Số lượng các ca kiểm thử không thể diệt bất kỳ SOM đã tạo nào (0%).
14 – Số lượng các ca kiểm thử khác: Số lượng các ca kiểm thử có thể diệt ít nhất một SOM đã tạo nhưng không thể diệt tất cả các SOM đã tạo. Kết quả thực nghiệm ở Bảng 3.3 đưa ra số lượng ca kiểm thử có thể diệt tất cả các đột biến liên quan cho mỗi lớp trong dự án, không thể diệt bất kỳ đột biến nào hoặc có thể diệt ít nhất một đột biến cho mỗi dự án. Điều này thể hiện chất lượng khác nhau của mỗi ca kiểm thử trong toàn bộ ca kiểm thử. Các ca kiểm thử có thể diệt tất cả các đột biến được tạo ra có hiệu quả cao. Nó có thể phát hiện tất cả các lỗi được đưa vào trong chương trình gốc. Các ca kiểm thử có thể được sử dụng để thay thế tất cả các ca kiểm thử còn lại được thiết kế cho từng lớp, do đó chi phí thử nghiệm có thể giảm đáng kể mà không làm giảm chất lượng thử nghiệm. Ngược lại, các ca kiểm thử không thể diệt được bất kỳ đột biến nào được coi là không sử dụng hoặc không hiệu quả thì nên bị loại bỏ ra khỏi ca kiểm thử. Trong Bảng 3.3, số lượng các ca kiểm thử này đối với một số dự án là đáng kể. Trong trường hợp đó, chi phí thử nghiệm có thể được giảm xuống trong khi vẫn giữ được khả năng phát hiện lỗi của ca kiểm thử. Bảng 3.3: Phân loại các ca kiểm thử Dự án Số lượng các Số lượng các Số lượng các Số lượng các ca kiểm thử ca kiểm thử ca kiểm thử ca kiểm thử hiệu quả không hiệu khác quả Antomology 22 6 1 15 Commons-chain-1.2-src 73 19 10 44 Commons-cli-1.3.1-src 435 9 7 419 Commons-csv 80 12 12 56 Commons-digester 121 41 8 72 Commons-email 32 7 6 19 Commons-exec 60 11 2 47 Commons-net 234 34 17 183 Commons-validator 404 54 11 339 Java-util 174 18 1 155 Jettison 105 19 2 84 Jra 2 2 0 0
15 Bảng 3.4: Phân loại các ca kiểm thử Dự án Số lượng Không 0% 1..19 20..79 80..99 100 các ca liên % % % % kiểm thử quan Antomology 22 0 1 0 15 0 6 Commons-chain-1.2-src 73 16 10 4 23 1 19 Commons-cli-1.3.1-src 435 407 7 2 9 1 9 Commons-csv 80 36 12 2 18 0 12 Commons-digester 121 36 8 6 21 9 41 Commons-email 32 0 6 0 14 5 7 Commons-exec 60 27 2 0 16 4 11 Commons-net 234 183 17 0 0 0 34 Commons-validator 404 212 11 1 99 27 54 Java-util 174 102 1 6 34 13 18 Jettison 105 49 2 4 18 13 19 Jra 2 0 0 0 0 0 2 Trong Bảng 3.4, chúng tôi xếp hạng các ca kiểm thử theo tỷ lệ phần trăm của số lượng đột biến bị diệt trên tổng số các đột biến có liên quan (tức là các đột biến được tạo ra cho mỗi lớp trong dự án) trong phạm vi khác nhau: số ca kiểm thử diệt 0% đột biến, từ 1% đến dưới 20% đột biến, từ 20% đến dưới 80% đột biến, từ 80% đến dưới 100% đột biến và tất cả các đột biến. Đáng chú ý là cột thứ ba “Không liên quan” đề cập đến số lượng ca kiểm thử không liên quan đến bất kỳ lớp nào đang được kiểm thử trong dự án. Điều đó có nghĩa là các ca kiểm thử này có thể bị loại trừ khỏi quá trình kiểm thử đột biến. Trong hoạt động kiểm thử, kiểm thử viên có thể kiểm thử từng lớp trong dự án và quyết định lựa chọn các ca kiểm thử được xếp hạng tùy theo nguồn lực sẵn có và yêu cầu chất lượng của chúng. 3.5. Kết chương Chương này tập trung vào hai vấn đề chính: Đánh giá chất lượng của toán tử đột biến được sử dụng để tạo HOM và ưu tiên các ca kiểm thử trong hoạt động kiểm thử bằng cách dựa trên khả năng phát hiện lỗi của chúng, hay khả năng diệt các đột biến bậc cao. Một quy trình đã được đề xuất để giải quyết cả hai vấn đề. Trong quá trình này, hai thuật toán LastToFirst và NeighPair được sử dụng để tạo HOM. Một mặt, nó cho phép loại bỏ các toán tử đột biến không được sử dụng để tạo ra các đột biến bậc cao. Mặt khác, các ca kiểm thử được xếp hạng theo thứ tự khả năng diệt HOM. Cách tiếp cận này có thể giúp kiểm thử viên giảm chi phí nhưng vẫn giữ được chất lượng kiểm thử cũng như phân phối tài nguyên một cách hợp lý. Trong chương 4, chúng tôi sẽ áp dụng kỹ thuật học máy để dự đoán HOM sẽ bị diệt bằng cách phân tích các tính năng dựa trên cú pháp của chúng mà không cần thực thi chúng.
16 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 Trong chương 4 này, luận án nghiên cứu áp dụng kỹ thuật học máy để dự đoán kiểm thử đột biến bậc cao sẽ bị diệt bằng cách phân tích các đặc trưng dựa trên cú pháp của đột biến mà không cần phải thực thi chương trình gốc và tất cả các đột biến của nó trên toàn bộ các ca kiểm thử đã được xây dựng để giảm chi phí tính toán của kiểm thử đột biến. 4.1. Giới thiệu Quy trình kiểm thử đột biến nói chung bao gồm các bước cơ bản sau đây: (1) Thực thi chương trình gốc trên bộ các ca kiểm thử được xây dựng dành riêng cho chương trình gốc đó. (2) Tiến hành sinh ra các đột biến, là các biến thể của chương trình gốc. (3) Lần lượt thực thi chương trình gốc và tất cả các đột biến của nó trên toàn bộ các ca kiểm thử đã được xây dựng. (4) Tính toán tỷ lệ đột biến và trên cơ sở đó đánh giá chất lượng của bộ dữ liệu thử. Trong chương này, luận án đặt ra vấn đề nghiên cứu là làm thế nào để không cần thực thi bước thứ (3) mà vẫn tính toán (dự báo) được tỷ lệ đột biến với độ chính xác cao nhằm giảm thời gian và chi phí tính toán nhưng vẫn đảm bảo được hiệu quả của kiểm thử đột biến như mong đợi. 4.2. Các nghiên cứu liên quan 4.2.1. Kiểm thử đột biến áp dụng học máy 4.2.2. Đề xuất vấn đề nghiên cứu Trên cơ sở phân tích các nghiên cứu liên quan ở trên, chúng tôi đặt ra vấn đề nghiên cứu: Chúng ta có thể đạt được kết quả và hiệu quả của kiểm thử đột biến bậc cao mà không cần thực thi đột biến hay không? Cụ thể hơn, rằng có thể đề xuất một giải pháp để nhằm dự báo trước một cách có cơ sở và chính xác tỷ lệ số lượng đột biến bậc cao bị diệt mà không cần thực hiện việc thực thi kiểm thử đột biến nói trên hay không? Trong chương này, chúng tôi sẽ tập trung đề xuất giải pháp để trả lời cho vấn đề nghiên cứu trên và tiến hành thực nghiệm trên các phần mềm viết bằng ngôn ngữ Python, một ngôn ngữ thông dụng và có miền ứng dụng rộng nhưng tốc độ thực thi chậm. Việc trả lời các câu hỏi này sẽ giúp chúng ta đánh giá được chất lượng bộ dữ liệu thử cho các phần mềm viết bằng Python, và tất nhiên có thể áp dụng cho các ngôn ngữ lập trình khác, mà không cần thực thi đột biến nhằm rút ngắn thời gian, chi phí kiểm thử đột biến mà không làm giảm hiệu quả của kỹ thuật này.
17 4.3. Giải pháp đề xuất Nhằm giải quyết vấn đề nêu trong phần 4.2, giải pháp mà chúng tôi đưa ra gồm hai giai đoạn. Giai đoạn thực nghiệm bắt đầu bằng việc tạo bộ dữ liệu thử là tập hợp các đột biến bậc hai. Công cụ MutPy và hai thuật toán hồi quy Logistic, Random Forest Classifier được chọn để tiến hành thực nghiệm nghiên cứu trong giai đoạn này, với 8 đặc trưng. Giai đoạn hai là việc cải tiến hiệu quả của đề xuất của giai đoạn một bằng cách sử dụng bốn thuật toán Hồi quy logistic, Random Forest Classifier, XGBoost và XGBoost với 13 đặc trưng. Giai đoạn này được thực hiện với quy trình hai bước: (a) Huấn luyện và kiểm thử mô hình, (b) Dự báo chéo. Kết quả được phân tích chi tiết và được đánh giá là khả quan, có thể áp dụng thực tế. 4.3.1. Bộ dữ liệu thử 4.3.2. Công cụ hỗ trợ, thuật toán và phần mềm thực nghiệm 4.3.2.1. Công cụ hỗ trợ Các công cụ hỗ trợ được sử dụng trong luận án: 1 – MutPy 2 – Scikit-learn 4.3.2.2. Các thuật toán học máy Trong thực nghiệm này, chúng tôi đã sử dụng các thuật toán sau để huấn luyện mô hình và dự đoán những đột biến nào sẽ bị diệt. Có thể nói rằng đây là những thuật toán hiệu quả và phổ biến trong xây dựng mô hình học máy. – Hồi quy logistic (Logistic Regression) – Random Forest Classifier – XGBoost – LightGBM 4.3.2.3. Các phần mềm thực nghiệm Đối với việc xây dựng dữ liệu huấn luyện cho mô hình, kiểm thử và dự đoán, 140 module được chọn trong dự án CPython phiên bản 3.73 Trong khi đó, 5 dự án được dùng để dự đoán chéo là các dự án thực tế được tải từ https://github.com. 1 https://pypi.org/project/MutPy/ 2 https://scikit-learn.org/stable/ 3 https://github.com/python/cpython/tree/3.7
18 4.3.3. Đặc trưng đề xuất sử dụng Dựa trên nghiên cứu [89] của Zhang và các cộng sự, trong 15 đặc trưng mà nhóm tác giả sử dụng, chúng tôi nhận thấy rằng có 8 đặc trưng khả dụng và hiệu quả trong việc tạo ra các đột biến bậc hai cũng như hiệu quả trong việc áp dụng các mô hình dự báo mà chúng tôi nghiên cứu đề xuất. Việc quyết định chọn đặc trưng nào cũng được nhắc đến trong kết quả thực nghiệm của Alireza Aghamohammandi và cộng sự [90]. Do đó, trong nghiên cứu này, chúng tôi sử dụng 8 đặc trưng đó (được trình bày dưới đây), và có cải tiến, cho việc thực nghiệm giải pháp của chúng tôi. Đồng thời, chúng tôi cũng sử dụng một công cụ có tên “Coverage.py” 4 , được sử dụng để đo lượng độ bao phủ mã nguồn của các chương trình Python. Với công cụ này, chúng ta có thể điều khiển các chương trình và xác định mã nguồn nào đã được thực thi hoặc chưa. Cụ thể hơn, chúng ta sử dụng công cụ “Coverage.py” để chạy các chương trình được kiểm thử trên từng ca kiểm thử để kiểm tra những dòng lệnh nào của chương trình được kiểm thử được bao phủ bởi từng ca kiểm thử cụ thể. Từ thực nghiệm này, chúng tôi đề xuất sử dụng 5 đặc tính bổ sung. 4.3.4. Quy trình thực nghiệm Quy trình thực nghiệm được thực hiện qua hai giai đoạn: huấn luyện và kiểm thử mô hình; dự đoán chéo. Bước 1. Huấn luyện và kiểm thử mô hình. Trong bước này chúng tôi sử dụng 140 dự án đã đề cập với các đặc trưng từ số 1 tới số 8. Bước 1.1. Tạo các FOM cho chương trình được kiểm thử. Bước 1.2. Tạo các SOM cho chương trình được kiểm thử bằng cách kết hợp hai trong số các FOM bất kỳ được sinh ra từ bước 1.1. Bước 1.3. Thực thi chương trình gốc và các SOM trên các ca kiểm thử đã xây dựng sẵn để kiểm thử chương trình gốc. Sau đó, tính toán tỷ lệ đột biến (được gọi là MS1). Bước 1.4. Sử dụng các thuật toán để huấn luyện mô hình (với 80% trong số các SOM được sinh trong bước 1.2 mà đã được gắn nhãn bị diệt hay còn sống) Bước 1.5. Sau khi hoàn thành huấn luyện, thực hiện dự đoán những đột biến sẽ bị diệt trong 20% số đột biến còn lại được sinh trong bước 1.2. Sau đó tính toán tỷ lệ đột biến (được là M S2) dựa trên số lượng SOM dự đoán bị diệt và tổng số SOM được sử dụng ở bước này. Bước 1.6. So sánh kết quả M S1 với M S2 và so khớp những đột biến thực sự bị diệt trong bước 1.3 với các đột biến dự đoán sẽ bị diệt trong bước 1.5. Bước 2. Dự đoán chéo. Trong bước này chúng tôi sử dụng 5 dự án đã đề cập với toàn bộ 13 đặc trưng. Bước 2.1. Tạo các FOM cho 05 chương trình được kiểm thử. 4 https://coverage.readthedocs.io/en/7.2.2