<p>This is only an extended comment that came to my mind immediately after reading the question:</p>

<ul>
<li><p>suppose you have a 3SAT formula $\phi$ with $n$ variables $x_1,...,x_n$ and let $C$ be the corresponding circuit;</p></li>
<li><p>build a new circuit $C'$, adding $m = n^k$ variables $y_1, y_2, ...,y_{n^k}$, and enough gates to AND the $m$ new variables with the output of the original $C$ ($C' = \phi \land y_1 \land ... \land y_m$);</p></li>
<li><p>build a new circuit $D'$ from $C'$ that simply forces its output to 0 using an AND and NOT gate ($D' = C' \land \neg C'$)</p></li>
</ul>

<p>If $\phi$ is not satisfiable then $D'$ and $C'$ are equivalent, otherwise they differ when the $x_i$ satisfy the formula AND all $y_i = 1$, but you can choose $m$ large enough to make the probability that $\bigwedge y_i =  1$ very small.</p>

<p>So if you have an efficient algorithm for your problem, you can afficiently solve the 3SAT instance.</p>

CC BY-SA 3.0
2013-10-05T12:10:32.607Z
2013-10-05T12:10:32.607Z
Marzio De Biasi
<p>Let $x=(x_1,\dots,x_n)$ be a vector of boolean variables.  Let $C,D$ be two boolean circuits on $x$.  Say that $C$ is similar to $D$ if:</p>

<ol>
<li><p>$\Pr[C(x) \ne D(x)]$ is exponentially small, when $x$ is drawn uniformly at random from $\{0,1\}^n$ (in other words, they have almost-identical functionality); and,</p></li>
<li><p>$C,D$ differ in graph edit distance by a tiny amount (their edit distance is much smaller than the size of the circuit, say, $O(1)$ or some small constant), meaning that almost all of the gates and wires of $C$ match a corresponding gate and wire in $D$, with only a few gates added/deleted/changed.</p></li>
</ol>

<hr>

<p>My problem: I am given a circuit $C$, and I want to know whether there exists a circuit $D$ that is similar to $C$ but not identical to $C$ (i.e., where there exists $x$ such that $C(x)\ne D(x)$).</p>

<p>Can anyone suggest an algorithm to solve this problem?</p>

<p>If it helps, we can restrict attention to circuits $D$ that are smaller than the given circuit $C$ (i.e., we want to know whether there exists a circuit $D$ such that $D$ is smaller than $C$, $D$ is similar to $C$, and there exists $x$ such that $C(x)\ne D(x)$).</p>

<p>If it helps, you can additionally assume we are given known-good test cases $x^1,\dots,x^m,y^1,\dots,y^m$ such that $C(x^i)=y^i$ for all $i$, and we can further restrict attention to only circuits $D$ such that $D(x^i)=y^i$ for all $i$.</p>

<hr>

<p>This arises from a practical application, so if you can't solve this problem, feel free to solve any variant or interesting special case.  For instance, feel free to instantiate any of the parameters or thresholds in any way that's convenient for you.  You can assume the circuits are not too large (polynomial sized, or something).  Feel free to replace graph edit distance by some other measure of near-match of implementation.  Also, in practice SAT solvers are often surprisingly effective on the structured circuits that arise in practice, so it's probably fine to invoke a SAT solver as a subroutine/oracle (at least, if you're invoking it on something like a SAT instance derived from a circuit like $C$).</p>

<p>Alternatively, lacking any algorithms, I would also be interested in the existence question: for an "average" circuit $C$, what's the probability that there exists some $D$ that meets all the criteria?  (I'm hoping this probability is very low, but I have no clue if that is the case.)</p>

<hr>

<p>The practical application is to test whether a circuit $C$ might contain a malicious backdoor / hidden Easter egg.  The hypothesis of how such a thing might get inserted goes like this.  We start with a "golden" circuit $D$, that computes the desired functionality and has no hidden backdoor.  Then, the adversary makes a small change to $D$ to introduce the hidden backdoor, obtaining a modified circuit $C$.  The purpose of the backdoor is to change the function computed by $D$ in some way.  If $\Pr[C(x) \ne D(x)]$ is not too small, the change can plausibly be detected by random testing, so an adversary will probably try to keep $\Pr[C(x) \ne D(x)]$ very small.  Similarly, if $C$ differs from $D$ in too many places, this might be noticed by random inspection of the circuit, so an adversary will probably try to minimize the number of changes.  (And, there may be a test suite of $x^i,y^i$ pairs that represent instances of the desired functionality, so we know that whatever the "golden" circuit $D$ is, it satisfies $D(x^i)=y^i$ for all $i$.)  Ultimately, we are given the circuit $C$ (but not the "golden" circuit $D$), and we want to know whether $C$ might be a modified version of some $D$, where the modification was made to introduce a hidden backdoor of this sort.</p>

CC BY-SA 3.0
2013-10-04T19:14:23.200Z
How many bits form the input to the circuit?  If this is sufficiently small then it might make sense to do exhaustive testing.
András Salamon
CC BY-SA 3.0
2013-10-04T20:15:47.400Z
@AndrásSalamon: Sadly, the number $n$ of inputs to the circuit is large enough in practice (in the applications that I have in mind) that exhaustive testing over all $2^n$ possible inputs is infeasible.  I appreciate the thought, though!
D.W.
CC BY-SA 3.0
2013-10-04T22:33:33.297Z
have used genetic algorithms to attack something like this problem empirically. in this case it appears the algorithm you state, random testing, is something to try. also, seems you didnt describe at all what a "backdoor" in the circuit is (this seems to have some unstated connection to cryptography), but thx for providing some attempt at motivation... an immediate question seems to be how could an adversary insert some backdoor while evading detection by random testing? but the overall scenario seems not fully defined.
vzn
CC BY-SA 3.0
2013-10-05T01:19:41.213Z
@vzn, The golden circuit $D(x)$ describes the intended functionality of the device. Suppose 100 of the $n$ input bits can be chosen/influenced by the attacker. We're worried there's a hidden backdoor in $C$ that works like this: if the attacker supplies a magic 100-bit value on his inputs, then the backdoored circuit $C$ computes the wrong output (with tragic effect), but otherwise $C$ behaves exactly like $D$. This'd allow the attacker to trigger a tragedy at a time of his choosing, but it's hard to detect with random testing (since only $1/2^{100}$ of the inputs trigger tragedy).
D.W.
CC BY-SA 3.0
2013-10-05T19:38:52.223Z
the question seems like it might have some relation to the SAT "backbone". also see this question on [cnf vs dnf conversion/errors](http://cstheory.stackexchange.com/questions/17239/k-cnf-k-dnf-conversion-to-minimize-errors) which might be a natural/formal way to quantify "similarity" which you dont formally quantify. is it true the attacker can only "flip" the "golden" result of true or false by adding gates? ie it sounds like a $f(x)$-xor-$g(x)$-like problem.
vzn
<sat><application-of-theory>
Detecting circuit that's similar in functionality and implementation
D.W.
# Detecting circuit that's similar in functionality and implementation

(Asked by: username_0 on 2013-10-04)

Let $x=(x\_1,\dots,x\_n)$ be a vector of boolean variables. Let $C,D$ be two boolean circuits on $x$. Say that $C$ is similar to $D$ if:

1. $\Pr[C(x) \ne D(x)]$ is exponentially small, when $x$ is drawn uniformly at random from $\{0,1\}^n$ (in other words, they have almost-identical functionality); and,
2. $C,D$ differ in graph edit distance by a tiny amount (their edit distance is much smaller than the size of the circuit, say, $O(1)$ or some small constant), meaning that almost all of the gates and wires of $C$ match a corresponding gate and wire in $D$, with only a few gates added/deleted/changed.

---

My problem: I am given a circuit $C$, and I want to know whether there exists a circuit $D$ that is similar to $C$ but not identical to $C$ (i.e., where there exists $x$ such that $C(x)\ne D(x)$).

Can anyone suggest an algorithm to solve this problem?

If it helps, we can restrict attention to circuits $D$ that are smaller than the given circuit $C$ (i.e., we want to know whether there exists a circuit $D$ such that $D$ is smaller than $C$, $D$ is similar to $C$, and there exists $x$ such that $C(x)\ne D(x)$).

If it helps, you can additionally assume we are given known-good test cases $x^1,\dots,x^m,y^1,\dots,y^m$ such that $C(x^i)=y^i$ for all $i$, and we can further restrict attention to only circuits $D$ such that $D(x^i)=y^i$ for all $i$.

---

This arises from a practical application, so if you can't solve this problem, feel free to solve any variant or interesting special case. For instance, feel free to instantiate any of the parameters or thresholds in any way that's convenient for you. You can assume the circuits are not too large (polynomial sized, or something). Feel free to replace graph edit distance by some other measure of near-match of implementation. Also, in practice SAT solvers are often surprisingly effective on the structured circuits that arise in practice, so it's probably fine to invoke a SAT solver as a subroutine/oracle (at least, if you're invoking it on something like a SAT instance derived from a circuit like $C$).

Alternatively, lacking any algorithms, I would also be interested in the existence question: for an "average" circuit $C$, what's the probability that there exists some $D$ that meets all the criteria? (I'm hoping this probability is very low, but I have no clue if that is the case.)

---

The practical application is to test whether a circuit $C$ might contain a malicious backdoor / hidden Easter egg. The hypothesis of how such a thing might get inserted goes like this. We start with a "golden" circuit $D$, that computes the desired functionality and has no hidden backdoor. Then, the adversary makes a small change to $D$ to introduce the hidden backdoor, obtaining a modified circuit $C$. The purpose of the backdoor is to change the function computed by $D$ in some way. If $\Pr[C(x) \ne D(x)]$ is not too small, the change can plausibly be detected by random testing, so an adversary will probably try to keep $\Pr[C(x) \ne D(x)]$ very small. Similarly, if $C$ differs from $D$ in too many places, this might be noticed by random inspection of the circuit, so an adversary will probably try to minimize the number of changes. (And, there may be a test suite of $x^i,y^i$ pairs that represent instances of the desired functionality, so we know that whatever the "golden" circuit $D$ is, it satisfies $D(x^i)=y^i$ for all $i$.) Ultimately, we are given the circuit $C$ (but not the "golden" circuit $D$), and we want to know whether $C$ might be a modified version of some $D$, where the modification was made to introduce a hidden backdoor of this sort.

**Tags:** sat, application-of-theory

> **Comments:**
> **username_1**: How many bits form the input to the circuit?  If this is sufficiently small then it might make sense to do exhaustive testing.  
> **username_0**: @AndrásSalamon: Sadly, the number $n$ of inputs to the circuit is large enough in practice (in the applications that I have in mind) that exhaustive testing over all $2^n$ possible inputs is infeasible.  I appreciate the thought, though!  
> **username_2**: have used genetic algorithms to attack something like this problem empirically. in this case it appears the algorithm you state, random testing, is something to try. also, seems you didnt describe at all what a "backdoor" in the circuit is (this seems to have some unstated connection to cryptography), but thx for providing some attempt at motivation... an immediate question seems to be how could an adversary insert some backdoor while evading detection by random testing? but the overall scenario seems not fully defined.  
> **username_0**: @username_2, The golden circuit $D(x)$ describes the intended functionality of the device. Suppose 100 of the $n$ input bits can be chosen/influenced by the attacker. We're worried there's a hidden backdoor in $C$ that works like this: if the attacker supplies a magic 100-bit value on his inputs, then the backdoored circuit $C$ computes the wrong output (with tragic effect), but otherwise $C$ behaves exactly like $D$. This'd allow the attacker to trigger a tragedy at a time of his choosing, but it's hard to detect with random testing (since only $1/2^{100}$ of the inputs trigger tragedy).  
> **username_2**: the question seems like it might have some relation to the SAT "backbone". also see this question on [cnf vs dnf conversion/errors](http://cstheory.stackexchange.com/questions/17239/k-cnf-k-dnf-conversion-to-minimize-errors) which might be a natural/formal way to quantify "similarity" which you dont formally quantify. is it true the attacker can only "flip" the "golden" result of true or false by adding gates? ie it sounds like a $f(x)$-xor-$g(x)$-like problem.  

---

## 1 answers

### Answer by username_3 on 2013-10-05. Score: 4

This is only an extended comment that came to my mind immediately after reading the question:

* suppose you have a 3SAT formula $\phi$ with $n$ variables $x\_1,...,x\_n$ and let $C$ be the corresponding circuit;
* build a new circuit $C'$, adding $m = n^k$ variables $y\_1, y\_2, ...,y\_{n^k}$, and enough gates to AND the $m$ new variables with the output of the original $C$ ($C' = \phi \land y\_1 \land ... \land y\_m$);
* build a new circuit $D'$ from $C'$ that simply forces its output to 0 using an AND and NOT gate ($D' = C' \land \neg C'$)

If $\phi$ is not satisfiable then $D'$ and $C'$ are equivalent, otherwise they differ when the $x\_i$ satisfy the formula AND all $y\_i = 1$, but you can choose $m$ large enough to make the probability that $\bigwedge y\_i = 1$ very small.

So if you have an efficient algorithm for your problem, you can afficiently solve the 3SAT instance.


---

