ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
-------------------

NGUYỄN THANH LIÊM

NGHIÊN CỨU
KỸ THUẬT GIẢI THÍCH TRỪU TƯỢNG

LUẬN VĂN THẠC SĨ KHOA HỌC

Hà Nội – Năm 2014


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
-------------------

NGUYỄN THANH LIÊM

NGHIÊN CỨU
KỸ THUẬT GIẢI THÍCH TRỪU TƯỢNG

Chuyên ngành: CƠ SỞ TOÁN HỌC CHO TIN HỌC
Mã số:

60460110

LUẬN VĂN THẠC SĨ KHOA HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC

TS. NGUYỄN TRƯỜNG THẮNG

Hà Nội – Năm 2014


LỜI CAM ĐOAN
Tơi xin cam đoan đây là cơng trình nghiên cứu của tơi trong đó có sự
giúp đỡ của giáo viên hướng dẫn TS. Nguyễn Trường Thắ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. 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, được
tham khảo theo các tài liệu của các tác giả do giáo viên hướng dẫn cung cấp
và được liệt kê tại mục tài liệu tham khảo.
Học viên

Nguyễn Thanh Liêm

1


LỜI CẢM ƠN
Lời đầu tiên tôi xin gửi lời cảm ơn chân thành và bày tỏ lòng biết ơn
sâu sắc nhất tới giáo viên hướng dẫn 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 đã hướng dẫn tận tình, giúp đỡ và truyền đạt cho những kiến
thức, kinh nghiệm quí báu trong suốt thời gian vừa qua, thầy đã cung cấp cho
tôi các tài liệu rất hữu ích để hồn thành luận văn này.
Tơi cũng xin gửi lời cảm ơn chân thành tới tất cả các thầy, cô trong bộ
môn Tin học - Khoa Toán - Cơ - Tin học - Trường Đại học Khoa học Tự
nhiên - ĐHQG Hà Nội đã giúp đỡ tơi về kiến thức, tinh thần và những lời
khun q báu trong suốt quá trình học tập vừa qua.

Cảm ơn đến tất cả các bạn bè, đồng nghiệp trong Viện Công nghệ
thông tin - Viện Hàn lâm Khoa học và Công nghệ Việt Nam, trường Đại học
Hải Dương đã cung cấp cho tơi những tài liệu q báu, giúp đỡ, động viên và
tạo điều kiện cho tôi về tất cả mọi mặt trong suốt một năm qua.
Cuối cùng tôi xin gửi lời cảm ơn tới các thành viên trong gia đình đã
tạo điều kiện tốt nhất cho tơi, động viên, cổ vũ tơi trong q trình học tập và
nghiên cứu để tơi hồn thành luận văn này.

Học viên

Nguyễn Thanh Liêm

2


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 THUẬT NGỮ VÀ CHỮ VIẾT TẮT ................................ 6
DANH MỤC CÁC HÌNH VẼ .......................................................................... 7
MỞ ĐẦU ........................................................................................................... 8
Chương 1 - TỔNG QUAN .............................................................................. 10
1.1. Tổng quan về phân tích chương trình .................................................. 10
1.1.1. Ý tưởng của bài tốn phân tích chương trình ............................... 11
1.1.2. Phân tích chương trình tĩnh ........................................................... 12
1.2. Tổng quan về kỹ thuật giải thích trừu tượng........................................ 13
1.3. Tổng quan về tình hình nghiên cứu ..................................................... 15
1.4. Kết luận chương 1 ................................................................................ 16
Chương 2 - CỞ SỞ LÝ THUYẾT CỦA KỸ THUẬT GIẢI THÍCH TRỪU

TƯỢNG ........................................................................................................... 17
2.1. Khái niệm về kỹ thuật giải thích trừu tượng ........................................ 17
2.2. Ứng dụng của kỹ thuật giải thích trừu tượng ....................................... 17
2.3. Một số khái niệm cơ bản ...................................................................... 18
2.3.1. Ngữ nghĩa cụ thể của chương trình ............................................... 18
2.3.2. Thuộc tính an tồn của chương trình ............................................ 19
2.3.3. Miền trừu tượng ............................................................................ 20
2.3.4. Độ phủ của kỹ thuật giải thích trừu tượng .................................... 21
2.3.5. Các phương pháp hình thức .......................................................... 22
2.3.6. Tính chất cần thiết của ngữ nghĩa trừu tượng ............................... 23
2.4. Lý thuyết dàn........................................................................................ 25

3


2.5. Lý thuyết điểm cố định ........................................................................ 28
2.5.1. Điểm cố định ................................................................................. 28
2.5.2. Mở rộng ký hiệu điểm cố định ...................................................... 29
2.5.3. Bước lặp ........................................................................................ 29
2.5.4. Đồ thị luồng điều khiển (Control Flow Graphs - CFG)................ 33
2.5.5. Phân tích luồng dữ liệu (Data Flow Analysis) .............................. 36
2.5.6. Thuật tốn tìm điểm cố định ......................................................... 36
2.6. Tiếp cận kết nối Galois cho kỹ thuật giải thích trừu tượng ................. 38
2.6.1. Kết nối Galois ............................................................................... 38
2.6.2. Tính đủ và tính chính xác (Soundness and Precision) .................. 39
2.6.3. Mở rộng tới không gian hàm (Extension to Function Spaces) ..... 40
2.6.4. Trừu tượng hàm (Functional Abstraction) .................................... 41
2.7. Trừu tượng hóa ngữ nghĩa chương trình .............................................. 41
2.7.1. Hệ dịch chuyển.............................................................................. 41
2.7.2. Ngữ nghĩa vết (Trace semantics) .................................................. 43

2.7.3. Biểu diễn ngữ nghĩa vết dưới dạng điểm cố định ......................... 44
2.7.4. Bao đóng phản xạ bắc cầu (RTC - reflexive transitive closure) là
trừu tượng hóa của ngữ nghĩa vết ........................................................... 45
2.7.5. Thỏa mãn kết nối Galois ............................................................... 45
2.7.6. Biểu diễn ngữ nghĩa RTC dưới dạng điểm cố định ...................... 46
2.7.7. Ngữ nghĩa tới được là trừu tượng hoá của ngữ nghĩa RTC .......... 47
2.7.8. Biểu diễn ngữ nghĩa tới được dưới dạng điểm cố định ................ 47
2.8. Kết luận chương 2 ................................................................................ 48
Chương 3 - THỰC NGHIỆM ......................................................................... 49
3.1. Giới thiệu về TVLA ............................................................................. 49
3.2. Phân tích trong TVLA.......................................................................... 50

4


3.2.1. Cấu trúc 3-valued Logic ................................................................ 51
3.2.2. Biểu diễn trạng thái bộ nhớ Heap qua cấu trúc Logic .................. 52
3.2.3. Trừu tượng heap ............................................................................ 53
3.2.4. Biểu diễn ngữ nghĩa và chương trình ............................................ 55
3.2.5. Ví dụ về phân tích chương trình ................................................... 57
3.3. Thuật tốn sinh hệ ràng buộc Coerce và thuật tốn giải hệ ràng buộc
tìm điểm cố định Focus ............................................................................... 59
3.3.1. Công thức ...................................................................................... 59
3.3.2. Các lớp con của công thức ............................................................ 60
3.3.3. Ngữ nghĩa ...................................................................................... 60
3.3.4. Focus ............................................................................................. 61
3.3.5 Cơng thức cập nhật......................................................................... 63
3.3.6. Thuật tốn Coerce xác định hệ ràng buộc..................................... 65
3.3.7. Thuật toán Focus giải hệ ràng buộc .............................................. 67
3.4. Thử nghiệm .......................................................................................... 70

3.4.1. Đặc tả hệ thống trong TVLA ............................................................ 70
3.4.2. Giới thiệu bài toán ......................................................................... 71
3.4.3. Đặc tả dữ liệu đầu vào................................................................... 71
3.4.4. Kết quả phân tích .......................................................................... 76
3.5. Kết luận chương 3 ................................................................................ 77
KẾT LUẬN ..................................................................................................... 78
TÀI LIỆU THAM KHẢO ............................................................................... 79
PHỤ LỤC A: ................................................................................................... 81
PHỤ LỤC B: ................................................................................................... 83

5


DANH MỤC CÁC THUẬT NGỮ VÀ CHỮ VIẾT TẮT
TT
Tiếng Anh - Viết tắt
1 Abstract domain

Tiếng Việt
Miền trừu tượng

2

Abstract semantics

Ngữ nghĩa trừu tượng

3

Concrete domain


Miền cụ thể

4

Concrete semantics

Ngữ nghĩa cụ thể

5

Continue - con

Tính liên tục của một hàm số

6

Control Flow Graphs - CFG

Đồ thị luồng điều khiển

7

Data Flow Analysis - DFA

Phân tích luồng dữ liệu

8 Fixpoint - fix
9 Fixpoint approximation
10 Galois connections


Điểm cố định
Xấp xỉ điểm cố định
Kết nối Galois

11 Interval semantics

Ngữ nghĩa khoảng
Dàn - Tập hợp các phần tử có thứ
tự từng phần có điểm chặn dưới
lớn nhất và trặn trên nhỏ nhất
Tính đơn điệu của một hàm
Thu hẹp
Tập hợp các phần tử có thứ tự
Tính chính xác
Ngữ nghĩa tới được

12 Lattice
13
14
15
16
17

Monotone - mon
Narrowing
Partial Ordered Set - Poset
Precise
Reachability semantics


18 Reflexive transitive closure - RTC
Reflexive
transitive
closure
19
semantics - RTCs
20 Soundness

Bao đóng phản xạ bắc cầu
Ngữ nghĩa bao đóng phản xạ bắc
cầu
Tính đủ

21 Trace semantics

Ngữ nghĩa vết, Tập hợp các dấu
vết về quá trình chuyển đổi trạng
thái của chương trình.

22 Transition system
23 Widening

Hệ dịch chuyển
Mở rộng

6


DANH MỤC CÁC HÌNH VẼ
TT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

31
32
33
34
35
36
37
38

Hình ảnh sử dụng
Hình 1.1: Bài tốn phân tích chương trình tổng qt
Hình 1.2: Trừu tượng hóa theo điểm cố định
Hình 1.3: Các thành phần chính của phân tích chương trình
Hình 2.1 Sơ đồ hành vi có thể của chương trình
Hình 2.2: Quĩ đạo an tồn của các thực thi
Hình 2.3: Quĩ đạo khơng an tồn đối với kiểm thử/gỡ lỗi
Hình 2.4: Biểu diễn miền trừu tượng
Hình 2.5: Trừu tượng hóa quĩ đạo hành vi của chương trình
Hình 2.6: Trừu tượng hóa quĩ đạo hành vi khơng đảm bảo tính đủ
Hình 2.7: Lỗi trừu tượng hóa quĩ đạo hành vi khơng chính xác
Hình 2.8: Tiêu chuẩn trừu tượng hóa theo khoảng
Hình 2.9: Biểu đồ Hasse của dàn (2A,⊆)
Hình 2.10: Biểu diễn ngữ nghĩa của một chương trình thành dàn
Hình 2.11: Biểu diễn điểm cố định của hàm cosx = x
Hình 2.12: Tính tốn điểm cố định trên dàn
Hình 2.13: Phép cộng dàn
Hình 2.14: Phép nâng dàn
Hình 2.15: Dàn phẳng
Hình 2.16: CFG cho các lệnh đơn giản
Hình 2.17: CFG cho cấu trúc tuần tự

Hình 2.18: CFG cho cấu trúc rẽ nhánh
Hình 2.19: CFG cho cấu trúc lặp
Hình 2.20: CFG của hàm tính n!
Hình 2.21: ¯F(¯x) là một xấp xỉ của F(x)
Hình 2.22: Biểu diễn quan hệ chuyển tiếp ngữ nghĩa chương trình
Hình 2.23: Hệ chuyển dịch quĩ đạo thực thực thi của chương trình
Hình 2.24: Biểu diễn ngữ nghĩa vết thực thi
Hình 2.25: Biểu diễn ngữ nghĩa vết dưới dạng điểm cố định
Hình 2.26: Trừu tượng hóa đến ngữ nghĩa tới được
Hình 3.1: Các tốn tử 3-valued logic của Kleene
Hình 3.2: Biểu diễn heap cụ thể
Hình 3.3: Trừu tượng hóa heap
Hình 3.4: Kết quả heap trừu tượng đầu ra
Hình 3.5: Trạng thái của chương trình sử dụng cấu trúc 2-valued logic
Hình 3.6: Trạng thái của chương trình sử dụng 3-valued logic
Hình 3.7: Biểu diễn quá trình làm việc của phân tích chương trình
Hình 3.8: Ứng dụng của giải thích trừu tượng cho phân tích lệnh
Hình 3.9: Kết quả phân tích hàm tạo danh sách liên kết

7

Trang
12
14
14
18
19
20
21
22

24
24
25
26
28
30
30
32
31
32
34
34
34
35
35
41
42
42
43
44
48
52
53
55
56
58
58
59
62
77



MỞ ĐẦU
Ngày nay, các hệ thống phần mềm được sử dụng một cách phổ biến
trên tất cả các lĩnh vực của đời sống, trong sản xuất, kinh doanh như: kinh tế,
tài chính, kế tốn, y tế, giáo dục, chính phủ,… , và trong các thiết bị điện tử
công nghiệp và dân dụng, nó được phát triển trở lên ngày càng phức tạp. Sự
phức tạp này còn lớn hơn đối với các hệ thống điều khiển và các hệ thống
nhúng trong các thiết bị công nghiệp, hàng không, vũ trụ, … Đối với những
đơn vị, cá nhân và các tổ chức làm phần mềm chuyên nghiệp họ đều hiểu rằng
một sản phẩm phần mềm được họ tạo ra không thể nào chạy một cách hoàn
hảo ngay từ lúc đầu tiên mà khơng mắc bất kỳ một lỗi gì. Trong q trình phát
triển và đưa vào sử dụng một phần mềm bất kỳ, thì hầu hết tất cả các lỗi chỉ
được phát hiện sau khi phần mềm đó được đưa vào sử dụng. Do vậy, các hoạt
động kiểm thử đóng góp một vai trò rất quan trọng nhằm đảm bảo chất lượng
của các hệ thống phần mềm.
Các hoạt động kiểm thử này ln được các nhà phát triển phần mềm
tính đến trong suốt quá trình phát triển cho một hệ thống phần mềm. Tuy
nhiên, các hoạt động kiểm thử thường có chi phí rất cao, nó chiếm đến 40%
tồn bộ chi phí phát triển phần mềm, cịn về mặt thời gian thì đơi khi nó cịn
nhiều hơn cả việc xây dựng hệ thống. Hầu hết các hoạt động kiểm thử nhằm
mục đích phân tích các thành phần và cấu trúc của phần mềm để xác định số
lượng lớn nhất các lỗi trong tiến trình phát triển: từ đặc tả cho đến mã hóa.
Đối với các hệ thống phần mềm phức tạp, cách giải quyết đưa ra ban
đầu với các hệ thống bao giờ cũng là cẩn thận trong từng khâu: phân tích,
thiết kế, lập trình, kiểm thử để giảm thiểu một cách tối đa các lỗi phát sinh.
Các nguồn lực cần thiết cho hoạt động kiểm thử là rất quan trọng. Vì vậy,
việc nghiên cứu các phương pháp nhằm mục đích giảm chi phí trong q trình
kiểm thử đã được đưa ra, nhưng vẫn đảm bảo mục tiêu về tính hiệu quả của
phần mềm là một biện pháp hữu hiệu.

8


Do vậy, trong luận văn này tôi giới thiệu một phương pháp trong lĩnh
vực phân tích chương trình tĩnh. Cụ thể là nghiên cứu về kỹ thuật giải thích
trừu tượng, mục tiêu chính là cập nhật các xu hướng mới của kỹ thuật này ở
trên thế giới để nâng cao chất lượng phần mềm.
Các đề tài nghiên cứu về kỹ thuật giải thích trừu tượng chưa được phổ
biến ở trong nước, do vậy trong khuôn khổ của đề tài tôi xin trình bày các
khái niệm cơ bản, cơ sở lý thuyết ban đầu dựa trên các báo cáo tại các hội
nghị thường niên VMCAI (Verification, Model Checking, and Abstract
Interpretation) và các tài liệu nghiên cứu, bài giảng của tác giả Patrick Cousot
trong những năm gần đây.
Ứng dụng thử nghiệm tập trung vào công cụ mã nguồn mở TVLA (3 –
Valued Logic Analysis Engine) được phát triển bởi Lev-Ami trường Đại học
Khoa học Máy tính Tel Aviv – Israel.
Bố cục của luận văn gồm 3 chương:
Chương 1 - TỔNG QUAN: Tập trung vào các khái niệm liên quan đến
kiểm chứng phần mềm, phân tích chương trình tĩnh, tiếp cận lý thuyết của kỹ
thuật giải thích trừu tượng trong phân tích chương trình tĩnh, tình hình nghiên
cứu ở trong và ngồi nước.
Chương 2 - CƠ SỞ LÝ THUYẾT CỦA KỸ THUẬT GIẢI THÍCH
TRỪU TƯỢNG: Tập trung vào cơ sở lý thuyết tốn học của kỹ thuật giải
thích trừu tượng, các phương pháp trừu tượng hóa ngữ nghĩa chương
trình, biểu diễn ngữ nghĩa của chương trình thơng qua các kỹ thuật trừu
tượng, …, và ứng dụng trong kỹ thuật giải thích trừu tượng.
Chương 3 - THỬ NGHIỆM: Tập trung vào việc cài đặt phương pháp
phân tích chương trình tĩnh bằng kỹ thuật giải thích trừu tượng dựa trên bộ
cơng cụ mã nguồn mở TVLA, làm rõ các ứng dụng trong phân tích hình dạng.
KẾT LUẬN: Trình bày nội dung nghiên cứu đã đạt được, các hạn chế

trong quá trình nghiên cứu và định hướng nghiên cứ tiếp theo.
9


Chương 1 - TỔNG QUAN
1.1. Tổng quan về phân tích chương trình
Sự phát triển vượt bậc, nhanh chóng của các thiết bị phần cứng với
một hệ số 106 lần trong gần 40 năm qua đã dẫn đến sự bùng nổ của kích cỡ
các chương trình phần mềm cũng theo một tỉ lệ tương tự chạy trên chúng.
Về Qui mô và phạm vi của các chương trình ứng dụng cực lớn này (từ 1 tới
40 triệu dịng mã lệnh) có thể vẫn tiếp tục mở rộng nhanh chóng trong thập
kỉ tới. Các chương trình cực lớn như vậy sẽ phải được thiết kế với chi phí
hợp lý, theo sau đó vẫn phải sửa chữa, bảo trì và nâng cấp trong suốt dịng
đời của chúng (thơng thường là khoảng trên 20 năm). Trên thực tế là số
lượng và hiệu quả của các đội lập trình, phụ trách việc bảo trì, theo dõi
chúng không thể phát triển theo tỷ lệ tương tự như vậy. Trong điều kiện
như vậy, một tỉ lệ không quá hiếm gặp với 1 lỗi trong 1000 dòng mã lệnh
đối với những chương trình cực lớn này thường là quá lạc quan và sẽ
khơng thể nhanh chóng đạt được trong một tương lai gần (hầu như khơng
thể kiểm sốt được), đặc biệt đối với những hệ thống quan trọng đòi hỏi độ
an tồn cao. Vì vậy trong khoảng 10 năm tới, vấn đề về độ tin cậy của phần
mềm (software reliability) có một khả năng sẽ trở thành là một mối quan
tâm rất lớn và cũng là một thách thức rất lớn đối với một xã hội hiện đại
phụ thuộc rất nhiều vào máy tính [7].
Trong hơn 3 thập kỷ qua, rất nhiều tiến bộ đã được thực hiện cả về mặt
tư duy/công cụ hỗ trợ (để nâng cao khả năng về trí tuệ của con người) để ứng
phó với các hệ thống phần mềm phức tạp giúp cho các lập trình viên suy luận
tốt hơn về chương trình [7].
Rất nhiều các kỹ thuật kiểm chứng phần mềm (software verification) và
các công cụ hỗ trợ kèm theo đã được phát triển, bắt đầu bằng các thực hiện/

mơ phỏng chương trình trong nhiều mơi trường khác nhau có thể. Tuy nhiên,
gỡ lỗi mã biên dịch hoặc mơ hình mơ phỏng của mã nguồn chương trình là
10


hầu như không thể mở rộng về qui mô và thường chỉ đưa ra được một phạm
vi bao phủ thấp các hành vi động của chương trình. Các phương pháp hình
thức (formal methods) trong kiểm chứng chương trình (program verification)
đã rất lỗ lực trong việc chứng minh một cách tự động rằng chương trình sẽ
thực hiện là chính xác trong tất cả các môi trường đặc tả. Lĩnh vực nghiên cứu
này bao gồm các phương pháp suy diễn (diductive methods), kiểm chứng mơ
hình (model checking), định kiểu chương trình (program typing) và phân tích
chương trình tĩnh (static program analysis) [7].
Khi bài tốn kiểm chứng chương trình đã được chứng minh là khơng
giải được. Vì vậy, việc hỗ trợ tính tốn cho tất cả các phương pháp kiểm
chứng là khơng hồn chỉnh (incomplete). Độ phức tạp tính tốn hoặc tính
khơng giải được này sẽ được giải quyết bằng cách sử dụng một số hình thức
xấp xỉ với mục đích là đưa chúng về bài toán giải được hoặc làm giảm độ
phức tạp tính tốn trong q trình kiểm chứng chương trình [7].
1.1.1. Ý tưởng của bài tốn phân tích chương trình
Bài tốn phân tích chương trình tĩnh có thể được mơ tả như sau: Cho
trước một chương trình

và một đặc tả , phân tích chương trình sẽ kiểm tra

xem ngữ nghĩa của chương trình L có thỏa mãn đặc S hay khơng (minh họa
hình 1.1). Trong trường hợp xảy ra lỗi, q trình phân tích sẽ cung cấp các gợi
ý để tìm hiểu nguồn gốc của lỗi (bằng cách phân tích ngược lại sẽ cung cấp
các điều kiện cần thiết cho đặc tả thơng qua phản ví dụ) [7].
Ví dụ 1.1: Cho đoạn chương trình cần phân tích như sau:

1.

a = 0;

2.

while(a < 1000){

3.

a = a + 1;

4.

}

5.

return;

L là mã nguồn và S là giá trị của biến
11

∈ [0,1000].


Hình 1.1: Bài tốn phân tích chương trình tổng qt
1.1.2. Phân tích chương trình tĩnh
Phân tích chương trình tĩnh là việc xác định tĩnh tự động các thuộc tính
động về thời gian thực thi của chương trình. Có rất nhiều câu hỏi thú vị mà

người ta có thể được hỏi về một chương trình nhất định nào đó:
+ Chương trình hiện tại có dừng hay khơng?
+ Độ lớn của vùng nhớ (heap) là bao nhiêu trong quá trình thực thi?
+ Đầu ra có thể của nó là gì?
Các câu hỏi khác liên quan đến các điểm chương trình riêng lẻ trong
mã nguồn cũng được đưa ra:
+ Biến x luôn luôn có giá trị như nhau hay khơng?
+ Giá trị của x sẽ được đọc trong tương lai hay khơng?
+ Có thể con trỏ p là null không?
+ Các biến p có thể trỏ đến vùng nhớ nào?
+ Biến x có được khởi tạo trước khi nó được đọc hay khơng?
+ Giá trị của biến số nguyên x là luôn dương?
12


+ Các ràng buộc trên và ràng buộc dưới là như thế nào đối với giá trị
của biến số nguyên x?
+ …
Theo lý thuyết Rice (một kết quả tổng quát từ năm 1953) có thể được
giải thích rằng tất cả các câu hỏi thú vị nêu trên về hành vi của chương trình
là khơng giải được, điều này rất dễ dàng thấy trong bất kỳ trường hợp đặc
biệt nào [2].
1.2. Tổng quan về kỹ thuật giải thích trừu tượng
Nguyên tắc của kỹ thuật giải thích trừu tượng (abstract interpretation)
là dựa trên tính tốn xấp xỉ ngữ nghĩa của chương trình nhằm mục đích kiểm
tra sự thỏa mãn một đặc tả nhất định. Kỹ thuật này được sử dụng để suy 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), ngữ nghĩa này đã được
xấp xỉ và tính tốn được (approximate and computable abstract semantics)
trên miền trừu tượng (abstract domain) theo hình minh họa 1.2 [7].

Tuy nhiên với quá trình suy dẫn này, bản thân nó khơng hồn tồ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 hàm trừu tượng
tạo ra

thông qua các tham số đưa vào, bởi vì có thể

đầu tiên

(là ngữ nghĩa trừu tượng từ L) không thỏa mãn đặc tả S, khi đó ta

khơng kết luận ngay là chương trình L khơng thỏa mãn đặc tả S do tính khơng
hồn chỉnh (incompleteness) của kỹ thuật giải thích trừu tượng
trước hết phải tinh chỉnh lại hàm

của L, mà

sao cho phù hợp.

Nếu S thỏa mãn bởi , do tính đúng đắn của kỹ thuật giải thích trừu
tượng suy ra S thỏa mãn L. Ưu điểm lớn nhất của kỹ thuật này là độ phức tạp
tính tốn trên

nhỏ hơn rất nhiều so với L tùy theo q trình trừu tượng hóa

(hàm trừu tượng hóa

từ L vào ), được minh họa trong hình 1.2:

13



Hình 1.2: Trừu tượng hóa theo điểm cố định

⊑ (

#

)

Trong thực tế, việc phân tích chương trình tĩnh bằng kỹ thuật giải thích
trừu tượng có chứa một thành phần là bộ sinh (generator) ngữ nghĩa trừu
tượng thông qua việc đọc mã nguồn chương trình và tạo ra các hệ phương
trình điểm cố định hoặc hệ phương trình ràng buộc cần giải bởi máy tính,
thành phần tiếp theo của kỹ thuật này là bộ giải (solver) được sử dụng để giải
các hệ phương trình điểm cố định/hệ phương trình ràng buộc. Các thành phần
chính của kỹ thuật này được mơ tả trong hình 1.3 [7].

Hình 1.3: Các thành phần chính của phân tích chương trình
14


Khi tìm được nghiệm xấp xỉ của hệ, một phương pháp phổ biến là dùng
hàm lặp khi giải. Các khái niệm và kỹ thuật trừu tượng hóa sẽ được xem xét
trong chương 2, 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), nếu giới hạn của hàm lặp
là khơng tồn tại (trường hợp này là có thể, ví dụ như khái niệm trừu tượng
theo đa diện) hoặc nó đạt được giới hạn sau vơ hạn bước lặp (ví dụ trừu tường
tượng hóa phân khoảng và bát giác), sự hội tụ này có thể được đảm bảo
hoặc/và tăng tốc độ hội tụ bằng cách sử dụng một số kỹ thuật mở rộng để mở

rộng hơn các ước lượng nghiệm gần đúng trong hữu hạn các bước tiếp theo
bởi một kỹ thuật thu hẹp để cải thiện nó [7]. Trong khn khổ mà luận văn
trình bày sẽ khơng đề cập đến các kỹ thuật liên quan đến trừu tượng phân
khoảng, trừu tượng bát giác, trừu tượng đa diện cũng như các kỹ thuật liên
quan đến mở rộng, thu hẹp điểm cố định.
1.3. Tổng quan về tình hình nghiên cứu
Khảo sát ở trong nước: Hiện nay ở Việt Nam việc sử dụng các phương
pháp hình thức trong thực tế kiểm chứng phần mềm còn nhiều hạn chế. Trong
3 mảng: phương pháp suy diễn (deductive method), kiểm chứng mơ hình
(model checking) và phân tích tĩnh với giải thích trừu tượng (static analysis
with abstract interpretation) thì mảng phân tích tĩnh với giải thích 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.
Có rất ít đề tài nghiên cứu về ứng dụng kỹ thuật giải thích trừu tượng
trong phân tích chương trình, các đề tài nghiên cứu tập trung chủ yếu ở Viện
Công nghệ thông tin - Viện Hàn lâm Khoa học và Công nghệ Việt Nam, Đại
học Quốc gia Hà Nội, Đại học Bách khoa Đà Nẵng và Đại học Quốc gia
Thành phố Hồ Chí Minh.
15


Khảo sát ở nước ngoài: tham khảo các kết quả của tác giả chính
Patrick Cousot, và những báo cáo tại các hội nghị thường niên VMCAI
(Verification, Model Checking, and Abstract Interpretation) trong những năm
gần đây. Ứng dụng kỹ thuật giải thích trừu tượng trong phân tích chương trình
tĩnh tập trung vào hai mảng lớn: phân tích luồng dữ liệu (Data-flow Analysis)
và phân tích dựa trên tập hợp (Set-based Analysis) [8]. Về ứng dụng có một
số cơng cụ (AiT, StackAnalysis, TVLA) nhưng còn rất nhiều hạn chế, chỉ

dừng lại ở mức hỗ thực nghiệm trong nghiên cứu, khi đưa vào ứng dụng trong
thực tế chưa đáp ứng được các yêu cầu của ngành công nghiệp phần mềm.
Astrée là công cụ thương mại thành công nhất hiện nay, tuy nhiên miền ứng
dụng khá hẹp nên chưa được ứng dụng rộng rã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 giải thích 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 đề tài 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 cơ bản ứng dụng vào thực tế kiểm soát
chất lượng phần mềm.
1.4. Kết luận chương 1
Trong chương 1 luận văn đã trình bày tổng quan về phân tích chương
trình, các ý tưởng chính cần thiết cho việc nghiên cứu kỹ thuật giải thích
trừu tượng và vai trị của kỹ thuật này trong phân tích chương trình tĩnh.
Khảo sát tình hình nghiên cứu ở trong và ngoài nước, các xu hướng đang
được ứng dụng của kỹ thuật này trong việc nâng cao chất lượng phần mềm.
Về cơ sở lý thuyết nền tảng của kỹ thuật này như: ngữ nghĩa chương
trình, ngữ nghĩa vết, các phương thức trừu tượng, biểu diễn trừu tượng của
các ngữ nghĩa, …, sẽ được nghiên cứu sâu trong chương 2.
16


Chương 2 - CỞ SỞ LÝ THUYẾT CỦA KỸ THUẬT GIẢI THÍCH
TRỪU TƯỢNG
2.1. Khái niệm về kỹ thuật giải thích trừu tượng
Kỹ thuật giải thích trừu tượng (Abstract interpretation): Là một kỹ
thuật trong phân tích chương trình, kỹ thuật này giúp giải thích về ngữ nghĩa
của một chương trình với những hàm đơn điệu trên các tập hợp đã được xếp
thứ tự. Lý thuyết giải thích 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, và tính đủ
(sound) cũng như tính chính xác (precise) của phương pháp xấp xỉ để tạo ra
ngữ nghĩa trừu tượng.
Kỹ thuật giải thích trừu tượng được hiểu theo nghĩa trực giác là việc
thực thi một phần của một chương trình để lấy thơng tin về nó: sơ đồ luồng
điều khiển, sơ đồ luồng dữ liệu, … [8].
+ Hình thức hóa: Tất cả những gì đã được chuẩn tắc hóa và được
chứng minh chặt chẽ bằng tốn học.
+ Phi hình thức hóa: dựa kinh nghiệm, thử nghiệm, mà khơng thể
chứng minh được bằng tốn học.
Ứng dụng của kỹ thuật giải thích trừu tượng: Phân tích trừu tượng được
ứng dụng trong phân tích cú pháp, trình biên dịch, gỡ lỗi chương trình ...
2.2. Ứng dụng của kỹ thuật giải thích trừu tượng
Kỹ thuật giải thích trừu tượng được ứng dụng rộng rãi và là một phần
không thể thiếu trong lĩnh vực kiểm thử phần mềm. Kỹ thuật giải thích trừu
tượng được dùng để chứng minh tính đầy đủ, tính chính xác, tính đúng đắn
cục bộ, tính đúng đắn toàn cục của hệ thống. Một số ứng dụng của giải thích
trừu tượng như [8]:
+ Phân tích cú pháp của dịng lệnh: phân tích thuộc tính và cú pháp
của các dịng lệnh bằng việc giải thích trừu tượng các thuộc tính
và cú pháp.
17


+ Phân tích tĩnh chương trình: đây là lĩnh vực được ứng dụng nhiều
nhất của giải thích trừu tượng. Phương pháp này phân tích mã
nguồn của chương trình bằng cách trừu tượng hóa các thực thi
của chương trình đó. Từ đó chứng minh tính đủ, tính đúng đắn, tính
chính xác của chương trình.
+ Ẩn thơng tin: trong các ngơn ngữ dựa trên các phần mềm bảo mật,

các thông tin được ẩn đi để tránh sự theo dõi, phát hiện bằng cách
sử dụng việc trừu tượng hóa các thơng tin của chương trình đó.
+ Ngồi ra giải thích trừu tượng cịn nhiều ứng dụng quan
trọng

khác

trong các ngành công nghiệp như xe hơi, hàng

không, vũ trụ, ...
2.3. Một số khái niệm cơ bản
2.3.1. Ngữ nghĩa cụ thể của chương trình
Ngữ nghĩa cụ thể của một chương trình được hình thức hóa (là một mơ
hình tốn học của) mơ tả tất cả các hành vi (quĩ đạo các đường thực thi) có
thể của chương trình thực hiện trong tất cả các mơi trường phù hợp, các thực
thi có thể của chương trình được thể hiện trong hình 2.1.

Hình 2.1 Sơ đồ hành vi có thể của chương trình.
Ngữ nghĩa cụ thể của chương trình là vơ hạn (tức là có vơ số các đường
thực thi như hình trên) các đối tượng tốn học, do đó khơng thể thực hiện các
tính tốn trên miền ngữ nghĩa cụ thể của một chương trình. Tất cả các câu hỏi
18


(được nêu trong chương 1) không tầm thường về ngữ nghĩa cụ thể của chương
trình là khơng giải được [3].
2.3.2. Thuộc tính an tồn của chương trình
Thuộc tính an tồn (Safety properties) của một chương trình là việc
khơng xuất hiện lỗi khi thực hiện các thực thi của chương trình đó trong bất
kỳ một mơi trường nào. Các hành vi của chương trình khơng vượt q phạm

vi của mơi trường cho phép minh họa trong hình 2.2.

Hình 2.2: Quĩ đạo an tồn của các thực thi
Trong hình 2.2 biểu diễn về tính an tồn của chương trình. Bằng chứng
cho tính an toàn bao gồm chứng minh rằng giao giữa miền ngữ nghĩa cụ thể
của chương trình và vùng cấm (forbidden zone) là tập rỗng.
Mặt khác, ngữ nghĩa cụ thể của chương trình là vơ hạn, đây chính là
vấn đề khơng giải quyết được (ngữ nghĩa cụ thể là khơng tính tốn được). Lý
do này dẫn đến khơng thể xác minh hồn tồn tự động tính an tồn của
chương trình với nguồn tài nguyên phần cứng máy tính là hữu hạn hoặc
khơng có sự tương tác của con người.
Trong khi đó các phương pháp kiểm thử 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, vì vậy kỹ thuật này khơng phải là một chứng
minh tối ưu cho tính đúng đắn của chương trình. Độ phủ hạn chế là vấn đề
19


chính của các kỹ thuật dạng này. Tức là một chương trình sẽ xuất hiện lỗi nếu
các hành vi của nó vượt q giới hạn cho phép của chương trình, có nghĩa là
giao của quỹ đạo các hành vi với vùng cấm là khác rỗng [3].

Hình 2.3: Quĩ đạo khơng an tồn đối với kiểm thử/gỡ lỗi
Trong hình 2.3 biểu diễn cơ chế của kỹ thuật kiểm thử/gỡ lỗi, chỉ
một số thực thi (đường nét liền) của chương trình được kiểm thử, các thực
thi cịn lại (nét đứt) thì khơng được kiểm tra và các lỗi của chương trình
được mơ tả trong hình là vi phạm vào vùng cấm (có thể xảy ra).
2.3.3. Miền trừu tượng
Miền trừu tượng là một đại số trừu tượng, được biểu diễn dưới dạng
một thư viện các modul, cung cấp các mơ tả về tính chất trừu tượng, các toán

tử và các lệnh của chương trình trên các tập thuộc tích trừu tượng của chương
trình đó (ví dụ như thuộc tính trừu tượng các chuyển dịch biểu diễn hiệu quả
các toán tử của các lệnh chương trình và các lệnh trừu tượng, …). Miền trừu
tượng thường là một dàn đầy đủ, là sự trừu tượng hóa của tập lũy thừa [8].
Có hai loại miền trừu tượng hữu hạn và vô hạn. Miền trừu tượng hữu
hạn được sử dụng như là một thư viện đầy đủ cung cấp các mơ tả về tính chất
trừu tượng của một ngôn ngữ. Miền trừu tượng vô hạn về cơ bản giống như
miền trừu tượng hữu hạn, nó khác miền trừu tượng hữu hạn ở chỗ nó có thể
cung cấp các mơ tả về tính chất trừu tượng của các đối tượng vô hạn [3].
20


Ví dụ về miền trừu tượng
Trừu tượng hóa theo khoảng (không liên kết):
⟹ [ , ],

⟹ [ ′, ′], . ..

Trừu tượng hóa theo đa diện (có liên kết):
+

− 2 ≤ 10, . ..

Trừu tượng hóa chênh lệch-ràng buộc (liên kết mạnh):
−

≤ 5,

−


≤ 10, . ..

Hình 2.4: Biểu diễn miền trừu tượng
2.3.4. Độ phủ của kỹ thuật giải thích trừu tượng
Do q trình phân tích của kỹ thuật giải thích trừu tượng và nó được xem
xét trên ngữ nghĩa trừu tượng của chương trình. Có thể nói rằng ngữ nghĩa trừu
tượng được xem xét là tập cha của tập ngữ nghĩa cụ thể của chương trình, do
đó các ngữ nghĩa trừu tượng bao gồm tất cả các trường hợp có thể [3].
Mục đích chính của kỹ thuật giải thích trừu tượng chuyển chứng minh
bài tốn phân tích chương trình về dạng: nếu ngữ nghĩa trừu tượng

của

thỏa

mãn đặc tả (tập các quĩ đạo hành vi có thể của chương trình giao với vùng vi
phạm là tập rỗng) thì ngữ nghĩa cụ thể của

cũng thỏa mãn đặc tả. Hình 2.5

biểu diễn cơ chế trừu tượng hóa ngữ nghĩa cụ thể của giải thích trừu tượng. Từ
miền ngữ nghĩa cụ thể của chương trình được trừu tượng hóa thành miền ngữ
nghĩa trừu tượng (màu xanh) bao trọn toàn bộ quĩ đạo hành vi có thể của
21


chương trình. Khi đó, nếu miền ngữ nghĩa trừu tượng thỏa mãn đặc tả thì miền
ngữ nghĩa cụ thể cũng thỏa mãn đặc tả [3].

Hình 2.5: Trừu tượng hóa quĩ đạo hành vi của chương trình

2.3.5. Các phương pháp hình thức
Các phương pháp hình thức chính là giải thích trừu tượng, trong đó có
sự khác biệt theo nhiều cách khác nhau để có được ngữ nghĩa trừu tượng từ
ngữ nghĩa cụ thể của chương trình.
 Kiểm chứng mơ hình (Model checking)
+ Ngữ nghĩa trừu tượng của chương trình được đưa ra thủ công (bằng
tay) bởi người sử dùng;
+ Được biểu diễn dưới hình thức của một mơ hình hữu hạn của các
thực thi chương trình;
+ Ngữ nghĩa trừu tượng có thể được tính tốn tự động bằng các kỹ
thuật có liên quan tới phân tích tĩnh.
 Phương pháp suy diễn (Deductive methods)
+ Ngữ nghĩa trừu tượng được xác định bởi các điều kiện kiểm chứng
(verification conditions);
+ Người sử dùng phải cung cấp các ngữ nghĩa trừu tượng theo hình
thức lập luận qui nạp (ví dụ như bất biến);
22


+ Ngữ nghĩa trừu tượng có thể được tính tốn tự động bằng các kỹ
thuật có liên quan tới phân tích tĩnh.
 Phân tích tĩnh (Static Analysis): Ngữ nghĩa trừu tượng được tính tốn
tự động từ mã nguồn chương trình theo quy định các khái niệm trừu tượng
định nghĩa trước (mà đơi khi có thể được thay đổi tự động/bằng tay bởi người
sử dụng) [3].
2.3.6. Tính chất cần thiết của ngữ nghĩa trừu tượng
Để đảm bảo tính chính xác của kết quả phân tích, miền ngữ nghĩa trừu
tượng phải thỏa mãn một số thuộc tính cơ bản sau đây [3]:
+ Tính đủ: tất cả các lỗi đều khơng được bỏ qua, nếu trong miền ngữ
nghĩa cụ thể chứa thông tin về lỗi (giao với vùng vi phạm khác rỗng)

thì miền ngữ nghĩa trừu tượng cũng phải chứa thông tin về lỗi đó;
+ Tính chính xác: q trình trừu tượng hóa để tạo ra miền ngữ nghĩa
trừu tượng phải đủ chính xác để tránh cảnh báo sai (false alarm);
+ Đơn giản: Miền ngữ nghĩa trừu tượng phải đơn giản nhất có thể
(tránh hiện tượng bùng nổ tổ hợp)
Biểu diễn tính đủ trong hình 2.6: Miền ngữ nghĩa trừu tượng khơng
đảm bảo tính đủ nên bỏ sót lỗi/miền trừu tượng vi phạm vùng cấm.

23