zeroshade commented on code in PR #1126:
URL: https://github.com/apache/arrow-go/pull/1126#discussion_r3866486581
##########
parquet/variant/variant.go:
##########
@@ -556,23 +556,406 @@ func validateScalarValue(value []byte) error {
want = 17
case PrimitiveBinary, PrimitiveString:
if len(value) < 5 {
- return fmt.Errorf("invalid variant value: %s length
prefix requires 5 bytes, got %d", primitiveType, len(value))
+ return 0, fmt.Errorf("invalid variant value: %s length
prefix requires 5 bytes, got %d", primitiveType, len(value))
}
dataLen := uint64(binary.LittleEndian.Uint32(value[1:5]))
if dataLen > uint64(len(value)-5) {
- return fmt.Errorf("invalid variant value: %s data
requires %d bytes, got %d", primitiveType, dataLen, len(value)-5)
+ return 0, fmt.Errorf("invalid variant value: %s data
requires %d bytes, got %d", primitiveType, dataLen, len(value)-5)
}
- return nil
+ return 5 + int(dataLen), nil
default:
- return fmt.Errorf("invalid variant value: unknown primitive
type %d", primitiveType)
+ return 0, fmt.Errorf("invalid variant value: unknown primitive
type %d", primitiveType)
}
if len(value) < want {
- return fmt.Errorf("invalid variant value: %s requires %d bytes,
got %d", primitiveType, want, len(value))
+ return 0, fmt.Errorf("invalid variant value: %s requires %d
bytes, got %d", primitiveType, want, len(value))
}
+ return want, nil
+}
+
+type validationRange struct {
+ start uint64
+ end uint64
+ field int
+}
+
+type validationFrame struct {
+ value []byte
+ size uint64
+ dataSize uint32
+ dataStart uint32
+ offsetStart uint32
+ numChildren uint32
+ nextChild uint32
+ pendingIndex uint32
+ pendingStart uint32
+ pendingExpectedSize uint32
+ rangeStart uint32
+ offsetSize uint8
+ kind uint8
+ initialized bool
+}
+
+const (
+ validationStackInlineCapacity = 32
+ // Values that exceed the inline stack commonly need only a modest
amount
+ // of additional depth, so avoid allocating the maximum stack for them.
+ validationStackIntermediateCapacity = 128
+ // The root value is at depth zero, so the stack needs one more frame
than
+ // the maximum allowed nesting depth. Keeping this storage fixed
prevents
+ // untrusted values from growing the validation stack on the heap.
+ validationStackCapacity = maxValidationDepth + 1
+ validationRangeInlineCapacity = 64
+)
+
+// validateValue walks compound values with an explicit stack so valid values
+// do not consume the Go call stack. Nesting is bounded to keep validation
+// memory usage independent of attacker-controlled input depth.
+func validateValue(meta Metadata, value []byte) (int, error) {
+ var stackStorage [validationStackInlineCapacity]validationFrame
+ stack := stackStorage[:1]
+ stack[0].value = value
+
+ var rangeStorage [validationRangeInlineCapacity]validationRange
+ ranges := rangeStorage[:0]
+ return validateValueLoop(meta, value, stack, ranges, 0)
+}
+
+func validateValueLoop(meta Metadata, value []byte, stack []validationFrame,
ranges []validationRange, rangeTop int) (int, error) {
+ var (
+ resultSize int
+ resultErr error
+ hasResult bool
+ )
+
+ for len(stack) > 0 {
+ frame := &stack[len(stack)-1]
+ if hasResult {
+ hasResult = false
+
+ if resultErr != nil {
+ switch BasicType(frame.kind) {
+ case BasicArray:
+ return 0, fmt.Errorf("invalid variant
value: array element %d: %w", frame.pendingIndex, resultErr)
+ case BasicObject:
+ return 0, fmt.Errorf("invalid variant
value: object field %d: %w", frame.pendingIndex, resultErr)
+ default:
+ return 0, resultErr
+ }
+ }
+
+ switch BasicType(frame.kind) {
+ case BasicArray:
+ if uint64(resultSize) !=
uint64(frame.pendingExpectedSize) {
+ return 0, fmt.Errorf("invalid variant
value: array element %d has trailing bytes", frame.pendingIndex)
+ }
+ case BasicObject:
+ end := uint64(frame.pendingStart) +
uint64(resultSize)
+ if end > uint64(frame.dataSize) {
+ return 0, fmt.Errorf("invalid variant
value: object field %d extends beyond data", frame.pendingIndex)
+ }
+ if rangeTop < len(ranges) {
+ ranges[rangeTop] = validationRange{
+ start:
uint64(frame.pendingStart),
+ end: end,
+ field: int(frame.pendingIndex),
+ }
+ } else {
+ ranges = append(ranges, validationRange{
+ start:
uint64(frame.pendingStart),
+ end: end,
+ field: int(frame.pendingIndex),
+ })
+ }
+ rangeTop++
+ }
+ continue
+ }
+
+ if !frame.initialized {
+ frame.initialized = true
+ if err := prepareValidationFrame(meta, frame); err !=
nil {
+ stack = stack[:len(stack)-1]
+ if len(stack) == 0 {
+ return 0, err
+ }
+ resultErr = err
+ hasResult = true
+ continue
+ }
+ if BasicType(frame.kind) == BasicObject {
+ frame.rangeStart = uint32(rangeTop)
+ }
+ }
+
+ if frame.kind == uint8(BasicArray) || frame.kind ==
uint8(BasicObject) {
+ if frame.nextChild < frame.numChildren {
+ if len(stack) == validationStackCapacity {
+ return 0, fmt.Errorf("invalid variant
value: maximum nesting depth exceeded")
+ }
+ if len(stack) == cap(stack) {
+ if cap(stack) ==
validationStackInlineCapacity {
+ return
validateValueIntermediate(meta, value, stack, ranges, rangeTop)
+ }
+ return validateValueDeep(meta, value,
stack, ranges, rangeTop)
+ }
+
+ child, index, start, expectedSize, err :=
nextValidationChild(frame)
+ if err != nil {
+ stack = stack[:len(stack)-1]
+ if len(stack) == 0 {
+ return 0, err
+ }
+ resultErr = err
+ hasResult = true
+ continue
+ }
+
+ frame.nextChild++
+ frame.pendingIndex = uint32(index)
+ frame.pendingStart = uint32(start)
+ frame.pendingExpectedSize = uint32(expectedSize)
+ stack = append(stack, validationFrame{value:
child})
+ continue
+ }
+
+ if err := finishValidationFrame(frame,
ranges[int(frame.rangeStart):rangeTop]); err != nil {
+ if BasicType(frame.kind) == BasicObject {
+ rangeTop = int(frame.rangeStart)
+ }
+ stack = stack[:len(stack)-1]
+ if len(stack) == 0 {
+ return 0, err
+ }
+ resultErr = err
+ hasResult = true
+ continue
+ }
+ if BasicType(frame.kind) == BasicObject {
+ rangeTop = int(frame.rangeStart)
+ }
+ }
+
+ resultSize = int(frame.size)
+ stack = stack[:len(stack)-1]
+ if len(stack) == 0 {
+ return resultSize, nil
+ }
+ hasResult = true
+ }
+
+ return 0, errors.New("invalid variant value: validation stack
exhausted")
+}
+
+func validateValueIntermediate(meta Metadata, value []byte, initialStack
[]validationFrame, ranges []validationRange, rangeTop int) (int, error) {
+ var stackStorage [validationStackIntermediateCapacity]validationFrame
+ stack := stackStorage[:len(initialStack)]
+ copy(stack, initialStack)
+ return validateValueLoop(meta, value, stack, ranges, rangeTop)
+}
+
+func validateValueDeep(meta Metadata, value []byte, initialStack
[]validationFrame, ranges []validationRange, rangeTop int) (int, error) {
+ var stackStorage [validationStackCapacity]validationFrame
+ stack := stackStorage[:len(initialStack)]
+ copy(stack, initialStack)
+ return validateValueLoop(meta, value, stack, ranges, rangeTop)
+}
+
+func finishValidationFrame(frame *validationFrame, ranges []validationRange)
error {
+ if BasicType(frame.kind) != BasicObject {
+ return nil
+ }
+
+ slices.SortFunc(ranges, func(a, b validationRange) int {
+ switch {
+ case a.start < b.start:
+ return -1
+ case a.start > b.start:
+ return 1
+ default:
+ return 0
+ }
+ })
+
+ var (
+ next uint64
+ previousField int
+ )
+ for _, child := range ranges {
+ switch {
+ case child.start < next:
+ return fmt.Errorf("invalid variant value: object fields
%d and %d overlap", previousField, child.field)
+ case child.start > next:
+ return fmt.Errorf("invalid variant value: object data
has a gap before field %d", child.field)
+ }
+ next = child.end
+ previousField = child.field
+ }
+ if next != uint64(frame.dataSize) {
+ return fmt.Errorf("invalid variant value: object data has
trailing bytes")
+ }
+ return nil
+}
+
+func prepareValidationFrame(meta Metadata, frame *validationFrame) error {
+ if len(frame.value) == 0 {
+ return errors.New("invalid variant value: empty")
+ }
+
+ frame.kind = uint8(basicTypeFromHeader(frame.value[0]))
+ switch BasicType(frame.kind) {
+ case BasicShortString:
+ want := 1 + int(frame.value[0]>>basicTypeBits)
+ if len(frame.value) < want {
+ return fmt.Errorf("invalid variant value: short string
requires %d bytes, got %d", want, len(frame.value))
+ }
+ frame.size = uint64(want)
+ case BasicObject:
+ return prepareObjectValidationFrame(meta, frame)
+ case BasicArray:
+ return prepareArrayValidationFrame(frame)
+ case BasicPrimitive:
+ size, err := validatePrimitiveValue(frame.value)
+ frame.size = uint64(size)
+ return err
+ default:
+ return fmt.Errorf("invalid variant value: unknown basic type
%d", BasicType(frame.kind))
+ }
+ return nil
+}
+
+func prepareArrayValidationFrame(frame *validationFrame) error {
+ value := frame.value
+ typeInfo := value[0] >> basicTypeBits
+ offsetSize := uint8(typeInfo&0b11) + 1
+ isLarge := ((typeInfo >> 2) & 0x1) != 0
+
+ var (
+ numElements uint32
+ offsetStart uint64
+ )
+ if isLarge {
+ if len(value) < 5 {
+ return fmt.Errorf("invalid variant value: array size
requires 5 bytes, got %d", len(value))
+ }
+ numElements = readLEU32(value[1:5])
+ offsetStart = 5
+ } else {
+ if len(value) < 2 {
+ return fmt.Errorf("invalid variant value: array size
requires 2 bytes, got %d", len(value))
+ }
+ numElements = uint32(value[1])
+ offsetStart = 2
+ }
+
+ dataStart := offsetStart + (uint64(numElements)+1)*uint64(offsetSize)
+ if dataStart > uint64(len(value)) || dataStart > math.MaxUint32 {
+ return fmt.Errorf("invalid variant value: array offset table
ends at %d, got %d bytes", dataStart, len(value))
+ }
+
+ var previousOffset uint32
+ for i := uint64(0); i <= uint64(numElements); i++ {
+ pos := offsetStart + uint64(i)*uint64(offsetSize)
+ offset := readLEU32(value[int(pos) : int(pos)+int(offsetSize)])
+ if i == 0 && offset != 0 {
+ return fmt.Errorf("invalid variant value: array first
offset must be zero, got %d", offset)
+ }
+ if i > 0 && offset < previousOffset {
+ return fmt.Errorf("invalid variant value: array offsets
are not monotonic")
+ }
+ if dataStart+uint64(offset) > uint64(len(value)) ||
dataStart+uint64(offset) > math.MaxUint32 {
Review Comment:
**Blocking:** This treats `dataStart + offset` as though the complete
encoded value were limited to `uint32`, but Variant's 4-byte field offsets are
relative to the start of the fields region. A valid compound can therefore
contain a `math.MaxUint32`-byte fields region plus its header and offset table.
A sparse-mapped array with one max-sized binary child passes on the merge base
but fails here with `array offset 4294967295 is out of range`. The equivalent
object condition at line 907 has the same issue. Please retain total positions
as `uint64` and compare them against `len(value)` without imposing this
undocumented total-value limit.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
