Tài liệu Phương pháp tự động sửa lỗi cho các chương trình java

ii TÓM TẮT Các hệ thống phần mềm luôn không ngừng phát triển theo lẽ tự nhiên để đáp ứng nhu cầu thay đổi liên tục từ khách hàng và thị trường. Tuy nhiên, những thay đổi này có thể gây ra các lỗi khiến cho những chức năng đã có của chương trình không hoạt động đúng. Những lỗi như thế này được gọi là lỗi hồi quy. Sửa lỗi tự động (Automated Program Repair - APR) gần đây đã cho thấy được tiềm năng lớn trong việc tự động sửa các lỗi của phần mềm. Mặc dù với sự phát triển mạnh mẽ của APR, chỉ có một số kỹ thuật tập trung xử lý các lỗi hồi quy. Tuy nhiên, các kỹ thuật chưa thực sự khai thác đầy đủ thông tin có sẵn trong lịch sử phát triển của các phần mềm (ví dụ: bản cập nhật gây ra lỗi, v.v.) để sửa lỗi hồi quy. Hơn nữa, những kỹ thuật này không công bố công cụ cài đặt cho cộng đồng hoặc công cụ rất hạn chế và khó có thể sử dụng để sửa lỗi trong thực tế. Luận văn này nhằm mục đích đề xuất phương pháp sửa lỗi hồi quy cho các chương trình Java bằng cách khai thác và mở rộng những phát hiện gần đây về lỗi hồi quy, ví dụ: mối tương quan giữa các bản cập nhật tạo ra lỗi và sửa lỗi. Luận văn cài đặt lại và cải tiến phương pháp sửa lỗi hồi quy tự động cho các chương trình C (Relifix). Từ đó, xây dựng một hệ thống có tên là LyFix, cho phép người dùng sửa lỗi hồi quy Java tự động bằng cách tận dụng các nguyên liệu sửa lỗi và các mẫu sửa lỗi cụ thể học được từ lịch sử phát triển phần mềm. Tám mẫu sửa lỗi hồi quy, thuật toán sửa lỗi đã được cài đặt lại dựa vào ý tưởng của Relifix. Ngoài ra, luận văn cài đặt thêm ba mẫu sửa lỗi hồi quy mới cho Java. Luận văn cũng thực hiện thực nghiệm để so sánh khả năng sửa lỗi của LyFix đối với jRelifix (bản cài đặt Relifix cho Java) và các công cụ sửa lỗi tự động tốt nhất hiện nay (jGenProg, jMutRepair, TBar) trên tập dữ liệu 51 lỗi hồi quy thực tế của các hệ thống phần mềm Java mã nguồn mở. Kết quả cho thấy LyFix có thể sinh ra bản vá thành công cho 56.8% lỗi có trong tập dữ liệu và tỉ lệ số bản vá chính xác là 79.3% trong khi các công cụ khác sửa lỗi tốt nhất (TBar) với kết quả sinh được bản vá 33.3% lỗi và tỉ lệ bản vá đúng là 41.1%. Từ khóa: tự động sửa lỗi chương trình, lỗi hồi quy, lịch sử phát triển phần mềm iii LỜI CẢM ƠN Đầu tiên và quan trọng nhất, tôi xin gửi lời cảm ơn trân trọng và sâu sắc tới PGS. TS. Phạm Ngọc Hùng - người Thầy giáo đã trực tiếp hướng dẫn tận tình và đóng góp những ý kiến quý báu trong quá trình tôi học tập, nghiên cứu và cả kinh nghiệm cuộc sống từ những năm tháng tôi còn là sinh viên tại trường Đại học Công nghệ cho đến nay. Thầy đã không ngần ngại cho phép và hỗ trợ tôi tự lựa chọn đề tài để thực hiện luận văn này. Tôi xin được gửi lời cảm ơn chân thành tới TS. Bách Lê, TS. Lê Quang Lộc, và PGS. TS. Corina Pasareanu đã hướng dẫn và hỗ trợ tôi rất nhiệt tình trong quá trình thực hiện luận văn này. Các anh và cô luôn động viên tôi và đưa ra những câu trả lời và gợi ý ngay lập tức mỗi khi tôi gặp khó khăn. Các anh và cô cũng chia sẻ rất nhiều kinh nghiệm quý báu trong nghiên cứu và cuộc sống và tôi đã học được nhiều điều từ các anh. Xin được cảm ơn ban tổ chức chương trình Google Summer of Code 2020 và Java PathFinder Team đã cho phép tài trợ kinh phí để tôi thực hiện đề tài trong luận văn này. Công trình này cũng được tài trợ một phần từ đề tài KHCN cấp ĐHQGHN, Mã số đề tài: QG.19.24. Cuối cùng, tôi xin được cảm ơn những lời động viên từ gia đình, người thân, bạn bè để giúp tôi luôn vững bước trong con đường tương lai. iv Mục lục 1 2 3 Giới thiệu 1 1.1 Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Đóng góp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Bố cục luận văn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Kiến thức nền tảng 4 2.1 Kiểm thử hồi quy và lỗi hồi quy . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Sửa lỗi chương trình tự động . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.1 Xác định vị trí gây ra lỗi . . . . . . . . . . . . . . . . . . . . . . 9 2.2.2 Các phương pháp sửa lỗi tự động hiện nay . . . . . . . . . . . 12 Phương pháp sửa tự động lỗi hồi quy 16 3.1 Tổng quan phương pháp . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Xác định bản cập nhật gây ra lỗi . . . . . . . . . . . . . . . . . . . . . . 17 3.3 Thu thập thông tin mã nguồn thay đổi và nguyên liệu sửa lỗi . . . . 22 3.4 Các mẫu sửa lỗi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.5 Xác định vị trí gây lỗi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 v 3.6 4 5 Thuật toán sửa lỗi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Cài đặt công cụ và thực nghiệm 40 4.1 Cài đặt công cụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.2 Thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.2.1 Phương pháp thực nghiệm . . . . . . . . . . . . . . . . . . . . 43 4.2.2 Kết quả thực nghiệm và thảo luận . . . . . . . . . . . . . . . . 46 Kết luận 52 A Danh sách các mẫu sửa lỗi 54 Tài liệu tham khảo 60 vi Danh sách hình vẽ 2.1 Các chiến lược kiểm thử hồi quy . . . . . . . . . . . . . . . . . . . . . 5 2.2 Các bước tiêu chuẩn trong các kỹ thuật APR hiện nay [27] . . . . . . 7 2.3 Số lượng công bố mỗi năm về APR từ 1996 - 2019 . . . . . . . . . . . . 8 2.4 Tổng quan về xác định vị trí gây lỗi dựa trên phổ chương trình . . . . 10 2.5 Tổng quan về các kỹ thuật sửa lỗi [14] . . . . . . . . . . . . . . . . . . 13 3.1 Tổng quan phương pháp sửa tự động lỗi hồi quy . . . . . . . . . . . . 17 3.2 Các bản cập nhật gây ra lỗi và sửa lỗi của Closure 31 [21] . . . . . . 18 3.3 Ví dụ minh họa tính độ đo giữa nguyên liệu sửa lỗi và câu lệnh nghi 4.1 ngờ lỗi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Kiến trúc công cụ sửa lỗi tự động LyFix . . . . . . . . . . . . . . . . . 41 vii Danh sách bảng 3.1 Nguyên liệu sửa lỗi và mẫu sửa lỗi sử dụng . . . . . . . . . . . . . . . 23 3.2 Các mẫu sửa lỗi đã cài đặt . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.1 Thống kê các chỉ số của bộ dữ liệu lỗi hồi quy . . . . . . . . . . . . . . 44 4.2 Thống kê số lượng các hành động sửa lỗi của bộ dữ liệu lỗi hồi quy . 46 4.3 Kết quả sửa lỗi trên tập dữ liệu lỗi hồi quy . . . . . . . . . . . . . . . 47 viii Danh sách từ viết tắt và thuật ngữ APR Automated Program Repair - Sửa lỗi chương trình tự động AST Abstract Syntax Tree - Cây cú pháp trừu tượng FL Fault Localization - Xác định vị trí gây lỗi SUT System Under Test - Hệ thống được kiểm thử RTS Regression Test Selection - Lựa chọn ca kiểm thử hồi quy TSM Test Suite Minimization - Giảm thiểu bộ ca kiểm thử TCP Test Case Prioritization - Ưu tiên ca kiểm thử BWTC Bug-witnessing Test Case - Ca kiểm thử phát hiện lỗi BIC Bug-inducing Commit - Bản cập nhật gây lỗi BFC Bug-fixing Commit - Bản cập nhật sửa lỗi RT Repair Templates - Các mẫu sửa lỗi, mỗi mẫu thực hiện một tập các hành động thay đổi mã nguồn để sửa lỗi FI Fix Ingredients - Các nguyên liệu sửa lỗi, là những thành phần mã nguồn có thể sử dụng làm tham số cho các mẫu sửa lỗi 1 Chương 1 Giới thiệu 1.1 Mở đầu Các hệ thống phần mềm phát triển và tiến hóa không ngừng như một lẽ tự nhiên để bắt kịp nhu cầu thay đổi liên tục từ phía khách hàng và thị trường. Quá trình phát triển phần mềm là một quá trình gia tăng, thường mang theo các tính năng mới được cài đặt để đáp ứng các yêu cầu thay đổi của người dùng. Tuy nhiên, những tính năng được thêm mới này có thể làm hỏng các chức năng hiện tại của hệ thống phần mềm và do đó gây ra lỗi mới. Những lỗi này thường được gọi là lỗi hồi quy. Lỗi hồi quy rất phổ biến trong các hệ thống phần mềm hiện nay và vẫn đang là một thách thức lớn trong ngành công nghiệp phát triển phần mềm [35, 11]. Xác định và sửa lỗi hồi quy là một hoạt động bắt buộc trong các vòng lặp bảo trì phần mềm [39]. Những nghiên cứu từ trước đến nay tập trung chủ yếu vào việc hỗ trợ phát hiện và xác định lỗi hồi quy [39, 52, 26, 22]. Trong khi đó, sửa lỗi hồi quy vẫn đang phụ thuộc lớn vào con người để gỡ và sửa lỗi một cách thủ công, khiến công việc này tiêu tốn thời gian và rủi ro. Ví dụ, người ta đã ước tính rằng các lập trình viên cần tới 8,5 năm để sửa một lỗi hồi quy [4]. Sửa lỗi tự động (Automated Program Repair - APR), bao gồm các pha xác định vị trí gây ra lỗi và sửa lỗi mới xuất hiện gần đây để giúp giải quyết vấn đề này. APR tập trung vào việc tự động quá trình gỡ lỗi phần mềm, từ đó giúp giảm bớt hoặc thậm chí loại bỏ sự can thiệp của con người vào quá trình sửa lỗi. Các nghiên cứu Chương 1. Giới thiệu 2 về APR gần đây đã đạt được một số thành công đáng kể và đóng góp cho ngành nhiều kỹ thuật sửa lỗi tốt [45, 17, 12]. Facebook gần đây đã công bố công cụ sửa lỗi tự động lần đầu tiên, được sử dụng rộng để sửa lỗi cho toàn bộ hệ thống mã nguồn lõi mà Facebook đang vận hành [2]. Điều này khẳng định APR đang là một hướng nghiên cứu mang lại nhiều đóng góp lớn cho lĩnh vực phát triển phần mềm. Mặc dù với sự phát triển mạnh mẽ gần đây, chỉ có một số kỹ thuật APR tập trung cho việc sửa lỗi hồi quy [33, 42]. Tuy nhiên, những kỹ thuật này hiện tại vẫn chưa khai thác đầy đủ thông tin trong lịch sử phát triển của hệ thống (ví dụ: thông tin thay đổi trong những bản cập nhật gây ra lỗi) để phục vụ cho việc sửa lỗi. Hơn nữa, những phương pháp sửa lỗi này không cung cấp công khai công cụ cài đặt kèm theo hoặc công cụ rất hạn chế và khó có thể áp dụng để sửa lỗi trong các dự án thực tế. Luận văn này hướng tới việc áp dụng sửa lỗi hồi quy tự động cho các chương trình Java bằng cách cài đặt và mở rộng các phương pháp sửa lỗi và các phát hiện gần đây về lỗi hồi quy (ví dụ: phương pháp sửa lỗi hồi quy tự động cho các chương trình C [42], sự tương quan giữa các bản cập nhật gây ra lỗi và sửa lỗi [46]). Luận văn tập trung vào việc sửa lỗi cho các chương trình Java bởi vì nó là một trong những ngôn ngữ lập trình phổ biến nhất cho đến hiện nay.1 Luận văn cũng đặt mục tiêu xây dựng một công cụ kèm theo, có tên LyFix, cho phép người dùng sửa lỗi hồi quy Java tự động và công bố nó như một phần mềm mã nguồn mở để cộng đồng có thể sử dụng. Khác với các kỹ thuật APR truyền thống, LyFix sử dụng các nguyên liệu sửa lỗi và những mẫu sửa lỗi cụ thể học từ lịch sử phát triển của các hệ thống phần mềm để đạt kết quả sửa lỗi tốt hơn cho các lỗi hồi quy. 1.2 Đóng góp • Luận văn phân tích bán tự động 3483 lỗi của hai bộ dữ liệu lỗi chuẩn BugSwarm2 và Bears3 , từ đó thu thập được 51 lỗi hồi quy. BugSwarm bao gồm 3232 lỗi được thu thập tự động dựa trên lịch sử tích hợp liên tục (TravisCI) của các ứng 1 http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html 2 http://www.bugswarm.org/releases/#v113 3 http://bears-bugs.github.io/bears-benchmark Chương 1. Giới thiệu 3 dụng mã nguồn mở. Bears bao gồm 251 lỗi được thu thập thủ công từ các ứng dụng mã nguồn mở với mục đích phục vụ cho các công cụ APR. • Luận văn cài đặt và công bố miễn phí công cụ kèm theo LyFix4 , bao gồm: – Đề xuất và cài đặt công thức xác định vị trí gây lỗi phù hợp cho đối tượng là lỗi hồi quy – Cài đặt lại tám mẫu sửa lỗi dựa trên tư tưởng sửa lỗi hồi quy cho chương trình C ở [42] – Đề xuất và cài đặt ba mẫu sửa lỗi hồi quy mới cho Java (mở rộng dựa trên [36] và học từ bộ dữ liệu 51 lỗi quy đã thu thập) – Đề xuất và cài đặt thuật toán cải tiến từ thuật toán sửa lỗi của [42] để sinh được nhiều bản vá hơn và các bản vá có chất lượng tốt hơn • Luận văn tiến hành thực nghiệm đánh giá khả năng sửa lỗi của LyFix so với jRelifix (là công cụ sửa lỗi phiên bản Java mà luận văn đã cài đặt lại giống với phương pháp sửa lỗi đề xuất trong [42]), jGenProg, jMutRepair và TBar trên tập dữ liệu 51 lỗi hồi quy. Đây là những lỗi hồi quy thực tế từ những hệ thống phần mềm mã nguồn mở được phát triển và kiểm thử tốt. 1.3 Bố cục luận văn Các phần còn lại của luận văn được cấu trúc như sau. Chương 2 cung cấp các kiến thức nền tảng về tính chất của lỗi hồi quy và sửa lỗi tự động. Chương 3 mô tả phương pháp sửa lỗi đề xuất, bao gồm các bước: xác định bản cập nhật gây ra lỗi, thu thập thông tin mã nguồn nguồn thay đổi và nguyên liệu sửa lỗi, xác định vị trí gây ra lỗi, các mẫu sửa lỗi và thuật toán sửa lỗi. Chương 4 mô tả về kiến trúc và cài đặt công cụ, các kết quả thực nghiệm đánh giá về khả năng sửa lỗi hồi quy của phương pháp đề xuất được tiến hành và bàn luận. Cuối cùng, Chương 5 kết luận lại toàn bộ công việc luận văn đã thực hiện, kèm theo các công việc tiếp theo có thể thực hiện để cải tiến và mở rộng công cụ. 4 https://github.com/bqcuong/lyfix 4 Chương 2 Kiến thức nền tảng Chương này cung cấp các kiến thức nền tảng cho luận văn. Đầu tiên, kiến thức kiểm thử hồi quy sẽ được giới thiệu một cách tổng quan. Tiếp theo, kiến thức về sửa lỗi chương trình tự động sẽ được trình bày, bao gồm: tổng quan, xác định vị trí gây ra lỗi, và các phương pháp sửa lỗi tự động phổ biến hiện nay. 2.1 Kiểm thử hồi quy và lỗi hồi quy Các hệ thống phần mềm thay đổi không ngừng theo thời gian. Khi có một thay đổi mới được thêm vào mã nguồn, thay đổi này có thể phá hỏng các chức năng khác của chương trình mà trước đó hoạt động bình thường. Kiểm thử hồi quy (regression testing) là một kỹ thuật được sử dụng để phát hiện các lỗi khi chương trình thay đổi. Kiểm thử hồi quy có thể áp dụng ở tất các mức kiểm thử: đơn vị, tích hợp, hệ thống, và chấp nhận [16]. Lỗi được phát hiện nhờ vào kiểm thử hồi quy gọi là lỗi hồi quy. Lỗi hồi quy được chia thành ba loại1 : • Local: Thay đổi mới gây ra lỗi, làm các chức năng tồn tại từ trước không hoạt động đúng như mong muốn nữa. Cách sửa là khôi phục lại phần mã nguồn gây ra lỗi này. 1 http://www.onestoptesting.com/regression-testing/types.asp Chương 2. Kiến thức nền tảng 5 • Unmasking: Thay đổi mới khiến luồng thực thi chương trình đi vào những câu lệnh gây ra những lỗi đã có từ trước. Cách sửa là thêm hoặc cập nhật lại các câu lệnh điều kiện để giúp luồng thực thi chương trình không còn đi vào các câu lệnh gây lỗi nữa. • Remote: Những thay đổi mới tạo ra các lỗi ở những phần mã nguồn khác trong chương trình. Để sửa những lỗi này, ta buộc phải cập nhật lại mã nguồn ở những vị trí có lỗi cho phù hợp với thay đổi hoặc ta cần phải tạo ra các câu lệnh điều kiện để luồng thực thi chương trình không đi vào những câu lệnh gây lỗi đối với một số trạng thái nhất định. Kiến thức về thông tin, tính chất của các loại lỗi hồi quy sẽ giúp luận văn này phát triển kỹ thuật xác định vị trí lỗi, lựa chọn được các nguyên liệu sửa lỗi phù hợp, và thiết kế được các mẫu sửa lỗi tốt hơn. Kiến thức về các kỹ thuật kiểm thử hồi quy giúp luận văn thiết kế thuật toán, lựa chọn bộ ca kiểm thử rút gọn để tiết kiệm thời gian thẩm định bản vá. HÌNH 2.1: Các chiến lược kiểm thử hồi quy Hình 2.1 mô tả các chiến lược phổ biến được sử dụng để thực hiện kiểm thử hồi quy hiện nay. Trong thực tế, người ta chỉ thực thi một phần của bộ ca kiểm thử để thực hiện kiểm thử hồi quy. Thử thách lớn nhất là cần thực thi lựa chọn đúng những ca kiểm thử có thể giúp đánh giá tốt nhất cho những phần mã nguồn thay đổi. Thực thi lại toàn bộ ca kiểm thử (Retest All) chỉ khả thi cho những dự án nhỏ. Trong những dự án có quy mô lớn, việc thực thi lại toàn bộ ca kiểm thử hầu như là Chương 2. Kiến thức nền tảng 6 điều không thể bởi vì nó tốn rất nhiều thời gian và có thể làm chậm quá trình phát hành sản phẩm tới khách hàng. Giảm thiểu bộ ca kiểm thử (Test Suite Minimization - TSM): Trong những hệ thống phần mềm quy mô lớn, bộ ca kiểm thử cho những hệ thống này thường rất đồ sộ, và luôn được cập nhật thêm mới các ca kiểm thử mỗi khi trải qua một bản phát triển mới. Việc thêm các ca kiểm thử mới có thể khiến những ca kiểm thử khác trở nên dư thừa bởi vì chức năng ca kiểm thử cũ có thể cũng đã được kiểm tra bởi những ca kiểm thử mới. Loại bỏ những ca kiểm thử dư thừa này không làm ảnh hướng tới độ phủ của bộ kiểm thử [41]. Các kỹ thuật TSM nhắm tới mục tiêu xác định và loại bỏ những ca kiểm thử dư thừa này ra khỏi bộ ca kiểm thử. Một số nghiên cứu đã được đề xuất có kết quả tốt như là [25, 47, 15]. Lựa chọn ca kiểm thử (Test Case Selection): Có tên gọi khác là Regression Test Selection - RTS. Các kỹ thuật RTS giống với các kỹ thuật TSM là đều lựa chọn một tập ca kiểm thử con và chỉ thực hiện kiểm thử hồi quy trên tập đó. Điểm khác biệt chính giữa hai loại kỹ thuật này là RTS lựa chọn ca kiểm thư dựa vào các thay đổi của hệ thống được kiểm thử (System Under Test - SUT) còn TSM thì không. Các kỹ thuật TSM thường lựa chọn ca kiểm thử dựa vào các chỉ số như độ phủ kiểm thử được đo từ một phiên bản nhất định của SUT. Ngược lại, RTS lựa chọn các ca kiểm thử dựa trên sự liên quan của chúng so với thay đổi giữa hai phiên bản của nguồn của SUT. Có nhiều nghiên cứu tập trung đã vào đề xuất các kỹ thuật RTS [39], [52], [53]. Ưu tiên ca kiểm thử (Test Case Prioritization - TCP): Các kỹ thuật TCP không lựa chọn một tập các ca kiểm thử còn mà tập trung vào việc sắp xếp độ ưu tiên thực thi của các kiểm thử theo một thứ tự dựa vào một số tiêu chí nào đó để có thể tìm được lỗi nhanh nhất. Điều này giúp cho các kiểm thử viên có thể tối đa tỷ lệ có thể tìm được lỗi sớm của bộ kiểm thử. Các kỹ thuật TCP có thể chia làm ba nhóm chính dựa trên các mức điều khiển, câu lệnh, và hàm của chương trình [38]. Một số nghiên cứu đề xuất các kỹ thuật TCP là [26], [22], [23]. Chương 2. Kiến thức nền tảng 2.2 7 Sửa lỗi chương trình tự động Sửa lỗi chương trình là một trong các bước của công việc gỡ lỗi chương trình cũng như vòng đời của lỗi chương trình, bao gồm: Nhận diện lỗi - Nhận diện sự tồn tại của lỗi trong chương trình, quan sát các dấu hiện của lỗi để phục vụ cho các bước sau; Xác định vị trí gây ra lỗi - Thường là bước khó nhất, mục tiêu là để xác định xem phần nào của chương trình gây ra lỗi, cụ thể nhất là ở dòng nào; Sửa lỗi - Xác định cách giải quyết lỗi như thế nào, sau đó đề xuất bản vá và thẩm định lại bản vá. HÌNH 2.2: Các bước tiêu chuẩn trong các kỹ thuật APR hiện nay [27] Sửa lỗi chương trình tự động nhắm tới mục đích tự động hóa quá trình gỡ lỗi, giảm nhu cầu về sự can thiệp của con người trong công việc này. Các kỹ thuật APR hiện tại thường gồm ba bước chính để thực hiện nhiệm vụ sửa lỗi một hoàn chỉnh như mô tả ở Hình 2.2: Xác định vị trí gây ra lỗi → Sinh và đề xuất bản vá → Thẩm định bản vá. Tương tự ở quá trình gỡ lỗi tự nhiên của con người, mô-đun xác định vị trí gây lỗi ở APR cũng nhằm mục đích xác định các phần mã nguồn nghi ngờ gây ra lỗi (ở mức dòng, phương thức, hoặc tệp). Mô-đun sinh bản vá sẽ cố gắng sửa lỗi bằng cách tạo ra nhiều bản vá ứng cử viên nhờ việc biến đổi mã nguồn có lỗi theo phương pháp đề xuất (cú pháp, ngữ nghĩa, hướng dữ liệu, v.v.). Những bản vá ứng cử viên này sẽ được mô-đun thẩm định bản vá kiểm tra xem có thực sự sửa lỗi thành công hay không thông qua việc thực hiện đánh giá chương trình đã được vá lỗi theo một đặc tả cho trước (bộ ca kiểm thử, đặc tả hình thức, v.v.). Kết quả cuối cùng sẽ là một danh sách bản vá lỗi được đề xuất cho người dùng mà có thể sử dụng để sửa lỗi chương trình ban đầu. Từ đầu những năm 2000, đã có rất nhiều nghiên cứu được thực hiện nhằm đề xuất các giải pháp phát hiện lỗi trong phần mềm [3, 6, 40] và xác định vị trí gây ra Chương 2. Kiến thức nền tảng 8 lỗi [37, 18, 19]. Các nghiên cứu cho việc tự động sửa lỗi xuất hiện theo sau với một số lượng bài báo còn hạn chế. Tuy nhiên, kể từ khi Weimer và cộng sự giới thiệu một phương pháp sửa lỗi mới dựa trên tư tưởng lập trình di truyền [45] vào năm 2009, APR đã phát triển rất mạnh mẽ và trở thành một hướng nghiên cứu hẹp thiết yếu đối với lĩnh vực công nghệ phần mềm. Điều này dễ dàng được nhận thấy ở biểu đồ thống kế số lượng công bố các nghiên cứu về APR trong giai đoạn 1996 - 2019 trong Hình 2.32 . Số lượng các công bố nghiên cứu về APR mỗi năm trước năm 2009 là dưới 5 công bố và sau năm 2009 không ngừng tăng mạnh đạt số lượng xấp xỉ 50 công bố ở các năm gần đây như năm 2018, 2019. HÌNH 2.3: Số lượng công bố mỗi năm về APR từ 1996 - 2019 2 http://program-repair.org/statistics.html Chương 2. Kiến thức nền tảng 2.2.1 9 Xác định vị trí gây ra lỗi Nhìn vào sơ đồ ở Hình 2.2, ta có thể thấy rằng xác định vị trí gây lỗi là bước đầu tiên trong các bước xử lý của bất kỳ phương pháp APR nào. Xác định vị trí gây lỗi được sử dụng để xác định những vị trí mã nguồn nghi ngờ gây ra lỗi. Những vị trí mã nguồn này sẽ được đưa vào các hệ thống APR để tập trung sửa lỗi tại đó. Ta sẽ tìm hiểu tổng quan các kỹ thuật xác định vị trí gây lỗi hiện nay, và sau đó tập trung vào kỹ thuật xác định vị trí gây lỗi dựa trên phổ (spectrum-based Fault Localization) là chiến lược xác định lỗi được sử dụng phổ biến nhất trong các kỹ thuật APR và trong luận văn này. Các kỹ thuật xác định vị trí gây lỗi truyền thống rất trực quan và đơn giản, bất cứ người lập trình nào cũng có thể sử dụng. Ta có thể nhắc tới bốn phương pháp sau đây [48]: • Hệ thống log: Sử dụng các câu lệnh dùng để in các giá trị trong chương trình (ví dụ: câu lệnh System.out.println()). Đây là một cách cực kỳ đơn giản và hữu hiệu để theo dõi thông tin về trạng thái của chương trình. Khi mà phát hiện có lỗi trong chương trình, nhà phát triển có thể điều tra log của chương trình để tìm ra vị trí lỗi xuất phát từ đâu. • Assertions: Là các câu lệnh do người phát triển thêm vào để đảm bảo các giá trị trạng thái của chương trình đúng với mong muốn tại thời điểm chèn assertion (ví dụ: assertEquals(5, arr.length)). Chương trình sẽ dừng lại ngay lập tức nếu như một trong các câu lệnh assertion đánh giá sai. Từ đó nhà phát triển có thể biết được lỗi bắt đầu ở câu lệnh cuối cùng thay đổi giá trị của biến được kiểm tra trong câu lệnh assertion (như ví dụ trên, biến này là arr.length). • Breakpoints: Các trình gỡ lỗi sẽ cho phép người đặt các Breakpoint này. Breakpoint được sử dụng để dừng chương trình khi luồng thực thi đi đến một điểm mong muốn, và nó cho phép nhà phát triển có thể theo dõi được trạng thái hiện tại của chương trình. Thậm chí nhà phát triển có thể thay đổi được giá trị các biến, thêm các câu lệnh mới ngay sau điểm Breakpoint để đánh giá và tìm Chương 2. Kiến thức nền tảng 10 hiểu thêm thông tin về lỗi để xác định vị trí gây ra lỗi. Một số trình gỡ lỗi hỗ trợ các tính năng này là GNU GDB3 , Microsoft Visual Studio Debugger4 . • Profiling: Là một phương pháp phân tích các chỉ số trong lúc chạy chương trình như mức sử dụng bộ nhớ, tốc độ thực thi, thường được sử dụng để đánh giá và tối ưu chương trình. Tuy nhiên, phương pháp này có thể được sử dụng để tìm ra một số lỗi chương như: Xác định lỗi rò rỉ bộ nhớ, Phát hiện số lần thực thi không mong muốn của một hàm, v.v. Một số công cụ tiêu biểu có thể nói đến là Valgrind5 , VisualVM6 . Các kỹ thuật xác định vị trí gây lỗi truyền thống thường được thực hiện một cách thủ công hoặc bán tự động. Chính vì vậy, các kỹ thuật xác định vị trí gây lỗi nâng cao ra đời, nhằm giảm thiểu tối đa sự can thiệp của con người vào quá trình xác định vị trí lỗi. Các kỹ thuật xác định vị trí gây lỗi nâng cao phổ biến hiện này có thể chia làm tám loại chính [48]: Dựa trên lát cắt (slide-based), Dựa trên mật đổ phổ chương trình (spectrum-based), Dựa trên xác suất (statistics-based), Dựa trên trạng thái chương trình (state-based), Dựa trên học máy (machine learning-based), Dựa trên khai phá dữ liệu (data mining-based), Dựa trên mô hình (model-based), và Một số kỹ thuật khác [5, 7, 13]. HÌNH 2.4: Tổng quan về xác định vị trí gây lỗi dựa trên phổ chương trình Hiện nay, thường thì các kỹ thuật APR đều sử dụng cùng một chiến lược xác định vị trí lỗi là dựa trên phổ chương trình. Phổ chương trình cung cấp các thông 3 https://www.gnu.org/software/gdb 4 https://docs.microsoft.com/visualstudio/debugger 5 https://www.valgrind.org 6 https://visualvm.github.io 11 Chương 2. Kiến thức nền tảng tin thực thi của chương trình theo một số khía cạnh nhất định. Phổ chương trình có thể dùng để theo dõi hành vi của chương trình, do đó nó có ích cho việc xác định vị trí gây lỗi. Khi một đường thực thi thất bại, những thông tin trên đường thực thi đó có thể được sử dụng để xác định ra những dòng mã nguồn nghi ngờ gây ra lỗi. Ví dụ như thông tin về độ phủ mã nguồn (code coverage), hoặc ESHS (Executable Statement Hit Spectrum) có thể cho ta biết những câu lệnh nào được thực thi khi thực hiện đường thực thi thất bại. Từ đó, giảm không gian tìm kiếm cho việc xác định các câu lệnh nghi ngờ gây ra lỗi. Có nhiều kỹ thuật xác định vị trí gây lỗi dựa trên phổ ra đời (chủ yếu dựa trên ESHS), trong đó có một kỹ thuật dựa trên hệ số tương đồng nổi tiếng nhất là Tarantula [20]. Kỹ thuật này sử dụng thông tin về độ phủ các câu lệnh và kết quả của các lần thực thi bộ kiểm thử. Từ đó, tính ra độ nghi ngờ gây lỗi cho các câu lệnh trong chương trình theo Công thức 2.1. Giá trị của công thức này được tính bằng tỉ lệ các ca kiểm thử failed đi qua câu lệnh s chia cho tổng tỉ lệ các ca kiểm failed và passed đi qua câu lệnh s. f ailed(s) Tarantula(s) = total f ailed f ailed(s) total f ailed Ochiai (s) = p + passed(s) (2.1) total passed f ailed(s) total f ailed × ( f ailed(s) + passed(s))) (2.2) Trong đó: s là câu lệnh được tính độ nghi ngờ, f ailed(s) là số lượng ca kiểm thử thất bại có đường thực thi qua s, passed(s) là số lượng ca kiểm thử thất bại có đường thực thi qua s, total f ailed là tổng số lượng ca kiểm thử thất bại, total passed là tổng số lượng ca kiểm thử thành công. Gần đây, kỹ thuật Ochiai [1] được đề xuất và thực nghiệm cho thấy Ochiai có kết quả đánh giá tốt hơn so với Tarantula. Độ nghi ngờ của các câu lệnh theo Ochiai Chương 2. Kiến thức nền tảng 12 được tính theo Công thức 2.2. Hình 2.47 mô tả tổng quan về kỹ thuật xác định vị trí gây lỗi dựa trên phổ chương trình với độ nghi ngờ của các câu lệnh tính bằng công thức Ochiai. Với đầu vào là chương trình và bộ ca kiểm thử, thông tin về phổ chương trình sẽ thu được nhờ thực thi tất cả ca kiểm thử (đường thực thi của ca kiểm thử chạy qua những câu lệnh nào). Những thư viện hỗ trợ nhiệm vụ này có thể là JaCoCo8 , PIT9 , v.v. Tiếp đó, những thông tin về phổ này được sử dụng để tính toán độ nghi ngờ cho từng câu lệnh dựa vào công thức đã đề xuất, giá trị độ nghi ngờ thuộc đoạn [0.0, 1.0]. 2.2.2 Các phương pháp sửa lỗi tự động hiện nay Hiện nay, các pnghiên cứu sửa lỗi tự động có thể chia thành ba loại chính: sửa lỗi dựa trên phỏng đoán/cú pháp (heuristic-based), sửa lỗi dựa trên ràng buộc/ngữ nghĩa (constraint-based), và sửa lỗi dựa trên học máy/dữ liệu (learning-based) [14]. Hình 2.5 mô tả tổng quan các phương pháp sửa lỗi này. Các phương pháp sửa lỗi dựa trên phỏng đoán thường sử dụng chiến lược Sinh và Thẩm định (Generate-and-Validate). Sau khi nhận kết quả các vị trí mã nguồn nghi ngờ có lỗi từ mô-đun xác định vị trí gây lỗi, những phương pháp này đầu tiên sẽ sinh ra một tập các biến đổi mã nguồn (bằng cách thêm, sửa, xóa các thành phần mã nguồn ở vị trí lỗi), gọi là không gian tìm kiếm. Sau khi áp dụng những biến đối mã nguồn này vào chương trình có lỗi sẽ thu được một tập các bản vá ứng cử viên. Quá trình này gọi là Sinh. Tiếp theo, quá trình Thẩm định sẽ thực thi các ca kiểm thử trên các chương trình đã áp dụng các bản vá ứng cử viên và đếm số lượng ca kiểm thử thành công. Nếu tất cả ca kiểm thử đều thành công, thì bản vá ứng cử viên đó được coi là một bản vá chính thức của chương trình có lỗi ban đầu. Nhược điểm của các kỹ thuật này là không gian tìm kiếm có thể vô cùng lớn bởi vì có vô số cách kết hợp của các thành phần mã nguồn với nhau để tạo thành một bản vá. Một số công cụ tiêu biểu có thể kể đến khi nói đến những phương pháp này bao gồm GenProg [45], ssFix [49], SimFix [17], HDRepair [24], v.v. 7 https://youtu.be/pJV1oMd-nno?t=60 8 https://www.eclemma.org/jacoco 9 https://pitest.org Chương 2. Kiến thức nền tảng 13 HÌNH 2.5: Tổng quan về các kỹ thuật sửa lỗi [14] Các phương pháp sửa lỗi dựa trên ngữ nghĩa sử dụng một phương pháp khác so với chiến lược của những phương pháp dựa trên phỏng đoán. Những phương pháp này tập trung xây dựng ra hệ các ràng buộc để phục vụ cho việc sinh các bản vá. Hệ các ràng buộc này thường mô tả về một phần mã nguồn (mã nguồn vá lỗi) mà có thể thỏa mãn được về kiểu, giá trị của biến hoặc hành vi được mô tả trong các ràng buộc. Phần mã nguồn vá lỗi này sẽ được coi như là một hàm ẩn. Ví dụ các phương pháp thực thi tượng trưng (symbolic execution) có thể trích xuất ra được các thuộc tính của hàm ẩn này, sau đó các thuộc tính này sẽ được tổng hợp thành hệ các ràng buộc. Bằng cách sử dụng các bộ giải ràng buộc (ví dụ Z3, CVC4, v.v.) hoặc các thuật toán tìm kiếm cao cấp, hệ các ràng buộc sẽ được giải. Phần mã nguồn vá lỗi sẽ được tổng hợp từ kết quả giải hệ các ràng buộc dựa trên các phương pháp tổng hợp chương trình (program synthesis). Những phương pháp này thường sửa hiệu quả cho các lỗi liên quan đến các biểu thức điều kiện ở câu lệnh if như sửa điều kiện sai, thêm điều kiện còn thiếu. Một số công cụ đại diện cho phương pháp này là SPS [31], Nopol [51], ACS [50], v.v.