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

Bùi Quang Cường

PHƯƠNG PHÁP TỰ ĐỘNG SỬA LỖI
CHO CÁC CHƯƠNG TRÌNH JAVA

LUẬN VĂN THẠC SĨ
Ngành: Khoa học máy tính

HÀ NỘI - 2020


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

Bùi Quang Cường

PHƯƠNG PHÁP TỰ ĐỘNG SỬA LỖI
CHO CÁC CHƯƠNG TRÌNH JAVA
Ngành: Khoa học máy tính
Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01 01

LUẬN VĂN THẠC SĨ

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. Phạm Ngọc Hùng

HÀ NỘI - 2020

VIETNAM NATIONAL UNIVERSITY, HA NOI
UNIVERSITY OF ENGINEERING AND
TECHNOLOGY

Bui Quang Cuong

A METHOD FOR AUTOMATED
REPAIR OF ERRORS FOR JAVA
PROGRAMS

MASTER THESIS OF COMPUTER SCIENCE
Major: Computer Science

Supervisor: Assoc. Prof., Dr. Pham Ngoc Hung

HANOI - 2020


i

LỜI CAM ĐOAN
Tôi xin cam đoan rằng những nghiên cứu về phương pháp tự động sửa lỗi cho các
chương trình Java được trình bày trong luận văn này là của tôi và chưa từng được
nộp như một báo cáo luận văn tại trường Đại học Công nghệ - ĐHQGHN hoặc bất kỳ
trường đại học khác. Những gì tơi viết ra không sao chép từ các tài liệu, không sử
dụng các kết quả của người khác mà khơng trích dẫn cụ thể. Tôi xin cam đoan công
cụ tự động sửa lỗi cho các chương trình Java tơi trình bày trong luận văn là do tôi tự
phát triển, không sao chép mã nguồn của người khác. Nếu sai tơi hồn tồn chịu
trách nhiệm theo quy định của trường Đại học Công nghệ - ĐHQGHN.


Hà Nội, ngày 15 tháng 08 năm
2020

Học viên cao học

Bùi Quang Cường


ii

TĨM TẮT
Các hệ thống phần mềm ln khơng ngừng phát triển theo lẽ tự nhiên để đáp ứng
nhu cầu thay đổi liên tục từ khách hàng và thị trường. Tuy nhiên, những thay đổi này
có thể gây ra các lỗi khiến cho những chức năng đã có của chương trình không hoạt
động đúng. Những lỗi như thế này được gọi là lỗi hồi quy. Sửa lỗi tự động (Automated
Program Repair - APR) gần đây đã cho thấy được tiềm năng lớn trong việc tự động
sửa các lỗi của phần mềm. Mặc dù với sự phát triển mạnh mẽ của APR, chỉ có một số
kỹ thuật tập trung xử lý các lỗi hồi quy. Tuy nhiên, các kỹ thuật chưa thực sự khai thác
đầy đủ thơng tin có sẵn trong lịch sử phát triển của các phần mềm (ví dụ: bản cập
nhật gây ra lỗi, v.v.) để sửa lỗi hồi quy. Hơn nữa, những kỹ thuật này không công bố
công cụ cài đặt cho cộng đồng hoặc công cụ rất hạn chế và khó có thể sử dụng để
sửa lỗi trong thực tế. Luận văn này nhằm mục đích đề xuất phương pháp sửa lỗi hồi
quy cho các chương trình Java bằng cách khai thác và mở rộng những phát hiện gần
đây về lỗi hồi quy, ví dụ: mối tương quan giữa các bản cập nhật tạo ra lỗi và sửa lỗi.
Luận văn cài đặt lại và cải tiến phương pháp sửa lỗi hồi quy tự động cho các chương
trình C (Relifix). Từ đó, xây dựng một hệ thống có tên là LyFix, cho phép người dùng
sửa lỗi hồi quy Java tự động bằng cách tận dụng các nguyên liệu sửa lỗi và các mẫu
sửa lỗi cụ thể học được từ lịch sử phát triển phần mềm. Tám mẫu sửa lỗi hồi quy,
thuật toán sửa lỗi đã được cài đặt lại dựa vào

ý tưởng của Relifix. Ngoài ra, luận văn cài đặt thêm ba mẫu sửa lỗi hồi quy mới cho
Java. Luận văn cũng thực hiện thực nghiệm để so sánh khả năng sửa lỗi của LyFix

đối với jRelifix (bản cài đặt Relifix cho Java) và các công cụ sửa lỗi tự động tốt
nhất hiện nay (jGenProg, jMutRepair, TBar) trên tập dữ liệu 51 lỗi hồi quy thực tế
của các hệ thống phần mềm Java mã nguồn mở. Kết quả cho thấy LyFix có thể
sinh ra bản vá thành cơng cho 56.8% lỗi có trong tập dữ liệu và tỉ lệ số bản vá
chính xác là 79.3% trong khi các cơng cụ khác sửa lỗi tốt nhất (TBar) với kết quả
sinh được bản vá 33.3% lỗi và tỉ lệ bản vá đúng là 41.1%.

Từ khóa: tự động sửa lỗi chương trình, lỗi hồi quy, lịch sử phát triển phần mềm


iii

LỜI CẢM ƠN
Đầu tiên và quan trọng nhất, tôi xin gửi lời cảm ơn trân trọng và sâu sắc tới
PGS. TS. Phạm Ngọc Hùng - người Thầy giáo đã trực tiếp hướng dẫn tận tình và
đóng góp những ý kiến q báu trong q trình tơi học tập, nghiên cứu và cả kinh
nghiệm cuộc sống từ những năm tháng tôi cịn là sinh viên tại trường Đại học
Cơng nghệ cho đến nay. Thầy đã không ngần ngại cho phép và hỗ trợ tôi tự lựa
chọn đề tài để thực hiện luận văn này. Tôi xin được gửi lời cảm ơn chân thành tới
TS. Bách Lê, TS. Lê Quang Lộc, và PGS. TS. Corina Pasareanu đã hướng dẫn và
hỗ trợ tôi rất nhiệt tình trong quá trình thực hiện luận văn này. Các anh và cô luôn
động viên tôi và đưa ra những câu trả lời và gợi ý ngay lập tức mỗi khi tơi gặp khó
khăn. Các anh và cơ cũng chia sẻ rất nhiều kinh nghiệm quý báu trong nghiên cứu
và cuộc sống và tôi đã học được nhiều điều từ các anh. Xin được cảm ơn ban tổ
chức chương trình Google Summer of Code 2020 và Java PathFinder Team đã
cho phép tài trợ kinh phí để tơi thực hiện đề tài trong luận văn này. Cơng trình này
cũng được tài trợ một phần từ đề tài KHCN cấp ĐHQGHN, Mã số đề tài:

QG.19.24. Cuối cùng, tôi xin được cảm ơn những lời động viên từ gia đình, người
thân, bạn bè để giúp tôi luôn vững bước trong con đường tương lai.


iv

Mục lục

1 Giới thiệu

1.1 Mở đầu . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Đóng góp . . . . . . . . . . . . . . . . . . . . . .
1.3 Bố cục luận văn . . . . . . . . . . . . . . . . .
2 Kiến thức nền tảng
2.1 Kiểm thử hồi quy và lỗi hồi quy . . . . .

2.2 Sửa lỗi chương trình tự động . . . . . .
2.2.1
2.2.2
3 Phương pháp sửa tự động lỗi hồi quy

3.1 Tổng quan phương pháp . . . . . . . . . .
3.2 Xác định bản cập nhật gây ra lỗi . . . .
3.3 Thu thập thông tin mã nguồn thay đổi

3.4 Các mẫu sửa lỗi . . . . . . . . . . . . . . . . .
3.5 Xác định vị trí gây lỗi . . . . . . . . . . . . .


3.6

4

Thuật toán sửa lỗi . . . . . . . . . . . . . . .

Cài đặt công cụ và thực nghiệm
4.1

Cài đặt công cụ . . . . . . . . . . . . . . . . .

4.2

Thực nghiệm . . . . . . . . . . . . . . . . . . .
4.2.1
4.2.2

5

Kết luận

A

Danh sách các mẫu sửa lỗi

Tài liệu tham khảo


vi

Danh sách hình vẽ


2.1 Các chiến lược kiểm thử hồi quy . . . . . . . . . . . . . . . . . . . .

2.2 Các bước tiêu chuẩn trong các kỹ thuật APR hiện nay [27]

2.3 Số lượng công bố mỗi năm về APR từ 1996 - 2019 . . . . . .

2.4 Tổng quan về xác định vị trí gây lỗi dựa trên phổ chương t
2.5 Tổng quan về các kỹ thuật sửa lỗi [14] . . . . . . . . . . . . . . .
3.1 Tổng quan phương pháp sửa tự động lỗi hồi quy . . . . . . .

3.2 Các bản cập nhật gây ra lỗi và sửa lỗi của Closure 31 [21]
3.3 Ví dụ minh họa tính độ đo giữa nguyên liệu sửa lỗi và câu
ngờ lỗi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1 Kiến trúc công cụ sửa lỗi tự động LyFix . . . . . . . . . . . . . . .


vii

Danh sách bảng

3.1 Nguyên liệu sửa lỗi và mẫu sửa lỗi sử dụng . . . . . . . . . . .

3.2 Các mẫu sửa lỗi đã cài đặt . . . . . . . . . . . . . . . . . . . . . . . . .

4.1 Thống kê các chỉ số của bộ dữ liệu lỗi hồi quy . . . . . . . . . .

4.2 Thống kê số lượng các hành động sửa lỗi của bộ dữ liệu lỗ
4.3 Kết quả sửa lỗi trên tập dữ liệu lỗi hồi quy . . . . . . . . . . . .



viii

Danh sách từ viết tắt và thuật ngữ
APR Automated Program Repair - Sửa lỗi chương trình tự động
AST Abstract Syntax Tree - Cây cú pháp trừu tượng
FL Fault Localization - Xác định vị trí gây lỗi SUT
System Under Test - Hệ thống được kiểm thử
RTS

Regression Test Selection - Lựa chọn ca kiểm thử hồi quy

TSM

Test Suite Minimization - Giảm thiểu bộ ca kiểm thử

TCP

Test Case Prioritization - Ưu tiên ca kiểm thử

BWTC Bug-witnessing Test Case - Ca kiểm thử phát hiện lỗi
BIC

Bug-inducing Commit - Bản cập nhật gây lỗi

BFC

Bug-fixing Commit - Bản cập nhật sửa lỗi

RT


Repair Templates - Các mẫu sửa lỗi, mỗi mẫu thực hiện một
tập các hành động thay đổi mã nguồn để sửa lỗi

FI

Fix Ingredients - Các nguyên liệu sửa lỗi, là những thành phần
mã nguồn có thể sử dụng làm tham số cho các mẫu sửa lỗi


1

Chương 1

Giới thiệu
1.1 Mở đầu
Các hệ thống phần mềm phát triển và tiến hóa khơng ngừng như một lẽ tự nhiên
để bắt kịp nhu cầu thay đổi liên tục từ phía khách hàng và thị trường. Q trình
phát triển phần mềm là một quá trình gia tăng, thường mang theo các tính năng
mới được cài đặt để đáp ứng các yêu cầu thay đổi của người dùng. Tuy nhiên,
những tính năng được thêm mới này có thể làm hỏng các chức năng hiện tại của
hệ thống phần mềm và do đó gây ra lỗi mới. Những lỗi này thường được gọi là lỗi
hồi quy. Lỗi hồi quy rất phổ biến trong các hệ thống phần mềm hiện nay và vẫn
đang là một thách thức lớn trong ngành công nghiệp phát triển phần mềm [35, 11].
Xác định và sửa lỗi hồi quy là một hoạt động bắt buộc trong các vòng lặp bảo trì
phần mềm [39]. Những nghiên cứu từ trước đến nay tập trung chủ yếu vào việc
hỗ trợ phát hiện và xác định lỗi hồi quy [39, 52, 26, 22]. Trong khi đó, sửa lỗi hồi
quy vẫn đang phụ thuộc lớn vào con người để gỡ và sửa lỗi một cách thủ công,
khiến công việc này tiêu tốn thời gian và rủi ro. Ví dụ, người ta đã ước tính rằng
các lập trình viên cần tới 8,5 năm để sửa một lỗi hồi quy [4].

Sửa lỗi tự động (Automated Program Repair - APR), bao gồm các pha xác định vị
trí gây ra lỗi và sửa lỗi mới xuất hiện gần đây để giúp giải quyết vấn đề này. APR tập
trung vào việc tự động quá trình gỡ lỗi phần mềm, từ đó giúp giảm bớt hoặc thậm chí
loại bỏ sự can thiệp của con người vào quá trình sửa lỗi. Các nghiên cứu


Chương 1. Giới thiệu
về APR gần đây đã đạt được một số thành cơng đáng kể và đóng góp cho ngành
nhiều kỹ thuật sửa lỗi tốt [45, 17, 12]. Facebook gần đây đã công bố công cụ sửa lỗi
tự động lần đầu tiên, được sử dụng rộng để sửa lỗi cho toàn bộ hệ thống mã nguồn
lõi mà Facebook đang vận hành [2]. Điều này khẳng định APR đang là một hướng
nghiên cứu mang lại nhiều đóng góp lớn cho lĩnh vực phát triển phần mềm.
Mặc dù với sự phát triển mạnh mẽ gần đây, chỉ có một số kỹ thuật APR tập trung
cho việc sửa lỗi hồi quy [33, 42]. Tuy nhiên, những kỹ thuật này hiện tại vẫn chưa khai
thác đầy đủ thông tin trong lịch sử phát triển của hệ thống (ví dụ: thơng tin thay đổi
trong những bản cập nhật gây ra lỗi) để phục vụ cho việc sửa lỗi. Hơn nữa, những
phương pháp sửa lỗi này không cung cấp công khai công cụ cài đặt kèm theo hoặc
cơng cụ rất hạn chế và khó có thể áp dụng để sửa lỗi trong các dự án thực tế. Luận
văn này hướng tới việc áp dụng sửa lỗi hồi quy tự động cho các chương trình Java
bằng cách cài đặt và mở rộng các phương pháp sửa lỗi và các phát hiện gần đây về
lỗi hồi quy (ví dụ: phương pháp sửa lỗi hồi quy tự động cho các chương trình C [42],
sự tương quan giữa các bản cập nhật gây ra lỗi và sửa lỗi [46]). Luận văn tập trung
vào việc sửa lỗi cho các chương trình Java bởi vì nó là một trong những ngơn ngữ lập
1

trình phổ biến nhất cho đến hiện nay. Luận văn cũng đặt mục tiêu xây dựng một
công cụ kèm theo, có tên LyFix, cho phép người dùng sửa lỗi hồi quy Java tự động và
cơng bố nó như một phần mềm mã nguồn mở để cộng đồng có thể sử dụng. Khác với
các kỹ thuật APR truyền thống, LyFix sử dụng các nguyên liệu sửa lỗi và những mẫu
sửa lỗi cụ thể học từ lịch sử phát triển của các hệ thống phần mềm để đạt kết quả

sửa lỗi tốt hơn cho các lỗi hồi quy.

1.2 Đóng góp
Luận văn phân tích bán tự động 3483 lỗi của hai bộ dữ liệu lỗi chuẩn BugSwarm
3

2

và Bears , từ đó thu thập được 51 lỗi hồi quy. BugSwarm bao gồm 3232 lỗi được
thu thập tự động dựa trên lịch sử tích hợp liên tục (TravisCI) của các ứng
1

2

/>
/>
3

/>

Chương 1. Giới thiệu
dụng mã nguồn mở. Bears bao gồm 251 lỗi được thu thập thủ công từ các
ứng dụng mã nguồn mở với mục đích phục vụ cho các công cụ APR.
4

Luận văn cài đặt và công bố miễn phí cơng cụ kèm theo LyFix , bao gồm:
– Đề xuất và cài đặt cơng thức xác định vị trí gây lỗi phù hợp cho đối
tượng là lỗi hồi quy
– Cài đặt lại tám mẫu sửa lỗi dựa trên tư tưởng sửa lỗi hồi quy cho
chương trình C ở [42]

– Đề xuất và cài đặt ba mẫu sửa lỗi hồi quy mới cho Java (mở rộng dựa
trên [36] và học từ bộ dữ liệu 51 lỗi quy đã thu thập)
– Đề xuất và cài đặt thuật toán cải tiến từ thuật toán sửa lỗi của [42] để
sinh được nhiều bản vá hơn và các bản vá có chất lượng tốt hơn
Luận văn tiến hành thực nghiệm đánh giá khả năng sửa lỗi của LyFix so với
jRelifix (là công cụ sửa lỗi phiên bản Java mà luận văn đã cài đặt lại giống
với phương pháp sửa lỗi đề xuất trong [42]), jGenProg, jMutRepair và TBar
trên tập dữ liệu 51 lỗi hồi quy. Đây là những lỗi hồi quy thực tế từ những hệ
thống phần mềm mã nguồn mở được phát triển và kiểm thử tốt.

1.3 Bố cục luận văn
Các phần còn lại của luận văn được cấu trúc như sau. Chương 2 cung cấp các
kiến thức nền tảng về tính chất của lỗi hồi quy và sửa lỗi tự động. Chương 3 mô
tả phương pháp sửa lỗi đề xuất, bao gồm các bước: xác định bản cập nhật gây ra
lỗi, thu thập thông tin mã nguồn nguồn thay đổi và nguyên liệu sửa lỗi, xác định vị
trí gây ra lỗi, các mẫu sửa lỗi và thuật toán sửa lỗi. Chương 4 mô tả về kiến trúc
và cài đặt công cụ, các kết quả thực nghiệm đánh giá về khả năng sửa lỗi hồi quy
của phương pháp đề xuất được tiến hành và bàn luận. Cuối cùng, Chương 5 kết
luận lại toàn bộ công việc luận văn đã thực hiện, kèm theo các cơng việc tiếp theo
có thể thực hiện để cải tiến và mở rộng công cụ.
4

/>

4

Chương 2

Kiến thức nền tảng
Chương này cung cấp các kiến thức nền tảng cho luận văn. Đầu tiên, kiến thức

kiểm thử hồi quy sẽ được giới thiệu một cách tổng quan. Tiếp theo, kiến thức về
sửa lỗi chương trình tự động sẽ được trình bày, bao gồm: tổng quan, xác định vị
trí gây ra lỗi, và các phương pháp sửa lỗi tự động phổ biến hiện nay.

2.1 Kiểm thử hồi quy và lỗi hồi quy
Các hệ thống phần mềm thay đổi khơng ngừng theo thời gian. Khi có một thay đổi
mới được thêm vào mã nguồn, thay đổi này có thể phá hỏng các chức năng khác
của chương trình mà trước đó hoạt động bình thường. Kiểm thử hồi quy
(regression testing) là một kỹ thuật được sử dụng để phát hiện các lỗi khi chương
trình thay đổi. Kiểm thử hồi quy có thể áp dụng ở tất các mức kiểm thử: đơn vị,
tích hợp, hệ thống, và chấp nhận [16]. Lỗi được phát hiện nhờ vào kiểm thử hồi
1

quy gọi là lỗi hồi quy. Lỗi hồi quy được chia thành ba loại :
Local: Thay đổi mới gây ra lỗi, làm các chức năng tồn tại từ trước không
hoạt động đúng như mong muốn nữa. Cách sửa là khôi phục lại phần mã
nguồn gây ra lỗi này.
1

/>

Chương 2. Kiến thức nền tảng
Unmasking: Thay đổi mới khiến luồng thực thi chương trình đi vào những
câu lệnh gây ra những lỗi đã có từ trước. Cách sửa là thêm hoặc cập nhật lại
các câu lệnh điều kiện để giúp luồng thực thi chương trình khơng cịn đi vào
các câu lệnh gây lỗi nữa.
Remote: Những thay đổi mới tạo ra các lỗi ở những phần mã nguồn khác
trong chương trình. Để sửa những lỗi này, ta buộc phải cập nhật lại mã
nguồn ở những vị trí có lỗi cho phù hợp với thay đổi hoặc ta cần phải tạo ra
các câu lệnh điều kiện để luồng thực thi chương trình khơng đi vào những

câu lệnh gây lỗi đối với một số trạng thái nhất định.
Kiến thức về thông tin, tính chất của các loại lỗi hồi quy sẽ giúp luận văn này
phát triển kỹ thuật xác định vị trí lỗi, lựa chọn được các nguyên liệu sửa lỗi phù
hợp, và thiết kế được các mẫu sửa lỗi tốt hơn. Kiến thức về các kỹ thuật kiểm thử
hồi quy giúp luận văn thiết kế thuật toán, lựa chọn bộ ca kiểm thử rút gọn để tiết
kiệm thời gian thẩm định bản vá.

HÌNH 2.1: Các chiến lược kiểm thử hồi quy

Hình 2.1 mô tả các chiến lược phổ biến được sử dụng để thực hiện kiểm thử hồi
quy hiện nay. Trong thực tế, người ta chỉ thực thi một phần của bộ ca kiểm thử để
thực hiện kiểm thử hồi quy. Thử thách lớn nhất là cần thực thi lựa chọn đúng những
ca kiểm thử có thể giúp đánh giá tốt nhất cho những phần mã nguồn thay đổi. Thực
thi lại toàn bộ ca kiểm thử (Retest All) chỉ khả thi cho những dự án nhỏ. Trong những
dự án có quy mơ lớn, việc thực thi lại tồn bộ ca kiểm thử hầu như là


Chương 2. Kiến thức nền tảng
điều khơng thể bởi vì nó tốn rất nhiều thời gian và có thể làm chậm quá trình phát
hành sản phẩm tới khách hàng.
Giảm thiểu bộ ca kiểm thử (Test Suite Minimization - TSM): Trong những hệ
thống phần mềm quy mô lớn, bộ ca kiểm thử cho những hệ thống này thường rất
đồ sộ, và luôn được cập nhật thêm mới các ca kiểm thử mỗi khi trải qua một bản
phát triển mới. Việc thêm các ca kiểm thử mới có thể khiến những ca kiểm thử
khác trở nên dư thừa bởi vì chức năng ca kiểm thử cũ có thể cũng đã được kiểm
tra bởi những ca kiểm thử mới. Loại bỏ những ca kiểm thử dư thừa này không
làm ảnh hướng tới độ phủ của bộ kiểm thử [41]. Các kỹ thuật TSM nhắm tới mục
tiêu xác định và loại bỏ những ca kiểm thử dư thừa này ra khỏi bộ ca kiểm thử.
Một số nghiên cứu đã được đề xuất có kết quả tốt như là [25, 47, 15].
Lựa chọn ca kiểm thử (Test Case Selection): Có tên gọi khác là Regression

Test Selection - RTS. Các kỹ thuật RTS giống với các kỹ thuật TSM là đều lựa
chọn một tập ca kiểm thử con và chỉ thực hiện kiểm thử hồi quy trên tập đó. Điểm
khác biệt chính giữa hai loại kỹ thuật này là RTS lựa chọn ca kiểm thư dựa vào
các thay đổi của hệ thống được kiểm thử (System Under Test - SUT) cịn TSM thì
khơng. Các kỹ thuật TSM thường lựa chọn ca kiểm thử dựa vào các chỉ số như độ
phủ kiểm thử được đo từ một phiên bản nhất định của SUT. Ngược lại, RTS lựa
chọn các ca kiểm thử dựa trên sự liên quan của chúng so với thay đổi giữa hai
phiên bản của nguồn của SUT. Có nhiều nghiên cứu tập trung đã vào đề xuất các
kỹ thuật RTS [39], [52], [53].
Ưu tiên ca kiểm thử (Test Case Prioritization - TCP): Các kỹ thuật TCP
khơng lựa chọn một tập các ca kiểm thử cịn mà tập trung vào việc sắp xếp độ ưu
tiên thực thi của các kiểm thử theo một thứ tự dựa vào một số tiêu chí nào đó để
có thể tìm được lỗi nhanh nhất. Điều này giúp cho các kiểm thử viên có thể tối đa
tỷ lệ có thể tìm được lỗi sớm của bộ kiểm thử. Các kỹ thuật TCP có thể chia làm
ba nhóm chính dựa trên các mức điều khiển, câu lệnh, và hàm của chương trình
[38]. Một số nghiên cứu đề xuất các kỹ thuật TCP là [26], [22], [23].


Chương 2. Kiến thức nền tảng

2.2 Sửa lỗi chương trình tự động
Sửa lỗi chương trình là một trong các bước của cơng việc gỡ lỗi chương trình cũng
như vịng đời của lỗi chương trình, bao gồm: Nhận diện lỗi - Nhận diện sự tồn tại của
lỗi trong chương trình, quan sát các dấu hiện của lỗi để phục vụ cho các bước sau;
Xác định vị trí gây ra lỗi - Thường là bước khó nhất, mục tiêu là để xác định xem phần
nào của chương trình gây ra lỗi, cụ thể nhất là ở dòng nào; Sửa lỗi - Xác định cách
giải quyết lỗi như thế nào, sau đó đề xuất bản vá và thẩm định lại bản vá.

HÌNH 2.2: Các bước tiêu chuẩn trong các kỹ thuật APR hiện nay [27]


Sửa lỗi chương trình tự động nhắm tới mục đích tự động hóa q trình gỡ lỗi,
giảm nhu cầu về sự can thiệp của con người trong công việc này. Các kỹ thuật
APR hiện tại thường gồm ba bước chính để thực hiện nhiệm vụ sửa lỗi một hồn
chỉnh như mơ tả ở Hình 2.2: Xác định vị trí gây ra lỗi ! Sinh và đề xuất bản vá !
Thẩm định bản vá. Tương tự ở quá trình gỡ lỗi tự nhiên của con người, mơ-đun
xác định vị trí gây lỗi ở APR cũng nhằm mục đích xác định các phần mã nguồn
nghi ngờ gây ra lỗi (ở mức dịng, phương thức, hoặc tệp). Mơ-đun sinh bản vá sẽ
cố gắng sửa lỗi bằng cách tạo ra nhiều bản vá ứng cử viên nhờ việc biến đổi mã
nguồn có lỗi theo phương pháp đề xuất (cú pháp, ngữ nghĩa, hướng dữ liệu, v.v.).
Những bản vá ứng cử viên này sẽ được mơ-đun thẩm định bản vá kiểm tra xem
có thực sự sửa lỗi thành công hay không thông qua việc thực hiện đánh giá
chương trình đã được vá lỗi theo một đặc tả cho trước (bộ ca kiểm thử, đặc tả
hình thức, v.v.). Kết quả cuối cùng sẽ là một danh sách bản vá lỗi được đề xuất
cho người dùng mà có thể sử dụng để sửa lỗi chương trình ban đầu.
Từ đầu những năm 2000, đã có rất nhiều nghiên cứu được thực hiện nhằm đề
xuất các giải pháp phát hiện lỗi trong phần mềm [3, 6, 40] và xác định vị trí gây ra


Chương 2. Kiến thức nền tảng
lỗi [37, 18, 19]. Các nghiên cứu cho việc tự động sửa lỗi xuất hiện theo sau với
một số lượng bài báo còn hạn chế. Tuy nhiên, kể từ khi Weimer và cộng sự giới
thiệu một phương pháp sửa lỗi mới dựa trên tư tưởng lập trình di truyền [45] vào
năm 2009, APR đã phát triển rất mạnh mẽ và trở thành một hướng nghiên cứu
hẹp thiết yếu đối với lĩnh vực công nghệ phần mềm. Điều này dễ dàng được nhận
thấy ở biểu đồ thống kế số lượng công bố các nghiên cứu về APR trong giai đoạn
2

1996 - 2019 trong Hình 2.3 . Số lượng các công bố nghiên cứu về APR mỗi năm
trước năm 2009 là dưới 5 công bố và sau năm 2009 không ngừng tăng mạnh đạt
số lượng xấp xỉ 50 công bố ở các năm gần đây như năm 2018, 2019.


HÌNH 2.3: Số lượng cơng bố mỗi năm về APR từ 1996 - 2019
2

/>

Chương 2. Kiến thức nền tảng

2.2.1 Xác định vị trí gây ra lỗi
Nhìn vào sơ đồ ở Hình 2.2, ta có thể thấy rằng xác định vị trí gây lỗi là bước đầu
tiên trong các bước xử lý của bất kỳ phương pháp APR nào. Xác định vị trí gây lỗi
được sử dụng để xác định những vị trí mã nguồn nghi ngờ gây ra lỗi. Những vị trí
mã nguồn này sẽ được đưa vào các hệ thống APR để tập trung sửa lỗi tại đó. Ta
sẽ tìm hiểu tổng quan các kỹ thuật xác định vị trí gây lỗi hiện nay, và sau đó tập
trung vào kỹ thuật xác định vị trí gây lỗi dựa trên phổ (spectrum-based Fault
Localization) - là chiến lược xác định lỗi được sử dụng phổ biến nhất trong các kỹ
thuật APR và trong luận văn này.
Các kỹ thuật xác định vị trí gây lỗi truyền thống rất trực quan và đơn giản, bất
cứ người lập trình nào cũng có thể sử dụng. Ta có thể nhắc tới bốn phương pháp
sau đây [48]:
Hệ thống log: Sử dụng các câu lệnh dùng để in các giá trị trong chương
trình (ví dụ: câu lệnh System.out.println()). Đây là một cách cực kỳ đơn giản
và hữu hiệu để theo dõi thơng tin về trạng thái của chương trình. Khi mà phát
hiện có lỗi trong chương trình, nhà phát triển có thể điều tra log của chương
trình để tìm ra vị trí lỗi xuất phát từ đâu.
Assertions: Là các câu lệnh do người phát triển thêm vào để đảm bảo các giá
trị trạng thái của chương trình đúng với mong muốn tại thời điểm chèn assertion
(ví dụ: assertEquals(5, arr.length)). Chương trình sẽ dừng lại ngay lập tức nếu
như một trong các câu lệnh assertion đánh giá sai. Từ đó nhà phát triển có thể
biết được lỗi bắt đầu ở câu lệnh cuối cùng thay đổi giá trị của biến được kiểm

tra trong câu lệnh assertion (như ví dụ trên, biến này là arr.length).
Breakpoints: Các trình gỡ lỗi sẽ cho phép người đặt các Breakpoint này.
Break-point được sử dụng để dừng chương trình khi luồng thực thi đi đến một
điểm mong muốn, và nó cho phép nhà phát triển có thể theo dõi được trạng thái
hiện tại của chương trình. Thậm chí nhà phát triển có thể thay đổi được giá trị
các biến, thêm các câu lệnh mới ngay sau điểm Breakpoint để đánh giá và tìm


Chương 2. Kiến thức nền tảng
hiểu thêm thông tin về lỗi để xác định vị trí gây ra lỗi. Một số trình gỡ lỗi hỗ
3

4

trợ các tính năng này là GNU GDB , Microsoft Visual Studio Debugger .
Profiling: Là một phương pháp phân tích các chỉ số trong lúc chạy chương trình
như mức sử dụng bộ nhớ, tốc độ thực thi, thường được sử dụng để đánh giá và
tối ưu chương trình. Tuy nhiên, phương pháp này có thể được sử dụng để tìm
ra một số lỗi chương như: Xác định lỗi rò rỉ bộ nhớ, Phát hiện số lần

thực thi không mong muốn của một hàm, v.v. Một số cơng cụ tiêu biểu có thể
5

6

nói đến là Valgrind , VisualVM .
Các kỹ thuật xác định vị trí gây lỗi truyền thống thường được thực hiện một
cách thủ công hoặc bán tự động. Chính vì vậy, các kỹ thuật xác định vị trí gây lỗi
nâng cao ra đời, nhằm giảm thiểu tối đa sự can thiệp của con người vào q trình
xác định vị trí lỗi. Các kỹ thuật xác định vị trí gây lỗi nâng cao phổ biến hiện này có

thể chia làm tám loại chính [48]: Dựa trên lát cắt (slide-based), Dựa trên mật đổ
phổ chương trình (spectrum-based), Dựa trên xác suất (statistics-based), Dựa
trên trạng thái chương trình (state-based), Dựa trên học máy (machine learningbased), Dựa trên khai phá dữ liệu (data mining-based), Dựa trên mơ hình (modelbased), và Một số kỹ thuật khác [5, 7, 13].

HÌNH 2.4: Tổng quan về xác định vị trí gây lỗi dựa trên phổ chương
trình

Hiện nay, thường thì các kỹ thuật APR đều sử dụng cùng một chiến lược xác
định vị trí lỗi là dựa trên phổ chương trình. Phổ chương trình cung cấp các thông
3

/>
4

5

/>


6




Chương 2. Kiến thức nền tảng
tin thực thi của chương trình theo một số khía cạnh nhất định. Phổ chương trình
có thể dùng để theo dõi hành vi của chương trình, do đó nó có ích cho việc xác
định vị trí gây lỗi. Khi một đường thực thi thất bại, những thơng tin trên đường
thực thi đó có thể được sử dụng để xác định ra những dòng mã nguồn nghi ngờ
gây ra lỗi. Ví dụ như thơng tin về độ phủ mã nguồn (code coverage), hoặc ESHS

(Executable Statement Hit Spectrum) có thể cho ta biết những câu lệnh nào được
thực thi khi thực hiện đường thực thi thất bại. Từ đó, giảm khơng gian tìm kiếm
cho việc xác định các câu lệnh nghi ngờ gây ra lỗi.
Có nhiều kỹ thuật xác định vị trí gây lỗi dựa trên phổ ra đời (chủ yếu dựa trên
ESHS), trong đó có một kỹ thuật dựa trên hệ số tương đồng nổi tiếng nhất là
Tarantula [20]. Kỹ thuật này sử dụng thông tin về độ phủ các câu lệnh và kết quả
của các lần thực thi bộ kiểm thử. Từ đó, tính ra độ nghi ngờ gây lỗi cho các câu
lệnh trong chương trình theo Cơng thức 2.1. Giá trị của cơng thức này được tính
bằng tỉ lệ các ca kiểm thử failed đi qua câu lệnh s chia cho tổng tỉ lệ các ca kiểm
failed và passed đi qua câu lệnh s.

Tarantula(s) =

Ochiai(s) =
Trong đó: s là câu lệnh được tính độ nghi ngờ, f ailed(s) là số lượng ca kiểm
thử thất bại có đường thực thi qua s, passed(s) là số lượng ca kiểm thử thất bại
có đường thực thi qua s, total f ailed là tổng số lượng ca kiểm thử thất bại, total
passed là tổng số lượng ca kiểm thử thành công.
Gần đây, kỹ thuật Ochiai [1] được đề xuất và thực nghiệm cho thấy Ochiai có kết
quả đánh giá tốt hơn so với Tarantula. Độ nghi ngờ của các câu lệnh theo Ochiai


Chương 2. Kiến thức nền tảng
7

được tính theo Cơng thức 2.2. Hình 2.4 mơ tả tổng quan về kỹ thuật xác định vị
trí gây lỗi dựa trên phổ chương trình với độ nghi ngờ của các câu lệnh tính bằng
cơng thức Ochiai. Với đầu vào là chương trình và bộ ca kiểm thử, thơng tin về phổ
chương trình sẽ thu được nhờ thực thi tất cả ca kiểm thử (đường thực thi của ca
kiểm thử chạy qua những câu lệnh nào). Những thư viện hỗ trợ nhiệm vụ này có

8

9

thể là JaCoCo , PIT , v.v. Tiếp đó, những thơng tin về phổ này được sử dụng để
tính tốn độ nghi ngờ cho từng câu lệnh dựa vào công thức đã đề xuất, giá trị độ
nghi ngờ thuộc đoạn [0.0, 1.0].

2.2.2 Các phương pháp sửa lỗi tự động hiện nay
Hiện nay, các pnghiên cứu sửa lỗi tự động có thể chia thành ba loại chính: sửa lỗi
dựa trên phỏng đốn/cú pháp (heuristic-based), sửa lỗi dựa trên ràng buộc/ngữ
nghĩa (constraint-based), và sửa lỗi dựa trên học máy/dữ liệu (learning-based)
[14]. Hình 2.5 mô tả tổng quan các phương pháp sửa lỗi này.
Các phương pháp sửa lỗi dựa trên phỏng đoán thường sử dụng chiến lược Sinh
và Thẩm định (Generate-and-Validate). Sau khi nhận kết quả các vị trí mã nguồn nghi
ngờ có lỗi từ mơ-đun xác định vị trí gây lỗi, những phương pháp này đầu tiên sẽ sinh
ra một tập các biến đổi mã nguồn (bằng cách thêm, sửa, xóa các thành phần mã
nguồn ở vị trí lỗi), gọi là khơng gian tìm kiếm. Sau khi áp dụng những biến đối mã
nguồn này vào chương trình có lỗi sẽ thu được một tập các bản vá ứng cử viên. Quá
trình này gọi là Sinh. Tiếp theo, quá trình Thẩm định sẽ thực thi các ca kiểm thử trên
các chương trình đã áp dụng các bản vá ứng cử viên và đếm số lượng ca kiểm thử
thành công. Nếu tất cả ca kiểm thử đều thành cơng, thì bản vá ứng cử viên đó được
coi là một bản vá chính thức của chương trình có lỗi ban đầu. Nhược điểm của các kỹ
thuật này là khơng gian tìm kiếm có thể vơ cùng lớn bởi vì có vơ số cách kết hợp của
các thành phần mã nguồn với nhau để tạo thành một bản vá. Một số cơng cụ tiêu biểu
có thể kể đến khi nói đến những phương pháp này bao gồm GenProg [45], ssFix [49],
SimFix [17], HDRepair [24], v.v.
7
8


/>
/>
9




Chương 2. Kiến thức nền tảng

HÌNH 2.5: Tổng quan về các kỹ thuật sửa lỗi [14]

Các phương pháp sửa lỗi dựa trên ngữ nghĩa sử dụng một phương pháp
khác so với chiến lược của những phương pháp dựa trên phỏng đoán. Những
phương pháp này tập trung xây dựng ra hệ các ràng buộc để phục vụ cho việc
sinh các bản vá. Hệ các ràng buộc này thường mô tả về một phần mã nguồn (mã
nguồn vá lỗi) mà có thể thỏa mãn được về kiểu, giá trị của biến hoặc hành vi được
mô tả trong các ràng buộc. Phần mã nguồn vá lỗi này sẽ được coi như là một hàm
ẩn. Ví dụ các phương pháp thực thi tượng trưng (symbolic execution) có thể trích
xuất ra được các thuộc tính của hàm ẩn này, sau đó các thuộc tính này sẽ được
tổng hợp thành hệ các ràng buộc. Bằng cách sử dụng các bộ giải ràng buộc (ví dụ
Z3, CVC4, v.v.) hoặc các thuật tốn tìm kiếm cao cấp, hệ các ràng buộc sẽ được
giải. Phần mã nguồn vá lỗi sẽ được tổng hợp từ kết quả giải hệ các ràng buộc
dựa trên các phương pháp tổng hợp chương trình (program synthesis). Những
phương pháp này thường sửa hiệu quả cho các lỗi liên quan đến các biểu thức
điều kiện ở câu lệnh if như sửa điều kiện sai, thêm điều kiện cịn thiếu. Một số
cơng cụ đại diện cho phương pháp này là SPS [31], Nopol [51], ACS [50], v.v.


Chương 2. Kiến thức nền tảng
Các phương pháp sửa lỗi dựa trên học máy thường sử dụng các kỹ thuật học

máy tiên tiến, đặc biệt là học sâu để giúp tăng khả năng sửa lỗi. Số lượng lớn dữ
liệu về các bản vá tự nhiên trong quá trình phát triển phần mềm của con người từ
các hệ thống mã nguồn mở (ví dụ: SourceForge, Github, v.v.) đã cho phép các kỹ
thuật này phát triển mạnh mẽ. Cho đến nay, các phương pháp sửa lỗi dựa trên
học máy có ba loại chính:
Học tập các chương trình mã nguồn khơng có lỗi, từ đó đánh giá độ đúng
đắn của các bản vá ứng cử viên sinh ra từ các phương pháp khác [30]
Học các mẫu sửa lỗi được tổng hợp từ các bản vá do con người thực hiện
để chuyển đổi từ mã nguồn có lỗi sang mã nguồn đúng [29]
Học cách cải tiến quá trình sửa lỗi và huấn luyện các mơ hình sửa lỗi end-toend, là các mơ hình mà có thể dự đốn được code đúng từ code có lỗi mà
không cần sử dụng bất cứ thông tin về ngữ cảnh nào (giống mơ hình phục
vụ cho việc dịch ngôn ngữ tự động) [8]
Trong luận văn này, phương pháp sửa lỗi tự động dựa trên mẫu sửa lỗi
(template-based repair) được sử dụng. Phương pháp này có thể coi là một phương
pháp con của sửa lỗi dựa trên phỏng đoán. Một mẫu sửa lỗi bao gồm thành phần
mã nguồn (ví dụ: câu lệnh, biểu thức, v.v.) và hành động sửa lỗi (ví dụ: thêm, sửa,
xóa, v.v.). Để sửa lỗi với mẫu sửa lỗi, thì thuật tốn sửa lỗi cần chọn ra đúng mẫu
thích hợp để sửa được lỗi đó (ví dụ: đơn giản nhất là lựa chọn ngẫu nhiêu, hoặc
lựa chọn dựa vào thông tin ngữ cảnh của mã nguồn tại vị trí cần sửa). Các mẫu
sửa lỗi có thể được tạo ra bằng những cách sau:
Tổng hợp thủ công: Các nhà nghiên cứu phân tích các bản vá của con người
đã có và tự tạo và lựa chọn ra những mẫu sửa lỗi một cách thủ công
Theo xác suất: Sau khi thu thập được toàn bộ các mẫu sửa lỗi theo cách tự
động hoặc thủ công, tác giả chọn ra những mẫu có độ phổ biến nhất trong
tập dữ liệu để dùng cho kỹ thuật