Formalisation and analysis of Dalvik bytecode

• We present a study of language features used in 1700 Android apps.
• We formalise the semantics of the Dalvik bytecode language.
• We formally specify a control flow analysis for the Dalvik bytecode language.
• We also formalise reflection both in semantics and analysis.
• A prototype implementation of the analysis is discussed.

With the large, and rapidly increasing, number of smartphones based on the Android platform, combined with the open nature of the platform that allows “apps” to be downloaded and executed on the smartphone, misbehaving and malicious (malware) apps are set to become a serious problem. To counter this problem, automated tools for analysing and verifying apps are essential. Furthermore, to ensure high-fidelity of such tools, it is essential to formally specify both semantics and analyses.In this paper we present, to the best of our knowledge, the first formalisation of the complete Dalvik bytecode language including reflection features and the first formally specified control flow analysis for the language, including advanced control flow features such as dynamic dispatch, exceptions, and reflection. To determine which features to include in the formalisation and analysis, 1700 Android apps from the Google Play app market (formerly known as Android Market) were downloaded and examined.