Undefined-oriented Programming: Detecting and Chaining Prototype Pollution Gadgets in Node.js Template Engines for Malicious Consequences

Undefined-oriented Programming: Detecting and Chaining Prototype Pollution Gadgets in Node.js Template Engines for Malicious Consequences

Speakers: Zhengyu Liu, Kecheng An, Yinzhi Cao

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=WRVVnlzRrss

Overview

This talk, presented by Zhengyu Liu from Johns Hopkins University, delves into a sophisticated exploitation technique for Prototype Pollution (PP) vulnerabilities in JavaScript, specifically within Node.js template engines. While Prototype Pollution has been recognized as a significant vulnerability since 2018, its direct exploitation often falls short of achieving high-impact consequences like Cross-Site Scripting (XSS) or Remote Code Execution (RCE) without additional gadgets. This work introduces a novel concept called Undefined-oriented Programming (UOP), which enables the chaining of multiple seemingly innocuous PP gadgets to escalate the severity of an initial pollution.

The core problem addressed is the limitation of prior research, which primarily focused on "direct" PP gadgets where a poisoned property directly leads to a sink. The speakers demonstrate that a more insidious class of "chained" gadgets exists, where one polluted property influences the control or data flow of another, ultimately leading to a malicious outcome. By coining UOP, analogous to Return-oriented Programming (ROP) or Property-oriented Programming (POP), the researchers provide a systematic framework for understanding, categorizing, and automatically detecting these complex chained exploits.

The significance of this research lies in its ability to transform what might seem like a low-severity information disclosure into a critical RCE or XSS vulnerability. The developed UOP framework not only provides a theoretical foundation for understanding these chained attacks but also offers a practical tool for their automatic discovery. Its findings, including 26 zero-day gadgets (30 of which were chained) in widely used Node.js template engines, underscore the pervasive and underappreciated danger of chained Prototype Pollution, urging developers and security practitioners to reconsider their approach to mitigating this class of vulnerabilities.

Background

▶ Watch: Introduction to Prototype Pollution vulnerability (0:00)

Prototype Pollution (PP) is a JavaScript vulnerability that arises from the language's prototype-based inheritance model. In JavaScript, every object has a prototype object from which it inherits properties and methods. This inheritance chain can be traversed via the special __proto__ property (or Object.getPrototypeOf()). Ultimately, most objects inherit from Object.prototype, which sits at the root of the prototype chain. A Prototype Pollution vulnerability occurs when an attacker can inject arbitrary properties or modify existing ones on Object.prototype at runtime. Since Object.prototype is inherited by all JavaScript objects by default, changes made to it affect a vast number of objects throughout the application, leading to unexpected behavior.

Consider a common scenario in web applications where user-supplied data is merged into an existing object, such as updating user information. A typical merge function might recursively copy properties from a client-provided payload to a server-side user info object. If this merge operation does not adequately sanitize or validate input, an attacker can craft a payload containing __proto__ as a key. For example, { "__proto__": { "isAdmin": true } } could inject an isAdmin property directly into Object.prototype, potentially granting administrative privileges to any object that later checks for this property.

However, polluting Object.prototype directly often isn't enough to achieve high-impact exploitation. This is where gadgets come into play. A gadget is a piece of existing code that, when triggered by a polluted prototype property, leads to a security-sensitive action. Previous work primarily focused on direct Prototype Pollution gadgets. In such a scenario, an undefined property lookup (e.g., obj.n where obj doesn't have n) traverses the prototype chain to Object.prototype. If Object.prototype has been polluted with n, the attacker's injected value is returned. If this value then flows directly into a sensitive sink (e.g., eval(), setTimeout(), template rendering functions), it can lead to XSS or RCE. For instance, if obj.n is directly used in new Function(obj.n), a polluted n could execute arbitrary code.

The limitation of prior research, as highlighted by the speakers, is its exclusive focus on these direct gadgets. Many real-world scenarios involve conditional logic or complex data flows that prevent a direct path from an undefined property lookup to a sink. For example, an if statement might check the type of a variable derived from a polluted property, blocking the execution path if the type doesn't match an expected value. Such branches are often "dead code" under normal execution but can be activated by a carefully crafted pollution. This challenge prompted the researchers to rethink how attackers could overcome these obstacles, leading to the concept of gadget chaining.

The idea of chaining small, seemingly harmless code snippets to achieve a larger malicious goal is not new. In the realm of binary exploitation, Return-oriented Programming (ROP) allows attackers to chain small instruction sequences (gadgets) ending in a ret instruction by overwriting the stack's return address. Similarly, Property-oriented Programming (POP) has been developed for object injection or deserialization vulnerabilities in languages like Java, PHP, and Python. POP involves constructing complex object structures that trigger malicious behavior during object instantiation, with gadgets chained through conflicting property or method names across different classes. Drawing parallels from these established paradigms, the researchers introduced Undefined-oriented Programming (UOP) for Prototype Pollution in JavaScript. In UOP, gadgets are linked through different undefined property lookups, and their chaining mechanism relies on their effects on the control or data flow of other gadgets.

Key Findings

▶ Watch: Chaining gadgets to bypass control flow blocks (2:20)

The research presents several significant findings that redefine the understanding and detection of Prototype Pollution vulnerabilities:

1. A Novel Taxonomy for Chained Prototype Pollution Gadgets: The speakers introduced the first comprehensive taxonomy for categorizing chained PP gadgets, based on two distinct criteria:

• Gadget Payload:
• Horizontally chained gadgets: Require the pollution of two or more distinct properties in Object.prototype, triggering separate gadgets in the existing codebase.
• Vertically chained (or self-chained) gadgets: Involve the payload triggering the same gadget multiple times but with different values or nested layers, often to break out of infinite loops or recursive calls.
• Gadget Dependency:
• Data flow dependent gadgets: One polluted property alters the data flow of another gadget, potentially correcting an error or enabling a subsequent exploitation step.
• Control flow dependent gadgets: One polluted property directly affects the control flow (e.g., an if condition) of another gadget, allowing the attacker to steer execution towards a sink that would otherwise be unreachable.

1. The Undefined-oriented Programming (UOP) Framework: To address the challenge of automatically finding these complex chained gadgets, the researchers developed the UOP framework. This framework employs a concolic execution approach, systematically exploring program states by treating undefined properties as symbolic values. It operates in three phases: test unit generation, concolic execution for path exploration and new undefined property discovery, and iterative refinement.

1. Discovery of Numerous Zero-Day Vulnerabilities: Applying the UOP framework to a collection of popular Node.js template engines, the researchers uncovered a significant number of previously unknown vulnerabilities:

• 26 zero-day gadgets were identified.
• 30 of these were chained gadgets, highlighting the prevalence of these complex attack vectors.
• Some affected template engines boast over a million downloads, indicating widespread impact.
• The researchers responsibly disclosed all findings, leading to 7 fixes in the latest versions of the affected libraries.

1. Superior Detection Capabilities: The UOP framework demonstrated superior performance compared to existing tools. When evaluated against two benchmarks (a curated set of Node.js PP gadgets and a GitHub repository of template engines), UOP significantly out-covered previous work, specifically a tool named SilenceBrain and its variants. Notably, UOP achieved this without any false positives on the benchmarks, indicating its precision.

1. Scalability and Effectiveness in Code Exploration: The evaluation showed that the UOP framework is scalable, with analysis time increasing roughly linearly with the number of undefined properties in a template engine. Furthermore, UOP proved highly effective in exploring target programs, discovering new code paths and unique control flows that were previously unreachable without pollution inputs. This capability is crucial for identifying complex, deeply nested gadgets.

These findings collectively establish UOP as a critical new paradigm for understanding and mitigating Prototype Pollution, moving beyond simplistic direct exploitation to encompass the intricate logic of chained attacks.

Technical Deep Dive

▶ Watch: Coining Undefined-oriented Programming (UOP) (4:00)

The core of this research revolves around answering two fundamental questions: how Prototype Pollution gadgets can be chained, and how to automatically discover them in real-world applications. The first question is addressed by the proposed taxonomy, while the second is tackled by the Undefined-oriented Programming (UOP) framework.

Gadget Chaining Taxonomy

The taxonomy categorizes chained gadgets based on their payload structure and their inter-gadget dependency.

Gadget Payload Criteria:

• Horizontally Chained Gadgets: These require polluting multiple distinct properties in Object.prototype. The motivating example illustrates this:
• Gadget 1: An undefined property lookup on obj.n (where n is polluted) flows to a sink, but an if condition (variable.type == 's') blocks it.
• Gadget 2: Another undefined property lookup on obj.m (where m is polluted) flows to the variable.type property, allowing an attacker to control its value.
• By polluting both n and m, the attacker horizontally chains two distinct prototype properties to achieve the desired effect.

• Vertically Chained (Self-Chained) Gadgets: In contrast, these involve polluting a single property name, but the payload requires a nested structure to trigger the same gadget multiple times with different values. A compelling example is a parse function that recursively walks an Abstract Syntax Tree (AST).
• An undefined property lookup within the parse function might lead to Object.prototype. If Object.prototype is polluted with node.plugins, the parse function might then recursively process the attacker-injected plugins value.
• However, if the pollution simply injects a value, the node.plugins lookup will now always return a defined value, potentially leading to an infinite recursive call.
• To break this infinite loop, the attacker needs to inject a nested object structure (e.g., __proto__.plugins = { plug: ... }) such that subsequent recursive calls eventually encounter an undefined plug property, allowing the program to exit the loop or take an alternative path. This demonstrates a self-chaining mechanism where the same property (plugins) is used repeatedly but with a layered payload.

Gadget Dependency Criteria:

• Control Flow Dependent Gadgets: These are exemplified by the motivating example. Gadget 2 (pollution of m) directly influences the if condition of Gadget 1, changing the program's control flow to ensure the payload of Gadget 1 reaches the sink. This allows an attacker to bypass conditional checks that would otherwise prevent exploitation.

• Data Flow Dependent Gadgets: These are particularly common and crucial for maintaining program functionality after pollution. An initial pollution might introduce an undefined value or an incorrect type into a data flow, causing the program to crash or raise an error before reaching a sink.
• Consider a string substitution function where a for-in loop iterates over keys from Object.prototype, and these keys are then used to look up values which are passed to an ESC (escape) function.
• If an attacker pollutes Object.prototype with a simple string value, the for-in loop might extract this string. However, a subsequent lookup like value.name would fail because a string does not have a name property, resulting in undefined. If the ESC function expects a string, passing undefined would cause an error and halt execution.
• To counteract this, a data flow dependent gadget is needed. The attacker must inject another property (e.g., __proto__.myString = { name: "malicious_string" }) such that when myString is looked up, it provides an object with a name property that supplies the correct string type to the ESC function, allowing the malicious payload to proceed. This second pollution corrects the data flow altered by the first.

The UOP Framework for Automatic Detection

The UOP framework is designed to automatically discover these complex chained gadgets. Its high-level idea is to concolically execute the target program, treating undefined properties as symbolic variables whose values can be manipulated to explore different execution paths.

The framework operates in three phases:

1. Phase A: Test Unit Generation:

• Given a target library (e.g., a Node.js template engine) and a normal input test case, the system performs an over-approximated call graph analysis. This identifies all potentially exploitable APIs that could eventually reach a security-sensitive sink.
• An instrumented Node.js runtime is then used to execute these selected test cases. During execution, it records a list of all undefined property lookups. These identified undefined properties become the initial set for testing.
• A scheduler organizes these components into "test units" for subsequent phases.

1. Phase B: Concolic Execution Engine:

• The core of UOP, this engine takes a test unit and systematically explores different program paths that can be triggered by polluting the identified undefined properties.
• When an undefined property lookup is encountered, UOP "pollutes" it with a concolic value. A concolic value is a dual representation: it has a concrete field (a default value for execution) and a symbolic field (representing the constraints and potential values of the injected property).
• As the program executes, all operations involving this concolic value (e.g., property access, arithmetic, comparisons) are modeled. The symbolic field is updated with constraints derived from these operations.
• Lazy Initialization: When the concolic value is treated as an object and a property is accessed on it (e.g., concolicVal.settings), UOP lazily initializes a nested concolic object for settings. This allows for exploration of complex nested prototype pollutions.
• Handling for-in Loops: for-in loops are critical for PP exploitation as they iterate over object properties, including those from the prototype chain. UOP handles this by introducing a symbolic key to the concolic object, which itself is a concolic value of type string, along with a concolic value for its corresponding property value. This allows the engine to capture constraints related to both the key name and its value during iteration.
• Constraint Solving for Control Flow: When a concolic variable is used in a conditional expression (e.g., if (concolicVal == 'expected')), UOP identifies a potential branching point. It then uses a constraint solver to determine a concrete value for the concolic property that would negate the current branch condition, thus activating an alternative control flow path. This is key to discovering control flow dependent gadgets.
• Gadget Identification: If the concolic value successfully flows to a security-sensitive sink (e.g., eval, new Function), the system identifies a gadget. The constraints gathered during execution are then solved to generate the concrete payload required to trigger the exploit.

1. Iteration: Phases A and B are repeated. Critically, during Phase B, the concolic engine often discovers new undefined properties that were not present in the initial set but become accessible through specific pollution inputs. These newly discovered undefined properties are added to the list, and the process iterates, allowing the framework to explore deeper and more complex chains.

Performance and Scalability

The analysis time of the UOP framework is dominated by the concolic execution's gadget search time, which explores different combinations of undefined properties. While static analysis and exploit generation are generally faster, the search for chained gadgets is computationally intensive. However, the evaluation demonstrated that the analysis time increases roughly linearly with the number of undefined properties, indicating the framework's scalability for large template engines. Furthermore, UOP significantly increased code coverage and the number of unique control flow paths explored, confirming its effectiveness in uncovering hidden execution flows conducive to chained gadget exploitation.

Demo / Proof of Concept

▶ Watch: Example: Vertically chained or self-chained gadgets (6:40)

While the talk did not feature a live, interactive demo in the traditional sense, the researchers provided a compelling conceptual walkthrough of how their Undefined-oriented Programming (UOP) framework operates and constructs exploitation payloads. The "motivating example" (02:00-04:00) serves as a foundational proof of concept for chained Prototype Pollution, illustrating how one gadget can manipulate the control flow of another to bypass an if condition and reach a sink.

The concolic execution engine walkthrough (12:00-14:20) further acts as a detailed, step-by-step demonstration of the framework's internal workings. It shows precisely how UOP identifies undefined properties, treats them as concolic values, models their interactions with program operations, lazily initializes nested properties, handles complex constructs like for-in loops, and ultimately solves constraints to generate a concrete payload that chains two gadgets to achieve a desired control flow. This technical exposition effectively functions as a proof of concept for the methodology itself.

The tangible results of the UOP framework's application serve as its most impactful proof of concept. The researchers successfully:

• Identified 26 zero-day Prototype Pollution gadgets, demonstrating the practical efficacy of their tool.
• Confirmed that 30 of these were chained gadgets, validating the prevalence and significance of UOP as an attack paradigm.
• Disclosed these vulnerabilities responsibly, leading to 7 fixes in popular Node.js template engines that collectively have over a million downloads. This real-world impact underscores the framework's ability to discover critical, exploitable vulnerabilities that traditional methods missed.

The fact that the UOP tool is now open source (19:00) also allows other researchers and security professionals to replicate these findings and further develop the framework, providing a strong, verifiable proof of concept for its capabilities.

Defensive Implications

▶ Watch: Example: Data flow dependent gadgets in exploitation (8:00)

The introduction of Undefined-oriented Programming (UOP) significantly raises the bar for defending against Prototype Pollution vulnerabilities in JavaScript applications, particularly those built with Node.js template engines. Traditional defensive strategies and detection tools, which primarily focus on direct pollution, are demonstrably insufficient against chained gadgets.

Here are the key defensive implications:

1. Rethink Prototype Pollution Severity: Developers and security teams must acknowledge that Prototype Pollution is rarely a low-severity issue. With UOP, even seemingly innocuous pollution points can be chained to achieve high-impact consequences like Remote Code Execution (RCE) or Cross-Site Scripting (XSS). Vulnerability assessment should treat any confirmed Prototype Pollution as potentially critical until proven otherwise through deep analysis.

1. Beyond Direct Detection: Existing static analysis tools and runtime monitors that only look for direct flows from a polluted Object.prototype property to a sink will fail to detect UOP-style attacks. Defenders need to adopt more sophisticated analysis techniques, such as concolic execution or advanced program analysis that can track symbolic values and explore complex control and data flow dependencies across multiple execution paths. The UOP framework itself, or principles derived from it, could be integrated into future security tooling.

1. Secure Coding Practices for Object Merging: The primary source of Prototype Pollution is often insecure object merging or deserialization functions. Developers should:

• Validate and Sanitize Input: Strictly validate and sanitize all user-supplied input before merging it into existing objects. Never trust client-side data.
• Avoid Recursive Merging: Be extremely cautious with recursive merge functions that iterate over object properties. If untrusted input is involved, ensure that keys like __proto__, constructor, or prototype are explicitly blacklisted or, preferably, that only whitelisted properties are allowed.
• Use Object.create(null): For objects that should not inherit from Object.prototype, explicitly create them using Object.create(null). This prevents them from being affected by Object.prototype pollution.
• Deep Copying: When merging or cloning objects, prefer deep copying mechanisms that do not inadvertently modify shared prototypes.

1. Awareness for Template Engine Developers: Developers of Node.js template engines and other libraries that handle dynamic object construction or property lookups are at the forefront of this threat. They must rigorously audit their code for potential chained gadget vulnerabilities. The responsible disclosure and subsequent fixes of 7 zero-day vulnerabilities highlight the immediate need for such audits.

1. Runtime Monitoring Enhancements: Enhanced runtime monitoring could potentially detect suspicious modifications to Object.prototype or unusual property lookups that deviate from expected application behavior. However, this is challenging given JavaScript's dynamic nature and the legitimate uses of prototype manipulation. Focusing on deviations from known good behavior or attempts to access sensitive sinks via polluted properties might be a more viable approach.

1. Supply Chain Security: Given that many vulnerabilities were found in popular template engines, organizations must pay closer attention to the security posture of their third-party dependencies. Regularly updating libraries and monitoring security advisories for transitive dependencies is crucial.

In essence, the UOP research mandates a paradigm shift: Prototype Pollution is no longer a simple one-and-done exploit. It is a sophisticated chaining mechanism that requires a holistic understanding of JavaScript's execution model and advanced program analysis techniques to effectively detect and mitigate.

Key Takeaways

• Undefined-oriented Programming (UOP) is a novel exploitation paradigm for Prototype Pollution in JavaScript, enabling the chaining of multiple gadgets to achieve high-impact consequences like RCE or XSS.
• Traditional Prototype Pollution detection is insufficient, as it primarily focuses on direct flows from polluted properties to sinks, missing complex chained dependencies.
• A new taxonomy categorizes chained gadgets based on payload (horizontally vs. vertically/self-chained) and dependency (data flow vs. control flow dependent), providing a structured understanding of these attacks.
• The UOP framework automatically discovers these complex chained gadgets using concolic execution, treating undefined properties as symbolic values to explore intricate control and data flow paths.
• The research uncovered 26 zero-day gadgets (30 of which were chained) in popular Node.js template engines, leading to 7 responsible fixes and highlighting the widespread, underestimated threat.
• UOP framework outperforms previous tools like SilenceBrain in coverage and accuracy, demonstrating its superior capability in identifying real-world exploitable chains.
• The UOP tool is open source, encouraging further research and adoption by the security community.

About the Speaker(s)

The primary speaker for this presentation was Zhengyu Liu, who is affiliated with Johns Hopkins University. He presented the research findings on Undefined-oriented Programming. The co-authors of the work are Kecheng An and Yinzhi Cao, also involved in the research, likely from Johns Hopkins University or a collaborating institution. Their work focuses on advanced security vulnerabilities in software, particularly within the realm of web technologies and programming language exploitation.