Method and apparatus for software integrity protection using timed executable agents

• US 20060090209A1
• Filed: 10/27/2004
• Published: 04/27/2006
• Est. Priority Date: 10/27/2004
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Garay, Juan A., Huelsbergen, Lorenz Francis
• Granted Patent: US 8,887,287 B2
• Time in Patent Office: Days
• US Class Current: 726/26
• CPC Class Codes: G06F 21/57 Certifying or maintaining trusted computer platforms, e.g. secure boots or power-downs, version controls, system software checks, secure updates or assessing vulnerabilities
• CPC Class Codes: G06F 21/577 Assessing vulnerabilities and evaluating computer system security
• CPC Class Codes: G06F 2221/2103 Challenge-response
• CPC Class Codes: G06F 2221/2151 Time stamp

Abstract

A method and apparatus are disclosed for evaluating the security of at least one client. An executable program is executed by the client being evaluated. A result is received from the executable program and an evaluation of the result indicates whether the client has been corrupted. The executable program is one of a plurality of possible programs. The result may be evaluated based on an elapsed time between when the executable program is provided to the client and when the result is received. The executable program may include at least one function that writes to a memory of the client. A program blinding technique is also disclosed to generate executable programs.

Claims

1. A method for evaluating the security of at least one client, comprising:

providing at least one executable program to be executed by said client, wherein said at least one executable program is one of a plurality of possible programs;

receiving a result from said at least one executable program; and

determining whether said client has been corrupted based on an evaluation of said result.

2. The method of claim 1, wherein said evaluation of said result includes evaluating an elapsed time between when said at least one executable program is provided to said client and when said result is received.

3. The method of claim 1, wherein said at least one executable program is selected from said plurality of possible programs.

4. The method of claim 1, wherein said at least one executable program is randomly generated.

5. The method of claim 1, wherein an analysis of said at least one executable program takes significantly longer than execution of said at least one executable program.

6. The method of claim 1, wherein said at least one executable program includes an irreducible flow construct.

7. The method of claim 1, wherein said at least one executable program includes at least one function that evaluates an undecidable property of said function.

8. The method of claim 1, wherein said at least one executable program includes at least one function that has a time complexity for being analyzed by a potential adversary that violates a time constraint for receiving said result.

9. The method of claim 1, wherein said at least one executable program is generated using a program blinding technique.

10. The method of claim 1, wherein said at least one executable program includes one or more operations that write to a memory of said client.

11. The method of claim 1, wherein said at least one executable program includes a plurality of programs that communicate over time using at least one function that writes to a memory location of said client.

12. The method of claim 1, wherein said at least one executable program includes a plurality of programs that perform a pseudo-random permutation of a memory of said client, evaluate one or more locations of said memory;

and restore said memory to a desired state.

13. A method for evaluating the security of at least one client, comprising:

providing at least one executable program to be executed by said client, said at least one executable program including at least one function that writes to a memory of said client;

receiving a result from said at least one executable program; and

determining whether said client has been corrupted based on an evaluation of said result.

14. The method of claim 13, wherein said at least one executable program is selected from said plurality of possible programs.

15. The method of claim 13, wherein said at least one executable program is randomly generated.

16. The method of claim 13, wherein said at least one executable program includes a plurality of programs that communicate over time using said at least one function that writes to a memory location of said client.

17. The method of claim 13, wherein said at least one executable program includes a plurality of programs that perform a pseudo-random permutation of a memory of said client, evaluates one or more locations of said memory;

and restoring said memory to a desired state.

18. A method for evaluating the security of at least one client, comprising:

providing at least one executable program to be executed by said client;

receiving a result from said at least one executable program;

determining whether said client has been corrupted based on an evaluation of said result; and

evaluating an elapsed time between when said at least one executable program is provided to said client and when said result is received.

19. The method of claim 18, wherein said at least one executable program is selected from said plurality of possible programs.

20. The method of claim 18, wherein said at least one executable program is randomly generated.

21. A method for generating a target program, comprising:

obtaining a first program; and

combining said first program with a random program to generate said target program, wherein said target program inherits one or more properties of said first program.

22. The method of claim 21, wherein said combining step further comprises the step of interleaving one or more instructions from said first program and said random program.

23. The method of claim 21, wherein said target program is used to evaluate security of at least one client.

24. An apparatus for evaluating the security of at least one client, comprising:

a memory; and

at least one processor, coupled to the memory, operative to;

provide at least one executable program to be executed by said client, wherein said at least one executable program is one of a plurality of possible programs;

receive a result from said at least one executable program; and

determine whether said client has been corrupted based on an evaluation of said result.

25. The apparatus of claim 24, wherein said evaluation of said result includes evaluating an elapsed time between when said at least one executable program is provided to said client and when said result is received.

26. The apparatus of claim 24, wherein said at least one executable program includes one or more operations that write to a memory of said client.

27. The apparatus of claim 24, wherein said at least one executable program includes a plurality of programs that communicate over time using at least one function that writes to a memory location of said client.

28. An apparatus for generating a target program, comprising:

a memory; and

at least one processor, coupled to the memory, operative to;

obtain a first program; and

combine said first program with a random program to generate said target program, wherein said target program inherits one or more properties of said first program.

29. The apparatus of claim 28, wherein said combining step further comprises the step of interleaving one or more instructions from said first program and said random program.

30. The apparatus of claim 28, wherein said target program is used to evaluate security of at least one client.

31. An article of manufacture for evaluating the security of at least one client, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

providing at least one executable program to be executed by said client, wherein said at least one executable program is one of a plurality of possible programs;

receiving a result from said at least one executable program; and

determining whether said client has been corrupted based on an evaluation of said result.