Tài liệu Phương pháp phân tích mã nguồn và sinh dữ liệu kiểm thử cho các dự án c c++

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Đức Anh PHƯƠNG PHÁP PHÂN TÍCH MÃ NGUỒN VÀ SINH DỮ LIỆU KIỂM THỬ CHO CÁC DỰ ÁN C/C++ LUẬN VĂN THẠC SĨ: KỸ THUẬT PHẦN MỀM HÀ NỘI – 2017 I ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Đức Anh PHƯƠNG PHÁP PHÂN TÍCH MÃ NGUỒN VÀ SINH DỮ LIỆU KIỂM THỬ CHO CÁC DỰ ÁN C/C++ Ngành: Công nghệ thông tin Chuyên ngành: Kỹ thuật phần mềm Mã số: 60480103 LUẬN VĂN THẠC SĨ: KỸ THUẬT PHẦN MỀM Cán bộ hướng dẫn: PGS. TS. Phạm Ngọc Hùng HÀ NỘI - 2017 II LỜI CẢM ƠN Đầu tiên, tôi xin gửi lời cám ơn chân thành tới Tiến sĩ Phạm Ngọc Hùng – giảng viên bộ môn Công Nghệ Phần Mềm – người đã hướng dẫn tận tình, tỉ mỉ, chu đáo tôi trong suốt hai năm làm luận văn. Quãng thời gian được thầy hướng dẫn đã giúp tôi học hỏi, đúc kết được nhiều kinh nghiệm về phương pháp nghiên cứu, kĩ năng giao tiếp, kĩ năng làm việc nhóm, kĩ năng trình bày. Thầy còn truyền cho tôi ngọn lửa yêu nghiên cứu khoa học, niềm tin vượt qua những khó khăn trong cuộc sống và dạy tôi cách vượt qua những khó khăn đó. Tôi cảm thấy tự hào và may mắn khi là một học viên được thầy hướng dẫn trong những năm tháng cao học. Ngoài ra, tôi xin gửi lời cám ơn chân thành đến nhóm nghiên cứu đã giúp đỡ tôi nhiệt tình để hoàn thành luận văn sao cho đạt hiệu quả cao nhất. Cám ơn nhóm nghiên cứu đã giúp đỡ tôi bằng hành động, bằng lời nói mỗi khi tôi gặp khó khăn, thất bại. Hai năm bên nhau không phải là dài nhưng đối với tôi, đây là quãng thời gian tuyệt vời nhất và không thể nào quên. Tiếp theo, tôi xin gửi lời cảm ơn đến các thầy cô giảng viên Trường Đại học Công Nghệ - Đại học Quốc Gia Hà Nội – những người đã tận tâm truyền đạt những kiến thức quý báu làm nền tảng để tôi tiếp tục đi xa hơn nữa trong lĩnh vực công nghệ thông tin. Cuối cùng, tôi xin được cảm ơn gia đình đã nuôi tôi khôn lớn để trở thành người có ích cho xã hội, giúp tôi có một điểm tựa vững chắc để yên tâm học hành trong suốt bao năm qua. Tôi xin gửi lời cám ơn chân thành tới cha, mẹ, em gái đã luôn động viên và cổ vũ tôi mỗi khi tôi gặp khó khăn và thử thách. Hà Nội, ngày 25 tháng 11 năm 2017 Học viên Nguyễn Đức Anh III LỜI CAM ĐOAN Tôi xin cam đoan rằng những nghiên cứu về kiểm thử tự động cho chương trình C/C++ được trình bày trong luận văn này là của tôi và chưa từng được nộp như một báo cáo luận văn tại trường Đại học Công Nghệ - Đại học Quốc Gia Hà Nội hoặc bất kỳ trường đại học khác. Những gì tôi viết ra không sao chép từ các tài liệu, không sử dụng các kết quả của người khác mà không trích dẫn cụ thể. Tôi xin cam đoan công cụ kiểm thử tự động tôi trình bày trong khoá luận là do tôi tự phát triển, không sao chép mã nguồn của người khác. Nếu sai tôi hoàn toàn chịu trách nhiệm theo quy định của trường Đại học Công Nghệ - Đại học Quốc Gia Hà Nội. Hà Nội, ngày 25 tháng 11 năm 2017 Học viên Nguyễn Đức Anh IV MỤC LỤC Giới thiệu ............................................................................................... 1 Tổng quan kĩ thuật kiểm thử tự động định hướng ........................... 5 2.1. Dữ liệu kiểm thử ........................................................................................ 5 2.2. Các tiêu chí độ phủ sử dụng trong kĩ thuật kiểm thử tự động định hướng 5 2.3. Đồ thị dòng điều khiển .............................................................................. 6 2.4. Cây cú pháp trừu tượng ............................................................................. 7 2.5. Quy trình chung kĩ thuật kiểm thử tự động định hướng ............................ 7 Phương pháp kiểm thử tự động dự án C/C++ sử dụng kĨ thuật kiểm thử tự động định hướng .......................................................................................... 9 3.1. Tổng quan phương pháp đề xuất ............................................................... 9 3.2. Pha tiền xử lý mã nguồn .......................................................................... 10 3.2.1. Xây dựng cây cấu trúc từ dự án C/C++ ................................................... 10 3.2.2. Chèn các câu lệnh đánh dấu vào hàm ...................................................... 13 3.3. Pha sinh dữ liệu kiểm thử ........................................................................ 14 3.3.1. Xây dựng đồ thị dòng điều khiển từ mã nguồn ....................................... 16 3.3.2. Xếp hạng đường thi hành ......................................................................... 18 3.3.3. Xây dựng hệ ràng buộc từ đường thi hành .............................................. 19 a. Mô hình bộ nhớ sử dụng trong kĩ thuật thực thi tượng trưng ............... 20 b. Xây dựng hệ ràng buộc từ đường thi hành sử dụng kĩ thuật thực thi tượng trưng .............................................................................................................. 22 3.3.4. Giải hệ ràng buộc sử dụng bộ giải SMT-Solver ...................................... 24 3.4. Biên dịch và thực thi dữ liệu kiểm thử trong môi trường chạy ............... 26 3.5. Tối ưu hóa pha sinh dữ liệu kiểm thử ...................................................... 27 3.5.1. Đơn giản hóa hệ ràng buộc ...................................................................... 27 V 3.5.2. Tăng tốc thời gian biên dịch và thực thi dữ liệu kiểm thử....................... 28 3.6. Xuất mã nguồn kiểm thử theo chuẩn Google Test .................................. 29 Công cụ và thực nghiệm .................................................................... 30 4.1. Giới thiệu công cụ kiểm thử tự động CFT4Cpp ...................................... 30 4.2. Thư viện hỗ trợ sử dụng trong công cụ kiểm thử tự động CFT4Cpp...... 33 4.2.1. Thư viện giải hệ ràng buộc Z3 ................................................................. 33 4.2.2. Thư viện phân tích mã nguồn CDT ......................................................... 34 4.2.3. Thư viện tính giá trị biểu thức Jeval ........................................................ 35 4.3. Kết quả thực nghiệm ................................................................................ 35 4.3.1. So sánh số lượng bộ dữ liệu kiểm thử và độ phủ với KLEE, CAUT, CREST, PathCrawler ......................................................................................... 35 4.3.2. Sinh dữ liệu kiểm thử vòng lặp ................................................................ 40 4.3.3. So sánh thời gian biên dịch và thực thi dữ liệu kiểm thử ........................ 42 Kết luận ............................................................................................... 44 Tài liệu tham khảo................................................................................................. 48 VI DANH SÁCH KÝ HIỆU, CHỮ VIẾT TẮT Tên đầy đủ Dynamic Symbolic Execution Tên viết tắt DSE Mô tả Kĩ thuật kiểm thử động Static Testing Kĩ thuật kiểm thử tĩnh Concolic Testing Kĩ thuật kiểm thử tự động định hướng Abstract Syntax Tree AST Cây cú pháp trừu tượng Control Flow Graph CFG Đồ thị dòng điều khiển C/C++ Development Tooling CDT Satisfiability Modulo Theories SMT-Solver Solver Boolean Satisfiability Problem SAT Symbolic Execution SE Kĩ thuật thực thi tượng trưng Path selection strategy Chiến thuật chọn đường thi hành (trong DSE) Test driver Bộ thực thi dữ liệu kiểm thử Test data Dữ liệu kiểm thử Test path Đường thi hành (sinh từ đồ thị CFG) Modified condition/ decision MC/DC coverage Độ phủ cấp ba (hoặc phủ điều kiện con) VII DANH SÁCH BẢNG BIỂU Bảng 3.1. Danh sách quan hệ phụ thuộc lô-gic điển hình .................................................. 10 Bảng 3.2. Luật chèn câu lệnh đánh dấu vào hàm ............................................................... 13 Bảng 4.1. Thông tin các công cụ so sánh trong thực nghiệm............................................. 35 Bảng 4.2. Thông tin cấu hình các ví dụ trong thực nghiệm ............................................... 36 Bảng 4.3. Thông tin các hàm kiểm thử về tiêu chí độ phủ và số bộ dữ liệu kiểm thử ....... 37 Bảng 4.4. Kết quả so sánh công cụ CFT4Cpp với KLEE và PathCrawler ........................ 38 Bảng 4.5. Kết quả so sánh công cụ CFT4Cpp với CREST và CAUT ............................... 39 Bảng 4.6. Sinh dữ liệu kiểm thử vòng lặp .......................................................................... 41 Bảng 4.7. Bảng so sánh thời gian biên dịch và thực thi dữ liệu kiểm thử giữa kĩ thuật cải tiến và kĩ thuật truyền thống ............................................................................................... 43 DANH SÁCH THUẬT TOÁN Thuật toán 3.1. Thuật toán LDFS sinh dữ liệu kiểm thử. ................................................... 15 Thuật toán 3.2. Thuật toán xây dựng hệ ràng buộc từ đường thi hành. ............................. 23 DANH SÁCH HÌNH VẼ Hình 2.1. Các cấu trúc điều khiển phổ biến trong C/C++. ................................................... 7 Hình 3.1. Tổng quan phương pháp đề xuất. ......................................................................... 9 Hình 3.2. Ví dụ cây cấu trúc của một dự án C/C++ điển hình. .......................................... 12 Hình 3.3. Minh họa đồ thị CFG phủ câu lệnh/nhánh. ........................................................ 17 Hình 3.4. Minh họa đồ thị CFG phủ MC/DC. .................................................................... 18 Hình 3.5. Mô hình bộ nhớ sử dụng trong kĩ thuật thực thi tượng trưng............................. 21 Hình 3.6. Quy trình xây dựng biểu thức SMT-Lib từ ràng buộc. ...................................... 25 Hình 3.7. Quá trình biến đổi hệ ràng buộc về chuẩn SMTLib. .......................................... 25 Hình 3.8. Kĩ thuật tạo bộ thực thi ca kiểm thử tổng quát. .................................................. 28 VIII Hình 4.1. Kiến trúc công cụ CFT4Cpp............................................................................... 30 Hình 4.2. Giao diện chính của công cụ CFT4Cpp. ............................................................ 31 Hình 4.3. Giao diện bước cấu hình công cụ CFT4Cpp. ..................................................... 32 Hình 4.4. Giao diện sinh dữ liệu kiểm thử cho hàm Divide. .............................................. 32 Hình 4.5. Biên bản kiểm thử xuất bởi công cụ CFT4Cpp cho hàm Divide. ...................... 33 Hình 4.6. Minh họa kết quả giải hệ ràng buộc sử dụng Z3. ............................................... 34 DANH SÁCH MÃ NGUỒN Mã nguồn 3.1. Ví dụ một phần mã nguồn trong dự án C/C++. ......................................... 12 Mã nguồn 3.2. Ví dụ hàm checkFirstSubject sau khi chèn câu lệnh đánh dấu. ................. 14 Mã nguồn 3.3. Mã nguồn hàm average. ............................................................................. 17 Mã nguồn 4.1. Minh họa một hệ ràng buộc theo chuẩn SMT-Lib. .................................... 34 IX TÓM TẮT Để đảm bảo chất lượng phần mềm, nhiều kĩ thuật kiểm thử khác nhau được áp dụng khiến chi phí kiểm thử tăng cao. Trong đó, kiểm thử đơn vị là một trong những kĩ thuật được áp dụng rộng rãi trong các công ty phần mềm để kiểm tra chất lượng mã nguồn, đặc biệt đối với các phần mềm nhúng viết bằng ngôn ngữ C/C++. Kĩ thuật này giúp phát hiện sớm nhiều vấn đề tiềm ẩn trong quy trình xây dựng phần mềm. Tuy nhiên, nhược điểm của kĩ thuật kiểm thử đơn vị là vấn đề chi phí tăng cao đối với những dự án lớn bởi vì kĩ thuật kiểm thử này xem xét tính đúng đắn của từng thành phần nhỏ nhất trong mã nguồn. Để giảm thiểu bài toán chi phí, quy trình kiểm thử đơn vị nên được tự động hóa hoàn toàn. Bởi thế, luận văn hướng đến xây dựng một giải pháp kiểm thử tự động mức đơn vị cho các dự án C/C++. Tư tưởng chính của phương pháp đề xuất dựa trên kĩ thuật kiểm thử tự động định hướng. Hiện nay, kĩ thuật kiểm thử tự động định hướng đã được chứng minh tính hiệu quả trong bài toán kiểm thử tự động. Tuy vậy, các vấn đề còn tồn tại cần giải quyết của kĩ thuật kiểm thử tự động định hướng gồm vấn đề sinh dữ liệu kiểm thử đầu tiên chưa đủ tốt, sinh tập dữ liệu kiểm thử có số lượng nhỏ nhưng đạt độ phủ cao. Do đó, luận văn tập trung giải quyết các bài toán này. Cụ thể, luận văn đề xuất kĩ thuật sinh dữ liệu kiểm thử đầu tiên dựa trên thông tin phân tích mã nguồn thay vì áp dụng kĩ thuật sinh ngẫu nhiên truyền thống trong kĩ thuật kiểm thử tự động định hướng. Để giảm thiểu số lượng bộ dữ liệu kiểm thử trong khi vẫn đạt độ phủ cao, thuật toán LDFS được đề xuất. Để chứng minh tính hiệu quả của phương pháp đề xuất, công cụ CFT4Cpp được xây dựng dựa trên phương pháp đề xuất và tiến hành so sánh với các phương pháp kiểm thử khác gồm KLEE, PathCrawler, CAUT, CREST. Kết quả nghiên cứu đã được đăng trong hai hội nghị NICS 2016 và SoICT 2017 với đánh giá khả quan về tính thực tiễn của phương pháp đề xuất. 1 GIỚI THIỆU Kiểm thử đơn vị là một trong những pha quan trọng nhất để đảm bảo chất lượng của phần mềm, đặc biệt các phần mềm nhúng. Hai phương pháp được sử dụng phổ biến gồm kiểm thử hộp đen và kiểm thử hộp trắng. Kiểm thử hộp đen chỉ kiểm tra tính đúng đắn của đầu ra với đầu vào cho trước mà không quan tâm đến mã nguồn chương trình. Ngược lại, phương pháp kiểm thử hộp trắng đánh giá chất lượng mã nguồn bằng cách sử dụng các kĩ thuật phân tích mã nguồn. Bởi vì kiểm thử hộp trắng đi sâu vào phân tích mã nguồn nên kĩ thuật này cho phép phát hiện các vấn đề tiềm ẩn mà kiểm thử hộp đen không phát hiện được. Tuy nhiên, chi phí kiểm thử hộp trắng lớn hơn rất nhiều so với kiểm thử hộp đen. Đặc biệt, trong các dự án công nghiệp, chi phí kiểm thử hộp trắng có thể chiếm hơn 50% tổng chi phí phát triển phần mềm. Nguyên nhân của tình trạng này là do số lượng hàm cần kiểm thử lên tới hàng nghìn, thậm chí hàng chục nghìn hàm. Kết quả là chi phí để kiểm thử hết những hàm này khá lớn, ảnh hưởng khá nhiều đến tốc độ phát triển dự án. Vì thế, quá trình kiểm thử hộp trắng cần được tự động hóa để giải quyết bài toán về chi phí. Hai hướng chính trong kiểm thử đơn vị theo phương pháp kiểm thử hộp trắng gồm phát hiện lỗi và tối đa hóa độ phủ. Cho một hàm cần kiểm thử hộp trắng, hàm này có thể có vấn đề tiềm ẩn rất khó phát hiện. Yêu cầu chính là sinh tập dữ liệu kiểm thử để kiểm tra chất lượng hàm này. Theo hướng đầu tiên, tập dữ liệu kiểm thử này cần phát hiện được các lỗi tiềm tàng như lỗi chia cho 0, lỗi tràn bộ nhớ [2], [14]. Hướng thứ hai yêu cầu sinh tập dữ liệu kiểm thử sao cho số lượng nhánh, câu lệnh, hoặc điều kiện con được thực thi lớn nhất. Khái niệm độ phủ liên quan đến chất lượng dữ liệu kiểm thử theo hướng tối đa hóa độ phủ. Độ phủ càng lớn đồng nghĩa với chất lượng bộ dữ liệu kiểm thử càng cao. Ví dụ, nếu hàm cần kiểm thử có 10 nhánh mà chỉ có 9 nhánh được đi qua bởi tập 3 dữ liệu kiểm thử thì độ phủ đạt được bằng 90%. Điều đó có nghĩa là trong hàm này có một nhánh thừa cần được phát hiện. Các công 2 cụ kiểm thử tiêu biểu theo hướng này có thể kể đến PathCrawler1 [13], CAUT2 [11], CUTE [10], CREST3 [1]. Đối với bài toán sinh tập dữ liệu kiểm thử để đạt độ phủ tối đa, hai phương pháp kiểm thử hộp trắng được sử dụng phổ biến gồm kiểm thử tĩnh và kiểm thử động. Tư tưởng chính của phương pháp kiểm thử tĩnh là sinh dữ liệu kiểm thử bằng phân tích mã nguồn. Theo như phương pháp này, tất cả mọi cú pháp trong chương trình cần được hỗ trợ phân tích đầy đủ. Tốc độ là một trong những ưu điểm chính của phương pháp kiểm thử tĩnh bởi kĩ thuật này không yêu cầu thực thi chương trình như kĩ thuật động. Tuy nhiên, phương pháp này khó áp dụng cho các dự án công nghiệp bởi vì rất khó để hỗ trợ tất cả mọi cú pháp có thể của ngôn ngữ C/C++. Trái ngược với phương pháp kiểm thử tĩnh, phương pháp kiểm thử động không yêu cầu phải phân tích mọi cú pháp của chương trình để sinh dữ liệu kiểm thử. Để giảm chi phí phân tích mã nguồn mà vẫn đạt độ phủ tối đa, phương pháp kiểm thử động kết hợp quá trình phân tích cú pháp chương trình với trình biên dịch [2] [13] [5] [1]. Bởi thế, phương pháp kiểm thử động dễ dàng đạt được độ phủ cao với nỗ lực phân tích chương trình nhỏ hơn so với phương pháp kiểm thử tĩnh. Phương pháp kiểm thử động gồm hai kĩ thuật kiểm thử được sử dụng phổ biến gồm kĩ thuật EGT (execution generated testing) và kĩ thuật kiểm thử tự động định hướng. Kĩ thuật EGT được áp dụng trong công cụ sinh dữ liệu kiểm thử tự động nổi tiếng KLEE (2008) – một công cụ được đánh giá cao bởi tính hiệu quả của nó. Tư tưởng chính của kĩ thuật EGT là vừa biên dịch và chạy chương trình vừa sinh dữ liệu kiểm thử trực tiếp. Chẳng hạn, khi trình biên dịch gặp một điều kiện, dữ liệu kiểm thử tương ứng nhánh đúng và nhánh sai của điều kiện này được sinh ra. Tại đây, với mỗi dữ liệu kiểm thử, một tiến trình mới được tạo ra sẽ phân tích chương trình theo nhánh đúng/sai đó. Quá trình sinh dữ liệu kiểm thử chỉ dừng khi một trong ba điều kiện sau thỏa mãn (i) đạt độ phủ tối đa (ii) không còn nhánh đúng/sai nào để phân tích tiếp, (iii) đạt đến giới hạn thời gian cho phép. Nhược điểm chính của kĩ thuật 1 http://pathcrawler-online.com:8080/ 2 https://github.com/tingsu/caut-lib 3 https://github.com/jburnim/crest 3 EGT là hiệu suất thấp khi kiểm thử hàm chứa vòng lặp có số lần lặp lớn, hoặc chứa lời gọi đệ quy. Khi đó, số tiến trình được tạo ra có thể từ hàng trăm tới hàng nghìn. Kĩ thuật này thể hiện tính hiệu quả khi tìm các lỗi tiềm ẩn trong chương trình bởi vì EGT xem xét mọi trường hợp có thể xảy ra. Tuy nhiên, kĩ thuật EGT không phù hợp với bài toán sinh dữ liệu kiểm thử đạt độ phủ tối đa bởi vì chúng ta không cần xem xét hết mọi trường hợp khi sinh dữ liệu kiểm thử. Kĩ thuật hay được sử dụng kế tiếp gọi là kĩ thuật kiểm thử tự động định hướng được đề xuất vào năm 2005 và cài đặt trong công cụ DART. Sau này, kĩ thuật kiểm thử tự động định hướng liên tục được cải tiến trong các công cụ PathCrawler, CUTE, CAUT, và CREST. Trong phương pháp này, dữ liệu kiểm thử đầu tiên được sinh ngẫu nhiên, sau đó đẩy vào hàm cần kiểm thử để lấy danh sách các câu lệnh đi qua. Với một bộ dữ liệu kiểm thử, tập các câu lệnh này gọi là một đường thi hành. Dữ liệu kiểm thử kế tiếp được sinh ra dựa trên hai thông tin gồm tiêu chí độ phủ (phủ câu lệnh/nhánh) và trạng thái của chương trình. Quá trình sinh dữ liệu kiểm thử kết thúc khi độ phủ đạt được tối đa hoặc chạm đến giới hạn thời gian. Hiện tại, nhiều công trình nghiên cứu đưa ra nhiều chiến thuật chọn đường thi hành khác nhau để sinh dữ liệu kiểm thử kế tiếp càng tăng độ phủ càng tốt như [11], [1], [13]. Bởi thế, số lượng bộ dữ liệu kiểm thử đạt được độ phủ tối ưu khá ít nên khiến quy trình quản lý dữ liệu kiểm thử dễ dàng hơn. Tuy nhiên, kĩ thuật kiểm thử tự động định hướng còn tồn tại nhiều vấn đề cần giải quyết. Vấn đề thứ nhất, dữ liệu kiểm thử đầu tiên thường được sinh ngẫu nhiên dựa trên kiểu biến. Chẳng hạn, nếu biến có kiểu con trỏ cấu trúc thì xác suất sinh giá trị biến đó bằng NULL hoặc khác NULL bằng 50% [5]. Kĩ thuật sinh ngẫu nhiên này không thể hiện tính hiệu quả khi chương trình có biến truy cập vùng nhớ, ví dụ như hàm sao chép xâu s1 cho s2. Rõ ràng, giá trị xâu s1 luôn khác NULL. Nếu giá trị s1 bằng NULL, chương trình sẽ bị lỗi khi thực thi bộ giá trị này. Tuy nhiên, kĩ thuật sinh dữ liệu kiểm thử đầu tiên theo phương pháp ngẫu nhiên không phát hiện được ràng buộc quan trọng này. Quá trình sinh dữ liệu kiểm thử đầu tiên lặp đi lặp lại đến khi dữ liệu kiểm thử này không gây lỗi. Điều đó dẫn đến thời gian sinh dữ liệu kiểm thử đầu tiên mà không gây lỗi tăng lên. Vấn đề thứ hai liên quan đến bài toán phân tích chương trình C/C++. Các phương pháp kiểm thử đã đề xuất trong [1], [11], [13], và [2] chỉ áp dụng cho ngôn ngữ C mà không hỗ trợ C++. 4 Luận văn hướng đến giải quyết các vấn đề của kiểm thử kĩ thuật kiểm thử tự động định hướng trong bài toán kiểm thử dự án C/C++. Mục tiêu chính của luận văn gồm đề xuất phương pháp sinh dữ liệu kiểm thử giải quyết vấn đề dữ liệu kiểm thử đầu tiên và phương pháp phân tích mã nguồn dự án C/C++ để sinh tập dữ liệu kiểm thử số lượng nhỏ và đạt độ phủ tối đa. Tư tưởng chính của phương pháp đề xuất như sau. Đầu vào bài toán gồm tiêu chí độ phủ (câu lệnh/nhánh/điều kiện con), số lần lặp tối đa của vòng lặp, cận biến số nguyên/kí tự, số phần tử tối đa của mảng, và hàm cần kiểm thử. Đầu tiên, hàm cần kiểm thử được phân tích xây dựng đồ thị dòng điều khiển tương ứng. Sau đó, tập các đường thi hành có thể có trên đồ thị này được thu thập bằng cách áp dụng thuật toán duyệt đồ thị theo chiều sâu. Tập các dữ liệu kiểm thử này được sắp xếp theo thứ tự ưu tiên nào đó, ví dụ như đường ngắn nhất có độ ưu tiên cao nhất. Với từng đường thi hành được sắp xếp theo độ ưu tiên, kĩ thuật thực thi tượng trưng và SMT-Solver được áp dụng để tìm bộ giá trị thỏa mãn đường thi hành đó. Nếu tồn tại bộ giá trị thỏa mãn, ta coi đó là một bộ dữ liệu kiểm thử. Đồng thời, trạng thái độ phủ đồ thị được cập nhật và tập đường thi hành nêu trên loại bỏ các đường thi hành thừa (không tăng độ phủ). Quá trình sinh dữ liệu kiểm thử lặp đi lặp lại đến khi đạt được độ phủ tối đa, hoặc đạt đến giới hạn thời gian cho trước. Phần còn lại luận văn được trình bày như sau. Chương 2 trình bày nền tảng lý thuyết về nghiên cứu sinh dữ liệu kiểm thử tự động cho C/C++. Chương 3 mô tả chi tiết về phương pháp đề xuất. Kế tiếp, chương 4 trình bày công cụ và thực nghiệm về tính hiệu quả phương pháp đề xuất. Cuối cùng, chương 5 đưa ra kết luận về những gì đã làm được, những vấn đề còn tồn tại và hướng phát triển. 5 TỔNG QUAN KĨ THUẬT KIỂM THỬ TỰ ĐỘNG ĐỊNH HƯỚNG Mục tiêu chương này chung cấp nền tảng lý thuyết trong sinh dữ liệu kiểm thử tự động gồm khái niệm dữ liệu kiểm thử và độ phủ, đồ thị dòng điều khiển, cây cú pháp trừu tượng, và tổng quan kĩ thuật kiểm thử tự động định hướng. 2.1. Dữ liệu kiểm thử Dữ liệu kiểm thử là những bộ giá trị được sinh từ chương trình mà không sử dụng giá trị đầu ra mong muốn (expected output) và được định nghĩa như sau: Định nghĩa 2.1 (Test data – Dữ liệu kiểm thử) Một bộ dữ liệu kiểm thử của hàm C/C++ được định nghĩa T = {v1, v2, …, vk | 1 <= k}, trong đó k là số lượng biến truyền vào hàm, vi là giá trị của biến thứ i trong danh sách biến. Biến truyền vào hàm có thể là tham số hoặc biến ngoài (biến tĩnh, biến extern, v.v.). Kiểu biến là kiểu cơ bản, kiểu dẫn xuất, kiểu con trỏ, hoặc kiểu mảng. 2.2. Các tiêu chí độ phủ sử dụng trong kĩ thuật kiểm thử tự động định hướng Mục đích của luận văn là sinh dữ liệu kiểm thử đạt độ phủ tối đa với số lượng bộ dữ liệu kiểm thử nhỏ. Nói chung, độ phủ là một thước đo quan trọng để đánh giá chất lượng mã nguồn. Các loại độ phủ phổ biến trong sinh dữ liệu kiểm thử đơn vị gồm phủ nhánh, phủ câu lệnh, và độ phủ điều kiện con. Tùy theo từng tiêu chí độ phủ mà công thức tính giá trị độ phủ khác nhau. - Độ phủ câu lệnh (statement coverage). Sinh tập dữ liệu kiểm thử sao cho mỗi câu lệnh được thực hiện ít nhất một lần. Nếu chương trình gồm 10 câu lệnh, mà tập dữ liệu kiểm thử chỉ thực thi 8 câu lệnh thì độ phủ đạt được bằng 80%. - Độ phủ câu lệnh (branch coverage). Sinh tập dữ liệu kiểm thử sao cho mỗi nhánh đúng/sai tại các câu lệnh điều kiện đều được đi qua. Nếu chương trình chỉ có 3 câu lệnh điều khiển (6 nhánh), mà tập dữ liệu kiểm thử chỉ thực thi 4 nhánh thì độ phủ đạt được bằng 66.67%. - Độ phủ điều kiện con (MC/DC). Độ phủ này tương tự như độ phủ câu lệnh. Để thỏa mãn độ phủ điều kiện con, tập dữ liệu kiểm thử sinh ca cần đảm bảo đi qua mọi nhánh đúng/sai của các điều kiện con. Điều kiện trong một câu lệnh 6 điều kiện cần được phân tách thành các điều kiện con để tính toán. Chẳng hạn, điều kiện a>b && c>1 gồm hai điều kiện con a>b và c>1. Tập dữ liệu kiểm thử cần đi qua hai nhánh đúng/sai của hai điều kiện con này. Tổng số nhánh đúng/sai của điều kiện này là 4. Về bản chất, nếu một tập dữ liệu kiểm thử cho độ phủ MC/DC đạt 100% (mọi nhánh đúng/sai của điều kiện con được đi qua) thì độ phủ nhánh và câu lệnh bằng 100%. Tương tự, nếu độ phủ nhánh bằng 100% thì độ phủ câu lệnh đạt được tối đa với cùng tập dữ liệu kiểm thử. Độ phủ điều kiện con chặt hơn độ phủ nhánh, và độ phủ nhánh chặt hơn độ phủ câu lệnh. Với cùng một chương trình, số lượng dữ liệu kiểm thử thỏa mãn độ phủ điều kiện con có thể lớn hơn độ phủ câu lệnh và độ phủ câu lệnh. Tuy độ phủ điều kiện con đảm bảo chất lượng phần mềm tốt hơn, chi phí để sinh bộ dữ liệu kiểm thử thỏa mãn tiêu chí độ phủ này cao hơn nhiều với hai độ phủ còn lại. Trong thực tế, độ phủ câu lệnh và nhánh được sử dụng phổ biến do đủ đảm bảo được chất lượng phần mềm. Trường hợp ta sinh tập dữ liệu kiểm thử không thể đạt được độ phủ tối đa, hai trường hợp có thể xảy ra gồm: - Tập dữ liệu kiểm thử sinh ra chưa đủ tốt. Để giải quyết vấn đề này, nhiều nghiên cứu đề xuất để sinh tập dữ liệu kiểm thử nhỏ mà đạt độ phủ tối đa - Mã nguồn thừa câu lệnh/nhánh. Nếu tập dữ liệu kiểm thử sinh ra không đạt được độ phủ tối đa, tức là chương trình có khả năng thừa câu lệnh hoặc nhánh không bao giờ đi qua 2.3. Đồ thị dòng điều khiển Định nghĩa 2.2 (Control flow graph - Đồ thị dòng điều khiển) Đồ thị dòng điều khiển của một hàm được định nghĩa G = (V, E), trong đó V = {n0, n1, …, nk-1} chứa các câu lệnh, nhóm câu lệnh trong chương trình. 𝑬 = {(𝒏𝒊 , 𝒏𝒋 )|𝒏𝒊 , 𝒏𝒋 ∈ 𝑽, 𝟎 ≤ 𝒊, 𝒋 ≤ 𝒌 − 𝟏} ⊂ 𝑽 × 𝑽 đại diện các cạnh. Cạnh (ni,nj) thể hiện rằng câu lệnh ni được thực thi trước câu lệnh nj. Các cấu trúc điều khiển phổ biến trong C/C++ gồm tuần tự, if-else, while-do, do-while, for, try-catch. Hình 2.1 minh họa các cấu trúc điều khiển nêu trên. Đỉnh có kí hiệu c là đỉnh điều kiện. 7 tuần tự if-else do-while while-do for Hình 2.1. Các cấu trúc điều khiển phổ biến trong C/C++. Đồ thị dòng điều khiển ứng với tiêu chí phủ câu lệnh/phủ nhánh giống nhau, và có thể khác với tiêu chí MC/DC. Sự giống nhau xảy ra khi mã nguồn hàm không có điều kiện kép, tức chỉ có điều kiện đơn. 2.4. Cây cú pháp trừu tượng Cây cú pháp trừu tượng được sử dụng rộng rãi trong các trình biên dịch hoặc IDE. Với đầu vào là mã nguồn, các trình biên dịch/IDE này sẽ xây dựng cây AST tương ứng. Về bản chất, cây AST là một cách biểu diễn cấu trúc mã nguồn dưới dạng cây. Mỗi một thành phần trong cây tương ứng với một thành phần mã nguồn như câu lệnh gán, khối lệnh điều kiện, biến, phép toán, v.v. Mỗi thành phần trong cây đều có các kiểu khác nhau được quy định bởi trình biên dịch. Ví dụ, trong CDT, kiểu IASTDeclSpecifier tương ứng với kiểu trả về của hàm hay kiểu biến. Kiểu IASTBinaryExpression tương ứng với dấu phép toán. Kiểu IASTName đại diện tên biến, tên hàm. IASTReturnStatement chính là câu lệnh return. 2.5. Quy trình chung kĩ thuật kiểm thử tự động định hướng Kĩ thuật kiểm thử tự động định hướng được đề xuất lần đầu tiên bởi nhà khoa học Koushik Sen cùng các cộng sự lần đầu tiên vào 2005 [5]. Quy trình thuật kiểm thử tự động định hướng gồm các bước như sau: Bước 1. Chèn các câu lệnh đánh dấu vào hàm cần kiểm thử (instrument function). Các câu lệnh đánh dấu giúp xác định được danh sách câu lệnh được thực thi khi chạy chương trình. Chi tiết kĩ thuật chèn các câu lệnh 8 đánh dấu được trình bày trong phần 3.2.2. Chèn các câu lệnh đánh dấu vào hàm. Bước 2. Dựa trên tham số truyền vào hàm và các biến ngoài hàm sử dụng, một bộ giá trị ngẫu nhiên được sinh ra để chạy chương trình. Chẳng hạn, nếu biến truyền vào là con trỏ kiểu cấu trúc thì giá trị của biến đó có thể bằng NULL, hoặc được cấp phát một vùng nhớ ngẫu nhiên nào đó. Ta coi bộ giá trị ngẫu nhiên này là dữ liệu kiểm thử đầu tiên. Tư tưởng của kĩ thuật kiểm thử tự động định hướng là sinh dữ liệu kiểm thử kế tiếp từ các dữ liệu kiểm thử trước đó. Điều đó có nghĩa là, nếu dữ liệu kiểm thử đầu tiên gây lỗi khi chạy chương trình thì quá trình kiểm thử thất bại. Vấn đề này xuất hiện phổ biến khi sinh dữ liệu kiểm thử cho các hàm có tham số truyền vào kiểu con trỏ. Bước 3. Thực thi chương trình với dữ liệu kiểm thử vừa tìm được. Nếu không thực thi được (lỗi xảy ra) thì quay lại bước 2 để sinh bộ giá trị khác. Bước 4. Tìm tập các câu lệnh đã được đi qua với bộ giá trị ở bước 3 (đường thi hành) Bước 5. Tính độ phủ đạt được với dữ liệu kiểm thử mới nhất. Nếu độ phủ đạt được tối đa, quá trình sinh dữ liệu kiểm thử kết thúc. Ngược lại, đường thi hành kế tiếp được sinh ra dựa trên trạng thái hiện tại của đồ thị. Nhiều chiến thuật chọn đường thi hành kế tiếp được đề xuất trong các nghiên cứu khác nhau từ 2005 trở lại nay. Bước 6. Nếu ta tìm được thi hành kế tiếp, ta xây dựng hệ ràng buộc ứng với đường thi hành này bằng cách áp dụng kĩ thuật thực thi tượng trưng Bước 7. Giải hệ ràng buộc thu được ở bước 6 để sinh dữ liệu kiểm thử kế tiếp. Nếu không có dữ liệu kiểm thử nào thỏa mãn, quay về bước 5 để tìm một đường thi hành tốt hơn. Ngược lại, quay lại bước 3 để chạy dữ liệu kiểm thử kế tiếp này. 9 PHƯƠNG PHÁP KIỂM THỬ TỰ ĐỘNG DỰ ÁN C/C++ SỬ DỤNG KĨ THUẬT KIỂM THỬ TỰ ĐỘNG ĐỊNH HƯỚNG Chương này trình bày chi tiết phương pháp đề xuất để sinh dữ liệu kiểm thử tự động cho dự án C/C++. Phần đầu tiên trình bày tổng quan của phương pháp gồm hai pha chính. Phần kế tiếp trình bày pha tiền xử lý mã nguồn. Pha sinh dữ liệu kiểm thử được trình bày ở phần kế tiếp. Các kĩ thuật cải tiến thời gian sinh dữ liệu kiểm thử được trình bày ở phần cuối cùng chương này. 3.1. Tổng quan phương pháp đề xuất Hình 3.1 trình bày tổng quan phương pháp sinh dữ liệu kiểm thử đề xuất gồm hai pha chính: pha tiền xử lý mã nguồn và pha sinh dữ liệu kiểm thử. Bước đầu tiên trong pha tiền xử lý mã nguồn xây dựng cây cấu trúc tương ứng. Các đỉnh trên cây cấu trúc này đại diện cho các thành phần mã nguồn như các thành phần vật lý (tệp, thư mục), các thành phần lô-gic (class, struct, namespace, khai báo, v.v.). Nói cách khác, thay vì phân tích trực tiếp trên dự án C/C++, quá trình phân tích được tiến hành trên cây cấu trúc này. Sau khi cây cấu trúc đã được xây dựng, bước kế tiếp trong pha đầu tiên chèn thêm các câu lệnh đánh dấu vào các hàm trong dự án C/C++. Nhờ có các câu lệnh đánh dấu này, khi các hàm này được gọi thì tập các câu lệnh được thực thi được lưu lại. Tập các câu lệnh này kết hợp lại theo thứ tự thực hiện được gọi là đường thi hành. Đầu ra của pha đầu tiên gồm cây cấu trúc tương ứng với dự án C/C++, và tập các hàm được chèn các câu lệnh đánh dấu. Hình 3.1. Tổng quan phương pháp đề xuất. Đầu vào trong pha sinh dữ liệu kiểm thử gồm hàm cần kiểm thử cùng với thông tin cấu hình (tiêu chí độ phủ, số lần lặp tối đa của vòng lặp, cận biến số nguyên/kí tự, số phần tử tối đa của mảng). Đầu ra của pha thứ hai là biên bản kiểm thử. Trong 10 pha này, đồ thị dòng điều khiển tương ứng với hàm cần kiểm thử được xây dựng. Sau đó, dựa trên đồ thị dòng điều khiển này, tập dữ liệu kiểm thử thỏa mãn độ phủ và thông tin cấu hình được sinh ra. Để sinh ra tập dữ liệu kiểm thử này, cây cấu trúc cùng với tập các hàm đã đánh dấu được sử dụng trong quá trình xử lý. Cuối cùng, tập dữ liệu kiểm thử này được chuyển sang các bộ mã nguồn kiểm thử tương ứng tuân theo chuẩn của Google Test. 3.2. Pha tiền xử lý mã nguồn 3.2.1. Xây dựng cây cấu trúc từ dự án C/C++ Định nghĩa 3.1 (Component - Thành phần dự án). Thành phần trong dự án C/C++ gồm hai loại: thành phần vật lý và thành phần lô-gic. Thành phần vật lý bao gồm tệp (header, mã nguồn) và thư mục. Thành phần lô-gic gồm các thành phần trong mã nguồn (hàm, biến, khai báo namespace, khai báo class, khai báo struct, v.v.). Định nghĩa 3.2 (Logic dependency – phụ thuộc lô-gic). Hai thành phần dự án n1và n2 có quan hệ phụ thuộc lô-gic khi n2 là tham chiếu của n1, hoặc n1 là tham chiếu của thành phần n2. Bảng 3.1 trình bày một vài danh sách quan hệ phụ thuộc lô-gic điển hình trong các dự án C/C++. Bảng 3.1. Danh sách quan hệ phụ thuộc lô-gic điển hình Quan hệ phụ thuộc lôgic Mô tả Ví dụ (Khai báo class, định Lớp được khai báo nhưng class Student trong nghĩa class) lại được định nghĩa ở nơi Mã nguồn 3.1 khác (typedef, class) Lớp được sử dụng với tên class Student; định nghĩa dùng keyword typedef Student stu; typedef