Abandon reassembly of a packet if fragments overlap

However, receiving duplicated fragments will not cause reassembly to
fail. This is what Linux does too:
https://github.com/torvalds/linux/blob/38525c6/net/ipv4/inet_fragment.c#L355

PiperOrigin-RevId: 345309546

5 files changed, 276 insertions, 116 deletions

diff --git a/pkg/tcpip/network/fragmentation/fragmentation.go b/pkg/tcpip/network/fragmentation/fragmentation.go
index c75ca7d71..d31296a41 100644
--- a/pkg/tcpip/network/fragmentation/fragmentation.go
+++ b/pkg/tcpip/network/fragmentation/fragmentation.go
@@ -46,9 +46,13 @@ const (
 )
 
 var (
-	// ErrInvalidArgs indicates to the caller that that an invalid argument was
+	// ErrInvalidArgs indicates to the caller that an invalid argument was
 	// provided.
 	ErrInvalidArgs = errors.New("invalid args")
+
+	// ErrFragmentOverlap indicates that, during reassembly, a fragment overlaps
+	// with another one.
+	ErrFragmentOverlap = errors.New("overlapping fragments")
 )
 
 // FragmentID is the identifier for a fragment.
diff --git a/pkg/tcpip/network/fragmentation/reassembler.go b/pkg/tcpip/network/fragmentation/reassembler.go
index 19f4920b3..04072d966 100644
--- a/pkg/tcpip/network/fragmentation/reassembler.go
+++ b/pkg/tcpip/network/fragmentation/reassembler.go
@@ -26,9 +26,9 @@ import (
 )
 
 type hole struct {
-	first   uint16
-	last    uint16
-	deleted bool
+	first  uint16
+	last   uint16
+	filled bool
 }
 
 type reassembler struct {
@@ -38,7 +38,7 @@ type reassembler struct {
 	proto        uint8
 	mu           sync.Mutex
 	holes        []hole
-	deleted      int
+	filled       int
 	heap         fragHeap
 	done         bool
 	creationTime int64
@@ -53,44 +53,86 @@ func newReassembler(id FragmentID, clock tcpip.Clock) *reassembler {
 		creationTime: clock.NowMonotonic(),
 	}
 	r.holes = append(r.holes, hole{
-		first:   0,
-		last:    math.MaxUint16,
-		deleted: false})
+		first:  0,
+		last:   math.MaxUint16,
+		filled: false,
+	})
 	return r
 }
 
-// updateHoles updates the list of holes for an incoming fragment and
-// returns true iff the fragment filled at least part of an existing hole.
-func (r *reassembler) updateHoles(first, last uint16, more bool) bool {
-	used := false
+// updateHoles updates the list of holes for an incoming fragment. It returns
+// true if the fragment fits, it is not a duplicate and it does not overlap with
+// another fragment.
+//
+// For IPv6, overlaps with an existing fragment are explicitly forbidden by
+// RFC 8200 section 4.5:
+//   If any of the fragments being reassembled overlap with any other fragments
+//   being reassembled for the same packet, reassembly of that packet must be
+//   abandoned and all the fragments that have been received for that packet
+//   must be discarded, and no ICMP error messages should be sent.
+//
+// It is not explicitly forbidden for IPv4, but to keep parity with Linux we
+// disallow it as well:
+// https://github.com/torvalds/linux/blob/38525c6/net/ipv4/inet_fragment.c#L349
+func (r *reassembler) updateHoles(first, last uint16, more bool) (bool, error) {
 	for i := range r.holes {
-		if r.holes[i].deleted || first > r.holes[i].last || last < r.holes[i].first {
+		currentHole := &r.holes[i]
+
+		if currentHole.filled || last < currentHole.first || currentHole.last < first {
 			continue
 		}
-		used = true
-		r.deleted++
-		r.holes[i].deleted = true
-		if first > r.holes[i].first {
-			r.holes = append(r.holes, hole{r.holes[i].first, first - 1, false})
+
+		if first < currentHole.first || currentHole.last < last {
+			// Incoming fragment only partially fits in the free hole.
+			return false, ErrFragmentOverlap
+		}
+
+		r.filled++
+		if first > currentHole.first {
+			r.holes = append(r.holes, hole{
+				first:  currentHole.first,
+				last:   first - 1,
+				filled: false,
+			})
+		}
+		if last < currentHole.last && more {
+			r.holes = append(r.holes, hole{
+				first:  last + 1,
+				last:   currentHole.last,
+				filled: false,
+			})
 		}
-		if last < r.holes[i].last && more {
-			r.holes = append(r.holes, hole{last + 1, r.holes[i].last, false})
+		// Update the current hole to precisely match the incoming fragment.
+		r.holes[i] = hole{
+			first:  first,
+			last:   last,
+			filled: true,
 		}
+		return true, nil
 	}
-	return used
+
+	// Incoming fragment is a duplicate/subset, or its offset comes after the end
+	// of the reassembled payload.
+	return false, nil
 }
 
 func (r *reassembler) process(first, last uint16, more bool, proto uint8, pkt *stack.PacketBuffer) (buffer.VectorisedView, uint8, bool, int, error) {
 	r.mu.Lock()
 	defer r.mu.Unlock()
-	consumed := 0
 	if r.done {
 		// A concurrent goroutine might have already reassembled
 		// the packet and emptied the heap while this goroutine
 		// was waiting on the mutex. We don't have to do anything in this case.
-		return buffer.VectorisedView{}, 0, false, consumed, nil
+		return buffer.VectorisedView{}, 0, false, 0, nil
 	}
-	if r.updateHoles(first, last, more) {
+
+	used, err := r.updateHoles(first, last, more)
+	if err != nil {
+		return buffer.VectorisedView{}, 0, false, 0, fmt.Errorf("fragment reassembly failed: %w", err)
+	}
+
+	var consumed int
+	if used {
 		// For IPv6, it is possible to have different Protocol values between
 		// fragments of a packet (because, unlike IPv4, the Protocol is not used to
 		// identify a fragment). In this case, only the Protocol of the first
@@ -109,13 +151,14 @@ func (r *reassembler) process(first, last uint16, more bool, proto uint8, pkt *s
 		consumed = vv.Size()
 		r.size += consumed
 	}
-	// Check if all the holes have been deleted and we are ready to reassamble.
-	if r.deleted < len(r.holes) {
+
+	// Check if all the holes have been filled and we are ready to reassemble.
+	if r.filled < len(r.holes) {
 		return buffer.VectorisedView{}, 0, false, consumed, nil
 	}
 	res, err := r.heap.reassemble()
 	if err != nil {
-		return buffer.VectorisedView{}, 0, false, consumed, fmt.Errorf("fragment reassembly failed: %w", err)
+		return buffer.VectorisedView{}, 0, false, 0, fmt.Errorf("fragment reassembly failed: %w", err)
 	}
 	return res, r.proto, true, consumed, nil
 }
diff --git a/pkg/tcpip/network/fragmentation/reassembler_test.go b/pkg/tcpip/network/fragmentation/reassembler_test.go
index a0a04a027..cee3063b1 100644
--- a/pkg/tcpip/network/fragmentation/reassembler_test.go
+++ b/pkg/tcpip/network/fragmentation/reassembler_test.go
@@ -16,92 +16,124 @@ package fragmentation
 
 import (
 	"math"
-	"reflect"
 	"testing"
 
+	"github.com/google/go-cmp/cmp"
 	"gvisor.dev/gvisor/pkg/tcpip/faketime"
 )
 
-type updateHolesInput struct {
-	first uint16
-	last  uint16
-	more  bool
+type updateHolesParams struct {
+	first     uint16
+	last      uint16
+	more      bool
+	wantUsed  bool
+	wantError error
 }
 
-var holesTestCases = []struct {
-	comment string
-	in      []updateHolesInput
-	want    []hole
-}{
-	{
-		comment: "No fragments. Expected holes: {[0 -> inf]}.",
-		in:      []updateHolesInput{},
-		want:    []hole{{first: 0, last: math.MaxUint16, deleted: false}},
-	},
-	{
-		comment: "One fragment at beginning. Expected holes: {[2, inf]}.",
-		in:      []updateHolesInput{{first: 0, last: 1, more: true}},
-		want: []hole{
-			{first: 0, last: math.MaxUint16, deleted: true},
-			{first: 2, last: math.MaxUint16, deleted: false},
+func TestUpdateHoles(t *testing.T) {
+	var tests = []struct {
+		name   string
+		params []updateHolesParams
+		want   []hole
+	}{
+		{
+			name:   "No fragments",
+			params: nil,
+			want:   []hole{{first: 0, last: math.MaxUint16, filled: false}},
 		},
-	},
-	{
-		comment: "One fragment in the middle. Expected holes: {[0, 0], [3, inf]}.",
-		in:      []updateHolesInput{{first: 1, last: 2, more: true}},
-		want: []hole{
-			{first: 0, last: math.MaxUint16, deleted: true},
-			{first: 0, last: 0, deleted: false},
-			{first: 3, last: math.MaxUint16, deleted: false},
+		{
+			name:   "One fragment at beginning",
+			params: []updateHolesParams{{first: 0, last: 1, more: true, wantUsed: true, wantError: nil}},
+			want: []hole{
+				{first: 0, last: 1, filled: true},
+				{first: 2, last: math.MaxUint16, filled: false},
+			},
 		},
-	},
-	{
-		comment: "One fragment at the end. Expected holes: {[0, 0]}.",
-		in:      []updateHolesInput{{first: 1, last: 2, more: false}},
-		want: []hole{
-			{first: 0, last: math.MaxUint16, deleted: true},
-			{first: 0, last: 0, deleted: false},
+		{
+			name:   "One fragment in the middle",
+			params: []updateHolesParams{{first: 1, last: 2, more: true, wantUsed: true, wantError: nil}},
+			want: []hole{
+				{first: 1, last: 2, filled: true},
+				{first: 0, last: 0, filled: false},
+				{first: 3, last: math.MaxUint16, filled: false},
+			},
 		},
-	},
-	{
-		comment: "One fragment completing a packet. Expected holes: {}.",
-		in:      []updateHolesInput{{first: 0, last: 1, more: false}},
-		want: []hole{
-			{first: 0, last: math.MaxUint16, deleted: true},
+		{
+			name:   "One fragment at the end",
+			params: []updateHolesParams{{first: 1, last: 2, more: false, wantUsed: true, wantError: nil}},
+			want: []hole{
+				{first: 1, last: 2, filled: true},
+				{first: 0, last: 0, filled: false},
+			},
 		},
-	},
-	{
-		comment: "Two non-overlapping fragments completing a packet. Expected holes: {}.",
-		in: []updateHolesInput{
-			{first: 0, last: 1, more: true},
-			{first: 2, last: 3, more: false},
+		{
+			name:   "One fragment completing a packet",
+			params: []updateHolesParams{{first: 0, last: 1, more: false, wantUsed: true, wantError: nil}},
+			want: []hole{
+				{first: 0, last: 1, filled: true},
+			},
 		},
-		want: []hole{
-			{first: 0, last: math.MaxUint16, deleted: true},
-			{first: 2, last: math.MaxUint16, deleted: true},
+		{
+			name: "Two fragments completing a packet",
+			params: []updateHolesParams{
+				{first: 0, last: 1, more: true, wantUsed: true, wantError: nil},
+				{first: 2, last: 3, more: false, wantUsed: true, wantError: nil},
+			},
+			want: []hole{
+				{first: 0, last: 1, filled: true},
+				{first: 2, last: 3, filled: true},
+			},
 		},
-	},
-	{
-		comment: "Two overlapping fragments completing a packet. Expected holes: {}.",
-		in: []updateHolesInput{
-			{first: 0, last: 2, more: true},
-			{first: 2, last: 3, more: false},
+		{
+			name: "Two fragments completing a packet with a duplicate",
+			params: []updateHolesParams{
+				{first: 0, last: 1, more: true, wantUsed: true, wantError: nil},
+				{first: 0, last: 1, more: true, wantUsed: false, wantError: nil},
+				{first: 2, last: 3, more: false, wantUsed: true, wantError: nil},
+			},
+			want: []hole{
+				{first: 0, last: 1, filled: true},
+				{first: 2, last: 3, filled: true},
+			},
 		},
-		want: []hole{
-			{first: 0, last: math.MaxUint16, deleted: true},
-			{first: 3, last: math.MaxUint16, deleted: true},
+		{
+			name: "Two overlapping fragments",
+			params: []updateHolesParams{
+				{first: 0, last: 10, more: true, wantUsed: true, wantError: nil},
+				{first: 5, last: 15, more: false, wantUsed: false, wantError: ErrFragmentOverlap},
+				{first: 11, last: 15, more: false, wantUsed: true, wantError: nil},
+			},
+			want: []hole{
+				{first: 0, last: 10, filled: true},
+				{first: 11, last: 15, filled: true},
+			},
 		},
-	},
-}
+		{
+			name: "Out of bounds fragment",
+			params: []updateHolesParams{
+				{first: 0, last: 10, more: true, wantUsed: true, wantError: nil},
+				{first: 11, last: 15, more: false, wantUsed: true, wantError: nil},
+				{first: 16, last: 20, more: false, wantUsed: false, wantError: nil},
+			},
+			want: []hole{
+				{first: 0, last: 10, filled: true},
+				{first: 11, last: 15, filled: true},
+			},
+		},
+	}
 
-func TestUpdateHoles(t *testing.T) {
-	for _, c := range holesTestCases {
-		r := newReassembler(FragmentID{}, &faketime.NullClock{})
-		for _, i := range c.in {
-			r.updateHoles(i.first, i.last, i.more)
-		}
-		if !reflect.DeepEqual(r.holes, c.want) {
-			t.Errorf("Test \"%s\" produced unexepetced holes. Got %v. Want %v", c.comment, r.holes, c.want)
-		}
+	for _, test := range tests {
+		t.Run(test.name, func(t *testing.T) {
+			r := newReassembler(FragmentID{}, &faketime.NullClock{})
+			for _, param := range test.params {
+				used, err := r.updateHoles(param.first, param.last, param.more)
+				if used != param.wantUsed || err != param.wantError {
+					t.Errorf("got r.updateHoles(%d, %d, %t) = (%t, %v), want = (%t, %v)", param.first, param.last, param.more, used, err, param.wantUsed, param.wantError)
+				}
+			}
+			if diff := cmp.Diff(test.want, r.holes, cmp.AllowUnexported(hole{})); diff != "" {
+				t.Errorf("r.holes mismatch (-want +got):\n%s", diff)
+			}
+		})
 	}
 }
diff --git a/test/packetimpact/tests/ipv4_fragment_reassembly_test.go b/test/packetimpact/tests/ipv4_fragment_reassembly_test.go
index e00a7aba2..d2203082d 100644
--- a/test/packetimpact/tests/ipv4_fragment_reassembly_test.go
+++ b/test/packetimpact/tests/ipv4_fragment_reassembly_test.go
@@ -34,10 +34,10 @@ type fragmentInfo struct {
 	offset uint16
 	size   uint16
 	more   uint8
+	id     uint16
 }
 
 func TestIPv4FragmentReassembly(t *testing.T) {
-	const fragmentID = 42
 	icmpv4ProtoNum := uint8(header.ICMPv4ProtocolNumber)
 
 	tests := []struct {
@@ -45,28 +45,75 @@ func TestIPv4FragmentReassembly(t *testing.T) {
 		ipPayloadLen int
 		fragments    []fragmentInfo
 		expectReply  bool
+		skip         bool
+		skipReason   string
 	}{
 		{
 			description:  "basic reassembly",
-			ipPayloadLen: 2000,
+			ipPayloadLen: 3000,
 			fragments: []fragmentInfo{
-				{offset: 0, size: 1000, more: header.IPv4FlagMoreFragments},
-				{offset: 1000, size: 1000, more: 0},
+				{offset: 0, size: 1000, id: 5, more: header.IPv4FlagMoreFragments},
+				{offset: 1000, size: 1000, id: 5, more: header.IPv4FlagMoreFragments},
+				{offset: 2000, size: 1000, id: 5, more: 0},
 			},
 			expectReply: true,
 		},
 		{
 			description:  "out of order fragments",
-			ipPayloadLen: 2000,
+			ipPayloadLen: 3000,
 			fragments: []fragmentInfo{
-				{offset: 1000, size: 1000, more: 0},
-				{offset: 0, size: 1000, more: header.IPv4FlagMoreFragments},
+				{offset: 2000, size: 1000, id: 6, more: 0},
+				{offset: 0, size: 1000, id: 6, more: header.IPv4FlagMoreFragments},
+				{offset: 1000, size: 1000, id: 6, more: header.IPv4FlagMoreFragments},
 			},
 			expectReply: true,
 		},
+		{
+			description:  "duplicated fragments",
+			ipPayloadLen: 3000,
+			fragments: []fragmentInfo{
+				{offset: 0, size: 1000, id: 7, more: header.IPv4FlagMoreFragments},
+				{offset: 1000, size: 1000, id: 7, more: header.IPv4FlagMoreFragments},
+				{offset: 1000, size: 1000, id: 7, more: header.IPv4FlagMoreFragments},
+				{offset: 2000, size: 1000, id: 7, more: 0},
+			},
+			expectReply: true,
+			skip:        true,
+			skipReason:  "gvisor.dev/issues/4971",
+		},
+		{
+			description:  "fragment subset",
+			ipPayloadLen: 3000,
+			fragments: []fragmentInfo{
+				{offset: 0, size: 1000, id: 8, more: header.IPv4FlagMoreFragments},
+				{offset: 1000, size: 1000, id: 8, more: header.IPv4FlagMoreFragments},
+				{offset: 512, size: 256, id: 8, more: header.IPv4FlagMoreFragments},
+				{offset: 2000, size: 1000, id: 8, more: 0},
+			},
+			expectReply: true,
+			skip:        true,
+			skipReason:  "gvisor.dev/issues/4971",
+		},
+		{
+			description:  "fragment overlap",
+			ipPayloadLen: 3000,
+			fragments: []fragmentInfo{
+				{offset: 0, size: 1000, id: 9, more: header.IPv4FlagMoreFragments},
+				{offset: 1512, size: 1000, id: 9, more: header.IPv4FlagMoreFragments},
+				{offset: 1000, size: 1000, id: 9, more: header.IPv4FlagMoreFragments},
+				{offset: 2000, size: 1000, id: 9, more: 0},
+			},
+			expectReply: false,
+			skip:        true,
+			skipReason:  "gvisor.dev/issues/4971",
+		},
 	}
 
 	for _, test := range tests {
+		if test.skip {
+			t.Skip("%s test skipped: %s", test.description, test.skipReason)
+			continue
+		}
 		t.Run(test.description, func(t *testing.T) {
 			dut := testbench.NewDUT(t)
 			conn := dut.Net.NewIPv4Conn(t, testbench.IPv4{}, testbench.IPv4{})
@@ -95,7 +142,7 @@ func TestIPv4FragmentReassembly(t *testing.T) {
 						Protocol:       &icmpv4ProtoNum,
 						FragmentOffset: testbench.Uint16(fragment.offset),
 						Flags:          testbench.Uint8(fragment.more),
-						ID:             testbench.Uint16(fragmentID),
+						ID:             testbench.Uint16(fragment.id),
 					},
 					&testbench.Payload{
 						Bytes: data[fragment.offset:][:fragment.size],
@@ -114,7 +161,7 @@ func TestIPv4FragmentReassembly(t *testing.T) {
 				}, time.Second)
 				if err != nil {
 					// Either an unexpected frame was received, or none at all.
-					if bytesReceived < test.ipPayloadLen {
+					if test.expectReply && bytesReceived < test.ipPayloadLen {
 						t.Fatalf("received %d bytes out of %d, then conn.ExpectFrame(_, _, time.Second) failed with %s", bytesReceived, test.ipPayloadLen, err)
 					}
 					break
diff --git a/test/packetimpact/tests/ipv6_fragment_reassembly_test.go b/test/packetimpact/tests/ipv6_fragment_reassembly_test.go
index 65f742f55..dd98ee7a1 100644
--- a/test/packetimpact/tests/ipv6_fragment_reassembly_test.go
+++ b/test/packetimpact/tests/ipv6_fragment_reassembly_test.go
@@ -35,10 +35,10 @@ type fragmentInfo struct {
 	offset uint16
 	size   uint16
 	more   bool
+	id     uint32
 }
 
 func TestIPv6FragmentReassembly(t *testing.T) {
-	const fragmentID = 42
 	icmpv6ProtoNum := header.IPv6ExtensionHeaderIdentifier(header.ICMPv6ProtocolNumber)
 
 	tests := []struct {
@@ -49,10 +49,11 @@ func TestIPv6FragmentReassembly(t *testing.T) {
 	}{
 		{
 			description:  "basic reassembly",
-			ipPayloadLen: 1500,
+			ipPayloadLen: 3000,
 			fragments: []fragmentInfo{
-				{offset: 0, size: 760, more: true},
-				{offset: 760, size: 740, more: false},
+				{offset: 0, size: 1000, id: 100, more: true},
+				{offset: 1000, size: 1000, id: 100, more: true},
+				{offset: 2000, size: 1000, id: 100, more: false},
 			},
 			expectReply: true,
 		},
@@ -60,12 +61,45 @@ func TestIPv6FragmentReassembly(t *testing.T) {
 			description:  "out of order fragments",
 			ipPayloadLen: 3000,
 			fragments: []fragmentInfo{
-				{offset: 0, size: 1024, more: true},
-				{offset: 2048, size: 952, more: false},
-				{offset: 1024, size: 1024, more: true},
+				{offset: 0, size: 1000, id: 101, more: true},
+				{offset: 2000, size: 1000, id: 101, more: false},
+				{offset: 1000, size: 1000, id: 101, more: true},
+			},
+			expectReply: true,
+		},
+		{
+			description:  "duplicated fragments",
+			ipPayloadLen: 3000,
+			fragments: []fragmentInfo{
+				{offset: 0, size: 1000, id: 102, more: true},
+				{offset: 1000, size: 1000, id: 102, more: true},
+				{offset: 1000, size: 1000, id: 102, more: true},
+				{offset: 2000, size: 1000, id: 102, more: false},
+			},
+			expectReply: true,
+		},
+		{
+			description:  "fragment subset",
+			ipPayloadLen: 3000,
+			fragments: []fragmentInfo{
+				{offset: 0, size: 1000, id: 103, more: true},
+				{offset: 1000, size: 1000, id: 103, more: true},
+				{offset: 512, size: 256, id: 103, more: true},
+				{offset: 2000, size: 1000, id: 103, more: false},
 			},
 			expectReply: true,
 		},
+		{
+			description:  "fragment overlap",
+			ipPayloadLen: 3000,
+			fragments: []fragmentInfo{
+				{offset: 0, size: 1000, id: 104, more: true},
+				{offset: 1512, size: 1000, id: 104, more: true},
+				{offset: 1000, size: 1000, id: 104, more: true},
+				{offset: 2000, size: 1000, id: 104, more: false},
+			},
+			expectReply: false,
+		},
 	}
 
 	for _, test := range tests {
@@ -101,7 +135,7 @@ func TestIPv6FragmentReassembly(t *testing.T) {
 						NextHeader:     &icmpv6ProtoNum,
 						FragmentOffset: testbench.Uint16(fragment.offset / header.IPv6FragmentExtHdrFragmentOffsetBytesPerUnit),
 						MoreFragments:  testbench.Bool(fragment.more),
-						Identification: testbench.Uint32(fragmentID),
+						Identification: testbench.Uint32(fragment.id),
 					},
 					&testbench.Payload{
 						Bytes: data[fragment.offset:][:fragment.size],
@@ -118,7 +152,7 @@ func TestIPv6FragmentReassembly(t *testing.T) {
 				}, time.Second)
 				if err != nil {
 					// Either an unexpected frame was received, or none at all.
-					if bytesReceived < test.ipPayloadLen {
+					if test.expectReply && bytesReceived < test.ipPayloadLen {
 						t.Fatalf("received %d bytes out of %d, then conn.ExpectFrame(_, _, time.Second) failed with %s", bytesReceived, test.ipPayloadLen, err)
 					}
 					break