Repositório RCAAP

Em 2009, N. Heninger e H. Shacham apresentaram um algoritmo de reconstrução que permite recuperar a chave secreta sk do criptossistema RSA básico em tempo polinomial tendo em forma aleatória 27 % dos seus bits. Sabemos que podemos obter uma versão com erros (bits modicados) da chave secreta RSA graças aos ataques cold boot. O algoritmo apresentado por Heninger-Shacham corrige esses erros fazendo uso das relações matemáticas que existe entre as chaves pública e secreta do criptossistema RSA básico. O objetivo deste trabalho é estudar esse algoritmo para implementar e analisar seu análogo para o criptossistema RSA multi-primo. Os resultados obtidos mostram que para reconstruir a chave secreta sk do criptossistema RSA u-primos é preciso ter uma fração de bits corretos maior a 2 - 2^((u+2)/(2u+1)), mostrando assim que a segurança oferecida pelo criptossistema RSA multi-primo (u>/ 3) é maior com relação ao criptossistema RSA básico (u = 2).

Concerns about reducing energy consumption in the sector of Information and Communication Technology has increasingly motivated the transition of traditional services to the clouds. In this context, Network Functions Virtualization (NFV) emerges as a solution to migrate various network functions, from dedicated hardware devices to a virtual environment based on commodity hardware. With this virtualization, in addition to the promise of increasing energy efficiency, it is expected to reduce the financial cost and increase the flexibility and scalability of the networks. In this research, it is proposed the development of algorithms based on three metaheuristics (Standard Hill-Climbing, Simulated Annealing, and Memetic Algorithm) to schedule network functions in cloud data centers, observing not only the capacities and energy consumption of the computers where the functions will be executed but also of the network and switches that connect these computers. Comparing the algorithms proposed in relation to the Best Fit algorithm found in the literature, the one based on Simulated Annealing saved 55.44% of energy consumption in a datacenter with Three-tier topology and the one based on memetic algorithm saved 49.18% of energy consumption in a data center with Fat-Tree topology. To allow the reproduction of all the experiments carried out in this research, the codes developed are publicly available as free software

Exploramos o seguinte problema: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y sem símbolos repetidos. Estudamos a estrutura deste problema, particularmente do ponto de vista de grafos e de combinatória poliédrica. Desenvolvemos algoritmos de aproximação e heurísticas para este problema. O enfoque deste trabalho está na construção de um algoritmo baseado na técnica branch-and-cut, aproveitando-nos de um algoritmo de separação eficiente e de heurísticas e técnicas para encontrarmos uma solução ótima mais cedo. Também estudamos um problema mais fácil no qual este problema é baseado: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y. Exploramos este problema do ponto de vista de combinatória poliédrica e descrevemos vários algoritmos conhecidos para resolvê-lo.

Two tasks that software engineers constantly perform are writing code that is easy to evolve and maintain, and detecting poorly written pieces of code. For the former, software engineers commonly rely on well-known software architecture styles, such as Model-View-Controller (MVC). To the latter, they rely on code metrics and code smell detection approaches. However, up to now, these code metrics and code smell approaches do not take into account underlying architectureall classes are assessed as if they were the same. In practice, software developers know that classes differ in terms of responsibilities and implementation, and thus, we expect these classes to present different levels of coupling, cohesion, and complexity. As an example, in an MVC system, Controllers are responsible for the flow between the Model and the View, and Models are responsible for representing the systems business concepts. Thus, in this thesis, we evaluate the impact of architectural roles within a system architecture on code metrics and code smells. We performed an empirical analysis in 120 open source systems, and interviewed and surveyed more than 50 software developers. Our findings show that each architectural role has a different code metric values distribution, which is a likely consequence of their specific responsibilities. Thus, we propose SATT, an approach that provides specific thresholds for architectural roles that are significantly different from others in terms of code smells. We also show that classes that play a specific architectural role contain specific code smells, which developers perceive as problems, and can impact class\' change- and defect-proneness. Based on our findings, we suggest that developers understand the responsibilities of each architectural role in their system architecture, so that code metrics and code smells techniques can provide more accurate feedback.

Composição de serviços é um tópico que tem atraído cada vez mais o interesse por parte de pesquisadores na área de sistemas distribuídos. Além disso, o interesse por ambientes baseados em nuvem tem crescido significativamente conforme o seu uso aumenta e se firma como um importante modelo de negócios. Coreografias são formas de composições de serviços em que não há pontos centrais de falha; a responsabilidade da sua execução é distribuída entre os vários serviços componentes. Devido à natureza distribuída do fluxo de informações e dados de controle, o cumprimento de \\textit{Service Level Agreements} (SLAs) depende estritamente do monitoramento da Qualidade de Serviços (QoS), recursos virtuais da nuvem e mecanismos de reconfiguração dinâmica, capazes de automaticamente adaptar composições a mudanças de estado no sistema. Nesta dissertação, abordamos o estudo do gerenciamento de QoS em coreografias de serviços. Para isso desenvolvemos um sistema de middleware capaz de implantar e gerenciar o QoS de composições. Este teve seu desempenho avaliado utilizando o serviço Amazon EC2. Os resultados da avaliação mostram que com pouco esforço por parte dos desenvolvedores de composições, é possível cumprir o SLA de composições dentro do esperado utilizando escalabilidade horizontal ou vertical provida pelo middleware automaticamente. Adicionalmente, a nossa proposta traz economias em relação ao custo de implantação pois diminui a quantidade de recursos subutilizados.

The motivation that originated this work was the desire to create an invasion team sports simulator capable of applying user defined strategies to guide the behavior of the agents in the simulation. With this objective in mind we created a formal strategy model to describe complex team behavior and developed methods of using that model to calculate collective plans. We defined both the strategy model and the planning methods in a broad manner that can be applied in many different domains. Then we defined a basketball simulation domain and implemented our methodology to develop a simulator. We also present a control system architecture that is compatible with our proposed planner and show how we implemented it to create the basketball simulator. The formal strategy model we developed can be used to represent team behavior, analyze real world events and create simulations. We developed a strategy design tool that allows the end user to create and visualize team strategies for basketball. Finally, we developed a system that interprets the user generated strategies and creates a basketball match simulation of the described behavior. We also proposed a methodology for the development of simulation systems involving multiple intelligent agents. Our recommended control system architecture separates the many layers of control, which simplifies the development process and results in a naturally expansible system. In this thesis we have provided a novel approach to collective behavior simulation utilizing user input as a guide to the strategy planning. Both the theory and methods developed have been tested through the implementation of a basketball simulator and the results were satisfactory. We believe this is a seminal work that will lead to many interesting developments, both in the realm of sports and in broader domains.

As organizações precisam trocar informações de forma simples e eficiente, com custos tão baixos quanto possível. Essas informações às vezes são apresentadas na forma de documentos com formato e conteúdos pré-definidos. Esses documentos podem ser equivalentes ou quase equivalentes, porém bastantes distintos em diferentes organizações. Numa mesma organização, os documentos podem ser diferentes em contextos históricos. O propósito deste trabalho é facilitar a distribuição dos documentos, superando o problema dos formatos com os quais foram criados. O objetivo é possibilitar a interoperabilidade de documentos e atingir a portabilidade simples e confiável de documentos através da reutilização de formatos e conteúdos, em diferentes combinações plausíveis. Propomos, usar ontologias como solução ao problema da falta de interoperabilidade nas implementações de formatos de documentos. Como prova de conceito consideramos a portabilidade entre os formatos padrão ODF(Open Document Format) e (Office Open XML).

Neste trabalho apresentamos um modelo para ambientes inteligentes baseado em organizações de agentes, onde interações entre entidades são associadas a espaços físicos, pessoas carregam dispositivos e se movimentam entre diferentes espaços físicos e cada espaço físico contém definições de interações (comportamentos definidos por normas) próprias do seu contexto. São definidos três componentes deste modelo: (1) modelo conceitual, (2) linguagem de especificação e (3) ambiente de execução. A separação do modelo nestes três componentes traz como principais conseqüências: (1) a ativação de um ambiente inteligente é feita através de um mecanismo de alto nível, (2) a especificação de um ambiente inteligente é independente do domínio de aplicação e (3) as especificações podem ser executadas em mecanismos diferentes de execução.

O problema de caminhos mínimos (SP shortest path problem) é frequentemente colo- cado em prática em uma grande variedade de aplicações em diversas áreas. Nessas aplicações geralmente se deseja realizar algum tipo de deslocamento ou transporte entre dois ou mais pontos específicos em uma rede. Tal ação deve ser executada de forma ótima em relação a algum critério, por exemplo o menor custo possível, ou o menor gasto de tempo ou o máximo de confiabilidade/segurança. Na prática, muitas vezes não desejamos apenas o menor custo ou o menor tempo, mas desejamos otimizar uma combinação de diferentes critérios, por exemplo, um caminho que seja rápido e barato. Como não é possível otimizar sobre todos os critérios de uma só vez, nós escolhemos um dos critérios para representar a função custo, que será minimizada, e para os demais critérios representamos como recursos e definimos os limites que julgamos aceitáveis para o consumo de cada um desses recursos. Esta variação é cha- mada de problema de caminhos mínimos com restrições por recursos, ou como preferimos chamar, problema de caminhos mínimos com recursos limitados (RCSP resource constrained shortest path problem), o qual será o objeto de estudo neste trabalho. A adição de restrições por recursos no SP, infelizmente torna o problema NP-difícil, mesmo em grafos acíclicos, com restrições sobre um único recurso, e com todos os consu- mos de recursos positivos. Temos reduções dos famosos problemas N P-difíceis Mochila e Partição para o nosso problema. Em contextos diversos são encontrados problemas de cunho teórico e prático que po- dem ser formulados como problemas de caminhos mínimos com recursos limitados, o que nos motivou a estudá-lo a fim de desenvolver um trabalho que resumisse informações sufi- cientes para auxiliar pesquisadores ou desenvolvedores que tenham interesse no problema. Nós apresentamos aqui, uma detalhada revisão bibliográfica do RCSP, tendo como foco o desenvolvimento de algoritmos exatos para o caso onde possuímos um único recurso e a im- plementação e comparação dos principais algoritmos conhecidos, observando-os em situações práticas.

O reconhecimento de texto manuscrito continua sendo um problema em aberto, objeto de intensa pesquisa na área de aprendizado de máquina. Neste projeto focamos numa categoria específica de problema nesta área, a leitura automática de planilhas de xadrez. Planilhas de xadrez contém anotações de lances de jogos escritos à mão pelos próprios jogadores num formato chamado de notação algébrica. Em comparação com um texto tradicional em linguagem natural, planilhas de xadrez são formulários de formato fixo, seu conteúdo textual é restrito a um vocabulário reduzido e a escrita em geral não é totalmente cursiva. Mesmo assim, elas ainda apresentam uma alta variabilidade de estilos de escrita à mão, tornando a sua leitura um problema suficientemente complexo. O objetivo deste trabalho é o treinamento ponta a ponta de uma rede neural para a leitura destas planilhas, em cenários com uma quantidade limitada de dados. A rede neural deverá receber a imagem de uma planilha e produzir em sua saída a sequência de lances que estão escritos na planilha. Além do reconhecimento da escrita propriamente, a rede deverá aprender a ordem correta de leitura. Por se tratar de um problema para o qual não encontramos trabalhos na literatura da área, o método utilizado consistiu na criação de um conjunto de dados e uma ampla investigação experimental utilizando uma rede neural recorrente com mecanismo de atenção. Identificamos três subtarefas subjacentes ao problema: (1) o aprendizado do modelo de linguagem, relacionado com a previsibilidade dos lances, (2) o alinhamento entre a entrada e a saída, e (3) o reconhecimento da escrita propriamente. Constatamos que essas tarefas possuem distintos graus de dificuldade e que existem alguns fatores que são críticos no aprendizado delas. Mais do que isso, constatamos também que uma combinação adequada desses fatores é fundamental para um treinamento ponta a ponta bem sucedido. Um modelo básico foi avaliado quanto ao reconhecimento dos 16 primeiros lances e alcançou acurácia de 65,78% em termos de lances corretamente reconhecidos.

JamSession foi proposto como uma plataforma para mediar e coordenar, por meio de protocolos de interação baseados em conhecimento, recursos computacionais existentes com o objetivo de compor novos serviços e desenvolver aplicações inovadoras. Entre as principais características da plataforma estão sua base formal e declarativa para permitir análise e verificação formal dos protocolos, alta performance e foco na usabilidade. A plataforma pode ser utilizada, por exemplo, na construção de ambientes inteligentes e no aprimoramento dos serviços de governo eletrônico, onde o JamSession pode atuar mediando a interação entre sistemas oferecidos por órgãos públicos visando a ampliação dos serviços oferecidos. O objetivo deste trabalho é o desenvolvimento da plataforma JamSession e sua aplicação em problemas concretos de integração e coordenação. Entre as aplicações consideradas para validar a plataforma desenvolvida estão a integração de workflows interorganizacionais e a demonstração do uso da plataforma na construção de ambientes virtuais interativos.

Esta dissertação tem por objetivo apresentar as licenças de software livre mais importantes, sob a luz dos seus principais aspectos jurídicos e da inter-compatibilidade, de forma a auxiliar pessoas envolvidas no desenvolvimento de software a compreender as implicações destas licenças ao fazer uso delas em seus projetos. A dissertação contextualiza as licenças, tanto no tocante à legislação brasileira, quanto no que diz respeito às restrições de licenciamento, de forma a viabilizar a análise de compatibilidade que se segue. Casos de projetos proeminentes de software livre cujo desenvolvimento foi afetado pelas implicações mencionadas ilustram a investigação, que é complementada por uma análise de ferramentas e metodologias existentes que auxiliam na gestão dos aspectos de licenciamento.

Sistemas criptográficos como o RSA e o Diffie-Hellman sobre Curvas Elípticas (DHCE) têm fundamento em problemas computacionais considerados difíceis, por exemplo, o problema do logaritmo (PLD) e o problema da fatoração de inteiros (PFI). Diversos trabalhos têm relacionado a segurança desses sistemas com os problemas subjacentes. Também é investigada a segurança do LSB (bit menos significativo) da chave secreta no DHCE (no RSA é o LSB da mensagem) com relação à segurança de toda a chave. Nesses trabalhos são apresentados algoritmos que conseguem inverter os sistemas criptográficos citados fazendo uso de oráculos que predizem o LSB. Nesta dissertação, fazemos a implementação de dois desses algoritmos. Identificamos parâmetros críticos e mudamos a amostragem do formato original. Com essa mudança na amostragem conseguimos uma melhora significativa nos tempos de execução. Um dos algoritmos (ACGS), para valores práticos do RSA, era mais lento que a solução para o PFI, com nosso resultado passou a ser mais veloz. Ainda, mostramos como provas teóricas podem não definir de maneira precisa o tempo de execução de um algoritmo.

Processos de Decisão Markovianos (Markov Decision Process - MDP) modelam problemas de tomada de decisão sequencial em que as possíveis ações de um agente possuem efeitos probabilísticos sobre os estados sucessores (que podem ser definidas por matrizes de transição de estados). Programação dinâmica em tempo real (Real-time dynamic programming - RTDP), é uma técnica usada para resolver MDPs quando existe informação sobre o estado inicial. Abordagens tradicionais apresentam melhor desempenho em problemas com matrizes esparsas de transição de estados porque podem alcançar eficientemente a convergência para a política ótima, sem ter que visitar todos os estados. Porém essa vantagem pode ser perdida em problemas com matrizes densas de transição, nos quais muitos estados podem ser alcançados em um passo (por exemplo, problemas de controle com eventos exógenos). Uma abordagem para superar essa limitação é explorar regularidades existentes na dinâmica do domínio através de uma representação fatorada, isto é, uma representação baseada em variáveis de estado. Nesse trabalho de mestrado, propomos um novo algoritmo chamado de FactRTDP (RTDP Fatorado), e sua versão aproximada aFactRTDP (RTDP Fatorado e Aproximado), que é a primeira versão eficiente fatorada do algoritmo clássico RTDP. Também propomos outras 2 extensões desses algoritmos, o FactLRTDP e aFactLRTDP, que rotulam estados cuja função valor convergiu para o ótimo. Os resultados experimentais mostram que estes novos algoritmos convergem mais rapidamente quando executados em domínios com matrizes de transição densa e tem bom comportamento online em domínios com matrizes de transição densa com pouca dependência entre as variáveis de estado.

Tratamos da generalização do problema da geração de caminho mínimo, no qual não apenas um, mas vários caminhos de menores custos devem ser produzidos. O problema dos k-menores caminhos consiste em listar os k caminhos de menores custos conectando um par de vértices. Esta dissertação trata de algoritmos para geração de k-menores caminhos em grafos simétricos com custos não-negativos, bem como algumas implementações destes.

Aprender a programar é uma tarefa árdua. Muitos erros são cometidos durante o desenvolvimento de código e aprender com esses erros pode ajudar a evitá-los. Apesar da quantidade considerável de pesquisas sobre esse tema, os professores têm pouco suporte para entender as dificuldades dos alunos. Perante esse cenário, o principal objetivo desta tese é identificar padrões de dificuldades enfrentadas pelos alunos durante o aprendizado de programação. Para realização da pesquisa, trabalhamos com dados de estudantes e professores de disciplinas de introdução à programação de cursos de graduação da USP. A pesquisa foi elaborada em três fases: primeiramente, analisamos dados para avaliar as taxas de insucesso do ensino introdutório de programação na universidade; em seguida, verificamos com alunos, através de diários de estudos, e professores, através de entrevistas semiestruturadas, o que eles entendem como sendo os problemas no ensino e aprendizagem de programação; e, por último, buscamos nos códigos de exercícios desenvolvidos por alunos durante seus cursos evidências sobre as dificuldades encontradas. Com essa última fase, catalogamos os resultados e os validamos através de um questionário com professores brasileiros com experiência no ensino desse conteúdo. Os dados coletados foram examinados utilizando-se de análise quanti e qualitativa. A análise de ~19.500 matrículas, nos possibilitou verificar que ~30% dos alunos matriculados em disciplinas de introdução à programação, no período analisado, não foram aprovados, ou seja, ~1.100 alunos por ano. Possibilitou ainda que fossem criadas listas das dificuldades citadas nos diários e entrevistas. Essas listas foram organizadas por conteúdo e por linguagem de programação (C e Python). Além disso, percebemos nesses dados ligações entre os conteúdos e, com isso, criamos um conjunto de conexões entre tópicos, mostrando a existência de pré-requisitos entre eles. Depois, analisando a evolução no desenvolvimento dos códigos dos estudantes, tivemos a oportunidade de identificar 139 tipos de equívocos cometidos utilizando-se as linguagens C e Python. Os equívocos que eram recorrentes foram considerados antipadrões (soluções comuns, porém com consequências negativas) e agrupados em catálogos. No total, foram criados 3 catálogos: um com antipadrões encontrados nos códigos desenvolvidos em C (21 equívocos), outro em Python (11 equívocos) e o último com a intersecção dos dois, totalizando 9 antipadrões encontrados tanto em C como em Python. Os antipadrões e os catálogos foram avaliados através de uma pesquisa de questionário respondida por 43 professores. Em geral, os professores conheciam os antipadrões apresentados. Além do mais, eles consideraram os catálogos fáceis para usar (~76%) e úteis (~81%); 53% mostraram ter intenção de usá-los regularmente nas suas aulas. Esperamos que os materiais gerados nesta tese possam ajudar professores no planejamento de suas aulas e pesquisadores a desenvolverem novas ferramentas e darem novos passos rumo ao aprimoramento do ensino e aprendizagem de programação.

Este trabalho trata do problema da construção de atributos para classificação quando atributos e rótulos são binários. A abordagem adotada visa reduzir efeitos de interação entre atributos, amenizando a necessidade dos classificadores lidarem com essas interações. Para tanto, é introduzida uma nova técnica que usa uma matriz de cálculo de paridade para transformar as coordenadas do vetor de atributos binários. Tal matriz permite a manipulação de diversas medidas derivadas da teoria da informação. A transformação resultante induz a formação de grupos de variáveis binárias. Baseando-se nessa técnica, um algoritmo inédito de análise de componentes independentes de variáveis binárias é apresentado, assim como um algoritmo que induz a independência condicional entre os atributos (dado o valor do rótulo). Um terceiro algoritmo apresentado reduz a Informação de Interação entre os atributos, uma medida associada ao grau de redundância ou colaboração entre atributos. Tal algoritmo é empregado no problema do projeto de operadores em dois níveis para imagens, em que múltiplos operadores são combinados para a obtenção de uma imagem final. Nesse caso, o algoritmo apresentado guia a estratégia de divisão de uma imagem em sub-regiões. É apresentado um arcabouço para o projeto de operadores de imagens em dois níveis, incorporando métodos de seleção de atributos e comparação de modelos. Os resultados mostram que o método proposto propicia melhor desempenho, em comparação com operadores de nível único.

Esta dissertação apresenta um estudo comparativo de diferentes métodos computacionais de segmentação estrutural musical, onde o principal objetivo é delimitar fronteiras de seções musicais em um sinal de áudio, e rotulá-las, i.e. agrupar as seções encontradas que correspondem a uma mesma parte musical. São apresentadas novas propostas para segmentação estrutural nãosupervisionada, incluindo métodos para processamento em tempo real, alcançando resultados com taxas de erro inferiores a 12%. O método utilizado compreende um estudo dos descritores sonoros e meios de modelá-los temporalmente, uma exposição das técnicas computacionais de segmentação estrutural e novos métodos de avaliação dos resultados que penalizam tanto a incorreta detecção das fronteiras quanto o número incorreto de rótulos encontrados. O desempenho de cada técnica computacional é calculado utilizando diferentes conjuntos de descritores sonoros e os resultados são apresentados e analisados tanto quantitativa quanto qualitativamente.

A área de recuperação de informação baseada em conteúdo visual vem ganhando importância graças ao volume de material visual existente (imagens e vídeo digitais), compartilhado e distribuído principalmente via Internet, e à capacidade de processamento alcançada pelos computadores pessoais na última década. Novas formas de consumo, manipulação e exploração de vídeo digital podem ser criadas através da organização e indexação apropriada desse material. A delimitação de tomadas fornece uma base para a abstração e estruturação de vídeo, agregando quadros contíguos em seqüências de mesmo contexto, isto é, trechos com unidade em termos de tempo e espaço. Nesta dissertação são apresentados os conceitos básicos de delimitação de tomadas e métodos tradicionais utilizados nesse tipo de segmentação, bem como vários resultados experimentais obtidos a partir de seqüências reais de TV. É analisada a distribuição das diferenças entre quadros sucessivos, calculada através de seus histogramas, na tentativa de caracterizar as transições entre tomadas e obter melhores parâmetros para a segmentação. Obtêm-se experimentalmente mais evidências que comprovam a superioridade da medida de intersecção de histogramas sobre outras medidas. A principal contribuição do trabalho consiste no desenvolvimento de um algoritmo baseado no método twin-comparison, que apresenta melhor desempenho que o método original na detecção dos limites de tomadas por utilizar análise local da variação visual entre os quadros do vídeo.

Modelos preditivos de mercado são ferramentas importantes para tomadores de decisões no âmbito público e privado. Devido à complexidade dinâmica do mercado imobiliário, composta pela interação de dois submercados distintos (mercado de ativos imobiliários e mercado de consumo de espaço) e pela limitação de dados disponíveis, o estudo analítico de mercados imobiliários requer a modelagem paramétrica de um sistema de equações que os descrevam, seguido pela identificação dos parâmetros deste sistema utilizando dados reais de uma região. Neste trabalho, estudamos o modelo dinâmico de mercado imobiliário proposto por Wheaton (1999), criado a partir do popular modelo de quatro quadrantes de autoria de DiPasquale e Wheaton (1996). Utilizamos técnicas de identificação de sistemas para elaborar um modelo de aprendizado para o estoque imobiliário, e o implementamos em Matlab. Aplicamos o método elaborado em dados simulados, para validá-lo, e então aplicamos o mesmo método, com adaptações, em dados reais do mercado imobiliário canadense. Os resultados obtidos validam o método de identificação de sistema dinâmico quando testado em dados simulados, e corroboram o modelo de Wheaton (1999) como modelo preditivo em dados reais. Ademais, os resultados indicam que um modelo que seja capaz de entender a evolução dinâmica dos parâmetros estáticos do modelo de Wheaton (1999), poderia melhorar os resultados deste como ferramenta preditiva.