Taint Analysis for Graph APIs Focusing on Broken Access Control

Leen Lambers ORCID:0000-0001-6937-5167, Lucas Sakizloglou ORCID:0000-0001-6971-1589, Taisiya Khakharova ORCID:0009-0006-7720-1160, Fernando Orejas ORCID:0000-0002-3023-4006 · 2025

Read Taint Analysis for Graph APIs Focusing on Broken Access Control by Leen Lambers ORCID:0000-0001-6937-5167, Lucas Sakizloglou ORCID:0000-0001-6971-1589, Taisiya Khakharova ORCID:0009-0006-7720-1160, Fernando Orejas ORCID:0000-0002-3023-4006 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-08947.txt.

Introduction

Leen Lambers, Lucas Sakizloglou, Taisiya Khakharova, and Fernando Orejas present the first systematic taint analysis for graph APIs, aimed at broken access control. Their paper from twenty twenty-five taints any graph node holding data that needs privileges to touch. Source and sink calls are modeled as graph transformation rules. Critical pair analysis then hunts dependencies that betray a tainted flow.

Direct and indirect flows get separate treatment, with conditions for when the static pass catches each. Flagged flows guide the design of dynamic security tests that confirm real risks. A slice of GitHub's GraphQL API serves as the testbed. Both failure directions surface: users wrongly locked out, and users wrongly let in. API security gains a systematic audit method.

Catalog record

CREATORLeen Lambers ORCID:0000-0001-6937-5167, Lucas Sakizloglou ORCID:0000-0001-6971-1589, Taisiya Khakharova ORCID:0009-0006-7720-1160, Fernando Orejas ORCID:0000-0002-3023-4006
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE98 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-08947

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Taint Analysis for Graph APIs Focusing on Broken Access Control Leen Lambers ORCID:0000-0001-6937-5167, Lucas Sakizloglou ORCID:0000-0001-6971-1589, Taisiya Khakharova ORCID:0009-0006-7720-1160, Fernando Orejas ORCID:0000-0002-3023-4006 Abstract . A Graph API models the data managed by a web application based on the graph data model, i.e., data objects are represented by nodes and relationships by edges. This rather novel type of APIs presents new challenges when it comes to properly securing the APIs against the usual web application security risks, e.g., broken access control. A prominent security testing approach is taint analysis, which traces tainted, i.e., security-relevant, data from sources (where tainted data is inserted) to sinks (where the use of tainted data may lead to a security risk), over the information flow in an application. We present the first systematic approach to static and dynamic taint analysis for Graph APIs focusing on broken access control. The approach comprises the following. We taint nodes of the Graph API if they represent data requiring specific privileges in order to be retrieved or manipulated, and identify API calls which are related to sources and sinks. Then, we statically analyze whether a tainted information flow between API source and sink calls occurs. To this end, we model the API calls using graph transformation rules. We subsequently use Critical Pair Analysis to automatically analyze potential dependencies between rules representing source calls and rules representing sink calls. We distinguish direct from indirect tainted information flow and argue under which conditions the Critical Pair Analysis is able to detect not only direct, but also indirect tainted flow. The static taint analysis (i) identifies flows that need to be further reviewed, since tainted nodes may be created by an API call and used or manipulated by another API call later without having the necessary privileges, and (ii) can be used to systematically design dynamic security tests for broken access control. The dynamic taint analysis checks if potential broken access control risks detected during the static taint analysis really occur. We apply the approach to a part of the GitHub GraphQL API. The application illustrates that our analysis supports the detection of two types of broken access control systematically: the case where users of the API may not be able to access or manipulate information, although they should be able to do so; and the case where users (or attackers) of the API may be able to access/manipulate information that they should not. Jan. 16, 2025Mar. 10, 2026 [a] [a] [a] [b] † † lmcs-doi: Volume 22, Issue 1, Paper 18 1. Introduction A Graph API models the data managed by a web application based on the graph data model, i.e., data objects are represented by nodes and relationships by edges. While initially they emerged to facilitate data management in social networks, Graph APIs are currently used by an increasing number of software applications in the area of service-oriented and cloud computing [ ZZX+23 , QFGR23 ] . A prominent specification and query language for Graph APIs is GraphQL [ GFa ] . GraphQL was introduced by Facebook in 2012 as part of the development of mobile applications, and is now used in various web and mobile applications, e.g., GitHub, Pinterest, Paypal, etc. Security [ Gra07 ] is particularly important in the area of web and mobile applications. Graph APIs are still relatively new, which means that a wide range of methods and tools for security analyses are not yet available for them [ QFGR23 , PMY23 ] . Taint analysis is a typical representative of such security analyses. It is a particular instance of data flow analysis [ PY07 ] and systematically tracks certain user inputs through the application. Broken access control is considered as one of the most prominent security vulnerabilities for web applications [ Tea ] . Access control enforces policies such that users cannot act outside their intended permissions. Failures typically lead to unauthorized information disclosure, modification, or destruction of all data or performing a business function outside the user’s limits. Typical access control failures occur when an API can be accessed with (i) missing or misunderstood access control, or (ii) wrongly implemented access control. Such failures occur in practice, as demonstrated by issues in the GitHub community forum, e.g., issues 110618, 106598, 85661 [ Gitb ] . In this paper, we present a taint analysis for Graph APIs focusing on broken access control (BAC). Specifically, our approach builds on the concept of taint analysis, which propagates taint labels through the implementation of a program, to trace the flow of sensitive data through the Graph API. Graph transformation is a technique dedicated to formalizing graph manipulations and is therefore a natural foundation for formalizing a Graph API. Specifically, we formalize both a Graph API and the taint analysis using concepts from graph transformation [ Roz97 , EEPT06 , HT20 ] and rely on related, formally founded tool support to perform part of the analysis. A security analyst can use the taint analysis to systematically and soundly check for BAC vulnerabilities. To the best of our knowledge, no other approach to checking for BAC vulnerabilities simultaneously supports key feature of our approach: use of taint analysis, native graph formalization, and sound detection—see discussion in Section 5 . We illustrate the taint analysis based on GraphQL, but our approach is applicable to any kind of Graph APIs that can be formalized using graph transformation. The presented taint analysis comprises three segments: the setup, the static analysis, and the dynamic analysis. During setup , the security analyst can taint nodes of the Graph API that represent sensitive data. This Graph API is represented formally using graph transformation rules typed over a type graph. The security analyst thus taints nodes in the type graph, representing node types entailing sensitive data that may be processed by the Graph API. From these tainted nodes, we can characterize graph transformation rules as Graph API sources , where tainted data are inserted, i.e, created by the rule, and sinks , where tainted data are used, i.e, changed by the rule, and may thus lead to a security risk. The static analysis supports the security analyst in validating the access control policies, i.e. finding missing or misunderstood access control policies. This is achieved by automatically generating pairs of source and sinks that may be risky in terms of leaking sensitive data and thus represent potential BAC vulnerabilities. The security analyst can then systematically check if the policy description indicates that it properly secures these risky flows. Subsequently, the dynamic analysis supports the security analyst in verifying that the access control policies are implemented correctly. If the security analyst expects a risky flow based on the results of the static analysis, then they can systematically try to uncover a corresponding BAC vulnerability in the Graph API implementation. We demonstrate that the static analysis is sound w.r.t. finding potential direct BAC vulnerabilities, i.e, when a sink directly follows a source, as well as a type of indirect ones, i.e, when other data manipulations occur between source and sink. However, since the static analysis is incomplete, we integrate it with a subsequent complete dynamic analysis. Graph transformation is a formal paradigm with many applications. A graph transformation system is a

Read the complete text