Learning DOM Trees of Web Pages by Subpath Kernel and Detecting Fake e-Commerce Sites

Abstract

The subpath kernel is a class of positive definite kernels defined over trees, which has the following advantages for the purposes of classification, regression and clustering: it can be incorporated into a variety of powerful kernel machines including SVM; It is invariant whether input trees are ordered or unordered; It can be computed by significantly fast linear-time algorithms; And, finally, its excellent learning performance has been proven through intensive experiments in the literature. In this paper, we leverage recent advances in tree kernels to solve real problems. As an example, we apply our method to the problem of detecting fake e-commerce sites. Although the problem is similar to phishing site detection, the fact that mimicking existing authentic sites is harmful for fake e-commerce sites marks a clear difference between these two problems. We focus on fake e-commerce site detection for three reasons: e-commerce fraud is a real problem that companies and law enforcement have been cooperating to solve; Inefficiency hampers existing approaches because datasets tend to be large, while subpath kernel learning overcomes these performance challenges; And we offer increased resiliency against attempts to subvert existing detection methods through incorporating robust features that adversaries cannot change: the DOM-trees of web-sites. Our real-world results are remarkable: our method has exhibited accuracy as high as 0.998 when training SVM with 1000 instances and evaluating accuracy for almost 7000 independent instances. Its generalization efficiency is also excellent: with only 100 training instances, the accuracy score reached 0.996.

1. Introduction

Tree-structured data has been the focus of a great deal of machine learning research for a long time. In 1979, Taï [1] extended Levenshtein edit distance [2] to trees, and since then, we have been able to use distance measures to evaluate the similarity of trees. In 2001, Collins and Duffy [3] introduced the first instance of tree kernels and has opened new avenues for leveraging a variety of powerful kernel machines to study trees. Furthermore, recent work has shown that the subpath kernel is both more efficient and accurate than other tree kernels: significantly fast algorithms that compute the subpath kernel in time linear to the size of input trees (the number of vertices) have been proposed [4,5]; An intensive experiment with various datasets has showed that the subpath kernel outperforms other tree kernels in classification accuracy when used with SVM.

Thus, the recent advances in tree kernel methods have made it possible to leverage powerful kernel machines for the purpose of analyzing various real tree data. Two of the most important advantages of using kernel machines are the wide variety of methods based on multivariate analysis, and the excellent generalization performance obtained even when analyzing small datasets. In this regard, the main aims of this paper are to introduce:

• A generic system design for effective and efficient analysis of tree data with the subpath kernel;
• A detailed application of the subpath kernel to document object model (DOM) trees, an important example of tree data; and
• The remarkably high performance observed in analysis of DOM trees for detecting fake e-commerce sites with the subpath kernel system.

Fake e-commerce sites have been serious threats to costumers and providers of e-commerce. They pretend to be authentic sites that are authorized by companies operating e-commerce platforms and attempt to obtain money by fraud, steal personal information such as credit card numbers, ruin reputation of the platform operators, and so forth. The number of reported incidents of fake e-commerce sites started to increase in 2012, and it continues to increase rapidly. In Japan, the monetary damage reported in 2012 was merely 48 million JPY, but rapidly grew to 2.9 billion JPY in 2014 and 3.1 billion JPY in 2015.

Although fake e-commerce sites may seem akin to a popular class of malicious sites referred to as phishing sites, there is a crucial difference. Phishing pages attempt to resemble a single legitimate site, meaning they must mimic one particular site as closely as possible. By contrast, fake e-commerce sites do not have any specific targets, and similarity to specific existing authentic sites is even harmful for them, because the similarity may raise consumers’ awareness of their illegality and as a result will shorten their lifetime. Therefore, phishing detection approaches do not work with e-commerce fraud detection sites, because they cannot be compared to a single known-good target site [6].

Nevertheless, it will be helpful to review the techniques developed for phishing detection. Surveys in the literature (e.g., [7,8,9,10]) have reported that the major sources of information consist of web-page contents, URLs of websites and blacklists.

• Web-page contents can provide information at the finest granularity, and the range of features that can be extracted is the widest. The features of hyperlinked URLs [11], linked images [11,12], and embedded executable codes [13] are all extracted from page contents. Distributions of various information such as terms used [14], tag contents [11], contents types [14] and terms’ TF-IDF values [15,16] are also useful features. In exchange, the detailed investigation of web-page contents may cause damages to users’ computers by executing malware included, and features extracted from texts are prone to be language-specific. More importantly, content-based features can be shallow in many cases, that is, it is not difficult for adversaries to alter them so as to circumvent detection.
• The URL of a website can also provide useful information for phishing detection. The features include not only tokens from the URL [15,16,17] but also metadata obtained from external sources such as DNS [15], Google PageRank [15] and Amazon Alexa [14]. Because of the limit of the length of URL strings, the information obtained is also limited. Link redirection and change of web-contents can be an effective circumvention method, as well.
• A blacklist is created in a concentrative manner and specifies URLs of known phishing sites. Since its trustworthiness is high, it is widely used in real services like Google Safe Browsing [18] and eBay Toolbar [7]. Nevertheless, automated crawlers can be easily detected, and also, changing web-contents can easily outdate it. The most significant disadvantage of blacklists is the time difference between discovery of phishing sites and their registration to blacklists. The most significant disadvantage of blacklists is the time difference between discovery of phishing sites and their registration on blacklists.

In this paper, we are interested in methods that can automatically detect newly born (zero-day) fake websites. Therefore, the blacklist approach is out of the scope of this paper. In general, use of machine learning techniques is known effective to detect zero-day attacks, and the survey [19] introduces latest attempts to apply machine learning techniques to the problem of detecting fake websites. Some leverage the remarkable advances of the research on artificial neural networks (ANN) to obtain excellent detection accuracy [20,21,22,23], while some rely on the established methods including SVM, Decision Tree, Random Forest and Gradient Boosting [23,24].

Many of the reported methods that can detect zero-day fake sites show significantly high accuracy rates of detection. For example, the accuracy of 0.999 is reported in [14,15]. They, however, rely on shallow features, such that adversaries can change their values to bypass detection without insuperable difficulties. This is the problem of the existing methods that we recognize and try to solve.

For the purpose, we develop a far more resilient approach. We propose a method that takes advantage of the structural information of a web page’s document object model (DOM) tree. A DOM tree of a web page is a tree that represents the nesting structure of its hypertext markup language (HTML) tags. Figure 1 shows an extremely simple example of an HTML document and the DOM tree that represents it. Real DOM trees usually include thousands of vertices.

This approach is based on a discovery reached through joint investigation with the National Police Agency of Japan and Rakuten Inc., an e-commerce company that is operating the largest e-commerce platform in Japan. Law enforcement agencies and e-commerce companies have been cooperating to identify fake sites as quickly as possible in order to minimize the damages to consumers. They collect information of fake sites through complaint forms and allocate staff to analyze the collected information. Once they discover fake sites, they add their URLs to public blacklists. This initiative has shut down thousands of fake sites, usually very quickly. As a result of this policework, the average lifetime of a fake site is short, and the criminals must continuously develop and release new fake sites quickly. Because of this short lifespan, a single group of criminals must operate make fake sites simultaneously in order to make profits worth the effort required to maintain a set of short-lived sites. Thus, criminals cannot spend much time or effort developing each new site from scratch. On the other hand, they have to make each site look different to fool consumers. Changing content and layout is easy and affordable, but modifying page structure is expensive. Thus, we expect that DOM trees of web-pages can carry effective and sustainable features for the purpose of discriminating fake sites from authentic sites.

Using HTML tags as features for detecting fake websites has been proposed in the literature. For example, the five categories recommended in [25] as important sources of features are: web page text; web page source code; URLs; images; and, linkage, and HTML tags are obtained from source codes of web pages. The tags are, however, used individually, and their structural information is not incorporated into detection of fake websites. In contrast, the method presented in this paper evaluates only the structural information of HTML tags, that is, DOM trees, not the content of web pages, such as texts or images. This does not mean, however, that features obtained from the other sources are useless. As recommended in [25], it is desirable that real fake-website detection tools rely on features from a variety of sources for robust performance, and we recommend including structural features of DOM trees to measure similarity of web pages.

In [26], the relationship between elements of fake-website detection tools and users’ acceptance of the tools is studied. In particular, accuracy and speed are critical for earning users’ acceptance. While structural information includes effective cues that can lead to improvement in accuracy, analyzing structural information is generally costly in time. In this regard, the subpath kernel can satisfy both of the seemingly contradictory requirements of high accuracy and high efficiency. In fact, as we see in Section 5, the accuracy rate observed in our experiments reaches as high as 0.998, and prediction of a single website with a support vector machine (SVM) classifier requires only a few tens of milliseconds.

In addition, because a (positive definite) tree kernel can be viewed as a method to plot trees as points in Euclidean (Hilbert) spaces, the subpath kernel can be combined with a variety of multi-variate analysis methods including SVM, principal component analysis (PCA), multiple regression analysis, and Gaussian process analysis, and we can select the most effective analysis tool according to our objective.

The remainder of this paper is organized as follows. In Section 2, we give a description of the data that we use in our research. In Section 3, we briefly review a theory of similarity measures to evaluate similarity of DOM trees. Section 3.3.2 reviews tree kernels, the class of measures that we use. Section 4 provides a specific description of the subtree kernel. Section 5 describes our method, experiments, and further applications. Although the target application in this paper is detection of fake e-commerce sites, it has larger applications.

2. The Data Used in Our Research

The initial form of the data that we use in our research is a list of URLs of real e-commerce sites annotated relating to whether the sites of the URLs are fake or authentic. We have obtained the data by different means for fake sites and authentic sites.

2.1. Positive Examples—Fake Sites

Rakuten, Inc. has provided us with a list of 3597 URLs of fake sites. Rakuten is a Japanese electronic commerce and Internet company, which operates Rakuten Ichiba, the largest e-commerce platform in Japan. Rakuten is a large target for fraud because it is ranked 14th worldwide in revenue. The fake sites that Rakuten provided claim to be authorized by Rakuten, but try to defraud consumers with low-quality goods, or products that are never delivered.

To confront this threat, Rakuten has formed an Internet patrol team whose mission is to investigate fraudulent sites. Their current method relies on manual investigation, which they would like to improve through automation.

2.2. Negative Examples—Authentic Sites

The number of authentic sites found by the aforementioned investigation is very small compared to the number of fake sites. Therefore, we need to collect a compatible number of URLs of authentic sites to apply machine learning properly. For the purpose, we have developed a crawler program that visits authentic sites by tracing links starting from a Rakuten’s official site, https://ranking.rakuten.co.jp. This method produced 3349 URLs of authentic sites.

We know, however, that the web-pages that this method collects include pages whose purpose is not to sell goods to consumers. For example, our dataset includes Rakuten’s help pages about its e-commerce platform and credit cards. Nevertheless, we decided to use all of these pages for two reasons: first, the positive examples also include non-shopping sites; and second, the percentage of such non-shopping pages is smaller than 1%, so their impact to machine learning analysis is expected to be limited.

2.3. Partition into a Training and Validation Datasets

We have selected 500 fake sites and 500 authentic sites to include in a training dataset, while the remaining 3097 fake sites and 2849 authentic sites are preserved for validation. The training dataset will be used to train classifiers, while the validation dataset will be used to evaluate how well the classifiers have been trained.

3. Similarity Measures for DOM Trees

As described, we expect that DOM trees include features that persist despite adversaries’ efforts to slip past detection attempts. Nevertheless, not all features of DOM trees are appropriate to use for our purpose. In the following, we will describe what features of DOM trees we should leverage in our proposal.

3.1. Measures Based on Shallow Features

Figure 2 shows histograms of the vertex number $s\left(t\right)$, the leaf number $l\left(t\right)$ and the height $h\left(t\right)$ of DOM trees t in the training dataset: a leaf is a vertex of t with no children; $h\left(t\right)$ is the length of the longest upward paths from a leaf to the root in t. We can observe that the thresholds of 970, 498 and 23 for $s\left(t\right)$, $l\left(t\right)$ and $h\left(t\right)$ can separate the distributions of fake and authentic sites clearly, and the accuracy rates reach 0.941, 0.943 and 0.974, respectively.

Despite the high accuracy of the methods, we cannot use them for our purpose, because adversaries can easily change these values by adding dummy tags to HTML documents without altering their logical meaning or layout. It is also important to note that an appropriate detection method must not be affected by these indices. Otherwise, adversaries can lower the effective detection accuracy by equalizing sizes of trees.

One alternative we might consider to evaluate the similarity of trees is the use of edit distances with distance-based classifiers (for example, k-nearest-neighborhood). However, this method also relies on shallow features. The edit distance is a widely used class of dissimilarity measures and has been intensively studied for a long time. The Taï distance [1] is a well-known example, and many variations have been derived from it. Among them, the subpath distance, which is based on subpaths in trees, has proven to be excellent in classification accuracy [27]: a subpath is an upward sequence of one or more contiguous vertices of a tree (Figure 3). When $\mathrm{SP}\left(t\right)$ denotes the entire set of subpaths of a tree t, the following formula defines the distance:

$$d_{SP}(t_1,t_2)=|t_1|+|t_2|-2·max\{\left|p\right|\mid p\in \mathrm{SP}\left(t_1\right)\cap \mathrm{SP}\left(t_2\right)\}.$$

This approach does not meet our purposes because $d_{SP}(t_1,t_2)$ relies on a single longest subpath shared between $t_1$ and $t_2$. In fact, when $t_1$ is fake and $t_2$ is authentic, adversaries can modify only a small portion of $t_1$ limiting the resulting change to its logical meaning and layout to the minimum so that $t_1$ and $t_2$ share a longer path, which results in a decrease of $d_{SP}(t_1,t_2)$. Any variations of the Taï distance suffer from the same problem, since they evaluate the similarity only by maximal shared substructures in the same way as the subtree distance.

3.2. Measures Based on Deep Features

In this paper, we pursue measures that evaluate the similarity of the entire spectrum distributions of substructures in trees.

For example, Figure 4 depicts spectrum distributions of $\mathrm{SP}\left(t\right)$ for a fake tree, an authentic tree and a tree whose authenticity is unknown: the x axis represents subpaths that appear in t, while the y axis indicates their occurrence numbers. Whether the third tree is fake or authentic should be determined by to which the unknown spectrum distribution is more similar, the first or the second. As mentioned, the edit distance $d_{SP}(t_1,t_2)$ leverages only the length of the longest common subpaths that appear in the distributions and ignore the remainder of the spectrum distributions.

In contrast, a similarity measure that we are pursuing should incorporate every local similarity of the distributions into evaluation: the entire set of substructures of a tree t (for example, $\mathrm{SP}\left(t\right)$) determines a neighborhood system around vertices of t, and hence, structural information around every vertex definitely affects the entire spectrum distribution; It is difficult for adversaries to intentionally control changes of a spectrum distribution, because every small change of a tree (for example, a substitution, insertion and deletion of a vertex) will spread widely over the distribution.

We can search such measures from tow major categories: divergences and positive definite mapping kernels.

• Kullback-Leibler divergence is the best known example, but it does not satisfy the axiom of symmetry. The symmetric divergences include Jensen-Shannon divergence, Bhattacharrya distance, Hellinger distance, $L^p$-norm and Brownian distance. Divergences can be used with distance-based classifiers such as the nearest centroid and k-nearest neighborhood algorithms for classification, and k-means and k-memoid algorithms for clustering.
• A positive definite kernel $K:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ can be viewed as an inner product operator $\langle ·,·\rangle$ of some inner product space $\mathcal{H}$ [28] (reproducing kernel Hilbert space, RKHS). That is, by some mapping $\mathsf{\Phi }:\mathcal{X}\to \mathcal{H}$, an element $x\in \mathcal{X}$ can be identified with a vector $\mathsf{\Phi }\left(x\right)\in \mathcal{H}$, and $K(x,y)=\langle \mathsf{\Phi }\left(x\right),\mathsf{\Phi }\left(y\right)\rangle$ holds. In particular, normalization of $K(x,y)$ yields the well-known cosine similarity.

  $$\frac{K(x,y)}{\sqrt{K(x,x)K(y,y)}}=\frac{\langle \mathsf{\Phi }\left(x\right),\mathsf{\Phi }\left(y\right)\rangle }{\parallel \mathsf{\Phi }\left(x\right)\parallel \parallel \mathsf{\Phi }\left(y\right)\parallel }=cos\theta .$$
  More importantly, by identifying $\mathcal{X}$ as a subspace of $\mathcal{H}$, we can extensively apply many useful multivariate analysis techniques to $\mathcal{X}$ including PCA for feature extraction, SVM classifier for classification, the kernel k-means algorithm for clustering, and Gaussian process analysis for regression. A positive definite mapping kernel [27], in addition, evaluates spectrum distributions.

Although both divergences and positive definite mapping kernels can be used for our purpose of evaluating the similarity between DOM trees, this paper deploys the latter, since the advantage of multivariate analysis is significant.

3.3. Prior Work on Tree Mapping Kernels

3.3.1. Positive Definite Mapping Kernels

The mapping kernel is a generalization of the well-known convolution kernel [29] and is defined as follows.

For sets x and y, we call a subset $\mu \subseteq x\times y$ a mapping from x to y and allocate a set of mappings $M_{x,y}$ to each pair $(x,y)$. Hence, when $\mathcal{X}$ denotes a family of sets, we have a mapping system $\mathcal{M}$ determined by $\mathcal{M}=\{M_{x,y}\mid (x,y)\in \mathcal{X}\times \mathcal{X}\}$. Furthermore, we let $k:\Omega \times \Omega \to \mathbb{R}$ be an arbitrary kernel defined over $\Omega ={\bigcup }_{x\in \mathcal{X}}x$. Then, the mapping kernel associated with $\mathcal{X}$ and k is determined by

$$K_{\mathcal{M},k}(x,y)=\sum _{\mu \in M_{x,y}}\prod _{(v,w)\in \mu }k(v,w).$$

(1)

For example, a convolution kernel is a mapping kernel with the setting of $M_{x,y}^{\mathsf{H}}=$$\left\{\left\{\right(v,w\left)\right\}\mid v\in x,w\in y\right\}$ and is of the form of

$$K_{{\mathcal{M}}^{\mathsf{H}},k}(x,y)=\sum _{(v,w)\in x\times y}k(v,w).$$

Positive definiteness of a kernel allows us to view it as the inner product operator of some inner product space (RKHS). With respect to positive definiteness of mapping kernels, we have

Theorem 1.

(Shin et al. [30].) The following are equivalent.

• $K_{\mathcal{M},k}$ is positive definite, if k is positive definite.
• $\mathcal{M}$ is transitive, that is, if $\mu \in M_{x,y}$ and $\nu \in M_{y,z}$, then the composition $\nu \circ \mu$ is in $M_{x,z}$.

For more details, refer to Appendix A.

3.3.2. Tree Mapping Kernels

In this paper, a tree always means a rooted ordered tree. A rooted ordered tree is equipped with two orders of vertices: a generation order and a traversal order; A generation order determines an ancestor-to-descendant relation of vertices; $v<w$ indicates that v is an ancestor of w; In particular, $v\ll w$ means that v is the immediate ancestor (parent) of w; The traversal order ≺, on the other hand, determines a left-to-right relation; The nearest common ancestor of v and w is denoted by $v\wedge w$. In Figure 3, for example, $\mathtt{html}<\mathtt{figure}$, $\mathtt{body}\ll \mathtt{figure}$, $\mathtt{head}\prec \mathtt{figure}$ and $\mathtt{figure}\wedge \mathtt{tbody}=\mathtt{body}$ hold. For a formal description, refer to Appendix B.

Furthermore, we assume the vertices of trees are all labeled: We denote the labeling function by $\ell :\Omega \to \mathcal{A}$, where $\Omega$ is the entire set of labeled vertices of our target trees and $\mathcal{A}$ is the alphabet of labels.

When $x\subseteq \Omega$ and $y\subseteq \Omega$ represent two trees, a mapping set $M_{x,y}$ to be used for a mapping kernel should be determined so that it reflects the interior structures of x and y. The minimum requirements for $\mu \in M_{x,y}$ are:

• $\mu$ is a one-to-one partial mapping;
• $\mu$ preserves the generation orders of x and y, that is, $\mu \left(v\right)<\mu \left(w\right)$, if, and only if, $v<w$;
• $\mu$ preserves the generation orders of x and y, that is, $\mu \left(v\right)\prec \mu \left(w\right)$, if, and only if, $v\prec w$;

In [31], 32 different mapping systems are defined, and the associated tree mapping kernels are investigated. Among them, we see two examples.

• The elastic tree kernel [32] is an important example of tree kernels in the literature and is also defined as an instance of mapping kernels with mapping sets $M_{x,y}^{\mathsf{E}}$ determined so that $\mu \in M_{x,y}^{\mathsf{E}}$ satisfies (1) $v\wedge w\in \mathrm{Dom}\left(\mu \right)$, if $\{v,w\}\subseteq \mathrm{Dom}\left(\mu \right)$, and (2) $\mu (v\wedge w)=\mu \left(v\right)\wedge \mu \left(w\right)$. Figure 5 exemplifies $\mu \in M_{x,y}^{\mathsf{E}}$.
• The subpath kernel [4,33] is also a mapping kernel determined by $M_{x,y}^{\mathsf{SP}}$, which consists of $\mu \subset x\times y$ such that $\mathrm{Dom}\left(\mu \right)$ and $\mathrm{Ran}\left(\mu \right)$ are subpaths. Figure 6 exemplifies $\mu \in M_{x,y}^{\mathsf{SP}}$,

For the interior kernel $k:\Omega \times \Omega \to \mathbb{R}$ to be used in Equation (1), we can use the following kernel with two weight parameters $\alpha$ and $\beta$:

$$\begin{array}{cc}\hfill & k_{\alpha ,\beta }(v,w)=(\alpha -\beta ){\delta }_{\ell \left(v\right),\ell \left(w\right)}+\beta =\left\{\begin{array}{cc}\alpha ,\hfill & \mathrm{if}\ell \left(v\right)=\ell \left(w\right);\hfill \\ \beta ,\hfill & \mathrm{otherwise}.\hfill \end{array}\right.\hfill \end{array}$$

(2)

It is easy to see that $k_{\alpha ,\beta }$ is positive definite, if $\alpha \ge \beta \ge 0$. For the elastic and subpath tree kernels, we further constrain $\beta$ to be zero.

3.3.3. A Comparison of Tree Mapping Kernels

In [31,33], tree mapping kernels obtained from Equations (1) and (2) are comprehensively investigated with respect to the classification accuracy when used with support vector classifiers (SVC). A mapping system $\mathcal{M}$ is chosen out of 32 different types including $M_{x,y}^{\mathsf{E}}$ and $M_{x,y}^{\mathsf{SP}}$, while $(\alpha ,\beta )$ moves over grid points in the region of $0\le \beta \le \alpha \le 1$. The comparison is based on averaged ten-fold cross validation scores (accuracy scores) across ten independent datasets.

Figure 7 shows the result of the comparison focusing on the best six tree kernels investigated. For the subpath, parse and elastic tree kernels, $\beta$ was fixed to zero, while $\alpha$ was adjusted to show the best accuracy performance. For the other kernels, both $\alpha$ and $\beta$ were adjusted. In the chart, the values in the hatched rectangles show the averaged rank of each kernel, while the figures in parentheses that follow kernel names are p-values of Hommel test [34] as recommendation by [35]. We should remark that the subpath kernel overwhelmingly outperforms the other kernels.

3.4. Conclusion on Kernel Selection

To confirm the superiority of the subpath kernel in classification accuracy, we run an additional experiment using a dataset with 25 fake DOM trees and as many authentic DOM trees. In the experiment, we compare the subpath kernel with 59 tree kernels including the kernels tested in [31,33]. Figure 8 shows the result. The accuracy scores are measured through ten-fold cross validation. Only the subpath kernel marks 1.0 accuracy, while the scores of all the other kernels falls between 0.54 and 0.93. Thus, the subpath kernel outperforms even for the dataset of this paper.

In addition, the subpath kernel has the following advantages.

• Linear time algorithms to compute the subpath kernel are known [4,5]. Since the time complexity of computing other tree kernels is mostly of the quadratic order of the size of input trees, this advantage is significant. In particular, this enables real-time detection of fake large-scale DOM trees with thousands of vertices.
• The definition of the subpath kernel is invariant no matter whether trees are ordered or unordered. Although DOM trees are derived as ordered trees, adversaries may change the traversal order of vertices without impacting their logical meaning or layout. Thus, we see that the results by the subpath kernel is secure against the attack of changing the traversal order.

4. The Subpath Kernel

In this section, we look into the subpath kernel more closely.

4.1. Efficient Computing of the Subpath Kernel

In [5], a linear-time algorithm to compute the subpath kernel is presented. It takes a least common prefix (LCP) array as an input, and LCP are computed from a suffix array extracted from trees [5].

4.1.1. Extraction of Suffixes

For better efficiency of computation, the first step of suffix array extraction is assignment of unique identifier to HTML tags. In this section, we use the following assignment.

3:html 4:head ... 6:title 7:link 8:body 9:js 10:div ... 13:img ... 17:a ... 21:span 22:form 23:table 24:tbody 25:tr 26:td ... 65:figure ...

A suffix is a sequence of the identifiers of HTML tags of a subpath from a vertex of a DOM tree to the root. Figure 9 exemplifies a DOM tree and all the suffixes extracted from it. Since the DOM tree consists of 17 vertices, 17 suffixes are extracted. For example, a subpath tr:tbody:table:body:html corresponds to a suffix [25,24,23,8,3]. In the suffix array, suffixes are sorted in the lexicographical order. A linear-time algorithm to compute the sorted suffix array is presented in [4].

4.1.2. Generation of Least Common Prefix Arrays

To generate an LCP array for two trees x and y, the suffix arrays of x and y are first merged and are the sorted in a lexicographical order.

Table 1. An LCP array.

Suffixes	LCP	$\in {\mathit{x}}_{?}$
3	1	0
3	0	1
4,3	0	0
6,4,3	0	0
7,4,3	0	0
8,3	2	0
8,3	0	1
10,24,23,8,3	1	1
10,65,8,3	0	0
13,17,10,65,8,3	0	0
17,10,65,8,3	0	0
23,8,3	3	0
23,8,3	0	1
24,23,8,3	4	0
24,23,8,3	0	1
25,10,24,23,8,3	1	1
25,24,23,8,3	5	0
25,24,23,8,3	0	0
26,25,10,24,23,8,3	7	1
26,25,10,24,23,8,3	2	1
26,25,24,23,8,3	6	0
26,25,24,23,8,3	6	0
26,25,24,23,8,3	6	0
26,25,24,23,8,3	0	0
65,8,3	−1	0

shows an example: suffixes extracted from x of Figure are displayed in red, while y in black.

The LCP length for a suffix in the merged array is determined by the length of the longest common prefix between the suffix and the next suffix. For example, the suffixes of [26,25,10,24,23,8,3] and [26,25,24,23,8,3] are adjacent, and their longest common prefix is [26,25]. Therefore, the LCP length assigned to [26,25,10,24,23,8,3] is two as displayed in red. $-1$ is assigned to the last suffix.

4.2. Understanding the Decay Factor $\alpha$

When computing $K^{\mathsf{SP}}(x,y)$, a subpath with n vertices shared between x and y is counted by a factor of ${\alpha }^n$. Therefore, the contribution of long subpaths increases, as $\alpha$ becomes greater. To be precise, if a subpath with n vertices is shared by x and y, they also share i subpaths with $n+1-i$ vertices, and therefore, its contribution to the kernel value is evaluated by

$$\gamma (n,\alpha )=\sum _{i=1}^{n}i{\alpha }^{n+1-i}=\left\{\begin{array}{cc}\frac{\alpha }{\alpha -1}\left(\frac{{\alpha }^{n+1}-1}{\alpha -1}-n-1\right),\hfill & \mathrm{if}\alpha \ne 1;\hfill \\ \frac{n(n+1)}{2},\hfill & \mathrm{if}\alpha =1.\hfill \end{array}\right.$$

Figure 10 shows the change of the ratio $\frac{\gamma (10,\alpha )}{\gamma (m,\alpha )}$, when m and $\alpha$ changes. We see that a single subpath with ten vertices is equivalent to 91 subpaths with two vertices for $\alpha =1.5$, and the number rapidly decreases as m increases and $\alpha$ decreases.

5. The Proposed Method

After seeing the entire picture of the steps of our detection system, we see experimental results on the performance of each step. In the experiments, we use iMac Pro with 14 core 2.5 GHz Intel Xeon W and 128 Gbyte memory.

5.1. The Entire Picture

Figure 11 depicts the entire structure of our proposed system. HTML mark-up documents are first input into an HTML parsing/sanitization program, which extract DOM trees from them after eliminating and correcting non-standardized descriptions included. The obtained DOM trees are input into a suffixes extracting program (Section 4.1.1), and the obtained suffix arrays are stored in a database. Since the suffix array of a DOM tree will be used for multiple times to compute the subpath kernel values with other DOM tree, storing the suffix array in a database will be beneficial to improve the efficiency of the entire process.

In the next step, the necessary subpath kernel values are computed. When a training dataset consists of DOM trees $x_1,\cdots ,x_n$, the complete Gram matrix

$$G(x_1,\cdots x_n)=\left[\begin{array}{ccc}k(x_1,x_1)& \cdots & k(x_1,x_n)\\ ⋮& \ddots & ⋮\\ k(x_n,x_1)& \cdots & k(x_n,x_n)\end{array}\right].$$

Is computed. $k(x_i,x_j)$ is the normalized value of the subpath kernel value $K^{\mathsf{SP}}$ determined by

$$k(x_i,x_j)=\frac{K^{\mathsf{SP}}(x_i,x_j)}{\sqrt{K^{\mathsf{SP}}(x_i,x_i)}\sqrt{K^{\mathsf{SP}}(x_j,x_j)}}.$$

The normalization is necessary to eliminate undesirable effects caused by different sizes of DOM trees (Section 3.1). For the prediction purpose, kernel values are computed only between the DOM trees in a test dataset and the DOM trees that comprise support vectors in the training dataset. To compute the subpath kernel value $K^{\mathsf{SP}}(x,y)$, the LCP array between x and y is first computed (Section 4.1.2), and then, it is input into the linear-time algorithms presented in [5].

In the step of parameter optimization, the optimal values for the two hyper-parameters of the decay factor $\alpha$ and the regulation coefficient C of SVC are computed through a grid search algorithm.

In the prediction step, a separating hyper-plane in the reproducing kernel Hilbert space is computed with the training dataset and the associated optimal hyper-parameters, and then, a predicted label of a DOM tree in the test dataset is computed by SVC.

5.2. Suffixes Extraction

The suffix array extraction program of our system takes a batch of DOM trees as inputs, and then, computes the associated suffix arrays efficiently through parallel computation. Figure 12 shows the averaged time in milliseconds to extract suffix arrays from a single DOM tree, when changing the batch size from 50 to 1000. Although the time scores for $n=50$ and 100 are higher because of the overhead of parallel computation, we see that our program can process a single DOM tree in 20 milliseconds on average.

5.3. Gram Matrix Generation

Since a Gram matrix is symmetric, to compute an n-dimensional Gram matrix, computation of $\frac{n(n+1)}{2}$ kernel values is necessary. Hence, the effect of deploying parallel computation is expected to be greater than used for suffix array extraction.

Figure 13 shows the total run-time scores of computing Gram matrices for n that varies from 50 to 1000. Although the total run-time (the blue line) should be in theory proportional to the number of kernel values to compute (the orange line), we can see a gap between them that is caused by the overhead of using parallel computation.

In fact, Figure 14 plots the averaged computation time to compute a single kernel value, that is, the ratio of the total run-time to the number of kernel values. the effect of the overhead is evident, when n is small. As n increases, the contribution of parallel computation becomes remarkable, and the averaged time only as great as 60 microseconds.

5.4. Hyper-Parameter Optimization

To build optimal models, there are two adjustable hyper-parameters: the decay factor $\alpha$ for the subpath kernel and the regulation coefficient C for SVC. Our program for hyper-parameter optimization performs a simple grid search by changing $\alpha$ from $0.1$ to $2.0$ with an interval $0.1$ and ${log}_{10}C$ from $-5$ to 5 with an interval 1. The total number of different combinations of $\alpha$ and C to test is 220. For evaluation of each combination of $\alpha$ and C, cross-validation scores with five folds are used. We evaluate the performance of this step from both efficiency and accuracy points of view.

Figure 15 shows that the relationship between the total run-time for optimizing the hyper-parameters and the size n of training datasets can be fit to an increasing regression line with a determination coefficient as high as 0.968. Furthermore, the run-time for $n=1000$ is 3004 s ≈ 50 min. Due to the excellent generalization performance of SVC, we can obtain good models even for $n\le 1000$, and hence, model updates can be performed quickly.

Figure 16a consists of a plane view and a contour plot of the cross-validation scores (accuracy scores) obtained through the grid search for $n=1000$. Except that there is a steep drop-off where the score falls from 1.0 to 0.857 within the rectangular area with $1.4\le \alpha \le 12.0$ and $-5\le {log}_{10}C\le -1$, the score is mostly 1.0.

When investigating the cases of fake and authentic sites separately (Figure 16b,c, the accuracy score for the fake sites, computed by $\frac{\mathrm{TP}}{\mathrm{TP}+\mathrm{FN}}$, varies within a narrow range between 0.976 and 1.0, while the score for the authentic site, computed by $\frac{\mathrm{TN}}{\mathrm{TN}+\mathrm{FP}}$, has a steep drop-off in the same rectangular area as the score for the entire dataset.

For the smaller training datasets we have tested, we observe the same property for most of cases (Figure 17). In particular, the maximum cross-validation is 1.0 for all the cases including when the dataset size is as small as 50.

5.5. Prediction

Next, using the 5946 validation examples, we test only the parameter combinations that have shown the highest cross-validation score of 1.0. Figure 18a shows the obtained accuracy scores. Interestingly, it turns out that the score drops rapidly from 0.98 to 0.8, when the decay factor exceeds 1.3. This implies that overfitting has occurred. When we focus on the fake sites, as Figure 18b shows, the range of the accuracy score is very narrow between 0.999 and 0.992, and the identification problem of fake sites turns out not to be sensitive to hyper-parameter selection. On the other hand, Figure 18c shows that learning of authentic sites with a decay factor higher than 1.3 is likely to generate overfitting models, whose accuracy score can be as low as 0.579.

As seen in Section 4.2, the subpath kernel with a high decay factor evaluates longer shared subpaths more significantly. Hence, the results of the validation shows that pages of authentic sites are better characterized by shorter subpaths rather than longer subpaths.

Furthermore, Figure 19 shows the results of validation when we use training datasets whose size are smaller than 1000. Surprisingly, even small datasets can exhibit very high accuracy, and for example, a dataset with only 50 examples shows the accuracy score of 0.994. Also, we can observe overfitting occurring in the same way and under almost the same conditions as when we use a dataset of size 1000, and SVC shows the best accuracy performance when the parameters are selected from the area of $0.9\le \alpha \le 1.1$ and $0\le {log}_{10}C\le 5$.

Once the hyper-parameters $\alpha$ and C are specified, we will be able to make prediction on which unknown sites are fake or authentic based on their DOM trees.

The first step of prediction is the step to train an SVC based on the hyper-parameter values obtained in the previous optimization process and the training dataset used. The output of training SVC is a model that specifies the separating hyperplane computed through training.

In our system, we assume that, once an SVC is trained, we continue to use the same SVC to make many predictions. Hence, the time efficiency of training an SVC is not significantly critical.

Figure 20 shows the runtime t in seconds to train an SVC when the size n of a dataset varies. When excluding one outlier ($n=400$), the relation between t and n fits to a line with determination coefficient $0.990$. When $n=400$, the objective function has converged exceptionally slowly, and the program of libSVM [36] has reached the default upper limit of 10,000,000 iterations. Including this exceptional datum, the total runtime for training does not one minute largely. We can conclude that.

The actual output of training an SVC is a subset of examples of a training dataset, which uniquely determines a hyperplane. To make a prediction on a new DOM tree, it suffices to compute the kernel values between the new DOM tree and the support vectors Since these DOM trees have been converted into suffix arrays in the suffix arrays extraction process, computing these kernel values can be performed very quickly by taking advantages of the algorithm introduced by [5].

In fact, Figure 21 shows the averaged runtime to make a prediction for a single unknown DOM tree and the number of support vectors for eleven training datasets with different sizes. We can see that the runtime and the number of support vectors are faithfully proportional. Although the runtime for $n=200$ is exceptionally high, it is only 65 milliseconds. For the other datasets the scores are lower than 25 milliseconds. This indicates that our system can sufficiently realize real-time detection of fake sites.

5.6. Comparison in Accuracy Performance

Table 2. Comparison in accuracy performance of our method (Subpath Kernel) against benchmark methods: Prec.$=\frac{\mathrm{TP}}{\mathrm{TP}+\mathrm{FP}}$; Recall$=\frac{\mathrm{TP}}{\mathrm{TP}+\mathrm{FN}}$; F-Score$=\frac{2\times \mathrm{TP}}{2\times \mathrm{TP}+\mathrm{FP}+\mathrm{FN}}$; Acc.$=\frac{\mathrm{TP}+\mathrm{TN}}{\mathrm{TP}+\mathrm{FP}+\mathrm{FN}+\mathrm{TN}}$.

Method	Test Dataset		Train	Evaluation
	Authentic	Fake	/Test	Prec.	Recall	F-Score	Acc.
Subpath Kernel (100)	2849	3097	1/60	0.988	1.000	0.994	0.994
Subpath Kernel (1000)	2849	3097	1/6	0.999	1.000	0.999	0.999
Whittaker et al. [15]	1,499,109	16,967	6/1	0.989	0.915	0.951	0.999
Cantina [16]	2100	19	–	0.212	0.89	0.342	0.969
PhishStorm [17]	48,009	48,009	9/1	0.984	0.913	0.947	0.949
PhishShield [37]	250	1600	–	0.999	0.971	0.985	0.966
Yang et al. [21]	22,390	22,445	44/1	0.994	0.986	0.996	0.989
Sonmez et al. [23]	–	–	–	–	–	–	0.953
Tyagi et al. [38]	–	–	–	–	–	–	0.984

exhibits the results of comparison of our method trained by 100 and 1000 data, respectively, against seven benchmark methods for phishing site detection in terms of accuracy performance. The accuracy performance is evaluated using four measures of precision, recall, F-score and accuracy rate, if possible. We see that our method trained with 1000 data (500 fake and 500 authentic) outperforms the others for all of the four measures. Interestingly, even when our method is trained with only 100 data, the measurements are almost compatible with the best of the benchmark methods.

Mainly because the datasets used for the evaluation are different according to the methods, we cannot statistically conclude that our method is superior to the benchmark methods. However, we should emphasize that our method leverages robust features derived from distributions of subpaths in DOM trees. In contrast, the benchmark methods mainly rely on shallow features, which the adversaries can alter without difficulties.

Furthermore, we should note the fact that our method exhibited high accuracy performance using small datasets for training and significantly larger datasets for testing. This observation should be a clear evidence that indicates the excellent generalization performance of our method. The practical meanings of this observation are: we can reduce the frequency of model renewal; and the model renewal by itself can be performed significantly efficiently.

6. Conclusions

We have shown a method to realize highly accurate and real-time detection of fake e-commerce sites based on DOM tree similarity. We demonstrated its accuracy and speed on a real dataset provided by Rakuten. While the efficiency and performance of our method alone make it compelling, another advantage is the minimal amount of training data required. We believe our method has the potential to increase the safety of e-commerce solutions. Not only does it detect fake sites quickly and with high accuracy, given that it requires only small training data sets, it allows web security software to update itself more quickly against new threats as they emerge.