Luận văn tốt nghiệp cao học Phát triển phương pháp top-down và hệ thống ngôn ngữ mở cho việc phát hiện sao cắp chương trình nguồn LỜI CAM ĐOAN Tôi cam đoan rằng, ngoại trừ những kết quả tham khảo từ các công trình khác như đã ghi rõ trong luận văn, các công việc được trình bày trong luận văn là do chính tôi thực hiện và chưa có phần nội dung nào của luận văn này được nộp để lấy một bằng cấp ở trường này hay trường khác Sinh viên thực hiện Phan Thị Thu Thảo 1 Luận văn tốt nghiệp cao học Phát triển phương pháp top-down và hệ thống ngôn ngữ mở cho việc phát hiện sao cắp chương trình nguồn LỜI CẢM ƠN Đầu tiên, con xin bày tỏ lòng biết ơn vô hạn đến Cha Mẹ và các Anh Chị đã ủng hộ, tạo mọi điều kiện để con có thể học tập và hoàn thành tốt luận văn. Tôi xin gửi đến TS.Cao Hoàng Trụ lòng biết ơn chân thành nhất. Cám ơn Thầy đã nhiệt tình hướng dẫn từ phương pháp nghiên cứu đến việc xây dựng mô hình; hiện thực hệ thống. Tôi cũng xin bày tỏ lòng cảm ơn sâu sắc nhất đến tất cả các Thầy Cô trong khoa Công Nghệ Thông Tin đã giảng dạy và giúp đỡ tôi trong thời gian học tập tại trường, đặc biệt chủ nhiệm cao học ngành CNTT, TS.
Dương Tuấn Anh. Cám ơn Guido Malpohl đã cung cấp account sử dụng JPlag để tôi có thể thử nghiệm và so sánh kết quả với hệ thống của mình. Vô cùng cảm ơn những lời khuyên của anh trong việc chọn tập dữ liệu để thử nghiệm. Xin cảm ơn tất cả bạn bè của tôi, những người đã chia sẽ và giúp đỡ tôi trong cuộc sống cũng như trong học tập.
Cuối cùng, tôi xin gửi đến tất cả mọi người những lời chúc tốt đẹp nhất. 2 Luận văn tốt nghiệp cao học Phát triển phương pháp top-down và hệ thống ngôn ngữ mở cho việc phát hiện sao cắp chương trình nguồn TÓM TẮT Việc sao cắp trong các trường Đại Học đang ngày càng phổ biến và đang là một vấn đề nghiêm trọng cần giải quyết ([1],[2]). Sinh viên có thể sao cắp từ các bài viết cho đến mã nguồn của chương trình. Do đọc mã nguồn của người khác là một công việc khá khó khăn và do sự phức tạp của bản thân mã nguồn nên việc sao cắp mã nguồn chương trình khó có thể phát hiện bằng mắt thường hơn so với việc sao cắp các bài viết.
Vì vậy các trường Đại Học đều cần có một chương trình phát hiện sao cắp mã nguồn, cụ thể là các bài thi viết bằng ngôn ngữ lập trình của sinh viên. Những hệ thống phát hiện sao cắp trước đây đều sử dụng kỹ thuật attribute- counting ([4],[5]) nhưng hầu hết các hệ thống phát hiện sao cắp khá thành công hiện nay như YAP3 ([8]), Plague ([6]), Sim ([7]) đều được xây dựng dựa trên phương pháp comparing structure ([9]). Các hệ thống này đều sử dụng giải thuật GST ([10]) so sánh những chuỗi token đại diện cho cấu trúc chương trình. Những hệ thống này không đòi hỏi sự so trùng tuyệt đối mà chỉ tìm kiếm độ tương tự của các chuỗi token.
Phương pháp này có hiệu suất và độ chính xác cao hơn so với phương pháp trước đây là attribute-counting. Tuy nhiên khi chiều dài chuỗi token tăng thì thời gian tìm kiếm cũng tăng lên đáng kể, đồng thời chuỗi token không thích hợp để đại diện cho cấu trúc của chương trình. Để tăng hiệu suất và độ chính xác, chúng tôi đề xuất phương pháp top-down trong việc tìm kiếm các chương trình có khả năng sao cắp. Phương pháp này so sánh các chương trình theo ba cấp: cấp module, cấp lưu đồ và cấp mệnh đề; tương tự như cách tự nhiên người ta dùng để pháp hiện sao cắp trong các chương trình.
Việc hiện thực phương pháp này dựa trên một phần trong luận văn tốt nghiệp ([11]) và những thư viện như ANTLR ([18]), VFLIB ([19]). Hệ thống được thử nghiệm và so sánh với hai hệ thống hiện tại là Sim ([7]) và JPlag ([20]) và trong một số trường hợp đã đạt được độ chính xác cao hơn. 3 Luận văn tốt nghiệp cao học Phát triển phương pháp top-down và hệ thống ngôn ngữ mở cho việc phát hiện sao cắp chương trình nguồn MỤC LỤC LỜI CAM ĐOAN. 4 DANH MỤC HÌNH .1 Phạm vi, động cơ thúc đẩy và mục tiêu .2 Những đóng góp chính của luận văn .3 Sơ lược cấu trúc luận văn.
9 TỔNG KẾT CÁC CÔNG TRÌNH LIÊN QUAN .2 Phương pháp Attribute-counting .3 Phương pháp Structure-metric .4 So sánh phương pháp Structure-metric và Attribute-counting. 16 PHƯƠNG PHÁP TOP-DOWN VÀ HỆ THỐNG NGÔN NGỮ MỞ .1 Tổng quát về phương pháp Top-Down .2 Phát hiện sao cắp ở cấp module.3 Phát hiện sao cắp ở cấp lưu đồ .4 Phát hiện sao cắp ở cấp phát biểu.5 Hệ thống ngôn ngữ mở. 37 THIẾT KẾ VÀ HIỆN THỰC .1 Cấu trúc hệ thống: .2 Bộ đặc tả .3 Bộ phân tích cú pháp .4 Bộ so sánh, tìm các bài sao cắp .5 Một số giải thuật sử dụng:. 48 4 Luận văn tốt nghiệp cao học Phát triển phương pháp top-down và hệ thống ngôn ngữ mở cho việc phát hiện sao cắp chương trình nguồn THỬ NGHIỆM, ĐÁNH GIÁ VÀ KẾT LUẬN .1 Thử nghiệm đánh giá kết quả đạt được .2 Tổng kết và đề nghị.
63 TÀI LIỆU THAM KHẢO. 83 5 Luận văn tốt nghiệp cao học Phát triển phương pháp top-down và hệ thống ngôn ngữ mở cho việc phát hiện sao cắp chương trình nguồn DANH MỤC HÌNH Hình 2.1: So sánh của Whale về độ chính xác giữa phương pháp Attribute-counting và Structure-metric .2: So sánh của Whale về hiệu suất giữa phương pháp Attribute-counting và Structure-metric .3: So sánh của Wise về hiệu suất và độ chính xác giữa phương pháp Attribute-counting và Structure-metric.1: Đồ thị triệu gọi .2: Cấu trúc tĩnh được chuyển thành đồ thị lồng khối .3: So sánh cấu trúc động của chương trình sao cắp và chương trình gốc .4: Lưu đồ được chuyển thành chuỗi lưu đồ .5: Vòng lặp khác nhau nhưng lưu đồ đẳng cấu .6: Phát biểu điều kiện khác nhau nhưng lưu đồ đẳng cấu.7: Sử dụng cấu trúc điều khiển tương đương, chèn các phát biều gán, gọi hàm vào khối phát biểu S.8: Chèn thêm khối phát biểu S vào giữa hai phát biều điều khiển.1: Sơ đồ DFD ngữ cảnh hệ thống .2: Sơ đồ DFD mức 0 của hệ thống .3: Sơ đồ DFD mức 1 của hệ thống .4: Cấu trúc thư mục sinh ra từ bộ phân tích cú pháp.5: Giao diện chương trình chính .6: Cửa sổ hội thoại để chọn thư mục chứa các bài làm cần kiểm tra.7: Hiển thị cặp đồ thị triệu gọi với các node được tô màu tương ứng.8: Hiển thị cặp đồ thị lồng khối với các node được tô màu tương ứng.9: Hiển thị cặp lưu đồ với các node được tô màu tương ứng.58 6 Luận văn tốt nghiệp cao học Phát triển phương pháp top-down và hệ thống ngôn ngữ mở cho việc phát hiện sao cắp chương trình nguồn 1 GIỚI THIỆU 1.1 Phạm vi, động cơ thúc đẩy và mục tiêu Sao cắp là việc sử dụng lại một phần hoặc toàn bộ tác phẩm của người khác mà không được sự đồng ý của tác giả hoặc không cho biết nguồn tài liệu được sử dụng. Với sự phát triển mạnh mẽ của Internet, các công cụ tìm kiếm trên WWW và các công cụ xử lý văn bản mạnh cũng như các ngân hàng luận văn, “term paper mills” ([3]) việc sao cắp trong các trường Đại Học đang ngày càng phổ biến và đang là một vấn đề nghiêm trọng cần giải quyết. Theo thống kê ([1]) , 35% sinh viên thừa nhận rằng họ thường xuyên sao cắp, 40% thỉnh thoảng làm như vậy và 19% sinh viên trả lời là “ít khi”.
Điều đó có nghĩa là 94% sinh viên ít nhất một lần sử dụng biện pháp gian lận đó. Tình trạng sao cắp trong các trường Đại Học không chỉ dừng lại ở đó. Hơn 50% sinh viên được phỏng vấn cho rằng tỉ lệ sao cắp đang gia tăng mạnh mẽ trong những năm gần đây. Vấn đề sao cắp không chỉ giới hạn trong các văn bản viết mà còn xuất hiện khá thường xuyên trong mã nguồn; ở đó sinh viên copy toàn bộ hoặc một phần mã nguồn của bàn bè, các sinh viên khóa trước hoặc từ các chương trình trong tài liệu, sách… Không may là do việc đọc mã nguồn của người khác viết là một việc khá khó khăn và do sự phức tạp bản thân mã nguồn nên việc sao cắp trong ngôn ngữ lập trình khó phát hiện hơn so với ngôn ngữ tự nhiên.
Vì vậy cần phải có một phần mềm phát hiện sao cắp để hổ trợ giảng viên trong việc phát hiện ra các bài làm có khả năng gian lận. Một hệ thống như vậy không những giúp cho giáo viên chấm bài chính xác hơn, đánh giá đúng hơn năng lực của sinh viên mà còn góp phần làm giảm tỉ lệ sao cắp trong các trường Đại Học, nâng cao ý thức tôn trọng tác quyền, làm trong sạch đạo đức và làm cơ sở để thực hiện những biện pháp trừng phạt đối với những hành vi gian lận trong thi cử. 7 Luận văn tốt nghiệp cao học Phát triển phương pháp top-down và hệ thống ngôn ngữ mở cho việc phát hiện sao cắp chương trình nguồn Mục tiêu của luận văn này là nghiên cứu phương pháp top-down và hệ thống ngôn ngữ mở áp dụng cho hệ thống hỗ trợ phát hiện sao cắp trong các mã nguồn của sinh viên. Phương pháp top-down là phân tích và so sánh mã nguồn của các chương trình từ cấp độ tổng quát nhất là cấp module, sau đó đến cấp lưu đồ và cuối cùng là cấp phát biểu.
Bằng cách sử dụng các cấu trúc đặc trưng của mã nguồn, việc so sánh sẽ đạt được kết quả chính xác hơn. Ở mỗi cấp, số lượng các cặp chương trình có khả năng sao cắp sẽ bị giảm xuống, đồng thời hệ thống chỉ tập trung phân tích so sánh ở những phần của mã nguồn có khả năng sao cắp nhiều nhất, điều này sẽ làm tăng hiệu xuất của việc so sánh. Mục đích việc xây dựng một hệ thống ngôn ngữ mở là để khi sử dụng hệ thống cho một ngôn ngữ khác chúng ta không phải phát triển lại hệ thống từ đầu. Bằng cách này chi phi và thời gian mở rộng hệ thống sẽ giảm đáng kể.
Bên cạnh việc nghiên cứu phương pháp, chúng tôi còn phát triển những giải thuật để giải quyết những bài toán trong phương pháp trên, đồng thời xây dựng chương trình cho phần nghiên cứu lý thuyết.