SECURING EXECUTION OF A PROGRAM

• US 20180068116A1
• Filed: 10/13/2017
• Published: 03/08/2018
• Est. Priority Date: 04/15/2015
• Status: Active Grant

• Current Assignee: Rambus Inc.
• Original Assignee: Inside Secure SA
• Inventors: Benchaalal, Othman, Dupaquis, Vincent
• Granted Patent: US 11,263,313 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/28 by checking the correct order of processing G06F11/08 - G06F11/26 take precedence; monitoring patterns of pulse trains H03K5/19
• CPC Class Codes: G06F 21/54 by adding security routines or objects to programs
• CPC Class Codes: G06F 2221/033 Test or assess software
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 9/004 for fault attacks
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

In a general aspect, a method can include: executing an operation of a program that loads an arbitrarily chosen value of an initial data item of a series of ordered data; executing a series of calculation operations distributed in the program, that calculate a current data item based on a preceding data item; performing a final calculation operation of the series of operations that calculates a final data item of the data series; and executing an operation of the program that detects a program execution error by comparing the current data item of the data series with an expected value of the current data item or the final data item, the final data item having an expected value that is independent of the number of data items in the data series and is calculated based on the current data item of the data series and a final compensation data item.

Claims

1. A method of executing a program by an electronic device, the method comprising:

executing an operation of the program that is configured to load an arbitrarily chosen value of an initial data item belonging to a series of ordered data,

executing a series of calculation operations distributed in the program, including calculation operations that are each configured to calculate a current data item of the series of ordered data based on a preceding data item of the data series,

performing a final calculation operation of the series of calculation operations to calculate a final data item of the data series, and

executing an error detection operation of the program configured to detect a program execution error by comparing the current data item of the series of ordered data with an expected value of the current data item or the final data item, the final data item having an expected value independent of a number of data items in the series of ordered data and being calculated by the final operation based on the current data item of the series of ordered data and a final compensation data item.

2. The method according to claim 1, wherein an expected value of a data item of the series of ordered data is:

calculated, by a module for calculating constants, during a pre-processing step for generating the program, and

used by the error detection operation and by the final calculation operation of the series of calculation operations.

3. The method of claim 1, wherein the expected value of the final data item is determined from the initial data item.

4. The method of claim 1, wherein the expected value of the final data item is set equal to a binary ones'"'"' complement of the initial data item.

5. The method of claim 1, wherein one of the calculation operations of the series of calculation operations is configured to determine one of the data items of the series or ordered data based on a rank of the one of the data items in the data series.

6. The method of claim 1, wherein one of the calculation operations of the series of calculation operations is configured to determine a data item of the series of ordered data by calculating a signature applied to the preceding data item of the data series.

7. The method of claim 1, wherein one of the calculation operations of the series of calculation operations is configured to determine a first data item of the data series based on a value of a variable specific to the program and a value of the preceding data item of the series of ordered data, and a subsequent calculation operation of the series of calculation operations is configured to determine a second data item of the data series, the second data item having an expected value independent of the variable specific to the program.

8. The method of claim 1, wherein a data item of the series of ordered data is obtained by a cyclic redundancy check calculation applied to the preceding data item of the series of ordered data.

9. The method of claim 1, wherein a data item of the series of ordered data is obtained by a modular arithmetic calculation applied to the preceding data item of the series of ordered, using, as a modulus, a prime number greater than a maximum value of the data items of the series or ordered data.

10. The method of claim 1, further comprising:

allocating respective distinct data series to a first function of the program and a second function of the program called by the first function,

upon returning to the first function following a call to, and execution of the second function, performing a calculation operation of the series of calculation operations that is applied to a data item of the distinct data series of the first function and to a calculated final data item of the distinct data series of the second function to obtain a third data item, and

performing another calculation operation of the series of calculation operations that is applied to the third data item to obtain a fourth data item having an expected value which is independent of an expected final data item of the distinct data series of the second function.

11. The method of claim 1, wherein the program includes an iterative processing loop implementing a first iteration counter varying in a first direction at each iteration, the method further comprising:

managing a second iteration counter varying in a second direction opposite to the first direction, such that a sum of a value of the first counter and a value of the second counter remains constant, and

in the iterative processing loop, performing a calculation operation of the series of calculation operations that is applied to a calculated data item of the series ordered data, and to a constant based on the sum of the value of the first counter and the value of the second counter, and performing another calculation operation applied to the expected value of the constant to obtain a fifth data item of the series of ordered data having an expected value which is independent of the expected value of the sum of the value of the first counter and the value of the second counter.

12. The method of claim 1, further comprising:

generating a file for declaring values of constants used by the method,

searching in source code or pre-processed code of the program for an instruction involving a comparison of the current data item of the data series with an expected value of the current data item,

calculating the expected value of the current data item based on the initial data item of the data series and a rank of the current data item of the data series, and

inserting, into the file for declaring values of constants, a constant having the calculated expected value of the current data item.

13. The method of claim 12, further comprising:

searching, in the source code of the program, for an instruction involving a final calculation operation of the series of calculation operations,

calculating a value of a final compensation data item to which the final calculation operation is applied, such that the final calculation operation applied to the final compensation data item provides an expected final data item of the data series, and

inserting a constant having the value of the final compensation data item into the file for declaring values of constants.

14. The method of claim 12, comprising the steps of:

searching, in the source code of the program, for a compensation instruction involving a calculation operation of a data item of the data series applied to a data item not belonging to the data series,

calculating a value of a compensation data item to which the calculation operation of the compensation instruction is applied, such that the calculating the value of the compensation data item produces a data item of the data series which is independent of an expected value of the data item not belonging to the data series, and

inserting a constant having the value of the compensation data item into the file for declaring values of constants.

15. A non-transitory computer program product having instructions stored thereon, the instructions, when executed by a processor, result in:

executing an operation of a program that is configured to load an arbitrarily chosen value of an initial data item belonging to a series of ordered data,

executing a series of calculation operations distributed in the program, including calculation operations that are each configured to calculate a current data item of the series of ordered data based on a preceding data item of the data series,

performing a final calculation operation of the series of calculation operations to calculate a final data item of the data series, and

executing an error detection operation of the program configured to detect a program execution error by comparing the current data item of the series of ordered data with an expected value of the current data item or the final data item, the final data item having an expected value independent of a number of data items in the series of ordered data and being calculated by the final operation based on the current data item of the series of ordered data and a final compensation data item.

16. The computer program product according to claim 15, wherein the calculation operations of the series of calculation operations and the error detection operation are included in one or more macros.