Application markets offer more than 700'000 applications: music, movies, games or small tools. It appears more and more difficult to propose an automatic and systematic method to analyse all of these applications. Google Bouncer [1] tries to keep malicious applications out of Google Play by analysing uploaded applications to find known malware and malicious behaviours. However, Google Bouncer suffers from the same drawbacks of usual scan methods: it is inefficient to detect unknown malicious be- haviour and it may be costly. In this paper we propose another method to efficiently detect malicious actions of applications. Our proposal consists in a new scheme of submitting applications to market place and installing applications on the device. More precisely, applications are uploaded with a companion information flow policy. A companion policy exactly de- scribes where data used by the application can flow. The policies are studied for acceptance by reviewers. Accepted policies are certified by the market and are made publicly available. When a user acquires an application, he has to retrieve the certified version of its companion flow policy. The companion policy of the application is composed with the current flow policy enforced in the system. The application is then moni- tored and each time the monitor detects an information flow not allowed in the composed flow policy it raises an alert or blocks the information flow. This way, only applications respecting an official policy accepted by the market can efficiently run.
