IP Traceback 2002년 5월 22일 정지웅 2018-11-11

Overview Introduction Hash-based IP Traceback Route-Based Distributed Packet Filtering Summary 2018-11-11

Introduction Denial-of-Service (DoS) attack 이용 가능한 모든 세션을 점령하여 네트워킹 기능 마비 과부하를 일으켜 시스템 다운시킴 존재하지 않는 IP 주소로 접속하여 세션들을 마비시킴 기형적이고 이상한 패킷 구조를 보내어 정확한 프로세싱을 방해하는 행위 Distributed DoS (DDoS) attack 여러 대의 호스트에서 동시 공격 실례 2000년 2월, Yahoo, eBay, Amazon 수시간 동안 시스템 마비 2018-11-11

IP Traceback IP traceback 송신자 추적의 어려움 공격 경로와 패킷의 송신자 추적하여 attack graph를 재구성 송신자 추적의 어려움 Stateless한 인터넷의 특성 때문에, 위조된 주소를 사용하여 공격 가능 NAT, Mobile IP, IP tunneling… Attack은 short-lived하기 때문 2018-11-11

Related Works Ingress filtering Packet marking Logging Boarder gateway에서 패킷의 address가 spoof되었는가를 감시 라우터가 허가되지 않은 소스 어드레스로 부터 오는 패킷을 막는 것이다. 이것은 라우터가 합법적인 소스어드레스와 불법적인 소스어드레스를 구분할수 있는 충분한 파워를 가져야 가능하다 Ingress filtering은 이를 지원하는 라우터가 널리 깔려 있어야만 효과적임 Packet marking IP header에서 잘 사용하지 않는 field에 정보를 encoding Logging Router에서 forword된 packet을 기록 패킷을 주요 라우터에 로그해 놓아서 패킷이 경유하는 경로를 결정하는 것으로 공격이 끝난 후에도 추적이 가능 2018-11-11

Related Works ICMP traceback message 라우터에서 패킷을 샘플하여 이를 포워딩하고 카피하여 인접라우터 정보와 함께 ICMP 메시지로 audit information을 전송 공격중에 이 정보를 이용하여 추적 공격이 종료된 후에도 추적 가능 문제점: ICMP message를 지원하지 않는 라우터 attacker가 거짓 ICMP message를 보낼때 2018-11-11

Overview Introduction Hash-based IP Traceback Route-Based Distributed Packet Filtering Summary 2018-11-11

Drawback of Logging Packet이 네트워크를 경유해서 오면서 변형될 수 있기 때문에 attack path를 재구성하는데 어려움이 있다. 완전한 packet을 저장하는데 문제가 있다. Packet의 log가 많아지면서 attacker에게 노출될 위험이 있다. 2018-11-11

Hash-based IP Traceback SPIE (Source Path Isolation Engine) System 라우터에서 자신이 전달한 패킷 기록 패킷 요약 정보(invariant IP header + 8 bytes payload)에 Bloom Filter (n 개의 hash functions)를 적용한 결과를 저장 일정 시간마다 페이지를 넘김(각 페이지에는 시간, hash functions, filtering result 기록) 단 하나의 패킷에 의한 공격이라도 traceback 가능 그러나, 메모리의 제한으로 traceback 가능한 시간이 제한됨 2018-11-11

Hash Input Ver HLen TOS Total Length Identification Fragment Offset TTL Protocol Checksum 28 bytes Source Address Destination Address Options First 8 bytes of Payload Remainder of Payload 2018-11-11

Bloom Filter 2018-11-11

Transform Lookup Table 충분한 packet data가 SPIE에 의해서 transformation time에 기록되어야 하고, 그 결과 original packet이 재구성 될 수 있음 NAT, IP-in-IP tunneling, fragmentation 2018-11-11

Graph construction R R A R R R R7 R R4 R5 R6 R R3 R1 R2 V 2018-11-11

System Components DGA (Data Generation Agent) 각 라우터에 위치 해당 라우터를 거쳐간 패킷에 대한 digest table 유지 SCAR (SPIE Collection and Reduction Agent) Traceback 요청 시 DGA로 부터 digest table 수신하여, local traceback 수행 STM (SPIE Traceback Manager) 전 SPIE system 관장 타 system과 정보 교환 2018-11-11

Architecture 2018-11-11

Overview Introduction Hash-based IP Traceback Route-Based Distributed Packet Filtering Summary 2018-11-11

Probabilistic Packet Marking PPM marking하기 위해서 패킷 헤더를 사용함 각 라우터에서 local path information을 확률적으로 기록 많이 수신된 주소일수록 가까운 라우터로 간주 멀리 떨어져 있는 라우터의 경우 수신된 패킷의 개수 비교가 부정확 높은 확률을 가지고 attack path를 재구성 장점 Efficient and implementable 단점 공격자들이 많을 경우에 구분이 어려움(DDoS 추적 불가능) Marking field가 spoofing될 수 있음 2018-11-11

Route-Based Distributed Packet Filtering Routing 정보를 사용해서 Packet Filtering을 함 Distributed fitering Implement ingress filtering on AS 2018-11-11

Key objectives of DPF Maximize proactive filtering of spoofed packets. For bogus packets that get through, minimize number of sites that could have sent those packets. ( for IP traceback) Achieve the two objectives while minimizing the number of sites carrying out route-based filtering. Find the optimal sites where filtering are to be carried out. 2018-11-11

Modeling for DPF AS Connectivity Graph G(V,E) Node Type ( V = T ∪ U ) V: AS node의 집합 ( |V|=n ) E: G에 있는 link들의 집합 Node Type ( V = T ∪ U ) T: filtering node의 집합 incoming traffic 뿐만 아니라 internal traffic도 filtering U: filtering이 없는 node의 집합 Routing (R) R(u,v) ⊆￡(u,v) ￡(u,v) : set of all loop-free paths from u to v 2018-11-11

Modeling for DPF Routing Policies Route-based filter Tight: single shortest-path routing, |R(u,v)|=1 Multipath: multiple routing paths, 1 < |R(u,v)| < |￡(u,v)| Loose: any loop-free path routing, R(u,v) =￡(u,v) Route-based filter Maximal filter routing path들의 모든 pair( source, destination )를 사용 Semi-maximal filter filtering을 수행하기 위해 패킷의 source address만을 사용 2018-11-11

Filtering Effect Spoofing range Sa,t (attaker의 관점) node a에 있는 attacker가 node t 에 도달하기 위해서 spoofed source IP addreses로 사용될 수 있는 node의 집합 Candidate range Cs,t (victim의 관점) Filtering 되지 않고 spoofed IP packet M(s,t)을 보낼 수 있는 노드의 집합 2018-11-11

Filtering Effect No filtering : S1,9 = {0,1,2,3,4,5,6,7,8} Filtering at AS 8 : S1,9 = {0,1,2,3,4,5} Filtering at AS 8 and 3: S1,9 = {1,2} 2018-11-11

Metric for proactive Perfect proactivity Ddos prevention Φ1(1) :어떤 곳으로부터 spoofed packet이 도달 될 수 없는 AS 의 fraction Ddos prevention Φ2(1) : spoofed packet이 다른 AS의 target 에 보낼 수 없는 attack site의 fraction 2018-11-11

Metric for reactive IP Traceback Capability localization : meaningful for parameter τ≥1 localization Ψ1(5) : 5site 안에 attack location을 결정할 수 있는 AS의 fraction 2018-11-11

Vertex Cover(VC) VC of G(V,E) T=VC ∀(u,v) ∈ E, u ∈ VC or v ∈ VC filtering 이 없는 U의 node 는 neighbor로 오직 T node만 갖는다. 2018-11-11

Impractical perfect proactivity G: 1997년 Internet connectivity(n=3015,|E|=5230) T: VC->n R: Tight F: Semi-maximal Φ1(1)=1 is hard to achieve 2018-11-11

DDoS Attack Prevention G: 1997~1999 Internet conn. T: VC R: Tight F: semi-maximal DPF는 DDoS attack의 수행 능력을 효과적으로 감소 시켰음(Φ2(1)는 약 88%) 2018-11-11

IP Traceback Effect(reactive) Traceback capability 1997~1999 AS conn localization to within 5 sites 2018-11-11

Maximal vs semi-maxiamal filter Maximal filter는 quadratic space를 요구하지만 τ=5일 때 성능상 차이점이 없다. 2018-11-11

Multi-path Routing traceback capability의 점진적인 감소 routing path의 수가 2~3일 때 τ=5~10 에 대해서 Ψ1(τ)≒1 DPF는 multi-path routing에도 효과적임 2018-11-11

Summary Hash-Based IP Traceback memory 를 적게 사용 single packet 의 traceback이 가능 high-speed router 지원 Route-Based Distributed Packet Filtering routing 정보를 사용하여 packet filtering을 함. BGP에서 구현 될 수 있음 DoS 과 DDoS attack 을 prevention, protection Traceback capability 2018-11-11

References Alex C. Snoeren, Craig Patridge, Luis A. Sanchez, Christine E. Jones, “Hash-Based IP Traceback,” SIGCOMM’2001 Kihong Park, Heejo Lee,“On the Effectiveness of Route-Based Packet Filtering for Distributed DoS Attack Prevention in Power-Law Internets” , SIGCOMM’2001 Stefan Savage, David Wetherall, Anna Karlin, Tom Anderson, “Practical Network Support for IP Traceback,” SIGCOMM'2000 2018-11-11