Faça métodos formais do programa de verificação têm um lugar na indústria?

Question

Eu peguei um vislumbre sobre Lógica De Hoare na faculdade.O que nós fizemos foi muito simples.A maior parte do que eu fazia, comprovando a exactidão de programas simples, consistindo de while loops, if declarações, e a sequência de instruções, mas nada mais.Estes métodos parecem ser muito úteis!

São métodos formais utilizados na indústria amplamente?

São estes métodos usados para provar a missão crítica de software?

Answer 1

Esta é uma questão perto do meu coração (eu sou um pesquisador em Software de Verificação usando a lógica formal), então você provavelmente não se surpreenda quando eu digo que eu acho que estas técnicas têm sua utilidade, e ainda não são utilizadas na indústria.

Existem muitos níveis de "métodos formais", então eu vou assumir que você quer dizer aqueles que descansam em um rigoroso base matemática (em oposição a, digamos, a seguir, cerca de 6-Sigma style processo).Alguns tipos de métodos formais têm tido grande sucesso - tipo de sistemas de ser um exemplo.Ferramentas de análise estática com base em dados de análise de fluxo também são populares, modelo de verificação é quase onipresente em design de hardware, e modelos computacionais como o Pi-Calculus e CCS parecem inspirar algumas mudanças nas práticas de linguagem de design para a concorrência.Rescisão de análise é que tinha um monte de imprensa recentemente - O SDV projeto da Microsoft e o trabalho por Byron Cozinhar são exemplos recentes de pesquisa/prática crossover em métodos formais.

Hoare Raciocínio não tem, até agora, fez grandes avanços na indústria - isto é por razões mais do que posso, mas eu suspeito que é principalmente em torno da complexidade da escrita, em seguida, provando especificações para programas reais (eles tendem a ficar grande, e não expressa as propriedades de muitos ambientes do mundo real).Vários sub-campos este tipo de raciocínio agora estão fazendo grandes avanços em problemas - Separação Lógica de ser um.

Isso é parcialmente a natureza do curso (disco rígido) de investigação.Mas devo confessar que nós, como teóricos, tem que inteiramente falhou para educar a indústria sobre o porquê de nossas técnicas são úteis, para mantê-los relevantes para as necessidades da indústria, e para torná-los acessíveis a desenvolvedores de software.Em algum nível, que não é o nosso problema - nós somos os pesquisadores, muitas vezes, matemáticos, e uso prático não é o mais importante em nossas mentes.Além disso, as técnicas sendo desenvolvidas geralmente são muito embrionárias para uso em grande escala de sistemas em pequenos programas, em sistemas simplificados, obter a matemática a trabalhar, e seguir em frente.Eu não muito comprar essas desculpas que devemos ser mais ativos em empurrar nossas idéias, e a obtenção de um ciclo de realimentação entre a indústria e o nosso trabalho (um dos principais motivos de eu voltei para a investigação).

É provavelmente uma boa idéia para me ressuscitar meu blog, e fazer mais alguns posts sobre essas coisas...

Answer 2

Bem, Senhor Tony Hoare juntou-se à Microsoft de Investigação há cerca de 10 anos, e uma das coisas que ele iniciou foi uma verificação formal de kernel do Windows NT.De fato, este foi um dos motivos para o atraso de tempo do Windows Vista:começando com Vista, grandes partes do kernel são na verdade, formalmente verificadas wrt.para certas propriedades, como a ausência de deadlocks, ausência de vazamentos de informações etc.

Certamente esse não é típico, mas é provavelmente o único e mais importante aplicação do programa formal de verificação, em termos de seu impacto (afinal, quase todo ser humano é, de alguma maneira, forma ou formulário afetado por um computador executando o Windows).

Answer 3

Eu não posso comentar muito sobre a missão-crítica de software, apesar de eu saber que o avionics indústria usa uma ampla variedade de técnicas para validar o software, incluindo Hoare estilo métodos.

Métodos formais têm sofrido porque os primeiros defensores como Edsger Dijkstra insistiu que ele deveria ser usado em todos os lugares.Nem o formalismos nem o suporte de software foram até o trabalho.Mais sensato que os defensores acreditam que esses métodos devem ser utilizados em problemas difíceis.Eles não são amplamente utilizados na indústria, mas a adoção é crescente.Provavelmente, os maiores avanços foram na utilização de métodos formais para a seleção propriedades de segurança de software.Alguns dos meus exemplos favoritos são o SPIN modelo verificador de e George Necula prova de transporte de código.

Afastar-se da prática e da investigação, da Microsoft Singularidade sistema operacional projeto é sobre a utilização de métodos formais para fornecer garantias de segurança, que normalmente exigem o suporte de hardware.Este, por sua vez, leva a um desempenho mais rápido e mais forte garantias.Por exemplo, na singularidade eles provaram que se um driver de dispositivo de terceiros é permitida em que o sistema (que os meios de verificação básica, condições foram provados), então ele não pode, possivelmente, levar para baixo que todo o SO–ele pior que pode fazer é a mangueira de seu próprio dispositivo.

Métodos formais, ainda não são amplamente utilizados na indústria, mas eles são mais utilizados do que eram há 20 anos, e de 20 anos a partir de agora, eles vão ser mais amplamente usado ainda.Então você está preparada para o futuro :-)

Answer 4

Sim, eles são usados, mas não são amplamente em todas as áreas.Existem métodos mais do que apenas a lógica de hoare, alguns são utilizados mais, outros menos, dependendo da aptidão para determinada tarefa.O problema comum é que o software é biiiiiiig e verificar se tudo está correto ainda é muito difícil um problema.

Por exemplo, o teorema-provador (um software que ajuda os seres humanos a demonstração de programa de correção) ACL2 tem sido usado para provar que um certo ponto flutuante, unidade de processamento não tenha um determinado tipo de erro.Era uma grande tarefa, para que esta técnica não é muito comum.

Modelo de verificação, um outro tipo de verificação formal, é utilizado, ao invés amplamente hoje em dia, por exemplo, a Microsoft fornece um tipo de modelo verificador de driver development kit e pode ser usado para verificar o controlador de um conjunto de erros comuns.Modelo de damas são também muitas vezes usado para verificar circuitos de hardware.

Testes rigorosos, pode ser também pensado como verificação formal - há algumas especificações formais de que os caminhos de programa deve ser testado e assim por diante.

Answer 5

"São métodos formais utilizados na indústria?"

Sim.

O assert instrução em muitas linguagens de programação, está relacionado a métodos formais para verificação de um programa.

"São métodos formais utilizados na indústria amplamente ?"

Não.

"São estes métodos usados para provar a missão crítica de software ?"

Às vezes.Mais frequentemente, eles são usados para provar que o software é seguro.Mais formalmente, eles são usados para provar certos de segurança relacionados com as afirmações sobre o software.

Answer 6

Existem duas abordagens diferentes para métodos formais na indústria.

Uma abordagem é alterar o processo de desenvolvimento completamente.A Z e notação a B método que foram mencionadas estão na primeira categoria.B foi aplicado para o desenvolvimento de driverless metrô (linha 14), em Paris (se você receber uma chance, subir na frente do vagão.Não é sempre que você receber uma chance para ver os trilhos em frente de você).

Outro, mais incremental, a abordagem é preservar o existente de desenvolvimento e processos de verificação e substituir apenas uma das tarefas de verificação de cada vez, um novo método.Isto é muito atraente, mas isso significa o desenvolvimento de ferramentas de análise estática para sair, as línguas que muitas vezes não são fáceis de analisar (porque eles não foram projetados para ser).Se você ir para (por exemplo)

http://dblp.uni-trier.de/db/indices/a-tree/d/Delmas:David.html

(desculpe, mas apenas um hiperlink permissão para novos utilizadores :( )

você vai encontrar instâncias de aplicações práticas de métodos formais para a verificação de programas em C (com analisadores estáticos Astrée, Ressalva, Fluctuat, Frama-C) e de um código binário (com ferramentas de AbsInt GmbH).

Pelo jeito, desde que você mencionou Lógica de Hoare, na lista acima de ferramentas, a única Ressalva é com base na lógica de Hoare (e Frama-C tem uma lógica de Hoare plug-in).Os outros dependem de resumo de interpretação, uma técnica diferente, com mais automático abordagem.

Answer 7

Minha área de especialização é o uso de métodos formais para análise estática de código para mostrar que o software esteja livre de erros de tempo de execução.Isto é implementado utilizando um métodos formais técnica conhecida como "abstrato interpretação".A técnica essencialmente permite que você para provar certos atributos de uma s/w do programa.E. g.prove que a+b não vai transbordar ou x/(x-y) não irá resultar em um erro de divisão por zero.Um exemplo de ferramenta de análise estática que utiliza esta técnica é Polyspace.

Com relação à sua pergunta: "São métodos formais utilizados na indústria amplamente?" e "São estes métodos usados para provar a missão crítica de software?"

A resposta é sim.Esta opinião é baseada na minha experiência e apoio a Polyspace ferramenta para indústrias que dependem da utilização do software embarcado para controle de segurança de sistemas críticos, tais como acelerador eletrônico no interior de um automóvel, sistema de frenagem de um trem, motor a jato controlador, a distribuição da droga, bomba de infusão, etc.Estas indústrias, de fato, usar estes tipos de métodos formais de ferramentas.

Eu não acredito que 100% desses segmentos da indústria estão usando essas ferramentas, mas o uso é crescente.A minha opinião é a de que as indústrias Aeroespacial e Automotiva levar com a indústria do Dispositivo Médico, rapidamente, aumentando a utilizar.

Answer 8

Polyspace é um (terrivelmente caro, mas muito bom) produto comercial com base na verificação do programa.É bastante pragmática, em que a escala de "reforço de teste de unidade que, provavelmente, irá encontrar alguns bugs' para 'os próximos três anos de sua vida vai ser gasto mostrando esses 10 arquivos que o zero defeitos'.

Baseia-se mais no negativo de verificação ('este programa não danificar o seu pilha') em vez positivo de verificação ('este programa vai fazer o que, precisamente, esses 50 páginas de equações dizer que vai').

Answer 9

Adicionar ao Jorg do responder, aqui está um entrevista com Tony Hoare.As ferramentas Jorg está a referir-se, penso eu, são PREfast e Prefixo.Ver aqui para obter mais informações.

Answer 10

Além de mais outras abordagens processuais, lógica de Hoare foi na base do Design por Contrato, introduzido como um objeto orientado técnica por Bertrand Meyer em Eiffel (ver Meyer artigo de 1992, página 4).Enquanto o Design por Contrato não é o mesmo que formal métodos de verificação (para uma coisa, a DbC não provar de nada até que o software é executado), na minha opinião, ele fornece uma forma mais prática de usar.