Tóm tắt Luận văn Thạc sĩ Kỹ thuật phần mềm: 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<br /> 1 GIA HÀ NỘI<br /> TRƯỜNG ĐẠI HỌC CÔNG NGHỆ<br /> <br /> Nguyễn Đức Anh<br /> <br /> PHƯƠNG PHÁP PHÂN TÍCH MÃ NGUỒN VÀ<br /> SINH DỮ LIỆU KIỂM THỬ CHO CÁC DỰ ÁN C/C++<br /> <br /> Ngành: Công nghệ thông tin<br /> Chuyên ngành: Kỹ thuật phần mềm<br /> Mã số: 60480103<br /> <br /> LUẬN VĂN THẠC SĨ: KỸ THUẬT PHẦN MỀM<br /> <br /> Cán bộ hướng dẫn: PGS. TS. Phạm Ngọc Hùng<br /> <br /> HÀ NỘI - 2017<br /> <br /> 1<br /> Kiểm thử đơn vị là một trong những pha quan trọng nhất<br /> để đảm bảo chất lượng cao của phần mềm, đặc biệt các<br /> phần mềm nhúng. Hai phương pháp được sử dụng phổ<br /> biến gồm kiểm thử hộp đen (black-box testing) và kiểm<br /> thử hộp trắng (white-box testing). Kiểm thử hộp đen chỉ<br /> kiểm tra tính đúng đắn của đầu ra với đầu vào cho trước<br /> mà không quan tâm đến mã nguồn chương trình. Ngược<br /> lại, phương pháp kiểm thử hộp trắng đánh giá chất lượng<br /> mã nguồn bằng cách sử dụng các kĩ thuật phân tích mã<br /> nguồn. Tuy nhiên, bởi vì kiểm thử hộp trắng đi sâu vào<br /> phân tích mã nguồn nên kĩ thuật này cho phép phát hiện<br /> được các lỗi tiềm ẩn mà kiểm thử hộp đen không phát<br /> hiện được. Tuy nhiên, chi phí kiểm thử hộp trắng lớn hơn<br /> rất nhiều so với kiểm thử hộp đen. Đặc biệt, trong các dự<br /> án công nghiệp, chi phí kiểm thử hộp trắng có thể chiếm<br /> hơn 50% tổng chi phí phát triển phần mềm. Nguyên nhân<br /> của tình trạng này là do số lượng hàm cần kiểm thử lên<br /> tới hàng nghìn, thậm chí hàng chục nghìn hàm. Kết quả<br /> là chi phí để kiểm thử hết những hàm này khá lớn, ảnh<br /> hưởng khá nhiều đến tốc độ phát triển dự án. Vì thế, quá<br /> trình kiểm thử hộp trắng cần được tự động hóa để giải<br /> quyết bài toán về chi phí.<br /> Hai hướng chính trong kiểm thử đơn vị theo phương<br /> pháp kiểm thử hộp trắng gồm phát hiện lỗi và tối đa hóa<br /> độ phủ. Cho một hàm cần kiểm thử hộp trắng, hàm này<br /> <br /> 2<br /> có thể có lỗi tiềm ẩn rất khó phát hiện. Yêu cầu chính là<br /> sinh tập ca kiểm thử để kiểm tra chất lượng hàm này.<br /> Theo hướng đầu tiên, tập ca kiểm thử này có thể chỉ gây<br /> lỗi như lỗi chia cho 0, lỗi tràn bộ nhớ. Hướng thứ hai yêu<br /> cầu sinh tập ca kiểm thử sao cho số lượng nhánh, câu<br /> lệnh, hoặc điều kiện con được thực thi lớn nhất. Khái<br /> niệm độ phủ liên quan đến chất lượng ca kiểm thử theo<br /> hướng tối đa hóa độ phủ. Độ phủ càng lớn đồng nghĩa<br /> với chất lượng ca kiểm thử càng tốt. Ví dụ, nếu hàm cần<br /> kiểm thử có 10 nhánh mà chỉ có 9 nhánh được đi qua bởi<br /> tập 3 ca kiểm thử thì độ phủ đạt được bằng 90%. Điều đó<br /> có nghĩa là trong hàm này có một nhánh thừa cần được<br /> phát hiện, hoặc có thể hàm này có lỗi tiềm ẩn nào đó mà<br /> kiểm thử hộp đen không phát hiện ra. Các công cụ kiểm<br /> thử tiêu biểu theo hướng này có thể kể đến PathCrawler,<br /> CAUT, CUTE, CREST. Đối với bài toán sinh tập ca<br /> kiểm thử để đạt độ phủ tối đa, hai phương pháp kiểm thử<br /> hộp trắng được sử dụng phổ biến gồm kiểm thử tĩnh<br /> (static tesing) và kiểm thử động (DSE - dynamic<br /> symbolic execution). Tư tưởng chính của phương pháp<br /> kiểm thử theo hướng tĩnh là sinh ca kiểm thử bằng phân<br /> tích mã nguồn. Theo như phương pháp này, tất cả mọi cú<br /> pháp trong chương trình cần được hỗ trợ phân tích đầy<br /> đủ. Tốc độ là một trong những ưu điểm chính của<br /> phương pháp kiểm thử theo hướng tĩnh bởi kĩ thuật này<br /> không yêu cầu thực thi chương trình như kĩ thuật DSE.<br /> <br /> 3<br /> Tuy nhiên, phương pháp này khó áp dụng cho các dự án<br /> công nghiệp bởi vì rất khó để hỗ trợ tất cả mọi cú pháp<br /> có thể của ngôn ngữ C/C++. Trái ngược với phương pháp<br /> kiểm thử tĩnh, phương pháp kiểm thử DSE không yêu<br /> cầu phải phân tích mọi cú pháp của chương trình để sinh<br /> ca kiểm thử. Để giảm chi phí phân tích mã nguồn mà vẫn<br /> đạt độ phủ tối đa, phương pháp kiểm thử DSE kết hợp<br /> quá trình phân tích cú pháp chương trình với trình biên<br /> dịch KLEE, PathCrawler, DART, CAUT, CREST. Bởi<br /> thế, phương pháp kiểm thử DSE dễ dàng đạt được độ phủ<br /> cao với nỗ lực phân tích chương trình nhỏ hơn so với<br /> phương pháp kiểm thử theo hướng tĩnh.<br /> Phương pháp kiểm thử theo hướng động gồm hai kĩ thuật<br /> kiểm thử được sử dụng phổ biến gồm kĩ thuật EGT<br /> (execution generated testing) và kĩ thuật concolic. Kĩ<br /> thuật EGT được áp dụng trong công cụ sinh ca kiểm thử<br /> tự động nổi tiếng KLEE (2008) – một công cụ được đánh<br /> giá cao bởi tính hiệu quả của nó. Tư tưởng chính của kĩ<br /> thuật EGT là vừa biên dịch và chạy chương trình vừa<br /> sinh ca kiểm thử trực tiếp. Chẳng hạn, khi trình biên dịch<br /> gặp một điều kiện, ca kiểm thử tương ứng nhánh đúng và<br /> nhánh sai của điều kiện này được sinh ra. Tại đây, với<br /> mỗi ca kiểm thử, một tiến trình mới được tạo ra sẽ phân<br /> tích chương trình theo nhánh đúng/sai đó. Quá trình sinh<br /> ca kiểm thử chỉ dừng khi một trong ba điều kiện sau thỏa<br /> <br /> 4<br /> mãn (1) đạt độ phủ tối đa (2) không còn nhánh đúng/sai<br /> nào để phân tích tiếp, (3) đạt đến giới hạn thời gian cho<br /> phép. Nhược điểm chính của kĩ thuật EGT là hiệu suất<br /> thấp khi kiểm thử hàm chứa vòng lặp có số lần lặp lớn,<br /> hoặc chứa lời gọi đệ quy. Khi đó, số tiến trình được tạo<br /> ra có thể từ hàng nghìn tới hàng chục nghìn. Kĩ thuật này<br /> thể hiện tính hiệu quả khi tìm các lỗi tiềm ẩn trong<br /> chương trình bởi vì EGT xem xét mọi trường hợp có thể<br /> xảy ra. Tuy nhiên, kĩ thuật EGT không phù hợp với bài<br /> toán sinh ca kiểm thử đạt độ phủ tối đa bởi vì chúng ta<br /> không cần xem xét hết mọi trường hợp khi sinh ca kiểm<br /> thử. Kĩ thuật hay được sử dụng kế tiếp gọi là concolic<br /> được đề xuất vào năm 2005 và cài đặt lần đầu tiên trong<br /> công cụ DART. Sau này, kĩ thuật concolic liên tục được<br /> cải tiến trong các công cụ PathCrawler, CUTE, CAUT,<br /> CREST. Trong phương pháp này, ca kiểm thử đầu tiên<br /> được sinh ngẫu nhiên, sau đó đẩy vào hàm cần kiểm thử<br /> để lấy danh sách các câu lệnh đi qua. Với một ca kiểm<br /> thử, tập các ca kiểm thử này gọi là một đường thi hành.<br /> Ca kiểm thử kế tiếp được sinh ra dựa trên hai thông tin<br /> gồm (1) tiêu chí độ phủ (phủ câu lệnh/nhánh) (2) trạng<br /> thái của chương trình. Quá trình sinh ca kiểm thử kết<br /> thúc khi (1) độ phủ đạt được tối đa, hoặc (2) đạt đến giới<br /> hạn thời gian. Hiện tại, nhiều công trình nghiên cứu đưa<br /> ra nhiều chiến thuật chọn đường thi hành khác nhau để<br /> sinh ca kiểm thử kế tiếp càng tăng độ phủ càng tốt như<br /> <br />