許金超，曾國蓀

(1.同濟大學 計算機科學及技術(shù)系，上海 201804；2.教育部嵌入式系統(tǒng)與服務計算教育部重點實驗室，上海 201804)

1 引言

隨著互聯(lián)網(wǎng)的快速發(fā)展，數(shù)字產(chǎn)品的分發(fā)變得簡單快捷，傳播范圍更加寬廣。數(shù)字產(chǎn)品的版權(quán)保護受到了嚴峻的挑戰(zhàn)，其中，軟件產(chǎn)品的狀況尤為不容樂觀，軟件盜版已經(jīng)成為軟件開發(fā)者最大的威脅。最近的報告[1]表明，2011年世界被盜版的軟件占總軟件數(shù)量的42%，價值高達630億美元，而中國的盜版率更是高達77%。盜版的猖獗嚴重打擊了軟件開發(fā)者的積極性，為軟件開發(fā)者提供有效的軟件保護方法成為亟待解決的問題。軟件水印是軟件保護方法中一種重要的技術(shù)，它將標志版權(quán)的秘密信息嵌入到要保護的軟件中達到保護的目的，這些秘密信息不影響軟件使用，不易被察覺，并且難以清除，在盜版發(fā)生時可以提取出來證明該文件的版權(quán)所有。

軟件水印通常分為靜態(tài)軟件水印和動態(tài)軟件水印2種[2]。靜態(tài)軟件水印隱藏在程序文件自身中，如保存在數(shù)據(jù)段或代碼段，而動態(tài)軟件水印則在程序運行時實時生成，信息隱藏在運行過程中的內(nèi)部狀態(tài)中。動態(tài)軟件水印又可以劃分為數(shù)據(jù)結(jié)構(gòu)水印(data structure watermark)、執(zhí)行過程水印(execution trace watermark)和復活節(jié)彩蛋水印(easter egg watermark) 3類[2,3]。數(shù)據(jù)結(jié)構(gòu)水印算法以 CT算法[2]為代表，它也是已知的第一個動態(tài)軟件水印算法。CT算法中，軟件水印隱藏在程序運行時動態(tài)建立的圖拓撲結(jié)構(gòu)中。同一類型的算法還有文獻[4]～文獻[6]等。執(zhí)行過程水印算法以動態(tài)路徑算法[7]為代表，它給出了Java程序和本地代碼程序2種不同載體下的實現(xiàn)方式，軟件水印隱藏在程序執(zhí)行過程中選擇的路徑分支中。文獻[8]是另外一種典型的執(zhí)行過程水印算法，它通過在 Java程序中選擇部分方法，在這些方法的第一個基本塊中使用一定數(shù)量的內(nèi)存，從而改變程序的運行過程中的等分時間片內(nèi)內(nèi)存的使用數(shù)量來隱藏軟件水印。執(zhí)行過程水印的實現(xiàn)算法還有文獻[9]～文獻[11]等。文獻[12]提出的混沌軟件水印算法屬于復活節(jié)彩蛋水印算法，它利用混沌序列把軟件水印信息均勻散列在程序的代碼段中，當輸入正確的密鑰時，軟件水印信息通過對話框的形式顯示給用戶。

已有的動態(tài)軟件水印算法中仍存在許多不足的地方。首先是算法實現(xiàn)時較少結(jié)合載體程序的性質(zhì)，用于隱藏軟件水印的代碼和程序中原有代碼存在明顯不同，從而造成了軟件水印和載體程序之間產(chǎn)生了一條分界線，使得軟件水印容易被發(fā)現(xiàn)并發(fā)動針對性的攻擊。如CT算法中，隱藏軟件水印的數(shù)據(jù)結(jié)構(gòu)的生成過程和程序的正常功能缺少聯(lián)系，很容易遭到逆向攻擊者懷疑，且存在大量重復性的代碼，無法抵抗模式匹配攻擊。其次，在目前已實現(xiàn)的動態(tài)軟件水印算法中，保護對象都是以Java程序為主，適用于本地代碼程序的算法所占比例仍然不高。本地代碼程序常見的以C或C++語言等開發(fā)，它們在執(zhí)行效率上存在的優(yōu)勢使之在軟件市場中依然占據(jù)重要份額，因此用于本地代碼程序的軟件水印算法仍有很大的需求。最后，已有的許多軟件水印算法只能容忍小范圍的軟件變換，然而目前有許多技術(shù)可以將一個程序大范圍改變的面目全非，例如代碼變形技巧能夠?qū)⑼欢未a變換成數(shù)種不同的形式。實用的軟件水印算法需要能抵抗形形色色的攻擊。

為了解決已有軟件水印算法的這些不足，需要面向使用C或C++等語言編程的開發(fā)者，提出一種高度隱蔽并且有效抵抗各種攻擊的軟件水印算法。程序執(zhí)行過程中，內(nèi)存操作是很常見的行為，對內(nèi)存分配釋放的方式和使用的內(nèi)存數(shù)量進行修改對程序的大小影響不大，而且不容易引起懷疑。文獻[8]正是修改了程序類方法中的內(nèi)存使用數(shù)量達到嵌入軟件水印的目的，盡管總是在類方法的第一個基本塊中使用內(nèi)存這一行為也易受矚目，但仍然提供了一種可借鑒的實現(xiàn)思想。然而在本地代碼程序中，程序中的函數(shù)通常不像Java程序中的類方法那么普遍，也不存在虛擬機可供方便的統(tǒng)計內(nèi)存的使用信息。除此之外，Java程序中不需關(guān)心內(nèi)存釋放、數(shù)組越界等內(nèi)存問題，而本地代碼中的內(nèi)存操作造成的內(nèi)存泄露、內(nèi)存溢出、野指針等內(nèi)存相關(guān)問題至今都是軟件開發(fā)中需要面對的考驗，并且這些問題依然會在很長一段時間內(nèi)存在。對于擁有程序源代碼的開發(fā)者則可以通過對程序的了解比攻擊者更清楚的優(yōu)勢利用內(nèi)存操作隱藏軟件水印，而對程序細節(jié)不了解的攻擊者任意修改內(nèi)存會造成多種內(nèi)存問題?；谶@些考慮，本文提出一種基于內(nèi)存操作的動態(tài)軟件水印算法。該方法通過調(diào)整內(nèi)存的分配釋放時機和分配的內(nèi)存數(shù)量以及程序執(zhí)行時使用的內(nèi)存數(shù)量來嵌入軟件水印，并充分利用開發(fā)者相對于攻擊者的優(yōu)勢，通過內(nèi)存分配和使用之間的制約關(guān)系增加攻擊者修改內(nèi)存的難度來保證軟件水印的安全。

2 基本概念

令P表示一個可執(zhí)行程序，I表示P的一個合法輸入，這里I可以為空，此時表示程序不需要外在輸入，如不帶參數(shù)的命令行程序。

定義1 動態(tài)簇。動態(tài)簇是P在給定輸入I下執(zhí)行經(jīng)過的部分代碼的集合。

根據(jù)不同的劃分準則，可以把程序執(zhí)行過程中經(jīng)過的所有代碼劃分為若干個動態(tài)簇。下文中動態(tài)簇簡稱簇。

定義2 簇間內(nèi)存分配關(guān)系。如果P運行過程中簇a中分配的所有內(nèi)存中有nbyte的內(nèi)存在簇b中得到釋放，則稱簇b釋放了簇a分配的nbyte的內(nèi)存，記作R(a, b)= n。

定義3 簇間內(nèi)存使用關(guān)系。如果程序P運行過程中簇a分配的內(nèi)存在簇b執(zhí)行結(jié)束時（若簇b執(zhí)行結(jié)束前這些內(nèi)存已經(jīng)釋放則是這些內(nèi)存釋放時）有nbyte的內(nèi)存較簇b執(zhí)行開始時不同，則稱簇b使用了簇a分配的nbyte的內(nèi)存，記作U(a,b)=n，若a=b，則令U(a,b)=0。

定義4 內(nèi)存關(guān)系矩陣。設P的執(zhí)行過程按順序劃分為 n個簇 c1、c2、…、cn，則矩陣 PR、PU分別是按如下定義的n階方陣。

其中，PR稱為內(nèi)存分配矩陣，PU稱為內(nèi)存使用矩陣，顯然，當j＜i時，PR中元素滿足rij=0；當j≤i時，PU中元素uij=0，即PR、PU是三角矩陣。為了充分利用矩陣空間，便于隱藏數(shù)據(jù)，對于三角矩陣PR和PU，可以合為一個n×n矩陣M，稱為內(nèi)存關(guān)系矩陣。其中，M=PR+PUT即M中元素滿足

3 基于內(nèi)存操作的軟件水印算法

3.1 算法概述

本文算法中軟件水印的載體為本地代碼程序，在嵌入時需要擁有程序的源代碼，在此基礎(chǔ)上，通過修改源代碼操控內(nèi)存行為從而在源代碼編譯來的程序中嵌入軟件水印。

程序中涉及到的內(nèi)存有用戶態(tài)內(nèi)存和內(nèi)核態(tài)內(nèi)存之分，如果同時考慮所有這些內(nèi)存需要擁有內(nèi)核權(quán)限，這通常不太現(xiàn)實。為了簡化操作，本文所指的內(nèi)存指的能在編程中使用指定函數(shù)或關(guān)鍵字分配的內(nèi)存，如C語言中的malloc、calloc等函數(shù)。

算法在實現(xiàn)過程使用了IDA Pro軟件[13]，IDA Pro是一款優(yōu)秀的反編譯工具和調(diào)試器，支持 IDC腳本，提供 SDK實現(xiàn)功能擴展，并且附帶IDAPython插件[14]支持Python腳本。算法中大部分的實現(xiàn)工作通過編寫Python腳本完成，涉及到源代碼修改時需要人工參與來保證修改的正確性。

嵌入過程分為4個主要步驟。首先，對程序進行分簇；其次，監(jiān)控程序執(zhí)行，生成內(nèi)存關(guān)系矩陣；然后，將軟件水印嵌入到內(nèi)存關(guān)系矩陣中；最后，根據(jù)嵌入軟件水印后的內(nèi)存關(guān)系矩陣修改程序源代碼。提取過程相對簡單，它可分為3個主要步驟:首先，對已嵌入軟件水印的程序進行分簇；然后，監(jiān)控含軟件水印程序的運行得到內(nèi)存關(guān)系矩陣；最后，從內(nèi)存關(guān)系矩陣中提取軟件水印。

3.2 簇間內(nèi)存關(guān)系統(tǒng)計

在嵌入軟件水印和提取軟件水印的過程中，都需要統(tǒng)計程序中的簇間內(nèi)存關(guān)系得到內(nèi)存關(guān)系矩陣。這一準備工作包括簇的劃分和生成內(nèi)存分配矩陣、內(nèi)存使用矩陣2部分。下文中仍用P表示可執(zhí)行程序，I表示程序P運行時的秘密輸入。

3.2.1 簇的劃分

本節(jié)給出按數(shù)量劃分、按時間劃分和按輸入分簇3種簇劃分方式，用以適應不同的軟件水印載體程序，劃分中都使用密鑰ω將P在輸入I下運行時產(chǎn)生的執(zhí)行蹤跡劃分為n個簇。

按數(shù)量分簇方式中，首先在輸入I下運行程序P，記錄程序執(zhí)行過程中的指令總量，然后以密鑰ω作為隨機種子，將程序運行過程中執(zhí)行的指令劃分為n段。每段作為一簇。這種劃分方式下的分簇過程實現(xiàn)簡單，而且劃分時輸入I可以為空，適用于控制臺程序等缺乏輸入?yún)?shù)的小規(guī)模單線程程序。

按時間分簇方式首先要選擇合適的輸入I使得P的運行能夠維持在一個相當長的時間內(nèi)，如用延長2次鼠標點擊的間隔來控制程序運行總時間。在I下執(zhí)行程序P并記錄該輸入下程序的運行時間，然后利用密鑰 ω作為隨機種子對運行時間進行劃分。當每個劃分的時間片到達時，掛起程序中斷P的運行，將在分時間片內(nèi)參與執(zhí)行的代碼作為一簇，這同樣將P的運行蹤跡劃分為n簇。此分簇方式需要較長的程序執(zhí)行時間，不適用于無法控制程序運行時間的程序。

按輸入分簇同樣需要選擇秘密輸入I使程序P能夠執(zhí)行相當長的一段時間，同時秘密輸入自身也需要由足夠多的連續(xù)子輸入構(gòu)成，利用密鑰ω將這些子輸入劃分為n個連續(xù)不相交集合，在每個子輸入集合下執(zhí)行的代碼作為一簇，同樣把程序劃分為n簇。這種分簇方式適合操作比較復雜的程序。

3.2.2 內(nèi)存分配矩陣和內(nèi)存使用矩陣的生成

分簇確定后即可監(jiān)測簇間的內(nèi)存關(guān)系，進而得到內(nèi)存分配矩陣和內(nèi)存使用矩陣。這一過程可以根據(jù)對源代碼的理解結(jié)合調(diào)試器通過人工分析的方式來完成，然而對較大的程序這種方法工作量過大，需要給出這一過程的自動化實現(xiàn)方法。

根據(jù)簇間內(nèi)存分配和使用關(guān)系的定義，實現(xiàn)中要跟蹤程序執(zhí)行過程中分配的每一內(nèi)存塊從分配到釋放整個過程中在每一簇間的變換情況，因此執(zhí)行過程中每一內(nèi)存塊需要記錄表1所示的內(nèi)容。

表1 內(nèi)存塊信息記錄包含的內(nèi)容

程序運行過程中指定函數(shù)分配的所有內(nèi)存塊信息記錄組織成內(nèi)存塊記錄表，使用數(shù)據(jù)庫存放。收集這些內(nèi)存塊信息的偽代碼實現(xiàn)如圖1內(nèi)存塊信息收集算法所示。為了防止載體程序在調(diào)試態(tài)下產(chǎn)生的內(nèi)存差異，通過在載體程序入口點設置斷點的方式由系統(tǒng)啟動IDA，然后在IDA中載入腳本運行內(nèi)存塊信息收集算法。內(nèi)存塊信息收集算法中數(shù)字標出的4個部分是算法中最核心的內(nèi)容，下面給出進一步說明。

圖1 內(nèi)存塊信息收集算法

1) 攔截相關(guān)內(nèi)存函數(shù)，創(chuàng)建并啟動監(jiān)控線程

攔截相關(guān)內(nèi)存函數(shù)就是在載體程序中相關(guān)的內(nèi)存函數(shù)入口處及出口處設置斷點，從而接管內(nèi)存函數(shù)獲得創(chuàng)建或釋放的內(nèi)存塊信息。IDA提供了API可以簡化了這一過程的實現(xiàn)。此后創(chuàng)建監(jiān)控線程并傳入載體程序信息，監(jiān)控線程負責控制載體程序的輸入，并根據(jù)選擇的分簇信息計算載體程序每一簇結(jié)束的地址，并擇機在載體程序中加入簇斷點。

2) 內(nèi)存分配函數(shù)調(diào)用時記錄分配的內(nèi)存塊信息

當載體程序中發(fā)生內(nèi)存分配操作的時候在內(nèi)存塊記錄表里生成一條新內(nèi)存塊記錄，在記錄中填入該內(nèi)存塊的 ID、Address、Size、AllocateClusterID、SourceLine等信息。最后分配一個大小和該內(nèi)存塊大小相同的影子內(nèi)存暫時保存該內(nèi)存塊內(nèi)容。

3) 內(nèi)存塊釋放時更新該內(nèi)存塊信息記錄

當監(jiān)測到內(nèi)存釋放操作時，查找內(nèi)存塊記錄表，找出待釋放的內(nèi)存塊所在的記錄，填入ReleaseClusterID，比較待釋放的內(nèi)存塊對應的影子內(nèi)存和待釋放內(nèi)存塊當前數(shù)據(jù)的差異并將變化的內(nèi)存數(shù)量值填入該內(nèi)存塊記錄中 ReleaseClusterID對應的MemDif_Cluster字段中，然后釋放相應的影子內(nèi)存。

4) 簇中斷時更新所有未釋放的內(nèi)存塊記錄

當發(fā)生簇中斷時意味著當前簇結(jié)束馬上進入下一簇的執(zhí)行，設當前簇簇號為 k。此時在內(nèi)存塊記錄表中找到當前每一個未釋放的內(nèi)存塊，比較該內(nèi)存塊和對應的影子內(nèi)存的差異，計算變化的內(nèi)存數(shù)量，然后將此數(shù)值填入該內(nèi)存塊記錄中的MemDif_Cluster_k字段中，最后將該內(nèi)存塊內(nèi)容保存到影子內(nèi)存中。

當程序執(zhí)行完成時，相應的內(nèi)存塊記錄表也已經(jīng)完善。 統(tǒng)計表中的內(nèi)存分配釋放記錄，將結(jié)果按定義填入內(nèi)存分配矩陣。統(tǒng)計表中的內(nèi)存塊在各個簇間的變化記錄，將結(jié)果按定義填入內(nèi)存使用矩陣。

為了進一步降低誤差，可以重復多次生成內(nèi)存分配矩陣和內(nèi)存使用矩陣，然后對得到的矩陣中的對應元素求平均值。

3.3 軟件水印的嵌入

軟件水印首先使用量化技術(shù)嵌入在內(nèi)存分配矩陣和內(nèi)存使用矩陣合并而來的內(nèi)存關(guān)系矩陣中，內(nèi)存關(guān)系矩陣每個元素嵌入一位軟件水印數(shù)據(jù)，然后修改載體程序源代碼使得源代碼編譯后的本地代碼程序生成的內(nèi)存關(guān)系矩陣和量化后的內(nèi)存關(guān)系矩陣完全一致。

3.3.1 軟件水印的嵌入過程

設嵌入到程序P中的軟件水印W是寬高皆為n的二值圖像，設其對應 n×n的二值矩陣為 NW={wij}n×n，其中，wij=0或1。則在P中嵌入W的步驟如下。

1) 利用密鑰ω對NW進行置亂變換，設置亂后的矩陣為 PW={pij}n×n。

2) 在輸入I下運行程序P并利用密鑰ω將其劃分為n個簇。

3) 監(jiān)測簇間內(nèi)存關(guān)系得到內(nèi)存分配矩陣PR、內(nèi)存使用矩陣PU，計算內(nèi)存關(guān)系矩陣M=PR+PUT，顯然M中元素mij和PM中元素pij存在一一對應關(guān)系。

4) 根據(jù)pij的值是0還是1，使用2個不同的量化器Q0、Q1對mij進行量化。2個量化器分別為

對 Q0、Q1有 Q(x) ≥ x 且 Q(Q(x))= Q(x)。即量化之后的數(shù)據(jù)不低于沒量化以前，并且已量化的數(shù)據(jù)再次量化將保持不變。為了便于內(nèi)存對齊，這里取量化步長Δ=4y，其中，y∈N+。

對 M 中所有元素進行量化后得到的矩陣記為M'={m'ij}n×n。

5) 由于分配的內(nèi)存數(shù)量需要高于使用的內(nèi)存數(shù)量，同時也不能過高造成內(nèi)存的浪費。在上一步驟的量化過程中，當M中來自于內(nèi)存使用矩陣PU的元素 mij發(fā)生改變時，即 mij≠m'ij且 j＜i，此時需要分配較多的內(nèi)存來滿足內(nèi)存使用量增加帶來的內(nèi)存需求，即要對M'中來自PR的元素進行修改。若mij=0,則令 m'ji= Qpji(mji+m'ij?mij)。若 mij≠0，則至少存在一個簇j分配并在簇i使用的內(nèi)存塊，設在內(nèi)存監(jiān)測記錄中找到該內(nèi)存塊將在簇 k釋放，則令m'jk= max{m'jk, Qpjk(mjk+m'ij?mij)}，暫存該內(nèi)存塊編號留待下一步驟使用。完成所有這些元素修改后的矩陣用 M''={m''ij}n×n表示。

6) 最后修改源程序使其編譯后得到的本地代碼程序生成的內(nèi)存關(guān)系矩陣和 M''一致，這需要找出所有M''和M不一致的元素并在源代碼中相應位置進行修改。

① 首先修改源代碼改動內(nèi)存分配數(shù)量。對任一滿足 mij≠m''ij且 i≤j的元素，顯然該元素涉及到簇i和簇j間的內(nèi)存分配關(guān)系。查找內(nèi)存塊記錄表，若存在簇i分配簇j釋放的內(nèi)存塊記錄，并且步驟5)存儲的內(nèi)存塊正是其中一個，則根據(jù)該內(nèi)存塊記錄中的SourceLine定位內(nèi)存分配在源代碼中位置，調(diào)整分配該內(nèi)存塊的函數(shù)申請的內(nèi)存數(shù)量，否則任選一個內(nèi)存塊記錄表中簇i分配簇j釋放的內(nèi)存塊對應的分配函數(shù)進行調(diào)整，使其分配的內(nèi)存數(shù)量增加m''ij?mij；若簇i中不存在對應于簇j釋放的內(nèi)存的分配關(guān)系，則在簇 i生成內(nèi)存分配函數(shù)分配m''ij?mij大小的內(nèi)存并在簇j釋放，選擇合適位置插入生成的代碼并保證任何輸入下程序執(zhí)行時分配的內(nèi)存一定可以釋放。

② 然后修改源代碼使之滿足M''和M中i＞j且mij≠m''ij的元素的變化，這說明簇j中分配并在簇i中使用的內(nèi)存大小需要改為 m''ij，該內(nèi)存在簇j中分配，所以簇j分配的內(nèi)存塊中，優(yōu)先選擇上面改動內(nèi)存分配數(shù)量時添加的內(nèi)存分配函數(shù)和改動的內(nèi)存分配函數(shù)分配的內(nèi)存塊，根據(jù)該內(nèi)存塊的地址和調(diào)整后的大小計算結(jié)束地址，然后在簇i中插入代碼實現(xiàn)在該內(nèi)存塊結(jié)束地址處從后往前改動該內(nèi)存塊的內(nèi)容，共改動 m''ij?mij大小的內(nèi)存。重復這個過程完成所有來自于內(nèi)存使用矩陣的不一致元素的處理。這一步驟的中的內(nèi)存修改，在改動數(shù)量較小的情況下可以針對內(nèi)存中的每個字節(jié)寫入一個不同的值，改動數(shù)量較大時也可以利用memset之類的庫函數(shù)一次更改一塊內(nèi)存。

3.3.2 軟件水印嵌入過程中的問題和處理方式

嵌入軟件水印的過程需要對載體程序的源代碼進行修改，修改的內(nèi)容包括以下3種:改變內(nèi)存分配的數(shù)量、成對增加內(nèi)存分配和釋放操作、對分配的內(nèi)存內(nèi)容進行修改。修改編譯后的載體程序大小和執(zhí)行時間已經(jīng)有所變化，需要解決這些變化對軟件水印和載體程序可能帶來的影響，保證修改后的載體程序中已經(jīng)正確地包含了軟件水印，并且不會影響載體程序的正確運行。

首先，源代碼修改導致編譯后的載體程序發(fā)生變化，由于軟件水印實際上隱藏在載體程序所生成的內(nèi)存關(guān)系中，因此需要保持軟件水印嵌入前后分簇的位置一致，從而保證軟件水印嵌入前后載體程序生成的內(nèi)存關(guān)系矩陣的對應。若算法中使用按時間分簇方式或按輸入分簇方式，只需在選擇恰當?shù)拿孛茌斎氡ＷC程序的執(zhí)行時間足夠長，此時源代碼修改編譯后在本地代碼程序中增加的代碼內(nèi)容產(chǎn)生的執(zhí)行時間遠遠小于整個程序的執(zhí)行時間，因此程序嵌入軟件水印前后簇劃分的位置不變或微變。此時無需對已嵌入軟件水印的程序做任何處理即可保證程序的修改對簇間內(nèi)存關(guān)系不產(chǎn)生影響。若算法中使用按數(shù)量分簇方式，當編譯后的載體程序自身參與執(zhí)行的代碼較多且增加的代碼在其中所占比例極小時，此時程序修改后分簇中每個簇的位置較程序修改前只相差少數(shù)指令，而影響內(nèi)存關(guān)系的代碼落入這部分指令中的概率不大，同時適當調(diào)整增加的代碼的位置，使其不對簇間內(nèi)存關(guān)系產(chǎn)生影響。對于自身體積較小的載體程序來說需要在編譯后的載體程序中各個簇之間按比例插入冗余指令保證程序修改前后每個簇仍然劃分在正確的位置。

其次，算法利用修改源代碼的方式使得軟件水印嵌入在編譯后的載體程序中，程序編譯過程中產(chǎn)生的符號調(diào)試文件在編譯后的程序和源代碼之間架起了橋梁，從而根據(jù)載體程序的內(nèi)存關(guān)系矩陣需要改動的數(shù)據(jù)可以正確地定位在源代碼中實現(xiàn)修改的位置，同時源代碼修改編譯后的程序也可以正確的生成需要的內(nèi)存關(guān)系矩陣，保證了源代碼修改編譯后的載體程序正確的嵌入了軟件水印。

最后，修改不會影響載體程序的正確性，改變內(nèi)存分配數(shù)量只是調(diào)整了內(nèi)存分配函數(shù)中的一個參數(shù)，成對增加內(nèi)存分配操作是通過開發(fā)者人工參與的方式進行保證所有分配的內(nèi)存都會得到正確的釋放，而對分配的內(nèi)容進行修改過程修改的內(nèi)存內(nèi)容是在額外分配的內(nèi)存上進行的，不會影響程序中原有的內(nèi)存內(nèi)容，因此軟件水印嵌入過程中的源代碼修改在編譯后得到的程序能夠正確運行，不會出現(xiàn)內(nèi)存問題。

3.4 軟件水印的提取

提取算法已知分簇總數(shù)n和密鑰ω，利用輸入I從含軟件水印的程序PW中提取出軟件水印，步驟如下。

1) 輸入I下運行程序PW，并利用密鑰ω將其分為n個簇。

2) 監(jiān)控程序運行并記錄內(nèi)存關(guān)系，得到內(nèi)存分配矩陣PRW、內(nèi)存使用矩陣PUW。

3) 計算 DW=PRW+(PUW)T將 PRW、PUW合并為n階方陣DW={dij}n×n，對DW中所有元素利用下述計算式尋找最近的量化點。

由wij組成的矩陣記作 ′W ={wij}n×n。

4)利用密鑰 ω 對 ′W 進行逆置亂變換得到的矩陣設為W，以W中每個元素作為像素得到的二值圖像就是要提取的軟件水印。

4 算法評估

評價一個軟件水印算法可以從平臺依賴性、可信性、數(shù)據(jù)率、隱蔽性、抗攻擊能力等方面進行。平臺依賴性衡量算法跨平臺使用的能力，可信性表明檢測到的軟件水印能否有效證明用戶版權(quán)。數(shù)據(jù)率衡量程序能嵌入的軟件水印容量。隱蔽性反映嵌入軟件水印前后載體程序的屬性差異。開銷衡量算法應用時需要花費的代價?？构裟芰υu價軟件水印算法在各種攻擊下能夠正確提取軟件水印的能力。

對軟件水印算法的評價結(jié)合實驗分析的方式進行，實驗基于3個Windows下的開源C語言程序:Filemon、BraveFable和 VLC。 Filemon是文件系統(tǒng)監(jiān)視程序，源程序共2個c文件（不包括驅(qū)動程序），程序使用的內(nèi)存大部分是靜態(tài)分配的，源文件中的動態(tài)內(nèi)存分配函數(shù)和釋放函數(shù)較少；BraveFable是小型的ARPG游戲，有42個c文件，程序中頻繁的進行內(nèi)存分配和釋放，但是大部分分配函數(shù)和釋放函數(shù)在代碼中的位置相距不遠；VLC是多媒體播放器，共94個c文件，其中的內(nèi)存分配釋放操作較多但不很集中。3個程序編譯后的程序文件（包括可執(zhí)行文件和動態(tài)鏈接庫）大小和在選定的秘密輸入下運行時間如表2所示。實驗中分簇方式選擇按時間劃分方式。

表2 實驗用到的3個程序的文件大小和運行時間(實驗環(huán)境:Pentium(R) 4 CPU 2.40GHz 1G RAM WinXp)

4.1 平臺依賴性

軟件水印的隱藏是通過修改C或C++等高級語言編寫的源代碼實現(xiàn)的，而源代碼最終通過編譯器編譯成本地代碼程序，軟件水印嵌入和提取過程不需要考慮具體的 CPU和其他硬件，因此算法實現(xiàn)不依賴于特定的硬件環(huán)境。

C或C++等語言編寫的程序中內(nèi)存操作最終仍然是使用操作系統(tǒng)提供的內(nèi)存管理接口實現(xiàn)的，同時很多高級語言編寫的程序在實現(xiàn)內(nèi)存操作時常常也不使用編程語言提供的標準庫函數(shù)或關(guān)鍵字，而是直接調(diào)用了操作系統(tǒng)提供的編程接口。在不同的操作系統(tǒng)中，內(nèi)存管理使用的編程接口并不盡相同。此時算法在收集內(nèi)存塊信息時需要相應的根據(jù)操作系統(tǒng)平臺的不同攔截不同的內(nèi)存函數(shù)。除此之外，修改源代碼時也要和源代碼原用的內(nèi)存操作方式保持一致。

在軟件水印算法實現(xiàn)過程中使用的IDA Pro軟件在Windows和Linux下都有對應的版本，而且這些版本提供的功能差別不大，同時Python本身具有跨平臺運行的能力，從而本文算法能夠以較小的代價在不同的操作系統(tǒng)間進行移植。

4.2 可信性和數(shù)據(jù)率

本文給出的軟件水印算法中的軟件水印是以二值圖像的形式給出的，而圖像具有一定的視覺冗余，即使軟件水印被部分篡改仍可以正確識別。同時由于軟件水印圖像置亂后遍布在載體程序的內(nèi)存關(guān)系中，很難被全部破壞。下文中抗攻擊分析也說明破壞軟件水印使它無法識別是非常困難的，因此算法有著較高的可信性。

從算法的具體實現(xiàn)過程可知，一個程序能嵌入的軟件水印數(shù)據(jù)量取決于分簇的數(shù)量，n簇可以嵌入n2bit數(shù)據(jù)，平均每簇可以嵌入nbit軟件水印數(shù)據(jù)，顯然分簇數(shù)量越多越有效率。然而程序中已有的內(nèi)存分配釋放函數(shù)總數(shù)固定的情況下，分簇過多必然導致需要在程序中插入更多內(nèi)存相關(guān)代碼，這會導致文件大小增加。分簇需要在對程序中的原有內(nèi)存關(guān)系的個數(shù)與分布進行分析的基礎(chǔ)上確定最優(yōu)分簇個數(shù)。

4.3 隱蔽性和開銷

內(nèi)存申請、釋放和讀寫是程序中常見的操作，適度的添加這些內(nèi)存操作并不會引起用戶懷疑，并且算法嵌入過程中增加分配的內(nèi)存大部分會得到使用，不存在明顯的異常特征。只有當較小的程序嵌入較大的軟件水印時，增加的代碼過多才容易被覺察。而軟件保護的對象通常具有較高的應用價值，相對比較復雜，程序體積一般較大，因此本軟件水印算法有著較好的隱蔽性。

圖2給出了嵌入不同大小的軟件水印后對載體程序大小的影響，圖3給出了嵌入不同大小的軟件水印后對程序運行時間的影響。嵌入不同大小的軟件水印前后程序大小和時間增加部分所占的百分比，由下式給出

其中，P和PW分別表示嵌入軟件水印前后的程序，M在圖2和圖3中分別表示程序大小的度量和在給定輸入下程序的運行時間的度量。

圖2 軟件水印對程序大小的影響

圖3 軟件水印對程序運行時間的影響

由圖2可以看出，程序能嵌入的最佳軟件水印大小取決于載體程序自身的性質(zhì)。當嵌入的軟件水印較大時，會增大程序文件的大小。其中，F(xiàn)ileMon程序文件大小的增長較快是由于需要添加的內(nèi)存分配釋放代碼較多造成的，而對于BraveFable程序，在嵌入的軟件水印較小時程序文件大小的增長不顯著，當嵌入的軟件水印較大時，程序大小增長明顯加快。VLC程序由于自身的內(nèi)存操作足夠多，較少需要增加太多的額外代碼，因而文件大小變化最小。

圖3可以看出，程序的運行時間隨嵌入的數(shù)據(jù)變化而變化。由于實驗中使用的輸入和軟件水印算法中用到的秘密輸入相同，因此嵌入的數(shù)據(jù)增多時，增加的內(nèi)存操作代碼較多并參與執(zhí)行，因此會造成時間上的延遲。然而相對于全部運行時間，這點延遲對程序運行的影響不大。實驗中的BravelFable程序中存在大量的循環(huán)，加入的內(nèi)存讀寫代碼有一部分落在循環(huán)中，這導致了圖3中BraveFable的時間變化比例偏高。由于這些代碼只在特定輸入下才會全部運行，對于采用其他輸入的情況下，插入的代碼執(zhí)行的機率不大，載體程序的運行時間幾乎沒有影響。

算法的實現(xiàn)過程中由于對于每個分配的內(nèi)存塊，都要分配一塊同樣大小的影子內(nèi)存塊備份其內(nèi)容，對內(nèi)存的消耗偏多。同時在軟件水印嵌入時需要開發(fā)者參與修改源代碼，因此整個算法實現(xiàn)過程中的開銷比其他可以自動完成的算法稍高。然而相對于開發(fā)者開發(fā)程序的長周期來比較，修改程序嵌入軟件水印的時間代價較小，在開發(fā)者可以接受的范圍內(nèi)。

4.4 抗攻擊能力

攻擊者往往使用一些攻擊手段使得軟件水印難以識別，軟件水印算法必須能提供一定的抗攻擊能力。由于攻擊者所掌握的是已嵌入軟件水印的本地代碼程序，在軟件大小日益膨脹的今天，攻擊者很難對程序完整的進行反匯編加以分析，因此對程序的全部實現(xiàn)細節(jié)了解程度不如開發(fā)者。此時攻擊者可以利用現(xiàn)成的工具進行常規(guī)攻擊，或者根據(jù)自己對程序的理解修改反匯編后的程序然后編譯得到攻擊后的程序。下面結(jié)合實驗給出了不同攻擊方式下的評價結(jié)果，實驗中的軟件水印選擇40×40的二值圖像，軟件水印載體選擇 VLC程序，分簇采用按時間劃分方式。

1) 常規(guī)攻擊

針對本地代碼的常規(guī)攻擊有代碼優(yōu)化、代碼變形、壓縮加密等方式。代碼優(yōu)化一般通過反編譯—編譯的方式利用編譯器對代碼進行優(yōu)化。代碼變形利用等價代碼替換的方式改變代碼特征。壓縮加密通常事先對原始程序壓縮或加密，程序執(zhí)行后使用一小段解壓縮和解密程序還原程序然后轉(zhuǎn)到真正的程序入口執(zhí)行。這些攻擊前后的程序?qū)τ谙嗤妮斎胼敵霰３植蛔?，即這些攻擊為語義保持變換攻擊。

對于代碼優(yōu)化，由于本文給出的軟件水印算法中，插入的代碼全部執(zhí)行，而且這些代碼都是必須的，不存在明顯冗余之處，代碼優(yōu)化過程不會導致含軟件水印程序大小劇烈變化，因此對分簇的影響不大，不會危及軟件水印的安全性。對于代碼變形攻擊，攻擊過程中改變的只是代碼的形狀，程序執(zhí)行中的實際功能未發(fā)生變化，同樣不會對簇間內(nèi)存關(guān)系造成影響。而壓縮或解密殼一般會在程序的開始部分完成解壓縮或解密操作。當?shù)谝粋€簇足夠大時或秘密輸入控制的程序執(zhí)行時間足夠長時，這些攻擊的影響會限制在前幾個簇內(nèi)，而不會對其他部分造成過多影響。

圖4給出了這幾種常規(guī)攻擊下的實驗結(jié)果。圖4(a)左側(cè)為原始軟件水印圖像，然后從左到右依次是對含軟件水印的程序用IDA Pro反編譯后分別使用TASM、MASM和NASM編譯后提取的軟件水印圖像。圖4(b)左側(cè)為原始圖像，然后依次是對含軟件水印的程序分別用 UPX 2.02、Aspack 2.12、ASProtect 1.35[16]等壓縮加密殼保護后提取的軟件水印圖像，這些殼或多或少帶有代碼變形功能?？梢钥闯龀Ｒ?guī)攻擊不影響軟件水印的正確識別?；旌鲜褂蒙鲜龀Ｒ?guī)攻擊，在加殼操作不超過3次的情況下，統(tǒng)計發(fā)現(xiàn)攻擊前后軟件水印圖像被修改的像素數(shù)依然不超過總像素數(shù)的1%。

圖4 常規(guī)攻擊對軟件水印提取的影響

2) 針對簇間內(nèi)存關(guān)系的攻擊

有效地攻擊應該是針對簇間的內(nèi)存關(guān)系進行攻擊，最直觀的方式是插入冗余代碼使得分簇不正確，對于按空間分簇方式，需要插入大量的冗余代碼，這會使得程序體積劇烈膨脹。對于按時間分簇方式，可以插入延時函數(shù)或循環(huán)代碼，由于算法選擇的秘密輸入控制下程序運行時間較長，插入的代碼也需要達到較長的延時才能分簇產(chǎn)生影響，由于攻擊者不知道算法選擇的秘密輸入，所以插入的代碼必然嚴重影響用戶使用感受，容易引起懷疑而加以去除。而在按輸入分簇的情況下攻擊對分簇基本沒有影響。在無法有效影響分簇的情況下，攻擊方式有成對添加內(nèi)存分配和釋放代碼、更改分配內(nèi)存數(shù)量、隨機修改內(nèi)存等。

① 添加內(nèi)存分配釋放代碼

在插入分配內(nèi)存的代碼后，緊接著插入內(nèi)存釋放代碼和在距離內(nèi)存分配代碼最遠距離處（不會產(chǎn)生內(nèi)存問題的前提下）插入內(nèi)存釋放代碼2種情況下的實驗結(jié)果如圖5(a)和圖5(b)所示。圖中最左圖為原圖，從左到右依次是40%、70%、100%的簇中隨機添加內(nèi)存分配函數(shù)和對應的釋放函數(shù)后的實驗結(jié)果。如圖5(a)所示，當添加的分配和釋放代碼相距較近時，分簇的時候有非常大的概率將它們劃分在同一簇或相鄰簇內(nèi)，此時對應的是內(nèi)存關(guān)系矩陣中的少量元素被修改，提取的軟件水印圖像基本不發(fā)生變化，因此對軟件水印的正確識別影響輕微。圖5(b)中采用的攻擊方式對程序的危害較大。然而對攻擊者來說，在對程序的細節(jié)不清楚的情況下，若添加的內(nèi)存分配和釋放代碼如果相隔太遠，在不同的輸入下分配的內(nèi)存能否得到釋放很難明確判斷，容易導致內(nèi)存泄漏或其他內(nèi)存問題。因此圖5(b)中的攻擊方式不容易在實際情況下應用。

圖5 不同強度下針對內(nèi)存關(guān)系的攻擊對提取的影響

② 更改分配內(nèi)存數(shù)量

改變每次分配的內(nèi)存數(shù)量，是較容易實現(xiàn)的攻擊方式，對應的是內(nèi)存分配矩陣發(fā)生改變。圖5(c)給出了對代碼中的每一處內(nèi)存分配數(shù)量增加一個隨機值時的實驗結(jié)果，圖5(c)最左邊是軟件水印原圖，然后從左到右依次是40%、70%、100%的內(nèi)存分配函數(shù)中分配的內(nèi)存數(shù)量改變后提取的軟件水印圖像?？梢钥闯鏊惴ㄖ惺褂玫牧炕夹g(shù)對這種攻擊有著良好的抵抗能力。

③ 隨機修改內(nèi)存

在不清楚一塊內(nèi)存是否還會使用之前就寫入是危險的事情。為了不對程序的正確性造成損害，可以采用2種方式寫入。第一種方式是在修改內(nèi)存數(shù)據(jù)后緊接著還原內(nèi)存數(shù)據(jù)，此時改動發(fā)生在同一個簇內(nèi)，顯然對整個軟件水印沒有影響。第二種方式是先為要寫入的內(nèi)存分配一段內(nèi)存，接著在分配的額外內(nèi)存中進行寫入。這種方式實際上是添加內(nèi)存分配釋放代碼和隨機修改內(nèi)存兩種攻擊的結(jié)合，其缺陷和前面分析類似，若代碼過于集中，它對整個軟件水印的影響輕微，若代碼過于分散，由于不完全清楚程序在不同輸入下的執(zhí)行細節(jié)，則難以保證內(nèi)存一定能得到釋放，并且在輸入不確定的情況下分配的內(nèi)存在修改的時候是否已釋放并重分配不能明確判斷，存在內(nèi)存溢出的風險。

4.5 和同類算法的比較

從上述分析可以看出，本文提出的算法能夠充分利用程序中已有的代碼，不會增加大量代碼，對載體程序的影響較小，并提供了較強的抗攻擊能力。

和動態(tài)路徑算法和混沌軟件水印算法相比，在隱蔽性方面，動態(tài)路徑算法大量重復性的調(diào)用同一個函數(shù)，因此可以通過簡單的靜態(tài)分析就可以定位并加以攻擊?；煦缢∷惴ǜ窃谳d體程序中加入了輸入監(jiān)控模塊、水印解碼模塊等大量特征鮮明的代碼，顯著增大了載體程序文件大小，延長了程序執(zhí)行時間，而本文給出的算法實現(xiàn)中增加或修改的代碼和原始軟件中的代碼之間不存在明顯區(qū)別，在不知道原始程序的情況下，很難定位代碼的改動位置，具有更好的隱蔽性。在抗攻擊能力方面，動態(tài)路徑算法由于內(nèi)置了修改檢測功能從而具有較強的抗攻擊能力，然而算法中用到的函數(shù)可以被替換從而繞開防護機制，文獻[15]就提出了一種低成本的攻擊方式對嵌入的軟件水印進行修改替換?；煦缢∷惴ㄖ型ㄟ^反逆向工程模塊來保證軟件水印免受逆向工程攻擊，然而不存在任何一種方法完美抵抗逆向工程。使用逆向工程方法只需要在載體程序代碼恢復時轉(zhuǎn)儲程序，即可完全繞過混沌水印算法中所施加的所有保護。而本文給出的算法由于良好的隱蔽性，逆向工程攻擊難以發(fā)現(xiàn)需要攻擊的內(nèi)容。本文算法不僅可以抵抗軟件傳輸過程中會遇到的各種常規(guī)變換，即使使用的內(nèi)存操作被修改時仍然能夠較好的識別軟件水印。

比較可以看出，其他面向本地代碼的軟件水印算法多是從代碼不可篡改的角度入手來保證軟件水印的安全，這種做法一方面難度較大，另一方面導致軟件水印的隱蔽性變的更差，更容易引起攻擊者懷疑。而本文給出的算法不使用額外的代碼防篡改措施，只通過使用載體程序自身存在的約束來保證軟件水印的安全，同時保證了軟件水印的隱蔽性而不容易受到攻擊者的注意，進一步增強了軟件水印的安全。

5 結(jié)束語

本文提出了一種新的基于內(nèi)存操作的軟件水印算法，給出軟件水印的嵌入算法和提取算法的詳細過程。實驗表明，本文提出的利用程序中的內(nèi)存操作嵌入軟件水印的算法除了隱蔽性好，對各種攻擊有著較好的抵抗能力之外，而且實現(xiàn)簡單，對原程序的影響較小。目前給出的算法仍需要改進，如內(nèi)存關(guān)系信息難以用矩陣全部表示，而且矩陣本身的表示效率不夠高，對這些問題的進一步的研究將是以后工作的一個方向。

[1]http://portal.bsa.org/globalpiracy2011/index.html[EB/OL].2012.

[2]COLLBERG C, THOMBORSON C.Software watermarking:models and dynamic embedding[A].Proceedings of Symposium on Principles of Programming Languages[C].New York, USA, 1999.311-324.

[3]張立和, 楊義先, 鈕心忻等.軟件水印綜述[J].軟件學報, 2003,14(2):268-277.ZHANG L H, YANG Y X, NIU X X, et al.A survey on software watermarking[J].Journal of Software, 2003, 14(2):268-277.

[4]COLLBERG C, THOMBORSON C, TOWNSEND G.Dynamic graph-based software fingerprinting[J].ACM Transactions on Programming Languages and Systems, 2007, 29(6):35-67.

[5]KAMELA I, ALBLUWIB Q.A robust software watermarking for copyright protection[J].Computers & Security, 2009,28(6):395-409.

[6]CHEN X J, FANG D Y, SHEN J B.A dynamic graph watermark scheme of tamper resistance[A].Proceedings of 5th International Conference on Information Assurance and Security[C].Xi'an, China, 2009.3-6.

[7]COLLBERG C, CARTER E.Dynamic path-based software watermarking[A].Proceedings of the ACM Conference on Programming Language Design and Implementation[C].Washington, CD, USA, 2004.107-118.

[8]LARKIN A J, BALADO F, HURLEY N J.Dither modulation watermarking of dynamic memory traces[A].Proceedings of Information Hiding[C].Berlin, Germany, 2005.372-386.

[9]GUPTA G, PIEPRZYK J.Source code watermarking based on function dependency oriented sequencing[A].Proceedings of the International Conference on Intelligent Information Hiding and Multimedia Signal Processing[C].Harbin, China, 2008.965-968.

[10]NAGRA J, THOMBORSON C.Threading software watermarks[A].Proceedings of 6th International Workshop on Information Hiding[C].Toronto, Canada, 2004, 3200:208-233.

[11]MYLES G, JIN H.Self-validating branch-based software watermarking[A].Proceedings of Information Hiding[C].2005.342-356.

[12]蘆斌,羅向陽,劉粉林.一種基于混沌的軟件水印算法框架及實現(xiàn)[J].軟件學報, 2007, 18(2):351-360.LU B, LUO X Y, LIU F L.A chaos-based rramework and implementation for software watermarking algorithm[J].Journal of Software,2007, 18(2):351-360.

[13]The IDA Pro Book[M].San Francisco:No Starch Press, 2008.

[14]Gray Hat Python[M].San Francisco:No Starch Press, 2009.

[15]SHI Y Q, JEON B.A low-cost attack on branch-based software watermarking schemes[A].Proceedings of the 5th International Workshop on Digital Watermarking[C].Jeju Island, Korea, 2006.282-293

[16]http://www.pediy.com/tools/packers.htm[EB/OL].2012.