Formalizing CPython:以 Lean 建模 CPython 並回報 418 項錯誤
Formalizing CPython
Formalizing CPython 專案以 Lean 逐行建模 CPython 3.15.2,透過測試、機器證明與獨立審查驗證模型,並據此提交了 418 項錯誤報告。
AI 伴隨問答
針對這篇報導有疑問?可直接點選快捷問題或向 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
重點摘要
- 我們讓 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%
為什麼要做
Python 沒有精確的書面定義。雖然有參考手冊,但實際上,「Python」指的就是 CPython 的行為,而 CPython 是數十萬行 C 程式碼加上大型標準函式庫。手冊涵蓋一般用法,對於各種特殊情況卻少有說明,而錯誤往往就藏在這些地方:物件在字典搜尋它時修改字典、更新到一半時丟擲錯誤,或是數值比 C 程式碼原本設計可處理的最大值多一。
為函式撰寫證明,會迫使你明確說明它在所有這些情況下的行為。你不能含糊帶過,因為證明檢查器不會接受。這讓證明成為找出程式碼與大家預期不符之處的好方法。
我們想了解,這種做法用在像 CPython 這樣規模龐大、歷史悠久的程式碼庫上能做到什麼程度,以及大部分工作由 AI 完成時,結果是否仍值得信賴。
運作方式
每個函式都會經過相同的四個步驟。
- 複製以 Lean 改寫函式,逐行遵循原始程式碼,包括錯誤訊息與特殊情況。
- 測試至少用 50,000 筆棘手輸入,讓複製版與真正的 Python 並行執行。只要結果不一致,複製版就有錯。
- 證明陳述一項應該永遠成立的性質,並讓電腦檢查證明。如果該性質其實不成立,就改為證明這一點。
- 檢查由未參與工作的第二個代理根據原始程式碼審查成果,並嘗試找出問題。只有通過檢驗的成果才會列入統計。
本頁頂端的程式碼,是 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 輪審查審查輪次 →
正確的證明為何仍可能是錯的
經過檢查的證明能保證某個敘述可以從複製版本推匯出來,卻不能保證複製版本符合實際 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
多數問題都很小:錯誤訊息有誤、邊界情況的行為與檔案說明不同,或是同一函式的兩個版本結果不一致。約有 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 NoneC 和 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 專用。只要有可閱讀的原始碼和可執行的版本,就適用於任何東西:其他語言、程式庫、檔案格式、編譯器。對我們來說,以下做法帶來了差異:
- 選定一個明確的版本並堅持使用。每份副本都要指向該版本中的特定程式碼行。
- 先列出所有專案。依完整清單計算進度,避免任何專案悄悄被跳過。
- 複製程式碼,而非檔案。根據檔案撰寫的副本會與檔案一致,而錯誤正是出在程式碼與檔案不一致之處。
- 讓使用者程式碼出錯。模擬會引發錯誤或在操作途中變更狀態的回呼。最嚴重的錯誤就出在這些地方。
- 先測試,再證明。針對錯誤副本進行證明,只會浪費時間。
- 如果某項陳述不成立,就保留反例。不要把陳述改得過於寬鬆,直到它變得可證明為止。
- 用實際版本檢查已證明的陳述。針對錯誤副本做出有效證明,是最具誤導性的結果。
- 只計入獨立審查者接受的成果,並請審查者確認有缺陷的版本是否也會通過。
我們的代理程式據以工作的指示放在程式碼儲存庫裡,並設計成可重複使用:供執行工作的代理程式參考的 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.c310Grammar/python.gram278Lib/collections/__init__.py184Lib/_pydecimal.py160Lib/_pydatetime.py150Modules/_struct.c122Objects/longobject.c119Objects/listobject.c114Objects/memoryobject.c107Objects/dictobject.c104Objects/bytesobject.c100Objects/exceptions.c97Objects/unicodeobject.c94Objects/bytearrayobject.c93Modules/arraymodule.c84Lib/_collections_abc.py81Modules/_operator.c73Modules/itertoolsmodule.c72Modules/_collectionsmodule.c64Python/codecs.c61Lib/operator.py59Lib/_pyio.py58Objects/typeobject.c57Lib/weakref.py54Objects/genobject.c46Lib/urllib/parse.py46Parser/action_helpers.c43Modules/_zoneinfo.c43Objects/floatobject.c38Objects/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}}
}參考資料
- M. Cranmer。使用 Lean 形式化 Julia(並在 Base 中找出 400 多個錯誤)。Julia Discourse,2026。程式碼:MilesCranmer/julia-in-lean。
- L. Koska、T. Koska、B. Koska。使用 Lean 形式化 PTX,以證明 GPU 核心的正確性。arXiv:2611.04447,2026。
- D. Lustig、S. Sahasrabuddhe、O. Giroux。NVIDIA PTX 記憶體一致性模型的形式化分析。ASPLOS 2019。
- J. G. Politz、A. Martinez、M. Milano、S. Warren、D. Patterson、J. Li、A. Chitipothu、S. Krishnamurthi。Python:完整解析。Python 程式語言經測試的語意。OOPSLA 2013。
- D. Guth。Python 3.3 的形式語意。伊利諾大學厄巴納-香檳分校碩士論文,2013。程式碼:runtimeverification/python-semantics。
- M. Bodin、A. Charguéraud、D. Filaretti、P. Gardner、S. Maffeis、D. Naudziuniene、A. Schmitt、G. Smith。可信賴的機械化 JavaScript 規格。POPL 2014。
- D. Park、A. Ştefănescu、G. Roşu。KJS:完整的 JavaScript 形式語意。PLDI 2015。
- C. Watt。WebAssembly 規格的機械化與驗證。CPP 2018。
- X. Leroy。實際編譯器的形式化驗證。Communications of the ACM 52(7),2009。
- G. Klein、K. Elphinstone、G. Heiser、J. Andronick 等人。seL4:作業系統核心的形式化驗證。SOSP 2009。
- W. M. McKeeman。軟體的差異測試。Digital Technical Journal 10(1):100–107,1998。
- X. Yang、Y. Chen、E. Eide、J. Regehr。在 C 編譯器中尋找並理解錯誤。PLDI 2011。