Towards integral binary execution: Implementing oblivious hashing using overlapped instruction encodings

Executing binaries without interference by an outside adversary
has been an ongoing duel between protection methods and attacks.
Recently, an efficient kernel-patch attack has been presented
against commonly used self-checking code techniques that
use checksumming ahead of execution. While methods based on
self-modifying code can defend against this attack, such techniques
depend on low-level architectural details and may not be practical
in the long run. An alternative defense is to use oblivious hashing
(OH). Instead of checking code integrity prior to execution, OH
can verify untampered runtime behavior continuously. However,
earlier OH approaches have some weaknesses, particularly with
binary code: Physical instruction bytes cannot be easily checked
during execution, and an attacker may be able to detect and remove
OH checks, since OH alone does not provide tamper-resistance or
obfuscation.
In our approach, we deliberately overlap a program’s basic
blocks so that they share instruction bytes. This increases tamperresistance
implicitly because malicious modifications affect multiple
instructions simultaneously. Also, our scheme facilitates
explicit anti-tampering checks via injection of OH instructions
overlapped with target code, enabling OH that can verify integrity
of both runtime state and executing instructions. Thus,
our method addresses anti-checksum attacks without resorting to
self-modifying code, and also extends OH to verify physical code,
not only program state. In addition, overlapping facilitates resistance
against disassembly and decompilation. Our approach works
on processor architectures and byte-codes that support variablelength
instructions. To our knowledge, this is the first technique
that blends tamper-resistance into architecture and therefore significantly
improves robustness of binaries.