apache / apache/casbin

[Bug] Performance issue in RBAC with pattern matching domains

Open
#1,004 9 comments 1 reaction 1 assignee Claimed by @hsluoyz View on GitHub
bug
Dominant language
Go
Stars
20.4k
Forks
1.8k
Avg merge
5d 11h
Merged PRs (30d)
2

Description

**Describe the bug**
When I modify the `BenchmarkRBACModelWithDomainPatternLarge` [performance test](https://github.com/casbin/casbin/blob/master/model_b_test.go#L269-L277) to add a bunch of unrelated users and then try to fetch an unauthorized resource, I see an exponential number of calls to the domain matching function `util.KeyMatch4`, resulting in exponentially bad performance related to the number of additional users.

For context, I am trying to use a model.conf similar to this large scale performance test, but I am hitting massive performance issues when many different users with different domains are added.

**To Reproduce**
I've modified the existing `BenchmarkRBACModelWithDomainPatternLarge` benchmark test to first add 1000 unrelated users with different domains to the unrelated role `staffOrgUser`. The result is that each of these users are being evaluated an exponential number of times when we try to run the enforcer.

```
func BenchmarkRBACModelWithDomainPatternLarge(b *testing.B) {
e, _ := NewEnforcer("examples/performance/rbac_with_pattern_large_scale_model.conf", "examples/performance/rbac_with_pattern_large_scale_policy.csv")
e.AddNamedDomainMatchingFunc("g", "keyMatch4", util.KeyMatch4)

_ = e.BuildRoleLinks()
for i := 0; i < 1000; i++ {
orgID := rand.Int()
user := fmt.Sprintf("staffUser%d", orgID)
role := fmt.Sprintf("staffOrgUser")
dom := fmt.Sprintf("/orgs/%d/sites/*", orgID)
if err := e.GetRoleManager().AddLink(user, role, dom); err != nil {
b.Fatal(err)
}
}

b.ResetTimer()
for i := 0; i < b.N; i++ {
const unauthorizedSite = "/orgs/999/sites/site001"
_, _ = e.Enforce("staffUser1001", unauthorizedSite, "App001.Module001.Action1001")
}
}
```

This results in an exponential number of calls to `util.KeyMatch4` (the domain matching function), exponentially related to the number of users added. (e.g. if I increase `1000` to `10000`, the benchmark never ends).

```
goos: darwin
goarch: amd64
pkg: github.com/casbin/casbin/v2
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkRBACModelWithDomainPatternLarge-12 19 61330779 ns/op
PASS
```

**Expected behavior**
Without these additional 1000 users, the performance is:
```
goos: darwin
goarch: amd64
pkg: github.com/casbin/casbin/v2
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkRBACModelWithDomainPatternLarge-12 7998 139011 ns/op
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.