Subject: Re: [alto] Security problem: DoS attacks via overload

From: Wendy Roome <[email-masked]>
Date: Tue, 19 Mar 2013 10:39:03 -0400

Richard,

You said,

> We anticipate that most deployment cases will not generate huge maps and
> hence it should be fine.
> 
A year ago, when I realized that full cost maps can get very large, I asked
the group how many PIDs they expected ALTO servers to provide. 10's, 100's,
1000's., Š.?  No one answered that question. Just in case, I extended the
Alcatel-Lucent ALTO server and client to handle several thousand PIDs, but
it took some effort.

Remember that protocols have a way of scaling up far past their designer's
original expectations. For example, I'm old enough to remember when IPV4
addresses seemed infinite. (I'm also old enough to have used keypunches and
card decks and IBM System 360s, but that's another issue.)

So think carefully about what would happen if the number of PIDs grows
beyond our wildest dreams. Because it might!

I certainly agree that the protocol should not define limits. But I think
the protocol should allow an ALTO server to define & impose its own limits,
and communicate those limits to clients. So here's my suggestion for how the
ALTO protocol could support implementation-defined limits:

1) Make full cost-maps optional, instead of required.
2) For filtered cost map requests, add an optional IRD capability giving the
server's limit on the number of source/destination pairs allowed per
request.
3) Add a "Request Too Large" ALTO error code in case a client exceeds that
limit.

Comments, suggestions?

- Wendy Roome

> Date: Mon, 18 Mar 2013 15:31:43 -0400
> From: "Y. Richard Yang" <[email-masked]>
> Subject: Re: [alto] Security problem: DoS attacks via overload
> Message-ID:
> <CANUuoLqjWLOB7w9Hhz3u1rMgM36-q=c55i=rNEbGHzU=[email-masked]>
> Content-Type: text/plain; charset="iso-8859-1"
> 
> Hi Wendy,
> 
> Good comment. The current wording on this related issue is:
> --------
> 13.5.  Availability of ALTO Service
> 
> 13.5.1.  Risk Scenarios
> 
>    An attacker may want to disable ALTO Service as a way to disable
>    network guidance to large scale applications.In particular, queries
>    which can be generated with low effort but result in expensive
>    workloads at the ALTO Server could be exploited for Denial-of-Service
>    attacks.  For instance, a simple ALTO query with n Source Network
>    Locations and m Destination Network Locations can be generated fairly
>    easily but results in the computation of n*m Path Costs between pairs
>    by the ALTO Server (see Section 5.2).
> 
> 13.5.2.  Protection Strategies
> 
>    ALTO Provider should be cognizant of the workload at the ALTO Server
>    generated by certain ALTO Queries, such as certain queries to the Map
>    Service, the Map Filtering Service and the Endpoint Cost (Ranking)
>    Service.  One way to limit Denial-of-Service attacks is to employ
>    access control to the ALTO Server.  The ALTO Server can also indicate
>    overload and reject repeated requests that can cause availability
>    problems.  More advanced protection schemes such as computational
>    puzzles [I-D.jennings-sip-hashcash] may be considered in an extension
>    document.
> 
>    An ALTO Provider should also leverage the fact that the Map Service
>    allows ALTO Servers to pre-generate maps that can be distributed to
>    many ALTO Clients.
> --------
> 
> We anticipate that most deployment cases will not generate huge maps and
> hence it should be fine.
> 
> The idea of limiting the topology size (i.e., the number of nodes) is quite
> interesting, but can be technology dependent. In the old days when the
> backbone of the Internet was only kbps or Mbps, the data to represent a
> small may produce a large amount of data and can be overwhelming for slow
> computers to process. Hence, such a limit cannot be fixed but should be
> changing as time passes by (e.g., announced in IRD). It adds complexity
> that we may not want to address at this stage. What do you think?
> 
> Richard
> 
>

---

From: "Y. Richard Yang" <[email-masked]>
Date: Tue, 19 Mar 2013 16:48:19 -0400

Hi Wendy,

Thanks for the good comments. Please see below.

On Tue, Mar 19, 2013 at 10:39 AM, Wendy Roome <[email-masked]>wrote:

> A year ago, when I realized that full cost maps can get very large, I
> asked the group how many PIDs they expected ALTO servers to provide. 10's,
> 100's, 1000's., ….?  No one answered that question. Just in case, I
> extended the Alcatel-Lucent ALTO server and client to handle several
> thousand PIDs, but it took some effort.
>
> and communicate those limits to clients. So here's my suggestion for how
> the ALTO protocol could support implementation-defined limits:
>

I actually dot not have strong preference here, and I can see the benefits
of your minimalist approach. For example, one deployment scenario of ALTO
might be to provide mostly endpoint properties, say for Hadoop rack API,
and there is no need that the ALTO Server must list an IR for CostMap. The
protocol interops.

> 2) For filtered cost map requests, add an optional IRD capability giving
> the server's limit on the number of source/destination pairs allowed per
> request.

I feel that the limit can be load/server capacity dependent. Adding the
limit may be a too large a change at this moment. I do like the idea of
adding a Request Too Large error code, and hence a client can learn
(through binary search or an future error code indicating suggested size).
What do you think?

Richard

Comments, suggestions?
> _______________________________________________
> alto mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/alto
>
>

---

From: Sebastian Kiesel <[email-masked]>
Date: Tue, 19 Mar 2013 22:29:44 +0100

Wendy,

thanks for bringing this back to our attention again.
Some thoughts on that:

1.  The size of the cost map does not necessarily scalewith the 
    square of the number of PIDs.

    In particular when the ALTO server is operated by an access network
    operator, I expect the cost matrix to be a very sparse matrix with
    most of the values being some "I don't know" default value.

    For example, being the operator of a (very small) access network in
    Europe I can tell the cost and with some uncertanity also some
    performance expecations for traffic from our network to various
    destinations in the world, but I cannot tell much about about, say,
    the connectivity from a given access network in the U.S. to one in
    Japan - and neither me nor the users in our network will care too
    much about that anyway ...  In other words, I expect that an ALTO
    server in an access network will basically deliver a vector (from
    here to ...), leaving all other positions in the matrix to the
    default value -> with our encoding the message size would scale 
    linear with the number of PIDs.

    On the other hand, there may be "independent" ALTO servers in
    the network, doing distributed meaurements and/or aggregation
    of data retrieved from various access-network-local ALTO servers.
    These might be able to deliver a dense matrix, i.e., one that
    scales quadratically.

2.  An ALTO server operator is free to define only a limited number
    of PIDs, small enough that the cost map can be handled. The
    opearator can decide on the tradeoff between accuracy and size,
    and can adjust this as both available server and bandwith ressources
    as well as network complexity change over time.

3.  The cost map is a simple "tell me all you know" thing that can be
    pre-computed and cached.  If we abandon it, clients might be tempted
    to ask multiple queries to gather as much information as possible,
    each possibly causing server-side computations.

4.  If we make the full cost map optional, what would be the
    "MUST implement" part of the ALTO protocol? If all map, property,
    and filtering services are optional this may harm interoperability.

So I tend say let's leave it mandatory but the opinion is not very strong.

Thanks
Sebastian

---

From: Wendy Roome <[email-masked]>
Date: Wed, 20 Mar 2013 13:11:04 -0400

How about making the limit optional, and calling it 'advice'?  That is,
      "capabilities":{"query-limit-advice": 1000}
means the server will probably accept requests if n(src)*n(dest) < 1000, and
will probably reject queries for more cost-points -- but there are no
guarantees. 

BTW, speaking as a server implementor, it would be difficult to dynamically
determine a limit based on the current load. Instead, I'd just define a
static limit (a configuration parameter, of course), and enforce that limit
regardless of the current conditions.

- Wendy Roome

> Date:  Tue, March 19, 2013 16:48
> To:  Wendy Roome <[email-masked]>
> Cc:  <[email-masked]>
>> server's limit on the number of source/destination pairs allowed per request.
> I feel that the limit can be load/server capacity dependent. Adding the limit
> may be a too large a change at this moment. I do like the idea of adding a
> Request Too Large error code, and hence a client can learn (through binary
> search or an future error code indicating suggested size). What do you think?
> 
> Richard

---

From: "Diego R. Lopez" <[email-masked]>
Date: Thu, 21 Mar 2013 00:41:17 +0000

Hi,

Since I am in the same situation as Wendy (in terms of being old enough to remember when the Internet was small and even when it barely existed) I like the idea of the "Request Too Large" error code, that reminds me what a LDAP server returns when a search would include more entries than what the server configuration allows to be returned.

And I must say I support the idea of making full cost maps optional. Replacing MUST for a SHOULD (and making clear that only the "Request Too Large" error is acceptable to not satisfy it) should be enough to avoid the overload risk while staying as close as possible to the minimum that makes Sebastian feel uneasy...

Be goode,

--
"Esta vez no fallaremos, Doctor Infierno"

Dr Diego R. Lopez
Telefonica I+D
http://people.tid.es/diego.lopez/

e-mail: [email-masked]
Tel:    +34 913 129 041
Mobile: +34 682 051 091
-----------------------------------------

________________________________

Este mensaje se dirige exclusivamente a su destinatario. Puede consultar nuestra política de envío y recepción de correo electrónico en el enlace situado más abajo.
This message is intended exclusively for its addressee. We only send and receive email on the basis of the terms set out at:
http://www.tid.es/ES/PAGINAS/disclaimer.aspx

---

From: Richard Alimi <[email-masked]>
Date: Thu, 21 Mar 2013 01:27:56 -0700

To the two things being considered on this thread:

(1) Should the map service be required or optional?

I believe we should have a base set of functionality that is required.  My
concern with making everything optional is that ALTO Clients wishing to
operate on the public Internet are left needing to implement code paths for
both the full maps and endpoint cost services.

I understand that there are going to be deployments that may not need the
map service.  It is within their power to return "I don't know".

In short, my preference is to reduce the complexity needed in the case
where there is little or no coordination between the ALTO Client and ALTO
Server providers (e.g., when the ALTO client is part of an application on a
subscriber's device, and the ALTO Server is hosted by an ISP).

Along those lines, I could probably be convinced that SHOULD instead of
MUST is suitable for the Map Service.

(2) Should there be a maximum response size and should the ALTO Client be
made aware of it?

I think its certainly within the server's ability to guard against requests
that it can't satisfy due to resource constraints.  I would imagine that it
an HTTP 503 would be reasonable here (which is already doable by the
current spec).

However, I don't believe its necessary to give ALTO clients guidance on the
size of the query.  A few reasons why:
- In an environment where the ALTO Server is behind some load-balancing
mechanism, the available resources to service a request are going to be
dependent on the particular machine handling the request.  If you tell the
client "sorry, I can support up to 1000 source/destination pairs" and the
client closes the TCP connection and retries with a different source port,
the next request may arrive at a different physical machine which may have
a different limit on what it can safely support.
- Let's say someone really wanted to DoS the server and you told them that
you can only reply to queries with up to 1000 source/destination pairs.  In
a DDoS scenario, they are just going to send more queries each with the
maximum query size that you'll allow.
- If the ALTO Server is overloaded and still wants to actually answer
queries (instead of returning errors), it is within its power to aggregate
the information (say, aggregate to 100 PIDs instead of 1000) and then
forget about serving the large maps that were causing it problems.

Thanks,
Rich

On Wed, Mar 20, 2013 at 5:41 PM, Diego R. Lopez <[email-masked]> wrote:

> Hi,
>
> Since I am in the same situation as Wendy (in terms of being old enough to
> remember when the Internet was small and even when it barely existed) I
> like the idea of the "Request Too Large" error code, that reminds me what a
> LDAP server returns when a search would include more entries than what the
> server configuration allows to be returned.
>
> And I must say I support the idea of making full cost maps optional.
> Replacing MUST for a SHOULD (and making clear that only the "Request Too
> Large" error is acceptable to not satisfy it) should be enough to avoid the
> overload risk while staying as close as possible to the minimum that makes
> Sebastian feel uneasy...
>
> Be goode,
>
> --
> Este mensaje se dirige exclusivamente a su destinatario. Puede consultar
> nuestra política de envío y recepción de correo electrónico en el enlace
> situado más abajo.
> This message is intended exclusively for its addressee. We only send and
> receive email on the basis of the terms set out at:

---

From: Jan Seedorf <[email-masked]>
Date: Thu, 21 Mar 2013 09:34:42 +0000

Just to second this, I am resending a comment I made a long time ago about DoS attacks / too large matrices (cut and paste from my IETF-75 notes):

"Jan Seedorf: has concerns with the workload for ALTO servers caused by queries with multiple source network locations, risk of easy DoS attacks, answer: the resulting answer matrices can be pre-computed and should not change that frequently"

I remember that in that session (IETF-75) we exactly discussed the problem of "n(src)*n(dest)" becoming too large, or at least I made that comment ...

 - Jan

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Diego R. Lopez
> Sent: Thursday, March 21, 2013 1:41 AM
> To: [email-masked]
> LDAP server returns when a search would include more entries than what
> the server configuration allows to be returned.
> 
> And I must say I support the idea of making full cost maps optional. Replacing
> MUST for a SHOULD (and making clear that only the "Request Too Large"
> error is acceptable to not satisfy it) should be enough to avoid the overload
> risk while staying as close as possible to the minimum that makes Sebastian
> feel uneasy...
> 
> Be goode,
> 
> --