[PATCH/RFC db/text-delta 0/4] vcs-svn: avoid hangs for corrupt deltas

[PATCH/RFC db/text-delta 0/4] vcs-svn: avoid hangs for corrupt deltas

[Jonathan Nieder]

Hi,

As promised, here's a quick series to stop a too-greedy delta from
causing svn-fe deadlock.  It took longer than I thought it would,
mostly because I started too late.

If I remember correctly, this first showed up as a theoretical
possibility when chatting with Ram and later showed up in practice due
to a bug in a test script or something like that.  I don't remember
the details but luckily it is not hard to make up a delta exhibiting
the problem.  See the test script in patch 4 for details.

After review, I'd like to push this to the main svn-fe branch and ask
Junio to pull it so text delta support can be rolled out.  There's
just no reason not to, except for the obvious ones:

 - less pleasant raw UI for svn-fe
 - losing support for non-git fast-import backends that don't
   support cat-blob yet

Waiting for those would be to put the cart before the horse (how can
people experiment with making something better if they haven't
experienced what we have now?).  Review of the pending patches at

 git://repo.or.cz/git/jrn.git svn-fe-next

to find missed details or other things that would be nice to get
taken care of toward that end would be very welcome.

As for this series: hopefully it's simple but it's perfectly
possible I got something terribly wrong.  Thoughts welcome, as
always.

Thanks to David and Ram for some useful discussions on irc, including
those that led to these patches.

Jonathan Nieder (4):
  test-svn-fe: split off "test-svn-fe -d" into a separate function
  vcs-svn: cap number of bytes read from sliding view
  vcs-svn: guard against overflow when computing preimage length
  vcs-svn: avoid hangs from corrupt deltas

[PATCH 1/4] test-svn-fe: split off "test-svn-fe -d" into a separate function

[Jonathan Nieder]

The helper for testing the svndiff library is getting dangerously
close to the right margin.  Split it off into a separate function so
it is easier to contemplate on its own.

In other words, this just unindents the code a little.  No functional
change intended.

Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
---
 test-svn-fe.c |   54 ++++++++++++++++++++++++++++++++----------------------
 1 files changed, 32 insertions(+), 22 deletions(-)

diff --git a/test-svn-fe.c b/test-svn-fe.c
index 66bd040..a027626 100644
--- a/test-svn-fe.c
+++ b/test-svn-fe.c
@@ -8,10 +8,37 @@
 #include "vcs-svn/sliding_window.h"
 #include "vcs-svn/line_buffer.h"
 
+static const char test_svnfe_usage[] =
+	"test-svn-fe (<dumpfile> | [-d] <preimage> <delta> <len>)";
+
+static int apply_delta(int argc, char *argv[])
+{
+	struct line_buffer preimage = LINE_BUFFER_INIT;
+	struct line_buffer delta = LINE_BUFFER_INIT;
+	struct sliding_view preimage_view = SLIDING_VIEW_INIT(&preimage);
+
+	if (argc != 5)
+		usage(test_svnfe_usage);
+
+	if (buffer_init(&preimage, argv[2]))
+		die_errno("cannot open preimage");
+	if (buffer_init(&delta, argv[3]))
+		die_errno("cannot open delta");
+	if (svndiff0_apply(&delta, (off_t) strtoull(argv[4], NULL, 0),
+					&preimage_view, stdout))
+		return 1;
+	if (buffer_deinit(&preimage))
+		die_errno("cannot close preimage");
+	if (buffer_deinit(&delta))
+		die_errno("cannot close delta");
+	buffer_reset(&preimage);
+	strbuf_release(&preimage_view.buf);
+	buffer_reset(&delta);
+	return 0;
+}
+
 int main(int argc, char *argv[])
 {
-	static const char test_svnfe_usage[] =
-		"test-svn-fe (<dumpfile> | [-d] <preimage> <delta> <len>)";
 	if (argc == 2) {
 		if (svndump_init(argv[1]))
 			return 1;
@@ -20,25 +47,8 @@ int main(int argc, char *argv[])
 		svndump_reset();
 		return 0;
 	}
-	if (argc == 5 && !strcmp(argv[1], "-d")) {
-		struct line_buffer preimage = LINE_BUFFER_INIT;
-		struct line_buffer delta = LINE_BUFFER_INIT;
-		struct sliding_view preimage_view = SLIDING_VIEW_INIT(&preimage);
-		if (buffer_init(&preimage, argv[2]))
-			die_errno("cannot open preimage");
-		if (buffer_init(&delta, argv[3]))
-			die_errno("cannot open delta");
-		if (svndiff0_apply(&delta, (off_t) strtoull(argv[4], NULL, 0),
-					&preimage_view, stdout))
-			return 1;
-		if (buffer_deinit(&preimage))
-			die_errno("cannot close preimage");
-		if (buffer_deinit(&delta))
-			die_errno("cannot close delta");
-		buffer_reset(&preimage);
-		strbuf_release(&preimage_view.buf);
-		buffer_reset(&delta);
-		return 0;
-	}
+
+	if (argc >= 2 && !strcmp(argv[1], "-d"))
+		return apply_delta(argc, argv);
 	usage(test_svnfe_usage);
 }
-- 
1.7.5.1

[PATCH 2/4] vcs-svn: cap number of bytes read from sliding view

[Jonathan Nieder]

Introduce a "max_off" field in struct sliding_view, roughly speaking
representing a maximum number of bytes that can be read from "file".
More precisely, if it is set to a nonnegative integer, a call to
move_window() attempting to put the right endpoint beyond that offset
will return an error instead.  A value of -1 disables the check.

The idea is to use this when applying Subversion-format deltas to
prevent reads past the end of the preimage (which has known length).
Without such a check, corrupt deltas would cause svn-fe to block
indefinitely when data in the input pipe is exhausted.

Inspired-by: Ramkumar Ramachandra <artagnon@gmail.com>
Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
---
 test-svn-fe.c            |    2 +-
 vcs-svn/sliding_window.c |    2 ++
 vcs-svn/sliding_window.h |    3 ++-
 3 files changed, 5 insertions(+), 2 deletions(-)

diff --git a/test-svn-fe.c b/test-svn-fe.c
index a027626..332a5f7 100644
--- a/test-svn-fe.c
+++ b/test-svn-fe.c
@@ -15,7 +15,7 @@ static int apply_delta(int argc, char *argv[])
 {
 	struct line_buffer preimage = LINE_BUFFER_INIT;
 	struct line_buffer delta = LINE_BUFFER_INIT;
-	struct sliding_view preimage_view = SLIDING_VIEW_INIT(&preimage);
+	struct sliding_view preimage_view = SLIDING_VIEW_INIT(&preimage, -1);
 
 	if (argc != 5)
 		usage(test_svnfe_usage);
diff --git a/vcs-svn/sliding_window.c b/vcs-svn/sliding_window.c
index 1b8d987..1bac7a4 100644
--- a/vcs-svn/sliding_window.c
+++ b/vcs-svn/sliding_window.c
@@ -54,6 +54,8 @@ int move_window(struct sliding_view *view, off_t off, size_t width)
 		return -1;
 	if (off < view->off || off + width < view->off + view->width)
 		return error("invalid delta: window slides left");
+	if (view->max_off >= 0 && view->max_off < off + width)
+		return error("delta preimage ends early");
 
 	file_offset = view->off + view->buf.len;
 	if (off < file_offset) {
diff --git a/vcs-svn/sliding_window.h b/vcs-svn/sliding_window.h
index ed0bfdd..b43a825 100644
--- a/vcs-svn/sliding_window.h
+++ b/vcs-svn/sliding_window.h
@@ -7,10 +7,11 @@ struct sliding_view {
 	struct line_buffer *file;
 	off_t off;
 	size_t width;
+	off_t max_off;	/* -1 means unlimited */
 	struct strbuf buf;
 };
 
-#define SLIDING_VIEW_INIT(input)	{ (input), 0, 0, STRBUF_INIT }
+#define SLIDING_VIEW_INIT(input, len)	{ (input), 0, 0, (len), STRBUF_INIT }
 
 extern int move_window(struct sliding_view *view, off_t off, size_t width);
 
-- 
1.7.5.1

[PATCH 3/4] vcs-svn: guard against overflow when computing preimage length

[Jonathan Nieder]

Signed integer overflow produces undefined behavior in C and off_t is
a signed type.  For predictable behavior, add some checks to protect
in advance against overflow.

On 32-bit systems, ftell as called by buffer_tmpfile_prepare_to_read
is likely to fail with EOVERFLOW when reading the corresponding
postimage, and this patch does not change that.  So this is more of a
futureproofing measure than a complete fix.

Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
---
 vcs-svn/fast_export.c |   15 ++++++++++++++-
 1 files changed, 14 insertions(+), 1 deletions(-)

diff --git a/vcs-svn/fast_export.c b/vcs-svn/fast_export.c
index edc658d..96a75d5 100644
--- a/vcs-svn/fast_export.c
+++ b/vcs-svn/fast_export.c
@@ -166,6 +166,7 @@ static int ends_with(const char *s, size_t len, const char *suffix)
 static int parse_cat_response_line(const char *header, off_t *len)
 {
 	size_t headerlen = strlen(header);
+	uintmax_t n;
 	const char *type;
 	const char *end;
 
@@ -174,14 +175,25 @@ static int parse_cat_response_line(const char *header, off_t *len)
 	type = memmem(header, headerlen, " blob ", strlen(" blob "));
 	if (!type)
 		return error("cat-blob header has wrong object type: %s", header);
-	*len = strtoumax(type + strlen(" blob "), (char **) &end, 10);
+	n = strtoumax(type + strlen(" blob "), (char **) &end, 10);
 	if (end == type + strlen(" blob "))
 		return error("cat-blob header does not contain length: %s", header);
+	if (memchr(type + strlen(" blob "), '-', end - type - strlen(" blob ")))
+		return error("cat-blob header contains negative length: %s", header);
+	if (n == UINTMAX_MAX || n > maximum_signed_value_of_type(off_t))
+		return error("blob too large for current definition of off_t");
+	*len = n;
 	if (*end)
 		return error("cat-blob header contains garbage after length: %s", header);
 	return 0;
 }
 
+static void check_preimage_overflow(off_t a, off_t b)
+{
+	if (signed_add_overflows(a, b))
+		die("blob too large for current definition of off_t");
+}
+
 static long apply_delta(off_t len, struct line_buffer *input,
 			const char *old_data, uint32_t old_mode)
 {
@@ -204,6 +216,7 @@ static long apply_delta(off_t len, struct line_buffer *input,
 	}
 	if (old_mode == REPO_MODE_LNK) {
 		strbuf_addstr(&preimage.buf, "link ");
+		check_preimage_overflow(preimage_len, strlen("link "));
 		preimage_len += strlen("link ");
 	}
 	if (svndiff0_apply(input, len, &preimage, out))
-- 
1.7.5.1

[PATCH 4/4] vcs-svn: avoid hangs from corrupt deltas

[Jonathan Nieder]

A corrupt Subversion-format delta can request reads past the end of
the preimage.  Set sliding_view::max_off so such corruption is caught
when it appears rather than blocking in an impossible-to-fulfill
read() when input is coming from a socket or pipe.

Inspired-by: Ramkumar Ramachandra <artagnon@gmail.com>
Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
---
The title feature.  Thanks for reading.

 t/t9010-svn-fe.sh     |   40 +++++++++++++++++++++++++++++++++++++---
 vcs-svn/fast_export.c |   15 +++++++++------
 2 files changed, 46 insertions(+), 9 deletions(-)

diff --git a/t/t9010-svn-fe.sh b/t/t9010-svn-fe.sh
index f24f004..b7eed24 100755
--- a/t/t9010-svn-fe.sh
+++ b/t/t9010-svn-fe.sh
@@ -18,12 +18,13 @@ reinit_git () {
 
 try_dump () {
 	input=$1 &&
-	maybe_fail=${2:+test_$2} &&
+	maybe_fail_svnfe=${2:+test_$2} &&
+	maybe_fail_fi=${3:+test_$3} &&
 
 	{
-		$maybe_fail test-svn-fe "$input" >stream 3<backflow &
+		$maybe_fail_svnfe test-svn-fe "$input" >stream 3<backflow &
 	} &&
-	git fast-import --cat-blob-fd=3 <stream 3>backflow &&
+	$maybe_fail_fi git fast-import --cat-blob-fd=3 <stream 3>backflow &&
 	wait $!
 }
 
@@ -1047,6 +1048,39 @@ test_expect_success PIPE 'deltas need not consume the whole preimage' '
 	test_cmp expect.3 actual.3
 '
 
+test_expect_success PIPE 'no hang for delta trying to read past end of preimage' '
+	reinit_git &&
+	{
+		# COPY 1
+		printf "SVNQ%b%b" "Q\001\001\002Q" "\001Q" |
+		q_to_nul
+	} >greedy.delta &&
+	{
+		cat <<-\EOF &&
+		SVN-fs-dump-format-version: 3
+
+		Revision-number: 1
+		Prop-content-length: 10
+		Content-length: 10
+
+		PROPS-END
+
+		Node-path: bootstrap
+		Node-kind: file
+		Node-action: add
+		Text-delta: true
+		Prop-content-length: 10
+		EOF
+		echo Text-content-length: $(wc -c <greedy.delta) &&
+		echo Content-length: $((10 + $(wc -c <greedy.delta))) &&
+		echo &&
+		echo PROPS-END &&
+		cat greedy.delta &&
+		echo
+	} >greedydelta.dump &&
+	try_dump greedydelta.dump must_fail might_fail
+'
+
 test_expect_success 'set up svn repo' '
 	svnconf=$PWD/svnconf &&
 	mkdir -p "$svnconf" &&
diff --git a/vcs-svn/fast_export.c b/vcs-svn/fast_export.c
index 96a75d5..97f5fdf 100644
--- a/vcs-svn/fast_export.c
+++ b/vcs-svn/fast_export.c
@@ -198,8 +198,7 @@ static long apply_delta(off_t len, struct line_buffer *input,
 			const char *old_data, uint32_t old_mode)
 {
 	long ret;
-	off_t preimage_len = 0;
-	struct sliding_view preimage = SLIDING_VIEW_INIT(&report_buffer, -1);
+	struct sliding_view preimage = SLIDING_VIEW_INIT(&report_buffer, 0);
 	FILE *out;
 
 	if (init_postimage() || !(out = buffer_tmpfile_rewind(&postimage)))
@@ -211,19 +210,23 @@ static long apply_delta(off_t len, struct line_buffer *input,
 		printf("cat-blob %s\n", old_data);
 		fflush(stdout);
 		response = get_response_line();
-		if (parse_cat_response_line(response, &preimage_len))
+		if (parse_cat_response_line(response, &preimage.max_off))
 			die("invalid cat-blob response: %s", response);
+		check_preimage_overflow(preimage.max_off, 1);
 	}
 	if (old_mode == REPO_MODE_LNK) {
 		strbuf_addstr(&preimage.buf, "link ");
-		check_preimage_overflow(preimage_len, strlen("link "));
-		preimage_len += strlen("link ");
+		check_preimage_overflow(preimage.max_off, strlen("link "));
+		preimage.max_off += strlen("link ");
+		check_preimage_overflow(preimage.max_off, 1);
 	}
 	if (svndiff0_apply(input, len, &preimage, out))
 		die("cannot apply delta");
 	if (old_data) {
 		/* Read the remainder of preimage and trailing newline. */
-		if (move_window(&preimage, preimage_len, 1))
+		assert(!signed_add_overflows(preimage.max_off, 1));
+		preimage.max_off++;	/* room for newline */
+		if (move_window(&preimage, preimage.max_off - 1, 1))
 			die("cannot seek to end of input");
 		if (preimage.buf.buf[0] != '\n')
 			die("missing newline after cat-blob response");
-- 
1.7.5.1

Re: [PATCH 1/4] test-svn-fe: split off "test-svn-fe -d" into a separate function

[Drew Northup]

On Fri, 2011-05-27 at 06:09 -0500, Jonathan Nieder wrote:
> The helper for testing the svndiff library is getting dangerously
> close to the right margin.  Split it off into a separate function so
> it is easier to contemplate on its own.
> 
> In other words, this just unindents the code a little.  No functional
> change intended.

>  
> +static const char test_svnfe_usage[] =
> +	"test-svn-fe (<dumpfile> | [-d] <preimage> <delta> <len>)";

>  int main(int argc, char *argv[])
>  {
> -	static const char test_svnfe_usage[] =
> -		"test-svn-fe (<dumpfile> | [-d] <preimage> <delta> <len>)";

How is this germane to the original intent? Is there a gain by making it
global (to that file) that I'm missing?

-- 
-Drew Northup
________________________________________________
"As opposed to vegetable or mineral error?"
-John Pescatore, SANS NewsBites Vol. 12 Num. 59

Re: [PATCH 1/4] test-svn-fe: split off "test-svn-fe -d" into a separate function

[Jonathan Nieder]

Drew Northup wrote:
> On Fri, 2011-05-27 at 06:09 -0500, Jonathan Nieder wrote:

>> +static const char test_svnfe_usage[] =
>> +	"test-svn-fe (<dumpfile> | [-d] <preimage> <delta> <len>)";
[...]
> How is this germane to the original intent? Is there a gain by making it
> global (to that file) that I'm missing?

It allows this variable with information about the program in general
to be shared by the two functions.  Many examples of that style show
up with

	git grep -l -F -e 'main(' | xargs git grep -F -e 'usage[]' --
	git grep -F -e 'usage[]' -- builtin

I should have mentioned so in the commit message, though; maybe
something like this:

	The helper for testing the svndiff library is getting
	dangerously close to the right margin.  Split it off into a
	separate function so it is easier to contemplate on its own.

	In other words, this just unindents the code a little.  In the
	process, make the test_svnfe_usage[] string static so it can
	be shared by the two functions (and other future functions in
	this test program) without fuss.  No noticeable change
	intended.

Thanks for noticing,
Jonathan