Determining applicability is hard [LWN.net]

Determining applicability is hard

Posted Apr 29, 2008 23:36 UTC (Tue) by jreiser (subscriber, #11027)
Parent article: Ksplice: kernel patches without reboots

"A person is expected to conﬁrm that the target security patch does not make any semantic changes to data structures. Performing this check requires only seconds or a few minutes for most security patches." (Section 1)

Changing a CRC algorithm is a semantic change to any piece of data that is derived from any output of that CRC algorithm. Thus patching a CRC algorithm must not be allowed as long as there are any outputs "in view", whether static globals, static locals, the stack of any thread, or dynamically allocated data. Now go back and reread this paragraph, deleting all instances of "CRC". Therefore, almost anything that is to be patched must be memoryless, either forever, or at the moment. That's hard.

(Log in to post comments)

Determining applicability is hard

Posted Apr 30, 2008 3:45 UTC (Wed) by jreiser (subscriber, #11027) [Link]

"But there's a lot of changes out there that can be done without changing the data in the memory."

The implication is: for any subroutine that is to be patched, along the dynamic execution path from the entry point to any instruction that is effectively modifed by the patch, then there have been no stores to memory (ever in the total execution history since booting the operating system, particularly including past intrusion attempts) except to on-stack local variables of the present subroutine. Within any patched subroutine, all prefixes of execution history up to any point of change must be (and have been) read-only except for automatic locals. That is more than a little restrictive.

Determining applicability is hard

Posted Apr 30, 2008 11:00 UTC (Wed) by dvdeug (subscriber, #10998) [Link]

Why? That's not what "semantic changes to data structures" means; it means that you can't
change the meaning or layout of data structures. What implies that it can't use stores to
memory?

Determining applicability is hard

Posted Apr 30, 2008 14:54 UTC (Wed) by jreiser (subscriber, #11027) [Link]

If any of the past outputs are "in view" (are stored in memory, or were used as inputs to
compute data that is stored in memory at the time of the patch), then changing an algorithm
such that its output changes, is a semantic change to the past outputs.  Running the patched
algorithm on the original inputs won't give the same outputs as the original algorithm, and
many things rely on getting the same output.

Determining applicability is hard

Posted May 1, 2008 0:59 UTC (Thu) by jzbiciak (✭ supporter ✭, #5246) [Link]

I'm not sure I follow. Let's look at a patch, shall we?

--- a/mm/memory.c
+++ b/mm/memory.c
@@ -983,6 +983,8 @@ int get_user_pages(struct task_struct *tsk, struct mm_struct *mm,
        int i;
        unsigned int vm_flags;
 
+       if (len <= 0)
+               return 0;
        /* 
         * Require read or write permissions.
         * If 'force' is set, we only require the "MAY" flags.

(If our dear editor is reading, he might get a chuckle out of my selection.)

I would argue that "get_user_pages" has plenty of side effects in memory on nearly all interesting execution paths. And yet, I imagine this splicing trick works just fine with this patch.

We've changed the algorithm for "get_user_pages" so it doesn't do strange and mysterious things (occasionally leading to local-root exploits) when the length is negative. Since we didn't free all other user pages ahead of time, previous outputs are "in view."

What I *will* buy is if someone exploited this hole on a running kernel, patching the bug after the fact won't cause the bogus allocation to disappear. But, in that case, you're b0rked anyway.

Your argument applies only when valid inputs give materially different outputs. Note that I say materially different. If I change Initial Sequence Number generation in my TCP/IP stack (a noticeable change!), I don't have to close all other TCP connections that are in the process of being established. I just get better behavior going forward.

Determining applicability is hard

Posted May 9, 2008 6:40 UTC (Fri) by xamal (guest, #51976) [Link]

Read my comments above where I post references to how and why this is done. Some systems do
not have the luxury of someone physically going to install new software and flicking a switch.

When applying a HOT-PATCH you do want to ensure that the patched area is not cached or some
intensive application is going on. The ideal way is to send the computer to some idle state
(some sort of idle loop), do the patch and transition from the idle mode.