LLM Biến Formal Verification Thành Thực Tế: Zstandard Được Chứng Minh Trong 20 Phút

Tin Chính

Adam Langley — chuyên gia bảo mật, cựu kỹ sư Google — vừa công bố một thử nghiệm đáng chú ý trên blog cá nhân ngày 26/7: anh xây dựng bộ giải nén Zstandard hoàn chỉnh trong Lean, một ngôn ngữ có dependent types (hệ thống kiểu phụ thuộc), và dùng LLM để tự động chứng minh tính đúng đắn của các thuật toán phức tạp.

Kết quả: những chứng minh từng tốn hàng ngày hoặc hàng tuần của chuyên gia, giờ chỉ mất khoảng 20 phút với gói subscription $20/tháng.

Đây không phải một bài báo học thuật. Đây là một kỹ sư thực thụ kiểm tra xem formal verification có thực sự khả thi cho công việc hàng ngày hay không — và câu trả lời là có.

Bối Cảnh: Từ "Quá Đắt" Đến "Có Thể Chi Trả Được"

Kiểm chứng hình thức (formal verification) là kỹ thuật chứng minh toán học rằng code hoạt động chính xác theo đặc tả — không cần test, không cần may mắn. Vấn đề kinh điển: chi phí chứng minh luôn cao hơn chi phí lập trình một cách phi lý.

Dự án seL4 — hệ điều hành được chứng minh đúng đắn toàn bộ — là minh chứng rõ nhất. Theo báo cáo tổng kết, nhóm seL4 dành thời gian chứng minh gấp 10 lần thời gian thiết kế và lập trình, và số dòng code chứng minh nhiều hơn 20 lần số dòng code C thực tế. Tỷ lệ này khiến ngay cả những tổ chức có nguồn lực dồi dào cũng phải cân nhắc.

Các công cụ như F* cố gắng tự động hóa bằng SMT solver, nhưng tạo ra vấn đề khác: solver dễ rơi vào trạng thái chạy vô hạn, buộc người dùng phải phát triển "giác quan thứ sáu" để viết code không làm solver treo. Như Langley mô tả: "bạn phục vụ một vị thần phức tạp và thất thường."

LLM thay đổi cuộc chơi nhờ một lý do then chốt: proof irrelevance — một khi mệnh đề đúng, nội dung cụ thể của chứng minh không quan trọng, chỉ cần nó tồn tại và type-check được. LLM trở thành công cụ lý tưởng: miễn chứng minh biên dịch thành công, chất lượng bên trong không thành vấn đề.

Thử Nghiệm: Zstandard Decompressor Trong Lean

Zstandard (zstd) là thuật toán nén đang dần thay thế gzip làm tiêu chuẩn. Thuộc họ LZ77, nhưng dùng entropy encoder tốt hơn và thiết kế cho tốc độ giải nén cực cao. RFC 8878 định nghĩa toàn bộ định dạng này.

Langley chọn Zstandard vì hai lý do: tò mò về thuật toán, và đây là bài toán đủ phức tạp để kiểm tra giới hạn của LLM trong formal verification.

Điểm Nhấn: Chứng Minh Thuật Toán FSE Table Construction

FSE (Finite State Entropy) là bộ mã hóa entropy của Zstandard — một state machine nơi mỗi ký hiệu được gán số trạng thái tỷ lệ với xác suất xuất hiện. Thuật toán xây dựng bảng FSE từ danh sách xác suất ký hiệu được mô tả trong RFC 8878, kèm ba test vector mẫu.

Thay vì chỉ viết unit test, Langley dùng LLM để chứng minh bốn thuộc tính toàn cục của hàm ofDistribution:

Kích thước bảng đúng: t.entries.size = 2 ^ accuracyLog
Phân bổ trạng thái đúng: số state cho mỗi ký hiệu khớp với xác suất
An toàn khi đọc bit: với mọi state, đọc nbBits bit và cộng baseline luôn ra một state hợp lệ
Tính duy nhất của đường dẫn: với mọi ký hiệu có xác suất >0 và mọi state đích, có đúng một state của ký hiệu đó dẫn tới đích

Đây là những bất biến tinh vi mà vòng lặp giải mã tối ưu đòi hỏi. Trong ngôn ngữ thông thường, chúng chỉ có thể là comment — hoặc tệ hơn, là giả định ngầm không ai kiểm chứng.

Kết quả: các LLM tự động chứng minh toàn bộ trong khoảng 20 phút, chỉ dùng một phần quota của gói subscription $20/tháng. Langley viết: "It'll probably be table-stakes next year" — năm sau có lẽ đây sẽ là tiêu chuẩn cơ bản.

Lean: Ngôn Ngữ Biến Chứng Minh Thành Kiểu Dữ Liệu

Lean là ngôn ngữ thuần hàm với dependent types — kiểu dữ liệu có thể phụ thuộc vào giá trị, cho phép biểu diễn các bất biến phức tạp ngay trong type system.

Ví dụ, hàm readExact trong Lean trả về {ba : ByteArray // ba.size = n} — mảng byte mà type system đảm bảo có độ dài đúng bằng n. Khi truy cập phần tử mảng, Lean bắt chứng minh chỉ số nằm trong phạm vi — nếu không, code không biên dịch được.

Langley ghi nhận một số điểm đáng chú ý:

Strict evaluation (không lazy như Haskell) giúp dễ suy luận về hiệu năng
Do-notation hỗ trợ for loop, return, break — lập trình theo phong cách imperative
Reference-counting optimization cho phép mutation tại chỗ khi chỉ có một tham chiếu

Tuy nhiên, bộ giải nén của anh chậm hơn zstd CLI khoảng 10 lần — lời nhắc rằng Lean vẫn là ngôn ngữ bậc cao, chưa cạnh tranh được về hiệu năng thuần túy.

Ranh Giới Hiện Tại: Assembly Verification Chưa Scale Được

Một hướng tham vọng hơn: chứng minh tính tương đương giữa code assembly đã tối ưu và code Lean đã xác minh. AWS đã phát triển LNSym — mô phỏng và ngữ nghĩa AArch64 trong Lean.

Langley đã thử nghiệm hướng này. Kết quả: ví dụ popcount đơn giản trong repo LNSym dùng bv_decide (SAT solver có chứng nhận) đã tiêu tốn nhiều bộ nhớ hơn máy của anh có. Các hàm nhỏ chạy được, nhưng cả anh và các LLM đều không thể scale lên hàm lớn hơn.

Đây là giới hạn rõ nhất hiện tại: chứng minh code bậc cao hoạt động, nhưng chứng minh assembly tối ưu thì chưa.

Điều Này Có Ý Nghĩa Gì Với Developer?

Ngắn Hạn: Không Còn Là Đặc Quyền Học Viện

LLM đã hạ rào cản chứng minh từ "10x effort" xuống mức một developer có thể tự thử nghiệm. Những bất biến trước đây chỉ tồn tại dưới dạng comment (hoặc trong đầu maintainer) giờ có thể được chứng minh toán học với chi phí chấp nhận được.

Trung Hạn: Một Lớp Ngôn Ngữ Lập Trình Mới

Đoạn thú vị nhất trong bài Langley: "we, practically speaking, have a new type of programming language available to us." Dependent types đã tồn tại hàng thập kỷ nhưng bị giới hạn trong học viện vì chi phí chứng minh. LLM có thể thay đổi phương trình đó.

Dài Hạn: Code Không Bug, Không Cần Test?

Những câu hỏi mở vẫn còn:

Chứng minh có scale được trên hệ thống hàng trăm nghìn dòng code không?
LLM sinh chứng minh sai nhưng vẫn type-check được thì sao?
Chi phí bảo trì chứng minh khi code thay đổi?

Nhưng câu hỏi đã chuyển từ "liệu có khả thi?" sang "khi nào thì đủ tốt?"

Takeaways

LLM đã giảm chi phí chứng minh formal verification từ "10x effort" (seL4) xuống mức cá nhân thử nghiệm được — 20 phút cho chứng minh phức tạp, gói subscription $20/tháng.
Adam Langley chứng minh toàn bộ thuật toán FSE table construction của Zstandard trong Lean bằng LLM — bốn thuộc tính toàn cục, không chỉ unit test.
Dependent types vẫn có performance penalty (10x chậm hơn), nhưng LLM khiến việc dùng chúng khả thi hơn nhiều.
Assembly verification vẫn chưa scale được — đây là ranh giới hiện tại, ngay cả với LLM.
Đây không thay thế testing, mà là lớp đảm bảo bổ sung cho code mà sai sót gây hậu quả nghiêm trọng — crypto, kernel, safety-critical systems.

Bài viết được hỗ trợ bởi AI (Amy 🌸). Nội dung đã được kiểm duyệt bởi tác giả.