The present invention relates to a computer- implemented method for automatically validating a hardware system by a model thereof, the model being a netlist at register transfer level .

Nowadays, electrical and electronic circuits (herein: also "hardware systems") are increasingly designed and/or manufac tured by third party suppliers according to respective func tional specifications. While decreasing time to market, such distribution of efforts and responsibilities creates threats to the function of the hardware system. Hence, a demand for exami nation of the designed and/or manufactured hardware systems arises to reliably discover potential threats and to validate a hardware system when the hardware system performs according to the functional specification. This validation is also referred to as "verification" in the environment of hardware system de velopment and testing. Said threats are, generally, non- specified functions which were inadvertently or deliberately added to the hardware system and impair the originally speci fied function thereof. One class of such threats are so-called "hardware Trojans" which perform malicious functions that are triggered by specific, usually rare, events and are, conse quently, difficult to detect.

Hardware systems are commonly specified and described in hardware description language (HDL) , such as VHDL or Verilog. While an automatic validation of thusly described hardware sys tems is per se possible, it is computationally expensive in particular due to the increasing size and complexity of today' s hardware systems .

One established method to reduce the computational ex penses of the examination and validation is to define one or more patterns (also: "structures") of functions of interest, e.g., malicious functions, and to search for the defined pat terns in the hardware system and to focus the validation thereon. However, due to the diverse variants in describing one and the same (malicious) function, the definition of the search patterns is difficult and potentially incomplete, thus render ing the validation questionable.

For overcoming this problem, it has been proposed to ana lyse a hardware system by a generalised model thereof, e.g., a netlist model. However, netlist representations still carry de tails leading to an unnecessary diversity. This diversity has to be matched when defining search patterns to be detected, re sulting in a plurality of search patterns to be defined even for detecting a single function and, consequently, in an exten sive search, both of which impeding an automatic examination and validation. Moreover, when a specific variation of the di versity is not included in the search pattern definition, this variation and consequently the occurrence of a (malicious) function will not be detected.

F. Demrozi et al . , "Exploiting Sub-Graph Isomorphism and Probabilistic Neural Networks for the Detection of Hardware Trojans at RTL" , 2017 IEEE International High Level Design Validation and Test Workshop (HLDVT) , Santa Cruz, CA (2017), pp . 67-73, propose to identify and classify hardware Trojans by means of an algorithm for finding, in a netlist model of the hardware system at register transfer level (RTL) , potentially malicious sub-graphs by isomorphism to known hardware Trojans and then using a probabilistic neural network (PNN) for classi fying the potentially malicious sub-graphs to eliminate non- malicious ones.

By using a PNN, this approach is non-deterministic and, therefore, not applicable to security-relevant validations. Furthermore, the necessary learning phase of the PNN is based on specific, known hardware Trojans, restricting the applica tion of this method to these learned cases and/or requiring further extensive learning for each further structure to be de tected . It is an object of the invention to provide a determinis tic, accurate and efficient method for automatically validating a hardware system by a computer that can be flexibly applied.

This object is achieved by a computer- implemented method for automatically validating a hardware system by a model thereof, wherein the model is a netlist at register transfer level, which netlist is bipartite having cells and links there between, the method comprising the following steps carried out by a computer:

providing one or more reference structures, which are prone to error or manipulation, and determining, in the model, sub- structures , each of which comprises a subset of the cells and links of the model and is structurally equivalent to one of said reference structures;

extracting, from the model, input cones for each of the determined sub- structures , each input cone comprising control inputs to one of the cells of the sub- structure up to a nearest register output in the model or to a nearest primary input to the model;

creating a set of monopartite candidate graphs by mapping the cells and links of each sub- structure and of the respective input cones extracted for the sub- structure to nodes and edges of one of the monopartite candidate graphs of the set, wherein each node has a node type;

creating, for each candidate graph, an n-dimensional match vector, each dimension of the match vector comprising a count of occurrences, in the candidate graph, of a different one of a number of n predetermined graphlets, wherein each graphlet has nodes and edges and each node has a node type;

clustering, on the basis of similarity of the created match vectors, the candidate graphs in clusters; and

selecting, from each of at least some of said clusters, one candidate graph and determining a functional behaviour of the sub- structure the selected candidate graph was mapped from for validating the hardware system. By creating candidate graphs from reference structures and clustering the candidate graphs on the basis of similarity of the match vectors the present method is very efficient, since the determination of the functional behaviour can be focussed on one candidate graph per clusters rather than determining the functional behaviour of the respective sub- structures of all candidate graphs. This is due to the fact that candidate graphs in the same cluster are of comparable functional behaviour. Some clusters may even be omitted when the functional behaviour of the candidate graphs therein can reliably be derived, e.g., from the cluster's environment and/or separateness from other clusters .

The present method is also very accurate due to the two- stage processing of (i) creating candidate graphs of poten tially undesirable functional behaviour by means of reference structures which can be defined rather broadly and (ii) effi ciently eliminating, by clustering, e.g., duplicates due to overlapping candidate graphs and/or candidate graphs of desired functional behaviour and thereupon, when no undesirable func tional behaviour is determined, validating the hardware struc ture. Furthermore, the present method is deterministic and therefore applicable in security-relevant cases and can also be flexibly customized to different validation scenarios, e.g., for detecting hardware Trojans, other malicious or simply spe cific functional behaviours, and adapted or expanded to evolv ing threats by adding and/or changing either reference struc tures or graphlets or both.

The graphlets are usually smaller than the candidate graphs, i.e., they comprise fewer nodes and edges, usually they are much smaller. Preferably, each graphlet has two or three nodes. It has been found that graphlets of this size are both characteristic and versatile so that meaningful match vectors are created. Particularly preferably, the nodes and edges of a graphlet which has three nodes form a 2-to-l coalescence or a l-to-2 bifurcation. Such coalescing or bifurcating graphlets are particularly characteristic and therefore particularly beneficial for creating meaningful match vectors and distinct clusters whereby the method becomes notably unerring.

In an advantageous embodiment of the method, the graphlets are predetermined by matching each of a set of graphlets with all candidate graphs, and wherein only such graphlets of said set are predetermined for which a match is found in at least one candidate graph. This embodiment facilitates both stan dardisation and efficiency as the set of graphlets may be large and universal, e.g., an extensive standard set, while only graphlets relevant for the specific validation are considered in the further steps of the method. Thereby, the dimension of the match vectors is reduced to a minimum by relevance.

For further reducing complexity and computational efforts, it is favourable that, in said step of clustering, a principal component analysis is applied to the created match vectors for determining their similarity. Thereby, the dimensionality of the match vectors, which, depending on the number of predeter mined graphlets, can be in the range of up to, e.g., a few hun dred dimensions, is reduced, in some cases to as little as, e.g., two dimensions. Consequently, the step of clustering is substantially simplified.

While a manifold of algorithms for clustering are known in the art and applicable here, it has been found to be particu larly efficient and accurate when said step of clustering the candidate graphs is performed using a density-based clustering algorithm .

It shall be understood that the initial step of determin ing the sub- structures in the model can be performed in a num ber of ways, some of which were referred to herein in the out set. The step can, in one embodiment, be performed by searching for, e.g., isomorphic sub- structures directly in the netlist at register transfer level; in other embodiments, the structural equivalence can be determined on a more abstract level of the model. In a preferred embodiment, however, said step of deter mining sub- structures in the model comprises:

mapping the cells and links of the model to nodes and edges of a monopartite model graph, wherein each node has a node type, and mapping the cells and links of each of the pro vided reference structures to nodes and edges of a monopartite reference graph, wherein each node has a node type;

finding, in the model graph, sub-graphs, each of which matches one of said reference graphs; and

determining, for each of said found sub-graphs, the re spective sub- structure in the model by re-mapping the sub-graph back to the model .

By mapping the model to a monopartite model graph, dispen sable or non-effective details, e.g., of the links, are elimi nated, whereby the matching of the model graph with the refer ence graphs is simplified and becomes even more efficient be cause differences which have no effect on the functional behav iour are no longer to be considered.

The invention shall now be explained in more detail below on the basis of exemplary embodiments thereof with reference to the accompanying drawings, in which:

Fig. 1 shows a computer- implemented method for automati cally validating a hardware system according to the present in vention in a flow chart;

Figs. 2a to 2d show details of a model of the hardware system validated according to Fig. 1 in a circuit diagram (Fig. 2a), as a bipartite netlist at register transfer level (Fig. 2b) , and as a monopartite graph in a linear (Fig. 2c) and a planar (Fig. 2d) diagram, respectively;

Figs. 3a and 3b show exemplary graphlets to be found in the monopartite graph of Figs. 2c and 2d, in particular a coa- lescent 2-to-l graphlet (Fig. 3a) and a bifurcating l-to-2 graphlet (Fig. 3b);

Fig. 4 shows an exemplary match vector for the method of Fig. 1; Fig. 5 shows a result of a clustering according to the method of Fig. 1 in a plane diagram; and

Fig. 6 shows a variation of a part of the method of Fig. 1 in a flow chart.

The flow chart of Fig. 1 depicts a computer- implemented method 1 for automatically validating (also referred to as "verifying" in the environment of hardware system development and testing) an electrical or electronic circuit (herein: a "hardware system") HS by a computer. A model MO describes the hardware system HS in form of a netlist at register transfer level ( "RTL" ) . The netlist is bipartite, i.e., it has cells Ci, C ₂ , ..., generally Ci, and links Li, L ₂ , ..., generally L _k , (also known as "nets" or "wires") between the cells Ci, see Fig. 2a. No cells Ci are immediately connected to other cells Ci without intermediate links L _k and no links L _k are immediately connected to other links L _k , see Fig. 2b.

Fig. 2b illustrates the bipartite character on the basis of an exemplary sub- structure SS (Fig. 2a) of the model MO. Therein, the cells Ci _, C ₂ , C ₃ , C ₄ of the sub- structure SS are concentrated in a first set Si on the left, where also further cells Ci of the bipartite model MO would be concentrated (as symbolised by dots in Fig. 2b), whereas the links 1^, L ₂ , L ₃ , L ₄ of the sub- structure SS are concentrated in a second set S ₂ on the right of Fig. 2b, where also further links L _k of the model MO would be concentrated (as symbolised by dots in Fig. 2b) . The interrelation between cells C ₄ and links L _k is symbolised by intermediate connections CO. The connections CO can be un derstood, e.g., as input-contacts I or output-contacts 0 (Fig. 2a) which connect cells Ci and links L _k of the sub- structure SS . For example, cell Ci is connected via its respective out- put-contact 0 to link Li and cell C ₄ is connected via its re spective input-contact I to link Li; no other cells Ci are con nected to link Li as shown by the connections CO in Fig. 2b.

Referring to Fig. 1, in a first step 2 of the computer- implemented method 1 for automatically validating the hardware system HS one or (typically) more reference structures RS are provided in the computer. The provided reference structures RS are relevant for the validation, e.g., because they are prone to error or to possible manipulation by a designer and/or manu facturer of the hardware system HS . Based on the provided ref erence structures RS, sub- structures SS, each of which is structurally equivalent to one of the reference structures RS, are determined in the model MO. Each of the determined sub structures SS comprises a subset of the cells Ci and links L _k of the model MO. As will be explicated in greater detail below, the structural equivalence may be determined on the level of the netlist model MO or on a further abstracted level of de scription of the hardware system HS . Hence, the term "struc tural equivalence", includes, e.g., isomorphism, on the one hand, but also more general structural comparability, on the other hand.

It shall be noted that, between consecutive steps in the flow chart of Fig. 1, some, usually newly created, information passed from one step to the next one is explicitly noted in the drawing for easier reference. However, further information, e.g., on the hardware system HS and its model MO, is understood to be available throughout all steps of the method 1 without explicit reference in the drawing.

In a second step 3 , input cones IN are extracted for each of the determined sub- structures SS from the model MO. Each in put cone IN comprises control inputs, i.e., all control inputs in the model MO to one of the cells Ci of the sub- structure SS . Each input cone IN reaches upstream, where necessary more than one upstream- level of a control path of the model MO, to a nearest register output in the model MO or to a nearest primary input, i.e., an input from outside to the model MO. In this way, an input cone IN is extracted for each cell Ci in the sub structure SS .

In a subsequent step 4, a set of monopartite candidate graphs CG is created from the bipartite sub- structures SS . This is performed by mapping the cells Ci and links L _k of each sub structure SS and of the respective input cones IN extracted for the sub- structure SS to nodes Ni, N ₂ , generally N _m , and edges Ei, E ₂ , generally E _p , of one of the candidate graphs CG of the set .

Figs. 2a to 2d illustrate an example of such a mapping. This example is simplified in that it does not include the in put cones IN to the cells Ci of the sub- structure SS, and in that the shown sub- structure SS, for better visibility, has merely four cells Ci _, C ₂ , C ₃ , C ₄ and four links Li, L ₂ , L ₃ , L ₄ . Apart from the cells Ci and links L _k of the sub- structure SS, Fig. 2a shows, in dashed lines, further links L ¹ from and to the rest of the model MO (not depicted in Fig. 2a) outside the sub- structure SS .

Figs. 2c and 2d show two different representations of a monopartite candidate graph CG which was mapped from the sub structure SS of Figs. 2a and 2b (in this exemplary illustra tion: without input cones IN) . Therein, the nodes N , N ₂ , N ₃ , N ₄ have node types, which are differentiated, in the example of Figs. 2c and 2d, by lines identifying the nodes Ni, N ₂ , N ₃ , N ₄ : In this example, solid lines and dashed lines symbolise a first and a second node type, respectively; in general, the candidate graphs CG may have node types from a set of dozens or even hun dreds of different node types as necessary. A node type in cludes the type of a cell Ci mapped to the node N _m , e.g., the cell Ci may be a logical AND, OR etc.; moreover, the node type may be another parameter of the cell Ci, e.g., the bit width or the like; furthermore, the node type may comprise parameters of the links L _k between the respective cell Ci and its neighbours, etc., or user defined attributes of the node. A node type may even comprise more than one such parameter, in a combination and/or in two or more dimensions, i.e., the node type is op tionally multi -dimensional .

Coming back to the method 1 of Fig. 1, in a step 5 a sepa rate n-dimensional match vector MV (Fig. 4) is created for each candidate graph CG that was created in step 4. For creating the match vectors MV, a number of n graphlets GL, one for each di mension Di, D ₂ , D _n , generally D _t , of the match vector MV, was predetermined. Each graphlet GL has nodes N _GI , N _G 2, ..., generally N _Gq , and edges E _GI , E _G2 , ..., generally E _Gr , and each node N _Gq has a node type, see Figs. 3a and 3b. The graphlets GL differ from each other in the node types, in the number of nodes N _Gq or edges E _Gr , and/or in their combination, i.e., in the structure of the graphlets GL . While some graphlets GL may have two nodes N _Gq , others may have three or more nodes N _Gq . However, the num ber of nodes N _Gq in the graphlets GL is generally lower or even substantially lower than the number of nodes N _m in typical can didate graphs CG.

Figs. 3a and 3b show two different examples of graphlets GL, both of which have three nodes N _Gq . The nodes N _Gq and edges E _Gr of the graphlet GL in the example of Fig. 3a form a 2-to-l coalescence, whereas the nodes N _Gq and edges E _Gr of the graphlet GL in the example of Fig. 3b form a l-to-2 bifurcation. Similar to the examples of Figs. 2c and 2d, two different node types of the graphlets GL shown in Figs. 3a and 3b are symbolised by solid lines and dashed lines, respectively. It shall be under stood that, like the candidate graphs CG, also the graphlets GL may have nodes N _Gq of more than two different types, e.g., a subset of a set of dozens or even hundreds of node types .

As shown in the example of Fig. 4, each match vector MV is created in step 5 of the method 1 by counting the occurrences of each of the predetermined graphlets GL in the candidate graph CG the respective match vector MV is created for, and by filling each count Xi, x ₂ , ..., x _n , generally x _t , of occurrence in a different one of the dimensions D _t (here: fields) of the match vector MV. Thereby, each dimension D _t of the match vector MV created for a respective candidate graph CG comprises the count x _t of occurrences, in the candidate graph CG, of a dif ferent one of the predefined graphlets GL . In the simplified example of Figs. 2d, 3a and 3b which comprises one candidate graph CG and two different graphlets GL, the match vector MV is two-dimensional, one dimension D _t for each graphlet GL of Figs. 3a and 3b, respectively. The graphlet GL of Fig. 3a occurs in the nodes N _I -N ₂ -N ₃ and in the nodes N; _L -N ₃ -N ₄ of the candidate graph CG of Fig. 2d; therefore, the first dimension Di of the match vector MV would comprise the count Xi = 2. The graphlet GL of Fig. 3b occurs only in the nodes N _I -N ₃ -N ₄ of the candidate graph CG of Fig. 2d and the sec ond dimension D ₂ of the match vector MV, therefore, would com prise the count x ₂ = 1.

It shall be noted that, for typical hardware systems HS, some dozens or even some thousands of candidate graphs CG and match vectors MV may be created by the method 1; moreover, the number n of predetermined graphlets GL and, hence, the n dimen sions D _t of each match vector MV may be up to a few dozen or even a few hundred.

In one embodiment, a fixed number n of graphlets GL may have been provided - and thereby be predetermined - for step 5. Alternatively, a set T of graphlets GL may generally be pro vided for the method 1 and each graphlet GL of the set T is matched with all candidate graphs CG. In this case, only such graphlets GL of the set T are predetermined for step 5, for which graphlets GL a match is found in at least one of the can didate graphs CG. Therein, n is the number of graphlets GL of the set T for which a match was found.

In the next step 6 of Fig. 1, the candidate graphs CG are clustered in clusters CL (Fig. 5) on the basis of similarity of the created match vectors MV.

A multitude of techniques to determine the similarity be tween vectors is known in the art and may be applied to the match vectors MV. In one embodiment, however, a principal com ponent analysis is applied to the created match vectors MV. By the principal component analysis, the number n of dimensions D _t of the match vectors MV can be significantly reduced in step 6, e.g., to only two dimensions Di, D ₂ as shown in Fig. 5, even when the original dimensionality was materially higher. Thereby, the determination of the similarity of the match vec tors MV is facilitated.

Many different algorithms for clustering are known in the art and can be used. In one embodiment, however, the step 6 of clustering the candidate graphs CG is performed using a den sity-based clustering algorithm, e.g., using the density-based algorithm known as "OPTICS" in the art.

As shown in the example of Fig. 5, the clustering of step 6 results in the candidate graphs CG being scattered over a (here: two-dimensional; in other cases: multi -dimensional ) area A spanned by the dimensions D _t of the match vector MV. Therein, a candidate graph CG which has a match vector MV that is simi lar to the match vector MV of another candidate graph CG is closer to said other candidate graph CG than to a further can didate graph CG having a dissimilar match vector MV. Thereby, candidate graphs CG lying side by side in the area A are clus tered in the clusters CL. Candidate graphs CG of the same clus ter CL indicate similar structural composition and, hence, com parable functional behaviour of the sub- structures SS, from which these candidate graphs CG were mapped.

In a subsequent validation step 7, it is therefore suffi cient to select only one candidate graph CG of each cluster CL and determine the functional behaviour of the respective sub structure SS said candidate graph CG was mapped from. When the functional behaviour of this sub- structure SS is invalid, the hardware system HS is not validated. When, on the other hand, the functional behaviour of this sub- structure SS is valid, further candidate graphs CG of the same cluster CL need not be selected. The same is repeated for one candidate graph CG of each of at least some of the remaining clusters CL until either an invalid functional behaviour of a respective sub- structure SS is determined or until the functional behaviour of the re spective sub- structure SS of the selected candidate graph CG of each further cluster CL is valid. In the latter case, the hard ware system HS is validated.

Some clusters CL may be omitted in step 7, e.g., because they are located in a specific part, for example a remote part of the area A, such that there are good reasons to reliably ex pect that the behaviours of the respective sub- structures SS of candidate graphs CG in those clusters CL are valid.

It shall be understood that the structural equivalence may be determined in step 2 on a level of description of the hard ware system HS which is further abstracted from the netlist model MO.

Fig. 6 depicts one example of such an abstraction of the hardware system's HS description. However, other examples are known to the skilled person. In the example of Fig. 6, said step 2 of determining sub- structures SS in the model MO com prises, in essence, three sub-steps 8 to 10:

The first sub-step 8 relates to mapping the cells Ci and links L _k of the whole model MO to nodes N _m and edges E _p of a mo- nopartite model graph MG, wherein each node N _m has a node type. Such mapping was exemplified with reference to Figs. 2a to 2d above. Similarly, the cells Ci and links L _k of each of the pro vided reference structures RS are mapped to nodes N _m and edges E _p of a monopartite reference graph RG, wherein each node N _m has a node type.

In the second sub- step 9, sub-graphs SG are searched and found in the model graph MG, wherein each sub-graph SG matches one of said reference graphs RG. Thereafter, in the sub-step 10, the respective sub- structure SS for each of said found sub graphs SG is determined in the model MO by re-mapping the sub graph SG back to the model MO, i.e., by finding the respective sub- structure SS the sub-graph SG was mapped from.

The invention is not restricted to the specific embodi ments described in detail herein, but encompasses all variants, modifications and combinations thereof that fall within the framework of the appended claims.