（计算机软件与理论专业论文）基于dcsp的敌意规划识别方法.pdf

摘要 智能规划与规划识别是人工智能研究领域中一个很重要的方向。规划识别是 指规划识别器根据观察到的智能体( 一个或多个) 的片断的、琐碎的动作，推导 出智能体将要执行的动作和欲实现的目标，即推导出智能体正在执行的规划。 敌意规划作为智能规划研究的一个重要分支，目前还只停留在游戏策略研究 方面。其在国际上也只是处于初步研究阶段，在国内对于该领域的研究和规划识 别器的开发也还仅处于起步阶段。 本文首先介绍了敌意动作，敌意规划和危机系数等基本概念；随后对敌意规 划库，敌意知识库和敌意推理机进行了研究，提出了一种新的规划识别方法一 基于d c s p 的规划识别算法。在敌对领域中，智能体只有充分、正确地识别敌方 规划才能有效地制定己方规划，因此规划识别方法的运用是否得当直接决定了智 能体的策略性。传统的规划识别方法存在着诸多的局限性，限制了其在敌对领域 中的应用。本文在给出动态已观察动作集，动态动作悬挂集和动态可能规划集的 基础上，结合d c s p 理论，给出了一种更适用于敌对领域的新的规划识别方法， 从而达到在当前时间步起始状态下经过攻击者攻击行为作用后，对攻击者可能实 现的最终目标状态进行有效识别的目的。该算法不仅可以有效处理域的部分可观 察问题和偏序规划及多规划交替执行等问题，还可以排除智能体的误导动作，这 将在网络安全及入侵检测等许多领域都有广阔的应用前景。 关键词= ，规划识别：敌意规划；d c s p a b s t r a c t i m e l l i g e mp l a n 幽呜觚dp l 趾r e c o g 血i o ni s 姐i i n p o r t a n tr e s e a r c hf i e l di i l a n i f i c i a li n t e l l i g e n c e p 1 锄阳c o 嘶t i o ni n v o l v e si n f e r r i n g 廿l ei n t e n t i o 璐a n dp l 觚o f 趾a g e n tf o ma s e to fo b s e r v a t i o 粥锄dp r e d i c t sf 曲m - e t i o 璐 a sah o tr e s e a r c hb r a n c ho fi n t e l l i g e n tp l 姐m n g ，h o s t i l ep l a n i l i 】唱o i l l yf o c l l so n g a m es t r a t e g yd o m 血t h er e s e a r c ho nh o s t i l ep l 趾虹i 培i ss t i l la tap r e l i i l l i 加r y 1 1 1 h o s t i l ep l 舡m i n gd o m a i l l ，a g e n tc 觚e s t a b l i s hi t so w np l a ne 丘e c t i v e l yb 嬲e do n a d v e r s a r i a jp l a nb yr e c o 嘶z e da c c 瑚a 钯l y t h e r e f o r e ，w k ；t l e ru s eo fp l a nr e c o g 面t i o n m e n l o d si sa p p 州a ：t ed e c i d e s 1 es t 阴t e g yo fa g e n td i r e c t l y t h e r ea m 锄y l i “t a t i o 硒i n 跏i t i o n a lp l 趾r e c o 鲥t i o na p p r o h e s ，诋c hr e s t r i c ti t sa p p l i c a t i o n s o 、) l ，ei n t r 0 i d u c ean e w p l a nr e c o g i l i t i o nn 坞t 1 1 0 db 鹤e do na 1 1o b s e r w 通a c t i o ns e t ， ad ) r l l 跗血a c t i p e n d i n gs e t ，ad y m 蚰cl i k e l yp l 锄s e ta n dd c s ew h i c hc 觚 c 0 9 m 臻a d v e r s a i i a lm o s tp o s s i b l ef i r i a l9 0 a le 虢c t i v e l y o u rm e n l o d to i d yc m h 舡l d l ep 1 的b l e m su n d e rp 枷a lo b s e n ，a t i o na n dp a r t i a lo r d e r e dp l 龇塔b 哦a l s oc 觚 e l i i i l i n a t em i s l e a d i n ga c t i o r 坞t h es y s t e mb 弱e do no u rn e w p l a nr e c o g l l i t i o nm e t h o d c a i ib ea p p i i e di l lc 伽叩u t e rn e 咖r ks e c u r i 够觚di n t r u s i o nd 醣斌i o n b a s e do nt l l e a l g o r i 廿1 l i lp r o p 0 da ：b o v e ，w el l a v ei i i l p l 锄髓t e dan e wp l a n r e c o g i l i t i o ns y s t 锄，w i l i c hc a r m o to i l l yr e c o g i l i z e l ep l a na 1 1 dt h eg o a lt h ea g e n tb e i i l g p 娟r m e de f f i c i e n t l y ，b u ta l s 0i n d i c a t e 也ea c t i o n st h ea g e n tw i l lt a k e n i o 坞o w 鼍舔 也i e r ei sn or e a d y p l a i lr e c o 鳓i o ns y s t e m 瑚a l l d ，o u rs y s t e m 、i l lb es i 鲥f i c a l l _ tb o mi n r e s e a r c ha n dp r a c t i c ed t 0i t sn o v e l 劬 k e yw o r d s ：p l 觚r c c o 鲥t i o n ；h o s t i l ep l 觚；d c s p h 、 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究工作所取得 的成果。据我所知，除了特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果。对本人的研究做出重要贡献的个人和集体，均已在文中作了 明确的说明。本声明的法律结果由本人承担。 学位论文作者签名：刍址日期：遗西哔 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许 论文被查阅和借阅。本人授权东北师范大学可以采用影印、缩印或其它复制手段保存、 汇编本学位论文。同意将本学位论文收录到中国优秀博硕士学位论文全文数据库 ( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论文全文数据库( 中国科学技 术信息研究所) 等数据库中，并以电子出版物形式出版发行和提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 日期： 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名： 日期： 电话： 邮编： 墨 雌叫 鱼趔 东北师范大学硕士学位论文 引言 在敌对领域( 入侵检测，战争领域，经济领域，电脑博弈游戏等) 中，敌对 过程是指智能体双方在能够合理制定、完整执行己方规划的同时，及时有效地阻 止敌方目标实现的过程。因此智能体必须从检测敌方已执行的动作向预测敌方未 来要执行的动作转变，这不仅是敌意规划有待于进一步解决的重要环节，同时也 是其发展的必然趋势。这就要求智能体不仅要能够及时观察到监测系统中攻击者 已执行的动作，同时还要能够合理地对已观察到的动作进行分析，进而推断攻击 者的目标和意图，以便系统采取必要的措施应对。 通过已观察动作来分析推断其它智能体目标的过程称为规划识别。规划识别 理论是人工智能研究领域中一个很重要的方向，目前在国际上还只是处于初步研 究阶段，在国内对于该领域的研究和规划识别器的开发也还仅止于起步阶段。将 规划识别理论应用于敌对领域是解决其中相关问题的一个重要途径，由于敌对领 域是一个含有诸多敌对特性( 动态性，非确定性，多智能体，部分可观察等) 的 复杂领域，而且传统的规划识别方法存在着许多的假设和应用条件，这些局限性 限制了规划识别在敌对领域中的应用。 本文正是从以上方面入手，针对于规划识别自身的特点，在特定的敌意规划 问题中应用规划识别理论，将d c s p 融入到规划识别方法中，通过构造合理的规 划识别模型和已观察到的敌意a g e n t 执行的动作来预测攻击行为所欲实现的所 有可能目标状态，以便从中找出攻击者所欲实现的最终目标状态，达到在当前攻 击过程中对攻击者攻击行为进行有效识别与响应的目的，从而解决了传统规划识 别方法的一些局限性，使新方法能够更适用于敌对领域。 东北师范大学硕士学位论文 第一章规划识别概述 规划识别n 1 是人工智能研究领域中一个相当活跃的研究方向，它已经被广泛 地应用于自然语言理解、知识理解和情景演算等计算机系统的许多方面。 规划识别问题是指从观察到的某一智能体的动作或动作效果出发，推导出该 智能体目标规划的过程乜1 。一个规划识别器得出的规划能补充一些我们未观察 到而又实际发生的现象，同时还可以合理地预测a g e n t 未来可能执行的动作。 一般认为，个规划识别问题由以下几部分组成： 一个动作描述的集合； 一个有限的、动态世界的对象集合； 一个初始条件的命题集合； 一个目标描述集合( 详细说明可能的目标) ； 一个已观察到的动作集合，它们可能局部有序； 一个明确的分离的时间步集合。 1 1 规划识别的发展历史 规划识别自1 9 7 8 年被s m i d t ，s r i d l l a 豫n 和g o o d n 作为一个独立的研究 问题提出至今，已历经3 0 多年的发展，其方法日臻成熟。 1 9 8 5 年，c h a n l i a l 【和m c d e m 酣提出溯因理论是规划识别的最好方式口1 ，只 有这样才能推导出最合理的目标解释。 1 9 8 6 年，量h u ：t z 和l e n 第一次将规划识别理论形式化h 1 ，提出了基于限定 理论和最小化集合思想的通用框架，这是规划识别研究史上的一个里程碑。 1 9 9 0 年，l a i l l 以l i h n z 理论为基础提出了一种基于语法分析的规划识别理 论嘲，该方法虽然搜索速度快，但表达能力不如l ；湎舵的方法，而且它无法处理 时序约束问题。 同年，c 矗b e 哪将d e m p s t e r - s h a f e r 理论应用到规划识别中嘲，通过多个证据 来计算规划假设的联合支持度。 1 9 9 1 年，c l l a ：h l i a l ( 和g o l d m 觚构建了规划识别的第一个概率模型口m 1 ，并将 贝叶斯网络应用到规划识别中，使规划识别方法向更广泛的应用又迈进了一步。 1 9 9 5 年，h o n gj 吼从b l 啪和f u r s t 提出的规划图中得到灵感，提出基于目 标图的规划识别嘲，极大地提高了规划识别的速度。 1 9 9 9 年，g b l d m 锄和g k i b 提出了基于规划执行的规划识别算法n 们，该方法 从一个新的角度出发来解决规划识别问题。之后的几年里，g o l 等人对这 种方法不断地修改，将其应用到了多种领域，特别是敌对环境下的规划识别，并 将其应用于入侵检测系统n 1 】。该算法虽然能处理环境的部分可观察问题、多规划 2 东北师范大学硕士学位论文 交替问题和支持多目标的动作问题，但在考虑未观察动作的识别问题时，算法的 效率不高。 2 0 0 2 年，姜云飞教授在一种基于规划知识图的规划识别算法中提出了 一种新的规划表示方法即规划知识图的概念n 甜，与目前规划识别领域广泛使用的 砒的方法相比，新的规划表示方法更加简便直观，而且由于在规划知识图中 增加了支持程度的概念，使得规划的识别可以随着收集到的新证据而合理地改 变。 2 0 0 3 年，m 蛐在h o n gj 吼目标图的基础上提出了利用回归图进行 规划识别n 。回归图由命题结点、动作结点和目标结点组成，将回归图中的结点 分成确定的结点和可能的结点来识别确定的目标和可能的目标。该方法既保留了 目标图分析方法的优点，又能识别出确定的一致目标和可能的一致目标。 同年，f 捌 1 l ( m u l d e r 和f 啪sv o o r b r a a l ( d 对战术规划识别进行了形式化描述， 给出了规划识别过程中观察的不确定性n 扣。观察的不确定性可以分为四种：可识 别的观察观察中的动作以及动作的对象都可被唯一识别；不可识别的观察一 一可观察到动作，但识别不了动作的对象；概率观察观察者能够估计观察中 某个变量的值；不确定的观察观察本身就是不确定的，每个观察都有一个信 任程度。 。 由规划识别的发展历程，我们可以看出，随着新方法的不断提出，规划识别 技术可以处理的实际问题越来越多，越来越复杂，从而使其应用前景也越来越广 泛。 1 2 规划识别的分类 根据不同的标准，规划识别有多种不同的分类方法，概括起来主要有以下几 种n 司： 1 根据智能体在规划识别中的作用分类 这是规划识别最常用的分类方法。c o h e i l p e 饿u j l t 和舢l e n 在1 9 8 1 年提出了 规划识别的这种分类方法，分为洞孔式规划识别和协作式规划识别。2 0 0 1 年g e i b 和g o l d m 眦又在此基础上增加了对手式规划识别n 町。 洞孔式规划识别：智能体不关心或不知道识别器在观察它的动作。在识别 器识别的过程中，智能体不会对识别器提供帮助，也不会刻意阻碍识别器对它的 识别。 协作式规划识别：智能体积极配合识别器的识别，智能体所做的动作有意 让识别器理解。 对手式规划识别：智能体所做的动作对识别方造成威胁，破坏了识别方的 正常规划，并且智能体还会阻止或干扰识别器对它的识别。 这三种规划识别都有其自身的特点，因此它们的应用领域也各不相同。洞孔 式规划识别主要应用在生产监控、智能用户接口等领域；协作式规划识别主要应 3 东北师范大学硕士学位论文 用在机器人足球、故事理解等领域；对手式规划识别则主要应用在入侵检测、军 事指挥等敌对环境。以上三种规划识别中较常用的是洞孔式规划识别。 2 根据规划识别是否具有规划库分类 有库的规划识别：用分层任务网络、事件层、知识图或其他方式预先描述 规划，并以此作为识别规划的依据。 无库的规划识别：识别器不需要根据预先给定的规划就能给出识别结果。 目前大部分的规划识别方法都是基于有库的规划识别。该方法直观、易于理 解，但用这种方法进行识别前，需要做大量的建立规划库的准备，在搜索过程中 常常会消耗大量的时间或空间。无库的规划识别突破了必须有特定规划库才能进 行规划识别的限制。无库的规划识别方法可以识别出新的规划，因此很适合入侵 检测、战术规划识别等智能体处于敌对状态的规划识别。但是，由于这种方法还 不完善，不能判断规划假设的优劣，所以可应用领域还比较狭窄。 3 根据规划识别是否具有完整的领域知识分类 有完整领域知识的规划识别：识别器完全掌握动作的前提，效果或动作的 执行概率等情况。 无完整领域知识的规划识别：识别器不能完全掌握动作的前提，效果或动 作的执行概率等情况。 由于后者的复杂度较高，目前大都假设识别器具有完整的领域知识。 4 根据所识别的规划是否有错误分类 对无误规划的规划识别：识别器所识别的智能体在进行规划的过程中，所 执行的每一个动作对于到达目标都是必要的。 对有误规划的规划识别：识别器所识别的智能体在进行规划的过程中，执 行了一些错误动作。这些错误动作，或者是智能体本身能力限制造成的，或者是 智能体为了干扰识别器对它的识别而特意执行的干扰性动作。 所识别的规划是否是有误规划，还要依据识别背景及经验来判断。与实际情 况更接近的是假设所识别的规划存在错误。但为了简便，目前大多数的规划识别 方法都是在假设所识别的规划为无误规划的前提下进行的。 5 根据所识别的动作序列是否完全可观察分类 完全可观察规划识别：识别器能够观察到所识别智能体的全部动作及动作 的执行顺序。 部分可观察规划识别：识别器不能观察到所识别智能体的全部动作。这可 能是由于识别器遗漏了，也可能动作本身是不可观察的。这种情况通常用动作的 效果来进行识别。 从某种角度来看，完全可观察规划识别是部分可观察规划识别的特例，前者 对比后者要相对简单。通常情况下人们都是假设所观察的动作序列是完全可观察 的，以降低识别难度。但是在现实生活中，很多情况是无法完全观察到的，尤其 是识别方与被识别方是敌对关系的情况下，想要得到对方的全部动作信息更是不 4 东北师范大学硕士学位论文 可能的。因此，部分可观察规划识别具有更高的研究价值。 6 根据观察结果是否可信赖分类 观察可信赖的规划识别：所观察到的动作就是实际发生了的动作，对这些 动作所做的规划识别就是观察可信赖的规划识别。 观察不可信赖的规划识别：在这种识别中，有些动作不能完全肯定是否真 实发生了，它们的发生带有一种可能性。这种动作通常都被赋予一个可信度，以 确定该动作可信赖的程度。 由于识别器的疏忽或某些情况的干扰，识别器可能无法确定一些动作是否真 实发生，因此导致了观察的不可信赖。为使问题求解更容易，或者某些领域不存 在不可信赖的动作，通常的规划识别都假设观察是可信赖的。 1 3 规划识别的方法 1 基于事件层的规划识别 1 9 8 6 年，和础l e n 第一次形式化了规划识别理论，提出了一种通用的 规划识别模型，其中，他们将动作和规划统称为事件，用事件层来表示已知的可 能规划。在事件层中，根结点为高层动作，其他动作均依赖于高层动作。用e n d 表示具有独立意义、不需要依赖于其它高层动作的动作或事件，抽象于e n d 的事 件都是e n d 事件。事件层中包括： 一元事件类型谓词集( h e ) 抽象公理集( h a ) 基本事件类型谓词集( h e b ) 分解公理集( h d ) 通用公理集( h g ) 该规划识别模型还包含四种假设；穷尽假设( e x a ) 、互斥假设( d j a ) 、使用 部件假设( c u a ) 及最小基数假设( m c a ) 。前三种假设都以m c c 砒h y 的限定理论 为基础。当观察到某一动作序列时，根据这四种假设，识别器会对其中的每个动 作都生成相应的解释图( 表示由某一动作推导出的各种事件及事件间的关系的与 威图) ，并找出这些动作的所有可能的合并结果。最后，选择合并后e n d 事件最 少的解释图或解释图集合作为规划识别的输出。 这种规划识别方法具有丰富的表达能力，可以处理动作间的时序关系及不完 全观察动作序列，并且能够很好的识别偏序规划。但由于识别中采用了最小覆盖 模型，并认为所有事件出现的可能性都是一样的，使得识别结果过于武断。该识 别还要求所识别的智能体不能犯错误，识别所依据的规划库是完备的，这在一定 程度上影响了该识别方法的应用n 刀n 钔。 2 基于规划知识图的规划识别 2 0 0 2 年，姜云飞和马宁将姚的事件层改造为更简便更直观更易于操作 的规划表示方法一规划知识图，并在此基础上提出了基于规划知识图的规划识 5 东北师范大学硕士学位论文 别1 训。 规划知识图是一个非循环的与或图，其中，结点表示规划，结点间的连接 符表示事件之间的整体与部分、具体与抽象的关系，连接符上的数字表示子结点 对父结点的支持程度( 指一个规划( 事件) 的出现使另一个规划( 事件) 出现的 可能性) 。 在识别过程中，根据已观察到的动作，通常可能推出多种结果。与龇选 择e n d 事件最少的推理结果作为识别的最终结果不同，姜云飞等人认为，根据支 持程度来判断识别的最终结果会更接近实际情况，因为不同动作在满足条件的规 划内的重要程度是不一样的，所以规划出现的可能性也不同。 3 基于目标图分析的规划识别 通常的规划识别都是有库识别。2 0 0 0 年，h o n gj l l l l 提出了一种不需要规划 库的目标识别方法基于目标图分析的目标识别方法。 给定观察动作集合，通常的规划识别方法会搜索可能的规划识别假设，作为 候选规划和目标，以此来解释观察动作。这一搜索过程无疑会增加规划识别的时 间及空间消耗，甚至使有些识别问题无法解决。 而h o n gj u i l 提出的规划识别方法与大多数规划识别方法不同，该方法没有 规划库，因此可识别新规划；不直接搜索可能规划，而是先构建一个目标图，用 这个图来分析识别的目标和规划，因此不存在指数级空间消耗的问题；只保留与 当前已观察动作一致的目标及规划，降低了识别结果的二义性。因此，与有库规 划识别相比，该方法有着明显的优势。 由于该方法突破了必须有特定规划库才能进行规划识别的限制，能够对新规 划做出识别，所以很适合入侵检测等智能体处于敌对状态下的识别。但是由于它 还不够完善，只能解释过去的动作而不能预测未来的动作，因此该方法目前适用 于故事理解、软件咨询系统、数据库查询优化和客户数据挖掘等领域。 4 基于动态贝叶斯网络的规划识别 贝叶斯网络又称信度网，是目前比较流行的一种不确定性推理方法，它用图 形的方法来表达结点间的因果关系。近年来，学者们将贝叶斯网络应用到动态领 域，即贝叶斯网络随着时间的推移而逐渐扩大。在有库规划识别中，以往通过手 工编码来建立规划库的方法限制了规划识别的发展，而动态贝叶斯网络可以在训 练过程中学习到领域特征，并能将所学应用到推理过程中。因此将动态贝叶斯网 络应用到规划识别领域能有效地解决手工编码所带来的问题。 a l b 粥c h t 等人利用动态贝叶斯网络来表示领域特征，以推导用户的规划及目 标，其网络结构是根据分析领域特征确定的。该方法在训练过程中确定条件概 率分布，因此能够依据所观察到的行为动态构建概率分布，并且在训练和测试过 程中允许不完整的、零散的或带有噪声的数据存在。试验表明，该方法具有很高 的预测准确度。 h 毗等人船u 也在他们的l u l i l i e f e 工程中将贝叶斯网络应用于规划识别。 6 东北师范大学硕士学位论文 由于不确定性无处不在，而动态贝叶斯网络又是建立在概率方法基础之上 的，因此，采用动态贝叶斯网络可以有效地诊断出用户的需求，为用户提供有用 的帮助。 5 基于回归图的规划识别 回归图识别方法与目标图识别方法一样，都属于无库识别方法。它的主体思 想直接来源于图规划和目标图，主要通过回归的思想来完成对观察到的和未观察 到的动作和目标的识别以及对未来可能发生的动作和目标的预测。回归图的结构 与目标图的结构相似，均是由命题结点、动作结点以及目标结点组成的层结构， 其中这三种结点交替出现。这种方法通过将回归图中的结点分为确定的结点和可 能的结点来识别确定的目标和可能的目标，其中确定的结点由观察到的动作生 成，可能的结点由领域知识生成。利用回归图的方法进行规划识别，首先识别器 会根据观察到的动作以及领域知识构造回归图，每观察到一个动作就将其添加到 图中，并且立即回退，以删除那些由领域知识生成的但与观察到的动作有冲突的 动作节点和命题节点，通过这样的回退来达到识别确定的目标和可能的目标。也 就是说，它可以识别出确实发生的动作及目标，也可以预测未来可能发生的动作 和目标。 ， 回归图识别方法继承了h o n gj 咖目标图方法的优点，并且在弥补其不足的 同时又具有自己特有的优势。它考虑了不可观察动作这一情况，使回归图算法更 符合客观事实，同时它也可以预测未来可能发生的动作及目标。由于引入了互斥 关系，回归图变得更为紧凑，在准确性、有效性以及可伸缩性等方面都有良好的 表现。由于它属于无库识别方法，省去了规划库的建立、管理和完善等繁杂工作。 但是回归图识别方法在处理一些动作之间的关系上还存在着一定的问题，识别也 只限制在s 1 砒p s 域，且只有具有较完整的领域知识才可以完成相关识别工作。 6 基于因果网络的攻击规划识别 在安全管理中，安全警报的联系与分析是一项非常重要的任务，目的是要有 效地识别攻击者的攻击目标、策略以及预测未来的攻击，以便及时有效地阻止攻 击者对需要保护的网络和系统的攻击。x i n z h o uq i n 和w 醯k el e e 提出一种名为 因果网络( c a u s a ln e 咖r k ) 的方法来解决以上问题嘲。这种方法首先用攻击树定 义攻击规划库来联系孤立的警报集，然后把攻击树转化为因果网络，在因果网络 上，可以通过合并领域知识来估计攻击目标的可能性和预测未来攻击。 网络攻击规划识别与传统的规划识别有着非常大的区别，所以传统的规划识 别方法并不适用于识别网络攻击。基于因果网络的攻击规划识别可以针对网络识 别的特殊要求，来实现源于底层警报的相关性分析，识别攻击者的高层策略和目 标，并基于观察到的攻击行为预测潜在的攻击。与其它的网络规划识别方法相比， 基于因果网络的攻击规划识别方法不但可以实现对孤立的警报集的相关性分析， 重要的是它可以识别出攻击者的高层策略和目标。但是这种方法在应用上还存在 着一定问题：首先因果网络是由攻击树转化而来的，而攻击树的定义和构造的困 7 东北师范大学硕士学位论文 难程度相当于传统规划识别的规划库的建立，虽然o s h e y n e r 等人提出一种自动 构造攻击树的方法，但仍存在着很多问题；其次，因果网络的构造目前还停留在 比较简单的层次上，即单连接因果网络，以简化因果网络连接程度的方式来减少 概率推理的时间代价。 规划识别的方法有很多，除以上方法外，还包括基于语法分析的规划识别， 基于规划执行的规划识别，基于动态概率关系模型的规划识别，基于决策理论的 规划识别，基于变形空间的规划识别和基于抽象策略的规划识别等。 1 4 规划识别的应用 规划识别经过近3 0 年的发展，在很多领域中都有所应用。早期广泛应用在 自然语言理解、智能用户接口及用户模型等领域，目前其应用己扩展到网络安全、 入侵检测、战术规划识别及工业控制等领域。 1 网络安全 入侵检测是当前网络安全中一个非常活跃的研究领域。而入侵检测系统如果 想要更进一步发展，就必须加入人工智能方法。入侵检测系统( h i 觚i o nd e t e c t i o n s y s t e m ，i d s ) 要求根据已发生的动作预测出未来动作，这一过程在人工智能领域 中称为规划识别。规划识别可以预测入侵者的未来动作，并做出适当的回应。因 此，规划识别方法必将是未来入侵检测系统的重要组成部分。 2 0 0 1 年，( k i b 和g o l d m 锄将规划识别应用到入侵检测领域嘲。该方法采用 了g e i b 等人之前的基于规划执行的规划识别方法，由于没有设置太多的限制性 假设，因此，能够处理较广泛的规划识别问题。该方法着重处理了与以往识别环 境不同的敌对环境下的规划识别问题，包括从已观察到的动作或状态改变中推理 出未观察到的动作。这些能力的增加，也极大地扩展了规划识别的应用领域。该 方法可以从同一观察数据流中区分出多个智能体的攻击目标及规划。 q i i l 等人认为g e i b 和g o l d m 孤提出的旨在识别网络攻击的规划识别方法对 规划库的定义过于细致，增加了推理的计算复杂度。2 0 0 4 年，) ( i l l z h o uq i n 和 w r e i 岫l 采用因果网络对网络攻击进行识别。他们认为，将传统的规划识别应 用到安全领域必须解决以下问题。首先，传统的规划识别技术通常应用在非敌对 的情况下，识别过程可以是辅助式的，也可以是不受所识别智能体干扰的。然而， 在安全应用方面，攻击者是试图消除或者干预对其入侵行动的识别的；其次，在 传统规划识别中应用的假设在对手式规划识别中已经不再适用，因此必须对原有 方法加以改进，以适应应用领域的变化。他们研究了组织概率推理方式，使其能 够联系和分析攻击方案。所提出的方法可以解决如下问题：从低层的警报中识别 出独立的攻击方案；识别攻击者的高层方案及目标；用观察到的攻击行为来预测 潜在的攻击。 2 军事防御系统 战术规划识别需要能够处理不完全知识、动作的随机结果及不确定观察。在 2 东北师范大学硕士学位论文 军事应用中，特别在利用感知数据进行决策时，采用规划识别方法有着重要的价 值。战术规划识别的主要特点是快速、准确、高效。因为军事指挥者通常需要快 速、准确、高效地判断战场状况及战争走势，并根据判断结果来做出战争部署。 3 其它应用领域 早期的规划识别方法主要应用于自然语言理解。规划识别能够增强用户接 口，从接口交互中对用户目标和规划进行识别，能更好地为用户提供智能辅助。 规划识别增强了用接口来辅助用户完成任务的能力，它能检测用户的错误，并给 予修复。通过接口来监视用户的行为，推断出其目标和规划，以此决定用户所需 的帮助，辅助用户完成任务。 另外，规划识别在交通监控、计算机辅助教学、危机管理等方面也有广泛的 应用。 1 5 本文工作 本文首先介绍了敌意动作，敌意规划和危机系数等基本概念；随后对敌意规 划库，敌意知识库和敌意推理机进行了研究，在给出动态已观察动作集，动态动 作悬挂集和动态可能规划集的基础上，结合d c s p 理论，提出了一种更适用于敌 对领域的新的规划识别方法基于d c s p 的规划识别算法。从而达到在当前时 间步起始状态下经过攻击者攻击行为作用后，对攻击者可能实现的最终目标状态 进行有效识别的目的。 本文结构如下：在具体介绍新的识别方法之前，我们有必要对其所涉及到的 相关知识和方法进行简要的回顾。第一章对规划识别进行了概述；第二章介绍了 敌意规划及敌意规划识别系统；第三章介绍了d c s p 及其在图规划中的应用并回 顾了一下几种主要的规划识别方法，归纳并总结出传统识别方法应用于敌对领域 时的局限性，然后针对存在的问题，本文给出动态动作悬挂集等新的概念，并提 出基于d c s p 的规划识别方法和模型；最后对新识别方法的功能、特点和实验结 果进行了总结。 9 东北师范大学硕士学位论文 第二章敌意规划 2 0 0 3 年1 月美国总统下令制定了网络战略，以便在必要的情况下对敌方的 网络系统发动袭击。这里对系统的攻击性动作必然包括对敌方网络系统中的软件 和硬件的破坏，这种动作就是敌意动作，包含敌意动作的规划就是敌意规划。 2 1 敌意动作与敌意规划 如果一个实体在初始状态下经过执行一系列的动作，如动作4 ，动作彳：， 动作彳。，最终到达目标状态，那么这一动作序列：动作4 ，动作彳，动作 彳。就叫做一个规划。 敌意动作嘲是指由a g e i i t 所发出的某些具有攻击性和破坏性的实例化操作， 它可能是部分的或零散的，也可能是即时的或实时的。但究其根本，这些动作的 最终目标都是破坏对手a g e m 系统( 软件系统或硬件系统) ，从而达到使对手系 统瘫痪的目的。 由这样一个或一系列敌意动作4 ，4 ，彳。所构成的序列，就叫做敌意 规划。 2 2 敌意动作的一种形式化描述 从对手a g e n t 的角度出发，对于被攻击a g e n t 而言，敌意动作可以用一个三 元组渊表示： 只= 0 1 ) 其中，口表示执行敌意规划的a g e n t 的个数； 彳表示a g e m 发出的一系列攻击破坏性动作( 动作集) ； g 表示此次由a g e m 发出的敌意规划所要攻击的目标( 目标集) 或欲摧毁的对象 ( 对象集) ； 五叫做危机系数，它表示对手a g e n t 动作集对于被攻击a g e n t 目标集的威胁程度， 五【o ，1 】。 下面介绍三种不同的危机度： 自身危机度，当前时间步中的当前攻击行为作用下所可能实现的多个可能 的目标状态结点根据专家经验及领域知识具有多个危机度值与其相对应，把这种 危机度称为该行为状态列可能的目标状态结点的自身危机度，记为p ( 丸) 。 相对危机度，指在通过对攻击行为作用下实现的所有可能的目标状态的自 身危机度值的计算后，所得到的该可能的目标状态相对于攻击者试图攻击前所欲 东北师范大学硕士学位论文 实现的最终目的状态的危毋程度，记为尸( 九g ) 。 尸( 九g ) = 尸( 九k ) 萎p ( 砧k ) 驷i 一 最大相对危机度，指将同一列中的所有可能的目标状态结点的相对危机度 值进行比较。其中，我们把具有最大相对危机度值的那一个可能的目标状态结点 作为该列的最终目标状态结点，记为p ( 砧k g ) 一 2 3 敌意规划识别系统的组成 基于敌意规划识别与应对的特点，我们可以通过构造一个敌意规划识别系统 的形式化模型，来实现对离散的、非连续性的敌意规划的处理。该系统主要由三 大部分组成嗍： 1 敌意规划库 敌意规划库是敌意规划识别系统中最基本的敌意动作库。它以2 2 中定义过 的敌意动作的形式结构存储记录，并且在敌意规划库中存储的每条记录的敌意目 标项都是软、硬件系统中最可能被敌意a g e n t 所攻击的敌意目标。它主要实现对 当前规划( 动作) 叶子节点与在敌意规划库中的记录进行匹配。当敌意指针在敌 意规划库中按照危机级别在相应的分段搜索过程中，发现当前敌意搜索树中分解 出的子节点与敌意规划库中的某一基本动作相匹配时，规划分解结束。并将匹配 成功的动作所对应的目标项返回给敌意规划识别系统，同时将该次匹配成功的九 值送入敌意知识库中，从而实现对敌意知识库的部分更新。 2 敌意知识库 敌意知识库是敌意规划识别系统的核心之一，它主要存储两种类型的知识： 一类是软件和硬件相关领域中的所谓公开性的敌意知识，比如软件系统漏洞，口 地址、硬件接口被攻击与破坏，网络入侵检测等一系列在相关领域中的相关定义、 事实与理论；另一类是在该敌意规划所攻击或欲破坏的目标方面，一些该领域的 知识工程师与领域专家的个人知识与经验，这些经验是该领域专家经过多年的业 务实践逐渐积累起来的，其中很多被称为启发式信息。在敌意知识库的信息存储 方面，信息都是以关系二维表的形式存储的，即根据统一的三元组格式，在敌意 知识库中将行为与状态的变化表示为最基本的攻击行为及对应的所有可能的目 标状态和所具有的自身危机度值。敌意规划识别系统正是通过这样的知识库，来 实现对那些由敌意规划的组合因素复合而成的模糊规划进行分解，从而使动作分 解规划不断扩展下去，为最终敌意规划的识别提供可能。 东北师范大学硕士学位论文 3 敌意推理机 图2 1 敌意规划识别系统结构示意图 敌意推理机实际上是敌意规划识别系统中的一组推理知识模块。其主要功能 是协调整个系统的运作，决定如何选用知识库中的相关知识，对具体敌意规划进 行分解，并对对手a g e n t 所发出的各种敌意规划进行正确推理，以使得规划分解 不断地进行下去，为最终搜索出基本敌意动作完成敌意规划识别提供动力机制 ( 如图2 1 所示) 。 此种匹配方法查找速度很快，因为当前攻击行为作用下所产生的所有可能的 目标状态都是以组的形式在敌意知识库中存储的，一旦敌意推理机在敌意知识库 中查找出了4 攻击行为在知识库中的第一条记录，那么它就可以以线性搜索的方 法将指针在关系表中递加，直到攻击行为不符合当前情况为止。这样，我们就可 以很容易的查找出敌意知识库中攻击行为所对应的所有可能的目标状态，进而也 就知道了所有可能的目标状态所具有的自身危机度值。如果匹配成功，则说明在 敌意知识库中存在着这样一条攻击行为状态信息，那么敌意推理机就会根据该组 状态信息所对应的状态表项取出该种可能的目标状态的自身危机度值，然后对该 值进行相对危机度及最大相对危机度值的计算，最后再将分析结果送往决策响应 模块进行决策响应，从而达到在入侵行为发生前就发出警报的目的；如果匹配不 成功，说明在当前敌意知识库中不存在该条攻击行为及其所对应的状态表项，即 当前状态不足以表明该行为状态的攻击性，那么就要按照行为状态图的变化继续 抽象描述，直至发现攻击性行为为止。如果直到最终状态时，还没有在敌意知识 库中发现表项，那么敌意推理机就会主动抛弃对该条信息的操作，当然也就不会 将分析结果送至决策响应模块进行决策响应，进而转到继续处理其它信息。在这 里，敌意推理机工作的重要前提是：考虑到每一种状态在前提条件允许的情况下， 经过一个攻击行为动作之后，它必然会导致下一个状态的发生，那么我们就会根 据当前攻击行为和可能的目标状态的条件在敌意知识库中线性搜索，如果一旦发 现了攻击行为及可能的目标状态与敌意知识库中的相关表项相匹配，那么敌意推 理机就将分析结果送入决策响应模块进行决策响应，从而就达到了响应入侵和识 别的目的。 1 2 东北师范大学硕士学位论文 2 4 敌意规划的识别 在复杂领域多a g 锄t 条件下，往往在敌意规划执行过程中对手之间的关系是 比较多样的( 可以是一对一，也可以是多对一等) ，且来自于对手的敌意规划形 式是不确定的、模糊的和复杂的。这就要求我们在识别敌意规划的过程当中必须 具有分解组合因素复合而成的模糊敌意规划的能力；另外，在现阶段敌意规划( 如 网络入侵) 识别过程中，被攻击a g e n t 往往无法预先确定敌意规划的攻击目标， 换句话说，我们应该在目标未被彻底攻击之前，就能够确定敌方意图，进而采取 有效的应对规划或反击规划田1 。 敌意规划作为智能规划研究的一个重要分支，目前，还只停留在游戏策略的 研究领域。但是随着网络技术的迅猛发展、黑客的肆意攻击、病毒的推陈出新和 广泛传播，要求我们必须及时展开对恶性网络入侵检测及应对的研究，否则，对 于国家的网络信息安全就会造成巨大的威胁。敌意规划的识别与应对正是从这一 点出发，为解决实际问题而产生。目前国际上对于敌意规划方面的研究还不是很 多，大大限制了敌意规划的应用范围和研究前景。同时在许多敌意规划的实际问 题当中，世界状态往往是纷繁多变的，这就要求敌意规划领域的研究要更多地关 注复杂环境状态下的敌意规划。除此之外，由于敌意规划的自身特点，它还可以 被广泛应用于机器人竞赛、智能用户接口设计、模式识别、人工智能和专家系统 等广阔领域。因此，在复杂领域中多a g 铋t 条件下的敌意规划的研究显得尤为迫 切和重要。 1 3 东北师范大学硕士学位论文 第三章基于d c s p 的敌意规划识别算法 3 1 约束满足问题( c o n s 仃a i n ts a t i s f a c t i o np r o b l e m 卜s p ) 1 c s p 的定义 一个c s p 问题可以定义如下： 一个变量的集合：x = x l ，x 2 ，x 。 ； 每一个变量墨都有一个有限的值域d ； 一个约束的集合( 限制变量的赋值) ：列出与约束相关的变量允许的赋值 组合： c s p 问题的目标：为所有变量找到能同时满足约束的赋值。 任何一个k ( k 卜2 ) 元c s p 问题都可以转化为一个二元c s p 问题。在二元c s p 中，变量作为结点，两个变量之间有约束就在它们之间连一条边。 2 c s p 的几种搜索算法 ( 1 ) 朴素回溯法( b a c l 出a c k i n g ) 按顺序对未赋值的变量进行赋值，若失败则回溯到前一个变量，为那个变量 重新赋值。 ( 2 ) 前向检查法( f o 嗍r dc h e c 妯 1 9 ) 无论何时，一旦变量x 被赋值，前向检查法考虑与x 有约束的未被赋值的变 量y ，然后从y 的n 值域中除去那些与x 的当前赋值存在约束的值。 ( 3 ) 边一致法( a r cc o n s i s 锄c y ) 它是一种快速传播约束的方法。在约束图中边一致法考察所有x 及与x 相邻 的节点涉l ，y 2 ，儿) 。如果对于节点x 的一个取值h l ，节点儿的值域中没有一个 可以满足x 与乃之间的约束关系，则把啊，从x 的值域中除去。当把x 的所有相邻 节点都考察完以后，再用相同的方法来考察y ，以此类推。( 朴素回溯法和前向 检查法是不完全的边一致法。) ( 4 ) 动态变量排序( d y m i n i c a b l eo r d e r i n 曲 下一个要赋值的变量是通过一种指标确定的，一般的方法是选择值域的规模 最小的变量。 ( 5 ) 由冲突引导的回溯( c o i 删c t - 捌r e c t e db a c k j 啪p i n 妙 当前变量赋值失败后不一定回溯到在它前面刚赋值过的变量，而是通过它的 冲突集进行回溯，每次回溯到当前变量的冲突集中赋值时间离它最近的变量。 变量x 的冲突集c s ( 曲的生成方式如下： 初始时c s ( x ) = x ) ；若x 的当前试探赋值与它前面已赋值的变量y 的当前赋 1 4 东北师范大学硕士学位论文 值相冲突，则将y 加入c s ( x ) ，即c s ( 工) = c s ( x ) + y 。 3 d c s p 的定义 作为c s p 的扩展，动态约束可满足问题d c s p 矧制( d 删cc 0 n 咖j 玎t s a t i s f ；t i o np r o b l e i n s ) 的定义如下： 一个变量的集合：x = x l ，x 2 ，x 。) ； 变量的活跃标志( 指明当前的活跃变量) ； 每一个变量t 都有一个有限的值域d ； 一个约束的集合( 限制变量的赋值) ； 变量激活约束：如，若x l = v l l ，那么4 c f f v e ( x 2 ) ； d c s p 问题的目