Description du sujet de thèse

Missions :
A fundamental result in computer science (computability) asserts that undecidable problems exist, meaning that no algorithm can provide a solution for them. This is a significant theoretical limitation, as it proves that some computational problems cannot be solved using an automated method.

A classic example of an undecidable problem—which will be studied in this thesis—is determining whether two programs compute the same result. This subject requires expertise in both compilation and artificial intelligence.
How can one tackle an undecidable problem? The pragmatic approach is to accept occasional errors. A program attempting to solve an undecidable problem may work correctly for some instances while producing incorrect results for others. It is also crucial to minimize the occurrence of incorrect computations. Neural networks are particularly suitable for this application because they inherently compute results with a margin of error.
Specifically, this thesis aims to develop a tool using neural networks to recognize what a program computes. Although automatic program recognition is undecidable, it remains a fundamental challenge in computer science with many applications, including reverse engineering, code compilation and optimization, security analysis, and malware detection. Identifying whether a program computes a specific function is a practical concern. Research efforts have been made to recognize programs algorithmically.
Activities :
This thesis addresses the problem of program recognition with a novel and non-intuitive approach. Artificial intelligence, a field rooted in mathematics and computer science, has proven effective in tasks such as image, speech, and text recognition, as well as human-machine interactions. We intend to apply a similar approach to our undecidable problem. Our initial methods will leverage neural networks. The research will involve the following steps:
1. Identifying an appropriate representation for program semantics: graphs (data dependencies, SSA) or text (functional representation, imperative program).
2. Generating multiple variants of a given program through compilation and training a neural network on them.
3. Evaluating whether and to what extent the neural network can recognize other variants of the same program.
4. Analyzing failure cases and investigating possible explanations.

Contexte de travail

The PhD student will join the KAIROS team, a joint team between the i3S laboratory (CNRS / Université Côte d'Azur) and the Centre Inria d'Université Côte d'Azur. This thesis will contribute to the ANR research project MLOpt and the INRIA exploratory action ProgReco.
The i3S laboratory, founded in 1989, conducts research in computer science. With a staff of nearly 300, including professors and researchers from the Université Côte d'Azur, CNRS and Inria researchers, administrative and technical staff, doctoral students and trainees, it is one of the largest public laboratories on the Côte d'Azur and was one of the first to be established in the Sophia Antipolis technology park.
Skills :
The candidate must hold a Bachelor's and Master's degree in Computer Science from a French or European university, with strong academic performance in fundamental subjects such as compilation and theoretical computer science. The PhD student should demonstrate autonomy, a strong willingness to delve into research topics, the ability to overcome technical challenges, and the capability to write scientific documents in English (articles, reports). Delivering a software prototype is also expected. The research requires continuous rigor and effort throughout the thesis.
A research internship in computer science in a laboratory in France or Europe.
Possible additional remuneration for teaching at Université Côte d'Azur.

Application form :
Interested candidates must enclose the following documents:
- detailed CV
- letter of motivation
- Copies of diplomas
- Copies of transcripts from the baccalaureate onwards

Contraintes et risques

None