O TESTE baseado em modelos visa a possibilitar a derivação de conjuntos de casos de teste a partir de especificações formais, tais como Máquinas de Estados Finitos. Os conjuntos de teste podem ser obtidos tanto pelos métodos clássicos de geração quanto por alguma abordagem ad hoc. Procura-se obter um conjunto de teste que consiga detectar todos os possíveis defeitos de uma implementação e possua tamanho reduzido para que a sua aplicação seja factível. Por questões de ordem prática, pode não ser possível a aplicação de todo o conjunto de teste gerado. Desse modo, um subconjunto de casos de teste deve ser selecionado, ou seja, uma minimização do conjunto de teste deve ser realizada. No entanto, é fundamental que a minimização reduza o custo de aplicação dos testes, mas mantenha a efetividade em revelar defeitos. Neste trabalho, propõe-se um algoritmo de minimização de conjuntos de teste para Máquinas de Estados Finitos. O algoritmo baseia-se em condições de suficiência para que a completude em relação à detecção de defeitos seja mantida. O algoritmo foi utilizado em dois diferentes contextos. Utilizou-se o algoritmo com conjuntos de teste gerados de forma aleatória para verificar a minimização obtida. O algoritmo também foi utilizado para reduzir o esforço em se obter um conjunto completo em relação à detecção de defeitos / THE Model-based testing aims at generating test suites from formal specifications, such as Finite State Machines. Test suites can be obtained either from classical test derivation methods or from some ad-hoc approach. It is desirable to produce a test suite which detects all possible faults of an implementation and has small size, so that its application can be feasible. For practical reasons, the application of the generated test suite may not be possible. Therefore, a subset of test cases should be selected, i.e., a test suite minimization should be performed. However, it is important that the minimization reduces the test application cost, but keeps the effectiveness in revealing faults. In this work, an algorithm is proposed for the minimization of test suites generated from Finite State Machines. The algorithm is based on sufficient conditions, so that test suite completeness can be maintained. The algorithm was used in two different contexts. It was used with randomly generated test suites to verify the minimization obtained. The algorithm was also used to reduce the effort of obtaining a test suite with full fault coverage

O teste baseado em modelos visa à derivação de casos de teste a partir de modelos produzidos ao longo do desenvolvimento de software. Nesse contexto, as Máquinas de Estados Finitos têm sido amplamente pesquisadas e utilizadas para derivação de seqüências de teste. Para isso, vários métodos de geração de seqüências de teste têm sido desenvolvidos há várias décadas. O objetivo desses métodos é a obtenção de um conjunto de teste que seja capaz de revelar os defeitos de uma implementação. Entretanto, muitas vezes os conjuntos gerados são muito grandes, o que torna sua aplicação inviável. Trabalhos recentes definiram condições que podem ser utilizadas para investigar mecanismos de redução de casos de teste. Este trabalho apresenta uma estratégia para a redução de conjuntos de seqüências de teste a partir de Máquinas de Estados Finitos com base em condições de suficiência. A estratégia baseia-se na combinação de seqüências de um conjunto de teste, de forma a reduzir o número de seqüências e o tamanho delas, mantendo a completude do conjunto. São apresentadas seis abordagens de redução baseadas na estratégia proposta, as quais foram implementadas em uma ferramenta. Para avaliar as abordagens foram conduzidos estudos experimentais, os quais também serviram para inferir sobre as características e propriedades de cada abordagem. Além disso, um estudo de caso com MEFs reais também foi realizado / Model-based testing aims at generating test cases from models produced along the software development process. In this context, Finite State Machines (FSM) have been largely investigated and used for generating test sequences. In the past decades, several test generation methods have been proposed to obtain test suites that are able to reveal implementation faults. Nevertheless, most of the generated test suites are huge, thus hindering their application in practice. Recent research has defined new sufficient conditions that can be employed in mechanisms for reducing the length of test sequences. This work presents a strategy based on sufficient conditions for reducing the length of test cases derived from FSMs. Our strategy is based on sequence combination of a test suite, aiming to reduce the number of sequences and their length, however still keeping full fault coverage. Six reduction approaches are presented based on the proposed strategy and implemented in a tool. In order to evaluate the strategy, we conducted experimental studies that identified characteristics and properties for each of the six proposed approaches. Moreover, a case study with real-world FSMs was performed

Máquinas de Estados Finitos, além de suas inúmeras aplicações, são amplamente utilizadas na Engenharia de Software para modelar especificações de sistemas. Nesses modelos, projetistas podem inserir, inadvertidamente, estados redundantes, ou seja, que exibem o mesmo comportamento. A eliminação desses estados traz diversos benefícios para as atividades que utilizam o modelo, como menor complexidade e menos recursos físicos para implementação. O processo de eliminação desses estados é denominado minimização, e pode ser realizado em tempo polinomial para máquinas completamente especificadas. Por outro lado, a minimização de máquinas parciais, cuja especificação não cobre todo o domínio de entrada, somente pode ser obtida em tempo polinomial com o uso de abordagens não determinísticas, ou seja, trata-se de um problema NP-Completo. Este trabalho apresenta uma estratégia para a minimização de máquinas de estados finitos parciais que faz o uso de heurísticas e otimizações para tornar o processo mais eficiente. Visando mensurar tal ganho de eficiência, foram realizados experimentos, nos quais os tempos de execução de uma implementação do método proposto foram medidos, juntamente com os tempos de implementações de dois outros métodos conhecidos. Os resultados mostraram vantagens significativas de performance para o novo método em relação aos métodos anteriores / Finite State Machines are largely used on Software Engineering to model systems specifications. In these models, designers may inadvertently include redundant states, i.e., states which exhibit the same input/output behavior. The absence of such states brings benefits to the modeling activities, reducing the complexity and taking less physical resources on implementations. The process of eliminating redundant states is known as minimization, and can be accomplished in polynomial time for completely specified machines. On the other hand, the minimization of partially specified machines, i.e., machines which have undefined behavior for some inputs, can only be done in polynomial time when non-deterministic approaches are applied. It is a known NP-Complete problem. This work presents a deterministic approach to minimize incompletely specified Finite State Machines, using heuristics and optimizations to accomplish the task more efficiently. In order to measure the performance improvements, experiments were done, observing the running time of an implementation of the proposed method, along with running times of implementations of two other known methods. The results revealed a significant performance advantage when using the proposed approach

O TESTE baseado em modelos visa a possibilitar a derivação de conjuntos de casos de teste a partir de especificações formais, tais como Máquinas de Estados Finitos. Os conjuntos de teste podem ser obtidos tanto pelos métodos clássicos de geração quanto por alguma abordagem ad hoc. Procura-se obter um conjunto de teste que consiga detectar todos os possíveis defeitos de uma implementação e possua tamanho reduzido para que a sua aplicação seja factível. Por questões de ordem prática, pode não ser possível a aplicação de todo o conjunto de teste gerado. Desse modo, um subconjunto de casos de teste deve ser selecionado, ou seja, uma minimização do conjunto de teste deve ser realizada. No entanto, é fundamental que a minimização reduza o custo de aplicação dos testes, mas mantenha a efetividade em revelar defeitos. Neste trabalho, propõe-se um algoritmo de minimização de conjuntos de teste para Máquinas de Estados Finitos. O algoritmo baseia-se em condições de suficiência para que a completude em relação à detecção de defeitos seja mantida. O algoritmo foi utilizado em dois diferentes contextos. Utilizou-se o algoritmo com conjuntos de teste gerados de forma aleatória para verificar a minimização obtida. O algoritmo também foi utilizado para reduzir o esforço em se obter um conjunto completo em relação à detecção de defeitos / THE Model-based testing aims at generating test suites from formal specifications, such as Finite State Machines. Test suites can be obtained either from classical test derivation methods or from some ad-hoc approach. It is desirable to produce a test suite which detects all possible faults of an implementation and has small size, so that its application can be feasible. For practical reasons, the application of the generated test suite may not be possible. Therefore, a subset of test cases should be selected, i.e., a test suite minimization should be performed. However, it is important that the minimization reduces the test application cost, but keeps the effectiveness in revealing faults. In this work, an algorithm is proposed for the minimization of test suites generated from Finite State Machines. The algorithm is based on sufficient conditions, so that test suite completeness can be maintained. The algorithm was used in two different contexts. It was used with randomly generated test suites to verify the minimization obtained. The algorithm was also used to reduce the effort of obtaining a test suite with full fault coverage

Máquinas de Estados Finitos, além de suas inúmeras aplicações, são amplamente utilizadas na Engenharia de Software para modelar especificações de sistemas. Nesses modelos, projetistas podem inserir, inadvertidamente, estados redundantes, ou seja, que exibem o mesmo comportamento. A eliminação desses estados traz diversos benefícios para as atividades que utilizam o modelo, como menor complexidade e menos recursos físicos para implementação. O processo de eliminação desses estados é denominado minimização, e pode ser realizado em tempo polinomial para máquinas completamente especificadas. Por outro lado, a minimização de máquinas parciais, cuja especificação não cobre todo o domínio de entrada, somente pode ser obtida em tempo polinomial com o uso de abordagens não determinísticas, ou seja, trata-se de um problema NP-Completo. Este trabalho apresenta uma estratégia para a minimização de máquinas de estados finitos parciais que faz o uso de heurísticas e otimizações para tornar o processo mais eficiente. Visando mensurar tal ganho de eficiência, foram realizados experimentos, nos quais os tempos de execução de uma implementação do método proposto foram medidos, juntamente com os tempos de implementações de dois outros métodos conhecidos. Os resultados mostraram vantagens significativas de performance para o novo método em relação aos métodos anteriores / Finite State Machines are largely used on Software Engineering to model systems specifications. In these models, designers may inadvertently include redundant states, i.e., states which exhibit the same input/output behavior. The absence of such states brings benefits to the modeling activities, reducing the complexity and taking less physical resources on implementations. The process of eliminating redundant states is known as minimization, and can be accomplished in polynomial time for completely specified machines. On the other hand, the minimization of partially specified machines, i.e., machines which have undefined behavior for some inputs, can only be done in polynomial time when non-deterministic approaches are applied. It is a known NP-Complete problem. This work presents a deterministic approach to minimize incompletely specified Finite State Machines, using heuristics and optimizations to accomplish the task more efficiently. In order to measure the performance improvements, experiments were done, observing the running time of an implementation of the proposed method, along with running times of implementations of two other known methods. The results revealed a significant performance advantage when using the proposed approach

O teste baseado em modelos visa à derivação de casos de teste a partir de modelos produzidos ao longo do desenvolvimento de software. Nesse contexto, as Máquinas de Estados Finitos têm sido amplamente pesquisadas e utilizadas para derivação de seqüências de teste. Para isso, vários métodos de geração de seqüências de teste têm sido desenvolvidos há várias décadas. O objetivo desses métodos é a obtenção de um conjunto de teste que seja capaz de revelar os defeitos de uma implementação. Entretanto, muitas vezes os conjuntos gerados são muito grandes, o que torna sua aplicação inviável. Trabalhos recentes definiram condições que podem ser utilizadas para investigar mecanismos de redução de casos de teste. Este trabalho apresenta uma estratégia para a redução de conjuntos de seqüências de teste a partir de Máquinas de Estados Finitos com base em condições de suficiência. A estratégia baseia-se na combinação de seqüências de um conjunto de teste, de forma a reduzir o número de seqüências e o tamanho delas, mantendo a completude do conjunto. São apresentadas seis abordagens de redução baseadas na estratégia proposta, as quais foram implementadas em uma ferramenta. Para avaliar as abordagens foram conduzidos estudos experimentais, os quais também serviram para inferir sobre as características e propriedades de cada abordagem. Além disso, um estudo de caso com MEFs reais também foi realizado / Model-based testing aims at generating test cases from models produced along the software development process. In this context, Finite State Machines (FSM) have been largely investigated and used for generating test sequences. In the past decades, several test generation methods have been proposed to obtain test suites that are able to reveal implementation faults. Nevertheless, most of the generated test suites are huge, thus hindering their application in practice. Recent research has defined new sufficient conditions that can be employed in mechanisms for reducing the length of test sequences. This work presents a strategy based on sufficient conditions for reducing the length of test cases derived from FSMs. Our strategy is based on sequence combination of a test suite, aiming to reduce the number of sequences and their length, however still keeping full fault coverage. Six reduction approaches are presented based on the proposed strategy and implemented in a tool. In order to evaluate the strategy, we conducted experimental studies that identified characteristics and properties for each of the six proposed approaches. Moreover, a case study with real-world FSMs was performed

Access Control (AC) is a major pillar in software security. In short, AC ensures that only intended users can access resources and only the required access to accomplish some task will be given. In this context, Role Based Access Control (RBAC) has been established as one of the most important paradigms of access control. In an organization, users receive responsibilities and privileges through roles and, in AC systems implementing RBAC, permissions are granted through roles assigned to users. Despite the apparent simplicity, mistakes can occur during the development of RBAC systems and lead to faults or either security breaches. Therefore, a careful verification and validation process becomes necessary. Access control testing aims at showing divergences between the actual and the intended behavior of access control mechanisms. Model Based Testing (MBT) is a variant of testing that relies on explicit models, such as Finite State Machines (FSM), for automatizing test generation. MBT has been successfully used for testing functional requirements; however, there is still lacking investigations on testing non-functional requirements, such as access control, specially in test criteria. In this Master Dissertation, two aspects of MBT of RBAC were investigated: FSM-based testing methods on RBAC; and Test prioritization in the domain of RBAC. At first, one recent (SPY) and two traditional (W and HSI) FSM-based testing methods were compared on RBAC policies specified as FSM models. The characteristics (number of resets, average test case length and test suite length) and the effectiveness of test suites generated from the W, HSI and SPY methods to five different RBAC policies were analyzed at an experiment. Later, three test prioritization methods were compared using the test suites generated in the previous investigation. A prioritization criteria based on RBAC similarity was introduced and compared to random prioritization and simple similarity. The obtained results pointed out that the SPY method outperformed W and HSI methods on RBAC domain. The RBAC similarity also achieved an Average Percentage Faults Detected (APFD) higher than the other approaches. / Controle de Acesso (CA) é um dos principais pilares da segurança da informação. Em resumo, CA permite assegurar que somente usuários habilitados terão acesso aos recursos de um sistema, e somente o acesso necessário para a realização de uma dada tarefa será disponibilizado. Neste contexto, o controle de acesso baseado em papel (do inglês, Role Based Access Control - RBAC) tem se estabelecido como um dos mais importante paradigmas de controle de acesso. Em uma organização, usuários recebem responsabilidades por meio de cargos e papéis que eles exercem e, em sistemas RBAC, permissões são distribuídas por meio de papéis atribuídos aos usuários. Apesar da aparente simplicidade, enganos podem ocorrer no desenvolvimento de sistemas RBAC e gerar falhas ou até mesmo brechas de segurança. Dessa forma, processos de verificação e validação tornam-se necessários. Teste de CA visa identificar divergências entre a especificação e o comportamento apresentado por um mecanismo de CA. Teste Baseado em Modelos (TBM) é uma variante de teste de software que se baseia em modelos explícitos de especificação para automatizar a geração de casos testes. TBM tem sido aplicado com sucesso no teste funcional, entretanto, ainda existem lacunas de pesquisa no TBM de requisitos não funcionais, tais como controle de acesso, especialmente de critérios de teste. Nesta dissertação de mestrado, dois aspectos do TBM de RBAC são investigados: métodos de geração de teste baseados em Máquinas de Estados Finitos (MEF) para RBAC; e priorização de testes para RBAC. Inicialmente, dois métodos tradicionais de geração de teste, W e HSI, foram comparados ao método de teste mais recente, SPY, em um experimento usando políticas RBAC especificadas como MEFs. As características (número de resets, comprimento médio dos casos de teste e comprimento do conjunto de teste) e a efetividade dos conjuntos de teste gerados por cada método para cinco políticas RBAC foram analisadas. Posteriormente, três métodos de priorização de testes foram comparados usando os conjuntos de teste gerados no experimento anterior. Neste caso, um critério baseado em similaridade RBAC foi proposto e comparado com a priorização aleatória e baseada em similaridade simples. Os resultados obtidos mostraram que o método SPY conseguiu superar os métodos W e HSI no teste de sistemas RBAC. A similaridade RBAC também alcançou uma detecção de defeitos superior.

A realização de atividades de teste é indispensável para a garantia da qualidade de um produto e para a identificação de defeitos, diminuindo custos de manutenção e evitando ao máximo o risco do cliente encontrar esses defeitos. Nessa linha, testes baseados em modelos têm se mostrado atrativos, pois o custo de geração de casos de testes e de correção de defeitos tende a ser menor. Devido à sua simplicidade conceitual e expressividade na descrição do comportamento de um sistema, um dos modelos mais usados e pesquisados na área de teste baseado em modelos são as Máquinas de Estados Finitos (MEFs). Por meio de MEFs e com apoio de ferramentas apropriadas, a geração de casos de testes para avaliar os comportamentos esperados de um sistema é automatizada, reduzindo tanto o custo da geração e da manutenção quanto as falhas humanas. Desta forma, a aplicabilidade de métodos de geração de casos de teste baseados em modelos no contexto de sistemas embarcados vem sendo investigada. O objetivo deste trabalho de mestrado consiste em investigar a aplicabilidade dos métodos de geração em cenários de teste reais, com foco em sistemas embarcados, identificando as difi- culdades e limitações do processo, bem como os requisitos essenciais para a adequação dos métodos de geração propostos na literatura e de ferramentas de apoio à atividade de teste. O foco principal do projeto é a implementação de mecanismos que atendam aos requisitos levantados, visando a usabilidade, segurança e portabilidade da ferramenta / Test activities are essential to ensure the quality of products and identify faults to reduce maintenance costs and avoid that the client finds these faults. In this sense, model-based tests have been proved useful, because the cost of generating test cases and fault correction tend to be smaller. Due to its conceptual simplicity and expressiveness in describing the behavior of a system, Finite State Machines (FSM) have been used and researched in the model-based testing area. FSMs, employed with the support of appropriate tools, enable the generation of test cases in an automated way to assess the expected behavior of a system, reducing both the generation and maintenance costs and human failures. Thus, the applicability of test cases generation methods based on models in the context of embedded systems should be investigated. Test cases generation methods based on FSM are designed to derive test cases from the model. In this context, this work aims to investigate the applicability of generation methods in real-world scenarios, focusing embedded systems. It should identify the difficulties and limitations of the process, as well as the essential requirements for the adequacy of generation methods proposed in the literature and tools to support the test activity. The main focus of the project is the implementation of mechanisms that meet the elicited requirements in order to provide usability, security and tool portability

Os sistemas produtivos (SPs) podem utilizar controladores programáveis (CPs) como dispositivos de realização do controle. Neste contexto, programas de controle executados por estes CPs podem ser desenvolvidos de forma que não estejam em conformidade com as especificações de projeto, o que poderá provocar o surgimento de erros funcionais associados à execução de tais programas de controle, erros estes que podem levar os SPs sob controle a um estado que poderá implicar em acidentes envolvendo equipamentos, pessoas e o meio-ambiente. Esta questão tem motivado o surgimento de diversas abordagens para identificar a existência de erros em programas de controle de CPs, de forma a permitir a correção destes erros e garantir, conseqüentemente, maior confiabilidade operacional. O presente trabalho tem por objetivo identificar a existência de erros em programas de controle baseados em LD (Ladder Diagram). Para isto, propõe-se um procedimento de desenvolvimento de modelos baseados em máquinas de estados finitos estendidas (MEFEs), que são gerados a partir do mapeamento de cada um dos rungs contidos no programa de controle que se deseja identificar erros. Uma vez desenvolvidos os modelos em MEFEs, torna-se possível a utilização de uma ferramenta computacional de verificação, própria para estabelecer se os modelos verificados satisfazem determinadas proposições estabelecidas em lógica temporal. Uma proposição em lógica temporal está relacionada a um estado específico do programa de controle modelado, sendo que o objetivo da verificação é o de estabelecer se a proposição estipulada é atendida ou não. Se um determinado estado específico for, por exemplo, um estado indesejado do programa de controle modelado, e este estado for possível de ser alcançado como resultado do processo de verificação realizado, isto impactará na não conformidade do programa de controle com as especificações comportamentais estipuladas na forma de proposição em lógica temporal, indicando haver, portanto, um erro neste programa de controle modelado. Palavras-chave: Controladores programáveis. Linguagem de programação LD. Modelagem e verificação de máquinas de estados finitos estendidas (MEFEs). / Productive systems (PS) can use programmable logic controllers (PLCs) as the devices of accomplishment of the control. In this context, control programs executed by these PLCs can be developed in a way so that they can be in non-conformity with the project specifications, and this fact may result in functional errors related to the control programs execution. These errors can take the PS under control to a state which can lead into accidents involving equipment, people and the environment. This fact has motivated the appearance of different approaches so as to identify the existence of these errors in PLC control programs so that they can be corrected and assure a greater operational reliability. This work aims at identifying the existence of errors in control programs based on Ladder Diagram (LD). In order to accomplish that, a modeling procedure that generates extended finite state machines (EFSMs) is proposed from the mapping of each one of the rungs in the control program whose errors are to be identified. Once the models based on EFSMs are developed it becomes possible to use a computational verification tool, specifically designed to determine if the verified models fulfill determined propositions established in temporal logic. A proposition in temporal logic is related to a specific state of the modeled control program and the objective of the verification is to establish whether the proposition is fulfilled or not. If a determined specific state, for example, is an unwanted state of the modeled control program and if this state is reachable as a result of the verification process, this will impact in the non-conformity of the control program with the behavior specifications established in a temporal logic proposition, indicating an error in this modeled control program.

A realização de atividades de teste é indispensável para a garantia da qualidade de um produto e para a identificação de defeitos, diminuindo custos de manutenção e evitando ao máximo o risco do cliente encontrar esses defeitos. Nessa linha, testes baseados em modelos têm se mostrado atrativos, pois o custo de geração de casos de testes e de correção de defeitos tende a ser menor. Devido à sua simplicidade conceitual e expressividade na descrição do comportamento de um sistema, um dos modelos mais usados e pesquisados na área de teste baseado em modelos são as Máquinas de Estados Finitos (MEFs). Por meio de MEFs e com apoio de ferramentas apropriadas, a geração de casos de testes para avaliar os comportamentos esperados de um sistema é automatizada, reduzindo tanto o custo da geração e da manutenção quanto as falhas humanas. Desta forma, a aplicabilidade de métodos de geração de casos de teste baseados em modelos no contexto de sistemas embarcados vem sendo investigada. O objetivo deste trabalho de mestrado consiste em investigar a aplicabilidade dos métodos de geração em cenários de teste reais, com foco em sistemas embarcados, identificando as difi- culdades e limitações do processo, bem como os requisitos essenciais para a adequação dos métodos de geração propostos na literatura e de ferramentas de apoio à atividade de teste. O foco principal do projeto é a implementação de mecanismos que atendam aos requisitos levantados, visando a usabilidade, segurança e portabilidade da ferramenta / Test activities are essential to ensure the quality of products and identify faults to reduce maintenance costs and avoid that the client finds these faults. In this sense, model-based tests have been proved useful, because the cost of generating test cases and fault correction tend to be smaller. Due to its conceptual simplicity and expressiveness in describing the behavior of a system, Finite State Machines (FSM) have been used and researched in the model-based testing area. FSMs, employed with the support of appropriate tools, enable the generation of test cases in an automated way to assess the expected behavior of a system, reducing both the generation and maintenance costs and human failures. Thus, the applicability of test cases generation methods based on models in the context of embedded systems should be investigated. Test cases generation methods based on FSM are designed to derive test cases from the model. In this context, this work aims to investigate the applicability of generation methods in real-world scenarios, focusing embedded systems. It should identify the difficulties and limitations of the process, as well as the essential requirements for the adequacy of generation methods proposed in the literature and tools to support the test activity. The main focus of the project is the implementation of mechanisms that meet the elicited requirements in order to provide usability, security and tool portability