기술 요약: 탄젠트 부공간 경계 공격 (Tangent Subspace Boundary Attack, TSBA)

문제 정의

본 논문은 공격자가 타겟 모델의 신뢰도 점수나 그래디언트에 접근할 수 없고, 오직 최종 예측 라벨에만 접근할 수 있는 환경인 **의사결정 기반 블랙박스 적대적 공격(decision-based black-box adversarial attacks)**의 과제를 다룹니다. 이러한 설정은 고차원 입력 공간(예: ImageNet)에서 매우 어려운데, 이는 그래디언트 정보의 부재로 인해 최소한의 섭동(perturbation)을 찾는 효율적인 입력 공간 탐색이 극도로 어렵기 때문입니다.

기존 방법론들은 다음과 같은 근본적인 한계를 가집니다:

• Boundary Attack: 고차원 무작위 샘플링과 거절(rejection) 방식에 의존하며, 이로 인해 쿼리 효율성이 떨어집니다.
• HopSkipJumpAttack (HSJA): 무작위 샘플링을 통해 그래디언트를 추정하여 효율성을 개선했지만, 높은 분산과 상당한 쿼리 오버헤드를 유발합니다.
• 일반적 한계: 기존의 접근 방식들은 **국소적 기하 구조(local geometric structure)**를 명시적으로 활용하지 못하는 경우가 많으며, 이는 불안정한 탐색, 섭동의 방사형 확장(radial expansion), 그리고 중복된 쿼리로 이어집니다.

방법론: 탄젠트 부공간 경계 공격 (TSBA)

저자들은 TSBA를 제안합니다. 이는 탐색 과정을 안정화하고 쿼리 분산을 줄이기 위해 기하학적 제약 조건을 명시적으로 포함하는 의사결정 기반 공격입니다. 핵심 철학은 **경계 근사와 방향 탐색을 분리(decouple)**하는 것입니다.

방법론은 세 가지 핵심 구성 요소로 이루어집니다:

1. 이진 탐색을 통한 경계 투영 (Boundary Projection via Binary Search)

무작위 보행(random walk)을 통해 섭동의 크기를 점진적으로 줄이는 대신, TSBA는 현재의 적대적 지점을 결정 경계 위로 명시적으로 투영합니다.

• 적대적 지점 $x_{adv}$와 원본 입력 $x_o$가 주어지면, 알고리즘은 이들 사이의 선분을 정의합니다.
• **이진 탐색(binary search)**을 수행하여 점 $(1-\lambda)x_o + \lambda x_{adv}$가 여전히 오분류되는 가장 작은 단계 크기 $\lambda$를 찾습니다.
• 이를 통해 결정 경계 위에 정확히 위치하는 투영된 지점 $x_b$를 얻으며, 이는 기존 방식에서 발견되는 불필요한 거리 감소 단계를 제거합니다.

2. 탄젠트 공간 제약 업데이트 (Tangent-Space Constrained Updates)

업데이트가 거리를 증가시키지 않으면서(방사형 확장 없이) 원본 이미지 쪽으로 이동하도록 하기 위해, TSBA는 **직교 제약 조건(orthogonality constraint)**을 부과합니다.

• 경계 지점 $x_b$에서 "소스 방향(source direction)"은 $v_k = x_b - x_o$로 정의됩니다.
• 임의의 후보 섭동 $\delta$는 $v_k$에 직교하는 **탄젠트 공간(tangent space)**으로 투영됩니다:
  $$\delta \leftarrow \delta - \frac{\langle \delta, v_k \rangle}{\|v_k\|^2} v_k$$
• 이론적 정당성: 본 논문은 이 직교 제약 조건 하에서 투영 후 원본 입력까지의 거리 $\|x_{b}^{k+1} - x_o\|$가 증가하지 않음을 증명합니다(Proposition 1). 이는 왜곡(distortion)의 국소적 단조 감소를 보장합니다.

3. 저차원 부공간 샘플링 (Low-Dimensional Subspace Sampling)

고차원 공간($d \gg 1$)에서의 샘플링 비효효율성을 해결하기 위해, TSBA는 섭동을 저차원 부공간으로 제한합니다.

• 기저(basis) $U \in \mathbb{R}^{d \times k}$ (여기서 $k \ll d$)가 사용됩니다.
• 섭동은 $\delta = Uz$ (단, $z \sim \mathcal{N}(0, I_k)$)로 샘플링됩니다.
• 이러한 구조적 샘플링은 전체 차원의 무작위 샘플링에 비해 효과적인 방향을 찾을 확률을 크게 높여줍니다.

알고리즘 흐름:

1. 이진 탐색을 통해 초기 적대적 예제를 경계로 투영합니다.
2. 저차원 부공간에서 섭동을 샘플링합니다.
3. 섭동을 탄젠트 공간(소스 방향에 직교하는 공간)으로 투영합니다.
4. 지점을 업데이트하고 이진 탐색을 통해 경계로 재투영합니다.
5. 수렴하거나 쿼리 예산이 소진될 때까지 반복합니다.

주요 기여

저자들은 다음과 같이 기여를 요약합니다:

1. 경계 투영 메커니즘: 결정 경계를 근사하는 효율적인 이진 탐색 방식을 제공하여, 기존의 무작위 보행 방식에 내재된 불필요한 단계를 제거했습니다.
2. 탄젠트 공간 업데이트 전략: 소스 방향에 대한 직교성을 강제하는 새로운 제약 조건을 통해 섭동 크기의 국소적 단조 감소를 이론적으로 보장합니다.
3. 구조적 부공간 샘플링: 고차원 공간에서의 탐색 효율성과 안정성을 향상시키기 위해 저차원 부공간 샘플링을 통합했습니다.
4. 실증적 검증: 최신 방법론들과 비교하여 우수한 쿼리 효율성과 경쟁력 있는 왜곡도를 입증하는 광범-한 실험을 수행했습니다.

실험 결과

ImageNet 데이터셋과 사전 학습된 ResNet-50 모델을 사용하여, TSBA를 Boundary Attack 및 **HopSkipJumpAttack (HSJA)**와 비교하는 실험을 진행했습니다.

쿼리 효율성 및 성공률

• 성공률: 500 쿼리 예산 하에서, TSBA는 **46%**의 성공률을 달성하여 HSJA(38%)와 Boundary Attack(28%)을 앞질렀습니다. 1500 쿼리에서는 TSBA가 **80%**에 도달한 반면, HSJA는 73%, Boundary Attack은 61%를 기록했습니다.
• 쿼리 비용: TSBA는 성공하는 데 필요한 중앙값(median) 쿼리 수가 현저히 적었습니다. 500 쿼리 예산 기준, TSBA는 중앙값 150 쿼리가 필요했던 반면, HS_JA는 210, Boundary Attack은 340이 필요했습니다.

쿼리-왜곡 트레이드오프 (Query-Distortion Trade-off)

• TSBA는 모든 쿼리 예산에 대해 일관되게 더 낮은 $\ell_2$ 왜곡도를 달성했습니다.
• 저쿼리 구간(<1000 쿼리)에서 TSBA는 최소한의 왜곡으로 결정 경계에 빠르게 접근하는 데 있어 상당한 우위를 보였습니다.

강건성 평가

TSBA는 방어된 모델(적대적 훈련된 PGD 및 Randomized Smoothing RS)을 대상으로 테스트되었습니다.

• RMSE 제약 조건($\le 0.1$) 하에서, TSBA는 강건한 모델들에 대해 **70-72%**의 성공률을 달성하여, Boundary Attack(35-48%) 및 HSJA(55-69%)를 크게 상회했습니다.
• 또한 강건한 모델에 대한 성공적인 공격을 달성하기 위해 TS-BA는 HSJA(5001 쿼리)나 Boundary Attack(2200+ 쿼리)보다 훨씬 적은 쿼리(약 1600-1700 쿼리)를 필요로 했습니다.

정성적 분석

섭동에 대한 시각적 분석 결과, TSBA는 넓은 이미지 영역에 걸친 고주파 노이즈를 생성하는 Boundary Attack과 달리, 의미론적으로 정보가 풍부한 영역(예: 물체의 경계)에 집중된 낮은 크기의 국소적 섭동을 생성함을 보여주었습니다.

절제 연구 (Ablation Study)

세 가지 핵심 구성 요소(경계 투영, 탄젠트 제약, 또는 부공간 샘플링) 중 하나라도 제거하면 성능이 저하되었습니다:

• 투영 미사용 시: 쿼리 수와 왜곡도가 증가했습니다.
• 탄젠트 제약 미사용 시: 안정성이 떨어지고 수렴 속도가 느려졌습니다.
• 부공간 미사용 시: 고차원 무작위 샘플링의 어려움으로 인해 쿼리 효율성이 크게 저하되었습니다.

의의 및 주장

본 논문은 기존의 의사결정 기반 공격이 비효효율적인 이유가 결정 경계의 국소적 기하 구조를 충분히 활용하지 못하기 때문이라고 주장합니다. 업데이트를 탄젠트 부공간으로 명시적으로 제한하고 경계 근사와 방향 탐색을 분리함으로써, TSBA는 다음과 같은 원칙적인 메커니즘을 제공합니다:

1. 섭동의 방사형 확장을 방지하여 탐색 과정을 안정화합니다.
2. 샘플링된 방향의 분산을 줄입니다.
3. 실제로 그래디언트를 추정하지 않고도 그래디언트 추정 방식에 필적하거나 그보다 나은 쿼리 효율성을 달성합니다.

저자들은 TSBA가 적대적 섭동이 저차원 탄젠트 구조 내에서 효과적으로 최적화될 수 있음을 보여준다고 결론짓습니다.

향후 연구로는 적응형 부공간 학습, 동적 단계 크기 제어, 비디오 및 3D 데이터로의 확장, 그리고 수렴 및 쿼리 복잡도에 대한 이론적 보증에 대한 조사가 제안되었습니다.