{CtChecker}: A Precise, Sound and Efficient Static Analysis for Constant-Time Programming

Quan Zhou, Sixuan Dang, Danfeng ZhangEcoop 2024 · DOI

TL;DR

This paper introduces CtChecker, a novel static analysis tool designed to automatically detect timing channel vulnerabilities in constant-time programming. By employing a precise, sound, and efficient information flow analysis with advanced features like field-sensitivity and context-sensitivity, CtChecker significantly reduces false positives compared to existing tools, making it a practical solution for securing cryptographic systems.

What Problem Does This Paper Address?

Modern cryptographic systems are increasingly vulnerable to timing channel attacks, where attackers exploit the time it takes for a program to execute to infer sensitive information, such as private keys. A common defense is the "constant-time programming" discipline, which aims to ensure that program execution time doesn't depend on secret data. However, manually enforcing this discipline is tedious and error-prone. Existing automated tools for detecting timing violations often struggle to balance precision (accurately identifying vulnerabilities), soundness (guaranteeing no false negatives), and efficiency (completing analysis in a reasonable time). This paper addresses the critical need for a tool that can achieve all three, particularly for complex real-world cryptographic code.

Methods

CtChecker is built upon a static information flow analysis framework that leverages Program Dependence Graphs (PDGs). Its core innovation lies in enhancing a baseline analysis with several key features:

  • Field-Sensitivity: The analysis can distinguish between different fields within a data structure, preventing over-tainting when only public fields are accessed.
  • Context-Sensitivity: The analysis considers different calling contexts of functions to improve precision.
  • Flow-Sensitivity: By utilizing LLVM's Static Single Assignment (SSA) form and the mem2reg pass, CtChecker can track how values change over time, reducing false positives caused by re-used variables.
  • Declassification: A whitelisting mechanism allows users to explicitly mark certain variables (e.g., key sizes) as harmless, preventing them from triggering false positives.
  • Sound Points-to Analysis: CtChecker uses a sound points-to analysis (specifically DSA) to accurately track memory accesses, which is crucial for soundness but can also be a source of imprecision.

The tool targets LLVM Intermediate Representation (IR), allowing it to analyze code written in various source languages.

Datasets

The paper evaluates CtChecker on two sets of benchmarks:

  1. Cryptographic Libraries: Code from four popular libraries (BearSSL, Libgcrypt, mbedTLS, and OpenSSL), focusing on their modular exponentiation implementations. This includes both full source code and minimal essential code for analysis.
  2. Rewritten Code: Code automatically generated by the Constantine [7] constant-time rewriter. This benchmark is used to test CtChecker's ability to find vulnerabilities missed by other tools, even in supposedly repaired code.

No new benchmarks were introduced; instead, existing codebases and rewritten code were utilized.

Key Insights and Ideas

  • Feature Synergy is Key: While individual features like field-sensitivity or declassification offer improvements, their combination in CtChecker leads to a significant reduction in false positives (67.6% overall).
  • Soundness vs. Precision Trade-off: The paper highlights that while sound points-to analysis is essential for correctness, it can be a major source of imprecision (false positives) due to over-approximation, especially when dealing with collapsed memory nodes or aliasing.
  • PDG-based Analysis Shines: The authors found that Program Dependence Graph (PDG)-based information flow analysis offers a better trade-off between precision and performance compared to logic-based formal verification (like ct-verif) or abstract interpretation (like CacheS).
  • Rewriters Aren't Perfect: CtChecker revealed that some code rewritten by tools like Constantine to eliminate timing channels still contained vulnerabilities, underscoring the need for robust verification.
  • LLVM's Role: Leveraging LLVM's IR and passes like mem2reg is crucial for achieving flow-sensitivity and improving analysis precision.

Key Results

  • Precision Improvement: CtChecker achieved a significant reduction in false positives, with an overall reduction of 67.6% compared to its baseline analysis.
  • Efficiency: CtChecker analyzes large codebases (up to 24K LOC) in under a minute, demonstrating its efficiency.
  • Comparison with ct-verif: CtChecker was found to be both more precise and more efficient than ct-verif, a sound logic-based verifier.
  • Comparison with CacheS and SC-Eliminator: CtChecker reported comparable or fewer positives than these tools, while maintaining soundness, unlike CacheS's unsound memory model and SC-Eliminator's lack of points-to analysis.
  • False Positives Analysis: The majority of false positives were attributed to imprecision in the underlying sound points-to analysis (DSA), followed by context-insensitivity and flow-insensitivity.

Limitations and Future Work

  • Points-to Analysis Imprecision: The paper acknowledges that the sound points-to analysis (DSA) is a primary source of remaining false positives, particularly due to collapsed memory nodes and aliasing.
  • Context-Insensitivity for Calls: When a callee function is invoked multiple times with different arguments, CtChecker's current context-sensitive analysis creates a single context, leading to aliasing and potential false positives.
  • Flow-Insensitivity for Memory: While LLVM's mem2reg helps with flow-sensitivity for registers, memory accesses involving GEPs remain flow-insensitive.

Future work suggested includes:

  • Investigating more precise points-to analyses to reduce collapsed memory nodes and improve context-sensitivity.
  • Developing strategies for selective inlining of functions to address context-insensitivity issues without sacrificing scalability.
  • Exploring techniques to improve flow-sensitivity for memory accesses.

Summary updated

BibTeX
@inproceedings{zhou2024ctchecker,
  author = {Quan Zhou and Sixuan Dang and Danfeng Zhang},
  title = {{\{CtChecker\}: A Precise, Sound and Efficient Static Analysis for Constant-Time Programming}},
  booktitle = {Ecoop},
  year = {2024},
  doi = {10.4230/lipics.ecoop.2024.46},
}
Figure