ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

BÙI THỊ THƯ

ỨNG DỤNG KỸ THUẬT DIỄN GIẢI TRỪU
TƯỢNG TRONG PHÂN TÍCH BỘ NHỚ HEAP

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

Hà Nội – 2014


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

BÙI THỊ THƯ

ỨNG DỤNG KỸ THUẬT DIỄN GIẢI TRỪU
TƯỢNG TRONG PHÂN TÍCH BỘ NHỚ HEAP

Ngành: Công nghệ thông tin
Chuyên ngành: Kỹ thuật phần mềm
Mã số: 60480103

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Nguyễn Trường Thắng

Hà Nội – 2014

1

LỜI CAM ĐOAN
Tôi xin cam đoan rằng đây là công trình nghiên cứu của tôi trong đó có sự
giúp đỡ của Thầy giáo hướng dẫn và các đồng nghiệp tại cơ quan. Các nội dung
và kết quả nghiên cứu trong luận văn này là hoàn toàn trung thực.
Trong luận văn, tôi có tham khảo đến một số tài liệu của một số tác giả được
liệt kê tại mục tài liệu tham khảo.
Hà Nội, tháng 03 năm 2014
Học viên

Bùi Thị Thư


2

LỜI CẢM ƠN
Tôi xin chân thành cảm ơn các thầy cô giáo trong Khoa Công nghệ Thông
tin, Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội đã tận tình giảng dạy
trang bị cho tôi kiến thức, giúp tôi hoàn thành luận văn.
Tôicũng xin được bày tỏ lòng kính trọng và lời cảm ơn sâu sắc nhất tới TS.
Nguyễn Trường Thắng, Phó Viện trưởng, Viện Công nghệ Thông Tin – Viện
Hàn lâm Khoa học và Công nghệ Việt Nam. Thầy đã luôn động viên và hướng
dẫn tôi hoàn thành luận văn tốt nghiệp.
Mặc dù đã cố gắng để hoàn thành luận văn, nhưng trong phạm vi và khả
năng cho phép không thể tránh khỏi những thiếu sót, mong nhận được sự cảm
thông và tận tình chỉ bảo của các thầy cô.
Hà Nội, tháng 03 năm 2014
Học viên


Bùi Thị Thư


3

MỤC LỤC
LỜI CAM ĐOAN .............................................................................................. 1
LỜI CẢM ƠN .................................................................................................... 2
MỤC LỤC ......................................................................................................... 3
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT.......................................... 5
DANH SÁCH HÌNH VẼ ................................................................................... 6
MỞ ĐẦU ........................................................................................................... 7
CHƯƠNG 1. GIỚI THIỆU CHUNG.................................................................. 9
1.1.

Vấn đề quản lý bộ nhớ ........................................................................ 9

1.2.

Phân tích chương trình tĩnh ................................................................. 9

1.3.

Các kỹ thuật phân tích chương trình tĩnh........................................... 10

CHƯƠNG 2. LÝ THUYẾT NỀN TẢNG ......................................................... 14
2.1.

Nền tảng phân tích ngữ nghĩa của chương trình ................................ 14

2.1.1. Lý thuyết giàn ......................................................................... 14
2.1.2. Lý thuyết điểm cố định............................................................ 15
2.1.3. Hệ dịch chuyển ....................................................................... 17
2.1.4. Ngữ nghĩa vết .......................................................................... 17
2.1.5. Biểu diễn ngữ nghĩa vết dưới dạng điểm cố định..................... 17

2.2.

Phân tích hình dạng........................................................................... 18

2.3.

Nền tảng diễn giải trừu tượng ........................................................... 20
2.3.1. Phân tích trên miền trừu tượng ................................................ 21
2.3.2. Kết nối Galois ......................................................................... 26
2.3.3. Trừu tượng hóa ngữ nghĩa chương trình .................................. 28
2.3.4. Giàn phân cấp ngữ nghĩa của chương trình ............................. 32
2.3.5. Các kỹ thuật tăng tốc độ hội tụ ................................................ 34

2.4.

Kết luận chương................................................................................ 35

CHƯƠNG 3. ỨNG DỤNG KỸ THUẬT DIỄN GIẢI TRỪU TƯỢNG TRONG
PHÂN TÍCH BỘ NHỚ HEAP VÀ THỰC NGHIỆM ...................................... 36


3.1.

4

Ứng dụng kỹ thuật diễn giải trừu tượng trong phân tích heap............ 36
3.1.1. Heap cụ thể ............................................................................. 36
3.1.2. Trừu tượng hóa heap ............................................................... 37

3.2.

Thực nghiệm ..................................................................................... 39
3.2.1. Giới thiệu TVLA ..................................................................... 39
3.2.2. Đặc tả hệ thống trong TVLA ................................................... 40
3.2.3. Biểu diễn ngữ nghĩa và chương trình....................................... 41
3.2.4. Tinh chỉnh sự trừu tượng hóa .................................................. 43
3.2.5. Ví dụ minh họa........................................................................ 44

KẾT LUẬN...................................................................................................... 50
TÀI LIỆU THAM KHẢO ................................................................................ 51
PHỤ LỤC A..................................................................................................... 53
PHỤ LỤC B ..................................................................................................... 54
PHỤ LỤC C ..................................................................................................... 56
PHỤ LỤC D..................................................................................................... 59
PHỤ LỤC E ..................................................................................................... 60


5

DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT

Ký hiệu
CFG
TVLA


Thuật ngữ
Control Flow Graph
Three - Valued Logic Analysis Engine

DFG

Data Flow Graph

TVS

Three Valued logical Structure

TVP

Three Valued Program

SMT

Satisfiability Modulo Theories

SAT

Satisfiability Testing


6

DANH SÁCH HÌNH VẼ
Hình 1.1. Các thành phần chính của kỹ thuật diễn giải trừu tượng ........... 12
Hình 2.1. Quan hệ thứ tự từng phần là giàn ............................................. 15

Hình 2.2. Quan hệ thứ tự từng phần không phải giàn .............................. 15
Hình 2.3. Tính toán điểm cố định trên giàn ............................................. 16
Hình 2.4. Ngữ nghĩa cụ thể của chương trình .......................................... 22
Hình 2.5. Thuộc tính an toàn ................................................................... 23
Hình 2.6. Kỹ thuật kiểm thử .................................................................... 23
Hình 2.7. Trừu tượng hóa ngữ nghĩa cụ thể ............................................. 24
Hình 2.8. Trừu tượng hóa không đảm bảo tính đủ ................................... 25
Hình 2.9. Trừu tượng hóa không đủ chính xác ........................................ 26
Hình 2.10. Sự trừu tượng hóa bằng kết nối

........................................... 27

Hình 2.11. Cây phân cấp các ngữ nghĩa ................................................... 33
Hình 3.1. Biểu diễn heap cụ thể ............................................................... 37
Hình 3.2. Các toán tử logic ...................................................................... 38
Hình 3.3. Trừu tượng hóa heap ................................................................ 38
Hình 3.4. Kết quả heap trừu tượng đầu ra ................................................ 42
Hình 3.5. Kết quả truy cập trường f ......................................................... 44
Hình 3.6. Thông số phân tích của TVLA ................................................. 49


7

MỞ ĐẦU
Ngày nay với sự phát triển vượt bậc của công nghệ thông tin, thì phần mềm
có vai trò cốt lõi và ngày càng chiếm vị trí quan trọng không những trong công
nghệ thông tin mà còn trong đời sống kinh tế xã hội. Khi đó sự phụ thuộc của
kinh tế xã hội vào phần mềm ngày càng lớn. Chính vì vậy, vấn đề chất lượng
phần mềm (software quality) chắc chắn là mối quan tâm và thách thức đối với
xã hội hiện đại ngày càng phụ thuộc vào các dịch vụ do máy tính đem lại này.

Từ trước đến nay, kĩ thuật kiểm thử thường được sử dụng để kiểm tra chương
trình. Nó đóng vai trò quan trọng trong việc đánh giá và thu được chất lượng cao
của sản phẩm phần mềm trong quá trình phát triển. Thông qua chu trình “kiểm
thử – tìm lỗi – sửa lỗi” ta hy vọng chất lượng của sản phẩm phần mềm sẽ được
cải tiến. Tuy nhiên phương pháp này bộc lộ điểm yếu quan trọng nhất đó là chỉ
có thể khẳng định được chương trình không gặp lỗi đối với các trường hợp kiểm
thử đã kiểm tra, tức là không tìm thấy lỗi chứ không thể khẳng định là chương
trình hoàn toàn không còn lỗi.
Liên quan tới khía cạnh đảm bảo tính năng và chất lượng phần mềm, lĩnh
vực công nghệ phần mềm trên thế giới hiện nay tập trung vào các phương pháp
hình thức (formal methods) trong kiểm chứng chương trình. Bài toán kiểm
chứng chương trình có thể được mô tả đơn giản như sau: Cho trước một chương
trình (program ) và một đặc tả (specification ), kiểm chứng sẽ xác định xem
ngữ nghĩa của chương trình có thỏa mãn đặc tảS trên hay không. Trường hợp
không thỏa mãn, quá trình kiểm chứng sẽ cho biết nguồn gốc lỗi để truy ngược
vết thông qua các phản ví dụ.
Cách tiếp cận này đặc biệt quan trọng đối với các hệ thống cần tính toàn vẹn
cao. Các phương pháp này có thể được sử dụng tại nhiều mức của quá trình phát
triển phần mềm, và nó cố gắng chứng minh một cách tự động rằng chương trình
sẽ thực thi đúng đắn trên mọi môi trường được đặc tả. Mảng nghiên cứu này bao
gồm các phương pháp suy dẫn (deductive methods), kiểm chứng mô hình (model
checking), định kiểu chương trình (program typing), kiểm chứng tĩnh mở rộng
(extended static checking – ESC) và phân tích chương trình tĩnh (static program
analysis). Ba phương pháp đầu tập trung vào việc kiểm chứng phần mềm ở mức
mô hình, trong khi hai nhóm cuối cùng xử lý phần mềm ở mức mã nguồn. Phân
tích chương trình tĩnh thu hút sự quan tâm lớn nhất do nền tảng lý thuyết hình
thức cũng như mục đích đối với các ứng dụng trong thực tế. Kỹ thuật này phát


8

hiện tính chất/hành vi của một chương trình mà không yêu cầu chạy chương
trình đó.
Mục tiêu của luận văn này là tìm hiểu về kỹ thuật phân tích chương trình
tĩnh, cập nhật những xu hướng nghiên cứu trong và ngoài nước về lĩnh vực phân
tích chương trình tĩnh, và cải tiến những kỹ thuật này. Cụ thể, luận văn tập trung
vào nghiên cứu kỹ thuật liên quan tới xấp xỉ ngữ nghĩa được gọi là diễn giải trừu
tượng (abstract interpretation), và thể hiện kỹ thuật này thông qua phân tích
hình dạng bộ nhớ heapdựa trên 3 giá trị logic (shape analysis via three-valued
logic). Tiến hành thực nghiệm trên công cụ TVLA, một công cụ mã nguồn mở
phân tích chương trình viết bằng Java.
Luận văn có cấu trúc như sau:
Chương 1 giới thiệu tổng quan về phân tích chương trình tĩnh. Trong chương
này trình bày định nghĩa kỹ thuật phân tích chương trình tĩnh, ứng dụng, điểm
mạnh và điểm yếu của kỹ thuật này. Tiếp đó luận văn trình bày một vài kỹ thuật
phân tích chương trình tĩnh phổ biến hiện nay, bài toán và kỹ thuật mà luận văn
thực hiện tìm hiểu.
Chương 2 trình bày nền tảng bài toán phân tích chương trình, lý thuyết của
kỹ thuật diễn giải trừu tượng (abstract interpretation).
Chương 3 trình bày về kỹ thuật phân tích hình dạng bộ nhớ heap dựa trên 3
giá trị logic. Thực nghiệm với TVLA – một công cụ mã nguồn mở để phân tích
chương trình.
Cuối cùng là phần kết luận và tài liệu tham khảo.


9

CHƯƠNG 1. GIỚI THIỆU CHUNG
1.1.

Vấn đề quản lý bộ nhớ


Với sự tiến bộ nhanh chóng của cách mạng công nghệ thông tin và chất liệu
chính là phần mềm. Nếu như trước đây phần mềm máy tính chỉ được sử dụng để
tính toán khoa học kỹ thuật và xử lý dữ liệu thì ngày nay nó đã được ứng dụng
vào mọi mặt của đời sống hàng ngày của con người. Vì thế con người ngày càng
phụ thuộc chặt chẽ vào các sản phẩm phần mềm và do vậy đòi hỏi về chất lượng
của các sản phẩm phần mềm ngày càng cao, tức là phần mềm phải được sản
xuất với giá thành thấp, dễ dùng, an toàn và tin cậy được. Đánh giá chất lượng
phần mềm thông thường qua các hoạt động phổ biến như tìm xem phần mềm có
lỗi không và có những kỹ thuật nào để phát hiện các lỗi đó.
Việc phát hiện lỗi hay bất cứ vấn đề gì về sản phẩm đều có thể thực hiện ở
các mức của quá trình sản xuất phần mềm như mức phân tích, mức thiết kế và
mức lập trình. Ở mức lập trình việc phát hiện lỗi trở nên phức tạp và khó giải
quyết hơn. Cụ thể như bài toán quản lý bộ nhớ. Hiện nay, nhiều hệ thống ngôn
ngữ lập trình sử dụng cơ chế quản lý bộ nhớ tự động, tiêu biểu như Java và C#
[1]. Tuy nhiên, một số ngôn ngữ lập trình truyền thống, được sử dụng phổ biến
trong thực tế như C, C++ thì vấn đề quản lý bộ nhớ vẫn được dựa hoàn toàn vào
lập trình viên[14]. Liên quan tới bài toán này kỹ thuật phân tích chương trình
tĩnh của mảng các kỹ thuật kiểm chứng chương trình là có tính ứng dụng và hiệu
quả cao. Và việc áp dụng kỹ thuật phân tích chương trình tĩnh vào trong bài toán
quản lý bộ nhớ sẽ là nội dung chính của luận văn này.
1.2.

Phân tích chương trình tĩnh

Phân tích chương trình tĩnh là kỹ thuật xác định tính chất/ hành vi của một
chương trình mà không cần phải chạy chương trình đó. Kỹ thuật này được xây
dựng dựa trên lý thuyết diễn giải trừu tượng (abstract interpretation)[2][3] để
chứng minh tính chính xác của các phân tích liên quan đến ngữ nghĩa của một
ngôn ngữ lập trình.

Có rất nhiều câu hỏi thú vị liên quan tới chương trình hoặc các điểm (point)
riêng lẻ trong chương trình:
 Chương trình có dừng hay không?
 Độ lớn có thể của vùng nhớheap trong quá trình chạy như thế nào?
 Đầu ra (output) có thể là gì?


10
 Giá trị của sẽ được đọc trong tương lai?
 Điểm và có cấu trúc tách rời nhau trong heap?
 Con trỏ có thể null?
Phân tích chương trình tĩnh có một số ưu điểm sau:
 Chỉ ra được chính xác vị trí lỗi trong chương trình.
 Lỗi được phát hiện sớm trong quy trình phát triển phần mềm nên chi
phí sửa thấp.
 Tự động hóa nhanh: thông qua các công cụ hỗ trợ như TVLA, Astree,
SOOT …
Ngoài ra phân tích này có một số nhược điểm sau:





Không phát hiện được lỗi chỉ xuất hiện khi chạy chương trình.
Mất thời gian nếu thực hiện bằng tay.
Việc tự động hóa chỉ hướng vào một số ngôn ngữ nhất định.
Đòi hỏi nhân lực phải có kiến thức về ngôn ngữ lập trình.

Theo lý thuyết Rice[13], tất cả các câu hỏi liên quan tới hành vi chương
trình là không giải được (undecidable). Việc xử lý vấn đề này luôn đi kèm một

số kĩ thuật xấp xỉ nhằm đưa về bài toán giải được hoặc để tối ưu hóa kết quả.
1.3.

Các kỹ thuật phân tích chương trình tĩnh

Hiện nay, trên thế giới có nhiều hướng nghiên cứu về các kỹ thuật phân tích
chương trình tĩnh. Về các kỹ thuật hình thức phân tích chương trình tĩnh có thể
chia thành 4 hướng chính như sau:
Thứ nhất, kỹ thuật phân tích chương trình tĩnh dựa trên phân tích luồng dữ
liệu (data flow analysis) [12][15].Phân tích luồng dữ liệu là một kỹ thuật thu
thập thông tin về tập các giá trị được tính toán có thể có tại các điểm khác nhau
của chương trình. Thông tin thu được thường được trình biên dịch sử dụng để tối
ưu hóa chương trình. Phân tích luồng dữ liệu là một cách rất hiệu quả và khả thi
trong việc phát hiện lỗi chương trình và tối ưu hóa trong các trình biên dịch.
Cách đơn giản để phân tích luồng dữ liệu là thiết lập phương trình luồng dữ liệu
cho mỗi nút của đồ thị luồng dữ liệu (DFG – data flow graph) và sử dụng thuật
toán điểm cố định để giải hệ phương trình này. Và một số ứng dụng phổ biển
của phân tích luồng dữ liệu là phân tích tính tới được (reaching definitions), biểu
thức có sẵn (available expressions), biểu thức bận rộn (very busy expressions)
và phân tích tính sống (liveness analysis)[15].


11
Thứ hai, nhóm kỹ thuật liên quan tới xấp xỉ ngữ nghĩa được gọi là diễn giải
trừu tượng (abstract interpretation)[2][3]. Kỹ thuật diễn giải trừu tượng dựa trên
nguyên tắc xấp xỉ ngữ nghĩa của chương trình khi kiểm tra đối chiếu sự thỏa
mãn đặc tả. Kỹ thuật này trích ra từ một ngữ nghĩa chuẩn (standard semantics)
trên miền cụ thể (concrete domain) được một ngữ nghĩa trừu tượng(abstract
semantics) đã xấp xỉ và tính toán được (approximate and computable abstract
semantics) trên miền trừu tượng (abstract domain). Quá trình chuyển này không

hoàn toàn tự động mà có thể cần sự tương tác với người dùng để tinh chỉnh
(refinement) các ánh xạ trừu tượng thông qua các tham số đưa vào, bởi vì có
thể đầu tiên tạo ra
(là ngữ nghĩa trừu tượng từ chương trình ) không thỏa
mãn đặc tả , trước hết phải tinh chỉnh chứ không kết luận ngay là không
thỏa mãn do tính không hoàn chỉnh (incompleteness) của kỹ thuật diễn giải
trừu tượng. Thay vì kiểm chứng đặc tả trên , chúng ta kiểm chứng đối với
ngữ nghĩa trừu tượng của . Nếu thỏa mãn bởi , do tính đúng đắn của kỹ
thuật diễn giải trừu tượng, đương nhiên thỏa mãn . Tính ưu việt của kỹ thuật
này là độ phức tạp của nhỏ hơn rất nhiều tùy theo quá trình trừu tượng hóa
(ánh xạ trừu tượng hóa từ vào ) như thế nào.
Trong thực tế, kỹ thuật diễn giải trừu tượng có một thành phần là bộ sinh
(generator) ngữ nghĩa trừu tượng đọc mã nguồn chương trình và tạo ra các ràng
buộc hoặc hệ các phương trình cần được giải bởi máy tính thông qua một thành
phần khác là bộ giải (solver). Cấu trúc các thành phần của kỹ thuật này được mô
tả trong hình 1.1.


12

Hình 1.1.

Các thành phần chính của kỹ thuật diễn giải trừu tượng

Một phương pháp phổ biến là dùng hàm lặp khi giải. Việc tìm nghiệm thông
qua hàm lặp có hạn chế về mặt thời gian (phương pháp không hội tụ sau vô hạn
lần lặp). Các kỹ thuật liên quan tới việc tăng tốc hội tụ cũng được nghiên cứu.
Thứ ba, nhóm kỹ thuật liên quan tới mô hình được gọi là kỹ thuật kiểm
chứng mô hình (Model checking). Kiểm chứng mô hình là kỹ thuật kiểm tra xem
một mô hình của hệ thống có thỏa mãn một tính chất nào đó hay không. Cụ thể

hơn, với mô hình và thuộc tính cho trước, kỹ thuật kiểm tra xem thuộc tính
có thỏa mãn trong mô hình
hay không: | = [9]. Về mặt thực thi, kiểm
chứng mô hình là kỹ thuật tĩnh, nó duyệt qua tất cả các trạng thái, các đường
thực thi có thể có trong mô hình để xác định tính khả thỏa của .Nếu một hệ
thống không thoả mãn một tính chất thì kiểm chứng mô hình sẽ đưa ra phản ví
dụ với một chuỗi các trạng thái và sự kiện liên quan bắt đầu từ trạng thái ban
đầu tới trạng thái lỗi của mô hình. Những tính chất kiểm tra thường là tính sống
(liveness properties), tính an toàn (safety properties) như khả năng không tồn tại
khóa chết (deadlock) hoặc rơi vào những trạng thái nguy hiểm tạo sự cố cho hệ
thống. Nhóm kỹ thuật này tập trung vào các hệ thống hữu hạn trạng thái hoặc
được giảm xuống còn hữu hạn trạng thái bởi sự trừu tượng hóa (abstraction).
Cuối cùng, kỹ thuật phân tích biểu trưng (symbolic analysis) [17]. Kỹ thuật
này là phân tích tĩnh mã nguồn tĩnh, xây dựng các luồng rẽ nhánh trong chương


13
trình dựa trên các nút. Tại các nút tương ứng sẽ là tập hợp các ràng buộc
(constraints) của dữ liệu, biến, tham số. Tại nút khởi tạo chương trình, tập hợp
các ràng buộc là rỗng. Càng đi sâu xuống các nhánh nhỏ, tại các nút con, tập
hợp ràng buộc sẽ được tạo ra từ tập hợp ràng buộc tại nút ngay phía trên cộng
với điều kiện giữa các biến số để có thể rẽ từ nút trên vào nút dưới trong luồng
chảy chương trình. Điểm đặc biệt của kỹ thuật này là các tham số hoàn toàn
được thể hiện bằng ký tự biểu trưng, chứ không phải giá trị cụ thể. Ý tưởng của
phương pháp này là để kiểm thử một nhánh trong chương trình, điều kiện tiên
quyết là dữ liệu tại đầu vào phải thỏa mãn tập hợp các ràng buộc tại nút bắt đầu
nhánh đó. Việc giải các ràng buộc gắn với một nút được thực hiện bởi các bộ
công cụ sẵn có gọi là giải ràng buộc (constraint solver) dựa trên SMT
(Satisfiability Modulo Theories) hay SAT (Satisfiability Testing).
Hai nhóm đầu tập trung vào việc nâng cao chất lượng phần mềm tại mức mã

nguồn, trong khi hai nhóm sau xử lý phần mềm tại mức trừu tượng cao hơn là
mô hình.Hiện nay ở Việt Nam việc sử dụng các phương pháp hình thứctrong
thực tế kiểm chứng phần mềm còn nhiều hạn chế. Trong các mảng của phương
pháp hình thức thì mảng phân tích chương trình tĩnh sử đụng diễn giải trừu
tượng có nhiều lợi thế khi sử dụng thực tế, với khả năng tự động sinh được mô
hình ngữ nghĩa trừu tượng từ mã nguồn để kiểm chứng và có thể áp dụng cho
các hệ thống vô hạn trạng thái. Tuy nhiên đây lại là mảng chưa nhận được nhiều
sự quan tâm nghiên cứu như hai mảng còn lại.
Với tình hình nghiên cứu cơ bản và xu thế công nghệ phần mềm trên thế giới
hiện nay tập trung vào các vấn đề lớn như quy mô và chất lượng của các sản
phẩm phần mềm, kỹ thuật diễn giải trừu tượng là một dải nghiên cứu và ứng
dụng quan trọng đối với ngành công nghệ phần mềm. Việc tiến hành nghiên cứu
trong lĩnh vực này là cần thiết trong việc nâng cao chất lượng nghiên cứu ứng
dụng vào thực tế kiểm soát chất lượng phần. Do đó, luận văn sẽ tập trung vào
nhóm các kỹ thuật liên quan tới xấp xỉ ngữ nghĩa là diễn giải trừu tượng.


14

CHƯƠNG 2. LÝ THUYẾT NỀN TẢNG
2.1.

Nền tảng phân tích ngữ nghĩa của chương trình

2.1.1. Lý thuyết giàn
Một thứ tự từng phần (Partial order) là một cấu trúc toán học[15]: = ( , ⊑
), trong đó là một tập hợp và ⊑ là một quan hệ 2 ngôi trên thỏa mãn các điều
kiện sau:
 Phản xạ: ∀ ∈ ∶ ⊑
 Bắc cầu: ∀ , , ∈ ∶

 Phản đối xứng: ∀ , ∈

⊑
∶

∧
⊑

⊑
∧

⇒
⊑
⊑
⇒

=

Cho
⊆ , khi đó
∈ được gọi là một cận trên của , kí hiệu là
⊑ , nếu ∀ ∈ ∶
⊑ .Tương tự ∈ được gọi là một cận dưới của
, kí hiệu là ⊑ , nếu ∀ ∈ ∶
⊑ . Cậntrên nhỏ nhất của kí hiệu là
⊔ , được định nghĩa như sau:
⊑⊔

∧∀


∈

∶

⊑

⇒⊔

⊑

Tương tự, cận dưới lớn nhất, kí hiệu là ⊓ , được định nghĩa như sau:
⊓

⊑

∧∀

∈

∶

⊑

⇒

⊑⊓

Giàn (Lattice) là một quan hệ thứ tự từng phần mà trong đó ⊔ và ⊓ tồn
tại đối với tất cả ⊆ . Lưu ý rằng một giàn có duy nhất một phần tử lớn nhất
⊤ được định nghĩa là ⊤ = ⊔S và duy nhất một phần tử nhỏ nhất ⊥ được định

nghĩa là ⊥ = ⊓ .
Khi xem xét các giàn hữu hạn, yêu cầu ít nhất là tồn tại phần tử lớn nhất và
nhỏ nhất và với mỗi cặp phần tử x và y có một cận trên nhỏ nhất kí hiệu là
⊔ và cận dưới nhất nhất kí hiệu là ⊓ .
Một quan hệ thứ tự từng phần hữu hạn được minh họa bởi một biểu đồ trong
đó các phần tử là các nút và quan hệ thứ tự là quan hệ bao đóng bắc cầu
(transitive closure) các cạnh từ nút thấp lên nút cao hơn. Với cách biểu diễn này
các quan hệ thứ tự trong Hình 2.1 đều là giàn.


15

Hình 2.1. Quan hệ thứ tự từng phần là giàn
Trong khi các quan hệ thứ tự trong hình 2.2 không phải là giàn.

Hình 2.2. Quan hệ thứ tự từng phần không phải giàn
Ví dụ mỗi tập hợp hữu hạn phần tử A định nghĩa một giàn(2 , ⊆), trong đó
⊥ = ∅, ⊤ = , ⊔
= ∪ , và ⊓
= ∩ .
Chiều cao của một giàn được định nghĩa là độ dài của đường dẫn dài nhất từ
phần tử ⊥ tới phần tử ⊤.
Để so sánh các ngữ nghĩa của một chương trình, diễn giải trừu tượng chỉ ra
rằng tất cả ngữ nghĩa của một chương trình có thể được tổ chức dạng phân cấp
theo quá trình trừu tượng hóa. Quan sát việc tính toán ở các mức độ trừu tượng
khác nhau, người ta thấy có thể sử dụng xấp xỉ điểm cố định (approximate
fixpoints) để tổ chức các ngữ nghĩa của một chương trình thành một giàn. Quan
hệ thứ tự của giàn dựa trên việc so sánh tính chính xác giữa các ngữ nghĩa trừu
tượng được tạo ra [2].
2.1.2. Lý thuyết điểm cố định

Hàm ∶
→ là đơn điệu khi∀ , ∈ ∶ ⊑
hợp của hai hàm đơn điệu là một hàm đơn điệu [15].

⇒ ( ) ⊑ ( ). Lưu ý

Lý thuyết về điểm cố định như sau: trong một giàn L có chiều cao hữu hạn,
mỗi hàm đơn điệu f có duy nhất một điểm cố định nhỏ nhất (least fixed-point)
định nghĩa như sau:
( )=

(⊥)


16
thỏa mãn ( ( )) =
( ). Chứng minh lý thuyết này như sau. Ta có
⊥⊑ (⊥) do ⊥là phần tử nhỏ nhất. Do f là hàm đơn điệu nên (⊥) ⊑ (⊥) và
bằng phép quy nạp ta có (⊥) ⊑
(⊥). Do đó, ta có chuỗi tăng dần:
⊥⊑
Do

(⊥) ⊑

(⊥) · · ·

được giả định là có chiều cao hữu hạn nên sẽ tồn tại

mà


(⊥) =

+1

(⊥). Chúng ta định nghĩa
( ) =
(⊥) và từ ( ( )) =
(⊥
) =
(⊥) =
( ), chúng ta thấy
( ) là một điểm cố định. Bây giờ giả
sử rằng là một điểm cố định khác. Từ ⊥⊑ dẫn đến (⊥) ⊑ ( ) = , vì f
là hàm đơn điệu và bằng quy nạp ta có
( ) =
(⊥) ⊑ . Do đó,
( ) là
điểm cố định nhỏ nhất. Do tính phản đối xứng nên nó là duy nhất.
Độ phức tạp tính toán một điểm cố định phụ thuộc vào 3 yếu tố:
 Độ cao của giàn, giá trị độ cao của giàn cung cấp biên cho tham số ;
 Chi phí tính toán của hàm ;
 Chi phí so sánh kết quả có bằng nhau sau mỗi bước lặp.
Tính toán một điểm cố định có thể được minh họa bằng các bước đi lên
trong một giàn bắt đầu từ điểm ⊥ (Hình 2.3)

Hình 2.3. Tính toán điểm cố định trên giàn
Ngữ nghĩa của chương trình cung cấp một mô hình toán học mô tả các hành
vi có thể của chương trình đó. Lý thuyết diễn giải trừu tượng chỉ ra rằng ngữ
nghĩa của chương trình có thể được biểu diễn dưới dạng điểm cố định [2].



17
2.1.3. Hệ dịch chuyển
Chương trình thường được biểu diễn bằng các hệ dịch chuyển (transition
systems) = 〈Σ, Σ, 〉 với Σ là tập các trạng thái, Σ ⊆ Σ là tập các trạng thái khởi
tạo và ⊆ Σ × Σ là một quan hệ dịch chuyển giữa một trạng thái và các trạng
thái kế tiếp có thể của nó[8].
Ví dụ: Xét chương trình sau
x := 0;
while x < 100 do
x := x + 1;
Chương trình này có thể được biểu diễn như sau:
〈 , {0}, {〈 ,

〉| < 100 ∧

=

+ 1}〉

trong đó Z là tập số nguyên.
2.1.4. Ngữ nghĩa vết
Một phân đoạn vết thực thi hữu hạn
… bắt đầu từ trạng thái bất kỳ
∈ Σ và sau đó di chuyển thông qua các dịch chuyển từ một trạng thái , <
〉 ∈ . Tập hợp tất cả các phân
tới một trạng thái kế tiếp
thỏa mãn 〈 ,
đoạn vết thực thi hữu hạn như vậy được gọi là ngữ nghĩa vết (tracesemantic) Σ ∗⃗

của hệ thống dịch chuyển.
Không có phân đoạn vết nào có độ dài bằng 0 bởi vì tập Σ các phân đoạn
vết là tập rỗng. Một phân đoạn vết có độ dài bằng 1 là với ∈ Σ là trạng thái
bất kỳ. Do đó, tập Σ các phân đoạn vết có độ dài 1 đơn giản là | ∈ Σ . Tương
tự, một vết có độ dài + 1 được tạo thành bằng phép ghép chuỗi
′ từ vết
có độ dài n với một phân đoạn vết ′ có độ dài 1, sao cho 〈 , ′〉 ∈ là một dịch
chuyển trạng thái có thể. Vì vậy, nếu Σ là tập các phân đoạn vết có độ dài n thì
Σ
={
| ∈ Σ ∧ 〈 , ′〉 ∈ }. Như vậy ngữ nghĩa vết của
là tập
Σ ∗⃗ = ⋃

Σ tất cả các phân đoạn vết có độ dài hữu hạn.

2.1.5. Biểu diễn ngữ nghĩa vết dưới dạng điểm cố định
Nhận thấy Σ ∪ Σ

= ℱ ∗⃗ (Σ ) với:

ℱ ∗⃗ ( ) = { | ∈ Σ} ∪ {

|

∈

∧ 〈 , 〉(∈ }

Do đó Σ ∗⃗ là một điểm cố định (fixpoint) của ℱ ∗⃗ vì ℱ ∗⃗ Σ ∗⃗ = Σ ∗⃗



18
Chứng minh như sau :
ℱ ∗⃗ Σ ∗⃗ = ℱ ∗⃗ (
= { | ∈ Σ} ∪ {
= { | ∈ Σ} ∪

|
{

|

Với

=

Σ

Σ ∧ 〈 , ′〉 ∈ }

∈

=Σ ∪
=

Σ )

∈ Σ ∧ 〈 , ′〉 ∈ }
Σ


=

Σ

+ 1 và do Σ = ∅

Giả sử rằng ℱ ∗⃗ ( ) = là một điểm cố định khác của ℱ ∗⃗ . Chứng minh bằng
quy nạp rằng ∀ ≥ 0: Σ ⊆ . Dễ dàng thấy: Σ = ∅ ⊆ và Σ = { | ∈ Σ} ⊆
ℱ ∗⃗ ( ) = . Giả sử rằng công thức trên đúng với ≥ 0, tức là Σ ⊆ . Ta cần
chứng minh công thức đúng với + 1, nghĩa là Σ
⊆ . Thật vậy,
∈
Σ nghĩa là
∈
nên {
| ∈⋃
Σ ∧ 〈 , 〉 ∈ } do đó Σ
⊆
ℱ ∗⃗ (Σ ) ⊆ ℱ ∗⃗ ( ), đây là điều chúng ta cần chứng minh.
Từ ∀ ≥ 0: Σ ⊆

suy ra Σ ∗⃗ là điểm cố định nhỏ nhất (least fixpoint) của

ℱ ∗⃗ , được ký hiệu như sau :
Σ ∗⃗ =
Với
2.2.

⊆ ∗⃗

∅ℱ

( )=

= ⋃
và

→

ℱ ∗ (∅)
( )= (

( )) là hàm lặp của .

Phân tích hình dạng

Phân tích hình dạng là việc xác định tĩnh và tự động các tính chất của heap
của một chương trình (còn được gọi là Store). Mỗi trạng thái của heap có thể
được biểu diễn thông qua một đồ thị gồm các nút đại diện cho các khối bộ nhớ
đã được cấp phát và các cạnh biểu diễn con trỏ giữa các khối bộ nhớ, cùng với
các biến của chương trình cũng có thể trỏ tới các nút trong heap[12]. Hiện nay,
phân tích hình dạng bộ nhớ heap có thể tiếp cận theo nhiều cách khác nhau, và
có thể thực hiện ở nhiều mức (mức cụ thể, mức trừu tượng). Nhưng đều sử dụng


19
lý thuyết giàn ngữ nghĩa của chương trình. Từng nút trong mã nguồn sẽ được
gắn một giá trị ngữ nghĩa(semantic). Ngữ nghĩa của một nút chịu sự ràng buộc
trong mối quan hệ với các nút ở trước và sau nó trong mã nguồn chương trình
tùy theo ngữ nghĩa của các câu lệnh đối với thuộc tính cần xem xét. Từ sự ràng

buộc về ngữ nghĩa của các nút trong mã nguồn sẽ tạo ra một hệ phương trình
ràng buộc. Thuật toán lặp tìm điểm cố định nhỏ nhất được áp dụng giải hệ
phương trình ràng buộc này. Kết quả sẽ là một tập các trạng thái heap có thể có
tại mỗi nút (điểm) của chương trình.
Mục tiêu của phân tích hình dạng là xác định, tại mỗi điểm của chương
trình, một tập đồ thị hình dạng thể hiện tất cả các cấu trúc heap có thể xảy ra
trong quá trình thực thi chương trình tại thời điểm đó.Từ đó rất nhiều thông tin
hữu ích ta có thể thu được qua phân tích. Một câu hỏi phổ biến là xác định tính
tới được của các nút trong heap (reachability – một nút heap có thể tới được từ
một biến). Cho hai nút và bắt đầu từ một nút, liệu có thể tới được nút còn lại
thông qua các kết nối con trỏ không[10]. Một số tính chất khác như xem xét
việc tồn tại của chu trình, tính rời nhau (disjointness – hai cấu trúc dữ liệu có
chung phần tử không), tính chia sẻ (sharing – có nhiều hơn một biểu thức con
trỏ tham chiếu tới nút của heap) cũng rất quan trọng. Nhìn chung, người ta quan
tâm tới hình dạng của một heap, đó là một đặc tính của cấu trúc dữ liệu của nó.
Đối với một chương trình thao tác với danh sách móc nối đơn, điều này có nghĩa
chúng ta có thể tiến hành xác định tĩnh xem heap của nó bao gồm các danh sách
hoặc chu trình hay không. Ngoài ra cũng có một số cấu trúc dữ liệu phổ biến
được quan tâm như danh sách móc nối kép, cấu trúc cây, DAGs.
Kết quả của phân tích hình dạng có nhiều ứng dụng. Chúng hữu ích hoặc rất
cần thiết đối với một số dạng kiểm chứng chương trình (ví dụ xác định có tham
chiếu con trỏ null trong chương trình), tối ưu hóa và tự động song song (các cấu
trúc dữ liệu tách rời có thể được xử lý song song).
Tuy nhiên, việc đưa ra câu trả lời chính xác với tất cả các câu hỏi về chương
trình là không thể. Như đã biết, có nhiều thuộc tính như tính kết thúc của
chương trình là không giải được. Thậm chí các thuộc tính giải được cũng thường
tốn quá nhiều chi phí để phân tích, đặc biệt khi gặp vấn đề bùng nổ không gian
trạng thái. Do đó chúng ta cần một kỹ thuật xấp xỉ: ngữ nghĩa chương trình được
xấp xỉ để câu trả lời không sai nhưng ít chính xác hơn. Vì vậy, nếu chúng ta
chứng minh được một thuộc tính trên miền xấp xỉ thì thuộc tính này phản ánh



20
được tất cả các thực thi có thể. Ngược lại, nếu thuộc tính không được chứng
minh thì điều này có thể xảy ra do cảnh báo sai vì vấn đề xấp xỉ.
Trong trường hợp phân tích hình dạng của heap, chúng ta thường phải đối
mặt với các chương trình thao tác với cấu trúc có kích cỡ không giới hạn. Ví dụ
độ dài của danh sách là không giới hạn. Tuy nhiên, chúng ta cần một biểu diễn
giới hạn trong phân tích của chúng ta. Điều này cho thấy sự cần thiết của các kỹ
thuật xấp xỉ. Kỹ thuật diễn giải trừu tượng trong phân tích tĩnh cho phép tóm tắt
hành vi (ngữ nghĩa cụ thể) của lệnh chương trình trên tập vô hạn các trạng thái
có thể có của bộ nhớ. Kết quả sau tóm tắt được gọi là ngữ nghĩa trừu tượng của
lệnh đó. Ngữ nghĩa cụ thể của một lệnh trong chương trình thường được biểu
diễn thông qua các phương pháp hình thức và được sử dụng khá tự nhiên. Tuy
nhiên, trừu tượng hóa ngữ nghĩa cụ thể để tạo ra ngữ nghĩa trừu tượng đảm bảo
tính mạnh, chính xác và có khả năng lập luận được lại là một vấn đề khó khăn.
Điều này đặc biệt đúng với một số vấn đề trong thực tế như: Phân tích hình dạng
(Shape Analysis), phân tích con trỏ, trong đó ngữ nghĩa cụ thể liên quan trực tiếp
tới cấu trúc dữ liệu và bộ nhớ.Trừu tượng hóa heap được chứng minh là một vấn
đề khó khăn trong phân tích tĩnh.
2.3.

Nền tảng diễn giải trừu tượng

Diễn giải trừu tượng là một lý thuyết xấp xỉ đúng đắn ngữ nghĩa của chương
trình, dựa trên các hàm đơn điệu của các tập có thứ tự đặc biệt là giàn. Nó có thể
được xem như một phần thực thi của chương trình máy tính, và thông tin thu
được của nó là ngữ nghĩa của chương trình mà không cần thực hiện tất cả các
tính toán.
Ứng dụng chính của diễn giải trừu tượng là phân thích hình thức tĩnh, và tự

động lý giải về các thực thi có thể có của chương trình nhằm hai mục đích
chính:
 Trong trình biên dịch, giúp xác định chỗ nào cần tối ưu hóa hoặc thay
đổi.
 Để gỡ lỗi hoặc xác nhận các loại lỗi mà chương trình thu được.
Diễn giải trừu tượng được chính thức hóa bởi Patrick Cousot và Radhia
Cousot vào cuối năm 1970.
Ta có thể minh họa diễn giải trừu tượng qua ví dụ thực tế: Trong một phòng
họp, giả sử mỗi người có một số định danh, là duy nhất trong phòng. Để chứng
minh rằng một người nào đó không có mặt trong phòng, thì cần phải xem xét


21
xem số định danh đó có trong danh sách hay không. Vì hai người không thể có
cùng số định danh, nên có thể chỉ ra hoặc bác bỏ việc có mặt của ai đó thông qua
số định danh.
Tuy nhiên, nếu chỉ có tên người tham dự được đăng ký. Nếu tên của người
đó không có trong danh sách thì có thể kết luận là người đó không có mặt.
Nhưng nếu có tên, thì không thể kết luận được là có mặt, bởi vì có thể do trùng
tên. Ta chỉ có thể kết luận rằng anh/ cô ấy có thể có mặt trong phòng. Và nếu đó
là một tên tội phạm thì sẽ bật báo động, tất nhiên đó có thể là báo động giả. Và
các trường hợp thế này cũng có thể xảy ra trong phân tích chương trình.
Nếu ta chỉ quan tâm tới vài thông tin đặc biệt là "Có người nào trong độ
tuổi20 trong phòng không?",khi đó việc lưu giữ một danh sách dài đầy đủ thông
tin tên và ngày sinh, địa chỉ là không cần thiết. Ta có thể rút ngắn danh sách độ
tuổi người tham gia mà vẫn giữ đảm bảo được độ an toàn và chính xác của
thông tin. Nếu quá nhiều thông tin cần xử lý thì ta chỉ giữ lại tuổi người trẻ nhất
là , và tuổi người già là . Khi đó, nếu tuổi cần hỏi thấp hơn hay cao hơn
thì có thể trả lời rằng không có người độ tuổi đó tham gia. Ngược lại thì chỉ
có thể trả lời là có thể có hoặc không.

Trong khoa học máy tính, thông tin cụ thể và chính xác nói chung không thể
tính toán được với giới hạn về thời gian và bộ nhớ. Sự trừu tượng được xem như
là câu trả lời tổng quát cho các câu hỏi (ví dụ: trả lời maybe cho câu hỏi yes/no,
tức là “ có thể có hoặc không” khi không thể đưa ra được câu trả lời chính xác
một cách chắc chắn); điều này giúp đơn giản hóa vấn đề, làm cho tuân theo các
giải pháp tự động. Một yêu cầu quan trọng là sự không rõ ràng vẫn đủ để quản
lý các vấn đề trong khi vẫn duy trì được độ chính xác các câu trả lời cho các câu
hỏi quan trọng.
2.3.1. Phân tích trên miền trừu tượng
Lý thuyết diễn giải trừu tượng hình thức hóa ý tưởng: việc chứng minh tính
chất của chương trình có thể được thực hiện trên một số mức độ trừu tượng, ở
đó các chi tiết không liên quan đến ngữ nghĩa cũng như đặc tả chương trình của
chương trình được bỏ qua. Khi đó vấn đề được chuyển về chứng minh một ngữ
nghĩa trừu tượng (abstract semantic) thỏa mãn một đặc tả trừu tượng (abstract
specification). Một ví dụ về ngữ nghĩa trừu tượng là biểu diễn của chương trình
qua Logic Hoare và đặc tả trừu tượng là các bất biến, tính đúng đắn cục bộ
(partial correctness), hoặc tính đúng đắn toàn cục (total correctness) [4]. Lý


22
thuyết diễn giải trừu tượng nghiên cứu về ngữ nghĩa của chương trình, phương
pháp trừu tượng hóa ngữ nghĩa của chương trình,tính đúng đắn (sound) – nếu
chứng minh được rằng ngữ nghĩa trừu tượng thỏa mãn đặc tả trừu tượng thì có
thể chỉ ra rằng ngữ nghĩa cụ thể cũng thỏa mãn đặc tả cụ thể, và tính đầy đủ
(complete) – nếu chứng mình được rằng ngữ nghĩa cụ thể thỏa mãn đặc tả cụ thể
thì cũng có thể chứng minh được trên miền trừu tượng,của phương pháp xấp xỉ
để tạo ra ngữ nghĩa trừu tượng[4].
Quá trình phân tích một chương trình luôn bắt đầu với ngữ nghĩa cụ thể
(concrete semantics) của chương trình đó. Ngữ nghĩa cụ thể là mô hình toán học
mô tả tập tất cả các thực thi trong tất cả các môi trường có thể của chương trình.

Hình 2.4 minh họa ngữ nghĩa cụ thể của chương trình, mỗi đường trên đồ thị
tương ứng với một hành vi thực thi.

Hình 2.4. Ngữ nghĩa cụ thể của chương trình
Ngữ nghĩa cụ thể là vô hạn (tức là có vô số các đường thực thi như trên), do
đó không thể thực hiện các tính toán trên miền ngữ nghĩa cụ thể của một chương
trình. Hầu hết các câu hỏi không thông thường trên miền ngữ nghĩa cụ thể của
chương trình đều dẫn đến vấn đề không giải được.
Ví dụ, tính an toàn (safety properties) của chương trình đạt được khi không
có hành vi nào của nó có thể đạt đến một trạng thái nguy hiểm (erroneous state).


23

Hình 2.5. Thuộc tính an toàn
Hình 2.5 minh họa về kiểm tra tính an toàn của chương trình. Chứng minh
một chương trình an toàn tức là chứng minh giao giữa miền ngữ nghĩa cụ thể
của chương trình đó và vùng vi phạm (forbidden zone) là rỗng. Tuy nhiên trên
miền ngữ nghĩa cụ thể đây là vấn đề không giải được, số lượng các thực thi là vô
hạn do đó chúng ta không thể kiểm tra đối với tất cả các thực thi. Lý do này dẫn
đến không thể xác minh hoàn toàn tự động tính an toàn của chương trình với
nguồn tài nguyên phần cứng máy tính hữu hạn hoặc không có sự tương tác của
con người.
Các kỹ thuật phổ biến hiện nay như kiểm thử và gỡ lỗi (Testing/ Debugging)
chỉ xem xét một tập con của tập tất cả các hành vi có thể của chương trình, do đó
không khẳng định được tính đúng. Độ phủ hạn chế là vấn đề chính của các kỹ
thuật dạng này. Hình 2.6 minh họa cơ chế của kỹ thuật kiểm thử, chỉ một số
nhánh thực thi (nét liền) của chương trình được kiểm tra trong quá trình kiểm
thử.


Hình 2.6. Kỹ thuật kiểm thử