**Team8 Hardware Security Final - Logic Locking**
Members:陳威任, 劉祐瑋, 劉得崙, 吳柏毅

Hackmd link:

Completion: 100%
- [x] Random logic locking
- [x] Fault analysis-based logic locking
- [x] Strong logic locking
- [x] Makefile for three different benchmarks using different logic locking methods.
- [x] Visualization
- [x] Quality analysis

Table of Contents:
[TOC]

# Introduction to Logic Locking and SAT Attack

### Logic Locking
* Definition: **Logic locking** is a design concealment mechanism used to protect IPs integrated into modern System-on-Chip (SoC) architectures from various hardware security threats within the IC manufacturing supply chain. It helps to guard against **reverse engineering**, **IP piracy**, **overproduction**, and unauthorized activation.
* The primary method involves inserting **additional logic gates**, referred to as **key gates**, into the IC design. These gates ensure the circuit operates correctly only when the correct key is applied.
* Reference: [*Advances in Logic Locking: Past, Present, and Prospects. Hadi Mardani Kamali, Kimia Zamiri Azar, et al.*](https://eprint.iacr.org/2022/260.pdf)


### SAT Attack
* Definition: A **SAT (Satisfiability) Attack** is a potent method used to undermine logic locking schemes. It involves using a SAT solver to iteratively deduce the correct key by examining the circuit’s responses to different input patterns.
* The SAT solver efficiently identifies key values that differentiate between correct and incorrect outputs, effectively decoding the locked circuit.
* Rule out incorrect key values by using **distinguishing input patterns (DIPs)**
* Reference: [*SAT Attack on Logic Locking*](https://www.youtube.com/watch?v=y6efE5TjoCU)
* Reference: [*SAT Attack Tool*](https://git.uwaterloo.ca/jmshahen/LogicLocking-Empirical/-/tree/master/SAT/spramod-host15-logic-encryption-90a8ca47d847)


### Types of Logic Locking
* Random Logic Locking
1. Concept: Involves randomly selecting any input, output, or internal wire for locking.
2. Reference: *EPIC: Ending Piracy of Integrated Circuits. Roy, Jarrod A. et al.*
* Fault Analysis-Based Logic Locking
1. Concept: Utilizes fault injection analysis to identify optimal locations for key gate insertion, aiming to maximize the impact of incorrect keys.
2. Reference: *Fault analysis-based logic encryption. Rajendran, J., Zhang, H., et al.*
* Strong Logic Locking
1. Concept: Ensures that the locked gates are pairwise secure, meaning no single input pattern can propagate an incorrect key to the output.
2. Reference: *On Improving the Security of Logic Locking. M. Yasin, J. J. Rajendran, et al.*

---

# Three Types of Logic Locking

## (**A**) Random Logic Locking
The concept of Random Locking is to randomly select any input, output, or internal wire for locking. Using `srand(time(0))` ensures a different key is generated with each program execution.

### ‧ Randomly Select and Insert Lockgate

### ‧ lockgate_insertion() detail
(1) Choose a key value and corresponding lock type ("XNOR" for 1, "XOR" for 0).
(2) Create a lockgate (differing between output gate and others).
(3) Set lockgate inputs.
(4) Copy original's outputs to lockgate's output.
(5) Change other inputs affected by this lockgate's insertion.
(6) Change original gate's output to lockgate.


## (**B**) Fault Analysis-Based Logic Locking

* Fault Analysis-Based Logic Locking initially calculates the fault impact for each gate. Fault impact refers to the number of detections when a gate is stuck at 0 or 1 across many input test patterns. A detection occurs if the primary output differs from the fault-free condition, indicating an impact. The algorithm selects the location with the highest fault impact score for key gate insertion, ensuring that an invalid key significantly affects the circuit's output accuracy.

* The algorithm iterates through K rounds (where K is the length of the key). In each round, it identifies the location with the highest fault impact (referred to as detect_time in our implementation), inserts an XOR gate, and updates the entire circuit. After inserting XOR gates throughout the circuit, we randomly generate keys to determine whether to convert an XOR gate to an XNOR gate. Unlike the original paper where the key is predetermined, we randomly generate the key and decide only on the key's length.

### pseducode for Fault analysis-based logic locking:

Below, we will briefly introduce the operations corresponding to each section of the code:

### ‧ `eval()` : Evaluate a Gate's Output Value
We use recursion to calculate from the output end back to the input end. A return occurs if today it is stuck at fault or if it is at the input end, then we use the input value.


### ‧ Two For Loops: Generate Test Patterns and Fault-Free Values for POs


### ‧ Two For Loops: Test Each Gate's Fault Impact (detect_time) When Stuck at 0 and 1


### ‧ Identify the Gate with the Maximum Impact


### ‧ Insert Logic Lock

Based on a random key, decide whether to insert an XOR or XNOR gate. After insertion, connect the lock to all the original gate output wires.


## (**C**) Strong Logic Locking
The principle of Strong Logic Locking is to ensure that no specific vector can propagate a key value to the output, achieving what's known as pairwise security.

### ‧ Strong Logic Locking Algorithm
### ‧ FindEdgeType(): Determine if two locks are pairwise secure
### ‧ DFS(): Depth First Search

# Circuit Visualization
Initially, we used the abc tool in Ubuntu for visualization, but we encountered limitations with node counts over 500. Therefore, we developed a custom C code for visualization, similar to the abc tool but displaying gate names and using a color scheme where red inverted triangles represent inputs and blue triangles represent outputs.

**Key Code Insights:**
- Open the `.bench` file.
- `gvContext()` initializes the Graphviz drawing context.
- Create a directed graph.
- Create two subgraphs for inputs (`sg_input`) and outputs (`sg_output`), setting their layout attributes to "same" (same level).
- Read each line of data and parse each component and connection using the `strtok` function.
- Based on the data type (input, output, gate type), create corresponding nodes and edges.
- Set attributes for nodes and edges.
- Use `gvLayout` function to apply a layout algorithm to the graph.
- Render the graph to a PDF file.


**the result of Image Placed on Last Page**

# Execute Makefile

The Makefile allows operation of different algorithms to generate `.bench` files (with logic locks applied) and provides tools for verifying performance and consistency.



Demonstration of Possible Commands (execute in the 8_FinalProject_Code folder):
- **make random_17**: Other options include strong_17, flg_17, etc., where the name indicates the algorithm and the number indicates the different circuit.
- **make sld_17**: Other options include sld_432, sld_3540 (consistent with the first command).
- **make lcmp_17**: Other options include lcmp_432, lcmp_3540(consistent with previous commands).

# Analysis of the Security and Equivalence of Locked Logic

### Fault Analysis-Based Logic Locking on c17.bench


1. Key length = 2
2. Iteration = 1
3. Backbones count = 0
4. Cube count = 70
5. CPU time = 0.005994
6. Max RSS = 1.53906
7. Gates = 8
8. LCMP: **equivalent**

### Random Logic Locking on c432.bench


1. Key length = 128
2. Iteration = 34
3. Backbones count = 0
4. Cube count = 65656
5. CPU time = 0.51577
6. Max RSS = 7.09375
7. Gates = 288
8. LCMP: **equivalent**

### Strong Logic Locking on c3540.bench


1. Key length = 128
2. Iteration = 24
3. Backbones count = 0
4. Cube count = 207138
5. CPU time = 2.3612
6. Max RSS = 14.4336
7. Gates = 1797
8. LCMP: **equivalent**

# Test Quality Way (Please not use above result)

**Please, TA, execute the following three commands for our quality assessment. We have prepared three `.bench` files in the ref directory to significantly reduce simulation time:**

1. make test1
2. make test2
3. make test3

**If using the prepared files isn't feasible, please run the following commands, which will automatically generate outputs (note that test5 will take a long time):**

4. make test4
5. make test5
6. make test6

Both sets of commands are for applying random logic locking to c17, fault analysis-based logic locking to c432, and strong logic locking to c3540, respectively.

:::danger
注意:如果要測試功能性，不想等那麼多時間請至fault.cpp調低test_pattern數量。


:::
# Hardness of This Assignment
(1) Fault-based and Strong Locking require knowledge from a VLSI Testing course, making implementation more challenging without such background.
(2) Initially, when modifying the `.bench` files, the syntax required for key inputs by sld and lcmp was unclear and had to be inferred from source code available online, complicating the debugging process based on logic alone.

# result of Visualization
:::danger
注意:這裡會降畫質，如果要清楚的圖，可以至/visualization資料夾中找到原始pdf檔案

:::

## C17(Original)


## C17 after insert logic lock


## C432(Original)


## C432 after insert logic lock


## C3540(Original)


## C3540 after insert logic lock