Desyan : A Platform for Seamless Value-Flow and Symbolic Analysis CCS: TBD
Panagiotis Diamantakis, Thanassis Avgerinos, Yannis Smaragdakis · 2025
Read Desyan : A Platform for Seamless Value-Flow and Symbolic Analysis CCS: TBD by Panagiotis Diamantakis, Thanassis Avgerinos, Yannis Smaragdakis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-00508.txt.
Introduction
Panagiotis Diamantakis, Thanassis Avgerinos, and Yannis Smaragdakis present Desyan, a platform that merges two classic styles of program analysis. Their paper appeared in 2025. For twenty years the field has split between value-flow analysis, which tracks how data moves, and symbolic analysis, which reasons about possible values. Each thrives alone, but no shared platform joined them well. Desyan builds on a fast Datalog engine and adds full constraint solving with leading solvers.
Built-in constructs handle the patterns analysts meet most, and the design stays neutral about which solver runs underneath. A native algebraic module also supports symbolic reasoning inside the Datalog style. The authors report the result matches the best Datalog evaluators on their home ground while adding symbolic power. The platform aims to make hybrid analyses routine rather than heroic.
Catalog record
| CREATOR | Panagiotis Diamantakis, Thanassis Avgerinos, Yannis Smaragdakis |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-00508
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Desyan : A Platform for Seamless Value-Flow and Symbolic Analysis CCS: TBD Panagiotis Diamantakis, Thanassis Avgerinos, Yannis Smaragdakis Abstract . Over the past two decades, two different types of static analyses have emerged as dominant paradigms both in academia and industry: value-flow analysis (e.g., data-flow analysis or points-to analysis) and symbolic analysis (e.g., symbolic execution). Despite their individual successes in numerous application fields, the two approaches have remained largely separate; an artifact of the simple reality that there is no broadly adopted unifying platform for effortless and efficient integration of symbolic techniques with high-performance data-flow reasoning. To bridge this gap, we introduce Desyan : a platform for writing program analyses with seamless integration of value-flow and symbolic reasoning. Desyan expands a production-ready Datalog fixpoint engine (Soufflé) with full-fledged SMT solving invoking industry-leading SMT engines. Desyan provides constructs for automatically (and efficiently!) handling typical patterns that come up in program analysis. At the same time, the integration is agnostic with respect to the solving technology, and supports Datalog-native symbolic reasoning, via a bottom-up algebraic reasoning module. The result is an engine that allows blending different kinds of reasoning, as needed for the underlying analysis. For value-flow analysis, the engine is the best-in-class Datalog evaluator (often by a factor of over 20x in execution time); for applications that require full SMT (e.g., a concolic execution engine or other symbolic evaluator that needs to solve arbitrarily complex conditions), the engine is leveraging the leading SMT solvers; for lightweight symbolic evaluation (e.g., solving simple conditionals in the context of a path-sensitive analysis), the engine can use Datalog-native symbolic reasoning, achieving large speedups (often of over 2x) compared to eagerly appealing to an SMT solver. 1. Introduction Static program analysis and verification (or just program analysis in our context) features an enormous variety of approaches, using different formal tools, conceptual techniques, and implementation platforms. There is little similarity, in concept and in realization, between pointer analysis ( PGL-014 ) , symbolic execution ( mattmight:King:1976:Symbolic ; godefroid2005dart ) , software model checking ( DBLP:journals/csur/JhalaM09 ) , and other sub-fields. In the last two decades, in pointer analysis (and other closely related flow analyses , such as taint analysis) a dominant trend has emerged and driven much progress in developing new approaches ( aplas/WhaleyACL05 ; DBLP:conf/pldi/MadsenYL16 ; DataDriven2017 ; DBLP:conf/pldi/SzaboEB21 ; madsen13javascript ; DataDriven2018 ; chord ; oopsla/BravenboerS09 ; 10.1145/2594291.2594327 ; Hybrid ; Introspective ; pldi/NaikAW06 ; aplas/LivshitsWL05 ) . The trend consists of specifying the analysis declaratively, typically in a variant of the Datalog language. The declarative specification allows expressing an analysis concisely, easily identifying its essence and variation points. At the same time, high-performance Datalog engines (initially the proprietary LogicBlox ( Aref:2015:DIL:2723372.2742796 ) , later the open-source Soufflé ( Jordan16 ) and several research tools that it inspired ( DBLP:conf/pldi/SzaboEB21 ; DBLP:conf/pldi/MadsenYL16 ) ) have ensured that the high-level specification becomes a highly-efficient implementation, often handily out-performing hand-coded alternatives ( oopsla/BravenboerS09 ) . Given that flow analysis has found an elegant, unifying platform, it is tempting to add more kinds of program analysis to the same platform. A single platform enables blending flow analysis with different approaches in a unified analysis algorithm. Further, it helps reap some of the same conciseness benefits in specifying analyses. Symbolic execution is a prime candidate for blending with flow analysis. Both techniques have found application to similar kinds of programs—often large, general-purpose imperative programs. (This is in contrast to, for instance, software model checking, which has mostly found application to distributed and concurrent programs, with emphasis on the complexity of non-deterministic interactions.) Analysis techniques that use both value-flow reasoning and symbolic reasoning can be highly profitable, with recent examples, such as Scuba ( DBLP:conf/aplas/FengWDD15 ) (which leverages SMT solving in order to summarize functions for points-to reasoning) and symbolic value-flow analysis ( symvalic ) (which has a value-flow analysis structure but manipulates symbolic expressions). In this work, we present Desyan : an approach to blending symbolic reasoning and value-flow reasoning seamlessly in a single high-performance platform. Desyan extends Soufflé, the most-used, highest-performance Datalog engine, with (a) functors that invoke an SMT solver, and (b) a native Datalog symbolic reasoning library. (Each solver has its benefits in different kinds of symbolic reasoning and both can be used interchangeably or mixed at will—e.g., one for small expressions, one for larger, both in the same analysis.) The Desyan extensions attempt to make the life of an analysis designer easier, when interfacing with an SMT solver. They include rewrites to automatically introduce SMT idioms that achieve high efficiency: expressing equality bindings via let-expressions and expressing “bound variables” with an inexpensive form of universal quantification (a pseudo-quantifier forall* ). The result is a platform that can be used to express cutting-edge program analysis algorithms declaratively. Flow analyses—the leading domain of declarative program analysis—are straightforward. If they are already coded in Soufflé, they run unmodified—no change in the language or evaluation semantics is required—since Desyan is just a Soufflé extension using the standard functor machinery. Appealing to a symbolic solver is similarly seamless, with either the native Datalog solver or the external-calling SMT functors. We demonstrate each of the approaches with a declarative symbolic execution engine, an adaptation of symbolic value-flow (symvalic) ( symvalic ) analysis to Desyan , and a regular points-to analysis implementation. In outline, the main contributions of the Desyan work are: \bullet the seamless integration of SMT reasoning in a leading-edge, industrial-strength Datalog engine; \bullet the automatic customization of SMT queries for common program analysis tasks; \bullet the introduction of a Datalog-native “lightweight” symbolic reasoning engine that can serve as a predictable alternative to SMT for simple queries; \bullet the study of the trade-offs of these approaches, for different styles of program analyses. In experimental terms, the integration with an industrial-strength engine yields speedups of over 7-26x on average (for different configurations along the compiled/interpreted, single-/multi-threaded axes); the Datalog-native symbolic reasoning engine achieves a 1.63x speedup over a large collection of inputs; the use of SMT solving enables reasoning that is simply impossible through other means. In total, these elements make for arguably the most powerful platform (as a combination of both expressiveness and efficiency) for program analysis implementation and a model of how to use it. The platform is fully open-source enabling unconstrained further development. 2. Background The declarative specification of program analysis algorithms has gained tremendous ground in the past two decades ( aplas/WhaleyACL05 ; DBLP:conf/pldi/MadsenYL16 ; DataDriven2017 ; DBLP:conf/pldi/SzaboEB21 ; madsen13javascript ; DataDriven2018 ; chord ; oopsla/BravenboerS09 ; 10.1145/2594291.2594327 ; Hybrid ; Introspective ; pldi/NaikAW06 ; aplas/LivshitsWL05 ) . The specification typically takes the form of Datalog rules, although the Datalog language is far from standardized and its different variants offer distinct features and portability challenges ( porting-doop ) . Effectively, the term “Datalog” has come to stand for any language with Prolog-like syntax and strictly declarative semantics (i.e., reorderings of clauses inside rules and of rule evaluation do not affect the result, unlike Prolog). A Datalog rule is simply a list of head predicates instances that are derived every time the predicates in the rule body can be simultaneously instantiated. For instance, the rule: HeadA ( x, y ), HeadB ( x, w, z ) \leftarrow Body1