Patching Scheme For Worm Containment In Mobile Social Networks

The rapid development of social networks makes people tend to use mobile de-vices to access social networks for getting information. On the other hand, more andmorethird-partyapplicationsareallowedtoberunoverOpen-APIcellularphoneoper-ation systems. However, this openness leads to making worms and malicious softwarepropagate among mobile devices by taking advantage of people’s social information.Moreover, the limitation of mobile network’s bandwidth and patch-download servers’load pose new challenges to worm containment strategy in mobile social networks.The problem we study in this paper is: How to select a set of nodes, whose size isrelatively small and fxed. And this set of nodes can achieve the following goal: Whenthe infection rate in the network reaches a certain threshold, we patch nodes in this set,and regard them as patch-seed nodes, which can propagate patches in P2P way to allthe nodes in shortest time, and meanwhile reduce the infection rate in the network.In the beginning, this paper briefy introduces social network’s evolution, its de-velopment tendency, mobile devices’ application on it, and the security problems itis undergoing. The main work of this paper is: We propose a new problem in thearea of social networks’ security, which is that when the number of patch-seed nodesare fxed, how to select them and propagate patches in P2P way, in order to reduceinfection rate and propagate patches to all the nodes in the social network as soon aspossible. To solve this problem, we frst analyze the ways of worm’s and patch’s propa-gation. Based on the actual situations, worm and patch propagation models are set up.Meanwhile, we transform our problem into a combinatorial optimization problem, anddefne its objective function and constraints. For static network, we use shortest pathfast algorithm to calculate the value of objective function, and use simulated annealing algorithm to select patch-seed nodes. For dynamic network, we classify all kinds ofnetwork’s changes into fve types. To each type, we design the solution to refresh thevalue of objective function by using local adjustment, which can avoid unnecessaryrecalculation and improve the efciency of the algorithm. The results of experimentsshow that our designed strategy is more efcient. In diferent experimental condition-s, the strategy can reduce infection rate efciently and meanwhile propagate patchesquickly. Moreover, the experimental results also show that to patches’ propagationways, serial way is more efcient than parallel way.The creative points of this paper are as following:(1) Propose a new securityproblem in social networks, which is that when the number of patch-seed nodes arefxed, how to select them to reduce infection rate and propagate patches to all the nodesin shortest time；(2)Set up the propagation models of worms and patches, and alsopropose two ways of patch propagation: parallel way and serial way;(3) Transform theproblem into a combinatorial optimization problem. For static network, we design aheuristic algorithm to fast select patch-seed nodes. For dynamic network, we designalgorithms to refresh the value of objective function by using local adjustment;...