基于递归原理的计算机病毒复制模型

基于递归原理的计算机病毒复制模型 1(引言 计算机病毒属于具有危害作用的恶意程序。计算机病毒的传染性是其最为本质的特性。本文首先给出计算机病毒的定义和用伪代码描述的一般结构。然后本文运用可计算理论中的图灵机和通用图灵机理论，在可计算函数、自引用和递归定理等理论工具的基础上，形式化的建立了精确的计算机病毒的自引用计算模型和复制计算模型。从递归定理的角度建立这些模型，有助于我们更加深刻的理解计算机病毒的复制和传播行为的本质，即，在本质上，计算机病毒的复制是一个递归的过程。 2(计算机病毒的定义和结构 本文所讨论的病毒定义为一段程序，该段程序具有如下性质: 1(该段程序寄生于宿主程序中，宿主程序执行时，该段程序首先被执行。即具有寄生性。 2(该段程序能够自我复制到其他宿主程序中，即具有传染性。且被感染的程序运行时，病毒程序能够进一步感染其他目标程序，从而使病毒得到传播。能够进行自我复制，是病毒最为本质的特性。病毒的结构可以用以下伪代码描述: program V := { goto main: 1234567: subroutine infect_executable := { loop: file:=get_random_executable_file; if (first_line_of_file = 12345) goto loop; else prepend V to file; } subroutine do_damage := { whatever damage is to be done; } subroutine trigger_pulled := { return true if some condition holds; } main: main_program := { infect_executable; if reigger_pulled then do_damage; goto next; } next: ... } 本文后面小节将运用通用图灵机模型研究病毒复制机理，建立基于递归原理的病毒复制计算模型。 3(图灵机、可计算函数与通用图灵机 图灵机是1936 年由Alan Turing 提出的自动机模型。在本质上，图灵机是将计算过程抽象化、形式化、理想化后得到的自动机模型。相对于有穷自动机而言，图灵机是更强大、更精确、更一般的计算模型。任何现实的计算机算法经过形式化后，都可以等价为图灵机算法的描述。反之，凡不存在图灵机算法的计算问题，则称该问题是不可判定的，这样的问题在现实计算机也不可能找到相应的算法解。这说明，是否存在图灵机算法，实际上是计算的理论极限，超出这个极限，则问题是不可计算的。 图灵机模型包括一个有穷状态控制器、一个向右无限延长的存储带、一个读写头。读写头能够在带上面读、写和移动。控制器根据当前状态和读写头当前读到的符号，在计算的每步完成两个功能: 1(进入新的状态。若进入接受或拒绝状态，则停机。 2(通过读写头在当前带方格内写一个符号或者使读写头向左或向右移一个方格。 图灵机若不能停机，则将循环往复的运行下去。 图灵机的形式定义 图灵机的形式定义:图灵机是一个7 元组(Q，Σ，Γ，δ，q0， qa ，qr)，其中: Q 为有穷状态集合; Σ是有穷输入字母表集合，不包括空白字符; Γ为有穷带字母表集合，其中，空白字符?Γ，Σ啨, δ为转移函数:Q×Γ?Q×Γ×{ L, R }，其中，L 表示左移，R 表示右移; q0 是起始状态，q0 ? Q; qa 是接受状态，qa ? Q; qr 是拒绝状态，qr ? Q，且qa ? qr。 图灵机的当前状态、当前带内容和读写头当前位置三项构成的整体称作图灵机的格局。 图灵机在进行计算时，总是根据转移函数δ所描述的规则进行，即若机器处于状态q，读写头所在的带方格内包含符号a ，则当δ(q ，a),(r，b，D)时，机器写下符号b 以取代a，并进入状态r，然后读写头按照D 指示的方向移动，这样，图灵机就从一个格局转换到了另外一个格局。一系列这样的转换，最终完成图灵机的计算过程。 可计算函数的形式定义 任何计算过程都可以看作一个函数f，实现输入到输出的变换。图灵机计算也不例外。图灵机的输入可以是任何对象，只要它能通过编码等技术表示成一个串w，例如，多项式、图、文法、自动机、甚至包括图灵机本身。对象O 经编码成串后，记为w,。 称函数f:?*??*是一个可计算函数，如果有某个图灵机M，使得在每个输入w 上，M 停机，且此时只有f(w)出现在带上。 可计算函数可以是机器的描述(算法)之间的变换，例如，如果w,是一个图灵机的编码，可以存在一个可计算函数f，以w 为输入，且返回另一个图灵机的描述。 通用图灵机的定义 通用图灵机U , “对于输入< M，w>，其中M 是一个图灵机的编码，w 是M的输入串: ? 在输入w 上模拟M; ? 如果M 进入接受状态，则接受;如果M 进入拒绝状态，则拒绝。” 由上述定义可以看出，通用图灵机之所以通用，是因为它能够模拟任何其他图灵机，只要能够得到其他图灵机的编码描述。 4(基于递归原理的病毒复制模型 在我们将要建立的模型中，第2 节中的计算机病毒V 将被认为是一个图灵机V，其编码记为。 4.1 计算机病毒的自引用 前面已经提到，能够进行自我复制是计算机病毒最本质的特征。而要进行自我复制首先要能够进行自我引用，即病毒图灵机V 要能够输出自身的描述。为此我们首先建立计算机病毒的自引用模型。 引理1:存在可计算函数q:?*??*，对任意串w，q(w)是图灵机Pw 的描述，Pw 输出w 并停机。 证明:采用构造式证明方法，即构造图灵机Q 实现可计算函数q(w)的计算: “对于输入串w: Q , ? 构造下列图灵机Pw: Pw , “对于任意输入: ? 在带上删除输入; ? 在带上写下w; ? 停机。” ? 输出< Pw >。” 现在我们在引理1 的基础上描述病毒图灵机V 的自引用过程。 首先，将病毒图灵机V 分为两个部分V伜蚔偅 = < V乂>。 根据引理1，令< V> = q(< V>)，即V伿鞘涑< V>的图灵机。这里， V伒拿枋鲆览涤赩偟拿枋觥,耍乖霽偛?枋鋈缦拢 V , “对于输入，其中M 是一个图灵机T 的一部分: ? 计算q(); ? 将?中计算出的结果与合并，组成一个完整的图灵机描述; ? 输出这个描述。” 至此，根据上面的论述，我们可以得到完整的病毒图灵机V的自引用运行过程: 1(首先V佋诵校 V佋诖鲜涑< V>; 2( V偪荚诵校诖险业狡涫淙< V>; 3( V偧扑鉸(< V>) = < V>; V偨< V>与其输入< V>合并，从而得到< V乂> = ; 4( V偸涑，停机。 4.2 计算机病毒的递归复制过程 首先我们给出递归定理: 定理:设T 是计算函数t:?*??*的一个图灵机，则存在计算函数r:?*??*的一个图灵机R，使得对每一个w，有:r(w) = t(，w) 该定理的证明同样可以采用构造式方法，其证明过程请参考文献[2]，这里从略。 递归定理指出任何图灵机T 具有这样的能力:得到自己的描述，然后能用这个描述作为自己的输入继续进行计算。这样的能力显然比引理1 所描述的图灵机的自引用能力更进了一步。 前面我们已经指出，通用图灵机能够模拟任何图灵机的运行。现在，我们结合病毒图灵机V 的运行，给出基于递归定理的病毒复制过程。在以下叙述中，设为将被病毒感染的目标程序的图灵机编码。 1( 通用图灵机U 运行，模拟病毒图灵机V 的运行。(参见第3 节通用图灵机定义) 读取图灵机编码到带上。 2( V 3( V 将一个特殊的符号插入到的起始处。 由递归定理得到自己的描述，并写到带上。 4( V 5( V 跳转到的起始特殊符号处，将病毒编码复制到的起始处。 6( V 将控制返回给的起始状态，并将的头部移到原始带内容的第一个单元。然后停机。 7( V 停机后，通用图灵机U 也停机。 经过以上过程，已经被病毒传染。 通过以上两个小节的描述，我们建立了精确的计算机病毒自引用和基于递归的复制模型。由此我们可以得出结论，计算机病毒的复制和传播在本质上是一个递归的过程。 5. 小结 本文首先给出了计算机病毒非形式定义、病毒结构的伪代码描述。然后运用图灵机、通用图灵机和可计算函数理论，形式化的建立了基于递归定理的计算机病毒的自引用和复制的计算模型。从而精确的体现了计算机病毒的本质特性——自我复制性和传染过程，并指出这一过程在本质上是一个递归的过程。 本文只对单机上的病毒复制过程进行了研究。下一步，我们还将对网络与分布式环境下的病毒传播和复制行为进行研究，建立精确的计算模型，从而为反病毒软件的研制奠定可靠的理论基础。 参考文献 1( Fred Cohen. Computer virus theory and experiments. Computer & Security，1987，6. 2( Michael Sipser. Introduction to the Theory of Computation(影印版). 北京:机械 工业出版社，2004. 3( Erkki M觡inen Comment on ‘A Framework for Modelling Trojans and Computer Virus Infection ’ .Computer Journal，2001，44.