CVE-2023-43645: Loop with Unreachable Exit Condition ('Infinite Loop') (CWE-835)
value: OpenFGA is an authorization/permission engine built for developers and inspired by Google Zanzibar. OpenFGA is vulnerable to a denial of service attack when certain Check calls are executed against authorization models that contain circular relationship definitions. When the call is made, it's possible for the server to exhaust resources and die. Users are advised to upgrade to v1.3.2 and update any offending models. There are no known workarounds for this vulnerability. Note that for models which contained cycles or a relation definition that has the relation itself in its evaluation path, checks and queries that require evaluation will no longer be evaluated on v1.3.2+ and will return errors instead. Users who do not have cyclic models are unaffected.
CWE description: The product contains an iteration or loop with an exit condition that cannot be reached, i.e., an infinite loop.
CVSS v3 base score: 5.9
Published: 2023-09-27T15:19Z
Repository: https://github.com/openfga/openfga
Language: Go
Files changed: CHANGELOG.md, internal/graph/check.go, internal/graph/check_test.go, pkg/server/commands/list_objects.go, pkg/server/commands/reverseexpand/reverse_expand.go, pkg/server/server.go, pkg/server/server_test.go, pkg/server/test/reverse_expand.go, pkg/server/test/write_authzmodel.go, pkg/typesystem/typesystem.go, pkg/typesystem/typesystem_test.go
Commit date: 2023-09-26 12:12:49 -0600
Commit message: Merge pull request from GHSA-2hm9-h873-pgqh

* fix: avoid revisiting computed relations in cycles

* Revert "fix: avoid revisiting computed relations in cycles"

This reverts commit 5d51d4fdcca1eb240310037c92d9085381866ed4.

* fix: validate against cyclical model definitions more accurately

* chore: drop unused code and wire up visited paths betweeen calls

* chore: touch up tests and restructure visited evaluation paths

* docs(release): add `v1.3.2` release notes to CHANGELOG

* Update CHANGELOG.md

Co-authored-by: Adrian Tam <adrian.tam@okta.com>

* docs(release): add additional contributions to v1.3.2 release notes

* docs(release): drop extra link added erroneously

* docs(release): add breaking compability notice

---------

Co-authored-by: Adrian Tam <adrian.tam@okta.com>
Diff: diff --git a/CHANGELOG.md b/CHANGELOG.md
index 53e76ab..9f06e84 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -6,10 +6,32 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 
 Try to keep listed changes to a concise bulleted list of simple explanations of changes. Aim for the amount of information needed so that readers can understand where they would look in the codebase to investigate the changes' implementation, or where they would look in the documentation to understand how to make use of the change in practice - better yet, link directly to the docs and provide detailed information there. Only elaborate if doing so is required to avoid breaking changes or experimental features from ruining someone's day.
 
 ## [Unreleased]
 
+## [1.3.2] - 2023-08-25
+### Added
+* Support TLS for OTLP trace endpoint ([#885](https://github.com/openfga/openfga/pull/885)) - thanks @matoous
+* Configurable limits to database reads per ListObjects query ([#967](https://github.com/openfga/openfga/pull/967))
+* Datastore query count labels to traces and query latency histogram in ListObjects ([#959](https://github.com/openfga/openfga/pull/959))
+* Github workflow to check markdown links ([#1016](https://github.com/openfga/openfga/pull/1016)) - thanks @sanketrai1
+
+### Fixed
+* Change response code to internal error for concurrency conflicts ([#1011](https://github.com/openfga/openfga/pull/1011))
+
+### Changed
+* Use slices and maps packages from go1.21 ([#969](https://github.com/openfga/openfga/pull/969)) - thanks @tranngoclam
+* Moved request validations to RPC handlers so library integrations benefit ([#975](https://github.com/openfga/openfga/pull/975), [#998](https://github.com/openfga/openfga/pull/998))
+* Refactored internal usages of ConnectedObjects to ReverseExpand ([#968](https://github.com/openfga/openfga/pull/968))
+* Expose validation middleware ([#1005](https://github.com/openfga/openfga/pull/1005))
+* Upgrade grpc validator middleware to the latest v2 package ([#1019](https://github.com/openfga/openfga/pull/1019)) - thanks @tranngoclam
+
+### Security
+* Patches [CVE-2023-43645](https://github.com/openfga/openfga/security/advisories/GHSA-2hm9-h873-pgqh) - see the CVE for more details
+
+  **[BREAKING]** If your model contained cycles or a relation definition that has the relation itself in its evaluation path, then Checks and queries that require evaluation will no longer be evaluated on v1.3.2+ and will return errors instead. You will need to update your models to remove the cycles.
+
 ## [1.3.1] - 2023-08-23
 
 ### Added
 * Count datastore queries involved in Check resolution metadata ([#880](https://github.com/openfga/openfga/pull/880))
 
@@ -624,11 +646,12 @@ no tuple key instead.
 * Initial working implementation of OpenFGA APIs (Check, Expand, Write, Read, Authorization Models, etc..)
 * Postgres storage adapter implementation
 * Memory storage adapter implementation
 * Early support for preshared key or OIDC authentication methods
 
-[Unreleased]: https://github.com/openfga/openfga/compare/v1.3.1...HEAD
+[Unreleased]: https://github.com/openfga/openfga/compare/v1.3.2...HEAD
+[1.3.2]: https://github.com/openfga/openfga/releases/tag/v1.3.2
 [1.3.1]: https://github.com/openfga/openfga/releases/tag/v1.3.1
 [1.3.0]: https://github.com/openfga/openfga/releases/tag/v1.3.0
 [1.2.0]: https://github.com/openfga/openfga/releases/tag/v1.2.0
 [1.1.1]: https://github.com/openfga/openfga/releases/tag/v1.1.1
 [1.1.0]: https://github.com/openfga/openfga/releases/tag/v1.1.0
diff --git a/internal/graph/check.go b/internal/graph/check.go
index 4449d6a..358ce7a 100644
--- a/internal/graph/check.go
+++ b/internal/graph/check.go
@@ -14,26 +14,36 @@ import (
 	"github.com/openfga/openfga/pkg/tuple"
 	"github.com/openfga/openfga/pkg/typesystem"
 	"go.opentelemetry.io/otel"
 	"go.opentelemetry.io/otel/attribute"
 	"go.opentelemetry.io/otel/trace"
+	"golang.org/x/exp/maps"
 )
 
 var tracer = otel.Tracer("internal/graph/check")
 
 const (
 	// same values as run.DefaultConfig() (TODO break the import cycle, remove these hardcoded values and import those constants here)
 	defaultResolveNodeBreadthLimit    = 25
 	defaultMaxConcurrentReadsForCheck = math.MaxUint32
 )
 
+var (
+	ErrCycleDetected = errors.New("a cycle has been detected")
+)
+
+var cycleDetectedCheckHandler = func(ctx context.Context) (*ResolveCheckResponse, error) {
+	return nil, ErrCycleDetected
+}
+
 type ResolveCheckRequest struct {
 	StoreID              string
 	AuthorizationModelID string
 	TupleKey             *openfgav1.TupleKey
 	ContextualTuples     []*openfgav1.TupleKey
 	ResolutionMetadata   *ResolutionMetadata
+	VisitedPaths         map[string]struct{}
 }
 
 type ResolveCheckResponse struct {
 	Allowed            bool
 	ResolutionMetadata *ResolutionMetadata
@@ -457,10 +467,23 @@ func (c *LocalChecker) ResolveCheck(
 	rel, err := typesys.GetRelation(objectType, relation)
 	if err != nil {
 		return nil, fmt.Errorf("relation '%s' undefined for object type '%s'", relation, objectType)
 	}
 
+	if req.VisitedPaths != nil {
+
+		if _, visited := req.VisitedPaths[tuple.TupleKeyToString(req.GetTupleKey())]; visited {
+			return nil, ErrCycleDetected
+		}
+
+		req.VisitedPaths[tuple.TupleKeyToString(req.GetTupleKey())] = struct{}{}
+	} else {
+		req.VisitedPaths = map[string]struct{}{
+			tuple.TupleKeyToString(req.GetTupleKey()): {},
+		}
+	}
+
 	resp, err := union(ctx, c.concurrencyLimit, c.checkRewrite(ctx, req, rel.GetRewrite()))
 	if err != nil {
 		return nil, err
 	}
 
@@ -583,20 +606,27 @@ func (c *LocalChecker) checkDirect(parentctx context.Context, req *ResolveCheckR
 
 					continue
 				}
 
 				if usersetRelation != "" {
+					tupleKey := tuple.NewTupleKey(usersetObject, usersetRelation, tk.GetUser())
+
+					if _, visited := req.VisitedPaths[tuple.TupleKeyToString(tupleKey)]; visited {
+						return nil, ErrCycleDetected
+					}
+
 					handlers = append(handlers, c.dispatch(
 						ctx,
 						&ResolveCheckRequest{
 							StoreID:              storeID,
 							AuthorizationModelID: req.GetAuthorizationModelID(),
-							TupleKey:             tuple.NewTupleKey(usersetObject, usersetRelation, tk.GetUser()),
+							TupleKey:             tupleKey,
 							ResolutionMetadata: &ResolutionMetadata{
 								Depth:               req.GetResolutionMetadata().Depth - 1,
 								DatastoreQueryCount: response.GetResolutionMetadata().DatastoreQueryCount,
 							},
+							VisitedPaths: maps.Clone(req.VisitedPaths),
 						}))
 				}
 			}
 
 			if len(handlers) == 0 {
@@ -626,28 +656,36 @@ func (c *LocalChecker) checkDirect(parentctx context.Context, req *ResolveCheckR
 	}
 }
 
 // checkComputedUserset evaluates the Check request with the rewritten relation (e.g. the computed userset relation).
 func (c *LocalChecker) checkComputedUserset(parentctx context.Context, req *ResolveCheckRequest, rewrite *openfgav1.Userset_ComputedUserset) CheckHandlerFunc {
+
 	return func(ctx context.Context) (*ResolveCheckResponse, error) {
 		ctx, span := tracer.Start(ctx, "checkComputedUserset")
 		defer span.End()
 
+		rewrittenTupleKey := tuple.NewTupleKey(
+			req.TupleKey.GetObject(),
+			rewrite.ComputedUserset.GetRelation(),
+			req.TupleKey.GetUser(),
+		)
+
+		if _, visited := req.VisitedPaths[tuple.TupleKeyToString(rewrittenTupleKey)]; visited {
+			return nil, ErrCycleDetected
+		}
+
 		return c.dispatch(
 			ctx,
 			&ResolveCheckRequest{
 				StoreID:              req.GetStoreID(),
 				AuthorizationModelID: req.GetAuthorizationModelID(),
-				TupleKey: tuple.NewTupleKey(
-					req.TupleKey.GetObject(),
-					rewrite.ComputedUserset.GetRelation(),
-					req.TupleKey.GetUser(),
-				),
+				TupleKey:             rewrittenTupleKey,
 				ResolutionMetadata: &ResolutionMetadata{
 					Depth:               req.GetResolutionMetadata().Depth - 1,
 					DatastoreQueryCount: req.GetResolutionMetadata().DatastoreQueryCount,
 				},
+				VisitedPaths: maps.Clone(req.VisitedPaths),
 			})(ctx)
 	}
 }
 
 // checkTTU looks up all tuples of the target tupleset relation on the provided object and for each one
@@ -720,20 +758,25 @@ func (c *LocalChecker) checkTTU(parentctx context.Context, req *ResolveCheckRequ
 				if errors.Is(err, typesystem.ErrRelationUndefined) {
 					continue // skip computed relations on tupleset relationships if they are undefined
 				}
 			}
 
+			if _, visited := req.VisitedPaths[tuple.TupleKeyToString(tupleKey)]; visited {
+				return nil, ErrCycleDetected
+			}
+
 			handlers = append(handlers, c.dispatch(
 				ctx,
 				&ResolveCheckRequest{
 					StoreID:              req.GetStoreID(),
 					AuthorizationModelID: req.GetAuthorizationModelID(),
 					TupleKey:             tupleKey,
 					ResolutionMetadata: &ResolutionMetadata{
 						Depth:               req.GetResolutionMetadata().Depth - 1,
 						DatastoreQueryCount: req.GetResolutionMetadata().DatastoreQueryCount, // add TTU read below
 					},
+					VisitedPaths: maps.Clone(req.VisitedPaths),
 				}))
 		}
 
 		if len(handlers) == 0 {
 			return response, nil
diff --git a/internal/graph/check_test.go b/internal/graph/check_test.go
index 1f73163..0b43c7d 100644
--- a/internal/graph/check_test.go
+++ b/internal/graph/check_test.go
@@ -320,5 +320,103 @@ func TestCheckDatastoreQueryCount(t *testing.T) {
 				})
 			}
 		})
 	}
 }
+
+// TestCheckWithUnexpectedCycle tests the LocalChecker to make sure that if a model includes a cycle
+// that should have otherwise been invalid according to the typesystem, then the check resolution will
+// avoid the cycle and return an error indicating a cycle was detected.
+func TestCheckWithUnexpectedCycle(t *testing.T) {
+	ds := memory.New()
+	defer ds.Close()
+
+	storeID := ulid.Make().String()
+
+	err := ds.Write(context.Background(), storeID, nil, []*openfgav1.TupleKey{
+		tuple.NewTupleKey("resource:1", "parent", "resource:1"),
+	})
+	require.NoError(t, err)
+
+	tests := []struct {
+		name     string
+		model    string
+		tupleKey *openfgav1.TupleKey
+	}{
+		{
+			name: "test_1",
+			model: `
+			type user
+
+			type resource
+			  relations
+				define x: [user] as self but not y
+				define y: [user] as self but not z
+				define z: [user] as self or x
+			`,
+			tupleKey: tuple.NewTupleKey("resource:1", "x", "user:jon"),
+		},
+		{
+			name: "test_2",
+			model: `
+			type user
+
+			type resource
+			  relations
+				define x: [user] as self and y
+				define y: [user] as self and z
+				define z: [user] as self or x
+			`,
+			tupleKey: tuple.NewTupleKey("resource:1", "x", "user:jon"),
+		},
+		{
+			name: "test_3",
+			model: `
+			type resource
+			  relations
+				define x as y
+				define y as x
+			`,
+			tupleKey: tuple.NewTupleKey("resource:1", "x", "user:jon"),
+		},
+		{
+			name: "test_4",
+			model: `
+			type resource
+			  relations
+			    define parent: [resource] as self
+				define x: [user] as self or x from parent
+			`,
+			tupleKey: tuple.NewTupleKey("resource:1", "x", "user:jon"),
+		},
+	}
+
+	checker := NewLocalChecker(ds)
+
+	for _, test := range tests {
+		typedefs := parser.MustParse(test.model)
+
+		ctx := typesystem.ContextWithTypesystem(context.Background(), typesystem.New(
+			&openfgav1.AuthorizationModel{
+				Id:              ulid.Make().String(),
+				TypeDefinitions: typedefs,
+				SchemaVersion:   typesystem.SchemaVersion1_1,
+			},
+		))
+
+		resp, err := checker.ResolveCheck(ctx, &ResolveCheckRequest{
+			StoreID:            storeID,
+			TupleKey:           test.tupleKey,
+			ResolutionMetadata: &ResolutionMetadata{Depth: 25},
+		})
+
+		// if the branch producing the cycle is reached first, then an error is returned, otherwise
+		// a result is returned if some other terminal path of evaluation was reached before the cycle
+		if err != nil {
+			require.ErrorIs(t, err, ErrCycleDetected)
+		} else {
+			require.False(t, resp.GetAllowed())
+			require.GreaterOrEqual(t, resp.ResolutionMetadata.DatastoreQueryCount, uint32(1)) // min of 1 (x) if x isn't found and it returns quickly
+			require.LessOrEqual(t, resp.ResolutionMetadata.DatastoreQueryCount, uint32(3))    // max of 3 (x, y, z) before the cycle
+		}
+	}
+}
diff --git a/pkg/server/commands/list_objects.go b/pkg/server/commands/list_objects.go
index f44b0ca..2d9277c 100644
--- a/pkg/server/commands/list_objects.go
+++ b/pkg/server/commands/list_objects.go
@@ -232,10 +232,15 @@ func (q *ListObjectsQuery) evaluate(
 				Relation:         targetRelation,
 				User:             sourceUserRef,
 				ContextualTuples: req.GetContextualTuples().GetTupleKeys(),
 			}, reverseExpandResultsChan, resolutionMetadata)
 			if err != nil {
+				if errors.Is(err, graph.ErrResolutionDepthExceeded) || errors.Is(err, graph.ErrCycleDetected) {
+					resultsChan <- ListObjectsResult{Err: serverErrors.AuthorizationModelResolutionTooComplex}
+					return
+				}
+
 				resultsChan <- ListObjectsResult{Err: err}
 			}
 
 			// this is necessary to terminate the range loop below
 			close(reverseExpandResultsChan)
@@ -280,10 +285,15 @@ func (q *ListObjectsQuery) evaluate(
 					ResolutionMetadata: &graph.ResolutionMetadata{
 						Depth: q.resolveNodeLimit,
 					},
 				})
 				if err != nil {
+					if errors.Is(err, graph.ErrResolutionDepthExceeded) || errors.Is(err, graph.ErrCycleDetected) {
+						resultsChan <- ListObjectsResult{Err: serverErrors.AuthorizationModelResolutionTooComplex}
+						return
+					}
+
 					resultsChan <- ListObjectsResult{Err: err}
 					return
 				}
 				atomic.AddUint32(resolutionMetadata.QueryCount, resp.GetResolutionMetadata().DatastoreQueryCount)
 
@@ -354,10 +364,11 @@ func (q *ListObjectsQuery) Execute(
 		case result, channelOpen := <-resultsChan:
 			if result.Err != nil {
 				if errors.Is(result.Err, serverErrors.AuthorizationModelResolutionTooComplex) {
 					return nil, result.Err
 				}
+
 				return nil, serverErrors.HandleError("", result.Err)
 			}
 
 			if !channelOpen {
 				return &ListObjectsResponse{
diff --git a/pkg/server/commands/reverseexpand/reverse_expand.go b/pkg/server/commands/reverseexpand/reverse_expand.go
index 40af1fd..2bfc741 100644
--- a/pkg/server/commands/reverseexpand/reverse_expand.go
+++ b/pkg/server/commands/reverseexpand/reverse_expand.go
@@ -8,11 +8,10 @@ import (
 	"sync"
 	"sync/atomic"
 
 	openfgav1 "github.com/openfga/api/proto/openfga/v1"
 	"github.com/openfga/openfga/internal/graph"
-	serverErrors "github.com/openfga/openfga/pkg/server/errors"
 	"github.com/openfga/openfga/pkg/storage"
 	"github.com/openfga/openfga/pkg/storage/storagewrappers"
 	"github.com/openfga/openfga/pkg/tuple"
 	"github.com/openfga/openfga/pkg/typesystem"
 	"go.opentelemetry.io/otel"
@@ -207,11 +206,11 @@ func (c *ReverseExpandQuery) execute(
 	depth, ok := graph.ResolutionDepthFromContext(ctx)
 	if !ok {
 		ctx = graph.ContextWithResolutionDepth(ctx, 0)
 	} else {
 		if depth >= c.resolveNodeLimit {
-			return serverErrors.AuthorizationModelResolutionTooComplex
+			return graph.ErrResolutionDepthExceeded
 		}
 
 		ctx = graph.ContextWithResolutionDepth(ctx, depth+1)
 	}
 
diff --git a/pkg/server/server.go b/pkg/server/server.go
index 1b0f8bd..dc57104 100644
--- a/pkg/server/server.go
+++ b/pkg/server/server.go
@@ -584,11 +584,11 @@ func (s *Server) Check(ctx context.Context, req *openfgav1.CheckRequest) (*openf
 			Depth:               s.resolveNodeLimit,
 			DatastoreQueryCount: 0,
 		},
 	})
 	if err != nil {
-		if errors.Is(err, graph.ErrResolutionDepthExceeded) {
+		if errors.Is(err, graph.ErrResolutionDepthExceeded) || errors.Is(err, graph.ErrCycleDetected) {
 			return nil, serverErrors.AuthorizationModelResolutionTooComplex
 		}
 
 		return nil, serverErrors.HandleError("", err)
 	}
diff --git a/pkg/server/server_test.go b/pkg/server/server_test.go
index b1ad4b2..8143ed3 100644
--- a/pkg/server/server_test.go
+++ b/pkg/server/server_test.go
@@ -554,261 +554,132 @@ func BenchmarkListObjectsNoRaceCondition(b *testing.B) {
 
 		require.ErrorIs(b, err, serverErrors.NewInternalError("", errors.New("error reading from storage")))
 	}
 }
 
-// This test ensures that when the data storage fails, ListObjects v0 throws an error
-func TestListObjects_Unoptimized_UnhappyPaths(t *testing.T) {
+func TestListObjects_ErrorCases(t *testing.T) {
 	ctx := context.Background()
 	store := ulid.Make().String()
-	modelID := ulid.Make().String()
 
 	mockController := gomock.NewController(t)
 	defer mockController.Finish()
 
-	mockDatastore := mockstorage.NewMockOpenFGADatastore(mockController)
-
-	mockDatastore.EXPECT().ReadAuthorizationModel(gomock.Any(), store, modelID).AnyTimes().Return(&openfgav1.AuthorizationModel{
-		SchemaVersion: typesystem.SchemaVersion1_1,
-		TypeDefinitions: parser.MustParse(`
-		type user
-
-		type repo
-		  relations
-		    define allowed: [user] as self
-		    define viewer: [user] as self and allowed
-		`),
-	}, nil)
-	mockDatastore.EXPECT().ReadStartingWithUser(gomock.Any(), store, gomock.Any()).AnyTimes().Return(nil, errors.New("error reading from storage"))
-
-	s := MustNewServerWithOpts(
-		WithDatastore(mockDatastore),
-	)
-
-	t.Run("error_listing_objects_from_storage_in_non-streaming_version", func(t *testing.T) {
-		res, err := s.ListObjects(ctx, &openfgav1.ListObjectsRequest{
-			StoreId:              store,
-			AuthorizationModelId: modelID,
-			Type:                 "repo",
-			Relation:             "viewer",
-			User:                 "user:bob",
-		})
-
-		require.Nil(t, res)
-		require.ErrorIs(t, err, serverErrors.NewInternalError("", errors.New("error reading from storage")))
-	})
-
-	t.Run("error_listing_objects_from_storage_in_streaming_version", func(t *testing.T) {
-		err := s.StreamedListObjects(&openfgav1.StreamedListObjectsRequest{
-			StoreId:              store,
-			AuthorizationModelId: modelID,
-			Type:                 "repo",
-			Relation:             "viewer",
-			User:                 "user:bob",
-		}, NewMockStreamServer())
-
-		require.ErrorIs(t, err, serverErrors.NewInternalError("", errors.New("error reading from storage")))
-	})
-}
-
-// This test ensures that when the data storage fails for known eror, ListObjects v0 throws the correct error
-func TestListObjects_Unoptimized_UnhappyPaths_Known_Error(t *testing.T) {
-	ctx := context.Background()
-	store := ulid.Make().String()
-	modelID := ulid.Make().String()
+	t.Run("database_errors", func(t *testing.T) {
+		mockDatastore := mockstorage.NewMockOpenFGADatastore(mockController)
 
-	mockController := gomock.NewController(t)
-	defer mockController.Finish()
+		s := MustNewServerWithOpts(
+			WithDatastore(mockDatastore),
+		)
 
-	mockDatastore := mockstorage.NewMockOpenFGADatastore(mockController)
+		modelID := ulid.Make().String()
 
-	mockDatastore.EXPECT().ReadAuthorizationModel(gomock.Any(), store, modelID).AnyTimes().Return(&openfgav1.AuthorizationModel{
-		SchemaVersion: typesystem.SchemaVersion1_1,
-		TypeDefinitions: parser.MustParse(`
-		type user
-
-		type repo
-		  relations
-		    define allowed: [user] as self
-		    define viewer: [user] as self and allowed
-		`),
-	}, nil)
-	mockDatastore.EXPECT().ReadStartingWithUser(gomock.Any(), store, gomock.Any()).AnyTimes().Return(nil, serverErrors.AuthorizationModelResolutionTooComplex)
+		mockDatastore.EXPECT().ReadAuthorizationModel(gomock.Any(), store, modelID).AnyTimes().Return(&openfgav1.AuthorizationModel{
+			SchemaVersion: typesystem.SchemaVersion1_1,
+			TypeDefinitions: parser.MustParse(`
+			type user
+	
+			type document
+			  relations
+				define viewer: [user, user:*] as self
+			`),
+		}, nil)
 
-	s := MustNewServerWithOpts(
-		WithDatastore(mockDatastore),
-	)
+		mockDatastore.EXPECT().ReadStartingWithUser(gomock.Any(), store, storage.ReadStartingWithUserFilter{
+			ObjectType: "document",
+			Relation:   "viewer",
+			UserFilter: []*openfgav1.ObjectRelation{
+				{Object: "user:*"},
+				{Object: "user:bob"},
+			}}).AnyTimes().Return(nil, errors.New("error reading from storage"))
+
+		t.Run("error_listing_objects_from_storage_in_non-streaming_version", func(t *testing.T) {
+			res, err := s.ListObjects(ctx, &openfgav1.ListObjectsRequest{
+				StoreId:              store,
+				AuthorizationModelId: modelID,
+				Type:                 "document",
+				Relation:             "viewer",
+				User:                 "user:bob",
+			})
 
-	t.Run("error_listing_objects_from_storage_in_non-streaming_version", func(t *testing.T) {
-		res, err := s.ListObjects(ctx, &openfgav1.ListObjectsRequest{
-			StoreId:              store,
-			AuthorizationModelId: modelID,
-			Type:                 "repo",
-			Relation:             "viewer",
-			User:                 "user:bob",
+			require.Nil(t, res)
+			require.ErrorIs(t, err, serverErrors.NewInternalError("", errors.New("error reading from storage")))
 		})
 
-		require.Nil(t, res)
-		require.ErrorIs(t, err, serverErrors.AuthorizationModelResolutionTooComplex)
-	})
-
-	t.Run("error_listing_objects_from_storage_in_streaming_version", func(t *testing.T) {
-		err := s.StreamedListObjects(&openfgav1.StreamedListObjectsRequest{
-			StoreId:              store,
-			AuthorizationModelId: modelID,
-			Type:                 "repo",
-			Relation:             "viewer",
-			User:                 "user:bob",
-		}, NewMockStreamServer())
-
-		require.ErrorIs(t, err, serverErrors.AuthorizationModelResolutionTooComplex)
-	})
-}
-
-// This test ensures that when the data storage fails, ListObjects v1 throws an error
-func TestListObjects_UnhappyPaths(t *testing.T) {
-	ctx := context.Background()
-	store := ulid.Make().String()
-	modelID := ulid.Make().String()
-
-	mockController := gomock.NewController(t)
-	defer mockController.Finish()
-
-	mockDatastore := mockstorage.NewMockOpenFGADatastore(mockController)
-
-	mockDatastore.EXPECT().ReadAuthorizationModel(gomock.Any(), store, modelID).AnyTimes().Return(&openfgav1.AuthorizationModel{
-		SchemaVersion: typesystem.SchemaVersion1_1,
-		TypeDefinitions: []*openfgav1.TypeDefinition{
-			{
-				Type: "user",
-			},
-			{
-				Type: "document",
-				Relations: map[string]*openfgav1.Userset{
-					"viewer": typesystem.This(),
-				},
-				Metadata: &openfgav1.Metadata{
-					Relations: map[string]*openfgav1.RelationMetadata{
-						"viewer": {
-							DirectlyRelatedUserTypes: []*openfgav1.RelationReference{
-								typesystem.DirectRelationReference("user", ""),
-								typesystem.WildcardRelationReference("user"),
-							},
-						},
-					},
-				},
-			},
-		},
-	}, nil)
-	mockDatastore.EXPECT().ReadStartingWithUser(gomock.Any(), store, storage.ReadStartingWithUserFilter{
-		ObjectType: "document",
-		Relation:   "viewer",
-		UserFilter: []*openfgav1.ObjectRelation{
-			{Object: "user:*"},
-			{Object: "user:bob"},
-		}}).AnyTimes().Return(nil, errors.New("error reading from storage"))
-
-	s := MustNewServerWithOpts(
-		WithDatastore(mockDatastore),
-	)
+		t.Run("error_listing_objects_from_storage_in_streaming_version", func(t *testing.T) {
+			err := s.StreamedListObjects(&openfgav1.StreamedListObjectsRequest{
+				StoreId:              store,
+				AuthorizationModelId: modelID,
+				Type:                 "document",
+				Relation:             "viewer",
+				User:                 "user:bob",
+			}, NewMockStreamServer())
 
-	t.Run("error_listing_objects_from_storage_in_non-streaming_version", func(t *testing.T) {
-		res, err := s.ListObjects(ctx, &openfgav1.ListObjectsRequest{
-			StoreId:              store,
-			AuthorizationModelId: modelID,
-			Type:                 "document",
-			Relation:             "viewer",
-			User:                 "user:bob",
+			require.ErrorIs(t, err, serverErrors.NewInternalError("", errors.New("error reading from storage")))
 		})
-
-		require.Nil(t, res)
-		require.ErrorIs(t, err, serverErrors.NewInternalError("", errors.New("error reading from storage")))
 	})
 
-	t.Run("error_listing_objects_from_storage_in_streaming_version", func(t *testing.T) {
-		err := s.StreamedListObjects(&openfgav1.StreamedListObjectsRequest{
-			StoreId:              store,
-			AuthorizationModelId: modelID,
-			Type:                 "document",
-			Relation:             "viewer",
-			User:                 "user:bob",
-		}, NewMockStreamServer())
+	t.Run("graph_resolution_errors", func(t *testing.T) {
 
-		require.ErrorIs(t, err, serverErrors.NewInternalError("", errors.New("error reading from storage")))
-	})
-}
+		s := MustNewServerWithOpts(
+			WithDatastore(memory.New()),
+			WithResolveNodeLimit(2),
+		)
 
-// This test ensures that when the data storage fails with known errors, ListObjects v1 throws an error
-func TestListObjects_UnhappyPaths_Known_Error(t *testing.T) {
-	ctx := context.Background()
-	store := ulid.Make().String()
-	modelID := ulid.Make().String()
+		writeModelResp, err := s.WriteAuthorizationModel(ctx, &openfgav1.WriteAuthorizationModelRequest{
+			StoreId:       store,
+			SchemaVersion: typesystem.SchemaVersion1_1,
+			TypeDefinitions: parser.MustParse(`
+			type user
 
-	mockController := gomock.NewController(t)
-	defer mockController.Finish()
+			type group
+			  relations
+			    define member: [user, group#member] as self
 
-	mockDatastore := mockstorage.NewMockOpenFGADatastore(mockController)
+			type document
+			  relations
+				define viewer: [group#member] as self
+			`),
+		})
+		require.NoError(t, err)
 
-	mockDatastore.EXPECT().ReadAuthorizationModel(gomock.Any(), store, modelID).AnyTimes().Return(&openfgav1.AuthorizationModel{
-		SchemaVersion: typesystem.SchemaVersion1_1,
-		TypeDefinitions: []*openfgav1.TypeDefinition{
-			{
-				Type: "user",
-			},
-			{
-				Type: "document",
-				Relations: map[string]*openfgav1.Userset{
-					"viewer": typesystem.This(),
-				},
-				Metadata: &openfgav1.Metadata{
-					Relations: map[string]*openfgav1.RelationMetadata{
-						"viewer": {
-							DirectlyRelatedUserTypes: []*openfgav1.RelationReference{
-								typesystem.DirectRelationReference("user", ""),
-								typesystem.WildcardRelationReference("user"),
-							},
-						},
-					},
+		_, err = s.Write(ctx, &openfgav1.WriteRequest{
+			StoreId: store,
+			Writes: &openfgav1.TupleKeys{
+				TupleKeys: []*openfgav1.TupleKey{
+					tuple.NewTupleKey("document:1", "viewer", "group:1#member"),
+					tuple.NewTupleKey("group:1", "member", "group:2#member"),
+					tuple.NewTupleKey("group:2", "member", "group:3#member"),
+					tuple.NewTupleKey("group:3", "member", "user:jon"),
 				},
 			},
-		},
-	}, nil)
-	mockDatastore.EXPECT().ReadStartingWithUser(gomock.Any(), store, storage.ReadStartingWithUserFilter{
-		ObjectType: "document",
-		Relation:   "viewer",
-		UserFilter: []*openfgav1.ObjectRelation{
-			{Object: "user:*"},
-			{Object: "user:bob"},
-		}}).AnyTimes().Return(nil, serverErrors.AuthorizationModelResolutionTooComplex)
+		})
+		require.NoError(t, err)
 
-	s := MustNewServerWithOpts(
-		WithDatastore(mockDatastore),
-	)
+		t.Run("resolution_depth_exceeded_error_unary", func(t *testing.T) {
+			res, err := s.ListObjects(ctx, &openfgav1.ListObjectsRequest{
+				StoreId:              store,
+				AuthorizationModelId: writeModelResp.GetAuthorizationModelId(),
+				Type:                 "document",
+				Relation:             "viewer",
+				User:                 "user:jon",
+			})
 
-	t.Run("error_listing_objects_from_storage_in_non-streaming_version", func(t *testing.T) {
-		res, err := s.ListObjects(ctx, &openfgav1.ListObjectsRequest{
-			StoreId:              store,
-			AuthorizationModelId: modelID,
-			Type:                 "document",
-			Relation:             "viewer",
-			User:                 "user:bob",
+			require.Nil(t, res)
+			require.ErrorIs(t, err, serverErrors.AuthorizationModelResolutionTooComplex)
 		})
 
-		require.Nil(t, res)
-		require.ErrorIs(t, err, serverErrors.AuthorizationModelResolutionTooComplex)
-	})
+		t.Run("resolution_depth_exceeded_error_streaming", func(t *testing.T) {
+			err := s.StreamedListObjects(&openfgav1.StreamedListObjectsRequest{
+				StoreId:              store,
+				AuthorizationModelId: writeModelResp.GetAuthorizationModelId(),
+				Type:                 "document",
+				Relation:             "viewer",
+				User:                 "user:jon",
+			}, NewMockStreamServer())
 
-	t.Run("error_listing_objects_from_storage_in_streaming_version", func(t *testing.T) {
-		err := s.StreamedListObjects(&openfgav1.StreamedListObjectsRequest{
-			StoreId:              store,
-			AuthorizationModelId: modelID,
-			Type:                 "document",
-			Relation:             "viewer",
-			User:                 "user:bob",
-		}, NewMockStreamServer())
-
-		require.ErrorIs(t, err, serverErrors.AuthorizationModelResolutionTooComplex)
+			require.ErrorIs(t, err, serverErrors.AuthorizationModelResolutionTooComplex)
+		})
 	})
 }
 
 func TestAuthorizationModelInvalidSchemaVersion(t *testing.T) {
 	ctx := context.Background()
diff --git a/pkg/server/test/reverse_expand.go b/pkg/server/test/reverse_expand.go
index 675697e..bca5a18 100644
--- a/pkg/server/test/reverse_expand.go
+++ b/pkg/server/test/reverse_expand.go
@@ -6,12 +6,12 @@ import (
 	"time"
 
 	parser "github.com/craigpastro/openfga-dsl-parser/v2"
 	"github.com/oklog/ulid/v2"
 	openfgav1 "github.com/openfga/api/proto/openfga/v1"
+	"github.com/openfga/openfga/internal/graph"
 	"github.com/openfga/openfga/pkg/server/commands/reverseexpand"
-	serverErrors "github.com/openfga/openfga/pkg/server/errors"
 	"github.com/openfga/openfga/pkg/storage"
 	"github.com/openfga/openfga/pkg/tuple"
 	"github.com/openfga/openfga/pkg/typesystem"
 	"github.com/stretchr/testify/require"
 )
@@ -355,11 +355,11 @@ func TestReverseExpand(t *testing.T, ds storage.OpenFGADatastore) {
 			tuples: []*openfgav1.TupleKey{
 				tuple.NewTupleKey("folder:folder1", "viewer", "user:jon"),
 				tuple.NewTupleKey("folder:folder2", "parent", "folder:folder1"),
 				tuple.NewTupleKey("folder:folder3", "parent", "folder:folder2"),
 			},
-			expectedError:        serverErrors.AuthorizationModelResolutionTooComplex,
+			expectedError:        graph.ErrResolutionDepthExceeded,
 			expectedDSQueryCount: 0,
 		},
 		{
 			name: "objects_connected_to_a_userset",
 			request: &reverseexpand.ReverseExpandRequest{
diff --git a/pkg/server/test/write_authzmodel.go b/pkg/server/test/write_authzmodel.go
index 70dbe2d..98623b9 100644
--- a/pkg/server/test/write_authzmodel.go
+++ b/pkg/server/test/write_authzmodel.go
@@ -1,22 +1,22 @@
 package test
 
 import (
 	"context"
-	"errors"
 	"fmt"
 	"testing"
 
 	parser "github.com/craigpastro/openfga-dsl-parser/v2"
 	"github.com/oklog/ulid/v2"
 	openfgav1 "github.com/openfga/api/proto/openfga/v1"
 	"github.com/openfga/openfga/pkg/logger"
 	"github.com/openfga/openfga/pkg/server/commands"
-	serverErrors "github.com/openfga/openfga/pkg/server/errors"
 	"github.com/openfga/openfga/pkg/storage"
 	"github.com/openfga/openfga/pkg/typesystem"
 	"github.com/stretchr/testify/require"
+	"google.golang.org/grpc/codes"
+	"google.golang.org/grpc/status"
 )
 
 func WriteAuthorizationModelTest(t *testing.T, datastore storage.OpenFGADatastore) {
 	storeID := ulid.Make().String()
 
@@ -44,21 +44,21 @@ func WriteAuthorizationModelTest(t *testing.T, datastore storage.OpenFGADatastor
 
 	var tests = []struct {
 		name          string
 		request       *openfgav1.WriteAuthorizationModelRequest
 		allowSchema10 bool
-		err           error
+		errCode       codes.Code
 	}{
 		{
 			name: "fails_if_too_many_types",
 			request: &openfgav1.WriteAuthorizationModelRequest{
 				StoreId:         storeID,
 				TypeDefinitions: items,
 				SchemaVersion:   typesystem.SchemaVersion1_1,
 			},
 			allowSchema10: false,
-			err:           serverErrors.ExceededEntityLimit("type definitions in an authorization model", datastore.MaxTypesPerAuthorizationModel()),
+			errCode:       codes.Code(openfgav1.ErrorCode_exceeded_entity_limit),
 		},
 		{
 			name: "fails_if_a_relation_is_not_defined",
 			request: &openfgav1.WriteAuthorizationModelRequest{
 				StoreId: storeID,
@@ -71,11 +71,11 @@ func WriteAuthorizationModelTest(t *testing.T, datastore storage.OpenFGADatastor
 					},
 				},
 				SchemaVersion: typesystem.SchemaVersion1_1,
 			},
 			allowSchema10: false,
-			err:           serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{ObjectType: "repo", Relation: "owner", Cause: typesystem.ErrInvalidUsersetRewrite}),
+			errCode:       codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
 		},
 		{
 			name: "Fails_if_type_info_metadata_is_omitted_in_1.1_model",
 			request: &openfgav1.WriteAuthorizationModelRequest{
 				StoreId:       storeID,
@@ -88,13 +88,11 @@ func WriteAuthorizationModelTest(t *testing.T, datastore storage.OpenFGADatastor
 						},
 					},
 				},
 			},
 			allowSchema10: false,
-			err: serverErrors.InvalidAuthorizationModelInput(
-				errors.New("the assignable relation 'reader' in object type 'document' must contain at least one relation type"),
-			),
+			errCode:       codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
 		},
 		{
 			name: "Fails_if_writing_1_0_model_because_it_will_be_interpreted_as_1_1",
 			request: &openfgav1.WriteAuthorizationModelRequest{
 				StoreId: storeID,
@@ -106,11 +104,11 @@ func WriteAuthorizationModelTest(t *testing.T, datastore storage.OpenFGADatastor
 						},
 					},
 				},
 			},
 			allowSchema10: true,
-			err:           serverErrors.InvalidAuthorizationModelInput(typesystem.AssignableRelationError("document", "reader")),
+			errCode:       codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
 		},
 		{
 			name: "Works_if_no_schema_version",
 			request: &openfgav1.WriteAuthorizationModelRequest{
 				StoreId: storeID,
@@ -161,15 +159,11 @@ func WriteAuthorizationModelTest(t *testing.T, datastore storage.OpenFGADatastor
 				  relations
 				    define viewer: [document#viewer] as self
 				`),
 				SchemaVersion: typesystem.SchemaVersion1_1,
 			},
-			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
-				ObjectType: "document",
-				Relation:   "viewer",
-				Cause:      typesystem.ErrNoEntrypoints},
-			),
+			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
 		},
 		{
 			name: "self_referencing_type_restriction_without_entrypoint_2",
 			request: &openfgav1.WriteAuthorizationModelRequest{
 				StoreId: storeID,
@@ -180,15 +174,11 @@ func WriteAuthorizationModelTest(t *testing.T, datastore storage.OpenFGADatastor
 				    define editor: [user] as self
 				    define viewer: [document#viewer] as self and editor
 				`),
 				SchemaVersion: typesystem.SchemaVersion1_1,
 			},
-			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
-				ObjectType: "document",
-				Relation:   "viewer",
-				Cause:      typesystem.ErrNoEntrypoints,
-			}),
+			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
 		},
 		{
 			name: "self_referencing_type_restriction_without_entrypoint_3",
 			request: &openfgav1.WriteAuthorizationModelRequest{
 				StoreId: storeID,
@@ -199,15 +189,11 @@ func WriteAuthorizationModelTest(t *testing.T, datastore storage.OpenFGADatastor
 				    define restricted: [user] as self
 				    define viewer: [document#viewer] as self but not restricted
 				`),
 				SchemaVersion: typesystem.SchemaVersion1_1,
 			},
-			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
-				ObjectType: "document",
-				Relation:   "viewer",
-				Cause:      typesystem.ErrNoEntrypoints,
-			}),
+			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
 		},
 		{
 			name: "rewritten_relation_in_intersection_unresolvable",
 			request: &openfgav1.WriteAuthorizationModelRequest{
 				StoreId: storeID,
@@ -221,15 +207,11 @@ func WriteAuthorizationModelTest(t *testing.T, datastore storage.OpenFGADatastor
 				    define action2 as admin and action1 and action3
 				    define action3 as admin and action1 and action2
 				`),
 				SchemaVersion: typesystem.SchemaVersion1_1,
 			},
-			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
-				ObjectType: "document",
-				Relation:   "action1",
-				Cause:      typesystem.ErrNoEntryPointsLoop,
-			}),
+			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
 		},
 		{
 			name: "direct_relationship_with_entrypoint",
 			request: &openfgav1.WriteAuthorizationModelRequest{
 				StoreId: storeID,
@@ -254,11 +236,10 @@ func WriteAuthorizationModelTest(t *testing.T, datastore storage.OpenFGADatastor
 				    define editor: [user] as self
 				    define viewer as editor
 				`),
 			},
 		},
-
 		{
 			name: "rewritten_relation_in_exclusion_unresolvable",
 			request: &openfgav1.WriteAuthorizationModelRequest{
 				StoreId: storeID,
 				TypeDefinitions: parser.MustParse(`
@@ -270,15 +251,11 @@ func WriteAuthorizationModelTest(t *testing.T, datastore storage.OpenFGADatastor
 				    define action1 as admin but not action2
 				    define action2 as admin but not action3
 				    define action3 as admin but not action1
 				`),
 			},
-			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
-				ObjectType: "document",
-				Relation:   "action1",
-				Cause:      typesystem.ErrNoEntryPointsLoop,
-			}),
+			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
 		},
 		{
 			name: "no_entrypoint_3a",
 			request: &openfgav1.WriteAuthorizationModelRequest{
 				StoreId: storeID,
@@ -289,17 +266,12 @@ func WriteAuthorizationModelTest(t *testing.T, datastore storage.OpenFGADatastor
 				  relations
 				    define viewer: [document#viewer] as self and editor
 				    define editor: [user] as self
 				`),
 			},
-			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
-				ObjectType: "document",
-				Relation:   "viewer",
-				Cause:      typesystem.ErrNoEntrypoints,
-			}),
+			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
 		},
-
 		{
 			name: "no_entrypoint_3b",
 			request: &openfgav1.WriteAuthorizationModelRequest{
 				StoreId: storeID,
 				TypeDefinitions: parser.MustParse(`
@@ -309,15 +281,11 @@ func WriteAuthorizationModelTest(t *testing.T, datastore storage.OpenFGADatastor
 				  relations
 				    define viewer: [document#viewer] as self but not editor
 				    define editor: [user] as self
 				`),
 			},
-			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
-				ObjectType: "document",
-				Relation:   "viewer",
-				Cause:      typesystem.ErrNoEntrypoints,
-			}),
+			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
 		},
 		{
 			name: "no_entrypoint_4",
 			request: &openfgav1.WriteAuthorizationModelRequest{
 				StoreId: storeID,
@@ -334,15 +302,11 @@ func WriteAuthorizationModelTest(t *testing.T, datastore storage.OpenFGADatastor
 				    define parent: [folder] as self
 				    define editor as viewer
 				    define viewer as editor from parent
 				`),
 			},
-			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
-				ObjectType: "document",
-				Relation:   "editor",
-				Cause:      typesystem.ErrNoEntrypoints,
-			}),
+			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
 		},
 		{
 			name: "self_referencing_type_restriction_with_entrypoint_1",
 			request: &openfgav1.WriteAuthorizationModelRequest{
 				StoreId: storeID,
@@ -402,13 +366,11 @@ func WriteAuthorizationModelTest(t *testing.T, datastore storage.OpenFGADatastor
 					{
 						Type: "",
 					},
 				},
 			},
-			err: serverErrors.InvalidAuthorizationModelInput(
-				fmt.Errorf("the type name of a type definition cannot be an empty string"),
-			),
+			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
 		},
 		{
 			name: "relation_name_is_empty_string",
 			request: &openfgav1.WriteAuthorizationModelRequest{
 				StoreId: storeID,
@@ -422,24 +384,80 @@ func WriteAuthorizationModelTest(t *testing.T, datastore storage.OpenFGADatastor
 					{
 						Type: "other",
 					},
 				},
 			},
-			err: serverErrors.InvalidAuthorizationModelInput(
-				fmt.Errorf("type 'user' defines a relation with an empty string for a name"),
-			),
+			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
+		},
+		{
+			name: "many_circular_computed_relations",
+			request: &openfgav1.WriteAuthorizationModelRequest{
+				StoreId: storeID,
+				TypeDefinitions: parser.MustParse(`
+				type user
+
+				type canvas
+				  relations
+					define can_edit as editor or owner
+					define editor: [user, account#member] as self
+					define owner: [user] as self
+					define viewer: [user, account#member] as self
+	  
+				type account
+				  relations
+					define admin: [user] as self or member or super_admin or owner
+					define member: [user] as self or owner or admin or super_admin
+					define owner: [user] as self
+					define super_admin: [user] as self or admin or member
+				`),
+			},
+			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
+		},
+		{
+			name: "circular_relations_involving_intersection",
+			request: &openfgav1.WriteAuthorizationModelRequest{
+				StoreId: storeID,
+				TypeDefinitions: parser.MustParse(`
+				type user
+
+				type other
+				  relations
+					define x: [user] as self and y
+					define y: [user] as self and z
+					define z: [user] as self or x
+				`),
+			},
+			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
+		},
+		{
+			name: "circular_relations_involving_exclusion",
+			request: &openfgav1.WriteAuthorizationModelRequest{
+				StoreId: storeID,
+				TypeDefinitions: parser.MustParse(`
+				type user
+
+				type other
+				  relations
+					define x: [user] as self but not y
+					define y: [user] as self but not z
+					define z: [user] as self or x
+				`),
+			},
+			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
 		},
 	}
 
 	ctx := context.Background()
 	logger := logger.NewNoopLogger()
 
 	for _, test := range tests {
 		t.Run(test.name, func(t *testing.T) {
 			cmd := commands.NewWriteAuthorizationModelCommand(datastore, logger)
 			resp, err := cmd.Execute(ctx, test.request)
-			require.ErrorIs(t, err, test.err)
+			status, ok := status.FromError(err)
+			require.True(t, ok)
+			require.Equal(t, test.errCode, status.Code())
 
 			if err == nil {
 				_, err = ulid.Parse(resp.AuthorizationModelId)
 				require.NoError(t, err)
 			}
diff --git a/pkg/typesystem/typesystem.go b/pkg/typesystem/typesystem.go
index 59b8691..d7219df 100644
--- a/pkg/typesystem/typesystem.go
+++ b/pkg/typesystem/typesystem.go
@@ -891,10 +891,23 @@ func (t *TypeSystem) validateRelation(typeName, relationName string, relationMap
 			Relation:   relationName,
 			Cause:      cause,
 		}
 	}
 
+	hasCycle, err := t.HasCycle(typeName, relationName)
+	if err != nil {
+		return err
+	}
+
+	if hasCycle {
+		return &InvalidRelationError{
+			ObjectType: typeName,
+			Relation:   relationName,
+			Cause:      ErrCycle,
+		}
+	}
+
 	return nil
 }
 
 func containsDuplicateType(model *openfgav1.AuthorizationModel) bool {
 	seen := make(map[string]struct{}, len(model.GetTypeDefinitions()))
@@ -1195,10 +1208,74 @@ func InvalidRelationTypeError(objectType, relation, relatedObjectType, relatedRe
 	}
 
 	return fmt.Errorf("the relation type '%s' on '%s' in object type '%s' is not valid", relationType, relation, objectType)
 }
 
+func (t *TypeSystem) hasCycle(
+	objectType, relationName string,
+	rewrite *openfgav1.Userset,
+	visited map[string]struct{},
+) (bool, error) {
+
+	visited[fmt.Sprintf("%s#%s", objectType, relationName)] = struct{}{}
+
+	visitedCopy := maps.Clone(visited)
+
+	var children []*openfgav1.Userset
+
+	switch rw := rewrite.Userset.(type) {
+	case *openfgav1.Userset_This, *openfgav1.Userset_TupleToUserset:
+		return false, nil
+	case *openfgav1.Userset_ComputedUserset:
+		rewrittenRelation := rw.ComputedUserset.Relation
+
+		if _, ok := visited[fmt.Sprintf("%s#%s", objectType, rewrittenRelation)]; ok {
+			return true, nil
+		}
+
+		rewrittenRewrite, err := t.GetRelation(objectType, rewrittenRelation)
+		if err != nil {
+			return false, err
+		}
+
+		return t.hasCycle(objectType, rewrittenRelation, rewrittenRewrite.GetRewrite(), visitedCopy)
+	case *openfgav1.Userset_Union:
+		children = append(children, rw.Union.GetChild()...)
+	case *openfgav1.Userset_Intersection:
+		children = append(children, rw.Intersection.GetChild()...)
+	case *openfgav1.Userset_Difference:
+		children = append(children, rw.Difference.GetBase(), rw.Difference.GetSubtract())
+	}
+
+	for _, child := range children {
+
+		hasCycle, err := t.hasCycle(objectType, relationName, child, visitedCopy)
+		if err != nil {
+			return false, err
+		}
+
+		if hasCycle {
+			return true, nil
+		}
+	}
+
+	return false, nil
+}
+
+// HasCycle runs a cycle detection test on the provided `objectType#relation` to see if the relation
+// defines a rewrite rule that is self-referencing in any way (through computed relationships).
+func (t *TypeSystem) HasCycle(objectType, relationName string) (bool, error) {
+	visited := map[string]struct{}{}
+
+	relation, err := t.GetRelation(objectType, relationName)
+	if err != nil {
+		return false, err
+	}
+
+	return t.hasCycle(objectType, relationName, relation.GetRewrite(), visited)
+}
+
 // getAllTupleToUsersetsDefinitions returns a map where the key is the object type and the value
 // is another map where key=relationName, value=list of tuple to usersets declared in that relation
 func (t *TypeSystem) getAllTupleToUsersetsDefinitions() map[string]map[string][]*openfgav1.TupleToUserset {
 	response := make(map[string]map[string][]*openfgav1.TupleToUserset, 0)
 	for typeName, typeDef := range t.typeDefinitions {
diff --git a/pkg/typesystem/typesystem_test.go b/pkg/typesystem/typesystem_test.go
index a5f7717..37eabdf 100644
--- a/pkg/typesystem/typesystem_test.go
+++ b/pkg/typesystem/typesystem_test.go
@@ -7,10 +7,168 @@ import (
 	parser "github.com/craigpastro/openfga-dsl-parser/v2"
 	openfgav1 "github.com/openfga/api/proto/openfga/v1"
 	"github.com/stretchr/testify/require"
 )
 
+func TestHasCycle(t *testing.T) {
+
+	tests := []struct {
+		name       string
+		model      string
+		objectType string
+		relation   string
+		expected   bool
+	}{
+		{
+			name: "test_1",
+			model: `
+			type resource
+			  relations
+			    define x as y
+			    define y as x
+			`,
+			objectType: "resource",
+			relation:   "x",
+			expected:   true,
+		},
+		{
+			name: "test_2",
+			model: `
+			type resource
+			  relations
+			    define x as y
+			    define y as z
+				define z as x
+			`,
+			objectType: "resource",
+			relation:   "y",
+			expected:   true,
+		},
+		{
+			name: "test_3",
+			model: `
+			type user
+
+			type resource
+			  relations
+			    define x: [user] as self or y
+			    define y: [user] as self or z
+				define z: [user] as self or x
+			`,
+			objectType: "resource",
+			relation:   "z",
+			expected:   true,
+		},
+		{
+			name: "test_4",
+			model: `
+			type user
+
+			type resource
+			  relations
+			    define x: [user] as self or y
+			    define y: [user] as self or z
+				define z: [user] as self or x
+			`,
+			objectType: "resource",
+			relation:   "z",
+			expected:   true,
+		},
+		{
+			name: "test_5",
+			model: `
+			type user
+
+			type resource
+			  relations
+				define x: [user] as self but not y
+				define y: [user] as self but not z
+				define z: [user] as self or x
+			`,
+			objectType: "resource",
+			relation:   "x",
+			expected:   true,
+		},
+		{
+			name: "test_6",
+			model: `
+			type user
+
+			type group
+			  relations
+				define member: [user] as self or memberA or memberB or memberC
+				define memberA: [user] as self or member or memberB or memberC
+				define memberB: [user] as self or member or memberA or memberC
+				define memberC: [user] as self or member or memberA or memberB
+			`,
+			objectType: "group",
+			relation:   "member",
+			expected:   true,
+		},
+		{
+			name: "test_7",
+			model: `
+			type user
+
+			type account
+			relations
+				define admin: [user] as self or member or super_admin or owner
+				define member: [user] as self or owner or admin or super_admin
+				define super_admin: [user] as self or admin or member or owner
+				define owner: [user] as self
+			`,
+			objectType: "account",
+			relation:   "member",
+			expected:   true,
+		},
+		{
+			name: "test_8",
+			model: `
+			type user
+
+			type account
+			relations
+				define admin: [user] as self or member or super_admin or owner
+				define member: [user] as self or owner or admin or super_admin
+				define super_admin: [user] as self or admin or member or owner
+				define owner: [user] as self
+			`,
+			objectType: "account",
+			relation:   "owner",
+			expected:   false,
+		},
+		{
+			name: "test_9",
+			model: `
+			type user
+
+			type document
+			  relations
+				define editor: [user] as self
+				define viewer: [document#viewer] as self or editor
+			`,
+			objectType: "document",
+			relation:   "viewer",
+			expected:   false,
+		},
+	}
+
+	for _, test := range tests {
+		t.Run(test.name, func(t *testing.T) {
+
+			typesys := New(&openfgav1.AuthorizationModel{
+				SchemaVersion:   SchemaVersion1_1,
+				TypeDefinitions: parser.MustParse(test.model),
+			})
+
+			hasCycle, err := typesys.HasCycle(test.objectType, test.relation)
+			require.Equal(t, test.expected, hasCycle)
+			require.NoError(t, err)
+		})
+	}
+}
+
 func TestNewAndValidate(t *testing.T) {
 
 	tests := []struct {
 		name          string
 		model         string

Vulnerable code: [Unreleased]: https://github.com/openfga/openfga/compare/v1.3.1...HEAD
							TupleKey:             tuple.NewTupleKey(usersetObject, usersetRelation, tk.GetUser()),
				TupleKey: tuple.NewTupleKey(
					req.TupleKey.GetObject(),
					rewrite.ComputedUserset.GetRelation(),
					req.TupleKey.GetUser(),
				),
	serverErrors "github.com/openfga/openfga/pkg/server/errors"
			return serverErrors.AuthorizationModelResolutionTooComplex
		if errors.Is(err, graph.ErrResolutionDepthExceeded) {
// This test ensures that when the data storage fails, ListObjects v0 throws an error
func TestListObjects_Unoptimized_UnhappyPaths(t *testing.T) {
	modelID := ulid.Make().String()
	mockDatastore := mockstorage.NewMockOpenFGADatastore(mockController)

	mockDatastore.EXPECT().ReadAuthorizationModel(gomock.Any(), store, modelID).AnyTimes().Return(&openfgav1.AuthorizationModel{
		SchemaVersion: typesystem.SchemaVersion1_1,
		TypeDefinitions: parser.MustParse(`
		type user

		type repo
		  relations
		    define allowed: [user] as self
		    define viewer: [user] as self and allowed
		`),
	}, nil)
	mockDatastore.EXPECT().ReadStartingWithUser(gomock.Any(), store, gomock.Any()).AnyTimes().Return(nil, errors.New("error reading from storage"))

	s := MustNewServerWithOpts(
		WithDatastore(mockDatastore),
	)

	t.Run("error_listing_objects_from_storage_in_non-streaming_version", func(t *testing.T) {
		res, err := s.ListObjects(ctx, &openfgav1.ListObjectsRequest{
			StoreId:              store,
			AuthorizationModelId: modelID,
			Type:                 "repo",
			Relation:             "viewer",
			User:                 "user:bob",
		})

		require.Nil(t, res)
		require.ErrorIs(t, err, serverErrors.NewInternalError("", errors.New("error reading from storage")))
	})

	t.Run("error_listing_objects_from_storage_in_streaming_version", func(t *testing.T) {
		err := s.StreamedListObjects(&openfgav1.StreamedListObjectsRequest{
			StoreId:              store,
			AuthorizationModelId: modelID,
			Type:                 "repo",
			Relation:             "viewer",
			User:                 "user:bob",
		}, NewMockStreamServer())

		require.ErrorIs(t, err, serverErrors.NewInternalError("", errors.New("error reading from storage")))
	})
}

// This test ensures that when the data storage fails for known eror, ListObjects v0 throws the correct error
func TestListObjects_Unoptimized_UnhappyPaths_Known_Error(t *testing.T) {
	ctx := context.Background()
	store := ulid.Make().String()
	modelID := ulid.Make().String()
	mockController := gomock.NewController(t)
	defer mockController.Finish()
	mockDatastore := mockstorage.NewMockOpenFGADatastore(mockController)
	mockDatastore.EXPECT().ReadAuthorizationModel(gomock.Any(), store, modelID).AnyTimes().Return(&openfgav1.AuthorizationModel{
		SchemaVersion: typesystem.SchemaVersion1_1,
		TypeDefinitions: parser.MustParse(`
		type user

		type repo
		  relations
		    define allowed: [user] as self
		    define viewer: [user] as self and allowed
		`),
	}, nil)
	mockDatastore.EXPECT().ReadStartingWithUser(gomock.Any(), store, gomock.Any()).AnyTimes().Return(nil, serverErrors.AuthorizationModelResolutionTooComplex)
	s := MustNewServerWithOpts(
		WithDatastore(mockDatastore),
	)
	t.Run("error_listing_objects_from_storage_in_non-streaming_version", func(t *testing.T) {
		res, err := s.ListObjects(ctx, &openfgav1.ListObjectsRequest{
			StoreId:              store,
			AuthorizationModelId: modelID,
			Type:                 "repo",
			Relation:             "viewer",
			User:                 "user:bob",
		require.Nil(t, res)
		require.ErrorIs(t, err, serverErrors.AuthorizationModelResolutionTooComplex)
	})

	t.Run("error_listing_objects_from_storage_in_streaming_version", func(t *testing.T) {
		err := s.StreamedListObjects(&openfgav1.StreamedListObjectsRequest{
			StoreId:              store,
			AuthorizationModelId: modelID,
			Type:                 "repo",
			Relation:             "viewer",
			User:                 "user:bob",
		}, NewMockStreamServer())

		require.ErrorIs(t, err, serverErrors.AuthorizationModelResolutionTooComplex)
	})
}

// This test ensures that when the data storage fails, ListObjects v1 throws an error
func TestListObjects_UnhappyPaths(t *testing.T) {
	ctx := context.Background()
	store := ulid.Make().String()
	modelID := ulid.Make().String()

	mockController := gomock.NewController(t)
	defer mockController.Finish()

	mockDatastore := mockstorage.NewMockOpenFGADatastore(mockController)

	mockDatastore.EXPECT().ReadAuthorizationModel(gomock.Any(), store, modelID).AnyTimes().Return(&openfgav1.AuthorizationModel{
		SchemaVersion: typesystem.SchemaVersion1_1,
		TypeDefinitions: []*openfgav1.TypeDefinition{
			{
				Type: "user",
			},
			{
				Type: "document",
				Relations: map[string]*openfgav1.Userset{
					"viewer": typesystem.This(),
				},
				Metadata: &openfgav1.Metadata{
					Relations: map[string]*openfgav1.RelationMetadata{
						"viewer": {
							DirectlyRelatedUserTypes: []*openfgav1.RelationReference{
								typesystem.DirectRelationReference("user", ""),
								typesystem.WildcardRelationReference("user"),
							},
						},
					},
				},
			},
		},
	}, nil)
	mockDatastore.EXPECT().ReadStartingWithUser(gomock.Any(), store, storage.ReadStartingWithUserFilter{
		ObjectType: "document",
		Relation:   "viewer",
		UserFilter: []*openfgav1.ObjectRelation{
			{Object: "user:*"},
			{Object: "user:bob"},
		}}).AnyTimes().Return(nil, errors.New("error reading from storage"))

	s := MustNewServerWithOpts(
		WithDatastore(mockDatastore),
	)
	t.Run("error_listing_objects_from_storage_in_non-streaming_version", func(t *testing.T) {
		res, err := s.ListObjects(ctx, &openfgav1.ListObjectsRequest{
			StoreId:              store,
			AuthorizationModelId: modelID,
			Type:                 "document",
			Relation:             "viewer",
			User:                 "user:bob",

		require.Nil(t, res)
		require.ErrorIs(t, err, serverErrors.NewInternalError("", errors.New("error reading from storage")))
	t.Run("error_listing_objects_from_storage_in_streaming_version", func(t *testing.T) {
		err := s.StreamedListObjects(&openfgav1.StreamedListObjectsRequest{
			StoreId:              store,
			AuthorizationModelId: modelID,
			Type:                 "document",
			Relation:             "viewer",
			User:                 "user:bob",
		}, NewMockStreamServer())
		require.ErrorIs(t, err, serverErrors.NewInternalError("", errors.New("error reading from storage")))
	})
}
// This test ensures that when the data storage fails with known errors, ListObjects v1 throws an error
func TestListObjects_UnhappyPaths_Known_Error(t *testing.T) {
	ctx := context.Background()
	store := ulid.Make().String()
	modelID := ulid.Make().String()
	mockController := gomock.NewController(t)
	defer mockController.Finish()
	mockDatastore := mockstorage.NewMockOpenFGADatastore(mockController)
	mockDatastore.EXPECT().ReadAuthorizationModel(gomock.Any(), store, modelID).AnyTimes().Return(&openfgav1.AuthorizationModel{
		SchemaVersion: typesystem.SchemaVersion1_1,
		TypeDefinitions: []*openfgav1.TypeDefinition{
			{
				Type: "user",
			},
			{
				Type: "document",
				Relations: map[string]*openfgav1.Userset{
					"viewer": typesystem.This(),
				},
				Metadata: &openfgav1.Metadata{
					Relations: map[string]*openfgav1.RelationMetadata{
						"viewer": {
							DirectlyRelatedUserTypes: []*openfgav1.RelationReference{
								typesystem.DirectRelationReference("user", ""),
								typesystem.WildcardRelationReference("user"),
							},
						},
					},
		},
	}, nil)
	mockDatastore.EXPECT().ReadStartingWithUser(gomock.Any(), store, storage.ReadStartingWithUserFilter{
		ObjectType: "document",
		Relation:   "viewer",
		UserFilter: []*openfgav1.ObjectRelation{
			{Object: "user:*"},
			{Object: "user:bob"},
		}}).AnyTimes().Return(nil, serverErrors.AuthorizationModelResolutionTooComplex)
	s := MustNewServerWithOpts(
		WithDatastore(mockDatastore),
	)
	t.Run("error_listing_objects_from_storage_in_non-streaming_version", func(t *testing.T) {
		res, err := s.ListObjects(ctx, &openfgav1.ListObjectsRequest{
			StoreId:              store,
			AuthorizationModelId: modelID,
			Type:                 "document",
			Relation:             "viewer",
			User:                 "user:bob",
		require.Nil(t, res)
		require.ErrorIs(t, err, serverErrors.AuthorizationModelResolutionTooComplex)
	})
	t.Run("error_listing_objects_from_storage_in_streaming_version", func(t *testing.T) {
		err := s.StreamedListObjects(&openfgav1.StreamedListObjectsRequest{
			StoreId:              store,
			AuthorizationModelId: modelID,
			Type:                 "document",
			Relation:             "viewer",
			User:                 "user:bob",
		}, NewMockStreamServer())

		require.ErrorIs(t, err, serverErrors.AuthorizationModelResolutionTooComplex)
	serverErrors "github.com/openfga/openfga/pkg/server/errors"
			expectedError:        serverErrors.AuthorizationModelResolutionTooComplex,
	"errors"
	serverErrors "github.com/openfga/openfga/pkg/server/errors"
		err           error
			err:           serverErrors.ExceededEntityLimit("type definitions in an authorization model", datastore.MaxTypesPerAuthorizationModel()),
			err:           serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{ObjectType: "repo", Relation: "owner", Cause: typesystem.ErrInvalidUsersetRewrite}),
			err: serverErrors.InvalidAuthorizationModelInput(
				errors.New("the assignable relation 'reader' in object type 'document' must contain at least one relation type"),
			),
			err:           serverErrors.InvalidAuthorizationModelInput(typesystem.AssignableRelationError("document", "reader")),
			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
				ObjectType: "document",
				Relation:   "viewer",
				Cause:      typesystem.ErrNoEntrypoints},
			),
			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
				ObjectType: "document",
				Relation:   "viewer",
				Cause:      typesystem.ErrNoEntrypoints,
			}),
			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
				ObjectType: "document",
				Relation:   "viewer",
				Cause:      typesystem.ErrNoEntrypoints,
			}),
			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
				ObjectType: "document",
				Relation:   "action1",
				Cause:      typesystem.ErrNoEntryPointsLoop,
			}),

			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
				ObjectType: "document",
				Relation:   "action1",
				Cause:      typesystem.ErrNoEntryPointsLoop,
			}),
			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
				ObjectType: "document",
				Relation:   "viewer",
				Cause:      typesystem.ErrNoEntrypoints,
			}),

			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
				ObjectType: "document",
				Relation:   "viewer",
				Cause:      typesystem.ErrNoEntrypoints,
			}),
			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
				ObjectType: "document",
				Relation:   "editor",
				Cause:      typesystem.ErrNoEntrypoints,
			}),
			err: serverErrors.InvalidAuthorizationModelInput(
				fmt.Errorf("the type name of a type definition cannot be an empty string"),
			),
			err: serverErrors.InvalidAuthorizationModelInput(
				fmt.Errorf("type 'user' defines a relation with an empty string for a name"),
			),
			require.ErrorIs(t, err, test.err)
Fixed code: ## [1.3.2] - 2023-08-25
### Added
* Support TLS for OTLP trace endpoint ([#885](https://github.com/openfga/openfga/pull/885)) - thanks @matoous
* Configurable limits to database reads per ListObjects query ([#967](https://github.com/openfga/openfga/pull/967))
* Datastore query count labels to traces and query latency histogram in ListObjects ([#959](https://github.com/openfga/openfga/pull/959))
* Github workflow to check markdown links ([#1016](https://github.com/openfga/openfga/pull/1016)) - thanks @sanketrai1

### Fixed
* Change response code to internal error for concurrency conflicts ([#1011](https://github.com/openfga/openfga/pull/1011))

### Changed
* Use slices and maps packages from go1.21 ([#969](https://github.com/openfga/openfga/pull/969)) - thanks @tranngoclam
* Moved request validations to RPC handlers so library integrations benefit ([#975](https://github.com/openfga/openfga/pull/975), [#998](https://github.com/openfga/openfga/pull/998))
* Refactored internal usages of ConnectedObjects to ReverseExpand ([#968](https://github.com/openfga/openfga/pull/968))
* Expose validation middleware ([#1005](https://github.com/openfga/openfga/pull/1005))
* Upgrade grpc validator middleware to the latest v2 package ([#1019](https://github.com/openfga/openfga/pull/1019)) - thanks @tranngoclam

### Security
* Patches [CVE-2023-43645](https://github.com/openfga/openfga/security/advisories/GHSA-2hm9-h873-pgqh) - see the CVE for more details

  **[BREAKING]** If your model contained cycles or a relation definition that has the relation itself in its evaluation path, then Checks and queries that require evaluation will no longer be evaluated on v1.3.2+ and will return errors instead. You will need to update your models to remove the cycles.

[Unreleased]: https://github.com/openfga/openfga/compare/v1.3.2...HEAD
[1.3.2]: https://github.com/openfga/openfga/releases/tag/v1.3.2
	"golang.org/x/exp/maps"
var (
	ErrCycleDetected = errors.New("a cycle has been detected")
)

var cycleDetectedCheckHandler = func(ctx context.Context) (*ResolveCheckResponse, error) {
	return nil, ErrCycleDetected
}

	VisitedPaths         map[string]struct{}
	if req.VisitedPaths != nil {

		if _, visited := req.VisitedPaths[tuple.TupleKeyToString(req.GetTupleKey())]; visited {
			return nil, ErrCycleDetected
		}

		req.VisitedPaths[tuple.TupleKeyToString(req.GetTupleKey())] = struct{}{}
	} else {
		req.VisitedPaths = map[string]struct{}{
			tuple.TupleKeyToString(req.GetTupleKey()): {},
		}
	}

					tupleKey := tuple.NewTupleKey(usersetObject, usersetRelation, tk.GetUser())

					if _, visited := req.VisitedPaths[tuple.TupleKeyToString(tupleKey)]; visited {
						return nil, ErrCycleDetected
					}

							TupleKey:             tupleKey,
							VisitedPaths: maps.Clone(req.VisitedPaths),

		rewrittenTupleKey := tuple.NewTupleKey(
			req.TupleKey.GetObject(),
			rewrite.ComputedUserset.GetRelation(),
			req.TupleKey.GetUser(),
		)

		if _, visited := req.VisitedPaths[tuple.TupleKeyToString(rewrittenTupleKey)]; visited {
			return nil, ErrCycleDetected
		}

				TupleKey:             rewrittenTupleKey,
				VisitedPaths: maps.Clone(req.VisitedPaths),
			if _, visited := req.VisitedPaths[tuple.TupleKeyToString(tupleKey)]; visited {
				return nil, ErrCycleDetected
			}

					VisitedPaths: maps.Clone(req.VisitedPaths),

// TestCheckWithUnexpectedCycle tests the LocalChecker to make sure that if a model includes a cycle
// that should have otherwise been invalid according to the typesystem, then the check resolution will
// avoid the cycle and return an error indicating a cycle was detected.
func TestCheckWithUnexpectedCycle(t *testing.T) {
	ds := memory.New()
	defer ds.Close()

	storeID := ulid.Make().String()

	err := ds.Write(context.Background(), storeID, nil, []*openfgav1.TupleKey{
		tuple.NewTupleKey("resource:1", "parent", "resource:1"),
	})
	require.NoError(t, err)

	tests := []struct {
		name     string
		model    string
		tupleKey *openfgav1.TupleKey
	}{
		{
			name: "test_1",
			model: `
			type user

			type resource
			  relations
				define x: [user] as self but not y
				define y: [user] as self but not z
				define z: [user] as self or x
			`,
			tupleKey: tuple.NewTupleKey("resource:1", "x", "user:jon"),
		},
		{
			name: "test_2",
			model: `
			type user

			type resource
			  relations
				define x: [user] as self and y
				define y: [user] as self and z
				define z: [user] as self or x
			`,
			tupleKey: tuple.NewTupleKey("resource:1", "x", "user:jon"),
		},
		{
			name: "test_3",
			model: `
			type resource
			  relations
				define x as y
				define y as x
			`,
			tupleKey: tuple.NewTupleKey("resource:1", "x", "user:jon"),
		},
		{
			name: "test_4",
			model: `
			type resource
			  relations
			    define parent: [resource] as self
				define x: [user] as self or x from parent
			`,
			tupleKey: tuple.NewTupleKey("resource:1", "x", "user:jon"),
		},
	}

	checker := NewLocalChecker(ds)

	for _, test := range tests {
		typedefs := parser.MustParse(test.model)

		ctx := typesystem.ContextWithTypesystem(context.Background(), typesystem.New(
			&openfgav1.AuthorizationModel{
				Id:              ulid.Make().String(),
				TypeDefinitions: typedefs,
				SchemaVersion:   typesystem.SchemaVersion1_1,
			},
		))

		resp, err := checker.ResolveCheck(ctx, &ResolveCheckRequest{
			StoreID:            storeID,
			TupleKey:           test.tupleKey,
			ResolutionMetadata: &ResolutionMetadata{Depth: 25},
		})

		// if the branch producing the cycle is reached first, then an error is returned, otherwise
		// a result is returned if some other terminal path of evaluation was reached before the cycle
		if err != nil {
			require.ErrorIs(t, err, ErrCycleDetected)
		} else {
			require.False(t, resp.GetAllowed())
			require.GreaterOrEqual(t, resp.ResolutionMetadata.DatastoreQueryCount, uint32(1)) // min of 1 (x) if x isn't found and it returns quickly
			require.LessOrEqual(t, resp.ResolutionMetadata.DatastoreQueryCount, uint32(3))    // max of 3 (x, y, z) before the cycle
		}
	}
}
				if errors.Is(err, graph.ErrResolutionDepthExceeded) || errors.Is(err, graph.ErrCycleDetected) {
					resultsChan <- ListObjectsResult{Err: serverErrors.AuthorizationModelResolutionTooComplex}
					return
				}

					if errors.Is(err, graph.ErrResolutionDepthExceeded) || errors.Is(err, graph.ErrCycleDetected) {
						resultsChan <- ListObjectsResult{Err: serverErrors.AuthorizationModelResolutionTooComplex}
						return
					}


			return graph.ErrResolutionDepthExceeded
		if errors.Is(err, graph.ErrResolutionDepthExceeded) || errors.Is(err, graph.ErrCycleDetected) {
func TestListObjects_ErrorCases(t *testing.T) {
	t.Run("database_errors", func(t *testing.T) {
		mockDatastore := mockstorage.NewMockOpenFGADatastore(mockController)
		s := MustNewServerWithOpts(
			WithDatastore(mockDatastore),
		)
		modelID := ulid.Make().String()
		mockDatastore.EXPECT().ReadAuthorizationModel(gomock.Any(), store, modelID).AnyTimes().Return(&openfgav1.AuthorizationModel{
			SchemaVersion: typesystem.SchemaVersion1_1,
			TypeDefinitions: parser.MustParse(`
			type user
	
			type document
			  relations
				define viewer: [user, user:*] as self
			`),
		}, nil)
		mockDatastore.EXPECT().ReadStartingWithUser(gomock.Any(), store, storage.ReadStartingWithUserFilter{
			ObjectType: "document",
			Relation:   "viewer",
			UserFilter: []*openfgav1.ObjectRelation{
				{Object: "user:*"},
				{Object: "user:bob"},
			}}).AnyTimes().Return(nil, errors.New("error reading from storage"))

		t.Run("error_listing_objects_from_storage_in_non-streaming_version", func(t *testing.T) {
			res, err := s.ListObjects(ctx, &openfgav1.ListObjectsRequest{
				StoreId:              store,
				AuthorizationModelId: modelID,
				Type:                 "document",
				Relation:             "viewer",
				User:                 "user:bob",
			})
			require.Nil(t, res)
			require.ErrorIs(t, err, serverErrors.NewInternalError("", errors.New("error reading from storage")))
		t.Run("error_listing_objects_from_storage_in_streaming_version", func(t *testing.T) {
			err := s.StreamedListObjects(&openfgav1.StreamedListObjectsRequest{
				StoreId:              store,
				AuthorizationModelId: modelID,
				Type:                 "document",
				Relation:             "viewer",
				User:                 "user:bob",
			}, NewMockStreamServer())
			require.ErrorIs(t, err, serverErrors.NewInternalError("", errors.New("error reading from storage")))
	t.Run("graph_resolution_errors", func(t *testing.T) {
		s := MustNewServerWithOpts(
			WithDatastore(memory.New()),
			WithResolveNodeLimit(2),
		)
		writeModelResp, err := s.WriteAuthorizationModel(ctx, &openfgav1.WriteAuthorizationModelRequest{
			StoreId:       store,
			SchemaVersion: typesystem.SchemaVersion1_1,
			TypeDefinitions: parser.MustParse(`
			type user
			type group
			  relations
			    define member: [user, group#member] as self
			type document
			  relations
				define viewer: [group#member] as self
			`),
		})
		require.NoError(t, err)
		_, err = s.Write(ctx, &openfgav1.WriteRequest{
			StoreId: store,
			Writes: &openfgav1.TupleKeys{
				TupleKeys: []*openfgav1.TupleKey{
					tuple.NewTupleKey("document:1", "viewer", "group:1#member"),
					tuple.NewTupleKey("group:1", "member", "group:2#member"),
					tuple.NewTupleKey("group:2", "member", "group:3#member"),
					tuple.NewTupleKey("group:3", "member", "user:jon"),
		})
		require.NoError(t, err)
		t.Run("resolution_depth_exceeded_error_unary", func(t *testing.T) {
			res, err := s.ListObjects(ctx, &openfgav1.ListObjectsRequest{
				StoreId:              store,
				AuthorizationModelId: writeModelResp.GetAuthorizationModelId(),
				Type:                 "document",
				Relation:             "viewer",
				User:                 "user:jon",
			})
			require.Nil(t, res)
			require.ErrorIs(t, err, serverErrors.AuthorizationModelResolutionTooComplex)
		t.Run("resolution_depth_exceeded_error_streaming", func(t *testing.T) {
			err := s.StreamedListObjects(&openfgav1.StreamedListObjectsRequest{
				StoreId:              store,
				AuthorizationModelId: writeModelResp.GetAuthorizationModelId(),
				Type:                 "document",
				Relation:             "viewer",
				User:                 "user:jon",
			}, NewMockStreamServer())
			require.ErrorIs(t, err, serverErrors.AuthorizationModelResolutionTooComplex)
		})
	"github.com/openfga/openfga/internal/graph"
			expectedError:        graph.ErrResolutionDepthExceeded,
	"google.golang.org/grpc/codes"
	"google.golang.org/grpc/status"
		errCode       codes.Code
			errCode:       codes.Code(openfgav1.ErrorCode_exceeded_entity_limit),
			errCode:       codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
			errCode:       codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
			errCode:       codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
		},
		{
			name: "many_circular_computed_relations",
			request: &openfgav1.WriteAuthorizationModelRequest{
				StoreId: storeID,
				TypeDefinitions: parser.MustParse(`
				type user

				type canvas
				  relations
					define can_edit as editor or owner
					define editor: [user, account#member] as self
					define owner: [user] as self
					define viewer: [user, account#member] as self
	  
				type account
				  relations
					define admin: [user] as self or member or super_admin or owner
					define member: [user] as self or owner or admin or super_admin
					define owner: [user] as self
					define super_admin: [user] as self or admin or member
				`),
			},
			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
		},
		{
			name: "circular_relations_involving_intersection",
			request: &openfgav1.WriteAuthorizationModelRequest{
				StoreId: storeID,
				TypeDefinitions: parser.MustParse(`
				type user

				type other
				  relations
					define x: [user] as self and y
					define y: [user] as self and z
					define z: [user] as self or x
				`),
			},
			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
		},
		{
			name: "circular_relations_involving_exclusion",
			request: &openfgav1.WriteAuthorizationModelRequest{
				StoreId: storeID,
				TypeDefinitions: parser.MustParse(`
				type user

				type other
				  relations
					define x: [user] as self but not y
					define y: [user] as self but not z
					define z: [user] as self or x
				`),
			},
			errCode: codes.Code(openfgav1.ErrorCode_invalid_authorization_model),
			status, ok := status.FromError(err)
			require.True(t, ok)
			require.Equal(t, test.errCode, status.Code())
	hasCycle, err := t.HasCycle(typeName, relationName)
	if err != nil {
		return err
	}

	if hasCycle {
		return &InvalidRelationError{
			ObjectType: typeName,
			Relation:   relationName,
			Cause:      ErrCycle,
		}
	}

func (t *TypeSystem) hasCycle(
	objectType, relationName string,
	rewrite *openfgav1.Userset,
	visited map[string]struct{},
) (bool, error) {

	visited[fmt.Sprintf("%s#%s", objectType, relationName)] = struct{}{}

	visitedCopy := maps.Clone(visited)

	var children []*openfgav1.Userset

	switch rw := rewrite.Userset.(type) {
	case *openfgav1.Userset_This, *openfgav1.Userset_TupleToUserset:
		return false, nil
	case *openfgav1.Userset_ComputedUserset:
		rewrittenRelation := rw.ComputedUserset.Relation

		if _, ok := visited[fmt.Sprintf("%s#%s", objectType, rewrittenRelation)]; ok {
			return true, nil
		}

		rewrittenRewrite, err := t.GetRelation(objectType, rewrittenRelation)
		if err != nil {
			return false, err
		}

		return t.hasCycle(objectType, rewrittenRelation, rewrittenRewrite.GetRewrite(), visitedCopy)
	case *openfgav1.Userset_Union:
		children = append(children, rw.Union.GetChild()...)
	case *openfgav1.Userset_Intersection:
		children = append(children, rw.Intersection.GetChild()...)
	case *openfgav1.Userset_Difference:
		children = append(children, rw.Difference.GetBase(), rw.Difference.GetSubtract())
	}

	for _, child := range children {

		hasCycle, err := t.hasCycle(objectType, relationName, child, visitedCopy)
		if err != nil {
			return false, err
		}

		if hasCycle {
			return true, nil
		}
	}

	return false, nil
}

// HasCycle runs a cycle detection test on the provided `objectType#relation` to see if the relation
// defines a rewrite rule that is self-referencing in any way (through computed relationships).
func (t *TypeSystem) HasCycle(objectType, relationName string) (bool, error) {
	visited := map[string]struct{}{}

	relation, err := t.GetRelation(objectType, relationName)
	if err != nil {
		return false, err
	}

	return t.hasCycle(objectType, relationName, relation.GetRewrite(), visited)
}

func TestHasCycle(t *testing.T) {

	tests := []struct {
		name       string
		model      string
		objectType string
		relation   string
		expected   bool
	}{
		{
			name: "test_1",
			model: `
			type resource
			  relations
			    define x as y
			    define y as x
			`,
			objectType: "resource",
			relation:   "x",
			expected:   true,
		},
		{
			name: "test_2",
			model: `
			type resource
			  relations
			    define x as y
			    define y as z
				define z as x
			`,
			objectType: "resource",
			relation:   "y",
			expected:   true,
		},
		{
			name: "test_3",
			model: `
			type user

			type resource
			  relations
			    define x: [user] as self or y
			    define y: [user] as self or z
				define z: [user] as self or x
			`,
			objectType: "resource",
			relation:   "z",
			expected:   true,
		},
		{
			name: "test_4",
			model: `
			type user

			type resource
			  relations
			    define x: [user] as self or y
			    define y: [user] as self or z
				define z: [user] as self or x
			`,
			objectType: "resource",
			relation:   "z",
			expected:   true,
		},
		{
			name: "test_5",
			model: `
			type user

			type resource
			  relations
				define x: [user] as self but not y
				define y: [user] as self but not z
				define z: [user] as self or x
			`,
			objectType: "resource",
			relation:   "x",
			expected:   true,
		},
		{
			name: "test_6",
			model: `
			type user

			type group
			  relations
				define member: [user] as self or memberA or memberB or memberC
				define memberA: [user] as self or member or memberB or memberC
				define memberB: [user] as self or member or memberA or memberC
				define memberC: [user] as self or member or memberA or memberB
			`,
			objectType: "group",
			relation:   "member",
			expected:   true,
		},
		{
			name: "test_7",
			model: `
			type user

			type account
			relations
				define admin: [user] as self or member or super_admin or owner
				define member: [user] as self or owner or admin or super_admin
				define super_admin: [user] as self or admin or member or owner
				define owner: [user] as self
			`,
			objectType: "account",
			relation:   "member",
			expected:   true,
		},
		{
			name: "test_8",
			model: `
			type user

			type account
			relations
				define admin: [user] as self or member or super_admin or owner
				define member: [user] as self or owner or admin or super_admin
				define super_admin: [user] as self or admin or member or owner
				define owner: [user] as self
			`,
			objectType: "account",
			relation:   "owner",
			expected:   false,
		},
		{
			name: "test_9",
			model: `
			type user

			type document
			  relations
				define editor: [user] as self
				define viewer: [document#viewer] as self or editor
			`,
			objectType: "document",
			relation:   "viewer",
			expected:   false,
		},
	}

	for _, test := range tests {
		t.Run(test.name, func(t *testing.T) {

			typesys := New(&openfgav1.AuthorizationModel{
				SchemaVersion:   SchemaVersion1_1,
				TypeDefinitions: parser.MustParse(test.model),
			})

			hasCycle, err := typesys.HasCycle(test.objectType, test.relation)
			require.Equal(t, test.expected, hasCycle)
			require.NoError(t, err)
		})
	}
}