• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tese de Doutorado
DOI
https://doi.org/10.11606/T.55.2020.tde-02092020-091958
Documento
Autor
Nome completo
Carlos Diego Nascimento Damasceno
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Carlos, 2020
Orientador
Banca examinadora
Simão, Adenilso da Silva (Presidente)
Sampaio, Augusto Cezar Alves
Souza, Simone do Rocio Senger de
Walkinshaw, Neil
Título em inglês
Learning finite state machine models of evolving systems: From evolution over time to variability in space
Palavras-chave em inglês
Automata learning
Reactive systems
Software evolution
Software variability
Resumo em inglês
Maintenance and evolution have been accepted as integral principles in the software development life-cycle. They are essential for any system that operates in or addresses problems or activities of the real world if it is to remain useful and profitable. Nevertheless, as time passes and modifications occur, modeling artifacts are often neglected due to the lack of proper maintenance. Hence, it may render outdated models and hinder the application of model-based reasoning techniques, such as model-based testing and model checking. To address these issues, recent academic and industrial studies have shown that finite state machine (FSM) model learning techniques are becoming increasingly popular in software verification and testing. Despite these advances, model learning algorithms are still hampered by scalability issues, as well as the constant changes over time that may require learning from scratch. Furthermore, there is a lack of investigations about learning strategies for software product lines (SPL), i.e., systems where variants shall co-exist to satisfying the needs of distinct market segments and, hence, incorporate variability in space. In this PhD Thesis, we improve upon the state-of-the-art of model-based software engineering by introducing theoretical and experimental contributions to address model learning in the setting of evolving systems that incorporate modifications over time and variability in space. Our main contributions are three-fold: (i) We have introduced the partial-Dynamic L* M, an adaptive algorithm that explores models from pre-existing versions onthe- fly to discard redundant and deprecated knowledge in terms of input sequences that may not lead to state discovery. Using realistic models of the OpenSSL toolkit, we have shown that our algorithm has been more efficient than state-of-the-art techniques and less sensitive to software evolution. (ii) We have filled the gap of model learning algorithms for variability-intensive systems by introducing the FFSMDiff algorithm. It is an automated technique to identify similar behavior shared among product-specific FSMs, annotate states, and transitions with feature constraints, and integrate them into succinct featured finite state machines (FFSM). Using 105 FSMs derived from six SPLs of academic benchmarks, we have shown that our algorithm can effectively merge families of state machines into succinct FFSMs, especially if there is high feature reuse among products. (iii) We have extended our expertise upon the FFSMDiff algorithm and reported our experiences on learning FFSMs through product sampling. Our results have indicated that FFSMs learned by sampling can be as precise as those learned from exhaustive analysis and hence, collectively cover the behavior of an SPL.
Título em português
Aprendizado de modelos de máquinas de estados finitos de sistemas em evolução: Da evolução ao longo do tempo para variabilidade em espaço
Palavras-chave em português
Aprendizado de autômatos
Evolução de software
Sistemas reativos
Varibilidade de software
Resumo em português
Manutenção e evolução são principios básicos do ciclo de vida de software. Apesar disso, artefatos de modelagem frequentemente tendem a ser negligenciados. Consequentemente, modelos podem ficar desatualizados e dificultar a adoção de algumas técnicas tais como verificação e teste baseado em modelos. Estudos recentes têm mostrado que técnicas de aprendizado de modelos de máquinas de estados finitos têm se tornado bastante populares no teste e verificação de software. Apesar disso, algoritmos para aprendizado de modelos ainda sofrem com problemas de escalabilidade assim como com a evolução ao longo do tempo que pode requerer o re-aprendizado do zero. Adicionalmente, há uma lacuna de pesquisas sobre estratégias de aprendizado de modelos para linhas de produto de software, i.e., sistemas onde variantes de software co-existem e, consequentemente, incorporam variabilidade no espaço. Esta Tese de Doutorado avança no estado da arte da engenharia de software baseada em modelos apresentando contribuições teóricas e práticas sobre aprendizado de modelos para sistemas que incorporam evolução ao longo do tempo e variabilidade no espaço. As três principais contribuições desta Tese de Doutorado são: (i) um algoritmo adaptativo de aprendizado de modelos que explora versões de software pré-existentes on-the-fly para descartar conhecimento redundante e descontinuado representados em termos de sequências de entradas que não levem à descoberta de estados. Usando máquinas de estados reais do projeto OpenSSL, mostra-se que o algoritmo proposto consegue ser mais eficiente que o estado da arte e menos sensível à evolução de software. (ii) Preenche-se a lacuna de pesquisas em algoritmos de aprendizado de modelos para linhas de produto com o algoritmo FFSMDiff , uma técnica automatizada para identificar comportamentos similares e anotar estados e transições de máquinas de estados finitos com restrições de características (FFSM, sigla do inglês). Usando 105 modelos derivados de seis linhas de produto acadêmicas, mostra-se que o algoritmo proposto consegue combinar famílias de máquinas de estados em FFSMs significativamente sucintas, especialmente quando há um alto reúso entre os produtos analisados. (iii) Um conjunto de experiências que incorporam amostragem de produtos no FFSMDiff . Os resultados indicam que modelos de FFSM construídos usando amostragem podem ser tão precisos quanto aqueles feitos usando aprendizado exaustivo e, consequentemente, cobrem o comportamento de uma linha de produto.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2020-09-02
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2021. Todos os direitos reservados.