diff options
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 |