<div class="gmail_extra">On Wed, Sep 26, 2012 at 4:17 AM, Peter Boström <span dir="ltr"><<a href="mailto:pbos@kth.se" target="_blank">pbos@kth.se</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Hi llvm-dev!<br>
<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>
<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>
<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 instrumented with<br>
different asan passes.<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>
      shadow && (Addr & 7) + AccessSize > shadow)<br>
      ReportAndCrash(Addr);<br>
<br>
<br>
* Main code:<br>
<br>
  if (alloc_id == 0x1F || // unallocated memory<br>
      shadow != 0 && (Addr & 7) + AccessSize > shadow)<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 = 0xFF: unallocated<br>
<br>
  ShadowAddr = (Addr >> 3) + offset;<br>
  k = *ShadowAddr;<br>
<br>
* Thread/plugin code:<br>
<br>
  if (k != my_short_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>
  state readable by the next plugin using that stack space. When<br>
  allocating stack variables, all corresponding shadow bytes have to be<br>
  set to readable by that stack. Though it may be possible to have<br>
  different stacks for each plugin, and use the same mapping as above.<br>
<br>
<br>
===<br>
<br>
What do you think? Does this sound feasible? This would of course not be<br>
changes to the existing -faddress-sanitizer flag, but part of the thesis<br>
project.<br>
<br>
<br>
Very thankful for feedback!<br><br></blockquote><div><br></div><div><br></div><div>Hi Peter,</div><div><br></div><div>Have you looked at ThreadSanitizer (-fthread-sanitizer)?</div><div>It does not exactly the thing you want, but something similar. It will detect data races between threads (when a data is accessed w/o proper synchronization). </div>
<div><br></div><div><br></div></div></div>