Avoid infinite loop in malformed packfiles

Commit Message

Ori Bernstein Aug. 23, 2020, 12:52 a.m. UTC

In packfile.c:1680, there's an infinite loop that tries to get
to the base of a packfile. With offset deltas, the offset needs
to be greater than 0, so it's always walking backwards, and the
search is guaranteed to terminate.

With reference deltas, there's no check for a cycle in the
references, so a cyclic reference will cause git to loop
infinitely, growing the delta_stack infinitely, which will
cause it to consume all available memory as as a full CPU
core.

This change puts an arbitrary limit of 10,000 on the number
of iterations we make when chasing down a base commit, to
prevent looping forever, using all available memory growing
the delta stack.
---
 packfile.c | 7 +++++++
 1 file changed, 7 insertions(+)

Comments

Ori Bernstein Aug. 23, 2020, 2:52 a.m. UTC | #1

> In packfile.c:1680, there's an infinite loop that tries to get
> to the base of a packfile. With offset deltas, the offset needs
> to be greater than 0, so it's always walking backwards, and the
> search is guaranteed to terminate.
> 
> With reference deltas, there's no check for a cycle in the
> references, so a cyclic reference will cause git to loop
> infinitely, growing the delta_stack infinitely, which will
> cause it to consume all available memory as as a full CPU
> core.
> 
> This change puts an arbitrary limit of 10,000 on the number
> of iterations we make when chasing down a base commit, to
> prevent looping forever, using all available memory growing
> the delta stack.

For context, I discovered this accidentally when I
introduced a bug in pack deltification in git9 (my
implementation of git for plan 9). An example of a
packfile and index that will reproduce this issue
is available here:

https://eigenstate.org/tmp/95a0f4f3f3f21d723d501552eaf22ff4055e13a4.pack
https://eigenstate.org/tmp/95a0f4f3f3f21d723d501552eaf22ff4055e13a4.idx

The suggestion to just cap the depth instead of
doing full cycle detection came from Jeff King
([e-mail])

Eric Sunshine Aug. 23, 2020, 3:08 a.m. UTC | #2

On Sat, Aug 22, 2020 at 8:59 PM Ori Bernstein <[e-mail]> wrote:
> In packfile.c:1680, there's an infinite loop that tries to get
> to the base of a packfile. With offset deltas, the offset needs
> to be greater than 0, so it's always walking backwards, and the
> search is guaranteed to terminate.
>
> With reference deltas, there's no check for a cycle in the
> references, so a cyclic reference will cause git to loop
> infinitely, growing the delta_stack infinitely, which will
> cause it to consume all available memory as as a full CPU
> core.
>
> This change puts an arbitrary limit of 10,000 on the number
> of iterations we make when chasing down a base commit, to
> prevent looping forever, using all available memory growing
> the delta stack.
> ---

Missing sign-off.

Junio C Hamano Aug. 24, 2020, 8:30 p.m. UTC | #3

Ori Bernstein <[e-mail]> writes:

> Subject: Re: [PATCH] Avoid infinite loop in malformed packfiles

Documentation/SubmittingPatches[[summary-section]]. Perhaps

    packfile: avoid infinite loop with malformed packfiles

> In packfile.c:1680, there's an infinite loop that tries to get

The line numbers can easily change.  "In packfile.c::unpack_entry(),
there is..." may be more change-resistant.

Patch

diff --git a/packfile.c b/packfile.c
index 6ab5233613..321e002c50 100644
--- a/packfile.c
+++ b/packfile.c
@@ -1633,6 +1633,7 @@  static void write_pack_access_log(struct packed_git *p, off_t obj_offset)
 
 int do_check_packed_object_crc;
 
+#define UNPACK_ENTRY_STACK_LIMIT 10000
 #define UNPACK_ENTRY_STACK_PREALLOC 64
 struct unpack_entry_stack_ent {
 	off_t obj_offset;
@@ -1715,6 +1716,12 @@  void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,
 			break;
 		}
 
+		if (delta_stack_nr > UNPACK_ENTRY_STACK_LIMIT) {
+			error("overlong delta chain at offset %jd from %s",
+			      (uintmax_t)curpos, p->pack_name);
+			goto out;
+		}
+
 		/* push object, proceed to base */
 		if (delta_stack_nr >= delta_stack_alloc
 		    && delta_stack == small_delta_stack) {