Skip to content

Commit d4d24cb

Browse files
pjbgfpjbgf
authored
Merge pull request #2119 from hiddeco/format-input-bounds
plumbing: format decoder input bounds and contracts
2 parents 54900a9 + 832a692 commit d4d24cb

17 files changed

Lines changed: 1018 additions & 287 deletions

File tree

‎plumbing/format/gitignore/pattern.go‎

Lines changed: 305 additions & 217 deletions
Large diffs are not rendered by default.

‎plumbing/format/idxfile/decoder.go‎

Lines changed: 160 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,7 @@ import (
66
"errors"
77
"fmt"
88
"io"
9+
"io/fs"
910

1011
"github.com/go-git/go-git/v6/plumbing/hash"
1112
"github.com/go-git/go-git/v6/utils/binary"
@@ -23,42 +24,87 @@ const (
2324
fanout = 256
2425
)
2526

26-
// Decoder reads and decodes idx files from an input stream.
27-
type Decoder struct {
27+
// Byte sizes of the idx v2 layout elements, used by the size formula
28+
// in [validateIdxV2Size]. See [gitformat-pack] for the canonical
29+
// layout.
30+
//
31+
// [gitformat-pack]: https://git-scm.com/docs/gitformat-pack
32+
const (
33+
headerLen = 8 // magic + version
34+
fanoutLen = fanout * 4 // uint32 per bucket
35+
crc32Len = 4 // CRC32 per object
36+
offset32Len = 4 // 32-bit offset per object
37+
offset64Len = 8 // 64-bit overflow offset
38+
trailerHashes = 2 // pack checksum + idx checksum, each hashsz
39+
)
40+
41+
// Input is the input to a [Decoder]. The decoder reads loose-object
42+
// bytes from it and calls Stat to learn the on-disk length, which it
43+
// uses to validate the canonical-Git size formula before any
44+
// allocations driven by the fanout table.
45+
//
46+
// [os.File] and the go-billy [File] type satisfy Input directly.
47+
//
48+
// [File]: https://pkg.go.dev/github.com/go-git/go-billy/v6#File
49+
type Input interface {
2850
io.Reader
29-
h hash.Hash
51+
Stat() (fs.FileInfo, error)
52+
}
53+
54+
// Decoder reads and decodes idx files from an [Input].
55+
type Decoder struct {
56+
in Input
57+
h hash.Hash
3058
}
3159

32-
// NewDecoder builds a new idx stream decoder, that reads from r.
33-
func NewDecoder(r io.Reader, h hash.Hash) *Decoder {
34-
tr := io.TeeReader(r, h)
35-
return &Decoder{tr, h}
60+
// NewDecoder builds a new idx decoder that reads from in.
61+
func NewDecoder(in Input, h hash.Hash) *Decoder {
62+
return &Decoder{in, h}
3663
}
3764

38-
// Decode reads from the stream and decode the content into the MemoryIndex struct.
65+
// Decode reads from the input and decodes the content into idx.
3966
func (d *Decoder) Decode(idx *MemoryIndex) error {
67+
fi, err := d.in.Stat()
68+
if err != nil {
69+
return fmt.Errorf("%w: stat input: %w", ErrMalformedIdxFile, err)
70+
}
71+
idxSize := fi.Size()
72+
4073
d.h.Reset()
41-
if err := validateHeader(d); err != nil {
74+
r := io.TeeReader(d.in, d.h)
75+
76+
if err := validateHeader(r); err != nil {
4277
return err
4378
}
4479

45-
flow := []func(*MemoryIndex, io.Reader) error{
80+
headerFlow := []func(*MemoryIndex, io.Reader) error{
4681
readVersion,
4782
readFanout,
83+
}
84+
for _, f := range headerFlow {
85+
if err := f(idx, r); err != nil {
86+
return err
87+
}
88+
}
89+
90+
if err := validateIdxV2Size(idx, idxSize); err != nil {
91+
return err
92+
}
93+
94+
bodyFlow := []func(*MemoryIndex, io.Reader) error{
4895
readObjectNames,
4996
readCRC32,
5097
readOffsets,
5198
readPackChecksum,
5299
}
53-
54-
for _, f := range flow {
55-
if err := f(idx, d); err != nil {
100+
for _, f := range bodyFlow {
101+
if err := f(idx, r); err != nil {
56102
return err
57103
}
58104
}
59105

60106
actual := d.h.Sum(nil)
61-
if err := readIdxChecksum(idx, d); err != nil {
107+
if err := readIdxChecksum(idx, r); err != nil {
62108
return err
63109
}
64110

@@ -200,3 +246,103 @@ func readIdxChecksum(idx *MemoryIndex, r io.Reader) error {
200246

201247
return nil
202248
}
249+
250+
// validateIdxV2Size enforces the size formula used by canonical Git
251+
// load_idx for idx v2 files: the on-disk length must lie within
252+
// [minSize, maxSize] where
253+
//
254+
// perObject = hashsz + crc32Len + offset32Len
255+
// minSize = headerLen + fanoutLen + trailerHashes*hashsz + nr*perObject
256+
// maxSize = minSize + (nr-1)*offset64Len when nr > 0
257+
//
258+
// with nr taken from the last fanout entry and hashsz from the
259+
// configured object ID size. Multiplications use a self-checking
260+
// overflow guard so inputs whose claimed object count overflows the
261+
// formula are rejected rather than wrapping into a smaller value.
262+
func validateIdxV2Size(idx *MemoryIndex, idxSize int64) error {
263+
nr := int64(idx.Fanout[fanout-1])
264+
hashsz := int64(idx.idSize())
265+
266+
minSize := minIdxV2Size(nr, hashsz)
267+
maxSize := maxIdxV2Size(nr, hashsz)
268+
if minSize < 0 || maxSize < 0 {
269+
return fmt.Errorf("%w: object count %d is inconsistent with file size", ErrMalformedIdxFile, nr)
270+
}
271+
272+
if idxSize < minSize || idxSize > maxSize {
273+
return fmt.Errorf("%w: file size %d is inconsistent with object count %d", ErrMalformedIdxFile, idxSize, nr)
274+
}
275+
return nil
276+
}
277+
278+
// minIdxV2Size returns the minimum on-disk size of an idx v2 file
279+
// holding nr objects with the given hash size, mirroring the
280+
// computation in canonical Git load_idx. Returns -1 when any
281+
// intermediate multiplication or addition would overflow int64.
282+
func minIdxV2Size(nr, hashsz int64) int64 {
283+
perObject := hashsz + crc32Len + offset32Len
284+
fixed := int64(headerLen+fanoutLen) + trailerHashes*hashsz
285+
286+
objects, ok := mulInt64(nr, perObject)
287+
if !ok {
288+
return -1
289+
}
290+
sum, ok := addInt64(fixed, objects)
291+
if !ok {
292+
return -1
293+
}
294+
return sum
295+
}
296+
297+
// maxIdxV2Size returns the maximum on-disk size of an idx v2 file
298+
// holding nr objects with the given hash size, mirroring the
299+
// computation in canonical Git load_idx. Returns -1 on overflow.
300+
func maxIdxV2Size(nr, hashsz int64) int64 {
301+
minSize := minIdxV2Size(nr, hashsz)
302+
if minSize < 0 {
303+
return -1
304+
}
305+
if nr == 0 {
306+
return minSize
307+
}
308+
overflow, ok := mulInt64(nr-1, offset64Len)
309+
if !ok {
310+
return -1
311+
}
312+
sum, ok := addInt64(minSize, overflow)
313+
if !ok {
314+
return -1
315+
}
316+
return sum
317+
}
318+
319+
// mulInt64 returns a*b and whether the result fits in an int64 without
320+
// overflow. Negative operands or overflow yield ok=false. The overflow
321+
// check uses the standard self-inverse identity: a*b/b == a only when
322+
// the multiplication did not wrap.
323+
func mulInt64(a, b int64) (int64, bool) {
324+
if a < 0 || b < 0 {
325+
return 0, false
326+
}
327+
if a == 0 || b == 0 {
328+
return 0, true
329+
}
330+
c := a * b
331+
if c/b != a {
332+
return 0, false
333+
}
334+
return c, true
335+
}
336+
337+
// addInt64 returns a+b and whether the result fits in an int64 without
338+
// overflow. Negative operands or overflow yield ok=false.
339+
func addInt64(a, b int64) (int64, bool) {
340+
if a < 0 || b < 0 {
341+
return 0, false
342+
}
343+
c := a + b
344+
if c < a {
345+
return 0, false
346+
}
347+
return c, true
348+
}

‎plumbing/format/idxfile/decoder_test.go‎

Lines changed: 98 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@ import (
55
"crypto"
66
"encoding/base64"
77
"encoding/binary"
8+
"errors"
89
"io"
910
"testing"
1011

@@ -57,12 +58,13 @@ func (s *IdxfileSuite) TestDecode() {
5758
}
5859

5960
func (s *IdxfileSuite) TestDecode64bitsOffsets() {
60-
f := bytes.NewBufferString(fixtureLarge4GB)
61+
raw, err := io.ReadAll(base64.NewDecoder(base64.StdEncoding, bytes.NewBufferString(fixtureLarge4GB)))
62+
s.Require().NoError(err)
6163

6264
idx := new(MemoryIndex)
6365

64-
d := NewDecoder(base64.NewDecoder(base64.StdEncoding, f), hash.New(crypto.SHA1))
65-
err := d.Decode(idx)
66+
d := NewDecoder(FromBytes(raw), hash.New(crypto.SHA1))
67+
err = d.Decode(idx)
6668
s.NoError(err)
6769

6870
expected := map[string]uint64{
@@ -135,9 +137,8 @@ func BenchmarkDecode(b *testing.B) {
135137

136138
hasher := hash.New(crypto.SHA1)
137139
for b.Loop() {
138-
f := bytes.NewBuffer(fixture)
139140
idx := new(MemoryIndex)
140-
d := NewDecoder(f, hasher)
141+
d := NewDecoder(FromBytes(fixture), hasher)
141142
if err := d.Decode(idx); err != nil {
142143
b.Errorf("unexpected error decoding: %s", err)
143144
}
@@ -238,7 +239,12 @@ func TestDecodeErrors(t *testing.T) {
238239
buf = append(buf, writeFanout(1, nil)...)
239240
return buf
240241
},
241-
wantErr: io.EOF,
242+
// The size formula now rejects the input before the
243+
// reader gets a chance to report EOF: a single-object
244+
// idx v2 needs at least 1100 bytes for SHA-1, and the
245+
// header+fanout alone is only 1032.
246+
wantErr: ErrMalformedIdxFile,
247+
wantErrContains: "inconsistent with object count",
242248
},
243249
{
244250
name: "checksum mismatch",
@@ -259,7 +265,7 @@ func TestDecodeErrors(t *testing.T) {
259265
t.Parallel()
260266

261267
idx := new(MemoryIndex)
262-
d := NewDecoder(bytes.NewReader(tt.input()), hash.New(crypto.SHA1))
268+
d := NewDecoder(FromBytes(tt.input()), hash.New(crypto.SHA1))
263269

264270
err := d.Decode(idx)
265271
require.Error(t, err)
@@ -297,3 +303,88 @@ func idxV2Header() []byte {
297303
binary.Write(&buf, binary.BigEndian, uint32(2))
298304
return buf.Bytes()
299305
}
306+
307+
// TestDecoderSizeFormulaBoundary exercises the [minSize, maxSize] range
308+
// enforced by validateIdxV2Size. The boundary is asymmetric for nr > 1:
309+
// each extra 8-byte offset64 slot extends maxSize by 8. Inputs at the
310+
// edge of the legal range must pass the size check (failing later with
311+
// the trailing checksum mismatch, since the payload is zero-filled);
312+
// inputs one byte outside must be rejected with a size-related error.
313+
func TestDecoderSizeFormulaBoundary(t *testing.T) {
314+
t.Parallel()
315+
316+
const hashsz = 20 // SHA-1
317+
const headerLen = 8 + 4*256
318+
minSize := func(nr int64) int64 {
319+
return headerLen + nr*(hashsz+8) + 2*hashsz
320+
}
321+
maxSize := func(nr int64) int64 {
322+
m := minSize(nr)
323+
if nr > 0 {
324+
m += (nr - 1) * 8
325+
}
326+
return m
327+
}
328+
build := func(nr uint32, total int64) []byte {
329+
buf := append(idxV2Header(), writeFanout(nr, nil)...)
330+
if int64(len(buf)) > total {
331+
t.Fatalf("header+fanout exceeds requested total: %d > %d", len(buf), total)
332+
}
333+
return append(buf, make([]byte, total-int64(len(buf)))...)
334+
}
335+
336+
tests := []struct {
337+
name string
338+
nr uint32
339+
size int64
340+
passesLen bool // true: size check passes (later parsing may fail)
341+
}{
342+
{"nr=1, at minSize", 1, minSize(1), true},
343+
{"nr=1, one byte below minSize", 1, minSize(1) - 1, false},
344+
{"nr=1, one byte above maxSize", 1, maxSize(1) + 1, false},
345+
{"nr=2, at minSize", 2, minSize(2), true},
346+
{"nr=2, at maxSize", 2, maxSize(2), true},
347+
{"nr=2, one byte below minSize", 2, minSize(2) - 1, false},
348+
{"nr=2, one byte above maxSize", 2, maxSize(2) + 1, false},
349+
}
350+
351+
for _, tt := range tests {
352+
t.Run(tt.name, func(t *testing.T) {
353+
t.Parallel()
354+
355+
idx := new(MemoryIndex)
356+
d := NewDecoder(FromBytes(build(tt.nr, tt.size)), hash.New(crypto.SHA1))
357+
err := d.Decode(idx)
358+
require.Error(t, err)
359+
require.ErrorIs(t, err, ErrMalformedIdxFile)
360+
if tt.passesLen {
361+
// Payload is zero-filled, so we reach the trailing
362+
// checksum comparison and fail there. The size check
363+
// itself must not fire.
364+
require.ErrorContains(t, err, "checksum mismatch")
365+
} else {
366+
require.ErrorContains(t, err, "inconsistent with object count")
367+
}
368+
})
369+
}
370+
}
371+
372+
func TestDecoderRejectsInconsistentObjectCount(t *testing.T) {
373+
t.Parallel()
374+
375+
// Header (\xff t O c) + version 2 + fanout where fanout[0..255] all
376+
// claim 0x4C4C4C4C objects. The byte count cannot possibly accommodate
377+
// that many object names.
378+
var buf bytes.Buffer
379+
buf.Write([]byte{0xff, 't', 'O', 'c', 0, 0, 0, 2})
380+
for range 256 {
381+
_ = binary.Write(&buf, binary.BigEndian, uint32(0x4C4C4C4C))
382+
}
383+
384+
idx := new(MemoryIndex)
385+
d := NewDecoder(FromBytes(buf.Bytes()), hash.New(crypto.SHA1))
386+
err := d.Decode(idx)
387+
if !errors.Is(err, ErrMalformedIdxFile) {
388+
t.Fatalf("expected ErrMalformedIdxFile, got %v", err)
389+
}
390+
}

‎plumbing/format/idxfile/encoder_test.go‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -27,7 +27,7 @@ func TestEncode(t *testing.T) {
2727

2828
validIdxFn := func() *MemoryIndex {
2929
idx := NewMemoryIndex(crypto.SHA1.Size())
30-
d := NewDecoder(bytes.NewBuffer(expected), hash.New(crypto.SHA1))
30+
d := NewDecoder(FromBytes(expected), hash.New(crypto.SHA1))
3131
err := d.Decode(idx)
3232
require.NoError(t, err)
3333
return idx
@@ -152,7 +152,7 @@ func TestEncodeDecodeRoundTrip(t *testing.T) {
152152
require.NoError(t, err)
153153

154154
idx := NewMemoryIndex(tc.hasher.Size())
155-
d := NewDecoder(bytes.NewBuffer(expected), hash.New(tc.hasher))
155+
d := NewDecoder(FromBytes(expected), hash.New(tc.hasher))
156156
err = d.Decode(idx)
157157
require.NoError(t, err)
158158

@@ -181,7 +181,7 @@ func TestDecodeEncode(t *testing.T) {
181181
}
182182

183183
idx := NewMemoryIndex(h.Size())
184-
d := NewDecoder(bytes.NewBuffer(expected), hash.New(h))
184+
d := NewDecoder(FromBytes(expected), hash.New(h))
185185
err = d.Decode(idx)
186186
require.NoError(t, err)
187187

0 commit comments

Comments
 (0)