基于動態分析的程序設計課程教學系統①

陳 哲,王 沖,黃志球

1(南京航空航天大學 計算機科學與技術學院,南京 211106)

2(高安全系統的軟件開發與驗證技術工業和信息化部重點實驗室,南京 211106)

程序設計是計算機、軟件工程等工科專業的第一門核心必修專業課程,其教學內容通常包括C 程序設計語言[1]、面向對象程序設計語言(例如C++)[2].由于后續專業課程(例如數據結構、編譯原理、軟件工程、軟件測試等)都需要使用程序設計來完成實驗和課程設計,而且程序設計也是計算機和軟件行業招聘面試的核心考查內容,所以熟練地掌握程序設計技能不僅是學習后續專業課程的基礎,也是獲得理想工作機會的重要條件.因此,如何改進程序設計課程教學、讓學生更好地掌握課程知識點是重要的研究課題[3–7].

筆者在教學實踐中發現,雖然采用了網絡教學組織[3,4]和在線判題[5–7]教學系統,學生還是很難掌握程序設計語言中一些復雜的或抽象的理論知識,也很難將這些知識正確地運用到編程實踐中.以C 程序設計教學為例,指針和內存操作較為復雜[1].程序內存被劃分為代碼段、數據段、BSS 段、棧、堆等不同的段,而每個段都有不同的訪問規則[8],例如:代碼段中的數據只能讀不能寫,棧中的數據不能被顯式釋放,堆中分配的內存塊被釋放后不能再次訪問,對內存塊的訪問不能超過該內存塊的上界和下界等.所以照本宣科式地講授相關的理論知識,學生難以消化吸收,更無法正確運用,使得編寫的程序經常帶有內存錯誤,導致錯誤的運行結果和耗時的調試過程.事實上,在工業界的軟件開發實踐中,內存錯誤也一直是最常見、危害最大的程序錯誤之一,它可以導致數據腐敗、安全漏洞和程序崩潰等致命后果,例如阿麗亞娜5 號火箭控制系統軟件的內存溢出錯誤導致火箭在升空后爆炸[9].因此,教師有必要使用教學系統幫助學生牢固掌握指針和內存操作的相關知識、更快地找到程序中的內存錯誤,從而正確運用指針和內存操作.

以面向對象程序設計教學為例,封裝、繼承、多態是面向對象的三大特性[2],但是這些概念較為抽象.注意,C 程序設計教學關注的是程序具體功能相關的知識點,如循環語句、函數等.與之不同,面向對象程序設計教學關注的是非功能的知識點,例如封裝、繼承、多態的主要目標是改善大規模代碼的模塊化、可維護性、可復用性、健壯性等.所以咬文嚼字式地講授相關的概念定義,或者通過小例子輔助教學,學生都難以理解這些特性的優點,更無法主動地在編程實踐中合理地運用,使得編寫的程序經常不具備面向對象的特征,導致程序模塊性差、難于維護.因此,教師有必要使用教學系統幫助學生深入理解面向對象的特性,從而正確運用面向對象程序設計思想.

基于上述教學需求,本文設計并使用C++程序設計語言實現了面向程序設計課程的教學系統:C 程序內存安全性動態分析系統(以下稱為Movec).該系統包含了C 程序編譯器前端,通過遞歸式遍歷和重寫程序源代碼的抽象語法樹(AST),實現對程序源代碼的自動插樁;通過編譯運行插樁后的源代碼,實現對內存錯誤的動態檢測.該系統綜合運用了C 程序設計、面向對象程序設計(C++)、數據結構、編譯原理、軟件工程、軟件測試等計算機和軟件工程專業核心課程的知識,同時可以展現這些知識之間的深度融合.學生通過學習和使用該系統有助于理解和掌握相關的理論知識,以及這些理論知識在實際軟件開發過程中的應用,可以激發學生學習的主動性和鉆研的興趣,從而有效地提高教學效果.

1 總體規劃

1.1 基本技術

程序分析技術是一種對程序行為進行自動分析的過程,通常用于發現程序中的缺陷和錯誤,例如內存安全性缺陷、死循環等邏輯錯誤.

程序分析技術分為靜態和動態兩種.靜態分析不需要運行程序,而是通過對程序代碼進行邏輯推理來檢測錯誤.由于靜態分析需要確保性能(在短時間內報告結果),而這是以檢測精度為代價的,因此通常有誤報和漏報.動態分析通過代碼插樁技術在代碼中插入用于錯誤檢測的代碼片段,從而在運行時實現對程序執行過程的分析和錯誤檢測[10].動態分析的優點是考慮了程序實際運行環境等因素,理論上不存在誤報.因此本系統采用基于動態分析的方法.

動態分析所采用的代碼插樁技術通常對程序的中間表示[11]或二進制代碼插樁[12],導致無法報告錯誤在源代碼中的準確位置,給錯誤調試帶來障礙.因此本系統采用源代碼插樁技術[13],即直接對源代碼進行重寫,在檢測到錯誤時,可以報告錯誤所在的源文件名和行號等.

1.2 系統結構

圖1展示了Movec 系統的總體結構,主要由C 程序解析器和遞歸式AST 訪問者組成.對于用戶給定的C 程序,Movec 首先使用C 程序解析器將程序源代碼解析為AST,然后通過遞歸式遍歷和訪問AST 上的每個節點,分析程序語義,并插入相應的用于錯誤檢測的代碼片段,生成插樁后的源代碼和接口文件(包括實現錯誤檢測算法的數據結構和接口函數).用戶通過編譯插樁后的源代碼,得到插樁后的可執行程序.最后用戶運行該程序,實現對內存錯誤的動態檢測.

2 錯誤檢測與自動插樁算法

內存錯誤動態檢測的基本思想是為每個指針變量分配一個指針元數據(Pointer Meta Data,PMD),用于記錄指針變量所指向的內存塊的下界、上界和狀態信息,并在程序通過指針變量訪問內存時檢測指針元數據所記錄的信息是否允許這次訪問.下面我們通過實例介紹錯誤檢測算法的基本思想.

圖1 系統結構圖

實例1.下列C 程序首先將指針p 初始化為指向變量i,然后對指針p+5 進行解引用和賦值.顯然,由于p+5 超出了變量i 所在內存塊的范圍,因此會發生內存溢出錯誤.

int i=1,*p=&i;

*(p+5)=1;

我們的檢測算法可以發現該錯誤.在程序初始化指針p 之后,檢測算法首先為指針p 分配一個指針元數據(如圖2所示),用于記錄p 所指向的內存塊的下界&i、上界&i+1 和狀態stack,其中stack 表示該內存塊(變量i)是被存儲在棧中的有效變量(即沒有被釋放),然后將該指針元數據插入指針元數據表,并使用p 的地址&p 作為該元數據的索引值,用于加快查找指針元數據的速度.

圖2 實例1 中指針p 的指針元數據

在程序對指針p+5 進行解引用訪問之前,檢測算法首先使用p 的地址&p 作為索引值在指針元數據表中查找p 的指針元數據,然后檢測程序即將訪問的內存塊范圍是否在指針元數據所記錄的下界和上界之間.由于程序即將訪問的內存塊范圍是從&i+5 到&i+6,超出了元數據所記錄的從&i 到&i+1 的范圍,因此存在內存溢出錯誤.此時檢測算法將報告內存錯誤及其所在的源文件名、行號、列號和導致錯誤的內存訪問表達式“*(p+5)”.

實例2.下列C 程序首先在函數foo 中將指針n 初始化為指向函數foo 中的局部變量x,然后在退出函數foo 后對指針n 進行解引用和賦值.顯然,由于n 所指向的變量x 此時是無效變量(即已經被釋放),因此會發生內存釋放后訪問的錯誤.

我們的檢測算法可以發現該錯誤.在程序初始化指針n 之后,檢測算法首先為指針n 分配一個指針元數據(如圖3(a)所示),用于記錄n 所指向的內存塊的下界&x、上界&x+1 和狀態stack,然后將該指針元數據插入指針元數據表,并使用n 的地址&n 作為該元數據的索引值.

圖3 實例2 中指針n 的指針元數據及其變化

在程序退出函數foo 之前,程序釋放函數foo 中所有的局部變量,檢測算法將n 的指針元數據中的狀態改為invalid,表示n 所指向的內存塊(變量x)已經被釋放(如圖3(b)所示).

在程序對指針n 進行解引用訪問之前,檢測算法首先使用n 的地址&n 作為索引值在指針元數據表中查找n 的指針元數據,然后檢測指針元數據所記錄的狀態是否不是invalid.由于此時元數據所記錄的狀態是invalid,因此存在內存釋放后訪問的錯誤.此時檢測算法將報告內存錯誤及其所在的源文件名、行號、列號和導致錯誤的內存訪問表達式“*n”.

我們通過以下3 個接口函數來實現以上錯誤檢測算法的主要功能:

1)接口函數pmd_tbl_update_as 用于更新給定指針變量p 的指針元數據,將&p 所索引的指針元數據的內容設置為給定的下界、上界和狀態信息.

2)接口函數pmd_tbl_lookup 用于獲取給定指針變量p 的指針元數據,返回&p 所索引的指針元數據的地址.

3)接口函數check_dpv 用于檢測要訪問的內存塊范圍是否在指針元數據所記錄的下界和上界之間、狀態是否有效.

接下來我們需要實現對程序源代碼的自動插樁,使得程序能在運行時調用以上接口實現對內存錯誤的動態檢測.算法1 給出了自動插樁的基本思想:通過遞歸式遍歷和訪問程序源代碼AST 上的每個節點,在合適的位置插入對以上接口的調用.例如,在指針變量定義之后插入對其pmd 的初始化操作,在指針變量賦值語句之后插入對其pmd 的更新操作,在指針解引用表達式之前插入對比其pmd 和實際訪問的內存塊范圍的檢測操作.

算法1.內存錯誤動態檢測的自動插樁算法遍歷程序源代碼AST,對于每個訪問到的節點:1)如果該節點是指針變量定義,例如“T *p;”或帶有空初始值“T*p=NULL;”,則在該語句后插入接口調用:pmd_tbl_update_as(&p,NULL,NULL,NULL);2)如果該節點是從指針常量到指針變量的賦值語句,例如“p=&i;”,則在該語句后插入接口調用:pmd_tbl_update_as(&p,&i,&i+1,i_status);3)如果該節點是從指針變量到指針變量的賦值語句,例如“p1=p;”,“p1=p+I;”或“p1=&p[i];”,則在該語句后插入接口調用:pmd=pmd_tbl_lookup(&p);pmd_tbl_update_as(&p1,pmd->base,pmd->bound,pmd->status);4)如果該節點包含指針解引用表達式,例如“i=*p1”或“*p1=i”,則在該語句前插入接口調用:check_dpv(pmd_tbl_lookup(&p1),p1,sizeof(*p1));然后遞歸訪問該節點的子節點.

3 系統開發

Movec 系統的開發包括兩部分:使用C 程序設計語言實現錯誤檢測算法,使用C++程序設計語言實現源代碼自動插樁算法.為了用戶可以在不同的平臺上使用Movec,我們充分利用C/C++的跨平臺特性,采用基于CMake 編譯系統的跨平臺架構,使得Movec 可以在Linux 和Windows 上運行.

3.1 錯誤檢測函數庫的實現

由于C 程序設計語言并不自帶容器類數據結構,因此我們從零開始實現了一個高效的指針元數據表.如圖4所示,指針變量ptr 的指針元數據包括該指針變量的地址&ptr、所指向內存塊的下界base、上界bound 和狀態信息節點的地址&st.由于多個指針(例如ptr1 和ptr2)可能指向同一個內存塊,因此內存塊的狀態信息節點必須是一個獨立的節點,這樣才可能被多個指針元數據引用.整個指針元數據表是使用指針變量地址為索引值的哈希表.圖5展示了指針元數據結構定義的UML 圖,其中指針變量的地址是指向指針的指針類型,下界和上界是指針類型,狀態信息節點的地址是指向狀態信息節點的指針類型.在狀態信息節點中,我們使用無符號整數表示內存塊的當前狀態,例如invalid、stack、heap 等.

圖4 指針元數據表

圖5 指針元數據

基于指針元數據表,實現錯誤檢測算法的3 個接口函數是較為直接的.例如,接口函數pmd_tbl_update_as先在指針元數據表中查找給定指針變量p 的指針元數據,如果未找到則插入一個新的指針元數據,然后對該元數據中的成員變量進行賦值.

3.2 源代碼自動插樁的實現

自動插樁實現的關鍵在于遞歸式AST 訪問者的實現.為了展示面向對象程序設計的特性,在實現中融合了封裝、繼承和多態.首先,設計了一個基本的AST訪問者類ASTVisitorBase,包含對程序源代碼AST 上各種節點進行訪問的成員虛函數VisitX,然后實現了Traverse 成員函數,在對AST 進行遞歸式遍歷的同時調用VisitX 函數來對AST 上的每個節點進行訪問,其中X 可以是任意類型的節點,例如訪問聲明Decl 的函數VisitDecl 和訪問語句Stmt 的函數VisitStmt 等.然后,設計了一個實現插樁的AST 訪問者類ASTVisitor,繼承于ASTVisitorBase,并對其中的成員虛函數VisitX 進行虛函數重載,實現源代碼插樁功能.

4 實施方案

Movec 的使用非常簡便.用戶只需要執行3 個命令即可得到檢測結果:運行Movec 對源代碼進行自動插樁;運行編譯器將插樁后的源代碼編譯為可執行程序;運行插樁后的可執行程序得到檢測結果.例如,圖6和圖7分別展示了對第2 節中的實例1 和實例2 進行檢測的過程.結果顯示,實例1 中對指針p+5 的解引用導致了空間錯誤(即內存溢出錯誤),實例2 中對指針n 的解引用導致了時間錯誤(即內存釋放后訪問).值得注意的是,檢測結果也報告了錯誤在源代碼中的精確位置,包括源文件名和行號等.

圖6 實例1 的檢測結果

圖7 實例2 的檢測結果

Movec 可以被用于C 程序設計語言的教學,有效提高教學效果.首先,學生可以對自己編寫的程序運行Movec,更快地找到程序中的內存錯誤,極大地縮短調試時間,提高學習效率.通過長期使用Movec,學生能養成正確運用指針和內存操作的習慣,提高編程能力.第二,Movec 的錯誤檢測函數庫可以作為C 語言的演示系統,幫助學生掌握C 語言中一些復雜的理論知識.函數庫的實現不僅大量使用了基本的條件語句、循環語句、數組、函數等,還覆蓋了較為復雜的指針和內存操作、結構體和鏈表等知識.例如,指針元數據采用結構體實現,并包含了指向狀態信息節點的指針;指針元數據表采用基于動態內存分配的哈希表實現,并采用鏈表來處理哈希沖突.這可以幫助學生深入理解這些理論知識,并掌握如何將這些知識正確地運用到編程實踐中.

Movec 可以被用于面向對象程序設計語言(C++)的教學,有效提高教學效果.Movec 的源代碼自動插樁模塊可以作為C++語言的演示系統,幫助學生掌握C++語言中一些抽象的理論知識.插樁模塊的實現覆蓋了重要但抽象的封裝、繼承和多態等知識.例如,AST中所有的語法節點類型都采用了封裝的類來實現,并且采用繼承來描述相關節點類型之間的聯系;遞歸式AST 訪問者的實現也采用了封裝、繼承和多態,即繼承于一個基本的AST 訪問者類,并對其中的AST 節點訪問函數進行虛函數重載;通過這些設計改善了大規模代碼的模塊化、可維護性、可復用性和健壯性.這可以幫助學生深入理解這些面向對象特性的優點,并主動地將這些知識合理地運用到編程實踐中.

Movec 也可以作為數據結構、編譯原理、軟件工程、軟件測試等課程的案例分析材料,全面貫穿計算機、軟件工程等專業的培養計劃.

5 結論

程序設計是計算機、軟件工程等工科專業的第一門核心必修專業課程.熟練地掌握程序設計技能不僅是學習后續專業課程的基礎,也是獲得理想工作機會的重要條件.筆者在教學實踐中發現,已有的教學系統只支持網絡教學組織[3,4]和在線判題[5–7],并不能幫助學生掌握課程難點.為此,我們設計和實現了面向程序設計課程的教學系統:C 程序內存安全性動態分析系統.該系統綜合運用了C 程序設計、面向對象程序設計(C++)、數據結構、編譯原理、軟件工程、軟件測試等計算機和軟件工程專業核心課程的知識,同時可以展現這些知識之間的深度融合.從教學效果來看,該系統不僅可以幫助學生理解和掌握相關的理論知識,以及這些理論知識在實際軟件開發過程中的應用,還可以激發學生學習的主動性和鉆研的興趣,從而有效地提高教學效果.