Tổng quan nghiên cứu

Trong kỹ nghệ phần mềm hiện đại, hoạt động kiểm thử chiếm khoảng 40% đến 50% tổng chi phí và hơn 60% thời gian của toàn bộ vòng đời phát triển dự án. Kiểm thử đơn vị (Unit Testing) đóng vai trò nền tảng nhằm phát hiện sớm các khiếm khuyết nội tại của mã nguồn, ngăn chặn lỗi lan truyền sang các giai đoạn tích hợp hệ thống. Luận văn thạc sĩ chuyên ngành Khoa học Máy tính (mã số 60 48 01) với đề tài "An Efficient Method for Automated Control Flow Testing of Programs" (Phương pháp hiệu quả cho kiểm thử luồng điều khiển tự động của chương trình) được thực hiện bởi tác giả Nguyễn Quang Trung dưới sự hướng dẫn khoa học của Tiến sĩ Phạm Ngọc Hùng tại Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội vào năm 2014.

Vấn đề nghiên cứu trọng tâm xuất phát từ thực tế các doanh nghiệp phần mềm thường tách rời hai phương pháp kiểm thử hộp đen (Black-box Testing) và kiểm thử hộp trắng (White-box Testing). Sự phân tách này khiến việc kiểm thử luồng điều khiển (Control Flow Testing) trong kiểm thử hộp trắng trở nên tốn kém, phụ thuộc nhiều vào thao tác thủ công và dễ bùng nổ không gian tìm kiếm khi phân tích đồ thị luồng điều khiển phức tạp. Mục tiêu cụ thể của luận văn là nghiên cứu, đề xuất và hiện thực hóa một giải pháp tự động hóa thông minh kết hợp ưu điểm của cả hai kỹ thuật kiểm thử. Bằng cách tận dụng các ca kiểm thử hộp đen sẵn có để rút gọn không gian đồ thị quyết định (ddgraph), phương pháp giúp giảm từ 30% đến 45% số cung dư thừa, hạ độ phức tạp thời gian thuật toán từ $O(n^4)$ xuống mức xấp xỉ $O(n^2 \log n)$ và bảo đảm độ bao phủ nhánh đạt trên 90% với chi phí tối ưu.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên hệ thống cơ sở lý thuyết vững chắc về đảm bảo chất lượng phần mềm và lý thuyết đồ thị trong kiểm thử luồng điều khiển:

  1. Lý thuyết chất lượng phần mềm và các cấp độ kiểm thử: Luận văn tiếp cận 5 góc nhìn chất lượng phần mềm theo mô hình của David Garvin cùng nghiên cứu của Barbara Kitchenham và Shari Lawrence Pfleeger, bao gồm góc nhìn siêu việt, người dùng, sản xuất, sản phẩm và giá trị. Nghiên cứu phân định rõ 4 cấp độ kiểm thử chuẩn hóa: kiểm thử thành phần (Component/Unit Testing), kiểm thử tích hợp (Integration Testing), kiểm thử hệ thống (System Testing) và kiểm thử chấp nhận (Acceptance Testing với Alpha/Beta test).
  2. Lý thuyết đồ thị luồng điều khiển và đồ thị quyết định (ddgraph): Đồ thị luồng điều khiển chuẩn biểu diễn cấu trúc rẽ nhánh của chương trình. Tác giả chuyển đổi đồ thị luồng điều khiển sang dạng đồ thị quyết định sang quyết định (Decision-to-Decision Graph - ddgraph) ký hiệu $G = (N, A)$ gồm tập đỉnh $N$ và tập cung có hướng $A$.
  3. Lý thuyết kiểm thử đường cơ sở và thực thi tượng trưng: Kế thừa phương pháp kiểm thử đường cơ sở của Thomas McCabe cùng các nghiên cứu về bộ sinh dữ liệu kiểm thử của Rajiv Gupta, Mary Lou Soffa, Martina Marre và Antonia Bertolino. Kết hợp kỹ thuật thực thi tượng trưng (Symbolic Execution) để chuyển đổi các đường dẫn thực thi thành hệ điều kiện ràng buộc nhằm sinh dữ liệu kiểm thử tự động.

Phương pháp nghiên cứu

Phương pháp nghiên cứu kết hợp giữa phân tích lý thuyết hình thức và thực nghiệm công nghệ:

  • Nguồn dữ liệu và phạm vi thực nghiệm: Dữ liệu nghiên cứu bao gồm các đơn vị mã nguồn chương trình viết bằng ngôn ngữ Java với các cấu trúc điều khiển rẽ nhánh phức tạp từ 2 đến 32 câu lệnh điều kiện lồng nhau, tương đương không gian trạng thái lên tới $2^{32} \approx 4{,}29$ tỷ đường đi tiềm năng trong trường hợp cực hạn.
  • Cỡ mẫu và phương pháp chọn mẫu: Tác giả lựa chọn có chủ đích 10 đơn vị mã nguồn Java mẫu đại diện, tiêu biểu như thuật toán phân loại cấu trúc cây (tree method) và phương thức tính cước phí dịch vụ phức tạp (calculateBill). Các mẫu kiểm thử được chọn đảm bảo bao phủ đầy đủ các mô hình luồng điều khiển từ tuần tự, rẽ nhánh nhị phân, cấu trúc điều kiện lồng nhau đến vòng lặp.
  • Phương pháp phân tích và quy trình thuật toán: Nghiên cứu áp dụng kỹ thuật phân tích tĩnh (phân tích mã nguồn, xây dựng đồ thị) kết hợp phân tích động (thực thi mã với dữ liệu kiểm thử). Quy trình gồm 2 thuật toán cốt lõi: Thuật toán SIMPLIFY (loại bỏ các cung dư thừa đã được duyệt bởi kiểm thử hộp đen và hàm hiệu chỉnh ADJUST1) và Thuật toán FIND_BASIC (tìm kiếm các đường dẫn hoàn chỉnh trên đồ thị con kết hợp hàm ADJUST2). Toàn bộ quá trình nghiên cứu, mô hình hóa toán học và thực nghiệm công cụ được hoàn thành trong chu kỳ đào tạo 2 năm từ 2012 đến 2014.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình thực nghiệm và kiểm chứng toán học của luận văn đã mang lại các phát hiện khoa học quan trọng:

  1. Khả năng rút gọn không gian đồ thị vượt trội: Bằng việc chứng minh định lý về bảo toàn tính liên thông khi loại bỏ cung dư thừa, thuật toán SIMPLIFY đã loại bỏ thành công 100% các cung dư thừa tương ứng với các ca kiểm thử hộp đen. Không gian tìm kiếm của đồ thị ddgraph ban đầu được rút gọn ngay từ 35% đến 50% số đỉnh và cung sau vòng lặp đầu tiên.
  2. Tối ưu hóa độ phức tạp thời gian tính toán: Trong trường hợp xấu nhất của phương pháp duyệt vét cạn truyền thống, độ phức tạp thời gian đạt mức $O(n^4)$. Khi áp dụng phương pháp kết hợp rút gọn đồ thị ddgraph với cấu trúc cây nhị phân có chiều cao $H = \log_2(|N|-1) + 1$, độ phức tạp thời gian của giải pháp đề xuất giảm mạnh về mức xấp xỉ $O(n^2 \log n)$.
  3. Sinh bộ dữ liệu kiểm thử tối thiểu đạt độ bao phủ tối đa: Trên các ca nghiên cứu điển hình như hàm calculateBill, thuật toán tự động sinh ra tập đường dẫn cơ sở không trùng lặp $S = {P_1, P_2, P_3, P_4}$ bao phủ 100% các nhánh điều kiện mà không cần duyệt lại các cung đã được bao phủ bởi kiểm thử hộp đen.
  4. Hiện thực hóa công cụ tự động hóa dạng Eclipse Plugin: Tác giả đã đóng gói thành công phương pháp thành một plugin hoàn chỉnh trên môi trường phát triển Eclipse, hỗ trợ lập trình viên kiểm thử đơn vị Java tự động, giúp rút ngắn hơn 40% thời gian tạo ca kiểm thử so với phương pháp thủ công.

Thảo luận kết quả

Nguyên nhân cốt lõi mang lại hiệu quả vượt trội của phương pháp là việc xóa bỏ ranh giới biệt lập giữa kiểm thử hộp đen và hộp trắng. Trong thực tế, các ca kiểm thử hộp đen vốn được thiết kế dựa trên yêu cầu người dùng đã vô tình thực thi một phần không nhỏ các nhánh mã nguồn. Việc tận dụng dấu vết thực thi này để cắt tỉa đồ thị ddgraph giúp thuật toán kiểm thử hộp trắng chỉ cần tập trung vào các vùng mã nguồn chưa được khám phá.

So với các hướng tiếp cận trước đây như việc dùng thuật toán di truyền của Ahmed S. Said và Sultan Aljahdali hay tìm kiếm theo chiều sâu (DFS) thuần túy của Guangmei, giải pháp của luận văn tránh được hiện tượng kẹt tại các cực trị địa phương và loại bỏ hoàn toàn các đường dẫn trùng lặp. Về mặt trình bày dữ liệu, các kết quả được trực quan hóa sinh động thông qua biểu đồ biến đổi trạng thái đồ thị qua từng vòng lặp (ba giai đoạn rút gọn ddgraph) cùng bảng phân tích ma trận thực thi tượng trưng (Symbolic Execution Table) xác định chính xác các biểu thức điều kiện đầu vào cho từng đường dẫn.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu lý thuyết và thực nghiệm, luận văn đưa ra 4 khuyến nghị hành động thiết thực dành cho các tổ chức phát triển phần mềm:

  1. Tích hợp công cụ kiểm thử tự động vào quy trình CI/CD: Các doanh nghiệp phần mềm cần đưa plugin kiểm thử luồng điều khiển vào đường ống tích hợp liên tục (CI/CD) tự động, đặt mục tiêu giảm 30% thời gian thực hiện kiểm thử hồi quy (Regression Testing) trong lộ trình 6 tháng triển khai.
  2. Chuẩn hóa quy trình phối hợp giữa đội ngũ QA và lập trình viên: Khuyến nghị các trưởng dự án (Project Managers) thiết lập quy chuẩn tái sử dụng dữ liệu kiểm thử hộp đen ngay sau giai đoạn phân tích đặc tả, nhằm mục tiêu giảm 50% kích thước đồ thị luồng điều khiển trước khi chuyển giao cho lập trình viên thực hiện kiểm thử đơn vị.
  3. Mở rộng khả năng xử lý cấu trúc vòng lặp và đệ quy phức tạp: Đội ngũ nghiên cứu và phát triển công cụ cần tiếp tục cải tiến thuật toán để hỗ trợ các khối điều khiển đa luồng, vòng lặp phức tạp và gọi hàm đệ quy trong các ứng dụng hướng đối tượng quy mô lớn, hướng đến tối ưu thêm 25% dung lượng bộ nhớ xử lý trong vòng 12 tháng tới.
  4. Xây dựng chương trình đào tạo chuyển giao công nghệ kiểm thử: Các trường đại học và viện nghiên cứu chuyên ngành Công nghệ Thông tin cần đưa kỹ thuật rút gọn đồ thị luồng điều khiển và thực thi tượng trưng vào chương trình giảng dạy thực hành môn Kiểm thử phần mềm, hoàn thành tài liệu đào tạo chuẩn hóa trong quý 2 năm tới.

Đối tượng nên tham khảo luận văn

Tài liệu luận văn mang lại giá trị học thuật và ứng dụng cao cho 4 nhóm đối tượng chính:

  1. Kỹ sư kiểm thử và đảm bảo chất lượng phần mềm (QA/QC Engineers): Nắm vững nguyên lý kết hợp kiểm thử hộp đen và hộp trắng để tối ưu hóa bộ ca kiểm thử, giúp giảm 35% công sức thiết kế kịch bản kiểm thử trong các dự án thực tế.
  2. Lập trình viên và kỹ sư phát triển phần mềm Java (Java Developers): Hiểu rõ cơ chế xây dựng đồ thị ddgraph và ứng dụng trực tiếp Eclipse Plugin vào quy trình phát triển hướng kiểm thử (Test-Driven Development - TDD), tiết kiệm trên 40% thời gian viết unit test.
  3. Giảng viên và nghiên cứu viên ngành Khoa học Máy tính: Khai thác các chứng minh toán học hình thức về định lý cắt tỉa cung dư thừa và thuật toán sinh ca kiểm thử tượng trưng để làm tài liệu giảng dạy chuyên sâu và phát triển các đề tài khoa học liên quan.
  4. Học viên cao học và sinh viên đại học ngành Công nghệ Thông tin: Tham khảo phương pháp luận nghiên cứu khoa học chuẩn mực, cách phân tích độ phức tạp thuật toán và kỹ năng xây dựng công cụ hỗ trợ công nghệ phần mềm hoàn chỉnh.

Câu hỏi thường gặp

1. Kiểm thử luồng điều khiển tự động giải quyết được hạn chế lớn nào của kiểm thử thủ công?
Kiểm thử luồng điều khiển thủ công đòi hỏi lập trình viên phải đọc hiểu sâu toàn bộ mã nguồn, phân tích hàng trăm nhánh điều kiện rẽ nhánh phức tạp. Quá trình này tiêu tốn hơn 60% thời gian kiểm thử đơn vị và rất dễ bỏ sót các lỗi tiềm ẩn bên trong logic chương trình.

2. Đồ thị quyết định ddgraph có ưu điểm gì vượt trội so với đồ thị luồng điều khiển CFG truyền thống?
Đồ thị ddgraph nhóm các khối lệnh tuần tự liên tiếp thành một đỉnh duy nhất và chỉ tập trung mô tả các nút quyết định rẽ nhánh. Nhờ đó, số lượng đỉnh và cung được thu gọn tối đa, giúp thuật toán giảm thiểu không gian trạng thái cần duyệt từ 30% đến 50%.

3. Tại sao việc kết hợp kiểm thử hộp đen lại giúp tối ưu hóa kiểm thử hộp trắng?
Kiểm thử hộp đen sinh ra các ca kiểm thử dựa trên yêu cầu chức năng. Bằng cách ghi nhận các đường dẫn mà kiểm thử hộp đen đã đi qua, thuật toán loại bỏ toàn bộ các cung dư thừa này trên đồ thị ddgraph, giúp kiểm thử hộp trắng chỉ tập trung vào các nhánh chưa được bao phủ.

4. Mức giảm độ phức tạp từ $O(n^4)$ xuống $O(n^2 \log n)$ mang lại ý nghĩa gì cho các dự án thực tế?
Với các hàm có số lượng nhánh điều kiện lớn, thuật toán $O(n^4)$ sẽ nhanh chóng rơi vào tình trạng quá tải tính toán và bùng nổ thời gian xử lý. Việc đưa độ phức tạp về mức $O(n^2 \log n)$ giúp công cụ phản hồi kết quả sinh ca kiểm thử gần như tức thì, phù hợp tích hợp vào môi trường làm việc thực tế.

5. Công cụ hiện thực hóa trong luận văn có thể áp dụng ngay cho các dự án hiện đại không?
Công cụ được xây dựng dưới dạng Eclipse Plugin dành cho Java. Các thuật toán cốt lõi (SIMPLIFY, FIND_BASIC) là độc lập với ngôn ngữ và hoàn toàn có thể tái áp dụng để xây dựng các tiện ích kiểm thử tự động trên các IDE hiện đại như IntelliJ IDEA hay VS Code.

Kết luận

  • Luận văn đã giải quyết triệt để bài toán lãng phí tài nguyên và chi phí cao do sự phân tách rời rạc giữa kiểm thử hộp đen và kiểm thử hộp trắng trong kiểm thử đơn vị.
  • Đề xuất mô hình rút gọn đồ thị quyết định (ddgraph) dựa trên chứng minh toán học chặt chẽ về việc loại bỏ cung dư thừa mà không làm suy giảm tính liên thông của đồ thị.
  • Tối ưu hóa thành công độ phức tạp thời gian tính toán từ $O(n^4)$ xuống mức xấp xỉ $O(n^2 \log n)$, đảm bảo độ bao phủ nhánh đạt mức tối đa với số ca kiểm thử tối thiểu.
  • Đóng gói thành công giải pháp dưới dạng Eclipse Plugin thực tế, hỗ trợ tự động hóa toàn diện từ khâu phân tích mã nguồn Java đến sinh dữ liệu kiểm thử.
  • Trong lộ trình 12 đến 24 tháng tới, giải pháp tiếp tục được mở rộng nghiên cứu để hỗ trợ các hệ thống phân tán và ứng dụng hướng đối tượng đa luồng phức tạp.

Các nhà quản lý kỹ thuật, kỹ sư phần mềm và nhà nghiên cứu quan tâm đến việc tối ưu hóa chi phí kiểm thử có thể tham khảo chi tiết toàn văn luận văn thạc sĩ của tác giả Nguyễn Quang Trung tại Thư viện Đại học Quốc gia Hà Nội để ứng dụng các giải pháp thuật toán tiên tiến này vào thực tiễn dự án.