Bỏ qua tới nội dung chính

Trước khi có phương pháp hình thức

Phương pháp hình thức: chứng minh phần mềm đúng, thay vì chỉ chạy thử

Vì sao chạy thử không đủ cho phần mềm máy bay, tàu điện, con chip: đặc tả, bất biến vòng lặp, kiểm tra mô hình, kiểu dữ liệu như chứng minh nhỏ.

Ban biên tập OpenER

Cập nhật 09/11/2026 · 19 phút đọc · CC BY 4.0

Không ai kiểm tra một cây cầu chỉ bằng cách cho một nghìn chiếc xe tải chạy qua rồi tuyên bố "cầu chắc". Kỹ sư cầu đường tính trước: tải trọng, sức chịu của từng dầm, hệ số an toàn — và chỉ đổ bê tông khi các con số cho thấy cây cầu đứng vững với mọi tải trong giới hạn thiết kế.

Phần mềm thì phần lớn được làm theo cách ngược lại: viết xong, chạy thử vài chục trường hợp, thấy ổn thì đưa lên. Với một ứng dụng ghi chú, như vậy là đủ. Nhưng với phần mềm điều khiển cánh máy bay, đoàn tàu điện không người lái, mạch chia số trong con chip, hay hệ thống giữ ảnh của hàng triệu người trên đám mây, "chạy thử thấy ổn" là một lời hứa quá mỏng. Ở những chỗ đó, người ta làm như kỹ sư cầu đường: chứng minh bằng toán rằng chương trình đúng với mọi đầu vào. Đó là việc của phương pháp hình thức (formal methods).

Trước khi có phương pháp hình thức

Những lập trình viên đầu tiên kiểm tra chương trình bằng cách đọc lại thật kỹ và chạy thử — không cách nào cho biết chắc đã hết lỗi, như nhận xét của Dijkstra mà bài Toán rời rạc, logic và chứng minh đã nhắc. Câu trả lời cho "vậy chứng minh bằng cách nào?" đến dần từng bước:

  1. Turing, 1949. Trong bài nói ngắn Checking a Large Routine ở hội nghị khánh thành máy EDSAC tại Cambridge, Alan Turing đề nghị ghi kèm chương trình những khẳng định (assertion) về trạng thái của máy ở từng điểm, để kiểm riêng từng cái một. Ví dụ của ông là chương trình tính giai thừa chỉ bằng phép cộng, kèm lập luận rằng nó chắc chắn dừng. Bài nói gần như bị lãng quên suốt mấy chục năm.
  2. Floyd (1967) và Hoare (1969). Robert Floyd gắn khẳng định lên từng mũi tên của lưu đồ chương trình. Tony Hoare — người nghĩ ra quicksort — viết ý đó thành một hệ logic gọn: bộ ba Hoare (Hoare triple) {P} C {Q}, đọc là "nếu P đúng trước khi chạy C, thì Q đúng sau khi C chạy xong". Cả hai về sau nhận Giải Turing.
  3. Dijkstra, giữa thập niên 1970. Edsger Dijkstra đảo chiều: bắt đầu từ điều muốn đạt được, tính ngược ra điều kiện trước yếu nhất (weakest precondition) của từng câu lệnh, để chương trình và chứng minh lớn lên cùng nhau.
  4. Kiểm tra mô hình, 1981–1982. Edmund Clarke và Allen Emerson ở Mỹ, Jean-Pierre Queille và Joseph Sifakis ở Pháp, độc lập với nhau, đề xuất để máy tự duyệt mọi trạng thái của hệ thống và kiểm một tính chất viết bằng logic thời gian (temporal logic) — logic nói được "luôn luôn", "rồi sẽ có lúc", do Amir Pnueli đưa vào khoa học máy tính năm 1977. Clarke, Emerson và Sifakis nhận Giải Turing năm 2007.
  5. Lỗi chia của chip Pentium, 1994 — chuyện đã kể trong bài Toán rời rạc: chip đã bán thì không vá được như phần mềm. Không lâu sau, thuật toán chia số thực của chip AMD K5 được chứng minh đúng bằng trình chứng minh ACL2; ngày nay kiểm chứng hình thức là một khâu thường trực khi thiết kế chip.
  6. Chứng minh do máy kiểm, từ những năm 2000. Các trợ lý chứng minh (proof assistant) như Coq (nay là Rocq) và Isabelle kiểm từng bước những chứng minh dài hàng trăm nghìn dòng. Năm 2009, nhóm ở NICTA (Úc) công bố seL4, nhân hệ điều hành đa dụng đầu tiên có chứng minh rằng chính code C của nó — không chỉ bản thiết kế — làm đúng đặc tả. Ở Pháp, Xavier Leroy và cộng sự xây CompCert, trình biên dịch C có chứng minh rằng code máy sinh ra làm đúng điều code nguồn nói.

Đặt cạnh nhau:

Chỉ chạy thử
Có phương pháp hình thức
"Đúng" nghĩa là gì
Nằm trong đầu người viết và vài dòng mô tả
Viết thành đặc tả chính xác, ai đọc cũng hiểu một nghĩa
Bảo đảm cho
Những đầu vào đã thử
Mọi đầu vào, mọi thứ tự chạy xen kẽ — trong phạm vi mô hình
Lỗi đồng thời hiếm gặp
Thỉnh thoảng hiện ra, khó tái hiện
Công cụ in ra đúng chuỗi bước dẫn tới lỗi
Chi phí
Rẻ lúc đầu, rất đắt khi lỗi lọt ra ngoài
Đắt lúc đầu, cần người được đào tạo

Phần lớn phần mềm hôm nay vẫn nằm ở cột bên trái. Ngày 19/7/2024, một bản cập nhật cấu hình của phần mềm bảo mật CrowdStrike Falcon làm khoảng 8,5 triệu máy Windows cùng hiện màn hình xanh; sân bay, bệnh viện, ngân hàng ở nhiều nước đứng hình. Theo báo cáo của chính hãng, một mẫu dữ liệu mới khai báo 21 trường nhưng code dùng nó chỉ đưa vào 20 giá trị, nên chương trình đọc ra ngoài vùng nhớ. Lỗi lọt qua "nhiều lớp" kiểm thử. Sau sự cố, hãng cho máy kiểm ngay lúc biên dịch rằng hai con số đó bằng nhau — một điều kiện viết rõ ra, đúng với mọi bản cập nhật chứ không chỉ những bản đã thử.

Môn này trả lời câu hỏi gì

Môn này trả lời hai câu hỏi đi liền nhau:

  1. Nói thế nào cho chính xác một hệ thống phải làm gì, để không còn hai cách hiểu?
  2. Biết chắc thế nào rằng nó làm đúng như vậy — với mọi đầu vào, mọi cách các luồng chạy xen kẽ — thay vì chỉ với những trường hợp đã thử?

Ai đã đọc bài Lý thuyết tính toán có thể thấy lạ: định lý Rice nói mọi câu hỏi không tầm thường về hành vi của chương trình — kể cả "nó có làm đúng đặc tả không" — đều không có thuật toán nào trả lời đúng cho mọi chương trình. Phương pháp hình thức không cãi định lý đó, mà đi vòng: chứng minh cho một chương trình cụ thể, người dẫn đường còn máy kiểm từng bước; làm việc trên một mô hình hữu hạn, duyệt hết được; hoặc chấp nhận câu trả lời "chưa biết" — báo "có thể có lỗi" để người xem lại, nhưng không bao giờ nói "đúng" khi thật ra sai.

Vì sao cần học, kể cả khi bạn sẽ không bao giờ chứng minh trọn một chương trình lớn? Vì cách nghĩ của môn này — viết rõ điều kiện, nghĩ về mọi trạng thái chứ không chỉ trạng thái thường gặp — làm người ta viết code khác hẳn; và vì các công cụ "hình thức nhẹ" — hệ thống kiểu (type system), phân tích tĩnh (static analysis), ngôn ngữ đặc tả TLA+ của Leslie Lamport — đã vào công việc hằng ngày của kỹ sư phần mềm. Nó không thay thế kiểm thử; hai thứ bổ sung cho nhau, như bài Kiểm thử phần mềm sẽ nói rõ.

Năm ý tưởng cốt lõi

1. Đặc tả: nói chính xác "đúng" là gì

Muốn chứng minh một chương trình đúng, trước hết phải nói được "đúng" nghĩa là gì. Bản mô tả chính xác đó gọi là đặc tả (specification). Nghe hiển nhiên, nhưng đây thường là phần khó nhất. Thử với hàm sắp xếp: "kết quả phải tăng dần" — đã đủ chưa?

python
from collections import Counter

def sap_xep_luoi(ds):
    return []                                  # chẳng sắp gì cả

def tang_dan(kq):
    return all(kq[i] <= kq[i + 1] for i in range(len(kq) - 1))

def dung_dac_ta(dau_vao, kq):
    return tang_dan(kq) and Counter(kq) == Counter(dau_vao)   # tăng dần VÀ đủ phần tử cũ

ds = [3, 1, 2]
print(tang_dan(sap_xep_luoi(ds)))             # True  — đặc tả hở, hàm lười vẫn "đúng"
print(dung_dac_ta(ds, sap_xep_luoi(ds)))      # False — đặc tả đủ thì bắt được
print(dung_dac_ta(ds, sorted(ds)))            # True

Hàm sap_xep_luoi không làm gì mà vẫn thỏa đặc tả thứ nhất — vì danh sách rỗng thì, về mặt logic, tăng dần. Đặc tả đúng phải có hai vế: kết quả tăng dần, và là một hoán vị của đầu vào, tức đủ mọi phần tử cũ, mỗi phần tử đúng số lần. Đặc tả hở cho ra chương trình "đúng" mà vô dụng, và mọi chứng minh dựa trên nó cũng vô dụng theo.

Với một hàm, đặc tả thường gồm tiền điều kiện (precondition) — điều người gọi phải bảo đảm — và hậu điều kiện (postcondition) — điều hàm hứa trả lại. Với cả một hệ thống, đặc tả mô tả các trạng thái và những bước chuyển được phép. Lợi ích đầu tiên đến trước cả khi chạy công cụ: buộc phải viết rõ ra là lộ ngay những chỗ thiết kế mơ hồ.

2. Bất biến vòng lặp: một chứng minh cho vô số lần chạy

Vòng lặp có thể chạy một lần hay một tỷ lần, nên là chỗ khó tin nhất của chương trình. Bí quyết từ Turing và Hoare là tìm một bất biến vòng lặp (loop invariant) — điều đúng trước vòng đầu tiên và vẫn đúng sau mỗi vòng. Bài Toán rời rạc đã giới thiệu khái niệm này; ở đây ta dùng nó thật, trên chính ví dụ trong bài báo năm 1969 của Hoare: chia lấy thương và dư chỉ bằng phép trừ.

python
def chia(x, y):
    """Tiền điều kiện: x >= 0 và y > 0.  Hậu điều kiện: x == q*y + r và 0 <= r < y."""
    assert x >= 0 and y > 0
    q, r = 0, x
    while r >= y:
        assert x == q * y + r and r >= 0      # bất biến: đúng ở đầu mỗi vòng lặp
        q, r = q + 1, r - y
    assert x == q * y + r and 0 <= r < y      # bất biến + điều kiện dừng = hậu điều kiện
    return q, r

print(chia(17, 5))                            # (3, 2)
for x in range(200):                          # thử 9.800 cặp: không assert nào hỏng
    for y in range(1, 50):
        chia(x, y)
print("ổn")

Bất biến là x = q·y + r với r ≥ 0. Chứng minh có ba bước, cùng khuôn với quy nạp:

  • Lúc bắt đầu: q = 0, r = x, nên q·y + r = x. Đúng.
  • Mỗi vòng giữ nó: sau một vòng, (q + 1)·y + (r − y) = q·y + r, vẫn bằng x; và vì chỉ vào vòng khi r ≥ y, nên r − y vẫn không âm.
  • Khi thoát: điều kiện lặp sai, tức r < y. Ghép với bất biến là ra đúng hậu điều kiện.

Còn phải chứng minh vòng lặp dừng: mỗi vòng r giảm đi y > 0 mà không bao giờ âm, nên không thể giảm mãi. Đại lượng giảm dần như vậy gọi là biến thiên (variant).

Để ý chỗ khác nhau: vòng for thử 9.800 cặp số không lỗi, nhưng đó vẫn là kiểm thử, chỉ nói về chừng ấy cặp; ba bước lập luận thì nói về mọi x ≥ 0 và y > 0. Những công cụ như Dafny hay Why3 cho viết bất biến ngay trong code, rồi chuyển từng bước chứng minh cho một bộ giải SMT (SMT solver) kiểm; bước nào không qua, công cụ chỉ đúng dòng đó.

3. Kiểm tra mô hình: để máy duyệt mọi trạng thái

Lỗi đồng thời — hai luồng giẫm lên nhau, như trong bài Hệ điều hành — là nơi kiểm thử yếu nhất: lỗi chỉ hiện ra với một thứ tự chạy hiếm. Kiểm tra mô hình (model checking) không chờ thứ tự xấu tự xảy ra, mà liệt kê mọi thứ tự.

Thử với một cách khóa ngây thơ. Mỗi luồng có một lá cờ. Muốn vào đoạn găng (critical section) — đoạn code mỗi lúc chỉ được một luồng chạy — luồng chờ tới khi cờ của luồng kia hạ, rồi giơ cờ của mình và đi vào; ra thì hạ cờ. Nghe ổn. Đoạn code dưới đây viết giao thức đó thành các trạng thái, rồi duyệt theo chiều rộng (breadth-first search) mọi cách hai luồng đi xen kẽ:

python
from collections import deque

def buoc(s, i):
    """Luồng i đi một bước. s = (vị trí luồng 0, vị trí luồng 1, cờ luồng 0, cờ luồng 1)."""
    vt, co, j = [s[0], s[1]], [s[2], s[3]], 1 - i
    if vt[i] == 0:                     # 0: chờ tới khi luồng kia hạ cờ
        if not co[j]:
            vt[i] = 1
    elif vt[i] == 1:                   # 1: giơ cờ của mình
        co[i], vt[i] = True, 2
    elif vt[i] == 2:                   # 2: đang ở trong đoạn găng
        vt[i] = 3
    else:                              # 3: hạ cờ, quay lại từ đầu
        co[i], vt[i] = False, 0
    return (vt[0], vt[1], co[0], co[1])

def tim_loi(dau):
    truoc, hang = {dau: None}, deque([dau])   # truoc: trạng thái nào dẫn tới trạng thái này
    while hang:
        s = hang.popleft()
        if s[0] == 2 and s[1] == 2:           # cả hai cùng ở đoạn găng: vi phạm
            vet = []
            while s is not None:
                vet.append(s)
                s = truoc[s]
            return vet[::-1]
        for i in (0, 1):                      # thử mọi cách xen kẽ: luồng 0 hoặc luồng 1 đi
            t = buoc(s, i)
            if t not in truoc:
                truoc[t] = s
                hang.append(t)
    return None

for s in tim_loi((0, 0, False, False)):
    print(s)

Kết quả:

text
(0, 0, False, False)
(1, 0, False, False)
(1, 1, False, False)
(2, 1, True, False)
(2, 2, True, True)

Đọc từng dòng: luồng 0 thấy cờ của luồng 1 đang hạ nên đi qua; trước khi nó kịp giơ cờ, luồng 1 cũng thấy cờ của luồng 0 đang hạ, cũng đi qua. Rồi cả hai giơ cờ và cùng vào đoạn găng — lỗi nằm trong khe hở giữa "nhìn" và "giơ cờ". Công cụ không chỉ báo "có lỗi" mà in ra phản ví dụ (counterexample): chuỗi bước ngắn nhất dẫn tới lỗi, vì duyệt theo chiều rộng luôn gặp đường ngắn nhất trước.

Cả giao thức chỉ có 16 trạng thái tới được. Đổi sang thuật toán Peterson (1981), thêm một biến "nhường lượt", công cụ duyệt hết 26 trạng thái và không thấy trạng thái nào có hai luồng cùng ở đoạn găng — với mô hình hữu hạn, duyệt hết tức là chứng minh. Các công cụ thật như SPIN, NuSMV hay TLC (bộ kiểm tra của TLA+) làm đúng việc này, kèm nhiều kỹ thuật chống kẻ thù số một: bùng nổ trạng thái (state explosion) — mỗi biến, mỗi luồng thêm vào lại nhân số trạng thái lên nhiều lần.

4. Kiểu dữ liệu: những chứng minh nhỏ chạy mỗi lần biên dịch

Có thể bạn đã dùng phương pháp hình thức mà không biết: mỗi lần trình biên dịch báo lỗi kiểu. Hệ thống kiểu là một cỗ máy chứng minh nhỏ: nó chứng minh vài tính chất cho mọi lần chạy — không bao giờ gọi hàm với sai loại tham số, không bao giờ cộng một chuỗi với một ngày tháng — mà không cần chạy.

Ví dụ quen thuộc là giá trị rỗng null. Chính Tony Hoare đưa tham chiếu rỗng vào ngôn ngữ ALGOL W năm 1965, và năm 2009 ông gọi nó là "sai lầm tỷ đô" của mình, vì vô số chương trình đã sập do quên rằng một biến có thể rỗng. TypeScript ở chế độ strict biến "có thể rỗng" thành một phần của kiểu, và từ chối chương trình quên kiểm tra:

ts
function timTen(id: number): string | null {
  return id === 1 ? "Lan" : null;       // không có người dùng thì trả về null
}

const ten = timTen(2);
console.log(ten.toUpperCase());         // tsc báo lỗi ngay, trước khi chạy

if (ten !== null) {
  console.log(ten.toUpperCase());       // qua: trong nhánh này ten chắc chắn là chuỗi
}

Trình biên dịch tsc dừng ở dòng thứ sáu với lỗi 'ten' is possibly 'null' — trước khi người dùng nào kịp gặp.

Quan hệ giữa kiểu và chứng minh còn sâu hơn thế: theo tương ứng Curry–Howard (Curry–Howard correspondence), một kiểu đọc được như một mệnh đề, và chương trình có kiểu đó là một chứng minh của mệnh đề — nền của Rocq và Lean. Ở đầu thực dụng, hệ thống kiểu của Rust chứng minh lúc biên dịch rằng phần code "an toàn" không có tranh chấp dữ liệu giữa các luồng và không dùng lại vùng nhớ đã giải phóng — loại lỗi an toàn bộ nhớ (memory safety) mà bài Bảo mật phần mềm kể là gốc của phần lớn lỗ hổng nghiêm trọng.

5. Đáng công ở đâu: chi phí, lợi ích và giới hạn

Chứng minh không miễn phí. seL4 có khoảng 8.700 dòng C, nhưng phần chứng minh dài khoảng 200.000 dòng. Viết nhân mất khoảng 2 người-năm; chứng minh riêng cho nó mất khoảng 11 người-năm, chưa kể công làm công cụ. Không ai làm vậy cho một trang web bán hàng. Câu hỏi thật là dùng tới mức nào, cho phần nào:

  • Nhẹ, gần như miễn phí: hệ thống kiểu chặt, phân tích tĩnh, assert ghi rõ tiền và hậu điều kiện.
  • Vừa: đặc tả thiết kế bằng TLA+ rồi kiểm tra mô hình — vài tuần công cho một giao thức khó.
  • Nặng: chứng minh trọn code bằng trợ lý chứng minh — cho phần lõi nhỏ mà mọi thứ khác dựa vào, như nhân hệ điều hành, trình biên dịch, thư viện mật mã.

Phương pháp hình thức đáng công nhất ở nơi lỗi vừa đắt vừa khó vá. Tuyến số 14 của tàu điện ngầm Paris chạy không người lái từ năm 1998; phần mềm an toàn của nó được phát triển bằng phương pháp B (B method) của Jean-Raymond Abrial — khoảng 86.000 dòng Ada sinh ra từ mô hình đã chứng minh — và theo nhóm phát triển, chưa phát hiện lỗi nào ở phần đã chứng minh. Airbus dùng bộ phân tích tĩnh Astrée để chứng minh phần mềm điều khiển bay viết bằng C không có lỗi lúc chạy như tràn số hay chia cho không.

Và một giới hạn cần nhớ: chứng minh chỉ đúng với mô hình và đặc tả nó dựa vào. Năm 2006, Joshua Bloch ở Google kể rằng hàm tìm kiếm nhị phân trong thư viện chuẩn Java đã sai suốt khoảng chín năm — và lỗi y hệt nằm trong phiên bản mà sách Programming Pearls của Jon Bentley chứng minh là đúng. Lập luận coi số nguyên là vô hạn; trong Java, int chỉ có 32 bit, nên với mảng cỡ hơn một tỷ phần tử, phép tính (trai + phai) / 2 tràn thành số âm. (Dòng tương tự trong bài Thiết kế và phân tích thuật toán chạy đúng, vì số nguyên Python không tràn.) Chứng minh không sai; mô hình đã thiếu một sự thật về máy. Mô hình ở ý 3 cũng thế: nó coi các lệnh đọc ghi chạy đúng thứ tự đã viết, trong khi bộ xử lý hiện đại có thể đảo thứ tự — code Peterson thật cần thêm rào bộ nhớ (memory barrier).

Phương pháp hình thức nằm ở đâu trong chồng tầng

Trong chồng tầng của bài Từ electron đến ứng dụng, mỗi tầng hứa với tầng trên một hợp đồng: tập lệnh hứa chạy đúng từng lệnh, trình biên dịch hứa giữ nguyên ý nghĩa của code. Phương pháp hình thức không là một tầng riêng, mà là cách biến những lời hứa đó thành định lý ở tầng nào cũng được: bộ chia trong chip (bài Kiến trúc máy tính), nhân hệ điều hành với seL4, trình biên dịch với CompCert, giao thức hệ phân tán với TLA+. Các lời hứa đã chứng minh nối thành một chuỗi bảo đảm từ code nguồn xuống phần cứng; mắt xích nào chưa chứng minh vẫn có thể đứt.

Đưa lên

Một bảo đảm có chứng minh — thành phần bên dưới làm đúng bản đặc tả với mọi đầu vào — để tầng trên chỉ cần đọc và tin bản đặc tả ngắn, không phải đọc hàng nghìn dòng code.

Giấu đi

Hàng chục nghìn dòng chứng minh và mọi chi tiết cài đặt — nhưng không giấu được giả định của mô hình: phần cứng chạy đúng, đặc tả nói đúng điều ta muốn. Giả định sai thì bảo đảm cũng mất.

Học trước và học sau

· 6 môn

Toán rời rạc, logic và chứng minh

Mathematics for Computer Science

Quy nạp, logic vị từ, cách viết chứng minh. Bất biến vòng lặp chính là quy nạp mặc áo lập trình. Học trước.

Xem chủ đề trên OpenER: Mathematics for Computer Science

Logic cho khoa học máy tính

Logic for Computer Science

Logic mệnh đề, logic vị từ, bài toán SAT — ngôn ngữ để viết đặc tả và động cơ bên trong các công cụ kiểm chứng.

Xem chủ đề trên OpenER: Logic for Computer Science

Kiểm thử phần mềm

Software Testing

Người anh em thực dụng: kiểm thử tìm lỗi trên code thật, môi trường thật; phương pháp hình thức bảo đảm cho mọi trường hợp trong mô hình. Nên học cả hai.

Xem chủ đề trên OpenER: Software Testing

Lý thuyết tính toán

Theory of Computation

Máy trạng thái hữu hạn và định lý Rice: vì sao kiểm tra mô hình làm được, và vì sao không có công cụ kiểm chứng vạn năng.

Xem chủ đề trên OpenER: Theory of Computation

Ngôn ngữ lập trình và trình biên dịch

Programming Languages and Compilers

Hệ thống kiểu và ngữ nghĩa — nơi "chương trình này nghĩa là gì" được định nghĩa đủ chính xác để chứng minh.

Xem chủ đề trên OpenER: Programming Languages and Compilers

Hệ phân tán

Distributed Systems

Giao thức đồng thuận, sao chép dữ liệu — nơi lỗi hiếm mà đắt nhất, sân chơi chính của TLA+.

Xem chủ đề trên OpenER: Distributed Systems

Ứng dụng thật và nghề nghiệp

  • Hệ thống đám mây: từ năm 2011, kỹ sư Amazon Web Services dùng TLA+ để kiểm thiết kế của S3, DynamoDB và nhiều hệ thống khác; bài báo năm 2015 của nhóm kể về những lỗi tinh vi mà kiểm thử và đọc code bỏ sót — có lỗi trong DynamoDB phải qua 35 bước mới lộ ra.
  • Trình biên dịch: năm 2011, một nhóm ở Đại học Utah sinh chương trình C ngẫu nhiên để thử, tìm ra hơn 325 lỗi trong các trình biên dịch như GCC và LLVM; ở phần đã chứng minh của CompCert, họ không tìm thấy lỗi sinh code sai nào.
  • Thiết kế chip: kỹ sư kiểm chứng hình thức (formal verification engineer) là một nghề riêng ở các công ty chip, kể cả các trung tâm thiết kế vi mạch ở Việt Nam.
  • Hợp đồng thông minh (smart contract): code trên blockchain không sửa được sau khi triển khai, nên kiểm chứng trước là lớp phòng thủ chính.

Học xong làm được gì, bắt đầu từ đâu

Sau môn này bạn có thể:

  • viết đặc tả chính xác cho một hàm hay một giao thức, và nhận ra đặc tả hở;
  • tìm bất biến vòng lặp, chứng minh một thuật toán ngắn và để Dafny hay Why3 kiểm lại;
  • đặc tả một giao thức đồng thời bằng TLA+ và dùng bộ kiểm tra mô hình tìm phản ví dụ;
  • dùng hệ thống kiểu để loại bỏ cả một họ lỗi;
  • biết phần nào của hệ thống đáng chứng minh, phần nào kiểm thử là đủ.

Nên biết trước: logic mệnh đề và logic vị từ, quy nạp, và lập trình vững ở một ngôn ngữ. Đây là môn nâng cao.

Bắt đầu trên OpenER: trang chủ đề Formal Methods for Software Engineering có các khóa học đã chọn lọc, và hướng dẫn học gợi ý thứ tự đi qua chúng. Khóa chính là Formal Methods for System Verification của IIT Guwahati trên NPTEL (logic, bộ giải SAT, logic thời gian, kiểm tra mô hình với NuSMV); có thêm một khóa tiếng Việt để khởi động, và môn Bug Catching (15-414) của Carnegie Mellon cho hướng chứng minh chương trình bằng Why3. Lời khuyên: bắt đầu nhỏ, và bắt đầu từ thiết kế — đặc tả một giao thức bạn từng viết bằng TLA+ trong vài chục dòng, rồi để bộ kiểm tra mô hình đi tìm lỗi. Lần đầu nó in ra một phản ví dụ bạn chưa từng nghĩ tới, bạn sẽ hiểu vì sao người ta chịu bỏ công.

Tài liệu tham khảo

  • Leslie Lamport — Specifying Systems: The TLA+ Language and Tools for Hardware and Software Engineers, bản PDF miễn phí trên trang của tác giả.
  • Christel Baier, Joost-Pieter Katoen — Principles of Model Checking, MIT Press.
  • Benjamin C. Pierce và cộng sự — Software Foundations, bộ sách mở dùng Coq/Rocq của Đại học Pennsylvania.
  • IIT Guwahati — Formal Methods for System Verification (Chandan Karfa), khóa học trên NPTEL.
  • Carnegie Mellon 15-414 Bug Catching: Automated Program Verification.
  • MIT 6.820 Fundamentals of Program Analysis — bài giảng mở trên MIT OpenCourseWare.
  • C. A. R. Hoare — "An Axiomatic Basis for Computer Programming", Communications of the ACM, 1969.
  • Chris Newcombe và cộng sự — "How Amazon Web Services Uses Formal Methods", Communications of the ACM, 2015.