Title: Certificate Enhanced Data-Flow Analysis,
Abstract: Proof-carrying-code was proposed as a solution to ensure a trust relationship
between two parties: a (heavyweight) analyzer and a (lightweight) checker. The
analyzer verifies the conformance of a given application to a specified
property and generates a certificate attesting the validity of the analysis
result. It suffices then for the checker just to test the consistency of the
proof instead of constructing it. We set out to study the applicability of this
technique in the context of data- flow analysis. In particular, we want to know
if there is a significant performance difference between the analyzer and the
checker. Therefore, we developed a tool, called DCert, implementing an
inter-procedural context and flow-sensitive data-flow analyzer and checker for
Android. Applying our tool to real-world large applications, we found out that
checking can be up to 8 times faster than verification. This important gain in
time suggests a potential for equipping applications on app stores with
certificates that can be checked on mobile devices which are limited in
computation and storage resources. We describe our implementation and report on
experimental results.