Luận văn thạc sĩ: Tối ưu hóa kiểm thử phần mềm qua sinh mẫu và khoanh vùng lỗi

Luận văn thạc sĩ nghiên cứu máy tính kết hợp các phương pháp sinh mẫu thử tự động và khoanh vùng lỗi để tăng hiệu quả trong quá, khảo sát thực trạng, phân tích nguyên nhân, đề

• Tác giả: Phạm Hồng Long
• Người hướng dẫn: PGS. Quản Thành Thơ
• Trường học: Đại học Quốc gia TP. HCM
• Chuyên ngành: Khoa học máy tính
• Đề tài: Kết hợp Các Phương Pháp Sinh Mẫu Thử Tự Động Và Khoanh Vùng Lỗi Trong Kiểm Thử Phần Mềm
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2014
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• Lời cảm ơn
• Tóm tắt
• Abstract
• Lời cam đoan
• Danh mục hình
• Danh mục bảng
• 1. Chương 1: Giới thiệu
• 1.1. Tổng quan vấn đề
• 1.2. Mục tiêu của đề tài
• 1.3. Giới hạn của đề tài
• 1.4. Đóng góp của đề tài
• 1.5. Công việc liên quan
• 1.6. Cấu trúc luận văn
• 2. Chương 2: Sinh mẫu thử tự động
• 2.1. Kiểm thử hộp đen và kiểm thử hộp trắng
• 2.2. Kiểm thử dòng điều khiển
• 2.3. Sinh mẫu thử bằng phương pháp tìm kiếm
• 2.4. Các kỹ thuật tìm kiếm
• 2.4.1. Tìm kiếm ngẫu nhiên
• 2.4.2. Tìm kiếm bằng giải thuật leo đồi đơn giản
• 2.4.3. Tìm kiếm bằng giải thuật leo đồi dốc nhất
• 2.4.4. Tìm kiếm bằng giải thuật tôi luyện mô phỏng
• 2.4.5. Tìm kiếm bằng giải thuật di truyền
• 2.5. Sinh mẫu thử bằng phương pháp giải ràng buộc
• 3. Chương 3: Khoanh vùng lỗi
• 3.1. Khoanh vùng lỗi dựa trên mô hình
• 3.2. Khoanh vùng lỗi dựa trên chứng minh
• 3.3. Khoanh vùng lỗi dựa trên phổ
• 4. Chương 4: Phương pháp tiến hành
• 4.1. Mô hình hiện thực
• 4.2. Một số chi tiết hiện thực
• 5. Chương 5: Kết quả thí nghiệm
• 5.1. Chương trình thí nghiệm
• 5.2. Kết quả thí nghiệm
• 5.2.1. Tính trị tuyệt đối
• 5.2.2. Kiểm tra bằng 0
• 5.2.3. Kiểm tra tính chẵn lẻ
• 5.2.4. Kiểm tra số nguyên tố
• 5.2.5. Tính giai thừa
• 5.2.6. Tính tổng các số chẵn
• 5.2.7. Tìm số lớn hơn
• 5.2.8. Kiểm tra hai số bằng nhau
• 5.2.9. Tính số nghiệm của phương trình bậc hai
• 5.2.10. Kiểm tra tam giác đều
• 5.3. Nhận xét tổng hợp
• 6. Chương 6: Trang web hỗ trợ học lập trình
• 6.1. Động lực phát triển
• 6.2. Mô hình của trang web
• 6.3. Hoạt động của trang web
• 7. Chương 7: Kết luận và hướng phát triển
• 7.1. Kết luận
• 7.2. Công việc tương lai
• 7.2.1. Khoanh vùng lỗi thích ứng
• 7.2.2. Tăng khả năng tương tác của trang web
• Tài liệu tham khảo

Tóm tắt

I. Tổng quan về kiểm thử phần mềm

Phần mềm đóng vai trò thiết yếu trong nhiều lĩnh vực, từ kinh tế đến giáo dục. Do đó, việc đảm bảo chất lượng phần mềm là vô cùng quan trọng. Kiểm thử phần mềm (kiểm thử phần mềm) được thực hiện để phát hiện lỗi và đảm bảo phần mềm hoạt động đúng theo yêu cầu. Quy trình này thường bao gồm nhiều giai đoạn như kiểm thử đơn vị, kiểm thử tích hợp, và kiểm thử hệ thống. Tuy nhiên, kiểm thử thủ công thường tốn nhiều thời gian và công sức. Do đó, việc áp dụng các phương pháp tự động hóa trong kiểm thử phần mềm trở nên cần thiết. Việc sử dụng các phương pháp sinh mẫu thử tự động giúp giảm thiểu thời gian và công sức cho quy trình này.

1.1. Quy trình kiểm thử phần mềm

Quy trình kiểm thử phần mềm truyền thống yêu cầu nhân viên kiểm thử tạo ra các mẫu thử. Mỗi mẫu thử bao gồm dữ liệu đầu vào và giá trị đầu ra mong đợi. Nếu giá trị đầu ra không khớp với mong đợi, lỗi được xác định. Tuy nhiên, việc này đòi hỏi một bộ mẫu thử lớn và phức tạp, dẫn đến việc kiểm thử phần mềm chiếm hơn 50% thời gian phát triển phần mềm. Để tối ưu hóa quy trình kiểm thử, nhiều nghiên cứu đã được thực hiện nhằm phát triển các hệ thống tự động hóa sinh mẫu thử, giúp giảm thiểu khối lượng công việc cho nhân viên kiểm thử.

II. Phương pháp sinh mẫu thử tự động

Các phương pháp sinh mẫu thử tự động là một trong những giải pháp quan trọng để nâng cao hiệu quả kiểm thử phần mềm. Những phương pháp này sử dụng các thuật toán để tự động tạo ra các mẫu thử dựa trên đặc tả chức năng hoặc cấu trúc của phần mềm. Các kỹ thuật như tìm kiếm ngẫu nhiên, tìm kiếm bằng giải thuật di truyền hay giải thuật leo đồi được áp dụng để tối ưu hóa quá trình sinh mẫu. Việc sinh mẫu thử tự động không chỉ giúp tiết kiệm thời gian mà còn đảm bảo rằng các mẫu thử được tạo ra là đa dạng và có khả năng phát hiện lỗi cao.

2.1. Kỹ thuật tìm kiếm trong sinh mẫu

Các kỹ thuật tìm kiếm trong sinh mẫu thử tự động bao gồm tìm kiếm ngẫu nhiên, tìm kiếm bằng giải thuật leo đồi đơn giản và tìm kiếm bằng giải thuật di truyền. Mỗi kỹ thuật có những ưu nhược điểm riêng, nhưng đều hướng đến mục tiêu tạo ra các mẫu thử có độ bao phủ cao và khả năng phát hiện lỗi tốt. Việc áp dụng các kỹ thuật này giúp tối ưu hóa quy trình kiểm thử, giảm thiểu thời gian và tăng cường hiệu quả phát hiện lỗi trong phần mềm.

III. Khoanh vùng lỗi trong phần mềm

Khoanh vùng lỗi là một kỹ thuật quan trọng trong quy trình phát hiện và sửa lỗi phần mềm. Kỹ thuật này dựa trên thông tin thu thập được trong quá trình thực thi các mẫu thử để xác định vị trí lỗi trong mã nguồn. Các phương pháp khoanh vùng lỗi như khoanh vùng dựa trên mô hình, chứng minh và phổ được áp dụng để đưa ra đánh giá về khả năng gây ra lỗi của từng thành phần trong chương trình. Việc áp dụng các kỹ thuật khoanh vùng lỗi giúp lập trình viên nhanh chóng xác định và sửa chữa lỗi, từ đó nâng cao chất lượng phần mềm.

3.1. Kỹ thuật khoanh vùng lỗi

Các kỹ thuật khoanh vùng lỗi dựa trên mô hình và chứng minh giúp lập trình viên xác định vị trí lỗi chính xác hơn. Thông qua việc phân tích kết quả thực thi, các kỹ thuật này có thể đưa ra danh sách các thành phần khả nghi, từ đó giúp lập trình viên tập trung vào những phần cần kiểm tra kỹ lưỡng hơn. Kỹ thuật khoanh vùng lỗi không chỉ hỗ trợ trong việc phát hiện lỗi mà còn giúp cải thiện quy trình phát triển phần mềm tổng thể.

IV. Kết hợp giữa sinh mẫu thử tự động và khoanh vùng lỗi

Việc kết hợp giữa phương pháp sinh mẫu thử tự động và khoanh vùng lỗi là một bước tiến quan trọng trong việc tối ưu hóa quy trình kiểm thử phần mềm. Nghiên cứu cho thấy rằng mẫu thử được sinh ra tự động có thể hỗ trợ tốt cho các phương pháp khoanh vùng lỗi, giúp xác định lỗi nhanh chóng và hiệu quả hơn. Điều này không chỉ nâng cao hiệu quả kiểm thử mà còn giảm thiểu thời gian và công sức cần thiết cho việc sửa lỗi. Việc tạo ra cầu nối giữa hai lĩnh vực này sẽ mở ra nhiều cơ hội mới cho nghiên cứu và ứng dụng trong ngành công nghiệp phần mềm.

4.1. Đánh giá và ứng dụng thực tiễn

Đánh giá khả năng kết hợp giữa sinh mẫu thử tự động và khoanh vùng lỗi cho thấy sự cải thiện rõ rệt trong quy trình phát hiện lỗi. Các phương pháp khoanh vùng lỗi có thể sử dụng các mẫu thử tự động để tăng cường độ chính xác trong việc xác định lỗi. Ứng dụng thực tiễn của nghiên cứu này không chỉ giúp các lập trình viên trong việc sửa lỗi mà còn tạo ra một công cụ hỗ trợ học lập trình hiệu quả cho sinh viên, giúp họ rèn luyện kỹ năng lập trình một cách độc lập.

Nội dung chính

Tổng quan nghiên cứu

Trong kỹ nghệ phần mềm hiện đại, quy trình kiểm thử phần mềm chiếm hơn 50% tổng thời gian và chi phí phát triển hệ thống. Khi một hệ thống gặp sự cố, việc truy vết thủ công nhằm định vị chính xác vị trí câu lệnh bị lỗi đòi hỏi nguồn lực kỹ thuật rất lớn và dễ phát sinh sai sót. Trước bối cảnh đó, hai hướng nghiên cứu trọng điểm đã được hình thành độc lập: sinh mẫu thử tự động và khoanh vùng lỗi dựa trên phổ thực thi. Tuy nhiên, phần lớn các công trình trước đây đều phát triển biệt lập hai mảng này mà chưa đánh giá toàn diện tính tương thích giữa bộ dữ liệu thử nghiệm tự sinh và các mô hình chẩn đoán lỗi.

Luận văn thạc sĩ chuyên ngành Khoa học máy tính của tác giả Phạm Hồng Long, dưới sự hướng dẫn khoa học của Phó Giáo sư Tiến sĩ Quản Thành Thơ tại Trường Đại học Bách Khoa – Đại học Quốc gia Thành phố Hồ Chí Minh (hoàn thành tháng 6 năm 2014), đã tiên phong giải quyết bài toán giao thoa này. Đề tài tập trung thiết lập một khung đánh giá thực nghiệm toàn diện trên 10 chương trình chuẩn với 34 phiên bản lỗi nhân tạo, khảo sát 5 thuật toán sinh mẫu thử và 3 mô hình khoanh vùng lỗi phổ biến. Mục tiêu cốt lõi là chứng minh các bộ mẫu thử đạt độ bao phủ cấu trúc mức cao do máy tính tự sinh có khả năng giúp lập trình viên rút ngắn từ 60% đến 80% số lượng câu lệnh cần phải rà soát, đồng thời tích hợp trực tiếp kết quả vào hệ sinh thái giáo dục trực tuyến nhằm hỗ trợ sinh viên tự động chẩn đoán lỗi lập trình.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu vận dụng lý thuyết kiểm thử dòng điều khiển hộp trắng với 4 cấp độ bao phủ chặt chẽ, trong đó cấp độ 4 (bao phủ toàn bộ các nhánh và điều kiện con) được chọn làm tiêu chuẩn ràng buộc tối đa cho bộ mẫu thử. Không gian tìm kiếm mẫu thử được tối ưu hóa dựa trên kỹ nghệ phần mềm tìm kiếm với 5 giải thuật tiêu biểu: tìm kiếm ngẫu nhiên, leo đồi đơn giản, leo đồi dốc nhất, tôi luyện mô phỏng và giải thuật di truyền.

Về phương diện chẩn đoán sai hỏng, tác giả áp dụng lý thuyết khoanh vùng lỗi dựa trên phổ thực thi. Các thuật toán chính gồm Tarantula, Ochiai và Jaccard. Mỗi thuật toán tính toán một điểm số nghi ngờ từ 0 đến 1 cho từng dòng lệnh dựa trên tần suất xuất hiện của câu lệnh đó trong các ca kiểm thử thành công và thất bại. Điểm nghi ngờ càng tiệm cận 1 thì xác suất dòng lệnh đó chứa lỗi càng cao.

Phương pháp nghiên cứu

Nghiên cứu triển khai phương pháp thực nghiệm định lượng trên tập dữ liệu gồm 10 chương trình thuật toán viết bằng cú pháp C/C++, bao gồm 34 phiên bản được cố ý chèn lỗi đơn vào các phép toán luận lý, điều kiện rẽ nhánh và khối lệnh gán. Không gian giá trị đầu vào cho mỗi biến nguyên được giới hạn chặt chẽ trong khoảng từ -128 đến 127.

Phương pháp chọn mẫu sử dụng cơ chế sinh tự động có kiểm soát với tối đa 10 lần tìm kiếm cho mỗi đường thực thi nhằm đảm bảo tính bao phủ mức 4. Để loại bỏ các sai số ngẫu nhiên, hệ thống tạo ra 500 bộ mẫu thử cho mỗi chương trình (tương ứng 100 bộ cho mỗi thuật toán tìm kiếm). Sau đó, phương pháp thống kê cắt tỉa 5% giá trị cao nhất và 5% giá trị thấp nhất được áp dụng, tính toán kết quả trung bình trên 90 bộ mẫu thử đại diện. Thước đo đánh giá hiệu năng chính là thời gian thực thi (mili giây) và số lượng thành phần mã nguồn mà kỹ sư cần rà soát trước khi tìm ra vị trí lỗi thực sự.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Thực nghiệm trên môi trường máy tính trang bị vi xử lý Intel Core i3 xung nhịp 2.10GHz và bộ nhớ RAM 2GB đã ghi nhận nhiều kết quả vượt trội:

Thứ nhất, hai công thức Ochiai và Jaccard thể hiện sự vượt trội vượt bậc so với Tarantula trong hầu hết các ca kiểm thử. Cụ thể, tại các bài toán logic như tính trị tuyệt đối (phiên bản 1), kiểm tra số 0 (phiên bản 1) và kiểm tra tính chẵn lẻ (phiên bản 1), Ochiai và Jaccard chỉ yêu cầu lập trình viên rà soát đúng 1 câu lệnh nghi ngờ duy nhất để phát hiện lỗi, trong khi Tarantula yêu cầu kiểm tra đến 3 câu lệnh (hiệu quả định vị của Ochiai cao gấp 300%).

Thứ hai, thời gian sinh mẫu thử tự động diễn ra cực kỳ tối ưu. Với hầu hết các chương trình đơn, thời gian sinh trung bình của thuật toán di truyền và tôi luyện mô phỏng dao động từ 0 đến 3 mili giây.

Thứ ba, sự kết hợp giữa kỹ thuật bao phủ nhánh mức 4 và giải thuật di truyền giúp giảm thiểu tỷ lệ nhận diện sai vị trí lỗi xuống dưới 10%, tạo ra các bộ dữ liệu kiểm thử cân bằng giữa số lượng ca chạy đúng và ca chạy sai.

Thảo luận kết quả

Hiệu năng vượt trội của Ochiai và Jaccard bắt nguồn từ việc công thức toán học của hai mô hình này phạt rất nặng các câu lệnh chỉ xuất hiện trong các ca chạy thành công, từ đó cô lập các nhánh sai lệch hiệu quả hơn Tarantula.

Các dữ liệu thực nghiệm được trình bày rõ ràng qua bảng đối sánh thứ hạng nghi ngờ và đồ thị phân bổ thời gian sinh mẫu. Kết quả này bổ sung và củng cố vững chắc cho các công trình quốc tế trước đây, tiêu biểu như nghiên cứu của Baudry năm 2006 về khái niệm khối cơ bản động và công trình của Shay Artzi năm 2010 về kỹ thuật thực thi kết hợp trên nền tảng PHP. Việc kết hợp đa giải thuật tìm kiếm với phổ thực thi đã chứng minh rằng các bộ dữ liệu kiểm thử tự động hoàn toàn đủ tiêu chuẩn phục vụ cho các công cụ tự động khoanh vùng lỗi mà không làm suy giảm độ chính xác chẩn đoán.

Đề xuất và khuyến nghị

Nhằm tối ưu hóa quy trình kiểm thử và nâng cao năng suất kỹ thuật phần mềm, các giải pháp cụ thể được đề xuất gồm:

1. Tích hợp mô hình Ochiai và giải thuật di truyền vào quy trình tích hợp liên tục (CI/CD): Các doanh nghiệp công nghệ nên triển khai bộ công cụ này để tự động tạo mẫu thử và cảnh báo vị trí lỗi, hướng tới mục tiêu giảm 70% thời gian gỡ lỗi thủ công của lập trình viên trong khung thời gian 6 tháng áp dụng.
2. Triển khai hệ thống tự động chẩn đoán mã nguồn trong giáo dục đại học: Đưa module khoanh vùng lỗi vào các cổng chấm bài trực tuyến cho sinh viên ngành Công nghệ thông tin trong vòng 3 đến 6 tháng, giúp hơn 1.000 sinh viên mỗi học kỳ tự nhận diện phản ví dụ và sửa lỗi lập trình mà không cần phụ thuộc hoàn toàn vào trợ giảng.
3. Chuẩn hóa kiểm thử đạt độ bao phủ mức 4 trong các dự án phần mềm quan trọng: Khuyến nghị các tổ chức phát triển phần mềm ngân hàng và y tế áp dụng quy chuẩn kiểm thử bao phủ toàn bộ điều kiện con trước khi phát hành sản phẩm, nhằm bảo đảm dữ liệu đầu vào cho các thuật toán chẩn đoán đạt độ tin cậy trên 95%.
4. Mở rộng kết hợp bộ giải ràng buộc với tìm kiếm kinh nghiệm: Trong giai đoạn 12 tháng tới, các nhóm nghiên cứu nên tích hợp các bộ giải ràng buộc như Z3 hoặc Redlog với thuật toán tôi luyện mô phỏng để sinh mẫu thử cho các hàm phần mềm doanh nghiệp phức tạp có quy mô trên 1.000 dòng mã.

Đối tượng nên tham khảo luận văn

Tài liệu nghiên cứu này mang lại giá trị học thuật và ứng dụng thực tiễn cao cho 4 nhóm đối tượng chính:

1. Kỹ sư kiểm thử tự động và đảm bảo chất lượng phần mềm (QA/QC/SDET): Sử dụng các công thức Ochiai, Jaccard và phương pháp bao phủ mức 4 để tối ưu hóa bộ kịch bản kiểm thử tự động, rút ngắn thời gian phân tích nguyên nhân gốc rễ của lỗi hệ thống.
2. Lập trình viên và kỹ sư phát triển phần mềm: Nắm vững cơ chế sinh phản ví dụ và luồng thực thi để tự động hóa việc gỡ lỗi trong giai đoạn kiểm thử đơn vị, nâng cao năng suất viết mã sạch.
3. Giảng viên và nghiên cứu sinh chuyên ngành Khoa học máy tính: Khai thác phương pháp luận kết hợp giữa Search-Based Software Engineering và chẩn đoán lỗi dựa trên phổ để mở rộng các đề tài nghiên cứu chuyên sâu về phân tích chương trình tĩnh và động.
4. Các công ty công nghệ giáo dục (EdTech): Tham khảo kiến trúc trang web hỗ trợ học lập trình được xây dựng trong luận văn để thiết kế các tính năng chấm điểm và phản hồi lỗi thông minh cho học viên.

Câu hỏi thường gặp

Tại sao cần kết hợp sinh mẫu thử tự động với các phương pháp khoanh vùng lỗi?
Trước đây, các thuật toán khoanh vùng lỗi luôn mặc định có sẵn một bộ kiểm thử chuẩn, trong khi các công cụ sinh mẫu thử lại chỉ tập trung vào độ bao phủ mã nguồn. Việc kết hợp giúp tự động hóa khép kín quy trình từ khâu tạo dữ liệu đầu vào đến khâu chỉ điểm vị trí dòng mã lỗi, giúp tiết kiệm hơn 50% thời gian bảo trì phần mềm.

Giữa Tarantula, Ochiai và Jaccard, công thức nào mang lại độ chính xác cao nhất?
Thực nghiệm trên 34 phiên bản lỗi cho thấy Ochiai và Jaccard đạt độ chính xác vượt trội nhất. Trong đa số các trường hợp như kiểm tra tính chẵn lẻ hay tìm số lớn hơn, hai phương pháp này chỉ yêu cầu lập trình viên kiểm tra 1 thành phần nghi ngờ duy nhất để định vị chính xác lỗi, trong khi Tarantula cần kiểm tra từ 2 đến 3 thành phần.

Độ bao phủ kiểm thử mức 4 có vai trò như thế nào trong việc tìm lỗi?
Bao phủ mức 4 yêu cầu kiểm tra mọi nhánh rẽ và từng điều kiện con của biểu thức logic. Tiêu chuẩn này đảm bảo các mẫu thử kích hoạt toàn bộ các trạng thái tiềm ẩn của chương trình, cung cấp ma trận thực thi đa dạng giúp các công thức phổ toán học phân biệt chính xác dòng lệnh lỗi với dòng lệnh bình thường.

Giải thuật tìm kiếm nào tối ưu nhất cho việc sinh mẫu thử tự động trong nghiên cứu?
Giải thuật di truyền và tôi luyện mô phỏng thể hiện khả năng vượt qua các điểm tối ưu cục bộ tốt nhất khi giải quyết các hàm có nhiều nhánh lặp. Thời gian thực thi trung bình chỉ mất từ 0 đến 3 mili giây trên các module hàm chuẩn, đảm bảo tốc độ sinh mẫu thử nhanh và chuẩn xác.

Nghiên cứu này đã được ứng dụng vào sản phẩm thực tiễn nào chưa?
Mô hình khoanh vùng lỗi của luận văn đã được tích hợp thành công vào nền tảng học lập trình trực tuyến của nhóm nghiên cứu SAVE tại Trường Đại học Bách Khoa Thành phố Hồ Chí Minh, đồng thời công bố tại 2 bài báo khoa học quốc tế uy tín trong hội nghị IETEC 2013 và tạp chí IJQAETE 2014.

Kết luận

• Luận văn đã thiết lập thành công cầu nối thực nghiệm giữa hai lĩnh vực sinh mẫu thử tự động và khoanh vùng lỗi dựa trên phổ thực thi.
• Khảo sát toàn diện 5 giải thuật tìm kiếm mẫu thử kết hợp với 3 mô hình định vị lỗi trên 34 phiên bản phần mềm có lỗi đơn.
• Chứng minh công thức Ochiai và Jaccard kết hợp độ bao phủ nhánh mức 4 giúp giảm thiểu số câu lệnh cần kiểm tra xuống chỉ còn 1 câu lệnh trong phần lớn các trường hợp.
• Đóng góp 2 công trình khoa học quốc tế tại hội nghị IETEC 2013 và tạp chí chuyên ngành IJQAETE 2014, đồng thời thương mại hóa ý tưởng vào nền tảng hỗ trợ sinh viên học lập trình tự động.
• Mở rộng lộ trình nghiên cứu trong 12 tháng tới hướng đến xử lý lỗi đa điểm và ứng dụng bộ giải ràng buộc Z3 cho các hệ thống phần mềm doanh nghiệp quy mô lớn.

Bạn đọc và các nhóm nghiên cứu quan tâm có thể khai thác toàn văn tài liệu luận văn để ứng dụng khung thử nghiệm tự động vào các dự án kiểm thử phần mềm thực tế ngay hôm nay.

Trích đoạn nội dung tài liệu

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).