Leen Lambers ; Lucas Sakizloglou ; Taisiya Khakharova ; Fernando Orejas - Taint Analysis for Graph APIs Focusing on Broken Access Control

lmcs:15080 - Logical Methods in Computer Science, March 10, 2026, Volume 22, Issue 1 - https://doi.org/10.46298/lmcs-22(1:18)2026
Taint Analysis for Graph APIs Focusing on Broken Access ControlArticle

Authors: Leen Lambers ; Lucas Sakizloglou ; Taisiya Khakharova ; Fernando Orejas

    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.


    Volume: Volume 22, Issue 1
    Published on: March 10, 2026
    Accepted on: December 12, 2025
    Submitted on: January 16, 2025
    Keywords: Cryptography and Security, Logic in Computer Science, Software Engineering

    Publications

    Is based on
    Lambers, L. ORCID, Sakizloglou, L. ORCID, Al-Wardi, O. ORCID, & Khakharova, T. ORCID. (2024). Taint Analysis for Graph APIs Focusing on Broken Access Control. In Lecture Notes in Computer Science (pp. 180-200). Springer Nature Switzerland. 10.1007/978-3-031-64285-2_10

    Datasets

    Is supplemented by
    Khakharova, T., Sakizloglou, L., & Lambers, L. (2025). Supplement to "Taint Analysis for Graph APIs Focusing on Broken Access Control" (LMCS journal) (Version 1). Zenodo. 10.5281/ZENODO.14524445