internal/impl: check recursion limit in lazy decoding validation

The recursion depth limit was introduced in https://go.dev/cl/385854,
but without any tests.

When I added a basic test, I noticed that lazily decoded messages
and extensions circumvent the recursion limit:

At validation time, the limit was not checked. Later, lazy unmarshaling
(MessageInfo.unmarshalField) starts with the default recursion limit
(10'000) by copying impl.lazyUnmarshalOptions.

Before this commit, a 9999-deeply nested message could have an extension
which contains another 9999 nested messages, and so on.

I also noticed that maps did not count as a recursion (now also fixed).

(Google-internally tested globally as cl/842145661)

Change-Id: Ica036d8625225b21473de58ecd1afc8414eb6784
Reviewed-on: https://go-review.googlesource.com/c/protobuf/+/728680
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Lasse Folger <lassefolger@google.com>
diff --git a/internal/impl/codec_map.go b/internal/impl/codec_map.go
index 229c698..4a3bf39 100644
--- a/internal/impl/codec_map.go
+++ b/internal/impl/codec_map.go
@@ -113,6 +113,9 @@
 }
 
 func consumeMap(b []byte, mapv reflect.Value, wtyp protowire.Type, mapi *mapInfo, f *coderFieldInfo, opts unmarshalOptions) (out unmarshalOutput, err error) {
+	if opts.depth--; opts.depth < 0 {
+		return out, errRecursionDepth
+	}
 	if wtyp != protowire.BytesType {
 		return out, errUnknown
 	}
@@ -170,6 +173,9 @@
 }
 
 func consumeMapOfMessage(b []byte, mapv reflect.Value, wtyp protowire.Type, mapi *mapInfo, f *coderFieldInfo, opts unmarshalOptions) (out unmarshalOutput, err error) {
+	if opts.depth--; opts.depth < 0 {
+		return out, errRecursionDepth
+	}
 	if wtyp != protowire.BytesType {
 		return out, errUnknown
 	}
diff --git a/internal/impl/decode.go b/internal/impl/decode.go
index e0dd21f..1228b5c 100644
--- a/internal/impl/decode.go
+++ b/internal/impl/decode.go
@@ -102,8 +102,7 @@
 
 func (mi *MessageInfo) unmarshalPointer(b []byte, p pointer, groupTag protowire.Number, opts unmarshalOptions) (out unmarshalOutput, err error) {
 	mi.init()
-	opts.depth--
-	if opts.depth < 0 {
+	if opts.depth--; opts.depth < 0 {
 		return out, errRecursionDepth
 	}
 	if flags.ProtoLegacy && mi.isMessageSet {
diff --git a/internal/impl/validate.go b/internal/impl/validate.go
index 7b2995d..99a1eb9 100644
--- a/internal/impl/validate.go
+++ b/internal/impl/validate.go
@@ -68,9 +68,13 @@
 	if in.Resolver == nil {
 		in.Resolver = protoregistry.GlobalTypes
 	}
+	if in.Depth == 0 {
+		in.Depth = protowire.DefaultRecursionLimit
+	}
 	o, st := mi.validate(in.Buf, 0, unmarshalOptions{
 		flags:    in.Flags,
 		resolver: in.Resolver,
+		depth:    in.Depth,
 	})
 	if o.initialized {
 		out.Flags |= protoiface.UnmarshalInitialized
@@ -257,6 +261,9 @@
 		states[0].typ = validationTypeGroup
 		states[0].endGroup = groupTag
 	}
+	if opts.depth--; opts.depth < 0 {
+		return out, ValidationInvalid
+	}
 	initialized := true
 	start := len(b)
 State:
@@ -451,6 +458,13 @@
 						mi:      vi.mi,
 						tail:    b,
 					})
+					if vi.typ == validationTypeMessage ||
+						vi.typ == validationTypeGroup ||
+						vi.typ == validationTypeMap {
+						if opts.depth--; opts.depth < 0 {
+							return out, ValidationInvalid
+						}
+					}
 					b = v
 					continue State
 				case validationTypeRepeatedVarint:
@@ -499,6 +513,9 @@
 						mi:       vi.mi,
 						endGroup: num,
 					})
+					if opts.depth--; opts.depth < 0 {
+						return out, ValidationInvalid
+					}
 					continue State
 				case flags.ProtoLegacy && vi.typ == validationTypeMessageSetItem:
 					typeid, v, n, err := messageset.ConsumeFieldValue(b, false)
@@ -521,6 +538,13 @@
 							mi:   xvi.mi,
 							tail: b[n:],
 						})
+						if xvi.typ == validationTypeMessage ||
+							xvi.typ == validationTypeGroup ||
+							xvi.typ == validationTypeMap {
+							if opts.depth--; opts.depth < 0 {
+								return out, ValidationInvalid
+							}
+						}
 						b = v
 						continue State
 					}
@@ -547,12 +571,14 @@
 		switch st.typ {
 		case validationTypeMessage, validationTypeGroup:
 			numRequiredFields = int(st.mi.numRequiredFields)
+			opts.depth++
 		case validationTypeMap:
 			// If this is a map field with a message value that contains
 			// required fields, require that the value be present.
 			if st.mi != nil && st.mi.numRequiredFields > 0 {
 				numRequiredFields = 1
 			}
+			opts.depth++
 		}
 		// If there are more than 64 required fields, this check will
 		// always fail and we will report that the message is potentially
diff --git a/proto/decode.go b/proto/decode.go
index 4cbf1ae..889d851 100644
--- a/proto/decode.go
+++ b/proto/decode.go
@@ -121,9 +121,8 @@
 
 		out, err = methods.Unmarshal(in)
 	} else {
-		o.RecursionLimit--
-		if o.RecursionLimit < 0 {
-			return out, errors.New("exceeded max recursion depth")
+		if o.RecursionLimit--; o.RecursionLimit < 0 {
+			return out, errRecursionDepth
 		}
 		err = o.unmarshalMessageSlow(b, m)
 	}
@@ -220,6 +219,9 @@
 }
 
 func (o UnmarshalOptions) unmarshalMap(b []byte, wtyp protowire.Type, mapv protoreflect.Map, fd protoreflect.FieldDescriptor) (n int, err error) {
+	if o.RecursionLimit--; o.RecursionLimit < 0 {
+		return 0, errRecursionDepth
+	}
 	if wtyp != protowire.BytesType {
 		return 0, errUnknown
 	}
@@ -305,3 +307,5 @@
 var errUnknown = errors.New("BUG: internal error (unknown)")
 
 var errDecode = errors.New("cannot parse invalid wire-format data")
+
+var errRecursionDepth = errors.New("exceeded maximum recursion depth")
diff --git a/proto/testmessages_test.go b/proto/testmessages_test.go
index 4d3f898..a26c084 100644
--- a/proto/testmessages_test.go
+++ b/proto/testmessages_test.go
@@ -1687,6 +1687,110 @@
 			}),
 		}.Marshal(),
 	},
+
+	{
+		desc: "under recursion limit, but with many varint fields",
+		unmarshalOptions: proto.UnmarshalOptions{
+			// This message has no submessages.
+			RecursionLimit: 1,
+		},
+		decodeTo: makeMessages(protobuild.Message{
+			"repeated_int32": []int32{
+				1, 2, 3,
+			},
+		}),
+		wire: protopack.Message{
+			protopack.Tag{31, protopack.VarintType}, protopack.Varint(1),
+			protopack.Tag{31, protopack.VarintType}, protopack.Varint(2),
+			protopack.Tag{31, protopack.VarintType}, protopack.Varint(3),
+		}.Marshal(),
+	},
+
+	{
+		desc: "just at recursion limit (no submessages)",
+		unmarshalOptions: proto.UnmarshalOptions{
+			// This message has no submessages.
+			RecursionLimit: 1,
+		},
+		decodeTo: makeMessages(protobuild.Message{
+			"repeated_int32": []int32{
+				1,
+			},
+		}),
+		wire: protopack.Message{
+			protopack.Tag{31, protopack.VarintType}, protopack.Varint(1),
+		}.Marshal(),
+	},
+
+	{
+		desc: "just at recursion limit",
+		unmarshalOptions: proto.UnmarshalOptions{
+			RecursionLimit: 3,
+		},
+		decodeTo: makeMessages(protobuild.Message{
+			"optional_nested_message": protobuild.Message{
+				"corecursive": protobuild.Message{
+					"repeated_int32": []int32{1},
+				},
+			},
+		}),
+		wire: protopack.Message{
+			protopack.Tag{18, protopack.BytesType}, protopack.LengthPrefix(protopack.Message{
+				protopack.Tag{2, protopack.BytesType}, protopack.LengthPrefix(protopack.Message{
+					protopack.Tag{31, protopack.VarintType}, protopack.Varint(1),
+				}),
+			}),
+		}.Marshal(),
+	},
+
+	{
+		desc: "just at recursion limit: maps",
+		unmarshalOptions: proto.UnmarshalOptions{
+			// Maps are syntactic sugar for repeated fields of a synthetic
+			// message type (with key as field 1, value as field 2).
+			RecursionLimit: 2,
+		},
+		decodeTo: makeMessages(protobuild.Message{
+			"map_int32_int32": map[int32]int32{1056: 1156, 2056: 2156},
+		}, &test3pb.TestAllTypes{}, &testeditionspb.TestAllTypes{}),
+		wire: protopack.Message{
+			protopack.Tag{56, protopack.BytesType}, protopack.LengthPrefix(protopack.Message{
+				protopack.Tag{1, protopack.VarintType}, protopack.Varint(1056),
+				protopack.Tag{2, protopack.VarintType}, protopack.Varint(1156),
+			}),
+			protopack.Tag{56, protopack.BytesType}, protopack.LengthPrefix(protopack.Message{
+				protopack.Tag{1, protopack.VarintType}, protopack.Varint(2056),
+				protopack.Tag{2, protopack.VarintType}, protopack.Varint(2156),
+			}),
+		}.Marshal(),
+	},
+
+	{
+		desc: "just at recursion limit: maps of messages",
+		unmarshalOptions: proto.UnmarshalOptions{
+			RecursionLimit: 3,
+		},
+		decodeTo: makeMessages(protobuild.Message{
+			"map_string_nested_message": map[string]protobuild.Message{
+				"71.1.key": {"a": 1171},
+				"71.2.key": {"a": 2171},
+			},
+		}, &test3pb.TestAllTypes{}, &testeditionspb.TestAllTypes{}),
+		wire: protopack.Message{
+			protopack.Tag{71, protopack.BytesType}, protopack.LengthPrefix(protopack.Message{
+				protopack.Tag{1, protopack.BytesType}, protopack.String("71.1.key"),
+				protopack.Tag{2, protopack.BytesType}, protopack.LengthPrefix(protopack.Message{
+					protopack.Tag{1, protopack.VarintType}, protopack.Varint(1171),
+				}),
+			}),
+			protopack.Tag{71, protopack.BytesType}, protopack.LengthPrefix(protopack.Message{
+				protopack.Tag{1, protopack.BytesType}, protopack.String("71.2.key"),
+				protopack.Tag{2, protopack.BytesType}, protopack.LengthPrefix(protopack.Message{
+					protopack.Tag{1, protopack.VarintType}, protopack.Varint(2171),
+				}),
+			}),
+		}.Marshal(),
+	},
 }
 
 var testInvalidMessages = []testProto{
@@ -2224,6 +2328,83 @@
 			protopack.Raw("\xff\xff\xff\xff\xff\xff\xff\xff\xff"),
 		}.Marshal(),
 	},
+	{
+		desc: "exceed recursion limit",
+		decodeTo: []proto.Message{
+			(*testpb.TestAllTypes)(nil),
+			(*testeditionspb.TestAllTypes)(nil),
+		},
+		unmarshalOptions: proto.UnmarshalOptions{
+			RecursionLimit: 5,
+		},
+		wire: recursivelyNestedMessage(3),
+	},
+	{
+		desc: "exceed recursion limit: maps",
+		unmarshalOptions: proto.UnmarshalOptions{
+			// Maps are syntactic sugar for repeated fields of a synthetic
+			// message type (with key as field 1, value as field 2).
+			RecursionLimit: 1,
+		},
+		decodeTo: []proto.Message{
+			(*testpb.TestAllTypes)(nil),
+			(*testeditionspb.TestAllTypes)(nil),
+		},
+		wire: protopack.Message{
+			protopack.Tag{56, protopack.BytesType}, protopack.LengthPrefix(protopack.Message{
+				protopack.Tag{1, protopack.VarintType}, protopack.Varint(1056),
+				protopack.Tag{2, protopack.VarintType}, protopack.Varint(1156),
+			}),
+			protopack.Tag{56, protopack.BytesType}, protopack.LengthPrefix(protopack.Message{
+				protopack.Tag{1, protopack.VarintType}, protopack.Varint(2056),
+				protopack.Tag{2, protopack.VarintType}, protopack.Varint(2156),
+			}),
+		}.Marshal(),
+	},
+	{
+		desc: "exceed recursion limit: maps of messages",
+		unmarshalOptions: proto.UnmarshalOptions{
+			RecursionLimit: 2,
+		},
+		decodeTo: []proto.Message{
+			(*testpb.TestAllTypes)(nil),
+			(*testeditionspb.TestAllTypes)(nil),
+		},
+		wire: protopack.Message{
+			protopack.Tag{71, protopack.BytesType}, protopack.LengthPrefix(protopack.Message{
+				protopack.Tag{1, protopack.BytesType}, protopack.String("71.1.key"),
+				protopack.Tag{2, protopack.BytesType}, protopack.LengthPrefix(protopack.Message{
+					protopack.Tag{1, protopack.VarintType}, protopack.Varint(1171),
+				}),
+			}),
+			protopack.Tag{71, protopack.BytesType}, protopack.LengthPrefix(protopack.Message{
+				protopack.Tag{1, protopack.BytesType}, protopack.String("71.2.key"),
+				protopack.Tag{2, protopack.BytesType}, protopack.LengthPrefix(protopack.Message{
+					protopack.Tag{1, protopack.VarintType}, protopack.Varint(2171),
+				}),
+			}),
+		}.Marshal(),
+	},
+}
+
+// recursivelyNestedMessage returns a message with 2*depth submessages
+// (2*depth because of the definition of testpb.TestAllTypes).
+func recursivelyNestedMessage(depth int) []byte {
+	var prev []byte
+	prev = protopack.Message{
+		protopack.Tag{1, protopack.VarintType}, protopack.Varint(depth),
+	}.Marshal()
+	for depth > 0 {
+		prev = protopack.Message{
+			protopack.Tag{18, protopack.BytesType}, protopack.LengthPrefix(protopack.Message{
+				protopack.Tag{2, protopack.BytesType}, protopack.LengthPrefix(protopack.Message{
+					protopack.Raw(prev),
+				}),
+			}),
+		}.Marshal()
+		depth--
+	}
+	return prev
 }
 
 type filterResolver struct {
diff --git a/proto/validate_test.go b/proto/validate_test.go
index e806998..7af5ea3 100644
--- a/proto/validate_test.go
+++ b/proto/validate_test.go
@@ -27,7 +27,8 @@
 					want = test.validationStatus
 				}
 				out, status := impl.Validate(mt, piface.UnmarshalInput{
-					Buf: test.wire,
+					Buf:   test.wire,
+					Depth: test.unmarshalOptions.RecursionLimit,
 				})
 				if status != want {
 					t.Errorf("Validate(%x) = %v, want %v", test.wire, status, want)
@@ -46,7 +47,8 @@
 			t.Run(fmt.Sprintf("%s (%T)", test.desc, m), func(t *testing.T) {
 				mt := m.ProtoReflect().Type()
 				_, got := impl.Validate(mt, piface.UnmarshalInput{
-					Buf: test.wire,
+					Buf:   test.wire,
+					Depth: test.unmarshalOptions.RecursionLimit,
 				})
 				want := impl.ValidationInvalid
 				if got != want {