Detect looped-back NDP DAD messages

...as per RFC 7527.

If a looped-back DAD message is received, do not fail DAD since our own
DAD message does not indicate that a neighbor has the address assigned.

Test: ndp_test.TestDADResolveLoopback
PiperOrigin-RevId: 363224288

2 files changed, 246 insertions, 17 deletions

diff --git a/pkg/tcpip/network/internal/ip/duplicate_address_detection.go b/pkg/tcpip/network/internal/ip/duplicate_address_detection.go
index 0053646ee..eed49f5d2 100644
--- a/pkg/tcpip/network/internal/ip/duplicate_address_detection.go
+++ b/pkg/tcpip/network/internal/ip/duplicate_address_detection.go
@@ -16,14 +16,27 @@
 package ip
 
 import (
+	"bytes"
 	"fmt"
+	"io"
 
 	"gvisor.dev/gvisor/pkg/sync"
 	"gvisor.dev/gvisor/pkg/tcpip"
 	"gvisor.dev/gvisor/pkg/tcpip/stack"
 )
 
+type extendRequest int
+
+const (
+	notRequested extendRequest = iota
+	requested
+	extended
+)
+
 type dadState struct {
+	nonce         []byte
+	extendRequest extendRequest
+
 	done  *bool
 	timer tcpip.Timer
 
@@ -33,14 +46,17 @@ type dadState struct {
 // DADProtocol is a protocol whose core state machine can be represented by DAD.
 type DADProtocol interface {
 	// SendDADMessage attempts to send a DAD probe message.
-	SendDADMessage(tcpip.Address) tcpip.Error
+	SendDADMessage(tcpip.Address, []byte) tcpip.Error
 }
 
 // DADOptions holds options for DAD.
 type DADOptions struct {
-	Clock    tcpip.Clock
-	Protocol DADProtocol
-	NICID    tcpip.NICID
+	Clock              tcpip.Clock
+	SecureRNG          io.Reader
+	NonceSize          uint8
+	ExtendDADTransmits uint8
+	Protocol           DADProtocol
+	NICID              tcpip.NICID
 }
 
 // DAD performs duplicate address detection for addresses.
@@ -63,6 +79,10 @@ func (d *DAD) Init(protocolMU sync.Locker, configs stack.DADConfigurations, opts
 		panic("attempted to initialize DAD state twice")
 	}
 
+	if opts.NonceSize != 0 && opts.ExtendDADTransmits == 0 {
+		panic(fmt.Sprintf("given a non-zero value for NonceSize (%d) but zero for ExtendDADTransmits", opts.NonceSize))
+	}
+
 	*d = DAD{
 		opts:       opts,
 		configs:    configs,
@@ -96,10 +116,55 @@ func (d *DAD) CheckDuplicateAddressLocked(addr tcpip.Address, h stack.DADComplet
 		s = dadState{
 			done: &done,
 			timer: d.opts.Clock.AfterFunc(0, func() {
-				var err tcpip.Error
 				dadDone := remaining == 0
+
+				nonce, earlyReturn := func() ([]byte, bool) {
+					d.protocolMU.Lock()
+					defer d.protocolMU.Unlock()
+
+					if done {
+						return nil, true
+					}
+
+					s, ok := d.addresses[addr]
+					if !ok {
+						panic(fmt.Sprintf("dad: timer fired but missing state for %s on NIC(%d)", addr, d.opts.NICID))
+					}
+
+					// As per RFC 7527 section 4
+					//
+					//   If any probe is looped back within RetransTimer milliseconds
+					//   after having sent DupAddrDetectTransmits NS(DAD) messages, the
+					//   interface continues with another MAX_MULTICAST_SOLICIT number of
+					//   NS(DAD) messages transmitted RetransTimer milliseconds apart.
+					if dadDone && s.extendRequest == requested {
+						dadDone = false
+						remaining = d.opts.ExtendDADTransmits
+						s.extendRequest = extended
+					}
+
+					if !dadDone && d.opts.NonceSize != 0 {
+						if s.nonce == nil {
+							s.nonce = make([]byte, d.opts.NonceSize)
+						}
+
+						if n, err := io.ReadFull(d.opts.SecureRNG, s.nonce); err != nil {
+							panic(fmt.Sprintf("SecureRNG.Read(...): %s", err))
+						} else if n != len(s.nonce) {
+							panic(fmt.Sprintf("expected to read %d bytes from secure RNG, only read %d bytes", len(s.nonce), n))
+						}
+					}
+
+					d.addresses[addr] = s
+					return s.nonce, false
+				}()
+				if earlyReturn {
+					return
+				}
+
+				var err tcpip.Error
 				if !dadDone {
-					err = d.opts.Protocol.SendDADMessage(addr)
+					err = d.opts.Protocol.SendDADMessage(addr, nonce)
 				}
 
 				d.protocolMU.Lock()
@@ -142,6 +207,68 @@ func (d *DAD) CheckDuplicateAddressLocked(addr tcpip.Address, h stack.DADComplet
 	return ret
 }
 
+// ExtendIfNonceEqualLockedDisposition enumerates the possible results from
+// ExtendIfNonceEqualLocked.
+type ExtendIfNonceEqualLockedDisposition int
+
+const (
+	// Extended indicates that the DAD process was extended.
+	Extended ExtendIfNonceEqualLockedDisposition = iota
+
+	// AlreadyExtended indicates that the DAD process was already extended.
+	AlreadyExtended
+
+	// NoDADStateFound indicates that DAD state was not found for the address.
+	NoDADStateFound
+
+	// NonceDisabled indicates that nonce values are not sent with DAD messages.
+	NonceDisabled
+
+	// NonceNotEqual indicates that the nonce value passed and the nonce in the
+	// last send DAD message are not equal.
+	NonceNotEqual
+)
+
+// ExtendIfNonceEqualLocked extends the DAD process if the provided nonce is the
+// same as the nonce sent in the last DAD message.
+//
+// Precondition: d.protocolMU must be locked.
+func (d *DAD) ExtendIfNonceEqualLocked(addr tcpip.Address, nonce []byte) ExtendIfNonceEqualLockedDisposition {
+	s, ok := d.addresses[addr]
+	if !ok {
+		return NoDADStateFound
+	}
+
+	if d.opts.NonceSize == 0 {
+		return NonceDisabled
+	}
+
+	if s.extendRequest != notRequested {
+		return AlreadyExtended
+	}
+
+	// As per RFC 7527 section 4
+	//
+	//   If any probe is looped back within RetransTimer milliseconds after having
+	//   sent DupAddrDetectTransmits NS(DAD) messages, the interface continues
+	//   with another MAX_MULTICAST_SOLICIT number of NS(DAD) messages transmitted
+	//   RetransTimer milliseconds apart.
+	//
+	// If a DAD message has already been sent and the nonce value we observed is
+	// the same as the nonce value we last sent, then we assume our probe was
+	// looped back and request an extension to the DAD process.
+	//
+	// Note, the first DAD message is sent asynchronously so we need to make sure
+	// that we sent a DAD message by checking if we have a nonce value set.
+	if s.nonce != nil && bytes.Equal(s.nonce, nonce) {
+		s.extendRequest = requested
+		d.addresses[addr] = s
+		return Extended
+	}
+
+	return NonceNotEqual
+}
+
 // StopLocked stops a currently running DAD process.
 //
 // Precondition: d.protocolMU must be locked.
diff --git a/pkg/tcpip/network/internal/ip/duplicate_address_detection_test.go b/pkg/tcpip/network/internal/ip/duplicate_address_detection_test.go
index e00aa4678..a22b712c6 100644
--- a/pkg/tcpip/network/internal/ip/duplicate_address_detection_test.go
+++ b/pkg/tcpip/network/internal/ip/duplicate_address_detection_test.go
@@ -15,6 +15,7 @@
 package ip_test
 
 import (
+	"bytes"
 	"testing"
 	"time"
 
@@ -32,8 +33,8 @@ type mockDADProtocol struct {
 	mu struct {
 		sync.Mutex
 
-		dad       ip.DAD
-		sendCount map[tcpip.Address]int
+		dad        ip.DAD
+		sentNonces map[tcpip.Address][][]byte
 	}
 }
 
@@ -48,26 +49,30 @@ func (m *mockDADProtocol) init(t *testing.T, c stack.DADConfigurations, opts ip.
 }
 
 func (m *mockDADProtocol) initLocked() {
-	m.mu.sendCount = make(map[tcpip.Address]int)
+	m.mu.sentNonces = make(map[tcpip.Address][][]byte)
 }
 
-func (m *mockDADProtocol) SendDADMessage(addr tcpip.Address) tcpip.Error {
+func (m *mockDADProtocol) SendDADMessage(addr tcpip.Address, nonce []byte) tcpip.Error {
 	m.mu.Lock()
 	defer m.mu.Unlock()
-	m.mu.sendCount[addr]++
+	m.mu.sentNonces[addr] = append(m.mu.sentNonces[addr], nonce)
 	return nil
 }
 
 func (m *mockDADProtocol) check(addrs []tcpip.Address) string {
-	m.mu.Lock()
-	defer m.mu.Unlock()
-
-	sendCount := make(map[tcpip.Address]int)
+	sentNonces := make(map[tcpip.Address][][]byte)
 	for _, a := range addrs {
-		sendCount[a]++
+		sentNonces[a] = append(sentNonces[a], nil)
 	}
 
-	diff := cmp.Diff(sendCount, m.mu.sendCount)
+	return m.checkWithNonce(sentNonces)
+}
+
+func (m *mockDADProtocol) checkWithNonce(expectedSentNonces map[tcpip.Address][][]byte) string {
+	m.mu.Lock()
+	defer m.mu.Unlock()
+
+	diff := cmp.Diff(expectedSentNonces, m.mu.sentNonces)
 	m.initLocked()
 	return diff
 }
@@ -84,6 +89,12 @@ func (m *mockDADProtocol) stop(addr tcpip.Address, reason stack.DADResult) {
 	m.mu.dad.StopLocked(addr, reason)
 }
 
+func (m *mockDADProtocol) extendIfNonceEqual(addr tcpip.Address, nonce []byte) ip.ExtendIfNonceEqualLockedDisposition {
+	m.mu.Lock()
+	defer m.mu.Unlock()
+	return m.mu.dad.ExtendIfNonceEqualLocked(addr, nonce)
+}
+
 func (m *mockDADProtocol) setConfigs(c stack.DADConfigurations) {
 	m.mu.Lock()
 	defer m.mu.Unlock()
@@ -277,3 +288,94 @@ func TestDADStop(t *testing.T) {
 	default:
 	}
 }
+
+func TestNonce(t *testing.T) {
+	const (
+		nonceSize = 2
+
+		extendRequestAttempts = 2
+
+		dupAddrDetectTransmits = 2
+		extendTransmits        = 5
+	)
+
+	var secureRNGBytes [nonceSize * (dupAddrDetectTransmits + extendTransmits)]byte
+	for i := range secureRNGBytes {
+		secureRNGBytes[i] = byte(i)
+	}
+
+	tests := []struct {
+		name                string
+		mockedReceivedNonce []byte
+		expectedResults     [extendRequestAttempts]ip.ExtendIfNonceEqualLockedDisposition
+		expectedTransmits   int
+	}{
+		{
+			name:                "not matching",
+			mockedReceivedNonce: []byte{0, 0},
+			expectedResults:     [extendRequestAttempts]ip.ExtendIfNonceEqualLockedDisposition{ip.NonceNotEqual, ip.NonceNotEqual},
+			expectedTransmits:   dupAddrDetectTransmits,
+		},
+		{
+			name:                "matching nonce",
+			mockedReceivedNonce: secureRNGBytes[:nonceSize],
+			expectedResults:     [extendRequestAttempts]ip.ExtendIfNonceEqualLockedDisposition{ip.Extended, ip.AlreadyExtended},
+			expectedTransmits:   dupAddrDetectTransmits + extendTransmits,
+		},
+	}
+
+	for _, test := range tests {
+		t.Run(test.name, func(t *testing.T) {
+			var dad mockDADProtocol
+			clock := faketime.NewManualClock()
+			dadConfigs := stack.DADConfigurations{
+				DupAddrDetectTransmits: dupAddrDetectTransmits,
+				RetransmitTimer:        time.Second,
+			}
+
+			var secureRNG bytes.Reader
+			secureRNG.Reset(secureRNGBytes[:])
+			dad.init(t, dadConfigs, ip.DADOptions{
+				Clock:              clock,
+				SecureRNG:          &secureRNG,
+				NonceSize:          nonceSize,
+				ExtendDADTransmits: extendTransmits,
+			})
+
+			ch := make(chan dadResult, 1)
+			if res := dad.checkDuplicateAddress(addr1, handler(ch, addr1)); res != stack.DADStarting {
+				t.Errorf("got dad.checkDuplicateAddress(%s, _) = %d, want = %d", addr1, res, stack.DADStarting)
+			}
+
+			clock.Advance(0)
+			for i, want := range test.expectedResults {
+				if got := dad.extendIfNonceEqual(addr1, test.mockedReceivedNonce); got != want {
+					t.Errorf("(i=%d) got dad.extendIfNonceEqual(%s, _) = %d, want = %d", i, addr1, got, want)
+				}
+			}
+
+			for i := 0; i < test.expectedTransmits; i++ {
+				if diff := dad.checkWithNonce(map[tcpip.Address][][]byte{
+					addr1: {
+						secureRNGBytes[nonceSize*i:][:nonceSize],
+					},
+				}); diff != "" {
+					t.Errorf("(i=%d) dad check mismatch (-want +got):\n%s", i, diff)
+				}
+
+				clock.Advance(dadConfigs.RetransmitTimer)
+			}
+
+			if diff := cmp.Diff(dadResult{Addr: addr1, R: &stack.DADSucceeded{}}, <-ch); diff != "" {
+				t.Errorf("dad result mismatch (-want +got):\n%s", diff)
+			}
+
+			// Should not have anymore updates.
+			select {
+			case r := <-ch:
+				t.Fatalf("unexpectedly got an extra DAD result; r = %#v", r)
+			default:
+			}
+		})
+	}
+}