Computing Security Certificates of Android Applications in Cassandra


Cassandra is a tool for checking Android applications against user
specified security policies. Cassandra works by performing a static
information flow analysis that is supported by a soundness result.
Cassandra creates a certificate, which acts as a verifiable proof
that a user specified policy is satisfied by an application.

A problem in the current implementation of the algorithm that
computes certificates is that it does not scale well to larger
applications. To address this problem, a new certification algorithm
was developed and implemented. The new algorithm is based on
constraint solving. Firstly, all dependencies between security
domains of storage locations of a program are collected as
constraints. Secondly, the collected constraints are solved to create
a certificate.

The new algorithm was integrated into Cassandra and evaluated with
respect to its runtime against the existing algorithm. The evaluation
suggests that the new algorithm scales linearly in the size of the
application, while the existing algorithm is of non-linear complexity
in the size of the application. Also, the new algorithm is faster for
all sizes of applications in practice.