Python的C外部函數(shù)的靜態(tài)類型推斷

Python 已經(jīng)成為最流行的編程語言之一，大量 Python 包采用 Python/C 的多語言架構(gòu)，其中宿主語言 Python 和外部語言 C/C++ 的結(jié)合兼具開發(fā)效率與性能，被包括 NumPy、Pillow、TensorFlow 和 PyTorch 等在內(nèi)的諸多主流軟件系統(tǒng)所采用。但是 Python 和 C/C++ 之間語言特性的差異也使得基于 Python/C API 的跨語言接口代碼容易出錯(cuò)，類型誤用就是常見的錯(cuò)誤之一。

# Python 程序的靜態(tài)類型推斷

學(xué)界和業(yè)界都在 Python 的靜態(tài)類型推斷這一問題上做了大量嘗試。這些工作可以分為以下三類：

通過擴(kuò)展語法支持類型標(biāo)注，并基于類型標(biāo)注進(jìn)行類型推斷。該方法的弊端在于需要修改源碼且影響了 Python 開發(fā)的敏捷性。

基于機(jī)器學(xué)習(xí)的方法。一方面該方法的數(shù)據(jù)集往往來自傳統(tǒng)方法的推斷結(jié)果，另一方面該方法是非確定性的，只能得到概率的結(jié)果。

基于數(shù)據(jù)流分析、抽象解釋、SMT 求解等傳統(tǒng)程序分析方法。這些工作對外部對象的處理往往采用直接忽略（如視為 object 類型）或預(yù)置類型存根（type stubs）等方法，類型推斷精度表現(xiàn)不佳或需要人工輔助。

# 研究方法與定義#

# 外部接口

Python 的外部接口 Python/C API 是橋接 Python 和 C/C++ 的中間層。如圖 1 所示，外部函數(shù) ext.foo 通過 Python/C API PyMethodDef 映射到 C 實(shí)現(xiàn) _foo，再通過 Python/C API PyModuleDef 關(guān)聯(lián)到模塊 ext。在 C 實(shí)現(xiàn)內(nèi)部，Python/C API PyArg_ParseTuple 是一類常見的參數(shù)解析方法，它通過格式化串指明由 Python 到 C 的類型轉(zhuǎn)換。Python/C API PyLong_FromLong 是一類常見的返回類型轉(zhuǎn)換，它把一個(gè) C 整型變量轉(zhuǎn)換到 Python 整型變量。

圖 1：Python 的 C 擴(kuò)展模塊的一個(gè)例子

對于靜態(tài)類型語言，外部函數(shù)在聲明時(shí)帶有顯式類型，動(dòng)態(tài)類型語言雖然沒有這一信息（如圖 1（b）第 2 行），但在接口層仍需給出包含跨語言的類型轉(zhuǎn)換等信息的調(diào)用接口描述。我們的核心思路就是建模并分析這些調(diào)用接口描述中的隱式信息，推斷作用于外部函數(shù)的類型約束。

圖 2：多語言與類型系統(tǒng)視角下的外部函數(shù)調(diào)用

圖 2 是類型系統(tǒng)視角下的外部函數(shù)調(diào)用。如果僅僅從單語言視角來看（藍(lán)色虛線），外部函數(shù)的參數(shù)類型和返回類型都是不可知的（灰色框）；但在多語言的視角下（紅色實(shí)線），結(jié)合跨語言接口層得到的調(diào)用接口描述，外部函數(shù)的類型實(shí)際是可推導(dǎo)的。我們把這些隱式信息分成三個(gè)部分：

外部函數(shù)聲明（D）建立 Python 側(cè)外部函數(shù)的調(diào)用名和 C 側(cè)外部函數(shù)實(shí)現(xiàn)之間的映射關(guān)系。

參數(shù)類型轉(zhuǎn)換（P）刻畫 Python 側(cè)傳入外部函數(shù)的實(shí)參到 C 變量的類型轉(zhuǎn)換。

返回類型轉(zhuǎn)換（R）刻畫 C 側(cè)返回值返回 Python 側(cè)時(shí)的類型轉(zhuǎn)換。

# 抽象語法

我們形式化地把 Python/C 多語言軟件系統(tǒng)的抽象語法表示為圖 3，其中上標(biāo) p 和 c 標(biāo)記不同的語言側(cè)。

圖 3：Python/C 多語言系統(tǒng)的抽象語法

不同于本地函數(shù)在 Python 側(cè)聲明與定義，并在 Python 側(cè)應(yīng)用，外部函數(shù)的應(yīng)用在 Python 側(cè)，但其聲明和定義都在 C 側(cè)。

# 類型

作為動(dòng)態(tài)類型語言，如圖 4 所示，Python 側(cè)的類型是 Python 變量在運(yùn)行時(shí)被綁定的類型值，包括 str、int、object 等內(nèi)置類型；同時(shí)我們引入函數(shù)類型 pFunc 表示函數(shù)，引入積類型 pProduct 表示 list、tuple、dict 等類型，引入和類型 pUnion 支持共用體這一 C 側(cè)常見的語言特性。一些類型如 module、iterator 等不在類型集合中，因?yàn)樗鼈冊趥鬟f給外部函數(shù)時(shí)會(huì)被作為 object 類型對象處理。

圖 4：Python 側(cè)類型

Python/C 跨語言接口層的調(diào)用接口描述能夠給出更嚴(yán)格的類型和值約束。比如圖 1 中，Python/C API 函數(shù) PyArg_ParseTuple 的第 2 個(gè)參數(shù)給出的格式化串 II 中的格式化單元I要求傳入對應(yīng)的外部函數(shù)的實(shí)參是一個(gè) Python 整型并且非負(fù)。我們利用子類型來刻畫這類規(guī)則。Python 側(cè)類型的子定型規(guī)則如圖 5 所示。

圖 5：Python 側(cè)類型的子定型規(guī)則

如圖 6 所示，C 側(cè)除了常見的內(nèi)置類型外，還包括一些在 CPython 解釋器內(nèi)部的、與 Python 側(cè)類型實(shí)現(xiàn)相對應(yīng)的結(jié)構(gòu)體。作為 Python/C API 的一部分，它們也被用于在接口層接收 Python 側(cè)傳遞并轉(zhuǎn)換的對象。

圖 6：C 側(cè)類型

# 類型推斷#

在以上核心思路和文法定義的基礎(chǔ)上，我們把類型推斷規(guī)則形式化地表示為如下形式：

外部函數(shù)聲明（D）、參數(shù)類型轉(zhuǎn)換（P）、返回類型轉(zhuǎn)換（R）共同構(gòu)成推理前提，從而推導(dǎo)出包含在 Python/C 跨語言接口層調(diào)用接口描述中的外部函數(shù)的類型簽名，函數(shù)類型的參數(shù)類型和返回類型由 D、P、R 的具體組合確定。

# 外部函數(shù)聲明 D

表示如上，它描述了 Python 側(cè)外部函數(shù)調(diào)用名和 C 側(cè)實(shí)現(xiàn)的映射關(guān)系。其中flag給出調(diào)用慣例，在 CPython 中典型的如METH_VARARGS，它表示外部函數(shù)接收一個(gè)或多個(gè) Python 對象作為參數(shù)，它們被打包成一個(gè)對象并傳遞到 C 側(cè)，跨語言接口層需要給出把這一打包對象解析到多個(gè) C 變量的規(guī)則。

# 參數(shù)類型轉(zhuǎn)換 P

表示如上，它刻畫了基于程序性質(zhì) P 在 C 側(cè)（包含跨語言接口代碼）的上下文中描述的 Python 類型到 C 類型的轉(zhuǎn)換。這種隱式信息的分析包含了以下兩類常見的規(guī)則：

## 調(diào)用慣例分析

例如，當(dāng)調(diào)用慣例flag為METH_NOARGS時(shí)，外部函數(shù)被聲明為無參的，表示為如下的無參分析（Parameter-Free Analysis），

假設(shè)判斷 表示只有當(dāng)關(guān)于程序性質(zhì) P 的門限語義謂詞 為真時(shí)，判斷 J 成立。

然而，當(dāng)對應(yīng)的 C 實(shí)現(xiàn)根本不解析并使用傳入的參數(shù)時(shí)，外部函數(shù)實(shí)際也是無參的?；谝粋€(gè)未使用形參的分析（Unused Parameter Analysis）可以類似地表示如下，

動(dòng)態(tài)類型語言（Python）和靜態(tài)類型語言（C/C++）之間類型系統(tǒng)的差異，以及 Python 外部接口的設(shè)計(jì)導(dǎo)致了這種聲明上的冗余，并且留下了聲明不一致的隱患。即只有當(dāng)上述兩個(gè)門限語義謂詞都為真時(shí)，才可以確定外部函數(shù)是無參的，用合取范式表示如下：

## 參數(shù)解析分析

當(dāng)上述兩個(gè)門限語義謂詞都為假時(shí)，外部函數(shù)至少接收一個(gè) Python 對象。如上所述，這些 Python 側(cè)對象被打包為跨語言接口層的一個(gè)中間參數(shù)，該參數(shù)被解析并恢復(fù)到若干個(gè) C 變量。最常見的，這一跨語言的類型轉(zhuǎn)換是由參數(shù)解析族 Python/C API 完成。這些 Python/C API 用一個(gè)格式化串指明轉(zhuǎn)換規(guī)則，一個(gè)格式化串包含零或多個(gè)格式化單元，每個(gè)格式化單元（特殊含義字符除外）對應(yīng)一個(gè) Python 類型到 C 類型的轉(zhuǎn)換，表示如下：

其中 是某個(gè)參數(shù)解析族的 Python/C API（常見的如 PyArg_ParseTuple）， 是其第 i 個(gè)格式化單元。例如，格式化單元 對應(yīng) Python 非負(fù)整型到 C 無符號(hào) int 類型的轉(zhuǎn)換， ，完整的格式化單元轉(zhuǎn)換規(guī)則表見論文表 1。

# 返回類型轉(zhuǎn)換 R

表示如上，它刻畫了基于程序性質(zhì) P 在 C 側(cè)（包含跨語言接口）的上下文中描述的 C 類型到 Python 類型的轉(zhuǎn)換。作為 Python 的一部分，其外部函數(shù)也支持多返回（multiple returns）的語言特性，而 C 本身是不支持的。這部分隱式信息的分析包含四類常見的規(guī)則。

##值構(gòu)建分析

同樣基于格式化串，但是方向與參數(shù)類型轉(zhuǎn)換的參數(shù)解析分析相反，即：

是某個(gè)值構(gòu)建族的 Python/C API（常見的如 Py_BuildValue）， 是其第 j 個(gè)格式化單元，m 個(gè) C 變量根據(jù)對應(yīng)的格式化單元轉(zhuǎn)換到 Python 對象并共同構(gòu)成一個(gè) tuple 對象作為多返回的值。

## 顯性轉(zhuǎn)換分析

一些 Python/C API 支持直接以單一對象作為外部函數(shù)的返回。

顯式轉(zhuǎn)換的 Python/C API 形如：（1）PyPT_FromCT 把一個(gè) CT 類型的 C 變量轉(zhuǎn)換到一個(gè) PT 類型的 Python 變量，（2）PyPT_New 創(chuàng)建并返回一個(gè) PT 類型的 Python 變量，（3）Py_PT 本身直接作為一個(gè) PT 類型的對象被返回到 Python 側(cè)。

## 類型轉(zhuǎn)換（type cast）分析

C 程序支持作為右結(jié)合算子的顯式類型轉(zhuǎn)換，對于一個(gè)形如 的返回表達(dá)式，可以推斷：

作為外部函數(shù)的 C 實(shí)現(xiàn)向 Python 側(cè)的返回，C 類型 是與 Python 內(nèi)置類型一一對應(yīng)的結(jié)構(gòu)體（圖 6 中 Py 開頭的 C 類型）。

## 可達(dá)定義分析

考慮如下圖所示的更復(fù)雜的返回情形，

圖 7：一個(gè)復(fù)雜的返回類型轉(zhuǎn)換的例子

變量 result 被聲明為 T1 類型（一般為 PyObject*），其可能通過調(diào)用前述的一些 Python/C API 被賦值為更精化的類型（T2，T3）。我們通過一個(gè)過程內(nèi)的可達(dá)定義分析 來分析這樣的類型傳播。 內(nèi)部會(huì)調(diào)用前面三類的返回類型轉(zhuǎn)換分析?；诳蛇_(dá)定義分析的返回類型轉(zhuǎn)換表示如下：

# 小結(jié)

對于類型推斷（TInfer）的三個(gè)前提，外部函數(shù)聲明（D）只有一種形式，參數(shù)類型轉(zhuǎn)換（P）包含形式（Pcc）和（Pap），返回類型轉(zhuǎn)換（R）包含形式（Rvb），（Rec），（Rtc）和（Rrd）。這樣，對于使用參數(shù)解析分析進(jìn)行參數(shù)類型轉(zhuǎn)換、使用值構(gòu)建分析進(jìn)行返回類型轉(zhuǎn)換的一個(gè)外部函數(shù)典型模式，其類型推斷規(guī)則如下：

類似地，帶有顯式返回的無參外部函數(shù)可以推斷如下：

# 實(shí)驗(yàn)結(jié)果#

我們的靜態(tài)類型推斷系統(tǒng) PyCType 的原型結(jié)構(gòu)如圖 8 所示。

圖 8：PyCType 架構(gòu)概覽

接口分離器從 Python/C 多語言項(xiàng)目中分離出跨語言接口代碼。預(yù)處理配置器配置解析文件所需的依賴。AST 解析器基于 Python 實(shí)現(xiàn)的 C99 解析器 pycparser。在得到接口代碼的 AST 后，多數(shù)分析基于訪問 AST 實(shí)現(xiàn)，當(dāng)某個(gè)分析需要其他中間表示如 CFG 時(shí)，AST 變換模塊對對應(yīng)的 AST 片段進(jìn)行變換。其他主要處理模塊（圓角矩形）與前文對應(yīng)。

# 外部函數(shù)聲明與其實(shí)現(xiàn)不一致的漏洞

如調(diào)用慣例分析小節(jié)所述，同一個(gè)外部函數(shù)其無參分析（PFA）和未使用參數(shù)分析（UPA）可能不能同時(shí)成立，這會(huì)導(dǎo)致一個(gè)無參外部函數(shù)可以接受任意類型的參數(shù)。

# 可靠性

類型推斷的可靠性是構(gòu)建以上嚴(yán)格的推理系統(tǒng)的主要目的之一，即類型推斷的結(jié)果沒有錯(cuò)誤（但可能不夠精確，如把 int 推斷為 object）。我們通過人工檢查驗(yàn)證了該靜態(tài)類型推斷系統(tǒng)的可靠性。同時(shí)漏洞發(fā)現(xiàn)也是沒有誤報(bào)的，所有錯(cuò)誤都可以構(gòu)造出對應(yīng)的觸發(fā)代碼。（這里的可靠性是對類型推斷而言的。在漏洞檢查的研究中，可靠一般指沒有漏報(bào)。如果將一致性漏洞檢查作為一個(gè)獨(dú)立的系統(tǒng)，其應(yīng)表示為類型推斷系統(tǒng)調(diào)用慣例分析的謂詞條件的否定命題。）

# 完備性

在可靠的基礎(chǔ)上，完備性成為衡量類型推斷系統(tǒng)有效性的一個(gè)重要指標(biāo)，即推斷率。如表 1 所示是 CPython、NumPy 和 Pillow 中外部函數(shù)的參數(shù)類型的推斷率?？梢钥吹?，對于參數(shù)類型轉(zhuǎn)換，規(guī)則（Pcc）和（Pap）能夠覆蓋大多數(shù)的情形。同時(shí)在規(guī)則中描述更多符合條件的 Python/C API 并不困難。

表 1：參數(shù)類型推斷的完備性

一方面，參數(shù)個(gè)數(shù)往往多于返回值，一方面，外部函數(shù)調(diào)用作為 Python 程序的一部分，其返回值可能是其他（外部或本地）函數(shù)的參數(shù)。因此，整個(gè)系統(tǒng)的有效性需要和已有的單語言的類型推斷工具結(jié)合起來進(jìn)行評估。

# 有效性

由于可靠并不等于精確，因此我們選擇上表中推斷率最高的 Pillow 來構(gòu)建類型增強(qiáng)實(shí)驗(yàn)以進(jìn)一步衡量有效性。來自 Google 的 Pytype 是 state-of-the-art 的 Python 靜態(tài)類型推斷工具，其不支持外部函數(shù)的自動(dòng)推斷，而是通過類型存根預(yù)置了一些外部函數(shù)的類型簽名，如常見的標(biāo)準(zhǔn)庫函數(shù)。我們把對 Pillow 中外部函數(shù)類型推斷的結(jié)果編碼成 Pytype 的類型存根，然后比較這一類型增強(qiáng)前后的推斷率。實(shí)驗(yàn)?zāi)繕?biāo)我們選擇 GitHub 中使用了 Pillow 且星標(biāo)多于 3 萬的 Python 倉庫，實(shí)驗(yàn)結(jié)果如表 2 所示，可以看到，PyCType 對 Pytype 有 7% 到 80% 的提升（平均 27.5%）。

表 2：類型推斷增強(qiáng)實(shí)驗(yàn)

# 總結(jié)#

我們提出了 Python 外部函數(shù)的靜態(tài)類型推斷系統(tǒng) PyCType。其類型推斷規(guī)則包括三部分可組合的推理前提，分別建模和分析 Python/C 跨語言接口層中類型轉(zhuǎn)換相關(guān)的隱式信息。在主流軟件系統(tǒng)上的實(shí)驗(yàn)表明，PyCType 能夠可靠地推斷多數(shù)外部函數(shù)的類型簽名。其作為單語言 Python 靜態(tài)類型推斷工具的增強(qiáng)，使其能夠推斷含有外部函數(shù)調(diào)用的程序。同時(shí)能夠檢查使得無參外部函數(shù)可以接受任意類型參數(shù)的聲明不一致的漏洞，部分發(fā)現(xiàn)漏洞已被確認(rèn)和修復(fù)。

審核編輯：劉清