웹 보안 시니어 알고리즘 면접
새 면접Q. 대용량 사용자 인증 시스템에서 패스워드 해싱 알고리즘을 선택해야 합니다. bcrypt, scrypt, Argon2의 내부 동작 원리와 시간/메모리 복잡도를 비교하고, 초당 10만 건의 로그인 요청을 처리해야 하는 환경에서 어떤 알고리즘을 선택할지 그 이유와 함께 설명해주세요.
각 알고리즘의 cost factor와 병렬화 저항성, 그리고 하드웨어 공격에 대한 방어 메커니즘을 고려해보세요.
bcrypt는 Blowfish 기반으로 cost factor만큼 반복 연산을 수행하며 시간 복잡도는 O(2^cost)이지만 메모리 사용량이 적어 GPU 공격에 취약합니다. scrypt는 시간과 메모리를 모두 소비하도록 설계되어 O(N*r*p) 시간 복잡도와 O(N*r) 메모리 복잡도를 가지며 병렬화 공격에 강합니다. Argon2는 Argon2d(메모리 의존), Argon2i(사이드채널 공격 방어), Argon2id(하이브리드) 세 가지 변형이 있으며, 시간/메모리/병렬성을 독립적으로 조정 가능합니다. 초당 10만 건 처리 환경에서는 Argon2id를 선택하되, 메모리와 시간 파라미터를 적절히 낮춰 응답시간 100ms 이내로 유지하고, 캐싱과 세션 관리로 재인증 빈도를 줄이는 아키텍처를 병행해야 합니다. 추가로 레이트 리미팅과 계정 잠금 정책으로 brute-force 공격을 방어하는 다층 방어 전략이 필요합니다.
- • 각 해싱 알고리즘의 시간/메모리 복잡도 정확한 이해
- • 대용량 트래픽 환경에서 보안과 성능의 트레이드오프 분석
- • Argon2의 파라미터 튜닝과 다층 방어 전략 제시
대규모 사용자 인증 시스템에서 패스워드 해싱 알고리즘 선택과 파라미터 튜닝은 보안과 서비스 가용성을 동시에 결정합니다.
Argon2의 메모리 파라미터를 너무 높게 설정하면 어떤 보안 위험이 발생할 수 있나요?
Q. CSRF 토큰을 생성하는 안전한 알고리즘을 설계해야 합니다. 암호학적으로 안전한 난수 생성기(CSPRNG)를 사용한다고 가정할 때, 토큰 길이는 몇 비트가 적절하며, 그 이유를 충돌 확률과 엔트로피 관점에서 설명해주세요. 또한 토큰 생성 시간 복잡도와 저장 공간 복잡도는 어떻게 되나요?
생일 역설(Birthday Paradox)과 브루트포스 공격에 필요한 시도 횟수를 고려해보세요.
CSRF 토큰은 128비트 이상이 적절하며, 이는 2^64번의 시도로 50% 충돌 확률을 갖는 생일 공격을 방어하기 위함입니다. 128비트는 2^128의 경우의 수를 제공하여 충분한 엔트로피를 보장하며, 브루트포스 공격으로 특정 토큰을 맞출 확률은 사실상 0에 가깝습니다. CSPRNG를 사용한 토큰 생성의 시간 복잡도는 O(1)로 상수 시간이며, 저장 공간 복잡도는 사용자당 하나의 토큰을 저장하므로 O(n)입니다. 실무에서는 토큰에 타임스탬프나 세션 정보를 HMAC으로 서명하여 서버 측 저장 없이 검증 가능한 stateless 토큰을 구현할 수도 있으며, 이 경우 공간 복잡도를 O(1)로 줄일 수 있습니다.
- • 생일 역설을 고려한 적절한 토큰 길이 산정
- • 엔트로피와 충돌 확률의 수학적 근거 제시
- • stateless 토큰 구현을 통한 공간 복잡도 최적화 방안
CSRF 토큰 생성 알고리즘 설계는 세션 관리 시스템의 보안성과 확장성을 동시에 결정합니다.
HMAC 기반 stateless 토큰을 사용할 때 토큰 폐기(revocation)는 어떻게 구현할 수 있나요?
Q. API 레이트 리미팅을 구현하기 위해 Token Bucket, Leaky Bucket, Fixed Window, Sliding Window Log, Sliding Window Counter 알고리즘을 비교 분석해야 합니다. 각 알고리즘의 시간/공간 복잡도를 설명하고, DDoS 공격 시나리오에서 burst traffic 처리 능력과 메모리 효율성을 기준으로 가장 적합한 알고리즘을 추천해주세요.
각 알고리즘이 순간적인 트래픽 급증을 어떻게 처리하는지, 그리고 분산 환경에서의 구현 복잡도를 생각해보세요.
Token Bucket은 O(1) 시간, O(1) 공간으로 burst를 허용하며 토큰 수만 추적하면 되어 효율적입니다. Leaky Bucket은 O(1) 시간, O(n) 공간으로 큐에 요청을 저장하며 burst를 평탄화하지만 메모리 사용량이 큽니다. Fixed Window는 O(1) 시간/공간이지만 윈도우 경계에서 2배 요청을 허용하는 취약점이 있습니다. Sliding Window Log는 O(log n) 시간, O(n) 공간으로 정확하지만 각 요청 타임스탬프를 저장해 메모리 비효율적입니다. Sliding Window Counter는 O(1) 시간/공간으로 이전 윈도우와 현재 윈도우 카운터만 유지하며 근사치로 정확도와 효율성을 균형있게 제공합니다. DDoS 방어 시나리오에서는 Sliding Window Counter를 추천하며, Redis 같은 분산 캐시에서 INCR과 EXPIRE로 간단히 구현 가능하고, 메모리 효율적이면서도 윈도우 경계 취약점을 완화합니다.
- • 5가지 레이트 리미팅 알고리즘의 시간/공간 복잡도 정확한 분석
- • burst traffic 처리와 메모리 효율성의 트레이드오프 이해
- • 분산 환경 구현 가능성과 DDoS 방어 효과를 고려한 알고리즘 선택
대규모 API 서비스에서 레이트 리미팅 알고리즘 선택은 DDoS 방어 효과와 인프라 비용을 직접적으로 결정합니다.
분산 환경에서 여러 서버 간 레이트 리미팅 카운터를 동기화할 때 발생할 수 있는 race condition을 어떻게 해결하시겠습니까?
Q. WAF(Web Application Firewall)에서 SQL Injection 패턴을 탐지하기 위해 수천 개의 악성 패턴을 HTTP 요청 본문에서 검색해야 합니다. 단순 문자열 매칭, KMP, Boyer-Moore, Aho-Corasick 알고리즘의 시간 복잡도를 비교하고, 실시간으로 초당 10만 건의 요청을 처리해야 하는 환경에서 어떤 알고리즘을 선택해야 하는지 전처리 시간과 메모리 사용량을 포함해 설명해주세요.
다중 패턴 매칭과 단일 패턴 매칭의 차이, 그리고 패턴 수가 많을 때의 효율성을 고려해보세요.
단순 문자열 매칭은 O(n*m*p) 시간 복잡도로 텍스트 길이 n, 패턴 길이 m, 패턴 수 p에 대해 비효율적입니다. KMP는 O(n+m) 시간, O(m) 공간으로 단일 패턴에 효율적이나 다중 패턴에는 O(n*p)가 됩니다. Boyer-Moore는 평균 O(n/m)으로 빠르지만 역시 다중 패턴에는 비효율적입니다. Aho-Corasick은 O(n+m+z) 시간 복잡도로 모든 패턴을 한 번의 순회로 찾으며, 전처리는 O(m) 시간과 공간으로 Trie와 failure function을 구축합니다. 초당 10만 건 처리 환경에서는 Aho-Corasick이 최적이며, 수천 개 패턴을 Trie로 컴파일하여 각 요청을 단일 순회로 검사할 수 있습니다. 메모리는 패턴 총 길이에 비례하지만 한 번 구축 후 재사용되므로 효율적이며, 실무에서는 정규표현식 엔진과 결합하거나 DFA로 최적화하여 성능을 더욱 향상시킬 수 있습니다.
- • 다중 패턴 검색에서 Aho-Corasick의 우수성 이해
- • 전처리 비용과 검색 시간의 트레이드오프 분석
- • 대용량 트래픽 환경에서 실시간 패턴 매칭 최적화 전략
WAF와 IDS 시스템에서 다중 패턴 매칭 알고리즘은 실시간 위협 탐지의 성능을 결정하는 핵심 요소입니다.
패턴이 동적으로 추가되거나 삭제되는 환경에서는 Aho-Corasick Trie를 어떻게 효율적으로 업데이트할 수 있나요?
Q. 세션 관리 시스템에서 세션 ID를 키로 사용하는 해시 테이블을 설계합니다. 충돌 해결 방법으로 Chaining과 Open Addressing(Linear Probing, Quadratic Probing, Double Hashing)을 비교하고, 각각의 평균/최악 시간 복잡도를 설명해주세요. 또한 로드 팩터가 0.7을 초과할 때 rehashing 전략과 그 시간 복잡도는 어떻게 되나요?
클러스터링 현상과 캐시 지역성, 그리고 rehashing 시 서비스 중단을 최소화하는 방법을 고려해보세요.
Chaining은 평균 O(1+α) 시간 복잡도(α는 로드 팩터)이며 최악의 경우 O(n)으로 모든 키가 한 체인에 몰릴 수 있지만, 로드 팩터가 1을 초과해도 동작하고 삭제 연산이 간단합니다. Linear Probing은 평균 O(1/(1-α))로 캐시 지역성이 좋지만 primary clustering으로 최악 O(n)이 될 수 있습니다. Quadratic Probing은 clustering을 완화하지만 secondary clustering이 발생하고, Double Hashing은 두 해시 함수를 사용해 clustering을 최소화하며 평균 O(1/(1-α))입니다. 로드 팩터 0.7 초과 시 테이블 크기를 2배로 늘리고 모든 항목을 재해싱하는데 O(n) 시간이 소요되며, 실무에서는 incremental rehashing이나 두 개의 테이블을 유지하며 점진적으로 이동시키는 방법으로 서비스 중단을 방지합니다. 세션 관리에서는 Chaining이 삭제가 빈번하고 로드 팩터 예측이 어려운 환경에 적합합니다.
- • 충돌 해결 방법별 시간 복잡도와 clustering 현상 이해
- • 로드 팩터에 따른 성능 변화와 rehashing 전략
- • 실무에서 서비스 중단 없는 incremental rehashing 구현
대규모 세션 관리 시스템에서 해시 테이블 설계는 조회 성능과 메모리 효율성을 직접적으로 결정합니다.
분산 환경에서 여러 서버에 세션을 분산 저장할 때 Consistent Hashing을 사용하는 이유와 그 시간 복잡도는 무엇인가요?
Q. 권한 관리 시스템에서 사용자-역할-권한이 계층적 그래프 구조로 연결되어 있습니다. 특정 사용자가 특정 리소스에 접근 권한이 있는지 확인하려면 그래프 순회가 필요합니다. DFS, BFS, 그리고 경로 압축을 사용한 Union-Find 알고리즘의 시간/공간 복잡도를 비교하고, 권한 체크가 초당 수만 번 발생하는 환경에서 최적화 전략을 제시해주세요.
권한 그래프의 특성(DAG, 순환 가능성)과 캐싱, 그리고 전처리를 통한 최적화를 생각해보세요.
DFS와 BFS는 모두 O(V+E) 시간, O(V) 공간 복잡도를 가지며, DFS는 스택 오버플로우 위험이 있고 BFS는 최단 경로를 찾습니다. Union-Find는 경로 압축과 랭크 기반 합치기로 거의 O(α(n)) 상수 시간에 연결성을 확인하지만, 동적 그래프 변경이 어렵고 DAG의 방향성을 표현하기 어렵습니다. 권한 체크가 빈번한 환경에서는 전처리로 Transitive Closure를 계산하여 O(V³) 시간에 Floyd-Warshall로 모든 도달 가능성을 비트맵으로 저장하면 조회는 O(1)이 됩니다. 실무에서는 권한 결과를 Redis에 캐싱하고 TTL을 설정하며, 권한 변경 시 관련 캐시를 무효화하는 하이브리드 전략이 효과적입니다. 또한 RBAC 그래프를 레벨별로 분리하여 depth를 제한하고, Bloom Filter로 확실히 없는 경우를 빠르게 거르는 최적화도 가능합니다.
- • 그래프 순회 알고리즘의 시간/공간 복잡도 정확한 비교
- • Transitive Closure 전처리를 통한 조회 시간 O(1) 최적화
- • 캐싱과 Bloom Filter를 활용한 실무 최적화 전략
대규모 엔터프라이즈 권한 관리 시스템에서 그래프 순회 최적화는 API 응답 시간과 시스템 확장성을 결정합니다.
권한 그래프에 순환이 있을 수 있는 경우 무한 루프를 방지하면서 권한을 체크하려면 어떻게 해야 하나요?
Q. 보안 이벤트 로그를 심각도와 타임스탬프 기준으로 정렬하여 처리하는 시스템을 설계합니다. Quick Sort, Merge Sort, Heap Sort의 시간/공간 복잡도를 비교하고, 실시간으로 새로운 이벤트가 계속 추가되는 스트리밍 환경에서는 어떤 자료구조와 알고리즘을 사용해야 하는지 설명해주세요. 또한 상위 K개의 심각한 이벤트만 추출하는 경우 시간 복잡도는 어떻게 되나요?
정적 정렬과 동적 삽입의 차이, 그리고 부분 정렬이 필요한 경우의 최적화를 고려해보세요.
Quick Sort는 평균 O(n log n), 최악 O(n²) 시간에 O(log n) 공간이지만 불안정 정렬이고, Merge Sort는 O(n log n) 보장에 O(n) 공간으로 안정 정렬이며, Heap Sort는 O(n log n) 시간에 O(1) 공간이지만 캐시 비효율적입니다. 스트리밍 환경에서는 Min-Heap이나 Max-Heap을 사용하여 O(log n) 시간에 삽입하고 O(1)에 최대/최소를 조회할 수 있습니다. 상위 K개만 필요한 경우 크기 K의 Min-Heap을 유지하며 새 이벤트를 O(log K) 시간에 삽입하고, 전체 n개 처리 시 O(n log K) 시간 복잡도로 O(n log n) 전체 정렬보다 효율적입니다. 실무에서는 Priority Queue로 구현하고, 심각도별로 여러 큐를 분리하거나, Kafka 같은 메시지 큐와 결합하여 백프레셔를 관리하며, 배치 처리로 I/O 오버헤드를 줄입니다.
- • 정렬 알고리즘별 시간/공간 복잡도와 안정성 비교
- • 스트리밍 환경에서 Heap 기반 우선순위 큐의 효율성
- • Top-K 문제에서 부분 정렬을 통한 시간 복잡도 최적화
SIEM 시스템에서 실시간 보안 이벤트 우선순위 처리는 중요한 위협을 신속하게 탐지하고 대응하는 데 필수적입니다.
분산 환경에서 여러 서버의 로그를 병합하여 전역적으로 정렬된 상위 K개를 추출하려면 어떤 알고리즘을 사용해야 하나요?
아직 댓글이 없습니다. 첫 번째 댓글을 남겨보세요!