Predicting and using utility of script execution in functional web crawling and other crawling

• US 10,649,740 B2
• Filed: 01/15/2015
• Issued: 05/12/2020
• Est. Priority Date: 01/15/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Pistoia, Marco, Tripp, Omer, Sperling, Shahar
• Primary Examiner(s): Jalil, Neveen Abel
• Assistant Examiner(s): Baker, Irene
• Application Number:
  US14/597,749
• Publication Number:
  US 20160210361A1
• Time in Patent Office: 1,944 Days
• Field of Search: None
• CPC Class Codes: G06F 16/986 Document structures and storage, e.g. HTML extensions
• CPC Class Codes: G06F 8/31 Programming languages or programming paradigms
• CPC Class Codes: G06F 9/45529 Embedded in an application, e.g. JavaScript in a Web browser

Abstract

A program is executed that includes multiple script functions. For a selected script function, the following are performed during program execution. It is determined whether the selected script function should or should not be executed based on a utility corresponding to the selected script function. The utility was determined prior to determining whether the selected script function should be executed. The selected script function is executed in response to a determination the selected script function should be executed. Execution of the selected script function is skipped in response to a determination the selected script function should not be executed. These techniques may be applied in real-time to crawl a program such as a webpage or may be applied using offline learning followed by a real-time crawling of the program. Apparatus, methods, and program products are disclosed.

Claims

1. A computer-implemented method, comprising:

performing, by a computer system serving webpages through a network to one or more client computers, analysis of a web application program, the analysis comprising;

training the computer system to learn which script functions to execute, wherein training the computer system includes populating a database comprising of mappings between feature vectors and corresponding utilities, wherein each feature vector corresponds to a script function, wherein each feature vector is generated using a specification set of features, wherein each feature vector is based on syntactic and document object model (DOM) related characteristics of the script function, and wherein each utility corresponds to one or more descriptions of function behaviors observed during execution of the script function;

executing, by the computer system, the web application program comprising markup language for a webpage, the markup language comprising a plurality of script functions, the executing comprising performing the following by the computer system during program execution;

crawling the web application program code while the web application program is being executed;

extracting and reducing the plurality of script functions encountered from the web application program code based on extraction rules, wherein the extraction and reduction process comprises of modeling the script function as an Abstract Syntax Tree (AST);

for each script function of the plurality of script functions, reducing the script function to a feature vector using the specification set of features and basing the feature vector on syntactic and DOM related characteristics of the script function;

predicting, for each selected script function of the plurality of script functions, whether the selected script function should or should not be executed by determining whether the feature vector corresponding to the selected script function is a known feature vector in the database;

in response to determining the feature vector is not a known feature vector in the database;

(a) executing the selected script function in order to determine the utility of the selected script function, wherein determining the utility of the selected script function is based on one or more descriptions of function behaviors observed during execution of the selected script function, and wherein the function behavior of the selected script function corresponds to at least one of;

a characterization of relevant DOM effects, a flag or confidence level indicating whether Asynchronous JavaScript+XML (AJAX) calls may be executed, or a measure of execution cost; and

(b) adding an entry comprising a mapping of the feature vector and the utility to the database;

in response to determining the feature vector is a known feature vector in the database;

(a) selecting an entry in the database matching the feature vector;

(b) accessing the utility for the selected entry, wherein the utility was determined previously during training of the computer system;

(c) using a prediction model, determining whether to execute the selected script function or skip executing the selected script function based on the utility being sufficiently high or not sufficiently high;

(d) in response to determining the utility is not sufficiently high, skipping execution of the selected script function; and

(e) in response to determining the utility is sufficiently high, (i) executing the selected script function; and

(ii) updating the prediction model in response to a predicted behavior of the selected script function not being compatible with an observed behavior of the selected script function,

wherein updating the prediction model comprises establishing a new mapping between the feature vector and the utility, the updating the prediction model further comprising instantiating the prediction model with a similarity algorithm incrementally or with a new similarity algorithm;

rendering the webpage in accordance with determining, based on the prediction model, whether the selected script function should be executed or should not be executed, wherein determining the selected script function should not be executed results in skipping execution of the selected script function; and

serving the rendered webpage through the network to the one or more client computers.

2. The computer-implemented method of claim 1, wherein determining whether the selected script function should or should not be executed based on the utility corresponding to the selected script function further comprises:

determining the selected script function should be executed when the utility of the selected script function is not sufficiently high and a predicted cost of execution being beneath a threshold.

3. The computer-implemented method of claim 1, wherein the selected script function is a first selected script function and wherein the method further comprises, prior to determining whether the first selected script function should or should not be executed:

determining a feature vector for a second selected script function;

determining whether the feature vector is a known feature vector stored in a database;

in response to a determination that the feature vector is not a known feature vector stored in the database, executing the second selected script function, determining the utility of the second selected script function based at least on one or more function behaviors observed during execution of the second selected script function, and adding an entry comprising a mapping of the feature vector and the utility, to the database.

4. The computer-implemented method of claim 3, wherein the first and second selected script functions are different script functions with the same corresponding feature vectors.

5. The computer-implemented method of claim 3, wherein the first and second selected script functions are different script functions with corresponding feature vectors that are similar based on a similarity measure.

6. The computer-implemented method of claim 3, performed prior to the program being executed, and performed using a plurality of different web application programs that do not include the web application program being executed.

7. The computer-implemented method of claim 1, wherein determining whether the feature vector is not or is a known feature vector stored in a database further comprises determining whether the feature vector is an exact match of a feature vector stored in the database, determining the feature vector is not a known feature vector in response to the feature vector not being an exact match of a feature vector stored in the database, and determining the feature vector is a known feature vector in response to the feature vector being an exact match of a feature vector stored in the database.

8. The computer-implemented method of claim 1, wherein determining whether the feature vector is not or is a known feature vector stored in a database further comprises determining whether the feature vector is similar to a feature vector stored in the database by using a similarity measure between the feature vectors, determining the feature vector is not a known feature vector in response to the feature vectors not being similar based on a similarity threshold, and determining the feature vector is a known feature vector in response to the feature vectors being similar based on the similarity threshold.

11. The computer-implemented method of claim 1, wherein training the computer system to learn which webpage script functions to execute further comprises mapping between a function behavior and a utility.

12. The computer-implemented method of claim 11, wherein the function behavior is execution of an AJAX function.

13. The computer-implemented method of claim 1, wherein the training the computer system to learn which script functions to execute further comprises:

selecting a website from a set of provided websites;

extracting and reducing a plurality of script functions encountered from a webpage of the website based on extraction rules, wherein the extraction and reduction process comprises of modeling the script function as an AST;

for each selected script function of the plurality of script functions, reducing the selected script function into a feature vector using a specification set of features including at least one of;

a regular description of a name of the selected script function, a signature of the selected script function, characteristics of the AST of the selected script function, or global DOM elements the selected script function accesses or manipulates; and

basing the feature vector on syntactic and DOM related characteristics of the script function;

in response to determining the feature vector is not a known feature vector in a database;

(a) executing the selected script function in order to determine a utility of the function, wherein determining the utility of the selected script function is based on one or more descriptions of function behaviors observed during execution of the selected script function, and wherein a function behavior of the selected script function corresponds to at least one of;

a characterization of relevant DOM effects, a flag or confidence level indicating whether AJAX calls may be executed, or a measure of execution cost; and

(b) adding an entry comprising a mapping of the feature vector and the utility to the database;

in response to determining the feature vector is a known feature vector in the database;

(a) selecting an entry in the database matching the feature vector;

(b) accessing the utility for the selected entry, wherein the utility was determined previously during training of the computer system;

(c) in response to determining the utility is not sufficiently high, skipping execution of the selected script function; and

(d) in response to determining the utility is sufficiently high, executing the selected script function;

continuing to execute the program until the one or more webpages have been crawled; and

continuing to select other websites from the set of provided websites and updating the database until all of the websites in the set of provided websites have been selected and their corresponding one or more webpages have been crawled.

9. A computer program product comprising a computer-readable storage medium comprising computer-readable code embodied thereon, where execution of the computer-readable code by at least one processor causes an apparatus to perform operations comprising:

performing, by a computer system serving webpages through a network to one or more client computers, analysis of a web application program, the analysis comprising;

training the computer system to learn which script functions to execute, wherein training the computer system includes populating a database comprising of mappings between feature vectors and corresponding utilities, wherein each feature vector corresponds to a script function, wherein each feature vector is generated using a specification set of features, wherein each feature vector is based on syntactic and document object model (DOM) related characteristics of the script function, and wherein each utility corresponds to one or more descriptions of function behaviors observed during execution of the script function;

executing, by the computer system, the web application program comprising markup language for a webpage, the markup language comprising a plurality of script functions, the executing comprising performing the following by the computer system during program execution;

crawling the web application program code while the web application program is being executed;

extracting and reducing the plurality of script functions encountered from the web application program code based on extraction rules, wherein the extraction and reduction process comprises of modeling the script function as an Abstract Syntax Tree (AST);

for each script function of the plurality of script functions, reducing the script function to a feature vector using the specification set of features and basing the feature vector on syntactic and DOM related characteristics of the script function;

predicting, for each selected script function of the plurality of script functions, whether the selected script function should or should not be executed by determining whether the feature vector corresponding to the selected script function is a known feature vector in the database;

in response to determining the feature vector is not a known feature vector in the database;

(a) executing the selected script function in order to determine the utility of the selected script function, wherein determining the utility of the selected script function is based on one or more descriptions of function behaviors observed during execution of the selected script function, and wherein the function behavior of the selected script function corresponds to at least one of;

a characterization of relevant DOM effects, a flag or confidence level indicating whether Asynchronous JavaScript+XML (AJAX) calls may be executed, or a measure of execution cost; and

(b) adding an entry comprising a mapping of the feature vector and the utility to the database;

in response to determining the feature vector is a known feature vector in the database;

(a) selecting an entry in the database matching the feature vector;

(b) accessing the utility for the selected entry, wherein the utility was determined previously during training of the computer system;

(c) using a prediction model, determining whether to execute the selected script function or skip executing the selected script function based on the utility being sufficiently high or not sufficiently high;

(d) in response to determining the utility is not sufficiently high, skipping execution of the selected script function; and

(e) in response to determining the utility is sufficiently high, (i) executing the selected script function; and

(ii) updating the prediction model in response to a predicted behavior of the selected script function not being compatible with an observed behavior of the selected script function,

wherein updating the prediction model comprises establishing a new mapping between the feature vector and the utility, the updating the prediction model further comprising instantiating the prediction model with a similarity algorithm incrementally or with a new similarity algorithm;

rendering the webpage in accordance with determining, based on the prediction model, whether the selected script function should be executed or should not be executed, wherein determining the selected script function should not be executed results in skipping execution of the selected script function; and

serving the rendered webpage through the network to the one or more client computers.

10. The computer program product of claim 9, wherein the selected script function is a first selected script function and wherein the one or more processors are further configured by execution of the computer-readable code to cause the apparatus to perform, prior to determining whether the first selected script function should or should not be executed, the following:

determining a feature vector for a second selected script function;

determining whether the feature vector is a known feature vector stored in a database;

in response to a determination that the feature vector is not a known feature vector stored in the database, executing the second selected script function, determining the utility of the second selected script function based at least on one or more descriptions of function behaviors observed during execution of the second selected script function, and adding an entry comprising a mapping of the feature vector and the utility to the database.

14. The computer program product of claim 9, wherein the training the computer system to learn which script functions to execute further comprises:

selecting a website from a set of provided websites;

extracting and reducing a plurality of script functions encountered from a webpage of the website based on extraction rules, wherein the extraction and reduction process comprises of modeling the script function as an AST;

for each selected script function of the plurality of script functions, reducing the selected script function into a feature vector using a specification set of features including at least one of;

a regular description of a name of the selected script function, a signature of the selected script function, characteristics of the AST of the selected script function, or global DOM elements the selected script function accesses or manipulates; and

basing the feature vector on syntactic and DOM related characteristics of the script function;

in response to determining the feature vector is not a known feature vector in a database;

(a) executing the selected script function in order to determine a utility of the function, wherein determining the utility of the selected script function is based on one or more descriptions of function behaviors observed during execution of the selected script function, and wherein a function behavior of the selected script function corresponds to at least one of;

a characterization of relevant DOM effects, a flag or confidence level indicating whether AJAX calls may be executed, or a measure of execution cost; and

(b) adding an entry comprising a mapping of the feature vector and the utility to the database;

in response to determining the feature vector is a known feature vector in the database;

(a) selecting an entry in the database matching the feature vector;

(b) accessing the utility for the selected entry, wherein the utility was determined previously during training of the computer system;

(c) in response to determining the utility is not sufficiently high, skipping execution of the selected script function; and

(d) in response to determining the utility is sufficiently high, executing the selected script function;

continuing to execute the program until the one or more webpages have been crawled;

continuing to select other websites from the set of provided websites and updating the database until all of the websites in the set of provided websites have been selected and their corresponding one or more webpages have been crawled.