Formal Analysis of Language-Based Android Security Using Theorem Proving Approach

Abstract

Mobile devices are an indispensable part of modern-day lives to support portable computations and context-aware communication. Android applications within a mobile device share data to support application operations and better user experience, which also increases security risks to device's data integrity and confidentiality. To analyze the security provided by the Android permissions, modern security techniques, based on the programming languages, have been used to enforce best practices for developing the secure Android applications. Android security assessment, based on the language-based techniques in an informal setting without formal tool support, is tedious and error-prone. Furthermore, the lack of proof of the soundness of the language-based techniques raises questions about the validity of the analysis. To enable computer-aided formal verification in Android security domain, we have developed a mathematical model of language-based Android security using computer-based proof assistant Coq. One of the main challenges for mechanizing the language-based security in theorem prover relates to the complexity of variable bindings in language-based security techniques. As the main contributions of the paper: 1) the language-based security, including variable binding, is formalized in theorem prover Coq; 2) a formal type checker is built to type check (capture safe data flows within) Android applications using computer; and 3) the soundness of the language-based security technique (type system) is mechanically verified. The formal model of the Android type system and their proof of soundness are machine-readable, and their correctness can be checked in the computer using Coq proof and type checkers.

Keywords

• Android security
• formal verification
• language-based security
• locally nameless representation
• machine-readable proofs
• theorem proving