Năm 1988, một dự án lớp học đưa ký tự ngẫu nhiên vào tiện ích Unix, phát hiện chương trình sập và treo trên 7 hệ điều hành

20/10/2026 · VietTechies · Biên tập

Mùa thu năm 1988, Barton Miller, giáo sư khoa học máy tính tại Đại học Wisconsin–Madison, giao cho lớp cao học về hệ điều hành một bài tập khác thường: viết chương trình sinh các chuỗi ký tự ngẫu nhiên rồi đưa vào những tiện ích dòng lệnh tiêu chuẩn của Unix. Thí nghiệm mà Miller đặt tên là fuzz testing — kiểm thử bằng dữ liệu ngẫu nhiên — cho thấy dữ liệu đầu vào thô sơ, vô nghĩa cũng dễ dàng làm các công cụ phần mềm cơ bản mà lập trình viên dùng hằng ngày bị sập hoặc treo.

Bài báo xuất phát từ kỳ vọng rằng những tiện ích hệ điều hành được sử dụng thường xuyên phải đáng tin cậy. Miller và các sinh viên phát hiện từ 25% đến 33% số tiện ích họ kiểm thử bị sập hoặc treo khi đọc các ký tự ngẫu nhiên, và điểm yếu này xuất hiện trên 7 biến thể hệ điều hành Unix.

Tiêu chí đánh giá kết quả đơn giản nhất có thể

Bài tập trong môn Hệ điều hành nâng cao (CS736) của Miller yêu cầu sinh viên viết một chương trình sinh các chuỗi ký tự ngẫu nhiên theo ASCII, bộ mã tiêu chuẩn Hoa Kỳ dùng để trao đổi thông tin. Đề bài cho phép sinh viên linh hoạt thử nhiều kiểu chuỗi, gồm các ký tự ASCII có thể in được, toàn bộ ký tự ASCII, byte có giá trị 0 và các dòng có độ dài ngẫu nhiên.

Sau khi hoàn thành, chương trình sinh dữ liệu đưa những chuỗi ngẫu nhiên không được định hướng theo hoạt động của từng tiện ích vào các tiện ích Unix quen thuộc như mail, vi, sed, awk, sort và cc. Phương pháp kiểm thử cố ý dùng một tiêu chí hết sức sơ khai: ứng dụng kết thúc bất thường (sập) hoặc ngừng phản hồi dữ liệu đầu vào (treo) thì không đạt. Nếu ứng dụng xử lý dữ liệu đầu vào rồi thoát bình thường thì đạt.

Tiện ích đang được kiểm thử có thể cho ra kết quả vô nghĩa hoặc thông báo lỗi chẳng giúp ích gì mà vẫn đạt, miễn là không sập hay treo. Quy tắc đạt hay không đạt đơn giản này — gọi là test oracle, tiêu chí xác định kết quả kiểm thử — không cần mô hình mô tả đầu ra mong đợi của tiện ích.

Ba nhóm, chỉ một nhóm tìm được lỗi

Ý tưởng thì đơn giản, nhưng để thực hiện được, sinh viên phải tiến hành thí nghiệm cẩn thận, có kỷ luật. Ba nhóm trong lớp của Miller vào mùa thu năm 1988 đã thử làm dự án này. Hai nhóm không tạo ra được trường hợp sập chương trình nào. Trong lời kể về sau, Miller không nêu nguyên nhân kỹ thuật cụ thể khiến hai nhóm thất bại.

Nhóm thứ ba, gồm hai học viên cao học Lars Fredriksen và Bryan So, đã thành công. Công cụ của họ ghi các chuỗi đầu vào ngẫu nhiên xuống đĩa; các tập lệnh lưu bản kết xuất bộ nhớ khi chương trình sập cùng dữ liệu đầu vào gây lỗi để điều tra sau. Khi họ cho các tiện ích thông dụng nhận dữ liệu từ chương trình sinh này, hết chương trình này đến chương trình khác bị sập.

Sập và treo trên 7 biến thể Unix

Fredriksen và So mở rộng kiểm thử sang 7 biến thể Unix trong thương mại và học thuật. Sau này, Miller tóm tắt kết quả: 25–33% số tiện ích được kiểm thử trên các hệ thống ấy bị sập hoặc treo. Bài báo xác định các vụ sập trong ftp và telnet bắt nguồn từ gets(), hàm có thể ghi tràn bộ đệm đầu vào, đồng thời phát hiện thao tác đọc chuỗi không giới hạn độ dài trong tsort, tiện ích sắp xếp tô pô.

Các lỗi này không bắt nguồn từ những nghịch lý logic tinh vi. Những nguyên nhân được chẩn đoán gồm truy cập mảng mà không kiểm tra giới hạn, con trỏ không hợp lệ và cách sử dụng thiếu an toàn các hàm nhập dữ liệu của C như gets, vốn không thể kiểm tra giới hạn bộ đệm đích. Bài báo còn xác định những nguyên nhân khác, gồm không kiểm tra giá trị trả về, tiến trình con gặp lỗi, xử lý lỗi sai và lỗi tranh chấp thời điểm (race condition).

Công bố dữ liệu và đối mặt với hoài nghi

Tháng 12 năm 1990, Miller, Fredriksen và So công bố kết quả trên Communications of the ACM, tạp chí của Hiệp hội Máy tính (Association for Computing Machinery), với tiêu đề “An Empirical Study of the Reliability of UNIX Utilities.” Không chỉ chỉ ra lỗi trong phần mềm của các nhà cung cấp, nhóm tác giả còn công khai mã nguồn chương trình sinh dữ liệu fuzz, các tập lệnh kiểm thử, nhật ký gốc ghi lại các lần chương trình sập và những bản vá code họ đề xuất.

Trong lời tựa viết năm 2008, Miller nhớ lại sự phản đối mạnh mẽ từ một số thành viên trong cộng đồng kiểm thử và kỹ nghệ phần mềm, những người cho rằng cách tiếp cận này thiếu mô hình hình thức và phương pháp luận. Ông mô tả fuzz testing là phần bổ sung cho các phương pháp kiểm thử có hệ thống hơn: thêm một công cụ để tìm lỗi.

Fuzz testing chứng minh được và không chứng minh được điều gì?

Thí nghiệm năm 1988 của Miller có ảnh hưởng lâu dài vì giúp làm rõ kiểm thử ngẫu nhiên kiểu hộp đen — không xét cấu trúc bên trong chương trình — thực sự đo lường điều gì. Vượt qua một phép kiểm thử fuzz không chứng minh chương trình hoạt động đúng, bảo mật hay không có lỗi logic. Ứng dụng có thể âm thầm tính toán sai dữ liệu hoặc trả về đáp án sai mà vẫn thoát với mã báo thành công.

Trong thí nghiệm này, fuzzing kiểm tra khả năng ứng dụng xử lý đầu vào bất thường mà không sập hay treo bằng cách đưa dữ liệu ngẫu nhiên vào ứng dụng rồi kiểm tra hai dấu hiệu đó. Kết quả đạt không chứng minh chương trình an toàn bộ nhớ. Dù vậy, cách tiếp cận này vẫn trụ vững: năm 2022, nghiên cứu công bố năm 1990 nhận giải thưởng Jean-Claude Laprie về điện toán đáng tin cậy do Nhóm công tác 10.4 (Working Group 10.4) thuộc Liên đoàn Quốc tế về Xử lý Thông tin (IFIP) trao tặng.

Ý tưởng đơn giản khởi đầu trong một lớp học ở Wisconsin năm 1988 cho thấy: trước khi có thể tin phần mềm sẽ suy luận đúng, phần mềm phải được xây dựng để chịu được những đầu vào ngoài dự tính.

Bài liên quan

Đọc bằng ngôn ngữ khác: English