La recherche de points communs entre des descriptions de données ou de connaissances est un problème de raisonnement fondamental en Machine Learning, qui a été formalisé par G. Plotkin dans les années 70s sous la forme du calcul du plus petit généralisant de ces descriptions. L'identification des plus petits généralisants a un large panel d'applications qui vont de l'optimisation de requêtes (e.g., pour matérialiser les points communs entre des requêtes lors de la sélection de vues ou pour factoriser leur exécution dans un contexte d'accès concurrentiel), à la recommandation dans le contexte des réseaux sociaux (e.g. pour créer de liens entre des utilisateurs basées sur leurs points communs selon leur profil ou leurs recherches). Dans cette thèse nous avons revisité la notion du plus petit généralisant dans le contexte de Resource Description Framework (RDF) et le fragment conjonctif de son langage de requêtes associé SPARQL, alias Basic Graph Pattern (BGP) queries. Contrairement à l'état de l'art, nous ne considérons aucune restriction, ni structurelle ni sémantique, sur les graphes et les requêtes. Nos contributions incluent la définition et le calcul des plus petits généralisants dans ces deux formalismes ce qui revient à trouver le plus grand ensemble de points communs entre des bases de données incomplètes et des requêtes conjonctives en présence de contraintes déductives. Nous proposons également une évaluation expérimentale de nos contributions. / Finding commonalities between descriptions of data or knowledge is a fundamental task in Machine Learning. The formal notion characterizing precisely such commonalities is known as least general generalization of descriptions and was introduced by G. Plotkin in the early 70's, in First Order Logic. Identifying least general generalizations has a large scope of database applications ranging from query optimization (e.g., to share commonalities between queries in view selection or multi-query optimization), to recommendation in social networks (e.g., to establish connections between users based on their commonalities between proles or searches), through exploration (e.g., to classify/categorize datasets and to identify common social graph patterns between organizations (e.g., criminal ones)). In this thesis we revisit the notion of least general generalizations in the entire Resource Description Framework (RDF) and popular conjunctive fragment of SPARQL, a.k.a. Basic Graph Pattern (BGP) queries. By contrast to the literature, we do not restrict the structure nor semantics of RDF graphs and BGPQs. Our contributions include the denition and the computation of least general generalizations in these two settings, which amounts to nding the largest set of commonalities between incomplete databases and conjunctive queries, under deductive constraints. We also provide an experimental assessment of our technical contributions.

Šiuo metu yra sukurta nemažai priemonių aptikti įvairiausias DDoS atakas, tačiau siekiant sustabdyti arba bent sušvelninti DDoS atakų poveikį yra nuveikta labai nedaug. Yra labai sunku pasirinkti tinkamą DDoS atakos atrėmimo metodą. DDoS atakų atrėmimo metodų analizė galėtų padėti pasirinkti tinkamiausią metodą. „BGP DDoS Diversion“ atakų atrėmimo metodas yra vienas efektyviausių ir mažiausiai kaštų reikalaujantis metodas. Šis metodas įgyvendinamas panaudojant BGP protokolą. Ataka yra atremiama kuomet BGP protokolo pagalba yra paskelbiama tik dalis tinklo. DDoS atakos duomenų srautas tokiu atveju yra nukreipiamas į paskelbtą tinklo dalį, o kita tinklo dalis lieka nepažeista atakos. Interneto paslaugų teikėjai naudodami „BGP DDoS Diversion“ atrėmimo metodą gali apsaugoti savo tinklą nuo visiško nepasiekiamumo. Šiame tyrime buvo išnagrinėti DDoS atakų atrėmimo metodai. Išsamiai analizei buvo pasirinktas „BGP DDoS Diversion“ atrėmimo metodas. Metodo analizei buvo pasirinkta virtuali terpė. Sudaryti virtualią terpę buvo pasirinkta OPNET tinklų modeliavimo programa. Panaudojant OPNET modeliavimo įrangą, buvo sukurtas virtualus tinklas, veikiantis Interneto tinklo pagrindu. Sukurtame tinkle buvo įgyvendintas „BGP DDoS Diversion“ atakų atrėmimo metodas. Šiame darbe yra pateikta minėto atrėmimo metodo veikimo charakteristikų analizė. / Nowadays there are lot of ways how to detect various types of DDoS attacks, but in order to stop, or at least to mitigate the impact of such DDoS attacks not enough work is done. It is very difficult to choose the right DDoS mitigation method. The research of DDoS attacks mitigation can provide a good manual how to choose the most appropriate method. „BGP DDoS Diversion“ method is one of the most effective and least cost to deliver DDoS mitigation method. This method is implemented using BGP protocol. BGP diversion mechanism is used to announce a specific part of the provider‘s network to (a part of) the Internet. Announcing a specific part of this network will divert the DDoS traffic and thereby prevent other parts of the provider‘s network becoming unreachable. This gives the provider the ability to continue providing services of the rest of his custumers. This research was based on analyzing the DDoS mitigation methods. For the better analyzes the „BGP DDoS Diversion“ method was chosen. To analyze this method the virtual environment was the best way to accomplish this task. OPNET modeler software was chosen to create the virtual environment. Using OPNET the virtual network was created. Virtual network was based on Internet network standards. „BGP DDoS Diversion“ method was implemented and tested in the virtual network. This research provides the detail analyzes of „BGP DDoS Diversion“ method.

Internet es una red de redes; para poder comunicarse, se debe encontrar un camino entre el emisor y el receptor. El protocolo más usado para encontrar caminos entre redes distantes es Border Gateway Protocol (BGP). Este protocolo se basa en la confianza, por lo que es vulnerable a ataques y a errores de configuración, además, estos errores se propagan rápidamente, pudiendo afectar una parte considerable de Internet. Por esto se hace necesario contar con herramientas que detecten estos problemas. Cada red se dice visible desde algún punto, si desde ese punto se puede enviar información hacia esa red. El ideal de internet, es que todas las redes sean visibles desde todos los puntos,pero por los problemas antes mencionados, esto no siempre se cumple. En este trabajo se estudió el porcentaje de visibilidad de las redes chilenas, agrupadas por empresa. Para esto se creó una herramienta dividida en tres partes: recolección de datos, procesamiento y visualización de los datos. La visualización se realiza vía web, y cuenta con gráficos generados dinámicamente, para ayudar a una mejor comprensión de los datos. Los resultados mostraron que Chile tiene una alta visibilidad, cercana al 100 % en IPv4,mientras que en IPv6, se mantiene cercana al 82 %. Así mismo, la cantidad de redes usadas difiere notablemente entre ambas versiones, se usan 315 redes chilenas IPv4 y sólo 13 de IPv6. Se concluye que las redes chilenas tienen una configuración adecuada, que les permite ser alcanzables desde todos los puntos estudiados. Además estas configuraciones son bastante estables. Se constató también que si bien IPv6 está aún muy por debajo de IPv4 en penetración, esta ha ido aumentando.

Internet est le résultat de l’interaction des milliers de réseaux qui le composent. On les appelle les systèmes autonomes, chacun est identifié par un numéro unique (ASN). Les politiques de routage des AS et les accords économiques restent confidentiels normalement. Afin de mieux comprendre le routage dans l’Internet, les chercheurs modèlent le routage. Le model souvent utilisé c’est la représentation d’un AS par un atome. Nous présentons trois contributions dans ce travail. On montre d’abord des contradictions entre les décisions de routage réellement faites et les inférences à partir d’un ensemble d’hypothèses souvent utilisées. 70% des instances de ce qu’on appelle «plusieurs sorties» montrent des incohérences. Le routage est appelé à plusieurs sorties quand un AS utilise simultanément plusieurs routes vers la même destination, et chacune passe par un AS différent. Notre deuxième contribution est sur les routes BGP erronées causées par des mauvaises configurations liées à la transaction de la représentation des ASNs de 16-bits à 32-bits et l’utilisation d’AS23456 pour assurer la compatibilité. Nous montrons que tels erreurs sont encore présentes, ensuite nous montrons les effets des routes qui contiennent AS23456 sur les travaux qui emploient ces routes. Notre dernière contribution concerne les dynamiques de de routage dans l’Internet. Nous proposons une méthode pour quantifier ces dynamiques dans chaque AS afin d’en extraire ceux les plus dynamiques. Ensuite, on se concentre sur l’AS Level 3, l’AS le plus dynamique. Nous expliquons que la raison pour ce grand nombre de dynamique c’est l’équilibration de charge entre des routeurs qui avait plusieurs liens physiques. / Internet is the result of interaction of the thousands of networks that compose it. Each of them is called an autonomous system (AS) and has a unique number (ASN). Routing policies of ASes and business agreements remain in most cases confidential. To understand Internet routing, researchers use routing models. A large family of models represents an AS as an atomic structure. We make in this work three contributions. We look first on a set of commonly made assumptions to show using what we call multi-exit routing contradictions in routing decisions between real routing observed in publicly available measurements and that inferred from the assumptions. Sometimes, more than 70% of multi-exit instances show incoherencies. Multi-exit routing happens when an AS uses simultaneously different routes to a destination, each passing through a different AS. Our second contribution concerns erroneous BGP routes due to misconfigurations in BGP routers related to AS_TRANS, the solution introduced to assure the compatibility with old BGP routers when the change was made to represent ASNs on 32-bits instead of 16-bits. We show that such errors are indeed present, then we show how they can affect work making use of routes carrying this ASN. Our last contribution concerns routing dynamics in the Internet. We propose a method to quantity routing dynamics in each AS, then we look on ASes that have a large proportion of dynamics. After that, we focus on the AS Level 3, one of the ASes that we observe to be most dynamic. We explain that one of the reasons of a large part of the observed dynamics is load balancing between routers that have multiple physical links between each of them.

<p dir="ltr">The Internet is a large network of globally interconnected devices p used to facilitate the exchange of information across different parties. As usage of the Internet is expected to grow in the future, the underlying infrastructure must be secure to ensure traffic reaches its intended destination without any disruptions. However, the primary routing protocol used on the Internet, the Border Gateway Protocol (BGP), while scalable and can properly route traffic between large networks, does not inherently have any security mechanisms built within the protocol. This leads to devices that use BGP over the internet to be susceptible to BGP Hijacking attacks, which involve maliciously injected routes into BGP’s Routing Information Base (RIB) to intentionally redirect traffic to another destination. Attempts to solve these issues in the past have been challenging due to the prevalence of devices that use BGP on the existing Internet infrastructure and the lack of backward compatibility for proposed solutions. The goal of this research is to categorize the different types of BGP Hijacking attacks that are possible on a network, identify indicators that an ongoing BGP Hijacking attack based on received routes from the Internet locally without access to machines from other locations or networks, and subsequently leverage these indicators to protect local networks from external BGP Hijacking attacks.</p>

The IP protocol suite has been initallyi designed to provide best effort reachability among the nodes of a network or an inter-network. The goal was to design a set of routing solutions that would allow routers to automatically provide end-to-end connectivity among hosts. Also, the solution was meant to recover the connectivity upon the failure of one or multiple devices supporting the service, without the need of manual, slow, and error-prone reconfigurations. In other words, the requirement was to have an Internet that "converges" on its own. Along with the "Internet Boom", network availability expectations increased, as e-business emerged and companies started to associate loss of Internet connectivity with loss of customers... and money. So, Internet Service Providers (ISPs) relied on best practice rules for the design and the configuration of their networks, in order to improve their Quality of Service. The goal of this thesis is to complement the IP routing suite so as to improve its resiliency. It provides enhancements to routing protocols that reduce the IP packet losses when an IP network reacts to a change of its topology. It also provides techniques that allow ISPs to perform reconfigurations of their networks that do not lead to packet losses.

To ensure that services can be delivered reliably and continuously over theInternet, it is important that both Internet routes and edge networks aresecured. However, the sophistication and distributed nature of many at-tacks that target wide-area routing and edge networks make it difficult foran individual network, user, or router to detect these attacks. Thereforecollaboration is important. Although the benefits of collaboration betweendifferent network entities have been demonstrated, many open questionsstill remain, including how to best design distributed scalable mechanismsto mitigate attacks on the network infrastructure. This thesis makes severalcontributions that aim to secure the network infrastructure against attackstargeting wide-area routing and edge networks. First, we present a characterization of a controversial large-scale routinganomaly, in which a large Telecom operator hijacked a very large numberof Internet routes belonging to other networks. We use publicly availabledata from the time of the incident to understand what can be learned aboutlarge-scale routing anomalies and what type of data should be collected inthe future to diagnose and detect such anomalies. Second, we present multiple distributed mechanisms that enable col-laboration and information sharing between different network entities thatare affected by such attacks. The proposed mechanisms are applied in thecontexts of collaborating Autonomous Systems (ASes), users, and servers,and are shown to help raise alerts for various attacks. Using a combina-tion of data-driven analysis and simulations, based on publicly availablereal network data (including traceroutes, BGP announcements, and net-work relationship data), we show that our solutions are scalable, incur lowcommunication and processing overhead, and provide attractive tradeoffsbetween attack detection and false alert rates. Finally, for a set of previously proposed routing security mechanisms,we consider the impact of regional deployment restrictions, the scale of thecollaboration, and the size of the participants deploying the solutions. Al-though regional deployment can be seen as a restriction and the participationof large networks is often desirable, we find interesting cases where regionaldeployment can yield better results compared to random global deployment,and where smaller networks can play an important role in achieving bettersecurity gains. This study offers new insights towards incremental deploy-ment of different classes of routing security mechanisms.

A new approach to distributed network simulations that eases the burdens on the simulation developer in creating space-parallel simulations is presented. It provides a full-topology knowledge for every federate (simulator instance) to make the best routing decision to destinations simulated at other federates. Later, this technique was used to characterize the benefits of IP Anycast mechanism at large scale. Different IP Anycast scenarios were simulated in a detailed Border Gateway Protocol (BGP) simulator using a realistic large-scale AS topology. Results indicated that Anycast indeed provides higher availability and decreased end-to-end delay. It also showed that Anycast does not provide load balancing, and the BGP overhead associated with a topology change is reduced when Anycast is deployed. In addition, a simulation model of Enhanced Interior Gateway Routing Protocol (EIGRP) was developed and used to present a new approach for host mobility within an AS. The new solution is to allow end systems to retain a fixed IP address as those systems move across subnet boundaries, and to use route advertisement updates (by EIGRP) to inform routers of new or revised routes to reach the mobile hosts as they migrate. The simulation results showed the viability of this approach, and the ability of EIGRP to update routing tables in a timely fashion.

Thesis (M.S.)--California Polytechnic State University, 2009. / Title from PDF title page; viewed on January 12, 2010. Major professor: Franz Kurfess, Ph.D. "Presented to the faculty of California Polytechnic State University, San Luis Obispo." "In partial fulfillment of the requirements for the degree [of] Master of Science in Computer Science." "December 2009." Includes bibliographical references (p. 125-135).

Thesis (M. Phil.)--University of Hong Kong, 2001. / Includes bibliographical references (leaves 148-153).