BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI ──────── * ─────── NGUYỄN ĐỨC CƯỜNG NGHIÊN CỨU VỀ SEPARATION LOGIC VÀ ỨNG DỤNG VÀO HỆ THỐNG KIỂM ĐỊNH TỰ ĐỘNG LUẬN VĂN THẠC SĨ KỸ THUẬT CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: TS TRẦN ĐỨC KHÁNH HÀ NỘI -2014 LỜI CAM ĐOAN Tôi xin cam đoan đề tài nghiên cứu hoàn toàn tự làm hướng dẫn Thầy giáo TS Trần Đức Khánh Những kết nghiên cứu, thử nghiệm thực phần mềm mô Các số liệu, kết trình bày luận văn hoàn toàn trung thực chưa công bố công trình Các tài liệu tham khảo sử dụng luận văn dẫn nguồn Nếu xảy điều không lời cam đoan trên, xin chịu hoàn toàn trách nhiệm trước Viện Nhà trường Hà Nội, ngày tháng năm 2014 Tác giả Nguyễn Đức Cường Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang2 LỜI CẢM ƠN Trong lời báo cáo luận văn tốt nghiệp “Nghiên cứu Separation Logic ứng dụng vào hệ thốngkiểm định tự động” này, muốn gửi lời cảm ơn biết ơn chân thành tới tất người hỗ trợ, giúp đỡ chuyên môn, vật chất tinh thần trình thực luận văn Trước hết, xin chân thành cảm ơn Tiến sĩ Trần Đức Khánh, môn Hệ thống thông tin, Viện Công nghệ Thông tin Truyền thông trường Đại học Bách khoa Hà Nội, người trực tiếp hướng dẫn, nhận xét, giúp đỡ suốt trình thực luận văn Xin chân thành cảm ơn Viện Công nghệ Thông tin Truyền thông, Viện Đào tạo sau đại học - Trường Đại học Bách khoa Hà Nội giúp đỡ suốt trình học tập tìm hiểu Xin cảm ơn cộng tác viên nhóm tìm hiểu Separation Logic năm 2013 (do TS Trần Đức Khánh hướng dẫn), đặc biệt Nguyễn Anh Tuấn lớp Kỹ sư tài năng, K52 - Trường Đại học Bách khoa Hà Nội giúp đỡ nhiều thời gian thực luận văn Tôi xin bày tỏ lòng biết ơn đến gia đình người bạn thân giúp đỡ, động viên nhiều suốt trình học tập làm luân văn tốt nghiệp Do thời gian thực có hạn, kiến thức chuyên môn nhiều hạn chế nên luận văn thực chắn không tránh khỏi thiếu sót định Tôi mong nhận ý kiến đóng góp thầy, cô giáo bạn Hà Nội, ngày 20 tháng 03 năm 2014 Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang3 MỤC LỤC LỜI CAM ĐOAN MỤC LỤC DANH MỤC BẢNG BIỂU DANH MỤC HÌNH VẼ DANH MỤC THUẬT NGỮ SỬ DỤNG 10 TÓM TẮT NỘI DUNG LUẬN VĂN TỐT NGHIỆP 11 1.Lý chọn đề tài 11 2.Lịch sử tìm hiểu 12 3.Mục đích tìm hiểu, đối tượng, phạm vi luận văn 13 3.1Mục đích tìm hiểu 13 3.2Đối tượng tìm hiểu 14 3.3 Phạm vi tìm hiểu 14 4.Các luận điểm đóng góp luận văn 15 4.1 Các luận điểm 15 4.2 Đóng góp luận văn 15 5.Phương pháp tìm hiểu 15 6.Cấu trúc luận văn 16 CHƯƠNG 1.TỔNG QUAN 17 1.1 Hoare Logic kiểm định phần mềm 17 1.2 Separation Logic kiểm định phần mềm 18 1.3Kiểm chứng mô hình 19 1.4 Vai trò Separation Logic tự động hóa kiểm định phần mềm 20 1.5 Kết luận chương 21 CHƯƠNG CƠ SỞ LÝ THUYẾT CỦA SEPARATION LOGIC VÀ GIẢI PHÁP CHO ỨNG DỤNG KIỂM ĐỊNH PHẦN MỀM TỰ ĐỘNG 22 2.1 Logic bậc 23 2.1.1 Logic mệnh đề 23 Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang4 2.2.2 Logic bậc 24 2.2.3 Tích liên tiếp 24 2.2 Hoare logic 25 2.2.1 Logic vị từ 25 2.2.2 Hoare logic 29 2.2.2.1 Công thức cú pháp cho chứng minh chương trình 29 2.2.2.2 Các khái niệm tính 30 2.2.2.3 Tiên đề Hoare Logic 31 2.3 Separation logic 34 2.3.1 Cơ Separation Logic 34 2.3.2 Ngôn ngữchương trình 37 2.3.2.1 Ngữ pháp 37 2.3.3 Ngôn ngữ đặc tả 39 2.3.3.1 Vị từ User-defined 41 2.3.3.2 Chú thích Well-formedness 45 2.3.3.3 Khái niệm Bag giá trị/địa 47 2.4 Quy tắc Forward Verification 49 2.5 Quy tắc kiểm tra suy diễn Entailment Checking 52 2.5.1 Quy tắc Matching up Heap Node 55 2.5.2 Quy tắc Unfold vị từ Shape Atendence 55 2.5.3 Quy tắc Fold vị từ Shape Consequence 56 2.6 Tính đắn quy tắc suy diễn 57 2.6.1 Mô hình ngữ nghĩa 58 2.6.2 Tính đắn quy tắc Verification 59 Định lý (Preservation) 60 Định lý (Progress) 60 Định lý (Safety) 60 2.6.3Tính đắn quy tắc Entailment 61 Định lý (Soundness) 61 Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang5 Định lý 2(Termination) 61 2.7 Kết luận chương 61 CHƯƠNG3 CÀI ĐẶT THỬ NGHIỆM CÔNG CỤ KIỂM ĐỊNH TỰ ĐỘNG ỨNG DỤNG SEPARATION LOGIC 62 3.1 Phương hướng cài đặt thử nghiệm công cụ kiểm định tự động ứng dụng Separation logic 62 3.2 Kiến trúc HIP/SLEEK 63 3.3 Hoạt động HIP/SLEEK 64 3.3.1 File đầu vào 64 3.3.2 Kiểu liệu 65 3.3.3 Cấu trúc liệu 65 3.3.4 Định dạng công thức khẳng định 65 3.3.5 Một vài tính đặc biệt khác 66 3.4 Kết thử nghiệm 67 3.4.1 Môi trường cài đặt 67 3.4.2 Kiểm định với cấu trúc liệu List 68 3.4.2.1 Mô tả cấu trúc liệu danh sách 68 3.4.2.2 Dạng thức File đầu vào danh sách 69 3.4.2.3 Kết kiểm định danh sách với HIP/SLEEK 72 3.4.3 Kiểm định với cấu trúc liệu Tree 73 3.4.3.1 Mô tả cấu trúc liệu Tree 73 3.4.3.2 Dạng thức File đầu vào Tree 74 3.4.3.3 Kết kiểm địnhTree với HIP/SLEEK 78 3.4.4 Kiểm định với cấu trúc liệu Queue 78 3.4.4.1 Mô tả cấu trúc liệu Queue 79 3.4.4.2 Dạng thức File đầu vào Queue 80 3.4.4.3 Kết kiểm địnhQueue với HIP/SLEEK 85 3.5 Kết luận chương 86 CÔNG VIỆC LIÊN QUAN 88 Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang6 4.1 Dạng thức phân tích/kiểm tra Shape 88 4.2 Thuộc tính Size 88 4.3 Thuộc tính Set/Bag 89 4.4 Kỹ thuật Fold/Unfold 89 4.5 Một số ứng dụng kiểm định Logic khác 89 KẾT LUẬN 91 TÀI LIỆU THAM KHẢO 93 Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang7 DANH MỤC BẢNG BIỂU Bảng - Toán tử Separation Logic 35 Bảng - Truy xuất vùng nhớ Heap 36 Bảng - Ý nghĩa ký hiệu sử dụng ngôn ngữ chương trình 38 Bảng - Ký hiệu định nghĩa mô hình 58 Bảng - Ký hiệu ngữ nghĩa 59 Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang8 DANH MỤC HÌNH VẼ Hình - Toán hạng logic mệnh đề 23 Hình - Ngôn ngữ chương trình 37 Hình - Ngôn ngữ đặc tả 41 Hình - Các quy tắc kiểm tra suy diễn 54 Hình - Tổng quan kiến trúc HIP/SLEEK 63 Hình – Kết kiểm định đặc tả cấu trúc danh sách nối kép 73 Hình – Cấu trúc liệu 74 Hình – Kết kiểm định đặc tả cấu trúc liệu 78 Hình – Cấu trúc liệu hàng 79 Hình 10 - Kết kiểm định đặc tả cấu trúc liệu hàng 86 Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang9 DANH MỤC THUẬT NGỮ SỬ DỤNG Ký hiệu Từ viết tắt Ý nghĩa Stack Bộ nhớ Stack Heap Separation Logic Bộ nhớ Heap Logic đề xuất O’Hearn Reynolds Hoare Logic Logic đề xuất Floyd Hoare Intuitionistic Logic Logic đề xuất Brouwer tương tự Logic bậc Intuitionistic Linear Logic Logic đề xuất Girard BI Logic Bunch BI đề xuất O'Hearn and Pym Program Chương trình Forward verification Quy tắc suy diễn biến đổi Entailment checking Quy tắc kiểm tra suy diễn Wellformedness Chú thích đặt tên Well-formedness Well-Founded Chú thích đặt tên Well-Founded Reachable Thuộc tính truy cập Size Thuộc tính kích thước vị từ Bag Thuộc tính tập hợp vị từ Prestate Tiền trạng thái PostState Hậu trạng thái Heap part Phần công thức chứa suy diễn Heap Pure part Phần công thức túy không chứa suy diễn Heap Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang10 3.4.4.2 Dạng thức File đầu vào Queue Với cấu trúc liệu mô tả trên, đặc tả đặc tả thủ tục liệu phù hợp với khai báo đầu vào HIP Đặc tả khai báo liệu Đặc tả khai báo vị từ Shape thuộc tính Đặc tả khai báo thủ tục với dạng tiền điều kiện/hậu điều kiện (Pre/Post) Đặc tả thủ tục chèn thêm giá trị có độ ưu tiên v vào hàng ưu tiên Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang80 Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang81 Đặc tả thủ tục xóa giá trị khỏi hàng ưu tiên Đặc tả thủ tục xóa Node gốc khỏi hàng ưu tiên Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang82 Đặc tả thủ tục khôi phục thuộc tính Heap hàng ưu tiên Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang83 Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang84 3.4.4.3 Kết kiểm địnhQueue với HIP/SLEEK Thực kiểm định thủ tục hàng ưu tiên với định dạng khai báo đầu vào phù hợp với khai báo HIP ta kết sau: Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang85 Hình 10 - Kết kiểm định đặc tả cấu trúc liệu hàng Kết kiểm định đặc tả thủ tục thành công, suy diễn chứng minh tự động (kết suy diễn SLEEK) trả file sleek_log home_loris_Desktop_HIP_SLEEK_HIP_LV_PriorityQueue_ss.txt 3.5 Kết luận chương Trong chương luận văn trình bày công cụ HIP/SLEEK phát triển nhóm tác giả “Wei-Ngan Chin, Cristina David, Huu Hai Nguyen, Shengchao Qin” Đây công cụ ứng dụng lý thuyết Separation Logic trình bày chương thực kiểm định Module chương trình tự động thông qua việc suy diễn mức mã nguồn chương trình Luận văn thực nghiệm kiểm định vài cấu trúc liệu điển hình trình bày kết thực nghiệm công cụ thực tế Việc tìm hiểu công cụ HIP/SLEEK làm rõ số vấn đề sau: -Lý thuyết kiểm định chương trình tự động ứng dụng Separation Logic áp dụng thực tế xây dựng công cụ kiểm định chương trình tự động Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang86 -Kỹ thuật đặc tả chương trình ứng dụng lý thuyết Separation Logic hoàn toàn đắn áp dụng cấu trúc liệu phức tạp, liệu có tính động Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang87 CÔNG VIỆC LIÊN QUAN 4.1 Dạng thức phân tích/kiểm tra Shape Trong nghiên cứu phân tích liệu chương trình, phân tích Shape sử dụng để kiểm tra cấu trúc liệu người dùng phổ biến Một kỹ thuật bật Pointer Assertion Logic Moeller Schwartzbach, kỹ thuật mô tả tính bất biến loại đồ thị Nhưng kỹ thuật chủ yếu tập trung cho việc cung cấp ngữ nghĩa cho suy diễn dựa Hoare Logic hệ thống kiểm định, luận văn dạng phân tích Shape đề cập có phạm vi áp dụng cho chương trình thao tác với liệu trỏ Khác với nghiên cứu phân tích Shape trước chủ yếu phân tích liệu Shape bất biến, kỹ thuật phân tích Shape sử dụng luận văn đặc tả thuộc tính Size Bag cấu trúc dữ.Ngoài việc xây dựng nên vị từ user-defined shape, cho phép mô tả cấu trúc liệu phức tạp AVL, đỏ đen, danh sách xếp, danh sách nối đôi, ngăn xếp, hàng đợi… 4.2 Thuộc tính Size Theo nhiều hướng nghiên cứu khác, thuộc tính Size coi khai phá lớn ngôn ngữ đặc tả, trước cấu trúc liệu dễ dàng phân tích nhờ thuộc tính bất biến Phân tích Size xuất sau chương trình dựa đối tượng, chương trình bị hạn chế việc quản lý kích thước đối tượng bất biến định danh kích thước đối tượng động định danh, hỗ trợ cho dạng thức Shape phức tạp Hệ thống Applied Type System (ATS)là hệ thống chứng minh chương trình việc sử dụng linear logic, ATS có khả thao tác với cấu trúc liệu phức tạp có chia sẻ liệu đồng thời Tuy nhiên với hệ thống này, người dùng phải cung cấp thuộc tính trạng thái áp dụng cho chương trình xác đầy đủ, vai trò ATS thực Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang88 việc chứng minh tính đắn chương trình Trong luận văn sử dụng mô tả với ràng buộc phân tích shape, size, bag cung cấp khả kiểm định Module tự động 4.3 Thuộc tính Set/Bag Kỹ thuật phân tích Set (tập) sử dụng để kiểm định cấu trúc liệu chương trình đề xuất Kuncak, đề cập tới khái niệm first order kết hợp khái niệm Set giải thuậtPresburger Sử dụng kết kỹ thuật việc xây dựng đặc tả ràng buộc kết hợp, nhiên giải thuật đưa phức tạp.Trong luận văn phân tích thuộc tính Reachability có liên quan tới thuộc tính Set/bag việc sử dụng đơn giản để gần gũi với khái niệm mức vị từ 4.4 Kỹ thuật Fold/Unfold Fold/Unfold(gấp/mở gấp)là kỹ thuật sử dụng biến đổi chương trình, biết đến tương tự kỹ thuật Unroll/Roll.Thủ tục sử dụng cách tự động suốt trình kiểm tra suy diễn Entailment Checking Thủ tục tự động sử dụng kỹ thuật Unroll/Roll đưa Berdine, lại gặp khó khăn làm việc với vị từ cho đoạn danh sách (lseg) (tree) Kỹ thuật Fold/Unfold đề cập luận văn phổ biến, tự động có tính dừng sử dụng kiểm tra suy diễn công thức Heap 4.5 Một số ứng dụng kiểm định Logic khác Những ứng dụng kiểm định chương trình dựa lý thuyết suy diễn Hoare Logic đời từ lâu so với ứng dụng tảng Separation Logic Sau đề cập tới số ứng dụng điển hình điểm hạn chế ứng dụng ESC/Java ứng dụng kiểm tra chương trình tĩnh cho Java, phát triển Compaq Systems Research Center.Với mong muốn tìm nhiều lỗi so với công cụ kiểm định tĩnh trước Ứng dụng ESC/Javacho phép Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang89 chương trình kiểm định qua lỗi mà thiết kế ESC/Java tức chấp nhận kết sai chương trình Với cách thức kiểm định đề cập luận văn, chương trình kiểm định đảm bảo tính đắn phù hợp với đặc tả chương trình thực thi ESC/Java2 cải tiến ESC/Java Trong thiết kế phù hợp với nhiều phiên Java nhiều cấu trúc JML Tuy nhiên gặp nhiều khó khăn cho việc kiểm định chương trình sử dụng cấu trúc liệu Heap mà yêu cầu thuộc tính Reachability Spec chương trình phát triển Microsoft Research, sử dụng để kiểm định chương trình viết với ngôn ngữ C# Điểm khác biệt Spec sử dụng trường đặc biệt thủ tục để lưu trữ tính chất bất biến, luận văn đề cập tới khái niệm vị từ Việc sử dụng vị từ giúp người dùng dễ dàng hình dung với đặc tính bất biến chương trình VeriFast công cụ phát triển để kiểm địnhnhững thuộc tính an toàn chương trình làm việc với trỏ Công cụ hỗ trợ vị từ dạng thức Separation Logic nhiên kỹ thuật đặc tả đề cập đơn giản Còn nhiều công cụ kiểm định khác sử dụng Logic để suy diễn tính đắn chương trình Những so sánh giúp cho người đọc dễ hình dung điểm khác biệt công cụ đề cập tới luận văn công cụ đưa so sánh Điểm nhấn mạnh mà luận văn đưa khái niệm vị từ User-defined, sử dụng để mô tả thuộc tính sử dụng để phân tích chương trình cách hiệu Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang90 KẾT LUẬN CÁC NHIỆM VỤ ĐÃ HOÀN THÀNH Lĩnh vực ứng dụng Separation Logic mẻ, nghiên cứu tìm hiểu Separation Logic người viết luận văn cố gắng tìm hiểu trình bày khía cạnh tập trung vào hoàn thành mục tiêu đề luận văn: 1) Nghiên cứu tổng quan tảng Separation Logic, nêu rõ vai trò Separation Logic việc phát triển ứng dụng kiểm định phần mềm tự động 2) Nghiên cứu Separation Logic kỹ thuật đặc tả chương trình ứng dụng Separation Logic ứng dụng xây dựng công cụ kiểm định tự động 3) Nghiên cứu công cụ HIP/SLEEK ứng dụng Separation Logic kiểm định cácModeule chương trình tự động CÁC KẾT QUẢ ĐẠT ĐƯỢC Về mặt lý thuyết: 1) Trình bày tảng sở xây dựnglên lý thuyết Separation Logic vai trò hoạt động kiểm định phần mềm tự động 2) Trình bày lý thuyết Separation Logic, kỹ thuật đặc tả chương trình dựa Separation Logic mô hình tính đắn suy diễn kiểm định Đây tảng xây dựng lên công cụ kiểm định chương trình tự động ứng dụng Separation Logic Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang91 Về mặt thực nghiệm: 1) Trình bày mô hình kiểm định ứng dụng lý thuyết Separation Logic kiểm định Module chương trình công cụ HIP/SLEEK 2) Trình bày thực nghiệm kiểm định đặc tả số cấu trúc liệu ứng dụng lý thuyết Separation Logicvà kết thực nghiệm thực tế với công cụ HIP/SLEEK Thực nghiệm đóng vai trò khai phá cho ứng dụng kiểm định đặc tả áp dụng công cụ HIP/SLEEK vào việc kiểm chứng tính đắn chương trình CÁC VẤN ĐỀ CÒN TỒN ĐỌNG Do khối lượng lý thuyết lớn lý thuyết Separation Logic mẻ nên luận văn số vấn đề tồn đọng sau: 1) Chưa đề cập tới quy tắc xấp xỉ lý thuyết Separation Logic suydiễn kiểm định chương trình 2) Chưa đưa hiệu kiểm định tự động mô hình ứng dụng lý thuyết Separation Logic với mô hình suy diễn tự động khác ĐỊNH HƯỚNG PHÁT TRIỂN Với đề tài này, người viết luận văn mong muốn thời gian tới tiếp tục bổ sung hoàn thiện lý thuyết Separation Logic, đặc biệt lý thuyết mô hình xấp xỉ làm rõ việc chứng minh định lý đề cập luận văn Đồng thời trình bày thêm ứng dụng kiểm định tự động khác ứng dụng lý thuyết Separation Logic tương lai phát triển công cụ kiểm định tự động toàn cấu trúc chương trình Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang92 TÀI LIỆU THAM KHẢO [1].BURDY, L., CHEON, Y., COK, D R., ERNST, M D., KINIRY, J R., LEAVENS, G T.,LEINO, K R M., and POLL, E., “An overview of JML tools and applications,” Software Tools for Technology Transfer, 2005 [2].CHIN, W.-N., DAVID, C., NGUYEN, H H., and QIN, S., “Multiple pre/post specifica-tions for heap-manipulating methods,” in HASE, 2007 [3].CHIN, W.-N., DAVID, C., NGUYEN, H H., and QIN, S., “Enhancing modular oo veri-fication with separation logic,” inPOPL, 2008 [4].CHIN, W and KHOO, S., “Calculating sized types,” in ACM SIGPLAN PEPM, (Boston, United States), pp 62–72, Jan 2000 [5].CHIN, W., KHOO, S., QIN, S., POPEEA, C., and NGUYEN, H., “Verifying Safety Poli-cies with Size Properties and Alias Controls,” inIEEE/ACM Intl Conf on Software En-gineering, (St Louis, Missouri), May 2005 [6].COK, D R and KINIRY, J., “ESC/Java2: Uniting ESC/Java and JML.,” in Int’l Work-shop on Construction and Analysis of Safe, Secure, and Interoperable Smart Devices, pp 108–128, 2004 [7].C.A.R Hoare An axiomatic basis for computer programming Communications of the ACM, 12(10):576–580, 1969 [8].C.A.R Hoare and J He A Trace Model for Pointers and Objects InEuropean Conference on Object-Oriented Programming, volume 1628 of Lecture Notes in Computer Science, pages 1–17 Springer, 1999 [9].C.A.R Hoare The verifying compiler: A grand challenge for computing research Journal of ACM, 50(1):63–69, 2003 Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang93 [10].JACOBS, B., SMANS, J., and PIESSENS, F., “A Quick Tour of the VeriFast Program Verifier,” inAPLAS, pp 304–311, 2010 [11].K.R.M Leino Specification and verification of object-oriented software lecture notes Marktoberdorf international summer school, 2008 [12].LEINO, K R M., “Dafny: An automatic program verifier for functional correctness,” in LPAR (Dakar), pp 348–370, 2010 [13].M Barnett, K R M Leino, and W Schulte The Spec# programming system: An overview InInt’l Workshop on Construction and Analysis of Safe, Secure, and Interop-erable Smart Devices, volume 3362 of Lecture Notes in Computer Science, pages 49–69 Springer, 2004 [14].NGUYEN, H H., DAVID, C., QIN, S., and CHIN, W., “Automated Verification of Shape And Size Properties via Separation Logic,” inIntl Conf on Verification, Model Checking and Abstract Interpretation, (Nice, France), Jan 2007 [15].REYNOLDS, J., “Separation Logic: A Logic for Shared Mutable Data Structures,” in IEEE Logic in Computer Science, (Copenhagen, Denmark), July 2002 [16].W.N Chin, S.C Khoo, S.C Qin, C Popeea, and H.H Nguyen Verifying Safet Policies with Size Properties and Alias Controls InACM SIGSOFT International Conference on Software Engineering, pages 186–195 ACM, 2005 Học viên thực hiện: Nguyễn Đức Cường – Lớp 11BCNTT Trang94 ... Lý thuyết kiểm định phần mềm ứng dụng kiểm định tự động rộng, khuôn khổ luận văn đề tài Nghiên cứu Separation Logic ứng dụng vào hệ thống kiểm định tự động” tập trung lĩnh vựckiểm định tĩnh... nhà khoa học trước, cố gắng tìm hiểu đề tài Nghiên cứu Separation Logic ứng dụng vào hệ thống kiểm định tự động” Bởi công trình nghiên cứu có tính định hướng cho luận văn 3.Mục đích tìm hiểu,... công cụ kiểm định dựa chứng minh Logic kiểm tra tính đắn chương trình hoàn toàn tự động Việc ứng dụng Logic học vào kiểm định tự động áp dụng nhiều công cụ kiểm định tự động hiệu mạnh mẽ Tuy