Luận văn 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

áp trừu tượng để phục vụ cho việc phân tích và quản lý. 2.3.3.1 Phân tích mã nguồn Cây cú pháp trừu tượng (AST) là một cấu trúc mô tả mối quan hệ giữa các thành phần trên mã nguồn. Trên cây AST, một lớp (class) bao gồm các thành phần như sau: - Định nghĩa lớp: Là nút bao gồm các nút con về phạm vi truy cập (public, private, v.v.), tên lớp và thân lớp. Phần thân lớp gồm các nút khai báo thuộc tính và các nút định nghĩa hành vi (phương thức). - Khai báo biến: Mỗi nút là một thuộc tính của lớp với các nút con về phạm vi truy cập (public, private, v.v.), kiểudữ liệu và danh sách tên biến. Ví dụ: câu lệnh “private int a, b=10;” bao gồm các thông tin về phạm vi truy cập private, kiểu dữ liệu int, danh sách các biến là a và b=10. - Định nghĩa phương thức: là một cây AST con bao gồm các thành phần: định nghĩa phương thức, khai báo hằng số, biến toàn cục/cục bộ, struct, các câu lệnh trong thân hàm, v.v. được thể hiện theo quan hệ cha - con. Mỗi AST của một phương thức sẽ có cấu trúc như sau: o Tên phương thức: Tên được sử dụng để tìm kiếm một phương thức khi nó được gọi (invoke) trong một câu lệnh ở thân một phương thức khác. o Kiểu trả về: Được sử dụng để sinh loại dữ liệu đầu ra. o Danh sách đối số: Dùng để xác định chính xác phương thức cần gọi tới trong trường hợp có nhiều hàm trùng tên. o Phần thân phương thức: là một cây AST con tương ứng với từng câu lệnh và các biểu thức tương ứng trên trong. 11 2.3.3.2 Xây dựng CFG từ cây cấu trúc trừu tƣợng. Từ cấu trúc cây AST, chúng ta sử dụng một thuật toán để biến đổi cây AST sang dạng đồ thị dòng điều khiển, được mô tả ở Thuật toán 2.1. Thuật toán 2.1: Sinh_G(AST, t) Đầu vào: AST: cây AST môt tả cấu trúc của hàm cần kiểm thử; t: tiêu chí kiểm thử Đầu ra: G: đồ thị dòng điều khiển ứng với độ phủ t, G là biến toàn cục được khởi tạo là rỗng 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: for (mỗi nút c trên cây AST) if (c là đỉnh quyết định) node := đỉnh đại diện cho c Cập nhật node vào G Liên kết node với các đỉnh của G T_AST := các đỉnh thuộc cây AST theo nhánh đúng Sinh_G(T_AST, t) F_AST :=các đỉnh thuộc cây AST theo nhánh sai Sinh_G(F_ AST, t) elseif(c là các câu lệnh break, continue, return, goto ...) N_ AST := đỉnh liên kết tiếp theo sau c thuộc cây AST Sinh_G(N_ AST, t) elseif (c là nhóm lệnh) c_AST :=cây AST của nhóm lệnh c Sinh_G(c, t) else node := đỉnh đại diện cho c cập nhật node vào G Liên kết node với các đỉnh của G endif endfor L L 12 Đầu vào của thuật toán là cây AST môt tả cấu trúc mã nguồn và tiêu chí kiểm thử t. Đầu ra của thuật toán là một đồ thị G mô tả dòng điều khiển của mã nguồn. Đầu tiên, với từng nút c của cây AST được duyệt theo thứ tự top-down (dòng 1). Nếu nút c là đỉnh quyết định (dòng 2) (ifelse, for, dowhile, v.v.) thì tạo một node mới của G tương ứng với nút c trên cây AST và cập nhật node vào G (dòng 3, 4). Tiếp theo, liên kết node với các đỉnh khác trong đồ thị G (dòng 5). Sau đó, gọi đệ quy (dòng 7, 9) cây AST là T_AST và F_AST của các khối lệnh ứng với nhánh đúng vào nhánh sai (dòng 6, 8). Nếu c là các từ khóa (return, break, continue, ) thì cây AST N_AST được gọi đệ quy (dòng 11, 12). Còn nếu c là một khối các câu lệnh thì cây AST c_AST của c được gọi đệ quy (dòng 14, 15). Nếu c là câu lệnh gán hoặc khai báo thì thì một đỉnh node mới của G được khởi tạo đại diện cho c và thêm các liên kết với các đỉnh khác trong đồ thị (dòng 17, 18, 19). Thuật toán kết thúc khi nút cuối cùng của cây AST được duyệt, ta dựng được đồ thị G mô tả cấu trúc điều khiển của mã nguồn Java. 2.4 Sinh đƣờng đi kiểm thử từ đồ thị Đường đi xuất phát từ đỉnh bắt đầu của CFG, đi qua các đỉnh trong đồ thị theo thứ tự thực hiện câu lệnh đến đỉnh kết thúc được gọi là một đường đi độc lập. Một tập đường đi độc lập trên đồ thị thỏa mãn các tiêu chí kiểm thử gọi là tập đường kiểm thử. Mục tiêu của quá trình sinh các đường kiểm thử là tìm được số đường kiểm thử ít nhất nhưng đạt được độ phủ tối đa trên đồ thị. Trên mỗi CFG, tập đường kiểm thử được xác định sao cho nó phủ hết các nhánh của đồ thị. Theo [7], số đường đi của chương trình ứng với đồ thị dòng điều khiển của nó được tính bằng số đỉnh quyết định của CFG tương ứng cộng 1 hoặc bằng số cạnh trừ số đỉnh của CFG tương ứng cộng 2. 2.4.1 Sinh đƣờng đi thỏa mãn tiêu chí phủ câu lệnh Để sinh các đường kiểm thử thỏa mãn tiêu chí phủ câu lệnh từ CFG tương ứng, chúng ta tìm các đường đi sao cho mỗi đỉnh được "ghé thăm" ít nhất một lần (đồng nghĩa với mỗi câu lệnh được duyệt qua ít nhất một lần). Ví dụ, ta cần sinh đường kiểm thử thỏa mãn tiêu chí phủ câu lệnh cho hàm laNamNhuan có CFG được hiển thị ở Hình 2.7. Trên đồ thị, ta xác định được ba đường đi để mỗi đỉnh của đồ thị được đi qua ít nhất một lần, các đường được liệt kê như sau: p1: 1(T), 2 p2: 1(F), 3(T), 4 p3: 1(F), 3(F), 5 13 Hình 2.7. Mã nguồn và CFG ứng với tiêu chí phủ câu lệnh của hàm laNamNhuan Rõ ràng, tất cả các đỉnh (tương ứng với câu lệnh từ 1 đến 5) đều xuất hiện trên tập đường đi này, nên đây chính là tập đường kiểm thử thỏa mãn tiêu chí phủ câu lệnh. 2.4.2 Sinh đƣờng đi thỏa mãn tiêu chí phủ nhánh Sinh các đường kiểm thử thỏa mãn tiêu chí phủ nhánh từ CFG là tìm tập đường đi sao cho các đỉnh quyết định trên CFG đều được duyệt qua cả hai nhánh đúng và sai. Ví dụ, CFG của hàm laNamNhuan ở Hình 2.7 có hai đỉnh quyết định là đỉnh 1 và đỉnh 3. Để đạt được tiêu chí phủ nhánh chúng ta cần 2+1=3 đường đi. Thứ tự các đường đi như sau: p1: 1(T), 2 p2: 1(F), 3(T), 4 p3: 1(F), 3(F), 5 Ta thấy, các đường đi này đều đi qua hai nhánh của đỉnh 1 và đỉnh 3. Vậy đây chính là tập đường đi kiểm thử thỏa mãn tiêu chí phủ nhánh của hàm laNamNhuan. 2.4.3 Sinh đƣờng đi thỏa mãn tiêu chí phủ điều kiện con Với CFG của tiêu chí phủ điều kiện con, đường kiểm thử sẽ được xác định sao cho nó phủ hết các nhánh của mọi đỉnh quyết định trên đồ thị. Ví dụ, trên CFG ứng với tiêu chí phủ điều kiện con của hàm laNamNhuan mô tả Hình 2.8 có 4 đỉnh quyết định là 1, 3a, 3b, 3c nên ta cần 4+1=5 đường đi để đạt 100% tiêu chí phủ điều kiện con. Các đường đi được liệt kê như sau: p1: 1(T), 2 p2: 1(F), 3a(T), 4 p3: 1(F), 3a(F), 3b(T), 3c(T), 4 p4: 1(F), 3a(F), 3b(T), 3c(F), 5 p5: 1(F), 3a(F), 3b(F), 5 public int laNamNhuan(int year) { 1. if(year<0) 2. return -1; 3. if((year%400==0)||((year%4==0)&&(year%100!=0))) 4. return 1; else 5. return 0; } 3 2 5 4 1 F T T a) b) 14 Hình 2.8. Mã nguồn và CFG ứng với tiêu chí phủ điều kiện con của hàm laNamNhuan Tập các đường đi từ p1 đến p5 đều đã đi qua cả hai nhánh đúng và sai của các đỉnh quyết định 1, 3a, 3b, 3c nên đây chính là tập đường đi kiểm thử thỏa mãn tiêu chí phủ điều kiện con của hàm laNamNhuan. 2.4.4 Phƣơng pháp sinh đƣờng đi kiểm thử trên đồ thị Từ CFG đã xây dựng được ở Thuật toán 2.1, luận văn tiến hành nghiên cứu phương pháp sinh tập các đường kiểm thử trên đồ thị của mã nguồn Java trong môi trường thực dựa vào phương pháp sinh đường kiểm thử của Mc-Cabe đề xuất trong [7]. Ý tưởng của phương pháp là tìm đường đi ngắn nhất trên CFG bằng các duyệt đồ thị theo nhánh fasle tại các đỉnh quyết định. Sau đó thay đổi đỉnh xuất phát và tìm đường đi ngắn nhất tiếp theo. Từng đường đi sẽ được đưa vào tập đường kiểm thử cho đến khi nó phủ hết toàn bộ các nhánh trên đồ thị. Thuật toán sinh đường kiểm thử dựa trên phương pháp nghiên cứu được mô tả ở Thuật toán 2.2. Đầu vào của thuật toán là một đồ thị dòng điều khiển G mô tả cấu trúc của hàm cần kiểm thử. Đầu ra của thuật toán là tập các đường kiểm thử trên đồ thị G. Đầu tiên, khởi tạo biến Path để lưu các đường kiểm thử trên đồ thị (dòng 1). Duyệt đồ thị theo nhánh false qua các đỉnh quyết định của đồ thị và lưu vào tập Path (dòng 2, 3). Tiếp theo, gọi P là tập các đỉnh quyết định trên đường kiểm thử Path và Visited là tập các đỉnh quyết định đã được duyệt theo cả hai nhánh (dòng 4,5). Với các đỉnh quyết định thuộc P (dòng 6), từ một đỉnh u bất kỳ trên P và đỉnh v liền kề với u sao cho cạnh (u,v) chưa có trong Path (dòng 7,8), ta tìm đường đi ngắn nhất qua (u,v) và cập nhật vào tập đường kiểm thử Path (dòng 9, 10) ta được đường kiểm thử mới là d. Bổ sung các đỉnh quyết định trên d vào P (dòng 11). Cuối cùng, giải phóng đỉnh u khỏi tập P và đánh dấu là đỉnh u đã được duyệt qua cả hai nhánh (dòng 12,13). Lặp lại quá trình đến khi các đỉnh quyết định thuộc P được duyệt hết. Thuật toán kết thúc khi chúng ta thu được tập đường kiểm thử Path trên đồ thị G. public int laNamNhuan(int year) { 1. if(year<0) 2. return -1; if((year%400==0)||((year%4==0)&&(year%100!=0))) 3a 3b 3c 4. return 1; else 5. return 0; } 3c 5 2 1 4 F 3a T T 3b F T T F b) a) 15 Thuật toán 2.2: Sinh_Path(G) Đầu vào: G: đồ thị dòng điều khiển Đầu ra: Path: tập các đường đi độc lập của đồ thị G 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: Path := Ø shortestPath := đường đi qua các nhánh false của G Cập nhật shortestPath vào Path P := tập các điểm quyết định thuộc shortestPath Visited := Ø tập các điểm quyết định đã được ghé thăm while (P != Ø) do u := một đỉnh quyết định thuộc P v := đỉnh liền kề với u sao cho cạnh (u,v) chưa có trong Path d := đường đi ngắn nhất qua (u, v) Bổ dung các đỉnh quyết định thuộc d vào P Loại bỏ đỉnh u khỏi tập P Bổ sung đỉnh u vào tập Visited end while 2.5 Sinh ca kiểm thử từ đƣờng đi Để kiểm tra sự đúng đắn của các đường kiểm thử trên đồ thị, chúng ta tiến hành thực hiện ca kiểm thử trên mỗi đường đi bằng cách sinh các dữ liệu kiểm thử và phân tích mã nguồn để có được giá trị đầu ra mong muốn (EO). Nếu sau khi thực hiện các ca kiểm thử trong môi trường thực, giá trị đầu ra thực tế (RO) trùng với giá trị đầu ra mong muốn thì ca kiểm thử ứng với đường đi là thực hiện được. Ngược lại, ca kiểm thử ứng với đường đi là có lỗi (fail), đường kiểm thử là không thực hiện được hoặc là một phần của đường đi khác. Dữ liệu kiểm thử được sinh ra dựa vào việc giải hệ ràng buộc bằng công cụ SMT-Solver như được mô tả chi tiết trong [5]. 2.5.1 Sinh dữ liệu kiểm thử Dữ liệu kiểm thử là bộ giá trị đầu vào được chọn để thực thi ca kiểm thử trên đường đi. Với mỗi đường kiểm thử, để sinh bộ dữ liệu kiểm thử tương ứng, chúng ta sẽ giải hệ ràng buộc với các biến là tham số của đối tượng cần kiểm thử sao cho giá trị các biến thỏa mãn các điều kiện trên đường đi. Ví dụ, để sinh dữ liệu kiểm thử cho tập đường kiểm thử ứng với tiêu chi phủ điều kiện con của hàm laNamNhuan đã tìm được ở Mục 2.4.3, liệt kê như dưới đây, ta sẽ 16 phân tích và giải các hệ ràng buộc trên mỗi đường đi sao cho điều kiện tại các điểm quyết định được thỏa mãn. Bảng 2.5 là dữ liệu kiểm thử cho mỗi đường đi. p1: 1(T), 2 p2: 1(F), 3a(T), 4 p3: 1(F), 3a(F), 3b(T), 3c(T), 4 p4: 1(F), 3a(F), 3b(T), 3c(F), 5 p5: 1(F), 3a(F), 3b(F), 5 - Xét đường đi p1: 1(T), 2. Để đường đi này được thi hành thì nghiệm của hệ ràng buộc ứng với đường đi này là các giá trị nguyên sao cho điều kiện tại đỉnh quyết định 1 (year<0) là đúng. Giả sử ta chọn giá trị year = - 1 làm dữ liệu kiểm thử của đường đi này. - Xét đường đi p2: 1(F), 3a(T), 4. Để đường đi này được thi hành thì nghiệm của hệ ràng buộc ứng với đường đi này là các giá trị nguyên thỏa mãn điều kiện tại đỉnh quyết định 1(year<0) là sai và điều kiện tại đỉnh quyết định 3a - (year%400==0) là đúng. Giả sử ta chọn giá trị year = 2000 làm dữ liệu kiểm thử của đường đi này. - Xét đường đi p3: 1(F), 3a(F), 3b(T), 3c(T),4. tương tự với cách làm trên ta chọn year =1996 để các điều kiện tại đỉnh quyết định 1 và 3a là sai; điều kiện tại đỉnh 3b (year%4==0) và điều kiện tại đỉnh 3c (year%100!=0) là đúng. Giả sử ta chọn year = 1996 làm dữ liệu kiểm thử của đường đi này. - Tương tự, với đường đi p4: 1(F), 3a(F), 3b(T), 3c(F), 5. Ta chọn giá trị year = 1200 làm dữ liệu kiểm thử để điều kiện tại đỉnh 3b (year%4==0) là đúng và điều kiện tại các đỉnh 1, 3a, 3c là sai. - Cuối cùng, với đường đi p5: 1(F), 3a(F), 3b(F), 5. Để đường đi được thi hành thì nghiệm của hệ ràng buộc ứng với đường đi này là giá trị nguyên sao cho điều kiện tại các đỉnh đỉnh 1, 3a, 3b là sai. Ta chọn giá trị year = 2001 làm dữ liệu kiểm thử. Bảng 2.5. Dữ liệu kiểm thử cho tiêu chí phủ điều kiện con của hàm laNamNhuan STT Path Input EO RO Tc1 1(T), 2 -1 Tc2 1(F), 3a(T), 4 2000 Tc3 1(F), 3a(F), 3b(T), 3c(T), 4 1996 Tc4 1(F), 3a(F), 3b(T), 3c(F), 5 1200 Tc5 1(F), 3a(F), 3b(F), 5 2001 17 2.5.2 Sinh đầu ra mong muốn Đầu ra mong muốn (Expected Output - EO) của ca kiểm thử là giá trị đầu ra mà ta mong muốn của ca kiểm thử sau khi ca kiểm thử được thực thi. Với các phương pháp hiện tại, dựa trên đặc tả của bài toán, chúng ta phân tích giá trị đầu vào ứng với đường thi hành để xác định giá trị đầu ra mon muốn. Quá trình này thường được tiến hành thủ công và rất khó tự động hóa. Tuy nhiên, trong luận văn này, giá trị đầu ra mong muốn chính là giá trị thực tế có được ứng với đầu vào tương ứng vì mã nguồn do giáo viên cung cấp là mã nguồn chuẩn (không có lỗi). Vì vậy, chúng ta dễ dàng tự động hóa việc sinh giá trị đầu ra mong muốn. Ví dụ, ta để tim đầu ra mong muốn cho các ca kiểm thử của hàm laNamNhuan ở bảng 2.5. Khi chạy các ca kiểm thử với các giá trị đầu vào là mã nguồn chuẩn, ta được kết quả đầu ra mong muốn, được ghi lại trên Bảng 2.6 Bảng 2.6. Các ca kiểm thử cho tiêu chí phủ câu lệnh của hàm laNamNhuan 2.6 Sinh các ca kiểm thử giá trị biên và vòng lặp Các ca kiểm thử ứng với ba tiêu chí kiểm thử là phủ câu lệnh, phủ nhánh, phủ điều kiện con đã đảm bảo phủ được tất cả các nhánh trên CFG. Tuy nhiên, các ca kiểm thử này lại không kiểm tra được các lỗi ứng với các tình huống có đặc tả và không được lập trình (thương được phát hiện bởi phương pháp kiểm thử hộp đen). Chẳng hạn, trong khi lập trình, các học sinh thường viết sai câu lệnh điều kiện hoặc không viết câu lệnh kiểm tra các giá trị biên, chính vì vậy, để có một bộ dữ liệu kiểm thử đủ tốt, chúng ta cần thiết kế thêm các ca kiểm thử để kiểm thử các giá trị biên của hàm. Thêm nữa, với mã nguồn có chứa vòng lặp, cho dù đã có được các ca kiểm thử thỏa mãn các tiêu chí phủ, thì lỗi vẫn có thể xảy ra bên trong vòng lặp. Nguyên nhân là do, các đường đi ứng với các tiêu chí kiểm thử chỉ đi qua vòng lặp một lần nên không thể phát hiện và kiểm soát hết các lỗi khi vòng lặp thực thi nhiều lần. Chính vì vậy, với những hàm có chứa vòng lặp, chúng ta cần sinh thêm các ca kiểm thử cho vòng lặp nhằm phát hiện lỗi. STT Path Input EO RO Tc1 1(T),2 -1 -1 Tc2 1(F), 3a(T), 4 2000 1 Tc3 1(F), 3a(F),3b(T),3c(T),4 1996 1 Tc4 1(F), 3a(F),3b(T),3c(F),5 1200 0 Tc5 1(F), 3a(F),3b(F),5 2001 0 18 2.6.1 Sinh ca kiểm thử giá trị biên Kiểm thử giá trị biên (boundary value testing) là một kỹ thuật kiểm thử hướng kiểm thử chức năng (kiểm thử hộp đen) [1]. Phương pháp này nhằm kiểm tra các lỗi xảy ra ở giá trị biên và cận biên của các biến. Các lỗi này thường do người lập trình không kiểm tra giá trị đầu vào hợp lệ hoặc viết sai biểu thức điều kiện. Dựa vào miền xác định của biến đầu vào và miền giá trị của biến đầu ra, người kiểm thử thiết kế các ca kiểm thử với dữ liệu kiểm thử là các giá trị biên và cận biên của các giá trị này. Thông thường, chúng ta thường lấy năm giá trị cận với các biên trong miền giá trị là: min, max, min+, max- và một giá trị thông thường nom ở giữa miền xác định để thực hiện kiểm thử [1]. Trong nhiều trường hợp, để tăng khả năng phát hiện lỗi (kiểm thử biên mạnh), người ta cũng có thể lấy thêm các giá trị cận biên là max+ và min- của biến trong miền xác định để thực hiện ca kiểm thử. Ví dụ, chúng ta cần sinh các ca kiểm thử giá trị biên cho hàm laNamNhuan được hiển thị như Bảng 2.7. Hàm có đầu vào vào là biến year nhận giá trị là một số nguyên dương, ta chọn giá trị cận dưới cho biến year là 0. Giả sử ta chọn một giá trị cận trên cho biến year là 9999. Như vậy, miền xác định của biến year là [0,9999]. Các giá trị cận biên được chọn để thực hiện ca kiểm thử lần lượt là -1,0,1, 9998,9999,10000, chúng ta chọn một giá trị ở giữa miền xác định là 5000 đại diện cho giá trị thông thường để thực hiện kiểm thử. Bảng 2.7. Các ca kiểm thử giá trị biên cho hàm laNamNhuan STT Input EO RO 1 -1 -1 2 0 0 3 1 0 4 500 0 5 1995 0 6 1996 1 7 1997 0 8 1999 0 9 2000 1 10 2001 0 11 9998 0 12 9999 0 13 10.000 -1 19 Giá trị đầu ra của hàm là giá trị nguyên thỏa mãn biểu thức điều kiện ở câu lệnh 3 (year%400==0)||((year%4==0)&&(year%100!=0). Toán tử liên kết giữa hai biểu thức (year%400==0) và ((year%4==0)&&(year%100!=0) là toán tử hoặc "||" nên biểu thức ở câu lệnh 3 đúng khi một trong hai biểu thức trên đúng. Với biểu thức (year% 400==0) ta chọn một giá trị cụ thể thỏa mãn biểu thức này làm biên của biến đầu ra, giả sử ta chọn year = 2000, các giá trị cận biên để thực hiện kiểm thử là 1999 và 2001. Tương tự với biểu thức (year%4==0)&&(year%100!=0) ta chọn giá trị thỏa mãn biểu thức này làm biên của biến đầu ra. Giả sử, ta chọn year = 1996 các giá trị cận biên là 1995 và 1997. 2.6.2 Sinh ca kiểm thử vòng lặp Các đường đi kiểm thử ứng với tiêu chí phủ cao nhất thỏa mãn phủ toàn bộ các nhánh trên CFG hay các giá trị biên đã đảm bảo phủ hầu hết các trường hợp có thể xảy ra lỗi trên mã nguồn. Tuy nhiên, với những hàm có chứa vòng lặp, đường kiểm thử có đỉnh đi qua vòng lặp chỉ thực hiện kiểm thử vòng lặp một lần duy nhất. Các lỗi có thể phát sinh ở các lần lặp tiếp theo chưa được kiểm thử tới. Do vậy, chúng ta phải thiết kế các ca kiểm thử để đường kiểm thử qua vòng lặp thực hiện nhiều hơn một lần lặp. Tư tưởng của kiểm thử vòng lặp là xác định các đường kiểm thử có chứa vòng lặp trên CFG, sau đó sinh thêm các ca kiểm thử cho đường đi này để vòng lặp thực hiện thêm một số lần lặp. Cụ thể là [1,2]: nếu ta đã biết trước số lần lặp là n thì với mỗi đường đi có chứa vòng lặp, chúng ta thực hiện thêm bảy ca kiểm thử để vòng lặp thực hiện lặp 0 lần lặp, một lần, hai lần, lặp một số k bất kỳ lần (2<k< n-1), n lần và n+1 lần lặp. Trong trường hợp chưa biết trước số lần lặp tối đa của vòng lặp thì ta chỉ cần thực hiện bốn ca kiểm thử đầu tiên. Hoặc trong các trường hợp khác, chúng ta không thể sinh ca kiểm thử để thực hiện lần lặp thứ n+1. Khi đó, chúng ta chỉ cần thực hiện sáu ca kiểm thử đầu. Các đường kiểm thử qua vòng lặp có thể là [1,2]: - Đường đi qua vòng lặp đơn: Là đường đi có đỉnh duy nhất đi vào vòng lặp, qua câu lệnh thực hiện rồi thoát khỏi vòng lặp. - Đường đi qua các vòng lặp nối tiếp: Là đường đi có đỉnh qua các câu lệnh lặp nối tiếp nhau. - Đường đi qua vòng lặp lồng nhau: Là đường đi có đỉnh đi qua hai vòng lặp, một vòng lặp bên trong và một vòng lặp bên ngoài. Ví dụ, ta cần sinh ca kiểm thử cho hàm giaithua có mã nguồn và CFG ứng với độ phủ cao nhất của hàm là phủ nhánh như Hình 2.9. Đồ thị có ba đỉnh quyết đinh, nên ta có 3+1=4 đường đi để phủ hết các nhánh của đồ thị. 20 Hình 2.9. Mã nguồn và CFG ứng với tiêu chí phủ nhánh của hàm giaithua Các đường đi được liệt kê như sau: p1: 1(T),2 p2: 1(F),3(T),4 p3: 1(F), 3(F), 5, 6(F), 9 p4: 1(F), 3(F), 5, 6(T), 7, 8, 6(F), 9 Với mỗi đường kiểm thử, ta sẽ tìm nghiệm thỏa mãn hệ ràng buộc trên đường đi. Mỗi nghiệm tìm được sẽ tương ứng với ca kiểm thử trên đường đi đó. Bảng các ca kiểm thử ứng với tiêu chí phủ nhánh cho hàm giaithua được liệt kê trong Bảng 2.8 Bảng 2.8. Các ca kiểm thử cho tiêu chí phủ nhánh của hàm giaithua Trên tập đường kiểm thử, đường đi p4 qua vòng lặp for chỉ thực hiện tối đa một lần lặp, do đó khó có thể phát hiện lỗi khi vòng for thực hiện nhiều lần lặp tiếp theo. Để kiểm thử vòng lặp for, chúng ta cần sinh các ca kiểm thử để vòng lặp thực hiện với một số lần lặp là 0 lần lặp, 1 lần lặp, 2 lần lặp và một số k (k>2) lần lặp. Ở tập ca kiểm thử trên Bảng 2.8, chúng ta đã có 2 ca kiểm thử với 0 và 1 lần lặp (ứng với đường đi p3 và p4) nên chúng ta chỉ cần sinh thêm 2 ca kiểm thử là lặp 2 lần và lặp k=4 lần cho STT Path Input EO RO Tc1 1(T),2 -1 -1 Tc2 1(F), 3(T), 4 0 1 Tc3 1(F), 3(F), 5, 6(F), 9 1 1 Tc4 1(F), 3(F), 5, 6(T), 7, 8, 6(F), 9 2 2 F public int giaithua(int n){ 1. if(n<0) 2. return -1; 3. if(n==0) 4. return 1; 5. int gt=1; for(int i=1;i<n+1;i++) { 5 6 8 gt*=i;}|7 9. return gt; } 7 6 2 1 T T T F 4 3 5 8 9 21 vòng lặp for. Các ca kiểm thử vòng lặp for của hàm giaithua được mô tả trong Bảng 2.9. Bảng 2.9. Các ca kiểm thử vòng lặp for của hàm giaithua TT Lần lặp Input EO RO 1 2 3 6 2 k (k=4) 5 120 Như vậy, để có một bộ ca kiểm thử hoàn chỉnh cho một hàm, chúng ta phải có bộ ca kiểm thử giá trị biên, bộ ca kiểm thử vòng lặp và bộ ca kiểm thử được sinh bằng phương pháp kiểm thử dòng dữ liệu. Khi có bộ ca kiểm thử hoàn chỉnh, giáo viên sẽ thực thi ca kiểm thử trên bài tập của học sinh bằng phương pháp thủ công, hoặc sử dụng các công cụ hỗ trợ như JUnit1 (cho Java), NUnit2 (cho C), v.v. 1 https://junit.org 2 https://nunit.org 22 Chƣơng 3: Công cụ và thực nghiệm 3.1 Đặc tả hệ thống chấm bài lập trình 3.1.1 Danh sách các tác nhân Hệ thống chấm bài lập trình có hai tác nhân (actor) chính là Giáo viên và Học sinh, được mô tả trong Bảng 3.1. Bảng 3.1. Danh sách tác nhân của hệ thống chấm bài lập trình. TT Tác nhân Mô tả 1 Giáo viên Đăng nhập, đăng xuất, tải bài tập mẫu, quản lý bài tập, xuất đề, chấm bài, thống kê điểm theo lớp. 2 Học sinh Đăng nhập, đăng xuất, xem đề bài, tải bài làm, xem điểm. Giáo viên khi đăng nhập vào hệ thống, sẽ tải lên các bài tập mẫu (là các tệp có chứa mã nguồn Java không có lỗi). Hệ thống sẽ tự động sinh các các đồ thị dòng điều khiển, đường kiểm thử và các ca kiểm thử mẫu ứng với từng bài tập, làm tiêu chí cho việc chấm bài. Giáo viên có thể thêm, sửa, xem, xóa, in bài tập mẫu từ hệ thống, chọn bài tập để xuất đề kiểm tra và thực hiện chấm bài khi các học sinh đã tải bài làm của mình lên. Khi hệ thống đã chầm bài, Giáo viên có thể xem điểm cho từng học sinh và thống kê điểm của các học sinh theo từng lớp. Giáo viên sẽ đăng xuất ra khỏi hệ thống khi đã hoàn tất các ca sử dụng. Học sinh khi đăng nhập vào hệ thống có thể xem được đề bài mà thầy cô đã tạo . Tại thời điểm bắt đầu kiểm tra, dựa vào đề bài, Học sinh sẽ chọn một trong số các bài tập (ứng với đề kiểm tra) có trên hệ thống để bắt đầu làm bài. Học sinh sẽ phải tải các tệp chứa mã nguồn Java lên để hệ thống thực hiện chấm bài tự động. Điểm sẽ được tính dựa trên tỷ lệ các ca kiểm thử thành công trên bài làm của học sinh so với tập ca kiểm thử mẫu. Học sinh sẽ xem được điểm của mình ngay khi trên hệ thống chấm bài xong. Ngoài ra, để tăng khả năng tự học, với mỗi bài tập đã kiểm tra, Học sinh sẽ xem được các lỗi trên bài tập của mình và danh sách cac ca kiểm thử mẫu. Học sinh sẽ đăng xuất khỏi hệ thống khi hoàn tất các ca sử dụng. Danh sách các ca sử dụng của hệ thống chấm bài lập trình và biểu đồ ca sử dụng được thể hiện trong Bảng 3.2 và Hình 3.1. 23 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. TT Tác nhân Ca sử dụng Mô tả ca sử dụng 1 Giáo viên, học sinh Đăng nhập Actor đăng nhập vào hệ thống. 2 Đăng xuất Actor đăng xuất khỏi hệ thống. 3 Giáo viên Tải bài tập mẫu Tải bài tập mẫu để hệ thống sinh ca kiểm thử. 4 Quản lý bài tập Thêm, sửa, xem, xóa, xem, phân nhóm bài tập. 5 Xuất đề Chọn các bài tập để tạo đề kiểm tra. 6 Chấm bài Chấm bài cho các học sinh đã nộp. 7 Thống kê điểm Thống kê điểm theo lớp. 8 Học sinh Xem đề bài Xem và chọn bài tập để làm. 9 Tải bài làm Tải bài làm lên hệ thống. 10 Xem điểm Xem điểm sau khi hệ thống chấm bài. Giáo viên Học sinh Hình 3.1. Biểu đồ ca sử dụng của hệ thống chấm bài lập trình. Đăng xuất Tải bài tập mẫu Quản lý bài tập Thống kê điểm Đăng nhập Xuất đề Xem đề bài Tải bài làm Xem điểm Chấm bài 24 3.1.2 Mô tả các ca sử dụng của hệ thống: - Ca sử dụng "Đăng nhập":  Đối tượng sử dụng (actor): Giáo viên, Học sinh.  Ca sử dụng này mô tả các bước đăng nhập của các actor vào hệ thống.  Các bước thực hiện: + Hệ thống yêu cầu actor nhập tên đăng nhập, mật khẩu và mã xác thực. + Actor nhập xong thông tin đăng nhập và kích nút đăng nhập. + Hệ thống kiểm tra thông tin đăng nhập. Nếu đăng nhập thành công, hệ thống sẽ dựa trên thông tin để đăng nhập vào actor tương ứng. Nếu thất bại, hệ thống sẽ yêu cầu người dùng đăng nhập lại. - Ca sử dụng: "Đăng xuất":  Đối tượng sử dụng: bao gồm các thành viên trong ca sử dụng "Đăng nhập"  Ca sử dụng mô tả việc đăng xuất khỏi hệ t