A Practical Split Manufacturing Framework for Trojan Prevention via Simultaneous Wire Lifting and Cell Insertion

Trojans and backdoors inserted by untrusted foundries have become serious threats to hardware security. Split manufacturing is proposed to hide important circuit structures and prevent Trojan insertion by fabricating partial interconnections in trusted foundries. Existing split manufacturing frameworks, however, usually lack security guarantee and suffer from poor scalability. It is observed that inserting dummy cells and wires can have high potential on overcoming the security and scalability problems of existing methods, but it is not compatible with current security definition. In this paper, we focus on answering the questions on how to define the notion of security and how to realize the required security level effectively and efficiently when the insertion of dummy cells and wires is considered. We first generalize existing security criterion by modeling the split manufacturing process as a graph problem. Then, a sufficient condition is derived for the proposed security criterion to avoid the computationally intensive operations in traditional methods. To further enhance the scalability of the framework, we propose a secure-by-construction split manufacturing flow. For the first time, a novel mixed-integer linear programming (MILP) formulation is proposed to simultaneously consider cell and wire insertion together with wire lifting. A Lagrangian relaxation algorithm with a minimum-cost flow transformation technique is employed to solve the MILP formulation efficiently. With extensive experiments, our framework demonstrates significantly better efficiency, overhead reduction, and security guarantee compared with the previous state-of-the-art.