Circuito de detección que es similar en funcionalidad e implementación

Sea un vector de variables booleanas. Sea dos circuitos booleanos en . Digamos que es similar a si:$x=(x_1,\dots,x_n)$$C,D$$x$$C$$D$

1. $\Pr[C(x) \ne D(x)]$ es exponencialmente pequeño, cuando $x$ se dibuja uniformemente al azar desde $\{0,1\}^n$ (en otras palabras, tienen una funcionalidad casi idéntica); y,

2. $C,D$ difieren en la distancia de edición del gráfico en una pequeña cantidad (su distancia de edición es mucho menor que el tamaño del circuito, por ejemplo, $O(1)$ o alguna pequeña constante), lo que significa que casi todas las puertas y cables de $C$ coinciden una puerta correspondiente y un cable en $D$ , con solo unas pocas puertas agregadas / eliminadas / modificadas.

Mi problema: me dan un circuito $C$ , y quiero saber si existe un circuito $D$ que sea similar a $C$ pero no idéntico a $C$ (es decir, donde existe $x$ tal que $C(x)\ne D(x)$ )

¿Alguien puede sugerir un algoritmo para resolver este problema?

Si ayuda, podemos restringir la atención a los circuitos $D$ que son más pequeños que el circuito C dado $C$(es decir, queremos saber si existe un circuito $D$ tal que $D$ es más pequeño que $C$ , $D$ es similar a $C$ y existe $x$ tal que $C(x)\ne D(x)$ ).

Si ayuda, también puede suponer que se nos dan casos de prueba bien conocidos $x^1,\dots,x^m,y^1,\dots,y^m$ modo que $C(x^i)=y^i$ para todo $i$ , y podemos restringir aún más la atención solo a los circuitos $D$ modo que $D(x^i)=y^i$ para todo $i$ .

Esto surge de una aplicación práctica, por lo que si no puede resolver este problema, no dude en resolver cualquier variante o caso especial interesante. Por ejemplo, siéntase libre de instanciar cualquiera de los parámetros o umbrales de la manera que le resulte conveniente. Puede suponer que los circuitos no son demasiado grandes (tamaño polinómico, o algo así). Siéntase libre de reemplazar la distancia de edición del gráfico por alguna otra medida de casi coincidencia de implementación. Además, en la práctica, los solucionadores de SAT a menudo son sorprendentemente efectivos en los circuitos estructurados que surgen en la práctica, por lo que probablemente esté bien invocar un solucionador de SAT como una subrutina / oráculo (al menos, si lo invoca en algo como una instancia de SAT derivada de un circuito como ).$C$

Alternativamente, al carecer de algoritmos, también me interesaría la pregunta de existencia: para un circuito "promedio" , ¿cuál es la probabilidad de que exista algo de que cumpla con todos los criterios? (Espero que esta probabilidad sea muy baja, pero no tengo idea si ese es el caso).$C$$D$

La aplicación práctica es probar si un circuito puede contener una puerta trasera maliciosa / huevo de Pascua oculto. La hipótesis de cómo podría insertarse algo así es así. Comenzamos con un circuito "dorado" , que calcula la funcionalidad deseada y no tiene una puerta trasera oculta. Entonces, el adversario hace un pequeño cambio en para introducir la puerta trasera oculta, la obtención de un circuito modificado . El propósito de la puerta trasera es cambiar la función calculada por de alguna manera. Si no es demasiado pequeño, el cambio puede detectarse plausiblemente mediante pruebas aleatorias, por lo que un adversario probablemente tratará de mantener$C$$D$$D$$C$$D$$\Pr[C(x) \ne D(x)]$$\Pr[C(x) \ne D(x)]$muy pequeña. Del mismo modo, si difiere de en demasiados lugares, esto podría notarse mediante una inspección aleatoria del circuito, por lo que un adversario probablemente tratará de minimizar el número de cambios. (Y, puede haber un conjunto de pruebas de pares que representan instancias de la funcionalidad deseada, por lo que sabemos que sea cual sea el circuito "dorado" , satisface para todo .) En última instancia, se nos da el circuito (pero no el circuito "dorado" ), y queremos saber si podría ser una versión modificada de alguna$C$$D$$x^i,y^i$$D$$D(x^i)=y^i$$i$$C$$D$$C$$D$, donde se realizó la modificación para introducir una puerta trasera oculta de este tipo.

Este es solo un comentario extenso que vino a mi mente inmediatamente después de leer la pregunta:

• supongamos que tiene una fórmula 3SAT con variables y deja que sea ​​el circuito correspondiente;$\phi$$n$$x_1,...,x_n$$C$

• construya un nuevo circuito , agregando variables , y suficientes puertas para AND las nuevas variables con la salida de la original ( );$C'$$m = n^k$$y_1, y_2, ...,y_{n^k}$$m$$C$$C' = \phi \land y_1 \land ... \land y_m$

• construya un nuevo circuito desde que simplemente fuerce su salida a 0 usando una compuerta AND y NOT ( )$D'$$C'$$D' = C' \land \neg C'$

Si no es satisfactoria, entonces y son equivalentes; de lo contrario, difieren cuando satisface la fórmula AND all , pero puede elegir suficientemente grande como para que la probabilidad de que muy pequeña.$\phi$$D'$$C'$$x_i$$y_i = 1$$m$$\bigwedge y_i = 1$

Entonces, si tiene un algoritmo eficiente para su problema, puede resolver de manera eficiente la instancia de 3SAT.