TechPrufer
Get started
Two Sigma
Two Sigma logoTwo Sigma · Feature trail

DPLL(T) String Solvers

1 post · Jul 2017

What this trail covers

Two Sigma is developing capabilities in formal verification and security applications by enhancing the scalability and efficiency of string solvers. This involves developing and implementing advanced techniques, such as context-dependent simplification, within SMT solvers like CVC4. The goal is to improve the ability to reason about complex string constraints arising from real-world problems, particularly in symbolic execution for security analysis.

All Two Sigma trails
  1. Scaling Up DPLL(T) String Solvers Using Context-Dependent SimplificationThis post introduces a novel context-dependent simplification technique for DPLL(T) string solvers. This technique significantly improves the scalability of string solvers on challenging constraints derived from real-world security and verification applications. An implementation in the SMT solver CVC4 demonstrates superior performance compared to state-of-the-art string solvers on benchmarks generated by PyEx, a symbolic execution engine for Python programs. The evaluation shows a substantial reduction in runtime and comparable program coverage.