Internships Proposals

The internships should start between February and the end of March 2013 and end at last in September 2013. The monthly wage is around 400 euros/month (negotiable). The ideal candidate must be preparing a Master in Computer Science with some basis in static-analysis, low-level code, computer security and/or cryptography.


Extraction of typing information from binary code

Goal

During this internship we would like the student to get acquainted with our C++ framework, to study the ideas behind the paper [Mycroft] and come up with an implementation transforming a fragment of microcode into SSA (Single Static Assignment) form and inferring from it possible datatypes of the various variables and memory locations manipulated by this fragment.

The Insight framework does not take as given the control flow graph of the program under study, and it is reconstructed on the fly while analyses are being performed. We would like the intern to explore how algorithms can be designed to make the general idea of [Mycroft] work in the case of an evolving control flow graph.

The expected contribution is twofold:

  • a good understanding of the whole inferrence chain and a proposed extension to the evolving control flow graph case
  • an implementation based on the Insight framework and working at least on a small example

References

[Mycroft] Alan Mycroft, Type-Based Decompilation, Lecture Notes in Computer Science: Proc. ESOP'99, vol. 1576. Springer-Verlag, 1999.

Advisors

  • Aymeric Vincent <vincent(at)labri.fr>, LaBRI, office 264, +33 5 4000 3509

Efficient Representation for Self-modifying Code

Self-modifying code is well-known to mislead any attempt to perform static-analysis on it. It is usually used as an obfuscation technique forcing the reverse-engineer to browse and understand manually the program [2].

Recently several attempts have been conducted to detect and represent efficiently self-modifying code for analysis purpose [1,3,4] through abstract interpretation or specific data-structures to represent programs that perform modification of their own code during execution.

The goal of this internship is to investigate the theory underlying self-modifying code and to come with a suitable data-structure to represent self-modifying programs in such a way that usual control-flow and data-flow analysis can still be performed on it as they are (or with a small modification of the algorithms).

This work might be directly applied and tested in the Insight framework on suitable binary program examples.

References

[1] Bertand Anckaert, Matias Madou and Koen De Bosschere: A Model for Self-modifying Code. In Proceedings of the 8th international conference on Information hiding (IH'06), p.232-248, LNCS 4437, Springer, 2006.

[2] Nikos Mavrogiannopoulos, Nessim Kisserli, Bart Preneel: A Taxonomy of Self-modifying Code for Obfuscation. Computers & Security 30(8): 679-691 (2011)

[3] Mila Dalla Preda, Roberto Giacobazzi, Saumya K. Debray, Kevin Coogan, Gregg M. Townsend: Modelling Metamorphism by Abstract Interpretation. SAS 2010:218-235.

[4] Mila Dalla Preda, Roberto Giacobazzi: Semantics-based code obfuscation by abstract interpretation. Journal of Computer Security (JCS) 17(6):855-908 (2009).

Advisors

  • Emmanuel Fleury <fleury(at)labri.fr>, LaBRI, office 261, +33 5 4000 6934

Software Obfuscation based on Fully Homomorphic Encryption

Perfect obfuscation has been told to be impossible since [1], but recent fully homomorphic encryption (FHE) scheme have been discovered with a more suitable size for keys and ciphers [2] (even if there are still not yet practical).

The usual usage of FHE is to conceal data from the user (whitebox cryptography). Imagine that we can provide a universal Turing machine and encode the program of the machine in the data. Our idea is to use FHE to obfuscate the steps of the computation of this machine, thus allowing an obfuscation scheme which will be based on a cryptographic FHE scheme.

The goal of this internship is to investigate, first, what can theoretically done if we assume to have an efficient FHE scheme in matter of cryptographic software obfuscation. And, second, to try to look at an implementation using the existing scheme (explore their limitations and try to test their real security).

[1] Boaz Barak, Oded Goldreich, Russel Impagliazzo, Steven Rudich and Amit Sahai, Salil Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. Journal of the ACM (JACM), volume 59 Issue 2, April 2012, p.1-48, article No.6.

[2] Jean-Sébastien Coron, Adradip Mandal, David Naccache and Mehdi Tibouchi. Fully Homomorphic Encryption over the Integers with Shorter Public Keys. Pages 487-504. In CRYPTO'11, 2011

[3] Craig Gentry. A Fully Homomorphic Encryption Scheme. PhD Thesis, Stanford University, September 2009.

Advisors

  • Emmanuel Fleury <fleury(at)labri.fr>, LaBRI, office 261, +33 5 4000 6934
Last modified 4 years ago Last modified on Dec 4, 2012 5:09:25 PM