20/10/2026 · VietTechies · Biên tập
Năm 1999, Andreas Zeller giới thiệu Delta Debugging để khoanh vùng những thay đổi trong code khiến phần mềm đang chạy bình thường gặp lỗi. Trong bài báo năm 2002, Zeller và Ralf Hildebrandt giải quyết một câu hỏi liên quan: có thể bỏ đi bao nhiêu phần của đầu vào gây lỗi mà chương trình vẫn gặp lỗi?
Khi công cụ kiểm thử tự động hoặc báo cáo của người dùng phát hiện chương trình bị văng, đầu vào gây ra sự cố thường dài hàng nghìn dòng văn bản, code hoặc dữ liệu, lẫn rất nhiều nội dung không liên quan. Để thu gọn đầu vào bằng tay, người ta xóa từng phần rồi chạy lại các phép thử để xem lỗi còn xuất hiện hay không. Thuật toán ddmin tự động hóa quá trình đó. Nếu kết quả kiểm thử có tính tất định, đầu vào ban đầu gây lỗi, đầu vào rỗng vượt qua phép thử và thuật toán có đủ thời gian chạy xong, ddmin đảm bảo kết quả đạt tính 1-tối thiểu theo các phần tử đầu vào đã chọn.
Tìm đầu vào gây lỗi bằng cách chia để trị
Năm 1999, Brian Kernighan và Rob Pike mô tả một cách gỡ lỗi thủ công trong cuốn The Practice of Programming: khi một đầu vào khiến chương trình gặp lỗi, hãy bỏ đi một nửa đầu vào rồi xem đầu ra còn sai không; nếu không, khôi phục đầu vào trước đó rồi bỏ nửa còn lại. Cách tìm kiếm nhị phân theo nguyên tắc chia để trị này hiệu quả khi lỗi nằm gọn trong một phần riêng biệt.
Tìm kiếm nhị phân đơn giản có thể bế tắc khi không nửa nào tái hiện được lỗi. Chương trình có thể bị văng do tương tác giữa hai tham số riêng biệt, hoặc việc bỏ đi một nửa đầu vào có thể làm sai cú pháp trước khi chương trình chạy đến đoạn code có lỗi. Thuật toán ddmin năm 2002 của Zeller và Hildebrandt mở rộng cách tìm kiếm nhị phân bằng cách thử những phần nhỏ hơn khi không nửa nào tái hiện được lỗi, dù các ràng buộc cú pháp vẫn có thể khiến quá trình thu gọn không mang lại kết quả hữu ích.
ddmin loại bỏ từng phần đầu vào như thế nào
Thuật toán ddmin gốc chia đầu vào hiện tại thành n phần có kích thước gần bằng nhau, bắt đầu với n = 2. Trước hết, thuật toán kiểm thử riêng từng phần. Nếu một phần tái hiện được lỗi cần tìm, thuật toán tiếp tục với phần đó và đặt lại n bằng 2. Nếu không, thuật toán kiểm thử các phần bù — tức đầu vào hiện tại sau khi bỏ đi một phần. Nếu một phần bù tái hiện được lỗi, thuật toán giữ phần bù đó và đặt n bằng giá trị lớn hơn giữa n − 1 và 2.
Nếu không phần nào hay phần bù nào tái hiện được lỗi, ddmin tăng n lên gấp đôi, nhưng không vượt quá số phần tử đầu vào còn lại. Thuật toán dừng khi đã chia nhỏ đến từng phần tử mà vẫn không thể thu gọn thêm. Người dùng tự chọn thế nào là một phần tử, chẳng hạn dòng, token hoặc ký tự; ddmin không tự chuyển từ loại phần tử này sang loại khác. Các cuốn sách được dẫn trong bài cũng trình bày một cách triển khai đơn giản hơn, chỉ kiểm thử các phần bù.
Vì sao 1-tối thiểu không có nghĩa là đầu vào ngắn nhất
Kết quả 1-tối thiểu của delta debugging không nhất thiết là tập con ngắn nhất gây lỗi trong toàn bộ đầu vào ban đầu. Nếu không có các giả định cho phép loại trừ những đầu vào đang xét, việc tìm tập con gây lỗi nhỏ nhất trên toàn bộ không gian tìm kiếm chỉ dựa vào kết quả kiểm thử có thể đòi hỏi số phép thử tăng theo hàm mũ: một đầu vào có m phần tử sẽ có 2m tập con.
Khi chạy xong trong các điều kiện đã nêu, ddmin đảm bảo tính 1-tối thiểu theo các phần tử đầu vào đã chọn: kết quả vẫn gây lỗi, nhưng xóa bất kỳ một phần tử nào cũng khiến phép thử đạt hoặc rơi vào trạng thái chưa phân giải. Điều này không chứng minh rằng mọi phần tử được giữ lại đều gây ra lỗi; có những lần xóa chỉ khiến phép thử không thể đưa ra kết luận. Nếu bỏ cùng lúc hai phần tử trở lên, vẫn có thể thu được một tập con nhỏ hơn của chính kết quả đó mà vẫn gây lỗi.
Xử lý trạng thái chưa phân giải
Quá trình thu gọn tự động cần một bộ đánh giá kết quả kiểm thử (test oracle) đáng tin cậy, trả về một trong ba trạng thái: đạt, lỗi hoặc chưa phân giải. Bộ đánh giá này — quy tắc dùng để phân loại kết quả của một phép thử — báo lỗi khi lỗi đã chỉ định xuất hiện, báo đạt khi phép thử thành công và báo chưa phân giải khi không xác định được kết quả. Lỗi cần tái hiện có thể là kết quả sai hoặc một assertion bị vi phạm, cũng có thể là ngoại lệ hay chương trình bị văng.
Trạng thái thứ ba — chưa phân giải — có vai trò then chốt. Nếu việc bỏ đi một phần tạo ra tệp không thể phân tích cú pháp, lỗi cú pháp hoặc một sự cố văng chương trình không liên quan, phép thử không thể xác định lỗi ban đầu còn tồn tại hay không. Thuật toán ddmin coi kết quả chưa phân giải là một lần thu gọn không thành công: thuật toán chỉ chấp nhận đầu vào nhỏ hơn khi đầu vào đó tái hiện được lỗi cần tìm.
Từ lý thuyết học thuật đến hạ tầng trình biên dịch
Năm 2009, nhóm chuyên trách kỹ nghệ phần mềm thuộc Hiệp hội Máy tính (ACM SIGSOFT) trao cho Zeller giải Impact Paper Award nhờ công trình nền tảng năm 1999 của ông.
Các nhà phát triển trình biên dịch (compiler) áp dụng những khái niệm delta debugging để phân loại và đánh giá lỗi. Hạ tầng trình biên dịch LLVM có llvm-reduce, một công cụ tự động chuyên dụng thực hiện các lượt thu gọn delta trên tệp biểu diễn trung gian (Intermediate Representation, IR), nhằm thu nhỏ những ca kiểm thử lớn khiến bộ tối ưu hóa bị văng. Quá trình thu gọn tự động có thể giúp lập trình viên dễ hiểu và trao đổi về các ca kiểm thử gây lỗi hơn.
Bằng cách xem gỡ lỗi là một bài toán tìm kiếm qua thực nghiệm, Zeller cho thấy muốn tìm ra phần cốt lõi của một lỗi, không cần đoán ý định của người viết chương trình; cần kiểm thử có hệ thống xem đầu vào có thể bỏ đi những phần nào mà chương trình vẫn gặp lỗi.
Bài liên quan
Đọc bằng ngôn ngữ khác: English
Nguồn
- Isolating Failure-Inducing Changes — Andreas Zeller, The Debugging Book
- Reducing Failure-Inducing Inputs — Andreas Zeller, The Debugging Book
- Giải ACM SIGSOFT Impact Paper Award — ACM SIGSOFT
- llvm-reduce – LLVM automatic testcase reducer — Dự án LLVM
- Reducing Failure-Inducing Inputs — Andreas Zeller, The Fuzzing Book
- Ảnh đại diện: Stefan Weil; Wikimedia Commons; CC BY 4.0 (đã chỉnh sửa từ ảnh gốc)
