(*WriteBatchIterator).decodeVarint unfortunately doesn’t correctly detect invalid varint sequences and can consume the entire buffer

[odeke-em]

This is a bug that I reported in July 2022 originally at tecbot/gorocksdb#221 and it is still relevant to this repo:

Courtesy of the Cosmos Network Security, I discovered this code while auditing supply chain dependencies.
If we examine this code in

grocksdb/write_batch.go

Lines 344 to 362 in 254f68b

	func (iter *WriteBatchIterator) decodeVarint() uint64 {
	var n int
	var x uint64
	for shift := uint(0); shift < 64 && n < len(iter.data); shift += 7 {
	b := uint64(iter.data[n])
	n++
	x |= (b & 0x7F) << shift
	if (b & 0x80) == 0 {
	iter.data = iter.data[n:]
	return x
	}
	}
	if n == len(iter.data) {
	iter.err = io.ErrShortBuffer
	} else {
	iter.err = errors.New("malformed varint")
	}
	return 0
	}

and then extract it and run the following https://go.dev/play/p/MXpanwJKofY or inlined below:

package main

import (
	"errors"
	"fmt"
	"io"
)

type wbi struct {
	data []byte
	err  error
}

func (iter *wbi) decodeVarint() uint64 {
	var n int
	var x uint64
	for shift := uint(0); shift < 64 && n < len(iter.data); shift += 7 {
		b := uint64(iter.data[n])
		n++
		x |= (b & 0x7F) << shift
		if (b & 0x80) == 0 {
			iter.data = iter.data[n:]
			return x
		}
	}
	if n == len(iter.data) {
		iter.err = io.ErrShortBuffer
	} else {
		iter.err = errors.New("malformed varint")
	}
	return 0
}

func main() {
	// The 10th byte here is invalid and should be reported.
	// Please see https://github.com/golang/go/issues/41185
	b := []byte{0xd7, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f}
	wb := &wbi{data: b}
	v := wb.decodeVarint()
	println(v)
	fmt.Printf("%v\n", wb.err) // This should have reported an error.
}

which prints

18446744073709551575
<nil>

Fix

The fix entails just using the Go standard library's code in which I fixed this bug in March 2021 in the Go standard library per golang/go@aafad20

with a demo at https://go.dev/play/p/kYGBjzh24Qx which should properly print malformed varint

package main

import (
	"encoding/binary"
	"errors"
	"fmt"
	"io"
)

type wbi struct {
	data []byte
	err  error
}

func (iter *wbi) decodeVarint() uint64 {
	var n int
	var x uint64
	for shift := uint(0); shift < 64 && n < len(iter.data); shift += 7 {
		b := uint64(iter.data[n])
		n++
		x |= (b & 0x7F) << shift
		if (b & 0x80) == 0 {
			iter.data = iter.data[n:]
			return x
		}
	}
	if n == len(iter.data) {
		iter.err = io.ErrShortBuffer
	} else {
		iter.err = errors.New("malformed varint")
	}
	return 0
}

func (iter *wbi) decodeVarint_good() (x uint64) {
	v, n := binary.Varint(iter.data)
	if n == len(iter.data) {
		iter.err = io.ErrShortBuffer
	} else if n < 0 {
		iter.err = errors.New("malformed varint")
	} else {
		x = uint64(v)
	}
	return x
}

func main() {
	// The 10th byte here is invalid and should be reported.
	// Please see https://github.com/golang/go/issues/41185
	b := []byte{0xd7, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f}
	wb := &wbi{data: b}
	v := wb.decodeVarint_good()
	println(v)
	fmt.Printf("%v\n", wb.err) // This should have reported an error.
}

which correctly prints

0
malformed varint

/cc @elias-orijtech @julienrbrt

[linxGnu]

@odeke-em Thank you so much for discovering this issue.

I made a fix, using your test cases that you used to patch go std.

Great catching!