chore: Update rego to be partial execution friendly #3449

Emyrk · 2022-08-10T04:04:55Z

What this does

Updates to a new rego policy that passes all the same tests. The new rego policy can be partially evaluated into simple queries. A unit was added to ensure the new policy always can be converted into these simple queries.

Performance

This does not affect performance when authorizing a single object. It only affects when using Filter.

Below is the Filter as is, vs the new filtering using Partial evaluation to optimize subsequent Auth() calls. Note this benchmark is using the new rego policy. The PR #3426 is using a different rego policy. So the benchmarks are expected to be different.

cpu: Intel(R) Core(TM) i7-6770HQ CPU @ 2.60GHz
BenchmarkRBACFilter/NoRoles-8              11178      104742 ns/op       44944 B/op      804 allocs/op
BenchmarkRBACFilter/Admin-8                 3532      314068 ns/op      101511 B/op      101 allocs/op
BenchmarkRBACFilter/OrgAdmin-8              3636      305136 ns/op       99223 B/op      997 allocs/op
BenchmarkRBACFilter/OrgMember-8             3472      318597 ns/op      101057 B/op      151 allocs/op
BenchmarkRBACFilter/ManyRoles-8             2389      527514 ns/op      161426 B/op      404 allocs/op

BenchmarkRBACFilter/NoRolesQueries-8              901699              1332 ns/op             137 B/op          3 allocs/op
BenchmarkRBACFilter/AdminQueries-8               2222412               636.1 ns/op           276 B/op          0 allocs/op
BenchmarkRBACFilter/OrgAdminQueries-8              29290             39604 ns/op           16264 B/op        305 allocs/op
BenchmarkRBACFilter/OrgMemberQueries-8             32221             36196 ns/op           14039 B/op        264 allocs/op
BenchmarkRBACFilter/ManyRolesQueries-8             43754             27587 ns/op           12949 B/op        243 allocs/op

Correctness

RBAC has a pretty good test suite, so I can pretty confidently say the behavior matches what we had before. Meaning false positives/negatives should not occur.

Notes

There is a difference between rego's Partial and PartialResult. PartialResult does not optimize in the same way Partial does. The reason Partial is much faster, is that the policy converts down to a set of queries based on the unknown fields (our new rego policy is designed to compress to these queries!)

opa eval --partial --format=pretty 'data.authz.allow = true' -d policy.rego --unknowns input.object.owner --unknowns input.object.org_owner -i input.json

+---------+--------------------------------------------------------------------+
| Query 1 | input.object.org_owner != ""                                       |
|         | input.object.org_owner in {"feda2e52-8bf1-42ce-ad75-6c5595cb297a"} |
|         | "me" = input.object.owner                                          |
+---------+--------------------------------------------------------------------+
| Query 2 | input.object.org_owner = ""                                        |
|         | "me" = input.object.owner                                          |
+---------+--------------------------------------------------------------------+

The number of queries and the content of the queries depends on the user's roles. The intention is to convert these queries into SQL WHERE clauses combined by an OR. Until we do that, we need to run through the queries ourselves, which as seen in the last benchmark, is quite fast.

Unfortunately this does slow down the unit tests :(

coderd/authorize.go

kylecarbs · 2022-08-10T20:37:57Z

coderd/rbac/authz.go

@@ -11,24 +11,35 @@ import (

 type Authorizer interface {
 	ByRoleName(ctx context.Context, subjectID string, roleNames []string, action Action, object Object) error
+	PrepareByRoleName(ctx context.Context, subjectID string, roles []string, action Action, objectType string) (PreparedAuthorized, error)


This function is only used internally, so seems like it might not need to be exported like this.

I need it for my Fake authorizer to work for some unit tests. I can't fake it without an interface ☹️

recordingAuthorizer always returns false and save the auth calls so I can assert them in my tests.

kylecarbs · 2022-08-10T20:39:45Z

coderd/authorize.go

+		return objects, nil
+	}
+	objecType := objects[0].RBACObject().Type
+	objects, err := rbac.Filter(r.Context(), api.Authorizer, roles.ID.String(), roles.Roles, action, objecType, objects)


Seems like all of this logic could be in the rbac package itself, then we wouldn't need the recordingAuthorizer code. Then functions could just call rbac.AuthorizeFilter directly.

You are right about the object type stuff 👍

As for recordingAuthorizer. That is needed for my unit test that checks all the routes. recordingAuthorizer is never used outside unit tests.

coderd/rbac/authz.go

coderd/rbac/authz_test.go

coderd/rbac/policy.rego

spikecurtis · 2022-08-10T22:12:00Z

coderd/rbac/authz.go

@@ -11,24 +11,35 @@ import (

 type Authorizer interface {
 	ByRoleName(ctx context.Context, subjectID string, roleNames []string, action Action, object Object) error
+	PrepareByRoleName(ctx context.Context, subjectID string, roles []string, action Action, objectType string) (PreparedAuthorized, error)


I don't see any use case for exposing the PreparedAuthorized to consumers of authorization --- why not just expose the Filter() method here?

I wish I could, but you can't make generic methods on structs. The nice thing about the generic Filter() method is you can pass in and return the same typed slice.

If I made it a non-generic function, you'd have to take your slice of []Workspace, convert it to []rbac.Object, and then convert it back to []Workspace. I could do this all in some rbac.Authorize, but it takes a lot of slice copying I prefer to avoid.

Well, that sucks. Go generics continue to disappoint.

Yea, it's really dumb because I don't see why it's not possible. Like I would like to know the objection to it.

coderd/rbac/auth_fake.go

coderd/rbac/authz_test.go

coderd/rbac/partial.go

spikecurtis · 2022-08-10T22:36:08Z

coderd/users_test.go

@@ -1209,7 +1209,7 @@ func TestPaginatedUsers(t *testing.T) {
 			t.Parallel()

 			// This test takes longer than a long time.
-			ctx, cancel := context.WithTimeout(context.Background(), testutil.WaitLong*2)
+			ctx, cancel := context.WithTimeout(context.Background(), testutil.WaitLong*3)


why did we increase timeout if we decreased RBAC time?

I am unsure why this test was timing out. I can spend more time and look into it

This test takes <3s on my local machine. I have no clue why it was timing out... going to drop back to *2 and see what I get.

- Move unit test to _internal - Remove example_test

coderd/rbac/policy.rego

Emyrk added 16 commits August 9, 2022 22:46

chore: Update rego to be partial execution friendly

b3536bc

test: Add unit test to verify partial query support

75e3a12

Add partial filtering and evaluation

6cdf575

Unfortunately this does slow down the unit tests :(

Benmark Partials

f5eacd0

Linting

4a7c68e

Spelling

df75be5

Fix recording fake authorizer

e90ac2d

Fix partial query tests

1e774e0

Working partial execution to queries

38917dc

Cleanup

e139a1f

Cleanup

c44d4d1

Add comments

19f3557

Spelling

f9dd9aa

Remove old Filter

bed9f4f

Improve error message

74d90f4

Comments

fe0d05a

Emyrk marked this pull request as ready for review August 10, 2022 20:22

Make test parallel

dd5c55c

Emyrk requested review from kylecarbs and spikecurtis August 10, 2022 20:30

kylecarbs reviewed Aug 10, 2022

View reviewed changes

Emyrk added 3 commits August 10, 2022 16:10

Fix typo

ae22f89

Drop an arg from Filter

0266963

Test timed out

af457b9

spikecurtis reviewed Aug 10, 2022

View reviewed changes

Emyrk added 5 commits August 11, 2022 10:07

Test less random, rename param

21f4f21

Add rego comments with explainations

2c87220

Add more rego comments

1c407ab

Move fakeauthorizer code

9f9b2d1

Unexport partial fields

ab55cf5

- Move unit test to _internal - Remove example_test

Emyrk added 2 commits August 11, 2022 13:38

Reduce wait

abf098d

Linting + Typos

44c7370

spikecurtis approved these changes Aug 11, 2022

View reviewed changes

coderd/rbac/policy.rego Outdated Show resolved Hide resolved

Emyrk added 3 commits August 11, 2022 15:38

Wording

4611322

Test runs long

c8e26a8

The single test is taking too long

510e94b

Emyrk enabled auto-merge (squash) August 11, 2022 22:00

Emyrk merged commit 3ae42f4 into main Aug 11, 2022

Emyrk deleted the stevenmasley/rbac_update_rego branch August 11, 2022 22:07

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

chore: Update rego to be partial execution friendly #3449

chore: Update rego to be partial execution friendly #3449

Emyrk commented Aug 10, 2022 •

edited

Loading

kylecarbs Aug 10, 2022

Emyrk Aug 10, 2022 •

edited

Loading

kylecarbs Aug 10, 2022

Emyrk Aug 10, 2022

spikecurtis Aug 10, 2022

Emyrk Aug 11, 2022

spikecurtis Aug 11, 2022

Emyrk Aug 11, 2022

spikecurtis Aug 10, 2022

Emyrk Aug 11, 2022

Emyrk Aug 11, 2022

chore: Update rego to be partial execution friendly #3449

chore: Update rego to be partial execution friendly #3449

Conversation

Emyrk commented Aug 10, 2022 • edited Loading

What this does

Performance

Correctness

Notes

Choose a reason for hiding this comment

Emyrk Aug 10, 2022 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Emyrk commented Aug 10, 2022 •

edited

Loading

Emyrk Aug 10, 2022 •

edited

Loading