Optimized Inlining of Runtime Monitors

A previous study showed how a monitor can be inlined into a potentially untrusted program, producing an instrumented version of this program which provably respects the desired security policy. That study extended previous approaches to the same problem in that it allowed non-safety properties to be monitored, and did not incur any runtime overhead. However, the algorithm itself runs in time

$\mathcal{O}(2^{m\cdot n})$

, where

n

is the size of the original program and

m

that of the property being monitored, and the resulting instrumented program is increased in the order of

$\mathcal{O}(m\cdot n)$

. These algorithmic factors limit the usefulness of the approach in practice. In this paper, we suggest several optimizations which reduce the algorithm’s run time and the size of the resulting instrumented code. Using these optimizations, the monitor inlining can run in time

$\mathcal{O}(v + e)$

where

v

and

e

are respectively the size and number of transitions present in the synchronous product of the original program and the property. Furthermore, we show how the size of the instrumented program can be minimized.