Tài liệu Luận văn cntt nghiên cứu phương pháp sinh dữ liệu kiểm thử từ mã nguồn và ứng dụng xây dựng hệ thống chấm bài tập lập trình

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ KHÁNH CHI PHƢƠNG PHÁP SINH DỮ LIỆU KIỂM THỬ TỰ ĐỘNG TỪ MÃ NGUỒN VÀ ỨNG DỤNG XÂY DỰNG HỆ THỐNG CHẤM BÀI LẬP TRÌNH LUẬN VĂN THẠC SĨ Ngành: Kỹ Thuật Phần Mềm HÀ NỘI – 2019 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ KHÁNH CHI PHƢƠNG PHÁP SINH DỮ LIỆU KIỂM THỬ TỰ ĐỘNG TỪ MÃ NGUỒN VÀ ỨNG DỤNG XÂY DỰNG HỆ THỐNG CHẤM BÀI LẬP TRÌNH Ngành: Kỹ Thuật Phần Mềm Chuyên ngành: Kỹ Thuật Phần Mềm Mã số: 848 01 03.01 LUẬN VĂN THẠC SĨ Ngành: Kỹ Thuật Phần Mềm NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS. TS. Phạm Ngọc Hùng HÀ NỘI – 2019 VIETNAM NATIONAL UNIVERSITY, HANOI UNIVERSITY OF ENGINEERING AND TECHNOLOGY NGUYEN THI KHANH CHI A METHOD FOR AUTOMATED TEST DATA GENERATION FROM SOURCE CODE AND APPLICATION IN BUILDING PROGRAMMING MARKING SYSTEM THE MS. THESIS Major: InformationTechnology Supervisor: Assoc. Prof. Pham Ngoc Hung HANOI - 2019 i MỤC LỤC MỤC LỤC ........................................................................................................................ i LỜI CẢM ƠN ................................................................................................................ iii TÓM TẮT....................................................................................................................... iv ABSTRACT .................................................................................................................... v LỜI CAM ĐOAN ........................................................................................................... vi DANH MỤC THUẬT NGỮ VIẾT TẮT ......................................................................vii DANH MỤC HÌNH VẼ .............................................................................................. viii DANH MỤC BẢNG ....................................................................................................... x Chương 1: Mở đầu ........................................................................................................... 1 Chương 2: Phương pháp sinh dữ liệu kiểm thử dòng điều khiển .................................... 3 2.1 Tổng quan về kiểm thử dòng điều khiển ..................................................................... 3 2.2 Các tiêu chí kiểm thử .................................................................................................. 4 2.3 Xây dựng đồ thị dòng điều khiển ................................................................................ 6 2.3.1.Xây dựng đồ thị dòng điều khiển ứng với tiêu chí phủ câu lệnh và phủ nhánh ..... 8 2.3.2. Xây dựng CFG ứng với tiêu chí phủ điều kiện con ............................................... 9 2.3.3. Phương pháp xây dựng CFG từ mã nguồn Java .................................................. 10 2.4. Sinh đường đi kiểm thử từ đồ thị............................................................................. 12 2.4.1. Sinh đường đi thỏa mãn tiêu chí phủ câu lệnh..................................................... 12 2.4.2. Sinh đường đi thỏa mãn tiêu chí phủ nhánh ........................................................ 13 2.4.3. Sinh đường đi thỏa mãn tiêu chí phủ điều kiện con ............................................ 13 2.4.4. Phương pháp sinh đường đi kiểm thử trên đồ thị ................................................ 14 2.5. Sinh ca kiểm thử từ đường đi ............................................................................. 15 2.5.1. Sinh dữ liệu kiểm thử .......................................................................................... 15 2.5.2. Sinh đầu ra mong muốn ....................................................................................... 17 2.6 . Sinh các ca kiểm thử giá trị biên và vòng lặp.......................................................... 17 2.6.1.Sinh ca kiểm thử giá trị biên ................................................................................. 18 2.6.2. Sinh ca kiểm thử vòng lặp ................................................................................... 19 Chương 3: Công cụ và thực nghiệm .............................................................................. 22 ii 3.1 Đặc tả hệ thống chấm bài lập trình .......................................................................... 22 3.1.1. Danh sách các tác nhân........................................................................................ 22 3.1.2. Mô tả các ca sử dụng của hệ thống: .................................................................... 24 3.2 . Kiến trúc tổng thể của hệ thống chấm bài lập trình................................................ 27 3.3 Kiến trúc của mô-đun sinh ca kiểm thử tự động ....................................................... 28 3.4 Giới thiệu công cụ sinh ca kiểm thử tự động ............................................................ 29 3.3.1.Giao diện công cụ sinh ca kiểm thử tự động ........................................................ 29 3.3.2.Đồ thị dòng điều khiển ......................................................................................... 29 3.3.3.Tập các đường kiểm thử ....................................................................................... 31 3.3.4. Tập các ca kiểm thử ............................................................................................. 31 3.5 Kết quả thực nghiệm ................................................................................................. 33 Bài toán 1: Bài toán kiểm tra năm nhuận ..................................................................... 33 Bài toán 2: Bài toán tính số ngày trong một tháng ....................................................... 35 Bài toán 3: Tìm ước số chung lớn nhất ......................................................................... 40 3.6 .Ý nghĩa của thực nghiệm.......................................................................................... 44 Chương 4: Kết luận ....................................................................................................... 46 TÀI LIỆU THAM KHẢO ............................................................................................. 47 iii LỜI CẢM ƠN Trước tiên, tôi xin gửi lời cảm ơn chân thành và sâu sắc đến người thầy đáng kính PGS. TS. Phạm Ngọc Hùng - người đã trực tiếp hướng dẫn, chỉ bảo và giúp đỡ tôi trong suốt quá trình tôi học tập và nghiên cứu tại trường. Nhờ có lòng tốt của thầy, sự say mê nghiên cứu khoa học, kiến thức uyên thâm và sự hướng dẫn tận tình, tôi đã vượt qua được những khó khăn từ phía gia đình để tiếp tục học tập, nghiên cứu và hoàn thiện luận văn này. Tôi xin chân thành cảm ơn các thầy cô giáo khoa Công nghệ thông tin, trường Đại học Công nghệ, Đại học Quốc Gia Hà Nội đã nhiệt tình giảng dạy, truyền đạt những kiến thức quý báu trong suốt quá trình tôi học tập và nghiên cứu tại trường. Tôi xin chân thành cảm ơn những người thân trong gia đình, các bạn bè, đồng nghiệp luôn tạo điều kiện, giúp đỡ động viên tôi trong công tác nghiên cứu khoa học. Cuối cùng, tôi xin cảm ơn ban giám hiệu trường THPT Ngô Gia Tự - Từ Sơn Bắc Ninh nơi tôi công tác, các đồng nghiệp và các em học sinh khối 11 đã tạo điều kiện tối đa, đóng góp những nhận xét khách quan cho đề tài nghiên cứu để tôi có thể hoàn thành luận văn Thạc sỹ tại trường Đại học Công nghệ - Đại học Quốc Gia Hà Nội. iv TÓM TẮT Luận văn tập trung nghiên cứu phương pháp sinh các ca kiểm thử từ mã nguồn và ứng dụng trong việc tự động chấm các bài tập lập trình của học sinh viết bằng ngôn ngữ Java nhằm hỗ trợ các giáo viên Tin học tại các Trường Trung học phổ thông/Trung học cơ sở trong việc sinh các ca kiểm thử và chấm các bài tập lập trình của học sinh. Với mỗi bài tập, giáo viên sẽ cung cấp mã nguồn mẫu (mã nguồn không có lỗi). Dựa vào mã nguồn này, chúng ta sẽ tiến hành phân tích nhằm xây dựng đồ thị dòng điều khiển của mã nguồn. Tiếp đến, các đường đi của đồ thị ứng với các dòng điều khiển có thể có của chương trình sẽ được sinh. Từ các đường đi này, chúng ta sẽ xây dựng hệ ràng buộc chứa các điều kiện của các tham số. Việc sinh dữ liệu kiểm thử trên đường thực thi chính là việc giải hệ ràng buộc trên đường đi tương ứng. Khi có dữ liệu kiểm thử, chúng ta sẽ sử dụng đầu ra của mã nguồn chuẩn để sinh giá trị đầu ra mong muốn tương ứng. Cùng với các ca kiểm thử đã được sinh ra, luận văn còn nghiên cứu các giải pháp để sinh các ca kiểm thử cho các vòng lặp và sinh các ca kiểm thử tại các biên của từng tham số ứng với miền giá trị và đặc tả của bài toán. Luận văn cũng đã tiến hành xây dựng công cụ hỗ trợ và áp dụng thử nghiệm với các chương trình đơn giản nhằm minh chứng cho tính đúng đắn và tính hiệu quả của phương pháp đề xuất. Tuy nhiên, công cụ cài đặt chưa được hoàn thiện và cần được tiếp tục phát triển nhằm có một công cụ hỗ trợ giáo viên như đã nêu ở trên. Từ khóa: Kiểm thử tự động, sinh dữ liệu kiểm thử, độ phủ kiểm thử, kiểm thử hộp trắng. v ABSTRACT The thesis focuses on studying the method of testing data from source code and applying in automatically marking students' programming exercises written in Java language to support Informatics teachers at high schools. information / junior high school in testing test cases and marking students' programming exercises. For each teacher exercise, the teacher will provide sample source code (source code without errors). Based on this source code, we will conduct source code analysis to build control line graph of source code. Next, we will generate the graph's paths corresponding to the possible control lines of the program. From these paths, we will build the binding system without the conditions of the parameters. Generating test data corresponding to the corresponding path is the finding of a solution of the corresponding system of equations. Whenever there is test data, we will use the specification to generate the desired output values. Along with the test cases as born, the thesis also studies solutions to generate test cases for loops and generate test cases at the boundaries of each parameter corresponding to the value domain and specification of the problem. The thesis has also developed support tools and applied experiments with simple programs to demonstrate the correctness and effectiveness of the proposed method. However, the installation tool has not been completed and needs to be further developed in order to have a teacher support tool as mentioned above. Keywords: Automated testing, test data generation, test coverage, white-box testing vi LỜI CAM ĐOAN Tôi xin cam đoan luận văn Thạc sỹ Công nghệ thông tin "Phương pháp sinh dữ liệu kiểm thử từ mã nguồn và ứng dụng xây dựng hệ thống chấm bài tập lập trình" là công trình nghiên cứu của tôi dưới sự hướng dẫn của Thầy hướng dẫn, không sao chép lại của người khác. Trong toàn bộ nội dung luận văn, những điều được trình bày là của cá nhân tôi hoặc là được tổng hợp từ các nguồn tài liệu khác. Tất cả các nguồn tài liệu tham khảo đều có trích dẫn cụ thể và hợp pháp. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định của trường Đại học Công Nghệ - Đại học Quốc Gia Hà Nội cho lời cam đoan này. Hà Nội, ngày 26 tháng 03 năm 2019 Nguyễn Thị Khánh Chi vii DANH MỤC THUẬT NGỮ VIẾT TẮT STT Từ viết tắt Từ đầy đủ Ý nghĩa 1 AST Abstract Syntax Tree Cây cú pháp trừu tượng 2 CFG Control Flow Graph Đồ thị dòng điều khiển 3 EO Expected Output Giá trị đầu ra mong đợi 4 JDT Java Development Tooling 5 RO Real Output Giá trị đầu ra thực tế 6 SE Symbolic Excecution Thực thi tượng trưng 7 SMT-Solver Satisfiability Modulo Theories Solver 8 TC Test Case Ca kiểm thử viii DANH MỤC HÌNH VẼ Hình 2.1. Tổng quan quy trình kiểm thử dòng điều khiển ..............................................3 Hình 2.2. Mã nguồn hàm laNamNhuan...........................................................................5 Hình 2.3. Các thành phần cơ bản của đồ thị dòng điều khiển .........................................7 Hình 2.4. Các cấu trúc điều khiển cơ bản của đồ thị dòng điều khiển ............................ 7 Hình 2.5. Mã nguồn và CFG ứng với tiêu chí phủ câu lệnh hàm laNamNhuan .............8 Hình 2.6. Mã nguồn và CFG ứng với tiêu chí phủ điều kiện con hàm laNamNhuan .....9 Hình 2.7. Mã nguồn và CFG ứng với tiêu chí phủ câu lệnh hàm laNamNhuan ...........13 Hình 2.8. Mã nguồn và CFG ứng với tiêu chí phủ điều kiện con hàm laNamNhuan ...14 Hình 2.9. Mã nguồn và CFG ứng với tiêu chí phủ nhánh hàm giaithua .......................20 Hình 3.1. Biểu đồ ca sử dụng của hệ thống chấm bài lập trình. ....................................23 Hình 3.2. Kiến trúc tổng thể của hệ thống chấm bài lập trình.......................................27 Hình 3.3. Kiến trúc của mô-đun sinh ca kiểm thử tự động ...........................................28 Hình 3.4. Giao diện của công cụ sinh ca kiểm thử tự động ..........................................29 Hình 3.5. CFG ứng với tiêu chí phủ câu lệnh và phủ nhánh hàm laNamNhuan ...........30 Hình 3.6. CFG ứng với tiêu chí phủ điều kiện con hàm laNamNhuan ......................... 30 Hình 3.7. Chi tiết các đường kiểm thử cho tiêu chí phủ nhánh hàm laNamNhuan ......31 Hình 3.8. Chi tiết các ca kiểm thử cho tiêu chí phủ câu lệnh của hàm laNamNhuan ...32 Hình 3.9. Kết quả kiểm thử được xuất dưới dạng MS. Excel hàm laNamNhuan .........32 Hình 3.10. Mã nguồn chuẩn của hàm laNamNhuan .....................................................33 Hình 3.11. Chi tiết ca kiểm thử cho tiêu chí phủ điều kiện con ham laNamNhuan ......33 Hình 3.12. Mã nguồn hàm laNamNhuan1 của học sinh thứ nhất .................................34 Hình 3.13. Mã nguồn hàm laNamNhuan2 của học sinh thứ hai ...................................34 Hình 3.14. Mã nguồn chuẩn của hàm songay ............................................................... 36 Hình 3.15. Chi tiết ca kiểm thử cho tiêu chí phủ điều kiện con hàm songay ................36 Hình 3.16. Mã nguồn hàm songayhs_1 của học sinh thứ nhất ......................................37 Hình 3.17. Mã nguồn hàm songayhs_2 của học sinh thứ hai ........................................37 Hình 3.18. Mã nguồn chuẩn của hàm timuscln ............................................................. 40 Hình 3.19. Chi tiết các ca kiểm thử cho tiêu chí phủ nhánh hàm timuscln ...................40 ix Hình 3.20. Chi tiết các ca kiểm thử phủ tất cả các nhánh hàm timuscln .......................41 Hình 3.21. Mã nguồn hàm timuscnl_1 của học sinh thứ nhất .......................................41 Hình 3.22. Mã nguồn hàm timuscln_2 của học sinh thứ hai .........................................41 x DANH MỤC BẢNG Bảng 2.1. Các ca kiểm thử cho tiêu chí phủ câu lệnh của hàm laNamNhuan.................5 Bảng 2.2. Các trường hợp cần kiểm thử với tiêu chí phủ nhánh cho hàm laNamNhuan 5 Bảng 2.3. Các trường hợp cần kiểm thử với tiêu chí phủ điều kiện con của hàm laNamNhuan ....................................................................................................................6 Bảng 2.4. Các ca kiểm thử cho tiêu chí phủ điều kiện con hàm laNamNhuan ...............6 Bảng 2.5. Dữ liệu kiểm thử cho tiêu chí phủ điều kiện con hàm laNamNhuan ............16 Bảng 2.6. Các ca kiểm thử cho tiêu chí phủ câu lệnh hàm laNamNhuan .....................17 Bảng 2.7. Các ca kiểm thử giá trị biên cho hàm laNamNhuan .....................................18 Bảng 2.8. Các ca kiểm thử cho tiêu chí phủ nhánh hàm giaithua .................................20 Bảng 2.9. Các ca kiểm thử vòng lặp for hàm giaithua ..................................................21 Bảng 3.1. Danh sách tác nhân của hệ thống chấm bài lập trình. ...................................22 Bảng 3.2. Danh sách các ca sử dụng của hệ thống chấm bài lập trình. ......................... 23 Bảng 3.3. Kết quả kiểm thử bài tập kiểm tra năm nhuận của hai học sinh ...................34 Bảng 3.4. Các ca kiểm thử giá trị biên cho hàm laNamNhuan .....................................35 Bảng 3.5. Kết quả kiểm thử giá trị biên bài tập kiểm tra năm nhuận của hai học sinh .35 Bảng 3.6. Kết quả kiểm thử bài tập tính số ngày trong tháng của hai học sinh ............38 Bảng 3.7. Các ca kiểm thử giá trị biên cho hàm songay ...............................................39 Bảng 3.8. Kết quả kiểm thử giá trị biên bài tập tính số ngày trong tháng của hai học sinh.................................................................................................................................39 Bảng 3.9. Kết quả kiểm thử bài tập tìm ước số chung lớn nhất của hai học sinh .........42 Bảng 3.10. Các ca kiểm thử giá trị biên cho hàm timuscln ...........................................43 Bảng 3.11. Kết quả kiểm thử giá trị biên bài tập tìm uscln của hai của học sinh ........43 Bảng 3.12. Các ca kiểm thử vòng lặp while cho hàm timuscln ....................................44 Bảng 3.13. Kết quả kiểm thử vòng lặp while cho hàm tìm uscln của hai học sinh .......44 1 Chƣơng 1: Mở đầu Hiện nay, môn học lập trình đã được đưa vào giảng dạy ở các trường Trung học phổ thông (THPT) trên toàn quốc, giúp các em học sinh làm quen với công việc lập trình và làm quen dần với tư duy thiết kế các thuật toán. Ngôn ngữ lập trình được sử dụng để giảng dạy trong hầu hết các trường THPT là Pascal. Tuy nhiên, theo chương trình giáo dục THPT mới, trên cơ sở định hướng lập trình và tùy chọn ngôn ngữ, nhiều trường THPT đã bước đầu đưa các ngôn ngữ lập trình phổ biến như C, Java, v.v. vào giảng dạy. Trong quá trình giảng dạy, công việc chấm bài tập lập trình đối với người giáo viên thường diễn ra thủ công và tiềm ẩn nhiều sai sót. Do thời gian chấm bài có hạn nên việc không phát hiện ra các lỗi trong bài lập trình là không tránh khỏi. Điều này dẫn đến điểm chấm chưa thực sự chính xác và công bằng. Làm thế nào để công việc chấp bài lập trình được dễ dàng hơn với các giáo viên, cũng như đảm bảo tính chính xác, rút ngắn thời gian chấm bài là mục tiêu cần hướng tới. Đối với các bài tập lập trình, việc chấm bài chính là rà soát để phát hiện các lỗi có thể có trên mã nguồn của bài tập học sinh. Khi chương trình xuất hiện lỗi cú pháp, các lỗi sẽ được trình biên dịch phát hiện để người lập trình sửa lỗi. Tuy nhiên, ngay cả khi một chương trình không có lỗi cú pháp thì chương trình vẫn chưa chắc đã đúng vì lỗi có thể xảy ra trong quá trình thiết kế giải thuật. Làm thế nào để hỗ trợ giáo viên kiểm tra xem chương trình có thực hiện đúng với đặc tả yêu cầu của bài toán hay không, hoặc đúng bao nhiêu phần so với đặc tả của bài toán chính là mục tiêu của quá trình chấm bài. Hơn nữa, việc giáo viên cung cấp các cơ chế cho phép học sinh tự làm bài và tương tác qua các ứng dụng nhằm nâng cao khả năng tự học và tăng cường chất lượng là một xu hướng tất yếu trong hệ thống giáo dục thời gian tới. Vì vậy, nhu cầu về bài toán này càng cấp thiết hơn. Để giải quyết vấn đề này, ứng với mỗi bài toán, giáo viên phải sinh ra một bộ ca kiểm thử đủ tốt (có khả năng phát hiện tất cả các lỗi có thể có của bài lập trình của học sinh). Bộ ca kiểm thử này sau đó sẽ được sử dụng để chấm các chương trình cho học sinh nộp (tự động hoặc thủ công tùy thuộc vào phương pháp và công cụ mà giáo viên sử dụng). Hiện tại, việc sinh ra các bộ ca kiểm thử như vậy là vượt ngoài khả năng của các giáo viên Trung học phổ thông. Vì vậy, có một công cụ tự động hỗ trợ giáo viên giải quyết bài toán này là một vấn đề cấp thiết, có ý nghĩa thực tiễn cao. Một trong những giải pháp để giải quyết vấn đề này là sinh dữ liệu kiểm thử từ mã nguồn sử dụng phương pháp kiểm thử dòng dữ liệu [2, 3, 4, 8, 9, 11]. Trong phương pháp này, ứng với đặc tả của mỗi bài toán, thay vì yêu cầu giáo viên phải sinh bộ ca kiểm thử, họ sẽ phải cung cấp mã nguồn mẫu (mã nguồn của bài toán tương ứng mà không có lỗi). Phương pháp này sẽ tự động sinh các ca kiểm thử (bao gồm dữ liệu kiểm thử và giá trị đầu ra mong muốn tương ứng) từ mã nguồn được giáo viên cung cấp. Sau khi 2 hoàn tất quá trình này, giáo viên sẽ có một bộ dữ liệu kiểm thử bao quát hết các nhánh của mã nguồn. Tuy nhiên, phương pháp này [2, 3] chỉ cho phép phát hiện những lỗi tiềm ẩn trong mã nguồn (có đặc tả và được lập trình hoặc không có đặc tả và được lập trình). Phương pháp này không kiểm tra được các lỗi ứng với tình huống có đặc tả và không được lập trình (thường được phát hiện bởi các phương pháp kiểm thử hộp đen). Phương pháp đề xuất trong [2] mới sinh được các dữ liệu kiểm thử, chưa sinh được đầu ra mong muốn, do đó không hỗ trợ được giáo viên trong việc sinh các ca kiểm thử mẫu. Trong [3] đã sinh được các ca kiểm thử cho mã nguồn Java nhưng chưa hỗ trợ xây dựng hệ thống chấm bài. Mục tiêu của luận văn này là hướng đến nghiên cứu giải pháp và xây dựng bộ công cụ hỗ trợ giáo viên chấm bài lập trình một cách tự động nhằm giải quyết các vấn đề như mô tả ở trên. Mấu chốt của giải pháp này là phương pháp sinh dữ liệu kiểm thử từ mã nguồn. Bản chất của các phương pháp này là phụ thuộc vào ngôn ngữ lập trình được sử dụng (mỗi ngôn ngữ lập trình thường có kỹ thuật sinh dữ liệu kiểm thử khác nhau vì chúng ta cần phải phân tích mã nguồn). Mặc dù ngôn ngữ lập trình được dùng phổ biến nhất trong các trường Trung học phổ thông là Pascal nhưng ngôn ngữ này chưa có công cụ phân tích cây cú pháp (nền tảng cho việc xây dựng đồ thị dòng điều khiển). Vì vậy, phương pháp sinh dữ liệu kiểm thử từ mã nguồn Pascal rất khó thực hiện trong luận văn này. Ngôn ngữ C/C++ đã được quan tâm nghiên cứu với giải pháp khá tốt trong [2]. Vì vậy, luận văn này tập trung nghiên cứu giải pháp cho ngôn ngữ Java. Trong [3] đã nghiên cứu giải pháp tương tự cho Java nhưng chỉ dừng lại với các đơn vị chương trình (hàm, phương thức). Phương pháp này có thể sử dụng khi chương trình được viết bằng phương pháp hướng đối tượng. Tuy nhiên, học sinh tại các trường Trung học phổ thông thường viết chương trình theo phương pháp hướng cấu trúc nên giải pháp này không sử dụng được. Cùng với phương pháp này, luận văn cũng sẽ nghiên cứu các kỹ thuật kiểm thử hộp đen nhằm sinh bổ sung các ca kiểm thử cho phương pháp trên. Một công cụ hỗ trợ cũng sẽ được phát triển và thực nghiệm với một số chương trình đơn giản ở bậc Trung học phổ thông nhằm minh chứng cho kết quả của luận văn. Phần còn lại của đề tài nghiên cứu sẽ gồm những nội dung sau. Chương 2 trình bày tổng quan phương pháp sinh dữ liệu kiểm thử dòng điều khiển từ mã nguồn. Đây là phương pháp chung, có thể áp dụng cho nhiều ngôn ngữ lập trình khác nhau, trong chương này cũng đề xuất phương pháp phân tích mã nguồn Java nhằm sinh ca kiểm thử cho các hàm Java. Chương 3 giới thiệu công cụ hỗ trợ sinh ca kiểm thử tự động và kết quả thực nghiệm bằng cách áp dụng công cụ, cài đặt với một số chương trình đơn giản. Cuối cùng, kết luận và các hướng nghiên cứu của luận văn sẽ được mô tả trong Chương 4. 3 Chƣơng 2: Phƣơng pháp sinh dữ liệu kiểm thử dòng điều khiển Chương này trình bày tổng quan về phương pháp kiểm thử dòng điều khiển từ đồ thị dòng điều khiển (Control Flow Graph - CFG) của chương trình nhằm sinh ca kiểm thử cho mã nguồn ứng với tiêu chí kiểm thử yêu cầu. Phương pháp trình bày trong chương này có thể áp dụng cho hầu hết các ngôn ngữ lập trình. 2.1 Tổng quan về kiểm thử dòng điều khiển Kiểm thử dòng điều khiển là phương pháp kiểm thử hộp trắng nhằm phát hiện các lỗi tiềm ẩn xảy ra trên mã nguồn [1, 6]. Phương pháp này dựa vào việc phân tích mã nguồn nhằm xây dựng đồ thị dòng điều khiển ứng với các tiêu chí kiểm thử cho trước. Dựa vào đồ thị này, một bộ dữ liệu kiểm thử sẽ được sinh ra đáp ứng 100% tiêu chí kiểm thử yêu cầu. Người sử dụng sẽ sử dụng đặc tả của bài toán để sinh ra các ca kiểm thử từ bộ dữ liệu kiểm thử đã được sinh ra. Bộ ca kiểm thử này sau đó sẽ được sử dụng để làm bộ kiểm thử mẫu thực hiện kiểm thử trên bài tập lập trình của học sinh phục vụ cho quá trình chấm bài. Mã nguồn Xây dựng CFG Tiêu chí kiểm thử Sinh đường đi kiểm thử Sinh dữ liệu kiểm thử Sinh đầu ra mong muốn Thực thi ca kiểm thử Báo cáo kiểm thử Hình 2.1. Tổng quan quy trình kiểm thử dòng điều khiển 4 Quy trình kiểm thử dòng điều khiển của một hàm được mô tả như Hình 2.1. Đầu vào của quy trình là mã nguồn và tiêu chí kiểm thử yêu cầu. Đầu ra của quy trình là báo cáo kiểm thử chứa các kết quả kiểm thử (ca kiểm thử nào phát hiện được lỗi và ca kiểm thử nào không phát hiện được lỗi). Chi tiết phương pháp bao gồm các bước sau: - Bước 1: Sinh đồ thị dòng điều khiển. Mã nguồn được phân tích dựa trên các tiêu chí kiểm thử để xây dựng đồ thị dòng điều khiển. Với mỗi tiêu chí kiểm thử là phủ câu lệnh, phủ nhánh và phủ điều kiện con, sẽ có một đồ thị dòng điều khiển tương ứng. - Bước 2: Sinh các đường đi kiểm thử. Từ đồ thị dòng điều khiển, luận văn đề xuất thuật toán duyệt đồ thị sao cho các đường đi kiểm thử được sinh ra đạt độ phủ thỏa mãn các tiêu chí đã đề ra. - Bước 3: Sinh ca kiểm thử. Ca kiểm thử bao gồm bộ giá trị đầu vào được chọn để thực hiện kiểm thử trên mỗi đường đi và giá trị đầu ra mong muốn tương ứng (Expected Output – EO). Ca kiểm thử được sinh ra bằng cách các hệ ràng buộc trên mỗi đường kiểm thử. Giá trị đầu ra mong muốn được sinh từ đặc tả bài toán. Kết thúc bước này, một tập các ca kiểm thử được sinh ra. - Bước 4: Thực thi các ca kiểm thử. Thực thi các ca kiểm thử nhằm tạo ra báo cáo kiểm thử trong đó chỉ ra ca kiểm thử nào phát hiện được lỗi, ca kiểm thử nào không phát hiện được lỗi. 2.2 Các tiêu chí kiểm thử Tiêu chí kiểm thử là chuẩn mực để đánh giá độ bao phủ của một tập ca kiểm thử so với mã nguồn. Nhằm tối ưu các ca kiểm thử, tiêu chí kiểm thử được đưa ra để thiết kế các ca kiểm thử sao cho số ca kiểm thử là ít nhất những vẫn có thể kiểm tra được tối đa các trường hợp (có thể mắc lỗi) xảy ra trên mã nguồn. Các thành phần cần kiểm tra bao gồm câu lệnh, các đỉnh quyết định, các điều kiện con, đường thi thành hoặc sự kết hợp giữa chúng [1]. Có rất nhiều tiêu chí kiểm thử được áp dụng trong thực tế, dưới đây là ba tiêu chí kiếm thử đang được sử dụng rộng rãi [1, 2]: - Phủ câu lệnh: Sau khi thực hiện các ca kiểm thử, mỗi dòng lệnh trên mã nguồn phải được duyệt qua ít nhất một lần. Giả sử, ta cần sinh các ca kiểm thử cho hàm laNamNhuan có mã nguồn được hiển thị ở Hình 2.2. Để đạt được 100% tiêu chí phủ câu lệnh cho hàm, ta cần thực hiện ba ca kiểm thử như Bảng 2.1. Giá trị EO (Expected Output) trên bảng là giá trị đầu ra mong muốn khi chạy ca kiểm thử, RO (Real Output) là giá trị đầu ra thực tế (giá trị này sẽ được điền khi chạy các ca kiểm thử trong môi trường thực). 5 public int laNamNhuan(int year) { if(year<0) return -1; if((year%400==0)||((year%4==0)&&(year%100!=0))) return 1; else return 0; } Hình 2.2. Mã nguồn hàm laNamNhuan Bảng 2.1. Các ca kiểm thử cho tiêu chí phủ câu lệnh của hàm laNamNhuan STT Tc1 Tc2 Tc3 - Input -2000 2000 2001 EO -1 1 0 RO Phủ nhánh: Sau khi thực hiện ca kiểm thử, các điểm quyết định trên mã nguồn được duyệt theo cả hai nhánh đúng và sai. Ví dụ, với hàm laNamNhuan, để đạt được 100% tiêu chí phủ nhánh, ta cần thực hiện các ca kiểm thử để kiểm tra các điều kiện như Bảng 2.2 để các điểm quyết định ở câu lệnh 1 và câu lệnh 3 được duyệt qua cả hai nhánh đúng và sai. Bảng 2.2. Các trƣờng hợp cần kiểm thử với tiêu chí phủ nhánh cho hàm laNamNhuan Điểm quyết định 1 3 Điều kiện Đúng Sai Year <0 Tc1 Tc2 (year%400==0)||((year%4==0)&&(year %100!=0)) Tc2 Tc3 Hàm laNamNhuan là một trường hợp đặc biệt, ba ca kiểm thử thỏa mãn tiêu chí phủ câu lệnh cũng đồng thời thỏa mãn tiêu chí phủ nhánh. Trong nhiều trường hợp khác, số ca kiểm thử ứng với tiêu chí phủ nhánh thường nhiều hơn số ca kiểm thử của tiêu chí phủ câu lệnh do các ca kiểm thử của tiêu chí phủ câu lệnh không phủ được hết các nhánh đúng và sai trên mã nguồn. - Phủ điều kiện con: Với các điểm quyết định có chứa điều kiện phức hợp (từ hai điều kiện con trở lên), sau khi thực hiện các ca kiểm thử, tất cả các điều kiện con đều được duyệt qua cả hai nhánh đúng và sai. Ví dụ, trong câu lệnh 3 của hàm laNamNhuan có chứa điều kiện phức hợp là (year%400==0)|| ((year%4==0)&&(year%100!=0)). Nếu chỉ thực hiện kiểm thử với tiêu chí phủ 6 nhánh thì chỉ có điều kiện (year%400==0)được kiểm tra, còn hai điều kiện con (year%4==0) và (year%100!=0) thì chưa được kiểm tra tới. Chúng ta cần phải kiểm tra tất cả các nhánh trên các điều kiện trên mã nguồn thì mới đạt được tiêu chí phủ điều kiện con. Bảng 2.3 là các trường hợp cần kiểm tra để mọi điều kiện con trên hàm laNamNhuan đều được "ghé thăm". Bảng 2.3. Các trƣờng hợp cần kiểm thử với tiêu chí phủ điều kiện con của hàm laNamNhuan Đỉnh quyết định 1 3 3 3 3 Điều kiện Đúng Sai Year<0 Tc1 Tc2 ? ? ? Tc2 Tc3 ? ? ? year%400==0 (Year%4==0)&&(year%100!=0) year%4==0 year%100!=0 Rõ ràng, các ca kiểm thử ứng với tiêu chí phủ nhánh chỉ kiểm thử được 3/6 ca kiểm thử (tương ứng với độ phủ đạt 50%) của tiêu chí phủ điều kiện con. Để kiểm tra tất cả các điểm quyết định cho hàm laNamNhuan, ta cần thực hiện sáu ca kiểm thử như Bảng 2.4. Bảng 2.4. Các ca kiểm thử cho tiêu chí phủ điều kiện con của hàm laNamNhuan STT Input EO Tc1 Tc2 Tc3 Tc4 Tc5 Tc6 -1 2000 1996 1997 1900 2200 -1 1 1 0 0 0 RO 2.3 Xây dựng đồ thị dòng điều khiển Đồ thị dòng điều khiển (CFG) là một phần rất quan trọng trong phương pháp kiểm thử dòng điều khiển. CFG mô tả cấu trúc của mã nguồn thông qua một đồ thị có hướng với mỗi đỉnh tương ứng là một câu lệnh/nhóm lệnh. CFG cho người dùng quan sát một cách trực quan các luồng điều khiển của mã nguồn. Từ đó, chúng ta dễ dàng thiết kế các ca kiểm thử sao cho nó phủ hết các nhánh trên đồ thị này. Để xây dựng được CFG từ mã nguồn, ta quy ước mỗi câu lệnh/ nhóm lệnh trên mã nguồn tương ứng là một đỉnh của đồ thị. Nếu một câu lệnh j thực hiện ngay sau câu 7 lệnh i thì sẽ tồn tại một đường đi từ đỉnh i đến đỉnh j. Mỗi tiêu chí kiểm thử, chúng ta xây dựng được một CFG tương ứng [1]. Một CFG được xây dựng từ đỉnh bắt đầu (ứng lời khai báo hàm), đi qua các đỉnh (các câu lệnh khai báo, câu lệnh gán, câu lệnh điều kiện, câu lệnh lặp, các khối xử lý...) theo thứ tự thực hiện trên mã nguồn và đi đến đỉnh kết thúc (ứng với điểm kết thúc hàm). Các thành phần để xây dựng CFG được mô tả ở Hình 2.3. [1] Đỉnh bắt đầu Đỉnh xử lý Đỉnh quyết định Đỉnh kết thúc Đỉnh nối Hình 2.3. Các thành phần cơ bản của đồ thị dòng điều khiển Ngoài đỉnh bắt đầu và đỉnh kết thúc, mỗi đỉnh là duy nhất trong đồ thị, các đỉnh khác trong đồ thị tương ứng với một câu lệnh của mã nguồn, được đặt tên theo chức năng của câu lệnh. Đỉnh xử lý ứng với câu lệnh khai báo, gán giá trị hoặc các câu lệnh tính toán. Đỉnh quyết định ứng với câu lệnh rẽ nhánh hoặc biểu thức điều kiện trong câu lệnh lặp. Đỉnh nối là đỉnh tiếp theo được thực hiện ngay sau khi câu lệnh rẽ nhánh hoặc lặp kết thúc [1, 2, 6]. Trong Java, các cấu trúc điều khiển bao gồm: cấu trúc tuần tự, cấu trúc rẽ nhánh if…else, cấu trúc rẽ nhánh switch...case, các cấu trúc lặp while...do, do...while. Riêng vòng lặp for, chúng ta sử dụng cấu trúc while...do để thay thế (vì for là một trường hợp đặc biệt của while...do với số lần lặp biết trước). Các ký hiệu đại diện cho mỗi cấu trúc điều khiển được minh họa trên Hình 2.4 [1, 2]. Chúng ta sẽ sử dụng các thành phần và cấu trúc ở Hình 2.3, Hình 2.4 cùng với các tiêu chí kiểm thử để xây dựng đồ thị dòng điều khiển cho mã nguồn. C Cấu trúc tuần tự Cấu trúc if…esle C Cấu trúc while...do C C Cấu trúc do...while Cấu trúc switch…case Hình 2.4. Các cấu trúc điều khiển cơ bản của đồ thị dòng điều khiển