That's the documented behavior of alloca(3):

    The alloca() function returns a pointer to the beginning of the allocated
    space.  If the allocation causes stack overflow, program behavior is
    undefined.

The whole problem can be reduced to the following minimal example:

#include <alloca.h>
#include <stdlib.h>

int main()
{
    long i;
    for (i = 1; i; i <<=1) {
        printf("0x%x\n", i);
        alloca(i);
    }
    return 0;
}

I propose to solve it like this:

sed -i 's|#define HAVE_ALLOCA 1|/* #undef HAVE_ALLOCA */|' lynx_cfg.h

On the other hand, it can introduce some memory leaks...

(In reply to comment #2)
> The whole problem can be reduced to the following minimal example:

Oops, a better one:

#include <alloca.h>
#include <stdio.h>

int main()
{
    long i;
    for (i = 1; i; i <<=1) {
        printf("0x%lx\n", i);
        alloca(i);
    }
    return 0;
}

Created attachment 424977 [details]
upstream patch to correct the issue

Patch provided by upstream.  This sets the maximum URI size to 8192, using a limit-check to stop page loading.

(In reply to comment #2)
> That's the documented behavior of alloca(3):

Right, this alloca behaviour is documented quite well know and yet source of many issues.

> I propose to solve it like this:
> 
> sed -i 's|#define HAVE_ALLOCA 1|/* #undef HAVE_ALLOCA */|' lynx_cfg.h

We can probably use more confined fix that only applies to HTParse.c's LYalloca define.

> On the other hand, it can introduce some memory leaks...

Probably not in HTParse.c, that defines and uses LYfree to, which expands to empty block when using alloca (and free() call when using standard malloc()).

It's probably going to have a performance impact that the use of alloca was supposed to address.  Possible solution to that may be use of some threshold.  If requested size is under that limit, it's ok to use alloca, otherwise use malloc.  glibc uses that, search for __libc_use_alloca and __MAX_ALLOCA_CUTOFF (currently 65536).

(In reply to comment #6)
> Created an attachment (id=424977) [details]
> upstream patch to correct the issue
> 
> Patch provided by upstream.  This sets the maximum URI size to 8192, using a
> limit-check to stop page loading.    

It seems to leave integer overflow issue not addressed.

Regarding integer overflow, I suppose you mean something
like
    if (need > MAX_URI_SIZE ||
        (int) need < len1 ||
        (int) need < len2)

and
        if (need > MAX_URI_SIZE ||
            (int) need < (p - aName) ||
            (int) need < strlen(p)) {

For anything more sophisticated, I would expect it to be
necessary to filter out long strings earlier in parsing,
or to change datatypes, etc.  (I've been picking away at
that, but don't have a quick fix).

gcc reminded me that it should be using casts, e.g.,

    if (need > (size_t) max_uri_size ||
        (int) need < (int) len1 ||
        (int) need < (int) len2)

and

        if (need > (size_t) max_uri_size ||
            (int) need < (int) (p - aName) ||
            (int) need < (int) strlen(p)) {

I was more thinking of following "standard" checks:

  if (len1 > SIZE_MAX - MIN_PARSE - len2  ||
      len > (SIZE_MAX - len1 - len2) / 2) {

You can use lower limit than SIZE_MAX (such as MAX_URI_SIZE used in the patch) and do an extra check that len2 does not exceed it.

HTParseAnchor should not need integer overflow check assuming aName is properly terminated, as you can't need more than what's already used for aName.

Using SIZE_MAX as a limit won't help much with the stack overflow.

I'm working to close out my changes for lynx 2.8.8dev.4 (which
includes the configurable change), and to put out a 2.8.8rel.2
patch (with just the hardcoded change).  I'll attach a copy of
the latter, since it is likely to be useful for backporting.

Created attachment 425508 [details]
fix for reported issue in 2.8.8rel (unreleased).

(In reply to comment #11)
> Using SIZE_MAX as a limit won't help much with the stack overflow.    

Sure, I was more thinking of a solution as mentioned in comment #7 - have a check to avoid integer overflows and independent check to decide whether to use malloc or alloca to allocate memory.

Is MAX_URI_SIZE the right bound for need too?  Such limit transitively implies that len1 and len2 are both less than MAX_URI_SIZE/3.

MAX_URI_SIZE at 8kb is probably big enough.  The largest value
I found above that was a comment about a 16k limit on fragment
size.  But in the development version, I made it configurable.

Since it is a small value, then the patch in #13 should be
sufficient (for the hardcoded limit) since both len1 and
len2 are less than the limit as well.  Checking all three
values merely ensures that there would not be an overflow
due to one of the components of the expression.

I released a 2.8.7rel.2 and 2.8.8dev.4 this morning, will
see if additional refinement is needed...

Using the public reproducer, I can't get Red Hat Enterprise Linux 3 to crash (2.8.5dev.7) but RHEL4 does crash (2.8.5dev.16) so it looks like something may have regressed somewhere between those two versions.

Perhaps it is in 2.8.5dev.13:

* improve performance of HTParse() for very long strings -LP

or in 2.8.5dev.10:

* in HTParse(), use single alloca instead of three malloc/free pairs -LP

The latter.  That's the first use of alloca() in that file.
It's been a while though: 2002-11-11 (2.8.5dev.10)

Ok, good to know, thank you.

For all of these issues, there is no possibility of arbitrary code execution, correct?  Just a crash?  (I'm not familiar with alloca() at all, so I'm not sure if this is a straight termination when encountering the overflowed buffer, or if it possible to do something nastier here).

It might be possible.  Using valgrind, I see several (perhaps a
hundred) incorrect uses of memory before it dies.  The manpage
for alloca() states that its behavior on stack overflow is
undefined.  Two scenarios come to mind: stack overflow which
would produce an illegal address reference, and stack overflow
which gives a pointer to a not-large-enough buffer.  I'm not
seeing the former.  There's no stack guard, so the program can
write onto the return-address area of the stack ("above" the
data).  Presumably someone could design a url that does some
damage (noting that the bytes used are limited by the character
set conventions).

The point at which it dies is in fact right on the alloca() call.
But the incorrect uses of memory before that point all go away
when the alloca() use is repaired.

(In reply to comment #18)
> Using the public reproducer, I can't get Red Hat Enterprise Linux 3 to crash
> (2.8.5dev.7) but RHEL4 does crash (2.8.5dev.16) so it looks like something may
> have regressed somewhere between those two versions.

As Thomas pointed out, version in EL3 does not use alloca, which makes that vector not applicable to it.

Integer overflow issue as affecting EL4+ is not applicable to EL3 either, as it allocates less memory:

  len = strlen(aName) + strlen(relatedName) + 10;

This is non-issue on 32bits, it may be issue on 64bits.  It requires larger input file and more memory, and there may be other constraint elsewhere that may make integer overflow impossible on 64bits too.

(In reply to comment #20)
> For all of these issues, there is no possibility of arbitrary code execution,
> correct?  Just a crash?  (I'm not familiar with alloca() at all, so I'm not
> sure if this is a straight termination when encountering the overflowed
> buffer, or if it possible to do something nastier here).    

I don't remember any case where similar alloca problem was demonstrated to be likely to be used to execute code in cases where alloca is used as:

   dst = alloca(strlen(src));
   strcpy(dst, src);

To make alloca attack useful, you'll need to use it to "allocate" enough memory to bridge unmapped memory gap between heap and stack.  If alloca size is based on the length of some other data already in memory and you fill the buffer right after allocating it, you're quite likely to touch that unmapped memory and crash.

Bad alloca use can be exploited if attacker can control size without need to provide too much data and can make application to only write to first few bytes of the allocated buffer.

It's even harder that actually. The function in question has to do the huge alloca, write some bits to an arbitrary location in memory, then return from the function. If the stack is too large, you can't make any function calls until the current frame returns fixing the stack pointer to something sane.

The strcpy call will fail not because it's touching memory, but because the current stack pointer is something silly.

I'd call this not a security flaw in the context of lynx. It's certainly a bug, but if you're a user, just don't go back to the page in question.

(In reply to comment #25)
> It's even harder that actually. The function in question has to do the huge
> alloca, write some bits to an arbitrary location in memory, then return from
> the function. If the stack is too large, you can't make any function calls
> until the current frame returns fixing the stack pointer to something sane.
> 
> The strcpy call will fail not because it's touching memory, but because the
> current stack pointer is something silly.

It does not have to fail.  alloca changes stack pointer.  If alloca size is sufficient, stack pointer may point to heap memory and hence new stack frame will be created on heap and more functions can still be called.

Statement:

This issue affects the versions of lynx as shipped with Red Hat Enterprise Linux 3, 4, 5 and 6. Red Hat Product Security has rated this issue as having Moderate security impact. A future update may address this issue. For additional information, refer to the Issue Severity Classification: https://access.redhat.com/security/updates/classification/.