SAST 2014 - Instituto de Computação

Transcrição

Congresso Brasileiro de Software: Teoria e Prática
28 de setembro a 03 de outubro de 2014 – Maceió/AL
8th Brazilian Workshop on Systematic and Automated Software Testing
SAST 2014
Anais
SAST
Volume 02
ISSN 2178-6097
Anais
SAST 2014
8th Brazilian Workshop on Systematic and Automated
Software Testing
COORDENADORES DO COMITÊ DE PROGRAMA
Valdivino Santiago Júnior - Instituto Nacional de Pesquisas Espaciais (INPE)
Wilkerson Andrade - Universidade Federal de Campina Grande (UFCG)
COORDENAÇÃO DO CBSOFT 2014
Baldoino Fonseca - Universidade Federal de Alagoas (UFAL)
Leandro Dias da Silva - Universidade Federal de Alagoas (UFAL)
Márcio Ribeiro - Universidade Federal de Alagoas (UFAL)
REALIZAÇÃO
Universidade Federal de Alagoas (UFAL)
Instituto de Computação (IC/UFAL)
PROMOÇÃO
Sociedade Brasileira de Computação (SBC)
PATROCÍNIO
CAPES, CNPq, INES, Google
APOIO
Instituto Federal de Alagoas, Aloo Telecom, Springer, Secretaria de Estado do Turismo
AL, Maceió Convention & Visitors Bureau, Centro Universitário CESMAC e Mix Cópia
2
SAST
PROCEEDINGS
Volume 02
ISSN 2178-6097
SAST 2014
8th Brazilian Workshop on Systematic and Automated
Software Testing
PROGRAM CHAIRS
CBSOFT 2014 GENERAL CHAIRS
ORGANIZATION
Universidade Federal de Alagoas (UFAL)
Instituto de Computação (IC/UFAL)
PROMOTION
Sociedade Brasileira de Computação (SBC)
SPONSORS
CAPES, CNPq, INES, Google
SUPPORT
Instituto Federal de Alagoas, Aloo Telecom, Springer, Secretaria de Estado do Turismo AL, Maceió Convention & Visitors Bureau, Centro Universitário CESMAC and Mix Cópia
3
SAST
Autorizo a reprodução parcial ou total desta obra, para fins acadêmicos, desde que citada a fonte
4
SAST
Apresentação
Teste de Software é uma das técnicas de Verificação e Validação mais
populares atualmente e, se for efetivamente utilizada, pode prover importantes
evidências sobre a qualidade de um produto de software. As pesquisas nessa área têm
aumentado nos últimos anos e casos de sucesso da indústria têm sido amplamente
divulgados.
O Brazilian Workshop on Systematic and Automated Software Testing (SAST –
Workshop Brasileiro de Testes de Software Automatizados e Sistemáticos) é um dos
mais importantes eventos científicos da área de teste no Brasil. Seu principal objetivo é
consolidar um fórum que reúna as comunidades de pesquisa e da indústria para
discutir melhorias na sistematização e automação de teste de software.
Nessa 8ª edição, o SAST ocorre em conjunto com o CBSoft – Congresso
Brasileiro de Software: Teoria e Prática, na cidade de Maceió – AL. Em 2014, o SAST
está sendo organizado em conjunto pela Universidade Federal de Campina Grande,
Campina Grande – PB, e pelo Instituto Nacional de Pesquisas Espaciais, São José dos
Campos – SP.
Seguindo o formato de anos anteriores, o programa técnico do SAST é
composto por: (i) uma palestra de pesquisa; (ii) uma palestra da indústria; e (iii)
sessões para apresentações de trabalhos, com artigos técnicos e relatos de
experiência, nas quais são apresentadas, respectivamente, contribuições para o estado
da arte da área e exemplos da aplicação prática de teste de software na indústria.
Neste ano, foram submetidos 22 trabalhos, sendo 18 artigos técnicos e 4
relatos de experiência. Os trabalhos foram selecionados por meio de um processo de
revisão rigoroso onde cada trabalho foi revisto por 3 membros do comitê de programa,
contando com a colaboração de revisores nacionais e internacionais. Em seguida,
houve um período de discussão para que os revisores pudessem confrontar suas
revisões sobre os artigos. Após a fase de discussão, 12 trabalhos foram selecionados,
sendo 9 artigos técnicos e 3 relatos de experiência (1 artigo técnico foi aceito, porém
com a condição de ser reformulado como um relato de experiência). A taxa de
aceitação de artigos do SAST 2014 foi de 54,6%, o que está em conformidade com a
média da taxa de aceitação de artigos de todas as edições anteriores (2007 a 2013) do
workshop que é de 55,3%.
Agradecemos a todos os membros do comitê de programa que permitiram que
o processo de revisão fosse realizado de maneira tão adequada. Agradecemos,
também, a Patrícia Machado e Roberta Coelho pelas valiosas dicas e
compartilhamento da experiência de organização de edições anteriores do workshop.
Por fim, agradecemos aos organizadores do CBSoft 2014 pela infraestrutura
disponibilizada e pela oportunidade oferecida.
Desejamos um excelente workshop a todos e esperamos que o SAST 2014
possa contribuir para ampliação e consolidação da área de Teste de Software no Brasil.
Wilkerson de Lucena Andrade (DSC/UFCG)
Valdivino Alexandre de Santiago Júnior (LAC/INPE)
5
SAST
Foreword
Testing is one of the most popular verification and validation techniques used
today and if it is used in an effective way, it can provide important evidences of quality
and reliability of a product. Research in this area has steadily increased in the last years
and industrial success cases have been openly reported.
The Brazilian Workshop on Systematic and Automated Software Testing (SAST)
is one of the most important scientific events about software testing in Brazil. His main
goal is to build a forum that brings the research and industry communities together to
discuss improvements in software testing systematization and automation.
In this 8th edition, SAST will be co-located with the Brazilian Conference on
Software: Theory and Practice (CBSoft), and will happen in Maceió – AL. In 2014, the
SAST workshop is being organized jointly by Federal University of Campina Grande
(UFCG), Campina Grande – PB, and National Institute For Space Research (INPE), São
José dos Campos – SP.
Following the model of previous years, the technical program of SAST consists
of: (i) a research talk; (ii) an industrial talk; and (iii) sessions for paper presentations,
with technical articles and experience reports, which are presented in contributions to
the state of the art and examples of practical application of software testing in
industry, respectively.
This year, 22 papers were submitted of which 18 were technical papers and 4
were experience reports. Studies were selected through a rigorous review process
where each paper was reviewed by three members of the program committee, with
the cooperation of national and international reviewers. Then there was a discussion
period so that reviewers could confront their reviews about the articles. After the
discussion phase, 12 papers were selected, 9 as technical papers 9 and 3 as experience
reports (1 technical paper was accepted, but with the condition of being reformulated
as an experience report). The paper's acceptance rate of SAST 2014 was 54.6%, which
is in line with the average acceptance rate of papers from all previous editions (20072013) of the workshop which is 55.3%.
We thank all members of the program committee for their interesting
comments and suggestions for improving the quality of the submitted papers. We also
thank Patricia Machado and Roberta Coelho for the valuable tips and sharing the
experience of organization of previous editions of the workshop. Finally, we thank the
organizers of CBSoft 2014 for the available infrastructure and the opportunity offered.
We wish everyone a great workshop and we hope that SAST 2014 will
contribute to the expansion and consolidation of the area of Software Testing in Brazil.
Wilkerson de Lucena Andrade (DSC/UFCG)
Valdivino Alexandre de Santiago Júnior (LAC/INPE)
6
SAST
Comitês Técnicos / Program Committee
Comitê do programa / Program Committee
Adenilso Simão - Universidade de São Paulo (USP)
Alexandre Petrenko - CRIM, Canada
Anamaria Martins Moreira - Universidade Federal do Rio de Janeiro (UFRJ)
Arilo Dias Neto - Universidade Federal do Amazonas (UFAM)
Arndt von Staa - Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio)
Auri Vincenzi - Universidade Federal de Goiás (UFG)
Érica Souza - Universidade Tecnológica Federal do Paraná
Edmundo Spoto - Universidade Federal de Goiás (UFG)
Eduardo Guerra - Instituto Nacional de Pesquisas Espaciais (INPE)
Eliane Martins - Universidade Estadual de Campinas (UNICAMP)
Elisa Yumi Nakagawa - Universidade de São Paulo (USP)
Elisângela Vieira - Alcatel-Lucent, FranceINPE
Ellen Francine Barbosa - Universidade de São Paulo (USP)
Fabiano Ferrari - Universidade Federal de São Carlos (UFSCar)
Fábio Silveira - Universidade Federal de São Paulo (UNIFESP)
Fatima Mattiello-Francisco - Instituto Nacional de Pesquisas Espaciais (INPE)
Jorge Figueiredo - Universidade Federal de Campina Grande (UFCG)
Juliano Iyoda - Universidade Federal de Pernambuco (UFPE)
Mário Jino - Universidade Estadual de Campinas (UNICAMP)
Maximiliano Cristiá - CIFASIS and UNR, Argentina
Patrícia Machado - Universidade Federal de Campina Grande (UFCG)
Plínio Leitão-Júnior - Universidade Federal de Goiás (UFG)
Sandra Fabbri - Universidade Federal de São Carlos (UFScar)
Silvia Vergilio - Universidade Federal do Paraná (UFPR)
Simone Souza - Universidade de São Paulo (USP)
Sudipto Ghosh - Colorado State University, United States of America
Revisores Adicionais / Additinal Reviewers
Alan Moraes - Universidade Federal da Paraíba (UFPB)
Arnaud Dury - CRIM, Canada
Ernesto Matos - Universidade Federal do Rio Grande do Norte (UFRN)
Lucas Oliveira - Universidade de São Paulo (USP)
Luciana Santos - Instituto Nacional de Pesquisas Espaciais (INPE)
Omer Nguena-Timo - CRIM, Canada
Valdemar Graciano Neto - Universidade Federal de Goiás (UFG)
7
SAST
Comitê organizador / Organizing Committee
COORDENAÇÃO GERAL
COMITÊ LOCAL
Adilson Santos - Centro Universitário Cesmac (CESMAC)
Elvys Soares - Instituto Federal de Alagoas (IFAL)
Francisco Dalton Barbosa Dias - Universidade Federal de Alagoas (UFAL)
COORDENADORES DO SAST 2014
8
SAST
Índice / Table of Contents
Technical Papers
Coverage Criteria for Logical Specifications
Maximiliano Cristiá, Joaquín Cuenca, Claudia Frydman
11
Towards the Establishment of a Sufficient Set of Mutation
Operators for AspectJ Programs
Jésus Thiago Sousa Lacerda, Fabiano Cutigi Ferrari
21
Uma Revisão Sistemática em Teste de Segurança Baseado em
Modelos
Carlos Diego Nascimento Damasceno , Márcio Eduardo Delamaro,
Adenilso da Silva Simão
31
Heurísticas para seleção da população inicial de
algoritmos de teste baseado em busca para software
controlador de veículos autônomos
Vânia de Oliveira Neves, Márcio Eduardo Delamaro, Paulo Cesar Masiero
41
A Systematic Mapping on Model Based Testing applied to
Web Systems
Silvia Regina Assis Meireles, Arilo Claudio Dias-Neto
51
Uma Investigação Inicial Sobre a Correlação entre Defeitos de
Software Simulados por Mutantes e Avisos Relatados por uma
Ferramenta de Análise Estática
Cláudio Antônio de Araújo, Márcio Eduardo Delamaro,
João Carlos da Silva, Auri Marcelo Rizzo Vincenzi
61
Geração automática de Dados de Teste para Programas
Concorrentes com uso de Meta-heurísticas
José D. P. Silva, Simone R. S. Souza, Paulo S. L. Souza
71
RTS Quality: Ferramenta de Análise Automatizada de
Técnicas de Seleção de Testes de Regressão Baseada em
Mineração de Repositórios de Software
João Guedes, Uirá Kulesza, Roberta Coelho, Eduardo Guerra, Lyrene
Fernandes, Felipe Alves
81
LoTuS-TCG: Uma ferramenta para geração e seleção de casos
de teste funcionais e estatísticos
Laryssa Lima Muniz, Ubiratan S. C. Netto, Paulo Henrique M. Maia
91
9
SAST
Experience Reports
Integrando Teste Baseado em Modelos no Desenvolvimento de
uma Aplicação Industrial: Benefícios e Desafios
Dalton Jorge, Patrícia D. L. Machado, Francisco G. Oliveira Neto,
Ana Emília V. B. Coutinho, João F. S. Ouriques
101
Automatização de Testes Funcionais em Dispositivos Móveis
Utilizando a Técnica BDD
Rafael Chiavegatto, Lidiane Silva, Maryane Pinheiro, Auri Marcelo Rizzo
Vincenzi
107
The Role of Software Testing on Modernizing a Balloon
Ground Station
Fátima Mattiello-Francisco, Mariam Gomez, William K. Ariyoshi, Fernando
Aranha, Marcelo Essado
113
10
SAST
Coverage Criteria for Logical Specifications
Maximiliano Cristiá1 , Joaquı́n Cuenca1 , Claudia Frydman2
1
CIFASIS and UNR, Rosario, Argentina
[email protected], [email protected]
2
LSIS-CIFASIS, Marseille, France
[email protected]
Abstract. Model-based testing (MBT) studies how to generate test cases from
a model of the system under test (SUT). Many MBT methods rely on building
an automaton from the model and then they generate test cases by covering the
automaton with different path coverage criteria. However, if a model of the SUT
is a logical formula over some complex mathematical theories (such as the Z
notation) it may be more natural or intuitive to apply coverage criteria directly
over the formula. In this paper we propose a set of coverage criteria for logical specifications based on domain partition. We call them testing strategies.
Testing strategies play a similar role to path- or data-based coverage criteria.
Furthermore, we show a partial order of testing strategies as is done in structural testing. We also describe an implementation of testing strategies for the
Test Template Framework, which is a MBT method for the Z notation.
1. Introduction
Testing is the predominant verification technique used in the software industry. At the
same time, testing is a time-consuming activity that needs lot of resources to produce
good results. Since many years ago the testing community works on the automation of
the testing process as a means to reduce its costs and improve its efficiency. Model-based
testing (MBT) is a collection of testing methods that aims at automatically generating test
cases from the analysis of a model of the system under test (SUT) [22]. MBT methods
have achieved impressive theoretical and practical results in recent years such as [13, 8,
21, 15, 23], to name just a few.
Some MBT methods generate test cases by first building an automaton from the
model of the SUT and then covering the automaton with different criteria. For example, ProTest [17] is a test case generation tool based on B machines [1]. It first writes
each given machine operation into DNF and then it builds a finite state machine (FSM)
“whose initial node is the initial state of the B machine. Each node in the FSM represents
a possible machine state and each edge is labeled by an operation”. Finally, ProTest “traverses the FSM to generate a set of operation sequences such that each operation in the
FSM appears in the generated sequences at least once”. As another example consider the
method proposed by Hierons et al. [11]. In this case a Z specification [18] is accompanied by a Statechart [10] that represents all the possible execution paths of the operations
defined in the Z specification. Then, some test sequence generation methods, based on
FSM test techniques, are defined. These criteria are based on covering the paths of the
Statechart in different ways. Since the Statechart is built from the Z specification then the
test sequences will cover the Z specification.
11
SAST
As can be seen, even when the model of the SUT is (essentially) a logical formula
(i.e. a B machine or a Z operation) test cases are generated by covering the paths of an
automaton derived from the model, and not by covering the structure of the formula. In
a sense, there is an assumption that the logical formula is covered by covering the automaton generated from it. In this paper we would like to propose an alternative method
that generates test cases by applying criteria that cover directly the logical formula. These
criteria are defined by conveniently assembling together rules that indicate how to partition an input domain. Our criteria do not need an automaton because they analyze the
structure, semantics and types of a logical formula. These criteria can be organized in a
partial order to help users to select the most appropriate for each project.
We also show how these criteria have been implemented in FASTEST [5], a tool
that supports the Test Template Framework (TTF) [20] which, in turn, is a MBT method
for the Z notation.
The paper starts by introducing the concept of domain partition in Section 2. Testing strategies are introduced in Section 3 where they are accommodated in partial order
and a prototype implementation is shown. We also discuss the contribution of this paper
along with its conclusions in Section 4.
2. Domain Partition
In this section we show some rules for domain partition that are already available. These
rules are later combined to define criteria that provide different levels of coverage of the
logical specification to which they are applied.
Consider the following logical formula as an example of some specification:
(s? ∈ dom st ∧ st0 = {s?} −
C st) ∨ (s? ∈
/ dom st ∧ st0 = st)
(1)
where st : SYM →
7 Z is a partial function; SYM is a given, underspecified set; s? : SYM
is an input variable; st is a state variable; st0 represents the value of st in the next state;
and −
C is a relational operator called domain anti-restriction. This formula formalizes the
elimination of a symbol (s?) from a symbol table (st) that associates elements of SYM with
integer numbers. In other words, (1) represents a state transition of some state machine.
If formula (1) is the specification of some implementation, then the MBT theory
says that engineers should analyze (1), instead of its implementation, to generate test
cases to test the implementation. Note that it would be difficult to build an automaton
from (1), as suggested by some MBT methods [17, 12, 11], because we have only one
transition. On the other hand, the implementation of (1) is not trivial because, for instance,
it seldom will be based on sets and set operators (such as −
C). Sets and set operators will
probably be implemented as arrays or linked lists and operations over them. Hence, the
implementation of (1) is worth to be tested.
Following the foundation of structural testing we may ask to ourselves, how (1)
can be covered? That is, how can we be sure that all aspects of (1) are going to be tested?
An answer given by some methods is to use domain partition [20, 2]. First, the input
domain or space of the specification is defined, then it is partitioned in subsets called
test conditions and finally one element of each test condition is taken as a test case. For
example, the input space of (1) is defined as:
IS = {st : SYM →
7 Z; s? : SYM}
(2)
12
SAST
R=∅
R 6= ∅ ∧ S = ∅
R 6= ∅ ∧ S = dom R
R 6= ∅ ∧ S 6= ∅ ∧ S ⊂ dom R
R 6= ∅ ∧ S 6= ∅ ∧ S ∩ dom R = ∅
R 6= ∅ ∧ S 6= ∅ ∧ S ∩ dom R 6= ∅ ∧ dom R ⊂ S
R 6= ∅ ∧ S 6= ∅ ∧ S ∩ dom R 6= ∅ ∧ ¬ (dom R ⊆ S) ∧ ¬ (S ⊆ dom R)
Figure 1. Standard partition for S −
CR
and we can partition it by taking the precondition of each disjunct in (1):
IS1 = {IS | s? ∈ dom st}
IS2 = {IS | s? ∈
/ dom st}
(3)
(4)
With this partition we can define two test cases:
TC1 = {IS1 | st = {(s1 , 3)} ∧ s? = s1 }
TC2 = {IS2 | st = ∅ ∧ s? = s1 }
(5)
(6)
However, are these test cases enough? Do they cover all the specification? Probably not because, for example, there is no test case removing an ordered pair from st when
it has more than one element. So, if st is implemented as, say, a linked list these test
cases will not test whether the iteration over the list is well implemented or not. Is there
something in (1) that indicates to us that this (and possibly others) test case is missing?
Yes, it is. The iteration over the (possible) list implementing st is specified by both the −
C
and dom operators, and we have not used them to generate test cases.
In this example we use −
C to guide the partitioning process. In order to do that
− as shown in Figure 1. Then, we can
we can define a so-called standard partition for C
substitute R by st and S by {s?} and use this to partition IS1 as follows:
IS11 ={IS1 | st = ∅}
(7)
IS12
IS13
IS14
IS15
IS16
IS17
={IS1 | st 6= ∅ ∧ {s?} = ∅}
(8)
={IS1 | st 6= ∅ ∧ {s?} = dom st}
(9)
={IS1 | st 6= ∅ ∧ {s?} =
6 ∅ ∧ {s?} ⊂ dom st}
(10)
={IS1 | st 6= ∅ ∧ {s?} =
6 ∅ ∧ {s?} ∩ dom st = ∅}
(11)
={IS1 | st 6= ∅ ∧ {s?} ∩ dom st 6= ∅ ∧ dom st ⊂ {s?}}
(12)
={IS1 | st 6= ∅ ∧ {s?} ∩ dom st 6= ∅ ∧ ¬ dom st ⊆ {s?}
∧ ¬ {s?} ⊆ dom st}
(13)
Note that now a test case derived from IS14 will test whether removing an ordered
pair from a symbol table containing more than one element is correct or not, which is the
missing test case analyzed above. Also observe that s ∈ dom st is implicitly conjoined to
every predicate of (7)-(13).
13
SAST
Surely more test cases are needed to test the implementation of (1) but we think
we have make it clear that logical specifications contain enough information as to derive
a good test case set without necessarily resorting to an automaton.
2.1. More Partitioning Rules
Free Types (FT) helps to partition an input domain when variables whose type is enumerated are used. If x is a variable of an enumerated type, T, FT generates test conditions
whose characteristic predicates are of the form x = val for each val ∈ T. In this way,
the FT guarantees that the implementation will be exercised on all these values, which
are usually part of conditional expressions and represent important states or operational
conditions of the system.
Numeric Ranges (NR) waits for an arithmetic expression, expr, and an ordered
list of numbers, n1 , . . . nk , and generates the following partition: expr < n1 , expr = n1 ,
n1 < expr < n2 , . . . , expr = ni , ni < expr < ni+1 , expr = ni+1 , . . . , expr < nk ,
expr = nk and nk < expr. NR is very useful, for instance, to test how programs behaves
when numeric variables reach or go beyond their implementation limits. For example, in
a C program a variable of type short can assume values in the range [−32768, 32767].
So, it would be reasonable to test the program with values less than, equal and greater
than −32768 and 32767 for each input or state variable of type short. If one of such
variables is x, likely, it was abstracted at the Z specification as an expression of type Z.
For instance, a potential C implementation of the symbol table described in the previous
section might be as follows: st can be a simply-linked list of nodes defined as:
struct st_node {char* sym; short val; struct st_node* nxt}
Therefore, if one wants to test the behavior of the program when a sym has a val
in the limits of the range for short, then the following list of values can be used
[−32768, 32767] to test the expression st(s?). In this case NR would generate, for example, st(s?) < −32768 as a test condition.
In Set Extension (ISE) applies to specifications including preconditions of the
form expr ∈ {expr1 , . . . , exprn }. In this case, it generates n + 1 test conditions such
that expr = expri , for i in 1 . . n, and expr ∈
/ {expr1 , . . . , exprn } are their characteristic
predicates.
3. A Partial Order of Testing Strategies
Although domain partition is not a very complex activity, engineers need to analyze the
specification, to select some partitioning rules and to decide what expressions, operators,
variables, etc. are going to be used when these rules are applied. Besides, engineers
working with domain partition do not have criteria that tell them “how much” the SUT is
going to be tested. So far, they only have a set of unrelated partitioning techniques. Our
proposal in this regard is to define so-called testing strategies. A testing strategy uses one
or more partitioning rules in such a way that some significant part of the specification is
covered. In this sense, testing strategies are (logic-)specification-based covering criteria.
Having the seminal work of Rapps and Weyuker [16] as an inspiration, we organized the strategies according to a partial order as is depicted in Figure 2. The strategies
closer to the bottom of the graph are those that produce a better coverage and those closer
to the root produce a worse coverage. Informally, the strategies are as follows:
14
SAST
basic-functions
some-arithmetic
all-arithmetic
integers
sets
sets-with-integers
some-enumerations
all-enumerations
some-functions
all-functions
full-coverage
Figure 2. Testing strategies are partially ordered
•
•
•
•
•
•
•
•
•
•
•
BASIC - FUNCTIONS
applies only disjunctive normal form (DNF) so it covers the
logical structure of the specification. Since all the other strategies are stronger
than this one we will not mention the logical coverage unless necessary.
SOME - ENUMERATIONS covers all enumerated types. In this way it guarantees that
sensible values declared in enumerated types will all be exercised at least once.
ALL - ENUMERATIONS is a stronger form of SOME - ENUMERATIONS since it not
only considers enumerated types but also all extensional sets defined in the specification.
INTEGERS instead of tackling enumerations it looks for integer overflows by covering all the integer expressions of the specification. It requires at least five test
cases for each integer expression by applying NR.
SOME - ARITHMETIC covers the arithmetic operators with the defined standard partitions.
ALL - ARITHMETIC puts together INTEGERS and SOME - ARITHMETIC .
SETS covers all the set operators with the defined standard partitions.
SETS - WITH - INTEGERS puts together INTEGERS and SETS .
SOME - FUNCTIONS combines SETS and SOME - ENUMERATIONS , thus covering
some interesting values (i.e. constants of enumerations) and all the set operators.
ALL - FUNCTIONS combines SETS , SOME - ARITHMETIC and SOME - ENUMERATIO NS covering in this way the essential elements appearing in the specification.
FULL COVERAGE combines ALL - FUNCTIONS, INTEGERS and ALL - ENUMERA TIONS .
Table 1 lists the set of domain partition rules that are applied for each strategy.
Note that, due to the way domain partition is performed (i.e. by logical conjunction, see
Section 2), it is not relevant the order in which rules are applied. This also explains the
partial order used to build the graph of Figure 2. In effect, if S1 and S2 are two testing
strategies such that there is an arrow pointing from S1 to S2 , then S2 will produce at least
the same set of test conditions than S1 . This is so because all the domain partition rules
that are applied by S1 are also applied by S2 plus some more. In general, these extra
15
SAST
Strategy
Rules
BASIC - FUNCTIONS
SOME - ENUMERATIONS
ALL - ENUMERATIONS
INTEGERS
SOME - ARITHMETIC
ALL - ARITHMETIC
SETS
SETS - WITH - INTEGERS
SOME - FUNCTIONS
ALL - FUNCTIONS
FULL - COVERAGE
DNF
DNF, FT
DNF, FT, ISE
DNF, NR
DNF, SP over arithmetic operators
DNF, NR, SP over arithmetic operators
DNF, SP over set and relational operators
DNF, NR, SP over set and relational operators
DNF, FT, SP over set and relational operators
DNF, FT, SP
DNF, FT, SP, NR, ISE
Table 1. Domain partition rules used in testing strategies
domain partition rules not necessarily produce new test conditions although they will
produce them in many cases. For example, ALL FUNCTIONS will not produce different
results than SETS if there are no variables of enumerated types; but if there are, then it
will produce more test conditions.
When we partitioned the input space declared in (2) we applied the standard partition of −
C only to IS1 , and not to IS2 . The reason to proceed in this way is that it is unlikely
that an error in the implementation of −
C can be revealed when the symbol to be removed
is not in the symbol table (i.e. IS2 ). In effect, a possible pseudo-code implementation of
(1) might be:
if s? is an element of the symbol table
then remove s? from st
where “s? is an element of the symbol table” is the implementation of s? ∈ dom st and
“remove s? from st” is the implementation of s? −
C st, which may entail several lines
of code depending on the data structure defined to hold the symbol table. Note that if
s? ∈
/ dom st nothing is done. Therefore, the implementation of s? −
C st will be tested only
if s? ∈ dom st, so it makes no sense to exercise the implementation in different ways
when s? ∈
/ dom st. This is equivalent to not partition IS2 .
In summary, testing strategies will produce good coverage with a minimum number of test cases if domain partition is applied only to some test specifications. Then every
testing strategy defined above applies domain partition as follows:
• Consider that SP is applied to the expression α β, where is any Z operator
and α and β are two subexpressions. If α β is part of the precondition of the
operation, then SP is applied to all test conditions where some variable in α or β
is present. If α β is part of the postcondition, then SP is applied to all test conditions whose predicates imply the precondition that leads to that postcondition.
• FT and NR are applied to all test conditions where the variable or expression being
considered is present.
• ISE is applied to all test conditions where any of expr, expr1 , . . . , exprn is present.
16
SAST
3.1. Testing Strategies in Practice
In this section we show how we have implemented in FASTEST the concept of testing
strategy. FASTEST [5] is a MBT tool providing support for the Test Template Framework
(TTF) [20]. The TTF is a MBT method that uses Z specifications as models from which
test cases are generated. The tool if freely available from http://www.fceia.unr.
edu.ar/˜mcristia/fastest-1.6.tar.gz.
FASTEST already implements the concept of domain partition by so-called testing
tactics. Testing tactics are applied to Z schemas. FASTEST implements testing strategies
as structural testing tools implement coverage criteria. Therefore, FASTEST’s users need
to indicate what testing strategy they want to use and the tool applies testing tactics (i.e.
domain partition) according to the strategy definition. Different strategies can be chosen
for different operations in the specification. Strategies completely hide from users the
complexities of domain partition.
As an example, consider the following Z operation over the symbol table:
Update == [st, st0 : SYM →
7 Z; s? : SYM; v? : VAL | st0 = st ⊕ {s? 7→ v?}]
Clearly, the specification uses a complex relational operator (⊕) but it also deals with integer numbers. In Z the set of integer numbers is infinite. So when an integer Z variable is
implemented, some programming language type is usually chosen (such as int, short,
etc.). Therefore, it would be important to check whether ⊕ and the restriction to say,
short, are correctly implemented. A testing strategy that covers all these situations is
SET- WITH - INTEGERS. If this strategy is used, FASTEST generates 20 tests specifications.
Due to space restrictions only two of them are shown below:
UpdateNR
18 ==
[UpdateVIS |
st 6= ∅ ∧ dom st ∩ dom{s? 7→ v?} = ∅ ∧ v? > −32768 ∧ v? < 32767]
NR
Update20 ==
[UpdateVIS |
st 6= ∅ ∧ (dom st ∩ dom{s? 7→ v?}) = ∅ ∧ v? > 32767]
FASTEST also features a scripting language that allows engineers to define new
testing strategies that later are automatically applied.
4. Discussion and Conclusions
There are several MBT methods that use specification languages whose models are complex formulas over some logic and mathematical theories [2, 9, 11, 12, 14, 3, 19]. Some
of these methods also rely on domain partition. None of them show how coverage criteria
can be defined directly over the logical specifications. These methods may be benefited
by the ideas proposed in this paper. As we have said in the introduction, some MBT
methods [11, 12] think of test cases as sequences of operations that execute the implementation. In these cases, users can extract these sequences by traversing an automaton,
which is derived from the specification. In turn, they can apply different testing criteria
that traverse the automaton in different ways, thus generating different sets of sequences.
This concept is somewhat similar to testing strategies as proposed in this paper, although
perhaps strategies provide more intuitive coverage criteria for logical specifications.
17
SAST
The concept of testing strategy came form the realization that domain partition
rules provide only local or partial coverage over the specification. Strategies are applicable to the whole specification like path- or data-based coverage criteria from structural
testing.
Besides, testing strategies embody the experience and knowledge gained after applying MBT to several projects and case studies [6, 4]. In this sense, the concept of testing strategy is not the mere assembly of partitioning rules nor their blind application to
each statement of the specification. Strategies really relieve testers from some non-trivial
analysis by, as we have said, implementing known testing heuristics. For example, SOME ARITHMETIC applies SP only over arithmetic operators because its focus is on the correct
implementation of arithmetics. Similarly, a structural criterion like condition-coverage
[7] tests conditions not in its most general way. As another example, BASIC - FUNCTIONS,
SOME - ENUMERATIONS and ALL - ENUMERATIONS provide a minimal coverage like statement or branch coverage.
Observe that testing strategies do not change the underlying theory nor the basic
techniques of MBT. This implies that engineers can combine strategies and domain partition to produce test sets as they wish. The partial order that organizes strategies can
be extended or modified as new partitioning rules are created or more insight about the
existing ones is gained.
The presentation made in Section 2 is essentially that of the TTF. However, in this
paper we go one step further by defining some criteria that generate test cases by covering
the logical specification in different ways. Also note that the presentation made in this
paper is more general than that made by Stocks and Carrington since we do not rely on
any particular notation.
The main conclusion we can draw from this paper is that it is possible to define
coverage criteria for MBT methods based on logic and mathematics that play a similar
role to path- or data-based coverage criteria in structural testing. This gives a very abstract and testing-oriented view of MBT methods based on this kind of specifications.
Furthermore, the partial order that can be defined among testing strategies allows testers
to choose the right strategy by what will be tested at the implementation level rather than
by how an input domain is partitioned. This partial order can be modified and extended
with new strategies as they are defined or improved.
In the future we plan to finish the implementation of all the testing strategies described here; to write descriptive cards that help testers to informally understand what
each strategy will test and the relation between them; and to explore whether some partitioning rules that have not be considered so far, can be used to define new strategies.
References
[1] Abrial, J.R.: The B-book: Assigning Programs to Meanings. Cambridge University Press,
New York, NY, USA (1996)
[2] Ammann, P., Offutt, J.: Using formal methods to derive test frames in category-partition
testing. In: Compass’94: 9th Annual Conference on Computer Assurance. pp.
69–80. National Institute of Standards and Technology, Gaithersburg, MD (1994),
citeseer.ist.psu.edu/ammann94using.html
18
SAST
[3] Burton, S.: Automated Testing from Z Specifications. Tech. rep., Department of Computer Science – University of York (2000)
[4] Cristiá, M., Albertengo, P., Frydman, C.S., Plüss, B., Monetti, P.R.: Applying the Test
Template Framework to aerospace software. In: Rash, J.L., Rouff, C. (eds.) SEW.
pp. 128–137. IEEE Computer Society (2011)
[5] Cristiá, M., Albertengo, P., Frydman, C.S., Plüss, B., Rodrı́guez Monetti, P.: Tool support
for the Test Template Framework. Softw. Test., Verif. Reliab. 24(1), 3–37 (2014)
[6] Cristiá, M., Santiago, V., Vijaykumar, N.: On comparing and complementing two MBT
approaches. In: Test Workshop (LATW), 2010 11th Latin American. pp. 1–6 (2010)
[7] Ghezzi, C., Jazayeri, M., Mandrioli, D.: Fundamentals of software engineering (2nd ed.).
Prentice Hall (2003)
[8] Grieskamp, W., Kicillof, N., Stobie, K., Braberman, V.A.: Model-based quality assurance
of protocol documentation: tools and methodology. Softw. Test., Verif. Reliab. 21(1),
55–71 (2011)
[9] Hall, P.A.V.: Towards testing with respect to formal specification. In: Proc. Second
IEE/BCS Conference on Software Engineering. pp. 159–163. No. 290 in Conference Publication, IEE/BCS (Jul 1988)
[10] Harel, D.: Statecharts: A visual formalism for complex systems. Science of Computer
Programming 8, 231–274 (1987)
[11] Hierons, R.M., Sadeghipour, S., Singh, H.: Testing a system specified using Statecharts
and Z. Information and Software Technology 43(2), 137–149 (February 2001),
http://dx.doi.org/10.1016/S0950-5849(00)00145-2
[12] Hierons, R.M.: Testing from a Z specification. Software Testing, Verification & Reliability 7, 19–33 (1997)
[13] Hierons, R.M., Bogdanov, K., Bowen, J.P., Cleaveland, R., Derrick, J., Dick, J., Gheorghe, M., Harman, M., Kapoor, K., Krause, P., Lüttgen, G., Simons, A.J.H.,
Vilkomir, S., Woodward, M.R., Zedan, H.: Using formal specifications to support
testing. ACM Comput. Surv. 41(2), 1–76 (2009)
[14] Hörcher, H.M., Peleska, J.: Using Formal Specifications to Support Software Testing.
Software Quality Journal 4, 309–327 (1995)
[15] Peleska, J.: Industrial-strength model-based testing - state of the art and current challenges. CoRR abs/1303.1006 (2013)
[16] Rapps, S., Weyuker, E.J.: Data flow analysis techniques for test data selection. In: ICSE
’82: Proceedings of the 6th international conference on Software engineering. pp.
272–278. IEEE Computer Society Press, Los Alamitos, CA, USA (1982)
[17] Satpathy, M., Leuschel, M., Butler, M.: ProTest: An automatic test environment for B
specifications. Electronic Notes in Theroretical Computer Science 111, 113–136
(January 2005)
[18] Spivey, J.M.: The Z notation: a reference manual. Prentice Hall International (UK) Ltd.,
Hertfordshire, UK, UK (1992)
19
SAST
[19] Stepney, S.: Testing as abstraction. In: Bowen, J.P., Hinchey, M.G. (eds.) ZUM. Lecture
Notes in Computer Science, vol. 967, pp. 137–151. Springer (1995)
[20] Stocks, P., Carrington, D.: A Framework for Specification-Based Testing. IEEE Transactions on Software Engineering 22(11), 777–793 (Nov 1996)
[21] Trab, M.S.A., Brockway, M., Counsell, S., Hierons, R.M.: Testing real-time embedded
systems using timed automata based approaches. Journal of Systems and Software
86(5), 1209–1223 (2013)
[22] Utting, M., Legeard, B.: Practical Model-Based Testing: A Tools Approach. Morgan
Kaufmann Publishers Inc., San Francisco, CA, USA (2006)
[23] Zander, J., Schieferdecker, I., Mosterman, P.: Model-based Testing for Embedded Systems. Computational Analysis, Synthesis, and Design of Dynamic Systems Series,
CRC Press (2012), http://books.google.com.ar/books?id=fzgzNW\
_alD0C
20
SAST
Towards the Establishment of a Sufficient Set of Mutation
Operators for AspectJ Programs
Jésus Thiago Sousa Lacerda1 , Fabiano Cutigi Ferrari1
1
Computing Department
Federal University of São Carlos (UFSCar) – São Carlos – SP – Brazil
{jesus.lacerda, fabiano}@dc.ufscar.br
Abstract. Mutation testing is an effective test selection criterion that has been explored
in the context of aspect-oriented (AO) programs written in the AspectJ language. Despite its effectiveness, mutation testing is expensive. To reduce its application cost,
some strategies based on mutation operator selection are available in the literature.
This paper describes the results of a study that aimed to reduce the costs of applying
mutation testing to AspectJ programs by identifying a reduced set of mutation operators known as sufficient operators. To achieve the proposed objective, we applied the
Sufficient Procedure, which has resulted in expressive cost reductions when applied to
procedural programs. Indeed, the procedure led to a small set of operators and to a
cost reduction of 53% in terms of number of mutants to be handled.
1. Introduction
Aspect-oriented programming (AOP) is an approach to improve the modularisation of software in the face of the difficulties faced by existing techniques, including object-oriented
programming (OOP). These difficulties refer to the behaviour of software that is usually
scattered in different modules of the system or the other intertwined behaviour. Such behaviour, which may be related to functional or non-functional properties of the software,
constitute the so-called crosscutting concerns [11]. Although AOP represents a possible solution to deal with crosscutting concerns, the adoption of this technique (or paradigm) may
introduce new types of faults. Thus, it is necessary design specialised tests to ensure the
quality of software that uses this paradigm.
From a variety of testing criteria that can be applied for the validation of AO programs, mutation testing [4] has shown to be a promising alternative [3, 7, 9, 15, 17]. In
spite of the high effectiveness of mutation testing, this criterion has been historically characterised as very expensive due to large number of the mutants generated, given that manual
tasks are required to analyse the mutants and improve the test set. Therefore, establishing
strategies for cost reduction of mutation testing of AO programs becomes essential for the
sake of feasibility of the criterion.
Amongst the techniques for reducing the costs of mutation testing, some focus on reducing the number of generated mutants based on the characteristics of mutation operators.
Examples are constrained mutation [13], selective mutation [14] and sufficient operators [2].
From these techniques, sufficient operators has resulted in the highest cost reduction rates
when applied to procedural programs.
To date, few studies explored the cost reduction of mutation testing for AO programs,
mainly focusing on reducing the number of equivalent mutants [15, 17]. In this context, the
objective of this study is to identify a sufficient set of mutation operators which is able to
reduce substantially the cost of mutation testing when compared to the full set of operators.
To accomplish the proposed objective, we apply the Sufficient Procedure [2] to a set
of 12 small-sized AO programs written in the AspectJ language. The Sufficient Procedure
aims to identify a set of sufficient mutation operators that keeps the effectiveness of the
21
SAST
test suite with respect the whole set of mutation operators. Note that AspectJ represents
the mainstream AOP technology, upon which research and practical usage have developed.
We choose the Sufficient Procedure since it has yielded expressive results for procedural
programs. Indeed, our results show that a reduced set of mutation operators for AspectJ
programs may produce a high mutant coverage with a cost reduction of 53%.
The remaining of this paper is organised as follows: Sections 2 and 3 describe basic
concepts and related work, respectively. The plan of the exploratory study to identify sufficient operators is described in Section 4, whereas Section 5 details the achieved results and
limitations. Conclusions and future work come in Section 6.
2. Background
2.1. Aspect-Oriented Programming
The goal of aspect-oriented programming (AOP) is improving the modularisation of the socalled crosscutting concerns [11]. In doing so, such concerns will not appear tangled with
other concerns or spread across various parts of the code. Adopting AOP, the developer
is able to separate and better organise the code and thus improve software quality through
the concept of separation of concerns [5, 11]. In AOP, the element responsible to make the
modularisation of these concerns is the aspect. Ideally, an aspect can change the behaviour
of the remaining system functionalities without their knowledge of the aspect action. In one
aspect, behaviour related to a crosscutting concern is termed advice, and it can be executed
at a specified time. The moment of the execution of an advice is determined by a join point
and can be defined in predicate-based expressions known as pointcuts. Mainstream AOP
technologies such as AspectJ1 , SpringAOP2 and CaesarJ3 provide mechanisms for defining
pointcut expressions to identify joint points throughout the software code.
Despite the benefits of AOP brings, using its programming constructs may result in
new types of faults in the code [1, 6]. Therefore, to ensure the quality of produced software,
several testing approaches have been explored, involving different techniques and testing
criteria. Among these approaches, mutation testing has attracted the research community’s
attention and has been on focus in recent research [7, 9, 15, 17].
2.2. Mutation Testing for AO Programs
The Mutant Analysis criterion – also known as mutation testing – was first described by
DeMillo et al. [4]. This criterion inserts small defects in software with the aim of simulating
the common mistakes made by programmers. Mutation testing consists in generating several
versions of the program P under testing with small syntactic changes (P 0 , P 00 , ...); these
modified versions are called mutants. Tests are executed on P and on (P 0 , P 00 , ...). Given a
mutant, say P 0 , if the result of at least one test case differs between P and P 0 , P 0 is said to
be killed (i.e. the simulated fault was revealed). Otherwise, the mutant remains alive so P 0
must be analysed to check for equivalence with P or to require a new test case that reveals
the difference between P and P 0 . The mutation score (MS) measures the test coverage based
on the ratio of killed mutants with respect to the total number of non-equivalent mutants.
For AO programs, Ferrari et al. [7] defined a set of mutation operators considering
the AspectJ language. The operators are based on fault types specific of the AO paradigm.
The operators are organised in three groups; each group simulates three categories of faults
related to main AOP concepts and constructs of AspectJ, namely: pointcut expressions
1
http://www.eclipse.org/aspectj/ – accessed in 27/06/2014
http://docs.spring.io/spring/docs/2.5.4/reference/aop.html – accessed in 27/06/2014
3
http://caesarj.org/ – accessed in 27/06/2014
2
22
SAST
(Group 1); declare-like expressions (Group 2); and advice definition and implementation
(Group 3). In total, 26 operators are defined (15 in Group 1, 5 in Group 2, and 6 in Group
3), and the Proteum/AJ tool [8] automates 24 of them.
2.3. The Sufficient Procedure
Many studies have investigated different approaches for mutation testing in order to reduce
costs of such criterion. A survey reported by Jia and Harman [10] describes the main contributions in this field. Examples of cost reduction strategies are selective mutation, higher
order mutation, weak mutation, and sufficient mutation. Amongst them, sufficient mutation
was proposed by Barbosa et al. [2] and, by applying a procedure called Sufficient, has shown
the highest reduction costs without effectiveness loses.
The Sufficient Procedure consists of six steps that aim to select the best mutation
operators to compose an essential (or sufficient) set. The steps are described as follows:
1. Consider operators that determine high score mutation: select operators which
produces the highest mutation scores in relation with the whole set of operators.
2. Consider at least one operator for each class of mutation: since each class of
operators models specific types of faults, it is desirable that the set of operators
contains at least one operator for each class.
3. Evaluate empirical inclusion among operators: check if operators in the sufficient
set are empirically included by other operators; if so, remove them from the set.
4. Establish incremental implementation strategy: due to the high cost of operators,
it is necessary to establish an incremental strategy for their application.
5. Consider operators that provide an increase in the mutation score: seek for
operators not yet selected, but have the ability to increase the mutation score.
6. Consider operators with high strength: consider operators which have high
strength, since they are usually not empirically included by other operators.
3. Related Work
Barbosa et al. [2] applied the Sufficient Procedure (described in Section 2) to procedural
programs developed in the C language. The procedure was applied to two different sets of
applications. In both sets the authors achieved expressive cost reduction of around 65%, on
average. Motivated by such results, we apply the Sufficient Procedure in the study presented
in this paper. The results are compared with Barbosa et al.’s results in Section 5.2.
In more recent studies focus on different approaches for testing AO programs using
mutation [15, 17]. Wedyan and Ghosh proposed the use of simple object-based analysis
to prevent the generation of equivalent mutants for some mutation operators for AspectJ
programs. They argue that reducing the amount of equivalent mutants generated by some
operators would consequently reduce the cost of mutation testing as a whole. The authors
use three testing tools (AjMutator, Proteum/AJ, MuJava) to assess their technique. The
results are that, on average, 80% of the equivalent mutants could be avoided of being generated, proving the efficiency of their approach. Note that Wedyan and Ghosh’s approach
consists in changing the mutation rules encapsulated into the operators with the aim of not
generating equivalent mutants. Such strategy requires tool adaptive maintenance. Once implemented, it could be applied in conjunction with the Sufficient Procedure to reduce even
more the cost of mutation testing applied to AO programs.
Omar and Ghosh [15] presented four approaches to generate higher order mutants for
AspectJ programs. The approaches were evaluated in terms of the ability to create mutants
of higher order resulting in higher efficacy and less effort when compared with first order
23
SAST
mutants. Some of these approaches can reduce the amount of equivalent mutants generated
or reduce the total number of mutants, i.e. they can reduce the cost of mutation testing in
this paradigm. Furthermore, all approaches proposed can produce higher order mutants that
can be used to increase test effectiveness and reduce test effort.
Ferrari et al. [9] evaluated the same set of applications we analyse in this study. They
apply a whole set of mutation operators proposed in their previous work [7]. Two analyses
are presented: (i) they compared the cost of applying mutation with the Systematic Functional Testing (SFT) criterion, which has shown to be very effective in detecting mutants for
C programs [12]; and (ii) they measured the effort required to achieve mutation adequate
test sets. In short, the results are that the application of SFT was not enough to achieve
adequate mutation coverage; on average, 5% of additional tests was required.
4. Study Setup
4.1. Research Question
This study aims to investigate how to reduce the cost of applying mutation testing in AO
programs. We define two research questions, the first related to the feasibility of achieving
significant cost reduction, and the second related to the amount of effort we can save.
• RQ1: Can one identify a reduced set of mutation operators which are effective to
reveal AO-specific faults simulated by a complete set of operators?
• RQ2: Can one achieve an expressive cost reduction in mutation testing for AO programs by applying the reduced set of operators?
We selected the Sufficient Procedure proposed by Barbosa et al. [2] as the approach
to be applied to AO programs in order to obtain a reduced set of operators for AspectJ
programs. The key measure considered by the Sufficient Procedure is the mutation score
associated with an individual mutation operator or to a set of mutation operators. Since
such procedure has resulted in the highest effort savings when applied to procedural programs when compared to other operator-based cost reduction approaches [2], we believe
this procedure should also provide significant results for AO programs as well.
4.2. The Dataset
In our study we reused mutation-adequate test sets originally designed by Ferrari et al. [9] for
12 small AO software applications developed in the AspectJ language. A short description
and some coarse-grained metrics of these applications are shown in Table 1. We highlight
that the design of test sets as well as the mutant analysis were thoroughly performed by
those authors with support of the Proteum/AJ tool [8].
General test data for each application is shown in Table 2. Column “#Total Mut.”
shows the total number of mutants per application. The remaining columns represent, respectively: the number of mutants automatically classified as equivalent (“#Autom.Equiv”)
and anomalous4 (“#Anom.”); the number of mutants that should be killed by tests or manually classified as equivalent (“#Alive Mut.”); the number of mutants manually classified
as equivalent (“#Man.Equiv.”); the size of the mutation-adequate test set (“|T M |”); and the
final mutation score (“M.S”).
4.3. Dataset Preparation
Based on the results generated in the study of Ferrari et al. [9], we implemented and executed a series of SQL queries and Java routines to obtain a cross-comparison table amongst
4
A mutant is classified as anomalous if it does not compile.
24
SAST
Table 1: Description of the applications used in the study (adapted from Ferrari et al. [9])
Application
1. BankingSystem
Description
System that manages transactions for bank accounts. Aspects in BankingSystem implement logging, minimum balance control and overdraft operations.
2. Telecom
Phone system simulator developed in AspectJ and distributed by The
Eclipse Foundation. Manage phone calls, and calculations of time and
cost of each call are made for aspects
3. ProdLine
Software product line for graph applications that includes a set of common
functionalities of the graph domain. The aspects in this application are
responsible for introducing the selected features in a determined instance
SPL.
4. FactorialOptimizer
Mathematical system that implements an optimization on the factorial of
a number. The calculation is managed by an aspect, it stores all cached
calculations to eventually be recovered and reused in other calculations.
5. MusicOnline
Management system from an online music store. The aspects are responsible for managing user accounts and billing system.
6. VendingMachine
System that manages the interaction of sales in a drinks machine. The
aspects managed manage the sale, returning the user coins when needed
and releasing the drink requested.
7. PointBoundsChecker Two-dimension point constraint checker. The aspect checks if the coordinates of the points belong to a given interval, otherwise an exception is
thrown
8. StackManager
It’s a simple stack that improves the operations of push and pop. The
aspects perform audit of the stored numbers and count the number of operations of push type.
9. PointShadowManager Application for managing two-dimension point coordinates. One aspect
create and manage the shadow of two points, the shadows most have
exactly same coordinates of the points.
10. Math
Math utility application that calculates the probability of successes in a sequence of n independent yes/no experiments (Bernoulli trial), each yielding success with probability p. The aspect logs exponentiation operations,
identifying the type of the exponent.
11. AuthSystem
Simpler version of a bank system, the system requires the user to authenticate before simple operations such as debit, credit and check balance. The
aspects are responsible for authentications and transaction management.
12. SeqGen
Implements a generator from a sequence of numbers and characters. The
aspects modularize the policy generation and logging concerns
LOC Classes Aspects
199
9
6
251
6
3
537
8
8
39
1
1
150
7
2
64
1
3
44
1
1
77
4
3
66
2
1
53
1
1
89
3
2
205
8
4
Table 2: Summary of the application of mutation testing on the set of programs
Application
#Total Mut. #Autom.Equiv. #Anom. #Alive Mut. # Man.Equiv. |T M |
1. BankingSystem
136
68
18
50
58
2. Telecom
111
46
12
53
10
67
3. ProdLine
199
125
16
58
36
4. FactorialOptimizer
29
8
6
15
1
19
5. MusicOnline
57
25
5
27
2
48
6. VendingMachine
113
58
8
47
13
23
7. PointBoundsChecker
70
32
10
28
14
8. StackManager
45
24
0
21
15
9. PointShadowManager
50
25
4
21
5
14
10. Math
20
13
0
7
2
54
11. AuthSystem
52
28
3
21
1
19
12. SeqGen
40
19
3
18
8
42
Total
922
471
85
366
42
409
M.S.
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
operators. For each mutation operator, we identified the respective adequate subset of test
cases and checked the coverage of mutants generated by all other operators. Part of the
comparison table appears in Table 3.
Similarly to Barbosa et al.’s study [2], using such a table we can check the average
mutation score obtained by each operator’s adequate test set with respect to all other operators. For instance, the subset of adequate test cases for operator ABHA (line 2) is almost
considered adequate for operator ABAR (column 1), achieving a mutation score of 0.9960.
In this case, it is said that the ABAR operator is included empirically by the ABHA operator.
25
SAST
Table 3: Part of the cross between mutation operators
Op/Op
ABAR
ABHA
ABPR
APER
APSR
DAPC
DAPO
PCCE
Average
ABAR
1
0.9960
0.6169
0.1422
0.5230
0.4410
0.1327
0.8708
0.5392
ABHA
0.9352
1
0.6508
0.2964
0.6361
0.5008
0.2360
0.8913
0.5518
ABPR
0.9431
0.9431
1
0.5583
0.7967
0.7154
0.3631
0.8238
0.5938
APER
1
1
1
1
1
1
0.4820
1
0.6634
APSR
0.8963
0.9931
0.7234
0.3872
1
0.5106
0.2851
0.6935
0.5178
DAPC
1
1
1
0.6107
1
1
0.4497
1
0.7363
DAPO
0.9853
0.9853
0.9853
0.5317
0.9853
0.9853
1
0.9853
0.7010
PCCE
0.8595
0.9372
0.5275
0.1946
0.5042
0.4019
0.1603
1
0.4761
...
...
...
...
...
...
...
...
...
...
Average
0.9246
0.9598
0.7730
0.3359
0.7196
0.6204
0.2744
0.9005
-
With this comparison table, we can perform some preliminary analysis required to
run the Sufficient Procedure. For example, we can rank the operator with the highest mutation score (MS), highest strength and highest cost. This data can be observed in Table 4.
Note that strength is obtained with the formula (1 - operator’s average mutation score with
respect to all other mutation operators). For example, the strength of ABHA operator is
0.4482 (i.e. 1 - 0.5518; see ABHA column in Table 3).
Table 4: Mutation score, strength and cost of operators.
MS
Operator
ABHA
PWIW
ABAR
PCCE
POAC
ABPR
APSR
DAPC
POPL
PSWR
...
Value
0.9598
0.9534
0.9246
0.9005
0.8728
0.7330
0.7196
0.6204
0.5718
0.5635
...
Strength
Operator
Value
PWIW
0.5564
PCCE
0.5239
PCTT
0.5082
POAC
0.5048
APSR
0.4822
PCGS
0.4706
ABAR
0.4608
ABHA
0.4482
POPL
0.4147
ABPR
0.4062
...
...
Cost
Operator Value
PWIW
456
ABAR
75
ABPR
62
PCCE
57
POPL
54
ABHA
52
POAC
50
PCCT
31
PCLO
30
APSR
18
...
...
5. Results and Analysis
In this section the Sufficient Procedure is applied step-by-step ad the results are described.
At the end of each step the partial result of the sufficient set is presented. After describing
all partial results, we present the final sufficient set and an analysis of the cost reduction
achieved with the procedure.
5.1. The Sufficient Procedure Step-by-Step
As described in Section 2.3, the Sufficient Procedure requires six steps to result in a sufficient set of mutation operators for programs written in a particular programming language.
Following we describe the execution of each step and the partial results we achieved.
Step 1: Consider mutant operators that determine a high mutation score
To apply this step, we defined the value of 0.75+
− 0.02 for mutation score (MS) as a
minimum threshold to select operators to compose the SSpre set, which is the preliminary
sufficient mutant operators sets. That is, only operators that produce MS equal or higher
than the threshold are selected to compose SSpre .
The minimum threshold for inclusion was defined based on the study of Barbosa
et al. [2]. Although those authors have chosen a higher threshold (MS = 0.9+
− 0.005), we
decided for a lower value in order to work with a similar SSpre size as they did. More
26
SAST
specifically, our threshold enabled us to create the SSpre set with six operators, as follows:
SSpre = {ABHA, PWIW, ABAR, PCCE, POAC, ABPR}
Step 2: Consider at least one operator for each class of mutation
As the reader can notice, SSpre lacks operators of Group 2, which are operators that
model faults related to declare-like expressions in AspectJ. From the five available operators (namely, DAPC, DAPO, DSSR, DEWC, DAIC), only DAPC and DAPO generated
mutants for the target applications. However, running mutants of DAPC and DAPO on
SSpre -adequate test cases results in MS = 1.000 and MS = 0.9852 in regard to those mutants, respectively. For this analysis, MS ≥ 0.95 is defined as an optimal index of mutation
score to consider a mutation operator empirically included by the others, likewise in Barbosa
et al.’s study [2]. We then conclude DAPC and DAPO are empirically included by SSpre
and that at this point, SSpre remains unchanged.
Step 3: Evaluate empirical inclusion among operators
From the SSpre set obtained so far, we can analyse the empirical inclusion amongst
its elements and possibly reduce the preliminary set. Table 5 supports the analysis, in which
operators one-by-one are contrasted with the remaining operators from SSpre . Similarly to
the previous step, MS ≥ 0.95 is considered an optimal index for empirical inclusion.
Table 5: Empirical inclusion considering SSpre operators one-by-one.
Relation Empirical Inclusion
{’ABHA’,’PWIW’,’ABAR’,’PCCE’,’POAC’} → {’ABPR’}
{’ABPR’,’PWIW’,’ABAR’,’PCCE’,’POAC’} → { ’ABHA’}
{’ABPR’,’ABHA’,’ABAR’,’PCCE’,’POAC’} → { ’PWIW’}
{’ABPR’,’ABHA’,’PWIW’,’PCCE’,’POAC’} → { ’ABAR’}
{’ABPR’,’ABHA’,’PWIW’,’ABAR’,’POAC’} → { ’PCCE’}
{’ABPR’,’ABHA’,’PWIW’,’ABAR’,’PCCE’} → { ’POAC’}
Highlight Op.
ABPR
ABHA
PWIW
ABAR
PCCE
POAC
Mutation Score
0.943089
0.999489
0.742682
0.996038
0.937153
0.921406
Operators to be considered for removal from SSpre are in ABHA and ABAR. Since
this step is performed incrementally, the first operator to be removed will be one that is more
empirically included by the other operators, in this case, ABHA, since it is the operator with
the highest score listed in Table 5 (MSABHA = 0.999489).
After removing the ABHA operator, SSpre was re-evaluated and we verified that the
values of the empirical inclusion remained the same. The values of this new revaluation of
inclusion relations are shown in Table 6.
Table 6: Empirical inclusion after removing ABHA.
{’PWIW’,’ABAR’,’PCCE’,’POAC’} → {’ABPR’}
{’ABPR’,’ABAR’,’PCCE’,’POAC’} → { ’PWIW’}
{’ABPR’,’PWIW’,’PCCE’,’POAC’} → { ’ABAR’}
{’ABPR’,’PWIW’,’ABAR’,’POAC’} → { ’PCCE’}
{’ABPR’,’PWIW’,’ABAR’,’PCCE’} → { ’POAC’}
Highlight Op.
ABPR
PWIW
ABAR
PCCE
POAC
Mutation Score
0.943089
0.742682
0.996038
0.937153
0.921406
The next operator to be removed is ABAR. After its removal, there were changes
in some mutation scores, but none of these changes lead to the empirical inclusion of any
operator in SSpre . This new revaluation is shown in Table 7.
At the end of step 3, we have the following SSpre set:
SSpre = {PWIW, PCCE, POAC, ABPR}
27
SAST
Table 7: Empirical Inclusion for the operator after exclude ABAR operator
{’PWIW’,’PCCE’,’POAC’} → {’ABPR’}
{’ABPR’,’PCCE’,’POAC’} → { ’PWIW’}
{’ABPR’,’PWIW’,’POAC’} → { ’PCCE’}
{’ABPR’,’PWIW’,’PCCE’} → { ’POAC’}
Highlight Op.
ABPR
PWIW
PCCE
POAC
Mutation Score
0.861788
0.688023
0.937153
0.921406
Step 4: Establish incremental implementation strategy
This step does not change the composition of SSpre ; instead, it defines an order
for the application of the pre-selected operators, based on their cost in terms of number of
generated mutants. Operators must be applied from the lowest-cost operator to the highestcost one, resulting in the following order of application: POAC (50 mutants), PCCE (57
mutants), ABPR (62 mutants), PWIW (456 mutants).
Step 5: Consider operators that provide an increase in the mutation score
In this step, Barbosa et al. [2] defined the minimum increment index (MII) (in this
case, MII ≥ 0.02), as a minimum increment an operator should provide to overall mutation
score if it was included in SSpre .
Observing all mutation operators (except those already in SSpre ), only PCLO and
POPL are not empirically included by SSpre . Thus, these are candidate operators to be
inserted into SSpre . However, neither PCLO nor POPL have achieved the MMI index, i.e.
none of them have increased substantially the mutation score of SSpre , so the preliminary
set remains the same.
Step 6: Consider operators with high strength
In Step 6, Barbosa et al. [2] defined a minimum index of strength (MSI) for the
inclusion of an operator in SSpre . The authors have set MSI = 0.4+
− 0.02.
Based on this index, we have the following operators: PWIW, PCCE, PCTT, POAC,
APSR, PCGS, ABAR, ABHA, POPL, ABPR and PCLO. From these, PWIW, PCCE, POAC
and ABPR are not considered as they already compose the SSpre set. From the remaining
operators, only POPL and PCLO are not empirically included, as noticed in Step 5. Thus,
they again become candidates for inclusion in SSpre .
Since POPL and PCLO belong to the same class of operators, only one will be
included in SSpre . Thus, the POPL operator (strength = 0.4147, see Table 4) was included
in SSpre because it has higher strength than PCLO (strength = 0.3850, not listed in Table 4
due to space limitations).
The resulting sufficient set of operators
At the end of the six steps, we have defined the following sufficient operator set, thus
we answer positively the first research question defined in Section 4.1:
SS = {POAC, PCCE, ABPR, PWIW, POPL}
5.2. Analysis
We now analyse the cost reduction we can obtain by applying the achieved sufficient set. For
this, we must compare the cost of applying only the SS operators with the cost of applying
the full set of operators. Table 8 shows the application costs for each SS operator. The
table columns include, respectively: the operator name; the number of mutants; the number
of compilable mutants; the number of equivalent mutants automatically detected by the
28
SAST
Proteum/AJ tool; and the number of significant mutants (i.e. killed by tests or manually
classified as equivalent).
At a first sight, we obtain a cost reduction of 26.4%, considering all 922 mutants generated (see Table 2) and the 679 mutants generated with SS operators. In a further analysis,
we discard anomalous mutants and mutants that are automatically detected as equivalent.
In both cases, no manual effort is required, since identifying such mutants only depends on
automated routines performed by the tool. Therefore, we consider only the last column of
Table 2 and the results are as follows:
From the 922 mutants generated by all operators, 471 are automatically classified
as equivalent and 85 are anomalous. This gives us a balance of 366 significant mutants.
Comparing this number with the value of 173 (which is the number of significant mutants
generated by the SS operators), the cost reduction reaches 53%.
This cost reduction is slightly lower than the reduction of 65% reached by Barbosa
et al. [2]. Nevertheless, it is undoubtedly an expressive value. Therefore, we can also answer
positively the second research question defined in Section 4.1.
Table 8: Cost of the Sufficient Set
Operator
POAC
PCCE
ABPR
PWIW
POPL
Total
Cost
50
57
62
456
54
679
Comp.Mut.
44
55
20
446
50
615
Equiv.Mut.
0
0
0
402
40
442
Total Mutants
44
55
20
44
10
173
5.3. Limitations
According to Barbosa et al. [2], the Sufficient Procedure depends on the application domain
and the set of applications used. Given that there is no other study reporting the use of this
procedure to determine sufficient sets of mutation operators in AO programs, it would be
interesting to apply the Sufficient Procedure to other application domains in order to contrast
the results with the findings of this study. It is also interesting to apply this procedure using
a larger set of application to investigate the scalability of the procedure in this paradigm,
because the set used in this study consists of only 12 applications.
Another limitation concerns the variety of mutation operators applied. The DSSR,
DEWC and DAIC operators did not generate any mutant for the target applications. Indeed,
a previous cost estimation study performed by Ferrari et al. [9] showed that these operators
are likely to produce few (if none) mutants even when applied to medium-sized systems.
6. Conclusion and Future Work
This paper reported an exploratory study that aimed to identify a reduced set of mutation
operators that require effective tests to reveal faults artificially introduced into programs. To
achieve the results, we applied the Sufficient Procedures, which is an incremental technique
to identify the most relevant mutation operators from a given set of operators. The relevance
of an operator relies on its produced mutant coverage (i.e. the mutation score) and on its
strength when compared to other operators. After concluding the study, we provided positive
answers to two research questions that regarded the feasibility of the procedure for the AO
programs, and the level of cost reduction that can be achieved. In short, a set compound by
5 out of 24 operators requires 53% less effort in terms of the number of generated mutants
when contrasted with the full set of operators.
29
SAST
The results of this study are useful, for instance, for researchers and testers who
intend to apply mutation testing in AspectJ programs from the same application domain.
Beyond that, the results can build a historical database of sufficient operators that can grow
with new rounds of experiments. As future work, we plan to apply the Sufficient Procedure
to larger sets of AspectJ applications, so that we can contrast the results to check if there is
any variation in the sufficient set of operators achieved.
Acknowledgements
The authors would like to thank the financial support received from CNPq (Universal Grant
#485235/2013-7), Federal University of São Carlos (RTN grant) and CAPES.
References
[1] Alexander, R. T., Bieman, J. M., and Andrews, A. A. (2004). Towards the systematic testing of aspectoriented programs. Tech. Report CS-04-105, Dept. of Computer Science, Colorado State University,
Fort Collins/Colorado - USA.
[2] Barbosa, E. F., Maldonado, J. C., and Vincenzi, A. M. R. (2001). Toward the determination of sufficient
mutant operators for C. The Journal of Software Testing, Verification and Reliability, 11(2):113–136.
[3] Delamare, R., Baudry, B., Ghosh, S., and Le Traon, Y. (2009). A test-driven approach to developing
pointcut descriptors in AspectJ. In Proceedings of the 2nd International Conference on Software Testing,
Verification and Validation (ICST), pages 376–385, Denver/CO - USA. IEEE Computer Society.
[4] DeMillo, R. A., Lipton, R. J., and Sayward, F. G. (1978). Hints on test data selection: Help for the
practicing programmer. IEEE Computer, 11(4):34–43.
[5] Dijkstra, E. W. (1976). A Discipline of Programming. Prentice-Hall, Englewood Cliffs/NJ - USA.
[6] Ferrari, F. C., Burrows, R., Lemos, O. A. L., Garcia, A., and Maldonado, J. C. (2010a). Characterising
faults in aspect-oriented programs: Towards filling the gap between theory and practice. In Proceedings
of the 24th Brazilian Symposium on Software Engineering (SBES), pages 50–59, Salvador/BA - Brazil.
IEEE Computer Society.
[7] Ferrari, F. C., Maldonado, J. C., and Rashid, A. (2008). Mutation testing for aspect-oriented programs.
In Proceedings of the 1st International Conference on Software Testing, Verification and Validation
(ICST), pages 52–61, Lillehammer - Norway. IEEE.
[8] Ferrari, F. C., Nakagawa, E. Y., Rashid, A., and Maldonado, J. C. (2010b). Automating the mutation
testing of aspect-oriented Java programs. In Proceedings of the 5th ICSE International Workshop on
Automation of Software Test (AST), pages 51–58, Cape Town - South Africa. ACM Press.
[9] Ferrari, F. C., Rashid, A., and Maldonado, J. C. (2013). Towards the practical mutation testing of
AspectJ programs. Science of Computer Programming, 78(9):1639–1662.
[10] Jia, Y. and Harman, M. (2009). Higher order mutation testing. Inf. Softw. Technol., 51(10):1379–1393.
[11] Kiczales, G., Irwin, J., Lamping, J., Loingtier, J.-M., Lopes, C., Maeda, C., and Menhdhekar, A.
(1997). Aspect-oriented programming. In Proceedings of the 11th European Conference on ObjectOriented Programming (ECOOP), pages 220–242 (LNCS v.1241), Jyväskylä - Finland. Springer-Verlag.
[12] Linkman, S., Vincenzi, A. M. R., and Maldonado, J. C. (2003). An evaluation of systematic functional testing using mutation testing. In Proceedings of the 7th International Conference on Empirical
Assessment in Software Engineering (EASE), pages 1–15, Keele - UK.
[13] Mathur, A. P. and Wong, W. E. (1993). Evaluation of the cost of alternative mutation strategies. In
Proceedings of the 7th Brazilian Symposium on Software Engineering (SBES), pages 320–335, João
Pessoa/PB - Brazil.
[14] Offutt, A. J., Rothermel, G., and Zapf, C. (1993). An experimental evaluation of selective mutation.
In Proceedings of the 15th International Conference on Software Engineering (ICSE), pages 100–107,
Baltimore/MD - USA. IEEE Computer Society.
[15] Omar, E. and Ghosh, S. (2012). An exploratory study of higher order mutation testing in aspectoriented programming. In Proceedings of the 23rd International Symposium on Software Reliability
Engineering (ISSRE), pages 1–10. IEEE.
[16] The Eclipse Foundation (2010). AJDT Eclipse plugin. Online. http://www.eclipse.org/
ajdt/ - last accessed on 27/06/2014.
[17] Wedyan, F. and Ghosh, S. (2012). On generating mutants for aspectj programs. Information and
Software Technology, 54(8):900–914.
30
SAST
Uma Revisão Sistemática em Teste de Segurança Baseado em
Modelos
Carlos Diego Nascimento Damasceno1 , Márcio Eduardo Delamaro1 ,
Adenilso da Silva Simão1
1
Instituto de Ciências Matemáticas e de Computação – ICMC
Universidade de São Paulo – USP
Av. Trabalhador São-carlense, 400 – 13566-590 – São Carlos – SP – Brasil
[email protected], {delamaro,adenilso}@icmc.usp.br
Abstract. Model-Based Testing (MBT) is a testing approach which uses explicit formal models to specify and automatize test case generation. It has been
successfully applied in funcional testing, however there are still challenges in
non-functional requirements testing, as security. This paper presents a systematic literature review about model-based security testing. An MBT taxonomy
was used as reference for data extraction to identify tendencies and gaps of research. Even though it was not possible to correlate all the studies found with
each dimension of the taxonomy, a predominance of the transition-based modeling paradigm and an increasing number of published papers per year were
identified.
Resumo. Teste baseado em modelos (TBM) é uma variante de teste que usa modelos explı́citos formais para especificar e automatizar a geração de testes. Ela
tem sido utilizada com sucesso no teste funcional, entretanto ainda existem desafios no teste de requisitos não funcionais, como segurança. Este artigo apresenta uma revisão sistemática sobre teste de segurança baseado em modelos.
Uma taxonomia proposta para TBM foi usada como base para a extração de
dados para identificar tendências e lacunas de pesquisa. Apesar de não ter sido
possivel estabelecer uma correlação integral entre os estudos e as dimensões
da taxonomia, foi identificado um crescente número de publicações nesta área
e uma predominância do paradigma de modelagem baseados em transição.
1. Introdução
A popularização de serviços baseados em mobilidade, virtualização e conectividade
têm contribuido fortemente não somente com a flexibilização de negócios de empresas, mas também com o aumento de vulnerabilidades que elas estão se expondo
[Rashid et al. 2013]. Consequentemente, a demanda por técnicas de garantia de qualidade, como o teste de software, tem crescido significativamente. Entretanto, o teste
de software ainda é frequentemente caracterizado como uma atividade custosa, tediosa e mal documentada [Utting et al. 2012]. Para tratar isso, uma variante denominada
teste baseado em modelos propõe o uso de modelos explı́citos em notação formal para
especificar sistemas em teste (do inglês, System Under Test - SUT) e automatizar a
geração de testes [Utting and Legeard 2007]. A fim de caracterizar as abordagens de
teste de segurança baseado em modelos (TSBM), foi realizada uma revisão sistemática
31
SAST
visando coletar evidências que apontassem os principais resultados obtidos, desvantagens, limitações, tendências e caracterı́sticas destas abordagens com base na taxonomia
proposta em [Utting and Legeard 2007] para TBM.
A partir dos dados extraı́dos identificamos que nem todas as dimensões da taxonomia do TBM estão evidentes nos estudos. Foi observada uma predominância no uso do
paradigma de modelagem baseado em modelos de transição e de SUTs reais, além de um
crescente número de publicações nos ultimos anos.
Na seção 2 é discutido o conceito de segurança da informação, seguido da
definição de teste baseado em modelos e da sua taxonomia (3) e de revisão sistemática (4).
Após isso, na seção 5, são mostradas as questões de pesquisa, bases de dados e strings de
busca usadas neste estudo sistemático. Os resultados obtidos são discutidos na seção 6.
Em 7 são expostas as ameaças a validade deste estudo e por fim, em 8, são mostradas as
conclusões deste estudo.
2. Segurança da Informação
Segurança da informação é a área da computação que lida com o entendimento das
diversas questões ligadas às estratégias de defesa e ataque virtual para preservar a
confidencialidade, integridade e disponibilidade de dados e recursos computacionais
[Jang-Jaccard and Nepal 2014]. Em segurança, mecanismos como firewalls, sistemas
de detecção de intrusão e de controle de acesso [Jang-Jaccard and Nepal 2014] são usados para monitorar redes de computadores, mediar acesso a recursos e alertar eventos
anômalos, como exfiltração de dados.
Exfiltração de dados consiste no vazamento não autorizado de dados sensitivos de
sistemas [Sharma et al. 2013]. É um tipo de ameaça de difı́cil detecção, pois usualmente
utiliza-se de técnicas sofisticadas para explorar multiplos canais de comunicação, tem
levado empresas a realizar altos investimentos em segurança [Brewer 2014] e que pode se
originar tanto em indivı́duos internos quanto externos a uma organização e causar danos
financeiros significativos [Sharma et al. 2013].
3. Teste Baseado em Modelos
Teste Baseado em Modelos é uma variante de teste de software que permite automatizar
a geração de casos de teste a partir de modelos comportamentais e critérios de seleção
sistemáticos [Utting and Legeard 2007]. É uma proposta que busca solucionar alguns dos
problemas enfrentados pelas metodologias tradicionais de teste que usualmente tendem
a ser manuais, mal documentadas e custosas [Utting and Legeard 2007]. O processo de
teste baseado em modelos pode ser dividido em cinco etapas [Utting and Legeard 2007]:
Modelagem, Geração, Concretização, Execução e Análise.
Na etapa de Modelagem, a especificação do SUT é feita com modelos explı́citos
em notação formal. Statecharts e máquinas de estados finitos são exemplos de notações
de modelagem que podem ser usadas [Neto et al. 2008]. Durante a Geração, critérios de
seleção são usados para analisar os modelos do SUT e gerar casos de teste abstratos. Estes
critérios podem se basear na cobertura estrutural de um modelo, no domı́nio de entrada
ou no modelo estatı́stico do SUT [Neto et al. 2008]. Na Concretização, os casos de teste
abstratos são mapeados para um formato executável que pode ser um código interpretável
32
SAST
ou compilável [Utting and Legeard 2007]. Na Execução, os casos de teste concretos são
aplicados sobre o SUT. Esta etapa pode ser combinada com a concretização, sendo então
denominado teste online. Casos de teste também podem ser convertidos para formatos não
executáveis, como relatórios [Utting and Legeard 2007]. Na Análise, os resultados obtidos durante a execução são avaliados com ajuda de um mecanismo denominado oráculo
de teste que determina a aprovação ou falha de casos de teste [Ammann and Offutt 2008].
3.1. Taxonomia do TBM
Idealmente, o desenvolvimento ou adoção de uma abordagem TBM deve ser feito de
forma criteriosa e embasada nas necessidades do testador, caracterı́sticas do SUT e
limitações de projeto [Utting and Legeard 2007]. Para auxiliar nisso, a taxonomia proposta em [Utting and Legeard 2007] pode ser usada para caracterizar abordagens de
TBM. A taxonomia TBM, ilustrada na Figura 1, possui sete dimensões: Assunto, Independência, Caracterı́sticas, Paradigma, Critério de Seleção de Testes, Tecnologia e Online/Offline.
Figura 1. Taxonomia do Teste Baseado em Modelos [Utting and Legeard 2007]
Assunto diz respeito ao elemento descrito que pode ser o SUT e/ou seu ambiente.
Independência descreve a origem do modelo que pode ser a própria especificação do SUT
ou ser independente dela. Caracterı́stica descreve o comportamento modelado que pode
ser determinı́stico, de tempo real, entre outros. Paradigma diz respeito à notação usada
na modelagem. Critério de seleção de testes define o critério de cobertura do modelo.
Tecnologia diz respeito ao potencial de automação. Online/Offline descreve a execução
dos casos de teste. TBM também pode combinar múltiplas caracterı́sticas de modelo,
paradigmas, critérios de seleção e tecnologias [Ammann and Offutt 2008].
33
SAST
4. Revisão Sistemática
Revisão sistemática (RS) é o termo utilizado para descrever metodologias de pesquisa voltadas para a coleta e analise de evidências sobre tópicos de estudo especı́ficos
[Biolchini et al. 2005]. Uma RS permite resumir evidências sobre fenômenos ou tecnologias, identificar lacunas de pesquisa e fornecer um arcabouço de conhecimento que
posicione novas propostas de pesquisa [Kitchenham and Charters 2007]. Ela pode ser
descrita em três etapas: Planejamento, Condução e Documentação.
No Planejamento, definem-se os objetivos e o protocolo da RS. Questões de pesquisa (do inglês, Research Question - RQ), strings e bases de busca, critérios de inclusão,
exclusão e extração de dados são definidos nesta etapa. Posteriormente, na Condução, é
realizada a busca dos estudos. Os estudos encontrados são analisados usando critérios de
inclusão e exclusão e, posteriormente, são extraı́dos dados que ajudem a responder as RQs
assim como pré-estabelecido no protocolo. Após a condução, durante a Documentação,
as informações obtidas são organizadas na forma de um relatório ou artigo cientı́fico.
Materiais suplementares podem ser disponibilizados para complementar a RS e viéses e
ameaças à validade também devem ser evidenciados e discutidos.
5. Execução da Revisão Sistemática
Para esta RS foi estabelecido o objetivo de categorizar os estudos que apliquem TBM
no teste de segurança de serviços baseados em mobilidade, virtualização e conectividade
segundo a taxonomia do TBM. A partir disso, foram definidas as seguintes questões de
pesquisa:
RQ1 Que resultados o uso de TSBM em serviços ligados a mobilidade, virtualização
ou conectividade tem proporcionado?
RQ2 Quais as caracterı́sticas predominantes nos estudos de TSBM?
RQ2.1 Considerando a taxonomia do TBM, como as abordagens de TSBM podem ser
categorizadas?
RQ2.2 Que tipo de SUTs estas abordagens utilizam em seus estudos empı́ricos?
RQ2.3 Quais as desvantagens e limitações destes estudos?
RQ2.4 Estes estudos podem ser aplicados no tratamento de exfiltração de dados?
Para responder as questões supracitadas, a string de busca de
[Dias Neto et al. 2007], uma RS sobre TBM em um nı́vel mais geral, foi adaptada
usando termos relacionados à segurança da informação, vazamento e exfiltração de
dados. Exfiltração de dados foi incluı́da pois ela é considerada uma ameaça crı́tica
e decisiva em ataques virtuais [Sharma et al. 2013] e, para garantir a segurança de
sistemas computacionais, mecanismos de segurança devem passar por processos de teste
criteriosos. A string de busca definida foi: (”security testing”OR ”security”OR ”data
exfiltration”OR ”data extrusion”OR ”data theft”OR ”data leakage”OR ”intrusion”OR
”malware”OR ”vulnerability”) AND (”threat modeling”OR ”model based”OR ”model
based testing”OR ”model based security testing”)
A string de busca foi adaptada e aplicada nas bases IEEE Xplore Digital Library,
ScienceDirect, ACM Digital Library e SpringerLink. Os artigos retornados foram gerenciados usando o software Mendeley Desktop 1 e uma planilha eletrônica para extração de
dados.
1
http://www.mendeley.com/
34
SAST
A seleção dos estudos foi dividida em duas etapas. Na primeira fase os artigos retornados tiveram o tı́tulo, resumo e palavras-chave analisados para identificar quais necessariamente discutiam teste baseado em modelos, realizavam algum experimento e abordavam alguma questão ligada a segurança da informação. Estudos não inseridos nesta
categoria foram automaticamente excluı́dos. Na segunda etapa, estudos duplicados ou
com menos de 3 páginas foram descartados. Este número mı́nimo de páginas foi estabelecido a fim de remover resumos e short papers desta análise.
Após a identificação, os estudos foram analisados visando extrair informações relacionadas as dimensões da taxonomia do TBM [Utting and Legeard 2007]. Além disso,
o tipo de ameaça tratada pela técnica, o tipo de SUT e a possibilidade de ser aplicado
no teste de serviços baseados em mobilidade, conectividade ou virtualização ou no tratamento de exfitração de dados também foram extraı́dos.
6. Resultados
Ao ser aplicada a string de busca nas bases de artigos, foi obtido um total de 227 artigos.
Desses 227, aproximadamente 22% foram oriundos da IEEE Xplorer, 38% da ScienceDirect, 38% da Springer e 2% da ACM. Eles tiveram seus tı́tulos, resumos e palavras-chave
lidos e avaliados segundo os critérios de inclusão e exclusão estabelecidos. Nesta primeira
etapa da análise, foram eliminados cerca de 78% dos estudos, restando 50 artigos.
Na segunda etapa, os 50 artigos foram reanalisados visando identificar aqueles que
realmente discutissem TSBM e realizassem experimentos. Após esta segunda avaliação,
restaram 23 artigos. Estes 23 artigos foram analisados a fim de extrair informações que
evidenciassem sua relação com a taxonomia do TBM. Foram extraı́dos destes estudos, o
tı́tulo do artigo, base de origem, ano de Publicação, as informações que correspondessem
as dimensões da taxonomia TBM (Assunto, Independência, Caracterı́sticas, Paradigmas,
Critérios de Seleção, Tecnologia e Online/Offline), tipo de ameaça modelada, tipo de
SUT testado, relação com mobilidade, virtualização, conectividade e exfiltração de dados,
vantagens, desvantagens e limitações, sempre que estas informações fossem encontradas.
Ao término da extração, os dados extraı́dos foram analisados a fim de responder as RQs.
Na tabela 1 podem ser vistos o tı́tulo, ano de publicação e base de origem dos 23 estudos
retornados pelas bases ACM, IEEE Xplorer (IEEE), ScienceDirect (SD) e Springer.
6.1. Questões de Pesquisa
Com relação a RQ1, foi identificado que o TSBM permitiu a especificação do comportamento de atacantes e de sistemas [Salas et al. 2007], uma redução na ambiguidade
do plano de testes [Barletta et al. 2011] e facilitou a geração [Fourneret et al. 2011] e
replicação [Xu et al. 2012] de testes.
Além disso, 7 dentre os 23 trabalhos foram categorizados como possibilitando o reuso de modelos de especificação, como RFCs (Request for Comments)
[Rütz and Schmaltz 2011]. Vale ressaltar que este número aumenta se for considerado
que 2 trabalhos incluiram reuso em seus trabalhos futuros [Bozic and Wotawa 2013]
[Lebeau et al. 2013]. Outro ponto identificado foi que praticamente todos os estudos permitiam a modelagem tanto de dados de entradas como de saı́da de SUTs. Isso mostra o
poder de automação que abordagens de TBM para segurança podem proporcionar.
35
SAST
Tabela 1. Lista dos 23 estudos identificados
Tı́tulo do Artigo
A test-based security certification scheme for web services
An Approach to Modular and Testable Security Models of Real-world Health-care Applications
A Methodology for Building Effective Test Models with Function Nets
A Model-based Approach to the Security Testing of Network Protocol Implementations
A Model-Based Fuzzing Approach for DBMS
Data vulnerability detection by security testing for Android applications
APSET, an Android aPplication SEcurity Testing tool for detecting intent-based vulnerabilities
Model-Based Vulnerability Testing for Web Applications
XSS pattern for attack modeling in testing
Testing access control and obligation policies
EMV Card: Generation of Test Cases based on SysML Models
Using Labeled Transition System Model in Software Access Control Politics Testing
Automated Security Test Generation with Formal Threat Models
An Experience Report on an Industrial Case-Study about Timed Model-Based Testing with UPPAAL-TRON
Model-Based Security Verification and Testing for Smart-cards
Mutation Analysis of Magento for Evaluating Threat Model-Based Security Testing
Verified Firewall Policy Transformations for Test Case Generation
Model-Based Security Vulnerability Testing
Test Generation from Security Policies Specified in Or-BAC
A declarative two-level framework to specify and verify workflow and authorization policies in service-oriented architectures
Fault coverage of Constrained Random Test Selection for access control: A formal analysis
A systematic approach to integrate common timed security rules within a TEFSM-based system specification
Robustness testing for software components
Ano
2013
2011
2012
2006
2013
2013
2014
2013
2013
2013
2013
2012
2012
2011
2011
2011
2010
2007
2007
2010
2010
2012
2010
Base
ACM
ACM
IEEE
IEEE
IEEE
IEEE
Springer
IEEE
IEEE
IEEE
SD
IEEE
IEEE
IEEE
IEEE
IEEE
IEEE
IEEE
IEEE
Springer
SD
SD
SD
Quanto ao contexto de aplicação, somente 6 estudos identificados aplicavam TBM no teste de serviços ligados a mobilidade [Salva and Zafimiharisoa 2014]
[Salva and Zafimiharisoa 2013], virtualização [Barletta et al. 2011] [Brucker et al. 2010]
[Wang et al. 2013] ou conectividade [Allen et al. 2006].
Com relação a RQ2, foi constatada uma tendência crescente na quantidade
de publicações ao longo dos anos (Figura 2 à esquerda). Além disso, foi identificada uma predominância de trabalhos usando modelos baseados em transição
(Figura 2 à direita), como máquinas de estados finitos [Bozic and Wotawa 2013],
autômatos finitos estendidos [Anisetti et al. 2013] [Li et al. 2007] [Yu et al. 2012] e
autômatos temporizados [Rütz and Schmaltz 2011].
Trabalhos usando variantes
de redes de petri [Xu and Chu 2012], incluı́dos na categoria de paradigma operacional [Utting and Legeard 2007], subconjuntos da Unified Modeling Language
(UML) [Lei et al. 2010] também foram identificados, assim como abordagens hı́bridas
[Anisetti et al. 2013] [Salas et al. 2007].
Figura 2. Total de publicações por ano e por paradigma
A questão RQ2.1 mostrou que nem todos os estudos apresentam claramente
informações que preencham as dimensões da taxonomia do TBM. Foi identificado que
algumas informações como critérios de seleção e tecnologia de geração de casos de teste
utilizados não estavam tão claras ou foram omitidas.
Além da dimensão Paradigma, foi possı́vel extrair de todos os estudos o Assunto
36
SAST
descrito nos modelos onde somente 1 dos 23 estudo foi categorizado como apoiado na
modelagem do SUT e do seu ambiente [Lebeau et al. 2013] e os demais foram categorizados como apoiando somente a modelagem do SUT. A Independência predominante
foi de modelo separado. As dimensões Caracterı́sticas de modelo, Critério de seleção
de teste, Tecnologia e Online/Offline não estava clara em todos os estudos. Dos estudos em que estas informações puderam ser extraı́das, percebeu-se uma predominância
de abordagens de teste offline, do uso de tecnologias de geração de testes baseadas em
busca e em execução simbólica, critérios de seleção de cobertura estrutural e de modelos
expressando caracterı́sticas determinı́sticas, de tempo real e eventos discretos. O fato destes estudos não terem evidente certas informações pode dificultar a realização de estudos
sistemáticos.
No contexto da RQ2.2, foi identificada uma predominância de 74% de estudos experimentais usando sistemas reais ou de grande porte como SUT. Dentre os SUTs foram encontrados programas para smart-cards [Fourneret et al. 2011]
[Ouerdi et al. 2013], clientes FTP open-source [Hsu et al. 2008], softwares da área de
saúde [Brucker et al. 2011], polı́ticas de segurança de firewalls [Brucker et al. 2010],
aplicações móveis reais [Salva and Zafimiharisoa 2014] [Salva and Zafimiharisoa 2013],
sistemas bancários [Xu et al. 2013], gerenciadores de conteúdo [Thomas et al. 2011] e
sistemas de tempo real [Mammar et al. 2012]. Isso mostra que TSBM é potencialmente
usável no contexto de sistemas reais.
Quanto a RQ2.3, foi constatado que algumas das abordagens não cobrem o processo de TBM por completo, da modelagem à geração de casos de teste concretos. O
estudo de [Ouerdi et al. 2013], por exemplo, não cobre a geração de casos de teste executáveis. O reuso de modelos também é citado como limitação em alguns dos estudos
[Bozic and Wotawa 2013] [Lebeau et al. 2013] porém é incluı́do como trabalhos futuros.
O esforço para a modelagem dos sistemas e do comportamento de atacantes também é
citado como uma desvantagem [Xu et al. 2012].
Quanto a RQ2.4, nenhum estudo tratou especificamente sobre exfiltração. Entretanto, alguns afirmam permitir a modelagem de ameaças como a “quebra de sigilo
de dados” e de requisitos de confidencialidade [Xu et al. 2012] [Anisetti et al. 2013]
[Wang et al. 2013] que possuem relação com a exfiltração de dados. Isso sugere que o
TBM talvez possa ser usado para mitigar ou detectar este tipo de ameaça.
7. Ameaças à Validade
O fato da string de busca desta RS ter considerado somente alguns termos da usada em
[Dias Neto et al. 2007] foi identificado como uma ameaça que pode ter limitado o alcance
deste trabalho. Entretanto, a decisão de descartar uma parte dos termos se embasou no
fato que durante um estudo piloto percebeu-se uma grande quantidade de artigos não
relacionados a TBM para segurança sendo retornada. A não inclusão de termos referenciando notações especı́ficas, como “máquinas de estados finitos” e “redes de petri”, também
pode ter limitado o alcance desta RS. Entretanto, considera-se em um trabalho futuro a
extensão desta string com sinônimos para TBM e nomes de notações de modelagem de
SUT especı́ficas.
37
SAST
8. Conclusão
Há um número crescente de publicações sobre teste de segurança baseado em modelos.
Os estudos identificados permitiram automatizar a geração e replicação de casos de testes
de segurança e redução de ambiguidade no projeto. Entretanto, o fato de haver um maior
esforço na modelagem pode afetar sua usabilidade e interferir na sua adoção.
As produções cientı́ficas identificadas usam sistemas reais como sistema em teste
onde tanto o comportamento esperado como os dados de entrada são modelados. Vários
tipos de notações são utilizadas para descrever sistemas em teste. Entretanto, foi identificada uma predominância de abordagens usando modelos baseados em transição, como
máquinas de estados finitos.
Nem todos os estudos puderam ser categorizados usando as dimensões da taxonomia de [Utting and Legeard 2007] pois muitas das informações não estavam claras ou
explicitadas. Os resultados obtidos apontam que é pequena a quantidade de estudos descrevendo suas abordagens por completo, considerando a explicitação das dimensões da
taxonomia teste baseado em modelos como parâmetro de completude. Isso pode dificultar
a execução de revisões e mapeamentos sistemáticos que tenham como foco dimensões da
taxonomia que não tenham sido totalmente identificadas neste estudo.
Além disso, foi identificada uma lacuna de pesquisas em teste baseado em modelos aplicado na mitigação e detecção de exfiltração de dados. Como trabalhos futuros,
considera-se a realização de uma outra revisão sistemática extendendo a string de busca
com termos relacionados a notações de modelagem especı́ficas, como “máquinas de estados”, “redes de petri” entre outros, ampliando o seu alcance.
Referências
Allen, W., Dou, C., and Marin, G. (2006). A model-based approach to the security testing
of network protocol implementations. In Local Computer Networks, Proceedings 2006
31st IEEE Conference on, pages 1008–1015.
Ammann, P. and Offutt, J. (2008). Introduction to Software Testing. Cambridge University
Press.
Anisetti, M., Ardagna, C. A., Damiani, E., and Saonara, F. (2013). A test-based security
certification scheme for web services. ACM Trans. Web, 7(2):5:1–5:41.
Barletta, M., Ranise, S., and Viganò, L. (2011). A declarative two-level framework to specify and verify workflow and authorization policies in service-oriented architectures.
Service Oriented Computing and Applications, 5(2):105–137.
Biolchini, J., Mian, P. G., and Natali, A. C. C. (2005). Systematic review in software engineering. Technical Report RT-ES 679/05, COPPE/UFRJ, Rio de Janeiro, RJ, Brasil.
Bozic, J. and Wotawa, F. (2013). Xss pattern for attack modeling in testing. In Automation
of Software Test (AST), 2013 8th International Workshop on, pages 71–74.
Brewer, R. (2014). Advanced persistent threats: minimising the damage. Network Security, 2014(4):5 – 9.
Brucker, A., BruÌgger, L., Kearney, P., and Wolff, B. (2010). Verified firewall policy
transformations for test case generation. In Software Testing, Verification and Validation (ICST), 2010 Third International Conference on, pages 345–354.
38
SAST
Brucker, A. D., Brügger, L., Kearney, P., and Wolff, B. (2011). An approach to modular
and testable security models of real-world health-care applications. In Proceedings of
the 16th ACM Symposium on Access Control Models and Technologies, SACMAT ’11,
pages 133–142, New York, NY, USA. ACM.
Dias Neto, A. C., Subramanyan, R., Vieira, M., and Travassos, G. H. (2007). A survey on
model-based testing approaches: A systematic review. In Proceedings of the 1st ACM
International Workshop on Empirical Assessment of Software Engineering Languages
and Technologies, WEASELTech ’07, pages 31–36, New York, NY, USA. ACM.
Fourneret, E., Ochoa, M., Bouquet, F., Botella, J., Jurjens, J., and Yousefi, P. (2011).
Model-based security verification and testing for smart-cards. In Availability, Reliability and Security (ARES), 2011 Sixth International Conference on, pages 272–279.
Hsu, Y., Shu, G., and Lee, D. (2008). A model-based approach to security flaw detection
of network protocol implementations. In Network Protocols, 2008. ICNP 2008. IEEE
International Conference on, pages 114–123.
Jang-Jaccard, J. and Nepal, S. (2014). A survey of emerging threats in cybersecurity. Journal of Computer and System Sciences, 80(5):973 – 993. Special Issue on Dependable
and Secure Computing The 9th {IEEE} International Conference on Dependable, Autonomic and Secure Computing.
Kitchenham, B. and Charters, S. (2007). Guidelines for performing systematic literature reviews in software engineering. Technical report, Keele University and Durham
University Joint Report.
Lebeau, F., Legeard, B., Peureux, F., and Vernotte, A. (2013). Model-based vulnerability testing for web applications. In Software Testing, Verification and Validation
Workshops (ICSTW), 2013 IEEE Sixth International Conference on, pages 445–452.
Lei, B., Li, X., Liu, Z., Morisset, C., and Stolz, V. (2010). Robustness testing for software components. Science of Computer Programming, 75(10):879 – 897. Selected
papers of the 5th International Workshop on Formal Aspects of Component Software
(FACSâ08).
Li, K., Mounier, L., and Groz, R. (2007). Test generation from security policies specified
in or-bac. In Computer Software and Applications Conference, 2007. COMPSAC 2007.
31st Annual International, volume 2, pages 255–260.
Mammar, A., Mallouli, W., and Cavalli, A. (2012). A systematic approach to integrate
common timed security rules within a tefsm-based system specification. Inf. Softw.
Technol., 54(1):87–98.
Neto, A., Subramanyan, R., Vieira, M., Travassos, G., and Shull, F. (2008). Improving
evidence about software technologies: A look at model-based testing. Software, IEEE,
25(3):10–13.
Ouerdi, N., Azizi, M., louis Lanet, J., Azizi, A., and Ziane, M. (2013). Emv card: Generation of test cases based on sysml models. IERI Procedia, 4(0):133 – 138. 2013 International Conference on Electronic Engineering and Computer Science (EECS 2013).
39
SAST
Rashid, A., Ramdhany, R., Edwards, M., Kibirige, S. M., Babar, A., Hutchison, D., and
Chitchyan, R. (2013). Detecting and preventing data exfiltration report. http://
goo.gl/epKO48. Acessado em 10 de maio de 2014.
Rütz, C. and Schmaltz, J. (2011). An experience report on an industrial case-study about
timed model-based testing with uppaal-tron. In Software Testing, Verification and Validation Workshops (ICSTW), 2011 IEEE Fourth International Conference on, pages
39–46.
Salas, P., Krishnan, P., and Ross, K. (2007). Model-based security vulnerability testing.
In Software Engineering Conference, 2007. ASWEC 2007. 18th Australian, pages 284–
296.
Salva, S. and Zafimiharisoa, S. (2013). Data vulnerability detection by security testing
for android applications. In Information Security for South Africa, 2013, pages 1–8.
Salva, S. and Zafimiharisoa, S. (2014). Apset, an android application security testing tool
for detecting intent-based vulnerabilities. International Journal on Software Tools for
Technology Transfer, pages 1–21.
Sharma, P., Joshi, A., and Finin, T. (2013). Detecting data exfiltration by integrating
information across layers. In 2013 IEEE 14th International Conference on Information
Reuse & Integration (IRI), pages 309–316. IEEE.
Thomas, L., Xu, W., and Xu, D. (2011). Mutation analysis of magento for evaluating threat model-based security testing. In Computer Software and Applications Conference
Workshops (COMPSACW), 2011 IEEE 35th Annual, pages 184–189.
Utting, M. and Legeard, B. (2007). Practical Model-Based Testing: A Tools Approach.
Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.
Utting, M., Pretschner, A., and Legeard, B. (2012). A taxonomy of model-based testing
approaches. Software Testing, Verification and Reliability, 22(5):297–312.
Wang, J., Zhang, P., Zhang, L., Zhu, H., and Xiaojun, Y. (2013). A model-based fuzzing
approach for dbms. In Communications and Networking in China (CHINACOM), 2013
8th International ICST Conference on, pages 426–431.
Xu, D. and Chu, W. (2012). A methodology for building effective test models with function nets. In Computer Software and Applications Conference (COMPSAC), 2012
IEEE 36th Annual, pages 334–339.
Xu, D., Sanford, M., Liu, Z., Emry, M., Brockmueller, B., Johnson, S., and To, M. (2013).
Testing access control and obligation policies. In Computing, Networking and Communications (ICNC), 2013 International Conference on, pages 540–544.
Xu, D., Tu, M., Sanford, M., Thomas, L., Woodraska, D., and Xu, W. (2012). Automated
security test generation with formal threat models. Dependable and Secure Computing,
IEEE Transactions on, 9(4):526–540.
Yu, H., Song, H., Bin, H., and Yi, Y. (2012). Using labeled transition system model in
software access control politics testing. In Instrumentation, Measurement, Computer, Communication and Control (IMCCC), 2012 Second International Conference on,
pages 680–683.
40
SAST
Heurı́sticas para seleção da população inicial de
algoritmos de teste baseado em busca para software
controlador de veı́culos autônomos
Vânia de Oliveira Neves1 , Márcio Eduardo Delamaro1 , Paulo Cesar Masiero1
1
Depto de Sistemas de Computação - ICMC
Universidade de São Paulo - São Carlos, SP - Brasil
{vaniaon,delamaro,masiero}@icmc.usp.br
Abstract. This paper presents a study conducted using logs collected in
field testing of an autonomous vehicle developed at ICMC-USP. It shows
an analysis of five logs for two of the more complex methods of the control
program and seven heuristics to generate an initial population. These heuristics are evaluated with the objective of minimizing the number of input
data and maximizing the quality of the population based on the test criteria
all-nodes and all-edges and could be used as seeds for search-based testing
algorithms.
Resumo. Neste artigo é apresentado um estudo realizado com base em
logs coletados em testes de campo de um veı́culo autônomo (SRM: sistema
robótico móvel) desenvolvido no ICMC-USP. Esse sistema executa no ambiente ROS e é programado em C++. É apresentada uma análise de cinco
logs para dois métodos mais complexos do programa e são analisadas sete
heurı́sticas propostas para gerar uma população inicial que poderia servir
como semente para algoritmos de busca. Essas heurı́sticas são avaliadas,
buscando minimizar o número de dados de entrada e maximizar a qualidade
da população com base nos critérios de teste todos-nós e todas-arestas.
1. Introdução
Um sistema robótico móvel (SRM ou MRS em inglês) é um tipo de sistema embarcado que tem como principal caracterı́stica a habilidade de se mover e operar parcial
ou completamente de maneira autônoma. Veı́culos autônomos são uma classe particular de SRM. São sistemas crı́ticos e, como tais, devem ser extremamente confiáveis,
uma vez que a ocorrência falhas pode, inclusive, causar danos ao ser humano. Como
consequência, foram criadas diferentes técnicas de teste, algumas focadas mais no
hardware e outras focadas na combinação hardware/software. O teste do software
pode usar técnicas funcionais, o que é mais comum, ou técnicas estruturais, baseadas
no código. Existem várias pesquisas relacionadas ao teste de sistemas embarcados
que buscam aumentar a cobertura do código sem ter como alvo um tipo de falha
especı́fico (Costa & Monteiro, 2013).
Um tipo de teste comum nesse ambiente é chamado de “teste de campo”,
em que certo cenário de teste é preparado (ou uma missão a ser cumprida), como
por exemplo: atingir um ponto final em uma área trafegável, a partir de um ponto
41
SAST
inicial e evitando obstáculos. Um teste como esse é avaliado principalmente de forma
funcional, verificando-se se o objetivo foi atingido ou não. Mesmo que o objetivo
tenha sido atingido, é importante também avaliar estruturalmente o código e quais
trechos foram ou não executados no teste. Durante um teste de campo, podem
ser coletados dados de entrada e armazenados em um arquivo de registro (log). É
importante notar que esse tipo de teste não usa um conjunto de dados de entradas
previamente preparado pelo testador, mas sim dados do ambiente recebidos durante
a execução do programa (ex.: imagens de uma câmera) e eles quase sempre são
diferentes em cada teste efetuado.
O contexto deste trabalho envolve o teste de veı́culos autônomos, com foco
principalmente no software que controla o componente inteligente do veı́culo. Em um
trabalho anterior, os autores deste artigo propuseram um metamodelo para apoiar
o teste de campo e apresentaram uma ferramenta de software que o implementa,
apoiando o planejamento do teste e dos cenários, coleta e armazenamento dos logs
do teste, re-execução simulada do teste e análise de cobertura do código com base
em um grafo de controle e com diferentes nı́veis de abstração da análise (Neves et al.,
2013). Como continuidade deste trabalho, a ferramenta está sendo melhorada para
permitir análises dos logs obtidos e uma forma de fazer isso é usar técnicas baseadas
em busca (McMinn, 2004; Wu et al., 2007; Yang et al., 2006) para criar logs derivados
que possam ser simulados e melhorar a cobertura original. Algoritmos desse tipo
partem de uma população inicial aleatória ou então de uma população inicial real,
como as que são coletadas em logs de testes de campo. A qualidade da população
inicial pode ser determinante para o sucesso da busca (Gordon & Arcuri, 2012).
Neste artigo é apresentado um estudo realizado com base em logs coletados
em testes de campo de um veı́culo autônomo desenvolvido no ICMC. Esse sistema
executa no ambiente ROS (ROS.org, 2014) e é programado em C++ (Mendes &
Wolf, 2013). Uma análise de cinco logs para dois métodos mais complexos do programa e de várias heurı́sticas para gerar a população inicial é apresentada. Essas
heurı́sticas são avaliadas com base em simulações usando as ferramentas descritas
acima, buscando minimizar o número de dados de entrada e maximizar a qualidade
da população com base na cobertura de nós e de arestas obtida. Embora o critério
todas-arestas inclua o critério todos-nós, considerando custos, geralmente se emprega
uma estratégia incremental, iniciando-se com todos-nós e indo para todas-arestas.
Essa população inicial será utilizada futuramente como semente para algoritmos de
teste baseado em busca para posterior geração de novos logs.
Este artigo está organizado da seguinte forma: alguns trabalhos relacionados
são brevemente discutidos na Seção 2; na Seção 3 é apresentada uma análise inicial
da cobertura obtida nos testes de campo; na Seção 4 são propostas e analisadas
sete heurı́sticas para criação da população inicial e, por fim, a Seção 5 contém as
conclusões e trabalhos futuros.
2. Trabalhos relacionados
A importância do teste de campo e do uso de logs de dados para avaliação off line
de softwares controladores de veı́culos autônomos é enfatizada por autores como
Urmson (2008) e Thrun (2006). Estratégias de redução do custo desse tipo de
42
SAST
teste são importantes e vários autores investigaram esse problema, seja no contexto
de algoritmos de busca para geração de dados de teste seja em outros contextos.
Yang et al. (2006) e Wu et al. (2007) fizeram uma ampla pesquisa sobre estratégias,
critérios e ferramentas baseadas em cobertura para o teste de sistemas embarcados
e apresentam um bom panorama sobre esse assunto.
Existem diversos trabalhos que discutem a geração de casos de teste por
algoritmos de busca, como o de Costa e Monteiro (2013), que não se preocupam
com a população inicial, quase sempre partindo de uma população gerada aleatoriamente. Uma linha de pesquisa visando melhorar a eficácia dos algoritmos baseados
em busca é a redução do domı́nio de entrada, isto é, das variáveis usadas na estratégia de busca. Harman et al. (2007) estudaram o efeito da redução do domı́nio de
entrada e apresentaram resultados da aplicação de algoritmos de busca local e global
a programas reais. Para os algoritmos evolutivos eles encontraram evidências empı́ricas de que a redução do domı́nio melhora a eficiência da busca, mas os resultados
quanto à eficácia não foram conclusivos.
A linha de pesquisa sobre redução de suites de casos de teste tem semelhanças com o estudo realizado neste artigo. Yu et al. (2008), por exemplo, aplicam
algoritmos clássicos de redução de casos de teste que se baseiam em requisitos de
teste – comandos executados, por exemplo – e depois usam essa informação para
apoiar a localização de erros no código. Uma diferença importante em relação a
este trabalho é que geralmente não existe um conjunto de casos de teste preparado
a priori, antes do teste de campo, e o objetivo da redução apresentada é outro.
Trabalhos mais próximos do apresentado são o de McMinn et al. (2012) e o de
Gordon & Arcuri (2012). Os primeiros autores investigaram estratégias para criar a
população inicial para algoritmos de geração de casos de teste especificamente para
dados do tipo string. Os segundos autores investigaram estratégias de “semeadura”
no teste de software baseado em busca. Uma dessas estratégias, a mesma que é foco
deste artigo, tem o objetivo de melhorar a população inicial da busca em termos
de diversidade e adequação para otimizar o objetivo. Eles usam um conjunto de
programas em Java para avaliar três estratégias de inicialização de população inicial
e mostram que elas podem produzir resultados muito diferentes. Estratégias desse
tipo foram implementadas na ferramenta EVOSUITE, desenvolvida pelos autores.
Eles afirmam que quando se tem algum conhecimento do domı́nio do problema,
torna-se mais fácil produzir uma população inicial. Nessa linha, informações do
domı́nio foram usadas nas heurı́sticas propostas neste trabalho.
3. Análise de cobertura de testes de campos
O programa escolhido para análise tem como objetivo dirigir um veı́culo autônomo
em uma região urbana para chegar a um determinado ponto definido por uma coordenada de GPS, evitando colisões. Ele é dotado de uma câmera estéreo que fornece
duas imagens, as quais são processadas por um método semi-estéreo global para
produzir um mapa de disparidade. Esse mapa é então convertido para uma nuvem
de pontos em 3D com base em parâmetros da câmera. A orientação da câmera em
relação ao solo é estimada pelo método RANSAC (Random Sample Consensus) e
é usado um método de detecção de obstáculos que classifica os pontos com base
43
SAST
em elevações e diferenças relativas de altura. Essas informações são usadas como
entradas para o Vector Field Histogram (VFH) que é usado para guiar o veı́culo até
o ponto de chegada (Mendes & Wolf, 2013). O diagrama de classes desse programa
é mostrado na Figura 1.
Figura 1. Diagrama de Classes
Figura 2. Grafo de Chamadas
O fluxo de execução do programa de controle do veı́culo pode ser descrito simplificadamente pelo grafo de chamadas mostrado na Figura 2. A partir do método
main() há um laço principal que recebe a leitura da câmera, faz os processamentos
descritos no parágrafo acima e toma a decisão sobre a atuação do veı́culo: acelerar, desacelerar, frenar, mudar o ângulo das rodas etc. Os dois métodos principais
do programa, responsáveis por esses cálculos e decisões são process(), da classe
cObstacleAvoidance, e calcule(), da classe cV F H. O primeiro tem 155 linhas de
código sem comentários e o segundo 153. O experimento e as análises apresentadas
neste artigo foram baseadas nesses dois métodos, pois os demais são mais simples e
pequenos, atingindo facilmente altos nı́veis de cobertura de nós e arestas.
44
SAST
Tabela 1. Dados dos logs e das coberturas dos cinco testes de campo
Log Tamanho Trechos
1
1412
283
2
680
137
3
1951
391
4
2100
421
5
2487
498
media
1726
346
Process-Nós Process-Arst Calcule-Nós
60%
46%
91%
71%
56%
93%
70%
54%
93%
71%
56%
90%
71%
56%
95%
68,6%
53,6%
92,4%
Calcule-Arst
74%
78%
77%
74%
81%
76,8%
O ambiente de execução do ROS está organizado em torno de uma arquitetura “editor-assinante” (publisher-subscriber ) e, dessa forma, as leituras da câmera
estéreo são publicadas por meio do ROS e recebidas pelo programa controlador.
Para estudar a criação de uma população inicial de casos de teste, foram conduzidos
cinco testes de campo em que um veı́culo autônomo trafegou por regiões do campus
da USP em São Carlos. Usando facilidades do ambiente ROS, foram gravados cinco
arquivos log das nuvens de pontos que correspondem às entradas dos cinco testes
de campo realizados. Também foram coletados os dados de execução do programa
e calculadas as coberturas de nós e arestas dos métodos process() e calcule(), baseado em seus Grafos de Fluxo de Controle (GFC). Para a coleta dos logs, geração
de grafos de fluxo controle e análise de cobertura foi utilizado o framework ROS,
as ferramentas trucov (Terry, 2014), gcov (Team, 2014) e a desenvolvida por Neves
(Neves et al., 2013).
As coberturas conseguidas nos cinco testes de campo para os métodos
process() e calcule() são mostradas na Tabela 1. O tamanho dos logs registrados na tabela indica o número de nuvens de pontos que foram usadas pelo programa
durante o teste. Isso corresponde principalmente ao tempo gasto para fazer os percursos do teste. Os logs podem ser usados para executar novamente o programa de
forma simulada, sempre que necessário, e foram usados neste trabalho para realizar
estudos sobre as coberturas obtidas com vistas a selecionar um subconjunto das
nuvens de ponto otimizado em relação ao tamanho e à cobertura obtida com eles.
Os critérios de teste todos-nós e todas-arestas foram usados, mas para simplificar o
texto, muitas vezes escrevemos cobertura de nós e cobertura de arestas.
Após obtidos os logs, a análise foi iniciada. Eles foram particionados em
trechos (ou subsequências) contendo aproximadamente cinco nuvens. O número de
trechos encontra-se na terceira coluna da Tabela 1. O programa foi executado de
forma simulada usando os trechos como entrada e as coberturas de nós e de arestas
de cada trecho foram calculadas. A razão para isso vem da intuição fı́sica de como
o programa se comporta quando executado: de um modo geral, em cada ciclo de
leitura da nuvem de pontos, se não há obstáculos no caminho que precisem de desvios
e mudanças de velocidade, é natural que o programa execute os mesmos comandos
computacionais e condições. Os trechos foram definidos com cinco nuvens de pontos
para que representassem uma pequena parte do percurso realizado durante o teste.
Como limite mı́nimo, cada trecho poderia ter apenas uma nuvem de pontos.
As tabelas apresentadas nas Figuras 3 e 4 mostram as coberturas individuais
45
SAST
de cada trecho do log 2 para os métodos process() e de cada trecho do log 5 para o
método calcule(), respectivamente. Tabelas semelhantes foram feitas para os outros
três logs. A ordem em que os trechos são apresentados é a mesma em que aparecem
no log completo, isto é, na ordem do percurso do teste de campo. Pode-se notar
que:
• Há uma correspondência entre as coberturas de arestas e nós e na forma geral
do contorno das barras.
• A cobertura de nós dos métodos process() e calcule() situa-se em torno de
50%, comparadas com cerca de 70% e 90% do log completo (Tabela 1).
• A cobertura de arestas dos métodos process() e calcule() situa-se em torno
de 40% a 50%, comparadas com cerca de 50% e 70% do log completo (Tabela
1).
Figura 3. Cobertura de nós (a) e arestas (b) do método process() com o log 2
particionado
Figura 4. Cobertura de nós (a) e arestas (b) do método calcule() com o log 5
particionado
No segundo passo foi feita uma análise mais detalhada das coberturas de
cada trecho, verificando-se quais nós ou arestas ela cobria e quais nós ou arestas
adicionais eram cobertos que já não haviam sido cobertos por algum dos trechos
anteriores. As tabelas foram então reorganizadas, mostrando a contribuição de cada
trecho para a cobertura acumulada (ou agregada) de todas os trechos.
Na Tabela 5 é mostrada a cobertura acumulada para o critério todos-nós
dos trechos do log 2 para o método process(). Na Figura 6 mostra-se a cobertura
acumulada para o método calcule() usando o log 5. Nota-se que em ambas as tabelas
há alguns trechos que têm uma contribuição maior para a cobertura, gerando um
salto na altura do diagrama. Esses trechos foram interpretados como aqueles em
que houve alguma mudança nas condições do percurso que levaram o programa a
46
SAST
Figura 5. Cobertura acumulada de nós do método process() para as partições do log
2
Figura 6. Cobertura acumulada de arestas do método calcule() para o log 5
percorrer outros caminhos em seu fluxo de execução. A esses trechos foi dado o nome
de trechos discriminatórios. Conforme a intuição inicial eles ocorrem em pequeno
número e podem ser bons candidatos para gerar a população inicial buscada. Com
base neles foram criadas e testadas algumas heurı́sticas.
4. Heurı́sticas para criação da população inicial: propostas e
análises
Com base nas análises apresentadas na seção anterior, foram definidas sete heurı́sticas a serem investigadas para verificar a cobertura que elas proporcionam, considerando também o número de trechos como um fator a ser minimizado. As heurı́sticas
são as seguintes:
•
•
•
•
•
•
•
H1
H2
H3
H4
H5
H6
H7
–
–
–
–
–
–
–
trechos discriminatórias de todos-nós.
trechos discriminatórias de todas-arestas.
trechos discriminatórias de todos-nós mais trechos inicial e final.
trechos discriminatórias de todas-arestas mais trecho inicial e final
trechos discriminatórias de todos-nós de todos os método sob teste.
trechos discriminatórias de todas-arestas de todos os método sob teste
Trechos escolhidas aleatoriamente.
Uma heurı́stica nula (H0), ou fator de controle, é a cobertura obtida com o log
original completo, que deve funcionar como um limitante superior. Os valores são os
da Tabela 1. A heurı́stica aleatória (H7) funciona como controle e deveria produzir
resultados inferiores às demais. Para ela foi definido um número de trechos igual à
média do número dos trechos das demais heurı́sticas e os trechos foram escolhidos
por meio de um sorteio aleatório usando um serviço na web para esse fim.
As heurı́sticas H1 e H2 são focadas em maximizar a cobertura de um método para um critério de teste. As heurı́sticas H3 e H4 são uma composição das
duas primeiras com os trechos inicial e final, considerando que nestes pontos podem
ocorrer computações diferentes do meio do percurso. A quinta heurı́stica junta os
trechos discriminatórios do critério todos-nós para todos os métodos sob teste, com
o objetivo de maximizar a cobertura de todos os métodos envolvidos no teste. A
heurı́stica H6 é semelhante à H5, mas para o critério todas-arestas.
47
SAST
No estudo apresentado a seguir foram definidos os conjuntos de trechos produzidos pelas heurı́sticas e depois eles foram usados como entrada para o programa
controlador do veı́culo autônomo do ICMC e as coberturas obtidas foram analisadas, considerando os logs, os métodos process() e calcule() e os critérios todos-nós e
todas-arestas. Como exemplo, considerando o log 2 e a heurı́stica H1 para process()
o conjunto de trechos gerado é {1,2,66,67,78}, conforme a Figura 5, para a heurı́stica
H4 seria acrescentado o trecho 137, pois o primeiro já está incluı́do. Para a heurı́stica H5, e o log 2 o conjunto seria {1,2,9,11,66,67,68,75,83,85}. H6 seria o mesmo
conjunto que o H5 para esse log.
Foram gerados setenta conjuntos de trechos (um para cada método (2), para
cada heurı́stica (7), para cada log (5)). O programa foi executado em modo de simulação e as coberturas obtidas para os dois métodos considerados foram calculadas.
As médias das coberturas são apresentadas na Figura 7 (a). A heurı́stica H0 é o log
completo. É fácil perceber que H7 (aleatório) sempre produziu resultados piores,
e que H0 é sempre superior, como esperado. Entretanto, nota-se que os resultados
conseguidos com os conjuntos de trechos discriminatórios estão muito próximos do
resultado com o log completo, apesar do tamanho muito menor de trechos/nuvens
de pontos.
Figura 7. Cobertura média obtidas com as sete heurı́sticas propostas (a) e média
do tamanho dos trechos (b)
Deve-se notar que ao executar os trechos sequencialmente, para cada uma
deles o programa é reexecutado e, portanto parte do estado inicial. Isso pode produzir resultados e coberturas um pouco diferentes da execução do log completo. No
estudo de caso realizado percebeu-se que em um determinado log a cobertura de
seu conjunto de trechos foi maior que a cobertura completa do log. O código fonte
foi analisado para determinar quais nós e arestas foram cobertos por esse trecho e
que não haviam sido cobertos no log completo. Observou-se que era um tratamento
para o caso de uma mensagem não ter sido recebida. No caso do log completo, essa
mensagem era recebida desde seu inı́cio. Pode-se concluir então que a junção de
trechos trata-se de um novo log que pode ter um comportamento diferente do log a
partir do qual foi gerado.
Considerando-se também os resultados obtidos por log (os gráficos de cada
log não são mostrados por falta de espaço), nota-se que pode haver algumas diferenças significativas da cobertura obtida, mas a média dos resultados dá uma visão
48
SAST
consistente dos resultados obtidos. A análise dos dados obtidos permitiu concluir
que os trechos iniciais são muito importantes, pois os trechos 1 ou 2 (ou ambos) apareceram como discriminatórios em todas as heurı́sticas. O trecho final não pareceu
importante, haja vista os resultados das heurı́sticas H3 e H4.
As heurı́sticas H1 e H3 geralmente têm o menor número de trechos em seu
conjunto, conforme se nota na Figura 7 (b), mas não produzem os melhores resultados. Nota-se que o conjunto de trechos de H5 (todos-nós) é um subconjunto de
H6. De um modo geral, a heurı́stica H6, que reúne os trechos discriminatórios para
o critério todas-arestas dos dois métodos sob teste, produziu os melhores resultados,
mas é a que contém o maior número médio de trechos. Esse número, entretanto, é
relativamente baixo.
Concluindo, nota-se que as heurı́sticas que envolvem a seleção dos trechos
discriminatórios de todas-arestas (H2 e H6) obtiveram os melhores resultados. Enquanto a heurı́stica H6 tem uma cobertura levemente superior à H2, esta última
possui um conjunto menor de trechos. Assim, caberia ao testador decidir qual heurı́stica utilizar levando em consideração o que seria mais importante: maior cobertura
ou número menor de trechos.
5. Conclusões
Neste trabalho foram realizadas análises da cobertura de um programa controlador
de um veı́culo autônomo baseado em logs coletados em teste de campo desse veı́culo.
Também foram propostas e avaliadas sete heurı́sticas para seleção de uma população
inicial cuja intenção é servir como semente para algoritmos de teste baseado em busca
para posterior geração de novos logs. Foram utilizados cinco logs obtidos a partir
de testes de campo e, posteriormente, esses logs foram particionados e a cobertura
atingida pelos subconjuntos de trechos foi calculada. Notou-se que com um pequeno
subconjunto desses trechos é possı́vel obter uma cobertura próxima à da execução
do log completo.
Como trabalhos futuros pretende-se realizar mais testes de campo considerando outros cenários, outros tamanhos dos trechos e também outros softwares controladores. Também pretende-se utilizar os conjuntos de trechos selecionados a partir
das heurı́sticas propostas como semente inicial para geração de novos logs utilizando
algoritmos evolutivos, criando logs derivados que satisfazem uma função de adequação (fitness), como atingir um nó ou uma aresta especı́fica, ou executar um dado
comando com a finalidade de aumentar a cobertura. Esse novo log poderia ser utilizado para simular o comportamento do veı́culo autônomo. Além disso, as heurı́sticas
podem ser úteis no teste de regressão uma vez que elas facilitam a seleção de pequenos conjuntos de trechos que podem ser armazenados juntamente com os resultados
produzidos e depois comparados quando forem feitas alterações no programa.
Agradecimentos
Os autores agradecem à FAPESP, CAPES, CNPq e INCT-SEC pelo apoio financeiro.
49
SAST
Referências
Costa, J. C. & Monteiro, J. C. (2013). Coverage-directed observability-based validation for embedded software. Trans. on Design Automation of Electronic Systems,
18(2), 1–20.
Gordon, F. & Arcuri, A. (2012). The seed is strong: Seeding strategies in searchbased software testing. In Proc. of the 5th IEEE Int. Conf. on Software Testing,
Verification and Validation (pp. 121–30). Montreal, CA: IEEE Computer Society.
Harman, M., Hassoun, Y., Lakhotia, K., McMinn, P., & Wegener, J. (2007). The
impact of input domain reduction on search-based test data generation. In Proc.
of the the 6th Joint Meeting of the European Software Engineering Conf. and
the ACM Symp. on The Foundations of Software Engineering (pp. 155–64). New
York, USA: ACM.
McMinn, P. (2004). Search-based software test data generation: A survey. Software
Testing, Verification and Reliability, 14, 105–156.
McMinn, P., Shahbaz, M., & Stevenson, M. (2012). In Search-Based Test Input
Generation for String Data Types Using the Results of Web Queries (pp. 141–50).
N: IEEE.
Mendes, C. C. T. & Wolf, D. F. (2013). In Real Time Autonomous Navigation and
Obstacle Avoidance Using a Semi-global Stereo Method (pp. 235–36). New York,
USA: ACM.
Neves, V. d. O., Delamaro, M. E., & Masiero, P. C. (2013). Structural testing of
autonomous vehicles. In Proc. of the 21th Int. Conf. on Software Engineering
and Knowledge Engineering, SEKE’13 (pp. 200–05). Boston, USA: Knowledge
Systems Institute.
ROS.org (2014). Documentation - ros. Online. Available: http://www.ros.org last access in em 26/06/2014.
Team, G. (2014). Gcov - using the gnu compiler collection (gcc). Online. disponı́vel em http://gcc.gnu.org/onlinedocs/gcc/Gcov.html - Último acesso em
31/05/2014.
Terry, N. (2014). trucov - the true c and c++ test coverage analysis tool. Online. disponı́vel em http://code.google.com/p/trucov/ - Último acesso em
31/05/2014.
Wu, X., Li, J. J., Weiss, D., & Lee, Y. (2007). Coverage-based testing of embedded
systems. In Proc. of the 2nd Int. Workshop on Automation of Software Test
(pp.7̃). Washington, DC, USA: IEEE Computer Society.
Yang, Q., Li, J. J., & Weiss, D. (2006). A survey of coverage based testing tools.
In Proc. of the Int. Workshop on Automation of Software Test (pp. 99–103). New
York, NY, USA: ACM.
Yu, Y., Jones, J. A., & Harrold, M. J. (2008). An empirical study of the effects
of test-suite reduction on fault localization. In Proc. of the 30th Int. Conf. on
Software Engineering (pp. 201–10). New York, USA: ACM.
50
SAST
A Systematic Mapping on Model Based Testing applied to
Web Systems
Silvia Regina Assis Meireles, Arilo Claudio Dias-Neto
Instituto de Computação (IComp) – Universidade Federal do Amazonas (UFAM)
Av. General Rodrigo Octávio, 6.200, Campus Universitário Senador Arthur Virgílio
Filho – Setor Norte – Manaus – CEP 69.077-000 – Manaus – AM – Brasil
{silvia, arilo}@icomp.ufam.edu.br
Abstract. Web systems have become simply fundamental in several areas. In
addition, Model-Based Testing (MBT) is an approach involves the
development of a model to generate tests. As web systems and MBT have
attracted the interest of software researcher community, it is necessary to
identify publications related to these areas. Therefore, we carried out a
systematic mapping study in order to get a body of knowledge regarding this
research field. We proposed three research questions and defined a search
protocol to support the mapping study execution. Our study selected 57 papers
from 160 papers retrieved from the defined sources. These papers were
published between 2005 and 2013. This study will support researchers to obtain
an overview of type of contribution, models, tools, test location, testing level,
among other perspectives, which are used in MBT applied to web systems.
1.
Introduction
Web applications or web systems are software systems based on technologies and
standards of the World Wide Web Consortium that provide Web-specific resources such
as content and services through a user interface, the Web browser (Kappel, 2004). Web
system development differs from traditional system development because of several
aspects, as continuous changes in user and technology requirements (Koch et al., 2007),
and content, hypertext, and presentation aspects should be considered (Kappel, 2004).
With the growing demand for complex web systems, also comes the need to find
strategies increase the product quality and reduce the cost and development time. One
way to improve the quality of such applications is applying software testing (Fasolino et
al., 2013). Generating test cases automatically can both reduce the costs and increase
the effectiveness of testing (Mariani et al., 2011). Among the strategies for software
testing automation, MBT involves developing and using a model describing the
structural and/or behavioral aspects of the system to generate test cases automatically
(Xi et al., 2008). MBT is one of most popular techniques used for testing web systems
(Garousi et al., 2013).
According to Dalal et al. (1999), MBT depends mainly on the notation used for
the data modeling, the algorithm used for test generation, and the tool infrastructure for
test generation. Some benefits in using MBT (Dias-Neto and Travassos, 2010) are:
 Lower cost and effort for testing planning/execution and shorter testing
schedule.
 Improvement of the final product quality.
 Capacity of automatically generating and running many useful tests.
51
SAST
We was interest to know regarding to MBT applied to Web system domain so it
was important to summarize and to provide an overview regarding these areas aiming at
to support future research in this field. This overview could be achieved through a
systematic mapping study (SM). We planned and performed a SM regarding the
application of MBT applied to the Web systems described in the technical literature.
In section 2 we present some related works. Section 3 shows our research
methodology, including the planning and execution of the SM. In planning section, we
describe the goals, research questions, search string, and inclusion criteria; in the
execution section we detail the selection process and form data extraction strategy. In
section 4, the results analysis is shown, describing which MBT techniques were
identified per year of publication, venues of publication, type of contribution, type of
research approach, test location, models used for test case generation, testing level,
quality characteristics, and indication of supporting tools.
2.
Related Works
In this section, we show some related works that have been reported regarding MBT
and Web Application Testing (WAT).
Dias-Neto and Travassos (2010) conducted a Systematic Literature Review
(SLR) with the purpose of identifying and characterizing MBT techniques. This SLR
carried out 271 papers appeared between 1990 and 2009. This study classified the
papers in MBT techniques using UML diagrams and MBT techniques not using UML.
At total, 219 MBT techniques were identified and characterized by category, testing
level, software category, models used for test case generation, indication of supporting
tools, the categories of Non-functional Requirements, and the complexity level of nonautomated steps composing the MBT techniques tests generation process. Finally, 18 of
219 MBT techniques could be applied to web application and web services.
Garousi et al. (2013) conducted a SM study on WAT. This study carried out 79
papers appeared between 2000 and 2010. They derived the observed trends in terms of
types of papers, sources of information to derive test cases, and types of evaluations
used in the papers. Their results showed the areas that had been covered and techniques
and tools that had been proposed in this field. Doğan et al. (2014) conducted a SLR a
follow-up complementary study of Garousi et al. (2013). This study carried out 95
papers appeared between 2000 and 2013. It indicated that WAT is an active area of
research with an increasing number of publications. They synthesized the following
data from the papers: the types of input test models, the fault models, taxonomy related
to web applications, test tools proposed, metrics used for assessing cost and
effectiveness of WAT techniques, the threats to validity, level of rigor and industrial
relevance of the empirical studies, and evidence regarding the scalability of the WAT
techniques.
3.
Research methodology
The SM protocol was developed following the guidelines published by Biolchini et al.,
(2005). We present the planning, execution and results analysis for this SM.
3.1.
Planning
The research goal was structured following the structure defined by the GQM paradigm
(Goal/Question/Metric) (Basili and Rombach, 1988). It is shown in Table 1.
52
SAST
Table 1. Research goal by GQM paradigm
Analyze
For the purpose of
With respect to their
From the point of view of the
In the context of
Model-Based Testing Techniques for Web Systems
Characterizing
Models adopted for software representation
Researcher
Academic research in software engineering
Based on the research goal, three research questions were formulated:
 Q1 - What models are used to specify|abstract|model the structure/behavior
of web systems regarding the automatic generation of test cases?
 Q2- What quality characteristics the models can represent/provide tests?
 Q3- What types of testing techniques can be applied to in a web system?
We searched in online academic paper search engines, Scopus1 and
IEEEXplore2. We also searched papers from the following software engineering and
testing research venues (not totally covered by the online international digital libraries):
Brazilian Symposium on Software Engineering (SBES), Brazilian Symposium on
Software Quality (SBQS), Brazilian Workshop on Systematic and Automated Software
Testing (SAST).
The search string was structured according to the PICO strategy (Population,
Intervention, Comparison e Outcomes) (Kitchenham and Charters, 2007).
 Population: Web systems.
 Intervention: Model-based testing.
 Comparison: Does not apply in mapping studies.
 Outcomes: Technique, approach, method, methodology, tool, and process.
The generic search string needed to be adapted to each library is shown below:



P = ("web development" OR "web software" OR "web application"
OR
"web
system"
OR
"web
engineering"
OR
"internet
engineering" OR "website" OR "web based-system" OR "web
based-application" OR "e-commerce" OR "network system" OR
"web gui")
AND
I = ("specification based test" OR "specification driven test"
OR "interface based test" OR "interface driven test" OR "gui
based test" OR "gui driven test" OR "gui test" OR "model
based test" OR "model driven test" OR "mbt" OR "uml based
test" OR "uml driven test" OR "use case driven test" OR
"requirement based test" OR "requirement driven test" OR
"scenario based test" OR "early test")
AND
O = ("technique" OR "approach" OR "method" OR "procedure" OR
"methodology" OR "tool" OR "process" OR "strategy")
Some inclusion criteria were defined to evaluate/analyze the identified studies:
 The paper must be written in English or Portuguese.
 Publications must be available on the web or contacting the authors.
1
http://www.scopus.com
2
http://ieeexplore.ieee.org
53
SAST
 Publications must describe automatic generation of test cases for web systems.
 Publications must mention the model(s) used for test cases generation.
Any paper that did not meet all inclusion criteria was excluded.
3.2.
Execution
This SM was carried out from November, 2013 until March, 2014. At total, 160 papers
were identified from the selected sources. We used The State of the Art through
Systematic Review (StArt3) tool to give support to the application for it. Firstly, the
inclusion criteria were applied to the papers identified. In this selection, the paper’s title,
abstract, and keywords were read. At total, 98 papers were selected in this phase. Next,
the second selection was carried out based on the reading of the full-papers. This phase
returned 57 papers. Each selected primary study was completely read, and pieces of
information were extracted based on the form data extraction shown in Table 2.
Table 2. Form Data Extraction
Field
Year of Publication
Venues of Publication
Type of Contribution
Type of research
Approach
Test Location
Model
Testing Level
Quality
Characteristics
Existence of tool
support
Description
Year in which the paper was published.
Venue (conference or journal) where the paper was published.
Type of contribution produced by the study. The categories are:
Model, technique, tool, and process.
It refers to the type of research approach is used in proposed paper.
These categories were used in Garousi et al. (2013): The categories
are: Solution proposal, Validation research, Evaluation research and
Industrial report.
It refers to the Computing environment for performing the tests on
web applications. The categories are: Server, Client and Both.
It refers to the model that describes the behavior or structure of the
System Under Test (SUT). The categories are: UML-diagram, State
Machine, Workflow, Petri net, Markov chains and others.
Testing level in proposed paper: Unit, Integration, System, and
Acceptance. As happened in Dias-Neto and Travassos (2010) and
Isabel (2011), Regression testing will be included in this category.
These are Quality Characteristics (ISO/IEC 9126-1) evaluated by
each paper: Reliability, Maintainability, Usability, Portability,
efficiency and functionality. It was adopted the categorization used
by Dias-Neto and Travassos (2010), in which the subcategory
security (related to Functionality group) was classified separately as
a quality characteristic. In addition, the Reliability was included to
the category Functionality.
It indicates whether the paper cites (or not) the generation of some
tool support.
We have provided the complete list of identified publications by our SM study
(and the main characteristics of the proposed MBT techniques) in an online publication
available at http://bit.ly/1j1c7qI.
3
http://lapes.dc.ufscar.br/tools/start_tool
54
SAST
4.
Results Analysis
In this section we present the results of the SM. Scopus returned a highest number of
papers (103), so it became the main repository. It was found 1 duplicated paper in own
Scopus, and after applying the inclusion criteria, 49 papers were included in final set.
IEEEXplore returned 36 papers of which 33 papers (92%) had been already in Scopus,
so we considered them as duplicated papers. We excluded the others 3 papers. Manual
sources returned 21 papers, but after applying the inclusion criteria, 8 papers were
included in the final set.
4.1.
Years of publication
The distribution of papers by publication year is shown in Figure 1. As observed, the
fifty-seven papers were published between 2005 and 2013. The years with more
publications were 2013 (16), 2011 (13), and 2012 (11).
Figure 1. Distribution of papers by publication year.
This result indicates the highest concentration of publications regarding MBT
applied to web applications in the last three years, suggesting this research topic started
recently to be more explored.
4.2.
Venues of publication
The venues with greater number of publications were: International Conference on
Software Testing, Verification and Validation (ICST, 8) and SAST (4). Others five
venues published 2 papers (each one): International Workshop on Automation of
Software Test (AST), International Computer Software and Applications Conference
(COMPSAC), European Software Engineering Conference and Symposium on the
Foundations of Software Engineering (ESEC/FSE), SBES, and SBQS. In the category
Others were found 22 papers that were published in different venues.
4.3.
Types of contribution
The analysis of types of contribution is shown in Figure 2A. Most of the studies
described a new or an existing technique (43). Fourteen papers proposed a tool that
supports partially or fully theirs technique. Few papers proposed a process or a model.
In the category Others, 7 studies compared and evaluated techniques or models. Some
studies presented more than one type of contribution. Thus, the sum of categories
discussed is above 57. For instance, eleven papers (19.3%) described both a technique
55
SAST
and a tool for supporting its technique fully or partially.
4.4.
Types of research approach
Figure 2B shows the types of research approach discussed in the selected papers. Most
approaches of research were Solution proposal, in other words they were based in a
good line of argumentation or a small example (27). The second mostly used approach
was Validation research (18), which papers contained some validation sections. Ten
papers proposed evaluation research using systematic empirical evaluations. Only two
studies presented industrial experience reports.
Figure 2. Type of (A) contribution papers; (B) research approach.
4.5.
Test location
The test location analysis is shown in Figure 3. Most of the papers discussed tests
occurring on server side (34), but many studies performed on tests both server-side and
client-side. Five papers discussed testing on client side. There was one study which we
cannot identify the test location, because its focus was to compare different techniques.
Figure 3. Distribution of MBT techniques by test location.
4.6.
Models used by MBT techniques
Figure 4 shows the models representing the behavior/structure of web system used by
MBT techniques. The main models adopted for test case generation were UML
diagrams and States machines with 14 papers, each one. There were several UML
diagrams for it, for instance, Class, Use Case, Acitivty, Statechart and Profile Test.
They were used alone or combined. Workflow-based models were used in 8 papers.
56
SAST
Finally, some techniques used petri nets (4 papers) and Markov chains (3 papers). In the
category Others, 14 papers described different category of models, including Grammars,
Object Z and requirement specifications.
Figure 4. Distribution of models used by MBT techniques.
4.7.
Testing levels
Figure 5 shows the testing levels distribution to selected papers. We can observe the
system testing level has been more applied by researchers in MBT applied to web
applications (43). Next, 21 papers focused on test of pages, classes or methods in unit
testing level. Eight papers referred to integration of units, such as pages and classes. Six
papers described techniques for Regression Testing. Only 2 papers focused acceptance
test level. Some studies presented more than one testing level. Thus, the sum of
categories presented in Figure 5 is above 57.
Figure 5. Distribution of MBT techniques by Testing Levels.
4.8.
Software Quality Characteristics
Some studies discussed the analysis of more than one software quality characteristic,
justifying the high number in Figure 6. The web applications’ functionality is dealt in 33
studies, in which many of the approaches check the application navigation flow for
proper processing and integrity of links. Eight studies focused on usability testing,
checking how easy is to use the application. Eight studies concerned in security testing,
where application vulnerabilities were evaluated and their ability to prevent attacks by
injecting malicious code. We identified 6 studies dealing with web applications’
maintainability. Few papers discussed the efficiency and portability of the application.
57
SAST
Figure 6. Software quality characteristics in the selected papers.
4.9.
Support Tools
Figure 7A shows the analysis whether the selected papers show some support tool.
Thirty-eight papers did not provide any tool support. On the other hand, 19 papers
described a tool to full or partial support of the proposed technique.
We present the tools/frameworks for supporting the selected MBT techniques
with at least two citations (Figure 7B). The most used tool was Eclipse4, an integrated
development environment used to build applications. Next, JUnit5 is a framework to
write repeatable tests for the Java language. Seven studies used Selenium6 tool, a
framework to support testing for web application using browsers or backend tests.
Olther tools were HtmlUnit7, Rational Rose8, Test Suite Designer (Belli et al., 2012),
TaRGeT (Silva et al., 2011), GɏST (Koopman et al., 2007), and ArgoUML9.
Figure 7. (A) Distribution of MBT techniques that provide support tools; (B) The
main support tools used by MBT techniques.
4
https://www.eclipse.org
5
http://junit.org
6
http://www.seleniumhq.org
7
http://htmlunit.sourceforge.net
8 http://www-03.ibm.com/software/products/pt/ratirosefami
9 http://argouml.tigris.org
58
SAST
5.
Discussion
As an important observation, almost half of the selected papers do not have empirical
evidence (Figure 2B). These studies present a technique and/or a tool to support its
technique and they are usually applied in toy or small applications. Therefore, these
techniques/tools have to be applied in real applications and should be assessed
empirically. Few papers present industrial experiences and it shows that MBT is not in
the software industry effectively.
We also could observe in the results with growing of development of Rich
Internet Applications and Ajax application, some processing has added to client side.
The most of studies presented test in server side, but testing in both sides are common
(Figure 3). Due to dynamic behavior these applications, testing them is a complex task.
The community researchers have been design a model to detect all states of Ajax
application when its behavior change, but this problem is still open.
We can observe in Figure 4, there are several models used by MBT approaches
for web systems. The main ones are: UML diagrams and Finite state machines. There
are several UML diagrams used with this purpose that can be used alone or combined.
State machines are adapted according to need. It is important the efficiency of these
models to describe the best usage contexts
The models to generation test case are based on formal methods. Although they
are well known and have received much attention by researchers, they have not been
established in industry (Morschhauser, 2007).
MBT was originally designed for system testing. Thus, this level comprises the
most number of publications (Figure 5). On the other hand, acceptance tests are
definitely not popular.
Finally, we noted few papers focusing on some non-functional software quality
characteristics, such as Efficiency and Portability (Figure 6). Efficiency testing of web
systems is a critical aspect, once the services have to be always available and it is hard
to know how many users will be connected to web system. About portability testing, the
wide variety of possible combinations of all components involved in running a web
application makes impracticable to test all possible usage scenarios.
6.
Conclusions and future work
In this paper, we presented a SM study on MBT applied to the Web systems domain.
Initially, we obtained a set of 160 studies from Scopus, IEEEXplore and manual
sources. Applying some inclusion criteria, 57 papers were selected. Scopus returned a
greater number of papers when compared to others. We also observed that 92% of
papers returned by the IEEEXplore had been already in Scopus.
As we followed the systematic methodology proposed by SM studies, we
believe this study is repeatable. As future work, we will analyze the advantages and
disadvantages of the models used to generate test cases from web systems using the
body of knowledge got through this work.
References
Basili, V.R. and Rombach, H.D. (1988) "The TAME project: towards improvementoriented software environments". In: IEEE Trans. Software Eng.14(6), pp.758–773.
Belli, F, Endo, A.T, Linschulte, M. and Simao, A. (2012) “A holistic approach to model
based testing of web service compositions”. Software: Practice and Experience.
59
SAST
Biolchini, J., Mian, P.G., Natali, A.C. and Travassos, G.H. (2005) "Systematic Review
in Software Engineering: Relevance and Utility". Technical Report ES-679/05,
PESC-COPPE/UFRJ. Available at http://www.cos.ufrj.br.
Dalal, S.R., Jain, A., Karunanithi, N., Leaton, J.M., Lott, C.M., Patton, G.C. and
Horowitz, B.M. (1999) "Model-based testing in practice". In: 21st international
conference on Software engineering, p.285-294.
Dias-Neto, A.C. and Travassos, G.H. (2010) "A Picture from the Model-Based Testing
Area: Concepts, Techniques and Challenges". Advances in Computers, vol. 80, p.45120.
Doğan, S., Betin-Can, A., Garousi, V. (2014) “Web Application Testing: A Systematic
Literature”, Journal of Systems and Software, vol. 91, pp. 174–201.
Fasolino, A.R., Amalfitano, D. and Tramontana, P. (2013) "Web Application Testing in
Fifteen Years of WSE". In: 15th IEEE International Symposium on Web Systems
Evolution (WSE).
Garousi, V., Mesbah, A., Betin-Can, A. and Mirshokraie, S. (2013) "A systematic
mapping study of web application testing". Information and Software Technology,
vol. 55, no. 8, pp. 1396–1374.
Isabel, S.L.S. (2011) "Selection testing approaches for web applications" (Seleção de
abordagens de teste para aplicações web). Master Thesis, COPPE. Federal University
of Rio de Janeiro. July. (In portuguese).
ISO/IEC (2002) "ISO-9126-1: Software engineering – Product Quality – Part 1 Quality
model". The International Organization for Standardization and the International
Electrotechnical Commission.
Kappel, G. (2004) "Web Engineering - Old Wine in New Bottles? Invited Talk". In: 4th
International Conference on Web Engineering, ICWE.
Kitchenham, B. and Charters, S. (2007) “Guidelines for Performing Systematic
Literature Reviews in Software Engineering”, version 2.3. Technical Report,
Evidence-Based Software Engineering (EBSE).
Koch, N., Knapp, A., Zhang, G. and Baumeister, H. (2007) "Uml-Based Web
Engineering - An Approach Based on Standards". In: Web Engineering: Modelling
and Implementing Web Applications, vol. 12, chapter 7, pp. 157-191.
Koopman, P., Achten, P., and Plasmeijer, R. (2007) “Model-based testing of thin-client
web applications and navigation input”, Lecture Notes in Computer Science
(including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in
Bioinformatics), 4902 LNCS, pp. 299–315.
Mariani, L., Pezzè, M., Riganelli, O. and Santoro, M. (2011) "AutoBlackTest:
Automatic black-box testing of interactive applications". In: 33rd International
Conference on Software Engineering, ser. ICSE 11. pp. 1013-1015.
Morschhauser, I., Lindvall, M. (2007) "Model-Based Validation Verification Integrated
with SW Architecture Analysis: A Feasibility Study". In: Aerospace Conference,
2007 IEEE, pp. 1 -18.
Silva, C., Leite, J.C. and Coelho, R. (2011) “Testes de Aceitação: Uma Abordagem
Baseada na Especificação de Casos de Uso e no Design da Interação”, Brazilian
Workshop on Systematic and Automated Software Testing.
Xi, W., Liang, G. and Huaikou, M. (2008) "An Approach to Transforming UML Model
to FSM Model for Automatic Testing". Computer Science and Software Engineering,
pp. 251-254.
60
SAST
Uma Investigação Inicial Sobre a Correlação entre Defeitos de
Software Simulados por Mutantes e Avisos Relatados por uma
Ferramenta de Análise Estática
Cláudio Antônio de Araújo1 , Márcio Eduardo Delamaro2 ,
João Carlos da Silva1 e Auri Marcelo Rizzo Vincenzi1
1
Instituto de Informática (INF) – Universidade Federal de Goiás (UFG)
Caixa Postal 131 – 74.001-970 – Goiânia – GO – Brasil
{claudioaraujo, jcs, auri}@inf.ufg.br
2
Instituto de Ciências Matemáticas e de Computação
Universidade de São Paulo
São Carlos - SP - Brasil
[email protected]
Abstract. This paper shows the initial results of an investigation of the relationship between software faults and warnings reported by a static analysis tool.
The software faults discussed in this paper are simulated by means of mutants,
and warnings are reported by FindBugs, a static analysis tool. As results obtained so far, considering the set of programs used in this work, one can mention
the indirect non-correlation and the evidence of direct correlation for some types
of software faults represented by specific mutation operators.
Resumo. Esse artigo apresenta os resultados iniciais de uma investigação sobre a correlação entre defeitos de software e avisos relatados por uma ferramenta de análise estática. Os defeitos de software discutidos neste artigo são
simulados por meio de mutantes e os avisos são relatados pela ferramenta de
análise estática FindBugs. Como resultados obtidos até o presente momento,
para o conjunto de programas utilizados neste trabalho, podem ser citados a
não correlação indireta e evidências de correlação direta para alguns tipos de
defeitos de software representados por operadores de mutação especı́ficos.
1. Introdução
Em ambiente de desenvolvimento de software, ferramentas de análise estática podem
ser utilizadas para apoiar a verificação de violações de determinados padrões de código.
Como exemplos de violações relatadas por essas ferramentas, podem ser citados: o acesso
a objetos inválidos (não inicializados), a utilização de métodos não recomendados (depreciados), a codificação em desacordo com um determinado padrão estabelecido, entre
outros.
Neste mesmo ambiente, também é comum a existência de atividades de
manutenção e desenvolvimento para encontrar (e corrigir) defeitos de software. Defeito de software (fault) é um passo, processo ou definicão de dados incorreto. Um
comando ou uma instrução incorreta presente no código é um exemplo de defeito
61
SAST
de software [IEEE 1990]. Observa-se que esse conceito é estático, pois está associado a um determinado programa ou modelo e não depende de uma execução particular [Delamaro et al. 2007].
Existem várias ferramentas de análise estática disponı́veis para programas desenvolvidos nas mais diferentes linguagens de programação. Entre elas, podem ser citadas a
StyleCop1 para programas em .NET e Lint2 para programas em C/C++. Para a linguagem
Java, podem ser citadas a FindBugs3 , a PMD4 , a CheckStyle5 , entre outras.
Apesar da utilização de ferramentas de análise estática, não há consenso dos reais
benefı́cios que estas ferramentas oferecem nas atividades de manutenção e desenvolvimento de software para que defeitos de software sejam encontrados a partir de avisos
relatados por elas.
Neste contexto, no qual são utilizadas ferramentas de análise estática e ocorrências
de defeitos em produtos de software, são apresentados, por meio deste artigo, os resultados iniciais obtidos para investigar a existência de correlação entre defeitos, simulados por
meio de defeitos semeados artificialmente, e avisos relatados pela ferramenta de análise
estática FindBugs.
Destacam-se como contribuições deste trabalho: a) a identificação da não
correlação indireta entre avisos e defeitos modelados por operadores de mutação; e b)
a identificação da existência de correlação direta entre avisos e determinadas categorias
de defeitos, representadas por operadores de mutação especı́ficos.
O restante deste artigo está organizado da seguinte forma: na Seção 2, são apresentados os conceitos básicos e os trabalhos relacionados; na Seção 3 são apresentados
os programas utilizados, o processo de coleta de dados e análise dos resultados obtidos;
na Seção 4, são relatadas as lições aprendidas; na Seção 5 são documentadas as ameaças
à validade deste estudo; e por fim, na Seção 6 as conclusões e os trabalhos futuros são
apresentados.
2. Conceitos Básicos e Trabalhos Relacionados
As atividades relacionadas a teste de software podem ser divididas em análise dinâmica
e análise estática. As atividades de análise dinâmica demandam a execução do produto
sendo avaliado. Por exemplo, as técnicas de teste podem ser classificadas como atividades de análise dinâmica. Já as atividades de análise estática avaliam o produto sem
necessidade de execução. Por exemplo, revisão e inspeção são atividades de análise
estática [Delamaro et al. 2007].
Do ponto de vista de custo, sabe-se que quanto antes um defeito for detectado, mais barato é a sua respectiva correção [Boehm & Basili 2001]. Além disso, o
fato de não exigir a execução do produto sendo avaliado torna as ferramentas que realizam análise estática atrativas. Entretanto, essas ferramentas costumam reportar uma
grande quantidade de falsos positivos, ou seja, avisos que não correspondem a defei1
http://stylecop.codeplex.com/documentation
http://www.unix.com/man-page/FreeBSD/1/lint
3
http://findbugs.sourceforge.net/
4
http://pmd.sourceforge.net/
5
http://checkstyle.sourceforge.net/
2
62
SAST
tos reais, mas que vão demandar tempo de investigação por parte do testador para sua
análise [de Araujo Filho et al. 2010]. Idealmente tais ferramentas deveriam gerar apenas
avisos para os quais a correção dos mesmos levassem à remoção de um defeito real presente no código fonte.
Para efeito dessa investigação são empregados os termos de correlação direta e
indireta, já utilizados nos trabalhos de [de Araujo Filho et al. 2010] e [Couto et al. 2013].
A correlação direta ocorre quando ao corrigir um aviso relatado por uma ferramenta de
análise estática, um defeito no código realmente é removido; já a correlação indireta é o
relacionamento entre a quantidade de defeitos de software e a quantidade de avisos relatados, ou seja, quanto mais avisos forem relatados por uma ferramenta de análise estática
maior a chance do produto de software em questão possuir defeitos que, posteriormente,
serão identificados pelo usuário final [de Araujo Filho et al. 2010].
A abordagem utilizada nos estudos apresentados em [de Araujo Filho et al. 2010]
e [Couto et al. 2013] mostra os seguintes resultados de correlação entre defeitos e avisos:
a) existência de correlação indireta; b) inexistência de correlação direta. Nesses trabalhos
foram utilizados históricos de versões armazenados nos repositórios iBugs e Fundação
Apache e relatos de defeitos de software registrados nas ferramentas Bugzilla6 e Jira7 .
Para
investigar
a
correlação
direta,
o
trabalho
apresentado
em [de Araujo Filho et al. 2010] utilizou dois programas que juntos somam 124
mil linhas de código e para os quais foram relatados 279 defeitos por meio da ferramenta
Bugzilla. No mesmo trabalho, para investigar a correlação indireta, foi utilizado um
conjunto de 25 programas da Fundação Apache, os quais somam quase dois milhões de
linhas de código e tiveram 2.983 defeitos registrados por meio da ferramenta Jira.
Estudos relacionados à qualidade de software relatam taxas de defeitos superiores,
em média, às taxas de defeitos investigadas nos trabalhos de [de Araujo Filho et al. 2010]
e [Couto et al. 2013]. Em média, é esperada que seja encontrada uma taxa de
defeitos entre 1 e 25 defeitos por mil linhas de código em produtos de software [McConnell & Johannis 2004]. Casos nos quais as taxas de defeitos são 10 vezes
menores, ou seja, taxas de defeitos entre 0, 1 e 2, 5 defeitos por mil linhas de código,
são tratados como exceções, tais como: a) taxas de 3 defeitos por 1.000 linhas de código
durante teste internos, e 0, 1 defeitos por linhas de código em produção foram reportados em [Cobb & Mills 1990]; b) aplicativos da Microsoft têm entre 10 e 20 defeitos por 1.000 linhas em testes internos e 0, 5 defeitos por 1.000 linhas de código em
produção [McConnell & Johannis 2004].
Desse modo, observa-se que uma possı́vel limitação daquele estudo é a baixa
quantidade de defeitos reais armazenados nas versões disponı́veis nos repositórios do
iBugs e da Fundação Apache. Para investigar a correlação direta foram analisados 2, 25
defeitos por mil linhas de código (279 defeitos cadastrados no Bugzilla por 124 mil linhas
de código no repositório iBugs). Para investigar a correlação indireta foram analisados
1, 60 defeitos por mil linhas de código (2.983 defeitos cadastrados no Jira por 1.862.000
linhas de código no repositório da Fundação Apache). Ou seja, as taxas de defeitos por
6
7
http://www.bugzilla.org/
https://www.atlassian.com/software/jira
63
SAST
mil linhas de código utilizadas nos trabalhos de [de Araujo Filho et al. 2010] são menores
do que as taxas médias relatadas em [McConnell & Johannis 2004].
Diante disso, é apresentado neste trabalho um experimento no qual se propõe a
utilização da técnica de teste baseada em defeitos, mais especificamente o critério análise
de mutantes (teste de mutação) [DeMillo et al. 1978]. O teste de mutação possibilita gerar
um número maior de versões de um determinado programa. Essa geração é efetuada devido às pequenas alterações automatizadas que são feitas no programa original por meio
dos operadores de mutação, que simulam os enganos mais frequentes cometidos por desenvolvedores. Para cada alteração realizada pelo operador de mutação é gerada uma nova
versão do programa original. Essa versão alterada pelo operador de mutação recebe o
nome de mutante. Do ponto de vista teórico, cada mutante representa um possı́vel defeito
que poderia estar presente no programa original [Delamaro et al. 2007]. São exemplos
de funcionamento dessa técnica: a troca de constantes por outros valores, permutação de
instruções, troca de operadores lógicos, troca de operações aritméticas, dentre outros. Na
Tabela 1 são ilustrados exemplos de possı́veis mutantes (terceira coluna) de acordo com
cada trecho de código original (segunda coluna).
Como pode ser observado na Tabela 1, o mutante exemplificado na linha 4 gerou
uma nova versão do programa original substituindo o comando de adição por divisão:
int a = b + c; por int a = b/c;.
Tabela 1. Alguns exemplos de códigos gerados por mutantes
#
1
Trecho de código original
Trecho de código mutante
int soma(int a, int b) {
return a + b;
}
int soma(int a, int b) {
return a + b++;
}
if (a == b){
///
}
if (a != b){
///
}
if (a == b & c == d){
///
}
if (a == b | c == d){
///
}
int a = c + b;
int a = c / b;
private static int saldo=0;
private int saldo=0;
2
3
4
5
Com essa técnica é possı́vel aumentar a concentração de defeitos por linha de
código com o objetivo de investigar a existência do nı́vel de correlação entre defeitos e avisos. Observa-se que, nesse caso, os defeitos são representados por mutantes gerados por
64
SAST
operadores de mutação. A opção por utilizar o teste de mutação baseia-se no fato de que
este já foi demonstrado ser um excelente modelo de defeitos reais [Andrews et al. 2005].
3. Apresentação do Experimento
Esta seção descreve o processo de coleta de dados, os programas utilizados e análise dos
resultados obtidos.
3.1. Processo Utilizado
O processo empregado para coletar os dados utilizados no experimento é apresentado a
seguir:
1. Escolha de um conjunto P de programas
2. Para cada programa pi do conjunto P
(a) Geração dos mutantes do programa pi
(b) Execução da ferramenta FindBugs no programa pi
(c) Execução da ferramenta FindBugs em cada um dos mutantes gerados
(d) Coleta de dados da execução da FindBugs dos itens (b) e (c)
3. Aplicação de métodos estatı́sticos para verificar a correlação indireta e direta
No processo empregado foram utilizados os 7 programas da Tabela 2, que juntos
somam 446 linhas de código. Esses programas foram selecionados por já terem sido
utilizados em experimentos anteriores [Polo et al. 2009]. Em seguida, para cada um dos
programas foram gerados mutantes por meio da ferramenta MuJava, utilizando-se todos
os 19 operadores tradicionais e os 28 operadores de classe [Offutt 2014]. Esse conjunto
de mutantes foi utilizado para verificar a correlação indireta e a correlação direta.
Tabela 2. Programas utilizados no experimento
#
1
2
3
4
5
6
7
8
Programa
Qtde.
Arquivos
Bisect
1
BubCorrecto
1
Ciudad
1
Find
1
Fourballs
1
PluginTokenizer
1
Triangulo
1
Total
7
Qtde.
Qtde. Linhas
Métodos
Código
3
26
7
30
23
183
4
46
2
34
16
67
5
60
60
446
Qtde.
Mutantes
138
93
289
183
221
126
429
1.489
Qtde.
Avisos
3
1
1
2
1
0
0
8
CCN
(Máx)
4
4
12
10
4
5
25
64
Na Tabela 2 são apresentadas as seguintes informações: as linhas apresentam dados sobre cada um dos programas selecionados; as colunas apresentam, por programa,
o nome do programa, a quantidade de arquivos, a quantidade de métodos, a quantidade
de linhas de código, a quantidade de mutantes gerados, a quantidade de avisos presentes
no programa original e a complexidade ciclomática máxima (calculada por meio da ferramenta JavaNCSS8 ). Por exemplo, o programa Ciudad (linha 3) tem apenas um arquivo, 23
métodos, 183 linhas de código que permitiram gerar 289 mutantes, teve 1 aviso relatado
no programa original, além de possuir complexidade ciclomática máxima de 12.
8
http://www.kclee.de/clemens/java/javancss/
65
SAST
3.2. Correlação Indireta
Para investigar a correlação indireta foi utilizado o coeficiente de correlação de postos
de Spearman (rs ). Sua principal vantagem é a possibilidade de ser aplicada a qualquer
amostra de dados. O valor do coeficiente de correlação de postos de Spearman fica entre
−1 e +1. Valor próximo de +1, 0 e −1 significam, respectivamente, correlação positiva,
ausência de correlação e correlação negativa [Triol 2008].
Aplicando a técnica de Spermam entre a quantidade de mutantes e a quantidade
de avisos da Tabela 2, tem-se o valor de correlação de −0, 151. O coeficiente obtido
indica a não existência de correlação indireta entre defeitos simulados por mutantes e
avisos relatados pela ferramenta FindBugs. Ou seja, os programas com mais avisos não
corresponderam com aqueles com mais defeitos gerados. Por exemplo: o programa Bisect
(linha 1 da Tabela 2) teve 3 avisos e gerou 138 mutantes; e o programa Triangulo (linha 7
da Tabela 2) com nenhum aviso reportado gerou 429 mutantes.
3.3. Correlação Direta
Para verificar a correlação direta entre defeitos e avisos foram utilizados os mesmos dados obtidos na análise de correlação indireta. Na Tabela 3 são exibidas as informações
relacionadas a quantidade de mutantes que foi gerada pelos operadores e a quantidade de
avisos que foi relatada exatamente na mesma linha onde ocorreu a mutação. Observa-se
que dos 47 operadores de mutação da MuJava (19 tradicionais e 28 de classe), 18 deles
(9 tradicionais e 9 de classe) geraram mutantes nos programas utilizados, ou seja, para 29
operadores restantes os programas utilizados não permitiram a geração de mutantes por
não possuı́rem as estruturas sintáticas requeridas pelos operadores.
Por exemplo, para o operador de classe JSD (linha 12) foram gerados 3 mutantes,
dos quais foram relatados 2 avisos exatamente na mesma linha na qual foi realizada a
alteração de código, ou seja, para esse operador a correlação direta foi de 66, 6%.
3.4. Resultados Obtidos e Análise
Em relação à correlação indireta, por meio do teste de correlação de postos de Spearman e
para o conjunto de programas da Tabela 2, conclui-se pela não existência de correlação indireta entre defeitos simulados por mutantes e avisos relatados pela ferramenta de análise
estática FindBugs.
Em relação à correlação direta, observam-se que os valores apresentados na Tabela
3 mostram uma variação nos resultados de correlação entre os tipos de operadores.
Conforme pode ser observado na Tabela 3, há diversos operadores, por exemplo
AODS (linha 1) e AORS (linha 5), para os quais não foi relatado nenhum aviso na mesma
linha onde ocorreu a mutação. Isso significa que a ferramenta de análise estática FindBugs
não foi capaz de detectar o defeito modelado pelo operador de mutação.
De forma geral, considerando todos os operadores, a coincidência exata entre a
linha de código na qual ocorreu a mutação e a linha da qual o warning foi relatado foi de
apenas 10, 04% (164 avisos relatados em 1.634 possı́veis).
Entretanto, os dados obtidos e apresentados na Tabela 3, para alguns operadores,
mostram uma relativa correspondência entre a linha de mutação e a linha de avisos. Isso
aconteceu no caso do operador JSD (linha 12) que, considerando o universo de programas
66
SAST
e mutantes gerados, foi responsável pela geração de 3 mutantes, dos quais 2 foram detectados por avisos, indicando uma taxa de correlação direta da ordem de 66, 7%. Outros
operadores apresentaram uma taxa de correlação direta um pouco menor, da ordem de
50%, como os nos casos dos operadores JTD (linha 14) e JTI (linha 15). Já os operadores
PRV (linha 17) e AOIS (linha 2) apresentaram taxas de correlação de 33, 33% e 16, 89%,
respectivamente.
Tabela 3. Correlação direta entre defeitos e avisos
# Operador
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
AODS
AOIS
AOIU
AORB
AORS
COD
COI
COR
EAM
EMM
JDC
JSD
JSI
JTD
JTI
LOI
PRV
ROR
Total
Média
Tipo de
Operador
Tradicional
Tradicional
Tradicional
Tradicional
Tradicional
Tradicional
Tradicional
Tradicional
Classe
Classe
Classe
Classe
Classe
Classe
Classe
Tradicional
Classe
Classe
-
Qtde. Mutantes
Gerados
14
835
108
184
30
5
70
8
50
2
26
3
55
2
2
128
3
109
1.634
90, 77
Qtde. de avisos na
mesma linha
0
141
5
4
0
0
1
0
0
0
0
2
0
1
1
3
1
5
164
9, 11
%
0, 00
16, 89
4, 63
2, 17
0, 00
0, 00
1, 43
0, 00
0, 00
0, 00
0, 00
66, 67
0, 00
50, 00
50, 00
2, 34
33, 33
4, 59
10, 04%
Consideram-se os resultados obtidos bastante promissores e espera-se que, com
o aumento no número de programas avaliados, seja possı́vel identificar outras categorias
de defeitos, representados pelos operadores de mutação, para os quais exista a correlação
direta, contribuindo para uma otimização na realização dos testes e no estabelecimento de
estratégias que combinem análise estática e dinâmica de forma mais eficiente.
4. Lições Aprendidas
A Tabela 4 apresenta uma comparação entre a abordagem utilizada em
[de Araujo Filho et al. 2010] e a abordagem por meio da técnica de mutação, empregada neste trabalho. A Tabela 4 mostra que a técnica de mutação gerou, para os
programas selecionados, em média 3, 338 defeitos para cada linha de código, equivalentemente a 3.338 defeitos por mil linhas de código, valor muito superior a média obtida
com o uso do histórico de versão. Ou seja, por mil linhas de código foram gerados em
torno de 1.500 (3.338/2, 25) vezes mais defeitos com o uso de teste de mutação do que
com o uso de histórico de versões por meio do repositório do iBugs. Espera-se que, caso
67
SAST
seja aplicado o teste de mutação sobre as 1.862.000 linhas de código, e mantendo a média
de 3, 338 defeitos por linha de código, sejam gerados em torno de 6 milhões de defeitos,
representados pelos mutantes produzidos, ao invés de 2.983 armazenados na ferramenta
Bugzilla. Desse modo, o emprego do teste de mutação permite que sejam analisadas
uma quantidade maior de dados, o que pode contribuir para um estudo mais conclusivo
sobre correlação entre defeitos de software e avisos relatados por ferramentas de análise
estática.
Como resultado do experimento apresentado, o teste de mutação mostrou, pelos
menos para os programas utilizados, a não correlação indireta entre defeitos de software
simulados por mutantes e avisos relatados pela ferramenta de análise estática FindBugs.
Para a correlação direta, o teste de mutação, conforme apresentado na Tabela 3,
mostrou uma variação de correlação direta entre os tipos de operadores, isto é, entre os
tipos de defeitos simulados por meio de mutantes. Como destaque dessa correlação têmse os seguintes operadores: JSD (66, 67%), JTD (50%), JTI (50%) e PRV (33, 33%).
Apesar da limitação do conjunto de programas utilizados, foi possı́vel identificar,
a não correlação indireta entre defeitos e avisos e indı́cios de correlação direta entre alguns
tipos de defeitos, modelados por operadores de mutação especı́ficos.
Tabela 4. Comparação da média de defeitos entre as abordagens
Abordagem
Histórico de versão para correlação direta
[de Araujo Filho et al. 2010]
Histórico de versão para correlação indireta [de Araujo Filho et al. 2010]
Mutantes
linhas de
código
124.000
Qtde.
defeitos
279
Média defeitos
por mil linhas
2, 25
1862.000
2.983
1, 60
446
1.489
3.338
5. Ameaças à Validade do Estudo
Nesta seção são apresentadas as ameaças observadas e as limitações relacionadas ao processo utilizado neste trabalho.
5.1. Validade Externa
A validade externa relaciona-se ao risco de generalizar os resultados obtidos na realização
do experimento apresentado. Neste estudo foram utilizados apenas os 7 programas apresentados na Tabela 2, que somam 446 linhas de código. Outra limitação dos programas
selecionados deve-se ao fato de que, para alguns operadores, não foi gerado nenhum mutante. Isso ocorre quando não existe no código original algumas construções esperadas
pelos operadores de mutação.
Outras limitações observadas no experimento estão relacionadas à linguagem de
programação e das ferramentas de análise estática utilizadas. No experimento foi considerado apenas a linguagem Java e, por isso, os resultados não podem ser extendidos automaticamente para outras linguagens, principalmente para aquelas de tipagem dinâmicas
68
SAST
(Ruby, PHP, etc). Com relação às ferramentas de análise estática, foi empregada apenas a FindBugs e os resultados não podem ser estendidos automaticamente para outras
ferramentas de análise estática como, por exemplo, a PMD.
5.2. Validade Interna
A validade interna relaciona-se ao controle do processo de experimentação para a coleta
dos dados analisados neste estudo. Inicialmente, foram gerados os mutantes, por meio da
ferramenta MuJava (versão 4), dos programas apresentados na Tabela 2. Para isso, foram
selecionados todos os operadores disponı́veis na ferramenta MuJava com o objetivo de
gerar a maior quantidade de mutantes (defeitos).
Em seguida, a ferramenta FindBugs (versão 2.0.3) foi utilizada com a opção “low” para que fossem relatados os avisos de qualquer prioridade. Neste nı́vel, a ferramenta FindBugs relata todos os avisos possı́veis. Para calcular o local onde ocorreu a
mutação foi necessário armazenar na base de dados a diferença textual entre cada mutante
e o programa original (diff).
5.3. Risco de Construção
O risco de construção deste trabalho reside no modelo de dados e no processo utilizado
no experimento.
Um risco relacionado ao modelo refere-se à existência de atributos e relacionamentos ausentes no modelo de dados. Para diminuir esse risco, procurou-se registrar no
modelo todos os dados necessários para verificar as correlações direta e indireta.
Para controlar o processo de experimentação e diminuir o risco de uma análise
baseada em dados incorretos, foram utilizados apenas os programas selecionados (apresentado na Tabela 2) com o objetivo de, ao mesmo tempo, validar o processo de coleta
de dados e o efetivo emprego da técnica baseada em defeitos para verificar a correlação
direta e indireta entre defeitos e avisos.
6. Conclusão e Trabalhos Futuros
Em especial, o teste de mutação utilizado nesse artigo permitiu gerar mais defeitos do que
a quantidade de defeitos utilizados em estudos semelhantes para a análise de correlação
entre defeitos e avisos [de Araujo Filho et al. 2010] e [Couto et al. 2013].
Como resultados desse estudo, para os programas utilizados, podem ser citados:
a) a inexistência de correlação indireta entre defeitos de software simulados por mutantes
e avisos relatados pela ferramenta FindBugs; b) possibilidade de existência de correlação
direta entre alguns tipos de defeitos (representados pelos tipos de operadores de mutação)
e avisos relatados pela ferramenta FindBugs. Esses resultados obtidos, em especial o de
correlação direta, pode colaborar para criar estratégias de testes com o objetivo de encontrar determinados tipos de defeitos a partir dos avisos relatados por ferramentas de análise
estática, o que pode contribuir para diminuir o custo de correção de software. Além disso,
esses resultados preliminares, embora sejam contrários aos reportados nos trabalhos de
[de Araujo Filho et al. 2010] e [Couto et al. 2013], nos motiva a expandir os estudos de
caso visando abranger um maior número de mutantes para, posteriormente, buscar melhor
classificar para quais classes de defeitos as ferramentas de análise estática são mais efetivas e quais avisos efetivamente contribuem para a localização de defeitos. Além disso,
69
SAST
para os defeitos não detectáveis por meio de análise estática é possı́vel identificar quais
critérios de teste seriam mais efetivos na sua detecção permitindo o estabelecimento de
estratégias de teste combinando as vantagens da análise estática e dinâmica visando a
maximizar a detecção de defeitos e minimizar os custos da atividade de Verificação e
Validação.
Desse modo, como trabalhos futuros pretende-se ampliar o experimento com: a)
inclusão de novos programas para investigar principalmente a correlação direta por tipo
de operador; b) inclusão de outras ferramentas de análise estática; c) extensão do experimento para outras linguagens de programação; d) realizar uma análise qualitativa detalhada sobre classes de defeitos e de avisos visando a contribuir para uma evolução das
ferramentas de análise estática e o estabelecimento de estratégias de teste incrementais.
Referências
[Andrews et al. 2005] Andrews, J. H., Briand, L. C., & Labiche, Y. (2005). Is mutation
an appropriate tool for testing experiments? In XXVII International Conference on
Software Engineering – ICSE’05, pages 402–411, New York, NY, USA. ACM Press.
[Boehm & Basili 2001] Boehm, B. & Basili, V. R. (2001). Software defect reduction top 10
list. Computer, 34(1):135–137.
[Cobb & Mills 1990] Cobb, R. & Mills, H. (1990). Engineering software under statistical
quality control. Software, IEEE, 7(6):45–54.
[Couto et al. 2013] Couto, C., Montandon, J. a. E., Silva, C., & Valente, M. T. (2013). Static
correspondence and correlation between field defects and warnings reported by a bug
finding tool. Software Quality Control, 21(2):241–257.
[de Araujo Filho et al. 2010] de Araujo Filho, J. E., de Moura Couto, C. F., de Souza, S. J.,
& Valente, M. T. (2010). Um estudo sobre a correlação entre defeitos de campo e
warnings reportados por uma ferramenta de analise estática. In IX Simposio Brasileiro
de Qualidade de Software – SBQS 2010, pages 9–23, Belem, PA.
[Delamaro et al. 2007] Delamaro, M. E., Maldonado, J. C., & Jino, M. (2007). Introdução
ao Teste de Software. Elsevier, Rio de Janeiro, RJ.
[DeMillo et al. 1978] DeMillo, R. A., Lipton, R. J., & Sayward, F. G. (1978). Hints on test
data selection: Help for the practicing programmer. IEEE Computer, 11(4):34–41.
[IEEE 1990] IEEE (1990). IEEE standard glossary of software engineering terminology.
Standard 610.12-1990, IEEE Computer Society Press.
[McConnell & Johannis 2004] McConnell, S. & Johannis, D. (2004). Code complete, volume 2. Microsoft press Redmond.
[Offutt 2014] Offutt, J. (2014). Mujava. Disponı́vel em: http://cs.gmu.edu/
õffutt/mujava/. Último acesso em 23/06/2014.
[Polo et al. 2009] Polo, M., Piattini, M., & Garcı́a-Rodrı́guez, I. (2009). Decreasing the cost
of mutation testing with second-order mutants. Softw. Test. Verif. Reliab., 19(2):111–
131.
[Triol 2008] Triol, M. F. (2008). Introdução a Estatı́stica. LTC, 10a edition.
70
SAST
Geração automática de Dados de Teste para Programas
Concorrentes com uso de Meta-heurı́sticas∗
José D. P. Silva1 , Simone R. S. Souza1 e Paulo S. L. Souza1
1
Instituto de Ciências Matemáticas e de Computação – ICMC (USP)
CEP 13566–590, São Carlos – SP – Brasil
{dario, srocio, pssouza}@icmc.usp.br
Resumo. Este artigo apresenta uma abordagem de geração automática de dados para o teste estrutural de programas concorrentes em MPI - Message Passing Interface. A meta-heurı́stica usada foi Algoritmo Genético em que a busca é
guiada por critérios de teste que consideram caracterı́sticas implı́citas de programas concorrentes. O desempenho da abordagem foi avaliado por meio da
cobertura dos testes, da eficácia em revelar defeitos e do custo de execução.
Para comparação, a geração aleatória foi considerada. Os resultados indicam
que a abordagem é equivalente em relação à cobertura do código e da eficácia
em revelar defeitos, apresentando um custo de execução maior quando comparada à geração aleatória.
1. Introdução
O teste de software tem como objetivo revelar defeitos no produto em desenvolvimento.
Uma atividade importante no processo de teste é a escolha dos dados que serão utilizados. A geração automática de dados de teste — que consiste em identificar dados de
entrada que satisfaçam um determinado critério de teste e que sejam capazes de revelar
defeitos ainda não revelados — tem como principal objetivo a redução de custo e esforço
de desenvolvimento na atividade de teste. Embora a geração automática de dados de
teste seja muito desejada, não existe um algoritmo de propósito geral capaz de gerar automaticamente um conjunto de teste que satisfaça um critério, ou seja, que cubra todos
os requisitos impostos pelo critério. Apesar disso, existem algumas propostas para apoiar
nessa atividade, tais como: geração aleatória, execução simbólica, geração com execução
dinâmica e o uso de computação evolutiva [Vergilio et al. 2007].
Search-Based Software é uma técnica de otimização que vem sendo aplicada para
apoiar a geração automática de dados de teste. Essa técnica auxilia a gerar dados de
teste, em geral, de acordo com um critério de adequação (ou função de aptidão) usando
algoritmos que são guiados por uma função de avaliação [McMinn 2004].
Vários trabalhos exploram o uso de meta-heurı́stica para geração de dados de teste,
considerando critérios de teste estruturais [McMinn 2004, Ferreira and Vergilio 2005].
Apesar de estes trabalhos considerarem programas sequenciais, eles se relacionam com o
trabalho proposto neste artigo.
Neste contexto, Ferreira e Vergilio apresentam um ambiente para geração de dados com uso de Algoritmo Genético que usa lista tabu, como memorização e métrica de
singularidade, para avaliação dos indivı́duos. O objetivo da abordagem é a geração de
∗
Trabalho desenvolvido com o apoio da Capes (DS-7907592/M) e da Fapesp: (2013/01818-7) e
(2014/14791-2).
71
SAST
dados para cobertura dos critérios estruturais para programas sequenciais com apoio de
duas ferramentas de teste. As ferramentas são responsáveis pela geração dos elementos requeridos e pela avaliação da cobertura [Ferreira and Vergilio 2005]. A abordagem
proposta neste artigo se baseou neste trabalho, mapeando as ideias para o contexto de
programas concorrentes.
No contexto de programas concorrentes novos desafios são encontrados durante
a atividade de teste. Esses programas são formados por processos concorrentes que interagem para realizar as tarefas [Almasi and Gottlieb 1994]. Essa interação pode ocorrer
de forma sincronizada ou não, sendo que esses processos podem ou não concorrerem pelos mesmos recursos computacionais. Caracterı́sticas como comunicação, sincronização
e não determinismo estão presentes nesses programas e devem ser consideradas durante
a atividade de teste. Por exemplo, um desafio relacionado à geração de dados de teste é
identificar quais são as possı́veis saı́das após a execução de um dado de teste. Devido ao
não determinismo, diferentes comunicações e sincronizações são possı́veis e podem ocorrer para um mesmo dado de teste e o desafio é identificar quais são as possibilidades e se
são corretas ou não. Isso é importante, pois é necessário estabelecer qual é a cobertura
do dado de teste em relação ao conjunto das possı́veis sincronizações entre os processos
concorrentes.
Nesta direção, este trabalho propõe uma abordagem para geração automática de
dados de teste para programas concorrentes, empregando a meta-heurı́stica Algoritmo
Genético (AG). A geração de dados de teste é guiada por critérios de teste estruturais
os quais cobrem aspectos de comunicação em programas concorrentes, os quais foram
propostos por Souza et al [Souza et al. 2008].
O artigo está organizado da seguinte maneira: Na Seção 2 é apresentado alguns
conceitos sobre teste de programas concorrentes. Na Seção 3 é descrita a geração de
dados com uso de meta-heurı́stica. Na Seção 4 é apresentada a abordagem proposta. A
Seção 5 descreve o experimento conduzido. Na Seção 7 são apresentadas as conclusões
deste trabalho.
2. Teste Estrutural de Programas Concorrentes
A comunicação e a sincronização em programas concorrentes podem seguir
dois paradigmas possı́veis: passagem de mensagem e variáveis compartilhadas
[Almasi and Gottlieb 1994]. Este trabalho considera o paradigma de passagem de mensagens. Nesse paradigma, os processos concorrentes podem executar diferentes programas e cada processo possui o seu próprio espaço de memória (memória distribuı́da).
A comunicação entre os processos pode seguir dois mecanismos básicos: comunicação
ponto a ponto, em que um processo pode enviar uma mensagem para outro processo usando primitivas como send e receive; e comunicação coletiva, em que um processo pode
enviar uma mensagem para todos os processos da aplicação (ou para um grupo).
Souza et al. propõem um modelo e um conjunto de critérios de teste estrutural
que cobrem as principais caracterı́sticas de programas concorrentes com passagem de
mensagem. Um Grafo de Fluxo de Controle (GFC) para cada processo é gerado usando
os mesmos conceitos para programas sequenciais, representando o fluxo de controle de
cada processo e, a partir de informações sobre a comunicação o GFCP (Grafo de Fluxo
de Controle Paralelo) é construı́do. O GFCP é formado pelo GFC de cada processo e por
arestas que representam a comunicação/sincronização entre os processos. Detalhes sobre
72
SAST
o modelo e critérios de teste estão fora do escopo deste artigo por questões de espaço. Os
mesmos podem ser obtidos em Souza et al. [Souza et al. 2008].
Baseando-se no GCFP e em informações sobre caminhos e associações entre
definição e uso de variáveis e mensagens, Souza et al. [Souza et al. 2008] definem
critérios de teste estruturais, que exploram o fluxo de controle, de dados e de comunicação
de programas concorrentes. O fluxo de controle e dados é similar ao aplicado em
programas sequenciais e são necessários para o teste neste contexto. Para o fluxo de
comunicação, os autores definem um novo tipo de associação s-uso, o qual é relacionado
a um uso de variável em uma comunicação ou em uma aresta de comunicação entre processos. Dentre os critérios propostos, os seguintes são considerados no desenvolvimento
da abordagem proposta neste artigo:
• todos-nós-s (tns): requer que todos os nós do GFCP com a primitiva de
comunicação send sejam cobertos pelo conjunto de teste.
• todos-nós-r (tnr): requer que todos os nós do GCFP com a primitiva de
comunicação receive sejam cobertos pelo conjunto de teste.
• todas-arestas-s (tas): requer que todas as arestas de comunicação do GFCP sejam
cobertas (ou executadas) pelo conjunto de teste.
• todos-s-usos (tsu): requer que todas as associações s-usos sejam exercitadas pelo
conjunto de caso de teste.
Os critérios acima foram escolhidos, pois são os que melhor exploram as caracterı́sticas inerentes ao paradigma de programação concorrente, ou seja, são os critérios
relacionados ao fluxo de comunicação da aplicação.
3. Geração de Dados de Teste com Uso de Meta-heurı́stica
Uma das etapas mais difı́ceis de serem automatizadas na atividade de teste é a geração de
dados, pois se trata de um problema indecidı́vel, em razão da complexidade e tamanho
dos programas. A indecidibilidade advém de algumas restrições inerentes à atividade
de teste que impossibilitam a automatização completa da fase de geração de dados
[Vergilio et al. 2007]. Em geral, essas restrições se relacionam com a efetividade dos
casos de teste gerados. Sabe-se que a qualidade da atividade de teste é dependente dos casos de teste utilizados, pois, por exemplo, dois casos de teste podem executar os mesmos
requisitos de teste, mas somente um deles ser capaz de revelar um defeito presente. Isso
é conhecido como correção coincidente. No contexto de programas concorrentes, esse
problema torna-se mais complexo, pois, dependendo das sincronizações entre os processos do programa, o defeito presente pode ou não ser revelado, conhecido como erro de
observabilidade.
Outro problema é a não executabilidade. Um caminho ou elemento é dito não
executável quando não existe valor do domı́nio de entrada que seja capaz de executálo. Assim, não existe um conjunto de dados de teste que cause a sua execução. Essa
limitação implica que nem sempre é possı́vel gerar um conjunto de dados de teste que
obtenha a cobertura de 100% dos elementos requeridos se existirem elementos não executáveis. A identificação desses elementos também é um problema, pois não é possı́vel a
sua automatização. Assim, o desafio durante a geração de dados de teste é ser capaz de
gerar dados que aumentem a qualidade da atividade de teste, frente a essas limitações.
Na literatura são encontradas diferentes técnicas que podem ser utilizadas para
gerar dados de teste. Normalmente, a efetividade dos dados de teste é avaliada
73
SAST
observando-se a capacidade desses para satisfazer critérios de teste. Dentre as técnicas
para geração de dados as mais conhecidas são: geração aleatória, geração com execução
simbólica, geração com execução dinâmica e geração com uso de meta-heurı́stica
[Vergilio et al. 2007].
O uso de meta-heurı́stica para geração automática de dados de teste é uma área
de grande interesse entre pesquisadores. Isso ocorre principalmente pelo fato de que a
geração manual de dados de teste é uma tarefa cara, difı́cil e demorada. Outra justificativa
para o uso de meta-heurı́stica é que essa técnica é uma ótima opção para lidar com o problema de indecidibilidade, o qual é inerente à geração de dados de teste [McMinn 2004].
No contexto de geração de dados de teste, meta-heurı́sticas são utilizadas para
a transformação de um critério de teste em uma função objetivo. Essa função objetivo
compara e contrasta soluções da busca em relação ao objetivo geral da mesma. Essa
informação é usada para direcionar a pesquisa em locais em que haja áreas promissoras
no espaço de busca [McMinn 2004].
Existem várias técnicas de meta-heurı́stica para geração de dados, como Subida da
Encosta, Têmpera Simulada e Algoritmos Genéticos, as quais têm apresentado resultados
promissores para programas sequenciais. Dentre essas técnicas, o trabalho proposto aqui
explora a geração utilizando Algoritmos Genéticos. Essa técnica é explicada na próxima
seção, juntamente com a abordagem proposta.
4. Geração de Dados de Teste para Programas Concorrentes
Provavelmente Algoritmo Genético (AG) é a classe mais conhecida dos algoritmos evolucionários. Segundo Holland [Holland 1975], AG são modelos computacionais que imitam os mecanismos da evolução natural para resolver problemas de otimização, os quais
podem ser aplicados em diversas áreas da ciência da computação. No contexto, deste
trabalho, explora-se o seu uso para a geração de dados de teste. De uma maneira geral,
a aplicação de AG compreende três fases: 1) codificação (ou preparação) dos dados de
interesse, 2) avaliação da população; e 3) evolução dos dados. A abordagem proposta é
apresentada a seguir, considerando essas fases e sua adaptação para o contexto de programas concorrentes.
4.1. Codificação dos dados de interesse
Para o AG, cada dado de teste é um indivı́duo na população. Assim, cada indivı́duo
é uma entrada do programa em questão. No indivı́duo, cada argumento da entrada é
representado como um bloco, cujo formato depende do tipo do argumento. Dessa forma,
se o programa possui entradas do tipo inteiro e do tipo real, o indivı́duo será representado
pela concatenação desses blocos. Essa representação é importante, pois durante a etapa
de evolução, os tipos de dados são levados em consideração para não haver erros durante
a geração de novos dados.
4.2. Avaliação da população
A avaliação da população é feita de duas maneiras: por valor de fitness e por bônus de
similaridade. Cada indivı́duo da população (dado de teste) recebe um valor de fitness, que
é calculado por meio de uma equação, a qual usa informações de um arquivo que contém
todos os requisitos cobertos por um dado x executado na ferramenta de teste. A partir
desse arquivo, a função de fitness de um indivı́duo x é obtida pela divisão dos requisitos
74
SAST
cobertos pela quantidade de requisitos de teste que precisam ser cobertos em relação a um
critério de teste.
O bônus de similaridade é um valor que cada indivı́duo da população recebe por
satisfazer requisitos de teste ainda não cobertos. Isso significa que se ele é capaz de
cobrir um requisito novo, ele recebe uma bonificação, indicando sua efetividade. Esse
bônus é calculado da seguinte forma: a partir de informações sobre elementos requeridos
cobertos por todos os indivı́duos da população, é possı́vel calcular um bônus para cada
elemento requerido x. Se poucos indivı́duos cobrem o elemento x, esse elemento recebe
uma bonificação maior. O valor final de bônus de similaridade para cada indivı́duo é a
somatória de todos os bônus atingido por ele. Dessa forma, durante a evolução, indivı́duos
com baixo valor de fitness, porém que cubram elementos requeridos inéditos, não são
penalizados.
4.3. Evolução dos dados de teste
Na fase da evolução acontece a seleção dos indivı́duos que estarão presentes na próxima
geração de população. O Algoritmo Genético apresenta três formas de evolução: por
fitness, por elitismo e por similaridade.
A evolução por fitness é um método tradicional de evolução onde a seleção dos
indivı́duos pais é feita com base no score de fitness por estes alcançados. Depois da
seleção são aplicados os operadores genéticos de mutação e crossover. O método de
seleção por roleta foi empregado, no qual os indivı́duos são representados nessa roleta
por uma porção equivalente ao seu valor de fitness. Um número aleatório é sorteado e o
indivı́duo que obtiver valor de fitness mair ou igual a este número é selecionado para a
população intermediária.
A estratégia de evolução com elitismo é uma estratégia que introduz um indivı́duo
na próxima geração baseado na lista ordenada pelo valor de fitness. Com isso é garantido
que bons indivı́duos com altos valores de fitness estarão na população.
A estratégia que usa similaridade usa uma lista ordenada pelo valor de similaridade alcançado pelos indivı́duos. Quem obtiver os maiores valores de similaridade é
selecionado.
A abordagem proposta aqui utiliza as três estratégias de evolução. Neste caso, o
testador pode configurar essas estratégias, podendo definir a quantidade de indivı́duos que
irão usar cada uma das estratégias.
4.4. Integração da abordagem proposta com ferramenta de teste ValiMPI
A abordagem proposta considera o não determinismo de programas concorrentes.
Desse modo, os dados de teste gerados precisam percorrer as diferentes sequências de
sincronização possı́veis no programa concorrente.
O AG desenvolvido trabalha em conjunto com a ferramenta de teste ValiMPI
[Hausen et al. 2007], a qual apoia a aplicação dos critérios de teste descritos na Seção 2
(Figura 1).
Quando um dado de teste é executado na ValiMPI, todas as possı́veis sequências
de sincronizações alcançadas por este dado é forçada a acontecer pelo módulo de
execução controlada existente na ferramenta. Com isso, o dado gerado possui uma prob75
SAST
abilidade maior de encontrar defeitos presentes na comunicação entre os processos concorrentes.
A integração da ferramenta ValiMPI com o AG ocorre da seguinte forma. Inicialmente, o programa a ser testado é instrumentado pela ValiMPI, gerando-se as informações
necessárias para a construção do GFCP e para coletar o trace de execução do programa.
A partir dessas informações, o módulo ValiElem gera os elementos requeridos para cada
critério de teste. O AG gera uma população inicial que é executada e avaliada na ferramenta, gerando-se informações sobre a cobertura do teste. Com base nessa informação,
o AG evolui a população que novamente é executada na ValiMPI. Esse processo continua
até o AG alcançar um critério de parada.
Fig. 1. Integração do algoritmo de geração com a ferramenta de teste ValiMPI .
5. Estudo Experimental da Abordagem Proposta
A abordagem proposta foi avaliada por meio de um estudo experimental, o qual foi
planejado e executado com base no processo de experimentação definido por Wholin
et al. [Wohlin et al. 2000]. O objetivo do estudo é avaliar a eficácia em revelar defeitos,
a cobertura alcançada e o custo de execução da abordagem proposta, considerando os
critérios de teste apresentados na Seção 2. Para efeito de comparação, a abordagem de
geração de dados aleatória foi utilizada.
O estudo considerou duas aplicações concorrentes, implementadas em C/MPI,
cada uma contendo quatro processos concorrentes: 1) Programa GCD (greatest common
divisor), o qual calcula o máximo divisor comum entre três números inteiros, e 2) Programa Mmult, que calcula a multiplicação de duas matrizes por meio da decomposição de
domı́nios. Apesar de resolverem problemas computacionalmente simples, esses problemas envolvem um conjunto expressivo de comunicação e sincronizações para a solução,
sendo que o programa GCD é composto por 7 comandos sends e 8 receives, e o programa
Mmult contém 15 comandos sends e 27 receives. Isso faz com que um número grande de
sincronizações seja possı́vel para cada programa. Por exemplo, para o programa Mmult
existem 189 sincronizações possı́veis entre os processos.
Com base no objetivo do estudo experimental, as seguintes questões de pesquisa
e hipóteses foram definidas:
76
SAST
QP1: Qual o percentual de cobertura obtido pelos dados de teste gerados pela
abordagem AG?
Hipótese Nula (H0 1): os dados gerados pelo AG têm percentual de cobertura
equivalente à técnica de geração aleatória.
Hipótese Alternativa (H1 1): os dados gerados pelo AG têm percentual de cobertura superior à técnica de geração aleatória.
Hipótese Alternativa (H2 1): os dados gerados pelo AG têm percentual de cobertura inferior à técnica de geração aleatória.
QP2: Qual a eficácia em revelar defeitos dos dados de teste gerados pela abordagem AG?
Hipótese Nula (H0 2): os dados gerados pelo AG revelam quantidade de defeitos
equivalente à técnica de geração aleatória.
Hipótese Alternativa (H1 2): os dados gerados pelo AG revelam quantidades de
defeitos superior à técnica de geração aleatória.
Hipótese Alternativa (H2 2): os dados gerados pelo AG revelam quantidades de
defeitos inferior à técnica de geração aleatória.
QP3: Qual o custo de aplicação da abordagem AG?
Hipótese Nula (H0 3): os dados gerados pelo AG têm custo equivalente à técnica
de geração aleatória.
Hipótese Alternativa (H1 3): os dados gerados pelo AG têm custo superior à
técnica de geração aleatória.
Hipótese Alternativa (H2 3): os dados gerados pelo AG têm custo inferior à
técnica de geração aleatória.
5.1. Preparação e Execução do Experimento
O seguinte ambiente foi utilizado para a execução do estudo experimental: Sistema Operacional GNU/Linux Ubuntu 10.04 (kernel 2.6.32), compilador gcc 4.1.2, Open MPI 1.4
e Java JDK 1.6.0 55 e a ferramenta de teste ValiMPI.
Durante a execução do experimento foram gerados dados para cada programa
usando o AG e a geração aleatória (GA). A fim de se obter relevância na análise estatı́stica, cada abordagem foi executada 30 vezes para cada critério de teste e a média
dessas execuções foi considerada. Diferentes tamanhos de população foram utilizados de
modo a avaliar o impacto de cada uma. Assim, para cada critério de teste foram consideradas populações contendo 10, 50 e 100 dados de teste. O AG foi configurado da seguinte
forma: número de gerações = 100, taxa crossover = 0,9 e taxa de mutação = 0,5 para todas
as configurações. Assim, o espaço de execução compreende 2 programas, 4 critérios de
teste e 3 conjuntos de teste e para cada um deles, 30 execuções foram realizadas. Isso foi
feito para as duas abordagens AG e GA.
Para avaliação da cobertura, os dados gerados foram executados na ferramenta
ValiMPI e somente os dados com melhor cobertura, para as duas abordagens, foram considerados. Para a análise da eficácia, foram considerados os defeitos inseridos por Brito et
al. [Brito et al. 2013], os quais representam defeitos tı́picos em programas concorrentes.
77
SAST
Um dos problemas durante a execução é garantir que um dado de teste execute o conjunto de sincronizações válidas para ele. Quando defeitos são inseridos, devido ao não
determinismo, o defeito pode ou não ser revelado. Assim, existem algumas alternativas
para execução determinı́stica de programas concorrentes. Neste trabalho, foi utilizada
uma técnica simples, a qual executa repetidas vezes o programa na expectativa que outras
sincronizações ocorram. É uma técnica de custo baixo que apresenta bons resultados e
portanto foi empregada neste estudo. A eficácia de cada conjunto de testes é calculada por
def r
, na qual defr é o número de defeitos revelados pelo conjunto e ndef é a quantidade
ndef
total de defeitos. O custo da abordagem AG foi calculado considerando o tempo gasto
por cada execução, medido em milissegundos.
6. Análise dos Resultados
A Tabela 1 apresenta a média de cobertura alcançada por ambas as abordagens. Os elementos não executáveis foram identificados, então a cobertura máxima é 100%. Em
negrito estão os melhores resultados, considerando sempre menor população e maior
cobertura. Para os critérios de teste mais fáceis de cobrir (critérios tns e tnr) tanto a
técnica AG e GA conseguiram bons resultados. Quando são considerados critérios mais
complexos, os quais exigem um custo maior para cobertura (critérios tas e tsu a técnica
AG obteve melhores resultados para o programa GCD. O AG atingiu a cobertura máxima
possı́vel com a configuração 10 para os dois programas para a maioria dos critérios de
teste (exceção foi o critério tsu para o programa GCD, a cobertura máxima foi obtida
com a configuração 100).
A Tabela 2 apresenta os resultados obtidos em relação à eficácia em revelar defeitos (melhores resultados em negrito). É possı́vel observar que a técnica AG obteve
melhores resultados na maioria dos casos apresentados, fornecendo indı́cios que a técnica
AG é capaz de gerar dados de teste com alta capacidade de revelar defeitos. Nota-se
que para o critério tnr a geração aleatória obteve melhores resultados. Esses resultados
motivam a exploração dessa abordagem para a geração de dados de teste.
Tab. 1. Média da cobertura dos conjuntos de teste (%).
Tab. 2. Média da eficácia dos conjuntos de teste (%).
A Tabela 3 apresenta a média de tempo de execução das abordagens AG e GA.
A fim de obter melhor visualização comparativa dos valores, a unidade de tempo adotada
78
SAST
foi de 33730,4667 milissegundos, que é a menor média de tempo obtida (critério tns do
programa GCD com GA e configuração 10). Conforme o esperado, a geração aleatória
apresenta menor tempo de execução para a maioria dos casos avaliados. Entretanto, podese observar que para o programa Mmult o tempo de execução para os critérios tns e tnr
foram menores para o AG, indicando que nem sempre essa abordagem apresenta um
maior custo.
Pode-se observar também que, apesar da geração aleatória apresentar um menor
tempo de execução, existiu vários casos que a cobertura da técnica AG com configuração
10 é equivalente à cobertura da técnica aleatória com configuração 50. Por exemplo,
para o GCD e para o critério tns, o AG obteve cobertura de 100% e tempo de 1,15
na configuração 10 e a técnica aleatória obteve 100% apenas com configuração 50 e
seu tempo de execução foi de 4,95. Assim sendo, ao comparar os tempos das duas
configurações, o AG mostrou-se mais vantajoso por obter melhor cobertura em menor
tempo.
Tab. 3. Média do tempo de execução de cada abordagem.
Para o teste estatı́stico foi considerado o Teste t. Esse teste indica se existem
evidências estatı́sticas significativas para os resultados obtidos (Tabela 4). Para a análise
estatı́stica foi admitido o nı́vel de significância de 95%, assim essa evidência se dá quando
o valor obtido para o Teste t é inferior a 0,05, onde nesse caso a H0 pode ser rejeitada.
Dessa forma, os resultados estatı́sticos para a cobertura indicam que a hipótese H0 1 foi
aceita, ou seja, que a média de cobertura de ambas as abordagens são equivalentes. Para
a eficácia, a hipótese H0 2 foi rejeitada, logo estatisticamente a técnica AG é capaz de
gerar dados de teste que revelam mais defeitos que a técnica aleatória. Para a análise do
tempo de execução a hipótese H0 3 foi aceita, indicando que a abordagem AG apresenta
um maior custo.
Tab. 4. Teste T para os Programas GCD e Mmult.
O experimento apresenta ameaça à validade externa, a qual define condições que
limitam a habilidade de generalizar os resultados de um experimento. Isso ocorre porque
foram empregados somente dois programas e os resultados podem não ser os mesmos
para outros programas, o que ocorre com a maioria dos experimentos realizados. Apesar
disso, os programas utilizados são representativos pois apresentam as caracterı́sticas mais
79
SAST
comuns presentes em aplicações concorrentes com passagem de mensagens. Além disso,
diferentes cenários de execução (variando as configurações) foram utilizados de modo a
minimizar os impactos dessa ameaça.
7. Conclusão e Trabalhos Futuros
Este artigo apresenta uma abordagem para geração automática de dados de teste que utiliza algoritmo genético, a qual é capaz de gerar dados que cobrem os requisitos de teste
dos critérios estruturais propostos para programas concorrentes. Um estudo experimental foi realizado a fim de avaliar a abordagem proposta, analisando a cobertura obtida, a
eficácia em revelar defeitos e o custo de execução da abordagem de geração comparada
com a geração aleatória de dados de teste. Os resultados indicaram que é promissor usar
geração de dados de teste no contexto de programas concorrentes, com resultados interessantes em relação à eficácia e cobertura dos requisitos de teste.
Como trabalhos futuros pretende-se investigar a aplicação de outras técnicas de
meta-heurı́stica para geração de dados de teste e como melhorar a priorização dos dados de teste para a geração de novos dados durante a evolução da técnica. Além disso,
pretende-se investigar também como tratar os elementos não executáveis, pois esses interferem no tempo de execução da técnica AG.
References
Almasi, G. and Gottlieb, A. (1994). Highly Parallel Computing. The Benjamin/Cummings Series
in Computer Science and Engineering. Benjamin/Cummings Pub. Co.
Brito, M. A., Souza, S. R., and Souza, P. S. (2013). An empirical evaluation of the cost and
effectiveness of structural testing criteria for concurrent programs. Procedia Computer Science,
18(0):250 – 259. 2013 International Conference on Computational Science.
Ferreira, L. P. and Vergilio, S. R. (2005). Tdsgen: An environment based on hybrid genetic
algorithms for generation of test data. In SEKE, pages 312–317.
Hausen, A. C., Vergilio, S. R., Souza, S. R. S., Souza, P. S. L., and Simao, A. S. (2007). A tool for
structural testing of mpi programs. In 8th IEEE Latin-American Test Workshop, Cuzco, Lima.
Holland, J. (1975). Adaptation in natural and artificial systems: an introductory analysis with
applications to biology, control, and artificial intelligence. University of Michigan Press.
McMinn, P. (2004). Search-based software test data generation: a survey: Research articles.
Software Testing Verification Reliability, 14(2):105–156.
Souza, S. R. S., Vergilio, S. R., Souza, P. S. L., Simao, A. S., and Hausen, A. C. (2008). Structural testing criteria for message-passing parallel programs. Concurrency and Computation:
Practice and Experience, 20(16):1893–1916.
Vergilio, S. R., Maldonado, J. C., and Jino, M. (2007). Geração de dados de teste. In Delamaro,
M. E., Jino, M., and Maldonado, J. C., editors, Introdução ao Teste de Software, pages 269 –
291. Elsevier.
Wohlin, C., Runeson, P., Höst, M., Ohlsson, M. C., Regnell, B., and Wesslén, A. (2000). Experimentation in Software Engineering: An Introduction. Kluwer Academic Publishers, Norwell,
MA, USA.
80
SAST
RTS Quality: Ferramenta de Análise Automatizada de
Técnicas de Seleção de Testes de Regressão Baseada em
Mineração de Repositórios de Software
João Guedes1, Uirá Kulesza1, Roberta Coelho1
Eduardo Guerra2, Lyrene Fernandes1, Felipe Alves1
1
2
Departamento de Informática e Matemática Aplicada – Universidade Federal do Rio
Grande do Norte (UFRN)
Caixa Postal 1524 – 59078-970 – Natal – RN – Brasil
Laboratório Associado de Computação e Matemática Aplicada – Instituto Nacional de
Pesquisas Espaciais (INPE)
{joao.mgcruz, guerraem, felipeapp}@gmail.com,
{uira, roberta, lyrene}@dimap.ufrn.br
Abstract. This paper investigates whether the features of the changes
performed on the source code of a system, would affect the quality of selection
made by an Regression Tests Selection (RTS), investigating the causes of such
errors. To do so, we developed a tool in the Java language to automate the
measurement of inclusion and precision averages achieved by a RTS
discriminated by a feature of the changes committed to the software
repository. To validate the tool, we evaluate the RTS technique Pythia on a
large web system, separating them by the types of tasks performed to evolve it.
Resumo. Este trabalho investiga se as características das modificações
realizadas no código-fonte de um sistema, podem afetar a qualidade da
seleção realizada por uma técnica de Seleção dos Testes de Regressão (RTS),
investigando as causas de tais erros. Para tanto, foi desenvolvida uma
ferramenta na linguagem Java para automatizar o cálculo da inclusão e da
precisão médias alcançadas por uma RTS discriminadas por uma
característica das modificações registradas em repositório de software. Para
validar a ferramenta, a técnica de RTS Pythia foi avaliada sobre um sistema
web de larga escala, discriminado pelos tipos das tarefas realizadas para
evoluí-lo.
1.
Introdução
Técnicas de testes de regressão reduzem o retrabalho de equipes de desenvolvimento de
software, reutilizando os testes já implementados nas versões anteriores do sistema.
Apesar das vantagens do reuso, reexecutar todos os testes consume tempo e recursos
excessivos. Surge então à necessidade de otimizar as soluções, garantindo que as novas
mudanças não prejudicam o comportamento das funções pré-existentes no sistema.
Segundo Yoo e Harman (2012) existem três formas de otimizar uma técnica de testes de
regressão, que envolvem a seleção, a priorização e a minimização dos casos de teste.
As técnicas de seleção dos testes de regressão (RTS – Regression Tests
Selection) [Rothermel e Harrold, 1996] visam selecionar um subconjunto dos testes da
versão anterior que sejam capazes de revelar faltas. Estudos realizados sobre técnicas de
RTS [Rothermel e Harrold, 1996][Biswas et al, 2011] avaliam o desempenho de tais
técnicas e as classificam em técnicas seguras ou não seguras, isto é, capazes de
81
SAST
identificar todos os testes necessários para a nova versão ou não, respectivamente.
Entretanto, tais estudos não investigam se o tipo de evolução ou manutenção do
software – correção de bugs, melhorias ou novas funcionalidades – pode afetar no
desempenho das técnicas de seleção dos testes. Além disso, não existem ferramentas ou
infraestrutura disponível desenvolvidas pela comunidade para apoiar a condução de
estudos de comparação de técnicas de seleção de testes de regressão.
Neste contexto, este trabalho tem como objetivos principais: (i) apresentar a
ferramenta RTS Quality desenvolvida para analisar técnicas de RTS, correlacionando as
métricas tradicionais de inclusão e precisão com o tipo de evolução realizado
(requisição de mudança); (ii) instanciar e avaliar a ferramenta, para validar suas
funcionalidades no contexto de um sistema web de larga escala; e (iii) investigar para
quais tipos de evolução a técnica de RTS Pythia [Vokolos e Frankl 1997] é mais
apropriada, dado que é considerada segura, atingindo sempre 100% de Inclusão.
2.
Fundamentação Teórica
Otimização de Técnicas de RT. Segundo Yoo e Harman (2012), existem três
diferentes formas de otimizar uma técnica de RT, que são as técnicas de: Seleção (RTS
– Regression Tests Selection), foco deste trabalho; Priorização (RTP – Regression Tests
Prioritization); e Minimização (RTM – Regression Tests Minimization).
As técnicas de RTS [Rothermel e Harrold 1996] visam selecionar um
subconjunto de testes da versão anterior capazes de revelar faltas, sem reduzir a
segurança de que testes importantes serão mantidos. As técnicas de RTM [Rothermel et
al 2002] reduzem o conjunto final dos testes necessários, para eliminar aqueles que
exercitam partes semelhantes do Sistema Sob Test (SUT – System Under Test). Por fim,
as técnicas de RTP [Rothermel, Untch e Chu 1999] ordenam os casos de teste para
maximizar alguma propriedade desejável.
Medindo Técnicas de RTS. Segundo Rothermel (1996), uma RTS separa os
testes em dois conjuntos: dos testes incluídos na regressão; e dos testes excluídos. Ele
propõe as métricas de Inclusão e Precisão (Figura 1) para medir os acertos da técnica.
(a)
(c)
𝑖𝑥 =
|𝑆 ∩ 𝐼|
× 100%
|𝐼|
𝑀𝑦𝑖 =
1
|𝑇𝑦 |
(b)
p𝑥 =
|𝑃 ∩ 𝐸|
× 100%
|𝐸|
|𝑇𝑦|
(d)
× ∑ 𝑖𝑥
𝑖=1
𝑀𝑦𝑝 =
1
|𝑇𝑦 |
|𝑇𝑦|
× ∑ 𝑝𝑥
𝑖=1
Figura 1. Equações para calcular: (a) Inclusão; (b) Precisão; (c) Inclusão Média;
e (d) Precisão Média.
Para calcular a taxa de Inclusão (𝒊) de uma tarefa (𝒙), é preciso obter os
conjuntos contendo: a relação dos testes que devem ser incluídos na seleção (𝑰) para a
tarefa (𝒙), obtidos pela intersecção dos testes não obsoletos da versão inicial com os
testes que exercitaram as modificações na versão final; e o conjunto dos testes que a
RTS selecionou (𝑺). Este cálculo é realizado através da equação da Figura 1a.
Semelhante à Inclusão, o cálculo da Precisão (𝒑) para uma tarefa (𝒙), analisa o
que a técnica de RTS acertou em excluir do conjunto de regressão, utilizando a equação
da Figura 1b. Para tanto, precisará dos conjuntos contendo: todos os testes não obsoletos
da versão inicial (𝑻); os testes que devem ser excluídos da regressão (𝑬) para a tarefa
(𝒙); e os testes que a RTS exclui da regressão (𝑷) para a tarefa (𝒙). Os conjunto 𝑬 e 𝑷
são obtido a partir de 𝑬 = 𝑻 − 𝑰 e de 𝑷 = 𝑻 − 𝑺.
82
SAST
Características das Modificações. As modificações possuem diversas
características que podem influenciar uma RTS a obter resultados equivocados, tais
como: a complexidade; o tamanho da modificação; o tamanho do impacto indireto; o
tipo da tarefa; ou o tipo da ação.
Cálculo das Médias por Tipo de Tarefa. Para descobrir se uma característica
pode afetar a RTS, é preciso correlacionar as métricas de Inclusão e Precisão com os
tipos das tarefas. Para calcular a Inclusão Média (𝑴𝒚𝒊 ), a RTS Quality agrupa as tarefas
de acordo com seus tipos (𝒚) e para cada conjunto de tipos (𝑻𝒚 ) soma todos os valores
de Inclusão (𝒊𝒙 ), dividindo o resultado pela quantidade de tarefas do conjunto (|𝑻𝒚 |),
conforme a equação da Figura 1c. A Precisão Média (𝑴𝒚𝒑 ) é calculada de forma
semelhante, utilizando a Precisão (𝒑𝒙 ) e a equação da Figura 1d.
3.
Ferramenta RTS Quality
Com o intuito de investigar e compreender as causas dos erros cometidos por uma RTS,
quando incluem testes desnecessários ou excluem testes importantes, foi proposta a
ferramenta RTS Quality para correlacionar as métricas de cada modificação com
alguma de suas características, sendo possível estipular a capacidade da RTS em
analisar modificações daquele tipo. Para tanto, este artigo propõe as métricas de
Inclusão e Precisão Médias discriminadas pela característica da modificação. Conhecer
o comportamento de várias RTSs diante de uma mesma característica permite: (i)
selecionar a melhor técnica, analisando apenas o tipo da modificação realizada; ou (ii)
conhecer as características das modificações para as quais uma RTS apresente os piores
resultados, o que permite identificar as origens de suas deficiências.
Para este trabalho, foi selecionada a característica do tipo da requisição de
mudança, pois pode ser obtido facilmente pelos testadores, realizando uma simples
consulta de qual requisição deve ser testada, e verificando qual o seu tipo, ficando a
tarefa mais difícil para a RTS Quality, que precisará minerar tal informação na base de
dados de um Sistema de Gerenciamento de Mudanças (CMT – Change Management
Tool), correlacionando as modificações realizadas com as requisições que tais
modificações atendem. Outras características podem ser analisadas, como será
apresentado mais adiante na Seção 5.
3.1.
Visão Geral
A ferramenta RTS Quality, implementada na linguagem Java, auxilia na compreensão
dos efeitos que uma característica de modificação exerce sobre uma RTS. A Figura 2
apresenta uma visão geral do seu funcionamento, que calcula as métricas de Inclusão e
Precisão [Rothermel 1996], agrupa as modificações com base em alguma característica,
e calcula as métricas de Inclusão e a Precisão Média para cada agrupamento.
Figura 2. Princípio básico do funcionamento da RTS Quality.
83
SAST
Para a ferramenta RTS funcionar, conforme a Figura 2, ela precisa analisar a
versão inicial do SUT, as partes exercitadas pelos testes nesta versão e as modificações
realizadas entre as versões inicial e final. Assim é possível incluir testes no conjunto de
regressão para a versão final. Por sua vez, a RTS Quality analisa a própria versão final,
executando nela seus testes e identificando quais são realmente necessários, isto é, cuja
execução exercita alguma modificação, calculando então a Inclusão e a Precisão.
A RTS Quality utiliza técnicas de mineração de repositórios de software para
analisar a descrição fornecida pelo desenvolvedor do sistema, durante as operações de
commit no repositório de software, que contém o identificador da requisição de
mudança atendida pela modificação. Com o identificador, é possível consultar a CMT
para encontrar o tipo da requisição de mudança. Nesta mineração são utilizados
identificadores de padrões em strings e uma consulta no CMT Database, esta consulta
pode ser substituída conforme a base de dados das diferentes CMTs.
3.2.
Arquitetura Interna
A Figura 3 apresenta as principais classes e métodos associadas a execução da RTS
Quality. Como módulo principal, o Executer é o responsável por gerenciar a execução
dos módulos auxiliares, solicitando e processando as informações. O módulo RTS
fornece a interface necessária a implementação de novas técnicas e permite que o
Executer comunique-se com a técnica única e exclusivamente através da classe pai
RegressionTestTechnique.
Figura 3. Arquitetura geral da RTS Quality.
84
SAST
O módulo HistoryMiner é responsável por fazer o download das versões do
SUT, a partir do SVN Repository, configurá-las na plataforma Eclipse e minerar as
características de cada modificação no sistema de gerência de mudanças (CMT
Database na Figura 3). O módulo TTracker é responsável pela instrumentação que
rastreia a execução de métodos de ação em métodos que iniciam a execução de casos de
uso do sistema coletando informações sobre os métodos cobertos. Todas as informações
são armazenadas na estrutura de dados TestCoverageMapping do módulo TTracker.
Antes de avaliar da RTS, o Executer solicita a configuração dos seguintes
parâmetros em arquivos de configuração: (i) as informações para que ele obtenha acesso
ao SVN Repository e a CMT Database do SUT analisado; (ii) o conjunto dos projetos
que compõem o SUT; e (iii) o número das versões inicial e final que serão avaliadas.
Figura 4. Sequência de execução da RTS Quality.
Obtenção das Tarefas e suas Modificações. Seguindo a numeração da Figura
4, o método Executer.obtainTasksModifiedMethods() é chamado nos passos de 1 a
3, para solicitar ao HistoryMiner obtenha os números das tarefas, seus tipos e revisões
registrados entre as revisões inicial e final. Nos passos 4 e 5, o HistoryMiner obtém os
métodos modificados em todas as revisões de cada requisição de mudança (tarefa), bem
como os métodos cujas modificações foram desfeitas. Modificações desfeitas ocorrem
quando o desenvolvedor realiza alterações em alguma revisão da tarefa, desfazendo-a
em uma revisão posterior, na tentativa de solucionar a tarefa por uma nova abordagem.
Para evitar equívocos, as modificações desfeitas são excluídas do conjunto final.
Análise da Revisão Inicial. Nos passos de 6 a 8, o Executer solicita ao History
Miner, através do método Executer.checkoutExecuteDelete(), o checkout da
revisão inicial dos projetos do sistema, e inclui neles a instrumentação do TTracker, que
rastreia a execução dos testes. Nos passos de 9 a 12, o pesquisador compila os projetos,
roda o sistema e executa os testes manuais desta versão. Em seguida, o Executer
recupera a estrutura de dados contendo os TestCoverageGroup, que reúnem os
diversos TestCoverage, gerados para cada teste executado, e adiciona à estrutura de
dados, através do método ProjectUtil.setAllUncoveredMethods(), os métodos
ainda não cobertos. Por fim, nos passos de 13 a 15, a RTS obtém as modificações
realizadas entre as versões e inclui os testes no conjunto de regressão.
Análise da Revisão Final. Nos passos 16 e 17, o Executer solicita ao History
Miner que faça o checkout da revisão final do sistema, nos passos 18 a 20, o
pesquisador executa os mesmos procedimentos da Fase 2. Em seguida, nos passos 21 e
22, o Executer recupera a estrutura de dados e seleciona os testes necessários, com base
85
SAST
nos TestCoverageGroups gerados durante a execução dos testes da revisão final. Isso
permite avaliar a seleção da RTS que utilizou apenas a revisão inicial.
Cálculo das Métricas e das Médias. Nos passos 23 e 24, o Executer, através do
método Executer.calculateMetricsAndAverages(), agrupa as modificações por
tarefas, compara os testes sugeridos pela RTS com os da RTS Quality e, para cada
tarefa, calcula as métricas de Inclusão e Precisão. Nos passos 25 e 26, agrupa as tarefas
com base em seus tipos (𝑻𝒚 ) e, nos passos 27 e 28, para cada tipo (𝒚) calcula a média
aritmética da Inclusão (𝑴𝒚𝒊 ) e da Precisão (𝑴𝒚𝒑 ), através do método
Executer.finalizeAverages(). Por fim, as porcentagens de inclusão e precisão
médias são exibidas no console do Eclipse para cada tipo de tarefa e armazenadas no
arquivo “result.txt”.
3.3.
Exemplo de Uso
Para demonstrar o funcionamento da RTS Quality a técnica de RTS Pythia foi
selecionada, para qual foi implementado um programa de exemplo com duas versões. A
Figura 5, apresenta suas as classes e métodos, e cada seta representa uma chamada
realizada pela classe durante a execução dos testes. Classes na cor preta representam
testes, na cor cinza classes cujos métodos foram cobertos pelos testes, e na cor branca
classes não cobertas. Os métodos modificados estão marcados com um “*”.
Figura 3. Callgraph dos métodos chamados a partir dos testes na versão: (a)
inicial e (b) final.
Na Fase 1 do estudo, a RTS Quality identifica os métodos modificados. Na Fase
2, de posse da revisão inicial, vista na Figura 5a, é necessário executar os testes para que
a instrumentação identifique os métodos cobertos. A ferramenta cruza os métodos
cobertos com os modificados, segue o caminho inverso das chamadas e identifica os
testes que deve incluir ou excluir do conjunto de regressão. Na Fase 3, a RTS Quality
obtém a revisão final, vista na Figura 5b, na qual são realizados os mesmos
procedimentos da Fase 2 na versão final, e, da mesma forma que a técnica RTS Pythia,
a RTS Quality identifica os testes que deve incluir no conjunto de regressão. Como a
RTS Quality utiliza a versão final, seu resultado serve de “gabarito” para conferir os
acertos da RTS. Assim, na Fase 4 é calculada a Inclusão e a Precisão alcançadas pela
RTS Pythia. A Tabela 1 permite observar os dados obtidos em cada fase.
Este exemplo auxilia na compreensão do funcionamento da RTS Quality,
entretanto, não possui nenhuma CMT, o que impossibilita a mineração dos tipos das
tarefas. Além do mais, possuir apenas duas revisões subsequentes, inviabilizando a
obtenção de uma média relevante para os diferentes tipos que as tarefas podem assumir.
86
SAST
Tabela 1. Dados analisados pela RTS Pythia nas Fase 2 e 3.
Fase 1 – Métodos Modificados
C1.m1*(); C2.m2*(); C3.m3*()
Fases 2 e 3 – Métodos Cobertos
Teste Executado
Na versão inicial
Na versão final
{T1.tM1(); C1.m1();
T1.tM1()
{T1.tM1()}
C2.m2()}
{T2.tM2(); C3.m3();
T2.tM2()
{T2.tM2(); C3.m3()}
C4.m4(); C2.m2()}
Fase 4 – Cálculo das Métricas
Métodos Modificado e Coberto
Na versão inicial
Na versão final
{C1.m1*(); C2.m2*(); C3.m3*()}
{C2.m2*(); C3.m3*()}
Resultados
Todos os Testes
Incluídos
Excluídos
4.
Inclusão e Exclusão
RTS Pythia
{T1.tM1(); T2.tM2()}
{T1.tM1(); T2.tM2()}
{∅}
RTS Quality
{T1.tM1(); T2.tM2()}
{T2.tM2()}
{T1.tM1()}
Avaliação Preliminar
Nesta seção as funcionalidades da RTS Quality são verificadas em plenitude, avaliando
se o comportamento da RTS Pythia é afetado pela característica dos tipos das tarefas
realizadas pelas modificações, característica esta, obtida a partir da mineração da CMT,
que gerencia as tarefas do SUT avaliado. Esta seção apresenta os objetivos da avaliação,
o SUT utilizado, como se dá a aplicação da ferramenta e os resultados alcançados.
4.1.
Objetivo
Os principais objetivos da avaliação foram: (i) analisar a adaptação da RTS Pythia para
a linguagem Java realizada por este trabalho, respondendo a seguinte questão de
pesquisa: (QP1) Os tipos das requisições de mudanças podem afetar a técnica de RTS
Pythia? e (ii) validar o funcionamento da RTS Quality, que deve constatar que a taxa de
inclusão da RTS Pythia é sempre de 100% independentemente do tipos da requisição, e
a de exclusão pode sofrer variações, já que a Pythia não é 100% precisa.
4.2.
Sistema Analisado
Para avaliar a RTS Pythia e a RTS Quality, foi selecionado o SIGAA (Sistema de
Gestão de Atividades Acadêmicas), desenvolvido pela Superintendência de Informática
da UFRN (SINFO). O SIGAA possui diversas versões executando em diferentes
instituições federais, estaduais e municipais do Brasil, sendo responsável por
informatizar procedimentos da área acadêmica através dos seus diversos módulos.
Devido à larga escala do sistema, foi selecionado para esta avaliação apenas o módulo
Biblioteca, desenvolvido para controlar a chegada, catalogação e empréstimo de livros.
O Módulo da Biblioteca possui os seguintes pré-requisitos que o viabilizam esta
avaliação: (i) sua evolução foi toda registrada em repositório de código com controle de
versões SVN, o que permite obter as modificações; (ii) foi implementado utilizando o
framework Java Server Faces (JSF) que adota o padrão arquitetural Model View
Control (MVC), que viabiliza o rastreamento da execução das actions (métodos de
ação) dos Managed Beans, classes Java que realizam o tratamento das diferentes
87
SAST
requisições HTTP submetidas ao sistema, e que são alvos de testes de aceitação; e (iii)
tem suas modificações gerenciadas por um sistema de gerência de mudanças, que define
quais modificações devem ser implementadas para evoluir da versão inicial até a final.
4.3.
Aplicação
Para responder a questão de pesquisa (QP1), esta avaliação foi organizada em 4 fases:
(i) Obtenção das Tarefas e Suas Modificações; (ii) Análise da Revisão Inicial; (iii)
Análise da Revisão Final; e (iv) Cálculo das Métricas e das Médias.
Obtenção das Tarefas e suas Modificações. A Figura 6 apresenta, para cada
tipo de tarefa da Biblioteca do SIGAA, a quantidade de vezes que ela ocorreu,
juntamente com suas porcentagens de frequência com relação as demais tarefas
encontradas. Os tipos das tarefas foram definidos pela equipe do SIGAA e esse estudo
não entrou no mérito da sua classificação.
Figura 4. Tipos de tarefas mais frequentes e suas porcentagens.
Análise da Revisão Inicial. Após a RTS Quality baixar a revisão inicial do
SUT, configurar os projetos na Plataforma Eclipse e incluir a instrumentação no SUT, o
pesquisador compila os projetos, roda o SUT e executa os testes. Em seguida, a RTS
Pythia é chamada para que selecione, com base nas informações capturadas pela
instrumentação, os testes que devem ser incluídos e excluídos do conjunto de regressão.
Tabela 2. Inclusão e Precisão médias por Tipo de Tarefa.
Inclusão Média
𝑴𝒚𝒊
𝚺𝒑𝒙 /|𝑻𝒚 |
Erro de Negócio/Validação
76/76
100%
75,98/76
99,97%
Erro de Execução
40/40
100%
40/40
100%
Aprimoramento
23/23
100%
22,94/23
99,77%
Verificação
18/18
100%
17,98/18
99,89%
Erro de Padron. de Visualização
12/12
100%
12/12
100%
Tipo da Tarefa
𝚺𝒊𝒙 /|𝑻𝒚 |
Precisão Média
𝑴𝒚𝒑
Análise da Revisão Final. Da mesma forma que na fase anterior, após a RTS
Quality e o pesquisador realiza os mesmos procedimentos na revisão final, ao invés de
executar a RTS Pythia, a própria RTS Quality identifica quais testes devem ser
incluídos e excluídos para a versão final.
Cálculo das Métricas e das Médias. A Tabela 2 apresenta a soma das inclusões
(Σ𝑖𝑥 ) e precisões (Σ𝑝𝑥 ) de cada tipo de tarefa, divididas pela quantidades de tarefas que
o tipo possui (|𝑇𝑦 |), obtendo assim as médias resultantes (𝑀𝑦𝑖 e 𝑀𝑦𝑝 ).
4.4.
Resultados
Após a execução de todas as fases da avaliação, foram obtidos os resultados tanto para a
avaliação da adaptação da RTS Pythia, quando para testar as funcionalidades da RTS
Quality e sua capacidade de obter as métricas das médias.
88
SAST
Avaliação da Técnica de RTS Pythia. Com base nos resultados obtidos, e em
resposta a (QP1), conclui-se que os tipos das tarefas não afetam diretamente o
desempenho da RTS Pythia. Esta não foi capaz de demonstrar grandes diferenças nas
médias calculadas para os 5 tipos de tarefas encontrados. Após a execução de 55 testes,
cobrindo 146 métodos de ação em Managed Beans, observa-se que os tipos analisados
obtiveram inclusão média de 100%. Entretanto, a Pythia incluiu testes demais em 3
tipos de tarefas, como um teste incluído representa um teste não excluído, diz-se que ela
não foi precisa, o que ocasiona um consumo de tempo desnecessário durante a execução
dos testes. A precisão afeta também a precisão média, mas com oscilações tão pequenas
que não se pode afirmar que a Pythia seja inapropriada para estes tipos, já que o tempo
total também sofrerá uma pequena variação.
Avaliação da Ferramenta RTS Quality. Ao analisar o Módulo da Biblioteca
do SIGAA, a RTS Quality encontrou um total de 1085 métodos modificados entre as
versões 3.11.24 e 3.12.36, distribuídos entre 169 tarefas classificadas em 5 tipos,
obtidos pela mineração na ferramenta de gerência de mudança (CMT Database). Como
esperado, tanto a Inclusão quanto a Inclusão Média foram sempre de 100%. Dentre as
76 tarefas do tipo “Erro de Negócio/Validação” a RTS Pythia errou em 1, pois excluiu
apenas 51 dos 52 testes. Dentre as 23 tarefas do tipo “Aprimoramento” errou em apenas
1 tarefa, excluindo para ela apenas 36 dos 38 testes. Dentre as 18 tarefas do tipo
“Verificação”, errou em 1, por não excluir 1 dos 52 testes. A Figura 7 apresenta o
cálculo das precisões médias dos 3 tipos. Desta forma a RTS Pythia garante que testes
que revelem faltas sejam sempre executados, mas não garante que todos os testes serão
realmente úteis a este propósito.
Figura 5. Precisão média alcançada pela RTS Pythia para cada tipo de tarefa.
5.
Trabalhos Relacionados
Os estudos realizados por [Rothermel e Harrold 1996] e por [Biswas et al. 2011] sobre
técnicas de RTS avaliam seu desempenho classificando-as em técnicas seguras ou não,
isto é, capazes de identificar todos os testes necessários para a nova versão ou não. Este
trabalho, no entanto, busca avaliar quais características das modificações podem afetar a
qualidade dos testes selecionados por uma RTS e quais são as origens de tais erros. O
estudo empírico realizado por [Frankl et al. 2003] se baseia em uma métrica parecida
com a Precisão, entretanto, calcula apenas a quantidade de testes que a RTS excluiu,
sem verificar se a exclusão está correta, não servindo ao propósito deste trabalho. A
avaliação empírica sobre técnicas de RTS, realizada em [Engström et al. 2008]
identifica diversos trabalhos, autores, tipos de técnicas, e as diversas métricas utilizadas
para avaliá-las, mas não implementa nenhuma ferramenta que as calcule. O experimento
realizado por [Vokolos e Frankl 1998], apesar de julgar como útil a presença de um
histórico que apresente os tipos de modificação realizadas para evoluir o sistema, não os
correlaciona com os valores das métricas obtidos pela RTS.
89
SAST
6.
Conclusões e Trabalhos Futuros
As principais contribuições da ferramenta RTS Quality são: (i) permitir avaliar técnicas
de RTS em sistemas implementados na linguagem Java; (ii) permitir rastrear a execução
tanto de testes manuais quanto testes automatizados JUnit em sistemas implementados
em Java; (iii) permitir calcular a inclusão e a precisão médias alcançadas por uma RTS
para os tipos das tarefas; (iv) possibilitar a escolha da melhor RTS, com base apenas no
características da nova modificação; (v) identificar os tipos de tarefas em que uma RTS
apresente piores resultados, ajudando na identificação das causas dos erros.
Observando as dificuldades do trabalho e com o intuito de aperfeiçoar a
ferramenta RTS Quality e os estudos que ela viabiliza, este artigo propõe os seguintes
trabalhos futuros: (i) Características Múltiplas – a RTS Quality analisa uma única
característica por vez, mas poderia ser adaptada para analisar múltiplas características
simultâneas, fornecendo avaliações mais precisa de uma RTS, permitindo avaliar qual
combinação de características provocam mais erros, apontando com maior precisão suas
causas; (ii) Sub-Ramo em Control Flow Graphs – as informações armazenadas na
estrutura de dados da RTS Quality utilizam uma granularidade cuja unidade de análise é
o método, entretanto, para uma maior precisão, a ferramenta poderia gerar um Grafo de
Fluxo de Controle (CFG – Control Flow Graph) sob demanda, adicionando nós a
medida que os fluxos fossem testados, identificando quais trechos foram
simultaneamente modificados e testados, sem precisar gerar um CFG do sistema inteiro;
e (iii) Generalização das Médias – as métricas de Inclusão e Precisão Médias propostas
por este trabalho possibilitam desvincular os “resultados obtidos” dos “SUTs
analisados”. Este trabalho não valida essa generalidade, e para tanto sugere a avaliação
e comparação de várias RTSs em diferentes SUTs.
Referências
Biswas, S. et al. (2011) “Regression test selection techniques: A survey”. Informatica:
An International Journal of Computing and Informatics, v. 35, n. 3, p. 289-321.
Engström, E., et al. (2008) “Empirical evaluations of regression test selection
techniques: a systematic review”. Proceedings of ESEM 2008.
Frankl, P. G. et al. (2003) “An empirical comparison of two safe regression test
selection techniques”. Proceedings of ISESE 2003, IEEE. p. 195-204.
Rothermel, G. et al. (2002) “Empirical studies of test‐suite reduction”. Software
Testing, Verification and Reliability, v. 12, n. 4, p. 219-249.
Rothermel, G. (1996) “Efficient, effective regression testing using safe test selection
techniques”. Tese de Doutorado. Clemson University.
Rothermel, G. e Harrold, M. J. (1996) “Analyzing regression test selection techniques”.
Software Engineering, IEEE Transactions on, v. 22, n. 8, p. 529-551.
Rothermel, G. et al. (1999) “Test Case Prioritization. Technical Report” GIT-99-28,
College of Computing, Georgia Institute of Technology: Dezembro.
Vokolos, F. I.; Frankl, P. G. (1998) “Empirical evaluation of the textual differencing
regression testing technique”. Proceedings of ICSM 2014, IEEE. p. 44-53.
Vokolos, F. I., Frankl, P. G. (1997) “Pythia: a regression test selection tool based on
textual differencing”. In: Reliability, quality and safety of software-intensive
systems. Springer US, p. 3-21.
Yoo, S., Harman, M. (2012) “Regression testing minimization, selection and
prioritization: a survey”. Software Testing, Verification and Reliability, v. 22, n. 2.
90
SAST
LoTuS-TCG: Uma ferramenta para geração e seleção de casos
de teste funcionais e estatı́sticos
Laryssa Lima Muniz1 , Ubiratan S. C. Netto1 , Paulo Henrique M. Maia2
1
Fundação Cearense de Meteorologia e Recursos Hı́dricos (Funceme)
Av. Rui Barbosa, 1246, CEP 60.115-221, Fortaleza – CE
2
Mestrado Acadêmico em Ciência da Computação
Universidade Estadual do Ceará
Campus do Itaperi, Av. Dr. Silas Munguba, 1700, CEP 60740-903, Fortaleza – CE
{laryssa.muniz,ubiratan.cavalcante}@funceme.br, [email protected]
Abstract. This paper presents LoTuS-TCG, a tool for the generation and selection of test cases for functional and statistical tests that accepts as input both
probabilistic and non-probabilistic models. The test case selection techniques
provided are test purposes, random path and most probable path. In addition,
this paper also introduces a selection technique called minimum probability of
path in which the tool selects test cases that have probability greater than or
equal to a value provided by the user.
Resumo. Este artigo apresenta LoTuS-TCG, uma ferramenta para geração e
seleção de casos de testes funcionais e estatı́sticos que aceita como entrada modelos probabilı́sticos e não probabilı́sticos. As técnicas de seleção fornecidas
são propósitos de teste, caminho randômico e caminho mais provável. Além
disso, este trabalho também apresenta a técnica de seleção chamada de probabilidade mı́nima de caminho, na qual a ferramenta seleciona os casos de teste
que possuam probabilidade de ocorrência maior ou igual a um valor informado
pelo usuário.
1. Introdução
O Teste Baseados em Modelos (Model-Based Testing - MBT) consiste em uma técnica
para geração automática de um conjunto de casos de testes utilizando modelos extraı́dos a
partir de artefatos de software [Binder 1999]. Essa abordagem visa melhorar a qualidade
do software, assim como reduzir os custos inerentes de um processo de teste. Como esta
abordagem é bastante dependente da qualidade do modelo que está sendo utilizado, é
necessário um elevado nı́vel de precisão na construção do modelo [Beizer 1995].
A automatização de uma abordagem MBT depende de três elementos principais [Dalal et al. 1999]: (i) o modelo usado para descrição do comportamento do sistema; (ii) o algoritmo de geração de teste (critérios de teste); e (iii) ferramentas que
forneçam a infraestrutura necessária para geração dos casos de teste. Em relação ao
modelo, os mais utilizados são diagramas da UML, como os diagramas de sequência,
de casos de uso e de estados, formalismos baseados em máquinas de estados finitos, statecharts, e sistemas de transição rotuladas - (Labelled Transition Systems - LTS). Para
manipulá-los, surgiram diversas ferramentas que aplicam diferentes critérios de teste,
91
SAST
como mostram vários surveys na área [Dias Neto et al. 2007, Shirole and Kumar 2013,
Shafique and Labiche 2013, Aichernig et al. 2008]. Como os casos de teste são gerados
a partir de modelos, e não do código, as abordagens de MBT são adequadas para testes
funcionais.
Adicionalmente, alguns trabalhos têm proposto o uso de modelos probabilı́sticos, como Cadeias de Markov, em conjunto com técnicas de MBT para geração
estatı́stica de casos de teste baseados na probabilidade de execução do sistema
[Walton and Poore 2000][Feliachi and Le Guen 2010], o que permite também estimar a
confiabilidade de um determinado sistema [Trammell 1995][Zhou et al. 2012]. Apoiado
em técnicas tradicionais de teste de software, como o teste funcional e o teste estrutural, o
teste estatı́stico compreende a aplicação da ciência estatı́stica para a solução de problemas
de teste de software [Sayre and Poore 1999]. O teste estatı́stico é visto como um excelente
complemento para as técnicas de teste existentes podendo ser utilizado não como uma diferente técnica de teste, mas como uma técnica que visa somar confiabilidade às demais
técnicas [Bertolini 2006]. Nesse contexto, a utilização do teste estatı́stico deve-se apoiar
em ferramentas que suportem todo esse processo de teste. Exemplos dessas ferramentas
são STAGE-TEST [Copstein and Oliveira 2004] e MaTeLo [Feliachi and Le Guen 2010].
Cada ferramenta de MBT disponibiliza, geralmente, apenas um tipo de formalismo para modelagem do comportamento do sistema, ou seja, o usuário pode usar um
modelo tradicional ou probabilı́stico, mas não tem a possibilidade de usar ambos. Isso
implica que a ferramenta fornece isoladamente geração de casos de teste funcionais ou estatı́sticos. Além disso, muitas ferramentas apresentadas na literatura não estão disponı́veis
para download ou são pagas, o que também impossibilita ou limita seu uso.
O objetivo deste artigo é apresentar LoTuS-TCG, uma ferramenta de MBT para
geração e seleção de casos de teste tanto funcionais quanto estatı́sticos. Isso é possı́vel
pois ela foi desenvolvida como um plugin para LoTuS, uma ferramenta para modelagem
gráfica de comportamento de software que permite ao usuário modelar tanto o comportamento não probabilı́stico, utilizando LTS, quanto probabilı́stico, utilizando LTSs probabilı́sticos, que são semelhantes a Cadeias de Markov de Tempo Discreto. Para seleção
de casos de teste funcionais, foi implementada a estratégia de propósitos de teste. Essa
técnica também está presente para seleção de casos de teste estatı́sticos, juntamente com
as estratégias de caminho randômico e caminho mais provável. Este trabalho também
apresenta a técnica de seleção chamada de probabilidade mı́nima de caminho, na qual a
ferramenta seleciona os casos de teste que possuam probabilidade de ocorrência maior ou
igual a um valor informado pelo usuário.
O artigo está estruturado da seguinte maneira. Na seção 2 apresentamos os principais conceitos que foram abordados neste trabalho, enquanto os trabalhos relacionados
são discutidos na seção 3. A seção 4 descreve a ferramenta LoTuS-TCG e detalha suas
técnicas de geração e seleção de casos de teste. A seção 5 apresenta um exemplo de uso
da ferramenta e, por fim, a seção 6 traz as considerações finais e trabalhos futuros.
2. Fundamentação Teórica
2.1. Teste Baseado em Modelo
MBT é uma abordagem que se baseia nas especificações do software para a criação do
modelo formal, e a partir deste, possibilita a extração de casos de teste. MBT é composto
92
SAST
por diversas atividades, conforme mostra a Figura 1[Cartaxo et al. 2008].
Figura 1. Processo de teste baseado em modelos
• Construção do modelo: a partir da especificação dos requisitos, diferentes modelos que representam o comportamento do sistema podem ser construı́dos, como
por exemplo diagramas da UML e LTSs.
• Gerar entradas: as entradas do teste são geradas partindo do modelo. Estas entradas são passos que servirão para exercitar a aplicação que está sendo testada.
• Gerar saı́das esperadas: as saı́das esperadas são geradas a partir do modelo e indicam o comportamento do sistema
• Geração de Casos de Teste: para se obter os casos de testes é necessário mapear
o modelo formal e utilizar técnicas de seleção para então reduzir a quantidade dos
casos de teste derivados do modelo.
• Execução dos Testes: a aplicação é executada com as entradas geradas, gerando
saı́das.
• Comparar os resultados: as saı́das da aplicação são comparadas com as saı́das
geradas a a partir do modelo.
O teste funcional, conhecido também como caixa-preta (black-box), enxerga o sistema como uma caixa fechada onde não se tem conhecimento sobre sua implementação ou
seu comportamento interno. Com a abordagem funcional temos a vantagem de gerar casos de teste mesmo antes de a implementação estar pronta, já que a base é a especificação.
Por outro lado, temos que esta abordagem é dependente do modelo, ou seja, só serão gerados casos de testes do comportamento do software que estiver na especificação. Se
todos os comportamentos possı́veis do software não estiverem especificados, então os
casos de teste gerados para aplicação não cobrirão todos os possı́veis comportamentos [Cartaxo et al. 2008].
Neste trabalho utilizamos como modelo de comportamento do sistema um
LTS [Keller 1976], que pode ser entendido como uma 4-tupla L = (S, A, T, q0 ), onde
S é o conjunto finito não vazio de estados, A é o conjunto finito não vazio de rótulos que
denota o alfabeto de L, T ⊆ em (S x A x S) define o conjunto de transições rotuladas entre
os estados, e q0 é o estado inicial.
2.2. Testes estatı́sticos
Testes estatı́sticos baseiam-se na elaboração de um modelo de comportamento do sistema
e, a partir dele, a especificação de um modelo de uso do mesmo que representa, por
exemplo, a probabilidade de uso das funções do sistema. Em [Walton et al. 1995], os
autores afirmam que os modelos de uso podem ser representados por Cadeias de Markov
e propõem um metodologia de oito etapas para a criação desses modelos, dentre as quais
93
SAST
destacamos: revisar a especificação do software; identificar o uso do software e definir
parâmetros de ambiente; desenvolver a estrutura do modelo de uso e verificar se ela está de
acordo com a especificação; desenvolver e verificar a distribuição da probabilidade para
o modelo. Vale ressaltar que o modelo de uso define apenas aspectos funcionais de um
software, não considerando aspectos não funcionais ou estruturais do software modelado.
Segundo[Bertolini 2006], dentre os benefı́cios no teste estatı́stico de software com
modelos de uso estão: (i) geração de testes automática: a utilização de modelos de uso
torna-se ideal para a geração automática de testes, por exemplo, utilizando cadeias de
Markov para a execução de testes estatı́sticos de software; (ii) testes eficientes: os testes
tornam-se bem estruturados e contribuem para a obtenção de resultados mais eficientes;
e (iii) gerenciamento quantitativo dos testes: os resultados quantitativos dos testes acabam ajudando no gerenciamento e tomadas de decisão. Como limitações, o autor cita a
possibilidade de explosão de estados, caso o modelo seja muito detalhado, ou perda de
informação, caso o modelo seja mais abstrato.
Neste trabalho utilizamos o LTS probabilı́stico (probabilistic LTS - PLTS) como
formalismo para modelagem do comportamento probabilı́stico do sistema. Um PLTS
estende um LTS acrescentando, para cada transição, uma probabilidade de ocorrência
entre 0 e 1 tal que a soma das probabilidades das transições de saı́da de um mesmo estado
seja sempre 1. Ao retirar os rótulos das transições do PLTS, o modelo resultante é uma
Cadeia de Markov de Tempo Discreto. Não está no escopo do trabalho validar a origem
das probabilidades utilizadas no modelo. Esta tarefa é deixada para o criador do modelo.
3. Trabalhos relacionados
Existem vários trabalhos na área [Dias Neto et al. 2007, Shirole and Kumar 2013,
Shafique and Labiche 2013, Aichernig et al. 2008] que apresentam revisões sistemáticas
ou surveys descrevendo diversas abordagens, técnicas e ferramentas de MBT e
comparando-as utilizando critérios variados. Nesta seção iremos concentrar a discussão
em trabalhos mais próximos ao nosso que também propõem ferramentas para geração
e seleção de casos de teste funcionais ou estatı́sticos e que utilizem, de alguma forma,
modelos em LTS, PLTS ou Cadeias de Markov.
TGV (Test Generation with Verification technology) [Jard and Jeron 2005] é uma
ferramenta de suporte a testes de conformidade que provê geração e seleção de casos
de teste para sistemas reativos e não-determinı́sticos de forma automática. A geração
de casos de teste é baseada em técnicas de verificação de modelos, tais como produto
sı́ncrono, verificação em tempo de execução e algoritmos de busca.
Devido à dificuldade em modelar LTSs, grande parte dos trabalhos relacionados
à geração de casos de teste utiliza como entrada diagramas UML que são transformados internamente para modelos LTSs. Por exemplo, LTS-BT [Cartaxo et al. 2008] é
uma ferramenta para geração e seleção de casos de teste funcionais no contexto das
aplicações móveis que recebe como entrada um conjunto de Diagramas de Sequências
da UML que posteriormente são transformados em LTSs anotados. Os casos de teste
são selecionados através de propósitos de teste e por similaridade de caminhos. Já em
[de Lucena Andrade 2007] o autor estende LTS-BT para dar suporte ao teste de interação
entre features em aplicações celulares, onde as features e suas interações são especificados
através de um template de casos de uso da UML.
94
SAST
A utilização de Cadeias de Markov como modelo para a geração de casos de teste
também é bastante difundida na literatura, podendo ser encontrados diversos trabalhos
sobre o assunto [Walton et al. 1995, Trammell 1995, Walton and Poore 2000]. MaTeLo
(Markov Test Logic) [Feliachi and Le Guen 2010] é uma ferramenta comercial que apresenta solução de MBT utilizando Cadeia de Markov como notação de modelagem. Ela
disponibiliza duas técnicas de geração de casos de teste (cobertura de transição e cobertura de estado) e duas técnicas de seleção de casos de teste: caminho aleatório e rota mais
provável. STAGE-TEST [Copstein and Oliveira 2004] é uma ferramenta para geração de
casos de teste e scripts de teste que recebe como entrada diferentes tipos de modelos, tanto
probabilı́sticos, como Cadeia de Markov e Redes de Autômatos Estocásticos, quanto não
probabilı́sticos, como máquina de estados finitos. As técnicas de seleção de casos de teste
são: Wp Method e Graph Tacker, para máquina de estados finitos, e caminho randômico
para os outros formalismos. Apesar de ser semelhante à ferramenta proposta neste trabalho, tem a diferença que os modelos são criados em uma outra ferramenta, tendo assim o
usuário que usar uma ferramenta para modelagem e outra para geração dos casos de teste.
Além disso, a ferramenta apresenta apenas um critério de seleção para testes estatı́sticos,
enquanto a proposta neste artigo apresenta quatro. Por fim, a ferramenta analisada não foi
encontrada para download.
4. LoTuS-TCG
LoTuS[Lima et al. 2014] é uma ferramenta para modelagem gráfica do comportamento
de sistemas usando LTS. Ela fornece uma maneira interativa e simples para a criação,
composição e manipulação de LTSs. Além disso, possibilita ao usuário associar às
transições do LTS condições de guarda e probabilidades de execução, o que permite a modelagem de um LTS probabilı́stico. Apesar de ser voltada para a modelagem de sistemas,
LoTuS tem uma importante caracterı́stica que é o fato de ser extensı́vel, disponibilizando
uma API Java com a qual um desenvolvedor pode criar plugins que adicionem à ferramenta novas funcionalidades. Alguns plugins já foram desenvolvidos e estão disponı́veis
no website da ferramenta1 , como plugin para geração de traces de execução, plugin para
anotação de probabilidades no modelo a partir de um conjunto de traces, e plugin para
checagem de modelos probabilı́sticos. A ideia, com isso, é deixar a ferramente leve, permitindo que o usuário escolha os plugins com os quais deseja trabalhar e possibilitando-o
de criar seus próprios plugins para atender às suas necessidades.
LoTuS-TCG (Test Case Generation) é um plugin para LoTuS que permite gerar
e selecionar casos de testes para os modelos probabilı́sticos e não-probabilı́sticos criados
pelo usuário. O plugin foi desenvolvido como um arquivo do tipo jar que, para ser carregado pelo LoTuS, basta apenas ser colocado na pasta extensions da ferramenta. Ao ser
iniciado, LoTuS carrega automaticamente todos os plugins contidos nessa pasta. Assim
como LoTuS, a ferramenta é gratuita para download2 e uso.
O plugin aparece visualmente na ferramenta como o item “TCG” do menu principal. Nele são encontrados dois sub-menus: Functional e Statistical, que contêm os
critérios para geração e seleção de casos de teste disponı́veis. Caso o modelo do sistema
seja um LTS, o usuário deve escolher dentre as opções de geração e seleção do sub-menu
1
2
http://jeri.larces.uece.br/lotus
http://jeri.larces.uece.br/lotus/plugins/tcg
95
SAST
Functional as que pretende usar; caso seja um PLTS, ele escolhe dentre as opções do outro
sub-menu. Essas opções são descritas na seções a seguir.
4.1. Geração de casos de teste
Para gerar os casos de testes funcionais, será adotado o critério de cobertura de caminhos.
Assim, podemos definir um caso de teste como um caminho no LTS. Para obter todos
os caminhos, utilizamos o método de busca em profundidade no LTS iniciando com o
estado inicial até um estado que não tenha transições de saı́da. Se existir algum loop não
condicional no modelo LTS, devemos passar por ele apenas se formar um novo caminho,
isto é, se o caminho resultante tiver pelo menos uma transição diferente. Se existir algum
loop condicional no modelo LTS, devemos passar por ele apenas uma vez.
Para os casos de teste estatı́sticos, o algoritmo de geração é o mesmo. Porém, os
casos de teste são exibidos juntamente com sua probabilidade de ocorrência. A probabilidade de ocorrência de um caminho é obtida multiplicando-se a probabilidade de cada
transição que compõe o caminho.
4.2. Seleção de casos de teste
Como nem sempre é possı́vel executar todos os testes que são obtidos numa geração
exaustiva de casos de teste, faz-se necessário adotar estratégias para selecionar os casos
de teste.
Para ambos os tipos de testes abordados neste trabalho, um dos critérios de seleção
é o baseado em propósito de teste, que tem como objetivo selecionar do modelo um
conjunto de casos de teste que atenda a um determinado propósito. O propósito de teste
serve para limitar o modelo e então é aplicada à geração. A partir destas duas entradas
podemos obter os casos de teste.
O propósito de teste segue a mesma abordagem usada em [Cartaxo et al. 2008] e
deverá ser composto por uma sequência de rótulos do modelo, podendo ter * (asterisco)
entre os rótulos. Neste caso o * representa qualquer rótulo de transição ou simplesmente
nenhum rótulo. A sequência é finalizada com “ACEITAR”, que significa que se quer
todos os casos de teste que satisfaçam o propósito, ou “REJEITAR”, que significa que se
deseja todos os casos de teste que não satisfaçam o propósito, isto é, o que se quer é o
complemento dos casos de teste que satisfazem o propósito.
Para escrever o propósito, o usuário deve obedecer a uma das seguintes regras de
formação: (i) *&ACEITAR : retorna todos os caminhos possı́veis; (ii) *a*&ACEITAR:
retorna todos os caminhos que possuam o rótulo a; (iii) *a&ACEITAR: retorna todos os
caminhos que terminem com o rótulo a; (iv) *a*b&ACEITAR: retorna todos os caminhos
que possuam o rótulo a e terminem no rótulo b; (v) *a,b&ACEITAR: retorna todos os
caminhos que terminem com um rótulo a seguido de um rótulo b; (vi) a*&ACEITAR:
retorna todos os caminhos que iniciem com o rótulo a. As mesmas regras de formação
valem para sequências terminadas com “REJEITAR”, porém os casos de teste retornados
serão justamente aqueles que não satisfazem a mesma sequencia terminada com “ACEITAR”. Por exemplo, a sequência *&REJEITAR não retorna nenhum caminho, enquanto
a sequência *a*&REJEITAR retorna todos os caminhos que não possuem o rótulo a.
Já para selecionar os casos de teste estatı́sticos, três outras estratégias também
foram implementadas: a primeira é o caminho mais provável (most probable path), que
96
SAST
consiste em mostrar apenas o caso de teste com maior probabilidade de ocorrência. A
segunda é a caminho randômico (random path), que consiste em selecionar randomicamente um dos caminhos do modelo. Por fim, a estratégia de probabilidade mı́nima de
caminho (minimum probability of path) permite ao usuário inserir qual a menor probabilidade de ocorrência que ele espera que um caso de teste tenha e a ferramenta retorna
apenas os caminhos cuja probabilidade são maiores ou iguais a esse critério de seleção.
Essa técnica de seleção é uma das contribuições deste trabalho, uma vez que não foi encontrada em outras ferramentas.
5. Exemplo de uso
Nesta seção mostraremos um exemplo de uso da ferramenta LoTuS-TCG. Considere um
sistema de envio de mensagens na web, ilustrado na Figura 2, que foi modelado em LoTuS. O sistema exibe inicialmente a tela de login. O usuário deve, então, se logar para
poder enviar mensagens. Caso o login esteja inválido, o usuário pode tentar novamente
ou cancelar. O sistema pode falhar ao enviar uma mensagem e, neste caso, tenta automaticamente enviar novamente a mensagem até que tenha êxito. O usuário finaliza seu uso ao
realizar logout do sistema. As respectivas probabilidades de ocorrência de cada transição
também estão representadas no modelo.
Devido à limitação de espaço, iremos restringir o exemplo apenas aos testes estatı́sticos. Todavia, para os testes funcionais, as opções de gerar casos de teste e selecionar
casos de teste através de propósitos de teste também estão disponı́veis e funcionam exatamente como mostrados no exemplo a seguir, com a única diferença que não será mostrada
a probabilidade de ocorrência do caso de teste.
Figura 2. Tela do LoTus-TCG
Ao clicar no menu “TCG”, selecionamos a opção “Statistical”, uma vez que o modelo é probabilı́stico. Nesse menu, o usuário pode escolher gerar todos os casos de teste
ou fazer uma seleção utilizando uma das técnicas descritas na seção anterior, conforme
mostrado na Figura 2. Quando clica em “Test case generation”, a lista de casos de teste
gerados pela ferramenta é exibida em uma tabela abaixo do painel de desenho do modelo
(chamada de Tabela de Casos de Teste), conforme mostra a Figura 3.
97
SAST
Figura 3. Exibição dos casos de testes em LoTuS-TCG
Para facilitar a visualização no modelo do caminho que representa o caso de teste,
LoTuS-TCG destaca esse caminho no próprio modelo quando o caso de teste é selecionado na tabela. A Figura 3 mostra a seleção do caso de teste telaLogin, entraLogin,
loginValido, enviaMsg, sucEnvio, logout, que representa a situação onde o usuário consegue se logar na primeira tentativa, mas não envia mensagem alguma, realizando logo em
seguida um logout.
Para testar as técnicas de seleção de casos de teste, o usuário seleciona a opção
desejada no menu “Teste case selection”. A opção “Test purpose” permite selecionar os
casos de teste utilizando um propósito de teste. Por exemplo, para o propósito *loginInvalido*sucEnvio*&ACEITAR, o conjunto de casos de teste retornados representa as
situações onde houve uma tentativa errada de login, mas o usuário conseguiu se logar e
enviar pelo menos uma mensagem. Por outro lado, o propósito *sucEnvio*&REJEITAR
retorna todos os casos de teste nos quais o usuário não conseguiu enviar com sucesso nenhuma mensagem. Pelo modelo, essas situações acontecem quando o usuário cancela o
login e realiza um logout logo após se logar no sistema.
Na opção “Minimum Probability of Path”, o usuário digita um valor mı́nimo de
probabilidade de ocorrência de caso de teste. Por exemplo, caso o usuário digite 0.02, a
ferramenta retornará todos os casos de teste cuja probabilidade de ocorrência seja maior
ou igual a esse valor. Esses casos são mostrados na Figura 4.
Figura 4. Casos de testes retornados pelo critério Minimum Probability of Path
Por fim, as técnicas “Most Probable Path” e “Random path” exibem seus resultados de forma igual, ou seja, ambas retornam apenas uma caso de teste, que é exibido na
98
SAST
Tabela de Casos de Teste. Para o exemplo do sistema de envio de mensagens, a primeira
opção gerou o caso de teste telaLogin, entraLogin, loginValido, logout, cuja probabilidade
de ocorrência é 0.09212.
6. Conclusão
Este artigo apresentou LoTuS-TCG, uma ferramenta para geração e seleção de casos de
teste funcionais e estatı́sticos. Para tanto, ela foi construı́da como um plugin para a ferramenta de modelagem LoTuS, que permite ao usuário modelar o comportamento do sistema como um LTS ou como um PLTS. A principal contribuição é permitir que ambos os
tipos de casos de teste possam ser gerados em uma só ferramenta, sendo esse também seu
grande diferencial em relação às outras ferramentas. O artigo também apresentou uma
nova técnica de seleção de casos de teste chamada mı́nima probabilidade de caminho.
Um exemplo de uso foi mostrado onde foram exercitadas algumas das funcionalidades
disponı́veis na ferramenta.
Atualmente, alguns estudos de casos estão em desenvolvimento. Por exemplo,
LoTuS-TCG está sendo testada para auxiliar a descoberta e seleção de casos de teste em
um sistema de monitoramento do tempo na Funceme, local de trabalho de alguns dos
autores. Além disso, a ferramenta também está sendo utilizada por alunos do curso de
Ciência da Computação e do Mestrado Acadêmico em Ciência da Computação, ambos
da Universidade Estadual do Ceará, na disciplina de Teste e Validação de Software. Os
resultados dos estudos de caso serão disponibilizados no website da ferramenta. Outra
funcionalidade que está sendo implementada é uma forma de poder utilizar as técnicas
de seleção caminho mais provável, randômico e probabilidade mı́nima em conjunto com
propóstos de teste.
Como trabalhos futuros, pretende-se aplicar a ferramenta a diversos contextos para
avaliar melhor sua usabilidade e aplicabilidade. Também planejamos implementar outros
tipos de seleção de casos de teste, como baseados em similaridade de caminhos, e técnicas
de priorização de casos de teste. Por fim, pretende-se criar um módulo de geração de
scripts ou códigos de teste a partir das suites de testes geradas pela ferramenta.
Referências
Aichernig, B., Krenn, W., Eriksson, H., and Vinter, J. (2008). D 1.2 - state of the art survey
- part a: Model-based test case generation. Technical report, AIT Austrian Institute of
Technology GmbH.
Beizer, B. (1995). Black-box Testing: Techniques for Functional Testing of Software and
Systems. John Wiley & Sons, Inc., New York, NY, USA.
Bertolini, C. (2006). Análise de casos de teste estatisticamente relevantes através da
descrição formal de programas. Mestrado, Pós-Graduação em Ciência da Computação,
PUC-RS.
Binder, R. V. (1999). Testing Object-oriented Systems: Models, Patterns, and Tools.
Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.
Cartaxo, E. G., Andrade, W. L., Neto, F. G. O., and Machado, P. D. L. (2008). Lts-bt: A
tool to generate and select functional test cases for embedded systems. In Proceedings
99
SAST
of the 2008 ACM Symposium on Applied Computing, SAC ’08, pages 1540–1544.
ACM.
Copstein, B. and Oliveira, F. M. (2004). Effective statistical test script generation. In
Proceedings of the 15th IEEE International Symposium on Software Reliability Engineering.
Dalal, S. R., Jain, A., Karunanithi, N., Leaton, J. M., Lott, C. M., Patton, G. C., and
Horowitz, B. M. (1999). Model-based testing in practice. In Proceedings of the 21st
International Conference on Software Engineering, ICSE ’99, pages 285–294. ACM.
de Lucena Andrade, W. (2007). Geração de casos de teste de interação para aplicações de
celulares. Mestrado, Pós-Graduação em Ciência da Computação, UFCG.
Dias Neto, A. C., Subramanyan, R., Vieira, M., and Travassos, G. H. (2007). A survey on
model-based testing approaches: A systematic review. In Proceedings of the 1st ACM
International Workshop on Empirical Assessment of Software Engineering Languages
and Technologies, WEASELTech ’07, pages 31–36. ACM.
Feliachi, A. and Le Guen, H. (2010). Generating transition probabilities for automatic
model-based test generation. In Software Testing, Verification and Validation (ICST),
2010 Third International Conference on, pages 99–102.
Jard, C. and Jeron, T. (2005). Tgv: Theory, principles and algorithms: A tool for the
automatic synthesis of conformance test cases for non-deterministic reactive systems.
Int. J. Softw. Tools Technol. Transf., 7(4):297–315.
Keller, R. M. (1976). Formal verification of parallel programs. Commun. ACM, 19:371–
384.
Lima, E. C. F., Barbosa, W. P., and Maia, P. H. M. (2014). Lotus: An extensible tool
for graphical modelling of software behavior using lts. Technical report, Universidade
Estadual do Ceará.
Sayre, K. and Poore, J. H. (1999). Partition testing with usage models. In Proceedings of
the Science and Engineering for Software Development: A Recognition of Harlan D.
Mills’ Legacy, SESD ’99, pages 24–. IEEE Computer Society.
Shafique, M. and Labiche, Y. (2013). A systematic review of state-based test tools. International Journal on Software Tools for Technology Transfer, pages 1–18.
Shirole, M. and Kumar, R. (2013). Uml behavioral model based test case generation: A
survey. SIGSOFT Softw. Eng. Notes, 38(4):1–13.
Trammell, C. (1995). Quantifying the reliability of software: Statistical testing based
on a usage model. In Proceedings of the 2Nd IEEE Software Engineering Standards
Symposium, ISESS ’95, pages 208–, Washington, DC, USA. IEEE Computer Society.
Walton, G. H. and Poore, J. H. (2000). Generating transition probabilities to support
model-based software testing. Softw. Pract. Exper., 30(10):1095–1106.
Walton, G. H., Poore, J. H., and Trammell, C. J. (1995). Statistical testing of software
based on a usage model. Softw. Pract. Exper., 25(1):97–108.
Zhou, K., Wang, X., Hou, G., and Jie Wang, S. A. (2012). Software reliability test based
on markov usage model. Journal of Software, 7(9):2061–2068.
100
SAST
Integrando Teste Baseado em Modelos no Desenvolvimento de
uma Aplicação Industrial: Benefı́cios e Desafios
Dalton Jorge, Patrı́cia D. L. Machado, Francisco G. Oliveira Neto,
Ana Emı́lia V. B. Coutinho, João F. S. Ouriques
1
Laboratório de Práticas de Software (SPLab), UFCG, Brasil
{netojin,ana,joao}@copin.ufcg.edu.br
Resumo. Teste Baseado em Modelos (MBT) tem sido aplicado com sucesso em
estudos de caso industriais. No entanto, os estudos apresentados na literatura
ainda são preliminares e, diante disto, há inúmeros desafios a serem vencidos na
integração de MBT com processos de desenvolvimento, deixando clara a necessidade de mais investigação exploratória. O objetivo deste artigo é descrever
um caso de sucesso no uso de MBT para o teste de sistema de uma aplicação
industrial. O artigo relata as soluções adotadas, as dificuldades enfrentadas
e os benefı́cios obtidos. De forma geral, os casos de teste obtidos cobriram
de forma satisfatória os objetivos de teste e se mostraram efetivos na detecção
de defeitos. Em contrapartida, a gerência de artefatos e a distância semântica
entre os casos de teste e o sistema sob teste apresentou alguns desafios.
1. Introdução
Teste Baseado em Modelos (do inglês Model-Based Testing - MBT) é uma abordagem de
teste que visa minimizar os custos e, ao mesmo tempo, aumentar a efetividade de processos de teste através da seleção sistemática de casos de teste [El-Far and Whittaker 2001,
Utting and Legeard 2007]. Usualmente, casos de teste são derivados a partir de modelos
abstratos do sistema, incluindo outros artefatos e dependências necessários a sua execução
automática, tais como drivers e oráculos de teste. Além disso, MBT pode ser aplicado em
diferentes nı́veis de teste.
Há relatos na literatura de benefı́cios práticos obtidos com a implantação de processos de MBT e que confirmam as expectativas existentes [Peleska et al. 2011]. No
entanto, ainda são inúmeros os desafios a serem vencidos a fim de tornar viável e efetiva a
integração de MBT em processos de desenvolvimento. Particularmente, os custos inerentes à criação (ou reuso de modelos existentes) e a manutenção de um modelo de testes podem inviabilizar a sua aplicação [Utting and Legeard 2007, Marques et al. 2014]. Adicionalmente, apesar de já existir um número considerável de abordagens propostas na literatura, ainda há poucos trabalhos focando na avaliação empı́rica e a maioria das abordagens
MBT desenvolvidas pela acadêmia não são aplicadas na indústria [Dias Neto et al. 2007].
Este artigo apresenta um relato de experiência no uso de MBT para o teste de
sistema de uma aplicação industrial. Casos de teste foram gerados automaticamente a
partir de documentos de requisitos escritos no formato de casos de uso em linguagem
natural e foram executados de forma manual em três versões da aplicação, onde as versões
subsequentes foram obtidas a partir de modificações corretivas e adaptativas, requisitando
alterações tanto em código quanto em casos de uso. O processo de MBT que foi seguido é
101
SAST
brevemente descrito na Seção 2. A aplicação é apresentada na Seção 3, seguida pela Seção
4 onde os resultados obtidos são apresentados. Na Seção 5 são discutidos outros relatos
já apresentados na literatura e, por fim, na Seção 6, são discutidas as principais lições
aprendidas. A aplicação foi desenvolvida como parte de uma cooperação técnica entre o
SPLab/UFCG e a empresa Ingenico do Brasil Ltda.1 , incentivada pela Lei de Informática
8.248.
2. Processo de MBT
O processo de MBT seguido e sua integração com o processo de desenvolvimento da
aplicação é ilustrado na Figura 1. O processo de desenvolvimento é centrado em requisitos
que foram definidos através de documentos no formato de casos de uso. O processo de
MBT inicia com a conversão automática de casos de uso em modelos LTS no formato
TGF (Trivial Graph Format). Tais modelos foram produzidos a partir da captura e junção
tanto dos fluxos de cada caso de uso (fluxo básico, alternativo e de exceção) quanto dos
modelos de casos de uso entre si (por meio de pontos de extensão e de inclusão). A
automatização desta se tornou possı́vel dado que os documentos foram produzidos usando
um formato pré-definido para especificação de fluxos.
Processo de Desenvolvimento
Use
Cases
Sistema
sob Teste
Modelos LTS
(TGF)
Conversor
para LTS
Mudanças
em
Requisitos
yEd
Modelos LTS
(TGF)
válidos
LTS-BT
CCTs
(XML)
TestLink
Plano de
Testes
Resultados
Execução
Manual
Relatórios
de Execução
Modificações
em Use Cases
Gerenciamento de Mudanças
Figura 1. Processo de MBT.
Uma vez produzidos, os modelos LTS foram visualizados usando a ferramenta
yEd2 a fim de valida-los e detectar possı́veis erros em desvios e pontos de junção. Tais
erros foram reportados à gerência de mudanças, devido à necessidade de corrigi-los diretamente nos documentos de casos de uso.
Os modelos LTS validados foram apresentados como entrada para a ferramenta
LTS-BT [Cartaxo et al. 2008], responsável por gerar automaticamente os conjuntos de
casos de teste (CCTs) de acordo com critérios de cobertura estabelecidos. Os CCTs são
exportados em um arquivo no formato XML, compatı́vel com a entrada aceita pela ferramenta Testlink3 . Em seguida, estes CCTs são importados pela ferramenta TestLink, responsável pela definição e gerenciamento dos planos de teste. Durante a execução manual
dos casos de teste, os testadores registraram no TestLink todas as informações relativas
aos resultados obtidos com a execução de cada caso de teste, incluindo comentários sobre
discrepâncias encontradas. Por fim, os resultados obtidos com a execução dos planos de
teste (relatórios automaticamente produzidos pelo TestLink) motivaram a modificação de
requisitos e correções no código.
1
http://www.ingenico.com.br/pt/
http://www.yworks.com/en/index.html
3
testlink.org
2
102
SAST
3. Aplicação
Por se tratar de uma aplicação industrial, detalhes sobre objetivos e funcionalidades não
podem ser descritos devido à necessidade de sigilo. No entanto, informações gerais são
apresentadas a seguir para caracterizar o perfil e a magnitude do sistema considerado.
A aplicação é um sistema distribuı́do de grande porte para controle de informações
obtidas através de dispositivos portáteis de autenticação biométrica e coleta de dados.
A arquitetura é formada por módulos controladores locais e globais que se comunicam
através da web e por módulos embarcados em dispositivos portáteis. Como requisitos,
a aplicação trata desde o armazenamento, gerência de dados e relatórios até o controle e
monitoramento da qualidade de serviços e proteção. Os requisitos funcionais foram descritos através de 21 casos de uso, onde cada um possui, em média 520 palavras, variando
entre 400 e 900 palavras.
As principais tecnologias utilizadas no desenvolvimento da aplicação foram:
(i) Linguagem Groovy para plataforma JVM; (ii) Framework Web Grails; (iii) Apache
Tomcat; (iv) Banco de dados relacional PostgreSQL; (v) Comunicação via REST (Representational State Transfer) por meio do formato de troca de dados JSON (JavaScript
Object Notation); (vi) Linguagem C e (vii) Software proprietário. Cada módulo controlador foi desenvolvido usando uma abordagem dirigida por testes, onde testes de unidade
e de integração foram continuamente aplicados. Por sua vez, MBT foi aplicado para realizar teste do sistema integrado a partir dos requisitos estabelecidos nos documentos de
caso de uso.
4. Resultados
A equipe de teste responsável pela revisão dos documentos de casos de uso, geração e
execução dos CCTs foi composta por dois testadores experientes. A partir dos 21 modelos
LTS gerados correspondendo a cada caso de uso, foram gerados um total de 280 casos
de teste para a primeira versão da aplicação. Para as versões subsequentes, onde um total
de nove casos de uso foram modificados, a geração produziu um número menor de casos
de teste: 266. Para a geração, foi aplicado o critério de cobertura all-one-loop-paths que
limita a execução de loops a apenas uma vez. Desta forma, podemos garantir que os
casos de teste cobrem todas as possı́veis combinações de cenários da aplicação, apenas
limitando a quantidade de vezes em que loops são executados.
Devido à complexidade do sistema e o custo de execução de cada caso de teste,
tornou-se inviável executar todos os casos de teste gerados. Além do mais, observouse um certo grau de redundância entre eles. Desta forma, os conjuntos foram reduzidos
procurando manter a cobertura de requisitos e a remoção de sequências redundantes, sem
afetar a capacidade de detecção de defeitos.
A Tabela 1 apresenta a quantidade de casos de teste selecionados em cada versão,
incluindo também a quantidade de casos de teste que falharam e a quantidade de casos
de teste que não puderam ser executados (bloqueados). Foram considerados como bloqueados: (i) casos de teste que foram considerados inválidos devido à falta de atualização
de modificações de requisitos nos documentos de casos de uso; (ii) casos de teste que
não puderam ser executados uma vez que a implementação não estava completa. As
modificações omissas nos casos de uso foram realizadas e os novos casos de teste gerados
foram executados. A terceira versão, que não apresentou falhas ou bloqueios durante a
execução dos casos de teste, foi convertida em release e entregue.
103
SAST
Casos de Teste Selecionados
Casos de Teste que Falharam
Casos de Teste Bloqueados
Versão 1
113
16
10
Versão 2
126
7
13
Versão 3
86
0
0
Tabela 1. Quantidade de casos de teste selecionados, executados com falha e
bloqueados em cada versão.
Apesar da aplicação ter sido sistematicamente testada em nı́vel de unidade e
integração, foram obtidas taxas de falha de 14% e 5% com relação ao total de casos
de teste selecionados para execução na primeira e segunda versão respectivamente. Estas falhas revelaram defeitos importantes e ao mesmo tempo difı́ceis de detectar, pois a
maior parte havia escapado dos nı́veis de teste anteriores, revelando que o sistema ainda
não atendia aos requisitos originais.
Além da efetividade dos casos de teste, o processo de MBT ainda se mostrou
de baixo custo, pois a criação de casos de teste foi automática, demandando apenas um
esforço adicional na validação dos modelos e na importação manual de cada CCT na ferramenta TestLink. No entanto, o primeiro esforço contribuiu diretamente para a correção
do documento de requisitos, enquanto que o segundo é pouco significativo quando comparado à criação manual dos casos de teste na ferramenta.
Por fim, a equipe do projeto concluiu que, apesar dos desafios apresentados, os
quais são discutidos na Seção 6, o processo de MBT contribuiu de forma significativa
para o sucesso obtido no desenvolvimento da aplicação. MBT tornou viável a execução
de casos de teste selecionados sistematicamente, obtidos a baixo custo (considerando que
o processo era de fato centrado em requisitos), que demonstraram efetividade e também
contribuiram para a melhoria do documento de requisitos.
5. Trabalhos Relacionados
Apesar da ampla quantidade de trabalhos acadêmicos desenvolvidos no contexto de MBT,
a quantidade de técnicas efetivamente utilizadas ou avaliadas na indústria ainda é limitada
[Dias Neto et al. 2007]. Um dos principais aspectos de MBT investigados na indústria é
a relação de custo-benefı́cio entre investir (tempo, esforço e dinheiro) na atividade de
modelagem e, com isso, reduzir os custos do teste [Dalal et al. 1999, Holt et al. 2014].
Além disso, também é investigada a possı́vel melhoria na qualidade, cobertura e taxa de
detecção de defeitos dos casos de teste gerados por meio dos modelos. Estes e demais
benefı́cios já foram observados por empresas como a IBM [Farchi et al. 2002], Microsoft
[Grieskamp et al. 2011] e Motorola [Nogueira et al. 2007], em que abordagens MBT são
comparadas com as tradicioniais abordagens de teste, como o teste manual.
Alguns experimentos já foram capazes de detectar uma redução nos custos do
teste [Hemmati et al. 2013, Holt et al. 2014] ao utilizar abordagens MBT, uma vez que os
custos relacionados à criação de modelos são menores do que o custo de criar manualmente os casos de teste para maximizar a cobertura do sistema [Holt et al. 2014]. Sob esta
perspectiva, observamos resultados semelhantes na nossa experiência com MBT, pois a
criação dos modelos permitiu não só a geração automática e sistemática de casos de teste,
mas também a melhoria dos documentos de requisitos.
Por sua vez, Sarma et al. [Sarma et al. 2010] destaca a necessidade de mais ferra104
SAST
mentas MBT que se adequem aos processos de desenvolvimento utilizados na indústria,
devido à dificuldade de adaptar ferramentas MBT aos diferentes tipos de modelos, processos de desenvolvimento ou estratégias de teste [Holt et al. 2014]. Nosso trabalho
apresenta uma vantagem nesse aspecto, pois a ferramenta utilizada (LTS-BT) permite a
implementação de diversas técnicas baseadas em modelos para diferentes objetivos, como
a seleção, priorização e a minimização de casos de teste.
6. Considerações Gerais e Lições Aprendidas
A investigação exploratória através de estudos de caso com aplicações industriais é fundamental para que ganhos e limitações de MBT possam ser melhor compreendidos. Por
um lado, com base nos resultados discutidos neste relato, bem como em outros relatos
apresentados na literatura, são evidentes os benefı́cios que podem ser atingidos com a
aplicação de MBT. Por exemplo, casos de teste podem ser obtidos mais rapidamente e
de forma sistemática, permitindo serem automaticamente importados pela ferramenta de
gerenciamento, que no caso deste relato foi TestLink. Além disso, MBT pode também
elevar a taxa de detecção de defeitos tanto em código quanto nos modelos. No entanto,
ainda há desafios que precisam ser vencidos.
Apesar dos fluxos funcionais terem sido capturados estruturalmente pelos casos de
teste de forma precisa, uma das dificuldades encontradas durante a execução dos casos de
teste foi a distância semântica entre a linguagem de requisitos e os conceitos tecnológicos
concretos do sistema sob teste (conceitos dependentes de plataforma). Muitas vezes, foi
necessário realizar um mapeamento mental dos conceitos. Apesar desta dificuldade ter
diminuı́do à medida que os casos de teste foram executados, ela se mostrou como um
desafio e um indı́cio de que o uso de uma linguagem mais concreta ou especı́fica de
domı́nio no artefato central a partir do qual casos de teste são gerados é imprescindı́vel.
O uso de linguagem controlada poderia também melhorar a descrição dos casos de teste,
tornando-os mais próximos da linguagem concreta do sistema.
Apesar de ter sido feito um acompanhamento rigoroso do processo de desenvolvimento a fim de capturar modificações de requisitos e implantá-las nos documentos de
casos de uso, algumas mudanças realizadas em nı́vel arquitetural ou de código passaram
despercebidas. Isto, por sua vez, gerou falsos positivos durante a execução dos testes. De
fato, a rigidez de formato dos documentos de casos de uso muitas vezes tornaram o processo de correção mais custoso. Desta forma, concluı́mos que nossa escolha de artefato
central, apesar de conveniente, não se mostrou efetiva.
Neste sentido, os modelos LTS, seriam potenciais candidatos a artefato central.
Em particular, eles permitiram uma melhor visualização dos fluxos de execução e vários
erros de junção e desvios de fluxo foram detectados mais facilmente do que com as
inspeções realizadas sobre os documentos originais. No entanto, à medida que crescem,
estes modelos são de difı́cil manipulação e modificação, mesmo considerando os recursos
gráficos apresentados pela ferramenta yEd. Sua construção manual é também tediosa.
Com relação à geração automática de casos de teste, como já era esperado devido
ao uso sistemático de critérios estruturais, a ferramenta LTS-BT produziu mais casos de
teste do que poderiam ser executados ou mesmo eram necessários. Uma importante lição
aprendida é que a seleção manual de casos de teste de sistema em um conjunto com mais
de 20 casos de teste é muito difı́cil, sujeita a erros e custosa. Desta forma, o uso de
algoritmos automáticos para redução dos CCTs se mostrou fundamental, apresentando
105
SAST
resultados mais rápidos e otimizados. Os demais CCTs não executados continuam disponı́veis em TestLink e podem ser utilizados em futuros testes de regressão.
Agradecimentos. Este trabalho foi apoiado em parte pelo Instituto Nacional de Ciência
e Tecnologia para Engenharia de Software (INES)4 /CNPq, processo 573964/2008-4.
Referências
Cartaxo, E. G., Andrade, W. L., Oliveira Neto, F. G., and Machado, P. D. L. (2008). LTSBT: a tool to generate and select functional test cases for embedded systems. In SAC
’08: Proc. of the 2008 ACM Symposium on Applied Computing, pages 1540–1544.
Dalal, S. R., Jain, A., Karunanithi, N., Leaton, J. M., Lott, C. M., Patton, G. C., and
Horowitz, B. M. (1999). Model-based testing in practice. In ICSE ’99: Proc. of the
21st international conference on Software engineering, pages 285–294.
Dias Neto, A. C., Subramanyan, R., Vieira, M., and Travassos, G. H. (2007). A survey
on model-based testing approaches: A systematic review. In Proc. of the 1st ACM Int.
Work. on Emp. Assessment of Soft. Eng. Languages and Technologies, pages 31–36.
El-Far, I. K. and Whittaker, J. A. (2001). Model-based software testing. In Encyclopedia
on Software Engineering. Wiley-Interscience.
Farchi, E., Hartman, A., and Pinter, S. (2002). Using a model-based test generator to test
for standard conformance. IBM Systems Journal, 41(1):89–110.
Grieskamp, W., Kicillof, N., Stobie, K., and Braberman, V. (2011). Model-based quality assurance of protocol documentation: Tools and methodology. Softw. Test. Verif.
Reliab., 21(1):55–71.
Hemmati, H., Arcuri, A., and Briand, L. (2013). Achieving scalable model-based testing
through test case diversity. ACM Trans. Softw. Eng. Methodol., 22(1):6:1–6:42.
Holt, N. E., Briand, L. C., and Torkar, R. (2014). Empirical evaluations on the costeffectiveness of state-based testing: An industrial case study. Information and Software
Technology, 56(8):890 – 910.
Marques, A., Ramalho, F., and Andrade, W. L. (2014). Comparing model-based
testing with traditional testing strategies: An empirical study. In IEEE ICST
Workshops/AMOST 2014.
Nogueira, S., Cartaxo, E. G., Torres, D., Aranha, E., and Marques, R. (2007). Model
based test generation: An industrial experience. In Proceedings of SAST’2007.
Peleska, J., Honisch, A., Lapschies, F., Löding, H., Schmid, H., Smuda, P., Vorobev, E.,
and Zahlten, C. (2011). A real-world benchmark model for testing concurrent real-time
systems in the automotive domain. In Testing Software and Systems, pages 146–161.
Sarma, M., Murthy, P. V. R., Jell, S., and Ulrich, A. (2010). Model-based testing in industry: A case study with two MBT tools. In Proc. of the 5th Workshop on Automation of
Software Test, AST ’10, pages 87–90.
Utting, M. and Legeard, B. (2007). Practical Model-Based Testing: A Tools Approach.
Morgan Kauffman, first edition.
4
www.ines.org.br
106
SAST
Automatização de Testes Funcionais em Dispositivos Móveis
Utilizando a Técnica BDD
Relato de Experiência
Rafael Chiavegatto1 , Lidiane Silva1 , Maryane Pinheiro1 , Auri Marcelo Rizzo Vincenzi2
1
FPF – Fundação Desembargador Paulo Feitoza
Manaus – Amazonas – Brasil
{rafael.chiavegatto, lidiane.silva, maryane.pinheiro}@fpf.br
2
Instituto de Informática – Universidade Federal de Goiás
Goiânia – Goiás – Brasil
[email protected]
Abstract. Testing is an essential activity to ensure the quality of a software product, but its manual execution is costly. This activity becomes even more costly
when performed in the context of mobile applications due to the large amount of
devices with different hardware and screen configurations. One way to minimize
this problem is adopting the test automation of the main flow of the application
using a framework for automating functional testing on Android devices, together with the use of the Behavior Driven Development (BDD) technique, to
reduce the time spent performing the test. This paper presents an initial investigation of the gains obtained with automation in this scenario.
1. Introdução
Com o advento das tecnologias da informação e comunicação, o mercado de software em
aplicativos móveis tem cada vez mais importância no escopo de desenvolvimento, principalmente para dispositivos com o sistema operacional Android, presente em mais de
80% dos dispositivos móveis atuais [Exame 2014]. Garantir a qualidade nos aplicativos
desenvolvidos tem um alto custo dada, principalmente, a grande diversidade de dispositivos a serem verificados. Esse problema evidencia a necessidade de automatizar os testes
para reduzir o esforço na etapa de validação do produto. Com a redução do esforço que a
automatização proporciona, o analista de teste poderá especificar cenários mais elaborados que vão além de simplesmente testar os cenários do fluxo principal do sistema.
Este trabalho descreve como resolver esta problemática, utilizando a técnica de
Behaviour Driven Development (BDD) em conjunto com a técnica de automatização de
testes, com apoio do arcabouço Cucumber-JVM para utilização da técnica de BDD e os
arcabouços Robotium e JUnit para automatização da execução dos testes, ilustrando os
ganhos e benefı́cios com a junção das técnicas.
O restante deste artigo está organizado da seguinte forma: na Seção 2 são apresentadas as terminologias e conceitos básicos necessários para a compreensão do texto; a
Seção 3 descreve a proposta de automatização de testes utilizando as ferramentas mencionadas na Seção 2 e ilustra o processo proposto por meio de uma prova de conceito; na
Seção 4 são sintetizados os resultados obtidos e na Seção 5 é apresentada a conclusão e
possı́veis desdobramentos para pesquisas futuras.
107
SAST
2. Terminologia e Conceitos Básicos
A técnica de automação é voltada principalmente para melhoria da qualidade, baseiase fortemente na teoria de Teste de Software, para aplicar as recomendações dos testes
manuais na automação dos testes. Não se deseja eliminar o teste manual mas sim reduzilo ao máximo, e focá-lo naquilo que é muito caro automatizar [Molinari 2010].
A automatização de testes se intensificou com as práticas ágeis e se mostra eficaz
para melhorar a qualidade do software, porém, inicialmente, a adoção da técnica é mais
cara, pois demanda um tempo maior para a elaboração dos scripts e requer mão de obra
qualificada. A automatização de testes demonstra um custo benefı́cio quando é necessário
executar testes repetitivos e na execução de testes de regressão.
Neste trabalho a automatização de testes é utilizada juntamente com a técnica de
BDD, para facilitar a manutenção e deixar a documentação mais próxima dos scripts
elaborados. Existe uma grande diversidade de arcabouços que amparam o uso do BDD
em várias linguagens de programação. O Cucumber – JVM [Wynne & Hellesoy 2012]
é utilizado neste relato de experiência para especificação de cenários de testes [Wynne & Hellesoy 2012], conforme ilustrado na Figura 1(a).
(a) Especificação
(b) Mapeamento
Figura 1. Exemplo de cenário de testes no Cucumber
Observa-se a descrição do cenário em alto nı́vel (Figura 1(a)) e o posterior mapeamento do mesmo para a sua implementação (Figura 1(b)). Finalmente, para a execução
dos testes (cenários especificados), são utilizados os arcabouços Robotium [Knott 2011]
e JUnit [Hunt & Thomas 2000]. Para mais informações sobre as tecnologias empregadas
o leitor pode consultar as referências oferecidas.
3. BDD e Arcabouços para Automatização de Testes Fucionais
Nesta prova de conceito é utilizado um aplicativo para gerenciamento de abastecimento de combustı́vel para veı́culos, chamado Desempenho Mensal, disponı́vel em:
https://github.com/chiavegatto/CalcDesempenho. Os dados gerais do
projeto, calculados com a ferramenta de gerenciamento de qualidade de código SonarQube [SonarSource S.A 2008], são apresentados na Tabela 1.
Tabela 1. Informações estruturais da aplicação extraı́das da ferramenta Sonar
Linhas de código
969
Complexidade das Classes
9.0
Complexidade das Funções
1.9
Qtde de Classes
14
Qtde de Funções
63
As seguintes funcionalidades foram implementadas: 1) adicionar abastecimento;
2) ver abastecimentos adicionados; 3) ver abastecimentos de meses anteriores, assim
108
SAST
como seu desempenho; e 4) ver desempenho mensal (mês corrente). Apesar do aplicativo ser considerado de baixa complexidade, a execução dos testes de forma manual se
torna onerosa e demanda tempo e esforço, devido à grande quantidade de dispositivos.
No plano de teste considerado, foram especificados os ambientes de execução, conforme
apresentado na Tabela 2.
Tabela 2. Relação dos dispositivos a serem testados
Tipo
Smartphone
Tablet
Marca
LG
LG
LG
LG
LG
LG
LG
LG
Motorola
Motorola
Motorola
Motorola
Motorola
Samsung
Samsung
Samsung
Samsung
Samsung
Samsung
Sony Ericsson
Sony Ericsson
Sony Ericsson
Samsung
Motorola
Dispositivo
Optimus L3
Optimus Hub
Optimus
LG GW620
Victor
Optimus 3D Max
Prada 3.0
Optimus L7
Defy Mini
Fire XT
Motorola Primus
Razr
Jorian
Galaxy Y Pro
Galaxy Y
Galaxy Y Duos
Galaxy Ace
Galaxy S III
Galaxy Note
Live Walkman
Xperia U
Xperia S/Nozomi
Galaxy Tab 2
Xoom
Modelo
E400
E510
GT540
GW620
E730
P720
P940
P705
XT320
XT531
Primus
XT910
XT 605
GT-B5510
GT-S5360
GT-S6102B
GT-S5830
SGH-i747
GT-N7000
WT19
ST25
LT26
P3100
MZ604
Resolução
240x320
320x480
320x480
320x480
480x800
480x800
480x800
480x800
320x480
320x480
480x800
540x960
640x480
240x320
240x320
240x320
320x480
720x1280
800x1280
320x480
480x854
720x1280
600x1024
800x1280
Versão OS
Android Gingerbread
Android Gingerbread
Android Gingerbread
Android Gingerbread
Android Gingerbread
Android Gingerbread
Android Gingerbread
Android ICS
Android Gingerbread
Android Gingerbread
Android Gingerbread
Android Gingerbread
Android Gingerbread
Android Gingerbread
Android Gingerbread
Android Gingerbread
Android Gingerbread
Android ICS
Android Gingerbread
Android Gingerbread
Android Gingerbread
Android Gingerbread
Android Jelly Bean
Android Jelly Bean
O plano de teste demanda a realização de testes funcionais e exploratórios [Whittaker 2009]. O intuito é automatizar os testes funcionais de modo que o
tempo de execução seja reduzido, e o analista de teste tenha mais tempo para executar
cenários mais elaborados, sem se preocupar com falha no fluxo principal da aplicação.
Na especificação dos testes manuais são descritos: 1) o objetivo do teste, 2) as précondições necessárias para execução, 3) os passos a serem executados, e 4) o resultado
esperado. Além disso, os critérios de teste Particionamento de Equivalência e Análise
de Valor Limite [Delamaro et al. 2007] são utilizados com intuito de explorar de forma
adequada o domı́nio de entrada do produto em teste.
Nessa forma de especificação, os casos de teste não fornecem todas as informações
detalhadas para execução, assim como termos técnicos, pois o responsável pela sua
elaboração possui conhecimento sobre as regras de negócio e conhece todos os termos
utilizados. Isso pode dificultar a execução se o executor dos testes não for o mesmo que
os elaborou. Esse problema pode ser minimizado com a utilização da técnica de BDD.
3.1. Automatização dos cenários e execução
Para elaboração da prova de conceito as seguintes atividades para execução das técnicas
de BDD e automatização de testes foram realizadas, de acordo com a Figura 2. A primeira
atividade consistiu em elaborar os cenários que foram automatizados. O cenário é representado pelo arquivo .feature. A Figura 3(a) mostra um dos cenários especificados na
prova de conceito: “Excluir abastecimento cadastrado”.
109
SAST
Na segunda atividade executada, o arcabouço Cucumber-JVM realiza a leitura dos
cenários do arquivo .feature. Caso a feature não esteja implementada, o CucumberJVM exibe no console do Integrated Development Environment (IDE) o cenário a ser
implementado.
Figura 2. Fluxo das atividades de BDD com automatização de testes
A terceira atividade envolveu a implementação dos cenários exibidos no console, com a utilização dos arcabouços Robotium e JUnit, estes são responsáveis pela
automatização das funcionalidades das features, conforme Figura 3(b).
(a) Cenário de teste
(b) Implementação
Figura 3. Passos do processo de automatização.
Nesta figura são mostrados os mesmos métodos vazios que foram listados no
console, agora implementados pelo analista de teste que utilizará uma linguagem de
programação, neste caso, Java que é a linguagem utilizada pelo Robotium. É necessário
implementar estes métodos de acordo com as necessidades e particularidades do projeto.
A quarta e última atividade, é a execução de todos os cenários implementados a
partir das features, sendo possı́vel a execução dos testes automatizados em todos os dispositivos. Estes devem estar conectados na máquina e serão executados de forma sequencial.
Para execução do projeto é utilizada a ferramenta Maven [Apache 2002]. A
própria ferramenta lista todos os dispositivos conectados na máquina e executa os testes
sequencialmente. Após o término da execução dos passos dos cenários em um dispositivo, são indicados no console os passos que passaram (passed), os que não passaram
(fail) e os que não foram executados (not performed), em função de uma falha detectada
no aplicativo ou de algum problema no dispositivo.
110
SAST
4. Análise dos Resultados
No contexto da prova de conceito, executar testes de forma manual é custoso e demanda
um grande esforço e principalmente tempo. Todos os casos de teste funcionais são executados em todos os dispositivos que fazem parte do plano de teste. Tendo em vista que para
um software de complexidade alta, existirá uma infinidade de casos de teste para cobrir
seu fluxo principal, demandando um maior tempo de execução.
Na Tabela 3, é apresentado a comparação dos resultados da execução dos casos de
teste (ct) manuais e dos cenários (c) de teste automatizados.
Tabela 3. Resultado da execução dos testes: manual versus automatizado
Qtde de dispositivos
Qtde de ct
24
24
18
18
Tempo de execução por
dispositivo (h)
2 horas
5 minutos
Tempo
médio
de
execução por ct/c (min)
6,67 minutos
17 segundos
Qtde de ct/c total
Tempo total
432
432
48 horas
2 horas
No teste manual foram especificados 18 casos de teste, cada um executado em
aproximadamente 6,67 minutos, sendo totalizadas 2 horas de execução. Os testes foram
repetidos nos 24 dispositivos, totalizando 432 execuções de casos de teste, realizados em
48 horas.
No teste automatizado foram especificados 18 cenários de teste, cada um executado em aproximadamente 17 segundos, sendo totalizados 5 minutos de execução. Os
testes foram repetidos nos 24 dispositivos, totalizando 432 execuções de cenários de teste,
realizados em aproximadamente 2 horas, uma redução no tempo em torno de 95,8%.
Ao comparar o tempo de execução total é notória a significativa redução no tempo
de execução dos testes, em virtude da agilidade que as ferramentas proporcionam. É
importante enfatizar que a primeira execução dos testes automatizados, considerando a
sua construção, demandará um tempo maior do que a execução manual em função da
necessidade de configuração das ferramentas e desenvolvimento dos scripts de teste.
Mais um fator a ser ressaltado é a manutenibilidade dos scripts de testes. Com a
junção das técnicas de automatização e BDD, e possı́vel deixar os scripts mais próximos
aos requisitos do sistema. Estes são especificados no arcabouço Cucumber e tornam-se
requisitos funcionais, extraı́dos de forma colaborativa e usados como teste de aceitação.
Desta forma, a manutenção dos scripts é simplificada, pois, se uma funcionalidade é
alterada, a rastreabilidade facilita a localização do método referente ao requisito, que
também deve ser modificado no script.
A prova de conceito tem como principal objetivo demonstrar que mesmo que os
benefı́cios da automatização sejam adquiridos a longo prazo, é vantajosa a adoção da
técnica, pois, o ganho na qualidade dos requisitos do sistema, na manutenibilidade dos
scripts e no tempo de reexecução dos testes é visivelmente significativo, refletindo diretamente na qualidade do software.
5. Conclusão
Para que haja agilidade nestas atividades a adoção de ferramentas que possam automatizar
tarefas repetitivas, agrega ganhos e contribui para o desenvolvimento ágil e qualitativo de
um software. Além de automatizar, a utilização de uma linguagem comum durante o
111
SAST
desenvolvimento, facilita e estimula a contribuição colaborativa entre os envolvidos no
projeto.
Na prova de conceito foi possı́vel demonstrar a integração de um dos arcabouços
mais utilizados para automatização de testes mobile, com um arcabouço para a utilização
da técnica de BDD. Com essa integração foi possı́vel observar os seguintes benefı́cios:
• Redução significativa no esforço e tempo na execução dos testes, principalmente
após a segunda execução;
• Esforço concentrado em cenários mais elaborados (testes exploratórios); Alta
automatização de testes, facilidade para execução de testes de regressão (aumento
na qualidade);
• Melhora na contribuição entre os envolvidos no projeto;
• Maior compreensão dos cenários especificados (linguagem natural);
• Facilidade na manutenção dos cenários e scripts de teste (Cenários associados ao
código dos scripts);
• Maior visualização no que está sendo desenvolvido;
• Ganho na qualidade do software.
Como trabalhos futuros um estudo de caso detalhado será desenvolvido com diferentes equipes visando avaliar qualitativamente e quantitativamente as vantagens e desvantagens da automatização dos testes.
Referências
Apache (2002). Apache Maven project. Página Web. Disponı́vel em:http://maven.
apache.org/. Acesso em: 26/06/2014.
Delamaro, M. E., Maldonado, J. C., & Jino, M. (2007). Introdução ao Teste de Software.
Elsevier, Rio de Janeiro, RJ.
Exame (2014).
Android está em cerca de 80% de smartphones vendidos em 2013.
Notı́cia On-line.
Disponivel em:
http://exame.abril.com.br/tecnologia/noticias/
android-esta-em-cerca-de-80-de-smartphones-vendidos-em-2013.
Acesso em: 26/06/2014.
Hunt, A. & Thomas, D. (2000). Pragmatic Unit Testing in Java with JUnit. AddisonWesley Professional.
Knott, D. (2011). Robotium @ xing. automated regression tests on mobile android devices. Agile Record, (7):26–29.
Molinari, L. (2010). Inovação e Automação de Testes de Software. Érica.
SonarSource S.A (2008). SonarSource. Página Web. Disponı́vel em:http://www.
sonarqube.org/. Acesso em: 26/06/2014.
Whittaker, J. A. (2009). Exploratory Software Testing: Tips, Tricks, Tours, and Techniques
to Guide Test Design. Addison-Wesley Professional.
Wynne, M. & Hellesoy, A. (2012). The Cucumber Book: Behaviour-Driven Development
for Testers and Developers. Pragmatic Bookshelf.
112
SAST
The Role of Software Testing on Modernizing a Balloon
Ground Station
Fátima Mattiello-Francisco1, Mariam Gomez1, William K.
Ariyoshi2, Fernando Aranha2, Marcelo Essado3
1
National Institute for Space Research (INPE)
Caixa Postal 515 – 91.501-970 – São José dos Campos – SP – Brazil
2
Beta/TELECOM
São José dos Campos – SP - Brazil
3
EMSISTI- Sistemas e Soluções em Tecnologia da Informação
Franca – SP - Brazil
{fatima.mattiello,mariam.gomez}@inpe.br, [email protected],
Abstract. This paper reports the use of different software testing techniques
and tools in a verification and validation (V&V) strategy for software and
hardware improvements on an existing old generation balloon ground station.
A model-based testing method was combined with both human machine
interface and communication testing techniques to carry out service driven test
cases specification. The strategy was effective on validating the behavior of
the new flight control system (OPS/ES) integrated to the ground station and
useful on verification of the server system (OPS/Server) on the tasks of routing
the original ground station TM and TC channels to TCP/IP gateways.
1. Introdution
Aiming at a cost reduction on the development and operations of the balloon-borne
protoMIRAX telescope experiment, the system requirement for reusing the ground
facilities available at INPE was a challenge to the ground system engineers.
Different age technologies were required to interoperate. The existing one
decade-old balloon ground station needed little hardware maintenance, but significant
effort on software updating was required. The improvements on INPE´s ground station
comprise only investments on information technology. The standalone computer system
available in the balloon ground station rack dedicated to run the flight control software
was modernized both in hardware and software by new system named OPS/ES. In
addition, a new server computer, properly configured for Ethernet connections, has
extended the existing ground station facilities with a network switch, serial converters
and a new software named OPS/Server in order to support the available uplink and
downlink channels being mapped to TCP/IP gateways.
Both solutions was developed by only one supplier (Sup 1) and the acceptance
phase leaded by costumer INPE at LabV&Vsis was supported by other company (Sup 2)
as independent verification and validation (V&V) activities.
113
SAST
This paper reports the experimental results of the V&V strategy adopted for
systematizing the OPS/ES and OPS/Server acceptance process. Section 2 presents the
concept of service in the space system engineering and its use as a V&V strategy.
Section 3 and 4 introduces the OPS/ES and OPS/Server respectively, the test bed and
how the proposed V&V strategy was used. In Section 5, the V&V strategy is discussed
in terms of the test cases set and fault detection capability, taking into account the role
of the techniques and tools used for both the test cases specification and management of
test execution and retesting cycles. Finally, the conclusions are presented in Section 6.
2. Service driven approach
In space system engineering, a service is a set of capabilities that a component provides
to another component via an interface in order to associate the set of operations that can
be invoked and performed through the service interface “Service specifications define
the capabilities, behavior and external interfaces, but do not define the implementation”.
[CCSDS 2010]
In the context of V&V, the verification of the expected behavior of a system and
the interfaces at system level (black box testing) can be oriented by the behavioral
models of a particular service provided by one or more reactive components [MattielloFrancisco at al. 2013]. The service defines the set of events accepted by the component
at its available external interfaces which stimulate the component actions, performing
the expected behavior. Thus, the expected behavior of a service at a particular
abstraction level can be represented by the automata formalism, where the states of the
automata represent the actions and the events are the state transitions.
Some model-based testing (MBT) approaches use such formalism to derive test
cases from behavioral models of the system under testing (SUT). A test case is one path
of the SUT model as result from a traverse algorithm implemented by a tool. In the last
decade there are many contributions of MBT techniques, methodologies and tools in
order to automatically generate test cases specification for reactive system [Shunkun at
al. 2013]. In particular, the concept of service according to CCSDS (2010) can be found
in two MBT methodologies developed at INPE and operational in LabV&Vsis to guide
the construction of behavioral models of the space SUT [Ambrosio 2005] and
[Mattiello-Francisco at al. 2012].
The proposed service driven approach is a V&V strategy that use automatic and
manual testing techniques, for test case specification aiming at validating SUT aspects
in terms of human machine interface (HMI), communication functionality and control
actions. Conformance and Fault Injection (CoFI) [Ambrosio 2005] is a MBT
methodology used to guide automatic test cases generation focusing control actions.
The TestLINK tool is used to supporting the management of the Test Case
suites for OPS/ES e OPS/Server software acceptance testing phase as a Test Project
manager [http://testlink.org/]. The TestLINK supports the SUT description and
definition of Testers (users) involved on testing activities. Test Plans are built
describing both the Services to be verified using each testing technique and the testing
environment (Test bed) required. For each test case execution Build memorizes the Test
Case Result (Passed, Failed, Blocked) providing testing management metrics and
supporting Report.
114
SAST
3. Ground Balloon Flight Control System - OPS/ES
On the context of balloon ground station modernization for protoMIRAX campaigns
operation purpose, the OPS/ES system substitutes the obsolete ground station
standalone computer. As ground station equipment’s integrator, this computer major
functionality is to support the ground station operator on balloon flight control.
The new software OPS/ES was designed using LabVIEW 2013, National
Instruments™ [http://www.ni.com/labview/pt/], and it is the integrator element of the
ground station and on-board system equipment. It enables flight control of the balloon
by sending telecommand and visualization of the flight parameters received by
telemetry. These parameters are displayed as real-time values, status indicators, leds and
graphics. OPS/ES also creates logs of all telemetry and telecommand information since
the beginning of the campaign. In addition, OPS/ES has a tracker function to always
keep the antenna pointed to the balloon to prevent connection losses. For this purpose it
uses the GPS antenna placed in the on-board system. It also has a mapping function
using a Google Maps API that tracks the balloon’s flight path.
OPS/ES software code size is approximately 1563KB and runs in an industrial
rack mounted computer whose hardware configuration is: 300W Power Supply;
Motherboard ATX-SB600C with one PCI-Express x16 slot and six PCI-32bits slots;
Processor Intel® Core™ i5-2400; RAM Memory Kingston 4GB DDR3 1333MHz;
HDD Seagate 500GB; DVD-RW. OPS/ES has four RS232 serial cables to communicate
with other ground station equipment: MUX/DMX – Telemetry; MUX/DMX –
Telecommand; Antenna Positioning Unit; and RF Decoder.
3.1. OPS/ES Test Plans, Test Cases Specification and Test bed
Two Test Plans were elaborated to carry on the testing activities related to OPS/ES
acceptance: (a) the Test Plan guided by Human Machine Interface Testing Technique,
named OPS/ES Interface TP; and (b) the Test Plan guided by MBT using CoFI
methodology, named OPS/ES Control TP.
The Test bed was composed of the OPS/ES software itself embedded in the
Ground Station standalone computer, the MUX/DMX chains and channels for groundspace communication. In addition, a software simulator provided by SUP 1 simulated
the telecommand and telemetry functions on board of the balloon.
Based on Inputs and Outputs available to control and observe OPS/ES operation
and the software design artifacts such as user manual provided by SUP 1, an abstract
view of the SUT, as a black box, allowed the identification of 4 services associated to
the human interface and 3 services associated to control, as summarized in Table 1.
The OPS/ES Interface TP comprises the verification of the following 4 services
SI-1 – TM: all telemetry data visualized by the Flight Control Operator (OPS/ES
operator) on OPS/ES display, as output; SI-2 – TC: all input (buttons and parameters)
and output event (led) available to the OPS/ES operator for telecommands selection
and transmission to the balloon flight control on board; SI-3 – RH: on time recording
on Historical file all telecommands sent by the OPS/ES operator and all telemetry data
received by OPS/ES software during the campaign; SI-4 – IC: all OPS/ES operational
parameters available for OPS/ES operator setting as Initial Configuration.
115
SAST
Two sets of test cases were manually specified for each SI, taking into account
the inputs variables provided by OPS/ES software to OPS/ES operator performing the
service. One set, referred as Normal (N), comprises OPS/ES expected behavior on the
service execution. For instance SI-1: telemetry value within the specified range shall be
displayed in the graphical interface and those out-of limit values shall be signalized with
visual warnings. The other set comprises Robustness (R) aspects, for instance, wrong
inputs. The number of test cases (N) and (R) per service related to SIs is presented in
Table 1. The expressive number of (N) test cases compared to (R) is due to the quantity
and nature of HMI screen components: (i) all output variables are displaying in
graphical screens using LabView libraries in SI-1; (ii) input variables are mostly
represented by buttons and parameters values already defined for OPS/ES operator
selection in SI-2; (iii) data log needs to be tested only in terms of timestamp and delay in
SI-3; (iv) only one input variable (Antenna Position) is open in SI-4 for OPS/ES
configuration by means of writing localization coordinates, which required one (R) test
case specification to validate the OPS/ES robustness in terms of invalid parameters.
The OPS/ES Control TP comprises the verification of the OPS/ES software
behavior on the following 3 services: SC-1 – TM: the tasks of acquiring and displaying
on OPS/ES graphics accordingly all telemetry parameters related to the different
equipment integrated in ground station; SC-2 – TC: the tasks of both sending
telecommands (sequence of buttons and parameters verified in SI-2) under selection of
OPS/ES operator to the on board balloon flight control system and feed backing on
screen telemetry data related to each telecommand effective execution on board for
monitoring purpose on ground; SC-3 – FE: the task of Flight Ending, transferring all
files recorded by OPS/ES during the campaign to the mission historical data center.
The specification of test cases for these services followed three main steps of
CoFI methodology: (a) the construction of a set of Finite State Machine (FSM) that
models the expected behavior of the services provided by SUT, (b) models validation
and (c) abstract test-case generated automatically using Condado tool [Martins 1999].
According to CoFI, a service behavior is modeled in different perspectives: (i) normal,
(ii) specified exceptions, (iii) inopportune inputs (i.e., corrects but occurring in wrong
moments) and (iv) invalid inputs caused by hardware faults. The models are generally
small because two levels of decomposition are taken into account: (i) the services
provided by system under test and (ii) the types of behavior, which are named as: Fault
Tolerance, Sneak Path, Specified Exception and Normal, respectively associated to the
input events: invalid, inopportune, specified exceptions, normal. Moreover, it is possible
to create more than one model to represent the same type of behavior of a service. The
selection of the inputs to be considered in the models must take into account the
controllability and observability available in the test executing tools (or test
environment). Thus, the test environment has to provide mechanisms for input events
and observation of the system outputs.
For sake of space, the FSM models built for the control services are not
presented. Table 1 summarizes the number of models built per service resulting from
only two types of behavior: Normal (N) and Sneak Path (R) which covers robustness
behavior related to wrong inputs. Exceptions models were not built because exception
behaviors were not specified in OPS/ES software requirement document. From those
116
SAST
models, abstract test-case suites were generated automatically by Condado tool. One
can observe in Table 1 a huge number of test cases generated per suite, in particular
from (R) models. The reason is the combination of input events (transitions) that are
added to each state of the nominal model in order to represent all unexpected input
variables. A test selection was necessary and manually performed by test expert analyst
using two criteria: (i) discarding all test case that comprise a step sequence already
included in other test case, considering as duplicated test case or similar; (ii) choosing
only one representative value in domain for each input variable, since most input and
output variable were already covered by the test cases specified in Interface Test Plan.
The numbers of test cases selected and effectively translated to executable test-cases for
SCs are presented by numerators in cells of Table 1 (three columns corresponding to
SCs on last two lines).
4. Gateways Mapping System – OPS/Server
The purpose of the software OPS/Server is to provide TCP/IP gateways to the payload
controllers and scientists (mission end users) for mission operation. Protomirax’s board
and ground system originally uses asynchronous RS232 and synchronous RS422
communication. These channels are routed respectively to Ethernet converter and to
USB converter in order to support OPS/Server with TCP/IP connections.
OPS/Server software was designed using LabVIEW and its code size is
approximately 241KB running in a computer configured with W7 Professional,
Processor Intel® Core™ i7-3770; RAM Memory 8GB; HDD 1TB; DVD-RW.
4.1. OPS/Server Test Plan, Test Cases Specification and Test bed
Only one Test Plan, named OPS/Server Communication TP, was elaborated to carry
on the testing activities related to ground-ground communication protocols that were
properly defined to support the OPS/Server routing functions.
The service driven approach was also useful for OPS/Server test case
specification that comprised the verification of the ground-ground communication
protocols involved on 3 services: SM-1 – TC: the task of sending direct telecommands
from TCP/IP gateways to particular Ground Station channel; SM-2 – TM: the task of
transmitting internally in ground all telemetry packets received from different ground
station channels to the end users; SM-3 – TMTC: the tasks of sending telecommands
and receiving telemetry simultaneously, covering SM-1 and SM-2 execution together.
Test cases were manually specified for SMs addressing three main aspects:
message format, communication faults and performance of the routing task.
5. Testing Results and Discussion
In total, 125 test cases (N) and (R) were effectively executed, as presented in Table 1 by
the cells numerators (last two lines). The corresponding denominators show the number
of test cases Failed (9%) and/or Blocked (14%) during first cycle of testing. Blocked
test cases were due to (i) lack of on board simulator functionalities or (ii)
misunderstandings on test case specification. Test cases were rewritten and functions
added to the simulator improving the Test bed to support the second cycle of testing,
which test cases Passed.
117
SAST
Table 1. Numbers of Models, Test Cases generated and executed per service
V&V
OPS/ ES
strategy
Interface Test Plan
Services
SI-1
SI-2
SI-3
SI-4
N
-
-
-
R
-
-
-
#Test
Cases
N
36
26
7
R
0
0
#Execut
N
36/11
R
0
#Models
OPS/ Server
Total
Control Test Plan
Communication TP
SC-1
SC-2
SC-3
SM-1
SM-2
SM-3
-
3
1
2
-
-
-
6
-
3
1
1
-
-
-
5
1
51
13
41
2
5
1
183
0
1
832
978
672
2
3
0
2527
26/2
7/4
1
5/1
6/5
2/1
2
5/1
1/1
91/26
0
0
1/1
4
19
5
2/1
3/1
0
34/3
10
The cells highlighted in gray show that most failures detection capability of the Test
Plans are concentrated in two services: (i) Interface TP pointed out 6 failures, 3 detected
by SI-1 test cases and all solved with the above mentioned Test bed improvements; (ii)
Control TP pointed out 3 failures, all detected by SC-2; (iii) no failure was detected by
Communication TP. Two failures detected in SC-2 were due to lack of on board
hardware in the loop. Only one failure was in fact software fault that was corrected.
6. Conclusion
The V&V strategy demonstrates that: (1) focus the model-based testing efforts on the
control services is cost-effective whether others testing techniques can be used to
supplement the whole software product verification; (2) the correspondence between
test cases specification and the resources available on the test bed for test cases control
and observation is essential to reduce testing effort and risk.
7. References
Ambrosio, A. M.. “COFI: uma abordagem combinando teste de conformidade e injeção de falhas para
validação de software em aplicações espaciais.”, 2005, 209 p. (INPE-13264-TDI/1031). Tese
(Doutorado em Computação Aplicada) - Instituto Nacional de Pesquisas Espaciais, São José dos
Campos, 2005
CCSDS-520.1-M-1. Mission Operation Reference Model. “Recommended for Space Data Systems
Practice”. (July 2010)
Mattiello-Francisco, F.; Villani, E.; Martins, E.; Dutra, T.; Coelho, B.; Ambrosio, A. M.; “An Experience
on the Technology Transfer of CoFI Methodology to Automotive Domain”; LADC2013 – Sixth LatinAmerican Symposium on Dependable Computing, Industrial Track – Rio de Janeiro 2-5 Abril 2013.
Martins, E.; Sabião, S.B.; Ambrosio, A.M. - "ConData: a Tool for Automating Specification-based Test
Case Generation for Communication Systems". In: Software Quality Journal, Vol. 8, No.4, 303-319,
1999.
Mattiello-Francisco, F.; Martins, E.; Cavalli, A.R.; Yano, E.T.; “InRob: An approach for testing
interoperability and robustness of real-time embedded software.” In: Journal of Systems and Software,
85,1, January 2012, 3-15.
Shunkun, Y.; Bin, L.; Shihai, W.; Minyan, L.; “Model-based robustness testing for avionics-embedded
software.” In: Chinese Journal of Aeronautics and Astronautics, 26(3), 2013, 730-740.
118

SAST 2014 - Instituto de Computação

Transcrição

Documentos relacionados

Pesquisas relacionadas com teste Speedtest.net

SAST 2012 VI Workshop Brasileiro de Teste de

do arquivo. - Marcos Treino Físico

SAST 2015

ARTIGO ORIGINAL Validade do teste aeróbico de corrida de vai

IT-141 - Abendi

Veja o caso - Specialisterne

Pinagem da porta serial RS232

exames de admissao em univ estrangeiras

do livro QualidadeBR

MD MD MD MD MD MD MD MD MD MD MD MD MD