跳到正文
Hacker News 熱門(buzzing.cc 中文翻譯)·· 9 天前精選AI 評分77

AI 智能體以 Lean 形式化 CPython,整理出 418 份 bug 報告

CPython的形式化

AI 導讀

團隊以 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
左邊是 CPython C 語言原始碼中的函式,右邊是 Agent 撰寫的 Lean 複製版本。將遊標移至某一行,即可查看對應的另一行。

重點摘要

  • 我們讓 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%
這裡顯示 CPython 3.15.2 各部分有多少已完成複製、測試、證明,並經審核接納。沒有可供檢查之處的程式碼,例如記憶體記帳程式碼,則不包括在內。

為甚麼要做

Python 沒有精確的書面定義。雖然有參考手冊,但實際上,「Python」指的是 CPython 的行為;而 CPython 由數十萬行 C 程式碼和大型標準程式庫組成。手冊涵蓋一般用法,對特殊情況則着墨不多,而錯誤往往藏在這些地方:物件在字典搜尋它時改動字典、更新進行到一半時拋出的錯誤,以及比 C 程式碼原本設計可處理的最大值大一的數字。

為函式撰寫證明,迫使你準確説明它在上述所有情況下的行為。你不能含糊帶過,因為證明檢查器不會接受。這令證明成為找出程式碼不如大家所想般運作之處的好方法。

我們想看看這種做法在 CPython 這樣規模龐大、歷史悠久的程式碼庫中能做到甚麼程度,以及大部分工作由 AI 完成時,成果能否繼續保持可信。

運作方式

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

  1. 複製以 Lean 重寫函式,逐行跟隨原始程式碼,包括其中的錯誤訊息和特殊情況。
  2. 測試以至少 50,000 個棘手輸入,並排執行複製版本和 Python 本身。任何不一致都表示複製版本有錯。
  3. 證明陳述一項應該永遠成立的命題,並由電腦檢查證明。如果命題其實不成立,就改為證明它不成立。
  4. 檢查由另一個沒有參與工作的 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 輪審查

審查輪數 →

各檔案在每輪審查後獲接納的函式比例,根據專案的歷史紀錄整理。每個數據點代表一次審查;所有圖表均使用相同刻度,從 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 崩潰的字典呼叫

若另一個相同類別的物件有該屬性,而這個物件沒有,以 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 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. 只計算獨立審查者接受的項目,並請審查者確認有缺陷的版本是否也會通過。

我們的 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.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, et al. 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。

來源:Hacker News 熱門(buzzing.cc 中文翻譯) · broyojo.com