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

Patent metadata

Field	Value
Publication number	US-9684870-B2
Application number	US-201314090261-A
Country	US
Kind code	B2
Filing date	Nov 26, 2013
Priority date	Jan 2, 2013
Publication date	Jun 20, 2017
Grant date	Jun 20, 2017

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.

First claim

What is claimed is:

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

Assignees

• Qualcomm Inc

Inventors

• Fawaz Kassem
• Sridhara Vinay
• Gupta Rajarshi

Classifications

• G06N5/043 Primary

  Distributed expert systems; Blackboards · CPC title

• G06N5/025

  Extracting rules from data · CPC title