[PATCH] userns: improve uid/gid map collision detection

[PATCH] userns: improve uid/gid map collision detection

[Aristeu Rozanski]

Initial implementation of the uid/gid maps will enforce that the
maps should be in order and would prevent a use case like this from
being used:
	0	1000	1
	48	500	1

since the second entry both values should be bigger than the previous.
This patch implements a more elaborate collision detection allowing any
order to be used.

Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Cc: "Serge E. Hallyn" <serge@hallyn.com>
Signed-off-by: Aristeu Rozanski <aris@redhat.com>

diff --git a/kernel/user_namespace.c b/kernel/user_namespace.c
index 2b042c4..fb0e492 100644
--- a/kernel/user_namespace.c
+++ b/kernel/user_namespace.c
@@ -521,6 +521,28 @@ struct seq_operations proc_projid_seq_operations = {
 
 static DEFINE_MUTEX(id_map_mutex);
 
+#define in_range(b,first,len) ((b)>=(first)&&(b)<(first)+(len))
+static inline int extent_collision(struct uid_gid_map *new_map,
+				   struct uid_gid_extent *extent)
+{
+	int i;
+	struct uid_gid_extent *cur;
+
+	for (i = 0; i < new_map->nr_extents; i++) {
+		cur = &new_map->extent[i];
+		if (in_range(extent->first, cur->first, cur->count) ||
+		    in_range(extent->first + extent->count, cur->first,
+			     cur->count))
+			return 1;
+		if (in_range(extent->lower_first, cur->lower_first,
+			     cur->count) ||
+		    in_range(extent->lower_first + extent->count,
+			     cur->lower_first, cur->count))
+			return 1;
+	}
+	return 0;
+}
+
 static ssize_t map_write(struct file *file, const char __user *buf,
 			 size_t count, loff_t *ppos,
 			 int cap_setid,
@@ -634,10 +656,7 @@ static ssize_t map_write(struct file *file, const char __user *buf,
 		if ((extent->lower_first + extent->count) <= extent->lower_first)
 			goto out;
 
-		/* For now only accept extents that are strictly in order */
-		if (last &&
-		    (((last->first + last->count) > extent->first) ||
-		     ((last->lower_first + last->count) > extent->lower_first)))
+		if (extent_collision(&new_map, extent))
 			goto out;
 
 		new_map.nr_extents++;

Re: [PATCH] userns: improve uid/gid map collision detection

[Serge E. Hallyn]

Quoting Aristeu Rozanski (aris@redhat.com):
> Initial implementation of the uid/gid maps will enforce that the
> maps should be in order and would prevent a use case like this from
> being used:
> 	0	1000	1
> 	48	500	1
> 
> since the second entry both values should be bigger than the previous.
> This patch implements a more elaborate collision detection allowing any
> order to be used.
> 
> Cc: "Eric W. Biederman" <ebiederm@xmission.com>
> Cc: "Serge E. Hallyn" <serge@hallyn.com>

I *think* that looks just right :)

Acked-by: Serge Hallyn <serge.hallyn@canonical.com>

> Signed-off-by: Aristeu Rozanski <aris@redhat.com>
> 
> diff --git a/kernel/user_namespace.c b/kernel/user_namespace.c
> index 2b042c4..fb0e492 100644
> --- a/kernel/user_namespace.c
> +++ b/kernel/user_namespace.c
> @@ -521,6 +521,28 @@ struct seq_operations proc_projid_seq_operations = {
>  
>  static DEFINE_MUTEX(id_map_mutex);
>  
> +#define in_range(b,first,len) ((b)>=(first)&&(b)<(first)+(len))
> +static inline int extent_collision(struct uid_gid_map *new_map,
> +				   struct uid_gid_extent *extent)
> +{
> +	int i;
> +	struct uid_gid_extent *cur;
> +
> +	for (i = 0; i < new_map->nr_extents; i++) {
> +		cur = &new_map->extent[i];
> +		if (in_range(extent->first, cur->first, cur->count) ||
> +		    in_range(extent->first + extent->count, cur->first,
> +			     cur->count))
> +			return 1;
> +		if (in_range(extent->lower_first, cur->lower_first,
> +			     cur->count) ||
> +		    in_range(extent->lower_first + extent->count,
> +			     cur->lower_first, cur->count))
> +			return 1;
> +	}
> +	return 0;
> +}
> +
>  static ssize_t map_write(struct file *file, const char __user *buf,
>  			 size_t count, loff_t *ppos,
>  			 int cap_setid,
> @@ -634,10 +656,7 @@ static ssize_t map_write(struct file *file, const char __user *buf,
>  		if ((extent->lower_first + extent->count) <= extent->lower_first)
>  			goto out;
>  
> -		/* For now only accept extents that are strictly in order */
> -		if (last &&
> -		    (((last->first + last->count) > extent->first) ||
> -		     ((last->lower_first + last->count) > extent->lower_first)))
> +		if (extent_collision(&new_map, extent))
>  			goto out;
>  
>  		new_map.nr_extents++;

[PATCH v2] userns: improve uid/gid map collision detection

[Aristeu Rozanski]

userns: improve uid/gid map collision detection

Initial implementation of the uid/gid maps (/proc/<pid>/{u,g}id_map) will
enforce that the UID and GID maps be written in strict order as a simple
way to check for range collision:
	local id	mapped to	count/range
	0		1000		50
	(ids 0-50 get mapped to 1000-1050)
	100		2120		10
	500		5000		200
so for each new entry, local id must be bigger than last local id (plus
count) and the ids it maps to also needs to be bigger than the last
entry (plus count).

This makes impossible to have a use case like this:
	local id	mapped to	count/range
	0		1000		1
	48		500		20

because while 48+20 > 0+1, 500+20 < 1000+1.

This patch implements a more elaborate collision detection allowing any
order to be used.

v2: improved the patch description as requested by Andrew

Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Cc: "Serge E. Hallyn" <serge@hallyn.com>
Cc: linux-security-module@vger.kernel.org
Signed-off-by: Aristeu Rozanski <aris@redhat.com>

diff --git a/kernel/user_namespace.c b/kernel/user_namespace.c
index 2b042c4..fb0e492 100644
--- a/kernel/user_namespace.c
+++ b/kernel/user_namespace.c
@@ -521,6 +521,28 @@ struct seq_operations proc_projid_seq_operations = {
 
 static DEFINE_MUTEX(id_map_mutex);
 
+#define in_range(b,first,len) ((b)>=(first)&&(b)<(first)+(len))
+static inline int extent_collision(struct uid_gid_map *new_map,
+				   struct uid_gid_extent *extent)
+{
+	int i;
+	struct uid_gid_extent *cur;
+
+	for (i = 0; i < new_map->nr_extents; i++) {
+		cur = &new_map->extent[i];
+		if (in_range(extent->first, cur->first, cur->count) ||
+		    in_range(extent->first + extent->count, cur->first,
+			     cur->count))
+			return 1;
+		if (in_range(extent->lower_first, cur->lower_first,
+			     cur->count) ||
+		    in_range(extent->lower_first + extent->count,
+			     cur->lower_first, cur->count))
+			return 1;
+	}
+	return 0;
+}
+
 static ssize_t map_write(struct file *file, const char __user *buf,
 			 size_t count, loff_t *ppos,
 			 int cap_setid,
@@ -634,10 +656,7 @@ static ssize_t map_write(struct file *file, const char __user *buf,
 		if ((extent->lower_first + extent->count) <= extent->lower_first)
 			goto out;
 
-		/* For now only accept extents that are strictly in order */
-		if (last &&
-		    (((last->first + last->count) > extent->first) ||
-		     ((last->lower_first + last->count) > extent->lower_first)))
+		if (extent_collision(&new_map, extent))
 			goto out;
 
 		new_map.nr_extents++;

Re: [PATCH v2] userns: improve uid/gid map collision detection

[Andrew Morton]

On Thu, 24 Jan 2013 10:28:59 -0500
Aristeu Rozanski <aris@redhat.com> wrote:

> userns: improve uid/gid map collision detection
> 
> Initial implementation of the uid/gid maps (/proc/<pid>/{u,g}id_map) will
> enforce that the UID and GID maps be written in strict order as a simple
> way to check for range collision:
> 	local id	mapped to	count/range
> 	0		1000		50
> 	(ids 0-50 get mapped to 1000-1050)
> 	100		2120		10
> 	500		5000		200
> so for each new entry, local id must be bigger than last local id (plus
> count) and the ids it maps to also needs to be bigger than the last
> entry (plus count).
> 
> This makes impossible to have a use case like this:
> 	local id	mapped to	count/range
> 	0		1000		1
> 	48		500		20
> 
> because while 48+20 > 0+1, 500+20 < 1000+1.
> 
> This patch implements a more elaborate collision detection allowing any
> order to be used.
> 
> v2: improved the patch description as requested by Andrew

Thanks.

> --- a/kernel/user_namespace.c
> +++ b/kernel/user_namespace.c
> @@ -521,6 +521,28 @@ struct seq_operations proc_projid_seq_operations = {
>  
>  static DEFINE_MUTEX(id_map_mutex);
>  
> +#define in_range(b,first,len) ((b)>=(first)&&(b)<(first)+(len))

eek, a macro!  Macros are always bad.

This one is bad because

a) it's a macro

b) it evaluates its args multiple times and hence will cause nasty
   bugs if called with expressions-with-side-effects.

c) it evaluates its args multiple times and if called with
   non-trivial expressions the compiler might not be able to CSE those
   expressions, leading to code bloat.

Add lo, this patch:

--- a/kernel/user_namespace.c~userns-improve-uid-gid-map-collision-detection-fix
+++ a/kernel/user_namespace.c
@@ -521,7 +521,11 @@ struct seq_operations proc_projid_seq_op
 
 static DEFINE_MUTEX(id_map_mutex);
 
-#define in_range(b,first,len) ((b)>=(first)&&(b)<(first)+(len))
+static bool in_range(u32 b, u32 first, u32 len)
+{
+	return b >= first && b < first + len;
+}
+
 static inline int extent_collision(struct uid_gid_map *new_map,
 				   struct uid_gid_extent *extent)
 {

reduces the user_namespace.o text from 4822 bytes to 4727 with
gcc-4.4.4.  This is a remarkably large difference.


btw, what the heck is up with CONFIG_UIDGID_CONVERTED?  That thing
prevents userns from being compiled in an allmodconfig build, which is
rather undesirable.  Isn't there a better, more user-friendly way of
doing this?

Re: [PATCH v2] userns: improve uid/gid map collision detection

[Eric W. Biederman]

I will look at this patch in a bit.  I already have a similar patch
in my queue, although I don't know if I have pushed that out yet.


Andrew Morton <akpm@linux-foundation.org> writes:

> btw, what the heck is up with CONFIG_UIDGID_CONVERTED?  That thing
> prevents userns from being compiled in an allmodconfig build, which is
> rather undesirable.  Isn't there a better, more user-friendly way of
> doing this?

CONFIG_UIDGID_CONVERTED is what keeps the allmodconfig building with user
namespaces enabled.

The practical issue is that the uid_t, gid_t converstion to kuid_t and
kgid_t is not quite done.  And it takes a lot of pain staking review in
some cases to get it done.

In places where the conversion is not complete the code fails to compile
preventing the introduction of security holes.

If you look in init/Kconfig at the definition of CONFIG_UIDGID_CONVERTED
you see the list of filesystems that still need changes.

I have the basic version of those changes queued up, and I believe those
changes are correct.  However I need to break them into smaller patches
to make the changes obviously correct.  One of the things I have
discovered along the way of making these conversions is that I need to
push kuid_t and kgid_t as deep and as thoroughly into the code as I can
or I will fail to place conversions where they need to be.

The amount of work required on those final pieces appears to be
proportional to the size of the filesystem rather than proportional to
the size of the changes to those filesystems.  Because there is so much
code that must be reviewed and understood.

I am hoping I can get the conversions done and CONFIG_UIDGID_CONVERTED
can be killed for 3.9 but we will see.

Eric

Re: [PATCH v2] userns: improve uid/gid map collision detection

[Aristeu Rozanski]

On Thu, Jan 24, 2013 at 04:46:12PM -0800, Andrew Morton wrote:
> eek, a macro!  Macros are always bad.
> 
> This one is bad because
> 
> a) it's a macro
> 
> b) it evaluates its args multiple times and hence will cause nasty
>    bugs if called with expressions-with-side-effects.
> 
> c) it evaluates its args multiple times and if called with
>    non-trivial expressions the compiler might not be able to CSE those
>    expressions, leading to code bloat.
> 
> Add lo, this patch:
> 
> --- a/kernel/user_namespace.c~userns-improve-uid-gid-map-collision-detection-fix
> +++ a/kernel/user_namespace.c
> @@ -521,7 +521,11 @@ struct seq_operations proc_projid_seq_op
>  
>  static DEFINE_MUTEX(id_map_mutex);
>  
> -#define in_range(b,first,len) ((b)>=(first)&&(b)<(first)+(len))
> +static bool in_range(u32 b, u32 first, u32 len)
> +{
> +	return b >= first && b < first + len;
> +}
> +
>  static inline int extent_collision(struct uid_gid_map *new_map,
>  				   struct uid_gid_extent *extent)
>  {
> 
> reduces the user_namespace.o text from 4822 bytes to 4727 with
> gcc-4.4.4.  This is a remarkably large difference.

thanks Andrew

(I see Eric already answered about the config option)

-- 
Aristeu

Re: [PATCH v2] userns: improve uid/gid map collision detection

[Eric W. Biederman]

Aristeu Rozanski <aris@redhat.com> writes:

> On Thu, Jan 24, 2013 at 04:46:12PM -0800, Andrew Morton wrote:
>> eek, a macro!  Macros are always bad.
>> 
>> This one is bad because
>> 
>> a) it's a macro
>> 
>> b) it evaluates its args multiple times and hence will cause nasty
>>    bugs if called with expressions-with-side-effects.
>> 
>> c) it evaluates its args multiple times and if called with
>>    non-trivial expressions the compiler might not be able to CSE those
>>    expressions, leading to code bloat.
>> 
>> Add lo, this patch:
>> 
>> --- a/kernel/user_namespace.c~userns-improve-uid-gid-map-collision-detection-fix
>> +++ a/kernel/user_namespace.c
>> @@ -521,7 +521,11 @@ struct seq_operations proc_projid_seq_op
>>  
>>  static DEFINE_MUTEX(id_map_mutex);
>>  
>> -#define in_range(b,first,len) ((b)>=(first)&&(b)<(first)+(len))
>> +static bool in_range(u32 b, u32 first, u32 len)
>> +{
>> +	return b >= first && b < first + len;
>> +}
>> +
>>  static inline int extent_collision(struct uid_gid_map *new_map,
>>  				   struct uid_gid_extent *extent)
>>  {
>> 
>> reduces the user_namespace.o text from 4822 bytes to 4727 with
>> gcc-4.4.4.  This is a remarkably large difference.
>
> thanks Andrew
>
> (I see Eric already answered about the config option)

Aritsteu after looking at both my version and yours I am going with
mine.  While my code is a little wordier I have half the number of
comparisons your code does, and I took the time to kill the variable
introducing a function to test for range collisions makes unnecessary.
On Andrews size metric my version seems noticably smaller as well.

 size $PWD-build/kernel/user_namespace.o
   text	   data	    bss	    dec	    hex	filename
   4376	    144	      0	   4520	   11a8	/home/eric/projects/linux/linux-userns-devel-build/kernel/user_namespace.o


Short of something unexpected I plan to push all my code to linux-next
sometime tomorrow.

Eric

Re: [PATCH v2] userns: improve uid/gid map collision detection

[Aristeu Rozanski]

On Fri, Jan 25, 2013 at 06:31:37PM -0800, Eric W. Biederman wrote:
> Aritsteu after looking at both my version and yours I am going with

one extra t.

> mine.  While my code is a little wordier I have half the number of
> comparisons your code does, and I took the time to kill the variable
> introducing a function to test for range collisions makes unnecessary.
> On Andrews size metric my version seems noticably smaller as well.
> 
>  size $PWD-build/kernel/user_namespace.o
>    text	   data	    bss	    dec	    hex	filename
>    4376	    144	      0	   4520	   11a8	/home/eric/projects/linux/linux-userns-devel-build/kernel/user_namespace.o
> 
> 
> Short of something unexpected I plan to push all my code to linux-next
> sometime tomorrow.

sure, no problem
Thanks Eric

-- 
Aristeu