What is a good approach for detecting/prevent/limited cyclic query types

[mfn]

Hi,

What are recommended practices if you have type tree which eventually can reference each other?

Assumme I've an Article and a Comment and I have queries like articlesList and commentsList and Article has comments but a Comment can also reference it's article.

Intended use cases:

query articlesList {
  title # of Article
  comments {
    message
  }

or

query commentsList {
  message # of Comment
  article {
    title
  }

It's now possible to also do this:

query articlesList {
  title # of Article

  comments {
    article {
      comments {
        article {
          title
        }
      }
    }
  }

I'm aware of:

• \GraphQL\Validator\Rules\QueryComplexity and setMaxQueryComplexity
• \GraphQL\Validator\Rules\QueryDepth and setMaxQueryDepth

But they need to be adjusted to their maxima I need for legitimate queries, of which I also have some, which needs higher values then for the example I gave.

I'm also aware with a proper data loader in place this shouldn't be a problem (n+1 problem), but I am looking at a different kind of protection.

Something which is looking at the types and is configurable to detect if e.g. article is already accessed in different levels in the tree and then thrown an error.

A recommendations to have something similar to QueryComplexity and QueryDepth but more targeted?

thanks!

[spawnia]

This could be done through a custom validation rule.

It probably needs to be configured with pairs of fields that are the inverse of each other, since that does not necessarily follow from the schema definition. Consider the following example:

"Represents a node in a tree, see https://en.wikipedia.org/wiki/Tree_(abstract_data_type)."
type TreeNode {
  parent: TreeNode
  children: [TreeNode!]!
  siblings: [TreeNode!]!
}

Considering the shape of a tree, parent/children are inverse, parent/siblings and children/siblings are not.

[mfn]

I don't fully understand the "pairs of fields / inverse each other".

In the meantime I came up with this:

<?php declare(strict_types = 1);

use GraphQL\Error\Error;
use GraphQL\Language\AST\FieldNode;
use GraphQL\Language\AST\FragmentDefinitionNode;
use GraphQL\Language\AST\FragmentSpreadNode;
use GraphQL\Language\AST\InlineFragmentNode;
use GraphQL\Language\AST\Node;
use GraphQL\Language\AST\NodeKind;
use GraphQL\Language\AST\OperationDefinitionNode;
use GraphQL\Language\AST\SelectionSetNode;
use GraphQL\Type\Definition\Type;
use GraphQL\Validator\QueryValidationContext;
use GraphQL\Validator\Rules\QuerySecurityRule;
use RuntimeException;

class DetectCyclicTypeAccess extends QuerySecurityRule
{
    /** @var int Maximum amount of depth uses of a single type in a query. */
    private int $maxTypeCyclicDepth;

    /** @var array<string, array<positive-int, true>> Mapping of object types and their visited field depths. */
    private array $visitedTypes = [];

    /** @var array<string, bool> Fragment names which are already calculated in recursion */
    private array $calculatedFragments = [];

    public function __construct(int $maxTypeCyclicDepth)
    {
        $this->setEnabled($maxTypeCyclicDepth);
    }

    public function setEnabled(int $maxTypeCyclicDepth): void
    {
        $this->maxTypeCyclicDepth = $maxTypeCyclicDepth;
    }

    public function getVisitor(QueryValidationContext $context): array
    {
        return $this->invokeIfNeeded(
            $context,
            [
                // Here we gather all object nodes and their field depths
                NodeKind::FIELD => [
                    'enter' => function (FieldNode $node) use ($context): void {
                        $type = $context->getType();

                        if (Type::isLeafType($type)) {
                            return;
                        }
                        $depth = $this->fieldDepth($node);

                        // Zero depth means it has no further selection and we can ignore it
                        if (0 === $depth) {
                            return;
                        }

                        $typeName = Type::getNamedType($type)->name;

                        if (!isset($this->visitedTypes[$typeName])) {
                            $this->visitedTypes[$typeName] = [];
                        }

                        $this->visitedTypes[$typeName][$depth] = true;
                    },
                ],
                // This is only called once and after all fields above have been
                // processed, which means we can do the validation now here.
                NodeKind::OPERATION_DEFINITION => [
                    'leave' => function (OperationDefinitionNode $node) use ($context): void {
                        // Report all types exceeding the maximum depth
                        foreach ($this->visitedTypes as $typeName => $depths) {
                            if (\count($depths) > $this->maxTypeCyclicDepth) {
                                $context->reportError(
                                    new Error(
                                        "Type `$typeName` has cyclic access exceeding the maximum depth of $this->maxTypeCyclicDepth.",
                                        [$node]
                                    ),
                                );
                            }
                        }
                    },
                ],
            ],
        );
    }

    /**
     * This is a copy of `\GraphQL\Validator\Rules\QueryDepth::fieldDepth`
     *
     * No changes where made.
     *
     * @param OperationDefinitionNode|FieldNode|InlineFragmentNode|FragmentDefinitionNode $node
     * @see \GraphQL\Validator\Rules\QueryDepth::fieldDepth
     */
    protected function fieldDepth(Node $node, int $depth = 0, int $maxDepth = 0): int
    {
        if ($node->selectionSet instanceof SelectionSetNode) {
            foreach ($node->selectionSet->selections as $childNode) {
                $maxDepth = $this->nodeDepth($childNode, $depth, $maxDepth);
            }
        }

        return $maxDepth;
    }

    /**
     * This is a copy of `\GraphQL\Validator\Rules\QueryDepth::nodeDepth`
     *
     * Changes made:
     * - Throw exception when a cycle fragment is detected
     *
     * @see \GraphQL\Validator\Rules\QueryDepth::nodeDepth
     */
    private function nodeDepth(Node $node, int $depth = 0, int $maxDepth = 0): int
    {
        switch (true) {
            case $node instanceof FieldNode:
                // node has children?
                if (null !== $node->selectionSet) {
                    // update maxDepth if needed
                    if ($depth > $maxDepth) {
                        $maxDepth = $depth;
                    }

                    $maxDepth = $this->fieldDepth($node, $depth + 1, $maxDepth);
                }

                break;

            case $node instanceof InlineFragmentNode:
                $maxDepth = $this->fieldDepth($node, $depth, $maxDepth);

                break;

            case $node instanceof FragmentSpreadNode:
                $fragment = $this->getFragment($node);

                if (null !== $fragment) {
                    $name = $fragment->name->value;

                    if (isset($this->calculatedFragments[$name])) {
                        // Modified part BEGIN
                        throw new RuntimeException("Cyclic GraphQL fragment detected: $name");
                        // Modified part END
                    }

                    $this->calculatedFragments[$name] = true;
                    $maxDepth = $this->fieldDepth($fragment, $depth, $maxDepth);
                    unset($this->calculatedFragments[$name]);
                }

                break;
        }

        return $maxDepth;
    }

    protected function isEnabled(): bool
    {
        return 0 !== $this->maxTypeCyclicDepth;
    }
}

I've never used the Visitor before, or, any of the AST code, so it's 95% me not knowing what I do.

The meat is in the NodeKind::FIELD visitor:

• for every non-leaf node it calculates the remaining depth of the tree (this is code directly taken from QueryDepth)
• for each type, it stores that (unique) level of remaining depth

That $visitedTypes property looks like this in practice:

<?php
[
    'Post' => [
        12 => true,
        8 => true,
        4 => true,
    ],
    'Comment' => [
        11 => true,
        7 => true,
        3 => true,
        1 => true,
    ],

This would say that the Comment that was referenced on three distinct levels (from the bottom of the tree), which means something like this:

query {
  posts {
    comments {
      posts {
        comments {
          posts {
…
                   comment {
                     id
                   }
…

As in: 11 levels from the bottom of the query, a type of Comment was referenced. Same 7 levels from the bottom, etc. That's why the last one hast 1, it's one level away from the end of the tree, that's because it has a selection.

The actual depths don't matter that much and therefore I figured, whether I "count" that depth from the bottom or the top isn't relevant. In fact, I could not figure out a way calculate the depth of a node because I couldn't figure out a way to traverse the tree up (QueryDepth only operates on "operation" nodes), so I simply used that.

Now, seeing we've found this type referenced on 4 different levels, we could configure it and say: if a(ny) type is used on more than 3 different levels, we throw an error.
Assuming that this is what we want to protect us from.

It's different form what QueryDepth does, because it could be legitimate to go n levels deep with completely distinct types, e.g.

query {
  data {
    a {
      b {
       c {
         d {
… # etc

and DetectCyclicTypeAccess would be different from that.

---

Still not sure if this all makes sense, but it's the first thing I came up with and when I tested it against the queries I use and want to prevent, so far they looked fine 🤞🏼

[spawnia]

I don't fully understand the "pairs of fields / inverse each other".

Alright, I will try to explain it more clearly. Let me define some terms first:

• By pairs of fields, I mean a set of exactly 2 fields. TreeNode.children/TreeNode.parent is one example of a pair of fields.
• I am talking about inverse in the mathematical sense, see https://en.wikipedia.org/wiki/Inverse_function.

To understand the example visually, consider the following image.

Suppose you have a query that allows you to query the tree, starting at any node of your choice. The following query would be an example of something your rule should prevent:

{
  treeNode(id: "D") {
    id # D
    children {
      id # H, I
      parent { # This is where delivering more results becomes nonsensical and the data repeats itself
        id # D again
        children {
          id # H, I again
        }
      }
    }
  }
}

In contrast to this, traversing the tree by looking at siblings and parent repeatedly (or siblings and children) might make sense to an arbitrary depth. At some point, the maximum query depth might be hit or the data might run out, but we are getting new information on each level.

{
  treeNode(id: "H") {
    id # H
    parent {
      id # D
      siblings {
        id # E
        parent {
          id # B
          siblings {
            id # C
            parent {
              id # A
              siblings { # empty list
                id
              }
           }
        }
      }
    }
  }
}

Thus, only the pair of fields parent/children would be cyclic in the sense that it makes no sense to query it.

[matasarei]

Following up on @spawnia's suggestion, here's a working custom validation rule. It limits how many times a given Type.field may appear on a single path of the query, and it follows named and inline fragments. I tested it on graphql-php v15 (PHP 8.3).

<?php declare(strict_types=1);

use GraphQL\Error\Error;
use GraphQL\Language\AST\FieldNode;
use GraphQL\Language\AST\FragmentSpreadNode;
use GraphQL\Language\AST\InlineFragmentNode;
use GraphQL\Language\AST\NodeKind;
use GraphQL\Language\AST\OperationDefinitionNode;
use GraphQL\Language\AST\SelectionSetNode;
use GraphQL\Type\Definition\HasFieldsType;
use GraphQL\Type\Definition\Type;
use GraphQL\Validator\QueryValidationContext;
use GraphQL\Validator\Rules\QuerySecurityRule;

final class FieldRepetitionLimit extends QuerySecurityRule
{
    /** @param array<string, int> $limits "Type.field" => max occurrences on one path */
    public function __construct(private array $limits) {}

    public function getVisitor(QueryValidationContext $context): array
    {
        return $this->invokeIfNeeded($context, [
            NodeKind::OPERATION_DEFINITION => function (OperationDefinitionNode $operation) use ($context): void {
                $rootType = $context->getSchema()->getOperationType($operation->operation);
                if ($rootType !== null) {
                    $this->walk($context, $operation->selectionSet, $rootType, [], []);
                }
            },
        ]);
    }

    /**
     * @param array<string, int> $seen coordinates used on the current path
     * @param array<string, true> $fragments fragments entered on the current path
     */
    private function walk(QueryValidationContext $context, SelectionSetNode $selectionSet, Type $parentType, array $seen, array $fragments): void
    {
        foreach ($selectionSet->selections as $selection) {
            if ($selection instanceof FieldNode) {
                if (! $parentType instanceof HasFieldsType || ! $parentType->hasField($selection->name->value)) {
                    continue; // unknown fields are reported by the FieldsOnCorrectType rule
                }

                $coordinate = $parentType->name . '.' . $selection->name->value;
                $count = ($seen[$coordinate] ?? 0) + 1;
                if (isset($this->limits[$coordinate]) && $count > $this->limits[$coordinate]) {
                    $context->reportError(new Error(
                        "Field \"{$coordinate}\" may appear at most {$this->limits[$coordinate]} time(s) on one path.",
                        [$selection]
                    ));

                    continue;
                }

                if ($selection->selectionSet !== null) {
                    $fieldType = Type::getNamedType($parentType->getField($selection->name->value)->getType());
                    $this->walk($context, $selection->selectionSet, $fieldType, [$coordinate => $count] + $seen, $fragments);
                }
            } elseif ($selection instanceof InlineFragmentNode) {
                $type = $selection->typeCondition !== null
                    ? $context->getSchema()->getType($selection->typeCondition->name->value)
                    : $parentType;
                if ($type !== null) {
                    $this->walk($context, $selection->selectionSet, $type, $seen, $fragments);
                }
            } elseif ($selection instanceof FragmentSpreadNode) {
                $fragment = $this->getFragment($selection);
                $name = $selection->name->value;
                if ($fragment === null || isset($fragments[$name])) {
                    continue; // fragment cycles are reported by the NoFragmentCycles rule
                }

                $type = $context->getSchema()->getType($fragment->typeCondition->name->value);
                if ($type !== null) {
                    $this->walk($context, $fragment->selectionSet, $type, $seen, $fragments + [$name => true]);
                }
            }
        }
    }

    protected function isEnabled(): bool
    {
        return $this->limits !== [];
    }
}

Usage for your example:

DocumentValidator::addRule(new FieldRepetitionLimit([
    'Article.comments' => 1,
    'Comment.article' => 1,
]));

Results:

{ articlesList { title comments { message } } }                          ok
{ commentsList { message article { title } } }                           ok
{ articlesList { comments { article { title } } } }                      ok
{ articlesList { comments { article { comments { article { title } } } } } }
  → Field "Article.comments" may appear at most 1 time(s) on one path.
{ articlesList { ...A } } fragment A on Article { comments { article { comments { message } } } }
  → Field "Article.comments" may appear at most 1 time(s) on one path.
{ articlesList { comments { message } c2: comments { message } } }       ok (siblings don't count)

Because the limits are per field and not a global depth, legitimate deep queries elsewhere in the schema are unaffected, and you can still keep a generous QueryDepth as a backstop.