張歡歡

(安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽馬鞍山243032)

0 引言

隨著計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，保障計(jì)算機(jī)和網(wǎng)絡(luò)上的信息安全性變得越來越重要。但是，傳統(tǒng)保障信息安全的機(jī)制仍存在缺陷，不能夠充分保障信息端到端的安全。D.E.Denning首先提出了信息流的概念，信息流是指若存儲(chǔ)在對(duì)象y(源頭)中的信息直接或間接地影響x(目標(biāo))，則對(duì)象y和x之間存在信息流。D.E.Bell和L.J.LaPadula提出并描述了安全信息流。J.Goguen和J.Meseguer也分別闡明了程序訪問的安全信息流特性。程序的信息流安全是信息流安全的一個(gè)重要研究方向。[1]事實(shí)上，攻擊者可以以多種不同方式獲取機(jī)密信息或者隱私信息：直接泄密(最簡(jiǎn)單且直截了當(dāng)?shù)男姑芊绞?，直接將機(jī)密信息傳給攻擊者；間接泄密(有時(shí)候也稱為隱蔽存儲(chǔ)信道)，機(jī)密信息被編碼在可觀察程序行為的程序中，程序可能根據(jù)機(jī)密數(shù)據(jù)的數(shù)據(jù)值不同而執(zhí)行不同的數(shù)據(jù)訪問；時(shí)間泄密(或者通過一個(gè)隱蔽時(shí)間信道)，當(dāng)程序?qū)C(jī)密數(shù)據(jù)編碼在與時(shí)間有關(guān)的行為時(shí)，或攻擊者通過在一個(gè)特定時(shí)間間隔期間測(cè)量資源的可用性從而可以觀察操作方式來操作共享資源時(shí)，時(shí)間泄密就會(huì)發(fā)生了。程序也可能通過其終止行為泄密信息。例如，當(dāng)機(jī)密數(shù)據(jù)滿足一些條件時(shí)，程序就正常終止或者進(jìn)入無限循環(huán)，可以認(rèn)為通過非終止泄密是一個(gè)特殊的時(shí)間泄密情況。[2]外部時(shí)間隱蔽信道已經(jīng)被用于在實(shí)踐中泄露信息和打破密碼系統(tǒng)。[3]現(xiàn)有緩解外部時(shí)間信道的機(jī)制，對(duì)于基于語言的信息流來說那些之前的機(jī)制在應(yīng)用中是非常受限的。現(xiàn)提出基于冗余代碼插入來平衡時(shí)間差，經(jīng)過轉(zhuǎn)換規(guī)則轉(zhuǎn)換的代碼，攻擊者不能通過測(cè)量執(zhí)行與機(jī)密信息有關(guān)的操作時(shí)間來得到機(jī)密信息。

1 命令式語言：語法和操作語義

命令式語言SIPL(Simple Imperative Programming Language)作為本文討論方法的載體，以下分別給出其語法和操作語義。SIPL語法和語義的定義參考了文獻(xiàn)[4]～文獻(xiàn)[5]的部分內(nèi)容。

1.1 語法

SIPL語法包括表達(dá)式和命令，其BNF范式如下：

e∷=(表達(dá)式)

n(整型)

υ(變量)

！(非)

c∷=(命令)

υ∶=e|skip|skip(n)|

ifethenc1elsec2

whileedoc

語法說明：本文所使用的表達(dá)式和命令的語法構(gòu)件與常見的命令式語言相同,以下僅給出必要的解釋和假設(shè)，如skip(n)表示有n個(gè)skip (n為2時(shí)：skip;skip)。

1.2 操作語義

為定義SIPL的操作語義，需要一個(gè)表達(dá)存儲(chǔ)狀態(tài)的函數(shù)σ:υ→(?υ,συ無定義)，它是變量名集合υ到自然數(shù)的函數(shù)。其次是表達(dá)式的語義函數(shù)，其歸納定義如下：

為了簡(jiǎn)化對(duì)執(zhí)行時(shí)間的計(jì)算，定義了函數(shù)τ。τ(e)，表示執(zhí)行表達(dá)式e所需要的時(shí)間單位數(shù)；τ(c)，表示執(zhí)行命令c所需要的時(shí)間單位數(shù)。

單位時(shí)間是指基于Intel core i7的一個(gè)指令周期。[5]

SIPL命令(線程)的操作語義是通過程序格局上的遷移關(guān)系“→”來定義的,格局G是一個(gè)三元組(c,σ,κ),其中：c是當(dāng)前正要執(zhí)行的命令;σ是程序的狀態(tài);κ(κ∈)是多少個(gè)時(shí)間單位。SIPL命令的結(jié)構(gòu)化操作語義定義如下。

1)if條件分支

(skip,σ,κ)→(_,σ,κ)

(x∷=e,σ,κ)→(_,σ[x|→eσ],κ+τ(e)+1)

2)while循環(huán)和sequence

2 轉(zhuǎn)換規(guī)則

給出的轉(zhuǎn)換規(guī)則包括以下算法1、算法2和算法3。算法中加粗字體是語法元素，而其他語法元素是源程序中的語句。

為了保證程序的安全，雖然給出的算法在一定程度上對(duì)程序的執(zhí)行時(shí)間產(chǎn)生了影響，但并不會(huì)影響源程序的語義，而且隨著處理器能力的提升，產(chǎn)生的時(shí)間影響是可以接受的。

2.1 轉(zhuǎn)換規(guī)則

1)算法1 轉(zhuǎn)換規(guī)則

//輸入：可以通過外部事件泄漏信息的源程序p

//輸出：攻擊者不能通過外部事件得到機(jī)密信息的程序

① Trans(p){

②ifpiscthen//單條命令

③ifpis skipthenp

④ifpis assignmentthenp

⑤ifpis cond-branchthenBasicF(p)//算法2，條件分支的處理

⑥ifpis while-loopthenBasicW(p)//算法3，while循環(huán)的處理

⑦elseifpisc1;c2thenTrans(c1);Trans(c2);//組合命令

⑧}

2)算法2 條件分支的處理

① BasicF(ifethenc1elsec2){

②ife不包含機(jī)密信息then

③returnifethenc1elsec2; //源程序無需改變

④elseife包含機(jī)密信息then

⑤ifc1是基本表達(dá)式then

⑥t1←τ(c1)

⑦ifc2是基本表達(dá)式then

⑧t2←τ(c2)

⑨ift1>t2then

⑩returnifethenc1else{c2;skip(t1-t2) };//在源碼中添加冗余代碼

//嵌套的處理

3)算法3 while循環(huán)的處理

① BasicW(whileedoc){

②ife不含敏感信息then

③returnwhileedoc;//源程序無需處理

④elsee含敏感信息then

⑤e′=e;//防止在c中會(huì)改變e

⑥ifc是基本表達(dá)式then;//通過在源程序添加冗余代碼來平衡時(shí)間

⑦returnwhileedoc;while !e′ doc′;

⑧ifc含有while循環(huán)thenBasicW(c);

⑨ifc含有條件分支thenBasicIF(c);

⑩}

算法說明：c′為c的影子，并且在c′中使用新的變量稱為影子變量(例如算法3中的e′)。將c中的賦值使用影子變量進(jìn)行重新賦值，類似加減乘除操作。同樣使用影子變量進(jìn)行再次操作，不影響源程序語義的同時(shí)彌補(bǔ)時(shí)間以消除外部時(shí)間泄漏機(jī)密信息。

2.2 實(shí)例分析

1)實(shí)例1

secret = 0;

i = 0;

while(i < 10000){

if(i%2 == 0){

secret +=1;

}

i++;

}

假設(shè)secret為機(jī)密變量，例中執(zhí)行時(shí)間主要在while循環(huán)中，而while循環(huán)的執(zhí)行時(shí)間又都在if分支中，if分支中存在機(jī)密變量的計(jì)算。攻擊者可以根據(jù)if分支的執(zhí)行時(shí)間而得到機(jī)密變量secret的值。

secret = 0;

i = 0;

while(i < 10000){

if(i%2 == 0){

secret += 1;

}else{ //平衡時(shí)間

skip;//加操作占用1個(gè)時(shí)間單位

}

i++;

}

例中代碼段是對(duì)源程序進(jìn)行轉(zhuǎn)換后的源碼，通過添加冗余代碼，使得if分支和else分支的執(zhí)行時(shí)間相同，攻擊者不再能夠根據(jù)程序的執(zhí)行時(shí)間而得到機(jī)密變量值。

2)實(shí)例2

sum = 1;

if( h == 1){

while (h<101){

sum = sum + 1;

}

} else {

sum = 5000;

}

假設(shè)h為高級(jí)別機(jī)密變量，由于if分支和else分支的執(zhí)行時(shí)間相差很大，攻擊者可以根據(jù)條件分支的結(jié)束時(shí)間得到機(jī)密變量h的值。

sum = 1;

sum′ = 1;

h′ = h;

if( h == 1){

while (h < 101){

sum = sum + 1;

}

} else {

sum = 5000;

while(h′ < 101){

sum′ += 1;

}

}

通過轉(zhuǎn)換的程序可以平衡掉if分支和else分支的時(shí)間差。通過添加影子變量的形式為源程序作出轉(zhuǎn)換，根據(jù)源程序的時(shí)間差添加冗余代碼。這樣就不能通過觀察if分支和else分支的執(zhí)行時(shí)間得到高級(jí)別機(jī)密變量的值，以達(dá)到保護(hù)機(jī)密變量的目的。

3 證明

對(duì)于給定的程序c，分下面2種情況進(jìn)行證明。

1)情況1

?σ,?κ

(Trans(c),σ,0)→(_,σ′,κ)

(Trans(c),σ,0)→(_,σ′,κ′)

有κ=κ′

對(duì)于給定的程序，從開始執(zhí)行到結(jié)束也許有多條路徑。程序的執(zhí)行時(shí)間可能根據(jù)不同的路徑而不同。經(jīng)過轉(zhuǎn)換規(guī)則進(jìn)行轉(zhuǎn)換的源碼，只要是能正常結(jié)束，那么無論走哪條路徑，其執(zhí)行時(shí)間是相同的。

2)情況2

如果轉(zhuǎn)換的程序有一條路徑不能執(zhí)行結(jié)束，那么對(duì)于任意一條執(zhí)行路徑都是不能終止的。

4 相關(guān)研究

Smith和Volpano在文獻(xiàn)[6]中描述了通過禁止那些依賴于機(jī)密數(shù)據(jù)的循環(huán)來解決終止信道的類型系統(tǒng)，形式化了Timing agreement理論。Timing agreement理論指出擁有獨(dú)立于高級(jí)數(shù)據(jù)的循環(huán)和分支條件的順序程序?qū)?huì)執(zhí)行在lock-step中。而lock-step具有環(huán)境的低安全部分獨(dú)立于高安全級(jí)別數(shù)據(jù)。但是他們并沒有處理時(shí)間泄漏，而是以一種靈活的方式泄漏給外部觀察者。

Agat在文獻(xiàn)[2]中描述一個(gè)代碼轉(zhuǎn)化的方法。通過冗余計(jì)算來填充程序移除外部時(shí)間泄露，并且通過禁止在機(jī)密數(shù)據(jù)上循環(huán)來避免終止信道。Agat′s轉(zhuǎn)變的一個(gè)缺點(diǎn)：如果有一個(gè)條件上有機(jī)密數(shù)據(jù)，并且只有其中一個(gè)分支是非終止的，轉(zhuǎn)換后的程序就是非終止的。

外部緩解是另一種控制外部時(shí)間信道的方法，它們通過定量限制多少信息通過外部事件交互泄漏。[7]但是由于外部緩解將計(jì)算看作黑盒，因此并不能區(qū)分良性時(shí)間變量和泄漏信息的變量。當(dāng)多數(shù)變量是良性變量時(shí)，將導(dǎo)致效率明顯地下降。

文獻(xiàn)[8]提出了一種基于語言的緩解方法。使用mitigate原語擴(kuò)展簡(jiǎn)單的While-language，他們的工作依賴于靜態(tài)注釋來提供有關(guān)底層硬件信息。

5 結(jié)語

時(shí)間信道一直以來都被認(rèn)為是計(jì)算機(jī)信息安全最嚴(yán)峻的挑戰(zhàn)之一，而外部時(shí)間信道由于其測(cè)量的難度，一直都是研究的難點(diǎn)。

本文提出了一種基于冗余代碼插入的外部時(shí)間信道屏蔽方法，通過額外的計(jì)算得到與機(jī)密信息有關(guān)的條件分支和循環(huán)的執(zhí)行時(shí)間，并根據(jù)得到的時(shí)間對(duì)含有機(jī)密信息的條件分支和循環(huán)進(jìn)行冗余代碼插入，從而消除外部觀察者通過觀察程序的執(zhí)行時(shí)間而得到機(jī)密信息。給出了一種轉(zhuǎn)化方法，并對(duì)其進(jìn)行了證明。

今后的工作，會(huì)繼續(xù)改進(jìn)方法使其更加接近實(shí)用，并將其應(yīng)用于開發(fā)程序。