Circuit de détection similaire en termes de fonctionnalité et d'implémentation

Soit un vecteur de variables booléennes. Soit C , D deux circuits booléens sur x . Disons que C est similaire à D si:$x=(x_1,\dots,x_n)$$C,D$$x$$C$$D$

1. est exponentiellement petit, lorsque x est tiré uniformément au hasard à partir de { 0 , 1 } n (en d'autres termes, ils ont une fonctionnalité presque identique); et,$\Pr[C(x) \ne D(x)]$$x$$\{0,1\}^n$

2. diffèrent dans la distance d'édition du graphique d'une petite quantité (leur distance d'édition est beaucoup plus petite que la taille du circuit, disons O ( 1 ) ou une petite constante), ce qui signifie que presque toutes les portes et les fils de C correspondent une porte et un fil correspondant en D , avec seulement quelques portes ajoutées / supprimées / modifiées.$C,D$$O(1)$$C$$D$

Mon problème: on me donne un circuit , et je veux savoir s'il existe un circuit D similaire à C mais pas identique à C (ie, où il existe x tel que C ( x ) ≠ D ( x ) ) .$C$$D$$C$$C$$x$$C(x)\ne D(x)$

Quelqu'un peut-il suggérer un algorithme pour résoudre ce problème?

Si cela peut aider, nous pouvons limiter l'attention aux circuits qui sont plus petits que le circuit C donné (c'est-à-dire que nous voulons savoir s'il existe un circuit D tel que D est plus petit que C , D est similaire à C et il existe x tels que C ( x ) ≠ D ( x ) ).$D$$C$$D$$D$$C$$D$$C$$x$$C(x)\ne D(x)$

Si cela aide, vous pouvez en outre supposer que nous recevons des cas de test connus comme bons tels que C ( x i ) = y i pour tout i , et nous pouvons restreindre davantage attention aux seuls circuits D tels que D ( x i ) = y i pour tout i .$x^1,\dots,x^m,y^1,\dots,y^m$$C(x^i)=y^i$$i$$D$$D(x^i)=y^i$$i$

Cela découle d'une application pratique, donc si vous ne pouvez pas résoudre ce problème, n'hésitez pas à résoudre toute variante ou cas spécial intéressant. Par exemple, n'hésitez pas à instancier l'un des paramètres ou seuils de la manière qui vous convient. Vous pouvez supposer que les circuits ne sont pas trop grands (taille polynomiale, ou quelque chose). N'hésitez pas à remplacer la distance d'édition du graphique par une autre mesure de quasi-correspondance d'implémentation. En outre, dans la pratique, les solveurs SAT sont souvent étonnamment efficaces sur les circuits structurés qui surviennent dans la pratique, il est donc probablement bien d'invoquer un solveur SAT en tant que sous-programme / oracle (au moins, si vous l'invoquez sur quelque chose comme une instance SAT dérivée à partir d'un circuit comme ).$C$

Alternativement, faute d'algorithmes, je serais également intéressé par la question de l'existence: pour un circuit "moyen" , quelle est la probabilité qu'il existe un D qui réponde à tous les critères? (J'espère que cette probabilité est très faible, mais je n'ai aucune idée si c'est le cas.)$C$$D$

L'application pratique consiste à tester si un circuit peut contenir une porte dérobée malveillante / un œuf de Pâques caché. L'hypothèse de la façon dont une telle chose pourrait être insérée se présente comme suit. Nous commençons avec un circuit "doré" D , qui calcule la fonctionnalité souhaitée et n'a pas de porte dérobée cachée. Ensuite, l'adversaire fait un petit changement à D pour introduire la porte dérobée cachée, l' obtention d' un circuit modifié C . Le but de la porte dérobée est de changer la fonction calculée par D d'une certaine manière. Si Pr [ C ( x ) ≠ D ( x ) $C$$D$$D$$C$$D$$\Pr[C(x) \ne D(x)]$n'est pas trop petit, le changement peut vraisemblablement être détecté par des tests aléatoires, donc un adversaire tentera probablement de garder très petit. De même, si C diffère de D à trop d'endroits, cela peut être remarqué par une inspection aléatoire du circuit, donc un adversaire tentera probablement de minimiser le nombre de changements. (Et, il peut y avoir une suite de tests de paires x i , y i qui représentent des instances de la fonctionnalité souhaitée, donc nous savons que quel que soit le circuit "doré" D , il satisfait D $\Pr[C(x) \ne D(x)]$$C$$D$$x^i,y^i$$D$ pour tout i .) Finalement, on nous donne le circuit C (mais pas le circuit "doré" D ), et nous voulons savoir si C pourrait être une version modifiée de certains D , où la modification a été fait pour introduire une porte dérobée cachée de ce type.$D(x^i)=y^i$$i$$C$$D$$C$$D$

Ce n'est qu'un commentaire prolongé qui m'est venu à l'esprit immédiatement après avoir lu la question:

• $\phi$$n$$x_1,...,x_n$$C$

• $C'$$m = n^k$$y_1, y_2, ...,y_{n^k}$$m$$C$$C' = \phi \land y_1 \land ... \land y_m$

• $D'$$C'$$D' = C' \land \neg C'$

$\phi$$D'$$C'$$x_i$$y_i = 1$$m$$\bigwedge y_i = 1$

Donc, si vous avez un algorithme efficace pour votre problème, vous pouvez résoudre facilement l'instance 3SAT.