Tổng quan về phương pháp sinh dữ liệu kiểm thử tự động từ mã nguồn

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