Wykrywanie obwodu o podobnej funkcjonalności i implementacji

Niech będzie wektorem zmiennych boolowskich. Niech będą dwoma obwodami logicznymi na . Powiedz, że jest podobny do jeśli: $x=(x_1,\dots,x_n)$ $C,D$ $x$ $C$ $D$

jest wykładniczo mały, gdy jest losowo narysowany równomiernie z (innymi słowy, mają prawie identyczną funkcjonalność); i, $\Pr[C(x) \ne D(x)]$ $x$ $\{0,1\}^n$
różnią się nieznacznie odległością edycji wykresu (ich odległość edycji jest znacznie mniejsza niż rozmiar obwodu, powiedzmy lub jakaś niewielka stała), co oznacza, że prawie wszystkie bramki i przewody w pasują do siebie odpowiednią bramę i drut w , z kilkoma bramkami dodanymi / usuniętymi / zmienionymi. $C,D$ $O(1)$ $C$ $D$

Mój problem: otrzymałem obwód i chcę wiedzieć, czy istnieje obwód który jest podobny do ale nie identyczny z (tj. Gdzie istnieje taki, że ) . $C$ $D$ $C$ $C$ $x$ $C(x)\ne D(x)$

Czy ktoś może zasugerować algorytm rozwiązania tego problemu?

Jeśli to pomoże, możemy ograniczyć uwagę do obwodów które są mniejsze niż dany obwód (tzn. Chcemy wiedzieć, czy istnieje obwód taki, że jest mniejszy niż , jest podobny do i istnieje takie, że ). $D$ $C$ $D$ $D$ $C$ $D$ $C$ $x$ $C(x)\ne D(x)$

Jeśli to pomoże, możesz dodatkowo założyć, że otrzymaliśmy znane dobre przypadki testowe takie, że dla wszystkich , i możemy dodatkowo ograniczyć uwaga tylko na obwody takie, że dla wszystkich . $x^1,\dots,x^m,y^1,\dots,y^m$ $C(x^i)=y^i$ $i$ $D$ $D(x^i)=y^i$ $i$

Wynika to z praktycznego zastosowania, więc jeśli nie możesz rozwiązać tego problemu, możesz rozwiązać dowolny wariant lub interesujący specjalny przypadek. Na przykład możesz dowolnie tworzyć dowolne parametry lub progi w dogodny dla siebie sposób. Możesz założyć, że obwody nie są zbyt duże (wielomianowe lub coś w tym rodzaju). Możesz zastąpić odległość edycji wykresu inną miarą zbliżonego dopasowania. Ponadto w praktyce solwery SAT są często zaskakująco skuteczne w obwodach strukturalnych, które powstają w praktyce, więc prawdopodobnie dobrze jest wywołać solver SAT jako podprogram / wyrocznię (przynajmniej, jeśli wywołuje się go na czymś w rodzaju pochodnej instancji SAT z obwodu takiego jak ). $C$

Alternatywnie, bez żadnych algorytmów, byłbym również zainteresowany pytaniem o istnienie: w przypadku „przeciętnego” obwodu , jakie jest prawdopodobieństwo, że istnieje jakieś które spełnia wszystkie kryteria? (Mam nadzieję, że prawdopodobieństwo to jest bardzo niskie, ale nie mam pojęcia, czy tak jest w tym przypadku). $C$ $D$

Praktycznym zastosowaniem jest sprawdzenie, czy obwód może zawierać złośliwe tylne drzwi / ukryte jajko wielkanocne. Hipoteza, jak coś takiego może zostać wstawione, wygląda następująco. Zaczynamy od „złotego” obwodu , który oblicza pożądaną funkcjonalność i nie ma ukrytego tylnego wejścia. Następnie przeciwnik robi małe zmiany wprowadzenie ukryty furtkę, uzyskując zmodyfikowany obwód . Celem backdoora jest zmiana funkcji obliczonego przez w jakiś sposób. Jeśli $C$ $D$ $D$ $C$ $D$ $\Pr[C(x) \ne D(x)]$ nie jest zbyt mały, zmiana może być prawdopodobnie wykryta przez losowe testy, więc przeciwnik prawdopodobnie będzie próbował utrzymać bardzo małym poziomie. Podobnie, jeśli różni się od w zbyt wielu miejscach, można to zauważyć przez losową kontrolę obwodu, więc przeciwnik prawdopodobnie spróbuje zminimalizować liczbę zmian. (I nie może być zestaw testów z par, które reprezentują wystąpienia pożądanej funkcjonalności, więc wiemy, że bez względu na „złoty” Obieg jest, że spełnia $\Pr[C(x) \ne D(x)]$ $C$ $D$ $x^i,y^i$ $D$ dla wszystkich .) Ostatecznie otrzymujemy obwód (ale nie „złoty” obwód ) i chcemy wiedzieć, czy może być zmodyfikowaną wersją jakiegoś , gdzie modyfikacja była wprowadzone w celu wprowadzenia tego rodzaju ukrytego backdoora. $D(x^i)=y^i$ $i$ $C$ $D$ $C$ $D$

sat application-of-theory

— DW
źródło

Ile bitów stanowi wejście do obwodu? Jeśli jest to wystarczająco małe, sensowne może być przeprowadzenie wyczerpujących testów.

— András Salamon,

n

$n$

2^{n}

$2^n$

zastosowali algorytmy genetyczne, aby empirycznie zaatakować coś takiego. w tym przypadku wydaje się, że algorytm, który podajesz, testowanie losowe, jest czymś, co można wypróbować. wydaje się również, że wcale nie opisałeś, czym jest „backdoor” w obwodzie (wydaje się, że ma to jakieś nieokreślone powiązanie z kryptografią), ale dziękuję za dostarczenie jakiejś próby motywacji ... natychmiastowe pytanie wydaje się, jak przeciwnik wstawić jakiś backdoor, unikając wykrycia przez losowe testy? ale ogólny scenariusz wydaje się nie w pełni zdefiniowany.

— vzn

D (x)

$D(x)$

n

$n$

C

$C$

C

$C$

C

$C$

D

$D$

1 / 2^{100}

$1/2^{100}$

— DW

f (x)

$f(x)$

g (x)

$g(x)$

To tylko rozszerzony komentarz, który przyszedł mi do głowy natychmiast po przeczytaniu pytania:

$\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$

Jeśli więc masz skuteczny algorytm dla swojego problemu, możesz skutecznie rozwiązać instancję 3SAT.

— Marzio De Biasi
źródło