計(jì)算機(jī)病毒及其防范技術(shù)（第2版）第2章 計(jì)算機(jī)病毒理論模型

計(jì)算機(jī)病毒理論模型 劉功申 上海交通大學(xué)信息安全工程學(xué)院 信息安全工程學(xué)院 本章學(xué)習(xí)目標(biāo) 掌握計(jì)算機(jī)病毒的抽象描述 掌握基于圖靈機(jī)的計(jì)算機(jī)病毒模型 掌握基于遞歸函數(shù)的計(jì)算機(jī)病毒模型 掌握網(wǎng)絡(luò)蠕蟲傳播模型 掌握計(jì)算機(jī)病毒預(yù)防理論模型 信息安全工程學(xué)院 虛擬案例 一個(gè)文本編輯程序被病毒感染了。每當(dāng)使用文本編輯程序時(shí)，它總是先進(jìn)行感染工作并執(zhí)行編輯任務(wù)，其間，它將搜索合適文件以進(jìn)行感染。每一個(gè)新被感染的程序都將執(zhí)行原有的任務(wù)，并且也搜索合適的程序進(jìn)行感染。這種過程反復(fù)進(jìn)行。當(dāng)這些被感染的程序跨系統(tǒng)傳播，被銷售，或者送給其他人時(shí)，將產(chǎn)生病毒擴(kuò)散的新機(jī)會(huì)。最終，在 1990年 1月 1日以后，被感染的程序終止了先前的活動(dòng)?，F(xiàn)在，每當(dāng)這樣的一個(gè)程序執(zhí)行時(shí)，它將刪除所有文件。 信息安全工程學(xué)院 計(jì)算機(jī)病毒偽代碼 If is to be If 信息安全工程學(xué)院 案例病毒的偽代碼 If 1,1990 = 0 信息安全工程學(xué)院 If to 信息安全工程學(xué)院 精簡(jiǎn)后的偽代碼 (壓縮或變型 ) of If 信息安全工程學(xué)院 If = 0 to 信息安全工程學(xué)院 病毒偽代碼的共同性質(zhì) 1對(duì)于每個(gè)程序，都存在該程序相應(yīng)的感染形式。也就是，可以把病毒看作是一個(gè)程序到一個(gè)被感染程序的映射。 2每一個(gè)被感染程序在每個(gè)輸入（輸入是指可訪問信息，例如，用戶輸入，系統(tǒng)時(shí)鐘，數(shù)據(jù)或程序文件等）上形成如下 3個(gè)選擇： 信息安全工程學(xué)院 破壞 (不執(zhí)行原先的功能，而去完成其它功能。何種輸入導(dǎo)致破壞以及破壞的形式都與被感染的程序無關(guān)，而只與病毒本身有關(guān)。 傳染 (執(zhí)行原先的功能，并且，如果程序能終止，則傳染程序。對(duì)于除程序以外的其它可訪問信息（如時(shí)鐘、用戶 /程序間的通信）的處理，同感染前的原程序一樣。另外，不管被感染的程序其原先功能如何（文本編輯或編譯器等），它傳染其它程序時(shí)，其結(jié)果是一樣的。也就是說，一個(gè)程序被感染的形式與感染它的程序無關(guān)。 模仿 (既不破壞也不傳染，不加修改地執(zhí)行原先的功能。這也可看作是傳染的一個(gè)特例，其中被傳染的程序的個(gè)數(shù)為零。 信息安全工程學(xué)院 基于圖靈機(jī)的計(jì)算機(jī)病毒的計(jì)算模型 基本圖靈機(jī) (圖靈機(jī)的經(jīng)典問題： 圖靈機(jī)停機(jī)問題 圖靈機(jī)存在不可計(jì)算數(shù) 1a 2a ia 控 制 器信息安全工程學(xué)院 隨機(jī)訪問計(jì)算機(jī)（ 1x 2x 單 元程 序 ( 不 能夠 存 儲(chǔ) 在存 儲(chǔ) 器 中 )0 帶存 儲(chǔ) 器輸 出 帶信息安全工程學(xué)院 隨機(jī)訪問存儲(chǔ)程序計(jì)算機(jī)（ 1x 2x 單 元程 序 ( 能 夠存 儲(chǔ) 在 存儲(chǔ) 器 中 )0 帶存 儲(chǔ) 器輸 出 帶信息安全工程學(xué)院 包含后臺(tái)存儲(chǔ)帶的隨機(jī)訪問存儲(chǔ)程序計(jì)算機(jī)( 輸 入 帶輸 入 帶2x r 0 單 元程 序 ( 能 夠存 儲(chǔ) 在 存儲(chǔ) 器 中 )存 儲(chǔ) 器后 臺(tái) 存 儲(chǔ) 器信息安全工程學(xué)院 基于 計(jì)算機(jī)病毒被定義成程序的一部分，該程序附著在某個(gè)程序上并能將自身鏈接到其他程序上。當(dāng)病毒所附著的程序被執(zhí)行時(shí)，計(jì)算機(jī)病毒的代碼也跟著被執(zhí)行。 信息安全工程學(xué)院 如果病毒利用了計(jì)算機(jī)的一些典型特征或服務(wù)，那么病毒的這種傳播方式被稱作專用計(jì)算機(jī)的傳播方式。如果病毒在傳播時(shí)沒有利用計(jì)算機(jī)的服務(wù)，那么此傳播方式被稱為獨(dú)立于計(jì)算機(jī)的傳播方式。 導(dǎo)型病毒就具有專用計(jì)算機(jī)的傳播方式 感染 信息安全工程學(xué)院 當(dāng)有兩個(gè)程序被同樣的病毒以指定傳播方式感染，并且病毒程序的代碼順序不同時(shí)，這種傳播方式稱為少形態(tài)的。 當(dāng)有兩個(gè)程序被同樣的病毒以指定傳播方式感染，并且病毒程序的代碼順相同但至少有一部分病毒代碼被使用不同的密鑰加密時(shí)，這種傳播方式稱為多形態(tài)的。 信息安全工程學(xué)院 多態(tài)型病毒的實(shí)現(xiàn)要比少態(tài)型病毒的實(shí)現(xiàn)復(fù)雜得多，它們能改變自身的譯碼部分。例如，通過從準(zhǔn)備好的集合中任意選取譯碼程序。該方法也能通過在傳播期間隨即產(chǎn)生程序指令來完成。例如，可以通過如下的方法來實(shí)現(xiàn)： 改變譯碼程序的順序； 處理器能夠通過一個(gè)以上的指令（序列）來執(zhí)行同樣的操作； 向譯碼程序中隨機(jī)地放入啞命令（ 信息安全工程學(xué)院 如果存在著某一能夠解決病毒檢測(cè)問題的算法，那么就能通過建立圖靈機(jī)來執(zhí)行相應(yīng)的算法。不幸的是，即使在最簡(jiǎn)單的情況下，我們也不可能制造出這樣的圖靈機(jī)。 定理：不可能制造出一個(gè)圖靈機(jī)，利用該計(jì)算機(jī)，我們能夠判斷 信息安全工程學(xué)院 如果我們只涉及一些已知病毒的問題，那么就可能簡(jiǎn)化病毒檢測(cè)問題。在此情況下，可以將已知病毒用在檢測(cè)算法上。 我們從每個(gè)已知病毒提取一系列代碼，當(dāng)病毒進(jìn)行傳播時(shí)，它們就會(huì)在每個(gè)被感染了的文件中顯示出來。我們將這一系列代碼成為序列。病毒檢測(cè)程序的任務(wù)就是在程序中搜尋這些序列。 信息安全工程學(xué)院 檢測(cè)多態(tài)型病毒的難點(diǎn) 不能確定多態(tài)型病毒是否含有某些序列，能夠通過這些序列可以檢測(cè)病毒的所有變異。 當(dāng)發(fā)現(xiàn)序列是隨機(jī)的時(shí)，不知道發(fā)生錯(cuò)誤報(bào)警的概率。發(fā)現(xiàn)任意序列的概率： L(LN)表示被檢測(cè)文件的總長(zhǎng)度； 應(yīng)二進(jìn)制為 16） 該采用什么樣的費(fèi)用標(biāo)準(zhǔn)來衡量序列搜尋算法的實(shí)現(xiàn)。 1 M n 信息安全工程學(xué)院 基于遞歸函數(shù)的計(jì)算機(jī)病毒的數(shù)學(xué)模型 （ 1） （ 2） 的可計(jì)算的入射函數(shù)，它具有可計(jì)算的逆函數(shù)。 （ 3）對(duì)所有的 s,t S,用 表示 e（ s,t）。 （ 4）對(duì)所有部分函數(shù) f： Ns,t S,用 f(s,t)表示f()。 （ 5） e表示一個(gè)從 N 的可計(jì)算的入射函數(shù)，它具有可計(jì)算的逆函數(shù)，并且對(duì)所有 i,j N， e(i,j)i。 信息安全工程學(xué)院 （ 6）對(duì)所有 i,j N， 表示 e(i,j)。 （ 7）對(duì)所有部分函數(shù) f： Ni,j N,f(i,j)表示 f()。 （ 8）對(duì)所有部分函數(shù) f： Nn N,f(n)表示 f(n)是有定義的。 （ 9）對(duì)所有部分函數(shù) f： Nn N,f(n)表示 f(n)是未定義的。 信息安全工程學(xué)院 計(jì)算機(jī)病毒的面太廣。 不具傳染性的也當(dāng)作病毒 定義并沒有反映出病毒的傳染特性。 定義不能體現(xiàn)出病毒傳染的傳遞特性。 “破壞”的定義不合適。 原程序功能保留不明確 信息安全工程學(xué)院 受感染的 信息安全工程學(xué)院 某種群中不存在流行病時(shí)，其種群（ N）的生長(zhǎng)服從微分系統(tǒng)。 其中 表示 表示種群中單位個(gè)體的生育率， NN b e N d N ()N N t信息安全工程學(xué)院 有疾病傳播時(shí)的模型 S， 表示一個(gè)染病者所具有的最大傳染力 S d a I信息安全工程學(xué)院 流行病的傳播服從雙線形傳染率的 總種群的生長(zhǎng)為： ()NS b e N S I d S r I d a r I NN b e N d N I ( ) ( ) ( )N t S t I t在 a=0時(shí)，該模型變?yōu)?信息安全工程學(xué)院 兩個(gè)假設(shè)： 已被病毒感染的文件（檔）具有免疫力。 病毒的潛伏期很短，近似地認(rèn)為等于零。 把系統(tǒng)中可執(zhí)行程序分為三種： 被傳播對(duì)象 ，即尚未感染病毒的可執(zhí)行程序，用S(t)表示其數(shù)目。 帶菌者 ，即已感染病毒的可執(zhí)行程序，用 p(t)表示其數(shù)目。 被感染后具有免疫力的可執(zhí)行程序 ，也包括被傳播后在一定時(shí)間內(nèi)不會(huì)運(yùn)行的可執(zhí)行程序（相當(dāng)患病者死去），用 R(t)表示其數(shù)目。 信息安全工程學(xué)院 表示傳播（感染）速度； 表示每個(gè)時(shí)間段接觸次數(shù)；表示第 類程序變成第 類程序的速度； 公式的解釋： S(t)的變化率即經(jīng)第 類程序變成第 類程序的變化率，它與傳染者和被傳染者之間的接觸次數(shù)有關(guān)，并且正比于這兩類文件的乘積。 R(t)的變化率即第 類程序變成第 類程序的變化率，與當(dāng)時(shí)第 類的可執(zhí)行程序數(shù)目成正比。 在考慮的時(shí)間間隔內(nèi)，系統(tǒng)內(nèi)可執(zhí)行程序的總數(shù)變化不大，并且假設(shè)它恒等于常數(shù)（即沒有文件被撤消，也沒有外面的新文件進(jìn)來），從而可執(zhí)行程序總數(shù)的變化率為零。 p ( ) ( ) ( )S t t R t N d d S d Rd t d t d t 信息安全工程學(xué)院 預(yù)防理論模型 模型”理論 (1) 基本隔離模型 該模型的主要思想是取消信息共享，將系統(tǒng)隔離開來，使得計(jì)算機(jī)病毒既不能從外部入侵進(jìn)來，也不可能把系統(tǒng)內(nèi)部的病毒擴(kuò)散出去。 (2) 分隔模型 將用戶群分割為不可能互相傳遞信息的若干封閉子集。由于信息處理流的控制，使得這些子集可被看作是系統(tǒng)被分割成的相互獨(dú)立的子系統(tǒng)，使得計(jì)算機(jī)病毒只能感染整個(gè)系統(tǒng)中的某個(gè)子系統(tǒng)，而不會(huì)在子系統(tǒng)之間進(jìn)行相互傳播。 信息安全工程學(xué)院 (3) 流模型 對(duì)共享的信息流通過的距離設(shè)定一個(gè)閥值，使得一定量的信息處理只能在一定的區(qū)域內(nèi)流動(dòng)，若該信息的使用超過設(shè)定的閥值，則可能存在某種危險(xiǎn)。 (4) 限制解釋模型 即限制兼容，采用固定的解釋模式，就有可能不被計(jì)算機(jī)病毒感染。 信息安全工程學(xué)院 類 把計(jì)算機(jī)程序或磁盤文件類比為不斷生長(zhǎng)變化的植物。 把