# Patent

## Title
Methods and systems of using boosted decision stumps and joint feature selection and culling algorithms for the efficient classification of mobile device behaviors

## Abstract

Methods and systems for classifying mobile device behavior include configuring a server use a large corpus of mobile device behaviors to generate a full classifier model that includes a finite state machine suitable for conversion into boosted decision stumps and/or which describes all or many of the features relevant to determining whether a mobile device behavior is benign or contributing to the mobile device's degradation over time. A mobile device may receive the full classifier model and use the model to generate a full set of boosted decision stumps from which a more focused or lean classifier model is generated by culling the full set to a subset suitable for efficiently determining whether mobile device behavior are benign. Boosted decision stumps may be culled by selecting all boosted decision stumps that depend upon a limited set of test conditions.

## Background
RELATED APPLICATIONS
This application claims the benefit of priority to U.S. Provisional Application No. 61/874,129, entitled “Methods and Systems of Using Boosted Decision Stumps and Joint Feature Selection and Pruning Algorithms for the Efficient Classification of Mobile Device Behaviors” filed Sep. 5, 2013, U.S. Provisional Patent Application No. 61/748,217 entitled “On-Device Real-Time Behavior Analyzer” filed Jan. 2, 2013, and U.S. Provisional Patent Application No. 61/748,220 entitled “Architecture for Client-Cloud Behavior Analyzer” filed Jan. 2, 2013, the entire contents of all of which are hereby incorporated by reference.


BACKGROUND
Cellular and wireless communication technologies have seen explosive growth over the past several years. This growth has been fueled by better communications, hardware, larger networks, and more reliable protocols. As a result wireless service providers are now able to offer their customers with unprecedented levels of access to information, resources, and communications.
To keep pace with these service enhancements, mobile electronic devices (e.g., cellular phones, tablets, laptops, etc.) have become more powerful and complex than ever. This complexity has created new opportunities for malicious software, software conflicts, hardware faults, and other similar errors or phenomena to negatively impact a mobile device's long-term and continued performance and power utilization levels. Accordingly, identifying and correcting the conditions and/or mobile device behaviors that may negatively impact the mobile device's long term and continued performance and power utilization levels is beneficial to consumers.
SUMMARY
The various aspects include methods of generating lean behavior classifier models in a mobile device, which may include receiving in a processor of the mobile device a full classifier model that includes a finite state machine, and using the full classifier model to generate a lean classifier model in the mobile device. The finite state machine may include information that is suitable for conversion or expression as a plurality of boosted decision stumps, and each of the boosted decision stumps may include a test condition and a weight value. In an aspect, the method may further include using the lean classifier model in the mobile device to classify a behavior of the mobile device as being either benign or not benign (i.e., malicious, performance degrading, etc.).
In an aspect, generating the lean classifier model based on the full classifier model may include converting the finite state machine included in the full classifier model into a list of boosted decision stumps and generating the lean classifier model based on the boosted decision stumps included in the list of boosted decision stumps.
In an aspect, generating the lean classifier model based on the full classifier model further may include determining a number of unique test conditions that should be evaluated to classify a mobile device behavior without consuming an excessive amount of processing, memory, or energy resources of the mobile device, generating a list of test conditions by sequentially traversing the list of boosted decision stumps and inserting the test condition associated with each sequentially traversed boosted decision stump into the list of test conditions until the list of test conditions may include the determined number of unique test conditions, and generating the lean classifier model to include only those boosted decision stumps that test one of a plurality of test conditions included in the generated list of test conditions.
In an aspect, the method may include using the lean classifier model in the mobile device to classify a behavior of the mobile device as being either benign or not benign by applying collected behavior information to each boosted decision stump in the lean classifier model, computing a weighted average of the results of applying the collected behavior information to each boosted decision stump in the lean classifier model, and comparing the weighted average to a threshold value.
In an aspect, generating the lean classifier model based on the full classifier model may include converting the finite state machine included in the full classifier model into a list of boosted decision stumps, and generating a family of lean classifier models based on the boosted decision stumps included in the list of boosted decision stumps, the family of lean classifier models including the lean classifier model and a plurality of additional lean classifier models, each of the plurality of additional lean classifier models including a different number of unique test conditions.
In an aspect, generating a lean classifier model may include generating a plurality of lean classifier models that each includes a decision stump that tests a first condition using a different weight value and a different threshold value, an aspect, the method may include re-computing threshold values associated with boosted decision stumps in a plurality of lean classifier models generated in the mobile device based on the full classifier model. In an aspect, the method may include re-computing weight values associated with boosted decision stumps in a plurality of lean classifier models generated in the mobile device based on the full classifier model.
In an aspect, the method may include generating the full classifier model in a server by receiving in the server a corpus of information on mobile device behaviors, and generating the finite state machine based on the corpus of information on mobile device behaviors to include data that is suitable for conversion into the plurality of boosted decision stumps, and sending the finite state machine to the mobile device as the full classifier model. In an aspect, each of the plurality of test conditions are associated with a probability value that identifies a likelihood that its associated test condition will enable the mobile device to determine whether a mobile device behavior is benign, the method further including organizing the boosted decision stumps in the finite state machine based on probability values prior to sending the finite state machine to the mobile device as the full classifier model.
Further aspects include a mobile computing device having a processor configured with processor-executable instructions to perform operations of the methods described above.
Further aspects include a non-transitory computer readable storage medium having stored thereon processor-executable software instructions configured to cause a processor in a mobile device to perform operations of the methods described above.
Further aspects include a system, including a mobile device including a device processor, and a server configured with server-executable instructions to perform operations including receiving a corpus of information on mobile device behaviors, generating a finite state machine based on the corpus of information and to include data that is suitable for conversion into a plurality of boosted decision stumps that each includes a test condition and a weight value, and sending the finite state machine to the mobile device as a full classifier model. In an aspect, the device processor may be configured with processor-executable instructions to perform operations including receiving the full classifier model, generating a lean classifier model in the mobile device based on the received full classifier model, and using the lean classifier model to classify a behavior of the mobile device as being either benign or not benign.
In an aspect system, the device processor may be configured with processor-executable instructions to perform operations such that generating the lean classifier model based on the full classifier model includes converting the finite state machine included in the full classifier model into a list of boosted decision stumps, determining a number of unique test conditions that should be evaluated to classify the behavior of the mobile device without consuming an excessive amount of processing, memory, or energy resources of the mobile device, generating a list of test conditions by sequentially traversing the list of boosted decision stumps and inserting the test condition associated with each sequentially traversed boosted decision stump into the list of test conditions until the list of test conditions includes the determined number of unique test conditions, and generating the lean classifier model to include the boosted decision stumps included in the list of boosted decision stumps that test one of a plurality of test conditions included in the generated list of test conditions.
In an aspect system, the device processor may be configured with processor-executable instructions to perform operations such that using the lean classifier model to classify the behavior of the mobile device includes applying collected behavior information to each boosted decision stump in the lean classifier model, computing a weighted average of the results of applying the collected behavior information to each boosted decision stump in the lean classifier model, and comparing the weighted average to a threshold value. In an aspect system, the device processor may be configured with processor-executable instructions to perform operations such that generating the lean classifier model based on the full classifier model includes converting the finite state machine included in the full classifier model into a list of boosted decision stumps, and generating a family of lean classifier models based on the boosted decision stumps included in the list of boosted decision stumps, the family of lean classifier models including the lean classifier model and a plurality of additional lean classifier models, each of the plurality of additional lean classifier models including a different number of unique test conditions.
In an aspect system, the device processor may be configured with processor-executable instructions to perform operations such that generating the lean classifier model based on the full classifier model includes generating a plurality of lean classifier models that each includes a decision stump that tests a first condition using a different weight value and a different threshold value. In an aspect system, the device processor may be configured with processor-executable instructions to perform operations further including re-computing threshold values and weight values associated with the boosted decision stumps in the plurality of lean classifier models.
In an aspect system, the server may be configured with server-executable instructions to perform operations such that each of the plurality of test conditions are associated with a probability value that identifies a likelihood that its associated test condition will enable the mobile device to determine whether a mobile device behavior is benign. In an aspect system, the server may be configured with server-executable instructions to perform operations further including organizing the boosted decision stumps in the finite state machine based on probability values prior to sending the finite state machine to the mobile device as the full classifier model.



BRIEF DESCRIPTION OF THE DRAWINGS
The accompanying drawings, which are incorporated herein and constitute part of this specification, illustrate exemplary aspects of the invention, and together with the general description given above and the detailed description given below, serve to explain the features of the invention.
FIG. 1 is a communication system block diagram illustrating network components of an example telecommunication system that is suitable for use with the various aspects.
FIG. 2 is a block diagram illustrating example logical components and information flows in an aspect mobile device configured to determine whether a particular mobile device behavior is malicious, performance-degrading, suspicious, or benign.
FIG. 3 is a block diagram illustrating example components and information flows in an aspect system that includes a network server configured to work in conjunction with a mobile device to determine whether a particular mobile device behavior is malicious, performance-degrading, suspicious, or benign.
FIG. 4 is a block diagram illustrating example components and information flows in an aspect system that includes a mobile device configured to generate a targeted and lean classifier model from a full classifier model without re-training the data, behavior vectors or classifier models.
FIG. 5A is a process flow diagram illustrating an aspect mobile device method of generating in the mobile device a lean classifier model that includes a subset of the features and data points included in a full classifier model received from a network server.
FIG. 5B is a process flow diagram illustrating another aspect mobile device method of generating a lean classifier model locally in the mobile device.
FIG. 5C is a process flow diagram illustrating an aspect mobile device method of using a locally generated lean classifier model to classify a behavior of the mobile device.
FIG. 5D is a process flow diagram illustrating yet another aspect mobile device method of generating a lean classifier model in the mobile device.
FIG. 6A is a process flow diagram illustrating an aspect network server method of generating in the network server a full classifier model that includes boosted decision stumps that are suitable for use by a mobile device in generating more focused and lean classifier models.
FIG. 6B is a process flow diagram illustrating an example method suitable for generating a boosted decision stump classifier in accordance with various aspects.
FIG. 7 is a process flow diagram of an example method of generating classifier models that include boosted decision stumps in accordance with an aspect.
FIG. 8 is an illustration of example boosted decision stumps that may be generated by an aspect server processor and used by a mobile device processor to generate lean classifier models.
FIG. 9 is a block diagram illustrating example logical components and information flows in an observer module configured to perform dynamic and adaptive observations in accordance with an aspect.
FIG. 10 is a block diagram illustrating logical components and information flows in a computing system implementing observer daemons in accordance with another aspect.
FIG. 11 is a process flow diagram illustrating an aspect method for performing adaptive observations on mobile devices.
FIG. 12 is a component block diagram of a mobile device suitable for use in an aspect.
FIG. 13 is a component block diagram of a server device suitable for use in an aspect.



DETAILED DESCRIPTION
The various aspects will be described in detail with reference to the accompanying drawings. Wherever possible, the same reference numbers will be used throughout the drawings to refer to the same or like parts. References made to particular examples and implementations are for illustrative purposes, and are not intended to limit the scope of the invention or the claims.
The word “exemplary” is used herein to mean “serving as an example, instance, or illustration.” Any implementation described herein as “exemplary” is not necessarily to be construed as preferred or advantageous over other implementations.
In overview, the various aspects include network servers, mobile devices, systems, and methods for efficiently identifying, classifying, modeling, preventing, and/or correcting the conditions and/or mobile device behaviors that often degrade a mobile device's performance and/or power utilization levels over time. A network server may be configured to receive information on various conditions, features, behaviors and corrective actions from a central database (e.g., the “cloud”), and use this information to generate a full classifier model (i.e., a data or behavior model) that describes a large corpus of behavior information in a format or structure that can be quickly converted into one or more lean classifier models by a mobile device.
In an aspect, the full classifier model may be a finite state machine description or representation of the large corpus of behavior information. In an aspect, the finite state machine may include information that is suitable for expression as a plurality of boosted decision stumps. For example, the finite state machine may be an information structure that may be expressed as a family of boosted decision stumps that collectively identify, describe, test, or evaluate all or many of the features and data points that are relevant to determining whether a mobile device behavior is benign or contributing to that mobile device's degradation in performance over time. The network server may then send the full classifier model (i.e., information structure that includes the finite state machine and/or family of boosted decision stumps, etc.) to the mobile device.
The mobile device may be configured to receive and use the full classifier model to generate a lean classifier model or a family of lean classifier models of varying levels of complexity (or “leanness”). To accomplish this, the mobile device may cull the robust family of boosted decision stumps included in the full classifier model received from the network server (herein “full boosted decision stumps classifier model”) to generate a lean classifier model that includes a reduced number of boosted decision stumps and/or evaluates a limited number of test conditions. This culling of the full boosted decision stumps classifier model may be accomplished by: selecting a boosted decision stump; identifying all other boosted decision stumps that depend upon the same mobile device state, feature, behavior, or condition as the selected decision stump (and thus can be applied based upon one determination result); including in the lean classifier model the selected and all identified other boosted decision stumps that depend upon the same mobile device state, feature, behavior, or condition; and repeating the process for a limited number of selected boosted decision stumps not already included in the lean classifier model. In this manner, a lean classifier model may be generated that includes all boosted decision stumps that depend upon a limited number of different mobile device states, features, behaviors, or conditions. The mobile device may then use this locally generated lean classifier model to quickly classify a mobile device behavior without consuming an excessive amount of its processing, memory, or energy resources.
In an aspect, the mobile device may perform the operations of culling the full boosted decision stumps classifier model a number of times using different numbers of different mobile device states, features, behaviors, or conditions in order to generate a family of lean classifier models of different degrees of leanness. The greater the number of different mobile device states, features, behaviors, or conditions used to create the lean classifier model, the more likely the model will accurately identify malicious or suspicious behavior, but the more processing power that will be consumed. Thus, in an aspect, the mobile device may be configured to apply the leanest of the family of lean classifier models (i.e., the model based on the fewest number of different mobile device states, features, behaviors, or conditions) routinely. If the results generated by the most lean classifier model are suspicious, the mobile device processor may apply a stronger (i.e., less lean) classifier model evaluating more device states, features, behaviors, or conditions to determine whether the behavior can identified as malicious or benign. If the results generated by applying that less lean classifier model are still suspicious, an even stronger (even less lean) classifier model may be applied, and so forth until the behavior is definitively classified as malicious or benign.
By storing information on such behaviors and corrective actions in a central database (e.g., the “cloud”), and configuring mobile devices and network servers to work in conjunction with one another to use the information stored in the central database to intelligently and efficiently identify the factors that are contributing to the degradation in performance and power utilization levels of each mobile device over time, the various aspects enable a mobile device to more accurately and efficiently identify and respond to performance-limiting and undesirable operating conditions of the mobile device.
In addition, by generating classifier models that include boosted decision stumps in the network server and sending these classifiers/models to the mobile device, the various aspects allow the mobile device to quickly and efficiently generate lean (or more focused) classifier models in the mobile device by culling the number of boosted decision stumps in the manner described above without accessing training data or further communicating with the network server, the central database, or the cloud network/server. This significantly reduces the mobile device's dependence on the network, and further improves the performance and power consumption characteristics of the mobile device.
A number of different cellular and mobile communication services and standards are available or contemplated in the future, all of which may implement and benefit from the various aspects. Such services and standards include, e.g., third generation partnership project (3GPP), long term evolution (LTE) systems, third generation wireless mobile communication technology (3G), fourth generation wireless mobile communication technology (4G), global system for mobile communications (GSM), universal mobile telecommunications system (UMTS), 3GSM, general packet radio service (GPRS), code division multiple access (CDMA) systems (e.g., cdmaOne, CDMA1020TM), enhanced data rates for GSM evolution (EDGE), advanced mobile phone system (AMPS), digital AMPS (IS-136/TDMA), evolution-data optimized (EV-DO), digital enhanced cordless telecommunications (DECT), Worldwide Interoperability for Microwave Access (WiMAX), wireless local area network (WLAN), Wi-Fi Protected Access I & II (WPA, WPA2), and integrated digital enhanced network (iden). Each of these technologies involves, for example, the transmission and reception of voice, data, signaling, and/or content messages. It should be understood that any references to terminology and/or technical details related to an individual telecommunication standard or technology are for illustrative purposes only, and are not intended to limit the scope of the claims to a particular communication system or technology unless specifically recited in the claim language.
The terms “mobile computing device” and “mobile device” are used interchangeably herein to refer to any one or all of cellular telephones, smartphones, personal or mobile multi-media players, personal data assistants (PDA's), laptop computers, tablet computers, smartbooks, ultrabooks, palm-top computers, wireless electronic mail receivers, multimedia Internet enabled cellular telephones, wireless gaming controllers, and similar personal electronic devices which include a memory, a programmable processor for which performance is important, and operate under battery power such that power conservation methods are of benefit. While the various aspects are particularly useful for mobile computing devices, such as smartphones, which have limited resources and run on battery, the aspects are generally useful in any electronic device that includes a processor and executes application programs.
Generally, the performance and power efficiency of a mobile device degrade over time. Recently, anti-virus companies (e.g., McAfee, Symantec, etc.) have begun marketing mobile anti-virus, firewall, and encryption products that aim to slow this degradation. However, many of these solutions rely on the periodic execution of a computationally-intensive scanning engine on the mobile device, which may consume many of the mobile device's processing and battery resources, slow or render the mobile device useless for extended periods of time, and/or otherwise degrade the user experience. In addition, these solutions are typically limited to detecting known viruses and malware, and do not address the multiple complex factors and/or the interactions that often combine to contribute to a mobile device's degradation over time (e.g., when the performance degradation is not caused by viruses or malware). For these and other reasons, existing anti-virus, firewall, and encryption products do not provide adequate solutions for identifying the numerous factors that may contribute to a mobile device's degradation over time, for preventing mobile device degradation, or for efficiently restoring an aging mobile device to its original condition.
Various other solutions exist for detecting malicious software by using machine learning techniques or modeling the behavior of processes or application programs executing on a computing device. However, many of these solutions are not suitable for use on mobile devices because they require evaluating a very large corpus of data, are limited to evaluating an individual application program or process, or require the execution of computationally-intensive processes in the mobile device. As such, implementing or performing such solutions in a mobile device may have a significant negative and/or user-perceivable impact on the responsiveness, performance, or power consumption characteristics of the mobile device. For these and other reasons, existing modeling and machine learning solutions are not well suited for use in the complex yet resource-constrained systems of modern mobile devices.
For example, an existing machine learning-based solution may include configuring a computing device to use a corpus of training data to derive a model that takes as input a feature vector. However, such a solution does not generate a full classifier model (or family of classifier models) that includes a finite state machine (or other similar information structure) that is suitable for conversion into or expression as a plurality of boosted decision stumps that each includes a test condition and a weight value. For at least this reason, such solutions cannot be used by a mobile device processor to quickly and efficiently generate a lean classifier model that includes a focused set of boosted decision stumps that be used to quickly and efficiently identify, analyze and/or classify mobile device behaviors without having a significant, negative, or user-perceivable impact on the responsiveness or performance or power consumption characteristics of the mobile device.
Mobile devices are resource constrained systems that have relatively limited processing, memory, and energy resources. Modern mobile devices are also complex systems, and it is often not feasible to evaluate all the various data flows, data operations (reads, writes, data encoding, data transmissions, etc.), processes, components, behaviors, or factors (or combinations thereof) that may be malicious or otherwise contribute to the performance degradation of the mobile device. For these and other reasons, it is increasingly difficult for users, operating systems, and/or application programs (e.g., anti-virus software, etc.) to accurately and efficiently identify the sources of problems and/or to provide adequate remedies to identified problems. As a result, mobile device users currently have few remedies for preventing the degradation in performance and power utilization levels of a mobile device over time.
The various aspects include network servers, mobile devices, systems, and methods for efficiently identifying, classifying, modeling, preventing, and/or correcting the conditions and/or mobile device behaviors that often degrade a mobile device's performance and/or power utilization levels over time.
In an aspect, an observer process, daemon, module, or sub-system (herein collectively referred to as a “module”) of the mobile device may instrument or coordinate various APIs, registers, counters or other components (herein collectively “instrumented components”) at various levels of the mobile device system. The observer module may continuously (or near continuously) monitor mobile device behaviors by collecting behavior information from the instrumented components. The mobile device may also include an analyzer module, and the observer module may communicate (e.g., via a memory write operation, function call, etc.) the collected behavior information to an analyzer module of the mobile device. The analyzer module may receive and use the behavior information to generate behavior vectors, generate spatial and/or temporal correlations based on the behavior vectors, and use this information to determine whether a particular mobile device behavior, sub-system, software application, or process is benign, suspicious, malicious, or performance-degrading.
The analyzer module may be configured to perform real-time behavior analysis operations, which may include performing, executing, and/or applying data, algorithms, classifiers or behavior models (herein collectively “classifier models”) to the collected behavior information to determine whether a mobile device behavior is benign or not benign (e.g., malicious or performance-degrading). Each classifier model may be a behavior model that includes information that may be used by a mobile device processor to evaluate a specific aspect of a mobile device behavior. The classifier models may be preinstalled on the mobile device, downloaded, received from a network server, generated in the mobile device, or any combination thereof. A classifier model may be generated by using machine learning and other similar techniques.
Each classifier model may be categorized as a full classifier model or a lean classifier model. A full classifier model may be a robust data model that is generated as a function of a large training dataset, which may include thousands of features and billions of entries. A lean classifier model may be a more focused data model that is generated from a reduced dataset that includes only the features/entries that are most relevant for determining whether a particular mobile device behavior is benign or not benign (e.g., malicious or performance-degrading).
As mentioned above, there may be thousands of features/factors and billions of data points that require analysis to properly identify the cause or source of a mobile device's degradation. Therefore, each classifier model used by the analyzer module must be trained on a very large number of features, factors, and data points in order for the mobile device to be able to make accurate decisions regarding whether a particular mobile device behavior is benign or not benign (e.g., malicious or performance-degrading). Yet, because mobile devices are resource constrained systems, it is often not feasible for the analyzer module to evaluate all these features, factors, and data points. Therefore, it is important for the analyzer module to apply lean classifier models that focus on evaluating a targeted subset of all the features, factors, and data points that would otherwise require analysis when classifying a mobile device behavior.
The various aspects include mobile devices and network servers configured to work in conjunction with one another to intelligently and efficiently identify the features, factors, and data points that are most relevant to determining whether a mobile device behavior is benign or not benign (e.g., malicious or performance-degrading). By generating classifier models that include boosted decision stumps in the network server and sending these classifiers/models to the mobile device, the various aspects allow the mobile device to quickly and efficiently generate lean classifier models in the mobile device.
In various aspects, the network server may be configured to receive a large amount of information regarding mobile device behaviors and states, features, and conditions during or characterizing those behaviors from a cloud service/network. This information may be in the form of a very large cloud corpus of mobile device behavior vectors. The network server may use this information to generate a full classifier model (i.e., a robust data/behavior model) that accurately describes the very large cloud corpus of behavior vectors. The network server may generate the full classifier model to include all or most of the features, data points, and/or factors that could contribute to the degradation over time of any of a number of different mobile devices.
In an aspect, the network server may generate the full classifier model to include a finite state machine expression or representation, such as a boosted decision stump or family of boosted decision stumps. This finite state machine expression or representation can be quickly and efficiently culled, modified or converted into lean classifier models that are suitable for use or execution in a mobile device through application of culling algorithms at the mobile device processor. The finite state machine expression or representation may be an information structure that includes test conditions, state information, state-transition rules, and other similar information. In an aspect, the finite state machine expression or representation may be an information structure that includes a large or robust family of boosted decision stumps that each evaluate or test a condition, feature, factor, or aspect of a behavior of the mobile device.
The mobile device may be configured to receive a full classifier model from the network server, and use the received full classifier model to generate lean classifier models (i.e., data/behavior models) locally in the mobile device. The mobile device may generate these local lean classifier models by culling a set of boosted decision stumps included in the received full classifier model into to a subset of boosted decision stumps that identify, test, evaluate and/or depend upon a reduced or limited number of different mobile device states, features, behaviors, or conditions. This culling of the full set of boosted decision stumps may be accomplished by: selecting a boosted decision stump; identifying all other boosted decision stumps that depend upon the same mobile device state, feature, behavior, or condition as the selected decision stump (and thus can be applied based upon one determination result); including in the lean classifier model the selected and all identified other boosted decision stumps that depend upon the same mobile device state, feature, behavior, or condition; and repeating the process for a reduced/limited number of selected boosted decision stumps not already included in the lean classifier model. By repeating the process using different numbers of mobile device states, features, behaviors, or conditions that are tested, a family of lean classifier models may be generated with varying degrees of leanness determined by the number of states, features, behaviors, or conditions that are evaluated. In addition, each of these lean classifier models may test or evaluate some or all of the same features or conditions as another lean classifier model, but using different threshold values and/or different weights assigned to the importance of the test results, features, or conditions evaluated. As such, the process of generating or regenerating the lean classifier models may include re-computing the threshold values and/or weights associated with the decision stumps.
Since these lean classifier models include a reduced subset of states, features, behaviors, or conditions that must be tested (compared to the full classifier model), the observer and/or analyzer modules may use them to quickly and accurately determine whether a mobile device behavior is benign or contributing to the degradation in the performance of the mobile device without consuming an excessive amount of processing, memory, or energy resources of the mobile device. As noted above, the leanest of the family of lean classifier models (i.e., the lean classifier model based on the fewest number of test conditions) may be applied routinely until a behavior is encountered that the model cannot categorize as either benign or malicious (and therefore is categorized by the model as suspicious), at which time a more robust (i.e., less lean) lean classifier model may be applied in an attempt to categorize the behavior as either benign or malicious. The application of ever more robust lean classifier models within the family of generated lean classifier models may be applied until a definitive classification of the behavior is achieved. In this manner, the observer and/or analyzer modules can strike a balance between efficiency and accuracy by limiting the use of the most complete, but resource-intensive lean classifier models to those situations where a robust classifier model is needed to definitively classify a behavior.
In various aspects, the mobile device may be configured to generate one or more lean classifier models by converting a finite state machine representation/expression into boosted decision stumps, culling the full set of boosted decision stumps included in the full classifier model to a subset or subsets of boosted decision stumps that depend upon a limited number of different mobile device states, features, behaviors, or conditions, and using the subset or subsets of boosted decision stumps to intelligently monitor, analyze and/or classify a mobile device behavior. The use of boosted decision stumps allows the observer and/or analyzer modules to generate and apply lean data models without communicating with the cloud or a network to re-train the data, which significantly reduces the mobile device's dependence on the network server and the cloud. This eliminates the feedback communications between the mobile device and the network server, which further improves the performance and power consumption characteristics of the mobile device.
Boosted decision stumps are one level decision trees that have exactly one node (and thus one test question or test condition) and a weight value, and thus are well suited for use in a binary classification of data/behaviors. That is, applying a behavior vector to boosted decision stump results in a binary answer (e.g., Yes or No). For example, if the question/condition tested by a boosted decision stump is “is the frequency of Short Message Service (SMS) transmissions less than x per minute,” applying a value of “3” to the boosted decision stump will result in either a “yes” answer (for “less than 3” SMS transmissions) or a “no” answer (for “3 or more” SMS transmissions).
Boosted decision stumps are efficient because they are very simple and primal (and thus do not require significant processing resources). Boosted decision stumps are also very parallelizable, and thus many stumps may be applied or tested in parallel/at the same time (e.g., by multiple cores or processors in the mobile device).
As described below, the network server (or another computing device) may generate a boosted decision stump-type full classifier model from another, more complex model of mobile device behaviors, such as a boosted decision tree model. Such complex models may correlate the full (or nearly full) set of interactions among device states, operations, and monitored nodes that characterize mobile device behavior in a sophisticated classification system. As mentioned above, the server or other computing device may generate a full, complex classifier model by applying machine learning techniques to generate models that describe a cloud corpus of behavior vectors of mobile devices collected from a large number of mobile devices. As an example, a boosted decision tree classifier model may trace hundreds of paths through decision nodes of testable conditions to arrive at a determination of whether a current mobile device behavior is malicious or benign. Such complex models may be generated in the server using a number of known learning and correlation modeling techniques. While such complex models can become quite effective in accurately recognizing malicious behaviors by learning from data from many hundreds of mobile devices, their application to a particular mobile device's configuration and behaviors may require significant processing, particularly if the model involves complex, multilevel decision trees. Since mobile devices are typically resource limited, using such models may impact device performance and battery life.
To render robust classifier models that are more conducive to use by mobile devices, a server (e.g., a cloud server or the network server) or another computing device (e.g., a mobile device or a computer that will couple to the mobile device) may transform complex classifier models into large boosted decision stump models. The more simple determinations involved in decision stumps and the ability to apply such classifier models in parallel processes may enable mobile devices to better benefit from the analyses performed by the network server. Also, as discussed below, a boosted decision stump full classifier model may be used by mobile devices to generate a lean classifier model using the aspect methods described below.
In an aspect, the server or other computing device that generates a boosted decision stump full classifier model may do so by following an aspect process described in more detail below. In summary, the server or other computing device may select a node within the full complex classifier model (e.g., a boosted decision tree model) and apply the model to determine the percentage of the time that the node is predictive of malicious behavior. In other words, the server or other computing device may select one branch of the node and follow all subsequent nodes and paths connected to that branch to determine the fraction of the time that branch leads to a determination of malicious behavior. In an aspect, this fraction of time may be used to compute a “weight” factor for the node. For example, a decision node with one branch whose subsequent path results in a malicious behavior conclusion 80% of the time might be associated with a weighting factor of 0.8, indicating that this single decision node is a reliable indicator of potentially malicious (and thus suspicious) behavior. As another example, a decision node in the complex classifier model whose branches may equally lead to a malicious behavior conclusion would provide little assistance in recognizing malicious behavior, and thus may be given a very low weighting factor or priority.
In the process of tracing the outcomes from each decision node, the server or other computing device may apply a variety of test conditions to each node if the decision node is not binary (i.e., “yes” or “no”). For example, a complex classifier model may accommodate a range of values (e.g., the number of SMS messages transmitted per minute), with the ultimate conclusion depending upon the value. However, ranges of values are inconsistent with the binary nature of decision stumps. So, the server or other computing device may develop a range of binary decisions or tests for such nodes that are conducive to conditions characterized by values. For example, the server or other computing device may generate and test through the complex classifier model a number of threshold tests or conditions, such as “more than one,” “more than ten” and “more than 100.” Such threshold tests may be identified or selected by the server based on conclusions it can reach from studying the complex model. Each such threshold-based test may then be treated as a single decision stump that can be tested to determine its predictive value and thus its boosting factor.
By following this process through all decision nodes in the complex classifier model, the server or other computing device can transform a complex multi-layered decision model into a single layer model of a large number of boosted decision stumps. The server or other computing device may then trim the model by removing decision stumps whose value is below a threshold value in order to remove test conditions that provide very little predictive or classification benefit (e.g., “is the power on?”).
While the resulting number of such stumps may be large in a full classifier model, the binary nature of the stumps may facilitate their application, particularly in resource constrained processors. In an aspect, the server or other computing device may provide the boosted decision stumps full classifier model to mobile devices for their use.
The process of generating a large classifier model of boosted decision stumps may be generated by the cloud server that analyzes inputs from many mobile devices and generates a full, complex behavior classifier model, since such servers will have the processing resource and processing time to complete the analysis. However, as noted above, the aspect methods may also be performed by another computing device, including even the mobile device. In this aspect, a server (e.g., a cloud or network server) may deliver the full, complex behavior classifier model to the other computing device, which may then process the model as outline above and in more detail below to transform it into a boosted decision stumps model. For example, a person computer that the user couples to his/her mobile device may download the full, complex behavior classifier model and then perform the aspect methods to generate a large boosted decision stumps model that it makes available (e.g., through a wired or wireless data link) to the mobile device. As another example, a mobile device may download the full, complex behavior classifier model and then perform the aspect methods, such as during late night hours when the device is being charged and not in use, to generate a large boosted decision stumps model that it stores in memory. Since the processes implemented by a server or another computing device are very similar, the aspect methods are described in more detail below as being performed by a server. However, that description is for example purposes and is not intended to limit the aspect methods to being performed on a server unless specifically so recited in the claims.
In a further aspect, mobile devices may be configured to use a received or self-generated large classifier model of boosted decision stumps to build lean classifier models by selecting a limited number of factors that are tested in decision stumps, without accessing the training data and without consuming an excessive amount of processing, memory, or energy resources of the mobile device. The analyzer module may use the lean classifier model of selected boosted decision stumps to identify malware and classify device behavior as malicious or benign. As described more fully below, mobile devices may generate lean classifier models by determining a number of features to monitor that will be tested (e.g., 15), selecting a first feature and incorporating into the lean classifier all of boosted decision stumps that include a test of that feature (e.g., all stumps with threshold tests based on a value obtained from the monitored feature), and repeating this process until the number of features addressed in the lean classifier model is the determined number. It is worth noting that the number of boosted decision stumps in such a lean classifier model may be significantly larger than the number of features.
In an aspect, a mobile device may be configured to receive a full classifier model that includes a finite state machine that is suitable for conversion into a plurality of boosted decision stumps. The mobile device may generate a lean classifier model based on the full classifier model, which may be accomplished by converting the finite state machine of the full classifier model into boosted decision stumps and using these boosted decision stumps as a lean classifier model.
The various aspects may be implemented within a variety of communication systems, such as the example communication system 100 illustrated in FIG. 1. A typical cell telephone network 104 includes a plurality of cell base stations 106 coupled to a network operations center 108, which operates to connect voice calls and data between mobile devices 102 (e.g., cell phones, laptops, tablets, etc.) and other network destinations, such as via telephone land lines (e.g., a POTS network, not shown) and the Internet 110. Communications between the mobile devices 102 and the telephone network 104 may be accomplished via two-way wireless communication links 112, such as 4G, 3G, CDMA, TDMA, LTE and/or other cell telephone communication technologies. The telephone network 104 may also include one or more servers 114 coupled to or within the network operations center 108 that provide a connection to the Internet 110.
The communication system 100 may further include network servers 116 connected to the telephone network 104 and to the Internet 110. The connection between the network server 116 and the telephone network 104 may be through the Internet 110 or through a private network (as illustrated by the dashed arrows). The network server 116 may also be implemented as a server within the network infrastructure of a cloud service provider network 118. Communication between the network server 116 and the mobile devices 102 may be achieved through the telephone network 104, the internet 110, private network (not illustrated), or any combination thereof.
The network server 116 may send lean data/behavior models to the mobile device 102, which may receive and use lean data/behavior models to identify suspicious or performance-degrading mobile device behaviors, software applications, processes, etc. The network server 116 may also send classification and modeling information to the mobile devices 102 to replace, update, create and/or maintain mobile device data/behavior models.
The mobile device 102 may collect behavioral, state, classification, modeling, success rate, and/or statistical information in the mobile device 102, and send the collected information to the network server 116 (e.g., via the telephone network 104) for analysis. The network server 116 may use information received from the mobile device 102 to update or refine the lean data/behavior models or the classification/modeling information to include a further targeted and/or reduced subset of features.
In an aspect, the mobile device 102 may be configured to use the collected behavioral, state, classification, modeling, success rate, and/or statistical information to generate, update or refine the lean classifier models (or data/behavior models) that include a further targeted and/or reduced subset of features in the mobile device 102. This reduces the amount of feedback communications between the mobile device and the network server 116, and improves the performance and power consumption characteristics of the mobile device 102.
FIG. 2 illustrates example logical components and information flows in an aspect mobile device 102 configured to determine whether a particular mobile device behavior, software application, or process is malicious/performance-degrading, suspicious, or benign. In the example illustrated in FIG. 2, the mobile device 102 includes a behavior observer module 202, a behavior analyzer module 204, an external context information module 206, a classifier module 208, and an actuator module 210. In an aspect, the classifier module 208 may be implemented as part of the behavior analyzer module 204. In an aspect, the behavior analyzer module 204 may be configured to generate one or more classifier modules 208, each of which may include one or more classifiers.
Each of the modules 202-210 may be implemented in software, hardware, or any combination thereof. In various aspects, the modules 202-210 may be implemented within parts of the operating system (e.g., within the kernel, in the kernel space, in the user space, etc.), within separate programs or applications, in specialized hardware buffers or processors, or any combination thereof. In an aspect, one or more of the modules 202-210 may be implemented as software instructions executing on one or more processors of the mobile device 102.
The behavior observer module 202 may be configured to instrument or coordinate application programming interfaces (APIs) at various levels/modules of the mobile device, and monitor/observe mobile device operations and events (e.g., system events, state changes, etc.) at the various levels/modules via the instrumented APIs, collect information pertaining to the observed operations/events, intelligently filter the collected information, generate one or more observations based on the filtered information, and store the generated observations in a memory (e.g., in a log file, etc.) and/or send (e.g., via memory writes, function calls, etc.) the generated observations to the behavior analyzer module 204.
The behavior observer module 202 may monitor/observe mobile device operations and events by collecting information pertaining to library application programming interface (API) calls in an application framework or run-time libraries, system call APIs, file-system and networking sub-system operations, device (including sensor devices) state changes, and other similar events. The behavior observer module 202 may also monitor file system activity, which may include searching for filenames, categories of file accesses (personal info or normal data files), creating or deleting files (e.g., type exe, zip, etc.), file read/write/seek operations, changing file permissions, etc.
The behavior observer module 202 may also monitor data network activity, which may include types of connections, protocols, port numbers, server/client that the device is connected to, the number of connections, volume or frequency of communications, etc. The behavior observer module 202 may monitor phone network activity, which may include monitoring the type and number of calls or messages (e.g., SMS, etc.) sent out, received, or intercepted (e.g., the number of premium calls placed).
The behavior observer module 202 may also monitor the system resource usage, which may include monitoring the number of forks, memory access operations, number of files open, etc. The behavior observer module 202 may monitor the state of the mobile device, which may include monitoring various factors, such as whether the display is on or off, whether the device is locked or unlocked, the amount of battery remaining, the state of the camera, etc. The behavior observer module 202 may also monitor inter-process communications (IPC) by, for example, monitoring intents to crucial services (browser, contracts provider, etc.), the degree of inter-process communications, pop-up windows, etc.
The behavior observer module 202 may also monitor/observe driver statistics and/or the status of one or more hardware components, which may include cameras, sensors, electronic displays, WiFi communication components, data controllers, memory controllers, system controllers, access ports, timers, peripheral devices, wireless communication components, external memory chips, voltage regulators, oscillators, phase-locked loops, peripheral bridges, and other similar components used to support the processors and clients running on the mobile computing device.
The behavior observer module 202 may also monitor/observe one or more hardware counters that denote the state or status of the mobile computing device and/or mobile device sub-systems. A hardware counter may include a special-purpose register of the processors/cores that is configured to store a count or state of hardware-related activities or events occurring in the mobile computing device.
The behavior observer module 202 may also monitor/observe actions or operations of software applications, software downloads from an application download server (e.g., Apple® App Store server), mobile device information used by software applications, call information, text messaging information (e.g., SendSMS, BlockSMS, ReadSMS, etc.), media messaging information (e.g., ReceiveMMS), user account information, location information, camera information, accelerometer information, browser information, content of browser-based communications, content of voice-based communications, short range radio communications (e.g., Bluetooth, WiFi, etc.), content of text-based communications, content of recorded audio files, phonebook or contact information, contacts lists, etc.
The behavior observer module 202 may monitor/observe transmissions or communications of the mobile device, including communications that include voicemail (VoiceMailComm), device identifiers (DevicelDComm), user account information (UserAccountComm), calendar information (CalendarComm), location information (LocationComm), recorded audio information (RecordAudioComm), accelerometer information (AccelerometerComm), etc.
The behavior observer module 202 may monitor/observe usage of and updates/changes to compass information, mobile device settings, battery life, gyroscope information, pressure sensors, magnet sensors, screen activity, etc. The behavior observer module 202 may monitor/observe notifications communicated to and from a software application (AppNotifications), application updates, etc. The behavior observer module 202 may monitor/observe conditions or events pertaining to a first software application requesting the downloading and/or install of a second software application. The behavior observer module 202 may monitor/observe conditions or events pertaining to user verification, such as the entry of a password, etc.
The behavior observer module 202 may also monitor/observe conditions or events at multiple levels of the mobile device, including the application level, radio level, and sensor level. Application level observations may include observing the user via facial recognition software, observing social streams, observing notes entered by the user, observing events pertaining to the use of PassBook/Google Wallet/Paypal, etc. Application level observations may also include observing events relating to the use of virtual private networks (VPNs) and events pertaining to synchronization, voice searches, voice control (e.g., lock/unlock a phone by saying one word), language translators, the offloading of data for computations, video streaming, camera usage without user activity, microphone usage without user activity, etc.
Radio level observations may include determining the presence, existence or amount of any or more of: user interaction with the mobile device before establishing radio communication links or transmitting information, dual/multiple subscriber identity module (SIM) cards, Internet radio, mobile phone tethering, offloading data for computations, device state communications, the use as a game controller or home controller, vehicle communications, mobile device synchronization, etc. Radio level observations may also include monitoring the use of radios (WiFi, WiMax, Bluetooth, etc.) for positioning, peer-to-peer (p2p) communications, synchronization, vehicle to vehicle communications, and/or machine-to-machine (m2m). Radio level observations may further include monitoring network traffic usage, statistics, or profiles.
Sensor level observations may include monitoring a magnet sensor or other sensor to determine the usage and/or external environment of the mobile device. For example, the mobile device processor may be configured to determine whether the phone is in a holster (e.g., via a magnet sensor configured to sense a magnet within the holster) or in the user's pocket (e.g., via the amount of light detected by a camera or light sensor). Detecting that the mobile device is in a holster may be relevant to recognizing suspicious behaviors, for example, because activities and functions related to active usage by a user (e.g., taking photographs or videos, sending messages, conducting a voice call, recording sounds, etc.) occurring while the mobile device is holstered could be signs of nefarious processes executing on the device (e.g., to track or spy on the user).
Other examples of sensor level observations related to usage or external environments may include, detecting near-field communications (NFC), collecting information from a credit card scanner, barcode scanner, or mobile tag reader, detecting the presence of a universal serial bus (USB) power charging source, detecting that a keyboard or auxiliary device has been coupled to the mobile device, detecting that the mobile device has been coupled to a computing device (e.g., via USB, etc.), determining whether an LED, flash, flashlight, or light source has been modified or disabled (e.g., maliciously disabling an emergency signaling app, etc.), detecting that a speaker or microphone has been turned on or powered, detecting a charging or power event, detecting that the mobile device is being used as a game controller, etc. Sensor level observations may also include collecting information from medical or healthcare sensors or from scanning the user's body, collecting information from an external sensor plugged into the USB/audio jack, collecting information from a tactile or haptic sensor (e.g., via a vibrator interface, etc.), collecting information pertaining to the thermal state of the mobile device, etc.
To reduce the number of factors monitored to a manageable level, in an aspect, the behavior observer module 202 may perform coarse observations by monitoring/observing an initial set of behaviors or factors that are a small subset of all factors that could contribute to the mobile device's degradation. In an aspect, the behavior observer module 202 may receive the initial set of behaviors and/or factors from a network server 116 and/or a component in a cloud service or network 118. In an aspect, the initial set of behaviors/factors may be specified in data/behavior models received from the network server 116 or cloud service/network 118. In an aspect, the initial set of behaviors/factors may be specified in a reduced feature model (RFMs).
The behavior analyzer module 204 and/or classifier module 208 may receive the observations from the behavior observer module 202, compare the received information (i.e., observations) with contextual information received from the external context information module 206, and identify subsystems, processes, and/or applications associated with the received observations that are contributing to (or are likely to contribute to) the device's degradation over time, or which may otherwise cause problems on the device.
In an aspect, the behavior analyzer module 204 and/or classifier module 208 may include intelligence for utilizing a limited set of information (i.e., coarse observations) to identify behaviors, processes, or programs that are contributing to—or are likely to contribute to—the device's degradation over time, or which may otherwise cause problems on the device. For example, the behavior analyzer module 204 may be configured to analyze information (e.g., in the form of observations) collected from various modules (e.g., the behavior observer module 202, external context information module 206, etc.), learn the normal operational behaviors of the mobile device, and generate one or more behavior vectors based the results of the comparisons. The behavior analyzer module 204 may send the generated behavior vectors to the classifier module 208 for further analysis.
The classifier module 208 may receive the behavior vectors and compare them to one or more behavior modules to determine whether a particular mobile device behavior, software application, or process is performance-degrading/malicious, benign, or suspicious.
When the classifier module 208 determines that a behavior, software application, or process is malicious or performance-degrading, the classifier module 208 may notify the actuator module 210, which may perform various actions or operations to correct mobile device behaviors determined to be malicious or performance-degrading and/or perform operations to heal, cure, isolate, or otherwise fix the identified problem.
When the classifier module 208 determines that a behavior, software application, or process is suspicious, the classifier module 208 may notify the behavior observer module 202, which may adjust the adjust the granularity of its observations (i.e., the level of detail at which mobile device behaviors are observed) and/or change the behaviors that are observed based on information received from the classifier module 208 (e.g., results of the real-time analysis operations), generate or collect new or additional behavior information, and send the new/additional information to the behavior analyzer module 204 and/or classifier module 208 for further analysis/classification. Such feedback communications between the behavior observer module 202 and the classifier module 208 enable the mobile device 102 to recursively increase the granularity of the observations (i.e., make finer or more detailed observations) or change the features/behaviors that are observed until a source of a suspicious or performance-degrading mobile device behavior is identified, until a processing or battery consumption threshold is reached, or until the mobile device processor determines that the source of the suspicious or performance-degrading mobile device behavior cannot be identified from further increases in observation granularity. Such feedback communication also enable the mobile device 102 to adjust or modify the data/behavior models locally in the mobile device without consuming an excessive amount of the mobile device's processing, memory, or energy resources.
In an aspect, the behavior observer module 202 and the behavior analyzer module 204 may provide, either individually or collectively, real-time behavior analysis of the computing system's behaviors to identify suspicious behavior from limited and coarse observations, to dynamically determine behaviors to observe in greater detail, and to dynamically determine the level of detail required for the observations. In this manner, the behavior observer module 202 enables the mobile device 102 to efficiently identify and prevent problems from occurring on mobile devices without requiring a large amount of processor, memory, or battery resources on the device.
FIGS. 3 and 4 illustrate example components and information flows in an aspect system 300 that includes a network server 116 configured to work in conjunction with a cloud service/network 118 to intelligently and efficiently identify actively malicious or poorly written software applications and/or suspicious or performance-degrading mobile device behaviors on the mobile device 102 without consuming an excessive amount of processing, memory, or energy resources of the mobile device. In the example illustrated in FIG. 3, the network server 116 includes a cloud module 302, a model generator 304 module, and a training data module 306. The mobile device 102 includes a behavior observer module 202, a classifier module 208, and an actuator module 210. In an aspect, the classifier module 208 may be included in, or as part of, the behavior analyzer module 204 (illustrated in FIG. 2). In an aspect, the model generator 304 module may be a real-time online classifier.
The cloud module 302 may be configured to receive a large amount of information from a cloud service/network 118 and generate a full or robust data/behavior model that includes all or most of the features, data points, and/or factors that could contribute to the mobile device's degradation over time.
The model generator 304 module may be configured to generate lean data/behavior models based on full model generated in the cloud module 302. In an aspect, generating the lean data/behavior models may include generating one or more reduced feature models (RFMs) that include a subset of the features and data points included in the full model generated by the cloud module 302. In an aspect, the model generator 304 may generate a lean data/behavior model that includes an initial feature set (e.g., an initial reduced feature model) that includes information determined to have a highest probably of enabling the classifier module 208 to conclusively determine whether a particular mobile device behavior is benign or malicious/performance-degrading. The model generator 304 may send the generated lean models to the behavior observer module 202.
The behavior observer module 202 may monitor/observe mobile device behaviors based on the received model, generate observations, and send the observations to the classifier module 208. The classifier module 208 may perform real-time analysis operations, which may include applying data/behavior models to behavior information collected by the behavior observer module 202 to determine whether a mobile device behavior is benign, suspicious, or malicious/performance-degrading. The classifier module 208 may determine that a mobile device behavior is suspicious when the classifier module 208 does not have sufficient information to classify or conclusively determine that the behavior is either benign or malicious.
The classifier module 208 may be configured to communicate the results of its real-time analysis operations to the behavior observer module 202 when the classifier module 208 determines that a device behavior is suspicious. The behavior observer module 202 may adjust the granularity of its observations (i.e., the level of detail at which mobile device behaviors are observed) and/or change the behaviors that are observed based on information received from the classifier module 208 (e.g., based on the results of the real-time analysis operations), generate or collect new or additional behavior information, and send the new/additional information to the classifier module for further analysis/classification (e.g., in the form of new models). In this manner, the mobile device 102 may recursively increase the granularity of the observations (i.e., make finer or more detailed observations) or change the features/behaviors that are observed until a source of a suspicious or performance-degrading mobile device behavior is identified, until a processing or battery consumption threshold is reached, or until the mobile device processor determines that the source of the suspicious or performance-degrading mobile device behavior cannot be identified from further increases in observation granularity.
The mobile device 102 may the send the results of its operations and/or success rates associated with the application of models to the network server 116. The network server 116 may generate training data (e.g., via the training data module 306) based on the results/success rates for use by the model generator 304. The model generator may generate updated models based on the training data, and send the updated models to the mobile device 102.
In the example illustrated in FIG. 4, there is no feedback communications between the mobile device 102 and the network server 116. Rather, the mobile device 102 includes a lean model generator module 402 configured to generate focused/targeted behavior models or classifiers based on the full or more robust models generated in the full model generator 404 and received from the network server 116. That is, the network server 116 may be configured to send the full classifier models to the mobile device 102, and the mobile device 102 may be configured to generate lean classifier models based on the full classifier model. This may be accomplished without consuming an excessive amount of the processing or battery resources of the mobile device due to the use (or inclusion) of boosted decision stumps in the classifier models. That is, by generating classifier models that include boosted decision stumps in the network server 116 and sending these classifiers/models to the mobile device 102, the various aspects allow the lean model generator module 402 to quickly and efficiently generate lean (or more focused) classifier models in the mobile device 102 by culling the number of boosted decision stumps included in the full classifier model without accessing training data or further communicating with the network server 116 or the cloud network/server 118. This significantly reduces the mobile device's dependence on network communications, and further improves the performance and power consumption characteristics of the mobile device 102.
FIG. 5A illustrates an aspect method 500 of generating a lean or focused classifier/behavior model in the mobile device (e.g., model generated in the model generator module 402, etc.). Method 500 may be performed by a processing core in a mobile device.
In block 502 of method 500, the processing core may receive a full classifier model that is or includes a finite state machine, a list of boosted decision stumps or other similar information structure. In an aspect, the full classifier model includes a finite state machine that includes information suitable for expressing plurality of boosted decision stumps and/or which include information that is suitable for conversion by the mobile device into a plurality of boosted decision stumps. In an aspect, the finite state machine may be (or may include) an ordered or prioritized list of boosted decision stumps. Each of the boosted decision stumps may include a test condition and a weight value.
As discussed above, boosted decision stumps are one level decision trees that have exactly one node (and thus one test question or test condition) and a weight value, and thus are well suited for use in a binary classification of data/behaviors. This means that applying a feature vector or behavior vector to boosted decision stump results in a binary answer (e.g., Yes or No). For example, if the question/condition tested by a boosted decision stump is “is the frequency of SMS transmissions less than x per min,” applying a value of “3” to the boosted decision stump will result in either a “yes” answer (for “less than 3” SMS transmissions) or a “no” answer (for “3 or more” SMS transmissions).
Returning to FIG. 5A, in block 504 of method 500, the processing core may determine the number unique test conditions that should be evaluated to accurately classify a mobile device behavior as being either malicious or benign without consuming an excessive amount of processing, memory, or energy resources of the mobile device. This may include determining an amount of processing, memory, and/or energy resources available in the mobile device, the amount processing, memory, or energy resources of the mobile device that are required to test a condition, determining a priority and/or a complexity associated with a behavior or condition that is to be analyzed or evaluated in the mobile device by testing the condition, and selecting/determining the number of unique test conditions so as to strike a balance or tradeoff between the consumption of available processing, memory, or energy resources of the mobile device, the accuracy of the behavior classification that is to be achieved from testing the condition, and the importance or priority of the behavior that is tested by the condition.
In block 506, the processing core may traverse the list of boosted decision stumps from the beginning to populate a list of selected test conditions with the determined number of unique test conditions. In an aspect, the processing core may also determine an absolute or relative priority value for each of the selected test conditions, and store the absolute or relative priorities value in association with their corresponding test conditions in the list of selected test conditions.
In block 508, the processing core may generate a lean classifier model that includes all the boosted decision stumps included in the full classifier model that test one of the selected test conditions. In an aspect, the processing core may generate the lean classifier model to include or express the boosted decision stumps in order of importance or priority value.
In optional block 510, the number of unique test conditions may be increased in order to generate another more robust (i.e., less lean) lean classifier model by repeating the operations of traversing the list of boosted decision stumps for a larger number test conditions in block 506 and generating another lean classifier model in block 508. These operations may be repeated to generate a family of lean classifier models.
FIG. 5B illustrates another aspect method 511 of generating data models in the mobile device. Method 511 may be performed by a processing core in a mobile device. In block 512 of method 511, the processing core may receive a full classifier model that includes a finite state machine. The finite state machine may be an information structure that includes information that is suitable for conversion into a plurality of boosted decision stumps. In block 514, the processing core may convert the finite state machine included in the full classifier model into boosted decision stumps that include a test condition and a weight value.
In an aspect, the processing core may also compute or determine priority values for each of the boosted decision stumps that are generated from the finite state machine in block 512. The processing core may determine the priorities of the boosted decision stumps so as to balance tradeoffs between the consumption of processing, memory, or energy resources of the mobile device, the accuracy of the behavior classification, etc. The processing core may also determine the priorities of the boosted decision stumps based on their associated weight values, relative or predicted importance of the test conditions to accurately classify a behavior, etc.
Also in block 512, the processing core may generate a first list (or other information structure) that includes, references, identifies, and/or organizes the boosted decision stumps generated from the finite state machine in accordance with their priorities and/or in order of their importance. For example, the processing core may generate the first list to be an ordered list that includes the stump having the highest priority as the first item, followed by the stump having the second highest priority value, and so on. This order of importance may also take into account the information gathered from the cloud corpus, as well as information specific to the device on which the culling algorithm is being executed.
In block 516, the processing core may compute or determine the number of unique test conditions (i.e., the mobile device states, features, behaviors, or conditions that may be tested in boosted decision stumps) that should be evaluated when applying the lean classifier model. Computing or determining this number of unique test conditions may involve striking a balance or tradeoff between the consumption of processing, memory, or energy resources of the mobile device required to apply the model, and the accuracy of the behavior classification that is to be achieved the lean classifier model. Such a determination may include determining an amount of processing, memory, and/or energy resources available in the mobile device, determining a priority and/or a complexity associated with the behavior that is to be analyzed, and balancing the available resources with the priority and/or complexity of the behavior.
In block 518, the processing core may generate a second list by sequentially traversing the first list of boosted decision stumps and inserting the test condition values associated with each traversed boosted decision stump into the second list. The processing core may continue to traverse the first list and insert values into the second list until the length of second list is equal to the determined number of unique test conditions or until the second list includes all the determined number of unique test conditions.
In block 520, the processing core may generate a lean classifier model based on the boosted decision stumps included in the first list. In an aspect, the processing core may generate the lean classifier model to include only the boosted decision stumps that test one of the test conditions included in the second list (i.e., the list of test conditions generated in block 518).
In optional block 522, the number of unique test conditions may be increased in order to generate another more robust (i.e., less lean) lean classifier model by repeating the operations of traversing the list of boosted decision stumps for a larger number test conditions in block 518 and generating another lean classifier model in block 520. These operations may be repeated to generate a family of lean classifier models.
FIG. 5C illustrates an aspect method 524 of using a lean classifier model to classify a behavior of the mobile device. Method 524 may be performed by a processing core in a mobile device.
In block 526 of method 524, the processing core my perform observations to collect behavior information from various components that are instrumented at various levels of the mobile device system. In an aspect, this may be accomplished via the behavior observer module 202 discussed above with reference to FIG. 2. In block 528, the processing core may generate a behavior vector characterizing the observations, the collected behavior information, and/or a mobile device behavior. Also in block 528, the processing core may use a full classifier model received from a network server to generate a lean classifier model or a family of lean classifier models of varying levels of complexity (or “leanness”). To accomplish this, the processing core may cull a family of boosted decision stumps included in the full classifier model to generate lean classifier models that include a reduced number of boosted decision stumps and/or evaluate a limited number of test conditions.
In block 529, the processing core may select the leanest classifier in the family of lean classifier models (i.e., the model based on the fewest number of different mobile device states, features, behaviors, or conditions) that has not yet been evaluated or applied by the mobile device. In an aspect, this may be accomplished by the processing core selecting the first classifier model in an ordered list of classifier models.
In block 530, the processing core may apply collected behavior information or behavior vectors to each boosted decision stump in the selected lean classifier model. Because boosted decision stumps are binary decisions and the lean classifier model is generated by selecting many binary decisions that are based on the same test condition, the process of applying a behavior vector to the boosted decision stumps in the lean classifier model may be performed in a parallel operation. Alternatively, the behavior vector applied in block 530 may be truncated or filtered to just include the limited number of test condition parameters included in the lean classifier model, thereby further reducing the computational effort in applying the model.
In block 532, the processing core may compute or determine a weighted average of the results of applying the collected behavior information to each boosted decision stump in the lean classifier model. In block 534, the processing core may compare the computed weighted average to a threshold value. In determination block 535, the processing core may determine whether the results of this comparison and/or the results generated by applying the selected lean classifier model are suspicious. For example, the processing core may determine whether these results may be used to classify a behavior as either malicious or benign with a high degree of confidence, and if not treat the behavior as suspicious.
If the processing core determines that the results are suspicious (e.g., determination block 535=“Yes”), the processing core may repeat the operations in blocks 529-534 to select and apply a stronger (i.e., less lean) classifier model that evaluates more device states, features, behaviors, or conditions until the behavior is classified as malicious or benign with a high degree of confidence. If the processing core determines that the results are not suspicious (e.g., determination block 535=“No”), such as by determining that the behavior can be classified as either malicious or benign with a high degree of confidence, in block 536, the processing core may use the result of the comparison generated in block 534 to classify a behavior of the mobile device as benign or potentially malicious.
In an alternative aspect method 540 illustrated in FIG. 5D the operations described above with reference to blocks 518 and 520 may be accomplished by sequentially selecting a boosted decision stump that is not already in the lean classifier model; identifying all other boosted decision stumps that depend upon the same mobile device state, feature, behavior, or condition as the selected decision stump (and thus can be applied based upon one determination result); including in the lean classifier model the selected and all identified other boosted decision stumps that that depend upon the same mobile device state, feature, behavior, or condition; and repeating the process for a number of times equal to the determined number of test conditions. Because all boosted decision stumps that depend on the same test condition as the selected boosted decision stump are added to the lean classifier model each time, limiting the number of times this process is performed will limit the number of test conditions included in the lean classifier model.
Referring to FIG. 5D, in block 542, the processing core may compute or determine a number (N) of unique test conditions (i.e., the mobile device states, features, behaviors, or conditions that may be tested in boosted decision stumps) that should be evaluated in the lean classifier model. Computing or determining this number of unique test conditions may involve striking a balance or tradeoff between the consumption of processing, memory, or energy resources of the mobile device required to apply the model, and the accuracy of the behavior classification that is to be achieved by the lean classifier model. Such a determination may include determining an amount of processing, memory, and/or energy resources available in the mobile device, determining a priority and/or a complexity associated with the behavior that is to be analyzed, and balancing the available resources with the priority and/or complexity of the behavior.
In block 544, the processing core may set the value of a loop count variable to be equal to zero (0), or otherwise initiate a loop that will be performed the determined number N times. In block 546, the processing core may select a boosted decision stump that is included in, or generated from, the full set of boosted decision stumps and which is not included in a lean classifier model list. The first time through the loop there will be no boosted decision stumps in the lean classifier model list, so the first boosted decision stump will be selected. As mentioned herein, the full classifier model may be configured so that the first boosted decision stump in the full set has the highest probability of recognizing malicious or benign behavior. In block 548, the processing core may determine the test condition associated with the selected decision stump. In block 550, the processing core may identify all of the decision stumps included in, or generated from, the full classifier model that depend on, include, or test the same test condition as the test condition of the selected decision stump. In block 552, the processing core may add the selected boosted decision stump and all of the identified boosted decision stumps that depend on, include, or test the same test condition to the lean classifier model list.
In block 554, the processing core may increment the value of the loop count variable. In determination block 556, the processing core may determine whether the value of the loop count variable is greater than or equal to the number N of unique test conditions determined in block 542. When the processing core determines that the value of the loop count variable is not greater than or equal to the number of unique test conditions (i.e., determination block 556=“No”), the processing core may repeat the operations in blocks 546-554. When the processing core determines that the value of the loop count variable is greater than or equal to the number of unique test conditions (i.e., determination block 556=“Yes”), in block 558, the processing core may generate the lean classifier model to include all the boosted decision stumps in the lean classifier model list.
This method 540 may be used a number of times to generate a family of lean classifier models of varying degrees of robustness or leanness by varying the number N of unique test conditions in the lean classifier model. For example, in optional block 560, the mobile device processor may increase the number N of unique test conditions determined in block 542 in order to generate another lean classifier model that incorporates more test conditions. In optional determination block 562, the processor may determine whether the increase number N exceeds a maximum number (max N) of test conditions. The maximum number of test conditions may be determined (e.g., by a developer, service provider, user or via an algorithm) based on a maximum performance penalty or resource investment desired for assessing difficult-to-classify behaviors. If the increased number N is less than the maximum number max N (i.e., determination block 562=“No”), the operations of blocks 544 through 560 described above may be repeated to generate another lean classifier model. Once the maximum number of unique test conditions have been included in a lean classifier model (i.e., determination block 562=“Yes”), the process of generating lean classifier models may end.
While FIGS. 5A, 5B and 5D describe generating a family of lean classifier models by repeating the entire process of traversing the full set of boosted decision stumps, a similar result may be achieved by beginning with a generated lean classifier model (i.e., a model generated in any of blocks 508, 520 and 558) and traversing the full set of boosted decision stumps for the added number of test conditions adding to that model boosted decision stumps depending on a test condition not already included in the generated lean classifier model.
Also, while FIGS. 5A, 5B and 5D describe generating a family of lean classifier models from leanest to most robust, the lean classifier models may also be generated from most robust to leanest simply by beginning with a maximum number of test conditions (e.g., N=max N) and decreasing the number each time.
FIG. 6A illustrates an aspect method 600 of generating a full classifier in the server or cloud. Method 600 may be performed by a processing core in a server computing device coupled to the cloud network.
In block 602, the processing core may gather a corpus of behavior data from many mobile devices, including a large number of device states, configurations and behavior, as well as information regarding whether a malicious behavior was detected. In block 604, the processing core may identify particular binary questions/test conditions that can be tested within the device states, configurations and behavior from the corpus of behavior data. To characterize all of the device states, configurations and behaviors, a large number of such binary questions/test conditions will typically be identified. Then, in block 606, for each identified binary question, the processing core may test the data base to determine the fraction or percentage of times that a malicious behavior corresponded to one or the other of the answers to the binary question. In block 608, the processing core may select the binary question with the highest correspondence to malicious behavior as a first decision stump with a weight value determined based on the correspondence percentage. In block 610, the processing core may boost the weight of the incorrectly classified samples/test conditions as described below with reference to FIG. 6B.
The processing core of the server may then repeat the process of scanning the binary question assuming the answer of the first question is the value (e.g., “no”) not associated with malicious behavior to identify the question with the highest correspondence to malicious behavior in this case. That question is then set as the second binary question in the model, with its weight value determined based on its correspondence percentage. The server then repeats the process of scanning the binary question—assuming the answers of the first and questions/test conditions are the values (e.g., “no”) not associated with malicious behavior—to identify the next question/test condition with the highest correspondence to malicious behavior in this case. That question/test condition is then the third binary question/test condition in the model, with its weight value determined based on its correspondence percentage. This process is continued through all of the identified binary questions/test conditions to build the complete set.
In the process of generating the binary questions/test conditions, the server may evaluate data that has a range, such as the frequency of communications, or the number of communications within a previous time interval, and formulate a series of binary questions/test conditions that encompass the range in a manner that helps classify behaviors. Thus, one binary question/test condition might be whether the device has sent more than zero data transmissions within the previous five minutes (which might have a low correlation), a second binary question/test condition might be whether the device has sent more than 10 data transmissions in the previous five minutes (which might have a medium correlation), and a third question/test condition might be whether the device has sent more than 100 data transmissions within the previous five minutes (which might have a high correlation).
Some culling of the final set of questions/test conditions may be done by the server before the full classifier set is sent to mobile devices, such as to remove those questions/test conditions whose determined weight or correlation to malicious behavior is less than a threshold value (e.g., less than statistically significant). For example, if the correlation to malicious behavior is approximately 50/50, there may be little benefit in using that decision stump as neither answer helps answer the question of whether current behavior is malicious or benign.
FIG. 6B illustrates an example boosting method 620 suitable for generating a boosted decision tree/classifier that is suitable for use in accordance with various aspects. In operation 622, a processor may generate and/or execute a decision tree/classifier, collect a training sample from the execution of the decision tree/classifier, and generate a new classifier model (h1(x)) based on the training sample. The training sample may include information collected from previous observations or analysis of mobile device behaviors, software applications, or processes in the mobile device. The training sample and/or new classifier model (h1(x)) may be generated based the types of question or test conditions included in previous classifiers and/or based on accuracy or performance characteristics collected from the execution/application of previous data/behavior models or classifiers in a classifier module 208 of a behavior analyzer module 204. In operation 624, the processor may boost (or increase) the weight of the entries that were misclassified by the generated decision tree/classifier (h1(x)) to generate a second new tree/classifier (h2(x)). In an aspect, the training sample and/or new classifier model (h2(x)) may be generated based on the mistake rate of a previous execution or use (h1(x)) of a classifier. In an aspect, the training sample and/or new classifier model (h2(x)) may be generated based on attributes determined to have that contributed to the mistake rate or the misclassification of data points in the previous execution or use of a classifier.
In an aspect, the misclassified entries may be weighted based on their relatively accuracy or effectiveness. In operation 626, the processor may boost (or increase) the weight of the entries that were misclassified by the generated second tree/classifier (h2(x)) to generate a third new tree/classifier (h3(x)). In operation 628, the operations of 624-626 may be repeated to generate “t” number of new tree/classifiers (ht(x)).
By boosting or increasing the weight of the entries that were misclassified by the first decision tree/classifier (h1(x)), the second tree/classifier (h2(x)) may more accurately classify the entities that were misclassified by the first decision tree/classifier (h1(x)), but may also misclassify some of the entities that where correctly classified by the first decision tree/classifier (h1(x)). Similarly, the third tree/classifier (h3(x)) may more accurately classify the entities that were misclassified by the second decision tree/classifier (h2(x)) and misclassify some of the entities that where correctly classified by the second decision tree/classifier (h2(x)). That is, generating the family of tree/classifiers h1(x)−ht(x) may not result in a system that converges as a whole, but results in a number of decision trees/classifiers that may be executed in parallel.
FIG. 7 illustrates an example method 700 of generating classifier models that include boosted decision stumps and which may be used to intelligently and efficiently identifying actively malicious or poorly written software applications and/or suspicious or performance-degrading mobile device behaviors on the mobile device 102 without consuming an excessive amount of processing, memory, or energy resources of the mobile device. In operation 1 of method 700, an offline classifier in a network server may generate a full or robust classifier model based on information received from a cloud service/network. For example, the full classifier may include 100 boosted decision stumps that test forty (40) unique conditions. In operation 2 of method 700, the full classifier models may be sent to an analyzer/classifier module 208 in a mobile device 102. In operation 3 of method 700, the analyzer/classifier module 208 may generate a set of lean data/behavior models classifiers in the form of boosted decision stumps based on analyzing the full classifier model. This may be accomplished by performing “joint feature selection and culling” operations that allow the mobile device to: generate lean models on-the-fly without needing access to cloud training data; dynamically reconfigure the classifiers per application to enhance the classification accuracy; and to specify a deterministic complexity for each classifier (e.g., O(# of stumps)). The “joint feature selection and culling” operations may also include performing feature selection operations.
FIG. 8 illustrates an example boosted decision stumps 800 that may be generated by an aspect server processor and used by a device processor to generate lean classifier models in the mobile device. In the example illustrated in FIG. 8, the boosted decision stumps 800 include a plurality of decision nodes W1-W4 that each includes a question or a test condition (e.g., F1, F3, F5), that when executed or performed by a processor, may result in either a definitive binary answer (e.g., true or false, malicious or benign, etc.). Each decision nodes W1-W4 may also be associated with a weight value.
FIG. 8 also illustrates a method 802 of performing “joint feature selection and culling” operations discussed above with reference to FIG. 7. Method 802 may include the analyzer module of a mobile device determining that it needs to generate a lean classifier that tests two unique conditions, in which case the feature selection operations may include traversing the list of 100 boosted decision stumps until the first 2 unique conditions (e.g., F1 and F3 in FIG. 8) are discovered. The analyzer/classifier module 208 may then test only the conditions identified by feature selection operations (e.g., F1 and F3), which may be accomplished by traversing the entire list of 100 boosted decision stumps and deleting any stump that tests a different condition (e.g., F5). The remaining boosted decision stumps (i.e., stumps that tests conditions “F1” and “F3”) may be used as a lean classifier without re-training the data. The analyzer/classifier module 208 may apply the behavior information to each of the remaining boosted decision stumps (i.e., stumps that tests conditions “F1” and “F3”), compute a weighted average of all the answers received from the remaining stumps, and use the weighted average to determine if a mobile device behavior is malicious or benign.
Once the boosted decision stumps have been generated through the feature selection and culling process, the selected decision stumps may used as a classifier or behavior model that may be compared against current device states, settings and behaviors. Since the decision stumps are binary tests that are independent, the behavior analysis process of comparing observed behaviors, which may be summarized in a behavior vector, to the model can be performed in parallel. Also, since the stumps are very simple (basically binary), the processing to perform each stump is very simple and thus can be accomplished quickly with less processing overhead. Each decision stump yields an answer with a weight value, and the ultimate decision regarding whether behaviors are malicious or benign can be determined as the weighted sum of all the results, which is also a simple calculation.
The weight associated with a node may be computed based on information collected from previous observations or analysis of mobile device behaviors, software applications, or processes in the mobile device. The weight associated with each node may also be computed based on how many units of the corpus of data (e.g., cloud corpus of data or behavior vectors) are used to build the boosted decision stumps.
FIG. 9 illustrates example logical components and information flows in a behavior observer module 202 of a computing system configured to perform dynamic and adaptive observations in accordance with an aspect. The behavior observer module 202 may include an adaptive filter module 902, a throttle module 904, an observer mode module 906, a high-level behavior detection module 908, a behavior vector generator 910, and a secure buffer 912. The high-level behavior detection module 908 may include a spatial correlation module 914 and a temporal correlation module 916.
The observer mode module 906 may receive control information from various sources, which may include an analyzer unit (e.g., the behavior analyzer module 204 described above with reference to FIG. 2) and/or an application API. The observer mode module 906 may send control information pertaining to various observer modes to the adaptive filter module 902 and the high-level behavior detection module 908.
The adaptive filter module 902 may receive data/information from multiple sources, and intelligently filter the received information to generate a smaller subset of information selected from the received information. This filter may be adapted based on information or control received from the analyzer module, or a higher-level process communicating through an API. The filtered information may be sent to the throttle module 904, which may be responsible for controlling the amount of information flowing from the filter to ensure that the high-level behavior detection module 908 does not become flooded or overloaded with requests or information.
The high-level behavior detection module 908 may receive data/information from the throttle module 904, control information from the observer mode module 906, and context information from other components of the mobile device. The high-level behavior detection module 908 may use the received information to perform spatial and temporal correlations to detect or identify high level behaviors that may cause the device to perform at sub-optimal levels. The results of the spatial and temporal correlations may be sent to the behavior vector generator 910, which may receive the correlation information and generate a behavior vector that describes the behaviors of particular process, application, or sub-system. In an aspect, the behavior vector generator 910 may generate the behavior vector such that each high-level behavior of a particular process, application, or sub-system is an element of the behavior vector. In an aspect, the generated behavior vector may be stored in a secure buffer 912. Examples of high-level behavior detection may include detection of the existence of a particular event, the amount or frequency of another event, the relationship between multiple events, the order in which events occur, time differences between the occurrence of certain events, etc.
In the various aspects, the behavior observer module 202 may perform adaptive observations and control the observation granularity. That is, the behavior observer module 202 may dynamically identify the relevant behaviors that are to be observed, and dynamically determine the level of detail at which the identified behaviors are to be observed. In this manner, the behavior observer module 202 enables the system to monitor the behaviors of the mobile device at various levels (e.g., multiple coarse and fine levels). The behavior observer module 202 may enable the system to adapt to what is being observed. The behavior observer module 202 may enable the system to dynamically change the factors/behaviors being observed based on a focused subset of information, which may be obtained from a wide verity of sources.
As discussed above, the behavior observer module 202 may perform adaptive observation techniques and control the observation granularity based on information received from a variety of sources. For example, the high-level behavior detection module 908 may receive information from the throttle module 904, the observer mode module 906, and context information received from other components (e.g., sensors) of the mobile device. As an example, a high-level behavior detection module 908 performing temporal correlations might detect that a camera has been used and that the mobile device is attempting to upload the picture to a server. The high-level behavior detection module 908 may also perform spatial correlations to determine whether an application on the mobile device took the picture while the device was holstered and attached to the user's belt. The high-level behavior detection module 908 may determine whether this detected high-level behavior (e.g., usage of the camera while holstered) is a behavior that is acceptable or common, which may be achieved by comparing the current behavior with past behaviors of the mobile device and/or accessing information collected from a plurality of devices (e.g., information received from a crowd-sourcing server). Since taking pictures and uploading them to a server while holstered is an unusual behavior (as may be determined from observed normal behaviors in the context of being holstered), in this situation the high-level behavior detection module 908 may recognize this as a potentially threatening behavior and initiate an appropriate response (e.g., shutting off the camera, sounding an alarm, etc.).
In an aspect, the behavior observer module 202 may be implemented in multiple parts.
FIG. 10 illustrates in more detail logical components and information flows in a computing system 1000 implementing an aspect observer daemon. In the example illustrated in FIG. 10, the computing system 1000 includes a behavior detector 1002 module, a database engine 1004 module, and a behavior analyzer module 204 in the user space, and a ring buffer 1014, a filter rules 1016 module, a throttling rules 1018 module, and a secure buffer 1020 in the kernel space. The computing system 1000 may further include an observer daemon that includes the behavior detector 1002 and the database engine 1004 in the user space, and the secure buffer manager 1006, the rules manager 1008, and the system health monitor 1010 in the kernel space.
The various aspects may provide cross-layer observations on mobile devices encompassing webkit, SDK, NDK, kernel, drivers, and hardware in order to characterize system behavior. The behavior observations may be made in real time.
The observer module may perform adaptive observation techniques and control the observation granularity. As discussed above, there are a large number (i.e., thousands) of factors that could contribute to the mobile device's degradation, and it may not be feasible to monitor/observe all of the different factors that may contribute to the degradation of the device's performance. To overcome this, the various aspects dynamically identify the relevant behaviors that are to be observed, and dynamically determine the level of detail at which the identified behaviors are to be observed.
FIG. 11 illustrates an example method 1100 for performing dynamic and adaptive observations in accordance with an aspect. In block 1102, the mobile device processor may perform coarse observations by monitoring/observing a subset of large number factors/behaviors that could contribute to the mobile device's degradation. In block 1103, the mobile device processor may generate a behavior vector characterizing the coarse observations and/or the mobile device behavior based on the coarse observations. In block 1104, the mobile device processor may identify subsystems, processes, and/or applications associated with the coarse observations that may potentially contribute to the mobile device's degradation. This may be achieved, for example, by comparing information received from multiple sources with contextual information received from sensors of the mobile device. In block 1106, the mobile device processor may perform behavioral analysis operations based on the coarse observations. In aspect, as part of blocks 1103 and 1104, the mobile device processor may perform one or more of the operations discussed above with reference to FIGS. 2-10.
In determination block 1108, the mobile device processor may determine whether suspicious behaviors or potential problems can be identified and corrected based on the results of the behavioral analysis. When the mobile device processor determines that the suspicious behaviors or potential problems can be identified and corrected based on the results of the behavioral analysis (i.e., determination block 1108=“Yes”), in block 1118, the processor may initiate a process to correct the behavior and return to block 1102 to perform additional coarse observations.
When the mobile device processor determines that the suspicious behaviors or potential problems can not be identified and/or corrected based on the results of the behavioral analysis (i.e., determination block 1108=“No”), in determination block 1109 the mobile device processor may determine whether there is a likelihood of a problem. In an aspect, the mobile device processor may determine that there is a likelihood of a problem by computing a probability of the mobile device encountering potential problems and/or engaging in suspicious behaviors, and determining whether the computed probability is greater than a predetermined threshold. When the mobile device processor determines that the computed probability is not greater than the predetermined threshold and/or there is not a likelihood that suspicious behaviors or potential problems exist and/or are detectable (i.e., determination block 1109=“No”), the processor may return to block 1102 to perform additional coarse observations.
When the mobile device processor determines that there is a likelihood that suspicious behaviors or potential problems exist and/or are detectable (i.e., determination block 1109=“Yes”), in block 1110, the mobile device processor may perform deeper logging/observations or final logging on the identified subsystems, processes or applications. In block 1112, the mobile device processor may perform deeper and more detailed observations on the identified subsystems, processes or applications. In block 1114, the mobile device processor may perform further and/or deeper behavioral analysis based on the deeper and more detailed observations. In determination block 1108, the mobile device processor may again determine whether the suspicious behaviors or potential problems can be identified and corrected based on the results of the deeper behavioral analysis. When the mobile device processor determines that the suspicious behaviors or potential problems can not be identified and corrected based on the results of the deeper behavioral analysis (i.e., determination block 1108=“No”), the processor may repeat the operations in blocks 1110-1114 until the level of detail is fine enough to identify the problem or until it is determined that the problem cannot be identified with additional detail or that no problem exists.
When the mobile device processor determines that the suspicious behaviors or potential problems can be identified and corrected based on the results of the deeper behavioral analysis (i.e., determination block 1108=“Yes”), in block 1118, the mobile device processor may perform operations to correct the problem/behavior, and the processor may return to block 1102 to perform additional operations.
In an aspect, as part of blocks 1102-1118 of method 1100, the mobile device processor may perform real-time behavior analysis of the system's behaviors to identify suspicious behavior from limited and coarse observations, to dynamically determine the behaviors to observe in greater detail, and to dynamically determine the precise level of detail required for the observations. This enables the mobile device processor to efficiently identify and prevent problems from occurring, without requiring the use of a large amount of processor, memory, or battery resources on the device.
The various aspects may be implemented on a variety of computing devices, an example of which is illustrated in FIG. 12 in the form of a smartphone. A smartphone 1200 may include a processor 1202 coupled to internal memory 1204, a display 1212, and to a speaker 1214. Additionally, the smartphone 1200 may include an antenna for sending and receiving electromagnetic radiation that may be connected to a wireless data link and/or cellular telephone transceiver 1208 coupled to the processor 1202. Smartphones 1200 typically also include menu selection buttons or rocker switches 1220 for receiving user inputs.
A typical smartphone 1200 also includes a sound encoding/decoding (CODEC) circuit 1206, which digitizes sound received from a microphone into data packets suitable for wireless transmission and decodes received sound data packets to generate analog signals that are provided to the speaker to generate sound. Also, one or more of the processor 1202, wireless transceiver 1208 and CODEC 1206 may include a digital signal processor (DSP) circuit (not shown separately).
Portions of the aspect methods may be accomplished in a client-server architecture with some of the processing occurring in a server, such as maintaining databases of normal operational behaviors, which may be accessed by a mobile device processor while executing the aspect methods. Such aspects may be implemented on any of a variety of commercially available server devices, such as the server 1300 illustrated in FIG. 13. Such a server 1300 typically includes a processor 1301 coupled to volatile memory 1302 and a large capacity nonvolatile memory, such as a disk drive 1303. The server 1300 may also include a floppy disc drive, compact disc (CD) or DVD disc drive 1304 coupled to the processor 1301. The server 1300 may also include network access ports 1306 coupled to the processor 1301 for establishing data connections with a network 1305, such as a local area network coupled to other broadcast system computers and servers.
The processors 1202, 1301 may be any programmable microprocessor, microcomputer or multiple processor chip or chips that can be configured by software instructions (applications) to perform a variety of functions, including the functions of the various aspects described below. In some mobile devices, multiple processors 1202 may be provided, such as one processor dedicated to wireless communication functions and one processor dedicated to running other applications. Typically, software applications may be stored in the internal memory 1204, 1302, 1303 before they are accessed and loaded into the processor 1202, 1301. The processor 1202, 1301 may include internal memory sufficient to store the application software instructions.
The term “performance degradation” is used in this application to refer to a wide variety of undesirable mobile device operations and characteristics, such as longer processing times, slower real time responsiveness, lower battery life, loss of private data, malicious economic activity (e.g., sending unauthorized premium SMS message), denial of service (DoS), operations relating to commandeering the mobile device or utilizing the phone for spying or botnet activities, etc.
Computer program code or “program code” for execution on a programmable processor for carrying out operations of the various aspects may be written in a high level programming language such as C, C++, C#, Smalltalk, Java, JavaScript, Visual Basic, a Structured Query Language (e.g., Transact-SQL), Perl, or in various other programming languages. Program code or programs stored on a computer readable storage medium as used in this application may refer to machine language code (such as object code) whose format is understandable by a processor.
Many mobile computing devices operating system kernels are organized into a user space (where non-privileged code runs) and a kernel space (where privileged code runs). This separation is of particular importance in Android® and other general public license (GPL) environments where code that is part of the kernel space must be GPL licensed, while code running in the user-space may not be GPL licensed. It should be understood that the various software components/modules discussed here may be implemented in either the kernel space or the user space, unless expressly stated otherwise.
The foregoing method descriptions and the process flow diagrams are provided merely as illustrative examples and are not intended to require or imply that the steps of the various aspects must be performed in the order presented. As will be appreciated by one of skill in the art the order of steps in the foregoing aspects may be performed in any order. Words such as “thereafter,” “then,” “next,” etc. are not intended to limit the order of the steps; these words are simply used to guide the reader through the description of the methods. Further, any reference to claim elements in the singular, for example, using the articles “a,” “an” or “the” is not to be construed as limiting the element to the singular.
As used in this application, the terms “component,” “module,” “system,” “engine,” “generator,” “manager” and the like are intended to include a computer-related entity, such as, but not limited to, hardware, firmware, a combination of hardware and software, software, or software in execution, which are configured to perform particular operations or functions. For example, a component may be, but is not limited to, a process running on a processor, a processor, an object, an executable, a thread of execution, a program, and/or a computer. By way of illustration, both an application running on a computing device and the computing device may be referred to as a component. One or more components may reside within a process and/or thread of execution and a component may be localized on one processor or core and/or distributed between two or more processors or cores. In addition, these components may execute from various non-transitory computer readable media having various instructions and/or data structures stored thereon. Components may communicate by way of local and/or remote processes, function or procedure calls, electronic signals, data packets, memory read/writes, and other known network, computer, processor, and/or process related communication methodologies.
The various illustrative logical blocks, modules, circuits, and algorithm steps described in connection with the aspects disclosed herein may be implemented as electronic hardware, computer software, or combinations of both. To clearly illustrate this interchangeability of hardware and software, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present invention.
The hardware used to implement the various illustrative logics, logical blocks, modules, and circuits described in connection with the aspects disclosed herein may be implemented or performed with a general purpose processor, a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field programmable gate array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein. A general-purpose processor may be a multiprocessor, but, in the alternative, the processor may be any conventional processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing devices, e.g., a combination of a DSP and a multiprocessor, a plurality of multiprocessors, one or more multiprocessors in conjunction with a DSP core, or any other such configuration. Alternatively, some steps or methods may be performed by circuitry that is specific to a given function.
In one or more exemplary aspects, the functions described may be implemented in hardware, software, firmware, or any combination thereof. If implemented in software, the functions may be stored as one or more processor-executable instructions or code on a non-transitory computer-readable storage medium or non-transitory processor-readable storage medium. The steps of a method or algorithm disclosed herein may be embodied in a processor-executable software module which may reside on a non-transitory computer-readable or processor-readable storage medium. Non-transitory computer-readable or processor-readable storage media may be any storage media that may be accessed by a computer or a processor. By way of example but not limitation, such non-transitory computer-readable or processor-readable media may include RAM, ROM, EEPROM, FLASH memory, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium that may be used to store desired program code in the form of instructions or data structures and that may be accessed by a computer. Disk and disc, as used herein, includes compact disc (CD), laser disc, optical disc, digital versatile disc (DVD), floppy disk, and blu-ray disc where disks usually reproduce data magnetically, while discs reproduce data optically with lasers. Combinations of the above are also included within the scope of non-transitory computer-readable and processor-readable media. Additionally, the operations of a method or algorithm may reside as one or any combination or set of codes and/or instructions on a non-transitory processor-readable medium and/or computer-readable medium, which may be incorporated into a computer program product.
The preceding description of the disclosed aspects is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these aspects will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other aspects without departing from the spirit or scope of the invention. Thus, the present invention is not intended to be limited to the aspects shown herein but is to be accorded the widest scope consistent with the following claims and the principles and novel features disclosed herein.

## Claims

1. A method of generating models in a mobile device, comprising:
receiving in a processor of the mobile device from a server computing device a full classifier model that includes a finite state machine, the finite state machine including information that is suitable for expression as a plurality of boosted decision stumps, each boosted decision stump including a test condition and a weight value;
generating, by the processor of the mobile device, an ordered list of boosted decision stumps by converting the finite state machine included in the received full classifier model into the plurality of boosted decision stumps;
culling, by the processor of the mobile device, the generated ordered list of boosted decision stumps to generate a lean classifier model in the mobile device, the culling comprising:
determining a number of different test conditions to evaluate in the mobile device in order to classify a mobile device behavior without consuming an excessive amount of energy resources of the mobile device;
generating a list of test conditions that includes the determined number of different test conditions by sequentially traversing the generated ordered list of boosted decision stumps and inserting the test condition associated with each sequentially traversed boosted decision stump into the list of test conditions until the list of test conditions includes the determined number of different test conditions; and
generating the lean classifier model to include the boosted decision stumps that test one of a plurality of test conditions included in the generated list of test conditions;

applying, by the processor of the mobile device, a mobile device behavior vector to the generated lean classifier model to generate results; and
using, by the processor of the mobile device, the generated results to classify the mobile device behavior.

2. The method of claim 1, wherein using the generated results to classify the mobile device behavior comprises using the generated results to classify the mobile device behavior as not benign.

3. The method of claim 1, wherein applying the mobile device behavior vector to the generated lean classifier model too generate the results comprises:
applying collected behavior information included in the mobile device behavior vector to each boosted decision stump in the lean classifier model;
computing a weighted average of the results of applying the collected behavior information to each boosted decision stump in the lean classifier model; and
comparing the weighted average to a threshold value.

4. The method of claim 1, wherein:
generating the lean classifier model comprises generating a family of lean classifier models based on the boosted decision stumps included in the generated ordered list of boosted decision stumps;
the generated family of lean classifier models including the lean classifier model and a plurality of additional lean classifier models; and
each of the plurality of additional lean classifier models includes a different number of different test conditions.

5. The method of claim 1, wherein generating the lean classifier model comprises:
generating a plurality of lean classifier models that each includes a decision stump that tests a first condition using a different weight value and a different threshold value.

6. The method of claim 1, further comprising:
re-computing threshold values associated with the boosted decision stumps in a plurality of lean classifier models generated in the mobile device based on the received full classifier model.

7. The method of claim 1, further comprising:
re-computing weight values associated with the boosted decision stumps in a plurality of lean classifier models generated in the mobile device based on the received full classifier model.

8. The method of claim 1, further comprising:
generating the full classifier model in a server by:
receiving in the server a corpus of information on mobile device behaviors; and
generating the finite state machine based on the corpus of information to include data that is suitable for conversion into the plurality of boosted decision stumps; and

sending the finite state machine to the mobile device as the full classifier model.

9. The method of claim 8, wherein:
each test condition is associated with a probability value;
each probability value identifies a likelihood that its associated test condition will enable the mobile device to determine whether the mobile device behavior is benign; and
the method further comprises:
ordering the plurality of boosted decision stumps in the finite state machine based on the probability values prior to sending the finite state machine to the mobile device as the full classifier model.

10. A mobile computing device, comprising:
a processor configured with processor-executable instructions to perform operations comprising:
receiving a full classifier model that includes a finite state machine, the finite state machine including information that is suitable for expression as a plurality of boosted decision stumps, each boosted decision stump including a test condition and a weight value;
generating an ordered list of boosted decision stumps by converting the finite state machine included in the received full classifier model into the plurality of boosted decision stumps;
culling the generated ordered list of boosted decision stumps to generate a lean classifier model, the culling comprising:
determining a number of different test conditions to evaluate in order to classify a mobile device behavior without consuming an excessive amount of energy resources;
generating a list of test conditions that includes the determined number of different test conditions by sequentially traversing the generated ordered list of boosted decision stumps and inserting the test condition associated with each sequentially traversed boosted decision stump into the list of test conditions until the list of test conditions includes the determined number of different test conditions; and
generating the lean classifier model to include the boosted decision stumps that test one of a plurality of test conditions included in the generated list of test conditions;

applying a mobile device behavior vector to the generated lean classifier model to generate results; and
using the generated results to classify the mobile device behavior.

11. The mobile computing device of claim 10, wherein the processor is configured with processor-executable instructions to perform operations such that applying the mobile device behavior vector to the generated lean classifier model to generate the results comprises:
applying collected behavior information included in the mobile device behavior vector to each boosted decision stump in the lean classifier model;
computing a weighted average of the results of applying the collected behavior information to each boosted decision stump in the lean classifier model; and
comparing the weighted average to a threshold value.

12. The mobile computing device of claim 10, wherein the processor is configured with processor-executable instructions to perform operations such that generating the lean classifier model comprises:
generating a family of lean classifier models based on the boosted decision stumps included in the generated ordered list of boosted decision stumps, the family of lean classifier models including the lean classifier model and a plurality of additional lean classifier models, each of the plurality of additional lean classifier models including a different number of different test conditions.

13. The mobile computing device of claim 10, wherein the processor is configured with processor-executable instructions to perform operations such that generating a lean classifier model comprises:
generating a plurality of lean classifier models that each includes a decision stump that tests a first condition using a different weight value and a different threshold value.

14. The mobile computing device of claim 10, wherein the processor is configured with processor-executable instructions to perform operations further comprising:
re-computing threshold values and weight values associated with the boosted decision stumps in a plurality of lean classifier models generated based on the received full classifier model.

15. A non-transitory computer readable storage medium having stored thereon processor-executable software instructions configured to cause a processor in a mobile device to perform operations comprising:
receiving a full classifier model that includes a finite state machine, the finite state machine including information that is suitable for expression as a plurality of boosted decision stumps, each boosted decision stump including a test condition and a weight value;
generating an ordered list of boosted decision stumps by converting the finite state machine included in the received full classifier model into the plurality of boosted decision stumps;
culling the generated ordered list of boosted decision stumps to generate a lean classifier model, the culling comprising:
determining a number of different test conditions to evaluate in order to classify a mobile device behavior without consuming an excessive amount of energy resources;
generating a list of test conditions that includes the determined number of different test conditions by sequentially traversing the generated ordered list of boosted decision stumps and inserting the test condition associated with each sequentially traversed boosted decision stump into the list of test conditions until the list of test conditions includes the determined number of different test conditions; and
generating the lean classifier model to include the boosted decision stumps that test one of a plurality of test conditions included in the generated list of test conditions;

applying a mobile device behavior vector to the generated lean classifier model to generate results; and
using the generated results to classify the mobile device behavior.

16. The non-transitory computer readable storage medium of claim 15, wherein the stored processor-executable software instructions are configured to cause a processor in the mobile device to perform operations such that applying the mobile device behavior vector to the generated lean classifier model to generate the results comprises:
applying collected behavior information included in the mobile device behavior vector to each boosted decision stump in the lean classifier model;
computing a weighted average of the results of applying the collected behavior information to each boosted decision stump in the lean classifier model; and
comparing the weighted average to a threshold value.

17. The non-transitory computer readable storage medium of claim 15, wherein the stored processor-executable software instructions are configured to cause a processor in the mobile device to perform operations such that generating the lean classifier model comprises:
generating a family of lean classifier models based on the boosted decision stumps included in the generated ordered list of boosted decision stumps,
the family of lean classifier models including the lean classifier model and a plurality of additional lean classifier models,
each of the plurality of additional lean classifier models including a different number of different test conditions.

18. The non-transitory computer readable storage medium of claim 15, wherein the stored processor-executable software instructions are configured to cause a processor in the mobile device to perform operations such that generating a lean classifier model comprises:
generating a plurality of lean classifier models that each includes a decision stump that tests a first condition using a different weight value and a different threshold value.

19. The non-transitory computer readable storage medium of claim 15, wherein the stored processor-executable software instructions are configured to cause a processor in the mobile device to perform operations further comprising:
re-computing threshold values and weight values associated with the boosted decision stumps in a plurality of lean classifier models generated based on the received full classifier model.

20. A system, comprising:
a mobile device comprising a device processor; and
a server configured with server-executable instructions to perform operations comprising:
receiving a corpus of information on mobile device behaviors;
generating, based on the corpus of information, a finite state machine including data that is suitable for conversion into a plurality of boosted decision stumps that each includes a test condition and a weight value; and
sending the finite state machine to the mobile device as a full classifier model,

wherein the device processor in the mobile device is configured with processor-executable instructions to perform operations comprising:
receiving the full classifier model;
generating an ordered list of boosted decision stumps by converting the finite state machine included in the received full classifier model into the plurality of boosted decision stumps;
culling the generated ordered list of boosted decision stumps to generate a lean classifier model, the culling comprising:
determining a number of different test conditions to evaluate in order to classify a mobile device behavior without consuming an excessive amount of energy resources of the mobile device;
generating a list of test conditions that includes the determined number of different test conditions by sequentially traversing the generated ordered list of boosted decision stumps and inserting the test condition associated with each sequentially traversed boosted decision stump into the list of test conditions until the list of test conditions includes the determined number of different test conditions; and
generating the lean classifier model to include the boosted decision stumps that test one of a plurality of test conditions included in the generated list of test conditions;

applying a mobile device behavior vector to the generated lean classifier model to generate results; and
using the generated results to classify the mobile device behavior.

21. The system of claim 20, wherein the device processor is configured with processor-executable instructions to perform operations such that applying the mobile device behavior vector to the generated lean classifier model to generate the results comprises:
applying collected behavior information included in the mobile device behavior vector to each boosted decision stump in the lean classifier model;
computing a weighted average of the results of applying the collected behavior information to each boosted decision stump in the lean classifier model; and
comparing the weighted average to a threshold value.

22. The system of claim 20, wherein the device processor is configured with processor-executable instructions to perform operations such that generating the lean classifier model comprises:
generating a family of lean classifier models based on the boosted decision stumps included in the generated ordered list of boosted decision stumps, the family of lean classifier models including the lean classifier model and a plurality of additional lean classifier models, each of the plurality of additional lean classifier models including a different number of different test conditions.

23. The system of claim 20, wherein the device processor is configured with processor-executable instructions to perform operations such that generating the lean classifier comprises:
generating a plurality of lean classifier models that each includes a decision stump that tests a first condition using a different weight value and a different threshold value.

24. The system of claim 23, wherein the device processor is configured with processor-executable instructions to perform operations further comprising:
re-computing threshold values and weight values associated with the boosted decision stumps in the plurality of lean classifier models generated in the mobile device based on the received full classifier model.

25. The system of claim 20, wherein:
the server is configured with server-executable instructions to perform operations such that generating the finite state machine includes generating the finite state machine so that;
each test condition is associated with a probability value;
each probability value identifies a likelihood that its associated test condition will enable the mobile device to determine whether the mobile device behavior is benign, and

the server is configured with server-executable instructions to perform operations further comprising:
ordering the plurality of boosted decision stumps in the finite state machine based on the probability values prior to sending the finite state machine to the mobile device as the fill classifier model.