Dealing with Asynchronous Signal Delivery in Multi-Variant Execution

A major problem that can cause false-positives in multi-variant execution is asynchronous signal delivery. As an example, assume variant (process) p1 receives a signal and starts executing its signal handler. p1's signal handler invokes system call s1, causing the monitor to wait for the same system call from p2. Meanwhile, variant p2 has not received the signal and is still running its main program code. When p2 calls system call s2, the monitor will detect the difference between s1 and s2 and raise an alarm. Therefore, it is essential that the variants receive signals at the same state of execution.

Whenever a signal is delivered to a variant, the OS pauses the variant and notifies the monitor. The monitor has the choice to deliver the signal to the variant or ignore it. The monitor immediately delivers signals that terminate program execution, such as SIGTERM and SIGSEGV. Other signals are delivered to all variants synchronously, meaning that signals are delivered to all variants either before or after a synchronization point. If at least half of the variants receive a signal before making a system call, and the rest invoke the system call, the monitor makes the latter variants skip the system call by replacing it with a non-state-changing call and forces them to wait for the signal. The monitor then delivers the signal to all variants and then restores the system call in those variants that have been made to skip it. The variants that are forced to wait for a signal and do not receive it within a configurable amount of time are considered as non-complying.

If fewer than half of the variants receive a signal and the rest invoke a system call, the signal is ignored and the variants which are stopped by the signal are resumed. The monitor keeps a list of pending signals for each variant. The ignored signals are added to these lists. As more variants receive the signal, the monitor checks the lists and when half of the variants have received the signal, the signal is delivered using the method mentioned above. The only difference is that the signal has to be sent again to the variants that ignored it. The monitor sends the signal to these variants again and removes it from the variants' pending signal lists.

The following flowchart depicts the algorithm that removes false-positives caused by asynchronous signal delivery in multi-variant environments (Click for larger picture). One could call this method "semi-synchronous signal delivery".