CaFA: Cost-aware, Feasible Attacks With Database Constraints Against Neural Tabular Classifiers

CaFA: Cost-aware, Feasible Attacks With Database Constraints Against Neural Tabular Classifiers

Speakers: Matan Ben-Tov, Daniel Deutch, Nave Frost, Mahmood Sharif

Conference: IEEE S&P

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

Overview

This article delves into CaFA, a novel framework for generating cost-aware, feasible adversarial attacks against neural tabular classifiers. Presented at IEEE S&P, this research by Matan Ben-Tov, Daniel Deutch, Nave Frost, and Mahmood Sharif addresses a critical gap in machine learning security: the difficulty of creating realistic and implementable evasion attacks in the tabular data domain. Unlike image data, where subtle pixel changes can fool models, tabular data features often have complex interdependencies and discrete values, making naive perturbations nonsensical and non-realizable in the real world.

The talk highlights how existing adversarial attack methods, primarily designed for vision tasks, fail when applied to structured tabular data. CaFA proposes a sophisticated approach that leverages database integrity constraints to ensure the feasibility of adversarial examples, alongside a dual cost measure to quantify the effort required for an attack. This work is particularly significant given the widespread deployment of neural networks on tabular data in high-stakes applications like malware detection, medical diagnosis, and financial analytics, where the robustness of these models against targeted attacks is paramount.

By introducing automated constraint mining and a specialized perturbation and projection mechanism, CaFA offers a more realistic and effective means of evaluating the security of tabular machine learning models. It provides a crucial tool for both understanding model vulnerabilities and developing more robust defenses, moving beyond theoretical attacks to practical, implementable adversarial examples that accurately reflect real-world attack vectors.

Background

▶ Watch: Introduction: Challenges of adversarial attacks on tabular data (0:00)

The field of adversarial machine learning has predominantly focused on the vision domain, where techniques like Projected Gradient Descent (PGD) can generate imperceptible noise to induce misclassification in image classifiers. The continuous and high-dimensional nature of pixel data lends itself well to gradient-based optimization, allowing for the creation of visually similar yet adversarial images. However, extending these successful methods to the tabular domain presents significant challenges.

Tabular datasets consist of feature vectors where each coordinate describes a distinct aspect of an input. Unlike pixels, these features often have specific types (e.g., integer, categorical), permissible ranges, and complex semantic dependencies. A naive perturbation, such as adding continuous noise to a categorical feature or altering a value in a way that violates a logical relationship with another feature, results in a "nonsensical sample." For instance, modifying a 'number of children' feature to 0.7 or altering a 'salary' feature without changing 'job title' in a consistent manner can create an input that is mathematically valid in the feature space but impossible to realize in the real-world problem space. This fundamental disconnect between the feature space and the problem space renders many vision-based attack strategies ineffective for tabular data.

Prior attempts to address these challenges in tabular adversarial attacks can be broadly categorized. Some approaches directly attack the problem space, defining a set of allowed transformations. While these can produce realizable attacks, they typically demand extensive domain expertise and manual intervention, severely limiting their generalizability to new datasets. Other methods operate in the feature space, similar to vision attacks, but try to enforce realizability through various means, such as manually coded constraints, training in a latent space, or employing classic machine learning techniques. However, these often struggle with misalignment with the actual problem space and rely on overly simplistic cost models like L0 norm (minimizing the number of modified features) or manually defined costs, which may not accurately reflect the real-world effort required for an attack. The concept of "imperceptibility," crucial in vision, also becomes ambiguous and less relevant when features represent distinct, often discrete, attributes. CaFA aims to overcome these limitations by providing a generic, automated, and more realistic framework for generating feasible and cost-aware attacks on tabular neural classifiers.

Key Findings

▶ Watch: CaFA: Proposed system for cost-aware, feasible attacks (3:20)

The CaFA framework introduces several key findings and contributions that significantly advance the state of adversarial attacks on tabular data:

1. Automated Constraint Mining for Realizability: CaFA's core innovation is its ability to automatically mine and integrate data integrity constraints, specifically structure constraints (e.g., feature type, range) and denial constraints (DCs), from the training data. This automated process, leveraging database techniques, ensures that generated adversarial examples remain semantically consistent and feasible within the problem space, addressing a major limitation of prior work.
2. Dual Cost Measure for Attack Effort: The framework formalizes attack cost using a dual measure: Max Norm to account for the extent of modification across different feature scales, and L0 Norm to minimize the variety or number of features altered. This comprehensive cost model provides a more accurate representation of the adversarial effort required to implement an attack in the real world.
3. Adapted Tabular Perturbation and Projection: CaFA introduces TabPGD and TabCW, specialized adaptations of traditional PGD and Carlini & Wagner attacks for tabular data. These methods incorporate mechanisms to maintain structure constraints during perturbation and are combined with a SAT solver-based projection step to enforce the mined denial constraints, ensuring both evasiveness and feasibility.
4. Superior Feasible Success Rate at Lower Cost: Through extensive evaluation on diverse datasets (Adult, Bank, Fishing) and models (MLPs, TabNet), CaFA consistently demonstrated a significantly higher feasible success rate (at least 25% higher on MLPs) compared to existing state-of-the-art tabular attack methods. Crucially, it achieves this while simultaneously requiring the lowest combined attack cost (L0 and Max Norm), indicating more efficient and practical attacks.
5. Practical Implementability: The research includes a real-world evaluation on phishing webpages, demonstrating that CaFA can generate adversarial examples that successfully fool models with inconspicuous changes, something that prior methods like standard PGD failed to achieve or resulted in loss of evasiveness. This underscores CaFA's ability to produce attacks that are genuinely implementable in practical scenarios.

In essence, CaFA provides a robust and generic framework for whitebox robustness evaluation of tabular classifiers, producing adversarial examples that are both effective in inducing misclassification and realistic enough to be implemented in real-world scenarios.

Technical Deep Dive

▶ Watch: Modeling feasibility with structure and denial constraints (4:00)

CaFA's technical architecture is structured around a three-stage process: offline constraint mining, adversarial perturbation, and projection onto the space defined by the mined constraints. The overarching goal is to find a feature space modification (Δ) that induces misclassification, is feasible according to defined constraints, and requires minimal adversarial cost.

Constraint Modeling for Realizability

The framework models feature space integrity using two primary types of data integrity constraints:

1. Structure Constraints: These capture the inherent properties of individual features. They include the feature's data type (e.g., integer, float, categorical), its permissible range (e.g., age between 0 and 100), and other domain-specific properties. These are typically straightforward to extract from dataset schemas or metadata.
2. Denial Constraints (DCs): These are more expressive and crucial for modeling semantic dependencies between features. DCs are widely used in databases and are defined as a conjunction of predicates that cannot hold simultaneously for a pair of samples. For example, a DC might state that if employment_status is 'unemployed', then salary cannot be greater than zero.

• CaFA mines these DCs from the training set as soft constraints. This means that unlike rigid database rules, a small violation rate (e.g., 1%) is allowed during mining. This tolerance makes the mining process less sensitive to anomalous samples or noise within the training data, leading to a more robust set of constraints. The mining process utilizes an algorithm like Fast ADC and employs a ranking scheme based on established database metrics to discard low-performing constraints and ensure a good balance between completeness and soundness.

Problem Formalization and Cost Measure

The problem is formalized as finding a perturbation Δ such that:

• The perturbed sample x + Δ is misclassified by the target model.
• x + Δ is feasible, meaning it satisfies both the structure constraints and the mined denial constraints.
• The modification Δ requires minimal cost. CaFA employs a dual cost measure to approximate real-world adversarial effort:
• Max Norm (L∞): This norm accounts for the varying scales of different features, aiming to minimize the maximum extent of modification applied to any single feature. It reflects the idea of making small, inconspicuous changes across all relevant features.
• L0 Norm: This norm minimizes the number of features that are modified. It reflects the attacker's desire to alter as few attributes as possible, reducing the "variety" of required efforts.

CaFA's Three Stages

1. Offline Constraint Mining

This initial stage is performed once, independent of the attack execution. It involves:

• Extracting Structural Properties: Identifying feature types, permissible ranges, and other basic properties directly from the dataset.
• Mining Denial Constraints: Using an algorithm like Fast ADC to discover semantic dependencies. As mentioned, a 1% violation rate is permitted for soft constraints, and a ranking scheme ensures the quality of the mined DCs based on completeness and soundness metrics.

2. Perturbation (TabPGD and TabCW)

This stage generates an initial adversarial sample that satisfies structural and cost requirements, but may still violate cross-feature dependencies. CaFA adapts well-known adversarial attack techniques:

• TabPGD: This is a modification of the classic Projected Gradient Descent (PGD) tailored for tabular data. Key adaptations include:
• Trivial Step Size: Adjusting the gradient step size to be appropriate for tabular features, which often have discrete or limited value ranges.
• Maintaining Structure Constraints: During each iteration, the perturbed features are projected back into their permissible ranges and types (e.g., rounding to the nearest integer, clipping to min/max values).
• Standardized Maximum Perturbation: Limiting the extent of perturbation in a standardized manner across features with different scales.
• TabCW: This method extends the Carlini & Wagner (C&W) L0 attack to minimize the number of modified features. It operates by repeatedly running TabPGD, but in each run, it "freezes" the least essential features. The "essentiality" of features is determined by a modified heuristic designed to suit the heterogeneous nature of tabular samples, helping to achieve a lower L0 cost.

3. Projection (SAT Solver)

After the perturbation stage, the generated adversarial sample might still violate the more complex semantic dependencies captured by the denial constraints. The projection stage uses a Satisfiability (SAT) solver to enforce these DCs:

• Treating Sample as a Formula: The adversarial sample, along with the denial constraints, is translated into a logical formula.
• Relaxing Literals: To find a valid solution, some "literals" (features) within the sample are relaxed, meaning their values are temporarily made flexible.
• SAT Solver Application: A SAT solver is then used to find new values for these relaxed literals such that all denial constraints are satisfied.
• Minimizing Relaxed Literals: A crucial observation is that relaxing too many literals can inadvertently revert the misclassification achieved by the previous perturbation step. To counteract this, CaFA minimizes the number of relaxed literals. This is achieved through an iterative process involving a binary search guided by a heuristic, ensuring that the minimal number of features are adjusted to satisfy the DCs, thereby preserving the adversarial nature of the sample as much as possible.

Evaluation and Comparison

CaFA was evaluated on three diverse tabular datasets: Adult, Bank, and Fishing, targeting both Multi-Layer Perceptrons (MLPs) and TabNet models. It was compared against several prior methods:

• Valiance algorithm: A prior work specifically proposing relation constraints.
• PGD + SAT: Classic vision PGD followed by a SAT solver projection.
• CPG: Combines misclassification and continuous approximation of constraints into PGD's adversarial loss.
• MO2: Combines objectives within a genetic optimization algorithm.

The evaluation focused on two key aspects:

1. Constraint Quality: Measured by completeness and soundness, analogous to recall and precision. CaFA's automatically mined DCs demonstrated a superior balance compared to Valiance, indicating a higher quality set of constraints.
2. Feasible Success Rate vs. Attack Cost: CaFA consistently achieved the highest feasible success rate (meaning the adversarial sample both fools the model and is feasible according to constraints) while requiring the lowest combined cost (both L0 and Max Norm). On MLPs, CaFA showed at least a 25% higher feasible success rate than prior attacks, with similar trends observed for TabNet. Ablation studies further confirmed that CaFA efficiently utilizes the mined constraints, outperforming other methods even when provided with the same set of DCs.

This detailed technical approach ensures that CaFA not only generates effective adversarial examples but also does so in a way that respects the intricate structure and semantic relationships inherent in tabular data, making the attacks genuinely realizable and cost-aware.

Demo / Proof of Concept

▶ Watch: Constraint mining and TabPGD perturbation process (6:20)

While the talk did not feature a live, interactive demonstration in the traditional sense, the researchers presented a compelling problem-space perspective on CaFA's capabilities, serving as a powerful proof of concept for its real-world applicability. This involved attempting to implement evasion attacks on real-world phishing pages.

The process involved manually translating feature-space adversarial samples generated by different attack methods into actual HTML modifications on phishing websites. The goal was to assess the "implementability" of these adversarial examples at the problem space level.

The findings were stark:

• Standard PGD attacks consistently failed to provide implementable attacks. The nonsensical feature space perturbations generated by PGD could not be coherently translated into meaningful, functional changes on a webpage that would still resemble a legitimate phishing attempt.
• Projecting into a previously proposed constraint space (from prior work) often resulted in the complete loss of evasiveness for most samples. While these methods might enforce some basic constraints, they were insufficient to maintain the adversarial properties after projection, rendering the attack ineffective.
• CaFA, however, achieved significant success. The framework was able to generate adversarial examples that successfully fooled the model while requiring inconspicuous changes to the phishing website. Specifically, CaFA managed to fool the model with half of the website exhibiting these subtle yet effective modifications.

This real-world evaluation on phishing pages is crucial because it bridges the gap between theoretical adversarial examples and practical attack scenarios. It demonstrates that CaFA's emphasis on automatically mined database integrity constraints and its sophisticated perturbation/projection mechanism translate directly into adversarial examples that are not only mathematically sound but also semantically coherent and implementable in real-world applications. This practical validation underscores CaFA's potential as a valuable tool for assessing and improving the robustness of machine learning models deployed in sensitive, real-world contexts.

Defensive Implications

▶ Watch: Projecting adversarial samples using SMT solver (7:20)

The CaFA framework provides critical insights for defenders aiming to build more robust neural tabular classifiers. Its ability to generate realistic, cost-aware, and feasible adversarial examples highlights specific vulnerabilities that traditional robustness evaluations often miss.

Here are key defensive implications:

1. Robustness Evaluation with Feasible Attacks: Defenders should move beyond generic, vision-inspired adversarial attacks for tabular data. CaFA provides a blueprint for generating realizable adversarial examples that respect data integrity constraints. Using CaFA-like methods for whitebox robustness evaluation can reveal true vulnerabilities that an attacker could exploit in the real world, rather than just theoretical weaknesses. This allows for a more accurate assessment of a model's security posture.
2. Adversarial Training with Constraint-Aware Examples: The most direct defensive measure is to incorporate CaFA-generated adversarial examples into the model's training process. By adversarially training models on examples that are both misclassified and feasible (i.e., satisfying structural and denial constraints), models can learn to be robust against such realistic perturbations. This would involve generating a diverse set of CaFA examples and retraining or fine-tuning the model to correctly classify them.
3. Monitoring and Enforcement of Data Integrity Constraints: CaFA demonstrates the power of denial constraints (DCs) in defining feasible data. Defenders should consider implementing robust mechanisms to monitor and enforce these semantic dependencies in their data pipelines. If an input violates known DCs, it could be an indicator of a malicious or corrupted sample, even if it appears benign to a classifier that isn't robustly trained. This could involve pre-processing steps to validate inputs against a mined set of DCs.
4. Feature Engineering and Selection with Robustness in Mind: The process of mining DCs can reveal critical semantic relationships between features. This information can be used to inform more robust feature engineering strategies, potentially creating features that are less susceptible to manipulation without violating underlying data logic. It also highlights the importance of understanding the interdependencies between features, rather than treating them as independent entities.
5. Developing Robustness against Minimal Cost Attacks: CaFA's dual cost measure (Max Norm and L0) shows that attackers seek to minimize both the extent and variety of modifications. Defenders should aim to build models that are resilient to attacks requiring minimal changes, as these are the most practical for adversaries. This might involve exploring model architectures or regularization techniques that are inherently less sensitive to small, targeted perturbations of a few features.
6. Understanding the "Problem Space" Impact: The phishing page example underscores the importance of considering how feature-space changes translate into the problem space. Defenders should engage with domain experts to understand what constitutes a "feasible" and "inconspicuous" change in their specific application context and use this knowledge to inform their robustness efforts and attack simulations.

In summary, CaFA offers a sophisticated framework for understanding and generating realistic adversarial examples in the tabular domain. By adopting its principles, defenders can transition from theoretical robustness to practical security, building models that are genuinely resilient to the types of attacks an adversary would likely launch.

Key Takeaways

• Tabular Adversarial Attacks are Unique: Unlike vision, tabular data's discrete nature, specific ranges, and complex semantic dependencies make naive adversarial perturbations nonsensical and non-realizable.
• Feasibility is Paramount: CaFA addresses the critical gap of "realizability" by automatically mining and integrating data integrity constraints (structure and denial constraints) from databases, ensuring adversarial examples are semantically valid.
• Cost-Awareness for Practicality: The framework uses a dual cost measure (Max Norm and L0) to quantify attack effort, reflecting the real-world cost and inconspicuousness of an attack.
• CaFA Outperforms Prior Work: It achieves significantly higher feasible success rates (at least 25% higher on MLPs) at a lower combined cost compared to existing tabular attack methods.
• Specialized Techniques are Necessary: CaFA introduces TabPGD and TabCW for perturbation, combined with a SAT solver-based projection to enforce constraints, demonstrating the need for tailored approaches for tabular data.
• Real-World Applicability Demonstrated: The successful implementation of CaFA attacks on real-world phishing pages, leading to inconspicuous changes that fooled models, validates its practical utility and the realism of its generated adversarial examples.

About the Speaker(s)

The research behind CaFA was a collaborative effort involving Matan Ben-Tov, Daniel Deutch, Nave Frost, and Mahmood Sharif. While specific titles and affiliations beyond their names and the conference context are not provided in the transcript, their work presented at IEEE S&P indicates a strong background in machine learning security, data integrity, and adversarial machine learning research within academic or industrial research institutions. Matan Ben-Tov was the presenter for this talk. Their combined expertise in databases (for constraint mining) and machine learning (for neural networks and adversarial attacks) was crucial in developing CaFA's interdisciplinary approach.