Tài liệu Xây dựng công cụ sinh đột biến cho chương trình lustre

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.