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]