Anomalous Path Detection - Revision history

Jcmartinez: /* Motivation */

2012-03-28T18:35:12Z

Motivation

← Older revision		Revision as of 18:35, 28 March 2012
Line 14:		Line 14:
	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.		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.

		+
		+	== Our approach ==
		+
		+	we introduce a novel approach of protecting program execution at the micro-architectural level. We propose to monitor control-flow transfers and execution paths at the super block granularity. At each checking point (indirect branch site), dynamic program execution information is compared against a full record set (FRS) stored in a secure memory region, including legitimate target addresses, execution paths, and size of the super block. In addition, behavior reference for future program execution is also prefetched for later monitoring. To enable fast validation, we consider introducing a cache architecture for the FRS in the memory. As branch prediction schemes have been widely adopted in embedded processors, the on-chip branch target buffer (BTB) can be used as a perfect cache for the FRS.
		+
		+	We propose a mechanism to ensure security for the BTB, i.e., avoiding any possible pollution from the tampered memory. We find that the validation mechanism only needs to be activated for those indirect branches that are mis-predicted by the BTB, in terms of direction, address, or execution history. The rare access of the external FRS results in much less performance degradation than other hardware schemes. The modification to the processor architecture is minor on top of the branch prediction structure and is transparent to the upper operating system and programs. Thus, legacy code can run on the secure processor without recompilations.

	== Extending the BTB ==		== Extending the BTB ==

Jcmartinez: /* Architectural Support */

2012-03-28T18:31:07Z

Architectural Support

← Older revision		Revision as of 18:31, 28 March 2012
Line 24:		Line 24:

	== Architectural Support ==		== Architectural Support ==
		+	[[File:architecture.png \|thumb\|right\|350px\|The architecture support in processor pipeline for control flow validation]]
		+	For every indirect branch instruction, the BPC is sent to the BTB during the fetch stage. After the execution stage, the dynamic information extracted, including next target PC (NTPC), BHSR, PBPC, and SIZE is also sent to the BTB for validation. On any mis-prediction, the full record set (FRS) in the secure memory is accessed, and the corresponding indirect control signature (ICS) is brought into the processor. With the expected path vector fetched into the processor pipeline, the program execution is monitored at run-time on a basic block basis.

	== People ==		== People ==

Jcmartinez: /* People */

2012-03-28T18:25:12Z

People

← Older revision		Revision as of 18:25, 28 March 2012
Line 22:		Line 22:

	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.		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 ==		== People ==

Jcmartinez: /* Extending the BTB */

2012-03-28T18:24:36Z

Extending the BTB

← Older revision		Revision as of 18:24, 28 March 2012
Line 17:		Line 17:
	== Extending the BTB ==		== Extending the BTB ==
	[[File:preditor.png \|thumb\|right\|350px\|Regular branch prediction flow enhanced with security features]]		[[File:preditor.png \|thumb\|right\|350px\|Regular branch prediction flow enhanced with security features]]
-	When an instruction is fetched from the instruction memory (in IF stage), the same PC address is used to access the BTB. A hit at this point indicates that the instruction to be executed is a control instruction. The predicted target PC (TPC) in BTB is then used as the next PC (NPC) to fetch a new instruction in the next pipeline stage (ID), rather than waiting until the later stage to use the NPC computed in EX stage for fetching instruction, avoiding branch stalls. Meanwhile, according to the instruction type, a direction prediction or computation is performed. If the branch is computed to be taken (direction hit), the TPC from the BTB will be compared with the computed NPC in the EX stage. If these two values match (address hit), both the branch direction and the target prediction are correct. However, one more validation has to be done for indirect control instructions in our approach.
-
	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 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	+	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.
-	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	+	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.
-	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.	+

	== People ==		== People ==

Jcmartinez: /* Extending the BTB */

2012-03-28T18:22:39Z

Extending the BTB

← Older revision		Revision as of 18:22, 28 March 2012
Line 17:		Line 17:
	== Extending the BTB ==		== Extending the BTB ==
	[[File:preditor.png \|thumb\|right\|350px\|Regular branch prediction flow enhanced with security features]]		[[File:preditor.png \|thumb\|right\|350px\|Regular branch prediction flow enhanced with security features]]
-	~~Fig~~. ~~4 illustrates~~ the ~~branch prediction flow using~~ a BTB in a ~~simple five-~~stage ~~pipeline~~	+	When an instruction is fetched from the instruction memory (in IF stage), the same PC address is used to access the BTB. A hit at this point indicates that the instruction to be executed is a control instruction. The predicted target PC (TPC) in BTB is then used as the next PC (NPC) to fetch a new instruction in the next pipeline stage (ID), rather than waiting until the later stage to use the NPC computed in EX stage for fetching instruction, avoiding branch stalls. Meanwhile, according to the instruction type, a direction prediction or computation is performed. If the branch is computed to be taken (direction hit), the TPC from the BTB will be compared with the computed NPC in the EX stage. If these two values match (address hit), both the branch direction and the target prediction are correct. However, one more validation has to be done for indirect control instructions in our approach.
-	~~architecture~~. ~~The solid objects~~ and ~~lines~~ are for the ~~regular branch~~ prediction ~~scheme~~. The	+
-	~~flow~~ is also ~~extended~~ with ~~some enhancements for control flow transfer and execution path~~	+	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.
-	~~validation~~, ~~as shown in dashed lines~~ and ~~objects, which will replace~~ the ~~original operations~~.	+	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.

	== People ==		== People ==

Jcmartinez: /* Extending the BTB */

2012-03-28T18:19:46Z

Extending the BTB

← Older revision		Revision as of 18:19, 28 March 2012
Line 16:		Line 16:

	== Extending the BTB ==		== Extending the BTB ==
-	[[File:preditor.png \|thumb\|right\|350px\|~~Microgrid for a community~~]]	+	[[File:preditor.png \|thumb\|right\|350px\|Regular branch prediction flow enhanced with security features]]
	Fig. 4 illustrates the branch prediction flow using a BTB in a simple five-stage pipeline		Fig. 4 illustrates the branch prediction flow using a BTB in a simple five-stage pipeline
	architecture. The solid objects and lines are for the regular branch prediction scheme. The		architecture. The solid objects and lines are for the regular branch prediction scheme. The

Jcmartinez: /* Extending the BTB */

2012-03-28T18:19:04Z

Extending the BTB

← Older revision		Revision as of 18:19, 28 March 2012
Line 16:		Line 16:

	== Extending the BTB ==		== Extending the BTB ==
-	[[File:~~Preditor~~.png \|thumb\|right\|350px\|Microgrid for a community]]	+	[[File:preditor.png \|thumb\|right\|350px\|Microgrid for a community]]
	Fig. 4 illustrates the branch prediction flow using a BTB in a simple five-stage pipeline		Fig. 4 illustrates the branch prediction flow using a BTB in a simple five-stage pipeline
	architecture. The solid objects and lines are for the regular branch prediction scheme. The		architecture. The solid objects and lines are for the regular branch prediction scheme. The

Jcmartinez: /* Extending the BTB */

2012-03-28T18:18:18Z

Extending the BTB

← Older revision		Revision as of 18:18, 28 March 2012
Line 16:		Line 16:

	== Extending the BTB ==		== Extending the BTB ==
-	[[File:~~MicrogridScheme~~.png \|thumb\|right\|350px\|Microgrid for a community]]	+	[[File:Preditor.png \|thumb\|right\|350px\|Microgrid for a community]]
	Fig. 4 illustrates the branch prediction flow using a BTB in a simple five-stage pipeline		Fig. 4 illustrates the branch prediction flow using a BTB in a simple five-stage pipeline
	architecture. The solid objects and lines are for the regular branch prediction scheme. The		architecture. The solid objects and lines are for the regular branch prediction scheme. The

Jcmartinez: /* Extending the BTB */

2012-03-28T18:12:57Z

Extending the BTB

← Older revision		Revision as of 18:12, 28 March 2012
Line 16:		Line 16:

	== Extending the BTB ==		== Extending the BTB ==
-		+	[[File:MicrogridScheme.png \|thumb\|right\|350px\|Microgrid for a community]]
	Fig. 4 illustrates the branch prediction flow using a BTB in a simple five-stage pipeline		Fig. 4 illustrates the branch prediction flow using a BTB in a simple five-stage pipeline
	architecture. The solid objects and lines are for the regular branch prediction scheme. The		architecture. The solid objects and lines are for the regular branch prediction scheme. The

Jcmartinez: /* Extending the BTB */

2012-03-28T18:12:10Z

Extending the BTB

← Older revision		Revision as of 18:12, 28 March 2012
Line 16:		Line 16:

	== Extending the BTB ==		== Extending the BTB ==
		+
		+	Fig. 4 illustrates the branch prediction flow using a BTB in a simple five-stage pipeline
		+	architecture. The solid objects and lines are for the regular branch prediction scheme. The
		+	flow is also extended with some enhancements for control flow transfer and execution path
		+	validation, as shown in dashed lines and objects, which will replace the original operations.

	== People ==		== People ==