Programmable unit for metadata processing

Patent metadata

Field	Value
Publication number	US-10078763-B2
Application number	US-201514946229-A
Country	US
Kind code	B2
Filing date	Nov 19, 2015
Priority date	Nov 19, 2014
Publication date	Sep 18, 2018
Grant date	Sep 18, 2018

Abstract

A system and method for metadata processing that can be used to encode an arbitrary number of security policies for code running on a stored-program processor. This disclosure adds metadata to every word in the system and adds a metadata processing unit that works in parallel with data flow to enforce an arbitrary set of policies, such that metadata is unbounded and software programmable to be applicable to a wide range of metadata processing policies. This instant disclosure is applicable to a wide range of uses including safety, security, and synchronization.

First claim

The invention claimed is:

1. A computer-implemented method on a non-transitory medium for metadata processing, comprising executing on a processor the steps of:
providing a pipeline processor including a plurality of stages, wherein a final stage is a writeback stage;
defining a number of security policies on data flowing within the pipeline processor;
adding metadata tags to the data in a processor state;
introducing a programmable metadata processing unit (PUMP) immediately before the final stage working in parallel with the data, and wherein the PUMP does not create additional stalls in the pipeline processor;
moving metadata through the plurality of stages and the PUMP;
enforcing a set of policies such that the metadata is unbounded and software programmable and adapted to be applicable to a plurality of metadata processing policies; and
associating, indivisibly, a metadata tag with every word in each state of the pipeline processor.

2. The method of claim 1 , further comprising the step of:
caching, indivisibly, the metadata tag with every word in a plurality of caches, wherein the metadata tag is a pointer-sized tag and the pointer-sized tag is uninterpreted at a hardware level.

3. The method of claim 2 , further comprising the step of:
registering, indivisibly, the metadata tag with every word in a register file.

4. The method of claim 3 , wherein each metadata tag is a sufficient size to indirect to a data structure in a main memory.

5. The method of claim 3 , wherein the metadata tags are unbounded to enforce any number of policies at the same time.

6. The method of claim 5 , further comprising the step of:
determining, on every instruction, if an operation is allowed based, at least in part on, the metadata tags and if the operation is allowed, then calculating the metadata tags for a set of results.

7. The method of claim 6 , further comprising the step of:
checking if a rule cache exists in a PUMP rule cache operates in parallel with an arithmetic logic unit (ALU);
if the rule cache exists in the PUMP rule cache, then the rule provides metadata tag propagation; and
if the rule cache does not exist in the PUMP rule cache, then identifying a miss and allowing a software handler to calculate a new result and put the new result into the PUMP rule cache.

8. The method of claim 7 , further comprising the step of:
servicing the rule cache misses based on the plurality of metadata processing policies in a software miss handler.

9. The method of claim 8 , wherein the plurality of metadata processing policies includes at least one of the following:
a non-executable data and non-writable (NXD+NWC) policy using the metadata tags to distinguish code from data in memory and to protect against code injection attacks;
a memory safety policy defending all spatial and temporal violations in heap-allocated memory;
a control-flow integrity policy restricting indirect control transfers to only allowed edges in a control flow graph to prevent return-oriented-programming-style attacks; and
a fine-grained taint tracking policy to identify whether each word is tainted from a plurality of sources.

10. The method of claim 7 , further comprising the step of:
increasing an effective capacity of the PUMP rule cache and reducing compulsory misses by translating instructions treated similarly into a common instruction group identifier, and using the group identifier when indexing the PUMP rule cache.

11. The method of claim 10 , further comprising the step of:
representing a subset of pointer-sized tags in use at a time with a minimal number of bits to minimize on-chip area and energy overhead.

12. The method of claim 7 , further comprising the step of:
reducing the data transferred from off-chip memory using a short index to specify the words in a block that use the same tag, wherein the block is a cache line or a virtual memory page.

13. The method of claim 7 , further comprising the step of:
reducing a cost of composite policy miss handlers by performing at least the following (i) adding a component policy cache, and (ii) adding cache to translate a tuple of policy components into a composite policy tag.

14. A system for processing metadata free from a bound on a number of bits allocated to metadata and free from a bound on a number of policies simultaneously enforced comprising:
a pipeline processor including a plurality of stages, wherein a final stage is a writeback stage;
a Programmable Unit for Metadata Processing (PUMP) integrated as a pipeline stage immediately before the final stage working in parallel with metadata, and wherein the PUMP does not create additional stalls in the pipeline processor which is adapted to move metadata through a first stage, then through the PUMP, and then through the final stage.

15. The system of claim 14 , further comprising:
at least one microarchitecture optimization operatively connected with the PUMP, wherein the microarchitecture optimization is selected from a group comprising grouped instruction operation codes, tag compression, tag translation, and miss handler acceleration.

16. The system of claim 15 , further comprising:
a tag compression logic utilizing a spatial tag locality to compress tag bits, and after compression transfer the compressed tag bits to and from the off-chip memory.

17. The system of claim 15 , further comprising:
a tag translation logic to translate the tag bits between different levels of memory hierarchy.

18. The system of claim 15 , further comprising:
a plurality of tag checking and propagation rules defined in software and executable by the processor; and
a PUMP rule cache operating in parallel with every stage of the processor to minimize performance impact thereof.

19. A method for metadata processing on a non-transitory medium comprising the steps of:
enforcing an arbitrary set of security policies with a reduced instruction set computing (RISC) architecture on a pipeline processor including a plurality of stages, wherein a first stage is a fetch stage, a second stage is a decode stage, a third stage is an execute stage, a fourth stage is a memory stage, and a fifth stage is a writeback stage;
adding a metadata processing unit that works in parallel with data flow to enforce the arbitrary set of security policies, such that metadata is unbounded and software programmable to be applicable to a plurality of metadata processing policies, wherein the metadata processing unit is positioned between the fourth stage and the fifth stage and does not create additional stalls in the pipeline processor;
adding metadata tags to words in the processor;
determining, on every instruction, if an operation is allowed based, at least in part on, metadata tags and if the operation is allowed, then calculating the metadata tags for a set of results; and
associating, indivisibly, one metadata tag with every word in a main memory of the processor.

20. The method of claim 19 , further comprising the step of:
caching, indivisibly, the metadata tag with every word in a plurality of caches wherein the metadata tag is a pointer-sized tag and the pointer-sized tag is uninterpreted at a hardware level.

21. The method of claim 20 , further comprising the step of:
registering, indivisibly, the metadata tag with every word in a register file.

Assignees

• Bae Sys Inf & Elect Sys Integ
• Univ Pennsylvania
• BAE Systems Information and Electronic Systems Integration Incc

Inventors

• Chiricescu Silviu
• Dehon Andre
• Dhawan Udit

Classifications

• G06F12/0893

  Caches characterised by their organisation or structure · CPC title

• G06F21/64 Primary

  Protecting data integrity, e.g. using checksums, certificates or signatures · CPC title

• G06F2212/1041

  Resource optimization · CPC title

• G06F21/71 Primary

  to assure secure computing or processing of information · CPC title

• G06F2212/1016

  Performance improvement · CPC title