Safe to execute verification of software

• US 6,128,774 A
• Filed: 10/28/1997
• Issued: 10/03/2000
• Est. Priority Date: 10/28/1997
• Status: Expired due to Fees

• Current Assignee: George C. Necula, Peter Lee
• Original Assignee: George C. Necula, Peter Lee
• Inventors: Lee, Peter, Necula, George C.
• Primary Examiner(s): Hafiz, Taria R.
• Assistant Examiner(s): Pender, Jr., Michael J.
• Application Number:
  US08/959,730
• Time in Patent Office: 1,071 Days
• Field of Search: 395/705, 395/708, 395/704
• US Class Current: 717/146
• CPC Class Codes: G06F 21/51 at application loading time, e.g. accepting, rejecting, starting or inhibiting executable software based on integrity or source reliability
• CPC Class Codes: G06F 2221/2149 Restricted operating environment
• CPC Class Codes: G06F 9/44589 Program code verification, e.g. Java bytecode verification, proof-carrying code high-level semantic checks G06F8/43; testing and debugging software G06F11/36

Abstract

A computer-implemented method of verifying that untrusted software supplied by a code producer is safe to execute by a code consumer. The method includes the step of defining a safety policy that specifies safe operating conditions of the untrusted software on the code consumer. The method also includes the steps of generating a safety predicate for the untrusted software that determines if execution by the code consumer of the untrusted software will violate said safety policy and generating a safety proof that proves that said safety predicate is valid. The method further includes the step of validating the untrusted software for execution based on said safety proof and said safety predicate.

Claims

1. A computer-implemented method of verifying that untrusted software supplied by a code producer is safe to execute by a code consumer, comprising the steps of:

defining a safety policy that specifies safe operating conditions of the untrusted software on the code consumer;

generating a safety predicate for the untrusted software that determines if execution by the code consumer of the untrusted software will violate said safety policy;

generating a safety proof that proves that said safety predicate is valid; and

validating the untrusted software for execution based on said safety proof and said safety predicate prior to execution of the untrusted software.

2. The computer-implemented method of claim 1 further comprising the steps of:

installing the untrusted software on the code consumer if the untrusted software was successfully validated by said validating step; and

discarding the untrusted software if the untrusted software was unsuccessfully validated by said validating step.

3. The computer-implemented method of claim 1 wherein said step of generating a safety predicate includes the step of adding said safety predicate to the untrusted software.

4. The computer-implemented method of claim 3 further comprising the step of extracting said safety predicate from the untrusted software.

5. The computer-implemented method of claim 1 further comprising the step of adding annotations to the untrusted software.

6. The computer-implemented method of claim 1 wherein said step of generating a safety predicate includes the steps of:

checking a plurality of safety properties of the untrusted software; and

checking the untrusted software for instructions that may violate said safety policy.

7. The computer-implemented method of claim 1 wherein said step of validating the untrusted software includes the steps of:

verifying that each inference step in said proof is a valid instance of axioms and rules in said safety policy; and

verifying that said proof proves said safety predicate.

8. The computer-implemented method of claim 1 wherein said step of generating a safety predicate includes the steps of:

translating the untrusted software to a stream of instructions in a generic intermediate language; and

producing said safety predicate by executing said intermediate language instruction stream.

9. An apparatus for verifying that software supplied by a code producer is safe to execute by a code consumer, comprising:

a predicate generator module responsive to annotated untrusted software, said generator module for generating a safety predicate;

a proof generator module responsive to said safety predicate, said proof generator module for generating a safety proof; and

a proof checker module responsive to said safety predicate and said safety proof, said proof checker module for verifying that said safety predicate complies with a safety policy defined by the code consumer prior to execution of the software.

10. The apparatus of claim 9 wherein said predicate generator module includes:

a language dependent parser module having as an input said annotated untrusted software, said parser module for translating said untrusted software to a stream of instructions in a generic intermediate language; and

a symbolic evaluator module responsive to said parser module and a configuration file, said symbolic evaluator module for generating said safety predicate.

11. An apparatus for verifying that software supplied by a code producer is safe to execute by a code consumer, comprising:

means for generating a safety predicate for untrusted software;

means for generating a safety proof from said safety predicate; and

means for verifying that said safety predicate complies with a safety policy defined by the code consumer based on said safety predicate and said safety proof prior to execution of the untrusted software.

12. A computer system, comprising:

a processor;

at least one input device for receiving untrusted software;

a communication link enabling communications between said processor and said input device; and

a memory coupled to said processor and storing a set of ordered data and a set of instructions which, when executed by said processor, cause said processor to perform the steps of;

generating a safety predicate for said untrusted software for determining if execution by a code consumer of said untrusted software will violate a safety policy defined by said code consumer;

generating a safety proof that proves that said safety predicate is valid; and

validating said untrusted software for execution based on said safety proof and said safety predicate prior to execution of the untrusted software.

13. The system of claim 12 wherein said memory stores an additional set of ordered data and instructions which, when executed by said processor, cause said processor to perform the additional steps of:

installing said untrusted software on said code consumer if said untrusted software was successfully validated by said validating step; and

discarding said untrusted software if said untrusted software was unsuccessfully validated by said validating step.

14. The system of claim 12 wherein said memory stores an additional set of ordered data and instructions which, when executed by said processor, cause said processor to perform the step of adding said safety predicate to said untrusted software.

15. The system of claim 14 wherein said memory stores an additional set of ordered data and instructions which, when executed by said processor, cause said processor to perform the additional step of extracting said safety predicate from said untrusted software.

16. The system of claim 12 wherein said memory stores an additional set of ordered data and instructions which, when executed by said processor, cause said processor to perform the additional step of adding annotations to said untrusted software.

17. The system of claim 12 wherein said memory stores an additional set of ordered data and instructions which, when executed by said processor, cause said processor to perform the step of generating a safety predicate by performing the steps of:

checking a plurality of safety properties of said untrusted software; and

checking said untrusted software for instructions that may violate said safety policy.

18. The system of claim 12 wherein said memory stores an additional set of ordered data and instructions which, when executed by said processor, cause said processor to perform said step of validating said untrusted software by performing the steps of:

verifying that each inference step in said proof is a valid instance of axioms and rules in said safety policy; and

verifying that said proof proves said safety predicate.

19. The system of claim 12 wherein said memory stores an additional set of ordered data and instructions which, when executed by said processor, cause said processor to perform said step of generating a safety predicate by performing the steps of:

translating said untrusted software to a stream of instructions in a generic intermediate language; and

producing said safety predicate by executing said intermediate language instruction stream.

20. A computer-readable medium having stored thereon instructions which, when executed by a processor, cause said processor to perform the steps of:

generating a safety predicate for determining if execution by a code consumer of untrusted software will violate a safety policy defined by said code consumer;

generating a safety proof that proves that said safety predicate is valid; and

validating said untrusted software for execution based on said safety proof and said safety predicate prior to execution of the untrusted software.

21. The computer-readable medium of claim 20 having stored thereon instructions which, when executed by said processor, cause said processor to perform the additional steps of:

installing said untrusted software on said code consumer if said untrusted software was successfully validated by said validating step; and

discarding said untrusted software if said untrusted software was unsuccessfully validated by said validating step.

22. The computer-readable medium of claim 20 having stored thereon additional instructions which, when executed by said processor, cause said processor to perform the step of adding said safety predicate to said untrusted software.

23. The computer-readable medium of claim 22 having stored thereon additional instructions which, when executed by said processor, cause said processor to perform the additional step of extracting said safety predicate from said untrusted software.

24. The computer-readable medium of claim 20 having stored thereon additional instructions which, when executed by said processor, cause said processor to perform the additional step of adding annotations to said untrusted software.

25. The computer-readable medium of claim 20 having stored thereon additional instructions which, when executed by said processor, cause said processor to perform the step of generating a safety predicate by performing the steps of:

checking a plurality of safety properties of said untrusted software; and

checking said untrusted software for instructions that may violate said safety policy.

26. The computer-readable medium of claim 20 having stored thereon additional instructions which, when executed by said processor, cause said processor to perform said step of validating said untrusted software by performing the steps of:

verifying that each inference step in said proof is a valid instance of axioms and rules of said safety policy; and

verifying that said proof proves said safety predicate.

27. The computer-readable medium of claim 20 having stored thereon additional instructions which, when executed by said processor, cause said processor to perform said step of generating a safety predicate by performing the steps of:

translating said untrusted software to a stream of instructions in a generic intermediate language; and

producing said safety predicate by executing said intermediate language instruction stream.

28. A computer-readable medium having stored thereon instructions which, when executed by a code consumer, cause said code consumer to perform the steps of:

defining a safety policy that specifies safe operating conditions of untrusted software on the code consumer;

generating a safety predicate that determines if execution by the code consumer of said untrusted software will violate said safety policy; and

validating said untrusted software for execution based on a safety proof and said safety predicate prior to execution of untrusted software.

29. A computer-readable medium having stored thereon instructions which, when executed by a proof producer, cause said proof producer to perform the step of explicitly generating a safety proof that proves that a safety predicate is valid prior to execution of untrusted software.