Subject: [sidr] NotFound vs Uninitialized

From: Andrew Chi <[email-masked]>
Date: Wed, 13 Mar 2013 10:19:40 -0400

Yesterday, Ruediger talked about a 4th validation state for BGP routes 
(RFC 6811 gives only 3).  After thinking about it more, I believe it may 
be helpful to call this validation state "Uninitialized".  Here's why.

First, for the purposes of this discussion, we assume that the 
validating cache has a "complete" snapshot of the global RPKI.  The 
definition of "complete" must be tuned via the validator settings 
according to local policy, but that's a separate conversation.

I believe Ruediger is talking about the actual variable *in the router* 
that stores validation state.  Currently, in the router, the three 
prescribed validation states for a BGP route are (RFC 6811):

    o  NotFound: No VRP Covers the Route Prefix.

    o  Valid: At least one VRP Matches the Route Prefix.

    o  Invalid: At least one VRP Covers the Route Prefix, but no VRP
       Matches it.

There's a hidden assumption in this trichotomy: that the snapshot has 
been completely transferred to the router (via the rpki-rtr), and all 
related processing is complete.  "NotFound" really means "I have 
searched the complete set of VRPs, and no VRP Covers the route prefix." 
  Similarly, "Invalid" really means "I have searched the complete set of 
VRPs, and at least one VRP Covers the route prefix, but no VRP Matches it."

During startup, however, it's important to for a validation state 
variable to start in a 4th state ("Uninitialized").  "Uninitialized" 
says "I haven't finished receiving/processing all the VRPs yet".  This 
is different from "NotFound".  In fact, filters would potentially treat 
this "Uninitialized" state differently from "NotFound".

In some sense this is just an implementation issue, but it is something 
that an implementer could easily get wrong.  You probably DON'T want 
your variables to start out in the "NotFound" state.

Andrew

---

From: Andrew Chi <[email-masked]>
Date: Wed, 13 Mar 2013 11:51:22 -0400

> be helpful to call this validation state "Uninitialized".  Here's why.

After talking to Doug and Sriram, it sounds like others already had this 
discussion and used the term "Undefined."  That's probably a better 
word, since one might need it for more than just startup conditions.

So do we explicitly call out this state and give it a label, or just 
leave it up to implementers and local policy?  Given that there are 
already several implementations, perhaps there's already a conclusion to 
this?

---

From: Andrew Chi <[email-masked]>
Date: Wed, 13 Mar 2013 13:28:48 -0400

After talking to Doug and Sriram, it sounds like others already had this 
discussion using the term "Undefined."  That's probably a better word, 
since one might need it for more than just startup conditions.

Should we explicitly call out this state?  Did we already decide not to?

---

From: Jay Borkenhagen <[email-masked]>
Date: Wed, 13 Mar 2013 15:02:44 -0400

> Should we explicitly call out this state?  Did we already decide not to?

Hi,

Not commenting for now on the need for a new term or the choices
offered, but I did want to point out that junos has a "4th" state now: 

Per
http://www.ripe.net/lir-services/resource-management/certification/router-configuration: 

===============

Note: There is an additional state in JunOS called “unverified”, which
indicates prefixes that haven’t been policed. This means there may be
a BGP neighbour session that doesn’t have an import policy
route-validation applied. You can verify this with the following
command:

junos.rpki.example.net> show route protocol bgp validation-state unverified

===============

We can hash out whether another standard state is required, but I
wanted to urge that in the end we arrive at a set of states with names
that have clear and unambiguous meanings.

Thanks.

							Jay B.

---

From: "Borchert, Oliver" <[email-masked]>
Date: Wed, 13 Mar 2013 21:16:01 -0400

>Should we explicitly call out this state?  Did we already decide not to?

As you correctly state Doug and Sriram, we do allow the validation state
"undefined" in our implementations BGP-Srx and QuaggaSRx. This is for the
timeframe where no information regarding the particular prefix/origin is
known or during its calculation. In our implementation for instance we
out-sorced the internal validation process into its own API - checking the
prefix-origin against the output of the validation cache outside of the
router. During this timeframe (which is a very short timeframe for origin
validation - but longer for path validation) we provide the state
"undefined" to allow the router to continue processing the update until
the final validation result is available and handed back to the router. We
added policies that can specifically deal with this situation which allows
us for instance to ignore the update until a calculated result (one of the
three specified ones) is available. But IMHO this is an implementation
specific solution and others might do it differently.

The main problem, as far as I understood it after talking to Ruediger
yesterday, is the timeframe in which the router fetches new information.
In other words the timeframe between "Serial Query" and "End of Data" -
RFC 6810. During this time new ROAS will be introduced or removed from the
router. If during this time the router reacts to each change individually
without waiting for the "big picture" of this particular
fetch/synchronization, the following problem can arise:

In case a route with a x/24 prefix has the validation result of "NotFound"
and a new ROA is introduced with a lesser specific prefix and insufficient
max length or even another ASN, this route will automatically change its
state from "NotFound" to "Invalid". If on top of this the prefix in
question belongs to the route that is selected, a withdrawal of this route
occurs.
Now an additional ROA is introduced that contains the exact x/24 prefix
including the same ASN, the route's validation state switches from
"Invalid" to "Valid" and the route will be re-selected. If the router
would have waited with its processing of the new information until all new
information are added to the system, the route never would have been
switched to "Invalid". In contrary, it would have switched right away from
"NotFound" to "Valid" without passing "Invalid" and therefore no change in
path selection would have occurred.

For this I see two solutions:
(A) The validation cache MUST send the deltas ordered from more specific
to less specific prefixes.
(B) The router does not process the new information until "End of Data"

Thinking further about (A) it would only solve the problem of a ROA
specifying the lesser specific prefixes that would invalidate the more
specific prefix but not the problem of a "same" specific prefix with a
different ASN. Here the temporary switch to "Invalid" will occur.
This leaves us with only solution (B) that requires the router to wait
until the cache update is performed (receiving "End of Data"), before
using the new information "snapshot". But to not having to wait with
calculating validation results until the update is performed, the old
"snapshot" should be used.

But this problem will not be resolved by adding a fourth state
"undefined". It is more a Best Practice kind of thing which the
implementer MUST be aware of.

Going back to the missing state "undefined", I think this is an
implementation dependent solution that actually only exists during the
time until either a validation state is calculated or during a power up or
until the FIRST "End of Data" is received from the validation cache - I
would not call it uninitialized because it also includes the time between
validation request and validation result as described earlier. This time
is short but not to neglectable, especially during table dumps.

Said that I firmly believe the state "undefined" should be added for
clarity and allowing a defined asynchronous processing of update
validation without delays of regular update-processing due to the fact of
a synchronization between router and cache. But again this could also be
only seen as too much implementation dependent.

Maybe one more information to our implementation, we allow to freely
configure our initialization state, which is by default "undefined" but
can be configured to any other state and therefore provide the operator
with a maximum on flexibility on how to proceed in this case.

Oliver

---------------------------------------------------------------------------
-

Oliver Borchert  Computer Scientist
National Institute of Standards and Technology
phone: 301-975-4856, fax: 301-975-6238

---

From: Randy Bush <[email-masked]>
Date: Thu, 14 Mar 2013 06:55:20 -0400

what will an operator do differently for these two shades of grey?

what is the trust difference?

was this perhaps discussed extensively before?  what did the security
folk tell us in that discussion?

randy

---

From: aservin <[email-masked]>
Date: Thu, 14 Mar 2013 06:51:19 -0700

After talking to Oliver and the comments of Andy I think that it 
might valuable that fourth state.

   Trying to respond to Randy I thought that it may be useful to know if 
a route is unknown (prefix holder does not care about the prefix, i 
might not trust it) or "undefined" (i lost connectivity with the cache)

   Perhaps adding a very low preference to unknown (not signed, perhaps 
unsecure?) and leave undefined untouched?

   Does it make sense?

/as

El 14-03-2013 03:55, Randy Bush escribió:
> _______________________________________________
> sidr mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/sidr

---

From: "Montgomery, Douglas" <[email-masked]>
Date: Thu, 14 Mar 2013 11:03:04 -0400

I remember, and agree with the decision to not try to distinguish among various flavors of INVALID.

I think this discussion is different.   RFC6811 provides a complete 3 state taxonomy for the result of origin validation, but is based on some assumptions (e.g., reasonable access ("loose consistency") to RPKI (or other DB) information).

"UNDEFINED" is a implementation realization that there are circumstances when the implicit assumptions of RFC6811 may not hold, and one may like to have routing policies that take that fact into consideration.

So far we have waived our hands and said smart people won't let those assumptions fail.  Folks who are worried about new systemic dependencies  between routing and global info systems would appreciate the ability to write purposeful policies that could deal with the scenario "what if we can't perform the validation function as defined?".

I can think of scenarios in which I might treat UNDEFINED different than UNKNOWN/NOT-FOUND.

I don't think could/should standardize all circumstances under which the result UNDEFINED is returned - other than the situations in which the assumptions of RFC6811 aren't met, or the validation function is unable to execute the defined validation algorithm.

dougm
--
Doug Montgomery - Manager Internet and Scalable Systems Research  / ITL / NIST

________________________________________
From: [email-masked] [[email-masked]] On Behalf Of aservin [[email-masked]]
Sent: Thursday, March 14, 2013 9:51 AM
To: [email-masked]
Subject: Re: [sidr] NotFound vs Uninitialized

   Does it make sense?

/as

---

From: "Borchert, Oliver" <[email-masked]>
Date: Thu, 14 Mar 2013 11:18:31 -0400

I prefer Undefined over Uninitialized and therefore use Undefined below.

> what will an operator do differently for these two shades of grey?

The "Undefined" state is most likely to change shortly after assigned. If processed as "NotFound" and selected but validated as "Invalid" it would have to be withdrawn right away. A well-defined temporary state such as "Undefined" allows scripting policies such as "Ignore until validation state is available" 

> what is the trust difference?

"FotFound" is a well-defined state within the Cache. It gives a clear answer about the content of the cache. It is what it is, no information found in the cache. 
"Undefined" on the other hand tells me that currently no cache information is available and I simply don't know if it is "NotFound", "Valid", or "Invalid" - I personally have some trouble just assuming a state.

> was this perhaps discussed extensively before?  what did the security folk
> tell us in that discussion?
> 

I don't remember this topic being discussed publicly but at NIST, we spend some time around this topic. And as one of the previous emails shows, at least one other implementation next to ours independently introduced this state.

Oliver

---

From: Andrew Chi <[email-masked]>
Date: Thu, 14 Mar 2013 13:16:20 -0400

> what will an operator do differently for these two shades of grey?

Good question.  *Operators*, would you ever treat these differently?

> what is the trust difference?

NotFound: The global RPKI doesn't know this route, i.e., *nobody* knows.
Undefined: *I* don't know what the RPKI says about this route.

---

From: "Murphy, Sandra" <[email-masked]>
Date: Thu, 14 Mar 2013 17:53:44 +0000

>Good question.  *Operators*, would you ever treat these differently?

I thought Ruediger was saying that the need for this 4th state arose as his company was studying using RPKI.

Ruediger, was there a difficulty?  a need not met by just 3 states?  can you say what it was?

--Sandy, speaking as regular ol' wg member

---

From: "Montgomery, Douglas" <[email-masked]>
Date: Thu, 14 Mar 2013 14:02:13 -0400

Not an ops person - so take with a grain of salt - but imagine a world N years from now where I only accept routes that have VALID origins.  All others routes are dropped.    

Imagine a net/power/nature event that both reboots my routers and all of the caches that I speak too.   If may prefer to reboot the routing system without validation, until enough infrastructure is up to begin validation. 

dougm
--
Doug Montgomery - Manager Internet and Scalable Systems Research Group  / ITL / NIST
________________________________________
From: [email-masked] [[email-masked]] On Behalf Of Andrew Chi [[email-masked]]
Sent: Thursday, March 14, 2013 1:16 PM
To: [email-masked]
Subject: Re: [sidr] NotFound vs Uninitialized

---

From: Jac Kloots <[email-masked]>
Date: Thu, 14 Mar 2013 19:21:16 +0100 (CET)

>From what I understood he's missing a state for unverifiable resources. eg. 
when the validator isn't reachable.

Reading the RFC6811 again, I think the state is covered by the NotFound 
state; No VRP Covers the Route Prefix.

The problem arises when strict RPKI policing is used. Using a strict policy 
you'd only accept Valid prefixes and drop _all_ the others.

For this case a 4th state could be introduced. This state would only be 
assigned if there are no entries in the entire VRP. The strict policy should 
then accept Valids and 4th state prefixes.

Jac

-- 
Jac Kloots
Network Services
SURFnet bv

---

From: heasley <[email-masked]>
Date: Thu, 14 Mar 2013 20:25:51 +0000

> Imagine a net/power/nature event that both reboots my routers and all of the caches that I speak too.   If may prefer to reboot the routing system without validation, until enough infrastructure is…

or your validation server is remote - within a prefix that will not be
accepted because it is NotFound/Undefined?

---

From: Randy Bush <[email-masked]>
Date: Thu, 14 Mar 2013 17:10:38 -0400

> NotFound: The global RPKI doesn't know this route, i.e., *nobody*

nope.  a cache can not make such an absolute statement

randy

---

From: Andrew Chi <[email-masked]>
Date: Thu, 14 Mar 2013 23:00:16 -0400

> nope.  a cache can not make such an absolute statement

I thought someone might pick on that!  I was trying to capture the 
intuition rather than the definition; apologies for being imprecise.

Randy, are you implying that in the operator's shoes, the shades of gray 
are not really that distinct?  Meaning that it will never be completely 
safe to drop NotFound?  Just trying to understand.

---

From: Randy Bush <[email-masked]>
Date: Fri, 15 Mar 2013 03:54:45 -0400

> Randy, are you implying that in the operator's shoes, the shades of
> gray are not really that distinct?  Meaning that it will never be
> completely safe to drop NotFound?

my *personal* take is drop invalid and keep the rest.  not sure if i
wanna up-pref valid, though i might.  i would be pretty comfortable to
up-metric valid.

randy