Ye et al. (2024): Feature Reconstruction Attacks and Countermeasures in VFL

Feature Reconstruction Attacks and Countermeasures of DNN Training in Vertical Federated Learning

Paper: Ye P., Jiang Z., Wang W., Li B., Li B. — IEEE TDSC, 2024
Focus: Feature security in VFL when training DNNs

---

1. What is Vertical Federated Learning (VFL)?

   Party A (Active)         Party B (Passive)
   ┌─────────────────┐      ┌─────────────────┐
   │ Features xA     │      │ Features xB     │
   │ Labels y        │      │ No labels       │
   │ Top model θ     │      │ Bottom model WB │
   └────────┬────────┘      └────────┬────────┘
            │                        │
            │    zB = WB · xB        │
            │◄───────────────────────┘
            │
            ▼
       z = WA·xA + zB
       Final prediction

Key Characteristics:

• Column-wise split: Each party holds different features (columns) of the same samples
• Active party: Has labels, coordinates training, holds top of the model
• Passive party: Has features only, sends intermediate results to active party

---

2. Threat Model

Aspect	Description
Adversary	Active party (honest-but-curious)
Goal	Reconstruct passive party’s input features xB
View	Own data (xA, y), local weights (WA, θ), intermediate results (zB = WB·xB)
Constraint	No knowledge of passive party’s weights WB

---

3. Core Theoretical Result — Impossibility Theorem

Theorem 1: With zero knowledge, feature reconstruction is impossible.

Why? For any intermediate result zB, there exist infinitely many pairs (WB, xB) that produce the same output:

• If U is any unitary matrix: WB·U⊤ and U·xB produce the same zB
• The active party cannot distinguish between these possibilities

Critical Implication: Attack only becomes possible when the attacker knows constraints on the features (e.g., binary/discrete values).

---

4. Binary Feature Attack

4.1 Why Binary Features are Vulnerable

If the attacker knows some features are binary ({0,1}):

• The search space becomes finite (2^n instead of infinite)
• Binary vectors in the column space of ZB correspond to actual features

4.2 Attack Algorithm 1: Solving Linear Equations

## Core idea: Find binary vectors in column space of ZB
1. Extract dB × dB full-rank submatrix Z'
2. For each x' in {0,1}^dB \ {0}:
    w = Z'^(-1) · x'
    x = Z · w
    if x is binary:
        Found a feature!

Complexity: O(2^dB) — exponential in feature dimension

4.3 Attack Algorithm 2: Robust Version (Linear Regression)

Handles noise/perturbations using Leverage Score Sampling:

• Samples r rows to reduce enumeration from 2^n to 2
• Solves least squares instead of exact linear equations
• r = O(dB log dB / ε²) theoretically, but r = dB + 1 works in practice

4.4 NP-Hardness

Theorem 2: Finding binary vectors in a matrix column span is NP-hard (reduces from Exact Cover problem)

Despite this, the attack is practical because:

• dB is typically small (≤ 20 features)
• 2^dB is tractable for most real datasets

---

5. Why Simple Defenses Fail

Gaussian Noise Defense

σ (noise level)	Attack Accuracy	Model Accuracy
0	100%	High
0.1	~70-90%	Moderate drop
0.5+	~60%	Significant drop

Problem: Even with noise, attack accuracy remains high while model performance degrades.

BlindFL (Privacy-Preserving Framework)

The paper shows their attack still works against BlindFL because the aggregated sum of intermediate results is still exposed.

---

6. Masquerade Defense

6.1 Core Idea

Inject fake binary features that mislead the attacker:

              ┌─────────────┐
   xB ──────► │ Transform Q │──┐
              └─────────────┘  │   ┌───────────────┐
                               ├──►│ zB = [P|u]... │──► To Party A
   Random a ──────────────────►┘   └───────────────┘
  (fabricated)

6.2 How It Works

1. Introduce matrices P and Q
2. For each sample, generate random binary value(s) {a1, …, am}
3. Attacker finds fabricated features instead of real ones
4. Set m = ⌈log₂(n)⌉ to prevent adaptive attacks

6.3 Effectiveness

Metric	Without Defense	With Masquerade
Attack Accuracy	100%	~50% (random)
Model Accuracy	Baseline	~Same (negligible drop)
Training Time	Baseline	+2-14% overhead

---

7. Experiments

Datasets Used

Dataset	Samples	Passive Features	Binary Features
Bank	41,188	8	1 (contact)
Credit	30,000	10	1 (gender)
Nursery	12,960	6	1 (financial)
Covertype	581,012	10	4 (one-hot)
COVID	5,434	12	12 (symptoms)
Monkey-pox	25,000	8	8 (symptoms)

Results Summary

• Algorithm 1: 100% reconstruction without noise
• Algorithm 2: 60-95% reconstruction with Gaussian noise
• Masquerade: Reduces attack to ~50% (random guessing)

---

8. Practical Takeaways

For Attackers (Understanding Threats)

1. Binary/discrete features in VFL are highly vulnerable
2. Even with noise, reconstruction is feasible
3. Attack works in multi-party settings too
4. One-hot encoded features can be fully recovered

For Defenders (Protecting Data)

1. Simple noise is insufficient
2. Masquerade defense is effective with minimal overhead
3. Use m = log₂(n) fabricated features minimum
4. Cutting at deeper layers (not input layer) prevents these attacks

Limitations

• Attack only works when cut layer is the input layer
• If cut at layer 2+, non-linear activations break the linear algebra basis
• Feature dimension dB must be tractable (practical limit ~20-30)

---

9. Key Equations to Remember

Concept	Equation
Intermediate result	zB = WB · xB
Aggregation	z = WA·xA + WB·xB
Attack objective	Find binary x in col-span(ZB)
Defense condition	m ≥ log₂(n) fabricated features

---

10. Questions for Further Investigation

1. How do other attack types (gradient inversion, model inversion) compare?
2. Are there defenses that don’t require modifying the training process?
3. What about attacks on continuous features with known distributions?
4. How does differential privacy compare to masquerade defense?