intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

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

Chia sẻ: ViDeshiki2711 ViDeshiki2711 | Ngày: | Loại File: PDF | Số trang:9

71
lượt xem
1
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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 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í của dự án và 35% tổng thời gian phát triển phần mềm. Bài viết này tóm tắt các kỹ thuật chính trong việc sinh dữ liệu kiểm thử tự động từ mã nguồn và một số hướng nghiên cứu cải tiến.

Chủ đề:
Lưu

Nội dung Text: 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
10=>1