基于遗传算法的信息流安全标记自动化挖掘*

　　0.引言

　　分布式信息流模型具有分布式降密、授权传递和污点跟踪等特征，与传统的访问控制模型相比，可以更加灵活有效地控制信息的非法访问和直接、间接传播。目前典型的分布式信息流模型主要包括加、Asbestos、DStar和Flume等。然而，分布式信息流模型本身的灵活性，也使得应用这些模型来实施策略管理的复杂性急剧增加，严重制约着模型在实际系统中的应用。

　　在云计算等分布式系统中，往往面临着成百上千的用户和数以万计的安全实体，存在着复杂多样的安全需求，应用分布式信息流控制机制来表达系统安全需求，是一个极其复杂的问题。如何将需求转化为具体系统中安全实体的标记配置，需要深刻理解模型的本质和应用程序行为安全。安全策略的错误表达和配置，会造成权限滥用或不足，导致严重安全后果。

　　现有的策略自动化配置方法主要集中于针对RBAC模型的角色挖掘研宄。角色挖掘是指从当前系统用户权限分配关系中抽取满足应用需求的最优角色集，常用的角色挖掘方法包括层次聚类、概率模型、子集枚举、图论和逻辑编程等方法。面向分布式信息流模型的标记挖掘方法较少，文献针对多级安全系统提出了一种层次聚类和遗传算法相结合的方法实现访问控制策略的自动转化，但是不支持可信主体的安全级动态调整。文献[12]提出了一个自动化工具Swim，根据输入的类自然语言描述的安全需求，将C程序自动转化为无策略冲突的Flume程序版本。Swim需要深入分析程序内部的复杂结构，存在状态空间爆炸的问题。上述研宄为安全模型的策略的自动化配置提供了良好的思想，但是仍无法很好地满足分布式信息流控制的特点。

　　对此，本文首先设计了一种基于安全断言的高层策略描述语言，用于表达分布式系统安全需求。在此基础上形式化定义了信息流安全标记挖掘问题，将其转化为关于断言满足率、标签和能力个数的多目标优化问题，分析并证明该问题是一个NP完全问题。然后，提出了基于遗传算法的安全标记配置最优化方案。分析评估了影响算法效率的主要因素，实验结果表明，该算法可以有效挖掘出满足系统安全需求的最优解方案，提高了分布式信息流模型的可用性，大大减轻系统安全策略管理的负担。

　　1信息流安全策略描述语言

　　分布式信息流模型通常使用标签和标记跟踪和控制实体间的信息流动，标记是标签集的子集，根据子集的偏序关系，标记可形成一个格。实体e的标记分为机密性标记LSe和完整性标记LTe。每个信息所有者对其拥有的信息具有完全的控制权，拥有降密/提权等能力。实体e的能力包括添加能力CaeM和删除能力。分布式信息流模型具有较强的表达能力，然而对于系统安全管理员而言，直接应用模型实施策略管理较为困难，特别是在大规模环境中，手动人工配置每个实体的安全标记，几乎是不可能的。因此需要在底层的安全标记与高层的策略管理之间建立联系。

　　本节设计了一种面向分布式信息流模型(DistributedInformationFlowControl,DIFC)的安全策略描述语言，以安全断言的形式表达实体的安全需求，定义了信息流允许、信息流禁止和授权管理三类断言语句。其中前两类断言用于表达静态的信息流控制策略，即在特定条件下允许或禁止的实体间信息流动。授权管理断言表达分布式降密和权限传递等动态安全需求。

　　下面分别介绍三类断言语句的语法语义。

　（1）AlloWsource,sink,conditions,type)

　　断言Allow允许从实体source到实体sink的直接信息流动，前提是source和sink之间必须满足参数conditions规定的约束条件，如不存在利益冲突等。参数type指定该类断言的信息流保护类型，包括机密性和完整性两类。参数source和inA;可以被赋值为*，表示任意实体。参数可以被赋值为#，表示允许从source到sink的信息流，只要二者标记满足相应的支配关系，不存在特别的约束条件。当纖=*且conditions=#时，允许sink接收来自任意实体的信息。类似地，当sink=*且conditions=#时，允许source向任意实体发送信息。该类断言的语义如下。defAllow(A,B,R,type)=if她e=Secrecy,VrGR,(LSA-CdAel)C(LSBUCaBdd)八(|(LSAUCaAdd\JLSBUCaBdd)Hr|<l)eliftype=Integrity,VrGR,断言AUou(AB，litypx)成立，当且仅当实体A和B的标记和能力满足如下条件：（i)当type=Secrecy时，机密性保护允许信息从低密级实体A流向高密级实体B。（ii)当type=Integrity时，完整性保护允许信息从高完整级实体A流向低完整级实体B。(iii)实体A和B满足约束集R中定义的所有约束条件。

　　(2) Deny(source,sink,downgraders,type)

　　断言Deny禁止从实体source到实体sink的直接信息流动，除非source和sink之间存在特定的降密器，且从source到sink的信息流动通过了该降密器的处理。参数type指定该类断言的信息流保护类型，包括机密性和完整性两类。参数source和sink可以被赋值为*，表示任意实体。参数downgraders可以被赋值为中，表示source和sink之间不存在任何可用的降密器，禁止从scrnrce到sink的任意信息流。当scrnrce=*且downgraders=99时，禁止sink接收任意实体的信息。类似地，当sink=*且dowmgraders=p时，禁止scmrce向任意实体发送信息。该类断言的语义如下。defDeny(A,B,D,type)=iftype=Secrecy,\/d^D,^((LSA-Cd/)C(LSBUCaBdd))A(LSA-Cr)C(LSd\JC：dd)A(((LSa—Cf)ULSd)—Cd/)C(LSbUCr)eliftype=Integrity,\fdGD,(，((LIB-Cd/)Q(LIA\JCfd))A(LId-Cddd)C(LIAUCldd)HLIb-Cf)C(((LIaUCf1C：dd)

　　断言Den/jlA,B,J)成立，当且仅当实体4,5和\/deD的标记和能力满足如下条件：（1)机密性和完整性保护均禁止从4到B的直接信息流。(ii)机密性和完整性保护均允许从A到d的信息流；（iii)即使d己经接收了来自A的信息，机密性和完整性保护依然允许信息从d流向B。

　　(3) Actfor(granter,actor,kind)

　　断言Actfor表示实体granter可以将其能力和权限传递给实体actor，前提是granter和actor之间存在某种特定的信任关系，actor可以部分支配granter。参数kind指定某种特定的支配类型，如读支配、写支配等。参数granter可以被赋值为丄，表示可以被任意实体支配。参数actor可以被赋值为T，表示可以支配任意实体。该类断言的语义如下。deActfor(A,B,kind)

　　断言Acf/or(A,B,kind)成立，当且仅当4,B的标记和能力满足如下条件：（i)B的标记必须包含于4的当前标记调整范围，即4可以通过能力进行调整的标记范围。(ii)B的能力必须是4的对应能力的子集。

　　2 安全标记挖掘问题及复杂度分析

　　2.1 安全标记挖掘问题形式化定义

　　直观来看，安全标记最优化挖掘是指从满足系统安全需求的实体安全标记分配方案中找一个DIFC最优解。DIFC模型是信息流控制方案的集合，方案通常包括实体集、主动/被动实体标记和主动实体能力等安全要素，形式化定义如下。

　　定义1DIFC安全标记解方案。DIFC中每一个解方案对应一个多元组(E,TS,TI,LS,LI,C,尺)，其中E表示所有实体集，包括主动实体和被动实体。JS表示所有机密性标签集合，77表示所有完整性标签集合。LS-.E^2ts表示所有实体的机密性标记集合，LI..E—2ti表示所有实体的完整性标记集合，C-.E^2卿TIh㈣邮〗表示所有主动实体的能力，i?表示标签授权约束集。

　　定义2安全标记基本挖掘问题(BasicSecurityLabelsMiningProblem,BSLMP)。给定一个实体集为E的授权系统，

　　已存在一个表达系统安全需求的信息流控制安全断言集儿求满足.4的最优化DIFC解方案&使得S中标签个数(|T5UT/|)和降密/提权能力个数(|C|)最小化。

　　通过前面的DIFC策略语言应用示例可知，针对特定的系统安全需求，可以给出不同的实体标记及能力配置方案，即存在多个不同的解方案。安全标记的最优化挖掘问题是指从满足系统安全断言集的所有安全标记方案集中找一个最优解，该解需要的实体标签和能力个数最小，寻找最优解的目的在于最大程度的减小系统安全配置和管理负担，提高DIFC模型的可用性。

　　最优解要求准确完备地匹配系统所有安全断言集，以满足系统所要求的全部安全需求。然而，很多时候最优解的计算成本过大，尤其在云计算环境下，很多大规模的分布式应用存在复杂多样的安全需求，往往面临着成百上千的用户和数以万计的实体规模，涉及数十条甚至上百条安全断言。因此，有些时候，需要在较短的时间内求一个近似的最优解，在精确性和计算成本之间寻求一个较好的平衡。

　　定义3安全标记次优化挖掘问题(ApproximateSecurityLabelsMiningProblem,ASLMP)。给定一个实体集为E的授权系统，已存在一个表达系统安全需求的信息流控制安全断言集.4和一个阈值S，求一个可以义一致性满足.4的解方案*5，使得5中标签个数(\TSUTI\)和降密/提权能力个数(|C|)最小化。

　　义一致性，是指允许S不满足乂中断言个数的上界为5。显然，当5=0时，BSLMP问题是ASLMP问题的一个特例。5-—致性的概念有助于限定次优解的精确度，便于在有限的计算资源和和可接受的时间内找一个合理的解。

　　2.2 计算复杂度分析

　　BSLMP和ASLMP都属于多目标优化问题。由于NP问题理论适用于判定问题，因此，为了分析BSLMP和ASLMP问题的计算复杂性，首先定义该问题的判定版。

　　定义4BSLMP问题的判定版。给定一个实体集为E的授权系统，已存在一个表达系统安全需求的信息流控制安全断言集.4和两个正整数/i、v，判定是否存在一个最优化的DIFC解方案&使得S语义完备地满足儿且S中标签个数和降密/提权能力个数分别满足(\TSUTI\<M)和(|C\<v)。定理1:BSLMP问题是NP完全问题。

　　首先，证明BSLMPGNP。给定一个BSLMP的解，判断该解是否满足断言集.4中的所有断言，只需要对每一条断言涉及的实体，从该解中取其标记能力配置进行对比验证即可。显然这一过程可在多项式时间内完成，所以BSLMP是NP问题。

　　其次，证明Monotone3SAT<BSLMP.即Monotone3SAT~P

　　问题可在多项式时间内规约为BSLMP问题。Monotone3SAT问题的定义如下，给定一个有穷布尔变量集X={xvx2：...xl},\X\=l,每个变量取0或1，一组子句L=C,ACnA......AD，每个子句1 2 m 1 2 nCVD.是由三个变量组成的析取范式，q=xaVx.2Vx.3,D.=V，xj2V^x.z，判定是否存在一个X上的真值赋值使得L为真，该问题是一个公认的NP完全问题。针对每个子句C.，添加三个实体£：,<,<到实体集£中，同时添加一个断言Uenj/he^e^secy'eq/J到断言集中。假定LS(e])={ ，%，ta，ta，t3eTS},C(e：)={},LS(e^)={},C(e^)={(广,t:1,,，t:}。针对每个子句D]，添加两个实体e，e.，同时添加一个断言secrecj到断言集W中。假定L5,(ei)={l1,^2,^3},<7(e3)={}。令p和"为co，显然，构造上述BSLMP问题实例可以在多项式时间内完成。

　　最后，证明上述BSLMP实例是可满足的，当且仅当Monotone3SAT实例是可满足的。一方面，如果存在一个真值赋值使得Monotone3SAT实例L为真，令所有为真的变量构成集合X’={:ci：p:ci2，...，:ciT}。显然，对于每个子句Ct=xsV ::为真，X’至少包含2:tl,:ri2,:ri3中的一个；对于每个子句Dj=~^xnV~^xj2V~^xj3为真，X’至多包含中的两个。相应地，令歸)={L4...AJ,C,(e)={},则上述.4中的每条断言都成立，即BSLMP实例是可满足的。

　　另一方面，如果BSLMP实例为真，即X中的每条断言都为真，LS(e)={tkVtk2,...,tkr},(7(e)={}。显然，对于每个断言Deny(e,e1,e2,secrecy)为真，LS(e)至少包含t.n,ta,t'i3中的一个；对于每个断言(^secrecy)为真，LS(e)至多包含ta,ti2,ti3中的两个。相应地，令集合中的所有变量都为真，则i中的每个子句都为真，即Monotone3SAT实例是可满足的。

　　综上所述可知，BSLMP问题是NP完全问题，得证。定理2：ASLMP问题是NP完全问题。证明：由于当5=0时，BSLMP问题是ASLMP问题的一个特例，因此，定理2的证明与定理1类似，此处不再重复。

　　3 基于遗传算法的标记挖掘问题求解

　　本节采用遗传算法(geneticalgorithm,GA)求解上述问题。遗传算法是一种自适应的全局优化概率搜索算法，基于对生物在自然界中生物遗传与进化机理的模拟，常用于解决大型复杂非线性系统的全局优化问题。遗传算法首先确定问题的一个候选种群，然后通过遗传操作算子不断淘汰适应度较低的个体。由于适应度较高的个体遗传到下一代种群中的概率较大，因此，随着进化过程的不断进行，最终可搜索到问题的最优解。基于遗传算法的ASLMP问题的具体求解过程如下：

　　(1) 用染色体表示候选的DIFC解方案。遗传算法中通过编码形式建立从问题空间表现型到遗传空间基因型的映射关系，每个解方案对应一条染色体。常见的编码方法分为二进制、浮点、符号编码等，本文采用二进制编码。将每个实体ee五分配的标记和能力看成染色体上的基因，这样每个基因就是一个四元组(LSe,LIe,C广,Cd；U)，每一元都是一个二进制位串。

　　(2) 种群初始化。遗传算法作用于包含多个个体的种群，因此需要产生一个初始种群作为初始解集合进行搜索，初始种群的规模大小直接影响算法的搜索效率和最优解的产生结果，本文通过随机方式产生初始种群。为确保种群的多样性，初始种群的规模可针对不同的应用实例动态调整，种群规模过小，容易导致遗传算法过早收敛，规模过大，易造成计算代价太高耗费资源过多。

　　(3) 适应度评价函数。适应度fitness用于度量种群中每个个体在优化计算中有接近于最优解的优良程度，反应了个体的

　　适应生存能力。适应度高的个体遗传到下一代的概率较大，反之较小。这里定义fitness(s)=w_fT(s)+(s)+w丨J「(s).fitness(s)越大表示种群S1中的个体s越优。其中，fT(s)=(\A\-r)/|2|，ts对应解方案s中不满足4的断言个数，/T(S)解表示S的断言满足率；/；i(s)=l/Ms,"s对应S中的标签个数；fr(s、=l/'，'对应S中的降密/提权能力个数；W、W、W分别对应各自的

T fu. U权重，KI+W+W=1,共同决定算法朝不同的方向优化搜索。T !_1 Vfitness采用权重系数变换法将多目标优化问题转化为单目标优化问题，通过评价解方案在标签和降密/提权能力个数等方面的综合表现，寻求一个整体较优的结果。

　　(4) 遗传算子。遗传算法最优解的迭代搜索过程中，采用选择、交叉、变异三种基本遗传算子对种群进行操作。

　　选择是从当前种群中选取适应度较高的优良个体，并将其以更大的概率复制遗传到下一代种群中。本文采用轮盘赌选择(roulettewheelselection)与最优个体保存策略相结合的方法作为选择算子，即当前种群中适应度最高的个体不参与交叉和变异运算，而是直接复制到下一代种群中，以提高算法的收敛速

　　度。从父代种群中选择个体气遗传至下一代种群的概率ph.)=fitness(st)/'^2l^—ifitness(sj)，每个个体st的轮盘刻度对应的累积概率为。生成(0，1]之间的随机数x与g(st)进行比较决定选择的个体，若gis")<x<g(st),则选择个体气。重复n轮，产生n个子代个体。

　　交叉是指两个父代染色体按某种方式相互交换部分基因从而形成新个体的操作，交叉算子决定算法的全局搜索能力。采用均匀交叉算法，即两个配对个体的每个基因都以等概率进行交换。实际算法实现过程中随机产生一个与染色体基因位串等长的屏蔽字，两个父代染色体基因位对的交叉取决于屏蔽字中等位的取值。

　　变异是产生新个体的一种辅助方法，允许父代个体的基因编码产生随机的小变化。采用基本位变异算法，即以小概率从种群中选择一个或多个染色体，随机选择被选中染色体的某些基因位作为变异点，并在标记允许的范围内取一个随机数进行替换。变异算子的引入有助于维持种群的多样性，和提高遗传算法的局部搜索能力。

　　(5)终止条件。算法到达指定遗传代数后，检查种群中的最优染色体，是否达到预期的适应度值，即是否已取得最优解决方案。若是，则算法终止；否则重新启动遗传算法再次进行搜索。

　　下面给出ASLMP问题的遗传算法详细求解过程，如算法1所示。

　　算法1ASLMP问题的遗传算法求解输入:A:安全断言集;S:DIFC候选解方案构成的种群；|E|:实体个数；　n: 染色体（解方案）个数；G:进化的最大代数；r:交叉取代成员的比例 k:变异率；W,W,W代表权重。T7(J,7V输出：sbest为ASLMP的近似最优解。

　　算法复杂度分析初始化种群P的时间复杂度是0{\A\|五.|n。计算个体适应度的时间复杂度是0(n-\A\),计算染色体选择、交叉和变异的时间复杂度是0((1+r+A:).n.|五|.|A|)。因此，算法1的计算复杂度是|朴|五|)。

　　4实验评估

　　本节首先测试算法在不同规模下的正确性与精度，然后验证不同的运行参数对算法性能的影响。通过基于C++语言实现的遗传算法对ASLMP进行求解，实验软硬件环境为：处理器IntelXeonX5650CPU(32核），内存32G;操作系统RedHatEnterpriseLinuxServer6.4，64位内核6.x86_64，编译器gcc4.4.7。

　　为了综合评估算法的效率及解的质量，本节基于多组随机生成的实体集E和断言集尤构造不同规模下的测试用例，进行仿真实验。设定算法运行参数，w=0.8、w=0.1、w=0.1,T VG=1000，r=0.8，k=0.05，实验结果如表1所示。其中，t表示对同等规模测试用例进行多轮测试的算法平均计算时间，I、I、I分别表示算法所求次优解的断言不满足个数均值、标签个数均值及降密/提权能力个数均值，fitness表示次优解的平均适应度。

　　实验结果表明，算法在小规模环境下能较快挖掘到最优解，且时间开销为秒级。而在大规模环境下，算法依然可以有效的求解出适应度较高的次优解。随着问题输入规模叫和冏的不断增加，次优解的适应度均值呈减小的趋势，算法的平均计算时间T显著增加。fitness的减小是由于算法的搜索空间变大，选择压力变大造成种群的过早收敛，导致解的质量出现略微降低。另一方面，F的增加是由于适应度计算过程中计算候选解的断言满足率时间开销增加导致。

　　下面进一步分析关键参数种群规模《对算法性能的影响。设置参数[4|=60,\E\=20,G=500,r=0.8,k=0.05,WT=0.8,iv^=0.1,'=0.1，结果如图1所示。从图1(a)可知，算法的运行时间与《的规模近似成线性正比，这是由于种群规模变大，造成染色体选择、交叉和变异计算时间增加所导致。而图1(b)中，适应度随《的增长缓慢增加最终趋于平稳，说明次优解的质量有所提升。因此，实践中应选择一个较好的平衡点，取得运算速度和适应度都适合的次优解。

　　5结束语

　　分布式信息流模型所具有的分布式降密、授权传递等特点，使其能够提供灵活细粒度地信息流控制，但是同时也不可避免地增加了系统安全需求表达和策略管理的复杂性。对此，本文提出了面向分布式信息流模型的高层策略描述语言，定义了用于表达系统安全需求的安全断言的语法和语义。形式化定义了信息流安全标记挖掘问题，并详细分析了问题的复杂度。提出了基于遗传算法的方法进行求解。实验结果表明，该算法可以在有效时间内挖掘出最优化的安全标记配置方案，减轻了分布式系统安全策略管理的复杂度。安全标记最优化挖掘的效率。