CN109557449A - Based on the difficult integrated circuit detection method and system for surveying Path selection - Google Patents

Abstract

The present invention proposes that a kind of integrated circuit difficulty surveys the selection method in path.The present invention includes: to calculate the probability for being 0 or being 1 with calibration logic value using sound state Cooperative Analysis；According to calculated probability, transmission probability small path in hopping edge is found from output to input direction；For selected coordinates measurement test vector, route availability is judged.The present invention improves probability calculation precision by sound state Cooperative Analysis method, and then effectively searches out the difficult survey path in integrated circuit, to guarantee that integrated circuit testing coverage rate provides important support.

Description

Based on the difficult integrated circuit detection method and system for surveying Path selection

Technical field

The present invention relates to information security field and integrated circuit fields, belong to a kind of selecting party in integrated circuit difficulty survey pathMethod, and more particularly to a kind of based on the difficult integrated circuit detection method and system for surveying Path selection.

Background technique

Design and manufacture service outsourcing new trend, to the dependence of third party's intellectual property (IP) core and Electronic Design fromDynamic chemical industry tool, so that integrated circuit is easy the attack by hardware Trojan horse in the different phase of its life cycle more and more.The incredible component involved in the IC life cycle or when personnel, multiple stages therein, all there may be the designs of malice to repairChange, this proposes a series of new trust authentication challenges to malicious modification.Particularly, this is right during also bringing Post Manufacturing CheckoutThe malice design modification that incredible manufacturer generates carries out the demand of reliability detection.Simultaneously, it was also proposed that from insincereThird-party vendor in the IP kernel that obtains carry out the demand of trust authentication.

For the detection of hardware Trojan horse, there are two types of main methods: one is hardware Trojan horses before silicon to detect, mainly for integratedCode in circuit design process, including RTL level, netlist grade and domain grade etc., discovery are hidden in malicious code therein；It is anotherKind it is that hardware Trojan horse detects after silicon, mainly for the integrated circuit after manufacture, covers FPGA, three dimensional integrated circuits etc., find hiddenIt is hidden in malice circuit therein.

Hardware Trojan horse detection method includes destructiveness and two kinds of non-destructive after silicon, wherein detection method after non-destructive siliconIt is divided into two class of on-line checking and offline inspection again.Off-line checking method generally realize by comparing by chip to be measured and reference chip,If certain feature of chip to be measured, such as power consumption, output response, differ greatly with reference chip, then it is assumed that chip to be measured mayThere are hardware Trojan horses after silicon.Ideal reference chip feature, also known as golden model, it should be chip to be measured hardware wood after no siliconFeature when horse.When test after silicon there are mainly two types of hardware Trojan horse detection methods: activation detection method and side Channel Detection method.

Activation detection method lays particular emphasis on test vector generation and activation wooden horse circuit and observes it to load in original outputMalice influences.This method is similar with traditional stuck-at fault (stuck-at-fault) test in methodology, however, woodenBut there were significant differences with fault model for horse model.Manufacturing defect is usually modeled as stuck-at fault, and internal node is fixedIn specific logical value.The difficulty for testing these failures is that motivating all internal nodes is all possible logical value, andSome original output observations influence.The node for being difficult to motivate or be difficult to observe is known as low controllability node and low observability sectionPoint.With the increase of door quantity, it is difficult to which the number of nodes of test is consequently increased, so that testing all nodes to reach comprehensiveFailure covering becomes the task of exponential difficulty.On the other hand, wooden horse is modeled as the door (or one group of door) of an ingenious insertion,It is only just triggered under conditions of rare, shows some vicious functions.The quantity of the wooden horse circuit of specific type and size isThe exponential function of circuit node quantity, for needing the timing wooden horse of multiple rare events activation, possibly can not be dduring testObserve vicious function caused by wooden horse.Finally, because possible wooden horse quantity be it is huge, for estimate fault detection coverThe traditional technology of rate cannot be suitable for trojan horse detection well.Jha et al. propose it is a kind of based on the probabilistic method of randomization comeDetect wooden horse.Wolff et al. analyzes the rare gauze combination in design, and the gauze that these are seldom activated is triggered as wooden horseDevice, while using the low gauze of observability as payload generates the test vector of one group of activation these gauze, and shouldTest vector combines to activate wooden horse with traditional ATPG test vector.

On the other hand, Multiple Channel Analysis method in side is based on the fact that the insertion of any malice in IC should be reflected inIn certain side channel parameters, such as leakage current or quiescent power supply current in semiconductor integrated circuit (IDDQ), dynamic power track (IDDT), path delay spyElectromagnetic radiation (EM) or the combination of these parameters caused by property, switch activity.For example, if ifq circuit has N_origDoor,Consume I_origQuiescent current, the then N being inserted into circuit for realization wooden horse_origA additional goalkeeper increases electric current by I_orig, pass throughMeasurement power supply electricity can observe I under normal operation_orig.It has been generally acknowledged that the major defect of these methods be susceptible to technique andThe influence of ambient noise, or even since the noise that measure setup introduces can also interfere with analysis, cause wooden to whether there is in circuitThe error inference of horse.Therefore, trojan horse detection problem is regarded as a statistical phenomeon, and target is to maximize detection probability, simultaneouslyMinimize rate of false alarm.Since wooden horse circuit is to be inserted by modifying the domain of original design in foundries, it is generally recognized thatWooden horse circuit size compared with original design is smaller, it is believed that attacker is a small amount of additional using the white space insertion in domainDoor, and rewiring circuit realizes malicious intent.However, side channel method has main compared with logic test methodAdvantage is without activating wooden horse that can detect it.Therefore, they not will lead to vicious function for detecting those and can pass throughThe passive load wooden horse of side channel leakage secret information is highly effective.If process noise can be calibrated, environment and measurement noiseIt can eliminate, then the presence of wooden horse circuit is certain to be reflected in measurement parameter.

Hardware Trojan horse based on path delay is a kind of recent emerging hardware Trojan horse method for implantation.This method passes throughThe time delay of the logic gate in circuit on a fullpath is modified, so that in specific input jump, circuit output resultError, and then reach the specific purpose of attacker.

Existing hardware Trojan horse detection method is primarily directed to the hardware Trojan horse of logic-based, i.e. the activation item of hardware Trojan horsePart is that specific signal wire meets specific logical value.However, in the hardware Trojan horse based on path delay, trigger condition isSome jump can be by specific propagated, and each logic gate on this paths has certain subtle time delay to becomeChange, the Delay Variation of final this circuit accumulation is caused to be enough to constitute the malicious act of hardware Trojan horse.Due to the row of hardware Trojan horseIt is completely not identical for mechanism, therefore existing detection method is difficult to detect such hardware Trojan horse, i.e., " transmission probability is compared with small path "Hardware Trojan horse, the prior art not look into the lesser path of these transmission probabilities.For this reason, it may be necessary to a kind of road integrated circuit Nan CeThe selection method of diameter, by the test to difficult survey path, to find this kind of hardware Trojan horse based on path delay.

Summary of the invention

In order to solve the above-mentioned technical problem, present invention aims at detection of concealed in " transmission probability is compared with small path " i.e. difficult surveyHardware Trojan horse in circuit.

Specifically, the invention discloses a kind of based on the difficult integrated circuit detection method for surveying Path selection, including:

Step 1 obtains to-be-measured integrated circuit, according to the logic and the order of connection of logic gate in the to-be-measured integrated circuit, reallyThe output probability of each logic gate output particular logic value in the fixed to-be-measured integrated circuit；

Step 2, according to the output probability, obtain to-be-measured integrated circuit each propagation path logical value jump propagateProbability, and propagation path corresponding lower than the logical value of preset value jump probability of spreading is found as path to be selected；

Step 3 generates test vector, and judges whether the test vector can jump a logical value from the path to be selectedInput terminal transmitted to output end, if so, using the path to be selected as difficult survey path, for detecting hardware Trojan horse, otherwise, thenDelete the path to be selected.

This is based on the difficult integrated circuit detection method for surveying Path selection, and wherein the particular logic value is 0 or 1.

This surveys integrated circuit detection method of Path selection based on hardly possible, wherein the step 1 further include:

Step 11, the input terminal that random vector is input to the to-be-measured integrated circuit, and to the defeated of the to-be-measured integrated circuitOutlet carries out logic calculation, to obtain the logical value of each line in the to-be-measured integrated circuit；

Step 12, according to the following formula, calculates the dynamic that each line in the to-be-measured integrated circuit exports the particular logic valueProbability；

Wherein, P_dIt (i) is the dynamic probability of i-th line, n is the sum of the random vector, n₁(i) refer to n at random toUnder amount input, the logical value of line i is the vector number of the particular logic value；

Step 13 sets the particular logic value and is input to the static probability of the to-be-measured integrated circuit input terminal as 0.5, with to thisThe output end of to-be-measured integrated circuit carries out logic probability calculating, and obtaining each line in the to-be-measured integrated circuit, to export this specificThe static probability of logical value,

Step 14 calibrates the static probability according to the dynamic probability and calibration function, obtains the integrated electricity to be measuredEach line exports the calibration probability of the particular logic value in road, and using the calibration probability as the output probability.

This wherein finds the process in the path to be selected based on the difficult integrated circuit detection method for surveying Path selection in step 2It specifically includes: using the output logic gate of the to-be-measured integrated circuit as starting point, to input terminal direction finding, the logical value being selected to jumpThe smallest input link of probability of spreading is as jumping edge transmission end, and the logic gate to export the input link is as new starting pointContinue to input terminal direction finding, the input terminal until reaching the to-be-measured integrated circuit, a path to be selected, which is found, to terminate.

This is based on the difficult integrated circuit detection method for surveying Path selection, and wherein the calibration function includes: arithmetic in step 14Average function, geometric mean function, harmonic average function.

The invention also discloses a kind of based on the difficult integrated circuit detection system for surveying Path selection, including:

Output probability computing module is patrolled for obtaining to-be-measured integrated circuit according to logic gate in the to-be-measured integrated circuitVolume and the order of connection, determine the output probability of the output particular logic value of each logic gate in the to-be-measured integrated circuit；

Module is found in path, for obtaining patrolling for to-be-measured integrated circuit each propagation path according to the output probabilityValue jump probability of spreading is collected, and finds and jumps the corresponding propagation path of probability of spreading as to be selected lower than the logical value of preset valuePath；

Trojan horse detection module for generating test vector, and judges whether the test vector can jump a logical valueIt is transmitted from the input terminal in the path to be selected to output end, if so, path is surveyed using the path to be selected as hardly possible, for detecting hardwareOtherwise wooden horse then deletes the path to be selected.

This is based on the difficult integrated circuit detection system for surveying Path selection, and wherein the particular logic value is 0 or 1.

This surveys integrated circuit detection system of Path selection based on hardly possible, wherein the output probability computing module further include:

Random vector is input to the input terminal of the to-be-measured integrated circuit, and is carried out to the output end of the to-be-measured integrated circuitLogic calculation, to obtain the logical value of each line in the to-be-measured integrated circuit；

According to the following formula, the dynamic probability that each line in the to-be-measured integrated circuit exports the particular logic value is calculated；

Wherein, P_dIt (i) is the dynamic probability of i-th line, n is the sum of the random vector, n₁(i) refer to n at random toUnder amount input, the logical value of line i is the vector number of the particular logic value；

If the static probability that the particular logic value is input to the to-be-measured integrated circuit input terminal is 0.5, with to the collection to be measuredLogic probability calculating is carried out at the output end of circuit, each line in the to-be-measured integrated circuit is obtained and exports the particular logic valueStatic probability,

The static probability is calibrated according to the dynamic probability and calibration function, is obtained each in the to-be-measured integrated circuitLine exports the calibration probability of the particular logic value, and using the calibration probability as the output probability.

This is based on the difficult integrated circuit detection system for surveying Path selection, and wherein path is found in module and finds the path to be selectedProcess specifically include: using the output logic gate of the to-be-measured integrated circuit as starting point, to input terminal direction finding, select the logicThe value the smallest input link of jump probability of spreading is as jump edge transmission end, and the logic gate to export the input link is as newlyStarting point continue to input terminal direction finding, knot is found in the input terminal until reaching the to-be-measured integrated circuit a, path to be selectedBeam.

This based on difficult integrated circuit detection system for surveying Path selection, wherein the calibration function include: arithmetic mean function,Geometric mean function, harmonic average function.

As a result, the present invention by determine in circuit it is difficult survey path, can check whether to have in circuit and be present in " transmission probabilityCompared with small path " in hardware Trojan horse.

Detailed description of the invention

Fig. 1 is framework figure of the invention；

Fig. 2 is dynamic analysis process example schematic of the invention；

Fig. 3 is dynamic analysis result example schematic of the invention；

Fig. 4 is staticaanalysis results example schematic of the invention；

Fig. 5 is static and dynamic analysis result example schematic of the invention；

Fig. 6 is that validity test vector generates schematic diagram.

Specific embodiment

Inventor deeply divide when studying the hardware Trojan horse based on path delay, to the principle of the wooden horseAnalysis, it was found that this hardware Trojan horse is caused to be difficult to two detected key factors:

(1) increase path delay and cause input jump after circuit output malfunction hardware Trojan horse so that hardware Trojan horse canThe potential activation condition of energy is more vast, it is more difficult to be detected in actual operation or in random vector test.

(2) hardware Trojan horse based on path delay can increase certain small time delay for logic gate each on path, these are smallTime delay, which only accumulates just, will lead to final output error, if only having selected a part of logic gate, then the hour accumulatedProlong and not will cause circuit output mistake, this equally also increases the difficulty of detection.

Inventor proposes and the completely new circuit of the two factors is overcome to detect by the further investigation to above-mentioned two reasonMethod.Firstly, proposing the method that a kind of sound state collaboration calibration logic door output line be 1 (or being 0) probability, realization is higherProbability calculation precision.Secondly, covering more majority gate by searching out the lesser path of a plurality of jump edge transmission probability, improveDetect the probability for giving the hardware Trojan horse in path delay.It should be noted that finding the lesser path of transmission probability and coveringMore majority gate is two targets, that is to say, that by finding the lesser path of transmission probability and covering more logics as far as possibleDoor, to improve the probability of detection hardware Trojan horse.The present invention is directed this kind of hardware Trojan horse based on transmission probability compared with small path.Which paths actual hardware wooden horse is not aware that when actual test is, so finding the lesser path of transmission probabilityThe probability for detecting actual hardware wooden horse will be improved with covering more majority gate.

The invention discloses a kind of based on the difficult integrated circuit detection method for surveying Path selection, including:

Step 1 obtains to-be-measured integrated circuit, according to the logic and the order of connection of logic gate in the to-be-measured integrated circuit, reallyThe output probability of each logic gate output particular logic value in the fixed to-be-measured integrated circuit；

Step 2, according to the output probability, obtain to-be-measured integrated circuit each propagation path logical value jump propagateProbability, and propagation path corresponding lower than the logical value of preset value jump probability of spreading is found as path to be selected；

Step 3 generates test vector, and judges whether the test vector can jump a logical value from the path to be selectedInput terminal transmitted to output end, if so, using the path to be selected as difficult survey path, for detecting hardware Trojan horse, otherwise, thenDelete the path to be selected.

This is based on the difficult integrated circuit detection method for surveying Path selection, and wherein the particular logic value is 0 or 1.

This surveys integrated circuit detection method of Path selection based on hardly possible, wherein the step 1 further include:

Step 11, the input terminal that random vector is input to the to-be-measured integrated circuit, and to the defeated of the to-be-measured integrated circuitOutlet carries out logic calculation, to obtain the logical value of each line in the to-be-measured integrated circuit；

Step 12, according to the following formula, calculates the dynamic that each line in the to-be-measured integrated circuit exports the particular logic valueProbability；

Wherein, P_dIt (i) is the dynamic probability of i-th line, n is the sum of the random vector, n₁(i) refer to n at random toUnder amount input, the logical value of line i is the vector number of the particular logic value；

Step 13 sets the particular logic value and is input to the static probability of the to-be-measured integrated circuit input terminal as 0.5, with to thisThe output end of to-be-measured integrated circuit carries out logic probability calculating, and obtaining each line in the to-be-measured integrated circuit, to export this specificThe static probability of logical value,

Step 14 calibrates the static probability according to the dynamic probability and calibration function, obtains the integrated electricity to be measuredEach line exports the calibration probability of the particular logic value in road, and using the calibration probability as the output probability.

This wherein finds the process in the path to be selected based on the difficult integrated circuit detection method for surveying Path selection in step 2It specifically includes: using the output logic gate of the to-be-measured integrated circuit as starting point, to input terminal direction finding, the logical value being selected to jumpThe smallest input link of probability of spreading is as jumping edge transmission end, and the logic gate to export the input link is as new starting pointContinue to input terminal direction finding, the input terminal until reaching the to-be-measured integrated circuit, a path to be selected, which is found, to terminate.

To allow features described above and effect of the invention that can illustrate more clearly understandable, special embodiment below, and cooperateBright book attached drawing is described in detail below.

The present invention is directed to the hardware Trojan horse that may be present based on path delay as a result, proposes a kind of detection method, walksIt is rapid as follows:

A, for to-be-measured integrated circuit, the analysis method for using sound state to cooperate with calculate its all lines output logical value for1 or 0 probability, is introduced for 1 below, in which:

Dynamic analysing method described in A11, step A, refers to using random vector, simulates to circuit under test, to obtainThe dynamic probability P that all wired logic values are 1_d, an input vector, is exactly made of 0,1 bit in integrated circuits, such asIn Fig. 2, circuit has 8 inputs, and endways to see, first row 00011001 is exactly an input vector, secondary series 11000000It is an input vector, in which:

Each random vector described in A111, step A11 all refers to the input data comprising equiprobability 0,1 logical value, at random toThe number of amount is determined by tester, such as in Fig. 2, circuit has 8 inputs, so the number of bits of each input vector is8,5 input vectors (endways to have seen 5 column) is illustrated altogether in Fig. 2, the number of input vector is 5.Number is bigger, and gained is generalRate is more accurate, but the time is longer, on the contrary, number is smaller, the time is shorter, but gained probability precision has loss；

Simulation described in A112, step A11 refers to for random vector described in circuit under test input step A111, then from circuitInput terminal to output end carry out logic calculation, to the logic gate of each known input logic value calculate its export line logicValue, until all lines of circuit under test calculate logical value；

The probability that wired logic value described in A113, step A11 is 1 are as follows:

Wherein, P_d(i) passing through the dynamic probability that simulation obtains for i-th line, n is the sum of random vector described in A11,n₁(i) refer in the case where n random vector inputs, the vector number that the logical value of line i is 1.

Static Analysis Method described in A12, step A refers to and sets circuit under test input logic value as the static general of 1 (or being 0)Rate Ps is 0.5, carries out logic probability calculating from input terminal to output end, and a logic gate is somebody's turn to do according to its logic knownIn the case of the static probability of all inputs of logic gate, the static probability of logic gate output line is calculated, until circuit under testAll lines calculate static probability.Wherein, P_s(i) static probability of line is exported for i-th of logic gate.

Sound state Cooperative Analysis method described in A13, step A, refers to the result P using dynamic analysing method_dStatic point of calibrationThe result P of analysis method_s, the calibration probability P (i) that wired logic value is 1 after calibrating is finally obtained, step includes:

A131, the calibration probability of all inputs of circuit under test is set as 0.5；

A132, one logic gate is patrolled according to it from the input terminal of circuit to output end progress logic probability calculatingVolume, under its known input calibration probability scenarios, calculates it and export static probability；

If A133, P_d(i) it is equal to P_s(i), then P (i)=P_d(i)=P_s(i), otherwise P (i)=Func { P_d(i),P_s(i) },The Func function is a kind of calibration function, is defined according to the actual situation by tester, and 3 kinds of calibration functions are listed below, butIt is not limited to this 3 kinds of calibration functions:

A1331, arithmetic mean function, when | P_d(i)-P_s(i)|<Δ₁, thenOtherwise, P (i)=P_d(i)；

A1332, geometric mean function, when | P_d(i)-P_s(i)|<Δ₂, thenOtherwise, P(i)=P_s(i)；

A1333, harmonic average function, when | P_d(i)-P_s(i)|<Δ₃, thenOtherwise,.Wherein,Δ₁、Δ₂、Δ₃It can be determined by tester according to actual circuit.

If all lines of A134, circuit under test have all calculated calibration probability, calculating terminates, and otherwise returns to A12 and continuesIt calculates.

B, the logical value jump lesser path of probability of spreading is found from circuit under test according to calibration probability, " logical value is jumpedBecome the lesser path of probability of spreading " it is the probability very little for inputting jump a to path, the output in the path and also jumping.Such as one the inputs of paths be originally 0, this 0 is become 1 now, just produces a jump from 0 to 1, then thisThe output in path is originally 1, because this paths probability of spreading is smaller, after input jumps, output is likely to still1, there is no variations.Its step includes:

B1, be at least selected, the calibration the smallest output line L of probability is selected from circuit under test_j, L_jIt is logic gateG_jOutput line；

B2, with G_jFor starting point, to G_jInput direction select a logic gate, if logic gate G_jInput link be respectivelyL_j1, L_j2, L_j3…..L_jn, P (j1), P (j2), P (j3) ... ..P (jn) is L respectively_j1, L_j2, L_j3…..L_jnCalibration probability, rootAccording to the logic of logic gate, calculates all input links propagation logical values of the logic gate and jumps to the probability of logic gate output line,Point 3 kinds of situations are found forward, for logic gate G_jFor, if logic gate G_jThe z articles input link L_jz(1 < z≤n) propagation is patrolledThe probability for collecting value jump to logic gate output line is PP_z(j):

If B21, logic gate G_jThe z articles input link L_jz(1 < z≤n) was not chosen, and PP_z(j)=Min { PP₁(j),PP₂(j)…..PP_n(j) }, then we select the z articles input link to jump edge transmission line as logical value, and to export the lineLogic gate be new starting point, continue to input direction select logic gate, until searching out the input terminal of circuit under test, onePaths searching terminates；

If B22, logic gate G_jThere are several input links to be chosen, then from logic gate G_jAll companies not being chosenThe smallest line L of a PPp (j) is selected in line_jpPth input link is jumped edge transmission line by (1 < p≤n),And to export the logic gate of the line as new starting point, continue to select logic gate to input direction, until searching out circuit under testInput terminal until, a paths searching terminate；

If B23, logic gate G_jAll input links be chosen, then from logic gate G_jAll lines in select oneIt is selected the least input link of number to jump edge transmission line as logical value, and is new rise to export the logic gate of the linePoint continues to select logic gate to input direction, and until searching out the input terminal of circuit under test, paths searching terminates.

B3, paths searching terminate, and judge that the number of path found whether more than m, terminates if being more than, otherwise returnsStep B is continually looked for, and m is customized by tester.

It C, is the coordinates measurement validity test vector searched out, validity test vector meets, and can jump a logical valueIt is transmitted from the path input terminal searched out to output end, if validity test vector exists, retains, otherwise, then delete the path.Validity test vector wherein is generated for a paths, this road can be traveled to from the input of this paths for jump by referring to generatingThe vector of diameter output.Such as Fig. 6 is that path a- > d- > e generates validity test vector, is just desirable to work as there are three a, b, c is inputtedA from 0 become 1 when, e also can become 1 (or becoming 0 from 1, that is, jump) from 0.So in this circuit, effectivelyTest vector is exactly abc=010, after a becomes 1 from 0, because b is that 1, d from 0 becomes 1, because c is that 0, e also canBecome 1 from 0.

To allow features described above and effect of the invention that can illustrate more clearly understandable, special embodiment below, and cooperateBright book attached drawing is described in detail below.

Fig. 1 is framework figure of the invention, which includes following four main modular:

Module 1: dynamic analysis module, dynamic analysis module inputs equiprobable 0,1 logical value to circuit under test, by rightThe simulation of each logic gate output line of circuit, calculates separately out it and exports the probability that logical value is 1 (or being 0), is i.e. dynamic is generalRate.The computational accuracy of dynamic analysis depends on the quantity of input logic value, and input logic value is more, and it is more accurate to calculate, from trueIt is worth closer.

Further, for ease of understanding, it is illustrated by taking Fig. 2 as an example below.In Fig. 2,5 input vectors are illustrated.For logic gate G₁For, export line L₁Analog logic value in have 41,10, then logic gate G₁Dynamic probabilityFor logic gate G₁₀For, export line L₁₀Analog logic value in have 21,30, thenLogic gate G₁₀Dynamic probabilityThe dynamic probability of other logic gate output lines can similarly be obtained.IFurther simulate more input vectors, gained dynamic probability is as shown in Figure 3.

Module 2: static analysis module, static analysis refer to that setting circuit under test input logic value as the probability of 1 (or 0) is 0.5,Output line is calculated by the logic behaviour of Different Logic door from input terminal to output end.

Further, for ease of understanding, it is illustrated by taking Fig. 4 static analysis as an example below.If circuit under test input 0,1 is patrolledThe probability for collecting value is 0.5, is calculated from input terminal to output extreme direction.Wherein: logic sum gate G₁Two input terminal inputs are patrolledCollecting the probability that value is 1 is 0.5, only works as G₁Input at least one be 1 when, output logical value be just 1, therefore its output lineL₁Static probability P_s(1)=1-0.5 × 0.5=0.75.Logical AND gate G₉The probability that input logic value is 1 is respectively 0.25 He0.75, only work as G₉Input when being all 1, output logical value is just 1, therefore its output line L₉Static probability P_s(9)=0.25× 0.75=0.1875.Logic XOR gate G₁₀The probability that input logic value is 1 is respectively 0.203125 and 0.1875, only works as G₁₀Input one for 0 one be 1 when, output logical value be just 1, therefore its output line L₁₀Static probability P_s(10)=1-(0.203125 × 0.1875)-(1-0.203125) × (1-0.1875)=0.314453.Other logic gate outputs can similarly be obtainedThe static probability of line.

Module 3: static and dynamic analysis module, static and dynamic analysis combine dynamic analysis and static analysis, by calibrating letterNumber, obtains the calibration probability of circuit under test.It during calibration, to calibrate when calculating, output line only passes through calibrationIt just can be used as the input of next logic gate afterwards.

Further, for ease of understanding, it is illustrated by taking Fig. 5 static and dynamic analysis as an example below.For being patrolled in circuit under testCollect door G₁~G₈Output line L₁~L₈, dynamic probability and static probability are equal, therefore calibrate probability P (i)=P_d(i)=P_s(i) (1≤i≤8, for logic gate G₉Output line L₉, dynamic probability P_d(9)=0, static probability P_s(9)=0.1875,It is calibrated with arithmetic mean function, that is, is worked as | P_d(9)-P_s(9)|<Δ₁(Δ₁=0.2) when, probability is calibratedAt this point, the output line L after calibration₉As logic gateG₁₀Input carry out next step calculating.

Module 4: path testing module, path testing module include two steps of searching and test in path.Wherein: finding in pathRefer to and searches out more lesser paths of hopping edge transmission probability from the circuit under test after calibration；Path testing refers to searching outCoordinates measurement validity test vector.

Further, for ease of understanding, it is illustrated by taking Fig. 5 static and dynamic analysis as an example below.With calibrate after circuit it is defeatedIt is used as starting point, i.e. logic gate G out₁₁For starting point, found to input extreme direction, logic gate G₁₁Input link be respectively L₇WithL₁₀, to export line L₇For logic gate G₁₁First input link, export line L₁₀For logic gate G₁₁Article 2 input connectLine can obtain PP₂(11)=Min { PP₁(11), PP₂(11) }=0.258790, therefore to export L₁₀Logic gate G₁₀For starting point continuationIt is found to input terminal, logic gate G₁₀Input link be respectively L₈And L₉, to export line L₈For logic gate G₁₀First it is defeatedEnter line, exports line L₉For logic gate G₁₀Article 2 input link, PP can be obtained₂(10)=Min { PP₁(10), PP₂(10)}=0.09375, therefore to export L₉Logic gate G₉Continue to find to input terminal for starting point, logic gate G₉Input link be respectivelyL₃And L₆, to export line L₃For logic gate G₉First input link, export line L₆For logic gate G₉Article 2 inputLine can obtain PP₁(9)=Min { PP₁(9), PP₂(9) }=0.25, therefore to export L₃Logic gate G₃Continue for starting point to inputEnd is found, logic gate G₃Input link be circuit input terminal, a paths searching terminate.

Again to export as starting point, i.e. logic gate G₁₁For starting point, found to input extreme direction, logic gate G₁₁It is defeatedEntering line is respectively L₇And L₁₀, to export line L₇For logic gate G₁₁First input link, export line L₁₀For logic gateG₁₁Article 2 input link, PP can be obtained₂(11)=Min { PP₁(11), PP₂(11) }=0.258790, therefore to export L₁₀PatrolCollect door G₁₀Continue to find to input terminal for starting point, logic gate G₁₀Input link be respectively L₈And L₉, but in a upper pathsL₉Be selected, so when selection output L₈Logic gate G₈Continue to find to input terminal for starting point, logic gate G₈Input linkRespectively L₃And L₅, to export line L₃For logic gate G₈First input link, export line L₅For logic gate G₈SecondInput link, can obtain PP₁(8)=Min { PP₁(8), PP₂(8) }=0.25 therefore to export L₃Logic gate G₃For starting point continue toInput terminal is found, logic gate G₃Input link be circuit input terminal, a paths searching terminate.Similarly, the jump of m item can be found outTransmit lesser transmission path in edge.

After transmission path is found, Yao Shengcheng test vector simultaneously rejects Invalid path, with two paths of above-mentioned searchingFor: in the first paths, when test vector is transferred to logic gate G₉When, jumping edge can not continue to transmit, and the first paths areIf G3- > G9- > G10- > G11 is in Fig. 5 it can be seen that an input in G3 occurs for a jump, as long as G3's is anotherAn outer input is 1, then the output of G3 will jump, so jump can propagate to G3's from the input of this pathsOutput.But if the input that the output of G3 becomes 1, G9 from 0 is to become 1 from 0, and another is inputted, i.e. G6Output then become 0 from 1, therefore the output of G9 still maintains 0, and there is no become 1 from 0, that is to say, that the jump in G3 outputThe output of G9 can not be traveled to., logic gate G₉Output be always 0, be a nothing so paths can not generate test vectorImitate path.In second paths, the jump edge of test vector can be efficiently transmitted to output end, so paths are successfully generated testVector can be used for detecting hardware Trojan horse, for example, select it is difficult survey path after, it is only necessary to corresponding test vector is inputed to circuit,Observe whether circuit output is correct, the process of this input vector observation output is identical with general test process.

What is surveyed due to the present invention is this kind of hardware Trojan horse based on transmission probability compared with small path, and this path is because of transmissionProbability is smaller, and existing test method does not account for this kind of hardware Trojan horse again, so the test vector used seldom jumps oneOutput is traveled to from the input in this path.Which road actual hardware wooden horse is not aware that when actual test isDiameter, so the present invention searches out many this lesser paths of transmission probability, it is then each coordinates measurement vector, so that jumpingChange can travel to output from the input in these paths, and the path searched out is more, successfully be detected actual hardware wooden horseProbability is bigger.

The following are system embodiment corresponding with above method embodiment, present embodiment can be mutual with above embodimentCooperation is implemented.The relevant technical details mentioned in above embodiment are still effective in the present embodiment, in order to reduce repetition,Which is not described herein again.Correspondingly, the relevant technical details mentioned in present embodiment are also applicable in above embodiment.

The invention also discloses a kind of based on the difficult integrated circuit detection system for surveying Path selection, including:

Output probability computing module is patrolled for obtaining to-be-measured integrated circuit according to logic gate in the to-be-measured integrated circuitVolume and the order of connection, determine the output probability of the output particular logic value of each logic gate in the to-be-measured integrated circuit；

Module is found in path, for obtaining patrolling for to-be-measured integrated circuit each propagation path according to the output probabilityValue jump probability of spreading is collected, and finds and jumps the corresponding propagation path of probability of spreading as to be selected lower than the logical value of preset valuePath；

Trojan horse detection module for generating test vector, and judges whether the test vector can jump a logical valueIt is transmitted from the input terminal in the path to be selected to output end, if so, path is surveyed using the path to be selected as hardly possible, for detecting hardwareOtherwise wooden horse then deletes the path to be selected.

This is based on the difficult integrated circuit detection system for surveying Path selection, and wherein the particular logic value is 0 or 1.

This surveys integrated circuit detection system of Path selection based on hardly possible, wherein the output probability computing module further include:

Random vector is input to the input terminal of the to-be-measured integrated circuit, and is carried out to the output end of the to-be-measured integrated circuitLogic calculation, to obtain the logical value of each line in the to-be-measured integrated circuit；

According to the following formula, the dynamic probability that each line in the to-be-measured integrated circuit exports the particular logic value is calculated；

Wherein, P_dIt (i) is the dynamic probability of i-th line, n is the sum of the random vector, n₁(i) refer to n at random toUnder amount input, the logical value of line i is the vector number of the particular logic value；

If the static probability that the particular logic value is input to the to-be-measured integrated circuit input terminal is 0.5, with to the collection to be measuredLogic probability calculating is carried out at the output end of circuit, each line in the to-be-measured integrated circuit is obtained and exports the particular logic valueStatic probability,

The static probability is calibrated according to the dynamic probability and calibration function, is obtained each in the to-be-measured integrated circuitLine exports the calibration probability of the particular logic value, and using the calibration probability as the output probability.

This is based on the difficult integrated circuit detection system for surveying Path selection, and wherein path is found in module and finds the path to be selectedProcess specifically include: using the output logic gate of the to-be-measured integrated circuit as starting point, to input terminal direction finding, select the logicThe value the smallest input link of jump probability of spreading is as jump edge transmission end, and the logic gate to export the input link is as newlyStarting point continue to input terminal direction finding, knot is found in the input terminal until reaching the to-be-measured integrated circuit a, path to be selectedBeam.

This based on difficult integrated circuit detection system for surveying Path selection, wherein the calibration function include: arithmetic mean function,Geometric mean function, harmonic average function.

Claims (10)

Translated fromChinese

1.一种基于难测路径选择的集成电路检测方法，其特征在于，包括：1. an integrated circuit detection method based on difficult to measure path selection, is characterized in that, comprises:步骤1、获取待测集成电路，根据该待测集成电路中逻辑门的逻辑及连接顺序，确定该待测集成电路中每一个逻辑门输出特定逻辑值的输出概率；Step 1. Obtain the integrated circuit to be tested, and determine the output probability of each logic gate in the integrated circuit to be tested outputting a specific logic value according to the logic and connection sequence of the logic gates in the integrated circuit to be tested;步骤2、根据该输出概率，得到该待测集成电路每一条传播路径的逻辑值跳变传播概率，并寻找低于预设值的该逻辑值跳变传播概率对应的传播路径作为待选路径；Step 2, according to the output probability, obtain the logic value hopping propagation probability of each propagation path of the integrated circuit under test, and find the propagation path corresponding to the logic value hopping propagation probability lower than the preset value as the candidate path;步骤3、生成测试向量，并判断该测试向量是否能将一个逻辑值跳变从该待选路径的输入端向输出端传输，若是，则将该待选路径作为难测路径，用于检测硬件木马，否则，则删除该待选路径。Step 3. Generate a test vector, and judge whether the test vector can transmit a logic value jump from the input end of the path to be selected to the output end. If so, then use the path to be selected as a difficult-to-test path for detecting hardware Trojan, otherwise, delete the candidate path.2.如权利要求1所述的基于难测路径选择的集成电路检测方法，其特征在于，该特定逻辑值为0或1。2 . The method for detecting an integrated circuit based on difficult path selection as claimed in claim 1 , wherein the specific logic value is 0 or 1. 3 .3.如权利要求2所述的基于难测路径选择的集成电路检测方法，其特征在于，该步骤1还包括：3. The integrated circuit detection method based on difficult-to-measure path selection according to claim 2, wherein step 1 further comprises:步骤11、将随机向量输入至该待测集成电路的输入端，并向该待测集成电路的输出端进行逻辑计算，以得到该待测集成电路中每一条连线的逻辑值；Step 11: Input the random vector to the input end of the integrated circuit under test, and perform logical calculation on the output end of the integrated circuit under test to obtain the logic value of each connection in the integrated circuit under test;步骤12、根据下式，计算该待测集成电路中每一条连线输出该特定逻辑值的动态概率；Step 12, according to the following formula, calculate the dynamic probability that each connection in the integrated circuit under test outputs the specific logic value;其中，P_d(i)为第i条连线的动态概率，n为该随机向量的总数，n₁(i)指在n个随机向量输入下，连线i的逻辑值为该特定逻辑值的向量个数；Among them, P_d (i) is the dynamic probability of the i-th connection, n is the total number of the random vectors, and n₁ (i) means that under the input of n random vectors, the logic value of the connection i is the specific logic value the number of vectors;步骤13、设该特定逻辑值输入至该待测集成电路输入端的静态概率为0.5，以向该待测集成电路的输出端进行逻辑概率计算，得到该待测集成电路中每一条连线输出该特定逻辑值的静态概率；Step 13: Set the static probability that the specific logic value is input to the input terminal of the integrated circuit under test to be 0.5, so as to perform logic probability calculation on the output terminal of the integrated circuit under test, and obtain the output of each connection in the integrated circuit under test. static probability of a specific logical value;步骤14、根据该动态概率和校准函数对该静态概率进行校准，得到该待测集成电路中每一条连线输出该特定逻辑值的校准概率，并将该校准概率作为该输出概率。Step 14: Calibrate the static probability according to the dynamic probability and the calibration function to obtain the calibration probability that each connection in the integrated circuit under test outputs the specific logic value, and use the calibration probability as the output probability.4.如权利要求1或3所述的基于难测路径选择的集成电路检测方法，其特征在于，步骤2中寻找该待选路径的过程具体包括：以该待测集成电路的输出逻辑门为起点，向输入端方向寻找，选择该逻辑值跳变传播概率最小的输入连线作为跳边沿传输端，并以输出该输入连线的逻辑门作为新的起点继续向输入端方向寻找，直到到达该待测集成电路的输入端，一条待选路径寻找结束。4. The integrated circuit detection method based on unmeasured path selection according to claim 1 or 3, wherein the process of finding the path to be selected in step 2 specifically comprises: taking the output logic gate of the integrated circuit to be tested as Starting point, look for the direction of the input terminal, select the input connection with the smallest jump propagation probability of the logic value as the jump edge transmission terminal, and use the logic gate outputting the input connection as a new starting point to continue to search in the direction of the input terminal until it reaches At the input end of the integrated circuit to be tested, the search for a candidate path ends.5.如权利要求3所述的基于难测路径选择的集成电路检测方法，其特征在于，步骤14中该校准函数包括：算术平均函数、几何平均函数、调和平均函数。5 . The integrated circuit detection method based on difficult path selection according to claim 3 , wherein the calibration function in step 14 comprises: an arithmetic mean function, a geometric mean function, and a harmonic mean function. 6 .6.一种基于难测路径选择的集成电路检测系统，其特征在于，包括：6. An integrated circuit detection system based on difficult-to-measure path selection, characterized in that it comprises:输出概率计算模块，用于获取待测集成电路，根据该待测集成电路中逻辑门的逻辑及连接顺序，确定该待测集成电路中每一个逻辑门输出特定逻辑值的输出概率；The output probability calculation module is used to obtain the integrated circuit to be tested, and to determine the output probability of each logic gate in the integrated circuit to be tested outputting a specific logic value according to the logic and connection sequence of the logic gates in the integrated circuit to be tested;路径寻找模块，用于根据该输出概率，得到该待测集成电路每一条传播路径的逻辑值跳变传播概率，并寻找低于预设值的该逻辑值跳变传播概率对应的传播路径作为待选路径；The path finding module is used to obtain the logic value hopping propagation probability of each propagation path of the integrated circuit under test according to the output probability, and find the propagation path corresponding to the logic value hopping propagation probability lower than the preset value as the waiting propagation path select path;木马检测模块，用于生成测试向量，并判断该测试向量是否能将一个逻辑值跳变从该待选路径的输入端向输出端传输，若是，则将该待选路径作为难测路径，用于检测硬件木马，否则，则删除该待选路径。The Trojan horse detection module is used to generate a test vector and determine whether the test vector can transmit a logic value jump from the input end to the output end of the path to be selected. To detect hardware Trojans, otherwise, delete the candidate path.7.如权利要求6所述的基于难测路径选择的集成电路检测系统，其特征在于，该特定逻辑值为0或1。7 . The integrated circuit inspection system based on unpredictable path selection as claimed in claim 6 , wherein the specific logic value is 0 or 1. 8 .8.如权利要求7所述的基于难测路径选择的集成电路检测系统，其特征在于，该输出概率计算模块还包括：8. The integrated circuit detection system based on hard-to-measure path selection according to claim 7, wherein the output probability calculation module further comprises:将随机向量输入至该待测集成电路的输入端，并向该待测集成电路的输出端进行逻辑计算，以得到该待测集成电路中每一条连线的逻辑值；Input the random vector to the input end of the integrated circuit under test, and perform logic calculation on the output end of the integrated circuit under test to obtain the logic value of each connection in the integrated circuit under test;根据下式，计算该待测集成电路中每一条连线输出该特定逻辑值的动态概率；According to the following formula, calculate the dynamic probability that each connection in the integrated circuit under test outputs the specific logic value;其中，P_d(i)为第i条连线的动态概率，n为该随机向量的总数，n₁(i)指在n个随机向量输入下，连线i的逻辑值为该特定逻辑值的向量个数；Among them, P_d (i) is the dynamic probability of the i-th connection, n is the total number of the random vectors, and n₁ (i) means that under the input of n random vectors, the logic value of the connection i is the specific logic value the number of vectors;设该特定逻辑值输入至该待测集成电路输入端的静态概率为0.5，以向该待测集成电路的输出端进行逻辑概率计算，得到该待测集成电路中每一条连线输出该特定逻辑值的静态概率；Set the static probability that the specific logic value is input to the input terminal of the integrated circuit under test to be 0.5, so as to perform logic probability calculation on the output terminal of the integrated circuit under test, and obtain the output of the specific logic value for each connection in the integrated circuit under test. The static probability of ;根据该动态概率和校准函数对该静态概率进行校准，得到该待测集成电路中每一条连线输出该特定逻辑值的校准概率，并将该校准概率作为该输出概率。The static probability is calibrated according to the dynamic probability and the calibration function to obtain the calibration probability that each connection line in the integrated circuit under test outputs the specific logic value, and the calibration probability is used as the output probability.9.如权利要求6或8所述的基于难测路径选择的集成电路检测系统，其特征在于，路径寻找模块中寻找该待选路径的过程具体包括：以该待测集成电路的输出逻辑门为起点，向输入端方向寻找，选择该逻辑值跳变传播概率最小的输入连线作为跳边沿传输端，并以输出该输入连线的逻辑门作为新的起点继续向输入端方向寻找，直到到达该待测集成电路的输入端，一条待选路径寻找结束。9. The integrated circuit detection system based on difficult-to-test path selection according to claim 6 or 8, wherein the process of finding the path to be selected in the path finding module specifically comprises: using the output logic gate of the integrated circuit to be tested As the starting point, look for the direction of the input terminal, select the input connection with the smallest jump propagation probability of the logic value as the jump edge transmission terminal, and use the logic gate outputting the input connection as a new starting point to continue to search in the direction of the input terminal until When the input end of the integrated circuit under test is reached, the search for a path to be selected ends.10.如权利要求8所述的基于难测路径选择的集成电路检测系统，其特征在于，该校准函数包括：算术平均函数、几何平均函数、调和平均函数。10 . The integrated circuit inspection system based on difficult path selection according to claim 8 , wherein the calibration function comprises: an arithmetic mean function, a geometric mean function, and a harmonic mean function. 11 .