From: Jeff King <peff@peff.net> To: "Martin Ågren" <martin.agren@gmail.com> Cc: Taylor Blau <me@ttaylorr.com>, Git Mailing List <git@vger.kernel.org>, Derrick Stolee <dstolee@microsoft.com>, Junio C Hamano <gitster@pobox.com> Subject: Re: [PATCH 03/23] pack-bitmap: bounds-check size of cache extension Date: Thu, 12 Nov 2020 23:57:00 -0500 [thread overview] Message-ID: <20201113045700.GA743619@coredump.intra.peff.net> (raw) In-Reply-To: <CAN0heSqiiMZgT+rEgWVVR_cEmPK2bS3QNnJuHahrqVQet7_Qug@mail.gmail.com> On Thu, Nov 12, 2020 at 06:47:09PM +0100, Martin Ågren wrote: > > A .bitmap file may have a "name hash cache" extension, which puts a > > sequence of uint32_t bytes (one per object) at the end of the file. When > > s/bytes/values/, perhaps? Yeah, definitely. > > we see a flag indicating this extension, we blindly subtract the > > appropriate number of bytes from our available length. However, if the > > .bitmap file is too short, we'll underflow our length variable and wrap > > around, thinking we have a very large length. This can lead to reading > > out-of-bounds bytes while loading individual ewah bitmaps. > > > + uint32_t cache_size = st_mult(index->pack->num_objects, sizeof(uint32_t)); > > Hmm. If `sizeof(size_t)` is 8, then this multiplication can't possibly > overflow. A huge value of `num_objects` (say, 0xffffffff) would give a > huge return value (0xffffffff<<2) which would be truncated (0xfffffffc). > I think? Yeah, `cache_size` should absolutely be a `size_t`. If you have more than a billion objects, obviously your cache is going to be bigger than that. But most importantly, somebody can _claim_ to have a huge number of objects and foil the size checks by wrapping around. > Do we want a `u32_mult()`? Nah, we should be doing this as a size_t in the first place. There are similar problems with the .idx format, btw. I have a series to deal with that which I've been meaning to post. > > + unsigned char *index_end = index->map + index->map_size - the_hash_algo->rawsz; > > The addition should be ok or mmap has failed on us. Do we know that we > have room for the final hash there so that the subtraction is ok? Yes, > from the previous commit, we know we have room for the header, which is > even larger. But that's cheating a bit -- see below. Yeah, I agree this ought to be checking the minimum size against the header _plus_ the trailer. I think the previous patch is actually where it goes wrong. The original was checking for a minimum of: if (index->map_size < sizeof(*header) + the_hash_algo->rawsz) which is the header plus the trailer. We want to readjust for the MAX_RAWSZ part of the header, so it should be: size_t header_size = sizeof(*header) - GIT_MAX_RAWSZ + the_hash_algo->rawsz; if (index->map_size < sizeof(*header) + the_hash_algo->rawsz) > > + if (index->map + header_size + cache_size > index_end) > > + return error("corrupted bitmap index file (too short to fit hash cache)"); > > + index->hashes = (void *)(index_end - cache_size); > > + index_end -= cache_size; > > If the header size we're adding is indeed too large, the addition in the > check would be undefined behavior, if I'm not mistaken. In practical > terms, with 32-bit pointers and a huge size, we'd wrap around, decide > that everything is ok and go on to do the same erroneous subtraction as > before. > > Maybe shuffle a few things over from the left to the right to only make > subtractions that we know are ok: > > if (cache_size > index_end - index->map - header_size) Yes, I agree this should be done as a subtraction as you showed to avoid integer overflow. > But I don't think we can fully trust those subtractions. We're > subtracting the size of two hashes (one in the header, one in the > footer), but after the previous patch, we only know that there's room > for one. So probably the previous patch could go > > + /* > + * Verify that we have room for the header and the > + * trailing checksum hash, so we can safely subtract > + * their sizes from map_size. We can afford to be > + * a bit imprecise with the error message. > + */ > - if (index->map_size < sizeof(*header) + the_hash_algo->rawsz) > + if (index->map_size < header_size + the_hash_algo->rawsz) > > I *think* I've got most of my comments here somewhat right, but I could > easily have missed something. Right. I think that's right, and the previous patch is just buggy. -Peff
next prev parent reply other threads:[~2020-11-13 4:59 UTC|newest] Thread overview: 173+ messages / expand[flat|nested] mbox.gz Atom feed top 2020-11-11 19:41 [PATCH 00/23] pack-bitmap: bitmap generation improvements Taylor Blau 2020-11-11 19:41 ` [PATCH 01/23] ewah/ewah_bitmap.c: grow buffer past 1 Taylor Blau 2020-11-22 19:36 ` Junio C Hamano 2020-11-23 16:22 ` Taylor Blau 2020-11-24 2:48 ` Jeff King 2020-11-24 2:51 ` Jeff King 2020-12-01 22:56 ` Taylor Blau 2020-11-11 19:41 ` [PATCH 02/23] pack-bitmap: fix header size check Taylor Blau 2020-11-12 17:39 ` Martin Ågren 2020-11-11 19:42 ` [PATCH 03/23] pack-bitmap: bounds-check size of cache extension Taylor Blau 2020-11-12 17:47 ` Martin Ågren 2020-11-13 4:57 ` Jeff King [this message] 2020-11-13 5:26 ` Martin Ågren 2020-11-13 21:29 ` Taylor Blau 2020-11-13 21:39 ` Jeff King 2020-11-13 21:49 ` Taylor Blau 2020-11-13 22:11 ` Jeff King 2020-11-11 19:42 ` [PATCH 04/23] t5310: drop size of truncated ewah bitmap Taylor Blau 2020-11-11 19:42 ` [PATCH 05/23] rev-list: die when --test-bitmap detects a mismatch Taylor Blau 2020-11-11 19:42 ` [PATCH 06/23] ewah: factor out bitmap growth Taylor Blau 2020-11-11 19:42 ` [PATCH 07/23] ewah: make bitmap growth less aggressive Taylor Blau 2020-11-22 20:32 ` Junio C Hamano 2020-11-23 16:49 ` Taylor Blau 2020-11-24 3:00 ` Jeff King 2020-11-24 20:11 ` Junio C Hamano 2020-11-11 19:43 ` [PATCH 08/23] ewah: implement bitmap_or() Taylor Blau 2020-11-22 20:34 ` Junio C Hamano 2020-11-23 16:52 ` Taylor Blau 2020-11-11 19:43 ` [PATCH 09/23] ewah: add bitmap_dup() function Taylor Blau 2020-11-11 19:43 ` [PATCH 10/23] pack-bitmap-write: reimplement bitmap writing Taylor Blau 2020-11-11 19:43 ` [PATCH 11/23] pack-bitmap-write: pass ownership of intermediate bitmaps Taylor Blau 2020-11-11 19:43 ` [PATCH 12/23] pack-bitmap-write: fill bitmap with commit history Taylor Blau 2020-11-11 19:43 ` [PATCH 13/23] bitmap: add bitmap_diff_nonzero() Taylor Blau 2020-11-11 19:43 ` [PATCH 14/23] commit: implement commit_list_contains() Taylor Blau 2020-11-11 19:43 ` [PATCH 15/23] t5310: add branch-based checks Taylor Blau 2020-11-11 20:58 ` Derrick Stolee 2020-11-11 21:04 ` Junio C Hamano 2020-11-15 23:26 ` Johannes Schindelin 2020-11-11 19:43 ` [PATCH 16/23] pack-bitmap-write: rename children to reverse_edges Taylor Blau 2020-11-11 19:43 ` [PATCH 17/23] pack-bitmap-write: build fewer intermediate bitmaps Taylor Blau 2020-11-13 22:23 ` SZEDER Gábor 2020-11-13 23:03 ` Jeff King 2020-11-14 6:23 ` Jeff King 2020-11-11 19:43 ` [PATCH 18/23] pack-bitmap-write: ignore BITMAP_FLAG_REUSE Taylor Blau 2020-11-11 19:44 ` [PATCH 19/23] pack-bitmap: factor out 'bitmap_for_commit()' Taylor Blau 2020-11-11 19:44 ` [PATCH 20/23] pack-bitmap: factor out 'add_commit_to_bitmap()' Taylor Blau 2020-11-11 19:44 ` [PATCH 21/23] pack-bitmap-write: use existing bitmaps Taylor Blau 2020-11-11 19:44 ` [PATCH 22/23] pack-bitmap-write: relax unique rewalk condition Taylor Blau 2020-11-11 19:44 ` [PATCH 23/23] pack-bitmap-write: better reuse bitmaps Taylor Blau 2020-11-17 21:46 ` [PATCH v2 00/24] pack-bitmap: bitmap generation improvements Taylor Blau 2020-11-17 21:46 ` [PATCH v2 01/24] ewah/ewah_bitmap.c: grow buffer past 1 Taylor Blau 2020-11-17 21:46 ` [PATCH v2 02/24] pack-bitmap: fix header size check Taylor Blau 2020-11-17 21:46 ` [PATCH v2 03/24] pack-bitmap: bounds-check size of cache extension Taylor Blau 2020-11-17 21:46 ` [PATCH v2 04/24] t5310: drop size of truncated ewah bitmap Taylor Blau 2020-11-17 21:46 ` [PATCH v2 05/24] rev-list: die when --test-bitmap detects a mismatch Taylor Blau 2020-11-17 21:46 ` [PATCH v2 06/24] ewah: factor out bitmap growth Taylor Blau 2020-11-17 21:47 ` [PATCH v2 07/24] ewah: make bitmap growth less aggressive Taylor Blau 2020-11-17 21:47 ` [PATCH v2 08/24] ewah: implement bitmap_or() Taylor Blau 2020-11-17 21:47 ` [PATCH v2 09/24] ewah: add bitmap_dup() function Taylor Blau 2020-11-17 21:47 ` [PATCH v2 10/24] pack-bitmap-write: reimplement bitmap writing Taylor Blau 2020-11-25 0:53 ` Jonathan Tan 2020-11-28 17:27 ` Taylor Blau 2020-11-17 21:47 ` [PATCH v2 11/24] pack-bitmap-write: pass ownership of intermediate bitmaps Taylor Blau 2020-11-25 1:00 ` Jonathan Tan 2020-11-17 21:47 ` [PATCH v2 12/24] pack-bitmap-write: fill bitmap with commit history Taylor Blau 2020-11-22 21:50 ` Junio C Hamano 2020-11-23 14:54 ` Derrick Stolee 2020-11-25 1:14 ` Jonathan Tan 2020-11-28 17:21 ` Taylor Blau 2020-11-30 18:33 ` Jonathan Tan 2020-11-17 21:47 ` [PATCH v2 13/24] bitmap: add bitmap_diff_nonzero() Taylor Blau 2020-11-22 22:01 ` Junio C Hamano 2020-11-23 20:19 ` Taylor Blau 2020-11-17 21:47 ` [PATCH v2 14/24] commit: implement commit_list_contains() Taylor Blau 2020-11-17 21:47 ` [PATCH v2 15/24] t5310: add branch-based checks Taylor Blau 2020-11-25 1:17 ` Jonathan Tan 2020-11-28 17:30 ` Taylor Blau 2020-11-17 21:47 ` [PATCH v2 16/24] pack-bitmap-write: rename children to reverse_edges Taylor Blau 2020-11-17 21:47 ` [PATCH v2 17/24] pack-bitmap.c: check reads more aggressively when loading Taylor Blau 2020-11-17 21:48 ` [PATCH v2 18/24] pack-bitmap-write: build fewer intermediate bitmaps Taylor Blau 2020-11-24 6:07 ` Jonathan Tan 2020-11-25 1:46 ` Jonathan Tan 2020-11-30 18:41 ` Derrick Stolee 2020-11-17 21:48 ` [PATCH v2 19/24] pack-bitmap-write: ignore BITMAP_FLAG_REUSE Taylor Blau 2020-12-02 7:13 ` Jonathan Tan 2020-11-17 21:48 ` [PATCH v2 20/24] pack-bitmap: factor out 'bitmap_for_commit()' Taylor Blau 2020-12-02 7:17 ` Jonathan Tan 2020-11-17 21:48 ` [PATCH v2 21/24] pack-bitmap: factor out 'add_commit_to_bitmap()' Taylor Blau 2020-12-02 7:20 ` Jonathan Tan 2020-11-17 21:48 ` [PATCH v2 22/24] pack-bitmap-write: use existing bitmaps Taylor Blau 2020-12-02 7:28 ` Jonathan Tan 2020-12-02 16:21 ` Taylor Blau 2020-11-17 21:48 ` [PATCH v2 23/24] pack-bitmap-write: relax unique rewalk condition Taylor Blau 2020-12-02 7:44 ` Jonathan Tan 2020-12-02 16:30 ` Taylor Blau 2020-12-07 18:19 ` Jonathan Tan 2020-12-07 18:43 ` Derrick Stolee 2020-12-07 18:45 ` Derrick Stolee 2020-12-07 18:48 ` Jeff King 2020-11-17 21:48 ` [PATCH v2 24/24] pack-bitmap-write: better reuse bitmaps Taylor Blau 2020-12-02 8:08 ` Jonathan Tan 2020-12-02 16:35 ` Taylor Blau 2020-12-02 18:22 ` Derrick Stolee 2020-12-02 18:25 ` Taylor Blau 2020-12-07 18:26 ` Jonathan Tan 2020-12-07 18:24 ` Jonathan Tan 2020-12-07 19:20 ` Derrick Stolee 2020-11-18 18:32 ` [PATCH v2 00/24] pack-bitmap: bitmap generation improvements SZEDER Gábor 2020-11-18 19:51 ` Taylor Blau 2020-11-22 2:17 ` Taylor Blau 2020-11-22 2:28 ` Taylor Blau 2020-11-20 6:34 ` Martin Ågren 2020-11-21 19:37 ` Junio C Hamano 2020-11-21 20:11 ` Martin Ågren 2020-11-22 2:31 ` Taylor Blau 2020-11-24 2:43 ` Jeff King 2020-12-01 23:04 ` Taylor Blau 2020-12-01 23:37 ` Jonathan Tan 2020-12-01 23:43 ` Taylor Blau 2020-12-02 8:11 ` Jonathan Tan 2020-12-08 0:04 ` [PATCH v3 " Taylor Blau 2020-12-08 0:04 ` [PATCH v3 01/24] ewah/ewah_bitmap.c: avoid open-coding ALLOC_GROW() Taylor Blau 2020-12-08 0:04 ` [PATCH v3 02/24] pack-bitmap: fix header size check Taylor Blau 2020-12-08 0:04 ` [PATCH v3 03/24] pack-bitmap: bounds-check size of cache extension Taylor Blau 2020-12-08 0:04 ` [PATCH v3 04/24] t5310: drop size of truncated ewah bitmap Taylor Blau 2020-12-08 0:04 ` [PATCH v3 05/24] rev-list: die when --test-bitmap detects a mismatch Taylor Blau 2020-12-08 0:04 ` [PATCH v3 06/24] ewah: factor out bitmap growth Taylor Blau 2020-12-08 0:04 ` [PATCH v3 07/24] ewah: make bitmap growth less aggressive Taylor Blau 2020-12-08 0:04 ` [PATCH v3 08/24] ewah: implement bitmap_or() Taylor Blau 2020-12-08 0:04 ` [PATCH v3 09/24] ewah: add bitmap_dup() function Taylor Blau 2020-12-08 0:04 ` [PATCH v3 10/24] pack-bitmap-write: reimplement bitmap writing Taylor Blau 2020-12-08 0:05 ` [PATCH v3 11/24] pack-bitmap-write: pass ownership of intermediate bitmaps Taylor Blau 2020-12-08 0:05 ` [PATCH v3 12/24] pack-bitmap-write: fill bitmap with commit history Taylor Blau 2020-12-08 0:05 ` [PATCH v3 13/24] bitmap: implement bitmap_is_subset() Taylor Blau 2020-12-08 0:05 ` [PATCH v3 14/24] commit: implement commit_list_contains() Taylor Blau 2020-12-08 0:05 ` [PATCH v3 15/24] t5310: add branch-based checks Taylor Blau 2020-12-08 0:05 ` [PATCH v3 16/24] pack-bitmap-write: rename children to reverse_edges Taylor Blau 2020-12-08 0:05 ` [PATCH v3 17/24] pack-bitmap.c: check reads more aggressively when loading Taylor Blau 2020-12-08 0:05 ` [PATCH v3 18/24] pack-bitmap-write: build fewer intermediate bitmaps Taylor Blau 2020-12-08 0:05 ` [PATCH v3 19/24] pack-bitmap-write: ignore BITMAP_FLAG_REUSE Taylor Blau 2020-12-08 0:05 ` [PATCH v3 20/24] pack-bitmap: factor out 'bitmap_for_commit()' Taylor Blau 2020-12-08 0:05 ` [PATCH v3 21/24] pack-bitmap: factor out 'add_commit_to_bitmap()' Taylor Blau 2020-12-08 0:05 ` [PATCH v3 22/24] pack-bitmap-write: use existing bitmaps Taylor Blau 2020-12-08 0:05 ` [PATCH v3 23/24] pack-bitmap-write: relax unique rewalk condition Taylor Blau 2020-12-08 0:05 ` [PATCH v3 24/24] pack-bitmap-write: better reuse bitmaps Taylor Blau 2020-12-08 20:56 ` [PATCH v3 00/24] pack-bitmap: bitmap generation improvements Junio C Hamano 2020-12-08 21:03 ` Taylor Blau 2020-12-08 22:03 ` Junio C Hamano 2020-12-08 22:03 ` [PATCH v4 " Taylor Blau 2020-12-08 22:03 ` [PATCH v4 01/24] ewah/ewah_bitmap.c: avoid open-coding ALLOC_GROW() Taylor Blau 2020-12-08 22:03 ` [PATCH v4 02/24] pack-bitmap: fix header size check Taylor Blau 2020-12-08 22:03 ` [PATCH v4 03/24] pack-bitmap: bounds-check size of cache extension Taylor Blau 2020-12-08 22:03 ` [PATCH v4 04/24] t5310: drop size of truncated ewah bitmap Taylor Blau 2020-12-08 22:03 ` [PATCH v4 05/24] rev-list: die when --test-bitmap detects a mismatch Taylor Blau 2020-12-08 22:03 ` [PATCH v4 06/24] ewah: factor out bitmap growth Taylor Blau 2020-12-08 22:03 ` [PATCH v4 07/24] ewah: make bitmap growth less aggressive Taylor Blau 2020-12-08 22:03 ` [PATCH v4 08/24] ewah: implement bitmap_or() Taylor Blau 2020-12-08 22:03 ` [PATCH v4 09/24] ewah: add bitmap_dup() function Taylor Blau 2020-12-08 22:03 ` [PATCH v4 10/24] pack-bitmap-write: reimplement bitmap writing Taylor Blau 2020-12-08 22:03 ` [PATCH v4 11/24] pack-bitmap-write: pass ownership of intermediate bitmaps Taylor Blau 2020-12-08 22:04 ` [PATCH v4 12/24] pack-bitmap-write: fill bitmap with commit history Taylor Blau 2020-12-08 22:04 ` [PATCH v4 13/24] bitmap: implement bitmap_is_subset() Taylor Blau 2020-12-08 22:04 ` [PATCH v4 14/24] commit: implement commit_list_contains() Taylor Blau 2020-12-08 22:04 ` [PATCH v4 15/24] t5310: add branch-based checks Taylor Blau 2020-12-08 22:04 ` [PATCH v4 16/24] pack-bitmap-write: rename children to reverse_edges Taylor Blau 2020-12-08 22:04 ` [PATCH v4 17/24] pack-bitmap.c: check reads more aggressively when loading Taylor Blau 2020-12-08 22:04 ` [PATCH v4 18/24] pack-bitmap-write: build fewer intermediate bitmaps Taylor Blau 2020-12-08 22:04 ` [PATCH v4 19/24] pack-bitmap-write: ignore BITMAP_FLAG_REUSE Taylor Blau 2020-12-08 22:04 ` [PATCH v4 20/24] pack-bitmap: factor out 'bitmap_for_commit()' Taylor Blau 2020-12-08 22:05 ` [PATCH v4 21/24] pack-bitmap: factor out 'add_commit_to_bitmap()' Taylor Blau 2020-12-08 22:05 ` [PATCH v4 22/24] pack-bitmap-write: use existing bitmaps Taylor Blau 2020-12-08 22:05 ` [PATCH v4 23/24] pack-bitmap-write: relax unique revwalk condition Taylor Blau 2020-12-08 22:05 ` [PATCH v4 24/24] pack-bitmap-write: better reuse bitmaps Taylor Blau
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style List information: http://vger.kernel.org/majordomo-info.html * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20201113045700.GA743619@coredump.intra.peff.net \ --to=peff@peff.net \ --cc=dstolee@microsoft.com \ --cc=git@vger.kernel.org \ --cc=gitster@pobox.com \ --cc=martin.agren@gmail.com \ --cc=me@ttaylorr.com \ --subject='Re: [PATCH 03/23] pack-bitmap: bounds-check size of cache extension' \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
Code repositories for project(s) associated with this inbox: https://80x24.org/mirrors/git.git This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).