Wendigo: Deep Reinforcement Learning for Denial-of-Service Query Discovery in GraphQL

GraphQL is an enticing alternative to REST APIs as it provides a unified graph abstraction to an application’s web resources. GraphQL shows a widespread adoption across industry with institutions such as Meta, GitHub, X, and PayPal adopting this API, alongside the 33.4% of surveyed API developers who planned to utilize GraphQL in 2020. All the while, DoS attacks are a recurrent issue across multiple domains. The traditional paradigm for DoS attacks involves flooding the target system with high volumes of traffic and protocol exploitation to overwhelm its resources. However, as a result of the powerful nature of GraphQL, complex operations can replace high traffic volumes, making DoS a serious threat to GraphQL applications.

An empirical study exemplifies this stating that most commercial and large open-source GraphQL APIs may be susceptible to DoS. The aforementioned study’s claims are further supported by a 2022 survey stating that of the respondents only 21.7% use timeouts, 23.1% use rate limiting, 26.7% use depth limiting, and 17.5% use cost analysis. With this potential risk in GraphQL, it becomes crucial that developers evaluate whether maliciously crafted queries can cause DoS. To perform this evaluation, as a result of the complex and expansive nature of the potential query space, an automated approach is necessary to search for malicious queries.

To aid in this security testing problem, we propose WENDIGO: a black-box DRL agent-based approach to discover GraphQL queries which can be leveraged to perform a DoS attack.

To the best of our knowledge, we are the first to utilize DRL to discover DoS queries in the GraphQL domain. Evolutionary algorithms have been used for white-box fuzzing of GraphQL applications, focusing on search-based testing and not the discovery of DoS queries. Although they may be effective at finding bugs, we demonstrate that they are insufficient at discovering the GraphQL specific DoS risk in an application. Other research discusses the risk of DoS for GraphQL applications by utilizing specific handcrafted queries. However, our approach eliminates the need to handcraft samples for applications.

Machine learning (ML) based approaches have also been used to great success in other security testing tasks, with DRL specifically being used to search for adversarial inputs in other domains such as SQL injection and cross-site scripting. Although these approaches cannot be directly applied as a result of the differences in domains, their past successes motivate our use of DRL for the task of DoS query discovery in GraphQL.

GraphQL is a query language for APIs which provides flexibility in retrieving data through a single-request declarative approach, thereby addressing both under-fetching and over-fetching problems in REST APIs. For example, consider the scenario in which a client requires a user’s e-mail and the content of their posts.

In a query, objects represent entities, such as users or posts, that consist of fields. Fields within an object are the individual pieces of data or references to objects. In addition, arguments pass on information for the resolution of a specific field, and aliases allow renaming fields in a query for clarity or to prevent naming conflicts. This structure is defined in the schema.

When the aforementioned concepts of GraphQL are used improperly, they can introduce unique attack vectors for DoS. We utilize the DoS attack vectors derived from standard GraphQL features as the set of capabilities used to derive the state and action spaces of our approach.

Static and dynamic tools such as InQL, GraphQL Cop and BatchQL test for these vulnerabilities. However, they focus on detecting each attack vector by performing simple checks. Therefore, they do not focus on the discovery of more complex queries utilizing a combination of these vulnerabilities. To the best of our knowledge, we are the first to utilize DRL to discover DoS exploitable GraphQL queries through the combination of vulnerabilities.

Traditionally, DoS attacks and Distributed DoS (DDoS) attacks, utilize high volumes of traffic to flood networks to impact the availability of an application. However, DoS attacks do not require high traffic volumes, Low-rate DoS (LDoS) attacks such as shrew account for only 10-20% of normal traffic. LDoS attacks achieve DoS through the use of periodic pulses instead of a high volume of traffic while maintaining good attack performance compared to DoS or DDoS. In the case of DoS in GraphQL, we extend the intuition behind the aforementioned LDoS attack however instead of traffic pulses we periodically use complex queries crafted from the aforementioned attack vectors.

Deep Reinforcement Learning (DRL) is a type of ML in which an agent learns through interacting with an environment. The three key components of a DRL problem are the: states, actions, and rewards. From a state, the agent decides on an action that results in a reward and a new state.

WENDIGO consists of two key components: the environment and the agent. The environment converts the GraphQL schema into the state and action spaces. The state space is a recursive expansion of the schema using GraphQL features which increase server load, thereby creating a representation of a bounded subset of the potential query space, therefore the states are representations of potential DoS queries. The action space mirrors that of the state space however it contains add and remove actions for each component of the state space. The agent chooses an action to modify the current query and receives the response time of that modified query as a reward. Through these components, WENDIGO not only discovers queries which induce large response times, but it is also able to build on these queries further maximizing their resource usage.

The motivation behind the design of a black-box approach is that it makes a more realistic threat model, utilizing only the URL and schema which would be available to a realistic adversary as the schema is often publicly available or can be reconstructed. Furthermore, black-box approaches can make security testing accessible to product developers who otherwise lack deep security expertise.

The environment was designed following the specifications of Gymnasium, a standardized agent-environment communication API, allowing compatibility between different agents and environments. The state, action, and rewards of the environment are defined as follows.

The DRL algorithm chosen for our approach is Proximal Policy Optimization (PPO), an actor-critic method, utilizing the original settings and implementation of the algorithm from cleanrl. PPO was chosen as it shows superior performance and training time when compared other algorithms.

We design two random search-based techniques in our environment to show the value of an agent-based approach. First, Random uses random action selection and secondly, Random-Greedy uses a random action selection which only updates the current state if the new response time is greater than the state’s response time. We utilize random search for these approaches following the lead of EvoMaster’s black-box setting.

Target. For evaluation safety we use a docker container of the target application. We utilize Damn Vulnerable GraphQL Application (DVGA), as a proof of concept to show the potential of our approach on a vulnerable application. We do not evaluate WENDIGO on real applications in this initial work because we want to ensure the evaluation is conducted safely in cooperation with the developers.

Baselines. The motivation behind our selection of a baseline from existing approaches is twofold. Firstly, to the best of our knowledge, there are no other approaches designed to discover DoS queries in the GraphQL domain, barring simple test suites which evaluate only the presence of specific attack vectors. Secondly, without alternatives, developers would have to rely on state-of-the-art fuzzers. Therefore utilizing a fuzzer as a baseline evaluates if a GraphQL fuzzer is sufficient to effectively search for DoS queries in an application. For the aforementioned reasons we have decided to utilize EvoMaster, a state-of-the-art GraphQL fuzzer, as our main baseline.

EvoMaster was initially crafted as an evolutionary white-box testing tool tailored for RESTful APIs, relying on their schema provided in the OpenAPI specification format. Recent developments have extended its capabilities to encompass testing for GraphQL APIs. In real-world scenarios, accessing the code for white-box testing may not always be feasible. Fortunately, EvoMaster realises a black-box approach that employs a Random Search on syntactically valid queries to explore the input space.

Additionally, we also utilize Random and Random-Greedy in our environment as additional baselines. For all evaluations the two random agents use the same random seed value therefore the only difference is the aforementioned state transition criteria.

We consider two settings for evaluating query discovery: UNPROTECTED and PROTECTED.

We take the highest response time (HRT) queries from both of the aforementioned settings and utilize them to perform a DoS attack on the application. We conduct this attack by sending the query to the application and waiting for the full response before re-sending the query. This results in pulses of activity by the attacker, akin to that described by the LDoS attack. While the attacker is sending its queries we have a benign user sending a basic query in the same fashion. The benign query has an average response time, over 100,000 queries, of 0.00783 seconds when the application is not under attack. We send queries from both the attacker and benign user for an hour (3,600 seconds) and wait until the last query from both agents is received. We then use the number of attacker queries required to successfully perform the DoS to compare the attack efficacy across settings and approaches.

Metric 4.1 (%Denial). To calibrate the DoS attack to ensure a fair comparison, we use the percentage of benign user response time which is a result of the attack. Formally, we define %Denial as follows:

This section presents the results for our evaluation of WENDIGO on DVGA.

Random and Random-Greedy have comparable performance under this setting as a result of their shared selection strategy. EvoMaster achieves a maximum response time of 23.96s throughout the evaluation, however, only achieves these response times sporadically.

Finally, the PPO agent is able to surpass both the random agents in 114 steps as well as EvoMaster in 144 steps. At 350 steps the agent achieves a response time of 1,649.57s before the application docker is terminated because of memory over-consumption and then the environment and state are restarted to continue evaluation.

For the UNPROTECTED setting, the query with the HRT of all queries is produced by PPO and induces a response time of 1,649.57s. When we utilize this query to perform the attack, we get an average response time of 1,824.18s over 3,648.36s for the attacker and 456.00s over 3,648.04s for the benign user. The attacker is able to successfully perform a DoS with a 99.998%Denial utilizing only 2 queries, the least amount of attack queries required for this setting.

Random performs comparable to Random-Greedy for the first 215 steps. However, subsequently drops off in performance as a result of randomly removing valuable components of the query. Random-Greedy stays within the 20.64s to 57.77s range throughout the evaluation as a result of maintaining sub-optimal states as its baseline. After Random’s initial decline, it is able to slowly increase the response time, eventually surpassing Random-Greedy. As a result of Random not being tied to a baseline state, it can explore more freely. EvoMaster achieves a maximum response time of 29.68s throughout the evaluation. However, it finds such response times sporadically and not consistently like our methods.

Finally, the PPO agent takes 650 steps to surpass EvoMaster and 681 steps to surpass both of the random agents. PPO continues to increase the response time up to 208s at 1,155 step in which the application docker is terminated because of memory over-consumption and then the environment is restarted to continue evaluation. In comparison, it took the UNPROTECTED PPO agent only 219 steps to achieve a 208s response time, thereby showing the impact of constraints on our agents.

For the PROTECTED setting, the query with the HRT of all queries is produced by PPO and induces a response time of 208s. When we utilize this query to perform the attack, we get an average response time of 20.28s over 3,609.65s for the attacker and 5.49s over 3,603.81s for the benign user. The attacker is able to successfully perform a DoS with a 99.852%Denial utilizing 178 queries, the least amount of attack queries required for this setting.

Importance of an Agent. The advantage of utilizing an agent-based approach is evident when comparing across the results. The Random approach suffers from a lack of information resulting from the completely random action selection, thereby discovering good states purely on chance. The Random-Greedy approach is more stable as a result of the state transition criteria maintaining the best state seen so far, however, the approach suffers when the state maintained is sub-optimal. Although both of the random agents perform better than the agent initially, once the agent begins to learn the environment, both random agents are greatly surpassed.

Designed for Purpose. State-of-the-art fuzzers, such as EvoMaster, may be sufficient for finding surface-level DoS queries in GraphQL as can be seen across the results, however, it only scratches the surface. We observe a 68.85x and 7x increase in the max response time for discovery using the UNPROTECTED and PROTECTED settings respectively when compared to EvoMaster. It is essential to take into consideration that EvoMaster was designed for comprehensive coverage of the input space and not to discover DoS queries. Therefore, intrinsically in its structure it lacks the capabilities for array-based query batching, field duplication, and circular object exploitation which are features crucial for DoS query generation in GraphQL. These findings show the importance of having an approach designed for the problem at hand, especially with the high-risk and complex nature of the GraphQL query space.

Impact of DoS in GraphQL. GraphQL’s ability to provide a unified interface for applications, all the while reducing under- and over-fetching, can be very beneficial to benign users and attackers alike. This is exemplified in our DoS Attack results, in which we achieve successful DoS attacks with queries discovered by our approach utilizing only 2 and 178 query requests for the UNPROTECTED and PROTECTED settings respectively. This demonstrates the importance of having an approach able to discover valid queries that pose a DoS threat for the purpose of application testing.

As GraphQL becomes increasingly prevalent and the cybersecurity landscape continues to be challenging, it is essential to recognize how DoS attacks affect GraphQL applications. The potential for significant disruption through the misuse of specific GraphQL features, which can lead to powerful attacks with minimal traffic, necessitates thorough testing. Therefore, this paper introduces WENDIGO, a novel agent-based black-box security testing method aimed at discovering DoS vulnerabilities in GraphQL queries.

• As future work, we first intend to extend the capabilities of our approach by including more pathways for DoS exploitation and investigate the impact that different DRL algorithms and approaches (e.g., hierarchical DRL) have on our query discovery.
• Subsequently, we plan to test the most common GraphQL defenses utilized in the industry to evaluate their robustness to our approach, and identify if these defenses can be improved.
• Finally, we would like to collaborate with developers of real-world applications to be able to safely evaluate our approach in the wild, in addition to aiding in the improvement of DoS robustness for the evaluated application through responsible disclosure.