Giới thiệu
Tổng quan về đề tài
Ngày nay, lỗi chương trình là một thách thức lớn đối với các nhà phát triển phần mềm Để giảm thiểu những lỗi này, nhiều công cụ hỗ trợ đã được đề xuất nhằm giúp các lập trình viên nâng cao chất lượng sản phẩm của mình.
Các công cụ kiểm tra phần mềm tự động ngày càng phổ biến và đóng góp tích cực cho quy trình kiểm tra phần mềm Chúng có thể được chia thành hai nhóm chính.
Phân tích MUST, hay còn gọi là kỹ thuật under-approximate, đảm bảo rằng một thuộc tính nhất định của chương trình sẽ xảy ra trong một số đường thực thi cụ thể, giúp phát hiện lỗi trong chương trình Các thuộc tính này thường liên quan đến các điều kiện lỗi như lỗi truy cập con trỏ null hoặc vượt quá kích thước của mảng Tuy nhiên, việc kiểm tra tất cả các đường thực thi của chương trình là không khả thi đối với những chương trình lớn, dẫn đến việc phân tích MUST không thể bao quát hết mọi khả năng Do đó, nhược điểm chính của phân tích MUST là khả năng phát sinh lỗi false-negatives, tức là nó có thể báo cáo rằng chương trình không có lỗi trong khi thực tế lại tồn tại lỗi.
Nhóm công cụ kiểm tra thứ hai dựa trên kỹ thuật over-approximate, hay còn gọi là phân tích MAY, được sử dụng để chứng minh rằng một thuộc tính nào đó của chương trình luôn đúng cho tất cả các đường thực thi Phân tích MAY giúp xác minh rằng chương trình không có lỗi, nhưng nhược điểm của nó là có thể dẫn đến tình trạng báo lỗi false-positives, tức là báo cáo rằng chương trình có lỗi mặc dù thực tế không phải vậy Điều này có thể làm cho các công cụ kiểm tra trở nên kém hiệu quả trong việc tìm kiếm và loại bỏ lỗi.
Gần đây, nhiều phương pháp mới đã được phát triển để kết hợp kỹ thuật under-approximate và over-approximate Mục tiêu của việc kết hợp này là nâng cao độ chính xác và hiệu quả cho các công cụ kiểm tra phần mềm.
Kiểm thử phần mềm hiện nay là một kỹ thuật phân tích thiết yếu trong phát triển phần mềm, chủ yếu sử dụng test-case để phát hiện lỗi Kỹ thuật kiểm tra hộp trắng, dựa vào phân tích luồng thực thi của chương trình, vẫn được ưa chuộng trong giáo dục và công nghiệp Tuy nhiên, nó có thể dẫn đến bùng nổ trạng thái do phụ thuộc vào số lệnh rẽ nhánh Để khắc phục nhược điểm này, concolic testing đã trở thành một phương pháp hiệu quả, giúp giảm số lần duyệt qua các đường thực thi mà vẫn đảm bảo tạo ra đủ test-case để phát hiện lỗi.
Các chương trình thao tác trên heap thường sử dụng con trỏ, nhưng các test-case được sinh ra từ kỹ thuật concolic testing không đảm bảo bao quát tất cả các trường hợp cần kiểm tra Nguyên nhân là do phương pháp này không tận dụng thông tin về đặc tả cấu trúc dữ liệu, dẫn đến việc không thể kiểm tra đầy đủ các tình huống xảy ra với cấu trúc dữ liệu đó.
Mục tiêu của đề tài là áp dụng ngữ nghĩa của separation logic để suy luận cho các chương trình thao tác trên heap, từ đó đề xuất phương pháp xây dựng hệ thống sinh test-case hoàn chỉnh Đề tài mở rộng kỹ thuật concolic testing bằng cách kết hợp đặc tả cấu trúc dữ liệu từ chương trình nguồn với luồng thực thi trong bước thực thi symbolic Hệ thống cũng cải tiến việc sinh test-case hiệu quả và hỗ trợ quá trình debug phát hiện lỗi bằng cách kết hợp kỹ thuật slicing trong quá trình này.
Mục tiêu nghiên cứu của luận văn
Đề tài nghiên cứu các kỹ thuật kiểm tra chương trình, đồng thời xây dựng hệ thống sinh logic test-case dựa trên kỹ thuật slicing cho các chương trình viết bằng ngôn ngữ HIP.
Tìm hiểu các kỹ thuật phân tích MUST và MAY và kết hợp 2 phương pháp này để kiểm tra chương trình
Tìm hiểu về separation logic và công cụ HIP/sleek - một công cụ hiệu quả.để kiểm tra chương trình dựa trên con trỏ
Tìm hiểu kỹ thuật concolic testing Xây dựng một hệ thống sinh logic test-case dựa trên kỹ thuật concolic testing cho chương trình dựa trên con trỏ
Kỹ thuật slicing là một phương pháp hữu ích trong việc phát hiện lỗi và cải tiến quy trình sinh test-case cho hệ thống Việc thử nghiệm, đánh giá và phân tích kỹ thuật này sẽ giúp nhận diện rõ ràng các ưu điểm và nhược điểm, từ đó tối ưu hóa hiệu quả trong quá trình phát triển phần mềm.
Đóng góp của luận văn
Luận văn đã đạt được các mục tiêu đề ra bằng cách nghiên cứu các kỹ thuật kiểm tra chương trình, đặc biệt là kỹ thuật phân tích MUST và concolic testing, nhằm phát hiện lỗi trong các chương trình thao tác trên con trỏ Hệ thống được xây dựng sẽ tạo ra tập hợp test-case hiệu quả nhất với số lượng tối thiểu nhưng vẫn đảm bảo độ bao phủ các đường thực thi để phát hiện lỗi Để nâng cao hiệu quả phát hiện lỗi và cải tiến quá trình sinh test-case, luận văn đã kết hợp kỹ thuật slicing trong hệ thống.
Trong quá trình hiện thực hóa hệ thống, luận văn đã phát triển một tập luật hỗ trợ sinh test-case cho chương trình viết bằng ngôn ngữ HIP Đồng thời, khi áp dụng kỹ thuật concolic testing cho các chương trình thao tác với con trỏ, luận văn cũng đề xuất giải pháp khắc phục một số vấn đề thường gặp, như bí danh và truy xuất thuộc tính của cấu trúc dữ liệu Những cải tiến này giúp đảm bảo rằng tập slice được trích xuất sẽ cho kết quả chính xác.
Trong quá trình thực hiện, đề tài đã đóng góp được 1 bài báo nghiên cứu được nói ở chương 7.
Cấu trúc của luận văn
Luận văn bao gồm 7 chương và được trình bày như sau:
Chương 1: Tổng quan về đề tài
Chương 2: Các kiến thức nền tảng
Chương 3: Hệ thống sinh test-case hoàn chỉnh
Chương 4: Các giải pháp cho hệ thống sinh test-case
Chương 5: Hiện thực hệ thống sinh test-case hoàn chỉnh
Chương 6: Kết quả thực nghiệm và Đánh giá
Chương 7: Kết luận và hướng phát triển
Các kiến thức nền tảng
Separation logic
2.1.1 Tổng quan về separation logic
Logic tách biệt là một mở rộng của logic Hoare, được sử dụng để suy diễn cho các chương trình với cấu trúc dữ liệu chia sẻ Cấu trúc dữ liệu chia sẻ, nơi một thuộc tính có thể được tham khảo từ nhiều con trỏ, thường dẫn đến vấn đề bí danh, gây khó khăn trong việc kiểm tra tính đúng đắn của chương trình Do đó, logic Hoare không thể áp dụng cho các chương trình có chứa con trỏ do khả năng xảy ra vấn đề bí danh.
Peter O'Hearn từ Đại học London và John Reynolds từ Đại học Carnegie Mellon đã phát triển separation logic dựa trên Hoare logic bằng cách giới thiệu hai toán tử mới là conjunction không gian (*) và implication không gian (-*) Những tiên đề trong separation logic đã hỗ trợ hiệu quả cho việc chứng minh các chương trình có chứa con trỏ.
2.1.2 Ngữ nghĩa của separation logic
2.1.2.1 Mô hình biểu diễn của separation logic Đối với Hoare logic, trạng thái của chương trình được biểu diễn bằng một ánh xạ đi từ tên biến đến miền giá trị Integer (biểu diễn giá trị của biến đó) và được gọi là Store
+ Integers: tập các số nguyên biểu diễn giá trị của biến
Trong các chương trình có chứa con trỏ, việc biểu diễn bí danh (hai con trỏ cùng trỏ đến một địa chỉ bộ nhớ) không thể thực hiện được bằng cách biểu diễn hiện tại Để khắc phục điều này, separation logic đã đề xuất thêm thành phần heap Mô hình của separation logic bao gồm hai thành phần chính: store và heap Store tương tự như stack trong ngôn ngữ lập trình, có chức năng ánh xạ các biến đến miền giá trị số nguyên, biểu diễn địa chỉ mà biến đó trỏ đến Trong khi đó, heap ánh xạ từ miền địa chỉ ô nhớ (một tập con của miền số nguyên) đến miền số nguyên, biểu diễn giá trị của ô nhớ Trạng thái của chương trình được thể hiện qua hai thành phần này (Store x Heap).
Hình 2.1 : Mô hình của separation logic (nguồn [12])
• Ints là miền các số nguyên
• Variables là miền các biến trong chương trình
• Atoms và Locations là tập con của Ints.
• Stores là hàm ánh xạ từ biến sang Ints
• Heap là ánh xạ từ Location sang Ints.
• States: biểu diễn trạng thái của chương trình được xác định bởi các cặp (Stores x
Mô hình separation logic cho phép biểu diễn các lệnh trong chương trình có chứa con trỏ, bao gồm cấp phát bộ nhớ, truy xuất, thay đổi giá trị ô nhớ và hủy bộ nhớ.
Trạng thái của chương trình có thể được mô tả bằng logic phân tách thông qua các thao tác như cấp phát, truy xuất, thay đổi giá trị ô nhớ và hủy ô nhớ.
Hình 2.2: Minh họa trạng thái chương trình qua các lệnh (nguồn [12])
Ký hiệu [E] biểu diễn giá trị tại ô nhớ E Ở hình 2.2, giả sử chương trình ban đầu có 2 biến x và y trỏ đến 2 ô nhớ có địa chỉ tương ứng là 3 và 4
- Lệnh x := cons(1,2) khai báo biến x trỏ đến ô nhớ trong heap có giá trị là 1, và ô nhớ tiếp theo ô nhớ này trong heap có giá trị là 2
- Lệnh y := [x] gán biến y trỏ đến ô nhớ có địa chỉ là nội dung của biến x
- Lệnh [x+1] := 3; thay đổi giá trị của ô nhớ tại địa chỉ x + 1
- Lệnh dispose(x+1): hủy ô nhớ tại địa chỉ x+1
Ví dụ 2.2: Minh họa việc dùng separation logic để có thể phát hiện lỗi trong chương trình, ở ví dụ này là lỗi truy xuất đến con trỏ null
Hình 2.3: Minh họa dùng separation logic để phát hiện lỗi chương trình (nguồn [12])
2.1.2.2 Các toán tử của separation logic
Separation logic, bên cạnh các toán tử trong Hoare logic, cung cấp thêm một số toán tử hữu ích cho việc biểu diễn heap Trong đó, toán tử emp biểu diễn một heap rỗng, e e’ thể hiện một heap chứa một ô nhớ duy nhất tại địa chỉ e với giá trị e’ Ngoài ra, p 1 * p 2 cho phép chia heap thành hai phần không giao nhau là p 1 và p 2, trong khi p 1 - * p 2 cũng đóng vai trò quan trọng trong việc quản lý heap.
Hoare logic chỉ có thể biểu diễn trạng thái của chương trình thông qua ánh xạ từ tên biến đến giá trị của biến trong các chương trình không chứa con trỏ Đối với các chương trình có con trỏ, Hoare logic không thể diễn tả trường hợp con trỏ trỏ đến ô nhớ cụ thể Để giải quyết vấn đề này, Separation logic đã giới thiệu toán tử , e e’, thể hiện rằng con trỏ e đang trỏ đến ô nhớ có giá trị e’.
Ví dụ 2.3: int * p = new int();
Bí danh là một vấn đề quan trọng trong lập trình, đặc biệt là khi sử dụng Hoare logic, vì nó không thể xác định liệu các con trỏ có trỏ đến cùng một địa chỉ bộ nhớ hay không Để giải quyết vấn đề này, Separation logic đã giới thiệu toán tử *, với p1 * p2 biểu thị rằng hai vùng nhớ heap không giao nhau, từ đó loại bỏ khả năng xảy ra bí danh.
Ví dụ 2.4: Minh họa cho trường hợp p và q trỏ đến 2 vùng nhớ khác nhau int * p = new int(); int * q = new int();
Sau đây là một số ví dụ dùng separation logic để biểu diễn trạng thái của chương trình
Ví dụ 2.5 minh họa rằng x3,y biểu diễn x trỏ đến hai ô nhớ liên tiếp trong heap Ô nhớ đầu tiên mà x trỏ đến có giá trị 3, trong khi ô nhớ tiếp theo chứa giá trị y Cụ thể, x ánh xạ đến địa chỉ α với giá trị 3, và ô nhớ tiếp theo tại địa chỉ α + 1 ánh xạ đến giá trị β.
Tương tự cho trường hợp
Công thức x3,y y3,x chỉ ra rằng có hai phần heap không giao nhau Phần đầu tiên được trỏ bởi x, chứa hai ô nhớ liên tục với giá trị 3 và y, trong khi phần thứ hai được trỏ bởi y, chứa hai ô nhớ liên tục với giá trị 3 và x.
Ví dụ 2.7: x3,y y3,x: biểu diễn 2 heap giao nhau, tức x và y trỏ đến cùng một ô nhớ
Separation logic rất hữu ích trong việc mô tả các cấu trúc dữ liệu phức tạp, yêu cầu việc mô tả chi tiết các hình thức cấu trúc và mối quan hệ giữa các trạng thái của chương trình với các giá trị trừu tượng mà chúng đại diện Ví dụ, để biểu diễn cấu trúc danh sách trong separation logic, chúng ta sử dụng các định nghĩa với α và β là những chuỗi.
• [x] là một chuỗi một phần tử duy nhất chứa x
• α.β là một chuỗi tạo ra bằng cách thêm β vào α
• α + là một dạng nghịch đảo (reflection) của α
• αi là phần tử thứ i trong chuỗi α
• list α(i, j) là một danh sách từ i tới j biểu diễn cho chuỗi α
Ví dụ 2.8: minh họa danh sách liên kết đơn
Chúng ta có thể định nghĩa bằng phương pháp quy nạp cho danh sách theo cấu trúc của α như sau: list (i,j) def emp i=j lista i j ji def
. ) , ( a,j list (j,k), và sử dụng định nghĩa này để chứng minh một số thuộc tính cơ bản cho danh sách list a(i, j) ia, j
) , (i k j list i j list j k list list b(i,k) j.list (i,j) jb,k
Ví dụ 2.9: minh họa xóa phần tử đầu tiên của một danh sách
Ngoài ra, separation logic còn dung cho những chương trình phức tạp hơn như đảo các phần tử của một danh sách
Ví dụ 2.10 : minh họa chương trình đảo các phần tử của một danh sách (nguồn [12])
Danh sách liên kết đôi (doubly-linked list) được biểu diễn bằng dlist α(i, i’, j, j’) cho chuỗi α từ i đến j và từ j’ ngược về i’ Định nghĩa quy nạp cho danh sách liên kết đôi được đưa ra như sau: dlist (i, i’, j, j’) được định nghĩa là emp khi i = j và i’ = j’ Trong trường hợp khác, dlist a (i, i’, k, k’) sẽ có j i α.
Từ định nghĩa này ta có thể suy luận ra các thuộc tính cơ bản sau cho danh sách liên kết đôi: dlist a (i, i ’ , j, j ’ ) ia, j, i ’ i=j ’ dlist i,i ' ,k,k ' j, j ' dlist i,i ' ,j, j ' dlist j, j ' ,k,k ' dlist b i,i ' ,k,k ' j ' dlist i,i ' ,k ' , j ' k ’ b, k, j ’
Phần này bổ sung các tiên đề cho phép suy luận trong logic phân tách dựa trên tiền điều kiện và hậu điều kiện, bên cạnh các tiên đề đã được giới thiệu trong logic Hoare.
Hình 2.4 : Các tiên đề áp dụng trên separation logic (nguồn [12]) x: = E là một phép gán bình thường giống như trong Hoare logic
Tiên đề đầu tiên cho rằng nếu E trỏ đến một ô nhớ có giá trị bất kỳ, khi gán nội dung của ô nhớ mà E trỏ đến cho F, thì nội dung tại ô nhớ E sẽ trở thành F Điều này có nghĩa là một con trỏ chỉ trỏ tới một ô nhớ cụ thể.
• Tiên đề thứ hai phát biểu rằng nếu chúng ta sử dụng hàm dispose(E), thì ô nhớ được trỏ bởi E sẽ được trả lại cho hệ thống
HIP
HIP là một hệ thống kiểm tra tự động cho các chương trình viết bằng ngôn ngữ mệnh lệnh đơn giản, dựa trên logic phân tách (separation logic) Hệ thống này có khả năng kiểm tra các chương trình thao tác trên con trỏ, cho phép người dùng định nghĩa các vị từ dưới dạng công thức của logic phân tách để mô tả hình dạng và thuộc tính của cấu trúc dữ liệu, như chiều cao, chiều dài và tập hợp giá trị Người dùng cũng cần chỉ định tiền điều kiện và hậu điều kiện cho mỗi phương thức hoặc vòng lặp trước khi tiến hành kiểm tra tự động HIP chuyển đổi các công thức logic phân tách sang các công thức thuần túy có thể được hiểu bởi các công cụ chứng minh định lý như Omega, Mona, CVC Lite hoặc Isabelle.
HIP, được phát triển bởi giáo sư Chin Wei Ngan tại Đại học Quốc gia Singapore, là một công cụ kiểm tra chương trình tự động yêu cầu kiến thức tối thiểu về separation logic từ người dùng Bên cạnh đó, HIP còn đóng góp quan trọng cho cả lĩnh vực nghiên cứu và ngành công nghiệp.
2.2.2 Kiến trúc của hệ thống HIP
Hình 2.5: Kiến trúc của HIP (nguồn [16])
HIP được phát triển bằng ngôn ngữ OCaml, một ngôn ngữ lập trình hàm nổi tiếng, được sáng tạo bởi một nhà nghiên cứu người Pháp và hiện đang được sử dụng rộng rãi.
Trong hệ thống HIP, người dùng phải cung cấp các thông tin sau:
• Định nghĩa các vị từ để mô tả cấu trúc dữ liệu
• Định nghĩa tiền điều kiện và hậu điều kiện cho các phương thức cần kiểm tra
HIP có 2 thành phần chính: Hoare-style Forward Verifier và Entailment Prover
Hoare-style Forward Verifier yêu cầu đầu vào là mã chương trình và các tiền/hậu điều kiện do người dùng định nghĩa Thành phần này hoạt động dựa trên tập luật forward rules {∆1}code{∆2}, trong đó Δ1 là tiền điều kiện và Δ2 là hậu điều kiện Dựa vào các luật này, thành phần sẽ kiểm tra từng phương thức để xác định liệu hậu điều kiện có được đảm bảo sau khi thực thi chương trình với tiền điều kiện đã cho hay không.
Entailment Prover là công cụ kiểm tra tính đồng nhất của các heap node dựa trên các vị từ định nghĩa cấu trúc dữ liệu mà người dùng cung cấp, giúp xác định xem có sự trùng lặp hay bí danh giữa chúng hay không.
2.2.3 Ngôn ngữ đặc tả của HIP
HIP định nghĩa một văn phạm cho ngôn ngữ bên trong hệ thống HIP (gọi là core language) để sử dụng cho quá trình chứng minh như sau:
Hình 2.6: Văn phạm của HIP định nghĩa core language (nguồn [16])
2.2.4 Cơ chế kiểm tra tự động của HIP
Trước khi tiến hành kiểm tra, HIP chuyển đổi ngôn ngữ đầu vào thành ngôn ngữ cốt lõi (core language) Sau đó, HIP sử dụng tập luật forward để thực hiện kiểm tra Dựa trên tập luật này, HIP kiểm tra từng phương thức nhằm xác định xem hậu điều kiện có được đảm bảo sau khi thực thi chương trình với tiền điều kiện đã cho hay không.
Do các prover chỉ có khả năng hiểu các công thức cơ bản như số nguyên và boolean, HIP thực hiện việc chuyển đổi các công thức trong separation logic sang các công thức thuần túy, chỉ sử dụng các kiểu dữ liệu cơ bản, trước khi gửi chúng đến các prover để tiến hành kiểm tra.
2.2.5 Mô tả chương trình input của HIP
Cấu trúc chương trình input của HIP gồm các phần chính sau đây:
Khai báo dữ liệu ( ví dụ như khai báo các cấu trúc node,…) Định nghĩa các vị từ cho cấu trúc dữ liệu bằng separation logic
Khai báo các phương thức, định nghĩa các tiền điều kiện và hậu điều kiện cho các phương thức)
Kiểu dữ liệu cơ bản được sử dụng trong HIP mà các prover có thể hiểu được là kiểu nguyên (int) và kiểu luận lý(bool)
Ví dụ 2.12: chương trình định nghĩa danh sách liên kết trong HIP
/* representation of a node */ data node { int val; node next;
/* view for a singly linked list */ ll == self = null & n = 0 or self::node * q::ll inv n >= 0;
/* function to insert a node in a singly linked list */ void insert(node x, int a) requires x::ll & n > 0 ensures x::ll;
//dprint; node tmp = null; if (x.next == null) x.next = new node(a, tmp); else insert(x.next, a);
Phần khai báo cấu trúc dữ liệu
Cấu trúc node bao gồm hai thuộc tính chính: đầu tiên là một số nguyên, được gọi là val, và thứ hai là một con trỏ next, trỏ đến node tiếp theo trong cấu trúc dữ liệu Để định nghĩa vị từ cho cấu trúc dữ liệu này, ta sử dụng logic phân tách (separation logic).
Công thức trong HIP được biểu diễn ở dạng chuẩn hội (disjunctive normal form), ví dụ như: A or B Mỗi phần hội có thể có 2 thành phần:
- công thức số học thuần túy (pure formula) ll == self = null & n = 0 or self::node * q::ll inv n >= 0; data node { int val; node next;
Trong HIP, công thức p::c(v*) biểu diễn 2 trường hợp:
Nếu c là tên của cấu trúc dữ liệu, thì p::c(v*) biểu thị rằng con trỏ p trỏ đến cấu trúc dữ liệu mang tên c, với v* là danh sách đối số thể hiện nội dung của cấu trúc dữ liệu đó.
Ví dụ: p::node: có nghĩa là con trỏ p trỏ đến node có giá trị của thuộc tính val là x và con trỏ next là q
Nếu c là vị từ, thì p::c(v*) tương đương với công thức c(p,v*) Trong HIP, mỗi vị từ có một thông số ngầm định là self, đóng vai trò như một con trỏ “root” để trỏ đến cấu trúc dữ liệu đặc tả Con trỏ self được sử dụng để duyệt qua cấu trúc dữ liệu và hỗ trợ định nghĩa các vị từ well-founded.
Ví dụ: q::ll: có nghĩa là con trỏ q trỏ đến vị từ ll có một thông số là (n-
1) Lúc đó con trỏ ngầm định self của vị từ ll sẽ tương đương với q
Vị từ ll định nghĩa một danh sách liên kết có chiều dài n Danh sách liên kết này sẽ là hội của 2 trường hợp:
- trường hợp danh sách rỗng, biểu diễn bởi (self = null & n = 0) Công thức này gồm có 2 thành phần, thành phần công thức heap là
(self = null) và thành phần thứ hai là công thức ở dạng số học thuần túy (pure formula) là (n = 0)
- trường hợp danh sách khác rỗng, biểu diễn bởi
Danh sách liên kết hiện tại bao gồm một node dữ liệu được trỏ bởi con trỏ “root” là self, cùng với cấu trúc dữ liệu tiếp theo được định nghĩa đệ quy là danh sách liên kết ll với chiều dài n-1, được trỏ bởi con trỏ next của node đầu tiên, q::ll Toán tử * đảm bảo rằng node dữ liệu đầu tiên và phần danh sách còn lại thuộc về hai heap không giao nhau.
Công thức định nghĩa vị từ ll không chỉ mô tả bất biến (invariant) n >= 0 mà còn được thể hiện dưới dạng công thức thuần túy (pure formula), đảm bảo tính chính xác cho mọi danh sách ll.
Khai báo các phương thức, định nghĩa các tiền điều kiện và hậu điều kiện cho các phương thức)
Phương thức insert(node x, int a) thêm node có giá trị là a vào danh sách liên kết được trỏ đến bởi x như con trỏ “root”
- Định nghĩa tiền điều kiện (pre-condition) cho phương thức insert của danh sách liên kết requires x::ll & n > 0
Tiền điều kiện của phương thức insert lúc này là đảm bảo danh sách phải khác rỗng và có chiều dài là n trước khi insert node a vào danh sách
- Định nghĩa hậu điều kiện (post-condition) cho phương thức insert ensures x :: ll < n +1>;
Sau khi thêm node a vào danh sách, điều kiện hậu phải đảm bảo rằng x trỏ đến danh sách có chiều dài n+1, với điều kiện tiền đã được thỏa mãn.
Người dùng có khả năng định nghĩa nhiều tiền điều kiện và hậu điều kiện cho một phương thức HIP cung cấp cơ chế để đặc tả các tiền/hậu điều kiện này thông qua lệnh case.
/* function to insert a node in a singly linked list */ void insert(node x, int a) requires x::ll & n > 0 ensures x::ll;
{ node tmp = null; if (x.next == null) x.next = new node(a, tmp); else insert(x.next, a);
Kỹ thuật concolic testing
Concolic testing là một kỹ thuật kết hợp giữa thực thi chương trình dựa trên input cụ thể và thực thi symbolic, được coi là một phương pháp hiệu quả để sinh test-case trong kiểm tra chương trình Kỹ thuật này sử dụng thực thi symbolic cùng với bộ chứng minh định lý tự động hoặc bộ giải ràng buộc để tạo ra các input cụ thể nhằm tối đa hóa độ bao phủ code Mục tiêu chính của concolic testing là phát hiện lỗi trong chương trình thay vì chỉ chứng minh tính đúng đắn của nó.
Về cơ bản, giải thuật concolic testing hoạt động như sau:
1 Phân loại tập các biến đầu vào Các biến này sẽ được coi là các biến symbolic trong quá trình thực thi symbolic Tất cả các biến khác sẽ được xem là các giá trị cụ thể
2 Cải tiến chương trình sao cho mỗi tác vụ có thể ảnh hưởng đến giá trị của một biến symbolic hoặc một điều kiện đường dẫn (path condition) sẽ được lưu lại trong một file, cũng như khi bất kỳ lỗi xảy ra
3 Chọn một tập các giá trị đầu vào tùy ý để bắt đầu thực thi chương trình
5 Thực thi symbolic chương trình trên các tập tin lưu được, tạo ra một tập các ràng buộc symbolic (gồm các điều kiện đường dẫn)
6 Phủ định điều kiện cuối cùng chưa từng được phủ định của điều kiện đường dẫn để thực thi chương trình theo một đường thực thi mới Nếu không có điều kiện đường dẫn nào như vậy, giải thuật dừng
7 Gọi một bộ chứng minh định lý tự động (prover) để sinh ra một đầu vào mới Nếu không có đầu vào thỏa mãn các ràng buộc, lặp lại bước 6 để thử các đường thực thi tiếp theo
Bảng 2.1 Ví dụ minh họa cho concolic testing void foo (int x, int y)
Trong chương trình được trình bày trong bảng 2.1, có hai điều kiện nhánh chính là (x ! y) và (2*x = x + 10) Kỹ thuật kiểm thử hộp trắng (white-box testing) sẽ được áp dụng để kiểm tra các điều kiện này.
Khi áp dụng kỹ thuật concolic testing, cần xem xét ba điều kiện đường dẫn Đầu tiên, thuật toán sẽ sinh ngẫu nhiên các giá trị cho x và y, ví dụ: x = 1 và y = 2 Trong quá trình thực thi chương trình với các giá trị cụ thể, dòng lệnh 0 sẽ được thực thi vì điều kiện (x != y) đúng, nhưng dòng lệnh 1 không được thực thi do điều kiện (2*x = x + 10) không thỏa mãn Quá trình thực thi symbolic sẽ xử lý x và y như các biến symbolic, và các điều kiện (x != y) và (2*x != x + 10) trở thành điều kiện đường dẫn Để thực hiện một đường dẫn khác trong lần chạy tiếp theo, concolic testing sẽ phủ định điều kiện cuối cùng (2*x != x + 10) để có điều kiện mới (2*x = x + 10) Một bộ chứng minh tự động sẽ được sử dụng để tìm giá trị đầu vào cho x và y thỏa mãn điều kiện mới này.
Khi thực thi chương trình với các giá trị inputs 10 và 5, sẽ xảy ra lỗi Áp dụng kỹ thuật concolic testing, chúng ta chỉ cần kiểm tra 2 nhánh của chương trình để phát hiện lỗi, mà không cần duyệt qua tất cả các đường thực thi có thể.
Kỹ thuật slicing
Static Slicing là kỹ thuật phân tích mã nguồn chương trình dựa trên việc trích xuất tập hợp các câu lệnh Quá trình này được thực hiện theo một tiêu chí nhất định, gọi là slicing criterion.
Tiêu chí slice: trong đó, là câu lệnh của chương trình chứa kết quả ta cần quan tâm; là tập slice sẽ được trích xuất ra từ chương trình P
Phương pháp Static Slicing chủ yếu dựa vào đồ thị phụ thuộc của chương trình
Đồ thị phụ thuộc chương trình (Program Dependence Graph - PDG) là công cụ quan trọng trong kỹ thuật cắt (slice) PDG được xây dựng dựa trên hai loại phụ thuộc chính: phụ thuộc dữ liệu và phụ thuộc điều khiển, giúp phân tích và tối ưu hóa mã nguồn hiệu quả hơn.
Đồ thị phụ thuộc chương trình (PDG) là một công cụ quan trọng trong việc phân tích các câu lệnh trong chương trình, trong đó các node đại diện cho các câu lệnh như lệnh gán, đọc ghi dữ liệu, hoặc các lệnh điều kiện như if-then-else và switch-case Trong PDG, có hai loại cạnh chính: cạnh phụ thuộc dữ liệu và cạnh phụ thuộc điều khiển Sự phụ thuộc dữ liệu xảy ra khi một câu lệnh (node v_i) sử dụng giá trị của một biến mà câu lệnh khác (node v_j) đã thiết lập, dẫn đến một cạnh từ v_i đến v_j Ngược lại, sự phụ thuộc điều khiển tồn tại khi việc thực thi của một câu lệnh (node v_i) phụ thuộc vào điều kiện của một câu lệnh khác (node v_j), tạo ra một cạnh điều khiển từ v_i đến v_j trong đồ thị PDG.
Bảng 2.1 Chương trình minh họa cho PDG
Hình 2.8 : Đồ thị phụ thuộc chương trình (PDG) cho chương trình ở bảng 2.1
Giải thuật Static Slicing sử dụng PDG để xác định các câu lệnh có ảnh hưởng đến biến quan tâm Bắt đầu từ node liên quan đến câu lệnh chứa biến đó, Static Slicing sẽ tìm tất cả các node phụ thuộc, bao gồm cả phụ thuộc dữ liệu và phụ thuộc điều khiển, sau đó lặp lại quá trình này với các node vừa tìm được.
Dựa vào PDG của chương trình, tập slice trích xuất được với tiêu chí C = (9, x.data) sẽ bao gồm các dòng lệnh như hình dưới đây:
Bảng 2.2 Ví dụ minh họa cho PDG int func (node x, int a) requires x::ll & n>0 ensures x::ll;
{ if (a < 0) x.data++; else x.data ; return x.data;
Khi áp dụng phương pháp Static Slicing, nếu tiêu chí được chọn dẫn đến việc trích xuất tập slice toàn bộ chương trình, thì hiệu quả của phương pháp này sẽ giảm sút đáng kể.
Thêm vào đó, khi ta debug chương trình với nhiều input đầu vào khác nhau
Mặc dù tiêu chí slice không thay đổi, tập slice được trích xuất vẫn giống nhau trong mọi trường hợp Điều này dẫn đến việc Static Slicing không hỗ trợ tốt cho việc gỡ lỗi với một đầu vào cụ thể Mỗi đầu vào khác nhau sẽ kích hoạt một tập hợp các câu lệnh khác nhau, do đó chỉ có một phần nhỏ trong tập thực thi đó mới có khả năng chứa lỗi của chương trình.
Vì vậy cần có một phương pháp tiếp cận khác để slice chương trình dựa vào một input cụ thể
Dynamic Slicing is an innovative approach that addresses the limitations of Static Slicing It utilizes Execution History (EH) and Definition/Use Program Representation (D/U) to extract a slice set effectively.
Execution History là một tập hợp có thứ tự các câu lệnh đã được thực thi khi chương trình nhận một input cụ thể Ví dụ, với input x::ll và a = -2, Execution History sẽ là Trong đó, chỉ số bên dưới đại diện cho ID của câu lệnh, được xác định dựa trên thứ tự của câu lệnh trong Execution History.
Chương trình Representation (D/U) là một cấu trúc quan trọng dùng để đại diện cho chương trình, bao gồm ba thành phần cơ bản: i, d và U Trong đó, i là ID của các câu lệnh, d là tên biến được định nghĩa (đối với lệnh gán), hoặc biểu thức điều kiện (ký hiệu p cho lệnh rẽ nhánh) hoặc biểu thức return (ký hiệu o) U đại diện cho các biến và câu lệnh mà i j phụ thuộc vào Đặc biệt, giá trị d trong mỗi dòng chỉ chứa một giá trị duy nhất, trong khi U có thể chứa nhiều giá trị khác nhau.
Bảng 2.3: Ví dụ minh họa tập D/U của chương trình trong bảng 2.1 i d U
Tiêu chí slice của phương pháp Dynamic Slicing bao gồm C = (x, i j , V)
Trong đó, x là input đầu vào của chương trình, i j là câu lệnh thuộc EH có chứa kết quả cần quan tâm, V là tập slice được trích xuất
Với tiêu chí slice C = (x ::ll a = -2, 9 4 , V), tập slice V được xác định là Trong tập V, lệnh số 8 không xuất hiện vì nó không ảnh hưởng đến kết quả của chương trình khi sử dụng test-case x ::ll a = -2.
Hình 2.9: Giải thuật Dynamic Slicing (nguồn [20])
Trong đó: LS là ID của câu lệnh i j
Sau đây là ví dụ minh hoạ cho giải thuật Dynamic Slicing cho chương trình ở bảng 2.1 với C = (x ::ll a = -2, 9 4 , V), khi đó:
Bảng 2.4: Minh họa giải thuật Dynamic Slicing cho chương trình trong bảng 2.1 i j d U DynSlice(d) LS(d)
Xem chương trình minh họa ở bảng 2.5
Bảng 2.5: Chương trình minh họa cho giải thuật Relevant Slicing
Giả sử input của chương trình ở bảng 2.5 là x::ll Khi đó lịch sử thực thi
EH của chương trình là EH =
Nếu ta chọn tiêu chí slice C = (x::ll, 10 6 , V) và áp dụng phương pháp
Dynamic Slicing thì ta được tập slice V =
Phương pháp Dynamic Slicing tuy hiệu quả hơn nhiều so với phương pháp
Mặc dù Static Slicing là một công cụ hữu ích, nó vẫn tồn tại những hạn chế Ví dụ, nếu chương trình có lỗi ở câu lệnh số 7 do lập trình viên nhập sai điều kiện (a>0 thay vì a>=0), chương trình sẽ chạy sai Ngoài ra, nếu điều kiện ở câu lệnh số 7 đúng nhưng câu lệnh số 6 lại sai (cần là int a = 1), thì câu lệnh số 8 sẽ không được thực thi, dẫn đến kết quả không chính xác Do đó, tập slice trích xuất từ chương trình cần phải bao gồm cả các câu lệnh số 6 và số 7 để đảm bảo tính chính xác.
6 và số 7 nữa mới đảm bảo tính đầy đủ của các câu lệnh tiềm ẩn lỗi dẫn đến kết quả sai
Giải thuật Relevant Slicing được phát triển dựa trên nền tảng của giải thuật
Dynamic Slicing Relevant Slcing cũng dựa vào Execution History và D/U Program Represen-tation để thực hiện slice Thêm vào đó, Relevant Slicing phát triển đồ thị
Extended Program Dependence Graph (EPDG) bằng cách thêm các cạnh
Conditional Flow Edge (cạnh phụ thuộc điều kiện) vào đồ thị PDG (của phương pháp Static Slicing)
Phụ thuộc điều kiện (Conditional Dependence) là khái niệm trong lập trình, trong đó câu lệnh m phụ thuộc vào câu lệnh p nếu có ít nhất một câu lệnh n sao cho câu lệnh m phụ thuộc dữ liệu vào n, và n lại phụ thuộc điều khiển vào p Điều này tạo ra mối quan hệ phụ thuộc điều kiện giữa m và p, được biểu thị qua cạnh phụ thuộc điều kiện (conditional flow edge) giữa chúng.
Hình 2.10 Minh họa phụ thuộc điều kiện
Giải thuật Relevant Slicing có ưu điểm hơn giải thuật Dynamic Slicing ở chỗ
Slicing liên quan đến việc thêm các câu lệnh điều kiện có thể ảnh hưởng đến kết quả, trong khi Dynamic Slicing sẽ loại bỏ những câu lệnh điều kiện không tác động đến kết quả cuối cùng.
Phụ thuộc tiềm ẩn (Potential Dependence) xảy ra khi câu lệnh m phụ thuộc vào câu lệnh p, tức là trong quá trình thực thi, cả hai câu lệnh này đều được thực hiện, với câu lệnh p được thực hiện trước m Điều quan trọng là trong đường thực thi từ p đến m, không có câu lệnh n nào được thực thi.
Hình 2.11: Minh họa giải thuật Relevant Slicing (nguồn [20])
LP(d): thứ tự của câu lệnh hiện hành trong EH
RelSlice: tập hợp chứa các câu lệnh đã được slice theo giải thuật Relevant
PotDep(d): chứa các câu lệnh u mà d và u có potential dependence
DataDepSet (PotDep(d)): chứa các câu lệnh u mà các câu lệnh v (v
PotDep(d)) phụ thuộc dữ liệu vào u
DataDep(p): với p PotDep(d) thì DataDep(p) chứa các câu lệnh u mà p có phụ thuộc dữ liệu vào u
Giả sử input của chương trình ở bảng 2.5 là x::ll Khi đó lịch sử thực thi
EH của chương trình là EH =
Nếu ta chọn tiêu chí slice C = (x::ll, 10 6 , V) và áp dụng phương pháp Relevant Slicing thì ta được tập slice V =
Bảng 2.6: Minh họa giải thuật Relevant Slicing cho chương trình trong bảng
Hệ thống sinh logic test-case dựa trên kỹ thuật slicing
Các tiền đề
Bảng 3.1: Xóa i phần tử đầu tiên của một danh sách liên kết
/*function of remove the first i elements of a singly linked list*/
1 void remove_heads (node x, int i)
6 //extra code for some other calculation that might not be relevant to the data structure x
Trong phần này, chúng ta sẽ minh họa một ví dụ để làm rõ vấn đề nghiên cứu trong luận văn Bảng 3.1 trình bày chương trình thực hiện việc xóa phần tử đầu tiên của một danh sách liên kết, trong đó có thể xảy ra lỗi khi danh sách liên kết rỗng Khi kiểm tra chương trình trong Listring 3, nhiều provers sẽ không thành công do cần có bất biến trong vòng lặp, ngay cả với các hệ thống xử lý con trỏ như HIP Việc suy diễn bất biến cho vòng lặp là một thách thức lớn đối với lập trình viên, do đó, người ta thường dựa vào thử nghiệm để phát hiện lỗi Bằng cách áp dụng phương pháp concolic testing, các giá trị đầu vào ngẫu nhiên được sinh ra, ví dụ, x:: ll và i = 0 Khi chạy chương trình với các giá trị này, mã nguồn trong vòng lặp while không được thực thi Tiếp theo, phủ định điều kiện (i % 2 = 0) dẫn đến (i 0 i % 2 != 0).
Khi ta có điều kiện 2 != 0 và (i > 0 i % 2 = 0), từ đó có thể xác định giá trị cụ thể cho các biến đầu vào, ví dụ như x ::ll và i = 2 Tuy nhiên, trong hai lần thực thi với hai test-case (x::ll i = 1) và (x::ll i = 2), mã trong vòng lặp while được thực thi nhưng vẫn không phát hiện lỗi.
Chúng tôi mong muốn phát triển các test-case bao gồm cả danh sách liên kết rỗng và không rỗng Để đạt được điều này, phương pháp concolic testing cần được mở rộng để phân tích không chỉ control-flow của chương trình mà còn cả phần đặc tả của các thông số Nghiên cứu này không nhằm tạo ra các test-case cụ thể mà chỉ sinh ra các công thức trong separation logic Tương ứng với hai trường hợp danh sách và bốn control-flow của chương trình, chúng tôi có tổng cộng tám trường hợp.
Khi áp dụng kỹ thuật concolic testing, có thể cần đến 8 test-case để duyệt qua tất cả các đường thực thi của chương trình Tuy nhiên, không phải tất cả các đường thực thi đều ảnh hưởng đến kết quả mà chúng ta quan tâm Chúng ta chỉ cần sinh ra một test-case cho những đường thực thi có cùng tác động đến kết quả đó Trong ví dụ, nếu chúng ta chỉ quan tâm đến kết quả cuối cùng của biến danh sách liên kết x, các dòng code từ dòng 6 đến dòng 11 không ảnh hưởng đến kết quả của biến x Để giảm bớt số lượng test-case cần sinh ra, nghiên cứu sẽ áp dụng kỹ thuật slicing, giúp rút gọn chương trình thành phiên bản nhỏ hơn chỉ chứa các dòng lệnh thực sự ảnh hưởng đến kết quả Sau khi loại bỏ phần code không cần thiết, số đường thực thi sẽ giảm và chúng ta chỉ cần sinh ra những test-case cần thiết.
Sau đó, dùng một solver để sinh ra các test-case cụ thể hơn như sau:
Các test-case được sinh ra từ công thức (1’) hoặc (2’) giúp phát hiện lỗi khi chạy chương trình, vì vậy chúng được gọi là logic test-case Những test-case này hỗ trợ hệ thống sinh ra các test-case thực (real test-case) tương ứng Phần tiếp theo sẽ bàn luận chi tiết về framework tạo logic test-case dựa trên slicing cho các chương trình thao tác trên heap.
Hệ thống sinh logic test-case hoàn chỉnh
Pure constraint Pure test case
Hình 3.1: Hệ thống sinh logic test-case dựa trên kỹ thuật slicing
Framework hoàn chỉnh cho hệ thống sinh logic test-case dựa trên kỹ thuật slicing được trình bày trong hình 3.1 Framework này bao gồm hai module chính: module slicing và module sinh test-case.
Module Slicing có nhiệm vụ sinh ra tập slice cho các test-case tương ứng và tạo điều kiện đường dẫn (path condition) liên quan Module này bao gồm ba thành phần chính.
Bộ tính toán Đồ thị phụ thuộc chương trình và Tập biểu diễn Defined/Used (PDG & Defined/Use Calculator) sử dụng mã nguồn của chương trình để tạo ra một đồ thị phụ thuộc và dạng biểu diễn.
Defined/Used tương ứng với chương trình
Bộ giả lập thực thi chương trình (Execution simulator) sẽ chạy chương trình với một test-case cụ thể, từ đó tạo ra lịch sử thực thi (execution history) tương ứng với test-case đó.
Bộ thực thi giải thuật Relevant slicing (Relevant slicing algorithm): nhận
The PDG (Program Dependence Graph) and the Defined/Used representation of a program are derived from the program's dependence analysis and the Defined/Used set This representation, along with the program execution history for a given test case from the program execution simulator, serves as input for the relevant slicing algorithm The relevant slicing algorithm generates the corresponding slice set and creates path conditions that are utilized by the test case generation module.
Module sinh test-case bao gồm 4 quá trình chủ yếu sau:
Constraint Combination involves merging the specifications, particularly the preconditions of a function, with the path conditions obtained from module slicing This process results in the creation of combined constraints that enhance the analysis of program behavior.
Chuyển đổi sang pure logic (Pure Logic Conversion) là quá trình chuyển các ràng buộc từ bước Kết hợp ràng buộc thành công thức ở dạng pure logic, tạo ra những ràng buộc gọi là pure constraints Mặc dù việc chuyển đổi từ separation logic sang pure logic là đúng đắn (sound) nhưng không hoàn toàn (complete), tôi đề xuất một tập luật mang tên Luật Mở rộng (expansion rules) Tập luật này được suy diễn từ đặc tả của cấu trúc dữ liệu trong chương trình và sẽ được mô tả chi tiết trong chương 4.
Pure test-case generation involves utilizing a prover to resolve constraints in pure logic form, resulting in the creation of corresponding test cases, known as pure test cases.
Test-case restoration is the process of converting pure test cases from step 3 into logic test cases using separation logic This process employs restoration rules, which will be elaborated in detail in Chapter 4.
Quá trình sinh test-case dựa trên kỹ thuật slicing sẽ được tóm tắt qua các bước sau
Khi xét chương trình trong Bảng 3.1, giá trị đầu vào được sinh ngẫu nhiên là x::ll i = 0 Khi thực thi, vòng lặp while không hoạt động do điều kiện (i = loop) Kết quả là điều kiện đường dẫn (path condition) là (i % 2 = 0 và i 0 x.next = 0 Khi prover Z3 giải ràng buộc này, giá trị n = 2 được thu được, nhưng giá trị này không chính xác vì x.next = 0 n > 0, nghĩa là danh sách chỉ có 1 phần tử.
Bảng 4.7: Hàm thực hiện insert một node vào danh sách liên kết đơn
/* function to insert a node into a singly linked list */ void insert(node x, int a) requires x::ll & n > 0 ensures x::ll;
{ node tmp = null; if (x.next == null) x.next = new node(a, tmp); else insert(x.next, a);
Nguyên nhân dẫn đến kết quả thiếu chính xác là do mất thông tin về mối quan hệ giữa x và x.next khi chuyển đổi từ separation logic sang pure logic Chúng ta cần lưu trữ mối quan hệ này để suy ra x.next::ll Khi hệ thống suy luận được x.next::ll và thêm vào ràng buộc đầu tiên, ta có ràng buộc mới x::ll n > 0 x.next null x.next::ll, được gọi là ràng buộc mở rộng (expanded constraint) Áp dụng Xpure trên ràng buộc mở rộng này, ta có thể tạo ra các ràng buộc pure logic [(x = 0 n = 0) (x > 0 n > 0)] n > 0 x.next = 0 [(x.next = 0 n-1 = 0) (x.next > 0 n-1 > 0)] Từ các ràng buộc này, chúng ta có thể phân chia thành các trường hợp khác nhau.
Trong 4 trường hợp trên, chỉ có trường hợp 3 là khả thỏa mãn (satisfiable), giải trường hợp 3 bằng prover Z3 chúng ta thu được test-case ở dạng pure logic chính xác, ví dụ x = 2 x.next = 0 n = 1 Để suy luận ra những ràng buộc mở rộng từ những ràng buộc kết hợp ban đầu, luận văn phát triển một tập luật gọi là luật mở rộng (expansion rules) sẽ được trình bày chi tiết trong phần này Trong phần trình bày tập luật mở rộng, ký hiệu p::c(v * ) biểu thị cho hai trường hợp sau trong hệ thống:
Nếu c là tên của một cấu trúc dữ liệu, chẳng hạn như Node, thì p::c(v *) biểu diễn một singleton heap pα[(v) * ], trong đó v * là các thuộc tính của phần khai báo dữ liệu c.
Nếu c là tên vị từ, thì p::c(v *) biểu diễn công thức c(p, v *), với p là tham số ẩn self của vị từ và v * là các tham số của vị từ Để thuận tiện, luận văn sử dụng lại các ký hiệu tương tự như trong hệ thống HIP.
: biểu diễn những công thức độc lập với heap (heap-independent)
: biểu diễn những công thức liên quan đến heap ở dạng separation logic
4.2.1 Luật mở rộng (Expansion rules)
4.2.1.1 Luật lưu trữ dữ liệu (Rules for capturing data) Để lưu trữ thông tin bị mất đi khi thực hiện chuyển đổi từ separation logic sang pure logic, chúng ta định nghĩa hai function Store và Store 0 , được trình bày trong hình 4.1 Mục đích của tập luật này là để suy diễn thêm các công thức hợp lý từ công thức ban đầu
Store self p v c p Store v c c edicate is
Hình 4.1: Luật lưu trữ dữ liệu
Xét công thức = x::ll và vị từ ll = (self = null n = 0) (self::node
* q::ll) Gọi là phần thân của định nghĩa vị từ ll, = (self = null n = 0) (self::node * q::ll) Áp dụng hàm Store 0 lên , chúng ta có:
Store 0 ( ) = Store 0 (self = null n = 0) Store 0 (self::node * q::ll) = (self = null n = 0) [Store 0 (self::node) Store 0 (q::ll)] = (self = null n = 0) [(self.val = _ self.next = q) (q::ll)]
[p self Store 0 biểu diễn phép thay thế self bằng p trong công thức Store 0 ( )
Vì vậy, Store (x::ll) = [x/self] Store 0 ( )
Kết quả đạt được từ bước Store có tính chất đệ quy do vị từ ll được định nghĩa theo cách đệ quy Tiếp theo, chúng ta sẽ áp dụng luật thay thế trong bước tiếp theo để có được công thức mở rộng cuối cùng.
4.2.1.2 Luật thay thế (Substitution Rule-SR)
Nếu kết quả của hàm Store có dạng đệ quy, chúng ta sẽ áp dụng luật thay thế
Substitution Rule để suy diễn ra công thức mở rộng Luật thay thế Substitution Rule được định nghĩa như sau:
Khi xác định được vị trí của vị từ trong cấu trúc đệ quy, chúng ta có thể áp dụng hàm Store cho công thức heap x:: c(v x * ) Kết quả thu được từ quá trình này sẽ giúp chúng ta hiểu rõ hơn về cách thức hoạt động của vị từ trong ngữ cảnh đệ quy.
Vì vị từ c(v*) có dạng well-founded theo định nghĩa trong HIP, nên q có thể tiến đến từ x Để đảm bảo rằng q có khả năng truy xuất trực tiếp từ x, q cần phải là một thuộc tính (field) của x Để đạt được điều này, chúng ta áp dụng luật thay thế SR cho đến khi q có thể được truy xuất trực tiếp từ x.
Xét ràng buộc đầu tiên trong bảng 4.7, x::ll với n > 0, có x.next = null Ràng buộc mới cần bao gồm công thức x.next::ll, trong đó ll được định nghĩa đệ quy Từ kết quả trong ví dụ 4.1, ta có Store(x::ll) = (x = null, n = 0) [(x.val = _ x.next = q) (q::ll)] Lưu ý rằng q không thể truy xuất trực tiếp từ x, do đó, áp dụng luật thay thế Substitution Rule SR là cần thiết.
Chúng ta có x.next::ll, cho phép truy xuất trực tiếp từ x Do đó, luật thay thế không còn áp dụng, và ràng buộc mới là x::ll với n > 0 Khi x.next null, x.next::ll được tạo ra bằng cách thêm công thức suy diễn x.next::ll vào ràng buộc ban đầu.
4.2.1.3 Luật đệ quy (Recursive Rule-RR)
Trong những trường hợp phức tạp, ràng buộc kết hợp không chỉ đơn giản chứa công thức x.next mà còn có thể bao gồm x.next.next, x.next.next.next, và nhiều hơn nữa Do đó, việc suy diễn x.next.next::ll, x.next.next.next::ll, là cần thiết Luật đệ quy Recursive Rule RR sẽ hỗ trợ chúng ta trong việc giải quyết vấn đề này.
Giả sử có khai báo dữ liệu d(v d *) và p::c(v *) p.v d ::c(u *) với v d là thuộc tính của khai báo dữ liệu d(v d *) Gọi g i là ánh xạ từ miền các giá trị có thể của v i (d(v i )) đến miền các giá trị có thể của u i (d(u i )) với g i (v i ) = u i, i Luật đệ quy RR được phát biểu như sau:
Ví dụ 4.3: Ở ví dụ 4.2, sau khi áp dụng luật thay thế SR, chúng ta có x.next::ll
Ban đầu, chúng ta có x::ll Áp dụng quy tắc đệ quy RR với ánh xạ g(x) = x-1, ta nhận được x.next.next::ll Tiếp tục áp dụng quy tắc này, ta có thể dễ dàng suy luận x.next.next.next::ll và tiếp tục nếu cần thiết.
4.2.2 Luật phục hồi test-case (Restoration rules)
Bước cuối cùng trong quá trình sinh test-case là chuyển đổi các test-case từ pure logic sang separation logic Luật phục hồi, hay Restoration Rule, được đề xuất dựa trên các heuristic Quá trình phục hồi này bao gồm hai bước chính.