Outsourcing of design and manufacturing processes makes integrated circuits (ICs) vulnerable to adversarial changes and raises concerns about their security and integrity. The difference in the levels of abstraction between the initial specification and the final available circuit design poses a challenge for analyzing the final circuit for malicious insertions.

In this thesis, we present a novel approach for the analysis of circuits using graph algorithms and different concepts from linear algebra, signal processing and machine learning techniques to detect malicious insertions and reverse engineer a given IC. Our first study provides a framework to flag the malicious nodes using the simulation results of the chip. The second part of the thesis focuses on reverse engineering where we present two algorithms to infer high-level blocks in an untrusted circuit by using a reference behavioral design or a corresponding block diagram accompanied by a natural-language document. Reverse engineering helps reduce the complexity of verification/analysis by partitioning the circuit into smaller parts.

All algorithms have been implemented and demonstrated to be scalable to significant sized ICs. They present valuable insights for reverse engineering digital ICs as well as for Trojan detection.