3. Tamper Resistance Techniques and Checksumming

Introduction.
Software tamper resistance is the art of crafting a program such that it cannot be modified by a potentially malicious attacker without the attack being detected. In some respects, it is similar to fault-tolerant computing, in that potentially dangerous changes in program state are detected at runtime. For tamper resistance, however, it is assumed that intelligent, malicious attackers (rather than hardware flaws or software errors) may be responsible for such changes. Self-checking tamper resistance is distinguished in its ability to run on current unmodified commodity hardware without requiring third parties, because all the tests are performed by the application on its own code/data.

There are of course different techniques for self-checking software (e.g. program or result checking and generation of the correct executable or part of code on the fly, decryption according to a calculated digest) partially derived from asimmetric signature algorithms, but we'll focus more on checksumming.

The standard threat model for software tamper resistance is the hostile host model. The challenge is to protect an application running on a system controlled by a malicious, intelligent user. Because such a user can in theory change any code on the computer, other software on such a system, including the operating system, is untrusted; in the case of particularly determined adversaries, even the hardware is untrusted. This situation is in contrast with the hostile client problem in which we assume a trusted host and untrusted application. The hostile client problem appears to be an easier problem to solve; numerous solutions have been developed, e.g. sandboxing and is typical of mobile agents such as smartphones or PDAs.

Since a single checksum is relatively easy for an attacker to disable, stronger proposals rely on a network of inter-connected checksums, all of which must be disabled to defeat tamper resistance. A tester reads the area of memory occupied by code and readonly data, building up a checksum result based on the data read. A subsequent section of the code may operate on the checksum result, affecting program stability or correctness in a negative way if a checksum result is not the same as a known good value pre-computed at compile time. The sections of code which perform the checksumming operations may be further hidden using code obfuscation techniques to prevent static analysis. Ideally the effects of a bad checksum result in the program are subtle (e.g. causing mysterious failures much later in execution) thus making it much more difficult for an attacker to locate the checksum code.

Figure 1 - A good distribution of checksum blocks within a code segment.

Figure 1 gives a simplified view of a typical distribution of checksum code within an application. In practise, there may be hundreds of checksum blocks hidden within the main application code. Each allows verification of the integrity of a predetermined section of the code segment. The read-only data segment may also be similarly checked.

The checksumming code is inserted at compile time and integrated with regular execution code. The application also requires a correct checksum result for each block in order to work properly.
The resulting scheme is an Interlocking Trust Model, for which each segment not only on itself but also on other segments to effectively perform its task. Thus each segment of code would be made responsible for maintaining and verifying the integrity of other segments

High level view of how the protection works, Testers and Guards
The overall protection works like this: at runtime, a large number of embedded code fragments called  testers test small segments of code for integrity (using a linear hash function and an expected has value); if integrity fails, an appropriate response is pursued. The peices of code called on check failures are called guards and can be programmed to carry out arbitrary tasks (for example common guards are peices of code repairing the code,  erasing the breakpoints or downloading a fresh copy of the application).

Two of the most common guards are checksumming and repairing.

• Checksum Guards: The checksum guards are programmed to check a code fragment within the software. If this code is tampered with in any way the guard takes action. The type of action the guard takes can vary in degree from logging the infraction to halting the program.
• Repair Guards: The repair guards can fix a tampered section of code. Thus, the changes an attacker made are wiped out and the program remains secure. The repair can be made by storing a clean copy of the segment of code the guard is protection somewhere, and then replacing the dirty copy with the clean one.

The security of the guards actually comes from guards watching each other's backs. Each guard protects fragments of code, and that includes protecting other guards. Figure 1.1 shows an example of a possible network of guards.

Figure 1.1 - A possible distribution of cross-checking guards of an application's integrity.

A group of guards working together implement a sophisticated protection scheme that is more resilient against attacks than a single guard. These schemes are used by the most modern protectors, such as Armadillo also: the nanomities trick is just a way to implements a Guard scheme and an interlocking scheme, made of two processes, controlling one each other.
In order to perform their duties, a network of guards is placed into the program and hooked to its execution flows in proper ways, before of the controlled code goes into execution: a repairing guard has to be inserted into a point in the control flow that is to be reached before guarded code (in execution order). In other words the guard has do dominate the guarded code. Guards can also be controlled by other guards too. Figure 1.2 reports another real more sophisticated example where a network of Guards (G) and Guarded Code (C) is presented beside it's distribution into the real application's memory.

Figure 1.2 - A Guards graph and the corresponding memory layout of the guarded program.

Defeating complex Guard Networks can be, generally speaking, a nightmare.

Anti-Tampering details
There are several aspects of such checksumming which an attacker must keep in mind:

1. Because of the overlapping network of testers, almost every checksumming block must be disabled at the same time in order for a tampering attack to be successful.
2. The resulting value from a checksum block must remain the same as the original value determined during compilation (or all uses of the checksum value must be determined and adjusted accordingly), if the results of a checksum are used during standard program execution.
3. The checksum values are only computed for static (i.e. runtime invariant) sections of the program.
4. Checksumming code is obfuscated, hard to find, and the use of checksum results is also hidden.

Note that a critical (implicit) assumption of checksumming algorithms is that D(x) = I(x), where D(x) is the bit-string result of a “data read” from memory address x, and I(x) is the bit-string result of an “instruction fetch” of corresponding length from x. In  the practical everyday cases this is the situation, because D(x) and I(x) are the same portion of memory "read as data and as instructions".
If I(x) were different from D(x), then the checksumming code would always check using D(x) while the processor would always execute I(x).
Checksumming aims to verify that the code the processor executes is the original code, and thus assumes that the code it reads is the code the processor executes.

While current checksumming proposal critically rely on this assumptions there are opportunities to violate this assumption on several modern processors..

4. CPU Support for Virtual Memory

This section provides background information for those less familiar with the virtual memory subsystems of modern processors, including translation look-aside buffers (TLBs). Thos of you already familiar with processor architecture can jump directly to the next section.

Modern processors do much more than execute a sequence of instructions. Advances in processor speed and flexibility have resulted in a very complex architecture. A significant part of this complexity comes from mechanisms designed to efficiently support virtual memory. Virtual memory, first introduced in the late 1950’s, involves splitting main memory into an array of frames (pages) which can be subsequently manipulated. Virtual addresses used by an application program are mapped into physical addresses by the virtual memory system.

Figure 2 - Translation of Virtual Address into a Physical Address

Even though the page table translation algorithmmay vary slightly between processors and may sometimes be implemented in software, modern processors all use roughly the same method for translating a virtual page number to a physical frame number. Specifically, this translation is performed through the use of page tables, which are arrays that associate a selected number of virtual page numbers with physical frame numbers.

Because the virtual address spaces of most processes are both large and sparse, page table entries are only allocated for the portions of the address space that are actually used. To determine the physical address corresponding to a given virtual address, the appropriate page table, and the correct entry within that page table must be located.

For systems that uses 3-level page tables, a virtual address is divided into four fields, x1 through x4. The x1 bits (the directory offset) specify an entry in a perprocess page directory. The entry contains the address of a page map table. The x2 bits (the map offset) are used as an offset within the specified page map table, giving the address of a page table. The x3 bits (the table offset) index into the chosen page table, returning the number of a physical page frame. x4, then, specifies the offset within a physical frame that contains the data referred to by the original virtual address.

This resolution process is illustrated in Figure 3. Note that if memory segments are used, segment translation typically occurs before operations involving the page table.

Figure 3 - Translation of a Virtual to Physical Address through Page Tables

TLB Translation look Aside Buffer
Because multiple memory locations must be accessed to resolve each virtual memory address, virtual address translation using page tables is a relatively expensive operation. To speed up these mappings, a specialized high-speed associative memory store called a translation look-aside buffer (TLB) is used.

A TLB caches recently used mappings of virtual page numbers to physical page frames. On every virtual memory access, all entries in a TLB are checked to see whether any of them contain the correct virtual page number. If an entry is found for the virtual page number, a TLB hit has occurred, and the corresponding physical page frame is immediately accessed. Otherwise, we have a TLB miss, and the appropriate page tables are consulted in the fashion
discussed previously. The mapping so determined is then added to the TLB by replacing the mapping that was least recently used. Figure 4 illustrates what happens on a TLB hit.

Figure 4 - Address Translation using a TLB

Because of the principal of locality, TLB translation works very well in practise. System designers have noticed, however, that code and data exhibit different patterns of locality. To prevent interference between these patterns, caches of code and data are often separated; for similar reasons, most modern CPUs have separate code and data TLBs.
CPU caches mark referenced memory as code or data depending upon whether it is sent to an instruction decoder. Whenever an instruction is fetched from memory, the instruction pointer is translated via the instruction TLB into a physical address. When data is fetched or stored, the processor uses a separate data TLB for the translation. Using different TLB units for code and data allows the processor to maintain a more accurate representation of recently used memory. Separate TLB’s also protect against frequent random accesses of code (data) overwhelming both TLB’s. Because most code and data references exhibit high degrees of locality, a combination of small amounts of fast storage (e.g. onchip memory caches) and more plentiful slower storage (DRAM memory) can together approximate the performance of a larger amount of fast storage.

Page swapping
Because the memory management unit presents a virtual address space to the application running, the application need not be aware of the physical sections of memory which it actively uses. Thus even though the virtual address space of a program is contiguous, the physical regions of memory it uses may not be. This presents a great opportunity for the operating system. Not only does it allow multiple applications to be run on the system (each with its own unique virtual address space, mapping to different physical pages), but it allows the operating system to only keep in physical memory those parts of each application required at the current time.

Since not all pages of virtual memory may map to a physical page, there must be some way for the processor to inform the OS when a virtual address does not have a physical mapping. The processor does this through the use of a page fault interrupt. The processor will store the virtual address which caused the page fault in a register, and then signal the operating system through an interrupt handler. The operating system updates the mapping of virtual to physical addresses, so that the requested virtual address can be mapped to a physical address.

This may mean bringing the section of the program into physical memory from disk or some other external storage. The OS then signals the processor to retry the instruction by returning from the interrupt. The OS also has the choice of aborting execution of the application if it determines that the virtual address is invalid, e.g. if the virtual address refers to memory that has not been allocated.

Access Controls on Memory.
Along with the translation of a virtual to physical address, the processor may implement access protection on memory regions. Since the virtual memory subsystem already splits physical memory into small areas (frames), it makes sense that the same memory management unit would also implement access control on a per-frame basis. The most important protection is that only pages that an application is allowed to access are mapped into its page table. To prevent an application from manually mapping a page into its address space, the page directory base pointer is stored in a read-only register, and the frames containing a process’s page table are themselves not accessible by the process.

In addition, there are protection mechanisms for pages which are in a process’s address space. Each mapped page is restricted in the types of operations that may be performed on its contents: read, write, and instruction fetch (also called execute). Permitted operations are specified using control bits associated with each page table entry. Read and write are common operations on data pages, while executing code is commonly associated with a page containing executable code.

Modern operating systems take advantage of the protection mechanisms implemented by the processor to distinguish various types of memory usage.
 

The ability to set no-execute permission on a per-page basis produces the restriction that many programs are confined to executing code from their code segment, unless they take specific action to make their data executable.

Although such changes can interfere with systems that generate machine code at runtime (e.g. modern Java Virtual Machines), many types of code injection attacks can be defeated by nonexecutable data pages

Table 1 - Separation of access control privileges for different page types

Table 1 shows the ideal separation of privileges for different sections of an application. This separation of privileges is currently assumed in executable file formats. All processors implementing page level access controls must check for disallowed operations and signal the operating system appropriately. Most often, the operating system is signalled through the page fault interrupt, which indicates the memory reference that caused the invalid operation.

References

I suggest the following further readings from now on to complete this argument..

1. O'Reilly - Secure Programming Cookbook for C and C++
2. There a lot of tutorials on http://tutorials.accessroot.com which fool anti-tampering protections involving hashing.
3. Intel - IA-32 Intel Architecture Software Developer's Manual, volume 3: System Programming Guide

..and essentially all the tutorials seens around (also others on our tutorials page) which often target checksummed applications..