A fabless chip company designs a circuit but sends the design to an offshore foundry to fabricate it, and nothing stops that foundry from reading the netlist, overproducing the chip, or selling the design. The standard defense is logic locking: key-controlled gates are inserted so the fabricated circuit computes the wrong function until a secret key is applied, and only the legitimate owner activates it. Unfortunately, an adversary with one activated chip can use a SAT solver — a program that finds inputs satisfying Boolean constraints — to query the working chip and systematically rule out wrong keys, breaking most locking schemes in minutes Protect Your Chip Design Intellectual Property: An Overview. The locking styles that survive this attack, such as Anti-SAT blocks Anti-SAT: Mitigating SAT Attack on Logic Locking or transistor-level redaction fabrics A TRAP for SAT: On the Imperviousness of a Transistor-Level Programmable Fabric to Satisfiability-Based Attacks, are so expensive in silicon area that no designer can apply them everywhere. So the real question is not how to lock, but where: given a budget of key bits, area, and delay, which parts of a large design get the strong protection and which go without?
Today that choice is made by heuristics. The best existing tool, a genetic-algorithm design-space explorer for high-level synthesis Optimizing the Use of Behavioral Locking for High-Level Synthesis, shows that locking every candidate point is wasteful — a selective subset reaches nearly the same security with over 90% fewer key bits — but it offers no worst-case guarantee and takes hours to converge. Worse, both it and every other scheme optimize one global security number for a monolithic core. On a modern system-on-chip assembled from IP blocks from multiple teams Hardware Design and Security in the Era of Chiplets and LLMs, a global optimizer will happily starve a secondary block of protection entirely, because protecting the primary block moves the aggregate metric more. That is exactly the pathology the fair-allocation literature documents in facility siting and grid curtailment: utilitarian optimization creates service deserts Maximizing Coverage While Ensuring Fairness: A Tale of Conflicting Objectives; Optimal Net-Load Balancing in Smart Grids with High PV Penetration.
Core Claim
Selecting locking points under a resource budget can be formulated as constrained submodular maximization: each candidate point covers some set of input patterns that a wrong key corrupts, and this corruption coverage exhibits diminishing returns, so a linear-programming relaxation — the standard trick of letting a discrete yes/no decision become a continuous value in $[0,1]$, solving the easy continuous problem, then rounding back to yes/no decisions — with swap rounding gives a near-optimal selection in seconds, with a provable approximation bound, and with per-partition security floors that no genetic or greedy search provides. Concretely, let $x_i \in [0,1]$ say how much of candidate locking point $i$ we take, $w_i$ its cost in key bits and area, and $F_p(x)$ the expected corruption coverage of partition $p$ (a functional block, say, or a timing path). We solve
$$\max_x \sum_p F_p(x) \;\; \text{subject to} \;\; \textstyle\sum_i w_i x_i \le B, \;\; F_p(x) \ge \ell_p \text{ for every } p,$$
where $B$ is the global budget and $\ell_p$ is a designer-chosen security floor per block. Swap rounding — repeatedly picking two fractional variables and shifting mass between them until one hits 0 or 1 — then returns an integral selection that satisfies the budget exactly and respects the floors, inheriting the budget-feasibility guarantees of From Fractional Solutions to Discrete Decisions and A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint. The equity machinery, including the feasibility trap and the frequency factor $f$ that degrades parity guarantees, is imported from the Fair Maximum Coverage work of Maximizing Coverage While Ensuring Fairness, and reinterpreted for hardware: in a netlist, $f$ corresponds to how many timing cones and fan-out regions a gate belongs to, which is exactly what determines how tightly per-block floors can be honored.
Research Program
The program has three parts. First, we build the selection engine: a tool that ingests an HLS specification (via Bambu) or a gate-level netlist, enumerates candidate locking points as in Optimizing the Use of Behavioral Locking for High-Level Synthesis, estimates each point's cost (key bits, LUT/area, delay after synthesis), measures its corruption coverage by simulation, and then solves the relaxation and rounds it. Second, we establish — or refute — the structural assumption: the whole approach rests on the coverage function being approximately submodular (adding a locking point helps less when much is already locked). We will measure the empirical submodularity ratio on every benchmark and report it honestly; if the ratio $\gamma$ degrades, the guarantee degrades proportionally to $\gamma(1-1/e)$, and we will say so rather than hide it. We deliberately avoid the nearly-linear algorithm of A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint as an implementation vehicle, because its leading constant $(1/\epsilon)^{O(1/\epsilon^4)}$ is astronomically large; instead we use a plain LP solve plus swap rounding, the combination shown to scale to 1,000-node instances in seconds in Equilibrium Computation and Robust Optimization in Zero Sum Games With Submodular Structure. Third, we analyze the fairness side: we adapt the color-discrepancy bounds of Maximizing Coverage While Ensuring Fairness to netlist topology, deriving how the integrality gap and achievable floors degrade with the fan-out overlap of the circuit graph, and we quantify the price of fairness — the global entropy sacrificed to guarantee every block its floor.
One design choice deserves emphasis: the floors $\ell_p$ are set by the designer, per block, from the threat model. A block containing a root-of-trust gets a high floor; an error-resilient accelerator gets a low one. This is where the application-level evidence of Robust and Attack Resilient Logic Locking with a High Application-Level Impact enters: they showed global error-rate locking fails precisely on machine-learning workloads, where corruption must be steered to critical minterms to matter. Our floors give the optimizer a principled place to encode that block-specific knowledge, replacing their manual, simulation-guided selection.
Baselines
The naive reference point is random locking, which places key gates uniformly; on the arf HLS benchmark at a matched key budget it reaches a normalized differential entropy of 0.939 Optimizing the Use of Behavioral Locking for High-Level Synthesis, and it never protects any block deliberately. The strongest existing competitor is the genetic-algorithm design-space exploration of Optimizing the Use of Behavioral Locking for High-Level Synthesis, which reports a normalized differential entropy of 0.999 on arf at budget c4, versus 0.926 for its topological alternative — the number to beat on global security, though it optimizes a single monolithic metric with no per-block guarantee and converges only after 20–30 generations of search. To make the comparison fair we run both methods on identical benchmark suites (the eight Bambu/MiBench/CHStone designs including arf and sha, plus ISCAS'85 circuits c1355, c1908, c3540 and MCNC/EPFL designs), at identical key-bit budgets, and we give the genetic algorithm the same wall-clock budget our LP pipeline uses end-to-end; we also report it with its published settings, since its authors' tuning is part of its strength. Because a global number can hide a starved block, the primary head-to-head metric is worst-partition entropy: the security of the least-protected functional block. Beating the baseline means matching its global entropy within one point (≥0.99 normalized) while guaranteeing every partition its floor — we expect the genetic search to leave at least one partition near zero — and cutting selection time from hours to seconds. We additionally run greedy insertion, since it is the default in EDA practice, and an exact integer program via a commercial solver on the smallest instances as an optimality reference; the LP pipeline beats greedy if it dominates it on global entropy at every budget and beats the exact solver only in runtime, using it instead to measure our optimality gap. Finally, the key ablation isolates the proposal's two ingredients: the same LP pipeline run with all floors removed (pure utilitarian relaxation) shows what equity costs, and swap rounding replaced by naive independent rounding shows whether budget-exactness matters, given that independent rounding is known to violate hard budgets From Fractional Solutions to Discrete Decisions.
Why not just…?
Why not just run the genetic algorithm or a greedy placer? The genetic approach is a genuine threat on the global metric, and we treat its 0.999 on arf as the bar rather than a strawman. But it carries three costs our experiments will make concrete: it takes hours against seconds; it has no worst-case bound, so a designer cannot certify any block's protection level before an adversary tries; and it optimizes a monolithic objective, so nothing stops it from sacrificing a secondary block — the same concentration pathology documented for utilitarian optimizers in Maximizing Coverage While Ensuring Fairness and Optimal Net-Load Balancing in Smart Grids with High PV Penetration. Greedy is weaker still: in adversarial settings greedy fails to scale and yields fragile solutions where relaxation-plus-rounding methods succeed Equilibrium Computation and Robust Optimization in Zero Sum Games With Submodular Structure, and greedy rounding violates hard resource budgets From Fractional Solutions to Discrete Decisions. Our decisive check is the worst-partition-entropy comparison at matched budgets; if the genetic search also happens to protect every block, our runtime argument alone would not carry the paper, and we would report that honestly.
Why not just maximize global security — why does a circuit need "fairness"? The word is a metaphor, but the underlying problem is not about social equity; it is about worst-case exposure in a multi-block system. An untrusted foundry steals whichever block is easiest to extract, so the system's security is its minimum over blocks, not its average — the same min-max logic used for service floors in facility allocation Joint Optimization of Fair Facility Allocation and Robust Inventory Management for Perishable Consumer Products and class-balanced protection in epidemic resource allocation Prathyush Sambaturu et al.. The empirical evidence that global metrics mislead is already in the literature: globally adequate locking left machine-learning models running at near-normal accuracy until protection was explicitly steered to the critical minterms Robust and Attack Resilient Logic Locking with a High Application-Level Impact. Our floors are simply the designer's way of stating that minimum. The price-of-fairness measurement in the experiments quantifies what this costs in global entropy, so a skeptic unconvinced by the argument still gets the numbers to judge it.
Why not just solve the integer program exactly with a commercial solver? On small circuits we will, as the optimality reference. The reason it cannot be the main method is scale and time: the discrete allocation problem is NP-hard, and exact solutions blow up on flattened netlists — a single $2\times2$ redaction fabric already involves over 700 key bits and a logic model with nearly 12,000 clauses A TRAP for SAT, and exact methods are known to miss hard operational deadlines in comparable networked resource problems Optimal Net-Load Balancing in Smart Grids with High PV Penetration. The relaxation route also delivers something the exact solver does not: a certified approximation ratio on instances too large to solve exactly, and rounding that never busts the budget. The honest risk here is that our LP with per-block floors is itself slow on the largest netlists; the scaling experiment below is designed to surface that rather than assume it away.
Proposed Experiments and Decisive Checks
The evaluation runs on three tiers. On the HLS tier we use the eight Bambu/MiBench/CHStone benchmarks from Optimizing the Use of Behavioral Locking for High-Level Synthesis, partitioned into functional sub-blocks, sweeping key-bit budgets and comparing global and worst-partition differential entropy against the genetic baseline, greedy, random, topological, and the exact ILP where feasible. On the gate-level tier we lock ISCAS'85 circuits (c1355, c1908, c3540) and MCNC/EPFL designs, composing our selected points with SAT-hardened Anti-SAT blocks Anti-SAT: Mitigating SAT Attack on Logic Locking and measuring PPA after synthesis with the Nangate 45nm library, the same flow used in Raise Your Game for Split Manufacturing. We then attack every locked circuit with the oracle-guided SAT attack under the community's own protocol: a 10-hour timeout, matching the setting in which a 14-bit obfuscated Anti-SAT block already defeated the attack Anti-SAT: Mitigating SAT Attack on Logic Locking, and reporting per-block key recovery so that a single unprotected block is visible, in the spirit of the red-team evaluation that showed random locking keys are 100% recoverable while SFLL keys were not Benchmarking at the Frontier of Hardware Security: Lessons from Logic Locking. Four checks decide the proposal: the measured submodularity ratio must stay high enough that the $\gamma(1-1/e)$ guarantee is meaningful; worst-partition entropy under our floors must beat every heuristic at matched budget and wall-clock; selection time must be seconds, not hours, at netlist sizes in the thousands of gates; and the price of fairness — global entropy lost to the floors — must be small and quantified as a function of the netlist's fan-out overlap, closing the loop between the circuit's topology and the frequency-factor bound of Maximizing Coverage While Ensuring Fairness. As an extension, we will replay the application-level evaluation of Robust and Attack Resilient Logic Locking on PARSEC and ImageNet workloads to test whether per-block floors recover the application-level corruption that monolithic locking misses.
References
- Protect Your Chip Design Intellectual Property: An Overview
- Anti-SAT: Mitigating SAT Attack on Logic Locking
- A TRAP for SAT: On the Imperviousness of a Transistor-Level Programmable Fabric to Satisfiability-Based Attacks
- Optimizing the Use of Behavioral Locking for High-Level Synthesis
- Hardware Design and Security in the Era of Chiplets and LLMs
- Maximizing Coverage While Ensuring Fairness: A Tale of Conflicting Objectives
- Optimal net-load balancing in smart grids with high PV penetration
- Bidder Selection Problem in Position Auctions: A Fast and Simple Algorithm via Poisson Approximation
- A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
- Equilibrium Computation and Robust Optimization in Zero Sum Games With Submodular Structure
- Robust and Attack Resilient Logic Locking with a High Application-Level Impact
- Joint Optimization of Fair Facility Allocation and Robust Inventory Management for Perishable Consumer Products
- Scalable and Memory-Efficient Algorithms for Controlling Networked Epidemic Processes Using Multiplicative Weights Update Method
- Raise your game for split manufacturing: restoring the true functionality through BEOL
- Benchmarking at the Frontier of Hardware Security: Lessons from Logic Locking