Re: [Sidrops] ASPA verification algorithm error

"Sriram, Kotikalapudi (Fed)" <kotikalapudi.sriram@nist.gov> Tue, 23 February 2021 17:53 UTC

Return-Path: <kotikalapudi.sriram@nist.gov>
X-Original-To: sidrops@ietfa.amsl.com
Delivered-To: sidrops@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id D931D3A0CB8 for <sidrops@ietfa.amsl.com>; Tue, 23 Feb 2021 09:53:38 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.672
X-Spam-Level:
X-Spam-Status: No, score=-2.672 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.57, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FROM_GOV_DKIM_AU=-0.001, RCVD_IN_MSPIKE_H2=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=nist.gov
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id OzD6BQX-pZrN for <sidrops@ietfa.amsl.com>; Tue, 23 Feb 2021 09:53:33 -0800 (PST)
Received: from GCC02-DM3-obe.outbound.protection.outlook.com (mail-dm3gcc02on2117.outbound.protection.outlook.com [40.107.91.117]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id DB8AA3A0CB5 for <sidrops@ietf.org>; Tue, 23 Feb 2021 09:53:31 -0800 (PST)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=A3lxWvQfhO5HlcliqHgSf4OwTSKWQUClyQ1Hk8BGZaeeK7RDODY/15ZIj8nOw5hJ5CQmQ9is1cP0WBDB5b4YwG4c6cFqLSZjRp9A6eYErMeHA1gQhw6Po9qdzkMpePLxTpSyl19UfZrVdbU46q15+v6Cv4oI5xuNwwuttxazEZobk95rIWLegmPfrftS3J0omI3UZTLmIZtwxXxPAq/Hdodh+hYHMv3/JQ5aEOXpy6tdi7A6UYClu6c/08gNpWG9R0m/KKVywbXkG6blnW2TR4ujXu3y+dSCrV9fF8HZijc4zcbNT0gYdoAb1cLaT4+xaPZI4owbERR0vNQRm1eCMA==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=P22lTHAB2T5Trm6v7pz2Qj9fTqgtdoBaAbzEI6ix+YI=; b=acXsNN75UwPklq2nZ7DHM9lyF1RuT3u8eXUSlRJ4El7nX5cmcWaFdSmChWUmaYvhEVLcTVonzobrQJUe/yIkyHZUmM8szVxO4TqW9QIrCubfjUPGl9qpqiC1OqyHR4SjVidaXDS75CDGMWAvu10x7HAvDQQLTOTSVKBWI6gBwU5oB/lIhu/5NNQ7j57HtixWFmL/KEmprpQXEfxAIFpex1jwad/gLMh6l0v9jQaRNcRk1z8OpemrOAvoojbDJf6OMX7/I+EEZrrKyNiQssau0NyIzAbAb6CroCjBhmrQa35kYGUnPmVXtvAm53O9ELeTfipmH9hmbGRtclaVKi/usA==
ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=nist.gov; dmarc=pass action=none header.from=nist.gov; dkim=pass header.d=nist.gov; arc=none
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=nist.gov; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=P22lTHAB2T5Trm6v7pz2Qj9fTqgtdoBaAbzEI6ix+YI=; b=wafyQPduYNPlwXODRKvhdcbAZyrI6DfeQYAuFm5aaFzcSFNVYgb6ltKSfgqTSWp9rXTsvw5fCC4i3pCUzk4CC2ApvTsWUlKH8SOib+BPAeriSfdOu1RVuPL498DeEHITSr3W3/qG3nNjERj1OXygAMDH8oiJoLLnO6MU13Ectqk=
Received: from SA9PR09MB4814.namprd09.prod.outlook.com (2603:10b6:806:43::15) by SA9PR09MB5613.namprd09.prod.outlook.com (2603:10b6:806:4a::16) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3868.28; Tue, 23 Feb 2021 17:53:29 +0000
Received: from SA9PR09MB4814.namprd09.prod.outlook.com ([fe80::2482:8839:8d2c:a1f9]) by SA9PR09MB4814.namprd09.prod.outlook.com ([fe80::2482:8839:8d2c:a1f9%7]) with mapi id 15.20.3868.034; Tue, 23 Feb 2021 17:53:29 +0000
From: "Sriram, Kotikalapudi (Fed)" <kotikalapudi.sriram@nist.gov>
To: "a.e.azimov@gmail.com" <a.e.azimov@gmail.com>
CC: "Jakob Heitz (jheitz)" <jheitz@cisco.com>, "sidrops@ietf.org" <sidrops@ietf.org>
Thread-Topic: [Sidrops] ASPA verification algorithm error
Thread-Index: AQHXCgj8acxr8GVk4E2tpnq7a+huzQ==
Date: Tue, 23 Feb 2021 17:53:28 +0000
Message-ID: <SA9PR09MB4814CAE0E801B1FC6296EFD384809@SA9PR09MB4814.namprd09.prod.outlook.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
authentication-results: gmail.com; dkim=none (message not signed) header.d=none;gmail.com; dmarc=none action=none header.from=nist.gov;
x-originating-ip: [129.6.220.132]
x-ms-publictraffictype: Email
x-ms-office365-filtering-ht: Tenant
x-ms-office365-filtering-correlation-id: 972d1aff-17ef-450c-d3cf-08d8d823ed61
x-ms-traffictypediagnostic: SA9PR09MB5613:
x-ms-exchange-transport-forked: True
x-microsoft-antispam-prvs: <SA9PR09MB5613424CDB4ACA6FC822B02A84809@SA9PR09MB5613.namprd09.prod.outlook.com>
x-ms-oob-tlc-oobclassifiers: OLM:10000;
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: yHmwaHRhPi50rIdd9XDXRhwPLrUVchyy76VXvxQLE6IKpXHOIjxpXxyJU3hdhlwZYklQ6eMlbw5yBQ58z1uG1udlUYHznzIFw5L+DitFWg0POFRb5aHgNCwLyowrJZC3TIO9F6M+clG/RAri2ns40TMG2OOONHOQRSfJQd401OSGZ1lEMSa68WqgRVV0kDpBojRZOq6sKnL0/Y+88i3A9VMig68Sl2T+wFACp5CXwyCuL0R2ppquUySDdo34rkMWctoUq/7LYR2ulLbkzMMCnGTOoGBJi8rk63mkZpF15X4orDEjWKss8JR9+qMTX4OMELWu3Cw3HxnFmey5Yp+b2f48eJkdiO5Qf4P0KVSF+e2mGcttaZ66OtYU5Zjp2yinZMdTPJn+MON1gQAWSs+jnGPcS53+P284sObLpo+B8aaucFgqyEYZXLGCx5bfnJScER7nyiRi89VqLWigTVJ6vQD+hyNd98Zn/UQUoOaEPzYuiUrd5cpd662DX+C/iCPmiQyq48ENF5hX/r29kUavlw==
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:SA9PR09MB4814.namprd09.prod.outlook.com; PTR:; CAT:NONE; SFS:(4636009)(366004)(52536014)(7696005)(8936002)(76116006)(66476007)(64756008)(66556008)(66446008)(66946007)(6916009)(498600001)(54906003)(33656002)(5660300002)(66616009)(9686003)(86362001)(91956017)(186003)(26005)(71200400001)(99936003)(8676002)(55016002)(2906002)(6506007)(83380400001)(4326008); DIR:OUT; SFP:1102;
x-ms-exchange-antispam-messagedata: =?Windows-1252?Q?Yo7DmjJh/saNzl+cnULrBp1ybooZK0/ggxcZB3LLKWsNV6z/oyMChAXq?= =?Windows-1252?Q?vF5wSPGPY84uYSRJyX9KOsQ0uhBfjZrGKbodHo8r8EAyMBk1gLel02xu?= =?Windows-1252?Q?H2LwQp6Gx+BwVVBad66A7/VSQO9E8RBtWr2esR5qCEZvYbXpEVUzZyCS?= =?Windows-1252?Q?vt0QLaxp3QHLE9e3Y0zziz0OAuehNILfPAqI8HmsBdIS449uA4OBgJeQ?= =?Windows-1252?Q?IKQyD1Pmj/qHSs40sE/jeszZuWhlwVKmH3zUWWRCbetj92n+XsiqnzYw?= =?Windows-1252?Q?VM1GBAWdfZN/KSJS3HiQQKyQLSegF6N7cygq5e9UcEQ9lxgsieX4ChFi?= =?Windows-1252?Q?vneK/BhJBZwnOabllj43NtdbwuAcbap1cGWKlwEdLEu8mCVo/vxjraPa?= =?Windows-1252?Q?PZFB5LLd5PJFhJswWfbwkCOKrJxIhDda/iCcNDCwIkJBZTV6kPc439Lg?= =?Windows-1252?Q?x9AWjieUNsHY0Mx+hFHfiUOSvm0ilFcCj65j2TCeUmdLQqnskv4/9suV?= =?Windows-1252?Q?VTPvES/vmAHrZmQFkqwKWe5pBn4a4wvys6l5sjzs4zRQBxspsnP88vyB?= =?Windows-1252?Q?STgC1iDjyGbwih+PbNrkgc43Nk7V8G3HwNxI6qrY2K3bDMf3U5NSSGGe?= =?Windows-1252?Q?eAz1d+wKZQzx6No6eDaB97Iq4HrwUB5dyk3ZaOnJSXoMzGSO2jFNIPry?= =?Windows-1252?Q?NA43lnmppCIvGY7bgUcHcDeFBBENDdUi8uwHCAFhvdhgZX/gs1XguKcW?= =?Windows-1252?Q?+lr+chf3Fy7IUAB+0YYXOYQbmfIxThcFT9zeNTSt8yAViTaDjeJd/uyS?= =?Windows-1252?Q?/1Jix3rixWJLQyetX/KQbUGNkTrvpnn2YO9ykMUiY+Bssm51Cl50OTia?= =?Windows-1252?Q?lrmrV5CrMHpG/Yt2340Asvhz3LYSciDkGgWeuiHEnCtugKWklPyjRer7?= =?Windows-1252?Q?GfZQZDOsYOkQpvk55T/HvO4XKduMmuyAsl+ezGPVKlp6WePN62hbpXAj?= =?Windows-1252?Q?zDAAiUpdaUrsytMq12s17V6GIEjCQMnBqmfNVeH4WaabDeBqzoYokHsn?= =?Windows-1252?Q?vnxTFBVqe6qu6Inzb6EXTlDwarXPCsRE3mldMtdUgphhv1zghrBRUp+e?= =?Windows-1252?Q?Lyfecbzk8v4WscXPWmwJJGaO84QhxCf35ZxJv2l2qQMEaFieta0tiwLe?= =?Windows-1252?Q?CnYZZATosRXo1gnbzFkFPDz2iSd07nn+eFNHsfVqP8nRYZHh8ZoK3KMQ?= =?Windows-1252?Q?PCTfedLSym2NMURODuttCIZizvUMTs1FqxDvHWCG5EOXfEb2l4gKyem3?= =?Windows-1252?Q?lfPrrLi+XOoLPz4ROdV4PbLiD1K53kkUWEgbjtPmi8rN5AjiXBFEM2yi?= =?Windows-1252?Q?i+kt4lfJLLo/WovDQitqxByBaer0MKdr1Wk=3D?=
Content-Type: multipart/mixed; boundary="_002_SA9PR09MB4814CAE0E801B1FC6296EFD384809SA9PR09MB4814namp_"
MIME-Version: 1.0
X-OriginatorOrg: nist.gov
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: SA9PR09MB4814.namprd09.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 972d1aff-17ef-450c-d3cf-08d8d823ed61
X-MS-Exchange-CrossTenant-originalarrivaltime: 23 Feb 2021 17:53:29.0165 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 2ab5d82f-d8fa-4797-a93e-054655c61dec
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: DKt8kM9JsH6cgRJleiZEpjf6C9/gJJ6fTplbWgDU5ryQQ27v7hWWKnvtwxGHGiZH75JIjLHQVoL4NzmQer+aPQ==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SA9PR09MB5613
Archived-At: <https://mailarchive.ietf.org/arch/msg/sidrops/uH7FRLoswH_hew3jfHKtj-Hhkpo>
Subject: Re: [Sidrops] ASPA verification algorithm error
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: Tue, 23 Feb 2021 17:53:39 -0000

Alexander and all,

I think the error that Jakob has pointed out should be fixed. He and I have discussed possible solutions. Building on insights from him and with additional observations, the downstream AS path validation algorithm described below is worth considering. Formally provable that it works correctly to classify Valid, Invalid, and Unknown. It also seems efficient and without side effects.

[Jakob and I have put together a set of slides – a pdf is attached here. The slides have figures and a more detailed description along with an implementation procedure.] 

Proposed downstream AS path validation algorithm for route leak detection:

The downstream AS path of length N (N > 1) can be represented (without loss of generality) as follows (these are unique AS numbers after the prepends are collapsed):

AS(1), AS(2), .…, AS(K-1), AS(K), AS(K+1), .…, AS(L-1), AS(L), AS(L+1), .…, AS(N-1), AS(N)

[please take help from figures in slides 4, 5 and 6 to follow along; see attached pdf]

where K is defined as follows: there is an up-ramp of K ASes on the left such that each of the ASes AS(1) through AS(K-1) attests in its ASPA that the next AS in the path is its provider. And L is defined as follows: there is a down-ramp of N-L ASes on the right such that each of the ASes AS(L) through AS(N-1) are attested to be a provider by the next AS in the path. The up-ramp ends at AS(K) and down-ramp begins at AS(L). 

Definition of g(AS(i), AS(j)): 
For simplicity in writing, the following AS hop-validity function is defined: g(AS(i), AS(j)) = Valid if the ASPA of AS(i) lists AS(j) as a provider. Else, g(AS(i), AS(j)) = Invalid if the ASPA of AS(i) does not list AS(j) as a provider. Else, g(AS(i), AS(j)) = Unknown if ASPA of AS(i) is absent. It is well understood that ASPAs are AFI dependent, so AFI is not explicitly shown in function g.    

So, for the AS path as represented above: 

g(AS(i), AS(i+1)) = Valid for i = 1,2, …, K-1 
g(AS(i+1), AS(i)) = Valid for i = L, L+2, …, N-1

Note: L=K is possible when the AS path is shaped like an inverted V. Also, K=1 when there is no up-ramp, and L=N when there is no down-ramp.

Further, when L > K, g(AS(K), AS(K+1)) = Unknown or Invalid; hence the up-ramp stops at K;

and g(AS(L), AS(L-1)) = Unknown or Invalid; hence the down-ramp starts at L. 

[Examples/figures: Please see slides 4-6.]  

Now the core part of the algorithm is presented. It relies on the following theorems which are intuitive and provable (see slides 4-8, 12-14).

Theorem 1: The downstream AS path is “Valid” if L-K = 0 or 1. If L-K > 1, then the AS path can be “Unknown” or “Invalid”, but never “Valid”.  

Theorem 2: For L-K > 1, the validity of the whole AS path is the same as that of the partial path AS(K), AS(K+1), .…, AS(L-1), AS(L). The partial path can only be either Invalid or Unknown. It is Invalid if there exist u and v (u and v in the range from K to L-1) such that u < v and g(AS(u), AS(u+1)) = Invalid and g(AS(v+1), AS(v)) = Invalid. Otherwise, the partial path is Unknown. 

Now, the core algorithm is nearly obvious and works as follows:

---- begin algorithm ------

The AS path is Valid if L-K = 0 or 1 and the procedure halts. 

(Note: For  L-K > 1, to determine whether the AS path is Invalid or Unknown, we only need to focus on the portion of the path from AS(K) to AS(L).)

Consider the partial path represented by AS(K), AS(K+1), …,  AS(L-1), AS(L).

For  L-K > 1, if there exist u and v in the range from K to L-1 such that u < v and

g(AS(u), A(u+1)) = Invalid, and
 
g(AS(v+1), A(v)) = Invalid,

then the AS path is Invalid and the procedure halts.

Else, the AS path is Unknown.

------------ end of algorithm --------------

[Please see examples in the slides to see how the algorithm works]

Slide 10 provides a detailed implementation procedure.

Comments welcome.
     
Thank you.

Sriram