- Recently, a new type of mobile malware applications with self-updating capabilities was found on the official Google Android marketplace. Malware applications of this type cannot be detected using the standard signatures approach or by applying regular static or dynamic analysis methods. In this paper we first describe and analyze this new type of mobile malware and then present a new network-based behavioral analysis for identifying such malware applications. For each application, a model representing its specific traffic pattern is learned locally on the device. Machine-learning methods are used for learning the normal patterns and detection of deviations from the normal application's behavior. These methods were implemented and evaluated on Android devices.