tailieunhanh - Dựa trên đồ thị chương trình phân tích tính khả đạt của chương trình

Ứng dụng kĩ thuật trừu tượng hóa trong phân tích chương trình (program analysis) giúp mở rộng phạm vi xử lí tới các hệ thống có không gian trạng thái lớn. Các kĩ thuật trừu tượng đang được sử dụng ngày càng nhiều trong phân tích phát hiện lỗi chương trình. Quá trình phân tích phát hiện lỗi một chương trình thường gắn chặt với việc xác định tính khả đạt (reachability) của chương trình đó. | TẠP CHÍ KHOA HỌC SỐ 8 2016 35 DỰA TRÊN ĐỒ THỊ CHƯƠNG TRÌNH PHÂN TÍCH TÍNH KHẢ ĐẠT CỦA CHƯƠNG TRÌNH 1 Nguyễn Đức Giang Nguyễn Văn Trãi Đinh Quang Đạt Viện Công nghệ Thông tin Viện Hàn lâm Khoa học và Công nghệ Việt Nam Tóm tắt tắt ắt Ứng dụng kĩ thuật trừu tượng hoá trong phân tích chương trình program analysis giúp mở rộng phạm vi xử lí tới các hệ thống có không gian trạng thái lớn. Các kĩ thuật trừu tượng ñang ñược sử dụng ngày càng nhiều trong phân tích phát hiện lỗi chương trình. Quá trình phân tích phát hiện lỗi một chương trình thường gắn chặt với việc xác ñịnh tính khả ñạt reachability của chương trình ñó. Nếu tính khả ñạt ñược chứng minh là ñúng trên mô hình trừu tượng là xấp xỉ của chương trình thì nó cũng ñúng trong chương trình thực do tính bảo toàn của phép trừu tượng hoá. Tuy nhiên sử dụng các kĩ thuật trừu tượng ñôi khi làm mất ñi tính chính xác trong phân tích tính khả ñạt do một số trạng thái ñã bị bỏ qua ñặc biệt khi có sự xuất hiện của các vòng lặp. Một số giải pháp hiện thời giải quyết vấn ñề này bằng cách sử dụng các tập bị chặn dưới và các hàm xếp hạng ranking function . Giải pháp của chúng tôi giải quyết vấn ñề theo một cách tiếp cận khác không sử dụng các tập bị chặn dưới và hàm xếp hạng. Thay vào ñó chúng tôi dựa trên việc kiểm tra các ñiều kiện trên ñồ thị chương trình program graph ứng với hệ thống thực các ñiều kiện này ñược kiểm tra tự ñộng ñối với mô hình trừu tượng. Từ khoá Đồ thị chương trình tính khả ñạt hàm xếp hạng kiểm chứng mô hình 1. GIỚI THIỆU Hiện nay trong bối cảnh phát triển nhanh chóng của lĩnh vực công nghệ thông tin CNTT các hệ thống phần mềm trở lên phổ biến và có tầm ảnh hưởng quan trọng tới nhiều hoạt ñộng kinh tế - xã hội. Mặc dù ñược sử dụng phổ biến có một thực tế là các hệ thống phần mềm thường xuyên mắc các lỗi nghiêm trọng trong cả thiết kế và cài ñặt. Những lỗi này trở thành mục tiêu của các cuộc tấn công phá hoại ñặt sinh mạng và tài sản của người dân và xã hội dưới nhiều hiểm hoạ. Thống kê cho thấy hầu hết các