Hi Peter, <div><br></div><div>Yes, the idea sounds feasible. </div><div>You could use 8:1 or even smaller shadow. </div><div>E.g. if you can live with 64-byte aligned mallocs/allocas, you can have very compact 64:1 mapping,. </div>
<div>As you mention, having 1 byte shadow may be not 100% accurate, so you may chose 2 byte shadow (e.g. 64:2 mapping). </div><div>If you know that you will not have more than 64 threads (or 64 classes of plugins), you may have 64:8 mapping </div>
<div>(i.e. 64 bytes of application bytes map to 8 shadow bytes, and the shadow is a 64-bit bitmask of threads (plugin classes) that could touch this memory). </div><div><br></div><div>I wouldn't try to modify the existing AddressSanitizer.cpp, but would write a new pass for your thesis. </div>
<div>If you need help with the asan code -- just ask. </div><div>--kcc </div><div><br></div><div><br></div><div><br></div><div><br><br><div class="gmail_quote">On Wed, Sep 26, 2012 at 2:56 PM, Peter Boström <span dir="ltr"><<a href="mailto:pbos@kth.se" target="_blank">pbos@kth.se</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi llvm-dev!<br>
<br>
I'm writing my master's thesis on sandboxing/isolation of plugins<br>
running in a multithreaded environment. These plugins run in a real-time<br>
environment where the cost of IPC/context switching and being at the<br>
scheduler's mercy is not an option. There can be a lot of plugin<br>
instances running and all have to perform some computations and return<br>
the result to the main thread on an audio-buffer callback.<br>
<br>
These need to be isolated, primarily from the main thread, but<br>
preferably from eachother as well. I'm thinking that modifying<br>
address-sanitizer for this purpose could be feasible.<br>
<br>
The shadow byte could also be split to contain a part with a 'short-id'<br>
associated with to which thread/plugin the memory belong. This would of<br>
course limit the plugin/thread short-ids available, and in theory some<br>
false negatives could arise if two plugins are given the same short-id,<br>
and then access eachother's memory, though this error would be detected<br>
if it occurs another time, when they don't have the same short-id.<br>
<br>
Modification would be slightly different if n threads drive n plugins,<br>
or if a thread pool of n threads drive m plugins.<br>
<br>
This would of course not work for globals, which naturally would be<br>
owned by the main thread. Also any kind of communication between plugins<br>
or back to the main thread would have to be mediated by the main thread<br>
or using uninstrumented/unsafe code.<br>
<br>
It's intended that the main code and plugin code are compiled with<br>
different asan passes, so their code is slightly differently<br>
instrumented.<br>
<br>
<br>
>From what I have thought of yet (but I'd love feedback!), these changes<br>
are needed:<br>
<br>
1. Storing+checking thread/plugin id in shadow byte.<br>
2. Modified stack instrumentation to set up these shadow bytes.<br>
3. Graceful shutdown of plugins preferred, free'ing heap and signaling<br>
back to main thread instead of shutting down.<br>
<br>
Also, an optional compile flag could be used to modify the<br>
instrumentation's granularity, whether to assume memory blocks are<br>
allocated in multiples of 8, giving less code-blowup. The shadow bytes<br>
would essentially be booleans then. Though this isn't directly related<br>
to the changes I'd require doing.<br>
<br>
<br>
=== Heap part ===<br>
<br>
shadow_byte k: 0 0 0 0 0 0 0 0<br>
<short_id><shadow><br>
<br>
short-id part: 0: main thread<br>
1-30: plugin/thread short-ids<br>
31 = 0x1F, all bits set: unallocated<br>
<br>
shadow part: 0-7, same encoding as original.<br>
<br>
<br>
== Original instrumentation code (ASan USENIX2012 paper) ==<br>
<br>
* All instrumented code:<br>
<br>
ShadowAddr = (Addr >> 3) + offset;<br>
k = *ShadowAddr;<br>
<br>
if (k != 0 && (Addr & 7) + AccessSize > k)<br>
ReportAndCrash(Addr);<br>
<br>
== Concept code (code blowup, though) ==<br>
<br>
ShadowAddr = (Addr >> 3) + offset;<br>
k = *ShadowAddr;<br>
alloc_id = k >> 3;<br>
shadow = k & 0x0F;<br>
<br>
* Thread/plugin code:<br>
<br>
if (alloc_id != my_short_id || // alloc belongs to other thread<br>
k && (Addr & 7) + AccessSize > k)<br>
ReportAndCrash(Addr);<br>
<br>
<br>
* Main code:<br>
<br>
if (alloc_id != 0x1F || // unallocated memory<br>
k != 0 && (Addr & 7) + AccessSize > k)<br>
ReportAndCrash(Addr);<br>
<br>
<br>
== Less granularity: assume+enforce multiples of 8, quicker/smaller ==<br>
<br>
shadow byte = short-id: 0 = main id<br>
1-254: short-ids<br>
255: unallocated<br>
<br>
ShadowAddr = (Addr >> 3) + offset;<br>
k = *ShadowAddr;<br>
<br>
* Thread/plugin code:<br>
<br>
if (k != my_id) // allocated/set from different thread<br>
ReportAndCrash(Addr);<br>
<br>
<br>
* Main code:<br>
<br>
if (k != 0xFF) // unallocated memory<br>
ReportAndCrash(Addr);<br>
<br>
<br>
=== Stack part ===<br>
<br>
This part would be different depending on whether there's a 1-to-1<br>
mapping between threads and plugins.<br>
<br>
* 1-to-1 mapping:<br>
<br>
Since the plugin owns the thread stack, all of the corresponding<br>
shadow can be initially filled with the shadow byte indicating that<br>
that thread can access all of it.<br>
<br>
Poisoning the redzones would have to be done still, but unpoisoning<br>
(and initial setup) would not set the shadow to zero(except for the<br>
main stack), but rather each byte (memset) back to (short_id << 3),<br>
which would indicate that the plugin with that short_id can read/write<br>
all corresponding bytes.<br>
<br>
<br>
* n-to-m mapping:<br>
<br>
If the stack is shared, it can't be poisoned/unpoisoned back to a<br>
readable state. When allocating stack variables, all corresponding<br>
shadow bytes have to be set to readable by that stack. Though it may<br>
be possible to have different stacks for each plugin, and use the same<br>
mapping as above.<br>
<br>
<br>
===<br>
<br>
What do you think? Does this sound at all feasible? This would of course<br>
not be changes to the existing -faddress-sanitizer flag, but part of<br>
another flag for the thesis project.<br>
<br>
<br>
Very thankful for feedback!<br>
<br>
Kind regards,<br>
- Peter<br>
<br>
</blockquote></div><br></div>