CN107491703A - The merging method of random hamiltonian circuit topological structure in chip top-layer overcoat - Google Patents

Abstract

The present invention relates to chip top-layer metal protection layer generation technique, to cause two or more random hamiltonian circuits generated to can be merged into a big loop, so that the generation of the random hamiltonian circuit of large area is simpler.Therefore, of the invention, the merging method of random hamiltonian circuit topological structure, step are as follows in chip top-layer overcoat：1) merging type is determined；2) travel direction merges；3) cell matrix using rectangular element loop array, loop a and loop b as random hamiltonian circuit to be generated；4) the square element loop needed for the extension of the row of generation one loop；5) newly-generated loop is using as new loop c；6) repeat step 4 and step 5, until the space that merges between a and b is completely filled with；7) solve and terminate.Present invention is mainly applied to chip top-layer metal protection layer to generate occasion.

Description

Merging method of stochastic Hamiltonian loop topology in chip top protection layer

technical field

The invention relates to a technology for generating a metal protective layer on the top layer of a chip, in particular to a method for merging topological structures of a random Hamiltonian circuit in the protective layer on the top layer of a chip.

Background technique

At present, physical intrusion attacks represented by Focused Ion beam (FIB) and micro-probe attacks seriously threaten the information security of integrated circuit chips. The existing mainstream anti-attack means to deal with FIB and micro-probe attacks still use the top metal protection layer as the attack-aware structure. There are many kinds of graph topological structures of the top metal protective layer, and the protective layer based on random Hamiltonian circuit has become the mainstream protective layer graph structure because of its complex graph topology and difficult to identify.

In 2012, Sebastien Briais of the French Secure-IC company proposed a random Hamiltonian circuit foundation generation algorithm suitable for the protective layer in the document "3D hardware canaries" - Cycle Merging algorithm (CycleMerging, CM). Subsequent research on the random Hamiltonian circuit generation algorithm is based on the optimization of this algorithm.

references

1. Briais S, Caron S, Cioranesco J M, et al. 3D hardware canaries[M]. Cryptographic Hardware and Embedded Systems–CHES 2012. Springer Berlin Heidelberg, 2012: 1-22.

Contents of the invention

In order to overcome the deficiencies in the prior art, the present invention aims to propose a merging algorithm suitable for random Hamiltonian circuits, so that two or more generated random Hamiltonian circuits can be merged into one large circuit, thus making large-area The generation of random Hamiltonian circuits is simpler. For this reason, the technical scheme that the present invention adopts is, the merging method of random Hamiltonian circuit topological structure in the top protection layer of the chip, the steps are as follows:

1) Determine the type of merging. If the width direction is horizontal merging, then based on the cyclic merging algorithm, generate two random Hamiltonian circuits a and b with the same height H; or select a random Hamiltonian circuit with the same Two loops a and b of height H; if the height direction is to be merged vertically, two loops a and b with the same width W need to be generated or selected;

2) If merging in the width direction, place loop b on the right side of loop a, and generate a rectangular unit loop array at the bottom of the gap between a and b; if merging in the height direction, place loop b above loop a , and generate a rectangular cell loop array at the far left of the gap between a and b;

3) Use the rectangular element loop array, loop a, and loop b as the element matrix of the random Hamiltonian loop to be generated, and use the loop merging algorithm to obtain a random Hamiltonian loop c of the element matrix, that is, connect a and b in a small area , get the circuit c;

4) If the width direction is merged, a row of block unit circuits required for circuit expansion will be generated above the generated connection part; if the height direction is merged, a row of block unit circuits required for circuit expansion will be generated on the right of the generated connection part unit circuit;

5) Use the loop c together with the extended block unit loop as the unit matrix of the random Hamiltonian loop to be generated, and use the loop merging algorithm to find the random Hamiltonian loop of the unit matrix, and the newly generated loop will be used as the new loop c;

6) Repeat step 4 and step 5 until the combined gap between a and b is completely filled;

7) Solving ends.

The rectangular cell loop array is composed of 4x4 square arrays whose side length is 1, and the specific number can be adjusted according to the situation.

Features and beneficial effects of the present invention are:

By using this method, the generated smaller random Hamiltonian circuits can be used in a short time to combine and generate larger-area random Hamiltonian circuits, which reduces the time cost of generating a large-area protective layer.

Description of drawings:

Fig. 1 Schematic flow chart of loop merging algorithm.

Fig. 2 Schematic diagram of a smaller random Hamiltonian circuit generated based on the cycle merging algorithm.

(a) Circuit a to be merged (b) Circuit b to be merged

Figure 3 is a schematic diagram of generating a rectangular unit circuit.

Fig. 4 is a schematic diagram of the loop c obtained by using the loop merging algorithm to connect small areas.

Figure 5 is a schematic diagram of generating an expansion unit circuit.

Fig. 6 Schematic diagram of newly generated circuit c.

Figure 7. Schematic diagram of a random Hamiltonian circuit after complete merging.

detailed description

The invention is applicable to the generation of a metal protective layer on the top layer of a chip, and relates to a method for merging multiple random Hamiltonian circuits when generating a protective layer based on a highly complex random Hamiltonian circuit topological structure.

The present invention proposes a merging method for the generated random Hamiltonian loops. The method utilizes a loop merging algorithm to connect two random Hamiltonian loops in a small area at the boundary, and then expands and connects to the entire graph in sequence. The method can use the existing loops to generate larger area loops in a shorter time, while maintaining the complexity of random Hamiltonian loops.

The loop merging algorithm was proposed in the document "3D hardware canaries", which is not the focus of the present invention, and only a brief description is given here.

As shown in FIG. 1 , it is a schematic flow chart of the loop merging algorithm. In Figure 1(1), it is a 4x4 lattice, and the generated random Hamiltonian circuit will traverse all lattice points, and each lattice point will only pass once. The algorithm first takes four grid points as a minimum unit to generate a certain number of square matrices as unit circuits, as shown in Figure 1(2). Then randomly select two unit loops, as shown in Figure 1(3),(7). Due to random selection, there are various selection methods, and (3) and (7) only represent two of them. Determine whether two randomly selected unit loops have adjacent sides, and if there are adjacent sides, remove the adjacent sides and merge them into one unit loop, such as loop 1 and loop 2 in (3), the right side of loop 1 If the side is adjacent to the left side of loop 2, remove these two sides and connect the dotted line to form a large unit loop 1, as shown in loop 1 in (4); if there is no adjacent side, then Reselect two unit loops at random. Repeat the selection and merging steps until there is only one loop in the entire 4x4 lattice, as shown in Figure 1 (6), (10).

The execution efficiency of loop merging algorithm is inversely proportional to the number of unit loops. When the number of unit loops increases, the generation time will increase greatly.

The random Hamiltonian loop merging method proposed by the present invention needs to connect the existing two random Hamiltonian loops in a small area based on the cyclic merging algorithm, and then dynamically expand the unit loop at the connection until all the connection gaps are filled, and finally the Two random Hamiltonian circuits merged into one. The algorithm framework is shown below, and the schematic diagrams of the algorithm generation process are shown in Figure 2 to Figure 7.

Random Hamiltonian loop merging algorithm:

8) Determine the merging type. If the width direction (horizontal) merging is performed, then based on the cyclic merging algorithm, generate two random Hamiltonian circuits a and b with the same height H; or select a random Hamiltonian circuit with Two loops a and b of the same height H; loop a is shown in (a) in Figure 2, and loop b is shown in (b) in Figure 2. If merging in the height direction (vertical direction), two loops a and b with the same width W need to be generated or selected.

9) If merging in the width direction is performed, place loop b on the right side of loop a, and generate a rectangular unit loop array at the bottom of the gap between a and b, as shown in Figure 3 (for ease of description, only Take width direction merging as an example); if height direction merging is performed, loop b is placed above loop a, and a rectangular unit loop array is generated at the far left of the gap between a and b. The rectangular cell loop array is generally composed of 4x4 square arrays with a side length of 1, and the specific number can be adjusted according to the situation.

10) Use the rectangular unit loop array, loop a and loop b as the unit matrix of the random Hamiltonian loop to be generated, and use the cycle merging algorithm to obtain a random Hamiltonian loop c of the unit matrix, that is, connect a and b in a small area , the circuit c is obtained, as shown in Figure 4.

11) If the width direction is merged, a row of square unit circuits required for circuit expansion will be generated above the generated connection part, as shown in Figure 5; if the height direction is merged, a column will be generated on the right of the generated connection part The block unit circuit required for circuit expansion.

12) Use the circuit c together with the extended block unit circuit as the unit matrix of the random Hamiltonian circuit to be generated, and use the cycle merging algorithm to find the random Hamiltonian circuit of the unit matrix, and the newly generated circuit will be used as the new circuit c, as shown in the figure 6.

13) Repeat step 4 and step 5 until the merging gap between a and b is completely filled, as shown in FIG. 7 .

14) The solution ends.

The method for merging random Hamiltonian loops proposed by the invention adopts a cyclic merging algorithm to firstly connect two loops in a small area, thereby maintaining the complexity of the connection. Then, one row or one column of block unit loops is expanded at the connection, so that the number of unit loops to be merged each time is small, thus ensuring the efficiency of the loop merging algorithm.

Implemented according to the framework of the random Hamiltonian cycle merging algorithm. The scope of protection of the present invention is not limited to the above-mentioned embodiments, and equivalent modifications or changes made by those skilled in the art based on the content disclosed in the present invention should be included in the scope of protection.

Claims (2)

1. a method for merging random Hamiltonian loop topological structure in a chip top layer protection layer, is characterized in that, the steps are as follows: 1) Determine the type of merging. If the width direction is horizontal merging, then based on the cyclic merging algorithm, generate two random Hamiltonian circuits a and b with the same height H; or select a random Hamiltonian circuit with the same Two loops a and b of height H; if the height direction is to be merged vertically, two loops a and b with the same width W need to be generated or selected; 2) If merging in the width direction, place loop b on the right side of loop a, and generate a rectangular unit loop array at the bottom of the gap between a and b; if merging in the height direction, place loop b above loop a , and generate a rectangular cell loop array at the far left of the gap between a and b; 3) Use the rectangular element loop array, loop a, and loop b as the element matrix of the random Hamiltonian loop to be generated, and use the loop merging algorithm to obtain a random Hamiltonian loop c of the element matrix, that is, connect a and b in a small area , get the circuit c; 4) If the width direction is merged, a row of block unit circuits required for circuit expansion will be generated above the generated connection part; if the height direction is merged, a row of block unit circuits required for circuit expansion will be generated on the right of the generated connection part unit circuit; 5) Use the loop c together with the extended block unit loop as the unit matrix of the random Hamiltonian loop to be generated, and use the loop merging algorithm to find the random Hamiltonian loop of the unit matrix, and the newly generated loop will be used as the new loop c; 6) Repeat step 4 and step 5 until the combined gap between a and b is completely filled; 7) Solving ends. 2. the merging method of random Hamiltonian loop topological structure in the top protection layer of the chip as claimed in claim 1, is characterized in that, the rectangular cell loop array is formed with 4x4 square arrays whose side length is 1, and the specific number can be adjusted according to the situation .