Quais são as diferenças entre a execução simbólica e solucionadores SAT?

Question

O meu entendimento é de que a execução simbólica lida apenas com caminhos específicos e maus padrões, enquanto solucionadores SAT, ou satisfiability módulo teorias em geral, se dão muito mais robusta análise do programa.

Alguém poderia validar a declaração acima e (brevemente) explicar as diferenças entre estes dois verificação formal metodologias?

Answer 1

TL;DR: Eles diferem em seus básico de entrada e de saída.SENTOU-se e SMT solucionadores de não saber quais são os programas;eles são ferramentas que responder sim ou não a perguntas sobre fórmulas matemáticas.Execução simbólica, por outro lado, é um método de análise de programas.Execução simbólica depende, normalmente, SENTOU-se e SMT solucionadores de problemas, mas não a outra maneira ao redor.

---

SENTOU-se e solucionadores de SMT diretamente não tem nada a ver com os programas.Em vez disso, SENTOU-se ou SMT solver toma como entrada uma matematicamente descrito "fórmula", e as respostas, a grosso modo, se é verdadeira ou falsa.(Muitas vezes, uma terceira opção é permitido, desconhecido, para os casos em que o solver é incapaz de descobrir uma resposta.)

Por exemplo, uma possível entrada do SAT solver é (a and not b) or (not a and c).Que é, é uma fórmula matemática, onde a, b, e c aqui estão Booleano (0 ou 1) constantes.O SAT, o solver é suposto para decidir se é possível que a fórmula seja verdadeira, escolhendo valores de a, b, e c.SMT solucionadores de problemas são semelhantes, mas a, b, e c poderia ser substituído por fórmulas mais complexas com números inteiros, strings, funções, etc., por exemplo x + 3 = y^2.

---

Execução simbólica é uma maneira elegante de execução de um programa, mas não como o programa foi concebido para ser executado.Em vez disso, o programa é executado usando o chamado "simbólico" valores", que são como marcadores de posição.Para um exemplo do que isso significa, suponha que eu tenha uma função como f(x) = if x > 0 then 1 else 0.Agora, normalmente, eu iria executar o programa pela inserção de, digamos, 3, e chegar f(3) = 1, já que 3 é maior do que 0.Com execução simbólica, o que eu executar o programa pela inserção de uma variável de espaço reservado, input, e eu avaliar o programa para se dois casos:ou input > 0 and answer = 1 ou input <= 0 and answer = 0.Isso pode parecer inútil, mas acaba por ser uma forma poderosa de análise de programas.

---

A conexão entre os dois é que a execução simbólica, muitas vezes, depende de SMT solucionadores de problemas durante a execução, para descobrir se um determinado caminho, na verdade, é possível, ou se deve ser descartado.Por exemplo, um SMT solver pode ser usado para determinar se input <= 0 and answer = 0 é possível (a resposta é sim, por exemplo se input = 0).Desta forma, SMT é um tipo de "força motriz" para trás o que faz simbólico de execução viável.