Subject: [Sip] Two minor Max-Breadth comments

From: Adam Roach <[email-masked]>
Date: Tue, 24 Jul 2007 09:48:26 -0500

During today's meeting, a point was raised surrounding whether the 
max-breadth approach should limit the total number of requests or merely 
the number of requests in flight at once. The statement is that limiting 
only the ones in flight simultaneously ultimately results in the same 
number of messages as would result without the extension.

While there has been a token mention of Timer C, I think we're 
underestimating the mitigating effect of Timer C.

As an additional point, I think it's worth pointing out that the victim, 
if they recognize they are being subjected to this style of attack, can 
tear the entire tree down fairly rapidly by throwing a 600-class response.

/a

_______________________________________________
Sip mailing list  https://www1.ietf.org/mailman/listinfo/sip
This list is for NEW development of the core SIP Protocol
Use [email-masked] for questions on current sip
Use [email-masked] for new developments on the application of sip

---

From: Dale Worley <[email-masked]>
Date: Tue, 24 Jul 2007 11:00:37 -0400

From: Adam Roach <[email-masked]>

Also, the UAC, if it is not perverse, will ultimately cancel the
request.

Dale

---

From: [email-masked]
Date: Tue, 24 Jul 2007 11:08:21 -0400

One difficulty with Max-Breadth or any similar feature is:  When
forking, how do I allocate the incoming Max-Breadth to the outgoing
forks?  The obvious solution is to split it equally, but the result is
that the depth of the tree is limited to log(Max-Breadth) forks.  One
can easily construct somewhat realistic examples that demand a large
Max-Breadth in order to succeed:

                UAC  Max-Breadth = 16
                / \
               /   \  Max-Breadth = 8
              v     v
             404   proxy
                   / \
                  /   \  Max-Breadth = 4
                 v     v
                404   proxy
                      / \
                     /   \  Max-Breadth = 2
                    v     v
                   proxy 404
                   / \
                  /   \  Max-Breadth = 1
                 v     v
                200   404

That generates only 5 forks but requires a Max-Breadth of 16 to
succeed.  And under Option 2, even using serial forking has this
problem, though the message load is rather light.

However, if we choose Option 1, so that the Max-Breadth allocated to a
canceled fork can be reclaimed for use on other forks, then a proxy
can always fall back from parallel forking to serial forking.  This
allows the forking tree to be explored to Max-Forwards depth, although
extreme cases will explore the deeper leaves serially rather than
parallely, which is a user-visible performance impact (if the UASs do
not respond promptly) but doesn't cause call failure.

Dale

---

From: Robert Sparks <[email-masked]>
Date: Tue, 24 Jul 2007 10:40:24 -0500

These are important points - adding max-breadth makes the effects of  
responses from the endpoints and CANCELS (from the originator or from  
proxies) meaningful.

(In the original attack, the cancel could never catch up with the  
request).

For the last point - Throwing the 600 doesn't tear the whole tree  
down immediately. The 600 will be held by each node until all  
branches under it complete.
Once that happens it moves upstream. When it moves upstream, the next  
node starts canceling other branches. Those CANCELs still won't catch  
the request,
but the number of things it has to chase is bounded above by a constant.

RjS

On Jul 24, 2007, at 9:48 AM, Adam Roach wrote:

> max-breadth approach should limit the total number of requests or  
> merely the number of requests in flight at once. The statement is  
> that limiting only the ones in flight simultaneously ultimately  
> results in the same number of messages as would result without the  
> extension.
>
> As an additional point, I think it's worth pointing out that the  
> victim, if they recognize they are being subjected to this style of  
> attack, can tear the entire tree down fairly rapidly by throwing a  
> 600-class response.
>
> /a
>
>

---

From: Adam Roach <[email-masked]>
Date: Tue, 24 Jul 2007 10:41:11 -0500

> attack, can tear the entire tree down fairly rapidly by throwing a 

To put a finer point on this: by "fairly rapidly," I mean "O(log(n))" 
where n=max-breadth at the root of the tree.

/a

---

From: "DRAGE, Keith \(Keith\)" <[email-masked]>
Date: Wed, 25 Jul 2007 09:08:04 +0200

How does the UAC cancelling the request help.

Surely all we end up with is the CANCEL request desperatly trying to
catch up with all the propagated INVITE requests. I see nothing in the
transaction model that helps it catch up, and I suspect (based on
experience in non-SIP systems) that it never will in most people's
implementations. It will always be pretty much the same number of steps
behind.

Regards

Keith 

> -----Original Message-----
> From: Dale Worley [mailto:[email-masked]] 
> Sent: Tuesday, July 24, 2007 4:01 PM
> To: [email-masked]
> Subject: Re: [Sip] Two minor Max-Breadth comments
> 
> Also, the UAC, if it is not perverse, will ultimately cancel 
> the request.
> 
> Dale
> 
> 
> This list is for NEW development of the core SIP Protocol Use 
> [email-masked] for questions on current sip

---

From: "DRAGE, Keith \(Keith\)" <[email-masked]>
Date: Wed, 25 Jul 2007 09:08:04 +0200

Regards

Keith

---

From: [email-masked]
Date: Mon, 30 Jul 2007 17:33:25 -0400

From: "DRAGE, Keith \(Keith\)" <[email-masked]>

By design, the total number of transactions active at any moment will
be limited to Max-Forwards times Max-Breadth.  In the canonical
example, that's 20 times 64 equals 1280.  There are 64 active
"fingers" that are depth-first-searching the tree of possible forks,
and each finger is limited to being 20 forwards long.  Of course,
there's a lot of activity at the ends of the fingers, but each
finger's actions are serial.

In the worse case, all 1280 transactions are happening on the same SIP
agent, so its work-queue can have 1280 items in it at any moment.  But
at the same time, the work-queue can have no more than 1280 items in
it.

Injecting a CANCEL at the top of the tree, the cancel may have to wait
for 1280 actions to be processed before it gets processed.  The CANCEL
stops the (unique) depth = 1 transaction from generating any more
requests, and also generates CANCELs that go to all of the depth = 2
transactions.

Each of those second-generation CANCELs may have to wait for 1280
work-items ahead of it before they are processed.  (Actually, 19 times
64 equals 1216 work-items.)  But that won't take horribly long, and
you can work out the time-bound by which time all the
second-generation CANCELs have been processed, terminated the
generation of depth = 3 requests, and caused the sending of the
third-generation CANCELs.

Etc., for depth = 3 to 20.

What saves the day is that Max-Breadth prevents any single SIP agent
from becoming totally jammed, so that any CANCEL will be processed
within a bounded amount of time.  And that Max-Forwards prevents the
fork fingers from extending beyond the limit at their tips while their
roots are being torn down by CANCELs.

Dale