[Sidrops] On validating AS paths

Iljitsch van Beijnum <iljitsch@muada.com> Wed, 26 June 2019 15:19 UTC

Return-Path: <iljitsch@muada.com>
X-Original-To: sidrops@ietfa.amsl.com
Delivered-To: sidrops@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 606181201A3 for <sidrops@ietfa.amsl.com>; Wed, 26 Jun 2019 08:19:48 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.7
X-Spam-Status: No, score=-2.7 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=muada.com header.b=PXJknEW/; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=j2ZCS6AG
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id 5SLnpAg0Evw3 for <sidrops@ietfa.amsl.com>; Wed, 26 Jun 2019 08:19:45 -0700 (PDT)
Received: from wout4-smtp.messagingengine.com (wout4-smtp.messagingengine.com []) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9CD0512006A for <sidrops@ietf.org>; Wed, 26 Jun 2019 08:19:45 -0700 (PDT)
Received: from compute2.internal (compute2.nyi.internal []) by mailout.west.internal (Postfix) with ESMTP id AD7FD53E for <sidrops@ietf.org>; Wed, 26 Jun 2019 11:19:44 -0400 (EDT)
Received: from mailfrontend1 ([]) by compute2.internal (MEProxy); Wed, 26 Jun 2019 11:19:44 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=muada.com; h= from:content-type:mime-version:subject:message-id:date:to; s= fm3; bh=8V4DgxlfjncehJiKuSbe1gi6lUwdBC4kjOKAKozRZiw=; b=PXJknEW/ 2xXWEJWgzQ/vb9+VUmAya+bk12hUWbKD+DvACHchuNpMsVlY5PqV/OWnOYr/C4Pq sJ05LAF48g6OjbHQ4OCc27BGSyUL1wwyoA8yPPgEZG91Du+d2nUlg5T5BjKz5OrH jaHEhI0bPtYjAbq0h7L4Y0ikgG+YCzCM30isl08uZhUyzr32zAR6pqOsm9IuqKHH CG485QYRZJG1U0Q8lblSmfHPbQCpM4jGeg+Eve8aLGDMbZmiNsKXoY+Ek4ojt7Az b324kc1X24ZGgIQMMrcWWTHs09CrML5PwxKQ9Bk+cQs4HwONHF4h1j7lpFQbeKC1 g8Sq5H3D7bhlVQ==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=content-type:date:from:message-id :mime-version:subject:to:x-me-proxy:x-me-proxy:x-me-sender :x-me-sender:x-sasl-enc; s=fm3; bh=8V4DgxlfjncehJiKuSbe1gi6lUwdB C4kjOKAKozRZiw=; b=j2ZCS6AGVnPGHPteDAbl5l1veQcY37cX+qsshR619Q4a8 IxIc1bjnC7E2gmg7RqyGdUFENadrRThNuMg7HGxtSsIOzt+B0DIZMTQx/uIwe6q8 pq2zPAcJB2xMQ5/75pjBeXAA+wJzeZxu4vmPq9h/ZNthmiNZZinuCh/Q24Qi8d6R 289m0urJCnsZjogEspZ+elSlBZUNdkYPpk7ln1bXQxjokwPrf6BdNYrOlL1RABaq K8tX0rXJgzzqea9NEeqqPjWpY/pyJGQoq2gjIrmBmSwF9F06zYiv8oSeDhKnKu/A bQUvZS/EcTIq1+2JJyaSR1jlS0CVJ4TqpuQT/TDXg==
X-ME-Sender: <xms:D40TXcceTIpysHTFSHd2xA5Op4qTMQPxfVHeKOWdsXqeGsVyus4IBg>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduvddrudeigdeklecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecunecujfgurhephfgtggfukfffvffosegrtdhmrehhtd dvnecuhfhrohhmpefklhhjihhtshgthhcuvhgrnhcuuegvihhjnhhumhcuoehilhhjihht shgthhesmhhurggurgdrtghomheqnecukfhppeekfedrkeehrdejuddrleehnecurfgrrh grmhepmhgrihhlfhhrohhmpehilhhjihhtshgthhesmhhurggurgdrtghomhenucevlhhu shhtvghrufhiiigvpedt
X-ME-Proxy: <xmx:D40TXTx-Qpds8iKN7d3nc_OyMsuY-RdwD38-mmJRdbUTIKT1xJVQuQ> <xmx:D40TXRakqvOhvxIrMkQxl_lXez5F1ZbYy2PGaysm_9EH6oR3zXUHPA> <xmx:D40TXZ91w1_d5VRQJ8MOfF3S5e_emBWFAnBTOE0sHg5aHb3AlytNVg> <xmx:EI0TXQWPi4LEuI0ScreI4TjkQ1VpML00f1gD4iigYNxhdsl_DJqnLA>
Received: from [] (83-85-71-95.cable.dynamic.v4.ziggo.nl []) by mail.messagingengine.com (Postfix) with ESMTPA id 3F06E8005C for <sidrops@ietf.org>; Wed, 26 Jun 2019 11:19:43 -0400 (EDT)
From: Iljitsch van Beijnum <iljitsch@muada.com>
Content-Type: multipart/alternative; boundary="Apple-Mail=_B4CC6D92-D118-4A1B-B950-FEB3E2C0E138"
Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.8\))
Message-Id: <9D1926FB-30B0-4A28-8AAF-32527BCC2F9F@muada.com>
Date: Wed, 26 Jun 2019 17:19:38 +0200
To: sidrops@ietf.org
X-Mailer: Apple Mail (2.3445.104.8)
Archived-At: <https://mailarchive.ietf.org/arch/msg/sidrops/1grgR1z7P7_XkiXjAnA7t6sbP1c>
Subject: [Sidrops] On validating AS paths
X-BeenThere: sidrops@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: A list for the SIDR Operations WG <sidrops.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/sidrops>, <mailto:sidrops-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/sidrops/>
List-Post: <mailto:sidrops@ietf.org>
List-Help: <mailto:sidrops-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/sidrops>, <mailto:sidrops-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 26 Jun 2019 15:19:48 -0000

(I hope the list retains my non-proportional font. Reformat if necessary.)

After an interesting discussion with Job Snijders the other day about our respective drafts, I think it would be helpful to analyze the issue of AS path validation further before discussion specific solutions.

I'm interested to hear if my assumptions and conclusions are shared.

I think we can agree that any AS path that doesn't conform to the valley-free model. A quick refresher: the valley-free model assumes four types of relationships between ASes:

customer-provider:  /
provider-customer:  \
peer-peer:          ^
sibling-sibling:    -

I've invented the / \ ^ - characters to indicate relationships myself, the idea being that they'll visually show valleys if a path isn't valley-free.

You can visualize valley-freeness as the customer ASes at the bottom sending many up the hierarchy, and the money will only flow up, not down. So if you have a "valley" in the relationships between the ASes in a path, someone isn't getting paid and the whole thing doesn't work economically.

The model also allows for mutual backup arrangements, where basically two ASes provide transit to each other (also called a sibling relationship). How that works financially is a bit murky, but the interesting thing here is that if nobody implements any policies or filters, you have a network with only sibling relationships.

So with these four relationships and the valley-free restriction we should be able model any working real-world relationship between two or more ASes.

(We'll ignore the possibility that the relationships between ASes may be different for different address families and/or prefixes for now.)

For a formal definition of the valley-free model, read "On inferring autonomous system relationships in the internet", Gao, 2001.

I'll state it in the form of the following AS path validation procedure.

In addition to / \ ^ - we'll also allow ? to indicate an unknown relationship between two adjacent ASes in the path. And we'll assume the sibling relationship between an AS and itself (i.e., if there is AS path prepending).

The steps:

1. Trim from the right (origin) side all \ and - relationships
2. Trim from the left side all / and - relationships
3. If the path is now empty or contains just one ^, the path is valley-free and therefore valid
6. If the path still contains / or \ or contains multiple ^, the path is invalid

Here are a few valid paths:

A: //\\ 
B: /^\
C: ^
D: ^\-\

So the steps produce:

            A       B       C       D
            //\\    /^\     ^       ^\-\
Step 1      //      /^      ^       ^
Step 2              ^       ^       ^
Step 3      valid   valid   valid   valid

If we look at RFC 7908, the first four types of route leaks are caused by the following relationships:

1: \/
2: ^^
3: ^/
4: \^

So the steps produce:

            Type 1  Type 2  Type 3  Type 4
            \/      ^^      ^/      \^
Step 1      \/      ^^      ^/      \^
Step 2      \/      ^^      ^/      \^
Step 3      \/      ^^      ^/      \^
Step 5      invalid invalid invalid invalid

Now what if we have unknown relationships in the path?

/?^\ could be:

//^\    /-^\    /^^\    /\^\
valid   valid   invalid invalid

/?\ could be:

//\     /-\     /^\     /\\
valid   valid   valid   valid

In other words: if steps 1 and 2 above just leave a ?, then regardless of what the unknown relationship turns out to be, we know the path will be valley-free and valid.

So we can now extend the validation steps to consider unknown relationships and see even if we assume a best case scenario, we still end up with an invalid path:

1. Trim from the right (origin) side all \ and - relationships
2. Trim from the left side all / and - relationships
3. If the path is now empty or contains just one ^ or just one ?, the path is valley-free and therefore valid
4. Trim from the right (origin) side all \, - and ? relationships
5. Trim from the left side all /, - and ? relationships
6. If the path still contains / or \ or contains multiple ^, the path is invalid
7. Else the path validity is unknown

Now all of the above assumes that the relationship between two ASes is uncontested. But what if the two ASes claim to have different relationships?

One approach would be to just assume an unknown relationship ?, so the path will only validate under worst case assumptions.

In my opinion, a better approach would be just keep track of claims of a customer-provider relationship from the customer side (where the sibling relationship is simply a mutual customer-provider relationship claim).

Overclaiming of the relationship by a customer is relatively unproblematic, because the claimed provider will simply not provide the service with no ill effect. Overclaiming by the provider, on the other hand, could be harmful, the combination of the relationship overclaim and incorrect BGP filters will now create a route leak that our path validation system will declare to have a valid path.

There is probably no reason to publish peer-to-peer relationships, as a path with ? where there should be ^ will also validate.

One interesting issue is route servers, as deployed by internet exchanges. Typically (universally?) those don't add their AS to the AS path, breaking the BGP specification in the process. In that case, the route server is invisible, so validation will have the same result as with a direct peering relationship.

If this behavior is not universal, we should either assume a - relationship for route servers, or define a new type of relationship that will be removed from the valley-free validation process.

With all of the above out of the way, we'll have to think about which relationship claims to carry in-band and which out-of-band.