document: the ability to gain control of a huge amount of internet hosts could be easily achieved by the exploitation of worms which self - propagate through popular internet applications and services . 
   internet worms have already proven their capability of inflicting massive - scale disruption and damage to the internet infrastructure . 
   these worms employ normal _ scanning _ as a strategy to find potential vulnerable targets , i.e. , they randomly select victims from the ip address space . 
   so far , there have been many existing schemes that are effective in detecting such scanning worms  @xcite , e.g. , by capturing the scanning events  @xcite or by passively detecting abnormal network traffic activities  @xcite .    in recent years 
   , peer - to - peer ( p2p ) overlay applications have experienced an explosive growth , and now dominate large fractions of both the internet users and traffic volume  @xcite ; thus , a new type of worms that leverage the popular p2p overlay applications , called _ p2p worms _ , pose a very serious threat to the internet  @xcite . 
   generally , the p2p worms can be grouped into two categories : _ passive _ p2p worms and _ active _ p2p worms . 
   the passive p2p worm attack is generally launched either by copying such worms into a few p2p hosts shared folders with attractive names , or by participating into the overlay and responding to queries with the index information of worms . 
   unable to identify the worm content , normal p2p hosts download these worms unsuspectedly into their own shared folders , from which others may download later without being aware of the threat , thus passively contributing to the worm propagation . 
   the passive p2p worm attack could be mitigated by current patching systems  @xcite and reputation models  @xcite . in this paper , we focus on another serious p2p worm : active p2p worm . 
   the active p2p worms could utilize the p2p overlay applications to retrieve the information of a few vulnerable p2p hosts and then infect these hosts , or as an alternative , these worms are directly released in a hit list of p2p hosts to bootstrap the worm infection . since the active p2p worms have the capacity of gaining control of the infected p2p hosts , they could perform rapid _ topological self - propagation _ by spreading themselves to neighboring hosts , and in turn , spreading throughout the whole network to affect the quality of overlay service and finally cause the overlay service to be unusable . 
   the p2p overlay provides an accurate way for worms to find more vulnerable hosts easily without probing randomly selected ip addresses ( i.e. , low connection failure rate ) . 
   moreover , the worm attack traffic could easily blend into normal p2p traffic , so that the active p2p worms will be more deadly than scanning worms . 
   that is , they do not exhibit easily detectable anomalies in the network traffic as scanning worms do , so many existing defenses against scanning worms are no longer effective  @xcite .    besides the above internal infection in the p2p overlay 
   , the infected p2p hosts could again mount attacks to external hosts . in similar sense , since the p2p overlay applications are pervasive on today s internet , it is also attractive for malicious external hosts to mount attacks against the p2p overlay applications and then employ them as an ideal platform to perform future massive - scale attacks , e.g. , botnet attacks .    in this paper 
   , we aim to develop a _ 
   holistic _ immunity system to provide the mechanisms of both _ internal defense _ and _ external protection _ against active p2p worms . in our system 
   , we elect a small subset of p2p overlay nodes , _ phagocytes _ , which are immune with high probability and specialized in finding and `` eating '' active p2p worms . 
   each phagocyte in the p2p overlay is assigned to manage a group of p2p hosts . 
   these phagocytes monitor their managed p2p hosts connection patterns and traffic volume in an attempt to detect active p2p worm attacks . 
   once detected , the local isolation procedure will cut off the links of all the infected p2p hosts . 
   afterwards , the responsible phagocyte performs the contagion - based alert propagation to spread worm alerts to the neighboring phagocytes , and in turn , to other phagocytes . here 
   , we adopt a threshold strategy to limit the impact area and enhance the robustness against the malicious alert propagations generated by infected phagocytes . finally , the phagocytes help acquire the software patches and distribute them to the managed p2p hosts . with the above four modules , i.e. , detection , local isolation , alert propagation and software patching , our system is capable of preventing internal active p2p worm attacks from being effectively mounted within the p2p overlay network . 
   the phagocytes also provide the access control and filtering mechanisms for the connection establishment between the internal p2p overlay and the external hosts . 
   firstly , the p2p traffic should be contained within the p2p overlay , and we forbid any p2p traffic to leak from the p2p overlay to external hosts . 
   this is because such p2p traffic is generally considered to be malicious and it is possible that the p2p worms ride on such p2p traffic to spread to the external hosts . 
   secondly , in order to prevent external worms from attacking the p2p overlay , we hide the p2p hosts ip addresses with the help of scalable distributed dns service , e.g. , codons  @xcite . 
   an external host who wants to gain access to the p2p overlay has no alternative but to perform an interaction towards the associated phagocyte to solve an adaptive computational puzzle ; then , according to the authenticity of the puzzle solution , the phagocyte can determine whether to process the request . 
   we implement a prototype system , and evaluate its performance on a massive - scale testbed with realistic p2p network traces . 
   the evaluation results validate the effectiveness and efficiency of our proposed holistic immunity system against active p2p worms .    * outline*. we specify the system architecture in section  [ sec : systemarchitecture ] . 
   sections  [ sec : internaldefenses ] and  [ sec : externaldefenses ] elaborate the internal defense and external protection mechanisms , respectively . 
   we then present the experimental design in section  [ sec : exdesign ] , and discuss the evaluation results in section  [ sec : exresults ] . 
   finally , we give an overview of related work in section  [ sec : relatedwork ] , and conclude this paper in section  [ conclusions ] . 
   current p2p overlay networks can generally be grouped into two categories  @xcite : _ structured _ overlay networks , e.g. , chord  @xcite , whose network topology is tightly controlled based on distributed hash table , and _ unstructured _ overlay networks , e.g. , gnutella  @xcite , which merely impose loose structure on the topology . 
   in particular , most modern unstructured p2p overlay networks utilize a two - tier structure to improve their scalability : a subset of peers , called _ ultra - peers _ , construct an unstructured mesh while the other peers , called _ leaf - peers _ , connect to the ultra - peer tier for participating into the overlay network .        as shown in figure  [ fig : lovers ] , 
   the network architecture of our system is similar to that of the two - tier unstructured p2p overlay networks . in our system , 
   a set of p2p hosts act as the phagocytes to perform the functions of defense and protection against active p2p worms . 
   these phagocytes are elected among the participating p2p hosts in terms of the following metrics : high bandwidth , powerful processing resource , sufficient uptime , and applying the latest patches ( interestingly , the experimental result shown in section  [ sec : exresults ] indicates that we actually do not need to have a large percentage of phagocytes applying the latest patches ) . as existing two - tier 
   unstructured overlay networks do , the phagocyte election is performed periodically ; moreover , even if an elected phagocyte has been infected , our internal defense mechanism ( described in section  [ sec : internaldefenses ] ) can still isolate and patch the infected phagocyte immediately . 
   in particular , the population of phagocytes should be small as compared to the total overlay population , otherwise the scalability and applicability are questionable .    as a result , 
   each elected phagocyte covers a number of managed p2p hosts , and each managed p2p host will belong to one closest phagocyte . 
   that is , the phagocyte acts as the proxy for its managed hosts to participate into the p2p overlay network , and has the control over the managed p2p hosts . 
   moreover , a phagocyte further connects to several nearby phagocytes based on close proximity . 
   our main interest is the unstructured p2p overlay networks , since most of the existing p2p worms target the unstructured overlay applications  @xcite . 
   naturally , due to the similar network architecture , our system can easily be deployed into the unstructured p2p overlay networks . moreover , for structured p2p overlay networks , a subset of p2p hosts could be elected to perform the functions of phagocytes . 
   we aim not to change the network architecture of the structured p2p overlay networks ; however , we elect phagocytes to form an overlay to perform the defense and protection functions  this overlay acts as a security wall in a separate layer from the existing p2p overlay , thus not affecting the original p2p operations . in the next two sections 
   , we will elaborate in detail our mechanisms of internal defense and external protection against active p2p worms . 
   in this section , we first describe the active p2p worm attacks , and then , we design our internal defense mechanism .      generally , active p2p worms utilize the p2p overlay to accurately retrieve the information of a few vulnerable p2p hosts , and then infect these hosts to bootstrap the worm infection . on one hand 
   , a managed p2p host clearly knows its associated phagocyte and its neighboring p2p hosts that are managed by the same phagocyte ; so now , an infected managed p2p host could perform the worm infection in several ways simultaneously . 
   firstly , the infected p2p host infects its neighboring managed p2p hosts very quickly . 
   secondly , the infected p2p host attempts to infect its associated phagocyte . 
   lastly , the infected managed p2p host could issue p2p key queries with worms to infect many vulnerable p2p hosts managed by other phagocytes . on the other hand 
   , a phagocyte could be infected as well ; if so , the infected phagocyte infects its managed p2p hosts and then its neighboring phagocytes . as a result , in such a topological self - propagation way , the active p2p worms spread through the whole system at extraordinary speed . 
   since the active p2p worms propagate based on the topological information , and do not need to probe any random ip addresses , thus their connection failure rate should be low ; moreover , the p2p worm attack traffic could easily blend into normal p2p traffic . 
   therefore , the active p2p worms do not exhibit easily detectable anomalies in the network traffic as normal scanning worms do .    in our system , 
   the phagocytes are those elected p2p hosts with the latest patches , and they can help their managed p2p hosts detect the existence of active p2p worms by monitoring these managed hosts connection transactions and traffic volume . if a managed p2p host always sends similar queries or sets up a large number of connections , the responsible phagocyte deduces that this managed p2p host is infected . 
   another pattern the phagocytes will monitor is to determine if a portion of the managed p2p hosts have some similar behaviors such as issuing the similar queries , repeating to connect with their neighboring hosts , uploading / downloading the same files , etc . 
   , then they are considered to be infected . 
   concretely , a managed p2p host s _ latest _ behaviors are processed into a _ behavior sequence _ consisting of continuous @xmath0 hereafter . ] 
   then , we can compute the behavior similarity between any two p2p hosts by using the _ levenshtein edit distance _  @xcite . without loss of generality 
   , we suppose that there are two behavior sequences @xmath1 and @xmath2 , in which @xmath3 , where @xmath4 , and @xmath5 is the length of the behavior sequence . 
   further , we can treat each behavior sequence @xmath6 as the combination of the _ operation sequence _ @xmath7 and the _ payload sequence _ @xmath8 . 
   now , we simultaneously _ sort _ the operation sequence @xmath9 and the payload sequence @xmath10 of the behavior sequence @xmath2 to make the following similarity score @xmath11 be maximum . to obtain the optimal solution , we could adopt the _ maximum weighted bipartite matching _ 
   algorithm  @xcite ; however , for efficiency , we use the _ greedy _ algorithm to obtain the approximate solution as an alternative . 
   @xmath12    here , @xmath13 denotes the sorted @xmath2 ; @xmath14 and @xmath15 denote the @xmath16 item of the sorted @xmath9 and @xmath17 , respectively ; @xmath18 is the levenshtein edit distance function . 
   finally , we treat the maximum @xmath11 as the similarity score of the two behavior sequences . 
   if the score exceeds a threshold @xmath19 , we consider the two p2p hosts perform similarly . 
   these detection operations are also performed between phagocytes at the phagocyte - tier because they could be infected as well though with latest patches . 
   the infected phagocytes could perform the worm propagation rapidly ; however , we have the local isolation , alert propagation and software patching procedures in place to handle these infected phagocytes after detected by their neighboring phagocytes with the detection module as described above . 
   note that , our detection mechanism is _ not _ a substitution for the existing worm detection mechanisms , e.g. , the worm signature matching  @xcite , but rather an effective p2p - tailored complement to them . specifically , some _ tricky _ p2p worms may present the features of mild propagation rate , polymorphism , etc . 
   , so they may maliciously propagate in lower speed than the aggressive p2p worms ; here , our software patching module ( in section  [ subsec : patching ] ) and several existing schemes  @xcite can help mitigate such tricky worm attacks . 
   moreover , a few elaborate p2p worms , e.g. , p2p-worm.win32.hofox , have recently been reported to be able to kill the anti - virus / anti - worm programs on p2p hosts  @xcite ; at the system level , some local countermeasures have been devised to protect defense tools from being eliminated , and the arms race will continue . in this paper , we assume that p2p worms can not disable our detection module , and therefore , each phagocyte can perform the normal detection operations as expected ; so can the following modules . 
   if a phagocyte discovers that some of its managed p2p hosts are infected , the phagocyte will cut off its connections with the infected p2p hosts , and ask these infected hosts to further cut off the links towards any other p2p hosts . 
   also , if a phagocyte is detected ( by its neighboring phagocyte ) as infected , the detecting phagocyte immediately issues a message to ask the infected phagocyte to cut off the connections towards the neighboring phagocytes , and then to trigger the software patching module ( in section  [ subsec : patching ] ) at the infected phagocyte ; after the software patching , these cut connections should be reestablished . with the local isolation module , 
   our system has the capacity of self - organizing and self - healing . 
   we utilize the local isolation to limit the impact of active p2p worms as quickly as possible . 
   if a worm event has been detected , i.e. , any of the managed p2p hosts or neighboring phagocytes are detected as infected , the phagocyte propagates a worm alert to all its neighboring phagocytes . 
   further , once a phagocyte has received the worm alerts from more than a threshold @xmath20 of its neighboring phagocytes , it also propagates the alert to all its neighboring phagocytes that did not send out the alert . in general 
   , we should appropriately tune @xmath20 to limit the impact area and improve the robustness against the malicious alert propagation generated by infected phagocytes . 
   the analytical study in  @xcite implied that the effective software patching is feasible for an overlay network if combined with schemes to bound the worm infection rate . in our system , the security patches are published to the participating p2p hosts using the following two procedures :    * periodical patching : * a patch distribution service provided by system maintainers periodically pushes the latest security patches to all phagocytes through the underlying p2p overlay , and then these phagocytes install and distribute them to all their managed p2p hosts . 
   note that , we can utilize the periodical patching to help mitigate the tricky p2p worms ( in section  [ subsec : detection ] ) which are harder to be detected . 
   * urgent patching : * when a phagocyte is alerted of a p2p worm attack , it will immediately pull the latest patches from a system maintainer via the direct http connection ( for efficiency , not via the p2p overlay ) , and then install and disseminate them to all its managed p2p hosts . 
   specifically , each patch must be signed by the system maintainer  @xcite , so that each p2p host can verify the patch according to the signature . 
   note that , the zero - day vulnerabilities are not fictional , thus installing the latest patches can not always guarantee the worm immunity . 
   the attackers may utilize these vulnerabilities to perform deadly worm attacks . 
   we can integrate our system with some other systems , e.g. , shield  @xcite and vigilante  @xcite , to defend against such attacks , which can be found in  @xcite . 
   as much as possible , the phagocytes provide the containment of p2p worms in the p2p overlay networks . 
   further , we utilize the phagocytes to implement the p2p traffic filtering mechanism which forbids any p2p connections from the p2p overlay to external hosts because such p2p connections are generally considered to be malicious  it is possible that the p2p worms ride on the p2p traffic to spread to the external hosts . 
   we can safely make the assumption that p2p overlay traffic should be contained inside the p2p overlay boundary , and any leaked p2p traffic is abnormal . 
   therefore , once this leakiness is detected , the phagocytes will perform the former procedures for local isolation , alert propagation and software patching . 
   our external protection mechanism aims to protect the p2p overlay network against the external worm attacks . 
   we hide the p2p hosts ip addresses to prevent external hosts from directly accessing the internal p2p resources . 
   this service can be provided by a scalable distributed dns system , e.g. , codons  @xcite . 
   such dns system returns the associated phagocyte which manages the requested p2p host . 
   then , the phagocyte is able to adopt our following proposed computational puzzle scheme to perform the function of access control over the requests issued by the requesting external host . 
   we propose a _ novel _ adaptive and interaction - based computational puzzle scheme at the phagocytes to provide the access control over the possible external worms attacking the internal p2p overlay .        since we are interested in how messages are processed as well as what messages are sent , for clarity and simplicity , we utilize the annotated alice - and - bob specification to describe our puzzle scheme . 
   as shown in figure  [ fig : puzzle ] , to gain access to the p2p overlay , an external host has to perform a lightweight interaction towards the associated phagocyte to solve an adaptive computational puzzle ; then , according to the authenticity of the puzzle solution , the phagocyte can determine whether to process the request . 
   * step 1 . * 
   the external host @xmath21 first generates a @xmath22-bit nonce @xmath23 as its session identifier @xmath24 . 
   then , the external host stores @xmath24 and sends it to the phagocyte . 
   * step 2 . * on receiving the message consisting of @xmath24 sent by the host @xmath21 , the phagocyte @xmath25 adaptively adjusts the puzzle difficulty @xmath26 based on the following two real - time statuses of the network environment . 
   @xmath27 _ status of phagocyte _ : this status indicates the usage of the phagocyte s resources , i.e. , the ratio of consumed resources to total resources possessed by the phagocyte . 
   the more resources a phagocyte has consumed , the harder puzzles the phagocyte issues in the future . 
   @xmath27 _ status of external host _ : in order to mount attacks against p2p hosts effectively , malicious external hosts have no alternative but to perform the interactions and solve many computational puzzles . 
   that is , the more connections an external host tries to establish , the higher the probability that this activity is malicious and worm - like . 
   hence , the more puzzles an external host has solved in the recent period of time , the harder puzzles the phagocyte issues to the very external host . 
   note that , since a malicious external host could simply spoof its ip address , in order to effectively utilize the status of external host , our computational puzzle scheme should have the capability of defending against ip spoofing attacks , which we will describe later . 
   subsequently , the phagocyte @xmath25 simply generates a _ unique _ @xmath22-bit session identifier @xmath28 for the external host according to the host s ip address @xmath29 ( extracted from the ip header of the received message ) , the host s session identifier @xmath24 and the puzzle difficulty @xmath26 , as follows :    @xmath30    here , the @xmath31 is a keyed hash function for message authentication , and the @xmath32 is a @xmath33-bit key which is _ periodically _ changed and only known to the phagocyte itself . 
   such @xmath32 limits the time external hosts have for computing puzzle solutions , and it also guarantees that an external attacker usually does not have enough resources to pre - compute all possible solutions in step 3 .    after the above generation process 
   , the phagocyte replies to the external host at @xmath29 with the host s session identifier @xmath24 , the phagocyte s session identifier @xmath28 and the puzzle difficulty @xmath26 . 
   once the external host has received this reply message , it first checks whether the received @xmath24 is really generated by itself . 
   if the received @xmath24 is bogus , the external host simply drops the message ; otherwise , the host stores the phagocyte s session identifier @xmath28 immediately . such reply and checking operations can effectively defend against ip spoofing attacks . 
   * step 3 . * 
   the external host @xmath21 retrieves the @xmath34 pair as the global session identifier , and then tries to solve the puzzle according to the equation below :    @xmath35    here , the @xmath36 is a cryptographic hash function , the @xmath37 is a hash value with the first @xmath26 bits being equal to @xmath38 , and the @xmath39 is the puzzle _ solution_. due to the features of hash function , the external host has no way to figure out the solution other than brute - force searching the solution space until a solution is found , even with the help of many other solved puzzles . the cost of solving the puzzle depends exponentially on the difficulty @xmath26 , which can be effortlessly adjusted by the phagocyte . 
   after the brute - force computation , the external host sends the phagocyte a message including the global session identifier ( i.e. , the @xmath40 pair ) , the puzzle difficulty , the puzzle solution and the actual _ request_. 
   once the phagocyte has received this message , it performs the following operations in turn :    * _ a _ ) * check whether the session identifier @xmath41 is really fresh based on the database of the past global session identifiers . 
   this operation can effectively defend against replay attacks . 
   * _ b _ ) * check whether the phagocyte s session identifier @xmath28 can be correctly generated according to equation [ eqn : sip ] . specifically 
   , this operation can additionally check whether the difficulty level @xmath26 reported by the external host is the original @xmath26 determined by the phagocyte .    * 
   _ c _ ) * check whether the puzzle solution is correct according to equation [ eqn : compute ] , which will also not incur significant overhead on the phagocyte .    * 
   _ d _ ) * store the global session identifier @xmath41 , and act as the overlay proxy to transmit the request submitted by the external host . 
   note that , in our scheme , the phagocyte stores the session - specific data and processes the actual request only after it has verified the external host s puzzle solution . 
   that is , the phagocyte does not commit its resources until the external host has demonstrated the sincerity .    specifically in the above sequence of operations , 
   if one operation succeeds , the phagocyte continues to perform the next ; otherwise , the phagocyte cancels all the following operations , and the entire interaction ends . 
   more details about the puzzle design rationale can be found in  @xcite . 
   so far , several computational puzzle schemes  @xcite have been proposed . 
   however , most of them consider only the status of resource providers , so they can not reflect the network environment completely . 
   recently , an ingenious puzzle scheme , portcullis  @xcite , was proposed . in portcullis , since a resource provider gives priority to requests containing puzzles with higher difficulty levels , to gain access to the requested resources , each resource requester , no matter legitimate or malicious , has to compete with each other and solve hard puzzles under attacks . 
   this may influence legitimate requesters experiences significantly . 
   compared with existing puzzle schemes , our adaptive and interaction - based computational puzzle scheme satisfies the fundamental properties of a good puzzle scheme  @xcite . 
   it treats each external host _ distinctively _ by performing a lightweight interaction to flexibly adjust the puzzle difficulty according to the real - time statuses of the network environment . 
   this guarantees that our computational puzzle scheme does not influence legitimate external hosts experiences significantly , and it also prevents a malicious external host from attacking p2p overlay without investing unbearable resources . 
   in real - world networks , hosts computation capabilities vary a lot , e.g. , the time to solve a puzzle would be much different between a host with multiple fast cpus and a host with just one slow cpu . to decrease the computational disparity , some other kinds of puzzles , e.g. , memory - bound puzzle  @xcite , could be complementary to our scheme . 
   note that , with low probability , a phagocyte may also be compromised by external worm attackers , then they could perform the topological worm propagation ; here , our proposed internal defense mechanism could be employed to defend against such attacks . 
   in our experiments , we first implement a prototype system , and then construct a massive - scale testbed to verify the properties of our prototype system .      * internal defense . 
   * we implement an internal defense prototype system including all basic modules described in section  [ sec : internaldefenses ] . here 
   , a phagocyte monitors each of its connected p2p hosts latest @xmath42 requests . 
   firstly , if more than half of the managed p2p hosts perform similar behaviors , the responsible phagocyte considers that the managed zone is being exploited by worm attackers . secondly 
   , if more than half of a phagocyte s neighboring phagocytes perform the similar operations , the phagocyte considers its neighboring phagocytes are being exploited by worm attackers . in particular , the similarity is measured based on the equation  [ eqn : sim ] with a threshold @xmath19 of @xmath43 . then , in the local isolation module , if a phagocyte has detected worm attacks , the phagocyte will cut off the associated links between the infection zone and the connected p2p hosts . 
   afterwards , in the alert propagation module , if a phagocyte has detected any worm attacks , it will broadcast a worm alert to all its neighboring phagocytes ; further , if a phagocyte receives more than half of its neighboring phagocytes worm alerts , i.e. , @xmath44 , the phagocyte will also broadcast the alert to all its neighboring phagocytes that did not send out the alert . 
   finally , in the software patching module , the phagocytes acquire the patches from the closest one of the system maintainers ( i.e. , @xmath42 online trusted phagocytes in our testbed ) , and then distribute them to all their managed p2p hosts . 
   we have not yet integrated the signature scheme into the software patching module of our prototype system . 
   note that , in the above , we simply set the parameters used in our prototype system , and in real - world systems , the system designers should appropriately tune these parameters according to their specific requirements 
   .    * external protection . * 
   we utilize our adaptive and interaction - based computational puzzle module to develop the external protection prototype system . in this prototype system , we use sha1 as the cryptographic hash function . generally , solving a puzzle with difficulty level 
   @xmath26 will force an external host to perform @xmath45 sha1 computations on average . 
   in particular , the difficulty level @xmath26 varies between @xmath38 and @xmath46 in our system  this will cost an external host @xmath47 second ( @xmath48 ) to @xmath49 seconds ( @xmath50 ) on our power5 cpus . 
   in addition , the change cycle of the puzzle - related parameters is set to @xmath51 minutes . 
   yet , we have not integrated our prototype system with the scalable distributed dns system , and this work will be part of our future work . 
   we use the realistic network traces crawled from a million - node gnutella network by the cruiser  @xcite crawler . 
   the dedicated massive scale gnutella network is composed of two tiers including the ultra - peer tier and leaf - peer tier . for historical reasons , 
   the ultra - peer tier consists of not only modern ultra - peers but also some _ legacy - peers _ that reside in the ultra - peer tier but can not accept any leaf - peers . 
   specifically , in our experiments , the ultra - peers excluding legacy - peers perform the functions of phagocytes , and the leaf - peers act as the managed p2p hosts .    then , we adopt the widely accepted gt - itm  @xcite to generate the transit - stub model consisting of @xmath52 routers for the underlying hierarchical internet topology . 
   there are @xmath53 transit domains at the top level with an average of @xmath53 routers in each , and a link between each pair of these transit routers has a probability of @xmath43 . 
   each transit router has an average of @xmath53 stub domains attached , and each stub has an average of @xmath53 routers , with the link between each pair of stub routers having a probability of @xmath54 . 
   there are two million end - hosts uniformly assigned to routers in the core by local area network ( lan ) links . 
   the delay of each lan link is set to @xmath51ms and the average delay of core links is @xmath55ms . 
   now , the crawled gnutella networks can model the realistic p2p overlay , and the generated gt - itm network can model the underlying internet topology ; thus , we deploy the crawled gnutella networks upon the underlying internet topology to simulate the realistic p2p network environment . 
   we do not model queuing delay , packet losses and any cross network traffic because modeling such parameters would prevent the massive - scale network simulation .    as shown in table  [ 
   tab : trace ] , we list various gnutella traces that we use in our experiments  with different node populations and/or different percentages of phagocytes . 
   @xmath27 _ trace _ 1 : crawled by cruiser on sep . 
   27th , 2004 . 
   @xmath27 _ trace _ 2 : crawled by cruiser on feb . 
   2nd , 2005 . 
   @xmath27 _ trace _ 3 : based on trace 1 , we remove a part of phagocytes randomly ; then , we remove the _ 
   isolated _ phagocytes , i.e. , these phagocytes do not connect to any other phagocytes ; finally , we further remove the isolated managed p2p hosts , i.e. , these managed p2p hosts do not connect to any phagocytes . 
   @xmath27 _ trace _ 4 : based on trace 3 , we remove a part of managed p2p hosts randomly . 
   @xmath27 _ trace _ 5 : based on trace 4 , we further remove a part of managed p2p hosts randomly . 
   @xmath27 _ trace _ 6 : based on trace 1 , we use the same method as described in the generation process of trace 3 . 
   in addition , we remove an extra part of managed p2p hosts . 
   in our experiments , we characterize the performance under various different circumstances by using three metrics :    @xmath27 _ peak infection percentage of all p2p hosts _ : the ratio of the maximum number of infected p2p hosts to the total number of p2p hosts . 
   this metric indicates whether phagocytes can effectively defend against internal attacks . 
   @xmath27 _ blowup factor of latency _ : this factor is the latency penalty between the external hosts and the p2p overlay via the phagocytes and direct routing . 
   this indicates the efficiency of our phagocytes to filter the requests from external hosts to the p2p overlay . 
   @xmath27 _ percentage of successful external attacks _ : the ratio of the number of successful external attacks to the total number of external attacks . 
   this metric indicates the effectiveness of our phagocytes to prevent external hosts from attacking the p2p overlay .                      in our prototype system , we model a percentage of phagocytes and managed p2p hosts being initially _ immune _ , respectively ; except these immune p2p hosts , the other hosts are _ 
   vulnerable_. moreover , there are a percentage of p2p hosts being initially _ infected _ , which are distributed among these vulnerable phagocytes and vulnerable managed p2p hosts uniformly at random . 
   all the infected p2p hosts perform the active p2p worm attacks ( described in section  [ subsec : threat_model ] ) , and meanwhile , our internal defense modules deployed at each participant try to defeat such attacks . with different experimental parameters described in table  [ tab : ex_in ] , we conduct four different experiments to evaluate the internal defense mechanism . 
   * experiment 1  impact of immune phagocytes : * with seven different initial percentages of immune phagocytes , we fix the initial percentage of immune managed p2p hosts to @xmath56 , and vary the number of initial infected p2p hosts so that these infected hosts make up between @xmath57 and @xmath58 of all the vulnerable p2p hosts . 
   now , we can investigate the impact of immune phagocytes by calculating the peak infection percentage of all p2p hosts . 
   the experimental result shown in figure  [ fig : ex1 ] demonstrates that when the initial infection percentage of all vulnerable p2p hosts is low ( e.g. , @xmath59 ) , the phagocytes can provide a good containment of active p2p worms ; otherwise , the worm propagation is very fast , but the phagocytes could still provide the sufficient containment  this property is also held in the following experiments . 
   interestingly , the initial percentage of immune phagocytes does not influence the performance of our system significantly , i.e. , the percentage of phagocytes being initially immune has no obvious effect . 
   this is a good property because we do not actually need to have high initial percentage of immune phagocytes . 
   also , this phenomenon implies that increasing the number of immune phagocytes does not further provide much significant defense . 
   thus , we can clearly conclude that the phagocytes are effective and scalable in performing detection , local isolation , alert propagation and software patching . 
   * experiment 2  impact of immune managed p2p hosts : * in this experiment , for @xmath60 of phagocytes being initially immune , we investigate the performance of our system with various initial percentages of immune managed p2p hosts in steps of @xmath56 . the result shown in figure 
   [ fig : ex2 ] is within our expectation . 
   the peak infection percentage of all p2p hosts decreases with the growth of the initial percentage of immune managed p2p hosts . 
   actually , in real - world overlay networks , even a powerful attacker could initially control tens of thousands of overlay hosts ( @xmath61  @xmath62 in the x - axis ) ; hence , we conclude that our phagocytes have the capacity of defending against active p2p worms effectively even in a highly malicious environment . 
   * experiment 3  impact of network scale : * figure  [ fig : ex3 ] plots the performance of our system in terms of different network scales . in traces 1 , 2 , 5 and 6 
   , there are different node populations , but the ratios of the number of phagocytes to the number of all p2p hosts are all around @xmath63 . 
   the experimental result indicates that our system can indeed help defend against active p2p worms in various overlay networks with different network scales . 
   furthermore , although the phagocytes perform more effectively in smaller overlay networks ( e.g. , traces 5 and 6 ) , they can still work quite well in massive - scale overlay networks with million - node participants ( e.g. , traces 1 and 2 ) . 
   * experiment 4  impact of the percentage of phagocytes : * in our system , the phagocytes perform the functions of defending against p2p worms . in this experiment 
   , we evaluate the system performance with different percentages of phagocytes but the same number of phagocytes . 
   the result in figure  [ fig : ex4 ] indicates that the higher percentage of phagocytes , the better security defense against active p2p worms . 
   that is , as the percentage of phagocytes increases , we can persistently improve the security capability of defending against active p2p worms in the overlay network . further 
   , the experimental result also implies that we do not need to have a large number of phagocytes to perform the defense functions  around @xmath56 of the node population functioning as phagocytes is sufficient for our system to provide the effective worm containment .      in this section 
   , we conduct two more experiments in our prototype system to evaluate the performance of the external protection mechanism . 
   * experiment 5  efficiency : * in this experiment , we show the efficiency in terms of the latency penalty between the external hosts and the p2p overlay via the phagocytes and direct routing . 
   based on trace 1 , we have @xmath42 external hosts connect to every p2p host via the phagocytes and direct routing in turn . 
   then , we measure the latencies for both cases .    figure  [ fig : ex5 ] plots the measurement result of latency penalty . 
   we can see that , if routing via the phagocytes , about @xmath64 and @xmath65 of the connections between the external hosts and p2p hosts have the blowup factor of latency be less than @xmath66 and @xmath67 , respectively . 
   figure  [ fig : ex5a ] shows the corresponding absolute latency difference , from which we can further deduce that the average latency growth of more than half of these connections ( via the phagocytes ) is less than @xmath68ms . 
   actually , due to the interaction required by our proposed computational puzzle scheme , we would expect some latency penalty incurred by routing via the phagocytes . with the puzzle scheme , our system can protect against external attacks effectively which we will illustrate in the next experiment . 
   hence , there would be a tradeoff between the efficiency and effectiveness .    * experiment 6  effectiveness : * in this experiment , based on trace 1 , we have @xmath42 external worm attackers flood all phagocytes in the p2p overlay . 
   then , we evaluate the percentage of successful external attacks to show the effectiveness of our protection mechanism against external hosts attacking the p2p overlay . for other numbers of external worm attackers , 
   we obtain the similar experimental results .    in figure  [ 
   fig : ex6 ] , the x - axis is the attack frequency in terms of the speed of external hosts mounting worm attacks to the p2p overlay , and the y - axis is the percentage of successful external attacks . 
   the result clearly illustrates the effectiveness of phagocytes in protecting the p2p overlay from external worm attacks . 
   our adaptive and interaction - based computational puzzle module at the phagocytes plays an important role in contributing to this observation . even in an extremely malicious environment , 
   our system is still effective . 
   that is , to launch worm attacks , the external attackers have no alternative but to solve hard computational puzzles which will incur heavy burden on these attackers . from the figure  [ fig : ex6 ] 
   , we can also find that when the attack frequency decreases , the percentage of successful external attacks increases gradually . 
   however , with a low attack frequency , the attackers can not perform practical attacks . 
   even if a part of external attacks are mounted successfully , our internal defense mechanism can mitigate them effectively . 
   p2p worms could exploit the perversive p2p overlays to achieve fast worm propagation , and recently , many p2p worms have already been reported to employ real - world p2p systems as their spreading platforms  @xcite . 
   the very first work in  @xcite highlighted the dangers posed by p2p worms and studied the feasibility of self - defense and containment inside the p2p overlay . 
   afterwards , several studies  @xcite developed mathematical models to understand the spreading behaviors of p2p worms , and showed that p2p worms , especially the active p2p worms , indeed pose more deadly threats than normal scanning worms .    recognizing such threats 
   , many researchers started to study the corresponding defense mechanisms . 
   specifically , yu _ et al . 
   _ in  @xcite presented a region - based active immunization defense strategy to defend against active p2p worm attacks ; freitas _ et al . 
   _ in  @xcite utilized the diversity of participating hosts to design a worm - resistant p2p overlay , verme , for containing possible p2p worms ; moreover , in  @xcite , xie and zhu proposed a partition - based scheme to proactively block the possible worm spreading as well as a connected dominating set based scheme to achieve fast patch distribution in a race with the worm , and in  @xcite , xie _ et al . 
   _ further designed a p2p patching system through file - sharing mechanisms to internally disseminate security patches . 
   however , existing defense mechanisms generally focused on the internal p2p worm defense without the consideration of external worm attacks , so that they can not provide a total worm protection for the p2p overlay systems . 
   in this paper , we have addressed the deadly threats posed by active p2p worms which exploit the pervasive and popular p2p applications for rapid topological worm infection . 
   we build an immunity system that responds to the active p2p worm infection by using _ 
   phagocytes_. the phagocytes are a small subset of specially elected p2p hosts that have high immunity and can `` eat '' active p2p worms in the p2p overlay networks . 
   each phagocyte manages a group of p2p hosts by monitoring their connection patterns and traffic volume . 
   if any worm events are detected , the phagocyte will invoke the internal defense strategies for local isolation , alert propagation and software patching . 
   besides , the phagocytes provide the access control and filtering mechanisms for the communication establishment between the p2p overlay and external hosts . 
   the phagocytes forbid the p2p traffic to leak from the p2p overlay to external hosts , and further adopt a novel adaptive and interaction - based computational puzzle scheme to prevent external hosts from attacking the p2p overlay . to sum up 
   , our holistic immunity system utilizes the phagocytes to achieve both internal defense and external protection against active p2p worms . 
   we implement a prototype system and validate its effectiveness and efficiency in massive - scale p2p overlay networks with realistic p2p network traces .
summary: active peer - to - peer ( p2p ) worms present serious threats to the global internet by exploiting popular p2p applications to perform rapid topological self - propagation . 
   active p2p worms pose more deadly threats than normal scanning worms because they do not exhibit easily detectable anomalies , thus many existing defenses are no longer effective . 
   we propose an immunity system with _ phagocytes _  a small subset of elected p2p hosts that are immune with high probability and specialized in finding and `` eating '' worms in the p2p overlay . 
   the phagocytes will monitor their managed p2p hosts connection patterns and traffic volume in an attempt to detect active p2p worm attacks . 
   once detected , local isolation , alert propagation and software patching will take place for containment . 
   the phagocytes further provide the access control and filtering mechanisms for communication establishment between the internal p2p overlay and the external hosts . 
   we design a novel adaptive and interaction - based computational puzzle scheme at the phagocytes to restrain external worms attacking the p2p overlay , without influencing legitimate hosts experiences significantly . 
   we implement a prototype system , and evaluate its performance based on realistic massive - scale p2p network traces . 
   the evaluation results illustrate that our phagocytes are capable of achieving a total defense against active p2p worms .