Phân Tích MUST-MAY Để Kiểm Tra Chương Trình

Luận văn thạc sĩ về phân tích MUST-MAY để kiểm tra chương trình trong lĩnh vực khoa học máy tính. Nghiên cứu các kỹ thuật kiểm thử và ứng dụng thực tế.

• Tác giả: Lê Thị Nhật Văn
• Người hướng dẫn: Ts. Quản Thành Thơ
• Trường học: Trường Đại học Bách Khoa
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Phân Tích MUST-MAY để kiểm tra chương trình
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2012
• Địa điểm: Tp. Hồ Chí Minh

Tóm tắt

I. Tổng Quan Phân Tích MUST MAY Trong Kiểm Thử Luận Văn

Lỗi chương trình là một thách thức lớn trong lập trình hiện đại. Các công cụ kiểm tra phần mềm tự động, phân loại thành hai nhóm chính: phân tích MUST (under-approximate) và phân tích MAY (over-approximate). Phân tích MUST chứng minh sự tồn tại lỗi, trong khi phân tích MAY chứng minh chương trình không có lỗi. Tuy nhiên, mỗi phương pháp đều có nhược điểm: phân tích MUST gây ra false-negatives và phân tích MAY gây ra false-positives. Gần đây, sự kết hợp giữa hai kỹ thuật này đã được nghiên cứu để tăng độ chính xác và hiệu quả của công cụ kiểm tra. Kiểm thử phần mềm dựa trên test-case vẫn là một kỹ thuật phổ biến. Kiểm tra hộp trắng (white-box testing) dựa trên phân tích luồng thực thi. Tuy nhiên, nó có thể dẫn đến bùng nổ trạng thái. Kỹ thuật concolic testing giúp giảm thiểu việc duyệt qua các đường thực thi, nhưng không đảm bảo phủ hết các trường hợp kiểm tra, đặc biệt với các chương trình thao tác trên heap. Đề tài này tập trung vào xây dựng hệ thống sinh test-case cho chương trình thao tác trên heap dựa trên ngữ nghĩa của separation logic. Hệ thống sẽ mở rộng concolic testing bằng cách kết hợp đặc tả cấu trúc dữ liệu và luồng thực thi. Kỹ thuật slicing được sử dụng để cải thiện hiệu quả sinh test-case.

1.1. Tìm Hiểu Kỹ Thuật Phân Tích MUST Trong Kiểm Thử

Kỹ thuật phân tích MUST tập trung vào việc chứng minh rằng một thuộc tính cụ thể chắc chắn xảy ra trong một số đường thực thi của chương trình. Mục tiêu là tìm ra lỗi bằng cách chứng minh rằng một điều kiện lỗi cụ thể (ví dụ, truy cập con trỏ null) có thể xảy ra. Tuy nhiên, vì không thể duyệt hết tất cả các đường thực thi trong các chương trình lớn, phân tích MUST có thể bỏ sót lỗi, dẫn đến false negatives. Ví dụ, các công cụ như [1][2][3] được đề cập trong tài liệu gốc sử dụng phương pháp này.

1.2. Phân Tích MAY Chứng Minh Tính Đúng Đắn Của Chương Trình

Phân tích MAY cố gắng chứng minh rằng một thuộc tính nhất định luôn đúng trên tất cả các đường thực thi của chương trình. Nếu phân tích MAY thành công, chương trình được coi là không có lỗi liên quan đến thuộc tính đó. Tuy nhiên, kỹ thuật này có thể dẫn đến false positives, tức là báo cáo lỗi khi thực tế không có lỗi. Các tài liệu tham khảo [4][5][6] nghiên cứu về phân tích MAY. Việc cân bằng giữa phân tích MUST và phân tích MAY là rất quan trọng.

II. Vấn Đề Và Thách Thức Trong Kiểm Thử Heap Luận Văn

Một thách thức lớn trong kiểm thử chương trình là xử lý các chương trình thao tác trên heap, đặc biệt là khi sử dụng con trỏ. Kỹ thuật concolic testing có những hạn chế nhất định trong trường hợp này, vì nó không xem xét đầy đủ các đặc tả của cấu trúc dữ liệu chia sẻ. Vấn đề bí danh (aliasing) cũng làm phức tạp quá trình kiểm tra, vì một đối tượng có thể được truy cập thông qua nhiều con trỏ khác nhau. Điều này làm cho việc đảm bảo độ bao phủ kiểm thử trở nên khó khăn hơn. Vì vậy, cần có một phương pháp tiếp cận mới, kết hợp thông tin về cấu trúc dữ liệu và luồng điều khiển, để giải quyết những thách thức này. Hệ thống được đề xuất trong luận văn này sử dụng separation logic để mô hình hóa trạng thái của heap và kết hợp với kỹ thuật slicing để giảm thiểu số lượng test-case cần thiết.

2.1. Hạn Chế Của Concolic Testing Với Chương Trình Heap

Kỹ thuật concolic testing thường không đủ mạnh để xử lý các chương trình thao tác trên heap. Phương pháp này không sử dụng thông tin về đặc tả cấu trúc dữ liệu, do đó không thể kiểm tra tất cả các trường hợp có thể xảy ra với cấu trúc dữ liệu đó. Điều này đặc biệt quan trọng đối với các cấu trúc dữ liệu phức tạp như danh sách liên kết hoặc cây, nơi có nhiều trường hợp biên và điều kiện khác nhau cần được kiểm tra.

2.2. Vấn Đề Bí Danh Con Trỏ Khó Khăn Trong Kiểm Thử

Vấn đề bí danh xảy ra khi hai hoặc nhiều con trỏ cùng trỏ đến một vị trí bộ nhớ. Điều này làm cho việc phân tích và kiểm tra chương trình trở nên phức tạp, vì một thay đổi thông qua một con trỏ có thể ảnh hưởng đến kết quả thông qua con trỏ khác. Separation logic cung cấp một cách để mô hình hóa và giải quyết vấn đề bí danh bằng cách đảm bảo rằng mỗi con trỏ chỉ sở hữu một phần riêng biệt của heap.

2.3. Độ Bao Phủ Kiểm Thử Đảm Bảo Phát Hiện Lỗi Toàn Diện

Đảm bảo độ bao phủ kiểm thử đầy đủ là một thách thức lớn. Với các chương trình lớn và phức tạp, việc kiểm tra tất cả các đường dẫn thực thi có thể là không khả thi. Kỹ thuật slicing được sử dụng để giảm số lượng test-case cần thiết bằng cách chỉ tập trung vào các phần của chương trình có liên quan đến một tiêu chí cụ thể, như giá trị của một biến hoặc một điều kiện lỗi.

III. Phương Pháp Sáng Tạo Sinh Logic Test Case Dựa Trên Slicing

Luận văn đề xuất một hệ thống sinh logic test-case dựa trên kỹ thuật slicing cho các chương trình được viết bằng ngôn ngữ HIP. Hệ thống này kết hợp concolic testing với separation logic và slicing để tạo ra các test-case hiệu quả. Mục tiêu là giảm số lượng test-case cần thiết trong khi vẫn đảm bảo độ bao phủ kiểm thử đầy đủ. Hệ thống sử dụng separation logic để mô hình hóa trạng thái của heap và slicing để loại bỏ các phần không liên quan của chương trình. Các test-case được biểu diễn dưới dạng các công thức logic, cho phép phân tích và suy luận tự động.

3.1. Kết Hợp Concolic Testing Separation Logic Slicing

Hệ thống kết hợp ba kỹ thuật mạnh mẽ: concolic testing, separation logic, và slicing. Concolic testing được sử dụng để tạo ra các test-case dựa trên việc thực thi chương trình với cả giá trị cụ thể và biểu tượng. Separation logic cung cấp một cách để mô hình hóa trạng thái của heap và xử lý vấn đề bí danh. Slicing giúp giảm số lượng test-case cần thiết bằng cách chỉ tập trung vào các phần liên quan của chương trình.

3.2. Sử Dụng Ngôn Ngữ HIP Để Biểu Diễn Chương Trình

Hệ thống được thiết kế để làm việc với các chương trình được viết bằng ngôn ngữ HIP (Heap-manipulating Imperative Programs). HIP là một ngôn ngữ đặc biệt được thiết kế để phân tích và chứng minh các chương trình thao tác trên heap. Nó cung cấp các tính năng như đặc tả dữ liệu và suy luận tự động.

IV. Giải Pháp Chi Tiết Cho Slicing Và Sinh Test Case Hiệu Quả

Luận văn trình bày các giải pháp chi tiết cho việc triển khai kỹ thuật slicing và sinh logic test-case. Các giải pháp này bao gồm các luật mở rộng (expansion rules) và luật phục hồi test-case (restoration rules). Các luật mở rộng được sử dụng để mở rộng miền của các test-case, trong khi các luật phục hồi được sử dụng để khôi phục các test-case bị loại bỏ trong quá trình slicing. Các giải pháp này giúp đảm bảo rằng hệ thống sinh test-case tạo ra các test-case chính xác và hiệu quả.

4.1. Các Giải Pháp Sáng Tạo Cho Cơ Chế Slicing

Việc triển khai kỹ thuật slicing đòi hỏi các giải pháp sáng tạo để đảm bảo rằng slice được trích xuất là chính xác và đầy đủ. Các giải pháp này phải xem xét các yếu tố như phụ thuộc dữ liệu, phụ thuộc điều khiển và các vấn đề bí danh. Cần phải đảm bảo trích xuất được slice chính xác để không bỏ sót các phần quan trọng.

4.2. Luật Mở Rộng Expansion Rules Để Tạo Test Case Đa Dạng

Luật mở rộng được sử dụng để tạo ra các test-case đa dạng bằng cách mở rộng miền của các giá trị đầu vào. Điều này giúp tăng độ bao phủ kiểm thử và phát hiện các lỗi tiềm ẩn. Các luật này phải được thiết kế cẩn thận để tránh tạo ra các test-case không hợp lệ hoặc không liên quan.

4.3. Luật Phục Hồi Test Case Restoration Rules Duy Trì Tính Toàn Diện

Luật phục hồi được sử dụng để khôi phục các test-case đã bị loại bỏ trong quá trình slicing. Điều này giúp đảm bảo rằng không có lỗi nào bị bỏ sót. Các luật này phải được thiết kế để chỉ khôi phục các test-case thực sự cần thiết.

V. Kết Quả Thực Nghiệm Đánh Giá Hiệu Quả MUST MAY Luận Văn

Luận văn trình bày kết quả thực nghiệm và đánh giá hiệu quả của hệ thống sinh logic test-case. Các thử nghiệm được thực hiện trên một loạt các chương trình ví dụ, và kết quả cho thấy rằng hệ thống có thể tạo ra các test-case hiệu quả với độ bao phủ kiểm thử cao. Hệ thống cũng được so sánh với các phương pháp kiểm thử khác, và kết quả cho thấy rằng nó có hiệu quả hơn trong việc phát hiện lỗi. Ví dụ bảng 4,5,6,7, trong chương 4 luận văn. Chương 6 sẽ đi sâu vào kết quả thực nghiệm.

5.1. Điều Kiện Thử Nghiệm Đảm Bảo Tính Khách Quan

Các điều kiện thử nghiệm được thiết lập để đảm bảo tính khách quan và công bằng. Các chương trình ví dụ được chọn phải đại diện cho nhiều loại ứng dụng khác nhau. Các phương pháp kiểm thử so sánh phải được thực hiện với các tham số tối ưu. Quan trọng nhất là đánh giá khách quan các kết quả thu được.

5.2. Đánh Giá Độ Bao Phủ Kiểm Thử Phát Hiện Lỗi

Độ bao phủ kiểm thử và khả năng phát hiện lỗi là các tiêu chí quan trọng để đánh giá hiệu quả của hệ thống. Độ bao phủ kiểm thử được đo bằng tỷ lệ các dòng mã được thực thi bởi các test-case. Khả năng phát hiện lỗi được đo bằng số lượng lỗi được tìm thấy bởi các test-case.

VI. Kết Luận Hướng Phát Triển Cho Phân Tích MUST MAY Luận Văn

Luận văn đã trình bày một hệ thống sinh logic test-case dựa trên kỹ thuật slicing cho các chương trình được viết bằng ngôn ngữ HIP. Hệ thống này kết hợp concolic testing với separation logic và slicing để tạo ra các test-case hiệu quả. Kết quả thực nghiệm cho thấy rằng hệ thống có thể tạo ra các test-case hiệu quả với độ bao phủ kiểm thử cao. Luận văn cũng đề xuất một số hướng phát triển trong tương lai, chẳng hạn như mở rộng hệ thống để hỗ trợ các ngôn ngữ lập trình khác.

6.1. Tóm Tắt Các Đóng Góp Chính Của Luận Văn

Luận văn đã đóng góp vào lĩnh vực kiểm thử phần mềm bằng cách đề xuất một phương pháp mới để sinh logic test-case. Phương pháp này kết hợp các kỹ thuật hiện có một cách sáng tạo để tạo ra các test-case hiệu quả hơn. Việc sử dụng separation logic và slicing là các đóng góp quan trọng.

6.2. Mở Rộng Hệ Thống Hướng Tới Tương Lai Của MUST MAY

Trong tương lai, hệ thống có thể được mở rộng để hỗ trợ các ngôn ngữ lập trình khác như C++ hoặc Java. Nó cũng có thể được tích hợp với các công cụ kiểm thử hiện có. Ngoài ra, nghiên cứu thêm về các kỹ thuật slicing tiên tiến có thể cải thiện hơn nữa hiệu quả của hệ thống. Kỹ thuật phân tích MUST-MAY còn nhiều tiềm năng phát triển.

Trích đoạn nội dung tài liệu

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 Phân tích MUST-MAY để kiểm tra chương trình 17 Chƣơng 2 Các kiến thức nền tảng 2.1 Tổng quan về separation logic Separation logic [12][13] là logic mở rộng của Hoare logic [14], được dùng để suy diễn cho chương trình sử dụng cấu trúc dữ liệu chia sẻ (mutable data structure). Cấu trúc dữ liệu chia sẻ, tức cấu trúc mà một thuộc tính của nó có thể được tham khảo từ nhiều hơn một con trỏ, thường xảy ra vấn đề bí danh. Đây là một vấn đề gây khó khăn trong việc kiểm tra tính đúng đắn của chương trình. Chúng ta không thể sử dụng Hoare logic để kiểm tra chương trình có chứa các con trỏ vì có thể xảy ra vấn đề bí danh.

Vì vậy, Peter O'Hearn-Đại học London và John Reynolds-Đại học Carnegie Mello đã phát triển separation logic từ Hoare logic bằng cách thêm 2 toán tử mới: spatial conjunction (*) và spatial implication (-*) và một số tiên đề trên separation logic giúp cho việc chứng minh những chương trình có chứa con trỏ.2 Ngữ nghĩa của separation logic 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. StoresV V Integers trong đó: + V: tập các biến + Integers: tập các số nguyên biểu diễn giá trị của biến Tuy nhiên, đối với các chương trình có chứa con trỏ, với cách biểu diễn này ta không thể biểu diễn được trường hợp bí danh (tức 2 con trỏ cùng trỏ đến một địa chỉ Phân tích MUST-MAY để kiểm tra chương trình 18 bộ nhớ). Vì vậy, separation logic đề xuất thêm thành phần thứ 2 là heap. Mô hình của separtion logic sẽ có 2 thành phần: store và heap.

Khái niệm store tương tự như khái niệm của stack trong ngôn ngữ lập trình, chức năng của nó là ánh xạ từ các biến đến miền giá trị số nguyên (miền số nguyên này biểu diễn địa chỉ mà biến đó trỏ đến). Heap là ánh xạ đi từ miền địa chỉ ô nhớ (miền này là 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 lúc này sẽ được biểu diễn bằng 2 thành phần (Store x Heap).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 Heaps). Với mô hình này, separation logic có thể biểu diễn các lệnh như cấp phát bộ nhớ, truy xuất, thay đổi giá trị ô nhớ, cũng như hủy bộ nhớ trong các chương trình có chứa con trỏ.1: Trạng thái của chương trình có thể được biểu diễn bằng separation logic qua các lệnh cấp phát, truy xuất, thay đổi giá trị ô nhớ và hủy ô nhớ. Phân tích MUST-MAY để kiểm tra chương trình 19 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.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. Phân tích MUST-MAY để kiểm tra chương trình 20 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.2Các toán tử của separation logic Bên cạnh các toán tử được sử dụng trong Hoare logic, separation logic cung cấp thêm một số toán tử sau để thuận tiện trong việc biểu diễn heap. emp: biểu diễn một heap rỗng e  e’: heap chứa một ô nhớ duy nhất, tại địa chỉ e và có giá trị là e’. p1 * p2 : heap được chia thành 2 phần heap không giao nhau là p1 và p2 p1 - * p2: Như ta đã biết, 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ó chứa con trỏ, để biểu diễn trạng thái của chương trình, Hoare logic không thể biểu diễn trường hợp một con trỏ đang trỏ đến một ô nhớ nào đó, như trong ví dụ 2. Separation logic đã đề xuất toán tử  , e  e’ biểu diễn cho con trỏ e đang trỏ đến một ô nhớ có giá trị e’.3: int * p = new int(); *p = 3; Thứ hai là vấn đề bí danh, Hoare logic không thể biểu diễn được trường hợp các Phân tích MUST-MAY để kiểm tra chương trình 21 con trỏ có trỏ đến cùng một địa chỉ bộ nhớ hay không. Separation logic đã đề xuất toán tử *, p1 * p2 biểu diễn 2 vùng nhớ heap là không giao nhau, lúc này sẽ không xảy ra vấn đề bí danh.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(); *p = 3; *q = 2; 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: x  3, y : biểu diễn x trỏ đến 2 ô nhớ liên tục trong heap. Ô nhớ x trỏ đến có giá trị là 3, ô nhớ kế tiếp có giá trị là y (tức là, store ánh xạ x đến giá trị α và y đến giá trị β, α là một địa chỉ, khi đó heap ánh xạ α đến giá trị là 3 và ánh xạ địa chỉ α + 1 đến giá trị β) Tương tự cho trường hợp Ví dụ 2.6: x  3, y y  3, x : công thức này có nghĩa là: 2 phần heap không giao nhau, phần thứ nhất chứa 2 ô nhớ liên tục có giá trị lần lượt là 3 và y, và được trỏ đến bởi x, phần thứ hai chứa 2 ô nhớ liên tục là 3 và x, và được trỏ đến bởi y.

Phân tích MUST-MAY để kiểm tra chương trình 22 Ví dụ 2.7: x  3, y y  3, x: biểu diễn 2 heap giao nhau, tức x và y trỏ đến cùng một ô nhớ Bên cạnh đó, separation logic còn rất hữu dụng trong việc mô tả các cấu trúc dữ liệu phức tạp. Để đặc tả chương trình một cách đầy đủ, cần phải mô tả nhiều hơn về các hình thức cấu trúc của nó và mối quan hệ giữa các trạng thái của chương trình đối với các giá trị trừu tượng mà chúng biểu thị. Cho ví dụ, để biểu diễn cấu trúc danh sách trong separation logic, chúng ta có các định nghĩa sau, với α và β là những chuỗi: • ε là chuỗi rỗng • [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 α • # α là độ dài 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 Phân tích MUST-MAY để kiểm tra chương trình 23 của α như sau: def list (i,j) emp i=j def list a (i, j ) j.9: minh họa xóa phần tử đầu tiên của một danh sách { list a (i, k ) } { j. i 1  j list ( j , k ) } j:=[i+1]; { i  a i 1  j list ( j , k ) } dispose i; {i 1  j list ( j , k )} dispose i+1; {list ( j , k )} i:=j {list (i, k )} 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]) Phân tích MUST-MAY để kiểm tra chương trình 24 Ví dụ 2.11: Biểu diễn danh sách liên kết đôi (doubly-linked list) (nguồn [12]) dlist α(i, i’, j, j’) biểu diễn danh sách liên kết đôi 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 như sau: def dlist (i, i’, j, j’) emp i=j i’=j’ def dlist a (i, i’, k, k’) j.

dlist i, i ' , j , j ' dlist j, j ' , k , k ' dlist b i, i ' , k , k ' j ' .3 Các tiên đề Phần này trình bày thêm các tiên đề cho phép suy luận trên separation logic dựa vào tiền điều kiện và hậu điều kiện, ngoài các tiền đề đã được giới thiệu trong Hoare logic. E E : F EF E dispose E emp x m x : cons E1 ,.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 phát biểu rằng nếu E trỏ vào một ô nhớ có giá trị bất kỳ thì sau đó khi gán nội dung của ô nhớ mà E trỏ đến cho F, thì cuối cùng ta sẽ có nội dung tại ô nhớ E là F. Ý nghĩa của tiên đề này là một con trỏ chỉ trỏ tới một ô nhớ.

• 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. • Tiên đề thứ ba phát biểu rằng ban đầu, x được gán cho giá trị m trong store, tức x trỏ đến ô nhớ có địa chỉ m. Sau đó, x được gán cho k giá trị liền kề E1, .,Ek trong heap và x trỏ tới giá trị đầu tiên E1.