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

• US 9,684,870 B2
• Filed: 11/26/2013
• Issued: 06/20/2017
• Est. Priority Date: 01/02/2013
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Fawaz, Kassem, Sridhara, Vinay, Gupta, Rajarshi
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Tran, Mai T
• Application Number:
  US14/090,261
• Publication Number:
  US 20140188781A1
• Time in Patent Office: 1,302 Days
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: G06N 5/043 Distributed expert systems; Blackboards

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.

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.