Reliable segments that overlap with previous segments can result in an invalid reliable segment gap map

[caleb-krause]

Reliable segments that overlap with previous segments can result in an invalid reliable segment gap map. I don't think a benign client will send these kind of segments.

The relevant code is here:

GameNetworkingSockets/src/steamnetworkingsockets/clientlib/steamnetworkingsockets_snp.cpp

Lines 3515 to 3598 in 4fbfe83

	// Check if this filled in one or more gaps (or made a hole in the middle!)
	if ( !lane.m_mapReliableStreamGaps.empty() )
	{
	auto gapFilled = lane.m_mapReliableStreamGaps.upper_bound( nSegBegin );
	if ( gapFilled != lane.m_mapReliableStreamGaps.begin() )
	{
	--gapFilled;
	Assert( gapFilled->first < gapFilled->second ); // Make sure we don't have degenerate/invalid gaps in our table
	Assert( gapFilled->first <= nSegBegin ); // Make sure we located the gap we think we located
	if ( gapFilled->second > nSegBegin ) // gap is not entirely before this segment
	{
	do {
	// Common case where we fill exactly at the start
	if ( nSegBegin == gapFilled->first )
	{
	if ( nSegEnd < gapFilled->second )
	{
	// We filled the first bit of the gap. Chop off the front bit that we filled.
	// We cast away const here because we know that we aren't violating the ordering constraints
	const_cast<int64&>( gapFilled->first ) = nSegEnd;
	break;
	}
	// Filled the whole gap.
	// Erase, and move forward in case this also fills more gaps
	// !SPEED! Since exactly filing the gap should be common, we might
	// check specifically for that case and early out here.
	gapFilled = lane.m_mapReliableStreamGaps.erase( gapFilled );
	}
	else if ( nSegEnd >= gapFilled->second )
	{
	// Chop off the end of the gap
	Assert( nSegBegin < gapFilled->second );
	gapFilled->second = nSegBegin;
	// And maybe subsequent gaps!
	++gapFilled;
	}
	else
	{
	// We are fragmenting.
	Assert( nSegBegin > gapFilled->first );
	Assert( nSegEnd < gapFilled->second );
	// Protect against malicious sender. A good sender will
	// fill the gaps in stream position order and not fragment
	// like this
	if ( len( lane.m_mapReliableStreamGaps ) >= k_nMaxReliableStreamGaps_Fragment )
	{
	// Stop processing the packet, and don't ack it
	SpewWarningRateLimited( usecNow, "[%s] decode pkt %lld abort. Reliable stream already has %d fragments, first is [%lld,%lld), last is [%lld,%lld). We don't want to fragment [%lld,%lld) with new segment [%lld,%lld)\n",
	GetDescription(),
	(long long)nPktNum,
	len( lane.m_mapReliableStreamGaps ),
	(long long)lane.m_mapReliableStreamGaps.begin()->first, (long long)lane.m_mapReliableStreamGaps.begin()->second,
	(long long)lane.m_mapReliableStreamGaps.rbegin()->first, (long long)lane.m_mapReliableStreamGaps.rbegin()->second,
	(long long)gapFilled->first, (long long)gapFilled->second,
	(long long)nSegBegin, (long long)nSegEnd
	);
	return false; // DO NOT ACK THIS PACKET
	}
	// Save bounds of the right side
	int64 nRightHandBegin = nSegEnd;
	int64 nRightHandEnd = gapFilled->second;
	// Truncate the left side
	gapFilled->second = nSegBegin;
	// Add the right hand gap
	lane.m_mapReliableStreamGaps[ nRightHandBegin ] = nRightHandEnd;
	// And we know that we cannot possible have covered any more gaps
	break;
	}
	// In some rare cases we might fill more than one gap with a single segment.
	// So keep searching forward.
	} while ( gapFilled != lane.m_mapReliableStreamGaps.end() && gapFilled->first < nSegEnd );
	}
	}
	}
	}

Example 1

Suppose the gap map has two entries: {1: 25} and {75: 100} and segment [10, 100) arrives. This segment overlaps with a gap so we enter the do-while loop with gapFilled pointing to {1: 25}.

Loop Iteration 1:
We enter the else if branch, where we modify the {1: 25} gap to be {1: 10}. We increment gapFilled so it points to {75: 100}

Loop Iteration 2:
We again enter the else if statement. We set the value of gapFilled to be the beginning of the segment. This results in the {75: 100} gap becoming a {75: 10} gap. This violates the assumption that the end of a gap should always be after the start of the gap! We exit the loop after this iteration.

Example 2

Again suppose the gap map has two entries: {1: 25} and {75: 100} and segment [10, 90) arrives. This segment overlaps with a gap so we enter the do-while loop with gapFilled pointing to {1: 25}.

Loop Iteration 1:
We enter the else if branch, where we modify the {1: 25} gap to be {1: 10}. We increment gapFilled so it points to {75: 100}

Loop Iteration 2:
We enter the else branch. We trigger the first assert as the beginning of the segment is less than the start of the gap. In release builds, this assert doesn't do anything. We set the value of gapFilled to be the beginning of the segment. This results in the {75: 100} gap becoming a {75: 10} gap. This violates the assumption that the end of a gap should always be after the start of the gap! We exit the loop after this iteration.

Example 3

Suppose the gap map has entry {25: 75} and segment [1, 100) arrives. We do not enter the do-while loop as gapFilled = lane.m_mapReliableStreamGaps.upper_bound( nSegBegin ) returns the {25: 75} gap, which is also the map's begin(), meaning we never enter the if ( gapFilled != lane.m_mapReliableStreamGaps.begin() ) branch that contains the loop. So even though this arriving segment fills in the {25: 75} gap, the gap map is not updated.

Effects

In all three examples, the effect is that the GNS library will provide less reliable bytes to the application than it could have. In examples 1 and 2, the library will not provide bytes 75 and on to the application because it thinks there is a gap starting at byte 75, even though in both examples the sender did send byte 75. In example 3, the library will similarly not provide bytes 25 and on to the application because it thinks the gap from byte 25 on still exists. In all cases, the sender could send segments that will cause these gaps to be removed from the gap map. However, I don't think these gaps will trigger relevant NACKs as the receiver did correctly receive the packets with the segments containing the bytes that the gap map thinks is missing, so the sender would have to manually send corrective segments instead of relying on NACKs.

However, I do not think benign clients using the GNS library will ever send reliable segments that overlap like this. And the worse thing a malicious client can do with this bug is DoS themselves.

Possible fixes

• Edit SNP_ReceiveReliableSegment so that it more robustly fills in gaps.
• Check that the sender is sending reliable segments in the manner that later code assumes it does (so in this case enforcing that segments don't overlap).
• Change nothing. I don't think benign clients will trigger this issue and I can't see a way a malicious client could use this to launch any kind of attack. More robust handling of gaps might slow the code down.