[PATCH net v2] ipv4: try to cache dst_entries which would cause a redirect

[PATCH net v2] ipv4: try to cache dst_entries which would cause a redirect

[Hannes Frederic Sowa]

Not caching dst_entries which cause redirects could be exploited by hosts
on the same subnet, causing a severe DoS attack. This effect aggravated
since commit f88649721268999 ("ipv4: fix dst race in sk_dst_get()").

Lookups causing redirects will be allocated with DST_NOCACHE set which
will force dst_release to free them via RCU.  Unfortunately waiting for
RCU grace period just takes too long, we can end up with >1M dst_entries
waiting to be released and the system will run OOM. rcuos threads cannot
catch up under high softirq load.

Attaching the flag to emit a redirect later on to the specific skb allows
us to cache those dst_entries thus reducing the pressure on allocation
and deallocation.

This issue was discovered by Marcelo Leitner.

Cc: Julian Anastasov <ja@ssi.bg>
Signed-off-by: Marcelo Leitner <mleitner@redhat.com>
Signed-off-by: Florian Westphal <fw@strlen.de>
Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
---
v2:
Julian noticed that v1 did omit the redirect flag in rtnetlink queries,
fixed. Thanks!

 include/net/ip.h      | 11 ++++++-----
 net/ipv4/ip_forward.c |  3 ++-
 net/ipv4/route.c      |  8 ++++----
 3 files changed, 12 insertions(+), 10 deletions(-)

diff --git a/include/net/ip.h b/include/net/ip.h
index 0e5a0ba..14211ea 100644
--- a/include/net/ip.h
+++ b/include/net/ip.h
@@ -39,11 +39,12 @@ struct inet_skb_parm {
 	struct ip_options	opt;		/* Compiled IP options		*/
 	unsigned char		flags;
 
-#define IPSKB_FORWARDED		1
-#define IPSKB_XFRM_TUNNEL_SIZE	2
-#define IPSKB_XFRM_TRANSFORMED	4
-#define IPSKB_FRAG_COMPLETE	8
-#define IPSKB_REROUTED		16
+#define IPSKB_FORWARDED		BIT(0)
+#define IPSKB_XFRM_TUNNEL_SIZE	BIT(1)
+#define IPSKB_XFRM_TRANSFORMED	BIT(2)
+#define IPSKB_FRAG_COMPLETE	BIT(3)
+#define IPSKB_REROUTED		BIT(4)
+#define IPSKB_DOREDIRECT	BIT(5)
 
 	u16			frag_max_size;
 };
diff --git a/net/ipv4/ip_forward.c b/net/ipv4/ip_forward.c
index 3a83ce5..787b3c2 100644
--- a/net/ipv4/ip_forward.c
+++ b/net/ipv4/ip_forward.c
@@ -129,7 +129,8 @@ int ip_forward(struct sk_buff *skb)
 	 *	We now generate an ICMP HOST REDIRECT giving the route
 	 *	we calculated.
 	 */
-	if (rt->rt_flags&RTCF_DOREDIRECT && !opt->srr && !skb_sec_path(skb))
+	if (IPCB(skb)->flags & IPSKB_DOREDIRECT && !opt->srr &&
+	    !skb_sec_path(skb))
 		ip_rt_send_redirect(skb);
 
 	skb->priority = rt_tos2priority(iph->tos);
diff --git a/net/ipv4/route.c b/net/ipv4/route.c
index 2000110..868c829 100644
--- a/net/ipv4/route.c
+++ b/net/ipv4/route.c
@@ -1568,10 +1568,8 @@ static int __mkroute_input(struct sk_buff *skb,
 	do_cache = res->fi && !itag;
 	if (out_dev == in_dev && err && IN_DEV_TX_REDIRECTS(out_dev) &&
 	    (IN_DEV_SHARED_MEDIA(out_dev) ||
-	     inet_addr_onlink(out_dev, saddr, FIB_RES_GW(*res)))) {
-		flags |= RTCF_DOREDIRECT;
-		do_cache = false;
-	}
+	     inet_addr_onlink(out_dev, saddr, FIB_RES_GW(*res))))
+		IPCB(skb)->flags |= IPSKB_DOREDIRECT;
 
 	if (skb->protocol != htons(ETH_P_IP)) {
 		/* Not IP (i.e. ARP). Do not create route, if it is
@@ -2316,6 +2314,8 @@ static int rt_fill_info(struct net *net,  __be32 dst, __be32 src,
 	r->rtm_flags	= (rt->rt_flags & ~0xFFFF) | RTM_F_CLONED;
 	if (rt->rt_flags & RTCF_NOTIFY)
 		r->rtm_flags |= RTM_F_NOTIFY;
+	if (IPCB(skb)->flags & IPSKB_DOREDIRECT)
+		r->rtm_flags |= RTCF_DOREDIRECT;
 
 	if (nla_put_be32(skb, RTA_DST, dst))
 		goto nla_put_failure;
-- 
2.1.0

Re: [PATCH net v2] ipv4: try to cache dst_entries which would cause a redirect

[Julian Anastasov]

	Hello,

On Wed, 21 Jan 2015, Hannes Frederic Sowa wrote:

> Not caching dst_entries which cause redirects could be exploited by hosts
> on the same subnet, causing a severe DoS attack. This effect aggravated
> since commit f88649721268999 ("ipv4: fix dst race in sk_dst_get()").
> 
> Lookups causing redirects will be allocated with DST_NOCACHE set which
> will force dst_release to free them via RCU.  Unfortunately waiting for
> RCU grace period just takes too long, we can end up with >1M dst_entries
> waiting to be released and the system will run OOM. rcuos threads cannot
> catch up under high softirq load.
> 
> Attaching the flag to emit a redirect later on to the specific skb allows
> us to cache those dst_entries thus reducing the pressure on allocation
> and deallocation.
> 
> This issue was discovered by Marcelo Leitner.

	After more thinking and after checking all
ip_route_input places other issues popup :(

	Another place with non-trivial handling is
icmp_route_lookup(), only called by icmp_send(). We do
lookup and then revert it. ip_options_rcv_srr() too.
In this case we even can replace initial route (which
should be to local host, without redirect flag) with
new route (which can be with  IPSKB_DOREDIRECT).
So, for this case we do not wrongly leave some
IPSKB_DOREDIRECT flag.

	But in icmp_route_lookup() should we restore the
original IPSKB_DOREDIRECT bit when_skb_refdst is restored?
I.e. I'm not sure if some icmp_send() caller continues to
use the skb. For now I see only one place where we continue
to use skb after icmp_send: ip_rt_send_redirect(). But
it is after our check for RTCF_DOREDIRECT. Other places
free the skb.

	If we want to be pedantic, should we create some
helper functions and structure to save old state? For now
we are ok but using IPCB looks risky. For example:

struct ip_route_input_state {
	unsigned long	refdst;
	unsigned char	flags;
};

/* Save state and re-init skb for new route lookup */
static inline void
ip_route_input_state_save(struct sk_buff *skb,
			  struct ip_route_input_state *state)
{
	state->refdst = skb->_skb_refdst;
	state->flags = IPCB(skb)->flags;
	skb_dst_set(skb, NULL);
	IPCB(skb)->flags &= ~IPSKB_DOREDIRECT;
}

static inline void
ip_route_input_state_restore(struct sk_buff *skb,
			     struct ip_route_input_state *state)
{
	skb->_skb_refdst = state->refdst;
	IPCB(skb)->flags = state->flags;
}

static inline void
ip_route_input_state_drop(struct ip_route_input_state *state)
{
	refdst_drop(state->refdst);
}

>  	skb->priority = rt_tos2priority(iph->tos);
> diff --git a/net/ipv4/route.c b/net/ipv4/route.c
> index 2000110..868c829 100644
> --- a/net/ipv4/route.c
> +++ b/net/ipv4/route.c
> @@ -1568,10 +1568,8 @@ static int __mkroute_input(struct sk_buff *skb,
>  	do_cache = res->fi && !itag;
>  	if (out_dev == in_dev && err && IN_DEV_TX_REDIRECTS(out_dev) &&
>  	    (IN_DEV_SHARED_MEDIA(out_dev) ||
> -	     inet_addr_onlink(out_dev, saddr, FIB_RES_GW(*res)))) {
> -		flags |= RTCF_DOREDIRECT;
> -		do_cache = false;
> -	}
> +	     inet_addr_onlink(out_dev, saddr, FIB_RES_GW(*res))))
> +		IPCB(skb)->flags |= IPSKB_DOREDIRECT;

	Looks like accessing IPCB may not be safe for
ARP (NEIGH_CB is used) or other protocols, may be we have
to add skb->protocol == htons(ETH_P_IP) check here because
ip_route_input() can be called for different protocols.

Regards

--
Julian Anastasov <ja@ssi.bg>

Re: [PATCH net v2] ipv4: try to cache dst_entries which would cause a redirect

[Hannes Frederic Sowa]

Hi,

On Mi, 2015-01-21 at 23:26 +0200, Julian Anastasov wrote:
> On Wed, 21 Jan 2015, Hannes Frederic Sowa wrote:
> 
> > Not caching dst_entries which cause redirects could be exploited by hosts
> > on the same subnet, causing a severe DoS attack. This effect aggravated
> > since commit f88649721268999 ("ipv4: fix dst race in sk_dst_get()").
> > 
> > Lookups causing redirects will be allocated with DST_NOCACHE set which
> > will force dst_release to free them via RCU.  Unfortunately waiting for
> > RCU grace period just takes too long, we can end up with >1M dst_entries
> > waiting to be released and the system will run OOM. rcuos threads cannot
> > catch up under high softirq load.
> > 
> > Attaching the flag to emit a redirect later on to the specific skb allows
> > us to cache those dst_entries thus reducing the pressure on allocation
> > and deallocation.
> > 
> > This issue was discovered by Marcelo Leitner.
> 
> 	After more thinking and after checking all
> ip_route_input places other issues popup :(
> 
> 	Another place with non-trivial handling is
> icmp_route_lookup(), only called by icmp_send(). We do
> lookup and then revert it. ip_options_rcv_srr() too.
> In this case we even can replace initial route (which
> should be to local host, without redirect flag) with
> new route (which can be with  IPSKB_DOREDIRECT).
> So, for this case we do not wrongly leave some
> IPSKB_DOREDIRECT flag.
> 
> 	But in icmp_route_lookup() should we restore the
> original IPSKB_DOREDIRECT bit when_skb_refdst is restored?
> I.e. I'm not sure if some icmp_send() caller continues to
> use the skb. For now I see only one place where we continue
> to use skb after icmp_send: ip_rt_send_redirect(). But
> it is after our check for RTCF_DOREDIRECT. Other places
> free the skb.
> 
> 	If we want to be pedantic, should we create some
> helper functions and structure to save old state? For now
> we are ok but using IPCB looks risky. For example:

I would try to not introduce this complexity. I am currently researching
if this change does improve things:

        do_cache = res->fi && !itag;
-       if (out_dev == in_dev && err && IN_DEV_TX_REDIRECTS(out_dev) &&
-           (IN_DEV_SHARED_MEDIA(out_dev) ||
-            inet_addr_onlink(out_dev, saddr, FIB_RES_GW(*res)))) {
-               flags |= RTCF_DOREDIRECT;
-               do_cache = false;
+       if (skb->protocol == htons(ETH_P_IP)) {
+               if (out_dev == in_dev && err && IN_DEV_TX_REDIRECTS(out_dev) &&
+                   skb->protocol == htons(ETH_P_IP) &&
+                   (IN_DEV_SHARED_MEDIA(out_dev) ||
+                    inet_addr_onlink(out_dev, saddr, FIB_RES_GW(*res))))
+                       IPCB(skb)->flags |= IPSKB_DOREDIRECT;
+               else if (IPCB(skb)->flags & IPSKB_DOREDIRECT)
+                       IPCB(skb)->flags &= ~IPSKB_DOREDIRECT;
        }

So we do reset the IPSKB_DOREDIRECT flag on every lookup. This would
keep the ip_options_rcv_srr() lookup happy, as we only use the flag as
we would do before when keeping the last dst_entry.

icmp_route_lookup actually looks fine to me just because the skb will
never end up in ip_forward, thus the state of the flag does not matter.

What do you think?

The problem with NEIGHCB and IPCB is solved by the snippet above, too.

Thanks for the review,
Hannes

Re: [PATCH net v2] ipv4: try to cache dst_entries which would cause a redirect

[Julian Anastasov]

	Hello,

On Thu, 22 Jan 2015, Hannes Frederic Sowa wrote:

> I would try to not introduce this complexity. I am currently researching
> if this change does improve things:
> 
>         do_cache = res->fi && !itag;
> -       if (out_dev == in_dev && err && IN_DEV_TX_REDIRECTS(out_dev) &&
> -           (IN_DEV_SHARED_MEDIA(out_dev) ||
> -            inet_addr_onlink(out_dev, saddr, FIB_RES_GW(*res)))) {
> -               flags |= RTCF_DOREDIRECT;
> -               do_cache = false;
> +       if (skb->protocol == htons(ETH_P_IP)) {
> +               if (out_dev == in_dev && err && IN_DEV_TX_REDIRECTS(out_dev) &&
> +                   skb->protocol == htons(ETH_P_IP) &&

	Above is duplicate. Or better to remove first
and to keep this second check if flag is not cleared below...

> +                   (IN_DEV_SHARED_MEDIA(out_dev) ||
> +                    inet_addr_onlink(out_dev, saddr, FIB_RES_GW(*res))))
> +                       IPCB(skb)->flags |= IPSKB_DOREDIRECT;
> +               else if (IPCB(skb)->flags & IPSKB_DOREDIRECT)
> +                       IPCB(skb)->flags &= ~IPSKB_DOREDIRECT;

	It seems we do not need to clear the flag for
ip_options_rcv_srr purposes because ip_route_input is called
only if initial rt_type is RTN_LOCAL, so the flag should be
unset. ip_mkroute_input/__mkroute_input is called only for
forwarding.

	In ip_options_rcv_srr we have RTN_LOCAL ... [RTN_LOCAL]
and may be final RTN_UNICAST. The flag can be set and used
only for RTN_UNICAST and that is the final ip_route_input
called there. Lets keep it just with the 2nd ETH_P_IP check?

Regards

--
Julian Anastasov <ja@ssi.bg>

Re: [PATCH net v2] ipv4: try to cache dst_entries which would cause a redirect

[Hannes Frederic Sowa]

On Thu, Jan 22, 2015, at 20:57, Julian Anastasov wrote:
> 
> 	Hello,
> 
> On Thu, 22 Jan 2015, Hannes Frederic Sowa wrote:
> 
> > I would try to not introduce this complexity. I am currently researching
> > if this change does improve things:
> > 
> >         do_cache = res->fi && !itag;
> > -       if (out_dev == in_dev && err && IN_DEV_TX_REDIRECTS(out_dev) &&
> > -           (IN_DEV_SHARED_MEDIA(out_dev) ||
> > -            inet_addr_onlink(out_dev, saddr, FIB_RES_GW(*res)))) {
> > -               flags |= RTCF_DOREDIRECT;
> > -               do_cache = false;
> > +       if (skb->protocol == htons(ETH_P_IP)) {
> > +               if (out_dev == in_dev && err && IN_DEV_TX_REDIRECTS(out_dev) &&
> > +                   skb->protocol == htons(ETH_P_IP) &&
> 
> 	Above is duplicate. Or better to remove first
> and to keep this second check if flag is not cleared below...

Yes, noticed it too late.

> 
> > +                   (IN_DEV_SHARED_MEDIA(out_dev) ||
> > +                    inet_addr_onlink(out_dev, saddr, FIB_RES_GW(*res))))
> > +                       IPCB(skb)->flags |= IPSKB_DOREDIRECT;
> > +               else if (IPCB(skb)->flags & IPSKB_DOREDIRECT)
> > +                       IPCB(skb)->flags &= ~IPSKB_DOREDIRECT;
> 
> 	It seems we do not need to clear the flag for
> ip_options_rcv_srr purposes because ip_route_input is called
> only if initial rt_type is RTN_LOCAL, so the flag should be
> unset. ip_mkroute_input/__mkroute_input is called only for
> forwarding.

Yes, that aligns pretty much with how source routing should work. :)

> 	In ip_options_rcv_srr we have RTN_LOCAL ... [RTN_LOCAL]
> and may be final RTN_UNICAST. The flag can be set and used
> only for RTN_UNICAST and that is the final ip_route_input
> called there. Lets keep it just with the 2nd ETH_P_IP check?

I agree, I don't see any other complications any more. Will send patch
soon. Thanks a lot! Also please feel free to add you SOB.

Bye,
Hannes