TL;DR
This paper introduces COMIX, a novel co-evolutionary algorithm for efficiently detecting multiple XML injection vulnerabilities in web applications simultaneously. By treating each vulnerability as an independent objective, COMIX outperforms existing single-target and multi-target approaches, especially when dealing with a large number of potential vulnerabilities, and uses a computationally cheaper fitness function.
What Problem Does This Paper Address?
Modern web applications often interact with internal web services, creating a complex attack surface. A significant vulnerability is XML Injection (XMLi), where malicious inputs can be crafted to compromise these internal services. Existing search-based testing techniques for XMLi typically focus on finding inputs for one malicious message at a time. This "single-target" approach is inefficient and doesn't scale well when many potential malicious messages (Test Objectives or TOs) need to be tested, especially since some TOs might be infeasible or harder to generate. The paper addresses the challenge of efficiently and effectively detecting multiple XMLi vulnerabilities simultaneously in a black-box manner.
Methods
The core contribution is the COMIX (CO-evolutionary algorithm for MultI-vulnerability testing of Xml injections) algorithm. COMIX is a many-objective, cooperative, and co-evolutionary approach.
- Cooperative Co-evolution: The problem of finding inputs for multiple XMLi vulnerabilities is divided into sub-problems, where each Test Objective (TO) is assigned to a separate "island" (population). These islands evolve independently but interact through migration.
- Multi-Target Approach: Unlike previous methods that tackled one TO at a time, COMIX aims to cover all TOs concurrently.
- Island Selection Heuristic: COMIX uses a feedback-directed approach (similar to MIO) to select islands for evolution, prioritizing those that have shown recent improvements, thus focusing the search.
- Modified MOSA: The authors also adapt and propose a variant of the MOSA (Many-Objective Sorting Algorithm) called vMOSA. This adaptation involves disabling the crossover operator, which was found to be detrimental when recombining chromosomes optimizing different TOs.
- Linear Complexity Fitness Function: To address the computational cost of traditional edit distance, a new, less expensive "linear distance" fitness function is proposed. This function penalizes length differences and character differences using ASCII codes, offering a faster but potentially less guided fitness evaluation.
Datasets
The study evaluated the proposed approach on four web applications:
- SBANK: Three versions (SBANK1, SBANK2, SBANK3) with varying numbers of user inputs. These are simplified versions of real-world bank card processing applications.
- SecureSBANK (SSBANK): Three versions (SSBANK1, SSBANK2, SSBANK3) similar to SBANK but with some input validation/sanitization.
- XMLMAO: An open-source, vulnerable-by-design web application.
- M: A large, real-world industrial web application.
For each application, 50 Test Objectives (TOs) were generated using SOLMI, an automated tool for creating malicious XML messages based on common XMLi attack types.
Key Insights and Ideas
- Multi-target is Key: The paper strongly demonstrates that tackling multiple vulnerabilities simultaneously (multi-target) is significantly more effective and efficient than single-target approaches, especially for larger applications.
- COMIX's Advantage: COMIX, with its cooperative co-evolutionary design and tailored island selection, proves to be a highly effective strategy for this multi-target problem.
- Fitness Function Trade-off: The linear distance fitness function, while less computationally expensive, significantly speeds up the search process, enabling more generations and thus better overall performance, even if it provides slightly less guidance than edit distance. This highlights a crucial trade-off between computational cost and guidance in search-based testing.
- Independence of TOs: The paper emphasizes that XMLi test objectives are independent, meaning covering one doesn't help cover another. This independence justifies the multi-target approach and the design of COMIX.
Key Results
- Coverage: COMIX consistently achieved higher coverage, often reaching 100%, compared to vMOSA, MIO, and the single-target approach, especially when optimizing a larger set of 50 TOs.
- AUC (Area Under the Curve): COMIX achieved significantly higher AUC values across most experiments, indicating it reached higher coverage levels in less time. For example, on SBANK with one input and 50 TOs, COMIX achieved 100% coverage in under 3 minutes, while vMOSA took over 4 minutes.
- Execution Time: COMIX with the linear distance function achieved maximum coverage for 50 TOs within practical time limits (3-23 minutes for most systems, up to 175 minutes for the industrial case study M).
- Fitness Calculation Time: The linear distance function reduced fitness calculation time drastically, often by over 90%, compared to the edit distance, freeing up more time for search.
- Migration Impact: A small migration rate (around 2-10%) in COMIX significantly improved coverage, suggesting that sharing genetic material between islands is beneficial, but too high a rate can be detrimental.
Limitations and Future Work
- Prototype-Based Study: The empirical study was based on a software prototype, and potential bugs or inefficiencies in implementation details could affect performance.
- Malicious Messages vs. Exploitable Vulnerabilities: The number of found TOs represents an upper bound on exploitable vulnerabilities; the actual impact depends on how internal services process these messages.
- Limited Case Studies: The study used a limited number of systems (three open-source, one industrial). More case studies are needed for better generalization.
- Future Work: The authors suggest extending the approach to cover more vulnerabilities and data exchange formats like JSON. They also note that COMIX is a generalizable approach and can be adapted for other attack types by modifying the TOs.
Summary updated