A process-level virtual machine (PVM) is a layer of software interleaved with the application and the host environment; it executes the application. The application binary is either transformed (obfuscated) to a secret instruction-set architecture, or encrypted. The general class of threats comprises advanced reverse-engineering tools.

This paper describes lucidly and logically “a novel methodology that imparts tamper detection at run time to PVM-protected applications.” The mechanism entails the “run-time creation of a network of ... instruction sequence[s] that [compute] checksums [of] portions of the target code.” These sequences are called software knots, and the authors have implemented, and experimented with, a PVM system that automatically generates software knots. Their evaluation shows the knots’ integrity checks add less than 10 percent overhead to performance and memory. Figure 3 is a clear flowchart of the application with knots versus the original application.

The authors implement knot polymorphism, the choice of random instructions from a database, to thwart attacks by automatic scanners. The random-number generator (RNG) that they use is custom, so as to protect the executing system against attacks on the RNG itself. Predicated triggering of knots is an additional enhancement, which deals with fluctuating rates of knot execution.

This well-written (only two innocuous typographical errors) and thoroughly researched (51 references) paper is for experts. However, I gained very much from reading it, and recommend it to all who, in James D. Watson’s words [1], want to “read around their subject.”