High Stakes, Low Certainty: Evaluating the Efficacy of High-Level Indicators of Compromise in Ransomware Attribution

DISPATCH: Unraveling Security Patches from Entangled Code Changes

Speakers: Shiyu Sun (George Mason University); Yunlong Xing (George Mason University); Xinda Wang (University of Texas at Dallas); Shu Wang (Inc); Palo Alto Networks (Inc); Qi Li (Tsinghua University); Kun Sun (George Mason University)

Conference: USENIX Security

YouTube: N/A - This is a peer-reviewed conference paper, not a recorded talk.

Overview

This article delves into DISPATCH, a novel patch decomposition system designed to disentangle individual security patches from complex, multi-purpose code changes. Presented by researchers from George Mason University, the University of Texas at Dallas, Tsinghua University, and industry partners Inc and Palo Alto Networks, DISPATCH addresses a critical challenge in software security: the delayed or compromised deployment of vital security updates due to their entanglement with non-security-related modifications. This entanglement complicates patch detection, verification, and deployment, often leading to increased maintenance overhead and prolonged exposure to known vulnerabilities.

The significance of DISPATCH lies in its ability to accurately isolate single-concern security fixes, making them easier to understand, test, and apply. By providing a fine-grained understanding of patch contents, DISPATCH empowers organizations to prioritize security updates, verify their efficacy without introducing regressions, and ultimately accelerate the secure patching of systems. This innovation is crucial for maintaining the integrity, confidentiality, and availability of computing resources in an era of escalating cyber threats.

DISPATCH introduces a new graph representation called PatchGraph to capture detailed code modifications, including syntax and dependency changes. It then employs a two-stage patch dependency analysis to group related statements into individual security patches, outperforming existing methods by at least 20% in accuracy and achieving over 91.9% recall in identifying individual security patches across diverse software repositories like OpenSSL, Linux Kernel, ImageMagick, and Nginx. This capability not only streamlines the patching process but also enhances the overall security posture of software systems.

Background

Software patches are essential for maintaining the health and security of computing systems, addressing issues ranging from bugs and performance enhancements to critical security vulnerabilities. While best practices advocate for single-purpose patches to facilitate understanding, testing, and deployment, real-world development often sees security patches "entangled" with other types of changes. Research indicates that between 11% and 39% of security patches are intricately mixed with non-fixing changes, and a specific sample of 500 security patches from NVD revealed that 34.6% (173/500) were entangled with at least one other security or non-security patch.

This entanglement creates significant challenges. Directly applying such complex patches can introduce unforeseen bugs or regressions, escalating the complexity of testing and verification. For organizations, entangled patches hinder the ability to prioritize security updates, rigorously verify their effectiveness, and ensure compatibility, thereby delaying critical security fixes and prolonging exposure to known vulnerabilities. For example, a non-security change like updating a function signature, when intertwined with a security fix, might cause users to reject the entire patch due to compatibility concerns, even if the security fix could be applied independently. A case study on OpenSSL pull requests revealed that 70% of 90 identified entangled patches were not merged, underscoring the practical difficulties.

Existing code change decomposition methods, while helpful for code review, fall short when it comes to isolating security patches. These methods, which include heuristic-based, slicing-based, and graph clustering-based solutions, often focus on connecting related parts without explicitly defining boundaries for individual, deployable patches. Consequently, they tend to include irrelevant statements in a "bloated" security patch, increasing testing efforts, or fail to guarantee the completeness of a security patch, potentially leading to compilation failures or incomplete vulnerability fixes. The core problem is that these traditional methods primarily preserve deleted/added syntax, neglecting "updated" statements and fine-grained dependency modifications that are crucial for accurately delineating patch purposes.

Key Findings

DISPATCH makes several significant contributions to the field of software security and program analysis, addressing the long-standing challenge of disentangling security patches:

• High Accuracy in Patch Decomposition: DISPATCH successfully unravels individual patches from entangled ones with an impressive average accuracy of 90.05% across various OpenSSL versions, outperforming traditional slicing by approximately 50%. When specifically identifying individual security patches, DISPATCH achieves a recall of 91.9% and a precision of 87.75% on OpenSSL 1.1.1.
• Superior Performance over State-of-the-Art (SOTA) Methods: In comparative evaluations, DISPATCH demonstrated substantial improvements over existing methods like SPatch (slicing-based), GPT-4 (LLM-based), and UTANGO (GNN-based). DISPATCH consistently outperformed these baselines, achieving an accuracy improvement of at least 20%, showcasing its advanced capabilities in patch decomposition.
• Novel Graph-Based Patch Representation (PatchGraph): A key innovation is the PatchGraph, which captures fine-grained code modifications by retaining changed syntax and dependencies between pre-patch and post-patch code. This representation goes beyond simply identifying deleted or added lines to precisely detail what has been changed and how those changes are made, including "diff behaviors" for updated statements and components.
• Two-Stage Patch Dependency Analysis: DISPATCH employs a sophisticated two-stage analysis process. The first stage, statement-level dependency analysis, groups modified statements into "patch segments" by excluding irrelevant changes, guided by diff behaviors and empirically derived patterns. The second stage, segment-level dependency analysis, merges these segments into complete, individual patches, ensuring grammatical correctness and functional completeness.
• Pattern-Guided Slicing for Refined Scope: The system incorporates a constrained slicing method guided by a set of empirically summarized patch patterns. These patterns, derived from over 5,000 security patches and non-security commits, define anchor nodes, slicing directions with termination criteria, and security attribute indicators. This allows DISPATCH to precisely define the scope of each patch segment, preventing the inclusion of irrelevant statements and ensuring the completeness of security fixes.
• Scalability and Generalizability: DISPATCH's effectiveness and generalization capability were demonstrated across four popular and diverse software repositories: OpenSSL, Linux Kernel, ImageMagick, and Nginx. It maintains strong performance even with large patches involving hundreds of individual changes and thousands of lines of code, achieving an average accuracy of 95% across these applications.
• Identification of Undisclosed Security Patches: Beyond publicly indexed CVEs, DISPATCH proved capable of identifying previously undisclosed or "silent" security patches. In OpenSSL 1.1.1, DISPATCH successfully decomposed and pinpointed 444 (92.5%) of 480 newly identified security patches that were not publicly indexed by NVD, showcasing its potential for proactive vulnerability discovery.

Technical Deep Dive

DISPATCH's core innovation lies in its ability to model and analyze code changes at a fine-grained level, moving beyond traditional program analysis techniques to specifically address the nuances of software patches. This is achieved through its PatchGraph representation and a two-stage patch dependency analysis.

Patch Representation: The PatchGraph

Traditional program representations like Abstract Syntax Trees (ASTs), Control Dependency Graphs (CDGs), Data Dependency Graphs (DDGs), and Call Graphs (CGs) are excellent for understanding a single version of code. However, they are insufficient for patches, which inherently involve two versions (pre-patch and post-patch). Simply merging these graphs often leads to detached, inadequate, or redundant representations that fail to highlight fine-grained modifications.

To overcome this, DISPATCH introduces diff behavior, a new type of program dependency that precisely records deleted, added, and updated behaviors in code changes. The PatchGraph is constructed by overlaying these essential diff behaviors onto traditional program dependencies.

1. Identifying Deleted/Added/Updated Statements: DISPATCH first analyzes the version diffs (e.g., Git commits) using a logic similar to GitHub's split view.

• Deleted statements are present in the pre-patch but absent in the post-patch (lines prefixed with '-').
• Added statements are present in the post-patch but absent in the pre-patch (lines prefixed with '+').
• Updated statements are pairs of statements, one from pre-patch and one from post-patch, that share the same statement type and common variables, but have internal variations. This also accounts for cases where a single statement is broken into multiple or multiple statements are merged.

1. Identifying Deleted/Added/Updated Components: Once statements are categorized, DISPATCH drills down to individual components (e.g., variables, functions, conditions, return values) within those statements.

• For deleted/added statements, all elements are considered deleted/added components.
• For updated statements, tokens are compared to identify which components were deleted, added, or updated between the paired statements.

1. Identifying Diff Behaviors: These fine-grained changes are then formally described as diff behaviors.

• Deleted/Added behaviors are represented as a 3-tuple: (modification type, token type, token details), e.g., (deleted, assignment, *q).
• Updated behaviors use a 4-tuple: (modification type, token type, paired statement id, token details), e.g., (updated, function, pre_8:post_9, free:clear_free). This explicitly links the pre- and post-patch versions of the modified component.

1. Constructing the PatchGraph: The PatchGraph is a directed graph (V, E).

• Nodes (V) represent statements in the patch and are described by a 5-tuple: (id, version, code, type, property). id is the line number, version is pre-patch or post-patch, type is deleted, added, updated, or unchanged. property includes paired node IDs for updated statements or modified content for deleted/added statements.
• Edges (E) represent dependencies and are described by a 6-tuple: (id1, id2, version, modification type, edge type, property). edge type can be CDG, DDG, CG, or diff behavior. The property details the specific dependency or modified token. For instance, an edge linking an updated function call would have edge type: diff behavior and property: function | free:clear_free.

Individual Patch Generation: Two-Stage Patch Dependency Analysis

With the comprehensive PatchGraph, DISPATCH employs a two-stage dependency analysis to decompose entangled patches into individual, single-concern patches.

Stage 1: Patch Statement Dependency Analysis (Generating Patch Segments)

This stage aims to aggregate code changes that serve the same purpose into patch segments. It employs a novel constrained slicing mechanism called pattern-guided slicing.

1. Diff Behavior Based Clustering: Initially, a slicing operation groups nodes linked by the same diff behavior into preliminary patch segments, identifying changes like restricted conditions or memory management actions.
2. Pattern-Guided Slicing: This is the core of statement-level analysis. DISPATCH leverages empirically summarized patch patterns to guide the slicing process.

• Pattern Summary: Three doctoral students with extensive software security experience manually analyzed 5,000 security patches from NVD and PatchDB, and 5,000 non-security commits from GitHub. This resulted in 12 types of security patch patterns (categorized into sanity checks, function operations, variable operations, and return statements) and 3 types of non-security patch patterns (debugging, code refactoring, new features). These patterns are extensible and C/C++ focused in the current implementation.
• Patch Pattern Structure: Each pattern is a 4-tuple: (anchor node, forward slicing termination criteria, backward slicing criteria, security attribute indicator).
• Anchor nodes are starting statements (e.g., an if statement for "Add Sanity Check").
• Slicing direction with termination criteria defines which statements are associated with the anchor node along specific dependencies (e.g., control dependencies for forward slicing, variable definitions for backward slicing).
• Security attribute indicator determines if a resulting patch segment is security-related (e.g., checking for keywords like NULL, MAX, MIN, or error statuses).
• Slicing Process: For each identified anchor node, backward and forward slicing are performed on specified dependencies until termination criteria are met. The resulting slice, a patch segment, is then labeled as security or non-security based on the security indicator. For example, an if (p == NULL) statement identified as an "Add Sanity Check" anchor would lead to slicing the if body and related variable definitions, labeling the segment as security-related if it involves error handling.

Stage 2: Patch Segment Dependency Analysis (Generating Individual Patches)

After obtaining patch segments, this stage focuses on integrating them into fully functional, grammatically correct individual patches and accurately identifying security-specific ones.

1. Patch Segment Integrator:

• Intraprocedural Remaining Dependency Analysis: Examines unvisited CDG and DDG edges within a function. It ensures nested statement completeness and includes DDG edges if variables in later segments are newly defined and assigned.
• Interprocedural Remaining Dependency Analysis: Completes patches across functions and files, analyzing caller-callee relationships for modified or newly added functions and handling macro definitions and usages.
• Patch Segment Similarity Analysis: Addresses cases where segments fix the same type of vulnerability but lack direct call/data/control dependencies. It calculates sequential similarity using Levenshtein distance (threshold > 0.9) to group syntactically similar segments.

1. Individual Security Patch Identification:

• If an individual patch contains only one type of segment (security or non-security), it inherits that label.
• If an individual patch contains both security and non-security segments, further analysis is conducted:
• If the security patch candidate is part of a non-security segment (e.g., a security fix within a refactoring change), it's treated as non-security.
• If the functionality of the security patch (e.g., a sanity check condition) already exists in the pre-patch code, the individual patch is treated as non-security, as it doesn't introduce a new security fix.
• Remaining individual patches are labeled as security patches.

Demo / Proof of Concept

The paper illustrates DISPATCH's capabilities with a motivating example from OpenSSL (Figure 1 in the paper), demonstrating how an entangled patch containing both a non-security optimization and a critical security fix is successfully decomposed.

The Entangled OpenSSL Patch:

The example patch involves changes in the RSA_padding_check_OAEP_mgf1 function.

• Non-security patch (Lines 4-6, 10-15): Optimizes memory allocation. The pre-patch allocated db and em then checked both for NULL. The post-patch optimizes this by allocating em only after db is successfully allocated and uses OPENSSL_zalloc (Lines 11) instead of OPENSSL_malloc followed by memset (Lines 4, 10). This is a structural optimization, not a security fix.
• Security patch (Lines 18-21): Replaces OPENSSL_free with OPENSSL_clear_free for variables db and em. OPENSSL_clear_free securely clears memory containing sensitive information before freeing it, preventing potential memory leakage vulnerabilities.

PatchGraph Construction:

DISPATCH first constructs a PatchGraph (Figure 1b). It identifies "diff behaviors" beyond simple additions/deletions:

1. Changing memory allocation functions for em (Lines 4, 10, 11).
2. Splitting the conditional statement (Line 5) into two if checks (Lines 6, 12).
3. Updating free functions (Lines 18, 20 and Lines 19, 21) to a more secure variant.

These diff behaviors, combined with the pre- and post-patch CDG/DDG, form the comprehensive PatchGraph.

Two-Stage Patch Dependency Analysis:

1. Statement-Level Analysis:

• Diff Behavior Guided Slicing: Groups statements based on diff behaviors. For example, the security function replacement (Lines 18-21) is identified as a security candidate segment s3.
• Pattern Guided Slicing: Uses predefined patterns. For instance, the "Add Sanity Check" pattern identifies the new if (em == NULL) check (Line 12) as an anchor node. Forward slicing captures the error handling (Lines 13-14), and backward slicing captures the assignment of em (Line 11), forming segment s4 (Lines 11-14). Other changes form segments s1 (Lines 4, 6) and s2 (Line 5, 10).
• This stage results in four patch segments: s1 (memory allocation changes for db), s2 (initial if check change), s3 (secure memory deallocation), and s4 (new em allocation and error check).

1. Segment-Level Analysis:

• Patch Segment Integrator: Re-examines dependencies. It finds essential dependencies between s1 and s2, and s1 and s4. However, dependencies between s1 and s3, and s3 and s4 are deemed dispensable because the values of em and db are independent of whether s3 is applied.
• Individual Security Patch Identification: After merging essential segments, two individual patches emerge: s1+s2+s4 and s3.
• s1+s2+s4 (Lines 4-15) involves memory allocation and error handling. Although s4 looks like a security check, it's determined that the functionality (checking em for NULL) was already implicitly covered in the pre-patch's Line 5. Thus, s1+s2+s4 is classified as a non-security patch (an optimization).
• s3 (Lines 18-21), involving OPENSSL_clear_free, is definitively a security patch.

This example clearly demonstrates how DISPATCH, through its fine-grained analysis and two-stage decomposition, successfully isolates the security patch from the non-security changes, enabling independent application.

The paper also presents other complex scenarios:

• Security Patches Entangled with Non-security Patches (Listing 7): A patch refactoring a while loop into a for loop (non-security) is entangled with a call to OPENSSL_free to prevent memory leakage (security). DISPATCH's pattern-guided slicing and segment analysis correctly identify and separate these two distinct patches.
• Security Patches Entangled with Security Patches (Listing 8): A patch that improves a conditional check (if (klen <= 0) to if (klen < 0)) is entangled with a call to OPENSSL_cleanse (secure memory clearing). DISPATCH can still decompose these into separate security patches, allowing administrators to understand the specific security concerns addressed by each component.

Defensive Implications

The capabilities of DISPATCH have profound implications for software defenders and the broader security ecosystem:

1. Accelerated Security Patch Deployment: By unraveling individual security patches, DISPATCH enables developers and system administrators to quickly identify, verify, and apply critical security fixes without being burdened by intertwined non-security changes. This significantly reduces the window of vulnerability, a crucial factor in mitigating risks from newly disclosed threats.
2. Enhanced Patch Verification and Testing: Isolating security patches simplifies the testing process. Defenders can focus their testing efforts specifically on the security-related code, ensuring its efficacy without the complexity of testing unrelated functional changes. This minimizes the risk of introducing regressions or new bugs, which is a major concern with entangled patches.
3. Improved Risk Prioritization: Organizations can gain a clearer understanding of which parts of a large, entangled commit address specific vulnerabilities. This allows for more accurate risk assessment and prioritization, ensuring that the most critical security updates are deployed first.
4. Proactive Vulnerability Management: DISPATCH's ability to identify "silent" or previously undisclosed security patches (as demonstrated by pinpointing 92.5% of newly identified security patches in OpenSSL) offers a powerful tool for proactive vulnerability management. This can help uncover implicit security improvements or fixes that were not formally documented as CVEs, further strengthening a system's security posture.
5. Streamlined Compliance and Auditing: For compliance-driven environments, DISPATCH provides a precise record of security fixes applied. This granular decomposition can simplify auditing processes by clearly delineating which code changes were made to address specific security concerns.
6. Better Code Quality and Maintainability: By encouraging the decomposition of changes, DISPATCH implicitly promotes cleaner commit hygiene. Developers can use such tools to ensure their commits are single-purpose, making codebases easier to understand, review, and maintain in the long run.
7. Integration into CI/CD Pipelines: The automated nature and high accuracy of DISPATCH make it a strong candidate for integration into Continuous Integration/Continuous Deployment (CI/CD) pipelines. It could automatically analyze incoming patches, flag security-related changes, and even suggest decomposed security-only patches for faster review and deployment.
8. Targeted Security Research: The PatchGraph representation and the pattern-guided slicing could serve as foundational components for further automated security research, such as identifying common patching patterns for specific vulnerability types or detecting subtle security regressions.

In essence, DISPATCH transforms the complex, often manual process of patch analysis into an automated, precise, and actionable defense mechanism, ultimately leading to more secure software systems and more efficient security operations.

Key Takeaways

• Entangled patches pose a significant threat to software security by delaying the deployment of critical fixes, increasing testing overhead, and prolonging exposure to known vulnerabilities.
• DISPATCH introduces a novel PatchGraph representation that captures fine-grained "diff behaviors" (deleted, added, and updated syntax and dependencies) between pre-patch and post-patch code, providing a comprehensive view of modifications.
• A two-stage patch dependency analysis is central to DISPATCH's accuracy, comprising statement-level analysis (using diff behaviors and pattern-guided slicing to form patch segments) and segment-level analysis (integrating segments for completeness and accurate security labeling).
• Pattern-guided slicing, based on 12 security and 3 non-security patterns, is crucial for precisely defining patch boundaries and identifying security-related modifications, leading to high decomposition accuracy.
• DISPATCH significantly outperforms existing state-of-the-art methods (slicing-based, LLM-based, and GNN-based approaches) by at least 20% in accuracy, achieving over 90% overall accuracy and 91.9% recall for individual security patches.
• The system is scalable and generalizable across diverse, real-world projects like OpenSSL, Linux Kernel, ImageMagick, and Nginx, and can even identify previously undisclosed or "silent" security patches, offering a powerful tool for proactive vulnerability management.

About the Speaker(s)

The research behind DISPATCH was a collaborative effort involving several distinguished researchers and institutions.

Shiyu Sun and Yunlong Xing are affiliated with George Mason University, which is also the institution of Kun Sun. George Mason University is known for its strong programs in computer science and cybersecurity.

Xinda Wang is associated with the University of Texas at Dallas, another institution recognized for its contributions to computer science and engineering research.

Shu Wang is affiliated with Inc, and the paper also lists Palo Alto Networks (Inc) as a contributor, indicating industry involvement and practical relevance in the cybersecurity space.

Qi Li is from Tsinghua University, a leading research institution globally, particularly strong in computer science and engineering in China.

The collective expertise of these authors, spanning multiple academic institutions and industry, underscores a strong background in software security, program analysis, and vulnerability research, which is evident in the sophisticated design and thorough evaluation of the DISPATCH system. Their work contributes significantly to advancing automated tools for enhancing software supply chain security.