Como criar software de missão crítica?

15

Eu sou auto-aprendizagem de métodos formais. Ouvi dizer que métodos formais são usados ​​(e geralmente usados ​​apenas) para criar software de missão crítica (como controlador de reator nuclear, controlador de vôo de aeronave, controlador de sonda espacial). É por isso que estou interessado em aprender: p

No entanto, depois de aprender métodos formais (especialmente LTL, CTL e seus irmãos), sinto que eles só podem ser usados ​​para verificar a exatidão da especificação (segurança, vivacidade, justiça, etc.).

Mas então como verificar se o software (não apenas a especificação) está realmente correto?

Disclaimer: Eu sou um idiota de 90% quando se trata de ciência da computação teórica. Portanto, seja misericordioso ao responder.

fajrian
fonte
2
O que você quer dizer com "... que o software está realmente correto ..." ? Qual dos 2 seguintes você quer dizer: 1) O software é compatível com a especificação 2) Blocos específicos de código respeitam alguma propriedade específica ou alguma relação de entrada e saída.
Giorgio Camerani
@GiorgioCamerani: O primeiro um
fajrian
2
A correção de um programa geralmente significa que (1) é consistente com uma especificação e (2) nunca falha. O ponto (1) é realmente uma afirmação sobre o par (programa, especificação) e não sobre o programa em si. Uma complicação adicional é que 'programa' é normalmente uma abreviação de 'modelo de programa', porque os próprios programas são muito complicados ou não têm semântica precisa. Diante disso, acho que você está perguntando sobre a diferença entre um programa e seu modelo, mas não tenho muita certeza.
Radu GRIGore
@RaduGRIGore: Na verdade, eu não entendo o que é "modelo". Mas acho que você abordou minha pergunta de perto. Basicamente, o que eu quero saber é a diferença entre a especificação e o código-fonte do programa. Muitas coisas estúpidas podem acontecer quando programadores (como eu) estão implementando a especificação.
fajrian
1
@fajrian: Eu suspeito que você diga 'especificação' para o que eu chamaria de 'modelo'. Existem ferramentas que funcionam em programas escritos em linguagens como C ou Java ou mesmo código de máquina. (Ainda é um modelo, embora, como eles têm que assumir alguns semântica, que deveria , mas não pode, correspondem ao que o compilador / processador faz.)
Radu Grigore

Respostas:

11

A questão é bastante ampla. Para responder em um espaço razoável, farei muitas simplificações demais.

Vamos concordar com a terminologia. Um programa está correto quando implica sua especificação. Essa vaga declaração é precisa de várias maneiras, identificando exatamente o que é um programa e o que exatamente é uma especificação. Por exemplo, na verificação de modelo, o programa é uma estrutura Kripke e a especificação geralmente é uma fórmula LTL . Ou, o programa pode ser uma lista de instruções do PowerPC e a especificação pode ser um conjunto de asserções de Hoare-Floyd escritas em, digamos, lógica de primeira ordem. Existem muitas variações possíveis. É tentador concluir que em um caso (estrutura Kripke) não verificamos um programa real, enquanto no segundo caso (lista de instruções do PowerPC), verificamos. No entanto, é importante perceber que realmente estamos analisando modelos matemáticos nos dois casos, e isso está perfeitamente correto. (A situação é bastante semelhante à física, onde, por exemplo, a mecânica clássica é um modelo matemático da realidade.)

A maioria das formalizações distingue entre a sintaxe e a semântica de um programa; isto é, como é representado e o que isso significa. A semântica de um programa é o que conta do ponto de vista da verificação do programa. Mas, é claro que é importante ter uma maneira clara de atribuir significados a (representações sintáticas de) programas. Duas maneiras populares são as seguintes:

  • (pequena etapa) semântica operacional : é como definir uma linguagem de programação escrevendo um intérprete para ela. Para isso, você precisa dizer qual é o estado , e ele é afetado por cada afirmação no idioma. (Você pode se perguntar em qual idioma escreve o intérprete, mas vou fingir que não.)
  • semântica axiomática : aqui cada tipo de instrução vem com um esquema axiomático . Então, grosso modo, sempre que uma declaração específica desse tipo é usada, ela se traduz em poder usar certos axiomas. Por exemplo, a atribuição vem com o esquema { P [ x / e ] }x: =e ; a atribuição específica x : = x + 1 vem com o axioma { x + 1 = 1 }{P[x/e]}x: =e{P}x: =x+1 se instanciarmos o esquema com P = ( x = 1 ) .{x+1=1}x: =x+1{x=1}P=(x=1)

(Existem outros. Sinto-me particularmente mal por omitir a semântica denotacional, mas essa resposta já é longa.) O código da máquina e a semântica operacional estão bem próximos do que a maioria das pessoas chamaria de 'programa real'. Aqui está um documento seminal, que usa semântica operacional para um subconjunto do código de máquina DEC Alpha:

Por que você usaria alguma semântica de nível superior, como as axiomáticas? Quando você não deseja que sua prova de correção dependa do hardware no qual você executa. A abordagem, então, é provar a correção de um algoritmo com relação a algumas semânticas de alto nível convenientes e, em seguida, provar que a semântica soa com relação à semântica de nível inferior mais próxima das máquinas reais.

Em resumo, pude pensar em três razões que levaram à sua pergunta:

  1. Você viu apenas semânticas de alto nível que não se parecem com o que costumava chamar de programa e se pergunta se há semânticas de baixo nível. A resposta é sim.
  2. Você quer saber como provar que um modelo corresponde à realidade. Como na física, você não. Você simplesmente cria modelos melhores e os compara com a realidade.
  3. Você não viu a distinção entre sintaxe e semântica e várias maneiras de atribuir significados a programas. Duas perguntas anteriores listam alguns livros.

Essa resposta está apenas tentando identificar três maneiras diferentes pelas quais eu entendi a pergunta. Aprofundar-se em qualquer um desses pontos exigiria muito espaço.

Radu GRIGore
fonte
8

Uma abordagem para reduzir a diferença entre um programa e sua especificação é usar uma linguagem com uma semântica formal. Um exemplo interessante aqui seria Esterel . Dê uma olhada na página de Gérard Berry na web para algumas palestras interessantes sobre seu trabalho que traz métodos formais para o mundo real. http://www-sop.inria.fr/members/Gerard.Berry/

ps Esteve em um Airbus? Você voou com métodos formais!

Ross Duncan
fonte
1
qualquer referência sobre como a airbus usa métodos formais seria útil. (entender que seu informações proprietárias possibily.)
vzn
@RossDuncan Encontrei esta página da web depois de acessar a página da Berry e fazer algumas pesquisas. Este é o método formal que a Airbus estava usando que você estava se referindo?
Scaaahu 16/09/12
Não tenho informações internas sobre o uso do Esterel pela Airbus; meu comentário simplesmente repete uma observação que Berry fez durante uma palestra. No entanto, esta página anuncia o uso bem-sucedido do produto SCADE na Airbus. Se você olhar para a história de Esterel, ela foi adotada pela Dassault bem cedo. Google é seu amigo.
Ross Duncan
2
Airbus também usa astree.ens.fr
Radu GRIGore
7

A ciência da construção de software confiável no "mundo real" ainda está sendo desenvolvida e, de certa forma, está se aproximando de um estudo inerentemente cultural ou antropológico, porque computadores e software não "causam" erros - os humanos fazem! esta resposta se concentrará em abordagens gerais de perguntas e respostas, nas quais a verificação formal de software pode ser vista como um elemento.

Uma observação notável é que muitas vezes os softwares "bons o suficiente" e "buggy" podem frequentemente superar os softwares testados, mas com menor funcionalidade, no mercado. em outras palavras, o mercado nem sempre valoriza a qualidade do software e as técnicas modernas de engenharia de software, que nem sempre enfatizam a qualidade, refletem isso. além disso, a qualidade muitas vezes pode adicionar uma despesa significativa ao produto final. com essas ressalvas, aqui estão alguns princípios básicos:

  • sistemas redundantes / tolerantes a falhas. esta é uma ampla área de estudo. tolerância a falhas e redundância podem ser projetadas nas várias camadas de um sistema. por exemplo, um roteador, um servidor, uma unidade de disco, etc.

  • teste . todos os tipos - teste de unidade, teste de integração, teste de aceitação do usuário, teste de regressão etc.

  • Atualmente, os testes automatizados por meio de suítes de testes que podem ser executados sem supervisão são mais desenvolvidos / importantes. os conjuntos de testes em execução geralmente são acoplados à ferramenta de construção.

  • Um conceito importante no teste é a cobertura do código . ou seja, qual código é exercido pelo teste. um teste não pode encontrar um erro no código que não é "tocado" pelo teste.

  • outro conceito-chave nos testes é a capacidade de teste, que exercita o código que não é facilmente acessado diretamente.

  • testes devem exercitar todos os níveis do software. se o software for bem modularizado, isso não será difícil. testes de nível superior devem penetrar profundamente no código. testes que exercem grandes quantidades de código com pequenas configurações de teste aumentam a "alavancagem de teste" .

  • tornar o código o menos complicado possível é importante para o teste. o teste deve ser considerado no design da arquitetura. geralmente existem várias maneiras de implementar o mesmo recurso, mas algumas têm implicações muito diferentes para a cobertura / alavancagem de teste. para cada ramificação do código, geralmente é outro caso de teste. ramificações dentro de ramificações escalam para aumento exponencial nos caminhos de código. portanto, evitar uma lógica altamente aninhada / condicional melhora a capacidade de testar.

  • estudar falhas de software famosas (maciças), das quais existem muitos exemplos e estudos de caso, é útil para entender a história e desenvolver uma mentalidade orientada para considerações de qualidade.

  • pode-se deixar levar pelos testes! existe um problema com muito pouco ou muito teste. existe um "ponto ideal". o software não pode ser construído com sucesso em nenhum dos extremos.

  • use todas as ferramentas básicas da maneira mais eficaz. depuradores, criadores de perfil de código, ferramentas de cobertura de código de teste, sistema de rastreamento de defeitos, etc! não se compromete necessariamente com a correção, mas rastreia até os menores defeitos do software de rastreamento.

  • O uso cuidadoso do SCM, o gerenciamento do código fonte e as técnicas de ramificação são importantes para evitar regressões, isolar e progredir correções, etc.

  • Programação em versão N : uma prática usada frequentemente para o desenvolvimento de software de missão crítica. A premissa dessa prática é que é improvável que N programas desenvolvidos independentemente tenham o mesmo bug / falha comum. Isso foi criticado em alguns artigos . NVP é, no entanto, uma prática e não um conceito teórico.

Acredito que o físico Feynman tenha algum relato do método usado pela NASA para garantir a confiabilidade dos sistemas de ônibus espaciais em seu livro "O que você se importa com o que as outras pessoas pensam?" - ele disse que tinha duas equipes, digamos, equipe A e equipe B. equipe A construiu o software. a equipe B adotou uma abordagem antagônica à equipe A e tentou interromper o software.

ajuda se a equipe B tiver bons conhecimentos de engenharia de software, ou seja, eles próprios poderão escrever código / testes programáticos etc. nesse caso, a equipe B tinha um nível quase igual de recursos que a equipe A., por outro lado, essa abordagem é cara porque pode quase dobrar o custo de construção do software. mais tipicamente, há uma equipe menor de controle de qualidade em comparação com a equipe de desenvolvimento.

vzn
fonte
8
Alguém deve verificar se o seu sistema operacional está correto com relação à especificação de que pressionar a tecla Shift e uma letra produz uma letra maiúscula.
Andrej Bauer
1
adendo: restrições de cronograma podem afetar a qualidade. veja também triângulo mgt do projeto composto por escopo, custo, cronograma com qualidade a "área" afetada por todos 3. veja também "Por que o setor de TI não pode entregar projetos grandes e sem falhas tão rapidamente quanto em outros setores?" . eu mesmo não adicionei o item da versão N [sua outra resposta], mas observe que Feynman mencionou que a NASA também o usou no design do ônibus espacial.
vzn
1
Além disso, "por que o software não é tão confiável quanto um carro"?
precisa saber é o seguinte
1
outro estudo de caso interessante é o mars rover, que possui grandes quantidades de código, muitas delas geradas automaticamente. nesse caso, o campo rovers anterior testou a maior parte do software e foi reutilizado.
vzn
6

Uma abordagem antiga (mas ainda é usada em alguns aplicativos) é a programação da versão N

Da Wikipedia:

Programação em versão N ( NVP ), também conhecida como programação multiversão , é um método ou processo na engenharia de software em que vários programas funcionalmente equivalentes são gerados independentemente a partir das mesmas especificações iniciais. O conceito de programação da versão N foi introduzido em 1977 por Liming Chen e Algirdas Avizienis com a conjectura central de que a "independência dos esforços de programação reduzirá bastante a probabilidade de falhas idênticas de software que ocorrem em duas ou mais versões do programa" .O objetivo O NVP é melhorar a confiabilidade da operação do software, construindo tolerância a falhas ou redundância.
....

Veja, por exemplo: " Desafios na construção de falhas - sistema de controle de vôo tolerante para aeronaves civis "

Marzio De Biasi
fonte
Vale a pena notar que a programação em versão n não funciona . A suposição fundamental - a saber, que erros em tentativas repetidas do processo de desenvolvimento de software são independentes - é completamente falsa . Essa ideia não faz sentido teoricamente (um algoritmo de difícil implementação não será magicamente mais fácil para uma segunda equipe independente) e também foi desmascarada experimentalmente: o experimento de John Knight e Nancy Leveson, mostrando que a suposição de independência não é estatisticamente válida é um dos jornais mais famosos em engenharia de software.
Neel Krishnaswami
@NeelKrishnaswami: Eu concordo! No entanto, acho que (mas não sou um especialista) que não funciona deve ser substituído por ele não melhora a confiabilidade tanto quanto deveria se comparado a outras abordagens . Citando K&L: " ... Nunca sugerimos que o nosso resultado fosse usado por si próprio como base para uma decisão sobre a eficácia da programação da versão N. Apenas sugerimos que o cuidado seria apropriado ... ". Eu acho que o debate sobre o quanto a abordagem NVP pode ser útil para o projeto crítico do sistema ainda está em aberto (ver o recente trabalho de Khoury et al.)
Marzio De Biasi
4

Fajrian, essa pergunta que você fez abordou dois dos maiores problemas na pesquisa do engenheiro de software: a conformidade entre a especificação e o modelo e entre o modelo e o código. Modele aqui uma representação do que o sistema fará, ou como será feito, há muitos níveis para modelar um sistema.

Portanto, algumas pessoas estão tentando encontrar a melhor resposta para sua pergunta. Porque é muito difícil verificar a correção de um software com base em um modelo, por exemplo, usando métodos formais. Sei que o JML é uma maneira de fazer isso, mas não conheço os limites de seu uso.

Para finalizar, como é difícil verificar a correção do código, as pessoas tentam misturar métodos e testes formais, criando testes automaticamente a partir de especificações, por exemplo. Um exemplo para sistemas em tempo real é o TIOSTS, baseado em eventos cronometrados de entrada / saída.

Testar apenas não é uma abordagem de método formal, pois melhora a confiabilidade, mas não verifica a correção.


fonte
3

Dois ou três anos atrás, comecei a analisar métodos formais aplicados ao software. Essa foi uma busca motivada pela curiosidade e pelo sentimento de que eu tinha que aprender ferramentas e métodos de programação com períodos de tempo mais longos. Embora eu tenha sonhado com um Silver Bullet , realmente pensei que não havia uma resposta para a pergunta: "Como posso escrever um programa correto?".

Neste ponto da busca, depois de experimentar algumas ferramentas (Z, B, VHDL e Estelle), estou usando o TLA + . Essa é uma variante da lógica temporal com ferramentas de software para verificação de modelos e provas mecânicas. Acho que escolhi essa abordagem porque L. Lamport estava por trás dela, a sintaxe era simples, havia muitos exemplos, havia uma comunidade cuidando dela e a linguagem e as ferramentas estavam razoavelmente bem documentadas.

Em relação à minha pergunta inicial, acho que não há uma resposta completa. No entanto, vale a pena aprender que vale a pena especificar formalmente algumas partes de um sistema. Também é bastante útil fazer engenharia reversa de alguns complexos. Ou seja, é eficaz criar um modelo para as partes difíceis e críticas. No entanto, não creio que exista um método eficaz para converter automaticamente a especificação em uma linguagem ou estrutura de programação (a menos que você restrinja o projeto a um ambiente muito específico). Também não acho que ter uma especificação formal o impeça de testar o software.

Em poucas palavras, acho que a seguinte metáfora (de Lamport) é realmente poderosa: "Você espera que uma casa seja construída automaticamente a partir de uma planta? Você comprará uma casa que ainda não foi construída e que não possui planta?" .

Durante esta missão, achei úteis os seguintes recursos:

  • Métodos de especificação de software . Este livro fornece uma ampla visão geral dos métodos e ferramentas existentes. Lá você encontra explicações e exemplos básicos de Z, SDL, TLA +, Redes de Petri, Coq, etc.
  • Se você acha que o TLA + atende às suas necessidades, eu realmente recomendo o livro Specifying Systems . Você pode obter o livro de graça e vem com exemplos para brincar :).
  • Recentemente, li alguns artigos relacionados que dão duas perspectivas diferentes ao estado da arte dos métodos formais: o caso dos métodos formais e a matemática formalmente verificada .

Boa sorte!

marcmagransdeabril
fonte
1

As respostas até agora já cobriam a maior parte do que deveria ser dito sobre os fundamentos de como relacionar especificação e código entre si. Eu só quero adicionar um ponto mais prático que aborda a questão no cabeçalho deste tópico:

Como criar software de missão crítica?

Existem ferramentas que analisam automaticamente seu código em busca de erros (violações da especificação ou "bugs típicos"). Que eu saiba, esses métodos se baseiam principalmente na análise estática e não estão imediatamente relacionados às teorias que você mencionou (LTL / CTL / ...), mas encontram erros no código real e já é viável, do ponto de vista prático. vista, usar essas ferramentas em projetos industriais. Pessoalmente, não usei muitos deles, mas parece que essas ferramentas começam a ser aceitas pelos praticantes. Para leituras adicionais, posso recomendar o seguinte artigo do blog:

http://www.altdevblogaday.com/2011/12/24/static-code-analysis/

Markus
fonte
Exemplo de implementação com Java, código-fonte aberto em Apache findbugs
vzn
0

Os algoritmos de certificação podem ser úteis na criação de software de missão crítica.

Um algoritmo de certificação é um algoritmo que produz, com cada saída, um certificado ou testemunha (prova fácil de verificar) de que a saída específica não foi comprometida por um bug.

Leia mais neste documento de pesquisa Algoritmos de certificação de McConnell, RM e Mehlhorn, K. e Naher, S. e Schweitzer, P.

Pratik Deoghare
fonte
Em 1998, Pnueli, Siegel e Singerman descreveram essa idéia aplicada aos compiladores, sob o nome de validação da tradução. Os compiladores são inerentemente de ordem superior (a entrada é um programa, a saída é um programa), portanto, eles tendem a ser difíceis de verificar. Mas existem pessoas loucas como X. Leroy que desenvolvem compiladores verificados de qualquer maneira. (Crazy, no melhor sentido possível!)
Radu Grigore
-2

Mas então como verificar se o software (não apenas a especificação) está realmente correto?

Teste de unidade? Escreva um teste para todos os requisitos da especificação e, em seguida, teste todos os métodos da sua implementação para verificar se a saída / entrada está em conformidade com a especificação. Isso pode ser automatizado para que esses testes sejam executados continuamente para garantir que nenhuma alteração interrompa os recursos que funcionavam anteriormente.

Teoricamente falando, se seus testes de unidade tiverem 100% de cobertura de código (ou seja, todos os métodos do seu código são testados), seu software deve estar correto, desde que os testes sejam precisos e realistas.

Gillesv
fonte
5
Para qualquer programa razoavelmente complexo, a cobertura do código (por teste) não pode garantir a correção. Você teria que cobrir todas as execuções possíveis; todas as linhas de código não são suficientes.
Radu GRIGore
1
A cobertura do código é um conceito muito vago. Distinguimos entre, por exemplo, cobertura de método, cobertura de declaração, cobertura de filial, cobertura de caminho e assim por diante. Como Radu aponta, para programas não triviais, os testes geralmente ocorrem em explosões combinatórias. Dito isto, o software aeronáutico tem um excelente histórico e sua correção geralmente é baseada em testes extensivos.
Martin Berger
Se você quer dizer testar com ferramentas como JUnit, esse tipo de teste automático padrão não pode cobrir todos os casos (a menos que o programa seja extremamente pequeno). Para aplicações típicas, esse tipo de teste geralmente é suficiente. Mas para aplicativos de missão crítica, não sei se isso é suficiente (ou não).
fajrian 12/09/12
2
@vzn: Na minha experiência, há um acordo notável entre o que é considerado um bug pelos acadêmicos e, respectivamente, pelos profissionais. Além disso, aposto que a maioria dos meus colegas da indústria concordaria que "todo método no seu código é testado" não parece muito reconfortante. (E, não, eu não downvote eu quase nunca o fazem..)
Radu Grigore
1
@vzn: Eu disse que você disse o contrário? Eu estava simplesmente tentando explicar por que acredito que outros não estão votando positivamente nessa resposta. No momento, não posso responder a essa pergunta, porque não a entendo.
Radu GRIGore