Chương 1, kiểm thử phần mềm là một bước quan trọng trong quy trình phát triển phần mềm. Trong lĩnh vực kiểm thử phần mềm, các phương pháp kiểm thử thường được chia làm hai loại lớn [2]: • Kiểm thử hộp đen (black box testing): Trong phương pháp kiểm thử hộp đen, kiểm thử viên tiến hành việc xây dựng mẫu thử dựa vào đặc tả về yêu cầu chức năng của chương trình (thường được trình bày dưới dạng ngôn ngữ tự nhiên) chứ không cần dựa vào mã nguồn của chương trình. • Kiểm thử hộp trắng (white box testing): Ngược lại với kiểm thử hộp đen, trong kiểm thử hộp trắng, kiểm thử viên phải dựa vào mã nguồn của chương trình, nghĩa là dựa vào việc chương trình đã được viết như thế nào để xây dựng mẫu thử. Do kiểm thử hộp trắng phải dựa vào mã nguồn của chương trình nên thường đòi hỏi kiểm thử viên phải có kĩ năng về lập trình để có thể hiểu được chương trình đang được kiểm thử.
Điều này ngược lại với kiểm thử hộp đen do trong phương pháp này kiểm thử viên chỉ cần dựa vào đặc tả chức năng của chương trình để xây dựng bộ mẫu thử. Bên cạnh đó, do yêu cầu phải hiểu được mã nguồn chương trình nên việc kiểm thử hộp trắng thường mất nhiều thời gian và công sức hơn so với kiểm thử hộp đen (đối với cùng cấp độ kiểm thử). Điều này dẫn đến việc kiểm thử hộp trắng thường chỉ thích hợp cho giai đoạn kiểm thử đơn vị trong quy trình phát triển phần mềm. Trong khi đó phương pháp kiểm thử hộp đen có thể áp dụng cho nhiều cấp độ khác nhau, từ kiểm thử đơn vị đến kiểm thử hệ thống.
Tuy vậy, kiểm thử hộp trắng lại có ưu điểm là việc 9 Chương 2. Sinh mẫu thử tự động 10 kiểm thử được tiến hành kĩ lưỡng hơn và do đó phát hiện được nhiều lỗi hơn so với kiểm thử hộp đen. Các phương pháp kiểm thử hộp trắng lại được chia thành: • Kiểm thử dòng điều khiển (control flow testing): Là kiểm thử giải thuật chức năng của chương trình. Phương pháp này dùng để kiểm tra xem chương trình có thực thi đúng chức năng được đưa ra trong bản đặc tả chương trình hay không.
• Kiểm thử dòng dữ liệu (data flow testing): Là kiểm thử đời sống của từng biến dữ liệu được dùng trong chương trình. Phương pháp này được dùng để kiểm tra xem có lỗi trong quá trình sử dụng biến của chương trình hay không. Các lỗi thường gặp bao gồm: truy xuất biến chưa được khởi tạo, khai báo biến nhưng không sử dụng,. Do mục tiêu của đề tài này muốn khảo sát khả năng kết hợp các giải thuật sinh mẫu thử tự động với các kĩ thuật khoanh vùng lỗi và thực tế là các giải thuật sinh mẫu thử tự động tập trung nhiều vào việc kiểm thử dòng điều khiển trong kiểm thử hộp trắng nên phần tiếp theo sẽ trình bày chi tiết về nội dung này.2 Kiểm thử dòng điều khiển Trong kiểm thử dòng điều khiển có một số khái niệm như sau: • Đồ thị dòng điều khiển (control flow graph): Là một đồ thị có hướng dùng để biểu diễn trực quan cấu trúc của chương trình.
Đồ thị dòng điều khiển bao gồm tập hợp các nút, mỗi nút biểu diễn cho một thành phần và một tập hợp các cạnh nối giữa các nút với nhau, hai nút được nối với nhau nếu như trong chương trình ta có thể chuyển trực tiếp giữa hai thành phần tương ứng. • Đường thực thi (execution path): Là danh sách có thứ tự các lệnh được thi hành ứng với một lần chạy cụ thể của đơn vị phần mềm, bắt đầu từ điểm nhập đến điểm kết thúc của đơn vị phần mềm. Thường mục tiêu lý tưởng trong việc kiểm thử dòng điều khiển là có thể sinh ra bộ mẫu thử đi qua tất cả các đường thực thi của chương trình. Đáng tiếc trong thực tế, chỉ một chương trình nhỏ cũng có thể có số lượng đường thực thi rất lớn nên việc sinh ra bộ mẫu thử lý tưởng như vậy là không thể thực hiện được.
Đó là chưa kể có khả năng đường thực thi quá dài gây khó khăn cho việc kiểm thử. Sinh mẫu thử tự động 11 • Phủ kiểm thử (coverage): Do không thể sinh ra một bộ mẫu thử lý tưởng nên khái niệm phủ kiểm thử được đưa ra để đánh giá chất lượng của một bộ mẫu thử. Phủ kiểm thử là tỉ lệ các thành phần thực sự được kiểm thử so với tổng thể sau khi đã thực thi hết các mẫu thử. Phủ kiểm thử bao gồm nhiều mức độ khác nhau.
Thông thường, phủ kiểm thử càng lớn thì độ tin cậy càng cao. Các mức độ của phủ kiểm thử bao gồm: • Mức 0 : Bộ mẫu thử được tạo ra để kiểm thử những gì có thể kiểm thử được, những lỗi còn lại sẽ được phát hiện khi người dùng sử dụng chương trình và báo lại. Theo như định nghĩa thì không cần kiểm thử gì cả cũng xem như đạt được phủ kiểm thử mức 0. Vì vậy thật ra đây chỉ là mức đưa ra như một cận dưới của khái niệm phủ kiểm thử.
• Mức 1 : Bộ mẫu thử dùng trong quá trình kiểm thử phải bảo đảm sao cho mỗi câu lệnh của chương trình được thực thi ít nhất một lần. Vì vậy phủ kiểm thử mức 1 còn được gọi là phủ câu lệnh (statement coverage). • Mức 2 : Bộ mẫu thử dùng trong quá trình kiểm thử phải bảo đảm sao cho mỗi điểm quyết định luận lý trong chương trình được thực thi ít nhất một lần cho mỗi trường hợp TRUE và FALSE. Điều này tương đương với việc mỗi nhánh của chương trình đều được kiểm thử nên phủ kiểm thử mức 2 còn được gọi là phủ các nhánh (branch coverage).
Một bộ mẫu thử đạt phủ kiểm thử mức 2 thì cũng đạt phủ kiểm thử mức 1. • Mức 3 : Bộ mẫu thử dùng trong quá trình kiểm thử phải bảo đảm sao cho mỗi điều kiện con trong từng điểm quyết định luận lý trong chương trình đều được thực thi ít nhất một lần cho mỗi trường hợp TRUE và FALSE. Vì yêu cầu này nên phủ kiểm thử mức 3 còn được gọi là phủ các điều kiện con (subcondition coverage). Chú ý là phủ kiểm thử mức 3 và mức 2 không so sánh được với nhau, nghĩa là tồn tại bộ mẫu thử đạt phủ kiểm thử mức 2 nhưng không đạt phủ kiểm thử mức 3 và ngược lại.
• Mức 4 : Bộ mẫu thử dùng trong quá trình kiểm thử phải bảo đảm mỗi điều kiện con trong từng điểm quyết định luận lý trong chương trình được thực thi ít nhất một lần cho mỗi trường hợp TRUE và FALSE và bản thân mỗi điểm quyết định luận lý cũng được thực hiện ít nhất một lần cho mỗi trường hợp TRUE và FALSE. Phủ kiểm thử mức 4 còn được gọi là phủ các nhánh và các điều kiện con (branch and subcondition coverage). Tất nhiên một bộ mẫu thử đạt phủ kiểm thử mức 4 thì cũng đạt phủ kiểm thử mức 2 và mức 3. Sinh mẫu thử tự động 12 Ví dụ 2.
Xét một chương trình như sau (để đơn giản, giả sử chương trình không có short circuit): 1: bool foo(int a, int b) 2: { 3: bool ret = false; 4: if (a > b) { 5: a = a - b; 6: } 7: if (a > 0 && b > 0) { 8: ret = true; 9: } 10: return ret; 11: } Bảng sau tóm tắt lại mức phủ kiểm thử của các bộ mẫu thử khác nhau đối với chương trình trên: Mức phủ kiểm thử Bộ mẫu thử Mức 0 Không có Mức 1 (2, 1) Mức 2 (1, 0); (1, 1) Mức 3 (1, 0); (0, 1) Mức 4 (1, 0); (0, 1); (1, 1) 2.3 Sinh mẫu thử bằng phương pháp tìm kiếm Các kĩ thuật sinh mẫu thử tự động thường hỗ trợ cho việc kiểm thử dòng điều khiển trong kiểm thử hộp trắng. Trong số các kĩ thuật đó, các kĩ thuật dựa trên phương pháp tìm kiếm thường được áp dụng rộng rãi nhất. Để có thể áp dụng phương pháp tìm kiếm vào việc sinh mẫu thử tự động, trước hết cần đáp ứng hai yêu cầu: • Thiết kế không gian tìm kiếm (search space) bao gồm các giải pháp cho vấn đề cần giải quyết. Không gian tìm kiếm phải được thiết kế sao cho việc chuyển từ giải pháp này sang giải pháp khác có thể thực hiện được một cách dễ dàng và hợp lí.
Trong bài toán sinh mẫu thử tự động, không gian tìm kiếm chính là tập hợp tất cả các mẫu thử có thể sinh ra và giải pháp ở đây chính là từng mẫu thử đơn lẻ. Sinh mẫu thử tự động 13 • Phải có một hàm lượng giá (objective function) để so sánh độ tốt của giải pháp này với giải pháp khác trong quá trình tìm kiếm. Thông thường, hàm lượng giá sẽ nhận đầu vào là giải pháp cần lượng giá và trả về kết quả là một con số phản ánh độ tốt của giải pháp ứng với bài toán đang được xét đến. Nguyên tắc của việc dùng kĩ thuật tìm kiếm để sinh mẫu thử tự động được thực hiện qua các bước như sau [8]: • Bước 1 : Xây dựng đồ thị dòng điều khiển của chương trình.
Dựa vào đồ thị dòng điều khiển vừa được xây dựng, ta có thể liệt kê tất cả đường thực thi của chương trình. • Bước 2 : Chọn trên đồ thị này một đường thực thi theo tiêu chí độ bao phủ được đưa ra. • Bước 3 : Tìm kiếm trong không gian các mẫu thử để chọn ra mẫu thử phù hợp với đường thực thi được chọn. Để đánh giá mức độ phù hợp của mẫu thử đang xét đối với đường thực thi được chọn, ta cần sử dụng hàm lượng giá.
Ở đây, hàm lượng giá sẽ được xây dựng dựa trên việc mẫu thử được xét có tạo ra được đường thực thi này hay không và nếu có sai lệch thì sự sai lệch là bao nhiêu. • Bước 4 : Tiếp tục quay lại bước 2 và chọn một đường thực thi khác cho đến khi có được bộ mẫu thử thỏa mãn tiêu chí độ bao phủ được đề ra.4 Các kỹ thuật tìm kiếm Khâu quan trọng trong kĩ thuật sinh mẫu thử tự động là tìm kiếm trong không gian mẫu thử để chọn ra mẫu thử phù hợp. Các kĩ thuật tìm kiếm mẫu thử trong không gian mẫu thử được khảo sát trong luận văn này bao gồm [9]: • Tìm kiếm ngẫu nhiên (random search). • Tìm kiếm bằng giải thuật leo đồi đơn giản (simple hill climbing search).
• Tìm kiếm bằng giải thuật leo đồi dốc nhất (steepest hill climbing search). • Tìm kiếm bằng giải thuật tôi luyện mô phỏng (simulated annealing search).
