CVE-2022-21708: Uncontrolled Recursion (CWE-674)
value: graphql-go is a GraphQL server with a focus on ease of use. In versions prior to 1.3.0 there exists a DoS vulnerability that is possible due to a bug in the library that would allow an attacker with specifically designed queries to cause stack overflow panics. Any user with access to the GraphQL handler can send these queries and cause stack overflows. This in turn could potentially compromise the ability of the server to serve data to its users. The issue has been patched in version `v1.3.0`. The only known workaround for this issue is to disable the `graphql.MaxDepth` option from your schema which is not recommended.
CWE description: The product does not properly control the amount of recursion that takes place,  consuming excessive resources, such as allocated memory or the program stack.
CVSS v3 base score: 6.5
Published: 2022-01-21T23:15Z
Repository: https://github.com/graph-gophers/graphql-go
Language: Go
Files changed: graphql_test.go, internal/validation/validate_max_depth_test.go, internal/validation/validation.go
Commit date: 2022-01-18 23:14:45 +0200
Commit message: validation: fix bug in maxDepth fragment spread logic (#492)


Diff: diff --git a/graphql_test.go b/graphql_test.go
index 497a74f..c8d9593 100644
--- a/graphql_test.go
+++ b/graphql_test.go
@@ -4295,5 +4295,34 @@ func TestInterfaceImplementingInterface(t *testing.T) {
 					}
 				}
 			`,
 	}})
 }
+
+func TestCircularFragmentMaxDepth(t *testing.T) {
+	withMaxDepth := graphql.MustParseSchema(starwars.Schema, &starwars.Resolver{}, graphql.MaxDepth(2))
+	gqltesting.RunTests(t, []*gqltesting.Test{
+		{
+			Schema: withMaxDepth,
+			Query: `
+	              query {
+	                  ...X
+	              }
+
+	              fragment X on Query {
+	                  ...Y
+	              }
+	              fragment Y on Query {
+	                  ...X
+	              }
+	          `,
+			ExpectedErrors: []*gqlerrors.QueryError{{
+				Message: `Cannot spread fragment "X" within itself via Y.`,
+				Rule:    "NoFragmentCycles",
+				Locations: []gqlerrors.Location{
+					{Line: 7, Column: 20},
+					{Line: 10, Column: 20},
+				},
+			}},
+		},
+	})
+}
diff --git a/internal/validation/validate_max_depth_test.go b/internal/validation/validate_max_depth_test.go
index f8bfd9a..613b22a 100644
--- a/internal/validation/validate_max_depth_test.go
+++ b/internal/validation/validate_max_depth_test.go
@@ -32,34 +32,39 @@ const (
 
 	interface Character {
 		id: ID!
 		name: String!
 		friends: [Character]
+		enemies: [Character]
 		appearsIn: [Episode]!
 	}
 
 	enum Episode {
 		NEWHOPE
 		EMPIRE
 		JEDI
 	}
 
-	type Starship {}
+	type Starship {
+		id: ID!
+	}
 
 	type Human implements Character {
 		id: ID!
 		name: String!
 		friends: [Character]
+		enemies: [Character]
 		appearsIn: [Episode]!
 		starships: [Starship]
 		totalCredits: Int
 	}
 
 	type Droid implements Character {
 		id: ID!
 		name: String!
 		friends: [Character]
+		enemies: [Character]
 		appearsIn: [Episode]!
 		primaryFunction: String
 	}`
 )
 
@@ -302,10 +307,68 @@ func TestMaxDepthFragmentSpreads(t *testing.T) {
 				}
 			}`,
 			depth:   6,
 			failure: true,
 		},
+		{
+			name: "spreadAtDifferentDepths",
+			query: `
+			fragment character on Character {
+				name # depth + 0
+				friends { # depth + 0
+					name # depth + 1
+				}
+			}
+
+			query laterDepthValidated {
+				...character # depth 1 (+1)
+				enemies { # depth 1
+					friends { # depth 2
+						...character # depth 2 (+1), should error!
+					}
+				}
+			}
+			`,
+			depth:   2,
+			failure: true,
+		},
+		{
+			name: "spreadAtSameDepth",
+			query: `
+			fragment character on Character {
+				name # depth + 0
+				friends { # depth + 0
+					name # depth + 1
+				}
+			}
+			query {
+				characters { # depth 1
+					friends { # depth 2
+						...character # depth 3 (+1)
+					}
+					enemies { # depth 2
+						...character # depth 3 (+1)
+					}
+				}
+			}
+			`,
+			depth: 4,
+		},
+		{
+			name: "fragmentCycle",
+			query: `
+			fragment X on Query { ...Y }
+			fragment Y on Query { ...Z }
+			fragment Z on Query { ...X }
+
+			query {
+				...X
+			}
+			`,
+			depth:   10,
+			failure: true,
+		},
 	} {
 		tc.Run(t, s)
 	}
 }
 
@@ -429,11 +492,11 @@ func TestMaxDepthValidation(t *testing.T) {
 			context := newContext(s, doc, tc.maxDepth)
 			op := doc.Operations[0]
 
 			opc := &opContext{context: context, ops: doc.Operations}
 
-			actual := validateMaxDepth(opc, op.Selections, 1)
+			actual := validateMaxDepth(opc, op.Selections, nil, 1)
 			if actual != tc.expected {
 				t.Errorf("expected %t, actual %t", tc.expected, actual)
 			}
 		})
 	}
diff --git a/internal/validation/validation.go b/internal/validation/validation.go
index d456dbe..e367263 100644
--- a/internal/validation/validation.go
+++ b/internal/validation/validation.go
@@ -74,11 +74,11 @@ func Validate(s *types.Schema, doc *types.ExecutableDefinition, variables map[st
 		c.usedVars[op] = make(varSet)
 		opc := &opContext{c, []*types.OperationDefinition{op}}
 
 		// Check if max depth is exceeded, if it's set. If max depth is exceeded,
 		// don't continue to validate the document and exit early.
-		if validateMaxDepth(opc, op.Selections, 1) {
+		if validateMaxDepth(opc, op.Selections, nil, 1) {
 			return c.errs
 		}
 
 		if op.Name.Name == "" && len(doc.Operations) != 1 {
 			c.addErr(op.Loc, "LoneAnonymousOperation", "This anonymous operation must be the only defined operation.")
@@ -233,41 +233,55 @@ func validateValue(c *opContext, v *types.InputValueDefinition, val interface{},
 	}
 }
 
 // validates the query doesn't go deeper than maxDepth (if set). Returns whether
 // or not query validated max depth to avoid excessive recursion.
-func validateMaxDepth(c *opContext, sels []types.Selection, depth int) bool {
+//
+// The visited map is necessary to ensure that max depth validation does not get stuck in cyclical
+// fragment spreads.
+func validateMaxDepth(c *opContext, sels []types.Selection, visited map[*types.FragmentDefinition]struct{}, depth int) bool {
 	// maxDepth checking is turned off when maxDepth is 0
 	if c.maxDepth == 0 {
 		return false
 	}
 
 	exceededMaxDepth := false
+	if visited == nil {
+		visited = map[*types.FragmentDefinition]struct{}{}
+	}
 
 	for _, sel := range sels {
 		switch sel := sel.(type) {
 		case *types.Field:
 			if depth > c.maxDepth {
 				exceededMaxDepth = true
 				c.addErr(sel.Alias.Loc, "MaxDepthExceeded", "Field %q has depth %d that exceeds max depth %d", sel.Name.Name, depth, c.maxDepth)
 				continue
 			}
-			exceededMaxDepth = exceededMaxDepth || validateMaxDepth(c, sel.SelectionSet, depth+1)
+			exceededMaxDepth = exceededMaxDepth || validateMaxDepth(c, sel.SelectionSet, visited, depth+1)
+
 		case *types.InlineFragment:
 			// Depth is not checked because inline fragments resolve to other fields which are checked.
 			// Depth is not incremented because inline fragments have the same depth as neighboring fields
-			exceededMaxDepth = exceededMaxDepth || validateMaxDepth(c, sel.Selections, depth)
+			exceededMaxDepth = exceededMaxDepth || validateMaxDepth(c, sel.Selections, visited, depth)
 		case *types.FragmentSpread:
 			// Depth is not checked because fragments resolve to other fields which are checked.
 			frag := c.doc.Fragments.Get(sel.Name.Name)
 			if frag == nil {
 				// In case of unknown fragment (invalid request), ignore max depth evaluation
 				c.addErr(sel.Loc, "MaxDepthEvaluationError", "Unknown fragment %q. Unable to evaluate depth.", sel.Name.Name)
 				continue
 			}
+
+			if _, ok := visited[frag]; ok {
+				// we've already seen this fragment, don't check depth again.
+				continue
+			}
+			visited[frag] = struct{}{}
+
 			// Depth is not incremented because fragments have the same depth as surrounding fields
-			exceededMaxDepth = exceededMaxDepth || validateMaxDepth(c, frag.Selections, depth)
+			exceededMaxDepth = exceededMaxDepth || validateMaxDepth(c, frag.Selections, visited, depth)
 		}
 	}
 
 	return exceededMaxDepth
 }

Vulnerable code: 	type Starship {}
			actual := validateMaxDepth(opc, op.Selections, 1)
		if validateMaxDepth(opc, op.Selections, 1) {
func validateMaxDepth(c *opContext, sels []types.Selection, depth int) bool {
			exceededMaxDepth = exceededMaxDepth || validateMaxDepth(c, sel.SelectionSet, depth+1)
			exceededMaxDepth = exceededMaxDepth || validateMaxDepth(c, sel.Selections, depth)
			exceededMaxDepth = exceededMaxDepth || validateMaxDepth(c, frag.Selections, depth)
Fixed code: 
func TestCircularFragmentMaxDepth(t *testing.T) {
	withMaxDepth := graphql.MustParseSchema(starwars.Schema, &starwars.Resolver{}, graphql.MaxDepth(2))
	gqltesting.RunTests(t, []*gqltesting.Test{
		{
			Schema: withMaxDepth,
			Query: `
	              query {
	                  ...X
	              }

	              fragment X on Query {
	                  ...Y
	              }
	              fragment Y on Query {
	                  ...X
	              }
	          `,
			ExpectedErrors: []*gqlerrors.QueryError{{
				Message: `Cannot spread fragment "X" within itself via Y.`,
				Rule:    "NoFragmentCycles",
				Locations: []gqlerrors.Location{
					{Line: 7, Column: 20},
					{Line: 10, Column: 20},
				},
			}},
		},
	})
}
		enemies: [Character]
	type Starship {
		id: ID!
	}
		enemies: [Character]
		enemies: [Character]
		{
			name: "spreadAtDifferentDepths",
			query: `
			fragment character on Character {
				name # depth + 0
				friends { # depth + 0
					name # depth + 1
				}
			}

			query laterDepthValidated {
				...character # depth 1 (+1)
				enemies { # depth 1
					friends { # depth 2
						...character # depth 2 (+1), should error!
					}
				}
			}
			`,
			depth:   2,
			failure: true,
		},
		{
			name: "spreadAtSameDepth",
			query: `
			fragment character on Character {
				name # depth + 0
				friends { # depth + 0
					name # depth + 1
				}
			}
			query {
				characters { # depth 1
					friends { # depth 2
						...character # depth 3 (+1)
					}
					enemies { # depth 2
						...character # depth 3 (+1)
					}
				}
			}
			`,
			depth: 4,
		},
		{
			name: "fragmentCycle",
			query: `
			fragment X on Query { ...Y }
			fragment Y on Query { ...Z }
			fragment Z on Query { ...X }

			query {
				...X
			}
			`,
			depth:   10,
			failure: true,
		},
			actual := validateMaxDepth(opc, op.Selections, nil, 1)
		if validateMaxDepth(opc, op.Selections, nil, 1) {
//
// The visited map is necessary to ensure that max depth validation does not get stuck in cyclical
// fragment spreads.
func validateMaxDepth(c *opContext, sels []types.Selection, visited map[*types.FragmentDefinition]struct{}, depth int) bool {
	if visited == nil {
		visited = map[*types.FragmentDefinition]struct{}{}
	}
			exceededMaxDepth = exceededMaxDepth || validateMaxDepth(c, sel.SelectionSet, visited, depth+1)

			exceededMaxDepth = exceededMaxDepth || validateMaxDepth(c, sel.Selections, visited, depth)

			if _, ok := visited[frag]; ok {
				// we've already seen this fragment, don't check depth again.
				continue
			}
			visited[frag] = struct{}{}

			exceededMaxDepth = exceededMaxDepth || validateMaxDepth(c, frag.Selections, visited, depth)