Avec la complexité croissante des systèmes sur puce, de nouveaux défis ne cessent d’émerger dans la conception de ces systèmes en matière de vérification formelle et de synthèse de haut niveau. Plusieurs travaux autour de SystemC, considéré comme la norme pour la conception au niveau système, sont en cours afin de relever ces nouveaux défis. Cependant, à cause du modèle de concurrence complexe de SystemC, relever ces défis reste toujours une tâche difficile. Ainsi, nous pensons qu’il est primordial de partir sur de meilleures bases en utilisant un modèle de concurrence plus efficace. Par conséquent, dans cette thèse, nous étudions une méthodologie de conception qui offre une meilleure abstraction pour modéliser des composants parallèles en se basant sur le concept de transaction. Nous montrons comment, grâce au raisonnement simple que procure le concept de transaction, il devient plus facile d’appliquer la vérification formelle, le raffinement incrémental et la synthèse de haut niveau. Dans le but d’évaluer l’efficacité de cette méthodologie, nous avons fixé l’objectif d’optimiser la vitesse de simulation d’un modèle transactionnel en profitant d’une machine multicoeur. Nous présentons ainsi l’environnement de modélisation et de simulation parallèle que nous avons développé. Nous étudions différentes stratégies d’ordonnancement en matière de parallélisme et de surcoût de synchronisation. Une expérimentation faite sur un modèle du transmetteur Wi-Fi 802.11a a permis d’atteindre une accélération d’environ 1.8 en utilisant deux threads. Avec 8 threads, bien que la charge de travail des différentes transactions n’était pas importante, nous avons pu atteindre une accélération d’environ 4.6, ce qui est un résultat très prometteur. / With the increasing complexity of SoCs, new challenges continue to emerge in the design of these systems in terms of formal verification and high-level synthesis. Several research efforts around SystemC, considered the de facto standard for system-level design, are underway to meet these new challenges. However, because of the complex concurrency model of SystemC, these challenges remain difficult tasks. Thus, we believe it is important to continue on a better footing by using a more effective concurrency model. Therefore, in this thesis, we study a design methodology that provides a better abstraction for modeling parallel components based on the concept of transaction. We show how, through simple reasoning about transactions, it becomes easier to apply formal verification, incremental refinement and high-level synthesis. In order to evaluate the effectiveness of this methodology, we set the goal to optimize the simulation speed of a transactional model by taking advantage of a multicore machine. We present a modeling and parallel simulation environment that we developed. We study different scheduling strategies in terms of parallelism and synchronization overhead. An experiment made on a Wi-Fi 802.11a transmitter model achieved a speed up of about 1.8 using two threads. With 8 threads, although the workload of individual transactions was not significant, we could reach a speed up equal to 4.6 which is a very promising result.

Le problème d'intersection d'automates consiste à vérifier si plusieurs automates finis déterministes acceptent un mot en commun. Celui-ci est connu PSPACE-complet (resp. NL-complet) lorsque le nombre d'automates n'est pas borné (resp. borné par une constante). Dans ce mémoire, nous étudions la complexité du problème d'intersection d'automates pour plusieurs types de langages et d'automates tels les langages unaires, les automates à groupe (abélien), les langages commutatifs et les langages finis. Nous considérons plus particulièrement le cas où chacun des automates possède au plus un ou deux états finaux. Ces restrictions permettent d'établir des liens avec certains problèmes algébriques et d'obtenir une classification intéressante de problèmes d'intersection d'automates à l'intérieur de la classe P. Nous terminons notre étude en considérant brièvement le cas où le nombre d'automates est fixé. / The automata non emptiness intersection problem is to determine whether several deterministic finite automata accept a word in common. It is known to be PSPACE-complete (resp. NL-complete) whenever the number of automata is not bounded (resp. bounded by a constant). In this work, we study the complexity of the automata intersection problem for several types of languages and automata such as unary languages, (abelian) group automata, commutative languages and finite languages. We raise the issue of limiting the number of final states to at most two in the automata involved. This way, we obtain relationships with some algebraic problems and an interesting classification of automata intersection problems inside the class P. Finally, we briefly consider the bounded version of the automata intersection problem.

L’avénement des réseaux sociaux, tel que Facebook, MySpace et LinkedIn, a fourni une plateforme permettant aux individus de rester facilement connectés avec leurs amis, leurs familles ou encore leurs collègues tout en les encourageant activement à partager leurs données personnelles à travers le réseau. Avec la richesse des activités disponibles sur un réseau social, la quantité et la variété des informations personnelles partagées sont considérables. De plus, de part leur nature numérique, ces informations peuvent être facilement copiées, modifiées ou divulguées sans le consentement explicite de leur propriétaire. Ainsi, l’information personnelle révélée par les réseaux sociaux peut affecter de manière concrète la vie de leurs utilisateurs avec des risques pour leur vie privée allant d’un simple embarras à la ruine complète de leur réputation, en passant par l’usurpation d’identité. Malheureusement, la plupart des utilisateurs ne sont pas conscients de ces risques et les outils mis en place par les réseaux sociaux actuels ne sont pas suffisants pour protéger efficacement la vie privée de leurs utilisateurs. En outre, même si un utilisateur peut contrôler l’accès à son propre profil, il ne peut pas contrôler ce que les autres révèlent à son sujet. En effet, les “amis” d’un utilisateur sur un réseau social peuvent parfois révéler plus d’information à son propos que celui-ci ne le souhaiterait. Le respect de la vie privée est un droit fondamental pour chaque individu. Nous pré- sentons dans cette thèse une approche qui vise à accroître la prise de conscience des utilisateurs des risques par rapport à leur vie privée et à maintenir la souveraineté sur leurs données lorsqu’ils utilisent un réseau social. La première contribution de cette thèse réside dans la classification des risques multiples ainsi que les atteintes à la vie privée des utilisateurs d’un réseau social. Nous introduisons ensuite un cadre formel pour le respect de la vie privée dans les réseaux sociaux ainsi que le concept de politique de vie privée (UPP). Celle-ci définie par l’utilisateur offre une manière simple et flexible de spécifier et communiquer leur attentes en terme de respect de la vie privée à d’autres utilisateurs, tiers parties ainsi qu’au fournisseur du réseau social. Par ailleurs, nous dé- finissons une taxonomie (possiblement non-exhaustive) des critères qu’un réseau social peut intégrer dans sa conception pour améliorer le respect de la vie privée. En introduisant le concept de réseau social respectueux de la vie privée (PSNS), nous proposons Privacy Watch, un réseau social respectueux de la vie privée qui combine les concepts de provenance et d’imputabilité afin d’aider les utilisateurs à maintenir la souveraineté sur leurs données personnelles. Finalement, nous décrivons et comparons les différentes propositions de réseaux sociaux respectueux de la vie privée qui ont émergé récemment. Nous classifions aussi ces différentes approches au regard des critères de respect de la vie privée introduits dans cette thèse. / The rise of Social Networking Sites (SNS), such as Facebook, Myspace, and LinkedIn has provided a platform for individuals to easily stay in touch with friends, family and colleagues and actively encourage their users to share personal information. With the wealth of activities available on SNS, the amount and variety of personal information shared is considerable and diverse. Additionally, due to its digital nature, this information can be easily copied, modified and disclosed without the explicit consent of their owner. Personal information disclosed from SNS could affect users’ life, with privacy risks ranging from simple embarrassment to ruining their reputation, or even identity theft. Unfortunately, many users are not fully aware of the danger of divulging their personal information and the current privacy solutions are not flexible and thorough enough to protect user data. Furthermore, even though users of SNS can control access to their own profile, they cannot control what others may reveal about them. Friends can sometimes be untrustworthy and disclose more information about the user than they should. Considering that privacy is a fundamental right for every individual, in this thesis, we present an approach that increases privacy awareness of the users and maintains the sovereignty of their data when using SNS. The first contribution of this thesis is the classification of multiple types of risks as well as user expectations regarding privacy in SNS. Afterwards, we introduce the Privacy Framework for SNS and the concept of User Privacy Policy (UPP) to offer users an easy and flexible way to specify and communicate their privacy concerns to other users, third parties and SNS provider. Additionally, we define a taxonomy (possibly non-exhaustive) of privacy criteria that can enhance the user privacy if they are integrated within the design of a SNS and introduce the concept of a Privacy-enhanced SNS (PSNS). Furthermore, we present also Privacy Watch, a theoretical proposal of a PSNS platform that combines the concept of provenance and accountability to help SNS users maintain sovereignty over their personal data. Finally, we survey and compare several privacy-enhanced SNS that were recently proposed that try to integrate some privacy features directly into the design of the system. We also classify these different approaches with respect to the privacy criteria developed.

De nos jours, les applications de grande taille sont développées à l’aide de nom- breux cadres d’applications (frameworks) et intergiciels (middleware). L’utilisation ex- cessive d’objets temporaires est un problème de performance commun à ces applications. Ce problème est appelé “object churn”. Identifier et comprendre des sources d’“object churn” est une tâche difficile et laborieuse, en dépit des récentes avancées dans les tech- niques d’analyse automatiques. Nous présentons une approche visuelle interactive conçue pour aider les développeurs à explorer rapidement et intuitivement le comportement de leurs applications afin de trouver les sources d’“object churn”. Nous avons implémenté cette technique dans Vasco, une nouvelle plate-forme flexible. Vasco se concentre sur trois principaux axes de con- ception. Premièrement, les données à visualiser sont récupérées dans les traces d’exécu- tion et analysées afin de calculer et de garder seulement celles nécessaires à la recherche des sources d’“object churn”. Ainsi, des programmes de grande taille peuvent être vi- sualisés tout en gardant une représentation claire et compréhensible. Deuxièmement, l’utilisation d’une représentation intuitive permet de minimiser l’effort cognitif requis par la tâche de visualisation. Finalement, la fluidité des transitions et interactions permet aux utilisateurs de garder des informations sur les actions accomplies. Nous démontrons l’efficacité de l’approche par l’identification de sources d’“object churn” dans trois ap- plications utilisant intensivement des cadres d’applications framework-intensive, inclu- ant un système commercial. / Nowadays, large framework-intensive programs are developed using many layers of frameworks and middleware. Bloat, and particularly object churn, is a common per- formance problem in framework-intensive applications. Object churn consists of an ex- cessive use of temporary objects. Identifying and understanding sources of churn is a difficult and labor-intensive task, despite recent advances in automated analysis tech- niques. We present an interactive visualization approach designed to help developers quickly and intuitively explore the behavior of their application with respect to object churn. We have implemented this technique in Vasco, a new flexible and scalable visualization platform. Vasco follows three main design goals. Firstly, data is collected from execu- tion traces. It is analyzed in order to calculate and keep only the data that is necessary to locate sources of object churn. Therefore, large programs can be visualized while keeping a clear and understandable view. Secondly, the use of an intuitive view allows minimizing the cognitive effort required for the visualization task. Finally, the fluidity of transitions and interactions allows users to mentally preserve the context throughout their interactions. We demonstrate the effectiveness of the approach by identifying churn in three framework-intensive applications, including a commercial system.

On retrouve dans la nature un nombre impressionnant de matériaux semi-transparents tels le marbre, le jade ou la peau, ainsi que plusieurs liquides comme le lait ou les jus. Que ce soit pour le domaine cinématographique ou le divertissement interactif, l'intérêt d'obtenir une image de synthèse de ce type de matériau demeure toujours très important. Bien que plusieurs méthodes arrivent à simuler la diffusion de la lumière de manière convaincante a l'intérieur de matériaux semi-transparents, peu d'entre elles y arrivent de manière interactive. Ce mémoire présente une nouvelle méthode de diffusion de la lumière à l'intérieur d'objets semi-transparents hétérogènes en temps réel. Le coeur de la méthode repose sur une discrétisation du modèle géométrique sous forme de voxels, ceux-ci étant utilisés comme simplification du domaine de diffusion. Notre technique repose sur la résolution de l'équation de diffusion à l'aide de méthodes itératives permettant d'obtenir une simulation rapide et efficace. Notre méthode se démarque principalement par son exécution complètement dynamique ne nécessitant aucun pré-calcul et permettant une déformation complète de la géométrie. / We find in nature several semi-transparent materials such as marble, jade or skin, as well as liquids such as milk or juices. Whether it be for digital movies or video games, having an efficient method to render these materials is an important goal. Although a large body of previous academic work exists in this area, few of these works provide an interactive solution. This thesis presents a new method for simulating light scattering inside heterogeneous semi-transparent materials in real time. The core of our technique relies on a geometric mesh voxelization to simplify the diffusion domain. The diffusion process solves the diffusion equation in order to achieve a fast and efficient simulation. Our method differs mainly from previous approaches by its completely dynamic execution requiring no pre-computations and hence allowing complete deformations of the geometric mesh.

Les structures avec des lieurs sont très communes en informatique. Les langages de programmation et les systèmes logiques sont des exemples de structures avec des lieurs. La manipulation de lieurs est délicate, de sorte que l’écriture de programmes qui ma- nipulent ces structures tirerait profit d’un soutien spécifique pour les lieurs. L’environ- nement de programmation Beluga est un exemple d’un tel système. Nous développons et présentons ici un compilateur pour ce système. Parmi les programmes pour lesquels Beluga est spécialement bien adapté, plusieurs peuvent bénéficier d’un compilateur. Par exemple, les programmes pour valider les types (les "type-checkers"), les compilateurs et les interpréteurs tirent profit du soutien spécifique des lieurs et des types dépendants présents dans le langage. Ils nécessitent tous également une exécution efficace, que l’on propose d’obtenir par le biais d’un compilateur. Le but de ce travail est de présenter un nouveau compilateur pour Beluga, qui emploie une représentation interne polyvalente et permet de partager du code entre plusieurs back-ends. Une contribution notable est la compilation du filtrage de Beluga, qui est particulièrement puissante dans ce langage. / In computer science, structures with variable binders are very common. Program- ming languages and logical frameworks are examples of structures with binders. Thus writing programs that deal with these kinds of data benefits with explicit support for data binding. The Beluga programming environment is an example of such a system. In this work we develop and present a compiler for the system. Many of the programs that Beluga is specially well suited for writing can benefit from a compiler. For example, some of the kinds programs that would benefit more are type-checkers, compilers and interpreters that take advantage of the binder support and dependent types present in the language, and also require a reasonably fast run-time. Our goal in this work, is to present a compiler for the Beluga system, that uses a very versatile internal representation that helps with the development of the system, and allows a sharing of code between several back-ends. Furthermore, we present a way of compiling the uniquely powerful pattern language supported by Beluga.

Dans ce mémoire, nous proposons des protocoles cryptographiques d'échange de clef, de mise en gage, et de transfert équivoque. Un premier protocole de transfert équivoque, primitive cryptographique universelle pour le calcul multi-parties, s'inspire du protocole d'échange de clef par puzzle de Merkle, et améliore les résultats existants. Puis, nous montrons qu'il est possible de construire ces mêmes primitives cryptographiques sans l'hypothèse des fonctions à sens unique, mais avec le problème 3SUM. Ce problème simple ---dans une liste de n entiers, en trouver trois dont la somme a une certaine valeur--- a une borne inférieure conjecturée de Omega(n^2). / In this work, we propose cryptographic protocols for key exchange, bit commitment and oblivious transfer. Our oblivious transfer protocol, universal cryptographic primitive for multipartie computation, is inspired from Merkle's key exchange protocol with puzzles, and improves on existing results. Then, we show that it's possible to build those same cryptographic primitives without the hypothesis of one-way functions, but with the 3SUM problem. This simple problem ---in a list of n integers, find three that sum is a desired value--- has a conjectured lower bound of Omega(n^2).

Les réseaux sociaux accueillent chaque jour des millions d’utilisateurs. Les usagers de ces réseaux, qu’ils soient des particuliers ou des entreprises, sont directement affectés par leur fulgurante expansion. Certains ont même développé une certaine dépendance à l’usage des réseaux sociaux allant même jusqu’à transformer leurs habitudes de vie de tous les jours. Cependant, cet engouement pour les réseaux sociaux n’est pas sans danger. Il va de soi que leur expansion favorise et sert également l’expansion des attaques en ligne. Les réseaux sociaux constituent une opportunité idéale pour les délinquants et les fraudeurs de porter préjudice aux usagers. Ils ont accès à des millions de victimes potentielles. Les menaces qui proviennent des amis et auxquelles font face les utilisateurs de réseaux sociaux sont nombreuses. On peut citer, à titre d’exemple, la cyberintimidation, les fraudes, le harcèlement criminel, la menace, l’incitation au suicide, la diffusion de contenu compromettant, la promotion de la haine, l’atteinte morale et physique, etc. Il y a aussi un « ami très proche » qui peut être très menaçant sur les réseaux sociaux : soi-même. Lorsqu’un utilisateur divulgue trop d’informations sur lui-même, il contribue sans le vouloir à attirer vers lui les arnaqueurs qui sont à la recherche continue d’une proie. On présente dans cette thèse une nouvelle approche pour protéger les utilisateurs de Facebook. On a créé une plateforme basée sur deux systèmes : Protect_U et Protect_UFF. Le premier système permet de protéger les utilisateurs d’eux-mêmes en analysant le contenu de leurs profils et en leur proposant un ensemble de recommandations dans le but de leur faire réduire la publication d’informations privées. Le second système vise à protéger les utilisateurs de leurs « amis » dont les profils présentent des symptômes alarmants (psychopathes, fraudeurs, criminels, etc.) en tenant compte essentiellement de trois paramètres principaux : le narcissisme, le manque d’émotions et le comportement agressif. / Social networks deal every day with millions of users (individuals or companies). They are directly affected by their rapid expansion. Some have developed a certain dependence on the use of social networks and even transform their everyday lifestyle. However, this craze for social networking is not always secure. It is obvious that their expansion promotes and serves the increase of online attacks. Social networks are an ideal opportunity for criminals and fraudsters to take advantage of users. They give access to millions of potential victims. Threats coming from “friends” on social networks are numerous: cyberintimidation, fraud, criminal harassment, moral and physical threats, incitement to suicide, circulation of compromising contents, hatred promotions, etc. There is also a “very close friend” who could cause us problems with his behavior on social networks: ourselves. When a user discloses too much information about himself, it contributes unwittingly to attracting scammers who are continually looking for preys. This thesis presents a new approach to protect Facebook users. We created a platform based on two systems: Protect_U et Protect_UFF. The first system tries to protect users from themselves by analysing the content of their profiles and by suggesting a list of recommendations in order to reduce the publication of private information. The second system aims to protect users from their “friends” who have profiles presenting alarming symptoms (psychopaths, fraudsters, criminals, etc.) taking into account essentially three main parameters: narcissism, lack of emotions and aggressive behaviour.

Nous proposons de construire un atlas numérique 3D contenant les caractéristiques moyennes et les variabilités de la morphologie d’un organe. Nos travaux seront appliqués particulièrement à la construction d'un atlas numérique 3D de la totalité de la cornée humaine incluant la surface antérieure et postérieure à partir des cartes topographiques fournies par le topographe Orbscan II. Nous procédons tout d'abord par normalisation de toute une population de cornées. Dans cette étape, nous nous sommes basés sur l'algorithme de recalage ICP (iterative closest point) pour aligner simultanément les surfaces antérieures et postérieures d'une population de cornée vers les surfaces antérieure et postérieure d'une cornée de référence. En effet, nous avons élaboré une variante de l'algorithme ICP adapté aux images (cartes) de cornées qui tient compte de changement d'échelle pendant le recalage et qui se base sur la recherche par voisinage via la distance euclidienne pour établir la correspondance entre les points. Après, nous avons procédé pour la construction de l'atlas cornéen par le calcul des moyennes des élévations de surfaces antérieures et postérieures recalées et leurs écarts-types associés. Une population de 100 cornées saines a été utilisée pour construire l'atlas cornéen normal. Pour visualiser l’atlas, on a eu recours à des cartes topographiques couleurs similairement à ce qu’offrent déjà les systèmes topographiques actuels. Enfin, des observations ont été réalisées sur l'atlas cornéen reflétant sa précision et permettant de développer une meilleure connaissance de l’anatomie cornéenne. / We propose to build a 3D digital atlas which contains the average characteristics and variability of the morphology of an organ. In particular our work consists in the construction of a 3D digital atlas of the entire human cornea including anterior and posterior surfaces. The atlas was built using topographies provided by the Orbscan II system. First, we normalized the given population of corneas using a variant of the ICP (iterative closest point) algorithm for shape registration to fit simultaneously the anterior and posterior surfaces with the anterior and posterior surfaces of a reference cornea. Indeed, we developed a specific algorithm for corneas topographies that considers scaling during registration and which is based on neighborhood search via the Euclidean distance to find the correspondence between points. After that, we built the corneal atlas by averaging elevations of anterior and posterior surfaces and by calculating their associated standard deviations. A population of 100 healthy corneas was used to construct the normal corneal atlas. To illustrate the atlas, we used topographic color maps like those already offered by existing topographic systems. Finally, observations were made on the corneal atlas that reflects its precision and allows to develop a better understanding of corneal anatomy.

Les techniques de groupement technologique sont aujourd’hui utilisées dans de nombreux ateliers de fabrication; elles consistent à décomposer les systèmes industriels en sous-systèmes ou cellules constitués de pièces et de machines. Trouver le groupement technologique le plus efficace est formulé en recherche opérationnelle comme un problème de formation de cellules. La résolution de ce problème permet de tirer plusieurs avantages tels que la réduction des stocks et la simplification de la programmation. Plusieurs critères peuvent être définis au niveau des contraintes du problème tel que le flot intercellulaire,l’équilibrage de charges intracellulaires, les coûts de sous-traitance, les coûts de duplication des machines, etc. Le problème de formation de cellules est un problème d'optimisation NP-difficile. Par conséquent les méthodes exactes ne peuvent être utilisées pour résoudre des problèmes de grande dimension dans un délai raisonnable. Par contre des méthodes heuristiques peuvent générer des solutions de qualité inférieure, mais dans un temps d’exécution raisonnable. Dans ce mémoire, nous considérons ce problème dans un contexte bi-objectif spécifié en termes d’un facteur d’autonomie et de l’équilibre de charge entre les cellules. Nous présentons trois types de méthodes métaheuristiques pour sa résolution et nous comparons numériquement ces métaheuristiques. De plus, pour des problèmes de petite dimension qui peuvent être résolus de façon exacte avec CPLEX, nous vérifions que ces métaheuristiques génèrent des solutions optimales. / Group technology techniques are now widely used in many manufacturing systems. Those techniques aim to decompose industrial systems into subsystems or cells of parts and machines. The problem of finding the most effectivegroup technology is formulated in operations research as the Cell Formation Problem. Several criteria can be used to specify the optimal solution such as flood intercellular, intracellular load balancing, etc. Solving this problem leads to several advantages such as reducing inventory and simplifying programming. The Cell Formation Problem is an NP-hard problem; therefore, exact methods cannot be used to solve large problems within a reasonabletime, whereas heuristics can generate solutions of lower quality, but in a reasonable execution time. We suggest in this work, three different metaheuristics to solve the cell formation problem having two objectives functions: cell autonomy and load balancing between the cells.We compare numerically these metaheuristics. Furthermore, for problems of smaller dimension that can be solved exactly with CPLEX, we verify that the metaheuristics can reach the optimal value.