O que exatamente é a verificação de modelo simbólico?

8

Eu sei que a Verificação Simbólica de Modelo é uma travessia de espaço de estado com base em representações de conjuntos de estados e relações de transição como fórmulas, como em CTL, usando modelos como o Modelo Kripke. Eu conheço a teoria. Mas acho difícil entender a aplicação real. Onde exatamente é usado? O que exatamente ele faz e como funciona?

Alguém pode explicar com um exemplo real e relacionar a teoria à prática?

formal-methods model-checking software-verification Xpleria
fonte
1
Isso parece amplo para mim. O "o que isso faz?" parte pode ter um escopo razoável (ou não), mas "onde é usada?" é a) outra questão inteiramente eb) provavelmente muito ampla.
Raphael
Mas um exemplo pode ser tomado e explicado com base nisso. Isso não é muito amplo.
Xpleria 22/03
2
Por que você não está satisfeito com a descrição de Verificação de modelo simbólico no livro-texto padrão, por exemplo, "Princípios de verificação de modelo", de Christel Baier e Joost-Pieter Katoen? De quais partes você está confuso?
Hengxin
Eles falam sobre 'como deve ser feito', mas não 'como exatamente é feito'. Estou tentando relacionar a teoria e a implementação prática. Ainda sou novo nisso e preciso de um exemplo.
Xpleria
1
Você pode estar no site errado então. A ciência da computação trata dos conceitos ("como deve ser feito"); você terá que perguntar aos profissionais sobre a parte "como é feito".
Raphael

Respostas:

4

Verificação de modelo simbólico é a Verificação de modelo que funciona em estados simbólicos. Ou seja, eles codificam os estados em representações simbólicas, normalmente diagramas de decisão binária ordenados (OBDDs).

A questão é o que eles fazem e como eles funcionam.

Você primeiro tem seu código-fonte para algum aplicativo. Você transforma seu código-fonte em algum gráfico de transição de estado, como uma Estrutura Kripke. Os estados são preenchidos com proposições atômicas que descrevem o que é verdadeiro naquele estado em particular. Na verificação do modelo simbólico, as proposições atômicas são codificadas como OBDDs para economizar espaço e melhorar o desempenho.

O Verificador de Modelos é iniciado em algum estado inicial e explora os estados, procurando erros no gráfico de transição de estado. Se encontrar um erro, geralmente gerará um caso de teste demonstrando o erro. Ele usa os OBDDs simbólicos para navegar de maneira otimizada no espaço de estados. Gostaria de poder explicar mais lá, mas ainda aprendendo.

Mas é basicamente isso. Você tem um programa convertido em um modelo formal (gráfico de transição de estado) e, em seguida, utiliza otimizações simbólicas para navegar no espaço de estados em busca de erros (comparando-o com uma especificação LTL / CTL). E se um erro for encontrado, o Model Checker fornece algumas informações para ajudar a documentar e resolvê-lo.

Lance Pollard
fonte
5

A verificação de modelo simbólico pode ser muito útil para verificar a correção das comunicações e protocolos de segurança. Por exemplo:

  • Um modelo simbólico de uma implementação do OAUTH2 pode ajudar a verificar conseqüências não intencionais, onde um adversário obtém tokens de autenticação secretos ou dados circunstanciais relacionados que podem ajudá-los a violar o processo.
  • Um modelo simbólico de um protocolo criptográfico, como um handshake TLS, pode ajudar a verificar se o design criptográfico não tem conseqüências não intencionais.

Isso funciona escrevendo uma descrição simbólica de todas as funções primitivas e algoritmos de protocolo e, em seguida, tendo um verificador de modelo simbólico, como o ProVerif , percorre o espaço de estados e tenta detectar combinações de estados que produzem resultados desfavoráveis. No caso do ProVerif, modelos simbólicos são descritos usando o cálculo Pi aplicado como a linguagem de modelagem. Isso permite a descrição de protocolos em uma sintaxe funcional semelhante a ML.

Kaepora
fonte