BIND 10 #506: Analysis of Wildcard Processing

[BIND 10 Development]

#506: Analysis of Wildcard Processing
-------------------------------------+-------------------------------------
                 Reporter:  stephen  |                Owner:  jinmei
                     Type:           |               Status:  accepted
  enhancement                        |            Milestone:  A-Team-
                 Priority:  major    |  Sprint-20110209
                Component:           |           Resolution:
  b10-auth                           |            Sensitive:  0
                 Keywords:           |  Add Hours to Ticket:  0
Estimated Number of Hours:  3.0      |          Total Hours:  0
                Billable?:  1        |
                Internal?:  0        |
-------------------------------------+-------------------------------------

Comment (by jinmei):

 This is a more complete version of BIND 9's wildcard handling
 in its rbtdb.  I've simplified the logic a bit for (the current
 implementation of) the BIND 10 in-memory zone.

 '''Loading'''

 The basic idea is to mark the parent node of a wildcard name
 (e.g. example.com for *.example.com) in order to force the find()
 logic to perform special callback (like delegation).

 This proces is two-fold:
  - when loading an RRset, if the owner name is a wildcard (e.g.
    *.foo.example.com) and the RR type is !NS && !NSEC3, enable callback
 for
    the parent node (e.g. foo.example.com), and mark that node as "wild".
  - for any owner name, check if any of its ancestor is a wildcard.
    this is the case, e.g., when adding "foo.*.example.com", which would
    result in an empty non terminal wildcard node for name "*.example.com".
    Note: adding such a name as "foo.*.example.com" is almost bogus, and
    BIND 9 rejects loading them by default.  It's still not prohibited
    by the protocol spec, however.  If an ancestor name is a wildcard,
    explicitly add a rbt node for that name (to make sure if can find it
    as an exact match by find()), and mark its parent as "wild".

 '''Finding (wildcard matching)'''

 First, add a new member variable "wild" (boolean) to FindState.
 If true, it means find() encounters a "wild" node during the search.

 We also need a new primitive to get the "previous" node of a given
 RBTree node (for a minor case handling).

  - in zonecutCallback(), if it's not a delegation and the node is marked
    as "wild", set FindState::wild to true.  on the other hand, once it
    encounters a delegation, reset it to false.  RFC1034 requires we cancel
    wildcard matching on delegation (Section 4.3.3)
  - in find(), if the search result is PARTIALMATCH and it's not a
 delegation,
    perform the wildcard check.  It works as follows:
    1. if the search stops at a node marked as "wild", that may be a
      wildcard match.  otherwise, it's not (this case is possible if
      there are *.example.com and foo.example.com, and the query name
      is bar.foo.example.com).
    2. if it can be a wildcard match, construct the wildcard name by
      prepending '*' to the node's abstract name.
    3. get the RBTree node for that wildcard name by searching RBTree.
    4. reject the case where the query name is a subdomain of an empty
      non terminal node under the node marked as "wild" (which was found
      in the first find()).  This process is complicated, so it's described
      separately below.
    5. if the wildcard match is allowed, use the RRsets for the wildcard
      node, and return any positive response with replacing the owner name
      of the RRset (which is the wildcard name) with the query name.

 '''Cancel wildcard match due to an empty non terminal'''

 This process is details of step 4 of the wildcard check in the previous
 section.  It implements the following part of Section 4.3.3 of RFC1034:
 {{{
    - When the query name or a name between the wildcard domain and
      the query name is know to exist.
 }}}

 Specifically, when the wildcard name *.example.com and the zone has
 bar.foo.example.com, this process will reject aaa.foo.example.com
 and zzz.foo.example.com to be matched against the wildcard.

 The necessary steps are as follows:
  - get the previous and next node (in DNSSEC order) of the last matching
    node for aaa.foo.example.com, they are *.example.com and
    bar.foo.example.com, respectively; for zzz.foo.example.com, they are
    aaa.foo.example.com and something else (or none), respectively.
  - check if any ancestor name of the query name (including the qname
    itself) up to the node marked as "wild" (in this case example.com)
    is a super domain of either the previous and next node name.
    For aaa.foo.example.com, its 1-generation ancestor, foo.example.com
    is a super domain of the next, "bar.foo.example.com"; for
 zzz.example.com,
    its 1-generation ancestor, again foo.example.com is a super domain
    of the previous, "bar.foo.example.com".  This means the query name
    is a subdomain of an empty non terminal under the "wild" node,
    foo.example.com, and should not allow wildcard match.

 '''proposed subtasks'''

 I propose breaking down the above into the following 4 sub tasks:

  - loading part
  - finding part (except the non empty terminal rejection)
  - a new primitive for rbtree to get the previous node of a given node
    (this task can be done separately)
  - implement canceling wildcard match due to an empty non terminal.
    it requires the new primitive described in the previous bullet.

-- 
Ticket URL: <http://bind10.isc.org/ticket/506#comment:3>
BIND 10 Development <http://bind10.isc.org>
BIND 10 Development