Taint Analysis for Graph APIs Focusing on Broken Access Control

This paper presents a novel hybrid approach combining static graph transformation-based taint analysis with dynamic verification to systematically detect both direct and indirect broken access control vulnerabilities in Graph APIs, as demonstrated through an application to the GitHub GraphQL API.

The Gist

Imagine you have a giant, digital library where people can borrow books, write notes in them, and even tear out pages. This library is managed by a Graph API. Think of the API not as a boring computer program, but as a super-efficient librarian who understands that everything in the library is connected. A "book" is a node, and the fact that "Book A" is related to "Author B" is an edge connecting them.

Now, imagine this library has strict rules:

• The Owner can do anything (borrow, write, destroy).
• The Collaborator can borrow and write, but not destroy.
• The Guest can only look at the cover.

The problem? Sometimes, the librarian makes a mistake. Maybe a Guest is accidentally allowed to tear out a page, or an Owner is blocked from writing a note. This is called Broken Access Control. It's like giving a janitor the keys to the CEO's safe, or locking the CEO out of their own office.

This paper introduces a new way to find these mistakes before bad actors do. They call it Taint Analysis. Here is how it works, broken down into simple steps:

1. The "Sticky Note" Strategy (Tainting)

Imagine you take a bright red sticky note and stick it on every piece of information in the library that is sensitive (like a "Repository" or a "Project"). You tell the librarian: "Hey, anything with a red sticky note on it is special. Only people with the right badge can touch it."

In the paper, they call this Tainting. They mark the digital "nodes" (the data objects) that need protection.

2. The "Source" and the "Sink"

Now, the authors look at the librarian's job description (the API calls) and categorize them into two types:

• The Source (The Creator): These are the actions that create new sticky-note-covered items. (e.g., "Create a new Repository").
• The Sink (The Manipulator): These are the actions that touch, change, or delete those sticky-note items. (e.g., "Update a Repository").

The danger happens when a Source creates a secret item, and a Sink tries to touch it later, but the person doing the touching doesn't have the right badge.

3. The Static Check (The "What-If" Game)

Before actually testing the library, the authors play a game of "What If?" using a technique called Critical Pair Analysis.

Imagine you have two cards:

• Card A: "Create a secret file."
• Card B: "Delete a secret file."

The computer asks: "If I do Card A, and then immediately do Card B, does the system allow it?"

• Direct Flow: If Card B happens right after Card A, the computer can easily see if the rules are broken.
• Indirect Flow (The Tricky Part): What if there are other cards in between?
  • Card A: Create File.
  • Card Middle: Add a folder to the file.
  • Card B: Delete the file.

The computer tries to see if the "Middle" card changes the rules. Sometimes, the middle card might accidentally unlock the door for the bad guy. The paper explains that their method is very good at spotting the direct mistakes and some of the indirect ones, provided the rules don't get too chaotic.

4. The Dynamic Check (The "Real World" Test)

The "What-If" game is great, but it might miss things or flag things that aren't actually dangerous (false alarms). So, the authors move to the Dynamic Analysis.

This is where they actually run the tests. They write a script that acts like a mischievous user.

• The Good Test: They try to update a file as the "Owner." (Expected: Success).
• The Bad Test: They try to update a file as the "Guest." (Expected: Failure/Error).

If the "Bad Test" succeeds when it should fail, BINGO! They found a security hole. The librarian let the Guest tear out a page!

5. The Real-World Proof (GitHub)

To prove this works, they applied it to GitHub (the real-world version of our library).

• They looked at a specific issue where a user could compare code branches in a way they shouldn't have been able to, depending on how they logged in.
• Their "Sticky Note" system identified the risky path.
• Their "Real World Test" script actually reproduced the bug, confirming that the security hole was real.

Summary: Why is this cool?

Most security tools look at code line-by-line, like reading a novel word by word. This paper looks at the connections between actions, like looking at the plot of the story.

• The Metaphor: It's like having a security guard who doesn't just check if you have a key, but watches the entire sequence of your day. "You created a secret room, then you walked through a hallway, and now you're trying to open the secret room. Wait a minute, you didn't have a key for the hallway!"

By combining a formal mathematical map of the library (Graph Transformation) with a "sticky note" tracking system (Taint Analysis), this paper gives security experts a powerful, systematic way to find the "broken locks" in modern web applications before hackers find them.

Technical Summary

Here is a detailed technical summary of the paper "Taint Analysis for Graph APIs Focusing on Broken Access Control."

1. Problem Statement

Graph APIs (e.g., GraphQL) model data as nodes and edges, offering flexibility but introducing unique security challenges compared to REST APIs. A primary vulnerability in web applications is Broken Access Control (BAC), where users can access or manipulate data outside their permitted roles.

• The Gap: Existing security testing tools are often ill-suited for Graph APIs because they lack native support for graph-structured data flows. Furthermore, BAC vulnerabilities often arise from complex interactions between API calls (e.g., creating a resource and then manipulating it in a subsequent call), which are difficult to detect with standard static analysis.
• The Challenge: There is a need for a systematic method to trace sensitive data flows through Graph APIs to identify both direct (immediate) and indirect (delayed via intermediate steps) access control violations, distinguishing between policy definition errors and implementation bugs.

2. Methodology

The authors propose a hybrid Static and Dynamic Taint Analysis framework grounded in Graph Transformation (GT) theory. The approach is divided into three segments:

A. Formalization & Setup

• Graph Transformation System: The Graph API schema (types) and operations (queries/mutations) are formalized as a Type Graph ($TG$) and a set of Graph Transformation Rules ($R$).
  • Queries are modeled as Read Rules (matching patterns without modification).
  • Mutations are modeled as Write Rules (creating, updating, or deleting nodes/edges).
• Tainting: A security analyst identifies sensitive data types (e.g., Repository, Issue) in the Type Graph and marks them as Tainted Nodes.
• Source and Sink Identification:
  • Source Rules: Rules that create instances of tainted nodes.
  • Sink Rules: Rules that read, update, or delete instances of tainted nodes.
• Policy Modeling: The access control policy is modeled via a Policy Oracle (theoretical requirement) and a Policy Implementation (actual code behavior).

B. Static Analysis (Dependency Detection)

The static phase aims to identify potential risky flows without executing the code.

• Critical Pair Analysis (CPA): The system uses CPA to compute dependency reasons between Source and Sink rules. A dependency exists if a Source rule creates data that a Sink rule subsequently consumes.
• Tainted Information Flow ($f$): The union of all dependency reasons between Source and Sink rules.
• Soundness & Completeness:
  • The analysis is sound for direct vulnerabilities (where a Sink immediately follows a Source).
  • For indirect vulnerabilities (where intermediate rules exist), the analysis is sound only if the intermediate rules are sequentially independent of the Source/Sink pair and the policy is stable under shift (swapping rule order does not change policy outcomes).
• Classification: The analyst reviews the generated flows to classify them as:
  • Secured Flows ($S_f$): The policy explicitly covers the flow.
  • Unsecured Flows ($U_f$): The policy is missing, ambiguous, or incorrect regarding the flow.

C. Dynamic Analysis (Verification)

The dynamic phase validates the static findings by executing actual API calls.

• Test Generation: Based on $S_f$ and $U_f$, the system generates Taint Tests.
  • Positive Tests: Execute Source $\to$ Sink with roles that should have access. (Expected: Success).
  • Negative Tests: Execute Source $\to$ Sink with roles that should not have access. (Expected: Failure/Exception).
• Coverage Criteria:
  • Flow Coverage: Ensures every dependency reason is tested.
  • Role Coverage: Ensures tests cover various role combinations (e.g., Owner vs. Collaborator) to verify privilege escalation or denial.
• Outcome: If a Positive test fails (denied access) or a Negative test succeeds (unauthorized access), a BAC vulnerability is confirmed.

3. Key Contributions

1. First Systematic Approach for Graph APIs: This is the first work to apply taint analysis specifically to Graph APIs focusing on BAC, utilizing graph transformation as the underlying formalism.
2. Formal Soundness for Indirect Flows: The paper extends taint analysis theory to handle indirect vulnerabilities. It provides a theorem (Theorem 3.13) proving that under conditions of sequential independence and policy stability, indirect flows can be reduced to direct dependencies for detection.
3. Hybrid Static-Dynamic Workflow: The approach combines the scalability of static analysis (finding potential risks) with the precision of dynamic analysis (confirming actual exploits), reducing false positives.
4. Role Coverage Definition: Introduces a new coverage metric ensuring that test cases adequately cover the hierarchy of roles defined in the access control policy.
5. Tool Support & Real-World Application: The approach is implemented using the Henshin tool for static analysis and Python/Pytest for dynamic execution.

4. Results & Evaluation

The authors applied their framework to the GitHub GraphQL API:

• Extended Running Example: They modeled a simplified GitHub-like schema involving Users, Repositories, Issues, and Projects.
  • Static Analysis: Identified 6 dependency pairs (e.g., createRepo $\to$ updateRepo).
  • Dynamic Analysis: Executed 18 test cases (covering secured and unsecured flows).
  • Outcome: All secured flows behaved correctly (access granted to owners, denied to collaborators). Unsecured flows were found to be implicitly secured by GitHub's implementation, validating the framework's ability to detect "false positives" in static analysis.
• Real-World Vulnerability Reproduction (Issue #106598):
  • The team reproduced a known GitHub permission issue regarding the compare field in the Ref object.
  • Finding: The static analysis identified the flow from creating a branch to comparing it. The dynamic analysis confirmed that while OAuth tokens required the repo scope, fine-grained tokens did not, allowing unauthorized comparisons.
  • This demonstrated the framework's ability to detect subtle, real-world access control flaws involving token scopes and authentication methods.

5. Significance

• Security for Modern Architectures: As Graph APIs (especially GraphQL) become ubiquitous in cloud and microservices, this paper provides a critical methodology for securing them against BAC, a top-tier OWASP vulnerability.
• Formal Rigor: By using graph transformation and critical pair analysis, the method moves beyond heuristic scanning to mathematically grounded dependency analysis.
• Practical Applicability: The framework bridges the gap between theoretical security models and practical testing, offering a workflow that security analysts can use to systematically audit API implementations.
• Future Automation: The paper outlines a vision for automating the translation from GraphQL schemas to graph transformation rules, which would significantly lower the barrier to entry for widespread adoption.

In summary, the paper presents a robust, formally verified, and practically tested methodology for detecting Broken Access Control in Graph APIs, successfully identifying both theoretical policy gaps and real-world implementation flaws in a major platform like GitHub.