我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:多盈娱乐注册 > 多带图灵机 >

基于通用图灵机模型的病毒判定性定理证明

归档日期:07-03       文本归类:多带图灵机      文章编辑:爱尚语录

  计算机科学2005V01.32No.8(增刊)基于通用图灵机模型的病毒判定性定理证明*) ProofoftheVirus Decidability Theomn B酬onaUniversal Turing MachineModel (国防科技大学计算机学院长沙410073)Ahstraet Asuitableuniversal Turing machinevirusmodelis presented first.Themodel preserves theexcellencesof originalCohenmodeland improves its veracity.On thatbasisthevirus decidability theoremis proved,which showsthemodel’S rationality. Keywm-ds Universal Turingmachine,Evolution,Virus decidability theorem 引言计算机病毒模型对于病毒研究具有十分重要的 意义,它能够解决一些根本性的问题,例如病毒的计 算本质、病毒的工作原理、病毒的可检测性、病毒的 传播条件等等。目前比较有影响的模型包括Cohen 的图灵机模型、Adleman的递归函数模型和Leitold 的RAsPM ABS模型[1 ̄3],它们都是建立在一种成熟的抽象计算模型基础之上,从而可以利用 基础模型对病毒进行理论上的分析。Cohen模型提 出最早,影响最广泛,不过随着时间的推移,也受到 了一些质疑[4’5]。本文借鉴Cohen模型的原有优 点,提出了一种更加贴近实际的通用图灵机病毒模 型,并在此基础上证明了病毒的判定性定理,显示了 该模型的合理性。 2通用图灵机病毒模型 任意描述某种封闭计算过程的程序都可以转换 为图灵机,而任意图灵机都可以用某种编程语言来 实现,因此可将图灵机作为程序的抽象模型;通用图 灵机能够模拟任意图灵机的计算,而计算机能够执 行任意程序,因此可将通用图灵机作为计算机的抽 象模型。正是基于上述认识,为了改进Cohen模型 的不足,Makinen提出了一种通用图灵机病毒模 型[5],但是该模型既缺乏精确的定义,思想上也不够 完善。为此,下面将重新建立一种更加合理的通用 图灵机病毒模型。 定义2.1 基本图灵机可用一个七元组T一 {Q,,r,艿,q。,B,F)来描述,其中:Q是控制器 的有限状态集合;乏是有限输入符号集合,不包括空 格符号B;I、是有限带符号集合,且BP,ECP;艿: Qr啼QPX{I。,R}是转移函数,L和R分别代 表左和右;qoQ是初始状态;B是空格符号;FCQ 是接受状态集合。 定义2.2对于一个图灵机T,它所接受的语 言L(T)一{Ict,。,T在输入(1J下进入接受状 定义2.3对于有限的输入符号集合,集合Sc’是可判定的,当且仅当存在一个对于任何输入 都会停机的图灵机T,使得S—L(T)。 定义2.4通用图灵机是这样一种图灵机,它 以任意图灵机T及其输入的编码组成的有序对 <T,>作为输入,并根据编码模拟T在输入下的 计算过程。 通用图灵机一般采用多带图灵机的结构形式来 进行描述[引,如图1所示。 输入带 工作带 状态带 草稿带 图1通用图灵机为了贴近实际,对后面定义中用到的图灵机和 通用图灵机概念特作以下规定: 1)计算机的内部编码都为二进制,因此可以使 用输入符号集合为{0,1)的图灵机和通用图灵机来 分别模拟程序和计算机。这里规定:本节提到的图 *)基金项目:国家自然科学基金第60373023号资助。篙敬波博士生,研究方向为信息安全;殷建平教授,博士生导师,研究方向为算法设 计与分析、模式识别与人工智能、信息安全等}张波云博士生,研究方向为信息安全。 243灵机和通用图灵机皆以{o,1)为输入符号集合,以 {o,1,B}为带符号集合,其中B为空格符号。由于 符号栩同,只需改动两个图灵机编码中的状态编码, 就可以直接将两个图灵机的编码进行合并,形成~ 个组合图灵机编码。此外由于符号相同,被模拟图 灵机的输人符号串在通用图灵机中无需改变。 2)程序在计算机中执行时,离不开软件平台的 支持。对于一个程序基于某种软件平台执行的情 况,可以用程序图灵机与软件平台图灵机(下面简称 为软件平台)组合的方式来模拟。这里规定:通用图 灵机U若要模拟某个图灵机T的计算,必须同时指 定软件平台S,两者合并为T+S。U在起始阶段, 输入带上包含T+S的编码(T+S>,且(T+S>所处 最左单元为0号单元,带上其它单元编号向右依次 递增。 3)程序在计算机中执行时,可以访问自身的代 码,而病毒也正是利用了这一点来进行自身的进化 和复制。这里规定:通用图灵机U若要模拟某个图 灵机T的计算,输入ct,中包含T在U中的编码 <T)。U在初始化后,工作带上包含,且co所处最 左单元为0号单元,带上其它单元编号向右依次递 Cohen在1984年给出了计算机病毒的经典定义ET]:“计算机病毒是这样一种程序,它可以通过修 改其它程序,使其包含病毒的可能进化了的副本的 方式来传染它们。”两年后在其博士论文中又首次提 出了病毒的图灵机模型[1],以严格的数学形式对病 毒进行了定义。Cohen在其模型中,基于“进化”的 概念,深入揭示了病毒的传染性本质,以及相关的进 化性和依赖性。不过由于他是以任意图灵机来抽象 计算机,以图灵机的任意带符号串来抽象程序,因此 其准确性值得商榷。下面将借鉴Cohen模型的优 点,建立一种新的通用图灵机病毒模型。 定义2.5执行平台P=(U,S),其中U为通 用图灵机,S为软件平台。 通用图灵机的一步执行对应于它的多步转移, 使之恰好可以完成对它所模拟的图灵机的一步转移 的模拟。下面引入一组函数,用来描述某个图灵机 T以为输入在平台P=(U,S)上的模拟计算过 程,其中N为自然数集合,表示U的执行时刻(步 数)或带单元编号,r一{0,1,B),QT为T的状态 编码集合,q0T为T的初始状态编码: 作带上i号单元内容。q:N—QT.q(n)表示执行到第n步时状态带 上的状态编码。 244在开始时刻: q(O)一q0T.定义2.6二进制串v以为输入在平台P一 (U,S)上开始执行,当且仅当: v是某个图灵机T的编码, q(0)一q0T。定义2.7对于通用图灵机U,程序全集UP 一(vI v是某个图灵机T的编码}。 定义2.8对于通用图灵机U,V是一个程序 UP且Vo。定义2.9对于通用图灵机U,程序幂集US UP且V0)。定义2.10对于平台P一(U,S),VUS,v V,v发生进化vo—V,当且仅当j(or以为输入在P上开始执行净3 v7V,3 tt>o,3j’lv|, 使得:y(o,j7)…y(o,j7+l v7 I一1vav7,7(t7,j7)…7 (t7,j’+lv7l-1)一v’。 定义2.11 病毒全集VS一{(P,V)|P一 (U,S)为任意平台,VUS(U的程序幂集),且 VvV,voV}。定义2.12 V是关于平台P的一个病毒集合, 定义2.13v是关于平台P的病毒,当且仅当 这里给出的通用图灵机病毒模型在充分继承了Cohen模型优点的同时,也较好地解决了Cohen模 型的不足。首先,由于计算机与通用图灵机,程序与 图灵机之间可以建立直接的对应关系,因此使用通 用图灵机和图灵机编码来分别描述计算机和程序显 得十分自然。其次,通过执行平台概念的引入,计算 机软、硬件平台对病毒的综合影响得到了体现,使得 该模型更加接近真实情况。相对T-Cohen模型,该 模型在准确性上得到了较大提高。 3病毒判定性定理证明 判定性问题是病毒检测理论中的一个基本问 题,即是否存在这样一种算法,能够正确检测出所有 的病毒。下面将基于上面介绍的通用图灵机病毒模 型,来证明病毒判定性定理。 定理3.1 令VS7一{(P,{<T>})}P一(U, S)为任意平台,(T)为任意图灵机T在U中的编 码,且(P,{<T)))VS),则VS’是不可判定的。 证明:用反证法,假设VS’是可判定的。对于任 意平台P=(U,S),其中U为通用图灵机,S为软件 平台,显然可将P转换为这样一个特殊的通用图灵 机,它不再简单地根据输入的图灵机T的编码模拟 T的执行,而是模拟T和S合并后的组合图灵机T +S的执行。 根据假设,令D为VS’的判定器,则有: 那么可以构造一个新的图灵机M,它将D作为一个子程序来使用,如图2所示。 图2基于判定器D构造的图灵机M按照D的定义,若令T=M,可以得到: 从上式可知,若(P,((M>))硭VS’,则可推出M((P.M))=(M),但是根据前面的病毒定义,却应 有(P,{(M)})VS’,这时显然产生了矛盾,因此假 设不成立,定理得证。 定理3.2病毒全集VS={(P,V)I S)为任意平台,VUS(U的程序幂集),且VvV,v—ov)是不可判定的。 证明:用反证法,假设VS是可判定的。 根据假设,令D为VS的判定器,则有: f接受,如果(p,v)VS’uo‘p’v’)5 1拒绝,如果(p,v)旺vs, 那么可以构造一个新的判定器M,它将D作为 一个子程序来使用,如图3所示。 显然M可作为VS7的判定器,与定理3.1相矛 盾,因此假设不成立,定理得证。 …、.广——]接受。 接受。 L—_J拒绝7拒绝7 图3基于判定器D构造的判定器M结束语对于计算机病毒,人们长期以来…直 存在不同的理解和认识,而缺乏完善的病毒模型正 是其中一个重要原因。虽然目前已有几种不错的病 毒模型,不过其自身一般还存在值得推敲的地方,另 外由于病毒技术的日新月异,迫切需要建立能适应 现时情况的病毒模型。本文给出的图灵机病毒模型 可以体现病毒最为核心的传染性,以及相关的进化 性和依赖性,但是还不足以包含交互性和移动性等 其它重要特性。不过随着图灵机理论的发展,更全 面的病毒模型的建立逐渐成为可能,我们将在这方 面展开进一步的研究。 参考文献 AnderssonK.Turing machinesand undecidability specialfocuson computerviruses:[TechnicalReport].Karlstad Uni— versity,Sweden,2003 AdlemanI。MAnabstracttheory computervirusesIn:Ad— VaPC!eSin Cryptology—CRYPTO’88,S.Go|dwasser ed.1N(二s 403,Springer-Verhg,Berlin,1990.354~374 l。eitoldF.Mathernaticalmodelofcomputer viruses.In:EI(:AR 2000Best Paper ProcBrussels,2000。194~217 ThimblebyH,AndersonS,CairnsP.Aframeworkformodel— ingTroians computervirusinfection.The ComputerJour— rlaI,1998,41(7):444~458 5她kinenE.CommentOn’aframeworkfor modelingtroians computervirusinfection’.The ComputerJoumal,2001,44(4): 32l~323 HoperoftJE,MotwaniR,UllmanJ13.IntroductiontOAutoma~ ta Theory.Languages,andComputation Second Edition,Ad_ dison-Wesley,2001 CohenF.Computerviruses—theory experiments。In:Pf()c.ofthe2ndIFIPIntl.Conf.on ComputerSecurity,Toronto, C“lDda,1984

本文链接:http://cakesbyrita.net/duodaitulingji/753.html