TỔNG QUAN VỀ PHƯƠNG PHÁP<br />
SINH DỮ LIỆU KIỂM THỬ TỰ ĐỘNG<br />
TỪ MÃ NGUỒN<br />
<br />
Trần Nguyên Hương Vũ Mạnh Điệp<br />
Trường Cao đẳng Sư phạm Trung ương Trường Cao đẳng Sư phạm Trung ương<br />
Email: huongtw@gmail.com Email: diepvm@gmail.com<br />
<br />
<br />
Tóm tắt: Kiểm thử là quá trình kiểm tra chương trình với mục đích phát hiện lỗi. Kiểm<br />
thử phần mềm cần nhiều thời gian và chi phí của dự án, thông thường chiếm 50% chi phí<br />
của dự án và 35% tổng thời gian phát triển phần mềm. Bước quan trọng của kiểm thử<br />
phần mềm là tự động sinh các bộ dữ liệu kiểm thử từ mã nguồn một cách tối ưu dựa trên<br />
các tiêu chuẩn cho trước. Bài báo này tóm tắt các kỹ thuật chính trong việc sinh dữ liệu<br />
kiểm thử tự động từ mã nguồn và một số hướng nghiên cứu cải tiến.<br />
Từ khóa: Kiểm thử phần mềm, sinh dữ liệu kiểm thử tự động, kiểm thử tĩnh, kiểm thử<br />
động, mã nguồn.<br />
<br />
<br />
<br />
I. TỔNG QUAN VỀ SINH DỮ LIỆU KIỂM nguồn chương trình. Ngược lại, phương pháp<br />
THỬ DỰA TRÊN MÃ NGUỒN kiểm thử hộp trắng đánh giá chất lượng mã<br />
nguồn bằng cách sử dụng các kĩ thuật phân<br />
Trong quá trình phát triển phần mềm, kiểm<br />
tích mã nguồn. Do kiểm thử hộp trắng đi sâu<br />
thử là một giai đoạn quan trọng và thực sự<br />
vào phân tích mã nguồn nên kĩ thuật này cho<br />
cần thiết để tạo ra phần mềm có chất lượng<br />
cao. Có nhiều mức kiểm thử trong giai đoạn phép phát hiện các lỗi tiềm ẩn mà kiểm thử<br />
này, bao gồm kiểm thử đơn vị, kiểm thử tích hộp đen không phát hiện được. Tuy nhiên, chi<br />
hợp, kiểm thử hệ thống và kiểm thử chấp phí kiểm thử hộp trắng lớn hơn rất nhiều so<br />
nhận. Trong các mức trên thì kiểm thử đơn với kiểm thử hộp đen. Đặc biệt, trong các dự<br />
vị (unit test) là một trong những pha quan án công nghiệp, chi phí kiểm thử hộp trắng<br />
trọng nhất để đảm bảo chất lượng của phần có thể chiếm hơn 50% tổng chi phí phát triển<br />
mềm. Hai phương pháp được sử dụng phổ phần mềm. Nguyên nhân của tình trạng này<br />
biến trong kiểm thử đơn vị gồm kiểm thử là do số lượng hàm cần kiểm thử lên tới hàng<br />
hộp đen (black-box testing) và kiểm thử hộp nghìn, thậm chí hàng chục nghìn. Kết quả là<br />
trắng (white-box testing). Kiểm thử hộp đen chi phí để kiểm thử hết những hàm này khá<br />
chỉ kiểm tra tính đúng đắn của đầu ra với đầu lớn, ảnh hưởng khá nhiều đến tốc độ phát<br />
vào cho trước mà không quan tâm đến mã triển dự án. Vì thế, quá trình kiểm thử hộp<br />
<br />
TẠP CHÍ KHOA HỌC 3<br />
QUẢN LÝ VÀ CÔNG NGHỆ<br />
trắng cần được tự động hóa để giải quyết bài các đường kiểm thử.<br />
toán về chi phí. Hiện nay, đa số quá trình thực<br />
Kỹ thuật kiểm thử tĩnh có ưu điểm là tốc<br />
hiện tự động hóa đều tập trung vào việc thực<br />
độ thực thi nhanh so với kỹ thuật kiểm thử<br />
thi ca kiểm thử (test case) mà không quan tâm<br />
động, số dữ liệu kiểm thử sinh ra ít (đặc biệt là<br />
đến việc thiết kế ca kiểm thử (việc phát hiện lỗi<br />
trong trường hợp chương trình có vòng lặp).<br />
phần mềm phụ thuộc chủ yếu vào chất lượng<br />
Tuy nhiên có hạn chế là độ phức tạp cao vì<br />
các ca kiểm thử). Hai thành phần chính trong<br />
phải phân tích toàn bộ mã nguồn, kỹ thuật này<br />
thiết kế ca kiểm thử là thiết kế dữ liệu kiểm<br />
khó áp dụng cho các dự án công nghiệp bởi<br />
thử và kết quả đầu ra mong đợi (expected<br />
vì hỗ trợ tất cả mọi cú pháp là điều không thể.<br />
output). Tuy nhiên, thiết kế các kết quả đầu ra<br />
mong đợi là khó khăn, khó tự động hóa. Do Trái ngược với kỹ thuật kiểm thử tĩnh, kỹ<br />
vậy trong thiết kế ca kiểm thử người ta quan thuật kiểm thử động không yêu cầu phải phân<br />
tâm nhiều đến sinh dữ liệu kiểm thử. tích mọi cú pháp của chương trình để sinh dữ<br />
liệu kiểm thử. Để giảm chi phí phân tích mã<br />
Cho đến nay, có hai kĩ thuật chính để<br />
nguồn mà vẫn đạt độ phủ cao, kỹ thuật kiểm<br />
sinh dữ liệu kiểm thử là kĩ thuật kiểm thử tĩnh<br />
thử động kết hợp quá trình phân tích cú pháp<br />
(static testing) và kiểm thử động (dynamic<br />
chương trình với trình biên dịch [1] [2] [3] [10].<br />
testing). Điểm chung của các kĩ thuật là sử<br />
Bởi thế, kỹ thuật kiểm thử động dễ dàng đạt<br />
dụng kĩ thuật thực thi tượng trưng (symbolic<br />
được độ phủ cao mà không cần phải phân<br />
execution) và sinh dữ liệu kiểm thử qua giải<br />
tích chương trình nhiều.<br />
hệ ràng buộc sử dụng kĩ thuật sinh ngẫu<br />
nhiên hoặc bộ giải SMT-Solver. Kĩ thuật thực Kỹ thuật kiểm thử động gồm hai kĩ thuật<br />
thi tượng trưng, nêu trong do James C. King kiểm thử được sử dụng phổ biến gồm kĩ<br />
giới thiệu lần đầu tiên vào năm 1976, sau đó thuật EGT (execution generated testing) và kĩ<br />
đã có một số cải tiến trong [5][6] và là một thuật kiểm thử tự động định hướng (concolic<br />
kĩ thuật phổ biến để sinh dữ liệu kiểm thử tự testing):<br />
động. Trong bài toán sinh dữ liệu kiểm thử,<br />
từ đầu vào là đường thi hành, kỹ thuật này sẽ Kĩ thuật EGT được áp dụng trong công cụ<br />
thay thế các giá trị đầu vào cụ thể bằng các sinh dữ liệu kiểm thử tự động nổi tiếng KLEE<br />
giá trị tượng trưng để đại diện cho một miền [2] – một công cụ được đánh giá cao bởi tính<br />
các mà hành vi chương trình là như nhau. hiệu quả của nó. Tư tưởng chính của kĩ thuật<br />
EGT là vừa chạy chương trình vừa sinh dữ<br />
Tư tưởng chính của kỹ thuật kiểm thử liệu kiểm thử trực tiếp. Chẳng hạn, khi gặp một<br />
tĩnh là sinh dữ liệu kiểm thử bằng phân tích điều kiện (điểm quyết định trên đồ thị CFG),<br />
mã nguồn (không thực thi mã nguồn) sử dữ liệu kiểm thử tương ứng nhánh đúng và<br />
dụng kĩ thuật thực thi tượng trưng. Quy trình nhánh sai của điều kiện này được sinh ra. Tại<br />
thực hiện như sau: (1) mã nguồn được phân đây, với mỗi dữ liệu kiểm thử, một tiến trình<br />
tích và chuyển thành đồ thị dòng điều khiển mới được tạo ra sẽ phân tích chương trình<br />
(control flow graph - CFG) theo tiêu chuẩn theo nhánh đúng/sai đó. Quá trình sinh dữ liệu<br />
bao phủ (coverage criteria) cho trước; (2) sinh kiểm thử chỉ dừng khi một trong ba điều kiện<br />
các đường kiểm thử (test path) bằng cách sau thỏa mãn (i) đạt độ phủ tối đa (ii) không<br />
duyệt đồ dòng điều khiển; (3) sinh ra hệ ràng còn nhánh đúng/sai nào để phân tích tiếp, (iii)<br />
buộc từ đường kiểm thử; (4) sinh dữ liệu kiểm đạt đến giới hạn thời gian cho phép. Nhược<br />
thử (ngẫu nhiên hoặc sử dụng bộ giải SMT- điểm chính của kĩ thuật EGT là hiệu suất thấp<br />
solver). Các bước (2), (3), (4) được lặp lại cho khi kiểm thử hàm chứa vòng lặp có số lần lặp<br />
đến khi đạt tiêu chí độ phủ hoặc đã duyệt hết lớn, hoặc chứa lời gọi đệ quy. Khi đó, số tiến<br />
<br />
4 TẠP CHÍ KHOA HỌC<br />
QUẢN LÝ VÀ CÔNG NGHỆ<br />
trình được tạo ra có thể từ hàng trăm tới hàng dụng sinh các dữ liệu kiểm thử kế tiếp. Nếu<br />
nghìn. Kĩ thuật này thể hiện tính hiệu quả khi không thể sinh hệ phủ định nào khác, thuật<br />
tìm các lỗi tiềm ẩn trong chương trình bởi vì toán kết thúc.<br />
EGT xem xét mọi trường hợp có thể xảy ra.<br />
Tuy nhiên, kĩ thuật EGT không phù hợp với Bước 7: Giải hệ ràng buộc thu được ở<br />
bài toán sinh dữ liệu kiểm thử đạt độ phủ tối bước 6 để sinh dữ liệu kiểm thử kế tiếp. Nếu<br />
đa bởi vì chúng ta không cần xem xét hết mọi không có dữ liệu kiểm thử nào thỏa mãn, quay<br />
trường hợp khi sinh dữ liệu kiểm thử. về bước 6 để tìm hệ ràng buộc phủ định mới<br />
sao cho khác hệ ràng buộc hiện tại. Ngược<br />
Kĩ thuật kiểm thử tự động định hướng lại, quay lại bước 3 để chạy dữ liệu kiểm thử<br />
được đề xuất vào năm 2005 và cài đặt trong kế tiếp này.<br />
công cụ DART [3]. Tư tưởng của kĩ thuật<br />
kiểm thử tự động định hướng là sinh dữ liệu II. NHỮNG HƯỚNG NGHIÊN CỨU HIỆN<br />
kiểm thử kế tiếp từ các dữ liệu kiểm thử trước NAY<br />
đó. Sau này, kĩ thuật kiểm thử tự động định 2.1. Phân tích chương trình, tiền xử lý mã<br />
hướng liên tục được cải tiến trong các công nguồn<br />
cụ PathCrawler [10], CUTE [4], CAUT [8][9],<br />
và CREST [1]. Quy trình kiểm thử tự động Trước khi thực thi chương trình để sinh dữ<br />
định hướng do Koushik Sen cùng các cộng liệu kiểm thử tự động từ mã nguồn, chương<br />
sự đề xuất DART [3] gồm các bước như sau: trình cần phải phân tích, tiền xử lý mã nguồn.<br />
Tuy nhiên, phân tích đầy đủ mã nguồn cho<br />
Bước 1: Chèn các câu lệnh đánh dấu vào<br />
một ngôn ngữ lập trình là điều rất khó khăn<br />
hàm cần kiểm thử (instrument function). Các<br />
nhất là khi ngôn ngữ lập trình thường xuyên<br />
câu lệnh đánh dấu giúp xác định được danh<br />
có sự nâng cấp thành phiên bản mới. Hiện<br />
sách câu lệnh được thực thi khi chạy chương<br />
nay, các ngôn ngữ lập trình được phân tích<br />
trình.<br />
nhiều là ngôn ngữ C/C++, Java, C#. Tuy<br />
Bước 2: Sinh ngẫu nhiên một bộ dữ liệu nhiên, việc phân tích mã nguồn chủ yếu tập<br />
kiểm thử đầu tiên dựa trên tham số truyền vào trung hỗ trợ cú pháp và các kiểu dữ liệu cơ<br />
hàm (kiểu cơ sở, con trỏ, mảng, dẫn xuất). bản, kiểu con trỏ, kiểu mảng, xử lý vòng lặp.<br />
Kỹ thuật thường được áp dụng là sử dụng thư<br />
Bước 3: Thực thi chương trình với dữ liệu viện phân tích mã nguồn, chẳng hạn Eclipse<br />
kiểm thử vừa tìm được. Nếu không thực thi CDT cho C/C++. Đầu vào của Eclipse CDT là<br />
được (lỗi xảy ra) thì quay lại bước 2 để sinh<br />
mã nguồn, đầu ra là cây cú pháp trừu tượng<br />
bộ giá trị khác.<br />
(Abstract Syntax Tree – AST) ứng với mã<br />
Bước 4: Tìm tập các câu lệnh đã được đi nguồn đó. Từ AST, người ta sẽ xây dựng đồ<br />
qua với dữ liệu kiểm thử ở bước 3 (đường thi thị CFG làm cơ sở cho việc thực thi các bước<br />
hành – test path) để xây dựng được hệ ràng tiếp theo của quá trình kiểm thử tự động.<br />
buộc tương ứng.<br />
Hiện nay đã có một số nghiên cứu quan<br />
Bước 5: Tính độ phủ đạt được với dữ liệu tâm đến giải quyết tính hướng đối tượng của<br />
kiểm thử mới nhất. Nếu độ phủ đạt được tối ngôn ngữ lập trình, chẳng hạn chương trình<br />
đa hoặc hết thời gian, quá trình sinh dữ liệu có tính đa hình động, khuôn hình lớp.<br />
kiểm thử kết thúc. Ngược lại sang bước 6<br />
Vấn đề phân tích mã nguồn cần tiếp tục<br />
Bước 6: Phủ định hệ ràng buộc thu được cải tiến để có thể hỗ trợ phân tích đầy đủ cho<br />
ở bước 4 để sinh các hệ ràng buộc mới có tác các chương trình C/C++, Java… và nhiều<br />
<br />
TẠP CHÍ KHOA HỌC 5<br />
QUẢN LÝ VÀ CÔNG NGHỆ<br />
ngôn ngữ khác. Các vấn đề còn đang được từ các câu lệnh/nhánh đã thăm tới khối lệnh<br />
nghiên cứu như vấn đề quản lý bộ nhớ, phân chưa được thăm; CAUT cố gắng tìm đường<br />
tích các chương trình có tính kế thừa, chồng thi hành tốt nhất từ câu lệnh đã được thăm<br />
toán tử, chồng hàm, khuôn hình v.v. Mặt khác, đến khối lệnh chưa được khám phá.<br />
tối ưu hóa quá trình phân tích mã nguồn là<br />
một vấn đề mở cần được nghiên cứu. Các tác giả Nguyễn Đức Anh và Phạm<br />
Ngọc Hùng đã đề xuất kĩ thuật xếp hạng đường<br />
2.2. Chiến lược tìm đường thi hành thi hành theo độ ưu tiên trong [7]. Đường thi<br />
hành tăng độ phủ càng lớn thì độ ưu tiên càng<br />
Sau khi thực thi bộ dữ liệu kiểm thử, tập<br />
cao. Mức độ tăng độ phủ được đánh giá qua<br />
hợp các câu lệnh được thực thi sẽ tạo thành<br />
trạng thái đồ thị dòng điều khiển (CFG). Trong<br />
đường thi hành (test path). Hiện tại, nhiều<br />
trường hợp hai đường thi hành cùng tăng độ<br />
công trình nghiên cứu đưa ra nhiều chiến<br />
phủ bằng nhau thì đường thi hành ngắn hơn<br />
lược chọn đường thi hành khác nhau để sinh<br />
được ưu tiên hơn. Nguyên nhân bởi vì chi phí<br />
dữ liệu kiểm thử kế tiếp càng tăng độ phủ<br />
phân tích mã nguồn khá lớn, những đường thi<br />
càng tốt như [1], [8], [10]. Theo tư tưởng của<br />
hành ngắn hơn được ưu tiên hơn các đường<br />
kĩ thuật kiểm thử tự động định hướng, bộ dữ<br />
thi hành khác để giảm chi phí phân tích mã<br />
liệu kiểm thử kế tiếp được sinh ra từ nhánh/<br />
nguồn.<br />
câu lệnh chưa được đi qua bởi các bộ dữ liệu<br />
kiểm thử trước đó. Có hai loại chiến lược tìm Ngoài các chiến lược ở trên, hai nhóm<br />
đường thi hành chính bao gồm chiến lược chiến lược sau đã được nghiên cứu và sử<br />
truyền thống và dựa trên đồ thị dòng điều dụng là nhóm chiến lược tìm kiếm heuristic<br />
khiển (CFG-based). Chiến lược truyền thống (Heuristic Search Strategy) và nhóm chiến<br />
được được Patrice Godefroid đề xuất vào lược loại bỏ dư thừa (Pruning Redundance<br />
năm 2005 và được áp dụng trong công cụ Strategy). Đây là các nghiên cứu có nhiều kết<br />
DART. Các kĩ thuật tìm kiếm trong chiến lược quả tốt và phù hợp.<br />
truyền thống gồm: tìm kiếm theo chiều sâu<br />
(DFS), tìm kiếm theo chiều rộng (BFS) và tìm 2.3. Tối ưu hóa và giải hệ ràng buộc<br />
kiếm ngẫu nhiên. Theo chiến lược này, điều Kích thước của hệ ràng buộc có thể khá<br />
kiện cuối cùng của đường thi hành mới nhất lớn, và cấu trúc khá phức tạp làm tăng thời<br />
được phủ định để sinh dữ liệu kiểm thử tiếp gian giải hệ ràng buộc. Điều đó dẫn đến bài<br />
theo mà không xét đến trạng thái của đồ thị toán tối ưu hệ ràng buộc trước khi sử dụng<br />
luồng điều khiển. Tuy nhiên, việc phủ định này SMT-Solver để giải hệ ràng buộc đó.<br />
có thể khiến quá trình sinh dữ liệu kiểm thử bị<br />
lặp vô hạn trong trường hợp hàm có vòng lặp. + Loại bỏ ràng buộc không liên quan:<br />
Sau này, các nghiên cứu trong PathCrawler<br />
Trước khi giải hệ ràng buộc cần xem xét<br />
[10] và CUTE [4] giải quyết vấn đề này bằng<br />
để loại bỏ các ràng buộc không liên quan,<br />
cách hạn chế số lần lặp tối đa của vòng lặp.<br />
nhằm tối ưu hóa hệ ràng buộc. Một vài kĩ thuật<br />
Tiếp nối với các nghiên cứu trước đó, số đơn giản để giảm độ phức tạp ràng buộc như<br />
lượng bộ dữ liệu kiểm thử được giảm thiểu hơn kĩ thuật đơn giản hóa biểu thức (ví dụ: x+0 ><br />
nữa bởi các nghiên cứu của nhóm CREST [1], 1 đơn giản hóa thành x >1), kĩ thuật suy biến<br />
nhóm CAUT [8] [9] do áp dụng chiến lược dựa nhanh giá trị biến (ví dụ: x+1=10 đơn giản hóa<br />
trên đồ thị dòng điều khiển để chọn nhánh phủ thành x=9), kĩ thuật loại bỏ hệ ràng buộc hiển<br />
định tốt nhất. Cụ thể là CREST sử dụng thuật nhiên (ví dụ: x0)^(z>0)^(y0)^(z>0)& ¬(y