-
Notifications
You must be signed in to change notification settings - Fork 244
/
accessibilityset.go
372 lines (319 loc) · 14.7 KB
/
accessibilityset.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
package consistencytestutil
import (
"testing"
"github.com/stretchr/testify/require"
"golang.org/x/exp/maps"
"github.com/authzed/spicedb/internal/developmentmembership"
"github.com/authzed/spicedb/internal/dispatch"
"github.com/authzed/spicedb/internal/dispatch/graph"
"github.com/authzed/spicedb/internal/graph/computed"
"github.com/authzed/spicedb/pkg/datastore"
"github.com/authzed/spicedb/pkg/genutil/mapz"
core "github.com/authzed/spicedb/pkg/proto/core/v1"
dispatchv1 "github.com/authzed/spicedb/pkg/proto/dispatch/v1"
"github.com/authzed/spicedb/pkg/tuple"
)
// ObjectAndPermission contains an object ID and whether it is a caveated result.
type ObjectAndPermission struct {
ObjectID string
IsCaveated bool
}
type Accessibility int
const (
// NotAccessible indicates that the subject is not accessible for the resource+permission.
NotAccessible Accessibility = 0
// NotAccessibleDueToPrespecifiedCaveat indicates that the subject is not accessible for the
// resource+permission due to a caveat whose context is fully prespecified on the relationship.
NotAccessibleDueToPrespecifiedCaveat Accessibility = 1
// AccessibleDirectly indicates that the subject is directly accessible for the resource+permission,
// rather than via a wildcard.
AccessibleDirectly Accessibility = 2
// AccessibleViaWildcardOnly indicates that the subject is only granted permission by virtue
// of a wildcard being present, i.e. the subject is not directly found for a relation used by
// the permission.
AccessibleViaWildcardOnly Accessibility = 3
// AccessibleBecauseTheSame indicates that the resource+permission and subject are exactly
// the same.
AccessibleBecauseTheSame Accessibility = 4
)
// AccessibilitySet is a helper for tracking the accessibility, permissions, resources
// and subjects found for consistency testing.
type AccessibilitySet struct {
// ResourcesByNamespace is a multimap of all defined resources, by resource namespace.
ResourcesByNamespace *mapz.MultiMap[string, *core.ObjectAndRelation]
// SubjectsByNamespace is a multimap of all defined subjects, by subject namespace.
SubjectsByNamespace *mapz.MultiMap[string, *core.ObjectAndRelation]
// RelationshipsByResourceNamespace is a multimap of all defined relationships, by resource namespace.
RelationshipsByResourceNamespace *mapz.MultiMap[string, *core.RelationTuple]
// UncomputedPermissionshipByRelationship is a map from a relationship string of the form
// "resourceType:resourceObjectID#permission@subjectType:subjectObjectID" to its
// associated *uncomputed* (i.e. caveats not processed) permissionship state.
UncomputedPermissionshipByRelationship map[string]dispatchv1.ResourceCheckResult_Membership
// PermissionshipByRelationship is a map from a relationship string of the form
// "resourceType:resourceObjectID#permission@subjectType:subjectObjectID" to its
// associated computed (i.e. caveats processed) permissionship state.
PermissionshipByRelationship map[string]dispatchv1.ResourceCheckResult_Membership
// AccessibilityByRelationship is a map from a relationship string of the form
// "resourceType:resourceObjectID#permission@subjectType:subjectObjectID" to its
// associated computed accessibility state.
AccessibilityByRelationship map[string]Accessibility
}
// BuildAccessibilitySet builds and returns an accessibility set for the given consistency
// cluster and data. Note that this function does *a lot* of checks, and should not be used
// outside of testing.
func BuildAccessibilitySet(t *testing.T, ccd ConsistencyClusterAndData) *AccessibilitySet {
// Compute all relationships and objects by namespace.
relsByResourceNamespace := mapz.NewMultiMap[string, *core.RelationTuple]()
resourcesByNamespace := mapz.NewMultiMap[string, *core.ObjectAndRelation]()
subjectsByNamespace := mapz.NewMultiMap[string, *core.ObjectAndRelation]()
allObjectIds := mapz.NewSet[string]()
for _, tpl := range ccd.Populated.Tuples {
relsByResourceNamespace.Add(tpl.ResourceAndRelation.Namespace, tpl)
resourcesByNamespace.Add(tpl.ResourceAndRelation.Namespace, tpl.ResourceAndRelation)
subjectsByNamespace.Add(tpl.Subject.Namespace, tpl.Subject)
allObjectIds.Add(tpl.ResourceAndRelation.ObjectId)
if tpl.Subject.ObjectId != tuple.PublicWildcard {
allObjectIds.Add(tpl.Subject.ObjectId)
}
}
// Run a *dispatched* check for each {resource+permission, defined subject} pair and
// record the results. Note that we use a dispatched check to ensure that we
// find caveated subjects. We then run a fully caveated-processed check on the
// caveated results to see if they are static.
//
// NOTE: We only conduct checks here for the *defined* subjects from the relationships,
// rather than every possible subject, as the latter would make the consistency test suite
// VERY slow, due to the combinatorial size of all possible subjects.
headRevision, err := ccd.DataStore.HeadRevision(ccd.Ctx)
require.NoError(t, err)
dispatcher := graph.NewLocalOnlyDispatcher(defaultConcurrencyLimit)
permissionshipByRelationship := map[string]dispatchv1.ResourceCheckResult_Membership{}
uncomputedPermissionshipByRelationship := map[string]dispatchv1.ResourceCheckResult_Membership{}
accessibilityByRelationship := map[string]Accessibility{}
for _, resourceType := range ccd.Populated.NamespaceDefinitions {
for _, possibleResourceID := range allObjectIds.AsSlice() {
for _, relationOrPermission := range resourceType.Relation {
for _, subject := range subjectsByNamespace.Values() {
if subject.ObjectId == tuple.PublicWildcard {
continue
}
resourceRelation := &core.RelationReference{
Namespace: resourceType.Name,
Relation: relationOrPermission.Name,
}
results, err := dispatcher.DispatchCheck(ccd.Ctx, &dispatchv1.DispatchCheckRequest{
ResourceRelation: resourceRelation,
ResourceIds: []string{possibleResourceID},
Subject: subject,
ResultsSetting: dispatchv1.DispatchCheckRequest_ALLOW_SINGLE_RESULT,
Metadata: &dispatchv1.ResolverMeta{
AtRevision: headRevision.String(),
DepthRemaining: 50,
TraversalBloom: dispatchv1.MustNewTraversalBloomFilter(50),
},
})
require.NoError(t, err)
resourceAndRelation := &core.ObjectAndRelation{
Namespace: resourceType.Name,
ObjectId: possibleResourceID,
Relation: relationOrPermission.Name,
}
permString := tuple.MustString(&core.RelationTuple{
ResourceAndRelation: resourceAndRelation,
Subject: subject,
})
if result, ok := results.ResultsByResourceId[possibleResourceID]; ok {
membership := result.Membership
uncomputedPermissionshipByRelationship[permString] = membership
// If the subject is caveated, run a computed check to determine if it
// statically has permission (or not). This can happen if the caveat context
// is fully specified on the relationship.
if membership == dispatchv1.ResourceCheckResult_CAVEATED_MEMBER {
cr, _, err := computed.ComputeCheck(ccd.Ctx, dispatcher,
computed.CheckParameters{
ResourceType: resourceRelation,
Subject: subject,
CaveatContext: nil,
AtRevision: headRevision,
MaximumDepth: 50,
},
possibleResourceID,
)
require.NoError(t, err)
membership = cr.Membership
}
permissionshipByRelationship[permString] = membership
switch membership {
case dispatchv1.ResourceCheckResult_NOT_MEMBER:
accessibilityByRelationship[permString] = NotAccessibleDueToPrespecifiedCaveat
case dispatchv1.ResourceCheckResult_CAVEATED_MEMBER:
fallthrough
case dispatchv1.ResourceCheckResult_MEMBER:
if resourceAndRelation.EqualVT(subject) {
accessibilityByRelationship[permString] = AccessibleBecauseTheSame
} else {
if isAccessibleViaWildcardOnly(t, ccd, dispatcher, headRevision, resourceAndRelation, subject) {
accessibilityByRelationship[permString] = AccessibleViaWildcardOnly
} else {
accessibilityByRelationship[permString] = AccessibleDirectly
}
}
default:
panic("unknown membership result")
}
} else {
uncomputedPermissionshipByRelationship[permString] = dispatchv1.ResourceCheckResult_NOT_MEMBER
permissionshipByRelationship[permString] = dispatchv1.ResourceCheckResult_NOT_MEMBER
accessibilityByRelationship[permString] = NotAccessible
}
}
}
}
}
return &AccessibilitySet{
RelationshipsByResourceNamespace: relsByResourceNamespace,
ResourcesByNamespace: resourcesByNamespace,
SubjectsByNamespace: subjectsByNamespace,
PermissionshipByRelationship: permissionshipByRelationship,
UncomputedPermissionshipByRelationship: uncomputedPermissionshipByRelationship,
AccessibilityByRelationship: accessibilityByRelationship,
}
}
// UncomputedPermissionshipFor returns the uncomputed permissionship for the given
// resource+permission and subject. If not found, returns false.
func (as *AccessibilitySet) UncomputedPermissionshipFor(resourceAndRelation *core.ObjectAndRelation, subject *core.ObjectAndRelation) (dispatchv1.ResourceCheckResult_Membership, bool) {
relString := tuple.MustString(&core.RelationTuple{
ResourceAndRelation: resourceAndRelation,
Subject: subject,
})
permissionship, ok := as.UncomputedPermissionshipByRelationship[relString]
return permissionship, ok
}
// AccessibiliyAndPermissionshipFor returns the computed accessibility and permissionship for the
// given resource+permission and subject. If not found, returns false.
func (as *AccessibilitySet) AccessibiliyAndPermissionshipFor(resourceAndRelation *core.ObjectAndRelation, subject *core.ObjectAndRelation) (Accessibility, dispatchv1.ResourceCheckResult_Membership, bool) {
relString := tuple.MustString(&core.RelationTuple{
ResourceAndRelation: resourceAndRelation,
Subject: subject,
})
accessibility, ok := as.AccessibilityByRelationship[relString]
if !ok {
return NotAccessible, dispatchv1.ResourceCheckResult_UNKNOWN, false
}
permissionship := as.PermissionshipByRelationship[relString]
return accessibility, permissionship, ok
}
// DirectlyAccessibleDefinedSubjects returns all subjects that have direct access/permission on the
// resource+permission. Direct access is defined as not being granted access via a wildcard.
func (as *AccessibilitySet) DirectlyAccessibleDefinedSubjects(resourceAndRelation *core.ObjectAndRelation) []*core.ObjectAndRelation {
found := make([]*core.ObjectAndRelation, 0)
for relString, accessibility := range as.AccessibilityByRelationship {
if accessibility != AccessibleDirectly {
continue
}
parsed := tuple.MustParse(relString)
if !parsed.ResourceAndRelation.EqualVT(resourceAndRelation) {
continue
}
found = append(found, parsed.Subject)
}
return found
}
// DirectlyAccessibleDefinedSubjectsOfType returns all subjects that have direct access/permission on the
// resource+permission and match the given subject type.
// Direct access is defined as not being granted access via a wildcard.
func (as *AccessibilitySet) DirectlyAccessibleDefinedSubjectsOfType(resourceAndRelation *core.ObjectAndRelation, subjectType *core.RelationReference) map[string]ObjectAndPermission {
found := map[string]ObjectAndPermission{}
for relString, accessibility := range as.AccessibilityByRelationship {
// NOTE: we also ignore subjects granted access by being themselves.
if accessibility != AccessibleDirectly && accessibility != AccessibleBecauseTheSame {
continue
}
parsed := tuple.MustParse(relString)
if !parsed.ResourceAndRelation.EqualVT(resourceAndRelation) {
continue
}
if parsed.Subject.Namespace != subjectType.Namespace || parsed.Subject.Relation != subjectType.Relation {
continue
}
permissionship := as.PermissionshipByRelationship[relString]
found[parsed.Subject.ObjectId] = ObjectAndPermission{
ObjectID: parsed.Subject.ObjectId,
IsCaveated: permissionship == dispatchv1.ResourceCheckResult_CAVEATED_MEMBER,
}
}
return found
}
// SubjectTypes returns all *defined* subject types found.
func (as *AccessibilitySet) SubjectTypes() []*core.RelationReference {
subjectTypes := map[string]*core.RelationReference{}
for _, subject := range as.SubjectsByNamespace.Values() {
rr := &core.RelationReference{
Namespace: subject.Namespace,
Relation: subject.Relation,
}
subjectTypes[tuple.StringRR(rr)] = rr
}
return maps.Values(subjectTypes)
}
// AllSubjectsNoWildcards returns all *defined*, non-wildcard subjects found.
func (as *AccessibilitySet) AllSubjectsNoWildcards() []*core.ObjectAndRelation {
subjects := make([]*core.ObjectAndRelation, 0)
seenSubjects := mapz.NewSet[string]()
for _, subject := range as.SubjectsByNamespace.Values() {
if subject.ObjectId == tuple.PublicWildcard {
continue
}
if seenSubjects.Add(tuple.StringONR(subject)) {
subjects = append(subjects, subject)
}
}
return subjects
}
// LookupAccessibleResources returns all resources of the given type that are accessible to the
// given subject.
func (as *AccessibilitySet) LookupAccessibleResources(resourceType *core.RelationReference, subject *core.ObjectAndRelation) map[string]ObjectAndPermission {
foundResources := map[string]ObjectAndPermission{}
for permString, permissionship := range as.PermissionshipByRelationship {
if permissionship == dispatchv1.ResourceCheckResult_NOT_MEMBER {
continue
}
parsed := tuple.MustParse(permString)
if parsed.ResourceAndRelation.Namespace != resourceType.Namespace ||
parsed.ResourceAndRelation.Relation != resourceType.Relation {
continue
}
if parsed.Subject.Namespace != subject.Namespace ||
parsed.Subject.ObjectId != subject.ObjectId ||
parsed.Subject.Relation != subject.Relation {
continue
}
foundResources[parsed.ResourceAndRelation.ObjectId] = ObjectAndPermission{
ObjectID: parsed.ResourceAndRelation.ObjectId,
IsCaveated: permissionship == dispatchv1.ResourceCheckResult_CAVEATED_MEMBER,
}
}
return foundResources
}
func isAccessibleViaWildcardOnly(
t *testing.T,
ccd ConsistencyClusterAndData,
dispatcher dispatch.Dispatcher,
revision datastore.Revision,
resourceAndPermission *core.ObjectAndRelation,
subject *core.ObjectAndRelation,
) bool {
resp, err := dispatcher.DispatchExpand(ccd.Ctx, &dispatchv1.DispatchExpandRequest{
ResourceAndRelation: resourceAndPermission,
Metadata: &dispatchv1.ResolverMeta{
AtRevision: revision.String(),
DepthRemaining: 100,
TraversalBloom: dispatchv1.MustNewTraversalBloomFilter(100),
},
ExpansionMode: dispatchv1.DispatchExpandRequest_RECURSIVE,
})
require.NoError(t, err)
subjectsFound, err := developmentmembership.AccessibleExpansionSubjects(resp.TreeNode)
require.NoError(t, err)
return !subjectsFound.Contains(subject)
}