Fix buffer underflow in xdl_build_script

PATCH In review Alex via GitGitGadget 3 participants 5 messages May 23, 2025 – May 24, 2025

lore

Share & tools

lore

Alex via GitGitGadget

author

2025-05-23 20:51 UTC #0 lore raw

PATCH 1/1 Fix buffer underflow in xdl_build_script

From: jinyaoguo <[email protected]>

The loop in xdl_build_script used i1 >= 0 || i2 >= 0, causing i1 (or i2) to reach 0 and then access rchg1[i1-1] (or rchg2[i2-1]), which underflows the buffer.
This commit adds explicit i1 > 0 and i2 > 0 checks around those array accesses to prevent invalid negative indexing.

Signed-off-by Alex Guo <[email protected]>

---
Fix buffer underflow in xdl_build_script

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1976%2Fmugitya03%2Fbuf-1-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1976/mugitya03/buf-1-v1
Pull-Request: https://github.com/git/git/pull/1976

 xdiff/xdiffi.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

xdiff/xdiffi.c +4 -3

index 5a96e36dfbe..2e983965328 100644
@@ -951,9 +951,10 @@ int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) {
 	 * Trivial. Collects "groups" of changes and creates an edit script.
 	 */
 	for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >= 0 || i2 >= 0; i1--, i2--)
-		if (rchg1[i1 - 1] || rchg2[i2 - 1]) {
-			for (l1 = i1; rchg1[i1 - 1]; i1--);
-			for (l2 = i2; rchg2[i2 - 1]; i2--);
+		if ((i1 > 0 && rchg1[i1 - 1]) ||
+			(i2 > 0 && rchg2[i2 - 1])) {
+			for (l1 = i1; i1 > 0 && rchg1[i1 - 1]; i1--);
+            for (l2 = i2; i2 > 0 && rchg2[i2 - 1]; i2--);
 
 			if (!(xch = xdl_add_change(cscr, i1, i2, l1 - i1, l2 - i2))) {
 				xdl_free_script(cscr);

base-commit: 8613c2bb6cd16ef530dc5dd74d3b818a1ccbf1c0

Signature · 1 line

gitgitgadget

René Scharfe

2025-05-24 05:57 UTC #1 lore raw

Am 23.05.25 um 22:51 schrieb Alex via GitGitGadget:

Quoted 7 lines

From: jinyaoguo <[email protected]>
The loop in xdl_build_script used i1 >= 0 || i2 >= 0, causing i1 (or i2) to reach 0 and then access rchg1[i1-1] (or rchg2[i2-1]), which underflows the buffer.
This commit adds explicit i1 > 0 and i2 > 0 checks around those array accesses to prevent invalid negative indexing.

xdl_prepare_ctx() in xdiff/xprepare.c allocates an extra entry at both ends for rchg arrays, so an index of -1 should be within the bounds.

i1 and i2 are decreased in lockstep, though, so one of them can become smaller than -1 if nrec is different between the files. And that's how this code run can indeed run off into the weeds.

Curiously, AddressSanitizer doesn't report anything, but if I add the following line after the outer for, I can trigger it to report a heap-buffer-overflow with e.g., git show 8613c2bb6c:

	if (i1 < 0 || i2 < 0) fprintf(stderr, "Oops: %ld %ld\n", i1, i2);

Quoted 17 lines

Signed-off-by Alex Guo <[email protected]>
---
Fix buffer underflow in xdl_build_script
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1976%2Fmugitya03%2Fbuf-1-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1976/mugitya03/buf-1-v1
Pull-Request: https://github.com/git/git/pull/1976
 xdiff/xdiffi.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)
xdiff/xdiffi.c +0 -0
index 5a96e36dfbe..2e983965328 100644

xdiff/xdiffi.c int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) { · line 953

Quoted 3 lines

xdiff/xdiffi.c +0 -0

@@ -951,9 +951,10 @@ int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) {
 	 * Trivial. Collects "groups" of changes and creates an edit script.
 	 */
 	for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >= 0 || i2 >= 0; i1--, i2--)

Should the || be a && instead? From a birds-eye view I would assume we can stop scanning for changes when we exhaust (reach the top) of either side. We just have to make sure everything from the other side is accounted for in the last added change.

xdiff/xdiffi.c int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) { · line 957

Quoted 7 lines

xdiff/xdiffi.c +4 -3

-		if (rchg1[i1 - 1] || rchg2[i2 - 1]) {
-			for (l1 = i1; rchg1[i1 - 1]; i1--);
-			for (l2 = i2; rchg2[i2 - 1]; i2--);
+		if ((i1 > 0 && rchg1[i1 - 1]) ||
+			(i2 > 0 && rchg2[i2 - 1])) {
+			for (l1 = i1; i1 > 0 && rchg1[i1 - 1]; i1--);
+            for (l2 = i2; i2 > 0 && rchg2[i2 - 1]; i2--);

Nit: The indentation of that line is off.

Quoted 5 lines

xdiff/xdiffi.c +0 -0
 			if (!(xch = xdl_add_change(cscr, i1, i2, l1 - i1, l2 - i2))) {
 				xdl_free_script(cscr);
 
base-commit: 8613c2bb6cd16ef530dc5dd74d3b818a1ccbf1c0

René Scharfe

2025-05-24 09:08 UTC #2 lore raw

Am 24.05.25 um 07:57 schrieb RenÃ© Scharfe:

Quoted 9 lines

Am 23.05.25 um 22:51 schrieb Alex via GitGitGadget:
Quoted 7 lines
From: jinyaoguo <[email protected]>
The loop in xdl_build_script used i1 >= 0 || i2 >= 0, causing i1 (or i2) to reach 0 and then access rchg1[i1-1] (or rchg2[i2-1]), which underflows the buffer.
This commit adds explicit i1 > 0 and i2 > 0 checks around those array accesses to prevent invalid negative indexing.

Quoted 6 lines

xdl_prepare_ctx() in xdiff/xprepare.c allocates an extra entry at both ends for rchg arrays, so an index of -1 should be within the bounds.
i1 and i2 are decreased in lockstep, though, so one of them can become smaller than -1 if nrec is different between the files. And that's how this code run can indeed run off into the weeds.

Actually no, i1 can't seem to reach 0 without i2 also being 0 and vice versa. Or can it? It makes sense that we reach the start of both buffers at the same time if we walk backwards from the end, don't misstep and have consistent rchg array contents, but I'm not sure.

Are you able to demonstrate any out-of-bounds access with e.g., Valgrind, AddressSanitizer or an assertion?

Quoted 5 lines

Curiously, AddressSanitizer doesn't report anything, but if I add the following line after the outer for, I can trigger it to report a heap-buffer-overflow with e.g., git show 8613c2bb6c:
	if (i1 < 0 || i2 < 0) fprintf(stderr, "Oops: %ld %ld\n", i1, i2);

That's because I forgot to add braces. D'oh! I can't trigger any out-of-bounds access or that Oops with them properly in place. So I let myself get fooled by a daring coding style. :-|

Quoted 13 lines

Quoted 13 lines
Signed-off-by Alex Guo <[email protected]>
---
Fix buffer underflow in xdl_build_script
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1976%2Fmugitya03%2Fbuf-1-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1976/mugitya03/buf-1-v1
Pull-Request: https://github.com/git/git/pull/1976
 xdiff/xdiffi.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

Quoted 6 lines

xdiff/xdiffi.c int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) { · line 951
Quoted 6 lines
xdiff/xdiffi.c +0 -0
index 5a96e36dfbe..2e983965328 100644
@@ -951,9 +951,10 @@ int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) {
 	 * Trivial. Collects "groups" of changes and creates an edit script.

Trivial for Davide perhaps (libxdiff author), but not my mushy brain..

Quoted 25 lines

xdiff/xdiffi.c int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) { · line 953
Quoted 2 lines
xdiff/xdiffi.c +0 -0
 	 */
 	for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >= 0 || i2 >= 0; i1--, i2--)
Should the || be a && instead? From a birds-eye view I would assume we can stop scanning for changes when we exhaust (reach the top) of either side. We just have to make sure everything from the other side is accounted for in the last added change.
xdiff/xdiffi.c int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) { · line 957
Quoted 7 lines
xdiff/xdiffi.c +4 -3
-		if (rchg1[i1 - 1] || rchg2[i2 - 1]) {
-			for (l1 = i1; rchg1[i1 - 1]; i1--);
-			for (l2 = i2; rchg2[i2 - 1]; i2--);
+		if ((i1 > 0 && rchg1[i1 - 1]) ||
+			(i2 > 0 && rchg2[i2 - 1])) {
+			for (l1 = i1; i1 > 0 && rchg1[i1 - 1]; i1--);
+            for (l2 = i2; i2 > 0 && rchg2[i2 - 1]; i2--);
Nit: The indentation of that line is off.
Quoted 5 lines
xdiff/xdiffi.c +0 -0
 			if (!(xch = xdl_add_change(cscr, i1, i2, l1 - i1, l2 - i2))) {
 				xdl_free_script(cscr);
 
base-commit: 8613c2bb6cd16ef530dc5dd74d3b818a1ccbf1c0

Phillip Wood

2025-05-24 13:38 UTC #3 lore raw

Quoted 12 lines · René Scharfe

Am 24.05.25 um 07:57 schrieb RenÃ© Scharfe:
Quoted 11 lines
Am 23.05.25 um 22:51 schrieb Alex via GitGitGadget:
Quoted 7 lines
From: jinyaoguo <[email protected]>
The loop in xdl_build_script used i1 >= 0 || i2 >= 0, causing i1 (or i2) to reach 0 and then access rchg1[i1-1] (or rchg2[i2-1]), which underflows the buffer.
This commit adds explicit i1 > 0 and i2 > 0 checks around those array accesses to prevent invalid negative indexing.
xdl_prepare_ctx() in xdiff/xprepare.c allocates an extra entry at both ends for rchg arrays, so an index of -1 should be within the bounds.

and rchg[-1] == 0 so i1 and i2 can never drop below -1

Quoted 8 lines

Quoted 3 lines
i1 and i2 are decreased in lockstep, though, so one of them can become smaller than -1 if nrec is different between the files. And that's how this code run can indeed run off into the weeds.
Actually no, i1 can't seem to reach 0 without i2 also being 0 and vice versa. Or can it? It makes sense that we reach the start of both buffers at the same time if we walk backwards from the end, don't misstep and have consistent rchg array contents, but I'm not sure.

The code looks like

	for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >= 0 || i2 >= 0; i1--, 
i2--)
		if (rchg1[i1 - 1] || rchg2[i2 - 1]) {
			for (l1 = i1; rchg1[i1 - 1]; i1--);
			for (l2 = i2; rchg2[i2 - 1]; i2--);

I think I've convinced myself that it is safe assuming there are an equal number of unchanged lines in rchg1 and rchg2 and rchg1[-1] == rchg2[-1] == 0. Each iteration consumes any changed lines in the preimage and the postimage plus a single context line from each (apart from the final iteration when the context lines may have been exhausted). At the start of the last iteration there are three possibilities

- i1 == -1 && i2 >= 0 => there are insertions as the start of the file. As the context lines in the preimage have been exhausted all the remaining rchg2 elements represent added lines and are consumed by for (l2 = i2; rchg2[i2 - 1]; i2--) so at the end of the loop body i2 == 0 and the outer loop will exit.

- i1 >= 0 && i2 == -1 => there are deletions at the start of the file. As the context lines in the postimage have been exhausted all the remaining rchg1 elements represent deleted lines and are consumed by for (l1 = i1; rchg1[i1 - 1]; i1--) so at the end of the loop body i1 == 0 and the outer loop will exit.

- i1 >= 0 && i2 >= 0 => the first line is unchanged or there are insertions and deletions at the beginning of the file. At the end of the loop body i1 == 0 && i2 == 0 and the outer loop will exit.

We could add

    if (i1 < -1 || i2 < -1)
        BUG("mismatched context line count");

before "if (rchg1[i1 - 1] || rchg2[i2 - 1])" inside the loop if we're worried about bugs that break the assumption that there are equal numbers of context lines on each side. Any such bug would generate invalid diffs. I don't know how likely that is to happen in practice.

Best Wishes

Phillip

Quoted 59 lines

Are you able to demonstrate any out-of-bounds access with e.g., Valgrind, AddressSanitizer or an assertion?
Quoted 5 lines
Curiously, AddressSanitizer doesn't report anything, but if I add the following line after the outer for, I can trigger it to report a heap-buffer-overflow with e.g., git show 8613c2bb6c:
	if (i1 < 0 || i2 < 0) fprintf(stderr, "Oops: %ld %ld\n", i1, i2);
That's because I forgot to add braces. D'oh! I can't trigger any out-of-bounds access or that Oops with them properly in place. So I let myself get fooled by a daring coding style. :-|
Quoted 13 lines
Quoted 13 lines
Signed-off-by Alex Guo <[email protected]>
---
Fix buffer underflow in xdl_build_script
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1976%2Fmugitya03%2Fbuf-1-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1976/mugitya03/buf-1-v1
Pull-Request: https://github.com/git/git/pull/1976
  xdiff/xdiffi.c | 7 ++++---
  1 file changed, 4 insertions(+), 3 deletions(-)
Quoted 6 lines
xdiff/xdiffi.c int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) { · line 951
Quoted 6 lines
xdiff/xdiffi.c +0 -0
index 5a96e36dfbe..2e983965328 100644
@@ -951,9 +951,10 @@ int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) {
  	 * Trivial. Collects "groups" of changes and creates an edit script.
Trivial for Davide perhaps (libxdiff author), but not my mushy brain..
Quoted 23 lines
xdiff/xdiffi.c int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) { · line 953
Quoted 2 lines
xdiff/xdiffi.c +0 -0
  	 */
  	for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >= 0 || i2 >= 0; i1--, i2--)
Should the || be a && instead? From a birds-eye view I would assume we can stop scanning for changes when we exhaust (reach the top) of either side. We just have to make sure everything from the other side is accounted for in the last added change.
xdiff/xdiffi.c int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) { · line 957
Quoted 7 lines
xdiff/xdiffi.c +4 -3
-		if (rchg1[i1 - 1] || rchg2[i2 - 1]) {
-			for (l1 = i1; rchg1[i1 - 1]; i1--);
-			for (l2 = i2; rchg2[i2 - 1]; i2--);
+		if ((i1 > 0 && rchg1[i1 - 1]) ||
+			(i2 > 0 && rchg2[i2 - 1])) {
+			for (l1 = i1; i1 > 0 && rchg1[i1 - 1]; i1--);
+            for (l2 = i2; i2 > 0 && rchg2[i2 - 1]; i2--);
Nit: The indentation of that line is off.
Quoted 5 lines
xdiff/xdiffi.c +0 -0
  			if (!(xch = xdl_add_change(cscr, i1, i2, l1 - i1, l2 - i2))) {
  				xdl_free_script(cscr);
 
base-commit: 8613c2bb6cd16ef530dc5dd74d3b818a1ccbf1c0

Phillip Wood

2025-05-24 13:53 UTC #4 lore raw

Quoted 32 lines · Phillip Wood

Quoted 12 lines · René Scharfe
Am 24.05.25 um 07:57 schrieb RenÃ© Scharfe:
Quoted 11 lines
Am 23.05.25 um 22:51 schrieb Alex via GitGitGadget:
Quoted 7 lines
From: jinyaoguo <[email protected]>
The loop in xdl_build_script used i1 >= 0 || i2 >= 0, causing i1 (or i2) to reach 0 and then access rchg1[i1-1] (or rchg2[i2-1]), which underflows the buffer.
This commit adds explicit i1 > 0 and i2 > 0 checks around those array accesses to prevent invalid negative indexing.
xdl_prepare_ctx() in xdiff/xprepare.c allocates an extra entry at both ends for rchg arrays, so an index of -1 should be within the bounds.
and rchg[-1] == 0 so i1 and i2 can never drop below -1
Quoted 8 lines
Quoted 3 lines
i1 and i2 are decreased in lockstep, though, so one of them can become smaller than -1 if nrec is different between the files. And that's how this code run can indeed run off into the weeds.
Actually no, i1 can't seem to reach 0 without i2 also being 0 and vice versa. Or can it? It makes sense that we reach the start of both buffers at the same time if we walk backwards from the end, don't misstep and have consistent rchg array contents, but I'm not sure.
The code looks like
    for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >= 0 || i2 >= 0;
i1--, i2--)
        if (rchg1[i1 - 1] || rchg2[i2 - 1]) {
            for (l1 = i1; rchg1[i1 - 1]; i1--);
            for (l2 = i2; rchg2[i2 - 1]; i2--);

Quoted 3 lines

I think I've convinced myself that it is safe assuming there are an equal number of unchanged lines in rchg1 and rchg2 and rchg1[-1] == rchg2[-1] == 0. Each iteration consumes any changed lines in the preimage and the postimage plus a single context line from each (apart from the final iteration when the context lines may have been exhausted). At the start of the last iteration there are three possibilities
- i1 == -1 && i2 >= 0 => there are insertions as the start of the file.

Sorry that should be i1 == 0 && i2 >= 0

Quoted 6 lines

As the context lines in the preimage have been exhausted all the remaining rchg2 elements represent added lines and are consumed by for (l2 = i2; rchg2[i2 - 1]; i2--) so at the end of the loop body i2 == 0 and the outer loop will exit.
- i1 >= 0 && i2 == -1 => there are deletions at the start of the file.

This one should be i1 >= 0 && i2 == 0

Quoted 80 lines

   As the context lines in the postimage have been exhausted all the remaining rchg1 elements represent deleted lines and are consumed by for (l1 = i1; rchg1[i1 - 1]; i1--) so at the end of the loop body i1 == 0 and the outer loop will exit.
- i1 >= 0 && i2 >= 0 => the first line is unchanged or there are insertions and deletions at the beginning of the file. At the end of the loop body i1 == 0 && i2 == 0 and the outer loop will exit.
We could add
    if (i1 < -1 || i2 < -1)
        BUG("mismatched context line count");
before "if (rchg1[i1 - 1] || rchg2[i2 - 1])" inside the loop if we're worried about bugs that break the assumption that there are equal numbers of context lines on each side. Any such bug would generate invalid diffs. I don't know how likely that is to happen in practice.
Best Wishes
Phillip
Quoted 59 lines
Are you able to demonstrate any out-of-bounds access with e.g., Valgrind, AddressSanitizer or an assertion?
Quoted 5 lines
Curiously, AddressSanitizer doesn't report anything, but if I add the following line after the outer for, I can trigger it to report a heap-buffer-overflow with e.g., git show 8613c2bb6c:
if (i1 < 0 || i2 < 0) fprintf(stderr, "Oops: %ld %ld\n", i1, i2);
That's because I forgot to add braces. D'oh! I can't trigger any out-of-bounds access or that Oops with them properly in place. So I let myself get fooled by a daring coding style. :-|
Quoted 13 lines
Quoted 13 lines
Signed-off-by Alex Guo <[email protected]>
---
Fix buffer underflow in xdl_build_script
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr- git-1976%2Fmugitya03%2Fbuf-1-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr- git-1976/mugitya03/buf-1-v1
Pull-Request: https://github.com/git/git/pull/1976
xdiff/xdiffi.c | 7 ++++---
  1 file changed, 4 insertions(+), 3 deletions(-)
Quoted 7 lines
xdiff/xdiffi.c int xdl_build_script(xdfenv_t *xe, xdchange_t · line 952
Quoted 7 lines
xdiff/xdiffi.c +0 -0
index 5a96e36dfbe..2e983965328 100644
@@ -951,9 +951,10 @@ int xdl_build_script(xdfenv_t *xe, xdchange_t 
 **xscr) {
        * Trivial. Collects "groups" of changes and creates an edit script.
Trivial for Davide perhaps (libxdiff author), but not my mushy brain..
Quoted 22 lines
xdiff/xdiffi.c int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) { · line 953
Quoted 2 lines
xdiff/xdiffi.c +0 -0
        */
       for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >= 0 || i2 >= 0; i1--, i2--)
Should the || be a && instead? From a birds-eye view I would assume we can stop scanning for changes when we exhaust (reach the top) of either side. We just have to make sure everything from the other side is accounted for in the last added change.
xdiff/xdiffi.c int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) { · line 957
Quoted 7 lines
xdiff/xdiffi.c +4 -3
-        if (rchg1[i1 - 1] || rchg2[i2 - 1]) {
-            for (l1 = i1; rchg1[i1 - 1]; i1--);
-            for (l2 = i2; rchg2[i2 - 1]; i2--);
+        if ((i1 > 0 && rchg1[i1 - 1]) ||
+            (i2 > 0 && rchg2[i2 - 1])) {
+            for (l1 = i1; i1 > 0 && rchg1[i1 - 1]; i1--);
+            for (l2 = i2; i2 > 0 && rchg2[i2 - 1]; i2--);
Nit: The indentation of that line is off.
Quoted 4 lines
xdiff/xdiffi.c +0 -0
               if (!(xch = xdl_add_change(cscr, i1, i2, l1 - i1, l2 - i2))) {
                   xdl_free_script(cscr);
base-commit: 8613c2bb6cd16ef530dc5dd74d3b818a1ccbf1c0