Datalog Static Analysis in Secrecy

Abstract

We present a secure static-analysis-as-a-service (SaaaS) system where a client may outsource static analysis to the cloud. To address copyright concerns associated with SaaaS, clients are allowed to encrypt the source code of a target program and upload it to the cloud. Our goal is to secure the privacy of the design and implementation of static analysis as well as the source code of the target program. Considering a family of static analyses written in Datalog, we propose a generic protocol that combines homomorphic encryption (HE) with secure two-party computation to manage the huge cost of HE operations. The server occasionally delegates sub-parts of analysis which are costly in the cipher-world to the client without exposing the design of analysis. During server-client interactions, the information of both sides (client and server) is not leaked to the opposite. We evaluated our system on two static analyses in Datalog in secrecy, which have not been feasible using the previous techniques. For example, Andersen pointer analysis is completed in an average of 45 mins for 14 C programs comprising up to 1.6 KLoC.

Keywords

• Datalog
• homomorphic encryption
• privacy-preserving software-as-a-service
• static analysis
• secure two-party computation