oss-security - alloca in inline functions can be dangerous

Follow @Openwall on Twitter for new release announcements and other news

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-Id: <a18696795bb4b91a@frisell.zx2c4.com>
Date: Mon, 10 Apr 2017 16:36:24 +0200
From: "Jason A. Donenfeld" <Jason@...c4.com>
To: oss-security <oss-security@...ts.openwall.com>
Subject: alloca in inline functions can be dangerous

Hey folks,

I'm not sure this is the right mailing list to discuss this matter, but
hopefully it finds an audience here. I was debugging some code recently,
when I found a very nasty interaction between alloca and inline functions.
Observe the following block:

static inline void process_widget(struct widget *widget,
				  unsigned int  fcount)
{
	struct fragment fragments[fcount];
	widgets_to_fragments(fragments, widget);
	process_fragments(fragments);
}

static void iterate_widgets(struct widgetlist *widgetlist)
{
	struct widget *widget;
	unsigned int fcount;

	for (widget = widgetlist->first; widget; widget = widget->next) {
		fcount = widget_get_frags_required(widget);
		if (fcount > 256)
			continue;
		process_widget(widget, fcount);
	}
}

This seems pretty benign. However, let's look at two transformations that
gcc makes. First the VLA is changed to use alloca:

static inline void process_widget(struct widget *widget,
				  unsigned int fcount)
{
	struct fragment *fragments = __builtin_alloca(fcount);
	widgets_to_fragments(fragments, widget);
}

Next, that block is inlined:

static void iterate_widgets(struct widgetlist *widgetlist)
{
	struct fragment *fragments;
	struct widget *widget;
	unsigned int fcount;

	for (widget = widgetlist->first; widget; widget = widget->next) {
		fcount = widget_get_frags_required(widget);
		if (fcount > 256)
			continue;

		fragments = __builtin_alloca(fcount);
		widgets_to_fragments(fragments, widget);
		process_fragments(fragments);
	}
}

Uh oh speghettio: now the vulnerability becomes clear. Alloca only gives
back its stack at the end of the function, not the end of the block. Since
process_widget was inlined, we now keep calling alloca for every widget in
the widgetlist. Problemo! A stack overflow is imminant, depending on the
size of widgetlist.

I briefly searched for some information about this type of vulnerability
on the internet, and couldn't find anything. At best, I found somebody on
a gcc list saying that gcc wouldn't inline functions that use alloca. But
now I see that this is clearly not true.

So now the standard advice of "don't use VLAs or alloca in loops!" now
extends to "don't use VLAs or alloca in loops or inline functions that
might be called inside loops."

It seems like it would be prudent for gcc to either issue a warning when
alloca is used in an inline function called from inside a loop, or simply
refuse to inline those function calls (similar to what it does if you ever
try to take the address of an inline function).

I'm interested if anybody else has encountered this behavior or has any
thoughts about it.

Thanks,
Jason

Please check out the Open Source Software Security Wiki, which is counterpart to this mailing list.

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.