使用访问控制列表和群组的分布式系统中的授权

摘要

在控制分布式系统中在实体之间共享对象的方法中，处理器将标识对象并生成对象的访问控制列表(ACL)，使得ACL包括子句列表。每个子句都将包括将与一个或多个许可相匹配的许可模式，并且至少一个子句也可能包括对一个或多个群组的引用。每个群组表示字符串集，该字符串表示许可模式或许可模式片段。处理器可以将ACL的每个子句生成为允许子句或拒绝子句，以指示具有由许可模式相匹配的许可的一个或多个实体是被允许访问该对象。处理器将ACL保存到数据存储，以用于响应访问对象的请求。

说明书

相关申请及优先权

本专利文献要求于2015年5月27日提交的美国临时专利申请No.62/167,000以及于2015年8月12日提交的美国专利申请No.14/824,727的优先权，其公开通过引用完全并入本文。

背景技术

本公开描述了用于标识、认证和授权两个或更多个电子设备之间的通信的机制。

当诸如移动电子设备和服务器的电子设备经由网络进行通信时，重要的是通信被认证和访问控制。分布式系统(诸如可以经由一个或多个通信网络彼此通信的电子设备的集合)的参与者通常需要知道其正在与谁通信和表达谁可以执行某些动作或访问某些服务的方式。标识和/或验证设备或其用户的过程可以被称为“认证”。标识一个或多个设备或用户可以执行或使用哪些动作或服务的过程可以被称为“授权”。

群组为授权政策提供有用的间接级别，特别是由访问控制列表(ACL)描述的那些。当ACL指代群组时，ACL可以是简单和简短的。作为示例，ACL可以允许访问群组“FriendlyClients(友好客户端)”中的所有主体，其本身由经由群组“TrustedApps(受信应用)”中的程序具有设备群组中的设备的朋友群组中的用户组成。这些群组的定义可以与ACL分开管理，并由许多其它ACL共享。

在分布式系统中，群组的使用并不是直截了当的。例如，它需要用于命名群组的分布式方案。即使使用这种方案，在ACL检查时，群组定义可能并不全部可用。此外，群组可能会有意想不到的后果，也可能包含系统中没有单个参与者能够在本地进行检测的循环性。此外，控制群组的实体可能并不都被同等地信任。此外，查找群组成员资格可能会导致远程通信的成本，并需要适当的安全和隐私措施。

本文描述了针对在分布式系统中改进认证和/或授权的方法和设备。

发明内容

在各种实施例中，系统实施控制分布式系统中在实体之间共享对象的方法。处理器将标识对象并生成该对象的访问控制列表(ACL)，使得ACL包含子句列表。每个子句将包括将与一个或多个许可相匹配的许可模式，并且一个或多个子句也可以包括对一个或多个群组的引用。每个群组表示字符串集，所述字符串表示许可模式或许可模式片段。处理器可以将ACL的每个子句生成为允许(容许)子句或拒绝子句来指示具有由许可模式相匹配的许可的一个或多个实体是否被允许访问该对象。处理器将ACL保存到数据存储，以用于响应访问该对象的请求。

在生成ACL之后，然后当处理设备从客户端设备接收访问该对象的请求时，处理设备可以访问ACL。如果确定ACL包括具有匹配请求中呈现的许可的相关许可模式的至少一个子句，则它可以解析ACL的每个所确定的子句以确定该子句是否包括允许子句或拒绝子句，并且它可以使用解析的结果来决定是否准许或拒绝客户端设备访问该对象，并且作为响应，准许或拒绝客户端设备访问该对象。

可选地，当确定ACL包括至少一个子句时，系统可以确定ACL包括具有匹配的许可模式的多个子句。如果是这样，那么当使用解析的结果来决定是否准许或拒绝客户端设备访问该对象时，只有当所确定的子句的较后者包括允许子句时，系统可以准许客户端设备访问该对象，否则系统可以拒绝客户端设备访问该对象。替换地，当使用解析的结果来决定是否准许或拒绝客户端设备访问该对象时，只有当所确定的子句的较早者包括允许子句时，系统可以准许客户端设备访问该对象，否则它可以拒绝客户端设备访问该对象。

可选地，当确定ACL包括至少一个子句时，系统可以确定ACL包括群组。如果是这样，系统可以向群组服务器发送请求以确定该请求是否与群组的成员相关联，从群组服务器接收响应，并且在决定是否准许或拒绝客户端设备访问该对象时也使用来自群组服务器的响应。当从群组服务器接收到响应时，系统可以接收包括与群组相关联的请求的部分的第一指示，并且还接收包括与群组不相关联的请求的剩余部分的第二指示。

在一些实施例中，每个许可和群组可以由一个或多个人类可读名称来表示。此外，群组名称的至少一个可以被嵌入在许可模式的单独成分内。

在一些实施例中，系统还可以包括具有群组服务器处理设备的群组服务器。如果是，则群组服务器可以将群组的定义保存到计算机可读存储器，使得群组的定义与第一时间相关联，并且还将更新的群组的定义保存到计算机可读存储器，使得更新群组的定义与第二时间相关联。当生成响应时，群组服务器然后可以确定与请求相关联的时间，并且它可以使用时间来确定在评估请求时使用群组定义的哪个版本。

附图说明

图1图示出了包括各种客户端设备和服务器的分布式系统的示例。

图2是图示出生成和使用访问控制列表的过程的各个步骤的流程图。

图3是图示出匹配过程的示例的流程图。

图4图示出了根据各种实施例的可以用于包含或实施程序指令和与其它设备的通信的示例硬件的框图。

具体实施方式

与本公开相关的术语包括：

“电子设备”或“计算设备”是指包括处理器和非暂时的计算机可读存储器硬件的设备。存储器可以包含或接收编程指令，该编程指令当由处理器执行时，使得电子设备根据编程指令执行一个或多个操作。计算设备的示例包括个人计算机、服务器、大型机、游戏系统、电视机以及诸如智能电话、个人数字助理、照相机、平板电脑、膝上型计算机、媒体播放器等的移动电子设备。在客户端-服务器安排中，客户端设备和服务器分别是电子设备。

“对象”是过程、数据集或其它资源、功能或交易，服务器控制所授权的客户端对其的访问。

“主体”是发出请求的实体(诸如联网资源)。主体具有身份，并且可以通过名称和/或密钥来标识。

“许可(blessing)”是用于主体的加密或其它电子呈现的凭证集，其包含一个或多个人类可读的名称。(为了简单起见，本文也可以使用缩写词“许可”来指基于上下文意义清楚的许可名称)。人类可读的名称可以称为“许可名称”。

“人类可读的名称”是人类可以自然地阅读和理解的数据的表示，诸如由英文或其它人类语言的字符组成的数据的表示，可选地具有其含义是被人类理解的一个或多个符号。示例包括人类的姓名、包含表示“at”的@符号的电子邮件地址等)。

术语“群组”当用作名词时，旨在指表示字符串集的对象，所述字符串表示许可模式或许可模式片段。因为许可模式是由人类可读的名称组成的，所以群组名称及其内容也可以是人类可读的。

“许可模式”是一个斜杠分离的成分序列，其中每个成分是无斜线的许可的字符串或群组引用。

“警告(caveat)”是对实体访问对象的授权的约束。例如，警告可能会将实体仅限为服务的某些功能，或仅限于一组服务内的某些服务。警告也可以包括必须适用于许可完全可以使用的谓词。

“访问控制列表”或“ACL”是标识附加到特定对象或对象集的允许的列表、表或其它数据结构。允许可能涉及单个实体或多个实体。在本文中描述的实施例中，ACL也可以由人类可读的名称构成。

“证书”是主体可以呈现以证明什么名称已经与主体的公共密钥相关联的电子文档。

证书的“链”意味着每个证书由与先前证书相关联的公共密钥的私人对应密钥签名。链中的第一证书(即根证书)可以(虽然不必要)由客户端亲自签名(即，由第一证书中提到的公共密钥的私人对应密钥签名)。第二证书也由作为先前的证书持有人的客户端签名，但是第三证书将由第二证书的客户端签名。

“证书链”是如上所述通过链已经被签名的有次序的证书群组。

除非另有特别说明，单数术语“处理器”或“处理设备”旨在包括单个处理设备的实施例和其中多个处理设备在一起或共同执行处理的实施例。类似地，除非另有特别说明，术语“存储器”、“数据存储”、“数据存储设施”等旨在包括单个设备的实施例，其中多个存储器设备在一起或共同存储数据集或指令集以及这些设备内的各个扇区的实施例。

如本文中所使用的，除非上下文另有清楚规定，否则单数形式“一”，“一个”和“所述”包括复数引用。除非另有定义，本文使用的所有技术和科学术语具有与本领域普通技术人员通常理解的相同的含义。如本文所用，术语“包括”是指“包括但不限于”。

图1图示出了分布式系统的各种实施例，其中一个或多个客户端设备12a...12n经由诸如无线的电话网络、互联网、内联网、局域网、广域网、另一种网络或这些的任何组合的一个或多个通信网络20与诸如服务器16a...16n的一个或多个其它处理设备通信。服务器16a...16n中的任何服务器可以用于使一个或多个对象可用于所授权的客户端设备。此外，服务器中的一个或多个(例如，16b)可以作为证书服务器，或以其它方式将客户端设备12a...12n中的任何客户端设备的访问凭证(诸如加密密钥)存储在结构(诸如访问控制列表)中。服务器16n中的任何服务器也可以是存储一个或多个群组的细节的群组服务器，诸如群组成员的列表。此外，任何客户端设备(例如，12a)可以将其访问各种对象的授权委托给其它客户端设备中的一个或多个(例如，12b)。

本文描述了在新的库集、工具和服务中用于群组访问控制的设计，其可以帮助简化构建分布式应用的过程。系统的各种实施例可以经由本地名称来支持委托的形式。系统还可以支持ACL中的当群组定义不可用或包含循环性时具有保守语义的否定子句。此外，它可以帮助确保群组成员资格检查的隐私和效率。

在所公开的实施例中，每个主体用公共密钥标识，一个或多个许可(以人类可读名称的形式)被绑定到该公共密钥。具体来说，这些许可可以在被绑定到主体的公共密钥的公共密钥证书链中给出。例如，由具有许可“Alice(爱丽丝)”的主体拥有的电视机可能会具有许可“Alice/TV(爱丽丝/电视)”。在这里，电视是一个本地名称，任何主体都可以能够自主生成和应用该名称。主体可能会有多个许可，每个许可都反映了准许它的主体。例如，同一台电视机也可能具有来自它的制造商的许可“SomeCorp/TV123(某个公司/电视123)”。

当本文使用以单数形式的术语“许可”时，其旨在包括使用单个许可或多个许可的形式，除非特别指定为单个许可选项。许可可以存储在数据存储中。客户端和服务器可以基于他们想要彼此揭示的信息的级别来选择性地将其许可相互呈现。

许可是认证和授权的基础。当客户端与服务器进行通信时，客户端可以基于服务器呈现的一个或多个主体和许可来标识服务器。类似地，服务器可以基于客户端呈现的一个或多个主体和许可来标识、认证和授权客户端。具体来说，“许可”操作容允主体延伸其许可中的一个，并创建绑定另一个主体的公共密钥的许可，从而委托与许可相关的授权。例如，ACL可以包括子句“Allow Alice/TV(容许Alice/电视)”，以便所有具有匹配“Alice/TV”的许可的主体将有对ACL保护的对象的访问，并且具有许可“Alice”的主体可以选择向其电视机准许许可“Alice/TV”。在实践中，授权的委托很少是无条件的。警告可以限制在其下许可是有用的条件，例如将其有效性限制在一定时间段内。

在各种实施例中，群组可以不仅包含诸如“Alice”和“TV”之类的原子名称，还可以包含更长的复合许可，诸如“Alice/TV”。此外，群组的定义可以指在顶级(例如“Friendsincludes OldFriends(朋友包括老朋友)”)和作为复合许可的部分(例如“FriendlyClients”包括“Friends/Devices/TrustedApps(朋友/设备/受信应用)”)的其它群组。因此，可以将群组视为形式语言(formal language)，其中群组定义引发语法成果。然而，与传统形式语言不同，语法成果是分布式的，因此本文中描述的系统可能会考虑诸如通信成本、可用性和隐私等顾虑。

在所公开的实施例的命名惯例中，系统可以假设群组名称集，以及可以被称为普通名称的不相交的其它名称集。在本文中，g表示群组名称，以及n表示普通名称。

普通名称和群组名称具有非常不同的形式和用途。特别地，每个群组名称足以确定可以回答关于群组的问题的合适的服务器并且足以查询该服务器。另一方面，普通名称可能是基础本地名称、可以跨系统以不同方式解释的简单字符串。它们可以指的是各种实体(用户、服务、程序、程序版本等)，然而尽管它们可能遵守惯例。

许可和许可模式的句法可以使用诸如以下的语法：

在上述语法中，B在许可的范围上以及P在许可模式的范围上；并且斜线标记(/)是用于形成许可和许可模式的二进制运算符。因此，许可可以用普通名称的非空序列来表示，用斜线标记(/)分开，而许可模式可以用普通名称和群组名称的非空序列表示，用斜线标记(/)分开。我们把斜线标记(/)视为关联的。

例如，如果“Alice”和“Phone”是普通的名称，而“朋友”和“设备”是群组名称，则：(1)“Alice”和“Alice/Phone”是许可，它们也是许可模式；(2)“Alice/Alice”、“Phone/Phone”和“Phone/Alice”也是许可和许可模式，尽管它们可能不必要是有意义的；以及(3)“Friends”、“Friends/Phone”、“Alice/Devices”和“Friends/Devices”都是许可模式，而不是许可，因为其中的每个都包含群组。

诸如“所有许可”的人类可读的名称可以表示所有许可的集。当B和B'是许可时，在本文中，我们可以写为B≤B'，并且如果B中的普通名称的序列是B'中的普通名称的序列的前缀，我们可以说B是B'的前缀。我们以这个前缀关系为不严格自反的。换句话说，每一个许可都是自己的前缀。

在如上所述的一些实施例中，群组引用可以被嵌入在许可模式内。可选地，为了便于标识，群组引用可以由附加字符绑定，诸如开始处的“<”和结尾处的“>”。因此，允许访问在X公司员工John Doe的“AllMyDevice(所有我的设备)”群组中运行的任何设备上运行的“CloudMail(云邮件)”应用的许可模式可能如下所示：

XCcorp/johndoe/<grp:xcorp/grp/johndoe/AllMyDevices>/CloudMail

另外，当群组引用被嵌入到许可模式中时，在一些实施例中，群组名称可以出现在许可模式的单个成分内，而不是被包含在两个斜线内的整个成分。例如，考虑以下ACL条目：

wombat/foo<group_name>bar

在该ACL条目中，“group_name”是指包含“1”、“2”和“3”的群组。因此，ACL条目表示以下群组：

wombat/foo1bar

wombat/foo2bar

wombat/foo3bar。

图2图示出了将在下面更详细描述的过程的实施例的概述。具有处理器的服务器或其它设备可以通过标识对象201并且生成对象的访问控制列表203来控制分布式系统中在实体之间共享对象，使得ACL包括子句列表。ACL中的每个子句包括包含一个或多个许可的许可模式。子句中的一个或多个还可以包括对一个或多个群组的引用，其中每个群组表示许可模式集。每个子句可以是“permit(允许)”子句或“deny(拒绝)”子句来指示具有由许可模式匹配的许可的一个或多个实体是否被允许访问对象。系统将ACL保存到数据存储205，以用于响应访问对象的请求。

当系统接收客户端设备访问对象的请求209时，它将访问访问控制列表(ACL)211，并且确定ACL是否包括具有与在请求中所呈现的许可相匹配的相关许可模式的至少一个子句213。如果是这样，它将解析具有相关许可的ACL的每个所确定的子句以确定该子句是允许子句还是拒绝子句215。它将使用解析的结果来决定是准许还是拒绝客户端设备访问该对象，并且然后相应地准许219或拒绝221客户端设备访问该对象。

系统可能需要或希望操纵许可列表和许可模式列表。在下面的示例中，许可列表是ACL检查的输入；许可模式列表出现在群组定义中。因此，我们为他们介绍句法类别：

我们使用常量“empty(空)”来表示空列表，并使用逗号作为用于形成列表的二进制运算符。在本文中所示的示例中，当在列表中出现时我们可以省略“empty”，以及例如我们可以将列表“empty,Alice,Bob(空，爱丽丝，鲍勃)”简单地写为“Alice,Bob(爱丽丝、鲍勃)”。

群组名称可以是至少两种类型：内置群组的群组名称和定义群组的群组名称。在这两种情况下，群组可以被认为是许可模式集。

内置群组可以是由底层平台提供的那些，因此不需要延伸的定义。我们以“AllBlessings(所有许可)”的名称指代的所有许可集，是一个示例。通常，内置群组可以通过特别是回答成员资格查询的相当任意段代码来实施。下面我们讨论这个代码应该提供的接口。正式地，我们可以假定函数Elts将每个g∈BuiltInGroups(内置群组)映射到许可集(直观地，g的元素)。例如，我们让Elts(AllBlessings)＝AllBlessings。如在这种情况下，Elts(g)集可以是无限的。

所定义的群组可以与将群组名称与许可模式列表相等的定义相关联：

g＝L

给出定义集DefSet{g₁＝L₁,...,g_k＝L_k}，系统可能要求群组名称g_i成对区分并且区分于BuiltInGroups(内置群组)中的元素。每个群组名称可以与服务器相关联，以有助于以分布式方式执行。

另一方面，系统可以不需要在定义中缺失循环。一些简单的循环可能偶尔是有用的。

系统可以容许某些群组名称既不在BuiltInGroups(内置群组)中也不具有定义(或至少不是系统可用的定义)的可能性。

系统可以容许一个或多个电子设备生成并输出用户界面(或自动化构造过程)，用户(或系统)可以通过该界面创建新群组、删除群组和修改群组成员资格。

与内置群组相关联的代码和与其它群组名称相关联的定义两者都可以随着时间而改变。它们甚至可以在ACL检查期间改变。正确性期望可能必须相应地放宽(例如，以便容许对服务器重新排序查询)。

ACL是子句列表，每个子句允许或拒绝访问与特定许可模式匹配的许可。ACL可以通过以下定义：

例如，在一个实施方式中，所有“Allow(容许)”子句(其也可以被称为“Permit(允许)”子句)可以在所有“拒绝”子句之前，但相反的安排或没有特定要求可以适用。在依赖于次序的语义安排中，系统会知道：

“Allow Friends,Deny Alice(容许朋友，拒绝爱丽丝)”

与以下是不一样的

“Deny Alice,Allow Friends(拒绝爱丽丝，容许朋友)”。

在一个实施例中，后面的ACL条目将优先于较早的条目(尽管在替选实施例中相反的优先级可以是真的)。在本实施例中，当“Alice”在“Friends”群组中时，后面的ACL将给予对“Alice”的访问，并且前面的将拒绝它。

在本公开和各种实施例中，我们可以通过组合连续的Allow子句来缩写ACL，例如将“Allow Friendes,Allow Alice(容许朋友，容许爱丽丝)”写为“Allow Friends,Alice(容许朋友，爱丽丝)”，以及类似地为连续的拒绝子句这样做。许多ACL可以是一个简单的形式，诸如“Allow g”，其中g是群组名称。更一般地，许多可以是“Allow>1,...,P_k”的形式，或作为另一个示例：

Allow>1，...，P_k，Deny>k+1，...，P_k+k′

其中P₁，...，P_k+k′是许可模式。

在一些实施例中，系统可以不容许命名ACL。这种限制意味着通过命名的群组发生共享。

每个许可模式-特别是每个群组名称-代表许可集。以下讨论解释了系统可以如何将许可模式映射到许可集。

假设群组名称的语义(从群组名称到许可集的映射，作为参数ρ给出)，函数“Meaning”将许可模式和许可模式列表映射到许可集。归纳地定义如下，首先是对于许可模式：

Meaning_ρ(n)＝{n}

Meaning_ρ(g)＝ρ(g)

Meaning_ρ(n/P)＝{n/s|s∈Meaning_ρ(P)}

Meaning_ρ(g/P)＝{s/s′|s∈Meaning_ρ(g)，s′∈Meaningρ(P)}

然后对于许可模式列表：

Meaning_ρ(L，P)＝Meaning_ρ(L)∪Meaning_ρ(P)

群组名称的语义基本上包括将每个群组名称映射到群组的成员集的函数ρ。当表达式(例如，ACL)直接或间接地指代尚未定义的群组时，则在分布式场境中(在这种实例下，当定义位于不同的服务器时)，系统可能必须决定当无论什么原因群组定义可能存在但不能被查找时，会发生什么。如果我们希望系统保守(失败安全)，则其在Allow和Deny子句中的决定可能不同。因为这个原因，在这个场境中，系统可以使用本文中指代为和的两个函数。在对群组的所有引用都可以解决的情况下，它们一致。

对于构造我们可以将群组定义列表DefSet视为引发形式语言，如下所示。

-普通名称和斜线(/)是终端。

-群组名称是非终端。

-系统可以将成果与群组定义相关联，例如将定义：

g₁＝Alice/Phone，g₂/Phone

转化成两个成果

g₁→Alice/Phone

g₁→g₂/Phone

-系统还可以将成果与每个内置群组名称相关联，对于每个B∈Elts(g)，g：g→B，。

-最后，系统可以不将成果与任何剩余的群组名称(既不在DefSet中定义也不是内置群组名称的群组名称)相关联。

对于每个群组名称g，系统可以使是由这些成果从g生成的许可集。因此，群组成员资格的问题可能会减少到形式语言成员资格的问题。

当Elts(g)对于每个g∈BuiltInGroups是有限的时，上面的成果构成无上下文的语法。否则，系统仍然可以获得每个群组名称g的形式语言尽管这些语言不必是无上下文的语言。更准确地说，就像形式语言理论一样，是函数F的最小定点，以至于对于每一个g，

-如果g由g＝L定义，则F(ρ)(g)＝Meaning_ρ(L)

-对于g∈BuiltInGroups，F(ρ)(g)＝Elts(g)；以及

-其它情况下

除了在最后一种情况下，系统可以使F(ρ)(g)＝AllBlessings以外，的构造是类似的。特别地，系统仍然采取最小的定点(不是最大的定点)。

在实践中，系统可能不总是需要计算最小固定点：它可以将某些群组定义视为不可用(或发现某些群组定义不可用)，例如当对应的服务器失败时，或者当我们具有计算预算已经耗尽或接近极限时。结果可能是保守的近似。

在其它系统中，在访问控制中例如在定义防火墙规则中使用常规表达式。通过上述定义，系统可能超出常规语言，以避免群组定义中繁琐的句法条件。

当处理器从请求实体接收到许可集(并且可选地，群组定义)并且针对对象在ACL中将所呈现的许可与每个许可模式匹配时(可选地，使用所接收的群组定义，和其它的)，ACL检查将进行。该过程的示例在图3中示出。系统可以迭代地比较许可名称中的文字成分与许可模式中的文字成分，继续直到系统在模式中遇到群组名称为止301。系统可以确定匹配是否存在303。如果任何文字成分在许可模式中没有被发现，系统可以确定它是不匹配的，并拒绝请求313。如果许可名称是模式的前缀，则系统可以将其确定为匹配。当系统遇到第一时间的群组名称时305，它可以经由群组服务器API向群组服务器发送许可名称的剩余不匹配部分(下面讨论的剩余)307。群组服务器将使用相同的匹配算法(递归地应用)将剩余与每个群组成员匹配并返回新的剩余集。如果在整个模式被消耗之后剩余集是非空的，则系统可以声明匹配309并容许请求313。否则，它可以拒绝请求303。如果模式是$终止(如下所述)，则可选地，只有在剩余集包含空字符串(意味着完全匹配)时，系统才可以声明匹配。可选地，如果群组服务器不可达，则它可以将群组视为空(如果许可模式是Allow子句)或全包括(如果许可模式是Deny子句)。

我们可以用一个简单的示例来说明这种匹配算法。假设我们有：

许可名称(由客户端提供)：“a/b/c/d/e”

许可模式(在服务器端)：“a/b/<grp：v/g₁>”

群组定义(v/g₁)：{“c”，“c/d”，“c/d/e”，“e”}

如果我们用群组的定义扩展模式，则所得到的模式是“a/b/c”、“a/b/c/d”、“a/b/c/d/e”和“a/b/e”。许可名称“a/b/c/d/e”成功匹配模式“a/b/c”、“a/b/c/d”和“a/b/c/d/e”(如上所述，如果模式是名称的前缀，许可名称可以匹配许可模式。)

然而，为了在不学习群组的定义(使用如上所述和如下所述的Rest函数)的情况下确定匹配，系统可以通过将每个许可名称成分与模式中的成分相匹配来进行。许可名称的前两个成分“a”、“b”与模式的前两个成分匹配。然后，系统可以将许可块“c/d/e”与群组“v/g1”相匹配。因此，我们向群组服务器发送Rest(“c/d/e”)RPC。给出群组定义，群组服务器匹配后设置的剩余为{“e”，“d/e”，“”}。这个剩余集作为Rest()调用的输出返回。系统可以声明匹配，既然它具有在结尾处设置的非空(即，不是{})剩余。

已经收集多个许可的主体可以为授权决定的目的而呈现子集。它可以决定不呈现其所有的许可，也许是因为对性能或保密性的顾虑。但是，它不应该由于保留某些许可而获得附加的权利。

相应地，执行授权检查的函数，例如，“IsAuthorized”被应用到许可M和ACL A的列表中。当在M中的许可被呈现时，它可以根据A决定是否应该准许访问。定义为辅助函数IsAuthorized₁(B，A)，其被应用于单个许可B和ACL>

该定义依赖于上述的映射和“Meaning”。旨在作为说明，没有必要的具体实施方式。

根据本实施例，ACL的语义是依赖于次序的，同时后面ACL子句胜过较早的子句。例如，对于任何许可模式P，ACL“Allow P，Deny P”总是拒绝访问。

通过依赖于根据子句类型的和来保守地处理(直接或间接地)指代未定义群组的ACL子句。这种保守处理可以一次进行一个条目。在某些情况下，这种方法可能会产生稍微令人惊讶(但安全)的结果。考虑一下，例如，异常ACL“Allow Alice，Deny Friends，Allow Friends(容许爱丽丝，拒绝朋友，容许朋友)”，其中“Friends(朋友)”是群组名称，但没有对应的定义，或者其定义不可用，并且“Friends”不在BuiltInGroups中。假设系统希望知道该ACL是否容许对许可“Alice”的请求进行访问。系统可能从结尾开始分析ACL。子句“Allow Friends”不允许访问，因为系统做出“Friends”是空的保守的假设。子句“DenyFriends”拒绝访问，因为系统做出“Friends”包含所有的许可的保守的假设。因此，在本示例中，系统可能永远不会查看“Allow Alice”，并且其可能会拒绝访问。

定义使用前缀关系≤(而不是要求精确的相等)来检查Allow和Deny子句。至少在以下两种情况下，≤的选择具有不同的意义：

首先，对于Allow子句，使用关系≤是为了方便。例如，当一个人针对其希望与具有许可“Alice”的主体共享的对象写为ACL“Allow Alice”时，即使这种访问可以经由具有许可“Alice/Phone”的电话发生，这个主体获得访问通常也是权宜的。因此，延长许可不会减少关于ACL检查中的Allow子句的授权。然而更长的许可在其它方面不等同于较短的许可：更长的许可可能触发Deny子句，并且拥有许可“Alice/Phone”的主体通常不能获得诸如“Alice/TV”的“Alice”的其它延伸。

这种语义可根据需要精确相等的语义来定义。例如，在后面的语义下，可以写为ACL“Allow Alice，Alice/AllBlessings”，而不是“Allow Alice”。相反，即使使用≤的语义，也可能定义坚持准确相等的ACL。例如，可以写为“Allow Alice，Deny Alice/AllBlessings”。替换地，假设“$”是仅在结束时出现在许可中的保留名称，可以写为“AllowAlice/$”

第二，对于Deny子句，从安全角度来看，禁止利用许可B访问但是允许利用更长的许可访问一般没有意义。谁有B就可以延伸它，以规避Deny检查。

可以使用在Allow子句中进行匹配的替换准则，我们将其称为“前缀匹配”。例如，利用此准则，ACL“Allow Alice/Phone”将允许利用许可“Alice”进行访问。这个决定的主要动机是拒绝这种访问没有清楚的安全利益。谁拥有“Alice”可以形成“Alice/Phone”，以获得访问。

作为授权检查的示例，如上定义的函数IsAuthorized可以通过在依赖方处计算函数和“Meaning”来实施，然后盲目地应用定义。然而，这些计算一般上需要群组定义的知识，系统可能不想为了效率和隐私的原因将该群组定义传播。相关群组甚至可能是无限的，并且因此不能够被列举。此外，有时不需要用于确定某些特定的许可是还是不是对应的许可集的成员的“Meaning”的全面计算。因此，实施例可以使用IsAuthorized的分布式查询驱动的实施方式。在下面的讨论中，我们首先将IsAuthorized减少到基本函数R，然后讨论如何实施R的所需调用。这可以被认为是一种形式的自上而下解析。

其它算法方法可以从形式语言上的工作导出。

假设系统希望知道特定的许可是否在Meaning_ρ(P)中。当许可是普通名称n时，系统可以如下进行：

-对于每个m≠n和每个群组名称g，如果P＝m或P＝m/P₁或P＝n/P₁或P＝g/P₁，则失败。

-如果P＝n，则成功。

-如果P＝g，则询问负责g的服务器是否n是g的元素并返回结果。

当许可是复合许可n/B₁时，系统可以改为如下进行：

-对于每个m≠n，如果P＝m或P＝m/P₁，则失败。

-如果P＝n，则失败。

-如果P＝n/P₁，则利用B₁和P₁递归。

-如果P＝g，则询问负责g的服务器是否n/B₁是g的元素并返回结果。

-如果P＝g/P₁，则询问负责g的服务器是否存在B₂、B₃，使得n/B₁＝B₂/B₃，并且B₂是g的元素，并且如果是利用B₃和P₁递归(为了完整起见，对于每个合适的B₃)。

因此，负责g的服务器可以回答以下形式的问题：

-许可B是否在Meaning_ρ(g)中，

-许可B能否写为B₂/B₃的形式，其中B₂是Meaning_ρ(g)的元素。

尽管后面种类的每个问题可以被减少到前面种类的几个问题(每个B的前缀B₂一个)，提供用于询问后面种类的问题的接口可以容许更直接、有效的交互。

因此，系统可以假设具有以下说明的函数R(该文可以称其为“Rest函数”)：R是这样的，给出许可B和许可集S，R(B，S)返回由以下组成的集：

-如果B是S的元素，∈，以及

-每个许可B″，使得对于某些B′我们有B＝B′/B″并且B′是S的成员。

注意，R(B，S)一般上可以包含许可和空字符串∈两者。例如，如果S＝{n₁，n1/n₂，n₁/n₂/n₃}则R(n₁/n₂，S)＝{∈，n₃}。名称R代表“剩余”、“剩下”或“残留”。Rest函数可用于确定许可或许可模式是否是特定群组的成员，同时容许群组服务器从请求实体屏蔽群组的整个内容。下面我们考虑系统可以如何实施这个Rest函数，R。

使用R，系统可以重新制定IsAuthorized的定义：

接下来，我们考虑系统可以如何计算和近似和而不完全扩展和Meaning的定义。我们首先呈现基本示例算法，然后详细阐述分布式实施方式。

首先，假设对于每个g∈BuiltInGroups，我们有R(B，Elts(g))。实际上，这个假设可能意味着实施内置群组g的代码应该提供用于询问R(B，Elts(g))形式的查询的接口。注意，即使Elts(g)是无限的，R(B，Elts(g))总是有限的。在AllBlessings的情况下，该集合包括空字符串和B的适当后缀。我们可以写S(B)来表示该集合。如果我们想要函数和使得：

其中作为隐式参数，和有群组定义DefSet。为简洁起见，在本文中，当我们希望引用和两者时，我们可以写为R_X(但是在诸如R_X(...)＝...R_X(...)...的等式中，我们指的是两边相同的R_X)。给出许可模式列表L＝P₁，...，P_k，我们让R_X(B，L)＝∪_i＝1..kR_X(B，P_i)。

期望的函数和满足等式：

R_X(n，n)＝{ε}

R_X(n/B，n)＝{B}

R_X(n/B，n/P)＝R_X(B，P)

当从左向右定向时，这些方程式立即提示用于计算R_X(B，P)的算法。该系统通过按照P形式的情况进行来实施该算法。当P不是群组名称并且不以群组名称开头时，算法则按照B形式的情况进行。当P是具有在DefSet中定义g＝L的群组名称g时，算法展开了这个定义。当P是群组名称g∈BuiltInGroups时，算法简单地返回R(B，Elts(g))，我们根据我们的假设具有它。最后，如果P是任何其它群组名称g(因此，没有定义或实施方式是可用的群组名称)，算法返回或

以这种方式，如果控制ACL的实体发出群组服务器的请求，并且该请求包括诸如“A/B”的许可模式，则群组服务器可以返回群组包括“A”、剩下的R为“B”的一个或多个标记。这容许系统针对所作出的特定请求而裁制响应，而不会透露关于群组的其它信息。

R_X(B,P)的计算基本上相当于自上而下解析B，作为与P相关联的形式语言的元素。当任何语法成果是左递归的(形式g→g...其中g是非终端的)时，自上而下的解析不起作用或不能工作的很好是正常的。这里，左递归可能导致算法陷入无限循环。在理论上，可以总是避免左递归成果(特别是通过使用Greibach正常形式)。然而，在一个实施例中，为了防止左递归，我们可能不希望限制或重写群组定义。

因此，系统可以使用不考虑假设而工作的较弱的和的定义。对于保守的实施方式，我们只需要：

系统可以应用适应的算法来实现这些属性，同时提高其效率并保证其终止。特别地，无论何时给出的计算预算已经用尽，系统可以容许计算终止-利用保守的决定。作为特殊情况，系统可能容许服务器上的查询超时。此外，通过向和传递附加的参数，系统可以跟踪我们已经检查的群组集，并且在检测到循环时再次利用保守的决定终止。可能存在检测所有循环或仅由于左递归产生的那些循环的变体。只有后面的循环会产生分歧，而前面的变体则稍微更简单。

分别为这些和的近似值写为和系统可以获得IsAuthorized的保守实施方式：

因此，我们用替换R的出现以用于“Allow”检查并且用替换R的出现以用于“Deny”检查。

对应于许可的ACL的部分的ACL检查可以被定向到第一处理设备，而与群组对应的ACL的部分的检查可以被定向到单独的群组服务器。如果这样，那么(参考图2)，控制ACL的实体可以与群组服务器通信，以获得群组的相关细节，以确定请求是否被授权，并且只允许所述请求中与授权群组230相关联的请求。

当ACL和群组根据其它群组来定义时，我们现在解释对应的服务器或其它处理设备如何对ACL检查做出贡献。此过程可以由请求访问的客户端或由持有ACL的实体进行组织。例如，如果ACL指的是本身根据群组g₂定义的群组g₁，则客户端可以获取和呈现关于g₁和g₂的证据，或者持有ACL的实体可以为两个群组进行查找。替选地，该实体可以联系负责g₁的服务器，该服务器可以进而联系负责g₂的服务器。

可选地，系统可以采用替换方案作为其主要方案。如果是这样：

-IsAuthorized^imp(M，A)评估可能在持有A的实体处本地发生，调用其它以评估R_X；

-R_X(B，P)的评估可以在由R_X定义指示的所有情况下使用本地递归调用，除了R_X(B，g)的情况外，这种情况应当咨询负责g的服务器(除非，如上所述，这将导致循环)。

在实践中，该方案可以经受各种优化，诸如缓存、查询的批处理以及客户端的“推送”凭证。

利用该方案，ACL和群组成员资格可以仅在响应于查询(针对ACL的IsAuthorized^imp查询，群组的R_X查询)时部分地揭示。可以看到足够的消息流的观察者也可以推断依赖关系，即特定的ACL或群组依赖于某些其它群组。但是，ACL和群组的全部内容可能不会被批量公开。

没有原子性假设，在IsAuthorized^imp(M,A)的评估期间，群组定义变化是可能的。例如，让A成为ACL“Allow>imp(Alice,A)将返回真，这种行为可能在添加之前和之后都不会发生。为了防止这种行为，系统可能会要求负责相关群组的服务器或其它处理设备经由R_X的额外的“时间”参数提供在ACL检查兴趣的当前时间的信息。假设处理设备保留最近群组变化的日志，这种技术将有助于完成相当快速经受到时钟同步的限制的ACL检查。

我们现在详细说明上述的前缀匹配。可选地，系统可以不采用它。原因可能与Deny子句和群组有关系；如果这些特征中的任何一个不存在，它们较弱。由于前缀匹配对于表达性或可用性不是必需的，因此可以将其省略以更好地处理这些特征。然而，各种实施例可以包括前缀匹配。

前缀匹配的原理如下。假设许可B'匹配ACL，而且B≤B'。谁拥有B可以将其延伸到B'，从而通过ACL检查；因此，不让B匹配ACL可能会导致不便，并且如果B恶意行为，则没有立即受益。(然而可能会防止意外的不当行为。)

采用前缀匹配将意味着例如当呈现许可n₁时，ACL“Allow>1/n₂”准许访问。

还考虑ACL“Allow>1/g”，并设想g被定义为空。当许可n₁被呈现时，应该准许访问吗？正面的答案似乎是令人惊讶的，并且没有被前缀匹配的所提出的原理证明：没有办法延伸n₁，使其严格匹配n₁/g。用于许可模式P的前缀匹配(在本示例中为n₁/g)关于匹配P的许可的前缀，而不是匹配P的前缀的许可。换句话说，它是关于P的含义(meaning)的前缀，而不是P的前缀的含义(meaning)。

接下来考虑ACL“Allow n1/n2，Deny n1/n2”。当许可n₁被呈现时，应该准许访问吗？系统可以通过计算Allow子句的含义(其利用前缀匹配，暗示授权n₁)，Deny子句的含义(并不暗示拒绝n₁)，并且然后取得差异，来正面地回答这个问题。由于没有办法延伸n₁使其匹配n₁/n₂但不匹配n₁/n₂，所以这种行为可能不被前缀匹配的所提出的原理证明。

替换的方法包括计算整个ACL容许的所有许可(减去Deny子句，但没有为Allow子句加前缀)，并且然后添加它们所有前缀。如示例所示，减去Deny子句不会用添加前缀交换。这种替换方法确实符合前缀匹配的原理。

在实践中，替换方法可能难以实施。考虑ACL“Allow>1/g₁/$，Deny>1/g₂/$”，其中g₁和g₂是群组名称，并且$是所指定的终结符名称。根据替换的方法，当且仅当存在g₁中的不在g₂中的某些元素时呈现许可n₁时，才会准许访问。

综上所述，如上所述，现有技术的许多系统支持分布式授权。在其特征包括群组的情况下，现有技术不提供诸如缺失、不可用和循环群组定义之类的问题的典范解决方案。

所公开的实施例可以通过向ACL提供群组和负子句来减轻这些困难。这种选择还使我们能够为ACL提供与群组的语义不同(根据这个，包含“Alice”的群组不需要包含“Alice/Phone”)的自由的语义(其中，例如，ACL“Allow Alice”允许访问“Alice/Phone”)。在现有技术中，准许Alice的访问的ACL一般上不会自动准许对形式为“Alice op Phone”的复合主体的访问，其中op是二进制运算符，除非该运算符恰好是连接词(∧)。连接词很难与/类似，例如因为它是可交换的；先前考虑的其它运算符似乎更接近于/。除了这些差异之外，本实施例可以仅具有一个运算符(/)并且它是关联的事实容许本系统加强与形式语言的有用连接。

主体的所有许可可以存储在许可存储中，类似于web浏览器中的饼干罐(cookiejar)。当作为服务器时，存储标志要呈现的许可。

因此，各种实施例可以使用几个独特的特征。例如，系统可以根据主体的特定委托而不是主体的所有委托写出ACL。例如，用户可能希望ACL容许用户的客户端电子设备的每个上的“日历”应用(或另一个交互式应用)访问用户的“我的日历”数据，而不容许其它应用或设备如此访问。

而且，系统可以使用群组来指任意身份的特定委托集。这使我们使用群组来表示身份的任意子字符串，而不只是前缀。例如，假设用户购买了名为“产品X”的特定生产力套件的版本，其包括某些应用的特定版本。系统可以写出当在任何用户的设备上运行时容许任何这些程序访问一些文件的ACL。当在用户的电话上运行时，那些应用中的一个可能会使用身份“company/mike/phone/productx_v4”。

如果用户将产品X的副本从v4升级到v5，或者从同一提供商添加另一个应用，他或她可能希望ACL仍然有效。因此，系统可能会写为{mikes_devices}/{provider_suite}(名称指群组)形式的ACL条目，其扩展到在任何用户设备上运行的提供商的产品套件中的任何应用。“mikes_devices”群组将由用户策划，但“provider_suite”群组将由产品X的提供商策划。

此外，系统可以容许其ACL中的“deny”子句。例如，系统可以容许所有员工访问对象，除了实习生-实习生可以在“deny”子句中被提到。

系统可以提供(暂时)从互联网断开连接的设备之间的对等通信。例如，当两个设备都在飞机上，与互联网断开连接时，一个设备可能与另一个设备交互，并且访问控制检查必须保守，即使有关群组成员资格的最新信息不可用。

系统可以提供开放式、分层的群组结构，其中任何人可以定义具有任意成员资格的群组，包括其它群组。因此，给出的身份可能在广泛地分散在分布式系统上的任意数目的群组中或由其暗示。换句话说，可能并不容易发现一个人必须咨询涉及特定身份的所有访问控制决定的“完整”的群组集。

系统保护隐私：群组的所有者可能不希望向系统检查ACL揭示其完整成员资格。ACL的所有者可能不希望向客户揭示ACL提到的所有群组。客户可能不希望向他人揭示他们所属的群组的身份。按照示例，设想日历应用的开发者希望在用户的日历数据上设置ACL，并且假设用户当前有两个设备：他的平板电脑和他的膝上型电脑。开发者可以想象地在ACL上包括身份“user/tablet/calendar(用户/平板电脑/日历)”和“user/laptop/calendar用户/膝上型电脑/日历”。但是，当用户获取必须然后添加到该ACL以及所有用户应用中的类似ACL的电话时，这将是不方便的。

替换地，可以使用群组来获得简单的间接级别，因此ACL准许对包含上面列出的身份的群组“users_calendar”的访问。这也是不方便的，因为再一次，每个应用拥有自己的群组，并且当用户购买电话时，每个应用都必须被编辑。

本文的实施例通过容许用户具有单个群组来解决这个问题，该单个群组列举他的设备但是可以用来导出其ACL引用该单个群组的每个应用的身份集。因此，群组G可能包含“user/tablet(用户/平板电脑)”和“user/laptop(用户/膝上型电脑)”，ACL条目“G/calendar”则将获得所期望的结果。

在一些实施例中，系统可以随着时间使用缓存来将群组成员资格或查询结果存储到群组服务器。以这种方式，请求也可以与时间相关联。考虑时间可以容许请求考虑许可模式是否是特定时间的群组的部分。它还可以帮助管理离线操作，和/或确保如果在正在进行请求时该群组正在被更新或修改，在特定时间做出的请求返回正确答案。

为了解决这些问题，客户端和/或群组服务器可以在计算机可读存储器中维护对群组服务器的查询结果的缓存。为了描述这点，下面的讨论使用术语“客户端”、“服务器”和“群组服务器”来指代访问请求/检查中涉及的三方。任何处理设备可以用作三个实体中的任何实体。

使用服务器侧缓存，服务器从群组服务器缓存Get/Rest响应，并在执行后续访问检查时使用这些缓存的响应(如果可用)。服务器可以在有限的时间段内保持缓存，诸如一小时、一天、一周、一个月或任何其它适当的时间段。然后，当服务器接收到请求时，它可以将时间与请求相关联。相关联的时间可以与请求一起被接收，诸如由时钟生成的时间戳或其它时间表示。替换地，服务器可以关联不同的时间，诸如编辑ACL的时间，或者编辑所请求的对象被的时间(诸如最近的编辑)。服务器可以标识与时间相对应的缓存(诸如具有相同时间或最接近的先前时间的缓存条目)。然后，它可以使用所标识的缓存来确定请求是否与授权群组相关联。

利用客户端缓存，客户端可以将时间编码到ACL中。例如，客户端可以从群组服务器或其它服务器获取不透明或防篡改的Get/Rest响应，并且它可以在对服务器的后续请求中包括任何相关的响应。例如，服务器在其对客户端的响应中可以包括不透明(服务器加密的)“票证”，并对任何相关的群组服务器响应进行编码。客户端可以存储此票证并将其呈现在后续请求上。票证是不透明的，因此不向客户端泄露信息。可选地，缓存的响应可以通过使群组服务器计算校验和，使用其私人密钥对其进行加密，并将所加密的校验和附加到响应来进行防篡改。具有对应公共密钥的任何一方则可以解密和验证校验和。

图4描绘了可用于包含或实施程序指令的硬件的框图。总线400作为互连硬件的其它所示组件的信息高速公路。处理器(CPU)405是系统的中央处理设备，实行执行程序所需的计算和逻辑运算。当这些术语在本公开内容内使用时，CPU 405单独地或与图4中公开的其它元件中的一个或多个相结合，是生产设备、计算设备或处理器的示例。只读存储器(ROM)410和随机存取存储器(RAM)415构成非暂时计算机可读存储介质的示例。

控制器420与一个或多个可选非暂时计算机可读存储介质(即，存储器设备425)接合到系统总线400。这些存储介质可以包括例如外部或内部DVD驱动器、CD ROM驱动器、硬盘驱动器、闪存、USB驱动器等。如前所述，这些各种驱动器和控制器是可选设备。

用于提供接口并执行与一个或多个数据集相关联的任何查询或分析的程序指令、软件或交互模块可以被存储在ROM 410和/或RAM 415中。可选地，程序指令可以存储在上面讨论的存储介质425上。

可选的显示接口430可以允许来自总线400的信息以音频、视觉、图形或字母数字格式被显示在显示器435上。可以使用各种通信端口440发生与诸如打印设备的外部设备进行通信。通信端口440可以附接到诸如互联网或内联网之类的通信网络。

硬件还可以包括接口445，其容许从诸如键盘450或诸如鼠标、触摸板、触摸屏、遥控器、定点设备、视频输入设备和/或音频输入设备的其它输入设备455的输入设备接收数据。

上述公开的特征和功能以及替换方案可以组合成许多其它不同的系统或应用。本领域技术人员可以做出各种目前不能预见的或意料之外的替换方案、修改、变化或改进，其中每一个也旨在被所公开的实施例所涵盖。