A wise and handsome guy.

Fan Long

Assistant Professor

Department of Computer Science, University of Toronto Bahen Centre for Information Technology, BA3250
416-978-6055

fanl at cs dot toronto dot edu

About

My research interests are programming language, software engineering, systems security, and blockchain. I am involved in the Conflux project for building the next generation blockchain platform.

Useful Links: Google Scholar page, and Automatic Patch Generation project website.

News

  • Our automatic horizontal kernel fusion paper is accepted by CGO 2022!

  • Welcome to my new homepage! My old homepage at MIT CSAIL is no longer maintained.

Research Projects


Blockchain Scalability

Conflux DAG

Following the success of the cryptocurrencies, blockchain has recently evolved into a technology platform that powers secure, decentralized, and consistent transaction ledgers at Internet-scale. However, the performance bottleneck remains one of the most critical challenges of current blockchains. In the standard Nakamoto consensus, the performance is bottlenecked by the facts 1) that only one participant can win the competition and contribute to the blockchain, i.e., concurrent blocks are discarded as forks, and 2) that the slowness is essential to defend against adversaries. For example, Bitcoin generates one 1MB block every 10 minutes and can therefore only process 7 transactions per second. The insufficient throughput and long confirmation delay severely limit the adoptions of blockchain techniques, causing poor user experience, congested network, and skyrocketing transaction fees.

Conflux: Conflux is a new fast, scalable, and decentralized blockchain system that can process thousands of transactions per second while confirming each transaction in minutes. Conflux records additional informations between blocks and organizes generated blocks into direct acyclic graphs. The core of Conflux is its consensus protocol that allows multiple participants to contribute to the Conflux blockchain concurrently (i.e., processing transactions in all concurrent blocks) while still being provably safe. See the Conflux project website for more information.

Shrec: Shrec is a novel transaction relay protocol for high-throughput blockchain systems built around a hybrid transaction hashing scheme that has a low hash collision rate, is resilient to collision attacks, and is fast to construct. Shrec reduces the bandwidth consumption by 60% at modest CPU overhead and improves the system throughput by up to 90%.

Gosig: Gosig is a scalable Byzantine consensus protocol for consortium blockchains. Gosig uses transmission pipelining to fully utilize the network bandwidth and uses aggregated signature gossip to reduce the number of messages. It can scale up to 5000 nodes while still maintaining the throughput of 3000 transactions per second.


Smart Contract Security

Smart Contract

Smart contract is a program that encodes a set of transaction rules. Once deployed to a blockchain, its encoded rules are enforced by all participants of the blockchain network, and therefore it eliminates counterparty risks in sophisticated transactions. Unfortunately, like other programs, smart contracts may contain errors. Errors inside smart contracts often lead to significant financial losses in the real world.

Solythesis: Solythesis is a source-to-source runtime validation tool for Solidity. Its design is based on the observation that smart contract execution is not the performance bottleneck of blockchain systems. The overhead of runtime validation, which is often too expensive for other domains, is in fact negligible for smart contracts.


Automatic Patch Generation

Patch Generation

Software defects are pervasive in software systems and can cause undesirable user experience, denial of service, or even security exploitation. Generating a patch for a defect is a tedious, time-consuming, and often repetitive process. Automatic patch generation techniques holds out the promise of automatically correcting software defects without the need for human developers to diagnose, understand, and correct these defects. To learn more, please visit our project website!

Prophet: Prophet is the state-of-art generate-and-validate patch generation system for C programs. It is the first system that uses machine learning techniques to learn from past successful human patches to recognize and predict correct patches for new errors.

SPR: SPR is the baseline system on which Prophet is built. It uses the condition synthesis technique to explore its search space up to two magnitude faster.

CodePhage: CodePhage systematically transfers useful security checks from a donor application to eliminate bugs and security vulnerabilities in a recipient application. It is the first system that transfers useful code across applications. It does not even require the source code of the donor application!


Input Filtering and Rectification

Input Filter and Rectification

What if we cannot change the source code of an application? Let's look at the inputs of the application. We can make sure that malicious input cannot reach the application, i.e., filter them or rectify them.

SIFT: SIFT is a sound input filter system with sophisticated program analysis techniques. It guarantees to filter out all malicious inputs that trigger critical integer overflow errors. In practice, it also has zero to negligible false positives.

SOAP: SOAP is the first automatic input rectification system. It enforces a set of inferred invariants on the inputs so that potentially malicious inputs are transformed to benign inputs.


Program Recovery

Program Recovery

What if an application crashes during its execution and we only have its binary? We can use our recovery shepherding technique to enable the application to survive the error triggering input unit and recovers its execution.

RCV: RCV is a lightweight program recovery tool with negligible overhead during normal execution. When a crash error (null-dereference and/or divide-by-zero) occurs, it systematically guides the application execution to survive the error triggering input unit. It also tracks how the error propagates in the application and waits until the error is flushed away after the program moves to the next input unit. Instead of crash and getting nothing, you can get part or all of your desired results.

Publications


  1. PipeZK: Accelerating Zero-Knowledge Proof with a Pipelined Architecture [pdf]
    Ye Zhang, Shuo Wang, Xian Zhang, Jiangbin Dong, Xingzhong Mao, Fan Long, Cong Wang, Dong Zhou, Mingyu Guo, Guangyu Sun
    ISCA 2021

  2. Smart Contract Refinement for Gas Optimization [pdf]
    Keerthi Nelaturu, Sidi Mohamed Beillahi, Fan Long, Andreas Veneris
    BRAIN 2021

  3. Shrec: Bandwidth-Efficient Transaction Relay in High-Throughput Blockchain Systems [pdf]
    Yilin Han, Chenxing Li, Peilun Li, Ming Wu, Dong Zhou, and Fan Long
    SoCC 2020

  4. Gosig: A Scalable and High-Performance Byzantine Consensus for Consortium Blockchains [pdf]
    Peilun Li, Guosai Wang, Xiaoqi Chen, Fan Long, and Wei Xu
    SoCC 2020

  5. Engineering Economics in the Conflux Network [pdf]
    Yuxi Cai, Fan Long, Andreas Park, and Andreas Veneris
    IEEE BRAIN 2020

  6. A Decentralized Blockchain with High Throughput and Fast Confirmation [pdf]
    Chenxing Li, Peilun Li, Dong Zhou, Zhe Yang, Ming Wu, Guang Yang, Wei Xu, Fan Long, and Andrew Chi-Chih Yao
    USENIX ATC 2020

  7. Securing Smart Contract with Runtime Validation [pdf]
    Ao Li, Jemin Andrew Choi, and Fan Long
    PLDI 2020

  8. Automatic Patch Generation via Learning from Successful Human Patches [pdf]
    Fan Long
    PhD Thesis

  9. Automatic Inference of Code Transforms for Patch Generation [pdf slides artifact]
    Fan Long, Peter Amidon, and Martin Rinard
    FSE 2017

  10. CodeCarbonCopy [pdf]
    Stelios Sidiroglou-Douskos, Eric Lahtinen, Anthony Eden, Fan Long, and Martin Rinard
    FSE 2017


  11. An Analysis of the Search Spaces for Generate and Validate Patch Generation Systems [pdf slides artifact]
    Fan Long and Martin Rinard
    ICSE 2016

  12. Automatic Patch Generation by Learning Correct Code [pdf slides artifact]
    Fan Long and Martin Rinard
    POPL 2016


  13. Control Jujutsu: On the Weaknesses of Fine-Grained Control Flow Integrity [pdf slides]
    Isaac Evans, Fan Long, Ulziibayar Otgonbaatar, Howard Shrobe, Martin Rinard, Hamed Okhravi, and Stelios Sidiroglou-Douskos
    CCS 2015

  14. Staged Program Repair with Condition Synthesis [pdf slides artifact]
    Fan Long and Martin Rinard
    ESEC-FSE 2015

  15. An Analysis of Patch Plausibility and Correctness for Generate-And-Validate Patch Generation Systems [pdf artifact]
    Zichao Qi, Fan Long, Sara Achour, and Martin Rinard
    ISSTA 2015

  16. Automatic Error Elimination by Multi-Application Code Transfer [pdf]
    Stelios Sidiroglou, Eric Lahtinen, Fan Long, and Martin Rinard
    PLDI 2015

  17. Automatic Integer Overflow Discovery Using Goal-Directed Conditional Branch Enforcement [pdf]
    Stelios Sidiroglou, Eric Lahtinen, Nathan Rittenhouse, Paolo Piselli, Fan Long, Doekhwan Kim, and Martin Rinard
    ASPLOS 2015

  18. Principled Sampling for Anomaly Detection [pdf]
    Brendan Juba, Christopher Musco, Fan Long, Stelios Sidiroglou, and Martin Rinard
    NDSS 2015


  19. Automatic Runtime Error Repair and Containment via Recovery Shepherding [ pdf ] [slides]
    Fan Long, Stelios Sidiroglou, and Martin Rinard.
    PLDI 2014

  20. Sound Input Filter Generation for Integer Overflow Errors [ pdf slides]
    Fan Long, Stelios Sidiroglou, Deokhwan Kim, and Martin Rinard.
    POPL 2014


  21. From Natural Language Specifications to Program Input Parsers [ pdf ]
    Tao Lei, Fan Long, Regina Barzilay, and Martin Rinard.
    ACL 2013


  22. Automatic Input Rectification [ pdf ]
    Fan Long, Vijay Ganesh, Michael Carbin, Stelios Sidiroglou, and Martin Rinard.
    ICSE 2012


  23. G2: A Graph Processing System for Diagnosing Distributed Systems. [ pdf ]
    Zhenyu Guo, Dong Zhou, Haoxiang Lin, Mao Yang, Fan Long, Chaoqiang Deng, Changshu Liu, and Lidong Zhou.
    USENIX ATC 2011

  24. Language-based Replay via Data Flow Cut. [ pdf | slides ]
    Ming Wu, Fan Long, Xi Wang, Zhilei Xu, Haoxiang Lin, Xuezheng Liu, Zhenyu Guo, Huayang Guo, Lidong Zhou, and Zheng Zhang.
    FSE 2010

  25. API Hyperlinking via Structural Overlap. [ pdf | slides ]
    Fan Long, Xi Wang, and Yang Cai.
    ESEC-FSE 2009

  26. MODIST: Transparent Model Checking of Unmodified Distributed Systems. [ pdf ]
    Junfeng Yang, Tisheng Chen, Ming Wu, Zhilei Xu, Xuezheng Liu, Haoxiang Lin, Mao Yang, Fan Long, Lintao Zhang, and Lidong Zhou
    NSDI 2009