1. Logic Locking

Logic locking protects design intent through structural obfuscation by inserting key-controlled logic elements into the gate-level netlist, while preserving functional integrity. The secret keys are stored in tamper-proof memory, ensuring the encrypted IC operates correctly only upon receiving the correct key input. Without the correct keys, adversaries cannot restore the original circuit functionality, effectively mitigating risks of reverse engineering and overproduction ^[3].

Since the inception of logic locking, a continuous cycle has emerged: new defense techniques are proposed, followed by research focused on breaking those defenses. Attacks against logic locking can be broadly categorized into two types: attacks targeting combinational logic locking and attacks targeting sequential logic locking. Each category can be further divided into Oracle-Guided attacks and Oracle-less attacks. Among Oracle-Guided attacks, the Boolean Satisfiability (SAT) attack is particularly significant ^[4]. It exploits the concept of key equivalence classes. By iteratively generating Distinguishing Input Patterns (DIPs) and using the correct outputs obtained from an oracle to constrain the key space, the SAT attack cracked all logic locking schemes proposed before it. Examples include schemes inserting XOR/XNOR gates ^[5], Look-Up-Tables (LUTs) ^[8], and Multiplexers (MUXs) ^[10]. All of these methods implemented functional obfuscation by adding logic elements to the original netlist and were highly vulnerable to the SAT attack.

Following the SAT attack, numerous countermeasures were developed. Point-function logic locking specifically aimed to maximize the number of iterations required for a SAT attack, thereby enhancing SAT resistance. Techniques like SARLock ^[12] and the Anti-SAT block ^[13] achieve this, forcing the SAT attack to approach its theoretical maximum iteration count. However, these point-function schemes are vulnerable to identification and removal through attacks like Signal Probability Skew (SPS) and other removal attacks ^[14], allowing adversaries to recover the original circuit function. Furthermore, point-function locking inherently exhibits low output corruptibility. To mitigate this vulnerability, composite schemes are often employed, such as combining it with Random Logic Locking (RLL), where the high output corruptibility of the RLL component significantly impacts the overall output corruptibility. However, AppSAT attacks can exploit the high output corruptibility of modules like RLL during early-stage iterations, prioritizes cracking high-corruptibility modules, effectively reducing the composite scheme to its low-corruptibility point-function locking scheme ^[15]. Newer proposals like DTL ^[15], G-Anti-SAT ^[16], and SAS ^[17] aim to increase output corruptibility based on the point-function locking structure and defend against other attacks. However, DTL increases output corruptibility at the cost of compromising SAT attack resilience. G-Anti-SAT imposes complex constraints and is relatively difficult to implement. SAS effectiveness relies heavily on the precise identification and selection of critical minterms; improper selection can negatively impact overall performance. To guard against removal attacks targeting point-function locking, the proposed TT-lock changes the original logic cone ^[18]. Building on this approach, SFLL was proposed to further enhance security. SFLL modifies the original circuit structure, using a restoration unit to generate correct functionality. While SFLL's resistance to SAT attacks depends on the configured Hamming distance, it trades off output corruptibility for SAT resilience ^[19]. Even with subsequent research achieving higher average corruptibility and reasonable security levels ^[20], the output corruptibility provided by SFLL remains relatively low.

2. Contributions

This paper introduces Maximum Output Corruption Anti-SAT Logic Locking, MOCASLL. Unlike previous approaches focused on increasing output corruption, MOCASLL fundamentally guarantees that incorrect keys induce maximum output corruption for the protected design. The design achieves this while maintaining near-maximal resistance to SAT attacks, incurring only a negligible reduction in required iterations from $2^n$ to $2^n - 1$. Furthermore, the correct key setting differs fundamentally from traditional Anti-SAT blocks, and the design offers enhanced resilience against removal attacks. MOCASLL incorporates two key components: the Iteration Increasing Unit IIU and the Corruptibility Increasing Unit CIU.

The major contributions of this paper are as follows.

1) MOCASLL ensures that incorrect keys induce output corruption approaching 50% of all outputs.

2) The design maintains near-maximal resistance to SAT attacks, incurring only a negligible reduction in required iterations (from $2^n$ to $2^n - 1$).

3) The Iteration Increasing Unit (IIU) exponentially increases SAT attack iterations, while the Corruptibility Increasing Unit (CIU) enforces the maximum output corruptibility.

4) The design provides improved resistance against removal attacks.

1. SAT Attack

SAT attack is the most effective logic locking attack, theoretically capable of breaking all encrypted combinational circuits. It operates on key equivalence classes (groups of keys producing identical outputs for all inputs) rather than individual key values. The attack iteratively generates distinguishing input patterns (DIPs) $X_d$ that yield different outputs for keys in different equivalence classes. Each DIP $X_d$ enables the elimination of all keys that produce incorrect outputs for that specific input.

The attack requires access to the encrypted gate-level netlist (obtainable via reverse engineering or an untrusted foundry) and an activated IC for oracle access. Attackers construct a miter circuit from the netlist, as shown in Fig. 1, where two locked circuit copies share primary inputs but have independent key inputs. Output differences are detected, and the SAT solver finds $X_d$ when a difference occurs. Applying $X_d$ to the activated IC reveals the correct output $Y_d$, and the pair ($X_d, Y_d$) is used to constrain the key space. This iterative process continues until no new DIPs are found, leaving only the correct key.

Fig. 1. Miter circuit to compute DIPs.

2. Anti-SAT Block

The Anti-SAT block is a means to defend against SAT attack, which mitigates the SAT attack by increasing the number of iterations of the SAT attack and thus increasing the running time of the SAT attack. The Anti-SAT architecture, as depicted in Fig. 2, consists of two complementary logic blocks $g$ and $\bar{g}$, where $\bar{g}$ is derived by appending an inverter to $g$. Both logic blocks share identical primary input vectors $\vec{X} = (X_1, ..., X_n)$ but are secured by distinct key vectors $\vec{K}_{l1} = (K_1, ..., K_n)$ and $\vec{K}_{l2} = (K_{n+1}, ..., K_{2n})$, yielding a total key size of $2n$. Each input $X_i$ is combined with corresponding key bits $K_i$ and $K_{i+n}$ to generate modified inputs $X_i \oplus K_i$ for $g$ and $X_i \oplus K_{i+n}$ for $\bar{g}$. The outputs of $g$ and $\bar{g}$ are then fed into a two-input AND gate to produce the final output $Y$. Consequently, the output of the Anti-SAT block is defined as $Y = g(\vec{X} \oplus \vec{K}_{l1}) \wedge g(\vec{X} \oplus \vec{K}_{l2})$. A fundamental property of the Anti-SAT block is that $Y$ output is 0 under correct key configurations, thereby avoiding the flipping of the original output. For incorrect keys, the output $Y$ dynamically depends on the input vector $\vec{X}$. To enforce this property, the correct key must satisfy the constraint that the $i$-th key bit in $\vec{K}_{l1}$ and $\vec{K}_{l2}$ holds identical values. This results in $2^n$ correct key combinations, as each of the $i$-bit key pairs ($\vec{L}_{l1}, \vec{K}_{l2}$) requires bitwise equivalence. Given the total key size of $2n$, the number of incorrect keys is $2^{2n} - 2^n$.

Fig. 2. Anti-SAT block.

Let the number of input patterns that drive the logic block $g$ to output 1 be denoted as $p$. Correspondingly, the number of input patterns causing $g$ to output 0 is $2^n - p$. From the definition of the output $Y$, it becomes logic 1 if and only if both logic blocks output 1 simultaneously, which occurs exclusively under incorrect key configurations. When executing the SAT attack on the Anti-SAT block, for any DIP, the number of incorrect keys triggering $Y = 1$ is quantified as $p \times (2^n - p)$. Consequently, each iteration eliminates at most invalid keys. Given the total number of incorrect keys $2^{2n} - 2^n$, the required number of SAT attack iterations $\lambda$ satisfies

It is easy to get that when the value of $p$ is 1 or $2^n - 1$, the iteration number $\lambda$ will reach the maximum value of $2^n$, which means that the SAT attack needs to iterate through all the input patterns in order to find the correct key, and thus it can be effectively defended against the SAT attack.

3. Other Attack on Anti-SAT

The Anti-SAT block attempts to thwart SAT attacks by increasing the number of required iterations. However, its inherent low output corruptibility creates vulnerabilities. The output corruptibility for a circuit obfuscation scheme is defined as:

For Anti-SAT and similar point-function schemes, the output corruptibility is very low, $Cr \in O\left(\frac{1}{2^n}\right)$ when the SAT attack's query limit is reached. Due to this low corruptibility, such schemes are often combined with logic locking techniques that exhibit high output corruptibility in composite schemes. However, the AppSAT attack exploits this composition by functioning as a SAT-based approximation method with early termination. It efficiently finds the correct key for the high-corruptibility locking component. By cracking this high-corruptibility module first, the AppSAT attack effectively reduces the composite locking scheme to its underlying vulnerable point-function locking scheme. Subsequently, this point-function scheme can be identified and removed by attacks such as the Signal Probability Skew (SPS) attack. The SPS attack exploits structural signatures within the Anti-SAT block. By analyzing the signal probability skew $s_x = Pr[x = 1] - 0.5$ across all signals in the reverse-engineered netlist, the attack identifies the Anti-SAT output gate. This gate exhibits a near-maximal absolute difference of skew (ADS) because its inputs typically have high but opposing skew values (e.g., $s_g \approx -0.5$ and $s_{\bar{g}} \approx 0.5$ for large $n$). Locating this gate via its high ADS and tracing its transitive fan-in allows the SPS attack to determine the gate's correct logic value and subsequently remove the Anti-SAT block by replacing its output with that constant value.

1. The Design Idea

As previously discussed, point-function logic locking resists SAT attacks by significantly increasing the number of iterations required. Taking the Anti-SAT block as an example, when $p = 1$, the SAT attack requires $2^n$ iterations. During each iteration, the SAT attack selects a DIP and eliminates keys that produce incorrect outputs for that DIP. To achieve a high number of iterations, it is necessary to design incorrect keys such that each key can only be invalidated by a specific DIP. Point-function logic locking exploits this principle: its incorrect keys have an output corruption of 1, meaning circuit functionality is inverted only for a specific input pattern. This enables the SAT attack to reach its maximum iteration count. However, this very mechanism also results in low output corruption for incorrect keys. Subsequent schemes like SFLL were designed to increase output corruption. However, this enhancement comes at the cost of SAT resistance. In SFLL, a single DIP can eliminate multiple incorrect keys. Crucially, the higher the output corruption designed for incorrect keys, the lower the scheme's resistance to SAT attacks becomes. Comparing SFLL and Anti-SAT reveals key differences: SFLL typically has $2^n$ keys. Increasing output corruption allows a single DIP to eliminate many keys, inevitably reducing the iteration count below the maximum possible. In contrast, the Anti-SAT block has $2^{2n}$ keys. While a single DIP can also eliminate multiple keys here, there exist at least $2^n$ incorrect keys in Anti-SAT, each requiring a unique DIP for invalidation. This ensures the SAT attack reaches its maximum iteration count of $2^n$.

To achieve robust SAT resistance while simultaneously maximizing output corruption, we employ a locking scheme using the same key length as Anti-SAT ($2n$ bits). The ideal input-output relationship for our design is depicted in Fig. 3. In this figure, the black area signifies regions where the output is flipped ($Y = 1$), while the white area represents normal operation ($Y = 0$). To ensure the SAT attack iterations approach the theoretical maximum of $2^n$, we must configure the locking so that as many input patterns as possible have at least one incorrect key that only that specific pattern can invalidate. Generally, a locking scheme needs to weigh the relationship between output corruptibility and its ability to resist SAT attacks. For a locked circuit, it is desirable to have high output corruptibility, with the ideal value approaching 1/2. At this level, correct and corrupted outputs are equally likely, providing the strongest obfuscation. As reflected in Fig. 3, this requires that the number of corrupted outputs under incorrect keys (represented by the gray regions) approaches half of the total possible outputs. Implementing the input-output relationship as depicted in Fig. 3 not only maintains high resistance against SAT attacks but also provides the highest possible output corruptibility characteristic.

Fig. 3. The input-output relationship that can resist SAT and provide the highest output corruptibility.

2. MOCASLL

Based on the aforementioned design concept, this paper proposes a novel logic locking scheme named Maximum Output Corruption Anti-SAT Logic Locking (MOCASLL). As its name implies, MOCASLL aims to protect circuits against SAT attacks while simultaneously maximizing the overall output corruption of the encrypted circuit, achieving a value approximately equal to half of the total outputs. As shown in Fig. 4, The proposed MOCASLL design consists of two distinct functional units that are inserted into the original circuit to provide protection: the Iteration Increasing Unit (IIU) and the Corruption Increasing Unit (CIU). The complete cryptographic key, denoted as $K = K_1 \parallel K_2$, comprises a total of $2n$ bits. Here, $K_1 = (k_1, k_2, ..., k_n)$ represents the $n$-bit key for the IIU, and $K_2 = (k_{n+1}, k_{n+2}, ..., k_{2n})$ represents the $n$-bit key for the CIU.

The outputs of these two units are interconnected via an XOR gate. This combined result is then XORed with the original circuit output $Y_o$, yielding the final output

Within the IIU, drawing inspiration from the effectiveness of point-function-based encryption schemes in resisting SAT attacks, we perform operations (XOR or XNOR) between the first $n$ bits of the key $K_1$ and the corresponding $n$ bits of the primary input $X$. The results of these operations are then fed into an AND gate network. This structure ensures that, across the combined space of primary inputs and IIU keys, each incorrect key $K_1$ flips the output value for exactly one specific input pattern. While this satisfies a critical condition for SAT attack resistance, it results in a low overall output corruptibility. To address this limitation, we designed the Corruptibility Increase Unit (CIU). In the CIU, a single primary input signal is connected to a single key input bit via an XOR or XNOR gate. Concurrently, one specific key bit from the $n$ bits of $K_2$, designated as the Selected Key (SK), has its logic value fed into a NAND gate. The outputs of these two gates (the XOR/XNOR gate and the NAND gate) are then combined using an AND gate. This design relaxes constraints on the primary inputs while strengthening constraints on the key inputs. Consequently, within the combined input-key space of the CIU, all keys except the SK exhibit an output corruption close to $2^{n-1}$ (i.e., half of the outputs are flipped for a given key). The SK itself produces zero output corruption.

Leveraging the XOR gate to connect the IIU and CIU outputs offers distinct advantages over traditional structures like the Anti-SAT block, which typically employ an AND gate. While maximizing the overall output corruptibility (Cr) with an AND gate requires both units to output `1' simultaneously across a large portion of the combined $2n$-bit key and $n$-bit primary input space - implying that each unit must achieve high individual corruptibility in its respective domain, potentially at the cost of SAT resistance - the XOR connection allows for a clear separation of concerns. The CIU can focus solely on maximizing Cr, while the IIU provides the essential SAT attack resistance. Across the entire $2n$-bit key space, the specific logic structure involving the SK dictates that for keys where $K_2$ equals the SK (i.e., $K_2 = SK$), the number of corrupted outputs is solely determined by the IIU. Given that the IIU produces exactly one corrupted output for each of its incorrect keys, this results in $2^n$ incorrect keys of the form $K_1 \parallel SK$, each producing exactly one corrupted output. Due to the point-function nature of the IIU's design, each of these keys can only be invalidated by its unique distinguishing input pattern, thereby maximizing the number of iterations required by a SAT attack. Among the remaining incorrect keys, there are $2^{2n-1} - 2^{n-1}$ incorrect keys that cause $2^{n-1} + 1$ corrupted outputs and $2^{2n-1} - 2^{n-1}$ incorrect keys that cause $2^{n-1} - 1$ corrupted outputs. Critically, this initial design lacks a correct key for normal circuit operation. To address this fundamental requirement of any locking mechanism - providing a usable correct key for legitimate users - we introduce a specific input pattern called the Indistinguishable Input Pattern (IIP). The logic value of this IIP is fed into the IIU's AND gate via a NAND gate. This modification strategically creates exactly one correct key that produces zero corrupted outputs across all primary inputs, enabling correct circuit functionality. Consequently, the distribution of the number of corrupted outputs across all keys in the final design is summarized in Table 1: yielding one correct key with 0 corrupted outputs, $2^n - 1$ incorrect keys each causing exactly one corrupted output, $2^n - 1$ incorrect keys each causing $2^{n-1}$ corrupted outputs, and $2^{2n} - 2^{n+1} + 1$ incorrect keys causing either $2^{n-1} + 1$ or $2^{n-1} - 1$ corrupted outputs, where the counts for these two latter categories differ by only one. Therefore, the total number of iterations required by the SAT attack is reduced from $2^n$ to $2^n - 1$, a reduction whose practical impact is negligible. According to the calculation formula shown in Eq. (2), the output corruptibility (Cr) over the total space of keys and primary inputs is expressed as

which approximates to

As $n$ increases, Cr asymptotically approaches $\frac{1}{2}$. This proves that MOCASLL provides both robust resistance against SAT attacks and near-maximal output corruptibility. In the next section, we will thoroughly validate MOCASLL's resilience against SAT and removal attacks, and discuss its comparison with other logic locking techniques aimed at enhancing output corruptibility.

Fig. 4. The structure of the proposed MOCASLL.

1. Analysis of SAT Attack Resistance

To assess the SAT attack resistance of our proposed MOCASLL scheme, We performed combinational SAT attacks on combinational circuits and sequential SAT attacks on sequential circuits. The iterations and runtime for varying benchmark circuits and input bits $n$ are detailed in Table 3. The attack threshold was set at 24 hours. We evaluated the scheme's SAT resilience by examining whether the required iterations and runtime exhibited exponential growth relative to $n$ within this threshold. For comparative analysis, we simulated the Anti-SAT module under identical hardware conditions; results are presented in Table 4.

As shown in Tables 3 and 4, MOCASLL achieves SAT resistance comparable to Anti-SAT in terms of iterations, consistent with our theoretical analysis. In terms of runtime, MOCASLL exhibits a shorter runtime than Anti-SAT. This stems from its reduced circuit overhead and lower logical complexity, which collectively diminish the complexity of constructing and solving the corresponding CNF formula by the SAT solver. For circuits with $n > 14$, the SAT attack runtime exceeds the 24-hour threshold. Moreover, the time required to decrypt both MOCASLL and Anti-SAT modules exhibits exponential growth as $n$ increases. These findings closely align with our theoretical security model, demonstrating strong resilience against SAT attacks.

2. Comparison of Output Corruptibility

We compare the output corruptibility enhancement achieved by our proposed design with other logic locking techniques, as summarized in Table 5. Our design demonstrates significant advantages in elevating corruptibility, whereas existing techniques-though designed to increase corruption-still exhibit substantially lower corruptibility. By maximizing the corruptibility in locked circuits, our approach asymptotically approaches the theoretical maximum of 50% as the input size $n$ increases.

3. Analysis of AppSAT Attack Resistance

In our proposed scheme, the output corruptibility for error keys specifically designed to resist SAT attacks is $\frac{1}{2^n}$, while for other incorrect keys it is close to $\frac{1}{2}$. The runtime of the AppSAT attack is not solely dependent on the circuit's output corruptibility. When the corruptibility is low, AppSAT can easily find an approximate key. Conversely, when the corruptibility is high, each iteration can quickly eliminate incorrect keys exhibiting high corruption, leaving behind the low-corruption keys effective against SAT attacks. Therefore, configuring an appropriate output corruptibility is crucial to defend against AppSAT attacks. Within our proposed CIU, while initially relaxing constraints on the primary inputs-adding only one input and one key bit constraint-to achieve maximum corruptibility, we can now tighten these constraints. This allows us to trade-off some output corruptibility for enhanced resistance to AppSAT attacks. The methodology for evaluating AppSAT resilience follows ^[12]. Since AppSAT runtime depends on multiple parameters, it is not an ideal metric for gauging defense strength. Instead, the corruptibility of the key returned by AppSAT significantly impacts its usability. Consequently, we define $m$ as the number of primary input constraints added within the CIU. Fig. 5 depicts the distribution of output corruption for incorrect keys returned by AppSAT (every 50 iterations) applied to MOCASLL with a 24-bit primary input, for varying $m$ values.

Fig. 5 reveals that when $m = 1$ -corresponding to maximum incorrect key corruption-the returned keys exhibit low corruption. This occurs because keys causing high output corruption have a high probability of being eliminated during iterations. As $m$ increases, the proportion of returned keys with higher corruption rises, but the overall corruptibility of the incorrect keys decreases. Thus, selecting an appropriate $m$ value is necessary to balance AppSAT resistance and circuit output corruptibility. Notably, unlike other logic locking schemes where the proportion of maximum-corruption incorrect keys within the key space diminishes as overall corruptibility increases, in our scheme, excluding the correct key and SAT-resistant keys, all remaining incorrect keys exhibit high output corruption. Even when we reduce the overall corruptibility to counter AppSAT attacks, MOCASLL maintains a superior output corruptibility compared to other techniques under identical conditions.

Fig. 5. The output corruption of the returned key in the AppSAT attack for MOCASLL with $n = 24$.

4. Analysis of Removal Attack Resistance

The SPS removal attack exploits ADS values to attack encrypted circuits. Generally, the ADS values of gates range between 0 and 1, but the last gate of Anti-SAT approaches 1, making it identifiable by sorting ADS values. However, our proposed design maintains the ADS value of the final gate within a moderate range, effectively hidden among the ADS values of other logic gates. For instance, in IIU and CIU designs, the average number of input patterns yielding output 1 per key is $\frac{2^{n-1}}{2^n}$ and $\frac{2^{n-1} \times (2^{n-1})}{2^n}$, respectively. Consequently, the ADS value of the final gate is $\left| \frac{2^{n-1} \times (2^{n-1})}{2^{2n}} - \frac{2^{n-1}}{2^{2n}} \right| \approx 0.5$. This design positions the ADS value within the median range, effectively camouflaging it among other logic gates and rendering the design resilient against SPS attacks.

5. Experiment on Overhead Comparison

In this paper, we employed Synopsys Design Compiler to measure the area and power consumption overheads of original circuits and locked circuits with $n = 15$, as illustrated in Figs. 6 and 7. The security of locked circuits has been validated previously. Experimental results indicate that our proposed MOCASLL achieves favorable circuit overhead performance, particularly in large-scale circuits such as des, where the additional area and power consumption account for only 2.9% and 2.5%, respectively. We further compared the area and power consumption overheads of MOCASLL with Anti-SAT and G-Anti-SAT on the des benchmark circuit at $n = 15$. The results, shown in Fig. 8, demonstrate that MOCASLL incurs both lower area and lower power overhead compared to Anti-SAT and G-Anti-SAT. This indicates that MOCASLL not only offers comparable SAT attack resistance (as shown in Tables 3 and 4) and higher output corruption (as detailed in Table 5), but also achieves lower circuit overhead. These demonstrate the effectiveness of MOCASLL in hardware implementations, showcasing its strong potential for secure and low-overhead circuit protection.

Fig. 6. The area overhead of MOCASLL

Fig. 7. The power overhead of MOCASLL

Fig. 8. The comparison of area and power overheads between MOCASLL, Anti-SAT, and G-Anti-SAT.