CHƯƠNG 1: KIẾN THỨC CƠ SỞ VỀ PHÂN TÍCH CHƯƠNG TRÌNH Trong chương này, tôi sẽ trình bày các khái niệm liên quan đến Phân tích chương trình, cũng như các kỹ thuật khác nhau và các ứng dụng của Phân tích chương trình. Khái niệm và phân loại Phân tích chương trình Theo [7]: “Trong khoa học máy tính, phân tích chương trình là quá trình tự động phân tích hành vi của các chương trình máy tính. 8], dựa vào việc chương trình có được thực hiện hay không, phân tích chương trình có thể được chia làm hai loại chính: + Phân tích chương trình tĩnh + Phân tích chương trình động Theo [4]: “Phân tích chương trình tĩnh là quá trình kiểm tra mã nguồn mà không thực hiện chương trình. Nó được sử dụng để xác định vị trí các lỗi mã bao gồm cả lỗi tiềm ẩn, các vùng phức tạp và dài dòng không cần thiết.” Trong phân tích chương trình tĩnh, một chương trình được phân tích mà không cần phải thực thi với một đầu vào cụ thể.
Phân tích chương trình tĩnh thường mô tả các kết quả có thể có cho một tập các yếu tố đầu vào (thường là cho tất cả các yếu tố đầu vào của chương trình). Vì hành vi của một chương trình có thể khác nhau cho mỗi đầu vào khác nhau cho nên phân tích tĩnh thường là mang ý nghĩa gần đúng. Thay vì đưa ra kết quả chính xác, phân tích tĩnh thường đưa ra giới hạn trên và dưới của các giá trị có thể. Theo [4]: “Phân tích chương trình động là việc phân tích phần mềm máy tính được làm bằng cách thực thi các chương trình trên một tập các dữ liệu đầu vào.” Để hiểu được hành vi của chương trình, chúng ta thực hiện chương trình bằng một số đầu vào, và sau đó kiểm tra đầu ra của nó.
Để hiểu được chương trình tốt hơn, chúng ta phải thực hiện chương trình với việc sử dụng nhiều bộ đầu vào khác nhau. Điều này khiến việc phân tích chương trình động mất nhiều thời gian hơn so với phân tích chương trình tĩnh. Tuy nhiên, phân tích chương trình động chính xác hơn phân tích chương trình tĩnh, vì đầu ra của nó là kết quả từ một đầu vào cụ thể và có kiểm chứng, chứ không phải là một tập hợp các giả định của cả đầu vào và đầu ra. Phân tích chương trình tĩnh Trong phân tích chương trình tĩnh, chương trình được phân tích bằng phương pháp phân tích cấu trúc, mà không cần chạy mã lệnh.
Phân chương trình tĩnh dựa trên mã nguồn có thể được thực hiện bằng nhiều cách khác nhau. Ví dụ: phân tích tĩnh có thể được dựa trên việc kiểm tra luồng điều khiển của chương trình, kiểm tra luồng dữ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 liệu của chương trình, hoặc kiểm tra sự phức tạp của chương trình bằng cách sử dụng các đơn vị (metrics) khác nhau, … Hầu hết các nghiên cứu về sự hiểu chương trình tự động đều dựa trên Phân tích chương trình tĩnh. Các phương pháp tiếp cận về việc hiểu chương trình tự động được chia thành các loại sau: + Phương pháp tiếp cận dựa trên tri thức + Sử dụng lý luận mờ trong việc hiểu chương trình + Phương pháp tiếp cận đánh giá chương trình tương tự +… 1. Phương pháp tiếp cận dựa trên tri thức Theo [3]: “Kỹ thuật dựa trên tri thức được dựa trên các cơ sở tri thức được lưu trữ và định nghĩa trước.
Ý tưởng cơ bản của hiểu chương trình dựa trên tri thức chỉ đơn giản là chúng ta so sánh mã nguồn đầu vào với các đoạn mã mẫu có trong thư viện. Các đoạn mã này thường được gọi là các kế hoạch, các mẫu, các phân đoạn, … ” Nếu chúng ta hiểu được các kế hoạch làm gì thì chúng ta có thể dễ dàng hiểu được đoạn mã nguồn đó làm gì khi chúng ta tìm thấy một sự phù hợp giữa những đoạn mã nguồn và một kế hoạch nào đó. Sự hiểu chương trình dựa trên tri thức là quá trình tìm hiểu một chương trình về mục tiêu của nó. Trong khái niệm này, viết một chương trình mới là một quá trình của việc viết lại các mục tiêu của chương trình trong một tập hợp các mục tiêu con sử dụng các kế hoạch như các quy tắc cho quá trình viết lại.
Sự hiểu chương trình có thể được coi là một quá trình ngược lại, là sự hiểu biết mục tiêu thông qua sự hiểu biết về các mục tiêu con sử dụng các kế hoạch. Các kế hoạch riêng biệt và đơn giản có thể được gộp lại thành một hình thức phức tạp để tạo ra một chương trình. Các thuật toán có thể được coi là được hình thành từ các kế hoạch. Ví dụ, như Letovsky và Soloway mô tả thuật toán mergesort có thể được suy ra từ sự kết hợp một số kế hoạch: kế hoạch đệ quy trên cây nhị phân, kế hoạch để tách một chuỗi thành hai, kế hoạch phân loại cặp số, và kế hoạch sát nhập các danh sách được sắp xếp.
Vì vậy, kế hoạch này không nên nhầm lẫn với các thuật toán hoặc thủ tục vì chúng là các khái niệm khác nhau. Phương pháp tiếp cận dựa trên tri thức có thể được chia làm 3 loại: Phương pháp tiếp cận từ trên xuống, từ dưới lên và kết hợp cả hai. Phương pháp chủ yếu là phương pháp tiếp cận từ dưới lên, có nghĩa là đầu tiên chúng tôi cố gắng để nhận dạng và hiểu những đoạn mã nhỏ (còn gọi là các kế hoạch cơ bản). Sau khi hiểu được các kế hoạch cơ bản, chúng tôi có thể tiếp tục quá trình nhận ra và hiểu kế hoạch cấp cao hơn bằng cách kết hợp ý nghĩa của những kế hoạch LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 cơ bản đã được xác định.
Tiếp tục quá trình này, cuối cùng chúng ta có thể kết luận toàn bộ những gì mã nguồn sẽ làm. Phương pháp tiếp cận từ trên xuống: ý tưởng ở đây là bằng cách biết được vấn đề chính, chúng ta có thể lựa chọn kế hoạch đúng từ thư viện để giải quyết vấn đề cụ thể và sau đó so sánh các mã nguồn với các kế hoạch. Nếu có một sự phù hợp giữa mã nguồn và kế hoạch trong thư viện, chúng ta có thể trả lời câu hỏi về những gì mà chương trình làm được. Thêm vào đó, một số phương pháp lai giữa hai kỹ thuật từ trên xuống và kỹ thuật từ dưới lên cũng được sử dụng.
Một ví dụ về các phương pháp này là: Các kế hoạch của chương trình đầu tiên được xác định (hiểu) bằng kỹ thuật từ dưới lên, sau đó kế hoạch chung được đề xuất bởi hệ thống được so sánh với chương trình bằng cách từ trên xuống. Các kế hoạch chung được đề xuất bằng cách sử dụng một thư viện kế hoạch được tổ chức tốt, trong đó mỗi kế hoạch được đánh một chỉ mục, mục tiêu và ý nghĩa liên kết đến các kế hoạch khác. Bằng cách sử dụng một cơ sở lập chỉ mục, hệ thống có thể nhanh chóng kết hợp một phần của mã nguồn với một kế hoạch trong cơ sở tri thức. Sử dụng lý luận mờ trong việc hiểu chương trình dựa trên tri thức Thay vì thực hiện nhiệm vụ so sánh mã với tất cả các kế hoạch, thì cách tiếp cận thường được sử dụng trong việc hiểu chương trình dựa trên tri thức ở đây là: Đầu tiên nó nhận ra một nhóm các câu lệnh như một phân vùng của mã gọi là khối mã.
Các khối mã, hoặc chỉ đơn giản là các khối – là các phần của mã có thể được hiểu khác các phần khác của mã, và làm điều gì đó có ý nghĩa độc lập. Khối đôi khi được coi như một bản mẫu, một kế hoạch, một lược đồ hoặc một cơ sở. Lúc đầu, các khối tiềm năng được xác định từ mã nguồn. Trong các chương trình lớn hơn, có thể có một số lượng lớn các khối tiềm năng được xác định.
Do đó, có một việc cần làm là phải bằng cách nào đó giảm con số này bằng cách chọn các khối có triển vọng nhất từ các khối tiềm năng được gọi là khối ứng cử viên. Ngay khi các khối ứng cử viên được hiểu, hệ thống sẽ chỉ lấy từ thư viện kế hoạch ra những kế hoạch mà trông giống như những khối này. Nó xếp hạng các kế hoạch theo sự tương đồng với mã và lựa chọn những kế hoạch xếp hạng cao nhất để nghiên cứu và so sánh kỹ lưỡng hơn. Chi tiết của việc nghiên cứu và so sánh bao gồm các thao tác tính toán giá trị mà không phải so sánh tất cả các kế hoạch với các mã sử dụng trong các thao tác này.
Vì vậy mà một lượng thời gian đáng kể có thể được tiết kiệm. Lý luận mờ được sử dụng cho việc tìm kiếm các kế hoạch tương tự nhất và xếp hạng chúng. Để áp dụng lý luận mờ, đầu tiên chúng ta phải tìm những loại đặc trưng LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 của mã có thể phân biệt được và so sánh các mã, từ đó giúp chúng ta tìm thấy sự tương đồng giữa các kế hoạch và khối. Nghiên cứu bởi Berghel và Sallach đưa ra các đặc trưng của mã được sử dụng như các phép đo tương tự.
Những đặc trưng này được thể hiện trong Bảng 1. Các đặc trưng của mã được sử dụng bởi Berghel and Sallach Code characteristics Effectiveness[0 -1] (Các đặc trưng) (Ảnh hưởng) Tổng số thao tác 0.98 Tổng số toán hạng 0.90 Tổng số biến 0.87 Các toán hạng duy nhất 0.85 Tổng số dòng 0.78 Các thao tác duy nhất 0.52 Các ảnh hưởng ở mức thấp hơn -- Sau khi chọn các đặc trưng mã thích hợp, bước tiếp theo là định lượng chúng. Có nhiều cách tiếp cận khác nhau về định lượng các yếu tố đã lựa chọn. Phương pháp tốt nhất và phù hợp nhất nên được lựa chọn là dựa trên ý nghĩa thông thường và có xem xét bối cảnh và các loại vấn đề.
Bước tiếp theo là chuyển đổi các yếu tố định lượng thành ngôn ngữ tập mờ, ví dụ LOW, MEDIUM và HIGH có nghĩa là tỉ lệ phần trăm thấp, trung bình và cao của sự khác biệt giữa kế hoạch và các đoạn mã tương ứng. Khi giá trị của từng yếu tố được tính toán, một bộ quy tắc được tạo ra. Những quy tắc này sau đó được sử dụng trong lý luận: một biến đơn được tìm thấy các giá trị khác nhau của các yếu tố khác nhau. Biến đơn này có thể được đặt tên, ví dụ SIMILARITY thể hiện sự tương tự của kế hoạch cụ thể với khối lệnh.