CVE-2023-43645 (Go, published 2023-09-27T15:19Z)
Description: 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.
Severity: nan (CVSS v3 base score: 5.9)
Weakness: CWE-835 \u2014 Loop with Unreachable Exit Condition ('Infinite Loop')
The product contains an iteration or loop with an exit condition that cannot be reached, i.e., an infinite loop.
Repository: https://github.com/openfga/openfga
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 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>

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)
		})
	}
}