Anomalous Path Detection

From NUEESS

Overview

Program execution can be tampered by malicious attackers through exploiting software vulnerabilities. Changing the program behavior by compromising control data and decision data has become the most serious threat in computer system security. Although several hardware approaches have been presented to validate program execution, they either incur great hardware overhead or introduce false alarms.

We propose a new hardware-based approach by leveraging the existing speculative architectures for run-time program validation. The on-chip branch target buffer (BTB) is utilized as a cache of the legitimate control flow transfers stored in a secure memory region. In addition, the BTB is extended to store the correct program path information. At each indirect branch site, the BTB is used to validate the decision history of previous conditional branches and monitor the following execution path at run-time.

Implementation of this approach is transparent to the upper operating system and programs. Thus, it is applicable to legacy code. Because of good code locality of the executable programs and effectiveness of branch prediction, the frequency of control-flow validations against the secure off-chip memory is low. Our experimental results show a negligible performance penalty and small storage overhead.

Motivation

When control flow attacks are inflicted on a system, the program execution can be directed to either malicious code injected by the attacker or some existing code that would not otherwise execute at that moment. It is the execution of the compromised control instructions that deviate from its expected behavior.

To prevent control flow attacks, our micro-architecture level mechanism validates both control flow transfers and execution paths. The program execution monitoring is sampled at run-time at the sites of indirect branches, instead of every conditional branch or jump. Thus, the performance and storage overhead incurred by the monitoring is reduced greatly. However, since the checking is carried out less frequently, the coverage of each checking process has to be adequate for the program to reduce the false negative rate of validation.

Extending the BTB

Regular branch prediction flow enhanced with security features

In execution stage, the system has to compare the dynamic BHSR, PBPC, and size against the ICS in the BTB entry. If the history matches as well, it is a history hit, and the program execution will continue as normal. Otherwise, it is a history mis-prediction: the history paths associated with the TPC in the BTB do not include the history just seen. The tuple of {BPC, computed NPC, BHSR, PBPC, SIZE} has to be sent to the external memory (FRS) for further validation. This is labeled 3. Only when it misses again, a security alarm will be raised.

In traditional architecture, on an address mis-prediction site, the BTB entry is just updated when the next PC is resolved from the instruction. However, since an indirect target address mis-prediction may also be caused by security attacks, in our enhanced architecture, the external memory has to be checked before the corresponding entry in the BTB is updated with the matched ICS. This site is labeled 2. At a direction mis-prediction site where there is a BTB entry for the instruction but the instruction is actually not taken, the entry is deleted and the fetched TPC is squashed. There is normally a mis-prediction penalty for these remedy actions.

On the leftmost side of the flow diagram, if no entry is found in the BTB for the current PC, the instruction may be a regular data path instruction or a control instruction falling through. In the subsequent ID stage, if the instruction is found to be a taken control instruction, it is a direction mis-prediction, and the address is not cached in the BTB. Before a new entry is inserted to the BTB, the tuple of {BPC, computed NPC, BHSR, PBPC, SIZE} has to be validated against the record in memory. This site is labeled 1. Since the BTB has limited capacity, a replacement policy, e.g., least recently used (LRU), may be employed to find a victim to evict for multi-associativity BTB.

Architectural Support

People

• Juan Carlos Martinez Santos

Publications

• J. C. Martinez Santos and Y. Fei, “Leveraging speculative architectures for run-time program validation,” in Proc. IEEE Int. Conf. Computer Design, Oct. 2008.