Trigger activation by repeated maximal clique sampling

A system comprising:

• one or more computing processors;
• and
• one or more memory storage elements;
• wherein the one or more computing processors are configured to:
• obtain a design graph representation of an electronic circuit;
• construct a satisfiability graph from the design graph representation, wherein the satisfiability graph includes a set of vertices representing rare signals of the electronic circuit and satisfiability connections between the vertices;
• find a plurality of maximal satisfiable cliques in the satisfiability graph, wherein a maximal satisfiable clique corresponds to a triggering condition for a payload of the electronic circuit;
• generate a test vector for each of the maximal satisfiable cliques;
• and
• perform a test for a presence of a hardware Trojan circuit in the electronic circuit using the generated test vectors as input signals.

A computer-readable medium having instructions stored thereon that, in response to execution by a computer-based system, cause the computer-based system to perform operations comprising:

• obtaining a design graph representation of an electronic circuit;
• constructing a satisfiability graph from the design graph representation, wherein the satisfiability graph includes a set of vertices representing rare signals of the electronic circuit and satisfiability connections between the vertices;
• finding a plurality of maximal satisfiable cliques in the satisfiability graph, wherein a maximal satisfiable clique corresponds to a triggering condition for a payload of the electronic circuit;
• generating a test vector for each of the maximal satisfiable cliques;
• and
• performing a test for a presence of a hardware Trojan circuit in the electronic circuit using the generated test vectors as input signals.