Seja um vetor de variáveis booleanas. Sejam dois circuitos booleanos em . Diga que é semelhante a se:
{ 0 , 1 } n
diferem na distância de edição do gráfico em uma quantidade minúscula (a distância de edição é muito menor que o tamanho do circuito, digamos, ou alguma pequena constante), significando que quase todos os portões e fios de correspondem um portão e um fio correspondentes em , com apenas alguns portões adicionados / excluídos / alterados.
Meu problema: recebo um circuito e quero saber se existe um circuito semelhante a mas não idêntico a (ou seja, onde existe tal que )
Alguém pode sugerir um algoritmo para resolver esse problema?
Se ajudar, podemos restringir a atenção aos circuitos que são menores que o circuito C fornecido (ou seja, queremos saber se existe um circuito tal que seja menor que , é semelhante a e existe tal que ).
Se ajudar, você também pode supor que recebemos casos de teste em bom estado modo que para all , e podemos restringir ainda mais a atenção apenas aos circuitos modo que para todos os .
Isso decorre de uma aplicação prática; portanto, se você não conseguir resolver esse problema, sinta-se à vontade para resolver qualquer variante ou caso especial interessante. Por exemplo, fique à vontade para instanciar qualquer um dos parâmetros ou limites da maneira que for mais conveniente para você. Você pode assumir que os circuitos não são muito grandes (tamanho polinomial ou algo assim). Sinta-se à vontade para substituir a distância de edição do gráfico por alguma outra medida de implementação próxima. Além disso, na prática, os solucionadores de SAT são surpreendentemente eficazes nos circuitos estruturados que surgem na prática; portanto, provavelmente é bom invocar um solucionador de SAT como uma sub-rotina / oráculo (pelo menos, se você o estiver chamando em algo como uma instância de SAT derivada de um circuito como ).
Como alternativa, na falta de algoritmos, eu também estaria interessado na questão da existência: para um circuito "médio" , qual é a probabilidade de existir algum que atenda a todos os critérios? (Espero que essa probabilidade seja muito baixa, mas não faço ideia se é esse o caso.)D
A aplicação prática é testar se um circuito pode conter um backdoor malicioso / ovo de Páscoa escondido. A hipótese de como uma coisa dessas pode ser inserida é assim. Começamos com um circuito "dourado" , que calcula a funcionalidade desejada e não possui backdoor oculto. Em seguida, o adversário faz uma pequena alteração em para introduzir a porta traseira oculta, obtendo um circuito modificado . O objetivo do backdoor é alterar a função calculada por de alguma maneira. Se não for muito pequeno, a alteração poderá ser detectada plausivelmente por testes aleatórios, portanto, um adversário provavelmente tentará manterD D C D Pr [ C ( x ) ≠ D ( x ) ] Pr [ C ( x ) ≠ D ( x ) ] C D x i , y i D D ( x i ) = y i i C D C Dmuito pequeno. Da mesma forma, se difere de em muitos lugares, isso pode ser percebido pela inspeção aleatória do circuito, de modo que um adversário provavelmente tentará minimizar o número de alterações. (E, pode haver um conjunto de testes de pares que representam instâncias da funcionalidade desejada, portanto sabemos que, seja qual for o circuito "dourado" , ele satisfaz para todos .) Por fim, recebemos o circuito (mas não o circuito "dourado" ) e queremos saber se pode ser uma versão modificada de algum, onde a modificação foi feita para introduzir um backdoor oculto desse tipo.
Respostas:
Este é apenas um comentário extenso que me veio à mente imediatamente após ler a pergunta:
suponha que você tenha uma fórmula 3SAT com variáveis e deixe ser o circuito correspondente;n x 1 , . . . , x n Cϕ n x1,...,xn C
construa um novo circuito , adicionando variáveis e portas suficientes para AND as novas variáveis com a saída do original ( ); m = n k y 1 , Y 2 , . . . , y n k m C C ′ = ϕ ∧ y 1 ∧ . . . ∧ y mC′ m=nk y1,y2,...,ynk m C C′=ϕ∧y1∧...∧ym
construa um novo circuito de que simplesmente force sua saída para 0 usando um gate AND e NOT ( )C ' D ' = C ' ∧ ¬ C 'D′ C′ D′=C′∧¬C′
Se não é satisfatório, e são equivalentes; caso contrário, diferem quando o satisfaz a fórmula AND todo , mas você pode escolher grande o suficiente para tornar a probabilidade de que muito pequena.D ' C ' x i y i = 1 m ⋀ y i = 1ϕ D′ C′ xi yi=1 m ⋀yi=1
Portanto, se você tiver um algoritmo eficiente para o seu problema, poderá resolver com eficiência a instância 3SAT.
fonte