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

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

[Alexey Dobriyan]

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.

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

[Ingo Molnar]

* 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

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

[Ingo Molnar]

* 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

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

[Ingo Molnar]

* 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

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

[Ingo Molnar]

* 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

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

[Ingo Molnar]

* 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);

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

[Chris Metcalf]

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

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

[Ingo Molnar]

* 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

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

[Linus Torvalds]

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

[PATCH] strscpy: zero any trailing garbage bytes in the destination

[Chris Metcalf]

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.

I did some light testing on big-endian tilegx and it appears
that zero_bytemask() is required and does the right thing.
On little-endian it's generally a no-op.  This is pretty much
the same pattern that fs/namei.c uses now too.

 lib/string.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/lib/string.c b/lib/string.c
index 8dbb7b1eab50..84775ba873b9 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 & zero_bytemask(data);
 			return res + find_zero(data);
 		}
+		*(unsigned long *)(dest+res) = c;
 		res += sizeof(unsigned long);
 		count -= sizeof(unsigned long);
 		max -= sizeof(unsigned long);
-- 
2.1.2

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

[kbuild test robot]

[-- Attachment #1: Type: text/plain, Size: 1291 bytes --]

Hi Chris,

[auto build test ERROR on v4.3-rc4 -- if it's inappropriate base, please ignore]

config: alpha-defconfig (attached as .config)
reproduce:
        wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross
        chmod +x ~/bin/make.cross
        # save the attached .config to linux build tree
        make.cross ARCH=alpha 

All errors (new ones prefixed by >>):

   lib/string.c: In function 'strscpy':
>> lib/string.c:209:4: error: implicit declaration of function 'zero_bytemask' [-Werror=implicit-function-declaration]
       *(unsigned long *)(dest+res) = c & zero_bytemask(data);
       ^
   cc1: some warnings being treated as errors

vim +/zero_bytemask +209 lib/string.c

   203			unsigned long c, data;
   204	
   205			c = *(unsigned long *)(src+res);
   206			if (has_zero(c, &data, &constants)) {
   207				data = prep_zero_mask(c, data, &constants);
   208				data = create_zero_mask(data);
 > 209				*(unsigned long *)(dest+res) = c & zero_bytemask(data);
   210				return res + find_zero(data);
   211			}
   212			*(unsigned long *)(dest+res) = c;

---
0-DAY kernel test infrastructure                Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all                   Intel Corporation

[-- Attachment #2: .config.gz --]
[-- Type: application/octet-stream, Size: 11535 bytes --]

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

[Chris Metcalf]

On 10/06/2015 12:47 PM, Chris Metcalf 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.

Oops, we need to ensure platforms all have zero_bytemask()
before we can do this.  It's pretty trivial in general, but not all
platforms have it now.  I'll post a patch to fix this as needed,
which should be taken before this patch to avoid git bisect
failures.

I'll also see about fixing some skew in platforms that are
either newer than the patch (h8300) or added word-at-a-time.h
since the original patch (powerpc, tile).

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

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

[Ingo Molnar]

* 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