Tóm tắt Luận văn 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++

1 ĐẠ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 1 Kiểm thử đơn vị là một trong những pha quan trọng nhất để đảm bảo chất lượng cao 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 (black-box testing) và kiểm thử hộp trắng (white-box testing). 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. Tuy nhiê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ác lỗi 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 2 có thể có lỗi tiềm ẩn rất khó phát hiện. Yêu cầu chính là sinh tập ca kiểm thử để kiểm tra chất lượng hàm này. Theo hướng đầu tiên, tập ca kiểm thử này có thể chỉ gây lỗi như lỗi chia cho 0, lỗi tràn bộ nhớ. Hướng thứ hai yêu cầu sinh tập ca 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 ca 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 ca kiểm thử càng tốt. 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 ca 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, hoặc có thể hàm này có lỗi tiềm ẩn nào đó mà kiểm thử hộp đen không phát hiện ra. Các công cụ kiểm thử tiêu biểu theo hướng này có thể kể đến PathCrawler, CAUT, CUTE, CREST. Đối với bài toán sinh tập ca 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 (static tesing) và kiểm thử động (DSE - dynamic symbolic execution). Tư tưởng chính của phương pháp kiểm thử theo hướng tĩnh là sinh ca 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ử theo hướng 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 DSE. 3 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ử DSE không yêu cầu phải phân tích mọi cú pháp của chương trình để sinh ca 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ử DSE 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 KLEE, PathCrawler, DART, CAUT, CREST. Bởi thế, phương pháp kiểm thử DSE 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ử theo hướng tĩnh. Phương pháp kiểm thử theo hướng độ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 concolic. Kĩ thuật EGT được áp dụng trong công cụ sinh ca 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 ca 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, ca 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 ca 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 ca kiểm thử chỉ dừng khi một trong ba điều kiện sau thỏa 4 mãn (1) đạt độ phủ tối đa (2) không còn nhánh đúng/sai nào để phân tích tiếp, (3) đạt đến giới hạn thời gian cho phép. Nhược điểm chính của kĩ thuật 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 nghìn tới hàng chục 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 ca 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 ca kiểm thử. Kĩ thuật hay được sử dụng kế tiếp gọi là concolic được đề xuất vào năm 2005 và cài đặt lần đầu tiên trong công cụ DART. Sau này, kĩ thuật concolic liên tục được cải tiến trong các công cụ PathCrawler, CUTE, CAUT, CREST. Trong phương pháp này, ca 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 ca kiểm thử, tập các ca kiểm thử này gọi là một đường thi hành. Ca kiểm thử kế tiếp được sinh ra dựa trên hai thông tin gồm (1) tiêu chí độ phủ (phủ câu lệnh/nhánh) (2) trạng thái của chương trình. Quá trình sinh ca kiểm thử kết thúc khi (1) độ phủ đạt được tối đa, hoặc (2) đạt đế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 ca kiểm thử kế tiếp càng tăng độ phủ càng tốt như 5 CAUT, CREST, PathCrawler. Bởi thế, số lượng ca kiểm thử đạt được độ phủ tối ưu khá ít nên khiến quy trình quản lý ca kiểm thử dễ dàng hơn. Tuy nhiên, kĩ thuật kiểm thử concolic còn tồn tại nhiều vấn đề cần giải quyết. Vấn đề thứ nhất, ca 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% DART. 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 ca 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 ca kiểm thử đầu tiên lặp đi lặp lại đến khi ca kiểm thử này không gây lỗi. Điều đó dẫn đến thời gian sinh ca 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 CREST, CAUT, PathCrawler, và KLEE chỉ áp dụng cho ngôn ngữ C mà không hỗ trợ C++. Khóa luận hướng đến giải quyết các vấn đề của kiểm thử concolic trong bài toán kiểm thử dự án C/C++. Mục tiêu chính của khóa luận gồm (1) đề xuất phương pháp sinh 6 ca kiểm thử giải quyết vấn đề ca kiểm thử đầu tiên (2) đề xuất phương pháp phân tích mã nguồn dự án C/C++ để sinh tập ca kiểm thử số lượng nhỏ nhất 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), 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 ca 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 ca kiểm thử. Trạng thái độ phủ đồ thị được cập nhật. Đồng thời, 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 ca 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. Tài liệu tham khảo [1] J. Burnim and K. Sen. 2008. Heuristics for Scalable Dynamic Test Generation. In Proceedings of the 2008 7 23rd IEEE/ACM International Conference on Automated Software Engineering (ASE ’08). IEEE Computer Society, Washington, DC, USA, 443–446. [2] Cristian Cadar, Daniel Dunbar, and Dawson Engler. 2008. KLEE: Unassisted and Automatic Generation of High-coverage Tests for Complex Systems Programs. In Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation (OSDI’08). USENIX Association, Berkeley, CA, USA, 209–224. [3] Cristian Cadar and Koushik Sen. 2013. Symbolic Execution for Software Testing: Three Decades Later. Commun. ACM 56, 2 (Feb. 2013), 82–90. [4] Leonardo De Moura and Nikolaj Bjørner. 2008. Z3: An Efficient SMT Solver. In Proceedings of the Theory and Practice of Software, 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS’08/ETAPS’08). Springer- Verlag, Berlin, Heidelberg, 337–340. [5] Patrice Godefroid, Nils Klarlund, and Koushik Sen. 2005. DART: Directed Automated Random Testing. In Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’05). ACM, New York, NY, USA, 213–223. 8 [6] James C. King. 1976. Symbolic Execution and Program Testing. Commun. ACM 19, 7 (July 1976), 385–394. [7] Guodong Li, Indradeep Ghosh, and Sreeranga P. Rajan. 2011. KLOVER: A Symbolic Execution and Automatic Test Generation Tool for C++ Programs. In Proceedings of the 23rd International Conference on Computer Aided Verification (CAV’11). Springer- Verlag, Berlin, Heidelberg, 609–615. [8] George C. Necula, Scott McPeak, Shree Prakash Rahul, and Westley Weimer. 2002. CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs. In Proceedings of the 11th International Conference on Compiler Construction (CC ’02). Springer-Verlag, London, UK, UK, 213–228. [9] D. A. Nguyen, P. N. Hung, and V. H. Nguyen. 2016. A method for automated unit testing of C programs. In 2016 3rd National Foundation for Science and Technology Development Conference on Information and Computer Science (NICS). 17–22. [10] Dirk Riehle. 1997. Composite Design Patterns. In Proceedings of the 12th ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and 9 Applications (OOPSLA ’97). ACM, New York, NY, USA, 218–228. [11] Koushik Sen, Darko Marinov, and Gul Agha. 2005. CUTE: A Concolic Unit Testing Engine for C. In Proceedings of the 10th European Software Engineering Conference Held Jointly with 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering (ESEC/FSE-13). ACM, New York, NY, USA, 263–272. [12] T. Su, G. Pu, B. Fang, J. He, J. Yan, S. Jiang, and J. Zhao. 2014. Automated CoverageDriven Test Data Generation Using Dynamic Symbolic Execution. In 2014 Eighth International Conference on Software Security and Reliability (SERE). 98–107. [13] Z. Wang, X. Yu, T. Sun, G. Pu, Z. Ding, and J. Hu. 2009. Test Data Generation for Derived Types in C Program. In 2009 Third IEEE International Symposium on Theoretical Aspects of Software Engineering. 155– 162. [14] Nicky Williams, Bruno Marre, Patricia Mouy, and Muriel Roger. 2005. PathCrawler: Automatic Generation of Path Tests by Combining Static and Dynamic Analysis. In Proceedings of the 5th European Conference 10 on Dependable Computing (EDCC’05). Springer-Verlag, Berlin, Heidelberg, 281–292