Dynamically Weighted Hidden Markov Model for Spam Deobfuscation

1 Introduction

Large vocabulary problems in hidden Markov models (HMMs) have been addressed in various areas such as handwriting recognition [A. L. Koerich and Suen, 2003] and speech recognition [Jelinek, 1999]. As the vocabulary size increases, the computational complexity for recognition and decoding dramatically grows, making the recognition system impractical. In order to solve the large vocabulary problem, various methods have been developed, especially in speech and handwriting recognition communities.

For example, one approach is to reduce the lexicon size by using the side information such as word length and word shape. However, this method reduces the global lexicon to only its subset so that the true word hypothesis might be discarded. An alternative approach is to reduce a search space in the large lexicon, since the same initial characters are shared by the lexical tree, leading to redundant computations. Compared to the flat lexicon where whole words are simply corrected, these methods reduce the computational complexity. However, the lexical tree still has a large number of nodes Seungjin Choi Department of Computer Science POSTECH, Korea seungjin@postech.ac.kr and its effect is limited. Other approaches involve various search strategies. The Viterbi decoding is a time-consuming task for HMMs which contain a large vocabulary (e.g., 20,000 words). The beam search algorithm [Jelinek, 1999] speeds up the Viterbi decoding by eliminating improper state paths in the trellis with a threshold. However, it still has a limitation in performance gain if a large number of states are involved (e.g., 100,000 states) since the number of states should still be taken into account in the algorithm.

Spam deobfuscation is an important pre-processing task for content-based spam filters which use words of contents in emails to determine whether an incoming email is a spam or not. For instance, the word "viagra" indicates that the email containing such word is most likely a spam. However, spammers obfuscate words to circumvent spam filters by inserting, deleting and substituting characters of words as well as by introducing incorrect segmentation. For example, "viagra" may be written as "vi@graa" in spam emails. Some examples of obfuscated words in real spam emails are shown in Table 1. Thus, an important task for successful content-based spam filtering is to restore obfuscated words in spam emails to original ones. Lee and Ng [Lee and Ng, 2005] proposed a method of spam deobfuscation based on a lexicon tree HMM (LTHMM), demonstrating promising results. Nevertheless, the LT-HMM suffers from a large number of states (e.g., 110,919 states), which is not desirable for practical applications.

In this paper, we present a complexity-reduced structure of HMM as a solution to the large vocabulary problem. The core idea is to group states involving the same emission probabilities into a few number of super-states, while preserving state transition probabilities of the original HMM. The proposed complexity-reduced HMM is referred to as dynamically weighted HMM (DW-HMM), since state transition probabilities are dynamically determined using the data structure which contains the state transition probabilities of the original HMM in the decoding phase. We illustrate how to construct a DW-HMM, given a LT-HMM, reducing the number of states dramatically. We also explain conditions for equivalence between DW-HMM and LT-HMM. We apply DW-HMM to the task of spam deobfuscation, emphasizing its reduced-complexity as well as performance.

2 DynamicallyWeighted HiddenMarkov Model

A hidden Markov model is a simple dynamic Bayesian network that is characterized by initial state probabilities, state transition probabilities, and emission probabilities. Notations for HMM are as follows:

1. Individual hidden states of HMM are denoted by {q1, q2, q3, . . . , qK}, where K is the number of states. The hidden state vector at time t is denoted by qt ∈ RK .
2. Observation symbols belong to a finite alphabet, {y1, y2, . . . , yM}, where M is the number of distinct observation symbols. The observation data at time t is denoted by yt ∈ RM .
3. The state transition probability from state qi to state qj is defined by P (qj |qi).
4. The emission probability of observation symbol yi, given state qj is denoted by P (yi |qj ).
5. The initial state probability of state qi is denoted by Π(qi).

With these definitions, HMM is characterized by the joint distribution of states q1:T = {q1, . . . , qT} and observed symbols y1:T = {y1, . . . , yT }, which is of a factorized form

We first illustrate the DW-HMM with a simple example. Figure 1 shows a transition diagram of a 8-state HMM and its associated DW-HMM that consists of four super-states, s1, s2, s3, and s4. In this example, the original 8-state HMM (as shown in the top in Figure 1) has four distinct emission probabilities, i.e.,

The states involving the same emission probability, are grouped into a super-state, denoted by s in the DW-HMM (as shown in the left of the bottom in Figure 1). In such a case, we construct a DW-HMM containing 4 super-states, s1, s2, s3, and s4, where the following is satisfied:

In the DW-HMM, the number of states is reduced from 8 to 4.

The data structure Φ (as shown in the right of the bottom in Figure 1) is constructed, in order to preserve the state transition probabilities defined in the original HMM. Each node in Φ is labeled by the super-state which it belongs to and state transition probabilities are stored, following the original HMM.

Φ

Figure 1: Transition diagrams for the 8-state HMM, its associated 4-state DW-HMM, and the data structure Φ, are shown. The original HMM contains 8 different states with 4 different emission probabilities. The nodes with the same emission probabilities are colored by the same gray-scale. DW-HMM contains 4 different super-states and the data structure Φ is constructed in such a way that the transition probabilities are preserved for the DW-HMM.

The trellis of the 4-state DW-HMM is shown in Figure 2. Transition probabilities are determined by searching Φ using a hypothesis, s1:t. To show the relation between DW-HMM and HMM, we define that super-state sequence of DW-HMM, s1:T , is corresponding to state sequence of HMM, q1:T , if

Thus, in Figure 2, the hypothesis of the 8-state HMM corresponding to s1:4 = {s1, s2, s3, s4} is the state sequence, q1:4 = {q1, q2, q5, q8}. Given an observation sequence, y1:4 = {y1, y2, y3, y4}, the joint probabilities of the state sequence and the observation sequence are as follows:

Since q1:4 is the state sequence corresponding to s1:4, the emission probabilities involved in the joint probabilities are equal as follows:

The DW-HMM searches Φ with the hypothesis, s1:t, determining the transition probabilities as follows:

By the above equalities, the 8-state HMM and the 4-state DWHMM have the same joint probability as follows:

In searching of a probability, P (st|st-1), we assume that state sequence s1:t is unique in Φ. The constraint is not so strong in that if there are several state sequences which have exactly the same emission probabilities for each state, it is very possible that the model has redundant paths. Therefore, it is usual when the constraint is kept in HMMs.

The joint probability of state sequence q1:T = {q1, q2, . . . , qT} and an observation sequence y1:T =

{y1, y2, . . . , yT } of HMMs equals that of the corresponding super-state sequence s1:T = {s1, s2, . . . , sT} and the same observation sequence y1:T of converted DW-HMMs as follows:

The state transition probability of DW-HMM is defined as follows:

where s1:t is state sequence decoded so far, s1:t = {s1, s2, . . . , st-1, st}. ω(s1:t) is a weight function which returns transition probabilities from Φ. The weight function, ω(s1:t), traces a hypothesis, s1:t, in Φ, and returns a state transition probability, P (st|st-1) that is stored in a node visited by st. For example, in Figure 2, ω(s1:3) determines the state transition probability, P (s3|s2) at t = 3. The thick line in Φ shows that ω(s1:3) traces the hypothesis s1:3, and returns the transition probability, P (s3|s2), stored in the node, s3, which is the same as the value of P (q5|q2) as shown in Figure 1. If a node contains several state transition probabilities, we choose the correct one according to the node visited at t - 1. It should be noted that DW-HMM determines the transition probability by searching the data structure of Φ whereas HMMs find them in the transition probability matrix.

DW-HMMs converted from HMMs have the following characteristics. First, DW-HMMs are useful for HMMs which have a very large state transition structure and common emission probabilities among a number of states, such as LT-HMMs. When we convert a HMM to its associated DW-HMM, the computational complexity significantly decreases because the number of states is dramatically reduced.

Second, there is no need to maintain a transition probability matrix since the weight function dynamically gives transition probabilities in the decoding phase. Third, DW-HMMs are so flexible that it is easy to add, delete, or change any states in the state transition structure since only the data structure, Φ, needs to be updated. Fourth, the speed and accuracy are configurable by using beam search algorithm and N-best search [Jelinek, 1999] respectively, thus securing a desirable performance.

2.1 Conversion algorithm

To convert a HMM to DW-HMM, we should make a set of super-states, S, from the states of HMM which represent unique emission probabilities. When S consists of a small number of super-states and the original HMM's state transition structure is large, the DW-HMM is more efficient than HMMs. For example, a LT-HMM is a good candidate to convert to a DW-HMM, because it only has a few states with unique emission probabilities and contains large trie dictionary. The following explains the algorithm of converting a HMM to DW-HMM.

Algorithm: Conversion of HMM to DW-HMM

1. Make a set of super-states which have unique emission probabilities, S = {s1, s2, . . . , sK}, from a HMM. In this step, the number of states of HMM is reduced as shown in Figure 1.
2. If there are any loops (self-transitions) in the HMM, add additional super-states. For example, if si has a loop, an additional sj state is made. It makes it possible to distinguish between self-transitions and non-self-transitions.
3. Construct the DW-HMM associated with the HMM using super-states in S. State transitions are made between super-states if there exists a state transition in the HMM, from which the super-states are made. For example, in Figure 1, the 4-state DW-HMM has a state transition from s2 to s3 because q2 may transition to q5 in the 8-state HMM.
4. Make a data structure, Φ, to define a weight function, ω(s1:t), which gives the transition probability of the DW-HMM. Φ contains the transition structure of the HMM and stores transition probabilities in each node. In making Φ, self-transitions in the HMM are changed as shown in Figure 3. The super-state that has a loop transitions to an additional super-state made from step 2 and it transitions to states where the original state goes. The structure of Φ and the state transition structure of the HMM may be different due to self-transitions.
5. Define emission probabilities of the DW-HMM's superstates which are the same as of the corresponding states

of the HMM.

2.2 Conditions for equivalence

In the conversion process, DW-HMM conserves transition and emission probabilities. However, there is a difference between HMM and its associated DW-HMM when we use straightforward Viterbi algorithm. Figure 4 illustrates trellis of DW-HMM at t = 3 and the state s1, the only state path {s1, s2, s1} that can propagate further since {s1, s3, s1} has a smaller probability than {s1, s2, s1}. Therefore, the path {s1, s3, s1} is discarded in a purging step of the Viterbi algorithm. However, in case of HMM shown in Figure 5, at t = 3 and the state q1, both state paths {q1, q2, q1} and {q1, q3, q1} can propagate to the next time instant because there are two q1 states.

To ensure that the results of DW-HMM and HMM are the same, we adapt N-best search for DW-HMMs and we choose the best path at the last time instant in the trellis. Figure 6 shows that the two-best search makes two hypotheses at s1 and t = 3. Both state paths {s1, s2, s1} and {s1, s3, s1} are kept to propagate further.

t = 1 t = 2 t = 3

t = 1 t = 2 t = 3

Figure 5: Trellis for HMM.

Figure 7 illustrates the case when two-best search is useful in LT-HMM. We denote the physical property of the states in the nodes, showing which states have the same emission t = 1 t = 2 t = 3

Figure 6: Trellis for two-best search.

probability. q1 and qN are the initial and final state of the LTHMM, respectively. Assuming that there exist two hypotheses at t = 4, {q1, a, b, a}, {q1, a, c, a}, the LT-HMM allow them to propagate further. However, the DW-HMM cannot preserve both at t = 4 if we use one-best search. Since the states labeled "a" in the LT-HMM are grouped into a superstate, one hypothesis should be selected at t = 4. Thus, in case of the DW-HMM, if the answer's state sequence is {q1, a, c, a, c, i, a, qN}, and only one hypothesis, {q1, a, b, a}, is chosen at t = 4, we will fail to find the answer. We address the problemwith N-best search. If we adapt two-best search, two hypotheses, {q1, a, b, a}, {q1, a, c, a}, are able to propagate further, thereby preserving the hypothesis for the answer.

HMM and converted DW-HMM give exactly the same results if we adapt the N-best search where N is the maximum number of states of HMMs that compose the same super-state and propagate further at a time instant. However, for practical purposes, N does not need to be large. Our application for spam deobfuscation shows that the DW-HMM works well when N is just two.

3 Application

A lexicon tree hidden Markov model(LT-HMM) for spam deobfuscation was proposed by Lee and Ng [Lee and Ng, 2005]. It consists of 110,919 states and 70 observation symbols, such as the English alphabet, the space, and all other standard non-control ASCII characters. We transform the LTHMM to the DW-HMM which consists of 55 super-states and the same observation symbols as the model of Lee and Ng. Transition probabilities of the DW-HMM are determined in the decoding phase by a weight function equipped with Φ, which is a data structure of lexicon tree containing transition probabilities of the LT-HMM. Null transitions are allowed and their transition probabilities are also determined by the weight function. It recovers deletion of characters in the input data. 1

The set of individual hidden super-states of the DW-HMM converted from the LT-HMM is as follows:

where s1 is an initial state and states in {s2, . . . , s27} are match states. States in {s28, . . . , s54} are insert states and s55 is the final state. A match state is the super-state representing the letters of the English alphabet and an insert state is the state stems from the self-transitions of the LT-HMM. Since self-transitions of the LT-HMM reflect insertion of characters in obfuscated words, the state is named an insert state. The final state is the state which represents the end of words.

Transition probability of the DW-HMM is as follows:

The structure of Φ is made using lexicon tree and each node of Φ has the transition probability of the LT-HMM.

Here, a hypothesis s1:t starts from s1 which is the initial state decoded. The DW-HMM converted from the LT-HMM has only one initial state and it may appear many times in the hypothesis since the input data is a sentence. To reduce the computational cost in searching Φ, we can use the subsequence of s1:t to search Φ since it is possible to reach the same node of Φ if a subsequence starts from the initial state at any time instant.

We deobfuscate spam emails by choosing the best path using decoding algorithms given observation characters. For example, given the observation characters, "vi@", the best state sequence, {s1, s23, s10, s2}, is chosen which represents "via".

We define emission probabilities as follows:

P (yt |st) when st is a match state = { ρ1 if yt is a corresponding character ρ2 if yt is a similar character ρ3 otherwise

P

P

(yt|st) when st is a insert state = ⎧⎪⎨⎪⎩ σ1 if yt is a corresponding character, a similar character, or not a letter of the English alphabet σ2 otherwise (yt |st) when st is a final state = { ψ1 if yt is a white space ψ2 if yt is not a letter of the English alphabet ψ3 otherwise.

1 More than one consecutive character deletion is not considered due to the severe harm in readability.

An emission probability mass function is given according to the type of the observation. Here, a corresponding character is a physical property of each node. For example, if a node represents a character "a", the letter "a" is the corresponding character. A similar character is given by Leet, 2 which lists analogous characters. For example, "@" is a similar character of the letter "a."

3.1 Decoding

The straightforward Viterbi algorithm is used to find the best state sequence, s1:T = {s1, s2, . . . , sT }, for a given observation sequence y1:L = {y1, y2, . . . , yL}. Here, T and L can be different due to null transitions.

The accuracy and speed are configurable for DW-HMM by using the N-best search and the beam search algorithm. Nbest search makes it possible to improve the accuracy in that multiple super-states are preserved in the decoding phase. For our model, we select the best path rather than N most probable paths at the final time instant in the trellis. However, it increases computational complexity at a cost of the improved accuracy.

The time complexity of the Viterbi algorithm is O(K2 T ), where K is the number of states and T is the length of the input. When the N-best search is used, the time complexity is O((NK)2 T ). To address the speed issue, the beam search algorithm is used and it improves the speed without losing much accuracy. Although LT-HMMs are also able to speed up by using beam search algorithm, the large number of states limits the speed to some extent.

In our experiment, when we use the Viterbi algorithm, the rate of process was 246 characters/sec. We speed up the deobfuscation process at a rate of 2,038 characters/sec with a beam width of 10 by using the beam search algorithm.

When it comes to the complexity of the weight function, ω(s1:t), it is almost negligible since trie has O(M ) complexity where M is the maximum length of words in the lexicon.

3.2 Parameter learning

Our model has several parameters, ⃗ θ 3 , which should be optimized. We adapt greedy hillclimbing search to get local maxima. By using a training set which consists of obfuscated words and corresponding answers, we find the parameter set which locally maximize the log likelihood.

where (s1:t, y1:t) is a pair of obfuscated observations in the training data and corresponding answer's state sequence. ⃗ θ0 is the locally optimized parameter set and n is the number of lines of the training set. η and ϵ determine the probability of the self-transition and null transition respectively [Lee and Ng, 2005].

We start optimizing parameters, ⃗ θ, from initial values which are set according to their characteristics. For example, the parameter for the self-transition should be significantly smaller than the parameter for non-self-transition, because the insertion of characters is less frequent than correctly written letters. From the starting point, we optimize each value in ⃗θ and get ⃗ θ0 which is locally maximized around the initial values of the parameters.

2 Leet is defined as the modification of written text, see (en.wikipedia.org/wiki/Leet) website.

3⃗ θ = {η, ϵ, ρ1, ρ2, ρ3, σ1, σ2, ψ1, ψ2, ψ3}.

4 Experimental results

In our experiment, we define transition probabilities, P (qt|qt-1), and make Φ using a English dictionary (83,552 words) and large email data from spam corpus. 4 Parameters of our model are optimized with actual spam emails containing 65 lines and 447 words. We perform an experiment with actual spam emails which contain 313 lines and 2,131 words, including insertion, substitution, deletion, segmentation, and the mixed types of obfuscation. Almost all the words are included in the lexicon that we use. Table 2 exhibits some examples of various types of obfuscation.

Our experiments are performed using various decoding methods. We use the one-best and two-best searches with various beam widths and evaluate the results in terms of the accuracy and speed. Table 3 shows the accuracy of the results of spam deobfuscation when two-best search with a beam width of five is used. It represents that our model performs well for the insertion, substitution, segmentation, and the mixed types of obfuscation. However, considering that the deletion type of obfuscation is rare in real spam emails, our model has not trained it well.

Figure 8 shows the effect of N-best search and beam width for the overall accuracy and computation speed 5 of our model. Overall accuracy is defined as the fraction of correctly deobfuscated words and the computation speed is the number of processed characters per second. As the beam width increases, the overall accuracy rises a little only when the onebest search with a beam width of five is used. However, it turns out that the two-best search significantly improves the overall accuracy compared to the one-best search. The twobest search with a beam width of five shows the accuracy of 96.9% and the processing speed of 2,136 characters/sec. The experimental results show that two-best search with a beam width of five is a desirable configuration maintaining the high accuracy and a low computational cost.

5 Conclusions

We have presented dynamically weighted hidden Markov model (DW-HMM) which dramatically reduced the number of states when a few sets of states had distinct emission probabilities. The states sharing the same emission probabilities were grouped into super-states in DW-HMM. State transition probabilities in DW-HMM were determined by a weight function which reflects the original state transitions maintained in the data structure Φ, rather than a large transition probability matrix. We have shown how an HMM is converted into its associated DW-HMM, retaining a few number of super-sates. We have applied DW-HMM to the task of spam deobfuscation, where the LT-HMM was replaced by the DW-HMM. Our experimental results showed that it improves the speed from 10 characters/sec to 207 characters/sec when a straightforward Viterbi algorithm is applied. DW-HMM can be applied to diverse areas where a highly structured HMM is used with a few distinct emission probabilities. For example, in speech and handwriting recognition areas, our model may be used to address the large vocabulary problems. We can also use DW-HMM where the state transition structure frequently changes since it is easy to maintain such changes for DW-HMM.

5 Computation speed is evaluated when DW-HMM is executed on PC with Pentium 4 1.66GHz and 512MB RAM.

Acknowledgment

Portion of this work was supported by Korea MIC under ITRC support program supervised by the IITA (IITA-2005C1090-0501-0018).