作者介紹

陳哲，南京航空航天大學(xué)副教授，碩士生導(dǎo)師。研究方向：軟件驗(yàn)證，程序分析，形式化方法等。

摘要

C 程序的內(nèi)存錯(cuò)誤可能導(dǎo)致程序崩潰和安全缺陷，因此使用動(dòng)態(tài)分析工具在運(yùn)行時(shí)自動(dòng)發(fā)現(xiàn)內(nèi)存錯(cuò)誤是工業(yè)界面臨的一個(gè)痛點(diǎn)，然而傳統(tǒng)的內(nèi)存安全性動(dòng)態(tài)分析工具具有三個(gè)缺點(diǎn)：低有效性、優(yōu)化敏感和平臺(tái)依賴。

為了克服以上問(wèn)題，我們提出了一種基于智能狀態(tài)的監(jiān)控算法和一種源代碼級(jí)別的插樁框架，并依此實(shí)現(xiàn)了一款新的動(dòng)態(tài)分析工具 —— Movec。實(shí)驗(yàn)表明，Movec 工具比 AddressSanitizer、Valgrind 等著名工具能找到更多的內(nèi)存錯(cuò)誤，在性能和可用性方面也非常有競(jìng)爭(zhēng)力。這項(xiàng)長(zhǎng)達(dá)五年的持續(xù)研究已經(jīng)在 ISSTA’19[1]、ISSTA’21[2]、ICSE’22[3]、IEEE TSE[4]等頂級(jí)會(huì)議和期刊發(fā)表了 4 篇論文，并獲得一次 ACM SIGSOFT 杰出論文獎(jiǎng)。

以下為正文。

# 背景 #

今天為大家?guī)?lái) C 程序內(nèi)存安全性動(dòng)態(tài)分析相關(guān)工作的分享，包含兩個(gè)創(chuàng)新點(diǎn)，一個(gè)是 智能狀態(tài)，一個(gè)是 源代碼插樁。

C 語(yǔ)言經(jīng)常被應(yīng)用于系統(tǒng)軟件的編程，比如嵌入系統(tǒng)、操作系統(tǒng)、編譯器等，它可以對(duì)內(nèi)存進(jìn)行低級(jí)別的控制。然而由于開發(fā)人員水平參差不齊，C 程序極易出現(xiàn)內(nèi)存錯(cuò)誤，導(dǎo)致數(shù)據(jù)腐敗、程序崩潰等一系列漏洞。

使用靜態(tài)分析工具，可以在不運(yùn)行程序的情況下，在程序編譯期間發(fā)現(xiàn)錯(cuò)誤。 但由于不可判定性，靜態(tài)分析工具往往會(huì)產(chǎn)生誤報(bào)。這時(shí)我們需要在準(zhǔn)確性和性能之間做出平衡，往往需要犧牲一些精確性來(lái)獲得更好的性能。

使用動(dòng)態(tài)分析工具，可以在運(yùn)行時(shí)動(dòng)態(tài)分析程序執(zhí)行有無(wú)錯(cuò)誤。 動(dòng)態(tài)分析工具一般情況下不會(huì)產(chǎn)生誤報(bào)，但可能產(chǎn)生一些 運(yùn)行時(shí)負(fù)載，即程序的運(yùn)行速度會(huì)比未插樁分析之前的程序慢。但通常來(lái)說(shuō)，動(dòng)態(tài)分析工具一般用于測(cè)試階段，這種為程序帶來(lái)的慢是可以接受的，所以動(dòng)態(tài)分析工具現(xiàn)在很流行。

# 內(nèi)存錯(cuò)誤類別

我們將內(nèi)存錯(cuò)誤分為四類：

空間錯(cuò)誤 Spatial Errors

即對(duì)空指針或未初始化指針的解引用。比如數(shù)組越界，定義一個(gè)數(shù)組，大小是 10，如果訪問(wèn)第 11 個(gè)元素，那么就發(fā)生了越界，屬于空間錯(cuò)誤。

時(shí)間錯(cuò)誤 Temporal Errors

包含懸空指針，或者對(duì)指針的二次釋放。比如在堆里分配一個(gè)內(nèi)存，把它釋放掉后，接著又去訪問(wèn)它或者釋放它。

段混淆錯(cuò)誤 Segment Confusion Errors

即未根據(jù)指針預(yù)期的類型來(lái)使用指針。比如有一個(gè)函數(shù)指針，正常應(yīng)該用指針去調(diào)用函數(shù)，但使用時(shí)卻用指針來(lái)輸出里面的指針?biāo)赶騾^(qū)域的數(shù)據(jù)。

內(nèi)存泄漏錯(cuò)誤 Memory Leaks

即堆內(nèi)存上存在不會(huì)再被使用也未被釋放的對(duì)象。比如，在內(nèi)存中分配了一個(gè)對(duì)象，但其既未被使用，也未被釋放，導(dǎo)致內(nèi)存越用越少，形成內(nèi)存泄露。

# 動(dòng)態(tài)分析方法和工具

## 監(jiān)控方法

動(dòng)態(tài)分析的 監(jiān)控方法 有很多種。這些監(jiān)控方法有一個(gè)共同點(diǎn)，即 在運(yùn)行時(shí)維護(hù)一些元數(shù)據(jù)。這些元數(shù)據(jù)用來(lái)描述程序當(dāng)中的一些空間和時(shí)間信息，比如，一個(gè)對(duì)象“被分配了多少空間”、“是否現(xiàn)在還存在于內(nèi)存當(dāng)中”、“是否正在被使用”等等。根據(jù)這些元數(shù)據(jù)信息，可以判斷程序當(dāng)中是否有內(nèi)存錯(cuò)誤。

下面列出了動(dòng)態(tài)分析的幾種主要監(jiān)控方法，以及支持的工具。比如 SoftBoundCETS[5]，使用基于指針的方法和基于標(biāo)識(shí)符的方法；Google 的 ASan[6]使用了面向?qū)ο蟮姆椒ê蛢?nèi)存哨兵技術(shù)。保存元數(shù)據(jù)是這些工具基本的思想。

基于指針的方法：SoftBoundCETS

基于標(biāo)識(shí)符的方法：SoftBoundCETS

面向?qū)ο蟮姆椒ǎ篏oogle's ASan, Valgrind[7]

內(nèi)存哨兵技術(shù)：Google's ASan

舉個(gè)例子，假設(shè)在內(nèi)存當(dāng)中使用 malloc 分配了一個(gè)內(nèi)存空間，工具會(huì)記錄 p 所指向的空間的基地址是 p 的值，上界是 p+100。如果程序訪問(wèn)的是 [p, p+100] 之間的內(nèi)存，則工具會(huì)判定是合法的，若程序訪問(wèn)超出了這個(gè)范圍的內(nèi)存，比如 p+101，則工具會(huì)認(rèn)定是一個(gè)內(nèi)存錯(cuò)誤。

int*p=malloc(100*sizeof(int));

//Thebaseofpis"p".
//Theboundofpis"p+100".

## 插樁框架

動(dòng)態(tài)分析工具的另一個(gè)基礎(chǔ)技術(shù)是 插樁框架。這些插樁框架需要在待驗(yàn)證的程序中插入一些代碼片段，這些代碼片段實(shí)現(xiàn)的就是監(jiān)控元數(shù)據(jù)的方法。被插入的代碼片段會(huì)隨著程序的運(yùn)行而運(yùn)行，并收集數(shù)據(jù)來(lái)判定是否有內(nèi)存錯(cuò)誤。

現(xiàn)有的插樁框架都是在中間代碼或者二進(jìn)制層面上進(jìn)行插樁，目前沒(méi)有在源代碼級(jí)別進(jìn)行插樁的工具。

中間代碼層 (中間表示)：SoftBoundCETS, Google's ASan

二進(jìn)制層 (目標(biāo)代碼，可執(zhí)行文件)：Valgrind

# 面臨的挑戰(zhàn) #

現(xiàn)有的算法和框架，面臨著三個(gè)挑戰(zhàn)。

一是 有效性比較低 low effectiveness?，F(xiàn)有的方法無(wú)法 確定地、完整地 找到所有的內(nèi)存錯(cuò)誤，包括子對(duì)象越界、釋放后使用、段混淆、內(nèi)存泄漏。

此外，現(xiàn)有的算法工具 對(duì)優(yōu)化敏感 optimization sensitivity。不同的編譯器優(yōu)化級(jí)別會(huì)對(duì)檢測(cè)的最終結(jié)果造成影響，一些在低優(yōu)化級(jí)別能找到的內(nèi)存錯(cuò)誤在高優(yōu)化級(jí)別下就找不到了。

第三個(gè)挑戰(zhàn)是 平臺(tái)依賴 platform dependence?，F(xiàn)有工具只能在一些主流的平臺(tái)上運(yùn)行，如 Linux、Windows；無(wú)法在一些特定的領(lǐng)域系統(tǒng)上使用，如航空航天領(lǐng)域、嵌入式系統(tǒng)領(lǐng)域，操作系統(tǒng)如 VxWorks 和 uC/OS、架構(gòu)如 MIPS, MicroBlaze, RISC-V 等。

下面是具體的挑戰(zhàn)舉例。

# 低有效性

段混淆錯(cuò)誤

以非法的解引用為例。

下面的示例代碼中，定義了一個(gè)指針 s 指向一個(gè)函數(shù) (第七行)。但在使用時(shí) (第八行)，訪問(wèn)的是它所指向的內(nèi)存空間里面的第 0 號(hào)元素。這個(gè)錯(cuò)誤可能引起信息泄露 information leakage。

//Example1:Usingafunctionasdata
//Thiserrormaycauseinformation
//leakage.
1voidfoo();/*afunc*/
2char*func(char*c){
3returnc;
4}
5intmain(){
6void(*p)()=foo;
7char*s=func(p);
8charch=s[0];/*error*/
9return0;
10}

下面示例代碼中，定義了一個(gè)指針 p，指向數(shù)組里面的一個(gè)元素。但在使用時(shí)，把它當(dāng)成了一個(gè)函數(shù)來(lái)調(diào)用 (第七行)。這種錯(cuò)誤可能引起控制流劫持 control-flow hijacking。

//Example2:Usingdataasafunction
//Thiserrormaycausecontrol-
//flowhijacking.
1void(*f(void(*p)()))(){
2returnp;
3}
4intmain(){
5inta[100];
6void(*p)()=f(a);
7(*p)();/*error*/
8return0;
9}

這些錯(cuò)誤已有的工具都是發(fā)現(xiàn)不了的。

子對(duì)象越界

下面示例代碼中，有一個(gè)指針 p，指向一個(gè)結(jié)構(gòu)體 s 的成員 m1 (第七行)，但在使用時(shí)，超出了 m1 的范圍 (第八行)。

//Example3:Sub-objectoverflow
//Anoverflowfromafieldofa
//structtoanother
1typedefstruct{
2intm1;
3intm2;
4}st;
5intmain(){
6sts;
7int*p=&s.m1;
8p[1]=0;/*spatialerror*/
9return0;
10}

下面示例代碼中，定義了數(shù)組 buf (第二行)，但在訪問(wèn)時(shí)，超出了數(shù)組所指向的范圍 (第七行)。由于 buf 是處于結(jié)構(gòu)體的內(nèi)部，所以已有的工具也發(fā)現(xiàn)不了。

//Example4:Intra-arrayoverflow
//Anoverflowfromanarrayelement
//toanother
1typedefstruct{
2charbuf[10];
3inti;
4}st;
5intmain(){
6starr[5];
7p[2].buf[20]='A';
8/*spatialerror*/
9return0;
10}

內(nèi)存釋放后使用

這種錯(cuò)誤指釋放一個(gè)內(nèi)存對(duì)象之后再訪問(wèn)它。對(duì)于這種錯(cuò)誤，現(xiàn)有的工具只能以概率的方式 (lock key scheme) 或者部分的方式 (object-based 和 quarantine-based 方法) 來(lái)檢測(cè)此種錯(cuò)誤，受限于算法本身的缺陷，會(huì)造成假陰性 false negative 的結(jié)果。

內(nèi)存泄漏

現(xiàn)有工具只能在程序終止時(shí)才能檢測(cè)到內(nèi)存泄漏，在程序運(yùn)行過(guò)程當(dāng)中，也就是內(nèi)存泄漏發(fā)生的地方，工具是無(wú)法及時(shí)發(fā)現(xiàn)的。

# 優(yōu)化敏感

空間錯(cuò)誤

下面代碼示例中有一個(gè)內(nèi)存錯(cuò)誤，指針 p 指向了變量 i 的地址 (第四行)，在解引用時(shí)超出了 i 的范圍 (第六行)。

//Example5:Aspatialerror
//*(p+5)causesaspatialeror.
/*Option-O1hideserror.*/
1#include
2intmain(){
3inta[10]={0};
4inti=1,sum=0,*p=&i;
5
6*(p+5)=1;/*spatialerror*/
7
8for(i=0;i<10;?i++)
9??????sum?+=?a[i];
10???printf("sum?is?%d
",?sum);
11???return?0;
12?}

針對(duì)上面的錯(cuò)誤，已有的工具檢測(cè)結(jié)果如下所示。當(dāng)使用比較高級(jí)別的優(yōu)化時(shí)，工具就沒(méi)有那么有效了。

ASan and Valgrind are the same on other programs.

時(shí)間錯(cuò)誤

下面示例中，第九行 *n 存在時(shí)間錯(cuò)誤。

//Example6:Atemporalerror
//Dereferencingnaccessesanout-of
//-scopestackvariablex,resulting
//inatemporalerror.
/*Option-O2hideserror*/
1#include
2voidfoo(int**p_addr){
3intx;
4*p_addr=&x;
5}
6intmain(){
7int*n;
8foo(&n);
9printf("%d
",*n);
10/*temporalerror*/
11return0;
12}

工具查找結(jié)果如下圖所示。

出現(xiàn)這種問(wèn)題的根本原因是 編譯器優(yōu)化。編譯器優(yōu)化會(huì)導(dǎo)致源代碼和二進(jìn)制代碼之間并不完全一致，這會(huì)使得工具在對(duì)優(yōu)化之后的代碼進(jìn)行插樁時(shí)出現(xiàn)一些問(wèn)題，使得原來(lái)在源碼中的錯(cuò)誤無(wú)法被檢測(cè)到。這也是在中間表示和二進(jìn)制代碼上插樁的局限性。

所以，我們?cè)谑褂眠@些工具的時(shí)候，需要在性能和有效性上做一個(gè)平衡。比如使用 -O0 的時(shí)候，獲得的有效性會(huì)比較高，但犧牲了性能；選擇更高的優(yōu)化水平，比如使用 -O3 時(shí)，就要接受其有效性可能會(huì)受到一定的損失。

# 平臺(tái)依賴性

中間表示級(jí)或二進(jìn)制級(jí)的工具總是被集成到有限的依賴于平臺(tái)的宿主編譯器中。比如基于 LLVM 的 SoCets 和 ASan，以及基于二進(jìn)制級(jí)的框架 Valgrind。但 C 是一種跨平臺(tái)的編程語(yǔ)言，這些強(qiáng)平臺(tái)依賴的工具無(wú)法支持我們?cè)诓恢С值钠脚_(tái)上測(cè)試或者部署插樁代碼。

下圖總結(jié)了目前工具所適用的平臺(tái)情況。

# 我們的工作 —— Movec #

有什么辦法來(lái)解決上述的三個(gè)局限性呢？我們從兩個(gè)方面來(lái)解決這三個(gè)問(wèn)題。

第一個(gè)是在 監(jiān)控算法 上面的創(chuàng)新。

我們提出一種 基于智能狀態(tài)的監(jiān)控算法 (smart-status-based, Smatus)，該監(jiān)控算法可以全面地檢測(cè)到上文提到的所有內(nèi)存錯(cuò)誤。

其核心思想是使用了 狀態(tài)節(jié)點(diǎn)，當(dāng)在內(nèi)存當(dāng)中創(chuàng)建一個(gè)內(nèi)存對(duì)象時(shí)，就會(huì)給這個(gè)對(duì)象創(chuàng)建一個(gè)狀態(tài)節(jié)點(diǎn)，記錄內(nèi)存對(duì)象當(dāng)前的狀態(tài)，比如是否仍在活躍當(dāng)中、是否已被釋放等。除了跟蹤每個(gè)指針?biāo)傅倪吔缤?，還會(huì)維護(hù)一個(gè)引用計(jì)數(shù)，用以記錄這些內(nèi)存狀態(tài)到底被多少個(gè)指針?biāo)谩Ｓ捎谟辛诉@些額外的元信息，我們就可以找出現(xiàn)有工具找不出的內(nèi)存錯(cuò)誤。

第二，我們提出了一個(gè)新的 源代碼級(jí)別的插樁框架。

這個(gè)插樁框架并不改寫中間表示或二進(jìn)制代碼，而是直接對(duì)程序員所寫的原始源代碼進(jìn)行操作，并且插入 ANSI C 的源代碼片段，因此插樁后產(chǎn)生的源代碼擺脫了平臺(tái)依賴，可以使用任何的 C 編譯器編譯。

我們實(shí)現(xiàn)了一個(gè)工具 Movec，結(jié)合了上面兩方面的技術(shù)。Movec 架構(gòu)和工作流如下，包含了一個(gè)預(yù)處理器、一個(gè) AST 解析器、一個(gè) AST 訪問(wèn)器 (這個(gè)訪問(wèn)器里面實(shí)際上包含了源代碼的插樁框架)。當(dāng)輸入一個(gè) C 程序時(shí)，程序會(huì)依次經(jīng)過(guò) 預(yù)處理器 -> 解析器 -> 訪問(wèn)器。

代碼插樁發(fā)生在 AST 訪問(wèn)器 (AST Visitor) 里。Movec 會(huì)對(duì)源代碼進(jìn)行改寫，生成一個(gè)修改后的源程序，以及一些接口源文件。這些接口源文件包含了監(jiān)控算法的代碼，會(huì)被自動(dòng)地包含到修改后的 C 程序當(dāng)中，通過(guò)對(duì)此時(shí)的 C 程序進(jìn)行編譯，就得到了一個(gè)可執(zhí)行文件。運(yùn)行該可執(zhí)行文件時(shí)，基于智能狀態(tài)的監(jiān)控算法就能夠自動(dòng)地捕獲程序里的錯(cuò)誤。

# 基于智能狀態(tài)的監(jiān)控算法

## 算法實(shí)現(xiàn)原理

下面通過(guò)幾個(gè)例子，說(shuō)明基于智能狀態(tài)的監(jiān)控算法的基本原理，便于大家有一個(gè)更直觀的理解。

子對(duì)象越界

定義結(jié)構(gòu)體 st 中有兩個(gè)成員 m1 和 m2。

聲明一個(gè)結(jié)構(gòu)體 s，假設(shè)給 s 分配的內(nèi)存空間范圍是 [0x3000, 0x3016]。此時(shí)，監(jiān)控算法會(huì)給 s 創(chuàng)建一個(gè)狀態(tài)節(jié)點(diǎn)，包括狀態(tài) stack，和一個(gè)引用計(jì)數(shù) 1。

接下來(lái)執(zhí)行第二行代碼，讓一個(gè)指針 p 指向 s.m1，這個(gè)時(shí)候會(huì)給 p 創(chuàng)建一個(gè)元數(shù)據(jù)，元數(shù)據(jù)里面會(huì)記錄 p 指向的上界 0x3008 和下界 0x3000。元數(shù)據(jù)里還有一個(gè)指針會(huì)指向 s 的狀態(tài)節(jié)點(diǎn)，通過(guò)指針就能夠找到它所指向的變量是在堆中還是棧中。同時(shí)，引用計(jì)數(shù)變成 2。

第三行代碼中，使用 p[1] 訪問(wèn) p 所指向的對(duì)象，這時(shí)候監(jiān)控算法會(huì)去查詢?cè)獢?shù)據(jù)，看到它能夠訪問(wèn)的正常范圍 [0x3000, 0x3008]，而我們要訪問(wèn)的范圍實(shí)際上是 [0x3000, 0x3016]，顯然超出了所記載的范圍，這個(gè)時(shí)候工具就會(huì)報(bào)錯(cuò)，因?yàn)樵L問(wèn)的范圍超過(guò)了元數(shù)據(jù)中所記錄的范圍。

?段混淆

程序中有一個(gè)函數(shù) foo()，在內(nèi)存當(dāng)中會(huì)給這個(gè)函數(shù)分配一個(gè)空間。假設(shè)它的內(nèi)存地址是 [0x1000, 0x1256]。接下來(lái)會(huì)給這個(gè)函數(shù)創(chuàng)建一個(gè)狀態(tài)節(jié)點(diǎn)，說(shuō)明它的狀態(tài)是一個(gè)函數(shù) function，它的引用計(jì)數(shù)初始值是 1。

第一行代碼中，用一個(gè)指針 p 指向這個(gè)函數(shù)，給指針 p 創(chuàng)建一個(gè)元數(shù)據(jù)，記錄它所指向的上界和下界。由于它是一個(gè)函數(shù)，進(jìn)行特殊處理后，記錄上界是 0x1000，下界是 0x1001。它也有一個(gè)指針指向它的狀態(tài)節(jié)點(diǎn)，引用計(jì)數(shù)變成 2。

第二行代碼中，指針變量 s 也指向這一個(gè)函數(shù)。也會(huì)給 s 創(chuàng)建一個(gè)元數(shù)據(jù)，它的上界是 0x1000，下界是 0x1001。它有一個(gè)指針指向狀態(tài)節(jié)點(diǎn)，同時(shí)引用計(jì)數(shù)變成 3。

第三行代碼中，用 s[0] 來(lái)訪問(wèn)元素，監(jiān)控算法會(huì)去查詢它所指向的對(duì)象是什么。圖中顯示是一個(gè)函數(shù) function，但是解引用的方式卻使用了數(shù)組元素解引用的方式，所以會(huì)發(fā)現(xiàn)它的段類型和使用指針的方式并不匹配，是一個(gè)段混淆錯(cuò)誤。

時(shí)間錯(cuò)誤

首先，使用 malloc 在堆里面分配一個(gè)內(nèi)存對(duì)象，范圍是 [0x2000, 0x2008]。接下來(lái)給這個(gè)內(nèi)存對(duì)象創(chuàng)建一個(gè)狀態(tài)節(jié)點(diǎn)，說(shuō)明它的狀態(tài)是 heap，計(jì)數(shù)器初始值是 0。

在執(zhí)行 p1 = (int*)malloc(8) 時(shí)，給 p1 創(chuàng)建一個(gè)元數(shù)據(jù)，p1 的狀態(tài)節(jié)點(diǎn)指針也指向這一個(gè)狀態(tài)節(jié)點(diǎn)，計(jì)數(shù)器為 1，現(xiàn)在有一個(gè)指針指向它。接下來(lái) p2=p1，給 p2 也創(chuàng)建一個(gè)指針元數(shù)據(jù)，記錄 base 和 bound，它的指針也指向這一個(gè)狀態(tài)節(jié)點(diǎn)，計(jì)數(shù)器變成 2。

接下來(lái)程序執(zhí)行 free(p1)，釋放堆中的內(nèi)存，將狀態(tài)節(jié)點(diǎn)中的狀態(tài)從 heap 改成 invalid，表示它已經(jīng)被釋放。

對(duì) p2 進(jìn)行解引用，監(jiān)控算法會(huì)去檢查 p2 所指向的對(duì)象是否還存在于內(nèi)存當(dāng)中。結(jié)果發(fā)現(xiàn)狀態(tài)變成了 invalid，顯然這是一個(gè)已經(jīng)被釋放的對(duì)象，所以工具會(huì)發(fā)現(xiàn)在訪問(wèn)一個(gè)已經(jīng)被釋放的內(nèi)存對(duì)象，是一個(gè)時(shí)間錯(cuò)誤。

內(nèi)存泄露

在內(nèi)存中分配一個(gè)堆中的對(duì)象，給它創(chuàng)建一個(gè)狀態(tài)節(jié)點(diǎn)，指針 p1、p2 的元數(shù)據(jù)指向這個(gè)狀態(tài)節(jié)點(diǎn)，計(jì)數(shù)器變成 2。

接下來(lái)使用 p1、p2 指向 i 的地址，i 是一個(gè)棧里面的變量，這時(shí) i 的計(jì)數(shù)器變?yōu)?2，heap 的計(jì)數(shù)器變?yōu)?0。

這時(shí)監(jiān)控算法會(huì)發(fā)現(xiàn)有一個(gè)堆中的狀態(tài)節(jié)點(diǎn)，計(jì)數(shù)器是 0，也沒(méi)有指針指向它，報(bào)出一個(gè)內(nèi)存泄漏的錯(cuò)誤。

## 算法數(shù)據(jù)結(jié)構(gòu)

接下來(lái)，我會(huì)對(duì) Smatus 算法中的基本數(shù)據(jù)結(jié)構(gòu)做一個(gè)介紹。

為了檢測(cè)對(duì)象和子對(duì)象層面的空間錯(cuò)誤，Smatus 算法會(huì)維護(hù)一個(gè)指針元數(shù)據(jù) (pointer metadata, PMD) 的結(jié)構(gòu)，包括所指向內(nèi)存的 base 和 bound，還有一個(gè)指針指向內(nèi)存塊的狀態(tài)節(jié)點(diǎn)。

typedefstruct{
void*base;
void*bound;
SND*snda;
}PMD;

Smatus 也會(huì)為每個(gè)內(nèi)存對(duì)象維護(hù)一個(gè)狀態(tài)節(jié)點(diǎn) (status node, SND)。狀態(tài)節(jié)點(diǎn)的結(jié)構(gòu)包括一個(gè)記錄狀態(tài)的成員 stat，和一個(gè)引用計(jì)數(shù)的成員 count。狀態(tài) stat 主要記錄內(nèi)存塊是有效還是無(wú)效，是在堆中還是棧中等。引用計(jì)數(shù) count 主要記錄有多少個(gè)指針指向它。

typedefenum{
function,...
}status;
typedefstruct{
statusstat;
size_tcount;
}SND;

對(duì)不同內(nèi)存錯(cuò)誤的檢查會(huì)用到不同的成員。若是檢查空間錯(cuò)誤，主要使用 base 和 bound；如果檢查時(shí)間錯(cuò)誤和段混淆錯(cuò)誤，主要使用狀態(tài) status；如果檢查內(nèi)存泄漏錯(cuò)誤，主要使用引用計(jì)數(shù) count。

Smatus 也會(huì)為每個(gè)有指針參數(shù)或返回指針的函數(shù)創(chuàng)建并維護(hù)一個(gè)函數(shù)元數(shù)據(jù) (function metadata, FMD)。當(dāng)把一些指針傳到函數(shù)里面，或者是函數(shù)返回一個(gè)指針的時(shí)候，F(xiàn)MD 會(huì)儲(chǔ)存這個(gè)指針的元數(shù)據(jù)。

對(duì)于庫(kù)函數(shù)的調(diào)用，Smatus 也有一些特殊的處理。如果庫(kù)函數(shù)是有源代碼的，可以用工具直接插樁，不需要做額外的處理。如果沒(méi)有源代碼，是預(yù)編譯的，需要給它提供一些包裝函數(shù) wrapper functions，并且在調(diào)用原始函數(shù)之前，檢查參數(shù)的 PMDs 以確保內(nèi)存安全，在調(diào)用后更新存儲(chǔ)返回值的變量的 PMDs。

在 Movec 中，我們已經(jīng)為 C 語(yǔ)言自帶的一些庫(kù)函數(shù)寫好了包裝函數(shù)，這部分是可以直接使用的。更多的技術(shù)細(xì)節(jié)在 ISSTA2021 [2] 的論文中，會(huì)具體描述監(jiān)控算法是如何起作用的，此處不再贅述。

# 源代碼插樁框架

## 傳統(tǒng)基于 IR 的插樁框架

傳統(tǒng)的 IR 級(jí)別的插樁，會(huì)先定義三個(gè)基本的接口：

pmd_tbl_lookup() 主要用來(lái)查找元數(shù)據(jù)表，查詢?cè)獢?shù)據(jù)的狀態(tài)、base、bound 等

pmd_tbl_update() 主要用來(lái)更新元數(shù)據(jù)表，當(dāng)給一個(gè)指針進(jìn)行賦值的時(shí)候，需要更新它的元數(shù)據(jù)

check_dpv() 是當(dāng)在對(duì)指針進(jìn)行解引用的時(shí)候，用來(lái)檢查是否有產(chǎn)生內(nèi)存錯(cuò)誤

插樁過(guò)程舉例。

T *p; 定義一個(gè)指針 p，通過(guò) pmd_tbl_update 更新 p 的元數(shù)據(jù)。

p = &i; 給 p 賦值，再次通過(guò) pmd_tbl_update 更新 p 的元數(shù)據(jù)。根據(jù) p 的地址索引到它的元數(shù)據(jù)，將元數(shù)據(jù)更新為 i 的狀態(tài)、起始地址、結(jié)束地址。

p1 = p; 需要將 p1 的元數(shù)據(jù)更新成和 p 的元數(shù)據(jù)一致。首先通過(guò) pmd_tbl_lookup 找出 p 的元數(shù)據(jù)，存到 pmd 變量中，然后通過(guò) pmd_tbl_update 將 pmd 更新到 p1 的元數(shù)據(jù)中，這樣 p1 就獲得了它所指向?qū)ο蟮脑獢?shù)據(jù)。

i = *p1; 最后對(duì) p1 解引用之前，需要通過(guò) check_dpv 檢查 p1 所指向的元數(shù)據(jù)和它要訪問(wèn)的范圍。

T*p;/*orT*p=NULL*/
pmd_tbl_update(&p,NULL,NULL,NULL);
p=&i;
pmd_tbl_update(&p,i_status,&i,&i+1);
p1=p;/*p1=p+iorp1=&p[i]*/
pmd=pmd_tbl_lookup(&p);
pmd_tbl_update(&p1,pmd->status,pmd->base,pmd->bound);
check_dpv(pmd_tbl_lookup(&p1),p1,sizeof(*p1));
i=*p1;/*or*p1=i*/

上述方法僅適用于基于 IR 的插樁 (比如 SSA 格式)，如果要在源代碼上做插樁，該方法會(huì)帶來(lái)一些問(wèn)題。

首先是內(nèi)嵌的表達(dá)式。比如當(dāng)兩個(gè)操作符寫在一個(gè)語(yǔ)句里面時(shí)，在 IR 級(jí)別，語(yǔ)句會(huì)被拆成兩個(gè)語(yǔ)句。我們可以在中間插入一些語(yǔ)句進(jìn)行檢測(cè)。但是在源代碼級(jí)別，我們是無(wú)法在一個(gè)內(nèi)嵌的語(yǔ)句中間插入一個(gè)語(yǔ)句的。

/*nestedexpressions*/
*(--p);

/*attheIR-level*/
--p;
/*wecaninsertacheckhere*/
/*whichisimpossibleatthesource-level*/
check_dpv(pmd_tbl_lookup(&p),p,sizeof(*p));
*p;

類似地，還有指針?biāo)阈g(shù)運(yùn)算、副作用、內(nèi)嵌的函數(shù)調(diào)用等問(wèn)題。

## 源代碼插樁

那么如何解決上述問(wèn)題？

第一步，我們需要將程序中所有可能出現(xiàn)指針的地方列出來(lái)。我們定義了一個(gè)系統(tǒng)的分類，如下所示，用以表示類型可能在什么地方出現(xiàn)。

Types and storage classes.

具體來(lái)說(shuō)，表中 dlr 表示類型有可能出現(xiàn)在一個(gè)指針變量的定義處 (d - definition)，還有可能出現(xiàn)在指針變量賦值表達(dá)式的左邊 (l - lhs)，或者是一個(gè)賦值表達(dá)式的右邊 (r - rhs)；e 表示指針的解引用 (e - dereference)；vpa 表示函數(shù)的定義和調(diào)用處 (v - return value, p - parameter, a - argument)。除此之外，在結(jié)構(gòu)體和數(shù)組當(dāng)中，也可能包含指針，也需要考慮進(jìn)去。

我們的源代碼插樁框架，主要是通過(guò)一個(gè)遞歸的 AST 訪問(wèn)器來(lái)遍歷整個(gè) AST，并在可能出現(xiàn)指針的地方進(jìn)行插樁。

我們定義了很多的接口，包括一系列針對(duì)不同情況下更新元數(shù)據(jù)的方法、以及檢測(cè)的方法，這邊不再細(xì)述。

/*Interfacesofmetadatatables*/

/*Lookupforthepmdofapointervariablebyaddress.*/
PRFpmd*PRFpmd_tbl_lookup(ptr_addr);

/*Updatethepmdofapointervarusingstatus,baseandbound.*/
PRFpmd*PRFpmd_tbl_update_as(ptr_addr,status,base,bound);

/*Updatethepmdofapointervarandreturnthelastparam.*/
void*PRFpmd_tbl_update_as_ret(ptr_addr,status,base,bound,ret);

/*Updatethepmdofapointervarusingthepmdofanotherone.*/
PRFpmd*PRFpmd_tbl_update_ptr(ptr_addr,ptr_addr2);

/*Updatethepmdofapointervarandreturnthelastparam.*/
void*PRFpmd_tbl_update_ptr_ret(ptr_addr,ptr_addr2,ret);

/*Interfacesofcheckingpmd*/
/*Checkdereferencesofpointervariables.*/
void*PRFcheck_dpv(pmd,ptr,size,...){
stat=PRFpmd_get_stat(pmd);
/*Checkpointervalidity.*/
if(ptr==NULL)print_error();
/*Checktemporalsafety.*/
if(pmd==NULL||stat==PRFinvalid)print_error();
/*Checkspatialsafety.*/
if(ptrbase||ptr+size>pmd->bound)print_error();
returnptr;
}

/*Morecheckingfunctions*/
/*Checkdereferencesofpointerconstants.*/
void*PRFcheck_dpc(base,bound,ptr,size,...);

/*Checkdereferencesoffunctionpointervariables.*/
void*PRFcheck_dpfv(pmd,ptr,...);

/*Checkdereferencesoffunctionpointerconstants.*/
void*PRFcheck_dpfc(base,bound,ptr,...);

除此之外，還有幾個(gè)核心的操作。

Getting KPE

第一個(gè)是獲得核心指針表達(dá)式的操作 (比如為了處理加法操作符)，如下圖所示。在這一個(gè)表達(dá)式里面，實(shí)際上有三個(gè)指針 p、p1、p2，在插樁的時(shí)候，程序應(yīng)該要能夠自動(dòng)分析出 p 是指向 p1 所指向的對(duì)象，還是 p2 所指向的對(duì)象。這里需要使用靜態(tài)分析的方法，根據(jù)類型來(lái)進(jìn)行推導(dǎo)，由于 p1 是一個(gè)指針，而 p2 是一個(gè)整數(shù)，所以右邊的表達(dá)式中最主要的表達(dá)式是 p1，因此 p 應(yīng)該將其元數(shù)據(jù)更新為與 p1 一致。

Getting Address

第二個(gè)是獲得表達(dá)式的地址的操作。在存儲(chǔ)元數(shù)據(jù)時(shí)，是用指針的地址來(lái)作為索引的。所以在更新指針的時(shí)候，首先要獲得表達(dá)式的地址，才能更新它的元數(shù)據(jù)。簡(jiǎn)單的變量是很好處理的，比如一個(gè)指針變量 p，地址就是 &p。同樣地，對(duì)于一個(gè)數(shù)組下標(biāo)表達(dá)式，在前面加一個(gè)取地址符即可。

但對(duì)于一些復(fù)雜的情況，比如 ++p，我們需要先把 p 的地址給存起來(lái) (而不是 ++p 的地址)。對(duì)于函數(shù)，我們會(huì)構(gòu)造一個(gè)新變量 PRFret_ID 去存它的地址，并且將原函數(shù) func() 重寫為 func(&PRFret_ID)，得到函數(shù)返回值的地址，再去索引其函數(shù)返回值的元素。

Getting Status, Base, and Bound

類似地，對(duì)于一個(gè)指針常量，需要獲得它的狀態(tài)、基地址、上界，也是需要靜態(tài)分析去做的。

有了這些基本的分析以后，就解決了上文基于 IR 插樁中存在的挑戰(zhàn)。

當(dāng)然，在開發(fā)的過(guò)程中，我們也面臨著一些設(shè)計(jì)上的選擇。比如使用了分離的元數(shù)據(jù)空間 disjoint metadata space，這可能會(huì)在運(yùn)行時(shí)帶來(lái)更高的負(fù)載，但是它的兼容性更好。我們還使用了多種存儲(chǔ)元數(shù)據(jù)的方法，包括哈希表和 Trie 中。此外，還可以將一部分元數(shù)據(jù)當(dāng)成變量存起來(lái)，這樣可以帶來(lái)更快的查找速度，一定程度上降低時(shí)間上的負(fù)載。

如果大家感興趣，可以去看我們 ISSTA 2019[1]、IEEE TSE 2022[3]的論文。

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

工具 Movec 實(shí)現(xiàn)了前述的技術(shù)。

我們?cè)诎?SARD、MiBench、SPEC、以及自行構(gòu)建的多個(gè)測(cè)試集上進(jìn)行了大量測(cè)試，用以評(píng)估 Movec 的有效性和性能。

1197 benchmarks from Suites IDs 81, 88 and 89 of the NISTSoftware Assurance Reference Dataset (SARD).

124 benchmarks from a new suite to cover typical memory errors that are not included in the SARD.

20 MiBench benchmarks and 5 pure-C SPEC CPU 2017 benchmarks.

我們將 Movec 與三個(gè)最先進(jìn)的工具進(jìn)行比較，即谷歌的 ASan、SoCets 和Valgrind。

Movec 和相關(guān)實(shí)驗(yàn)已通過(guò)了 Artifact Evaluation[8]。

實(shí)驗(yàn)結(jié)果如下。

在檢測(cè)能力 (即有效性) 方面，Movec 在 SARD 測(cè)試集中找出了全部錯(cuò)誤，而其他的工具或多或少都會(huì)漏掉一些。此外，在打開編譯器 O3 優(yōu)化的情況下，Movec 依然不受影響地找出了全部錯(cuò)誤，但是其他的工具找到的錯(cuò)誤會(huì)大幅度減少。在其他的測(cè)試集上，Movec 找到的錯(cuò)也是最多的。

在性能方面，ASan 的速度可能會(huì)更快一些，但是它耗費(fèi)的內(nèi)存比 Movec 要多。而相比 SoCets 和 Valgrind，Movec 在速度和內(nèi)存方面都更優(yōu)。

在可用性方面，Movec 支持跨平臺(tái)，并且報(bào)錯(cuò)友好度更高。

# 總結(jié) #

本次分享中，我們提出了一種新的、全面的智能監(jiān)測(cè)算法 Smatus，其中智能的狀態(tài)是這個(gè)方法的核心。Smatus 可以同時(shí)檢測(cè)空間錯(cuò)誤、時(shí)間錯(cuò)誤、段混淆錯(cuò)誤和內(nèi)存泄漏。

我們還提出了一種新的基于源碼級(jí)的插樁框架，并從中獲得了很多好處，比如找到了更多的錯(cuò)誤、優(yōu)化不敏感、支持跨平臺(tái)、報(bào)錯(cuò)友好度更高等。

實(shí)驗(yàn)結(jié)果表明，Movec 有著更強(qiáng)的錯(cuò)誤查找能力和可用性，并且開銷適中。

審核編輯：湯梓紅