CN104166708A - Mobile phone virus spreading modeling method based on social network and semi-Markov process - Google Patents

Abstract

The invention discloses a mobile phone virus propagation modeling method based on a social network and a semi-Markov process. The main technical points of this method include: firstly, the behavior of social interaction by sending short messages or multimedia messages is abstracted into a social network, and then the characteristics of the social network are analyzed to reveal the relationship between it and the spread of mobile phone viruses; secondly, the introduction of A semi-Markov process is used to model the state transition of the node, and the number of interactions and the state transition probability are organically combined to effectively discover the law of the state change of the node after being attacked by the virus; thirdly, the introduction of infection coefficient and resistance coefficient to describe the impact of individual differences on virus transmission; a simulator was also developed for experimental verification. Compared with the prior art, the present invention has the advantage of considering the impact of people's social behavior and individual differences on virus transmission, and the method is simple, practical and can effectively improve the speed and accuracy of predicting virus transmission.

Description

Modeling Method of Mobile Virus Propagation Based on Social Network and Semi-Markov Process

technical field

The present invention relates to modeling and analysis of mobile phone virus propagation dynamics, provides a mobile phone virus propagation modeling method based on social network and semi-Markov process, and belongs to the field of network and information security.

Background technique

As short message (short message service, SMS) and multimedia messaging (multimedia messaging service, MMS) are more and more popular, making SMS/MMS-based social networks very suitable for the spread of mobile phone viruses. Therefore, how to model and analyze the dynamics of virus propagation based on SMS/MMS has become an important issue in the security of mobile communication networks. The virus spreads when people send and receive SMS/MMS for social interaction, and has the characteristics of strong concealment, fast transmission speed, and great harm. In addition, the node degree distribution of SMS/MMS-based social network has the characteristics of power-law distribution. According to the characteristics of social network and mobile phone virus transmission, a virus transmission dynamics model is designed to describe the impact of people's social interaction on mobile phone virus transmission and The impact of individual variability on the spread of mobile phone viruses. This is conducive to discovering the spread of mobile phone viruses and predicting the spread of mobile phone viruses, laying the foundation for curbing the spread of mobile phone viruses.

At present, most of the existing research on mobile phone viruses uses the principles of biological virus transmission to model, which cannot be applied to large-scale network environments, and does not consider the impact of people's social behavior and individual differences on mobile phones. Effects of viral spread.

Therefore, considering the needs of the country and people for network security, we propose a A Modeling Method for Mobile Virus Propagation Based on Social Network and Semi-Markov Process. This method abstracts the behavior of people sending SMS/MMS for social interaction into a social network, and then analyzes the characteristics of the social network to reveal the relationship between it and the spread of mobile phone viruses; introduces a semi-Markov process to analyze the status of nodes Transformation is modeled, and the number of interactions is organically combined with the state transition probability; the infection coefficient and resistance coefficient are introduced to describe the impact of individual differences on virus transmission; a hybrid programming technology of Visual C++ 6.0 and MATLAB 7.0 is used to develop a Simulator for experimental verification.

Contents of the invention

The purpose of the present invention is to provide a mobile phone virus propagation modeling method based on social network and semi-Markov process. This method takes into account the complexity of the virus and the uncertainty of its transmission process, and can better describe the impact of people's social behavior and individual differences on the spread of the virus. So as to provide an effective solution for the prevention and control of mobile phone viruses.

In order to achieve the above purpose, the present invention utilizes the actual SMS/MMS communication data to construct a social network, so as to discover and describe the relationship between the interaction between different individuals and the virus transmission. Then, analyze and model the abnormal behavior of the nodes and their transformation rules; finally, introduce the infection coefficient and resistance coefficient to reveal the relationship between individual differences and virus transmission. The main invention content is as follows.

(1) Construction of social network

It can be represented by an undirected weighted graph G = ( V , E , W ), where: V represents the set of vertices, that is, mobile phones in the mobile communication network; E is the directed edge between nodes in the network, representing the relationship between mobile phone users The behavior of sending short messages, the arc head of the edge points to the recipient of the short message behavior; W is the weight of the directed edge, which represents the value of the short message sending behavior, and the larger the value, the more the number of short messages sent. d _i represents the degree of vertex i , that is, the number of mobile phones (means the number of links or mobile phones have d _i friends). C _ij represents the number of short messages and multimedia messages sent from i to j . In addition, two functions f ( i ) and f ( i , j ) are introduced to map each vertex and each edge . Therefore, the graph can use f ( i ) and f ( i , j ) to determine the weights of vertices and edges, respectively. The mapping function of the weights of vertices and edges is expressed as: f ( i ) = d _i , f ( i , j ) = C _ij +C _ji .

The weights of vertices and edges can be used to represent the probability of a mobile phone being infected by a virus at the same time. From f ( i ) = d _i we can see that the weight of a vertex depends on d _i . For SMS/MMS-based viruses, if the in-degree of a certain mobile phone is large, it means that it is more likely to be infected by the virus, while the large out-degree means that it is more likely to infect other mobile phones with the virus. Therefore, those phones with large node degrees should be assigned a larger vertex weight no matter whether it has a large in-degree or a large out-degree. The social interaction between any two mobile phones can be represented by f ( i , j ) = C _ij +C _ji .

(2) Node status classification

The basis of modeling the abnormal behavior of mobile phones after virus infection by semi-Markov process is to divide mobile phones into different states. According to the behavior characteristics displayed by the mobile phone itself, it is proposed to divide the individual states into the following four types.

A) Susceptible state S (Susceptible), that is, the node is not infected and has no immunity; the virus starts from the node in the susceptible state S and spreads around through the network connection.

B) Latent state E (Exposed). After the virus invades, the infected nodes are in the latent state E. Because different nodes attach different importance to the virus, some nodes in the latent period E will enter the state I and R , and the other part will return state S.

C) Infected state I (Infected), that is, the node has been infected, and the node is infectious at this time.

D) Immune state R (Recovered). After the virus spreads, some nodes in state S take some safety measures to pre-immunize the virus and enter immune state R.

(3) Mutual conversion relationship between states

The mutual conversion relationship between the states of the nodes is as follows.

A) Due to the installation of anti-virus software, a node in a susceptible state is converted to an immune state; due to many reasons, the node can also be converted to a latent state, such as: no anti-virus software is installed, and applications are downloaded and installed from the Internet at will.

B) If a node in an infected state can install anti-virus software in time, it can be transformed into an immune state or a susceptible state.

C) If a node in a latent state can take corresponding safety measures in time, it can be transformed into an immune state or a susceptible state; but if it is in a virus outbreak period, it may also be transformed into an infected state.

D) When a new virus appears, a node in an immune state can be converted into a susceptible node again.

(4) Node abnormal behavior modeling

In a semi-Markov process, the transition of a node from one state to another can be represented by two matrices: P = ( p _ij ) and F ( t ) = ( F _ij ( t )), where p _ij represents the node The transition probability from state Z _i to state Z _j ; the F _ij ( t ) node represents the time distribution from current state Z _i to state Z _j . Assuming a semi-Markov process { X ( t ), t ≥ 0}, its state space is W = { S , E , I , R } and the one-step transition probability matrix P of DTMC, when t → ∞, The transition distribution P _ij ( t ) obeys the non-lattice distribution and has a limit probability P _j , then

Among them, M ( j ) and M ( k ) represent the average time of staying in states Z _j and Z _k respectively, and , (Let T _i be the time spent in state Z _i and T _j be the time spent in state Z _j ); is a stationary distribution of { Z _n }, and , , .

To calculate P _j , it is necessary to find p _ij and M ( i ). However, it is not an easy task to calculate P _j through this formula, because it is difficult to determine the residence time M ( i ). Therefore, the present invention not only provides a node behavior model based on a semi-Markov process and calculation expressions for analyzing limit state probability, but also establishes a network scene and provides corresponding theoretical analysis.

(5) Individual difference modeling

Since the spread of the virus is related to the resistance of the individual and the strength of the virus infectivity, most of the existing virus spread models do not consider the impact of individual differences on the spread of the virus. Therefore, the present invention introduces three parameters to characterize the influence of individual differences on virus transmission, which are specifically described as follows.

A) Infection coefficient: Expressed by IC _ji (Infection Coefficient, IC), that is, the strength of node j 's infectivity to i ( ); when IC _ji =0, it means that the node is not infectious; when IC _ji =1, it means that the node is extremely infectious.

B) Resistance coefficient: represented by RC _ij (Resisted Coefficient, RC), that is, the resistance of node i to j ( ); when RC _ij =1, it means that the node has extremely strong resistance.

C) Infection Threshold: represented by IT _i (Infection Threshold, IT), which is the sum of the influence of node i 's friend nodes on it. It is used to judge whether the state of the node in state S will change.

(6) Virus transmission model

According to the characteristics of SMS/MMS virus propagation, on the basis of constructing the social relationship graph, the corresponding state transition algorithm is designed, and the algorithm is used to describe the propagation process of SMS/MMS virus. The state transition algorithm is specifically.

Step 1: Initialize the network. According to the SMS/MMS data set, the relevant information of the network is counted, such as the number of nodes, the sending status of SMS, etc.

Step 2: Initialize the state of each node. Randomly select node j and set its state to I , and set the state of other nodes to S.

Step 3: Statistics of friend node information. Each node counts its own friend node information according to the situation of sending SMS/MMS with other nodes.

Step 4: Assuming that node j is visited at a certain time t , assuming that T represents the threshold for the node to change from S state to E state, then: if the state of j is I , then traverse j ’s friend nodes, if its friend node i ’s The state is S , and at this time j sends a short message or multimedia message to i , then: A) when , then i transitions to state E with probability p _SE ; B) when , then i remains in state S unchanged; C) when IC _ji =0 or RC _ij =1, then i transitions to state R with probability p _SR ; at the same time, j transitions to state R with probability p _IR ; if j 's The state is E , then the node changes to state R with probability p _ER , or the node changes to state I with probability p _EI ; repeat step 4 until all nodes are traversed.

Step 5: t = t +1, the algorithm ends.

(7) Virus transmission analysis

Refer to the existing analysis methods of infectious disease transmission (such as SARS, HIV, H1N1, etc.) and cable network virus transmission (such as Code-Red, Slammer, etc.) to determine the number of relevant parameters related to mobile phone virus transmission and the value of each parameter range, the size of the initial value, etc. Analyze the main form of the topological structure on which the virus spreads, and design an Erdǒs-Rényi (ER) network topology generation algorithm based on directed graphs. The main idea is to use random graph theory to Simulation analysis of virus propagation under directed graph ER network topology.

Since the static topology generation algorithm in the complex network field only considers the characteristics of the network itself, when it is applied to the mobile phone virus propagation network generation, it also needs to consider the conditions and attributes related to the virus propagation process. For example, whether to create an edge between two nodes, in addition to meeting their respective degree value requirements, it is also necessary to consider whether the individual interaction meets the given local judgment conditions (resistance factor and interaction times, etc.), and at the same time, it is necessary to give the edge Attribute values related to the interaction relationship (such as the number of interactions, duration, etc.). A simulator was developed using the mixed programming technology of Visual C++ 6.0 and MATLAB 7.0 to verify the correctness and effectiveness of the directed graph-based ER network topology generation algorithm.

Description of drawings

Figure 1 is an example of a social network graph.

Figure 2 is a state transition diagram.

Figure 3 is a flowchart of the node state transition algorithm.

Figure 4 is a flowchart of the data analysis algorithm.

Figure 5 is an analysis diagram of mobile phone virus transmission dynamics.

Detailed ways

The present invention will be described in further detail below in conjunction with the accompanying drawings.

(1) Construction of social network

It can be represented by an undirected weighted graph G = ( V , E , W ), where: V represents the set of vertices, that is, mobile phones in the mobile communication network; E is the directed edge between nodes in the network, representing the relationship between mobile phone users The behavior of sending short messages, the arc head of the edge points to the recipient of the short message behavior; W is the weight of the directed edge, which represents the value of the short message sending behavior, and the larger the value, the more the number of short messages sent. d _i represents the degree of vertex i , that is, the number of mobile phones (means the number of links or mobile phones have d _i friends). C _ij represents the number of short messages and multimedia messages sent from i to j . In addition, two functions f ( i ) and f ( i , j ) are introduced to map each vertex and each edge . Therefore, the graph can use f ( i ) and f ( i , j ) to determine the weights of vertices and edges, respectively. The mapping function of the weights of vertices and edges is expressed as: f ( i ) = d _i , f ( i , j ) = C _ij +C _ji .

The weights of vertices and edges can be used to represent the probability of a mobile phone being infected by a virus at the same time. From f ( i ) = d _i we can see that the weight of a vertex depends on d _i . For SMS/MMS-based viruses, if the in-degree of a certain mobile phone is large, it means that it is more likely to be infected by the virus, while the large out-degree means that it is more likely to infect other mobile phones with the virus. Therefore, those phones with large node degrees should be assigned a larger vertex weight no matter whether it has a large in-degree or a large out-degree. The social interaction between any two mobile phones can be represented by f ( i , j ) = C _ij +C _ji . Any two mobile phones have a chance to become friends no matter when they communicate by sending SMS and MMS. Therefore, the probability of opening and activating a message from the other party carrying a virus is high. It shows that the social network can not only reveal how any two mobile phones are connected with each other, but also describe how the virus uses this social relationship to spread.

The present invention uses SMS and MMS records provided by China Telecom, one of the largest mobile communication network operators in China, to study the construction of social networks. The message log includes approximately 20 million SMS and MMS messages sent by 400,000 users in a three-week period in October 2012. In order to protect user privacy, the contents of SMS and MMS are blocked when they are extracted, and the extracted information only retains the phone numbers of the sender and receiver and the sending time, and the phone numbers are also technically processed, and other numbers are used to replace. In order to further illustrate the construction process of the social network, a social network was built by extracting the number of text messages/MMS messages sent by 10 mobile phones within a week (see Figure 1).

(2) Node status classification

The basis of modeling the abnormal behavior of mobile phones after virus infection by semi-Markov process is to divide mobile phones into different states. According to the behavioral characteristics displayed by the mobile phone itself, the states of individuals can be divided into the following four types.

A) Susceptible state S (Susceptible), that is, the node is not infected and has no immunity; the virus starts from the node in the susceptible state S and spreads around through the network connection.

B) Latent state E (Exposed). After the virus invades, the infected nodes are in the latent state E. Because different nodes attach different importance to the virus, some nodes in the latent period E will enter the state I and R , and the other part will return state S.

C) Infected state I (Infected), that is, the node has been infected, and the node is infectious at this time.

D) Immune state R (Recovered). After the virus spreads, some nodes in state S take some safety measures to pre-immunize the virus and enter immune state R.

(3) Mutual conversion relationship between states

The mutual conversion relationship between the states of the nodes is as follows.

A) Due to the installation of anti-virus software, a node in a susceptible state is converted to an immune state; due to many reasons, the node can also be converted to a latent state, such as: no anti-virus software is installed, and applications are downloaded and installed from the Internet at will.

B) If a node in an infected state can install anti-virus software in time, it can be transformed into an immune state or a susceptible state.

C) If a node in a latent state can take corresponding safety measures in time, it can be transformed into an immune state or a susceptible state; but if it is in a virus outbreak period, it may also be transformed into an infected state.

D) When a new virus appears, a node in an immune state can be converted into a susceptible node again.

After a node is attacked by a virus, its state transition has the following characteristics: first, the future state of the node is only related to its current state; distributed. The above characteristics are in line with the basic properties of the semi-Markov process. Therefore, the semi-Markov process can be used to model the abnormal behavior of the mobile phone SMS/MMS virus transmission node. Combined with the characteristics of mobile phone virus transmission, a node state transition diagram based on a semi-Markov process can be obtained (see Figure 2).

(4) Node abnormal behavior modeling

In a semi-Markov process, the transition of a node from one state to another can be represented by two matrices: P = ( p _ij ) and F ( t ) = ( F _ij ( t )), where p _ij represents the node The transition probability from state Z _i to state Z _j ; the F _ij ( t ) node represents the time distribution from current state Z _i to state Z _j . Therefore, the transition probability matrix of { Z _n } is:

Among them, p _ii =0 means that the state transition in { Z _n } can only change from one state to another state; in the above formula, there is a case where the transition probability is zero, such as p _IE =0, p _IE =0, which means A node in an infected state does not transition to a susceptible or latent state. In addition, since the sum of transition probabilities of a state in the random matrix is equal to 1, p _IR =1, p _RS =1.

Assuming a semi-Markov process { X ( t ), t ≥ 0}, its state space is W = { S , E , I , R } and the one-step transition probability matrix P of DTMC, when t → ∞, The transition distribution P _ij ( t ) obeys the non-lattice distribution and has a limit probability P _j , then

Among them, M ( j ) and M ( k ) represent the average time of staying in states Z _j and Z _k respectively, and , (Let T _i be the time spent in state Z _i and T _j be the time spent in state Z _j ); is a stationary distribution of { Z _n }, and , , .

To calculate P _j , it is necessary to find p _ij and M ( i ). However, it is not an easy task to calculate P _j through this formula, because it is difficult to determine the residence time M ( i ).

First, assume that within the time period [0, t ], the total number of transitions from state i to other states k is N _ik ( ), then p _ij can be approximated as: .

In addition, establish a network scenario and give corresponding theoretical analysis. For the convenience of analysis, the following assumptions are made.

A) Each node has the same health index limit value H , if when the node's health index limit value is lower than the threshold There is a possibility of virus infection.

B) When the health index of each node is lower than the threshold When , it will be converted from a susceptible state to a latent state; when the health index of each node is lower than the threshold When , it will be converted from a latent state to an infected state; when the health index of each node is greater than the threshold ( ), it will transition from an infected state to an immune state.

C) When any two nodes conduct social communication through SMS/MMS per unit time, they will encounter a risk index ( ); each node has a repair index per unit time ( ).

D) The time each node resides in the network is random and related to the behavior of mobile phone users, which can be used To represent.

E) The expected time for each node to switch from the immune state to the susceptible state is .

because It is related to the number of interactions of nodes, so it can be expressed as:

Among them, TM represents the total number of messages sent to it by all friend nodes of node i , using To represent.

So far, since there is no effective method for analyzing the limit probability, a heuristic method is proposed to evaluate the expected state transition time M ( i , j ) ( ). The available state transition expected time matrix Q is:

If a node's health index is lower than When , the node changes from susceptible state to latent state, M ( S , E ) can be approximated as:

Likewise, M ( S , I ), M ( E , S ), M ( E , I ), and M ( I , R ) can be approximated as:

Generally, if any node transitions from other states to the immune state, the average time required is , then M ( S , R ) and M ( E , R ) can be approximated as: , .

In addition, if the average time required for any node to transition from an immune state to a susceptible state is , then M ( R , S ) can be approximated as: .

Therefore, the state transition expectation time matrix Q of { Z _n } can be approximated as:

In this way, by solving the matrix Q, the stay time M ( i ) can be obtained.

(5) Individual difference modeling

Since the spread of the virus is related to the resistance of the individual and the strength of the virus infectivity, most of the existing virus spread models do not consider the impact of individual differences on the spread of the virus. Therefore, the present invention introduces three parameters to characterize the impact of individual differences on virus transmission. For the convenience of analysis, the following assumptions are made: C _ji represents the number of SMS/MMS messages sent by node j to node i within a week, C _max represents the maximum number of SMS/MMS messages sent by any pair of nodes within a week; N _i represents the number of node i i 's friend node number; , is a constant, set according to the specific actual environment; and are the adjustment factors of the infection coefficient and the resistance coefficient ( , ≥ 0). The specific description of the three parameters is as follows.

A) Infection coefficient: Expressed by IC _ji (Infection Coefficient, IC), that is, the strength of node j 's infectivity to i ( ); when IC _ji =0, it means that the node is not infectious; when IC _ji =1, it means that the node is extremely infectious.

B) Resistance coefficient: represented by RC _ij (Resisted Coefficient, RC), that is, the resistance of node i to j ( ); when RC _ij =1, it means that the node has extremely strong resistance.

C) Infection Threshold: represented by IT _i (Infection Threshold, IT), which is the sum of the influence of node i 's friend nodes on it. It is used to judge whether the state of the node in state S will change.

In order to ensure that the final calculated IT _i value is in the interval [0,1], the following normalization processing is done.

Among them, N represents the total number of nodes in the network, and min{ IT _k } and max{ IT _k } represent the minimum and maximum values of the infection index in all nodes, respectively.

(6) Virus transmission model

According to the characteristics of SMS/MMS virus propagation, on the basis of constructing the social relationship graph, the corresponding state transition algorithm is designed, and the algorithm is used to describe the propagation process of SMS/MMS virus. The state transition algorithm is specifically.

Step 1: Initialize the network. According to the SMS/MMS data set, the relevant information of the network is counted, such as the number of nodes, the sending status of SMS, etc.

Step 2: Initialize the state of each node. Randomly select node j and set its state to I , and set the state of other nodes to S.

Step 3: Statistics of friend node information. Each node counts its own friend node information according to the situation of sending SMS/MMS with other nodes.

Step 4: Assuming that node j is visited at a certain time t , assuming that T represents the threshold for the node to change from S state to E state, then: if the state of j is I , then traverse j ’s friend nodes, if its friend node i ’s The state is S , and at this time j sends a short message or multimedia message to i , then: A) when , then i transitions to state E with probability p _SE ; B) when , then i remains in state S unchanged; C) when IC _ji =0 or RC _ij =1, then i transitions to state R with probability p _SR ; at the same time, j transitions to state R with probability p _IR ; if j 's The state is E , then the node changes to state R with probability p _ER , or the node changes to state I with probability p _EI ; repeat step 4 until all nodes are traversed.

Step 5: t = t +1, the algorithm ends.

Therefore, the flow chart of the node state transition algorithm for SMS/MMS-based mobile phone virus propagation dynamics analysis can be obtained (see Figure 3).

(7) Virus transmission analysis

Refer to the existing analysis methods of infectious disease transmission (such as SARS, HIV, H1N1, etc.) and cable network virus transmission (such as Code-Red, Slammer, etc.) to determine the number of relevant parameters related to mobile phone virus transmission and the value of each parameter range, the size of the initial value, etc. Analyze the main form of the topological structure on which the virus spreads, and design an Erdǒs-Rényi (ER) network topology generation algorithm based on directed graphs. The main idea is to use random graph theory to Simulation analysis of virus propagation under directed graph ER network topology.

Since the static topology generation algorithm in the complex network field only considers the characteristics of the network itself, when it is applied to the mobile phone virus propagation network generation, it also needs to consider the conditions and attributes related to the virus propagation process. For example, whether to create an edge between two nodes, in addition to meeting their respective degree value requirements, it is also necessary to consider whether the individual interaction meets the given local judgment conditions (resistance factor and interaction times, etc.), and at the same time, it is necessary to give the edge Attribute values related to the interaction relationship (such as the number of interactions, duration, etc.).

A simulator was developed using the mixed programming technology of Visual C++ 6.0 and MATLAB 7.0 to verify the correctness and effectiveness of the directed graph-based ER network topology generation algorithm. Combined with the characteristics of mobile phone virus transmission dynamics, the flow chart of data analysis algorithm (see Figure 4) and the analysis diagram of mobile phone virus transmission dynamics (see Figure 5) can be obtained.

Claims (4)

1. A mobile phone virus propagation dynamics modeling and analysis method based on social network and semi-Markov process, it is characterized in that: first utilize the actual short message/MMS communication data that people carry out social interaction in daily life to construct Social network, which is used to describe the relationship between social interaction and virus transmission; then, establish a node abnormal behavior model to reveal the state transition rules of nodes after being attacked by viruses, such as the time distribution of nodes staying in each state, node state The mutual conversion relationship among them; finally, an individual difference analysis mechanism is established to describe the impact of individual differences on virus transmission. 2. The social network based on SMS/MMS according to claim 1, characterized in that: the social network behavior shown by mutual sending of SMS/MMS between mobile phone users is analyzed and social network is constructed, and complex network theory is introduced To analyze the characteristics of the social network, and describe the impact of various parameters based on SMS/MMS virus spread on the virus spread. 3. The node abnormal behavior model according to claim 1, characterized in that: the state of the mobile phone before and after infection of the virus is divided, so that the characteristics of the mobile phone in various states are more prominent; the model The division method of node states and the time distribution law of staying in each state are analyzed; and the semi-Markov process is introduced to reveal the mutual conversion relationship between node states, the limit probability of being in each state and the internal relationship between them. 4. The individual difference analysis mechanism according to claim 1, characterized in that: Infection coefficient (the strength of node infectivity) and resistance coefficient (node resistance) are introduced to describe individual differences, and the infection coefficient is used to and the resistance coefficient to predict whether the state of a node in the susceptible state S will change.