  In this paper, we propose a canonical prune-and-SAT (CP&SAT) attack for
breaking state-of-the-art routing-based obfuscation techniques. In the CP&SAT
attack, we first encode the key-programmable routing blocks (keyRBs) based on
an efficient SAT encoding mechanism suited for detailed routing constraints,
and then efficiently re-encode and reduce the CNF corresponded to the keyRB
using a bounded variable addition (BVA) algorithm. In the CP&SAT attack, this
is done before subjecting the circuit to the SAT attack. We illustrate that
this encoding and BVA-based pre-processing significantly reduces the size of
the CNF corresponded to the routing-based obfuscated circuit, in the result of
which we observe 100% success rate for breaking prior art routing-based
obfuscation techniques. Further, we propose a new intercorrelated logic and
routing locking technique, or in short InterLock, as a countermeasure to
mitigate the CP&SAT attack. In Interlock, in addition to hiding the
connectivity, a part of the logic (gates) in the selected timing paths are also
implemented in the keyRB(s). We illustrate that when the logic gates are
twisted with keyRBs, the BVA could not provide any advantage as a
pre-processing step. Our experimental results show that, by using InterLock,
with only three 8$\times$8 or only two 16x16 keyRBs (twisted with actual logic
gates), the resilience against existing attacks as well as our new proposed
CP&SAT attack would be guaranteed while, on average, the delay/area overhead is
less than 10% for even medium-size benchmark circuits.
