Luận văn Các kỹ thuật kiểm thử đột biến và ứng dụng kiểm thử chương trình C

ến đó để được phiên bản đúng của chương trình. Tuy nhiên, trước khi kiểm thử, chúng ta không biết được liệu PUT là đúng hay không. Thay vào đó, PUT phải được giả sử là đúng, trừ khi một dữ liệu thử có thể chứng minh khác. Trong tình huống đó, tỷ lệ các đột biến không tương đương bị diệt bởi bộ dữ liệu thử là thước đo cho chất lượng của bộ dữ liệu thử và thước đo của sự tin tưởng vào tính đúng đắn của PUT. Gần đây, nghiên cứu về kiểm thử đột biến đã tập trung phát triển các toán tử đột biến mới, đặc biệt cho các môi trường hướng đối tượng như C, C++, C_Sharp, Nghiên cứu này tập trung kiểm thử các chương trình đơn giản, hầu hết các toán tử đột biến truyền thống vẫn còn hiệu quả. 2.4. Quy trình kiểm thử đột biến Kiểm thử đột biến là một quy trình được lặp đi lặp lại để cải tiến dữ liệu thử đối với một chương trình và được chia thành các bước cơ bản [13] sau: Bước 1: Sản sinh đột biến (dùng công cụ sản sinh tự động hoặc sản sinh thủ công) từ chương trình gốc. Bước 2: Sản sinh các dữ liệu kiểm thử. Bước 3: Thực hiện từng dữ liệu kiểm thử với chương trình gốc. Bước 3.1: Nếu kết quả không đúng, phải chỉnh sửa l ạ i chương trình và kiểm thử lại. Bước 3.2: Nếu kết quả đúng, thực hiện bước tiếp theo. Bước 4: Thực hiện từng dữ liệu kiểm thử với từng đột biến còn sống. 33 Bước 4.1: Nếu kết quả ra của đột biến khác với chương trình gốc, chương trình đột biến được xem là không đúng và bị diệt. Hoàn thành kiểm thử. Bước 4.2: Nếu đột biến sống sót được (qua kiểm thử): phân tích các đột biến còn sống. Có hai khả năng xảy ra: - Hoặc các đột biến là đột biến tương đương: không thể bị diệt. - Hoặc có thể diệt các đột biến được nhưng các dữ liệu kiểm thử không đủ mạnh để diệt đột biến. Do đó phải tạo ra các dữ liệu kiểm thử khác và lặp lại bước 1. Từ các bước của thuật toán đã được tóm tắt thành sơ đồ [7] như hình sau: ( Lưu ý: Trong hình trên các bước biểu diễn trong hộp liền nét được thực hiện tự động. Còn các bước biểu diễn trong hộp nét đứt được thực hiện bằng tay) T F F T Tạo các đột biến Tất cả các đột biến bị diệt? Đầu vào chương trình P Đầu vào test cases, T Chạy T trên P P(T) đúng ? Sửa P Chạy test cases trên từng đột biến còn sống Phân tích và đánh dấu các đột biến tương đương Kết thúc Cập nhật T Các toán tử đột biến Hình 2.3 – Quy trình kiểm thử đột biến 34 2.5. Hạn chế của kiểm thử đột biến Mặc dù được xem là một kỹ thuật kiểm thử đơn vị mạnh, tuy nhiên kiểm thử đột biến gặp phải một số vấn đề khó khăn trong ngành công nghiệp phần mềm. Các vần đề này có thể được phân loại thành hai nhóm: chi phí tính toán – tốn rất nhiều thời gian và công sức để thực hiện kiểm thử đột biến, và tự động hóa – để giảm công sức của kiểm thử viên. Kiểm thử đột biến thì tốn kém vì số lượng lớn các chương trình đột biến cần được tạo ra và thực hiện. Do đó, các nhà nghiên cứu tiến hành nghiên cứu bằng thực nghiệm với kiểm thử đột biến thường chỉ sử dụng chương trình nhỏ để hạn chế số lượng đột biến được tạo ra. Trong khi đó, hạn chế này là chấp nhận được ở các trường (đại học, học viện, ), nó không dành cho công nghiệp thường mong muốn được kiểm thử các chương trình lớn hơn, phức tạp hơn. Vì tính phức tạp gia tăng, do thời gian thực hiện cho một chương trình và các phiên bản đột biến của nó, do đó làm tăng toàn bộ thời gian chạy cho kiểm thử đột biến. Các vấn đề trầm trọng hơn nữa là rất khó khăn trong việc tự động hoá toàn bộ quá trình kiểm thử đột biến. Mặc dù, một phần lớn quá trình có khả năng tự động được dễ dàng, các công việc như xác định các đột biến tương đương và kiểm tra tính đúng đắn của kết quả đầu ra thường được thực hiện một cách thủ công. Mặc dù, việc thực hiện những công việc này bằng thủ công cho phép chương trình được xem xét kỹ lưỡng hơn, nhưng dễ bị lỗi. Vì vậy, làm tăng thời gian kiểm thử ở một giai đoạn trong vòng đời phát triển phần mềm, khi thời gian kiểm thử thường là rất quan trọng. 35 2.6. Kết luận Kiểm thử đột biến được giới thiệu để cung cấp một phương tiện để đánh giá và cải tiến chất lượng các bộ dữ liệu thử. 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, hiệu ứng liên kết. Do đó, kiểm thử đột biến chỉ tập trung vào các lỗi đơn giản của chương trình (ví dụ: sự khác biệt một từ đơn hoặc thay thế tên biến sai). Tuy nhiên, chi phí để thực hiện kiểm thử đột biến khá cao vì một số lượng lớn các chương trình đột biến cần phải được thực hiện bởi ít nhất một dữ liệu thử và khó khăn để tự động hóa vì các dữ liệu thử mạnh cần phải được tạo ra, đột biến tương đương cần được loại bỏ, và kết quả đầu ra của PUT cần được kiểm thử tính đúng đắn. Vì vậy, chương 3 sẽ đề cập một số phương pháp cải tiến kỹ thuật kiểm thử đột biến để khắc phục các vần đề trên. 36 CHƯƠNG 3 - MỘT SỐ CẢI TIẾN KỸ THUẬT KIỂM THỬ ĐỘT BIẾN 3.1. Giảm chi phí tính toán Các hệ thống kiểm thử đột biến truyền thống tạo ra số lượng lớn các chương trình đột biến. Ví dụ, có 385 đột biến được tạo ra cho thủ tục tìm nghiệm theo phương pháp NiuTơn gồm 18 dòng lệnh. Phân tích cho thấy rằng số lượng các đột biến tạo ra xấp xỉ bằng tích của số các tham chiếu dữ liệu và số các đối tượng dữ liệu. Do đó, số lượng đột biến sẽ làm tăng tính phức tạp của chương trình. Điều này làm tăng chi phí thực thi do mỗi đột biến phải thực thi với ít nhất một trường hợp kiểm thử. Như vậy, chi phí là chấp nhận được cho nghiên cứu ở các trường (đại học, học viện, ) với các ràng buộc về thời gian có thể linh hoạt, nhưng trong công nghiệp sự lãng phí này là không thể. Mặt khác, các hệ thống truyền thống phải thông dịch các chương trình đột biến nên thực tế thời gian chạy sẽ lâu hơn. Điều này gây ra nhiều bất tiện, nó làm cho các hệ thống thực hiện chậm và rất khó để mô phỏng môi trường hoạt động. Để khắc phục những chi phí liên quan với đột biến, các nghiên cứu hầu hết đã tập trung vào một số phương pháp: làm ít hơn, làm nhanh hơn mà không làm giảm khả năng phát hiện lỗi. 3.1.1. Phương pháp làm ít hơn (A “do fewer” approach) Muốn giảm chi phí kiểm thử đột biến thì phải giảm số lượng các chương trình đột biến thực thi. Để làm được điều này, chúng ta sử dụng một trong số các phương pháp: Lấy mẫu đột biến (Mutant Sampling), đột biến ràng buộc (Constrained Mutation), và N - đột biến lựa chọn (N - Selective Mutation), mà không làm giảm các khả năng tìm kiếm lỗi. 37 3.1.1.1. Lấy mẫu đột biến (Mutant Sampling) Lấy mẫu đột biến là một phương pháp đơn giản lựa chọn ngẫu nhiên một tập con nhỏ các đột biến từ tập toàn bộ các đột biến. Ý tưởng này được đề xuất đầu tiên bởi Acree và Budd [19, 7]. Trong phương pháp lấy mẫu đột biến, đầu tiên tất cả các đột biến có thể có được tạo ra như trong kiểm thử đột biến truyền thống. Sau đó, x% của những đột biến này được lựa chọn ngẫu nhiên để phân tích đột biến và các đột biến còn lại được bỏ đi. Đã có nhiều nghiên cứu thực nghiệm về phương pháp này. Vấn đề chính là về việc chọn tỷ lệ lựa chọn ngẫu nhiên (x) còn được gọi là tỷ lệ lấy mẫu x%. Các nghiên cứu của Acree và Budd đề nghị rằng tỷ lệ lấy mẫu 10% có thể xác định trên 99% tất cả đột biến không tương đương trong khi cung cấp tiết kiệm chi phí đáng kể. Wong [23] tiếp tục nghiên cứu các lợi ích về chi phí của lấy mẫu đột biến bằng cách thay đổi tỷ lệ lấy mẫu từ 10% đến 40%. Ngay cả ở mức thấp nhất, các kết quả của Wong cho thấy lẫy mẫu đột biến là một chiến lược cắt giảm chi phí hiệu quả cung cấp các tập dữ liệu thử có khả năng xác định ít nhất 96,14% tất cả các đột biến nhưng chỉ phải kiểm tra 9,8% đột biến. Một điểm nổi bật hơn nữa trong [23] là đối với các tập dữ liệu thử chất lượng dựa vào lấy mẫu, một tỷ lệ lấy mẫu cao không có nghĩa là sẽ tạo ra tỷ lệ đột biến cao hơn tỷ lệ lấy mẫu thấp. Ban đầu, điều này có vẻ không hợp lý. Một trong những mong chờ đó là các dữ liệu thử được tạo ra từ tỷ lệ lấy mẫu lớn thì sẽ chất lượng hơn trong việc xác định đột biến còn lại so với từ tỷ lệ lấy mẫu nhỏ. Tuy nhiên, các kết quả của Wong cho thấy; đối với hàm TEXTFMT, tỷ lệ lấy mẫu 25% đạt được tỷ lệ đột biến 98,92% so với 99,01% cho tỷ lệ lấy mẫu 10%. Các kết quả này cho thấy rằng số lượng đột biến được kiểm tra không phải là chỉ báo rõ ràng về tỷ lệ đột biến (ngoại trừ kiểm tra tất cả các đột biến), nhưng thay vào đó, dấu hiệu là các dữ liệu thử có khả năng xác định đột biến nhiều hơn những dấu hiệu khác. Trong trường hợp này, việc 38 lựa chọn các đột biến cho kiểm thử có ảnh hưởng đến các dữ liệu thử được tạo ra và tỷ lệ đột biến không? Các đột biến có thể được phân loại dựa trên tập các dữ liệu thử diệt chúng. Đột biến mạnh là rất khó phát hiện, đòi hỏi dữ liệu thử đặc biệt để diệt nó. Ngược lại, đột biến yếu có thể dễ dàng phát hiện bởi bất kỳ dữ liệu thử nào. Do đó, cần có các tập dữ liệu thử khác nhau để diệt chúng. Các tập dữ liệu thử này nói chung là không được biết trước khi (và thường sau khi) kiểm thử. Tuy nhiên, tập dữ liệu thử đó phải được tạo ra để diệt đột biến. Xem xét tình huống, chọn W là đột biến yếu và chọn S là đột biến mạnh, W sẽ có tập dữ liệu thử để diệt nó - TW và S chưa có dữ liệu thử diệt được nó - TS. Có ba tình huống có thể xảy ra được minh họa ở hình 3.1: 1. TS  TW. Tập dữ liệu thử diệt đột biến mạnh hơn là tập con của tập dữ liệu thử diệt các đột biến yếu hơn– hình 3.3(a). 2. (TS  TW)  (TS  TW  ). TS không phải là tập con của TW nhưng hai tập giao nhau – hình3.3 (b). 3. TS TW = . Hai tập dữ liệu thử rời nhau – hình 3.3 (c). Nếu tình huống 1 xảy ra, thì chọn đột biến mạnh hơn trong quá trình lấy mẫu sẽ đảm bảo dữ liệu thử được tạo ra diệt đột biến yếu hơn- tức là dữ liệu thử được tạo ra trong cả TS và TW. Tuy nhiên, nếu đột biến yếu hơn được lựa chọn, thì cơ hội dữ liệu thử được tạo ra diệt được đột biến mạnh hơn sẽ bị giảm - tức là dữ liệu thử ở trong TW nhưng có thể hoặc không thể ở trong TS. TW Ts (a) (b) (c) Ts TW TW Ts Hình 3.1- Ba kịch bản có thể có cho quan hệ giữa các tập dữ liệu thử diệt đột biến yếu và mạnh 39 Nếu tình huống 3 xảy ra, thì việc lựa chọn đột biến trong lấy mẫu sẽ chỉ tạo ra dữ liệu thử có khả năng diệt đột biến đặc biệt. Tình huống 2 là sự kết hợp của hai loại. Lựa chọn đột biến mạnh hơn sẽ tạo ra dữ liệu thử có thể hoặc không thể diệt được đột biến yếu hơn và ngược lại. Nói chung, kích thước của TW có thể sẽ lớn hơn kích thước của TS, dữ liệu thử từ TW giao nhau với TS có thể sẽ nhỏ hơn so với dữ liệu thử từ TS giao nhau với TW. Ví dụ, cho một dữ liệu thử x là giao với hai tập |TW| = 20 và |TS| = 5. Nếu dữ liệu thử được tạo ra để diệt đột biến yếu hơn (nghĩa là dữ liệu thử thuộc TW) thì tỷ lệ của x là 1/20. Nếu dữ liệu thử được tạo ra để diệt đột biến mạnh hơn (nghĩa là dữ liệu thử thuộc TS) thì tỷ lệ của x là 1/5. Ba tình huống trên cho thấy rằng, đột biến được chọn trong quá trình lấy mẫu sẽ ảnh hưởng đến các dữ liệu thử được tạo ra. Hơn nữa, chúng cho thấy rằng lựa chọn các đột biến mạnh hơn cải thiện cơ hội diệt các đột biến yếu hơn và vì vậy kích thước của lấy mẫu đột biến là không quan trọng, nhưng đó vẫn là sự lựa chọn đột biến. Lấy mẫu từ đột biến mạnh hơn với tỷ lệ thấp hơn có thể tạo ra tỷ lệ đột biến cao hơn lấy mẫu từ đột biến yếu hơn với tỷ lệ cao hơn. 3.1.1.2. Đột biến ràng buộc (Constrained Mutation) Giảm số lượng các đột biến cũng có thể đạt được bằng cách giảm số lượng các toán tử đột biến được áp dụng. Đây là ý tưởng cơ bản làm nền tảng cho đột biến ràng buộc được đề xuất bởi Mathur [4], bằng cách lựa chọn một tập con các toán tử đột biến tạo ra một tập con tất cả các đột biến có thể có mà không mất tính hiệu quả của kiểm thử đột biến. Các kiểm tra dựa trên kinh nghiệm thu được các kết quả khá thuyết phục khi sử dụng đột biến ràng buộc. Nhìn chung, các kết quả của Wong cho thấy rằng các tỷ lệ đột biến trung bình từ các tập dữ liệu thử chất lượng dựa trên ràng buộc bằng cách sử dụng chỉ hai toán tử ABS và ROR đạt trên 95% trong số bốn chương trình kiểm tra và giảm số lượng đột biến từ 14.39% đến 40 19.94% của tổng số đột biến [22]. Trong khi đó, tiết kiệm chi phí không lớn bằng tỷ lệ lấy mẫu 10% (thực hiện từ 9,8% cho đến 10,98% tổng số đột biến), tỷ lệ đột biến trung bình là xấp xỉ bằng 97,56% với tỷ lệ lấy mẫu 10% và 97,18% với đột biến ràng buộc ABS / ROR. Các nghiên cứu của Mathur và đồng nghiệp cũng cho ra kết quả tương tự, kết quả này thu được 7 trong số 10 thí nghiệm, đột biến ràng buộc ABS / ROR đạt hiệu quả ít nhất bằng tỷ lệ lấy mẫu 10% trong việc phát hiện có lỗi. Hơn nữa, còn lại 3 thí nghiệm đều được thực hiện trên cùng một chương trình không được sử dụng trong 7 thí nghiệm khác. 3.1.1.3. N - đột biến lựa chọn (N - Selective Mutation) Offutt và đồng nghiệp [9, 10] mở rộng nghiên cứu đột biến ràng buộc của Mathur bằng cách sử dụng tất cả các toán tử đột biến trừ đi hai toán tử tạo ra hầu hết các đột biến (được gọi là phương pháp 2 - đột biến lựa chọn). Giả thuyết phương pháp N – đột biến lựa chọn, trong đó N là số toán tử đột biến tạo ra nhiều đột biến nhất được loại bỏ. Ban đầu, 28 chương trình đã được kiểm tra để xác định tỷ lệ đột biến được tạo ra bởi mỗi toán tử đột biến, như thể hiện trong hình 3.2. Dựa trên đó, họ đề xuất loại bỏ hai toán tử SVR và ASR cho 2 - đột biến lựa chọn, cùng với SCR và CSR cho 4 - đột biến lựa chọn, kết hợp với ACR và SRC cho 6 - đột biến lựa chọn. Đối với mỗi phương pháp lựa chọn, bộ tạo dữ liệu thử tự động Godzilla được dùng để tạo ra dữ liệu thử chất lượng dựa trên đột biến lựa chọn. Sau đó, các tập dữ liệu thử này được thực hiện với tất cả các đột biến để xác định hiệu quả của chúng đối với tất cả các đột biến - tức là tỷ lệ đột biến của chúng. Các kết quả mang lại nhiều hứa hẹn. Phương pháp 2 - đột biến lựa chọn cho kết quả tỷ lệ đột biến 99,99% và tiết kiệm 23,98% số lượng đột biến không phải kiểm tra. Đối với 4 - đột biến lựa chọn thu được những số liệu tương ứng này là 99,84% và 41,36%, và 6 - đột biến lựa chọn là 99,71% và 60,56%. 41 Hình 3.2 - Phân bố đột biến bằng toán tử đột biến cho Mothra Như vậy, các tỷ lệ đột biến cao thu được từ các tập dữ liệu thử chất lượng dựa trên lựa chọn cho thấy rằng các dữ liệu thử được thiết kế để diệt đột biến từ các toán tử đột biến tạo ra ít đột biến cũng có khả năng diệt các đột biến từ các toán tử đột biến tạo ra nhiều đột biến. Offutt và đồng nghiệp tiếp tục nghiên cứu để loại bỏ thêm các đột biến nhằm tiết kiệm thêm chi phí mà không ảnh hưởng nhiều đến hiệu quả của các tập dữ liệu thử được tạo ra [10]. 22 toán tử đột biến chuẩn được sử dụng trong Mothra được chia thành ba nhóm:  Các toán tử thay thế toán hạng - thay thế từng toán hạng của chương trình bằng toán hạng hợp lý khác.  Các toán tử thay đổi biểu thức của chương trình - thay thế các toán tử của chương trình và thêm các toán tử mới.  Các toán tử thay đổi câu lệnh - thay đổi các câu lệnh hoàn toàn. Offutt và đồng nghiệp thực hiện ba thí nghiệm để tạo ra dữ liệu thử chất lượng, loại trừ một nhóm các toán tử đột biến trong từng thí nghiệm. Khi so sánh với tất cả các đột biến, kết quả thu được 5 toán tử biểu thức (ABS, AOR, LCR, ROR, UOI) là hữu ích nhất. Các thí nghiệm đã chứng minh rằng các tập dữ liệu thử chất lượng tạo ra từ 5 toán tử này đạt tỷ lệ đột biến trung bình là 99,51% và tiết kiệm 77,56% số lượng các đột biến phải kiểm tra. Các kết quả này tương tự như các tỷ lệ đột biến trung bình thu được bằng cách sử Toán tử đột biến T ỷ lệ đ ột b iế n tiế t k iệ m đ ượ c 42 dụng lấy mẫu đột biến với tỷ lệ lấy mẫu 25% (tiết kiệm 75%): từ 98,27% đến 99,01%. Tuy nhiên, không giống như lấy mẫu đột biến, phương pháp này đã tập trung vào lớp đột biến phải kiểm tra, cung cấp độ tin cậy vào các toán tử đột biến giúp tạo ra dữ liệu thử mạnh hơn (tức là chúng có thể diệt nhiều đột biến hơn). 3.1.2. Phương pháp làm nhanh hơn (A “do smarter” approach) Các kỹ thuật làm nhanh hơn nhằm mục đích tạo ra và chạy các chương trình đột biến nhanh hơn các hệ thống chuẩn. Hầu hết các hệ thống đột biến truyền thống thông dịch các đột biến của chúng, nó thì thuận tiện nhưng chậm hơn so với thực hiện biên dịch chương trình. Kỹ thuật biên dịch riêng rẽ: biên dịch từng đột biến trước khi thực hiện. Điều này sẽ làm tăng tốc độ chạy từ 15-20 lần so với hệ thống truyền thống. Tuy nhiên, nếu thời gian biên dịch lớn hơn nhiều so với thời gian chạy thì tắc nghẽn biên dịch có thể xảy ra, kết quả là trong khi xây dựng các chương trình được biên dịch, sự thực thi vẫn đang diễn ra [7]. Để tránh tắc nghẽn, Krauser đã sử dụng một cơ chế đột biến tích hợp trình biên dịch, sử dụng một trình biên dịch mới để biên dịch đồng thời PUT và phát triển các đoạn chương trình (code patches) biểu diễn cho các đột biến. Trước khi thực thi, các đoạn chương trình cần thiết được áp dụng để PUT được biên dịch cung cấp một chương trình đột biến thực hiện với tốc độ biên dịch. Do đó, PUT chỉ cần được biên dịch một lần. Các kết quả của Krauser chứng minh rằng phương pháp tích hợp trình biên dịch làm tăng tốc độ đáng kể (tính bằng tỷ lệ giữa các kỹ thuật thời gian thực hiện trung bình trên mỗi đột biến để tạo ra và thực hiện tất cả các đột biến đối với một trường hợp kiểm thử) so với biên dịch riêng rẽ khi thời gian thực hiện PUT thấp. Ví dụ, sử dụng phương pháp tích hợp trình biên dịch cho chương trình TRANSPOSE 43 nhanh hơn 7,58 lần so với sử dụng kỹ thuật biên dịch riêng rẽ và làm cho chương trình TRITYP nhanh hơn 27,33 lần. Nói chung, thời gian thực hiện chương trình ảnh hưởng đến sự gia tăng tốc độ của phương pháp tích hợp trình biên dịch. Với thời gian thực hiện thấp (tức là thời gian thực hiện < thời gian biên dịch), phương pháp biên dịch riêng rẽ thực hiện các đột biến nhanh hơn. Sự chậm trễ lúc biên dịch xảy ra trong toàn bộ thời gian thực hiện tất cả các đột biến tăng và vì vậy làm tăng thời gian thực hiện đột biến trung bình. Tuy nhiên, với số lần thực hiện cao hơn (tức là thời gian thực hiện > thời gian biên dịch), thời gian biên dịch sẽ trở nên ít quan trọng. Các đột biến có thể dễ dàng được biên dịch trước khi thực hiện có nghĩa là thời gian trung bình để thực hiện từng đột biến bằng phương pháp biên dịch riêng rẽ chỉ phụ thuộc vào thời gian thực hiện - giống như kỹ thuật tích hợp trình biên dịch, có nghĩa là tỷ lệ gia tăng tốc độ các phương pháp là 1/1. 3.1.2.1. Phương pháp tạo lược đồ đột biến Phương pháp tạo lược đồ đột biến (MSG) [18] là một trong những phương pháp giúp khắc phục vấn đề tắc nghẽn. Tất cả các đột biến của chương trình được mã hóa vào một mức mã nguồn duy nhất gọi là chương trình siêu đột biến (metamutant). Các điểm đột biến trong PUT (chẳng hạn như một phép toán số học) được thay thế bằng các lời gọi hàm có cú pháp hợp lệ được gọi là siêu thủ tục (metaprocedure). Mỗi metaprocedure mã hóa toán tử đột biến và thay đổi đầu ra của nó tùy thuộc vào các đối số. Ví dụ, tùy thuộc vào các đối số của nó, metaprocedure số học sẽ thực hiện cộng, trừ, nhân, chia, hoặc module. Sau đó, các đột biến được biểu diễn dưới dạng một tập các đối số metaprocedure được áp dụng lúc thực thi metamutant. Bằng cách chỉ thay đổi một đối số metaprocedure duy nhất từ tập các đối số metaprocedure (của PUT) ban đầu, đột biến thích hợp có thể được thực hiện. 44 Điều này có nghĩa là các đột biến không được biên dịch hoặc thông dịch riêng rẽ và được thực hiện trong môi trường đích với tốc độ chương trình biên dịch. Một metamutant đơn giản của đoạn chương trình ở hình 3.3 được mô tả ở hình 3.4. Metamutant này được tạo ra bằng cách chỉ sử dụng toán tử đột biến toán tử quan hệ thay thế mọi trường hợp của toán tử quan hệ bằng một metaprocedure toán tử quan hệ thích hợp, trong trường hợp này ROR:op() được biểu diễn ở dòng 2- hình 3.4. ROR:op() có ký hiệu: ROR:op(int lhs; int rhs; int mutantNumber). Metaprocedure được định nghĩa dòng 1- hình 3.4. Trong quá trình thực hiện metamutant này, các đối số thích hợp được cung cấp cho metaprocedure ROR cho phép bất kỳ toán tử quan hệ được áp dụng hai giá trị. Mỗi đột biến được biểu diễn bằng một dãy các giá trị biểu diễn toán tử cho mỗi metaprocedure. MutantNumber là chỉ số metaprocedure trong dãy đột biến. Ví dụ: mutantNumber trong đoạn mã 3.2 là 0, biểu diễn giá trị ở chỉ // phương thức PUT đột biến bằng toán tử ROR 1 import MTAIS.Operators.ROR; ... public boolean sumIsPositive (int n, int m){ z = 0; sum = n + m; 2 return (ROR.op(sum, z, 0)); } Hình 3.4- Phiên bản đột biến của PUT gốc hình 3.3 // phương thức PUT gốc public boolean sumIsPositive (int n, int m){ z = 0; sum = n + m; return (sum > z); } Hình 3.3- Ví dụ phương thức PUT gốc 45 số 0 trong dãy đột biến thiết lập toán tử được sử dụng trong ROR:op(). Tất cả các toán tử quan hệ được đánh số, ví dụ: là 3 và v.v... Giá trị chỉ số mutantNumber xác định toán tử quan hệ để áp dụng, trong ví dụ này, câu lệnh sum > z sẽ được thực hiện bởi một dãy đột biến với chỉ số 0 chứa 3 (số cho toán tử quan hệ >). Để thực hiện sum == z, giá trị ở chỉ số 0 sẽ được sửa đổi bằng 2 (số cho toán tử quan hệ ==). Bằng cách sử dụng phương pháp này, tất cả các đột biến đều xuất hiện trong metamutant, từng đột biến được chọn lúc thực thi bằng cách áp dụng các giá trị thích hợp từ dãy đột biến vào các metaprocedure. Untch và các đồng nghiệp [18] cho biết rằng việc thực hiện thủ tục tìm nghiệm theo phương pháp Niutơn bằng cách sử dụng sản sinh lược đồ đột biến thì nhanh hơn 4,1 lần sử dụng phương pháp thông dịch [18]. Họ lập luận rằng đây “là một tín hiệu tốt cho thấy MSG có thể tăng đáng kể khả năng thực thi của kiểm thử đột biến ". 3.1.2.2. Đột biến yếu (Weak Mutation) Kỹ thuật này được đề xuất bởi Howden [21]. Để tăng tỷ lệ đột biến, kiểm thử đột biến phải diệt các đột biến được thể hiện ở kết quả đầu ra khác với PUT khi nhận cùng đầu vào. Do đó, kiểm thử đột biến mạnh (strong mutation) tiếp tục thực hiện đột biến cho đến khi hoàn thành và so sánh các kết quả đầu ra tiếp theo hoặc các trạng thái chương trình. Nhưng điều này là lãng phí. Hãy so sánh một đột biến với PUT. Từng câu lệnh chương trình là giống nhau ngoại trừ câu lệnh đơn có chứa đột biến, dẫn đến các kết quả đầu ra có thể khác nhau, code “lỗi” này sẽ gây ra một số trạng thái khác ngay sau khi nó được thực hiện. Nếu không tìm thấy trạng thái khác thì đột biến sẽ tiếp tục theo đường chương trình giống nhau và tạo ra đầu ra giống như PUT. Tuy nhiên, nếu tìm thấy trạng thái khác từ điểm này (vị trí tạo ra đột biến) thì điều này cho biết các kết quả đầu ra của chương trình có thể khác nhau và lưu việc 46 thực hiện phần còn lại của đột biến. Đây là tiền đề về sau của kiểm thử đột biến yếu. Đột biến yếu khác với đột biến mạnh khi so sánh các trạng thái của đột biến và PUT. Cả hai phương pháp có thể được phân loại khi so sánh ở các thái cực đối lập: đột biến yếu so sánh ngay sau câu lệnh đột biến, còn đột biến mạnh so sánh khi kết thúc chương trình. Những biến đổi này của đột biến yếu đã được nghiên cứu bằng thực nghiệm. Cụ thể, sử dụng phiên bản đã sửa đổi của Mothra, được gọi là Leonardo (quan sát đầu ra mong đợi không phải sau khi trả về nhưng vẫn trong quá trình hoạt động). Offutt và Lee [9] thực hiện các nghiên cứu về đột biến vững chắc bằng cách sử dụng bốn điểm so sánh khác nhau: i. Sau khi thực hiện biểu thức trong cùng nhất bao quanh đột biến đầu tiên; ii. Sau khi thực hiện câu lệnh đột biến đầu tiên - đột biến yếu truyền thống; iii. Sau khi thực hiện khối cơ bản đầu tiên (các lệnh tuần tự với các điểm vào và ra duy nhất) bao quanh đột biến; iv. Sau N lần thực hiện đột biến chứa khối cơ bản trong đó N là lớn hơn 1 và nhỏ hơn số lần khối cơ bản được thực hiện trong PUT - một đột biến bị diệt khi xuất hiện trạng thái không chính xác đầu tiên. Offutt và Lee đã thực hiện hai nghiên cứu so sánh bốn phiên bản trên với đột biến mạnh. Nghiên cứu đầu tiên là tạo ra các tập dữ liệu thử có tỷ lệ đột biến vững chắc (firm-mutation scoring) 100% cho từng phương pháp vững chắc và thực hiện chúng bằng cách sử dụng đột biến mạnh để tạo ra toàn bộ tỷ lệ đột biến. Nghiên cứu thứ hai là tạo ra tập dữ liệu thử với các tỷ lệ đột biến ít hơn 90% và thực hiện bằng bốn phương pháp vững chắc để xác định các tỷ lệ đột biến vững chắc của chúng. Các kết quả khá thú vị. Bằng trực quan, 47 phương pháp (iv) sẽ kiểm tra các trạng thái chương trình gần với kết thúc chương trình tự nhiên hơn và do đó gần với hệ thống đột biến mạnh hơn, cho thấy rằng phương pháp này cung cấp mạnh hơn tức là thu được dữ liệu thử chất lượng hơn. Đây không phải là trường hợp duy nhất. Nghiên cứu đầu tiên cũng chỉ ra rằng điểm hiệu quả nhất để thực hiện các so sánh trạng thái là sau khi thực hiện câu lệnh bị đột b