[Search] [txt|pdfized|bibtex] [Tracker] [Email] [Nits]
Versions: 00                                                            
Network Working Group                                          B. Campen
Internet-Draft                                          Estacado Systems
Expires: August 30, 2006                               February 26, 2006


         An Efficient Loop Detection Algorithm for SIP Proxies
               draft-campen-sipping-stack-loop-detect-00

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on August 30, 2006.

Copyright Notice

   Copyright (C) The Internet Society (2006).

Abstract

   This document defines a loop-detection algorithm with a cumulative
   O(n) complexity (O(1) average complexity for each proxy) and average
   O(log n) state-space, where n is the number of proxies that the
   message passes through.  Also, the backwards-compatibility and
   security of this algorithm are discussed.

   Comments are solicited, and should be directed to the SIPPING working
   group list at 'sipping@ietf.org'.




Campen                   Expires August 30, 2006                [Page 1]


Internet-Draft          sipping-stack-loop-detect          February 2006


Table of Contents

   1.  Conventions and Definitions  . . . . . . . . . . . . . . . . .  3
   2.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   3.  The Stack Cycle Detection Algorithm in brief . . . . . . . . .  3
   4.  Applying the stack algorithm . . . . . . . . . . . . . . . . .  3
     4.1.  Basic ordering of proxies  . . . . . . . . . . . . . . . .  3
     4.2.  Differentiating between spirals and loops  . . . . . . . .  4
     4.3.  Representation of state  . . . . . . . . . . . . . . . . .  4
   5.  Normative language . . . . . . . . . . . . . . . . . . . . . .  5
   6.  Properties of this algorithm . . . . . . . . . . . . . . . . .  5
     6.1.  Robustness against non-compliant proxies . . . . . . . . .  5
     6.2.  Robustness against a malicious UAC . . . . . . . . . . . .  6
     6.3.  Robustness against malicious proxies . . . . . . . . . . .  7
     6.4.  Robustness against value collisions  . . . . . . . . . . .  7
     6.5.  Special consideration: High availability and load
           balancing  . . . . . . . . . . . . . . . . . . . . . . . .  7
   7.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . .  8
   8.  Security Considerations  . . . . . . . . . . . . . . . . . . .  8
   9.  Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . .  8
   10. References . . . . . . . . . . . . . . . . . . . . . . . . . .  8
     10.1. Normative References . . . . . . . . . . . . . . . . . . .  8
     10.2. Informative References . . . . . . . . . . . . . . . . . .  8
   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 10
   Intellectual Property and Copyright Statements . . . . . . . . . . 11


























Campen                   Expires August 30, 2006                [Page 2]


Internet-Draft          sipping-stack-loop-detect          February 2006


1.  Conventions and Definitions

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC-2119 [RFC2119].


2.  Introduction

   The [maxforwards-problems] draft shows that a forking loop can be
   used to easily bring down a collection of SIP proxies.  Loop
   detection offers a strategy to prevent this sort of attack, but the
   loop-detection algorithm defined in [RFC3261] sec 16.3 takes O(n)
   runtime at each node, where n is the depth of the Via stack at that
   node.  This document shows how a more efficient loop detection
   algorithm [stack-cycle-detection] may be applied to loop detection
   for SIP requests.  The paper referenced shows that the runtime of
   this algorithm is O(1) for each node (O(n) overall) with an average
   state space of O(log(n)).  Other desirable characteristics of this
   algorithm are summarized here.


3.  The Stack Cycle Detection Algorithm in brief

   Suppose we have a set of nodes.  Assign a unique number (node value)
   to each of these nodes.  As a request passes through a node, look for
   a stack of node values in the request, and pop every value found that
   is higher than the current node's value.  Then, push the current node
   value onto the stack.

   Suppose we have a loop.  Take the node in the loop with the lowest
   node value (call it A).  The first time the message passes through A,
   A pushes its node value onto the stack (since every node pushes its
   value onto the stack).  No other node in the loop will pop A's node
   value, since A's node value is lowest.  When the message returns to
   A, A is guaranteed to pop the stack until it finds its own node
   value, and detects the loop.


4.  Applying the stack algorithm

4.1.  Basic ordering of proxies

   In order for this algorithm to work, we must have a numbering scheme
   for all the SIP proxies in the world.  Using a randomly chosen (at
   least 32-bit) number could suffice, as the probability of a collision
   is very small.  However, if a collision occurs, it is likely to occur
   again with non-trivial frequency, because the proxy node values have



Campen                   Expires August 30, 2006                [Page 3]


Internet-Draft          sipping-stack-loop-detect          February 2006


   a long lifetime.  Therefore, it is desirable to attempt a unique
   naming scheme.  An easy way to do this is to base the node value on
   IP address, but there are cases where this will not be acceptable
   (see Section 6.5).

   Unfortunately, allowing the node values to be constant for long
   periods of time means that proxies with relatively low node values
   will do a larger share of the work than other proxies.  However,
   allowing node values to change is problematic, as we must ensure that
   the node values are invariant throughout the forwarding of any
   request.

   An easy way of accomplishing this is to use a hash of CallId and the
   proxy's unique id.  Because CallId is invariant throughout the
   forwarding of a request, the proxy node values would be invariant
   throughout and specific to that request.  However, the node values
   will be different for every request, allowing work to be distributed
   more fairly.

4.2.  Differentiating between spirals and loops

   In order to differentiate between spirals and loops with this
   approach, we would need to keep a record of the various headers that
   influence routing behavior, which is what the branch parameter hash
   specified in sec 16.6 of [RFC3261] is intended to do.  However, since
   we are already capturing information about the proxy and the request
   in a hash, it is appropriate to capture the rest of the information
   normally found in the branch parameter hash.  In this scheme, a node
   no longer corresponds to a proxy, but to a state within a finite-
   state-machine, where each state is defined by
      a.  The proxy the request is passing through.
      b.  The CallId of the request (in other words, which request this
      is).
      c.  Any information that might affect the routing of the request
      (Request-Uri and topmost route header value, at a bare minimum).
   If we observe a loop within the state machine, we have found a
   genuine loop that must be stopped.  Spirals will not manifest as
   loops within this state machine, because c will differ.

4.3.  Representation of state

   Now that we have identified the state that must be captured in the
   loop detection stack, we must have somewhere in the message to store
   this stack.  To this end, we propose a new header called LDStack that
   will contain a lower-case string of hex-digits representing 64 bits
   (ie, 16 lower-case hex digits).

   This value will be constructed as a 64-bit hash of the proxy's unique



Campen                   Expires August 30, 2006                [Page 4]


Internet-Draft          sipping-stack-loop-detect          February 2006


   id (this could be based on IP address, for instance), the CallId
   header value, the Request-Uri, the URI in the topmost route header,
   and any other information that may change throughout forwarding that
   impacts the routing decisions of this proxy.  The values of To, From,
   and CSeq are unnecessary, since they are invariant throughout
   forwarding.  We have only included the value of CallId in order to
   make node values specific to given requests.

   The first LDStack header value will be understood to represent the
   top of the stack.


5.  Normative language

   A proxy that uses this algorithm MUST adhere to the following
   procedure.

      1.  Compute a fresh hash according to Section 4.3.
      2.  Pop LDStack header field values that satisfy either of the
      following conditions:
         -The LDStack header value is garbage (ie, does not consist of a
         16 lower-case hex digit string)
         -The 64-bit integer represented by the LDStack header value is
         greater than the 64-bit integer calculated in step 1. (this can
         be done as either a lexical comparison or an integer
         comparison; the results will be the same)
      3.  If the 64-bit value remaining at the top of the stack is equal
      to the value calculated in step 1, respond with a 482.  Otherwise,
      push the value calculated in step 1 (in lower-case hex
      representation) onto the stack as a new LDStack header value, and
      continue processing the message as specified in section 16.3 of
      RFC 3261.


6.  Properties of this algorithm

   As with any proposed addition to SIP, we must examine this
   algorithm's backwards-compatibility and resistance to malicious
   messages.

6.1.  Robustness against non-compliant proxies

   It is important to note that this algorithm still works when non-
   participating proxies are present in the loop.  This is because the
   non-participating proxies may be considered non-entities with respect
   to the algorithm.  When all non-compliant proxies are removed from
   consideration, we still will have a loop in the compliant proxies,
   and the algorithm will still function.



Campen                   Expires August 30, 2006                [Page 5]


Internet-Draft          sipping-stack-loop-detect          February 2006


   To motivate further, let us consider the trivial case, where we have
   only one compliant proxy.  The first time this message passes through
   this node, it will push the first (and only) LDStack header into the
   message.  No other proxy will modify the loop-detection stack, and
   when the message comes back to the only compliant proxy, it will find
   the node value that was inserted earlier, and halt the loop.

   However, it should be noted that proxies participating in the
   algorithm incorrectly will likely cause the algorithm to fail.  The
   algorithm will also fail to function if there are proxies or other
   sip elements inside the loop that re-order or remove the LDStack
   headers.

6.2.  Robustness against a malicious UAC

   It is also important to note that a malicious UAC will be unable to
   cause the algorithm to fail in detecting a loop by pre-loading
   garbage LDStack header values.  To motivate this, consider the
   following:

   Suppose a malicious UAC has pre-loaded some number of LDStack headers
   into a request.  (These may be ordered in any fashion) Take the
   minimal node value x within the chain of nodes that this message will
   pass through (recall that a node is a _state_ describing what proxy
   the message is passing through, which request this is, and the values
   of its Request-Uri and topmost route header).  Consider the pre-
   loaded LDStack headers.  Take the first header whose value y is less
   than or equal to x. (if there is no such value y, all of the forged
   node values will be removed, and the algorithm proceeds unimpeded) If
   y is equal to x, a loop will be detected, which is opposite the
   intention of the malicious UAC.  If y is less than x, when this
   request first passes through node with value x, the stack will be
   reduced to x, then y, then some progression of arbitrary LDStack
   headers.  These arbitrary headers have never been inspected, and
   never will be, because y is lower than any node value in the chain.
   Hence, these arbitrary headers do not impact the algorithm in any way
   from here on, and may be considered as non-existent for all intents
   and purposes.  When we consider these values as non-existent, we have
   a valid loop-detection stack (even y may be considered non-existent
   because it will never be inspected again).  If x is before the loop,
   the request will enter the loop with a valid loop-detection stack,
   and the algorithm will work as intended.  If x is inside the loop, it
   is the minimal element within the loop (because it was the minimal
   element overall), and the next time the request comes through x, the
   loop will be detected.

   In the event that a proxy discovers a malformed LDStack value, it is
   necessary that the proxy remove that value, or respond with an error.



Campen                   Expires August 30, 2006                [Page 6]


Internet-Draft          sipping-stack-loop-detect          February 2006


   This is because if proxies are allowed to attempt interpretation of
   this header value, we could have different proxies interpreting it in
   different ways, leading to failure in the algorithm.

6.3.  Robustness against malicious proxies

   Because this algorithm relies on all participating nodes to properly
   implement the algorithm, a malicious proxy inside the loop could
   easily cause loop detection to fail.  However, any malicious proxy
   inside the loop will be exposed to the effects of an attack, making
   it an expensive method for causing DoS.  It is also worth noting that
   RFC 3261 loop detection may also be defeated, by altering the branch
   parameters of requests as they are forwarded, or even deleting Via
   header field values while not decreasing the value of Max-forwards.

   Malicious proxies outside of the loop (in the "tail") will be unable
   to tamper with the algorithm, by a similar argument as presented in
   Section 6.2.

   The possibility that a malicious proxy might cause this algorithm to
   falsely detect a loop is moot, because that proxy could just choose
   to not forward the request.

   In short, this algorithm would present no new avenues of exploit to
   malicious proxies, with regards to loop-detection.

   It is worth noting that a proxy designed to generate artificially
   high hash values will be unlikely to do much of the work required by
   this algorithm.  (Because the hash values are higher than what is
   currently on top of the stack, it needs to do only one comparison,
   and push its hash onto the stack) This sort of misbehavior could be
   used to artificially inflate performance statistics of closed-source
   sip elements.

6.4.  Robustness against value collisions

   In order for a value collision to occur, two proxies must generate
   identical 64-bit hashes.  This is astronomically unlikely, and will
   only cause a single request to fail.  Further, since the hashes are
   based on the CallId header value, they will change with each request,
   meaning that a repeated collision is just as unlikely as the
   original.  Further, there is no case where a hash collision will
   cause a loop to go undetected.

6.5.  Special consideration: High availability and load balancing

   Because the hash generated may be based in part on the proxy's IP
   address, it is reasonable to ask what happens in systems where



Campen                   Expires August 30, 2006                [Page 7]


Internet-Draft          sipping-stack-loop-detect          February 2006


   several different machines are acting as a single logical SIP
   element, or in systems where several logical SIP elements are
   collocated.  In these cases, using an IP address is not appropriate,
   but the desire still remains for a unique id.

   This is an open issue, and merits discussion.


7.  IANA Considerations

   TBD


8.  Security Considerations

   Security considerations are discussed in Section 6.2 and Section 6.3.


9.  Acknowledgments

   Thanks goes to the individuals who gave their input on the viability
   of this algorithm.  These include Robert Sparks, Adam Roach, Scott
   Lawrence, and Scott Godin.  Also, thanks goes to Nicolas Grunbaum,
   who pointed out the problem mentioned in Section 6.5


10.  References

10.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC3261]  Rosenberg, J., Schulzrinne, H., Camarillo, G., Johnston,
              A., Peterson, J., Sparks, R., Handley, M., and E.
              Schooler, "SIP: Session Initiation Protocol", RFC 3261,
              June 2002.

10.2.  Informative References

   [maxforwards-problems]
              Sparks, R., Ed., Lawrence, S., and A. Hawrylyshen,
              "Problems with Max-Forwards Processing (and Potential
              Solutions)".

   [stack-cycle-detection]
              Nivasch, G., "Cycle Detection Using a Stack
              (http://yucs.org/~gnivasch/stackalg/index.html)",



Campen                   Expires August 30, 2006                [Page 8]


Internet-Draft          sipping-stack-loop-detect          February 2006


              January 2004.


















































Campen                   Expires August 30, 2006                [Page 9]


Internet-Draft          sipping-stack-loop-detect          February 2006


Author's Address

   Byron Campen
   Estacado Systems
   17210 Campbell Road
   Suite 250
   Dallas, Texas  75254-4203
   USA

   Email: bcampen@estacado.net









































Campen                   Expires August 30, 2006               [Page 10]


Internet-Draft          sipping-stack-loop-detect          February 2006


Intellectual Property Statement

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.


Disclaimer of Validity

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
   ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
   INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
   INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.


Copyright Statement

   Copyright (C) The Internet Society (2006).  This document is subject
   to the rights, licenses and restrictions contained in BCP 78, and
   except as set forth therein, the authors retain all their rights.


Acknowledgment

   Funding for the RFC Editor function is currently provided by the
   Internet Society.




Campen                   Expires August 30, 2006               [Page 11]