CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN ĐÁNH GIÁ MỨC ĐỘ TƯƠNG TỰ GIỮA CÁC MÃ NGUỒN.1: Không gian ROC Đường chéo nét đứt từ tọa độ (0,0) tới (1,1) đại diện cho phép dự đoán ngẫu nhiên, chia không gian ROC thành 2 phần theo 2 chiều hướng tốt hơn và xấu hơn. Tức là những phép dự đoán cho kết quả nằm phía trên đường chéo được đánh giá là có kết quả tốt hơn so với các phép dự đoán cho kết quả nằm dưới đường chéo, phép đo có kết quả càng gần với đỉnh trên bên trái (0,1) thì càng tiệm cận tới phép đo “hoàn hảo”. Tập hợp kết quả các lần dự đoán của một hệ thống dự đoán sẽ tạo thành một đường cong trong không gian ROC, thường được gọi là “đường cong ROC”. 10 Hình CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN ĐÁNH GIÁ MỨC ĐỘ TƯƠNG TỰ GIỮA CÁC MÃ NGUỒN.2: Đường cong ROC Một số tính chất của đường cong ROC: Đường cong càng đi dọc theo biên trái và rồi đi dọc theo biên phía trên của không gian ROC, thì chứng tỏ kết quả kiểm tra càng chính xác.
Đường cong càng tiến tới thành đường chéo 45 độ trong không gian ROC, thì độ chính xác của kiểm tra càng kém. Hệ số góc của đường thẳng tiếp tuyến tại một điểm cutpoint cho ta tỉ lệ likelihood ratio (LR) của giá trị cutpoint đó của bài kiểm tra. Diện tích phía dưới đường cong, giới hạn trong không gian ROC, là thước đo cho độ chính xác của bài kiểm tra, chẳng hạn: 1 là tối ưu, 0. Phần diện tích này có ý nghĩa là thước đo cho khả năng phân biệt (discrimination) tốt hay không.
Dựa vào tính chất trên, chúng ta có thể so sánh kết quả của những chương trình đánh giá mức độ tương tự bằng cách vẽ đường cong ROC tương ứng với mỗi chương trình, chương trình nào cho đường cong ROC nằm trên thì được đánh giá có khả năng dự đoán chính xác hơn. Cây cú pháp trừu tượng (AST, abstract syntax tree) 1.1 Tổng quan về các công nghệ so sánh mã nguồn phổ biến Trong giai đoạn đầu nghiên cứu về vấn đề sao chép, công nghệ chủ yếu để phát hiện ra một bản sao là dựa trên nội dung của văn bản. Phương pháp này rất đơn giản là xác định xem hai tệp tương tự bằng cách so sánh các giá trị được tính toán của các tệp. Nhưng giải pháp này chỉ có thể phát hiện khi sao chép mà không có sửa đổi.
Với sự phát triển của công nghệ, nhiều nghiên cứu trong lĩnh vực này đã đề xuất rất nhiều thuật toán và phương án khác nhau. Đến nay có nhiều phần mềm, công cụ giúp phân tích và phát hiện trùng lặp trong mã nguồn, tuy nhiên về cơ bản đều thuộc một trong 4 trường phái sau: Dựa trên phân tích văn bản thuần túy (string-based): Mã nguồn được chuyển thành các chuỗi liên tiếp ký tự. Hai mã nguồn được coi là tương tự nhau nếu chúng bao gồm các chuỗi ký tự giống nhau. Thuật toán chính được sử dụng trong công nghệ này là thuật toán tìm chuỗi con dài nhất (LCS).
Nhưng rõ ràng thuật toán có những hạn chế, chỉ khi tất cả các chuỗi giống nhau, hai mã nguồn mới có thể được coi là tương tự. Dựa trên phân tích chuỗi ký tự đại diện (token-based): Công nghệ này được cải tiến từ việc phân tích mã nguồn dựa trên văn bản thuần túy trình bày phía trên. Mã nguồn chương trình lúc này được tách từ thành chuỗi các token, sau đó thực hiện quét và kiểm tra các chuỗi token trùng nhau để xác định khả năng xảy ra lặp, sao chép mã nguồn. So với hướng tiếp cận trên, hướng tiếp cận này mạnh hơn trong việc phát hiện các đoạn mã nguồn lặp cho dù mã nguồn đã được sửa chữa đôi chút.
Các công cụ phát hiện sao chép mã nguồn tiêu biểu theo trường phái này gồm: CP-Mine, CCFinder, Jplag. Tuy nhiên các công cụ này đều có nhược điểm không thể phát hiện khi mã nguồn có sự thay đổi như thay đổi tên hàm, biến, thứ tự các đoạn code độc lập, hay chèn thêm các đoạn code vô nghĩa. Dựa trên cấu trúc cây (tree-based): Đây là công nghệ mới được đề cập và phát triển nhanh trong những năm gần đây. Việc so sánh các mã nguồn dựa trên cấu trúc của nó là hướng đi rất hợp lý, khi mà nó có thể bằng cách này hay cách khác để loại bỏ sự ảnh hưởng bởi những thao tác như: đổi tên hàm, tên biến, thứ tự code… Do ưu điểm của phương pháp tiếp cận này, nên các thuật toán trong luận văn này tập trung vào việc phân tích mã nguồn dựa trên cấu trúc cây.
12 Dựa trên biểu đồ phụ thuộc (Program Dependence Graph - PDG): Một số nghiên cứu chỉ ra rằng các thủ thuật sao chép mã nguồn không làm thay đổi nhiều đối với biểu đồ phụ thuộc của mã nguồn gốc. Do đó việc tiếp cận PDG trong phân tích đánh giá mức độ tương tự giữa các mã nguồn là một ý tưởng rất thú vị. Trong khuôn khổ của luận văn này, tác giả không trình bày về các giải thuật liên quan đến phương pháp tiếp cận này.2 Khái niệm về cây cú pháp trừu tượng (AST, abstract syntax tree) Trong ngành khoa học máy tính, cây cú pháp trừu tượng (AST, abstract syntax tree), là cấu trúc dữ liệu được sử dụng rộng rãi trong trình biên dịch, do thuộc tính đại diện cho cấu trúc của mã chương trình. AST thường là kết quả của giai đoạn phân tích cú pháp của trình biên dịch [11].
AST là cấu trúc cây mà các nút gốc của cây được gán nhãn bằng các toán tử và các nút là của cây là các toán hạng. Trong các công đoạn của chương trình dịch, cây AST này được dùng trong bộ phân tích cú pháp như là một trung gian giữa cây phân tích cú pháp (concrete syntax tree) và cấu trúc dữ liệu. Cây cú pháp trừu tượng khác với cây phân tích cú pháp là ở chỗ nó không chỉ quan tâm đến cú pháp mà còn quan tâm đến ngữ nghĩa của chương trình. Hãy cùng xem xét ví dụ đoạn mã nguồn sau (ngôn ngữ C++): void fun1(){ int a = 2; int b = 5; fun2(a, b); } Về cơ bản đoạn mã nguồn này có cây AST như sau: 13 Hình CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN ĐÁNH GIÁ MỨC ĐỘ TƯƠNG TỰ GIỮA CÁC MÃ NGUỒN.3: Cây cú pháp trừu tượng của mã nguồn hàm func 1.3 Các phần mềm sinh ra cây cú pháp AST Mỗi ngôn ngữ lập trình có những công cụ complier khác nhau (ví dụ Java có Java Complier Complier – JavaCC hoặc JJTree, Javascript có JIT, C++ có GCC hoặc Clang).
Tương ứng với mỗi công cụ này, sẽ có các công cụ xây dựng cây cú pháp AST khác nhau. Ngoài ra hiện nay trên internet đã có những công cụ trực tuyến cho phép xem trực tiếp cây cú pháp của một đoạn mã nguồn ngay trên trình duyệt web tại địa chỉ sau: https://astexplorer. Công cụ này hỗ trợ nhiều ngôn ngữ lập trình như PHP, Python, Lua, Javascript. Trong phạm vi luận văn này, do chỉ tập trung vào ngôn ngữ C++ nên chọn lựa trình biên dịch Clang trong bộ khung biên dịch LLVM để phục vụ cho việc xây dựng cây AST từ các mã nguồn viết bằng ngôn ngữ C++.
Dưới đây là một số thông tin tổng quan về LLVM và Clang.4 Tổng quan về LLVM (Low-Level Virtual Machine) LLVM là một bộ khung biên dịch (compiler framework) được sử dụng để tối ưu hóa mã cho nhiều ngôn ngữ lập trình khác nhau. Nó cung cấp những công cụ mạnh mẽ để xây 14 dựng phần front-end (parser, lexer) cũng như phần backend (phần chuyển phần code trung gian LLVM sang mã máy), cho các ngôn ngữ lập trình mới [12]. Xuất phát từ khái niệm Low-Level Virtual Machine - Máy ảo cấp thấp, LLVM thường được xem là một khung để tạo nên các trình biên dịch được thiết kế để hỗ trợ phân tích và chuyển đổi chương trình suốt đời, suốt đời cho các chương trình tùy ý, bằng cách cung cấp thông tin cấp cao để chuyển đổi trình biên dịch tại thời điểm compile-time, link-time, run- time và idle time giữa các lần chạy. LLVM cung cấp những công cụ mạnh mẽ để xây dựng phần front-end (parser, lexer) cũng như phần backend (phần chuyển phần code trung gian LLVM sang mã máy), cho các ngôn ngữ lập trình mới.
LLVM đã được sử dụng để xây dựng nên nhiều trình biên dịch (compiler) của nhiều ngôn ngữ lập trình cấp cao phổ biến hiện nay, ví dụ như C, C++, Python, Java, Ruby, cũng như Objective-C và Swift. Hình CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN ĐÁNH GIÁ MỨC ĐỘ TƯƠNG TỰ GIỮA CÁC MÃ NGUỒN.4: Kiến trúc nền tảng biên dịch LLVM Như được thể hiện trong hình trên, một hệ sinh thái chương trình dịch LLVM gồm 3 phần: Front-end: nhận mã nguồn viết trên các ngôn ngữ lập trình và chịu trách nhiệm thực hiện 3 bước gồm Lexical analysis (phân tích từ tố) - đọc từng ký tự thành các token, syntax analysis (phân tích cú pháp) - Parser chuyển các token ở bước 15 trước thành AST và semantic analysis (phân tích ngữ nghĩa) - kiểm tra các thông tin khác. Đầu ra của Front-end là mã trung gian. Middle-end: được biết đến với cái tên "LLVM Optimizer", sử dụng một ngôn ngữ lập trình cấp thấp gọi là intermediate representation (IR) làm mã trung gian.
IR được sử dụng nhằm mục đích chuyển đổi giữa kết quả của phần Front- end sang Back-end để có thể tạo mã máy. Back-end: chịu trách nhiệm tạo ra mã máy từ mã trung gian cho từng kiến trúc CPU cụ thể. Hình CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN ĐÁNH GIÁ MỨC ĐỘ TƯƠNG TỰ GIỮA CÁC MÃ NGUỒN.5: Luồng xử lý từ frontend middle-end back-end Nhờ thiết kế độc lập của 3 thành phần dạng module, LLVM giúp các nhà phát triển rất dễ hỗ trợ thêm ngôn ngữ front-end mới, cũng như hỗ trợ cho các kiến trúc CPU mới ở phía back-end, ngay cả những kiến trúc không tồn tại ở thời điểm ứng dụng ra đời. Cùng với nhiều công cụ mạnh mẽ khác, dự án LLVM mang đến sức mạnh, tốc độ, an toàn cùng với tiện lợi cho hầu hết các ngôn ngữ hiện đại ngày nay.5 Tổng quan về Clang Clang là một trình biên dịch (compiler front-end) sử dụng cơ sở hạ tầng trình biên dịch LLVM cho các ngôn ngữ lập trình C, C ++, Objective-C và Objective-C ++ [13].
Clang được thiết kế để hoạt động như một sự thay thế cho Bộ trình dịch GNU (GNU Compiler Collection - GCC). Clang được đóng góp và hỗ trợ bởi các tổ chức uy tín như Apple, Microsoft, Google, ARM, Sony, Intel và Advanced Micro Devices (AMD). Đây là 16 phần mềm nguồn mở, với mã nguồn được phát hành theo Giấy phép của Đại học Illinois / NCSA.