Como podemos ter certeza de que os componentes inferiores da programação de computadores, como compiladores, montadores, instruções de máquina etc. são impecáveis?

57

Como estamos nos tornando cada vez mais dependentes da computação, incluindo tarefas muito críticas da vida cotidiana, fiquei pensando como esses componentes vitais são testados.

Mais tecnicamente, como são testados os compiladores e montadores? (Suponho que isso esteja relacionado ao problema da parada !!)

Sudip Bhandari
fonte
36
Você pode querer começar sua pesquisa com o "Ken Thompson Hack" Veja reflexões sobre a confiança em confiança
Bryan Oakley
7
Aqui está um exemplo de um compilador para o qual existe uma prova de correção: compcert.inria.fr/doc/index.html
Giorgio
8
A maioria dos compiladores / linkers / montadores é testada mais profundamente, usando-os muito em muitas circunstâncias diferentes. Para encontrar erros, não há nada além de ter milhões de usuários usando seu compilador.
Bart van Ingen Schenau
3
e adicione o sistema operacional à lista também.
Erik Eidt

Respostas:

104

Você não pode ter certeza, mas apenas assume que sim, até descobrir que não. Houve muitos bugs em compiladores e hardware ao longo dos anos.

A maneira como eles são testados, por exemplo, um compilador, é que eles são definidos de maneira muito estreita e rígida, escritos com cuidado e testados com um enorme conjunto de testes para verificar a exatidão. Acrescente a isso a ampla base de usuários de um compilador, e mais bugs serão detectados e relatados. Um aplicativo de agendamento de consultas com dentistas, comparativamente, tem muito menos usuários e ainda menos capazes de detectar defeitos.

O SQLite consiste em cerca de 73k linhas de código, enquanto seu conjunto de testes consiste em cerca de 91378k linhas de código, mais de 1250x vezes a do próprio SQLite. Espero que os compiladores e outras ferramentas principais tenham proporções similares. Atualmente, os processadores são projetados essencialmente com software, usando linguagens de descrição de hardware como Verilog ou VHDL, e eles também executam testes de software, além de pinos de E / S especializados para executar autotestes no ponto de fabricação.

Por fim, é um jogo de probabilidade, e os testes repetidos e abrangentes permitem que você reduza a probabilidade de defeitos a um nível aceitável baixo, o mesmo que em outro projeto de software.

whatsisname
fonte
7
Muitas vezes me perguntei a mesma pergunta que o OP, mas em relação aos DBMS. Você deu um ótimo exemplo que respondeu no contexto do SQLite. Obrigado!
Brandon
7
+1, mas de alguma forma duvido que "compiladores e outras ferramentas principais tenham proporções similares".
Mehrdad
5
Observe que (1) o SQLite realmente tem dois conjuntos de testes, com redundância não trivial entre os dois e (2) ainda existem erros encontrados no SQLite, apesar disso.
Matthieu M.
7
Fiquei com a impressão de que o SQLite é um dos softwares mais "amplamente testados" (em termos de linhas de código de teste / linhas de código operacional) disponíveis para uso geral, mais ainda do que muitos compiladores. No mínimo, um compilador completo é um software enorme e não consigo imaginar que ele tenha milhares de vezes a quantidade de código de teste. (O GCC tem até 14,5 milhões de linhas. Parece improvável que a coleção do compilador propriamente seja apenas 14k LOC ou que eles tenham uma base de código de teste de 14 bilhões de linhas ao lado! :-P)
David Z
2
@DavidZ: Certamente, é certamente o único projeto que conheço a usar testes extensivos de OOM, por exemplo (eles usam um injetor de falhas para o teste e os repetem repetidamente na 1ª e na 2ª alocação ... até todo o teste É executado).
Matthieu M.
46

Em termos leigos:

  1. Você não pode.
  2. Compiladores e intérpretes são testados em unidade como qualquer outro software (profissional).
  3. Um teste bem-sucedido não significa que um programa esteja livre de erros, apenas significa que nenhum erro foi detectado.
  4. Uma ampla base de usuários que utiliza o compilador durante um longo período de tempo é um bom indicador de poucos bugs, porque os usuários costumam testar casos nos quais os designers não pensavam.
  5. Ser código aberto também é um bom indicador. "Dado o número suficiente de olhos, todos os bugs são superficiais ... Dada uma base grande de beta-testadores e co-desenvolvedores, quase todos os problemas serão caracterizados rapidamente e a correção será óbvia para alguém". . Um compilador de código fechado pode ter bugs que surgem em horários muito específicos ou que geram código de máquina abaixo do ideal, e a empresa por trás dele simplesmente não pode divulgar sua existência, dando a ele uma prioridade muito baixa no roteiro do produto.

Conclusão:

Eu diria que vá para OOP ( O ld, O pen e P opular). Acabei de inventar esse acrônimo.

Tulains Córdova
fonte
19
+1 Para inventar outro TLA (acrônimo de três letras) - o mundo ainda não possui o suficiente.
s1lv3r
34
Além disso, OOP ainda não tinha significado na programação de computadores. Então KTT (parabéns a ti)!
Pierre Arlaud
15
O comentário de Pierre é uma piada @Dannnno.
precisa
19
Alternativamente, poderia P opular, O ld, e ó caneta. ;) Na verdade, é assim que eu os classificaria em ordem de importância.
jpmc26
23
@ jpmc26 Eu iria com Prático, Antigo, Aberto e Popular. Quanto à sigla ...
StupidOne 30/12/2015
24

São tartarugas até o fim.

Nada é certo. Você não tem escolha a não ser se contentar com classificações de confiança.

Você pode pensar nisso como uma pilha: Matemática> Física> Hardware> Firmware> Sistema operacional> Assembler / Compiler / etc

Em cada nível, você tem testes que podem ser executados para melhorar seus índices de confiança. Alguns desses testes têm a qualidade de provas formais, alguns deles são baseados em observação, a maioria é uma combinação de ambos.

A parte complicada é desvendar a recursão em alguns desses testes, porque agora usamos programas para fazer provas e análises observacionais, onde ficou muito difícil fazer isso manualmente.

Em última análise, embora a resposta seja que você tente tudo o que puder pensar. Análise estática, distorção, simulação, execução com entradas extremas propositadamente selecionadas ou entradas aleatórias, execução / mapeamento de todos os caminhos de controle, provas formais etc. Basicamente, seu objetivo nos testes deve sempre ser o máximo possível para provar que seu produto (por exemplo, teoria / chip / programa) não funciona como pretendido. Se você fizer um esforço genuíno e ainda falhar, poderá melhorar sua classificação de confiança na correção do seu produto.

O teste é, na melhor das hipóteses, um processo de semidecisão, o que significa que, dado que há um erro, você o encontrará eventualmente, mas nunca poderá ter certeza de ter encontrado todos eles. Mesmo com o software formalmente verificado, você ainda conta com a física, as ferramentas usadas para fazer as provas formais e o que você provou ser necessário e suficiente para o seu programa fazer o que é (geralmente subjetivamente) "pretendido". Isso sem mencionar todos os outros componentes que você está usando que não têm provas formais.

voutasaurus
fonte
17

Essa é uma pergunta "perigosa" para os novos desenvolvedores, pois eles começarão a culpar suas ferramentas em vez de seu código (já estiveram lá, fizeram isso, viram muitas fazê-lo). Embora haja erros nos compiladores, ambientes de tempo de execução, SO, etc., os desenvolvedores devem ser realistas e lembrar que, até que haja evidências e testes de unidade demonstrando o contrário, o erro está no seu código .

Em mais de 25 anos de programação principalmente em C, C ++ e Java, encontrei:

  • dois erros devido a um erro do compilador (gcc e SunOS C)
  • cerca de uma vez por ano ou dois, um erro devido a um problema Java JVM (geralmente relacionado ao consumo de memória / coleta de lixo)
  • cerca de uma vez por mês ou dois, um bug em uma biblioteca, que freqüentemente é corrigido usando a versão mais recente ou revertendo para a versão anterior da biblioteca

Todos os outros erros estão diretamente relacionados a um erro ou, mais frequentemente, à falta de entendimento de como uma biblioteca funciona. Às vezes, o que parece ser um bug deve-se a uma incompatibilidade, por exemplo, como a estrutura da classe Java mudou e quebrou algumas bibliotecas da AOP.

Ed Griebel
fonte
Estou curioso - em que anos para quais idiomas? No EGCS, dias antes de o C ++ ser padronizado adequadamente, os bugs do compilador não eram tão difíceis de encontrar ...
Charles Duffy
3
O mais obscuro o compilador, cpu ou linguagem mais fácil é assim que encontrar bug nos compiladores (antes que alguém) assim que encontrar 2 em GCC C é bom :)
Surt
11
Por acaso, perdi apenas um mês presumindo que o problema que estava tendo estava nos meus scripts gdb ou na minha compreensão do que estava examinando. Eventualmente, fiquei desconfiado, simplifiquei meu caso de teste e encontrei uma falha de design em uma biblioteca (libkvm), que tornava um depurador de kernel incapaz de acessar determinados endereços a partir de um core dump. Ou seja, YMMV - e estou mais feliz quando encontro um novo bug no código a montante, especialmente algo que estou usando em vez de desenvolver.
Arlie Stephens
Claro que não foi um bug do compilador , nem mesmo uma das bibliotecas mais usadas. E, para dizer a verdade, não encontro bugs naqueles com nenhuma frequência.
Arlie Stephens
@ArlieStephens Há uma lição: simplificar seu caso de teste é algo que você deve fazer desde o início quando não conseguir encontrar um problema. Independentemente de o problema ser seu ou de outro código, isso o ajudará a reduzi-lo. Frequentemente, se o problema estiver no outro código, isso resultará em "evidências e testes de unidade demonstrando" isso.
Jpmc26
8

Acho que um ponto interessante aqui é que a grande maioria das licenças de software comercial (e de fato software de código aberto) especifica especificamente que você não pode confiar no software.

O SOFTWARE É FORNECIDO "TAL COMO ESTÁ", SEM GARANTIA DE QUALQUER TIPO, EXPRESSA OU IMPLÍCITA, INCLUINDO MAS NÃO SE LIMITANDO A GARANTIAS DE COMERCIALIZAÇÃO, ADEQUAÇÃO A UMA FINALIDADE ESPECÍFICA E NÃO INFRACÇÃO.

Do contrato de licença do Microsoft Word

. Exceto pela Garantia Limitada e na extensão máxima permitida pela lei aplicável, a Microsoft e seus fornecedores fornecem o Software e os serviços de suporte (se houver) COMO ESTÃO E COM TODAS AS FALHAS, e por este meio negam todas as outras garantias e condições, sejam expressas, implícitas ou estatutárias, incluindo, entre outras, garantias, deveres ou condições implícitas de comercialização (se houver), adequação a um propósito específico, confiabilidade ou disponibilidade, precisão ou completude de respostas, resultados, esforço profissional, de falta de vírus e falta de negligência, tudo com relação ao Software, e o fornecimento ou falha no fornecimento de suporte ou outros serviços, informações, software e conteúdo relacionado através do Software ou decorrentes do uso do Software .

Em essência, essa frase da licença em quase todos os softwares que você usa especifica que você não pode confiar no software e muito menos no compilador usado.

O software é como uma teoria científica, é considerado como funcionando conforme especificado até que não funcione.

Toby Allen
fonte
+1 por apontar que as próprias licenças afirmam que nenhum software é perfeito.
Tulains Córdova
3
Fiquei satisfeito ao notar um desvio dessa prática no ViaVoice da IBM para Mac. Em vez do habitual "se não funcionar, muito ruim", eles na verdade disseram algo como "O software deve ser executado conforme especificado".
WGroleau
11
Uma tradução em linguagem simples dessa parte específica da frase de garantia é: "Isso pode ser um software ou pode ser um sh * t. Pode funcionar. Pode não funcionar. Mesmo que funcione, pode não funcionar. faça o que quiser. Ah, a propósito, podemos ter roubado pedaços dele de outra pessoa. Pena que temos o seu dinheiro e o usamos para contratar muitos advogados. JOGO! ON! Nyah-nyah -nyah-nyah-nyaaah-naah! ". :-)
Bob Jarvis
2
@BobJarvis: Minha declaração de garantia favorita, usada em alguns softwares de código aberto (como o nmap IIRC), é "Se quebrar, você poderá manter as duas partes".
Peter Cordes 01/01
Essa declaração é onipresente em software de código aberto e em muitos softwares de código fechado sem custo. Ele não aparece na maioria das licenças de software pagas comerciais.
GTC
2

Como escritor de compilador para uma linguagem matemática *, pela minha experiência, posso dizer em teoria que você não pode. E alguns dos erros fornecem resultados errados, como (da minha lista de vergonha), calculando 6/3*2da direita 6/(3*2)e produzindo 1 sem travar ou fornecer erros de compilação sem sentido.

Porém, muitos compiladores da IMHO não têm tantos bugs quanto outros softwares porque:

  • Escrever testes de unidade é fácil. Cada declaração é uma unidade e você pode escrever testes tão simples quanto:test_unit("2+(-2)*(-2+1)*3+1",9);
  • Um programa é uma combinação de instruções e, para qualquer programa produzir o resultado correto, cada instrução individual deve fornecer o resultado correto (principalmente). Portanto, é muito improvável que haja erros enquanto o programa fornece o resultado correto.
  • À medida que o tamanho e o número de programas escritos aumentam, a probabilidade de pegar bugs aumenta dramaticamente.

Para montadores, instruções de máquina, etc, o acima também é válido; por outro lado, a verificação e a validação no design e produção de chips têm processos muito mais rigorosos, pois é um grande negócio: a automação de design eletrônico .

Antes de iniciar a produção, cada CPU deve ser testada rigorosamente porque cada bug custa quase dois milhões de dólares: existem enormes custos de produção não recorrentes na produção de chips. Portanto, as empresas gastam muito dinheiro e escrevem muito código de simulação para seu design antes de iniciarem a produção, embora isso não dê 100% de garantia - por exemplo: o bug do Pentium FDIV.

Em suma, é muito improvável que haja erros graves em compiladores, códigos de máquina etc.

Minha humilde linguagem matemática *

Gorkem
fonte
A Intel testa sua CPU executando sequências de instruções aleatórias e comparando com um modelo de software, entre outras coisas: tweakers.net/reviews/740/4/… . É por isso que você costuma ver erratas realmente obscuras publicadas, para alguma combinação realmente improvável de instruções em um modo incomum.
Peter Cordes 01/01
0

Sem falhas? Eles não são. Eu instalei recentemente algumas "atualizações" e levou meses (e várias seções reprogramadas do código) mais tarde para que meu site ASP.NET estivesse funcionando corretamente novamente, devido a alterações inexplicáveis ​​em como várias coisas básicas funcionaram ou falharam.

No entanto, eles são testados e usados ​​por muitas pessoas inteligentes e orientadas para os detalhes, que tendem a perceber, relatar e corrigir a maioria das coisas. O Stack Exchange é um ótimo exemplo (e aprimoramento) de como todas as pessoas que usam essas ferramentas ajudam a testar e analisar como essas ferramentas incrivelmente complexas e de baixo nível funcionam, pelo menos no que diz respeito ao uso prático.

Mas impecável, não. Embora você também possa ver pessoas no Stack Exchange obtendo informações impressionantes sobre detalhes de desempenho, conformidade e peculiaridades dos padrões, sempre existem falhas e imperfeições, especialmente quando pessoas diferentes têm opiniões diferentes sobre o que é uma falha.

Dronz
fonte
-1

Para mostrar que os sistemas subjacentes são impecáveis, você também

a) Necessidade de provar que são impecáveis

  1. Prova matemática
  2. Realisticamente possível apenas para programas triviais

b) Faça um teste exaustivo

  1. Só é possível para programas triviais e alguns programas simples
  2. Assim que um elemento de temporização entra no teste, não é possível fazer um teste exaustivo, pois o tempo pode ser dividido indefinidamente.
  3. Além dos programas triviais, as possíveis opções de execução explodem exponencialmente.

No teste de software, o teste exaustivo é usado apenas no teste de unidade de algumas funções simples.

Exemplo: você deseja testar uma entrada utf-8 de 8 caracteres em algum campo, escolhe cortar a entrada 8 vezes o comprimento máximo 6 de utf-8 em bytes, o que fornece 8 * 6 = 48 bytes para realmente ter um quantidades finitas de possibilidades.

Agora você pode pensar que só precisa testar os 1.112.064 pontos de código válidos de cada um dos 8 caracteres, ou seja. 1.112.064 ^ 8 (digamos 10 ^ 48) testa (o que já é improvável), mas você realmente precisa testar cada valor de cada um dos 48 bytes ou 256 ^ 48, que é cerca de 10 ^ 120, que é a mesma complexidade do xadrez comparado ao número total de átomos no universo de aproximadamente 10 ^ 80.

Em vez disso, você pode usar, em ordem crescente de esforço, e cada teste deve cobrir todo o anterior:

a) teste uma amostra boa e uma ruim.

b) cobertura de código, ie. tente testar todas as linhas de código, o que é relativamente simples para a maioria dos códigos. Agora você pode se perguntar qual é o último 1% do código que não pode testar ... bugs, código morto, exceções de hardware etc.

c) cobertura do caminho, todos os resultados de todos os ramos em todas as combinações são testados. Agora você sabe por que o departamento de teste o odeia quando suas funções contêm mais de 10 condições. Você também se pergunta por que o último 1% não pode ser testado ... alguns ramos dependem dos ramos anteriores.

d) teste de dados, teste várias amostras com valor de borda, valores problemáticos comuns e números mágicos, zero, -1, 1, min +/- 1, max +/- 1, 42, rnd valores. Se isso não lhe fornecer cobertura de caminho, você sabe que não capturou todos os valores em sua análise.

Se você já faz isso, deve estar pronto para o exame básico do ISTQB.

Surt
fonte