Commodity computer systems today do not provide system support for privacy. As a result, given the creation of new leak opportunities by ever-increasing software complexity, leaks of private data are inevitable. This thesis presents Suliban and Lacuna, two systems that allow programs to execute privately on commodity hardware. These systems demonstrate different points in a design space wherein stronger privacy guarantees can be traded for greater system usability. Suliban uses trusted computing technology to run computation-only code privately; we refer to this protection as "cloaking". In particular, Suliban can run malicious computations in a way that is resistant to analysis. Suliban uses the Trusted Platform Module and processor late launch to create an execution environment entirely disjoint from normal system software. Suliban uses a remote attestation protocol to demonstrate to a malware distribution platform that the environment has been correctly created before the environment is allowed to receive a malicious payload. Suliban's execution outside of standard system software allows it to resist attackers with privileged operating system access and those that can perform some forms of physical attack. However, Suliban cannot access system services, and requires extra case-by-case measures to get outside information like the date or host file contents. Nonetheless, we demonstrate that Suliban can run computations that would be useful in real malware. In building Suliban, we uncover which defenses are most effective against it and highlight current problems with the use of the Trusted Platform Module. Lacuna instead aims at achieving forensic deniability, which guarantees that an attacker that gains full control of a system after a computation has finished cannot learn answers to even binary questions (with a few exceptions) about the computation. This relaxation of Suliban's guarantees allows Lacuna to run full-featured programs concurrently with non-private programs on a system. Lacuna's key primitive is the ephemeral channel, which allows programs to use peripherals while maintaining forensic deniability. This thesis extends the original Lacuna work by investigating how Linux kernel statistics leak private session information and how to mitigate these leaks. / text

Participatory Sensing (PS) is a new data collection paradigm in which people use their cellular phone resources to sense and transmit data of interest to address a collective problem that would have been very difficult to assess otherwise. Although many PS-based applications can be foreseen to solve interesting and useful problems, many of them have not been fully implemented due to privacy concerns. As a result, several privacy-preserving mechanisms have been proposed. This dissertation presents the state-of-the-art of privacy-preserving mechanisms for PS systems. It includes a new taxonomy and describes the most important issues in the design, implementation, and evaluation of privacy-preserving mechanisms. Then, the most important mechanisms available in the literature are described, classified and qualitatively evaluated based on design issues. The dissertation also presents a model to study the interactions between privacy-preserving, incentive and inference mechanisms and the effects that they may have on one another, and more importantly, on the quality of information that the system provides to the final user. Then, a new hybrid privacy-preserving mechanism is proposed. This algorithm dynamically divides the area of interest into cells of different sizes according to the variability of the variable of interest being measured and chooses between two privacy-preserving mechanisms depending on the size of the cell. In small cells, where participants can be identified easier, the algorithm uses a double-encryption technique to protect the privacy of the participants and increase the quality of the information. In bigger cells, where the variability of the variable of interest is low, data anonymization and obfuscation techniques are used to protect the actual location (privacy) of the participant. The proposed mechanism is evaluated along with other privacy-preserving mechanisms using a real PS system for air pollution monitoring. The systems are evaluated considering the quality of information provided to the final user, energy consumption, and the level of privacy protection. This last criterion is evaluated when the adversary is able to compromise one or several records in the system. The experiments show the superior performance of proposed mechanism and the existing trade-offs in terms of privacy, quality of information, and energy consumption.

Constructing advanced cryptographic applications often requires the ability of privately embedding messages or functions in the code of a program. As an example, consider the task of building a searchable encryption scheme, which allows the users to search over the encrypted data and learn nothing other than the search result. Such a task is achievable if it is possible to embed the secret key of an encryption scheme into the code of a program that performs the "decrypt-then-search" functionality, and guarantee that the code hides everything except its functionality. This thesis studies two cryptographic primitives that facilitate the capability of hiding secrets in the program of random functions. 1. We first study the notion of a private constrained pseudorandom function (PCPRF). A PCPRF allows the PRF master secret key holder to derive a public constrained key that changes the functionality of the original key without revealing the constraint description. Such a notion closely captures the goal of privately embedding functions in the code of a random function. Our main contribution is in constructing single-key secure PCPRFs for NC^1 circuit constraints based on the learning with errors assumption. Single-key secure PCPRFs were known to support a wide range of cryptographic applications, such as private-key deniable encryption and watermarking. In addition, we build reusable garbled circuits from PCPRFs. 2. We then study how to construct cryptographic hash functions that satisfy strong random oracle-like properties. In particular, we focus on the notion of correlation intractability, which requires that given the description of a function, it should be hard to find an input-output pair that satisfies any sparse relations. Correlation intractability captures the security properties required for, e.g., the soundness of the Fiat-Shamir heuristic, where the Fiat-Shamir transformation is a practical method of building signature schemes from interactive proof protocols. However, correlation intractability was shown to be impossible to achieve for certain length parameters, and was widely considered to be unobtainable. Our contribution is in building correlation intractable functions from various cryptographic assumptions. The security analyses of the constructions use the techniques of secretly embedding constraints in the code of random functions.

Orientador: Aleardo Manacero Junior / Banca: Sergio Azevedo de Oliveira / Banca: Francisco Villarreal Alvarado / Banca: Rodolfo Jardim Azevedo / Banca: André Luiz Moura dos Santos / Resumo: Ofusca c~ao de c odigo tem por nalidade di cultar a detec c~ao de propriedades intr nsecas de um algoritmo atrav es de altera c~oes em sua sintaxe, entretanto preservando sua sem^antica. Desenvolvedores de software usam ofusca c~ao de c odigo para defender seus programas contra ataques de propriedade intelectual e para aumentar a seguran ca do c odigo. Por outro lado, programadores maliciosos geralmente ofuscam seus c odigos para esconder comportamento malicioso e para evitar detec c~ao pelos anti-v rus. Nesta tese, e introduzido um m etodo para realizar an alise com sensitividade ao contexto em bin arios com ofuscamento de chamada e retorno de procedimento. Para obter sem^antica equivalente, estes bin arios utilizam opera c~oes diretamente na pilha ao inv es de instru c~oes convencionais de chamada e retorno de procedimento. No estado da arte atual, a de ni c~ao de sensitividade ao contexto est a associada com opera c~oes de chamada e retorno de procedimento, assim, an alises interprocedurais cl assicas n~ao s~ao con aveis para analisar bin arios cujas opera c~oes n~ao podem ser determinadas. Uma nova de ni c~ao de sensitividade ao contexto e introduzida, baseada no estado da pilha em qualquer instru c~ao. Enquanto mudan cas em contextos a chamada de procedimento s~ao intrinsicamente relacionadas com transfer^encia de controle, assim, podendo ser obtidas em termos de caminhos em um grafo de controle de uxo interprocedural, o mesmo n~ao e aplic avel para mudan cas em contextos a pilha. Um framework baseado em interpreta c~ao abstrata e desenvolvido para avaliar contexto baseado no estado da pilha e para derivar m etodos baseado em contextos a chamada de procedimento para uso com contextos baseado no estado da pilha. O metodo proposto n~ao requer o uso expl cito de instru c~oes de chamada e retorno de procedimento, por em depende do... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: A code obfuscation intends to confuse a program in order to make it more di cult to understand while preserving its functionality. Programs may be obfuscated to protect intellectual property and to increase security of code. Programs may also be obfuscated to hide malicious behavior and to evade detection by anti-virus scanners. We introduce a method for context-sensitive analysis of binaries that may have obfuscated procedure call and return operations. These binaries may use direct stack operators instead of the native call and ret instructions to achieve equivalent behavior. Since de nition of context-sensitivity and algorithms for context-sensitive analysis has thus far been based on the speci c semantics associated to procedure call and return operations, classic interprocedural analyses cannot be used reliably for analyzing programs in which these operations cannot be discerned. A new notion of context-sensitivity is introduced that is based on the state of the stack at any instruction. While changes in calling-context are associated with transfer of control, and hence can be reasoned in terms of paths in an interprocedural control ow graph (ICFG), the same is not true for changes in stackcontext. An abstract interpretation based framework is developed to reason about stackcontext and to derive analogues of call-strings based methods for the context-sensitive analysis using stack-context. This analysis requires the knowledge of how the stack, rather the stack pointer, is represented and on the knowledge of operators that manipulate the stack pointer. The method presented is used to create a context-sensitive version of Venable et al.'s algorithm for detecting obfuscated calls. Experimental results show that the contextsensitive version of the algorithm generates more precise results and is also computationally more e cient than its context-insensitive counterpart. / Doutor

Today, smartphones are in widespread use by consumers, commercial companies and government authorities. Unfortunately, there are many examples of applications carrying out malicious activities, such as stealing information or subscribing to premium-rate services. In this thesis work, a novel application whitelisting process (AWP) is proposed. It defines processes for application security audits and whitelisting i.e. methods on how to classify, evaluate and test a given application to make sure that it with a level of assurance does not have malicious intentions. In a risk analysis of users in high security environments, the results showed that confidentiality and availability is the top most important security aspects to protect in this environment. The applications in the whitelisting process should therefore be tested for known malware and adware as well as permissions that can be used to send private information to remote servers. Additionally, testing should also be carried out for information leakage through intents and content resolvers. Because whitelisting is locking down the freedom and usability that comes with a smartphone, three different leveled whitelists are proposed to satisfy users and organizations with different security needs. A prototype was developed to prove the overall usability of the design. The result of scanning 200 applications from Google Play showed that 12% of all applications can be placed in the highest leveled whitelist. The results also suggest that 17.5 % of all applications on Google Play are malware or potentially unwanted applications. The results points to that using this novel whitelisting process, about 30% of all applications can be automated into whitelists and will not need manual analysis.

La rétro-conception est une technique qui consiste à analyser un produit afin d'en extraire un secret. Lorsque le produit ciblé est un programme informatique, le rétro-concepteur peut chercher à extraire un algorithme ou tout élément du code de ce programme. L'obfuscation est une technique de protection qui consiste à modifier le code d'un programme afin de le rendre plus difficile à rétro-concevoir. Nous nous intéressons à l'étude et au développement de techniques d'obfuscation de programmes informatiques. Nous avons développé une nouvelle technique d'obfuscation de code, puis nous avons démontré son efficacité et finalement nous avons implémenté une autre technique de protection ayant pour objectif de renforcer la résilience des techniques de protection anti-rétro conception. Nous avons donc, dans un premier temps, imaginé et implémenté une nouvelle technique d'obfuscation permettant de protéger certains éléments spécifiques contenus dans les programmes implémentés en langage C. En nous appuyant sur un état de l'art détaillé des techniques d'analyses utilisées lors de la rétro-conception de programmes, nous avons établi l'efficacité de cette technique de protection. Dans un second temps, nous avons étayé les éléments précédemment établis, en démontrant de façon empirique que cette mesure de protection peut être appliquée sur des programmes concrets. Nous démontrons qu'elle peut être mise en place sur des codes de haut niveau et rester efficace sur les fichiers exécutables obtenus à partir de ces codes. Nous poussons notre analyse jusqu'à démontrer que lorsque le processus d'obfuscation est réalisé de façon scrupuleuse, le temps d'exécution des programmes protégés reste dans le même ordre de grandeur que celui des programmes non protégés. Dans un troisième temps, nous travaillons en avance de phase en développant des mécanismes de protection ciblés, visant à contrer les outils d'analyse automatique utilisés par les rétro-concepteurs. Leur objectif est de renforcer la robustesse des techniques appliquées à haut niveau en augmentant leur furtivité et en fournissant au rétro-concepteur des résultats erronés. Nos contributions couvrent divers sujets liés à la lutte contre la rétro-conception. Nous avons développé et implémenté de nouvelles techniques de protection de code. Lorsque ces techniques de protection s'appliquent à haut niveau, nous avons mis au point un processus permettant de démontrer qu'elles ne perdent pas en efficacité et que leur coût en terme de temps d'exécution reste acceptable. Pour les techniques de protection plus bas niveau que nous avons développées, nous avons démontré leur efficacité face à des outils d'analyse dynamique de code utilisés lors de la rétro-conception. / Reverse engineering is a technique that consists in analyzing a product in order to extract a secret. When a computer program is targeted, the reverse engineer may seek to extract an algorithm code or any component of this program. Obfuscation is a protection technique aimed to make it more difficult to reverse engineer. We are interested in the study and development of obfuscation techniques to protect computer programs. We have developed a new technique of code obfuscation, then we have demonstrated its effectiveness, and finally we implemented another protection technique with the aim of enhance the resilience of anti-reverse engineering protection techniques. So we, initially, designed and implemented a new obfuscation technique to protect certain specific elements contained in the programs implemented in C language. By relying on dynamic analysis techniques, we have established the effectiveness of this protection technique. Secondly, we have backed up previously established elements, by demonstrating empirically that this protection can be applied to concrete programs. We demonstrate that this protection can be placed on high-level codes and remain effective on executable files obtained from these codes. We demonstrate that when the process of obfuscation is realized in a scrupulous way, the execution time of programs remains in the same order as that of the protected programs. Thirdly, we work on developing targeted protection mechanisms to counter automatic analysis tools used by reverse engineers. Their aim is to enhance the robustness of the techniques applied to high level by increasing their stealth and providing fake results for the reverse engineers. Our contributions cover various topics related to protection against reverse engineering. We have developed and implemented new code protection techniques. When these protection techniques are apply to high level, we have developed a process to demonstrate that they do not lose efficiency and their cost in terms of execution time remains acceptable. For the lowest level protection techniques that we have developed, we have demonstrated their effectiveness face of dynamic code analysis tools used in reverse engineering.

In many forensic investigations, questions linger regarding the identity of the authors of the software specimen. Research has identified methods for the attribution of binary files that have not been obfuscated, but a significant percentage of malicious software has been obfuscated in an effort to hide both the details of its origin and its true intent. Little research has been done around analyzing obfuscated code for attribution. In part, the reason for this gap in the research is that deobfuscation of an unknown program is a challenging task. Further, the additional transformation of the executable file introduced by the obfuscator modifies or removes features from the original executable that would have been used in the author attribution process. Existing research has demonstrated good success in attributing the authorship of an executable file of unknown provenance using methods based on static analysis of the specimen file. With the addition of file obfuscation, static analysis of files becomes difficult, time consuming, and in some cases, may lead to inaccurate findings. This paper presents a novel process for authorship attribution using dynamic analysis methods. A software emulated system was fully instrumented to become a test harness for a specimen of unknown provenance, allowing for supervised control, monitoring, and trace data collection during execution. This trace data was used as input into a supervised machine learning algorithm trained to identify stylometric differences in the specimen under test and provide predictions on who wrote the specimen. The specimen files were also analyzed for authorship using static analysis methods to compare prediction accuracies with prediction accuracies gathered from this new, dynamic analysis based method. Experiments indicate that this new method can provide better accuracy of author attribution for files of unknown provenance, especially in the case where the specimen file has been obfuscated.

No description available.

La thèse contient deux parties principales: la première partie est consacrée à l’extraction du format des messages, la deuxième partie est consacrée à l’obfuscation des comportements des malwares et la détection. Pour la première partie, nous considérons deux problèmes: "la couverture des codes" et "l’extraction du format des messages". Pour la couverture des codes, nous proposons une nouvelle méthode basée sur le "tainting intelligent" et sur l’exécution inversée. Pour l’extraction du format des messages, nous proposons une nouvelle méthode basée sur la classification de messages en utilisant des traces d’exécution. Pour la deuxième partie, les comportements des codes malveillants sont formalisés par un modèle abstrait pour la communication entre le programme et le système d’exploitation. Dans ce modèle, les comportements du programme sont des appels systèmes. Étant donné les comportements d’un programme bénin, nous montrons de façon constructive qu’il existe plusieurs programmes malveillants ayant également ces comportements. En conséquence, aucun détecteur comportemental n’est capable de détecter ces programmes malveillants / The thesis consists in two principal parts: the first one discusses the message for- mat extraction and the second one discusses the behavioral obfuscation of malwares and the detection. In the first part, we study the problem of “binary code coverage” and “input message format extraction”. For the first problem, we propose a new technique based on “smart” dynamic tainting analysis and reverse execution. For the second one, we propose a new method using an idea of classifying input message values by the corresponding execution traces received by executing the program with these input values. In the second part, we propose an abstract model for system calls interactions between malwares and the operating system at a host. We show that, in many cases, the behaviors of a malicious program can imitate ones of a benign program, and in these cases a behavioral detector cannot distinguish between the two programs

Le but de cette thèse est de trouver des modèles de haut niveau dans lesquelles l'auto-modification s'exprime facilement. Une donnée est lisible et modifiable, alors qu'un programme est exécutable. On décrit une machine abstraite où cette dualité est structurellement mise en valeur. D'une part une zone de programmes contient tous les registres exécutables, et d'autre part une zone de données contient les registres lisibles et exécutables. L'auto-modification est permise par le passage d'un registre d'une zone à l'autre. Dans ce cadre, on donne une abstraction de l'exécution de la machine qui extrait seulement les informations d'auto-modification. Logiquement, on essaye de trouver une correspondance de Curry-Howard entre un langage avec auto-modification et un système logique. Dans ce but on construit une extension de lambda-calcul avec termes gelés, c'est à dire des termes qui ne peuvent se réduire. Ces termes sont alors considérés comme des données, et les autres sont les programmes. Notre langage a les propriétés usuelles du lambda-calcul (confluence). D'autre part, on donne un système de types dans lequel un sous ensemble des termes du langage peuvent s'exprimer. Ce système est inspiré de la Logique Linéaire, sans gestion des ressources. On prouve que ce système de types a de bonnes propriétés, comme celle de la réduction du sujet. Finalement, on étend le système avec les continuations et la double négation, dans un style à la Krivine / The goal of my Ph.D. is to finds high level models in which self-modification can be expressed. What is readable and changeable is a data, and a program is executable. We propose an abstract machine where this duality is structurally emphasized. On one hand the program zone beholds registers which can be executed, and on the other hand data zone contains readable and changeable registers. Self-modification is enabled by passing a data register into program zone, or a program register into data zone. In this case, we give an abstraction of executions which only extracts information about self-modifications: execution is cut into paths without self-modification. For the logical part, we tried to find a Curry-Howard correspondence between a language with self-modifications and logical world. For that we built an extension of lambda-calculus with frozen terms, noted <t>, that is, terms which cannot reduce. This terms are considered as data. Other terms are programs. We first prove that this language as expected properties like confluence. On the other hand, we found a type system where a subset of terms of this language can be expressed. Our type system is inspired by Linear Logic, without resources management. We prove that this system has good properties like subject reduction. We finally have extended the system with continuation and double negation. This extension can be expressed in a krivine style, using a machine inspired by krivine machine