Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1239676 > unrolled thread

Re: [PATCH] string: Improve the generic strlcpy() implementation

Back to article view | Back to linux.kernel

Contents

  Re: [PATCH] string: Improve the generic strlcpy() implementation Alexey Dobriyan <adobriyan@gmail.com> - 2015-10-05 17:40 +0200
    Re: [PATCH] string: Improve the generic strlcpy() implementation Ingo Molnar <mingo@kernel.org> - 2015-10-05 18:20 +0200
      Re: [PATCH] string: Improve the generic strlcpy() implementation Ingo Molnar <mingo@kernel.org> - 2015-10-05 18:20 +0200
    Re: [PATCH] string: Improve the generic strlcpy() implementation Ingo Molnar <mingo@kernel.org> - 2015-10-05 18:30 +0200
      [PATCH] string: Fix strscpy() uninitialized data copy bug Ingo Molnar <mingo@kernel.org> - 2015-10-05 18:40 +0200
        Re: [PATCH] string: Fix strscpy() uninitialized data copy bug Chris Metcalf <cmetcalf@ezchip.com> - 2015-10-05 21:00 +0200
          Re: [PATCH] string: Fix strscpy() uninitialized data copy bug Ingo Molnar <mingo@kernel.org> - 2015-10-06 09:30 +0200
    Re: [PATCH] string: Improve the generic strlcpy() implementation Ingo Molnar <mingo@kernel.org> - 2015-10-05 18:30 +0200
      Re: [PATCH] string: Improve the generic strlcpy() implementation Linus Torvalds <torvalds@linux-foundation.org> - 2015-10-05 22:50 +0200
        Re: [PATCH] strscpy: zero any trailing garbage bytes in the  destination Ingo Molnar <mingo@kernel.org> - 2015-10-07 09:30 +0200

#1239676 — Re: [PATCH] string: Improve the generic strlcpy() implementation

I want to say two things:

1) strlcpy race

>  * In addition, the implementation is robust to the string changing out
>  * from underneath it, unlike the current strlcpy() implementation.

Canonical OpenBSD version does byte-by-byte copying,
this race is purely Linux invention.

2) strscpy() will copy garbage past NUL from source into destination.
It won't fault but still, who knows what lies after string.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [next] | [standalone]

#1239717

* Alexey Dobriyan <adobriyan@gmail.com> wrote:

> I want to say two things:
> 
> 1) strlcpy race
> 
> >  * In addition, the implementation is robust to the string changing out
> >  * from underneath it, unlike the current strlcpy() implementation.
> 
> Canonical OpenBSD version does byte-by-byte copying,
> this race is purely Linux invention.
> 
> 2) strscpy() will copy garbage past NUL from source into destination.
> It won't fault but still, who knows what lies after string.

So I think your argument is nonsense on several levels:

1)

In 99% of the cases the source string access is not racy so the point is moot.

2)

In the remaining 1% of cases, where the source string might indeed be modified in 
a racy fashion, the only result is that we might get some harmless copy of the end 
of the string _that we would have copied had we been a bit faster_.

I.e. it's violently not 'garbage' - it's portion of a valid string that was valid 
literally a few cycles ago. It's not uninitialized data and it's not data of 
something we should never have gotten access to.

3)

The strscpy() based Linux variant suggested by Linus (for which I sent the patch) 
does not have that small (and harmless) race and is much faster than the OpenBSD 
implementation.

Thanks,

	Ingo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1239718

* Ingo Molnar <mingo@kernel.org> wrote:

> 
> * Alexey Dobriyan <adobriyan@gmail.com> wrote:
> 
> > I want to say two things:
> > 
> > 1) strlcpy race
> > 
> > >  * In addition, the implementation is robust to the string changing out
> > >  * from underneath it, unlike the current strlcpy() implementation.
> > 
> > Canonical OpenBSD version does byte-by-byte copying,
> > this race is purely Linux invention.
> > 
> > 2) strscpy() will copy garbage past NUL from source into destination.
> > It won't fault but still, who knows what lies after string.
> 
> So I think your argument is nonsense on several levels:

Oh, you are right strscpy() - I mis-read your mail.

So the argument that is nonsensical here is mine!

Thanks,

	Ingo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1239723

* Ingo Molnar <mingo@kernel.org> wrote:

> We could do something like:
> 
>                 c = *(unsigned long *)(src+res);
>                 *(unsigned long *)(dest+res) = c;
> 
>                 if (has_zero(c, &data, &constants)) {
> 			unsigned int zero_pos;
> 
>                         data = prep_zero_mask(c, data, &constants);
>                         data = create_zero_mask(data);
> 
> 			zero_pos = find_zero(data);
> 			res += zero_pos;
> 
> 			memset(dest+res, 0, sizeof(long)-zero_pos);
> 
>                         return res;
>                 }
> 
> I.e. the extra memset() clears out the partial word (if any) after the NUL.

A slightly more paranoid version would be:

		c = *(unsigned long *)(src+res);
 
		if (has_zero(c, &data, &constants)) {
 			unsigned int zero_pos;
 
			data = prep_zero_mask(c, data, &constants);
			data = create_zero_mask(data);
 
 			zero_pos = find_zero(data);

			/* Clear out undefined data within the final word after the NUL: */ 
 			memset((void *)&c + zero_pos, 0, sizeof(long)-zero_pos);

			*(unsigned long *)(dest+res) = c;
 
			return res+zero_pos;
		}
		*(unsigned long *)(dest+res) = c;

This would solve any theoretical races in the _target_ buffer: if the target 
buffer may be copied to user-space in a racy fashion and we don't ever want it to 
have undefined data, then this variant does the tail-zeroing of the final word in 
the temporary copy, not in the target buffer.

Still untested.

Thanks,

	Ingo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1239737 — [PATCH] string: Fix strscpy() uninitialized data copy bug

* Ingo Molnar <mingo@kernel.org> wrote:

> A slightly more paranoid version would be:
> 
> 		c = *(unsigned long *)(src+res);
>  
> 		if (has_zero(c, &data, &constants)) {
>  			unsigned int zero_pos;
>  
> 			data = prep_zero_mask(c, data, &constants); data = 
> 			create_zero_mask(data);
>  
>  			zero_pos = find_zero(data);
> 
> 			/* Clear out undefined data within the final word after 
> 			the NUL: */
>  			memset((void *)&c + zero_pos, 0, sizeof(long)-zero_pos);
> 
> 			*(unsigned long *)(dest+res) = c;
>  
> 			return res+zero_pos;
> 		}
> 		*(unsigned long *)(dest+res) = c;
> 
> This would solve any theoretical races in the _target_ buffer: if the target 
> buffer may be copied to user-space in a racy fashion and we don't ever want it 
> to have undefined data, then this variant does the tail-zeroing of the final 
> word in the temporary copy, not in the target buffer.
> 
> Still untested.

So the patch below got tested a bit more seriously, with the strscpy() based 
strlcpy() patch I sent earlier: at least a typical Fedora bootup with a few 
thousand strlcpy() uses does not crash in any obvious way.

Still needs review to make sure I have not missed anything ...

Thanks,

	Ingo

===================>
From 946bab4d7138e5db53c5f1759e97809ebdf89551 Mon Sep 17 00:00:00 2001
From: Ingo Molnar <mingo@kernel.org>
Date: Mon, 5 Oct 2015 18:30:37 +0200
Subject: [PATCH] string: Fix strscpy() uninitialized data copy bug

Alexey Dobriyan noticed that our new strscpy() implementation will copy 
potentially out of range or uninitialized data from post the end of the
source string.

Fix this by zeroing out the tail of the final word of the copy.

Reported-by: Alexey Dobriyan <adobriyan@gmail.com>
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 lib/string.c | 14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)

diff --git a/lib/string.c b/lib/string.c
index 6b89c035df74..548f52b7a145 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -177,12 +177,24 @@ ssize_t strscpy(char *dest, const char *src, size_t count)
 		unsigned long c, data;
 
 		c = *(unsigned long *)(src+res);
-		*(unsigned long *)(dest+res) = c;
+
 		if (has_zero(c, &data, &constants)) {
+			unsigned int zero_pos;
+
 			data = prep_zero_mask(c, data, &constants);
 			data = create_zero_mask(data);
+
+			zero_pos = find_zero(data);
+
+			/* Clear out undefined data within the final word after the NUL (if any): */
+			memset((void *)&c + zero_pos, 0, sizeof(long)-zero_pos);
+
+			*(unsigned long *)(dest+res) = c;
+
 			return res + find_zero(data);
 		}
+		*(unsigned long *)(dest+res) = c;
+
 		res += sizeof(unsigned long);
 		count -= sizeof(unsigned long);
 		max -= sizeof(unsigned long);
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1239844 — Re: [PATCH] string: Fix strscpy() uninitialized data copy bug

On 10/05/2015 12:36 PM, Ingo Molnar wrote:
> So the patch below got tested a bit more seriously, with the strscpy() based
> strlcpy() patch I sent earlier: at least a typical Fedora bootup with a few
> thousand strlcpy() uses does not crash in any obvious way.
>
> Still needs review to make sure I have not missed anything ...
>
> Thanks,
>
> 	Ingo
>
> ===================>
>  From 946bab4d7138e5db53c5f1759e97809ebdf89551 Mon Sep 17 00:00:00 2001
> From: Ingo Molnar<mingo@kernel.org>
> Date: Mon, 5 Oct 2015 18:30:37 +0200
> Subject: [PATCH] string: Fix strscpy() uninitialized data copy bug
>
> Alexey Dobriyan noticed that our new strscpy() implementation will copy
> potentially out of range or uninitialized data from post the end of the
> source string.
>
> Fix this by zeroing out the tail of the final word of the copy.
>
> Reported-by: Alexey Dobriyan<adobriyan@gmail.com>
> Signed-off-by: Ingo Molnar<mingo@kernel.org>
> ---
>   lib/string.c | 14 +++++++++++++-
>   1 file changed, 13 insertions(+), 1 deletion(-)
>
> diff --git a/lib/string.c b/lib/string.c
> index 6b89c035df74..548f52b7a145 100644
> --- a/lib/string.c
> +++ b/lib/string.c
> @@ -177,12 +177,24 @@ ssize_t strscpy(char *dest, const char *src, size_t count)
>   		unsigned long c, data;
>   
>   		c = *(unsigned long *)(src+res);
> -		*(unsigned long *)(dest+res) = c;
> +
>   		if (has_zero(c, &data, &constants)) {
> +			unsigned int zero_pos;
> +
>   			data = prep_zero_mask(c, data, &constants);
>   			data = create_zero_mask(data);
> +
> +			zero_pos = find_zero(data);
> +
> +			/* Clear out undefined data within the final word after the NUL (if any): */
> +			memset((void *)&c + zero_pos, 0, sizeof(long)-zero_pos);

Unfortunately using memset() like that will break on big-endian
machines.  I always have to go back and play around with the
word-at-a-time.h definitions to get this right, but I think it's possible
that the "data" itself has the mask to clear the unwanted bytes,
i.e. you could do something like the following (untested).

I'm still not totally convinced it's necessary, as programmers
should generally assume anything beyond the end of a copied
string is garbage anyway, and since we're not copying it to
userspace we're not exposing any possibly secure data.

Races shouldn't be a concern either since, after all, there is
already a window where we may have overwritten the NUL
end of an earlier shorter string, and now a racy copy from the
partially-written dest buf could walk right off the end of the
buffer itself, so you'd already better not be doing that.

But, all that said, I'm not opposed to a simple fix to avoid
carrying along the uninitialized bytes from beyond the end
of the source string, since it does seem a bit cleaner, even
if I can't put my finger in a reason why it would actually matter.

diff --git a/lib/string.c b/lib/string.c
index 8dbb7b1eab50..ba64f4e0382d 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -203,12 +203,13 @@ ssize_t strscpy(char *dest, const char *src, size_t count)
  		unsigned long c, data;
  
  		c = *(unsigned long *)(src+res);
-		*(unsigned long *)(dest+res) = c;
  		if (has_zero(c, &data, &constants)) {
  			data = prep_zero_mask(c, data, &constants);
  			data = create_zero_mask(data);
+			*(unsigned long *)(dest+res) = c & data;
  			return res + find_zero(data);
  		}
+		*(unsigned long *)(dest+res) = c;
  		res += sizeof(unsigned long);
  		count -= sizeof(unsigned long);
  		max -= sizeof(unsigned long);

-- 
Chris Metcalf, EZChip Semiconductor
http://www.ezchip.com

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1240199 — Re: [PATCH] string: Fix strscpy() uninitialized data copy bug

* Chris Metcalf <cmetcalf@ezchip.com> wrote:

> Unfortunately using memset() like that will break on big-endian machines.

doh ... and I somehow convinced myself that it was endian safe ;-)

> [...]  I always have to go back and play around with the word-at-a-time.h 
> definitions to get this right, but I think it's possible that the "data" itself 
> has the mask to clear the unwanted bytes, i.e. you could do something like the 
> following (untested).
> 
> I'm still not totally convinced it's necessary, as programmers should generally 
> assume anything beyond the end of a copied string is garbage anyway, and since 
> we're not copying it to userspace we're not exposing any possibly secure data.
> 
> Races shouldn't be a concern either since, after all, there is already a window 
> where we may have overwritten the NUL end of an earlier shorter string, and now 
> a racy copy from the partially-written dest buf could walk right off the end of 
> the buffer itself, so you'd already better not be doing that.
> 
> But, all that said, I'm not opposed to a simple fix to avoid carrying along the 
> uninitialized bytes from beyond the end of the source string, since it does seem 
> a bit cleaner, even if I can't put my finger in a reason why it would actually 
> matter.

So it would matter for more advanced sharing ABIs: for example if there's an 
mlock()-ed area registered on the kernel side as well as kernel accessible memory, 
and if we do an strscpy() to such a target area, we don't want to leak 
uninitialized data to user-space.

(This is not theoretical, the perf ring-buffer is such a construct for example.)

So IMHO this is a quality of implementation issue that we should fix.

> diff --git a/lib/string.c b/lib/string.c
> index 8dbb7b1eab50..ba64f4e0382d 100644
> --- a/lib/string.c
> +++ b/lib/string.c
> @@ -203,12 +203,13 @@ ssize_t strscpy(char *dest, const char *src, size_t count)
>  		unsigned long c, data;
>  		c = *(unsigned long *)(src+res);
> -		*(unsigned long *)(dest+res) = c;
>  		if (has_zero(c, &data, &constants)) {
>  			data = prep_zero_mask(c, data, &constants);
>  			data = create_zero_mask(data);
> +			*(unsigned long *)(dest+res) = c & data;
>  			return res + find_zero(data);
>  		}
> +		*(unsigned long *)(dest+res) = c;
>  		res += sizeof(unsigned long);
>  		count -= sizeof(unsigned long);
>  		max -= sizeof(unsigned long);

Looks good to me!

Thanks,

	Ingo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1239728

* Linus Torvalds <torvalds@linux-foundation.org> wrote:

> > 2) strscpy() will copy garbage past NUL from source into destination. It won't 
> > fault but still, who knows what lies after string.
> 
> Yes, that's probably worth fixing before we get actual users..

Hm, this is the spot:

                c = *(unsigned long *)(src+res);
                *(unsigned long *)(dest+res) = c;

                if (has_zero(c, &data, &constants)) {
                        data = prep_zero_mask(c, data, &constants);
                        data = create_zero_mask(data);
                        return res + find_zero(data);
                }

We could do something like:

                c = *(unsigned long *)(src+res);
                *(unsigned long *)(dest+res) = c;

                if (has_zero(c, &data, &constants)) {
			unsigned int zero_pos;

                        data = prep_zero_mask(c, data, &constants);
                        data = create_zero_mask(data);

			zero_pos = find_zero(data);
			res += zero_pos;

			memset(dest+res, 0, sizeof(long)-zero_pos);

                        return res;
                }

I.e. the extra memset() clears out the partial word (if any) after the NUL.

Completely untested.

Thanks,

	Ingo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1239944

On Mon, Oct 5, 2015 at 5:22 PM, Ingo Molnar <mingo@kernel.org> wrote:
>
> We could do something like:
>
>                 c = *(unsigned long *)(src+res);
>                 *(unsigned long *)(dest+res) = c;
>
>                 if (has_zero(c, &data, &constants)) {

No, I think we'd be better off just moving the "has_zero()" to to
before the destination write, and instead doing the destination write
for the "word has zero" case one byte at a time. Sure, you'd need to
do it differently for little- and big-endian, but big deal.

So just something like

    c = *(unsigned long *)(src+res);
    if (has_zero(c, &data, &constants))
        return strscpy_final_word(c, dst, res);
    *(unsigned long *)(dest+res) = c;
    ...

where that "strscpy_final_word()" looks something like

    static inline strscpy_final_word(unsigned long word, char *dst, long res)
    {
        for (;;res++) {
            char c;
#ifdef LITTLE_ENDIAN
            c = word; word >>= 8;
#else
            c = word >> 8*(sizeof(unsigned long)-1); word <<= 8;
#endif
            dst[res] = c;
            if (!c)
                return res;
        }
    }

which really shouldn't be too bad.

I don't think it's much better to use "memset()" than it is to have
the partially filled from the last word of the source.

For "strncpy_from_user()" we do that "partial source word write", and
it's ok there, mainly because (a) that case isn't even trying to be
some generic interface and (b) "strncpy_from_user()" is really
performance-critical. I suspect for strscpy() we're better off just
being slightly more careful. I don't think it's *nearly* as
performance-critical as something like strncpy_from_user() that is
used for every single pathname copy etc.

Alternatively, if we really do expect strscpy() to maybe be
performance-critical, we could just document the fact that it does
things word-at-a-time and that bytes after the terminating NUL
character are *not* reliable. So we *might* just choose to document
this as an implementation issue. But the "memset()" approach just
looks bad.

             Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1241189 — Re: [PATCH] strscpy: zero any trailing garbage bytes in the destination

* Chris Metcalf <cmetcalf@ezchip.com> wrote:

> It's possible that the destination can be shadowed in userspace
> (as, for example, the perf buffers are now).  So we should take
> care not to leak data that could be inspected by userspace.
> 
> Signed-off-by: Chris Metcalf <cmetcalf@ezchip.com>
> ---
> Ingo, can you test this change in your Fedora+strlcpy boot test?
> I think it's correct but the more testing the better, particularly
> if we're about to add the support for strlcpy to use it.

Yeah, booted it on a couple of systems and everything seems to be fine:

Tested-by: Ingo Molnar <mingo@kernel.org>

Thanks,

	Ingo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web