selective blackholing: implementation, usage & effectiveness

Job Snijders job.snijders at hibernianetworks.com
Mon Feb 10 20:33:21 UTC 2014


Dear fellow networkers,

Through this tutorial-styled email I'd like to introduce the concept,
usage and implementation of "selective blackholing" through the BGP
protocol to the community. This email contains some python code, example
router configurations references to RIPE Atlas data to demonstrate
effectiveness.

Selective Blackholing is a DDoS damage control mechanism which is
(compared to scrubbing or conventional blackholing) cheaper and more
effective from the perspective of both the Service Provider and the
End-User.

In today's internet DDoS attacks are common-place, and the balance is
not particularly fair: very expensive on the receiver-side and very
cheap for the evil-doer (think DNS-, NTP- and SNMP-amplification
attacks). I propose a method which is effective for businesses with a
scoped radius of interaction with their customers. 

To elaborate on what 'scoped' (read: selective) means: a Dutch
herring-shop owner will see most legitimate visitors come from within
the Netherlands; a Dallas, TX based Automotive Bulletin Board will see
most conversions from visitor to part-buyer come from visitors within
the United States. 

If we look at today's DDoS mitigation solutions (scrubbers: expensive
hardware or subscription services, or BGP blackhole: all or nothing
reachability)... it seems intuitive that a lot of business-owners would
care more about traffic from visitors in the surrounding 1000 kilometers
(or from the same country), than say (for the duration of the attack)
traffic sourced from other continents.

In this document we sequentially number any line of router config or
python code, to allow for easy references.

Let's focus on the implementation following four features:

 * discard traffic sourced outside 'this' country               (5580:664)
 * discard traffic sourced outside 'this' continent             (5580:660)
 * discard traffic sourced outside a 1000 km radius from 'here' (5580:663)
 * discard traffic sourced outside a 2500 km radius from 'here' (5580:662)

The 'this' and 'here' designators refer to the point of interconnection
with any given customer: 'this' and 'here' for a customer connecting to
AS5580 in Amsterdam, would respectable be "Netherlands, Europe, 'most of
West Europe', 'most of West + Central Europe'". It is important to
understand that all proposed mechanisms are designed to perform
uniformly in terms of intended usage regardless of location of
interconnection, so for a Dutch customer 5580:664 means 'discard any
traffic for my prefix received on PEs outside the Netherlands' but
for an Dallas, TX based customer BGP community '5580:663' would mean
'discard traffic destined to my prefix on routers located outside a 1000
km radius around Dallas'.

The 1000 km and 2500 km distances referenced throughout this document
mean the distance between AS 5580 network devices as calculated with a
haversine formula with the GPS coordinates of devices as input. The
haversine formula is an equation giving great-circle distances between
two points on a sphere from their longitudes and latitudes. Actual
length of datapath or optical paths is not taken into consideration, nor
is a peering partner's home country a factor.

To create the above described features we need a simplistic CMDB
database, some python code, static inbound iBGP route-map and
semi-dynamic customer facing inbound route-map. For illustration
purposes we assume a fictional ISP with a POP in the following cities:
Tokyo, San Jose, Dallas, New York, London, Amsterdam and Stockholm. 

+-----------+-----------+----------+-------+---------------------+
|   router  | continent | country  | metro | latitude, longitude |
|    name   |    id     | ISO31661 |  id   |                     |
+-----------+-----------+----------+-------+---------------------+
| r1.tky.jp |     3     |   392    |  46   | 35.65671, 139.80342 |
| r1.sjo.us |     1     |   840    |  29   | 37.44569,-122.16111 |
| r1.dal.us |     1     |   840    |  33   | 32.80096, -96.81962 |
| r1.nyc.us |     1     |   840    |  26   | 40.71780, -74.00885 |
| r1.lon.uk |     2     |   276    |  23   | 51.51173,  -0.00197 |
| r1.ams.nl |     2     |   528    |  20   | 52.35600,   4.95068 |
| r1.sto.se |     2     |   752    |  22   | 59.36264,  17.95560 |
+-----------+-----------+----------+-------+---------------------+
                     Table 1. Simplistic CMDB

Based on the above CMDB table we can construct the following device
specific configuration snippets. Within these snippets we adhere to the
concept that edge devices are smart and core devices dumb. At the edge
of the network we accept BGP Communities from customers, which we
translate through a process of testing & branching from 'something the
customer understands' to 'something the network understands'. 

r1.tky.jp:
001.  ip community-list THIS:METRO     seq 5 permit 65123:30046
002.  ip community-list THIS:COUNTRY   seq 5 permit 65123:392
003.  ip community-list THIS:CONTINENT seq 5 permit 65123:3000

r1.sjo.us:
004.  ip community-list THIS:METRO     seq 5 permit 65123:10029
005.  ip community-list THIS:COUNTRY   seq 5 permit 65123:840
006.  ip community-list THIS:CONTINENT seq 5 permit 65123:1000

r1.dal.us:
007.  ip community-list THIS:METRO     seq 5 permit 65123:10033
008.  ip community-list THIS:COUNTRY   seq 5 permit 65123:840
009.  ip community-list THIS:CONTINENT seq 5 permit 65123:1000

r1.nyc.us:
010.  ip community-list THIS:METRO     seq 5 permit 65123:10026
011.  ip community-list THIS:COUNTRY   seq 5 permit 65123:840
012.  ip community-list THIS:CONTINENT seq 5 permit 65123:1000

r1.lon.uk:
013.  ip community-list THIS:METRO     seq 5 permit 65123:20023
014.  ip community-list THIS:COUNTRY   seq 5 permit 65123:276
015.  ip community-list THIS:CONTINENT seq 5 permit 65123:2000

r1.ams.nl:
016.  ip community-list THIS:METRO     seq 5 permit 65123:20020
017.  ip community-list THIS:COUNTRY   seq 5 permit 65123:528
018.  ip community-list THIS:CONTINENT seq 5 permit 65123:2000

r1.sto.us:
019.  ip community-list THIS:METRO     seq 5 permit 65123:20022
020.  ip community-list THIS:COUNTRY   seq 5 permit 65123:725
021.  ip community-list THIS:CONTINENT seq 5 permit 65123:2000

all devices (common references for more humane route-map definitions):
022.  ! communities which are exposed in public documentation for customers
023.  ip community-list OUTSIDE:THIS:CONTINENT:DISCARD seq 5 permit 5580:660
024.  ip community-list OUTSIDE:2500KM:RADIUS:DISCARD  seq 5 permit 5580:662
025.  ip community-list OUTSIDE:1000KM:RADIUS:DISCARD  seq 5 permit 5580:663
026.  ip community-list OUTSIDE:THIS:COUNTRY:DISCARD   seq 5 permit 5580:664
027.  ip community-list GLOBAL:BLACKHOLE               seq 5 permit 5580:666
028.  ip community-list SCOPED:ACTION                  seq 5 permit 5580:660 
029.  ip community-list SCOPED:ACTION                  seq 5 permit 5580:662
030.  ip community-list SCOPED:ACTION                  seq 5 permit 5580:663
031.  ip community-list SCOPED:ACTION                  seq 5 permit 5580:664
032.  ip route 10.0.0.1/32 null0

all devices (static inbound iBGP route-map):
033.  route-map RX:iBGP permit 100
034.    match community  GLOBAL:BLACKHOLE
035.    continue 1100
036.  route-map RX:iBGP permit 100
037.    match community  OUTSIDE:THIS:COUNTRY:DISCARD OUTSIDE:THIS:CONTINENT:DISCARD 
038.    continue 1100
039.  route-map RX:iBGP permit 110
040.    match community  OUTSIDE:1000KM:RADIUS:DISCARD OUTSIDE:2500KM:RADIUS:DISCARD
041.    continue 1100
042.  route-map RX:iBGP permit 1000
043   route-map RX:iBGP permit 1100
044.    match community  THIS:METRO THIS:COUNTRY THIS:CONTINENT
045.  route-map RX:iBGP permit 1101
046.    set community  no-export additive
047.    set ip next-hop 10.0.0.1
048.    set local-preference 1000000

The above route-map allows BGP speakers in our routing domain to apply
different actions depending on the (geographically significant)
communities. Let's use three example input and run them through the
route-map to illustrate what happens:

    evaluation takes place on: router r1.lon.uk
    input: communities: none
    result: prefix accepted without modifications
    why: The first match is 'permit 1000' at line 042, because there is
    no match statement all prefixes will be accepted and the route-map
    is not evaulated any further. 

    evaluation takes place on: router r1.lon.uk
    input: communities: "5580:662 65123:10033 65123:10029"
        (for example when a customer attached to r1.sjo.us sets
        "5580:662 - discard outside 2500km")
    result: traffic for the prefix will be discarded
    why: The prefix matches with the clause 110 (line 039) because
    5580:662 matches OUTSIDE:2500KM:RADIUS:DISCARD (line 040). Because a
    match is found on line 041 we jump to line 043 for further matching.
    Because the community string cannot match any of the communities on
    line 044 (in the case of r1.lon.uk 65123:20023 OR 65123:276 OR
    65123:2000), the prefix is further evaluated at line 045. There is
    no match statement in the 'permit 1101' clause so for any prefix
    that arrives at this particular clause in the route-map the next-hop
    will be 10.0.0.1 (discard). Because the prefix matches with clause
    1101 the route-map will not be evaluated any further. 

    evaluation takes place on: router r1.dal.us
    input: communities: "5580:662 65123:10033 65123:10029"
        (for example when a customer attached to r1.sjo.us sets 
        "5580:662 - discard outside 2500km")
    result: prefix will be accepted with no further modifications
    why: The prefix matches with the clause 110 (line 039) because
    5580:662 matches OUTSIDE:2500KM:RADIUS:DISCARD (line 040). Because a
    match is found, the continue statement (line 041) is followed and we
    jump to line 043 for further matching. Because the community string
    matches one of the communities on line 044 (in the case of r1.dal.us
    65123:10033 OR 65123:840 OR 65123:1000), further evaluation of the
    route-map is halted, and the clause which actually makes it a
    blackhole is never reached. 

The attentive reader will now probably think "How come you are inputting
"5580:662 65123:10033 65123:10029", and not just 5580:662?! You promised
simple end-user configuration, no customer will want to invest time to
figure out magic values such as 65123:10033 65123:10029!

Now we get down the the secret sauce: extensive community rewriting.... 

Based on our CMDB database, we can calculate sets of magic values that
will cause the network to behave according to the desired feature. I've
made a sample python program available that will do these calculations.
This is the output:

049.  Eleanor:~ job$ wget -q http://noc.as5580.net/~job/example_community_calculator.py
050.  Eleanor:~ job$ python example_community_calculator.py
051.  r1.lon.uk - rewrite targets:
052.  1000 km: 65123:20020 65123:276
053.  2500 km: 65123:2000
054.
055.  r1.dal.us - rewrite targets:
056.  1000 km: 65123:10033
057.  2500 km: 65123:840
058.
059.  r1.sjo.us - rewrite targets:
060.  1000 km: 65123:10029
061.  2500 km: 65123:10033 65123:10029
062.
063.  r1.nyc.us - rewrite targets:
064.  1000 km: 65123:10026
065.  2500 km: 65123:10026 65123:10033
066.
067.  r1.tky.jp - rewrite targets:
068.  1000 km: 65123:30046
069.  2500 km: 65123:30046
070.
071.  r1.sto.se - rewrite targets:
072.  1000 km: 65123:20022
073.  2500 km: 65123:2000
074.
075.  r1.ams.nl - rewrite targets:
076.  1000 km: 65123:20020 65123:276
077.  2500 km: 65123:2000
078.  Eleanor:~ job$

Now we can use the above to create the route-map for a customer
connected to r1.sjo.us (San Jose, US):

079.  ip prefix-list 15562:PREFIX seq 5 permit 194.33.96.0/24
080.  ip prefix-list 15562:PREFIX:BLACKHOLE seq 5 permit 194.33.96.0/24 le 32

081.  route-map IMPORT:FROM:15562:CUSTOMER:IPv4 permit 200
082.    match ip address prefix-list 15562:PREFIX:BLACKHOLE
083.    match community GLOBAL:BLACKHOLE
084.    set community  5580:26220 no-export additive
085.    set ip next-hop 10.0.0.1
086.    set local-preference 1000000
087.  route-map IMPORT:15562:CUSTOMER:IPv4 permit 300
088.    match ip address prefix-list 15562:PREFIX:BLACKHOLE
089.    match community SCOPED:ACTION
090.    set community  5580:26220 no-export additive
091.    set local-preference 650
092.    continue 600
093.  route-map IMPORT:15562:CUSTOMER:IPv4 permit 400
094.    match ip address prefix-list 15562:PREFIX
095.    set community  5580:26220 additive
096.    set local-preference 650
097.  route-map IMPORT:15562:CUSTOMER:IPv4 deny 500
098.  route-map IMPORT:15562:CUSTOMER:IPv4 permit 600
099.    match community  OUTSIDE:1000KM:RADIUS:DISCARD
100.    set community  65123:10029 additive
101.    continue 1200
102.  route-map IMPORT:15562:CUSTOMER:IPv4 permit 700
103.    match community  OUTSIDE:2500KM:RADIUS:DISCARD
104.    set community  65123:10033 65123:10029 additive
105.    continue 1200
106.  route-map IMPORT:15562:CUSTOMER:IPv4 permit 900
107.    match community  OUTSIDE:THIS:COUNTRY:DISCARD
108.    set community  65123:840 additive
109.    continue 1200
110.  route-map IMPORT:15562:CUSTOMER:IPv4 permit 1100
111.    match community  OUTSIDE:THIS:CONTINENT:DISCARD
112.    set community  65123:1000 additive
113.  route-map IMPORT:15562:CUSTOMER:IPv4 permit 1200

Various rewrites need to happen to offer the four scoped features we
promised at the beginning of the document, the rewrites come either
directly from the CMDB (line 108 and 112) or from the python program
(line 100 and 104). Any network that wants to implement this should run
software such as the python program every time a new POP is added, and
update all IMPORT route-maps on all devices accordingly. 

Lines 081 to 113 bring us back to the second two examples where I
illustrated what happens with various community strings if they are
parsed through the RX:iBGP route-map. The customer in San Jose just sets
5580:662 (matched at line 102), but the IMPORT route-map will rewrite
that to "5580:662 65123:10033 65123:10029" (line 104). Et voila, we
have accomplished selective blackholing based on distance. :-)

I ran some measurements with the RIPE Atlas system to test which probes
can reach a given prefixes when a selective blackhole community is
attached, the results are available here:
    
    http://noc.as5580.net/~job/selective_blackholing/

Disclaimer: Seeming route-map inefficiencies might be more related to
the particular vendor on which I implemented this rather than my logic
capabilities. If this document contains any errors, they most likely
originated in the process of converting real world configuration to
something of educational value. :-)

I'd like to thank Saku Ytti Torsten Blum and Peter van Dijk for their
gracious inspiration. If not for free and unhindered dialogue between
organisations, we would never be able to create mechanisms like these.

If you have any questions, please approach me through email or in person
at NANOG60 in Atlanta!

Kind regards,

Job



More information about the NANOG mailing list