基于状态机模型的网络安全策略验证方法研究

程晓荣，冯志伟

（华北电力大学 控制与计算机工程学院，河北 保定071003）

0 引 言

随着信息系统面临的安全威胁越来越严峻，需要制定安全策略实现安全设备的统一管理和有效联动，安全策略的表达和验证方法成为基于策略的安全管理研究重点。文献[1，2]讨论了安全策略的语法、语义和决策算法，但未考虑策略的验证；在此基础上，文献[3]基于一阶逻辑提出了基于良基语义的安全策略验证方式，在访问控制应用中具有可靠的策略验证能力；文献[4]提出用有向无环图描述主 （客）体之间的关系，提出了一种基于有向图的策略冲突检测方法，检测的复杂度是主 （客）体间关系的幂函数，当系统中主 （客）体间的关系较为复杂时，该方法的耗时量较大；文献[5]将安全策略描述为安全事件、规则、动作三元组，验证安全策略的完备性、一致性和冗余性，由于未进行安全域的划分，随着策略集的增加和系统复杂度的提升，策略验证方法复杂度较高；文献[6]用安全域、触发条件、执行动作和指导原则描述安全策略，设计了策略的正确性评估函数，并通过特征矩阵验证策略一致性，一致性检测算法的复杂度为O（4n2）；文献[7，8]分别运用高级Petri网对策略规则进行描述并对策略库中的循环、冗余、矛盾等异常规则进行验证。本文采用状态机模型验证策略库中的异常规则，在Petri网的基础上分离了系统状态、触发条件和执行动作，用无环状态有向图描述系统的状态变迁。并通过以子网划分安全域的方式降低了有向图的规模，使算法具有理想的执行效率。

1 相关概念

在网络信息安全系统中，安全域构成环境的子集，是由一系列实体与资源构成的[6]。安全域的划分有多种方式，文献[8]根据设备类型与业务将安全域划分为安全业务域、安全用户域、网络设备域和安全网络域。上述划分方式虽然分离了不同安全域的职责，但当网络结构较为复杂时，每个安全域的规模会非常庞大，不利于安全域中实体或资源的查询。本文将安全域按照子网的方式划分，因为子网中同时包含了防火墙、IPS等安全设备和这些安全设备控制范围内的实体资源，安全事件的捕获和策略的分发都可以在子网内部完成。同时按照子网划分安全域可以降低安全域的规模。

本文用状态机模型描述安全域中实体与资源的状态，安全策略的执行实质上直接反映为安全域中实体与资源状态的变迁。比如在触发条件TCP扫描事件的作用下，IPS的防TCP扫描模块会变迁为开启状态，在杀毒程序执行完成后扫描器会进入到漏洞扫描状态。通过分析安全域中设备的日志，可以及时捕获安全域中发生的一系列安全事件。安全策略就是通过执行相应设备的配置动作，实现系统状态的切换，最终达到解决安全事件的效果。

下面介绍相关的定义:

定义1 状态机，全称为有限状态机 （finite－state machine，FSM），是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。本文采用Mealy型状态机，它的下一个状态即输出是由输入和当前状态决定的[9]。本文阐述的状态机考虑单向的状态流动，即从开始状态到终止状态的变迁过程可由无环有向图来描述。状态机由五元组 （∑，S，s0，δ，F）构成，它们的含义分别为:

∑表示输入的非空有限集合，对应系统的触发条件集；

S表示状态的非空有限集合，对应系统的当前状态集和输出状态集；

s0表示初始状态，其中s0∈S；

δ表示状态转移函数，即δ:S×∑→S，即系统当前状态集在触发条件的作用下变迁为输出状态集；

F表示最终状态的集合，到达最终状态后不会再向其它状态转移，其中FS。

定义2 安全域D。安全域可以看作是系统中实体和安全策略的组合。安全域将规模庞大的网络信息系统划分为较小的研究单元，对每个研究单元分别制定安全策略，通过将不同安全域中的安全策略相关联，可以得到系统整体的安全策略。本文根据子网划分安全策略，使子网间的安全策略执行能够相互独立。网络信息系统的安全策略知识库是其包含的所有安全域的安全策略并集。

定义3 安全策略P。从广义上讲，安全策略是指实体为保证网络的安全性，在面临安全事件时对安全设备如何进行控制的规则集合。本文将安全策略具体描述为P＝＜D，C，R＞。其中D表示安全域，C表示触发条件，R表示策略包含的规则集，规则集中的每一条规则r对应一个配置动作，基于状态机模型，将规则r定义为r＝＜i，o，s0，l＞，其中i表示规则的原状态，o表示输出状态，则状态机中的状态转移可以描述为i（C）→o，其中i，o∈S，C∈∑。例如当 “IPS开启”时 （记作IS），发生 “DoS攻击”事件 （记作事件da），则系统执行规则进入 “IPS的防DoS攻击模块开启状态”（记作DO），则此策略规则可以表示为IS（da）→DO。s0表示规则所在安全域的初始状态，l表示规则的输出状态是否为最终状态。因为规则的输出状态包含了策略执行动作达到的效果，因此不再将执行动作显式地表现在策略中。每一条安全策略包含着一条或多条规则，每一条规则对应状态机中唯一的状态变迁过程，它包含的配置动作只包含完成一次状态改变的配置。由于安全策略实质上是规则的集合，因此只要系统的当前状态和触发条件满足，多个不矛盾规则中的配置动作可以同时执行。安全策略的执行原理如图1所示。

图1 安全策略的执行过程

2 策略知识库与系统运行分析

本节介绍通过状态机模型建立特定安全域的策略规则库的方法，一个安全域的全部策略规则对应一个完整的状态机，可以用无环状态有向图展现状态之间的变迁关系，如图2所示。下面有向图中展现的一个或多个状态变迁即构成某个特定安全域的规则库。

通过子网划分的安全域中主要包含服务器，用户主机，网络设备和各类安全设备。其中安全设备主要包括防火墙、IPS、防病毒系统和扫描器等。图2中状态机的初始状态为“系统运行”状态，状态变迁包括系统自发的状态变迁和因策略执行由触发动作引发的状态变迁两类，前者不包含触发条件，输出的状态在系统运行过程中始终存在于当前状态集中，在状态图中用椭圆形的节点标识；后者代表的策略规则统一存储在策略知识库中，是本文主要的研究对象，在状态图中用矩形节点标识。

图2 策略规则的无环状态有向图描述

采用具有强大数据处理能力的大型关系数据库作为主要存储部件，为便于寻址和易于扩展，将数据表看作可操作的最小存储单位，定义为存储资源[10]。策略库主要包含两个数据表，一个表用来存储安全策略，一个表用来存储供安全策略调用的规则集。为了提高策略的搜索效率和策略规则的验证效率，对每个安全域中的策略和策略包含的规则分别建表。根据安全策略及其包含规则的定义，设定安全策略表包含的字段为:策略ID、所属安全域ID、触发条件、规则集、异常、备用策略；设定规则表的字段为:规则ID、原状态、输出状态、在状态有向图中的初始状态、输出状态是否为最终状态。由于规则集中不包含触发条件，所以必须保证在建立安全策略时，从规则集中选取合理有效的规则。

系统运行中，要明确状态有向图中哪些状态是激活的，将安全域内所有激活的状态记做系统当前状态集。当接收到新的触发条件时，首先查看触发条件对应安全策略是否存在于知识库中，若不存在，则不满足策略完整性要求；若存在，查询安全策略所包含规则的 “原状态”，并确认其是否属于系统当前状态集。如果 “原状态”存在于系统当前状态集，则符合安全策略的执行条件，开始通过一系列配置动作执行安全策略；如果规则的 “原状态”不在系统当前状态集中，则将安全策略置入缓存中等待，直到系统执行完成特定数量的安全策略后再次考察缓存中等待的安全策略是否满足执行条件。系统在同一时间段内可能会收到很多触发条件，只要这些触发条件对应的安全策略都符合执行条件，则系统中的多个状态会同时发生变迁。在系统没进行到某些特定状态之前，某些触发条件是不可能发生的，比如系统未进入 “邮件过滤”状态，则不可能出现“邮件包含非法信息”触发事件。当状态机的某一条路径运行到最终状态时，最终状态从当前状态集合中删除，意味着一个完整工作流的结束。状态机模型可以准确地描述系统在各个状态之间的切换情况。

3 策略库知识库验证

知识库中的策略规则可能存在不合理性，需要对其进行异常分析，策略规则的验证主要包括正确性分析、完整性分析、一致性分析、冗余性分析、可执行性分析。针对特定安全域中的策略规则，通过以下几个方面进行规则验证。

（1）正确性分析:在策略规则的有向图模型中，从某个原状态到某个输出状态可能存在多条路径，即多个不同的触发条件可能引发相同的状态变迁，但是必须保证这些触发条件不能相互矛盾。

定义4 对于策略集P中的任意两个策略Pi和Pj，满足:

当且仅当 （Pi·Ci，Pj·Cj）∈∝时，称策略集P符合正确性要求，其中∝表示策略动作的非矛盾关系集。

在实际应用中，存在诸多的矛盾触发条件，例如可信IP地址和不可信IP地址、登录成功和登录失败、发现漏洞和未发现漏洞、系统无开发任务和开发任务等。举例说明:

例1:策略P1＝＜D1，C1，＜r1＞＞，P2＝＜D2，C2，＜r2＞＞

规则r1:WB（tp，lf）→LP表示 “当Web服务开启时，检测到连接的IP地址为可信IP地址且发生登录失败N次事件，则锁定登录用户IP”；

规则r2→LP表示 “当Web服务开启时，检测到连接的IP地址为不可信IP地址，则锁定用户IP”。

在上述两条规则中，都是状态WB向状态LP变迁，但是r1中包含的触发条件tp（可信IP地址）和r2中包含的触发条件（不可信IP地址）相互矛盾，因此如果两条安全策略作用的安全域存在交集，则不符合正确性要求。实际上，规则r1完全可以去掉触发条件tp。

（2）完整性分析：完整性是指对于系统能够捕获到的所有触发事件，策略知识库中都有相应的处理策略。

定义5 对于系统触发事件集conditions的任意一个触发条件c，满足：

在复杂的网络环境中，不能确保所有安全事件都有相应的处理策略，出现不完整的情况是很有可能的，此时可以构造默认策略满足完整性要求，比如 “向管理员发出特殊事件告警”等默认策略。

（3）一致性分析：策略的一致性保证策略集中不能发生同时应用在同一个对象上的两种不同策略［11］。如果策略作用于相同的安全域且触发条件相同，那么在此安全域策略规则的状态有向图中，对于同一个原状态，同一个它的触发条件不能引发多个不同的输出状态。

定义6 对于策略集P中的任意两个策略Pi和Pj，满足：

则称策略集P是一致的。

定义7 对于策略集P中的任意两个策略Pi和Pj，若满足：

当且仅当ri·oi≠rj·oj时，策略集P是一致的。

策略不一致往往是因为策略在添加、修改过程中更新后的安全策略与系统内原有的其它安全策略发生一致性冲突；还有一种原因是安全策略对于处理某类安全事件的效果没有明确之前，往往会出现备选策略，策略与其备选策略之间会存在不一致性，因此在策略知识库验证时要排除备选策略的干扰。下面举例说明违背一致性的策略：

例2：策略P3＝＜D3，C3，＜r3＞＞，P4＝＜D4，C4，＜r4＞＞

规则r3：V（v）→VK表示 “当防病毒系统开启时，检测到发现病毒事件，则启动病毒查杀程序”；

规则r4：V（v）→SC表示 “当防病毒系统开启时，检测到发现病毒事件，则进行漏洞修复操作”。

在上述两条策略中，规则的原状态和触发条件均相同，如果策略作用的安全域存在交集，则根据一致性的定义，上述两条策略不符合一致性要求。

（4）冗余性分析：策略的冗余性包含两种情况。如果两条策略完全一致，即作用的安全域、触发条件与执行规则均完全一致，称为重复冗余；如果策略作用的安全域中策略主体或策略客体因系统更新或网络拓扑结构发生变化而脱离安全域，此时相关的策略无法执行，称为失效冗余。

定义8 对于策略集P中的任意两个策略Pi和Pj，若满足：

当且仅当ri·ii＝rj·ij且ri·oi＝rj·oj时，称策略集P存在重复冗余。

定义9 设当前安全域中设备包含的所有状态集合为state－Di，对于策略集P中的任意策略Pi，-ri∈Pi·Ri，若ri·iistates－Di∨ri·oistates－Di，则P为失效冗余策略。

对于重复冗余的检测，只需逐条对比两条策略的所有参数；对于失效冗余的检测，需要对设备进行定期监控，确保策略库所有规则包含的状态都属于当前安全域中设备能够产生的状态。

（5）可执行性分析：策略的可执行性需要保证规则状态有向图中所有的状态必须可达，同时保证所有的状态节点都具有能达到最终状态的路径。一个安全域只对应唯一的状态有向图，且状态有向图具有唯一的根节点。只需保证在有向图的一次遍历中能够经过安全域内所有的状态节点，且所有的叶子节点都为最终状态节点，则能够保证策略规则的可达性和可终止性。

通过遍历所有安全域中策略规则的无环状态有向图对上述的所有异常情况进行验证。为了便于执行有向图的深度优先遍历，降低复杂性，设置状态有向图不存在环路。在策略知识库验证前，需要检测安全域中的所有设备，明确所有设备能够产生的状态，构建安全域状态集state－Di，便于失效冗余检测；同时，明确安全域中的安全设备能够应对的触发条件集conditions，便于完整性检测；还需明确状态有向图的根节点 （初始状态）和叶子节点 （终止状态），便于可执行性分析。

对系统中所有安全域对应的无环状态有向图进行深度优先遍历，可实现对策略规则的上述五类异常情况分析。在进行正确性与一致性分析时，只需判断状态有向图中由同一状态节点出发的各条路径中是否包含矛盾触发条件，是否包含重复触发条件。对于矛盾触发条件引出的多个输出状态，如果相同，则违背正确性原则。对于重复触发条件引出的多个输出状态，如果相同，则违背冗余性原则；如果不同，则违背一致性原则。

4 复杂度分析和实验

设系统中包含安全域的数量为k，设定安全域Di包含的状态节点数为ni，边数为ei，相邻的两个状态之间可能有一条边或多条边。遍历有向图的时间复杂度为O（ni＋ei）。当遍历到某个节点时，将其引出的所有边依次放在数组中，每条新加入的边都要与数组中的边进行对比 （判断是否重复或是否矛盾），考虑极端情况，即假设所有的边都进行对比，则比较次数为ei（ei－1）／2，时间复杂度为O2）。考虑平均情况，设有向图中有h个非叶子节点，且每个非叶子节点均引出e／h条边，则比较总次数为ei（eih）／2h，对于一般的有向图而言，h接近于ni／2，则有向边之间进行比较的时间复杂度一般为2／ni）。当然，不管同一个状态节点引出的有向边之间重叠与否或矛盾与否，还需要对比其所有的输出状态 （一致性检验、重复性检验和正确性检验的需要），由于输出状态的数量不大于有向边的数量 （两个状态之间可能出现多条路径，但同一条边不可能引出多个状态），因此输出状态之间进行比较的时间复杂度也可记作O2／ni）。另外，有向图中的所有状态与集合state－Di中元素进行对比 （失效冗余检验和可执行性检验）的时间复杂度为nisi（state－Di集合包含的元素个数为si）；所有边与集合conditions中元素进行对比 （完整性检验）的时间复杂度为eici（conditions集合包含的元素个数为ci）。因此对于安全域Di中的策略进行验证的平均时间复杂度为O（ni＋ei＋nisi＋eici＋2／ni），对于系统全体策略进行验证的平均时间复杂度为

文献[4]中，针对所有策略主体和客体分别构建有向图，策略冲突验证的时间复杂度为O（｜V｜2／2＋｜V｜），当有向图的规模较大时，时间复杂度相当可观；本文中按照安全域对系统资源进行划分，对每个安全域分别构建有向图，虽然时间复杂度中也包含二次项O（nisi＋eici），但ni与ei的值由于安全域的划分明显减小，同时由于各个安全域彼此相互独立，因此本文的策略验证方法更利于在分布式系统中进行并发处理。

文献[6]中，一致性检验的时间复杂度为O（4n2），n为策略规则的数量。而本文中的策略验证复杂度在一致性方面表现为O（ni＋ei＋2／ni），ei代表某一个有向图中策略规则的数量。对于稠密的有向图而言，任意两个状态之间均有变迁，此时ei＝ni（ni－1）／2。对于中等稠密的有向图而言，ei接近于ni（ni－1）／4。则本文一致性检验的复杂度按照中密图的标准可转化为其中最高次项为。因此本文的一致性检验方法在理论上优于文献[6]中的一致性检验方法。

实验环境为Intel Core 2Duo，2GHz，2GRAM，windows7，Java语言，使用MySQL数据库存储安全策略和规则，对有向图采用深度优先搜索遍历。以一个安全域中的状态有向图作为研究对象，将有向图中的策略规则由40条逐步增加到400条，随着策略规则的增多，安全域中的状态数增多，对应的算法执行时间随之增加，如图3所示，总体执行效率比较理想。

图3 策略库验证算法执行结果

5 结束语

安全策略的合理性决定了网络信息系统的安全性，同时是安全设备协同工作的必要前提。本文根据子网划分安全域，定义了安全策略并根据状态机模型将安全策略规则用无环有向图进行描述，阐述了策略库的构建方法和通过深度优先遍历状态有向图的方式对特定安全域中的安全策略规则进行验证。本文介绍的策略验证方法不仅综合考虑并分析了策略的正确性、完整性、一致性、冗余性和可执行性几种情况，同时通过复杂度分析说明了本文验证方法相对于现有策略验证方法的优势。实验证明基于状态机模型的策略规则描述方法和策略库验证算法具有理想的执行速度，是有效可行的。

[1]Becker MY，Fournet C，Gorden AD.Design and semantics of a decentralized authorization language[C]／／Proc of the 20th IEEE Computer Security Foundations Symposium.Washington:IEEE Computer Society，2007.

[2]Gurevich Y，Neeman I.DKAL:Distributed Knowledge authorization language[C]／／Proc of the 21st IEEE Computer Security Foundations Symposium.Washington:IEEE Computer Society，2008.149－162.

[3]BAO Yibao，YIN Lihua，FANG Binxing，et al.Approach of security policy expression and verification based on well－founded semantic[J].Journal of Software，2012，23 （4）:912－927（in Chinese）.[包义保，殷丽华，方滨兴，等.基于良基语义的安全策略表达与验证方法[J]，软件学报，2012，23（4）:912－927.]

[4]YAO Jian，MAO Bing，XIE Li.A Dag－based security policy conflicts detection method[J].Journal of Computer Research and Development，2005，42 （7）:1108－1114 （in Chinese）.[姚键，茅兵，谢立.一种基于有向图模型的安全策略冲突检测方法[J].计 算机研究与发展，2005，42 （7）:1108－1114.]

[5]ZHANG Huan，CAO Wanhua，FENG Li，et al.A network security interaction policy model based on status transition[J].Ship Electric Engineering，2009，29 （3）:124－127 （in Chinese）.[张焕，曹万华，冯力，等.基于状态迁移的网络安全联动策略模型[J].船舶电子工程，2009，29 （3）:124－127.]

[6]TANG Chenghua，YU Shunzheng.Verifying network security policy based on features[J].Journal of Computer Research and Decelopment，2009，46 （11）:1854－1861 （in Chinese）.[唐成华，余顺争.基于特征的网络安全策略验证[J].计算机研究与发展，2009，46 （11）:1854－1861.]

[7]LIU Daobin，GUO Li，BAI Shuo.A methodology for analyzing security policy in workflow[J].Journal of Computer Research and Development，2008，45 （6）:967－973 （in Chinese）.[刘道斌，郭莉，白硕.一种工作流安全策略分析方法[J]，计算机研究与发展，2008，45 （6）:967－973.]

[8]TANG Chenghua.Research on key technologies of network security management policy[D].Beijing:Institute of Technology，2006:47－57 （in Chinese）.[唐成华.网络安全管理策略关键技术研究[D].北京:北京理工大学，2006:47－57.]

[9]LI Li，LI Zhiping，WANG Liang，et al.A finite－state machine model for strategy table search and match of standardized stability control device[J].Automation of Electric Power Systems，2012，36 （17）:86－89 （in Chinese）.[李力，李志平，王亮，等.稳定控制装置中策略搜索匹配状态机模型[J].电力系统自动化，2012，36 （17）:86－89.]

[10]ZANG Tianning，YUN Xiaochun，ZHANG Yongzheng，et al.A model of network device coordinative run[J].Chinese Journal of Computers，2011，34 （2）:216－228 （in Chinese）.[臧天宁，云晓春，张永铮，等.网络设备协同联动模型[J].计算机学报，2011，34 （2）:216－228.]

[11]TANG Chenghua，YAO Shuping，ZHANG Xiang，et al.Research on security policy in NSMP[J].Journal of Computer Research and Development，2006，43 （Suppl.）:430－436（in Chinese）.[唐成华，姚淑萍，张翔，等.网络安全综合监控平台中安全策略的研究[J].计算机研究与发展，2006，43 （增刊）:430－436.]