（计算机应用技术专业论文）rtr系统中面向风险评估的最优证书链查找.pdf

浙江大学硕士学位论文摘要 摘要 基于角色的信任委托管理系统是分布式证书管理系统中一个重要的授权管 理解决方案，也是计算机安全领域的研究热点。信任委托管理系统的一个重要功 能是授权查询，即一个实体是否拥有一个角色。怎样高效准确地查找一条证书链 成为信任委托管理系统的核心问题。然而，现有的信任委托管理系统和证书链查 找算法中，所有证书都是被一视同仁，即一个证书要么存在要么不存在，只有这 两种状态，而这种粗粒度的信任表达显然无法描述现实中的信任关系。 本论文首先介绍面向风险评估的信任委托管理系统( r t 8 系统) ，即每个证书 都附加一个风险值，表示依赖该证书所需要承担的风险。随后本论文在r t 8 系统 上设计最优证书链查找算法( o c c d ) ，来解决r t r 系统中的证书链查找问题。 最优证书链查找算法可以在r t r 系统中查找从给定实体到给定角色的最优路 径，即累计风险值最低的路径。并且该算法有多项式的时间复杂度( o ( n 4 ) ) 和 多项式的空间复杂度( o ( n 4 ) ) 保证，其中为信任委托管理系统中证书总数。 最优证书链查找算法是基于l i 等人所提出的证书链查找算法框架，引入了 优先队列等新的数据结构来解决最优风险路径问题。该算法用优先队列和对算法 框架的相应调整来保证每次得到的都是新的一条最优路径，并且记录处理过的节 点，避免重复处理来保证多项式的时空复杂度。 关键词：基于角色的信任委托管理系统，风险评估，最优证书链查找 浙江大学硕士学位论文 a b s t r a c t r o le b a s e dt r u s tm a n a g e m e n ts y s t e m ( r b t m ) isa ne f f e c tiv ew a yt o a u t h o r i z a t i o ns o l u t i o ni nd i s t r i b u t e dc r e d e n t i a lm a n a g e m e n ts y s t e m ，a n d i sah o tf i e l di nc o m p u t e rs e c u r i t y o n eo ft h ei m p o r t a n tf u n c t i o n a li t i e s o fr b t mi st od i s c o v e rac r e d e n t i a lc h a i nf r o mg i v e ne n t i t yt ot h eg i v e n r o l e h o wt od i s c o v e rs u c hc r e d e n t i a lc h a i nc o r r e c t l ya n de f f i c i e n t l yi s t h ec o r ep r o b l e mi nr b t m y e tt h ee x i s t i n gr b t m m o d e l sa n dc r e d e n t i a lc h a i n d i s c o v e r ya l g o r i t h m sd on o td i f f e r e n t i a t ea l lt h ec r e d e n t i a l s ，a c r e d e n t i a lo n l yc o u l dh a v et w os t a t e s ，t h a te i t h e re x i s t si nt h ec r e d e n t i a l s y s t e mo rn o t t h i si sc l e a r l yi n s u f f i c i e n tt op r e c i s e l yd e s c r i b e r e l a t i o n s h i pi nr e a l i t y i nt h i sp a p e r ，w ef i r s ti n t r o d u c er o l e b a s e dt r u s tm a n a g e m e n ts y s t e m w i t hr i s ka s s e s s m e n t ( r t 8s y s t e m ) ，i e e v e r yc r e d e n ti a lisa t t a c h e dw i t h ar i s kv a l u et h a ti n d i c a t e st h er i s ko n eb e a r sw h e nh e s h et r u s t sa n dr e l i e s o nt h ec r e d e n t i a l a n dt h e nw ed e s i g na no p t i m a lc r e d e n t i a lc h a i nd i s c o v e r y a l g o r i t h m ( o c c d ) t os o l v et h ec r e d e n t i a lc h a i nd i s c o v e r yp r o b l e mi nr t 2 t h eo c c da l g o r i t h mc o u l df i n da no p t i m a lc r e d e n t i a lc h a i nc o n n e c t i n g t h eg i v e ne n t i t yt ot h eg i v e nr o l e ，w i t h1 e a s tp o s s i b l ea c c u m u l a t e dr i s k w h a t sm o r e ，i tc o u l dg u a r a n t e ep o l y n o m i a lt i m ea n ds p a c ec o m p l e x i t y ， o ( n 4 ) a n do ( n 4 ) r e s p e c t i v e l y ，w h e r eni st h et o t a ln u m b e r o f c r e d e n t i a l si nr t 8 t h ea l g o r it h misb a s e do nt h ec r e d e n ti a lc h a i nd is c o v e r yf r a m e w o r k i n t r o d u c e db yl i ，e ta l ，a n di n t r o d u c e ss o m eo t h e rd a t as t r u c t u r e s ，s u c h a sp r i o r i t yq u e u e ，t os o l v et h eo p t i m a lr i s kp a t hp r o b l e m i ne a c hs t e p ， t h ea l g o r i t h mc o u l do b t a i nan e wo p t i m a lp a t h ，u s i n gp r i o r it yq u e u ea n d 浙江大学硕士学位论文 w it hs o m e n e c e s s a r ya d j u s t m e n tt ot h ea b o v ef r a m e w o r k a n da l s ot h e a l g o r i t h mk e e p st r a c ko fa 1 1t h ev i s i t e dr o l ee x p r e s s i o n sa n dc r e d e n t i a l s t oa v o i dr e d u n d a n tp r o c e s s ，b yh o wi tg u a r a n t e e st h ep o l y n o m i a lt i m ea n d s p a c ec o m p l e x it y k e y w o r d s ： r o l e b a s e dt r u s tm a n a g e m e n t ，r is ka s s e s s m e n t ，o p ti m a l c r e d e n ti a lc h a ind is c o v e r y 浙江大学硕士学位论文 图目录 图目录 图5 1 用d c g a 算法生成的数据测试时间效率4 3 图5 2 用d c g a 算法生成的数据测试空问效率4 4 图5 3 用时| 日j 最坏情况数据测试时间效率4 5 图5 4 用空间最坏情况数据测试空间效率4 7 i i i 浙江大学硕士学位论文表目录 表目录 表3 1 算法核心数据结构2 3 表5 1d c g a 算法的参数列表3 8 表5 2d c g a 算法随机数据生成参数配置4 0 表5 3d c g a 算法随机生成数据特性4 0 表5 4 考察时间复杂度的证书集合属性4 l 表5 5 考察空间复杂度的证书集合属性4 2 i v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人存导师指导下进行的研究工作及取得的 研究成果。除丫文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝选太堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已存论文 中作了明确的说明并表示谢意。 学位论文作者签名：三忆知炙 签字日期：2u 。p年月扩日 学位论文版权使用授权书 本学位论文作者完全了解浙江太堂有权保留并向国家有关部门或机构 送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝堑太堂可 以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：右羟炙 导师签名： 签字u 期：0 ，u 猝 月pl i 签字口期： 1m 。孑年6 月 浙江大学硕士学位论文 第1 章绪论 第1 章绪论 1 1 背景 随着互联网的高速发展，软件系统的形态发生了根本性的转变。从早期的网 络服务到w e b 服务，进而发展到智能w e b 服务，软件系统正从面向封闭的、熟 识的用户群体和相对静止的形式向开放的、公共可访问的和高度动态的服务模式 转变。这种转变使得开放式环境下的应用系统的安全分析复杂化，同时使许多基 于传统软件系统形态的安全技术和手段，尤其是安全授权机制，如访问控制和一 些传统的公钥证书体系等，不再适用于解决开放式环境下的安全问题，传统的访 问控制技术面临着更大的安全挑战。基于角色的信任委托管理方案【l 】是开放式环 境诸多信任证管理方法【2 3 4 】中的一个比较有效的解决方案，它结合了基于角色的 访问控制【5 】和信任委托管理逻辑【6 1 ，使用易于表达的信任委托管理逻辑来描述基 于角色的访问控制【7 】，目前被学术界广泛的关注和研究。l i 等人首先提出了基于 角色的信任委托管理模型【8 】，并且提出了一个在该模型上的证书链查找算法框架 【9 1 。证书链查找算法解决了在信任管理模型中的一个重要问题，即授权查询问题。 信任委托管理系统中授权查询问题是给定一个实体和一个角色，判断该实体是否 拥有该角色，即在证书图上是否存在从该实体出发到该角色的一条可行路径。 然而，现有的信任委托管理系统中，所有证书都是被一视同仁的，即一个证 书要么存在要么不存在，只有这两种状态。从信任的角度来说，这表明证书颁布 机构，要么完全信任证书的所有人，要么完全不信任证书所有人，而这种粗粒度 的信任表达显然无法描述现实中的信任关系。基于上述考虑，c h a p i n 等人在已有 的信任委托管理技术的基础上，提出了证书风险评估的概念【l0 1 ，即每个证书都附 加一个风险值，表示依赖该证书所需要承担的风险。c h a p i n 等人并没有明确指定 风险值实际上该表示什么含义，也没有提出风险值该如何得到，而是把风险值的 意义作为一种可根据实际需要，作为可配置的参数。此外，c h a p i n 等人把面向风 险评估的信任委托管理系统称为r t r 系统，并且也构想了一个在该系统上的证书 浙江大学硕士学位论文第l 章绪论 链查找方法。但是该方法只是在“等人的方法【9 】基础上简单引入风险概念，并没 有为新的问题做专门的设计，导致该算法的时间复杂度为指数级别，在实际应用 中因为效率瓶劲而很难实用，无法达到在大规模证书集合中进行最优证书链查找 的性能要求。 针对上述挑战，本论文基于经典的证书链查找框架【9 】，设计了一个r t r 系统 中最优证书链查找算法。 给定一个面向风险评估的证书集合以及一个角色和一个实体，最优证书链查 找算法可以在多项式的时间和空问复杂度内找出一条从该实体出发到该角色的 累计风险值最小的证书链。l i 等人提出的证书链查找算法只判断证书存在与否两 种状态，不适用于r t r 系统，无法在面向风险评估的证书集合上找出累计风险值 最小的证书链。最优证书链查找算法有效地解决了在r t r 系统中的证书链查找问 题。设证书集合中证书总数为，则该算法的时间复杂度和空间复杂度分别为 d ( 4 ) 和o ( n 4 ) 。该算法跟c h a p i n 等人构想的指数级别时间复杂度的算法比起， 在时间复杂度上有了质的改进。 在绝大多数的现实情况中，证书链查找过程中实际处理的状态不会达到 o ( n 4 ) 的时间空间复杂度极限，所以本算法依然可以解决大部分大规模证书集合 场合的应用。但单从复杂度的角度考虑，o ( n 4 ) 的复杂度依然相对过高，可以再 进一步进行优化。因为不考虑风险评估的普通证书链查找算法的时间复杂度已用 下推自动机等各种形式化的方法证明其时间复杂度的理论下限为o ( n 3 ) ，单从时 间复杂度上的优化变得非常困难，甚至几乎不可能。所以可以考虑引入启发式的 方法，尽量避免o ( n 4 ) 复杂度最坏情况的出现。 本文的结构如下，第二章介绍了算法设计和正确性证明所需要的一些基本理 论，包括基于角色的信任委托管理系统概念，证书的风险，r t r 系统等。第三章 设计了最优证书链查找算法，给出了伪代码以及相应说明。第四章中对算法进行 了分析，分析其正确性以及时间空间复杂度。第五章用三种不同种类的数据，每 个种类用1 0 种不同的规模对本论文设计的最优证书链查找算法和c h a p i n 等人的 6 浙江大学硕士学位论文第1 章绪论 算法进行了效率比较测试。 1 2 本章小结 信任委托管理是计算机安全领域的热点问题之一。本章首先简要介绍了该领 域现状，r b t m 系统的相关基础理论。然后分析了向r b t m 系统引入风险评估概 念的必要性，以及提出了i 盯r 系统中最优证书链查找问题。最后介绍了本论文的 概况。 7 浙江大学硕士学位论文 第2 章信任委托管理系统 第2 章信任委托管理系统 2 1 基于角色的信任委托管理系统 2 1 1r b t m 系统简介 基于角色的信任委托管理系统( r o l e b a s e dt r u s tm a n a g e m e n ts y s t e m ，简称 r b t m 系统) 首先由“等人提出【1 6 】。r b t m 系统结合了基于角色的访问控制 ( r o l e b a s e da c c e s sc o n t r 0 1 ) 1 5 j 和信任委托管理逻辑( t r u s tm a n a g e m e n tl o g i c ) ， 使得用易于表达的信任委托管理逻辑来描述基于角色的访问控制。并且r b t m 系 统的具体实现技术也相对较成剥6 1 ，还可以有效解决证书分布式存放的问题【1 1 1 。 这些特性使r b t m 系统成为最成熟的信任委托管理系统，是继续研究证书风险评 估的一个最佳奠基石。 r b t m 系统实际上是一系列信任委托管理系统的总和，统指所有可以从r t o 【9 】 系统演变得到的信任委托管理系统。r t r 【1 川就是其中一个变种，它在r t o 的基础 上用形式化的方式引入了风险评估的概念，即每个证书都有一个风险值r 。 2 1 2r b t m 系统语法 实体( e n t i t y ) 和角色( r o l e ) 是r t o 系统的基本单位。 实体也被称为责任人，它可以发行证书，r t o 系统假设每个证书的发行者都 是可以确定的。一个证书的发行者可以用公钥私钥方法进行确认。比如在某些应 用场合中，一个实体可以是一个私钥，也可以是一个用户帐号。在本论文中我们 使用a ，ec ，d 等大写字母来表示一个实体，有时候这些字母还会带有下标。在r t 0 系统中，角色名称是一个标识符，我们用，来表示一个角色，后面可以跟下标来 表示不同的角色名称。 在r t o 系统中一个角色是一个实体后跟一个角色名称，中间用点隔开，比如 a ，b r ，等。角色的概念是r t o 系统的核心。在r t o 系统中，一个角色定义一个 所有以拥有这个角色的实体构成的集合。比如一个实体a ，他有权限决定哪些实 体拥有彳，这个角色。一个角色也可以当作一个属性，一个实体当且仅当拥有一 8 浙江大学硕士学位论文 第2 章信任委托管理系统 个角色的时候，这个实体是该角色所定义的实体集合中的一个元素。比如z i u 代 表浙江大学实体，s t u d e n t 代表学生角色名称，z u s t u d e n t 可以被视为一种角色， 即以所有浙江大学学生组成的一个集合，也可以被视为一个学生可以拥有的一种 属性。在r t o 系统中访问控制也用一个角色来表示。比如允许写文件的权限可以 用f i l e w r i t e 角色来表示。 在r t o 系统中一个证书( c r e d e n t i a l ) 有如下四类形式的定义【9 l = 第一类证书：彳，卜b 其中a 和b 为实体，为角色名称。彳和b 可以为相同的实体。 这个证书表明彳把b 声明为a 的，角色的成员，即b m e m b e r s ( , 4 ，) 。其中 m e m b e r s ( , 4 一表示以所有拥有a ，角色的实体组成的实体集合。从属性的角度 描述，则该证书可以被理解为b 拥有a ，属性，或者彳声明b 拥有，属性。 第二类证书：么，卜曰z 其中彳和b 为实体，和，为角色名称。a 和b 可以为相同的实体，和，j 也可以为相同的角色名称。 该证书表示彳声明它的角色，拥有所有b 的n 角色的成员，即 m e m b e r s ( , 4 ，) 2m e m b e r s ( b r 1 ) 。因为所有b r l 的成员都是彳，的成员，所以 所有b r ，的成员同时拥有4 ，成员所具有的所有权限，所以从某种意义上该 证书定义b r ，为比彳，更强大的角色。这类证书可以用在基于角色的访问控 制( r o l e b a s e da c c e s sc o n t r o l ，简称r b a c ) 【5 1 中定义角色层次。从属性的 角度理解该证书，则为如果b 声明一个实体拥有，角色，则a 声明该实体拥 有，角色。特别如果，和，j 为相同的角色名称时，该证书表示a 把，的权限 委托给b 。 第三类证书：彳，- 卜彳以一 其中a 为实体，、，、n 为角色名称。我们称彳，厂2 为连接角色( 1 i n k e dr o l e ) 。 该证书表示坍p m 6 p 船( 4 厂) 2 所p 聊6 p 船( 月吒) ，即u 艇，。施。( 舢) m e m b e r s ( b s z ) 。 从属性的角度理解该证书，如果彳声明b 有，属性并且b 声明d 有厂2 属性， 9 浙江大学硕士学位论文第2 章信任委托管理系统 则a 声明d 有，属性。特别如果，和厂2 为相同角色名称时，该证书表示a 把 ，角色的权限委托给任何彳声明拥有，角色的实体。这是基于角色的委托， 即彳把，2 权限委托给另外一个实体b ，但并不关心实体b 本身的身份，只是 因为b 拥有权限，。 第四类证书：彳，卜石n 石n 石n 以 其中4 为实体，k 是一个正整数，( 【1 七】) 可以为角色或者以a 开头的连 接角色。我们称石r 、正n 石r 、五为交叉角色。 该证书表示m e m b e r s ( a 厂) 2 ( m e m b e r s ( f i ) n nm e m b e r s ( f k ) ) 。 角色表达式( r o l e e x p r e s s i o n ) 是指实体、角色、连接角色或者交叉角色，我 们用e 、e 卜e 2 等来表示角色表达式。r t o 系统中所有证书都是彳厂卜p 的形式， 其中e 为角色表达式。该证书表示m e m b e r s ( a ，) m e m b e r s ( e ) ，我们称为该证书 定义角色彳 其中么为证书的发布方，e 为主题，所有在角色表达式e 中涉及过 的实体为证书的接受方。 2 2 证书的风险 2 2 1 风险的概念 大多数信任委托管理系统把所有证书都一视同仁，即所有证书的可信度都是 一样的。在这些系统中一个证书只有两种状态，即要么存在于证书集合中，要么 不存在。虽然用密码学的技术可以一定程度上保证证书的可信度，但现实中证书 并不止简单的存在与否两种状态，而是有一个风险属性( r i s k ) 。比如有些实体相 对其他实体不够可靠，他们发布的证书，虽然是存在于证书集合中，但是没有其 他的实体发布的证书可靠；还有些证书，在分布式存放的证书系统中相对其他证 书较难得到，影响证书链查找算法的实际效率。另外，在实际的应用中，查找一 条证书链也并不只是拿这样一条路径的存在与否作为标准，而是需要指定一个风 险上限，需要找出一条不超过这个风险的证书链。 l o 浙江大学硕士学位论文 第2 章信任委托管理系统 2 2 2 证书风险值的估算 证书的风险值可以是一个实数，也可以是一个阶梯性的枚举常量( 比如高、 中、低) 。在本论文中我们统一使用【o ，1 】的实数来表示一个证书的原始风险值。 其他的风险值都可以用某种映射方法来转换到这个定义域里，只用【0 ，1 】的实数来 表示证书的原始风险值跟其他的风险值表现方法有着同样的表达能力。比如以 高、中、低表示的证书风险值，可以分别用1 ，0 5 ，0 来表示。 证书的风险值除了表示信赖一个证书所需要承担的风险之外，还可以用于表 示各种不同的含义，它可以用于表示一个证书的可信赖程度( t r u s t w o r t h i n e s s ) ， 也可以用于表示得到该证书所需要的计算开销( c o m p u t a t i o n a lc o s t ) ，或者其他根 据具体应用场合所需要的含义。证书风险值的估算也应根据该风险值所代表的含 义，用相应的方法进行估算。 证书的风险值最原始的含义是表示信赖一个证书所需要承担的风险程度。比 如浙江大学( 刀u ) 声明a 为自己的学生( s t u d e n t ) ，则浙江大学会发布一个证书 z u j t u d e n t 卜a 。但是发布这个证书，z j u 需要承担一定的后果风险，比如彳 会用自己浙江大学学生的身份去做一些刀u 并不希望看到的事情，所以刀u 发布 该证书的同时需要承担一定的风险。该风险值可以根据s t u d e n t 角色的社会用途以 及彳学生的个人品德等参数综合算出。如果s t u d e n t 角色社会威望很高，可以凭 着这个身份做很多事情，那么z j u 所承担的风险也越高；如果彳学生品德越好， 则z 彤所承担的风险也越低。 风险值可以用于表示证书的可信赖程度。证书的可信赖程度表示一个证书的 真假与否程度。虽然密码学技术可以一定程度上保证证书的真实性，但是也并不 能提供绝对的可信度，而根据使用的加密或数字签名技术有着不同的可信赖程 度。比如用凯撒密码( c a e s a rc i p h e r ) 加密的证书可信度相当低，因为容易破解 并且伪造一个假证书；相反用m d 5 1 1 2 1 签名的证书可信度相对较高，但还是达不 到绝对的可信度【l3 1 。可信赖程度除了受发布证书本身的技术影响之外，还受证书 发布方权威的影响。比如浙江大学( z ，u ) 声明a 为自己学生( s t u d e n t ) ，则因为 z j u 是相对威望较高的实体，证书z j u 。s t u d e m + - - a 的可信赖程度也较高，相反一 浙江大学硕士学位论文第2 章信任委托管理系统 个小工厂( 尉c 兀墉】，) 声明b 为自己工人( w o r k e r ) ，则因为尉c 兀砍y 是相对没 有威望的实体，证书f a c t o r y w o r k e r 卜b 的可信赖程度也较低。 风险值也可以用于表示得到证书所需要的计算开销。在实际应用中并不是所 有证书都是集中式地存放在同一个地方，而大多数情况是分布式地存放在不同节 点上，比如所有证书都存放在该证书的发布方节点上。不同节点所提供的证书查 询服务不同，提供服务能力也有差别，所以得到不同的证书所需要的时间开销也 是不同的。比如请求浙江大学一个证书，如果浙江大学有强劲的服务系统来处理 该类请求，则从浙江大学得到一个证书所需要的计算开销相对较少；相反请求一 个小公司，如果该公司都是人工处理该类请求，则得到证书所需要等待的时间相 对较长，得到该证书所需要的计算开销相对较大。 2 3r t 2 系统 2 3 1r 1 r r 系统语法 因为证书是信任委托系统最根本的单位，r t r 系统的基础也是给每个证书都 赋一个风险值。所以在r t r 系统中证书为如下形式： a r 上 其中k 为该证书的风险值。至于k 的具体计算方法，在2 2 2 节中有简要介绍， 这里不再展开。在实际应用中k 一般是由管理该证书的机构事先给出。 从集合的角度解释，则r t r 系统将给每个a ，的实体成员附加一个风险值k 。 所以m e m b e r s ( a ，) 的意义也变为以( b ，k ) 形式的成员组成的有限集合。需要注意 的是一个实体在一个角色实体集合中出现多次，即可能存在( a ，与) m e m b e r s ( a y ) 并且( 4 ，乞) m e m b e r s ( a ，) ，其中毛屯。不过在证书链查找过程中，我们可以始 终选择风险更小的证书进行扩张，而不需要风险更大的证书，即在同样的证书不 同的风险值下可以用风险值最小的证书来代表其他所有证书。如果我们用c 表示 一个证书集合，这个特性可以表示为： c u ( 彳，k 1 ) ，( 彳，k 2 ) = c u ( 彳，k 1 ) ) ，毛乞 浙江大学硕十学位论文第2 章信任委托管理系统 如果一个证书集合c 中不存在两个只有风险值不同的证书，即不存在 ( a ，k 。) ，( 彳，k ：) c ( 其中毛k 2 ) ，则我们称这种证书集合为规范的证书集合。可 以知道任何以等价的证书集合组成的集合中，都有唯一一个规范的证书集合。 证书的风险值不需要是个数值，但它需要满足两个条件。 首先风险值要可比较。任何两个风险值k ，和幻都应该可以比较出大小，即 毛k 2 要么为真，要么为假。实际上证书的风险值定义域应是个良序集合。在本 论文中我们都使用实数集合作为证书风险值定义域，所以满足可比较条件。 我们还需要在证书风险值的定义域上定义一个结合运算： f ( c ，七) = ( 彳，厂( j | ，七) ) l ( a ，k ) c ) 厂( c l ，c 2 ) = ( 彳，f ( k 1 ，k 2 ) ) i ( a ，k 。) ，( 彳，k 2 ) c i c 2 ) 该运算需要满足交换律和结合律，并且在定义域上单调递增，即要在所有定 义域内始终满足下列不等式： 交换律：f ( a ，b ) = 厂( 6 ，a ) 结合律：f ( f ( a ，6 ) ，c ) = f ( a ，f ( b ，c ) ) 单调递增：如果b b 则f ( a ，b ) f ( a ，b ) 此外因为两个证书的风险值结合运算结果是表示同时承担两个证书风险的 时候所承担的风险值，所以结果风险值自然不能反而小于两个证书单独的风险 值，即需要满足： a f ( a ，6 ) kb f ( a ，6 ) 2 3 2r t r 系统实例 在本实例中，我们用【0 ，1 】的实数表示证书的风险值。并且证书风险值的结合 运算采用： l ( 口，6 ) ： ：， p ， w h e r e ( a 6 ) w h e r e ( 口 6 ) 假设有一家超市m 给该超市的贵宾( v i p ) 以及某几个大学( u n i v e r s i t y ) 的 学生( s t u d e n t ) 提供打折优惠( d i s c o u n t ) ，其中一个大学有u ，s 为该学校一位 塑望奎兰堡主兰垡笙茎墨! 兰笪堡重堑笪型至竺 学生。该场景用r t r 系统语言可以表示为： c l jm d i s c o u n t 卜也m 1 ，驷 cjm d i s c o u n t 卜生旦lm z m i v e r s i t y j t u d e n t c 3 jm j u n i v e r s i t y 卜吐u gju s t u d e n t 卜生：坠一s 根据证书a 知s 为【，的学生，根据。知u 为m 所认可的大学，根据c 2 知 m 所认可的大学所有学生都可以得到m 的打折优惠，所以s 通过a ，g ，c 2 三 个证书，可以从m 得到打折优惠。这条证书链的累计风险值为： k 删= l ( 忌。，毛，k 2 ) = 0 2 即m 承担k 刎= 0 2 的风险给s 提供打折优惠。当查询s 是否具有m 的打折 优惠资格，如果风险值的上限是大于等于o 2 ，则s 具有资格，如果风险值上限 小于0 2 则s 不具有资格。 现在m 决定为了鼓励u 的学生到该超市的购物，宣布所有u 的学生均为其 贵宾，所以增加了一个新的证书： c 5 jm r i p ! o lu s t u d e n t 现在s 有另外一个途径可以得到m 的打折优惠，即通过a ，g ，o 三个证 书。这条证书链的累计风险值为： k 删= 丘( 缸，屯，毛) = 0 1 即m 承担k 删= o 1 的风险给s 提供打折优惠。新的路径使得s 可以用更低 的风险值得到m 的打折优惠资格，即证书链查询的风险值上限大于等于0 1 则s 都可以获得打折优惠资格。 2 4 本章小结 本章首先介绍了基于角色的信任委托管理系统( r b t m ) 的概念，随之介绍 了证书的风险概念并简单介绍了估算风险值的可能方法。最后介绍了r t r 系统， 即引入了风险值的r b t m 系统。下面一章所设计的算法就是解决i 玎r 系统中的最 1 4 浙江大学硕士学位论文第2 章信任委托管理系统 优证书链查找问题。 1 5 浙江大学硕上学位论文第3 章面向风险评估的证书链查找 第3 章面向风险评估的证书链查找 3 1 风险值的累计 r t r 系统一个关键的基础就是结合运算的定义，不同的结合运算定义使得 r t r 系统中的证书链风险值赋有不同的含义。 3 1 1 已有的风险值累计方法 结合运算可以定义为取两个风险值中较大的风险值作为运算结果，即： 肋= 侄篆黜 这种累计方法称作为累计上限( b o u n d o f - r i s k s ) 【1 0 】。 假设杭州市政府( h z g ) 在5 1 长假期间给每个杭州籍( h z c i t i z e n ) 的浙江 大学学生( z j u s t u d e n t ) 免费提供一辆自行车( b i c y c l e ) ，且彳是一个杭州籍的浙 江大学学生。该场景用r t r 系统语言可以描述为： g h z g j 哆i c y c l e 卜吐h z c i t i z e n c 、z j u s t u d e n t cjh z c i t i z e n 卜吐a ejz i u s t u d e n t 卜生彳 根据c ，o ，o 三个证书，彳在5 1 长假期间可以从杭州市政府免费借用一 辆自行车，其证书链的风险值为： k 删= 厶( 毛，k 2 ，毛) = 0 3 从集合的角度，该证书集合中每个角色的解集为： h z g j b i c y c l e ： ( 彳，0 3 ) ) h z c i t i z e n ： ( 彳，0 3 ) ) z _ 2 u s t u d e n t ： ( 彳，0 2 ) ) 结合运算也可以定义为风险值累加，即两个风险值的和作为运算结果： 1 6 浙江大学硕士学位论文第3 章面向风险评估的证书链查找 厶。( 口，b ) = a + b 这种累计方法称作为累计和( s u m o f - r i s k s ) 1 0 】。 在上面的例子中，如果使用累计和的结合运算计算证书链的风险值，则h z g 免费提供自行车给a 所承担的风险值为t k 删= 厶( 毛，乞，毛) = 0 3 + 0 2 + o 1 = 0 6 3 1 - 2 累计概率乘积 在大多数情况下，证书的风险值所表示的是证书发布方所承担的风险概率， 即因发布该证书而可能会引起的发布方不希望看到的事情所发生的概率。比如假 设风险值代表可信赖程度，则k = o 1 表示有o 1 的概率该证书为假证书。在这种 情况下，累计两个证书风险值的时候基于概率运算的结合运算比累计上限或累计 和更有实际意义。 假设有c ，和q 两个证书，证书风险值表示可信赖程度，且其风险值分别为 幻和幻。如果一个证书链需要同时依赖c ，和c 2 两个证书，则该证书链当且仅当 c ，和。两个证书同时可信赖的时候才是有效的。所以该证书链有效的概率为： 尸e f f e c t i v e = ( 1 一毛) ( 1 一乞) o 一 、1n 1 ，、1“2 ， 该证书链的总风险值则为： k t o t a t = 1 一加州。 基于这个概率计算，累计概率乘积的结合运算可以定义为： 0 蚰( 口，b ) = l 一( 1 一a ) o b ) 再考虑上面杭州市政府5 1 长假期间免费提供自行车的场景，杭州市政府还 额外特别照顾当地经济相对贫困( p o v e r t y ) 的居民，也给他们免费借用自行车， 居民的经济情况也是杭州市政府所维护，爿是经济贫困的一个居民。该场景用r t r 系统语言可以描述为： gjh z g j a i c y c l e 卜上三盟一h z c i t i z e nn z d u s t u d e n t c jh z c i t i z e n 卜土生彳 1 7 浙江大学硕士学位论文第3 章面向风险评估的证书链查找 gjz j u ，t u d e n t 卜生生2 _ 彳 c 4 jh z g ；b i c y c l e ! 韭lh z g p o v e r t y c 5 jh z g p o v e r t y ：韭l _ a 现在a 有两种方法可以得到免费借用自行车的资格，第一种为通过g ，c 2 ， o 三个证书，根据给定的结合运算公式，这条证书链的总风险值为： k t o t a l = 曲( 屯，如，向) = 1 一( 1 0 3 ) ( 1 一o 2 ) ( 1 一o 1 ) = 0 4 9 6 a 也可以利用贫困居民的身份，通过g 和a 证书得到同样的资格，这条证 书链的总风险值为： k t o t a = 二6 ( 屯，k 4 ) = l 一( 1 0 1 ) ( 1 0 1 ) = o 1 9 从集合的角度，该证书集合中每个角色的解集为： h z g ；b i c y c l e ： ( 彳，0 19 ) ) h z c i t i z e n ： ( 彳，0 3 ) ) 7 m u s t u d e n t ： ( 彳，0 2 ) ) h z g p o v e r t y ： ( 彳，0 1 ) ) 值得注意的是h z g h i c y c l e 角色的解集中我们只需要保留( a ，o 1 9 ) ，而另一个 一样的实体但风险值更大的( 彳，0 4 9 6 ) 不需要保留。 3 2r t r 系统证书链查找算法 3 2 1 证书图 证书图( c r e d e n t i a lg r a p h ) 的概念首先由l i 等人 9 1 提出，是用来用图论的理 论证明在r t o 系统中证书链查找算法的正确性。在本节中我们将对证书图的概念 进行扩展，使其可以适用下面所提出的r t r 系统中的证书链查找算法。 给定一个证书集合c ，e n t i t i e s ( c ) 表示所有在该证书集合中出现过的实体， r o l e n a m e s ( c ) 表示所有在该证书集合中出现过的角色名称，i n t e r s e c t i o n ( c ) 表示 所有在该证书集合中出现过的交叉角色。利用e n t i t i e s ( c ) 和r o l e n a m e s ( c ) 我们可 以定义所有可能的角色表达式r o l e e x p r e s s i o n s ( c ) ，即： 1 8 浙江大学硕士学位论文第3 章面向风险评估的证书链查找 r o l e e x p r e s s i o n s ( c ) = a ，彳 ，a r 2a e n t i t i e s ( c ) ，r l , r 2 r o l e n a m e s ( c ) ) 。 一个证书集合c 可以理解为一个用若干节点( n o d e ) 和相关的带权有向边 ( w e i g h t e d d i r e c t e d - e d g e ) 组成的带权有向图，我们称这个图为证书图。证书图 是一个以角色表达式为节点，以证书为边，以证书风险值为边权的带权有向图， 代表着一个相应的证书集合c 。证书图上不但有代表证书集合c 中显式证书的边， 还可能会有代表可从证书集合c 中的连接角色和交叉角色所能推导出来的隐式证 书( d e r i v e de d g e ) 。 定义3 1 ( 证书图) ：给定证书集合c ，其证书图为g c = ( c ，巨) 。 其中札为：札= u 彳，p ) u q 月r + l p e 为根据如下规则得出的的最小集合： 1 如果彳，士e c 则e 与么，e 。 2 如果a s 2 ，b ，2 虬并且4 吒卜盟一b ，则b r 2 上4 吃e c ，该证书并 没有显式存在于证书集合中，是通过连接角色推到出来的隐式证书 ( d e r i v e dl i n ke d g e ) 。其中彳，i 卜l b 并不一定是一个证书，而也可能 是一条证书链，在这条证书链上的证书共同支撑着该隐式证书，我们称 这条证书链为支撑证书集合( s u p p o r t i n gs e t ) 。 3 如果 彳，石r 、五r 、六以m 并 且 z 卜生l 彳，f 1 刀】 则 彳生生垒= 丝j 石n 五r 、石以丘 。 其中 彳型世出。墨屿石n 石r 、石石为通过交叉角色推倒出来的隐式证书 ( d e r i v e di n t e r s e c t i o ne d g e ) ，z 卜些l 彳，i e 【1 埘】中的所有证书构成该隐 式证书的支撑证书集合。 直观地理解，其中q 是证书链查找过程中可能会新产生的，原先不出现在任 何给定证书集合证书当中的角色表达式。给定的证书集合c 中的所有证书是显式 存在的证书，因为连接角色和交叉角色的存在，除了这些证书以外还存在一些根 据上面规则2 和规则3 可以推导的隐式证书。这些隐式证书中可能会出现一些显 1 9 浙江大学硕士学位论文第3 章面向风险评估的证书链查找 式证书中未出现过的角色表达式，q 为所有这种角色表达式的集合。 e 的定义还可以用归纳推导的方法得出，即从p 开始： e = p 彳，ia ，止p c 掣是根据规则l 所得到的，包含所有表示显式证书的边组成的集合。从硭开 始不断迭代，每次迭代都可以添加一个或多个表示着隐式证书的新的边进来，直 到某次迭代没有再产生新的边为止。因为证书集合c 是有限集合，所以迭代过程 必定会终止，终止时候的边的集合即为证书图的边集合e 。 定理3 1 ( 充分性) ：如果证书图中有路径b 山a r e ，则存在七使得 ( b ，k ) m e m b e r s ( a r ) ，k k 。 定理3 2 ( 完备性) ：如果有( b ，k ) m e m b e r s ( a r ) ，则证书图中存在相应一条 路径b 盟专a r g 。 充分性定理说明对于证书图中任何一条实体到角色的路径( 即实体获得该角 色的路径) ，在r t r 系统中该角色的解集中存在一个解，其实体为路径的起始实 体节点，其风险值大于等于路径的总风险值。完备性定理说明对于角色解集中的 任何一个解，在证书图中都存在相应一条从该解的实体开始到该角色的路径，其 总风险值为该