We do research in the design and implementation of programming languages (PL), mathematical models of computation, and computer-assisted formal reasoning, at School of Computing at National University of Singapore.

Our results address software reliability issues that arise in everyday job of software developers. We investigate the theoretical foundations of programming and build tools for ensuring that certain kinds of costly software errors and vulnerabilities never occur in the real-world code, which many people rely upon in their everyday lives.

Our current investigations follow the themes outlined below.

For more details on our research, check out our blog posts, projects, and recent papers.

Theme 1: Trustworthy Distributed Systems

It is hard to overstate the significance and ubiquity of distributed services in many aspects of modern life, such as health care, online commerce, transportation, entertainment and cloud-based applications. Given the importance of distributed software and its complexity, it is vital in industry to have a rigorous verification methodology for establishing its correctness properties, ensuring that, once a distributed system is up and running, it will never go wrong and will eventually complete its goals.

Our recent work has established logical foundations for compositional verification of complex distributed protocols using a proof assistant. We have also produced the first mechanically verified proof of safety of Nakamoto consensus. Our ongoing work builds libraries and techniques for mechanised reasoning about probabilistic properties of distributed protocols and data structures employed by them. In particular, we have produced the first mechanised proof of the false-positive ratio for Bloom filters (see this blog post for more details).

Theme 2: Programming Languages for Distributed Programming

In this line of research we apply core PL techniques, such as semantics, type systems, and abstract interpretation, for building safe and secure decentralised applications.

For instance, in our recent work, inspired by the verification ideas from Theme 1, we have developed a library for compositional construction of distributed protocols, allowing their modular testing and model-checking. By reflecting on the analogy between design principles of secure smart contracts (a particularly prominent class of decentralised applications) and concurrent software (also see the related ACSAC'18 and ISSTA'19 papers), in collaboration with industry partners we have developed Scilla, a functional smart contract language with strong safety guarantees. We have also developed a set of efficient compilation techniques for Scilla as well as a Coq-powered verification methodology for it.

Our ongoing research explores opportunities for (a) developing low-overhead abstractions for automated reasoning about distributed applications and (b) enhancing parallelism offered by modern distributed protocols via programming language techniques.

Theme 3: Program Synthesis and Repair

Program synthesis is an emerging research and technology paradigm for automatically deriving programs from user-provided declarative specifications, thereby significantly reducing the implementation effort required for producing correct-by-construction and efficient code.

Our recent work explored applications of state-of-the-art techniques for analysis, verification, and deductive proofs for fast and expressive program synthesis (check out the papers on SuSLik, and on the grand challenges in deductive synthesis of program with pointers) and for program repair. Our long-term agenda involves synthesis of correct concurrent and distributed programs by adopting our work on static analysis and logical foundations for reasoning about concurrent and distributed systems.