Teste X-Máquina

O (Stream) X-Máquina Metodologia de ensaio é um teste funcional completo para uma abordagem de teste de software- e de hardware , que explora a escalabilidade do Córrego X-Machine modelo de computação. Usando esta metodologia, é provável para identificar um finito conjunto-teste que exaustivamente determina se a implementação do sistema testado corresponde a sua especificação. Este objetivo é alcançado através de uma abordagem de dividir e conquistar, em que o projeto é decomposto por refinamento em uma coleção de Córrego X-Máquina s, que são implementados como módulos separados, então testados na abordagem " bottom-up ". Em cada estágio de integração, o método de teste garante que os componentes testados estão corretamente integrada.

A metodologia supera limitações formais de indecidibilidade, exigindo que certos princípios de design para teste são seguidos durante a especificação e implementação. A escalabilidade resultante significa que sistemas de software e hardware práticos são constituídos por centenas de milhares de milhões de estados e transições foram testados com sucesso.

Motivação

Muito teste de software é meramente esperançoso, buscando exercer o sistema de software de várias formas para ver se todas as falhas podem ser detectadas. Teste pode de fato revelar algumas falhas, mas nunca pode garantir que o sistema está correto, uma vez que o teste é longo. Métodos de Teste funcionais procuram melhorar esta situação, através do desenvolvimento de um especificação formal que descreve o comportamento esperado do sistema, contra a qual a execução é posteriormente testada (uma espécie de teste de conformidade). A especificação pode ser validado contra as necessidades dos usuários e, mais tarde comprovada em termos deconsistente e completo pelo raciocínio matemático (eliminando quaisquer falhas de projeto lógicos). Métodos completos de [[teste] funcionais] exploraram a especificação sistematicamente, gerando conjuntos de testes que exercem o sistema de software implementado exaustivamente , para determinar se ele está de acordo com a especificação. Em particular:

• Teste positivo completo: confirma que todo o comportamento desejado está presente no sistema;
• O teste negativo completa: confirma que nenhum comportamento indesejado está presente no sistema.

Este nível de teste pode ser difícil de alcançar, uma vez que os sistemas de software são extremamente complexas, com centenas de milhares de milhões de estados e transições. O que é necessário é uma forma de quebrar a especificação e testar problema em partes que podem ser abordados separadamente.

Escaláveis, Especificações Abstratas

Mike Holcombe propôs pela primeira vez usando o modelo teórico de Eilenberg Samuel X-máquina como base para a especificação de software no final de 1980. Isso ocorre porque o modelo de forma limpa separa o fluxo de controle de um sistema da transformação realizada pelo sistema. Em um dado nível de abstração, o sistema pode ser visto como uma simples máquina de estado finito que consiste em alguns estados e transições. O processamento mais complexo é delegada as funções de processamento sobre as transições, que modificam o tipo de dados fundamental subjacente X . Mais tarde, cada função de processamento pode ser exposto e caracterizado por uma outra X-máquina, modelando o comportamento daquela operação do sistema.

Este apoia uma abordagem de dividir e conquistar, em que a arquitetura geral do sistema é especificado em primeiro lugar, em seguida, cada uma das principais operação do sistema é especificada, seguido por sub-rotinas, e assim por diante. Em cada passo, o nível de complexidade é administrável, devido à independência de cada camada. Em particular, é fácil para os engenheiros de software para validar a simples máquina de estados finitos em relação às necessidades do usuário.

Especificações Incrementalmente testáveis

Gilbert Laycock propôs pela primeira vez um tipo particular de X-máquina, o Stream X-Máquina, como a base para o método de teste. A vantagem desta variante foi a maneira na qual o teste pode ser controlado. Em um Stream X-Máquina, o tipo de dados fundamental tem uma forma particular: X = Out * × Mem × In *, onde In * é um fluxo de entrada, Out * é um fluxo de saída, e Mem é a memória interna. As transições de um Stream X-Máquina são rotulados com funções de processamento da forma φ: Mem × em → Out × Mem , isto é, eles consumem uma entrada do fluxo de entrada, possivelmente modificando memória, e produzir uma saída no fluxo de saída (veja artigo associado para mais detalhes).

Os benefícios para os testes são de que os sistemas de software projetados desta forma são observáveis em cada etapa. Para cada entrada, a máquina dá um passo, produzindo uma saída, de modo que os pares de entrada / saída que podem ser exatamente combinados. Isto contrasta com outras abordagens em que o sistema é executado para conclusão (tendo várias etapas) antes de que qualquer observação é feita. Além disso, em camadas Stream X-Máquinas oferecem uma abstração conveniente. Em cada nível, o testador pode esquecer sobre os detalhes das funções de processamento e considerar o (sub-)sistema de apenas como uma simples máquina de estados finitos. Existem métodos poderosos para sistemas de controle que estejam em conformidade com as especificações finitas estaduais, como W-método de Chow.

Método Especificação

Quando seguindo a metodologia de (Stream) X- máquina, a primeira etapa consiste em identificar os vários tipos de dados a serem processados. Por exemplo, um processador de texto irá usar tipos básicos Personagem (a entrada de teclado), Posição (posição do cursor do mouse) e Comando (comando de mouse ou menu). Pode haver outros tipos construídos, como Texto  :: = caráter * (a sequência de caracteres), Seleção  :: = Posição × Posição ( o início e final da seleção) e documento  :: = Texto × Seleção × booleano (o texto, uma possível seleção, e uma bandeira para sinalizar se o documento foi modificado).

Especificação de Alto Nível

A especificação de alto nível é um Stream X-Máquina que descreve a interação do usuário com o sistema principal. Por exemplo, o processador de texto vai existir em um número de estados, em que as teclas digitadas e comandos terão efeitos diferentes. Suponha-se que este processador de texto existe nos estados { 'Escrever' , 'Seleção' , 'Arquivo' , 'Edição' }. Esperamos que o processador de texto para começar no estado inicial 'Escrever' , mas para passar para o estado 'Seleção' se o mouse é arrastado , ou se a tecla shift é pressionada. Uma vez que a seleção for estabelecida, ele deve retornar para o 'estado' 'Escrever' . Da mesma forma, se uma opção de menu é escolhido, este deve entrar no 'Editar' ou 'estado' 'Arquivo' . Nesses estados, certas combinações de teclas podem ter significados diferentes. O processador de texto acabou voltando para o 'estado' 'Escrever' , quando qualquer comando de menu foi concluída. Esta máquina de estado é projetada e rotulada informalmente com as diversas ações que fazem com que ele mude de estado.

A entrada, memória e tipos de saída para a máquina de nível superior são agora formalizados. Suponha que o tipo de memória do processador de texto simples é o tipo Documento definido acima. Este trata de um documento como uma cadeia de texto, com duas posições marcando uma possível seleção e uma bandeira para indicar modificações desde o último salvar - comando. Um processador de texto mais complexo pode suportar a edição que pode ser desfeito, com uma sequencia de estados de documento: Documento  :: = ( Texto × Seleção ) *, que são contraídos em um documento cada vez que um ' 'salvar' '- comando é executado.

Suponha que o tipo de entrada para a máquina é: '=' In  :: Comando × caráter × Posição . Este reconhece que cada interação poderia ser uma inserção de caracteres simples, um comando de menu ou um posicionamento cursor. Qualquer dado interação é uma 3-tupla, mas alguns lugares podem estar vazios. Por exemplo, ( Inserir , 'a', ε) representaria digitar o caractere 'a'; enquanto ( Posição , ε, 32) significaria colocar o cursor entre caracteres 32 e 33; e ( Select , ε, 32) significaria selecionando o texto entre a posição atual do cursor e o lugar entre 32 e 33 caracteres.

O tipo de saída da máquina é concebida de modo que é possível determinar a partir da saída , que foi executado o processamento de função, em resposta a um dado de entrada. Isto refere-se à propriedade de saída distinguibilidade , descrito abaixo.

Especificação de baixo nível

Se um sistema é complexo, então ele provavelmente irá ser decomposto em vários Stream X-Máquinas. O tipo mais comum de refinamento é levar cada uma das principais funções de processamento (que foram as etiquetas na máquina de alto nível) e tratá-los como separados Stream X-Máquinas. Neste caso, a entrada, a memória e os tipos de saída para as máquinas de baixo nível será diferente dos definidos para a máquina de alto nível. Ou, este é tratado como uma expansão dos conjuntos de dados utilizados no nível alto, ou há uma tradução de conjuntos de dados mais abstratos em nível elevado em conjuntos de dados mais detalhados no nível inferior. Por exemplo, um comando Select em nível elevado poderia ser decomposto em três eventos: MouseDown , MouseMove , MouseUp no nível mais baixo.

Ipate e Holcombe mencionam vários tipos de refinamento, incluindo refinamento funcional , em que o comportamento das funções de processamento é elaborado em mais detalhe, e refinamento estado , em que um espaço de estado simples é dividida numa de espaço de estado mais complexo. Ipate comprova esses dois tipos de refinamento para ser eventualmente equivalente

Os sistemas são especificados baixo para o nível em que o designer está disposta a confiar nas operações primitivas suportados pelo ambiente de implementação. Também é possível testar pequenas unidades exaustivamente por outros métodos de teste.

Design para Testes de Condições

O (Stream) metodologia X-Máquina requer que o designer observe certas condições de projeto para teste. Estes não são normalmente muito difícil de satisfazer. Para cada Stream X-Máquina na especificação, temos de obter:

• 'Especificação Minimal' : A especificação deve ser um mínima máquina finita estado. Isto significa que a máquina estatal não deve conter estados redundantes, ou seja, estados em que o comportamento de transição observável é idêntica à de algum outro estado.

• 'Especificação determinística' : para cada estado da máquina, no máximo, uma das φ funções de processamento deve ser habilitado para a memória atual e a próxima valor de entrada. Isto assegura que o comportamento necessário para ser testado é previsível.

• 'Teste de Integridade' : Cada função φ tratamento deve ser executável para, pelo menos, uma entrada, com respeito a todos os estados de memória. Isto assegura que não existem impasses, onde a máquina está bloqueada com o estado atual da memória. Para garantir a integridade do teste, o domínio de uma função φ pode ser prorrogado com entradas de teste "especiais" que são usados somente durante o teste.

• Saída de distiguibilidade : Deve ser possível distinguir qual a função de processamento foi invocada a partir do seu valor de saída sozinho, para todos os pares de memória de entrada. Isto assegura que a máquina de estados pode ser dissociada a partir das funções de processamento. Para garantir uma saída distiguibilidade, o codomain de uma função φ pode ser prorrogado com saídas de teste "especiais" que são relevantes apenas durante os testes.

A máquina mínima é a máquina com o menor número de estados e transições para algum determinado comportamento. Mantendo a especificação mínima apenas assegura que os conjuntos de teste são tão pequenas quanto possível. Uma máquina determinística é necessário para sistemas que são previsíveis. Caso contrário, uma aplicação poderia fazer uma escolha arbitrária em relação à qual a transição foi feita. Alguns trabalhos recentes relaxou essa suposição para permitir testes de máquinas não determinísticas.

É necessária a integralidade de teste para garantir que a implementação é testável dentro do tempo tratável. Por exemplo, se um sistema tem distante ou difícil de alcançar estados que só são introduzidos depois de memória atingiu um certo valor limite, então entradas de teste especiais deve ser adicionado para permitir memória para ser ignorada, forçando a máquina do Estado para o distante estado. Isso permite que todos os estados (abstrato) a ser coberto rapidamente durante o teste. Saída de distiguibilidade é a propriedade da chave apoiar o método de ensaio escalável. Ele permite que o testador para tratar as funções de processamento φ rótulos como simples, cujo comportamento detalhado pode ser ignorada com segurança, ao testar a máquina de estado da próxima camada de integração. As saídas originais são valores de testemunhas, que garantem que uma determinada função foi chamado.

Método de Ensaio

O (Stream) X-Máquina método de ensaio assume que tanto o design e a implementação pode ser considerado (a coleção de) Stream X-Máquinas. Para cada par de máquinas correspondentes ( Spec , Imp ), o objetivo do teste é determinar se o comportamento de Imp , a máquina da execução, corresponde exatamente o comportamento dos Spec , a máquina da especificação. Note-se que PIM não precisa ser uma máquina mínima - que pode ter mais estados e transições do que Spec e ainda se comportam de forma idêntica.

Para testar todos os comportamentos, deve ser possível conduzir uma máquina em todos os seus estados, em seguida, tentar todas as transições possíveis (aqueles que deveriam ter sucesso, e aqueles que devem ser bloqueados) para alcançar a plena positiva e negativo ' 'teste (veja acima). Para transições que se sucedem, o estado de destino também deve ser verificada. Observe que, se Spec e PIM tem o mesmo número de estados, o acima descreve a menor test-set que atinge o objetivo. Se Imp tem mais estados e transições do que Spec , sequências de teste mais longos são necessários para garantir que os "estados redundantes 'em' 'Imp' 'também se comportam como esperado.

Testando todos os Estados

A base para a estratégia de geração de teste é W-método Tsun S. Chow para testar autômatos de estados finitos, escolhido porque ele suporta o teste de implementações redundantes. Método de Chow assume simples máquinas de estados finitos s com entradas e saídas observáveis, mas os estados não diretamente observáveis. Para mapear para formalismo Chow, as funções φ _i sobre as transições do Stream X-Máquinas são tratados simplesmente como rótulos (entradas, em termos Chow) e as saídas de distinção são usados diretamente . (Mais tarde, um mapeamento de entradas reais e memória ( mem , em ) é escolhido para acionar cada φ função, de acordo com o seu domínio).

Para identificar estados específicos em Imp , Chow escolhe um set caracterização, W , o menor conjunto de sequências de teste que caracteriza exclusivamente cada estado em Spec . Ou seja, quando a partir de um determinado estado, exercendo as sequências em W deve render pelo menos uma diferença observável, em comparação com a partir de qualquer outro estado.

Para chegar a cada estado esperado em Spec , o testador constrói o 'cover estado, C' , o menor conjunto de sequências de teste que atinge todos os estados. Este pode ser construído por exploração automática de primeira largura de Spec . O set-teste que valida todos os estados de um mínimo Imp é então: C math\Otimes</Matemática> W, ondemath\Otimes</Matemática> denotam o produto concatenado dos dois conjuntos. Por exemplo, se C = {<a>, <b>} e W = {<c>, <d>}, entãoC math\Otimes</Matemática> W = {<ac>, <ad>,<bc>, <bd>}.

Testando todas as transições

O test-set acima determina se um mínimo Imp tem os mesmos estados como Spec . Para determinar se um mínimo Imp também tem o mesmo comportamento de transição como Spec , o testador constrói a «tampa de transição, K '. Este é o menor conjunto de sequências de teste que atinge todos os estados e em seguida, tenta cada transição possível uma vez que, a partir desse estado. Agora, o alfabeto de entrada consiste de (os rótulos de cada) φ em função Φ. Vamos construir um conjunto de comprimento-1 sequências de teste, que consiste em funções únicas, escolhidas de Φ, e chamam isso de Φ ₁. A capa de transição é definida como K <Código>::=</Código> C math\cup</Matemática> C math\Otimes</Matemática> Φ₁.

Este tentará cada transição possível de todos os estados. Para aqueles que se sucedem, é preciso validar os estados de destino. Então, o menor conjunto de teste T₁ que valida completamente o comportamento de um mínimo Imp é dado por: T₁ ::= C $\otimes$ W $\cup$ C $\otimes$ Φ₁ $\otimes$ W. Essa fórmula pode ser rearranjada da seguinte maneira:

T₁ ::= C $\otimes$ (Φ₀ $\cup$ Φ ₁) $\otimes$ W,

onde Φ₀ é o conjunto contendo uma sequencia vazia {<>}.

SeImp possuir mais estados do que Spec, o conjunto de teste acima pode não ser suficiente para garantir o comportamento de replicar estados em Imp. Então, conjutos de grandes testes de sequencia são escolhidos, consistindo de todos os pares de funções Φ₂, todas as triplas de funções Φ₃ até o limite Φ_k, onde o teste é convencida de que Imp não pode conter cadeias de estados mais do que duplicado k-1. A fórmula teste final é dada por:

T_k ::= C $\otimes$ (Φ₀ $\cup$ Φ ₁ ... $\cup$ Φ _k) $\otimes$ W.

Esta completamente set-teste valida o comportamento de um não-minimal Imp em que se espera cadeias de estados duplicados para não mais do que k ser - 1. Para fins práticos, testando-se a k = 2, ou k = 3 é bastante exaustiva, revelando todas as falhas relacionadas com o Estado em implementações realmente pobres.