Curiosity around 'exec_id' and some problems associated with it

Problems:
I. The "exit_notify" function in the Linux kernel does not
sufficiently restrict exit signals
II. Preserve references to the "old" / dead process' VM via
file descriptor

Author:               Adam Zabrocki (<[email protected]>)
Date:                 September 1999 - March 2020

Description:

In 2009 Oleg Nesterov discovered that Linux kernel has an incorrect logic to reset ->exit_signal. As a result, the malicious user can bypass it if it execs the setuid application before exiting (->exit_signal won't be reset to SIGCHLD). His original message can be found here:

https://marc.info/?l=linux-kernel&m=123560588713763&w=2

CVE-2009-1337 was assigned to track this issue. More information about this bug can be found here:

https://www.cvedetails.com/cve/CVE-2009-1337/

Patch:

https://lore.kernel.org/patchwork/patch/150993/

The logic responsible for handling ->exit_signal has been changed a few times and the current logic is locked down since Linux kernel 3.3.5. However, it is not fully robust and it's still possible for the malicious user to bypass it. Basically, it's possible to send arbitrary signals to a privileged (suidroot) parent process (Problem I.). Nevertheless, it's not trivial and more limited comparing to the CVE-2009-1337.

Details (Problem I.):

    When process dies function do_exit() -> exit_notify() from "kernel/exit.c"

is called:

"kernel/exit.c"
static void exit_notify(struct task_struct *tsk, int group_dead)

{
        ...
        tsk->exit_state = EXIT_ZOMBIE;
        if (unlikely(tsk->ptrace)) {
        ...
        } else if (thread_group_leader(tsk)) {
                autoreap = thread_group_empty(tsk) &&
                        do_notify_parent(tsk, tsk->exit_signal);
        } else {
        ...
    }
    ...
}

To be able to inform that child process died, do_notify_parent() from "kernel/signal.c" is executed:

"kernel/signal.c"
bool do_notify_parent(struct task_struct *tsk, int sig)

{
        ...
        if (sig != SIGCHLD) {
                /*
                 * This is only possible if parent == real_parent.
                 * Check if it has changed security domain.
                 */
                if (tsk->parent_exec_id != tsk->parent->self_exec_id)
                        sig = SIGCHLD;
        }
        ...
        if (valid_signal(sig) && sig)
                __group_send_sig_info(sig, &info, tsk->parent);
        ...
}

It is possible for the child process to send to the parent process any signal only when they run within the same security domain. If parent or child process are not in the same domain, kernel will overwrite signal with SIGCHLD value.

However, this check is weak. It is possible for the malicious user to cause an integer overflow for the value tsk->parent->self_exec_id and bypass this validation.

Both values, self_exec_id and parent_exec_id are defined in the "task_struct" structure in file "include/linux/sched.h":

"include/linux/sched.h"

struct task_struct {
        ...
        /* Thread group tracking: */
        u32                             parent_exec_id;
        u32                             self_exec_id;
        ...
}

Linux kernel defines "u32" as "unsigned int" type, which most of the modern compiler's data model defines as a 32 bits value.

Some curiosities which are interesting to point out:

1) Linus Torvalds in 2012 suspected that such 'overflow' might be possible. You can read more about it here:

https://www.openwall.com/lists/kernel-hardening/2012/03/11/4

2) Solar Designer in 1999(!) was aware about the problem that 'exit_signal' can be abused. The kernel didn't protect it at all at that time. So he came up with the idea to introduce those two counters to deal with that problem. Originally, these counters were defined as "long long" type. However, during the revising between September 14 and September 16, 1999 he switched from "long long" to "int" and introduced integer wraparound handling. His patches were merged to the kernel 2.0.39 and 2.0.40.

3) It is worth to read the Solar Designer's message during the discussion about the fix for the problem CVE-2012-0056 (I'm referencing this problem later in that write-up about "Problem II"):

https://www.openwall.com/lists/kernel-hardening/2012/03/11/12

Exploitability:

To be able to cause an integer overflow on self_exec_id or parent_exec_id,
attacker needs to find a way to precisely control that value from the user-mode. Linux kernel references '*_exec_id' variables just in a few places in the code:

1) Function do_notify_parent() from "kernel/exit.c"
2) Function copy_process() from "kernel/fork.c"
3) Function setup_new_exec() from "fs/exec.c"

Option 1) we already covered. Let's take a look at 2nd case:

"kernel/fork.c"
static __latent_entropy struct task_struct *copy_process(
struct pid *pid,
int trace,
int node,
struct kernel_clone_args *args)

{
        ...
        /* CLONE_PARENT re-uses the old parent */
        if (clone_flags & (CLONE_PARENT|CLONE_THREAD)) {
                p->real_parent = current->real_parent;
                p->parent_exec_id = current->parent_exec_id;
        } else {
                p->real_parent = current;
                p->parent_exec_id = current->self_exec_id;
        }
        ...
}

When mother creates a child process / thread (or in general 'task'), there is a way to semi-control 'parent_exec_id' value by controlling which process will be assigned as a 'real_parent'. To be able to do that, an attacker can pass (or not) a CLONE_PARENT or CLONE_THREAD flag. However, this 'primitive' doesn't directly allow to bypass the checks in do_notify_parent() function.

The only hope is in option 3:

"fs/exec.c"
void setup_new_exec(struct linux_binprm * bprm)

{
        ...
        current->self_exec_id++;
        flush_signal_handlers(current, 0);
}

Whenever current process executes a new binary, kernel increments "self_exec_id" variable. There is no validation on the current value, and malicious user can indirectly set any value for that variable.

However, to be able to bypass validation in do_notify_parent() function, attacker needs to control parent's "self_exec_id":

                if (tsk->parent_exec_id != tsk->parent->self_exec_id)
                        sig = SIGCHLD;

To achieve that, malicious user must:

a) Create a mother process
b) Invoke clone() without CLONE_PARENT neither CLONE_THREAD flag. In such case, a new process will get the same values for "parent_exec_id" and "self_exec_id" as mother process.
c) Mother process executes itself as many times as to be able to overflow own "self_exec_id" value, and set it to the "original self_exec_id" - 1.
d) If desired value is acquired, then mother process executes any SUID privileged binary. By doing that, mother process will run in much higher security domain but the child's "parent_exec_id" will match "tsk->parent->self_exec_id" and that leads to bypass of the validation in do_notify_parent() function.

It is important to note, that beginning from the version 3.3.5, before kernel calls setup_new_exec(), function flush_old_exec -> de_thread() will be executed:

"fs/exec.c"
static int de_thread(struct task_struct *tsk)

{
        ...
no_thread_group:
        /* we have changed execution domain */
        tsk->exit_signal = SIGCHLD;
        ...
}

This function overwrites "exit_signal" to always be SIGCHLD. This means that any "exit_signal" set-up by the mother to the new child process, will be overwriten as soon as child execs.

A few examples:

1) No execve at all

tsk1: mother
,--------------------,

|  self_exec_id = 6  |
| parent_exec_id = 6 |
|   parent = <bash>  |
|   exit_signal =    |
|           SIGCHLD  |
`--------------------`
  ^       |
  |       |
  |       `---> clone(SIGSEGV) --->     tsk2: child
  |                                 ,--------------------,
  |                                 |  self_exec_id = 6  |
  |                                 | parent_exec_id = 6 |
  |                                 |    parent = tsk1   |
  |                                 |   exit_signal =    |
  |                                 |           SIGSEGV  |
  |   original                      `--------------------`
  | "exit_signal"                             |
  |    SIGSEGV                                v
  |                                        exit(...)
  |                                           |
  |                                           v
  |                                    x = tsk2->parent_exec_id = 6
  |                                    y = tsk2->tsk1->self_exec_id = 6
  |                                         x == y
  |                                           |
  |                                           v

^------------------------< Deliver original "exit_signal" (SIGSEGV) >

2) child calls execve

tsk1: mother
,--------------------,

|  self_exec_id = 6  |
| parent_exec_id = 6 |
|   parent = <bash>  |
|   exit_signal =    |
|           SIGCHLD  |
`--------------------`
  ^       |
  |       |
  |       `---> clone(SIGSEGV) --->     tsk2: child
  |                                 ,--------------------,
  |                                 |  self_exec_id = 6  |
  |                                 | parent_exec_id = 6 |
  |                                 |    parent = tsk1   |
  |                                 |   exit_signal =    |
  |                                 |           SIGSEGV  |
  |   original                      `--------------------`
  | "exit_signal"                             |
  |    SIGCHLD                                v
  |                                        execve(...)
  |                                    exit_signal = SIGCHLD
  |                                           |
  |                                           v
  |                                        exit(...)
  |                                           |
  |                                           v
  |                                    x = tsk2->parent_exec_id = 6
  |                                    y = tsk2->tsk1->self_exec_id = 6
  |                                         x == y
  |                                           |
  |                                           v

^------------------------< Deliver overwritten "exit_signal" (SIGCHLD) >

3) mother calls execve

tsk1: mother
,--------------------,

|  self_exec_id = 6  |
| parent_exec_id = 6 |
|   parent = <bash>  |----------------------,
|   exit_signal =    |                      |
|           SIGTERM  |                      |
`--------------------`                      |
          |                                 |
          v                                 |
       execve(...)                          |
          |                                 v
          v                            clone(SIGSEGV)
     tsk1: mother                           |
,--------------------,                      |
|  self_exec_id = 7  |                      |
| parent_exec_id = 6 |                      |
|   parent = <bash>  |                      |
|   exit_signal =    |                      |
|           SIGCHLD  |                      |
`--------------------`                      |
                                            |
                                            |
                                            |
                                            |
                                            v
                                        tsk2: child
                                    ,--------------------,
                                    |  self_exec_id = 6  |
                                    | parent_exec_id = 6 |
                                    |    parent = tsk1   |
                                    |   exit_signal =    |
                                    |           SIGSEGV  |
                                    `--------------------`
                                              |
                                              v
                                           execve(...)
                                       exit_signal = SIGCHLD
                                              |
                                              v
                                           exit(...)
                                              |
                                              v
                                       x = tsk2->parent_exec_id = 6
                                       y = tsk2->tsk1->self_exec_id = 7
                                            x != y
                                              |
                                              v
                                "exit_signal" will NOT be delivered

4) mother execs as many times as generates an integer overflow (our attack)

tsk1: mother
,--------------------,

|  self_exec_id = 6  |
| parent_exec_id = 6 |
|   parent = <bash>  |----------------------,
|   exit_signal =    |                      |
|           SIGTERM  |                      |
`--------------------`                      |
          |                                 |
          v                                 |
       execve(...)                          |
          |                                 v
          v                            clone(SIGSEGV)
     tsk1: mother                           |
,--------------------,                      |
|  self_exec_id = 7  |                      |
| parent_exec_id = 6 |                      |
|   parent = <bash>  |                      |
|   exit_signal =    |                      |
|           SIGCHLD  |                      |
`--------------------`                      |
          |                                 |
          v                                 |
       execve(...)                          |
          |                                 |
         ...                                |
    "self_exec_id"                          |
      overflows                             |
         ...                                |
          |                                 |
          v                                 |
       execve(...)                          |
          |                                 v
          v                             tsk2: child
     tsk1: mother                   ,--------------------,
,--------------------,              |  self_exec_id = 6  |
|  self_exec_id = 5  |              | parent_exec_id = 6 |
| parent_exec_id = 6 |              |    parent = tsk1   |
|   parent = <bash>  |              |   exit_signal =    |
|   exit_signal =    |              |           SIGSEGV  |
|           SIGCHLD  |              `--------------------`
`--------------------`                        |
          |                                   |
          v                                   v
      execve(SUID)                         exit(...)
          |                                   |
          v                                   |
     tsk1: mother                             |
,--------------------,                        |
|  self_exec_id = 6  |                        v
|   parent = <bash>  |                 x = tsk2->parent_exec_id = 6
|   exit_signal =    |                 y = tsk2->tsk1->self_exec_id = 6
|           SIGCHLD  |                      x == y
`--------------------`                        |
  ^   original                                |
  | "exit_signal"                             |
  |    SIGSEGV                                v

^------------------------< Deliver original "exit_signal" (SIGSEGV) >

Proof of Concept (PoC):

    I was able to generate an integer overflow on tsk->parent->self_exec_id and

successfully pass the verification in the "do_notify_parent" function. This allowed me to send an arbitrary signal to the mother process running in the different security domain. However, it takes relatively long time to generate such integer overflow:

1) test_case 1:

    Machine: VM under Hyper-V hypervisor
    CPU:     2 VCPUs (i7-8850H CPU @ 2.60GHz)
    RAM:     3.4 GB
    OS:      Ubuntu 19.10 (eoan)
    kernel:  5.5.1-050501-generic

    Time to overflow -> 17 days*

2) test_case 2:

    Machine: Bare-metal
    CPU:     12 CPUs (Xeon(R) E-2176G CPU @ 3.70GHz)
    RAM:     32 GB
    OS:      Ubuntu 18.04.3 LTS (bionic)
    kernel:  4.15.0-72-generic

    Time to overflow -> 7 days*

*) However, my test cases were NOT optimized for speed and it is likely possible
to reduce amount of time needed for such overflow.

After successful verification that described scenario is possible to achieve, I've created a kernel module which simplifies my tests and instead of waiting for a few days to generate an integer overflow, it simulates it. Kernel module exports 2 IOCTLs:
1) Dump current process':

    -> current process' task_struct pointer
    -> current process' PID
    -> current process' self_exec_id
    -> current process' parent_exec_id
    -> parent's task_struct pointer
    -> parent's PID
    -> parent's self_exec_id
    -> parent's parent_exec_id

2) Overwrites parent's self_exec_id with value -100

I've adopted my PoC to leverage new kernel module and immediately simulate described attack. Here are some notes from my tests:

-> Ubuntu sets 2 as a default value for /proc/sys/fs/suid_dumpable
-> This value requires that pattern set in /proc/sys/kernel/core_pattern
must be either an absolute pathname (starting with a leading '/' character) or a pipe.
-> Ubuntu is shipped with 'apport' package by default. This means that
crashes are forwarded through pipe to the 'apport'
-> However, apport throws an unhandled exception in case of ruid != uid, e.g.:

        ERROR: apport (pid 12773) Mon Mar  9 21:07:00 2020: called for pid 12762, signal 11, core limit 0, dump mode 2
        ERROR: apport (pid 12773) Mon Mar  9 21:07:00 2020: not creating core for pid with dump mode of 2
        ERROR: apport (pid 12773) Mon Mar  9 21:07:00 2020: Unhandled exception:

Traceback (most recent call last):
File "/usr/share/apport/apport", line 589, in <module>
info.add_proc_info(proc_pid_fd=proc_pid_fd)
File "/usr/lib/python3/dist-packages/apport/report.py", line 548, in add_proc_info
self['ExecutablePath'] = os.readlink('exe', dir_fd=proc_pid_fd)
PermissionError: [Errno 13] Permission denied: 'exe'
ERROR: apport (pid 12773) Mon Mar 9 21:07:00 2020: pid: 12773, uid: 1000, gid: 1000, euid: 0, egid: 0
ERROR: apport (pid 12773) Mon Mar 9 21:07:00 2020: environment: environ({})

This situation is a results of dropped privileges by apport:

euid = os.geteuid()
egid = os.getegid()
try:
# Drop permissions temporarily to make sure that we don't # include information in the crash report that the user should # not be allowed to access. os.seteuid(os.getuid())
os.setegid(os.getgid()) info.add_proc_info(proc_pid_fd=proc_pid_fd)
finally:
os.seteuid(euid)
os.setegid(egid)

-> If you set 1 as a value for /proc/sys/fs/suid_dumpable (not recommended),
you are free to fully play with crashdumps.

Vectors of attack:

The most obvious attack is to generate a coredump from the higher privileged
processes (like SUID binary). However, most of the modern distros should be securely configured to protect from the attack using such situation (but I just verified Ubuntu case).
Nevertheless, SIGSEGV is not the only useful signal to send. It is possible that some privileged applications (SUID) might change their behavior based on the signals which they receive. Various apps might implement signal handlers in a various way which might be exploited using a described kernel bug. More research is needed in that field.

Details (Problem II.):

Until 2012, 'self_exec_id' field (among others) was used to enforce
permissions checking restrictions for /proc/pid/{mem/maps/...} interface. However, it was done poorly and serious security problem was reported known as "Mempodipper" (CVE-2012-0056). More details about the bug can be found here:

https://git.zx2c4.com/CVE-2012-0056/about/

Linux kernel received a patch for that issue which completely changed the logic how permission checks are enforced for /proc/pid/{mem/maps/...} interface. It can be found here:

https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=e268337dfe26dfc7efd422a804dbb27977a3cccc

Since that patch, 'self_exec_id' is not tracked anymore, but kernel is looking at process' VM during the time of the open(). However, as Solar Designer pointed out, this logic might generate some problems:

https://www.openwall.com/lists/oss-security/2012/01/22/5

In short, if you hold the file descriptor open over an execve() (e.g. share it with child) the old VM is preserved (refcounted) and might be never released. Essentially, mother process' VM will be still in memory (and pointer to it is valid) even if the mother process passed an execve().
This is some kind of 'memory leak' scenario. I did a simple test where process open /proc/self/maps file and calls clone() with CLONE_FILES flag. Next mother 'overwrite' itself by executing SUID binary (doesn't need to be SUID), and child was still able to use the original file descriptor - it's valid.

Nevertheless, I didn't explore that problem more. Maybe it is worth to do so? Suspected resource limits bypass, to be confirmed or disproved with further research.

Another interesting curiosity which is worth to point out about Problem II is the Alan Cox's message sent during the discussion on the fix for CVE-2012-0056:

https://www.openwall.com/lists/kernel-hardening/2012/03/11/13

Affected Software:

Almost all Linux kernels should be affected. However, currently tested logic
is available since 3.3.5 up to the latest one (5.5.8).
Kernels 2.0.39 and 2.0.40 looks secure ;-)

Best regards,
Adam 'pi3' Zabrocki

--
pi3 (pi3ki31ny) - pi3 (at) itsec pl
http://pi3.com.pl

Hi!

Sorry, I missed this originally because it got filed into my lkml archive and not kernel-hardening, but no one actually reads lkml directly, myself included -- it's mostly a thread archive. I'll update my filters, and I've added a handful of people to CC that might be interested in looking at this too. Here's the full email, I trimmed heavily since it's very detailed:
https://lore.kernel.org/lkml/[email protected]/

There was some effort made somewhat recently to get this area fixed:
https://lore.kernel.org/linux-fsdevel/[email protected]/

Nothing ultimately landed, but it's worth seeing if we could revitalize interest. Part of Jann's series was also related to fixing issues with cred_guard_mutex, which is getting some traction now too:
https://lore.kernel.org/lkml/AM6PR03MB5170938306F22C3CF61CC573E4CD0@AM6PR03MB5170.eurprd03.prod.outlook.com/

It'd be worth exploring where the resource counting is happening for this. I haven't looked to see how much of the VM stays in kernel memory in this situation. It probably wouldn't be hard to count it against an rlimit or something.

Thanks for the details! I hope someone will have time to look into this. It's a bit of a "long timeframe attack", so it's not gotta a lot of priority (obviously). :)

-Kees

Kees Cook

This was true after e268337dfe26dfc7efd422a804dbb27977a3cccc, but please see 6d08f2c7139790c ("proc: make sure mem_open() doesn't pin the target's memory"), iir it was merged soon after the 1st commit.

Oleg.

Hey,

No worries ;-)

These changes looks comprehensive and definitely fix current issue.

Thanks for pointing to that discussion. Definately both of that changes fix problems which I've described (and not only that). However, what are the reasons behind not merging them in? Especially, the first part (exec_id) looks harmless and don't require any other updates.

Thanks :) However, I did not focus on optimizing the '*exec_id overflow' scenario and that's certainly possible. E.g. by creating the code as small as possible, don't link with external libraries (or statically compile them in), etc. In such case the time will be significantly smaller.

Another interesting fact (not possible for performing 'overflow' attack but worth to mention) is that we might increment '*exec_id' and force execve() to fail. Function load_elf_binary() calls setup_new_exec() (which increments the counter) and then continue execution of a more heavy work. In such case an 'overflow' would be a matter of hours. However, search_binary_handler() function "protects" from such scenario and in case of error in load_elf_binary() sends SIGSEGV:

    int search_binary_handler(struct linux_binprm *bprm)
    {
    ...
        retval = fmt->load_binary(bprm);
    ...
        if (retval < 0 && !bprm->mm) {
            /* we got to flush_old_exec() and failed after it */
            read_unlock(&binfmt_lock);
            force_sigsegv(SIGSEGV, current);
            return retval;
        }
    ...
    }

flush_old_exec() is called before setup_new_exec().

Thanks,
Adam

pi3 (pi3ki31ny) - pi3 (at) itsec pl
http://pi3.com.pl

Replace the 32bit exec_id with a 64bit exec_id to make it impossible to wrap the exec_id counter. With care an attacker can cause exec_id wrap and send arbitrary signals to a newly exec'd parent. This bypasses the signal sending checks if the parent changes their credentials during exec.

The severity of this problem can been seen that in my limited testing of a 32bit exec_id it can take as little as 19s to exec 65536 times. Which means that it can take as little as 14 days to wrap a 32bit exec_id. Adam Zabrocki has succeeded wrapping the self_exe_id in 7 days. Even my slower timing is in the uptime of a typical server. Which means self_exec_id is simply a speed bump today, and if exec gets noticably faster self_exec_id won't even be a speed bump.

Extending self_exec_id to 64bits introduces a problem on 32bit architectures where reading self_exec_id is no longer atomic and can take two read instructions. Which means that is is possible to hit a window where the read value of exec_id does not match the written value. So with very lucky timing after this change this still remains expoiltable.

I have updated the update of exec_id on exec to use WRITE_ONCE and the read of exec_id in do_notify_parent to use READ_ONCE to make it clear that there is no locking between these two locations.

---

Linus would you prefer to take this patch directly or I could put it in a brach and send you a pull request.

 fs/exec.c             | 2 +-
 include/linux/sched.h | 4 ++--
 kernel/signal.c       | 2 +-
 3 files changed, 4 insertions(+), 4 deletions(-)

index 0e46ec57fe0a..d55710a36056 100644
@@ -1413,7 +1413,7 @@ void setup_new_exec(struct linux_binprm * bprm)
 
 	/* An exec changes our domain. We are no longer part of the thread
 	   group */
-	current->self_exec_id++;
+	WRITE_ONCE(current->self_exec_id, current->self_exec_id + 1);
 	flush_signal_handlers(current, 0);
 }
 EXPORT_SYMBOL(setup_new_exec);

index 04278493bf15..0323e4f0982a 100644
@@ -939,8 +939,8 @@ struct task_struct {
 	struct seccomp			seccomp;
 
 	/* Thread group tracking: */
-	u32				parent_exec_id;
-	u32				self_exec_id;
+	u64				parent_exec_id;
+	u64				self_exec_id;
 
 	/* Protection against (de-)allocation: mm, files, fs, tty, keyrings, mems_allowed, mempolicy: */
 	spinlock_t			alloc_lock;

index 9ad8dea93dbb..5383b562df85 100644
@@ -1926,7 +1926,7 @@ bool do_notify_parent(struct task_struct *tsk, int sig)
 		 * This is only possible if parent == real_parent.
 		 * Check if it has changed security domain.
 		 */
-		if (tsk->parent_exec_id != tsk->parent->self_exec_id)
+		if (tsk->parent_exec_id != READ_ONCE(tsk->parent->self_exec_id))
 			sig = SIGCHLD;
 	}
 

2.20.1

Ack, makes sense to me.

Just put it in your branch, this doesn't look urgent, considering that it's something that has been around forever.

Linus

Done

Eric

+memory model folks because this seems like a pretty sharp corner

$ cat volatile-8.c
typedef unsigned long long u64;
static volatile u64 n;
void blah(void) {
  n = n + 1;
}
$ gcc -O2 -m32 -c -o volatile-8.o volatile-8.c -Wall
$ objdump --disassemble=blah volatile-8.o
[...]
   b: 8b 81 00 00 00 00    mov    0x0(%ecx),%eax
  11: 8b 91 04 00 00 00    mov    0x4(%ecx),%edx
  17: 83 c0 01              add    $0x1,%eax
  1a: 83 d2 00              adc    $0x0,%edx
  1d: 89 81 00 00 00 00    mov    %eax,0x0(%ecx)
  23: 89 91 04 00 00 00    mov    %edx,0x4(%ecx)
[...]
$

This is very much a "we don't care" case.

It's literally testing a sequence counter for equality. If you get tearing in the high bits on the write (or the read), you'd still need to have the low bits turn around 4G times to get a matching value.

So no. We're not doing atomics for the 32-bit case. That's insane.

Linus

Put another way: first you'd have to work however many weeks to do 4 billion execve() calls, and then you need to hit basically a single-instruction race to take advantage of it.

Good luck with that. If you have that kind of God-like capability, whoever you're attacking stands no chance in the first place.

Linus

I'm not really worried about someone being able to hit this in practice, especially given that the only thing it lets you do is send signals; I just think that the code is wrong in principle, and that we should avoid having "technically wrong, but works in practice" code in the kernel.

This kind of intentional race might also trip up testing tools like the upcoming KCSAN instrumentation, unless it is specifically annotated as an intentionally racing instruction. (For now, KCSAN is 64-bit only, so it won't actually be able to detect this though; and the current KCSAN development branch actually incorrectly considers WRITE_ONCE() to always be atomic; but still, in principle it's the kind of issue KCSAN is supposed to detect, I think.)

But even without KCSAN, if we have tearing stores racing with loads, I think that we ought to *at least* have a comment noting that we're intentionally doing that so that people don't copy this kind of code to a place where the high bits change more frequently and correctness matters more.

Since the read is already protected by the tasklist_lock, an alternative might be to let the execve path also take that lock to protect the sequence number update, given that execve is not a particularly hot path. Or we could hand-code the equality check and increment operations to be properly race-free.

No.

tasklist_lock is aboue the hottest lock there is in all of the kernel.

We're not doing stupid things for theoretical issues.

Stop this crazy argument.

A comment - sure. 64-bit atomics or very expensive locks? Not a chance.

Linus

Do you know code paths you see tasklist_lock being hot?

I am looking at some of the exec/signal/ptrace code paths because they get subtle corner case wrong like a threaded exec deadlocking when straced.

If the performance problems are in the same neighbourhood I might be able to fix those problems while I am in the code.

Eric

It's generally not bad enough to show up on single-socket machines.

But the problem with tasklist_lock is that it's one of our remaining completely global locks. So it scales like sh*t in some circumstances.

On single-socket machines, most of the truly nasty hot paths aren't a huge problem, because they tend to be mostly readers. So you get the cacheline bounce, but you don't (usually) get much busy looping. The cacheline bounce is "almost free" on a single socket.

But because it's one of those completely global locks, on big multi-socket machines people have reported it as a problem forever. Even just readers can cause problems (because of the cacheline bouncing even when you just do the reader increment), but you also end up having more issues with writers scaling badly.

Don't get me wrong - you can get bad scaling on other locks too, even when they aren't really global - we had that with just the reference counter increment for the user signal accounting, after all. Neither of the reference counts were actually global, but they were just effectively single counters under that particular load (ie the count was per-user, but the load ran as a single user).

The reason tasklist_lock probably doesn't come up very much is that it's _always_ been expensive. It has also caused some fundamental issues (I think it's the main reason we have that rule that reader-writer locks are unfair to readers, because we have readers from interrupt context too, but can't afford to make normal readers disable interrupts).

A lot of the tasklist lock readers end up looping quite a bit inside the lock (looping over threads etc), which is why it can then be a big deal when the rare reader shows up.

We've improved a _lot_ of those loops. That has definitely helped for the common cases. But we've never been able to really fix the lock itself.

Linus

FYI, if you actually optimize this, it's more like 12s to exec 1048576 times according to my test, which means ~14 hours for 2^32 executions (on a single core). That's on an i7-4790 (a Haswell desktop processor that was launched about six years ago, in 2014).

Here's my test code:

=============

$ grep 'model name' /proc/cpuinfo | head -n1
model name : Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
$ cat build.sh
#!/bin/sh
set -e
nasm -felf32 -o fast_execve.o fast_execve.asm
ld -m elf_i386 -o fast_execve fast_execve.o
gcc -o launch launch.c -Wall
gcc -o finish finish.c -Wall
$ cat fast_execve.asm
bits 32

section .text
global _start
_start:
; eax = argv[0]
; expected to be 8 hex digits, with 'a' meaning 0x0 and 'p' meaning 0xf mov eax, [esp+4]

mov ebx, 0 ; loop counter
hex_digit_loop:
inc byte [eax+ebx]
cmp byte [eax+ebx], 'a'+16
jne next_exec
mov byte [eax+ebx], 'a'
inc ebx
cmp ebx, 5 ;;;;;;;;;;;;;;;;;; this is N, where iteration_count=pow(16,N) jne hex_digit_loop

; reached pow(256,N) execs, get out

; first make the stack big again
mov eax, 75 ; setrlimit (32-bit ABI)
mov ebx, 3 ; RLIMIT_STACK
mov ecx, stacklim
int 0x80

; execute end helper
mov ebx, 4 ; dirfd = 4
jmp common_exec

next_exec:
mov ebx, 3 ; dirfd = 3

common_exec: ; execveat() with file descriptor passed in as ebx mov ecx, nullval ; pathname = empty string
lea edx, [esp+4] ; argv
mov esi, 0 ; envp
mov edi, 0x1000 ; flags = AT_EMPTY_PATH
mov eax, 358 ; execveat (32-bit ABI)
int 0x80
int3

nullval:
dd 0
stacklim:
dd 0x02000000
dd 0xffffffff

$ cat launch.c
#define _GNU_SOURCE
#include <fcntl.h>
#include <err.h>
#include <unistd.h>
#include <sys/syscall.h>
#include <sys/resource.h>
int main(void) {
  close(3);
  close(4);
  if (open("fast_execve", O_PATH) != 3)
    err(1, "open fast_execve");
  if (open("finish", O_PATH) != 4)
    err(1, "open finish");
  char *argv[] = { "aaaaaaaa", NULL };

  struct rlimit lim;
  if (getrlimit(RLIMIT_STACK, &lim))
    err(1, "getrlimit");
  lim.rlim_cur = 0x4000;
  if (setrlimit(RLIMIT_STACK, &lim))
    err(1, "setrlimit");

syscall(__NR_execveat, 3, "", argv, NULL, AT_EMPTY_PATH);
}

$ cat finish.c
#include <stdlib.h>
int main(void) {
  exit(0);
}
$ ./build.sh
$ time ./launch

real 0m12,075s
user 0m0,905s
sys 0m11,026s
$
=============

Half a day. I am not at all surprised, but it is good to know it can take so little time.

Eric

Yep, there are a few ways of optimizing it and I believe I've pointed it out here:
https://www.openwall.com/lists/kernel-hardening/2020/03/31/11

Thanks for doing such tests :)

I've also modified your PoC to use 'sysenter' and 'syscall' instruction. Both cases gave me an extra 4% speed bump (including a test for 64-bits "fast_execve"). I've run it under Intel(R) Xeon(R) E-2176G CPU @ 3.70GHz

As you've proven, it is possible to be done in a matter of hours.

Thanks,
Adam

pi3 (pi3ki31ny) - pi3 (at) itsec pl
http://pi3.com.pl

Thanks for chasing this down. :)

-Kees

Kees Cook

Thanks
Bernd.