Logo image
Back
Modeling SAT-attack Search Complexity
Conference proceeding

Modeling SAT-attack Search Complexity

Saran Phatharodom, Nagarajan Kandasamy, Ioannis Savidis and IEEE
2020 IEEE INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS (ISCAS), pp 1-5
01 Jan 2020
DOI: https://doi.org/10.1109/ISCAS45731.2020.9180706

Abstract

Engineering Engineering, Electrical & Electronic Science & Technology Technology
In this paper, a metric based on mathematical modeling is proposed to evaluate the strength in security of a logic-locked circuit against a satisfiability (SAT) based attack. Current approaches estimate the SAT resilience experimentally based on time-to-solve or the number of calls to a SAT-solver. However, the estimate is often based on one sample or a small sample size. Due to the possible variation in the search path length of the SAT-attack, a measure of resilience based on statistical characterization is proposed. A probabilistic model of a SAT-attack search process is developed to properly capture the variation in the path length and report the SAT resilience as an expectation of the computational complexity. An estimator of the expected complexity, assuming an equally likely branching probability, is proposed. The model and the estimator allow for 1) the derivation of a closed-form estimate of the expected security, and 2) characterization of the key search space without experimental bias toward SAT-attack implementation or circuit topology. As a case study, an analysis of the security gain per inserted key gate is performed on a full adder circuit. The study reveals a monotonically increasing resilience and provides insights on the most efficient key gate placement strategy that maximizes the achievable security.

Metrics

19 Record Views

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Web of Science research areas
Engineering, Electrical & Electronic
Logo image