Evaluation Strategies for Datalog-based Points-To Analysis

Abstract

During the last decade, several hard problems have been described and solved in Datalog in a sound way (points-to analyses, data web management, security, privacy, and trust). In this work, we describe novel evaluation strategies for this language within the context of program analyses. We first decompose any Datalog program into a program where rules have at most two atoms in their body. Then, we show that a specialized bottom-up evaluation algorithm with time and memory guarantees can be described as the on-the-fly resolution of a Boolean Equation System (Bes). The resolution computes all ground atoms in an efficient way thanks to a compact data structure with constant time access that has so far not been used in the Datalog or the Bes literature. A prototype has been developed and tested on a number of real Java projects in the context of Andersen’s points-to analysis. Experimental results show that our prototype is better than state-of-the-art solvers in terms of resolution time and memory consumption.