Subject: [Ietf-not43] traditional searches

From: ehall at ehsco.com (Eric A. Hall)
Date: Fri Aug 22 12:54:27 2003

In the message I sent last night, I gave an example of finding all of the
netblocks in a range by having the client query for TC-NET-00.

This is a traditional search-by-value query, and those have several
inter-related issues.

The obvious issue is that these are scope-restrained to a specific
partition. In other words, the client has to know which partition the
query is for (eg, arin.net, or netsol.com, or whatever), find a server
that is capable of processing queries for that partition, and then issue
the query to the selected server. Cumulatively this is all described as
part of the "targetted" model in the current specs.

Since these queries use standard LDAP matching filters, they do not
require any special support by servers that support LDAP. However, Andy
made a case for limiting these, and if we're going to be publishing
capability lists that indicate whether or not any of these are going to be
supported on a particular server, this means that some discussion in the
specs is going to be required.

The current specs allow clients to issue any query-by-value that they
desire, but does not encourage any of them. If we're going to be talking
about the capabilities (above), then we may want to itemize some of the
queries that clients should expect to be able to support, and that servers
should be making available to clients. For example, should we say that
servers SHOULD support equality matches for the private identifier
sequences (the TC-NET-00 example from earlier)? What about soundex queris
for other attributes like company name or whatever? Or should we just
leave it that clients can issue any search-by-value they want/need,
according to the capabilities of the current server?

-- 
Eric A. Hall                                        http://www.ehsco.com/
Internet Core Protocols          http://www.oreilly.com/catalog/coreprot/

---

From: anewton at ecotroph.net (Andrew Newton)
Date: Fri Aug 22 13:17:51 2003

> specs is going to be required.

I am not following this very well.  So I don't know what it is you are 
claiming I said should be limited.  However, the idea of publishing 
capability lists is yours, and in the case of LDAP I think it is a bad 
solution to 3.1.8, if that is what you referencing.

> according to the capabilities of the current server?

By current specs, I assume you are talking about FIRS.  This is already 
true for IRIS by its very nature.

-andy

---

From: ehall at ehsco.com (Eric A. Hall)
Date: Fri Aug 22 13:23:23 2003

on 8/22/2003 12:45 PM Andrew Newton wrote:

>> require any special support by servers that support LDAP. However, 
>> Andy made a case for limiting these, and if we're going to be 
>> publishing capability lists that indicate whether or not any of these
>>  are going to be supported on a particular server, this means that 
>> some discussion in the specs is going to be required.
> 
> claiming I said should be limited.

I took it from the examples you cited that you wanted to be able to refuse
things like substring and approximate matching unless the user was known
to be authorized to do those.

> However, the idea of publishing  capability lists is yours, and in the
> case of LDAP I think it is a bad solution to 3.1.8, if that is what you
> referencing.

Perhaps you could honor us with a counter-proposal that doesn't introduce
outrageous costs on every search.

>>  desire, but does not encourage any of them. If we're going to be 
>> talking about the capabilities (above), then we may want to itemize 
>> some of the queries that clients should expect to be able to support,
>>  and that servers should be making available to clients. For example,
>>  should we say that servers SHOULD support equality matches for the 
>> private identifier sequences (the TC-NET-00 example from earlier)? 
>> What about soundex queris for other attributes like company name or 
>> whatever? Or should we just leave it that clients can issue any 
>> search-by-value they want/need, according to the capabilities of the 
>> current server?
> 

Yes, FIRS already works this way. I'm trying to accomodate the additional
restraint mechanisms you indicated were necessary.

---

From: anewton at ecotroph.net (Andrew Newton)
Date: Fri Aug 22 13:39:19 2003

Solution 2 mentioned here:
> http://lists.verisignlabs.com/pipermail/ietf-not43/2003-August/000767.html

Now, maybe you could honor us with a reason why it can't/shouldn't be 
done that way.

-andy

---

From: ehall at ehsco.com (Eric A. Hall)
Date: Fri Aug 22 13:47:02 2003

on 8/22/2003 1:06 PM Andrew Newton wrote:

> Eric A. Hall wrote:
> 
>>> However, the idea of publishing  capability lists is yours, and in
>>> the case of LDAP I think it is a bad solution to 3.1.8, if that is
>>> what you referencing.
>> 
>> Perhaps you could honor us with a counter-proposal that doesn't
>> introduce outrageous costs on every search.
> 

Presumably the reference to (2) are a reference to the (2b) in the
original. As I've already said, that approach has excessive costs. For the
same amount of time spent on the probe, the original query could have just
been issued and rejected, with the exact same results. By comparison, a
capability list would have been returned before the client even got the
chance to issue either the probe or the query, and would have already
moved on to the recovery steps. In short, the capability model is faster
and has significantly lower processing requirements for all parties.

---

From: anewton at ecotroph.net (Andrew Newton)
Date: Fri Aug 22 14:26:27 2003

> and has significantly lower processing requirements for all parties.

No publicly-facing server is going to trust that the client obeys a 
capabilities list and it will always do an authorization check on a 
query.  A 'dry run' switch simply stops the trip to the data store, 
which is probably more expensive than the authorization check.

-andy

---

From: ehall at ehsco.com (Eric A. Hall)
Date: Fri Aug 22 14:55:13 2003

on 8/22/2003 1:53 PM Andrew Newton wrote:

> query.

The benefits of a capabilities model go to both the client and the server
(the client benefits are arguably higher in some scenarios). I'm not
calling this a guarantee of use, just pointing out the motivation. On the
other hand, there is absolutely zero motivation for a client to use a
probe. This is illustrated below.

> A 'dry run' switch simply stops the trip to the data store, 

Here are some examples.

First, a basic rejection of a submitted query due to permission failures
of the query context does not require a trip to the mail store:

  client: bind
  server: okay
  client: query
  server: permission denied
  client: bye

This is identical to a probe that gets rejected. There are zero savings in
this scenario, and the client would have gotten the same mileage from just
issuing the original query:

  client: bind
  server: okay
  client: probe
  server: rejected due to permissions
  client: bye

Worse are successes. Here's a non-probe success:

  client: bind
  server: okay
  client: query
  server: answer data...
  client: bye

Here's a probe success. Again, the client would have been better off by
just issuing the damn query:

  client: bind
  server: okay
  client: probe
  server: okay
  client: query
  server: answer data...
  client: bye

Variations on those themes such as recovery probes/queries follow the same
basic math.

Here's what failure with the capabilities model looks like:

  client: bind
  server: okay; capabilities
  client: bye

Here's what success with the capabilities model looks like:

  client: bind
  server: okay; capabilities
  client: query               <--known valid
  server: answer data...
  client: bye

So, probes are always of equal or higher cost than just issuing the
original query, while the capabilities model is always faster and cheaper.
This is demonstrably better for the servers, but is also better for
clients since latency is cumulative, and the cumulative penalty goes
against the client. EG, if the client gets directed to a resource entry on
a server that is three or four levels deep (domain.isp.co.uk, or a
netblock that is reallocated multiple times), then the extra round trips
really start adding up, especially if they are coming via a high-latency
link (eg, a cellular PDA).

---

From: anewton at ecotroph.net (Andrew Newton)
Date: Fri Aug 22 16:32:27 2003

> link (eg, a cellular PDA).

Admittedly, the use cases are vague.  However, a probe is not guaranteed 
to be as expensive as the query.

Also, a probe is at the client's discretion on a per query basis, where 
as a capabilities list is something always done.

Finally, how do you handle granularity with authorization based on the 
user's relationship with the data.  Is your capabilities list going to 
list all 1000 domains a tech contact is related to?  Not only is that 
bandwidth entensive, it causes a massive search on the server during the 
authentication step and could be totally useless if the user were 
looking up a domain to which they have no relationship.

-andy

---

From: ehall at ehsco.com (Eric A. Hall)
Date: Fri Aug 22 17:25:37 2003

on 8/22/2003 3:59 PM Andrew Newton wrote:

> user's relationship with the data.

Numerous combinations are possible, but again, it would be very useful to
get a description of what is actually needed.

Here's the full text of the addtional requirements presented so far:

Andrew Newton wrote in <[email-masked]>

| I know our service will not allow somebody to do a subtree search in
| the contacts DIT.  For RLDAP, we excluded any partial string matching
| if they didn't give use the first three letters of the name (e.g.
| cn=*, cn=b*, and cn=bob*).  Therefore matching rules, search filters,
| and scope will be allowed and disallowed depending on what the
| person is attempting to do.

---

From: davidb at verisignlabs.com (David Blacka)
Date: Fri Aug 22 18:38:07 2003

> get a description of what is actually needed.

Heh.  Here you go:

3.1.8.1 Protocol Requirement

   The protocol MUST provide a mechanism allowing a client to determine
   if a query will be denied before the query is submitted according to
   the appropriate policies of the operator.

> Here's the full text of the addtional requirements presented so far:

<snipped>

Those weren't requirements.  That was just an example.

The problem here is that the CRISP service is expected to be able to 
support various detailed, nuanced, and, from the perspective of the 
protocol, *arbitrary* policies.  It is hard for me to see how a 
capabilities list could possibly handle that.

In reality, it is likely that the policies enacted by the service operators 
will be common and possibly easily enumerable, but we don't know what they 
are now and don't want to constrain them.

However, given the session state and the query, it will *always* be 
possible to determine whether or not policy will allow it.

I can totally understand the difficulty you are having understanding *why* 
this requirement exists, as I don't really understand why either: why not 
just issue the query and see if it fails?  Maybe those folks who argued 
for the requirement in the first place could enlighten us.  Or maybe it is 
somewhere in the list archives.

I do agree that if the policy in question is based on the data the the 
query would return, it is totally useless from an efficiency standpoint: 
the query is going to actually have to be run, so why not just actually 
issue the query?  But if the policy is based on the session state and 
query itself (thus avoiding a trip to the datastore), I can see how it 
might be useful.

Note that I'm not saying that a capabilities list is a bad thing in and of 
itself.  In fact, I believe that it satisfies the language of 3.1.8.1.  
But in order to actually do it, you will have to enumerate all of the 
policy types as part of the protocol, which might be seen as limiting.  
Also, since the WG hasn't gone through the exercise of enumerating the 
types of policies (and I don't think it should), it will be hard to come 
up with the list.

-- 
David Blacka    <[email-masked]> 
Sr. Engineer    Verisign Applied Research

---

From: ehall at ehsco.com (Eric A. Hall)
Date: Fri Aug 22 19:40:47 2003

on 8/22/2003 5:34 PM David Blacka wrote:

>  query would return, it is totally useless from an efficiency
> standpoint: the query is going to actually have to be run, so why not
> just actually issue the query?  But if the policy is based on the
> session state and query itself (thus avoiding a trip to the datastore),
> I can see how it might be useful.

That's pretty much what I'm focusing on. If you're going to refuse a query
because of syntax (not because of data), then telling the user what they
can expect is useful (to the extent that this is possible). If you're
going to error a query because of data, then the query has to run anyway
so why bother running it in advance.

Right now I'm thinking that the capability list should itemize the FIRS
objectclasses and the filters that are supported for each objectclass. EG,
something like "inetDnsDomain:inetDnsDomainMatch;equalityMatch" would mean
that the swerver will let you use either the inetDnsDomainMatch or
equalityMatch filters to search for domain name resources, but don't
bother submitting substringMatch, approxMatch, or any of the others. In
the case where the server allowed any of the supported queries through,
then the database ACLs are where any additional rejections should happen,
so there is no sense in specifying any of that stuff.

Another more obscure condition would be the contact restrictions Andy
cited, which allowed substringMatch, but only if the assertion value
contained three characters. I'm not sure I want to try and specify
something like that, so that condition should probably be handled with a
private error (text, not code).