Java 8은 HashMap에서 충돌 기반의 서비스 거부 공격을 완화하기 위해 트리화(treeification)를 도입했습니다. 기준점 8은 포아송 분포에서 로드 팩터가 0.75일 때 유래하며, 단일 버킷에 8개 이상의 요소가 포함될 확률은 약 0.00000606 (6 × 10⁻⁶)입니다. 이 통계적 희귀성은 연결 리스트에서 레드-블랙 트리로 변환되는 것이 O(log n) 조회 복잡성을 유지하기 위한 절대적인 필요성이 있을 때만 발생하도록 보장합니다.
구현은 메모리 효율성과 공격 저항성 간의 균형을 유지합니다. TreeNode 객체는 64비트 JVMs에서 압축된 OOPs를 사용하는 표준 Node의 32바이트에 비해 48바이트를 요구하며, 이는 주로 부모, 왼쪽, 오른쪽, 이전 노드에 대한 추가 레퍼런스와 색상 플래그 때문입니다. 이 기준점은 악의적인 충돌 동안 O(n) 탐색 비용이 트리 구조의 메모리 오버헤드를 초과하는 지점을 나타냅니다.
// HashMap.java에서 상수 정의 static final int TREEIFY_THRESHOLD = 8; static final int UNTREEIFY_THRESHOLD = 6; static final int MIN_TREEIFY_CAPACITY = 64;
트래픽이 많은 전자상거래 플랫폼은 플래시 세일 중 재앙적인 지연 스파이크를 경험했습니다. 조사 결과 공격자들이 동일한 hashCode() 값을 생성하도록 설계된 수천 개의 조작된 쿼리 매개변수를 포함한 HTTP 요청을 제출했다는 것이 밝혀졌습니다. 이로 인해 매개변수 구문 해석에 사용되는 HashMap 인스턴스가 링크드 리스트로 전환되어 O(n) 접근 시간이 발생했습니다.
// HashDoS 공격 시뮬레이션 Map<String, String> vulnerableMap = new HashMap<>(); for (int i = 0; i < 10000; i++) { // 동일한 해시 코드를 생성하는 조작된 키 vulnerableMap.put(createCollidingKey(i), "malicious_value"); } // 조회 시간: JDK 7에서는 O(n), JDK 8+에서는 O(log n)
여러 가지 수정 전략이 평가되었습니다.
웹 서버 수준에서의 요율 제한이 의심스러운 트래픽 패턴을 제한할 수 있다고 고려되었습니다. 그러나 이 접근 방식은 합법적인 플래시 세일 트래픽도 높은 요청 볼륨을 발생시켰기 때문에 효과가 없었으며, 수익이 가장 높은 기간 동안 유효한 고객을 차단할 가능성이 있었습니다.
매개변수 수를 100으로 제한하는 입력 검증이 해시 플러딩을 방지하기 위한 간단한 수정으로 제안되었습니다. 그러나 이 해결책은 복잡한 필터 매트릭스에 대한 지원을 요구하는 제품 관리자들에 의해 거부되었고, 보안 엔지니어들은 공격자가 50개의 신중하게 선택된 매개변수 내에서도 여전히 충돌을 발생시킬 수 있다고 언급했습니다.
ConcurrentHashMap으로의 마이그레이션이 충돌을 다르게 처리할 수 있다는 가정하에 잠시 고려되었습니다. 그러나 ConcurrentHashMap이 동일한 트리화 메커니즘을 사용하며 트리화 임계값 이하에서 공격을 받을 경우 비슷한 O(n) 저하가 발생할 것이라는 점에서 relief는 없었습니다.
엔지니어링 팀은 두 가지 전략을 선택했습니다. 그들은 플랫폼을 JDK 8로 업그레이드하여 충돌이 8을 초과할 경우 연결 리스트를 레드-블랙 트리로 변환하는 자동 트리화 메커니즘을 활용했습니다. 이를 통해 악의적인 입력에서도 선형 저하 대신 O(log n) 조회 성능이 보장되었습니다. 또한, 그들은 수신 요청의 해시 분포 엔트로피를 계산하고 의심스러운 충돌 패턴을 가진 요청을 맵 생성 이전에 거부하는 서블릿 필터를 구현했습니다.
배포 후 메트릭은 지속적인 공격 조건에서도 50ms 이하의 일관된 응답 시간을 보여주었습니다. CPU 사용률은 최대 트래픽 동안 40% 이하로 유지됐으며, 이전 구현이 공격 시작 몇 분 내에 모든 코어를 포화시켰던 것과는 대조적이었습니다. 이 플랫폼은 서비스 저하 없이 플래시 세일을 성공적으로 처리하였고, 외부 요율 제한보다 JVM의 내부 충돌 처리를 신뢰하는 아키텍처 결정을 검증했습니다.
임계값이 7 또는 8보다 6개 요소에서 연결 리스트로 다시 전환되는 이유는 무엇인가요?
UNTREEIFY_THRESHOLD인 6은 변동하는 작업 부하 동안 데이터 구조 간의 진동을 방지합니다. 제거 작업에 의해 트리가 7개 요소로 줄어들 경우, 즉시 다시 변환 비용을 피하기 위해 트리 구조를 유지합니다. 6개 요소의 경계는 히스테리시스를 제공하여 트리 구성 비용(새 TreeNode 객체 할당 및 재균형 포함)이 충분한 긴 기간에 걸쳐 분산되는 것을 보장합니다.
포아송 분포가 8이라는 숫자를 어떻게 정당화하나요?
기본 로드 팩터가 0.75인 경우, 각 버킷당 예상 요소 수는 포아송 분포를 따르며 λ는 0.5입니다. 확률 질량 함수는 P(0) = 0.6065, P(1) = 0.3033, P(2) = 0.0758로 지수적으로 감소합니다. 8개 요소에 도달할 확률은 0.5⁸/8! × e^(-0.5) ≈ 6.0 × 10⁻⁶입니다. 이는 백만 개 중 여섯 번의 기회를 나타내며, TreeNode 객체의 메모리 비용이 정상 작동 중 0.0006% 미만의 버킷에 영향을 미친다는 것입니다.
트리화된 버킷을 유지하는 데 드는 구체적인 메모리 오버헤드는 연결 리스트와 비교하여 얼마인가요?
표준 HashMap.Node는 32바이트를 소모합니다(객체 헤더, 해시 int, 키에 대한 참조, 값에 대한 참조, 다음에 대한 참조). TreeNode는 LinkedHashMap.Entry를 확장하며, 이는 Node를 확장하여 추가 필드(부모, 왼쪽, 오른쪽, 이전 및 불린 레드 플래그)를 상속합니다. 이로 인해 64비트 JVMs에서 압축된 OOPs를 사용하는 경우 각 항목당 48바이트가 소요되며, LinkedHashMap의 오버헤드도 포함됩니다. 정확히 8개 요소를 포함하는 버킷의 경우, 트리화된 구조는 약 384바이트가 필요하며, 연결 리스트의 경우 256바이트로, 이는 충돌의 드문 경우를 고려할 때 여전히 수용 가능한 50% 증가를 의미합니다.