跳到正文
Hacker News (official RSS)(broyojo.com)·· 13 天前精選品質評分86

Formalizing CPython:以 Lean 建模 CPython 並回報 418 項錯誤

Formalizing CPython

重點導讀

Formalizing CPython 專案以 Lean 逐行建模 CPython 3.15.2,透過測試、機器證明與獨立審查驗證模型,並據此提交了 418 項錯誤報告。

AI 伴隨問答

自備 Key 深度分析

針對這篇報導有疑問?可直接點選快捷問題或向 AI 追問背景脈絡與技術細節:

推薦理由

文章呈現以逐行建模、差異測試、機器證明與獨立審查檢查大型程式碼庫的流程,並以 CPython 案例說明各環節如何協助找出錯誤。

正文 · 中文翻譯

AI 代理逐行複製 Python 的內部實作,寫出 613,318 行 Lean 程式碼,每一部分都對照真正的 Python 進行測試,每個證明都由電腦檢查,過程中還找出 Python 的 418 項錯誤。

CPython · Objects/rangeobject.c

static unsigned longget_len_of_range(long lo, long hi, long step){    assert(step != 0);    if (step > 0 && lo < hi)        return 1UL + (hi - 1UL - lo) / step;    else if (step < 0 && lo > hi)        return 1UL + (lo - 1UL - hi) / (0UL - step);    else        return 0UL;}

Lean 複製版 · RangeSlice/Model.lean

def getLenOfRange (lo hi step : Int) : Int :=  if step > 0 ∧ lo < hi then    uadd 1 (usub (usub (toU hi) 1) (toU lo) / toU step)  else if step < 0 ∧ lo > hi then    uadd 1 (usub (usub (toU lo) 1) (toU hi)              / usub 0 (toU step))  else 0 -- step ≠ 0 is assumed by every proof-- uadd, usub: C's unsigned arithmetic,-- which wraps around past 2^64
左側是 CPython C 原始碼中的函式,右側是代理撰寫的 Lean 複製版。將遊標移到某一行,即可檢視對應的程式碼。

重點摘要

  • 我們讓 Opus 5.5 檢視執行幾乎所有 Python 程式碼的 CPython,並將其中的函式改寫成 Lean,這是一種用來撰寫可由機器檢查之證明的語言。
  • 每次改寫都會逐行複製原始程式碼,並在數萬筆輸入上對照真正的 Python 進行測試,之後才開始嘗試證明任何性質。
  • 只有在另一個未參與撰寫的代理檢查並認可成果後,函式才算完成。目前已有 4,071 個函式通過檢查。
  • 成果涵蓋 1,539 個檔案,共 613,318 行 Lean 程式碼,包含 18,898 個定理與引理;每次建置時都會由 Lean 的證明檢查器逐一檢查。
  • 證明過程中共找出 418 項錯誤並提交回報。大多數問題不大,但約有 55 項可能讓直譯器當機,或因一般 Python 程式碼而破壞記憶體。

已檢查並接受已撰寫,尚未接受尚未開始

  • 整個 CPython16%
  • 直譯器核心10%
  • 內建型別35%
  • C 模組19%
  • 剖析器31%
  • 文法規則100%
  • 標準函式庫9%
CPython 3.15.2 各部分中,已完成複製、測試、證明並通過審查的比例。不需要檢查的程式碼,例如記憶體帳務管理,並未納入。

為什麼要做

Python 沒有精確的書面定義。雖然有參考手冊,但實際上,「Python」指的就是 CPython 的行為,而 CPython 是數十萬行 C 程式碼加上大型標準函式庫。手冊涵蓋一般用法,對於各種特殊情況卻少有說明,而錯誤往往就藏在這些地方:物件在字典搜尋它時修改字典、更新到一半時丟擲錯誤,或是數值比 C 程式碼原本設計可處理的最大值多一。

為函式撰寫證明,會迫使你明確說明它在所有這些情況下的行為。你不能含糊帶過,因為證明檢查器不會接受。這讓證明成為找出程式碼與大家預期不符之處的好方法。

我們想了解,這種做法用在像 CPython 這樣規模龐大、歷史悠久的程式碼庫上能做到什麼程度,以及大部分工作由 AI 完成時,結果是否仍值得信賴。

運作方式

每個函式都會經過相同的四個步驟。

  1. 複製以 Lean 改寫函式,逐行遵循原始程式碼,包括錯誤訊息與特殊情況。
  2. 測試至少用 50,000 筆棘手輸入,讓複製版與真正的 Python 並行執行。只要結果不一致,複製版就有錯。
  3. 證明陳述一項應該永遠成立的性質,並讓電腦檢查證明。如果該性質其實不成立,就改為證明這一點。
  4. 檢查由未參與工作的第二個代理根據原始程式碼審查成果,並嘗試找出問題。只有通過檢驗的成果才會列入統計。

本頁頂端的程式碼,是 CPython 一小部分功能的第一步:計算 range 中有多少個數字的 C 函式,旁邊則是它的 Lean 版本。這份 Lean 版本保留了 C 程式碼的精確算術行為,包括數字過大時如何溢位。相關證明顯示,這個函式、CPython 用來處理超大數字的較慢版本,以及在兩者之間做選擇的程式碼,都會算出相同且正確的數量。

證明瞭卻什麼也沒證明的證明

最難的不是讓 AI 代理撰寫證明,而是讓證明真正有意義。

我們第一次嘗試時,要求代理廣泛涵蓋:複製每個函式,並至少證明每個函式的一件事。它們做到了。接著,另一組人員進行審查,發現受檢函式中不到一半經得起檢驗,有個檔案甚至只有 21%。這些證明全都正確,只是沒有說明任何有用的事。例如,「如果這個函式傳回數字,該數字就至少是零」這句話是對的,但永遠當機的函式也符合這項敘述。

因此,現在審查者會針對每個證明提出一個問題:函式即使有錯,能不能也通過這項證明?

函式版本「如果有傳回,答案就 ≥ 0」「一定會傳回正確的數量」
實際版本通過通過
永遠當機通過抓出錯誤
超大數字時傳回 0通過抓出錯誤
倒數時差 1通過抓出錯誤
關於同一個函式的兩個正確敘述。第一個敘述讓所有錯誤版本都能通過,因此如果某個函式唯一的證明看起來像這樣,就等於沒有證明任何事。

要補強薄弱的證明,通常得回頭讓複製版本更貼近實際情況,例如允許使用者的程式碼在函式執行途中擲出錯誤。下方圖表顯示十個檔案的審查結果。每個點代表一輪審查。曲線有時會下降:當審查者發現已接受的證明與實際 Python 行為不符時,所有依賴該證明的內容都會撤回。

已接受的函式

Objects/typeobject.c135 個中接受 142 個 · 5 輪審查
Objects/genobject.c56 個中接受 56 個 · 5 輪審查
Objects/setobject.c46 個中接受 46 個 · 7 輪審查
Modules/_json.c48 個中接受 45 個 · 5 輪審查
Lib/enum.py39 個中接受 37 個 · 9 輪審查
Lib/random.py38 個中接受 37 個 · 3 輪審查
Objects/abstract.c43 個中接受 41 個 · 2 輪審查
Objects/rangeobject.c33 個中接受 33 個 · 2 輪審查
Lib/pickletools.py33 個中接受 31 個 · 2 輪審查
Modules/binascii.c40 個中接受 35 個 · 2 輪審查

審查輪次 →

根據專案歷史記錄,各檔案每輪審查後,受審函式中獲接受的比例。每個點代表一輪審查;所有圖表的刻度相同,從 0% 到該檔案所有受審函式。獲接受的函式也包括審查者確認無需檢查的函式,例如記憶體記帳作業。

正確的證明為何仍可能是錯的

經過檢查的證明能保證某個敘述可以從複製版本推匯出來,卻不能保證複製版本符合實際 Python 行為;測試也只能涵蓋你想到要嘗試的輸入。因此,每個獲接受的敘述也都會拿來對照實際 Python 執行。這個做法抓出好幾個雖然有效、結果卻仍然錯誤的證明。

16 TB 的字串

Python 快速 JSON 編碼器的複製版本假設記憶體要求一定會成功。因此,它「證明」編碼器能為任意巢狀深度建立縮排字串,包括需要 16 TB 記憶體的情況。實際的 Python 會因記憶體不足而失敗。修正後的複製版本現在會將每次記憶體要求都視為可能失敗。

只多出九層呼叫,而且只發生一次

一份證明指出,Python 的 pickle 模組在巢狀呼叫深度上有上限。結果發現,這個說法唯獨在全新的 Python 程式中不成立。該程式第一次編碼字串時,會悄悄載入文字編碼器,而載入過程又多出九層巢狀呼叫。我們的測試從未發現這個問題,因為測試工具早已載入該編碼器。

錯誤型別也有家族

在 Python 中,捕捉 TypeError 時,也會捕捉任何以它為基礎建立的更具體錯誤型別。有三份不同的副本都檢查錯誤的確切名稱。這三份副本都有證明指出,自訂錯誤型別可能造成問題。

重新出現的記憶體

Python 的 set 副本假設記憶體釋出後,相同位址就不會再次出現。實際上,記憶體配置器經常重複使用位址。CPython 會透過檢查「位址是否改變?」來偵測使用者程式碼是否替換了集合的內部結構。若位址被重複使用,這項檢查就可能被騙過。修正這份副本後,原本通過的證明揭露了一個真正的記憶體錯誤,如今已成為我們提交的錯誤回報之一。

我們的發現

如果證明失敗是因為 Python 本身有問題,而非副本有誤,我們就會將問題整理成錯誤回報。每份回報都會附上簡短的程式碼,在 Python 3.15.2(多數問題也能在開發版本中)重現錯誤;搜尋是否已有重複回報;並誠實評估問題的嚴重程度。

  • C 與 Python 版本結果不一致129
  • 其他122
  • 結果錯誤56
  • 當機28
  • 記憶體毀損27
  • 與檔案說明不符26
  • 錯誤型別或訊息錯誤18
  • 缺少輸入檢查12
依型別分類的 418 份錯誤回報。「C 與 Python 版本結果不一致」表示某個模組有兩種實作方式:以 C 撰寫的快速版本,以及備用的 Python 版本,而兩者對同一呼叫給出不同答案。

多數問題都很小:錯誤訊息有誤、邊界情況的行為與檔案說明不同,或是同一函式的兩個版本結果不一致。約有 55 個問題較為嚴重,能只靠一般 Python 程式碼讓 Python 當機或毀損記憶體;通常是使用者程式碼在 C 程式碼使用容器的過程中修改了容器。Python 不把執行有惡意的 Python 程式碼視為安全性邊界,因此這些都屬於一般錯誤。尚未列在 CPython 問題追蹤系統中的問題,都會回報給專案團隊,這篇文章便是起點。以下是六個不同型別的小範例:

當機

導致 Python 當機的字典呼叫

如果同一類別的另一個物件有該屬性,而這個物件沒有,對物件的屬性字典呼叫 setdefault 並使用 StrEnum 索引鍵,就會讓直譯器當機。

class Key(StrEnum):
    NAME = "name"
class User: pass
a = User(); a.name = "ada"
b = User(); b.age = 36
vars(b).setdefault(Key.NAME, "anon")
# Segmentation fault

記憶體毀損

毀損記憶體的 XML 編輯操作

對 ElementTree 元素的反向切片進行指定,理應像對串列操作一樣插入專案,實際上卻會複製其中一個子元素但未增加參照計數,並遺失另一個子元素。

e = ET.Element("root")
e[:] = [ET.Element(f"a{i}") for i in range(7)]
e[5:2] = [ET.Element("X")]
[c.tag for c in e]
# 'a2' appears twice, 'a4' is gone

錯誤型別錯誤

讓剖析器出錯的電子郵件標頭

Message-ID 在方括號內含有空格時,Python 的電子郵件剖析器會因內部錯誤而失敗。這個標頭來自電子郵件寄件者。

msg = email.message_from_string(
    "Message-ID: <a@[ x]>\n\nhi\n",
    policy=policy.default)
msg["Message-ID"]
# UnboundLocalError

結果悄悄出錯

Base32 填補字元會因位置而影響結果

Python 3.15 新增的功能允許 Base32 解碼器忽略指定字元。如果 = 是其中一個指定字元,它出現的位置仍會改變解碼結果。

a2b_base32(b"AAAAAAA",  ignorechars=b"=")
# Error: Incorrect padding
a2b_base32(b"AAAA=AAA", ignorechars=b"=")
# b'\x00\x00\x00\x00'

缺少錯誤

消失的列舉錯誤

給第二個成員指定列舉值應該會引發錯誤。如果類別的 __repr__ 損壞,錯誤會被吞掉,呼叫也會悄悄地什麼都不做。

class W(Enum):
    A = 1; B = 2
    def __repr__(self): return 5
W.B._add_value_alias_(3)
W.A._add_value_alias_(3)  # returns None

C 和 Python 意見不合

兩種 pickler,兩種限制

Python 有 C 語言版 pickler 和純 Python 版 pickler。它們在不同的巢狀深度就會放棄。這項差異於 2008 年首次回報,至今仍未解決。

v = []
for _ in range(400): v = [v]
pickle.dumps(v, 5)    # works
pickle._dumps(v, 5)   # RecursionError

每份回報及其指令碼都在程式碼儲存庫裡。

為自己的專案這樣做

這些做法並非 Python 專用。只要有可閱讀的原始碼和可執行的版本,就適用於任何東西:其他語言、程式庫、檔案格式、編譯器。對我們來說,以下做法帶來了差異:

  1. 選定一個明確的版本並堅持使用。每份副本都要指向該版本中的特定程式碼行。
  2. 先列出所有專案。依完整清單計算進度,避免任何專案悄悄被跳過。
  3. 複製程式碼,而非檔案。根據檔案撰寫的副本會與檔案一致,而錯誤正是出在程式碼與檔案不一致之處。
  4. 讓使用者程式碼出錯。模擬會引發錯誤或在操作途中變更狀態的回呼。最嚴重的錯誤就出在這些地方。
  5. 先測試,再證明。針對錯誤副本進行證明,只會浪費時間。
  6. 如果某項陳述不成立,就保留反例。不要把陳述改得過於寬鬆,直到它變得可證明為止。
  7. 用實際版本檢查已證明的陳述。針對錯誤副本做出有效證明,是最具誤導性的結果。
  8. 只計入獨立審查者接受的成果,並請審查者確認有缺陷的版本是否也會通過。

我們的代理程式據以工作的指示放在程式碼儲存庫裡,並設計成可重複使用:供執行工作的代理程式參考的 AGENTS.md、供審查者使用的 REVIEW_PROMPT.md,以及列出所有函式及其狀態的完整清單 coverage/methods。

相關工作

最接近的專案是 julia-in-lean,它以這種方式處理 Julia 語言,並直接啟發了本專案1。該專案在 Lean 中建模 Julia 標準程式庫,使用 Julia 測試這些模型,記錄約 400 個錯誤,並提交了 75 個錯誤回報。它發現 130 個快速證明中有 128 個悄悄避開了困難案例,這項發現形塑了我們的審查規則。近期有一篇論文在 Lean 中建模 NVIDIA 的 PTX GPU 指令集,以證明 GPU 核心正確2,並延續先前對 PTX 記憶體模型的形式化研究3。

就 Python 而言,λπ4 和 Python 3.3 的 K framework 語意5都以數學方式描述了這門語言;本專案則直接複製 CPython 的實際程式碼。JavaScript6,7 和 WebAssembly8 也有類似工作,而 CompCert9 和 seL410 仍是完全驗證軟體的高標。比較兩種實作在相同輸入下的結果,也就是本專案的測試部分,已有數十年歷史11,12。

目前進展

本專案於 2026 年 10 月 29 日啟動。值得檢查的 26,004 個函式中,已有 4,071 個(15.7%)完成複製、測試、證明並通過審查。Lean 程式碼共 1,539 個檔案、613,318 行,包含 18,898 個定理與引理;頂層屬性中有 3,834 個已證明,另有 588 個已透過反例證明為假。Python 的大部分內容仍待處理,尤其是以 Python 本身撰寫的標準函式庫大部分內容。目前不在範圍內的是多執行緒。在這 57 個檔案中,目前已複製的每個函式都已通過審查。以下列出已接受函式數量最多的 30 個檔案:

  • Python/bytecodes.c310
  • Grammar/python.gram278
  • Lib/collections/__init__.py184
  • Lib/_pydecimal.py160
  • Lib/_pydatetime.py150
  • Modules/_struct.c122
  • Objects/longobject.c119
  • Objects/listobject.c114
  • Objects/memoryobject.c107
  • Objects/dictobject.c104
  • Objects/bytesobject.c100
  • Objects/exceptions.c97
  • Objects/unicodeobject.c94
  • Objects/bytearrayobject.c93
  • Modules/arraymodule.c84
  • Lib/_collections_abc.py81
  • Modules/_operator.c73
  • Modules/itertoolsmodule.c72
  • Modules/_collectionsmodule.c64
  • Python/codecs.c61
  • Lib/operator.py59
  • Lib/_pyio.py58
  • Objects/typeobject.c57
  • Lib/weakref.py54
  • Objects/genobject.c46
  • Lib/urllib/parse.py46
  • Parser/action_helpers.c43
  • Modules/_zoneinfo.c43
  • Objects/floatobject.c38
  • Objects/tupleobject.c37

本專案開放參與,歡迎協助。CPython 的大部分內容仍未建模:請在 coverage/methods 中挑選函式仍標示為 todo 的檔案,依照 AGENTS.md 操作,並提交 pull request。對現有成果進行獨立審查,與建立新模型同樣重要。請參閱 CONTRIBUTING.md。

引用

@misc{andrews2026formalizing,
  author       = {Andrews, David and Zhang, Chao},
  title        = {Formalizing {CPython}: A Lean Model of {CPython} 3.15.2},
  year         = {2026},
  howpublished = {\url{https://broyojo.com/python-formalization/}},
  note         = {Code: \url{https://github.com/Broyojo/python-formalization}}
}

參考資料

  1. M. Cranmer。使用 Lean 形式化 Julia(並在 Base 中找出 400 多個錯誤)。Julia Discourse,2026。程式碼:MilesCranmer/julia-in-lean。
  2. L. Koska、T. Koska、B. Koska。使用 Lean 形式化 PTX,以證明 GPU 核心的正確性。arXiv:2611.04447,2026。
  3. D. Lustig、S. Sahasrabuddhe、O. Giroux。NVIDIA PTX 記憶體一致性模型的形式化分析。ASPLOS 2019。
  4. J. G. Politz、A. Martinez、M. Milano、S. Warren、D. Patterson、J. Li、A. Chitipothu、S. Krishnamurthi。Python:完整解析。Python 程式語言經測試的語意。OOPSLA 2013。
  5. D. Guth。Python 3.3 的形式語意。伊利諾大學厄巴納-香檳分校碩士論文,2013。程式碼:runtimeverification/python-semantics。
  6. M. Bodin、A. Charguéraud、D. Filaretti、P. Gardner、S. Maffeis、D. Naudziuniene、A. Schmitt、G. Smith。可信賴的機械化 JavaScript 規格。POPL 2014。
  7. D. Park、A. Ştefănescu、G. Roşu。KJS:完整的 JavaScript 形式語意。PLDI 2015。
  8. C. Watt。WebAssembly 規格的機械化與驗證。CPP 2018。
  9. X. Leroy。實際編譯器的形式化驗證。Communications of the ACM 52(7),2009。
  10. G. Klein、K. Elphinstone、G. Heiser、J. Andronick 等人。seL4:作業系統核心的形式化驗證。SOSP 2009。
  11. W. M. McKeeman。軟體的差異測試。Digital Technical Journal 10(1):100–107,1998。
  12. X. Yang、Y. Chen、E. Eide、J. Regehr。在 C 編譯器中尋找並理解錯誤。PLDI 2011。

讀者討論

理性交流 · 即時討論