How to implement the "special pool" ?

[He Chuan]

Hi 

    KEDR can not check kernel space memory overflow and some other potential problems, so I want to delevop it using the "special pool" tech, which is mentioned in a paper --<Runtime Verification of Linux Kernel Modules Based on Call Interception>.

    If I use the "special pool", the first I think I should allocate a big enough memory in kernel as the special pool.

    Then, create a payload to instrument the functions to replace the interesting functions(alloc functions and free functions).  When the module is allocating memory, I will do something before retrun the address in my special pool. But I don't know how to split the pool. Do I need to develop a tiny memory management like the kernel using the page or slab/slub structs ?

    I confuse it .

Thanks

He Chuan

[Eugene Shatokhin]

Hi,

Well, the term "special pool" I used then was misleading. Actually, I meant two techniques under that name.

1.

If a module allocates a memory page or a range of pages, allocate 2 more pages, one right before the beginning of the requested memory area and one right after it. Then mark these pages non-existent (not accessible). Should the module trigger an overflow / underflow and try to read the data outside of the allocated memory area, an exception (page fault) will occur.

I learned later that vmalloc() does exactly that already, so it is not needed to implement that with KEDR.

No need to create the pools of memory pages, etc.

2. 

A weaker technique that however can be applied to smaller memory allocations is as follows. Again, we need to intercept memory allocation/deallocation operations made by a module. Each time a memory block is requested, allocate one larger by, say, 2-20 bytes. The requested memory should be in the middle of the allocated block like in (1). The additional bytes before and after it should be filled with some predefined values. If the target module overwrites these values, it could be detected when the memory is freed.

This way, reads outside of the allocated buffer cannot be caught but some writes can. IIRC, the in-kernel SLAB debugging facilities may do something like this already.

The problem with implementing (1) and (2) with KEDR, as I see it now, is that the tool needs to track all allocations and deallocations. Even if the memory is actually deallocated by another kernel module of the kernel proper, which KEDR cannot always do. Otherwise some code will call kfree/vfree on a pointer inside of a memory block rather than to the beginning of one => kernel oops.

So, now I suppose, it is very hard to do that kind of analysis with KEDR unlike leak detection and fault simulation, which are fine.

Good news is, there is probably another project that may suit your needs better: AddressSanitizer for the kernel:

http://code.google.com/p/address-sanitizer/wiki/AddressSanitizerForKernel

I would suggest taking a look at it, if you haven't done so already.

Hope this helps.

Regards,

Eugene

2014/1/17 He Chuan <tinys...@163.com>

--
You received this message because you are subscribed to the Google Groups "kedr-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to kedr-discuss...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[He Chuan]

Hello,

   Thanks for reply. Actually, the two points you mentioned have been considered already.

   To (1), I don't know how to catch the exception from page-fault if not change the function do_page_fault(), that will be called by the system. But now I know vmalloc() has done it, so I can leave it.

    To (2), I have made one, and tryed it useing a simple module written by myself. It works, but I know the problems, when other functions free the point(middle in the memory), it maybe cause crash.

    what I want to do is to check the kernel memory without change the source code, like kedr. Though it may not works well, but also can detect some possible problems,  that is fine.

ps: I have replied through email, but the content is not yet displayed on this webpage.

Thanks

HeChuan

[Eugene Shatokhin]

Hi,

Yes, I received both letters, that is OK.

By the way, if you ever need to intercept page faults as well as other exceptions, you can do so using "die notifiers" (see register_die_notifier() kernel function).  It is probably not needed for your current project, but still, a nice thing to be aware of. I actually use these now in one of the systems that help reveal data races in the kernel modules.

As for (2), yes, I think I see your point now. Good to know it is working.

I would also recommend looking at Kprobes if you haven't so far. Your kernel module can place them at almost arbitrary places in the kernel code. And, IIRC, you can access and change the arguments of the "probed" kernel functions (with a variant of Kprobes called jprobes). This could complement KEDR and alleviate the problems with the memory allocated or deallocated outside of the module under analysis. That is, with Kprobes you can hook into, say, kfree() and your code will execute each time kfree() is called, not only if it is called from the module under analysis. There you may check somehow if the memory was allocated by your analysis system and deallocate it appropriately. Your KEDR payload handles allocations/deallocations that happen in the target module, your Kprobe hooks handle the remaining ones. A kind of a safety net. This is just an idea, I haven't tried it yet.

Regards,

Eugene

2014/1/18 He Chuan <tinys...@163.com>

[何川]

Hello,

  Happy Chinese New Year! It's a little late, but best wishes for you too!

  I have relaxed in my holiday for a while, so I restart to my work recently. I study the Kprobe you mentioned, and I found the Kprobe can change parameter whitch is sent into the kfree(). In the pre_handle function, pt_regs->ax is the "const void *objp". If I change the regs->ax, then I can change the parameter. So I can only ues Kprobe to detect kfree outside the payloads. I will use a data struct to store the addrs returned by kmalloc after changed(I means use the (2) method, use more bytes at the top and bottom). Then the Kprobe will monitor the kfree, if the ax match my stored data, I will fix the ax(minus the offset), so I can free the memory correctlly. That my point.

  My English is just soso, if anywhere is not clear, please send email to me.

Thanks

HeChuan

------------------ Original ------------------

From:  "Eugene Shatokhin";<eusp...@gmail.com>;

Date:  Mon, Jan 20, 2014 02:09 AM

To:  "kedr-discuss"<kedr-d...@googlegroups.com>;

Cc:  "He Chuan"<tinys...@163.com>;

Subject:  Re: [kedr-discuss] How to implement the "special pool" ?

Hi,

Yes, I received both letters, that is OK.

By the way, if you ever need to intercept page faults as well as other exceptions, you can do so using "die notifiers" (see register_die_notifier() kernel function). It is probably not needed for your current project, but still, a nice thing to be aware of. I actually use these now in one of the systems that help reveal data races in the kernel modules.

As for (2), yes, I think I see your point now. Good to know it is working.

I would also recommend looking at Kprobes if you haven't so far. Your kernel module can place them at almost arbitrary places in the kernel code. And, IIRC, you can access and change the arguments of the "probed" kernel functions (with a variant of Kprobes called jprobes). This could complement KEDR and alleviate the problems with the memory allocated or deallocated outside of the module under analysis. That is, with Kprobes you can hook into, say, kfree() and your code will execute each time kfree() is called, not only if it is called from the module under analysis. There you may check somehow if the memory was allocated by your analysis system and deallocate it appropriately. Your KEDR payload handles allocations/deallocations that happen in the target module, your Kprobe hooks handle the remaining ones. A kind of a safety net.. This is just an idea, I haven't tried it yet.

Regards,

Eugene

[Eugene Shatokhin]

Hi,

Thank you! Glad to know you've had good holidays!

Now to the Kprobes - yes, that was I meant. That might work. 

One more thing to note is the register usage conventions on passing parameters to the functions.

On 32-bit x86 systems, the kernel functions (except system calls) get their arguments as follows:

- eax, edx, ecx (in order), the rest goes on stack. So, yes, %eax contains the argment of kfree() in this case.

On x86-64, things are different, the arguments are passed this way:

- rdi, rsi, rdx, rcx, r8, r9 (in order), the rest goes on stack. So, the argument of kfree() is in %rdi register in this case.

Regards,

Eugene