[PATCH] ELF: fix overflow in total mapping size calculation

[PATCH] ELF: fix overflow in total mapping size calculation

[Alexey Dobriyan]

Kernel assumes that ELF program headers are ordered by mapping address,
but doesn't enforce it. It is possible to make mapping size extremely huge
by simply shuffling first and last PT_LOAD segments.

As long as PT_LOAD segments do not overlap, it is silly to require
sorting by v_addr anyway because mmap() doesn't care.

Don't assume PT_LOAD segments are sorted and calculate min and max
addresses correctly.

Signed-off-by: Alexey Dobriyan <adobriyan@gmail.com>
---

 fs/binfmt_elf.c |   23 +++++++++++------------
 1 file changed, 11 insertions(+), 12 deletions(-)

--- a/fs/binfmt_elf.c
+++ b/fs/binfmt_elf.c
@@ -93,7 +93,7 @@ static int elf_core_dump(struct coredump_params *cprm);
 #define ELF_CORE_EFLAGS	0
 #endif
 
-#define ELF_PAGESTART(_v) ((_v) & ~(unsigned long)(ELF_MIN_ALIGN-1))
+#define ELF_PAGESTART(_v) ((_v) & ~(int)(ELF_MIN_ALIGN-1))
 #define ELF_PAGEOFFSET(_v) ((_v) & (ELF_MIN_ALIGN-1))
 #define ELF_PAGEALIGN(_v) (((_v) + ELF_MIN_ALIGN - 1) & ~(ELF_MIN_ALIGN - 1))
 
@@ -399,22 +399,21 @@ static unsigned long elf_map(struct file *filep, unsigned long addr,
 	return(map_addr);
 }
 
-static unsigned long total_mapping_size(const struct elf_phdr *cmds, int nr)
+static unsigned long total_mapping_size(const struct elf_phdr *phdr, int nr)
 {
-	int i, first_idx = -1, last_idx = -1;
+	elf_addr_t min_addr = -1;
+	elf_addr_t max_addr = 0;
+	bool pt_load = false;
+	int i;
 
 	for (i = 0; i < nr; i++) {
-		if (cmds[i].p_type == PT_LOAD) {
-			last_idx = i;
-			if (first_idx == -1)
-				first_idx = i;
+		if (phdr[i].p_type == PT_LOAD) {
+			min_addr = min(min_addr, ELF_PAGESTART(phdr[i].p_vaddr));
+			max_addr = max(max_addr, phdr[i].p_vaddr + phdr[i].p_memsz);
+			pt_load = true;
 		}
 	}
-	if (first_idx == -1)
-		return 0;
-
-	return cmds[last_idx].p_vaddr + cmds[last_idx].p_memsz -
-				ELF_PAGESTART(cmds[first_idx].p_vaddr);
+	return pt_load ? (max_addr - min_addr) : 0;
 }
 
 static int elf_read(struct file *file, void *buf, size_t len, loff_t pos)

Re: [PATCH] ELF: fix overflow in total mapping size calculation

[Andrew Morton]

On Sun, 3 Oct 2021 15:11:24 +0300 Alexey Dobriyan <adobriyan@gmail.com> wrote:

> Kernel assumes that ELF program headers are ordered by mapping address,
> but doesn't enforce it. It is possible to make mapping size extremely huge
> by simply shuffling first and last PT_LOAD segments.
> 
> As long as PT_LOAD segments do not overlap, it is silly to require
> sorting by v_addr anyway because mmap() doesn't care.
> 
> Don't assume PT_LOAD segments are sorted and calculate min and max
> addresses correctly.

It sounds good, but why do I have the feeling this will explode in some
unexpected fashion?  Because it's elf, and that's what it does :(

Re: [PATCH] ELF: fix overflow in total mapping size calculation

[Kees Cook]

On Sun, Oct 03, 2021 at 03:11:24PM +0300, Alexey Dobriyan wrote:
> Kernel assumes that ELF program headers are ordered by mapping address,
> but doesn't enforce it. It is possible to make mapping size extremely huge
> by simply shuffling first and last PT_LOAD segments.
> 
> As long as PT_LOAD segments do not overlap, it is silly to require
> sorting by v_addr anyway because mmap() doesn't care.
> 
> Don't assume PT_LOAD segments are sorted and calculate min and max
> addresses correctly.

Nice! Yes, this all make sense.

> 
> Signed-off-by: Alexey Dobriyan <adobriyan@gmail.com>
> ---
> 
>  fs/binfmt_elf.c |   23 +++++++++++------------
>  1 file changed, 11 insertions(+), 12 deletions(-)
> 
> --- a/fs/binfmt_elf.c
> +++ b/fs/binfmt_elf.c
> @@ -93,7 +93,7 @@ static int elf_core_dump(struct coredump_params *cprm);
>  #define ELF_CORE_EFLAGS	0
>  #endif
>  
> -#define ELF_PAGESTART(_v) ((_v) & ~(unsigned long)(ELF_MIN_ALIGN-1))
> +#define ELF_PAGESTART(_v) ((_v) & ~(int)(ELF_MIN_ALIGN-1))

Errr, this I don't like. I assume this is because of the min() use
below?

>  #define ELF_PAGEOFFSET(_v) ((_v) & (ELF_MIN_ALIGN-1))
>  #define ELF_PAGEALIGN(_v) (((_v) + ELF_MIN_ALIGN - 1) & ~(ELF_MIN_ALIGN - 1))
>  
> @@ -399,22 +399,21 @@ static unsigned long elf_map(struct file *filep, unsigned long addr,
>  	return(map_addr);
>  }
>  
> -static unsigned long total_mapping_size(const struct elf_phdr *cmds, int nr)
> +static unsigned long total_mapping_size(const struct elf_phdr *phdr, int nr)
>  {
> -	int i, first_idx = -1, last_idx = -1;
> +	elf_addr_t min_addr = -1;
> +	elf_addr_t max_addr = 0;
> +	bool pt_load = false;
> +	int i;
>  
>  	for (i = 0; i < nr; i++) {
> -		if (cmds[i].p_type == PT_LOAD) {
> -			last_idx = i;
> -			if (first_idx == -1)
> -				first_idx = i;
> +		if (phdr[i].p_type == PT_LOAD) {
> +			min_addr = min(min_addr, ELF_PAGESTART(phdr[i].p_vaddr));
> +			max_addr = max(max_addr, phdr[i].p_vaddr + phdr[i].p_memsz);

How about:
		min_addr = min_t(elf_addr_t, min_addr, ELF_PAGESTART(phdr[i].p_vaddr));
		max_addr = max_t(elf_addr_t, max_addr, phdr[i].p_vaddr + phdr[i].p_memsz);

> +			pt_load = true;
>  		}
>  	}
> -	if (first_idx == -1)
> -		return 0;
> -
> -	return cmds[last_idx].p_vaddr + cmds[last_idx].p_memsz -
> -				ELF_PAGESTART(cmds[first_idx].p_vaddr);
> +	return pt_load ? (max_addr - min_addr) : 0;
>  }
>  
>  static int elf_read(struct file *file, void *buf, size_t len, loff_t pos)

-Kees

-- 
Kees Cook

Re: [PATCH] ELF: fix overflow in total mapping size calculation

[Alexey Dobriyan]

On Tue, Oct 05, 2021 at 05:21:29PM -0700, Andrew Morton wrote:
> On Sun, 3 Oct 2021 15:11:24 +0300 Alexey Dobriyan <adobriyan@gmail.com> wrote:
> 
> > Kernel assumes that ELF program headers are ordered by mapping address,
> > but doesn't enforce it. It is possible to make mapping size extremely huge
> > by simply shuffling first and last PT_LOAD segments.
> > 
> > As long as PT_LOAD segments do not overlap, it is silly to require
> > sorting by v_addr anyway because mmap() doesn't care.
> > 
> > Don't assume PT_LOAD segments are sorted and calculate min and max
> > addresses correctly.
> 
> It sounds good, but why do I have the feeling this will explode in some
> unexpected fashion?  Because it's elf, and that's what it does :(

Good news, it is ELF, we'll hear about breakage immediately. :^)

Kernel "enforces" PT_LOAD ordering: if total mapping size overflows,
then mmap will reject it. I hope every ELF binary maintains ordering.

But! total_mapping_size() only looks at first and the last PT_LOAD
segments which is obviously incorrect.

Re: [PATCH] ELF: fix overflow in total mapping size calculation

[Alexey Dobriyan]

On Tue, Oct 05, 2021 at 07:31:09PM -0700, Kees Cook wrote:
> On Sun, Oct 03, 2021 at 03:11:24PM +0300, Alexey Dobriyan wrote:
> > Kernel assumes that ELF program headers are ordered by mapping address,
> > but doesn't enforce it. It is possible to make mapping size extremely huge
> > by simply shuffling first and last PT_LOAD segments.
> > 
> > As long as PT_LOAD segments do not overlap, it is silly to require
> > sorting by v_addr anyway because mmap() doesn't care.
> > 
> > Don't assume PT_LOAD segments are sorted and calculate min and max
> > addresses correctly.
> 
> Nice! Yes, this all make sense.
> 
> > 
> > Signed-off-by: Alexey Dobriyan <adobriyan@gmail.com>
> > ---
> > 
> >  fs/binfmt_elf.c |   23 +++++++++++------------
> >  1 file changed, 11 insertions(+), 12 deletions(-)
> > 
> > --- a/fs/binfmt_elf.c
> > +++ b/fs/binfmt_elf.c
> > @@ -93,7 +93,7 @@ static int elf_core_dump(struct coredump_params *cprm);
> >  #define ELF_CORE_EFLAGS	0
> >  #endif
> >  
> > -#define ELF_PAGESTART(_v) ((_v) & ~(unsigned long)(ELF_MIN_ALIGN-1))
> > +#define ELF_PAGESTART(_v) ((_v) & ~(int)(ELF_MIN_ALIGN-1))
> 
> Errr, this I don't like. I assume this is because of the min() use
> below?

Yes, this is to shut up the warning.

The macro is slightly incorrect because "_v" can be either uint32_t or
uint64_t. But standard ALIGN macros are slightly incorrect too.

I don't want to clean this particular mess right now. Those are separate stables.

> >  #define ELF_PAGEOFFSET(_v) ((_v) & (ELF_MIN_ALIGN-1))
> >  #define ELF_PAGEALIGN(_v) (((_v) + ELF_MIN_ALIGN - 1) & ~(ELF_MIN_ALIGN - 1))
> >  
> > @@ -399,22 +399,21 @@ static unsigned long elf_map(struct file *filep, unsigned long addr,
> >  	return(map_addr);
> >  }
> >  
> > -static unsigned long total_mapping_size(const struct elf_phdr *cmds, int nr)
> > +static unsigned long total_mapping_size(const struct elf_phdr *phdr, int nr)
> >  {
> > -	int i, first_idx = -1, last_idx = -1;
> > +	elf_addr_t min_addr = -1;
> > +	elf_addr_t max_addr = 0;
> > +	bool pt_load = false;
> > +	int i;
> >  
> >  	for (i = 0; i < nr; i++) {
> > -		if (cmds[i].p_type == PT_LOAD) {
> > -			last_idx = i;
> > -			if (first_idx == -1)
> > -				first_idx = i;
> > +		if (phdr[i].p_type == PT_LOAD) {
> > +			min_addr = min(min_addr, ELF_PAGESTART(phdr[i].p_vaddr));
> > +			max_addr = max(max_addr, phdr[i].p_vaddr + phdr[i].p_memsz);
> 
> How about:
> 		min_addr = min_t(elf_addr_t, min_addr, ELF_PAGESTART(phdr[i].p_vaddr));
> 		max_addr = max_t(elf_addr_t, max_addr, phdr[i].p_vaddr + phdr[i].p_memsz);

No! The proper fix is to fix ELF_PAGESTART().

Re: [PATCH] ELF: fix overflow in total mapping size calculation

[Kees Cook]

On Thu, Oct 07, 2021 at 08:20:03PM +0300, Alexey Dobriyan wrote:
> On Tue, Oct 05, 2021 at 07:31:09PM -0700, Kees Cook wrote:
> > On Sun, Oct 03, 2021 at 03:11:24PM +0300, Alexey Dobriyan wrote:
> > > Kernel assumes that ELF program headers are ordered by mapping address,
> > > but doesn't enforce it. It is possible to make mapping size extremely huge
> > > by simply shuffling first and last PT_LOAD segments.
> > > 
> > > As long as PT_LOAD segments do not overlap, it is silly to require
> > > sorting by v_addr anyway because mmap() doesn't care.
> > > 
> > > Don't assume PT_LOAD segments are sorted and calculate min and max
> > > addresses correctly.
> > 
> > Nice! Yes, this all make sense.
> > 
> > > 
> > > Signed-off-by: Alexey Dobriyan <adobriyan@gmail.com>
> > > ---
> > > 
> > >  fs/binfmt_elf.c |   23 +++++++++++------------
> > >  1 file changed, 11 insertions(+), 12 deletions(-)
> > > 
> > > --- a/fs/binfmt_elf.c
> > > +++ b/fs/binfmt_elf.c
> > > @@ -93,7 +93,7 @@ static int elf_core_dump(struct coredump_params *cprm);
> > >  #define ELF_CORE_EFLAGS	0
> > >  #endif
> > >  
> > > -#define ELF_PAGESTART(_v) ((_v) & ~(unsigned long)(ELF_MIN_ALIGN-1))
> > > +#define ELF_PAGESTART(_v) ((_v) & ~(int)(ELF_MIN_ALIGN-1))
> > 
> > Errr, this I don't like. I assume this is because of the min() use
> > below?
> 
> Yes, this is to shut up the warning.
> 
> The macro is slightly incorrect because "_v" can be either uint32_t or
> uint64_t. But standard ALIGN macros are slightly incorrect too.

Right, but "int" is neither 64-sized nor unsigned. :P I would just leave
this macro as-is.

> 
> I don't want to clean this particular mess right now. Those are separate stables.
> 
> > >  #define ELF_PAGEOFFSET(_v) ((_v) & (ELF_MIN_ALIGN-1))
> > >  #define ELF_PAGEALIGN(_v) (((_v) + ELF_MIN_ALIGN - 1) & ~(ELF_MIN_ALIGN - 1))
> > >  
> > > @@ -399,22 +399,21 @@ static unsigned long elf_map(struct file *filep, unsigned long addr,
> > >  	return(map_addr);
> > >  }
> > >  
> > > -static unsigned long total_mapping_size(const struct elf_phdr *cmds, int nr)
> > > +static unsigned long total_mapping_size(const struct elf_phdr *phdr, int nr)
> > >  {
> > > -	int i, first_idx = -1, last_idx = -1;
> > > +	elf_addr_t min_addr = -1;
> > > +	elf_addr_t max_addr = 0;
> > > +	bool pt_load = false;
> > > +	int i;
> > >  
> > >  	for (i = 0; i < nr; i++) {
> > > -		if (cmds[i].p_type == PT_LOAD) {
> > > -			last_idx = i;
> > > -			if (first_idx == -1)
> > > -				first_idx = i;
> > > +		if (phdr[i].p_type == PT_LOAD) {
> > > +			min_addr = min(min_addr, ELF_PAGESTART(phdr[i].p_vaddr));
> > > +			max_addr = max(max_addr, phdr[i].p_vaddr + phdr[i].p_memsz);
> > 
> > How about:
> > 		min_addr = min_t(elf_addr_t, min_addr, ELF_PAGESTART(phdr[i].p_vaddr));
> > 		max_addr = max_t(elf_addr_t, max_addr, phdr[i].p_vaddr + phdr[i].p_memsz);
> 
> No! The proper fix is to fix ELF_PAGESTART().

Why? The warning from min() is about making sure there isn't an
unexpected type conversion. min_t() uses an explicit type, so why not
the above?

-- 
Kees Cook

Re: [PATCH] ELF: fix overflow in total mapping size calculation

[Alexey Dobriyan]

On Thu, Oct 07, 2021 at 10:40:01AM -0700, Kees Cook wrote:
> On Thu, Oct 07, 2021 at 08:20:03PM +0300, Alexey Dobriyan wrote:
> > On Tue, Oct 05, 2021 at 07:31:09PM -0700, Kees Cook wrote:
> > > On Sun, Oct 03, 2021 at 03:11:24PM +0300, Alexey Dobriyan wrote:
> > > > Kernel assumes that ELF program headers are ordered by mapping address,
> > > > but doesn't enforce it. It is possible to make mapping size extremely huge
> > > > by simply shuffling first and last PT_LOAD segments.
> > > > 
> > > > As long as PT_LOAD segments do not overlap, it is silly to require
> > > > sorting by v_addr anyway because mmap() doesn't care.
> > > > 
> > > > Don't assume PT_LOAD segments are sorted and calculate min and max
> > > > addresses correctly.
> > > 
> > > Nice! Yes, this all make sense.
> > > 
> > > > 
> > > > Signed-off-by: Alexey Dobriyan <adobriyan@gmail.com>
> > > > ---
> > > > 
> > > >  fs/binfmt_elf.c |   23 +++++++++++------------
> > > >  1 file changed, 11 insertions(+), 12 deletions(-)
> > > > 
> > > > --- a/fs/binfmt_elf.c
> > > > +++ b/fs/binfmt_elf.c
> > > > @@ -93,7 +93,7 @@ static int elf_core_dump(struct coredump_params *cprm);
> > > >  #define ELF_CORE_EFLAGS	0
> > > >  #endif
> > > >  
> > > > -#define ELF_PAGESTART(_v) ((_v) & ~(unsigned long)(ELF_MIN_ALIGN-1))
> > > > +#define ELF_PAGESTART(_v) ((_v) & ~(int)(ELF_MIN_ALIGN-1))
> > > 
> > > Errr, this I don't like. I assume this is because of the min() use
> > > below?
> > 
> > Yes, this is to shut up the warning.
> > 
> > The macro is slightly incorrect because "_v" can be either uint32_t or
> > uint64_t. But standard ALIGN macros are slightly incorrect too.
> 
> Right, but "int" is neither 64-sized nor unsigned. :P I would just leave
> this macro as-is.

"int" will be promoted to either "unsigned int" or to whatever 64-bit
ELF type is, it is enough to fix warnings, it will be sign extended
correctly.