libutp

libutp copied to clipboard

It appears that the resends[] buffer in selective_ack() is either mis-sized or not appropriately constrained. It is hard-coded to a stack of 32 entries, but no check is made that we won't run past this limit. The code simply relies on the declared size of the selective_ack in the packet itself (ugh)

For instance:

// Resend segments
// if count is less than our re-send limit, we haven't seen enough
// acked packets in front of this one to warrant a re-send.
// if count == 0, we're still going through the tail of zeroes
if (((v - fast_resend_seq_nr) & ACK_NR_MASK) <= OUTGOING_BUFFER_MAX_SIZE &&
    count >= DUPLICATE_ACKS_BEFORE_RESEND &&
    duplicate_ack < DUPLICATE_ACKS_BEFORE_RESEND) {
    resends[nr++] = v;
    LOG_UTPV("0x%08x: no ack for %u", this, v);
}

This is tripped regularly in large windows.

For what it's worth: there is no check for proper selack header length in UTP_ProcessIncoming(). For selective_ack, per the published protocol, it must be a non-zero multiple of 4.

Here is a test patch being used by some transmission users: https://trac.transmissionbt.com/attachment/ticket/5002/RESENDS_MAX_COUNT.diff https://trac.transmissionbt.com/raw-attachment/ticket/5002/RESENDS_MAX_COUNT.diff

and associated ideas: https://trac.transmissionbt.com/ticket/5002#comment:25

There was another patch, developed by BitTorrent, which I'd like to confirm fixes the issue well enough for you:

https://gist.github.com/0a3b9bdc9f3a81dda96f

Let me know?

Why would this ever happen?

if (nr >= MAX_EACK)

As opposed to

nr==MAX_EACK

There is one edge case where nr can still be incremented and remains unchecked, just below this.

Also, this patch doesn't compile. I assume you mean memmove() not memmov(), and the enum{} block has a typo.

I think you need (void *)resends cast in the memmove() arguments. Compiler will otherwise do array math. Conversely: memmove(resends, resends+MAX_EACK/2, MAX_EACK/2*sizeof(resends[0])

If you put this after the resend[nr++] assignment, then you can avoid a duplicative check after this loop completes.

I see a couple of problems with proposed BitTorrent patch. The biggest issue is brought up by reardonia:

There is one edge case where nr can still be incremented and remains unchecked, just below this.

this we can still get a crash with the BitTorrent patch.

In my patch https://trac.transmissionbt.com/attachment/ticket/5002/RESENDS_MAX_COUNT.diff I take care of this as so:

    if (((base - 1 - fast_resend_seq_nr) & ACK_NR_MASK) < 256 &&
        count >= DUPLICATE_ACKS_BEFORE_RESEND &&
        duplicate_ack < DUPLICATE_ACKS_BEFORE_RESEND &&
        ((nr + 1) < RESENDS_MAX_COUNT)) {
        // obey the RESENDS_MAX_COUNT limit SRS 11-30-2012
        // if we get enough duplicate acks to start
        // resending, the first packet we should resend
        // is base-1
        resends[nr++] = base - 1;
    } else {
        LOG_UTPV("0x%08x: not resending %u count:%d dup_ack:%u fast_resend_seq_nr:%u nr:%d",
                 this, base - 1, count, duplicate_ack, fast_resend_seq_nr, nr);

My compiler also had issues with: enum { MAX_EACK = 128; }

enum { MAX_EACK = 128 }; eliminated this.

and memmov needed to changed to memmove

I see some sloppy work with BitTorrent patch and don't see it could have been tested as it stands.

I do believe I have a couple more coding logic issues with BitTorrent's patch but I won't have the time right now to describe them precisely.

My patch is testing out just fine with a variety of RESENDS_MAX_COUNT values.

I'll get back on all this next week in a timely fashion.

Typos and array math were fixed in subsequent revisions which I failed to gather in that patch. I've updated the diff:

https://gist.github.com/ef69847aaa2482f14ddb

I've run it for the last 12hours and it seems fine.

patch to fix without throwing away data and whatever array size you want.

https://gist.github.com/4199256#file_resends_max_count_v2.diff

next I'll explain...

I don't see why to throw-away half the array at a time, especially when we don't really know if we'll fill it back up again. There are lots of reasons we might not fill it up again and so why waste the data like this. We might delete half the data to gain nothing. It is very fast and easy to just throw away a single resends[] element at a time, still keep the most recent elements on the top of the array/stack and not have to use memmove. We can use an array half the size of the BitTorrent patch and have the same amount. My above patch demonstrates this along with fixing the couple of other problems included in the updated BitTorrent patch.

The BitTorrent patch does fix the issue along with the other problems, even though not the best implementation in my opinion.

just a note: my old test patch has a bug where the very last resends[] data might be unnecessarily not saved/used.

Actually, aren't resends limited to 4 in the code?

        // Re-send max 4 packets.
        if (++i >= 4) break;

Why keep track of more than this? Why not a ring-buffer with 4 entries? This function is just horrible code...

This last patch from cfpp2p seems all wrong. I don't think you've read the original code & logic properly. First, any check of "nr>=MAX" misses the point. If you somehow are already "greater-than", then you have a big problem. It can't happen. So the check should simply be "equal-to". Same with the second check below.

The whole top/bottom stuff is overkill. Just keep it one below current, increment and wrap. ie, use a ring buffer. But really, given the 4 packet limit, all of this just seems like overwrought code.

And I still can't quite parse the fast_resend vs. regular resend logic, or the intentions of BEP29 in this situation.

of course I have read the code properly, as far as "nr>=MAX" I was just keeping with the developer's (ghazel) style as per the developers submitted BitTorrent patches i.e. if (nr >= MAX_EACK

my intent is to share ideas so that the developers can gain what information they need for a final fix to the problem as they deem fit.

whether or not the function is horrible code or not is a matter of opinion and I'm sure the libutp developers would be happy to look at patches that might clean it up. I'm finding the code an enjoyable challenge to pick apart.

I've tested the BitTorrent patch as well as my own patches and found no noticeable differences in the functionality of uTP between them. I'm more than happy to test further submitted patches by anyone.

I don't think bickering will solve the problem or inspire the developers. Lets hope that the information submitted here facilitates the libutp developers to a speedy solution.

The greater-than check is an issue of (incorrect) logic, not style. More importantly, it leads to easy misinterpretation of the intent.

Anyway, I'm just thinking aloud, which I think is the healthiest way to improve code, ie code reviews. So: why do we run the whole list of packet acks if we only care about the oldest 4?

Could we confirm that this was fixed in 365254427e5358a0c390aa5a60df5f449b9c0f00?

Also probably worth linking to the CVE for this vulnerability: http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2012-6129

Could we confirm that this was fixed in 3652544?

yes, fixed