[PATCH] elf: Relax assumptions about vaddr ordering

[PATCH] elf: Relax assumptions about vaddr ordering

[Magnus Groß]

From ff4dde97e82727727bda711f2367c05663498b24 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Magnus=20Gro=C3=9F?= <magnus.gross@rwth-aachen.de>
Date: Wed, 26 Jan 2022 16:35:07 +0100
Subject: [PATCH] elf: Relax assumptions about vaddr ordering
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Commit 5f501d555653 ("binfmt_elf: reintroduce using
MAP_FIXED_NOREPLACE") introduced a regression, where the kernel now
assumes that PT_LOAD segments are ordered by vaddr in load_elf_binary().

Specifically consider an ELF binary with the following PT_LOAD segments:

Type  Offset   VirtAddr   PhysAddr   FileSiz  MemSiz    Flg Align
LOAD  0x000000 0x08000000 0x08000000 0x474585 0x474585  R E 0x1000
LOAD  0x475000 0x08475000 0x08475000 0x090a4  0xc6c10   RW  0x1000
LOAD  0x47f000 0x00010000 0x00010000 0x00000  0x7ff0000     0x1000

Note how the last segment is actually the first segment and vice versa.

Since total_mapping_size() only computes the difference between the
first and the last segment in the order that they appear, it will return
a size of 0 in this case, thus causing load_elf_binary() to fail, which
did not happen before that change.

Strictly speaking total_mapping_size() made that assumption already
before that patch, but the issue did not appear because the old
load_addr_set guards never allowed this call to total_mapping_size().

Instead of fixing this by reverting to the old load_addr_set logic, we
fix this by comparing the correct first and last segments in
total_mapping_size().

Signed-off-by: Magnus Groß <magnus.gross@rwth-aachen.de>
---
 fs/binfmt_elf.c | 18 ++++++++++++++----
 1 file changed, 14 insertions(+), 4 deletions(-)

diff --git a/fs/binfmt_elf.c b/fs/binfmt_elf.c
index f8c7f26f1fbb..0caaad9eddd1 100644
--- a/fs/binfmt_elf.c
+++ b/fs/binfmt_elf.c
@@ -402,19 +402,29 @@ static unsigned long elf_map(struct file *filep, unsigned long addr,
 static unsigned long total_mapping_size(const struct elf_phdr *cmds, int nr)
 {
 	int i, first_idx = -1, last_idx = -1;
+	unsigned long min_vaddr = ULONG_MAX, max_vaddr = 0;
 
 	for (i = 0; i < nr; i++) {
 		if (cmds[i].p_type == PT_LOAD) {
-			last_idx = i;
-			if (first_idx == -1)
+			/*
+			 * The PT_LOAD segments are not necessarily ordered
+			 * by vaddr. Make sure that we get the segment with
+			 * minimum vaddr (maximum vaddr respectively)
+			 */
+			if (cmds[i].p_vaddr <= min_vaddr) {
 				first_idx = i;
+				min_vaddr = cmds[i].p_vaddr;
+			}
+			if (cmds[i].p_vaddr >= max_vaddr) {
+				last_idx = i;
+				max_vaddr = cmds[i].p_vaddr;
+			}
 		}
 	}
 	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 max_vaddr + cmds[last_idx].p_memsz - ELF_PAGESTART(min_vaddr);
 }
 
 static int elf_read(struct file *file, void *buf, size_t len, loff_t pos)
-- 
2.34.1

Re: [PATCH] elf: Relax assumptions about vaddr ordering

[Kees Cook]

On Wed, Jan 26, 2022 at 05:25:20PM +0100, Magnus Groß wrote:
> From ff4dde97e82727727bda711f2367c05663498b24 Mon Sep 17 00:00:00 2001
> From: =?UTF-8?q?Magnus=20Gro=C3=9F?= <magnus.gross@rwth-aachen.de>
> Date: Wed, 26 Jan 2022 16:35:07 +0100
> Subject: [PATCH] elf: Relax assumptions about vaddr ordering
> MIME-Version: 1.0
> Content-Type: text/plain; charset=UTF-8
> Content-Transfer-Encoding: 8bit
> 
> Commit 5f501d555653 ("binfmt_elf: reintroduce using
> MAP_FIXED_NOREPLACE") introduced a regression, where the kernel now
> assumes that PT_LOAD segments are ordered by vaddr in load_elf_binary().
> 
> Specifically consider an ELF binary with the following PT_LOAD segments:
> 
> Type  Offset   VirtAddr   PhysAddr   FileSiz  MemSiz    Flg Align
> LOAD  0x000000 0x08000000 0x08000000 0x474585 0x474585  R E 0x1000
> LOAD  0x475000 0x08475000 0x08475000 0x090a4  0xc6c10   RW  0x1000
> LOAD  0x47f000 0x00010000 0x00010000 0x00000  0x7ff0000     0x1000
> 
> Note how the last segment is actually the first segment and vice versa.
> 
> Since total_mapping_size() only computes the difference between the
> first and the last segment in the order that they appear, it will return
> a size of 0 in this case, thus causing load_elf_binary() to fail, which
> did not happen before that change.
> 
> Strictly speaking total_mapping_size() made that assumption already
> before that patch, but the issue did not appear because the old
> load_addr_set guards never allowed this call to total_mapping_size().
> 
> Instead of fixing this by reverting to the old load_addr_set logic, we
> fix this by comparing the correct first and last segments in
> total_mapping_size().

Ah, nice. Yeah, this is good.

> Signed-off-by: Magnus Groß <magnus.gross@rwth-aachen.de>

Fixes: 5f501d555653 ("binfmt_elf: reintroduce using MAP_FIXED_NOREPLACE")
Cc: stable@vger.kernel.org
Acked-by: Kees Cook <keescook@chromium.org>

-Kees

> ---
>  fs/binfmt_elf.c | 18 ++++++++++++++----
>  1 file changed, 14 insertions(+), 4 deletions(-)
> 
> diff --git a/fs/binfmt_elf.c b/fs/binfmt_elf.c
> index f8c7f26f1fbb..0caaad9eddd1 100644
> --- a/fs/binfmt_elf.c
> +++ b/fs/binfmt_elf.c
> @@ -402,19 +402,29 @@ static unsigned long elf_map(struct file *filep, unsigned long addr,
>  static unsigned long total_mapping_size(const struct elf_phdr *cmds, int nr)
>  {
>  	int i, first_idx = -1, last_idx = -1;
> +	unsigned long min_vaddr = ULONG_MAX, max_vaddr = 0;
>  
>  	for (i = 0; i < nr; i++) {
>  		if (cmds[i].p_type == PT_LOAD) {
> -			last_idx = i;
> -			if (first_idx == -1)
> +			/*
> +			 * The PT_LOAD segments are not necessarily ordered
> +			 * by vaddr. Make sure that we get the segment with
> +			 * minimum vaddr (maximum vaddr respectively)
> +			 */
> +			if (cmds[i].p_vaddr <= min_vaddr) {
>  				first_idx = i;
> +				min_vaddr = cmds[i].p_vaddr;
> +			}
> +			if (cmds[i].p_vaddr >= max_vaddr) {
> +				last_idx = i;
> +				max_vaddr = cmds[i].p_vaddr;
> +			}
>  		}
>  	}
>  	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 max_vaddr + cmds[last_idx].p_memsz - ELF_PAGESTART(min_vaddr);
>  }
>  
>  static int elf_read(struct file *file, void *buf, size_t len, loff_t pos)
> -- 
> 2.34.1

-- 
Kees Cook

Re: [PATCH] elf: Relax assumptions about vaddr ordering

[Kees Cook]

On Wed, Jan 26, 2022 at 08:50:15AM -0800, Kees Cook wrote:
> On Wed, Jan 26, 2022 at 05:25:20PM +0100, Magnus Groß wrote:
> > From ff4dde97e82727727bda711f2367c05663498b24 Mon Sep 17 00:00:00 2001
> > From: =?UTF-8?q?Magnus=20Gro=C3=9F?= <magnus.gross@rwth-aachen.de>
> > Date: Wed, 26 Jan 2022 16:35:07 +0100
> > Subject: [PATCH] elf: Relax assumptions about vaddr ordering
> > MIME-Version: 1.0
> > Content-Type: text/plain; charset=UTF-8
> > Content-Transfer-Encoding: 8bit
> > 
> > Commit 5f501d555653 ("binfmt_elf: reintroduce using
> > MAP_FIXED_NOREPLACE") introduced a regression, where the kernel now
> > assumes that PT_LOAD segments are ordered by vaddr in load_elf_binary().
> > 
> > Specifically consider an ELF binary with the following PT_LOAD segments:
> > 
> > Type  Offset   VirtAddr   PhysAddr   FileSiz  MemSiz    Flg Align
> > LOAD  0x000000 0x08000000 0x08000000 0x474585 0x474585  R E 0x1000
> > LOAD  0x475000 0x08475000 0x08475000 0x090a4  0xc6c10   RW  0x1000
> > LOAD  0x47f000 0x00010000 0x00010000 0x00000  0x7ff0000     0x1000
> > 
> > Note how the last segment is actually the first segment and vice versa.
> > 
> > Since total_mapping_size() only computes the difference between the
> > first and the last segment in the order that they appear, it will return
> > a size of 0 in this case, thus causing load_elf_binary() to fail, which
> > did not happen before that change.
> > 
> > Strictly speaking total_mapping_size() made that assumption already
> > before that patch, but the issue did not appear because the old
> > load_addr_set guards never allowed this call to total_mapping_size().
> > 
> > Instead of fixing this by reverting to the old load_addr_set logic, we
> > fix this by comparing the correct first and last segments in
> > total_mapping_size().
> 
> Ah, nice. Yeah, this is good.
> 
> > Signed-off-by: Magnus Groß <magnus.gross@rwth-aachen.de>
> 
> Fixes: 5f501d555653 ("binfmt_elf: reintroduce using MAP_FIXED_NOREPLACE")
> Cc: stable@vger.kernel.org
> Acked-by: Kees Cook <keescook@chromium.org>

Andrew, can you pick this up too?

-Kees

> 
> -Kees
> 
> > ---
> >  fs/binfmt_elf.c | 18 ++++++++++++++----
> >  1 file changed, 14 insertions(+), 4 deletions(-)
> > 
> > diff --git a/fs/binfmt_elf.c b/fs/binfmt_elf.c
> > index f8c7f26f1fbb..0caaad9eddd1 100644
> > --- a/fs/binfmt_elf.c
> > +++ b/fs/binfmt_elf.c
> > @@ -402,19 +402,29 @@ static unsigned long elf_map(struct file *filep, unsigned long addr,
> >  static unsigned long total_mapping_size(const struct elf_phdr *cmds, int nr)
> >  {
> >  	int i, first_idx = -1, last_idx = -1;
> > +	unsigned long min_vaddr = ULONG_MAX, max_vaddr = 0;
> >  
> >  	for (i = 0; i < nr; i++) {
> >  		if (cmds[i].p_type == PT_LOAD) {
> > -			last_idx = i;
> > -			if (first_idx == -1)
> > +			/*
> > +			 * The PT_LOAD segments are not necessarily ordered
> > +			 * by vaddr. Make sure that we get the segment with
> > +			 * minimum vaddr (maximum vaddr respectively)
> > +			 */
> > +			if (cmds[i].p_vaddr <= min_vaddr) {
> >  				first_idx = i;
> > +				min_vaddr = cmds[i].p_vaddr;
> > +			}
> > +			if (cmds[i].p_vaddr >= max_vaddr) {
> > +				last_idx = i;
> > +				max_vaddr = cmds[i].p_vaddr;
> > +			}
> >  		}
> >  	}
> >  	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 max_vaddr + cmds[last_idx].p_memsz - ELF_PAGESTART(min_vaddr);
> >  }
> >  
> >  static int elf_read(struct file *file, void *buf, size_t len, loff_t pos)
> > -- 
> > 2.34.1
> 
> -- 
> Kees Cook

-- 
Kees Cook

Re: [PATCH] elf: Relax assumptions about vaddr ordering

[Magnus Groß]

On Wed, Jan 26, 2022 at 10:31:42PM -0800 Kees Cook wrote:
> On Wed, Jan 26, 2022 at 08:50:15AM -0800, Kees Cook wrote:
> > On Wed, Jan 26, 2022 at 05:25:20PM +0100, Magnus Groß wrote:
> > > From ff4dde97e82727727bda711f2367c05663498b24 Mon Sep 17 00:00:00 2001
> > > From: =?UTF-8?q?Magnus=20Gro=C3=9F?= <magnus.gross@rwth-aachen.de>
> > > Date: Wed, 26 Jan 2022 16:35:07 +0100
> > > Subject: [PATCH] elf: Relax assumptions about vaddr ordering
> > > MIME-Version: 1.0
> > > Content-Type: text/plain; charset=UTF-8
> > > Content-Transfer-Encoding: 8bit
> > > 
> > > Commit 5f501d555653 ("binfmt_elf: reintroduce using
> > > MAP_FIXED_NOREPLACE") introduced a regression, where the kernel now
> > > assumes that PT_LOAD segments are ordered by vaddr in load_elf_binary().
> > > 
> > > Specifically consider an ELF binary with the following PT_LOAD segments:
> > > 
> > > Type  Offset   VirtAddr   PhysAddr   FileSiz  MemSiz    Flg Align
> > > LOAD  0x000000 0x08000000 0x08000000 0x474585 0x474585  R E 0x1000
> > > LOAD  0x475000 0x08475000 0x08475000 0x090a4  0xc6c10   RW  0x1000
> > > LOAD  0x47f000 0x00010000 0x00010000 0x00000  0x7ff0000     0x1000
> > > 
> > > Note how the last segment is actually the first segment and vice versa.
> > > 
> > > Since total_mapping_size() only computes the difference between the
> > > first and the last segment in the order that they appear, it will return
> > > a size of 0 in this case, thus causing load_elf_binary() to fail, which
> > > did not happen before that change.
> > > 
> > > Strictly speaking total_mapping_size() made that assumption already
> > > before that patch, but the issue did not appear because the old
> > > load_addr_set guards never allowed this call to total_mapping_size().
> > > 
> > > Instead of fixing this by reverting to the old load_addr_set logic, we
> > > fix this by comparing the correct first and last segments in
> > > total_mapping_size().
> > 
> > Ah, nice. Yeah, this is good.
> > 
> > > Signed-off-by: Magnus Groß <magnus.gross@rwth-aachen.de>
> > 
> > Fixes: 5f501d555653 ("binfmt_elf: reintroduce using MAP_FIXED_NOREPLACE")
> > Cc: stable@vger.kernel.org
> > Acked-by: Kees Cook <keescook@chromium.org>
> 
> Andrew, can you pick this up too?
> 
> -Kees
> 

May I also propose to include this patch in whatever mailing-list
corresponds to the 5.16.x bugfix series?
It turns out that almost all native Linux games published by the Virtual
Programming company have this kind of weird PT_LOAD ordering including
the famous Bioshock Infinite, so right now those games are all
completely broken since Linux 5.16.

P.S.: Someone should probably ask Virtual Programming, what kind of
tooling they use to create such convoluted ELF binaries.

> > 
> > -Kees
> > 
> > > ---
> > >  fs/binfmt_elf.c | 18 ++++++++++++++----
> > >  1 file changed, 14 insertions(+), 4 deletions(-)
> > > 
> > > diff --git a/fs/binfmt_elf.c b/fs/binfmt_elf.c
> > > index f8c7f26f1fbb..0caaad9eddd1 100644
> > > --- a/fs/binfmt_elf.c
> > > +++ b/fs/binfmt_elf.c
> > > @@ -402,19 +402,29 @@ static unsigned long elf_map(struct file *filep, unsigned long addr,
> > >  static unsigned long total_mapping_size(const struct elf_phdr *cmds, int nr)
> > >  {
> > >  	int i, first_idx = -1, last_idx = -1;
> > > +	unsigned long min_vaddr = ULONG_MAX, max_vaddr = 0;
> > >  
> > >  	for (i = 0; i < nr; i++) {
> > >  		if (cmds[i].p_type == PT_LOAD) {
> > > -			last_idx = i;
> > > -			if (first_idx == -1)
> > > +			/*
> > > +			 * The PT_LOAD segments are not necessarily ordered
> > > +			 * by vaddr. Make sure that we get the segment with
> > > +			 * minimum vaddr (maximum vaddr respectively)
> > > +			 */
> > > +			if (cmds[i].p_vaddr <= min_vaddr) {
> > >  				first_idx = i;
> > > +				min_vaddr = cmds[i].p_vaddr;
> > > +			}
> > > +			if (cmds[i].p_vaddr >= max_vaddr) {
> > > +				last_idx = i;
> > > +				max_vaddr = cmds[i].p_vaddr;
> > > +			}
> > >  		}
> > >  	}
> > >  	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 max_vaddr + cmds[last_idx].p_memsz - ELF_PAGESTART(min_vaddr);
> > >  }
> > >  
> > >  static int elf_read(struct file *file, void *buf, size_t len, loff_t pos)
> > > -- 
> > > 2.34.1
> > 
> > -- 
> > Kees Cook
> 
> -- 
> Kees Cook

Re: [PATCH] elf: Relax assumptions about vaddr ordering

[Kees Cook]

On Fri, Jan 28, 2022 at 09:26:09AM +0100, Magnus Groß wrote:
> On Wed, Jan 26, 2022 at 10:31:42PM -0800 Kees Cook wrote:
> > On Wed, Jan 26, 2022 at 08:50:15AM -0800, Kees Cook wrote:
> > > On Wed, Jan 26, 2022 at 05:25:20PM +0100, Magnus Groß wrote:
> > > > From ff4dde97e82727727bda711f2367c05663498b24 Mon Sep 17 00:00:00 2001
> > > > From: =?UTF-8?q?Magnus=20Gro=C3=9F?= <magnus.gross@rwth-aachen.de>
> > > > Date: Wed, 26 Jan 2022 16:35:07 +0100
> > > > Subject: [PATCH] elf: Relax assumptions about vaddr ordering
> > > > MIME-Version: 1.0
> > > > Content-Type: text/plain; charset=UTF-8
> > > > Content-Transfer-Encoding: 8bit
> > > > 
> > > > Commit 5f501d555653 ("binfmt_elf: reintroduce using
> > > > MAP_FIXED_NOREPLACE") introduced a regression, where the kernel now
> > > > assumes that PT_LOAD segments are ordered by vaddr in load_elf_binary().
> > > > 
> > > > Specifically consider an ELF binary with the following PT_LOAD segments:
> > > > 
> > > > Type  Offset   VirtAddr   PhysAddr   FileSiz  MemSiz    Flg Align
> > > > LOAD  0x000000 0x08000000 0x08000000 0x474585 0x474585  R E 0x1000
> > > > LOAD  0x475000 0x08475000 0x08475000 0x090a4  0xc6c10   RW  0x1000
> > > > LOAD  0x47f000 0x00010000 0x00010000 0x00000  0x7ff0000     0x1000
> > > > 
> > > > Note how the last segment is actually the first segment and vice versa.
> > > > 
> > > > Since total_mapping_size() only computes the difference between the
> > > > first and the last segment in the order that they appear, it will return
> > > > a size of 0 in this case, thus causing load_elf_binary() to fail, which
> > > > did not happen before that change.
> > > > 
> > > > Strictly speaking total_mapping_size() made that assumption already
> > > > before that patch, but the issue did not appear because the old
> > > > load_addr_set guards never allowed this call to total_mapping_size().
> > > > 
> > > > Instead of fixing this by reverting to the old load_addr_set logic, we
> > > > fix this by comparing the correct first and last segments in
> > > > total_mapping_size().
> > > 
> > > Ah, nice. Yeah, this is good.
> > > 
> > > > Signed-off-by: Magnus Groß <magnus.gross@rwth-aachen.de>
> > > 
> > > Fixes: 5f501d555653 ("binfmt_elf: reintroduce using MAP_FIXED_NOREPLACE")
> > > Cc: stable@vger.kernel.org
> > > Acked-by: Kees Cook <keescook@chromium.org>
> > 
> > Andrew, can you pick this up too?
> > 
> > -Kees
> > 
> 
> May I also propose to include this patch in whatever mailing-list
> corresponds to the 5.16.x bugfix series?
> It turns out that almost all native Linux games published by the Virtual
> Programming company have this kind of weird PT_LOAD ordering including
> the famous Bioshock Infinite, so right now those games are all
> completely broken since Linux 5.16.

Thanks for additional rationale!

I included the field that would be expected to have this picked up for
the 5.16 stable tree (the "Fixes: ..." and "Cc: stable@vger.kernel.org")
so once it lands in Linus's tree, it'll get picked up for the v5.16.z
series too.

> P.S.: Someone should probably ask Virtual Programming, what kind of
> tooling they use to create such convoluted ELF binaries.

Does "strings" provide any hints? :)

-- 
Kees Cook

Re: [PATCH] elf: Relax assumptions about vaddr ordering

[Kees Cook]

On Fri, Jan 28, 2022 at 09:26:09AM +0100, Magnus Groß wrote:
> On Wed, Jan 26, 2022 at 10:31:42PM -0800 Kees Cook wrote:
> > On Wed, Jan 26, 2022 at 08:50:15AM -0800, Kees Cook wrote:
> > > On Wed, Jan 26, 2022 at 05:25:20PM +0100, Magnus Groß wrote:
> > > > From ff4dde97e82727727bda711f2367c05663498b24 Mon Sep 17 00:00:00 2001
> > > > From: =?UTF-8?q?Magnus=20Gro=C3=9F?= <magnus.gross@rwth-aachen.de>
> > > > Date: Wed, 26 Jan 2022 16:35:07 +0100
> > > > Subject: [PATCH] elf: Relax assumptions about vaddr ordering
> > > > MIME-Version: 1.0
> > > > Content-Type: text/plain; charset=UTF-8
> > > > Content-Transfer-Encoding: 8bit
> > > > 
> > > > Commit 5f501d555653 ("binfmt_elf: reintroduce using
> > > > MAP_FIXED_NOREPLACE") introduced a regression, where the kernel now
> > > > assumes that PT_LOAD segments are ordered by vaddr in load_elf_binary().
> > > > 
> > > > Specifically consider an ELF binary with the following PT_LOAD segments:
> > > > 
> > > > Type  Offset   VirtAddr   PhysAddr   FileSiz  MemSiz    Flg Align
> > > > LOAD  0x000000 0x08000000 0x08000000 0x474585 0x474585  R E 0x1000
> > > > LOAD  0x475000 0x08475000 0x08475000 0x090a4  0xc6c10   RW  0x1000
> > > > LOAD  0x47f000 0x00010000 0x00010000 0x00000  0x7ff0000     0x1000
> > > > 
> > > > Note how the last segment is actually the first segment and vice versa.
> > > > 
> > > > Since total_mapping_size() only computes the difference between the
> > > > first and the last segment in the order that they appear, it will return
> > > > a size of 0 in this case, thus causing load_elf_binary() to fail, which
> > > > did not happen before that change.
> > > > 
> > > > Strictly speaking total_mapping_size() made that assumption already
> > > > before that patch, but the issue did not appear because the old
> > > > load_addr_set guards never allowed this call to total_mapping_size().
> > > > 
> > > > Instead of fixing this by reverting to the old load_addr_set logic, we
> > > > fix this by comparing the correct first and last segments in
> > > > total_mapping_size().
> > > 
> > > Ah, nice. Yeah, this is good.
> > > 
> > > > Signed-off-by: Magnus Groß <magnus.gross@rwth-aachen.de>
> > > 
> > > Fixes: 5f501d555653 ("binfmt_elf: reintroduce using MAP_FIXED_NOREPLACE")
> > > Cc: stable@vger.kernel.org
> > > Acked-by: Kees Cook <keescook@chromium.org>
> > 
> > Andrew, can you pick this up too?
> > 
> > -Kees
> > 
> 
> May I also propose to include this patch in whatever mailing-list
> corresponds to the 5.16.x bugfix series?
> It turns out that almost all native Linux games published by the Virtual
> Programming company have this kind of weird PT_LOAD ordering including
> the famous Bioshock Infinite, so right now those games are all
> completely broken since Linux 5.16.
> 
> P.S.: Someone should probably ask Virtual Programming, what kind of
> tooling they use to create such convoluted ELF binaries.

Oh, actually, this was independently fixed:
https://lore.kernel.org/all/YVmd7D0M6G/DcP4O@localhost.localdomain/

Alexey, you never answered by question about why we can't use a proper
type and leave the ELF_PAGESTART() macros alone:
https://lore.kernel.org/all/202110071038.B589687@keescook/

I still don't like the use of "int" in ELF_PAGESTART(), but I agree
it shouldn't cause a problem. I just really don't like mixing a signed
type with address calculations, from a robustness perspective.

Andrew, can you update elf-fix-overflow-in-total-mapping-size-calculation.patch
to include:

Fixes: 5f501d555653 ("binfmt_elf: reintroduce using MAP_FIXED_NOREPLACE")
Cc: stable@vger.kernel.org
Acked-by: Kees Cook <keescook@chromium.org>

Thanks!

-Kees

> 
> > > 
> > > -Kees
> > > 
> > > > ---
> > > >  fs/binfmt_elf.c | 18 ++++++++++++++----
> > > >  1 file changed, 14 insertions(+), 4 deletions(-)
> > > > 
> > > > diff --git a/fs/binfmt_elf.c b/fs/binfmt_elf.c
> > > > index f8c7f26f1fbb..0caaad9eddd1 100644
> > > > --- a/fs/binfmt_elf.c
> > > > +++ b/fs/binfmt_elf.c
> > > > @@ -402,19 +402,29 @@ static unsigned long elf_map(struct file *filep, unsigned long addr,
> > > >  static unsigned long total_mapping_size(const struct elf_phdr *cmds, int nr)
> > > >  {
> > > >  	int i, first_idx = -1, last_idx = -1;
> > > > +	unsigned long min_vaddr = ULONG_MAX, max_vaddr = 0;
> > > >  
> > > >  	for (i = 0; i < nr; i++) {
> > > >  		if (cmds[i].p_type == PT_LOAD) {
> > > > -			last_idx = i;
> > > > -			if (first_idx == -1)
> > > > +			/*
> > > > +			 * The PT_LOAD segments are not necessarily ordered
> > > > +			 * by vaddr. Make sure that we get the segment with
> > > > +			 * minimum vaddr (maximum vaddr respectively)
> > > > +			 */
> > > > +			if (cmds[i].p_vaddr <= min_vaddr) {
> > > >  				first_idx = i;
> > > > +				min_vaddr = cmds[i].p_vaddr;
> > > > +			}
> > > > +			if (cmds[i].p_vaddr >= max_vaddr) {
> > > > +				last_idx = i;
> > > > +				max_vaddr = cmds[i].p_vaddr;
> > > > +			}
> > > >  		}
> > > >  	}
> > > >  	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 max_vaddr + cmds[last_idx].p_memsz - ELF_PAGESTART(min_vaddr);
> > > >  }
> > > >  
> > > >  static int elf_read(struct file *file, void *buf, size_t len, loff_t pos)
> > > > -- 
> > > > 2.34.1
> > > 
> > > -- 
> > > Kees Cook
> > 
> > -- 
> > Kees Cook

-- 
Kees Cook

Re: [PATCH] elf: Relax assumptions about vaddr ordering

[Alexey Dobriyan]

On Fri, Jan 28, 2022 at 02:30:12PM -0800, Kees Cook wrote:
> On Fri, Jan 28, 2022 at 09:26:09AM +0100, Magnus Groß wrote:
> > On Wed, Jan 26, 2022 at 10:31:42PM -0800 Kees Cook wrote:
> > > On Wed, Jan 26, 2022 at 08:50:15AM -0800, Kees Cook wrote:
> > > > On Wed, Jan 26, 2022 at 05:25:20PM +0100, Magnus Groß wrote:
> > > > > From ff4dde97e82727727bda711f2367c05663498b24 Mon Sep 17 00:00:00 2001
> > > > > From: =?UTF-8?q?Magnus=20Gro=C3=9F?= <magnus.gross@rwth-aachen.de>
> > > > > Date: Wed, 26 Jan 2022 16:35:07 +0100
> > > > > Subject: [PATCH] elf: Relax assumptions about vaddr ordering
> > > > > MIME-Version: 1.0
> > > > > Content-Type: text/plain; charset=UTF-8
> > > > > Content-Transfer-Encoding: 8bit
> > > > > 
> > > > > Commit 5f501d555653 ("binfmt_elf: reintroduce using
> > > > > MAP_FIXED_NOREPLACE") introduced a regression, where the kernel now
> > > > > assumes that PT_LOAD segments are ordered by vaddr in load_elf_binary().
> > > > > 
> > > > > Specifically consider an ELF binary with the following PT_LOAD segments:
> > > > > 
> > > > > Type  Offset   VirtAddr   PhysAddr   FileSiz  MemSiz    Flg Align
> > > > > LOAD  0x000000 0x08000000 0x08000000 0x474585 0x474585  R E 0x1000
> > > > > LOAD  0x475000 0x08475000 0x08475000 0x090a4  0xc6c10   RW  0x1000
> > > > > LOAD  0x47f000 0x00010000 0x00010000 0x00000  0x7ff0000     0x1000
> > > > > 
> > > > > Note how the last segment is actually the first segment and vice versa.
> > > > > 
> > > > > Since total_mapping_size() only computes the difference between the
> > > > > first and the last segment in the order that they appear, it will return
> > > > > a size of 0 in this case, thus causing load_elf_binary() to fail, which
> > > > > did not happen before that change.
> > > > > 
> > > > > Strictly speaking total_mapping_size() made that assumption already
> > > > > before that patch, but the issue did not appear because the old
> > > > > load_addr_set guards never allowed this call to total_mapping_size().
> > > > > 
> > > > > Instead of fixing this by reverting to the old load_addr_set logic, we
> > > > > fix this by comparing the correct first and last segments in
> > > > > total_mapping_size().
> > > > 
> > > > Ah, nice. Yeah, this is good.
> > > > 
> > > > > Signed-off-by: Magnus Groß <magnus.gross@rwth-aachen.de>
> > > > 
> > > > Fixes: 5f501d555653 ("binfmt_elf: reintroduce using MAP_FIXED_NOREPLACE")
> > > > Cc: stable@vger.kernel.org
> > > > Acked-by: Kees Cook <keescook@chromium.org>
> > > 
> > > Andrew, can you pick this up too?
> > > 
> > > -Kees
> > > 
> > 
> > May I also propose to include this patch in whatever mailing-list
> > corresponds to the 5.16.x bugfix series?
> > It turns out that almost all native Linux games published by the Virtual
> > Programming company have this kind of weird PT_LOAD ordering including
> > the famous Bioshock Infinite, so right now those games are all
> > completely broken since Linux 5.16.
> > 
> > P.S.: Someone should probably ask Virtual Programming, what kind of
> > tooling they use to create such convoluted ELF binaries.
> 
> Oh, actually, this was independently fixed:
> https://lore.kernel.org/all/YVmd7D0M6G/DcP4O@localhost.localdomain/

Oh wow, I accidently fixed real bug.

> Alexey, you never answered by question about why we can't use a proper
> type and leave the ELF_PAGESTART() macros alone:
> https://lore.kernel.org/all/202110071038.B589687@keescook/
> 
> I still don't like the use of "int" in ELF_PAGESTART(), but I agree
> it shouldn't cause a problem. I just really don't like mixing a signed
> type with address calculations, from a robustness perspective.

It is very robust. There are 2 ways to mask pointers

	unsigned long & ~(unsigned long)-1

	or

	unsigned long & ~(int)-1

Both work. Second variant works for uint32_t too.

As I wrote in that thread, this macro

	#define ELF_PAGESTART(_v) ((_v) & ~(unsigned long)(ELF_MIN_ALIGN-1))

is slightly incorrect because type of the expression can be (unsigned long)
but it logically should be typeof(v). Now fixing by switching to ALIGN
doesn't do anything because ALIGN has the same problem.
And fixing ALIGN requires to go through thousands of usages, which is
way too much for one localised ELF fix.

	PT_ALEXEY

Re: [PATCH] elf: Relax assumptions about vaddr ordering

[Magnus Groß]

On Fri, Jan 28, 2022 at 02:30:12PM -0800 Kees Cook wrote:
> On Fri, Jan 28, 2022 at 09:26:09AM +0100, Magnus Groß wrote:
> > On Wed, Jan 26, 2022 at 10:31:42PM -0800 Kees Cook wrote:
> > > On Wed, Jan 26, 2022 at 08:50:15AM -0800, Kees Cook wrote:
> > > > On Wed, Jan 26, 2022 at 05:25:20PM +0100, Magnus Groß wrote:
> > > > > From ff4dde97e82727727bda711f2367c05663498b24 Mon Sep 17 00:00:00 2001
> > > > > From: =?UTF-8?q?Magnus=20Gro=C3=9F?= <magnus.gross@rwth-aachen.de>
> > > > > Date: Wed, 26 Jan 2022 16:35:07 +0100
> > > > > Subject: [PATCH] elf: Relax assumptions about vaddr ordering
> > > > > MIME-Version: 1.0
> > > > > Content-Type: text/plain; charset=UTF-8
> > > > > Content-Transfer-Encoding: 8bit
> > > > > 
> > > > > Commit 5f501d555653 ("binfmt_elf: reintroduce using
> > > > > MAP_FIXED_NOREPLACE") introduced a regression, where the kernel now
> > > > > assumes that PT_LOAD segments are ordered by vaddr in load_elf_binary().
> > > > > 
> > > > > Specifically consider an ELF binary with the following PT_LOAD segments:
> > > > > 
> > > > > Type  Offset   VirtAddr   PhysAddr   FileSiz  MemSiz    Flg Align
> > > > > LOAD  0x000000 0x08000000 0x08000000 0x474585 0x474585  R E 0x1000
> > > > > LOAD  0x475000 0x08475000 0x08475000 0x090a4  0xc6c10   RW  0x1000
> > > > > LOAD  0x47f000 0x00010000 0x00010000 0x00000  0x7ff0000     0x1000
> > > > > 
> > > > > Note how the last segment is actually the first segment and vice versa.
> > > > > 
> > > > > Since total_mapping_size() only computes the difference between the
> > > > > first and the last segment in the order that they appear, it will return
> > > > > a size of 0 in this case, thus causing load_elf_binary() to fail, which
> > > > > did not happen before that change.
> > > > > 
> > > > > Strictly speaking total_mapping_size() made that assumption already
> > > > > before that patch, but the issue did not appear because the old
> > > > > load_addr_set guards never allowed this call to total_mapping_size().
> > > > > 
> > > > > Instead of fixing this by reverting to the old load_addr_set logic, we
> > > > > fix this by comparing the correct first and last segments in
> > > > > total_mapping_size().
> > > > 
> > > > Ah, nice. Yeah, this is good.
> > > > 
> > > > > Signed-off-by: Magnus Groß <magnus.gross@rwth-aachen.de>
> > > > 
> > > > Fixes: 5f501d555653 ("binfmt_elf: reintroduce using MAP_FIXED_NOREPLACE")
> > > > Cc: stable@vger.kernel.org
> > > > Acked-by: Kees Cook <keescook@chromium.org>
> > > 
> > > Andrew, can you pick this up too?
> > > 
> > > -Kees
> > > 
> > 
> > May I also propose to include this patch in whatever mailing-list
> > corresponds to the 5.16.x bugfix series?
> > It turns out that almost all native Linux games published by the Virtual
> > Programming company have this kind of weird PT_LOAD ordering including
> > the famous Bioshock Infinite, so right now those games are all
> > completely broken since Linux 5.16.
> > 
> > P.S.: Someone should probably ask Virtual Programming, what kind of
> > tooling they use to create such convoluted ELF binaries.
> 
> Oh, actually, this was independently fixed:
> https://lore.kernel.org/all/YVmd7D0M6G/DcP4O@localhost.localdomain/
> 
> Alexey, you never answered by question about why we can't use a proper
> type and leave the ELF_PAGESTART() macros alone:
> https://lore.kernel.org/all/202110071038.B589687@keescook/

Oh sorry, I didn't see that there was already a patch floating around
that fixed the issue, otherwise I would have not wasted so much time on
debugging this.
Oh well, doesn't matter now, I still learned a lot about kernel
development and debugging with kgdb, I will probably be able to make
some use of that knowledge in the future for another kernel patch.

> > P.S.: Someone should probably ask Virtual Programming, what kind of
> > tooling they use to create such convoluted ELF binaries.
> 
> Does "strings" provide any hints? :)

It seems to be crosstool-ng
(https://github.com/crosstool-ng/crosstool-ng):

readelf -p .comment bioshock.i386

String dump of section '.comment':
[  0]  GCC: (crosstool-NG 1.17.0) 4.6.3
[ 21]  GCC: (Ubuntu 4.9.1-16ubuntu6) 4.9.1
[ 45]  GCC: (Ubuntu 4.8.2-19ubuntu1) 4.8.2


Not sure though if crosstool-ng outputs these weird ELF binaries in
general or if it's just a bug.

--
Magnus

> > 
> > > > 
> > > > -Kees
> > > > 
> > > > > ---
> > > > >  fs/binfmt_elf.c | 18 ++++++++++++++----
> > > > >  1 file changed, 14 insertions(+), 4 deletions(-)
> > > > > 
> > > > > diff --git a/fs/binfmt_elf.c b/fs/binfmt_elf.c
> > > > > index f8c7f26f1fbb..0caaad9eddd1 100644
> > > > > --- a/fs/binfmt_elf.c
> > > > > +++ b/fs/binfmt_elf.c
> > > > > @@ -402,19 +402,29 @@ static unsigned long elf_map(struct file *filep, unsigned long addr,
> > > > >  static unsigned long total_mapping_size(const struct elf_phdr *cmds, int nr)
> > > > >  {
> > > > >  	int i, first_idx = -1, last_idx = -1;
> > > > > +	unsigned long min_vaddr = ULONG_MAX, max_vaddr = 0;
> > > > >  
> > > > >  	for (i = 0; i < nr; i++) {
> > > > >  		if (cmds[i].p_type == PT_LOAD) {
> > > > > -			last_idx = i;
> > > > > -			if (first_idx == -1)
> > > > > +			/*
> > > > > +			 * The PT_LOAD segments are not necessarily ordered
> > > > > +			 * by vaddr. Make sure that we get the segment with
> > > > > +			 * minimum vaddr (maximum vaddr respectively)
> > > > > +			 */
> > > > > +			if (cmds[i].p_vaddr <= min_vaddr) {
> > > > >  				first_idx = i;
> > > > > +				min_vaddr = cmds[i].p_vaddr;
> > > > > +			}
> > > > > +			if (cmds[i].p_vaddr >= max_vaddr) {
> > > > > +				last_idx = i;
> > > > > +				max_vaddr = cmds[i].p_vaddr;
> > > > > +			}
> > > > >  		}
> > > > >  	}
> > > > >  	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 max_vaddr + cmds[last_idx].p_memsz - ELF_PAGESTART(min_vaddr);
> > > > >  }
> > > > >  
> > > > >  static int elf_read(struct file *file, void *buf, size_t len, loff_t pos)
> > > > > -- 
> > > > > 2.34.1
> > > > 
> > > > -- 
> > > > Kees Cook
> > > 
> > > -- 
> > > Kees Cook
> 
> -- 
> Kees Cook

Re: [PATCH] elf: Relax assumptions about vaddr ordering

[Andrew Morton]

On Fri, 28 Jan 2022 14:30:12 -0800 Kees Cook <keescook@chromium.org> wrote:

> Andrew, can you update elf-fix-overflow-in-total-mapping-size-calculation.patch
> to include:
> 
> Fixes: 5f501d555653 ("binfmt_elf: reintroduce using MAP_FIXED_NOREPLACE")
> Cc: stable@vger.kernel.org
> Acked-by: Kees Cook <keescook@chromium.org>

Done.

I'm taking it that we can omit this patch ("elf: Relax assumptions
about vaddr ordering") and that Alexey's "ELF: fix overflow in total
mapping size calculation" will suffice?

Re: [PATCH] elf: Relax assumptions about vaddr ordering

[Kees Cook]

On Tue, Feb 01, 2022 at 02:48:16PM -0800, Andrew Morton wrote:
> On Fri, 28 Jan 2022 14:30:12 -0800 Kees Cook <keescook@chromium.org> wrote:
> 
> > Andrew, can you update elf-fix-overflow-in-total-mapping-size-calculation.patch
> > to include:
> > 
> > Fixes: 5f501d555653 ("binfmt_elf: reintroduce using MAP_FIXED_NOREPLACE")
> > Cc: stable@vger.kernel.org
> > Acked-by: Kees Cook <keescook@chromium.org>
> 
> Done.
> 
> I'm taking it that we can omit this patch ("elf: Relax assumptions
> about vaddr ordering") and that Alexey's "ELF: fix overflow in total
> mapping size calculation" will suffice?

Yes, it has the same result. Thanks!

-- 
Kees Cook

Re: [PATCH] elf: Relax assumptions about vaddr ordering

[Alexey Dobriyan]

On Tue, Feb 01, 2022 at 02:48:16PM -0800, Andrew Morton wrote:
> On Fri, 28 Jan 2022 14:30:12 -0800 Kees Cook <keescook@chromium.org> wrote:
> 
> > Andrew, can you update elf-fix-overflow-in-total-mapping-size-calculation.patch
> > to include:
> > 
> > Fixes: 5f501d555653 ("binfmt_elf: reintroduce using MAP_FIXED_NOREPLACE")
> > Cc: stable@vger.kernel.org
> > Acked-by: Kees Cook <keescook@chromium.org>
> 
> Done.
> 
> I'm taking it that we can omit this patch ("elf: Relax assumptions
> about vaddr ordering") and that Alexey's "ELF: fix overflow in total
> mapping size calculation" will suffice?

Yes, it is same patch conceptually.
It should work, but those who can't play Bioshock are better test it.

Re: [PATCH] elf: Relax assumptions about vaddr ordering

[Magnus Groß]

Am Wed, Feb 02, 2022 at 06:15:58PM +0300 schrieb Alexey Dobriyan:
> On Tue, Feb 01, 2022 at 02:48:16PM -0800, Andrew Morton wrote:
> > On Fri, 28 Jan 2022 14:30:12 -0800 Kees Cook <keescook@chromium.org> wrote:
> > 
> > > Andrew, can you update elf-fix-overflow-in-total-mapping-size-calculation.patch
> > > to include:
> > > 
> > > Fixes: 5f501d555653 ("binfmt_elf: reintroduce using MAP_FIXED_NOREPLACE")
> > > Cc: stable@vger.kernel.org
> > > Acked-by: Kees Cook <keescook@chromium.org>
> > 
> > Done.
> > 
> > I'm taking it that we can omit this patch ("elf: Relax assumptions
> > about vaddr ordering") and that Alexey's "ELF: fix overflow in total
> > mapping size calculation" will suffice?
> 
> Yes, it is same patch conceptually.
> It should work, but those who can't play Bioshock are better test it.

Yes it works.

Although the change from unsigned int to int is not necessary in the
first place, as you can avoid the -1 initialization for min_addr by
simply using ULONG_MAX, as can be seen in my patch.

Re: [PATCH] elf: Relax assumptions about vaddr ordering

[Andrew Morton]

On Wed, 26 Jan 2022 22:31:42 -0800 Kees Cook <keescook@chromium.org> wrote:

> On Wed, Jan 26, 2022 at 08:50:15AM -0800, Kees Cook wrote:
> > On Wed, Jan 26, 2022 at 05:25:20PM +0100, Magnus Groß wrote:
> > > From ff4dde97e82727727bda711f2367c05663498b24 Mon Sep 17 00:00:00 2001
> > > From: =?UTF-8?q?Magnus=20Gro=C3=9F?= <magnus.gross@rwth-aachen.de>
> > > Date: Wed, 26 Jan 2022 16:35:07 +0100
> > > Subject: [PATCH] elf: Relax assumptions about vaddr ordering
> > > MIME-Version: 1.0
> > > Content-Type: text/plain; charset=UTF-8
> > > Content-Transfer-Encoding: 8bit
> > > 
> > > Commit 5f501d555653 ("binfmt_elf: reintroduce using
> > > MAP_FIXED_NOREPLACE") introduced a regression, where the kernel now
> > > assumes that PT_LOAD segments are ordered by vaddr in load_elf_binary().
> > > 
> > > Specifically consider an ELF binary with the following PT_LOAD segments:
> > > 
> > > Type  Offset   VirtAddr   PhysAddr   FileSiz  MemSiz    Flg Align
> > > LOAD  0x000000 0x08000000 0x08000000 0x474585 0x474585  R E 0x1000
> > > LOAD  0x475000 0x08475000 0x08475000 0x090a4  0xc6c10   RW  0x1000
> > > LOAD  0x47f000 0x00010000 0x00010000 0x00000  0x7ff0000     0x1000
> > > 
> > > Note how the last segment is actually the first segment and vice versa.
> > > 
> > > Since total_mapping_size() only computes the difference between the
> > > first and the last segment in the order that they appear, it will return
> > > a size of 0 in this case, thus causing load_elf_binary() to fail, which
> > > did not happen before that change.
> > > 
> > > Strictly speaking total_mapping_size() made that assumption already
> > > before that patch, but the issue did not appear because the old
> > > load_addr_set guards never allowed this call to total_mapping_size().
> > > 
> > > Instead of fixing this by reverting to the old load_addr_set logic, we
> > > fix this by comparing the correct first and last segments in
> > > total_mapping_size().
> > 
> > Ah, nice. Yeah, this is good.
> > 
> > > Signed-off-by: Magnus Groß <magnus.gross@rwth-aachen.de>
> > 
> > Fixes: 5f501d555653 ("binfmt_elf: reintroduce using MAP_FIXED_NOREPLACE")
> > Cc: stable@vger.kernel.org
> > Acked-by: Kees Cook <keescook@chromium.org>
> 
> Andrew, can you pick this up too?
> 

It conflicts significantly with Alexey's "ELF: fix overflow in total
mapping size calculation".