Complexidade Ciclomática
Prof. Alysson Filgueira Milanez
alysson.milanez@ufersa.edu.br
Teste de Software
Conceitos Básicos
2
Complexidade Ciclomática
O teste estrutural baseia-se no conhecimento da estrutura interna do programa, sendo os aspectos de implementação fundamentais para a geração/seleção dos casos de teste associados
3
Complexidade Ciclomática
Em geral, a maioria dos critérios da técnica estrutural utiliza uma representação de programa conhecida como “Grafo de Fluxo de Controle” (GFC) ou “Grafo de Programa”
4
Complexidade Ciclomática
Um programa P pode ser decomposto em um conjunto de blocos disjuntos de comandos
A execução do primeiro comando de um bloco acarreta a execução de todos os outros comandos desse bloco, na ordem dada
5
Complexidade Ciclomática
Todos os comandos de um bloco, possivelmente com exceção do primeiro, têm um único predecessor e exatamente um único sucessor, exceto possivelmente o último comando
6
Complexidade Ciclomática
Usualmente, a representação de um programa P como um GFC (G = (N, E, s)) consiste em estabelecer uma correspondência entre vértices (nós) e blocos e em indicar possíveis fluxos de controle entre blocos por meio das arestas (arcos)
7
Complexidade Ciclomática
Assume-se que um GFC é um grafo orientado, com um único nó de entrada s ∈ N e um único nó de saída o ∈ N, no qual cada vértice representa um bloco indivisível de comandos e cada aresta representa um possível desvio de um bloco para outro
8
Complexidade Ciclomática
Quando essas condições não forem satisfeitas, esse fato será indicado explicitamente
Cada bloco de comandos tem as seguintes características:
9
Complexidade Ciclomática
Com base no GFC podem ser escolhidos os elementos que devem ser executados, caracterizando, assim, o teste estrutural
10
Complexidade Ciclomática
Seja um GFC G = (N, E, s) em que N representa o conjunto de nós, E o conjunto de arcos, e s o nó de entrada
Um “caminho” é uma sequência finita de nós (n1, n2, ..., nk), k ≥ 2, tal que existe um arco de ni para ni+1 para i = 1, 2, ..., k − 1
11
Complexidade Ciclomática
Um caminho é um “caminho simples” se todos os nós que compõem esse caminho, exceto possivelmente o primeiro e o último, são distintos; se todos os nós são distintos, diz-se que esse caminho é um “caminho livre de laço”
12
Complexidade Ciclomática
Um “caminho completo” é aquele em que o primeiro nó é o nó de entrada e o último nó é um nó de saída do grafo G
Seja IN(x) e OUT(x) o número de arcos que entram e que saem do nó x, respectivamente
Assumimos IN(s) = 0, tal que s é o nó de entrada, e OUT(o) = 0, tal que o é o nó de saída
13
Complexidade Ciclomática
As ocorrências de uma variável em um programa podem ser uma “definição”, uma “indefinição” ou um “uso”
Usualmente, os tipos de ocorrências de variáveis são definidos por um modelo de fluxo de dados
Uma definição de variável ocorre quando um valor é armazenado em uma posição de memória
14
Complexidade Ciclomática
Em geral, em um programa, uma ocorrência de variável é uma definição se esta estiver: (i) no lado esquerdo de um comando de atribuição; (ii) em um comando de entrada; ou (iii) em chamadas de procedimentos como parâmetro de saída
15
Complexidade Ciclomática
Uma variável está indefinida quando não se tem acesso ao seu valor ou sua localização deixa de estar definida na memória
A ocorrência de uma variável é um uso quando a referência a essa variável não a definir
Dois tipos de usos são caracterizados: “c-uso” e “p-uso”
16
Complexidade Ciclomática
O primeiro tipo afeta diretamente uma computação realizada ou permite que o resultado de uma definição anterior possa ser observado; o segundo tipo afeta diretamente o fluxo de controle do programa
Observa-se que, enquanto c-usos estão associados aos nós do GFC, p-usos estão associados a seus arcos
17
Complexidade Ciclomática
Considere uma variável x definida em um nó i, com uso em um nó j ou em um arco que chega em j
Um caminho de i a j que não contenha definição de x é chamado de “caminho livre de definição”
18
Complexidade Ciclomática
Um nó i possui uma “definição global” de uma variável x se ocorre uma definição de x no nó i e existe um caminho livre de definição de i para algum nó ou para algum arco que contém um c-uso ou um p-uso, respectivamente, da variável x
19
Complexidade Ciclomática
Um c-uso da variável x em um nó j é um “c-uso global” se não houver uma definição de x no nó j precedendo este c-uso; caso contrário, é um “c-uso local”
20
Complexidade Ciclomática
Consideremos o programa identifier: responsável por determinar se um identificador é válido ou não - um identificador válido deve começar com uma letra e conter apenas letras ou dígitos; além disso, deve ter no mínimo 1 e no máximo 6 caracteres de comprimento
É importante observar que o programa identifier contém ao menos um defeito
21
Complexidade Ciclomática
#include<stdio.h>
main (){
/* 1 */ char achar;
/* 1 */ int length, valid_id;
/* 1 */ length = 0;
/* 1 */ valid_id = 1;
/* 1 */ printf("Identificador: ");
/* 1 */ achar = fgetc(stdin);
/* 1 */ valid_id = valid_s(achar);
/* 1 */ if(valid_id){
/* 2 */ length = 1;
/* 2 */ }
/* 3 */ achar = fgetc (stdin);
22
Complexidade Ciclomática
/* 4 */ while(achar != '\n'){
/* 5 */ if(!(valid_f(achar))){
/* 6 */ valid_id = 0;
/* 6 */ }
/* 7 */ length++;
/* 7 */ achar = fgetc (stdin);
/* 7 */ }
/* 8 */ if(valid_id && (length >= 1) && (length < 6)){
/* 9 */ printf ("Valido\n");
/* 9 */ }
/* 10 */ else{
/* 10 */ printf ("Invalid\n");
/* 10 */ }
/* 11 */ }
23
Complexidade Ciclomática
int valid_s(char ch)
/* 1 */ {
/* 1 */ if(((ch >= 'A') && (ch <= 'Z')) || ((ch >= 'a') && (ch <= 'z')))
/* 2 */ {
/* 2 */ return 1;
/* 2 */ }
/* 3 */ else
/* 3 */ {
/* 3 */ return 0;
/* 3 */ }
/* 4 */ }
24
Complexidade Ciclomática
int valid_f(char ch)
/* 1 */ {
/* 1 */ if(((ch >= 'A') && (ch <= 'Z')) || ((ch >= 'a') && (ch <= 'z')) ||
((ch >= '0') && (ch <= '9'))) {
/* 2 */ return 1;
/* 2 */ }
/* 3 */ else{
/* 3 */ return 0;
/* 3 */ }
/* 4 */}
Esse código pode ser encontrado no repl.it
25
Complexidade Ciclomática
Os blocos são numerados e se encontram à esquerda como comentário
Grafo da função main
26
Complexidade Ciclomática
O comando if(valid_id) ilustra um desvio de execução entre os nós do programa
Caso sejam exercitados os comandos internos ao if, tem-se um desvio de execução do nó 1 para o nó 2, representado no grafo pelo arco (1,2)
27
Complexidade Ciclomática
Do contrário, se os comandos internos ao if não forem executados, tem-se um desvio do nó 1 para o nó 3, representado pelo arco (1,3)
De maneira similar, obtêm-se os arcos (2,3),(3,4),(4,5), e assim por diante
28
Complexidade Ciclomática
O caminho (2,3,4,5,6,7) é um caminho simples e livre de laços
O caminho (1,2,3,4,5,7,4, 8,9,11) é um caminho completo
O caminho (1,3,4,8,9) é dito um “caminho não executável”, ou seja, não existe um dado de entrada que leve à execução desse caminho
29
Complexidade Ciclomática
Para executar o caminho (1,3,4,8,9) a variável valid_id tem de ser avaliada como 0 no comando if(valid_id) (nó 1), fazendo com que haja um desvio de execução do nó 1 para o nó 3
Observe que a variável length permanece com seu valor inicial, ou seja, 0
30
Complexidade Ciclomática
Além disso, para que haja um desvio de execução do nó 4 para o nó 8, os comandos internos à estrutura de repetição while (achar !=‘\n’) (nó 4) não podem ser executados
Nesse caso, a variável achar deve receber um ‘\n’ no nó 3
31
Complexidade Ciclomática
Como os valores de valid_id e length são iguais a 0, o comando condicional no nó 8 é avaliado como falso e, consequentemente, não ocorre desvio do nó 8 para o nó 9
Nesse caso, os comandos do nó 9 não são executados
32
Complexidade Ciclomática
Caracteriza-se, assim, que o caminho (1,3,4,8,9) é não executável
De fato, qualquer caminho completo que inclua tal caminho também é considerado não executável
33
Complexidade Ciclomática
O comando length = 0 consiste em uma definição de variável, enquanto os comandos achar !=‘\n’ e length++ correspondem, respectivamente, a um uso predicativo e a um uso computacional de variável (neste caso, seguido de uma redefinição, visto que length++ é equivalente a length = length + 1)
34
Complexidade Ciclomática
35
Complexidade Ciclomática
Os critérios baseados na complexidade utilizam informações sobre a complexidade do programa para derivar os requisitos de teste
Um critério bastante conhecido dessa classe é o critério de McCabe (ou teste de caminho básico), que utiliza a complexidade ciclomática do GFC para derivar os requisitos de teste
36
Complexidade Ciclomática
O critério de McCabe, utiliza uma medida de complexidade de software baseada na representação de fluxo de controle de um programa – a complexidade ciclomática –, foi um dos primeiros critérios estruturais definidos
37
Complexidade Ciclomática
A complexidade ciclomática é uma métrica de software que proporciona uma medida quantitativa da complexidade lógica de um programa
38
Complexidade Ciclomática
Utilizado no contexto do teste de caminho básico, o valor da complexidade ciclomática estabelece o número de caminhos linearmente independentes do conjunto básico de um programa, oferecendo um limite máximo para o número de casos de teste que devem ser derivados a fim de garantir que todas as instruções sejam executadas pelo menos uma vez
39
Complexidade Ciclomática
Um caminho linearmente independente é qualquer caminho do programa que introduza pelo menos um novo conjunto de instruções de processamento ou uma nova condição
40
Complexidade Ciclomática
Quando estabelecido em termos de um GFC, um caminho linearmente independente deve incluir pelo menos um arco que não tenha sido atravessado antes que o caminho seja definido
Assim, cada novo caminho introduz um arco
41
Complexidade Ciclomática
Caminhos linearmente independentes estabelecem um conjunto básico para o GFC
Ou seja, se casos de teste puderem ser projetados a fim de forçar a execução desses caminhos (um conjunto básico), cada instrução do programa terá a garantia de ser executada pelo menos uma vez e cada condição terá sido executada com verdadeiro e falso
42
Complexidade Ciclomática
É importante observar que o conjunto básico não é único; de fato, diferentes conjuntos básicos podem ser derivados para determinado GFC
43
Complexidade Ciclomática
Para saber quantos caminhos devem ser procurados, é necessário calcular a complexidade ciclomática V(G), que pode ser computada destas três maneiras:
1. O número de regiões em um GFC: uma região pode ser informalmente descrita como uma área incluída no plano do grafo; o número de regiões é computado contando-se todas as áreas delimitadas e a área não delimitada fora do grafo
44
Complexidade Ciclomática
2. V(G) = E − N + 2, tal que E é o número de arcos e N é o número de nós do GFC G
3. V(G) = P + 1, tal que P é o número de nós predicativos contido no GFC G
45
Complexidade Ciclomática
O valor da complexidade ciclomática V(G) oferece um limite máximo para o número de caminhos linearmente independentes que constitui o conjunto básico e, consequentemente, um limite máximo do número de casos de teste que deve ser projetado e executado para garantir a cobertura de todas as instruções de programa
46
Complexidade Ciclomática
Uma vez que o número de regiões aumenta com o número de caminhos de decisão e laços, a métrica de McCabe oferece uma medida quantitativa da dificuldade de conduzir os testes e uma indicação da confiabilidade final
47
Complexidade Ciclomática
A Complexidade Ciclomática é o número mínimo de caminhos independentes e livres de loop (chamados de caminhos básicos) que podem, em combinação linear, gerar todos os caminhos possíveis através de um módulo sob teste
48
Complexidade Ciclomática
A complexidade ciclomática é uma métrica útil para previsão dos módulos que têm a tendência de apresentar erros
Ela pode ser usada tanto para o planejamento de teste quanto para projeto de casos de teste
49
Teste Estruturado / Teste do Caminho Básico
50
Complexidade Ciclomática
O teste de caminho básico permite ao projetista de casos de teste derivar uma medida da complexidade lógica de um projeto procedimental e usar essa medida como guia para definir um conjunto base de caminhos de execução
Casos de teste criados para exercitar o conjunto básico executam com certeza todas as instruções de um programa pelo menos uma vez durante o teste
51
Complexidade Ciclomática
Nesse tipo de teste, o analista que projetou o caso de teste verifica a complexidade lógica dos procedimentos que formam conjuntos básicos de caminhos de execução do software
Ele é realizado com caminhos mais básicos, até que todos os caminhos passíveis de serem percorridos pelo software sejam avaliados
52
Complexidade Ciclomática
Um bom exemplo disso seria o testador incluir um registro no banco de dados, alterar esse registro utilizando outra parte da interface, executar um relatório em que esse registro apareça e ainda tentar excluí-lo — tudo isso sem utilizar a interface do software, apenas seguindo os passos dentro da estrutura interna
53
Complexidade Ciclomática
Teste estruturado se baseia no trabalho de McCabe acerca de Complexidade Ciclomática
Ele usa uma análise da topologia do grafo de fluxo de controle para identificar casos de teste
54
Complexidade Ciclomática
55
Complexidade Ciclomática
As setas no grafo de fluxo, chamadas de arestas ou ligações, representam fluxo de controle
Uma aresta deve terminar em um nó, mesmo que esse nó não represente qualquer comando procedural
56
Complexidade Ciclomática
As áreas limitadas por arestas e nós são chamadas de regiões
Ao contarmos as regiões, incluímos a área fora do grafo como uma região
57
Complexidade Ciclomática
Quando condições compostas são encontradas em um projeto procedimental, a geração de um grafo de fluxo torna-se ligeiramente mais complicada
Uma condição composta ocorre quando um ou mais operadores booleanos (OR, AND, NAND, NOR lógicos) estão presentes em um comando condicional
58
Complexidade Ciclomática
59
Complexidade Ciclomática
Note que é criado um nó separado para cada uma das condições a e b no comando SE a OU b
Cada nó contendo uma condição é chamado de nó predicado e é caracterizado por duas ou mais arestas saindo dele
60
Caminhos de programa independentes
61
Complexidade Ciclomática
Um caminho independente é qualquer caminho através do programa que introduz pelo menos um novo conjunto de comandos de processamento ou uma nova condição
Quando definido em termos de um grafo de fluxo, um caminho independente deve incluir pelo menos uma aresta que não tenha sido atravessada antes de o caminho ser definido
62
Complexidade Ciclomática
Conjunto base: se testes podem ser projetados para forçar a execução desses caminhos, cada comando do programa terá sido executado com certeza pelo menos uma vez e cada condição terá sido executada em seus lados verdadeiro e falso
63
Complexidade Ciclomática
Deve-se notar que o conjunto base não é único
De fato, vários conjuntos base diferentes podem ser derivados para um dado projeto procedimental
64
Complexidade Ciclomática
Como sabemos quantos caminhos procurar?
O cálculo da complexidade ciclomática fornece a resposta
65
Complexidade Ciclomática
Quando usada no contexto do método de teste de caminho básico, o valor computado para a complexidade ciclomática define o número de caminhos independentes no conjunto base de um programa, fornecendo um limite superior para a quantidade de testes que devem ser realizados para garantir que todos os comandos tenham sido executados pelo menos uma vez
66
Complexidade Ciclomática
A complexidade ciclomática fornece o limite superior no número de casos de teste que precisam ser executados para garantir que cada comando do programa tenha sido executado pelo menos uma vez
67
Complexidade Ciclomática
E.g. Consideremos o grafo a seguir
A complexidade ciclomática pode ser calculada usando cada um dos algoritmos já mencionados
68
1
2,3
10
6
9
7
8
11
4,5
Complexidade Ciclomática
1. O grafo de fluxo tem quatro regiões
2. V(G) = 11 arestas – 9 nós + 2 = 4
3. V(G) = 3 nós predicados + 1 = 4
Portanto, a complexidade ciclomática para o grafo de fluxo é 4
69
Complexidade Ciclomática
E o mais importante, o valor para V(G) fornece um limite superior para o número de caminhos independentes que podem formar o conjunto base e, como consequência, um limite superior sobre o número de testes que devem ser projetados e executados para garantir a abrangência de todos os comandos do programa
70
Derivação de casos de teste
71
“O foguete Ariane 5 explodiu no lançamento simplesmente por um defeito de software (uma falha) envolvendo a conversão de um valor em ponto flutuante de 64 bits em um inteiro de 16 bits. O foguete e seus quatro satélites não estavam segurados e valiam $500 milhões. Testes de caminho [que exercitam o caminho de conversão] teriam descoberto o defeito, mas foram vetados por razões de orçamento.”
Notícia de um jornal
72
Complexidade Ciclomática
O processo de teste estruturado consiste dos seguintes passos:
73
Complexidade Ciclomática
74
Complexidade Ciclomática
Consideremos o seguinte grafo de fluxo de controle
75
Complexidade Ciclomática
McCabe define a Complexidade Ciclomática (C) de um grafo como
C = arestas - nodos + 2
76
Complexidade Ciclomática
As arestas são as setas e os nodos são as bolas no grafo
Assim, nosso exemplo tem
24 arestas e 19 nodos
Assim, a Complexidade Ciclomática: C = 24 - 19 + 2 = 7
77
Complexidade Ciclomática
Em alguns casos, esta computação pode ser simplificada
Se todas as decisões no grafo são binárias (elas têm exatamente duas arestas fluindo para fora) e há p decisões binárias, então
C = p + 1
78
Complexidade Ciclomática
Em termos de grafo de fluxo de controle, cada caminho básico atravessa ao menos uma aresta que nenhum outro caminho atravessa
79
Complexidade Ciclomática
A técnica de teste estruturado de McCabe exige a criação de C casos de teste, um para cada caminho básico
A criação e execução de C casos de teste, com base nos caminhos básicos, garante a cobertura de branch (ramificação) e de statements (instruções)
80
Complexidade Ciclomática
Um processo para criar um conjunto de caminhos básicos é dado por McCabe
1. Escolha um caminho 'base'
Este caminho deve ser um caminho razoavelmente típico de execução ao invés de um caminho de processamento de exceção
81
Complexidade Ciclomática
A melhor escolha seria o caminho mais importante na visão do testador
O caminho escolhido foi
ABDEGKMQS
82
Complexidade Ciclomática
2. Para escolher o próximo caminho, mude o resultado da primeira decisão ao longo do base ao passo que mantém o número máximo de outras decisões as mesmas que no caminho base
83
Complexidade Ciclomática
O segundo caminho básico é ACDEGKMQS
84
Complexidade Ciclomática
3. Para gerar o terceiro caminho, comece novamente com o caminho base, mas varie a segunda decisão em vez da primeira
85
Complexidade Ciclomática
O terceiro caminho básico é ABDFILORS
86
Complexidade Ciclomática
4. Para gerar o quarto caminho, comece novamente com o caminho base, mas varie a terceira decisão em vez da segunda
Continue variando cada decisão, uma por uma, até que a parte inferior do grafo seja alcançada
87
Complexidade Ciclomática
O quarto caminho básico é ABDEHKMQS
88
Complexidade Ciclomática
O quinto caminho básico é ABDEGKNQS
89
Complexidade Ciclomática
5. Agora que todas as decisões ao longo do caminho base foram invertidas, passamos para o segundo caminho, invertendo suas decisões, uma por uma
Esse padrão é continuado até que o conjunto de caminhos básicos seja concluído
90
Complexidade Ciclomática
O sexto caminho básico é ACDFJLORS
91
Complexidade Ciclomática
O sétimo caminho básico ACDFILPRS
92
Complexidade Ciclomática
Assim, o conjunto de caminhos básicos para este grafo é
ABDEGKMQS
ACDEGKMQS
ABDFILORS
ABDEHKMQS
ABDEGKNQS
ACDFJLORS
ACDFILPRS
93
Exemplo
94
Complexidade Ciclomática
Procedimento average
average, apesar de ser um algoritmo simples, contém condições compostas e ciclos
95
Complexidade Ciclomática
Os seguintes passos podem ser aplicados para derivar o conjunto base
1. Usando o projeto ou o código como base, desenhe o grafo de fluxo correspondente
É criado um grafo de fluxo enumerando-se os comandos que serão mapeados por nós correspondentes do grafo de fluxo
96
Complexidade Ciclomática
2. Determine a complexidade ciclomática do diagrama de fluxo resultante
V(G) = 17 arestas – 13 nós + 2 = 6
97
Complexidade Ciclomática
3. Determine um conjunto base de caminhos linearmente independentes
O valor de V(G) fornece o limite superior no número de caminhos linearmente independentes através da estrutura de controle do programa
98
Complexidade Ciclomática
No caso do procedimento average, esperamos especificar seis caminhos:
Caminho 1: 1-2-10-11-13
Caminho 2: 1-2-10-12-13
Caminho 3: 1-2-3-10-11-13
Caminho 4: 1-2-3-4-5-8-9-2-...
Caminho 5: 1-2-3-4-5-6-8-9-2-...
Caminho 6: 1-2-3-4-5-6-7-8-9-2-...
99
Complexidade Ciclomática
A reticência (...) após os caminhos 4, 5 e 6 indica que qualquer caminho através do resto da estrutura de controle é aceitável
Muitas vezes compensa identificar nós predicados como um auxílio na dedução de casos de teste
Nesse caso, os nós 2, 3, 5, 6 e 10 são nós predicados
100
Complexidade Ciclomática
4. Prepare casos de teste que vão forçar a execução de cada caminho do conjunto base
Os dados devem ser escolhidos de forma que as condições nos nós predicados sejam definidas de forma apropriada à medida que cada caminho é testado
101
Complexidade Ciclomática
Cada caso de teste é executado e comparado com os resultados esperados
Depois que todos os casos de teste tiverem sido completados, o testador pode ter a certeza de que todos os comandos do programa foram executados pelo menos uma vez
102
Complexidade Ciclomática
É importante notar que alguns caminhos independentes (por exemplo, caminho 1 em nosso exemplo) não podem ser testados de forma individual
Isso significa que a combinação de dados necessária para percorrer o caminho não pode ser conseguida no fluxo normal do programa
103
Complexidade Ciclomática
Nesses casos, esses caminhos são testados como parte de outro teste de caminho
104
Referências
105
Referências
COPELAND, L. A Practitioner's Guide to Software Test Design
Cap. 10
DELAMARO, M. Introdução ao Teste de Software
Cap. 4
106
Referências
JORGENSEN, P. C. Software Testing: A Craftsman's Approach.
Cap. 8
PRESSMAN, R. S. Engenharia de Software: Uma abordagem profissional.
Cap. 18.4
107
Veja mais...
108
Veja mais...
109
Complexidade Ciclomática
Prof. Alysson Filgueira Milanez
alysson.milanez@ufersa.edu.br
Teste de Software