1
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Đức Anh
PHƯƠNG PHÁP PHÂN TÍCH MÃ NGUỒN VÀ
SINH DỮ LIỆU KIỂM THỬ CHO CÁC DỰ ÁN C/C++
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Ĩ: KỸ THUẬT PHẦN MỀM
Cán bộ hướng dẫn: PGS. TS. Phạm Ngọc Hùng
HÀ NỘI - 2017
1
Kiểm thử đơn vị là một trong những pha quan trọng nhất
để đảm bảo chất lượng cao của phần mềm, đặc biệt các
phần mềm nhúng. Hai phương pháp được sử dụng phổ
biến gồm kiểm thử hộp đen (black-box testing) và kiểm
thử hộp trắng (white-box testing). Kiểm thử hộp đen chỉ
kiểm tra tính đúng đắn của đầu ra với đầu vào cho trước
mà không quan tâm đến mã nguồn chương trình. Ngược
lại, phương pháp kiểm thử hộp trắng đánh giá chất lượng
mã nguồn bằng cách sử dụng các kĩ thuật phân tích mã
nguồn. Tuy nhiên, bởi vì kiểm thử hộp trắng đi sâu vào
phân tích mã nguồn nên kĩ thuật này cho phép phát hiện
được các lỗi tiềm ẩn mà kiểm thử hộp đen không phát
hiện được. Tuy nhiên, chi phí kiểm thử hộp trắng lớn hơn
rất nhiều so với kiểm thử hộp đen. Đặc biệt, trong các dự
án công nghiệp, chi phí kiểm thử hộp trắng có thể chiếm
hơn 50% tổng chi phí phát triển phần mềm. Nguyên nhân
của tình trạng này là do số lượng hàm cần kiểm thử lên
tới hàng nghìn, thậm chí hàng chục nghìn hàm. Kết quả
là chi phí để kiểm thử hết những hàm này khá lớn, ảnh
hưởng khá nhiều đến tốc độ phát triển dự án. Vì thế, quá
trình kiểm thử hộp trắng cần được tự động hóa để giải
quyết bài toán về chi phí.
Hai hướng chính trong kiểm thử đơn vị theo phương
pháp kiểm thử hộp trắng gồm phát hiện lỗi và tối đa hóa
độ phủ. Cho một hàm cần kiểm thử hộp trắng, hàm này
2
có thể có lỗi tiềm ẩn rất khó phát hiện. Yêu cầu chính là
sinh tập ca kiểm thử để kiểm tra chất lượng hàm này.
Theo hướng đầu tiên, tập ca kiểm thử này có thể chỉ gây
lỗi như lỗi chia cho 0, lỗi tràn bộ nhớ. Hướng thứ hai yêu
cầu sinh tập ca kiểm thử sao cho số lượng nhánh, câu
lệnh, hoặc điều kiện con được thực thi lớn nhất. Khái
niệm độ phủ liên quan đến chất lượng ca kiểm thử theo
hướng tối đa hóa độ phủ. Độ phủ càng lớn đồng nghĩa
với chất lượng ca kiểm thử càng tốt. Ví dụ, nếu hàm cần
kiểm thử có 10 nhánh mà chỉ có 9 nhánh được đi qua bởi
tập 3 ca kiểm thử thì độ phủ đạt được bằng 90%. Điều đó
có nghĩa là trong hàm này có một nhánh thừa cần được
phát hiện, hoặc có thể hàm này có lỗi tiềm ẩn nào đó mà
kiểm thử hộp đen không phát hiện ra. Các công cụ kiểm
thử tiêu biểu theo hướng này có thể kể đến PathCrawler,
CAUT, CUTE, CREST. Đối với bài toán sinh tập ca
kiểm thử để đạt độ phủ tối đa, hai phương pháp kiểm thử
hộp trắng được sử dụng phổ biến gồm kiểm thử tĩnh
(static tesing) và kiểm thử động (DSE - dynamic
symbolic execution). Tư tưởng chính của phương pháp
kiểm thử theo hướng tĩnh là sinh ca kiểm thử bằng phân
tích mã nguồn. Theo như phương pháp này, tất cả mọi cú
pháp trong chương trình cần được hỗ trợ phân tích đầy
đủ. Tốc độ là một trong những ưu điểm chính của
phương pháp kiểm thử theo hướng tĩnh bởi kĩ thuật này
không yêu cầu thực thi chương trình như kĩ thuật DSE.
3
Tuy nhiên, phương pháp này khó áp dụng cho các dự án
công nghiệp bởi vì rất khó để hỗ trợ tất cả mọi cú pháp
có thể của ngôn ngữ C/C++. Trái ngược với phương pháp
kiểm thử tĩnh, phương pháp kiểm thử DSE không yêu
cầu phải phân tích mọi cú pháp của chương trình để sinh
ca kiểm thử. Để giảm chi phí phân tích mã nguồn mà vẫn
đạt độ phủ tối đa, phương pháp kiểm thử DSE kết hợp
quá trình phân tích cú pháp chương trình với trình biên
dịch KLEE, PathCrawler, DART, CAUT, CREST. Bởi
thế, phương pháp kiểm thử DSE dễ dàng đạt được độ phủ
cao với nỗ lực phân tích chương trình nhỏ hơn so với
phương pháp kiểm thử theo hướng tĩnh.
Phương pháp kiểm thử theo hướng động gồm hai kĩ thuật
kiểm thử được sử dụng phổ biến gồm kĩ thuật EGT
(execution generated testing) và kĩ thuật concolic. Kĩ
thuật EGT được áp dụng trong công cụ sinh ca kiểm thử
tự động nổi tiếng KLEE (2008) – một công cụ được đánh
giá cao bởi tính hiệu quả của nó. Tư tưởng chính của kĩ
thuật EGT là vừa biên dịch và chạy chương trình vừa
sinh ca kiểm thử trực tiếp. Chẳng hạn, khi trình biên dịch
gặp một điều kiện, ca kiểm thử tương ứng nhánh đúng và
nhánh sai của điều kiện này được sinh ra. Tại đây, với
mỗi ca kiểm thử, một tiến trình mới được tạo ra sẽ phân
tích chương trình theo nhánh đúng/sai đó. Quá trình sinh
ca kiểm thử chỉ dừng khi một trong ba điều kiện sau thỏa
4
mãn (1) đạt độ phủ tối đa (2) không còn nhánh đúng/sai
nào để phân tích tiếp, (3) đạt đến giới hạn thời gian cho
phép. Nhược điểm chính của kĩ thuật EGT là hiệu suất
thấp khi kiểm thử hàm chứa vòng lặp có số lần lặp lớn,
hoặc chứa lời gọi đệ quy. Khi đó, số tiến trình được tạo
ra có thể từ hàng nghìn tới hàng chục nghìn. Kĩ thuật này
thể hiện tính hiệu quả khi tìm các lỗi tiềm ẩn trong
chương trình bởi vì EGT xem xét mọi trường hợp có thể
xảy ra. Tuy nhiên, kĩ thuật EGT không phù hợp với bài
toán sinh ca kiểm thử đạt độ phủ tối đa bởi vì chúng ta
không cần xem xét hết mọi trường hợp khi sinh ca kiểm
thử. Kĩ thuật hay được sử dụng kế tiếp gọi là concolic
được đề xuất vào năm 2005 và cài đặt lần đầu tiên trong
công cụ DART. Sau này, kĩ thuật concolic liên tục được
cải tiến trong các công cụ PathCrawler, CUTE, CAUT,
CREST. Trong phương pháp này, ca kiểm thử đầu tiên
được sinh ngẫu nhiên, sau đó đẩy vào hàm cần kiểm thử
để lấy danh sách các câu lệnh đi qua. Với một ca kiểm
thử, tập các ca kiểm thử này gọi là một đường thi hành.
Ca kiểm thử kế tiếp được sinh ra dựa trên hai thông tin
gồm (1) tiêu chí độ phủ (phủ câu lệnh/nhánh) (2) trạng
thái của chương trình. Quá trình sinh ca kiểm thử kết
thúc khi (1) độ phủ đạt được tối đa, hoặc (2) đạt đến giới
hạn thời gian. Hiện tại, nhiều công trình nghiên cứu đưa
ra nhiều chiến thuật chọn đường thi hành khác nhau để
sinh ca kiểm thử kế tiếp càng tăng độ phủ càng tốt như