[PATCH 0/2] Add commit-graph fuzzer and fix buffer overflow

[PATCH 0/2] Add commit-graph fuzzer and fix buffer overflow

[Josh Steadmon]

Add a new fuzz test for the commit graph and fix a buffer read-overflow
that it discovered.

Josh Steadmon (2):
  commit-graph, fuzz: Add fuzzer for commit-graph
  commit-graph: fix buffer read-overflow

 .gitignore          |  1 +
 Makefile            |  1 +
 commit-graph.c      | 76 +++++++++++++++++++++++++++++++++------------
 fuzz-commit-graph.c | 18 +++++++++++
 4 files changed, 77 insertions(+), 19 deletions(-)
 create mode 100644 fuzz-commit-graph.c

-- 
2.20.0.rc2.403.gdbc3b29805-goog

[PATCH 1/2] commit-graph, fuzz: Add fuzzer for commit-graph

[Josh Steadmon]

Breaks load_commit_graph_one() into a new function,
parse_commit_graph(). The latter function operates on arbitrary buffers,
which makes it suitable as a fuzzing target.

Adds fuzz-commit-graph.c, which provides a fuzzing entry point
compatible with libFuzzer (and possibly other fuzzing engines).

Signed-off-by: Josh Steadmon <steadmon@google.com>
---
 .gitignore          |  1 +
 Makefile            |  1 +
 commit-graph.c      | 63 +++++++++++++++++++++++++++++++++------------
 fuzz-commit-graph.c | 18 +++++++++++++
 4 files changed, 66 insertions(+), 17 deletions(-)
 create mode 100644 fuzz-commit-graph.c

diff --git a/.gitignore b/.gitignore
index 0d77ea5894..8bcf153ed9 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,4 @@
+/fuzz-commit-graph
 /fuzz_corpora
 /fuzz-pack-headers
 /fuzz-pack-idx
diff --git a/Makefile b/Makefile
index 1a44c811aa..6b72f37c29 100644
--- a/Makefile
+++ b/Makefile
@@ -684,6 +684,7 @@ SCRIPTS = $(SCRIPT_SH_INS) \
 
 ETAGS_TARGET = TAGS
 
+FUZZ_OBJS += fuzz-commit-graph.o
 FUZZ_OBJS += fuzz-pack-headers.o
 FUZZ_OBJS += fuzz-pack-idx.o
 
diff --git a/commit-graph.c b/commit-graph.c
index 40c855f185..0755359b1a 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -46,6 +46,10 @@
 #define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * GRAPH_CHUNKLOOKUP_WIDTH \
 			+ GRAPH_FANOUT_SIZE + GRAPH_OID_LEN)
 
+struct commit_graph *parse_commit_graph(void *graph_map, int fd,
+					size_t graph_size);
+
+
 char *get_commit_graph_filename(const char *obj_dir)
 {
 	return xstrfmt("%s/info/commit-graph", obj_dir);
@@ -84,16 +88,10 @@ static int commit_graph_compatible(struct repository *r)
 struct commit_graph *load_commit_graph_one(const char *graph_file)
 {
 	void *graph_map;
-	const unsigned char *data, *chunk_lookup;
 	size_t graph_size;
 	struct stat st;
-	uint32_t i;
-	struct commit_graph *graph;
+	struct commit_graph *ret;
 	int fd = git_open(graph_file);
-	uint64_t last_chunk_offset;
-	uint32_t last_chunk_id;
-	uint32_t graph_signature;
-	unsigned char graph_version, hash_version;
 
 	if (fd < 0)
 		return NULL;
@@ -108,27 +106,61 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 		die(_("graph file %s is too small"), graph_file);
 	}
 	graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);
+	ret = parse_commit_graph(graph_map, fd, graph_size);
+
+	if (ret == NULL) {
+		munmap(graph_map, graph_size);
+		close(fd);
+		exit(1);
+	}
+
+	return ret;
+}
+
+/*
+ * This function is intended to be used only from load_commit_graph_one() or in
+ * fuzz tests.
+ */
+struct commit_graph *parse_commit_graph(void *graph_map, int fd,
+					size_t graph_size)
+{
+	const unsigned char *data, *chunk_lookup;
+	uint32_t i;
+	struct commit_graph *graph;
+	uint64_t last_chunk_offset;
+	uint32_t last_chunk_id;
+	uint32_t graph_signature;
+	unsigned char graph_version, hash_version;
+
+	/*
+	 * This should already be checked in load_commit_graph_one, but we still
+	 * need a check here for when we're calling parse_commit_graph directly
+	 * from fuzz tests. We can omit the error message in that case.
+	 */
+	if (graph_size < GRAPH_MIN_SIZE)
+		return NULL;
+
 	data = (const unsigned char *)graph_map;
 
 	graph_signature = get_be32(data);
 	if (graph_signature != GRAPH_SIGNATURE) {
 		error(_("graph signature %X does not match signature %X"),
 		      graph_signature, GRAPH_SIGNATURE);
-		goto cleanup_fail;
+		return NULL;
 	}
 
 	graph_version = *(unsigned char*)(data + 4);
 	if (graph_version != GRAPH_VERSION) {
 		error(_("graph version %X does not match version %X"),
 		      graph_version, GRAPH_VERSION);
-		goto cleanup_fail;
+		return NULL;
 	}
 
 	hash_version = *(unsigned char*)(data + 5);
 	if (hash_version != GRAPH_OID_VERSION) {
 		error(_("hash version %X does not match version %X"),
 		      hash_version, GRAPH_OID_VERSION);
-		goto cleanup_fail;
+		return NULL;
 	}
 
 	graph = alloc_commit_graph();
@@ -152,7 +184,8 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 		if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
 			error(_("improper chunk offset %08x%08x"), (uint32_t)(chunk_offset >> 32),
 			      (uint32_t)chunk_offset);
-			goto cleanup_fail;
+			free(graph);
+			return NULL;
 		}
 
 		switch (chunk_id) {
@@ -187,7 +220,8 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 
 		if (chunk_repeated) {
 			error(_("chunk id %08x appears multiple times"), chunk_id);
-			goto cleanup_fail;
+			free(graph);
+			return NULL;
 		}
 
 		if (last_chunk_id == GRAPH_CHUNKID_OIDLOOKUP)
@@ -201,11 +235,6 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 	}
 
 	return graph;
-
-cleanup_fail:
-	munmap(graph_map, graph_size);
-	close(fd);
-	exit(1);
 }
 
 static void prepare_commit_graph_one(struct repository *r, const char *obj_dir)
diff --git a/fuzz-commit-graph.c b/fuzz-commit-graph.c
new file mode 100644
index 0000000000..420851d0d2
--- /dev/null
+++ b/fuzz-commit-graph.c
@@ -0,0 +1,18 @@
+#include "object-store.h"
+#include "commit-graph.h"
+
+struct commit_graph *parse_commit_graph(void *graph_map, int fd,
+					size_t graph_size);
+
+int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size);
+
+int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)
+{
+	struct commit_graph *g;
+
+	g = parse_commit_graph((void *) data, -1, size);
+	if (g)
+		free(g);
+
+	return 0;
+}
-- 
2.20.0.rc2.403.gdbc3b29805-goog

[PATCH 2/2] commit-graph: fix buffer read-overflow

[Josh Steadmon]

fuzz-commit-graph identified a case where Git will read past the end of
a buffer containing a commit graph if the graph's header has an
incorrect chunk count. A simple bounds check in parse_commit_graph()
prevents this.

Signed-off-by: Josh Steadmon <steadmon@google.com>
Helped-by: Derrick Stolee <stolee@gmail.com>
---
 commit-graph.c | 13 +++++++++++--
 1 file changed, 11 insertions(+), 2 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index 0755359b1a..fee171a5f3 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -175,10 +175,19 @@ struct commit_graph *parse_commit_graph(void *graph_map, int fd,
 	last_chunk_offset = 8;
 	chunk_lookup = data + 8;
 	for (i = 0; i < graph->num_chunks; i++) {
-		uint32_t chunk_id = get_be32(chunk_lookup + 0);
-		uint64_t chunk_offset = get_be64(chunk_lookup + 4);
+		uint32_t chunk_id;
+		uint64_t chunk_offset;
 		int chunk_repeated = 0;
 
+		if (chunk_lookup + GRAPH_CHUNKLOOKUP_WIDTH > data + graph_size) {
+			error(_("chunk lookup table entry missing; graph file may be incomplete"));
+			free(graph);
+			return NULL;
+		}
+
+		chunk_id = get_be32(chunk_lookup + 0);
+		chunk_offset = get_be64(chunk_lookup + 4);
+
 		chunk_lookup += GRAPH_CHUNKLOOKUP_WIDTH;
 
 		if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
-- 
2.20.0.rc2.403.gdbc3b29805-goog

Re: [PATCH 1/2] commit-graph, fuzz: Add fuzzer for commit-graph

[Ævar Arnfjörð Bjarmason]

On Wed, Dec 05 2018, Josh Steadmon wrote:

> Breaks load_commit_graph_one() into a new function,
> parse_commit_graph(). The latter function operates on arbitrary buffers,
> which makes it suitable as a fuzzing target.
>
> Adds fuzz-commit-graph.c, which provides a fuzzing entry point
> compatible with libFuzzer (and possibly other fuzzing engines).
>
> Signed-off-by: Josh Steadmon <steadmon@google.com>
> ---
>  .gitignore          |  1 +
>  Makefile            |  1 +
>  commit-graph.c      | 63 +++++++++++++++++++++++++++++++++------------
>  fuzz-commit-graph.c | 18 +++++++++++++
>  4 files changed, 66 insertions(+), 17 deletions(-)
>  create mode 100644 fuzz-commit-graph.c
>
> diff --git a/.gitignore b/.gitignore
> index 0d77ea5894..8bcf153ed9 100644
> --- a/.gitignore
> +++ b/.gitignore
> @@ -1,3 +1,4 @@
> +/fuzz-commit-graph
>  /fuzz_corpora
>  /fuzz-pack-headers
>  /fuzz-pack-idx
> diff --git a/Makefile b/Makefile
> index 1a44c811aa..6b72f37c29 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -684,6 +684,7 @@ SCRIPTS = $(SCRIPT_SH_INS) \
>
>  ETAGS_TARGET = TAGS
>
> +FUZZ_OBJS += fuzz-commit-graph.o
>  FUZZ_OBJS += fuzz-pack-headers.o
>  FUZZ_OBJS += fuzz-pack-idx.o
>
> diff --git a/commit-graph.c b/commit-graph.c
> index 40c855f185..0755359b1a 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -46,6 +46,10 @@
>  #define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * GRAPH_CHUNKLOOKUP_WIDTH \
>  			+ GRAPH_FANOUT_SIZE + GRAPH_OID_LEN)
>
> +struct commit_graph *parse_commit_graph(void *graph_map, int fd,
> +					size_t graph_size);
> +
> +
>  char *get_commit_graph_filename(const char *obj_dir)
>  {
>  	return xstrfmt("%s/info/commit-graph", obj_dir);
> @@ -84,16 +88,10 @@ static int commit_graph_compatible(struct repository *r)
>  struct commit_graph *load_commit_graph_one(const char *graph_file)
>  {
>  	void *graph_map;
> -	const unsigned char *data, *chunk_lookup;
>  	size_t graph_size;
>  	struct stat st;
> -	uint32_t i;
> -	struct commit_graph *graph;
> +	struct commit_graph *ret;
>  	int fd = git_open(graph_file);
> -	uint64_t last_chunk_offset;
> -	uint32_t last_chunk_id;
> -	uint32_t graph_signature;
> -	unsigned char graph_version, hash_version;
>
>  	if (fd < 0)
>  		return NULL;
> @@ -108,27 +106,61 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
>  		die(_("graph file %s is too small"), graph_file);
>  	}
>  	graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);
> +	ret = parse_commit_graph(graph_map, fd, graph_size);
> +
> +	if (ret == NULL) {

Code in git usually uses just !ret.

> +		munmap(graph_map, graph_size);
> +		close(fd);
> +		exit(1);

Ouch, exit(1) from load_commit_graph_one()? Can't we return NULL here
instead? Nasty to exit from a library routine, but then I see later...

> @@ -201,11 +235,6 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
>  	}
>
>  	return graph;
> -
> -cleanup_fail:
> -	munmap(graph_map, graph_size);
> -	close(fd);
> -	exit(1);
>  }

... ah, I see this is where you got the exit(1) from. So it was there
already.

>  static void prepare_commit_graph_one(struct repository *r, const char *obj_dir)
> diff --git a/fuzz-commit-graph.c b/fuzz-commit-graph.c
> new file mode 100644
> index 0000000000..420851d0d2
> --- /dev/null
> +++ b/fuzz-commit-graph.c
> @@ -0,0 +1,18 @@
> +#include "object-store.h"
> +#include "commit-graph.h"
> +
> +struct commit_graph *parse_commit_graph(void *graph_map, int fd,
> +					size_t graph_size);
> +
> +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size);
> +
> +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)
> +{
> +	struct commit_graph *g;
> +
> +	g = parse_commit_graph((void *) data, -1, size);
> +	if (g)
> +		free(g);
> +
> +	return 0;
> +}

I hadn't looked at this before, but see your 5e47215080 ("fuzz: add
basic fuzz testing target.", 2018-10-12) for some prior art.

There's instructions there for a very long "make" invocation. Would be
nice if this were friendlier and we could just do "make test-fuzz" or
something...

Re: [PATCH 1/2] commit-graph, fuzz: Add fuzzer for commit-graph

[Josh Steadmon]

On 2018.12.05 23:48, Ævar Arnfjörð Bjarmason wrote:
> 
> On Wed, Dec 05 2018, Josh Steadmon wrote:
> 
> > Breaks load_commit_graph_one() into a new function,
> > parse_commit_graph(). The latter function operates on arbitrary buffers,
> > which makes it suitable as a fuzzing target.
> >
> > Adds fuzz-commit-graph.c, which provides a fuzzing entry point
> > compatible with libFuzzer (and possibly other fuzzing engines).
> >
> > Signed-off-by: Josh Steadmon <steadmon@google.com>
> > ---
> >  .gitignore          |  1 +
> >  Makefile            |  1 +
> >  commit-graph.c      | 63 +++++++++++++++++++++++++++++++++------------
> >  fuzz-commit-graph.c | 18 +++++++++++++
> >  4 files changed, 66 insertions(+), 17 deletions(-)
> >  create mode 100644 fuzz-commit-graph.c
> >
> > diff --git a/.gitignore b/.gitignore
> > index 0d77ea5894..8bcf153ed9 100644
> > --- a/.gitignore
> > +++ b/.gitignore
> > @@ -1,3 +1,4 @@
> > +/fuzz-commit-graph
> >  /fuzz_corpora
> >  /fuzz-pack-headers
> >  /fuzz-pack-idx
> > diff --git a/Makefile b/Makefile
> > index 1a44c811aa..6b72f37c29 100644
> > --- a/Makefile
> > +++ b/Makefile
> > @@ -684,6 +684,7 @@ SCRIPTS = $(SCRIPT_SH_INS) \
> >
> >  ETAGS_TARGET = TAGS
> >
> > +FUZZ_OBJS += fuzz-commit-graph.o
> >  FUZZ_OBJS += fuzz-pack-headers.o
> >  FUZZ_OBJS += fuzz-pack-idx.o
> >
> > diff --git a/commit-graph.c b/commit-graph.c
> > index 40c855f185..0755359b1a 100644
> > --- a/commit-graph.c
> > +++ b/commit-graph.c
> > @@ -46,6 +46,10 @@
> >  #define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * GRAPH_CHUNKLOOKUP_WIDTH \
> >  			+ GRAPH_FANOUT_SIZE + GRAPH_OID_LEN)
> >
> > +struct commit_graph *parse_commit_graph(void *graph_map, int fd,
> > +					size_t graph_size);
> > +
> > +
> >  char *get_commit_graph_filename(const char *obj_dir)
> >  {
> >  	return xstrfmt("%s/info/commit-graph", obj_dir);
> > @@ -84,16 +88,10 @@ static int commit_graph_compatible(struct repository *r)
> >  struct commit_graph *load_commit_graph_one(const char *graph_file)
> >  {
> >  	void *graph_map;
> > -	const unsigned char *data, *chunk_lookup;
> >  	size_t graph_size;
> >  	struct stat st;
> > -	uint32_t i;
> > -	struct commit_graph *graph;
> > +	struct commit_graph *ret;
> >  	int fd = git_open(graph_file);
> > -	uint64_t last_chunk_offset;
> > -	uint32_t last_chunk_id;
> > -	uint32_t graph_signature;
> > -	unsigned char graph_version, hash_version;
> >
> >  	if (fd < 0)
> >  		return NULL;
> > @@ -108,27 +106,61 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
> >  		die(_("graph file %s is too small"), graph_file);
> >  	}
> >  	graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);
> > +	ret = parse_commit_graph(graph_map, fd, graph_size);
> > +
> > +	if (ret == NULL) {
> 
> Code in git usually uses just !ret.

Will fix in V2, thanks.


> > +		munmap(graph_map, graph_size);
> > +		close(fd);
> > +		exit(1);
> 
> Ouch, exit(1) from load_commit_graph_one()? Can't we return NULL here
> instead? Nasty to exit from a library routine, but then I see later...
> 
> > @@ -201,11 +235,6 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
> >  	}
> >
> >  	return graph;
> > -
> > -cleanup_fail:
> > -	munmap(graph_map, graph_size);
> > -	close(fd);
> > -	exit(1);
> >  }
> 
> ... ah, I see this is where you got the exit(1) from. So it was there
> already.
> 
> >  static void prepare_commit_graph_one(struct repository *r, const char *obj_dir)
> > diff --git a/fuzz-commit-graph.c b/fuzz-commit-graph.c
> > new file mode 100644
> > index 0000000000..420851d0d2
> > --- /dev/null
> > +++ b/fuzz-commit-graph.c
> > @@ -0,0 +1,18 @@
> > +#include "object-store.h"
> > +#include "commit-graph.h"
> > +
> > +struct commit_graph *parse_commit_graph(void *graph_map, int fd,
> > +					size_t graph_size);
> > +
> > +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size);
> > +
> > +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)
> > +{
> > +	struct commit_graph *g;
> > +
> > +	g = parse_commit_graph((void *) data, -1, size);
> > +	if (g)
> > +		free(g);
> > +
> > +	return 0;
> > +}
> 
> I hadn't looked at this before, but see your 5e47215080 ("fuzz: add
> basic fuzz testing target.", 2018-10-12) for some prior art.
> 
> There's instructions there for a very long "make" invocation. Would be
> nice if this were friendlier and we could just do "make test-fuzz" or
> something...

Yeah, the problem is that there are too many combinations of fuzzing
engine, sanitizer, and compiler to make any reasonable default here.
Even if you just stick with libFuzzer, address sanitizer, and clang, the
flags change radically depending on which version of clang you're using.

Re: [PATCH 1/2] commit-graph, fuzz: Add fuzzer for commit-graph

[Junio C Hamano]

Josh Steadmon <steadmon@google.com> writes:

> @@ -108,27 +106,61 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
>  		die(_("graph file %s is too small"), graph_file);
>  	}
>  	graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);
> +	ret = parse_commit_graph(graph_map, fd, graph_size);

OK, assuming that the new helper returns NULL from all places in the
original that would have jumped to the cleanup-fail label, this would
do the same thing (it may not be the right thing to exit, but that
is OK for the purpose of this change).

> +	if (ret == NULL) {
> +		munmap(graph_map, graph_size);
> +		close(fd);
> +		exit(1);
> +	}
> +
> +	return ret;
> +}
> +
> +/*
> + * This function is intended to be used only from load_commit_graph_one() or in
> + * fuzz tests.
> + */

Hmph, is that necessary to say?  

"Right now, it has only these two callers" is sometimes handy for
those without good static analysis tools, like "git grep" ;-), but I
do not think of a reason why a new caller we'll add in the future,
who happens to have the data of the graph file in-core, should not
be allowed to call this function.


> +struct commit_graph *parse_commit_graph(void *graph_map, int fd,
> +					size_t graph_size)
> +{
> +	const unsigned char *data, *chunk_lookup;
> +	uint32_t i;
> +	struct commit_graph *graph;
> +	uint64_t last_chunk_offset;
> +	uint32_t last_chunk_id;
> +	uint32_t graph_signature;
> +	unsigned char graph_version, hash_version;
> +
> +	/*
> +	 * This should already be checked in load_commit_graph_one, but we still
> +	 * need a check here for when we're calling parse_commit_graph directly
> +	 * from fuzz tests. We can omit the error message in that case.
> +	 */

In the same spirit, I am dubious of the longer-term value of this
comment.  As an explanation of why this conversion is correct in the
proposed log message for this change, it perfectly makes sense,
though.

> +	if (graph_size < GRAPH_MIN_SIZE)
> +		return NULL;
> +

The load_commit_graph_one() grabbed graph_map out of xmmap() so it
is guaranteed to be non-NULL, but we need to check graph_map != NULL
when we're calling this directly from the fuzz tests, exactly in the
same spirit that we check graph_size above.  Besides, these are to
make sure future callers won't misuse the API.

>  	data = (const unsigned char *)graph_map;

And the reset of the function is the same as the original modulo
jumping to the cleanup_fail label has been replaced with returning
NULL.

Looks good.

> ...
> -
> -cleanup_fail:
> -	munmap(graph_map, graph_size);
> -	close(fd);
> -	exit(1);
>  }
>  
>  static void prepare_commit_graph_one(struct repository *r, const char *obj_dir)
> diff --git a/fuzz-commit-graph.c b/fuzz-commit-graph.c
> new file mode 100644
> index 0000000000..420851d0d2
> --- /dev/null
> +++ b/fuzz-commit-graph.c
> @@ -0,0 +1,18 @@
> +#include "object-store.h"
> +#include "commit-graph.h"
> +
> +struct commit_graph *parse_commit_graph(void *graph_map, int fd,
> +					size_t graph_size);
> +
> +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size);
> +
> +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)
> +{
> +	struct commit_graph *g;
> +
> +	g = parse_commit_graph((void *) data, -1, size);
> +	if (g)
> +		free(g);
> +
> +	return 0;
> +}

Re: [PATCH 1/2] commit-graph, fuzz: Add fuzzer for commit-graph

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

>> +	if (graph_size < GRAPH_MIN_SIZE)
>> +		return NULL;
>> +
>
> The load_commit_graph_one() grabbed graph_map out of xmmap() so it
> is guaranteed to be non-NULL, but we need to check graph_map != NULL
> when we're calling this directly from the fuzz tests, exactly in the
> same spirit that we check graph_size above.  Besides, these are to
> make sure future callers won't misuse the API.

Insert "Please check graph_map != NULL here, too." before the above
paragraph.

>>  	data = (const unsigned char *)graph_map;
>
> And the reset of the function is the same as the original modulo
> jumping to the cleanup_fail label has been replaced with returning
> NULL.
>
> Looks good.

Of course, s/reset/rest/ is what I meant.

Re: [PATCH 1/2] commit-graph, fuzz: Add fuzzer for commit-graph

[Junio C Hamano]

Josh Steadmon <steadmon@google.com> writes:

> diff --git a/fuzz-commit-graph.c b/fuzz-commit-graph.c
> new file mode 100644
> index 0000000000..420851d0d2
> --- /dev/null
> +++ b/fuzz-commit-graph.c
> @@ -0,0 +1,18 @@
> +#include "object-store.h"
> +#include "commit-graph.h"
> +
> +struct commit_graph *parse_commit_graph(void *graph_map, int fd,
> +					size_t graph_size);
> +
> +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size);
> +
> +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)
> +{
> +	struct commit_graph *g;
> +
> +	g = parse_commit_graph((void *) data, -1, size);
> +	if (g)
> +		free(g);

As it is perfectly OK to free(NULL), please lose "if (g)" and a
level of indentation; otherwise, "make coccicheck" would complain.

Thanks.

> +	return 0;
> +}

Re: [PATCH 2/2] commit-graph: fix buffer read-overflow

[Derrick Stolee]

On 12/5/2018 5:32 PM, Josh Steadmon wrote:
>   
> +		if (chunk_lookup + GRAPH_CHUNKLOOKUP_WIDTH > data + graph_size) {
> +			error(_("chunk lookup table entry missing; graph file may be incomplete"));
> +			free(graph);
> +			return NULL;
> +		}

Something I forgot earlier: there are several tests in 
t5318-commit-graph.sh that use 'git commit-graph verify' to ensure we 
hit these error conditions on a corrupted commit-graph file. Could you 
try adding a test there that looks for this error message?

Thanks,
-Stolee

[PATCH v2 0/3] Add commit-graph fuzzer and fix buffer overflow

[Josh Steadmon]

Add a new fuzz test for the commit graph and fix a buffer read-overflow
that it discovered. Additionally, fix the Makefile instructions for
building fuzzers.

Changes since V1:
  * Moved the parse_commit_graph() declaration to the header file, since
    we don't mind if others use it.
  * Moved some unnecessary comments into commit messages.
  * Fixed some style issues.
  * Added a test case for detecting commit graphs with missing chunk
    lookup entries.
  * Ævar's comments on the Makefile made me realize the fuzzer build
    instructions were using the wrong variable. Added a new commit to
    fix this.

Josh Steadmon (3):
  commit-graph, fuzz: Add fuzzer for commit-graph
  commit-graph: fix buffer read-overflow
  Makefile: correct example fuzz build

 .gitignore              |  1 +
 Makefile                |  3 +-
 commit-graph.c          | 67 +++++++++++++++++++++++++++++------------
 commit-graph.h          |  3 ++
 fuzz-commit-graph.c     | 16 ++++++++++
 t/t5318-commit-graph.sh | 28 +++++++++++++++++
 6 files changed, 98 insertions(+), 20 deletions(-)
 create mode 100644 fuzz-commit-graph.c

Range-diff against v1:
1:  53e62baaa8 ! 1:  0b57ecbe1b commit-graph, fuzz: Add fuzzer for commit-graph
    @@ -4,7 +4,9 @@
     
         Breaks load_commit_graph_one() into a new function,
         parse_commit_graph(). The latter function operates on arbitrary buffers,
    -    which makes it suitable as a fuzzing target.
    +    which makes it suitable as a fuzzing target. Since parse_commit_graph()
    +    is only called by load_commit_graph_one() (and the fuzzer described
    +    below), we omit error messages that would be duplicated by the caller.
     
         Adds fuzz-commit-graph.c, which provides a fuzzing entry point
         compatible with libFuzzer (and possibly other fuzzing engines).
    @@ -35,17 +37,6 @@
      diff --git a/commit-graph.c b/commit-graph.c
      --- a/commit-graph.c
      +++ b/commit-graph.c
    -@@
    - #define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * GRAPH_CHUNKLOOKUP_WIDTH \
    - 			+ GRAPH_FANOUT_SIZE + GRAPH_OID_LEN)
    - 
    -+struct commit_graph *parse_commit_graph(void *graph_map, int fd,
    -+					size_t graph_size);
    -+
    -+
    - char *get_commit_graph_filename(const char *obj_dir)
    - {
    - 	return xstrfmt("%s/info/commit-graph", obj_dir);
     @@
      struct commit_graph *load_commit_graph_one(const char *graph_file)
      {
    @@ -70,7 +61,7 @@
      	graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);
     +	ret = parse_commit_graph(graph_map, fd, graph_size);
     +
    -+	if (ret == NULL) {
    ++	if (!ret) {
     +		munmap(graph_map, graph_size);
     +		close(fd);
     +		exit(1);
    @@ -79,10 +70,6 @@
     +	return ret;
     +}
     +
    -+/*
    -+ * This function is intended to be used only from load_commit_graph_one() or in
    -+ * fuzz tests.
    -+ */
     +struct commit_graph *parse_commit_graph(void *graph_map, int fd,
     +					size_t graph_size)
     +{
    @@ -94,11 +81,9 @@
     +	uint32_t graph_signature;
     +	unsigned char graph_version, hash_version;
     +
    -+	/*
    -+	 * This should already be checked in load_commit_graph_one, but we still
    -+	 * need a check here for when we're calling parse_commit_graph directly
    -+	 * from fuzz tests. We can omit the error message in that case.
    -+	 */
    ++	if (!graph_map)
    ++		return NULL;
    ++
     +	if (graph_size < GRAPH_MIN_SIZE)
     +		return NULL;
     +
    @@ -162,12 +147,25 @@
      
      static void prepare_commit_graph_one(struct repository *r, const char *obj_dir)
     
    + diff --git a/commit-graph.h b/commit-graph.h
    + --- a/commit-graph.h
    + +++ b/commit-graph.h
    +@@
    + 
    + struct commit_graph *load_commit_graph_one(const char *graph_file);
    + 
    ++struct commit_graph *parse_commit_graph(void *graph_map, int fd,
    ++					size_t graph_size);
    ++
    + /*
    +  * Return 1 if and only if the repository has a commit-graph
    +  * file and generation numbers are computed in that file.
    +
      diff --git a/fuzz-commit-graph.c b/fuzz-commit-graph.c
      new file mode 100644
      --- /dev/null
      +++ b/fuzz-commit-graph.c
     @@
    -+#include "object-store.h"
     +#include "commit-graph.h"
     +
     +struct commit_graph *parse_commit_graph(void *graph_map, int fd,
    @@ -179,9 +177,8 @@
     +{
     +	struct commit_graph *g;
     +
    -+	g = parse_commit_graph((void *) data, -1, size);
    -+	if (g)
    -+		free(g);
    ++	g = parse_commit_graph((void *)data, -1, size);
    ++	free(g);
     +
     +	return 0;
     +}
2:  ad2e761f44 ! 2:  af45c2337f commit-graph: fix buffer read-overflow
    @@ -22,7 +22,8 @@
     +		uint64_t chunk_offset;
      		int chunk_repeated = 0;
      
    -+		if (chunk_lookup + GRAPH_CHUNKLOOKUP_WIDTH > data + graph_size) {
    ++		if (chunk_lookup + GRAPH_CHUNKLOOKUP_WIDTH >
    ++		    data + graph_size) {
     +			error(_("chunk lookup table entry missing; graph file may be incomplete"));
     +			free(graph);
     +			return NULL;
    @@ -34,3 +35,49 @@
      		chunk_lookup += GRAPH_CHUNKLOOKUP_WIDTH;
      
      		if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
    +
    + diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
    + --- a/t/t5318-commit-graph.sh
    + +++ b/t/t5318-commit-graph.sh
    +@@
    + 	test_i18ngrep "$grepstr" err
    + }
    + 
    ++
    ++# usage: corrupt_and_zero_graph_then_verify <corrupt_position> <data> <zero_position> <string>
    ++# Manipulates the commit-graph file at <corrupt_position> by inserting the data,
    ++# then zeros the file starting at <zero_position>. Finally, runs
    ++# 'git commit-graph verify' and places the output in the file 'err'. Tests 'err'
    ++# for the given string.
    ++corrupt_and_zero_graph_then_verify() {
    ++	corrupt_pos=$1
    ++	data="${2:-\0}"
    ++	zero_pos=$3
    ++	grepstr=$4
    ++	orig_size=$(stat --format=%s $objdir/info/commit-graph)
    ++	cd "$TRASH_DIRECTORY/full" &&
    ++	test_when_finished mv commit-graph-backup $objdir/info/commit-graph &&
    ++	cp $objdir/info/commit-graph commit-graph-backup &&
    ++	printf "$data" | dd of="$objdir/info/commit-graph" bs=1 seek="$corrupt_pos" conv=notrunc &&
    ++	truncate --size=$zero_pos $objdir/info/commit-graph &&
    ++	truncate --size=$orig_size $objdir/info/commit-graph &&
    ++	test_must_fail git commit-graph verify 2>test_err &&
    ++	grep -v "^+" test_err >err &&
    ++	test_i18ngrep "$grepstr" err
    ++}
    ++
    + test_expect_success 'detect bad signature' '
    + 	corrupt_graph_and_verify 0 "\0" \
    + 		"graph signature"
    +@@
    + 		"incorrect checksum"
    + '
    + 
    ++test_expect_success 'detect truncated graph' '
    ++	corrupt_and_zero_graph_then_verify $GRAPH_BYTE_CHUNK_COUNT "\xff" \
    ++		$GRAPH_CHUNK_LOOKUP_OFFSET "chunk lookup table entry missing"
    ++'
    ++
    + test_expect_success 'git fsck (checks commit-graph)' '
    + 	cd "$TRASH_DIRECTORY/full" &&
    + 	git fsck &&
-:  ---------- > 3:  7519fc76df Makefile: correct example fuzz build
-- 
2.20.0.rc2.10.g7519fc76df

[PATCH v2 1/3] commit-graph, fuzz: Add fuzzer for commit-graph

[Josh Steadmon]

Breaks load_commit_graph_one() into a new function,
parse_commit_graph(). The latter function operates on arbitrary buffers,
which makes it suitable as a fuzzing target. Since parse_commit_graph()
is only called by load_commit_graph_one() (and the fuzzer described
below), we omit error messages that would be duplicated by the caller.

Adds fuzz-commit-graph.c, which provides a fuzzing entry point
compatible with libFuzzer (and possibly other fuzzing engines).

Signed-off-by: Josh Steadmon <steadmon@google.com>
---
 .gitignore          |  1 +
 Makefile            |  1 +
 commit-graph.c      | 53 ++++++++++++++++++++++++++++++---------------
 commit-graph.h      |  3 +++
 fuzz-commit-graph.c | 16 ++++++++++++++
 5 files changed, 57 insertions(+), 17 deletions(-)
 create mode 100644 fuzz-commit-graph.c

diff --git a/.gitignore b/.gitignore
index 0d77ea5894..8bcf153ed9 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,4 @@
+/fuzz-commit-graph
 /fuzz_corpora
 /fuzz-pack-headers
 /fuzz-pack-idx
diff --git a/Makefile b/Makefile
index 1a44c811aa..6b72f37c29 100644
--- a/Makefile
+++ b/Makefile
@@ -684,6 +684,7 @@ SCRIPTS = $(SCRIPT_SH_INS) \
 
 ETAGS_TARGET = TAGS
 
+FUZZ_OBJS += fuzz-commit-graph.o
 FUZZ_OBJS += fuzz-pack-headers.o
 FUZZ_OBJS += fuzz-pack-idx.o
 
diff --git a/commit-graph.c b/commit-graph.c
index 40c855f185..07dd410f3c 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -84,16 +84,10 @@ static int commit_graph_compatible(struct repository *r)
 struct commit_graph *load_commit_graph_one(const char *graph_file)
 {
 	void *graph_map;
-	const unsigned char *data, *chunk_lookup;
 	size_t graph_size;
 	struct stat st;
-	uint32_t i;
-	struct commit_graph *graph;
+	struct commit_graph *ret;
 	int fd = git_open(graph_file);
-	uint64_t last_chunk_offset;
-	uint32_t last_chunk_id;
-	uint32_t graph_signature;
-	unsigned char graph_version, hash_version;
 
 	if (fd < 0)
 		return NULL;
@@ -108,27 +102,55 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 		die(_("graph file %s is too small"), graph_file);
 	}
 	graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);
+	ret = parse_commit_graph(graph_map, fd, graph_size);
+
+	if (!ret) {
+		munmap(graph_map, graph_size);
+		close(fd);
+		exit(1);
+	}
+
+	return ret;
+}
+
+struct commit_graph *parse_commit_graph(void *graph_map, int fd,
+					size_t graph_size)
+{
+	const unsigned char *data, *chunk_lookup;
+	uint32_t i;
+	struct commit_graph *graph;
+	uint64_t last_chunk_offset;
+	uint32_t last_chunk_id;
+	uint32_t graph_signature;
+	unsigned char graph_version, hash_version;
+
+	if (!graph_map)
+		return NULL;
+
+	if (graph_size < GRAPH_MIN_SIZE)
+		return NULL;
+
 	data = (const unsigned char *)graph_map;
 
 	graph_signature = get_be32(data);
 	if (graph_signature != GRAPH_SIGNATURE) {
 		error(_("graph signature %X does not match signature %X"),
 		      graph_signature, GRAPH_SIGNATURE);
-		goto cleanup_fail;
+		return NULL;
 	}
 
 	graph_version = *(unsigned char*)(data + 4);
 	if (graph_version != GRAPH_VERSION) {
 		error(_("graph version %X does not match version %X"),
 		      graph_version, GRAPH_VERSION);
-		goto cleanup_fail;
+		return NULL;
 	}
 
 	hash_version = *(unsigned char*)(data + 5);
 	if (hash_version != GRAPH_OID_VERSION) {
 		error(_("hash version %X does not match version %X"),
 		      hash_version, GRAPH_OID_VERSION);
-		goto cleanup_fail;
+		return NULL;
 	}
 
 	graph = alloc_commit_graph();
@@ -152,7 +174,8 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 		if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
 			error(_("improper chunk offset %08x%08x"), (uint32_t)(chunk_offset >> 32),
 			      (uint32_t)chunk_offset);
-			goto cleanup_fail;
+			free(graph);
+			return NULL;
 		}
 
 		switch (chunk_id) {
@@ -187,7 +210,8 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 
 		if (chunk_repeated) {
 			error(_("chunk id %08x appears multiple times"), chunk_id);
-			goto cleanup_fail;
+			free(graph);
+			return NULL;
 		}
 
 		if (last_chunk_id == GRAPH_CHUNKID_OIDLOOKUP)
@@ -201,11 +225,6 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 	}
 
 	return graph;
-
-cleanup_fail:
-	munmap(graph_map, graph_size);
-	close(fd);
-	exit(1);
 }
 
 static void prepare_commit_graph_one(struct repository *r, const char *obj_dir)
diff --git a/commit-graph.h b/commit-graph.h
index 9db40b4d3a..813e7c19f1 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -54,6 +54,9 @@ struct commit_graph {
 
 struct commit_graph *load_commit_graph_one(const char *graph_file);
 
+struct commit_graph *parse_commit_graph(void *graph_map, int fd,
+					size_t graph_size);
+
 /*
  * Return 1 if and only if the repository has a commit-graph
  * file and generation numbers are computed in that file.
diff --git a/fuzz-commit-graph.c b/fuzz-commit-graph.c
new file mode 100644
index 0000000000..cf790c9d04
--- /dev/null
+++ b/fuzz-commit-graph.c
@@ -0,0 +1,16 @@
+#include "commit-graph.h"
+
+struct commit_graph *parse_commit_graph(void *graph_map, int fd,
+					size_t graph_size);
+
+int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size);
+
+int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)
+{
+	struct commit_graph *g;
+
+	g = parse_commit_graph((void *)data, -1, size);
+	free(g);
+
+	return 0;
+}
-- 
2.20.0.rc2.10.g7519fc76df

[PATCH v2 2/3] commit-graph: fix buffer read-overflow

[Josh Steadmon]

fuzz-commit-graph identified a case where Git will read past the end of
a buffer containing a commit graph if the graph's header has an
incorrect chunk count. A simple bounds check in parse_commit_graph()
prevents this.

Signed-off-by: Josh Steadmon <steadmon@google.com>
---
 commit-graph.c          | 14 ++++++++++++--
 t/t5318-commit-graph.sh | 28 ++++++++++++++++++++++++++++
 2 files changed, 40 insertions(+), 2 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index 07dd410f3c..224a5f161e 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -165,10 +165,20 @@ struct commit_graph *parse_commit_graph(void *graph_map, int fd,
 	last_chunk_offset = 8;
 	chunk_lookup = data + 8;
 	for (i = 0; i < graph->num_chunks; i++) {
-		uint32_t chunk_id = get_be32(chunk_lookup + 0);
-		uint64_t chunk_offset = get_be64(chunk_lookup + 4);
+		uint32_t chunk_id;
+		uint64_t chunk_offset;
 		int chunk_repeated = 0;
 
+		if (chunk_lookup + GRAPH_CHUNKLOOKUP_WIDTH >
+		    data + graph_size) {
+			error(_("chunk lookup table entry missing; graph file may be incomplete"));
+			free(graph);
+			return NULL;
+		}
+
+		chunk_id = get_be32(chunk_lookup + 0);
+		chunk_offset = get_be64(chunk_lookup + 4);
+
 		chunk_lookup += GRAPH_CHUNKLOOKUP_WIDTH;
 
 		if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index 5fe21db99f..2503cb0345 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -384,6 +384,29 @@ corrupt_graph_and_verify() {
 	test_i18ngrep "$grepstr" err
 }
 
+
+# usage: corrupt_and_zero_graph_then_verify <corrupt_position> <data> <zero_position> <string>
+# Manipulates the commit-graph file at <corrupt_position> by inserting the data,
+# then zeros the file starting at <zero_position>. Finally, runs
+# 'git commit-graph verify' and places the output in the file 'err'. Tests 'err'
+# for the given string.
+corrupt_and_zero_graph_then_verify() {
+	corrupt_pos=$1
+	data="${2:-\0}"
+	zero_pos=$3
+	grepstr=$4
+	orig_size=$(stat --format=%s $objdir/info/commit-graph)
+	cd "$TRASH_DIRECTORY/full" &&
+	test_when_finished mv commit-graph-backup $objdir/info/commit-graph &&
+	cp $objdir/info/commit-graph commit-graph-backup &&
+	printf "$data" | dd of="$objdir/info/commit-graph" bs=1 seek="$corrupt_pos" conv=notrunc &&
+	truncate --size=$zero_pos $objdir/info/commit-graph &&
+	truncate --size=$orig_size $objdir/info/commit-graph &&
+	test_must_fail git commit-graph verify 2>test_err &&
+	grep -v "^+" test_err >err &&
+	test_i18ngrep "$grepstr" err
+}
+
 test_expect_success 'detect bad signature' '
 	corrupt_graph_and_verify 0 "\0" \
 		"graph signature"
@@ -484,6 +507,11 @@ test_expect_success 'detect invalid checksum hash' '
 		"incorrect checksum"
 '
 
+test_expect_success 'detect truncated graph' '
+	corrupt_and_zero_graph_then_verify $GRAPH_BYTE_CHUNK_COUNT "\xff" \
+		$GRAPH_CHUNK_LOOKUP_OFFSET "chunk lookup table entry missing"
+'
+
 test_expect_success 'git fsck (checks commit-graph)' '
 	cd "$TRASH_DIRECTORY/full" &&
 	git fsck &&
-- 
2.20.0.rc2.10.g7519fc76df

[PATCH v2 3/3] Makefile: correct example fuzz build

[Josh Steadmon]

Signed-off-by: Josh Steadmon <steadmon@google.com>
---
 Makefile | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/Makefile b/Makefile
index 6b72f37c29..bbcfc2bc9f 100644
--- a/Makefile
+++ b/Makefile
@@ -3104,7 +3104,7 @@ cover_db_html: cover_db
 # An example command to build against libFuzzer from LLVM 4.0.0:
 #
 # make CC=clang CXX=clang++ \
-#      FUZZ_CXXFLAGS="-fsanitize-coverage=trace-pc-guard -fsanitize=address" \
+#      CFLAGS="-fsanitize-coverage=trace-pc-guard -fsanitize=address" \
 #      LIB_FUZZING_ENGINE=/usr/lib/llvm-4.0/lib/libFuzzer.a \
 #      fuzz-all
 #
-- 
2.20.0.rc2.10.g7519fc76df

Re: [PATCH v2 2/3] commit-graph: fix buffer read-overflow

[Jeff King]

On Thu, Dec 06, 2018 at 12:20:54PM -0800, Josh Steadmon wrote:

> diff --git a/commit-graph.c b/commit-graph.c
> index 07dd410f3c..224a5f161e 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -165,10 +165,20 @@ struct commit_graph *parse_commit_graph(void *graph_map, int fd,
>  	last_chunk_offset = 8;
>  	chunk_lookup = data + 8;
>  	for (i = 0; i < graph->num_chunks; i++) {
> -		uint32_t chunk_id = get_be32(chunk_lookup + 0);
> -		uint64_t chunk_offset = get_be64(chunk_lookup + 4);
> +		uint32_t chunk_id;
> +		uint64_t chunk_offset;
>  		int chunk_repeated = 0;
>  
> +		if (chunk_lookup + GRAPH_CHUNKLOOKUP_WIDTH >
> +		    data + graph_size) {
> +			error(_("chunk lookup table entry missing; graph file may be incomplete"));
> +			free(graph);
> +			return NULL;
> +		}

Is it possible to overflow the addition here? E.g., if I'm on a 32-bit
system and the truncated chunk appears right at the 4GB limit, in which
case we wrap back around? I guess that's pretty implausible, since it
would mean that the mmap is bumping up against the end of the address
space. I didn't check, but I wouldn't be surprised if sane operating
systems avoid allocating those addresses.

But I think you could write this as:

  if (data + graph_size - chunk_lookup < GRAPH_CHUNKLOOKUP_WIDTH)

to avoid overflow (we know that "data + graph_size" is sane because
that's our mmap, and chunk_lookup is somewhere between "data" and "data
+ graph_size", so the result is between 0 and graph_size).

I dunno. I think I've convinced myself it's a non-issue here, but it may
be good to get in the habit of writing these sorts of offset checks in
an overflow-proof order.

-Peff

Re: [PATCH v2 2/3] commit-graph: fix buffer read-overflow

[Derrick Stolee]

On 12/6/2018 3:20 PM, Josh Steadmon wrote:
> +
> +# usage: corrupt_and_zero_graph_then_verify <corrupt_position> <data> <zero_position> <string>
> +# Manipulates the commit-graph file at <corrupt_position> by inserting the data,
> +# then zeros the file starting at <zero_position>. Finally, runs
> +# 'git commit-graph verify' and places the output in the file 'err'. Tests 'err'
> +# for the given string.
> +corrupt_and_zero_graph_then_verify() {

This method is very similar to to 'corrupt_graph_and_verify()', the only 
difference being the zero_pos, which zeroes the graph.

Could it instead be a modification of corrupt_graph_and_verify() where 
$4 is interpreted as zero_pos, and if it is blank we don't do the 
truncation?

> +test_expect_success 'detect truncated graph' '
> +	corrupt_and_zero_graph_then_verify $GRAPH_BYTE_CHUNK_COUNT "\xff" \
> +		$GRAPH_CHUNK_LOOKUP_OFFSET "chunk lookup table entry missing"
> +'
> +

Thanks for this! I think it's valuable to keep explicit tests around 
that were discovered from your fuzz tests. Specifically, I can repeat 
the test when I get around to the next file format.

Thanks,
-Stolee

[PATCH v3 0/3] Add commit-graph fuzzer and fix buffer overflow

[Josh Steadmon]

Ad a new fuzz test for the commit graph and fix a buffer read-overflow
that it discovered. Additionally, fix the Makefile instructions for
building fuzzers.

Changes since V2:
  * Avoid pointer arithmetic overflow when checking the graph's chunk
    count.
  * Merge the corrupt_graph_and_verify and
    corrupt_and_zero_graph_then_verify test functions.

Josh Steadmon (3):
  commit-graph, fuzz: Add fuzzer for commit-graph
  commit-graph: fix buffer read-overflow
  Makefile: correct example fuzz build

 .gitignore              |  1 +
 Makefile                |  3 +-
 commit-graph.c          | 67 +++++++++++++++++++++++++++++------------
 commit-graph.h          |  3 ++
 fuzz-commit-graph.c     | 16 ++++++++++
 t/t5318-commit-graph.sh | 15 +++++++--
 6 files changed, 83 insertions(+), 22 deletions(-)
 create mode 100644 fuzz-commit-graph.c

Range-diff against v2:
1:  af45c2337f ! 1:  675d58ecea commit-graph: fix buffer read-overflow
    @@ -22,8 +22,8 @@
     +		uint64_t chunk_offset;
      		int chunk_repeated = 0;
      
    -+		if (chunk_lookup + GRAPH_CHUNKLOOKUP_WIDTH >
    -+		    data + graph_size) {
    ++		if (data + graph_size - chunk_lookup <
    ++		    GRAPH_CHUNKLOOKUP_WIDTH) {
     +			error(_("chunk lookup table entry missing; graph file may be incomplete"));
     +			free(graph);
     +			return NULL;
    @@ -40,31 +40,34 @@
      --- a/t/t5318-commit-graph.sh
      +++ b/t/t5318-commit-graph.sh
     @@
    - 	test_i18ngrep "$grepstr" err
    - }
    + GRAPH_BYTE_OCTOPUS=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4))
    + GRAPH_BYTE_FOOTER=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4 * $NUM_OCTOPUS_EDGES))
      
    -+
    -+# usage: corrupt_and_zero_graph_then_verify <corrupt_position> <data> <zero_position> <string>
    -+# Manipulates the commit-graph file at <corrupt_position> by inserting the data,
    -+# then zeros the file starting at <zero_position>. Finally, runs
    -+# 'git commit-graph verify' and places the output in the file 'err'. Tests 'err'
    -+# for the given string.
    -+corrupt_and_zero_graph_then_verify() {
    -+	corrupt_pos=$1
    -+	data="${2:-\0}"
    -+	zero_pos=$3
    -+	grepstr=$4
    +-# usage: corrupt_graph_and_verify <position> <data> <string>
    ++# usage: corrupt_graph_and_verify <position> <data> <string> [<zero_pos>]
    + # Manipulates the commit-graph file at the position
    +-# by inserting the data, then runs 'git commit-graph verify'
    ++# by inserting the data, optionally zeroing the file
    ++# starting at <zero_pos>, then runs 'git commit-graph verify'
    + # and places the output in the file 'err'. Test 'err' for
    + # the given string.
    + corrupt_graph_and_verify() {
    + 	pos=$1
    + 	data="${2:-\0}"
    + 	grepstr=$3
     +	orig_size=$(stat --format=%s $objdir/info/commit-graph)
    -+	cd "$TRASH_DIRECTORY/full" &&
    -+	test_when_finished mv commit-graph-backup $objdir/info/commit-graph &&
    -+	cp $objdir/info/commit-graph commit-graph-backup &&
    -+	printf "$data" | dd of="$objdir/info/commit-graph" bs=1 seek="$corrupt_pos" conv=notrunc &&
    ++	zero_pos=${4:-${orig_size}}
    + 	cd "$TRASH_DIRECTORY/full" &&
    + 	test_when_finished mv commit-graph-backup $objdir/info/commit-graph &&
    + 	cp $objdir/info/commit-graph commit-graph-backup &&
    + 	printf "$data" | dd of="$objdir/info/commit-graph" bs=1 seek="$pos" conv=notrunc &&
     +	truncate --size=$zero_pos $objdir/info/commit-graph &&
     +	truncate --size=$orig_size $objdir/info/commit-graph &&
    -+	test_must_fail git commit-graph verify 2>test_err &&
    -+	grep -v "^+" test_err >err &&
    -+	test_i18ngrep "$grepstr" err
    -+}
    + 	test_must_fail git commit-graph verify 2>test_err &&
    + 	grep -v "^+" test_err >err
    + 	test_i18ngrep "$grepstr" err
    + }
    + 
     +
      test_expect_success 'detect bad signature' '
      	corrupt_graph_and_verify 0 "\0" \
    @@ -73,9 +76,9 @@
      		"incorrect checksum"
      '
      
    -+test_expect_success 'detect truncated graph' '
    -+	corrupt_and_zero_graph_then_verify $GRAPH_BYTE_CHUNK_COUNT "\xff" \
    -+		$GRAPH_CHUNK_LOOKUP_OFFSET "chunk lookup table entry missing"
    ++test_expect_success 'detect incorrect chunk count' '
    ++	corrupt_graph_and_verify $GRAPH_BYTE_CHUNK_COUNT "\xff" \
    ++		"chunk lookup table entry missing" $GRAPH_CHUNK_LOOKUP_OFFSET
     +'
     +
      test_expect_success 'git fsck (checks commit-graph)' '
2:  7519fc76df = 2:  06a32bfe8b Makefile: correct example fuzz build
-- 
2.20.0.rc2.12.g4c11c11dec

[PATCH v3 1/3] commit-graph, fuzz: Add fuzzer for commit-graph

[Josh Steadmon]

Breaks load_commit_graph_one() into a new function,
parse_commit_graph(). The latter function operates on arbitrary buffers,
which makes it suitable as a fuzzing target. Since parse_commit_graph()
is only called by load_commit_graph_one() (and the fuzzer described
below), we omit error messages that would be duplicated by the caller.

Adds fuzz-commit-graph.c, which provides a fuzzing entry point
compatible with libFuzzer (and possibly other fuzzing engines).

Signed-off-by: Josh Steadmon <steadmon@google.com>
---
 .gitignore          |  1 +
 Makefile            |  1 +
 commit-graph.c      | 53 ++++++++++++++++++++++++++++++---------------
 commit-graph.h      |  3 +++
 fuzz-commit-graph.c | 16 ++++++++++++++
 5 files changed, 57 insertions(+), 17 deletions(-)
 create mode 100644 fuzz-commit-graph.c

diff --git a/.gitignore b/.gitignore
index 0d77ea5894..8bcf153ed9 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,4 @@
+/fuzz-commit-graph
 /fuzz_corpora
 /fuzz-pack-headers
 /fuzz-pack-idx
diff --git a/Makefile b/Makefile
index 1a44c811aa..6b72f37c29 100644
--- a/Makefile
+++ b/Makefile
@@ -684,6 +684,7 @@ SCRIPTS = $(SCRIPT_SH_INS) \
 
 ETAGS_TARGET = TAGS
 
+FUZZ_OBJS += fuzz-commit-graph.o
 FUZZ_OBJS += fuzz-pack-headers.o
 FUZZ_OBJS += fuzz-pack-idx.o
 
diff --git a/commit-graph.c b/commit-graph.c
index 40c855f185..07dd410f3c 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -84,16 +84,10 @@ static int commit_graph_compatible(struct repository *r)
 struct commit_graph *load_commit_graph_one(const char *graph_file)
 {
 	void *graph_map;
-	const unsigned char *data, *chunk_lookup;
 	size_t graph_size;
 	struct stat st;
-	uint32_t i;
-	struct commit_graph *graph;
+	struct commit_graph *ret;
 	int fd = git_open(graph_file);
-	uint64_t last_chunk_offset;
-	uint32_t last_chunk_id;
-	uint32_t graph_signature;
-	unsigned char graph_version, hash_version;
 
 	if (fd < 0)
 		return NULL;
@@ -108,27 +102,55 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 		die(_("graph file %s is too small"), graph_file);
 	}
 	graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);
+	ret = parse_commit_graph(graph_map, fd, graph_size);
+
+	if (!ret) {
+		munmap(graph_map, graph_size);
+		close(fd);
+		exit(1);
+	}
+
+	return ret;
+}
+
+struct commit_graph *parse_commit_graph(void *graph_map, int fd,
+					size_t graph_size)
+{
+	const unsigned char *data, *chunk_lookup;
+	uint32_t i;
+	struct commit_graph *graph;
+	uint64_t last_chunk_offset;
+	uint32_t last_chunk_id;
+	uint32_t graph_signature;
+	unsigned char graph_version, hash_version;
+
+	if (!graph_map)
+		return NULL;
+
+	if (graph_size < GRAPH_MIN_SIZE)
+		return NULL;
+
 	data = (const unsigned char *)graph_map;
 
 	graph_signature = get_be32(data);
 	if (graph_signature != GRAPH_SIGNATURE) {
 		error(_("graph signature %X does not match signature %X"),
 		      graph_signature, GRAPH_SIGNATURE);
-		goto cleanup_fail;
+		return NULL;
 	}
 
 	graph_version = *(unsigned char*)(data + 4);
 	if (graph_version != GRAPH_VERSION) {
 		error(_("graph version %X does not match version %X"),
 		      graph_version, GRAPH_VERSION);
-		goto cleanup_fail;
+		return NULL;
 	}
 
 	hash_version = *(unsigned char*)(data + 5);
 	if (hash_version != GRAPH_OID_VERSION) {
 		error(_("hash version %X does not match version %X"),
 		      hash_version, GRAPH_OID_VERSION);
-		goto cleanup_fail;
+		return NULL;
 	}
 
 	graph = alloc_commit_graph();
@@ -152,7 +174,8 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 		if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
 			error(_("improper chunk offset %08x%08x"), (uint32_t)(chunk_offset >> 32),
 			      (uint32_t)chunk_offset);
-			goto cleanup_fail;
+			free(graph);
+			return NULL;
 		}
 
 		switch (chunk_id) {
@@ -187,7 +210,8 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 
 		if (chunk_repeated) {
 			error(_("chunk id %08x appears multiple times"), chunk_id);
-			goto cleanup_fail;
+			free(graph);
+			return NULL;
 		}
 
 		if (last_chunk_id == GRAPH_CHUNKID_OIDLOOKUP)
@@ -201,11 +225,6 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 	}
 
 	return graph;
-
-cleanup_fail:
-	munmap(graph_map, graph_size);
-	close(fd);
-	exit(1);
 }
 
 static void prepare_commit_graph_one(struct repository *r, const char *obj_dir)
diff --git a/commit-graph.h b/commit-graph.h
index 9db40b4d3a..813e7c19f1 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -54,6 +54,9 @@ struct commit_graph {
 
 struct commit_graph *load_commit_graph_one(const char *graph_file);
 
+struct commit_graph *parse_commit_graph(void *graph_map, int fd,
+					size_t graph_size);
+
 /*
  * Return 1 if and only if the repository has a commit-graph
  * file and generation numbers are computed in that file.
diff --git a/fuzz-commit-graph.c b/fuzz-commit-graph.c
new file mode 100644
index 0000000000..cf790c9d04
--- /dev/null
+++ b/fuzz-commit-graph.c
@@ -0,0 +1,16 @@
+#include "commit-graph.h"
+
+struct commit_graph *parse_commit_graph(void *graph_map, int fd,
+					size_t graph_size);
+
+int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size);
+
+int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)
+{
+	struct commit_graph *g;
+
+	g = parse_commit_graph((void *)data, -1, size);
+	free(g);
+
+	return 0;
+}
-- 
2.20.0.rc2.12.g4c11c11dec

[PATCH v3 2/3] commit-graph: fix buffer read-overflow

[Josh Steadmon]

fuzz-commit-graph identified a case where Git will read past the end of
a buffer containing a commit graph if the graph's header has an
incorrect chunk count. A simple bounds check in parse_commit_graph()
prevents this.

Signed-off-by: Josh Steadmon <steadmon@google.com>
---
 commit-graph.c          | 14 ++++++++++++--
 t/t5318-commit-graph.sh | 15 +++++++++++++--
 2 files changed, 25 insertions(+), 4 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index 07dd410f3c..836d65a1d3 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -165,10 +165,20 @@ struct commit_graph *parse_commit_graph(void *graph_map, int fd,
 	last_chunk_offset = 8;
 	chunk_lookup = data + 8;
 	for (i = 0; i < graph->num_chunks; i++) {
-		uint32_t chunk_id = get_be32(chunk_lookup + 0);
-		uint64_t chunk_offset = get_be64(chunk_lookup + 4);
+		uint32_t chunk_id;
+		uint64_t chunk_offset;
 		int chunk_repeated = 0;
 
+		if (data + graph_size - chunk_lookup <
+		    GRAPH_CHUNKLOOKUP_WIDTH) {
+			error(_("chunk lookup table entry missing; graph file may be incomplete"));
+			free(graph);
+			return NULL;
+		}
+
+		chunk_id = get_be32(chunk_lookup + 0);
+		chunk_offset = get_be64(chunk_lookup + 4);
+
 		chunk_lookup += GRAPH_CHUNKLOOKUP_WIDTH;
 
 		if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index 5fe21db99f..5b6b44b78e 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -366,24 +366,30 @@ GRAPH_OCTOPUS_DATA_OFFSET=$(($GRAPH_COMMIT_DATA_OFFSET + \
 GRAPH_BYTE_OCTOPUS=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4))
 GRAPH_BYTE_FOOTER=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4 * $NUM_OCTOPUS_EDGES))
 
-# usage: corrupt_graph_and_verify <position> <data> <string>
+# usage: corrupt_graph_and_verify <position> <data> <string> [<zero_pos>]
 # Manipulates the commit-graph file at the position
-# by inserting the data, then runs 'git commit-graph verify'
+# by inserting the data, optionally zeroing the file
+# starting at <zero_pos>, then runs 'git commit-graph verify'
 # and places the output in the file 'err'. Test 'err' for
 # the given string.
 corrupt_graph_and_verify() {
 	pos=$1
 	data="${2:-\0}"
 	grepstr=$3
+	orig_size=$(stat --format=%s $objdir/info/commit-graph)
+	zero_pos=${4:-${orig_size}}
 	cd "$TRASH_DIRECTORY/full" &&
 	test_when_finished mv commit-graph-backup $objdir/info/commit-graph &&
 	cp $objdir/info/commit-graph commit-graph-backup &&
 	printf "$data" | dd of="$objdir/info/commit-graph" bs=1 seek="$pos" conv=notrunc &&
+	truncate --size=$zero_pos $objdir/info/commit-graph &&
+	truncate --size=$orig_size $objdir/info/commit-graph &&
 	test_must_fail git commit-graph verify 2>test_err &&
 	grep -v "^+" test_err >err
 	test_i18ngrep "$grepstr" err
 }
 
+
 test_expect_success 'detect bad signature' '
 	corrupt_graph_and_verify 0 "\0" \
 		"graph signature"
@@ -484,6 +490,11 @@ test_expect_success 'detect invalid checksum hash' '
 		"incorrect checksum"
 '
 
+test_expect_success 'detect incorrect chunk count' '
+	corrupt_graph_and_verify $GRAPH_BYTE_CHUNK_COUNT "\xff" \
+		"chunk lookup table entry missing" $GRAPH_CHUNK_LOOKUP_OFFSET
+'
+
 test_expect_success 'git fsck (checks commit-graph)' '
 	cd "$TRASH_DIRECTORY/full" &&
 	git fsck &&
-- 
2.20.0.rc2.12.g4c11c11dec

[PATCH v3 3/3] Makefile: correct example fuzz build

[Josh Steadmon]

Signed-off-by: Josh Steadmon <steadmon@google.com>
---
 Makefile | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/Makefile b/Makefile
index 6b72f37c29..bbcfc2bc9f 100644
--- a/Makefile
+++ b/Makefile
@@ -3104,7 +3104,7 @@ cover_db_html: cover_db
 # An example command to build against libFuzzer from LLVM 4.0.0:
 #
 # make CC=clang CXX=clang++ \
-#      FUZZ_CXXFLAGS="-fsanitize-coverage=trace-pc-guard -fsanitize=address" \
+#      CFLAGS="-fsanitize-coverage=trace-pc-guard -fsanitize=address" \
 #      LIB_FUZZING_ENGINE=/usr/lib/llvm-4.0/lib/libFuzzer.a \
 #      fuzz-all
 #
-- 
2.20.0.rc2.12.g4c11c11dec

Re: [PATCH v3 2/3] commit-graph: fix buffer read-overflow

[Junio C Hamano]

Josh Steadmon <steadmon@google.com> writes:

> diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
> index 5fe21db99f..5b6b44b78e 100755
> --- a/t/t5318-commit-graph.sh
> +++ b/t/t5318-commit-graph.sh
> @@ -366,24 +366,30 @@ GRAPH_OCTOPUS_DATA_OFFSET=$(($GRAPH_COMMIT_DATA_OFFSET + \
>  GRAPH_BYTE_OCTOPUS=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4))
>  GRAPH_BYTE_FOOTER=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4 * $NUM_OCTOPUS_EDGES))
>  
> -# usage: corrupt_graph_and_verify <position> <data> <string>
> +# usage: corrupt_graph_and_verify <position> <data> <string> [<zero_pos>]
>  # Manipulates the commit-graph file at the position
> -# by inserting the data, then runs 'git commit-graph verify'
> +# by inserting the data, optionally zeroing the file
> +# starting at <zero_pos>, then runs 'git commit-graph verify'
>  # and places the output in the file 'err'. Test 'err' for
>  # the given string.
>  corrupt_graph_and_verify() {
>  	pos=$1
>  	data="${2:-\0}"
>  	grepstr=$3
> +	orig_size=$(stat --format=%s $objdir/info/commit-graph)

"stat(1)" is not so portable, so you'll get complaints from minority
platform users later.  So is "truncate(1)".

> +	zero_pos=${4:-${orig_size}}
>  	cd "$TRASH_DIRECTORY/full" &&
>  	test_when_finished mv commit-graph-backup $objdir/info/commit-graph &&
>  	cp $objdir/info/commit-graph commit-graph-backup &&
>  	printf "$data" | dd of="$objdir/info/commit-graph" bs=1 seek="$pos" conv=notrunc &&
> +	truncate --size=$zero_pos $objdir/info/commit-graph &&
> +	truncate --size=$orig_size $objdir/info/commit-graph &&
>  	test_must_fail git commit-graph verify 2>test_err &&
>  	grep -v "^+" test_err >err
>  	test_i18ngrep "$grepstr" err
>  }
>  
> +
>  test_expect_success 'detect bad signature' '
>  	corrupt_graph_and_verify 0 "\0" \
>  		"graph signature"
> @@ -484,6 +490,11 @@ test_expect_success 'detect invalid checksum hash' '
>  		"incorrect checksum"
>  '
>  
> +test_expect_success 'detect incorrect chunk count' '
> +	corrupt_graph_and_verify $GRAPH_BYTE_CHUNK_COUNT "\xff" \

Implementations of printf(1) may not grok "\xff" as a valid
representation of "\377".  The shell built-in of dash(1) for example
would not work with this.

> +		"chunk lookup table entry missing" $GRAPH_CHUNK_LOOKUP_OFFSET
> +'
> +
>  test_expect_success 'git fsck (checks commit-graph)' '
>  	cd "$TRASH_DIRECTORY/full" &&
>  	git fsck &&

Re: [PATCH v3 2/3] commit-graph: fix buffer read-overflow

[SZEDER Gábor]

On Sun, Dec 09, 2018 at 01:01:29PM +0900, Junio C Hamano wrote:
> Josh Steadmon <steadmon@google.com> writes:
> 
> > diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
> > index 5fe21db99f..5b6b44b78e 100755
> > --- a/t/t5318-commit-graph.sh
> > +++ b/t/t5318-commit-graph.sh
> > @@ -366,24 +366,30 @@ GRAPH_OCTOPUS_DATA_OFFSET=$(($GRAPH_COMMIT_DATA_OFFSET + \
> >  GRAPH_BYTE_OCTOPUS=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4))
> >  GRAPH_BYTE_FOOTER=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4 * $NUM_OCTOPUS_EDGES))
> >  
> > -# usage: corrupt_graph_and_verify <position> <data> <string>
> > +# usage: corrupt_graph_and_verify <position> <data> <string> [<zero_pos>]
> >  # Manipulates the commit-graph file at the position
> > -# by inserting the data, then runs 'git commit-graph verify'
> > +# by inserting the data, optionally zeroing the file
> > +# starting at <zero_pos>, then runs 'git commit-graph verify'
> >  # and places the output in the file 'err'. Test 'err' for
> >  # the given string.
> >  corrupt_graph_and_verify() {
> >  	pos=$1
> >  	data="${2:-\0}"
> >  	grepstr=$3
> > +	orig_size=$(stat --format=%s $objdir/info/commit-graph)
> 
> "stat(1)" is not so portable, so you'll get complaints from minority
> platform users later.  So is "truncate(1)".

I complain: this patch breaks on macOS (on Travis CI), but in a
curious way.  First, 'stat' in the above line errors out with:

  +++stat --format=%s .git/objects/info/commit-graph
  stat: illegal option -- -
  usage: stat [-FlLnqrsx] [-f format] [-t timefmt] [file ...]

Alas, this doesn't immediately fail the test, because it's not part of
the &&-chain.

> > +	zero_pos=${4:-${orig_size}}

No && here, either.

> >  	cd "$TRASH_DIRECTORY/full" &&
> >  	test_when_finished mv commit-graph-backup $objdir/info/commit-graph &&
> >  	cp $objdir/info/commit-graph commit-graph-backup &&
> >  	printf "$data" | dd of="$objdir/info/commit-graph" bs=1 seek="$pos" conv=notrunc &&
> > +	truncate --size=$zero_pos $objdir/info/commit-graph &&

  ++truncate --size= .git/objects/info/commit-graph
  t5318-commit-graph.sh: line 385: truncate: command not found

Note that even if 'truncate' were available, it would most likely
complain about the empty '--size=' argument resulting from the 'stat'
error above.

Alas, this doesn't fail the test, either, because ...

> > +	truncate --size=$orig_size $objdir/info/commit-graph &&
> >  	test_must_fail git commit-graph verify 2>test_err &&
> >  	grep -v "^+" test_err >err

... here the &&-chain was broken already before this patch.  However,
since this above command was not executed due to the missing
'truncate', it didn't have a chance to create the 'err' file, ...

> >  	test_i18ngrep "$grepstr" err

... so 'test_i18ngrep' can't find the file, which triggers its linting
error, finally aborting the whole test script.

> >  }
> >  
> > +

Stray newline.

> >  test_expect_success 'detect bad signature' '
> >  	corrupt_graph_and_verify 0 "\0" \
> >  		"graph signature"
> > @@ -484,6 +490,11 @@ test_expect_success 'detect invalid checksum hash' '
> >  		"incorrect checksum"
> >  '
> >  
> > +test_expect_success 'detect incorrect chunk count' '
> > +	corrupt_graph_and_verify $GRAPH_BYTE_CHUNK_COUNT "\xff" \
> 
> Implementations of printf(1) may not grok "\xff" as a valid
> representation of "\377".  The shell built-in of dash(1) for example
> would not work with this.
> 
> > +		"chunk lookup table entry missing" $GRAPH_CHUNK_LOOKUP_OFFSET
> > +'
> > +
> >  test_expect_success 'git fsck (checks commit-graph)' '
> >  	cd "$TRASH_DIRECTORY/full" &&
> >  	git fsck &&

Re: [PATCH v3 2/3] commit-graph: fix buffer read-overflow

[Josh Steadmon]

On 2018.12.09 13:01, Junio C Hamano wrote:
> Josh Steadmon <steadmon@google.com> writes:
> 
> > diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
> > index 5fe21db99f..5b6b44b78e 100755
> > --- a/t/t5318-commit-graph.sh
> > +++ b/t/t5318-commit-graph.sh
> > @@ -366,24 +366,30 @@ GRAPH_OCTOPUS_DATA_OFFSET=$(($GRAPH_COMMIT_DATA_OFFSET + \
> >  GRAPH_BYTE_OCTOPUS=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4))
> >  GRAPH_BYTE_FOOTER=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4 * $NUM_OCTOPUS_EDGES))
> >  
> > -# usage: corrupt_graph_and_verify <position> <data> <string>
> > +# usage: corrupt_graph_and_verify <position> <data> <string> [<zero_pos>]
> >  # Manipulates the commit-graph file at the position
> > -# by inserting the data, then runs 'git commit-graph verify'
> > +# by inserting the data, optionally zeroing the file
> > +# starting at <zero_pos>, then runs 'git commit-graph verify'
> >  # and places the output in the file 'err'. Test 'err' for
> >  # the given string.
> >  corrupt_graph_and_verify() {
> >  	pos=$1
> >  	data="${2:-\0}"
> >  	grepstr=$3
> > +	orig_size=$(stat --format=%s $objdir/info/commit-graph)
> 
> "stat(1)" is not so portable, so you'll get complaints from minority
> platform users later.  So is "truncate(1)".

Ack, thanks for the catch. I have a workaround for stat in the form of
"wc -c", and for truncate with a combination of dd and /dev/zero.
However, I'm finding conflicting information about whether or not
/dev/zero exists on macOS. At the least, it sounds like it might not
work on very old versions. Would this be acceptable, or should I add a
new test function to do this?

> > +	zero_pos=${4:-${orig_size}}
> >  	cd "$TRASH_DIRECTORY/full" &&
> >  	test_when_finished mv commit-graph-backup $objdir/info/commit-graph &&
> >  	cp $objdir/info/commit-graph commit-graph-backup &&
> >  	printf "$data" | dd of="$objdir/info/commit-graph" bs=1 seek="$pos" conv=notrunc &&
> > +	truncate --size=$zero_pos $objdir/info/commit-graph &&
> > +	truncate --size=$orig_size $objdir/info/commit-graph &&
> >  	test_must_fail git commit-graph verify 2>test_err &&
> >  	grep -v "^+" test_err >err
> >  	test_i18ngrep "$grepstr" err
> >  }
> >  
> > +
> >  test_expect_success 'detect bad signature' '
> >  	corrupt_graph_and_verify 0 "\0" \
> >  		"graph signature"
> > @@ -484,6 +490,11 @@ test_expect_success 'detect invalid checksum hash' '
> >  		"incorrect checksum"
> >  '
> >  
> > +test_expect_success 'detect incorrect chunk count' '
> > +	corrupt_graph_and_verify $GRAPH_BYTE_CHUNK_COUNT "\xff" \
> 
> Implementations of printf(1) may not grok "\xff" as a valid
> representation of "\377".  The shell built-in of dash(1) for example
> would not work with this.

Ack, will fix in V4. Thanks.

> > +		"chunk lookup table entry missing" $GRAPH_CHUNK_LOOKUP_OFFSET
> > +'
> > +
> >  test_expect_success 'git fsck (checks commit-graph)' '
> >  	cd "$TRASH_DIRECTORY/full" &&
> >  	git fsck &&

Re: [PATCH v3 2/3] commit-graph: fix buffer read-overflow

[Josh Steadmon]

On 2018.12.10 05:28, SZEDER Gábor wrote:
> On Sun, Dec 09, 2018 at 01:01:29PM +0900, Junio C Hamano wrote:
> > Josh Steadmon <steadmon@google.com> writes:
> > 
> > > diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
> > > index 5fe21db99f..5b6b44b78e 100755
> > > --- a/t/t5318-commit-graph.sh
> > > +++ b/t/t5318-commit-graph.sh
> > > @@ -366,24 +366,30 @@ GRAPH_OCTOPUS_DATA_OFFSET=$(($GRAPH_COMMIT_DATA_OFFSET + \
> > >  GRAPH_BYTE_OCTOPUS=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4))
> > >  GRAPH_BYTE_FOOTER=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4 * $NUM_OCTOPUS_EDGES))
> > >  
> > > -# usage: corrupt_graph_and_verify <position> <data> <string>
> > > +# usage: corrupt_graph_and_verify <position> <data> <string> [<zero_pos>]
> > >  # Manipulates the commit-graph file at the position
> > > -# by inserting the data, then runs 'git commit-graph verify'
> > > +# by inserting the data, optionally zeroing the file
> > > +# starting at <zero_pos>, then runs 'git commit-graph verify'
> > >  # and places the output in the file 'err'. Test 'err' for
> > >  # the given string.
> > >  corrupt_graph_and_verify() {
> > >  	pos=$1
> > >  	data="${2:-\0}"
> > >  	grepstr=$3
> > > +	orig_size=$(stat --format=%s $objdir/info/commit-graph)
> > 
> > "stat(1)" is not so portable, so you'll get complaints from minority
> > platform users later.  So is "truncate(1)".
> 
> I complain: this patch breaks on macOS (on Travis CI), but in a
> curious way.  First, 'stat' in the above line errors out with:
> 
>   +++stat --format=%s .git/objects/info/commit-graph
>   stat: illegal option -- -
>   usage: stat [-FlLnqrsx] [-f format] [-t timefmt] [file ...]
> 
> Alas, this doesn't immediately fail the test, because it's not part of
> the &&-chain.
> 
> > > +	zero_pos=${4:-${orig_size}}
> 
> No && here, either.
> 
> > >  	cd "$TRASH_DIRECTORY/full" &&
> > >  	test_when_finished mv commit-graph-backup $objdir/info/commit-graph &&
> > >  	cp $objdir/info/commit-graph commit-graph-backup &&
> > >  	printf "$data" | dd of="$objdir/info/commit-graph" bs=1 seek="$pos" conv=notrunc &&
> > > +	truncate --size=$zero_pos $objdir/info/commit-graph &&
> 
>   ++truncate --size= .git/objects/info/commit-graph
>   t5318-commit-graph.sh: line 385: truncate: command not found
> 
> Note that even if 'truncate' were available, it would most likely
> complain about the empty '--size=' argument resulting from the 'stat'
> error above.
> 
> Alas, this doesn't fail the test, either, because ...
> 
> > > +	truncate --size=$orig_size $objdir/info/commit-graph &&
> > >  	test_must_fail git commit-graph verify 2>test_err &&
> > >  	grep -v "^+" test_err >err
> 
> ... here the &&-chain was broken already before this patch.  However,
> since this above command was not executed due to the missing
> 'truncate', it didn't have a chance to create the 'err' file, ...
> 
> > >  	test_i18ngrep "$grepstr" err
> 
> ... so 'test_i18ngrep' can't find the file, which triggers its linting
> error, finally aborting the whole test script.
> 
> > >  }
> > >  
> > > +
> 
> Stray newline.
> 
> > >  test_expect_success 'detect bad signature' '
> > >  	corrupt_graph_and_verify 0 "\0" \
> > >  		"graph signature"
> > > @@ -484,6 +490,11 @@ test_expect_success 'detect invalid checksum hash' '
> > >  		"incorrect checksum"
> > >  '
> > >  
> > > +test_expect_success 'detect incorrect chunk count' '
> > > +	corrupt_graph_and_verify $GRAPH_BYTE_CHUNK_COUNT "\xff" \
> > 
> > Implementations of printf(1) may not grok "\xff" as a valid
> > representation of "\377".  The shell built-in of dash(1) for example
> > would not work with this.
> > 
> > > +		"chunk lookup table entry missing" $GRAPH_CHUNK_LOOKUP_OFFSET
> > > +'
> > > +
> > >  test_expect_success 'git fsck (checks commit-graph)' '
> > >  	cd "$TRASH_DIRECTORY/full" &&
> > >  	git fsck &&

Thanks for the catch. All these will be fixed in V4.

Re: [PATCH v3 2/3] commit-graph: fix buffer read-overflow

[Jeff King]

On Mon, Dec 10, 2018 at 01:56:49PM -0800, Josh Steadmon wrote:

> > "stat(1)" is not so portable, so you'll get complaints from minority
> > platform users later.  So is "truncate(1)".
> 
> Ack, thanks for the catch. I have a workaround for stat in the form of
> "wc -c", and for truncate with a combination of dd and /dev/zero.
> However, I'm finding conflicting information about whether or not
> /dev/zero exists on macOS. At the least, it sounds like it might not
> work on very old versions. Would this be acceptable, or should I add a
> new test function to do this?

If you're just interested in truncation (and not a bunch of zero bytes),
you can dd from /dev/null.

Another way to truncate is to move the file elsewhere, and then copy
only some of the bytes back (see t1450's "fsck detects truncated loose
object").

-Peff

[PATCH v4 0/3] Add commit-graph fuzzer and fix buffer overflow

[Josh Steadmon]

Add a new fuzz test for the commit graph and fix a buffer read-overflow
that it discovered. Additionally, fix the Makefile instructions for
building fuzzers.

Changes since V3:
  * Improve portability of the new test functionality.
  * Fix broken &&-chains in tests.

Changes since V2:
  * Avoid pointer arithmetic overflow when checking the graph's chunk
    count.
  * Merge the corrupt_graph_and_verify and
    corrupt_and_zero_graph_then_verify test functions.

Josh Steadmon (3):
  commit-graph, fuzz: Add fuzzer for commit-graph
  commit-graph: fix buffer read-overflow
  Makefile: correct example fuzz build

 .gitignore              |  1 +
 Makefile                |  3 +-
 commit-graph.c          | 67 +++++++++++++++++++++++++++++------------
 commit-graph.h          |  3 ++
 fuzz-commit-graph.c     | 16 ++++++++++
 t/t5318-commit-graph.sh | 16 ++++++++--
 6 files changed, 83 insertions(+), 23 deletions(-)
 create mode 100644 fuzz-commit-graph.c

Range-diff against v3:
1:  675d58ecea ! 1:  80b5662f30 commit-graph: fix buffer read-overflow
    @@ -55,29 +55,26 @@
      	pos=$1
      	data="${2:-\0}"
      	grepstr=$3
    -+	orig_size=$(stat --format=%s $objdir/info/commit-graph)
    -+	zero_pos=${4:-${orig_size}}
    ++	orig_size=$(wc -c < $objdir/info/commit-graph) &&
    ++	zero_pos=${4:-${orig_size}} &&
      	cd "$TRASH_DIRECTORY/full" &&
      	test_when_finished mv commit-graph-backup $objdir/info/commit-graph &&
      	cp $objdir/info/commit-graph commit-graph-backup &&
      	printf "$data" | dd of="$objdir/info/commit-graph" bs=1 seek="$pos" conv=notrunc &&
    -+	truncate --size=$zero_pos $objdir/info/commit-graph &&
    -+	truncate --size=$orig_size $objdir/info/commit-graph &&
    ++	dd of="$objdir/info/commit-graph" bs=1 seek="$zero_pos" count=0 &&
    ++	dd if=/dev/zero of="$objdir/info/commit-graph" bs=1 seek="$zero_pos" count=$(($orig_size - $zero_pos)) &&
      	test_must_fail git commit-graph verify 2>test_err &&
    - 	grep -v "^+" test_err >err
    +-	grep -v "^+" test_err >err
    ++	grep -v "^+" test_err >err &&
      	test_i18ngrep "$grepstr" err
      }
      
    -+
    - test_expect_success 'detect bad signature' '
    - 	corrupt_graph_and_verify 0 "\0" \
    - 		"graph signature"
     @@
      		"incorrect checksum"
      '
      
     +test_expect_success 'detect incorrect chunk count' '
    -+	corrupt_graph_and_verify $GRAPH_BYTE_CHUNK_COUNT "\xff" \
    ++	corrupt_graph_and_verify $GRAPH_BYTE_CHUNK_COUNT "\377" \
     +		"chunk lookup table entry missing" $GRAPH_CHUNK_LOOKUP_OFFSET
     +'
     +
2:  06a32bfe8b = 2:  21101b961a Makefile: correct example fuzz build
-- 
2.20.0.rc2.10.g21101b961a

[PATCH v4 1/3] commit-graph, fuzz: Add fuzzer for commit-graph

[Josh Steadmon]

Breaks load_commit_graph_one() into a new function,
parse_commit_graph(). The latter function operates on arbitrary buffers,
which makes it suitable as a fuzzing target. Since parse_commit_graph()
is only called by load_commit_graph_one() (and the fuzzer described
below), we omit error messages that would be duplicated by the caller.

Adds fuzz-commit-graph.c, which provides a fuzzing entry point
compatible with libFuzzer (and possibly other fuzzing engines).

Signed-off-by: Josh Steadmon <steadmon@google.com>
---
 .gitignore          |  1 +
 Makefile            |  1 +
 commit-graph.c      | 53 ++++++++++++++++++++++++++++++---------------
 commit-graph.h      |  3 +++
 fuzz-commit-graph.c | 16 ++++++++++++++
 5 files changed, 57 insertions(+), 17 deletions(-)
 create mode 100644 fuzz-commit-graph.c

diff --git a/.gitignore b/.gitignore
index 0d77ea5894..8bcf153ed9 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,4 @@
+/fuzz-commit-graph
 /fuzz_corpora
 /fuzz-pack-headers
 /fuzz-pack-idx
diff --git a/Makefile b/Makefile
index 1a44c811aa..6b72f37c29 100644
--- a/Makefile
+++ b/Makefile
@@ -684,6 +684,7 @@ SCRIPTS = $(SCRIPT_SH_INS) \
 
 ETAGS_TARGET = TAGS
 
+FUZZ_OBJS += fuzz-commit-graph.o
 FUZZ_OBJS += fuzz-pack-headers.o
 FUZZ_OBJS += fuzz-pack-idx.o
 
diff --git a/commit-graph.c b/commit-graph.c
index 40c855f185..07dd410f3c 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -84,16 +84,10 @@ static int commit_graph_compatible(struct repository *r)
 struct commit_graph *load_commit_graph_one(const char *graph_file)
 {
 	void *graph_map;
-	const unsigned char *data, *chunk_lookup;
 	size_t graph_size;
 	struct stat st;
-	uint32_t i;
-	struct commit_graph *graph;
+	struct commit_graph *ret;
 	int fd = git_open(graph_file);
-	uint64_t last_chunk_offset;
-	uint32_t last_chunk_id;
-	uint32_t graph_signature;
-	unsigned char graph_version, hash_version;
 
 	if (fd < 0)
 		return NULL;
@@ -108,27 +102,55 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 		die(_("graph file %s is too small"), graph_file);
 	}
 	graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);
+	ret = parse_commit_graph(graph_map, fd, graph_size);
+
+	if (!ret) {
+		munmap(graph_map, graph_size);
+		close(fd);
+		exit(1);
+	}
+
+	return ret;
+}
+
+struct commit_graph *parse_commit_graph(void *graph_map, int fd,
+					size_t graph_size)
+{
+	const unsigned char *data, *chunk_lookup;
+	uint32_t i;
+	struct commit_graph *graph;
+	uint64_t last_chunk_offset;
+	uint32_t last_chunk_id;
+	uint32_t graph_signature;
+	unsigned char graph_version, hash_version;
+
+	if (!graph_map)
+		return NULL;
+
+	if (graph_size < GRAPH_MIN_SIZE)
+		return NULL;
+
 	data = (const unsigned char *)graph_map;
 
 	graph_signature = get_be32(data);
 	if (graph_signature != GRAPH_SIGNATURE) {
 		error(_("graph signature %X does not match signature %X"),
 		      graph_signature, GRAPH_SIGNATURE);
-		goto cleanup_fail;
+		return NULL;
 	}
 
 	graph_version = *(unsigned char*)(data + 4);
 	if (graph_version != GRAPH_VERSION) {
 		error(_("graph version %X does not match version %X"),
 		      graph_version, GRAPH_VERSION);
-		goto cleanup_fail;
+		return NULL;
 	}
 
 	hash_version = *(unsigned char*)(data + 5);
 	if (hash_version != GRAPH_OID_VERSION) {
 		error(_("hash version %X does not match version %X"),
 		      hash_version, GRAPH_OID_VERSION);
-		goto cleanup_fail;
+		return NULL;
 	}
 
 	graph = alloc_commit_graph();
@@ -152,7 +174,8 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 		if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
 			error(_("improper chunk offset %08x%08x"), (uint32_t)(chunk_offset >> 32),
 			      (uint32_t)chunk_offset);
-			goto cleanup_fail;
+			free(graph);
+			return NULL;
 		}
 
 		switch (chunk_id) {
@@ -187,7 +210,8 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 
 		if (chunk_repeated) {
 			error(_("chunk id %08x appears multiple times"), chunk_id);
-			goto cleanup_fail;
+			free(graph);
+			return NULL;
 		}
 
 		if (last_chunk_id == GRAPH_CHUNKID_OIDLOOKUP)
@@ -201,11 +225,6 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 	}
 
 	return graph;
-
-cleanup_fail:
-	munmap(graph_map, graph_size);
-	close(fd);
-	exit(1);
 }
 
 static void prepare_commit_graph_one(struct repository *r, const char *obj_dir)
diff --git a/commit-graph.h b/commit-graph.h
index 9db40b4d3a..813e7c19f1 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -54,6 +54,9 @@ struct commit_graph {
 
 struct commit_graph *load_commit_graph_one(const char *graph_file);
 
+struct commit_graph *parse_commit_graph(void *graph_map, int fd,
+					size_t graph_size);
+
 /*
  * Return 1 if and only if the repository has a commit-graph
  * file and generation numbers are computed in that file.
diff --git a/fuzz-commit-graph.c b/fuzz-commit-graph.c
new file mode 100644
index 0000000000..cf790c9d04
--- /dev/null
+++ b/fuzz-commit-graph.c
@@ -0,0 +1,16 @@
+#include "commit-graph.h"
+
+struct commit_graph *parse_commit_graph(void *graph_map, int fd,
+					size_t graph_size);
+
+int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size);
+
+int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)
+{
+	struct commit_graph *g;
+
+	g = parse_commit_graph((void *)data, -1, size);
+	free(g);
+
+	return 0;
+}
-- 
2.20.0.rc2.10.g21101b961a

[PATCH v4 2/3] commit-graph: fix buffer read-overflow

[Josh Steadmon]

fuzz-commit-graph identified a case where Git will read past the end of
a buffer containing a commit graph if the graph's header has an
incorrect chunk count. A simple bounds check in parse_commit_graph()
prevents this.

Signed-off-by: Josh Steadmon <steadmon@google.com>
---
 commit-graph.c          | 14 ++++++++++++--
 t/t5318-commit-graph.sh | 16 +++++++++++++---
 2 files changed, 25 insertions(+), 5 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index 07dd410f3c..836d65a1d3 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -165,10 +165,20 @@ struct commit_graph *parse_commit_graph(void *graph_map, int fd,
 	last_chunk_offset = 8;
 	chunk_lookup = data + 8;
 	for (i = 0; i < graph->num_chunks; i++) {
-		uint32_t chunk_id = get_be32(chunk_lookup + 0);
-		uint64_t chunk_offset = get_be64(chunk_lookup + 4);
+		uint32_t chunk_id;
+		uint64_t chunk_offset;
 		int chunk_repeated = 0;
 
+		if (data + graph_size - chunk_lookup <
+		    GRAPH_CHUNKLOOKUP_WIDTH) {
+			error(_("chunk lookup table entry missing; graph file may be incomplete"));
+			free(graph);
+			return NULL;
+		}
+
+		chunk_id = get_be32(chunk_lookup + 0);
+		chunk_offset = get_be64(chunk_lookup + 4);
+
 		chunk_lookup += GRAPH_CHUNKLOOKUP_WIDTH;
 
 		if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index 5fe21db99f..a1b5a75882 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -366,21 +366,26 @@ GRAPH_OCTOPUS_DATA_OFFSET=$(($GRAPH_COMMIT_DATA_OFFSET + \
 GRAPH_BYTE_OCTOPUS=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4))
 GRAPH_BYTE_FOOTER=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4 * $NUM_OCTOPUS_EDGES))
 
-# usage: corrupt_graph_and_verify <position> <data> <string>
+# usage: corrupt_graph_and_verify <position> <data> <string> [<zero_pos>]
 # Manipulates the commit-graph file at the position
-# by inserting the data, then runs 'git commit-graph verify'
+# by inserting the data, optionally zeroing the file
+# starting at <zero_pos>, then runs 'git commit-graph verify'
 # and places the output in the file 'err'. Test 'err' for
 # the given string.
 corrupt_graph_and_verify() {
 	pos=$1
 	data="${2:-\0}"
 	grepstr=$3
+	orig_size=$(wc -c < $objdir/info/commit-graph) &&
+	zero_pos=${4:-${orig_size}} &&
 	cd "$TRASH_DIRECTORY/full" &&
 	test_when_finished mv commit-graph-backup $objdir/info/commit-graph &&
 	cp $objdir/info/commit-graph commit-graph-backup &&
 	printf "$data" | dd of="$objdir/info/commit-graph" bs=1 seek="$pos" conv=notrunc &&
+	dd of="$objdir/info/commit-graph" bs=1 seek="$zero_pos" count=0 &&
+	dd if=/dev/zero of="$objdir/info/commit-graph" bs=1 seek="$zero_pos" count=$(($orig_size - $zero_pos)) &&
 	test_must_fail git commit-graph verify 2>test_err &&
-	grep -v "^+" test_err >err
+	grep -v "^+" test_err >err &&
 	test_i18ngrep "$grepstr" err
 }
 
@@ -484,6 +489,11 @@ test_expect_success 'detect invalid checksum hash' '
 		"incorrect checksum"
 '
 
+test_expect_success 'detect incorrect chunk count' '
+	corrupt_graph_and_verify $GRAPH_BYTE_CHUNK_COUNT "\377" \
+		"chunk lookup table entry missing" $GRAPH_CHUNK_LOOKUP_OFFSET
+'
+
 test_expect_success 'git fsck (checks commit-graph)' '
 	cd "$TRASH_DIRECTORY/full" &&
 	git fsck &&
-- 
2.20.0.rc2.10.g21101b961a

[PATCH v4 3/3] Makefile: correct example fuzz build

[Josh Steadmon]

Signed-off-by: Josh Steadmon <steadmon@google.com>
---
 Makefile | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/Makefile b/Makefile
index 6b72f37c29..bbcfc2bc9f 100644
--- a/Makefile
+++ b/Makefile
@@ -3104,7 +3104,7 @@ cover_db_html: cover_db
 # An example command to build against libFuzzer from LLVM 4.0.0:
 #
 # make CC=clang CXX=clang++ \
-#      FUZZ_CXXFLAGS="-fsanitize-coverage=trace-pc-guard -fsanitize=address" \
+#      CFLAGS="-fsanitize-coverage=trace-pc-guard -fsanitize=address" \
 #      LIB_FUZZING_ENGINE=/usr/lib/llvm-4.0/lib/libFuzzer.a \
 #      fuzz-all
 #
-- 
2.20.0.rc2.10.g21101b961a

Re: [PATCH v4 0/3] Add commit-graph fuzzer and fix buffer overflow

[Jeff King]

On Thu, Dec 13, 2018 at 11:43:55AM -0800, Josh Steadmon wrote:

> Add a new fuzz test for the commit graph and fix a buffer read-overflow
> that it discovered. Additionally, fix the Makefile instructions for
> building fuzzers.
> 
> Changes since V3:
>   * Improve portability of the new test functionality.

I thought there was some question about /dev/zero, which I think is
in this version (I don't actually know whether there are portability
issues or not, but somebody did mention it).

-Peff

Re: [PATCH v4 0/3] Add commit-graph fuzzer and fix buffer overflow

[Josh Steadmon]

On 2018.12.18 12:35, Jeff King wrote:
> On Thu, Dec 13, 2018 at 11:43:55AM -0800, Josh Steadmon wrote:
> 
> > Add a new fuzz test for the commit graph and fix a buffer read-overflow
> > that it discovered. Additionally, fix the Makefile instructions for
> > building fuzzers.
> > 
> > Changes since V3:
> >   * Improve portability of the new test functionality.
> 
> I thought there was some question about /dev/zero, which I think is
> in this version (I don't actually know whether there are portability
> issues or not, but somebody did mention it).
> 
> -Peff

I've only found one reference [1] (from 1999) of OS X Server not having
a /dev/zero. It appears to be present as of 2010 though [2].

[1]: https://macosx-admin.omnigroup.narkive.com/sAxj0XeP/dev-zero-equivalent-in-mac-os-x
[2]: https://serverfault.com/questions/143248/zeroing-a-disk-with-dd-vs-disk-utility

Re: [PATCH v4 0/3] Add commit-graph fuzzer and fix buffer overflow

[Jeff King]

On Tue, Dec 18, 2018 at 01:05:51PM -0800, Josh Steadmon wrote:

> On 2018.12.18 12:35, Jeff King wrote:
> > On Thu, Dec 13, 2018 at 11:43:55AM -0800, Josh Steadmon wrote:
> > 
> > > Add a new fuzz test for the commit graph and fix a buffer read-overflow
> > > that it discovered. Additionally, fix the Makefile instructions for
> > > building fuzzers.
> > > 
> > > Changes since V3:
> > >   * Improve portability of the new test functionality.
> > 
> > I thought there was some question about /dev/zero, which I think is
> > in this version (I don't actually know whether there are portability
> > issues or not, but somebody did mention it).
> > 
> > -Peff
> 
> I've only found one reference [1] (from 1999) of OS X Server not having
> a /dev/zero. It appears to be present as of 2010 though [2].

Thanks for digging. That seems like enough to assume we should try it
and see if any macOS people complain.

I do wonder if we'll run into problems on Windows, though.

-Peff

Re: [PATCH v4 0/3] Add commit-graph fuzzer and fix buffer overflow

[Johannes Schindelin]

Hi Peff,


On Wed, 19 Dec 2018, Jeff King wrote:

> On Tue, Dec 18, 2018 at 01:05:51PM -0800, Josh Steadmon wrote:
> 
> > On 2018.12.18 12:35, Jeff King wrote:
> > > On Thu, Dec 13, 2018 at 11:43:55AM -0800, Josh Steadmon wrote:
> > > 
> > > > Add a new fuzz test for the commit graph and fix a buffer read-overflow
> > > > that it discovered. Additionally, fix the Makefile instructions for
> > > > building fuzzers.
> > > > 
> > > > Changes since V3:
> > > >   * Improve portability of the new test functionality.
> > > 
> > > I thought there was some question about /dev/zero, which I think is
> > > in this version (I don't actually know whether there are portability
> > > issues or not, but somebody did mention it).
> > > 
> > > -Peff
> > 
> > I've only found one reference [1] (from 1999) of OS X Server not having
> > a /dev/zero. It appears to be present as of 2010 though [2].
> 
> Thanks for digging. That seems like enough to assume we should try it
> and see if any macOS people complain.
> 
> I do wonder if we'll run into problems on Windows, though.

As long as we're talking about Unix shell scripts, /dev/zero should be
fine, as we are essentially running in a variant of Cygwin.

If you try to pass /dev/zero as an argument to a Git command, that's an
entirely different thing: this most likely won't work.

Ciao,
Dscho

Re: [PATCH v4 0/3] Add commit-graph fuzzer and fix buffer overflow

[Jeff King]

On Thu, Dec 20, 2018 at 08:35:57PM +0100, Johannes Schindelin wrote:

> > I do wonder if we'll run into problems on Windows, though.
> 
> As long as we're talking about Unix shell scripts, /dev/zero should be
> fine, as we are essentially running in a variant of Cygwin.
> 
> If you try to pass /dev/zero as an argument to a Git command, that's an
> entirely different thing: this most likely won't work.

Thanks for confirming. We're talking about passing it to dd here, so I
think it should be OK.

-Peff

Re: [PATCH v4 0/3] Add commit-graph fuzzer and fix buffer overflow

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Tue, Dec 18, 2018 at 01:05:51PM -0800, Josh Steadmon wrote:
>
>> On 2018.12.18 12:35, Jeff King wrote:
>> > On Thu, Dec 13, 2018 at 11:43:55AM -0800, Josh Steadmon wrote:
>> > 
>> > > Add a new fuzz test for the commit graph and fix a buffer read-overflow
>> > > that it discovered. Additionally, fix the Makefile instructions for
>> > > building fuzzers.
>> > > 
>> > > Changes since V3:
>> > >   * Improve portability of the new test functionality.
>> > 
>> > I thought there was some question about /dev/zero, which I think is
>> > in this version (I don't actually know whether there are portability
>> > issues or not, but somebody did mention it).
>> > 
>> > -Peff
>> 
>> I've only found one reference [1] (from 1999) of OS X Server not having
>> a /dev/zero. It appears to be present as of 2010 though [2].
>
> Thanks for digging. That seems like enough to assume we should try it
> and see if any macOS people complain.

Our tests have been relying on /dev/zero since 852a1710 ("am: let
command-line options override saved options", 2015-08-04) that
appeared in v2.6.0.  Anybody who has trouble with /dev/zero now has
kept silent for about a dozen major releases, I think, and will be
silent with this one, too ;-)

>
> I do wonder if we'll run into problems on Windows, though.
>
> -Peff

Re: [PATCH v4 2/3] commit-graph: fix buffer read-overflow

[SZEDER Gábor]

On Thu, Dec 13, 2018 at 11:43:57AM -0800, Josh Steadmon wrote:
> diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
> index 5fe21db99f..a1b5a75882 100755
> --- a/t/t5318-commit-graph.sh
> +++ b/t/t5318-commit-graph.sh
> @@ -366,21 +366,26 @@ GRAPH_OCTOPUS_DATA_OFFSET=$(($GRAPH_COMMIT_DATA_OFFSET + \
>  GRAPH_BYTE_OCTOPUS=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4))
>  GRAPH_BYTE_FOOTER=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4 * $NUM_OCTOPUS_EDGES))
>  
> -# usage: corrupt_graph_and_verify <position> <data> <string>
> +# usage: corrupt_graph_and_verify <position> <data> <string> [<zero_pos>]
>  # Manipulates the commit-graph file at the position
> -# by inserting the data, then runs 'git commit-graph verify'
> +# by inserting the data, optionally zeroing the file
> +# starting at <zero_pos>, then runs 'git commit-graph verify'
>  # and places the output in the file 'err'. Test 'err' for
>  # the given string.
>  corrupt_graph_and_verify() {
>  	pos=$1
>  	data="${2:-\0}"
>  	grepstr=$3
> +	orig_size=$(wc -c < $objdir/info/commit-graph) &&

A minor nit: this test script is unusually prudent about which
directory/repository each test is executed in, as the first thing each
test does is to 'cd' into the right directory.  (I think this is a
Good Thing, and other test scripts should follow suit if they use a
repo other than $TRASH_DIRECTORY.)  Though it doesn't cause any
immediate issues (the previous test happens to use the same
repository), the above line violates this, as it accesses the
'.git/.../commit-graph' file ...

> +	zero_pos=${4:-${orig_size}} &&
>  	cd "$TRASH_DIRECTORY/full" &&

... before this line could ensure that it's in the right repository.

>  	test_when_finished mv commit-graph-backup $objdir/info/commit-graph &&
>  	cp $objdir/info/commit-graph commit-graph-backup &&
>  	printf "$data" | dd of="$objdir/info/commit-graph" bs=1 seek="$pos" conv=notrunc &&
> +	dd of="$objdir/info/commit-graph" bs=1 seek="$zero_pos" count=0 &&
> +	dd if=/dev/zero of="$objdir/info/commit-graph" bs=1 seek="$zero_pos" count=$(($orig_size - $zero_pos)) &&
>  	test_must_fail git commit-graph verify 2>test_err &&
> -	grep -v "^+" test_err >err
> +	grep -v "^+" test_err >err &&
>  	test_i18ngrep "$grepstr" err
>  }
>  
> @@ -484,6 +489,11 @@ test_expect_success 'detect invalid checksum hash' '
>  		"incorrect checksum"
>  '
>  
> +test_expect_success 'detect incorrect chunk count' '
> +	corrupt_graph_and_verify $GRAPH_BYTE_CHUNK_COUNT "\377" \
> +		"chunk lookup table entry missing" $GRAPH_CHUNK_LOOKUP_OFFSET
> +'
> +
>  test_expect_success 'git fsck (checks commit-graph)' '
>  	cd "$TRASH_DIRECTORY/full" &&
>  	git fsck &&
> -- 
> 2.20.0.rc2.10.g21101b961a
> 

Re: [PATCH v4 2/3] commit-graph: fix buffer read-overflow

[Josh Steadmon]

On 2019.01.12 11:57, SZEDER Gábor wrote:
> On Thu, Dec 13, 2018 at 11:43:57AM -0800, Josh Steadmon wrote:
> > diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
> > index 5fe21db99f..a1b5a75882 100755
> > --- a/t/t5318-commit-graph.sh
> > +++ b/t/t5318-commit-graph.sh
> > @@ -366,21 +366,26 @@ GRAPH_OCTOPUS_DATA_OFFSET=$(($GRAPH_COMMIT_DATA_OFFSET + \
> >  GRAPH_BYTE_OCTOPUS=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4))
> >  GRAPH_BYTE_FOOTER=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4 * $NUM_OCTOPUS_EDGES))
> >  
> > -# usage: corrupt_graph_and_verify <position> <data> <string>
> > +# usage: corrupt_graph_and_verify <position> <data> <string> [<zero_pos>]
> >  # Manipulates the commit-graph file at the position
> > -# by inserting the data, then runs 'git commit-graph verify'
> > +# by inserting the data, optionally zeroing the file
> > +# starting at <zero_pos>, then runs 'git commit-graph verify'
> >  # and places the output in the file 'err'. Test 'err' for
> >  # the given string.
> >  corrupt_graph_and_verify() {
> >  	pos=$1
> >  	data="${2:-\0}"
> >  	grepstr=$3
> > +	orig_size=$(wc -c < $objdir/info/commit-graph) &&
> 
> A minor nit: this test script is unusually prudent about which
> directory/repository each test is executed in, as the first thing each
> test does is to 'cd' into the right directory.  (I think this is a
> Good Thing, and other test scripts should follow suit if they use a
> repo other than $TRASH_DIRECTORY.)  Though it doesn't cause any
> immediate issues (the previous test happens to use the same
> repository), the above line violates this, as it accesses the
> '.git/.../commit-graph' file ...
> 
> > +	zero_pos=${4:-${orig_size}} &&
> >  	cd "$TRASH_DIRECTORY/full" &&
> 
> ... before this line could ensure that it's in the right repository.

Thanks for the catch. Fixed in v5.

[PATCH v5 0/3] Add commit-graph fuzzer and fix buffer overflow

[Josh Steadmon]

Add a new fuzz test for the commit graph and fix a buffer read-overflow
that it discovered. Additionally, fix the Makefile instructions for
building fuzzers.

Changes since V4:
  * Ensure that corrupt_graph_and_verify() in t5318 changes to the
    proper directory before accessing any files.

Changes since V3:
  * Improve portability of the new test functionality.
  * Fix broken &&-chains in tests.

Changes since V2:
  * Avoid pointer arithmetic overflow when checking the graph's chunk
    count.
  * Merge the corrupt_graph_and_verify and
    corrupt_and_zero_graph_then_verify test functions.

Josh Steadmon (3):
  commit-graph, fuzz: Add fuzzer for commit-graph
  commit-graph: fix buffer read-overflow
  Makefile: correct example fuzz build

Josh Steadmon (3):
  commit-graph, fuzz: Add fuzzer for commit-graph
  commit-graph: fix buffer read-overflow
  Makefile: correct example fuzz build

 .gitignore              |  1 +
 Makefile                |  3 +-
 commit-graph.c          | 67 +++++++++++++++++++++++++++++------------
 commit-graph.h          |  3 ++
 fuzz-commit-graph.c     | 16 ++++++++++
 t/t5318-commit-graph.sh | 16 ++++++++--
 6 files changed, 83 insertions(+), 23 deletions(-)
 create mode 100644 fuzz-commit-graph.c

Range-diff against v4:
1:  80b5662f30 ! 1:  a3b5d33c4b commit-graph: fix buffer read-overflow
    @@ -52,12 +52,12 @@
      # and places the output in the file 'err'. Test 'err' for
      # the given string.
      corrupt_graph_and_verify() {
    - 	pos=$1
    +@@
      	data="${2:-\0}"
      	grepstr=$3
    + 	cd "$TRASH_DIRECTORY/full" &&
     +	orig_size=$(wc -c < $objdir/info/commit-graph) &&
     +	zero_pos=${4:-${orig_size}} &&
    - 	cd "$TRASH_DIRECTORY/full" &&
      	test_when_finished mv commit-graph-backup $objdir/info/commit-graph &&
      	cp $objdir/info/commit-graph commit-graph-backup &&
      	printf "$data" | dd of="$objdir/info/commit-graph" bs=1 seek="$pos" conv=notrunc &&
2:  21101b961a = 2:  350ea5f7c9 Makefile: correct example fuzz build
-- 
2.20.1.97.g81188d93c3-goog

[PATCH v5 1/3] commit-graph, fuzz: Add fuzzer for commit-graph

[Josh Steadmon]

Breaks load_commit_graph_one() into a new function,
parse_commit_graph(). The latter function operates on arbitrary buffers,
which makes it suitable as a fuzzing target. Since parse_commit_graph()
is only called by load_commit_graph_one() (and the fuzzer described
below), we omit error messages that would be duplicated by the caller.

Adds fuzz-commit-graph.c, which provides a fuzzing entry point
compatible with libFuzzer (and possibly other fuzzing engines).

Signed-off-by: Josh Steadmon <steadmon@google.com>
---
 .gitignore          |  1 +
 Makefile            |  1 +
 commit-graph.c      | 53 ++++++++++++++++++++++++++++++---------------
 commit-graph.h      |  3 +++
 fuzz-commit-graph.c | 16 ++++++++++++++
 5 files changed, 57 insertions(+), 17 deletions(-)
 create mode 100644 fuzz-commit-graph.c

diff --git a/.gitignore b/.gitignore
index 0d77ea5894..8bcf153ed9 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,4 @@
+/fuzz-commit-graph
 /fuzz_corpora
 /fuzz-pack-headers
 /fuzz-pack-idx
diff --git a/Makefile b/Makefile
index 1a44c811aa..6b72f37c29 100644
--- a/Makefile
+++ b/Makefile
@@ -684,6 +684,7 @@ SCRIPTS = $(SCRIPT_SH_INS) \
 
 ETAGS_TARGET = TAGS
 
+FUZZ_OBJS += fuzz-commit-graph.o
 FUZZ_OBJS += fuzz-pack-headers.o
 FUZZ_OBJS += fuzz-pack-idx.o
 
diff --git a/commit-graph.c b/commit-graph.c
index 40c855f185..07dd410f3c 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -84,16 +84,10 @@ static int commit_graph_compatible(struct repository *r)
 struct commit_graph *load_commit_graph_one(const char *graph_file)
 {
 	void *graph_map;
-	const unsigned char *data, *chunk_lookup;
 	size_t graph_size;
 	struct stat st;
-	uint32_t i;
-	struct commit_graph *graph;
+	struct commit_graph *ret;
 	int fd = git_open(graph_file);
-	uint64_t last_chunk_offset;
-	uint32_t last_chunk_id;
-	uint32_t graph_signature;
-	unsigned char graph_version, hash_version;
 
 	if (fd < 0)
 		return NULL;
@@ -108,27 +102,55 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 		die(_("graph file %s is too small"), graph_file);
 	}
 	graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);
+	ret = parse_commit_graph(graph_map, fd, graph_size);
+
+	if (!ret) {
+		munmap(graph_map, graph_size);
+		close(fd);
+		exit(1);
+	}
+
+	return ret;
+}
+
+struct commit_graph *parse_commit_graph(void *graph_map, int fd,
+					size_t graph_size)
+{
+	const unsigned char *data, *chunk_lookup;
+	uint32_t i;
+	struct commit_graph *graph;
+	uint64_t last_chunk_offset;
+	uint32_t last_chunk_id;
+	uint32_t graph_signature;
+	unsigned char graph_version, hash_version;
+
+	if (!graph_map)
+		return NULL;
+
+	if (graph_size < GRAPH_MIN_SIZE)
+		return NULL;
+
 	data = (const unsigned char *)graph_map;
 
 	graph_signature = get_be32(data);
 	if (graph_signature != GRAPH_SIGNATURE) {
 		error(_("graph signature %X does not match signature %X"),
 		      graph_signature, GRAPH_SIGNATURE);
-		goto cleanup_fail;
+		return NULL;
 	}
 
 	graph_version = *(unsigned char*)(data + 4);
 	if (graph_version != GRAPH_VERSION) {
 		error(_("graph version %X does not match version %X"),
 		      graph_version, GRAPH_VERSION);
-		goto cleanup_fail;
+		return NULL;
 	}
 
 	hash_version = *(unsigned char*)(data + 5);
 	if (hash_version != GRAPH_OID_VERSION) {
 		error(_("hash version %X does not match version %X"),
 		      hash_version, GRAPH_OID_VERSION);
-		goto cleanup_fail;
+		return NULL;
 	}
 
 	graph = alloc_commit_graph();
@@ -152,7 +174,8 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 		if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
 			error(_("improper chunk offset %08x%08x"), (uint32_t)(chunk_offset >> 32),
 			      (uint32_t)chunk_offset);
-			goto cleanup_fail;
+			free(graph);
+			return NULL;
 		}
 
 		switch (chunk_id) {
@@ -187,7 +210,8 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 
 		if (chunk_repeated) {
 			error(_("chunk id %08x appears multiple times"), chunk_id);
-			goto cleanup_fail;
+			free(graph);
+			return NULL;
 		}
 
 		if (last_chunk_id == GRAPH_CHUNKID_OIDLOOKUP)
@@ -201,11 +225,6 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 	}
 
 	return graph;
-
-cleanup_fail:
-	munmap(graph_map, graph_size);
-	close(fd);
-	exit(1);
 }
 
 static void prepare_commit_graph_one(struct repository *r, const char *obj_dir)
diff --git a/commit-graph.h b/commit-graph.h
index 9db40b4d3a..813e7c19f1 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -54,6 +54,9 @@ struct commit_graph {
 
 struct commit_graph *load_commit_graph_one(const char *graph_file);
 
+struct commit_graph *parse_commit_graph(void *graph_map, int fd,
+					size_t graph_size);
+
 /*
  * Return 1 if and only if the repository has a commit-graph
  * file and generation numbers are computed in that file.
diff --git a/fuzz-commit-graph.c b/fuzz-commit-graph.c
new file mode 100644
index 0000000000..cf790c9d04
--- /dev/null
+++ b/fuzz-commit-graph.c
@@ -0,0 +1,16 @@
+#include "commit-graph.h"
+
+struct commit_graph *parse_commit_graph(void *graph_map, int fd,
+					size_t graph_size);
+
+int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size);
+
+int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)
+{
+	struct commit_graph *g;
+
+	g = parse_commit_graph((void *)data, -1, size);
+	free(g);
+
+	return 0;
+}
-- 
2.20.1.97.g81188d93c3-goog

[PATCH v5 2/3] commit-graph: fix buffer read-overflow

[Josh Steadmon]

fuzz-commit-graph identified a case where Git will read past the end of
a buffer containing a commit graph if the graph's header has an
incorrect chunk count. A simple bounds check in parse_commit_graph()
prevents this.

Signed-off-by: Josh Steadmon <steadmon@google.com>
---
 commit-graph.c          | 14 ++++++++++++--
 t/t5318-commit-graph.sh | 16 +++++++++++++---
 2 files changed, 25 insertions(+), 5 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index 07dd410f3c..836d65a1d3 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -165,10 +165,20 @@ struct commit_graph *parse_commit_graph(void *graph_map, int fd,
 	last_chunk_offset = 8;
 	chunk_lookup = data + 8;
 	for (i = 0; i < graph->num_chunks; i++) {
-		uint32_t chunk_id = get_be32(chunk_lookup + 0);
-		uint64_t chunk_offset = get_be64(chunk_lookup + 4);
+		uint32_t chunk_id;
+		uint64_t chunk_offset;
 		int chunk_repeated = 0;
 
+		if (data + graph_size - chunk_lookup <
+		    GRAPH_CHUNKLOOKUP_WIDTH) {
+			error(_("chunk lookup table entry missing; graph file may be incomplete"));
+			free(graph);
+			return NULL;
+		}
+
+		chunk_id = get_be32(chunk_lookup + 0);
+		chunk_offset = get_be64(chunk_lookup + 4);
+
 		chunk_lookup += GRAPH_CHUNKLOOKUP_WIDTH;
 
 		if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index 5fe21db99f..694f26079f 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -366,9 +366,10 @@ GRAPH_OCTOPUS_DATA_OFFSET=$(($GRAPH_COMMIT_DATA_OFFSET + \
 GRAPH_BYTE_OCTOPUS=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4))
 GRAPH_BYTE_FOOTER=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4 * $NUM_OCTOPUS_EDGES))
 
-# usage: corrupt_graph_and_verify <position> <data> <string>
+# usage: corrupt_graph_and_verify <position> <data> <string> [<zero_pos>]
 # Manipulates the commit-graph file at the position
-# by inserting the data, then runs 'git commit-graph verify'
+# by inserting the data, optionally zeroing the file
+# starting at <zero_pos>, then runs 'git commit-graph verify'
 # and places the output in the file 'err'. Test 'err' for
 # the given string.
 corrupt_graph_and_verify() {
@@ -376,11 +377,15 @@ corrupt_graph_and_verify() {
 	data="${2:-\0}"
 	grepstr=$3
 	cd "$TRASH_DIRECTORY/full" &&
+	orig_size=$(wc -c < $objdir/info/commit-graph) &&
+	zero_pos=${4:-${orig_size}} &&
 	test_when_finished mv commit-graph-backup $objdir/info/commit-graph &&
 	cp $objdir/info/commit-graph commit-graph-backup &&
 	printf "$data" | dd of="$objdir/info/commit-graph" bs=1 seek="$pos" conv=notrunc &&
+	dd of="$objdir/info/commit-graph" bs=1 seek="$zero_pos" count=0 &&
+	dd if=/dev/zero of="$objdir/info/commit-graph" bs=1 seek="$zero_pos" count=$(($orig_size - $zero_pos)) &&
 	test_must_fail git commit-graph verify 2>test_err &&
-	grep -v "^+" test_err >err
+	grep -v "^+" test_err >err &&
 	test_i18ngrep "$grepstr" err
 }
 
@@ -484,6 +489,11 @@ test_expect_success 'detect invalid checksum hash' '
 		"incorrect checksum"
 '
 
+test_expect_success 'detect incorrect chunk count' '
+	corrupt_graph_and_verify $GRAPH_BYTE_CHUNK_COUNT "\377" \
+		"chunk lookup table entry missing" $GRAPH_CHUNK_LOOKUP_OFFSET
+'
+
 test_expect_success 'git fsck (checks commit-graph)' '
 	cd "$TRASH_DIRECTORY/full" &&
 	git fsck &&
-- 
2.20.1.97.g81188d93c3-goog

[PATCH v5 3/3] Makefile: correct example fuzz build

[Josh Steadmon]

Signed-off-by: Josh Steadmon <steadmon@google.com>
---
 Makefile | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/Makefile b/Makefile
index 6b72f37c29..bbcfc2bc9f 100644
--- a/Makefile
+++ b/Makefile
@@ -3104,7 +3104,7 @@ cover_db_html: cover_db
 # An example command to build against libFuzzer from LLVM 4.0.0:
 #
 # make CC=clang CXX=clang++ \
-#      FUZZ_CXXFLAGS="-fsanitize-coverage=trace-pc-guard -fsanitize=address" \
+#      CFLAGS="-fsanitize-coverage=trace-pc-guard -fsanitize=address" \
 #      LIB_FUZZING_ENGINE=/usr/lib/llvm-4.0/lib/libFuzzer.a \
 #      fuzz-all
 #
-- 
2.20.1.97.g81188d93c3-goog

Re: [PATCH v5 1/3] commit-graph, fuzz: Add fuzzer for commit-graph

[Junio C Hamano]

Josh Steadmon <steadmon@google.com> writes:

> Breaks load_commit_graph_one() into a new function,

s/Breaks/Break/

> parse_commit_graph(). The latter function operates on arbitrary buffers,
> which makes it suitable as a fuzzing target. Since parse_commit_graph()
> is only called by load_commit_graph_one() (and the fuzzer described
> below), we omit error messages that would be duplicated by the caller.
>
> Adds fuzz-commit-graph.c, which provides a fuzzing entry point
> compatible with libFuzzer (and possibly other fuzzing engines).
>
> Signed-off-by: Josh Steadmon <steadmon@google.com>
> ---
>  .gitignore          |  1 +
>  Makefile            |  1 +
>  commit-graph.c      | 53 ++++++++++++++++++++++++++++++---------------
>  commit-graph.h      |  3 +++
>  fuzz-commit-graph.c | 16 ++++++++++++++
>  5 files changed, 57 insertions(+), 17 deletions(-)
>  create mode 100644 fuzz-commit-graph.c
>
> diff --git a/.gitignore b/.gitignore
> index 0d77ea5894..8bcf153ed9 100644
> --- a/.gitignore
> +++ b/.gitignore
> @@ -1,3 +1,4 @@
> +/fuzz-commit-graph
>  /fuzz_corpora
>  /fuzz-pack-headers
>  /fuzz-pack-idx
> diff --git a/Makefile b/Makefile
> index 1a44c811aa..6b72f37c29 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -684,6 +684,7 @@ SCRIPTS = $(SCRIPT_SH_INS) \
>  
>  ETAGS_TARGET = TAGS
>  
> +FUZZ_OBJS += fuzz-commit-graph.o
>  FUZZ_OBJS += fuzz-pack-headers.o
>  FUZZ_OBJS += fuzz-pack-idx.o
>  
> diff --git a/commit-graph.c b/commit-graph.c
> index 40c855f185..07dd410f3c 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -84,16 +84,10 @@ static int commit_graph_compatible(struct repository *r)
>  struct commit_graph *load_commit_graph_one(const char *graph_file)
>  {
>  	void *graph_map;
> -	const unsigned char *data, *chunk_lookup;
>  	size_t graph_size;
>  	struct stat st;
> -	uint32_t i;
> -	struct commit_graph *graph;
> +	struct commit_graph *ret;
>  	int fd = git_open(graph_file);
> -	uint64_t last_chunk_offset;
> -	uint32_t last_chunk_id;
> -	uint32_t graph_signature;
> -	unsigned char graph_version, hash_version;
>  
>  	if (fd < 0)
>  		return NULL;
> @@ -108,27 +102,55 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
>  		die(_("graph file %s is too small"), graph_file);
>  	}
>  	graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);
> +	ret = parse_commit_graph(graph_map, fd, graph_size);
> +
> +	if (!ret) {
> +		munmap(graph_map, graph_size);
> +		close(fd);
> +		exit(1);
> +	}
> +
> +	return ret;
> +}

Looks like a reasonable splitting of a helper function with a clean
interface.  I like it.

Thanks.


> +struct commit_graph *parse_commit_graph(void *graph_map, int fd,
> +					size_t graph_size)
> +{
> +	const unsigned char *data, *chunk_lookup;
> +	uint32_t i;
> +	struct commit_graph *graph;
> +	uint64_t last_chunk_offset;
> +	uint32_t last_chunk_id;
> +	uint32_t graph_signature;
> +	unsigned char graph_version, hash_version;
> +
> +	if (!graph_map)
> +		return NULL;
> +
> +	if (graph_size < GRAPH_MIN_SIZE)
> +		return NULL;
> +
>  	data = (const unsigned char *)graph_map;
>  
>  	graph_signature = get_be32(data);
>  	if (graph_signature != GRAPH_SIGNATURE) {
>  		error(_("graph signature %X does not match signature %X"),
>  		      graph_signature, GRAPH_SIGNATURE);
> -		goto cleanup_fail;
> +		return NULL;
>  	}
>  
>  	graph_version = *(unsigned char*)(data + 4);
>  	if (graph_version != GRAPH_VERSION) {
>  		error(_("graph version %X does not match version %X"),
>  		      graph_version, GRAPH_VERSION);
> -		goto cleanup_fail;
> +		return NULL;
>  	}
>  
>  	hash_version = *(unsigned char*)(data + 5);
>  	if (hash_version != GRAPH_OID_VERSION) {
>  		error(_("hash version %X does not match version %X"),
>  		      hash_version, GRAPH_OID_VERSION);
> -		goto cleanup_fail;
> +		return NULL;
>  	}
>  
>  	graph = alloc_commit_graph();
> @@ -152,7 +174,8 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
>  		if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
>  			error(_("improper chunk offset %08x%08x"), (uint32_t)(chunk_offset >> 32),
>  			      (uint32_t)chunk_offset);
> -			goto cleanup_fail;
> +			free(graph);
> +			return NULL;
>  		}
>  
>  		switch (chunk_id) {
> @@ -187,7 +210,8 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
>  
>  		if (chunk_repeated) {
>  			error(_("chunk id %08x appears multiple times"), chunk_id);
> -			goto cleanup_fail;
> +			free(graph);
> +			return NULL;
>  		}
>  
>  		if (last_chunk_id == GRAPH_CHUNKID_OIDLOOKUP)
> @@ -201,11 +225,6 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
>  	}
>  
>  	return graph;
> -
> -cleanup_fail:
> -	munmap(graph_map, graph_size);
> -	close(fd);
> -	exit(1);
>  }
>  
>  static void prepare_commit_graph_one(struct repository *r, const char *obj_dir)
> diff --git a/commit-graph.h b/commit-graph.h
> index 9db40b4d3a..813e7c19f1 100644
> --- a/commit-graph.h
> +++ b/commit-graph.h
> @@ -54,6 +54,9 @@ struct commit_graph {
>  
>  struct commit_graph *load_commit_graph_one(const char *graph_file);
>  
> +struct commit_graph *parse_commit_graph(void *graph_map, int fd,
> +					size_t graph_size);
> +
>  /*
>   * Return 1 if and only if the repository has a commit-graph
>   * file and generation numbers are computed in that file.
> diff --git a/fuzz-commit-graph.c b/fuzz-commit-graph.c
> new file mode 100644
> index 0000000000..cf790c9d04
> --- /dev/null
> +++ b/fuzz-commit-graph.c
> @@ -0,0 +1,16 @@
> +#include "commit-graph.h"
> +
> +struct commit_graph *parse_commit_graph(void *graph_map, int fd,
> +					size_t graph_size);
> +
> +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size);
> +
> +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)
> +{
> +	struct commit_graph *g;
> +
> +	g = parse_commit_graph((void *)data, -1, size);
> +	free(g);
> +
> +	return 0;
> +}

Re: [PATCH v5 3/3] Makefile: correct example fuzz build

[Junio C Hamano]

Josh Steadmon <steadmon@google.com> writes:

> Signed-off-by: Josh Steadmon <steadmon@google.com>
> ---
>  Makefile | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/Makefile b/Makefile
> index 6b72f37c29..bbcfc2bc9f 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -3104,7 +3104,7 @@ cover_db_html: cover_db
>  # An example command to build against libFuzzer from LLVM 4.0.0:
>  #
>  # make CC=clang CXX=clang++ \
> -#      FUZZ_CXXFLAGS="-fsanitize-coverage=trace-pc-guard -fsanitize=address" \
> +#      CFLAGS="-fsanitize-coverage=trace-pc-guard -fsanitize=address" \
>  #      LIB_FUZZING_ENGINE=/usr/lib/llvm-4.0/lib/libFuzzer.a \
>  #      fuzz-all
>  #

I know this appeared in v2 of the series, but I cannot quite read
the reasoning/justification behind this change.  After this hunk
there is

    FUZZ_CXXFLAGS ?= $(CFLAGS)

so if you do not give CFLAGS but give FUZZ_CXXFLAGS, like the
sample, shouldn't it have worked just fine?  IOW "correct" in the
title is a bit too terse as an explanation for this change.

Re: [PATCH v5 3/3] Makefile: correct example fuzz build

[Josh Steadmon]

On 2019.01.15 12:39, Junio C Hamano wrote:
> Josh Steadmon <steadmon@google.com> writes:
> 
> > Signed-off-by: Josh Steadmon <steadmon@google.com>
> > ---
> >  Makefile | 2 +-
> >  1 file changed, 1 insertion(+), 1 deletion(-)
> >
> > diff --git a/Makefile b/Makefile
> > index 6b72f37c29..bbcfc2bc9f 100644
> > --- a/Makefile
> > +++ b/Makefile
> > @@ -3104,7 +3104,7 @@ cover_db_html: cover_db
> >  # An example command to build against libFuzzer from LLVM 4.0.0:
> >  #
> >  # make CC=clang CXX=clang++ \
> > -#      FUZZ_CXXFLAGS="-fsanitize-coverage=trace-pc-guard -fsanitize=address" \
> > +#      CFLAGS="-fsanitize-coverage=trace-pc-guard -fsanitize=address" \
> >  #      LIB_FUZZING_ENGINE=/usr/lib/llvm-4.0/lib/libFuzzer.a \
> >  #      fuzz-all
> >  #
> 
> I know this appeared in v2 of the series, but I cannot quite read
> the reasoning/justification behind this change.  After this hunk
> there is
> 
>     FUZZ_CXXFLAGS ?= $(CFLAGS)
> 
> so if you do not give CFLAGS but give FUZZ_CXXFLAGS, like the
> sample, shouldn't it have worked just fine?  IOW "correct" in the
> title is a bit too terse as an explanation for this change.

Sorry for being too vague. The problem with only including FUZZ_CXXFLAGS
is that all the .c files need to be compiled with coverage tracking
enabled, not just the fuzzer itself.

The motivation for splitting CFLAGS and FUZZ_CXXFLAGS in the first place
was to enable OSS-Fuzz (and others) to include C++-specific flags
without causing a ton of compiler warnings when those are applied to the
.c files. So OSS-Fuzz sets both CFLAGS and FUZZ_CXXFLAGS when building.

We could fix the comment by setting both CFLAGS and FUZZ_CXXFLAGS, but
since we're not including any C++-specific flags there's no reason to
set both.

I'll fix the commit message in v6.

[PATCH v6 0/3] Add commit-graph fuzzer and fix buffer overflow

[Josh Steadmon]

Add a new fuzz test for the commit graph and fix a buffer read-overflow
that it discovered. Additionally, fix the Makefile instructions for
building fuzzers.

Changes since V5:
  * Conform to commit message standards for the 1st patch in the series.
  * Clarify commit message for the 3rd patch in the series.

Changes since V4:
  * Ensure that corrupt_graph_and_verify() in t5318 changes to the
    proper directory before accessing any files.

Changes since V3:
  * Improve portability of the new test functionality.
  * Fix broken &&-chains in tests.

Changes since V2:
  * Avoid pointer arithmetic overflow when checking the graph's chunk
    count.
  * Merge the corrupt_graph_and_verify and
    corrupt_and_zero_graph_then_verify test functions.

Josh Steadmon (3):
  commit-graph, fuzz: Add fuzzer for commit-graph
  commit-graph: fix buffer read-overflow
  Makefile: correct example fuzz build

 .gitignore              |  1 +
 Makefile                |  3 +-
 commit-graph.c          | 67 +++++++++++++++++++++++++++++------------
 commit-graph.h          |  3 ++
 fuzz-commit-graph.c     | 16 ++++++++++
 t/t5318-commit-graph.sh | 16 ++++++++--
 6 files changed, 83 insertions(+), 23 deletions(-)
 create mode 100644 fuzz-commit-graph.c

Range-diff against v5:
1:  0b57ecbe1b ! 1:  c4ec3fc3fc commit-graph, fuzz: Add fuzzer for commit-graph
    @@ -2,11 +2,11 @@
     
         commit-graph, fuzz: Add fuzzer for commit-graph
     
    -    Breaks load_commit_graph_one() into a new function,
    -    parse_commit_graph(). The latter function operates on arbitrary buffers,
    -    which makes it suitable as a fuzzing target. Since parse_commit_graph()
    -    is only called by load_commit_graph_one() (and the fuzzer described
    -    below), we omit error messages that would be duplicated by the caller.
    +    Break load_commit_graph_one() into a new function, parse_commit_graph().
    +    The latter function operates on arbitrary buffers, which makes it
    +    suitable as a fuzzing target. Since parse_commit_graph() is only called
    +    by load_commit_graph_one() (and the fuzzer described below), we omit
    +    error messages that would be duplicated by the caller.
     
         Adds fuzz-commit-graph.c, which provides a fuzzing entry point
         compatible with libFuzzer (and possibly other fuzzing engines).
2:  a3b5d33c4b = 2:  d7b137650f commit-graph: fix buffer read-overflow
3:  350ea5f7c9 ! 3:  c06e0667fa Makefile: correct example fuzz build
    @@ -2,6 +2,15 @@
     
         Makefile: correct example fuzz build
     
    +    The comment explaining how to build the fuzzers was broken in
    +    927c77e7d4d ("Makefile: use FUZZ_CXXFLAGS for linking fuzzers",
    +    2018-11-14).
    +
    +    When building fuzzers, all .c files must be compiled with coverage
    +    tracing enabled. This is not possible when using only FUZZ_CXXFLAGS, as
    +    that flag is only applied to the fuzzers themselves. Switching back to
    +    CFLAGS fixes the issue.
    +
     
      diff --git a/Makefile b/Makefile
-- 
2.20.1.97.g81188d93c3-goog

[PATCH v6 1/3] commit-graph, fuzz: Add fuzzer for commit-graph

[Josh Steadmon]

Break load_commit_graph_one() into a new function, parse_commit_graph().
The latter function operates on arbitrary buffers, which makes it
suitable as a fuzzing target. Since parse_commit_graph() is only called
by load_commit_graph_one() (and the fuzzer described below), we omit
error messages that would be duplicated by the caller.

Adds fuzz-commit-graph.c, which provides a fuzzing entry point
compatible with libFuzzer (and possibly other fuzzing engines).

Signed-off-by: Josh Steadmon <steadmon@google.com>
---
 .gitignore          |  1 +
 Makefile            |  1 +
 commit-graph.c      | 53 ++++++++++++++++++++++++++++++---------------
 commit-graph.h      |  3 +++
 fuzz-commit-graph.c | 16 ++++++++++++++
 5 files changed, 57 insertions(+), 17 deletions(-)
 create mode 100644 fuzz-commit-graph.c

diff --git a/.gitignore b/.gitignore
index 0d77ea5894..8bcf153ed9 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,4 @@
+/fuzz-commit-graph
 /fuzz_corpora
 /fuzz-pack-headers
 /fuzz-pack-idx
diff --git a/Makefile b/Makefile
index 1a44c811aa..6b72f37c29 100644
--- a/Makefile
+++ b/Makefile
@@ -684,6 +684,7 @@ SCRIPTS = $(SCRIPT_SH_INS) \
 
 ETAGS_TARGET = TAGS
 
+FUZZ_OBJS += fuzz-commit-graph.o
 FUZZ_OBJS += fuzz-pack-headers.o
 FUZZ_OBJS += fuzz-pack-idx.o
 
diff --git a/commit-graph.c b/commit-graph.c
index 40c855f185..07dd410f3c 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -84,16 +84,10 @@ static int commit_graph_compatible(struct repository *r)
 struct commit_graph *load_commit_graph_one(const char *graph_file)
 {
 	void *graph_map;
-	const unsigned char *data, *chunk_lookup;
 	size_t graph_size;
 	struct stat st;
-	uint32_t i;
-	struct commit_graph *graph;
+	struct commit_graph *ret;
 	int fd = git_open(graph_file);
-	uint64_t last_chunk_offset;
-	uint32_t last_chunk_id;
-	uint32_t graph_signature;
-	unsigned char graph_version, hash_version;
 
 	if (fd < 0)
 		return NULL;
@@ -108,27 +102,55 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 		die(_("graph file %s is too small"), graph_file);
 	}
 	graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);
+	ret = parse_commit_graph(graph_map, fd, graph_size);
+
+	if (!ret) {
+		munmap(graph_map, graph_size);
+		close(fd);
+		exit(1);
+	}
+
+	return ret;
+}
+
+struct commit_graph *parse_commit_graph(void *graph_map, int fd,
+					size_t graph_size)
+{
+	const unsigned char *data, *chunk_lookup;
+	uint32_t i;
+	struct commit_graph *graph;
+	uint64_t last_chunk_offset;
+	uint32_t last_chunk_id;
+	uint32_t graph_signature;
+	unsigned char graph_version, hash_version;
+
+	if (!graph_map)
+		return NULL;
+
+	if (graph_size < GRAPH_MIN_SIZE)
+		return NULL;
+
 	data = (const unsigned char *)graph_map;
 
 	graph_signature = get_be32(data);
 	if (graph_signature != GRAPH_SIGNATURE) {
 		error(_("graph signature %X does not match signature %X"),
 		      graph_signature, GRAPH_SIGNATURE);
-		goto cleanup_fail;
+		return NULL;
 	}
 
 	graph_version = *(unsigned char*)(data + 4);
 	if (graph_version != GRAPH_VERSION) {
 		error(_("graph version %X does not match version %X"),
 		      graph_version, GRAPH_VERSION);
-		goto cleanup_fail;
+		return NULL;
 	}
 
 	hash_version = *(unsigned char*)(data + 5);
 	if (hash_version != GRAPH_OID_VERSION) {
 		error(_("hash version %X does not match version %X"),
 		      hash_version, GRAPH_OID_VERSION);
-		goto cleanup_fail;
+		return NULL;
 	}
 
 	graph = alloc_commit_graph();
@@ -152,7 +174,8 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 		if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
 			error(_("improper chunk offset %08x%08x"), (uint32_t)(chunk_offset >> 32),
 			      (uint32_t)chunk_offset);
-			goto cleanup_fail;
+			free(graph);
+			return NULL;
 		}
 
 		switch (chunk_id) {
@@ -187,7 +210,8 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 
 		if (chunk_repeated) {
 			error(_("chunk id %08x appears multiple times"), chunk_id);
-			goto cleanup_fail;
+			free(graph);
+			return NULL;
 		}
 
 		if (last_chunk_id == GRAPH_CHUNKID_OIDLOOKUP)
@@ -201,11 +225,6 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 	}
 
 	return graph;
-
-cleanup_fail:
-	munmap(graph_map, graph_size);
-	close(fd);
-	exit(1);
 }
 
 static void prepare_commit_graph_one(struct repository *r, const char *obj_dir)
diff --git a/commit-graph.h b/commit-graph.h
index 9db40b4d3a..813e7c19f1 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -54,6 +54,9 @@ struct commit_graph {
 
 struct commit_graph *load_commit_graph_one(const char *graph_file);
 
+struct commit_graph *parse_commit_graph(void *graph_map, int fd,
+					size_t graph_size);
+
 /*
  * Return 1 if and only if the repository has a commit-graph
  * file and generation numbers are computed in that file.
diff --git a/fuzz-commit-graph.c b/fuzz-commit-graph.c
new file mode 100644
index 0000000000..cf790c9d04
--- /dev/null
+++ b/fuzz-commit-graph.c
@@ -0,0 +1,16 @@
+#include "commit-graph.h"
+
+struct commit_graph *parse_commit_graph(void *graph_map, int fd,
+					size_t graph_size);
+
+int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size);
+
+int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)
+{
+	struct commit_graph *g;
+
+	g = parse_commit_graph((void *)data, -1, size);
+	free(g);
+
+	return 0;
+}
-- 
2.20.1.97.g81188d93c3-goog

[PATCH v6 2/3] commit-graph: fix buffer read-overflow

[Josh Steadmon]

fuzz-commit-graph identified a case where Git will read past the end of
a buffer containing a commit graph if the graph's header has an
incorrect chunk count. A simple bounds check in parse_commit_graph()
prevents this.

Signed-off-by: Josh Steadmon <steadmon@google.com>
---
 commit-graph.c          | 14 ++++++++++++--
 t/t5318-commit-graph.sh | 16 +++++++++++++---
 2 files changed, 25 insertions(+), 5 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index 07dd410f3c..836d65a1d3 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -165,10 +165,20 @@ struct commit_graph *parse_commit_graph(void *graph_map, int fd,
 	last_chunk_offset = 8;
 	chunk_lookup = data + 8;
 	for (i = 0; i < graph->num_chunks; i++) {
-		uint32_t chunk_id = get_be32(chunk_lookup + 0);
-		uint64_t chunk_offset = get_be64(chunk_lookup + 4);
+		uint32_t chunk_id;
+		uint64_t chunk_offset;
 		int chunk_repeated = 0;
 
+		if (data + graph_size - chunk_lookup <
+		    GRAPH_CHUNKLOOKUP_WIDTH) {
+			error(_("chunk lookup table entry missing; graph file may be incomplete"));
+			free(graph);
+			return NULL;
+		}
+
+		chunk_id = get_be32(chunk_lookup + 0);
+		chunk_offset = get_be64(chunk_lookup + 4);
+
 		chunk_lookup += GRAPH_CHUNKLOOKUP_WIDTH;
 
 		if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index 5fe21db99f..694f26079f 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -366,9 +366,10 @@ GRAPH_OCTOPUS_DATA_OFFSET=$(($GRAPH_COMMIT_DATA_OFFSET + \
 GRAPH_BYTE_OCTOPUS=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4))
 GRAPH_BYTE_FOOTER=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4 * $NUM_OCTOPUS_EDGES))
 
-# usage: corrupt_graph_and_verify <position> <data> <string>
+# usage: corrupt_graph_and_verify <position> <data> <string> [<zero_pos>]
 # Manipulates the commit-graph file at the position
-# by inserting the data, then runs 'git commit-graph verify'
+# by inserting the data, optionally zeroing the file
+# starting at <zero_pos>, then runs 'git commit-graph verify'
 # and places the output in the file 'err'. Test 'err' for
 # the given string.
 corrupt_graph_and_verify() {
@@ -376,11 +377,15 @@ corrupt_graph_and_verify() {
 	data="${2:-\0}"
 	grepstr=$3
 	cd "$TRASH_DIRECTORY/full" &&
+	orig_size=$(wc -c < $objdir/info/commit-graph) &&
+	zero_pos=${4:-${orig_size}} &&
 	test_when_finished mv commit-graph-backup $objdir/info/commit-graph &&
 	cp $objdir/info/commit-graph commit-graph-backup &&
 	printf "$data" | dd of="$objdir/info/commit-graph" bs=1 seek="$pos" conv=notrunc &&
+	dd of="$objdir/info/commit-graph" bs=1 seek="$zero_pos" count=0 &&
+	dd if=/dev/zero of="$objdir/info/commit-graph" bs=1 seek="$zero_pos" count=$(($orig_size - $zero_pos)) &&
 	test_must_fail git commit-graph verify 2>test_err &&
-	grep -v "^+" test_err >err
+	grep -v "^+" test_err >err &&
 	test_i18ngrep "$grepstr" err
 }
 
@@ -484,6 +489,11 @@ test_expect_success 'detect invalid checksum hash' '
 		"incorrect checksum"
 '
 
+test_expect_success 'detect incorrect chunk count' '
+	corrupt_graph_and_verify $GRAPH_BYTE_CHUNK_COUNT "\377" \
+		"chunk lookup table entry missing" $GRAPH_CHUNK_LOOKUP_OFFSET
+'
+
 test_expect_success 'git fsck (checks commit-graph)' '
 	cd "$TRASH_DIRECTORY/full" &&
 	git fsck &&
-- 
2.20.1.97.g81188d93c3-goog

[PATCH v6 3/3] Makefile: correct example fuzz build

[Josh Steadmon]

The comment explaining how to build the fuzzers was broken in
927c77e7d4d ("Makefile: use FUZZ_CXXFLAGS for linking fuzzers",
2018-11-14).

When building fuzzers, all .c files must be compiled with coverage
tracing enabled. This is not possible when using only FUZZ_CXXFLAGS, as
that flag is only applied to the fuzzers themselves. Switching back to
CFLAGS fixes the issue.

Signed-off-by: Josh Steadmon <steadmon@google.com>
---
 Makefile | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/Makefile b/Makefile
index 6b72f37c29..bbcfc2bc9f 100644
--- a/Makefile
+++ b/Makefile
@@ -3104,7 +3104,7 @@ cover_db_html: cover_db
 # An example command to build against libFuzzer from LLVM 4.0.0:
 #
 # make CC=clang CXX=clang++ \
-#      FUZZ_CXXFLAGS="-fsanitize-coverage=trace-pc-guard -fsanitize=address" \
+#      CFLAGS="-fsanitize-coverage=trace-pc-guard -fsanitize=address" \
 #      LIB_FUZZING_ENGINE=/usr/lib/llvm-4.0/lib/libFuzzer.a \
 #      fuzz-all
 #
-- 
2.20.1.97.g81188d93c3-goog

Re: [PATCH v5 3/3] Makefile: correct example fuzz build

[Junio C Hamano]

Josh Steadmon <steadmon@google.com> writes:

> Sorry for being too vague. The problem with only including FUZZ_CXXFLAGS
> is that all the .c files need to be compiled with coverage tracking
> enabled, not just the fuzzer itself.

OK.

> We could fix the comment by setting both CFLAGS and FUZZ_CXXFLAGS, but
> since we're not including any C++-specific flags there's no reason to
> set both.

Yes.

Re: [PATCH v6 2/3] commit-graph: fix buffer read-overflow

[Ævar Arnfjörð Bjarmason]

On Tue, Jan 15 2019, Josh Steadmon wrote:

> fuzz-commit-graph identified a case where Git will read past the end of
> a buffer containing a commit graph if the graph's header has an
> incorrect chunk count. A simple bounds check in parse_commit_graph()
> prevents this.

This has a 2.21 regression where the test fails on NetBSD:
https://gitlab.com/git-vcs/git-ci/-/jobs/164224275

> Signed-off-by: Josh Steadmon <steadmon@google.com>
> ---
>  commit-graph.c          | 14 ++++++++++++--
>  t/t5318-commit-graph.sh | 16 +++++++++++++---
>  2 files changed, 25 insertions(+), 5 deletions(-)
>
> diff --git a/commit-graph.c b/commit-graph.c
> index 07dd410f3c..836d65a1d3 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -165,10 +165,20 @@ struct commit_graph *parse_commit_graph(void *graph_map, int fd,
>  	last_chunk_offset = 8;
>  	chunk_lookup = data + 8;
>  	for (i = 0; i < graph->num_chunks; i++) {
> -		uint32_t chunk_id = get_be32(chunk_lookup + 0);
> -		uint64_t chunk_offset = get_be64(chunk_lookup + 4);
> +		uint32_t chunk_id;
> +		uint64_t chunk_offset;
>  		int chunk_repeated = 0;
>
> +		if (data + graph_size - chunk_lookup <
> +		    GRAPH_CHUNKLOOKUP_WIDTH) {
> +			error(_("chunk lookup table entry missing; graph file may be incomplete"));
> +			free(graph);
> +			return NULL;
> +		}
> +
> +		chunk_id = get_be32(chunk_lookup + 0);
> +		chunk_offset = get_be64(chunk_lookup + 4);
> +
>  		chunk_lookup += GRAPH_CHUNKLOOKUP_WIDTH;
>
>  		if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
> diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
> index 5fe21db99f..694f26079f 100755
> --- a/t/t5318-commit-graph.sh
> +++ b/t/t5318-commit-graph.sh
> @@ -366,9 +366,10 @@ GRAPH_OCTOPUS_DATA_OFFSET=$(($GRAPH_COMMIT_DATA_OFFSET + \
>  GRAPH_BYTE_OCTOPUS=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4))
>  GRAPH_BYTE_FOOTER=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4 * $NUM_OCTOPUS_EDGES))
>
> -# usage: corrupt_graph_and_verify <position> <data> <string>
> +# usage: corrupt_graph_and_verify <position> <data> <string> [<zero_pos>]
>  # Manipulates the commit-graph file at the position
> -# by inserting the data, then runs 'git commit-graph verify'
> +# by inserting the data, optionally zeroing the file
> +# starting at <zero_pos>, then runs 'git commit-graph verify'
>  # and places the output in the file 'err'. Test 'err' for
>  # the given string.
>  corrupt_graph_and_verify() {
> @@ -376,11 +377,15 @@ corrupt_graph_and_verify() {
>  	data="${2:-\0}"
>  	grepstr=$3
>  	cd "$TRASH_DIRECTORY/full" &&
> +	orig_size=$(wc -c < $objdir/info/commit-graph) &&
> +	zero_pos=${4:-${orig_size}} &&
>  	test_when_finished mv commit-graph-backup $objdir/info/commit-graph &&
>  	cp $objdir/info/commit-graph commit-graph-backup &&
>  	printf "$data" | dd of="$objdir/info/commit-graph" bs=1 seek="$pos" conv=notrunc &&
> +	dd of="$objdir/info/commit-graph" bs=1 seek="$zero_pos" count=0 &&
> +	dd if=/dev/zero of="$objdir/info/commit-graph" bs=1 seek="$zero_pos" count=$(($orig_size - $zero_pos)) &&

In the limited time I had to dig it starts failing at test 46, when
count=0 is given. dd on NetBSD exits with 127 when given count=0 it
seems.

>  	test_must_fail git commit-graph verify 2>test_err &&
> -	grep -v "^+" test_err >err
> +	grep -v "^+" test_err >err &&
>  	test_i18ngrep "$grepstr" err
>  }
>
> @@ -484,6 +489,11 @@ test_expect_success 'detect invalid checksum hash' '
>  		"incorrect checksum"
>  '
>
> +test_expect_success 'detect incorrect chunk count' '
> +	corrupt_graph_and_verify $GRAPH_BYTE_CHUNK_COUNT "\377" \
> +		"chunk lookup table entry missing" $GRAPH_CHUNK_LOOKUP_OFFSET
> +'
> +

Hacking around the above (e.g. "dd ... || :") makes all the failing
tests pass except this new one, which I didn't dig into.

Re: [PATCH v6 2/3] commit-graph: fix buffer read-overflow

[SZEDER Gábor]

On Wed, Feb 20, 2019 at 03:55:58PM +0100, Ævar Arnfjörð Bjarmason wrote:
> > @@ -376,11 +377,15 @@ corrupt_graph_and_verify() {
> >  	data="${2:-\0}"
> >  	grepstr=$3
> >  	cd "$TRASH_DIRECTORY/full" &&
> > +	orig_size=$(wc -c < $objdir/info/commit-graph) &&
> > +	zero_pos=${4:-${orig_size}} &&
> >  	test_when_finished mv commit-graph-backup $objdir/info/commit-graph &&
> >  	cp $objdir/info/commit-graph commit-graph-backup &&
> >  	printf "$data" | dd of="$objdir/info/commit-graph" bs=1 seek="$pos" conv=notrunc &&
> > +	dd of="$objdir/info/commit-graph" bs=1 seek="$zero_pos" count=0 &&
> > +	dd if=/dev/zero of="$objdir/info/commit-graph" bs=1 seek="$zero_pos" count=$(($orig_size - $zero_pos)) &&
> 
> In the limited time I had to dig it starts failing at test 46, when
> count=0 is given. dd on NetBSD exits with 127 when given count=0 it
> seems.

So the first 'dd' is supposed to truncate the commit-graph file at
$zero_pos.  I don't think we need 'count=0' for that: in the absence
of the 'if=...' operand, 'dd' reads from standard input, which is
redirected from /dev/null in our test scripts, i.e. there is nothing
to read, and, consequently, there is nothing to write, either.

Though not strictly necessary, I would feel more comfortable if
'if=/dev/null' would be explicitly specified, and even more so with a
"# truncate at $zero_pos" comment above that command.

As to the second 'dd', I think we should not run it at all when count
would be zero, i.e. when $orig_size = $zero_pos, because in
combination with 'if=/dev/zero' it's asking for trouble.  According to
POSIX [1]:

  count=n
      Copy only n input blocks. If n is zero, it is unspecified
      whether no blocks or all blocks are copied.

Imagine a 'dd' that implements the second option: there are infinite
blocks in /dev/zero to copy!  OTOH, if an implementation chooses the
first option (e.g. the usual Linux 'dd' from coreutils), then both of
these 'dd' invocations will leave the commit-graph file as-is, so it
doesn't matter whether we run them or not.


[1] http://pubs.opengroup.org/onlinepubs/9699919799/utilities/dd.html