- In this paper we present a new behavior-based anomaly detection system for detecting meaningful deviations in a mobile application's network behavior. The main goal of the proposed system is to protect mobile device users and cellular infrastructure companies from malicious applications by: (1) identification of malicious attacks or masquerading applications installed on a mobile device, and (2) identification of republished popular applications injected with a malicious code (i.e., repackaging). More specifically, we attempt to detect a new type of mobile malware with self-updating capabilities that were recently found on the official Google Android marketplace. Malware of this type cannot be detected using the standard signatures approach or by applying regular static or dynamic analysis methods. The detection is performed based on the application's network traffic patterns only. For each application, a model representing its specific traffic pattern is learned locally (i.e., on the device). Semi-supervised machine-learning methods are used for learning the normal behavioral patterns and for detecting deviations from the application's expected behavior. These methods were implemented and evaluated on Android devices. The evaluation experiments demonstrate that: (1) various applications have specific network traffic patterns and certain application categories can be distinguished by their network patterns; (2) different levels of deviation from normal behavior can be detected accurately; (3) in the case of self-updating malware, original (benign) and infected versions of an application have different and distinguishable network traffic patterns that in most cases, can be detected within a few minutes after the malware is executed while presenting very low false alarms rate; and (4) local learning is feasible and has a low performance overhead on mobile devices.