Mendeteksi sirkuit yang memiliki fungsionalitas dan implementasi yang serupa

Misalkan menjadi vektor variabel boolean. Misalkan C , D menjadi dua sirkuit boolean pada x . Katakan bahwa C mirip dengan D jika:$x=(x_1,\dots,x_n)$$C,D$$x$$C$$D$

1. kecil secara eksponensial, ketika x ditarik secara acak secara acak dari { 0 , 1 } n (dengan kata lain, mereka memiliki fungsi yang hampir identik); dan,$\Pr[C(x) \ne D(x)]$$x$$\{0,1\}^n$

2. berbeda dalam jarak edit grafik dengan jumlah kecil (jarak edit mereka jauh lebih kecil dari ukuran sirkuit, katakanlah, O ( 1 ) atau konstanta kecil), yang berarti bahwa hampir semua gerbang dan kabelpertandingan C gerbang dan kabel yang sesuai di D , dengan hanya beberapa gerbang yang ditambahkan / dihapus / diubah.$C,D$$O(1)$$C$$D$

Masalah saya: Saya diberi sirkuit , dan saya ingin tahu apakah ada sirkuit D yang mirip dengan C tetapi tidak identik dengan C (yaitu, di mana ada x sedemikian rupa sehingga C ( x ) ≠ D ( x ) ) .$C$$D$$C$$C$$x$$C(x)\ne D(x)$

Adakah yang bisa menyarankan algoritma untuk mengatasi masalah ini?

Jika itu membantu, kita dapat membatasi perhatian pada sirkuit yang lebih kecil dari sirkuit C yang diberikan (yaitu, kita ingin tahu apakah ada sirkuit D sehingga D lebih kecil dari C , D mirip dengan C , dan ada x sedemikian rupa sehingga C ( x ) ≠ D ( x ) ).$D$$C$$D$$D$$C$$D$$C$$x$$C(x)\ne D(x)$

Jika itu membantu, Anda juga dapat mengasumsikan bahwa kami diberikan kasus uji yang dikenal baik sedemikian rupa sehingga C ( x i ) = y i untuk semua i , dan kami dapat lebih jauh membatasi hanya memperhatikan sirkuit D sehingga D ( x i ) = y i untuk semua i .$x^1,\dots,x^m,y^1,\dots,y^m$$C(x^i)=y^i$$i$$D$$D(x^i)=y^i$$i$

Ini muncul dari aplikasi praktis, jadi jika Anda tidak dapat menyelesaikan masalah ini, jangan ragu untuk menyelesaikan varian atau kasus khusus yang menarik. Misalnya, jangan ragu untuk instantiate parameter atau ambang batas dengan cara apa pun yang nyaman bagi Anda. Anda dapat mengasumsikan sirkuit tidak terlalu besar (ukuran polinom, atau sesuatu). Jangan ragu untuk mengganti jarak edit grafik dengan ukuran implementasi lain yang hampir cocok. Juga, dalam praktiknya, pemecah SAT sering mengejutkan efektif pada sirkuit terstruktur yang muncul dalam praktik, jadi mungkin baik untuk memanggil pemecah SAT sebagai subrutin / oracle (setidaknya, jika Anda memohonnya pada sesuatu seperti turunan SAT yang diturunkan dari rangkaian seperti ).$C$

Atau, kurang algoritma apapun, saya akan juga mungkin tertarik dalam pertanyaan keberadaan: untuk "rata-rata" sirkuit , apa probabilitas bahwa ada beberapa D yang memenuhi semua kriteria? (Saya berharap probabilitas ini sangat rendah, tetapi saya tidak tahu apakah itu masalahnya.)$C$$D$

Aplikasi praktisnya adalah untuk menguji apakah sirkuit mungkin mengandung backdoor berbahaya / telur Paskah tersembunyi. Hipotesa bagaimana hal semacam itu bisa dimasukkan berjalan seperti ini. Kita mulai dengan sirkuit "emas" D , yang menghitung fungsi yang diinginkan dan tidak memiliki pintu belakang tersembunyi. Kemudian, musuh membuat perubahan kecil ke D untuk memperkenalkan pintu belakang tersembunyi, memperoleh sirkuit C yang dimodifikasi . Tujuan dari backdoor adalah untuk mengubah fungsi yang dihitung oleh D dalam beberapa cara. Jika Pr [ C ( x ) ≠ D ( x ) $C$$D$$D$$C$$D$$\Pr[C(x) \ne D(x)]$tidak terlalu kecil, perubahan itu dapat dideteksi dengan pengujian acak, jadi musuh mungkin akan mencoba untuk menjaga sangat kecil. Demikian pula, jika C berbeda dari D di terlalu banyak tempat, ini mungkin diperhatikan dengan inspeksi acak dari rangkaian, sehingga musuh mungkin akan mencoba meminimalkan jumlah perubahan. (Dan, mungkin ada suite uji x i , y i pasangan yang mewakili contoh dari fungsionalitas yang diinginkan, jadi kita tahu bahwa apa pun sirkuit "emas" D , ia memenuhi D $\Pr[C(x) \ne D(x)]$$C$$D$$x^i,y^i$$D$ untuk semua i .) Pada akhirnya, kita diberikan sirkuit C (tetapi bukan sirkuit "emas" D ), dan kami ingin tahu apakah C mungkin merupakan versi modifikasi dari beberapa D , di mana modifikasi itu dibuat untuk memperkenalkan pintu belakang tersembunyi semacam ini.$D(x^i)=y^i$$i$$C$$D$$C$$D$

Ini hanya komentar panjang yang muncul di pikiran saya segera setelah membaca pertanyaan:

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

Jadi, jika Anda memiliki algoritma yang efisien untuk masalah Anda, Anda dapat menyelesaikan contoh 3SAT dengan efisien.