Luận văn Thạc sĩ Hệ thống thông tin: Nghiên cứu giải pháp và công cụ hỗ trợ gợi ý sửa lỗi cho các chương trình java

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

Thêm vào BST

Báo xấu

18
lượt xem 2
download

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

Luận văn được cấu trúc như sau: Chương 2 trình bày về các cơ sở lí thuyết hoặc công nghệ được sử dụng trong luận văn; Chương 3 mô tả chi tiết về các giải pháp giải quyết bài toán; Cách cài đặt công cụ và các kết quả thực nghiệm trên các ví dụ cụ thể được trình bày ở Chương 4; Cuối cùng là Chương 5 tổng kết và hướng nghiên cứu tiếp theo của luận văn.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Hệ thống thông tin: Nghiên cứu giải pháp và công cụ hỗ trợ gợi ý sửa lỗi cho các chương trình java

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Phan Thị May NGHIÊN CỨU GIẢI PHÁP VÀ CÔNG CỤ HỖ TRỢ GỢI Ý SỬA LỖI CHO CÁC CHƯƠNG TRÌNH JAVA LUẬN VĂN THẠC SĨ Ngành: Hệ thống thông tin HÀ NỘI – 2021
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Phan Thị May NGHIÊN CỨU GIẢI PHÁP VÀ CÔNG CỤ HỖ TRỢ GỢI Ý SỬA LỖI CHO CÁC CHƯƠNG TRÌNH JAVA LUẬN VĂN THẠC SĨ Ngành: Hệ thống thông tin Cán bộ hướng dẫn: PGS. TS. Phạm Ngọc Hùng HÀ NỘI – 2021 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
VIETNAM NATIONAL UNIVERSITY, HANOI UNIVERSITY OF ENGINEERING AND TECHNOLOGY Phan Thị May RESEARCH SOLUTIONS AND SUPPORT TOOLS TO SUGGEST FIXES FOR ERRORS IN JAVA PROGRAMS MASTER THESIS Information Systems Supervisor: Assoc. Prof. Pham Ngoc Hung LỜI CẢM ƠN HANOI - 2021 VIETNAM NATIONAL UNIVERSITY, HANOI UNIVERSITY OF ENGINEERING AND TECHNOLOGY
LỜI CẢM ƠN Trước tiên tôi xin gửi lời cảm ơn chân thành và sâu sắc tới thầy giáo PGS. TS. Phạm Ngọc Hùng, người thầy định hướng cho tôi, đưa cho tôi những lời khuyên, động viên tôi trong suốt quá trình học tập và làm luận văn. Thầy đã dạy cho tôi những bài học kinh nghiệm quý giá trong công việc, nghiên cứu và trong cuộc sống, tiếp thêm động lực cho tôi, giúp tôi tự tin vào chính mình. Tôi cũng xin gửi lời cảm ơn chân thành tới các bạn trong phòng nghiên cứu R320, đặc biệt là sự hỗ trợ và động viên của bạn Nguyễn Thị Huyền và Phạm Khắc Ân. Nhờ có những chia sẻ và hỗ trợ của các bạn nên tôi đã tìm kiếm được những bài báo có giá trị trong nghiên cứu và làm chủ được công cụ. Tiếp theo tôi xin gửi lời cảm ơn tới các thầy cô trong trường Đại học Công nghệ, những người thầy tận tâm truyền đạt những kiến thức bổ ích giúp tôi tiếp tục đi xa hơn trong lĩnh vực công nghệ thông tin. Thời gian học tập tại Đại học Công nghệ tôi không chỉ học kiến thức mà còn học được rất nhiều bài học từ phương pháp, từ phong cách, từ triết lí sống và học tập của thầy cô. Những gì học được ở đây sẽ giúp ích tôi rất nhiều trên con đường trở thành một giáo viên Tin học tốt. Tôi xin gửi lời cảm ơn tới Ban giám hiệu trường trung học phổ thông Yên Hòa và các đồng nghiệp trong cơ quan. Trong suốt thời gian tôi học thạc sĩ đã nhận được sự động viên, giúp đỡ và tạo điều kiện để việc học được thuận lợi nhất. Cuối cùng tôi xin được cảm ơn gia đình của tôi, những người đã hết sức hỗ trợ, lo chu toàn việc nhà để tôi yên tâm học tập. Gia đình cũng đã động viên tôi rất nhiều, là nguồn động lực tinh thần to lớn để tôi phấn đấu hoàn thiện bản thân. Xin chân thành cảm ơn vì tất cả. i
TÓM TẮT Tóm tắt: Xuất phát từ thực tế dạy lập trình ở trường phổ thông học sinh thường hay mắc lỗi nhưng do lớp học đông, giáo viên rất khó bao quát và sửa lỗi cho từng em. Vấn đề đặt ra là làm thế nào để hỗ trợ sửa lỗi cho học sinh trong quá trình học lập trình. Để giải quyết vấn đề này học viên đi nghiên cứu các công cụ định vị lỗi và gợi ý sửa lỗi hiện có. Trên cơ sở phù hợp với bài toán đặt ra đã lựa chọn hai công cụ mã nguồn mở Gzoltar và JPlag để tích hợp với nhau, giúp giải quyết bài toán lõi. Công cụ Gzoltar sử dụng phương pháp định vị lỗi quang phổ để xác định vị trí lỗi. Tư tưởng chung là dựa trên độ bao phủ của các ca kiểm thử trên mỗi câu lệnh của chương trình để tính ra điểm nghi ngờ của từng câu lệnh theo công thức quang phổ Ochiai. Điểm nghi ngờ càng cao thì câu lệnh càng có khả năng lỗi, do đó giúp học sinh tập trung vào các câu lệnh lỗi thay vì sửa toàn bộ chương trình. Trong trường hợp học sinh được chỉ lỗi nhưng chưa sửa được, chương trình thì có thể gọi tới dịch vụ gợi ý sửa lỗi. Tư tưởng chính của việc gợi ý sửa lỗi là tìm ra các chương trình đúng có độ tương đồng cao với chương trình lỗi để đưa ra làm gợi ý. Việc so sánh và tìm ra chương trình đúng có độ tương đồng cao với chương trình lỗi phải được thực hiện bằng phương pháp so sánh đặc biệt, phương pháp Tokenization. Phương pháp Tokenization tiến hành so sánh các Tokens, mã thông báo đặc trưng cho câu lệnh, chứ không thực hiện so sánh từ với từ giữa các mã nguồn. Sau khi nhận được các gợi ý học sinh tiến hành sửa chữa và chạy lại chương trình đến khi thu được chương trình đúng. Chương trình này được gắn nhãn và lưu vào bộ sưu tập tương ứng, làm căn cứ gợi ý cho các chương trình trong tương lai. ii
ABSTRACT Abstract: Derived from the reality of teaching programming in high schools, students often make mistakes, but due to large classes, it is difficult for teachers to cover and correct each child's errors. The problem is how to support students to correct errors in the process of learning programming. Learners go to research the existing debugging tools and suggestions. On the basis of matching with the problem posed, two open source tools Gzoltar and JPlag were selected to integrate together, helping to solve the core problem. The Gzoltar tool uses the spectral fault locating method to locate the fault. The general idea is based on the coverage of test cases on each statement of the program, applying the Ochiai spectral formula to calculate the suspect score of each statement. The higher the doubt score, the more likely the statement is to fail, thus helping students focus on the error statements instead of fixing the entire program. In case the student is shown the error but cannot fix the program, they can call the error correction service. The main idea of debugging suggestions is to find correct programs with high similarity to the faulty program to make suggestions. Comparing and finding the correct program with high similarity to the error program must be done by a special comparison method, comparing Tokens, the token specific to the statement, and not doing word comparisons. with words between source codes. After receiving the suggestions, the students make corrections and run the program again until the correct program is obtained. This program is labeled and saved in the corresponding collection, as a basis for suggestions for future shows. iii
LỜI CAM ĐOAN Tôi xin cam đoan rằng luận văn của tôi chưa từng được nộp như một báo cáo luận văn tại Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội hoặc bất kỳ trường đại học nào khác. Những gì tôi viết ra không sao chép từ các tài liệu, không sử dụng các kết quả nghiên cứu của người khác mà không trích dẫn cụ thể. Nếu sai tôi hoàn toàn chịu trách nhiệm theo quy định của trường Đại học Công nghệ - Đại học Quốc gia Hà Nội. Hà Nội, ngày tháng 11 năm 2021 Học viên Phan Thị May iv
MỤC LỤC LỜI CẢM ƠN ................................................................................................................ i TÓM TẮT ..................................................................................................................... ii ABSTRACT ................................................................................................................. iii LỜI CAM ĐOAN ........................................................................................................ iv DANH SÁCH THUẬT NGỮ/ TỪ VIẾT TẮT ......................................................... vii DANH SÁCH HÌNH VẼ ............................................................................................ vii DANH SÁCH BẢNG ................................................................................................. viii DANH SÁCH CÁC MÃ NGUỒN ............................................................................ viii DANH SÁCH CÁC THUẬT TOÁN ........................................................................ viii Chương 1. Đặt vấn đề ....................................................................................................1 Chương 2. Kiến thức nền tảng .....................................................................................5 2.1. Các phương pháp xác định vị trí lỗi .....................................................................5 2.1.1. Phương pháp định vị lỗi truyền thống ...........................................................5 2.1.2 Phương pháp định vị lỗi hiện đại....................................................................6 2.2. Các phương pháp gợi ý sửa lỗi .............................................................................7 Chương 3. Phương pháp xác định vị trí lỗi và gợi ý sửa lỗi ....................................13 3.1. Tổng quan về phương pháp xác định vị trí lỗi và gợi ý sửa lỗi ..........................13 3.2. Xác định vị trí lỗi ................................................................................................14 3.2.1. Xác định vị trí lỗi bằng phương pháp quang phổ .......................................14 3.2.2. Sử dụng thư viện Gzoltar để xác định vị trí lỗi ...........................................17 3.3. Gợi ý sửa lỗi chương trình ..................................................................................18 3.3.1. Tổng quan về giải pháp gợi ý chương trình ................................................18 3.3.2. Phân tích chương trình thành chuỗi các Tokens .........................................19 3.3.3. So sánh các chuỗi Tokens............................................................................21 3.4. Ví dụ minh họa ...................................................................................................25 Chương 4. Công cụ và thực nghiệm...........................................................................31 4.1. Cài đặt công cụ ...................................................................................................31 4.2. Thực nghiệm .......................................................................................................36 4.2.1. Chuẩn bị thực nghiệm .................................................................................36 4.2.2. Kết quả thực nghiệm ...................................................................................37 4.3. Thảo luận ............................................................................................................40 v
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN TƯƠNG LAI .........................................43 1. Kết luận..................................................................................................................43 2. Hướng phát triển tương lai ....................................................................................43 TÀI LIỆU THAM KHẢO...........................................................................................45 PHỤ LỤC .....................................................................................................................48 vi
DANH SÁCH THUẬT NGỮ/ TỪ VIẾT TẮT Thuật ngữ/ từ viết tắt Từ đầy đủ Ý nghĩa Application API Giao diện lập trình ứng dụng Programming Interface Thuật toán so sánh chuỗi Tokens GST Greedy-String-Tiling sử dụng trong công cụ Jplag Integrated Development IDE Môi trường phát triển tích hợp Environment NT Negative Test Kiểm thử tiêu cực PT Positive Test Kiểm thử tích cực DANH SÁCH HÌNH VẼ Hình 1. 1. Biểu đồ ca sử dụng hệ thống hỗ trợ học lập trình .......................................... 2 Hình 2.1. Tập hành vi của chương trình .......................................................................... 9 Hình 2.2. Mối quan hệ giữa các hành vi được cài đặt, được đặc tả và được kiểm thử ............ 10 Hình 2.3. Đồ thị dòng điều khiển tương ứng độ phủ C3 của hàm fibonacci ................ 11 Hình 3. 1. Luồng thực thi tổng quan ............................................................................ 13 Hình 3. 2. Tiền xử lí mã nguồn .................................................................................... 14 Hình 3. 3. Luồng xử lí của thuật toán định vị lỗi quang phổ ....................................... 15 Hình 3. 4. Luồng xử lí định vị lỗi ................................................................................. 17 Hình 3. 5. Quy trình thực thi của JPlag ........................................................................ 19 Hình 3. 6. So sánh chương trình lỗi với các chương trình mẫu ................................... 21 Hình 4. 1. Kiến trúc hệ thống ....................................................................................... 41 Hình 4. 2. Kết quả chỉ lỗi một chương trình................................................................. 33 Hình 4. 3. Danh sách kết quả so sánh mã nguồn .......................................................... 34 Hình 4. 4. Hiển thị chương trình gợi ý ......................................................................... 35 vii
DANH SÁCH BẢNG Bảng 2 1. Các ca kiểm thử cho hàm fibonacci với độ phủ C3 ......................................12 Bảng 3. 1. Ví dụ về mã nguồn và ca kiểm thử ..............................................................16 Bảng 3. 2. Kết quả tính điểm số nghi ngờ từng câu lệnh ..............................................16 Bảng 3. 3. So sánh và tìm chuỗi con trong mã nguồn A và B.......................................24 Bảng 4. 1. Danh sách các ca kiểm thử cho bài toán số nguyên tố ................................ 26 Bảng 4. 2. Kết quả định vị lỗi Problem1 .......................................................................26 Bảng 4. 3. Kết quả định vị lỗi Problem2 .......................................................................27 Bảng 4. 4. Kết quả định vị lỗi Problem3 ...................................................................... 28 Bảng 4. 5. Kết quả định vị lỗi Problem4 .......................................................................29 Bảng 4. 6. Thống kê kết quả thực nghiệm .....................................................................38 Bảng 4. 7. Đánh giá hiệu quả của công cụ trên các bài toán thực nghiệm ................... 39 DANH SÁCH CÁC MÃ NGUỒN Mã nguồn 2. 1. Hàm fibonacci ......................................................................................11 Mã nguồn 3. 1. Sử dụng Gzoltar để định vị lỗi .............................................................18 Mã nguồn 3.2. Tách mã nguồn thành các Token ..........................................................20 Mã nguồn 3.3. Mã nguồn lỗi cần gợi ý sửa ...................................................................23 Mã nguồn 4.1. Phương thức GetSuspiciousContext ....................................................32 Mã nguồn 4.3. Phương thức FaultStatement .................................................................33 DANH SÁCH CÁC THUẬT TOÁN Thuật toán 3. 1. Thuật toán Greedy-String-Tiling (GST) .............................................22 viii
Chương 1. Đặt vấn đề Chương trình giáo dục phổ thông năm 2018 [1] xác định vai trò chiến lược của môn Tin học là trang bị cho học sinh các kiến thức cơ bản về thế giới công nghệ, các kỹ năng về lập trình, thuật toán, tư duy logic, kỹ năng phân tích và giải quyết vấn đề. Chương trình cũng không giới hạn ngôn ngữ lập trình mà khuyến khích giảng dạy các ngôn ngữ lập trình phổ biến, có tính ứng dụng cao như Python, Java, C++, v.v. Định hướng đơn vị nơi học viên đang công tác sẽ lựa chọn giảng dạy Java trong chương trình sắp tới. Theo TIOBE index [2], tính đến 8/2021 Java hiện là ngôn ngữ có mức độ phổ biến đứng thứ ba trên thế giới, do đó việc dạy ngôn ngữ lập trình Java có nhiều ưu điểm nổi bật hơn các ngôn ngữ khác, thu hút được học sinh. Chương trình giáo dục phổ thông 2018 cũng chú trọng dạy học phát triển năng lực học sinh trên nền tảng đổi mới phương pháp giảng dạy. Để hiện thực hóa mục tiêu đó trong môn Tin học thì việc phát triển các công cụ hỗ trợ là điều cần thiết. Trên thực tế việc dạy và học lập trình ở trường phổ thông gặp khá nhiều khó khăn. Do mặt bằng chung của học sinh còn kém, học sinh mới học lập trình thường xuyên xảy ra lỗi (cả lỗi cú pháp và lỗi ngữ nghĩa) mà không tự sửa được nên phụ thuộc nhiều vào giáo viên. Tuy nhiên, học sinh mỗi lớp rất đông nên giáo viên không thể sâu sát sửa lỗi cho từng em. Thời lượng phân bổ cho nội dung thực hành ít, khoảng 35% tổng thời lượng chương trình nên số lượng bài tập được giải quyết trong mỗi kì không nhiều. Mà kỹ năng lập trình của học sinh tỉ lệ thuận với số lượng bài tập các em làm nên làm ít bài tập đồng nghĩa với kỹ năng thực hành của học sinh chưa tốt. Để giải quyết vấn đề trên học viên có định hướng xây dựng một hệ thống hỗ trợ sửa lỗi trong quá trình học lập trình Java trực tuyến cho học sinh trung học phổ thông như mô tả trong Hình 1.1. Hệ thống này cho phép học sinh học và làm bài bất cứ khi nào, không phân biệt không gian, thời gian. Hệ thống cho phép học sinh nộp bài và xem kết quả bài làm, nếu bài làm còn lỗi (lỗi ngữ nghĩa) hệ thống sẽ chỉ lỗi cho học sinh, cùng với đó sẽ hỗ trợ gợi ý sửa lỗi bằng cách đưa ra các chương trình đúng tương tự. Việc hỗ trợ học tập như trên sẽ giúp học sinh làm được nhiều bài tập hơn, tăng kỹ năng lập trình. Ý nghĩa lớn hơn là việc tương tác với hệ thống tự động có thể giải quyết các nhiệm vụ khó khăn sẽ khiến học sinh vô cùng thích thú, từ đó sẽ tạo được tình yêu với lập trình, đam mê khoa học cho học sinh. Đây cũng là môi trường học tập chủ động, tích cực giúp phát triển tư duy của học sinh. Các bài tập trên hệ thống được chia thành các chủ đề khác nhau và được gắn nhãn để phân biệt. Khi học sinh làm và nộp bài trên hệ thống, bài làm sẽ được kiểm tra bằng bộ các ca kiểm thử được xây dựng sẵn. Nếu bài làm đúng với mọi ca kiểm thử thì được đánh giá là không có lỗi, bài sẽ được chấm điểm và được lưu trữ vào bộ sưu tập tương ứng. Bộ sưu tập các lời giải cho bài toán sẽ nhiều lên qua thời gian khi bài làm đúng 1
của các học sinh nộp vào tăng dần. Các bài làm này sẽ đóng vai trò các gợi ý cho các học sinh làm sai. Nếu bài làm của học sinh có lỗi (không vượt qua tất cả các ca kiểm thử), học sinh có thể lựa chọn tự sửa lỗi và chạy lại chương trình cho tới khi đúng hoặc sử dụng gợi ý. Gợi ý mức một là hệ thống sẽ giúp chỉ ra vị trí câu lệnh có khả năng gây lỗi cao. Dựa trên gợi ý của hệ thống học sinh sẽ tiếp tục sửa lỗi và chạy lại chương trình cho tới khi đúng và thực hiện lưu vào bộ sưu tập như trên. Nếu chương trình vẫn chưa đúng, hệ thống sẽ đưa ra gợi ý mức hai là hiển thị chương trình đúng “tương tự” như chương trình học sinh đang viết. Học sinh dựa trên kết quả chỉ lỗi ở bước trước và chương trình đúng được gợi ý mà tự đối chiếu và sửa lỗi hoàn chỉnh cho chương trình của mình. Điểm của học sinh được tính theo quy chế khác nhau với các mức gợi ý khác nhau. Đối với học sinh đúng ngay từ lần đầu hoặc tự sửa lỗi không sử dụng gợi ý sẽ được tối đa 100 điểm. Học sinh sử dụng gợi ý chỉ vị trí lỗi (gợi ý mức một) mà sửa được bài đúng sẽ được tối đa 95 điểm. Học sinh xem gợi ý bài đúng tương tự (gợi ý mức hai) và sửa được bài sẽ được tối đa 90 điểm. Điểm của học sinh sẽ được cộng dần qua từng bài tập học sinh giải được. Cơ chế cho điểm này vừa đảm bảo nguyên tắc công bằng, vừa khuyến khích học sinh tích cực chủ động trong học tập. Xem bài tập Quản lí bài tập Nộp bài Giao bài tập Xem kết quả Quản lí điểm Xem gợi ý sửa lỗi Xem điểm Học sinh Giáo viên Xem vị trí lỗi XÁC ĐỊNH VỊ TRÍ LỖI & GỢI Ý SỬA LỖI Hình 1.1. Biểu đồ ca sử dụng hệ thống hỗ trợ học lập trình 2
Hiện nay, đã có nhiều hệ thống hỗ trợ học sinh học lập trình trực tuyến và phần nào giải quyết được những vấn đề nêu trên. Có thể kể đến hệ thống hỗ trợ dạy và học học phần lập trình hướng đối tượng OASIS [3] dành cho sinh viên của Khoa Công nghệ thông tin, Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội, hệ thống Codehub [4], hệ thống Ucode.vn [5], hệ thống codelearn.io [6] do FPT Soft phát triển, v.v. Các hệ thống cho phép học sinh, sinh viên thực hành lập trình trực tiếp trên Web, hỗ trợ chỉ lỗi cú pháp, chấm điểm và chỉ ra ca kiểm thử lỗi (nếu có). Các hệ thống cũng cung cấp các video bài giảng hoặc các tài nguyên học tập khác giúp học sinh học tập. Ưu điểm hơn cả là hệ thống OASIS. Hệ thống này giúp giảng viên quản lí và giao bài cho sinh viên. Cơ chế chấm điểm của OASIS dựa trên ba tiêu chí: chấm điểm dựa trên bộ các ca kiểm thử, chấm điểm bằng tệp kiểm thử đơn vị và chấm điểm dựa trên thiết kế. Hệ thống này còn giúp đánh dấu vị trí lỗi cú pháp và thông báo lỗi giúp sinh viên dễ dàng sửa chữa. Tuy nhiên, chưa có ứng dụng nào có chức năng chỉ vị trí lỗi ngữ nghĩa và gợi ý sửa lỗi cho chương trình như bài toán đưa ra. Vì vậy, phát triển một hệ thống theo định hướng trên là hết sức cần thiết. Lõi của hệ thống được mô tả ở trên gồm hai mô-đun là xác định vị trí lỗi (định vị lỗi) và gợi ý sửa lỗi. Để định vị lỗi hệ thống tính điểm nghi ngờ của từng câu lệnh tương ứng bộ ca kiểm thử xây dựng sẵn. Dựa trên điểm nghi ngờ, câu lệnh nào có chỉ số cao là câu lệnh có khả năng gây lỗi nhiều nhất. Từ đây, học sinh sẽ tập trung vào các câu lệnh có khả năng gây lỗi cao thay vì tìm kiếm trong toàn bộ chương trình. Quá trình gợi ý sửa lỗi, hệ thống sẽ tìm kiếm trong bộ sưu tập các chương trình đúng “tương tự” về cấu trúc, cách viết với chương trình đang cần sửa của học sinh và đưa ra hai chương trình song song để học sinh so sánh. Cùng với những gợi ý về vị trí lỗi được chỉ ra ở bước trên và chương trình đúng được gợi ý, học sinh sẽ tự so sánh, đánh giá để sửa chữa chương trình của mình sao cho chính xác. Trong thời gian ngắn làm luận văn và năng lực phát triển các ứng dụng của bản thân còn hạn chế, học viên chỉ đi xây dựng hệ thống lõi cho bài toán nêu trên với ngôn ngữ lập trình Java. Phần chỉ lỗi cú pháp sẽ được phát hiện bởi các IDE, tương tự như IntelliJ. Với các yêu cầu về hệ thống dự kiến nêu trên, luận văn sẽ phải giải quyết những vấn đề sau: Một là, nghiên cứu về các phương pháp xác định vị trí lỗi (định vị lỗi) và tự động sửa lỗi hiện có, đánh giá tính hiệu quả và phù hợp với yêu cầu của bài toán để lựa chọn công cụ phù hợp nhất giúp giải quyết bài toán. Có thể thấy có rất nhiều các phương pháp định vị lỗi khác nhau từ phương pháp truyền thống như Logging [7], Breakpoint [8], v.v. hay một số phương pháp hiện đại như Slicing [9], Spectrum [8], Program State [10], v.v. Báo cáo tổng hợp về các phương pháp định vị lỗi [8] của W. Eric Wrong đã đánh giá tính hiệu quả của các phương pháp kể trên. Báo cáo cũng đồng thời chỉ ra phương pháp định vị lỗi quang phổ đang được nhận được nhiều sự quan tâm nghiên cứu và phát 3
triển ứng dụng trong thời gian qua, điều này chứng minh phương pháp quang phổ là một phương pháp có hiệu quả. Các phương pháp định vị lỗi trên cũng đã được phát triển và sử dụng trong các công cụ sửa lỗi tự động như GenProg [11], SimFix [12], Getafix [13], v.v. Getafix là công cụ của Facebook, có khả năng sửa được lỗi NullPulumException trên hệ điều hành Android. Đặc biệt, Gzoltar [14] là một thư viện mã nguồn mở sử dụng phương pháp định vị lỗi quang phổ, nó được quan tâm phát triển hiệu quả trong thời gian gần đây và là một lựa chọn phù hợp cho nhiệm vụ này của bài toán. Hai là, nghiên cứu về các công cụ gợi ý sửa lỗi. Thực chất là nghiên cứu các công cụ so sánh các chương trình với mục tiêu tìm ra các chương trình có độ tương đồng cao để gợi ý cho học sinh. Bản chất của việc này tương tự như nghiên cứu các phương pháp kiểm tra mã nguồn trùng lặp để phát hiện đạo văn, nhưng được ứng dụng để tìm chương trình đúng gần nhất với chương trình cần sửa chữa của học sinh. Ba là vận dụng các kiến thức thu được áp dụng vào các định vị lỗi và gợi ý sửa lỗi cho các bài tập cụ thể của học sinh. Sau đó triển khai thực nghiệm, đánh giá tính hiệu quả của phương pháp này. Việc xây dựng và hoàn thiện hệ thống sẽ là hướng nghiên cứu tiếp theo của luận văn. Hệ thống sẽ là một công cụ đắc lực hỗ trợ giáo viên dạy học, giúp tiết kiệm nhiều thời gian và công sức. Hệ thống cũng giúp học sinh học tập chủ động mọi lúc mọi nơi, tương tác tích cực và hiệu quả hơn. Những tác động đó sẽ giúp học sinh tăng thêm tình yêu với môn học, với lập trình. Sự thành công của hệ thống cũng là căn cứ để phát triển các hệ thống tương tự và tốt hơn hỗ trợ quá trình dạy học, đây là một điều hết sức ý nghĩa và có thể thực hiện được. Phần tiếp theo của luận văn được cấu trúc như sau: Chương 2 trình bày về các cơ sở lí thuyết hoặc công nghệ được sử dụng trong luận văn; Chương 3 mô tả chi tiết về các giải pháp giải quyết bài toán; Cách cài đặt công cụ và các kết quả thực nghiệm trên các ví dụ cụ thể được trình bày ở Chương 4; Cuối cùng là Chương 5 tổng kết và hướng nghiên cứu tiếp theo của luận văn. 4
Chương 2. Kiến thức nền tảng Vấn đề xác định vị trí lỗi đặc biệt được quan tâm trong thời gian gần đây với hàng trăm nghiên cứu. Báo cáo nghiên cứu về các phương pháp định vị lỗi [8] của nhóm tác giả W. Eric Wong đã tổng hợp vấn đề này và là một cơ sở tham khảo của luận văn ở mục này. Học viên cũng đi nghiên cứu các kiến thức nền tảng về gợi ý sửa lỗi, nội dung đó sẽ được trình bày cụ thể trong Mục 2.2. 2.1. Các phương pháp xác định vị trí lỗi Xác định vị trí lỗi (định vị lỗi) là khâu quan trọng trong việc gỡ lỗi, là việc làm tốn nhiều thời gian. Trước đây việc này thường được làm thủ công, dựa trên kinh nghiệm của lập trình viên. Định vị lỗi giúp giới hạn không gian tìm kiếm, việc sửa lỗi sẽ tập trung vào các câu lệnh có khả năng gây lỗi cao giúp tăng hiệu quả sửa lỗi. Ngày nay, yêu cầu phát triển phần mềm với số lượng và quy mô lớn thì tự động hóa một phần hoặc tự động hóa hoàn toàn khâu định vị lỗi là cần thiết. Có nhiều phương pháp định vị lỗi truyền thống và hiện đại, trong các khoảng thời gian khác nhau và yêu cầu khác nhau các phương pháp định vị lỗi đã có những hiệu quả nhất định. 2.1.1. Phương pháp định vị lỗi truyền thống Một trong số những phương pháp truyền thống để định vị lỗi là Logging [7]. Phương pháp Logging chèn các chỉ thị vào chương trình để theo dõi giá trị các biến và các thông tin trạng thái khác của chương trình. Các thông tin này được ghi vào nhật ký theo dõi (log file). Khi phát hiện các hành vi bất thường, các nhà phát triển sẽ kiểm tra nhật ký chương trình và thông tin thời gian chạy để xác định nguyên nhân lỗi. Phương pháp Breakpoint [8] cho phép người dùng tạm dừng (ngắt) chương trình ở bất kỳ điểm nào để kiểm tra tình trạng biến hoặc giá trị biểu thức có hợp lí hay không. Điểm ngắt cũng có thể được kích hoạt khi một điều kiện nào đó xảy ra, ví dụ thay đổi giá trị biểu thức được đánh dấu. Khi chương trình được ngắt, người dùng có thể tiến hành sửa đổi giá trị các biến và chạy lại để theo dõi sự thay đổi tiếp theo. Quá trình ngắt và theo dõi giá trị biến và trạng thái chương trình này cho phép ta xác định các vị trí gây lỗi. Phương pháp này đã được ứng dụng trong công cụ gỡ lỗi GNU GDB [15] và Microsoft Visual Studio Debugger [16]. Bên cạnh các phương pháp trên có thể kể tới phương pháp sử dụng hồ sơ phân tích (Profiling), hay Assertions (theo dõi giá trị các lệnh ràng buộc) v.v. Các phương pháp định vị lỗi truyền thống không hiệu quả trong việc xác định nguyên nhân gốc rễ của lỗi nên các phương pháp này không được đánh giá cao và chưa đáp ứng được với những phần mềm có quy mô lớn như hiện nay [8]. 5
2.1.2 Phương pháp định vị lỗi hiện đại Một số phương pháp định vị lỗi hiện đại có thể kể tới như: định vị lỗi dựa trên lát cắt, định vị lỗi quang phổ, định vị lỗi dựa trên thống kê, định vị lỗi dựa trên trạng thái chương trình, định vị lỗi dựa trên học máy, định vị lỗi dựa trên học máy, định vị lỗi dựa trên mô hình, v.v. Chúng đang được sử dụng phổ biến trong các công cụ sửa lỗi tự động và bán tự động. Các phương pháp này nghiên cứu mối quan hệ giữa nguyên nhân (lỗi chương trình) và hiện tượng (kết quả thực thi chương trình không thành công), có sự tính toán dựa trên lí thuyết về xác suất thống kê để đánh giá.  Phương pháp Slicing Slicing [17] hay còn gọi là phương pháp định vị lỗi dựa trên lát cát. Slicing phương pháp cho phép làm đơn giản hóa chương trình bằng cách cắt các câu lệnh thành lát cắt và xoá các câu lệnh thừa sao cho ý nghĩa của chương trình không thay đổi. Các lát cắt sẽ được cắt dựa theo các biến của chương trình, nghĩa là mỗi lát cắt sẽ chứa các dòng lệnh liên quan đến một biến được định trước, các câu lệnh có liên quan đến biến khác sẽ bị xóa bỏ. Mỗi lát cắt bao gồm các câu lệnh phụ thuộc vào nhau, đồng thời giữa các lát cắt không có sự phụ thuộc lẫn nhau. Việc phân chia này giúp giảm thiểu không gian tìm kiếm lỗi. Bởi vì lỗi sẽ nằm ở một vị trí bất kỳ trong chương trình, vị trí này sẽ nằm trong một lát cắt. Do giữa hai lát cắt không có sự phụ thuộc lẫn nhau nên vị trí lỗi chỉ thuộc một lát cắt độc lập. Điều này sẽ giới hạn việc tìm kiếm lỗi ở trong một lát cắt thay vì toàn bộ chương trình. Với phương pháp Slicing, việc định vị lỗi được xác định tới cả khối lệnh chứa câu lệnh lỗi chứ không cụ thể tới từng câu lệnh.  Phương pháp Spectrum Phương pháp Spectrum [8] còn gọi là phương pháp định vị lỗi quang phổ. Đây là phương pháp được nghiên cứu nhiều nhất trong thời gian gần đây, chiếm 35% những bài báo nghiên cứu [8]. Định vị lỗi bằng phương pháp quang phổ là phương pháp dựa trên các đặc tính cụ thể của chương trình. Với phương pháp quang phổ điểm số nghi ngờ được đánh giá đến từng câu lệnh thay vì từng khối lệnh như trong phương pháp Slicing. Trước tiên chương trình được kiểm tra với các ca kiểm thử. Có hai loại ca kiểm thử tham gia vào quá trình định vị lỗi đó là ca kiểm thử tiêu cực (Negative Test - NT) và ca kiểm thử tích cực (Positive Test - PT). PT là những ca kiểm thử không phát hiện ra lỗi của chương trình bị lỗi, đó là trường hợp thử nghiệm mà chương trình vượt qua được. NT là ca kiểm thử gây ra lỗi cho chương trình. Khi chương trình chạy qua bộ ca kiểm thử bao gồm cả NT và PT, độ bao phủ của chương trình với mỗi ca kiểm thử được ghi lại. Đó là các câu lệnh của chương trình tham gia vào quá trình thực thi mỗi ca kiểm thử. Nhìn chung, khi một câu lệnh nằm trên đường thực thi của NT thì khả năng bị lỗi của câu lệnh đó được đánh giá cao hơn so với một câu lệnh nằm trên đường đi của PT. Một câu lệnh không nằm trên đường thực thi của bất kỳ ca kiểm thử nào thì câu lệnh đó không có lỗi. 6
Sau khi xác định được độ bao phủ của toàn bộ ca kiểm thử trên các câu lệnh của chương trình thì tính toán điểm nghi ngờ cho từng câu lệnh bằng công thức quang phổ. Có nhiều công thức quang phổ để tính toán điểm số nghi ngờ cho câu lệnh như Ochiai, Tarantula, Ample, GenProg, Jaccard, v.v. So về tính hiệu quả, công thức Ochiai đang được đánh giá tốt hơn Tarantula [18]. Một số công cụ mã nguồn mở được phát triển dựa trên phương pháp định vị lỗi quang phổ như công cụ Zoltar, Gcov, Gzoltar, v.v. Gzoltar [14] tích hợp công thức quang phổ Ochiai. Gzoltar cung cấp các API hỗ trợ việc định vị lỗi bằng cách đọc vào tất cả các package của mã nguồn dự án và tất cả các tệp mã nguồn chứa ca kiểm thử, rồi tự động phân tích đánh giá điểm số nghi ngờ cho từng câu lệnh. 2.2. Các phương pháp gợi ý sửa lỗi Một số nghiên cứu thực nghiệm [19] [20] chỉ ra rằng có từ 3% đến 7% mã nguồn được khảo sát có thể được sửa chữa bằng chính những câu lệnh được tìm thấy trong mã nguồn lỗi, đây là tư tưởng chính để phát triển các chương trình sửa lỗi tự động dựa trên thuật toán di truyền. Dựa trên kết quả kiểm tra chương trình với các ca kiểm thử, các câu lệnh hoặc khối lệnh được gắn nhãn với các mức độ khác nhau như có khả năng gây lỗi cao, khả năng gây lỗi thấp, không có lỗi, tương ứng với kết quả số ca kiểm thử vượt qua hay thất bại khi đi qua câu lệnh đó. Chương trình tập trung vào sửa lỗi những câu lệnh có khả năng gây lỗi cao. Để sửa lỗi, chương trình thực hiện thay thế câu lệnh được gắn nhãn không có lỗi cho câu lệnh được gắn nhãn có khả năng gây lỗi cao, sau đó thử lại với bộ ca kiểm thử để đánh giá. Quá trình này được thực hiện nhiều lần với các lựa chọn thử thay thế khác nhau cho đến khi sửa được chương trình. Tư tưởng này được áp dụng trong phát triển công cụ jGenProg [21]. Bên cạnh đó còn có các phương pháp gợi ý sửa khác như sửa lỗi dựa trên ngữ nghĩa [22], sửa lỗi bằng phương pháp học máy [23]. Các phương pháp gợi ý sửa lỗi trên đòi hỏi cài đặt tương đối phức tạp nhưng kết quả sửa lỗi cũng chưa nổi bật. Phần dưới đây trình bày phương pháp gợi ý sửa lỗi dựa trên bài làm của học sinh, cách làm này khá thô sơ, dễ cài đặt mà phù hợp và hiệu quả với bài toán đặt ra. Với định hướng gợi ý sửa lỗi cho học sinh dựa trên các bài làm đúng tương tự, học viên đã nghiên cứu các công cụ về kiểm tra mã nguồn tương đồng để áp dụng cho trường hợp này. Việc kiểm tra mã nguồn tương đồng thường được ứng dụng trong việc kiểm tra và phát hiện đạo văn. Tuy nhiên, từ góc độ bài toán này việc kiểm tra độ tương đồng nhằm mục đích tìm kiếm chương trình đúng trong bộ sưu tập có mức độ tương đồng cao nhất với chương trình đang lỗi của học sinh. Chương trình đúng này sẽ được đưa ra làm mẫu để học sinh tự đối chiếu và sửa chữa chương trình của mình. Tỉ lệ tương đồng càng cao, gợi ý học sinh càng hiệu quả. Do đó nghiên cứu các công cụ hỗ trợ gợi 7
ý chương trình đúng trong bài toán này chính là nghiên cứu các công cụ kiểm tra mã nguồn tương đồng. Trong mục này học viên sẽ nghiên cứu cụ thể về các nhóm giải pháp chính, so sánh và kết luận phương pháp phù hợp nhất cho bài toán. Các nội dung trong phần này được tham khảo trong báo cáo của tác giả Lutz Prechelt về kiểm tra tương đồng với công cụ JPlag [24] và báo cáo so sánh cấu trúc và hệ thống đếm thuộc tính của phần mềm phát hiện nghi ngờ đạo văn [25] của nhóm tác giả Kristina L. Verco và Michael J. Wise. Phương pháp kiểm tra tương đồng ra đời sớm nhất so sánh dựa trên vectơ đặc trưng. Một chương trình được đặc trưng bởi n thông số, mỗi thông số được ánh xạ tới một điểm trong không gian n chiều. Các điểm này càng gần nhau thể hiện các tài liệu có độ tương đồng cao. Phương pháp này xác định hai tài liệu là sao chép nếu tất cả các thông số đặc trưng là trùng nhau. Ban đầu Halstead [26] đề xuất bốn thông số cần so sánh là số lượng toán tử duy nhất, số lượng toán hạng duy nhất, tổng số toán tử, tổng số toán hạng. Ottenstein đã sử dụng các thông số trên để phát triển chương trình phát hiện đạo văn Fortran [27]. Sau này Donaldson và cộng sự [28] đã cải tiến các hệ thống với việc bổ sung thêm nhiều thuộc tính so sánh khác để tăng hiệu quả. Phương pháp này bỏ qua các đặc trưng về cấu trúc, vì thế nếu các chương trình sử dụng cấu trúc tương đương nhau nhưng chỉ cần thay đổi tên biến hoặc toán hạng của biểu thức thì việc kiểm tra tương đồng dễ bị lừa hoặc phán đoán sai, do đó hiệu quả của phương pháp chỉ được đánh giá ở mức độ trung bình [25]. Ngày nay, phương pháp kiểm tra tương đồng mã nguồn có những cải tiến hơn, cho phép vừa kết hợp vectơ đặc trưng vừa tính đến cấu trúc, gọi là phương pháp Tokenization [29]. Phương pháp này chia nhỏ mã nguồn thành các thẻ (Tokens), trong khi chia sẽ bỏ qua các thông tin thụt lề, ngắt dòng, nhận xét, dòng trắng, v.v. là những thông tin dễ thay đổi và không ảnh hưởng lớn tới cấu trúc chương trình. Sau đó, các thẻ này sẽ được so sánh với nhau, tìm ra đoạn chung lớn nhất. Các thông số được đưa vào các công thức của thuật toán để tính ra tỉ lệ tương đồng. Có nhiều công cụ hiện đại được phát triển dựa trên phương pháp Tokenization như Plague, Sim , YAP3, MOSS, JPlag, v.v. Qua các nghiên cứu và so sánh, có thể thấy rằng tính hiệu quả của JPlag được đánh giá cao, bằng hoặc hơn so với công cụ MOSS (một công cụ thương mại trên thị trường) và tốt hơn so với YAP3 [24]. JPlag sử dụng thuật toán Greedy-String-Tiling [30], có khả năng so sánh lượng dữ liệu lớn một cách nhanh chóng. JPlag có giao diện trực quan giúp hiển thị kết quả so sánh song song và là một phần mềm mã nguồn mở nên thích hợp để tích hợp trong công cụ của bài toán này. Trên thực tế các chương trình học sinh có thể đặt tên biến khác nhau, cách viết câu lệnh cũng khác nhau, nếu chỉ so sánh từ với từ thì không có nhiều khả năng có hai chương trình giống nhau, càng không có khả năng chương trình đúng giống (tương đồng cao) với chương trình đang có lỗi. Điều này càng khẳng định so sánh mã nguồn dựa trên phương 8
pháp Tokenization như JPlag là phù hợp cho định hướng của bài toán. Ngoài ra còn một số công cụ khác tương tự đang được sử dụng trên thị trường nhưng tài liệu học thuật về sản phẩm khó tìm kiếm và không có các đánh giá về tính hiệu quả nên trong học viên không tiếp tục đi sâu vào tìm hiểu các công cụ này. 2.3. Lí thuyết về xây dựng các ca kiểm thử Đầu vào của mô-đun định vị lỗi là chương trình nguồn cùng với bộ ca kiểm thử tương ứng để kiểm tra tính chính xác của chương trình. Để định vị lỗi chương trình cần có một bộ các ca kiểm thử đủ tốt. Do đó việc xây dựng các bộ ca kiểm thử phải đảm bảo các tiêu chí nhất định trong kiểm thử phần mềm. Nội dung được trình bày trong phần lí thuyết này được tham khảo từ giáo trình kiểm thử phần mềm [31] của nhà xuất bản Đại học Quốc gia Hà Nội. Trong bài toán về xác định các ca kiểm thử như mô tả trong Hình 2.1 ta thấy có hai tập hành vi của chương trình cần kiểm thử. Coi S là tập các hành vi được đặc tả và P là tập các hành vi được lập trình. Khi đó phần giao giữa S và P là phần đúng đắn (tập các hành vi vừa được đặc tả vừa được lập trình). Để kiểm tra chương trình, việc xây dựng các ca kiểm thử phải đảm bảo kiểm tra được tất cả các trường hợp có thể xảy ra. Gọi T là tập hợp các ca kiểm thử cần thiết. Ở Hình 2.2 (a) và Hình 2.2 (b) tập T chỉ bao quát được các hành vi được đặc tả và được kiểm thử hoặc được lập trình và được kiểm thử. Ở cả hai trường hợp trên việc kiểm thử đều chưa đầy đủ. Việc xây dựng các ca kiểm thử cần đảm bảo vừa kiểm tra được các hành vi được đặc tả và được kiểm thử; được lập trình và được kiểm thử như Hình 2.2 (c). Điều này tương đương với nhiệm vụ xây dựng bộ các ca kiểm thử theo cả phương pháp kiểm thử hộp đen (kiểm thử chức năng) và kiểm thử hộp trắng (kiểm thử cấu trúc). Hình 2.1. Tập hành vi của chương trình [31] Luận văn hướng tới giải quyết bài toán sửa lỗi cho các chương trình Java của học sinh. Học sinh mới học lập trình cơ bản nên các bài toán thường đơn giản, không có nhiều chức năng. Do đó để đơn giản hóa bài toán, việc xây dựng bộ các ca kiểm thử sẽ chỉ quan tâm tới kiểm thử hộp trắng, cụ thể là kiểm thử dòng điều khiển với độ bao phủ cấp 3 (C3) hay độ bao phủ câu lệnh con. 9