Techniques for metadata processing

• US 10,642,616 B2
• Filed: 06/16/2017
• Issued: 05/05/2020
• Est. Priority Date: 12/17/2015
• Status: Active Grant

• Current Assignee: Trustees Of The University Of Pennsylvania (University of Pennsylvania)
• Original Assignee: Charles Stark Draper Laboratory Incorporated
• Inventors: DeHon, Andre', Dhawan, Udit
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US15/624,878
• Publication Number:
  US 20170293563A1
• Time in Patent Office: 1,054 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 12/1458 by checking the subject access rights
• CPC Class Codes: G06F 15/78 comprising a single central processing unit
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 21/52 during program execution, e.g. stack integrity ; Preventing unwanted data erasure; Buffer overflow
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2212/1052 Security improvement
• CPC Class Codes: G06F 2212/402 Encrypted data
• CPC Class Codes: G06F 2212/452 Instruction code
• CPC Class Codes: G06F 9/30072 to perform conditional operations, e.g. using predicates or guards
• CPC Class Codes: G06F 9/30098 Register arrangements
• CPC Class Codes: G06F 9/30101 Special purpose registers
• CPC Class Codes: G06F 9/3867 using instruction pipelines

Abstract

Techniques are described for metadata processing that can be used to encode an arbitrary number of security policies for code running on a processor. Metadata may be added to every word in the system and a metadata processing unit may be used that works in parallel with data flow to enforce an arbitrary set of policies. In one aspect, the metadata may be characterized as unbounded and software programmable to be applicable to a wide range of metadata processing policies. Techniques and policies have a wide range of uses including, for example, safety, security, and synchronization. Additionally, described are aspects and techniques in connection with metadata processing in an embodiment based on the RISC-V architecture.

Claims

1. A method of processing instructions comprising:

receiving, for metadata processing, a current instruction with an associated metadata tag, said metadata processing being performed in a metadata processing domain isolated from a code execution domain including the current instruction;

determining, in the metadata processing domain and in accordance with the current instruction and metadata tags associated with the current instruction, whether a rule exists in a rule cache for the current instruction, said rule cache including rules on metadata used by said metadata processing to define allowed operations; and

responsive to determining no rule exists in the rule cache for the current instruction, performing rule cache miss processing in the metadata processing domain, wherein the rule cache miss processing includes performing first rule cache miss processing for a first set of one or more rules using a first rule cache miss handler that is a hardware-implemented rule cache miss handler generating outputs, the outputs including metadata tags used in forming a new rule for the current instruction triggering the rule cache miss processing.

2. The method of claim 1, wherein a composite policy includes multiple policies that are simultaneously enforced for the current instruction by the metadata processing, the composite policy including a first policy and a second policy, wherein the first policy includes the first set of one or more rules and the second policy includes a second set of one or more rules.

3. The method of claim 2, wherein the rule cache miss processing includes performing second rule cache miss processing for a second set of one or more rules using a second rule cache miss handler that is a software-implemented rule cache miss handler performing the second rule cache miss processing for the second set of rules by executing code of the software-implemented rule cache miss handler on a processor in the metadata processing domain.

4. The method of claim 3, wherein the first rule cache miss processing includes the hardware-implemented rule cache miss handler generating first outputs including first output metadata tags, and wherein the second rule cache miss processing includes the software-implemented rule cache miss handler generating second outputs including second output metadata tags.

5. The method of claim 4, wherein the rule cache miss processing includes generating composite results in accordance with the first outputs and the second outputs, said composite results including composite metadata tags.

6. The method of claim 5, wherein the rule cache miss processing includes:

generating the new rule for the current instruction, the new rule including input metadata tags in accordance with the current instruction, an opcode of the current instruction, and the composite metadata tags, wherein the composite metadata tags are output tags for the new rule; and

inserting the new rule into the rule cache.

7. The method of claim 6, wherein the input metadata tags and the opcode of the current instruction are provided as inputs to the hardware-implemented rule cache miss handler for use in the first rule cache miss processing and provided as inputs to the software-implemented rule cache miss handler for use in the second rule cache miss processing.

8. The method of claim 1, wherein the hardware-implemented rule cache miss handler performs the first rule cache miss processing using dedicated hardware.

9. The method of claim 1, wherein the first set of one or more rules include rules for any one or more of:

a memory safety policy, a control flow integrity policy, and a stack protection policy.

10. The method of claim 2, wherein the composite policy includes at least one policy having hardware-specified rules encoded and enforced using hardware and wherein the method includes performing the rule cache miss processing responsive to determining no rule exists in either the rule cache or the hardware-specified rules for the current instruction.

11. The method of claim 1, wherein a cache of tags includes a plurality of tags, and wherein the first rule cache miss processing includes the hardware-implemented rule cache miss handler allocating at least one new tag from the cache of tags, and wherein the method includes periodically executing code in the metadata processing domain to refill the cache of tags with new additional tags available for allocation by the hardware-implemented rule cache miss handler.

12. A method for performing processor-mediated data transfers between tagged and untagged data sources comprising:

executing, on a processor, a first instruction that loads first data from an untagged data source, said untagged data source including memory locations not having associated metadata tags;

tagging, by first hardware, the first data with a first metadata tag denoting the first data is untrusted and from a public data source, wherein the first data and the first metadata tag are stored in a first buffer; and

executing, on the processor, first code that triggers metadata processing using first one or more rules, wherein the metadata processing using the first one or more rules performs retagging that retags the first data to have a second metadata tag denoting the first data is trusted.

13. The method of claim 12, wherein the second metadata tag additionally denotes that the first data is from a public source.

14. The method of claim 12, wherein the first data having the second metadata tag is stored in a memory that is a tagged data source including memory locations each having an associated metadata tag.

15. The method of claim 14, wherein the memory is a trusted memory including data from one or more trusted data sources.

16. The method of claim 12, wherein the metadata processing is performed in a metadata processing domain isolated from a code execution domain including the first code.

17. The method of claim 16, wherein the first one or more rules are rules on metadata used by the metadata processing to define allowed operations.

18. The method of claim 12, wherein the first code includes one or more instructions and each of the one or more instructions has a special instruction tag denoting that said each instruction has authority to invoke the one or more rules that retags the first data to have the second metadata tag.

19. The method of claim 12, wherein the first data, having the first metadata tag, is encrypted, and the method further comprising:

decrypting, by executing one or more instructions on the processor, the first data having the first metadata tag and generating a decrypted form of the first data having the first metadata tag; and

performing validation processing by executing one or more additional instructions on the processor, said validation processing using digital signatures to ensure the decrypted form of the first data is valid, wherein said retagging is performed after successful validation processing of the first data.

20. The method of claim 12, wherein the first data having the second metadata tag is stored in a decrypted form in a first memory location of a tagged memory, and the method further comprises:

encrypting the first data to produce the first data in an encrypted form and generating a digital signature in accordance with the first data, wherein said encrypting and said generating are performed by executing additional code on the processor; and

executing, on the processor, a second instruction that stores the encrypted form of the first data from the first memory location of the tagged memory to a destination location of an untagged memory, wherein the encrypted form of the first data is stored in the destination location without an associated metadata tag and wherein the second metadata tag is removed by second hardware prior to storing the encrypted form of the first data in the destination location.

21. The method of claim 12, wherein, at a first point in time, the first data is stored in a first location of an untagged memory portion, and at a second point in time, the first data, having the first metadata tag, denoting that the first data is untrusted and from a public data source, is stored in a second location of a tagged memory portion, wherein said untagged memory portion and said tagged memory portion are included in a same memory serviced by a same memory controller, and wherein second metadata processing rules only allow the processor to perform operations that write data to the untagged memory portion when an associated metadata tag denotes that the data is public, and wherein direct memory operations from an external untagged source operating on untagged data are only allowed to access the untagged memory portion of the same memory.

22. The method of claim 21, wherein at least a portion of the second metadata processing rules further only allow the processor to perform operations that write data to the untagged memory portion when an associated metadata tag denotes that the data is public and additionally untrusted.

23. The method of claim 21, wherein the untagged data source is connected to a first interconnect fabric including only untagged data sources, wherein the first data with the second metadata tag is stored in a location of a memory connected to a second interconnect fabric including only tagged data sources.

24. The method of claim 23, wherein a second processor connected to the first interconnect fabric executes other instructions using untagged data from the untagged data sources and wherein said other instructions are executed without performing metadata processing and without using rules on metadata to enforce allowable operations, wherein execution of said other instructions by said second processor includes performing one or more operations including any of:

reading data from an untagged data source of the first interconnect fabric, and writing data to an untagged data source of the first interconnect fabric.

25. A system comprising:

a processor;

one or more tagged memories, wherein each memory location of the one or more tagged memories has an associated metadata tag;

one or more untagged memories including a first untagged memory, wherein memory locations of the one or more untagged memories do not have associated metadata tags;

a rule cache including rules on metadata used in performing metadata processing to define allowed operations in connection with instructions, wherein prior to executing a current instruction by the processor, metadata processing using one or more rules of the rule cache is performed to determine whether execution of the current instruction is allowed;

a first instruction stored in a computer readable medium, wherein the first instruction, when executed by the processor, loads first data from the first untagged memory into a data cache used by the processor, wherein the first data stored in the data cache has an associated first metadata tag;

a second instruction stored in a computer readable medium, wherein the second instruction, when executed by the processor, stores second data from the data cache to the first untagged memory, wherein the second data stored in the data cache has an associated second metadata tag;

a first hardware component that converts untagged data to tagged data used in the system by the processor, wherein responsive to execution of the first instruction, the first hardware component receives, from the first untagged memory, the first data without any associated metadata tag, and outputs the first data having the associated first metadata tag; and

a second hardware component that converts tagged data to untagged data, wherein responsive to execution of the second instruction, the second hardware component receives the second data having the associated second metadata tag and outputs the second data without any associated metadata tag.

26. The system of claim 25, wherein the first data without any associated metadata tag is encrypted and the first hardware component converts the first data to a decrypted form, performs validation processing of the first data using digital signatures, and upon successful validation processing, tags the first data to have the associated first metadata tag denoting that the first data is trusted;

and

wherein the second data having the second associated metadata tag is in a decrypted form and the second hardware component converts the second data to an encrypted form and generates a digital signature in accordance with the second data.

27. The system of claim 26, wherein the first hardware component tags the first data to have the associated first metadata tag denoting that the first data is trusted and also identifying that the first data is from a public source.

28. The system of claim 26, wherein one or more cryptographic key sets are any of encoded in hardware and stored in a memory, the one or more cryptographic key sets being used by the first hardware component in connection with performing decryption and validation processing and being used by the second hardware component in connection with performing encryption and creating digital signatures, wherein the first data identifies a particular one of the cryptographic key sets used by the first hardware component to decrypt the first data, and wherein the associated second metadata tag of the second data identifies a specific one of the cryptographic key sets used by the second hardware component to encrypt and sign the second data.

29. A method of processing a current instruction comprising:

receiving, for metadata processing, the current instruction; and

performing metadata processing for the current instruction in a metadata processing domain isolated from a code execution domain including the current instruction, said current instruction referencing a first memory location having a first metadata tag used in the metadata processing, said metadata processing for the current instruction including;

performing processing to retrieve the first metadata tag from memory;

prior to receiving the first metadata tag for the first memory location from the memory, determining a predicted value of the first metadata tag of the first memory location;

determining, using the predicted value of the first metadata tag of the first memory location, a first result metadata tag for a result operand of the current instruction; and

receiving, from the memory, the first metadata tag;

determining whether the first metadata tag matches the predicted value of the first metadata tag; and

responsive to determining the first metadata tag matches the predicted value of the first metadata tag, using the first result metadata tag as a final result metadata tag for the result operand.

30. The method of claim 29, wherein the metadata processing for the current instruction further comprises:

determining, in accordance with the current instruction and a set of input metadata tags for the current instruction, a first rule for the current instruction, wherein said first rule includes the predicted value of the first metadata tag of the first memory location and includes the first result metadata tag, said first rule being included in a rule cache used for metadata processing in the metadata processing domain; and

responsive to determining the first metadata tag does not match the predicted value of the first metadata tag, performing rule cache miss processing in the metadata processing domain for the current instruction.

31. The method of claim 30, wherein said rule cache miss processing in the metadata processing domain for the current instruction includes:

determining whether execution of the current instruction in the code execution domain is allowed;

responsive to determining execution of the current instruction in the code execution domain is allowed, generating a new rule for the current instruction, wherein said new rule is generated in accordance with the current instruction, the set of input metadata tags, and the first metadata tag; and

inserting the new rule into the rule cache used for metadata processing in the metadata processing domain.

32. The method of claim 30, wherein, prior to performing the metadata processing for the current instruction, the method includes performing other rule cache miss processing for another instance of the current instruction:

executing code of a rule cache miss handler that is executed in the metadata processing domain and that generates the first rule including the predicted value; and

inserting the first rule with the predicted value into the rule cache.

33. The method of claim 30, wherein the set of other input metadata tags include a plurality of other metadata tags for the current instruction, said set of other metadata input tags including metadata tags for any of:

a program counter, the current instruction, and an input operand of the current instruction.

34. The method of claim 30, wherein said result operand is a destination memory location or a destination register storing results of executing the current instruction.

35. The method of claim 30, wherein the instruction is processed in accordance with a plurality of stages including a first stage and a second stage wherein the first stage occurs prior to the second stage, wherein the predicted value of the first metadata tag of the first memory location is determined in the first stage, and the second stage includes performing said determining whether the first metadata tag matches the predicted value of the first metadata tag, and the second stage also includes performing said rule cache miss processing in the metadata processing domain for the current instruction responsive to determining the first metadata tag does not match the predicted value of the first metadata tag.

36. The method of claim 30, wherein the rule cache is configurable to operate in either a prediction mode or a normal processing mode in accordance with a prediction selector mode.

37. The method of claim 36, wherein, when the rule cache is configured to operate in said prediction mode, the rule cache generates first outputs in accordance with the first rule, the first outputs including a metadata tag for a program counter of a next instruction, the first result metadata tag for the result operand of the current instruction, and the predicted value of the first metadata tag as an output of the first stage, and wherein, when the rule cache is configured to operate in said normal processing mode, the rule cache generates second outputs in accordance with a second rule different from the first rule, wherein the second outputs do not include the predicted value of the first metadata tag, and the second outputs include metadata tags for result operand of the current instruction and for the program counter of the next instruction.

38. The method of claim 36, wherein the rule cache uses a first version of rules of a first policy when operating in the prediction mode and otherwise uses a second version of rules of the first policy when operating in the normal processing mode, and wherein the first rule is included in the first version of rules and the second rule is included in the second version of rules.

39. A system comprising:

a pipeline processor including a plurality of pipeline stages, said plurality of stages including a memory stage and a writeback stage;

a programmable unit for metadata processing (PUMP) that operates prior to completion of the memory stage, wherein the PUMP performs metadata processing for a current instruction referencing a first memory location having a first metadata tag used in the metadata processing, wherein the PUMP receives first inputs including first metadata tags for the current instruction and wherein the PUMP generates first outputs provided as inputs to the writeback stage, the first outputs including a predicted value of the first metadata tag of the first memory location and a first result metadata tag for a result operand of the current instruction, wherein the first result metadata tag is determined by the PUMP in accordance with the predicted value of the first metadata tag for the first memory location; and

hardware components of said writeback stage that determine whether the first metadata tag for the first memory location matches the predicted value of the first metadata tag, and that use the first result metadata tag as a final result metadata tag for the result operand when the first metadata tag matches the predicted value of the first metadata tag.

40. The system of claim 39, wherein the PUMP is a first PUMP that operates simultaneously with the memory stage and further operates in a prediction mode and determines the predicted value of the first metadata tag of the first memory location, and wherein the system includes a second PUMP that operates in a normal, non-prediction mode and does not determine any predicted value for the first metadata tag of the first memory location, the second PUMP integrated between the memory stage and the writeback stage.

41. The system of claim 40, wherein the first PUMP uses a first version of rules of a first policy for use when operating in the prediction mode, the second PUMP uses a second version of rules of the first policy for use when operating in the normal, non-prediction mode, the first PUMP determines the first outputs in accordance with a first rule from the first version, the second PUMP determines second outputs in accordance with a second rule from the second version, said second outputs include a second result metadata tag for the first memory location and said second outputs are provided as inputs to the writeback stage, and wherein the hardware components of the write back stage additionally use the second result metadata tag as the final result metadata tag for the result operand when the first metadata tag does not match the predicted value.

42. A non-transitory computer readable medium comprising code stored thereon that, when executed, performs a method of processing instructions comprising:

receiving, for metadata processing, a current instruction with an associated metadata tag, said metadata processing being performed in a metadata processing domain isolated from a code execution domain including the current instruction;

determining, in the metadata processing domain and in accordance with the current instruction and metadata tags associated with the current instruction, whether a rule exists in a rule cache for the current instruction, said rule cache including rules on metadata used by said metadata processing to define allowed operations; and

responsive to determining no rule exists in the rule cache for the current instruction, performing rule cache miss processing in the metadata processing domain, wherein the rule cache miss processing includes performing first rule cache miss processing for a first set of one or more rules using a first rule cache miss handler that is a hardware-implemented rule cache miss handler generating outputs, the outputs including metadata tags used in forming a new rule for the current instruction triggering the rule cache miss processing.

43. A system comprising:

one or more processors; and

a memory comprising code stored therein that, when executed by at least a first of the one or more processors, performs a method of processing instructions comprising;

receiving, for metadata processing, a current instruction with an associated metadata tag, said metadata processing being performed in a metadata processing domain isolated from a code execution domain including the current instruction;

determining, in the metadata processing domain and in accordance with the current instruction and metadata tags associated with the current instruction, whether a rule exists in a rule cache for the current instruction, said rule cache including rules on metadata used by said metadata processing to define allowed operations; and

responsive to determining no rule exists in the rule cache for the current instruction, performing rule cache miss processing in the metadata processing domain, wherein the rule cache miss processing includes performing first rule cache miss processing for a first set of one or more rules using a first rule cache miss handler that is a hardware-implemented rule cache miss handler generating outputs, the outputs including metadata tags used in forming a new rule for the current instruction triggering the rule cache miss processing.

44. A non-transitory computer readable medium comprising code stored thereon that, when executed, performs a method of processor-mediated data transfers between tagged and untagged data sources comprising:

executing, on a processor, a first instruction that loads first data from an untagged data source, said untagged data source including memory locations not having associated metadata tags;

tagging, by first hardware, the first data with a first metadata tag denoting the first data is untrusted and from a public data source, wherein the first data and the first metadata tag are stored in a first buffer; and

executing, on the processor, first code that triggers metadata processing using first one or more rules, wherein the metadata processing using the first one or more rules performs retagging that retags the first data to have a second metadata tag denoting the first data is trusted.

45. A non-transitory computer readable medium comprising code stored thereon that, when executed, performs a method of processing a current instruction comprising:

receiving, for metadata processing, the current instruction; and

performing metadata processing for the current instruction in a metadata processing domain isolated from a code execution domain including the current instruction, said current instruction referencing a first memory location having a first metadata tag used in the metadata processing, said metadata processing for the current instruction including;

performing processing to retrieve the first metadata tag from memory;

prior to receiving the first metadata tag for the first memory location from the memory, determining a predicted value of the first metadata tag of the first memory location;

determining, using the predicted value of the first metadata tag of the first memory location, a first result metadata tag for a result operand of the current instruction; and

receiving, from the memory, the first metadata tag;

determining whether the first metadata tag matches the predicted value of the first metadata tag; and

responsive to determining the first metadata tag matches the predicted value of the first metadata tag, using the first result metadata tag as a final result metadata tag for the result operand.