龔萌曉, 謝惠揚

(北京林業(yè)大學 理學院,北京 100083)

0 引 言

C語言是一種應用廣泛的計算機語言,其功能豐富、使用靈活、可移植性好[1]。但是C語言的語法檢查不是很嚴格,一些未定義的操作結果若不注意使用則容易出現(xiàn)錯誤,且也容易出現(xiàn)編譯正常卻運行異常的情況[2]。文獻[3]詳細列舉了C語言的諸多缺陷,這些問題可能會影響數(shù)據(jù)的安全性,造成內存的占用,甚至會導致系統(tǒng)崩潰等。文獻[4]對不同編程語言存在的漏洞進行了分類。文獻[5]將使用C語言開發(fā)程序時存在的漏洞分為5種,并分析產(chǎn)生漏洞的原因,進而提出利用漏洞實施的攻擊和緩解漏洞的技術。因此，研究C語言的缺陷,從而避免缺陷和漏洞的產(chǎn)生尤為重要。

拓撲學、代數(shù)學和分析學被認為是基礎數(shù)學的三大領域[6]，拓撲學在計算機科學方面的應用主要是在圖像處理和圖論基礎等方面[6]。目前，新興的拓撲數(shù)據(jù)分析(topology data analysis,TDA)已成為研究的熱點。本文擬用拓撲學分析C語言中字符串函數(shù)缺陷,運用拓撲學解決C語言程序缺陷是一種新的方法，需要借鑒拓撲學在其他領域里的應用。很多針對拓撲學的應用往往得不到定量的結果,僅僅是定性分析。

1 C語言字符串缺陷函數(shù)示例

在C語言編程中,字符型數(shù)據(jù)并不是以字符形式存儲在內存中,而是以字符的整數(shù)形式存在存儲單元中,且大多數(shù)操作系統(tǒng)采用ASCII字符集編碼[1]。C語言中沒有字符串類型的變量,如果要將一個字符串存放在內存中,那么需要使用字符數(shù)組進行操作[1]。雖然編譯系統(tǒng)提供的字符串庫函數(shù)給用戶帶來了極大的便利，但是字符串函數(shù)運行過程對變量不做邊界長度檢查卻造成了許多缺陷。尤其在大型的編譯代碼中 稍有差錯便不能得到正確的輸出結果,更為嚴重的是會產(chǎn)生內存問題[7]。由于C語言對變量不做邊界檢查,代碼在一定程度上會造成緩沖區(qū)溢出,從而難以得到正確的輸出結果,這就是最為典型和常見的緩沖區(qū)溢出漏洞[8]。

下面給出2個缺陷函數(shù)的示例代碼。

(1) 示例代碼1。strcpy函數(shù)溢出缺陷示例代碼為：

#include〈stdio.h〉

#include〈string.h〉

int main()

{

chars1[10];

chars2[20]=“the source string”;

strcpy(s1,s2);

}

strcpy為string copy(字符串復制)的縮寫,其作用是將字符數(shù)組s2存儲的字符串復制到字符數(shù)組s1中[1]。這里要求s1定義的長度足夠大,以使s1能夠容納s2中的字符串。編程人員有時將s2直接定義為常量,但是因為strcpy函數(shù)不檢查字符串長度,所以容易出現(xiàn)錯誤。在示例代碼1中s2中的字符串“the source string”的長度大于10,但是s1的長度只是10,因此s1的長度不能夠容納s2中的字符串,復制后便造成緩沖區(qū)溢出。

(2) 示例代碼2。strcat函數(shù)溢出缺陷示例代碼為：

#include〈stdio.h〉

#include〈string.h〉

int main()

{

chars1[20]=“the string1 and”;

chars2[10]=“string2”;

strcat(s1,s2);

}

strcat函數(shù)為string catenate(字符串連接)的縮寫,作用是將字符數(shù)組s2的字符串連接在字符數(shù)組s1的字符串后面,然后把結果存放在字符數(shù)組s1中[1]。此處同樣要求s1定義的長度足夠大,以使s1能夠容納連接后的新字符串。示例代碼2中s1和s2連接后的字符串“the string1 and string2”的總長度超過分配給s1的長度20,說明分配給s1的長度不足，這便造成緩沖區(qū)溢出。

由2個示例代碼可見,使用字符串函數(shù)時應當對字符數(shù)組定義足夠大的長度,以便字符數(shù)組能夠容納處理后的新字符串[9]，C語言在編譯過程中不會給出錯誤信息,因而一旦運行往往很難得到理想的輸出結果[10]。對于大型的編程文件來說,出現(xiàn)一點小的錯誤,結果卻可能千差萬別,甚至容易被黑客利用，造成具有危害性的結果[8]。

2 拓撲空間有關定義

點集拓撲學與其他的幾何學相比,更具有靈活性和可塑性。點集拓撲學中應用最頻繁的特性可歸納為“3個C”:連續(xù)性(continuous)、連通性(connectedness)和緊致性(compactedness)[6]。通過點與集合構造拓撲空間的結構,并考查拓撲空間中的不變性質是拓撲學應用的關鍵之一。本文主要根據(jù)其具有連續(xù)性特點分析問題。

定義1[11]設X是一個集合,T是X的一個子集族,如果T滿足如下條件:

(1) ?,X∈T。

(2) 若A,B∈T，則A∩B∈T。

(3) 若T1?T,則∪A∈T1A∈T,稱T是X的一個拓撲。如果T是集合X的一個拓撲,那么稱偶對(X,T)是一個拓撲空間,或稱集合X是一個相對于拓撲T而言的拓撲空間,簡稱集合X是一個拓撲空間。此外T中的每一個元素為拓撲空間(X,T)或X中的一個開集。

定義2[11]設X和Y是2個拓撲空間,映射f:X→Y,如果Y中每個開集U的原像f-1(U)是X中的一個開集,那么稱f是X到Y的一個連續(xù)映射。

定義3[11]設(X，T)是一個拓撲空間,x∈X,如果U是X的一個子集,并滿足條件:存在一個開集V∈T使得x∈V?U,那么稱U是點x的一個鄰域。點x所有鄰域構成的X子集族被稱之為點x的一個鄰域系。

定理1[11]如果U是包含著點x的一個開集,那么它一定是點x的一個鄰域。

定義4[11]設X是一個拓撲空間,A?X。如果點x∈X的每一個鄰域U中都有A中異于x的點,即U∩(A-{x})≠?,那么稱點x是集合A的一個凝聚點。集合A的所有凝聚點構成的集合稱為A的導集,記為d(A)。

3 基于拓撲空間的缺陷檢測

一般地,拓撲學往往用于對問題進行定性分析[6]。本文將通過映射的連續(xù)性分析C語言中字符串函數(shù)的溢出缺陷。

3.1 字符串函數(shù)的拓撲刻畫

定理3 令C語言代碼chars[n+1]中的s是一個賦初始長度為n+1的字符數(shù)組,s[0]～s[n]是s的n+1個數(shù)組元素。如果X為所有數(shù)組元素s[i]中存儲的字符為元素構成的集合,其中0≤i≤n(若實際字符串長度小于n,那么默認令終止符后面的字符元素為空);如果Tx為數(shù)組元素s[0]～s[j]中存儲的字符為元素構成的集合,其中0≤j≤n;那么Tx是X的一個子集族,而且Tx是X的一個拓撲,偶對(X,Tx)是一個拓撲空間。

證明由X和Tx的形式可知:

(1) ?∈Tx,當j=n時，可得X∈Tx。

(2) 若A,B∈Tx,設A表示s[0]～s[i]中存儲的字符為元素構成的集合，B表示s[0]～s[j]中存儲的字符為元素構成的集合,其中0≤i≤n,0≤j≤n,則有i≤j或j≤i成立。當i≤j時，A?B,A∩B=A∈Tx；當j≤i時，B?A,A∩B=B∈Tx,故有A∩B∈Tx。

(3) 若T1?Tx,由(2)中的討論可知∪A∈T1A表示T1中存儲字符元素數(shù)目最大的那個字符元素集合,則∪A∈T1A∈T1?Tx,因此有:

∪A∈T1A∈Tx。

Tx滿足定義1中的3個條件,因此由定義1可知,Tx是X的一個拓撲,偶對(X,Tx)是一個拓撲空間,Tx中的每一個元素就是X中的一個開集。

例1C語言代碼為chars[10]=“string”,則該語句的結構如圖1所示。

圖1 C語言代碼為char s[10]=“string”的結構

X={s,t,r,i,n,g}，

Tx={?,{s},{s,t},{s,t,r},{s,t,r,i},{s,t,r,i,n},{s,t,r,i,n,g}}。

為了不引起混淆,定義使用[s[i]](0≤i≤n)表示數(shù)組元素s[i]中存儲的字符元素，則有拓撲空間X={[s[0]],[s[1]],…,[s[n]]},定義的拓撲Tx={?,{[s[0]]},{[s[0]],[s[1]]},…,{[s[0]],[s[1]],…,[s[n]]}}。

對于點x∈X,不妨設x={[s[i]]}(0≤i≤n),令U={[s[0]],[s[1]],…,[s[i]]},由此可見U∈Tx,則U是X的一個開集,且x∈U,由定理1可知,U是x的一個鄰域。此外,由定義3中鄰域的定義可知,需要存在一個開集V∈Tx滿足x∈V?U,由定理3中Tx的形式可以看出包含x的開集V的形式,這說明點x=[s[i]]的最小鄰域的形式為U={[s[0]],[s[1]],…,[s[i]]}。

設子集A?X和點x∈X，當A為單點集時,設A={[s[i]]}(0≤i≤n),存儲在數(shù)組元素s[i]中。當點x為在[s[i]]之前的字符元素時,A-{x}={[s[i]]},x的其中一個鄰域U={[s[0]],[s[1]],…,[s[i-1]]}滿足U∩(A-{x})=?,由定義4可知,這些點x不是A的凝聚點。

綜上所述,可得定理4。

C語言代碼chars1[n1+1]和chars2[n2+1]中的s1和s2是2個字符數(shù)組,把s1和s2中存儲的字符為元素構成的集合看作定理4中定義的拓撲空間,分別記為拓撲空間X1和X2,對應的拓撲分別記為Tx1和Tx2。假設s1和s2初始賦值的字符串長度分別為m1+1和m2+1(m1≤n1,m2≤n2),其中,s1[m1]和s2[m2]分別存儲字符串的終止符。下文擬利用映射的連續(xù)性進行缺陷檢測。

3.2 strcpy函數(shù)缺陷檢測

對于示例代碼1中的代碼strcpy(s1,s2),利用strcpy函數(shù)將s2中字符串內容復制到s1中。定義同名映射strcpy表示strcpy(s1,s2),由strcpy函數(shù)的意義可知,映射strcpy:X2→X1,其逆映射記為strcpy-1。

定理5在代碼沒有缺陷的情況下,strcpy映射是一個連續(xù)映射。

由定理5可知,當strcpy映射不是一個連續(xù)映射時,代碼是存在缺陷的。如果?A∈Tx1,當strcpy-1(A)?Tx2時,即存在X1中的一個開集,其原像不是X2的開集,那么由定義2可知,strcpy不是一個連續(xù)映射。此時在拓撲空間中不能夠保持開集的不變性,說明代碼是存在缺陷的,不能輸出正確的復制結果。

對于示例代碼1,s1定義了10個數(shù)組元素,在代碼沒有缺陷的情況下,即當s2中的字符元素數(shù)目不大于10時,strcpy映射是一個連續(xù)映射。此時對于任意0≤i≤9,有[s1[i]]=[s2[i]],代碼可以正常地復制字符串并且一對一輸出正確的復制結果。如果至少存在一個0≤i≤9使得[s1[i]]≠[s2[i]],即存在X1中的一個開集A={[s1[0]],[s1[1]],…,[s1[i]]}∈Tx1,但是A的原像strcpy-1(A)≠{[s2[0]],[s2[1]],…,[s2[i]]},從而有strcpy-1(A)?Tx2,那么strcpy映射不是一個連續(xù)映射,代碼存在溢出缺陷。

3.3 strcat函數(shù)缺陷檢測

對于示例代碼2中的代碼strcat(s1,s2),利用strcat函數(shù)將s2中字符串內容連接在s1后面。定義同名映射strcat表示strcat(s1,s2),由strcat函數(shù)的意義知,映射strcat:X2→X1,其逆映射記為strcat-1。

定理6 在代碼沒有缺陷的情況下,strcat映射是一個連續(xù)映射。

由定理6可知,當strcat映射不是一個連續(xù)映射時,代碼是存在缺陷的。如果?A∈Tx1,當strcat-1(A)?Tx2時,即存在X1中的一個開集,其原像不是X2的開集,那么由定義2可知,strcat不是一個連續(xù)映射。說明存在溢出缺陷,連接后的字符元素個數(shù)超過初始定義的字符數(shù)組長度。

對于示例代碼2,s1定義了20個數(shù)組元素,在代碼沒有缺陷的情況下,即當s1和s2賦值的字符元素數(shù)目之和不大于20時,strcat映射是一個連續(xù)映射,此時代碼可以正常地連接字符串并且輸出正確的結果。如果存在X1中的一個開集A={[s1[0]],[s1[1]],…,[s1[i]]}∈Tx1,但是A的原像strcpy-1(A)≠{[s2[0]],[s2[1]],…,[s2[i]]},從而strcpy-1(A)?Tx2,那么strcat映射不是一個連續(xù)映射,代碼存在溢出缺陷。

4 結 論

本文運用點集拓撲學分析了C語言存在的缺陷。本研究的具體創(chuàng)新性主要有2個方面: ① 本文將點集拓撲學和C語言缺陷檢測結合起來,運用拓撲學分析了C語言存在的缺陷；② 本文從2個字符串處理函數(shù)入手,構造拓撲空間和空間之間的連續(xù)映射,利用拓撲空間的連續(xù)性發(fā)現(xiàn)2個C語言字符串函數(shù)的缺陷。揭示了2個C語言字符串函數(shù)的缺陷。

本文僅限于使用連續(xù)性解決字符串函數(shù)中由于長度分配不足造成的緩沖區(qū)溢出缺陷,并考慮能否應用定理3中的拓撲結構解決C語言中存在的其他缺陷。另外,還考慮了能否利用拓撲空間的連通性、緊致性等性質來判定C語言中是否存在缺陷。