計(jì)算機(jī)病毒理論模型

計(jì)算機(jī)病毒理論模型第一頁，共三十一頁，編輯于2023年，星期一本章學(xué)習(xí)目標(biāo)掌握計(jì)算機(jī)病毒的抽象描述掌握基于圖靈機(jī)的計(jì)算機(jī)病毒模型掌握基于遞歸函數(shù)的計(jì)算機(jī)病毒模型掌握網(wǎng)絡(luò)蠕蟲傳播模型掌握計(jì)算機(jī)病毒預(yù)防理論模型第二頁，共三十一頁，編輯于2023年，星期一虛擬案例一個(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í)，它將刪除所有文件。第三頁，共三十一頁，編輯于2023年，星期一計(jì)算機(jī)病毒偽代碼{main:= Callinjure;

… Callsubmain;

… Callinfect;}{injure:= Ifconditionthenwhateverdamageistobedoneandhalt;}{infect:= Ifconditiontheninfectfiles;}第四頁，共三十一頁，編輯于2023年，星期一案例病毒的偽代碼{main:= Callinjure; Callsubmain; Callinfect;}{injure:= Ifdate>=Jan.1,1990then Whilefile!=0 File=get-random-file; Deletefile; Halt;}第五頁，共三十一頁，編輯于2023年，星期一{infect:= Iftruethen File=get-random-executable-file; Renamemainroutinesubmain; Prependselftofile;}第六頁，共三十一頁，編輯于2023年，星期一精簡后的偽代碼{main:= Callinjure; Decompresscompressedpartofprogram; Callsubmain; Callinfect;}{injure:= Iffalsethenhalt;}第七頁，共三十一頁，編輯于2023年，星期一{infect:=Ifexecutable!=0thenFile=get-random-executable-file;Renamemainroutinesubmain;Compressfile;Prependselftofile;

}第八頁，共三十一頁，編輯于2023年，星期一病毒的性質(zhì)1．對(duì)于每個(gè)程序，都存在該程序相應(yīng)的感染形式。也就是，可以把病毒看作是一個(gè)程序到一個(gè)被感染程序的映射。2．每一個(gè)被感染程序在每個(gè)輸入（這里的輸入是指可訪問信息，例如，用戶輸入，系統(tǒng)時(shí)鐘，數(shù)據(jù)或程序文件等）上做形成如下3個(gè)選擇：第九頁，共三十一頁，編輯于2023年，星期一破壞(Injure)：不執(zhí)行原先的功能，而去完成其它功能。何種輸入導(dǎo)致破壞以及破壞的形式都與被感染的程序無關(guān)，而只與病毒本身有關(guān)。傳染(Infect)：執(zhí)行原先的功能，并且，如果程序能終止，則傳染程序。對(duì)于除程序以外的其它可訪問信息（如時(shí)鐘、用戶/程序間的通信）的處理，同感染前的原程序一樣。另外，不管被感染的程序其原先功能如何（文本編輯或編譯器等），它傳染其它程序時(shí)，其結(jié)果是一樣的。也就是說，一個(gè)程序被感染的形式與感染它的程序無關(guān)。模仿(Imitate)：既不破壞也不傳染，不加修改地執(zhí)行原先的功能。這也可看作是傳染的一個(gè)特例，其中被傳染的程序的個(gè)數(shù)為零。第十頁，共三十一頁，編輯于2023年，星期一基于圖靈機(jī)的計(jì)算機(jī)病毒的計(jì)算模型基本圖靈機(jī)(TM)第十一頁，共三十一頁，編輯于2023年，星期一隨機(jī)訪問計(jì)算機(jī)（RandomAccessMachine——RAM）第十二頁，共三十一頁，編輯于2023年，星期一隨機(jī)訪問存儲(chǔ)程序計(jì)算機(jī)（RamdomAccessStoredProgramMachine,RASPM）第十三頁，共三十一頁，編輯于2023年，星期一包含后臺(tái)存儲(chǔ)帶的隨機(jī)訪問存儲(chǔ)程序計(jì)算機(jī)(TheRandomAccessStoredProgramMachinewithAttachedBackgroundStorage,RASPM_ABS)第十四頁，共三十一頁，編輯于2023年，星期一基于RASPM_ABS的病毒計(jì)算機(jī)病毒被定義成程序的一部分，該程序附著在某個(gè)程序上并能將自身鏈接到其他程序上。當(dāng)病毒所附著的程序被執(zhí)行時(shí)，計(jì)算機(jī)病毒的代碼也跟著被執(zhí)行。第十五頁，共三十一頁，編輯于2023年，星期一1.病毒的傳播模型如果病毒利用了計(jì)算機(jī)的一些典型特征或服務(wù)，那么病毒的這種傳播方式被稱作專用計(jì)算機(jī)的傳播方式。如果病毒在傳播時(shí)沒有利用計(jì)算機(jī)的服務(wù)，那么此傳播方式被稱為獨(dú)立于計(jì)算機(jī)的傳播方式。PC中，引導(dǎo)型病毒就具有專用計(jì)算機(jī)的傳播方式感染C源文件的病毒就是具有獨(dú)立計(jì)算機(jī)的傳播方式第十六頁，共三十一頁，編輯于2023年，星期一2.少態(tài)型病毒和多態(tài)型病毒當(dāng)有兩個(gè)程序被同樣的病毒以指定傳播方式感染，并且病毒程序的代碼順序不同時(shí)，這種傳播方式稱為多形態(tài)的。當(dāng)有兩個(gè)程序被同樣的病毒以指定傳播方式感染，并且病毒程序的代碼順相同但至少有一部分病毒代碼被使用不同的密鑰加密時(shí)，這種傳播方式稱為少形態(tài)的。第十七頁，共三十一頁，編輯于2023年，星期一多態(tài)型病毒的實(shí)現(xiàn)要比少態(tài)型病毒的實(shí)現(xiàn)復(fù)雜得多，它們能改變自身的譯碼部分。例如，通過從準(zhǔn)備好的集合中任意選取譯碼程序。該方法也能通過在傳播期間隨即產(chǎn)生程序指令來完成。例如，可以通過如下的方法來實(shí)現(xiàn)：改變譯碼程序的順序；處理器能夠通過一個(gè)以上的指令（序列）來執(zhí)行同樣的操作；向譯碼程序中隨機(jī)地放入啞命令（DummyCommand）。第十八頁，共三十一頁，編輯于2023年，星期一3.病毒檢測(cè)的一般問題如果存在著某一能夠解決病毒檢測(cè)問題的算法，那么就能通過建立圖靈機(jī)來執(zhí)行相應(yīng)的算法。不幸的是，即使在最簡單的情況下，我們也不可能制造出這樣的圖靈機(jī)。定理：不可能制造出一個(gè)圖靈機(jī)，利用該計(jì)算機(jī)，我們能夠判斷RASPM_ABS中的可執(zhí)行文件是否含有病毒。第十九頁，共三十一頁，編輯于2023年，星期一4.病毒檢測(cè)方法如果我們只涉及一些已知病毒的問題，那么就可能簡化病毒檢測(cè)問題。在此情況下，可以將已知病毒用在檢測(cè)算法上。我們從每個(gè)已知病毒提取一系列代碼，當(dāng)病毒進(jìn)行傳播時(shí)，它們就會(huì)在每個(gè)被感染了的文件中顯示出來。我們將這一系列代碼成為序列。病毒檢測(cè)程序的任務(wù)就是在程序中搜尋這些序列。第二十頁，共三十一頁，編輯于2023年，星期一基于遞歸函數(shù)的計(jì)算機(jī)病毒的數(shù)學(xué)模型Adlemen給出的計(jì)算機(jī)病毒形式定義：（1）S表示所有自然數(shù)有窮序列的集合。（2）e表示一個(gè)從S╳S到N的可計(jì)算的入射函數(shù)，它具有可計(jì)算的逆函數(shù)。（3）對(duì)所有的s,t∈S,用<s,t>表示e（s,t）。（4）對(duì)所有部分函數(shù)f：N→N及所有s,t∈S,用f(s,t)表示f(<s,t>)。（5）e′表示一個(gè)從N╳N到N的可計(jì)算的入射函數(shù)，它具有可計(jì)算的逆函數(shù)，并且對(duì)所有i,j∈N，e′(i,j)≥i。第二十一頁，共三十一頁，編輯于2023年，星期一（6）對(duì)所有i,j∈N，<i,j>表示e′(i,j)。（7）對(duì)所有部分函數(shù)f：N→N及所有i,j∈N,f(i,j)表示f(<i,j>)。（8）對(duì)所有部分函數(shù)f：N→N及所有n∈N,f(n)↓表示f(n)是有定義的。（9）對(duì)所有部分函數(shù)f：N→N及所有n∈N,f(n)↑表示f(n)是未定義的。第二十二頁，共三十一頁，編輯于2023年，星期一Adlemen病毒模型有如下缺陷：⑴計(jì)算機(jī)病毒的面太廣。⑵定義并沒有反映出病毒的傳染特性。⑶定義不能體現(xiàn)出病毒傳染的傳遞特性。⑷“破壞”的定義不合適。第二十三頁，共三十一頁，編輯于2023年，星期一Internet蠕蟲傳播模型SI(Susceptible[易受感染的]-Infected)SIS(Susceptible-Infected-Susceptible)SIR(Susceptible-Infected-Removed)第二十四頁，共三十一頁，編輯于2023年，星期一SIS模型和SI模型某種群中不存在流行病時(shí)，其種群（N）的生長服從微分系統(tǒng)。其中表示t時(shí)刻該環(huán)境中總種群的個(gè)體數(shù)量，表示種群中單位個(gè)體的生育率，d表示單位個(gè)體的自然死亡率。

第二十五頁，共三十一頁，編輯于2023年，星期一有疾病傳播時(shí)的模型S，I分別表示易感者類和染病者類β表示一個(gè)染病者所具有的最大傳染力α表示自然死亡率和額外死亡率第二十六頁，共三十一頁，編輯于2023年，星期一流行病的傳播服從雙線形傳染率的SIS模型總種群的生長為：在SIS模型中，當(dāng)r=0時(shí)，該模型變?yōu)镾I模型。第二十七頁，共三十一頁，編輯于2023年，星期一SIR模型兩個(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ù)目。第二十八頁，共三十一頁，編輯于2023年，星期一λ表示傳播（感染）速度；表示每個(gè)時(shí)間段接觸次數(shù)；ｕ表示第Ⅱ類程序變成第Ⅲ類程序的速度；公式的解釋：⑴S(t)的變化率即經(jīng)第Ⅰ類程序變成第Ⅱ類程序的變化率，它與傳染者和被傳染者之間的接觸