Compiler Front End for Aporia

Bachelor or Master Thesis (Scope adjusted according to level)

Supervisor: Ali Ajorian (main), Erick Lavoie (support)

Aporia is a language-based security framework, that enables a set of programs written in high-level languages to become indistinguishable from one another when executed on commodity hardware. This framework currently comprises a new execution model, a runtime environment, and an interpreter that reads programs in a low-level syntax that makes instruction independence easier to achieve. We are looking for a motivated Bachelor or Master student to take on the challenge of designing and implementing a translator/compiler from a widely-used language, such as Python, to our custom low-level syntax. 

Pre-requisites:

• (Mandatory) Good familiarity with the source language (ex: Python)
• (Desirable) Experience with text transformation or writing compilers (successful completion of Seminar on Interpretation and Compilation of Programming Languages definitely a plus!)

References:

• Current draft of "Instruction-Independent Obfuscation" paper available on demand

Run-Time Interleaving for Aporia

Master Thesis 

Supervisor: Ali Ajorian (main), Erick Lavoie (support)

Aporia is a language-based security framework, that enables a set of programs written in high-level languages to become indistinguishable from one another when executed on commodity hardware. This framework currently comprises a new execution model, a runtime environment, and an interpreter that reads programs in a low-level syntax that makes instruction independance easier to achieve. The goal is to modify the interpreter to support adding a new program that was not known at compile-time. This may require modification of the compiler, run-time environment, and interpreter.

Pre-requisites:

• (Desirable) Familiarity C/C++ Linking Process
• (Desirable) Experience with text transformation or writing compilers (successful completion of Seminar on Interpretation and Compilation of Programming Languages definitely a plus!)

References:

• Current draft of "Instruction-Independent Obfuscation" paper available on demand

Trusted-Execution Environment Support for Aporia

Bachelor Thesis, Master Project (12 Credits) or Master Thesis (Scope adjusted according to level)

Supervisor: Ali Ajorian (main), Erick Lavoie (support)

Aporia is a language-based security framework, that enables a set of programs written in high-level languages to become indistinguishable from one another when executed on commodity hardware. This framework currently comprises a new execution model, a runtime environment, and an interpreter that reads programs in a low-level syntax that makes instruction independance easier to achieve. The goal of this project is to modify the current interpreter to use a Trusted Execution Environment for implementing security-critical operations such as randomization of memory layout and address translation.

Pre-requisites:

• (Desirable) Familiarity with C/C++
• (Desirable) Experience with writing compilers and interpreters (successful completion of Seminar on Interpretation and Compilation of Programming Languages definitely a plus!)

References:

• Current draft of "Instruction-Independent Obfuscation" paper available on demand

Software Engineering of Commitment Scheme

Bachelor or Master Thesis (Scope adjusted according to level)

Supervisor: Osman Biçer

Commitment schemes are cryptographic primitives highly useful for blockchain applications, banking systems, and online gambling. They are network system analogs of envelopes used in non-computer real-life settings. The goal of the project will be gaining hands-on experience with cryptographic software engineering by implementing a commitment scheme that can be chosen together with the supervisor. The student will be able to gain experience on cryptographic algorithms and protocols as well as their applications. The programming language can be chosen based on student's skills and desires.

Pre-requisites:

• (Mandatory all levels) Proven background of a low-level programming language such as C, C++, Go, Rust.

References:

• Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: CRYPTO ’91 (1992). [ePrint]

• Di Crescenzo, G., Ishai, Y., Ostrovsky, R.: Non-interactive and non-malleable commitment. In: ACM STOC ’98 (1998). [ACM]

• Jain, A., Krenn, S., Pietrzak, K., Tentes, A.: Commitments and efficient zero-knowledge proofs from learning parity with noise. In: ASIACRYPT ’12 (2012). [ePrint]

• Our work "Oblivious Homomorphic Encryption".

Software Engineering of Fully Homomorphic Encryption Scheme

Bachelor or Master Thesis (Scope adjusted according to level)

Supervisor:  Osman Biçer

Fully Homomorphic Encryption enables outsourcing arbitrary computations on private data. The party that executes the computations obtains the results in encrypted form and returns the owner who can see the result in open form. They are quite promising primitives for cloud applications, particularly useful for medical applications on private patient data, outsourced authentication, etc. The goal of the project will be to gain hands-on experience with cryptographic software engineering by implementing a fully homomorphic encryption scheme that can be chosen together with the supervisor. The student will be able to gain experience on cryptographic algorithms and protocols as well as their applications. The programming language can be chosen based on student's skills and desires.

Pre-requisites:

• (Mandatory all levels) Proven background of a low-level programming language such as C, C++, Go, Rust

References:

• Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) lwe. In: IEEE FOCS ’11 (2011). [ePrint]

• Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (leveled) fully homomorphic encryption without bootstrapping. In: ITCS ’12 (2012). [ePrint]

• Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. In: ASIACRYPT ’16 (2016). [ePrint]

• Our work "Oblivious Homomorphic Encryption".

Adding Pull-based Replication Hooks to Git Core

Bachelor Thesis or Master Project (12 credits)

Supervisor: Erick Lavoie

Git supports hooks, which are scripts invoked during the replication process, to customize the replication behaviour by enforcing that, for example, commits are signed, new commits are descendants of the current HEAD, a committer has the right capabilities to update the references, etc. Unfortunately, certain hooks (ex: pre-receive) are supported on the receiving side of a push but not on the receiving side of a pull. This is because a replica hosted on a trusted platform such as GitHub or GitLab, is usually trusted while the pushers to that replica are not.  However, when using Git in a peer-to-peer setting or when the server cannot be trusted, it would be useful to also validate the updates just pulled with hooks before updating the state of a local repository. The goal of this project is to modify the core library of Git to have the same hooks available when receving a pulled update, as for a pushed update. If the resulting solution is of a high-enough quality, it will be submitted to the Git maintainers for hopefully merging into the official repository.

Pre-requisites:

• (Mandatory Bachelor-level) Completed the equivalent of 2 years
• (Mandatory Master-level) None
• (Mandatory) Familiarity with writing C code or in similar low(er)-level languages

References:

• Git Hooks
• libgit2 [github]
• SSB over Git Tutorial [repo][video]
• P2P Basel Workshop

Optimize the Processing Time and Memory Size of Delta-GOC-Ledger

Bachelor Thesis, Master Project (12 credits), or Master Thesis

Supervisor: Erick Lavoie

Eventually-consistent ledgers relax the usual blockchain requirement that double-spending should be prevented with consensus mechanisms, such as proof-of-work, proof-of-stake, etc., and instead detect the double-spending after it has occurred and later punish the offenders. [1] This relaxation allows crypto-tokens to be implemented with eventually-consistent databases such as Git, Secure-Scuttlebutt [4,5], or others.

The Delta-GOC-Ledger [2] is a novel implementation of an eventually-consistent ledger based on delta-state Conflict-Free Replicated Data Types (CRDTs), with lower communication requirements than the state-based GOC-Ledger [3] it is based on. While robust, the current implementation still has two significant limitations:

1. It relies heavily on Git trees to encode updates, which in turn dominate the storage and communication requirements;
2. It is implemented in Bash, which performs loops very slowly and creates a sub-process for every command executed. 

The goal of the project is to further lower storage and communication requirements by finding an alternative for encoding delta-state updates, possibly using commit messages [2], and lower processing time by re-implementing the key bottleneck operations in a faster language, C or other, up to the preference of the student.

Pre-requisites:

• (Mandatory Bachelor-level) Successful completion of Distributed Programming and the Internet Architecture
• (Mandatory Master-level) Successful completion of Foundations of Distributed Systems

References:

• [1] Lavoie, Erick, and Christian Tschudin. "Local crypto-tokens for local economics." Proceedings of the 3rd International Workshop on Distributed Infrastructure for the Common Good. 2022. [doi][pdf]

• [2] Heisch, Jannick "Delta-GOC-Ledger: Incremental Checkpointing and Lower Message Sizes for Grow-Only Counters Ledgers with Delta-CRDTs", Master Thesis, University of Basel, Apr 2024 [pdf]

• [3] Lavoie, Erick. "GOC-Ledger: State-based Conflict-Free Replicated Ledger from Grow-Only Counters." arXiv preprint arXiv:2305.16976 (2023). [url] [pdf]

• [4] Tarr, Dominic et al. "Secure scuttlebutt: An identity-centric protocol for subjective and decentralized applications" ICN 2019 [DOI]

• [5] Kermarrec et al. "Gossiping with Append-Only Logs in Secure Scuttlebutt", DICG 2020, [DOI]

• P2P Basel Workshop

Decentralized Application Design with Conflict-Free Replicated Data Types

Bachelor Thesis, Master Project (12 credits), or Master Thesis

Supervisor: Erick Lavoie

Centralized applications, such as Twitter/X, Facebook, Dropbox, Messenger, Google Docs, Maps, etc. have become essential services with limited mature alternatives because of network effects, economies of scale, and more than a decade of continuous and well-funded developments. However they are prone to privacy-violation, abuse of market position, and catastrophic failures. Fortunately, the decrease in the cost of storage and the tremendous amount of performance of modern hardware makes it now possible to build alternatives based on decentralized principles with the ability to work offline [5] and without most of the infrastructure costs that are otherwise required for centralized hosting [4].

Conflict-Free Replicated Data Types (CRDTs) [1] are a mathematical framework that simplifies the design and implementation of eventually-consistent applications that must tolerate both concurrent updates and intermittent failures. The goal of this project is to better understand how to design alternatives to centralized applications by using CRDTs to implement the core functionalities of one application among the followings:

1. Any of the previous mentioned (Twitter/X, Facebook, etc.)
2. Archive.org for Backups of the Internet
3. Arxiv.org for Storing and Distributing Pre-prints of Academic Papers
4. BoardGameArena for Remote Multiplayer Boardgames
5. Substack for Optionally-Paid Blogging/Newsletters
6. Podcasting
7. Bulletin-Board System (BBS)
8. Discourse (API)

Any other suggestion, up to the interest of students is welcome!

A high-quality implementation may be promising to later use as a basis for new startups after graduation, using economic models compatible with decentralized designs. [4]

Pre-requisites:

• (Mandatory Bachelor-level) Successful completion of Distributed Programming and the Internet Architecture
• (Mandatory Master-level) Successful completion of Foundations of Distributed Systems
• (Mandatory) Working Knowledge of Discrete Mathematics

References:

• [1] Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski. "Conflict-free Replicated Data Types." SSS 2011 - 13th International Symposium Stabilization, Safety, and Security of Distributed Systems, Oct 2011, Grenoble, France. pp.386-400, ⟨10.1007/978-3-642-24550-3_29⟩. ⟨hal-00932836⟩

• [2] Heisch, Jannick "Delta-GOC-Ledger: Incremental Checkpointing and Lower Message Sizes for Grow-Only Counters Ledgers with Delta-CRDTs", Master Thesis, University of Basel, Apr 2024 [pdf]

• [3] Lavoie, Erick. "GOC-Ledger: State-based Conflict-Free Replicated Ledger from Grow-Only Counters." arXiv preprint arXiv:2305.16976 (2023). [url] [pdf]

• [4] Lavoie, Erick. "Designing Peer-to-Peer Systems as Closed Knowledge Commons." Proceedings of the 4th International Workshop on Distributed Infrastructure for the Common Good. 2023. [doi][pdf]

• [5] Kleppmann, Martin, et al. "Local-first software: you own your data, in spite of the cloud." Proceedings of the 2019 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software. 2019. [doi][pdf]

• P2P Basel Workshop

Modelling and Implementing Peer-to-Peer BoardGame Mechanics

Bachelor Thesis, Master Project (6, 12 credits), or Master Thesis

Supervisor: Erick Lavoie

The mechanics of many boardgames can be modelled as state machines, possibly concurrent, that exhibit issues that distributed programming has to face in general (ex: agreement on the state of the game, coordination of player actions, etc.). Modelling the wide variety of mechanics used in game design has the potential to provide unique insights in reusable abstractions and programming patterns for distributed programming that could be useful for general purpose programming. It also provides engaging applications to apply what you have learned in your studies and recruit your friends to have fun with the code you write!

The following theses have already modelled and implemented Catan (pdf) and Monopoly (pdf). We are looking for more games that use interesting mechanics exhibiting concurrency, i.e. multiple players being able to take actions at the same time, and security/privacy issues, i.e. preventing other players from learning secrets of a player. The models we design and the implementations we do are peer-to-peer, i.e. they only rely on participant devices to implement the mechanics, with servers only helping disseminate messages without implementing any of the game's logic.

Modelling of games is done with TLA+ which is both a language and toolbox, based on the discrete mathematics and logics you most likely have already done in your Computer Science studies. You are not expected to know TLA+ before the project, you will learn it as you go. The TLA+ toolbox contains both a parser, that ensures the mathematical expressions you write are syntactically correct, and a model checker that allows you to quickly find errors in your designs that would otherwise take you days to debug.

Current projects are implemented with Git but any other Peer-to-Peer replication systems are also of interest (including TinySSB, or any active project listed on the P2P Basel webpage). Larger projects, Bachelor and Master Theses are expected to provide both a verified model of the application as well as a working implemention. A smaller project, such as a 6-credit Master Project, can consist of implementing one of our current game models on a platform we have not supported yet, to compare different replication systems on the same set of applications, on programming model, storage usage, communication performance (message size, bandwidth, latency), etc.

Pre-requisites:

• (Mandatory Bachelor-level) Successful completion of Distributed Programming and the Internet Architecture
• (Mandatory Master-level) Successful completion of Foundations of Distributed Systems
• (Mandatory) Working Knowledge of Discrete Mathematics

References:

• TLA+ Learning Material: https://lamport.azurewebsites.net/tla/learning.html (Video may be the most accessible for beginners)
• The Science of Concurrent Programs: https://lamport.azurewebsites.net/tla/science-book.html?back-link=learning.html#science 

Augmented-Reality Chess using Projection Mapping

Bachelor Thesis, Master Project (6, 12 credits), or Master Thesis

Supervisor: Erick Lavoie

Augmented-reality(AR) has the potential of bringing interactive information-processing onto the real-world to provide a more intuitive user experience. Unfortunately, the most commonly-known approaches to AR typically use a headset, such as a Meta Quest or Apple Vision Pro, that breaks the direct connection between users and their physical and social environment in order to inject virtual objects in their visual field. Moreover, the headset are typically uncomfortable for long sessions, and some headsets are quite expensive, with the Vision Pro costing several thousand CHFs.

Dynamicland and Folk Computer, an offshoot by a former participant of Dynamicland, have been experimenting  with Projection Mapping as an alternative, in which a projector overlays real-world objects with images and a camera captures the users' interactions with objects. This removes the need for headsets, does not break the users' connection to their environment, and provides a shared collaborative space by default by tracking the objects being manipulated rather than the users.

Tim Bachmann's Master Thesis has explored the use of Mixed Reality for playing chess using the Apple Vision Pro. The goal of this project is to implement similar functionalities using a portable projector and a mobile phone mounted on a tripod and compare the user experience and potential opportunities and tradeoffs along other dimensions. The object recognition implemented with a fine-tuned YOLO object model as well as the chess engine used to validate moves from Mr. Bachmann project could be reused. The lessons obtained from this project may carry over to other boardgames and serve as a foundation for remote play and the management of automated opponents.

A Bachelor or Master Thesis are expected to provide a full implementation and comparison to the previous work by Mr. Bachmann. A smaller Bachelor or Master Project may focus on providing a proof-of-concept of key technologies.

Pre-requisites:

None

Possible Hardware:

The recent commercial availability of utra-short throw projectors, based on the DLP projectors from Texas Instruments or equivalents, such as the AAXA Technologies M8 , the Philips UL5 Smart or the Touyinger UST01 is making the approach significantly more conventient than previous generations of heavier projectors that required more complicated setups. Moreover, phone cameras with high resolutions can be used as webcams on MacOS and Linux removing the need to buy dedicated high-resolution video cameras.

Optimizing Python-based Git Operations by Compiling Python Operations to C+libgit2

Bachelor Thesis

Supervisor: Erick Lavoie

When implementing applications using higher-level languages such as Python and Git as an eventually-consistent database and replication protocol, the verification of invariants on application messages and the batch processing of Git objects in Python can be quite slow. The goal of this project is to apply compilation techniques to speed up both kinds of operations.

The project will consist in defining a subset of Python with type annotations, that will then be compiled to C and libgit2 operations. Depending on student preference, the result might be called either as a standalone executable or a C python library accessible through the Python Foreign-Function Interface. The evaluation will consist on quantifying the speed-up obtained over a pure Python approach.

Pre-requisites:

• (Mandatory) Successful completion of Seminar on Interpretation and Compilation of Programming Languages 
• (Mandatory) Successful completion of Distributed Programming and Internet Architecture