AI 智能體以 Lean 形式化 CPython,整理出 418 份 bug 報告
CPython的形式化
團隊以 Opus 5.5 驅動 AI 智能體,將 CPython 3.15.2 的函數逐行改寫為 Lean 模型,並以真實 Python 測試、機器證明和獨立審查驗證。
文章展示以逐行建模、差分測試、機器證明與獨立審查處理大型程式碼庫,並説明如何辨別形式正確但對實際行為缺乏約束力的證明。
AI Agent 寫出 613,318 行 Lean 程式碼,逐行複製 Python 的內部實作;每部分均以 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 重寫其中的函式。Lean 是一種用來撰寫可由機器檢查證明的語言。
- 每個重寫版本都逐行複製原始程式碼,並先以數以萬計的輸入對照 Python 本身進行測試,之後才嘗試證明任何相關事項。
- 只有經另一個沒有撰寫該函式的 Agent 檢查並確認經得起檢驗,該函式才會計入數目。目前已有 4,071 個函式通過檢查。
- 成果包括 1,539 個檔案中的 613,318 行 Lean 程式碼,以及 18,898 項定理和引理;每次建置時,Lean 的證明檢查器都會檢查所有內容。
- 過程中的證明找出 418 項 Python 錯誤報告。大部分問題都很小,但約有 55 項可透過一般 Python 程式碼令直譯器崩潰或破壞記憶體。
已檢查並接納已撰寫,尚未接納尚未開始
- CPython 整體16%
- 直譯器核心10%
- 內置類型35%
- C 模組19%
- 剖析器31%
- 文法規則100%
- 標準程式庫9%
為甚麼要做
Python 沒有精確的書面定義。雖然有參考手冊,但實際上,「Python」指的是 CPython 的行為;而 CPython 由數十萬行 C 程式碼和大型標準程式庫組成。手冊涵蓋一般用法,對特殊情況則着墨不多,而錯誤往往藏在這些地方:物件在字典搜尋它時改動字典、更新進行到一半時拋出的錯誤,以及比 C 程式碼原本設計可處理的最大值大一的數字。
為函式撰寫證明,迫使你準確説明它在上述所有情況下的行為。你不能含糊帶過,因為證明檢查器不會接受。這令證明成為找出程式碼不如大家所想般運作之處的好方法。
我們想看看這種做法在 CPython 這樣規模龐大、歷史悠久的程式碼庫中能做到甚麼程度,以及大部分工作由 AI 完成時,成果能否繼續保持可信。
運作方式
每個函式都會經過相同的四個步驟。
- 複製以 Lean 重寫函式,逐行跟隨原始程式碼,包括其中的錯誤訊息和特殊情況。
- 測試以至少 50,000 個棘手輸入,並排執行複製版本和 Python 本身。任何不一致都表示複製版本有錯。
- 證明陳述一項應該永遠成立的命題,並由電腦檢查證明。如果命題其實不成立,就改為證明它不成立。
- 檢查由另一個沒有參與工作的 Agent 根據原始程式碼審核,並嘗試找出問題。只有經得起檢驗的成果才會計入。
本頁頂部的程式碼,是 CPython 一小部分的第一步:計算 range 中有多少個數字的 C 函式,旁邊是它的 Lean 版本。這個版本保留 C 程式碼的精確算術行為,包括數字過大時如何回繞。相關證明顯示,這個函式、CPython 用於極大數字的較慢版本,以及負責在兩者之間作出選擇的程式碼,始終會得出相同而正確的計數。
毫無證明力的證明
最困難的部分不是讓 AI 代理程式撰寫證明,而是讓證明真正有意義。
我們最初要求代理程式廣泛處理:複製每個函式,並為每個函式至少證明一件事。它們做到了。之後,另一輪獨立審查發現,受檢查的函式中,不到一半經得起檢驗;其中一個檔案更只有 21%。這些證明全都正確,只是沒有説明任何有用的事情。例如,「如果這個函式傳回一個數字,該數字至少是零」這句話是正確的,但即使某個函式永遠當機,也符合這個條件。
因此,審查者現在會就每個證明提出一個問題:有問題的函式版本是否也能通過這個證明?
| 函式版本 | 「如果函式有傳回結果,答案就 ≥ 0」 | 「函式總會傳回正確的計數」 |
|---|---|---|
| 原本的函式 | 通過 | 通過 |
| 永遠當機 | 通過 | 被識破 |
| 極大數字時傳回 0 | 通過 | 被識破 |
| 倒數計數時多算或少算一個 | 通過 | 被識破 |
要補強薄弱的證明,通常需要回頭讓複製的版本更貼近實際情況,例如容許用戶程式碼在函式執行中途擲出錯誤。以下圖表顯示十個檔案的審查結果。每個資料點代表一輪審查。折線有時會向下:如果審查者發現某個已通過的證明與實際 Python 的行為不符,所有依賴該證明的內容都會撤回。
通過審查的函式
Objects/typeobject.c:第一輪審查後有 0 個通過(共 142 個),第 5 輪後有 135 個
Objects/typeobject.c135 of 142 通過 · 5 輪審查Objects/genobject.c:第一輪審查後有 1 個通過(共 56 個),第 5 輪後有 56 個
Objects/genobject.c56 of 56 通過 · 5 輪審查Objects/setobject.c:第一輪審查後有 31 個通過(共 46 個),第 7 輪後有 46 個
Objects/setobject.c46 of 46 通過 · 7 輪審查Modules/_json.c:第一輪審查後有 31 個通過(共 48 個),第 5 輪後有 45 個
Modules/_json.c45 of 48 通過 · 5 輪審查Lib/enum.py:第一輪審查後有 21 個通過(共 39 個),第 9 輪後有 37 個
Lib/enum.py37 of 39 通過 · 9 輪審查Lib/random.py:第一輪審查後有 11 個通過(共 38 個),第 3 輪後有 37 個
Lib/random.py37 of 38 通過 · 3 輪審查Objects/abstract.c:第一輪審查後有 9 個通過(共 43 個),第 2 輪後有 41 個
Objects/abstract.c41 of 43 通過 · 2 輪審查Objects/rangeobject.c:第一輪審查後有 19 個通過(共 33 個),第 2 輪後有 33 個
Objects/rangeobject.c33 of 33 通過 · 2 輪審查Lib/pickletools.py:第一輪審查後有 14 個通過(共 33 個),第 2 輪後有 31 個
Lib/pickletools.py31 of 33 通過 · 2 輪審查Modules/binascii.c:第一輪審查後有 29 個通過(共 40 個),第 2 輪後有 35 個
Modules/binascii.c35 of 40 通過 · 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 崩潰的字典呼叫
若另一個相同類別的物件有該屬性,而這個物件沒有,以 StrEnum 為鍵,在物件的屬性字典上呼叫 setdefault 會令直譯器崩潰。
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 專用。只要是能讀取原始碼並執行正常版本的項目,無論是另一種語言、程式庫、檔案格式還是編譯器,都適用。以下做法對我們最有幫助:
- 選定一個確切版本,並始終使用該版本。每個副本都對應到該版本中的特定程式碼行。
- 先列出所有項目。 以完整清單計算進度,避免有項目在不知不覺間被跳過。
- 直接複製程式碼,而非照抄文件。 根據文件編寫的副本自然會與文件一致,而錯誤正正出現在程式碼與文件不一致之處。
- 讓用戶程式碼出現異常行為。 模擬會引發錯誤或在操作途中作出更改的回呼函式。最嚴重的錯誤都出現在這些情況。
- 先測試,再證明。 證明錯誤副本的性質只會浪費時間。
- 陳述不成立時,保留反例。 不要不斷弱化陳述,直至它變得可證明。
- 以實際程式檢查已證明的陳述。 對錯誤副本作出的有效證明,是最容易令人誤判的結果。
- 只計算獨立審查者接受的項目,並請審查者確認有缺陷的版本是否也會通過。
我們的 Agent 使用的指引收錄在儲存庫中,並供重用:供負責工作的 Agent 使用的 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。
進展狀況
項目於 29 October 2026 開始。在 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, et al. 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。
來源:Hacker News 熱門(buzzing.cc 中文翻譯) · broyojo.com